改进的RANSAC 点云分割算法及其应用

邹 鹏，李蓓智，龚菊贤，杨建国

（1.东华大学机械工程学院，上海 松江 201620；2.上海航天设备制造有限公司，上海 闵行 200240）

1 引言

工件复杂型面的精确修磨是现代制造最常见的一种技术。三维激光扫描技术是二十世纪九十年代中期发展起来的一项高新技术，激光测量具有准直性好、精度高、测量快速等特点。利用三维扫描仪获取物体表面的三维坐标信息为快速建立物体三维影像模型及精密测量提供了一种全新的技术手段[1]。在点云模型特征提取中点云特征分割是点云数据处理的关键步骤，点云模型分割依据空间结构、纹理特征等对点云进行分类，使得同一区域的点拥有相似的特征[2]。为后续利用点云分割模型确定型面特征几何信息奠定基础。

目前针对点云数据主要分割方法主要有以下几类：区域增长法，聚类分割算法和随机采样一致性（RANSAC）算法等。区域增长算法基本思想是从点云中随机选取一个种子，然后根据点云法向量夹角将种子周围邻域的点云归为一类。该方法但对种子初选位置要求较高，区域增长过程中易受噪声点影响[3]。聚类分割算法是多元统计学方法的一种，将点云数据看作具有一定关联属性的多维度数据集合。按照相同属性对点云数据进行聚类分割。该方法参数设置灵活、鲁棒性好，但存在收敛速度慢效率低[4]。RANSAC 算法能够抑制点云噪声对特征分割的影响，且迭代计算效率较高[5]。但仍然还存在不足之处，对于含有较多干扰点的原始点云数据，每次随机选择初始样本子集易受噪声影响，或者无法找到足够的点支撑样本子集而被抛弃。针对传统RANSAC 算法不足提出了改进的RANSAC，首先对点云数据进行滤波去除离散点，然后利用点云间欧式距离阈值进行粗略分区，最后利用RANSAC 算法对工件型面点云数据进行特征提取，工程运用证明了以上算法的有效性。

2 随机采样一致性算法模型

随机采样一致性算法（RANSAC）最早由Fishier 和Bolles 于1982 年提出[6]，利用随机采样一致性算法分割点云是通过随机取样剔除局外点，构建一个仅由局内点数据组成的点集。其分割原理是：对输入的点云数据随机选取点集计算预设的判别模型参数，计算点集中所有的点到该模型的距离是否在阈值之内，以此作为局内点和局外点判别准则，保存当前模型系数将局内点作为分割结果输出。要求在保证一定置信度下，基本子集最小抽样数M 与至少取得一个良性取样子集的概率P（P＞ε）满足如下关系：

式中：ε—局内点与数据点集的比值；m—计算模型参数需要的最小数据量；P 值一般取值为（0.9～0.99）。

3 改进RANSAC 算法的点云分割

3.1 初始化点云分区

摄影测量、三维激光扫描仪等设备获取的点云数据量庞大、呈现无规律散乱分布，并且点云间无任何几何拓补关系。因此，有必要建立点云间的拓补关系实现海量点云高效组织与管理。八叉树是一种自顶而下逐级划分空间的索引结构[7-8]。利用八叉树结构对点云进行体元剖分，首先依据点云空间模型的最小包络立方体确立八叉树根节点，然后将八叉树根节点沿X、Y、Z 方向进行等分，将立方体剖分为8个小立方体作为根节点的子节点。对所有节点及所包含的点集进行递归细分，直到立方体边长小于规定的阈值时停止剖分[9]。八叉树剖分逻辑图，如图1 所示。通过建立的八叉树数据结构，对点云进行K 邻域搜索，计算每个点与K 邻近点的间欧式距离R，将点距小于预设阈R0值的分为一类，进行点云初步分割。

图1 八叉树剖分图Fig.1 Octree Tree Split Diagram

3.2 分割模型判别准则

主要针对激光扫描获取工件表面点云模型进行平面分割，在同一平面上的点满足如下平面模型参数方程ρ：

式中：点（x，y，z）—点云空间坐标；（A，B，C）—平面单位法向量，且A2+B2+C2=1；D—坐标原点到平面的距离。从原始点云数据中分割型面，实则是求不同点云面片的平面参数。

建立好平面模型参数方程后，判别准则的设计至关重要，这里评定方法为计算点集中P（x，y，z）到平面的距离为：

理论上，局内点到平面的距离为零，但是三维扫描仪获取的点云数据无规则、分布不均匀，并不完全处在同一平面。平面模型是具有一定厚度点云的拟合面片，设定点到平面模型距离阈值为τ。当距离d 小于阈值τ 时称为局内点，反之为局外点。设置合理的阈值对点云平面分割具有重要影响，阈值τ 过大会导致平面分割不完全，阈值τ 过小会导致过度分割。阈值的选取需要根据激光扫描仪精度，采集点云数据空间波动情况合理选取。

3.3 点云分割结果优化

考虑到距离阈值选取会影响分割效果，可能造成位于同一点云面片区域过度分割为多个小区域。为保证表面特征的完整性，需要对分割后的点云进行合并。首先计算两模型平面上点P1、P2的法向量[10]按式（4）计算两平面的夹角，然后按式（5）计算两模型平面的距离，若小于一定阈值θ0就合并两个平面区域。

3.4 改进的算法流程

改进RANSAC 算法的关键环节在于对点云数据集进行平面分割提取时，利用八叉树管理点云数据，然后从点集中提取出含局内点较多的平面，通过不断迭代直至提取出工件所有型面同时利用阈值判断对分割结果进行优化，具体流程，如图2 所示。

图2 改进的点云特征提取流程Fig.2 Improved Point Cloud Feature Extraction Proces

步骤如下：

（1）确定最小抽样数M；

（2）点云八叉树结构建立及距离阈值判别；

（3）利用式（2）确立平面模型参数；

（4）对每个聚类中所有点利用式（3）计算距离d 并与阈值τ进行比较，进行局内点与局外点判别；

（5）重复步骤（2）和步骤（3），选取分割出局内点数最多的点集确定平面模型最优模型参数；

（6）运用式（4）与式（5）计算面片之间的法向夹角与距离，若小于阈值说明为过度分割，需要将这两个面合并为同一平面。

4 点云分割算法实现

4.1 工程应用环境

主要通过对DMG-ecoMill 635v 机床加工的上表面呈阶梯状的铝制工件进行激光点云数据采集，激光扫描设备采用加拿大LMI Gocator2330，每条轮廓包含 1280 数据点，Z 向分辨率（0.006～0.014）mm，视野（47～85）mm。软件开发基于QT 编程平台下，利用PCL 点云库处理点云数据并提取铝块凹槽面。工件样件，如图3所示。工件点云模型，如图4 所示。

图3 待测工件Fig.3 Workpiece to be Tested

图4 工件点云模型Fig.4 Workpiece Point Cloud Model

4.2 点云面片提取

4.2.1 点云滤波与精简

获取的点云数据包含1142183 个点，由于原始点云数据中包含有离群点和噪声且数据量较大需对点云数据进行滤波和数据精简，以提高计算效率和平面提取的精确度[11-12]。首先使用统计滤波方法（StatisticalOutlierRemoval）移除离群点，然后通过体素滤波（VoxelGrid）算法对点云数据进行三维体素栅格滤波[13]。其主要原理是：创建一个三维体素栅格，用每个栅格体素重心替代栅格内其它点，以达到在保证点云形状特征不变的条件下缩减点云数据量。缩减后的点云包含435521 个点，如图5 所示。

图5 点云模型滤波去噪Fig.5 Point Cloud Model Filtering Denoising

4.2.2 面片分割提取

工程应用中，由于激光扫描仪获取的点云点距约为0.042mm，可设置初始点云分区欧式距离阈值R0=0.06mm。随机选取600 个点，点云Z 向坐标波动，如图6 所示。由于受环境光照、信噪等影响，Z 轴最大波动量约为0.1mm，可设置点到平面的距离阈值τ=0.05mm。由于铣床加工工件行成面与面之间的位置关系为平行与垂直，设定θ0=8°，分割出的面与面之间的阈值Δd=0.08mm。

图6 点云平面Z 向波动Fig.6 Point Cloud Plane Z-Direction Fluctuation

工件型面分割结果，如图7 所示。利用这里方法能够成功分离出工件凹槽上表面与下表面，且分割的点云平面质量较好，点云边界辨识度高且噪点少，有利于后续点云边界特征曲线拟合及尺寸计算。工件凹槽几何尺寸测量结果，如表1 所示。

图7 分割后点云型面特征Fig.7 Point Cloud Surface Feature After Segmentation

表1 工件凹槽几何尺寸测量结果Tab.1 Workpiece Groove Geometry Measurement Results

用0 级标准量块对激光扫描仪进行标定可以确定扫描仪的精度为±10μm。通过点云数据获得的槽几何尺寸偏差大约为0.07mm 满足工件加工要求。

5 结论

（1）利用改进的RANSAC 点云平面分割方法，在一定的置信概下能够较好的分割出凹槽上表面与下表面，通过对分离出的点云面片进行法线和距离判定防止点云面片过度分割。

（2）算法设定的条件下对分割的点云平面进行特征尺寸计算，获取的尺寸信息在工件加工误差范围内，说明这里算法处理点云数据精度满足工程应用，验证了算法的有效性。