融合RANSAC 与GMS 图像特征的匹配算法

冯宝凤， 杨剑锋，2， 严 可， 邹 琼， 仝天乐

（1 贵州大学数学与统计学院， 贵阳 550025； 2 贵州理工学院大数据学院， 贵阳 550003；3 深圳市瑞云科技股份有限公司， 广东 深圳 518000； 4 贵州黔驴科技有限公司， 贵阳 550000）

0 引 言

图像匹配是通过计算机和数学理论知识，对给定的图像按照特定目的进行处理［1］，其在物体识别［2］、图像拼接［3］、视觉映射［4］等领域应用广泛。图像匹配大致分为两大类：对区域的匹配算法和对特征的匹配算法［5］。 对区域进行匹配的方法主要是指对图像进行密集匹配，利用整幅图像的像素强度进行图像匹配，建立一个密集像素的对应关系；利用图像特征进行匹配的方法，需要提取两幅图像中的特征点以及图像的局部特征描述符，通过描述符与度量空间相似度的距离判断来建立对应关系，进行图像特征匹配。 其中，图像特征匹配算法具有强鲁棒性、高配准率、计算速度快等优势，因此常被用于图像处理［6］。

基于图像的特征匹配算法发展至今，已经产生了许多经典以及改进算法。 如：Lowe 等［2］提出的SIFT（scale-invariant feature transform）算法，拥有旋转不变性、尺度不变性以及独特性，不会受光照、仿射变换、噪声的影响，广泛应用于各个领域，但其利用128 维数据，高维数据计算时间长，实时性目的较差；Bay 等［7］在SIFT 基础上提出了具有64 特征维数的SURF（Speeded Up Robust Features）算法，SURF降低了数据维度，具有良好的鲁棒性，但存在精度低、实时性差等缺点； Leutenegger 等［8］提出BRISK（Binary Robust Invariant Scalable Keypoints）算法，虽然该算法也拥有旋转不变性、尺度不变性以及鲁棒性，针对较大模糊的图像配准较好，但存在配准率低的问题；2017 年，JW Bian 等［9］提出GMS（Gridbased Motion Statistics）算法，其具有运动特性，超鲁棒性的优点，但其在进行网格划分时，存在误匹配等问题。 针对这些算法，国内外的许多优秀学者也对其计算速度、配准率进行了改进。 对于大部分匹配算法存在误匹配问题，Wu 等［10］提出利用RANSAC算法删除误匹配，但是这个方法存在耗时长等问题。针对SIFT 算法实时性差，存在误匹配问题，许多学者提出了大量优秀的改进方法。 针对RSANSAC［11］删除误匹配存在的不足问题，Muja 等［12］提出FLANN 算法，该算法主要是利用了比率测试，来删除误匹配，提高了计算速度；程明明等［13］进行双边建模，又加入运动的空间信息，对误匹配进行删除；程向红等［14］加入了运动平滑约束，结合RANSAC 的单应矩阵对低匹配区域进行筛选，提高了召回率与RANSAC 的计算时间；陈洁等［15］将极限约束引入特征匹配中，但是该算法加大了匹配时间。 丁辉等［16］为解决传统匹配算法配准时间长、配准率低问题，提出了一种将GMS、矢量系数相似度（VCS） 与RANSAC 相结合的GC-RANSAC 图像配准算法，提高了匹配精度、缩短了匹配时间。

本文在GMS 算法的启发下，由于GMS 匹配算法在利用运动平滑性约束进行匹配时仍会存在一些误匹配问题，影响其匹配率与配准率。 因此为提高其算法的性能，本文提出了RGMS 算法，先用RANSAC 对两幅图像的特征进行筛选，再利用GMS进行图像的特征匹配，使GMS 算法提高其配准率的情况下，不影响匹配的实时性，并对RGMS 算法进行了实证对比实验分析研究。

1 ORB 特征点检测算法

ORB 算法是由Ethan Rublee 等人［17］提出的一种基于FAST［18］和BRIEF［19］非常快速的二进制描述符。 其主要贡献在于：在FAST 中增加了一个快速和准确的方向计算，有效地计算了定向BRIEF 特征，并分析了定向BRIEF 特征的方差和相关性，减少了旋转BRIEF 特征的方差损失。

1.1 OFAST 算法

ORB 算法首先提出基于FAST 的OFAST（FAST Keypoint Orientation）算法。 FAST 算法是一种二维图像的特征点检测算法。 其将图片转换为灰度图，快速检测其特征点，具体步骤如下：

（1）设中心点p为目标像素，半径为r， 得到M个领域像素点；

（2）分别对像素点与p点灰度值之差的绝对值进行计算；

（3）利用设定的阈值与步骤（2）得到的值进行对比，如果像素点与目标像素点p的灰度值之差的绝对值大于设定的阈值，则认为该点为FAST 点，否则该点不为FAST 点。

OFAST 使用FAST-9 算法进行关键点检测定位，该算法利用一个“强度质心点”来计算角点的方向。 强度质心点［20］的具体定义为：假设一个角度的强度从其中心偏移，则可以使用向量来计算方向。计算流程为：

（1）Rosin 定义图像矩为

（2）利用这些图像矩找到质心点

（3）计算图像的中心点到强度质心点的向量由此得到角点的角度：

其中，atan2 是arctan 的四边形感知。

为提高度量的旋转不变性，x和y在以r为半径的圆形区域内。

1.2 RBRIEF 算法

RBRIEF（Rotation-Aware Brief）算法是通过对关键点的区域进行二进制计算，得到二进制字符串描述符。 考虑图像块p，定义τ为一个二进制计算：

其中，p（x） 是p在某点x的强度。

由此可以得到n个二进制操作的组合向量：

对不同类型的测试分布，该算法考虑了高斯分布，选择描述子的长度n＝256，每一个点是来自31×31 像素块的5×5 的子窗口。 为了使BRIEF 不受图像旋转的影响，可根据关键点的方向来引导BRIEF。

对于任何长度为n的描述子，需要n个匹配对，在位置（xi，yi），定义一个2×n的矩阵：

在得到关键点的方向θ和其旋转矩阵Rθ的情况下，构造S的旋转矩阵Sθ：

所以，得到旋转的BRIEF 运算符变为

但是，旋转的BRIEF 方差会有损失。 为了得到一个良好的二进制特征，提高描述子各个位置的方差，提出了如下RBRIEF 算法，RBRIEF 在方差和相关性方面对旋转BRIEF 进行了改进。

（1）针对所有训练集的图像块进行计算，得到矩阵；

（2）计算矩阵每一列的均值，按从小到大进行排序，得到向量T；

（3）贪心搜索：

①从T中取出一个对比对，计算该对比对与R各个对比对的相关联程度。 若相关度大于阈值，则舍弃取出的对比对，否则将这个对比对加入R中。

②重复进行步骤①的操作，其结果是让256 个对比对存在R中。 如果少于256 个对比对，则提高设定的域值重复操作。

③最终得到固定的256 个对比对。

2 改进的RGMS 特征匹配算法

利用ORB进行图像特征点提取后，两幅图片的特征点存在明显差异，两幅图片差异越大，特征点越不一致。 因此，本文提出RGMS算法，先用RANSAC算法对两幅图像的特征进行筛选，再结合GMS算法进行特征点匹配，提高图像的特征点匹配率。

2.1 RANSAC 特征筛选

RANSAC（Random Sample Consensus）算法是由MA Fischler等［11］提出的一种应用于图像分析和自动制图的模型拟合算法，该算法能够解释含有相当大比例的严重错误数据，非常适用于图像分析的应用。RANSAC算法主要是通过一组含有“异常值”的数据，得到一个正确的数学模型。 图像中的＂异常值＂，通常是指提取数据中含有噪声的干扰。RANSAC并不是使用的数据越多越好，而是利用尽可能少的数据集，通过估计模型不断扩展数据集，直到得到合适的模型。RANSAC的具体计算流程如下：

（1）设定模型M1：该模型需要大于等于n个数据点来获得自由参数，一组数据p（其中的数据点数量应该大于n），通过从p中随机选择n个数据点的一个子集S1 来实例化模型；

（2）通过M1 确定p中的子集S1*，S1*在M1的某个误差容限之内，称为S1 的共识集；

（3）如果S1*大于阈值t，则利用S1*来计算一个新的模型M1*；如果S1*小于阈值t， 则随机再选择一个新的子集，重复上述步骤。 设定迭代次数k，经过k次迭代后，找到最大的共识集拟合模型，或者以失败告终。

RANSAC算法包含3 个未指定参数。

2.1.1 确定误差容限

误差容限定义为超过平均误差的一至两个标准差，标准差可以通过实验得到。 如计算干扰数据和测量造成的隐含误差，可以得到样本偏差。 数据的样本偏差是数据的误差容限的一个函数，误差容限对每个模型都是不同的。 与总误差的大小相比，误差容限的变化相对较小。

2.1.2 确定最大迭代次数

得到最终模型需要设定所需的预期实验次数k，实验次数越多，所需的时间也就越久。 设w是任何选定的数据点在模型的误差容限内的概率。则有：

其中，由k得到的期望值为

因为几何数列之和具有如下性质：

则可利用该性质对a进行微分，得到：

因此，可以得到：

E（k） 一些数值列表对应的n和w的值见表1。再计算k的标准差SD（k）：

表1 E（k）的一些数值的列表对应的n 和w 的值Tab. 1 List of some values of E（k） corresponding to the values of n and w

其中，

利用几何数列的特性和两个不同的指数，得到：

因此，最终可以得到：

由此可看出，SD（k） 约等于E（k）。

如果想以概率z确保随机选择中至少有一个是由n个数据点组成的无错误组合，则需要k次选择（每次至少选择n个数据点），其中：

可以得到，当wn≪1 时，k≈log（1-z）E（k）。因此，想要保证有一个高的概率z， 本文选择当z＝0.9，wn≪1 时，得到k≈2.3E（k）。 为了达到筛选的目的，选择对模型进行500 次迭代，即K＝500。

2.1.3 阈值t的选择

阈值t是确定p的所有子集被找到的下限，其必须有一个足够大的共识集。 因此，阈值t的值不能太小。 阈值的选择必须满足要有足够数量的数据点，并对改进的模型可以进行正确的评估。 为了不让错误的模型和共识集兼容，令y是随机给定的数据点在不正确模型误差容限内的概率，同时要求足够小。 目前还没有能够完全精确得到y的方法，但可由假设其小于w且y ＜0.5，则t-n的值等于5 时，就可以达到高于95%概率，使其与错误的模型不会存在兼容性。

2.2 GMS 特征匹配

GMS（Grid-based Motion Statistics）算法［9］是一种快速匹配特征检测点的算法，通过该算法对筛选出的特征点进行匹配，得到RGMS 改进的匹配结果。 GMS 算法假设：运动平滑可以使得在一个领域周围的正确匹配，可在另一幅三维图像中相同的位置检测到。 该假设意味着在正确匹配的邻近点，对于一个相同的位置，两幅图像中有着更多相似的特征。

GMS 算法流程如下：

假设图像Ia和Ib对应的区域为{a，b}，Ia有N个特征点，Ib有M个特 征 点。X＝{x1，x2，x3，…，xi，…，xN} 是Ia到Ib中所有最近邻特征匹配的集合。Xi⊆X是区域{a，b} 中xi匹配的子集。Si是邻域支持的衡量标准：

xi邻域内的匹配数可以通过二项分布来计算，特征点的匹配是相互独立的，可以得到：

式中：pt＝t＋（1-t）m／M为真匹配的概率，pf＝β（1-t）m／M是假匹配的概率，t为区域a支持域中一个特征正确匹配的概率，m为b邻域区域中的特征点数，M为Ib中的所有特征点数，β为弥补假设所增加的参数。

为了增大描述差异，对Si进行更广义的假设：

其中，K表示两个不相交区域内匹配i预测一起移动的数量，akbk

{} 表示预测的区域对。

同时也可以得到Si的二项分布：

其中，n表示每个支持区域中的特征数量平均值，K表示每个网格划分的区域。

由于GMS 算法的性能和网格的大小相关，因此网格的划分非常重要。 网格单元格越多，匹配定位效果越好，但也会影响计算时间。 实验结果证明，G＝20× 20 的网格有10 000 个特征，得到n的平均值为25，如果需要更多的特征就需要更精细的单元格。 为了达到更好的效果，本文采用G＝20× 20 网格进行划分。 对于阈值Sij的设定，会把单元对分成真集、假集{T，F} 两个集合。 为了能够拒绝大量的错误单元对，阈值可以近似为，由此可以得到一个单一的参数阈值函数：

其中，ni是单个网格单元格中的特征数量的平均值，将每个网格划分为9 个单元格，根据实验可得α＝6，GMS 算法是在BF 算法的启发下得到的，BF算法可以得到大量的匹配对，但是难以可靠的分离正确和错误匹配。 GMS 算法是将运动平滑封装在一个区域内，可以通过计算一个支持区域内的匹配数量，来区分一个匹配是否正确。

3 实验结果与分析

3.1 实验平台

本次实验使用的CPU 为Intel（R） Core（TM） i5-10300H，频率为2.50 GHz，操作系统为Windows 10，实验测试的图片来自TUM 数据集。 对于TUM 数据集，选取两类图片进行实验。 其中，实验1 为纹理清晰丰富的家庭办公室长桌面图片集，实验2 为表面光滑纹理较少的柜子图片集，分别选取200 张图片，100 组数据进行实验分析。 实验1、实验2 的图片样式如图1 所示。

图1 测试图片Fig. 1 Test pictures of experiments 1 and 2

3.2 实验结果分析

经典的特征点匹配方法种类有暴力匹配算法、SIFT 算法、FLANN 算法等，但是这些算法都存在匹配率低的问题，特别是在图片纹理低的情况下，匹配率不高。 本文在GMS 的算法下融合RANSAC 算法，在纹理丰富和纹理低的情况下都能很好的进行特征点匹配，匹配率均高于其他算法。 通过暴力匹配、FLANN、GMS 以及本文算法，分别对两类图片集进行特征点匹配实验。

实验1 的RGMS 算法匹配效果如图2 所示，4种算法的匹配率如图3 所示，4 种算法对图片集的特征点匹配效果对比详见表2。 由表2 可知，传统的BF＋KNN 算法的匹配率为21.02%，FlANN 算法的匹配率为19.59%，GMS 算法的匹配率为27.52%，RGMS 算法的匹配率为29.65%；RGMS 算法比GMS算法提高了2.13%，比FlANN 算法提高了10.06%，比BF 算法提高了8.63%；虽然匹配时间略高于其它算法，但总体上并不影响该算法的实时性。

图2 RGMS 算法对实验1 图片匹配效果图Fig. 2 RGMS algorithm matching effect for experiment 1 images

图3 实验1 中4 种算法匹配率的结果图Fig. 3 Graph of the results of the matching rate of the four algorithms in Experiment 1

表2 基于ORB 算法的4 种算法对实验1 图片集的特征点匹配效果对比Tab. 2 Comparison of four algorithms based on ORB algorithm for matching feature points on the experiment 1 image set

表3 是对实验2 纹理少的图片集进行特征点提取与特征点匹配，RGMS 算法匹配效果如图4 所示，4 种算法的匹配率效果如图5 所示。 由此可见，对于表面纹理少的图片，传统的BF＋KNN 算法的匹配率为9.52%，FlANN 的匹配率为6.78%，GMS 的匹配率为15.34%，RGMS 算法的匹配率为17.54%；RGMS 算法比GMS 算法提高了2.2%，比FlANN 算法提高了10.76%，比BF 算法提高了8.02%；匹配时间较其它算法略高，但比GMS 算法用时少0.01，且总体上不影响该算法的实时性，说明该算法在图片纹理较少的情景更具优势。

图4 RGMS 算法对实验2 图片匹配效果图Fig. 4 RGMS algorithm matching effect for experiment 2 images

图5 实验2 中4 种算法匹配率的结果图Fig. 5 Graph of the results of the matching rate of the four algorithms in Experiment 2

表3 基于ORB 算法的4 种算法对实验2 图片集的特征点匹配效果对比Tab. 3 Comparison of the four algorithms based on the ORB algorithm for matching feature points on the Experiment 2 image set

4 结束语

本文提出的RGMS 算法是为解决传统的算法存在配准率低的问题。 该算法主要是将RANSAC 与GMS 算法相结合，采用RANSAC 算法筛选特征点，得到更适合匹配的特征；再通过GMS 对特征点进行平滑约束以及划分网格计算，优化了匹配结果。 同时，将传统算法与RGMS 算法进行对比实验得到：

（1）RGMS 算法的匹配率在不影响计算速度的情况下高于其他匹配方法；

（2）在对纹理少的图片集匹配时，RGMS 算法匹配时间少于GMS 算法，缩短了匹配时间，更具有匹配优势，可以进行高质量、实时的特征匹配。

关于如何提高本文算法的匹配时间，如何获得更高的匹配率和准确率，并将其运用于图像拼接、三维重建中，将是本文的后续研究内容。