计算两组点之间的三维变换

Question

使用Microsoft Kinect，我正在收集有关对象的深度数据。从这些数据中，我创建了一个点云（point cloud），当绘制时，它允许我查看使用Kinect扫描的对象。

但是，我希望能够从不同的“视图”中收集多个点云并将它们对齐。更具体地说，我想使用诸如Iterative Closest Point (ICP)之类的算法来实现，通过计算我收集的每个云和以前收集的云之间的旋转和平移来转换点云中的每个点。

然而，虽然我了解ICP背后的过程，但我不知道如何在3D中实现它，也许是我缺乏数学经验，或者缺乏OpenCV等框架的经验，但我找不到解决方案。我想避免使用点云库之类的库，因为我想自己做。

任何和所有的建议都是值得赞赏的（如果有一个涉及OpenCV/python的解决方案，我可以进行研究，那会更好！）

Answer 1

我目前正在与国际比较项目斗争。以下是我迄今为止收集到的资料：

国际比较项目包括三个步骤：

• 给定两个点云A和B，在A和B之间找到可能表示空间中相同点的点对。通常，只需将每个点与其在另一个云中最近的相邻点匹配即可完成此操作，但可以使用其他特征（例如颜色、纹理或曲面法线）来改进匹配。然后可以选择丢弃最差的匹配项。
• 给出对应对的列表，找到从A到B的最佳转换
• 将此转换应用于
• 重复这三个步骤，直到找到一个可接受的解决方案。

第一步很简单，虽然有很多方法可以优化它的速度，因为这是ICP的主要性能瓶颈；提高精度，因为这是误差的主要来源。OpenCV可以帮助您处理FLANN library。

我想你的麻烦在于第二步，在给出一个对应关系列表的情况下，找到最佳的转换。

一种常见的方法可以与Singular Value Decomposition (SVD)一起使用。这是算法的草图。对ICP&SVD的研究将提供更多的参考。

• 取对应点A₁的列表。A_n和B₁。B_n从步骤1开始
• 计算a中所有点的质心C_a，b中所有点的质心C_b
• 计算3x3协方差矩阵M
  M=（A₁-C_A）*（B₁-C_B）^T+。。。+（A_n-C_A）*（B_n-C_B）^T
• 使用SVD计算M
  的3x3矩阵U和V （OpenCV有一个function to perform SVD）
• 计算R=U*V^{T
  这是你想要的最佳旋转矩阵。}
• 计算最佳平移为C_b-R*C_a
• 最佳转换是R和这个翻译的组合

请注意，我自己还没有实现这个算法，所以我只是解释我读到的内容。

Answer 2

OpenCV-contrib（曲面匹配模块）中提出了一种新的ICP算法。它还受益于各种类型的变体（包括Rusinkievicz等）：

http://docs.opencv.org/3.0-beta/modules/surface_matching/doc/surface_matching.html

对于MATLAB实现： http://www.mathworks.co.jp/matlabcentral/fileexchange/47152-icp-registration-using-efficient-variants-and-multi-resolution-scheme/content/icp_mod_point_plane_pyr.m

Answer 3

在Rusinkievicz的旧论文here中可以找到对国际比较项目的非常好的介绍，包括加速变体。