|
|
- 2018
一种适于硬件实现的快速连通域标记算法
|
Abstract:
针对模式识别、计算机视觉和图像处理中常用的特征提取和选择问题,提出了一种适于硬件实现的快速连通域标记算法。首先进行行扫描,判定同一行内连续的前景像素,即游程,并记录游程的起始坐标和结束坐标;然后进行游程标记和等价游程对合并,对上述标记的游程根据连通情况对其赋予临时标记;最后扫描上一行游程,通过检测相应的标志位判断上一行游程是否真正结束,若已结束,将已结束区域信息进行输出,否则继续进行下一行的扫描。使用不同的二值图像进行实验,并与已有算法性能进行比较,仿真结果表明,所提出的快速连通域标记算法在速度和资源需求方面具有明显优势,对图像处理的平均帧率可以达到20帧/s以上,对于分辨率为2 048×1 536像素的图像,需求的片上存储资源约为3.45 Mbit,仅为块决策表算法的21.9％、He算法的7.6％左右。
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
| [1] | ［1］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. |
| [2] | ［2］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. |
| [3] | ［3］王凯, 施隆照. 基于FPGA的快速连通区域标记算法的设计与实现 ［J］. 计算机工程与应用, 2016, 52(18): 192？？198. |
| [4] | ［9］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. |
| [5] | ［10］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. |
| [6] | ［11］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. |
| [7] | ［12］冯海文, 牛连强, 刘晓明. 高效的一遍扫描式连通区域标记算法 ［J］. 计算机工程与应用, 2014, 50(23): 31？？35. |
| [8] | FENG Haiwen, NIU Lianqiang, LIU Xiaoming. Efficient one？？pass scanning connected area labeling algorithm ［J］. Computer Engineering and Design, 2014, 50(23): 31？？35. |
| [9] | ［13］王凯, 黄山, 赵瑜, 等. 面向图像目标提取的改进连通域标记算法 ［J］. 计算机工程与设计, 2014, 35(7): 2438？？2441. |
| [10] | 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. |
| [11] | ［14］刘关松, 吕嘉雯. 一种新的二值图像标记的快速算法 ［J］. 计算机工程与应用, 2002, 38(4): 57？？59. |
| [12] | ［15］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. |
| [13] | ［16］CHEN Baisheng. A new algorithm for binary connected components labeling ［J］. Computer Engineering and Applications, 2006, 42(25): 46？？47. |
| [14] | ［18］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. |
| [15] | ［19］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. |
| [16] | 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. |
| [17] | ［4］ROSENFELD A. Sequential operations in digital picture processing ［J］. Journal of the ACM, 1966, 13(4): 471？？494. |
| [18] | ［5］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. |
| [19] | ［6］HE Lifeng, CHAO Yuyan, SUZUKI K. A run？？based two？？scan labeling algorithm ［J］. IEEE Transactions on Image Processing, 2008, 17(5): 749？？756. |
| [20] | ［7］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. |
| [21] | ［8］HE Lifeng, CHAO Yuyan, SUZUKI K, et al. Fast connected？？component labeling ［J］. Pattern Recognition, 2009, 42(9): 1977？？1987. |
| [22] | LIU Guansong, L？a Jiawen. A new fast algorithm for binary image marking ［J］. Computer Engineering and Applications, 2002, 38(4): 57？？59. |
| [23] | ［17］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. |
