Share Email Print
cover

Proceedings Paper

Optimizing connected component labeling algorithms
Author(s): Kesheng Wu; Ekow Otoo; Arie Shoshani
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper 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.

Paper Details

Date Published: 29 April 2005
PDF: 12 pages
Proc. SPIE 5747, Medical Imaging 2005: Image Processing, (29 April 2005); doi: 10.1117/12.596105
Show Author Affiliations
Kesheng Wu, Lawrence Berkeley National Lab. (United States)
Ekow Otoo, Lawrence Berkeley National Lab. (United States)
Arie Shoshani, Lawrence Berkeley National Lab. (United States)


Published in SPIE Proceedings Vol. 5747:
Medical Imaging 2005: Image Processing
J. Michael Fitzpatrick; Joseph M. Reinhardt, Editor(s)

© SPIE. Terms of Use
Back to Top