Block-Based Connected-Component Labeling Algorithm Using Binary Decision Trees
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
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
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