深度学习混沌模拟退火算法（模拟退火算法在点云配准中的应用）

深度学习混沌模拟退火算法（模拟退火算法在点云配准中的应用）目前，在点云配准算法中，应用最广泛的是Besl和Mckey提出的ICP算法［3］，该算法本质上是基于最小二乘法的最优匹配算法，解决了多视角点云配准问题。通过建立目标点集和参考点集之间的映射关系，根据最小二乘法原理计算一个最优的坐标变换，更新迭代，直到满足收敛精度后停止配准，求得最终的旋转和平移参数［4］。为了提高ICP算法的精度和效率，朱新宇等人提出首先利用主成分分析法进行初始配准，然后在ICP算法的基础上采用kd tree结构加速搜索［5］。CHEN Y等人提出利用点的切平面来逼近点云，利用点到切平面的距离来提高点对点的距离［6］。综上，ICP算法易陷入局部最优解和配准效率低的问题仍没有得到解决。随着计算机仿真技术日新月异的发展和市场需求的逐步提高，由实物模型产生数字模型的逆向工程技术得到了越来越广泛的应用。虽然三维激光扫描仪可以在不接触物体的情况下，快速并精确地获得物体表面的三维信息

王鹏，俆磊

（南京邮电大学 自动化学院，江苏 南京 210023）

：针对经典的最近迭代点（Iterative Closest Point，ICP）算法易陷入局部最优解且配准效率较低的问题，提出一种基于模拟退火（Simulated Annealing，SA）算法和ICP算法的混合点云配准算法。该算法以模拟退火算法的结果作为ICP算法的初值进行迭代，以寻求更优解。该算法结合了ICP算法的寻优能力和模拟退火算法的概率突跳特性，克服了ICP算法收敛速度慢的问题，且在成像质量上较ICP算法有所提高。实验结果表明，该方法能够在消除错误点对、提高配准精度的同时，具有较高的配准速度。

：模拟退火算法；最近迭代点算法；点云配准

：TP391.7文献标识码：： 10.19358/j.issn.1674-7720.2017.02.007

引用格式：王鹏，俆磊.模拟退火算法在点云配准中的应用［J］.微型机与应用，2017 36（2）：20-21，27.

0引言

随着计算机仿真技术日新月异的发展和市场需求的逐步提高，由实物模型产生数字模型的逆向工程技术得到了越来越广泛的应用。虽然三维激光扫描仪可以在不接触物体的情况下，快速并精确地获得物体表面的三维信息，得到点云数据，但是受光照条件及被测物体体积等因素的影响，只能得到当前视角下的点云数据，无法获得物体的完整信息［1］。所以需要从多视角对物体进行多次测量，将各个视角下扫描得到的孤立的点云数据进行重新整合和配准，生成一个位于同一个坐标系的三维点云数据集，该过程称为点云数据的配准［2］。

目前，在点云配准算法中，应用最广泛的是Besl和Mckey提出的ICP算法［3］，该算法本质上是基于最小二乘法的最优匹配算法，解决了多视角点云配准问题。通过建立目标点集和参考点集之间的映射关系，根据最小二乘法原理计算一个最优的坐标变换，更新迭代，直到满足收敛精度后停止配准，求得最终的旋转和平移参数［4］。为了提高ICP算法的精度和效率，朱新宇等人提出首先利用主成分分析法进行初始配准，然后在ICP算法的基础上采用kd tree结构加速搜索［5］。CHEN Y等人提出利用点的切平面来逼近点云，利用点到切平面的距离来提高点对点的距离［6］。综上，ICP算法易陷入局部最优解和配准效率低的问题仍没有得到解决。

本文提出一种混合方法，在ICP算法的基础上，以模拟退火算法的结果作为ICP算法迭代的初值进行迭代。使其跳出局部最优解，达到全局最优解，从而获得更好的成像效果。

1初始配准SA算法

SA算法来源于固体退火原理，是基于MonteCarlo迭代求解策略的一种随机寻优算法［7］。基于物理中固体物质的退火过程与一般组合优化问题之间的相似性［7］。用SA算法进行初始配准是针对整体点云数据而言的，不依赖于具体的点云数据的几何特征，通过优化迭代，在满足迭代条件后，找到最优的平移变换和旋转向量，为ICP算法找到更优的初始位置，并有效防止点云配准陷入局部最优的情况。

SA算法初始化一个N维目标搜索空间，由m个点云数据组成，则点云中的潜在解中第i个点在迭代次数为t的时候表示为一个N维的向量xti=(xti1，xti2，…，xtiN)，i=1 2 … m，将xti代入其约束的目标函数f(xti)中 求得适应度值，通过新解与初始解的比较来判断该点的优劣。随着算法的运行，退火温度t自动调整，随着温度的逐渐下降，点云逐渐形成基态。当算法接近收敛时，局部最大适应值和个体平均最大适应值之比逐渐减小并趋向于1，退火温度t随之逐渐接近于0。为了提高配准效率，本文设计了模拟退火概率接受准则，即

根据点的适应值进行概率接受，既接受优化解，也接受恶化解，跳出局部极小。当新点的适应值增大时，系统一定接受新点，当新点的适应值降低时，先由（1）计算出模拟退火概率q 如果q>rand［0 1］(0~1之间的随机数)时，系统也接受新点，否则舍弃。随着算法的运行，概率q逐渐趋向于0，算法从局部最优解中跳出，找到全局最优解。

2SA-ICP算法

2.1ICP算法分析

ICP算法的目标是找到两个不同视角下的点云数据的旋转变换和平移向量，使得两配准点云数据满足给定约束条件下的最优坐标变换［89］关系。设目标点P={p1 p2 … pn}和参考点集X={x1 x2 … xn}，其中pi和xi分别为点集合P和点集合X中的点，rk为P、X在第k次迭代中的刚体变换，Xk={xk1 xk2 … xkn}为X在第k次迭代中的对应点，根据最小二乘法求解最优空间变换，使下列目标函数最小：

fmin=∑ni=1r(xki-pki)2（2）

根据对应点求出使平均距离最小的刚性变换，如果F(rk-1)-F(rk)<σ 结束迭代；否则执行k 1次迭代，并将新的变换点集作为新的迭代初值。

2.2优化的SA-ICP算法

初始化SA算法中的7个参数，rx，ry，rz，tx，ty，tz，u 其中rx，ry，rz表示旋转变量，tx，ty，tz表示平移变量，缩放参数u=1。初始给定旋转变量R3×3=100

010

001，平移变量T1×3=［000］，通过下列公式得到旋转参数和平移参数：

计算旋转变量参数R和平移变量参数T，缩放参数u=1，计算新的变换点集

X=R·X T(4)

通过目标函数计算得到适应度值fmin。

更新点云位置，计算更新后的适应度值，当前迭代次数t=t 1 判断是否满足迭代条件，如果不满足返回，重新迭代，若满足则将配准后得到的新的点云数据集X作为ICP配准的初始位置。算法流程图如图1所示。

为了有效地分析各配准算法的有效性，本文采用平均配准误差作为评价标准，设{Ai|i=1 2 … m}为一组配准方法，wAik(k=1 2 … n)为某一配准方法Ai的有效配准点对，则对于配准方法Ai有下列平均配准误差计算公式［10］：

3实验分析

实验平台为双核CPU，主频3.2 GHz，内存4 GB，Windows 7操作系统，算法由MATLAB软件编程仿真实现。

图2为经典ICP算法的点云数据配准，从图中可以看出配准精度比较低。图3为SAICP算法配准结果，此时点云配准精度大幅提高，点云重合度大幅提升。从表1可见，本文算法与经典ICP算法相比，在提高了精度的同时，提高了效率。

4结论

点云配准作为三维重建过程中的关键环节，具有重要研究意义。但该技术一直难以实用化的主要原因在于经典的ICP算法在点云配准中易选到噪声点，产生较高的错配率，造成重建模型失真。在SA算法和ICP算法的结合过程中，通过适应度函数控制点云配准精度，可以整体寻优，为ICP算法找到最佳的初始位置，避免了ICP算法陷入局部最优，有效地提高了ICP算法的准确性。

参考文献

［1］ 钟莹，张蒙.基于改进ICP算法的点云自动配准技术［J］.控制工程，2014 21（1）：37-40.

［2］ 高珊珊.基于三维激光扫描仪的点云配准［D］.南京：南京理工大学，2008.

［3］ 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.［4］ 杨现辉，王惠南.ICP算法在3D点云中配准的应用研究［J］.计算机仿真，2010，27（8）:235-238.

［5］ 朱新语，万剑华，刘善伟，等.改进的ICP点云配准算法［J］.海洋测绘，2015 35（2）：78-79.

［6］ CHEN Y MEDIONI G.Object modeling by registration of multiple range images［C］.Processing of the 1991 IEEE International Conference on Robotics and Automation Sacramento CA USA 1991:2724-2729.

［7］ 王华秋，曹长修.基于模拟退火的并行粒子群优化研究［J］.控制与策 2005 20(5):500-504.

［8］ 王 欣，张明明，丁晓，等.应用改进迭代最近点方法的点云数据配准［J］.光学，2012 20（9）:2068-2077.

［9］ 戴静兰，陈志扬，叶新梓.ICP算法在点云配准中的应用［J］.中国图象图形学报，2007 12（3）：517-521.

［10］ 李俊山，王蕊，李建军.三维视景仿真可视化建模技术［M］.北京：科学出版社，2011.