论文专区▏改进的ICP点云配准算法
【编者按：三维激光点云配准是点云三维建模的关键问题之一。经典的ICP算法对点云初始位置要求较高且配准效率较低，提出了一种改进的ICP点云配准算法。该算法首先利用主成分分析法实现点云的初始配准，获得较好的点云初始位置，然后在经典ICP算法的基础上，采用k-d tree结构实现加速搜索，并利用方向向量夹角阈值去除错误点对，提高算法的效率。实验表明，本算法流程在保证配准精度的前提下，显著提高了配准效率｡本文发表在《海洋测绘》2015年第2期上，现编发给朋友们阅读了解｡朱新宇，男，1989年出生，安徽宿州人，中国石油大学地球科学与技术学院，硕士研究生，主要从事三维点云数据处理研究｡】
文/朱新宇 万剑华 刘善伟 曾喆
一､引言
三维激光扫描技术具有直接快速､非接触､精度高等优点，被广泛应用于地形测量､摄影测量､古建筑修复､数字城市､逆向工程等领域。在实际测量过程中，由于仪器设备视野､物体几何形状以及测量方式的限制，往往需要进行多视角测量。为了实现三维点云建模，须把不同视角测量得到的点云数据通过坐标变换统一在一个坐标系统中，即点云配准[1]，点云配准的精度和效率直接影响点云三维建模的精度与效率。
目前点云配准算法中，应用最为广泛的是Besl等提出的迭代最近点算法(iterative closest point，ICP)[2]。ICP算法实质上是基于最小二乘法的最优匹配方法，重复进行“确定对应点集——计算最优刚体变换的过程”，直到某个表示正确匹配的收敛准则得到了满足，该算法要求两个匹配点集中的一个点集是另一个点集的严格子集，为了避免陷入局部最优，还要求两个点集初始的相对位置与真实位置相差不大[3]。为了提高ICP算法的效率和适用性，国内外研究人员做了大量的工作来改进ICP算法。Chen等提出利用点的切平面来逼近点云，利用点到切平面的距离来取代点到点的距离，但这种方法计算较为复杂，配准速度仍然比较慢[4]。Blais等结合随机采样和定标法来提高搜索点对的速度，但这种方法会降低配准的精度[5]。戴静兰等提出了基于特征点曲率特征的改进ICP算法，但该算法中曲率特征计算量过大，影响整体配准效率[6]。朱延娟等提出了一种基于点云曲率特征和几何哈希的点云配准算法[7]，薛耀红根据点的邻域曲率相似度和刚体变换不变量进行初始配准[8]，但在配准的精度和速度上还有待与进一步的提高。综上，ICP算法易陷入局部最优解和效率低下的问题仍然没有同时得到解决。
基于上述点云配准算法的分析，本文提出一种改进的ICP配准算法，该算法主要进行如下改进：
⑴针对ICP算法易陷入局部最优解的问题，在初始配准过程中引入主成分分析法，快速实现两个点集整体大致重合。
⑵针对ICP算法精确配准效率低下的问题，提出基于k-d tree和方向向量阈值的点云精确配准算法，通过k-d tree进行快速搜索，并利用方向向量阈值去除错误点对，提高算法效率，尤其适用于几何特征明显的点云数据。
二､改进的ICP点云配准算法
实践证明ICP算法具有较好的配准精度，但算法效率较低，对于实测的海量点云数据无法直接使用[6]。基于此，本文提出了改进的ICP点云配准算法。本文点云配准算法分为两部分：初始配准和精确配准。首先，基于主成分分析法(PCA)获得点云的主方向坐标系，实现点云的初始配准，为ICP算法提供一个较好的点云初始位置；然后基于ICP算法利用k-d tree查找对应点对，并根据点云的方向向量夹角阈值去除错误点对，实现点云精确配准。算法流程见图1。
⒈ 初始配准
ICP算法对点云初始位置的要求较高，如果初始位置不合适，有可能导致迭代收敛到局部最优解，造成配准失败。因此，点云初始配准非常重要。PCA是一种有效的检测数据集简化分析方法，用于减少数据集的维数，同时保持数据集对方差贡献最大特征[9]。对于点云数据集，PCA 算法求出的3个特征向量可以作为点云的3个主方向，由此可以建立一个以点云重心为原点，以3个主方向为坐标轴的参考坐标系。由于PCA反映了数据集对方差贡献最大特征，因此对于相似度大的两片点云，只要把两片点云的参考坐标系调整到一致，就可达到点云初始配准的目的。PCA计算的主方向可能出现相差180°的情况，需要建立两片点云的最小包围盒，通过比较坐标变换后最小包围盒的重合体积来测试点云是否大致重合，否则依次旋转坐标轴180°，直到点云大致重合。本文采用PCA，可以快速地实现点云的初始位置匹配。
⒉ 精确配准
经初始配准后，目标点云和参考点云大致重合，但配准精度达不到点云配准的要求，因此还需要进行精确配准。本文在ICP算法的基础上，采用k-d tree结构来搜寻最近点以提高对应点对的搜索速度，同时利用方向向量阈值来去除错误点对以提高每次迭代的精度。
⑴k-d tree结构
k-d tree法建立点与点的拓扑结构是基于二叉树的坐标轴分割法。k-d tree的详细构建过程为：首先沿X轴查找分割线，求出所有点的x值的平均值，以最接近平均值的点的x值将空间分成两部分，在子空间中按Y轴查找分割线，将其各分为两部分，然后在新的子空间中按Z轴分割，以此类推，直到最后分割的区域内只有一个点为止[10]。利用k-d tree查找最近点的时间效率为O(n log n)级，可以大大提高点云最近点的搜索速度。
⑵方向向量阈值
利用最近点距离搜索得到的点对依然包含一定的错误点，影响配准的精度。本文使用对应点对的方向向量夹角来判断是否为正确对应点对，提高点云配准的精度。
①法向量估计
对于点云中任一点P，估算其法向量等价于估计该点与其K个邻近点拟合而成的切平面的法向量。本文采用邻域协方差分析法求取点的法向量[11]。原理如下：
任一点P与其K 邻域得到协方差矩阵：
式中，p0为K邻域的质心，协方差矩阵CV的最小特征值对应的特征向量即为点P的法向量。
经上述方法求得的法向量可能具有两个方向，因此需要对所有点的法向量进行调整使其指向点云曲面的同一侧[12]。由于点云数据具有稠密的采样点，可以先确定一个初始点的正确朝向，然后调整其邻域集中采样点的法向量朝向，继而通过不断邻域扩散，完成对整个点云数据法向量朝向的调整。
②方向向量夹角
将点云中各点法向量单位化，并计算各对应点云法向量夹角。经初始配准后，点云大致重合，若为正确的对应点对，应该满足方向向量夹角小于某一阈值t，因此若夹角大于给定的阈值t，则认为是错误点对，将之剔除，以此来提高点云的配准效率。
三､实验与分析
本文采用的实验数据为著名的Stanford bunny中两个视角(0°和45°)的点云数据，见图2，两片点云个数分别为40256､40097，图中坐标系为利用主成分分析法为两片点云建立的主方向坐标系。实验平台为CPU主频2.26GHz，内存2GB的Windows7系统，算法由MFC结合OpenGL环境实现。
图3为点云初始配准结果，缩小了两幅点云的平移和旋转错位，两幅点云位置和方向大致重合，配准精度仍较低。图4为初始配准基础上的精确配准结果，此时配准精度大幅提高，点云完全重合。本文同时也进行了经典ICP算法的实验，表1为实验结果比较。
从表1看出，经初始配准后的点云配准误差为23.10483mm，明显高于经典ICP算法配准误差，经精确配准后，配准误差与经典ICP算法基本持平，且略高；本文算法总计配准时间为36.539s，而经典ICP算法的耗时是本算法的约4倍，配准速度提高显著。这是由于采用k-d tree结构缩短了搜索对应点对的时间周期，而且利用方向向量阈值减少错误点对，提高了算法每次迭代的准确度，减少了精确配准的迭代次数。综上，本文算法与经典ICP算法相比，不仅具有良好的配准精度，同时显著提高了配准效率。
四､结束语
本文提出了一种改进的ICP点云配准算法，采用主成分分析法实现了点云的初始配准，避免了算法陷入局部最优而导致配准失败，增强了算法的适用性，提出k-d tree搜索与方向向量阈值相结合的策略来快速获取正确的对应点对。实验表明，该算法具有较好的配准精度和收敛速度，算法效率显著提高。但是对于几何特征不明显的点云数据而言，由于不同对应点对之间的方向向量夹角差异过小，本算法未能显著提高精确配准效率，这也是下一步工作的研究方向。
参考文献：
[1]周春艳，李 勇，邹峥嵘.三维点云ICP算法改进研究[J].计算机技术与发展，2011，21(8)：75-77.
[2]Besl PJ，Mckay ND. A method for registration of 3-dshapes [J]. IEEE Transactions on PatternAnalysis andMachine Intelligence，1992，14(2)：239-256.
[3]高珊珊.基于三维激光扫描仪的点云配准[D].南京：南京理工大学，2008.
[4]Chen Y，MedioniG.Object Modeling by Registration ofMultiple Range Images [C]// In：Proceeding of the 1991IEEE International Conference on RoboticsandAutomation，Sacramento，CA，USA，1991：2724-2729.
[5]Blais G，Levine MD.Registering Multiview Range Datato Create 3D Computer Graphics [J].IEEETransactionson Pattern Analysis and Machine Intelligence，1995，17(8)：820-824.
[6]戴静兰，陈志扬，叶修梓.ICP算法在点云配准中的应用[J].中国图象图形学报，2007，12(3)：517-521.
[7]朱延娟，周来水，张丽艳.散乱点云数据配准算法[J].计算机辅助设计与图形学报，2006，18(4)：475-481.
[8]薛耀红.点云数据配准及曲面细分技术[M].北京：国防工业出版社，2010：24-30.
[9]杨现辉，王惠南.ICP算法在3D 点云中的应用研究[J].计算机仿真，2010，27(8)：235-238.
[10]苑 博. 散乱点云数据表明重建方法研究[D]. 哈尔滨：哈尔滨理工大学，2012.
[11]钟 莹，张 蒙.基于改进ICP算法的点云自动配准技术[J].控制工程，2014，21(1)：37-40.
[12]邢正全，邓喀中，薛继群.基于K-近邻搜索的点云初始配准[J].测绘科学，2013，38(2)：93-95.