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

图像初始标记类型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）　　

追踪置换方法：步骤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的内部分区