基于改进网格划分统计的特征点快速匹配方法

陈方杰，韩 军， 王祖武

(1.上海大学 通信与信息工程学院，上海 200444；2.上海先进通信与数据科学研究院，上海 200444)

0 引言

图像特征匹配是计算机视觉领域中基础又重要的研究课题，其广泛应用于视觉SLAM，图像拼接和三维重建等领域[1]。基于特征的匹配策略一般是通过寻找两幅图像之间的局部映射关系来完成，主要包括点匹配[2]，线匹配[3]和区域匹配[4]等。由于特征点更易提取，匹配方式灵活，所以基于特征点的匹配算法在图像特征匹配中被普遍采用。基于特征点的匹配算法有两种：特征描述子相似约束和几何约束。

对于特征描述子相似约束，其实是使用特征点周围的信息作为描述特征，通过优化描述特征，提高匹配精度和匹配速度。SIFT(scale invariant feature transform)算法[5]在关键点邻域计算局部梯度，生成的描述子具有较好的尺度不变性和旋转不变性，但计算耗时较久，匹配描述子的计算量很大，实时性较低。文献[6]对SIFT算法进行改进，提出SURF(speed-up robust features)算法，其采用Hessian矩阵和积分图加快计算，但当图像间视角变换过大时，提取的特征点没有SIFT稳定，而且仍达不到实时性要求。Rublee等人[7]提出ORB(ORiented Brief)算法，其先利用改进的FAST (features from accelerated segment test)[8]算法检测特征点，再利用改进的BRIEF(binary robust independent elementary features)[9]算法计算特征点描述子，极大地提高了特征点检测和匹配速度。LIFT算法[10]利用卷积神经网络实现图像特征点检测、方向估计和特征描述符提取。其通过三步训练，可以比SIFT算法得到更多的正确特征点匹配对，对光照和季节性变化的图像具有更强的鲁棒性，但在训练过程中容易出现过拟合，而且对数据集依赖较大。

对于几何约束，传统的特征点匹配方法先使用NNDR (nearest neighbour distance ratio)算法[11]进行特征点匹配，再利用RANSAC (random sample consensus)算法[12]剔除错误匹配。RANSAC算法是从包含错误匹配的特征点匹配点集中，通过迭代方式估计数学模型参数的方法。其鲁棒性较好，但准确率会随着错误匹配的比例增大而降低，增大迭代次数可以提高一定的准确率，但运算时间也会增加，实时性较低。为了提供特征点匹配的效率和精度，Yuille等人[13]提出VFC (vector field consensus)算法，其使用公认集和几何约束来建立对应点，通过内插两个点集之间的矢量场来求解对应关系，然后使用Tikhonov正则化器计算图像的Hilbert空间。在此基础上，利用EM算法计算所提取的贝叶斯模型方差，最后与预期值对比，剔除错误特征匹配点对。Bian等人[14]提出GMS (grid-based motion statistics)算法，其将运动平滑度转换为区域对之间具有一定数量特征匹配的统计似然性。GMS算法提出九宫格划分法，较大地提高了特征点匹配速度，实时性较高。但该算法存在两个问题，第一个问题是当图像间旋转角度较小，甚至无旋转角度时，特征点匹配的准确率最高，但大多数成对的图像都会存在一定的旋转关系。该算法的解决方法是根据九宫格形状，计算8次不同状态下最大的九宫格特征分数，即增加额外7次旋转统计操作，此方法一定程度上解决了旋转关系问题，但相应增加了额外计算量。第二个问题是对于任何图像，GMS算法都是根据设定好的经验值来固定网格的划分数量，而且一般设定成横向网格数量与纵向网格数量相同。这种划分方法对于长宽比不一致的图像，其划分的网格呈矩形状，会使得在旋转统计操作时，网格中的特征点可能出现分布不均等问题。

基于上述分析，本文针对几何约束的GMS算法所存在的问题进行优化，提出一种改进网格划分统计的特征点快速匹配算法。本文主要的创新点是：1)改进网格统计方法，提出一种五宫格统计法，保证结构对称性的同时，减少了旋转次数，减少了计算量；2)改进网格划分方法，提出一种方形状网格划分法，将输入图像的长宽比作为约束项，确保划分后的网格形状不受输入图像的形状影响。

1 GMS算法

1.1 运动平滑

GMS算法本质上是匹配统计约束模型。对于从不同角度拍摄同一场景的成对图像，特征点匹配表示一幅图像上的特征点在另一幅图像上是一致的。如果场景中的物体发生移动，那么特征点相邻的像素和特征也将一块移动。运动平滑保证正确匹配的邻域看到相同的区域，而错误匹配的邻域看到不同的区域。从特征点的角度来看，在两幅图像上正确匹配特征点的邻域中会存在一些匹配特征点，而错误匹配特征点的邻域是不同的，所以错误匹配邻域中正确匹配的数量基本为零。

将{F1,F2}记为输入图像{I1,I2}的初始匹配点集，假设一共有N组匹配点对，所以其中F1={f1,1,f1,2,...,f1,N}和F2={f2,1,f2,2,...,f2,N}。

令{N1,N2}表示为{F1,F2}匹配点集的邻域，即N1={N1,1,N1,2,...,N1,N},N2={N2,1,N2,2,...,N2,N}。针对{f1,i,f2,i}粗匹配特征点对，计算在N1,i中的粗匹配特征点集{f1,i,1,f1,i,2,...,f1,i,Wi}和粗匹配特征点数量Wi。然后统计上述特征点初始匹配的特征点集{f2,i,1,f2,i,2,...,f2,i,Wi}和{f2,i,1,f2,i,2,...,f2,i,Wi}位于N2,i中的数量，记为特征邻域分数Si。其中令si,k表示N1,i中第k个特征点粗匹配对应的特征点是否位于N2,i的标志分数，若位于N2,i中，计分为1，反之不计分。最后根据分数阈值T来判定第i组粗匹配特征点对{f1,i,f2,i}是正确匹配还是错误匹配。

部分潮汕美食和传统节日相关文化负载词的翻译译者采用音译（潮汕方言），同时考虑到读者的认知能力，为使其无须付出不必要的努力，而获得充分的语境效果，所以在音译后面添加文本注释，既保留文化的差异性，又能帮助译文读者花较少的努力，获得较大的语境效果。音译加上文本注释可以看作是跨文化传播策略初期的一种尝试，甚至可以培养语境，慢慢消除“意义真空”。

(1)

(2)

1.2 九宫格统计法

为了提高特征邻域分数的计算速度，GMS算法将输入图像进行网格划分，生成G=P×Q个网格，其中P表示纵向网格数量，Q表示横向网格数量，即将邻域统计问题转化为网格统计问题，如图1所示。在统计特征点所在网格的特征分数的同时，统计环绕其四周相邻的8个网格的特征分数，其中Si,j表示第i个网格所在的九宫格中第j个网格特征分数。九宫格如图2所示，其中G1,5表示I1中一个特征点所在的网格，G1,1,G1,2…,G1,9表示G1,5相邻对称的8个网格。GMS算法将此方法的特征邻域分数之和称为九宫格特征分数S，公式如下：

(3)

图1 网格划分和九宫格网格邻域

(4)

(5)

(6)

(7)

其中:α为权重稀疏系数，一般设置为6。

图2 九宫格示意图

图3 九宫格旋转示意图

2 改进的五宫格划分统计

2.1 五宫格统计法

对特征点所在的网格需要计算8个额外相邻网格的特征分数，这种统计方法会增加不必要的计算量。根据观察，本文针对网格分布的对称性，旨在保持鲁棒性的前提下，只统计与当前网格相邻且对称的4个网格特征分数，分布情况如图4所示。将此方法的特征邻域分数之和称为五宫格特征分数S，计算公式如下：

(8)

(9)

(10)

阈值T的计算公式修改如下：

T=μln(αWi+β)

(11)

其中:α是特征点数量均值Wi的权重系数，β是对数函数的偏差系数，μ是对数函数的权重系数。

图4 五宫格示意图

图5 五宫格旋转示意图

2.2 方形状网格划分法

GMS算法中网格划分的P值和Q值都是人工定义的经验值，一般设置为P=Q，这样的经验值会限制网格划分数量，对于长宽比例不一致的图像，会生成不同的矩形状网格，导致九宫格或者五宫格内每个网格中粗匹配特征点数量分布不均，如Iw:Ih=4:3，P=Q=8时，划分结果如图6所示。

针对这个问题，本文提出将每幅图像的长宽比值作为约束项，目的使得划分的网格形状接近规则的正方形，即只通过一个经验值E和图像自身的长宽比值来初始化P值和Q值。经验值E，P值和Q值的计算关系如下：

(12)

比如当Iw:Ih=4:3时，令E=8，则P=6,Q=8, 所以五宫格划分的结果如图7所示。

图6 矩形状网格

3 实验结果与分析

本文算法利用Visual Studio 2013编写C++代码，在CPU为2.3 GHz Intel core i5，12 GB内存的计算机上运行。本文采用了被广泛使用的Oxford公开标准数据集[15]，该数据集共有8组图像，包含多种类型的图像变化，如平移、旋转和视角变换等，本文针对其中bike和graffiti这两组图像进行测试，图像尺寸分别为1 000×700和800×640，如图8(a)～8(b)所示。同时为了验证本文算法的实际应用效果，本文采用两组由无人机实际拍摄的遥感图像进行测试，图像尺寸为7 952×5 304，如图8(c)～8(d)所示。

本文算法的实验数据参数统一设置为{N,E,μ,α,β}={3 000,25,10,1.1,2}，其它比较算法均使用默认参数。为公平起见，所有算法的输入是相同的ORB特征点和粗匹配点集。

3.1 图像匹配评价指标

本文采用精确率，召回率和运算时间3个评价指标对算法进行综合评价。

1)精确率(Precision)表示预测为正确匹配的样本中真正正确匹配的比例，定义如下：

(13)

2)召回率(Recall)表示预测为正确匹配的样本占所有真正正确匹配的比例，定义如下：

(14)

其中:TP表示检测出的正确匹配的样本数量，FP表示将错误匹配误检为正确匹配的数量，FN表示将正确匹配误检为错误匹配的数量。

3)采用精匹配运行时间对匹配速度进行评价。

3.2 图像匹配实验结果

首先使用实时性较高的ORB算法对每幅图像检测出3 000个特征点，然后利用暴力匹配法得到图像间的3 000组粗匹配点对，最后利用RANSAC算法，VFC算法，GMS算法和本文算法进行特征点精匹配的实验比较。最终的实验结果都是对每组图像数据进行50次测试的平均结果。

表1 特征点精匹配对数结果

表2运算时间结果 ms

方法图8(a)图8(b)图8(c)图8(d)RANSAC93.19132.28122.65131.27VFC41.8948.6339.8648.97GMS20.2223.7526.1329.77本文算法14.8717.5219.6821.53

通过表1和表2上的实验结果可知，RANSAC算法剔除特征点错误匹配后，剩余的特征点数量最少，且由于自身算法复杂度较大，因此运算时间最长，平均耗时119.85 ms。VFC算法剔除错误匹配后，剩余的特征点数量相对最多，运行速度明显优于RANSAC算法，但运算时间还是较久，平均耗时44.84 ms。GMS算法剔除错误匹配后，剩余的特征点数量与VFC算法相近，平均耗时24.97 ms。而本文算法剔除错误匹配后，剩余的特征点数量也相对较多，略少于VFC算法，但运行速度最快，平均耗时18.41 ms，相对于GMS算法，提高35.6%。因此在运算速度方面，本文算法相对于RANSAC算法，VFC算法和GMS算法有明显的提升。

表3 精确率结果 %

表4 召回率结果 %

通过表3和表4上的实验结果可知，RANSAC算法的平均精确率适中，而平均召回率为89.71%，在这4种算法中相对最低。VFC算法的平均精确率整体高于RANSAC算法，且平均召回率在这4种算法中最高。GMS算法的平均精确率略低于VFC算法，而平均召回率较高。本文算法的平均精确率与GMS算法相近，平均召回率略低于GMS算法，分别可达97.25%和92.85%。由上述可知，将九宫格统计法替换成五宫格统计法，精确率没有明显变化，虽然召回率相对略有减小，但仍然属于有效范围内。

4 结束语

针对目前特征点匹配算法计算时间长，无法应用在对实时性要求较高的领域等问题，如视觉SLAM，本文提出了一种改进网格划分统计的特征点快速匹配算法。把图像的长宽比作为约束项，使得划分的网格呈方形状，并根据对称性将特征点所在网格相邻的4个网格作为邻域来统计五宫格邻域分数。相比于GMS算法，统计网格数量和旋转次数都减少一半，较大地提高了特征点匹配效率。实验结果表明，与目前特征点匹配算法相比，本文算法在保持较高精度的情况下，具有较大的速度优势，综合效率较高。