一种面向三维重建的改进SIFT图像匹配算法

◆王梓任 杨友良 马翠红

（华北理工大学电气工程学院 河北 063210）

随着虚拟现实和三维建模技术在国内的迅速发展，相比之前需要设备的性能可能也会变得更高。而快速获取和处理目标场景数据，建立较高精度的三维模型也成为现今的研究热点。现如今主流的三维信息获得方式有三种：第一种，使用精密仪器的三维数据获取，比如说，激光雷达扫描，这种方式虽然高效，直接，精度也高，但是成本比较高。第二种，使用Kinect扫描来获取数据，这种方式便捷，有效，局限在于范围有限。第三种，是利用图像的来收集三维信息的方式。这种方式便捷，经济，有真实感。这几种方法中基于图像的三维数据获取是最具发展前景和应用价值的，并且方便图像的处理，也拥有更广泛的视角。同时图像匹配方法通常应用在图像处理方面，其主要是针对不同视角、不一样的方式获得的图像，通过匹配算法，找出图像之间纹理、特征、结构等的相似性和一致性，进而找出相似图像。其中特征匹配成为图像领域中的热点问题，高精度的特征匹配能够更好得到三维建模所需要的条件。这样我们就有必要应用更好的更加低廉的实时处理算法。

1 小波变换和Harris相结合算法

目前，有许多特征点检测和算法提取方法。现阶段主流算法有采用角点提取的Harris算法与点提取的SIFT算法、FAST算法、SURF算法、ORB算法。Harris角点检测算法基于灰度图像，并设计局部检测窗口，使窗口在所有方向上略微移动[1]。当检测中能量变化大于阈值，那么其中心像素会被选取为角点[2]。该算法简单而稳定，它不受照明，旋转和噪声的影响，但是当图像比例改变时，特征点会发生显著变化。FAST算法是加速算法。SURF是SIFT算法的加速版本，ORB是FAST和描述符的组合。所有加速算法都有少量特征点，却因为点变少，导致精度变差，加大了误差。首先对参考图像和场景图像进行离散小波变换，提取两幅图像的低频部分，然后利用Harris角点检测来检测其低频部分的感兴趣点，确定场景的匹配候选区域。

2 小波变换和哈里斯角点检测

2.1 小波变换

我们可以学习每次通过小波分解分解低频f0的二维小波分析分解成因此，通过db小波变换，每部分图像的大小将减小到之前图片的1/4大小。为了获得有效且准确的匹配图像，最初图像的大小应满足式（1）：

其中L是分解的最大次数，图像大小是N×N。

1.2 harris角点检测

harris角点检测算法是由 C.Harris和 M.Stephens 在H.Moravec 工作时受启发于 1988 年提出的。此方法是对Moravec 算法的扩充与完善。为了相对减少噪声的影响我们采取高斯函数，这是因为一阶方向差分对噪声敏感。如果R超过某个阈值，则将该点作为角点。再采用Harris 算法提取图像特征点时。基本能够划分成下面几个阶段：

首先分别计算像素点在x和y方向上的梯度Ix和Iy，再计算每个像素点对应的梯度乘积 即[3]得到自相关矩阵M1，如式(2)所示。

利用高斯核函数G=(x,y,σ)进行高斯滤波，于是有新的自相关矩阵M2。

利用角点响应函数R求解初始图片里一一对应的像素点响应值，即R值。其中角点响应函数R=Det(M2)-k∗Tr(M2)，Det(M2)=λ1λ2，Tr(M2)=λ1+λ2，其中λ1,λ2为自相关矩阵M2的特征值，k为经验值。若是某点的角点响应值R超过预先选好的阈值大小，那么这个点就被选定为特征点[4]。选取局部的极值点：根据给定的阈值，采用非极大值抑制的方法对不符合条件的极值进行置零处理，以确定最终的特征点。

2.3 SIFT特征点检测

1999年，Lowe首次提出关于尺度不变特征变换（SIFT）局部特征。该算法对于旋转，仿射变换和视点变化方面比其他方法更 具有鲁棒性和高效性。SIFT算法在灰度图像特征检测中显示了相当不错的性能。SIFT算法的过程可以简述如下。

阶段1：SIFT在高斯（DoG）标度空间的差异中检测局部极值。输入图像f(x,y)与具有不同尺度kσ的高斯滤波器G(x,y,kσ)卷积以获得尺度空间L(x,y,kσ)，k= 1,2...,ñ。随后，可以通过获得DoG标度空间：

其中D(x,y,σ)是高斯差分图像，G(x,y,σ)是高斯滤波器，L(x,y,σ)是比例空间的比例表示。在DoG空间中，可以使用搜索局部极值的方法判断来尺度和方向不变的潜在兴趣点。当地的极值是第二阶段标记的关键点的候选者。

图1显示了高斯尺度空间金字塔，高斯金字塔在差异里创建了一个区间。为了观察并得到G(x,y,σ)的局部最大值和最小值，把所有的采样点和其图像中的上面八个邻居点和下面九个邻居点相比较。

图1 高斯尺度空间金字塔在差异里创建一个区间

图2 高斯差分图像中的最大值和最小值检测

阶段2：通过选择符合详细定义模型要求的局部极值来定位关键点。在该模型中，在DoG空间的不同尺度上具有高稳定性的候选点被标记为关键点。

阶段3：有关局部图像梯度方向将一种或多种取向分到所有关键点位置。所有做法都是对比于所有特征的指定方位，由比例与位置发生变换的图像数据所处理的，进而给上述变换提供不变性。

阶段4：最终生成关键点描述符。它使用梯度幅度m(x,y)与方向θ(x,y)作为描述符中的基本元素，它们的定义如下：

原算法的描述子因为维数太高，这导致构建特征描述子以及最后进行匹配都需要很长时间。也因为关键点的增加错误匹配概率上升，剔除错误匹配的耗时增加，很难满足对时间的要求。由于关键点的特征描述子不仅与该点所在的像素有关，也和该点周围的像素区域有关，它们对描述子的贡献与距离的大小成正比，因此还要考虑距离的问题，对各个区域与关键点的距离进行加权，得到新的特征描述子[5]。圆形区域比正方形区域含有更少的像素点，剔除了边缘易受干扰的像素点，使得计算梯度描述子的时间有所缩短，相似性加强。

如图3，在圆形部分划分8个小区域用公式（3）、（4）计算每个像素的幅值与幅角。圆形分为8个区域即45度为一个区域。每个像素点根据其幅角判断位置，找到后进行高斯加权并加到相关区域。加权系数为：

图3 新描述子和梯度方向

(i0,j0),(i,j)分别为所求像素点和中心点在待描述图像区域中的坐标，σ0为选定的常数[6]，这样就得到了64维梯度描述子。

3 图像匹配方法

为加快速度，本文对提取的特征点进行构建二维KD树。通过 KD 树搜索邻近点后利用比值提纯法获取粗匹配。再利用RANSAC剔除错误匹配

RANSAC其本身就是依据一组含有非正确数据的样本数据集。RANSAC是为得到正确且有效的数据的方法，其通过计算解得数据本身的模型参数。它于1981年由 Fischler和Bolles最先提出。RANSAC算法的基本假设是样本中包含正确数据，也包含异常数据，即数据集中含有噪声。得到的错误数据有一部分原因是因为测量时出现误差、假设预期相差很多、计算出现错误。给出进行解决所需要正确参考数据，在给出数据时RANSAC则需要假设，这样就是能够找到计算出最适合给出数据的模型参数的算法。

因为是使用一幅图像，那么能够把它定义成刚性的。这样能够在pattern image与query image的不同特征点间寻找其中单应性变换。若是发现能够发现单应性变换，那么就可以运用RANSAC来找到合适的单应性矩阵。这样就可以剔除一部分错误匹配。

4 实验平台搭建

本实验是在Windows 7 系统下以Matlab 2016B作为开发环境，图3为经典的Lena照片，第二张为稍微旋转之图像，图4—图6为几种算法的效果图。图7—图9为另一幅图片几种算法的效果图。表1为几种算法效果数字比较。

图3 Lena照片与稍微旋转片

图4 SIFT检测

图5 SURF检测

图6 本文算法

图7 SIFT检测

图8 SURF检测

图9 本文算法

表1 几种算法效果数字比较

改进后的新算法具有相对不错的鲁棒性，跟SIFT相比，新算法因为角点检测去筛选了边缘信息小的点，信息密集的点则用了改进的SIFT算法。所以可以有效提高准确率，匹配精度。可以更好的完成为三维重建的匹配工作。

5 结论

本文提出的改进算法不仅在低频部分运用了小波变换与角点检测，而且新算法也改变了原描述子，以此来降低维度，提高匹配的实时性。之后实验首先用KD树做粗匹配，再用RANSAC来找到合适的单应性矩阵。这样就可以剔除一部分错误匹配。新算法匹配正确率有了相对不错的提高，这样就能更好地应用在三维重建中去。