极端外点率下鲁棒配准的多项式时间解

论文地址
论文视频

文章导读

为什么要解读这篇文章？因为之前接连介绍该作者的两个工作，TEASER | 快速且可证明的点云配准算法和代码解读 和 基于四元数的存在外点Wahba问题的可证明最优解，前者的未知有界噪声，几何不变测量，内点选择最大团和SDP松弛思想均来自该工作，而后者和该工作共同组成了TEASER。所以为了彻底理解TEASER，就不得介绍本文。本文使用截断最小二乘将点云配准问题转化为优化问题，然后设计出可处理高外点率的多项式时间算法进行相对变换（尺度，旋转和平移）的计算。

摘要

提出了一种在存在大量外点的情况下两组3D点的鲁棒配准方法。第一个贡献是使用截断最小二乘（TLS）代价重新建模配准问题，该代价使得估计对大量外点不敏感。第二个贡献是一个解耦旋转、平移和尺度估计的通用框架，该框架允许级联地求解这三个量。但是每个子问题（尺度，旋转和平移估计）仍然是非凸和组合的，所以第三个贡献是证明（i）adaptive voting机制可以在多项式时间内精确地求解TLS尺度和分量形式的平移估计，（ii）TLS旋转估计可以被松弛为半定规划，并且该松弛实际上是紧的，甚至在极端外点率情况下也仍然是紧的。将提出的算法命名为TEASER（截断最小二乘估计和半定松弛），并在标准的3D配准基准上验证该算法，实验结果证明其超越了RANSAC和鲁棒的局部优化方法，比Branch-and-Bound方法效果更好。与此同时，这还是一个多项时间算法，十分快速。此外，TEASER可以处理高达99%外点率的情况，同时给出一个高精度的解。

动机

1. 能够全局地求解配准问题，不需要依赖初始值；
2. 能够忍受极端的外点数量，如99%的测量值都是外点；
3. 能够在多项时间内运行；
4. 能够提供正式的性能保证，也就是全局最优性保证。

主要贡献

1. 使用截断最小二乘（TLS）代价重新建模配准问题，该代价对大量外点不敏感。将产生的问题称为截断最小二乘配准（TR）问题；
2. 分离尺度，旋转和平移估计的通用框架。该方法的创新性有三个方面：（i）开发估计尺度的不变测量，（ii）在未知但有界噪声的框架下，将分离形式化。解耦使得可以级联地求解尺度，旋转和平移；
3. 证明（i）使用adaptive voting机制能够在多项式时间内精确地求解标量情况的TLS估计，这样可以高效地估计尺度和（分量形式的）平移；（ii）通过寻找由不变测量定义的图的最大团来修剪大量的外点；（iii）建立一个紧的半定规划（SDP）松弛来估计旋转，（iv）在SDP松弛的性能上提供每个实例的界限。这是第一个可计算性能保证的外点鲁棒配准问题的多项式时间算法。

算法流程

1. 使用截断最小二乘代价函数的鲁棒配准
   1.1 原始问题
   给定两组点云 A = { a i } i = 1 N \mathcal{A}=\left\{ a_i \right\}^N_{i=1} A={ai​}i=1N​ 和 B = { b i } i = 1 N \mathcal{B}=\left\{ b_i \right\}^N_{i=1} B={bi​}i=1N​，满足：
   
   其中， ϵ i \epsilon_i ϵi​为测量噪声， o i o_i oi​为inlier-outlier向量（内点为0向量，外点为任意向量）。
   1.2 截断最小二乘配准模型
   当一部分对应点云是外点时，需要引入鲁棒的模型去处理它们，这里引入截断最小二乘配准模型：
   
2. 解耦尺度，旋转和平移估计
   这部分内容是这篇文章的一大贡献，利用仿射变换具有空间距离不变性的思想，也就是分别来自两组点云的两个点之间的线段长度是（近似）相等的，进而重新转换测量值以得到尺度、旋转和平移变换的不变量。
   2.1 平移不变测量（TIM）
   点的绝对位置是依赖于平移量 t t t，但是两个点之间的相对位置对于平移量是不变的，那么求取两组点 a i a_i ai​ 和 b i b_i bi​ 之间的相对位置就抵消掉了平移量 t t t：
   
   因为，平移不变测量定义为 a ˉ i j = . a j − a i \bar{a}_{ij} \overset{.}{=} a_j-a_i aˉij​=.aj​−ai​ 和 b ˉ i j = . b j − b i \bar{b}_{ij} \overset{.}{=} b_j-b_i bˉij​=.bj​−bi​，它们满足以下模型：
   
   可以看到这个模型只依赖于未知的尺度 s s s 和旋转量 R R R，该不变量思想如图所示
   
   2.2 平移和旋转不变测量（TRIM）
   TIM 还是依赖于旋转量 R R R，但TIM的模长对于旋转量 R R R 和平移量 t t t 都是不变的，因此首先计算 TIM 的范数：
   
   这里使用有界噪声，那么就可以得到：
   
   然后将上式两边同时除以 ∣ ∣ a ˉ i j ∣ ∣ ||\bar{a}_{ij}|| ∣∣aˉij​∣∣，就可以得到新的不变测量值 s i j = . ∣ ∣ b ˉ i j ∣ ∣ ∣ ∣ a ˉ i j ∣ ∣ s_{ij} \overset{.}{=} \frac{||\bar{b}_{ij}||}{||\bar{a}_{ij}||} sij​=.∣∣aˉij​∣∣∣∣bˉij​∣∣​：
   
   可以看到这个测量值仅仅依赖于未知的尺度 s s s，该不变量思想如图所示
   
   2.3 上述不变测量值的总结
   
3. 配准算法：截断最小二乘估计和半定松弛（TEASER）
   3.1 鲁棒尺度估计
   使用平移和旋转不变测量 s k s_k sk​ 和估计尺度 s ^ \hat{s} s^，采用第4部分介绍的adaptive voting 算法进行估计：
   
   3.2 鲁棒旋转估计
   使用上式得到的尺度估计 s ^ \hat{s} s^ 和平移不变测量TIM估计旋转 R ^ \hat{R} R^，采用第5部分介绍的半定松弛和快速证实算法进行估计：
   
   3.3 鲁棒平移估计
   在截断最小二乘配准模型中使用上面得到的尺度估计 s ^ \hat{s} s^ 和旋转估计 R ^ \hat{R} R^，从 ( a i , b i ) (a_i,b_i) (ai​,bi​) 估计粗平移 t ^ \hat{t} t^ 的三个分量，采用第4部分介绍的 adaptive voting 算法进行三个分量的估计：
   
   3.4 TEASER算法
   
4. 尺度，旋转和平移三个子问题的具体求解
   4.1 鲁棒的尺度估计
   给定标量尺度 s s s，定义一致集 C ( s ) = { k : ( s − s k ) α k 2 ≤ c ˉ 2 } \mathcal{C}(s)=\left\{ k: \frac{(s-s_k)}{\alpha^2_k} \le \bar{c}^2 \right\} C(s)={k:αk2​(s−sk​)​≤cˉ2}。对任何 s s s，最多有 2 K − 1 2K-1 2K−1 个不同的非空一致集，将这些一致集命名为 C 1 , . . . , C 2 K − 1 \mathcal{C_1},...,\mathcal{C_{2K-1}} C1​,...,C2K−1​，那么可以通过枚举公式（6）的解：
   
   上式可以直接采用 adaptive voting 算法来求取
   
   上述算法第4行见Fig. 3(a)，第6、12行见Fig. 3(b)
   
   4.2 鲁棒的旋转估计
   这部分是本文的另一大贡献，设计一个计算旋转估计的紧的凸松弛，并且该松弛对于高外点率情况仍然能够保持紧度。
   4.2.1 二值模型和克隆
   引入辅助的二值变量 θ k \theta_k θk​，将（7）改写为：
   
   然后使用合适的正交矩阵代替二值变量，将（10）改写为以下二值克隆问题：
   
   4.2.2 凸松弛
   将（11）中所有未知变量堆叠起来，组成一个 3 × 3 ( K + 2 ) 3 \times 3(K+2) 3×3(K+2) 矩阵 X = [ I 3 , R , R 1 , . . . , R K ] X=[I_3,R,R_1,...,R_K] X=[I3​,R,R1​,...,RK​]，然后可以发现矩阵 Z = X X T Z=XX^T Z=XXT 的元素包含所有 R R R 和 R K R_K RK​ 的线性项和二次项：
   
   进一步发现（11）中的目标函数和约束都可以使用矩阵 Z Z Z 的函数来表示，并且 Z Z Z 是秩为3的半正定矩阵，那么就可以使用 Z Z Z 来改写问题（11），从而设计出一个凸松弛：
   
   其中用到的技巧是在添加冗余约束（（13）中最后两个约束）和舍弃秩约束（ r a n k ( Z ) = 3 rank(Z)=3 rank(Z)=3），因此（13）是（11）的凸松弛，可以使用凸算子在多项式时间内求解得到最优解 Z ∗ Z^* Z∗。如果 Z ∗ Z^* Z∗ 的秩为3，可以将其分解为 Z ∗ = ( X ∗ ) T ( X ∗ ) Z^*=(X^*)^T(X^*) Z∗=(X∗)T(X∗)， X ∗ = . [ I 3 , R ∗ , R 1 ∗ , . . . , R K ∗ ] X^*\overset{.}{=}[I_3,R^*,R^*_1,...,R^*_K] X∗=.[I3​,R∗,R1∗​,...,RK∗​] 是矩阵 Z ∗ Z^* Z∗ 的第一行矩阵块，并且 R ∗ , R 1 ∗ , . . . , R K ∗ R^*,R^*_1,...,R^*_K R∗,R1∗​,...,RK∗​ 是（11）的最优解。
   这里作者并没有给出这个凸松弛紧度的分析，也就是没有从理论上证明该凸松弛是紧的，而是通过后续的实验结果从经验上说明该松弛是紧的（也就是产生秩为3的解）。那么问题是，如果该凸松弛得到的解不是紧的，即 Z ∗ Z^* Z∗ 的秩不为3，该怎么办？其实可以通过将 Z ∗ Z^* Z∗ 投影到流形 O ( 3 ) O(3) O(3) 得到结果解的次优程度的上界，作为旋转估计 R ^ \hat{R} R^。
   4.3 鲁棒的平移估计
   类似于4.1，同样可以使用 adaptive voting 算法来求解平移估计，也就是使用三次算法2分别求解平移向量的三个分量 t ^ j \hat{t}_j t^j​，得到每个分量的估计值，最终组成平移估计值 t ^ = [ t ^ 1   t ^ 2   t ^ 3 ] T \hat{t}=[\hat{t}_1 \ \hat{t}_2 \ \hat{t}_3]^T t^=[t^1​ t^2​ t^3​]T：
   

主要实验结果

1. 标准数据集的benchmarking
   未知尺度情况下，与Fast Global Registration (FGR)、Guaranteed Outlier REmoval (GORE) 和RANSAC两种变体进行精度的比较，分别评估尺度，旋转和平移误差
   
2. 极端外点率（外点率为95%-99%）的测试
   
3. 目标位姿估计和定位
   输入为含噪声的FPFH特征描述子建立的对应点，其中含有大量外点（蓝色线），绿色线为内点，红色部分为最终配准的目标
   

总结

这个工作提出了一个基于截断最小二乘模型计算相对变换（尺度，旋转和平移）的算法，用于极端外点率情况的点云配准问题。虽然该方法对外点很鲁棒，计算速度也比较快，但也是存在一些问题和改进点的：

1. 实验中问题规模不大，这里受限制的原因是通用的SDP算子在大规模问题上会计算很慢，可以预见该方法在大规模点云配准上会表现不佳，作者也没有给出算法的效率测试，所以可以通过设计特定的SDP算子来实时地求解大规模配准问题，可以参考 IJRR18 的经典论文 “SE-Sync: a certifiably correct algorithm for synchronization over the Special Euclidean group.”；
2. 旋转估计中使用的凸松弛，并不是一个经过理论证明（certifiable）的紧凸松弛，不过作者在之后的TRO20 TEASER 工作中对其进行了证明，从理论上分析和保证了紧度。
   该工作使用的估计理论中的未知但有界噪声，几何中的不变测量，图理论中的内点选择最大团和优化中的SDP松弛这些理论和技巧均出现在之前介绍过的作者TRO20 TEASER工作中；该工作的旋转估计部分在作者ICCV2019 “A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers”中进行了改进，即将旋转参数化为四元数。所以该工作和ICCV2019共同组成了TEASER的前置工作，说明了作者这一系列工作的连贯性，并且这些工作都是理论和开源效果俱佳，非常值得关注和学习。