陈 帅

（中海广东天然气有限责任公司 广东 珠海 519015）

0 引言

巡检无人机自主规划巡检路径对输电线路杆塔进行巡检和拍摄后，对拍摄图像进行实时分析诊断，并自动统计输出巡检过程中发现的缺陷。但存在单个缺陷点反复统计的问题，造成统计种类及数量远大于真实情况，严重影响巡检报告的真实性，具体原因是因为同一个缺陷在多个图像中都会被拍摄并统计[1]。

聚类算法是机器学习的核心任务之一。聚类的目标是把相似的数据点划分到同一个簇中，并最终得到划分完成的多个簇，根据簇的数量可以将数据点分为不同的类别。其在机器学习领域上有规范的应用。对于空间中的三维点云数据，通过聚类算法，也能够进行划分，得到对应数量的簇，以此判断三维点云所代表的三维物体数量。

K-means 聚类算法为当下最为直观和方便使用的聚类算法。Ball 和Hall[2]发明了ISODATA 技术进行k 值的估算，动态调整集群的数量k。Figueiredo 和Jain 使用最小信息长度准则并结合高斯混合模型，对k 值进行估计。针对手肘法确定k 值过程中存在的“肘点”位置不明确问题，基于指数函数特点、权重调整、偏执项及手肘法基本思想，提出了一种改进的k 值选择算法ET-SSE 算法，但k 值选择的效果由受到其引入的权重调整变量的影响，在实际场景中需要不断实验才能得到优于基本手肘法的效果 。

由于means 算法只收敛于局部最小值，因此聚类有可能无法得到全局最优结果。为克服这个问题，需要对集群的初始化进行改进。K-means 算法常用欧式距离度量点与聚类中心的距离。利用马氏距离能够优化K-means 聚类在超椭球集群的度量，但会带来极高的计算成本，鉴于以上分析的困难，寻找合适的方法与计算技巧是本研究的核心目的。

1 研究目标

对无人机拍摄的多图像间重复目标进行筛查和定位，靠人工对图像进行核查是十分耗时耗力的，因此通过建立航拍图片位姿信息获取、三维数据重建、聚类计算等流程，研发了“面向输电线路巡检的多图像间重复缺陷自动筛查组件”，以实现对重复缺陷的准确筛查和定位。

（1）在方案步骤中，“读取图像并分类”与“三维数据重建分析”部分作为已经完成的研究工作，直接为本文提供图像资料源。如图1 所示

（2）结合已经获取的图像资料，研究三维点云的K-means 聚类，通过对空间中点云的聚类划分以及聚类结果的评估，对多图像间同类型缺陷在空间中的实际数量得到初步结果。

（3）研究三维聚类结果与二维缺陷图片的关系映射，结合先前研究获得的约束条件，计算准确得多图像间同类型缺陷的实际数量，并输出得到结果[3]。

2 聚类计算

2.1 技术原理

2.1.1 K-means clustering algorithm（聚类算法）

K-means 聚类算法属于聚类算法中的一种，其本质是通过迭代的方式把数据对象归于不同的簇里面去，然后求极值。其算法的大致思想为：先从数据集中选取K个样本作为簇中心，后验算所有样本点至各个簇的中心之间的间距，再将每个样本划分到与其距离最近的簇中心中，对于得到的新的簇，再次计算新的“簇-中心”[4]。

根据上述描述，可知实现means 算法，主要有如下三点：

（1）簇个数k 的选择

（2）各个样本点到“簇中心”的距离

（3）根据新划分的簇，更新“簇中心”

对于不同图片上的缺陷区域，总会存在一点，使其投影回图片上时，会在对应的缺陷区域内。不同图片相同缺陷所产生的点，其空间位置应是接近的，而不同图片不同缺陷所产生的点，则会出现很大偏差。因此，通过means聚类，就能判断生成的空间点，是否为同一拍摄缺陷所产生的点。

首先，运用“肘”方法确定k 值。

其次，距离的度量：

闵氏距离（Minkowski distance）：

欧氏距离（Euclidean distance），即当p=2 时的闵可夫斯基距离：

曼哈顿距离（Manhattan distance），即当p=1 时的闵可夫斯基距离：

最后，更新“簇中心”，对于划分好的各个簇，计算各个簇中的样本点均值，将其均值作为新的簇中心。

2.1.2 聚类效果评估

传统K-means 聚类算法由于需要提前设定k值，因此需要在使用时，对不同k值下的聚类进行评估，从而判断合适的k值。对于K-means 聚类效果评估的办法，常见的为手肘法和轮廓度系数。肘方法为计算聚类的误差平方和，按照肘方法理论进行分析和计算如图2 所示，k取4 时曲率最高，故对于这个数据集的聚类而言，最佳聚类数应该选4。

轮廓度系数法对每个k值下聚类簇中的成员点，计算其轮廓系数。具体为：

对于第k个聚类下的点Pi来说，有：

其中，size（i，k）为第k个聚类排除点Pi的情况下成员点数量，dis(i，j)为点Pi与Pj的欧式距离。由此，a(i，k)的物理意义为：点Pi到第k个簇的所有点的距离的平均值，b(i)为点Pi到所有非所在簇的平均距离的最小值。S(i)即可表示点Pi的轮廓系数，所有样本点的轮廓系数均值，即可表示为当前k聚类下的轮廓度系数。

2.2 技术方案

对于聚类计算的研究，具体技术路线为图3 所示。首先根据缺陷图像和三维点云，初步估计K值可能的范围，其次遍历范围内的K值，对三维点云进行means 聚类。然后对不同k值下的结果，进行评估。最后根据评估的结果，选出最合适的k值，并得到该k值下的聚类结果，并根据k得到初步的实际缺陷数量判断。

根据聚类计算的研究现状、技术原理、技术路线以及实际实验的情况，设计并实现了聚类分析模块，其功能为根据点云和缺陷图片，进行means 聚类计算，并比较不同k值下聚类的结果，选取最符合的k值为聚类数，并获得对应k值下的聚类簇，以此作为初步的实际缺陷数量判断。

2.2.1k值范围

由于需要对多个不同的k值进行聚类计算，以此若能够初步确定k值的范围，便能够减少许多不必要的计算。根据缺陷图像中每张图像上同类型缺陷的数量，可以得到k值的下限Kmin:

其中，Pic(n)为第n张图片下对应缺陷类型的缺陷数量。同理，可计算k值的上限jmax

其中size为点云的点数量，each为两图片的两个缺陷计算可靠三维点时，加入到点集进行聚类计算的点数量。由此可得到聚类的上限值。但在实验中发现中，jmax的值仍会偏大，因此在实际使用中，会选取一个合适的数组，代替jmax，作为k值选取范围的上界。

2.2.2 中心点打靶

进行means 迭代运算前，需要进行初始聚类中心点的选取，由于传统means 聚类容易陷入局部最优解的情况，因此需要通过合理的初始聚类中心点选取方式，避免在聚类过程中出现情况。因此，设计如下步骤，获得较好的初始聚类中心点：

（1） 计算点集P中各个点之间的距离

（2）选取点间距最大的两个点p1，p2，作为初始的两个聚类中心点，并从P中剔除p1，p2，放入聚类中心点集Pf。

（3）for 2

2.2.3 实现流程

means 聚类算法通过设置初值K，假设点集中聚类的个数，并以此寻找合适的K个点作为初始点后进行means聚类，从而得到有K个聚类时的聚类结果。对于该算法，其大致步骤为：

（1）获得图片集中关于某一缺陷类别生成的样本点集Pn；

（2）计算选取Pn中的K个点，作为最初的聚类中心点Pfi，其中i∈[1，K]；

（3）for，计算其与各个聚类中心点的欧式距离，并选择最近的聚类中心点为其所属的聚类，该点为；

（4）计算各个聚类中样本点的中心，并以此更新聚类中心点；

（5）重复（3）-（4）步骤直至稳定或超过限定次数；

（6）获得最终的聚类和聚类中心点。

通过上述步骤，即可得到假设点集是由K个不同缺陷生成时的点分布情况。

2.2.4 最优K值获取

得到指定K值时的聚类情况，但此时的K并不一定与实际的不重复缺陷数量相同，因此需要对其进行判断。在此之前，首先需要对已完成means 聚类计算的K聚类结果进行处理。

处理方法大致分为合并和去噪。首先需要计算各个聚类中心点之间的距离和各个聚类的类内距，若聚类中心点距离小于聚类的类内距之和乘以一系数，则可认为两个聚类可以合并为一个聚类，因此进行合并。当合并操作结束后，再检查各个聚类的成员点数，当点数过少时，则判断该聚类为噪声点距离，并给予筛除。

完成合并和去噪后，得到了处理后的聚类结果，对此，需要计算其可信度，判断此时的聚类结果是否为实际的聚类结果。经实验，对于K=n时的聚类结果，其可信度公式为：

其中，Pi为第i个聚类的中心点，dis(p1，p2)为点p1与点p2的距离，numsi为第i个聚类的成员点数，inner_xisi为第i个聚类的类内距。support的值越大，则K=n时的聚类结果越可信。

因此对于给定的点集和图片，首先获得一个K 值选取的范围后，依次进行means 聚类计算，之后对于不同的K值下聚类结果，计算其可信度，并选取可信度最高时的聚类结果，作为所认为的不重复缺陷的数量。

2.2.5 仿真运行

聚类计算步骤以及项目的开发环境为window 环境，采用c++作为编程语言。在进行聚类之前设置了筛选系数coe，将位于图片组的相机包围圆一定范围外的点以及过于靠近相机位置的点筛除后，根据技术方案的步骤进行实验，并与预期结果进行比较。

实验中在取coe=0.8 的情况下，即与相机包围圆中心距离小于0.8 时的点筛选为可靠点时，根据上述步骤的最优k值选取策略，能够得到较高准确率的结果。

2.3 小结

聚类计算的研究，通过means 聚类的具体原理、以及常用的聚类效果评估方法入手，在结合实验对聚类评估和聚类点筛选等方面进行调整，使得最后得到较为准确的支持率算法，通过该支持率算法对聚类进行评估获得初步的聚类计算结果，为之后的进一步聚类计算结果提供了可靠的数值参考。同时实验表明，此时的聚类计算k值选取已有较高的准确率。

3 聚类与缺陷映射

3.1 技术路线

聚类与缺陷区域的映射关系，实际上为三维空间点与二维图像的映射关系。此时需要解决的问题，主要为将具体的聚类与具体的缺陷区域进行一一对应，得到最终的缺陷区域划分结果。

由此具体技术路线为：实现将获得的聚类的中心点，投影至图片上；其次计算投影后的点与图片上缺陷区域的距离百分比；之后根据距离百分比，寻找缺陷区域最匹配的投影点，此时认为该缺陷区域即属于投影点本身对应的聚类；以上述方式完成聚类与缺陷的映射。最终输出结果。

3.2 技术方案

聚类与缺陷映射的具体技术方案和步骤如下：

对于分析得到的聚类结果，需要将聚类与图片的缺陷进行对应。其步骤为：

（1）计算各个聚类的中心点，得到点集PK；

（2）通过变换矩阵模块，将点集的点投影至图片上，得到投影后的点集Pk；

（3）计算图片上对应类型缺陷的中心点位置，得到点集Pd；

（4）选取Pd上内的一点pd，计算其与Pk上各点的距离；

（5）选取与pd距离最近的点pk，将pk投影前所在聚类与pd对应；

（6）将pd、pk分别从Pd、Pk中去除；

（7）重复（4）～（6）直至Pd内没有剩余点；

（8）完成聚类与缺陷的对应。

由此，完成就聚类与缺陷的对应。

3.3 研究总结

聚类与缺陷映射的研究，将空间的三维点聚类问题，回归至了原本的重复缺陷筛查问题。通过可靠三维点计算，将二维的图像问题先转换成三维的点云分布问题；再通过k-means 聚类算法，解决了三维点云的划分问题；之后再通过聚类投影至图片于缺陷进行比较现实映射关系，将三维点云划分的解决结果，转换成了需要的缺陷筛查结果，使得最终得到所需要的判断出现重复的缺陷并筛查的功能。此时得到的结果，能够将其输出成研究内容所需要的格式，是组件的收尾步骤，也是研究的收尾问题[5]。

同时，可以再根据点筛查时得到的缺陷区域可能存在的互斥的约束条件，修正聚类计算时的聚类结果，得到最终的实际缺陷数量，输出正确的结果。

4 研究成果及创新点

4.1 研究成果

通过“面向输电线路巡检的多图像间重复缺陷自动筛查组件”的研发，研究了K-means 聚类算法以及对应的聚类评估指标，根据实验得到了一种准确率高的聚类结果评估方法，能通过means 聚类方法得到初步的聚类结果；研究了三维空间点与二维的缺陷图像区域的映射关系，得到了将具体缺陷区域与聚类中心联系起来的方法，并以此获得最终的缺陷筛查结果，完成了“面向输电线路巡检的多图像间重复缺陷自动筛查组件”的整体流程。

4.2 创新点

（1）采用了K-means 聚类算法作为判断重复缺陷的主要算法，通过将生成的三维交点聚类，得到大致的缺陷数量，并通过反投影将聚类中心反投影至图片，根据反投影的点与缺陷中心距离，得到各图片的缺陷区域与各个聚类之间的联系。并在使用K-means 聚类的基础上，对聚类的结果进行可信度计算，验证聚类的结果，从而选择最可信的聚类结果作为实际结果。

（2）针对计算量较大导致的组件计算时间较长的问题，采用了OpenCL 技术，将大部分计算转至GPU 上运行。在图片和缺陷较多时，运算的时间由1 分多钟优化只需要3 ～5 s，同时其准确率也得到保证，组件的运算效率有了显著提高。