A fast and memory-efficient two-pass connected-component labeling algorithm for binary images

Connected-component labeling is an important process in image analysis and pattern recognition. It aimsto deduct the connected components by giving a unique label value for each individual component. Many algorithms have been proposed, but they still face several problems such as slow execution time, falling in the pipeline, requiring a huge amount of memory with high resolution, being noisy, and giving irregular images. In this work, a fast and memoryefficient connected-component labeling algorithm for binary images is proposed. The proposed algorithm is based on a new run-base tracing method with a new resolving process to find the final equivalent label values. A set of experiments were conducted on different types of binary images. The proposed algorithm showed high performance compared to the other algorithms.

PDF

___

[1] Soh Y, Ashraf H, Hae Y, Kim I. A hybrid approach to parallel connected component labeling using cuda. International Journal of Signal Processing Systems 2013; 1 (2): 130-135.
[2] Di Stefano L, Bulgarelli A. A simple and efficient connected components labeling algorithm. In: IEEE International Conference Proceedings in Image Analysis and Processing; Venice, Italy; 1999. pp. 322-327.
[3] Rakhmadi A, Othman Z. Bade A, Rahim M, Amin I. Connected component labeling using components neighborsscan labeling approach. Journal of Computer Science 2010; 6 (10): 1070-1078.
[4] He L, Chao Y. A very fast algorithm for simultaneously performing connected-component labeling and Euler number computing. IEEE Transactions on Image Processing 2015; 24 (9): 2725-2735. doi: 10.1109/TIP.2015.2425540
[5] He L, Chao Y, Suzuki K. A run-based two-scan labeling algorithm. IEEE Transactions on Image Processing 2008; 17 (5): 749-756. doi: 10.1109/TIP.2008.919369
[6] Eusse JF, Leupers R, Ascheid G, Sudowe P, Leibe B, Sadasue T. A flexible ASIP architecture for connected components labeling in embedded vision applications. In: IEEE Design, Automation and Test in Europe Conference and Exhibition; Dresden, Germany; 2014. pp. 1-6.
[7] He L, Chao Y, Suzuki K. An algorithm for connected-component labeling, hole labeling and Euler number computing. Journal of Computer Science and Technology 2013; 28 (3): 468-478. doi.org/10.1007/s11390-013-1348-y
[8] Klaiber M, Rockstroh L, Wang Z, Baroud Y, Simon S. A memory-efficient parallel single pass architecture for connected component labeling of streamed images. In: International Conference on In Field-Programmable Technology; Seoul, South Korea; 2012. pp. 159-165.
[9] Lacassagne L, Zavidovique B. Light speed labeling: efficient connected component labeling on rise architectures. Journal of Real-Time Image Processing 2011; 6 (2): 117-135. doi.org/10.1007/s11554-009-0134-0
[10] He L, Chao Y, Suzuki K. An efficient first-scan method for label-equivalence-based labeling algorithms. Pattern Recognition Letters 2010; 31 (1): 28-35. doi.org/10.1016/j.patrec.2009.08.012
[11] He L, Chao Y, Suzuki K. A new two-scan algorithm for labeling connected components in binary images. In: IEEE Proceedings of the World Congress on Engineering; London, UK; 2012. pp. 1141-1146.
[12] Grana C, Borghesani D, Cucchiara R. Connected component labeling techniques on modern architectures. In: International Conference on Image Analysis and Processing Image Analysis and Processing; Italy; 2009. pp. 816- 824.
[13] Cabaret L, Lacassagne L, Oudni L. A review of world’s fastest connected component labeling algorithms: Speed and energy estimation. In: IEEE Conference in Design and Architectures for Signal and Image Processing; Madrid, Spain; 2014. pp. 1-6.
[14] Hashmi MF, Pal R, Saxena R, Keskar AG. A new approach for real time object detection and tracking on high resolution and multi-camera surveillance videos using GPU. Journal of Central South University 2016; 23 (1): 130-144. doi.org/10.1007/s11771-016-3056-6
[15] Walczyk R, Armitage A, Binnie TD. Comparative study on connected component labeling algorithms for embedded video processing systems. In: International Conference in Image Processing, Computer Vision, and Pattern Recognition; Las Vegas, NV, USA; 2010. pp. 176-183.
[16] Rosenfeld A, Pfaltz JL. Sequential operations in digital picture processing. Journal of the ACM 1966; 13 (4): 471-494.
[17] Gotoh T, Ohta Y, Yoshida M, Shirai Y. Component labeling algorithm for video rate processing. In: Hague International Symposium, International Society for Optics and Photonics; Hague, the Netherlands; 1987. pp. 217- 224.
[18] Wu K, Otoo E, Suzuki K. Optimizing two-pass connected-component labeling algorithms. Pattern Analysis and Applications 2009; 12 (2): 117-135. doi.org/10.1007/s10044-008-0109-y
[19] Shima Y, Murakami T, Koga M, Yashiro H, Fujisawa H. A high-speed algorithm for propagation-type labeling based on block sorting of runs in binary images. In: 10th IEEE International Conference in Pattern Recognition; Atlantic City, NJ, USA; 1990. pp. 655-658.
[20] Devi GG, Sumathi CP. Positional connected component-labeling algorithm. Indian Journal of Science and Technology 2014; 7 (3): 306-311.
[21] Bailey DG, Johnston CT. Single pass connected components analysis. In: Proceedings of Image and Vision Computing New Zealand; Hamilton, New Zealand; 2007. pp. 282-287.
[22] Chang F, Chen CJ, Lu CJ. A linear-time component-labeling algorithm using contour tracing technique. Computer Vision and Image Understanding 2004; 93 (2): 206-220.
[23] Chang F, Chen CJ. A component-labeling algorithm using contour tracing technique. In: 7th IEEE International Conference on Document Analysis and Recognition; Edinburgh, UK; 2003. pp. 741-745.
[24] Pavlidis T. Algorithms for Graphics and Image Processing. Heidelberg, Germany: Springer Science & Business Media, 2012.
[25] Haralick RM. Some neighborhood operators. In: Real-Time Parallel Computing. Boston, MA, USA: Springer, 1981.
[26] Suzuki K, Horiba I, Sugie N. Linear-time connected-component labeling based on sequential local operations. Computer Vision and Image Understanding 2003; 89 (1): 1-23. doi.org/10.1016/S1077-3142(02)00030-9
[27] Wu K, Otoo E, Shoshani A. Optimizing connected component-labeling algorithms. In: Medical Imaging 2005: Image Processing. International Society for Optics and Photonics; San Diego, CA, USA; 2005. pp. 1965-1976.
[28] He L, Chao Y, Suzuki K, Wu K. Fast connected-component labeling. Pattern Recognition 2009; 42 (9): 1977-1987. doi.org/10.1016/j.patcog.2008.10.013
[29] Hernandez-Belmonte U, Ayala-Ramirez V, Sanchez-Yanez R. Enhancing CCL algorithms by using a reduced connectivity mask. In: Mexican Conference on Pattern Recognition; Querétaro, Mexico; 2013. pp. 195-203.
[30] Niblack W. An Introduction to Digital Image Processing. Englewood Cliffs, NJ, USA: Prentice-Hall, 1986.