基于FPGA的二值图像连通域快速标记
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，则不存入等价表，合并下一个等价关系。
②若bd，则以d为索引在当前新等价表中查找d对应等价值，查得d没有对应关系，从而将d为索引，b为等价值存入新等价表。
③若b>d，则将d替代a的等价值b，然后以b为索引查找得到其对应值c，比较c，d大小。若cd，则以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(0mn)，则以n替代Xn。
1．5 算法特点分析
本文算法主要是针对FPGA流水线和并行处理的特点而提出的。利用FPGA实现时的运算复杂度优于文献。采用FPGA实现该算法需要总时钟周期小于2×N×M，N为图像行数，M为列数。
算法利用FPGA的特点主要体现在：图像标记过程中同时对等价关系进行合并，在FPGA实现时图像标记和等价关系合并可以并行执行，减少了整个过程的处理时间；临时标记和顺序合并采用了流水线方式进行，减少了处理等待时间，能较快输出图像；链表归并和顺序合并单元采用高于临时标记和等价关系合并单元时钟频率，既体现了并行处理特性又提高了处理速度。
2 硬件实现方案
该设计采用单片FPGA来实现上述连通域快速标记算法，标记处理单元均利用FPGA片内资源，不需要其他外部单元，缩小了硬件体积，电路结构简单，节约了硬件资源、易于实现。该算法实现过程采用VHDL编程的方式在FPGA上实现。硬件实现框图如图4所示。本文引用地址：http://www.amcfsurvey.com/article/191201.htm
标记单元采用流水线的方式对二值图像逐个像素进行标记。采用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存储的像素标记相对应。顺序合并主要采用寄存器和比较器来实现。利用寄存器存储经等价链表处理后图像非零像素的不同的标记，然后通过比较器进行判断处理，最后以自然数顺序的标记替代像素的标记。
评论