Optimizing two-pass connected-component labeling algorithms

We present two optimization strategies to improve connected-component labeling algorithms. Taking together, they form an efficient two-pass labeling algorithm that is fast and theoretically optimal. The first optimization strategy reduces the number of neighboring pixels accessed through the use of a decision tree, and the second one streamlines the union-find algorithms used to track equivalent labels. We show that the first strategy reduces the average number of neighbors accessed by a factor of about 2. We prove our streamlined union-find algorithms have the same theoretical optimality as the more sophisticated ones in literature. This result generalizes an earlier one on using union-find in labeling algorithms by Fiorio and Gustedt (Theor Comput Sci 154(2):165–181, 1996). In tests, the new union-find algorithms improve a labeling algorithm by a factor of 4 or more. Through analyses and experiments, we demonstrate that our new two-pass labeling algorithm scales linearly with the number of pixels in the image, which is optimal in computational complexity theory. Furthermore, the new labeling algorithm outperforms the published labeling algorithms irrespective of test platforms. In comparing with the fastest known labeling algorithm for two-dimensional (2D) binary images called contour tracing algorithm, our new labeling algorithm is up to ten times faster than the contour tracing program distributed by the original authors.

Kenji SuzukiEmail:

---

Kesheng Wu   is a staff computer scientist at Lawrence Berkeley National Laboratory. His work primarily involves data management, data analyses and scientific computing. He is the lead developer of FastBit bitmap indexing software for searching over large datasets. He also led the development of a software package call TRLan, which computes eigenvalues of large symmetric matrices on parallel machines. He received a Ph.D. in computer science from the University of Minnesota, an M.S. in physics from the University of Wisconsin-Milwaukee, and a B.S. in physics from Nanjing University, China. His homepage on the web is . Ekow Otoo   holds a B.Sc. degree in Electrical Engineering from the University of Science and Technology, Kumasi, Ghana, and a Ph.D. degree in Computer Science from McGill University, Montreal, Canada. From 1987 to 1999, he was a tenured faculty at Carleton University, Ottawa, Canada. He has served as a consultant to Bell Northern Research, and the GIS Division, Geomatics Canada. He is presently a consultant with Mathematical Sciences Research Institute, Ghana, and a staff scientist/engineer, LBNL, Berkeley. He is a member of the ACM and IEEE. His research interests include database management, data structures, algorithms, parallel and distributed computing. Kenji Suzuki   received his Ph.D. degree from Nagoya University in 2001. In 2001, he joined Department of Radiology at University of Chicago. Since 2006, he has been Assistant Professor of Radiology, Medical Physics, and Cancer Research Center. His research interests include computer-aided diagnosis, machine learning, and pattern recognition. He published 110 papers including 45 journal papers. He has served as an associate editor for three journals and a referee for 17 journals. He received Paul Hodges Award, RSNA Certificate of Merit Awards, Cancer Research Foundation Young Investigator Award, and SPIE Honorable Mention Award. He is a Senior Member of IEEE.