Home   >   CSC-OpenAccess Library   >    Manuscript Information
Proposal and Implementation of the Connected-Component Labeling of Binary Images and Filling Holes for GPGPU
Hiroto Kizuna, Hiroyuki Sato
Pages - 8 - 29     |    Revised - 30-04-2020     |    Published - 01-06-2020
Volume - 14   Issue - 2    |    Publication Date - June 2020  Table of Contents
Connected Component Labeling, Parallel Processing, GPGPU, Image Processing.
The connected-component labeling (CCL) is a technique for extracting connected pixels having the same value. It is mainly used for abnormality diagnosis of products, and for extracting noise areas of products. In the extraction of product areas in product diagnosis, a hole filling processing (HFP) is used to complement discolored areas. However, the HFP is inefficient, because the CCL needs to be executed twice in the foreground and background, and half of the threads are idle during each process. In this study, we propose a rewriting method for continuous label IDs with pixel-by-pixel parallelism, and a HFP method using simultaneous CCL of foreground and background. We implemented and evaluated these methods on Jetson TX2. The rewriting process to the continuous label ID is 3.7-13.8 times faster than the conventional method of sequential processing on the CPU, and on average 9.2 times faster. For the HFP using simultaneous CCL, we implemented and verified the conventional method that requires twice the CCL and the proposed method that can extract the foreground and background with one CCL. The performance of the proposed method is about 13-27% better than that of the conventional method. In addition, in the lightweight object detection method that is an application using the proposed method, the facial detection time is about 14 ms, which is about 60 times faster than the conventional method. As a result, the facial detection processing with high computational complexity can be operated practically even on an inexpensive and small processor. The CCL process for GPGPU has little room for optimization, and it has been difficult to achieve higher speeds. However, we focused on wasted idols in the HFP, proposed a method to reduce and supplement them, and realized a faster HFP than the conventional method.
1 Google Scholar 
2 Semantic Scholar 
3 refSeek 
4 BibSonomy 
5 Doc Player 
6 Scribd 
7 SlideShare 
A. Hashidume, R. Suzuki, H. Yokouchi, H. Horiuchi, S. Yamamoto, "Red blood cell automatic discrimination algorithm and its evaluation." Medical electronics and biotechnology, vol. 28, no. 1, pp. 25-32, in Japanese, Jan. 1990.
A. Hemlata, M. Motwani. "Face detection by finding the facial features and the angle of inclination of tilted face." International Journal of Computer Science Issues (IJCSI), vol. 10, issue 2, pp.472-479, Mar. 2013.
A. Ito, Y. Aoki, S. Hashimoto. "Accurate extraction and measurement of fine cracks from concrete block surface image,"in Proc. 28th Annual Conference of the IEEE Industrial Electronics Society (IECON02), vol. 3, 2002, pp. 2202-2207.
A. Rakhmadi, M.S.M. Rahim, A. Bade, et al. "Loop back connected component labeling algorithm and its implementation in detecting face." International Journal of Computer, Electrical, Automation, Control and Information Engineering, vol. 4, no. 4, pp. 635-640, Apr. 2010.
A. Seal, S. Gangulyb, D. Bhattacharjee, M. Nasipuri, D.K. Basu. "Minutiae based thermal human face recognition using label connected component algorithm." Procedia Technology, vol. 4, pp. 604-611, Feb. 2012.
D. D. Sidibe, P. Montesinos, S. Janaqi. "A simple and efficient eye detection method in color images." in Proc. International Conference Image and Vision Computing New Zealand 2006, pp. 385-390.
D. E. King. "Dlib C++ Library." http://dlib.net/, Dec.14.2019 [Mar.11.2020].
H. Arunachalam, M. Motwani. "Image segmentation for the extraction of face using haar like feature", Int. Arab J. Inf. Technol, vol. 13, no. 6A, pp.951-958, Dec. 2016.
H. Furukawa, K. Ueda, R. Tachibana, N. Kido, "Extraction of liver region from 3D abdominal CR image using CT value distribution information and template image." Computer Assisted Diagnostic Imaging Society, vol. 9, no. 3, pp. 27-35, in Japanese, Nov. 2005.
H. Kawada, T. Kamiya, Y. Marutani, "A Method of Strain Inspection of Automotive Rearview Mirror by Image Processing." IEICE Transactions D, vol. J83-D2, no. 3, pp. 947-956, in Japanese, Mar. 2000.
H. Kizuna, H. Sato. "Accelerating Facial Detection for Improvement of Person Identification Accuracy in Entering and Exiting Management System." In Proc. Sixth International Symposium on Computing and Networking Workshops (CANDAR), 2018, pp. 202-208.
H. Kizuna, H. Sato. "Acceleration of Face Detection for Improving Person Identification Accuracy in Entrance / Exit Control System." IEICE research report of Image Engineering, vol. 117, no. 484, pp. 229-234, in Japanese, Mar. 2018.
H. Ogawam D. Sakai. "Diagnosis of cucumber leaf disease by image processing." Bulletin of Aichi Univ. of Education, 58 (Natural Sciences), pp. 13-19, in Japanese, Mar. 2009.
J. Hasegawa, K. Mori, J. Toriwaki, Y. Yasuno, K. Katada, "Extraction of Lung Cancer Candidate Regions from Chest Sequential CT Images by 3D Digital Image Processing." IEICE Transactions D, vol. J76-D2, no. 8, pp.1587-1594, in Japanese, Aug. 1993.
J. Masumoto, M. Hori, Y. Sato, T. Murakami, T. Kamikou, H. Nakamura, S. Tamura, "Automatic liver region extraction from multi-slice CT images." IEICE Transactions D, vol. J84-D2, no. 9, pp. 2150-2161, in Japanese, Sep. 2001.
J. Masumoto, M. Hori, Y. Sato, T. Murakami, T. Kamikou, H. Nakamura, S. Tamura, "Study on automatic liver tumor extraction from X-ray CT images." IEICE Transactions D, vol. J83-D2, no. 1, pp. 219-227, in Japanese, Jan. 2000.
K. Suzuki, H. Horiba, N. Sugie. "Linear-time connected-component labeling based on sequential local operations." Computer Vision and Image Understanding, vol. 89, no.1, pp.1-23, Jan. 2003.
K. Wu, E. Otoo, K. Suzuki. "Optimizing two-pass connected-component labeling algorithms." Pattern Analysis and Applications, vol. 12, no. 2, pp. 117-135, Jun. 2009.
L. He, Q. Gao, X. Zhao, et al. "The connected-component labeling problem: A review of state-of-the-art algorithms." Pattern Recognition, vol. 70, pp. 25-43, Oct. 2017.
L. He, Y. Chao, K. Suzuki. "A run-based two-scan labeling algorithm." IEEE transactions on image processing, vol. 17, no. 5, pp. 749-756, Mar. 2008.
N. Dalal, B. Triggs, "Histograms of oriented gradients for human detection." in Proc. International Conference on Computer Vision and Pattern Recognition (CVPR), 2005, vol. 1, pp. 886-893, 2005.
N. Shibata, S. Yamamoto, "Implementation of parallel algorithm for connected component extraction for CPU using AVX2 instruction set." In Proc. Workshop on Multimedia Communication and Distributed Processing (DPSWS2013), 2013, pp. 300-307, in Japanese.
N. Shibata, S. Yamamoto, "SumiTag: Uses a less noticeable AR marker and GPGPU Read method." IPSJ DPS research report, vol. 2011-DPS-149, no.7, pp.v1-9, in Japanese, Nov. 2011.
N. Shibata, S. Yamamoto. "GPGPU-Assisted Subpixel Tracking Method for Fiducial Markers." Journal of Information Processing, vol. 22, no. 1, pp. 19-28, Jan. 2014.
NVIDIA. "NVIDIA JETSON The embedded platform for autonomous everything." https:// www.nvidia.com/en-us/autonomous-machines/embedded-systems-dev-kits-modules/, Apr. 29, 2020 [May. 07, 2020].
O. Kalentev, A. Rai, S. Kemnitz, R. Schneider. "Connected component labeling on a 2D grid using CUDA." Journal of Parallel and Distributed Computing, vol. 71, no. 4, pp. 615-620, Apr. 2011.
O. Shiku, A. Nakamura, "Character line extraction from scene image using LoG filter." IEICE Transactions D, vol. J87-D2, no.8, pp. 1735-1739, in Japanese, Aug. 2004.
O. St., B. Benes. "Connected component labeling in CUDA" In GPU computing gems emerald edition, W. W. Hwu, Morgan Kaufmann, 2011, pp.569-581.
S. Gupta, D. Palsetia, M. Patwary, M. Ali, A. Agrawal, A. Choudhary. "A new parallel algorithm for two-pass connected component labeling." In Proc. 2014 IEEE International Parallel & Distributed Processing Symposium Workshops, 2014, pp. 1355-1362.
T. Fuda, S. Omachi, H. Aso, "Recognition of Line Graph Images in Documents by Tracing Connected Components." IEICE Transactions D, vol. J86-D2, no. 6, pp. 825-835, in Japanese, Jun. 2003.
T. Miyake, S. Haruta, S. Horihata, "Gaze determination method using features that do not depend on face orientation." IEICE Transactions D, vol. J86-D2, no. 12, pp. 1737-1744, in Japanese, Dec. 2003.
T. Oshige, "Automatic inspection technology for quality evaluation of steel products." Measurement and control, vol. 55, no. 3, pp. 228-233, in Japanese, Mar. 2016.
V.N.Vapnik. "Statistical Learning Theory", Wikey, New York, 1988.
Y. Aramaki, Y. Matsui, T. Yamasaki, K. Aizawa, "Character region detection in comics based on connected components and region classification." IEICE Transactions A, vol. J100-A, no.1, pp. 3-11, in Japanese, Jan. 2017.
Y. Bian, F. Dong, H. Wang. "Reconstruction of rising bubble with digital image processing method," in Proc. 2011 IEEE International Instrumentation and Measurement Technology Conference, IEEE, 2011, pp.1-5.
Y. Hayase, Y. Mekata, K. Mori, J. Hasegawa, J. Torwaki, M. Mori, H. Natori, "A method for detecting multiple nodules from 3D chest X-ray CT images." IEICE Transactions D, vol. J87-D2, no. 1, pp. 219-227, in Japanese, Jan. 2004.
Y. Hirano, J. Hasegawa, J. Toriwaki, H. Daimatsu, K. Eguchi, "Interactive lung tumor region extraction from 3D chest CT images and its application to malignant differentiation." IEICE Transactions D, vol. J87-D2, no. 1, pp. 237-247, in Japanese, Jan. 2004.
Y. Purwar, S. L. Shah, G. Clarke, A. Almugairi, A. Muehlenbachs. "Automated and unsupervised detection of malarial parasites in microscopic images." Malaria Journal, vol. 10, no. 364, pp. 1-10, Dec. 2011.
Y. Saito, Y. Kenmochi, K. Kotani, "Extraction and removal of eyeglass frame area in face image using parametric eyeglass frame model." IEICE Transactions D, vol. J82-D2, no. 5, pp. 880-890, in Japanese, May. 1999.
Mr. Hiroto Kizuna
Graduate School of Software and Information Science, Iwate Prefectual University - Japan
Professor Hiroyuki Sato
Iwate Prefectural University - Japan

View all special issues >>