面向多目标透镜的连通域标记检测算法

谢智烜，姚红兵，范 宁，陈 枫

(1.江苏大学 机械工程学院，江苏 镇江 212000；2.河海大学 理学院，江苏 南京 210098)

机器视觉[1-2]是一门研究如何利用计算机来模拟人类视觉功能并识别图像中有价值信息的学科，主要由3个系统组成[3]：照明系统、图像处理系统和机械控制系统。图像处理系统是机器视觉中非常重要的一个部分，它接收来自照明系统的图像，并对其分析出所需要的有价值信息，例如目标的坐标、种类等，并将这些信息传输给机械控制系统。

连通域标记是图像处理系统中常用的一个方法，该方法可以从图像中提取目标区域，并统计目标区域的特征参数，如面积和外接矩形等。目前常用的连通域标记算法主要分为两类[4-5]：基于游程的连通域标记算法和基于像素的连通域标记算法。其中基于行程的连通域标记算法[6]先对游程进行编码，然后判断游程与游程之间的是否连通来标定连通域；基于像素的连通域标记算法[7]直接通过判断像素与像素之间是否相连来标定连通域。目前针对单目标[8]、多目标[9-10]以及动态目标追踪[11-12]等方面已有较多研究：王凯[13]等人通过对图像面积分块来达到快速区分前后景的目的。赵晓[14]等人提出一种基于段的连通域标记处理算法，用于检测纸病。姑丽祖热·吐尔逊和尤努斯·艾沙[15]等使用跑长码的连通区域算法，通过结合重叠度计算方法完成了对维吾尔族文字的切分。

上述方法中的目标物与目标物大多是完全分离开的，可是在实际中则会出现两个甚至多个目标物体紧挨在一起且连通域相连的情况。如图1所示，图1(a)为透镜在侧面光源照射下产生的图像，图1(b)是经过预处理后的二值图像。由图可知，标号为2和3的目标透镜是紧挨在一起的。为了解决这一问题，本文在图像边框处做一个特殊的标记值，设计了一种针对多目标透镜的连通域检测算法。

1 算法原理

本算法以被白色区域包围的黑色区域为提取目标，将图像的4个边框处的临时标记值都置为2，将二值图像中的原本为1的白色区域的临时标记置为1。原本被白色区域包围的黑色区域的临时标记都将大于2，最终只输出所有标记值大于2的区域，从而完成目标区域的提取。

算法首先对二值图像进行从上到下、从左到右的一次扫描，在扫描过程中进行连通域的临时标记，并且对临时标记对应的参数存储器进行更新。在标记过程中发现两个临时标记等价时，需要在等价表中生成对应的等价关系。一次扫描结束后，对临时标记以及参数存储器进行整理，同时剔除一些面积小的虚假目标。最后，将目标区域对应的参数寄存器内的数据输出。

算法主要由3个部分组成：图像标定与等价表生成模块、标记值参数寄存器更新与合并模块，以及等价表整理模块。

1.1 图像标定与等价表生成模块

标记模块采用单次逐像素法对输入的大小为M×N的二值图像进行标记。标记模块采用4连通模式，每个点需要考虑该点的正上方点和左边点的值(如果存在)。标记时，需要1个初始值为3的标记值tip，1个等价表L和两个行存储器，分别为行存储器0和行存储器1。等价表L中地址代表临时标记，值对应等价关系，例如L(n1)=n2，表示临时标记n1和n2具有等价关系。当标记模块对第0行进行读取时，只对行存储器0进行操作，在行存储器0对应位置写入当前行位置像素的标记值；当标记模块对1、3、5等等奇数行进行读取时，行存储器1写入，行存储器0作为该行的上一行；当标记模块对2、4、6等等偶数行进行读取时，行存储器0写入当前行位置像素的标记值，行存储器1作为该行的上一行。

图3中箭头表示图像扫描的顺序，灰色部分为已经标记完成的像素点，白色部分为未标记点，x表示当前待标记点的值，a、b、c、d均为临时标记值。在进行全图标记时主要由以下几种情况：第1行、第M行、第1列、第N列以及2～M行2～N列。其中第一行、第M行、第一列和第N列组成了一幅图像的框架，本算法中将这两行两列所对应的标记都置为2。对第2～M行2～N列，先判断当前像素点的值为0还是1：如果是1，那么将该点对应的标记都置为1；如果为0，则需要查看该像素点上一行同位置行存储器1中的值和当前行坐标位置行存储器0中的值。具体可以分为以下几种情况(假设当前行为偶数行，即行存储器0为当前行，行存储器1为上一行)：(1)左边和上边都是1。即左边像素点值的标记值d为1，上边像素点值的标记值b为1，当前像素点与左边和上边的点都不连通，可以当做一个新的开始节点，将tip的值赋给当前像素点对应的行存储器0。同时对等价表L进行操作，以tip为地址，写入值为tip，最后tip加1；(2)左边为1，上边大于等于2。即左边像素点值为1，上边像素点值为0，该像素点的标记值等于上边的点的标记值，将该值写入对应的行存储器0。不对等价表进行操作；(3)左边大于等于2，上边为1。即左边像素点值为0，上边像素点值为1，该像素点的标记值等于左边的点的标记值，将该值写入对应的行存储器0，此时不对等价表进行操作；(4)左边大于等于2，上边大于等于2。此时出现了等价关系，需要比较上边像素点的标记值b和左边像素点的标记值d的大小关系。若b=d，不进行等价关系的处理；若b>d，将左边点标记值赋给当前点，同时将临时标记b和d计入等价关系；若b

1.2 标记值参数寄存器更新和合并模块

参数存储器的结构如表1所示，其中需要记录的参数有6个：对应的标记值、该区域的x坐标最大值Xmax、x坐标最小值Xmin、y坐标最大值Ymax、y坐标最小值Ymin以及该区域的面积。

表1参数存储器结构Table 1.Memory data structure

在图像顺序标定的同时，需要对标记值参数存储器进行更新操作。当在标记过程中遇到一个坐标为(x,y)像素点时，若该点不和邻域连通，则为一个新的临时标记值，令该像素点的标记值对应的参数存储器中的Xmax=Xmin=x，Ymax=Ymin=y，面积置为1。当遇到的临时标记值出现过时，将面积加1，同时将该点的x、y坐标值和参数存储器中对应的值比较后更新。当出现两个临时标记值的区域合并，且该两个临时标记值都大于2时，进行标记参数存储器的合并。将两个临时标记值对应参数存储器中的面积相加，x,y最值相比较更新后都存入数值较小的临时标记值对应的参数存储器中。

1.3 等价表整理模块

图像标定结束时会给出等价表整理开始信号，同时新建一个输出表L1，此时记录需要输出的临时标记值，以及一个初始为1的最终标记值sum。从地址0开始读等价表L中的值，每当地址和读出的数据相等时，将该临时标记值写入原先的地址中，然后处理下一个地址；如果读出数据小于地址，那么将该数据当做新的地址，再次读取。重复这个操作，直到所有地址都处理完成。在这个过程中，每次出现地址和读出数据相等的情况时，若满足输出表L1更新条件，则将该临时标记值写入L1[sum]，同时最终标记值sum加1。输出表L1更新条件为：该临时标记值大于L1[sum-1]且大于2，对应的参数存储器中面积大于500。

2 FPGA实验

为了验证该算法的实际效果，采用Xilinx的Spartan-6系列XC6SLX45芯片，将待处理的二值图像通过PC输入到FPGA，经过处理后再将结果输出回PC端以方便显示与分析。需要注意的是，本算法针对的目标图像有一定的局限性：(1)目标透镜需要尽可能不出现在第1行、第M行、第1列和第N列；(2)目标需要在特定光照条件下生成具有环形轮廓的目标。

选择图6中二值图像(a)为待处理图像，大小为1 280×1 024。整个过程一共形成了254个临时标记，经过等价表处理和虚假目标剔除，最终只剩下4个最终标记进行输出。图6(b)是经过标记后的图像，其中白色区域是临时标记值大于2的像素点。

经过等价表整理后，sum=4，因此输出L1中地址1到地址4对应临时标记值的参数存储器。表2是输出表L1记录的数值。表3是4个对应参数存储器输出的数据。

表3临时标记值以及对应的参数Table 3.Temporary markup value and corresponding parameters

在初次标记后的图像的基础上，利用统计出来的每个区域x和y的最值所形成的外接矩形在每个区域外都画一个方框，结果如图7所示。可以看出一共框出了4个区域，且这4个区域分别对应二值图像中目标的内部轮廓，完成了多个目标透镜分离。整个电路的工作时间为1 280×1 024×2+254×2个电路时钟周期，对比文献[8,16]中的实现方法，对该图像标记的工作周期是1 280×1 024×4，本算法消耗的时间更少。

3 结束语

连通域标记是图像处理的重要部分，本文设计了面向环形目标的连通域标记算法，在单次连通域扫描的过程中，通过在图像的4个边框处做一个特殊的标记值，提取出具有环形轮廓的目标内部轮廓所包含的区域，实现了将紧挨在一起的透镜目标分离开的目的。该算法运算速度较快且结构简单，已经被应用在了多目标透镜的定位和凹凸面的识别系统上。