点云配准：ICP 方法对比

Edgar Maass

4.83/5 (8投票s)

2015年1月16日

GPL3

11分钟阅读

96369

5012

通过 ICP（迭代最近点）方法对点云进行对齐（又名拼接、配准）的各种方法比较

引言

本文介绍了“迭代最近点”算法的 4 种变体的实现。

本文内容
- 简要比较 ICP 变体的数学背景
- 讨论和示例，重点介绍缩放变换，特别是非均匀缩放
- 所有讨论的 ICP 变体的平移、旋转和缩放变换的示例和比较
- ICP 算法可能失效的点云示例

我的目标也是展示 ICP 算法在基本层面上仍然可能遇到的收敛问题——主要是为了找到源点云和目标点云之间点的正确对应关系。这项工作正在进行中：也许有些人会花一些时间在评论中。在我看来，在处理 ICP 中的非线性问题（如文献中高度研究的异常值等）之前，应该先解决这些收敛和基本问题。

该领域有大量的文献，也有一些源代码，但我没有找到对不同方法进行系统比较并包含源代码的，以便日后用于自己的实现。

背景

ICP 算法用于将从不同角度拍摄的点云对齐（拼接、配准）到单个 3D 点云。

“对齐”（配准、拼接）点云是什么意思？

这意味着将一个 2D 或 3D 点云（源点云）匹配到另一个（目标点云）。
在 2D 中，这个问题是众所周知的并且已经解决，许多程序可以“拼接”从不同角度拍摄的照片以形成全景照片。

迭代最近点方法简介

问题陈述：将一个点云（源）匹配到另一个（目标）

对于源点云中的每个点，找到目标点云中的最近点。这可以通过 “k-d 树”搜索算法来高效完成
计算变换（旋转、平移和缩放的组合）
这是通过最小化均方误差成本函数来完成的，如参考文献 [1]-[5] 所示。它涉及求解例如特征值系统或使用四元数数学，这属于高等大学数学的范畴。
使用获得的变换来变换源点。
检查点云是否在所需的阈值内匹配。如果不是，则转到步骤 1 - 再次迭代

所讨论的不同 ICP 方法的数学背景

有许多不同的 ICP 方法在数百篇出版物中得到实现。它们之间的区别可以根据 ICP 方法的 4 个步骤进行分类（参见“ICP 方法简介”中的 4 点）。

1. 用于查找源点云和目标点云之间点对应关系的不同算法。
如果假设源点云中有 N 个点，目标点云中有 N 个点，则“暴力破解”方法需要 N*N 次运算，速度非常慢。k-d 树在 (N ln N) 次运算中完成这项工作。还有 Octree 或其他变体，速度基本相同。

2. 计算两个点云之间变换的不同方法

对于刚性（平移、旋转）和仿射（缩放）变换，大多数方法都使用数学驱动的解决方案，因为仿射变换有一个数学上封闭的解。一些（但非常少）使用其他方法，例如概率方法（如蒙特卡洛）。

对于旋转和平移，Horn 的原始 ICP 文章 [1] 提出了一个四元数方法。这已被证明（在参考文献 [6] 的文章中）基本上等同于其他方法，例如：
- [3]、[4] 和 [5] 中也使用的 SVD（奇异值分解）方法，最初由 [7] 提出
- 使用正交矩阵的方法方法参见 [2]
- 双四元数方法 [8]

然而，在尺度变换方面存在差异。1987 年的原始 ICP 方法不包含尺度变换，但 Horn 在其 1988 年的出版物 [2] 中添加了这一项。
在现实世界中，尺度变换很重要，试想一下，你从一个角度拍摄了点云，然后靠近目标以拍摄第二个点云。这基本上是一个尺度变换。
[3] 和 [4] 中对尺度变换进行了比较容易理解的讨论。
在我实现的`代码`中，有四种不同的方法来包含缩放
- 如 [2] 的“Horn”方法在正交矩阵层面
- “Umeyama”[3] 方法在特征值层面推导尺度因子（他的数学证明很精彩 :) ）
- “Zinsser”[4] 方法将尺度因子推导为偏导数
- “Du”[5] 方法类似于 [4]，但将三个尺度因子（用于 3 个几何轴）推导为偏导数

3. ICP 的其他差异涉及如何处理小的测量误差、异常值和缺失点。
测量误差很常见——由于扫描精度不足：空间中的同一点在源点云和目标点云中由略微不同的坐标表示。在一定程度上，这已包含在基本算法中。
异常值是错误测量的点，应忽略。
缺失点是指一个点云中在另一个点云中没有对应关系的点。这是期望的效果：通过从另一个角度扫描目标，你当然会得到第一个扫描中不存在的点。

由于这三种效应高度非线性，因此发表了许多不同的实现，带有权重因子等。方法不能真正进行比较，因为在许多情况下实现细节不完整，当然，他们主要发布点云的有效示例。最好也能发布无效的示例，这将有助于方法比较。

还有一些方法可以找到源点云和目标点云中的一些相同点子集（例如，通过比较颜色或光强度）。

比较 [1]-[4] 的 ICP 方法

- Umeyama [3] 和 Zinsser [4] 的行为相同，尽管方法不同。它们在平移、旋转和均匀缩放时给出相同的结果。（均匀缩放意味着所有 3 个空间方向的尺度因子都相同）

- Horn [2] 方法在缩放时与 [3] 和 [4] 的行为略有不同：收敛行为不同（有时更快，有时慢得多），并且单次迭代的性能较慢，至少在我使用的实现中是这样，该实现是从 VTK 库移植的。我发现有些情况下 [3] 和 [4] 会陷入错误的局部最小值，但 Horn [2] 方法表现良好，而有些情况下则相反，请参阅下面的示例。

- Du [5] 方法是唯一适用于非均匀缩放变换的方法。这很清楚，因为其他方法根据定义对所有 3 个方向具有相同的尺度因子。这对于真实对象来说应该更好，因为您需要考虑被扫描对象的非线性变换。
Du 方法的收敛速度比其他方法慢。

使用代码

要运行示例，您需要先安装 NUnit，然后在 Visual Studio 项目中配置 NUnit exe 的路径，以便运行测试。

提示：我未能使用使用 .NET 2.0 的 NUnit 2.6，但使用 .NET 4.5 编译了 NUnit。NUnit 3.0（alpha 版本）可能也有效——我没有尝试过。

测试用例概述

下面讨论的测试用例位于“UI”和“ExpectedError”文件夹中

其他是正在进行中的，或者是“自动化”的：一组运行速度很快的小型测试用例，每次程序更改后都必须正常工作。

1. Cube 代码库（测试用例位于类：ICP_Test5_Cube）

从左到右：平移、旋转、均匀缩放、非均匀缩放、平移 + 旋转 + 缩放

颜色编码：
- 源点云为白色
- 目标为绿色
- 红色用于变换后的点云。

如果屏幕上没有任何红色，则目标（绿色）与变换后的点云重叠，因此 ICP 结果为“成功”，匹配率为 100%。

1.a Cube 平移示例

在测试用例中

ICPTest5_Cube.Cube_Translate

此方法代码，简要说明

 [TestFixture]
 [Category("UnitTest")]
 public class ICPTest5_Cube : ICPTestBase
 {
             
        [Test]
        public void Cube_Translate()
        {
            Reset();
            IterativeClosestPointTransform.ICPVersion = ICP_VersionUsed.Horn;
            IterativeClosestPointTransform.FixedTestPoints = true;
            IterativeClosestPointTransform.ResetVertexToOrigin = false;

            ICPTestData.Test5_CubeTranslation(ref verticesTarget, ref verticesSource, 
                 ref verticesResult);
          
            this.ShowResultsInWindow_CubeLines(false);
            Assert.IsTrue(ICPTestData.CheckResult(verticesTarget, verticesResult, 1e-10));
 }

代码解释

IterativeClosestPointTransform.ICPVersion = ICP_VersionUsed.Horn;
使用的 ICP 方法是“Horn”方法（参见 [2]）
-IterativeClosestPointTransform.FixedTestPoints = true;
对于立方体，假设源点和目标点之间的关系是已知的，这在 FixedTestPoints 参数中配置
-IterativeClosestPointTransform.ResetVertexToOrigin = false;
有可能将所有点云变换到坐标系的原点。这基本上是一个平移（参见例如参考 [2]），在这种情况下，无需进一步进行 ICP。因此，此参数设置为 false，以便可以看到平移 ICP 的效果。

如果您运行单元测试，您会看到类似这样的内容

1.b Cube 旋转

ICPTest5_Cube.Cube_Rotate

1.c Cube - 均匀缩放（所有 3 个轴的缩放因子相同）

ICPTest5_Cube.Cube_Scale_Uniform

1.d Cube - 非均匀缩放（所有 3 个轴的缩放因子不同）

ICPTest5_Cube.Cube_ScaleInhomogenous_Du

1.e 平移、旋转和均匀缩放

ICPTest5_Cube.Cube_RotateTranslate_ScaleUniform_Umeyama

2. Bunny，变换后

ICPTest6_Bunny.Horn

3. 一个脸部 - 由 Microsoft Kinect 扫描，变换后

测试用例

ICPTest6_Bunny.Horn

该脸部旋转 30 度，平移一个小向量，并按 0.8 的比例缩放

这是在方法中完成的： ICPTestData.Test7_Face_KnownTransformation

VertexUtils.ScaleByFactor(myVerticesSource, 0.8);
Matrix3d R = new Matrix3d();
R = R.Rotation30Degrees();
VertexUtils.RotateVertices(myVerticesSource, R);
VertexUtils.TranslateVertices(myVerticesSource,  -0.15, 0.05, 0.02);

这 4 种方法研究的收敛行为不同。Umeyama [2] 和 Zinsser [3] 方法收敛效果最好——经过 35 次迭代。目标和结果之间的重叠率为 100%。使用 Horn 或 Du 方法，经过 50 次迭代后，结果点和目标点之间的平均距离仍然大于 1 毫米。

ICP 示例，无效

如果 ICP 未收敛，变换后的（红色）点云将不会与绿色点云（目标）重叠。因此，您会看到 3 个物体。

1. Horn 方法的非均匀尺度变换
预期错误：使用方法 1-3 将不会收敛，这是显而易见的。只有使用 Du [5] 方法才能收敛，请参阅背景部分中的解释。

ICPTest5_Cube_ExpectedError.Cube_ScaleInhomogenous_Horn()

2. Bunny 对象，旋转 65 度
也不会收敛到目标。我认为这是 k-d 树算法中查找点正确对应关系的问题。

ICPTest6_Bunny_ExpectedError.Horn()

3. 脸部 - 从不同角度扫描两次
未收敛

ICPTest9_Face_ExpectedError.Umeyama

结论

展示了 4 种主要 ICP 方法之间的一些基本差异，特别是缩放点云的行为很重要。
在我的实现中，即使对模型进行一些简单的变换，ICP 方法也无法收敛。可以轻松构造更多情况。原因主要是查找源点和目标点之间的正确对应关系。假设点对应关系子集已知的机制（例如，通过颜色、光强度）有所帮助。

我渴望从读者那里获得关于如何改进代码以及可能是我做错了什么的信息。我很感谢任何文章链接或提示！

参考文献

“Horn”ICP 方法
-Berthold K. P. Horn (1987), “Closed-form solution of absolute orientation using unit quaternions” in Journal of the Optical Society of America A, vol. 4, page 629-642. See article link
Horn BKP, Hilden HM, Negahdaripour S (1988), "Closed-form solution of
absolute orientation using orthonormal matrices", J Opt Soc Am Ser A, vol 5, page 1127–1135
-此方法最初的 Python 实现由 David G. Gobbi 完成，后来在 VTK 库中有一个 C++ 移植版本，我将其移植到了 C#。
“Umeyama” ICP 方法
Umeyama (1991), "Least-squares estimation of transformation parameters between two point patterns", IEEE Transactions On Pattern Analysis And Machine Intelligence, vol. 13, no. 4, page 376–380
“Zinsser” ICP 方法
Timo Zinßer, Jochen Schmidt, Heinrich Niemann (2003), “A REFINED ICP ALGORITHM FOR ROBUST 3-D CORRESPONDENCE ESTIMATION” in IEEE International Conference on Image Processing, September 2003, Barcelona, Spain
“Du” ICP 方法
Shaoyi Du, Nanning Zheng, Shihui Ying, Qubo You, Yang Wu (2007), “AN EXTENSION OF THE ICP ALGORITHM CONSIDERING SCALE FACTOR”, in Conference Image Processing, 2007. ICIP 2007. IEEE International Conference on, Volume: 5, see link
ICP 方法比较
D.W. Eggert, A. Lorusso, R.B. Fisher (1997), “Estimating 3-D rigid body transformations: a comparison of four major algorithms”, Machine Vision and Applications, vol. 9, page 272–290, Springer-Verlag.
K. S. Arun, T. S. Huang, and S. D. Blostein. Least square fitting of two 3-d point sets. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(5):698 – 700, 1987.
M. W. Walker, L. Shao, and R. A. Volz. Estimating 3-d location parameters using dual number quaternions. CVGIP: Image Understanding, 54:358 – 367, November 1991.

其他使用的代码

VTK 库 - 部分代码被移植，主要是 Horn [1] 方法
我的 OpenTK Code Project 文章中的 OpenTK 控件以及那里使用的代码列表

关注点

进一步的工作

- 研究和改进收敛性
- 将该方法应用于扫描数据，进一步研究收敛问题
- 包含非均匀变换。例如，通过“Du”方法扩展到其他变换
- 加快迭代收敛速度
- 包含异常值，提高精度

另请参阅

点云查看器文章

历史

版本 0.9.0.6 提交于 2015/1/16