一种适于硬件实现的快速连通域标记算法

张国和; 徐快; 段国栋; 赵晨; 梁峰

doi:10.7652/xjtuxb201808015

您当前的位置：

首页 >

文章列表页 >

一种适于硬件实现的快速连通域标记算法

更新时间：2025-07-09

- 一种适于硬件实现的快速连通域标记算法
- A Fast Labeling Algorithm of Connected Components Applicable for Hardware Implementation
- 西安交通大学学报 2018年52卷第8期页码：95-101
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
  
  : 2018-03-12。作者简介: 张国和(1981—),男,副教授,博士生导师。基金项目:国家自然科学基金资助项目(61474093)
- DOI：10.7652/xjtuxb201808015
  中图分类号： TN492
- 网络首发：2018-08-10，
  
  纸质出版：2018
- 稿件说明：
移动端阅览
张国和, 徐快, 段国栋, 等. 一种适于硬件实现的快速连通域标记算法[J]. 西安交通大学学报, 2018,52(8):95-101.

A Fast Labeling Algorithm of Connected Components Applicable for Hardware Implementation[J]. 2018, 52(8): 95-101.
张国和, 徐快, 段国栋, 等. 一种适于硬件实现的快速连通域标记算法[J]. 西安交通大学学报, 2018,52(8):95-101. DOI： 10.7652/xjtuxb201808015.

A Fast Labeling Algorithm of Connected Components Applicable for Hardware Implementation[J]. 2018, 52(8): 95-101. DOI： 10.7652/xjtuxb201808015.

摘要

针对模式识别、计算机视觉和图像处理中常用的特征提取和选择问题

提出了一种适于硬件实现的快速连通域标记算法。首先进行行扫描

判定同一行内连续的前景像素

即游程

并记录游程的起始坐标和结束坐标; 然后进行游程标记和等价游程对合并

对上述标记的游程根据连通情况对其赋予临时标记; 最后扫描上一行游程

通过检测相应的标志位判断上一行游程是否真正结束

若已结束

将已结束区域信息进行输出

否则继续进行下一行的扫描。使用不同的二值图像进行实验

并与已有算法性能进行比较

仿真结果表明

所提出的快速连通域标记算法在速度和资源需求方面具有明显优势

对图像处理的平均帧率可以达到20帧/s以上

对于分辨率为2 048×1 536像素的图像

需求的片上存储资源约为3.45 Mbit

仅为块决策表算法的21.9%、He算法的7.6%左右。

Abstract

A fast labeling algorithm of connected components applicable for hardware implementation is proposed for feature extraction and selection that are commonly used in pattern recognition

computer vision and image processing. First

row scanning is performed to determine consecutive foreground pixels in the same row

i.e.

runs

and to record the start and end coordinates of the runs. Then

the run labels and the equivalent run pairs are merged

and temporary values are assigned to these labeled runs according to the connection conditions. Finally

runs of the last row is scanned to determine whether the run of the last row is really over by detecting the corresponding flag bit if it is really finished

and the information of finished region is output

otherwise the next row is scanned. Experiments using different binary images and comparisons with the performance of existing algorithms show that the proposed algorithm has obvious advantages in speed and resource requirements. The average frame rate of image processing speed reaches up to 20 frames/s

and the algorithm requires about 3.45 Mbit on-chip memory resource for an image with a resolution of 2 048×1 536 pixels

which is only 21.9% and 7.6% of the requirements of the block based decision table algorithm and the He algorithm

respectively.

关键词

Keywords

references

HUGO H, FREDRIK K, VIKTOR O. Implementation of a labeling algorithm based on contour tracing with feature extraction [C]∥Proceedings of IEEE International Symposium on Circuits and Systems. Piscataway, NJ, USA: IEEE, 2007: 1101-1104.

AYMAN A, RAMI Q, STAN I, et al. One scan connected component labeling technique [C]∥Proceedings of 2007 IEEE International Conference on Signal Processing and Communications. Piscataway, NJ, USA: IEEE, 2007: 1283-1286.

王凯, 施隆照. 基于FPGA的快速连通区域标记算法的设计与实现 [J]. 计算机工程与应用, 2016, 52(18): 192-198.

WANG Kai, SHI Longzhao. Design and implementation of fast connected region marking algorithm based on FPGA [J]. Computer Engineering and Applications, 2016, 52(18): 192-198.

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

CHANG Fu, CHEN Chunjin, LU Chijin. A linear-time component-labeling algorithm using contour tracing technique [J]. Computer Vision and Image Understanding, 2004, 93(2): 741-745.

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

HE Lifeng, CHAO Yuyan, SUZUKI K, et al. Linear-time two-scan labeling algorithm [C]∥Proceedings of the IEEE International Conference on Image Processing. Piscataway, NJ, USA: IEEE, 2007: 241-244.

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

COSTANTINO G, DANIELE B, RITA C. Optimized block-based connected components labeling with decision trees [J]. IEEE Transactions on Image Processing, 2010, 19(6): 1596-1609.

KOFI A, ANDREW H, PATRICK D, et al. A run-length based connected component algorithm for FPGA implementation [C]∥Proceedings of the International Conference on Field-Programmable Technology. Piscataway, NJ, USA: IEEE, 2008: 177-184.

JOHNSTON CT, BAILEY DG. FPGA implementation of a single pass connected components algorithm [C]∥Proceedings of the IEEE International Symposium on Electronic Design, Test and Applications. Piscataway, NJ, USA: IEEE, 2008: 228-231.

冯海文, 牛连强, 刘晓明. 高效的一遍扫描式连通区域标记算法 [J]. 计算机工程与应用, 2014, 50(23): 31-35.

FENG Haiwen, NIU Lianqiang, LIU Xiaoming. Efficient one-pass scanning connected area labeling algorithm [J]. Computer Engineering and Design, 2014, 50(23): 31-35.

王凯, 黄山, 赵瑜, 等. 面向图像目标提取的改进连通域标记算法 [J]. 计算机工程与设计, 2014, 35(7): 2438-2441.

WANG Kai, HUANG Shan, ZHAO Yu, et al. Improved connected domain marking algorithm for image object extraction [J]. Computer Engineering and Design, 2014, 35(7): 2438-2441.

刘关松, 吕嘉雯. 一种新的二值图像标记的快速算法 [J]. 计算机工程与应用, 2002, 38(4): 57-59.

LIU Guansong, LÜ Jiawen. A new fast algorithm for binary image marking [J]. Computer Engineering and Applications, 2002, 38(4): 57-59.

DIEGO J C, SANTIAGO R, CAVALCANTI G, et al. Efficient 2×2 block-based connected components labeling algorithms [C]∥Proceedings of the IEEE International Conference on Image Processing. Piscataway, NJ, USA: IEEE, 2015: 4818-4822.

CHEN Baisheng. A new algorithm for binary connected components labeling [J]. Computer Engineering and Applications, 2006, 42(25): 46-47.

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-2.

WANG J Z, LI J, WIEDERHOLD G. Semantics-sensitive integrated matching for picture libraries [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(9): 947-963.

SUTHEEBANJARD P, PREMCHAISWADI W. Efficient scan mask techniques for connected components labeling algorithm [J]. Eurasip Journal on Image and Video Processing, 2011(1):1-20.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

深度学习驱动的碳纤维管壁缺陷镜面红外检测无损定量评估方法

一种Roberts自适应边缘检测方法

从高空摄像中获取车辆瞬态信息和驾驶行为

焊缝结构光图像处理与特征提取方法

采用自主图像处理程序的非侵入式滚动轴承保持架运动轨迹提取方法