基于改进网格运动统计特征的图像匹配算法

朱成德 李志伟 王凯 高燕 郭亨长

摘 要：为了解决尺度不变特征变换（SIFT）算法在图像匹配中匹配正确率低、耗时长等问题，提出一种基于改进网格运动统计特征RANSAC-GMS的图像匹配算法。首先，利用快速旋转不变性特征（ORB）算法对图像进行预匹配，对预匹配的特征点采用网格运动统计（GMS）来支持估计量以实现正确匹配点与错误匹配点的区分;然后，采用改进的随机抽样一致性（RANSAC）算法通过匹配点间的距离相似性对特征点进行筛选，并采用评价函数对筛选后的新数据集进行重新整理，进而实现对误匹配点的剔除。采用Oxford标准图库和现实中拍摄的图像对图像匹配算法进行测试对比，实验结果表明，所提算法在图像匹配中的平均匹配正确率达到91%以上;与GMS、SIFT、ORB等算法相比，该改进算法的近景匹配正确率和远景匹配正确率分别最少提高了16.15个百分点和3.56个百分点，说明它能有效剔除误匹配点，进一步提高图像匹配精度。

关键词：图像匹配;特征点匹配;距离相似性;误匹配;网格运动统计

中图分类号： TP391.41

文献标志码：A

Image matching algorithm based on improved RANSAC-GMS

ZHU Chengde1，2， LI Zhiwei1*， WANG Kai1， GAO Yan1， GUO Hengchang2

1.School of Electronic and Electrical Engineering， Shanghai University of Engineering Science， Shanghai 201620， China ;

2.Shanghai M&G Stationery Incorporation， Shanghai 201406， China

Abstract： In order to solve the problem that Scale Invariant Feature Transform （SIFT） algorithm has low matching accuracy and long time consuming in image matching， an improved image matching algorithm based on grid motion statistical feature， namely RANSAC-GMS， was proposed. Firstly， the image was pre-matched by Oriented FAST and Rotated BRIEF （ORB） algorithm and Grid-based Motion Statistics （GMS） was used to support the estimator to distinguish the correct matching points from the wrong matching points. Then， an improved RANdom SAmple Consensus （RANSAC） algorithm was used to filter the feature points according to the distance similarity between the matching points， and an evaluation function was used to reorganize the filtered new datasets to eliminate the mismatching points. The experiments were carried out on Oxford standard image library and images taken in reality. Experimental results show that the average matching accuracy of the proposed algorithm in image matching is over 91%. Compared with algorithms such as GMS， SIFT and ORB， the near-scene matching accuracy and the far-scene matching accuracy of the proposed algorithm are improved by 16.15 percentage points and 3.56 percentage points respectively. The proposed algorithm can effectively eliminate mismatching points and achieve further improvement of image matching accuracy.

Key words： image  matching; feature point matching; distance similarity; wrong matching; Grid-based Motion Statistics （GMS）

0 引言

图像匹配作为对两幅或多幅图像相似性或一致性检测的分析方法，在人脸识别[1]、目标跟踪[2]、视觉导航[3]、图像拼接及检索[4]等领域具有较为广泛的应用。常用的图像匹配方法主要分为基于灰度信息的匹配方法[5-6]和基于特征的匹配方法[7-8]。基于特征的图像匹配算法主要包括尺度不变特征变换（Scale-Invariant Feature Transform， SIFT）算法[9]、加速稳健特征（Speeded Up Robust Features， SURF）算法[10]、快速特 征點提取和描述ORB（Oriented FAST （Features from Accelerated Segment Test） and Rotated BRIEF （Binary Robust Independent Elementary Features））[11]等算法。ORB算法将FAST角点检测和BRIEF特征描述相结合，保证了尺度和旋转的不变性，具有匹配质量高、匹配速度快等优点;但在实际运用中，该算法仍然存在图像特征点匹配精度较低等问题。随着研究的不断推进，ORB算法被不断完善，在构建图像之间的映射关系时，经常与随机抽样一致性（RANdom SAmple Consensus，RANSAC）算法[12-14]相结合。RANSAC算法可有效剔除误匹配，但当样本中数据较多且局内点所占比例较低时，RANSAC算法计算最优模型参数时间将呈指数增长，且经过剔除误匹配后依然会有明显的匹配错误存在。鉴于此，陈树等[15]将提取的彩色图像颜色不变量信息与SURF-ORB算法相结合，通过优化RANSAC算法完成图像的匹配，但该算法针对不同光照强度和光照角度情况下，图像匹配效果有所提升;

秦晓飞等[16]提出通过8点改进法减少RANSAC迭代次数，采用极线约束来剔除误匹配，但采用极线约束可能存在没有可行解的情况。

Bian等[17]提出了一种基于网格运动统计（Grid-based Motion Statistics，GMS）特征的匹配算法，具有计算速度快、存储量高等优点，但也存在着大量的错误匹配点。

基于上述分析，本文提出了一种基于改进的网格运动统计特征RANSAC-GMS的图像匹配算法，着重于进一步提高图像匹配正确率。本文首先介绍了GMS算法和RANSAC算法，在此基础上提出改进的RANSAC算法，根据匹配点间的距离相似对匹配点进行筛选，进一步利用评价函数对数据进行整理，以此增大局内点所占比例、减少迭代次数。实验结果表明，本文所提算法可以有效剔除误匹配点，实现图像匹配正确率的进一步提高，有利于工程推广应用。

1 GMS算法

GMS算法[18-19]是一种根据网格划分特征点来作为邻域支持估计量，将高数量匹配点转换成高质量匹配的快速、高鲁棒性的图像匹配算法。GMS算法利用ORB算法对特征点进行提取和描述，采用基于网格运动统计邻域支持估计量以区分正确匹配点和错误匹配点。图1为正确匹配与错误匹配的特征分布图，左侧为匹配图像Ia、右侧为待匹配图像Ib。两幅图像分别有M、N个特征点，其对应的特征点集合为{M，N}。a、b区域的匹配点集合为x={x1，x2，…，xn}，其中xi={Mi， Ni}表示一对特征点匹配对。正确匹配点附近存在若干对符合匹配关系的特征，而错误匹配的周围符合匹配关系的特征数量较少甚至没有，根据此特性，在a区域有一特征点Mi匹配到b区域中的Ni中，匹配对xi匹配正确，而匹配对xj匹配错误。对图1中的a区域，用si表示xi邻域支持估计量，则有：

si= | xi | -1

（1）

其中：-1表示去除a区域的原始特征点Mi。图1中si=2。

匹配过程中，为了计算区域a中特征点到区域b中匹配正确的概率，用图2表示特征点匹配过程的事件空间，其中图（a）为区域a和区域b匹配正确事件，图（b）为区域a和区域b匹配错误事件。区域a中的一个特征点用fa表示，事件fba表示fa匹配到区域b，反之匹配到区域b之外的事件记为fba 。事件fta表示fa匹配到区域b中特征点匹配正确，反之匹配错误记为事件ffa。事件Tab、Fab分别表示区域a和区域b匹配正确和匹配错误。其中，事件ffa发生时事件fba发生的概率为：

p（fba | ffa）=βn/N;  β∈（0，1）

（2）

其中：n是区域b中特征点个数;N是待匹配图像Ib中特征点总个数;β是权重值。

由特征点fa匹配事件空间的分布，设pt、 pf分别表示在区域a中一个特征点匹配到区域b中正确的概率和错误的概率，令事件fta的概率为p（fta）=t，则pt、pf分别为：

pt= p（fba | Tab）=

p（fba | Tab）+p（fba， fba | Tab）=

p（fta）+p（ffa）p（fba | ffa）=t+（1-t）βn/N

（3）

pf=p（fba | Fab）=p（ffa， fba | Fab）=β（1-t）（n/N）

（4）

根据式（3）、式（4），si邻域支持估计量和xi的二项分布之间的关系如下：

si～ B（n，pt），   xi匹配正确B（n，pf）， xi匹配错误

（5）

为了快速区分正确匹配和错误匹配，把图像划分为G=g×g个网格，图3展示了网格运动划分，这里将邻域支持估计量分配给一个单元网格，而不是计算每一个特征点对应的支持估计量。通过计算周围相邻网格的估计量，来加快区分匹配点。根据式（1）得到匹配网格区域间支持估计量si的表达式为：

si=∑ K k=1  | xakbk |

（6）

其中：K表示与匹配xi一起连续的不相交区域网格数目;xakbk∈x表示在xi预测周围区域对应的匹配子集{ak，bk}。相邻网格区域的邻域支持估计量si的二项分布如下：

si～ B（Kn，pt），   xakbk匹配正确B（Kn，pf）， xakbk匹配错误

（7）

根据以上得si的均值和标准差的分布如下：

mt=Knpt，st= Knt（1-pt） ，   xakbk匹配正确mf=Knpf，sf= Knt（1-pf） ， xakbk匹配错误

（8）

由于运动网格的划分，使得正确匹配与错误匹配的概率相差越来越大，即si的值逐渐增大。根据计算的均值和标准差可得到区域匹配对{ak，bk}的二值化表达式：

cell-pair{i， j}∈ F，  sij≤τ=mf+αsf

T， sij>τ=mf+αsf

（9）

其中：i表示圖像Ia中第i个网格区域;j表示图像Ib中第j个网格区域;{i， j}表示两个匹配的网格区域;α为权重值。在实践中，τ可以近似为：

τ≈αsf≈α n

（10）

将邻域估计量si大于τ的网格区域匹配对保留下来，则保留下的网格中存在大量满足条件的特征点，为样本提供了可靠的特征匹配对。

2 改进RANSAC算法

2.1 RANSAC算法

RANSAC算法[20]是根据一组观测数据集，经过反复迭代的方式计算出数据集的参数模型，去除不符合模型的局外点及噪声，进而得到可信的样本数据的算法。RANSAC算法消除错误匹配的本质是寻找一个最优参数单应矩阵（Homography Matrix），假设A图像中坐标点为（xa，ya），B图像中的点为（xb，yb），则向量表达关系为Bi= H Ai，进行 H 变换的一般式为：

xbyb1  =  h11 h12 h13h21 h22 h23h31 h32 h33  =  xaya1

（11）

对于单应矩阵 H ，通常令h33=1进行归一化处理。此时单应矩阵 H 含有8个未知参数，需要4对匹配点来计算单应矩阵模型参数。虽然RANSAC算法很大程度上能够提取正确的匹配点，但大量的实验表明，直接使用RANSAC算法剔除误匹配点的运行效率较低。RANSAC算法的迭代次数直接体现了RANSAC的运行效率，而模型最小迭代次数k须满足：

1-（1-εq）k=p

（12）

其中：ε表示每次选取一个局内点在样本中所占的概率;q表示计算模型参数所需的最小数据点数;p表示为被测量参数测量值可信程度的物理量。由式（12）可以求出为：

k=lg（1-p）/lg（1-εq）

（13）

由式（13）可知，在置信度p∈[0.95，0.99]情况下，ε减小，则k增大;反之，ε增大，则k减小。因此，为了提高计算最优内点集的效率，缩短算法运行时间，可以通过提高局内点在数据集中所占比例来减少迭代次数。

2.2 改进的RANSAC算法

尽管RANSAC算法具有极大的容错性和较好的鲁棒性，然而，当提取的数据集含有较多错误的匹配点时，算法的运行时间将呈指数增加，加之初始模型参数估计的数据源具有一定的随机性，因此，在剔除误匹配点方面仍然有进一步改进的空间。本文通过计算匹配点对的距离，根据距离相似性特点进行筛选，实现部分局外点的剔除，剩下的匹配点组成新的数据集，此时局内点所占的比例较高，可以计算出最优单应矩阵参数模型;同时，也减少了计算最优模型参数的迭代次数，提高了算法剔除误匹配点效率，减少了运行时间。

为了进一步说明本文方法，采用图4所示的匹配点距离相似筛选示意图来作详细说明。设（Ai，Bi）和（Aj，Bj）是参考图像A和待匹配图像B最邻近匹配对，那么，Ai和Bi的距离l（Ai，Bi）应相似于Aj和Bj的距离l（Aj，Bj）;再由距离一致性原理，该距离应满足l∈[Lmin，λ·Lmax]，其中Lmax为匹配距离的最大值，Lmin为匹配距离的最小值，λ∈[0，1]为比例因子。

要获取更多特征点，可以将λ设定靠近1，该λ可以通过实验确定，一般λ取0.6～0.8较为合适，本文λ取值0.7。利用参考图像A和待匹配图像B中匹配对（Ai，Bi）与最邻近匹配对（Aj，Bj）距离关系相似性来评价距离两点对应关系，提出如下评价函数：

F（i）=∑ c j=1  R（i， j） 1+Y（i， j）

（14）

R（i， j）=exp -  | l（Ai，Bi）-l（Aj，Bj） |  Y（i， j）

（15）

Y（i， j）=[l（Ai，Bi）+l（Aj，Bj）]/2

（16）

其中：c为内点个数;R（i， j）表示（Ai，Bi）与各自对应特征点距离相对差异;Y（i， j）表示（Ai，Bi）与各自相对应特征点的平均距离。根据式（14），若想要得到稳定的特征点，计算该距离与最邻近距离的F（i）应尽可能地小。

改进RANSAC算法步骤如下：

1）求出匹配图像A和待匹配图像B中特征点匹配距离l和最邻近点距离l′，该距离应满足l∈[Lmin，λ·Lmax]。

2）计算评价函数F（i）的所有值并求取平均值，平均值记为F 。

3）对选取的匹配距离l进行F（i）值条件判断，若F（i）小于F ，将匹配点保留下来组成新的样本集C。

4）从C中随机抽取4个匹配对作为内点集Ci，用这4个样本数据拟合出一个模型 H i。

5）利用当前计算的模型去验证样本集C中剩余的内点集，如果某个点对适合当前模型 H i，且误差小于阈值μ，则认为该点为局内点，将其加入内点集Ci。

6）如果内点集Ci中元素个数大于阈值θ，则更新内点集，重新计算当前模型;否则，转到4）。

7）重复以上过程，如果迭代次数大于k，则退出。

2.3 本文算法设计

在本文中将匹配图像和待匹配图像分别划成G=20×20个互不重叠的网格区域[17]，采取K=9邻域网格进行估计，阈值τ是基于α的sij均值和方差之和，取α=6，在进行匹配点距离一致性筛选时，取λ=0.7。总体算法流程如下：

1）对参考图像和待匹配图像进行网格划分，并使用ORB算法对特征点进行提取，分别获取粗匹配特征点集。

2）使用基于网格运动统计邻域支持估计量进行正确匹配点和错误匹配点的区分，组成可信度较高的匹配点集。

3）采用改进的RANSAC算法进行误匹配点的剔除，完成圖像匹配。

具体流程如图5所示。

3 实验结果与分析

本文测试算法实验条件为，笔记本电脑：操作系统为Windows 10（64位），Intel Core i5-4210U CPU @ 2.40GHz，4GB内存，运行环境为Visual Studio 2015和opencv3.4.0，程序采用C+ +编写。为了验证改进的RANSAC-GMS算法在图像模糊、旋转缩放、光照变化等图像变换下具有良好的匹配效果，选取4个近期具有代表性的算法（GMS、ORB、SIFT、文献[21]算法）与本文算法进行测试对比。对比实验采用Oxford标准图集[21]，图6（a）～（g）分别有图像模糊（image blur）、视点变换（viewpoint change）、缩放/尺度（zoom/scale）、光照变化（illumination change）和JPEG压缩（JPEG compression）等7组图像，每组包括6幅不同变换程度的相同场景图像。

[4] 侯一民，隋文秀，孙晓雪. SIFT特征降维方法及其在图像检索中的应用 [J].中国激光， 2015，42（s1）：s108002. （HOU Y M， SUI W X， SUN X X. SIFT feature dimension reduction method and its application in image retrieval [J]. Chinese Journal of Lasers， 2015， 42（s1）：108002.）

[5] 王凯，李志伟，朱成德，等.基于二次引导滤波的局部立体匹配算法[J]. 激光与光电子学进展， 2019，56（8）：081004. （WANG K， LI Z W， ZHU C D， et al. Local stereo matching algorithm based on twice guided filtering [J]. Laser & Optoelectronics Progress， 2019， 56（8）： 081004.）

[6] 吳强，侯树艳，李旭雯.融合图像灰度信息与边缘特征的快速匹配算法[J]. 信号处理， 2013，29（2）：268-273. （WU Q， HOU S Y， LI X W. Fast image matching algorithm based on gray and edge features [J]. Journal of Signal Processing， 2013， 29（2）： 268-273.）

[7] 贾雯晓，张贵仓，汪亮亮，等.基于SIFT和改进的RANSAC图像配准算法[J].计算机工程与应用，2018，54（2）：203-207. （JIA W X， ZHANG G C， WANG L L， et al. Image registration algorithm based on SIFT and improved RANSAC [J]. Computer Engineering and Applications， 2018， 54（2）： 203-207.）

[8] 陈虹，肖越，肖成龙，等.基于SIFT算子融合最大相异系数的自适应图像匹配算法[J].计算机应用，2018，38（5）：1410-1414. （CHEN H， XIAO Y， XIAO C L， et al. Adaptive image matching algorithm based on SIFT operator fused with maximum dissimilarity coefficient [J]. Journal of Computer Applications， 2018， 38（5）： 1410-1414.）

[9] LOWE D G. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision， 2004， 60（2）： 91-110.

[10] BAY H， ESS A， TUYTELAARS T， et al. Speeded-up robust features [J]. Computer Vision & Image Understanding， 2008， 110（3）： 346-359.

[11] BRADSKI G， RUBLEE E， KONOLIGE K， RABAUD V， et al. ORB： an efficient alternative to SIFT or SURF [C] // Proceedings of the 13th IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2011： 2564-2571.

[12] TRAN Q， CHIN T， CARNEIRO G， et al. In defence of RANSAC for outlier rejection in deformable registration [C]// Proceedings of the 2012 European Conference on Computer Vision， LNCS 7575. Berlin： Springer， 2012： 274-287.

[13] 冯文斌，刘宝华.改进的SIFT算法图像匹配研究[J].计算机工程与应用，2018，54（3）：200-205. （FENG W B， LIU B H. Research on image matching based on improved SIFT algorithm [J]. Computer Engineering and Applications， 2018， 54（3）： 200-205.）

[14] 孙雪强，黄旻，张桂峰，等.改进RANSAC算法在多光谱图像匹配中的应用 [J].半导体光电，2018，39（4）：563-568. （SUN X Q， HUANG M， ZHANG G F， et al. Application of improved RANSAC algorithm to multi-spectral image matching [J]. Semiconductor Optoelectronics， 2018， 39（4）： 563-568.）

[15] 陈树，杨天，孙顺远.融合彩色不变量和SURB检测的特征点匹配算法[J]. 激光与光电子学进展，2018，55（5）：138-145. （CHEN S， YANG T， SUN S Y. Feature point matching algorithm for fusion of color invariants and SURB detection [J]. Laser & Optoelectronics Progress， 2018， 55（5）： 138-145.）

[16] 秦晓飞，皮军强，李峰.基于极线约束的ORB特征匹配算法[J].计算机应用研究，2018，35（8）：2865-2868. （QIN X F，PI J Q， LI F.ORB feature matching based on epipolar constraint [J]. Application Research of Computers， 2018， 35（8）： 2865-2868.）

[17] BIAN J， LIN W， MATSUSHITA Y， et al. GMS： Grid-based motion statistics for fast， ultra-robust feature correspondence [C]// Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC：IEEE Computer Society， 2017： 2828-2837.

[18] 陳方杰，韩军，王祖武，等.基于改进GMS和加权投影变换的图像配准算法[J].激光与光电子学进展，2018，55（11）：174-180. （CHEN F J， HAN J， WANG Z W， et al. Image registration algorithm based on improved GMS and weighted projection transformation [J]. Laser & Optoelectronics Progress， 2018， 55（11）：174-180.）

[19] YAN K， HAN M. Aerial image stitching algorithm based on improved GMS [C]// Proceedings of the 2018 Eighth International Conference on Information Science and Technology. Washington， DC： IEEE Computer Society， 2018： 351-357.

[20] 赵明富，陈海军，宋涛，等.改进RANSAC-SIFT算法在图像匹配中的研究[J].激光杂志，2018，39（1）：114-118. （ZHAO M F， CHEN H J， SONG T， et al. Research on image matching based on improved RANSAC-SIFT algorithm [J]. Laesr Journal， 2018， 39（1）： 114-118.）

[21] 李倩，江泽涛.二值化的SIFT特征描述子及图像拼接优化[J].中国图象图形学报，2016，21（12）：1593-1601. （LI Q， JIANG Z T. Binary quantized SIFT feature descriptors for optimized image stitching [J]. Journal of Image and Graphics， 2016， 21（12）： 1593-1601.）

[22] 李为，李为相，张璠，等.基于运动平滑约束项的快速误匹配剔除算法[J].计算机应用，2018，38（9）：2678-2682. （LI W， LI W X， ZHANG F， et al. Rapid mismatching elimination algorithm based on motion smoothing constraints [J]. Journal of Computer Applications， 2018， 38（9）： 2678-2682.）