基于动态窗口运动统计信息的特征匹配筛选算法

相恒永 周莉 巴晓辉，3† 陈杰

(1.中国科学院微电子研究所，北京100029;2.中国科学院大学电子电气与通信工程学院，北京100049;3.中国科学院大学微电子学院，北京100049)

基于局部特征的图像匹配是计算机视觉的基础工作之一，被广泛应用于全景拼接、三维重建、视觉导航等热门领域。该工作的主要思路是:从输入图像中提取关键点并计算描述子，然后通过描述子的相似性进行匹配，从而得到输入图像中不同局部特征点之间的对应关系。而在很多情况下，仅仅依靠特征进行的图像匹配结果不会很理想，这是因为手工设计的特征的可区分性与可重复性很难在所有的场景中都起作用。因此，如何从已经得到的匹配集合中滤除错误匹配成为了一个值得研究的问题。

比较经典的方法是RANSAC(随机抽样一致性)算法［1］，该方法使用随机抽样一致性方法建立特征匹配约束的空间几何模型，并借助建立的模型过滤错误匹配。但由于二维平面点空间约束的不完备性，很多时候这种方法的效果并不是很好。因此，近年来的很多工作均聚焦于利用特征匹配之间的局部约束过滤错误匹配的方法。在2017年的CVPR(IEEE国际计算机视觉与模式识别会议)上，Bian等［2］提出了一种叫做GMS(基于网格的运动统计)的算法，它利用基于网格的运动统计建立局部约束关系模型过滤错误匹配。该算法在速度与效果上都表现得很好。但是由于其使用了固定尺度、固定位置的网格，因此在尺度变换较大或者旋转角度过大的场景中的匹配效果不佳。Ma等［3-5］提出了一种LPM(局部保持匹配)方法，这种方法通过保持局部结构信息可以得到很好的匹配效果，不过其对于原始的输入匹配集合质量有较高要求，一般需要原始匹配集合中正确匹配的占比大于50%。因此文献 ［3-5］采用经过预处理的SIFT(尺度不变特征变换)［6］特征匹配结果作为算法输入。STFT特征具有较高的鲁棒性，但是比较耗时，这使得算法很难应用于实时任务。

由于目前特征匹配工作在视觉导航、实时三维重建等领域应用较多，因此保证特征匹配的实时性非常重要。而上述方法中真正可以实时应用的GMS算法在面对尺度变换较大或者旋转角度较大的场景时表现不佳。为了得到一种实时的、鲁棒的、实用的特征匹配筛选算法，文中深入分析了运动统计方法的数学原理，提出了一种新的基于运动统计的特征匹配筛选算法，下文中称这种算法为DWMS(动态窗口运动统计)算法。DWMS算法使用可以动态调整尺度与位置的窗口代替网格进行运动统计，同时考虑到动态窗口的建立时间较长，故采用快速近似最近邻［7］算法加速窗口的建立过程。

1 匹配的局部约束与GMS算法

对两幅图像完成特征匹配后，如何从匹配集合中过滤出错误的匹配是本文研究的重点。本节主要是描述匹配的局部约束关系原理，并给出相应的数学分析，最后介绍基于网格的运动统计方法的原理与局限性。

1.1 特征匹配的局部约束原理

通常用作局部特征匹配的两张图片，是由摄像机从不同的角度对同一实物场景拍摄的。一个正确匹配的两个端点是由真实世界中同一三维点在两个相机成像平面上投影形成的。如果将点拓展成块，真实世界中的一个立方体块在分别投影到两个成像平面上后就是对应的两个平面区域，此时在这两个平面区域中检测到的特征点应该是相互匹配的，这是一种天然的约束。

如图1所示，假设其中的一个匹配xi(鼻子处)是正确的，则在其邻域 (周围黄色圆圈区域)中还会存在一些其他的匹配对与其指向一致，文中称这些匹配对是匹配xi在其邻域中的支持匹配。相反，如果一个匹配xj(嘴巴处)是错误的，则在这个匹配的邻域 (周围红色圆圈区域)中将很难再找到其他的匹配。基于这一事实，在得到初始的匹配集合后，可以通过这种邻域的约束关系完成匹配集合的筛选工作。

1.2 对特征匹配局部约束的数学分析

假设在两幅不同的图像I1、I2中存在相同的场景，从这两幅图像中分别提取出N个特征点，最近邻匹配后得到如下匹配集合:

图1 正确匹配与错误匹配的邻域约束对比Fig.1 Comparison of correct matching and mismatched neighborhood constraints

从中选定一个匹配xi，假设这个匹配的两端点在I1、I2上的邻域分别为a、b。已知在邻域a、b中分别提取出了n、n′个特征点。如果匹配xi是错误的，则邻域a中的其他n-1个特征会无规律地匹配到图像I2的N个特征点上，假设此时其落在邻域b上的概率为Pf;反之，如果匹配xi是正确的，则假设其落在邻域b上的概率为Pt。令Si表示邻域a、b中的匹配数量，也就是匹配xi的支持匹配的数量。由文献［2］可知在一定假设下Si服从如下二项分布:

图2中画出了更加直观的分布形式。

图2 正确、错误匹配的邻域得分分布情况Fig.2 Positive and false matching neighborhood score distribution

如果匹配xi是错误的，则Si的均值mf与标准差sf为

可以使用下式表示上述正确、错误两类分布的类间距:

基于运动统计方法的目标就是在保证计算量的前提下设计出使D足够大的算法，并据此完成匹配的筛选。

1.3 基于网格的运动统计方法

前文介绍了匹配的局部约束关系，而运动统计是描述这种局部约束关系的方法，基于网格的运动统计算法GMS在2017年被提出，该算法通过将图像划分为网格来进行运动统计。值得一提的是，在GMS算法中并不是仅仅只评估两个对应网格的运动统计。如图3所示，在GMS算法中，首先使用一定数量的网格对图像进行划分。当待验证匹配的两端分别落在网格i5与j5中时，统计网格i5与j5中的匹配的数量，当其高于一定阈值时，会继续对i5与j5周围的8对网格进行运动统计，只有在周围8个网格对 (i1到j1，i2到j2，…，i9到j9)的运动统计加起来大于一定阈值时才会认为该匹配有效。

图3 基于网格的运动统计示意图［2］Fig.3 Diagram of motion statistics based on grid

上述实现思路带来了两个问题。首先，GMS算法固定网格划分的尺寸，这使得算法不具备尺度不变性。虽然文献 ［2］中提到GMS算法可以通过对图像做尺度缩放来解决这个问题，但是由于事先并不知道第2幅图像相对于第1幅图像的尺度变换比例，因此需要在很多尺度空间上分别进行GMS算法，然后选取其中结果最好的。比如在GMS的多尺度版本实现中一共在5个尺度空间上进行了GMS操作，它们的缩放尺度分别为1、、2。在上述5个尺度空间上分别执行GMS算法，然后比较结果，从而选取最好的一个作为输出。这种做法的缺点一是不能精确定位最佳尺度，使得算法结果很难达到最佳，二是不同尺度空间上的重复操作会降低 GMS算法的时效性。其次，GMS算法同样不具备旋转不变性，很显然，GMS算法基于九宫格的运动统计假设了两幅图像中匹配所处的中心网格周围的8个网格一一对应，而当上述两幅图像相对旋转一定角度时，该一一对应关系便不再适配。虽然类似尺度变换场景，GMS算法中提供了一个较简单的解决方案，即对第2幅图像上九宫格外围的8个网格做依次旋转然后分别进行GMS操作，最后选取其中效果最好的那个。但是这种做法也带来了同样的问题:①由于不能精确定位旋转角度，如果待处理两幅图像之间的旋转不刚好是45°的倍数时，最后的结果都会受到影响;②在不同旋转角度上的重复操作会降低GMS算法的时效性。

综上，GMS算法基于网格的运动统计方式足够新奇，但是带来的两个问题同样需要解决。

2 DWMS算法

前文详细分析了特征匹配的局部约束原理，并介绍了GMS算法的原理与不足，接下来介绍基于动态窗口的运动统计方法DWMS算法与其实现细节。

2.1 基于动态窗口的运动统计

前文关于局部约束的数学分析是在匹配的邻域上进行的，在GMS算法中使用固定尺寸与位置的网格来确定邻域，这使得其不具备尺度不变性与旋转不变性。在DWMS算法中使用动态窗口为匹配确定邻域范围，这个动态窗口以该匹配为中心，分别为该匹配的两个端点确定邻域范围。确定邻域范围后，便可以通过运动统计算法完成对正确匹配与错误匹配的划分。

首先，选定一个匹配xi，确定其在I1与I2上的邻域a、b，邻域a、b中均存在n个特征点。文中算法定义该匹配在邻域上的运动统计得分为

式中，xab为邻域a、b上特征匹配的数量，也就是匹配xi的支持匹配数量。参考图2中的概率分布，即运动统计得分越高的匹配是正确匹配的概率也越高，文中设置

作为阈值区分出错误匹配，如式 (4)中表示的一样，mf、sf分别为错误匹配的支持匹配数量均值和标准差，α为对sf的一个调和参数，它的作用是确保更多错误的匹配可以被找到。

最后，本文方法使用如下公式判别匹配xi是正确匹配还是错误匹配:

式中，T为DWMS算法最终保留的匹配集合，F为被DWMS算法滤除的匹配集合。

2.2 动态窗口的获取

本文方法基于动态窗口确定匹配的邻域范围，在确定超参数n后，如何建立动态窗口是一个关键的问题。

使用传统暴力最近邻的方式获取DWMS所需的动态窗口复杂度较高，会使算法丧失实时性。本文考虑到此处所需的动态窗口无需是严格的最近邻窗口，因此DWMS算法采用快速近似最近邻算法加速动态窗口的获取。

快速近似最近邻算法有很多，此处选用的是kd 树 (k-dimension tree［8］)算法。该算法比较简单，并且在低维空间中表现优异，比较适合此处的应用场景。该算法的主要思路是根据给定的相似性度量方式在搜索空间中建立一棵二叉树，通过这棵树对搜索空间进行层层划分，树的每个节点都代表整个搜索空间的一个子集，其中根节点代表整个搜索空间，子节点将父亲节点代表的搜索空间划分成两个大小相同的不相交子集，并存储自身每个维度的边界值。

图4所示的是k-d树在二维空间中的经典划分方式，它使用一个正方形平面代表整个搜索空间，搜索空间中每个点用两维坐标 (X，Y)表示，依次通过点的数量分布对空间进行二等分，在划分完毕后其对应的k-d树的树状结构如图5所示。此处需要指出的是，对于一个大小是N的集合，使用暴力搜索的平均时间复杂度是O(N)，而使用k-d树结构的索引结构进行索引的平均时间复杂度仅为O(lbN)。

图4 二维搜索空间划分Fig.4 2D search space partition

图5 k-d树结构Fig.5 k-d tree structure

在本文算法中，一张图像代表一个二维平面，每个特征点在图像上都有一个二维坐标代表其在图像中的位置。DWMS算法会据此建立k-d树索引，对一个匹配xi建立动态窗口的过程其实就是利用k-d树算法获得当前匹配的n近邻窗口的过程。

2.3 超参数n大小的确定与分析

DWMS算法中使用动态窗口为匹配确定邻域范围，动态窗口以该匹配为中心，寻找距离该匹配最近的其他匹配构成邻域。此时窗口内的匹配数量即该匹配邻域中的匹配数量n，由1.2节的推导可知类间距D服从如下规律:

即邻域中匹配数量越多，错误类与正确类的统计差异越明显。但是，上述推导的一个前提是邻域a、b是局部的，这意味着如果邻域范围很大，局部约束的概念便不再适用。并且随着邻域中匹配数量的增大，基于k-d树的最近邻算法复杂度增长较快。因此邻域大小的确定是一个需要仔细考虑的问题。下文会结合实验对n的取值进行详细说明。

2.4 DWMS算法的实现

经典的手工设计的局部特征算法有 SIFT、SURF(加速鲁棒特征)算法［9］、KAZE 算法［10］等，近期基于深度学习的局部特征算法有LIFT(学习不变特征变换)算法［11］、Superpoint算法［12］等，都可以作为本文算法的前置算法。最终考虑到本文任务对实时性和鲁棒性的较高要求，经过大量实验验证，最终DWMS算法选用更加快速、简单的 ORB(Oriented FAST and Rotated BRIEF)［13］特征。同时算法实现时有3个环节需要特别标注:①使用Flann(快速近似最近邻搜索库)［14］实现初始匹配的快速构建;②采用k-d树的索引结构加速动态窗口的建立;③经过实验，为了保证邻域a、b可以具备更好的兼容性，本文算法设置邻域b中的特征数量是邻域a中的1.2倍。

DWMS算法详细步骤如下。

输入:一对图像 I1、I2，匹配集合 C={xi;

输出:正确匹配集合 T={ti′}，其中 ti′为第i′个正确的匹配，nt为正确匹配的数量;

(1)基于两张图像中的特征点集合构建两个快速最近邻索引结构;

(2)对匹配集合C中的每个匹配构建n近邻邻域;

(3)在每个匹配的邻域范围内，计算其运动统计得分Si与判断阈值;

(4)根据式 (8)判断匹配的合理性，将合理匹配 ti′加入 T;

(5) 输出结果 T={ti′}。

3 实验

实验部分主要分为6个部分进行介绍，首先是进行算法衡量指标的介绍，接下来介绍本文实验涉及到的4个数据集，最后从几个方面来具体测试DWMS算法的综合性能。一是考察超参数n的不同取值对算法效果的影响;二是进行DWMS与GMS算法、DWMS与RANSAC算法的对比实验;三是对上述各种算法的耗时进行对比。下文实验的运行环境是ubuntu16.04系统，处理器型号为Intel Core i5-4200U，4 GB内存，开发语言为 C+ +，OpenCV版本为4.0.0。

3.1 衡量指标介绍

通常以正确匹配为正类、错误匹配为负类，正确匹配的筛选就变成了一个二分类问题。对于二分类问题常用的评价指标是精确率与召回率［15］。依据分类器在测试集上预测的结果，会出现如下4类情况:①将正确匹配预测为正类，将此类个数记为TP;②将正确匹配预测为负类，将此类个数记为FN;③将错误匹配预测为正类，将此类个数记为FP;④将错误匹配预测为负类，将此类个数记为TN。可以通过如下公式计算出匹配结果的精确率P与召回率R:

下文中较多使用精确率与召回率的调和均值F1来综合评价匹配的性能。

3.2 实验数据集介绍

实验中一共涉及了4个数据集。第1个数据集是专门用于特征匹配的VGG数据集［16-17］，全名为Affine Covariant Regions Datasets，这个数据集提供了8组图像序列共40张图片，这些序列分别代表了图像模糊、尺度缩放、旋转变换、视角变换和光照变换等场景。每个图像序列包含6张图片与图片对之间对应的单应矩阵信息。第2个数据集是被广泛用于视觉同时定位与建图的TUM［18］数据集，全名为RGB-D SLAM Dataset and Benchmark，这个数据集一共3141张图片，提供了彩色图片和与之对应的深度图，同时提供了摄像机的运动轨迹真值信息。整个数据集提供了各种条件下的测试场景。第3个数据集是三维重建数据集 Strecha［19］，全名为Dense Multi-view Stereo Dataset，这个数据集一共500张图片，提供了每张图片的位姿和场景的3D模型，整个数据集纹理比较丰富。最后一个数据集是Cabinet［18］，这个数据集与TUM数据集一样，由慕尼黑工业大学提供，一共578张图片，提供了彩色图片和与之对应的深度图，同时提供了摄像机的运动轨迹真值信息。整个数据集记录了强光照条件下的低纹理环境。

3.3 超参数n的分析实验

由前文的分析可知，本文方法通过超参数n确定匹配的邻域范围，而邻域范围的大小对基于局部约束的匹配筛选方法具有较大影响。为了确保最终匹配的性能与效率，本文设计如下实验。在3.2节提到的4种数据集上，当每对图像一共具有500、1000、2000个特征匹配的情况下，分别绘制出由DWMS算法得到的精确率与召回率的调和均值F1和每对图像进行匹配的平均耗时与超参数n的对应关系曲线图，如图6所示。由图6可以发现，超参数n的取值在1到5之间时，DWMS算法得到的F1值会有一个迅速的提升，之后便会逐渐趋于稳定，n继续增大对性能提升不再明显。而随着n的增大，DWMS算法的耗时也会近似呈线性趋势上升，故n的取值不宜过大。因此综合考虑算法表现与时间成本，通过如下公式设置超参数n的大小效果较好:

n的取值被控制在5到10之间，此时DWMS算法性能已经达到较高水准，同时基本可以保证算法耗时在几十毫秒左右，可以实时应用。此处需要说明的一点是，由于本文主要提出的是一种可以实时应用的特征匹配筛选算法，所以图像提取的特征点总数不宜过多，因此实验假设的2000已经是一幅图像提取特征点的最大数量，超过2000时仅仅特征点的提取与匹配工作便很难实时进行。

图6 n对匹配的影响Fig.6 Effect of n on matching

3.4 DWMS与GMS算法的对比实验

由于本文算法与GMS算法都是对局部约束进行运动统计的方法，所以本文针对这两种算法进行一次详细的对比。首先分别在4种数据集上针对旋转角度与尺度变化进行实验，然后在其他更丰富的场景下进行实验，并依此对两种算法进行全方位的对比。

3.4.1 DWMS与GMS算法的旋转与尺度变化实验

首先，由于本文算法对GMS算法的主要优势是在旋转与尺度变换的场景中，因此首先在此场景下进行实验，其中VGG数据集是标准的特征匹配数据集，其boat序列主要用来验证算法是否可以适应旋转与尺度变化的场景，图7关于VGG数据集的实验中以序列中的boat 1为基准，横坐标所示2-6是另外5张图片的序号 (分别对应boat 2到boat 6)，而另外3个数据集都是用于视觉同时定位与建图或者三维重建的数据集，因此本文统计图片序列的旋转角度，据此绘制出在旋转角度从0°到30°变换时的算法性能变化 (在此类数据集中缩放信息不容易确定，因此暂且只考虑角度变换)。绘制出的GMS算法、多角度多尺度版本的GMS算法(图中简称为MGMS)及DWMS 3种算法在4种数据集中的表现如图7所示。

图7 GMS与DWMS算法的旋转不变性实验Fig.7 Rotation invariance experiment of GMS and DWMS

从图7中可以发现，在旋转变化的情况下，DWMS算法相对GMS算法优势明显，对多角度多尺度版本的GMS算法也具备一定优势。

最后，为了更加直观地对比DWMS与GMS算法在这个序列上的匹配结果，本文画出了这两种算法在boat序列上boat 1与boat 6的匹配效果图 (见图8)，其中红色线代表错误匹配，黄色线代表正确匹配。

图8 两种算法的匹配效果图Fig.8 Matching effect diagram of two algorithms

3.4.2 DWMS与GMS算法的其他场景实验

本文对其他场景下DWMS与GMS算法的匹配性能进行了对比。一共在6个场景下进行实验，分别是VGG数据集的bikes、graf、leuven和ubc序列上与TUM数据集的freiburg3_structure_texture_far序列上以及Cabinet数据集上进行实验。其中bikes序列展示了模糊变换的场景，graf序列展示了视角变换的场景，leuven序列展示了光照变换的场景，ubc序列展示了图片压缩变换的场景，TUM数据集的图片序列展示了纹理与结构丰富的场景，Cabinet数据集展示了强光照条件下的低纹理环境。本文会以每个序列的第1幅图片为基准，将接下来的图片与其进行匹配，并应用匹配筛选算法，最终获得两种算法 (GMS与DWMS算法)匹配筛选的调和均值F1，结果如表1所示。

表1 其他场景下GMS和DWMS算法的F1值对比Table 1 Comparison of F1obtained by GMS and DWMS in other scenes

由表1可以发现，本文算法在更多的场景中具有较优的表现。因此，本文算法在显著提高了旋转与尺度变换场景性能的同时，并没有牺牲其对其他场景下的鲁棒性。

3.5 DWMS与RANSAC算法的对比实验

RANSAC算法是综合性能均衡的算法，其基于两视图平面几何约束进行匹配的筛选，目前被广泛采用。本文方法是基于局部约束的筛选算法，与基于空间约束的方法原理差异较大，但是两者应用任务相同，因此有必要对这两种算法进行详细的对比实验。首先在VGG数据集上对比两种算法在各种常见的、具有挑战性的场景下的表现，然后通过修改阈值，对比两种算法在TUM数据集上的P-R曲线［20］差异，以此来观察两种算法的性能特点。

3.5.1 DWMS与RANSAC算法在VGG数据集上的对比实验

首先本文在VGG数据集上进行两种算法在不同挑战下匹配的性能分析。其中，bikes与trees表示的是平滑操作的序列，graf和wall是视角变化的序列，bark和boat是缩放与旋转变换序列，leuven是亮度变化的序列，ubc是图像压缩下的序列。由表2可以发现两种算法在很多场合下效果相当，在视角变化场景下RANSAC算法较有优势，在平滑变换的图片上本文算法效果更优。

表2 VGG数据集上两种算法的对比实验数据Table 2 Comparison of experimental data obtained by two algorithms

3.5.2 DWMS与RANSAC算法在TUM数据集上的对比实验

在一些任务中可能会要求算法达到一定的召回率或精确率，本文会在TUM数据集上进行实验，做出两种方算法的P-R曲线［20］，通过对两种算法阈值的修改，来考察两种算法的召回率与精确率特性。如图9所示，在TUM数据集上，室内机器人主动探索的一般场景下，总体来看本文算法所得P-R曲线下的面积更大，综合性能更加全面。另外在召回率大于90%时，RANSAC算法具有一定优势，但当召回率小于90%时，DWMS算法综合性能会更好一些。这说明基于空间约束的RANSAC算法在高召回率要求时表现较为优秀，但是由于两视图下平面约束的不完备性，使得其在高精确率要求下表现不佳。而基于局部约束的DWMS算法在一般场景下可以得到更高的精确率。因此在与其他匹配方法［21］进行协同工作时，RANSAC算法更适合作为前置操作，本文算法更适合作为后置操作。

图9 两种算法的P-R曲线图Fig.9 P-R curve of two algorithms

3.6 算法耗时对比

本文也对这3种算法的耗时进行了测量。在每张图片提取2000个ORB特征点的情况下，测量3种算法在每张图片上的平均总耗时，得到GMS算法、DWMS、RANSAC、多尺度多角度版本的GMS算法平均每张图片耗时分别为143.12、191.79、185.28、276.57ms。

从上述实验结果可以发现本文算法的时间性能相比于单尺度单角度的GMS算法稍有落后，与RANSAC算法相比基本处于同一水平，但优于多尺度多角度版本的GMS算法。

4 结论

本文提出了一种利用动态窗口进行运动统计的特征匹配筛选算法，该算法十分简单、有效。由于在使用ORB特征进行快速特征匹配时往往会出现原始匹配中错误匹配较多的问题，故本文算法利用特征匹配的局部约束关系完成错误匹配的过滤，使用动态窗口灵活的适应尺度与角度变化大的场景，应用快速近似最近邻算法加速动态窗口的建立过程，提高整体匹配的实时性。实验表明本文算法有效地解决了运动统计方法不能适应尺度与旋转变化场景的问题，并保持了其在其他场景下的良好表现;同时本文算法具有良好的时间性能，可以应用于实时任务。