一種改進的SURF快速匹配算法

崔振興，曾 威，楊明強，韓 峰

（山東大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟南 250100）

0 引言

在圖像處理與計算機視覺中，局部圖像特征的描述與檢測可以用來幫助辨識物體，因此對物體的局部特征提取具有很重要意義.1999年，Lowe［1］提出了SIFT（scale－invariant feature transform）算法，并在2004年進行了改進［2］.SIFT算法用來檢測與描述圖像中的局部性特征，它在尺度空間中尋找極值點，提取出其位置、尺度、旋轉(zhuǎn)不變量等特征值并生成128維的特征向量.但是由于SIFT統(tǒng)計的是關(guān)鍵點周圍鄰域的梯度信息，計算復(fù)雜度高，并且需要形成128維的高維向量，在特征匹配時耗時巨大，不能達到實時性要求.近年來，基于SIFT改進的算法層出不窮［3－4］.為了提高匹配速度，文獻［5］提出了主成分分析法（principal component analysis，PCA），運用PCA降低特征向量的維數(shù).為了增強特征描述子的唯一性，文獻［6］提出用以關(guān)鍵點作為圓心的同心圓代替棋盤格來計算梯度方向直方圖，并計算得到一個272維的特征向量，然后通過主成分分析法將特征向量降成128維.此方法雖然能提高特征向量的獨特性，并增加了特征匹配的準確率，但同時也增加了運算時間.Bay等［7］于2006年提出了SURF（speeded up robust features）算法，其速度比SIFT算法提高了3～5倍，準確度也有所提升.在基于視覺的目標識別過程中，人們最關(guān)心的問題是識別的準確度和能否實時處理.由于SURF算法特征描述子的維數(shù)為64維，與SIFT算法的描述子相比雖然已經(jīng)減少了很多，但是要達到特征之間的實時匹配仍然顯得吃力.相對于SIFT算法，SURF算法在速度上的提升是因為使用了積分圖像和盒式濾波器（box filter），但是其在特征點的匹配上仍然采用一一對應(yīng)相匹配［8］.這樣，不僅耗時高，而且容易出現(xiàn)誤匹配.

本文針對SURF算法，在特征點的形成和匹配方面進行了改進.首先利用圖像的Hessian矩陣進行極值點的檢測，在確定了極值點之后再利用Haar小波對圖像進行計算，得到特征點主方向和64維特征描述子.然后結(jié)合特征點的分類思想［9］，根據(jù)特征點的主方向鄰域內(nèi)像素和之間的差值，形成一個4維的特征向量，與SURF的特征描述子相結(jié)合形成新的68維特征向量，以達到提高匹配速度的目的.在匹配時，首先對特征點按照其特征向量的前4維進行粗匹配，從而將特征點分成9組，然后將9組特征點分別進行組內(nèi)匹配，這樣就避免了不同組特征向量之間的相互匹配，從而提高匹配速度和準確率.本文算法流程如圖1所示.

圖1 算法流程圖Fig.1 Flow chart of the algorithm

1 SURF算法特征點檢測

SURF算法的設(shè)計步驟基本同于SIFT算法，它基于積分圖像提取特征點，并通過Haar小波濾波器來描述特征點，是一種集特征提取和特征描述于一身的算法.SURF算法主要包括3個步驟：特征點檢測、特征點描述和特征點匹配.

SURF算法使用近似的 Hessian矩陣［10］來檢測特征點，并使用積分圖像，大幅度減少了運算量.SURF算法之所以在計算速度上明顯快于同類算法，主要是因為它引入了積分圖像和盒式濾波器的概念.

1.1 積分圖像

積分圖像的概念最早是由Viola和Jones［11］提出的，其目的是為了能夠快速計算矩形區(qū)域的像素和（或者是像素的平方和）.它是一種中間圖像，通過對原圖像遍歷即可得到.圖2為積分圖像示意圖.假設(shè)圖像中的任一點（i，j）的值為I（i，j），則對應(yīng)積分圖像的值IΣ（i，j）為

這樣，通過積分圖像就能夠快速地計算圖像中任意矩形區(qū)域的像素和，且計算的耗時與矩形區(qū)域面積大小無關(guān).

圖2 積分圖像Fig.2 Integral image

1.2 Hessian矩陣

對給定的一幅圖像I，在其任意一點（x，y）處的Hessian矩陣表達式為

式中Lxx（x，y，σ），Lxy（x，y，σ），Lyy（x，y，σ）分別表示高斯二階偏導(dǎo)數(shù)在點（x，y）處與原圖像I的卷積.二維高斯核函數(shù)為

其中σ為標準差.

為了降低復(fù)雜度并提高算法的提取速度，Bay在算法中引入了盒式濾波器來近似高斯二階差分模板.如圖3所示，上面一行為高斯二階差分在xx，yy，xy方向上的模板，下面一行為盒式濾波器對上面一行模板的近似.用Dxx，Dxy，Dyy來近似表示公式（1）中的Lxx，Lxy，Lyy，于是 Hessian矩陣行列式就可以近似表示為

其中w為權(quán)重，一般取0.9.用式（1）求圖像中每個像素點的響應(yīng)就可以得到在對應(yīng)尺度上的響應(yīng)圖.

圖3 用盒式濾波器近似高斯濾波器Fig.3 Using box filter to approximate Gaussian filter

1.3 尺度空間

為了使SURF算法具有尺度不變性，可通過改變盒式濾波器的模板大小來建立尺度空間金字塔［12］.如圖4所示，圖像金字塔共分為4層，對每一層進行4次濾波.在第1層中，相鄰的模板尺寸相差6個像素，在第2層中相差12個像素，在第3層中相差24個像素，以此類推.每一層的第一個模板尺寸等于其上一層的第二個模板的尺寸.每次濾波對應(yīng)的近似尺度可由下式計算：

圖4 SURF算法尺度空間金字塔Fig.4 Pyramid of scale space

特征點定位：

首先，為Hessian矩陣的響應(yīng)值設(shè)定一個閾值，所有小于這個閾值的點都被去除.

其次，在3×3×3的立體鄰域內(nèi)進行非極大值抑制.只有那些比其上一尺度、下一尺度及本尺度周圍的26個點的響應(yīng)值都大或都小的點才被選為特征點.

最后，通過擬合3維二次函數(shù)從而精確確定特征點的位置和尺度.

1.4 特征點主方向定位

為了使SURF特征向量具有旋轉(zhuǎn)不變的特性，需要為SURF特征點確定一個主方向.特征點主方向的確定過程主要分3步（圖5）：

1）在以特征點為圓心，以6σ（σ為特征點所在的尺度值）為半徑的圓形鄰域里，用邊長為4σ的Haar小波模板［13－14］求x和y兩個方向的 Haar小波響應(yīng)；

圖5 主方向選擇Fig.5 Main direction selection

2）以特征點為中心，用標準差為2σ的高斯函數(shù)對濾波后的區(qū)域進行加權(quán)；

3）以關(guān)鍵點為圓心，用一個圓心角為π／3的扇形窗口掃描一周，計算該扇形窗口每個角度內(nèi)包括的圖像點的Haar小波響應(yīng)總和，取其中最大響應(yīng)的方向為該關(guān)鍵點的方向.

2 改進SURF算法特征點的描述

2.1 特征點分類

本文算法結(jié)合特征點的分類思想，根據(jù)特征點主方向鄰域內(nèi)像素和之間的差值形成一個4維的特征向量，與SURF特征描述子相結(jié)合形成新的特征向量，進而達到提高速率的目的.

首先，將檢測到的特征點在其相應(yīng)尺度上按照其主方向旋轉(zhuǎn)，將特征點的主方向作為平面直角坐標系xOy中的一個軸，然后以此特征點為圓心，以其所在尺度σ為半徑作圓，將此圓形鄰域劃分為4個區(qū)域，分別為平面直角坐標系xOy的4個象限中的像素區(qū)域.對于第一象限，以象限內(nèi)的某一像素點為起點，順時針遍歷象限內(nèi)的所有點的灰度值至起點，并計算第一象限內(nèi)所有像素點的灰度值之和Σ1.同理，分別計算Σ2，Σ3，Σ4，如圖6所示.

圖6 特征點各象限像素點求和示意圖Fig.6 Pixel sum in each quadrant

其次，計算Σ13＝Σ1－Σ3和Σ24＝Σ2－Σ4.設(shè)定閾值T0，求出特征向量τi（用二進制數(shù)表示）：

然后將τ1和τ2組合，形成一個4維特征向量.這樣，在最后特征點的特征描述子生成之前，先根據(jù)τ1和τ2組合將特征點分為9類：0000，0001，0010，0100，0101，0110，1000，1001，1010.

閾值T0的選取原則：選取的閾值T0應(yīng)該使9類特征點分組中每組特征點的個數(shù)盡量相同或者接近，這樣可以最大地減小每組匹配耗時.對于不同圖像庫里的圖像，因其特征點的分布不同，故閾值T0的選取也不同.

本文算法與文獻［15］中提到的比較描述子思想類似但又不同.通過計算關(guān)于特征點對稱區(qū)域的差值形成描述子，與SURF算法相比，這樣計算簡單方便，易于后續(xù)的特征匹配；而且就比較描述子而言，計算區(qū)域之間的差值，能增加描述子的抗噪能力，使匹配更精確.為了增加特征向量的準確度，設(shè)置閾值T0，將可以用一位二進制數(shù)表示的大小關(guān)系變成用兩位描述，這樣雖然增加了計算復(fù)雜度，但是增加了特征點的類別，使后續(xù)的匹配更加快速精確.

2.2 建立特征向量

將特征點的主方向作為平面直角坐標系xOy中的一個軸，以其特征點為原點，選取特征點周圍的大小為20σ×20σ的矩形鄰域，然后將其平均分成4×4個子區(qū)域，如圖7所示.

圖7 特征描述子的生成示意圖Fig.7 Generation of feature descriptor

在大小為5σ×5σ的16個子區(qū)域內(nèi)用窗口尺寸為2σ的Haar小波進行濾波，Haar小波窗口在子區(qū)域內(nèi)均勻移動25次，可得到25組x方向和y方向上的響應(yīng)值dx，dy；再用標準差為3.3σ的高斯函數(shù)對其進行加權(quán)，統(tǒng)計子區(qū)域內(nèi) ∑dx，∑｜dx｜，∑dy，∑｜dy｜的值，形成子區(qū)域的特征向量；將4×4個子區(qū)域內(nèi)的特征向量組合形成64維的向量；最后，將通過式（2）得到的4維向量與此64維向量結(jié)合形成68維向量v，并對此68維向量進行歸一化處理，可得到特征點的改進SURF特征描述子.

3 SURF特征點匹配

圖像特征提取的直接目的就是特征匹配.本文在提取出SURF特征向量后，首先根據(jù)前4維向量對得到的68維特征向量進行粗匹配分組，具體實現(xiàn)過程如下：取出每個特征點形成的68維特征向量v的前4維向量τ1和τ2（其中τ1和τ2都是兩維）；然后進行同或運算，當兩個特征點前4位的同或結(jié)果為1111時，將這兩個特征點視為同一類.經(jīng)過一系列的同或運算之后，就可以將特征向量分成9組：0000，0001，0010，0100，0101，0110，1000，1001，1010.最后分別對這9組特征向量進行組內(nèi)匹配.組內(nèi)特征匹配的方法有很多，其中用向量的最近鄰匹配法［16－17］可以找出潛在的匹配對而無需進行額外信息量的計算.本文算法進行組內(nèi)匹配時，運用基于BBF搜索方法的最近鄰匹配算法來完成對目標的檢測和識別.匹配時進行雙向匹配.對特征向量進行相似性測量［18］，以兩個特征向量的歐氏距離［19］作為特征相似的判別標準.設(shè)兩幅圖像I1和I2的SURF特征向量集分別為V1＝｛v11，v12，…，v1m｝，V2＝｛v21，v22，…，v2n｝，其中 m，n 分別是兩圖像上SURF特征點的個數(shù).計算相似特征向量：

其中

這里dis（v1i，v2j）表示兩個特征向量的歐式距離.R即為最小距離與次小距離之比.設(shè)定閾值R0，當R＞R0時，特征向量匹配不成功，反之則兩向量為匹配向量對.

雖然對特征向量的分組會有一定時間損耗，但相比于SURF特征的歐氏距離的運算，這些計算都是少量的加減運算，計算量很小.

4 實驗結(jié)果及分析

對經(jīng)典SURF算法與本文改進的SURF算法在特征匹配速度和精度方面進行比較.實驗在Windows XP下Matlab 2010a軟件中實現(xiàn).硬件條件為：CPU，Pentium（R）Dual－Core E5800；內(nèi) 存，2 GB；主頻，3.20GHz.

為便于比較，實驗中取T0＝0，此時公式（2）變?yōu)椋?/p>

這樣特征點被分成00，01，10，11共4組.

在特征向量的形成過程中，對子區(qū)域用Haar小波進行濾波，得到25組響應(yīng)值后需要用高斯函數(shù)進行加權(quán).本文從0.1σ開始，以0.1σ個單位遞增，在Coil－100圖像庫中選取每種物體0°和35°兩種圖像進行驗證，求取匹配的平均準確率.

試驗結(jié)果（表1）表明，當高斯函數(shù)的標準差為3.3σ時匹配準確率最高，標準差再增大時準確率不變，因此選用標準差為3.3σ的高斯函數(shù)加權(quán).

表1 不同高斯標準差對結(jié)果的影響Tab.1 Influence of differentσto the results

圖8為實驗用的原始圖像與提取SURF特征后的圖像，第一行為一對具有較強仿射變化和旋轉(zhuǎn)變化同時相似性又較強的原始圖像，圖像大小為800像素×640像素.第二行為采用本文算法提取特征點后對應(yīng)圖像的特征點信息在圖像上的顯示，其中“·”，“＋”，“△”，“＊”分別表示4組特征向量.

圖8 原始圖像與提取SURF特征后的圖像Fig.8 Original figure and SURF feature points

表2為原始圖像的特征點信息.可以看出，本文算法在提取出的圖像特征點上與經(jīng)典SURF算法一致，即不會減少從原圖像中提取出的特征點數(shù)目.

表2 原始圖像提取特征點的數(shù)目Tab.2 Number of the feature points

在提取出特征點之后，對原始圖像進行特征點的匹配（圖9）.圖像為object0024.view01.jpg和object0024.view03.jpg.圖像大小均為640像素×480像素，分辨率為96dpi.表3為按照本文算法分組后的兩幅圖像各自的特征點個數(shù)及匹配耗時.可以看出，本文算法實現(xiàn)兩幅原始圖像特征點的匹配耗時為0.046s，同時，本文算法在分組時所消耗的時間為0.009s，所以總耗時為0.046＋0.009＝0.054s.本文算法在速度與精度上較經(jīng)典SURF算法都有一定提高，具體比較結(jié)果如表4所示.

圖9 匹配結(jié)果圖Fig.9 Matching results

表3 原始圖像特征點分組情況及匹配耗時Tab.3 Group of the feature points and matching time－consuming

表4 本文算法與經(jīng)典SURF算法對比結(jié)果Tab.4 Comparation of the two algorithms

可以看出，本文的改進算法比經(jīng)典SURF算法所消耗的時間少0.090s，而正確匹配率也因為降低了噪聲干擾而比經(jīng)典SURF算法高.

為了驗證本文算法在特征點提取與匹配方面的普遍適用性，在哥倫比亞大學(xué)的Coil－100圖像庫中做實驗驗證.Coil－100圖像庫為100種不同物體的各個不同視角不同尺度的圖像.從Coil－100圖像庫中隨機挑選30種不同物體，分別取其視角為0°，5°，10°，15°，20°，25°，30°，35°，40°，45°的10種圖像進行特征匹配，取每次實驗數(shù)據(jù)的平均值作為最后的結(jié)果，并與經(jīng)典SURF算法相比較.圖10為其中一組圖像0°和35°的原圖、特征點提取圖及匹配結(jié)果圖.結(jié)果顯示，SURF算法平均匹配耗時為0.008s，而本文算法為0.005s.

由于Coil－100數(shù)據(jù)庫中圖像大小為128像素×128像素，提取特征點的數(shù)目也較少，因此用經(jīng)典SURF算法匹配耗時比較短，準確率也較高，但從平均匹配耗時和圖11仍然可以看出，在Coil－100圖像庫中，相較于經(jīng)典SURF算法，本文算法在精確度不下降的情況下匹配時間仍有明顯提高.

圖10 原始圖、特征點提取圖及匹配結(jié)果圖Fig.10 Original figure，feature points and matching results

圖11 兩種算法在Coil－100庫的匹配準確率Fig.11 Accurate of the two algorithms based on Coil－100

5 結(jié)語

經(jīng)典SURF算法在匹配的過程中，對一幅圖像上每一個選定的特征點都要與另一幅圖像上所有的特征點一一進行匹配，耗時較高.基于此，本文提出了將特征點分組匹配的改進方法，根據(jù)特征點鄰域內(nèi)像素之間的差值形成一個4維的特征向量，與SURF的特征描述子相結(jié)合，以達到提高匹配速度和準確率的目的.通過對改進算法的理論分析和實驗驗證，結(jié)果表明：相對于經(jīng)典SURF算法，本文算法在速度上有明顯的提高，精確度也有所改善，更適用于對實時性要求較高的圖像配準，如基于單目視覺的智能服務(wù)機器人的目標識別過程中，本文算法可以提高其目標識別的速度，以達到實時性要求.

［1］Lowe D G.Object recognition from local scale－invariant features［C］／／7th International Conference on Computer Vision.September 20－25，Corfu，Greece.IEEE，1999，2：1150.

［2］Lowe D G.Distinctive image features from scale－invariant feature points［J］.Int J Comput Vision，2004，60：91.

［3］胡海青，譚建龍.改進SIFT算法在文字圖像匹配中的應(yīng)用［J］.計算機工程，2013，39（1）：239.

［4］王民，劉偉光.基于改進SIFT特征的雙目圖像匹配算法［J］.計算機工程與應(yīng)用，2013，49（2）：203.

［5］Ke Y，Sukthankar R.PCA－SIFT：a more distinctive representation for local image descriptors［C］／／IEEE Computer Society Conference on Computer Vision and Pattern Recognition.June 27－July 02，Washington DC，USA.IEEE，2004，2：506－513.

［6］Viola P，Jones M.Rapid object detection using a boosted cascade of simple features［C］／／Proceedings of the 2001IEEE Computer Society Conference on Computer Vision and Pattern Recognition.December 08－14，Kauai，Hawaii.IEEE，2001，1：511－518.

［7］Bay H，Ess A，Tuytelaars T.SURF：speeded up robust features［J］.Computer Vision ＆ Image Understanding，2008，110（3）：346.

［8］杜冬梅，王紅旗，田昆鵬.一種改進的快速SURF算法［J］.科學(xué)技術(shù)與工程，2013，13（5）：1350.

［9］黃詩捷，王定祥，張征宇.一種同名像點快速匹配方法［J］.兵工自動化，2012，31（3）：51.

［10］康長青，袁磊，華麗.一種新的血管造影圖像Hessian矩陣增強算法［J］.計算機工程與科學(xué)，2012，34（10）：104.

［11］Viola P，Jones M J.Robust real－time face detection［J］.Int J Comput Vision，2004，57（2）：137.

［12］方亦凱，程健.基于快速尺度空間特征檢測的手勢識別方法［J］.圖像圖形學(xué)報，2009，14（2）：214.

［13］陳景航，楊宜民.一種基于Harr小波的快速模板匹配算法［J］.計算機工程，2005，31（22）：167.

［14］趙沁平，車英慧.基于Harr小波的動態(tài)場景全頻陰影繪制算法［J］.軟件學(xué)報，2011，22（8）：1948.

［15］Rublee E，Rabaud V，Konolige K.ORB：an efficient alternative to SIFT or SURF［C］／／IEEE International Conference on Computer Vision.Nov 6－13，Barcelona.IEEE，2011：2564－2571.

［16］蔡賀，張睿.k最近鄰域分類算法分析與研究［J］.甘肅科技，2012，28（18）：14.

［17］趙璐璐，耿國華，李康.基于SURF和快速近似最近鄰搜索的圖像匹配算法［J］.計算機應(yīng)用研究，2013，30（3）：921.

［18］賈克斌，方晟，沈蘭蓀.基于顏色和空間特征的彩色圖像獲取方法［J］.電子學(xué)報，2003，31（6）：895.

［19］劉相濱，鄒北驥，王勝春.一種新的完全歐氏距離變換算法［J］.計算機工程與應(yīng)用，2005，41（13）：44.