Fast connected-component labeling

被引：262

作者：

He, Lifeng ^{[1
,5
]}

Chao, Yuyan ^{[2
,5
]}

Suzuki, Kenji ^{[3
]}

Wu, Kesheng ^{[4
]}

机构：

[1] Aichi Prefectural Univ, Grad Sch Informat Sci & Technol, Aichi 4801198, Japan

[2] Nagoya Sangyo Univ, Grad Sch Environm Management, Aichi 4888711, Japan

[3] Univ Chicago, Div Biol Sci, Dept Radiol, Chicago, IL 60637 USA

[4] Univ Calif Berkeley, Lawrence Berkeley Lab, Berkeley, CA 94720 USA

[5] ShaanXi Univ Sci & Technol, Xian 710021, Shannxi, Peoples R China

来源：

PATTERN RECOGNITION | 2009年 / 42卷 / 09期

关键词：

Labeling algorithm; Label equivalence; Connected component; Linear-time algorithm; Pattern recognition; BINARY IMAGES; FALSE POSITIVES; REDUCTION; ALGORITHM; NODULES; CT;

D O I：

10.1016/j.patcog.2008.10.013

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Labeling of connected components in a binary image is one of the most fundamental operations in pattern recognition: labeling is required whenever a computer needs to recognize objects (connected components) in a binary image. This paper presents a fast two-scan algorithm for labeling of connected components in binary images. We propose an efficient procedure for assigning provisional labels to object pixels and checking label equivalence. Our algorithm is very simple in principle, easy to implement, and suitable for hardware and parallel implementation. We show the correctness of our algorithm, analyze its complexity, and compare it with other labeling algorithms. Experimental results demonstrated that our algorithm is superior to conventional labeling algorithms. (C) 2008 Elsevier Ltd. All rights reserved.

引用

页码：1977 / 1987

页数：11

共 57 条

[1]

Aho A. V., 1974, The design and analysis of computer algorithms

[2] PARALLEL ARCHITECTURES AND ALGORITHMS FOR IMAGE COMPONENT LABELING [J].

ALNUWEIRI, HM ;

PRASANNA, VK .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1992, 14 (10) :1014-1034

[3]

[Anonymous], 1992, Computer and Robot Vision, DOI DOI 10.1109/MRA.2011.941638

[4]

[Anonymous], 1984, CONNECTED COMPONENTS

[5]

Ballard DH, 1982, Computer vision

[6] Connected component labeling for binary images on a reconfigurable mesh architecture [J].

Bhattacharya, P .

JOURNAL OF SYSTEMS ARCHITECTURE, 1996, 42 (04) :309-313

[7] A linear-time component-labeling algorithm using contour tracing technique [J].

Chang, F ;

Chen, CJ ;

Lu, CJ .

COMPUTER VISION AND IMAGE UNDERSTANDING, 2004, 93 (02) :206-220

[8] CONNECTED COMPONENT LABELING ON COARSE-GRAIN PARALLEL COMPUTERS - AN EXPERIMENTAL-STUDY [J].

CHOUDHARY, A ;

THAKUR, R .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1994, 20 (01) :78-83

[9] A GENERAL-APPROACH TO CONNECTED-COMPONENT LABELING FOR ARBITRARY IMAGE REPRESENTATIONS [J].

DILLENCOURT, MB ;

SAMET, H ;

TAMMINEN, M .

JOURNAL OF THE ACM, 1992, 39 (02) :253-280

[10] Two linear time Union-Find strategies for image processing [J].

Fiorio, C ;

Gustedt, J .

THEORETICAL COMPUTER SCIENCE, 1996, 154 (02) :165-181

← 1 2 3 4 5 6 →