基于随机抽样一致性的误匹配剔除方法研究

计算机仿真

2019年10月

文章编号：1006 -9348(2019) 10 -0233 -05

基于随机抽样一致性的误匹配剔除方法研究

李文彬，刘璇，张建畅，张建华

(河北工业大学机械工程学院，天津300130)

摘要:针对图像特征在匹配过程中产生误匹配、漏匹配的问题，对SURF算法与误匹配剔除算法进行了相关的研究。提出最 小距离与随机抽样一致性（RANSAC)两种方法相融合的误匹配消除算法。算法首先通过设置适当阈值的最小距离法对特 征之间的匹配进行粗略的淘汰，然后利用优化了的RANSAC对其进行精确的剔除。最后，从数据集中的随机选取两帧图像 对算法进行了实验验证,表明提出的算法提高了误匹配剔除的效率的同时，保持了正确匹配的数量。关键词：特征匹配;加速鲁棒特征;误匹配;随机抽样一致性 中图分类号:TP391.41

文献标识码:B

Mismatching Culling Algorithm Based on Minimum Distance and RANSAC Fusion

LI Wen - bin, LIU Xuan, ZHANG Jian - chang, ZHANG Jian ~ hua

(School of Mechanical Engineering,Hebei University of Technology,Tianjin 300130,China)

ABSTRACT ： Aiming at the problem of mismatching and missing matching in the matching process of image features, SURF algorithm and mismatch elimination algorithm were studied. On this basis, a mismatch elimination algorithm based on the two methods of minimum distance and random sampling consistency( RANSAC) was proposed. First, the algorithm was used to eliminate the matching between features by setting the minimum distance method of the ap­propriate threshold, and then the optimized RANSAC was used to eliminate it accurately. Finally, the algorithm was tested through random selection of two frame images from the data set. It shows that the algorithm proposed in this pa­per improves the efficiency of mismatch rejection and keeps the number of correct matching.KEYWORDS ： Feature matching ； SURF ； Mis - matching ； Random sample consensus( RANSAC)

Moisan等人w提出了优化的RANSAC算法,该算法有效地

i

引言

降低了计算剔除模型时采集数据的随机性且能够提高匹配 图像匹配技术在日常生活的相关领域中已经得到了广

关系的质量。Aguilar等人[7]通过在匹配关系中计算出最近 泛应用，如图像融合、三维重建、虚拟现实、目标识别、遥感图 邻图的邻接矩阵不断的迭代来消除误匹配，计算较复杂。刘 像技术等[1]。在图像匹配的过程中，由于现实环境中总存在 川熙等人[8]提出自适应阈值的方法从特征匹配的过程选择 一些相似的特征，进行特征匹配时会产生不同数量的误匹 最优阈值来降低误匹配，该方法从匹配产生的源头来降低误 配。而快速准确地获得高精度的匹配是进行位姿估计、图像 匹配。程德志等人[9]利用准欧式距离来提高图像匹配效率 配准、图像检索等应用的前提和关键。因此,在图像之间的 和准确率。童莹等人[1(>1提出渐进抽样一致性（PROSAC)算 特征点进行匹配后，如何减少误匹配的数量和提髙剔除误匹 法,对图像之间的匹配点对的质量进行的排序，有效地节省 配算法的运行速度在实际应用中至关重要。

了计算量。但是这些方法在剔除误匹配的过程中，容易减少 在剔除误匹配的过程中的相关技术主要有极线约束[2]、 正确匹配的数量并且较髙的计算成本降低了在应用中的实 单应性约束[3]等。其中，在极线约束技术中的随机抽样一致 时性。

性算法[4]在剔除误匹配中得到了广泛的应用[5]。近年来，

本文针对SURF算法对相邻两帧图像进行的特征提取 和匹配产生的误匹配问题提出采用融合剔除算法对其进行 基金项目：河北省杰出青年科学基金（F2017202062) 收稿日期:2018 - 07 - 24修回日期:20丨8-07-25

淘汰。该算法主要采用较大阈值的最小距离法对初始匹配 集进行初步的筛选;然后,采用改进了的RANSAC算法对匹

—

233 —

配集中的错误匹配进行进一步的淘汰。其中，对初步剔除后 的匹配集中正确的匹配数的比例得到很大的提升，RANSAC 算法在寻找最优模型时随机抽取正确的匹配关系的概率得 到了提高,因此可以减少了迭代的次数，并且在寻找模型时 对其进行了验证，减少了错误模型对内点的计算，提高了算 法的运行速度和匹配的数量和质量。

采样的过程，其图片一直保持原始尺寸不变，而不同层的图 片是通过不同大小的高斯模板处理得到的，并且在同一层中 的几张图片进行模糊处理时也需要尺度不同的模板函数。 该算法因为尺度空间不同层的图像没有相互依赖的降采样 的过程，因此允许对不同层的图像同时处理，提高了特征检 测和提取的速度。SIFT算法中的图像金字塔是通过对图像 连续降采样建立的结构,并且为了消除图像中的噪音，不断 的使用高斯模板对其进行平滑处理。而SURF算法改变的 是高斯滤波器的大小，保持的是原始图片的尺寸不发生改 变。SIFT和SURF的图像金字塔结构如图2所示。

2 SURF特征提取与匹配 2.1特征点提取

SURF算法[u]是通过黑塞矩阵的判别式来计弇特征值，

其中黑塞尔矩阵由函数的二阶偏导组成，如式（1)所示。如 果要计算式⑴中的人,、i„.三个元素，则需要使用特定 核函数间的卷积计算二阶偏导数并使用高斯函数作为滤波器。

La{x,a) ,(*,〇•)

/,„(*,〇■)-. Lyy{x,a)i

…

/ 、'、丨 (1)

图2 SIFT和SURF的图像金字塔

为了降低高斯卷积运算过程中成本，Lowe等人112]提出 了采用高斯差分算法来代替拉普拉斯算法。而Bay等人 提出的采用如图1所示的框式滤波器来对图像进行卷积计 算，计算之后分别用4„和化,代替i在三个方向 的近似值。因此,//矩阵的行列式的判别式的近似计算可以 表示为式(2)

det(HapprJ = DaDn - (〇,0„)2

(2)

为了保证图像中的特征具有旋转不变性的特性，在

SURF中以关键点为中心,半径为6s(其中S为特征点所在图

像金字塔中的尺度值）的特定区域内，统计60度扇形处于每 一个角度时,该扇形中的图像点在x和y方向的Haar小波响 应值的总和，并给这些响应值设置高斯权重系数，根据响应 与特征点的距离来确定其贡献的大小;然后以60度扇形区 域内的响应矢量相加以形成新的矢量,以递增的形式遍历整 个圆形区域，通过比较矢量的长度来确定特征点主方向。这 样,就可以确定不同视角的图像中每一个特征点在环境中的 主方向。

在确定特征点的主方向后,就可以根据局部区域进行特 征描述子的计算。在SURF中，首先以特征点为中心取一个 20sx2〇s的方框。该框的方向作为检测出的特征的主方向， 方框的区域分成4 x4个矩形区域，在每一个子矩形区域中

其中，代表了在点;c附近区域的框式滤波响应值

的近似结果，该结果可作为判断该点是否被选为特征点的理 论依据。0是一个协调系数，通常在图像处理的实际应用中 取〇. 9比较合理。

(a)x方向 （b)少方向 （c>Ay方向

统计25个像素在dx、dy方向的Haai•小波响应的分量。在构 建特征向量之前,需要用高斯模板函数对每一个矩形区域中 的rfe、办方向进行加权。然后，在每个矩形区域中对办、 1<£(1、办、丨办I求和，从而得到F= ( 5：厶，5：丨办丨，5：办，E丨办

I)的4维向量。最后，把每个矩形区域的4维向量按照一定

图1 9x9框式滤波器模板

2.2 SURF尺度空间与特征点描述

在模式识别领域中，图像的尺度空间是对一幅图像在不 同的解析度下，对不同层的图像函数与高斯函数进行反复的 卷积计算的表示,这种处理的方法被象征性的称为图像金字 塔。在SIFT特征检测算法中，构建的多尺度空间是多层的， 并且每个层中有几张尺度不同的图片，不同层的图像都是经 过降采样得到的,然后对其采用尺寸相同但尺度不同的高斯 内核函数在不同的方向上进行卷积计算形成尺度空间函数。 这样使每一组图像都需要依赖上一组图像，因此，在不断进 行降采样的时候需要比较大的计算量,这样在特征检测中需 要花费更长的时间。而SURF算法中的图像金字塔没有降 —234 —

的规则连接起来就能得到一个特征点的维特征向量，如 图3所示。

2.3特征点匹配

在得到图像特征点的向量后，通常采用特征向量之间的 相似性作为不同视角下图像特征之间匹配是否成功的判断 依据。SURF算法则是通过欧氏距离的大小作为判断特征向 量之间相似度的衡量标准，其距离越小则表示对应的特征点 之间的相似度越高。

相邻两帧图像的特征点的集合分别记为％和F

X = {%. | i = 1,2,••• y -

I i = 1,2,•••

因此两个特征点&和的欧氏距离可由（3)计算为

^

(3)

其中，化A■分别为特征点七乂的特征向量。

匹配时，计算图像中的特征点&对应的特征向量仏;与 另一幅图像中的所有向量之间的欧氏距离，选取距离最小且 满足一定阈值的对应关系作为两点的匹配。

3误匹配剔除算法

图像匹配过程中采集的图像受场景复杂度和光照等因

素的影响,并且特征点在检测和描述过程中都会受外界因素 的影响存在一定的误差。因此，即使在不同视角上的同一区 域的两帧图像之间在进行特征匹配时也会产生一定数量的 误匹配。本研究在欧氏距离进行匹配的前提下，针对最小距 离阈值法和RANSAC算法在剔除误匹配过程中存在的问题， 提出了两者相融合的误匹配剔除算法。该算法主要首先对 初始匹配集中的误匹配进行粗略的剔除，然后进一步对误匹 配进行精确的剔除。3.1最小距离阈值法

最小距离阈值法通过计算图像之间的所有匹配对之间 的距离，当匹配对满足式(4),则该匹配为正确的匹配；否则 剔除该匹配。该方法主要是通过设定不同的阈值来达到剔 除误匹配的不同效果。该算法具有原理简单，运行速度快的 优点,但当阈值设置不当的情况下，容易产生大量正确的匹 配关系被淘汰的结果且剔除后匹配数量可能不足以满足应 用的后果。

A < 也

(4)

式中，—第i个匹配对中特征向量的距离；

初始匹配集中匹配对的最小距离；设定的阈值。

3.2 RANSAC 算法

在图像之间的特征点的对应关系已知的情况下,可以计 算出图像之间的相对变换关系，即u’ =//u，如式（5)。相对 变换矩阵//有8个自由度可以通过4对相对应的特征点对 其进行计算求解

< h、

h-2 ^fx\\=

h4 h5 h6y(5)

VI )、h7 h& h9 J其中—第A'-l帧图像上的特征点；第K帧

图像上与(》,7)相对应的特征点。

利用特征点之间的正确对应关系得到图像之间变化的 运动模型,通过判断匹配关系是否满足u’

来进行图像

之间的误匹配淘汰。通过/fe计算出第K-1帧图像的特征 点转换到在第贞图像上的位置，并计算在第K帧图像中与 之对应特征点的误差，通过判断该误差是否小于设定的阈值 来进行误匹配的消除。

RANSAC算法是对带有噪声的数据进行处理的算法，通

过不断的迭代来估计出最优数据模型的参数。该算法能够 有效的从带有噪声的数据中找出被模型描述的内点数据和 偏离模型正常范围的外点数据。这里的外点即为误匹配数 据，内点数据为正确的匹配，所以应通过不断的迭代得到最 优模型以得到更多的内点。RANSAC在剔除误匹配中的步 骤如下：

步骤1:通过数据集中的第K - 1帧与第K帧图像中的 特征向量之间的相似性获得图像之间特征点的对应关系，即 初始匹配集数据0;

步骤2:随机从初始匹配集0中选取4对匹配点的数据， 利用选取的数据计算初始匹配集〇中的模型，即为相对变换 的矩阵H;

步骤3:通过计算得出的剔除误匹配模型中的相对变换 矩阵H来判断初始匹配集中那些匹配符合该模型，即为内 点，并统计该模型中内点的数量；

步骤4:设定迭代次数n,对步骤2和步骤3进行迭代， 将所得内点数最多的迭代结果作为最终剔除误匹配之后的 正确匹配结果。

3.3融合误匹配剔除算法

考虑到在估计机器人运动过程中需要采集图像的帧数、 特征的数量和特征的对应关系，有必要考虑实时性和匹配的 准确性的问题。

在最小距离阈值法进行误匹配的剔除过程存在的主要 缺陷是:当选择比较小的阈值时，剔除误匹配后的匹配数量 会急剧地减少，并且其中可能还会存在误匹配。对于

RANSAC算法的实现过程中，该算法每次的循环都需要为计

算误匹配剔除模型随机选取4对匹配点，并且需要判断匹配 集中的每一对特征点是否满足该模型，这样反复的判断过程 会耗费很多的时间和内存。这里针对最小距离阈值法和

RANSAC算法存在的问题进行改进。对误匹配剔除这个阶

段主要分为两个步骤:首先用设置较大阈值的最小距离法对 初始匹配集进行粗略的筛选；然后，采用改进了的RANSAC 算法对匹配集中的错误匹配进行进一步的淘汰，即在

RANSAC算法随机抽取样本进行计算最优模型时，可以减少

迭代次数同时对样本模型的正确性进行验证，减少用错误的 模型对匹配关系进行内点计算。

对于融合后的提出误匹配的算法步骤如图4所示。首 先采用阈值为4的最小距离法对初始匹配集0进行粗略的

—

235 —

误匹配剔除得到匹配集0,,然后利用改进的RANSAC算法 从初步淘汰过的匹配集〇,中随机选取5对匹配，其中4对 用于计算匹配点相对应的模型中的相对变换矩阵H,剩余1 对匹配关系用来验证模型中的矩阵H的正确性。当矩阵H 不满足匹配关系时,就淘汰该模型，减少匹配集〇,中其它匹

配对的在其中的内点判断。再者，匹配集〇,是经过剔除误 匹配得到的，其中相对来说有比较少的误匹配，因此可以减 少对RANSAC算法步骤四中的迭代次数，在这里选取的次数 为原来的1/3，即s = n/3。

图4融合剔除算法步骤

4实验及分析

实验平台采用Windows7操作系统、Intel(R)Core(TM)i5

-2450M CPU @ 2. 50GHz、4GB 内存，编程环境是 Visual Stu-

di〇2013,并且加人了 OpenCV2.4. 10的开源库。为了更好对

本文提出的融合剔除误匹配算法的验证，采用慕尼黑大学用 摄像机采集的图像序列frl/r〇〇m数据集[14]，其中采集图像 的帧率为30fpS,像素大小为0 X 480。这里采用图像集中 的第K - 1帧和第K帧图像进行误匹配剔除实验，分别如图 5(a)、（b)所示。

图6

初始匹配结果

值设置为2时，匹配对数为47,运行时间为15.3#。最小距 离算法可以有效地降低匹配中误匹配的数量，但匹配的总数 量也会急剧下降。图8为采用RANSAC算法是通过寻找最 优模型进行剔除误匹配后的匹配对数为126,有效地保证了 剔除之后匹配的数量，但在剔除误匹配的过程中花费的时间 为 . 56ms。

(a)第K-1帧图像 （b)第K帧图像

图5相邻的两帧图像

SURF特征通过特征向量的相似性进行匹配的初始结果

如图6所示。其中不同颜色的圆点代表图像之间进行特征 匹配的特征点，图像之间的直线表示的是匹配后的特征的对 应关系；由于图像的采集是经过旋转之间图中平行的线代表 正确的匹配，交叉的线代表错误的匹配。图6的初始匹配结 果表明图像之间的特征点会因各种原因产生错误的匹配。

采用最小距离阈值法和随机采样一致法进行误匹配的 结果分别如图7和图8所示。从图6与图7可以看出最小距 离法可以有效的减少无匹配的对数。当阈值设置为4时，匹 配对数从初始的795降到403,但仍然存在大量的误匹配；阈

—

236 —

(b)阈值 ci =2

图7最小距离法剔除误匹配

图8 RANSAC剔除误匹配

本文提出融合的剔除算法采用阈值为4的最小距离与 改进的RANSAC对初始匹配中的误匹配进行循序渐进的两 次剔除，效果如图9所示。该算法剔除后的匹配对的数量为 119,运行的时间为70. 58ms。

图9

本文算法剔除误匹配

本文主要对最小距离法、RANSAC算法和本文的融合剔 除算法在运行时间、正确匹配对数进行了实验对比，如表1 所示。实验结果说明提出的算法在运算速度比RANSAC算 法快，且正确的匹配对数与之相当；与最小距离法相比有更 多的正确的匹配对数。

表1

实验结果剔除算法运行时间正确匹配对数

最小距离法

15. 3us47RANSAC

. 56ms126本文算法

70. 58ms

119

5结束语

本文通过SURF算法分析了最小阈值法在误匹配剔除

结果中存在正确匹配数量少且还存在少量错误的匹配，同时 分析了 RANSAC算法在剔除误匹配过程中迭代次数与模型 的正确性对运算速度的影响。因此，提出最小距离与

RANSAC算法两者相融合的误匹配剔除方法来解决误匹配

的效率与正确匹配数量的问题。实验表明，提出的融合剔除 误匹配算法与RANSAC算法相比有较快的运算效率,且剔除 后的正确匹配的数量多于最小距离阈值法，即该算法在剔除 速度和正确匹配数量上进行了折中，能有效地排除误匹配在 应用中造成的影响。但提出的融合剔除算法过程中的阈值 设置并没有自适应性的特性，这将是以后研究工作中的 重点。

参考文献：

[1] 赵璐璐，等.基于SURF和快速近似最近邻搜索的图像匹配算

法[J].计算机应用研究，2013,30(3) :92丨-923.

[2] 陈洁，等.引人极线约束的SURF特征匹配算法[J].中国图象

图形学报，2016,21(8): 1048-1056.

[3] 齐乃新，等.一种对错误匹配点鲁棒的多单应矩阵估计方法

[J].机器人，2017,39(5): 608 -619.

[4] 常青，张斌，邵金玲.基于SIFT和RANSAC的特征图像匹配方

法[J].华东理工大学学报，2012,38(6) :747 -751.

[5] 雷玉珍，等.基于随机抽样一致算法的误匹配标志点校正方法

[J].光学学报，2013,33(3) :205 -212.[6]

L Moisan, P Moulon, P Monasse. Automatic Homographic Regis­tration of a Pair of Images, with A Contrario Elimination of Outliers [J]. Image Processing on Line, 2012 -2：329 -352.[7]

W Aguilar, et al. A robust Graph Transformation Matching for non -rigid registration [ J ]. Image & Vision Computing, 2009,27 (7)：7 -910.

[8] 刘川熙，等•基于RANSAC的SIFT匹配阈值自适应估计[J].

计算机科学，2017，44(si): 157 - 160.

[9] 程德志，李言俊，余瑞星.基于改进SIFT算法的图像匹配方法

[J]•计算机仿真，2011,28(7) :285-2.

[10] 童莹，张宴.双重检测策略耦合PR0SAC技术的图像匹配算

法[J].计算机工程与设计，2017,(11) :3137 -3142.[11]

H Bay, et al. Speeded-Up Robust Features[J]. Computer Vi­sion & Image Understanding, 2008,110(3) ：404 -417.[12 ] D G Lowe. Object Recognition from Local Scale - Invariant Fea­tures [ C ]. IEEE International Conference on Computer Vision. IEEE, 2002：1150.

[13] R Kalia, et al. An analysis of the effect of different image prepro­cessing techniques on the performance of SURF ： Speeded Up Ro­bust Features[ C]. Frontiers of Computer Vision. IEEE, 2011 ： 1

-

6.

[14] Computer Vision Group - Datasets - RGB - D SLAM Dataset and Benchmark[ DB] . https： vision, in. turn, de/data/datasets/rgbd

-dataset.

[作者简介]

李文彬（1991 -),男（汉族），河南许昌人，硕士研

究生，主要研究领域为视觉SLAM。

刘璇（1980 -),女（汉族），河北秦皇岛人，讲师，

主要研究领域为智能机器人技术。

张建畅（19 -),男（汉族），河北深州人，教授，博

士研究生导师,主要研究领域为智能机器人技术。

张建华（1979 -)，男（汉族），河北邯郸人，教授，硕士研究生导师，主要研究领域为智能机器人技术、视觉SLAM。

—237 —