盧清薇，羅旌鈺，王云峰

（廈門(mén)大學(xué) 廈門(mén)大學(xué)電子工程系，福建 廈門(mén) 361005）

SURF 算法的降維研究

盧清薇，羅旌鈺，王云峰

（廈門(mén)大學(xué) 廈門(mén)大學(xué)電子工程系，福建 廈門(mén) 361005）

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

圖像匹配；特征點(diǎn)；SURF算法；降維

0 引言

即時(shí)定位與地圖創(chuàng)建（SLAM, Simultaneous Localization and Mapping）系統(tǒng)在環(huán)境勘測(cè)、抗險(xiǎn)救災(zāi)、物體追蹤、終端移動(dòng)自治等方面得到了廣泛的應(yīng)用。隨著研究的深入以及計(jì)算機(jī)視覺(jué)的發(fā)展，SLAM系統(tǒng)研究的重心已經(jīng)從基于昂貴的激光和聲納等傳感器轉(zhuǎn)移到基于視覺(jué) SLAM 上了。視覺(jué)SLAM的核心問(wèn)題是多場(chǎng)景間的匹配問(wèn)題，選擇有效的匹配算法是重構(gòu)環(huán)境的重要前提。

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

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

1 SURF特征點(diǎn)匹配算法

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

1.1 特征點(diǎn)提取與描述

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

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

2g(σk)/?x2

則：

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

為了在有縮放關(guān)系的圖像間找到相互匹配的特征點(diǎn)，SURF算法通過(guò)改變?chǔ)襨獲得不同尺度下的濾波器，分組對(duì)圖像進(jìn)行處理，得到相應(yīng)尺度空間下的響應(yīng)圖；濾波器尺度Sk與σk的關(guān)系如式（5）所示：

式中：Nk為濾波器邊長(zhǎng)。

特征點(diǎn)判斷時(shí)，逐組進(jìn)行，只要有一組滿足式（6）即為特征點(diǎn)。

式中 ε值的大小影響特征點(diǎn)數(shù)目，通常是根據(jù)經(jīng)驗(yàn)值選取，大多數(shù)文獻(xiàn)選取ε為0.650，本文也取此值。

特征點(diǎn)描述[9]首先利用Haar小波濾波器確定描述的主方向，再以特征點(diǎn)為中心,以主方向?yàn)樗椒较虼_定4×4個(gè)描述的子區(qū)域；每個(gè)子區(qū)域中用Haar小波濾波器計(jì)算水平方向的響應(yīng)dx和豎直方向的響應(yīng) dy，得到 4 維向量(∑dx,∑dy,∑|dx|,∑|dy|)，把 4×4個(gè)子塊區(qū)域的向量連接起來(lái)就得到了一個(gè) 64維的特征點(diǎn)描述向量。

1.2 特征點(diǎn)匹配

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

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

當(dāng)RoD小于一個(gè)閾值threshold時(shí)，就認(rèn)為這對(duì)點(diǎn)是匹配點(diǎn)。threshold∈[0.5, 0.7]是個(gè)比較理想的范圍[9]，本文選取0.65。SURF算法匹配的具體過(guò)程如表1所示：

表1 特征點(diǎn)匹配算法Tab.1 The SURF feature point matching

2 SURF算法的降維實(shí)現(xiàn)方法

2.1 SURF算法的64維描述

SURF特征點(diǎn)描述是利用特征點(diǎn)周?chē)畔?lái)描述這個(gè)點(diǎn)。首先以特征點(diǎn)為中心，用尺寸為4S的Haar小波濾波器在以6S為半徑的圓形鄰域里，求得每個(gè)像素點(diǎn)的Haar小波響應(yīng)，然后用以特征點(diǎn)為中心的高斯函數(shù)(2Sσ=)對(duì)這些響應(yīng)進(jìn)行加權(quán)。用一個(gè)圓心角為/3π扇形（如圖1）以特征點(diǎn)為中心環(huán)繞一周，計(jì)算該扇形處于每個(gè)角度時(shí)，它所包括的圖像點(diǎn)的Haar小波響應(yīng)之和，取和值的最大值為該特征點(diǎn)所對(duì)應(yīng)的主方向。

圖1 滑動(dòng)的扇形窗口Fig.1 The fan widow for calculating direction

以特征點(diǎn)為中心、上述得到的主方向?yàn)樗椒较虻拇_定一個(gè)正方形領(lǐng)域，其邊長(zhǎng)為20S，把該正方形區(qū)域分成4× 4個(gè)子塊區(qū)域，每個(gè)子塊區(qū)域中用Haar小波濾波器處理。 dx表示水平方向的Haar小波響應(yīng)， dy表示豎直方向的 Haar小波響應(yīng)，在構(gòu)建描述子向量之前，對(duì)于所有的 dx、 dy都要用一個(gè)以特征點(diǎn)為中心的高斯函數(shù)加權(quán)，該高斯函數(shù)的σ= 3 .3S 。在每個(gè)子塊區(qū)域中對(duì) d求和，從而得到一個(gè) 4維向量把4× 4個(gè)子塊區(qū)域的向量連接起來(lái)就得到了一個(gè)64維的特征點(diǎn)描述向量。

2.2 降維實(shí)現(xiàn)方法

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

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

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

3 降維SURF算法性能分析

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

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

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

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

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

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

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

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

4 結(jié)論

本文通過(guò)改變SURF算法特征點(diǎn)描述的正方形鄰域的大小，實(shí)現(xiàn)了16維與4維的特征點(diǎn)SURF描述。實(shí)驗(yàn)結(jié)果表明，16維SURF描述用于圖像特征點(diǎn)匹配可以大幅降低匹配時(shí)間，并且大多數(shù)環(huán)境下匹配性能與原64維SURF相當(dāng)；僅不適合用于存在大量旋轉(zhuǎn)的環(huán)境下的圖像特征點(diǎn)匹配。4維 SURF描述的匹配效果大幅下降，不宜用于特征點(diǎn)匹配。但可以以擴(kuò)展到圖像的每個(gè)像素點(diǎn)，用于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] 劉博文, 童立靖. 基于多視角三維掃描數(shù)據(jù)的圖像配準(zhǔn)[J].軟件, 2016, 37(9): 29-32.

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

[12] 翁秀玲, 王云峰, 余小亮. 一種圖像立體匹配的誤匹配點(diǎn)剔除與校正方法[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系統(tǒng)；羅旌鈺(1994-)，男，碩士研究生，主要研究方向：SLAM系統(tǒng)。

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