基于SURF特征提取和FLANN搜索的图像匹配算法

冯亦东， 孙 跃

(温州大学城市学院，浙江 温州 325000)

基于SURF特征提取和FLANN搜索的图像匹配算法

冯亦东， 孙 跃

(温州大学城市学院，浙江 温州 325000)

针对传统图像匹配算法存在特征信息少和误匹配率高的问题，提出基于SURF特征提取和FLANN搜索的图像匹配算法。通过Hessian矩阵获取图像局部最值，并使用不同尺寸特征描述器，同时处理尺度空间多层图像的向量特征，最后采用FLANN搜索算法进行特征匹配。试验表明，该算法比传统的图像匹配算法在效果和效率方面都表现得更好。

加速鲁棒特征；Hessian；FLANN；图像匹配

图像匹配即通过一定的匹配算法在两幅或多幅影像之间识别同名点的过程。图像特征提取与匹配一直是计算机视觉中的一个关键问题，在目标检测、物体识别、三维重建、图像配准、图像理解等具体应用中发挥着重要作用[1]。由于图像的成像条件和所记录的内容复杂多样，而且应用需求各有不同，对图像特征提取和图像匹配的研究一直都是视觉领域中一个极具挑战性的问题。

文献[2-5]提出了采用小波变换来实现图像的快速匹配，其具有良好的时频局部化、多分辨分析和抑制高频噪声的优点，但图像在特征提取方面受选取的小波基影响较大。1988年 Harris和Stephens[6]提出Harris角点检测特征匹配算法，是一种直接基于灰度图像的角点提取，稳定性高，对 L型的角点检测敏感，但是运算速度较慢，存在角点信息丢失和位置偏移和聚簇现象。在此基

础上，文献[7-9]对 Harris匹配算法进行了改进，但是无法适应图像尺度变化的问题。Lowe[7]在2004年提出尺度不变特征(scale invariant feature transform，SIFT)算法，即在尺度空间寻找极值点，提取位置、尺度、旋转不变特征量。SIFT算法通过采用金字塔分层方式，大幅降低了计算量，并提取出了图像中大量的特征点，但是由于SIFT算法没有考虑空间的几何约束信息，因而导致误匹配率高，易出现明显的错配和乱配情况。2006年Bay等[10]提出加速鲁棒特征(speed up robust features，SURF)提取算法。SURF特征由SIFT特征改进而来，通过Harris特征和积分图像(integral image)相结合，大大加快了程序的运行速度，在图像尺度和仿射变换下都可以保持不变性，在多幅图片下具有更好的鲁棒性，同时也存在误匹配率高的问题。文献[11-12]结合其他算法对SURF进行进一步改进，取得了不错的效果。

基于上述研究，本文提出了基于SURF特征提取和快速近似最近邻查找(fast library for approximate nearest neighbors, FLANN)搜索的图像匹配算法。利用SURF算法中的Hessian矩阵来提取图像中的局部最大值，采用不同尺寸的框式滤波器，同时处理尺度空间多层图像获取特征矢量，最后采用 FLANN中 KD-TREE快速搜索匹配SURF特征矢量。该算法不仅对两幅图像之间局部特征、平移、旋转、尺度缩放、亮度变化、遮挡和噪声等具有良好地匹配适应能力，而且速度也相对较快。

1 SURF特征提取算法

1.1 Hessian矩阵

Hessian矩阵是SURF算法的核心，其行列式的局部最大值可以确定特征点的位置和尺度[13]。SURF算法通过Hessian矩阵求极值点来获取稳定点，用矩阵行列式的最大值来标记块状特征结构(blob-like structure)的位置。

假设函数 f(x,y)，Hessian矩阵H是由函数偏导数组成，可以表示为式(1)：

Hessian矩阵判别式为：

式(2)中，d (H )是H矩阵的特征值，可以利用判定结果的符号将所有点进行分类，根据判别式取正负，判别该点是否为极值点。在SURF算法中，用图像像素 X(x,y)代替函数值 f(x,y)，选用二阶标准高斯函数作为滤波器，通过特定核间的卷积计算二阶偏导数，这样便能计算出在尺度σ下的H矩阵的 3个矩阵元素 L xx (X,σ), L yy(X,σ) , L xy(X,σ)从而计算出H矩阵，如式(3)、(4)：

其中， g(t)为高斯函数，t为高斯方差。 L xx(X,σ)是高斯二阶导数与图像I在X点处的卷积。 L xy (x,σ)， L yy(x,σ)同样也是高斯滤波后图像在y和xy方向上的二阶偏导数和二维图像的卷积。

通过计算得到图像中每个像素其H行列式的决定值，并用此值来判别特征点。根据 Lowe[14]成功地用高斯差分(difference of Gaussian，DoG)算法近似拉普拉斯高斯算子(Laplacian of Gaussian，LoG)的经验，Bay等[10]提出采用框式滤波器来代替L在x、y、xy三个方向的近似值，分别记为 Dx x、 Dy y和 D xy。为平衡准确值与近似值间的误差引入权值，则 H矩阵判别式的近似计算可表示为式(5)：

其中，w为权重系数，其值与尺度σ相关，主要是为平衡准确值与近似值之间的误差，在实际的应用中，通常取0.9。

1.2 SURF尺度空间及特征提取

图像的尺度空间是一幅图像在不同解析度下的表示，可以利用高斯核的卷积来实现，图像的尺度大小一般用高斯标准差来表示[15]。在计算视觉领域，尺度空间需要对输入图像函数反复与高斯函数的核卷积并反复对其进行二次抽样，被象征性地表述为一个图像金字塔。SURF算

法采用不同尺寸的框式滤波器进行处理，允许尺度空间多层图像同时被处理，只改变滤波器大小不需要进行二次采样，从而提高算法性能。图1(a)是传统方式建立金字塔结构，滤波器尺寸不变，图像的尺寸随尺度变化，需要反复使用高斯函数对子层进行平滑处理；图1(b) SURF算法保持原始图像不变而只改变滤波器大小。

SURF特征提取利用了插值技术在亚像素精度上寻找空间和尺寸的位置，可通过 Brown和Lowe[16]提出的三维二次方程得到。假设 Hessian的行列式函数记为 H(x,y,s)，并且 x = (x,y,s)T，根据泰勒展开式可以得到：

其函数导数可以利用相邻像素间的差异来近似得到。如果xˆ在x、y、σ三个方向中的值大于0.5，则需要调整特征点的位置并再次实用插值算法，直到在所有方向上xˆ小于0.5或者预先设定的插值算法使用次数溢出。图2为使用Hessian矩阵获取特征点的效果，其中圆圈点表示被检测出的特征点位置，共检测出32个特征点。

图2 SURF特征检测

2 Flann特征紧邻像素匹配

Muja和Lowe[17]于2009年提出FLANN算法，该方法基于K均值树或KD-TREE搜索操作所实现的，可以根据数据集的分布特点、对映射精度和空间资源消耗的要求来推荐索引类型和检索参数，在高维空间最近邻查找不受局部敏感哈希[18]影响。FLANN算法模型的特征空间一般是n维实数向量空间 Rn，核心在于使用欧式距离找到实例点的邻居。特征点p和q的特征分向量可记为 Dp和 D q，则 d(p,q)的欧氏距离可以表示为式(8)：

本文通过 KD-TREE将数据点在n维空间 Rn划分为特定的几个部分，其目的是检索在KD-TREE中与查询点距离最近的欧氏距离[19]。图3中所标的A～J表示被搜索范围中的点，将图3(a)中被搜索区域按一定规则分割后，就可以建立图3(b)所示的树型结构。

向量空间 Rn中所有欧氏距离 d(p,q)通过KD-TREE结构存储后，便可以有效搜索与参考点距离最邻近的点。整个搜索过程是KD-TREE由上至下的递归过程。首先以某一特定维数为基准将目标点和分割点的值进行比较，判别目标点是在左区域还是右区域；然后循环和对应节点进行比较，直到目标搜索成功为止。

3 试验分析

本 次 实 验 以 Visual studio 2010 和OPenCV2.4.6为开发平台，在PIV 2.4 GHz，1 GB内存的微机上实现。测试图像图4(a)为223×324大小灰度图像，测试图像图4(b)为512×384灰度图像。

图3 KD-TREE结构

图 4为两幅测试图像分别采用不同方法进行特征提取和匹配的试验，图 4(a)、(b)是测试图像采用SIFT算法提取图像的特征；图4(c)为对SIFT提取的图像特征采用Flann匹配后得出的结果；图4(d)、(e)是本文采用的SURF特征提取算法获得的试验结果，图4(f)是对SURF算法提取的特征进行Flann匹配后得出的效果。从视觉效果上来分析，图 4(a)、(b)和图 4(d)、(e)都不同程度地提取了两幅图像的特征信息，但本文SURF提取出来的特征信息点更多，表达的信息量也更丰富。图4(c)和(f)对特征信息进行Flann快速匹配后的效果，从匹配速度和成功率来看也比较理想。

本文统计了SIFT算法和SURF算法的特征点个数、匹配点数、匹配成功率和运行时间 4个指标，并对两种不同的算法进行了质量评价。特征点个数反映了算法特征提取能力，特征点越多，表明图像细节信息更丰富；匹配点数量和匹配成功率反映图像匹配的质量，值越高，效果越理想；运行时间体现了算法的效率。从表1中可以看到，本文提出的 SURF算法的特征点个数和匹配点数更多，匹配成功率也较高，并且运行时间更短。

图4 SIFT 和SURF特征匹配对比

表2是图4(c)和图4(f)通过FLANN匹配算法对前面特征向量进行的KD-TREE搜索对比分析，从数据中可以看到，图4(f)SURF算法的邻近标准

差值比较大，说明该算法提取的特征细节表达较SIFT更为明显；由于图 4(f)特征点数量较多，所以KD-TREE搜索算法用时较图4(c)长0.03 s。

表1 SIFT和SURF特征匹配数据对比

表2 Flann匹配分析

4 总 结

本文针对目前图像特征匹配算法中存在图像提取特征量少、特征误匹配率高和匹配速度慢的问题，提出基于SURF特征提取和FLANN搜索的图像匹配算法。利用SURF算法提取大量的图像特征信息，同时采用FLANN的KD-TREE搜索相似的特征矢量，在不影响图像匹配速度的前提下，提高特征匹配率准确率。实验结果表明，本文提出的算法在匹配的效果、稳定性和速度方面表现更好。

[1] 谭博怡. 图像特征提取与匹配[D]. 北京: 中国科学院研究生院, 2008.

[2] 洪小伟, 石守东, 康 丹. 一种基于小波模极大值的图像特征匹配算法[J]. 宁波大学学报, 2009, 22(1): 66-69.

[3] 范新南, 朱佳媛. 基于小波变换的快速图像匹配算法与实现[J]. 计算机工程与设计, 2009, 30(20): 1674-1676.

[4] 郭丰俊, 杨 新, 施鹏飞. 基于小波变换的多尺度图像匹配算法[J]. 红外与激光工程, 1999, 28(4): 30-33.

[5] 王俊卿, 黄沙白, 史泽林. 基于复数小波能量特征和支持向量机的图像匹配算法[J]. 中国图象图形学报, 2004, 9(9): 1075-1079.

[6] Harris C, Stephens M. A combined corner and edge detector [C]//Manchester: Proceedings of the 4th Alvey Vision Conference. Manchester, UK, 1988: 147-151.

[7] Lowe D G. Distinctive image features form scale-invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[8] 魏志强, 黄 磊, 纪筱鹏. 基于点特征的序列图像匹配方法研究[J]. 中国图象图形学报, 2009, 14(3): 525-530.

[9] 邱建国, 张建国, 李 凯. 基于Harris与SIFT的图像匹配方法[J]. 测试技术学报, 2009, 23(3): 271-274.

[10] Bay H, Tuytelaars T, Van Gool L. SURF: speeded up robust features [C]//Proceedings of European Conference on Computer Vision. Graz, Austria, 2006: 404-407.

[11] 顾大龙, 曾 峦, 翟 优. 基于 SURF的图像匹配算法改进[J]. 现代电子技术, 2012, 35(14): 79-82.

[12] 赵璐璐, 耿国华, 李 康, 等. 基于SURF和快速近似最近邻搜索的图像匹配算法[J]. 计算机应用研究, 2013, 30(3): 921-923.

[13] 时 磊, 谢晓方, 乔勇军. 基于SURF算法和OPenCV的人脸特征检测技术研究[J]. 计算机与数字工程, 2010, 38(2): 124-126.

[14] Lowe D G. Object recognition from local scale-invariant features [C]//International Conference on Computer Vision. Corfu, Greece, 1999: 1150-1157.

[15] 高 健, 黄心汉, 彭 刚, 等. 一种简化的 SIFT图像特征点提取算法[J]. 计算机应用研究, 2008, 25(7): 2213-2215.

[16] Brown M, Lowe D. Invariant features from interest point groups [C]//British Machine Vision Conference. Cardiff, Wales, 2002: 656-665.

[17] Muja M, Lowe D G. Fast approximate nearest neighbors with automatic algorithm configuration [C]//Proceedings of IEEE Conference on Computer Vision Theory and Applications. Lisbon, Portugal: IEEE Computer Society, 2009: 331-340.

[18] Chum O, Philbin J, Zisserman A. Near duplicate image detection: min-hash and tf-idf weighting [C]// Proceedings of the 19th British Machine Vision Conference. London, UK, 2008: 493-502.

[19] 刘树勇, 杨超庆, 位秀雷, 等. 邻近点快速搜索方法在混沌识别中的应用[J]. 华中科技大学学报, 2012, 40(11): 89-92.

Image Matching Algorithm Based on SURF Feature Extraction and FLANN Search

Feng Yidong, Sun Yue
(City College of Wenzhou University, Wenzhou Zhejiang 325000, China)

The traditional algorithm of image matching exist the problems of little feature information and high rate false match. An image matching algorithm is presented based on SURF feature extraction and FLANN search. Firstly, the extremum value of local image is gotten using the Hessian matrix. Secondly, the feature vector is simultaneously processed in multilayer image scale space by using of different size feature description. Finally, the FLANN algorithm is used for feature matching. The experiments show that this algorithm is better than the traditional algorithm of image matching in the aspect of effectiveness and efficiency.

speed up robust features; Hessian; FLANN; image matching

TP 391.4

A

2095-302X(2015)04-0650-05

2014-10-30；定稿日期：2015-03-10

冯亦东(1986–)，女，浙江苍南人，助理实验师，硕士。主要研究方向为图像处理。E-mail：graceyidong@163.com

通讯简介：孙 跃(1961–)，男，浙江苍南人，副教授，学士。主要研究方向为图像处理和模式识别、可视化技术。E-mail：1053231712@qq.com