A New Connected-Component Labeling Algorithm


Share / Export Citation / Email / Print / Text size:

International Journal of Advanced Network, Monitoring and Controls

Xi'an Technological University

Subject: Computer Science, Software Engineering


eISSN: 2470-8038





Volume / Issue / page

Related articles

VOLUME 1 , ISSUE 1 (June 2016) > List of articles

A New Connected-Component Labeling Algorithm

Yuyan Chao / Lifeng He / Kenji Suzuki / Qian Yu / Wei Tang

Keywords : connected component, labeling, pattern recognition

Citation Information : International Journal of Advanced Network, Monitoring and Controls. Volume 1, Issue 1, Pages 0-0, DOI: https://doi.org/10.21307/ijanmc-2016-008

License : (CC BY-NC-ND 4.0)

Published Online: 01-April-2018



This paper proposes a new first-scan method for two-scan labeling algorithms. In the first scan, our proposed method first scans image lines three by three with a leaving line, and for foreground pixels among each three lines, assigns them provisional labels, and finds and resolves label equivalences among them. Then, it processes the leaving lines from top to bottom one by one, and for each line, assigns foreground pixels on the line provisional labels, finding and resolving label equivalences between the foreground pixels and those on the lines immediately above and below the current line. Experimental results demonstrated that our method is more efficient than conventional label-equivalence-based labeling algorithms.

Content not available PDF Share



C. Ronsen and P. A. Denjiver. Connected Components in Binary Images: The Detection Problem, Research Studies Press, 1984.


R. C. Gonzalez and R. E. Woods. Digital Image Processing. Addison Wesley, 1992.


K. Suzuki, I. Horiba, and N. Sugie. Linear-time connected-component labeling based on sequential local operations. Computer Vision and Image Understanding, 89:1-23, 2003.


A. Rosenfeld and J. L. Pfalts. Sequential operations in digital picture processing. Journal of ACM, 13(4):471-494, October 1966.


L. He, Y. Chao, and K. Suzuki. A Run-based Two-Scan Labeling Algorithm. IEEE Transactions on Image Processing, 17(5):749-756, 2008


L. He, Y. Chao, and K. Suzuki, K. Wu. Fast Connected-Component Labeling. Pattern Recognition, 42 (2009):1977


L. He, Y. Chao, and K. Suzuki. An Efficient First-Scan Method for Label-Equivalence-Based Labeling Algorithms. Pattern Recognition Letters, 31:28-35, 2010.


L. He, Y. Chao, and K. Suzuki. A Run-Based One-and-a-Half-Scan Connected-Component Labeling Algorithm. International Journal of Pattern Recognition and Artificial Intelligence, Vol. 24, No. 4(2010), pp.557-579.


L. He, Y. Chao, and K. Suzuki. Two Efficient Label-Equivalence-Based Connected-Component Labeling Algorithms for Three-Dimensional Binary Images. IEEE Transactions on Image Processing, 20( 8), 2011, DOI:. 10.1109/TIP.2011.2114352.


F. Chang, C. J. Chen, and C. J. Lu. A linear-time component-labeling algorithm using contour tracing technique. Computer Vision and Image Understanding, 93:206-220, 2004.


Q. Hu, G. Qian and W. L. Nowinski, Fast connected-component labeling in three-dimensional binary images based on iterative recursion. Computer Vision and Image Understanding, 99:414-434, 2005


A. Alexey, K. Tomas, W. Florentin, and D. Babette. Real-Time Image Segmentation on a GPU. Facing the Multicore-Challenge, Lecture Notes in Computer Science, 6310:131-142, 2011, Springer Berlin / Heidelberg.


Christopher Wolfe, T. C. Nicholas Graham, and Joseph A. Pape. Seeing through the fog: an algorithm for fast and accurate touch detection in optical tabletop surfaces. In ACM International Conference on Interactive Tabletops and Surfaces (ITS '10). ACM, 73-82, 2010, New York, NY, USA.