A fast connected components labeling algorithm for binary images 被引量：1

A fast connected components labeling algorithm for binary images

下载PDF

导出

摘要 A fast label-equivalence-based connected components labeling algorithm is proposed in this paper.It is a combination of two existing efficient methods,which are pivotal operations in two-pass connected components labeling algorithms.One is a fast pixel scan method,and the other is an array-based Union-Find data structure.The scan procedure assigns each foreground pixel a provisional label according to the location of the pixel.That is to say,it labels the foreground pixels following background pixels and foreground pixels in different ways,which greatly reduces the number of neighbor pixel checks.The array-based Union-Find data structure resolves the label equivalences between provisional labels by using only a single array with path compression,and it improves the efficiency of the resolving procedure which is very time-consuming in general label-equivalence-based algorithms.The experiments on various types of images with different sizes show that the proposed algorithm is superior to other labeling approaches for huge images containing many big connected components. A fast label-equivalence-based connected components labeling algorithm is proposed in this paper. It is a combination of two existing efficient methods, which are pivotal operations in two-pass connected compo- nents labeling algorithms. One is a fast pixel scan method, and the other is an array-based Union-Find data structure. The scan procedure assigns each foreground pixel a provisional label according to the location of the pixel. That is to say, it labels the foreground pixels following background pixels and foreground pixels in differ- ent ways, which greatly reduces the number of neighbor pixel checks. The array-based Union-Find data struc- ture resolves the label equivalences between provisional labels by using only a single array with path compres- sion, and it improves the efficiency of the resolving procedure which is very time-consuming in general label-e- quivalence-based algorithms. The experiments on various types of images with different sizes show that the pro- posed algorithm is superior to other labeling approaches for huge images containing many big connected compo- nents.

作者付宜利韩现伟王树国

机构地区 State Key Laboratory of Robotics and System

出处《Journal of Harbin Institute of Technology(New Series)》 EI CAS 2012年第3期81-87,共7页 哈尔滨工业大学学报（英文版）

基金 Sponsored by the National Natural Science Foundation of China (Grant No. 81071219)

关键词 binary image connected components labeling algorithm Union-Find label-equivalence binary image connected components labeling algorithm Union-Find label-equivalence

分类号 TP751.1 [自动化与计算机技术—检测技术与自动化装置]

引文网络
相关文献

参考文献19

1Rosenfeld A, Kak A C. Digital Picture Processing. New York : Academic Press, 1982. 206 - 207.
2Yapa R D, Koichi H. A connected component labeling a|- gorithm for grayscale images and application of the algo- rithm on mammograms. International Journal of Computer Science and Network Seeurity, 2008, 8(6) : 33 -41.
3Zhu Yunfang. Background subtraction and color clustering based moving objects detection. Proceedings of the Interna- tional Conference on Information Engineering and Computer Science, Piscataway: IEEE, 2009. 1 -5.
4Rosenfeld A, Plaits J L. Sequential operations in digital picture processing. Journal of the Association for Compu- ting Machinery, 1966, 13(4) : 471 -494.
5Grana C, Borghesani D, Cucchiara R. Optimized block- based connected components labeling with decision trees. IEEE Trans on Image Processing, 2010, 19 (6) : 1596 - 1609.
6Haralick R M. Some neighborhood operations. Real Time/ Parallel Computing Image Analysis. New York: Plenum, 1981. 11-35.
7Hashizume A, Suzuki R, Horiuchi H, et al. An algorithmof automated RBC classification and its evaluation. Bio Med Eng, 1990, 28(1) : 25 -32.
8Suzuki K, Horiba I, Sugie N. Linear-time connected-com- ponent labeling based on sequential local operations. Com- puter Vision and Image Understanding, 2003, 89 ( 1 ) : 1 - 23.
9Lumia R, Shapiro L, Zungia 0. A new connected compo- nents algorithm for virtual memory computers. Computer Vision, Graphics, and Image Processing, 1983, 22 (2) : 287 - 3O0.
10Haralick R M, Shapiro L G. Computer and Robot Vision. Boston: Addison-Wesley, 1992. 28 -48.