导读：
3D点云配准是计算机视觉的关键研究问题之一，在多领域工程应用中具有重要应用，如逆向工程、SLAM、图像处理和模式识别等。点云配准的目的是求解出同一坐标下不同姿态点云的变换u ] H | X = ~ u C矩阵，利用该矩阵实现3 X I O N h % b ]多视扫描点云的精确配准，最终获取完整的3D数字模型、场景。本质上，关于六自由度(旋转和平移)的3D点云配准问题是典型的非凸优化问题p n s，其目标函数在六维可行域空间中具有多个波峰波谷，即优化求解过程中受初始变换矩阵影响，容易陷入局部最优解。点云配准结果虽然受限于其初始位置，但是早期的一些局部的配准算法对解决点云配准问j 4 = I题具有重要的Q 3 f U ~ x Z应用、启示意义。因此，本文重点介绍一些鲁棒性或效率较好的局部、全局3D点云配准算法。
--! f * R + q局部的3D点云配准算法--
ICP（Iterative Clos~ z x Dest Point）算法是应用最广泛的3D点云配准算法之一, 其通过欧式变换求解出两片点云的旋转平移矩阵及C 2 % = t D z .对应的配准误差。
ICP算法的核心思想可以简述为:假设数据点云 。向源点云 移动配准，ICP算法通过不断求解估计的变换矩阵，直到RMSE(Root Mean Square Error)配准误差收敛于局部最优解 (每一次迭代过程可以描述为：在 中搜索关于 的最近邻点集，构造协方差矩阵，奇异值分解获得单位四元数，进而求解旋转矩阵，平移向量则由对应点云的质心确定，由此实现数据Z 8 | Y f 9 i点云的旋转平移变换)。其中，关于RM9 X [SE的配准模型可以表示为：
在对旋转、平移可行域v 0 进行参数化的前提下，关于 范数配准模型的点云配准问题可以转化为关于旋转和平移的非凸优化问题。IC( + A K : +P虽然具有简单、收敛性好等优点，但其受限于点云初始位置且在解决具有离群值的点云配准问题，容易陷入局部最优解。
为了提高ICP算法的鲁棒性，学者提出了一系列的变种ICP算法。LM-ICP算法提出利用Leves n N ] 9 ?nberg-Marquardt算法对ICP配s G _ Q q :准模型进行求解，并利用DT（Distance-Transform）算法替代KD-tree搜索最近邻点时，减小点云初始位置对其配准结果的影响，并提高了配准效率。Chetverikov等。在ICP算法的基础上，提出了鲁棒性更好、更实用的Trimmed ICP 算法，对每次迭代匹配得到的最近邻点进行筛选，即对两两估计的匹配点的欧式距离进行排序，摒弃其中距离较大的点集，Y , . y ,惩罚的百e 3 ( !分率由核函数动态计算。Trimmed ICP 算法应用于具有离群值、噪声l q u的点云1 ] a配准问题时，能获得良好的配Z M W 7 ~准精度。然而，高占比的离群值对点l D T Y E B = p F云配o o N A R j x 5 3准算法的鲁棒性要求仍然是巨大的挑战。Bouaziz等提出Sparse ICP算法利用稀v & p S $ r疏l ; H h X e i D表示理论对进一步改进ICP算法的鲁棒性，即在 范数配准模型上增加p范数的惩罚项，提高每次迭代中求解匹配点的准确性，但其利用增广拉格朗Q 4 W T日求解大规模点云配准问题时效率较差。Mavridis等结合模拟退火算法提出了更为高效的Efficie? i G e F % }nt Sparse ICP算法，加速点云配准的收敛速度。
为了进一步提高配准效率，Li等利用CAD模型的三角切片性质，高效求解最近邻点，保证了配准精度，v J G @ s 6 ^ P 1并进一步提出动态步长试探性配准，避免收敛_ I O b曲线出现震荡。但实际扫描点云的分布并非均匀，基于CAD 模型的配准方法仅适用性于理想点云配准问题。Zhu等通过设置硬、软( : ^指标实现点云的高效精确配准，即在每次迭代过程中利用双向匹配的方式对噪声及离群值进行惩罚。但是配准结果受限于核函数中参数的预设值。上述基于 范数的迭代最近点配准算法主要包括ICP算法及其变种算法，该类局部的配准4 | .算法受 4 J R E R限于点云初始位置，仅适用于6 c ; p _ m K小角度错开的点云配准问题。在人机交互获得较好点云初始Y q D j p位置的前提下^ h 3 o { 7 c R，迭代最近 / I - M ^ A N点算法在解决点云配准问题时具有良好的鲁棒性，但也存在一些可以继续优化的不足，可以总结为三点：
（一）受限于主成分分析、奇异值分解算法，迭代最近点算法虽然具有良好的收敛性，但其迭代次数较多，后期收G y o / ~ ` & $敛缓慢。
（二）受限于数据结构，迭代最近点算法在每次迭代过程中搜索最近邻点的成本较高，KD-tree虽然搜索效率较高，但仍无X & & q m法满足于解决大规模点云的配准问题。
（三）受限于点云的稀疏特性} N - # b，并且实际应1 T : u * V用中主要通过对点云进行下采样以提高配准效率，迭代最近点算法无法实现精确配准。
针对上述不足点，学者区别于迭代最近点的配准算法构M x i建新的配准E 0 x m C b ; D模型，如概率密度模型、隐式最小二乘函数和高斯混合模型等，并结合其它优化算法提高点云配准的效率和精度。Biber等基于概率密度模型提出了Normal Dc y b o R x Q / .istribute Tranw ( M f ; D 1 Q #sform（NDT）算法，即使用D维的高斯函数作为配准模型：
NDT算法通过对源点云Q进行体素划分，即求解点云Q的包围盒，并对该包围盒进行细分，对包含于不同体素的源点云分别构建高斯模型。该算法_ k $ ~ , Q q最大的优势是迭代过程中不需要求解最近邻匹配点，其计算复杂度较低。其# P 8 5 E @ O中体素的划分方式与点云配准的精度和效率g S =相关，可利用回环控制点云配准精度，主要应用于机器人的实时Simultaneous Localizatc l h 9 u 4 Qion And Mapping（SLAM）环节。Jian等提出利用混合高斯模型替代单一的高斯模型。为了提高配准模型的鲁棒性，体素高斯模型被分别进行加权计算，其中多尺度的点云配准方法应用较为广泛，如NDT、EM-ICP等。上述基于概率模型的点云配准算法只需在每次迭代中求解雅可比矩阵，计算复杂度$ L u [ ] I K大大F E r D $ v m降低，且Magnusson等指出NDT算法较ICP算法能更好地避免点云初始位置对配准结果的影响。
针对点云配准的精度问题，部分学者提出了点到面的点云配准算法，利用曲线、曲面拟= 5 - = 3合求解出源点云的显、隐式表达，并利E % F用法向量求解每次迭代中的对应点对，如下图所示
Liu等提出利用动曲面构建源点云的拓扑外形实现点云配准，主要应~ Q L s 2 u M用于简单0 9 _形状组合而成的零件点云配准问题，如圆锥、圆柱、旋转扫掠螺旋曲面等_ D P G J。为了解决复杂外形点云的配准问题，学者提出了k f & ( Z N R 1 m鲁棒性更强的曲面拟合方法，如B样条模型、八叉树结点等。该类配准算法的实用性更强且应用范围更广。在此基础上，张等分析了移动最小二乘法在y u H ^ . e 9曲面拟合应用中的发展及其优越性，并提出该方法能实现精确的点云配准d A K 8 S G )且对噪声具有良好的鲁棒性。但是此类算法其需要预先设置较好的参数，如分支数、权值等。
相较之下，迭代最近点的点云配准算法的鲁棒性; a e更强，因其不需设置冗余的优化参数，但其S @ * Z | l ) 3它算法则在提高效率U / J 6 Y T $和精度方面更具优势。上述局部算法及其变种广泛应用于解决点云配准问题，且可有效避免噪声和离群值对配准结果的影响。但是，此类配准算| ~ E / L法受限于点云初始位置，容易陷入局部最优。区别于此类具有鲁棒性的局部配准算法，学~ & E 8 ~ b b 3者针对点云初始配准位置的优化问题提出了一系列全局优化的配准算法。
--全局的3D点云配准算法--
Silva等将点云配准问题转换为多变量的非凸优化问题，并结合遗传算法求解出全局优化的变换矩阵，能有效E W U Y C W ( 避免点云初始位置对配准结果的影响。其他应用g v { 3 { 6 -于点云全局配准的智能算法还包括粒子群算法、模拟退火等。然而，此类启发式算法需多次调用配准模型进行优化求解，在处理大规模点云配准问题时效率较低，且其全局解并未0 T n h * ` y % K有严格的证明。为了提高点云配准效率，部分学者提出通过构造几何不变量匹配对应T 4 j K @ I N F点对（理论上三组: ~ S匹配点对就可求解出点云配准的变换矩阵），该类方法同样不受点云初始位置影响，且计算复杂度更低。Wyngaerd等通| + K B w } A p 9过曲率特征求解对应点对，实现点云全局配* o ? o * v ` 6准；Gelfand等则通过构造积分体积特征T G I - ;计算匹配点对求解变换矩阵；Ru$ z _ { G ~ ] `su等提出构造点特征直方图作为局部描述符。RANSAC方法被直接应用于点云配准，但受限于其配准效率，一开始V L O ; I主要应用于解决二维的点云v : H a &配准问题。随后，Aiger等利用4点法构造几何特征进而提取稀疏的匹配点对，使得R2 h _ANSAC方法能有效地应用于三维点云配准。当点云的特征不变量较为明显时，基于几何不变量的点云配准方法可以作为性能优异的算# o B 2 W ( ? }法使用。
Yang等基于 范数配准模型首次推导出了关于六维变换域的上下界函数，并利用分支定界算法提出了全局优M ; 9 &化的Go-ICP算法，且该算法有效地证明了所求解变换矩? ] , @阵的全局最优性。但是，Go-ICP算法需结合DT算法才可能高效地实现点云配准，而DT算法的初始化较为耗时。Lian等提出了更为高效的AMP算法进行点云g L t m全局优化配准，但其主要适用于图A r V L X q -像处理领域。为了提高点云配准效率，Chin等提出了Glob-GM-ML算法将六维K R 4 w c 9 P的点云% e Y L J Z o 5配准问题分解为两个独立的三维平移、旋转问9 g { ; = ~ A题，该算法通过构建特征不变量求解平移参数并认为其在配准问题中是先验的，即E X T h l (六维的点云配准问题有效地转化为关于旋转的三维非凸优化问题。该方法利用解耦的思想高效地实现点云全局优化配准，是近些年研究的热点之一R R b N M ^ Z j O，Liu和Li等基于旋转不变量并利用分支定界方法求解出全局优化的平D n K a E移参数，进而实现高效的点云全局优化配准。
为了解决构造旋转不变量是的超参数M . P ! 6 4 u 设置问题，Yang等利用多项式时间提出了6 : V I O n 6 _TEASER算法对解决具有极高离群值的点云全局配准问题具有良好的鲁棒性。区别于应用于CPU常规硬件的全局点云配准算法，GOGMA算法等基P N D于混合高斯模型构建了适用于GPU框架的高效点云全局优化配准算法，即在全局优化过程中可利用GPU框架实现并行计算，提高加速点云全局优化配准效率。