GMS：基于网格的运动统计快速、超鲁棒特征对应

GMS：基于网格的运动统计快速、超鲁棒特征对应 (2017CVPR会议版)

https://ieeexplore.ieee.org/document/8099785/

JiawangBian/GMS-Feature-Matcher: GMS: Grid-based Motion Statistics for Fast, Ultra-robust Feature Correspondence (CVPR 17 & IJCV 20) (github.com)

GMS算法

摘要：

在特征匹配中引入平滑约束已知能够实现超鲁棒匹配。 然而，这种公式既复杂又缓慢，使得它们不适用于视频应用。 本文提出了基于网格的运动统计方法GMS（Grid-based Motion Statistics)，它是一种简单的方法，将运动平滑性封装为一个区域内一定数量匹配的统计似然。 GMS可以将高匹配数转换为高匹配质量。 这提供了一个实时、超鲁棒的通信系统。 对低纹理、模糊和宽基线视频的评估显示，GMS的性能一直优于其他实时匹配器，并可以与更复杂、更慢的技术实现对等。

1. 概述

特征匹配是许多计算机视觉算法的基本输入。 因此，它的速度、精度和鲁棒性至关重要。 目前，在速度慢（但健壮）的特征匹配器和速度快（但往往不稳定）的实时解决方案之间存在很大的性能差距。

核心问题在于更强大的特征对应技术中使用的一致性约束（相邻像素具有相似的运动）。 一致性是一个强大的约束，但稀疏特征缺乏定义良好的邻居。 这导致基于一致性的特征对应[16，42]计算成本高且实现复杂。 本文提出了GMS（Gridbased Motion Statistics)，将运动平滑度封装为一个区域对之间具有一定数量特征匹配的统计可能性。 我们证明了GMS能够快速可靠地区分真假匹配，从而实现了图1中高质量的对应。

图1. 备受推崇的SIFT[22]描述符在这个场景中有困难，因为狗的皮毛运动给局部描述符增加了噪声。 虽然我们使用较弱的ORB描述符，但我们的GMS解决方案可以利用特征数来提高质量，同时保持实时性能。

本文从BF中得到启示。 BF强调，特征匹配的明显缺乏并不是由于正确匹配太少，而是由于难以可靠地分离真假匹配。 BF证明了通过使用复杂最小化计算的相干测度来实现这种分离的可行性。 在实践中，BF工作得很好（尽管很慢）。 然而，它主要是由观察和直觉驱动的。 由于研究人员必须依赖于受许多波动变量影响的图像数据的实证检验，因此缺乏理论上的清晰度使得改进变得困难。

我们建议BF和其他类似技术中使用的复杂光滑性约束可以简化为一个简单的陈述：运动光滑性诱导出极不可能随机发生的对应簇。 因此，真匹配和假匹配可以通过简单地计算其邻域中匹配的数量来区分。 从大数定律、真标度和假标度的可分性到用匹配数的无穷大。 数学分析是直截了当的，但结果可能会改变范式。

以前的特征匹配文献假设匹配质量主要随着特征不变性/独特性的提高而提高。 GMS揭示了改进的新方向； 原始特征数也会影响质量。 由于寻找更多的特征比设计新的描述符更简单，GMS潜在地为以前难以解决的匹配问题提供了简单的解决方案，如图1所示。

概括地说，我们的贡献是：

• 将运动平滑性约束转换为统计度量以拒绝假匹配。 我们展示了这个约束使得以前难以处理的场景能够匹配；
• 开发一个高效的基于网格的得分估计器，该估计器可以并入实时特征匹配器
• 用标准比率测试证明我们的GMS系统明显优于传统的SIFT、SURF和最近的CNN训练的升力特性。

1.1 相关工作

特征匹配的基础工作旨在提高特征描述子的显著性/不变性，提高定位能力。 例如SIFT[22]、ORB[35]、SURF[2]、A-SIFT[26]、Harris角[9]和仿射协变区域检测器[25]等经典作品。 这些作品中的许多都有GPU加速[45，40，7]允许真实（或接近真实）的时间性能。 此外，还有加速特征匹配的FLANN工作[14,27,28]。 这种研究仍在进行中，最近的例子是CNN训练的电梯描述符[47]。 这些工作共同构成了我们构建的核心技术集。

完全依赖描述符的问题是很难区分真假匹配。 这导致消除大量的真匹配以限制假匹配。 RANSAC可以利用几何信息来缓解这个问题。 然而，ransac本身要求预先消除大多数假匹配（因为RANSAC计算复杂度随离群点指数上升），并且不能容纳所有最近邻匹配集合中的假匹配的绝对数量。

最近，许多技术[30,16,17,19,42,24]集中于使用匹配分布约束来分离真匹配和假匹配。 然而，它们的公式导致复杂的光滑性约束，这是难以理解和昂贵的最小化。 我们的方法受到了这些工作的启发，但使用了一个更简单、更容易理解的统计匹配约束。 这使得匹配既健壮又有效。

更广泛地说，我们的工作涉及光流[13,23,4,43,33,21,1,46]，基于点的相干技术[48,18,29]，基于块匹配的匹配器[12]，这些匹配器直接使用平滑度来帮助匹配估计。 这些技术可能非常强大。 然而，它们也要复杂得多，昂贵得多。 最后，我们承认像Adaboost[11]这样的被提升的学习者的启发，它将多个弱者整合为一个强大的学习者。 GMS通过使用平滑约束来集成来自多个匹配的信息来做出高质量的决策，从而分享了这一设计哲学。

图2. 匹配$x_i$的邻域定义为{a,b}，即围绕各自特征的一对小的支持区域。 我们预测真匹配邻域将比假匹配邻域有更多的支持匹配。

2. GMS

给定取自同一3D场景的不同视图的一对图像，特征对应意味着一幅图像中的像素（特征点）被标识为另一幅图像中的相同点。 如果运动是平滑的，相邻的像素和特征一起运动。 这使我们可以作出以下假设：

假设1：

运动平滑性使得正确的匹配周围的小领域具有相似的运动（运动一致性约束）

这里，邻域被定义为围绕图2中所示的各个图像特征的一对区域{a，b}。

假设1意味着真正匹配邻域，查看相同的3D区域，从而在两幅图像中共享许多相似的特征。 这导致邻域有许多支持匹配。 相反，假匹配邻域查看不同的3D区域，具有更少的相似特征。 这减少了匹配支持。 我们将这种直觉封装到一个名为GMS的统计框架中，该框架可靠地区分真假匹配。第3节介绍了快速计算邻域分数的网格算法，同时介绍了第4节给出了结果和比较。

2.1 符号

图像对$\{I_a,I_b\}$分别具有$\{N,M\}$特征。$\chi=\{x_1,x_2,..,x_i,..,x_N\}$是从$I_a$到$I_b$的所有最近邻特征匹配的集合。 $\chi$具有基数$|\chi|=N$，我们的目标是通过分析每个匹配的局部支持度，将$\chi$划分为真匹配和假匹配的集合。

图2中所示的匹配邻域的表示法如下：

$\{I_a,I_b\}$中的各个区域被表示为{a，b}，每个区域分别具有$\{n,m\}$个附加（不包括原始匹配对）特征。$\chi_i\subseteq \chi$是匹配$x_i$的区域{a,b}之间匹配的子集。 $S_i$是邻里支持度的度量：

$S_i=|\chi_i|-1\tag{1}$

其中-1是从总和中移除原始匹配项。

2.2 基本统计约束

由于区域很小，我们将我们的考虑限制在理想化的真和假区域对，忽略部分相似的位置。 设$f_a$是区域a中的n个支持特征之一，给定$f_a$具有正确匹配的概率t，我们的目标是在{a,b}查看相同/不同位置的情况下，求出区域{a,b}的匹配到达率。表1总结了常用的符号和事件，图3说明了$f_a$的事件空间。

表1. 符号和事件表。

图3. 特征$f_a$的事件空间。$f_a$的最近邻匹配要么落在区域b（事件$f_a^b$）,要么不落在区域b（事件$\bar{f_a^b}$）。 匹配为true（事件$f_a^t$）或false（事件$f_a^f$）。(I)给定$T^{ab}$，$f_a^b$是事件$f_a^t$和一些$f_a^f$事件的并集。 (ii)给定$F^{ab}$，$f_a^b$必然是事件$f_a^f$的子集

为了使这个问题容易处理，我们做了这样的假设 ：

假设2：

如果$f_a$匹配错误，则它的最近邻匹配可以位于M个可能位置中的任意一个（没有先验信息）。

假设2的出现是因为在一般情况下，一个特征的错误的最近邻并不适合任何图像区域。 假设2给出 ：

$p(f_a^b|f_a^f)=\beta m/M\tag{2}$

其中m是区域b中特征的数量，β是一个因子，以适应由像一排窗口这样的重复结构引起的对假设2的违反。

设$p_t=p(f_a^b|T^{ab})$为给定{a,b}查看相同位置时，特征$f_a$的最近邻区域b中的概率。 因此:

$\begin{aligned} p_t=p(f_a^b|T^{ab})&=p(f_a^t|T^{ab})+p(f_a^f,f_a^b|T^{ab})\\ &=p(f_a^t|T^{ab})+p(f_a^f|T^{ab})p(f_a^b|f_a^f,T^{ab})\\ &=p(f_a^t)+p(f_a^f)p(f_a^b|f_a^f)\\ &=t+\beta(1-t) (m/M) \end{aligned}\tag{3}$

说明：

图3(i)显示事件$f_a^b$仅当$f_a$正确匹配，或者它错误匹配但巧合地落在区域B中时才发生。 这就给出了方程（3）的第一条线。 第二条线源于贝叶法则。 由于特征是预先匹配的，所以$p(f_a^t)$和$p(f_a^f)$与$T^{ab}$无关。 由于假设2，$p(f_a^b|f_a^f)$也与$T^{ab}$无关。 删除条件$T^{ab}$并替换表1和方程（2）中的值给出了最后的表达式。

令$p_f=p(f_a^b|F^{ab})$。与等式（3）相同：

$\begin{aligned} p_f=p(f_a^b|F^{ab})&=p(f_a^f,f_a^b|F^{ab})\\ &=p(f_a^f|F^{ab})p(f_a^b|f_a^f,F^{ab})\\ &=p(f_a^f)p(f_a^b|f_a^f)\\ &=\beta(1-t) (m/M) \end{aligned}\tag{4}$

说明：

从图 3(ii) 我们知道事件$f_a^b$是$f_a^f$的子集。因此，得出等式（4）第一行，$p(f_a^b|F^{ab})=p(f_a^f,f_a^b|F^{ab})$。与等式 (3) 类似，概率可以通过贝叶斯规则扩展为独立于$F^{ab}$的子概率。替换表（1）中和等式（2）的值给出了最终表达式

由于每个特征的匹配是独立的，使用假设1和方程(3)(4)，我们可以用一对二项分布来近似$S_i$的分布，即匹配xi的邻域中的匹配数：

$S_i\sim \begin{cases} B(n,p_t),& if\ \ x_i \ \ is \ true\\ B(n,p_f),& if\ \ x_i \ \ is \ false \end{cases}\tag{5}$

虽然方程 (5) 看起来很复杂，但重要的是，真假匹配的邻域分数 S 遵循非常不同的分布。这意味着 S 的整体 pdf 可能是双峰的，使 S 分数成为区分真假匹配的有用指标。这如图 4 所示。

图4. 真假匹配的邻域分数遵循不同的分布。如果分布均值相对于它们的标准偏差具有足够大的分离度，则真假匹配可能通过基于分数的阈值分离。

2.3 多邻域泛化

运动通常在大面积上是平滑的。然而，假设 1 需要足够小的邻域。在过大的邻域中，真正匹配的邻域将包括一些错误匹配的区域，反之亦然。这降低了真假分数分布的可分离性。因此，概括假设 1，我们有：

假设 3：如果运动在一个区域上是平滑的，则真正的匹配允许预测多个查看相同 3D 位置的小区域对。对错误匹配使用相同的预测函数将导致几何上不同的 3D 位置。

这给出了更通用的分数

$S_i=\sum_{k=1}^K |\chi_{a^kb^k}|-1\tag{6}$

其中 K 是匹配 i 预测一起移动的不相交区域的数量。$\{a^k,b^k\}$是预测的区域对，$\chi_{a^k,b^k}\subseteq\chi$是落在区域对$\{a^k,b^k\}$上的匹配子集，即落在$a^k$又落在$b^k$的匹配对。

假设每个区域对有$\{n,m\}$个特征，与等式 (5) 类似，假设 3 表示$S_i$的二项式分布：

$S_i\sim \begin{cases} B(Kn,p_t),& if\ \ x_i \ \ is \ true\\ B(Kn,p_f),& if\ \ x_i \ \ is \ false \end{cases}\tag{7}$

$S_i$分布的均值和标准差分别为

$\begin{cases} m_t=Knp_t,s_t=\sqrt{Knp_t(1-p_t)} & if\ \ x_i\ \ is\ true\\ m_f=Knp_f,s_f=\sqrt{Knp_f(1-p_f)} & if\ \ x_i\ \ is\ false \end{cases} \tag{8}$

通常，在处理统计事件时，我们认为与平均值有 x 个标准差的事件极不可能发生。这在图 4 中进行了说明，并且可以用可分割性分数来量化：

$P=\frac{m_t-m_f}{s_t+s_f}=\frac{Knp_t-Knp_f}{\sqrt{Knp_t(1-p_t)}+\sqrt{Knp_f(1-p_f)}}\tag{9}$

我们的目标是设计最大化 P 的算法。

2.4 分析

这些推导很简单。然而，它们使我们的直觉变得清晰，并允许推导一些有用的结果。

数量-质量等价：这些推导的关键结果是：

$P\propto\sqrt{Kn}\tag{10}$

这意味着，如果$m_t>m_f$，真假匹配的可分割性随着特征数量 n 扩大到无穷大。也就是说，即使对于真正匹配很少的困难场景，如果真实匹配位置比随机位置有更多的匹配，只要特征数量足够大，我们就可以获得我们想要的尽可能多的匹配，并且具有完美的精度和召回率。这形成了从假设 1、2、3 到大数定律的直接联系。结果很有趣，因为大多数以前的工作都假设更好的对应的关键是增加特征的独特性/不变性。相反，等式 (10) 显示原始特征数有助于匹配质量。这使得通过增加特征数量来解决具有挑战性的匹配问题成为可能！图 5 显示了一个示例。

图5. 顶部：传统的特征匹配侧重于增加描述符的不变性。最近的迭代是 LIFT [47]。因此，显式模拟大变形的 A-SIFT [26] 具有最佳的宽基线性能。底部：GMS 通过简单地增加特征的数量（在括号中表示）达到与标准 ORB [35] 相同的效果。这使得 ORB 成为一个可行的宽基线功能！

运动预测：通常，简单地增加 n 是不切实际的。等式（10）表明另一种方法是通过预测图像区域的更多联合移动来增加 K。这是我们用来构建实时匹配系统的方法。

实际适用性：给定足够大的 n，GMS 约束是强大的。问题是 n 在实践中是否足够大？给定 10, 000 个均匀分布的特征，一些典型值为$\{m = n =25,β = 1,t =0.5,K =1\}$。因此，等式 (8) 的基本约束中的 Si 的均值和标准差为：

$\{m_t=12.5,s_t=2.5\},\{m_f=0.03,s_f=0.176\},P=4.7\tag{11}$

这是一个广泛的分离。注意K = 1。这表明基本 GMS 约束在典型匹配数下非常强大。这也可能有助于解释为什么这么多具有相似配方的技术都能取得良好的效果 [30,16,17,19,42,24]。

与描述符的关系：可分割性与 t 的关系，百分比匹配正确性由下式给出

$\lim_{t\to 1}m_t\to Kn,\lim_{t\to 1}m_f\to 0,\lim_{t\to 1}P\to \infty\tag{12}$

由于最近邻匹配趋于完美，mt 趋于最大值，mf 趋于最小值，可分割性趋于∞。因此，如果设置了一个固定的阈值，GMS 的结果在更容易的高 t 场景上会更好。这具有实际重要性，因为 t 是未知的并且取决于场景对。它还允许 GMS 随着特征描述符设计的改进而扩展，从而增加了 GMS 的通用性。

3. 快速评分的网格框架

本节将前面的分析转换为有效的实时匹配算法。 3.1 介绍了网格框架，解决了以下问题： a) 通过网格单元进行高效的分数计算； b) 哪些邻域（网格单元）组合在一起； c) 使用多少个网格单元； d) 如何计算有效的阈值 S。算法 1 中给出了实现概述，3.2 中讨论了细节。

3.1 网格化问题

a) 有效的分数评估。对每个特征匹配的邻域进行评分的成本是 O(N)，其中 N 是图像特征的数量。这与我们使用尽可能多的功能的愿望相冲突。我们使用网格近似来解决它，将图像划分为 G = 20×20 个不重叠的单元格。潜在单元格对的分数只计算一次。接受被认为是真的单元对之间的所有匹配。这使得分数计算独立于特征数，即 O(1)。在实践中，许多特征位于网格边缘。为了适应这一点，我们再重复算法 3 次，网格图案在 x、y 以及 x 和 y 方向上移动半个单元格宽度。

b) 对匹配邻域（单元对）进行分组以提高鲁棒性。如等式(6)(10)所示，将单元对分组增加了可分割性。我们使用平滑的横向运动假设对细胞对进行分组。因此，根据等式 (6)，单元对 {i, j} 的得分$S_{ij}$为：

$S_{ij}=\sum_{k=1}^{K=9}|\chi_{i^kj^k}|\tag{13}$

其中$|\chi_{i^kj^k}|$是单元格$\{i^k,j^k\}$之间的匹配数,如图6所示。该解决方案是有效的，但限制了平面内旋转不变性。如图6所示，GMS 在极端旋转时与比率测试具有竞争力，但在较低旋转时性能更好。在实践中，旋转通常可以由其他传感器估计，OpenCV 3.0 实际上使用它们的 EXIF 信息将所有读取的图像自动旋转到规范方向。或者，我们还通过对所有潜在的比例旋转对执行网格选择并从具有最佳结果的对中选择匹配来提供算法的比例和旋转版本。

图6. 用于分数评估的单元格 {i, j} 周围的区域。

c) 应该使用多少个网格单元？更多的网格单元改善了匹配本地化。然而，它减少了 n，每个单元格中的特征数量，从而减少了可分割性。这可以通过增加 K 来补偿，但这会影响计算时间。我们的理论和实证结果表明 G = 20 × 20 个细胞，用于 10, 000 个特征。这使 n 的平均值为 25。更多的特征允许更精细的单元格。

d) 阈值$S_{ij}$将单元格对分为真集和假集$\{\mathcal{T},\mathcal{F}\}$

图4显示所需的阈值可以给出为$\tau=m_f+\alpha s_f$，其中$m_f$是平均值，$\alpha s_f$是适当数量的标准偏差，以确保拒绝大多数错误的网格单元。在实践中，$m_f$在设计上很小，而 α 非常大，以确保可靠地拒绝大量错误的单元格对。稍微滥用符号，阈值可以近似为$\tau\approx\alpha\sqrt{s_f}\approx\alpha\sqrt{n}$

这导致单个参数阈值函数:

$cell-pair\{i,j\}\in \begin{cases} \mathcal{T},&if\ S_{ij}>\tau_i=\alpha\sqrt{n_i}\\ \mathcal{F},&otherwise \end{cases}\tag{14}$

其中 α =6 是通过实验确定的，ni 是（图 6 中 9 个网格单元的）单个网格单元中存在的特征数的平均值。

3.2 实现细节

我们使用 OpenCV ORB 功能。功能编号固定为 10, 000，这是实时性能允许的最大数量。大的、纹理良好的图像可以有超过 10,000 个特征。这会导致特征分布不均（聚集在角落）。较小的纹理较少的图像可以具有远少于 10,000 个不同的特征。前一个问题通过将所有图像的大小调整为 480 × 640 来解决。后者通过将 FAST [34] 特征阈值设置为零来解决。这可以在弱纹理环境中进行匹配（参见随附的视频）。在 GPU 上通过蛮力汉明距离比较发现最近邻居。这与基于 CPU 的特征检测并行运行。这是两个最昂贵的模块。最后，通过 GMS 算法 1 筛选出真正的匹配项。这一步需要 1ms 的单线程 CPU 时间。代码在下面的链接中提供。CODE: https://github.com/JiawangBian/GMS-Feature-Matcher

GMS(2020)

JiawangBian/GMS-Feature-Matcher: GMS: Grid-based Motion Statistics for Fast, Ultra-robust Feature Correspondence (CVPR 17 & IJCV 20) (github.com)

2. 相关工作

2.1 错误匹配去除

劳氏比率检验 (Lowe 2004)，称为 RT，是一种广泛使用的方法。它比较两个最近邻居的距离以识别不同的对应关系。然而，由于缺乏更强大的约束，许多错误的对应关系仍然存在于具有挑战性的场景中。其他方法包括 KVLD (Liu et al. 2012)，它在光度学和几何学中使用约束，以及 VFC (Ma et al. 2014)，它在两个点集之间插入一个向量场并估计一致集。最近，CODE (Lin et al. 2017) 利用非线性优化对运动平滑度进行全局建模。我们的方法受到它的启发，但更简单、更有效。 LPM (Ma et al. 2019) 探索了周围特征点的局部结构，这比 GMS 做出了更严格的假设。 LC (Yi et al. 2018) 使用深度神经网络通过拟合基本矩阵来找到良好的对应关系。它就像 RANSAC 的替代品（Fischler 和 Bolles 1981）。然而，作者表明预测模型不如使用 RANSAC 好。相反，他们建议使用该方法找到良好的对应关系，然后应用 RANSAC 进行模型拟合。

2.2 使用 GMS 的成功应用程序

在 GMS 的会议版本发布后，我们注意到许多近期的工作在他们的应用中使用了我们的方法并取得了显着的性能。例如，（Causo et al. 2018）在亚马逊机器人挑战赛的物品拣选系统中使用 GMS，系统可以在最短的时间内拣选所有目标物品； (Zhang et al. 2019) 使用 GMS 并扩展该想法以解决动态场景中的跟踪问题。在 TUM 基准测试 (Sturm et al. 2012) 中，所得解决方案产生的相机轨迹比 ORB-SLAM2 (Mur-Artal et al. 2015) 精确一个数量级； (Yoon et al. 2018) 在他们的轨迹重建系统中使用 GMS 进行 3D 点云三角测量。此外，我们的 GMS 实现已集成到 OpenCV 库（Bradski 2000）中，我们鼓励研究人员在更实时的应用程序中使用和扩展它。

3 基于网格的运动统计

给定由特征检测器、描述符和匹配器生成的假定对应，我们的目标是将真实对应与错误对应分开。

3.1 运动平滑假设

为了区分真假对应，我们假设在图像坐标中空间上接近的像素会一起移动。这是直观的，即想象相邻像素很有可能落在一个刚性物体或结构中，因此具有相似的运动。该假设通常不正确，例如，它可能在图像边界中被违反，其中相邻像素可能落在不同的对象中并且这些对象具有独立的运动。但是，它适用于规则像素，这些像素压倒性地超过边缘。此外，由于我们的目标是一组用于进一步处理的高质量对应假设，而不是最终的对应解决方案，因此该假设足以满足我们的目的。

3.2 运动统计

真对应受平滑约束的影响，而假对应则不受。因此，真实对应通常比虚假对应具有更多相似的邻居，如图 2 所示，其中相似邻居指的是在两幅图像中与参考对应关系接近的对应。我们使用相似邻居的数量来识别好的信息。

图2. 运动统计。真实对应通常比虚假对应具有更多相似的邻居，因此我们计算相似邻居的数量以将它们分开

形式上，令$C$是图像$I_1$和$I_2$上的所有对应关系，$c_i$是连接两个图像之间的点$p_i$和$q_i$的对应关系。我们将$c_i$的邻域定义为（在图像P中，$p_i$周围半径为$r_1$的匹配）：

$N_i=\{c_j|c_j\in C,c_j\neq c_i,d(p_i,p_j)<r_1\}\tag{1}$

并且相似的邻域被定义为（$p_i$邻域点对应到图像Q中且距离$q_i$半径为$r_2$的匹配）：

$S_i=\{c_j|c_j\in N_i,d(q_i,q_j)<r_2\}\tag{2}$

其中 d(·,·) 是指两点的欧几里得距离，r1, r2 是阈值。我们称$|S_i|$是$S_i$中的元素数量，$c_i$的运动支持。

也就是说$S_i$表示存在这样一组对应关系$c_i=\{p,q\}$，使得$d(p_i,p)<r_1且d(q_i,q)<r_2$ 。

运动支持可以用作区分真假对应的判别特征。模拟$|S_i|$的分布对于真假对应，我们得到：

$|S_i|\sim \begin{cases} B(|N_i|,t),&if\ c_i\ is\ correct\\ B(|N_i|,\epsilon),&if\ c_i\ is\ wrong \end{cases}\tag{3}$

其中 B(·,·) 是指二项式分布。$|N_i|$指 ci 的邻居数。t和$\epsilon$是其邻居之一支持真假对应的各自概率。

在等式(3)，t受特征质量支配，即接近正确的对应率。通常很小，因为错误对应几乎随机分布在规则区域中。请注意，在视觉上相似但地理上不同的区域，例如重复结构（Kushnir and Shimshoni 2014），它会更大。在这里，我们假设特征能够充分区分它们的对应分布优于随机分布，并且是由重复模式引起的，即t大于$\epsilon$。

我们可以推导出$|S_i|$的期望：

$E_{|S_i|}= \begin{cases} E_t=|N_i|\cdot t,& if\ c_i\ is\ correct\\ E_f=|N_i|\cdot \epsilon,&if\ c_i\ is\ wrong \end{cases}\tag{4}$

和方差：

$V_{|S_i|}= \begin{cases} V_t=|N_i|\cdot t\cdot (1-t),& if\ c_i\ is\ correct\\ V_f=|N_i|\cdot \epsilon\cdot(1-\epsilon),&if\ c_i\ is\ wrong \end{cases}\tag{5}$

这允许将真假对应之间的可分割性定义为：

$P=\frac{|E_t-E_f|}{\sqrt{V_t}+\sqrt{V_f}}=\frac{|N_i|\cdot(t-\epsilon)}{\sqrt{|N_i|\cdot t\cdot(1-t)}+\sqrt{|N_i|\cdot \epsilon\cdot(1-\epsilon)}}\tag{6}$

其中$P\propto\sqrt{|N_i|}$且若$|N_i|\to\infty$则$P\to\infty$。这意味着基于$|S_i|$的真假匹配的可分离性，随着特征数量足够大，它变得越来越可靠。即使 t 仅略大于$\epsilon$也会发生这种情况，这使得通过简单地增加检测到的特征的数量就可以在困难的场景中获得可靠的对应关系。类似的结果显示在 Lin 等人（2018），其中通过大量独立试验分离了模棱两可的分布。此外，它表明提高特征质量（t）也可以提高可分离性。

独特的属性允许我们通过简单的阈值$|S_i|$ 将$c_i$分类为真或假，给出：

$c_i\in \begin{cases} \mathcal{T},&if\ |S_i|>\tau_i\\ \mathcal{F},&otherwise \end{cases}\tag{7}$

其中$\mathcal{T}$和$\mathcal{F}$分别表示真和假对应集。基于方程式(6)我们将$\tau_i$设为：

$\tau_i=\alpha\sqrt{|N_i|}\tag{8}$

其中$\alpha$是一个超参数，我们根据经验发现，当$\alpha$介于 4 到 6 之间时，它会产生良好的性能。

3.3 基于网格的框架

计算$|S_i|$的简单实现的复杂度是 O(N)，其中$N =|C|$是所有对应的数量，因为我们需要将$c_i$与所有其他对应进行比较。因此，整体算法复杂度为$O(N^2)$。尽管近似最近邻算法，如 FLANN (Muja and Lowe 2009)，可以将复杂度降低到O(Nlog(N))，但我们表明使用所提出的基于网格的框架更快 (O(N))。

图3. 基于网格的框架。我们使用预先计算的网格来寻找相似的邻居，而不是点之间的显式距离比较

图 3 说明了该框架，我们将两个图像分别划分为不重叠的单元格$\mathcal{G}_1$和$\mathcal{G}_2$。假设$c_i$是落在单元格$G_a$和$G_b$中的对应关系，如图 3 中的红色对应关系之一。$c_i$的邻居被重新定义为：

$N_i=\{c_j|c_j\in C_a,c_i\neq c_j\}\tag{9}$

并且相似的邻居被重新定义为：

$S_i=\{c_j|c_j\in C_{ab},c_i\neq c_j\}\tag{10}$

其中$C_a$是落在$G_a$的对应关系，$C_{ab}$是同时落在$G_a$和$G_b$的对应关系。换句话说，我们将一个单元格中的对应关系视为邻居，而将一对单元格中的对应关系视为相似的邻居。这避免了对应关系之间的显式比较。为了获得所有对应的运动支持，我们只需要将它们放在单元格对中。以这种方式，整体复杂度降低到 O(N)。

请注意，那些落在一个单元对中的对应共享相同的运动支持，因此我们只需要对单元对进行分类，而不是单独的对应。此外，我们不是确定所有可能的单元对，而是只检查第一张图像中每个单元包含最多对应关系的最佳单元对。例如，我们只检查$G_{ab}$ 并丢弃图 3 中的$G_{ac}$、$G_{ad}$。此操作显着减少了单元对的数量并提前拒绝了大量的错误对应。

3.4 运动内核

如果像元大小很小，将考虑很少的邻居。这会降低性能。但是，如果像元大小很大，则会包含不准确的对应关系。为了解决这个问题，我们将网格大小设置为小以提高准确性，并提出运动内核以考虑更多邻居。

图4. 基本运动内核。在计算原始单元对$(C_{ab})$的运动支持时，我们会考虑周围的单元对$(C_{a^1b^1},...,C_{a^9b^9})$

图 4 显示了基本运动内核，其中我们考虑了额外的八个单元对$(C_{a^1b^1},...,C_{a^9b^9})$用于对原始单元对$(C_{ab})$进行分类。形式化的，让$c_i$再次登陆$C_{ab}$。我们将其领域重新定义为：

$N_i=\{c_j|c_j\in C_A,c_i\neq c_j\}\tag{11}$

其中

$C_A=C_{a^1}\cup C_{a^2}\cup C_{a^3}...\cup C_{a^9}\tag{12}$

我们将其相似的邻居重新定义为

$S_i=\{c_j|c_j\in C_{AB},c_i\neq c_j\}\tag{13}$

其中

$C_{AB}=C_{a^1b^1}\cup C_{a^2b^2}\cup C_{a^3b^3}...\cup C_{a^9b^9}\tag{14}$

基本内核假设两个图像之间的相对旋转很小。为了匹配具有显着旋转变化的图像对，我们可以旋转基本内核，如下一节所述。

3.5 多尺度多旋转

为了处理两个图像之间的显着尺度和旋转变化，我们在本节中提出了多尺度和多旋转解决方案。

3.5.1 多旋转解决方案

图5. 旋转运动内核。我们将第一幅图像中的图案设置为固定，并以顺时针方向旋转第二幅图像中的图案，从而产生总共 8 个运动内核来模拟可能的相对旋转

我们旋转基本内核来模拟不同的相对旋转，得到总共 8 个运动内核，如图 5 所示。旋转在实际问题中通常是未知的，因此我们使用所有运动内核运行 GMS 算法并收集最佳结果，即，我们找到了导致检索到大多数对应关系的内核。多旋转解决方案的有效性在第 4.2节中得到了证明。

3.5.2 多尺度解决方案

两个图像之间的相对比例可以在我们的网格框架中模拟，即我们固定一个图像的单元格大小（单元格数）并改变另一张图像的单元格大小。假设两个图像都被划分为 n×n 个单元。我们将第二张图像的单元格数更改为 $(n·α)×(n·α)$。在这里，我们提供了 5 个候选 α，包括$\{\frac{1}{2},\frac{\sqrt{2}}{2},1,\sqrt{2},2\}$。同样，我们使用所有预定义的相对比例运行 GMS 并收集最佳结果。请注意，我们仅提供 5 个相对比例来证明我们的解决方案对于解决比例问题是有效的，这对于大多数场景来说是有效且充分的，如4.2 和 4.4节中所展示的。然而，对于更显着的尺度变化，我们可以使用更多的候选者或增加 α。

3.6 算法和限制

算法1显示了 GMS 算法，该算法将假定的对应关系以及缩放和旋转的设置作为输入并输出选定的匹配项。我们使用基本运动内核和单个等比例来匹配常规图像，例如视频帧。多尺度和多旋转解决方案分别用于尺度和旋转发生显着变化的图像。

3.6.1 实施

我们使用 C++ 和 OpenCV 库 (Bradski 2000) 实现算法。目前使用的是单CPU线程，但多线程编程可用于加速多尺度多轮换的方案。我们使用 20×20 单元格作为默认模式，并且在激活多尺度解决方案时我们会改变第二张图像中的单元格数量。 α = 4在等式8用于阈值化。该代码已集成到 OpenCV 库中。

3.6.2 限制

GMS的局限性在于三个方面。首先，由于我们假设图像运动是分段平滑的，因此在违反假设的区域，例如图像边界，性能可能会退化。这个问题并不重要，因为常规像素压倒性地超过了边界。此外，由于我们的目标不是最终的对应解决方案，而是一组高质量的假设，因此该假设足以满足我们的目的。为了解决这个问题，我们将考虑在未来的工作中使用边缘检测 (Liu et al. 2019) 或图像分割 (Cheng et al. 2016; Liu et al. 2018) 技术。其次，性能在视觉上相似但地理上不同的图像区域受到限制。此问题通常发生在具有大量重复模式的场景中。我们将问题留给全局几何估计算法（Kushnir 和 Shimshoni 2014），因为只有局部视觉信息不足以解决这个问题。第三，当我们在单元对级别处理数据时，位于正确单元对的不准确对应关系将仍然存在。这些对应关系在许多对匹配精度不敏感的应用程序中很有用，例如对象检索 (Philbin et al. 2007)。然而，对于精度敏感的任务，例如几何估计，它们应该被排除在外。因此，我们建议在 RT 选择的对应关系上运行 GMS，而不是所有假定的对应关系来缓解问题。

总结

1. GMS的速度为毫秒级，可以有效的运用到视频处理中，但精度不高，作者建议将GMS作为RANSAC的预处理工作，还可在RT的对应关系上运行GMS。GMS可能不适用于直接进行错误匹配去除工作
2. 邻域相似性约束不够严格，GMS可以去除单应性矩阵映射误差较大的对应关系，但对于误差较小的对应关系没有办法，这使得使用F分数进行性能评估的时候可能分数不会很高（目前我使用的F分数的误差阈值为1.5）
3. GMS受到阈值$\tau_i=\alpha\sqrt{|N_i|}$中超参数$\alpha$的影像
4. 旋转不变性：我们旋转基本内核来模拟不同的相对旋转，得到总共 8 个运动内核，如图 5 所示。旋转在实际问题中通常是未知的，因此我们使用所有运动内核运行 GMS 算法并收集最佳结果，即，我们找到了导致检索到大多数对应关系的内核。
5. 尺度不变性：两个图像之间的相对比例可以在我们的网格框架中模拟，即我们固定一个图像的单元格大小（单元格数）并改变另一张图像的单元格大小。假设两个图像都被划分为 n×n 个单元。我们将第二张图像的单元格数更改为 $(n·α)×(n·α)$。在这里，我们提供了 5 个候选 α，包括$\{\frac{1}{2},\frac{\sqrt{2}}{2},1,\sqrt{2},2\}$。同样，我们使用所有预定义的相对比例运行 GMS 并收集最佳结果。对于更显着的尺度变化，我们可以使用更多的候选者或增加 α。（实现尺度不变性，就是在所有尺度中进行计算，如SIFT）
6. 放射不变性：GMS假设在图像坐标中空间上接近的像素会一起移动。这是直观的，即想象相邻像素很有可能落在一个刚性物体或结构中，因此具有相似的运动。该假设通常不正确，例如，它可能在图像边界中被违反，其中相邻像素可能落在不同的对象中并且这些对象具有独立的运动。但是，它适用于规则像素，这些像素压倒性地超过边缘。此外，由于我们的目标是一组用于进一步处理的高质量对应假设，而不是最终的对应解决方案，因此该假设足以满足我们的目的。

补充内容

1. 二项分布

二项分布$S_i\sim B(n,p_t)$指的是如果点$x_i$是正确匹配点，那么$x_i$的邻域中正确匹配点数$S_i$的大小为k的概率为：

$P\{S_i=k\}=C_n^k p_t^k(1-p_t)^{n-k}$