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 backgroundpixels 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. Therepresentation 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 computationalcomplexity 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 connectedcomputer [O(log n)], a unidirectional and bidirectional mesh connected computer [O(n{sup}1/2)], and a hypercube computer [O(log n)] are discussed. The computational and communicational complexities of these implementations are computed, and are the bestyet 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.
展开▼
