Block-Based Connected-Component Labeling Algorithm Using Binary Decision Trees

Sensors - Tập 15 Số 9 - Trang 23763-23787
Wan-Yu Chang1, Chung‐Cheng Chiu2, Jia-Horng Yang3
1Department of Electrical and Electronic Engineering, Chung Cheng Institute of Technology, National Defense University, Taoyuan County 33551, Taiwan. [email protected].
2Department of Electrical and Electronic Engineering, Chung Cheng Institute of Technology, National Defense University, Taoyuan County 33551, Taiwan. [email protected].
3Department of Electrical and Electronic Engineering, Chung Cheng Institute of Technology, National Defense University, Taoyuan County 33551, Taiwan. [email protected].

Tóm tắt

In this paper, we propose a fast labeling algorithm based on block-based concepts. Because the number of memory access points directly affects the time consumption of the labeling algorithms, the aim of the proposed algorithm is to minimize neighborhood operations. Our algorithm utilizes a block-based view and correlates a raster scan to select the necessary pixels generated by a block-based scan mask. We analyze the advantages of a sequential raster scan for the block-based scan mask, and integrate the block-connected relationships using two different procedures with binary decision trees to reduce unnecessary memory access. This greatly simplifies the pixel locations of the block-based scan mask. Furthermore, our algorithm significantly reduces the number of leaf nodes and depth levels required in the binary decision tree. We analyze the labeling performance of the proposed algorithm alongside that of other labeling algorithms using high-resolution images and foreground images. The experimental results from synthetic and real image datasets demonstrate that the proposed algorithm is faster than other methods.

Từ khóa


Tài liệu tham khảo

Dong-Chen, H., and Li, W. (1989, January 10–14). Texture unit, texture spectrum and texture analysis. Proceedings of the 12th Canadian Symposium on Remote Sensing, Vancouver, BC, Canada.

Dalal, N., and Triggs, B. (, 2005). Histograms of oriented gradients for human detection. Proceedings of the CVPR 2005. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Diego, CA, USA.

Cyganek, 2012, One-class support vector ensembles for image segmentation and classification, J. Math. Imaging Vision, 42, 103, 10.1007/s10851-011-0304-0

Krawczyk, 2014, Clustering-based ensembles for one-class classification, Inf. Sci., 264, 182, 10.1016/j.ins.2013.12.019

Rosenfeld, 1966, Sequential operations in digital picture processing, J. ACM, 13, 471, 10.1145/321356.321357

Haralick, R. (1981). Real-Time Parallel Computing, Springer.

Lumia, 1983, A new connected components algorithm for virtual memory computers, Comput. Vision Gr. Image Process., 22, 287, 10.1016/0734-189X(83)90071-3

Suzuki, 2003, linear-time connected-component labeling based on sequential local operations, Comput. Vision Gr. Image Underst., 89, 1, 10.1016/S1077-3142(02)00030-9

Wu, K., Otoo, E., and Shoshani, A. (2005). Medical Imaging, SPIE Proceedings.

He, L., Chao, Y., and Suzuki, K. (October, January 16). A linear-time two-scan labeling algorithm. Proceedings of the ICIP 2007 IEEE International Conference on Image Processing, San Antonio, TX, USA.

He, 2009, Fast connected-component labeling, Pattern Recognit., 42, 1977, 10.1016/j.patcog.2008.10.013

He, 2010, An efficient first-scan method for label-equivalence-based labeling algorithms, Pattern Recognit. Lett., 31, 28, 10.1016/j.patrec.2009.08.012

Lifeng, 2008, A run-based two-scan labeling algorithm, IEEE Trans. Image Process., 17, 749, 10.1109/TIP.2008.919369

Kamel, M., and Campilho, A. (2009). Image Analysis and Recognition, Springer Berlin Heidelberg.

He, 2010, A run-based one and a half scan connected-component labeling algorithm, Int. J. Pattern Recognit. Artif. Intell., 24, 557, 10.1142/S0218001410008032

He, 2013, An algorithm for connected-component labeling, hole labeling and euler number computing, J. Comput. Sci. Technol., 28, 468, 10.1007/s11390-013-1348-y

Lifeng, 2015, A very fast algorithm for simultaneously performing connected-component labeling and euler number computing, IEEE Trans. Image Process., 24, 2725, 10.1109/TIP.2015.2425540

Grana, C., Borghesani, D., and Cucchiara, R. (2009, January 6–8). Fast block based connected components labeling. Proceedings of the 16th IEEE International Conference on Image Processing, Cairo, Egypt.

Grana, 2010, Optimized block-based connected components labeling with decision trees, IEEE Trans. Image Process., 19, 1596, 10.1109/TIP.2010.2044963

Wu, 2009, Optimizing two-pass connected-component labeling algorithms, Pattern Anal. Appl., 12, 117, 10.1007/s10044-008-0109-y

Sutheebanjard, 2011, Efficient scan mask techniques for connected components labeling algorithm, EURASIP J. Image Video Process., 14, 1

Grana, 2012, Optimal decision trees for local image processing algorithms, Pattern Recognit. Lett., 33, 2302, 10.1016/j.patrec.2012.08.015

Lifeng, H., Xiao, Z., and Suzuki, K. (2012, January 4–6). A new two-scan algorithm for labeling connected components in binary images. Proceedings of the World Congress on Engineering, London, UK.

Lifeng, 2014, Configuration-transition-based connected-component labeling, IEEE Trans. Image Process., 23, 943, 10.1109/TIP.2013.2289968

Source Code of the BBDT algorithm. Available online: http://imagelab.ing.unimore.it/imagelab/labeling.asp.

Han, 1990, An efficient and fast parallel-connected component algorithm, J. ACM, 3, 626, 10.1145/79147.214077

Samet, 1981, Connected component labeling using quadtrees, J. ACM, 3, 487, 10.1145/322261.322267

Source Code of the Proposed Algorithm. Available online: http://j.mp/CCITsourcecode.

GF Image Datasets. Available online: http://j.mp/GFdatasets.

FH Image Datasets. Available online: http://j.mp/FHdatasets.

Otsu, 1979, A threshold selection method from gray-level histograms, IEEE Transa. Syst. Man Cybern., 9, 62, 10.1109/TSMC.1979.4310076

Chiu, 2010, A robust object segmentation system using a probability-based background extraction algorithm, IEEE Trans. Circuits Syst. Video Technol., 20, 518, 10.1109/TCSVT.2009.2035843

Thông tin
Thông tin xuất bản

Sensors

Tập 15 Số 9

23763-23787

Thông tin tác giả