GMS论文阅读

主要对论文《GMS: Grid-based Motion Statistics for Fast, Ultra-robust Feature Correspondence》进行翻译和测试

（GMS:一种基于网格运动统计的快速鲁棒的特征匹配方法）

这篇论文主要针对特征匹配问题，提出了一种基于网格的、运动统计特性的方法，该方法可以迅速剔除错误的匹配，从而提高匹配的稳定性。该方法的效果与SIFT匹配的效果对比如下：

图 1 SIFT特征匹配（左）与GMS特征匹配（右）

文章的主要贡献如下：

1.将运动平滑限制转成去除错误匹配的数据测量；

2.提出了一种有效的基于网格的分数估计方法，使得特征匹配算法能达到实时性；

3.将GMS方法与传统的SIFT、SURF、LITF特征进行对比，表明GMS方法在时间与准确率方面都要优于其他算法。

该算法的基本思想是：先对两张图片Ia和Ib分别提取关键点和描述子，设分别有N和M个；对两张图片的特征点进行BF匹配，这样找到了图片Ia中每个特征点对应的Ib中的最邻近的特征点。由于运动的平滑性，在正确匹配的特征点附近的正确匹配点对数应该大于错误匹配的特征点附近的正确匹配点对数。这样我们就可以根据BF匹配好的特征点xi附近的正确匹配个数n与阈值来判断该点是否被正确匹配。所以主要问题就集中在：①如何合理选取阈值；②匹配点xi的小邻域范围应如何选取；③若对每个点都进行统计会消耗大量时间，思考应提高运算效率。

文章主要用到的主要符号定义及理论推导如下：

首先提出假设1：如果两个特征点匹配正确，那么两个特征点附近很小的一个区域可以看做对应同一个3D位置。如图 2所示，对于一个匹配xi，在Ia、Ib两幅图上的小邻域记为a和b。若xi匹配正确，则a和b对应同一个3D区域，所以a和b内匹配的点对数较多；同理，若xj匹配错误，则对应的小邻域内匹配的点对数就较少。引入一个分数估计方法Si，表示匹配点xi小邻域内匹配的点对数，如下图xi邻域内的匹配点对数为2则Si=2，xj邻域内的匹配点个数为0，则Sj=0。

图 2 匹配过程

假设二：如果某一点匹配错误，则它正确的匹配点在整幅图片所有特征点M内的概率相同。因此，则有：

图 3 fa的事件空间

图3表示fa的事件空间，可以看出当xi匹配正确时，fa的匹配点可能在b内也可能不在b内，若fa的匹配点在b内则fa可能匹配正确，也可能没有匹配正确。同理，当xi匹配不正确时，fa的匹配点可能在b内也可能不在b内，若fa的匹配点在b内则fa一定匹配错误。令

则有：

令

则有：

根据大数定律，当事件足够大时，正确匹配与错误匹配就会出现规律，即t就一定。因此，pt和pf在某种情况下可看成定值，所以，若xi匹配正确与匹配错误时邻域a内正确匹配点服从一个二值分布：

画出图如下：

图 4 正确匹配点（右）与错误匹配点（左）附近正确匹配点对的概率分布

以上的方法与推导仅限于邻域a和b足够小，但很多情况下达不到足够小的要求，因此可以将一个较大的区域分成K个很小的区域，再次用以上公式。所以概率分布：

Si的均值与方差分别为：

在统计事件中，如果一个事件偏离其中值很多个标准差我们会认为此事件不会发生，我们因此会希望以下公式越大越好，P越大就会越具有区分度。

增大P有两种方式：增大K或者增大n。当n增大时运算量就会大大增加，但是准确度会提高，这是其他方法增大准确度的一种途径，如图5，在本文中我们会增大K，使运算减少时还能保证准确率。

图 5 特征点n增大时SIFT（上）与GMS（下）的效果图

下面的部分主要解决以下问题：

（1）基于网格分割的分数计算；

（2）网格应该多大；

（3）一张图应该划分为多少小方格；

（4）如何计算出阈值。

正常情况下，若分别为每个匹配点找邻域内的匹配对数，需要完成次运算，但是如果我们引入网格，划分完网格后，以每个网格当作一个小邻域，对网格内的每个匹配点来说分数估计值都一样，所以每个网格内的所有匹配点只需统计一次即可，不需要对每个点分别统计，节约了大量时间。但是可能有特征点正好位于网格边缘，我们可以通过将网格平移半个单位重新计算。

一张普通的图片，正常情况可以有10000个特征点，假设该特征点均匀分布，则若进行20*20的网格划分，每个网格平均有25个特征点，这时比较好计算。在本文的方法中都进行20*20的网格划分，若遇到更加复杂纹理多的图片可以加大网格划分。

但是划分出的大网格是不具备足够小这一假设的，所以每个大网格还要继续划分，令K=9，即每个大网格还要继续划分成9个小网格，如图6，所以统计的分数应该是9个小网格内的分数和。