Share Email Print
cover

Optical Engineering

Parallel image component labeling for target acquisition
Format Member Price Non-Member Price
PDF $20.00 $25.00

Paper Abstract

An important step in target acquisition is to be able to label various unconnected objects (components) in the scene. We present new algorithms for labeling connected components in a binary image. Eight connectivity for object and background pixels is assumed. The sequential algorithm is described first. The computational complexity of the algorithm is linear (optimal) in the number of object pixels in the image. The memory requirement is also linear in the number of object pixels. The representation of the connected components used in the algorithm makes it easy to calculate certain properties of regions, i.e., area, perimeter, etc. The algorithm is then parallelized and implemented on a shared memory computer. The computational complexity of this parallel algorithm is O(é\log n?) for an image with n object pixels using n processors, and is the best achieved yet. The implementations of the algorithm on several distributed memory architectures, i.e., a binary tree connected computer [O(log n)], a unidirectional and bidirectional mesh connected computer [O(n1/2)], and a hypercube computer [O(log n)] are discussed. The computational and communicational complexities of these implementations are computed, and are the best yet achieved. The algorithm is easily extended for gray-level images without affecting the complexities. Results of the implementation on the sequent balance multiprocessor are presented.

Paper Details

Date Published: 1 July 1998
PDF: 13 pages
Opt. Eng. 37(7) doi: 10.1117/1.601713
Published in: Optical Engineering Volume 37, Issue 7
Show Author Affiliations
Vipin Chaudhary, Wayne State Univ. (United States)
Jake K. Aggarwal, Univ. of Texas/Austin (United States)


© SPIE. Terms of Use
Back to Top