A Fast Labeling Algorithm of Connected Components Applicable for Hardware Implementation

doi:10.7652/xjtuxb201808015

您当前的位置：

首页 >

文章列表页 >

A Fast Labeling Algorithm of Connected Components Applicable for Hardware Implementation

更新时间：2025-07-09

- A Fast Labeling Algorithm of Connected Components Applicable for Hardware Implementation
- Vol. 52, Issue 8, Pages: 95-101(2018)
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201808015
  CLC： TN492
- Online First：10 August 2018，
  
  Published：2018
- 稿件说明：
移动端阅览
A Fast Labeling Algorithm of Connected Components Applicable for Hardware Implementation[J]. 2018, 52(8): 95-101.
DOI：

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Intelligent Quantitative Non-Destructive Evaluation Method for Delamination of Carbon Fiber Composite Tube with Mirror-Reflection Infrared Thermography

A Roberts' Adaptive Edge Detection Method

Obtaining Transient Information of Vehicles and Behaviors of Drivers from High-Altitude Photography

Image Processing and Feature Extraction for Structured Light Images of Welded Seam

A Non-Intrusive Rolling Bearing Cage Trajectory Extraction Method Using Image Processing Program

Related Author

CHEN Zhenmao

PEI Cuixiang

TONG Zongfei

LIU Bofan

CHEN Hongen

YANG Yang

王宝树 1

许庆功 3

Related Institution

Shaanxi Engineering Research Center of Nondestructive Testing and Structural Integrity Evaluation，Xi’an Jiaotong University

State Key Laboratory for Strength and Vibration of Mechanical Structures，Xi’an Jiaotong University

School of Aerospace Engineering，Xi’an Jiaotong University

School of Computer, Xidian University

Academy of Information Technology, Luoyang Normal University

⁰