基于改进欧式聚类的工件分割方法

姜立豪，刘星桥，李长峰，陈 辉，马 腾，赵德安

（1.江苏大学 电气信息工程学院，江苏 镇江 212013；2.常州铭赛机器人科技股份有限公司，江苏 常州 213164）

0 引言

目前，线激光三维测量技术［1-2］广泛应用于非接触式工业测量领域，具有测量精度高、速度快，能适应各种复杂工业环境等优点。点云分割技术［3］有助于进一步分析场景，例如定位、识别、分类物体或特征提取等。

常用的分割方法包括基于边缘、基于区域增长、基于模型拟合和基于聚类4 种，其中聚类分割应用最广泛。刘继忠等［4］利用物体的对称性优化聚类分割，并通过生活场景进行验证，得到了更完整的分割结果。

欧式聚类在速度和效果方面均具有不错的表现，但距离阈值难以确定，通常会导致欠分割和过分割问题。Rodrí-guez 等［5］对城市街区进行分类，提出一种新的基于自适应欧式距离和城市块距离的区间值数据分区聚类算法，通过在子空间中识别不同形状、大小的聚类来优化全局聚类。田青华等［6］利用工件形态的确定性，将单个工件离线检测的数据转化为特征，作为自适应确定欧式聚类阈值的参考。火统乐［7］通过研究非接触边缘点的几何特征，提出基于点云区域特征的非接触边缘点判定方法，在去除接触边缘点的基础上避免了分割现象发生。王瑞丰等［8］在判据中加入超像素的法向量夹角信息，以改进局部凸连接生长算法的欠分割问题。黄际玮等［9］以小型电容为研究对象，通过欧式聚类结合区域生长，改善了传统欧式聚类欠分割的问题。李仁忠等［10］以最小曲率为种子点，加入基于局部特征的生长准则，解决了传统区域生长分割不稳定的问题。宋柱等［11］提出一种分区、有噪声的基于密度的聚类方法（DBSCAN）聚类算法，解决了密度变化导致行人检测准确率较低的问题。蔡怀宇等［12］根据目标距离调整DBSCAN 算法的距离阈值，对不同距离物体的聚类效果良好。此外，三维点云神经网络分割法［13-15］对点云具有较高的分割精度和自适应能力，但需要预先进行一定量的训练，在没有足够多样本的情况下无法顺利实现。

虽然，欧式聚类在大多数场景下效果较好，但在特殊场景下需根据各自场景特点，改进欧式聚类才能取得较好的效果。本文研究多个摄像模组场景的点云分割发现，此类场景工件内部面与面的交界处密度较低，且工件摆放空间有限，容易相互靠近。针对欧式聚类在点云密度不均匀时或工件相距较近时表现不佳的问题，提出一种基于相邻工件区域识别的改进欧式聚类分割方法，该方法在分割环节中解决了上述问题，为后续检测工件缺陷奠定了良好基础。主要工作为：①滤波采集的点云，获得去噪后的感兴趣区域；②研究两类相邻工件的点云分布特征识别算法；③改进欧式聚类，根据目标区域识别结果自适应确定目标区域的聚类方法。

1 基本原理

基于改进欧式聚类的相邻工件点云分割方法的流程包括点云预处理和改进欧式聚类分割，如图1所示。

Fig.1 Algorithm flow图1 算法流程

1.1 点云预处理

图2（b）为使用线扫相机得到的含有较多噪声的点云图，需要先采用直通滤波［16］进行去噪处理，才能得到可用于检测缺陷的工件表面，如图2（c）所示。直通滤波是一种简单的滤波器，能对某个指定维度实行滤波，即去掉指定范围内的点。为了对后续的改进欧式聚类作数据准备，采用K 维树（k-tree）邻近点搜索算法［17］建立三维点云空间中的拓扑关系，并利用主成分分析法［18］以邻近数量kn为尺度，求得每个点的法向量。

Fig.2 Preprocessing results图2 预处理结果

1.2 改进欧式聚类分割

1.2.1 相邻工件区域识别算法

当欧式聚类时的搜索区域同时包含不同工件的点，此时区域为相邻工件区域。本文算法通过识别相邻工件区域的激光点分布特征，以正确判定欧式聚类的搜索区域是否属于工件相邻区域。本文以平面二维点为例，对两种不同分布特征的相邻工件区域识别算法的主要思想和步骤进行说明。

（1）相邻工件区域1。相邻工件区域存在明显离群点（见图3（a）），在搜索区域内的分布特征如图3（b）所示，在A 工件的边缘搜索时，由于搜索半径过大将导致B 类边缘也进入搜索范围，离群点判定的具体步骤如下：

Fig.3 Adjacent workpiece area 1图3 相邻工件区域1

步骤1：计算搜索区域的内点中心以判断搜索更倾向哪个目标，如图3（c）所示。求解搜索范围内点的坐标的质点，越接近搜索中心点的占比越大。内点中心C的计算公式为：

式中：C.x、C.y为内点中心C的x轴、y轴坐标；D(pi，p0)为搜索范围内点到搜索中心的距离；n为搜索范围内点的数量；p0.x、p0.y为搜索中心的x轴、y轴坐标；pi.x、pi.y为搜索范围内点的x轴、y轴坐标。

步骤2：为了表示区域内每点距内点中心的偏移程度，求解每个点的离群值L。

式中：r为搜索区域R的半径；Lth为离群值的阈值，当某点L≥Lth时，判定该点为离群点。

步骤3：由于工件内部两个面的交界处同样存在离群点（见图4（a）），搜索区域A 为工件A 两个面的交界处，搜索区域B 为两工件相邻区域（见图4（b））。为了防止内部的高曲率区域被判定为离群点，导致欠分割现象发生，本文利用搜索中心和离群点的法向量夹角对算法判定进行约束，如图4（c）所示。

Fig.4 Constraint for determining the angle between normal vectors图4 法向量夹角判定约束

由于区域A 的法向量夹角远大于区域B，可通过夹角阈值θth区分工件边缘和内部交界处，当θ≤θth时判定为相邻工件区域1。具体计算公式为：

式中：n0为搜索中心的法向量；nlj(j=1，2，…，m)为离群点的法向量分别；m为区域内离群点的个数。

（2）相邻工件区域2。相邻工件区域存在噪点和两块不相连的高密度区域（见图5（a）），在搜索区域内的分布特征如图5（b）所示。

Fig.5 Adjacent workpiece area 2图5 相邻工件区域2

由于工件距离过近，间隙中可能会产生噪点，当两块工件边缘的密度较高时噪点密度较低，此时离群点判定可能无法适用。考虑到DBSCAN 复杂度较高，当离群点判定算法无法识别噪点时，引入DBSCAN 算法根据密度对点云进行聚类，以此识别分布特征。密度聚类的具体步骤如下：

步骤1：初始化密度聚类阈值e、nth。

步骤2：选取搜索区域R内一点p，以参数e进行半径搜索，若n≥nth，将搜索到的点归入集合Q。

步骤3：在集合Q中选取p以外的点重复步骤2，直至Q不在满足条件，保存Q作为相邻工件区域1 类的高密度点并清空。

步骤4：在剩余点中重复步骤2、3。

如图5（c）所示，密度聚类去除了低密度点云，得到了不同类别不相连的高密度点云，若个数不少于2，则判定为相邻工件区域2。一旦出现如图5（d）所示情况，搜索区域R将属于相邻工件区域，由于范围限制只存在局部信息，只计算相邻工件区域1 的高密度点，因此考虑扩展搜索区域以获得足够多的尺度判别特征。当搜索区域R经过密度聚类后只存在相邻工件区域1 类的高密度点时，扩展搜索区域的步骤如下：

步骤1：分别求得高密度点云质心hc、低密度点云lc。

步骤2：作hc对lc的对称点kc，并对kc进行半径为R的邻近搜索，与区域R合并得到搜索区域Rex（见图5（e））。扩展完成后，对搜索区域Rex进行密度聚类，获得正确结果。

1.2.2 基于相邻工件区域识别算法的欧式聚类分割

图6 为使用传统欧式聚类方法产生的欠分割和过分割现象。

Fig.6 Results of traditional Euclidean clustering with different distance thresholds图6 不同距离阈值下传统欧式聚类结果

为此，本文对欧式聚类分割进行改进，具体思路为：在点云欧式聚类过程中，使用K 邻近点确定足够大的搜索半径，防止过分割现象发生；为了使相邻工件区域能被正确分割，对每次迭代产生的搜索区域，通过判定相邻工件区域的种类来执行不同的聚类方案。当识别为相邻工件区域1 时，对搜索中心点选择较小的搜索半径并聚类；当识别为相邻工件区域2 时，聚合经DBSCAN 分割后搜索中心所在的类。具体步骤如下：

步骤1：对输入点云Pin建立k-tree 索引。

步骤2：创建点云索引向量S存储聚类结果，创建点云索引向量Sdbscan存储欠分割点云，创建整型向量q存储单次聚类结果；新建一个bool 型向量Pprocessed与点云Pin大小数量相同，以记录点云是否被处理过。

步骤3：初始化i=0、最小聚类数nmin、最大聚类数nmax，对pi∈Pin执行以下步骤。

步骤3.1：初始化c=0，将pi的索引放入q，Pprocessed[i]=ture，代表该点已处理。

步骤3.2：取队列q中的第c个位置储存点索引，此点在Pin中对于Pc。在k-tree 中，对此点进行k近邻搜索得到搜索区域R，将其中k个点放入向量qindice_k，距中心点的距离放入向量qdistence_k。对qindece_k的点云，通过相邻工件区域1的识别算法判定区域R是否为工件相邻区域，若判定成功则自适应搜索半径表示为：

反之，自适应搜索半径表示为：

步骤3.3：根据Rada将点Pc半径近邻搜索得到索引放入向量qindece_k，对每一个索引若Pprocessed[qindice_k[i]]=false，将qindice_k[i]放入q并标记为已分类，c=c+1。重复步骤3.2、3.3，直至q中所有点都已分类。q的索引数为nq，若nq≤nmin则舍弃并清空队列；若nq≥nmax，将其复制到Sdbscan并清空队列；若nmin＜n＜nmax，将q推入S，i=i+1。

步骤4：重复步骤3，直至Pin中所有点已被处理。

步骤5：创建一个整型向量qdbscan并初始化为空，将Sdbscan中的每组点云索引保存为nm组点云的输出，记作Cdbm，m=1，2，…，nm。

步骤6：初始化i=0、m=1、数组q，对pi∈Cdbm执行以下步骤。

步骤6.1：初始化d=0，将pi的索引放入qdbscan，Pprocessed[i]=ture，标记该点已处理。

步骤6.2：取队列qdbscan中第d个位置储存的点索引，此点在Cdbm中对应于Pd。在k-tree 中，对此点进行kdb近邻搜索，得到搜索区域R，将其中kdb个点放入向量q中，根据密度聚类算法聚类区域R，获得聚类个数mdb，并将高密度点云聚类结果放入向量qdbcluster。

步骤6.3：若Pd在qdbcluster中，将qdbcluster保留含有Pd的相邻工件区域1 的点云，并放入向量qindice_k。反之，判断聚类个数mdb，若mdb=1，获得扩展后的搜索区域Rex。对区域Rex进行密度聚类得到聚类个数mdb′，当mdb′＞1 时清空qindice_k；若mdb＞1 清空qindice_k。对每一个索引，若Pprocessed[qindice_k[i]]=false，将qindice_k放入qdbscan并标记为已分类，d=d+1。

步骤6.4：重复步骤6.2、6.3，直至qdbscan中所有点已分类，将qdbscan推入S，i=i+1。

步骤7：重复步骤6，直至Cdbm中所有点均已处理，m=m+1。

步骤8：重复步骤7，直至m＞nm代表欧式聚类完成，将S中每组点云索引保存成z个工件点云进行输出，记作{P1，P2，…，Pz}。

2 实验结果与分析

2.1 工件点云分割结果

为验证分割算法的有效性，本文以一组摄像头模组工件为实验对象，由于相机视野受限，需要靠近摆放才能容下更多工件。实验PC 机为64 位的Windows 11 操作系统，CPU 为Intel（R）Core（TM）i7-7950 2.6 GHz，内存为16 GB，平台为64 位的VS 2019，编程语言为C++，涉及库文件为点云库PCL1.11.0。预处理后的点云如图7（a）所示，然后按照多组工件点云分割方法进行分割，相关参数阈值如表1所示。

Table 1 Related parameter thresholds表1 相关参数阈值

Fig.7 Recognition and classification results using different algorithms图7 不同算法识别分类结果

图7（彩图扫OSID 可见，下同）中每种颜色代表不同的类别。图7（b）中相邻工件区域1 判定后的结果依然存在欠分割现象，图7（c）为单独提取出的欠分割部分，图7（d）为对剩下欠分割部分进行相邻工件区域2 判别所得到的聚类结果，图7（e）为最终分割结果。

对相同点云进行预处理操作后，设置距离阈值r=0.4进行欧式聚类、曲率阈值为0.1 进行区域生长聚类、凹面阈值为10 和平滑阈值为0.1 进行局部凸连接生长算法获得的结果分别为图7（f）、图7（g）、图7（h）所示。

为定量分析各种方法的分割效果，将分割情况统计汇总为表2。其中，Ideal result 表示理想情况下的分割效果，得到的点数为nideal；ninliers表示实际分割部分与理想分割的交集点数；noutliers表示实际分割不在理想分割的部分点数。

Table 2 Statistics of segmentation results of four methods for single group workpiece point cloud表2 单组工件点云的4种方法的分割结果统计

2.2 多组工件点云分割

为进一步验证本文分割算法的有效性，进行多次重复实验。实验对象分别为塑料和金属材质的摄像模组，每种对象获取3组不同场景下的三维点云数据，实验结果如表3 所示。其中，2 种实验对象分别对应目标1、2，通过A/B/C/D 形式的数据记录4种分割方法的结果，A 为欧氏聚类分割结果，B 为区域生长分割，C 为局部凸连接生长算法，D为本文算法。

Table 3 Comparison of segmentation effect of four methods for multiple groups workpiece point cloud表3 多组工件点云4种方法的分割效果比较

在目标数量相同的条件下，分别记录4 种算法正确分割的子集个数、分割正确率AP 和交并比（IoU），用于分析算法性能。当某个目标交并比大于95%时，判断为正确分割，IoU 计算公式为：

为了更直观地展现实验结果，图8 给出2 种实验对象在场景2中，通过不同算法输出的图像。

Fig.8 Classification result of two experimental objects using different algorithms in scenario 2图8 两种实验对象在场景2下不同算法的分类结果

2.3 实验结果

从定性角度而言，对于一些贴合不紧密的工件，使用传统欧式聚类就能得到较好的分割精度，例如第二种工件的第1、2、3、4、7、8 个工件（见图7（a）），5、6、9、10 个工件在欧式聚类时存在工件粘连现象，使用局部凸连接生长算法虽然避免了该问题，但工件完整性较差。本文分割方法在工件靠近时，能避免粘连现象且工件完整性较好。从定量角度而言，本文方法的正确率、稳定性相较于其他3 种方法更优。

3 结语

本文算法较好地解决了在摄像模组场景下，工件分割发生的欠分割和过分割问题。在两种摄像模组的多场景实验中，本文方法均未出现因工件密度变化而引起过分割，或因多工件靠近引起欠分割现象。

结果表明，本文算法能准确分割单个工件，精确度高于95%，相较于欧式聚类算法、区域生长算法、局部凸连接生长算法分别提升54%、41%、33%。