📝笔记：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}=\left(\mathbf{x}_{1}^{S_{i}}, \mathbf{x}_{2}^{S_{i}}\right)\)，其中\(\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}}\)）。那么对于任意匹配\(\left(p_{1}, p_{2}\right)=\left(\left(\mathbf{x}_{1}, \mathbf{d}_{1}, \sigma_{1}, \alpha_{1}\right),\left(\mathbf{x}_{2}, \mathbf{d}_{2}, \sigma_{2}, \alpha_{2}\right)\right) \in \mathcal{M}\)，其中\(\mathbf{d}\)表示描述子，如果上述匹配满足如下约束关系，就能够被纳入到支持种子点的匹配集合\(\mathcal{N}_{i} \subseteq \mathcal{M}\)中，该约束关系为：

\[ \begin{array}{c} \left(\left\|\mathbf{x}_{1}^{S_{i}}-\mathbf{x}_{1}\right\| \leq \lambda R_{1}\right) \wedge \left(\left\|\mathbf{x}_{2}^{S_{i}}-\mathbf{x}_{2}\right\| \leq \lambda R_{2}\right) \end{array} \]

\[ \begin{array}{c} \left(\left|\alpha^{S_{i}}-\alpha^{p}\right| \leq t_{\alpha}\right) \wedge\left(\left|\ln \left(\frac{\sigma^{S_{i}}}{\sigma^{p}}\right)\right| \leq t_{\sigma}\right) \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}\)，然后我们就可以得到匹配关系对两个匹配对产生的残差，如下式：

\[ r_{k}\left(A_{i}^{j}\right)=\left\|A_{i}^{j} \mathbf{x}_{1}^{k}-\mathbf{x}_{2}^{k}\right\| \]

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

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

实验

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

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

借鉴意义

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

附录

1. Paper: AdaLAM: Revisiting Handcrafted Outlier Detection