【泡泡点云时空】ICP算法的高效变种

泡泡点云时空，带你精读点云领域顶级会议文章

标题：Efficient Variants of the ICP Algorithm

作者:  Szymon Rusinkiewicz, Marc Levoy, Stanford University

编译：田花花同学

审核：徐二帅，吕佳俊

欢迎个人转发朋友圈；其他机构或自媒体如需转载，后台留言申请授权

摘要

在相对初始位置已知的情况下，ICP（iterating closest point）算法大量使用在3D模型的几何匹配上。人们已经提出了ICP的各类变种算法，这些算法涉及到ICP的每一个阶段，从点的选取匹配到最小化策略等。我们列举了大部分变种算法，对其进行归类，并且评估了它们获得正确匹配结果的速度效率。为了提高对近乎平面又缺乏特征点的网格匹配的收敛速度，我们使用了基于正态空间的单位采样的变种算法。最终给出一个结合各种变种算法长处来提升运算速度。这里还展示了在有一个还不错的初值时，可以将两个深度图像在几十毫秒内完成匹配的算法。这在未来的实时3D模型获取及基于模型的追踪都具有很大的潜力。

测试场景介绍

我们使用三个人工合成场景来评估变种算法。“波浪”场景Figure1.a）对于大多数ICP算法来说都很简单，因为它包含着相对来说平滑的大比例几何特征。两个网格都相对独立的添加了高斯噪声，异常值以及随机失活。不规则“分形地貌”测试场景（Figure1.b），有着不同程度的细节特征。“划痕平面”（Figure1.c）上则有着高斯白噪及一个“X”形的刻槽。这对ICP来说是一个复杂场景，即使在初始位置上给一个很小的旋转角度，大部分变种都无法获得正确的匹配结果。注意这三个场景都相应包含了低频，全频域及高频特征。尽管这些场景确实不能包括所有的情况，但也是大部分扫描应用中遇到的代表性场景。

使用人造数据的原因是因为我们能够知道正确结果是多少，并且能够用正确结果与ICP表现进行对比。本文中使用的度量是两个网格上两点实际坐标的均方根距离。使用这种真实的误差度量相比于算法自带的度量方式可以更加客观的反映变种算法们的表现情况。所有运算结果都是使用c++在550 MHz Pentium III Xeon 处理器上运行的。

ICP变种方法多场景收敛速度对比

1、点的选取

我们将从两个网格上分别取点和从一个网格选点进行对比优势。对于“波浪”测试场景以及基础算法，差距微小（见图5）。然而其中一部分原因是因为使用的是匹配共同最近点算法（见3.2章），两个网格是相对称的。如果使用一个“非对称”算法，如投影或者法相射线（见3.2章）可以看到从两个网格取点有略微优秀一些（见图6），尤其是在开始迭代时两个网格差的较远时。此外，我们认为在网格重叠部分很小或者网格上有漏洞的时候，从两个网格上取点结果会更优。

2、点的匹配

首先看“划痕”场景的表现（图7）。对于这样的场景，与投影算法相比，法相射线方法会给出更优的结果。临近点算法相应表现差强人意。我们猜想是因为最近点算法对噪声更加敏感并且比其他算法得到更大量的错误的配对（图8）。

3、匹配组的权重

我们首先看“波浪场景”（图11）。我们引入过更多的噪声来更明显的看出变种算法间的差别。可见，在加入噪声时，所有的权重策略结果都是相似的。只有“uncertainty”和“compatibility of normals”会稍微优于其他方法。但是对于“刻痕”场景（见图12），结果相差不多，尽管表现差距较大。我们会慎重诠释这个结果，因为模型上点的法向量不指向扫描仪的时候，基于不确定性的方法给该点分配的权重更高。因此，在这个场景中，刻痕内部的点的权重更高。这就使得收敛速度大幅增加。总之，权重的选取对收敛速度的效果微小并且高度依赖数据。而且权重的选择依赖于其他因素，例如最终结果的精度。

4、剔除点对:

图14显示的是，在“波浪”场景加入额外噪声与异常数据时，对比了无剔除，剔除最差10%，剔除不兼容组队，2.5等方法。我们可以看到对异常值的剔除不会对初始收敛有任何帮助。实际上，即使是最激进的算法（剔除最差的10%）在两个网格距离较远时收敛也很慢。因此结论便是，异常值剔除尽管在最终匹配结果上的精度和稳定性更好，但是对收敛速度并没有帮助。

5、误差度量及最小化:

“分形地貌”场景中，我们可以看到即使使用外推法，点到平面的度量误差要远优于点到点的度量（图15）。在“刻痕”场景中，差距就更加明显（图16）。这里点到点的度量就无法得到正确解，因为使用点到点的误差度量无法轻易的使两个平面产生滑动。

ICP实时高速配准

让ICP在实时情况下运行（例如视频的频率下）将会在计算机视觉和图像上产生新的应用。例如，一个低价的结构光扫描系统返回60Hz的深度图片。如果可以在图片产生之时就进行匹配，那么用户就会拿到一个实时扫描的模型，这样即直观又可以让用户填补模型上的“洞“。让用户以这种方式进行扫描至少是对“next best view”问题的一种替代解决方案，至少对小型手持物体来说是这样的。实时ICP的另一种应用对刚体模型的追踪。

结论

我们归类并对比了几种ICP的变种算法，我们主要关注不同算法间的收敛速度。我们介绍了一种对小且稀疏特征场景可以快速收敛的采样方式。最终，我们展示了一种使用固定时长寻找匹配点的ICP的优化算法，使得两个网格可以在几十毫秒内完成匹配。由于当前我们主要是对收敛速度进行的对比，但是我们预测未来的ICP变种更加注重鲁棒性及准确性。此外，未来会更加关注实际中含噪数据中，不同种类的噪声及干扰对匹配算法影响。

Abstract

The ICP (Iterative Closest Point) algorithm is widely used for geometric alignment of three-dimensional models when an initialestimate of the relative pose is known. Many variants of ICP havebeen proposed, affecting all phases of the algorithm from the selection and matching of points to the minimization strategy. Weenumerate and classify many of these variants, and evaluate theireffect on the speed with which the correct alignment is reached.In order to improve convergence for nearly-flat meshes with smallfeatures, such as inscribed surfaces, we introduce a new variantbased on uniform sampling of the space of normals. We concludeby proposing a combination of ICP variants optimized for highspeed. We demonstrate an implementation that is able to aligntwo range images in a few tens of milliseconds, assuming a goodinitial guess. This capability has potential application to real-time3D model acquisition and model-based tracking.

如果你对本文感兴趣，想要下载完整文章进行阅读，可以关注【泡泡机器人SLAM】公众号。

欢迎来到泡泡论坛，这里有大牛为你解答关于SLAM的任何疑惑。

有想问的问题，或者想刷帖回答问题，泡泡论坛欢迎你！

泡泡网站：www.paopaorobot.org

泡泡论坛：http://paopaorobot.org/forums/

泡泡机器人SLAM的原创内容均由泡泡机器人的成员花费大量心血制作而成，希望大家珍惜我们的劳动成果，转载请务必注明出自【泡泡机器人SLAM】微信公众号，否则侵权必究！同时，我们也欢迎各位转载到自己的朋友圈，让更多的人能进入到SLAM这个领域中，让我们共同为推进中国的SLAM事业而努力！

商业合作及转载请联系liufuqiang_robot@hotmail.com