本帖最后由 阿常 于 2021-8-11 07:26 编辑

        　　连通域标记算法是图像处理、计算机视觉和模式识别领域的一种基本算法。它可以对图像中的不同目标进行标记，然后对目标进行提取和分离，确定目标的特征和参数，从而对目标进行识别和跟踪。连通域标记算法广泛应用于军事目标跟踪、工业产品监控、交通路口监控等图像处理系统中。现有的连通元件标注算法分为两类：基于像素的连通元件标注和基于笔划的连通元件标注。基于行程的连通域标记算法难以硬件实现。它一般在PC机上通过软件编程实现，处理速度慢，占用资源多。基于像素的连通域标记在软件中实现，速度慢，适合硬件实现。根据FPGA的特点，提出了一种适合FPGA实现的快速连通域标记方法。在33mhz的工作时钟下，单片机FPGA可以完成1000f/s×128的128次，处理速度可以满足实时系统的要求。
　　
　　1标记算法
　　
　　1.1临时标记
　　
　　连接的域标记从左到右和从上到下扫描二值图像两次。在第一扫描过程中，为具有一个像素的点标记临时标记，并且不标记具有零的点。标记后，得到一个等价表，并将该等价表组合成一个按较大标记值索引的链表；在第二次扫描中，将临时标记逐像素替换，最终获得按目标外观自然数顺序排列的标记。
　　
　　（1） 如果当前像素P不为零：如果L和u中只有一个不为零，则将该标志复制到pl；如果l和u不为零且相同，则将此标志复制到pl；如果l和u都为零，则为pl分配一个新的标志ln+1；如果l和u不是零而是不同的，则将较小的复制到PL，并将l和u存储在等价表中。如中所示。
　　
　　（2） 如果当前像素P为零，则PL为零。
　　
　　1.2等价关系合并
　　
　　在第一次扫描期间，将合并等效表，同时临时标记像素。等价表按照等价表的存储顺序，以较大值为索引，通过链表循环搜索的方式进行合并，合并后的等价关系存储在新的等价表中。
　　
　　（1） 首先，以a为索引，在新的等价表中找到a对应的等价值。发现a没有相应的值。因此，较大的值a是索引，B是等值，存储在新的等价表中。同样，B和C也存储在新的等价表中。
　　
　　（2） 合并等价关系a、D时：
　　
　　① 如果B=D，则不保存等价表，并合并下一个等价关系。
　　
　　② 如果B③ 如果b>D，用D代替a的相等值b，然后用b作为索引找到其对应值C，并比较C和D的大小。如果使用了CD，用D替换B的相等值C，然后用C作为索引进行搜索。发现C没有对应关系，所以C是索引，D是等值，存储在新的等价表中。如果C=D，则不保存等价表，并合并下一个等价关系。
　　
　　1.3列表合并
　　
　　合并等价表后，按从小到大的顺序从1合并到临时标记的最大值。使用当前合并值作为索引来搜索合并的新等效表。如果没有对应的等价值，则将其作为等价值存储在新的等价链表中；如果发现对应的等价值为m，则继续搜索当前新的以m为索引的等价链表，发现m的对应值为p；如果P不为零，则P作为当前合并值的等值存储在新的等价链表中；否则，M将作为当前合并值的等值存储在新的等效链表中。


　　1.4顺序合并

　　第二次扫描图像时，像素的临时标记值用作索引，以在等效链表中查找其对应值。合并后，按自然数顺序输出标记图像。在第二次扫描期间，如果第一临时标记X1的对应值Q1不为零，则将X1替换为1；如果第二个临时标记X2的对应值Q2不为零，如果Q2不等于Q1，则将X2替换为2，否则将X2替换为1。通过类推，当第n个临时标记xn的对应值QN不为零时，如果QN=QM，则m将替换xn；如果QN≠ QM（0

　　1.5算法特性分析

　　该算法主要是根据FPGA流水线和并行处理的特点提出的。FPGA实现的计算复杂度优于文献中的计算复杂度。使用FPGA实现该算法需要总时钟周期小于2×N×M。N是图像行数，M是列数。

　　该算法充分利用了FPGA的特点，主要体现在：在图像标记过程中同时融合了等价关系。在FPGA中实现时，图像标记和等价关系合并可以并行执行，减少了整个过程的处理时间；通过流水线进行临时标记和序列合并，减少了处理等待时间，可以快速输出图像；链表合并和顺序合并单元的时钟频率高于临时标记和等价关系合并单元的时钟频率，这不仅反映了并行处理的特点，而且提高了处理速度。

　　2硬件实现方案

　　本设计采用单片FPGA实现上述连通域快速标记算法。标签处理单元使用FPGA片上资源，不需要其他外部单元，减少了硬件体积，电路结构简单，节省了硬件资源，易于实现。该算法通过VHDL编程在FPGA上实现。

　　标记单元以流水线方式逐像素标记二值图像。FPGA内部FIFO用于存储1行标记像素的标签值，实现2×2扫描窗口。在由标记单元处理图像之后，像素的标记值被标记为u值被存储在图像存储单元中，并且等价关系Eq u值l、Eq u值2被存储在等价表中。图像存储、等价列表合并和链表合并都是通过读/写双端口RAM来实现的。处理单元的流程图如图6所示。图像存储单元通过两个双端口RAM（即Rama和RAMB）的乒乓操作实现。每个双端口RAM分别存储一帧图像像素临时标记。在图像标记过程中，像素的临时标记值实时存储在Rama或RAMB中。等价表存储器使用异步双端口Ramc作为高速缓存，并输出标记的等价关系EQ valuel，EQ 2中较大的值用作高值，较小的值用作低值。合并后，按顺序存储在Ramc中。存储时，从另一个端口读取Ramc中存储的等价关系，并合并等价表。在等价表合并过程中，等价关系中较大的值作为地址，较小的值作为数据存储在异步双端口ramd中。链表合并使用两个双端口RAM进行乒乓操作，即RAME和Ramf。每个RAM在1帧图像标记后存储合并的链表值。存储在Rama和Ramf中的图像链表分别对应于存储在Rama和RAMB中的像素标记。顺序合并主要由寄存器和比较器实现。寄存器用于存储经过等效链表处理的图像非零像素的不同标记，然后通过比较器进行判断处理。最后，按照自然数的顺序将像素的标记替换为标记。

　　3 FPGA实验结果

　　为了仿真算法的硬件可实现性和正确性，采用Matlab7.1和Modelsim 6.5A进行混合仿真。利用Simulink中Modelsim模块的链接，建立了MATLAB与Modelsim混合仿真的VHDL协同仿真模型。

　　通过MATLAB读取1128×128的二进制图像通过VHDL仿真处理后存储在MATLAB的工作窗口中。然后，利用MATLAB将图像数据恢复为图像矩阵，并给出了仿真结果。利用Xinx公司的ml506开发板对本文算法进行了验证。在工作钟下