A Provisional Labels-Reduced, Real-Time Connected Component Labeling Algorithm for Edge Hardware
- 18 February 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems II: Express Briefs
- Vol. 69 (6) , 2997-3001
Abstract
Connected component labeling (CCL) is an important operation in computer vision tasks, widely used for real-time image processing on edge hardware. The existing connected component labeling algorithms always generate plenty of provisional labels. Solving the equivalence of provisional labels needs much memory access and processing time. The greater difficulty is that the processing time varies with the number and shape of the connected components. To solve the problems, this brief proposes a new two-scan CCL algorithm. It consists of novel provisional label predicting and provisional label assignment methods based on predicting table, linked lists, and equivalent table. The provisional label predicting method reduces the number of provisional labels effectively. The provisional label assignment method can implement quickly the assignment operation of CCL by combination of the first scan and the second scan with fixed processing time. We have implemented the proposed algorithm on Field Programmable Gate Arrays (FPGA) for raster scan images. The results show that its processing speed can achieve 726fps@225MHz for $640\times 480$ image resolution, and its resource utilization is less than 15% of compared implementation. It is suitable for real-time edge applications. Compared with other algorithms, the proposed algorithm reduces provisional labels efficiently and completes the CCL operation with a fixed number of iterations. Therefore, it shortens processing time and makes the processing time constant.Keywords
Funding Information
- National Key Research and Development Program of China (2019YFB2204303)
- National Natural Science Foundation of China (U20A20205)
- Youth Innovation Promotion Association Program Chinese Academy of Sciences (2021109)
This publication has 29 references indexed in Scilit:
- Optimized Connected Components Labeling with Pixel Prediction2016
- Block-Based Connected-Component Labeling Algorithm Using Binary Decision TreesSensors, 2015
- A Resource-Efficient Hardware Architecture for Connected Component AnalysisIEEE Transactions on Circuits and Systems for Video Technology, 2015
- Configuration-Transition-Based Connected-Component LabelingIEEE Transactions on Image Processing, 2013
- Optimized Block-Based Connected Components Labeling With Decision TreesIEEE Transactions on Image Processing, 2010
- Light speed labeling: efficient connected component labeling on RISC architecturesJournal of Real-Time Image Processing, 2009
- Fast connected-component labelingPattern Recognition, 2009
- A Run-Based Two-Scan Labeling AlgorithmIEEE Transactions on Image Processing, 2008
- Optimizing two-pass connected-component labeling algorithmsPattern Analysis and Applications, 2008
- A simple and efficient connected components labeling algorithm2003