传统的面向CPU的连通域标记算法都是以串行执行为基础,优化的方向是如何减少运算量。本文提出了一种新的面向CPU的实时二值图像连通域标记方法。并行计算包含3个层级,分别是指令级并行、函数级并行(软件流水)和多核并行。针对这3个层级,本文提出了3种优化方法:位或操作、循环体分解和数据分块。本方法运算耗时受背景复杂度的影响小,同时可以按行处理,特别适合对串行传输的图像进行连通域标记。
Abstract
The traditional CPU oriented method of connected domain labeling algorithms are based on serial execution,and the optimization direction is how to reduce the amount of computation.In the paper,a new CPU oriented method for marking the connected domain of real-time binary images is proposed.The parallel computing consists of three levels:instruction level parallelism,function level parallelism(software pipelining) and multi-core parallelism.For these three levels,this paper proposes three optimization methods:bit or operation,loop volume decomposition and data blocking.This method has little influence on the operation time by the background complexity,and can be processed by line.It is especially suitable for marking the connected domain of serial transmitted images.
关键词
连通域标记 /
CPU /
并行计算
Key words
connected component labeling /
CPU /
parallel computing
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] 吕璐,程虎,朱鸿泰,等.基于深度学习的目标检测研究与应用综述[J].电子与封装,2022,22(1):72-80.
[2] 张国和,徐快,段国栋,等.一种适于硬件实现的快速连通域标记算法[J].西安交通大学学报,2018,52(8):95-101.
[3] 赵菲,张路,张志勇,等.基于硬件加速的实时二值图像连通域标记算法[J].电子与信息学报,2011,33(5):1069-1075.
[4] 覃方涛,房斌.GPU加速的二值图连通域标记并行算法[J].计算机应用,2010,30(10):2774-2776.
[5] 甘晓英,白阳,何晓栋,等.一种并行二值图像连通域标记算法[J].计算机与数字工程,2021,49(5):993-997,1002.
[6] NAKASHIMA S,NAITO T.Program optimization method, progtram optimazation program,and program optimization apparatus:US 14/799,625[P].2015-07-15.
[7] 马益杭,占利军,谢传节,等.连通域标记算法的并行化研究[J].地理与地理信息科学,2013,29(4):67-71,2.
[8] 吴倩,王小航.众核任务映射算法研究现状与发展趋势[J].电子与封装,2022,22(2):66-72.
[9] 冯海文,牛连强,刘晓明.高效的一遍扫描式连通区域标记算法[J].计算机工程与应用,2014,50(23):31-35.
[10] Wu K,Otoo E,Suzuki K.Optimizing two-pass connected-component labeling algorithms[J].Advanced in Soft Computing,2011,7095(12):452-462.
[11] 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.
[12] He Li-feng,Chao Yu-yan,Susuki Ken-ji.A run-based two-scan labeling algorithm[J].IEEE Transaction on Image Processsing,2008,17(5):749-756.
PDF(1215 KB)
