基于FPGA的二值图像连通域标记快速算法实现

摘  要：针对高速图像目标实时识别和跟踪任务，需要利用系统中有限的硬件资源实现高速、准确的二值图像连通域标记，提出了一种适合FPGA实现的二值图像连通域标记快速算法。算法以快捷、有效的方式识别、并记录区域间复杂的连通关系。与传统的二值图像标记算法相比，该算法具有运算简单性、规则性和可扩展性的特点。利用FPGA实现该算法时，能够准确有效的识别出图像中复杂的连通关系，产生正确的标记结果。在100MHz工作时钟下，处理384×288像素的红外图像能够达到400帧／s以上的标记速度，足够满足实时目标识别系统的要求。
关键词：二值图像；连通域标记；并行处理；FPGA

Realization of a fast connected components labeling algorithm for binary image based on FPGA
He Ming   Wang Xinsai 
(Infrared & radio-frequency technology Center,
Air Defense Forces Command Academy, Zhengzhou, 450052, P.R. China)
Abstract: Based on high-speed image target recognition and tracking tasks, need to make use of limited hardware resources required to achieve high-speed system, accurate binary image component labeling. Proposed a suitable hardware algorithm to achieve rapid binary image component labeling. Algorithm for fast, effective way to identify and record the complex inter-regional connectivity. With the traditional binary image marker algorithm, the algorithm is a simple, rules and scalability characteristics.The simulation results show that the algorithm can accurately identify effective connectivity complex images, produced the correct labeling. The algorithm in hardware form, in the 100MHz clock work, 384 × 288-pixel infrared image processing to achieve more than 400 pictures of the markings s speed enough to meet the demands of real-time object recognition system.
Key words: binary image ,connected components labeling, parallel process,FPGA;

1 引言

　　在图像自动目标识别和跟踪过程中，首先对图像目标进行阈值分割提取，得到的二值图像通常包含多个连通区域，系统利用图像目标的形状特性对可疑高威胁的飞行目标进行自动识别。因此，需要对各连通区域块进行分别检测判断，本文采用改进的适合FPGA实现的快速标记算法对各连通域进行检测提取。

　　实现二值图像连通体检测通常采用的方法有下几种[1] [2] [3]：区域生长法：首先对图像进行逐行(列)扫描，每遇到一个未标记的“1”像素点，就分配其一个未使用过的标号，然后对其领域进行检测，如有未标记过的“1”像素，则赋予相同的标号。反复进行这一操作．直到不存在应该传播标号的“1”像素。然后继续图像行(列)扫描，如检测判未标记的“1”像素则赋予其新的标号，并进行与以上相同的处理。整个图像扫描结束，算法也就终止。这种方法可准确地检测出各种类型的连通体．但处理时间也较长．因为要逐一检测每一“1”像素的邻域，且出现“1”像素的重复扫描。跟踪算法：二值图像中每个取值为“1”的像素 被标记一个与其坐标相关的标号，如由n，m串构成的数。热后，扫描标记后的图像，并将每十像素的标号改为其邻域内的最小标号。反复执行这个过程，直到不需要作标记更改为止。用这种方法处理小而凸的目标时，收敛速度较慢。

　　本文以适合FPGA实现为目的，提出一种具有计算规则性的快速二值图像连通域标记算法。与传统的二值图像标记算法相比，该算法具有运算简单性、规则性和可扩展性的特点，适合以FPGA实现。选用在100MHz工作时钟下，处理384×288像素的红外图像能够达到400帧／秒以上的标记速度，足够满足实时目标识别系统的要求。处理速度可以满足大部分实时目标识别系统的要求。该算法同样可以软件编程方式应用于嵌入式DSP系统中。

2 算法描述

　　首先，在进行标记算法以前，利用硬件开辟独立的图像标记缓存和连通关系数组，接着在视频流的采集传输过程中，以流水线的方式按照视频传输顺序对图像进行逐行像素扫描，然后对每个像素的邻域分别按照逆时针方向和水平方向进行连通性检测和等价标记关系合并，检测出的结果对标记等价数组和标记缓存进行更新，在一帧图像采集传输结束后，得到图像的初步标记结果以及初步标记之间的连通关系，最后，根据标号对连通关系数组从小到大的传递过程进行标号的归并，利用归并后的连通关系数组对图像标记缓存中的标号进行替换，替换后的图像为最终标记结果，并且连通域按照扫描顺序被赋予唯一的连续自然数。

　
图 1 标记算法流程

　　本文快速二值图像连通域标记算法分为三个环节：

　　1.图像初步标记：为每个像素赋予临时标记，并且将临时标记的等价关系记录在等价表中

　　2.整理等价表：这一环节分为两个步骤：

　　　　（1）将具有等价关系的临时标记全部等价为其中的最小值；
　　　　（2）对连通区域以自然数顺序重新编号，得到临时标记与最终标记之间的等价关系。

　　3.图像代换：对图像进行逐像素代换，将临时标记代换为最终标记．经过3个环节处理后，算法输出标记后的图像，图像中连通域按照由上到下，由左至右出现的顺序被标以连续的自然数。

2.1 图像初始标记

　　标记算法符号约定：算法在逆时钟方向检测连通域时用w1，w2表示连续两行的图像数据，在紧接着的顺时钟方向连通域检测时用k0，k表示连续两行经过逆时钟方向标记后的图像数据。 其在工作窗口的位置在图2、3中分别说明；对初始逆时针方向临时标记用Z表示。Z初始标记值为1。

　　二值图像连通域标记算法采用8连通判断准则，通过缩小标记范围剔除了图像的边界效应。为了简化标记处理过程，使标记处理在硬件对一帧图像传输操作时间内结束，标记处理利用中间数据缓存分为连续的两种类型，其中类型1用于直接图像序列传输，硬件发起图像序列传输时，类型1采用逆时钟顺序连通域检测，对2×3工作窗口中的二值像素进行初始标记。类型2对经过类型1初始标记过的图像数据再进行水平方向的连通域检测和归并，然后把标记结果存入图像存储区。

图像初始标记类型1：

　　步骤1读取像素w1（2）、w1（1）、w1（0）、w0（2）、w0（1），以及相应的二值像素值。

　　步骤2读取像素w0（1），按照逆时针方向依次与w1（0）、w1（1）、w1（2）、w0（2）比较，若w0（1）= w1（0），则k0（1）=k（2）；若w0（1）= w1（1），则k0（1）=k（1）；若w0（1）= w1（2），则k0（1）=k（0）；若w0（1）= w0（2），则k0（1）=k0（0）；否则（即w0（1）≠（w1（2）、w1（1）、w1（0）、w0（2）），k0（1）= Z；Z ++。

　　步骤3写入等价关系表，以Z为地址将Z写入等价关系数组。

　
图 2 逆时钟方向初始标记的工作窗

图像初始标记类型2：

　　步骤1判断经过逆时针方向标记后，如果w0（1）=  w0（2）=  1，而标记灰度k0（1）≠ k0（0），则进行下一步骤。

　　步骤2 假设k0（1）> k0（0），判断lab（k0（1））=k0（1）或者lab（k0（1））=k0（0），则lab（k0（1））=k0（0），否则对标记数组进行追踪置换。跳转至步骤3。

　　步骤3 假设k0（1）< k0（0），判断lab（k0（0））=k0（0）或者lab（k0（0））=k0（1），则lab（k0（0））=k0（1），否则对标记数组进行追踪置换。

　　追踪置换方法：步骤2的追踪置换令t= lab（k0（0））；若lab（t）≠ t，则令t= lab（t），重复执行，直lab（t）=t；步骤3的追踪置换令t1= lab（k0（1）），对lab（k0（1））同样执行上述追踪过程。

　
图 3 水平方向初始标记的工作窗

2.2 等价表整理与图像代换

　　首先，从等价表地址1开始扫描等价表，依次检查其中各个临时标记是否存在等价关系，若存在，则以标记值作为等价表地址的数据更新等价表。由于整理过程从等价表地址1开始，因此对整个等价表的扫描可以一遍结束。

　　图像代换环节对临时标记图像中的每个像素进行代换，生成最终的标记后图像。具体做法是：设图像中坐标为（n，m）的像素的临时标记值为S，则将lab（S）写入图像中（n，m）位置。代换后得到的图像，其中的
　　连通区域按照由上到下，由左至右出现的顺序被标以惟一的自然数。

2.3 算法特点分析

算法设计具有以下特点：

　　a．本文算法针对空中目标的识别和跟踪进行标记，可以剔除对空中目标识别没有影响的图像的边界，图像中其他像素的标记工作均利用2.1中所述算法完成，因此运算具有规则性和同地址性，利用硬件实现时只需要定义两个算法框架函数循环使用，节约了算法存储器资源。

　　b．图像初步标记过程中，在记录标记等价信息的同时对等价表进行初步整理，这样安排，一方面可以保证区域之间存在复杂连通关系时，等价表能够保存已经检测到的全部等价关系；另一方面，在以硬件电路实现标记算法时，图像初步标记和等价表初步整理的过程可以并行执行，等价表的初步整理，能够简化随后的等价表整理操作，相当于压缩了标记执行的全过程。

　　c．在本算法中，采取两方面措施减少临时标记数量：其一，反复利用8邻域范围内生成的所有标记信息，在逆时针顺序8邻域范围标记后借助图像传输的顺序进行水平方向的等价标记归并，降低了需要赋予新标记值的概率；其二，在等价表整理时，归并等价标记时按照等价表地址从小到大的的顺序进行比较替换，使等价标记取较小值并且不会遗漏等价标记。其三，结合视频数据流传输方式，采用乒乓存储结构进行流水线处理，同时进行图像标记和图像标记替换。使图像标记达到实时处理的效果。

3 算法的FPGA实现

　　FPGA(Field Programmable Gate Array)是一种大规模的可编程逻辑器件，可以用于各种数字逻辑系统，特别是实时处理方面，具有独特的优势。在本算法的实时实现过程中，采用Altera公司的性价比高的Cyclone II EP2C8 FPGA[4]，该器件内部有8256个LE，，18个DSP模块，165888bits存储单元。这些存储单元可以配置为大小、位数不同的存储器，它可以减少外部存储器的使用，缩小硬件的体积，便于电路的小型化。

　
图4 快速标记算法FPGA实现的硬件结构

　　图4所示快速标记算法FPGA实现的硬件结构，主要由二值视频流延迟FIFO串并转换、逆时针标记单元、归并数据传输接口、水平方向标记归并单元、标记等价关系表、标记等价关系整理单元、图像标记代换等单元构成。

　　FPGA内部视频流采集单元，根据分割阈值对采集来的灰度数据进行二值化，输出二值视频流；通过延迟FIFO的串并转换，将串行的二值视频数据流转换成两行并行的数据；逆时针方向标记单元利用移位寄存器对接受来的并行数据流组成图2所示窗口，在窗口内对数据进行逆时针的连通性检测，生成初始的等价关系表并且对像素数据进行临时标记；水平方向标记归并单元紧接在逆时针方向标记后，对初始标记后的像素数据通过移位寄存器组成如图3所示的数据窗，对数据窗中的数据在水平方向进行标记等价性判断，归并属于同一区域的标记值，并且追踪置换标记等价关系表，把在此以前的等价标记值全部统一成最小的标记值，最后把归并后的并行标记视频流存入后续双端口RAM组成的存储器组中；外部双端口RAM在下一行视频数据流处理时把标记好的上一行像素数据存入到外部双端口RAM中。

　　一帧图像数据标记完毕后，在视频数据的间隙对等价关系表数组进行整理归并，等到下一帧视频数据传输时，从外部双端口RAM中取出上一帧数据进行标记图像代换完成最终的图像标记。

　　标记缓存采用乒乓结构通过FPGA中的双端口RAM构成，标记两行图像数据的同时外部双端口RAM接口对已标记的一行图像数据进行存储。图5所示标记缓存结构，乒乓结构标记缓存模块一共用了3个384*10bit的双端口RAM，每个双端口RAM对应一行图像标记数据，依靠水平方向归并单元和外部DPRAM接口交互进行数据存储，当水平方向归并单元同时存储其中两个双端口RAM时，外部DPRAM接口对剩余的第三个双端口RAM进行存数操作，构成标记缓存乒乓结构存储操作。外部存储接口用像素时钟的4倍频对缓存中的数据进行搬移，确保在其余两个双端口RAM标记完毕后外部数据也搬移完毕。实验证明在一行标记数据传输时间里可以完成3行标记数据搬移。

　
图5 标记缓存结构

　　为了满足标记的实时流水线处理，外围双端口RAM也采用乒乓结构。在对一帧图像标记数据存储的同时取出数据进行标记图像代换，并且在取数的过程中完成对标记结果图像的形状的识别，外围双端口RAM的内部构造如图6所示，把外围双端口RAM设成图像帧A、B两个区，利用两个数据地址端口同时对A、B两个区进行操作。因此标记算法整体延时一帧视频数据传输时间，具有很强的实时性。

　
图6 外围双端口RAM的内部分区

4 实验结果与分析

　　图7、8、9、10给出对4幅384×288二值红外图像的标记结果，由于本文设计针对天空中飞行目标，因此剔除图像边缘（对于图像边缘的背景目标不标记，致为0值）；统一了标记算法规则，减小了边缘背景对目标识别的影响。

　　图7、8、9、10所示均为在多云背景的天空中含有飞机编队，对于形状各异的云层具有复杂的复连通关系，产生复杂的等价表操作，最终被正确地赋予相同的标记。仿真结果相关数据示于表1。其中，FPGA工作时钟为100 MHz；n为连通区域个数；N（MAX）为最大临时标记；T1为TI公司的6416DSP通过传统的收敛标记算法执行时间；T2为TI公司的6416DSP通过本文设计的快速标记算法执行时间；T3为FPGA通过本文设计的快速标记算法执行时间。

　　仿真结果证明，传统的收敛标记算法以软件方式运行于TI公司DSP6416系统中时，算法处理速度不确定，取决于图像中连通域的形状和数量；本文中描述的二值分割图像标记快速算法以软件方式运行于TI公司DSP6416系统中时，算法处理384×288像素图像可以达到50帧的处理速度；但是，以FPGA实现该算法时，在100MHz工作时钟下，能够达到400帧／秒的处理速度。
表1 图像标记仿真结果对比
　

　
图7 含有4架飞机目标的二值红外图像和标记后的图像

　
图8 含有2架飞机目标的二值红外图像和标记后的图像

　
图9 含有4架飞机目标的二值红外图像和标记后的图像

　
图10 含有2架飞机目标的二值红外图像和标记后的图像

参考文献
[1]张树生.一种基于线的标号传播二值图像连通体快速检测方法[J].计算机研究与发展,1994,31(10):51-54
[2]Ranganathan N,Mehrotra R.Subramanmian S.A high speed systolic architecture for labeling connected components in an image[J].IEEE Transaction on Systems.Man.and Cybernetics，1995，25(3):415-423
[3]Nicol C J,A systolic approach for reahime connected component labeling[J].CVGIP,Image Understanding，1995，61(1):17-31
[4]Altera.cycloneII_handbook[R].published by Altera,2005

作者：
贺明：男，1981，江苏丹阳，防空兵指挥学院在读研究生，研究的方向为图像处理、红外成像技术、FPGA和DSP图象处理系统设计等。
王新赛：男，1963，博士，硕士生导师，防空兵指挥学院红外与射频技术研究中心主任、教授，研究的方向为图像处理、人工智能。 
李坚：男，1982，湖北荆门，防空兵指挥学院在读研究生，研究的方向为图像处理、红外成像技术等。
联系地址：郑州市建设东路防空兵指挥学院红外与射频技术研究中心          邮编：450052  
联系电话：0371-63534669    13838119647（M）