改进的近邻聚类算法用于水下焊缝图像的识别

何银水，胡兆吉，胡宗梅，谢晓闻

（1.南昌大学 过程装备与测控工程系，江西 南昌 330031；2.格特拉克（江西）传动系统有限公司，江西 南昌 330031）

0 前言

在识别焊缝图像待焊位置的坐标时，一些比较多的方案中会采用小波分析、滤波、阈值分割和拟合[1-3]等，而这些处理过程中很难有效地消除干扰数据，究其原因文献[4]详细的分析了干扰的成因。文献[5]提出采用跟踪V形焊缝的平均高度，以此高度作为基准，结合V形焊缝的深度来消除干扰。这一方法的前提是要较为准确地获得V形焊缝的平均高度，当气泡或者弧光形成的干扰阈值分割后的形状与焊缝的左右边类似时，这一方法的效果将大打折扣。聚类分析法通过对焊缝图像中的各类数据进行分类，再根据一些决策直接寻找到属于V形焊缝的类，在不消除干扰数据的情况下可以准确地识别焊缝。当然，近邻聚类法的聚类结果很大程度上依赖于第一个聚类中心的位置的选择、待分类模式样本的排列次序、距离阈值T的大小以及样本分布的几何性质等[6]。

1 改进的近邻聚类算法

1.1 算法描述

（1）任取样本Xi作为第一个聚类中心的初始元素，例如 Z1=X1。

（2）计算样本X2到Z1欧式距离D21= ||x2-x1||，如果D21>T，则定义一个新的聚类Z2=X2；否则X2∈Z1聚类。

（3）假设已经有聚类Z1和Z2，且它们都已有多个样本。对样本Xj，计算其与Z2聚类最后一个样本之间的距离t，如果tT，则计算其与所有聚类的最短距离 t′，同时记下所在的类 c′，如果 t′

（4）以此类推，直到把所有的样本分类完全。

1.2 实现步骤

第一步：对阈值处理后的焊缝图像从左到右、从下到上进行遍历。以第一次搜索的“白点”样本数据作为第一个聚类的初始值。

第二步：计算第二个样本与第一个样本的欧式距离，如果大于T，则开新类；如果小于T，则把它仍归为第一聚类。当只有一个聚类且其样本数大于1时，那么后面搜索到的样本在归类前先计算其与第一个聚类中的最后一个样本的欧式距离，只要这个距离比T小，则该样本仍然属于该聚类（这是由搜索顺序决定的，这样做可以减少计算量）。当上述距离比T大时就计算其与第一个聚类中所有其他样本的欧式距离，找出最短距离，如果该最短距离仍然小于T，则该样本仍然属于第一聚类，否则就开新类。

第三步：当聚类的个数大于1时，搜索到的样本先计算其与最后一个聚类的最后一个样本的欧式距离t。当tT时，就计算其与已知的所有聚类的所有样本的欧式距离，找出最短距离t′并同时记下对应的聚类 c′，当 t′

1.3 聚类合并处理

（1）对需要合并的聚类处理。

如果聚类之间出现了合并的情况，可以在算法进行中合并，也可以在分类结束后完成。如果选择在分类结束后完成，那么必须在算法进行中保存需要合并的聚类的名称，可以通过定义结构体来保存：struct combination{int category[100]；int sum；}。结构体中定义两个成员变量：一个是数组category[100]，用于存放被合并的聚类；一个是整型变量sum，用来统计被合并的类的个数。这样的结构体可以定义100个：combination[100]，用来保存与之前合并的聚类没有联系而需要合并的新的聚类。结合本研究的最终识别V形焊缝处数据的这一目的，选择在分类完成后合并聚类。

进行合并时，把结构体中后面数组所保存的聚类的数据依次保存在第一个数组所代表的聚类的名目下，每个结构体数组都进行类似处理即可实现数据的合并。当然，合并后后面数组所代表的聚类的数据可以进行销毁，也可以保持不动。

（2）出现了合并聚类现象总的分类数目的确定。

在对图像中的数据进行分类而又出现了合并聚类的现象时，真正的聚类数目要比算法统计出来得少，那么真正的聚类的数目可以如下计算

式中 sumstatistic是算法统计的聚类数目；combination[i].sum是每个结构体数组保存的合并的聚类的数目。

2 图像分类处理分析

2.1 阈值分割后直接进行分类

把图1进行自动阈值分割，得到的结果如图2所示。由图2可知，相当于对两类光带状的样本（灰度值为255的白点）进行分类。由于两类之间距离比较远，且类间相距很近，所以分类很准确。

图1 水下原始图像

图2 对图1阈值处理

因干扰光斑或者V字形焊缝在阈值处理后都是带状形的，程序在搜索样本时，只要相邻样本不是在光带的边缘，那么其间的欧式距离都是很小的，只有在上下边缘部分相邻的样本，其欧式距离才有可能超过距离阈值，因此，算法设计对待分类的样本先计算它和当前聚类最后一个样本的欧式距离来判断其是否属于当前聚类，有助于节省计算时间。如果上下边缘相邻的样本的欧式距离超过了距离阈值，这种情形算法设计计算该样本与所有已知聚类的所有样本的距离，用最近邻法则对其进行归类也保证了分类的准确性。

图3是在图1的基础上人为添加了不同形状的干扰，且干扰离V形焊缝比较近。阈值处理后如图4所示，当距离阈值设置得比较小时，它们所属的类别会不同，但是当距离阈值设置为20时，正方形形状的干扰和V形焊缝就应该被合并在一起。通过处理试验，本算法可以准确做到这一点。

2.2 阈值分割求取光带中心线再分类

在寻找V形焊缝待焊中心坐标时，有时要求取阈值处理后图像中的光带的平均位置，这样所得图像中的样本呈现线状，如图5所示。那么如果是对这样图像中的样本数据进行分类时，基本上就只要计算待分类的样本与当前类的最后一个样本的欧式距离，根据这一距离的大小对其进行归类，当距离大于距离阈值时就不需要计算其与所有已知聚类的所有样本的距离，然后再根据最近邻法进行归类。

图3 加干扰图像

图4 对图3阈值处理

图5 对图4求取样本平均高度的结果

3 基于聚类V形焊缝的识别

在成功对所有样本进行分类后，剩下的工作就是如何在这些聚类中准确的寻找属于V形焊缝的聚类。问题的关键是以什么样的准则来完成这一工作。现介绍三种准则。

（1）根据每个聚类中第一个样本与最后一个样本的欧式距离准则识别V形焊缝。

这一准则实现起来比较简单，但是前提是干扰形成的样本在空间上比较集中，因此其应用有相当的局限性。应用这一准则上述图像还是比较容易达到目的，识别的结果略去。

（2）根据“V”字的特征识别V形焊缝。

V字的特征是先有相当一部分数据在一定的水平范围内其高度是逐渐降低的，后在另外一定的水平范围内其高度是逐渐升高的。经过试验，在水平30个像素范围内高度逐渐降低或者升高的样本个数大于25个。那么根据这两个特征，可以准确寻找到V形焊缝的类。这样准则实现起来也不难，但是其适应性大大提高了。

（3）同时满足上述两种准则。

把准则一和准则二结合起来，即当某一聚类的样本同时满足第一个特征和第二个特征就认为是属于V形焊缝数据的聚类。这样更能提高识别的准确性。根据准则三对图4和图5识别的结果如图6、图 7所示。

图6 消去干扰

图7 消去干扰线形焊缝

注意：当获得图4中各个光带在图中的平均高度位置后，此时V形焊缝光带与正方形光带的平均高度之间的距离超过了设定的距离阈值20，所以当从线形焊缝图像中以本算法消除干扰数据时，正方形干扰形成的线形数据被消去了。

4 提取V形焊缝待焊位置坐标

V形焊缝图像识别的最终目的是获取待焊位置的坐标，方法有投影法、曲率法[7]和最小二乘法等。其中最小二乘法能比较准确获得各种V字形焊缝待焊位置的坐标。本研究采用最小二乘法获取图7待焊位置坐标，结果如图8所示。

图8 拟合获取焊缝待焊位置

5 结论

（1）由于本算法设置了自决断是否对聚类进行合并，因此算法克服了因搜索路径或者因待分类模式样本的排列次序的不同而致使分类结果的不同，提高了算法分类的准确性。

（2）在对所有的样本进行分类后，提出的基于“V字”形的特征可以准确的识别出属于V形焊缝的类，从而准确获得焊缝待焊接位置的坐标。

：

[1]刘 桑，钟继光，王国荣，等.水下湿法焊接电弧图像的边缘检测技术[J].电焊机，2000，30（4）：14-17.

[2]李国进，王国荣，钟继光，等.水下焊缝自动跟踪路径的识别[J].焊接学报，2005，26（3）：58-62.

[3]何银水，张 华，余卓骅，等.水下焊接中V形焊缝的识别[J].焊接，2007（7）:49-52.

[4]徐鹏飞，张 华，贾剑平，等.水下焊接机器人视觉传感系统图像干扰因素分析[J].焊接，2008（5）：33-37.

[5]何银水，周国发，张 华，等.基于路径跟踪的水下焊接V形焊缝识别中强干扰的去除[J].应用光学，2009（5）：747-750.

[6]齐 敏，李大健，郝重阳.模式识别导论[M].清华大学出版社，p20.

[7]刘国平，张 华，胡瑢华，等.V形焊缝特征点提取的算法研究[J].焊接，2006（2）：36-38.