Abstract
Connected component labeling (CCL) of binary images is one of the fundamental operations in real time applications. The adjacency tree (AdjT) of the connected components offers a region-based representation where each node represents a region which is surrounded by another region of the opposite color. In this paper, a fully parallel algorithm for computing the CCL and AdjT of a binary digital image is described and implemented, without the need of using any geometric information. The time complexity order for an image of \(m \times n\) pixels under the assumption that a processing element exists for each pixel is near \(O(log(m+n))\). Results for a multicore processor show a very good scalability until the so-called memory bandwidth bottleneck is reached. The inherent parallelism of our approach points to the direction that even better results will be obtained in other less classical computing architectures.
This work has been supported by the Spanish research projects MTM2016-81030-P (AEI/FEDER, UE) and TEC2012-37868-C04-02 of Ministerio de Economía y Competitividad and the VPPI of the University of Seville.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bhattacharya, P.: Connected component labeling for binary images on a reconfigurable mesh architecture. J. Syst. Arch. 42(4), 309–313 (1996)
Buneman, O.P.: A grammar for the topological analysis of plane figures. Mach. Intell. 15, 383–393 (1969)
Chiavetta, F., Di Gesù, V.: Parallel computation of the Euler number via connectivity graph. Pattern Recognit. Lett. 14, 849–859 (1993)
Diaz-del-Rio, F., Real, P., Onchis, D.: A parallel homological spanning forest framework for 2D topological image analysis. Pattern Recognit. Lett. 83, 49–58 (2016)
Cohn, A., Bennett, B., Gooday, J., Gotts, N.: Qualitative spacial representation and reasoning with the region connection calculus. GeoInformatica 1(3), 275–316 (1997)
Costanza, E., Robinson, J.: A region adjacency tree approach to the detection and design of fiducials. Video Vis. Graph., 63–99 (2003)
Cucchiara, R., Grana, C., Prati, A., Seidenari, S., Pellacani, G.: Building the topological tree by recursive FCM color clustering. In: 16th IEEE ICPR, vol. 1, pp. 759–762 (2002)
Gupta, S., Palsetia, D., Patwary, M.M.A., Agrawal, A., Choudhary, A.N.: A new parallel algorithm for two-pass connected component labeling. In: IEEE IPDP Symposium, pp. 1355–1362 (2014)
Heijmans, H.J.: Connected morphological operators for binary images. Comput. Vis. Imag. Understand. 73(1), 99–120 (1999)
Kalentev, O., Rai, A., Kemnitz, S., Schneider, R.: Connected component labeling on a 2D grid using CUDA. J. Parallel Distrib. Comput. 71, 615–620 (2011)
Kovalevsky, V.: Algorithms in digital geometry based on cellular topology. In: Klette, R., Žunić, J. (eds.) IWCIA 2004. LNCS, vol. 3322, pp. 366–393. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30503-3_27
Keshet, R.: Shape-tree semilattice. J. Math. Imag. Vis. 22(2–3), 309–331 (2005)
Murty, A., Natarajan, V., Vadhiyar, S.: Efficient homology computations on multicore and manycore systems. In: 20th Annual International Conference on High Performance Computing, pp. 333–342 (2013)
Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, Oxford (2017). NVIDIA, Cuda C best practices guide version. http://developer.nvidia.com/
Patwary, M., Ali, M., Refsnes, P., Manne, F.: Multi-core spanning forest algorithms using the disjoint-set data structure. In: 26th IEEE IPDP Symposium, pp. 827–835 (2012)
Institute of Computer Science, Jagiellonian University (2017). REDHOM, Redhom. http://redhom.ii.uj.edu.pl/
Ranwez, V., Soille, P.: Order independent homotopic thinning for binary and grey tone anchored skeletons. Pattern Recognit. Lett. 23(6), 687–702 (2002)
Rosenfeld, A.: Adjacency in digital pictures. Inf. Control 26, 24–33 (1974)
Serra, J.: Image Analysis and Mathematical Morphology. Academic Press, Cambridge (1982)
Stell, J., Worboys, M.: Relations between adjacency trees. Theor. Comput. Sci. 412(34), 4452–4468 (2011)
Williams, S., Waterman, A., Patterson, D.A.: Roofline: an insightful visual performance model for multicore architectures. Commun. ACM 52, 65–76 (2009)
YACCLAB - Yet Another Connected Components Labeling Benchmark (2017). https://github.com/prittt/YACCLAB
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Díaz del Río, F., Molina-Abril, H., Real, P. (2019). Computing the Component-Labeling and the Adjacency Tree of a Binary Digital Image in Near Logarithmic-Time. In: Marfil, R., Calderón, M., Díaz del Río, F., Real, P., Bandera, A. (eds) Computational Topology in Image Context. CTIC 2019. Lecture Notes in Computer Science(), vol 11382. Springer, Cham. https://doi.org/10.1007/978-3-030-10828-1_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-10828-1_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-10827-4
Online ISBN: 978-3-030-10828-1
eBook Packages: Computer ScienceComputer Science (R0)