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

1 引言  
　　
在图像自动目标识别和跟踪过程中，首先对图像目标进行阈值分割提取，得到的二值图像通常包含多个连通区域，系统利用图像目标的形状特性对可疑高威胁的飞行目标进行自动识别。因此，需要对各连通区域块进行分别检测判断，本文采用改进的适合FPGA实现的快速标记算法对各连通域进行检测提取。  
　　
实现二值图像连通体检测通常采用的方法有下几种：区域生长法：首先对图像进行逐行(列)扫描，每遇到一个未标记的“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 逆时钟方向初始标记的工作窗