Optimizing connected component labeling algorithms

Kesheng Wu; Ekow Otoo; Arie Shoshani

doi:10.1117/12.596105

29 April 2005 Optimizing connected component labeling algorithms

Kesheng Wu, Ekow Otoo, Arie Shoshani

Proceedings Volume 5747, Medical Imaging 2005: Image Processing; (2005) https://doi.org/10.1117/12.596105
Event: Medical Imaging, 2005, San Diego, California, United States

Abstract

This paper presents two new strategies that can be used to greatly improve the speed of connected component labeling algorithms. To assign a label to a new object, most connected component labeling algorithms use a scanning step that examines some of its neighbors. The first strategy exploits the dependencies among them to reduce the number of neighbors examined. When considering 8-connected components in a 2D image, this can reduce the number of neighbors examined from four to one in many cases. The second strategy uses an array to store the equivalence information among the labels. This replaces the pointer based rooted trees used to store the same equivalence information. It reduces the memory required and also produces consecutive final labels. Using an array instead of the pointer based rooted trees speeds up the connected component labeling algorithms by a factor of 5 ~ 100 in our tests on random binary images.

Citation Download Citation

Kesheng Wu, Ekow Otoo, and Arie Shoshani "Optimizing connected component labeling algorithms", Proc. SPIE 5747, Medical Imaging 2005: Image Processing, (29 April 2005); https://doi.org/10.1117/12.596105

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