基于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为零。

　　1.2 等价关系合并

　　在第一次扫描过程中，在对像素临时标记的同时对等价表进行合并。等价表合并按照等价表的存储顺序以较大值为索引的链表循环查找的方式进行合并，合并后的等价关系存储到新的等价表中。以图3所示的等价表合并为例来说明等价表合并过程。图3中，第一行为等价关系存储的顺序;第二、三行分别为等价关系的索引值和等价值。其中，a>b>0，a>d>0，b>c>0。等表合并步骤如下：

　　(1)首先以a为索引在新的等价表中查找a所对应等价值，查得a没有对应值，因此将较大值a为索引，b为等价值存入新的等价表。同理，b，c也存入了新的等价表。