We use cookies to improve your experience with our site.

Indexed in:

SCIE, Ei, Scopus, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Li-Feng He, Yu-Yan Chao, Kenji Suzuki. An Algorithm for Connected-Component Labeling, Hole Labeling and Euler Number Computing[J]. Journal of Computer Science and Technology, 2013, 28(3): 468-478. DOI: 10.1007/s11390-013-1348-y
Citation: Li-Feng He, Yu-Yan Chao, Kenji Suzuki. An Algorithm for Connected-Component Labeling, Hole Labeling and Euler Number Computing[J]. Journal of Computer Science and Technology, 2013, 28(3): 468-478. DOI: 10.1007/s11390-013-1348-y

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

Funds: 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.
More Information
  • Received Date: March 06, 2012
  • Revised Date: January 06, 2013
  • Published Date: May 04, 2013
  • 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.

Catalog

    Article views (16) PDF downloads (2117) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return