一種改進的基于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