📝笔记：GMS一种基于运动统计的快速鲁棒特征匹配过滤算法

Posted on 2020-09-05 Edited on 2022-09-05 Waline: Views:

今天要介绍的文章是边佳旺在CVPR2017以及IJCV2020发表的GMS，论文名是"GMS: Grid-based Motion Statistics for Fast, Ultra-robust Feature Correspondence"。同之前介绍的外点滤除算法AdaLAM的目的相同，该算法能够实现对初始匹配的筛选，以减少错误匹配。

(a)图是ORB+Lowe Ratio的结果，有很多错误的匹配；(b)图是ORB+Lowe Ratio+GMS的结果，匹配效果明显变好。首先祭出代码 Repo：

原有技术问题

原有算法复杂，为了达到好的效果，设计的算法比较复杂，导致运行速度慢，性价比低，无法部署在实时性要求较高的系统中。

新技术创新点

将运动平滑约束转换为剔除错误匹配的统计量，实验证明该算法能够应对较为棘手的场景；
提出了一种高效的基于网格的得分估计器，使得该算法能够用于实时特征匹配；
能够取得比Lowe Ratio更好的特征匹配筛选效果，该结论已经在传统特征如SIFT，SURF以及CNN特征如LIFT上得到验证；

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

首先给出第一个假设：

运动平滑性：真实匹配的小邻域内匹配通常是在三维空间中的同一块区域。同样地，一个错误匹配的邻域内的匹配通常是几何上不同的三维位置。

这个假设告诉我们：正确匹配的邻域内有多个支持它的匹配，而错误匹配的邻域内支持它的匹配是很少的。这里其实隐含着一个逻辑：作者通过观察发现，正确匹配的邻域内匹配的数量多的概率就会很大，反之则少；那么根据贝叶斯法则，那些匹配对邻域内有很多匹配的匹配关系有很大概率是正确匹配。一句话：正确匹配周围会有较多的匹配去支持它，而错误的匹配周围支持它的匹配很少。

运动统计

输入图像为\(\{I_1,I_2\}\)，它们分别有\(\{N,M\}\)个特征匹配；

\(C=\left\{c_{1}, c_{2}, \ldots, c_{i}, \ldots, c_{N}\right\}\)表示图\(I_a\)到图\(I_b\)的最近邻匹配；

其中\(c_{i}\)表示像素点\(p_i\)与\(q_i\)的匹配；定义\(c_{i}\)的邻域为： \[ N_{i}=\left\{c_{j} \mid c_{j} \in C, c_{j} \neq c_{i}, d\left(p_{i}, p_{j}\right)\right\}, \] 以及它的相似邻域可以表示为： \[ S_{i}=\left\{c_{j} \mid c_{j} \in N_{i}, d\left(q_{i}, q_{j}\right)<r_{2}\right\}, \] 其中\(d(·,·)\)表示两点之间的欧式距离，\(r_1\)和\(r_2\)为距离阈值，对于\(\left|S_{i}\right|\)，它表示在\(S_{i}\)中元素的个数，即匹配\(c_{i}\)的运动支持。如下图所示：黄圈区域即表示邻域\(N_i\)。支持它的匹配对为\(S_i=2\)，错误匹配没有支持它的匹配对，即\(S_j=0\)。那么我们就可以通过统计的方式知道哪些匹配是正确的，哪些是错误的。

由上文我们知道：统计支持域内的匹配数量就能够判别正确/错误匹配。于是我们可以对\(\left|S_{i}\right|\)建模，如下：

\[\left|S_{i}\right| \sim\left\{\begin{array}{ll} B\left(\left|N_{i}\right|, t\right), & \text { if } c_{i} \text { is correct } \\ B\left(\left|N_{i}\right|, \epsilon\right), & \text { if } c_{i} \text { is wrong } \end{array}\right.\]

其中\(B(·,·)\)表示二项分布，\(\left|N_{i}\right|\)表示邻域\(N_{i}\)内匹配对的数量，\(t\)和\(\epsilon\)分别表示正确/错误匹配被其某个邻域窗口匹配支持的概率。

进一步解释：\(t\)是受特征质量的控制，即接近匹配的正确率。\(\epsilon\)通常很小，因为错误匹配几乎随机分布在图像范围内。上式的期望为：

\[E_{\left|S_{i}\right|}=\left\{\begin{array}{ll} E_{t}=\left|N_{i}\right| \cdot t, & \text { if } c_{i} \text { is correct } \\ E_{f}=\left|N_{i}\right| \cdot \epsilon, & \text { if } c_{i} \text { is wrong } \end{array}\right.\]

方差为：

\[V_{\left|S_{i}\right|}=\left\{\begin{array}{ll} V_{t}=\left|N_{i}\right| \cdot t \cdot(1-t), & \text { if } c_{i} \text { is correct } \\ V_{f}=\left|N_{i}\right| \cdot \epsilon \cdot(1-\epsilon), & \text { if } c_{i} \text { is wrong } \end{array}\right.\]

于是真假匹配的可区分度被表示为如下形式（均值差异比方差之和）：

\[P=\frac{\left|E_{t}-E_{f}\right|}{\sqrt{V_{t}}+\sqrt{V_{f}}}=\frac{\left|N_{i}\right| \cdot(t-\epsilon)}{\sqrt{\left|N_{i}\right| \cdot t \cdot(1-t)}+\sqrt{\left|N_{i}\right| \cdot \epsilon \cdot(1-\epsilon)}}\]

上式告诉我们\(P \propto \sqrt{\left|N_{i}\right|}\)，如果\(\left|N_{i}\right| \rightarrow \infty\)时，\(P \rightarrow \infty\)。也就是说，当图像中的匹配点越多，此时正确与错误匹配的可区分度就越强！同时，即使是在\(t\)比\(\epsilon\)稍微大一丁点的情况下，也可以通过增多特征点的数量来弥补正确匹配与错误匹配区分程度不足的缺点；当然，也可以通过提高特征质量\(t\)来增加正确/错误匹配之间的区分度。

上图展示了作者在Oxford Affine Dataset上验证模型合理性的示意图。利用SIFT特征进行匹配，根据真值标记出正确以及错误匹配。统计每个匹配所在小邻域内的匹配数量。可以发现，正确匹配的支持域得分明显高于错误匹配，即使在非常困难的匹配序列上，该现象仍然存在。

因此，可通过对\(\left|S_{i}\right|\)设置阈值来判定\(c_{i}\)是正确或者错误匹配：

\[c_{i} \in\left\{\begin{array}{ll} \mathcal{T}, & \text { if }\left|S_{i}\right|>\tau_{i} \\ \mathcal{F}, & \text { otherwise } \end{array}\right.\]

上式中，\(\mathcal{T}\)以及\(\mathcal{F}\)分别表示正确/错误匹配集合，\(\tau_{i}\)的阈值被设置为：

\[\tau_{i}=\alpha \sqrt{\left|N_{i}\right|}\]

其中\(\alpha\)为超参数，经验值为4~6。

基于网格的框架

看到这里，大家肯定有一个疑问：如何高效地实现上述算法呢？难道对每一个匹配画个圈圈，然后统计圈圈内的匹配数？当然不是，本文设计了一种基于划分网格的算法对上述算法进行加速。将两幅图像划分为多个不重合的网格：\(\mathcal{G}_{1}\)以及\(\mathcal{G}_{2}\)，\(c_{i}\)表示为落到网格\(G_a\)和\(G_b\)中的一个匹配对，如上图中的一个红线段。于是邻域（表示在网格网格\(G_a\)中的匹配）被重新定义为：

\[N_{i}=\left\{c_{j} \mid c_{j} \in C_{a}, c_{i} \neq c_{j}\right\},\]

相似邻域被重新定义为：

\[S_{i}=\left\{c_{j} \mid c_{j} \in C_{a b}, c_{i} \neq c_{j}\right\},\]

上面的两个式子中，\(G_{a}\)表示某个网格，\(C_{a}\)表示落在\(G_{a}\)中的匹配对，\(C_{ab}\)表示同时落在\(G_{a}\)和\(G_{b}\)中的匹配对。换句话说，本文将落在同一个网格中的匹配当作邻域，将同时落在两个网格中的匹配称为相似邻域，即cell-pair。

注意：一个cell-pair中的匹配满足运动平滑性假设，所以在判断匹配关系是正确还是错误时，仅需要判定一个cell-pair中的所有匹配是否正确即可，无需逐个匹配判断。此外，不需要确定所有可能的cell-pair，而是只检查与第一个图像网格匹配数量最多的一个cell-pair即可。

运动核

如果网格很小，则很少邻域信息将被考虑，这会降低算法性能。但是，如果网格很大，则将包括更多不正确的对应关系。为解决这个矛盾，我们将网格大小设置为较小以提高准确性，并提出运动内核以考虑更多邻域信息。

考虑了原有网格邻域的8个网格，构成一个更大的网格\(\left(C_{a^{1} b^{1}}, \ldots, C_{a^{9} b^{9}}\right)\)。

于是我们从新定义了邻域： \[N_{i}=\left\{c_{j} \mid c_{j} \in C_{A}, c_{i} \neq c_{j}\right\}\] 其中\(C_{A}=C_{a^{1}} \cup C_{a^{2}} \cup C_{a^{3}} \ldots \cup C_{a^{9}}\)；重新定义相似邻域： \[S_{i}=\left\{c_{j} \mid c_{j} \in C_{A B}, c_{i} \neq c_{j}\right\}\] 其中：\(C_{A B}=C_{a^{1} b^{1}} \cup C_{a^{2} b^{2}} \cup C_{a^{3} b^{3}} \ldots \cup C_{a^{9} b^{9}}\)。

多尺度+多旋转

为了应对匹配过程中的尺度与旋转问题，本文提出了多尺度以及多旋转策略。

多尺度

固定一个图像网格，假设网格大小为\(n \times n\)，改变另一个图像的网格大小为\((n \cdot \alpha) \times(n \cdot \alpha)\)，其中有5个候选的\(\alpha\)取值，分别为\(\left\{\frac{1}{2}, \frac{\sqrt{2}}{2}, 1, \sqrt{2}, 2\right\}\)。在不同尺度的网格上运行GMS算法，然后统计最好的匹配结果。如果场景的尺度发生较大改变，此时可以设置更多的候选值或者增大\(\alpha\)。

多旋转

利用旋转运动核模拟不同方向的旋转，如下图所示，固定\(C_A\)，对\(C_B\)按照顺时针旋转，这样可以得到8个运动核。然后利用GMS算法在所有的运动核上，然后选择最好的结果（选择匹配数量最多那个）。

伪代码

综上，算法伪代码如下：

局限性

首先，算法假设图像运动是分段平滑的时，在违反假设的区域，例如图像边界，性能可能退化；
其次，在视觉上相似但空间位置不同的图像区域，算法性能受到限制。此问题通常发生在具有大量重复纹理的场景中；
最后，由于算法使用了网格化对图像进行处理，算法判定正确的匹配网格中仍然存在不准确匹配。

实验

旋转以及尺度变化

高精确率与召回率

算法快速

GMS能够在PC端速度2ms，multi-scale(GMS-S)以及multi-rotation(GMS-R)会增加一定的耗时。

高效解算位姿

求解位姿速度快，且位姿精确。

有利于SLAM初始化

集成到SLAM也可获得较好的结果（该实验不够充分，仅测试了将GMS集成到SLAM初始化的阶段，为了展示GMS能够更快/更好的进行初始化，同时能够产生较多的地图点）。

借鉴意义

本文提供了一种高效/快速的外点滤除算法，能够在PC端实现实现实时滤除外点；
本算法已经被集成到OpenCV中，接口名为matchGMS()，可直接调用；
本算法可用于SLAM/SFM等领域，可提高位姿解算的精度以及速度；
（局限）本算法需要提取较多的特征点以提高正确匹配与错误匹配的可区分度，若特征匹配较少；该算法性能会有一定下降；
（局限）由于仅统计特征匹配数量，在重复纹理条件下该算法的性能也会下降；