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 条

[11]

Gargantini I., 1982, Proc. 12th Conf. Numerical Mathematics and Computation, V37, P257

[12]

Gonzalez R. C., 1992, DIGITAL IMAGE PROCES, V2nd

[13]

Gotoh T., 1987, Proceedings of the SPIE - The International Society for Optical Engineering, V804, P217, DOI 10.1117/12.941317

[14]

Haralick R. M., 1981, Real-Time/Parallel Computing. Image Analysis. Proceedings of Part of the Japan-United States Seminar on Research Towards Real-Time Parallel Image Analysis and Recognition, P11

[15]

HASHIZUME A, 1990, JAPANESE J MED ELECT, V28, P25

[16]

Hattori T., 1990, Proceedings. 10th International Conference on Pattern Recognition (Cat. No.90CH2898-5), P494, DOI 10.1109/ICPR.1990.119408

[17]

He LF, 2007, IEEE IMAGE PROC, P2493

[18] A run-based two-scan labeling algorithm [J].

He, Lifeng ;

Chao, Yuyan ;

Suzuki, Kenji .

IEEE TRANSACTIONS ON IMAGE PROCESSING, 2008, 17 (05) :749-756

[19] CONNECTED COMPONENT LABELING WITH LINEAR OCTREE [J].

HECQUARD, J ;

ACHARYA, R .

PATTERN RECOGNITION, 1991, 24 (06) :515-531

[20] COMPUTING CONNECTED COMPONENTS ON PARALLEL COMPUTERS [J].

HIRSCHBERG, DS ;

CHANDRA, AK ;

SARWATE, DV .

COMMUNICATIONS OF THE ACM, 1979, 22 (08) :461-464

← 1 2 3 4 5 6 →