基于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为零。
1．2 等价关系合并
    在第一次扫描过程中，在对像素临时标记的同时对等价表进行合并。等价表合并按照等价表的存储顺序以较大值为索引的链表循环查找的方式进行合并，合并后的等价关系存储到新的等价表中。以图3所示的等价表合并为例来说明等价表合并过程。图3中，第一行为等价关系存储的顺序；第二、三行分别为等价关系的索引值和等价值。其中，a>b>0，a>d>0，b>c>0。等表合并步骤如下：
    (1)首先以a为索引在新的等价表中查找a所对应等价值，查得a没有对应值，因此将较大值a为索引，b为等价值存入新的等价表。同理，b，c也存入了新的等价表。
    (2)合并等价关系a，d时：
    ①若b=d，则不存入等价表，合并下一个等价关系。
    ②若b<d，则以d为索引在当前新等价表中查找d对应等价值，查得d没有对应关系，从而将d为索引，b为等价值存入新等价表。
    ③若b>d，则将d替代a的等价值b，然后以b为索引查找得到其对应值c，比较c，d大小。若c<d，则以d为索引在当前新等价表中查找，查得d没有对应关系，从而将d为索引，c为等价值存入新等价表。若c>d，则将d替代b的等价值c，然后以c为索引查找，查得c没有对应关系，从而将c为索引，d为等价值存入新等价表。若c=d，则不存入等价表，合并下一个等价关系。
1．3 链表归并
    等价表合并完成后，从1到临时标记的最大值按照从小到大的顺序依次进行归并。以当前合并值为索引对合并后的新等价表进行查找，如果没有对应等价值，则将其本身作为其等价值存入新的等价链表；如果查得其对应等价值为M，则继续以M为索引对当前新的等价链表查找，查得M对应值为P；若P为不零，则将P作为当前合并值的等价值存入新的等价链表；否则，就将M作为当前合并值的等价值存入新的等价链表。
1．4 顺序合并
    图像进行第二次扫描时，利用像素的临时标记值为索引在等价链表中查找其对应值，经过归并后输出以自然数顺序的标记的图像。第二次扫描过程中，如果第一个临时标记X1对应值Q1不为零时，以1替代X1；如果第二个临时标记X2对应值Q2不为零时，若Q2不等于Q1，则以2替代X2，否则以1替代X2。依此类推，当第n个临时标记Xn对应值Qn不为零时，若Qn=Qm，则以m替代Xn；若Qn≠Qm(0<m<n)，则以n替代Xn。
1．5 算法特点分析
    本文算法主要是针对FPGA流水线和并行处理的特点而提出的。利用FPGA实现时的运算复杂度优于文献。采用FPGA实现该算法需要总时钟周期小于2×N×M，N为图像行数，M为列数。
    算法利用FPGA的特点主要体现在：图像标记过程中同时对等价关系进行合并，在FPGA实现时图像标记和等价关系合并可以并行执行，减少了整个过程的处理时间；临时标记和顺序合并采用了流水线方式进行，减少了处理等待时间，能较快输出图像；链表归并和顺序合并单元采用高于临时标记和等价关系合并单元时钟频率，既体现了并行处理特性又提高了处理速度。

2 硬件实现方案
    该设计采用单片FPGA来实现上述连通域快速标记算法，标记处理单元均利用FPGA片内资源，不需要其他外部单元，缩小了硬件体积，电路结构简单，节约了硬件资源、易于实现。该算法实现过程采用VHDL编程的方式在FPGA上实现。硬件实现框图如图4所示。

    标记单元采用流水线的方式对二值图像逐个像素进行标记。采用FPGA内部的FIFO存储1行已标记像素的标记值来实现2×2的扫描窗口。标记单元结构如图5所示。图像经标记单元处理后，将像素的标记值Label_value存储到图像存储单元中，等价关系Eq_valuel，Eq_value2存储到等价表中。图像存储、等价表合并和链表归并三个处理单元都是采用对双口RAM的读／写操作来实现。处理单元流程图如图6所示。图像存储单元采用两个双口RAM乒乓操作来实现，分别为RAMa和RAMb，每个双口RAM单独存储一帧图像像素临时标记。在图像的标记过程中，像素的临时标记值实时的存储到RAMa或RAMb中。等价表存储采用一个异步的双口RAMc作为缓存，将标记输出的等价关系Eq_valuel，Eq_value2中较大值作为高位，较小值作为低位合并后按顺序存储到RAMc中。存储的同时，从另一个端口读取RAMc中存储的等价关系，进行等价表合并。等价表合并过程中，将等价关系中较大值作为地址，较小值作为数据存储到异步双口RAMd中。链表归并采用两个双口RAM进行乒乓操作，分别为RAMe和RAMf。每个RAM存储1帧图像标记后的归并链表值。RAMe和RAMf存储的图像链表分别与RAMa和RAMb存储的像素标记相对应。顺序合并主要采用寄存器和比较器来实现。利用寄存器存储经等价链表处理后图像非零像素的不同的标记，然后通过比较器进行判断处理，最后以自然数顺序的标记替代像素的标记。

3 FPGA实验结果
    为了能够仿真该算法的硬件可实现性和正确性，利用Matlab 7．1和ModelSim 6．5a进行混合仿真。通过利用Simulink中Link for ModelSim模块建立Matlab和ModelSim混合仿真的VHDL协同仿真模型，如图7所示。

    通过Matlab读入1幅128×128的二值图像，经VHDL Cosimulation处理后，存到Matlab的工作窗口。然后，通过Matlab把图像数据还原成图像矩阵显示出来，仿真结果如图8所示。采用XIUNX的ML506开发板对本文的算法进行了验证，在33 MHz工作时钟下，单片FPGA能完成1 000 f／s的128×128的二值图像标记。实验结果表明本文提出的适于FPGA实现的二值图像连通域快速标记算法能满足实时性要求。

4 结语
    图像连通域标记是目标跟踪与识别图像处理系统中的重要环节。由于图像的数据运算量大，利用软件来实现难以满足系统的实时性。本文介绍的适于FPGA实现的连通域快速标记算法能够对二值图像以自然数顺序对图像连通区域进行快速标记。软件仿真和硬件实现结果表明，本文介绍的连通域快速标记算法能够对存在复杂连通关系的二值图像进行正确标记。该设计只采用单片FPGA实现，电路结构简单，大大节约了硬件资源，体积小，易于实现。对于较大的图像的连通域快速标记，只需在FPGA外接存储器就能够实现。