改进ICP算法的点云配准

邱世聪 罗意

（江西理工大学建筑与测绘工程学院，江西赣州 341000）

改进ICP算法的点云配准

邱世聪 罗意

（江西理工大学建筑与测绘工程学院，江西赣州 341000）

针对传统ICP算法所存在的对初始点云位置要求高、算法效率低等局限性，本文对算法进行研究改进，改进结合K-近邻搜索和法向量估计，采用组建不变角度作为不变特征求解旋转矩阵和平移向量实现初配准，利用基于八叉树的ICP算法进行精配准。研究表明，改进算法能提高配准精度，缩短配准时间，优势明显。

点云配准；法向量估计；不变特征；ICP算法；八叉树

三维激光扫描技术是目前用于测绘学科的一项高新技术，该技术具有非接触性、快速性、实时获取的数据具有精度高等特点，因此被广泛应用于文物保护、数字城市、变形监测、逆向工程等领域［1-3］。由于实际测量工作中常常受三维激光扫描仪自身、扫描目标的复杂程度及周围环境的影响，需要进行多次设站扫描以获得完整的数据，由于不同测站扫描的点云数据所在的坐标系统不同，因此需要对不同测站的点云数据进行配准，即将不同坐标系的点云数据转换到相同的坐标系下以获得同一基准［4］。

目前，国内外的学者在点云配准方面做了许多研究，由Besl等提出的迭代最近点算法（Iterative Closest Points，ICP）应用最为广泛，许多学者也对此算法做出了不同的改进［5-7］。最近点迭代算法本质上是基于最小二乘法的最优匹配算法，算法重复进行确定对应点集解算出最优刚体变换，直到满足某个表示正确匹配的收敛准则［8］。ICP算法存在的局限性主要有两方面：①该算法要求2个点集有较好的相对初始位置以避免陷入局部最优解［9］；②搜寻匹配点对的时间较长［10］。

本文基于上述ICP算法存在的不足，提出了一种改进算法，此算法主要进行以下两方面的改进：①根据ICP算法对点云初始位置的要求，避免陷入局部最优解，结合K-近邻搜索和法向量估计，通过构造不变角度作为不变特征求解旋转矩阵和平移向量对点云进行初始配准；②针对ICP算法处理工作量大及搜索效率低下等缺点，通过求取内点点集来减少搜索工作量，同时利用Octree结构来加快点云配准的搜索速率，并利用配准点云中点对的距离关系剔除错误点，以提高配准精度。

1 改进的点云配准算法

1.1 点云初始配准

ICP算法是逼近迭代算法，需要两点集有较大范围的重合区域，以满足精确配准的收敛精度要求。实际测量过程中获得的两视角点云由于目标物体的复杂程度、扫

本文通过局部表面拟合的方法估计法向量［8］。在点云表面处处光滑的情况下，可以用平面很好地拟合出任意点的局部邻域，因此，对扫描点云数据中的任意点p，当搜索到距离点P最近的K个邻近点，然后解算出K个邻近点的局部平面P。对点云数据中的任意一点p进行法向量估计等价于对点p与其K个邻近点拟合成的局部平面P的切平面进行法向量的求解。本文通过邻域协方差分析法求得点云数据中各个点的法向量。原理如下：

任意一点P与其K近邻域点得到协方差阵：

式（1）中，p0为K近邻域的质心，点P的法向量为协方差矩阵CV最小特征值对应的特征向量。

1.2 点云的精确配准

按照上述方法进行初配准后，两点云已经大致取得了良好的配准位置，但是还需要进行精确配准，以达到点云配准的精度要求。鉴于初配准已得到较好的结果，为进一步提高配准精度，对于目标点集中的点pi以及其在参考点集中的最近点qj设定一个阈值δ，若dist（pi，qj）＜δ，即两点之间的距离小于阈值，则将pi作为内点，否则认为其降低配准精度而作为外点去除，用得到的内点点集计算配准参数。首次迭代时将初始配准的误差值设定为阈值δ，首次迭代后的配准误差值作为第2次迭代的阈值δ，之后上一次迭代后的配准误差值作为下一次迭代的阈值δ。如此反复进行迭代，直到配准误差满足终止条件时结束。此外，改进算法利用Octree结构代替原传统ICP算法里的查找部分来搜寻最近点，这样可以大大提高点云最近点的搜索速度，从而降低点云配准的时间。

通过最近点距离搜索得到的点对中依然存在影响配准精度的错误点，改进算法通过求取对应点对的方向向量夹角来判断对应点对是否正确。由于在初始配准中已经求取了点云数据中所有点的法向量且将法向量方向的指向调整到点云曲面的同一侧，所以在这里只需要将各点法向量转化为单位向量，并求取各对应点对法向量夹角。经上述方法进行初配准后，两点云基本重合，正确的对应点对应满足点对法方向向量夹角小于某一阈值β，因此若夹角大于设定的阈值β，则认为是错误的点对，并将其剔除以避免错误的点对参加配准，从而提高点云配准精度。

2 实例验证

图1 龟模型配准对比图

为了验证改进算法的有效性，本文利用Rigel VZ-6000三维激光扫描仪采集的点云数据进行了实验。实验平台为CPU主频2.6GHz，内存4GB的Windows10系统。在本次三维模型重建中用到的点云处理软件是GeomagicStudio2012，在Microsoft Visual Studio 2010环境下利用C++语言编程设计、采用PCL 1.7.2版本点云库［11］、CMAKE 3.0跨平台编译工具来实现算法。

由于采集的数据中具有噪声，首先将点云数据进行去躁，而且为了提高配准效率对去躁后的点云数据，在保留其特征的前提下进行了采样等一系列预处理。

在点云配准过程中，按照上述初始配准的算法步骤，实现视点点云数据的K-邻域搜索、法向量及不变特征的求取，本文采用4邻域。

本文通过搜索不变特征来组成匹配点对，由最小二乘拟合计算旋转矩阵及平移向量，此次初始配准选取四邻域且进行了3次旋转平移。初配准后的两视角点云大致重合能够满足ICP算法对点云初始位置要求，而且为后续的点云精配准提供了良好的环境。

在PCL点云库的环境下按照前面描述的精配准策略进行实现，为了验证本文所采用精配准方法的有效性，分别按照传统ICP算法、初始配准+传统ICP算法和初始配准+改进ICP算法进行验证，结果如图1所示。

从配准效果图可以看出，由于传统ICP算法没有进行初始配准获得较好的精配准位置，导致迭代收敛到局部最优解，配准失败。而后面2次试验对点云进行了初始配准，使得配准成功，但是从初始配准+传统ICP算法、初始配准+改进ICP算法可以看出在点云轮廓边缘位置的配准上传统ICP算法的效果没有改进ICP算法好，这是由于在传统ICP算法中没有加入错误点对的去除条件，使得在同样的迭代收敛条件下，配准效果没有改进ICP算法好。同时，在配准时间及配准误差上，改进ICP算法都在传统ICP算法基础上有所提高。

3 结论

本文针对ICP算法存在的一些不足，提出了一种初始配准加精确配准的配准策略，在初始配准中通过点对之间不变特征的匹配完成点云数据的大致配准，在精确配准ICP算法中通过加入八叉树结构及求取内点点集来加快对应点对的搜索，提高配准效率。同时，利用配准点对之间的限制关系来去除错误点对提高配准精度。验证结果证明，本文配准策略及其改进方法能够很好地解决ICP算法存在的一些缺陷，并且有效提高配准效率及精度，满足配准要求。

［1］程效军，贾东锋，程小龙.海量点云数据处理理论与技术［M］.上海：同济大学出版社，2014.

［2］杨现辉，王惠南.ICP算法在3D点云配准中的应用研究［J］.计算机仿真，2010（8）：235-237.

［3］郑德华.ICP算法及其在建筑物扫描点云数据配准中的应用［J］.测绘科学，2011（3）：86-91.

［4］周春艳，李勇，皱峥嵘.三维点云ICP算法改进研究［J］.计算机技术与发展，2011（8）：75-77.

［5］F Su.The research of optical 3D measuring precision influencing factor in reverse engineering［J］.Applied Mechanics&Materials，2010（33）：157-162.

［6］S Du，N Zheng，S Ying，et al.Affine iterative closest point algorithm for point set registration［J］.Pattern Recognition Letters，2010（9）：791-799.

［7］LE Walizer，JF Peters.A bounding box search algorithm for DEM simulation［J］.Computer Physics Communications，2011 （2）：281-288.

［8］邢正全，邓喀中，薛继群.基于K-近邻搜索的点云初始配准［J］.测绘科学，2013（2）：93-95.

［9］钟莹，张蒙.给予改进ICP算法的点云自动配准技术［J］.中国图像图形学报，2007（3）：517-521.

［10］朱德海，郭浩，苏伟.点云库PCL学习教程［M］.北京：北京航空航天大学出版社，2012.

［11］PJ Besl，ND Mckay.A method for registration of 3-D shapes［C］//IEEE Transactions on Pattern Analysis and Machine Intelligence，1992（2）：239-256.

Point Cloud Registration Based on Improved ICP Algorithm

Qiu ShicongLuo Yi
（School of Architectural and Surveying&Mapping Engineering，Jiangxi University of Science and Technology，Ganzhou Jiangxi 341000）

In order to overcome the problem of requiring high quality initial point cloud position and low registration efficiency existing in the traditional iterative closest point(ICP)method,this paper developed an improved ICP algorithm.The improved algorithm combines K-nearest neighbor search and normal estimation,and set the invariant angle as invariant feature to achieve rotation matrix and the translation vector to realize initial registration,then the ICP algorithm based on Octree was used for accurate registration.The experimental results showed that the improved algorithm had obvious advantages for improving the registration accuracy and shortening the registration time.

point cloud registration；normal estimation；invariant feature；ICP algorithm；Octree

TP391.7

A

1003-5168（2017）04-0040-03

2017-03-07

邱世聪（1993-），男，硕士，研究方向：三维激光扫描数据处理。描仪自身及周围环境的影响往往没有较好的初始位置。因此，为了满足后续精确配准的要求，首先需要对点云数据进行初始配准。