1 引言

图像匹配是指通过匹配算法寻找同一场景下多幅图像的重叠部分,然后经过变换、融合,组成一幅场景图像。图像匹配技术在视觉同时定位与地图构建(SLAM)^[1]、目标识别^[2]、目标跟踪、三维重建^[3]以及视频监控等领域都得到了广泛应用。现有的图像匹配方法主要分为三类:基于灰度信息的匹配方法、基于变换域的匹配方法和基于特征的匹配方法^[4]。其中基于特征的匹配方法信息量大、抗干扰能力强,一直是该领域的研究热点。Bay等^[5]提出的加速稳健特征(SURF)算法主要利用Hessian矩阵确定候选关键点,并计算其位置、方向和大小,该算法提高了匹配效率,但降低了精确度。Sergieh等^[6]提出了一种机器学习的方法,使用二进制分类器识别对匹配过程有用的关键点,提高了算法的匹配效率。兰红等^[7]提出了一种基于聚类和马氏距离的多角度SURF算法,利用聚类算法剔除原有算法提取的特征点噪声;马氏距离具有仿射不变性等特点,且考虑了整体相关性,有效提高了图像匹配的效率,但正确率较低。由于采用了快速近似最近邻(FLANN)算法^[4]进行特征点匹配会产生许多误匹配,因此需要利用随机采样一致性(RANSAC)算法^[8]剔除误匹配,以增加图像匹配的精度。

RANSAC算法是一种鲁棒性强,且适用于大比例外点的参数估计算法。外点比例越大,迭代次数越多,对算法的匹配精度和效率影响越严重。为了提高RANSAC算法的匹配效率和精度,研究人员提出了一系列改进算法。Xu等^[9]根据统计学思想选择输入数据的随机子集,然后从每个子集中选定样本点拟合最佳模型,减少了样本数量,提高了算法的匹配效率。王可等^[10]利用混合分布模型获取测试样本点的初始概率估计,根据估计的模型与测试样本点对一致集的适应度建立全概率评价准则,并采用逆变映射作为采样策略,加快了算法的收敛速度。Hossein-Nejad等^[11]提出了基于均值的自适应RANSAC算法,用每个点与模型变换后对应点间距离的平均值和方差选择RANSAC的阈值,取得了良好的估计模型参数。Jia等^[12]通过处理原始样本数据并根据特征描述符之间的欧几里德距离预测样本数据中的内点,然后用所选样本估计对应矩阵,提升了算法的实时性和匹配精度。

本文提出了一种基于多层次FAST(MFAST)和优化采样的RANSAC(OSRAC)算法图像匹配算法。针对FAST算法易受光照影响、稳定性差等问题,根据系统层次性理论,采用MFAST算法进行角点提取,用SURF算法确定主方向并生成特征描述子;为了加快算法的收敛速度、提高图像的匹配精度,在基于RANSAC的框架下,利用改进的加权K-最近邻(PTM-DWKNN)分类算法构建两个新的样本集合,根据预检验方法快速计算出最佳模型参数,以剔除误匹配点。最后进行了图像匹配实验,比较了该算法与传统算法的性能,结果表明,该算法能有效提高图像匹配的精度和效率。

2 MFAST-SURF算法

MFAST-SURF算法的主要步骤:首先采用MFAST算法提取角点,然后根据SURF算法确定主方向和特征描述子,最后利用特征描述子完成特征点匹配。算法流程如图1所示。

图 1. MFAST-SURF算法流程图

Fig. 1. Flow chart of MFAST-SURF algorithm

下载图片 查看所有图片

2.1 MFAST算法

FAST算法^[13]是一种基于模板和机器学习的角点检测方法,主要思想:若一个像素与周围邻域像素的差别较大,则该像素可能为角点。FAST算法仅通过比较像素间的灰度值获取角点,计算速度快、实时性较好,但易受光照强度变化的影响,稳定性差,且提取的角点数量多,精度低。

为了提高算法的稳定性和精度,根据系统层次性理论,对FAST算法进行了改进,首先以一个像素点为圆心,分别以3,2 pixel为半径构造两个同心圆,如图2所示。设置一个阈值t,将半径为3,2 pixel圆上的28个像素点的灰度值与I_P(点P的灰度值)进行比较,若连续有21个或18个点差值的绝对值大于t,则认为P是一个候选角点,最后对角点进行非极大值抑制,得到最终角点,将这种方法称为MFAST。经论证,取t=0.18时效果最好。

图 2. MFAST角点检测原理

Fig. 2. Principle of MFAST corner detection

下载图片 查看所有图片

2.2 生成特征描述子

以特征点为中心,构建一个半径围为6s(s为尺度)的圆,如图3所示,用一个角度为60°的扇形滑动窗口,计算窗口内所有特征点水平和垂直方向上的Harr小波响应d_x、d_y,然后按(1)式~(2)式进行累加,响应之和最大的区域对应方向即为特征点的主方向。

mw=∑dx+∑dy,(1)θw=arctan(∑dx/∑dy),(2)

式中,m_w为模值,θ_w为幅值,w为特征点数量。

图 3. 确定特征点主方向

Fig. 3. Determine the main direction of feature point

下载图片 查看所有图片

为了减少光照、视角等因素对特征点的影响,需要对每个特征点构建一个描述子。以特征点为中心取20s×20s的邻域窗口,然后将每个窗口分成4×4的子区域,利用Harr模板计算每个子区域的响应值,形成 ∑dx、∑dx、∑dy、∑dy4个特征矢量,最后生成64维的SURF特征向量,如图4所示。

图 4. SURF描述子的生成

Fig. 4. Generation of SURF descriptors

下载图片 查看所有图片

3 特征点提纯

3.1 标准的随机采样一致性算法

RANSAC是一种鲁棒性参数估计算法,也是目前剔除误匹配点常用的一种方法^[14]。该算法的主要思想:存在某个数据集合,随机从数据集合中选取两个点确定一条直线,然后设置一个误差阈值,计算剩余点到这条直线的距离,如果小于该阈值,判断该点为直线的内点;否则,视为外点。不断迭代随机采样的过程,直到内点数目达到最大且不再改变。其中算法的迭代次数直接影响算法的效率和性能,迭代次数N与内点比例e的关系可表示为

N=log(1-p)log(1-en),(3)

式中,n为计算变换模型H所需最少的匹配对数,p为期望的最大概率。可以发现,e越大,算法迭代次数越少,匹配效率越高;反之,算法迭代次数增加,匹配效率变低,影响了算法的实时性。

3.2 优化采样的RANSAC算法

3.2.1 PTM-DWKNN分类算法获取新样本

传统的RANSAC需要从所有粗匹配对组成的数据集中随机选取4个样本点,计算模型参数H,并利用特征点对模型参数的误差计算内外点集合。其中样本点的选取是随机的,具有一定的盲目性,通常需要大量的迭代次数才能得到最优参数模型。为了提高样本集合中内点的比例,实验采用PTM-DWKNN分类算法^[15]获取新的样本集合,即根据分布特征,为每一个实例(粗匹配点之间的距离)选择最优局部k值。考虑到实例与相邻实例之间的距离带来的影响差异,给相邻的每个实例都分配不同的权重,通过加权投票对测试实例进行分类。计算出初步筛选的每对匹配点的欧氏距离d_i,组成一个数据集合,进行标准化处理。按照一定的比例划分为训练集和测试集,根据每个训练集样本的k值(最近邻样本的个数)求出测试集样本的k值,k的取值范围是预先设定的,且只能为奇数,然后逐个测试k的性能,最佳k值即首次将训练集正确分类的最小k值。利用k个近邻样本与待测样本之间欧氏距离的大小,赋予每个近邻样本一个权重值,通过计算所有近邻的权重之和将数据集分为近距离集合和远距离集合,算法流程如图5所示,其中d_i为欧氏距离,W_i为权值,W₊为近距离样本权值,W_-为远距离样本权值。特征点对之间的距离越近,越可能是匹配点,因此从近距离集合中随机抽取4个点估计模型参数。

3.2.2 预检验

RANSAC中的模型参数是从包含显著比例的异常值数据集中计算得到的,因此得到的模型参数存在较大误差。为了快速得到正确的模型参数,提高算法的匹配效率,文献[ 16]提出了采用预检验的方法减少模型评估的时间。即随机从数据集合中抽取少量数据对计算的模型参数进行检验,过滤掉偏差较大的模型参数,以减少计算量。但由于预检验中抽取的少量数据也可能含有外点,如果计算的模型为错误模型,利用错误样本和正确样本检验的误差都是近似的,所以在外点比例较高的情况下,上述预检验方法会失效。

图 5. 优化采样流程图

Fig. 5. Flow chart of optimized sampling

下载图片 查看所有图片

利用PTM-DWKNN分类算法可得到的近距离集合和远距离集合,即内点集合和外点集合;对待检验的模型参数,从内点集合中随机抽取少量的数据进行预检验,可排除大部分质量不高的模型参数。

4 图像匹配算法

采用MFAST算法提取关键点,SURF算法确定主方向并生成特征描述子,利用快速近似最近邻算法进行粗匹配,计算每对粗匹配点对之间的欧氏距离^[17]

di=(x2-x1)2+(y2-y1)2。(4)

在此基础上用PTM-DWKNN算法将得到的欧氏距离按比例分开,组成两个新的样本集合,以提高内点在样本集合中的比例。从新的集合中随机抽取4个匹配点对计算模型参数H_i,并对得到的模型参数进行预检验,如果通过检验,则采用H_i计算内外点集合,即对于一个特征点k_i,如果其误差值r_i大于设定的阈值r₀,则将该点作为外点,否则作为内点,统计内点的数量M;若M大于设定的阈值S,则认为H_i是正确的模型参数,并利用该集合中所有的内点进行模型参数估计;否则,重新抽样计算模型参数H_i。基于OSRAC的具体步骤:

1) 采用MFAST算法提取关键点,SURF算法生成特征描述子;

2) 利用快速近似最近邻算法完成粗匹配,并计算粗匹配对之间的欧氏距离;

3) 采用PTM-DWKNN算法将所有匹配点的欧氏距离集合按距离分为两个新的样本集合;

4) 从近距离集合中随机抽取4个匹配点对计算模型参数H_i;

5) 对模型参数进行预检验,如果通过验证,进行下一步;否则舍弃,回到步骤3);

6) 利用H_i验证匹配点对是否为内点,并统计内点的数量M;

7) 如果M>S,则利用M重新计算新的模型H_i;否则,返回步骤3);

8) 重复步骤3)~步骤6)N次。

5 实验结果与分析

5.1 阈值t的确定

实验条件:操作系统为Windows10,处理器为Intel(R) Core(TM) i7-7700HQ,频率为2.80 GHz,内存为8 G,仿真软件环境为Matlab R2014a。

选取一组图像,改变MFAST算法中的阈值t,根据图像匹配的精度确定算法的最佳阈值t。选取两幅图像,取t在0.13~0.22范围内进行实验,结果如图6所示。可以看出:当t<0.18时,图像匹配的精度随t的增大而增加;当t>0.18时,图像匹配的精确度随t的增大而降低。当t=0.18时,图像的匹配率最高,所以MFAST算法的t为0.18。匹配精度R可表示为

R=NcorrectNall,(5)

图 6. t的确定

Fig. 6. Determination of t

下载图片 查看所有图片

式中,N_correct为正确的匹配点对,N_all为全部匹配点对。

5.2 基于OSRAC的实验

为了验证OSRAC的有效性,选取1组图像(原始图像、旋转图像、光照变化的图像),分别采用尺度不变特征变换(SIFT)算法-RANSAC和SIFT算法-OSRAC进行图像配准实验,实验条件与5.1节相同,软件环境为VS2017,配置OpenCV3.4,SIFT算法阈值为0.8,结果如图7~图9所示。可以看出,SIFT-RANSAC虽然剔除了一部分误匹配点,提高了匹配精度,但仍存在一些错误的匹配点;

而SIFT-OSRAC剔除了大部分的误匹配点,且相比SIFT-RANSAC匹配精度有明显的提升。

表1对两种算法的匹配精度和时间进行了对比分析,可以看出,RANSAC在图像发生变化后,匹配精度有所下降,稳定性差;而OSRAC在图像发生变换后,匹配精度依然保持在85%以上,相比RANSAC算法,稳定性好、匹配时间少,这证明了OSRAC的匹配精度高、实时性好。

图 7. 两种算法对原始图像的处理结果。(a) SIFT-RANSAC;(b) SIFT-OSRAC

Fig. 7. Processing results of the two algorithms on the original image. (a) SIFT-RANSAC; (b) SIFT-OSRAC

下载图片 查看所有图片

图 8. 两种算法对旋转图像的处理结果。(a) SIFT-RANSAC;(b) SIFT-OSRAC

Fig. 8. Processing results of two algorithms on rotated image. (a) SIFT-RANSAC; (b) SIFT-OSRAC

下载图片 查看所有图片

图 9. 两种算法对光照变化图像的处理结果。(a) SIFT-RANSAC;(b) SIFT-OSRAC

Fig. 9. Processing results of the two algorithms on the image of illumination change. (a) SIFT-RANSAC; (b) SIFT-OSRAC

下载图片 查看所有图片

5.3 图像匹配实验

在Matlab R2014a中,对三组真实场景下拍摄的原始图像、光照变换后的图像,分别用FAST-RANSAC、MFAST-OSRAC和SIFT-RANSAC三种算法进行匹配,结果如10~图11所示。表2为三种算法在匹配原始图像、光照变化图像时的匹配精度和时间,可以看出,与原始的FAST-RANSAC相比,MFAST-OSRAC的图像匹配算法的匹配精度高、耗时短。

图 10. 第一组图像。(a) FAST-RANSAC;(b) MFAST-OSRAC;(c) SIFT-RANSAC

Fig. 10. First group of images. (a) FAST-RANSAC; (b) MFAST-OSRAC; (c) SIFT-RANSAC

下载图片 查看所有图片

图 11. 第二组图像。(a) FAST-RANSAC;(b) MFAST-OSRAC;(c) SIFT-RANSAC

Fig. 11. Second group of images. (a) FAST-RANSAC; (b) MFAST-OSRAC; (c) SIFT-RANSAC

下载图片 查看所有图片

图 12. 第三组图像。(a) FAST-RANSAC;(b) MFAST-OSRAC;(c) SIFT-RANSAC

Fig. 12. Third group of images. (a) FAST-RANSAC; (b) MFAST-OSRAC; (c) SIFT-RANSAC

下载图片 查看所有图片

6 结论

提出了一种基于MFAST和OSRAC的图像匹配算法。利用MFAST算法进行特征点提取,SUFT算法生成描述子。然后,采用快速近似最近邻算法进行特征点粗匹配,计算得到粗匹配对的欧氏距离;在利用RANSAC算法剔除误匹配点的过程中,根据PTM-DWKNN分类算法计算出两个新的样本集合,从而提高了内点在样本集合中的比例,减少了算法的迭代次数,并采用预检验技术对计算的模型参数进行检验,计算出更加精确的模型参数。实验结果表明,该算法显著提高了图像配准的精度。但由于使用MFAST算法将28个像素点与中心像素点进行比较,增加了系统的计算量。因此,在未来的研究工作中将重点考虑进一步降低计算量,以提高系统匹配效率。