改进的SURF-RANSAC图像匹配算法

赵 谦，童申鑫+，贺 顺，尹怡晨,2

(1.西安科技大学 通信与信息工程学院，陕西 西安 710054；2.西安地山视聚科技有限公司，陕西 西安 712044)

0 引 言

随着科技的进步，计算机视觉技术在国内外被广泛应用，例如三维重建、图像配准[1,2]等。图像拼接技术已深入到遥感影像、全景图像、医学影像处理等领域，其中特征点检测与匹配作为不可或缺的分支也得到了人们的重视。DavidG. Lowe提出了SIFT算法[3]，该算法具有128维的特征描述向量，但数据复杂度高、匹配精度低且算法运行时间长。Bay等提出的SURF算法[4]虽然降低了描述符维度并且保留了SIFT算法的旋转、尺度不变性，但仍存在匹配精度低、时效性差等问题。赵俊峰等[5]在无人机影像匹配实验中改进SURF算法，虽然提高了匹配速率但发现对角点的提取不是很理想。文献[6]提出一种双向邻近匹配的彩色图像配准算法，提高了对图像色彩信息的自适应匹配能力，但在特征点数量较多情况下匹配精度不高。文献[7]将图像分块与SIFT相结合，在待匹配图像中减少了大量无用搜索区域，进而提高了匹配速度。文献[8]将BRISK描述符和Canny边缘检测应用于红外图像拼接，该方法有效地减少了算法运行时间，但匹配精度还有待提高。

针对上述算法存在的问题，提出一种改进SURF特征匹配和余弦约束RANSAC相结合的算法，从特征描述符降维、自适应阈值匹配及误匹配点对的剔除3个方面进行改进。实验结果表明，改进的算法不仅提高了匹配速率和匹配精度，还具备较好的鲁棒性。

1 SURF算法

SURF算法加入积分图以及Haar特征来减少数据复杂度，同时在处理图像的旋转和模糊不变性等方面也有所提高。该算法首先通过Hessian矩阵生成所有的兴趣点，构建尺度空间确定特征点的位置；然后统计特征点圆形邻域内的小波特征来找到特征点主方向；最后生成64维度的特征向量并完成匹配过程。该算法具体包括以下几个步骤。

1.1 SURF特征点提取

SURF算法在特征提取阶段分为积分图像建立、尺度空间极值检测和特征点定位3个步骤。

SURF特征匹配算法[9,10]利用积分图像，相比于SIFT算法节省了大量运行时间，首先将原图像I(x,y)与二阶高斯微分模型做卷积处理，记为L(x,y,σ)，σ为图像尺度

L(x,y,σ)=G(x,y,σ)*I(x,y)

(1)

对图像I(x,y)中像素点(x,y)计算Hessian矩阵H

(2)

式中：Lxx(x,y,σ)、Lxy(x,y,σ)和Lyy(x,y,σ)指高斯滤波二阶微分。即∂2G(x,y,σ)/∂2x、∂2G(x,y,σ)/∂x∂y和∂2G(x,y,σ)/∂2y与图像I(x,y)在点(x,y)处做卷积运算。其中

(3)

在特征点检测过程中，为了使其具备尺度不变性，需要在不同尺度下寻找特征点。因此使用不同尺寸盒子滤波器在不同方向上对积分图像做卷积运算，构建图像的尺度空间。

通过快速Hessian矩阵判别式来提取局部极大值，确定关键点的位置，上述关于SURF特征点提取的原理见参考文献[11]。将滤波过程变为有限次数的加减运算，如图1所示。通过不同大小的方框滤波器快速构建Hessian矩阵判别式为

图1 盒子滤波器代替高斯二阶微分

Det(H)=DxxDyy-(ωDxy)2>K

(4)

式中：Dxx、Dxy和Dyy分别是图像I(x,y)中像素点(x,y)与不同尺寸方框滤波器卷积结果，K为选定的阈值；ω为补偿系数。

1.2 特征点主方向确定

为满足旋转不变性，需要确定特征点的主方向。具体的做法是以特征点为中心，计算半径为6S(S为特征点所在的尺度值)邻域内的点在x方向和y方向的Haar响应值，并将其赋予高斯权重。使用60°的扇形窗口扫描整个圆形区域，并计算每次旋转后区域内Haar小波特征值[12]。数值最大的扇形对应的方向为主方向，如图2所示。

图2 选取特征点主方向

dx和dy分别为x、y方向的小波响应，τ为扇形区域，θτ为τ扇形窗口内采样点的幅角，该区域对应的方向计算方法如下

θτ= arctan(∑τdx/∑τdy)

(5)

1.3 特征描述符生成

在坐标系中以特征点为圆心，坐标轴旋转至主方向位置。选取边长为20S的正方形窗口，然后将其分割为16个子窗口。统计每一点的 Haar小波响应，在每个子区域中分别统计∑dx、∑dy、∑|dx|和∑|dy|，形成一个四维向量。按此方法计算整个窗口的响应值后可得到一个64维[13]的特征向量。将特征描述符进行归一化处理，其目的是为了在图像发生旋转变换、尺度变换等情况下具有很好的鲁棒性。

1.4 SURF特征点匹配

SURF特征匹配算法是对特征向量进行某种距离度量，常用方法有以下两种：

最小距离法[14]是根据待测图像间特征点之间的欧氏距离来确定匹配度，欧氏距离越小则匹配度越高。

最近邻比值法[15]是在找到原图像和待匹配图像特征点后，在原图像中针对某一特征点，在待匹配图像中寻找与该特征点具有最小欧式距离的待匹配点，即为最近邻点距离，同时计算次近邻点距离，计算两者这间的比值作为特征匹配的阈值，距离比率小于该阈值则记为正确匹配点对。

2 本文算法

传统SURF算法生成的64维描述符存在维数高、实时性差等问题，本文提出的图像匹配算法流程如图3所示，主要包括特征提取、特征描述符降维、阈值自适应匹配、匹配点对提纯4个步骤。

图3 本文算法流程

首先在基于SURF算法检测到特征点及确定主方向后，构建圆形邻域提取到32维描述符；然后采用阈值自适应方法完成特征点粗匹配；最后利用特征向量建立余弦约束模型优化RANSAC算法完成特征点的精匹配。

2.1 SURF描述符的降维

为了减少SURF特征匹配算法的数据复杂度，本文首先对特征描述符的生成过程进行改进从而实现其降维处理。在传统算法中当主方向处于不同位置时，其计算描述符统计响应的区域也不一致，如图4(a)所示。当主方向发生偏差时原本需要统计的黑色区域就会被忽略，降低了旋转后的区域相似性。因此本文以特征点为中心采用圆形领域计算特征描述符，如图4(b)所示。目的是当主方向不管如何偏移，描述符计算的范围都相同，剔除了边缘干扰像素点的同时，相比于矩形区域提取描述符减少了大量时间。

图4 矩形与圆形邻域比较

本文针对SURF描述符的降维提取分为以下几步：

步骤1以特征点为圆心，在邻域内选取R为10S的圆形领域。为了实现旋转不变性，将圆形区域根据特征点的主方向进行旋转；

图5 基于圆形邻域提取描述符

步骤3通过以上方法在每个特征点的周围构建了8个子区域，每个区域计算特征点在水平、垂直方向上的Haar小波响应值。并对其赋予高斯加权系数，然后计算每个区域响应值的和。因此，在每个子区域中可得到V=(∑dx,∑|dx|,∑dy,∑|dy|)。最后对每个子区域的响应值进行统计，可以得到32维的描述符。计算的特征向量可表示为

L=(l1,l2,l3……,l32)

(6)

步骤4对特征向量长度做归一化处理

(7)

圆形具有很好的旋转不变性，因此将描述符提取方式由矩形改为圆形则在每个特征点的匹配过程都会减少相应的旋转时间。描述符维度从64维度降到32维度，匹配过程不仅降低数据复杂度还会提高算法的运行速率。

2.2 阈值自适应匹配

传统SURF特征匹配算法在找到待测图像与模板图像的匹配点后，将其之间的欧氏距离作为相似度准则[16]

(8)

传统方法中利用人为设定的阈值往往会对匹配精度和结果产生影响，并且单向匹配会产生一对多匹配的现象。在特征点匹配阶段，本文首先通过阈值自适应方法对初始匹配特征集合进行筛选，然后将每组特征点对与计算得到的阈值进行比较，最后结合特征双向匹配消除“一对多”的误匹配情况。特征匹配过程改进的具体步骤如下：

步骤1假设两幅图像的特征点集分别为N1与N2。在N1中针对每一个特征点，从N2中寻找与之欧式距离最小的两个点，分别记为d′n和d″n，两幅图像的特征匹配对数记为n。因此获得比值集合

(9)

步骤2对上一步得到特征点比值集合Gd进行降序排序，剔除前10%及后10%的数据，将剩余数据求和取平均值得到Te，将其作为初始化阈值；

步骤3若检测到的点的最近和次近邻域距离之比满足：d′n/d″n

步骤4将以上待检测图像反过来作为基准图像，即将点集N2作为寻求最佳匹配点对的集合。

2.3 改进的RANSAC算法

2.3.1 RANSAC算法原理

随机抽样一致性(RANSAC)算法[17,18]是一种稳定可靠的剔除错误匹配点算法，利用不断迭代的方式来获取一个最优的数学模型，如图6(a)所示，数据集合中包含噪声点和能形成一条直线的数据点集合。RANSAC的基本原理：首先随机选取4个不共线样本点，计算其变模型矩阵。接着设定一个误差阈值，将在误差范围内的数据点归为拟合直线中的点，即为内点；若计算误差大于阈值，即为外点。最后通过不断迭代拟合直线的数据点，直到数量最多并保持不变，如图6(b)所示。

图6 RANSAC算法数据拟合模型

RANSAC算法具有良好的鲁棒特性同时能减少噪声的影响，但RANSAC算法也存在迭代次数不稳定、计算复杂度高等不足之处。

2.3.2 特征向量余弦约束

在进行RANSAC算法剔除误匹配阶段，考虑将余弦约束加入其中实现精准匹配。本文通过计算两个特征向量的夹角余弦值来评估他们的相似度。由于两个特征向量构成的余弦值满足旋转不变性，而且具备不受缩放等变化干扰的特性。因此建立特征向量余弦约束，即

(10)

式中：p和q分别对应待匹配图像中特征点对应的特征向量。

特征向量余弦约束原则：实验中计算出每对特征向量之间的余弦值，根据余弦数值的分布情况设定余弦判定阈值Cω，然后通过上式计算的结果与Cω进行比较。若计算的余弦值大于Cω，则判定特征向量p、q对应的特征点为候选匹配点。将该约束方法与RANSAC算法相结合完成精准匹配。

2.3.3 本文RANSAC算法

为了减少迭代次数和提高配准精度，本文对RANSAC算法进行改进，具体思路如下：

步骤1由于最近邻与次近邻的比值越小，两者匹配的置信度越高。首先选取特征点的最近邻与次近邻距离比值在0.45附近的40%点集作为样本集合；

步骤2从得到的特征点集中随机选取4组匹配点建立约束方程。在保证选取的匹配点对不共线的情况下，采用最小二乘法计算单应性矩阵F；

步骤3利用特征向量余弦对剩余特征点进行约束，即如果每对特征匹配点的特征向量余弦值大于设定的阈值Cω，则将其加入内点，否则，将其剔除；

步骤4若当前内点集中特征点数大于最优内点集中的数目，则认为当前参数模型矩阵为最佳矩阵，并更新迭代次数M；

步骤5直到内部点数不再变化并得到最终的内部点集，计算最终的变换矩阵。

改进的RANSAC算法在选择匹配点上发生了变化，初始样本集合中内点数增大，因此大大减少了算法的迭代次数，选择正确点对的概率增加并且建立了特征向量余弦约束提高了匹配精度。

3 算法结果与分析

本实验平台为：MATLAB(2014b)，运行环境：Intel core i5-8250U/1.60 GHz CPU，8 GB内存，64位Windows 10操作系统。

为了验证本文算法的时效性和准确性，实验中采用了大量图像进行特征匹配实验分析。并与其它3种算法进行比较，选取其中A、B、C这3组实验对比结果如图7～图9所示。并结合匹配时间、匹配精度和算法鲁棒性3个评价指标进行分析验证。

图7 A组图像不同算法匹配结果对比

图8 B组图像不同算法匹配结果对比

图9 C组图像不同算法匹配结果对比

3.1 匹配正确率分析

匹配正确率反映了特征描述符匹配性能的优劣程度，匹配正确率越高说明其匹配性能越好。其计算公式如下

P=Nc/(Nc+Ne)

(11)

式中：Nc为最终正确匹配特征点对数目，Ne为错误匹配特征点数目。

表1为传统SIFT算法、SURF算法、文献[19]及本文算法对选取的3组实验匹配正确率对比结果，从表中以及实验对比结果图中可以看出SIFT算法虽然检测的特征点较多，但是出现大量的误匹配点对，即“匹配交叉”、匹配“一对多”等情况，从而导致正确匹配率不高。从图7～图9的实验中可以看出传统SURF算法处理的匹配结果中均出现匹配交叉的情况；图10可以看出在同一组测试实验中本文算法得到的正确匹配率均高于其它3种算法，达到90%以上，得到的总匹配对数虽然不多，但在匹配正确率方面提高了10%～20%。因为在特征匹配阶段采用阈值自适应方法及双向匹配准则减少了伪匹配点对，最后建立特征向量余弦模型优化RANSAC算法进行特征点对的提纯，实验结果表明本文算法具有较好的稳定性和抗干扰能力。

表1 不同算法正确匹配率比较

图10 正确匹配率对比结果

3.2 时间复杂度分析

实验中为了验证算法的时效性进行多组分析比较，得到本文算法和其它3种算法的匹配时间结果见表2。

表2 不同算法时间对比/s

从表2及图11算法时间对比中可以看出，对于同一组测试实验本文提出的算法匹配时间最少，相比于SIFT算法匹配速度提高了70%左右，与传统SURF算法及文献[19]算法相比，匹配速度均有所提高。这是由于本文采用圆形区域构建描述符，以至于描述向量降至32维，减少了数据复杂度；同时结合余弦向量约束改进RANSAC算法，优化样本模型来求解变换矩阵减少了迭代次数，运行总体时间相比于传统算法明显提高，因此本文算法具有运算速度优势且具有良好的性能。

图11 匹配时间对比结果

3.3 鲁棒性分析

为了验证本文算法的鲁棒性，从牛津大学机器人实验室的图像数据库中任意选取4组图像[20]。图12(a)为旋转和尺度发生变换的图像，图12(b)为发生模糊变化的图像，图12(c)为相机视角发生30°仿射变换的图像，图12(d)为亮度和对比度发生变化的图像。

图12 本文算法匹配结果

图12为选取具有不同几何、光照变换以及不同场景下的图像作为测试图像，并通过本文算法得到匹配结果。本文使用圆形邻域代替矩形邻域提取描述符，增强了描述符的抗旋转能力，降低了描述符的维度，并将描述符进行归一化降低了其对仿射变换和光照的敏感性。采用自适应阈值的匹配法则并结合RANSAC算法的优化，减少了伪匹配点对，提高了匹配正确率。实验结果显示本文提出的算法对图像的仿射变换、模糊、光照变化、旋转与缩放都有较强的鲁棒性，能较好克服几何变换产生的伪匹配点，表3显示与传统SURF算法相比提高了匹配正确率和运行时间，有较好的稳定性和抗干扰能力。因此本文算法适用于图像的仿射变换、模糊情况、光照变化、旋转等情况，在不同的干扰下仍然具有很好的鲁棒性。

表3 本文算法与SURF算法对比

4 结束语

本文针对传统SURF算法存在描述符维数高、匹配精度低的问题，提出了一种改进SURF-RANSAC算法。首先在提取特征点阶段将原有64维的特征描述符降至32维，减少数据复杂度和算法匹配时间；然后采用自适应阈值的方法避免了人为设定阈值对匹配结果的影响，采用双向匹配准则消除匹配“一对多”的现象；最后对于误匹配剔除过程，结合特征向量余弦约束改进RANSAC算法，进一步提高匹配精度。通过实验结果分析并与其它3种算法进行对比，本文算法在提高了匹配精度的同时，缩短了匹配时间，使得算法具有较强有效性和鲁棒性。在今后的研究中，仍需要进一步优化算法的性能和自适应性，以至于能够应用于不同场景的图像配准实验中。