A Review of Single-pass Connected Component Analysis Algorithms

QU Li-gou; CHEN Gou-hao; HU Jun; CHEN Peng

doi:10.12263/DZXB.20210368

您当前的位置：

首页 >

文章列表页 >

A Review of Single-pass Connected Component Analysis Algorithms

SURVEYS AND REVIEWS | 更新时间：2025-12-08

- A Review of Single-pass Connected Component Analysis Algorithms
- ACTA ELECTRONICA SINICA Vol. 50, Issue 6, Pages: 1521-1536(2022)
- 作者机构：
  
  1.安徽师范大学物理与电子信息学院,安徽芜湖 241002
  2.安徽省智能机器人信息融合与控制实验室,安徽芜湖 241002
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20210368
  CLC： TP211;
- Received：16 March 2021，
  
  Revised：2022-03-09，
  
  Published：25 June 2022
- 稿件说明：
移动端阅览
曲立国,陈国豪,胡俊等.单次扫描连通域分析算法研究综述[J].电子学报,2022,50(06):1521-1536.

QU Li-gou,CHEN Gou-hao,HU Jun,et al.A Review of Single-pass Connected Component Analysis Algorithms[J].ACTA ELECTRONICA SINICA,2022,50(06):1521-1536.
曲立国,陈国豪,胡俊等.单次扫描连通域分析算法研究综述[J].电子学报,2022,50(06):1521-1536. DOI： 10.12263/DZXB.20210368.

QU Li-gou,CHEN Gou-hao,HU Jun,et al.A Review of Single-pass Connected Component Analysis Algorithms[J].ACTA ELECTRONICA SINICA,2022,50(06):1521-1536. DOI： 10.12263/DZXB.20210368.

摘要

连通域分析在单次扫描中标记像素同时提取每个连通域的特征数据，是二值图像处理的重要步骤之一.基于FPGA的硬件架构实现单次扫描连通域分析算法可以实现快速位流图像实时处理.本文重点分析了近十年来发展的连通域标记算法和单次扫描连通域分析算法，阐述了典型连通域分析算法的实现策略和框架，给出了它们的伪代码，并描述了它们的联合查找算法.此外，通过数据对比，从算法硬件架构的内存需求和吞吐量等方面对不同算法的性能进行了比较分析，并总结了它们的优缺点.分析结论为实现基于FPGA高速位流图像的连通域检测提供了理论依据和数据参考.

Abstract

Connected component analysis(CCA) is one of the major steps in binary image processing

which label pixels in single-pass and extract the features of each connected component at the same time. Single-pass connected component analysis algorithm based on FPGA hardware architecture can realize fast real-time bit stream image processing. In this article

we focus on connected component labeling(CCL) algorithms and single-pass connected component analysis algorithms developed in the last decade

explain the implementation strategies and architectures of the typical connected component analysis algorithms

present their pseudo codes

and describe their Union-find algorithms. In addition

through data comparison

the performance of different algorithms is compared and analyzed in terms of memory requirements and throughput of algorithm hardware architectures

and their advantages and disadvantages are summarized. The analysis results provide a theoretical basis and data reference for the realization of connected component detection based on FPGA high-speed bit stream images.

关键词

Keywords

references

CHEN W J , GIGER M L , BICK U . A fuzzy c-means (FCM)-based approach for computerized segmentation of breast lesions in dynamic contrast-enhanced MR Images [J]. Academic Radiology , 2006 , 13 ( 1 ): 63 - 72 .

DING M , CAO Y F , WU Q X . Autonomous craters detection from planetary image [C]// Proceedings of the 3rd International Conference on Innovative Computing Information and Control (ICICIC 2008) . Dalian : IEEE Computer Society , 2008 : 443 - 443 .

ABUZAGHLEH O , BARKANA B D , FAEZIPOUR M . Noninvasive real-time automated skin lesion analysis system for melanoma early detection and prevention [J]. IEEE Journal of Translational Engineering in Health and Medicine , 2015 , 3 : 1 - 12 .

LAO W L , HAN J G , DE P . Automatic video-based human motion analyzer for consumer surveillance system [J]. IEEE Transactions on Consumer Electronics , 2009 , 55 ( 2 ): 591 - 598 .

JOSHI K A , THAKORE D G . A survey on moving object detection and tracking in video surveillance system [J]. International Journal of Soft Computing and Engineering , 2012 , 2 ( 3 ): 44 - 48 .

CHENG H Y , WENG C C , CHEN Y Y . Vehicle detection in aerial surveillance using dynamic bayesian networks [J]. IEEE Transactions on Image Processing , 2012 , 21 ( 4 ): 2152 - 2159 .

曲立国 , 黄友锐 , 唐超礼 , 等 . 基于FPGA的线阵CCD雨滴图像快速连续识别方法 [J]. 光电工程 , 2012 , 39 ( 10 ): 103 - 110 .

QU L G , HUANG Y R , TANG C L , et al . Rapid and continuous identification method of linear array ccd dynamic raindrop image based on FPGA [J]. Opto-Electronic Engineering , 2012 , 39 ( 10 ): 103 - 110 .

MOHAMED A A , YAMPOLSKIY R V . An improved LBP algorithm for avatar face recognition [C]// Proceeding of the XXIII International Symposium on Information, Communication and Automation Technologies(ICAT) . Sarajevo, Bosnia and Herzegovina : IEEE Computer Society 2011 : 1 - 5 .

华彩成 , 王世凯 , 张成峰 , 等 . 返回散射电离图仰角信息提取方法研究 [J]. 电子学报 , 2019 , 47 ( 11 ): 2438 - 2442 .

HUA C C , WANG S K , ZHANG C F , et al . Research on Extraction Method of Elevation from Backscatter Lonogram [J]. Acta Electronica Sinica , 2019 , 47 ( 11 ): 2438 - 2442 .

ROSENFELD A , PFALTZ J L . Sequential operations in digital picture processing [J]. Journal of the ACM , 1966 , 13 : 471 - 494 .

LUMIA R , SHAPIRO L , ZUNIGA O . A new connected components algorithm for virtual memory computers [J]. Computer Vision Graphics and Image Processing , 1983 , 22 ( 2 ): 287 - 300 .

RONSE C , DEJVIJVER P . Connected Components In Binary Images:The Detection Problems [M]. Letchworth : Hertfordshire Research Studies Press , 1984 .

HARALICK R M . Some neighborhood operations [C]//Rosenfeld A. Real-Time Parallel Computing Image Analysis . New York : Plenum Press , 1981 : 11 - 35 .

SUZUKI K , HORIBA I , SUGIE N . Linear-time connected-component labeling based on sequential local operations [J]. Computer Vision and Image Understanding , 2003 , 89 ( 1 ): 1 - 23 .

CHANG F , CHEN C J , LU C J . A linear-time component-labeling algorithm using contour tracing technique [J]. Computer Vision and Image Understanding , 2004 , 93 ( 2 ): 206 - 220 .

CHANG F , CHEN C J . A component-labeling algorithm using contour tracing technique [C]// Proceedings of the Seventh International Conference on Document Analysis and Recognition(ICDAR 2003) . Edinburgh : IEEE Computer Society , 2003 : 741 - 745 .

SUN D , LIU Y . A new contour tracing algorithm in eight-connected binary images [C]// Proceedings of the 2010 Third International Joint Conference on Computational Science and Optimization . Huangshan : IEEE Computer Society , 2010 : 249 - 253 .

LIU Y , ZHU M . A new contour tracing automaton in binary image [C]// Proceedings of IEEE international conference in computer science and automation engineering . Shanghai : IEEE Computer Society , 2011 : 577 - 581 .

STEFANO L D , BULGARELLI A . A simple and efficient connected components labeling algorithm [C]// Proceedings of the 10th International Conference on Image Analysis and Processing . Venice : IEEE Computer Society , 1999 : 322 - 327 .

APPIAH K , HUNTER A , DICKINSON P , et al . A run-length based connected component algorithm for FPGA implementation [C]// Proceedings of the 2008 International Conference on Field-Programmable Technology(FPT) . Taipei : IEEE Computer Society , 2008 : 177 - 184 .

HE L , CHAO Y , SUZUKI K . A run-based two-scan labeling algorithm [J]. IEEE Transactions on Image Processing , 2008 , 17 ( 5 ): 749 - 756 .

HE L , ZHAO X , CHAO Y , et al . Configuration-transition-based connected-component labeling [J]. IEEE Transactions on Image Processing , 2014 , 23 ( 2 ): 943 - 951 .

ZHAO X , HE L , YAO B , et al . A new connected-component labeling algorithm [J]. IEICE Transactions on Information and Systems , 2015 , 98 ( 11 ): 2013 - 2016 .

HE L , CHAO Y , SUZUKI K . An run-based one-and-a-half-scan connected-component labeling algorithm [J]. International Journal of Pattern Recognition and Artificial Intelligence , 2010 , 24 ( 4 ): 557 - 579 .

WU K , OTOO E , SUZUKI K . Optimizing two-pass connected-component labeling algorithms [J]. Pattern Analysis and Applications , 2009 , 12 ( 2 ): 117 - 135 .

GRANA C , BORGHESANI D , CUCCHIARA R . Optimized block-based connected components labeling with decision trees [J]. IEEE Transactions on Image Processing , 2010 , 19 ( 6 ): 1596 - 1609 .

HE L , CHAO Y , SUZUKI K , et al . Fast connected-component labeling [J]. Pattern Recognition , 2009 , 42 ( 9 ): 1977 - 1987 .

HE L , CHAO Y , SUZUKI J . An efficient first-scan method for label-equivalence-based labeling algorithms [J]. Pattern Recognition Letters , 2010 , 31 ( 1 ): 28 - 35 .

ZHAO F , ZHANG Z Y . Hardware acceleration based connected component labeling algorithm in real-time ATR system [C]// Proceedings of SPIE 8784, Fifth International Conference on Machine Vision(ICMV 2012): Algorithms, Pattern Recognition, and Basic Technologies . Wuhan : Society of Photo-Optical Instrumentation Engineers , 2013 : 87841S .

CABARET L , LACASSAGNE L , OUDNI L . A review of world's fastest connected component labeling algorithms: speed and energy estimation [C]// Proceedings of the International Conference on Design and Architectures for Signal and Image Processing(DASIP) . Madrid : IEEE , 2014 : 1 - 6 .

CABARET L , LACASSAGNE L . What is the world's fastest connected component labeling algorithm [C]// Proceedings of the 2014 IEEE Workshop on Signal Processing Systems(SiPS) . Belfast : IEEE , 2014 : 1 - 6 .

CHANG W Y , CHIU C C , YANG J H . Block-based connected-component labeling algorithm using binary decision trees [J]. Sensors , 2015 , 15 ( 9 ): 23763 - 23787 .

ROUABEH H , ABDELMOULA C , et. al . A new efficient connected component labeling algorithm and its VHDL circuit [C]// Proceedings of the 2016 28th International Conference on Microelectronics(ICM) . Giza : IEEE Circuits and Systems Society , 2016 : 105 - 108 .

GUPTA S , PALSETIA D , PATWARY M M A , et al . A new parallel algorithm for two-pass connected component labeling [C]// Proceedings of the 2014 IEEE International Parallel and Distributed Processing Symposium Workshops(IPDPSW) . Phoenix : IEEE , 2014 : 1355 - 1362 .

HE L , REN X , GAO Q , et al . The connected-component labeling problem: A review of state-of-the-art algorithms [J]. Pattern Recognition , 2017 , 70 : 25 - 43 .

NIU L Q , CHEN X , PENG M , et al . Connected components labeling based on union-find operations applied to connected branches [J]. Journal of Intelligent and Fuzzy Systems , 2017 , 32 ( 5 ): 3739 - 3748

HOPCROFT J E , ULLMAN J D . Set merging algorithms [J]. SIAM Journal on Computing , 1973 , 2 ( 4 ): 294 - 303 .

TARJAN R E , LEEUWEN J V . Worst-case analysis of set union algorithms [J]. Journal of the Assoaatton for Computmg Machinery , 1984 , 31 ( 2 ): 245 - 281 .

DILLENCOURT M B , SAMET H , TAMMINEN M . A general approach to connected-component labeling for arbitrary image representations [J]. Journal of the Assoaatton for Computmg Machinery , 1992 , 39 ( 2 ): 253 - 280 .

WU K , OTOO E , SHOSHANI A . Optimizing connected component labeling algorithms [C]// Proceedings of Image Processing . San Diego, California : The International Society for Optical Engineering , 2005 : 1951 - 1976 .

ABUBAKER A , QAHWAJI R , IPSON S , et al . One scan connected component labeling technique [C]// Proceedings of the 2007 IEEE International Conference on Signal Processing and Communications(ICSPC 2007) . Dubai : IEEE Computer Society , 2007 : 1283 - 1286 .

BAILEY D G , JOHNSTON C T . Single pass connected components analysis [C]// Proceedings of Image and Vision Computing . New Zealand : IEEE , 2007 : 282 - 287 .

Bailey D , Johnston C , Ma N . Connected components analysis of streamed images [C]// Proceedings of the 2008 International Conference on Field Programmable Logic and Applications(FPL) . Heidelberg : IEEE Computer Society , 2008 : 679 - 682 .

JOHNSTON C , BAILEY D . FPGA implementation of a single pass connected components algorithm [C]// Proceedings of the 4th International Symposium on Electronic Design, Test and Applications . Hong Kong : IEEE Computer Society , 2008 : 228 - 231 .

MA N , BAILEY D G , JOHNSTON C T . Optimised single pass connected components analysis [C]// Proceedings of the 2008 International Conference on Field-Programmable Technology(FPT) . Taipei : IEEE Computer Society , 2008 : 185 - 192 .

KLAIBER M , ROCKSTROH L , WANG Z , et al . A memory-efficient parallel single pass architecture for connected component labeling of streamed images [C]// Proceedings of the 2012 International Conference on Field-Programmable Technology(FPT) . Seoul : IEEE Computer Society , 2012 : 159 - 165 .

KLAIBER M , BAILEY D , AHMED S , et al . A high-throughput FPGA architecture for parallel connected components analysis based on label reuse [C]// Proceedings of the 2013 International Conference on Field-Programmable Technology(FPT) . Kyoto : IEEE Computer Society , 2013 : 302 - 305 .

KLAIBER M , BAILEY D , BAROUD Y , et al . A resource-efficient hardware architecture for connected components analysis [J]. IEEE Transactions on Circuits and Systems for Video Technology , 2016 , 26 ( 7 ): 1334 - 1349 .

KLAIBER M , BAILEY D , SIMON S . A single-cycle parallel multi-slice connected components analysis hardware architecture [J]. Journal of Real-Time Image Processing , 2019 , 16 ( 4 ): 1151 - 1175 .

KLAIBER M , BAILEY D , SIMON S . Comparative study and proof of single-pass connected components algorithms [J]. Journal of Mathematical Imaging and Vision , 2019 , 61 : 1112 - 1134 .

BAILEY D , KLAIBER M . Zig-Zag based single-pass connected components analysis [J]. Journal of Imaging , 2019 , 5 ( 4 ): 45 .

TREIN , J , SCHWARZBACHER A T , HOPPE B , et al . Development of a FPGA based real-time blob analysis circuit [C]// Proceedings of the Irish Signals and Systems Conference . Derry : IEEE , 2007 : 121 - 126 .

ZHAO F , LU H Z , ZHANG Z Y . Real-time single-pass connected components analysis algorithm [J]. EURASIP Journal on Image and Video Processing , 2013 , 1 : 21 .

TANG J W , SHAIKH H N , SHEIKH U U , et al . A linked list run-length-based single-pass connected component analysis for real-time embedded hardware [J]. Journal of Real-Time Image Processing , 2018 , 15 ( 1 ): 197 - 215 .

GU Q Y , TAKAKI T , ISHII I . 2000-fps multi-object extraction based on cell-based labeling [C]// Proceedings of the 2010 IEEE International Conference on Image Processing(ICIP 2010) . Hong Kong : IEEE , 2010 : 3761 - 3764 .

GU Q , TAKAKI T , ISHII I . A fast multi-object extraction algorithm based on cell-based connected components labeling [J]. IEICE Transactions on Information and Systems , 2012 , E95.D( 2 ): 636 - 645 .

GU Q , TAKAKI T , ISHII I . Fast FPGA-based multi-object feature extraction [J]. IEEE Transactions on Circuits and Systems for Video Technology , 2013 , 23 ( 1 ): 30 - 45 .

JEONG J , LEE G , LEE M , et al . A single-pass connected component labeler without label merging period [J]. Journal of Signal Processing Systems , 2016 , 84 ( 2 ): 211 - 223 .

ISHII I , TATEBE T , GU Q Y , et al . 2000 fps real-time vision system with high-frame-rate video recording [C]// Proceedings of the 2010 IEEE International Conference on Robotics and Automation(ICRA 2010) . Anchorage : IEEE , 2010 : 1536 - 1541 .

KUMAR V S , IRICK K , MAASHRI A A , et al . A scalable bandwidth aware architecture for connected component labeling [C]// Proceedings of the 2010 IEEE Computer Society Annual Symposium on VLSI(ISVLSI) . Lixouri : IEEE , 2010 : 116 - 121 .

赵峙江 , 张田文 , 张志宏 . 一种基于视觉模型与连通域统计的阈值分割新算法 [J]. 电子学报 , 2005 , 33 ( 5 ): 793 - 797 .

ZHAO S J , ZHANG T W , ZHANG Z H . A Novel Threshold Algorithm about Image Segmentation Based on Vision Model and Statistics of Consecutive Fields [J]. Acta Electronica Sinica , 2005 , 33 ( 5 ): 793 - 797 .

MALIK A W , THÖRNBERG B , IMRAN M , et al . Hardware architecture for real-time computation of image component feature descriptors on a FPGA [J]. International Journal of Distributed Sensor Networks , 2014 ( 1 ): 1 - 14 .

YU Z Q , CLAESEN L , PAN Y , et al . SoC processor for real-time object labeling in life camera streams with low line level latency [C]// Proceedings of the 2014 IEEE International Symposium on Circuits and Systems(ISCAS) . Melbourne : IEEE , 2014 : 345 - 348 .

TAYARA H , HAM W , CHONG K T . A real-time marker-based visual sensor based on a fpga and a soft core processor [J]. Sensors , 2016 , 16 ( 12 ): 2139 .

LING L , CHEN Z , LI S , et al . FPGA-based connected components analysis algorithm without equivalence-tables [C]// Proceedings of the 10th International Conference on Intelligent Robotics and Applications(ICIRA 2017) . Wuhan : Lecture Notes in Computer Science , 2017 : 543 - 553 .

SPAGNOLO F , FRUSTACI F , PERRI S , et al . An efficient connected component labeling architecture for embedded systems [J]. Journal of Low Power Electronics and Applications , 2018 , 8 ( 1 ): 7 .

SPAGNOLO F , PERRI S , FRUSTACI F , et al . Connected component analysis for traffic sign recognition embedded processing systems [C]// Proceedings of the 2018 IEEE 25th International Conference on Electronics, Circuits and Systems(ICECS) , Bordeaux : IEEE , 2018 : 749 - 752 .

SPAGNOLO F , PERRI S , CORSONELLO P . An efficient hardware-oriented single-pass approach for connected component analysis [J]. Sensors , 2019 , 19 ( 14 ): 3055 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Abnormal Event Detection Based on Deep Learning

Survey of Object Detection Based on Deep Learning

Operator Fusion Method and Hardware Architecture Design Based on Non-Standard Operators

Research on Dynamic Continuous Emotional Recognition of EEG Based on Improved TCNN Algorithm

Research on Lightweight Sensing Technology Based on Single Antenna and Multiple Subcarriers

Related Author

WEN Jia

WANG Hong-jun

DENG Jia

LIU Peng-fei

LUO Hui-lan

CHEN Hong-kun

WANG Ying

GAO Lan

Related Institution

School of Information Science and Engineering, Yanshan University

The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province

State Key Laboratory of Software Engineering of Hebei Province

School of Information Science and Engineering Yanshan University Qinhuangdao Hebei China

The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province Qinhuangdao Hebei China

⁰