基于FPGA 的快速连通域标记算法*

黄名政，李彬华，2*，王锦良

(1.昆明理工大学信息工程与自动化学院，云南 昆明650500；2.昆明理工大学云南省计算机技术应用重点实验室，云南 昆明650500)

连通域标记是机器人视觉、目标跟踪与识别、交通检测和字符识别等领域的基础与前提[1-2]，在图像分析、模式识别和计算机视觉中也扮演着重要角色[3]。 对于实时性要求较高的图像处理系统，通常可使用图形处理单元(GPU)、FPGA 等以附加硬件的方式进行加速处理，特别是小型设备中，FPGA 具有较大的优势。 目前在FPGA 上，只需通过流水线方式就可实现图像滤波、阈值分割和边缘检测这类流程相对简单的图像处理算法[4]。 但通常的连通域标记算法由于需要更多的存储资源，在使用资源较为有限的FPGA 进行处理时，资源消耗问题显得尤为重要。 因此，基于FPGA 的高效连通域标记算法成为当前的研究热点之一。

连通域标记算法可分为连通域标号标记和连通域特征分析，连通域标号标记是将同一连通域的所有像素分配唯一的标号；连通域特征分析是提取每个连通域的特征信息，如面积、周长、包围盒和重心等[3]。 针对连通域标号标记，Chang 等[5]提出的轮廓标记法，仅对图像进行一次扫描，检测每个连通域轮廓，并标记其内部区域，但轮廓点扫描次数可能不止一次。 Bataineh[1]提出快速的双扫描连通域标记算法，优化了等价标号与临时标号替换规则，使连通域算法具有更高的效率。 Stefania 等[6]提出的双扫描方法，可在像素及帧间进行并行处理，通过缓冲器存储等价标号，实时处理等价标号与临时标号，在一定程度上降低了系统耗时。 张国和等人[4]提出的快速连通域标记算法，利用片上RAM 读写特性，减少了资源的消耗。 Zhao 等人[7]提出的高效连通域标记算法，在扫描时对输入的二进制图像用游程编码进行压缩，同时扫描相邻行，实时输出已结束区域并释放其存储空间。

通常为了清晰地区分各连通域，还需对连通域进行特征分析。 针对连通域特征分析，再结合包围盒特点，Tang 等[8]提出的单通循环编码算法对目标进行了包围盒标记，结合链表和游程特征优化了等价标号处理过程，但处理过程中需要对图像进行单行缓存，加大了系统内存资源的消耗。 闫石等人提出的基于地址-事件的高速连通域标记方式，处理极低冗余的事件信息，降低了算法运行时间[9]，但仅在前景目标较少的二值图像的前提下才具有较高的执行效率。 王凡等人提出的快速连通域标记方法，对图像一次扫描，不产生临时标号[10]，但仅适合于舰船或其他形状较规则的目标。 戴华东等人提出了一种适用于单目标图像实时检测与跟踪算法，简化了等价标号处理过程，缓存单行图像即可完成标记[11]，但仅支持单目标标记或者已知个数的多目标标记，并不适用于一般性的多目标检测。

综上，在连通域标记的算法中，大多需要处理等价标号与临时标号[1，4，6-8]，必然导致额外的运行时间与片上RAM 资源消耗；此外，当标记特殊图案时，等价标号与临时标号过大，使算法时间与资源的消耗成倍增加。 同时大多数算法仅对图像进行标号标记，并未对特征进行分析[1，6-7]。 针对以上问题，再结合包围盒特点，本文提出了一种基于FPGA 的快速连通域标记算法。 该算法利用片上RAM 读写特性，处理游程时就判断游程间连通与否，同时合并优化连通游程信息，不产生等价标号；利用片上RAM 地址信息判断不同连通域，不产生临时标号。整个过程仅对图像扫描一次，即可得到所有连通域排序后的行特征信息(包围盒起始特征信息/结束行特征信息)，最后将行特征信息叠加在待标记图像上就能完成连通域标记。

1 快速连通域标记算法设计

1.1 新的连通域标记算法流程

连通域标记算法是对图像中前景像素进行标记，目的是区分图像中不同连通域。 其连通性一般分为4 连通和8 连通，因8 连通在处理过程中判断更多的像素点，标记更为准确，常用8 连通作为连通域标记检测算子。 结合包围盒特点，本算法最终采用不同颜色包围盒交叉标记各连通域，算法流程图如图1 所示。

图1 快速连通域标记算法流程图

与传统标记算法类似，新的标记算法仍以像素为基本单位按光栅扫描顺序(即由左至右、由上至下)逐行扫描，但在几个关键步骤(如等价游程优化置换、行特征信息提取和包围盒快速显示)与传统算法不同。 扫描过程中以游程为单位记录行列信息。 等价游程优化置换过程:将游程视为运算单元，进行8 邻域判断，若连通则将游程信息合并优化后置换原数据，否则直接将游程信息按地址累加方式存储于片上RAM。 行特征信息提取过程:实时提取已结束连通域的结束行特征信息，当所有区域检测完成(帧结束信号)后提取起始行特征信息。 包围盒快速显示过程:将排序后的行特征信息叠加在待标记图像上显示。

1.2 FPGA 系统总体设计

按图1 所示算法流程，结合FPGA 对信息处理的特点，采用Verilog 硬件描述语言(HDL)对新的快速连通域标记算法进行了逻辑设计，并在基于Xilinx Spartan-6 系列XC6SLX150 芯片为核心的开发板上进行了系统实现。

这一新的FPGA 系统总体分为图像输入、图像存储、连通域检测和包围盒快速显示4 个模块。 图像输入模块:将输入图像进行二值化处理后转为以像素为单位的连续数据流。 得到的数据流分两路输入不同模块:一路输入到连通域检测模块，经过该模块将得到图像中各连通域包围盒行特征信息；一路直接输入到第三代双倍数据率同步动态随机存取存储器(DDR3)中缓存，即DDR3 缓存模块。 图像显示模块:将排序后的行特征信息叠加在缓存于DDR3 中的图像上，并通过视频图形阵列(VGA)显示模块显示标记后图像。 系统总体结构框图如图2 所示。

图2 系统总体结构框图

本文主要介绍快速标记算法，而算法仅对图像进行连通域特征分析，所以下面仅对连通域检测模块和包围盒快速显示模块进行详细介绍。 另外两个模块(即图像输入和DDR3 图像缓存模块)可以参看我们以前发表的相关论文[12]。

1.3 连通域检测模块设计

连通域检测模块主要完成图像扫描、等价游程优化置换和行特征信息提取等任务。 其中图像扫描模块由像素扫描模块和游程信息缓存组成，等价游程优化置换模块由邻域判断模块和RAM 存储模块组成，行特征信息提取模块则主要由行特征信息缓存模块构成。 各模块详细情况介绍如下。

1.3.1 图像扫描

光栅扫描过程中记录游程信息，游程信息中行地址、列起始地址和列结束地址，分别用row、left 和right 表示。 检测到“01”时，说明游程开始，记录行列信息并存储到寄存器R0{row，left}；检测到“10”时，说明游程结束，将记录的列信息与寄存器R0 值合并后存储到寄存器D0{row，left，right}中。 单行游程可能出现的情况如图3 所示。

图3 单行可能出现游程示意图

针对图3，本算法游程信息存储详细过程:扫描到第一个前景像素(第0 行第1 列)时，R0 赋值为{0，1}，当扫描到游程结束(第0 行第4 列)时，D0赋值为{0，1，4}。 为了避免两游程相近时(即上一游程未处理完，下一游程已被检测)，丢失下一游程信息的情况发生，将游程信息D0 数据缓存于先进先出存储器(FIFO)FIFO_RUN 中。 类似地处理后续每个游程。 同时还需注意边界情况，当检测到前景像素且位于第一列时视为游程开始，当检测到前景像素且位于最后一列时视为游程结束，其赋值方式不变。

1.3.2 等价游程优化置换

经图像扫描后得到的第一个游程视为新游程，直接将其信息存储于RAM0 第1 个地址中。 RAM0数据为一个临时包围盒特征信息，数据格式为起始行/结束行地址和起始列/结束列地址，分别up、down、left 和right 表示，其中新游程对应的up 与down 数值均赋值为row；同时将列信息(列起始与结束地址)存储于RAM1 中，数据格式{left，right}。 当第2 个及其之后游程到来时，需要将RAM1 中非零数据读出并与该游程(即当前游程)进行8 连通判断，若连通则将该游程信息与对应地址RAM0 中数据合并优化后置换原数据；否则，将其视为新游程，相关信息按地址累加方式存储于RAM0 中。 RAM1始终存储该游程(实时处理游程)对应临时包围盒中上一行前景像素列信息。 判断连通关系用式(1)，合并优化过程用式(2)至式(5)。

式中:M1_left 和M1_right 为RAM1 中数据，M0_up、M0_down、M0_left 和M0_right 为RAM0 中数据，Mr_row、Mr_left 和Mr_right 为当前游程数据，Mn_up、Mn_down、Mn_left 和Mn_right 为合并优化后数据。

当出现一个游程与上一行多个游程满足连通，即“U”或“W”型图案时，处理过程中需要将最终合并优化后数据置换RAM0 中最小地址数据，RAM1中数据也随之置换；同时在该游程处理完成后将其余地址RAM(RAM0 和RAM1)数据写0。 相邻两行游程可能存在的关系，如图4 所示。

图4 相邻两行可能出现游程示意图

针对图4，本算法处理的详细过程:当第0 行扫描结束后RAM 中数据如表1；处理第1 行游程(第5游程)时，RAM 中数据置换过程如表2。

表1 第1 行处理完存储器数值

表2 处理游程比较置换过程

因为RAM1 存储数据的特殊性，导致RAM1 中数据除处理过程中写入数据外，还需在同行游程确定不同连通域后或下一行游程到来时写入上一游程列信息。 处理完成游程5 后，类似地处理下一游程，若该游程(游程6)与上一游程(游程5)属于同行游程且与上一游程(游程5)区域不连通，则将上一游程列信息{7，13}写入RAM1；否则，重复以上步骤，直至游程为下一行的游程，再将上一游程列信息写入RAM1。 引入RAM1 可提高了特殊情况判断连通性的准确率。 针对图4，在判断游程连通关系时，若采用RAM0(临时包围盒特征信息)中列信息{5，15}，则将错误的判断游程6 与游程5 连通；引入RAM1(上一行前景像素列信息){7，13}，则准确地将游程6 视为新的游程。

1.3.3 行特征信息提取

确定连通域结束后需要提取该连通域结束行特征信息。 当满足式(6)或式(7)表示连通域结束。

连通区域结束后实时提取特征信息就完成了图像连通域检测。 为了后续快速显示包围盒，需要将包围盒特征信息分为起始行特征信息和结束行特征信息。

结束行特征信息提取:将结束区域地址信息存储于FIFO(FIFO_DOWN)，后续提取包围盒结束行特征信息时，提取该FIFO 中数据作为RAM0 地址对应的数据即可，数据格式为{down，left，right}，同时后续处理游程间关系读RAM1 数据时无需读该地址数据。

当处理某一游程时出现多个连通域结束，此时需要考虑各连通域结束的先后顺序。 式(6)判断结束区域优先于式(7)，所以在提取地址信息时优先提取式(6)判断区域；当式(6)、式(7)各自判断出多个连通域结束时，在式(6)优先于式(7)前提下，还需按列数据小的地址信息优先提取。

起始行特征信息提取:根据片上RAM 地址从小到大顺序可得到排序后的起始行特征信息，但由于各区域结束的不确定性，无法实时按该顺序提取已结束的起始行特征信息，需等所有区域检测完成后提取，将RAM0 非零数据按格式{up，left，right}提取，还需同步记录color 数值。 其中color 数值根据地址确定，但color 仅在2～3 间循环，实现两种颜色包围盒交叉标记各连通域。 其中颜色数值0 代表背景像素，1 代表前景像素，2、3 代表两种不同颜色。

1.4 包围盒快速显示模块设计

由于算法用于目标检测系统的前端模块，需要考虑能否快速显示包围盒标记。 本算法提出一种快速显示包围盒标记方法，分为行特征信息排序、VGA显示两个过程。

行特征信息排序:经过连通域检测模块后得到两组数据(起始行特征信息和结束行特征信息)，通过对两组数据按光栅扫描出现的先后顺序读取，将得到所有排序后的行特征信息；同时结合颜色数值color 存储在FIFO(FIFO_ROW)中，数据格式为{color，up/down，left，right}，其中取结束行特征信息时，color 数值赋0。 处理过程中连通域可能出现的特殊情况，如图5 所示。

针对图5，本算法处理行特征信息排序过程，如表3 所示。

表3 包围盒快速标记过程

VGA 显示:将排序后的行特征信息叠加在待标记图像上显示，实现对图像各连通域的包围盒标记。

行标记:当FIFO_ROW 出现{2，0，12，15}时，表示起始行特征信息，有颜色数值，待标记图像第0 行12 列至15 列将显示颜色2；当FIFO_ROW 出现{0，3，5，8}，表示结束行特征信息，无颜色数值，待标记图像第3 行5 列至8 列将显示对应列标记颜色。

列标记:仅用0 和1(非0)缓存上一行标记结果，当检测“01”或“10”时则表示各包围盒对应列出现，此时显示上一行颜色数值；当结束行特征信息到来时，结束对应列标记。 同时需要注意包围盒交叉情况，将交叉标记点取列标记值，同时产生使能信号，这样在下一行标记时能准确按列标记，使包围盒交叉情况也能准确标记。

2 算法运行时间及硬件资源分析

2.1 算法运行时间

基于上述理论分析可知，对于分辨率为N×M的图像，本算法运行时间T0满足式(8)。

式中:t为机器周期，td为提取剩余结束行特征信息时间，tr为提取所有起始行特征信息时间。td＝(l+2)×t，tr＝(n+n0+1)×t。l为处理最后一游程时未结束区域个数，n为总的连通域个数，n0为零数据个数。

根据多次实验表明l与n0值偏小对算法总体时间影响较小，连通域个数n值可能出现较大情况，但一般不会超过列最大值N，故算法最大运行时间Tmax满足式(9)。

考虑到一般图像中最后一行无前景像素，若将所有区域检测完成信号由帧结束信号提前至最后一行开始，此时算法运行时间T′0满足式(10)。

结合实际情况，算法运行时间应大于等于图像扫描时间，故算法最小运行时间Tmin满足式(11)。

基于上述理论分析可知，不同分辨率图像在工作频率100 MHz 的条件下本算法运行时间如表4所示。

表4 工作频率100 MHz 不同分辨率本算法运行时间

2.2 硬件资源消耗

基于上述理论分析可知，本算法需要消耗2 组片上RAM 和3 组FIFO 资源。 对一副N×M(N列M行)图像，各存储器消耗位宽及深度分析如下。

对于N×M图像，通过8 邻域判断连通的情况，理论上连通域个数至多可达N/2×M/2，但实际上几乎不会出现这种情况，而且当出现这种情况时，也没有对其做连通域标记意义。 同时若二值图像已经过滤波或形态学处理，那么连通域个数至多为N/6×M/6。 若采用单个有效区域大小至少为N/100×M/100 个像素点，则连通域个数至多为100/6×100/6≈278。

下面以分辨率为1 920×1 080 pixel 的全高清(FHD)图像为例，对算法进行资源需求分析。 因存储器均通过二进制方式对其进行存储，通过式(12)可求出十进制数X所需位宽B。

连通域检测模块资源消耗:片上RAM0 数据位宽44(4×11)bit；片上RAM1 数据位宽22(2×11)bit。 其深度均需根据最大连通域个数确定。 经过MATLAB 实验分析及多次实验，得出通常情况下连通域个数小于278，FIFO_RUN 仅为防止两游程太近丢失数据，深度Rf设为N/20≈96 即可。 为防止连通域过多，结合二进制位宽特性，本文将最大连通域个数设为512，Rf设为128。 FIFO_DOWN 存储结束连通域地址信息，数据位宽9bit，深度512bit。

包围盒快速显示模块资源消耗:color 数值和FIFO_ROW 存储行特征信息，需数据位宽35(3×11+2)bit，深度1 024(2×512)bit。 本算法连通域检测过程存储器资源需求如表5 所示。

表5 本算法存储器资源需求

从表5 可知，本算法在检测模块消耗片上资源约41.63 kbit，在包围盒快速显示模块消耗片上资源35 kbit，总共消耗片上资源约76.63 kbit。 本算法运算过程仅利用FIFO_RUN 和RAM1 中数据，而RAM0 存储包围盒特征信息。 若特征信息需要连通域面积时，仅需将RAM0 中{up，left}数据更改为连通域中心坐标，{down，right}数据更改为连通域面积信息即可求出各连通域面积。

3 实验结果及分析

为验证本算法准确性，选取了含多种特殊形状的图像进行实验。 并通过ChipScope pro 14.7 和Modelsim 10.1 对算法运行时间进行验证；通过VGA显示对包围盒标记进行验证。

3.1 时间消耗及标记结果

为了验证本算法运行时间准确性，首先通过Modelsim 进行验证算法运行时间。 模拟输入64×64 pixel 图像(最后一行无前景像素)，共3 个连通域(一个普通型、一个“W”型和一个“U”型)，进行了仿真实验，得到连通域检测模块运行时序图，如图6 所示。

图6 连通域检测模块运行时序图

由图6 可知，l＝1，n＝3，n0＝3，t＝10 ns。 (N×M-N)×t＝40 320 ns，td＝(l+2)×t＝30 ns，tr＝(n+n0+1)×t＝70 ns，满足式(10)。 但算法实际运行时间应为Tmin＝40.96 μs。

为了进一步验证本算法运行时间准确性，接下来通过ChipScope pro 抓取信号来验证上板后的准确性，采用分辨率为480×320 pixel 图像(最后一行无前景像素)进行实验，其图像包含52 个字母(含大小写)，得到连通域检测模块运行时序图如图7 所示。

图7 算法运行时序图

由图7 可知，所有区域检测完成信号产生后需77 个周期产生结束信号。l＝1，n＝52，n0＝21，td＝(l+2)×t＝3t，tr＝(n+n0+1)×t＝74t；可以得出算法运行时间满足式(10)，但实际算法运行时间应为Tmin≈2.621 ms。

在确定算法运行时间准确后，还需对标记结果进行验证，对含52 个字母图像进行实验，FPGA 开发板上标记结果，如图8(a)所示，在MATLAB 上进行相同处理，结果如图8(b)所示。 为了针对图片环境和连通域更为复杂的情况，对含15 个不规则图案的图像进行实验，FPGA 开发板上标记结果，如图8(c)所示，在MATLAB 上进行相同处理，结果如图8(d)所示。

对比图8(a)和图8(b)、图8(c)和图8(d)可知，在FPGA 上对图像标记的结果与在MATLAB 上标记的结果完全一致，说明在本算法能准确地对各连通域进行标记。

图8 实验结果图

为验证包围盒交叉时标记的准确性，将对含包围盒交叉情况的图像进行实验，其中行特征信息及排序情况，通过ChipScope pro 抓取相关信号，结果如图9 所示，在MATLAB 上进行相同处理，结果如图10 所示，原图如图11(a)所示，二值化结果图如图11(b)所示，FPGA 开发板上标记结果，如图11(c)所示，在MATLAB 上进行相同处理，结果如图11(d)所示。

图9 FPGA 行特征信息排序结果

图10 MATLAB 行特征信息排序结果

图11 包围盒交叉实验结果图

对比图9 和图10 可知，在FPGA 上对行特征信息提取及排序的结果与在MATLAB 上实现的结果完全一致，说明行特征信息提取及排序模块设计正确；对比图11(c)和图11(d)可知，在FPGA 上对图像标记的结果与在MATLAB 上标记的结果完全一致，验证了在包围盒交叉情况下包围盒快速显示模块设计的准确性。

3.2 实验对比分析

在算法运行时间上，为了与文献[4]相比，本文选择了与文献[4]相同的工作频率(100 MHz)，并选取了相同分辨率(512×512 pixel)的图像进行实验。两种不同算法运行时间如表6 所示。

表6 不同算法运行时间对比

从表6 可以看出，文献[4]运行最小时间大于本算法运行最大时间，且运算时间的最小值与最大值相差较大。 这是因为文献[4]在运算过程中需要处理等价标号与临时标号，带来了额外时间消耗，同时多游程情况下等价标号与临时标号过大，导致算法运行时间成倍增加。

在资源消耗上，为了公平比较各算法资源消耗，假设所有算法均对N×M图像进行连通域标记。 其中Rr表示单行游程上限(Rowruns)，Ar表示游程总数(Allruns)，A′r表示优化后游程总数(A′r≤Ar)，Rw表示游程数据位宽(Runswidth)，Dw表示特征数据位宽(Datawidth)。Rr＝N/2，LR＝「log2Rr」，Ar＝Rr×M，LA＝「log2Ar」，Rw＝Dm+2×Dn，(Dn＝「log2N」，Dm＝「log2M」)，Rf＝「N/20」，其中Dw由算法自身确定。几种不同算法对连通域标记所需片上资源如表7所示。

从表7 可知，相比文献[8，10-11，13]，虽然本算法在提取特征信息时需要缓存片上RAM 地址信息，但在其他存储器方面具有更低的资源消耗。 相比文献[10，13]，本算法没有等价标号与临时标号，降低了算法运行的复杂性。 相比文献[11]仅支持单个目标或已知个数的多个目标检测，本算法在功能上具有更大的优势。 此外，本算法引入RAM1(上一行前景像素列信息)使得在标记特殊图案时有更高的准确率。 当最后一行无前景像素时，各算法时间均为T0＝M×N×t。

表7 不同算法资源消耗对比

为了方便比较不同算法具体的资源消耗，参照文献[8，10-11，13]以三种不同分辨率的图像为例对几种算法进行资源分析比较。 其中在资源消耗分析时，由于部分参数过大，结合实际情况，最终将文献[10]的A′r设为4 096，LA设为14；而将文献[11]的LA设为10，进行分析。 不同算法资源消耗如表8 所示。

表8 不同算法资源消耗对比

由表8 可知，与文献[8，10-11，13]的算法相比，本算法在相同分辨率图像上进行连通域检测标记所需资源最少。 同时算法增加了快速显示包围盒标记，使图像在显示同时完成包围盒标记。

4 结论

本文在传统连通域标号标记算法的基础上，结合包围盒特点，提出了一种连通域特征分析算法——基于FPGA 的快速连通域标记算法。 在检测过程中，以游程为处理单元实时合并连通游程并以包围盒特征信息格式存储到片上RAM，不产生等价标号与临时标号；在标记过程中，将排序后的行特征信息叠加在图像上，可实现包围盒标记随图像显示而显示。 同时，在保证资源不变的情况下，可根据需求更换连通域特征信息(包围盒或面积)。 实验结果表明在连通域检测过程中，相比其他算法，本算法在时间和资源方面均有一定优势；同时提出的包围盒快速显示方法，在包围盒交叉情况下亦能成功显示。 本算法仅存储连通域特征信息，并未对前景像素进行标号存储，在一定程度上降低了算法运行时间及资源消耗，虽然不支持提取连通域周长，但可根据需求对连通域包围盒或面积进行提取，所以在目标实时检测系统中具有一定的实用价值。