SURF 算法的降維研究

盧清薇，羅旌鈺，王云峰

（廈門大學 廈門大學電子工程系，福建 廈門 361005）

SURF 算法的降維研究

盧清薇，羅旌鈺，王云峰

（廈門大學 廈門大學電子工程系，福建 廈門 361005）

SURF(Speed-up robust features)算法進行圖像特征點匹配時需要循環遍歷待匹配圖像所有特征點，計算特征點之間的SURF64描述距離，耗時大。本文對SURF算法進行了16維與4維的降維研究。實驗結果表明，16維SURF算法性能與64維SURF算法基本相當，但能大幅度降低運算時間；4維運算性能降低較大，不能用于特征點匹配，但4維SUFR描述算法可以擴展到圖像的各個像素點，用于ICP算法及圖像的稠密匹配。

圖像匹配；特征點；SURF算法；降維

0 引言

即時定位與地圖創建（SLAM, Simultaneous Localization and Mapping）系統在環境勘測、抗險救災、物體追蹤、終端移動自治等方面得到了廣泛的應用。隨著研究的深入以及計算機視覺的發展，SLAM系統研究的重心已經從基于昂貴的激光和聲納等傳感器轉移到基于視覺 SLAM 上了。視覺SLAM的核心問題是多場景間的匹配問題，選擇有效的匹配算法是重構環境的重要前提。

最早單獨使用視覺傳感器來估計移動終端的運動狀態是在19世紀80年代末，Moravec等[1]在他的研究工作中不但首次介紹了運動估計的流程，還提出了最早的圖像角點檢測算法。Matthies等[2]使用雙目視覺系統，結合Moravec的研究成果，進行SLAM研究。Davison等[3]利用視覺匹配的方法實現了對一個自由運動攝像頭的運動狀態求解。Henry等[4]率先利用新一代視覺傳感器Kinect采集室內場景數據，聯合形狀和表面信息進行圖像之間的配準，可以完成Kinect的即時定位與場景地圖的創建。Endres等[5]基于手持Kinect，利用SIFT（Scale Invariant Feature Transform）算法從彩色圖像提取特征點，進行匹配，結合圖像深度信息，在三維空間中構建可視化的地圖。上述文獻都是通過圖像特征點匹配，計算圖像之間的變換關系來完成即時定位與地圖創建。因此，特征點匹配算法的效率嚴重影響SLAM系統的性能。

SIFT[6-8]和SURF[9]是應用最廣的兩種圖像特征點匹配算法。SIFT是由Lowe率先提出的一種魯棒性強的圖像局部特征提取與匹配算法，具有對旋轉、光照、尺度變化等不變性。而SURF是由Bay在SIFT的基礎上提出的一種特征點提取匹配算法，SURF在各個方面均接近或超越了SIFT的性能，并且計算效率比SIFT算法提高了2倍左右，得到了廣泛的應用[10-12]。但在匹配時需要循環遍歷待匹配圖像所有特征點，計算各個特征點之間的64維SURF描述距離，耗時大。一些改進 SURF算法已經被提出。BBF-SURF[13]未對 SURF算法做出任何改變，只是軟件實現方法的改進；即在匹配過程中采用 K-D tree進行遍歷搜索，提高運算效率。該實現方法可應用到各類改進SURF特征點匹配算法中。Oriented BRIEF-SURF[14]算法同 SURF算法相比，不同點在于沒有采用64維描述向量，而是采用了BRIEF描述算子對特征點進行描述，減弱了匹配算法的針對圖像變換的不變性，降低模糊圖像的正確匹配率，運算效率提升幅度不大。ROI-SURF[15]采用 ROI算子進行特征點提取，結合隨機點半徑剔除法減少了特征點提取的數目，然后采用與SURF相同的描述與匹配，但是實驗結果顯示該算法降低了正確匹配率且運算效率提升幅度小。FAST-SURF[16]是采用FAST檢測器提取特征點，不具備尺度不變性，因此即使運算效率提升大，但適用范圍有限。本文將對SURF算法的描述進行降維，并基于Mikolajczyk圖像數據庫進行性能分析。

1 SURF特征點匹配算法

圖像特征點匹配算法可以分為特征點提取與描述、特征點匹配[9]過程。SURF算法是目前應用最多的特征點匹配算法，它采用了高斯二階微分模板進行特征點提取，使用64維向量描述特征點，并利用線性遍歷搜索的方法進行匹配。

1.1 特征點提取與描述

SURF算法基于圖像中各點的Hessian矩陣進行特征點提取，對于圖像中任意一點 P=(x,y)， 其灰度值為I(P)=I(x,y)，則Hessian矩陣[9]H(P, σk) 如式（1）所示：

設?為邊長為 N 的高斯二階偏導濾波模板，σk為高斯函數的參數，則式（1）中 Lxx(P,σk)為?2g(σk)/?x2與以 P為中心的邊長為 N的正方形局部圖像灰度的卷積。高斯函數二階偏導濾波模板?2g(σk)/?x2可由式（2）表示：

2g(σk)/?x2

則：

Lxy(P,σk)，Lyy(P,σk)具有相似的含義，但模板不同。Hessian矩陣對應的行列式[9]det(H)為：

為了在有縮放關系的圖像間找到相互匹配的特征點，SURF算法通過改變σk獲得不同尺度下的濾波器，分組對圖像進行處理，得到相應尺度空間下的響應圖；濾波器尺度Sk與σk的關系如式（5）所示：

式中：Nk為濾波器邊長。

特征點判斷時，逐組進行，只要有一組滿足式（6）即為特征點。

式中 ε值的大小影響特征點數目，通常是根據經驗值選取，大多數文獻選取ε為0.650，本文也取此值。

特征點描述[9]首先利用Haar小波濾波器確定描述的主方向，再以特征點為中心,以主方向為水平方向確定4×4個描述的子區域；每個子區域中用Haar小波濾波器計算水平方向的響應dx和豎直方向的響應 dy，得到 4 維向量(∑dx,∑dy,∑|dx|,∑|dy|)，把 4×4個子塊區域的向量連接起來就得到了一個 64維的特征點描述向量。

1.2 特征點匹配

特征點匹配是為兩幅圖像共有的特征點建立一一對應關系的過程。SURF算法采用的是遍歷式線性搜索方法。設算法中PA是圖像A的特征點集 SA中任意一點，PB是圖像B的特征點集SB中任意一點，它們的特征點描述向量分別為 Des(PA)和 Des(PB)，Desi(PA)和 Desi(PA)分別是特征點描述向量的第 i個分量，PA和PB之間的歐式距離Dist(PA,PB)為：

把A圖中的點PA與B圖SB中的所有點的距離計算一遍，得到最近距離ND （Nearest Distance）和次最近距離NND （Next Nearest Distance），則距離之比RoD （Ratio of Distance） 如式（8）所示:

當RoD小于一個閾值threshold時，就認為這對點是匹配點。threshold∈[0.5, 0.7]是個比較理想的范圍[9]，本文選取0.65。SURF算法匹配的具體過程如表1所示：

表1 特征點匹配算法Tab.1 The SURF feature point matching

2 SURF算法的降維實現方法

2.1 SURF算法的64維描述

SURF特征點描述是利用特征點周圍信息來描述這個點。首先以特征點為中心，用尺寸為4S的Haar小波濾波器在以6S為半徑的圓形鄰域里，求得每個像素點的Haar小波響應，然后用以特征點為中心的高斯函數(2Sσ=)對這些響應進行加權。用一個圓心角為/3π扇形（如圖1）以特征點為中心環繞一周，計算該扇形處于每個角度時，它所包括的圖像點的Haar小波響應之和，取和值的最大值為該特征點所對應的主方向。

圖1 滑動的扇形窗口Fig.1 The fan widow for calculating direction

以特征點為中心、上述得到的主方向為水平方向的確定一個正方形領域，其邊長為20S，把該正方形區域分成4× 4個子塊區域，每個子塊區域中用Haar小波濾波器處理。 dx表示水平方向的Haar小波響應， dy表示豎直方向的 Haar小波響應，在構建描述子向量之前，對于所有的 dx、 dy都要用一個以特征點為中心的高斯函數加權，該高斯函數的σ= 3 .3S 。在每個子塊區域中對 d求和，從而得到一個 4維向量把4× 4個子塊區域的向量連接起來就得到了一個64維的特征點描述向量。

2.2 降維實現方法

生成SURF 描述符時首先要以特征點為中心確定的邊長為20S的正方形鄰域，該鄰域被稱為為20S方鄰域。如圖2所示，則20s 方鄰域內共有400 個采樣像素，以25 個采樣像素為單元區域，則20s 方鄰域被劃分為 4×4=16 個子區域。對每個子區域進行 Haar小波濾波，并且在每個子塊區域中對 dx、求和就得到一個 4維向量由于每個子區域生成4維描述向量，所以16個子區域共生成64維描述向量。

SURF描述的核心思想是以一個正方形的區域特征來代表其中心特征點。顯而易見這種描述方式比以單個點的特征參數代表特征點的方式更加具備魯棒性。這種描述方式完全可以擴展到圖像的所有點，影響擴展應用的原因在于其維數。應用時對圖像全部像素點進行 64維描述向量運算需要大量的運算時間，不具備可行性。基于此，本文實現了對SURF描述向量實現了16維與4維的降維。16維的降維方法是固定單位區域為25個像素點；然后選取描述區域時是以特征點為中心，以邊長為10S構造正方形鄰域。則正方形鄰域可以劃分成4個子區域，每個區域采用原SURF的處理方式，構造4維描述向量。4個區域則共16維描述向量。4維的降維方法同16維類似，以邊長為5S構造正方形鄰域。整個鄰域只包含一個子區域，則只有4維描述向量。

圖2 SURF描述生成示意圖Fig.2 The generation of SURF description

3 降維SURF算法性能分析

Mikolajczyk圖像數據集是用來測試圖像匹配算法的性能的圖像集合，其中包含了8組圖像，每組圖像集合中都有6幅圖像，其中每組集合中的圖像都是相機在不同參數情況下拍攝得到的，分別具有尺度、壓縮、旋轉、光照、視角等圖像變換。其中Boat圖像集和Bark圖像集是旋轉圖集，可以用來檢測匹配算法的旋轉魯棒性。匹配算法對模糊變換的魯棒性可以使用Bikes圖像集合Trees圖像集來檢測，因為這兩個圖像集是由原圖像和不同尺度的高斯核卷積得到的。Graf圖像集和Wall圖像集中的圖像是由視角變換得到的，可以用來匹配算法在視角變換下的穩定性。匹配算法在光照變換的穩定性可以使用 Leuven圖像集來檢測，Leuven圖像集為不同亮度下的同一物體的圖像。最后一組圖像集Ubc圖像集內的圖像具有不同的壓縮程度，可以用來檢測匹配算法在壓縮變換下的穩定性。

本文選用具有代表性的ubc圖集、boat圖集、bikes圖集、leuven圖集和graf圖集進行降維性能分析。根據這幾組圖像的特征，將每組圖像的第一幅圖像和剩余的圖像一一匹配，各個維度的性能比較如表2-表6所示。

表2 ubc圖集上性能比較Tab.2 The performance comparison on ubc

表3 boat圖集上正確匹配數目比較Tab.3 The performance comparison on boat

表4 bikes圖集上正確匹配數目比較Tab.4 The performance comparison on bikes

表5 Leuven圖集上正確匹配數目比較Tab.5 The performance comparison on Leuven

表6 graf圖集上正確匹配數目比較Tab.6 The performance comparison on graf

SURF描述在各個圖像集上的所體現的匹配性能均有大幅下降，不適合用于圖像特征點匹配。但由于其維數較少，并且具備一定的各種變換的魯棒性，可以擴展到圖像的每個像素點，用于ICP算法及稠密匹配。

4 結論

本文通過改變SURF算法特征點描述的正方形鄰域的大小，實現了16維與4維的特征點SURF描述。實驗結果表明，16維SURF描述用于圖像特征點匹配可以大幅降低匹配時間，并且大多數環境下匹配性能與原64維SURF相當；僅不適合用于存在大量旋轉的環境下的圖像特征點匹配。4維 SURF描述的匹配效果大幅下降，不宜用于特征點匹配。但可以以擴展到圖像的每個像素點，用于ICP算法及稠密匹配。

[1] MORAVEC H P. Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover [D]. California: Stanford University, 1980.

[2] MATTHIES L, SHAFER S. Error modeling in stereo navigation[J]. Robotics and Automation, IEEE, 1987, 3(3): 239-248.

[3] DAVISON A J. Real-time simultaneous localization and mapping with a single Camera[C], Computer Vision. Nice,France, 2003:1403-1410.

[4] HENRY P, REN X, FOX D, et al. RGB-D mapping:Using depth cameras for dense 3D modeling of indoor environments[J]. International Journal of Robotics Research, 2010,31(5): 647-663.

[5] ENDRES F, HESS J, ENGELHARD N,et al. An evaluation of the RGB-D system[C], Robotics andAutomation. St. Paul,Minnesota, 2012: 1691-1696.

[6] LOWE DG. Distinctive image features from scaleinvariant Keypoints[J]. International Journal of Computer Vision, 2004,60(2): 91-110.

[7] TAKEISHI N, TANIMOTO A, YAIRI T. Evaluation of interest-region detectors and descriptors for automatic landmark tracking on asteroids[J]. Transactions of the Japan Society for Aeronautical and Space Sciences, 2015, 58(1): 45-53.

[8] WU Hao, TIAN Guo-hui, LI Yan. Building of cognizing semantic map in large-scale semi-unknown environment[J].Journal of Central South University. 2014, 21(5): 1804-1815.[9] HERBERT B, TINNE T, LUC V G. SURF: Speeded Up Robust Features [J]. Computer Vision and Image Understanding,2008, 110(3): 346-359.

[10] 劉博文, 童立靖. 基于多視角三維掃描數據的圖像配準[J].軟件, 2016, 37(9): 29-32.

[11] 李守憲, 魏芳. 移動終端Logo識別系統[J]. 軟件, 2016,37(02): 98-102.

[12] 翁秀玲, 王云峰, 余小亮. 一種圖像立體匹配的誤匹配點剔除與校正方法[J]. 軟件, 2016, 37(9): 20-24.

[13] Jia X, Wang X, Dong Z. Image matching method based on improved SURF algorithm[C], IEEE International Conference on Computer and Communications. IEEE, 2015: 142-145.

[14] Ye Y. The Research of SLAM Monocular Vision Based on The Improved SURF Feather[C], International Conference on Computational Intelligence and Communication Networks.IEEE, 2014: 344-348.

[15] Ma Y L S. Research on Image Based on Improved SURF Feature Matching[C], Seventh International Symposium on Computational Intelligence and Design. IEEE, 2015: 581-584.

[16] Zhang H, Hu Q. Fast image matching based-on improved SURF algorithm[C], International Conference on Electronics,Communications and Control. IEEE, 2011: 1460-1463.

Research on Dimensional Reduction for SURF Algorithm

LU Qing-wei, LUO Jing-yu, Wang Yun-feng
(Department of electronic engineering, Xiamen University, Xiamen Fujian 361005, China)

Matching image feature point by SURF(Speed-up robust features) algorithm needs to loop through all feature points on the image to be matched, and compute the sixty-four dimensional distance of SURF between feature points, which will take a long computation time. The sixteen dimensional SURF and four SURF are implemented. The experimental results show that the performance of the sixteen dimensional SURF is almost the same as that of the sixty-four dimensional SURF, moreover the sixteen dimensional SURF takes less time than sixty-four dimensional SURF. The performance of four dimensional SURF is much inferior to that of sixty-four dimensional SURF, so it cannot used to match feature point. However the four dimensional description of SURF can be expanded to all feature points, which can be applied in ICP algorithm and dense matching algorithm.

Image matching; Feature points; SURF algorithm; Dimensional reduction

TP391

A

10.3969/j.issn.1003-6970.2017.12.028

本文著錄格式：盧清薇，羅旌鈺，王云峰. SURF算法的降維研究[J]. 軟件，2017，38（12）：148-152

盧清薇(1994-)，女，碩士研究生，主要研究方向：SLAM系統；羅旌鈺(1994-)，男，碩士研究生，主要研究方向：SLAM系統。

王云峰(1977-)，男，副教授，博士，研究方向:數字集成電路設計及SLAM系統軟硬件設計。