一种改进的基于SURF的视频帧间匹配方法

武 频，王 庆，朱永华，高洪皓

(1.上海大学 计算机工程与科学学院，上海 200444； 2.上海大学 计算中心，上海 200444)

一种改进的基于SURF的视频帧间匹配方法

武 频1，王 庆1，朱永华1，高洪皓2

(1.上海大学 计算机工程与科学学院，上海 200444； 2.上海大学 计算中心，上海 200444)

针对视频连续帧间匹配不准确、错误率高、匹配速度慢的问题，提出了一种改进的基于SURF(Speeded Up Robust Feature)特征点的匹配方法。按照SURF算法进行特征点检测和描述；对视频连续帧利用改进的最近邻与次近邻的比的方法进行双向匹配，在匹配时仅在以相应位置为中心的邻域内寻找最近邻点和次近邻点，根据最近距离与次近距离的比值与预先设定阈值的比较结果确定是否接受这一匹配点对；用RANSAC(Random Sample Consensus)方法建立变换矩阵模型剔除错误匹配点，得到精确匹配的特征点对，完成匹配过程。在经典的视频数据集上进行实验，实验结果表明该方法不仅提高了视频连续帧间匹配的正确率，同时使匹配时间相对缩短了一半左右，显著提高了匹配效率，证明了算法的有效性。

SURF；视频连续帧；最近邻；匹配；随机抽样一致性

0 引 言

视频帧间特征点匹配是视频连续相邻两帧间的匹配，以图像特征点匹配为基础。目前图像特征点匹配方法广泛用于运动跟踪、动作识别和基于内容的视频检索等领域，是计算机视觉的重要研究热点和研究基础[1]。有很多学者在基于特征点的匹配方法方面进行研究，并取得了显著效果。常用的匹配特征点有Lowe等提出并完善的SIFT(Scale Invariant Feature Transform)特征点[2-3]，Bay提出的对SIFT的改进SURF(Speeded Up Robust Features)特征点[4]等。文献[5]对SIFT和SURF进行比较，SIFT特征点在很多方面表现较好，但由于特征向量维度过高，实时性不好，SURF与SIFT相比，性能相近但时间上是SIFT的三倍。为了加快匹配速度，有人对SURF特征点提取与描述方法进行改进[6-7]，也有对匹配方法进行改进[8]。文中是对匹配方法进行改进。

随着运动跟踪和动作识别等领域的发展，越来越多的学者将图像的匹配方法用于视频连续帧匹配。如佟爱华[9]利用SIFT算法提取视频帧的特征点，使用基于欧氏距离的最近邻与次近邻匹配的方法进行视频连续帧匹配，但SIFT特征点提取时间长，且匹配时对视频帧中的每个特征点在下一帧的所有特征点中搜索，时间效率低且匹配正确率低。卓武汉等[10]提取视频相邻帧的SURF特征点，同样采用最近邻与次近邻比的方法进行匹配，虽然使用SURF算法提高了特征点提取的速度，但匹配方法在时间效率和匹配正确率上同样较低。上述两种方法均是将图像匹配直接用于视频帧间匹配，未考虑视频帧自身的特点即视频帧连续间相差很小。为了解决这一问题，J. Yu等[11]使用SURF算法提取特征点，在匹配时利用欧氏距离度量法在下一帧的一个窗口中搜索距离最近的点作为匹配点。该方法虽在一定程度上缩短了搜索时间，但所使用匹配方法的匹配正确率较低。

针对上述问题，文中抓住SURF特征提取速度快及视频帧自身的特点，使用SURF算法提取特征点，提出一种改进的最近邻与次近邻比的方法，同时将双向匹配[12]方法用于视频帧间匹配，利用随机抽样一致性(RANdom SAmple Consensus,RANSAC)算法[13]剔除错误匹配点，不仅减少了特征提取与匹配的时间，同时一定程度上提高了匹配正确率。

1 SURF特征提取与描述

SURF算法采用积分图像和盒式滤波器的思想，提高了计算速度。这一节将重点介绍SURF特征点提取和描述的步骤。

1.1 SURF特征点提取

特征点提取过程包括积分图像、极值点检测和特征点确定三个部分。

首先是积分图像，主要是利用其计算速度快的特征来做图像卷积。积分图像表示图像上所有像素的和，即对图像I和其上的像素点I(x,y)，积分图像可用式(1)表示:

(1)

由式(1)可见，其计算方法非常简单，速度快。例如，若图像区域由顶点A,B,C和D四点构成，则图像的像素值之和为Σ=A-B-C+D。

其次，使用近似Hessian矩阵检测极值点。Hessian矩阵具有良好的计算时间和精度表现，SURF算法和SIFT算法一样都是基于尺度空间的，那么在尺度空间为σ的点I(x,y)的Hessian矩阵定义如下：

(2)

构建尺度空间的过程为：首先在图像上下采样，然后将其与各个尺度的二维高斯函数进行卷积操作。在进行卷积时，SURF算法使用方框滤波器代替二阶高斯滤波，这样大大提高了卷积计算速度，进而提高了整个算法的计算速度。仅仅通过改变方框滤波器的大小，就能建立尺度空间，Bay等对Hessian矩阵行列式的值做了较精确的估计，表示为式(3)：

ΔH=Dxx(x)Dxy(x)-(0.9Dxy(x))2

(3)

其中，ΔH是点I(x,y)周围邻域的方框滤波器响应值；Dxx，Dxy，Dyy是图像和各个方框滤波器模板进行卷积操作后的结果。

判断该点是否为极值点主要是依据两类重要的值,即该矩阵行列式的值及其特征值，如果行列式的结果符号为负，并且特征值有不同的符号，就判定该点不是局部极值点；如果行列式的结果符号为正，且两个特征值同时为正或为负，就可以把该点归类为极值点。

最后确定选出哪些极值点作为最终的特征点。该过程是通过比较极值点的邻域信息进行判断的，具体实现方法是在一个以某极值点为中心的3×3×3的立体邻域内，比较相邻的上下尺度和该尺度周围的26个邻域值，若该极值点的值比邻域值都大或都小，则判定其是最终的特征点。

1.2 SURF特征点描述

特征描述过程主要包括两个方面：一是确定基准方向，二是描述子的生成过程。

(1)基准方向确定。

为了保证特征矢量具有旋转不变性，需要为每一个特征点分配一个主方向即基准方向。具体方法是，首先在以特征点为圆心，6s(s为特征点所在尺度值)为半径的区域内计算水平方向和垂直方向的加权Harr小波响应，令越靠近特征点的Harr小波响应的权值越大；然后用一个60°的扇形模板遍历该圆形区域，得到多个由扇形模板内Harr响应的累加之和构成的矢量，把最大的累加和所对应的方向作为该特征点基准方向。

(2)生成描述子。

图1 特征描述符的生成过程

2 视频连续帧间特征匹配

在提取特征之后，为了提高匹配正确率，减少匹配时间，文中对已经提取过特征点的连续视频帧，采用改进的最近邻与次近邻比的方法进行双向匹配，然后使用RANSAC算法剔除错误匹配点。其中，距离衡量方式采用欧氏距离，定义如下:

D=

(4)

2.1 改进算法

基本思想为：对于前一帧中的每个特征点，在下一帧以这个位置为中心的N×N(窗口范围很小)的窗口范围内搜索最近点和次近点，得到两个距离：最近距离和次近距离。把最近距离与次近距离的比值和预先设定的阈值进行比较，若前者小于后者，则接受最近点作为该点的匹配点，完成单向匹配过程，得到单向匹配的候选匹配对集，然后对后一帧中已匹配的点用同样的方法与前一帧进行反向匹配，得到反向匹配的特征点对。对两个方向得到的匹配点对进行比较，若完全一样，则接受这一匹配点对，将其加入最终的匹配点对集。

具体步骤如下：

(1)在视频连续帧间，对于前一帧I1的特征点p1，在下一帧I2中，在以对应位置为中心的32×32(该邻域大小对存在较大幅度相机抖动的视频可适当放大)的邻域内搜索计算出欧氏距离最小的两个点作为最近邻点和次近邻点。最近点为p11，次近点为p12，得到两个距离，最近距离和次近距离，分别标记为d11和d12。若d11与d12的比值k小于给定阈值r(r取0.8)，则接受这对匹配对(p1,p11)作为候选匹配对，否则剔除该特征点。接着继续匹配下一对特征点，完成单向匹配。

2.2 RANSAC剔除错误匹配点

按照上述方法完成匹配后，为了进一步剔除错误匹配点对，可以使用RANSAC算法。其基本思想是，样本中包含两类数据，正确数据即可以被模型描述的数据，异常数据即偏离正常范围的数据。通常异常数据可能是由错误的测量、估算等产生。文中的异常数据是由匹配误差过大产生的。RANSAC也假定，可以为一组正确的数据建立一个描述它的模型，其基本步骤如下[14]：

(1)初始化模型M。已知初始化M所需的最小参数为n和一个样本集P，其中P的样本个数大于n。从P中随机抽取n个样本，组成集合S，用S来初始化模型M。

(2)构建内点集S'。将P中剩余样本中与模型M的误差小于给定阈值的样本组成的集合与集合S构成内点集S'，称S'是S的一致集(consensusset)。

(3)重复多次寻找一致集。若S'的样本数大于等于N，就认为得到了正确的模型参数，然后在集合S'上采用最小二乘等方法重新计算模型M'。重复步骤(1)和(2)。

(4)用一致集判断内外点。在重复一定次数的抽样后，若找到一致集，则选取抽样后得到的最大一致集判断内外点。否则算法失败。

文中运用RANSAC算法的思想是：从前面算法得到的匹配点对集中随机取出一些匹配点对来计算模型，然后根据计算出的模型遍历所有匹配点对，计算在某一特定阈值下满足该模型的百分比。重复上面的步骤，比较满足每个模型的百分比，取对应百分比最大的那个模型作为最终模型。实际实验中，首先根据上述思想建立一个3×3的最好的特征变换矩阵作为最终模型，然后在最好模型下剔除误差超过某个阈值的匹配对，得到精确匹配的特征点对。

3 实验结果与分析

实验环境为：MicrosoftVisualStudio2012和OpenCV，在Intel(R)Core(TM)i5-3230M，主频2.6GHz，内存4G的主机上进行。

共进行两组测试，分别对SURF和文中匹配方法在匹配对数、匹配时间、匹配正确率上进行比较。

第一组测试使用中科院的行为数据集CASIA进行实验，每帧大小为320×240。该视频为静态相机拍摄，共包括299帧，帧率为25fps。测试步骤如下：

(1)对于随机的连续两帧，如视频第86,87帧(左边front为86帧，右边after为87帧)见图2(a)。

(2)使用SURF算法提取特征点并进行64维的特征点描述。

(3)利用一般的SURF特征匹配方法得到的匹配结果如图2(b)所示。

(4)利用文中的匹配方法得到的匹配结果如图2(c)所示。

图2 匹配结果(1)

由图2(b)可看出，一般SURF特征匹配方法得到的匹配对比较杂乱，并且存在很多错误匹配点对。而由图2(c)可看出，文中方法得到的特征点对相对图2(b)有所减少，但匹配正确率较高。

下面在匹配点对数、匹配正确率和匹配时间这几个方面进行详细的分析比较。图2(a)中前一帧有255个特征点，后一帧有263个特征点，对该视频的299帧综合分析所得平均匹配点数、平均错误匹配数、平均正确匹配率和平均匹配时间如表1所示。

表1 算法比较(1)

由表1可知,文中匹配算法对于静止相机拍摄的视频的特征点匹配情况，不仅在匹配正确率上提高了大概10%，同时显著缩短了匹配时间，使得匹配时间变为原来的一半左右，证明了文中算法的有效性。

第二组测试使用YouTube数据集进行实验，其中的视频是用运动相机拍摄，存在旋转和噪声，用于验证文中算法对于旋转和噪声的鲁棒性。每帧大小为320×240，帧率为29fps，测试过程如下：

按照与第一组测试同样的步骤，对于随机连续的两帧如42，43帧，原图如图3(a)所示(左边front为前一帧，右边after为后一帧)。一般SURF特征匹配方法得到的结果如图3(b)所示，文中匹配方法得到的结果如图3(c)所示。

图3 匹配结果(2)

由图3中的(b)和(c)可明显看出，匹配时虽然一般的SURF特征匹配方法得到的匹配对较多，但由于在全图片范围搜索对应特征点，存在较多的错误匹配对。而文中的匹配方法虽然匹配对数相对较少，但匹配正确率显著提高。

对这两帧进行综合分析，前一帧检测出337个特征点，后一帧352个特征点，对一般SURF特征匹配方法和文中匹配方法在特征点匹配数量、匹配正确率、匹配时间方面进行比较，结果如表2所示。

表2 算法比较(2)

由表2可知，文中算法在相机运动和噪声存在情况下不仅在匹配正确率方面优势明显，同时匹配时间大概缩短了一半，保证了实时性。对于该情况下的多帧实验，由于存在相机运动和噪声，从各帧提取的特征点数量相差较大，进而匹配时间也相差较多，对上述各比较项不能平均而论，但文中匹配方法的匹配正确率都在90%以上，且匹配时间也较一般的SURF特征匹配时间缩短了一半左右，从而证明了文中算法的有效性。

对两组实验进行综合分析，第一组测试针对静态相机拍摄视频，通过图2和表1可看出，文中算法不仅提高了匹配正确率，而且缩短了匹配时间，证明了在该情况下的有效性。第二组实验视频是在运动相机下拍摄且存在严重噪声，比较图2(c)和图3(c)可明显看出，匹配对间的连线在图2(c)中是水平的，在图3(c)中是斜的，这是由于存在相机运动，导致两帧间有一定程度的旋转，进而得到图3(c)匹配对间的连线是斜的。该组实验验证了文中算法在该情况下的有效性。通过两组实验证明了文中算法对静态相机、相机抖动及噪声存在情况下拍摄的视频进行连续帧匹配的有效性。

4 结束语

研究了视频帧间的基于SURF的匹配方法。采用Fast-Hessian快速检测特征点，并对特征点进行描述，然后通过改进的最近邻与次近邻比的方法进行双向匹配，最后用RANSAC算法剔除错误匹配点。通过在静态相机、动态相机、噪声这几种不同情况下拍摄的视频进行实验，证明文中算法不仅提高了匹配正确率，而且缩短了匹配时间，对于视频中基于特征匹配的跟踪、识别等都有很大的实际作用。下一步可以在特征的提取和匹配上使用GPU加速进一步提高匹配效率。

[1] 余道明.图像配准技术研究及应用[D].成都:西南交通大学,2014.

[2]LoweDG.Objectrecognitionfromlocalscale-invariantfeature[C]//Proceedingsoftheseventhinternationalconferenceoncomputervision.[s.l.]:IEEE,1999:1150-1157.

[3]LoweDG.Distinctiveimagefeaturesfromscale-invariantfeaturespoints[J].InternationalJournalofComputerVision,2004,60(2):91-110.

[4]BayH.SURF:speededuprobustfeatures[J].ComputerVisionandImageUnderstanding,2008,110(3):346-359.

[5] 葛盼盼,陈 强.基于SURF特征提取的遥感图像自动配准[J].计算机系统应用,2014,23(3):16-24.

[6] 张开玉,梁凤梅.基于改进SURF的图像配准关键算法研究[J].科学技术与工程,2013,13(10):2875-2879.

[7] 崔振兴,曾 威,杨明强,等.一种改进的SURF快速匹配方法[J].江苏师范大学学报:自然科学版,2014,32(3):41-46.

[8]YangGui.Point-patternmatchingmethodusingSURFandshapecontext[J].OPTIK,2013,124:1869-1873.

[9] 佟爱华.一种改进的高精度视频帧间匹配算法[C]//第二届仪表、自动化与先进集成技术大会论文集.出版地不详:出版者不详,2008:146-150.

[10] 卓武汉,严京旗.基于SURF的连续帧图像配准及高光去除[J].微型电脑应用,2011,27(1):37-39.

[11]YuJ,JeonM,PedryczW.Weightedfeaturetrajectoriesandconcatenatedbag-of-featuresforactionrecognition[J].Neurocomputing,2014,131(7):200-207.

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

[13]FengQi,XuW,ZhangW,etal.ResearchofimagematchingbasedonimprovedSURF[J].TelkomnikaIndonesianJournalofElectricalEngineering,2014,12(2):1395-1402.

[14] 宋卫艳.RANSAC算法及其在遥感图像处理中的应用[D].北京:华北电力大学，2011.

An Improved Matching Method in Video Frames Based on SURF

WU Pin1,WANG Qing1,ZHU Yong-hua1,GAO Hong-hao2

(1.School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China; 2.Computer Center,Shanghai University,Shanghai 200444,China)

With the problem of inaccurate matching,high error rate and low speed in video frames,an improved matching method based on SURF (Speeded Up Robust Feature) is presented.The SURF features are detected and described.The improved method of ratio between the nearest and the next nearest neighbor is used for bidirectional matching.When matching,the nearest and next nearest neighbor points are searched only in the neighborhood of the corresponding points and the two matching points are accepted according to the comparison results between the distance ratio and the present threshold.The RANSAC method is applied to build the transformation matrix model to removing the error matches and get the exact match,completing the match process.The experiment is carried out on the classic video dataset,and the result shows that the method can improve the matching accuracy,and the matching time is relatively shortened by about half,significantly improving the matching efficiency and verifying the effectiveness of the algorithm.

SURF;continuous video frames;nearest neighbor;matching;RANSAC

2015-07-16

2015-12-15

时间：2017-01-10

上海市自然科学基金(15ZR1415200)

武 频(1975-)，女，副教授，博士后，研究方向为数值计算、图像处理。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1010.026.html

TP301.6

A

1673-629X(2017)02-0020-05

10.3969/j.issn.1673-629X.2017.02.005