双目视觉空间定位系统中点云目标融合分割算法

彭 凯，饶钰涵，肖艳军，杨泽青

（1.河北工业大学 机械工程学院，天津 300131；2.天津大学 精密仪器与光电子工程学院，天津 300072）

随着工业制造水平的不断发展，传统的二维接触式测量存在大量弊端。三维非接触式点云测量作为机器视觉技术，能够满足当前高速、高产、优质的生产环境[1]。采用双目立体视觉系统生成点云数据的方法，可实现目标对象的远距离定位和测量，且结构简单，成本较低[2]。

将目标物体从点云场景中分割，是保证点云测量结果准确性的关键[3]。现有点云分割算法[4]主要有基于边缘检测方法、基于区域增长分割方法、基于特征聚类方法和基于模型拟合方法。

基于边缘检测方法适用于点云数据密度均匀的情况，而且噪声对分割结果影响较大。Castillo 等人[5]提出这种方法受到噪声和点分布的影响，只能检测到间断的边缘，但对于连续封闭的区域识别效果较差。

基于区域增长分割方法[6,7]最早由Besl 等人[8]在1988 年提出，适用于小目标物体的分割，易产生欠分割现象。由于区域增长的分割方法使用到了全局信息，因此这种方法比边缘检测方法对噪声更具鲁棒性。

基于特征聚类方法[2]适用于特征信息明显的模型[9]，但分割结果严格依赖人工和分割阈值的选择，算法自适应能力较差。2016 年，Lu X 等人[10]提出了一种基于聚类中心点连接的点云分割算法，即P-Linkage 分割。该方法无需自定义参数和阈值，算法自适应能力强同样分割效果较好。

基于模型拟合方法，可以一定程度上减少噪声对于分割结果的影响，1981 年提出的随机采样一致性算法（Random Sample Consensus,RANSAC）成为模型拟合方法的基础模型[11]。

采用单一分割算法普遍存在算法自适应性能差、无法根据环境及时调整，因此可采用多个基础算法融合的方式分步处理，利用多个算法的优势，彼此弥补。杨琳等人[12]将超体素和区域生长分割融合，首先根据法向量信息分割得到超体素点，然后将超体素点作为种子点进行区域生长完成分割。该融合算法有效提高了分割效率，但易受点云分布和规模的影响，且自适应性较差。文献[13]将分水岭和图割算法融合，先利用分水岭算法将图像分割为多个小区域，再对小区域进行图割分割，这种方式提高了分割精准度，但该算法适用于图像分割且未在实际中应用。上述算法存在一定限制，但对点云分割提供了融合算法的新思路。

综上，为了提高精度、节约成本。本文提出一种双目视觉空间定位系统中多层次点云目标物体分割、测量算法。首先通过双目立体视觉系统获取的点云数据进行数据预处理。采用RANSAC 算法检测并去除场景中多余的背景平面，保留目标物体，减少点云数据量。其次基于P-Linkage 算法原理[14]将目标物体聚类分割，使用最小包围盒算法进行测量，获取该场景中几何物体的尺寸信息。最后通过实验将本文非接触测量算法与传统算法进行对比，验证了本文算法在时间成本上有一定优势，且具有较高测量精度。

1 RANSAC 和P-Linkage 融合分割方法

1.1 基于RANSAC 算法的分割

RANSAC 算法作为一种模型拟合类方法，其原理是：首先随机选择一组点云数据作为样本点集，然后结合方差估计形成样本模型，此样本模型也可以由用户自定义。接下来就是计算样本点集内所有样本点值与样本模型的偏差，并让偏差值与用户设定阈值进行比较。将满足阈值范围内的样本点设为内点，不满足即在阈值范围外的样本点设为外点，然后更换模型进行比较，选择包含内点数量最多的模型为最佳拟合模型。图1 为本文设计的基于RANSAC 算法点云分割的具体流程图。

图1 基于RANSAC 算法的点云分割流程图Fig.1 Flow chart of point cloud segmentation based on RANSAC algorithm

使用RANSAC 算法可以在数据特征过多的点云数据中提取满足目的要求的点云特征。若内点占全部数据点的比例为t，计算模型使用的点的个数为n，迭代次数为k，则采集点为正确模型的概率A和迭代次数k的计算公式为：

1.2 P-Linkage 分割

基于聚类中心点连接的分割算法与区域增长分割和特征聚类分割不同的是，P-Linkage 聚类分割方式通过计算三维点云的平面度，并以此作为特征值。通过特征值大小的排列顺序，找到点与点之间的连接关系。通过搜索查询点和邻域连接点的关系，索引类型的聚类。将满足相似条件的聚类合并，并完成点云目标分割。

对于每个数据点，基于 K 近邻（K-Nearest Neighbors,KNN）的方法从点云中选择与其具有最小距离的点的集合作为其邻域并进行分类，此方法通过应用k-d 树等空间划分策略来实现。然后通过主成分分析法（Principal Components Analysis,PCA）估计各个邻域点表面的法线。

通过构建一个k-d 树，对于每个数据点P，找到它最近邻域内的m个点，并将其记录为I。根据P到近邻域点I的距离，将I按升序排列。通过计算协方差矩阵，可以求得各点的法向量、平面度等。每个数据点P的协方差矩阵可表示为：

其中，∑P为数据点P的协方差矩阵；为邻域点集I中前(m/2)个数据点的均值向量。由于数据量过大，且每个数据点的邻域点按升序排列，所以用前(m/2)个数据点表示。结合计算点云表面法向量推导出的结论，可求得数据点P协方差矩阵的特征向量V以及特征向量对应的特征值λ。V的特征向量子集ν2、ν1和ν0根据对应的特征值，按照依次减小的顺序排列，即λ2＞λ1＞λ0。ν2和ν1形成一个正交基，表示最大可变性的两个维度，它定义了I中相邻点的最佳拟合平面，ν0与前两个特征向量形成正交关系，并且近似拟合平面的法线。λ0估计点偏离切面的多少表示该点的平面度，可以用其评价一个平面拟合的质量。λ0越小，平面拟合的质量越好。

找到每个数据点P的最近邻域的m个点I。使用PCA 原理，利用前(m/2)个邻域点I计算数据点P的特征向量。上述计算结果中的特征向量ν0为拟合平面的法线，特征值λ0是估计平面的平面度。通过各点的计算结果与计算阈值R找出各个邻域点I中与P相似的一致集PS。首先，计算数据点P的m个最近邻域点I到其估计拟合平面的正交距离，将其收集为集合。然后，计算中值绝对偏差M与计算阈值R。

其中，median（NOD）是上述距离集合的中值，a为常数。

通过各点的R值与规定阈值进行对比，可以得到与P相似的一致集PS，以及每个数据点P的法向量ν0和平面度λ0，建立点与点之间的成对连接。在相似一致集PS中寻找平面度小于P且法向量与P的偏差最小的点，记做CN(P)。如果相似一致集中有满足CN(P)的点存在，则创建P和CN(P)之间点与点的成对连接，将成对连接点记录到查找表T中。如果P的平面度λ（p）是其邻域点平面度中的最小值，同时平面度λ（p）小于跟随阈值thλ，那么聚类中心可以用P表示，并将其放入点云聚类中心点集C中。跟随阈值thλ的计算公式为：

其中，λ是m个数据点的平面度的平均值；σλ是所有平面度的标准差。

利用找到的成对连接点和聚类中心点集，形成聚类，创建点云的表面切片。首先，从点云聚类中心点集C中选取中心点，并利用查找表T建立点与点之间的连接，查找对应连接点并形成聚类。这些聚类点有直接连接也有间接连接，但由于其有相似的特征属性，因而被归为一类。当某聚类点集中点的个数小于10 时，则将该类点视为异常点并删除。然后，通过合平面为每个聚类建立切面，并选择具有相对最小平面度的面作为最佳拟合面。利用与求数据点特性值相同的方法，求得平面的法向量、平面度和相似一致集，并利用相似于P-Linkage 的方式，将这些切片聚类合并，完成分割。

1.3 融合RANSAC 和P-Linkage 算法的分割

对点云数据进行点云预处理操作[15]，由于三维点云数据包含了丰富的空间信息，所以对点云数据按照数据特征进行结构划分，可以有效地提高算法搜索效率。

RANSAC 算法通过建立的点云模型检测并排除点云异常数据和噪声干扰，能够得到优化的点云模型。因此在本文的融合算法中，首先，使用RANSAC 算法将与原始点云数据的无关平面进行分割去除，如实验台、地面等多余点云环境。然后，利用P-Linkage 算法对剩余点云进行自适应性高的精确分割。该融合算法的优势将在下文实验中，通过与传统欧式聚类分割算法、区域生长分割算法进行对比验证。融合分割算法流程图如图2 所示。

图2 融合分割算法流程图Fig.2 Flow chart of fusion segmentation algorithm

1.4 点云测量

求不规则形状点云数据的最小包围盒。首先，将聚类形成的点云聚类集进行去均值化的数据预处理操作，各个维度的数据减去相应维度上的均值，使每个维度的中心坐标为0，这样可以减小数据量，方便后续计算。然后，建立新的数据空间(a,b,c)来代替原始的三维空间(x,y,z)。原始聚类点云计算生成协方差矩阵，然后通过PCA 主成分降维分析法求得的三个特征向量即为新的数据特征空间的三个方向。

原始聚类点云在新建立的(a,b,c)数据空间坐标系中建立投影，即某方向上最内点和最外点的坐标值。由于点云数据已完成预处理和分割处理，数据可靠性高，离散点少。完成投影后，可通过投影求得三个方向上的最小值和最大值。

求得的六个点可以在(x,y,z)坐标系确定一个包围盒，将8 个求得包围盒坐标逆变换可以得到在(x,y,z)坐标系下的新坐标值以及最小包围盒。

由于OBB（Oriented Bounding Boxes）算法具有方向性，可以生成最贴合点云的包围盒。因此，当点云数据为规则形状，如长方体时，可利用OBB 完全贴合。当点云形状不规则时，可以使用AABB（Axis-Aligned Bounding Boxes）生成包围盒，来近似估计几何物体的尺寸。因此，通过最小包围盒的八点距离的差值可以求出包围盒的长宽高，进而求得聚类点云的长宽高。使用最小包围盒算法对点云进行测量可以将分割出来的目标点云的长、宽、高的尺寸参数化，再与实际物体尺寸进行对比分析，该方法即可以检验各个算法的分割精度又可以对实际物体尺寸进行非接触式测量。

2 实验验证

本文实验以Qt5.14.2 为开发平台，使用VS2019作为编译器。利用OpenCV4.5.1 视觉库处理双目相机采集的图像，通过PCL1.10.1 进行点云数据相关算法设计，并生成用户操作界面，方便用户独立完成点云数据处理的各项操作，实现点云数据读取、处理并保存的完整体系。

2.1 点云分割实验

通过分析随机采样一致性算法、欧式聚类分割算法、区域生长分割算法运行结果原理，明确了各个分割算法的适用情况。为了验证该组合分割算法的理论在工程社会中具备实际应用效果，本实验在工程环境中拍摄了标准工件照片如图3 所示，通过双目空间立体视觉系统生成点云图，如图4 所示。

图3 实际空间环境物体Fig.3 Actual space environment objects

图4 初始点云图Fig.4 Initial point cloud image

图5 为点云数据预处理运行结果，从图中可以发现，点云离散点被滤除，点云数量减少，同时保留原始形状。

图5 点云数据预处理运行结果Fig.5 Result of point cloud data preprocessing

随机采样一致性算法分割结果如图6 所示，该算法只适用于固定模型的分割，检测并剔除场景中的背景平面，保留目标点云数据。后续点云聚类分割的数据源，均使用此结果。

图6 平面分割算法运行结果Fig.6 Result of plane segmentation algorithm

欧式聚类分割算法分割运行结果如图7 所示，在该场景下多个物体相距较远，因此，具有良好的分割效果。聚类分割算法适合于分割间隔较大的物体，且聚类距离需要进行测试。当有多个目标物体且距离较近时，聚类分割无法将目标进行合理分割。

区域生长分割算法运行结果如图8 所示，由于区域生长算法可以根据曲率、法向量等实现不同区域的划分，这种算法严格依赖于种子点的选择以及阈值的设置，自适应能力较差。通过观察分割结果可以发现，正方体物体被分割成为多个区域，产生了过分割的问题。

图8 区域生长分割算法运行结果Fig.8 Results of region growth segmentation algorithm

P-Linkage 分割算法运行结果如图9 所示，由于不需要提前设置参数，该算法的自适应能力较好。而且与区域生长算法分割结果相比较，并没有产生过分割现象。与欧式聚类算法分割结果相比较，该算法也可以把间隔小的物体分割开，适用范围更大。

图9 P-Linkage 分割算法运行结果图9 Results of P-Linkage segmentation algorithm

2.2 点云测量实验

在本次实验中，使用RANSAC 算法分别融合欧式聚类和P-Linkage 分割方式，对数据预处理后的原始点云进行分割，然后用最小包围盒算法对分割的点云目标进行测量。将测量结果与实际测量值进行对比，并计算出每种分割算法的测量误差和相对误差。

Type-A 插口实际测量宽度为8 mm，钢板实际测量长度和宽度分别为120 mm 和90 mm，三通管实际测量长度和宽度分别为140 mm 和100 mm。在多目标场景环境中，正方体边长为20 mm，选择的围棋直径为24.5 mm。

采样相同数据预处理操作后，不同分割算法的测量值、测量误差和相对误差结果，分别如表1-7 所示。表1-7 中分割算法1、2、3 分别为融合RANSAC 与欧式聚类算法、区域生长算法、融合 RANSAC 与P-Linkage 算法。

表1 Type-A 宽度测量结果Tab.1 Type-A width measurement results

表2 钢板长度测量结果Tab.2 Steel plate length measurement results

表3 钢板宽度测量结果Tab.3 Steel plate width measurement results

表4 三通管长度测量结果Tab.4 Tee length measurement results

表5 三通管宽度测量结果Tab.5 Tee width measurement results

表6 多目标物体中正方体边长测量结果Tab.6 Measurement results of cube side length in multi-object object

表7 多目标物体中围棋直径测量结果Tab.7 Measurement results of the diameter of Weiqi in multi-object

分别使用三种分割算法分割上述七类目标物体，并测量。将测量结果的相对误差进行统计，统计结果如表8 所示。物体类别1、2、3、4、5、6、7 分别对应上述几种测量物体。

表8 各类融合分割算法目标物体测量结果的相对误差统计表Tab.8 Statistical table of relative errors of object measurement results in various segmentation algorithms

表8 的相对误差统计结果证明融合RANSAC 与P-Linkage 分割算法的分割精度相较于融合RANSAC与欧式聚类算法和区域生长算法更高。在各种环境下，目标物体尺寸测量相对误差始终保持在3.8%及以下。

为了证明融合使用RANSAC 算法和P-Linkage 分割算法可以提高单一算法效率，分别计算采用单一P-Linkage 算法和融合算法分割上述几种类别物体的算法运行时间，其中Type-A 插口、钢板、三通管、多目标物体分别对应类别A、B、C、D，两种算法的运行时间如表9 所示。

表9 算法运行时间（单位：ms）Tab.9 Algorithm running time (Unit: ms)

从表9 可以看出，使用本文提出的融合分割算法比使用单一P-Linkage 算法运行效率提高1.5～4.4 倍。

3 结论

RANSAC 算法通过拟合模型实现快速场景平面分割，P-Linkage 算法在多种来源的多目标场景空间中能表现出良好的分割效果。本文结合二者优点提出了一种基于双目立体视觉系统的点云多层次融合分割和测量的算法。本算法设计的用户操作界面可以完成点云数据的读取、操作和保存，实现了工业制造的自动化测量。实验结果表明，本文使用的融合分割算法，可以使运行效率提高1.5～4.4 倍，具有精度高和良好的自适应能力，并且可以将物体测量误差稳定在3.8%以下。