×

An algorithm for connected-component labeling, hole labeling and Euler number computing. (English) Zbl 1280.68287

Summary: 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.

MSC:

68U10 Computing methodologies for image processing
68T45 Machine vision and scene understanding
68T10 Pattern recognition, speech recognition
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gonzalez R C, Woods R E. Digital Image Processing (3rd edition). Addison-Wesley, 1992.
[2] Ronsen C (1984) Denjiver P A. Connected Components in Binary Images: The Detection Problem. John Wiley & Sons. Inc., New York, USA
[3] Hashizume A, Suzuki R, Yokouchi H et al (1990) An algorithm of automated RBC classification and its evaluation. Bio Medical Engineering 28(1):25–32
[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 difference threshold strategies and shadow detection. In Proc. British Machine Vision Conference, September 1995, pp.347–356.
[6] Nayar SK, Bolle RM (1996) Reflectance-based object recognition. International Journal of Computer Vision 17(3):219–240 · Zbl 05476067 · doi:10.1007/BF00128232
[7] Horn B K P. Robot Vision. New York: McGraw-Hill Higher Education, 1986, pp.73–77.
[8] Lumia R, Shapiro L, Zungia O (1983) A new connected components algorithm for virtual memory computers. Comput Vision, Graphics and Image Processing 22(2):287–300 · doi:10.1016/0734-189X(83)90071-3
[9] Rosenfeld A, Pfalts JL (1996) Sequential operations in digital picture processing. Journal of ACM 13(4):471–494
[10] Rosenfeld A, Kak AC (1982) Digital Picture Processing, vol 2, 2nd edn. Academic Press, San Diego, USA · Zbl 0564.94002
[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 (2003) Linear-time connected-component labeling based on sequential local operations. Computer Vision and Image Understanding 89(1):1–23 · Zbl 1038.68107 · doi:10.1016/S1077-3142(02)00030-9
[13] Wu K, Otoo E, Suzuki K (2009) Optimizing two-pass connected-component labeling algorithms. Pattern Analysis & Applications 12(2):117–135 · Zbl 05802721 · doi:10.1007/s10044-008-0109-y
[14] He L, Chao Y, Suzuki K, Wu K (2009) Fast connected-component labeling. Pattern Recognition 42(9):1977–1987 · Zbl 1192.68577 · doi:10.1016/j.patcog.2008.10.013
[15] He L, Chao Y, Suzuki K (2010) An efficient first-scan method for label-equivalence-based labeling algorithms. Pattern Recognition Letters 31(1):28–35 · doi:10.1016/j.patrec.2009.08.012
[16] Ballard D H, Brown C M. Computer Vision. Prentice-Hall, 1982.
[17] Chang F, Chen CJ, Lu CJ (2004) A linear-time component-labeling algorithm using contour tracing technique. Computer Vision and Image Understanding 93(2):206–220 · Zbl 02040458 · doi:10.1016/j.cviu.2003.09.002
[18] Hu Q, Qian G, Nowinski WL (2005) Fast connected-component labeling in three-dimensional binary images based on iterative recursion. Computer Vision and Image Understanding 99(3):414–434 · doi:10.1016/j.cviu.2005.04.001
[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 MH, Yan PF (1988) A fast algorithm to calculate the Euler number for binary image. Pattern Recognition Letters 8(5):295–297 · Zbl 0664.68098 · doi:10.1016/0167-8655(88)90078-5
[23] Díaz-De-León SJL, Sossa-Azuela JH (1996) On the computation of the Euler number of a binary object. Pattern Recognition 29(3):471–476 · Zbl 05476033 · doi:10.1016/0031-3203(95)00098-4
[24] Di Zenzo S, Cinque L, Levialdi S (1996) Run-based algorithms for binary image analysis and processing. IEEE Transactions on PAMI 18(1):83–89 · Zbl 05110529 · doi:10.1109/34.476016
[25] Gray SB (1971) Local properties of binary images in two dimensions. IEEE Transactions on Computers 20(5):551–561 · Zbl 0216.50101 · doi:10.1109/T-C.1971.223289
[26] Pratt W K. Digital Image Processing. New York: John Wiley & Sons, Inc., 1991, p.633. · Zbl 0728.68142
[27] Otsu N (1979) A threshold selection method from gray-level histograms. IEEE Trans Syst, Man and Cybernet 9(1):62–66 · doi:10.1109/TSMC.1979.4310076
[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 JK, Ajjanagadde VG (1990) Boundary and object labeling in three-dimensional images. Comput Vision, Graphics, and Image Processing 51(3):355–369 · doi:10.1016/0734-189X(90)90008-J
[31] He L, Chao Y, Suzuki K (2011) Two efficient label-equivalence-based connected-component labeling algorithms for 3-dimensional binary images. IEEE Transactions on Image Processing 20(8):2122–2134 · Zbl 1372.94108 · doi:10.1109/TIP.2011.2114352
[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 (2007) A co-processor for computing the Euler number of a binary image using divide-and-conquer strategy. Fundamental Informaticae 76(1/2):75–89 · Zbl 1111.68141
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.