1 July 1998 Parallel image component labeling for target acquisition
Author Affiliations +
Optical Engineering, 37(7), (1998). doi:10.1117/1.601713
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.
Vipin Chaudhary, Jake K. Aggarwal, "Parallel image component labeling for target acquisition," Optical Engineering 37(7), (1 July 1998). http://dx.doi.org/10.1117/1.601713

Image processing

Binary data

Optical engineering

Computer architecture

Computer vision technology

Data communications

Machine vision


Assessment of target detection limits in hyperspectral data
Proceedings of SPIE (October 21 2015)
Motion estimation for coding of moving video at 8 kbit...
Proceedings of SPIE (September 01 1990)
Modeling the radiance of the moon for on-orbit calibration
Proceedings of SPIE (November 10 2003)
On-board target acquisition for CHEOPS
Proceedings of SPIE (July 26 2016)

Back to Top