基于SURF 算子与FLANN 搜索的图像匹配方法研究

徐明，刁燕

（四川大学机械工程学院，成都610065）

0 引言

图像匹配是指在两幅或者多幅图像中通过一定的算法找到相似影像的方法[1]。在数字图像处理的研究过程中，图像的特征提取以及图像匹配一直是一个关键问题，在图像配准、目标检测、模式识别、计算机视觉等领域发挥着至关重要的作用[2]。

1998 年，Harris 和Stephens 在工作的启发下提出Harris 角点检测算法[3]，是对Moravec 算法的扩充和完善。通过分别计算像素点在x 和y 方向上的梯度，利用高斯核函数对图像进行高斯滤波，然后根据角点响应函数计算原图像上对应的每个像素点的响应值，最后通过给定的阈值选取局部极值点来确定图像的特征点。Harris 算法是直接通过灰度图像然后进行角点提取，该算法适用于L 型的角点检测，稳定性好，但是容易出现角点信息丢失和角点的位置偏移以及聚簇现象，运行速度也比较慢。

2004 年，Lowe 发表了尺度不变特征（Scale Invariant Feature Transform，SIFT）算法[4]，通过构建高斯尺度空间，寻找极值点，剔除不稳定特征点，确定关键点方向和生成特征点描述子来提取图像的特征点。

SIFT 算法引入图像金字塔结构，在不影响提取图像中大量特征点的基础下，降低了计算量，但是SIFT算法没有考虑到空间中的几何约束信息，造成了误匹配率高，而且还容易出现特别明显的乱配和错配现象。

2006 年，Bay 对SIFT 算子进行了改进，提出了加速鲁棒特征（Speeded Up Robust Feature，SURF）算法[5]，该算法通过构建Hessian 矩阵，建立尺度空间，定位特征点，确定特征点主方向，最后生成特征点描述子来得到特征点。SURF 算法引入积分图像并且与Harris 特征相结合，在图像尺度和仿射变换都可以保持不变性的条件下，更好地提高了程序的运算速度，同时在多幅图片中也具备良好的鲁棒性，但误匹配率高仍然存在。

通过对上述方法的研究，本文提出了基于加速鲁棒特征（Speed Up Robust Feature，SURF）算法与快速近似最近邻查找（Fast Library for Approximate Nearest Neighbors，FLANN）搜索的图像匹配方法。首先采用Hessian 矩阵来获知图像的局部最值，然后在图像上构建尺度空间，通过不同的尺度空间定位出特征点，并确立特征点的主方向，再生成特征点描述子，最后结合FLANN 搜索算法对图像进行匹配。实验表明，该算法相对传统的图像匹配方法提高了准确度和匹配效果。

1 SURF算子原理

1.1 特征点检测

首先需要在一幅图像上构建Hessian 矩阵，然后通过Hessian 矩阵得到图像上稳定的边缘点，为接下来的特征提取奠定基础。若一幅图像为f（x,y），则此图像的上某个像素点的Hessian 矩阵可如下表示：

由于求出的特征点需要具有尺度无关性，则在构建Hessian 矩阵之前需要对处理图像进行高斯滤波，经过高斯滤波后得到的Hessian 矩阵为：

为了提高运算速度，Bay 提出采用盒子滤波器，然后使用Dxx、Dxy和Dyy来替换Hessian 矩阵中的Lxy、Lxy、Lyy，则Hessian 矩阵判别式可以简化为：

其中w 为通用系数，在实际应用中不断总结经验得到该值近似为0.9。

当Hessian 矩阵判别式取得局部极大值时，可以判断该点比周围邻域内的其他点更亮或者更暗，从而定位出兴趣点的位置。

1.2 构建尺度空间

构建尺度空间，顾名思义，是指在不同的维度上对图像进行特征检测，现在常用的方法是通过建立图像金字塔，然后通过图像金字塔来对图像进行多维度描述。在SIFT 算法中，首先通过对目标图像进行下采样得到多幅图像，然后通过生成的高斯金字塔中同组图像中上一层图像减去下一层图像，从而获得差分图像，改变了原始图像的大小，该方法运算慢，效率低。而在SURF 算法中，不改变目标图像的大小，根据提出的盒式滤波器，在改变盒式滤波器的模板尺寸大小从而获得图像金字塔，该方法运算速度快，提高了效率，如图1所示。

图1 金字塔结构

1.3 特征点定位

在得到兴趣点的位置和建立图像金字塔之后，需要在兴趣点中定位出特征点。首先需要选择合适的阈值，在兴趣点当中保留响应最强烈的点，选取的阈值越大，则保留下来的特征点越多。然后根据非极大值抑制，将得到的点与尺度空间中周围邻域的8 个像素点相比较，再与上次两层的尺度空间的各9 个像素点进行比较，总共是26 个像素点，不包括图像金字塔的第一层和最后一层，如图2 所示。最后对选出的关键点进行三次线性插值计算，可以得到稳定的特征点。

图2 特征点定位

1.4 选取特征点主方向

为了确保图像具有旋转不变形，需要给每一个特征点选择一个主方向，在SURF 算法中，是通过Haar小波特征来确定。以特征点为中心，取半径为6s 的绘制一个圆形，在圆形区域内取一个60°扇形，计算在60°扇形范围内的Harr 小波特征，形成一个新的矢量，然后再转动扇形直到所有的圆形区域被覆盖，最后在整个圆形区域内选取一条最长的新的矢量作为此特征点的主方向，如图3 所示。

图3 特征点主方向求取过程

1.5 生成特征描述子

计算出特征点的位置以及选取出特征点的主方向，最后一步就是在局部区域内生成特征描述子。在SURF 算法中，以特征点为中心，在特征点附近选取4×4 个矩形区域，计算每个区域内的Harr 小波响应值。由于每个子区域含有4 个特征向量，故SURF 特征向量共有4×4×4 即64 维特征向量来表示每一个特征点。

2 FLANN搜索

FLANN 算法是在2009 年由Muja 和Lowe[6-7]提出的，主要是根据KD-TREE 操作或者是K 均值树实现，由已知的数据集的分布特点以及所要求的空间资源消耗来给出有效的搜索类型和检索参数。FLANN 算法要求的特征空间通常是n 维实数向量空间Rn，此算法的关键点是根据欧氏距离寻找在实例点附近邻域最邻近的点，欧氏距离的数学定义式如下所示。

如果得到的D 值越小，就说明所存在的特征点对之间的距离就很“近”，也就是图像中的特征点对的相似程度就越高。

本方法将n 维空间Rn中的数据点根据KD-TREE方法分成几个特定的区域，其作用是在查询点邻域范围内检索出与其查询点最近的欧氏距离[8]。

在n 维空间Rn中，通过KD-TREE 这种结构存储所有的欧氏距离，就可以很方便而且更行之有效地查找与参考点最邻近的点。KD-TREE 结构的搜索过程是由上而下进行递归。首先根据特定的基准将目标点与分割点分离开，然后将它们进行比较，判断目标点是在基准点左边还是右边；逐一与对应点进行循环比较，直到目标点被成功搜索。

3 实验结果分析

根据上述提出的算法，本次实验以SURF 算法与SURF+FLANN 算法作对比，在Windows 10 上运行，使用到Visual Studio 2015 和OpenCV3.4，通过Mikolajazyk[9]数据集进行验证。

第一组实验取自Mikolajazyk 数据集中的bark 的两幅图像，图4 为原始输入的图像，图5 为采用SURF算法进行特征点检测并进行特征匹配后的实验结果，图6 为采用SURF+FLANN 算法进行特征点检测并进行特征匹配后的实验结果。

图4 原始输入图像

图5 SURF特征匹配

图6 SURF+FLANN特征匹配

第二组实验取自Mikolajazyk 数据集中的tree 的两幅图像，图7 为原始输入的图像，图8 为采用SURF 算法进行特征点检测并进行特征匹配后的实验结果，图9为采用SURF+FLANN 算法进行特征点检测并进行特征匹配后的实验结果。

图7 原始输入图像

图8 SURF特征匹配

图9 SURF+FLANN特征匹配

本文分别统计了在SURF 算法与SURF+FLANN算法下，左图特征点数量、右图特征点数量、两幅图像之间的匹配点数量以及正确匹配点数量的四个指标，并计算出匹配正确率，统计结果如表1 所示。

表1 SURF 与SURF+FLANN 特征匹配数据对比

在表1 中可以看出，在相同的实验条件下，SURF+FLANN 算法提取的特征点以及两幅图像之间的匹配点数量虽然不如SURF 算法多，但是两幅图像之间的正确匹配点数量以及匹配的正确率要比SURF 算法高，说明SURF+FLANN 算法能够更准确地提取出匹配点，具有较强的匹配能力，匹配出的效果也更佳，也能够更丰富地表现出两幅图像的细节信息以及相似程度。

4 结语

本文针对传统的图像匹配算法中存在的误匹配率高和匹配效果不佳的问题，提出了基于SURF 算法与FLANN 搜索的图像匹配方法。利用SURF 算法对图像提取大量有效的特征信息，同时结合FLANN 搜索算法，在不影响匹配准确率的前提下，提高了图像匹配的效果。由实验结果可知，本文提出的算法在图像匹配效果以及准确率方面都要表现地更好。