基于改进SURF的增强现实图像匹配方法

贾一鑫,邓魏永,殷 强,毋 涛

(1.西安工程大学 计算机科学学院,陕西 西安 710699;2.华宇铮蓥集团,福建 泉州 362801;3.中国纺织工业联合会,北京 100020)

0 引 言

随着计算机视觉的飞速发展,增强现实技术[1](Augmented Reality,AR)在多个领域得到广泛应用,包括游戏娱乐[2]、教育培训[3]和工业制造[4]等。其中,图像匹配技术是AR最基本的一步,其基本原理就是将摄像头捕获的图像中提取的关键点和特征描述子与预先建立好的数据模型中的关键点及特征描述子进行匹配,最终得到匹配结果。

Lowe提出了SIFT[5](Scale-Invariant Feature Transform)算法,该算法能够在不同的光照、旋转、缩放等变换下提取出相同的特征点,因此在计算机视觉和图像处理领域得到广泛应用。但是此算法仍有很多不足,如算法复杂度高、计算量大、匹配成功率低、花费时间长等。Herbert Bay等在2006年提出了SURF[6](Speeded-Up Robust Features)算法,在计算机视觉和增强现实等领域得到广泛应用。尽管SURF算法在匹配速度和稳健性方面表现良好,但在一些特殊情况下,例如场景发生剧烈变化或存在光照变化时,其匹配精度仍然有待进一步提高。因此,研究人员提出了许多改进SURF的算法,旨在提高其匹配精度和鲁棒性。黄春凤等[7]提出了一种改进SURF算法,该算法采用近邻搜索算法实现Kd-Tree快速查找最近邻特征点,最后用双向唯一性匹配的方法完成特征匹配,虽然该算法降低了时间复杂度并提高了匹配精度,但是鲁棒性有待提高。Liu等[8]提出了一种改进RANSAC特征图像匹配方法,虽然提高了匹配精度,但是算法的时间复杂度较高。Gu等[9]提出了一种用于大旋转角估计的数字图像相关的改进SURF方法,此方法用新的收敛阈值从参考图像和变形图像中细化初始参数,并提出了一种由多环模板发展而来的评估标准来计算特征点对的相似性,以提高收敛速度和采样精度,但是该算法的时间复杂度相对于传统算法没有提高。邹玉英等[10]提出一种用SURF算法来提取待匹配图像特征点,之后对SURF的度描述符降维,用KNN算法双向匹配特征点,再使用RANSAC算法剔除错误匹配的匹配算法,此算法提高了匹配精度,但是匹配效率较差。

针对以上问题,该文提出了一种基于SURF算法的改进图像匹配算法。首先,对SURF算法中的特征描述子进行改进,对于匹配结果,用RANSAC[11]去除极端异常值;然后,使用基于三角不规则网络(TIN)[12]局部估计来去除其余虚假匹配,从而提高其匹配精度和鲁棒性。

1 相关理论

1.1 SURF算法

SURF算法采用Hessian矩阵行列式近似值图像,也就是DOH算子,替代了SIFT的DOG算子[13]。该算法继承了SIFT算法的鲁棒性,并且改进了其特征提取部分,大大缩短了SIFT算法的计算时间[14]。SURF算法主要包括以下三个步骤。

第一步:特征检测。首先,建立积分图像,I∑(x)表示位于位置(x,y)处像素上方的左侧的输入图像的像素总和,其公式如下:

(1)

然后,用Box滤波器取代二阶高斯滤波器开始检测和定位特征点,目的是降低计算成本,Box滤波器的原理就是利用模板近似高斯二阶偏导数,如图1(a)所示。通过以上两步可以求得尺度空间函数。与SIFT的高斯差分金字塔不同,SURF建立尺度空间是不需要进行高斯模糊。SURF特征点定位的核心是Hessian矩阵,公式如下:

(2)

(3)

其中,x和y表示点X的坐标。

接着,用多向BOX滤波器进行卷积得到Dxx,Dxy,Dyy,替换Hessian矩阵中的Lxx,Lxy,Lyy,从而得到SURF快速Hessian矩阵,其公式如下:

det(H)=DxxDyy-ω(Dxy)2

(4)

然后,在3×3×3尺度空间中应用非极大值抑制,如图1(b)所示,在尺度空间中所选点的26个邻居中的极值点被视为SURF特征点,其对源图像的尺度是不变的。

图1 盒式滤波和非极大值抑制

第二步:特征描述。每个SURF特征点的主要方向由x和y方向上的高斯分布加权的Haar小波卷积表示。Haar小波模板如图2所示。

图2 特征点主方向和描述符构造

以当前特征点为中心,半径为6σ(σ是滤波器的大小)的滑动π/3扇窗,以扫描此处的圆形区域的小波响应,如图2(a)所示,小波响应之和最大的扇形被确定为特征主方向。

完成之后开始构建特征描述符。在确定当前特征点的主方向后,构建一个正方形采样区域,接着,将这个采样区域划分为16个子区域,并进一步将每个子区域划分为25个样本网格,并从Haar小波卷积中获得每个子区域的x轴和y轴正负方向上的四个描述符。随后,获得SURF特征点的64维描述符,如图2(b)所示。

第三步:特征匹配。对于参考图像和待匹配图像,分别执行步骤一和二。使用对应的描述符来计算两个图像中的所有SURF特征点之间的欧几里得距离d。d的最小值和次最小值分别定义为最短距离d1和第二短距离d2。如果比率d1/d2低于指定的阈值,则可以获得一对匹配点。所有SURF特征点都是以这种方式获得的,并且所有特征点都形成了匹配特征集。

1.2 DAISY描述符

尽管SURF算法的速度比SIFT算法的速度快三到四倍,但是与局部特征算子的性能相比,SURF算法的鲁棒性较差[15]。

DAISY[16]描述符是一种局部特征描述符。它由一些中心对称的圆构成,如图3所示,以原点为中心,构建一个三层同心圆,每层包含8个采样点,并且这些点呈45度分布[17]。且每个采样点具有相同的高斯尺度值,随着与原点的距离越来越大,高斯尺度值也逐渐增大。这种结构使得DAISY描述符对图像的仿射变换和光照变化具有良好的鲁棒性。

图3 DAISY描述符

1.3 随机抽样一致算法

RANSAC算法[11]是一种高度鲁棒的估计技术,通过去除给定数据集中的异常值来拟合任何给定模型。它主要基于随机投票原理计算模型参数,即使在存在大量异常值的情况下也能高效计算,并能鲁棒地处理多种结构数据[18]。下面是RANSAC算法的主要步骤:

(1)从数据集中随机选择一个子集作为内点集合,使用该子集来估计模型的参数。

(2)对于数据集中的所有其他点,计算它们与估计的模型之间的误差。将所有与该模型拟合误差小于某个预定义阈值的点视为内点,其他点视为外点(离群点)。

(3)如果当前估计的模型内点数目大于之前模型的内点数目,则用当前模型来更新内点集合,并重新估计模型参数。

(4)前模型内点数目小于预定义的阈值,则返回第1步。

(5)如果最大迭代次数或内点数目超过某个预定义的阈值时,终止算法。

最后输出的模型参数是在所有迭代中拥有最多内点的模型的参数。RANSAC算法的优点在于它的鲁棒性,即能够对包含大量噪声和异常值的数据集进行有效的模型拟合。另外,由于它是一种随机采样的算法,因此在不同的采样次数下,能够获得不同的模型参数,并能够找到全局最优解。

但是,RANSAC算法也存在一些缺点。首先,由于它是基于随机采样的,因此可能无法找到最优解。其次,RANSAC算法的性能取决于内点数目,而内点数目与预定义的阈值有关。这个阈值可能需要根据实际情况进行调整,这会导致算法的复杂性增加。

1.4 三角不规则网络

三角不规则网络(TIN)也可用于剔除误匹配对,算法原理如下:

(1)使用匹配点的坐标构建三角网,并通过以下步骤逐一判断三角网中的点;

(2)基于TIN结构收集当前判断点周围的几个最近的相邻点。通过迭代方法确定相邻点:首先,收集与判断点相邻的所有点,然后找到更多与所收集的点相邻的点,并不断地收集这些点;

(3)基于所收集的匹配点的坐标,可以估计局部失真的仿射变换参数;

(4)使用先前获得的仿射参数来计算判断点的残差。如果误差大于某个阈值,则判断点及其对应点被消除为假匹配。否则,进入步骤(2)来判断下一点;

(5)在遍历三角网中的所有点之后,返回步骤(1),使用剩余的点重建新的三角网[12]。该过程继续进行,直到所有点的残余误差满足要求为止。

最后,将所有获得的关键点连接到一组匹配点。

2 文中算法

由于传统SURF算法在特征描述阶段采用高达64维的特征描述符,导致算法的复杂度高,计算量大,并且最终匹配结果正确率不高。因此,该文对特征描述符进行改进,并对匹配结果进行提纯。算法流程如图4所示。

图4 算法流程

2.1 改进特征描述符

SURF算法在特征描述阶段获得特征主方向后,使用DAISY描述符替代SURF中的64维描述符,与SIFT和SURF使用矩形邻域不同,DAISY描述符使用圆形邻域,因为圆形邻域具有更好的定位特性。DAISY算子采用高斯核卷积完成梯度直方图加权,由于高斯核存在各向同性,无需重复计算梯度直方图。由图3可知,每隔45度取一个采样点,共得到25个采样点。DAISY描述符可较容易获得旋转不变性,因此该文选择DAISY描述符替换SURF算法的描述符。DAISY描述符的基本流程如下。

首先,原始图像上像素的八个方向梯度可以表示为Lxy*Dxy,其中Dxy表示梯度方向。然后,通过多次高斯卷积可以获得同心圆中每层的采样点高斯卷积值。对于每个像素,可以获得长度为8的向量来表示局部梯度方向直方图,用Hxy表示。因此,可以得到DAISY的描述符方程,其表示如下:

(5)

其中,∂H表示每层的方向,x表示以像素为中心的同心圆上采样点的坐标。最终获得的特征向量包含8个维度,两个向量的欧几里得距离用于测量描述符之间的相似性,如果低于设定的阈值,则可以获得一堆匹配点。

2.2 匹配结果提纯

如果使用SURF中的匹配算法进行匹配,这样的策略不能完全降低在特征匹配阶段匹配的关键点集中出现错误匹配和异常值的风险。

因此,大多数匹配策略采用RANSAC算法或其变体来减少失配。然而,这种算法无法准确处理复杂的局部失真,尤其是当图像比较大或目标需要精确匹配时[19]。因此,对于2.1获得的匹配点对,该文首先应用RANSAC算法来去除极端异常值,然后使用基于三角不规则网络(TIN)的局部估计[12]去除其余虚假匹配。

文中算法虽然略微增加了算法时间复杂度,但提高了经典SURF算法在处理图像旋转匹配方面的能力,不仅在计算速度上保持了原始SURF算法的优点,而且提高了匹配精度和鲁棒性。

3 实验结果和分析

实验平台为MATLAB R2020b,实验环境为DELL G15 5511,Intel Core i7-11800H 2.3 GHz,8核心16线程,GPU为NVIDIA GeForce RTX 3060 Laptop 6G (GDDR6 Micron),16 GB内存,操作系统为64位Windows 11。实验数据采用两张分辨率为2 641×3 519的书的图片。

为验证文中算法的性能,进行了对比实验,分别使用SIFT算法、SURF算法、文献[10]算法以及文中改进算法进行测试,如图5所示。并从匹配正确率、算法所用时间和鲁棒性三个方面进行验证分析。

3.1 匹配正确率分析

匹配成功率是算法的重要指标之一,其计算方法是用成功匹配对数比正确匹配对数与错误匹配数之和。分别使用SIFT算法、SURF算法、文献[10]算法和文中改进算法对同一组图片进行多次实验,最后取平均值,得到每个算法的匹配正确率。

从表1可知,SIFT算法获得了最多的匹配点,相较于SIFT算法,SURF算法的正确率较低且匹配点数量较少。该文提出的算法直接使用DAISY描述符来替代原始SURF算法的描述符,降低了描述符维度,相对于SURF算法和文献[10]算法,在平均正确率和平均正确匹配点数方面有较大的改进。这表明在相同的特征点检测和主方向确定的情况下,使用DAISY描述符进行匹配比原始SURF描述符效率更高,并且使用RANSAC算法加TIN算法处理得到的结果正确率更高。

表1 四种算法正确率对比

图5 四种算法对比

3.2 时间复杂度分析

时间复杂度是指执行算法所需要的计算工作量,公式如下:

T(n)=O(f(n))

(6)

其中,n为问题规模,T(n)为时间复杂度,f(n)和程序执行时间成正比,O表示程序执行的阶。

实验使用上述4种算法对同一组数据进行多次实验,最后得到平均时间复杂度,并进行对比分析,结果见表2。

表2 三种算法时间复杂度对比

由表2可以看出,SIFT算法非常耗时,并且该算法的时间复杂度几乎是SURF算法的三倍。传统SIFT算法耗费时间最长,文献[10]算法由于对描述符降维并对匹配结果进行了优化,因此耗费时长略大于原始SURF算法。文中算法采用了DAISY描述符代替SURF中的描述符,并采用随机抽样一致算法和TIN对匹配结果进行优化,虽然算法时间复杂度与传统SURF算法以及文献[10]算法相当,但在几乎相同的时间内达到了更好的效果。

3.3 鲁棒性分析

为了验证文中算法的鲁棒性,分别对实验图像做光照变换和旋转变换,如图6所示。

图6 光照变换和旋转变换

图6中(a)和(b)分别表示使用文献[10]算法和文中算法在光照变换和旋转变换下的匹配结果。

由表3数据显示,在实验图像光照变换和旋转变换下,文中算法的平均时间复杂度比传统文献[10]算法略高,但匹配精度更高。综合考虑匹配结果和计算时间,文中算法在运行时间略有增加的情况下,得到了更好的结果,这表明文中算法在鲁棒性上比原始SURF算法以及文献[10]算法更优越。

表3 光照变换和旋转变换对比

4 结束语

针对原始SURF算法匹配精度较差、鲁棒性不强等缺点,提出了一种改进SURF算法。首先用原始算法的Hessian矩阵进行特征点检测和提取,然后计算原始图像的梯度方向图像,用DAISY描述符替代SURF算法的描述符,最后使用RANSAC算法结合TIN算法对匹配结果进行剔除和优化。实验结果表明,该算法虽然略微增加了时间复杂度,但却大大提高了原始SURF算法的鲁棒性和匹配精度。

但是,由于增强现实对于图像匹配算法的实时性要求很高,该算法还需要在时间复杂度上进一步优化,这也是未来工作的重点。