›› 2013, Vol. 28 ›› Issue (3): 468-478.doi: 10.1007/s11390-013-1348-y

Special Issue: Computer Graphics and Multimedia

• Graphics, Visualization, and Image Processing • Previous Articles     Next Articles

An Algorithm for Connected-Component Labeling, Hole Labeling and Euler Number Computing

Li-Feng He1,2 (何立风), Senior Member, IEEE, Yu-Yan Chao1,3 (巢宇燕), and Kenji Suzuki4, Senior Member, IEEE   

  1. 1. Artificial Intelligence Institute, College of Electrical and Information Engineering, Shaanxi University of Science and Technology, Xi'an 710021, China;
    2. Faculty of Information Science and Technology, Aichi Prefectural University, Aichi 4801198, Japan;
    3. Faculty of Environment, Information and Business, Nagoya Sangyo University, Aichi 4888711, Japan;
    4. Department of Radiology, The University of Chicago, IL 60637, U.S.A.
  • Received:2012-03-07 Revised:2013-01-07 Online:2013-05-05 Published:2013-05-05
  • Contact: 10.1007/s11390-013-1348-y
  • Supported by:

    This work was supported in part by the Grant-in-Aid for Scientific Research (C) of the Ministry of Education, Science, Sports and Culture of Japan under Grant No. 23500222.

Labeling connected components and holes and computing the Euler number in a binary image are necessary for image analysis, pattern recognition, and computer (robot) vision, and are usually made independently of each other in conventional methods. This paper proposes a two-scan algorithm for labeling connected components and holes simultaneously in a binary image by use of the same data structure. With our algorithm, besides labeling, we can also easily calculate the number and the area of connected components and holes, as well as the Euler number. Our method is very simple in principle, and experimental results demonstrate that our method is much more efficient than conventional methods for various kinds of images in cases where both labeling and Euler number computing are necessary.

[1] Gonzalez R C, Woods R E. Digital Image Processing (3rd edition). Addison-Wesley, 1992.

[2] Ronsen C, Denjiver P A. Connected Components in Binary Images: The Detection Problem. New York, USA: John Wiley & Sons. Inc., 1984.

[3] Hashizume A, Suzuki R, Yokouchi H et al. An algorithm of automated RBC classification and its evaluation. Bio. Medical Engineering, 1990, 28(1): 25-32. (In Japanese)

[4] Srihari S N. Document image understanding. In Proc. ACM Fall Joint Computer Conference, November 1986, pp.87-95.

[5] Rosin P L, Ellis T. Image di?erence threshold strategies and shadow detection. In Proc. British Machine Vision Conference, September 1995, pp.347-356.

[6] Nayar S K, Bolle R M. Reflectance-based object recognition. International Journal of Computer Vision, 1996, 17 (3): 219240.

[7] Horn B K P. Robot Vision. New York: McGraw-Hill Higher Education, 1986, pp.73-77.

[8] Lumia R, Shapiro L, Zungia O. A new connected components algorithm for virtual memory computers. Comput. Vision, Graphics and Image Processing, 1983, 22(2): 287-300.

[9] Rosenfeld A, Pfalts J L. Sequential operations in digital picture processing. Journal of ACM, 1996, 13(4): 471-494.

[10] Rosenfeld A, Kak A C. Digital Picture Processing (2nd edition), Vol. 2. San Diego, USA: Academic Press, 1982.

[11] Naoi S. High-speed labeling method using adaptive variable window size for character shape feature. In Proc. IEEE Asian Conf. Computer Vision, December 1995, pp.408-411.

[12] Suzuki K, Horiba I, Sugie N. Linear-time connectedcomponent labeling based on sequential local operations. Computer Vision and Image Understanding, 2003, 89(1): 123.

[13] Wu K, Otoo E, Suzuki K. Optimizing two-pass connectedcomponent labeling algorithms. Pattern Analysis & Applications, 2009, 12(2): 117-135.

[14] He L, Chao Y, Suzuki K, Wu K. Fast connected-component labeling. Pattern Recognition, 2009, 42(9): 1977-1987.

[15] 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.

[16] Ballard D H, Brown C M. Computer Vision. Prentice-Hall, 1982.

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

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

[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 Proc. the 10th Int. Conf. Pattern Recognition, June 1990, pp.655-658.

[20] Wolfe C, Nicholas Graham T C, Pape J A. Seeing through the fog: An algorithm for fast and accurate touch detection in optical tabletop surfaces. In Proc. ACM International Conference on Interactive Tabletops and Surfaces, November 2010, pp.73-82.

[21] Abramov A. Kulvicius T, Wörgötter F, Dellen B. Real-time image segmentation on a GPU. In Lecture Notes in Computer Science 6310, Keller R, Kramer D, Weiss J P (eds.), Springer-Verlag, 2011, pp.131-142.

[22] Chen M H, Yan P F. A fast algorithm to calculate the Euler number for binary image. Pattern Recognition Letters, 1988, 8(5): 295-297.

[23] Díaz-De-León S J L, Sossa-Azuela J H. On the computation of the Euler number of a binary object. Pattern Recognition, 1996, 29(3): 471-476.

[24] Di Zenzo S, Cinque L, Levialdi S. Run-based algorithms for binary image analysis and processing. IEEE Transactions on PAMI, 1996, 18(1): 83-89.

[25] Gray S B. Local properties of binary images in two dimensions, IEEE Transactions on Computers, 1971, 20(5): 551561.

[26] Pratt W K. Digital Image Processing. New York: John Wiley & Sons, Inc., 1991, p.633.

[27] Otsu N. A threshold selection method from gray-level histograms. IEEE Trans. Syst., Man and Cybernet, 1979, 9(1): 62-66.

[28] Dey S, Bhattacharya B B, Kundu M K, Acharya T. A fast algorithm for computing the Euler number of an image and its VLSI implementation. In Proc. the 13th Int. Conf. VLSI Design, January 2000, pp.330-335.

[29] Ito Y, Nakano K. Optimized component labeling algorithm for using in medium sized FPGAs. In Proc. the 9th Int. Conf. Parallel and Distributed Computing, Applications and Technologies, Dec. 2008, pp.171-176.

[30] Udupa J K, Ajjanagadde V G. Boundary and object labeling in three-dimensional images. Comput. Vision, Graphics, and Image Processing, 1990, 51 (3): 355-369.

[31] He L, Chao Y, Suzuki K. Two efficient label-equivalence-based connected-component labeling algorithms for 3-dimensional binary images. IEEE Transactions on Image Processing, 2011, 20(8): 2122-2134.

[32] Niknam M, Thulasiraman P, Camorlinga S. A parallel algorithm for connected component labeling of gray-scale images on homogeneous multicore architectures. Journal of Physics: Conference Series 256, 2010, 012010: 1-7.

[33] Dey S, Bhattacharya B, Kundu M, Bishnu A, Acharya T. A co-processor for computing the Euler number of a binary image using divide-and-conquer strategy. Fundamental Informaticae, 2007, 76(1/2): 75-89.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved