nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Run-Based Connected Components Labeling Using Double-Row Scan

verfasst von : Dongdong Ma, Shaojun Liu, Qingmin Liao

Erschienen in: Image and Graphics

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents a novel run-based connected components labeling algorithm which uses double-row scan. In this algorithm, the run is defined in double rows and the binary image is scanned twice. In the first scan, provisional labels are assigned to runs according to the connectivity between the current run and runs in the last two rows. Simultaneously, equivalent provisional labels are recorded. Then the adjacent matrix of the provisional labels is generated and decomposed with the Dulmage-Mendelsohn decomposition, to search for the equivalent-label sets in linear time. In the second scan, each equivalent-label set is labeled with a number from 1, which can be efficiently accomplished in parallel. The proposed algorithm is compared with the state-of-the-art algorithms both on synthetic images and real image datasets. Results show that the proposed algorithm outperforms the other algorithms on images with low density of foreground pixels and small amount of connected components.

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 Online High-Accurate Calibration of RGB+3D-LiDAR for Autonomous Driving

Nächstes Kapitel A 3D Tube-Object Centerline Extraction Algorithm Based on Steady Fluid Dynamics

Hu, S., Zhang, F., Wang, M., et al.: PatchNet: a patch-based image representation for interactive library-driven image editing. ACM Trans. Graph. 32(6), 196 (2013)

Haralick, R.M., Shapiro, L.G.: Computer and Robot Vision, vol. I. Addison-Wesley, Boston (1992)

Suzuki, K., Horiba, I., Sugie, N.: Linear time connected component labeling based on sequential local operations. Comput. Vis. Image Underst. 89(1), 1–23 (2003)CrossRefMATH

Bailey, D.G., Johnston, C.T., Ma, N.: Connected components analysis of streamed images. In: International Conference on Field-Programmable Logic and Applications, pp. 679–682. IEEE, New York (2008)

Klaiber, M.J., Bailey, D.G., Baroud, Y.O., Simon, S.: A resource-efficient hardware architecture for connected component analysis. IEEE Trans. Circ. Syst. Video 26(7), 1334–1349 (2016)CrossRef

Rosenfeld, A., Pfaltz, J.L.: Sequential operations in digital pictures processing. J. Assoc. Comput. Mach. 13(4), 471–494 (1966)CrossRefMATH

Lumia, R., Shapiro, L.G., Zuniga, O.: A new connected components algorithm for virtual memory computers. Comput. Graph. Image Process. 22(2), 287–300 (1983)CrossRef

He, L., Chao, Y., Suzuki, K., Wu, K.: Fast connected-component labeling. Pattern Recognit. 32(9), 1977–1987 (2009)CrossRefMATH

He, L., Chao, Y., Suzuki, K.: An efficient first-scan method for label-equivalence-based labeling algorithms. Pattern Recognit. Lett. 31(1), 28–35 (2010)CrossRef

10.

Chang, F., Chen, C.-J., Lu, C.-J.: A linear-time component-labeling algorithm using contour tracing technique. Comput. Vis. Image Underst. 93(2), 206–220 (2004)CrossRef

11.

Grana, C., Borghesani, D., Cucchiara, R.: Optimized block-based connected components labeling with decision trees. IEEE Trans. Image Process. 19(6), 1596–1609 (2010)MathSciNetCrossRefMATH

12.

Grana, C., Baraldi, L., Bolelli, F.: Optimized connected components labeling with pixel prediction. In: Blanc-Talon, J., Distante, C., Philips, W., Popescu, D., Scheunders, P. (eds.) ACIVS 2016. LNCS, vol. 10016, pp. 431–440. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48680-2_38 CrossRef

13.

He, L., Zhao, X., Chao, Y., Suzuki, K.: Configuration-transition-based connected-component labeling. IEEE Trans. Image Process. 23(2), 943–951 (2014)MathSciNetCrossRefMATH

14.

Chang, W.-Y., Chiu, C.-C., Yang, J.-H.: Block-based connected-component labeling algorithm using binary decision trees. Sensors 15(9), 23763–23787 (2015)CrossRef

15.

Santiago, D.J.C., Ren, T.I., Cavalcanti, G.D.C., Jyh, T.I.: Efficient 2×2 block-based connected components labeling algorithms. In: IEEE International Conference on Image Processing, pp. 4818–4822. IEEE, New York (2015)

16.

Grana, C., Bolelli, F., Baraldi, L., Vezzani, R.: YACCLAB - Yet Another Connected Components Labeling Benchmark. In: Proceedings of International Conference on Pattern Recognition. IEEE, New York (2016)

17.

He, L., Chao, Y., Suzuki, K.: A run-based two-scan labeling algorithm. IEEE Trans. Image Process. 17(5), 749–756 (2008)MathSciNetCrossRef

18.

He, L., Chao, Y., Suzuki, K., Itoh, H.: A run-based one-scan labeling algorithm. In: Proceedings of International Conference on Image Analysis and Recognition, pp. 93–102 (2009)

19.

He, L., Chao, Y., Suzuki, K.: A run based one and a half scan connected component labeling algorithm. Int. J. Pattern Recognit. Artif. Intell. 24(4), 557–579 (2011)CrossRef

20.

Dulmage, A.L., Mendelsohn, N.S.: Coverings of bipartite graphs. Can. J. Math. 10, 517–534 (1958)MathSciNetCrossRefMATH

21.

Pothen, A., Fan, C.J.: Computing the block triangular form of a sparse matrix. ACM Trans. Math. Softw. 16(4), 303–324 (1990)MathSciNetCrossRefMATH

22.

Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Clarendon Press, Oxford (1986)MATH

23.

Ait-Aoudia, S., Jegou, R., Michelucci, D.: Reduction of constraint systems. In: Compugraphic, pp. 331–340 (1993)

24.

Tarjan, R.: Depth first search and linear graph algorithms. In: Symposium on Switching and Automata Theory, vol. 1, no. 4, pp. 114–121 (1971)

25.

Huiskes, M.J., Lew, M.S.: The MIR flickr retrieval evaluation. In: Proceedings of ACM International Conference on Multimedia Information Retrieval, pp. 39–43 (2008). http://press.liacs.nl/mirflickr/

26.

The Legacy Tobacco Document Library (LTDL): University of California (2007). http://legacy.library.ucsf.edu/

27.

Baltieri, D., Vezzani, R., Cucchiara, R.: 3DPeS: 3D people dataset for surveillance and forensics. In: Proceedings of Joint ACM Workshop on Human Gesture and Behavior Understanding, pp. 59–64 (2011)

28.

Dong, F., Irshad, H., Oh, E.-Y., et al.: Computational pathology to discriminate benign from malignant intraductal proliferations of the breast. PLoS One 9(12), e114885 (2014)CrossRef

29.

Maltoni, D., Maio, D., Jai, A., Prabhakar, S.: Handbook of Fingerprint Recognition. Springer, London (2009). https://doi.org/10.1007/978-1-84882-254-2 CrossRefMATH

Titel: Run-Based Connected Components Labeling Using Double-Row Scan
verfasst von: Dongdong Ma
Shaojun Liu
Qingmin Liao
Verlag: Springer International Publishing
Buch: Image and Graphics
Print ISBN: 978-3-319-71597-1

Electronic ISBN: 978-3-319-71598-8

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-71598-8_24

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"