📝笔记：AdaLAM: Revisiting Handcrafted Outlier Detection 超强外点滤除算法

AdaLAM的全称是Adaptive Locally-Affine Matching(自适应局部仿射匹配)，本文提出了一种高效快速外点滤除算法。

先祭出Github Repo:

原有技术问题

在图像匹配任务中初始匹配中外点较多，目前难以高效快速地滤除外点。

新技术创新点

1. 基于目前已有的外点滤除算法（spatial matching），提出了现有的鲁棒快速的图像一致性空域验证算法；
2. 本框架基于一种几何假设（局部仿射），场景实用性较强；经实验验证，该算法目前达到了SOTA（很自信啊）。

新技术主要框架以及关键技术点

总共分四步：

1. 找到初始匹配（最近邻top1）;
2. 找到置信度高且分布较好的点作为“种子点”；
3. 在初始匹配中选择与该种子点在同一个区域的匹配点；
4. 保留那些局部一致较好匹配；

接下来重点介绍后3点。

种子点选择

将ratio-test得到的最优次优比作为左图上匹配点的匹配置信度，选择那些在半径$R$内匹配置信度最大的点作为种子点。由于每个匹配点都是独立的，此时可用GPU对该过程进行并行加速。

局部选择与过滤

接下来要寻找一些可以支持种子匹配的匹配对。

令$S_i=({\mathbf{x}}_1^{S_i},{\mathbf{x}}_2^{S_i})$，其中${\mathbf{x}}_1^{S_i},{\mathbf{x}}_2^{S_i}$分别表示两张图上的第$i$个种子匹配对，它们之间符合相似变换（即旋转+缩放，其中旋转${\alpha }^{S_i}={\alpha }_2^{S_i}-{\alpha }_1^{S_i}$, 缩放为${\sigma }^{S_i}={\sigma }_2^{S_i}/{\sigma }_1^{S_i}$）。那么对于任意匹配$(p_1,p_2)=(({\mathbf{x}}_1,{\mathbf{d}}_1,{\sigma }_1,{\alpha }_1),({\mathbf{x}}_2,{\mathbf{d}}_2,{\sigma }_2,{\alpha }_2))\in \mathcal{M}$，其中$\mathbf{d}$表示描述子，如果上述匹配满足如下约束关系，就能够被纳入到支持种子点的匹配集合${\mathcal{N}}_i\subseteq \mathcal{M}$中，该约束关系为：

$$\begin{array}{}\text{(1)}& \begin{array}{c}(\Vert {\mathbf{x}}_1^{S_i}-{\mathbf{x}}_1\Vert \le \lambda R_1)\wedge (\Vert {\mathbf{x}}_2^{S_i}-{\mathbf{x}}_2\Vert \le \lambda R_2)\end{array}\end{array}$$

$$\begin{array}{}\text{(2)}& \begin{array}{c}(|{\alpha }^{S_i}-{\alpha }^p|\le t_{\alpha })\wedge (|\ln \left(\frac{{\sigma }^{S_i}}{{\sigma }^p}\right)|\le t_{\sigma })\end{array}\end{array}$$

上式中${\alpha }^p={\alpha }_2-{\alpha }_1,{\sigma }^p={\sigma }_2/{\sigma }_1$表示两个匹配点之间的角度与尺度差异；$R_1$与$R_2$分别表示图像$I_1$与$I_2$的种子点扩散半径；$\lambda$表示邻域圈圈的覆盖程度的正则项。

上面的第一个式子表示：初始匹配中与种子点相对位置差不多且在半径在$\lambda R$的匹配会加入到${\mathcal{N}}_i$；第二个式子告诉我们：上面加入的这些匹配对需要满足角度以及尺度一致性才能够被加入，否则免谈。上面的两个条件需要同时满足才能得到${\mathcal{N}}_i$。

自适应仿射校验

我们假设匹配对之间符合局部仿射变换，即上述的每个${\mathcal{N}}_i$都满足该假设，那么接下来可利用该假设去滤除一些错误的匹配对：使用RANSAC的思想找到最小解集去拟合仿射矩阵，然后滤除置信度低的匹配对。

由于仅使用2对匹配点就可以得到仿射矩阵，那么即使对每个圈圈求仿射也并不耗时。对于第$j$次迭代，我们可以得到匹配关系$k$，对于集合${\mathcal{N}}_i$，我们可以从中随机选择一对匹配${\mathbf{x}}_1^k,{\mathbf{x}}_2^k$，进而得到二者之间的仿射矩阵$A_i^j$，然后我们就可以得到匹配关系对两个匹配对产生的残差，如下式：

$$\begin{array}{}\text{(3)}& r_k\left(A_i^j\right)=\Vert A_i^j{\mathbf{x}}_1^k-{\mathbf{x}}_2^k\Vert \end{array}$$

然后作者参考文献³⁶，设计了置信度$c_k$（不展开讲），当置信度大于某个阈值，表示该模型对该匹配关系拟合的较好，视该匹配被视为内点；否则为外点。

注意每次迭代需要更新上述残差/置信度以及内点，后一次利用前一次得到的内点去拟合新的仿射矩阵，然后做校验，直至达到最大迭代次数，最后输出内点。

实验

看到没，竟然超过了效果极好的GMS。

实时性：在RTX2080Ti平台下处理4000-8000个点耗时15-25ms。

借鉴意义

本文提出了一种高效快速的外点滤除算法，可加入到任何特征匹配算法中，预期能够提高位姿解算的精度。但上述实验结果中对GPU的要求较高，目前不清楚在低配版GPU或者在CPU平台下的表现。

附录

1. Paper: AdaLAM: Revisiting Handcrafted Outlier Detection