点云配准论文阅读笔记--Efficient Variants of the ICP Algorithm
该文本总结了ICP（Iterative Closest Point）算法及其变体在三维模型配准中的应用。文章通过分类和比较不同ICP变体算法，重点关注了算法的收敛速度。研究采用了人工合成数据进行测试，结果表明，通过优化选点、点匹配、权重分配、点对剔除和误差度量等策略，可以显著提高ICP算法的效率。最终提出了一种高速优化组合变体，能够在30毫秒内完成大规模点云数据的配准。
目录
-
点云配准系列
-
前言
-
摘要
-
1.1 引言-ICP变体算法的分类
-
- 比较方法
-
2.1 用于测试的数据集
-
3种ICP变体的对比分析
-
3.1 基于采样率的点选区对比
- 3.2 点匹配策略的对比分析
- 3.3 点对权重的分配策略
- 3.4 点对剔除策略的优化
- 3.5 误差度量与优化策略
-
4 High-Speed Variants高速的icp变体
-
5 Conclusion结论
-
参考文献
-
完
-
点云配准系列
点云配准1：基础概念与ICP算法实现
点云配准2：PCL1.10.0环境下ICP算法实现及源码解析
点云配准3：3D-NDT算法在PCL上的实现及其参数配置
点云配准4：CloudCompare软件及其点云配准功能解析
点云配准5：4PCS算法在PCL环境下的实现
点云配准6：Tricp算法在PCL平台上的应用
点云配准论文阅读笔记–高效ICP变体研究
点云配准论文阅读笔记–实证对比ICP变体
点云配准论文阅读笔记–4PCS算法的鲁棒性研究
点云配准论文阅读笔记–3D-NDT博士论文内容
写在前面
论文Efficient Variants of the ICP Algorithm阅读笔记
摘要
该算法在三维模型配准领域得到了广泛的应用。本文系统性地介绍了几种icp变体算法，并对这些变体算法进行了系统性比较分析。研究者们在此基础上，提出了一个高效且快速的icp组合变体算法。
1 1 Introduction – Taxonomy of ICP Variants引言-icp变体算法的分类
icp是三维模型配准的主要方法，本文假设初始配准已经完成。（两点云已经有好的初始相对位置）。
我们将icp变体算法分成了下面6种，也就是影响算法的6个阶段（stage）：
1、选点：降采样，从一个还是两个点云都选（降采样）
2、点匹配：匹配源点云的点至参考点云，生成对应点对
3、权重：为每个点对赋予权重
4、剔除点对：剔除影响结果的点
5、误差度量方法：点到点、点到面
6、最小化误差方式
本文的关注点是算法速度。主要的结构是：
1、比较icp变体的方法
2、测试所用数据
3、icp变体在六个6个stage的表现
4、法向量空间直接采样的概念
5、最后，我们测试了一个为高速而优化的变体组合。
2 Comparison Methodology比较方法
首先确定一个基准组合方法（baseline），在该框架中，icp变体的对比进行。降采样采用随机采样方法，点匹配基于法向量计算，且法向量在45度以内。所有点对均采用统一的权重进行评估。在剔除点对的过程中，采用边缘剔除与最大距离剔除两种方法。误差度量采用点面对测度，通过最小化误差完成配准。为保证配准结果的公平比较，采样点数统一设置为2000，并基于深度图像进行处理。其中，法向量基于最近邻4点计算，不考虑颜色和几何信息。
2.1 Test Scenes用于测试的数据
基于三组人工合成的数据集：
1、wave数据集，大多数icp变体都能实现配准；
2、分形地形数据集，具有不规则地形特征，包含多层次的形态特征；
3、切割平面数据集，两平面均带有高斯噪声和X形凹槽，对大多数icp变体而言，配准效果较差
使用合成数据的主要因素是，我们能够明确知道正确的变换关系，相对于让算法自行计算误差而言，这样做的主要目的是为了更客观地比较算法的效果。
3 Comparisons of ICP Variants icp变体算法的对比
3.1 Selection of Points选点（降采样）方式对比
降采样比较：
1、全部点
2、均匀降采样所有点
3、随机降采样，每次迭代使用的点各不相同
4、具有较大梯度的点
5、是选择从单一点云降采样还是同时对两个点云进行降采样
结果表明，对于法线分布良好的场景（wave），采样策略的选择并不显著影响结果。
但是，对于切平面这种数据，仅向量空间采样能实现收敛性，如图3所示。其原因在于，均匀采样和随机采样在凹槽中的采样点数量较少，导致在平面和噪声中采到的点的影响未能有效覆盖凹槽中的点的影响。而法向量空间采样在凹槽中采样了大量点，如图4(a)、(b)所示。
3.2 Matching Points点匹配方法对比
点匹配：
1、确定最近点，可以借助kd树进行加速运算
2、源点云的法线方向与参考点云的交点位置，可以通过几何计算获得
3、通过从目标网格的角度，使用距离摄影机将源点投影到目标网格上，这被称为反向校准
4、颜色与法线的结合度决定了整体匹配效果
结果：
对于不规则地形（fractal landscape），normal shooting算法表现最佳。最近点匹配算法在初始距离较大时，对噪声数据敏感，且会产生较多的误匹配现象，具体可见图7和图8的实验结果。
在切平面（incised plane）上，该方法的最近点计算具有唯一收敛性。尽管该方法在计算速度上不如其他方法高效，但在处理最复杂和最难以配准的数据时，其稳定性表现得尤为突出，如图9所示。
从时间复杂度来看，如图所示，投影算法的时间复杂度为常数，而基于kd树搜索的算法，其时间复杂度为O(logn)。
3.3 Weighting of Pairs点权重
权重策略：
1、所有点的权重相同
2、随着点之间的距离增加，权重逐渐减小，公式表示为：
Weight=1-\frac{Dist(p_1,p_2)}{Dist_{max}}
3、法向量的点积计算方式：
Weight=n_1\cdot n_2
4、权重设置为动态调整的值
结果：
点对之间的权重对收敛速度的影响受数据分布的影响较大。对于同一组数据，采用不同权重策略的效果差异较小，如图11和图12所示。
3.4 Rejecting Pairs点对剔除
点对剔除策略：
1、去除超出设定阈值的点对
2、剔除表现最差的10%
3、去除与平均距离相差超过2.5个标准差的点对
4、与邻近点对的差异较大（可能需要进一步确认）
5、去除边界点对
去除边界点对造成的错误配对确实有效，如图13所示。
结果：
rejection在初始收敛阶段没有显著的帮助，如图14所示。当初始两点云较为遥远时，采用rejection反而会导致收敛速度减慢。总体而言，rejection可能对算法的精度和稳定性产生一定影响，但不会显著提高计算速度。
3.5 Error Metric and Minimization误差度量和最小化
求解方法：
- 点间平方和：奇异值分解（SVD）、四元数、正交矩阵、双四元数
- 点间距离与颜色
- 点到面的平方和
为初始配准配置扰动，以选择最优结果，这有助于避免误差函数的局部最小值。
结果表明，采用点到面的距离度量方式更为有效，如图15、16所示。
4 High-Speed Variants高速的icp变体
该高速ICP变体通过以下方式组合：基于投影的点对生成（无需kd树搜索，且迭代时间恒定），点面对距离度量，采用随机采样策略，赋予相同权重分配，并在距离阈值下进行点对剔除。最终实验结果表明，真实的大象数据可在30ms内完成配准。
5 Conclusion结论
对icp变体算法进行分类和比较，重点考察其收敛速度。通过提出一种新型采样策略，旨在促进稀疏点云配准的收敛性。进一步优化了icp变体算法，实现点对匹配时间恒定，并可在几毫秒内完成点云配准。
参考文献
Szymon Marek Rusinkiewicz. Efficient variants of the Iterative Closest Point (ICP) algorithm. In the proceedings of the International Conference on 3-D Digital Imaging and Modeling, pages 145–152, 2001.
完
边学边用，如有错漏，敬请指正
--------------------------------------------------------------------------------------------诺有缸的高飞鸟202012