快速连通域标记算法在堆叠棒材计数中的应用研究

，

(1.咸阳师范学院计算机学院，陕西 咸阳 712000；2.陕西科技大学电气与信息工程学院，陕西 西安 710021)

0 引言

钢材制造、销售企业里成品棒材按规定支数进行标准化打捆包装是棒材生产、销售过程中的一个重要步骤。目前，在定支打捆和计数过程中，很多企业仍然采用人工或机械方式进行计数，劳动强度大且效率低。随着企业自动化程度的提高及生产节奏的加快，对堆叠棒材支数进行自动、准确、快速计数的需求已越来越迫切。

1 基于图像处理的堆叠棒材自动计数方法

近年来,很多国内外学者实现了基于不同方法的堆叠棒材自动计数功能，其中基于计算机视觉的方法由于其便于操作、结果准确等特点越来越受关注。基于计算机视觉的堆叠棒材自动计数方法主要有模板匹配、极限腐蚀、凹点分割及融合计数等方法。

模板匹配是计算机视觉领域中以目标几何形状为基础的识别方法，具体是将模板图像在待检测图像上移动，计算匹配程度，然后根据设定的阈值确定是否检测到目标对象。采用这种方法，搜索间隔的选取会影响算法的性能，间隔太大容易导致漏计，间隔太小又会降低搜索速度，进而影响算法的效率。极限腐蚀法是通过对图像不断进行形态学中的腐蚀操作，找到每一根棒材截面区域的中心点，用以解决粘连棒材计数问题，采用这种方法腐蚀结构元素的选取较为关键。凹点分割法的思想基于棒材断面是近似圆形的假设，认为在两根棒材的连接处必会形成一对凹点，凹点的连线能够将连通棒材分离，从而消除棒材间相互粘连现象的干扰。融合计数方法是将棒材端面图像进行阈值分割，利用边缘检测算法找出各连通域的边界，对其进行填充，并滤除细小的区域，然后将所得数据加以融合，去除粘连后计数[1-3]。

经过对现有基于计算机视觉的棒材自动计数方法的研究、分析，发现在这些计数方法中，最后一步都需要统计二值化以后的棒材截面图像中的目标(物体)个数。目前统计图像中目标个数，最终大都需要采用图像连通域标记算法对图像中的连通区域进行计数。因此，采用计算机视觉的方法对棒材进行自动计数，提高计数速度的关键是提高连通域标记算法的效率。

2 连通域标记算法

连通域标记算法一般针对二值图像进行。二值图像是指图像中的每一个像素只有两种可能的取值或灰度等级状态，通常用黑白、B&W表示。在二值图像中，由于同一目标的像素通常具有连通性，可以通过连通域标记来区分图像中不同的目标，进而提取各个目标的特征，再进行图像分析。所以，二值图像连通域标记处理是提取图像中各个目标特征的前提，是图像模式识别领域里极为重要的基本处理之一。

二值图像进行连通域标记后示意图如图1所示。经过标记的图像，位于同一个连通域里的像素都赋予一个相同的标记(用数字标记)，不同的连通域代表不同的目标(物体)，具有不同的标记。在图1中，有3个不同的连通域，也就是有3个(目标)物体。

图1 连通域标记

近年来，很多学者在从事二值图像连通域标记算法的研究，也提出了很多有效的算法。例如，Chang等人提出了基于边界跟踪的连通域标记算法，通过一次光栅扫描之后的标记和两次内外连通区域的扫描来确定一个连通区域[4]；Martin-Herrero提出了混合标记算法，将光栅扫描和队列结合使用，该算法也得到了较好的效果[5]；Wu等人提出了运用Union-Find数据结构解决等价关系的标记算法，采用了类似有向图连通性的划分方式，将各个等价类映射为一个图上的点，如果等价则相互连接构成环，最终一个环就是一个划分的等价类，实现了划分等价类的目的[6]。曹长虎和李亚非提出了通过轮廓跟踪技术进行标记的方法[7]。2014～2017年，He等人提出了利用等价标号集合来解决等价关系的新方法，并给出了实现这种方法的数据结构[8-9]，马毅超等人将这种处理方法用FPGA实现，充分利用FPGA的并行处理能力，在一个时钟周期内完成9个像素的处理，在对图像进行遍历的同时进行快速标记，得到了较好的效果[10]。

3 计数方法的实现

经过对堆叠棒材截面图像分析，发现这类图像中目标像素比例较大，而且相对集中。针对堆叠棒材截面图像这一特征，在现有研究成果的基础上，提出基于图段的快速连通域标记算法并应用于堆叠棒材的计数。

所谓图段，指的是二值图像中任意一行中连续的目标像素的序列，图段之间被背景像素或行边界分隔。如图2所示，图中第1行有3个图段，第2行有3个图段，两行之间有4个相邻接的图段，图2中用椭圆标出。

图2 图段以及相邻接的图段

3.1 图像预处理

为了在后续步骤中计数准确，需要将获取到的堆叠棒材的原始图像进行预处理。预处理包括图像增强、二值化、去噪和分割等步骤。

在实际生产环境中，由于图像拍摄环境所限，在曝光不足或过度的情况下，图像的灰度可能会局限在一个很小的范围内，目标和背景对比度不是很明显，这时得到的图像可能是一个模糊不清、没有灰度层次的图像。这时可以采用线性变换对图像中每一个像素灰度作线性拉伸，将有效改善图像视觉效果。

线性变换是一种最基本的灰度变换，主要思想是提高图像处理时灰度级的动态范围，使用的是最简单的分段线性变换函数，可以有选择的拉伸某段灰度区间以改善输出图像。

假定原图像f(x,y)的灰度范围为[a,b]，变换后的图像g(x,y)的灰度范围线性的扩展至[c,d]。则对于图像中的任一点的灰度值P(x,y)，变换后为g(x,y)，其数学表达式为：

(1)

若图像中大部分像素的灰度级分布在区间[a,b]内，maxf为原图的最大灰度级，只有很小一部分的灰度级超过了此区间，则为了改善增强效果，可以利用公式(2)进行图像增强。

g(x,y)=

(2)

在图像二值化步骤中，由于棒材截面图像背景较为单一，可以利用灰度图像的直方图，选取波谷的灰度值作为二值化的阈值。

在图像分割步骤中，为了避免采用传统分水岭算法容易出现的图像过分割问题，本实验中将传统分水岭算法进行了改进，去除了局部最小值，有效的避免了图像的过分割现象，将粘连棒材较好的分割开便于计数。图3是棒材图像去噪、分割前后的对比图。

图3 图像预处理前后的对比

3.2 基于图段的连通域标记方法

二值图像基于图段的连通域标记过程分为3个步骤：

①逐行扫描图像，为扫描到的每个图段分配临时标记，并寻找哪些标记属于等价标记。

②记录并解析等价标记。

③用唯一标记进行等价标记替换。

因此，在进行图像连通域标记过程中，需要对图像进行两次从上到下、从左到右的扫描。第一次扫描完成后，所有位于等价标记集合之中的标记是等价标记；第二次扫描的任务是标记替换，用唯一的代表标记替换等价标记集中的所有标记。

在第一次扫描过程中，对于寻找到的每一个图段，需要检查上一行中已经扫描过的图段，并进行以下处理：

①如果上一行中没有与当前图段形成邻接关系的图段，给当前图段分配一个临时标记。如图4a所示，需要给新扫描到的2个图段分配标记“1”和“2”。

②如果上一行中有一个图段与当前图段形成邻接关系，将当前图段的标记为上一行中的图段的标记。如图4b所示，第2行中的第1个图段和第1中的第1个图段邻接，因此该图段的标记也是“1”；同理，第2行第2个图段的标记为“2”。

③如果上一行中有多个图段与当前图段形成邻接关系，将当前图段标记为与之形成邻接关系的任意图段的标记，同时记录这些等价标记。如图4c所示，第2行中的图段和第1行中2个(或2个以上)图段相邻接，可以给这个图段标记“1”或“2”。此时，标记“1”和标记“2”为等价标记，需要记录下来S(1)={1,2}。(在这个集合中，标记“1”和标记“2”为等价标记，这个等价集合的代表标记为“1” 。)

图4 相邻行之间图段可能存在相邻情况

将所有图段标记后，会得到一些等价标记集合。为了解析等价集合中的标记，确定哪些不同集合中的标记是等价的，本实验中事先定义了3个一维数组。

第1个数组R用来记录代表标记。当为一个图段分配了一个临时标记a，而这个临时标记的代表标记为r时，R[a] =r。第2个数组NEXT用来记录在一个等价集合中一个临时标记的下一个标记。NEXT[d] =e表示在一个等价集合中，标记d的下一个标记是e。特别地，当某一个标记x是一个等价集合中最后一个标记时，x没有下一个标记时，标记x的NEXT[x] = -1。第3个数组LAST，当一个等价标记集合S(其代表标记为p)的最后一个标记为t时，LAST[p] =t。

如图5所示，如果2个等价标记集合中的标记是等价的，则这2个集合属于一个等价类，则需要将这2个等价集合合并，S(w) =S(u)∪S(v)，其中，w是u和v中的较小值。

如果u小于v，则等价标记集合S(v)会被合并到等价标记集合S(u)中，步骤为：

①对S(v)中的每一个标记k，更改其代表标记。

②将S(u)中的最后一个标记的下一个标记为v。

③将S(u)中的最后一个标记更改为S(v)的最后一个标记。

事实上，在图5中，标记“u”，“x”，“v”和“y”都属于同一个等价标记集合，这4个图段是属于同一个连通域的。

如果v小于u，则刚好是一个相反的合并过程。

图5 等价集合合并

由于已经解析了等价标记集合，知道哪些标记是等价的，接下来将属于同一等价标记集合中的最小标记作为该等价标记集合的代表标记，在第二次扫描过程中，将各个图段的临时标记用其所在等价标记集合的代表标记进行替换，得到每个图段最终的标记。

最后，只需要统计不同标记个数就可以得到图像中连通域个数。

4 实验结果

为了验证方法的正确性和有效性，本实验采用随机生成的噪声图像对算法的正确性和有效性进行了测试。测试平台为台式机(Intel Core i5-3470 CPU@3.20 GHz，4 GB内存)，编译器为GNU C compiler(版本4.6.1)。为保证实验结果的准确性，所有计算图像的连通域的程序均被运行1 000次，取平均值作为实验结果。

用来测试算法的41幅512×512的噪声图像采用门限法随机生成，阈值从0到1 000(阈值为0的图像中没有目标像素，阈值为1 000的图像中全部像素为目标像素)，步长值为25。测试结果表明，提出算法的结果和用其他算法对图像进行连通域标记的结果完全一致，而且在绝大多数图像的运行时间小于现有其他算法。

此外，如图6所示，本实验采用经过预处理的棒材图像对算法进行测试(为了有较好的显示效果，在算法实现过程中将图像中目标像素置为黑色，背景像素置为白色)，测试图像分辨率为1 366×768像素。

图6 测试样图及结果

经过测试，算法在测试图像上运行1 000次的平均时间为152 ms。

5 结束语

针对堆叠棒材计数中存在的问题，根据堆叠棒材的图像截面特征，本文提出了基于图段的连通域标记算法应用到堆叠棒材的计数中，实验验证了算法的准确性和有效性。此外，此方法可以稍加修改就可以应用到其他领域的快速计数中，如医学病理检测领域中的细胞计数、环境保护领域中水中浮游生物的计数等。