Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Framework for Forming Middle Distance Routes Based on Spatial Guidelines, Perceived Accessibility and Visual Cues in Smart City Kapitel lesen Erstes Kapitel lesen

2022 | OriginalPaper | Buchkapitel

An Efficient Run-Based Connected Component Labeling Algorithm for Processing Holes

verfasst von : Florian Lemaitre, Nathan Maurice, Lionel Lacassagne

Erschienen in: Image Analysis and Processing. ICIAP 2022 Workshops

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This article introduces a new connected component labeling and analysis algorithm framework that is able to compute in one pass the foreground and the background labels as well as the adjacency tree. The computation of features (bounding boxes, first statistical moments, Euler number) is done on-the-fly. The transitive closure enables an efficient hole processing that can be filled while their features are merged with the surrounding connected component without the need to rescan the image. A comparison with State-of-the-Art shows that this new algorithm can do all these computations faster than all existing algorithms processing foreground and background connected components or holes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Quest for Speed: The Epic Saga of Record-Breaking on OpenCV Connected Components Extraction
Nächstes Kapitel LSL3D: A Run-Based Connected Component Labeling Algorithm for 3D Volumes
Literatur
1.
Bailey, D., Johnston, C.: Single pass connected component analysis. In: Image and Vision New Zeland (IVNZ), pp. 282–287 (2007)
2.
Bailey, D.G., Klaiber, M.J.: Zig-zag based single-pass connected components analysis. J. Imaging 5(45), 1–26 (2019)
3.
Bolelli, F., Allegretti, S., Baraldi, L., Grana, C.: Spaghetti labeling: directed acyclic graphs for block-based connected components labeling. IEEE Trans. Image Process. 29, 1999–2012 (2020)CrossRef
4.
5.
Cabaret, L., Lacassagne, L.: What is the world’s fastest connected component labeling algorithm? In: IEEE International Workshop on Signal Processing Systems (SiPS), pp. 97–102 (2014)
6.
Cabaret, L., Lacassagne, L., Etiemble, D.: Parallel light speed labeling for connected component analysis on multi-core processors. J. Real-Time Image Process. (JRTIP) 15(1), 173–196 (2018)CrossRef
7.
Galil, Z., Italiano, G.: Data structures and algorithms for disjoint set union problems. ACM Comput. Surv. 23(3), 319–344 (1991)CrossRef
8.
Gray, S.B.: Local properties of binary images in two dimensions. Trans. Comput. 20(5), 551–561 (1971)CrossRef
9.
He, L., Chao, Y.: A very fast algorithm for simultaneously performing connected-component labeling and Euler number computing. Trans. Image Process. 24(9), 2725–2735 (2017)MathSciNetMATH
10.
He, L., Chao, Y., Suzuki, K.: A new algorithm for labeling connected-components and calculating the Euler number, connected-component number, and hole number. In: International Conference on Pattern Recognition (ICPR), pp. 3099–3102 (2012)
11.
He, L., Chao, Y., Suzuki, K.: An algorithm for connected-component labeling, hole labeling and Euler number computing. J. Comput. Sci. Technol. 28(3), 468–478 (2013)MathSciNetCrossRef
12.
He, L., Ren, X., Gao, Q., Zhao, X., Yao, B., Chao, Y.: The connected-component labeling problem: a review of state-of-the-art algorithms. Pattern Recogn. 70, 25–43 (2017)CrossRef
13.
He, L., Ren, X., Zhao, X., Yao, B., Kasuya, H., Chao, Y.: An efficient two-scan algorithm for computing basic shape features of objects in a binary image. J. Real-Time Image Proc. 16(4), 1277–1287 (2016)CrossRef
14.
Hennequin, A., Masliah, I., Lacassagne, L.: Designing efficient SIMD algorithms for direct connected component labeling. In: ACM Workshop on Programming Models for SIMD/Vector Processing (PPoPP), pp. 1–8 (2019)
15.
Hennequin, A., Meunier, Q.L., Lacassagne, L., Cabaret, L.: A new direct connected component labeling and analysis algorithm for GPUs. In: IEEE International Conference on Design and Architectures for Signal and Image Processing (DASIP), pp. 1–6 (2018)
16.
Klaiber, M.J., Bailey, D.G., Simon, S.: A single-cycle parallel multi-slice connected components analysis hardware architecture. J. Real-Time Image Proc. 16(4), 1165–1175 (2019)CrossRef
17.
Lacassagne, L., Zavidovique, A.B.: Light speed labeling for RISC architectures. In: IEEE International Conference on Image Analysis and Processing (ICIP) (2009)
18.
Lacassagne, L., Zavidovique, B.: Light speed labeling: efficient connected component labeling on RISC architectures. J. Real-Time Image Process. (JRTIP) 6(2), 117–135 (2011)CrossRef
19.
Lemaitre, F., Hennequin, A., Lacassagne, L.: How to speed connected component labeling up with SIMD RLE algorithms. In: ACM Workshop on Programming Models for SIMD/Vector Processing (PPoPP), pp. 1–8 (2020)
20.
21.
22.
Playne, D.P., Hawick, K.: A new algorithm for parallel connected-component labelling on GPUs. IEEE Trans. Parallel Distrib. Syst. 29(6), 1217–1230 (2018)CrossRef
23.
Díaz del Río, F., Molina-Abril, H., Real, P.: 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.) CTIC 2019. LNCS, vol. 11382, pp. 82–95. Springer, Cham (2019). https://​doi.​org/​10.​1007/​978-3-030-10828-1_​7CrossRef
24.
del Rio, F.D., Sanchez-Cuevas, P., Molina-Abril, H., Real, P.: Parallel connected-component-labeling based on homotopy trees. Pattern Recogn. Lett. 131, 71–78 (2020)CrossRef
25.
26.
Rosenfeld, A., Platz, J.: Sequential operator in digital pictures processing. J. ACM 13(4), 471–494 (1966)CrossRef
27.
Somasundaram, K., Kalaiselvi, T.: A method for filling holes in objects of medical images using region labeling and run length encoding schemes. In: National Conference on Image Processing (NCIMP), pp. 110–115 (2010)
28.
Tang, J.W., Shaikh-Husin, N., Sheikh, U.U., Marsono, M.N.: A linked list run-length-based single-pass connected component analysis for real-time embedded hardware. J. Real-Time Image Proc. 15(1), 197–215 (2016)CrossRef
29.
30.
31.
Wu, K., Otoo, E., Suzuki, K.: Optimizing two-pass connected-component labeling algorithms. Pattern Anal. Appl. 12, 117–135 (2009)MathSciNetCrossRef
32.
Yao, B., He, L., Kang, S., Zhao, X., Chao, Y.: Bit-quad-based Euler number computing. IEICE Trans. Inf. Syst. E100.D(9), 2197–2204 (2017)
33.
Zhao, H., Chen, Z.X.: A simple hole filling algorithm for binary cell images. Appl. Mech. Mater. 433–435, 1715–1719 (2013)CrossRef
Metadaten
Titel
An Efficient Run-Based Connected Component Labeling Algorithm for Processing Holes
verfasst von
Florian Lemaitre
Nathan Maurice
Lionel Lacassagne
Copyright-Jahr
2022
Buch
Image Analysis and Processing. ICIAP 2022 Workshops

Print ISBN: 978-3-031-13323-7

Electronic ISBN: 978-3-031-13324-4

Copyright-Jahr: 2022

DOI
https://doi.org/10.1007/978-3-031-13324-4_11