基于扩散距离的SURF特征图像匹配算法

贡 超， 蒋建国， 齐美彬

（合肥工业大学 计算机与信息学院，安徽 合肥 230009）

图像匹配在运动跟踪、图像搜索、目标识别、目标定位、运动分析等领域应用广泛［1］。常用的图像匹配方法［2－4］主要有基于区域的匹配方法和基于局部特征点的匹配方法。近年来，以SIFT［5－6］特征点匹配为代表的图像匹配方法成为研究热点，SIFT特征对平移、旋转、尺度缩放、亮度变化、遮挡和噪声等具有良好的不变性，对视角变化、仿射变换也保持一定程度的稳定性，但SIFT特征描述符是一个128维向量，算法计算量大。文献［7］在2006年提出了SURF算法，运算速度大大领先于SIFT，且具有很好的鲁棒性；文献［8］对几种具有代表性的局部特征算法进行了性能评估，SURF算法被证明是综合性能最好的算法。

传统的SURF特征点图像匹配方法采用欧式距离来度量特征向量的差异，然而使用欧氏距离得到的是像素灰度差异的累积，一个较小的图像形变就可能使原来的欧式距离变长，从而导致匹配的误差变大。本文利用扩散距离［9］计算SURF特征描述符向量间的距离；扩散距离将向量之间的差异作为一个温度场，根据温度场热扩散的性质，在欧式距离相等的条件下，相似度大的向量差异下降到0的速度快，将下降过程叠加为距离作为相似度判断的依据。实验表明该方法在图像形变、光照变化和图像噪声方面所得到的匹配比传统SURF算法具有更好的匹配效果。

1 SURF特征算法简介

SIFT算法在特征提取匹配上速度较慢，很难满足实时目标跟踪的要求，使用SURF特征提取方法不仅保持了SIFT算法高精度的优点，而且克服了速度慢的缺陷。

SURF特征提取算法主要包括特征点检测、特征点描述和特征点匹配。基于Hessian矩阵的检测器在特征点检测中的稳定性和可重复性都优于基于Harris的检测器。由于Harr特征速度快，能减少计算时间，因此在特征点描述中采用Haar小波［10］作为特征描述子来增加鲁棒性；同时使用方框滤波近似替代二阶高斯滤波，运用积分图像加速卷积，减少了时间计算的复杂度，提高了计算速度。

2 扩散距离SURF特征匹配

传统的SURF匹配采用选定的特征向量欧式距离作为2帧图像中关键点的相似性判定度量。但是欧氏距离对图像形变比较敏感，缺少考虑像素间的空间关系，较小的形变就能使欧式距离计算变化较大，产生误匹配。本文引入扩散距离代替欧氏距离，对相似性判定度量来克服该缺点。扩散距离根据热扩散的性质，在欧式距离相等的条件下，相似度大的向量差异下降到0的速度快，相似度小的向量差异下降速度缓慢，将下降过程叠加为距离用于SURF匹配的相似度计算，能够更好地将相似性差异大的匹配点区分开来。

2.1 扩散距离

一维分布h1（x）和h2（x）的差异表示为：

扩散距离将2个向量之间的差异看成一个温度场T（x，t），在t＝0时刻，T（x，0）＝d（x）。随着时间的推移，扩散过程整合归一化温度场的差异。温度场的热扩散方程为：

其中

T0（x）＝T（x，0）＝d（x）；

一维分布h1（x）和h2（x）的扩散距离定义为：

其中

其中，↓2为对滤波后的矢量进行1／2降采样，且各分量的值降为原来值的1／2；L为降采样的次数，即热扩散路径数目。

高斯滤波器表达式为：

为了简化计算，用L1范数代替k（），可得：

温度场热扩散下降速度越快，整合归一化温度场差异的值越小，2点之间的相似度就越高，反之，热扩散下降速度越慢，整合归一化的差异值越大，2点之间的相似度越低，从而能把扩散距离应用在相似度比较中。

2.2 特征点匹配

在生成的64维SURF特征描述符中，使用（5）式计算2幅图像关键点特征向量的扩散距离，并作为关键点相似性判定的度量，用来判断向量间点对是否匹配。

对于目标中的某个特征点，采用近似最邻近查找算法BBF（best bin first）从基准影像上找到与之匹配的具有最近扩散距离和次最近扩散距离的匹配点对，用最近扩散距离与次最近扩散距离的比值作为阈值（一般为0.3～0.8），删除比值大于设定阈值的特征点对，从而确定关键点的匹配。设定阈值越小，匹配结果越可靠，获得的匹配点对越可靠。特征点匹配后仍会存在一定比例的误匹配，通过RANSAC（随机抽样一致算法）剔除误匹配，在相似度高的样本中得到最佳模型参数，估计正确匹配点对。

3 实验结果和分析

实验图片是从文献［11］的图像库中选取的32幅图片，如图1所示。

图1中图片A、B是同一目标在光照、形变以及尺度有差异时的2组图片。

图1 数据库中的2组对比图片

在一台处理器为2.0GIntel Pentium 4Processor、编程环境为 Matlab 2010b＋VS 2008的PC机上进行编程实验。表1～表3分别为基于扩散距离的SURF算法［12］、基于马氏距离的SURF算法和基于欧式距离的SURF算法的实验结果。

在3个表中，对角线上的值是相同目标所对应的2幅图片的匹配特征点个数，其余是不同目标的图片匹配的特征点个数。可以看出，大多数情况下，3个表中对角线元素的值都是各行和各列的最大值，即3种方法大多数情况下都能实现正确匹配，但是前2种方法也存在一些错误匹配情况。如在表1中，A5与B2、B3、B10的匹配点数分别为65、46、46，大于 A5与 B5的匹配点数41，也就是说，按照欧式距离匹配，就会将A5与B2判为同一目标，导致错误匹配。同样的问题在马氏距离的SURF匹配中同样存在，如在表2中，A13与B0、B1、B2、B3、B5、B6、B10、B15的匹配点数也大于A13与B13的匹配点数，B13与 A1、A3、A6、A11、A12的匹配点数也大于B13与A13的匹配点数，这样就导致A13、B13都不能实现准确匹配。而在表3中，对角线中所有数据在对应的行和列中全部都是最大值，都能实现正确匹配。

另外，从表中还可以看出，欧氏距离SURF算法和马氏距离SURF算法存在大量的误匹配点，而扩散距离SURF算法的误匹配点数目大大减少，甚至全部消除。

表1 基于欧式距离匹配的特征点数目

表2 基于马氏距离匹配的特征点数目

表3 基于扩散距离匹配的特征点数目

图2～图5所示为部分对比实验结果。

图2 原始图像

图3 图像一的3种SURF方法对比实验

图4 图像二的3种SURF方法对比实验

由图2可以看出，2组图像对应的是2幅同一目标的图片，但是在每组不同的图像中存在明显的变形和光照变化。图3a、图4a和图5a是使用欧式距离SURF算法进行匹配的结果，图3b、图4b和图5b是使用马氏距离SURF算法进行匹配的结果，由于欧氏距离和马氏距离计算的仅仅是像素灰度之间差异的累加，一个较小的形变或者光照变化就能使欧式距离或马氏距离变化很大，如图5a和图5b2个明显不同的图片中仍然得到很多错误的匹配点，而扩散距离很好地解决了这一问题。从图5c中可以看出，SURF在图像形变和光照变化较大的情况下，消除了2个不同图片的错误匹配点对，只有1个错误匹配点存在，得到了更加准确的匹配结果。

图5 本文方法与马氏距离、欧氏距离SURF方法的对比实验

4 结束语

本文针对原始SURF算法对于形变或者光线变化较大的图像不能进行有效匹配的缺陷，提出了使用扩散距离改进的SURF算法。通过针对不同视角、旋转、光照、缩放变换进行的实验证明，本文算法克服了原始SURF算法的缺点，大大提高了SURF算法匹配的精度。

［1］ 高 明，曹 洋，方 帅.序列全景图像的特征提取与匹配［J］.合肥工业大学学报：自然科学版，2009，32（4）：449－452，460.

［2］ Mikolajczyk K，Schmid C.An affine invariant interest point detector［M］.Computer Vision－ECCV 2002.Berlin：Springer，2002：128－142.

［3］ Mikolajczyk K，Schmid C.Scale ＆ affine invariant interest point detectors［J］.International Journal of Computer Vision，2004，60（1）：63－86.

［4］ Matas J，Chum O，Urban M，et al.Robust wide－baseline stereo from maximally stable extremal regions［J］.Image and Vision Computing，2004，22（10）：761－767.

［5］ Lowe D G.Object recognition from local scale－invariant features［C］／／The Proceedings of the Seventh IEEE International Conference on Computer Vision，1999：1150－1157.

［6］ Lowe D G.Distinctive image features from scale－invariant keypoints［J］.International Journal of Computer Vision，2004，60（2）：91－110.

［7］ Bay H，Tuytelaars T，Van Gool L.Surf：speeded up robust features［M］.Computer Vision－ECCV 2006.Berlin：Springer，2006：404－417.

［8］ Mikolajczyk K，Schmid C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615－1630.

［9］ Ling H，Okada K.Diffusion distance for histogram comparison［C］／／IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2006：246－253.

［10］ Khashman A，Dimililer K.Image compression using neural networks and haar wavelet［J］.WSEAS Transactions on Signal Processing，2008，4（5）：330－339.

［11］ Ling H B.Image DataSet［EB／OL］.http：／／www.dabi.temple.edu／hbling／data／RD－cvpr06.zip，http：／／www.dabi.temple.edu／hbling／data／SD－cvpr06.zip.

［12］ 赵璐璐，耿国华，李 康，等.基于SURF和快速近似最近邻搜索的图像匹配算法［J］.计算机应用研究，2013，30（3）：921－923.