Fast Labeled Spanning Tree in Binary Irregular Graph Pyramids
by Majid Banaeyan * 
, Walter G. Kropatsch
Pattern Recognition and Image Processing Group, Institute of Visual Computing and Human-Centered Technology, TU Wien, Vienna, Austria
* Author to whom correspondence should be addressed.
Journal of Engineering Research and Sciences, Volume 1, Issue 10, Page # 69-78, 2022; DOI: 10.55708/js0110009
Keywords: Spanning Tree, Total Order, Parallel Processing
Received: 15 August 2022, Revised: 10 October 2022, Accepted: 18 October 2022, Published Online: 31 October 2022
APA Style
Banaeyan, M., & Kropatsch, W. G. (2022). Fast Labeled Spanning Tree in Binary Irregular Graph Pyramids. Journal of Engineering Research and Sciences, 1(10), 69–78. https://doi.org/10.55708/js0110009
Chicago/Turabian Style
Banaeyan, Majid, and Walter G. Kropatsch. “Fast Labeled Spanning Tree in Binary Irregular Graph Pyramids.” Journal of Engineering Research and Sciences 1, no. 10 (October 1, 2022): 69–78. https://doi.org/10.55708/js0110009.
IEEE Style
M. Banaeyan and W. G. Kropatsch, “Fast Labeled Spanning Tree in Binary Irregular Graph Pyramids,” Journal of Engineering Research and Sciences, vol. 1, no. 10, pp. 69–78, Oct. 2022, doi: 10.55708/js0110009.
Irregular Pyramids are powerful hierarchical structures in pattern recognition and image processing. They have high potential of parallel processing that makes them useful in processing of a huge amount of digital data generated every day. This paper presents a fast method for constructing an irregular pyramid over a binary image where the size of the images is more than 2000 in each of 2/3 dimensions. Selecting the contraction kernels (CKs) as the main task in constructing the pyramid is investigated. It is shown that the proposed fast labeled spanning tree (FLST) computes the equivalent contraction kernels (ECKs) in only two steps. To this purpose, first, edges of the corresponding neighborhood graph of the binary input image are classified. Second, by using a total order an efficient function is defined to select the CKs. By defining the redundant edges, further edge classification is performed to partition all the edges in each level of the pyramid. Finally, two important applications are presented : connected component labeling (CCL) and distance transform (DT) with lower parallel complexity 𝒪(𝑙𝑜𝑔(𝛿)) where the 𝛿 is the diameter of the largest connected component in the image.
- A. Rosenfeld, J. L. Pfaltz, “Sequential operations in digital picture processing”, Association for Computing Machinery, vol. 13, no. 4, p. 471–494, 1966.
- P. Meer, “Stochastic image pyramids”, Computer Vision, Graphics, and Image Processing, vol. 45, no. 3, pp. 269–294, 1989.
- Z. Pizlo, Problem Solving, Cognitive Mechanisms and Formal Models, Cambridge University Press, 2022.
- M. C. Potter, B. Wyble, C. E. Hagmann, E. S. McCourt, “De- tecting meaning in rsvp at 13 ms per picture”, Attention, Per- ception, & Psychophysics, vol. 76, no. 2, pp. 270–279, 2014, doi: 10.3758/s13414-013-0605-z.
- J. A. Feldman, D. H. Ballard, “Connectionist models and their proper- ties”, Cognitive science, vol. 6, no. 3, pp. 205–254, 1982.
- M. Banaeyan, W. G. Kropatsch, “Pyramidal connected component labeling by irregular graph pyramid”, “2021 5th International Conference on Pattern Recognition and Image Analysis (IPRIA)”, pp. 1–5, 2021, doi:10.1109/IPRIA53572.2021.9483533.
- J.-M. Jolion, A. Rosenfeld, A pyramid framework for early vision: mul- tiresolutional computer vision, vol. 251, Springer Science & Business Media, 2012.
- W. G. Kropatsch, “Building irregular pyramids by dual graph con- traction”, IEE-Proc. Vision, Image and Signal Processing, vol. Vol. 142, no. No. 6, pp. pp. 366–374, 1995, doi:10.1049/ip-vis:19952115.
- W. G. Kropatsch, H. Macho, “Finding the structure of connected components using dual irregular pyramids”, “Cinquième Colloque DGCI”, pp. 147–158, LLAIC1, Université d’Auvergne, ISBN 2-87663- 040-0, 1995.
- Y. Haxhimusa, W. G. Kropatsch, “Segmentation graph hierarchies”, “Structural, Syntactic, and Statistical Pattern Recognition, Joint IAPR International Workshops on SSPR 2004 and SPR 2004”, vol. LNCS 3138, pp. 343–351, Springer, Berlin Heidelberg, New York, 2004.
- M. Cerman, I. Janusch, R. Gonzalez-Diaz, W. G. Kropatsch, “Topology-
ng LBP pyramids”, Machine Vision and ons, pp. 1–14, 2016, doi:10.1007/s00138-016-0795-1. - R. Klette, Concise computer vision, vol. 233, Springer, 2014.
- R. Trudeau, Introduction to Graph Theory, Dover Books on Mathematics, Dover Pub., 1993.
- L. Brun, W. G. Kropatsch, “Hierarchical graph encodings”, O. Lézoray,L. Grady, eds., “Image Processing and Analysis with Graphs: Theory and Practice”, pp. 305–349, CRC Press, 2012.
- L. Brun, W. Kropatsch, “Introduction to combinatorial pyramids”, “Digital and Image Geometry”, pp. 108–128, Springer, 2001.
- F. Torres, W. G. Kropatsch, “Canonical encoding of the combinato- rial pyramid”, “Proceedings of the 19th Computer Vision Winter Workshop”, pp. 118–125, 2014.
- M. Banaeyan, D. Batavia, W. G. Kropatsch, “Removing redundancies in binary images”, “International Conference on Intelligent Systems and Patterns Recognition (ISPR), Hammamet, Tunisia, March 24-25, 2022”, pp. 221–233, Springer, 2022, doi:10.1007/978-3-031-08277-1_19.
- B. A. Davey, H. A. Priestley, Introduction to lattices and order, Cambridge university press, 2002.
- M. Banaeyan, W. G. Kropatsch, “Parallel 𝑙𝑜 𝑔 𝑛 computation of the adjacency of connected components”, “International Confer- ence on Pattern Recognition and Artificial Intelligence (ICPRAI), Paris, France, June 1-3, 2022”, pp. 102–113, Springer, 2022, doi: 10.1007/978-3-031-09282-4_9.
- M. Banaeyan, C. Carratù, W. G. Kropatsch, J. Hladůvka, “Fast distance transforms in graphs and in gmaps”, “IAPR Joint International Work- shops on Statistical Techniques in Pattern Recognition (SPR 2022) and Structural and Syntactic Pattern Recognition (SSPR 2022), Montreal, Canada, August 26-27, 2022”, p. in print, 2022.
- W. G. Kropatsch, “Equivalent contraction kernels to build dual ir- regular pyramids”, Advances in Computer Science, vol. Advances in Computer Vision, pp. pp. 99–107, 1997.
- P. J. Burt, E. H. Adelson, “The Laplacian pyramid as a compact image code”, “Readings in computer vision”, pp. 671–679, Elsevier, 1987.
- Y. Haxhimusa, A. Ion, W. G. Kropatsch, “Evaluating hierarchical graph-based segmentation”, “18th International Conference on Pat- tern Recognition”, vol. II, pp. 195–198, IEEE Comp.Soc., 2006, doi: 10.1109/ICPR.2006.511.
- L. He, X. Ren, Q. Gao, X. Zhao, B. Yao, Y. Chao, “The connected- component labeling problem: A review of state-of-the-art algorithms”, Pattern Recognition, vol. 70, pp. 25–43, 2017, doi:10.1016/j.patcog.2017. 04.018.
- L. He, Y. Chao, K. Suzuki, “Two efficient label-equivalence-based connected-component labeling algorithms for 3D binary images”, IEEE Transactions on Image Processing, vol. 20, no. 8, pp. 2122–2134, 2011, doi:10.1109/TIP.2011.2114352.
- U. H. Hernandez-Belmonte, V. Ayala-Ramirez, R. E. Sanchez-Yanez, “A comparative review of two-pass connected component labeling algo- rithms”, “Mexican International Conference on Artificial Intelligence”, pp. 452–462, Springer, 2011, doi:10.1007/978-3-642-25330-0_40.
- F. Bolelli, S. Allegretti, L. Baraldi, C. Grana, “Spaghetti labeling: Di- rected acyclic graphs for block-based connected components labeling”, IEEE Transactions on Image Processing, vol. 29, pp. 1999–2012, 2020, doi:10.1109/TIP.2019.2946979.
- C. Grana, F. Bolelli, L. Baraldi, R. Vezzani, “YACCLAB – Yet Another Connected Components Labeling Benchmark”, “2016 23rd Interna- tional Conference on Pattern Recognition (ICPR)”, pp. 3109–3114, Springer, 2016, doi:10.1109/ICPR.2016.7900112.
- S. Prakash, U. Jayaraman, P. Gupta, “Ear localization from side face images using distance transform and template matching”, “2008 First theory, Tools and Applications”, pp.
.1109/IPTA.2008.4743786. - J. Lindblad, N. Sladoje, “Linear time distances between fuzzy sets with applications to pattern matching and classification”, IEEE Transactions on Image Processing, vol. 23, no. 1, pp. 126–136, 2014, doi: 10.1109/TIP.2013.2286904.
- B. Hill, R. A. Baldock, “Constrained distance transforms for spatial atlas registration”, BMC bioinformatics, vol. 16, no. 1, pp. 1–10, 2015, doi:10.1186/s12859-015-0504-5.
- H. Sobreira, C. M. Costa, I. Sousa, L. Rocha, J. Lima, P. Farias, P. Costa, P. Moreira, “Map-matching algorithms for robot self-localization: a comparison between perfect match, iterative closest point and normal distributions transform”, Journal of Intelligent & Robotic Systems, vol. 93, no. 3, pp. 533–546, 2019, doi:10.1007/s10846-017-0765-5.
- C. Niblack, P. B. Gibbons, D. W. Capson, “Generating skeletons and centerlines from the distance transform”, CVGIP: Graphical Models and Image Processing, vol. 54, no. 5, pp. 420–437, 1992.
- M. Kassis, J. El-Sana, “Learning free line detection in manuscripts using distance transform graph”, “2019 International Conference on Document Analysis and Recognition (ICDAR)”, pp. 222–227, 2019, doi:10.1109/ICDAR.2019.00044.
- D. Brunet, D. Sills, “A generalized distance transform: Theory and applications to weather analysis and forecasting”, IEEE Transactions on Geoscience and Remote Sensing, vol. 55, no. 3, pp. 1752–1764, 2017, doi:10.1109/TGRS.2016.2632042.
- R. Fabbri, L. D. F. Costa, J. C. Torelli, O. M. Bruno, “2D eu- clidean distance transform algorithms: A comparative survey”, ACM Computing Surveys (CSUR), vol. 40, no. 1, pp. 1–44, 2008, doi: 10.1145/1322432.1322434.
- M. Momayyezi, A. Borsuk, C. Brodersen, M. Gilbert, G. Théroux- Rancourt, D. Kluepfel, A. McElrone, “Desiccation of the leaf meso- phyll and its implications for CO2 diffusion and light processing”, & Environment, vol. 45, no. 5, pp. 1362 – 1381, 2022, doi: 1111/pce.14287.
