点云配准 -- ICP 算法

1 问题描述

点云配准(Point Cloud Registration)指的是输入两幅点云 P_s (source) 和 P_t (target) ,输出一个变换 T 使得 T(P_s)P_t 的重合程度尽可能高。变换 T 可以是刚性的(rigid),也可以不是,本文下面只考虑刚性变换,即变换只包括旋转、平移。

点云配准可以分为粗配准(Coarse Registration)和精配准(Fine Registration)两步。粗配准指的是在两幅点云之间的变换完全未知的情况下进行较为粗糙的配准,目的主要是为精配准提供较好的变换初值;精配准则是给定一个初始变换,进一步优化得到更精确的变换。

目前应用最广泛的点云精配准算法是迭代最近点算法(Iterative Closest Point, ICP)及各种变种 ICP 算法。

2 算法描述

ICP 算法的直观想法如下:

  • 如果我们知道两幅点云上点的对应关系,那么我们可以用 Least Squares 来求解 R, t 参数;
  • 怎么知道点的对应关系呢?如果我们已经知道了一个大概靠谱的 R, t 参数,那么我们可以通过贪心的方式找两幅点云上点的对应关系(直接找距离最近的点作为对应点)。

ICP 算法实际上就是交替进行上述两个步骤,迭代进行计算,直到收敛。

ICP 一般算法流程为:

  1. 点云预处理
    • 滤波、清理数据等
  2. 匹配
    • 应用上一步求解出的变换,找最近点
  3. 加权
    • 调整一些对应点对的权重
  4. 剔除不合理的对应点对
  5. 计算 loss
  6. 最小化 loss,求解当前最优变换
  7. 回到步骤 2. 进行迭代,直到收敛

整体上来看,ICP 把点云配准问题拆分成了两个子问题:

  • 找最近点
  • 找最优变换

2.1 Find Closet Point

2.2 Find Best Transform

(未完待续)