基于FPGA的二值图像连通域快速标记

摘要：针对连通域标记算法运算量大、速度慢、硬件实现困难的缺点，提出一种适于现场可编程逻辑门阵列(FPGA)实现的二值图像连通域快速标记的算法，并用VHDL硬件开发语言在XILINX公司的FPGA上实现。实验结果表明了该算法能对二值图像复杂的连通关系正确标记，易于硬件实现，大大节约了硬件资源，电路结构简单，满足实时性要求。
关键词：FPGA；二值图像；连通域；快速标记

连通域标记算法是图像处理、计算机视觉和模式识别等领域的基本算法，它可以对图像中不同目标标上不同的标记，进而提取、分离目标，确定目标的特征和参数，从而对目标进行识别和跟踪。连通域标记算法广泛应用于军事目标跟踪、工业产品监控、交通路口监控等场合图像处理系统中。目前的连通标记算法分为两大类，一是基于像素的连通成分标记，另一种就是基于行程的连通成分标记算法。基于行程的连通域标记算法难以采用硬件实现，一般都采用软件编程的方式在PC机上实现，处理速度较慢，占用资源多。基于像素的连通域标记采用软件实现速度较慢，适于硬件实现。针对FPGA的特点，提出了一种适于FPGA实现的连通域快速标记的方法。在33 MHz工作时钟下，单片FPGA能够完成1 000 f／s的128×128的二值图像标记，处理速度能够满足实时系统要求。

1 标记算法
1．1 临时标记
连通域标记对二值图像采取从左到右，从上到下的方式进行两次扫描。第一次扫描过程中，对像素为一的点标记一个临时标记，为零的点不标记，标记完后得到一个等价表，合并等价表形成一个以较大标记值为索引的链表；第二次扫描时，对临时标记的逐个像素进行替代，最后得到以目标出现顺序的自然数顺顺序的标记。二值图像整个标记处理过程如图1所示。

采用2×2的窗口进行逐行扫描的方式对二值图像的逐个像素进行临时标记，扫描窗口如图2所示。图2中：P为当前像素；U为当前像素上一行像素对应的标记；L为其左边像素标记；P的临时标记记为PL；当前标记最大值记为LN。临时标记方法如下：
(1)如果当前像素P不为零：如果L和U只有一个不为零，则复制此标记给PL；如果L和U均不为零且相同则复制此标记给PL；如果L和U均为零，则分配一个新的标记LN+1给PL；如果L和U均不为零但不相同，则复制其中较小一个给PL，并将L和U，存入等价表中。如图3所示。
(2)如果当前像素P为零则PL为零。