一种新的扫描点云自动配准方法

钱鹏鹏,郑德华

(河海大学大地测量与测绘工程学院,江苏南京210098)

数据配准是将两个或者两个以上的坐标系中的大量三维空间数据点转换到统一的坐标系中的数学计算过程。随着三维激光扫描技术的发展,点云数据配准也显得尤为重要。其中基于同名特征和同名点的配准是点云配准的重要方式。最为经典的是Besl提出的ICP算法[1-2],但是它对点云的包含关系和初始位置有相当高的要求。在这个基础上,朱延鹃等提出了一种根据曲率和几何哈希的初始配准算法[3],薛耀红等根据曲率和点的邻域相似度进行初始配准[4],张梅等利用离散特征对点云进行初始配准[5]。类似的方法较多,但是在配准的精度和速度上有待于进一步的提高。本文的主要思路是使用参数二次曲面拟合的方法计算点的曲率、法向量和主方向向量,根据曲率相近点构成系列点对。在这些点对中运用RANSAC算法进行采样,在给定阈值范围内寻找特征点进行配准。将粗配准的两个新的点云位置再运用ICP算法实现精确配准。实验证明,通过曲率的随机采样一致性算法能够为ICP算法提供良好的初始配准点云,有效的提高点云配准的速度和精度。

1 RANSAC算法

RANSAC最初由Fischler提出,是一种抽样一致算法,它可以用来处理包含大量外点的数据集。RANSAC算法的主要思想是:利用最小的采样集来估计模型的参数,在估计参数下选择数据集中的点来扩大初始的采样集。通过迭代得到最大一致性的数据集。利用这个最大一致性数据集,重新进行模型参数估计[6]。

假设我们需要将原始数据集S配准到目标数据集T下,则RANSAC配准算法的思想可以如下描述:

(1)从S中抽取不共线的三点{S1,S2,S3},在目标数据集中搜索到对应点{T1,T2,T3};

(2)利用这三对点进行欧式变换矩阵的估计Hc;

(3)计算在Hc和误差阈值δ下,源数据集S和目标数据集T之间的一致程度;

(4)迭代K次,找出S和T对应一致程度最大的H。

通过迭代找出欧式变换矩阵H,从而完成源数据集到目标数据集的配准。迭代次数K是关系配准给过的关键参数,K值过大,配准的速度就会变慢,K值过小,就很难取得好的样本。通过抽样统计的计算,得到K最佳选值为。其中 p为K次抽样样本,w为期望值。误差阈值的选取也是配准的重要环节,根据误差分布的经验公式可以计算出误差阈值δ为其中η为误差向量,α为内点被接受的概率。但是,在实际应用的过程中,无法知道源数据集到目标数据集的误差距离概率分布,阈值 δ通常是通过经验来选取的[7]。

2 初次配准

2.1 曲率相似度构造点对数组

根据该公式给出的相似度度量规定,可以找出S1、S2中曲率相似的所有点对。在处理过程中应保证主曲率方向的一致性。

2.2 RANSAC算法优化点对数组

找出主曲率方向一致的对应点之后,由于数据量大,并不适合直接用来配准。RANSAC算法可以有效的对通过曲率相似度得到的点对数据进行重新采样,与曲率有效结合来进行初始配准。在得到曲率信息以后,利用RANSAC算法对曲率相似的特征点进行筛选,多次筛选后得到有效的,数据量较小的点对数据。本文使用RANSAN即随机采样一致性算法对找出的点对再进行采样。经过处理的点云数据明显变小,缩短了后续配准的时间。用RANSAC配准的鲁棒性较高,处理的过程中配准点云的精度可以得到保证。在RANSAC进行采样的过程中,需要考虑的问题是如果满足采样率、重叠比例和处理时间之间的关系。该算法的基本过程见图1。

图1 RANSABC算法的主要思路

3 二次配准

二次配准采用改进的 ICP算法。在初次配准后,点云的数据量已经大幅的减少,点数的位置也是非常接近了。这就给ICP配准创造了非常有利的条件。ICP配准的实质是最小二乘方法的最优化配准,本文使用的ICP算法步骤如下:

(1)利用法向空间在数据集中对数据进行重采样;

(2)根据统一的权值在目标集中进行匹配点的选择;

(3)根据一定的比例结合阈值来剔除匹配错误的点对;

(4)依据两个点对的距离平方和来选择误差度量函数;

(5)利用四元数法进行最小化。

为了避免出现大量匹配点,点对匹配采用法向投影匹配。权值采用比较简单的同一权值是因为它对点云配准收敛的速度影响较小,而选取阈值可以剔除相近的数据集[8-10]。

4 实验与分析

本文对斯坦福大学网站提供的bunny模型进行了实验,如图2所示。图2(1)、图2(2)分别为 bunny 0°和45°角的点云数据,图2(3)为初次配准的结果,图2(4)为经过ICP算法11次迭代后的数据效果。本文初次配准的效果良好,但是在某些地方还是出现了不重合,经过二次配准,不重合的地方基本消除。初始配准的误差为2.090942,经过二次配准后的误差为0.2070813。初始配准分为曲率的计算、RANSAC采样和配准三个部分,当RANSAC算法找到的对应同名特征点数目趋于稳定时,迭代终止,时间为98.703 s。经过初始配准后的两个点云数据精细配准的时间为17.524 s,迭代次数11次。实验结果见表1。

图2 bunny模型点云数据配准过程

表1 Bunny模型配准时间

为了验证本算法的可靠性,本文接着对河海大学徐芝纶像雕塑的点云数据进行了实验。采用了分别从0°和45°采集的点云数据配准。如图3所示图3(1)、图3(2)为两个角度的点云数据,图3(3)为经过初次配准的点云,图3(4)为经过二次配准后的点云。点云数据的初始配准误差为2.131749,经过了ICP算法11次迭代后,精细配准误差为0.28541203。初始点云数据通过曲率计算,RANSAC采样和配准,当RANSAC算法找到的对应同名特征点数目趋于稳定时,迭代终止,所用时间为95.387 s。二次配准所用时间为16.342 s。ICP迭代次数11次,配准效果如图3所示,配准效果基本令人满意。实验结果见表2。

图3 某雕塑模型的数据配准过程

表2 雕塑模型配准时间

5 结 论

点云数据配准是三维建模的重要步骤,配准中如何将点云数据快速有效的配准是研究的重点。本文在总结基于曲率配准各种文献算法的基础上,提出结合曲率和RANSAC的点云数据配准方法。

(1)验证了这种方法在点云配准过程中的正确性和有效性,通过曲率和随机采样一致性算法的结合,避免了ICP的算法的缺点,为ICP算法提供了有效的初始点云数据。

(2)本文为点云数据配准提供了一个新的思考方向。在配准过程中,RANSAC算法阈值的选取,如何更好的处理对曲率特征的采样都可以进一步研究。

[1]Besl P J,Mckay N D.A method for registration of 3-D shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239-256.

[2]Chen Y,Medioni G.Object modeling by registration of multiple range images[J].Image and Vision Computing,1992,10(3):145-155.

[3]朱延鹃,周来水,张丽艳.散乱点云数据配准算法[J].计算机辅助设计与图形学报,2006,18(4):475-481.

[4]张 梅,文静华,张祖勋,等.基于欧氏距离测度的激光点云配准[J].测绘科学,2010,35(3):5-8.

[5]薛耀红.点云数据配准及曲面细分技术[M].北京:国防工业出版社,2010:24-30.

[6]袁 亮.三维重建过程中的点云数据配准算法的研究[D].西安:西安电子科技大学,2010:20-26.

[7]陈 楚.基于激光扫描的深度影像配准方法研究[D].武汉:武汉大学,15-23.

[8]郑德华.ICP算法及其在建筑物扫描点云数据配准中的应用[J].测绘工程,2007,32(2):31-32.

[9]李万逵.激光扫描在阿尔塔什右岸高边坡稳定性分析中的应用[J].水利与建筑工程学报,2011,9(2):66-72.

[10]潘建刚.基于激光扫描仪数据的三维重建关键技术研究[D].北京:首都师范大学,2005:22-23.