单次扫描连通域分析算法研究综述

A Review of Single-pass Connected Component Analysis Algorithms

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

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.