一种改进的RANSAC算法提取多模型圆弧特征点云

许烨璋，王鑫森，郑德华，谢 波，王春林

（1．河海大学 地球科学与工程学院，江苏 南京 210098；2．天津市勘察院，天津 300191）

目前点云数据的特征提取大多是直接在三维空间中进行的［1］。特征提取算法基本可分为基于边界的算法和基于面域的算法两大类，另外还有综合使用两种方法的混合算法［2］。前者主要是提取点云数据表面形态变化剧烈的点，通常利用法矢、曲率等微分几何变量的突变来提取特征。这种方法对噪声比较敏感，故抗差性较弱。后者主要在于寻找点云数据中具有相同属性的点集，构造出可靠的生长区域进行生长，最终实现分割和特征提取。这类方法主要有RANSAC（随机抽样一致算法）、M估计、最小中值算法、遗传算法和霍夫变换等［3］。这些方法本身具有良好的抗差估计性能，因此在提取特征时能有效抵御噪声。

RANSAC（Rando m Sample Consensus）算法是1981年由Fischler和Bolles［4］最先提出。该方法能够在含有大量粗差点的情况下估计出正确的模型，较经典的最小二乘法具有明显优势。但随着局外点的增多，算法的迭代次数会呈现指数式增长，算法耗时急剧增加。另外RANSAC算法只能实现单个模型的识别。本文提出一种改进的RANSAC算法，能够有效地克服传统RANSAC的不足。

1 扫描线点云特点及其二维化

1．1 扫描线点云特点

扫描线式点云由一组扫描线组成，每条扫描线点云数据是按照扫描仪与激光脚点的仰角大小依次存储的[5]。本文采用的数据为Tri mble GX200三维激光扫描仪采集的扫描线式点云数据，每条扫描线都是扫描光刀平面与目标物体的交线。由于本文所扫描的对象为球体目标，因此所要提取的圆弧特征点云都位于每条扫描线上。同一条扫描线中的扫描点基本共面，对于单独一条扫描线数据，完全可以在二维平面内进行特征点的提取，这样就可以把复杂的三维点云的问题简化到二维平面内处理［6］，故本文以扫描线为单位进行圆弧点云的提取。

1．2 扫描线点云二维化

由于各项误差的存在，每条扫描线上的点云不可能都严格位于各自的光刀平面内，而是以微小的距离分布在光刀平面的两侧。因此将扫描线点云二维化至其对应的光刀平面，首先须根据扫描线点云拟合计算出对应的光刀平面方程式。本文采用特征值法求取平面方程式，具体解求过程不再详述。拟合平面求出后将对应的三维点云投影上去，完成点云的投影。

经过投影后点空间三维点虽已全部位于平面上，但其坐标仍为（Ind，X，Y，Z）（其中Ind为索引值）的三维形式，须将这些点转化为（Ind，X，Y）的二维形式，图1所示为某拟合平面α1内的投影点集（P0，P1，…，Pn）在三维直角坐标系中；图2所示为所要得到的二维坐标。其转换过程为：①以P1点为原点，P1Pn连线的方向矢量为X 轴，以过点P1并垂直于X轴成右手系的向量作为Y轴。②计算其他点Pi到P1点的距离d，以及向量与之间的夹角γ。③根据d和γ，将二维极坐标向二维直角坐标转换，求取Pi点的直角坐标（X，Y）。

图1 投影点的三维表达

图2 投影点的二维表达

2 RANSAC算法的改进

2．1 RANSAC算法原理及其不足

RANSAC算法是通过不断地选择数据集中的一组随机子集来估计待定模型。选取的点集假设为局内点即符合模型的数据点，不符合模型的点称为局外点。每次用选定的随机子集去估计一个待估模型，然后用该模型去测试数据集中其他的点，符合该模型的点归为局内点，当局内点数量达到设定要求时就认为该模型合理，并且将局内点归纳进来重新估算模型。如果局内点数量不够，则认为该模型估算的不正确，此时舍弃原模型，重新在数据集中随机抽取一个子集来估算模型。每次估算的模型要么因为局内点数量充足而重新生长，要么由于局内点数量不足而遭到舍弃［7］。最终以局内点和模型的错误率来评价模型估算的精度。

虽然传统RANSAC算法能从含有大量局外点的数据集中估算出高精度的模型参数，但其迭代次数没有上限。如果设置了迭代上限，可能会导致抽样不充分从而计算出错误的模型，如果不控制迭代次数，便会造成算法效率低下，难以收敛。RANSAC算法的另一个不足是它只能在特定的数据集中估计出一个模型，对于数据集中存在两个或者两个以上的模型，RANSAC不能识别。RANSAC算法输入参数见表1。

表1 RANSAC算法输入参数

设n个点全部为局内点的概率为P，点集的总点数为N，所有局外点数为Nt，则随机选取一个点为局外点的概率为W ，且W ＝Nt／N。n个点全部为局内点的概率又可以表示为（1－W）n，1－（1－W）n表示n个点中至少有一个为局外点的概率，则（1－（1－W）n）k表示永远都取不到n个点全部都为局内点的概率，它应该和1－P相等，即1－P＝（1－（1－W）n）k，对两边取对数即可得出迭代时取略大于k的值即可。

由式（1）可以看出，在n和P固定的情况下，局外点率W 越大，迭代次数k也就越大，算法效率越低下。因此为了减少迭代次数，提高算法效率，就必须降低局外点所占的比例并且根据每次数据的调整对k值进行自适应调整。

2．2 局外点的预剔除

本文提取的圆弧点云为球面圆弧点云，为扫描光刀平面在球面上截取的圆，其直径必然小于或等于球直径（球面被光刀面所截的圆截面中，通过球直径的截面最大），因此那些直径大于球直径的数据点即可认为局外点。利用这一特性本文以相邻的3个点为一组遍历整条扫描线，计算每组数据对应圆的直径，将直径大于设定阈值的数据剔除，从而达到降低外点率的目的。图3为局外点剔除示意图。

图3 局外点剔除示意图

2．3 k值的自适应调整

随着迭代次数的增加，内点被不断地增加到估算模型的点集中来，即在迭代过程中内点率不断增加，相应的外点率在不断减小，则根据式（1）迭代次数k值也在随之减小。本文算法在开始计算时将k值设置为一个较大的值，然后在每次迭代时根据外点率重新计算k的值使其趋于一个合理的值完成迭代。为了验证k值自适应调整的效果，事先针对迭代次数k值做了一组测试。将k的初始值设为14 000，开始计算后每隔10 s记录一次k值，从图4可以看出k值在前40 s中数值下降显著，最终在第90 s处自适应停止，稳定到55 s左右，表明本文的自适应处理能够取到良好的效果。

图4 k值自适应变化过程

2．4 多模型识别的改进

上文提到RANSAC算法的另一大不足就是只能对待估点集中的一个模型进行识别，对包含两个及其以上的模型就无法适用。为解决这一问题，本文采用分次识别的方法，即将第一次识别出的模型所对应的点集剔除出二维点集后再进行下一个模型的识别，按照这种流程直到满足某种条件为止。

综合以上3点改进，本文改进的RANSAC算法提取圆弧点的算法步骤如下：

1）选定一组已经二维化后的扫描线点集｛P1，P2，…，Pn｝，将相邻的3个｛Pi，Pi＋1，Pi＋2｜i∈ ［1，n－2］｝计算构成圆的半径值r，按顺序无重复地遍历点集。

2）将半径值r∈ ［R1，R2］对应的点保留，将超过r阈值范围的对应点集剔除，构成新的点集｛Q1，Q2，…，Qm｝。

3）将迭代次数k设置为一个足够大的数值，随机抽取一个包含3个点的样本，计算其模型参数Modelk，即圆心坐标及半径 （xo，yo，r）k。

4）再次检验样本点计算的r值是否符合r∈［R1，R2］，若是，则进入下一步，否则退出本次循环，转回到3）。

5）遍历点集｛Q1，Q2，…，Qm｝，判断每加入一个点后圆拟合余差σ0是否符合阈值来找出所有符合本模型的点，并判断内点数是否达到设定的阈值Nu m，若达到则记录本模型参数Modelk，σ0和对应的内点集Inliersk，并根据式（1）计算新的外点率W和对应的新的迭代次数k，其中N取点集｛Q1，Q2，…，Qm｝的个数。

6）重复迭代过程3）～5），以内点数更多的模型Modelk＋1作为更好的模型替换上一个模型Modelk，最终得到一个置信概率下的模型并保存相应内点点集。

7）将6）中得到的模型对应的内点从点集｛Q1，Q2，…，Qm｝中剔除，重复3）～6）完成下一模型选取。

3 实验分析

实验选取3个排列在一起大小不等的3个球体，采用Tri mble GX200型扫描仪进行扫描，经过去噪等简单处理后得到16 230个数据点，134个切片。图5所示为扫描点云。

分别用RANSAC算法和本文改进的RANSAC算法提取其中的圆弧点。对RANSAC算法中迭代次数k分别取4个不同的值进行测试，由于3个扫描球体的半径最大为200 mm，最小为41 mm，考虑到一定的容差，将预剔除阈值设置为10～500 mm，超过此范围的点作为外点剔除掉。经过多次实验，两种算法中模型拟合余差σ0取0．8 mm，最小内点数Nu m取8。最终本实验共提取圆弧总数319条，以41号切片数据为例，包含数据点109个，实际圆弧数为3条。本文改进的RANSAC算法所提取的圆弧如图6所示，两种算法效果对比见表2。

图5 扫描点云

图6 本文算法提取的41号圆弧点云

表2 41号扫描线的计算结果对比

从表2和图6可以看出，传统的RANSAC算法当迭代次数k分别取较小值500，2 000，8 000时，算法最终的拟合结果为失败、错误和遗漏。这就充分证明了对于传统RANSAC算法，迭代次数如果设置得太小就无法估算出模型。当k值增加到较大值12 000时，传统算法仅能够识别出1条圆弧并且耗时较大。这充分显示了传统RANSAC算法计算效率低下且仅能估计单一模型的缺点。本文改进的RANSAC算法不仅将3条圆弧点云有效提取，而且每条圆弧提取的k值最终都以一个较小的值固定下来，算法耗时为最少。

4 结束语

本文利用了扫描线式点云数据的特点，先以扫描线为单位将三维点云进行二维化处理，降低了数据处理的复杂度。在分析传统RANSAC的基础上，针对球面圆弧点云数据的特点，提出了改进的RANSAC算法的流程，对局外点进行的预剔除，从总体上降低了迭代次数。对迭代次数进行的自适应调整使迭代次数能够根据数据的变化及时调整到合理的较小值。分次识别法则实现了多个圆弧模型的提取。实验证明，本文改进的RANSAC算法能够有效克服传统RANSAC算法的不足，为复杂场景下多模型特征点云的提取提供了一种思路。但本文处理的点云数据仅为扫描线式，所提取的模型也仅仅是圆弧模型，对于其他格式的点云数据和其他性质模型的提取还有待进一步研究。

［1］ WEINKAUF T，GNT HER D．Separatrix persistence：Extraction of salient edges on surfaces using topological met hods［M］．Co mputer Graphics，2009．

［2］ 潘国荣，秦世伟，蔡润彬，等．三维激光扫描拟合平面自动提取算法［J］．同济大学学报：自然科学版，2009，37（9）：1250－1255．

［3］ 赵伟玲．三维点云的数据预处理和圆提取算法研究［D］．哈尔滨：哈尔滨工程大学，2008．

［4］ FISCHLER M A，BOLLES R C．Random sample consensus：a paradig m for model fitting wit h applications to i mage analysis and automated cartography［J］．Grap hics and Image Processing，1981，24（6）：381－395．

［5］ 郭杰，刘建永，张有亮，等．基于扫描线自适应角度限差法的地面点云滤波［J］．计算机应用，2011，31（8）：2243－2245．

［6］ 潘国荣，谷川，王穗辉，等．三维激光扫描拟合直线自动提取算法研究［J］．大地测量与地球动力学，2009，29（1）：57－63．

［7］ 蔡润彬．地面激光扫描数据后处理若干关键技术研究［D］．上海：同济大学，2008．