电子学报 ›› 2022, Vol. 50 ›› Issue (6): 1521-1536.DOI: 10.12263/DZXB.20210368

• 综述评论 • 上一篇    下一篇

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

曲立国1,2, 陈国豪1, 胡俊1, 陈鹏1   

  1. 1.安徽师范大学物理与电子信息学院, 安徽 芜湖 241002
    2.安徽省智能机器人信息融合与控制实验室, 安徽 芜湖 241002
  • 收稿日期:2021-03-16 修回日期:2022-03-09 出版日期:2022-06-25
    • 作者简介:
    • 曲立国 男,1979年出生,吉林舒兰人.安徽师范大学物理与电子信息学院副教授.主要研究方向为智能信息处理,检测技术与自动化装置.E-mail: qlg77@163.com
      陈国豪 男,1997年出生,安徽池州人.安徽师范大学物理与电子信息学院硕士研究生.主要研究方向为计算机视觉与自动化装置. E-mail: cgh591614156@163.com
      胡 俊 男,1996年出生,安徽六安人.安徽师范大学物理与电子信息学院硕士研究生.主要研究方向为智能信息处理与自动化装置.E-mail: 17856939565@163.com
      陈 鹏 男,1975年出生,安徽萧县人.安徽师范大学物理与电子信息学院讲师.主要研究方向为机器学习.E-mail: ahnuchp@ahnu.edu.cn
    • 基金资助:
    • 安徽省高等学校自然科学研究项目重点项目 (KJ2019A0511)

A Review of Single-pass Connected Component Analysis Algorithms

QU Li-gou1,2, CHEN Gou-hao1, HU Jun1, CHEN Peng1   

  1. 1.School of Physics and Electronic Information, Anhui Normal University, Wuhu, Anhui 241002, China
    2.Anhui Provincial Engineering Laboratory on Information Fusion and Control of Intelligent Robot, Wuhu, Anhui 241002, China
  • Received:2021-03-16 Revised:2022-03-09 Online:2022-06-25 Published:2022-06-25
    • Supported by:
    • Natural Science Research Project Key Program of colleges and Universities in Anhui Province (KJ2019A0511)

摘要:

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

Key words: connected component analysis, connected component labeling, feature extraction, image processing, FPGA

中图分类号: