一种基于SURF的图像特征点快速匹配算法

陈小丹，杜宇人，高秀斌

（扬州大学 信息工程学院，江苏 扬州225127）

基于特征点的图像匹配［1］因具有计算量小、适应能力强和匹配精度高的特点而得到了广泛应用．目前，比较常用的特征点检测方法有Harris角点检测方法［2］和SIFT（scale－invariant featrue transform）图像特征点算法［3］．Harris角点检测法尺度可变且抗噪声能力较差，而SIFT 算法则具有良好的尺度、光照、空间旋转不变性，普遍应用于图像匹配领域［4－5］．然而，SIFT 算法也存在不足之处：①特征向量的维数高达128维，匹配时计算数据量大、耗时长；②使用的是图像灰度信息，忽略了彩色信息，故图像信息未能得到充分利用．针对上述缺陷，文献［6－7］在特征描述及匹配阶段进行了改进，但没有改变算法本身．BAY［8］，熊智［9］等提出的SURF（speeded up robust features）图像特征点算法可广泛应用于实时性要求高的物体识别、图像拼接等方面．为此，本文采用了一种基于SURF的图像特征点匹配算法，故在满足匹配精度要求的同时具有较快的匹配速度．

1 SURF特征点检测及特征描述

SURF算法是对SIFT 算法的改进．SIFT 算法中用差分高斯金字塔（DOG）代替高斯金字塔（LOG）来提高算法性能；SURF算法中用方框滤波近似代替高斯滤波，用积分图像加速卷积提高运算速度，以较小的精度损失获得更快的特征点检测速度．

1．1 特征点检测

SURF算法对特征点的检测基于Hessian矩阵．对于图像中的某一点p＝（x，y）以及高斯滤波器的尺度σ，其Hessian矩阵H（p，σ）表达式如下：

其中Lxx（p，σ），Lxy（p，σ），Lyy（p，σ）是图像中p 点与高斯二阶偏导数的卷积．Hessian矩阵的行列式为

实际运算中由于高斯滤波器须离散化，故随着尺度σ的增大图像细节逐渐被过滤．采用SURF 算法以方框滤波（box filter）近似代替高斯二阶导数，用积分图像加速卷积后式（2）的近似表达式为

其中Dxx，Dxy，Dyy是图像中p 点与方框滤波的卷积．

为了在不同尺度上寻找特征点，须建立图像的尺度空间．SIFT 算法中构造尺度空间是对原图不断进行高斯平滑和降采样，计算图像金字塔中相邻尺度空间函数的差值得到DOG 尺度空间，此过程中高斯滤波器的大小不变，改变的是图像大小．SURF算法中，图像大小保持不变，改变滤波器大小，利用积分图像快速计算大大提高了效率，且由于未对图像进行降采样而不存在混叠现象．在3维（x，y，σ）空间中，每个3×3×3的区域内进行非极大值抑制．选取比相邻的26个点的响应值都大的点为特征点，即可得到稳定的SURF特征点位置及其所在的尺度值．

1．2 特征描述

以每一个特征点为圆心、6σ为半径的圆形区域计算x 和y 方向的Haar小波（Haar小波边长取4σ）响应，继而以特征点为中心对这些响应进行高斯加权．采用1个π／3的扇形区域的滑动窗口，计算窗口内x 和y 方向的响应总和，得到1个局部的方向向量．转动扇形遍历整个圆，选择最长的向量方向作为特征点的主方向．

以特征点为中心，首先将坐标轴旋转到主方向，按主方向选取边长为20σ的正方形区域，将该区域划分成4×4个子区域；对每个子区域计算25个空间归一化采样点的Haar小波响应．假设dx和dy分别表示水平与垂直（相对于特征点的方向）方向上的Haar小波响应，为了增强鲁棒性，可对dx和dy进行高斯滤波，以滤波器中心为特征点，在每一子区域对dx，dy，｜dx｜，｜dy｜求和，得到1个4维向量所有子区域的向量构成该点的特征向量，长度为64，对其归一化所得的特征向量具有旋转、尺度和光照不变性．

2 特征点匹配

获取SURF特征向量后即可进行特征点匹配．采用最近邻搜索算法（best bin first，BBF）在欧式空间搜索查找每个特征点的2个最近邻特征点．在这2个特征点中，如果最近距离与次近距离的比值小于某个比例阈值（本试验中取0．7），则接受这对匹配点．

为了加速匹配点的搜索过程，笔者采用优化的BBF算法，有效减少了计算量，加速了匹配进程．在计算Hessian矩阵行列式的同时计算出Hessian矩阵迹t，判断t符号，若大于0，则对描述子赋值1；若小于0，则对描述子赋值－1．将每幅图像的特征点按描述子的值分成2组，对相同类型数据进行比较，如果2个描述子的值不同即表示不匹配，则无须继续比较．

针对特征点匹配得到的匹配点中存在误匹配问题，利用随机抽样一致性算法（RANSAC）［10］将匹配质量较差的点作为外点去除，然后在程序中设定选取相似度最高的前n 对匹配特征点，通过对n赋值来满足匹配精度的要求．

3 实验结果及分析

本文实验环境为Pentium（R）Dual－Core CPU，2Gb内存．采用标准测试图像Lena图为实验图，对Lena图分别采用SIFT 和SURF算法提取特征点（图1）．为了测试SURF特征点的性能，本文从平移、旋转及抗噪性3个方面进行了研究，部分结果如图2所示．实验结果表明，当图像进行平移或旋转变换时特征点性能好，且抗噪声能力强．

为了验证SURF算法的时效性，分别采用SIFT 和SURF 算法对同一组图像进行特征点提取，并统计出所提取特征点的个数及特征点检测消耗的时间，结果如表1所示．通过对比可知，SURF算法提取特征点效率高，且能满足精度要求．

表2给出对一组图像进行SURF特征点提取后分别采用BBF算法和本文算法进行特征点匹配的时间比较．由表2可见，基于SUFR 的匹配算法进行图像特征点提取和匹配时比传统的算法速度更快，因此有利于进行实时的物体识别或图像拼接．

图1 SIFT和SURF算法的特征点提取图Fig．1 Feature points extraction fig of Lena image using SIFT and SURF algorithm

图2 图像变换后的特征点提取图组Fig．2 Feature points extraction after image transformation

图3 不同角度拍摄的SURF匹配结果图Fig．3 SURF matching result of images under different shooting angle

表1 2种算法的特征点检测时间及特征点数比较Tab．1 The comparision of feature point detection time required by the two algorithms

4 结论

本文首先采用SURF算法提取特征点形成特征向量，然后用优化的BBF算法进行特征点匹配，通过RANSAC算法去除误匹配点，最后接受相似度最高的前n 对匹配对．实验验证了该算法的有效性，当图像存在平移、旋转、噪声影响时具有较好的鲁棒性．然而，在图像采集过程中由于光照、相机抖动、场景运动等因素，图像的纹理信息有所减少，加大了匹配难度，今后将对算法作进一步的研究和改善，以提高其鲁棒性．

表2 特征点匹配时间比较Tab．2 The comparision of feature point match time required by the two algorithms

［1］ SCHMID C，MOHR R，BAUCKHAGE C．Evaluation of interest point detectors［J］．Int J Comput Vision，2000，37（2）：151－172．

［2］ 周爱军，杜宇人．基于视频图像Harris角点检测的车型识别［J］．扬州大学学报：自然科学版，2008，11（1）：67－70．

［3］ LOWE D G．Distinctive image features from scale－invariant keypoints［J］．Int J Comput Vision，2004，60（2）：91－110．

［4］ MIKOLAJCZYK K，SCHMID C．A performance evaluation of local descriptors［J］．IEEE Trans Pattern Anal Mach Intell，2005，27（10）：1615－1630．

［5］ BASTANLAR Y，TEMIZEL A，YARDIMCI Y．Improved SIFT matching for image pairs with scale difference［J］．Electron Lett，2010，46（5）：346－348．

［6］ YAN K，SUKTHANKAR R．PCA－SIFT：a more distinctive representation for local image descriptors［C］／／Proceedings of the 2004IEEE Computer Society Conference on Computer Vision and Pattren Recognition．Washington，DC，USA：IEEE，2004，2：506－513．

［7］ DELPONTE E，ISGRÒ F，ODONE F，et al．SVD－matching using SIFT features［J］．Graph Models，2006，68（5／6）：415－431．

［8］ BAY H，TUYTELAARS T，VAN GOOL L．SURF：speeded up robust features［J］．Comput Vision Im Understanding，2008，110（3）：346－359．

［9］ 熊智，陈方，王丹，等．SAR／INS组合导航系统中基于SURF的鲁棒景象匹配算法［J］．南京航空航天大学学报，2011，43（1）：49－54．

［10］ 杨敏，沈春林．基本矩阵随机采样鲁棒估计［J］．应用科学学报，2004，22（2）：178－182．