戴华东，胡谋法，卢焕章，王阳
（国防科学技术大学自动目标识别重点实验室，湖南长沙410073）
摘要：在图像目标识别和跟踪任务中，连通域标记算法的设计优化主要体现在执行速度、存储空间和逻辑判断次数三个方面，因此提出并实现了一种基于一次逐像素扫描连通域标记的单目标检测算法。算法结合包围盒和单目标图像检测的特点，只需单行的图像缓存空间，同时简化复杂的等价标号替换操作，目标的判断准则为目标图像连通区域面积最大化，最终以包围盒形式给出目标位置。FPGA仿真结果表明：该方法资源占用率小，检测一幅图像的总时钟周期数为M×N×4（M，N 分别为图像行列数），适用于单目标图像的实时识别与跟踪。
教育期刊网 http://www.jyqkw.com
关键词 ：连通域标记；FPGA；目标检测；包围盒
中图分类号：TN911?34；TP391 文献标识码：A 文章编号：1004?373X（2015）20?0071?04
Design and implementation of target detection algorithm based onconnected?domain labeling
DAI Huadong，HU Moufa，LU Huanzhang，WANG Yang
（Key Laboratory on Automatic Target Recognition，National University of Defense Technology，Changsha 410073，China）
Abstract：In the task of image target recognition and tracking，the design optimization of connected?domain labeling algo?rithm is only reflected in three aspects：executing speed，storage space and numbers of logical judgment. That’s why a single?target detection algorithm based on single per?pixel scanning connected?domain labeling is proposed and realized. The algorithmcombines the characteristics of bounding box and single?target image detection，which only requires a single?line image cachingspace，while simplifying the complex equivalent label replacement operation. The target judging criteria is the maximized area oftarget image connected region，and the target location is given in the form of bounding box finally. The FPGA simulation resultsshow that the method has less resource consumption rate and total clock cycle number of detecting an image is M×N×4（M andN express the number of image rows and columns respectively），which is suitable for real?time recognition and tracking for sin?gle target image.
Keywords：connected?domain labeling；FPGA；object detection；bounding box
在精确制导图像目标识别和跟踪任务中，连通域标记算法用于从图像中提取目标区域，计算目标区域的特征参数，是图像处理系统中必不可少的环节。因此对于高帧频图像序列，研究如何优化底层二值图像连通域标记算法的时间性能、存储空间占用和可靠性，实现目标的检测识别，具有较大的应用价值。
目前常用的快速连通域标记算法大致可以归纳为以下3类：第1类是基于像素的1次或2次连通域标记算法[1]，其中2次扫描算法的第1次扫描获得所有像素点的临时标号（中间会有标号的等价处理操作），第2次扫描是替换已标记图像中等价的临时标号。1次与2次扫描算法的主要区别在于：1次扫描算法在等价标号替换过程中直接计算连通区域的特征（如面积、矩、包围盒、平均灰度值等）[1]。第2类是基于游程的1次或2次连通域标记算法[2]，和基于像素方法的差异在于：以游程代替像素作为基本处理单元，可以简化邻域标号关系的判断逻辑，减少标记结果所需的存储空间。第3类基于区域生长的连通域标记算法[3]采用种子点填充原理，可分为递归法和深度优先法等，此类方法均会消耗大量的内存空间，仅适用于小面积区域的标记。
在以上基本的连通域标记算法基础上，文献[4]结合基于像素和游程扫描算法的优点，利用树形拓扑结构完成等价标号替换，并输出线段作为结果，适于硬件实现，有较高的性能和执行效率。但对于大目标图像，图像处理所需时间和存储空间与直线段条数成正比关系，消耗资源较多。文献[5]用分段的思想替代游程，以段为标记单位，等价关系的计算量最小，时间性能远远优于其他算法。但其数据存储有像素点、直线段和线段块三级结构，对于多分叉情况会造成存储资源的浪费。文献[6]是结合游程和区域增长的改进算法，该算法不对二值图像进行逐行逐列扫描，简化了等价标号处理，一次性标记整个连通区域，但其受限于深度优先搜索思想，需要反复搜索每个连通体的邻域，降低了运行效率。可以看出，文献[4?6]中的连通域标记算法都是基于两条思路：存储空间的优化[4?5，7?9]，节省了FPGA上有限的存储资源；简化了等价标号的逻辑判断[4，6，10]，同时避免了连通信息的损失[11]。本文算法采用基于游程的连通判断方法[4]，结合包围盒和单目标图像的特点，只需单行的图像缓存空间，简化了复杂的等价标号替换操作。对于目标像素比较集中且连通的二值图像，进行一次逐像素扫描，以目标连通区域包围盒面积最大为判断准则，最终通过包围盒的形式给出图像中最大面积目标区域坐标位置，适用于单目标图像的实时识别与跟踪处理。
1 算法原理
本文算法按光栅扫描顺序（从上到下，从左到右），使用包围盒表示目标位置信息。算法的主要思路是：（1）在图像第1行，当遇到未标记的第1个目标点时，将该目标点作为新直线段的起点，向右扫描直到目标点构成直线段结束，并标上相应的标号，标号存储格式为info（x）={pix_value，line_start，col_min，col_max，row_min，label}（其中x 是对应的列号），并计算标号区域包围盒的面积aera。
（2）缓存上一行的标记结果，遇到未标记的直线段时，判断该直线与上一行已标记直线有无构成邻域关系。如果有则使用上一行的标号，并更新相应的包围盒信息；否则使用新的标号。
（3）重复以上操作。当遇到U字形结构（即当行的1条直线段分别与上行的2条直线段构成邻域关系），使用上行中左侧直线段的标号作为该直线段的标号。
（4）每条直线段处理完成时，计算该直线对应标号的包围盒面积aera_temp，并与之前缓存的最大面积aera_Max（初始值为0）比较，如果前者大则输出aera_Max_out，其中包含当条直线段对应标号的包围盒、标号和面积信息，否则不做任何处理。
（5）继续扫描图像，直到扫描到最后1行的最后1列。最终处理结果以目标所在连通域的包围盒[col_max，col_min，row_max，row_min]形式给出。
1.1 基于游程的图像标记
基于游程的图像标记算法是用直线段替代像素点作为基本标记处理单元，标记过程中会有两种情况：（1）当前行目标像素构成的直线段与上行目标像素没有构成邻域关系（图像第1行由于没有上行也当作这种情况），则在扫描到该线段最后1个像素点时给该直线段分配1个新的标号，如图1标号3的直线段；（2）当前行目标像素构成的直线段与上行目标像素构成邻域关系，则该直线段使用上1行的标号，如图1中标号1的直线段。 
如上描述，该方法的好处在于：1条直线段对应1个标记信息，存储量小，而且充分利用区域连通性的结构信息，减少了邻域逻辑判断。
1.2 等价关系处理
在图像标记过程中，当遇到U 型结构时，由于之前的目标像素已标记完成，且标号更新只能通过下一次逐像素扫描更改，因此会出现等价的临时标号，如图1中U型结构所示，可以看出标号1和标号2是属于同一连通区域，即构成等价关系（本文图1，图2，图3都是未做等价标号替换前的标号结果）。当图像比较复杂时，多个连通嵌套的U 型结构会导致复杂的等价标号替换逻辑。本文算法采用包围盒形式表示连通结构信息，简化了等价关系替换过程，思路如下：如图2所示，在检测到U 型结构时，比较上行标号4和标号5对应的[col_max，col_min，row_max，row_min]大小，将其合并同时使用左侧标号（即标号4），在当行直线段结束时，上行邻接的直线段信息即为合并后的标号信息，因此完成了等价标号包围盒信息的合并。对于连接的多个U型结构，均采用以上原则，最终上行合并后包围盒信息标号为4（即为最左侧标号）。 
1.3 同标号信息合并处理
算法的标号传递都是基于上一行目标直线段，对于同一行同标号的直线段，倒U型结构会导致整个连通区域出现分叉现象，如图3标号8的连通区域，分叉会导致在图像的同一行中多条直线段使用同一个标号，所以在标记过程中需要实时合并该标号的包围盒信息。由于同一行同标号直线段的条数、对应标号、中间间隔线段数等都不确定，所以需要对每一个标号对应的[col_max，col_min，row_max，row_min]参数建立1个更新表，在每1条直线段结尾处进行更新。对于256×256的图像，1行可能出现的最多线段条数是86条（只做行缓存），需要的存储空间是86×32 b，需要占用新的BRAM块。 
算法针对特定的单一目标，目标像素相对集中且连通，并且以包围盒形式输出目标位置是一种近似的结果。所以当只合并相邻的同标号直线段时，即对于图3情况，标号为9的直线段左右两边直线段（不相邻）不做合并，而其上行或下行的直线段同标号且相邻，则做合并操作，经测试该方法最终结果与建立更新表方法的结果一致。合并思路是先将2条直线段所属的包围盒信息合并，然后在第2条直线段结束时，将合并后的信息写入第1条直线段的行缓冲位置（即覆盖上一条直线段信息），节省了建立更新表所需的行缓存空间。
2 连通域标记的硬件实现
本文算法对图像进行单次从左到右，从上到下的扫描，扫描的同时进行图像标记。标记电路的输入是图像数据流（包括图像时钟、像素值、行列号、帧同步信号等），图像数据经行缓存后进行连通关系判断（本文采用四邻域），当1条直线段标记完成时，进行标号选择、行列坐标极值比较、标号合并等操作，最后将该直线段标记结果写入行缓存，输出目标包围盒结果，标记检测电路结构图如图4所示。 
2.1 连通关系判断模块
连通关系判断是整个电路最基本的模块，对于图像中任意一个像素点，连通关系判断过程中存在4种位置关系：直线段起点、中点、结束点和直线段外。算法基于这4个位置关系和像素点左侧、上方的邻域关系完成连通关系判断，流程图如图5所示。 
2.2 等价关系合并模块
如图2所示，本文算法的所有等价关系都来自于图中所示U 型结构，对于第2 行目标像素，当光栅扫描到第2个标号为4的像素时，从行缓存中读出的上行直线段的信息是{1，line_start，col_min，col_max，row_min，4}；光栅扫描到第3个标号为4的像素时，上行该像素值为0，直线段信息也为0；光栅扫描到第4 个标号为4 的像素时，从行缓存中读出的上行直线段的信息是{1，line_start，col_min，col_max，row_min，5}，在下一个时钟比较标号4和标号5的col_min，col_max，row_min值，并将合并后的包围盒参数写入当前上行直线段信息的临时变量中。即在光栅扫描到第5个标号为4的像素时，上行直线段信息已是合并后的包围盒信息，且标号修改为4。
3 实验结果
3.1 资源消耗
本文设计在Xilinx 公司的XC2V3000?4CG717 硬件平台上实现，对于大小为256×256的二值图像，行缓存采用256×36的BRAM，存储格式为：像素值（1位）、线段起始标志（1位）、标号（10位）、最大列号（8位）、最小列号（8 位）、最小行号（8 位）。经测试，此电路对大小为256×256 的二值图像，图像传输频率为25 MHz时，由于在1个像素的处理中，需要对当前像素的上一行对应像素信息进行读取和对当前像素信息的写入2次操作，为节省FPGA内部存储资源和避免存储器乒乓操作，本算法采用4倍图像传输时钟频率f（不高于30 MHz）对行缓存双口BlockRAM进行读写，所以标记一幅图像所需时间t=M×N× 4 f ，即能够在图像传输完成的同时输出标记结果。算法实现FPGA的内部资源占用如表1所示，从表中可以看出，算法的硬件实现所占用FPGA 各项内部资源均不超过1%。
3.2 仿真结果与分析
本文算法对目标图像有一定的针对性，要求目标单一且像素相对集中，所以选取如图6所示的6幅二值图像进行测试，标记检测电路对二值图像的处理结果如图6所示，并根据最终输出的包围盒结果以方框的形式在已标记目标区域显示出来。 
测试结果表明，标记电路能够准确定位目标（如图6目标连通区域均在方框内），并且在图像传输完成的同时输出标记结果。对于100 Hz 的帧频（10 ms/帧），25 MHz时钟速率下图像传输时间（也是图像处理时间）为1（2.5 × 10 7）×256×256≈1.85 ms，完全满足实时处理要求。该算法在图像目标由粗到精的检测识别硬件加速中应用前景广阔。例如，在粗识别过程通过包围盒锁定目标图像区域，为后期目标精确识别减少所需处理的数据量，为满足弹载平台目标识别算法的实时性奠定了基础。同时，虽然算法的设计针对单一目标，但对于已知的多个目标，存储多个连通区域面积较大的目标信息，可实现多目标的标记检测。另外在目标标记的同时可以计算目标面积、平均灰度值等目标特性参数，以获得更高的处理效率，具有较大的实用价值。
4 结论
本文针对单目标光学成像敏感器图像处理的实时性要求，提出了一种基于连通域标记的单目标检测算法。算法结合包围盒和单目标图像的特点，在图像传输过程中完成整幅图像的标记检测，并以包围盒形式给出图像中目标的坐标位置。算法以目标连通区域包围盒面积最大为判断准则，有一定的局限性。但其占用较少的存储空间，简化了复杂的等价标号替换操作，在弹载平台单一目标图像的实时识别与跟踪处理方面具有实用价值。
教育期刊网 http://www.jyqkw.com
参考文献
[1] BAILEY D G，JOHNSTON C T. Single pass connected compo?nents analysis [J]. Proceedings of Image and Vision Com?puting，2007，23（19）：282?287.
[2] 徐利华，陈早生.二值图像中的游程编码区域标记[J].光电工程，2004，31（6）：63?65.
[3] 夏晶，孙继银.基于区域生长的前视红外图像分割方法[J].激光与红外，2011，41（1）：107?111.
[4] 赵菲，张路，张志勇，等.基于硬件加速的实时二值图像连通域标记算法[J].电子与信息学报，2011，33（5）：1069?1075.
[5] 王静.二值图像连通域的分段标记算法及实现[J].红外与激光工程，2010（4）：761?765.
[6] 高红波，王卫星.一种二值图像连通区域标记的新算法[J].计算机应用，2008，27（11）：2776?2777.
[7] JOHNSTON C T，BAILEY D G. FPGA implementation of a sin?gle pass connected components algorithm [C] // Proceedings ofthe 4th IEEE International Symposium on Electronic Design，Test and Applications. [S.l.]：IEEE，2008：228?231.
[8] KLAIBER M，ROCKSTROH L，WANG Z，et al. A memory?ef?ficient parallel single pass architecture for connected compo?nent labeling of streamed images [J]. Field?Programmable Tech?nology，2012，10（12）：159?165.
[9] SANTIAGO D J C，REN T I，CAVALCANTI G D C，et al.Fast block?based algorithms for connected components labeling[C]// Proceedings of 2013 IEEE International Conference onAcoustics，Speech and Signal. [S.l.]：IEEE，2013：2084?2088.
[10] WU K，OTOO E，SHOSHANI A. Optimizing two?pass con?nected ? component labeling algorithms [J]. Pattern Analysisand Applications，2005，12（2）：117?135.
[11] 冯海文，牛连强，刘晓明.高效的一遍扫描式连通区域标记算法[J].计算机工程与应用，2014，50（23）：31?35.
作者简介：戴华东（1990—），男，湖南邵阳人，硕士研究生。主要研究方向为光学成像自动目标识别。
胡谋法（1979—），男，讲师。主要研究方向为光学信息处理、目标识别等。
卢焕章（1963—），男，博士生导师。主要研究方向为目标识别、实时系统与专用集成电路等。
