Parallel image component labeling for target acquisition

Vipin Chaudhary; Jake K. Aggarwal

doi:10.1117/1.601713

1 July 1998 Parallel image component labeling for target acquisition

Vipin Chaudhary, Jake K. Aggarwal

Optical Engineering, Vol. 37, Issue 7, (July 1998). https://doi.org/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.

Citation Download Citation

Vipin Chaudhary and Jake K. Aggarwal "Parallel image component labeling for target acquisition," Optical Engineering 37(7), (1 July 1998). https://doi.org/10.1117/1.601713

Published: 1 July 1998

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available