SURF和RANSAC的特征圖像匹配

王衛(wèi)兵　白小玲　徐倩

摘要：針對圖像匹配過程中存在匹配運(yùn)行時間長、匹配正確率低的問題，采用隨機(jī)采樣一致性（random sample consensus， RANSAC）算法優(yōu)化加速魯棒特征（speed up robust features， SURF）的方法，提出一種適應(yīng)性強(qiáng)的優(yōu)化匹配算法。首先使用SURF算子進(jìn)行特征檢測和特征描述，再使用鄰近算法對特征點(diǎn)進(jìn)行預(yù)匹配，最后使用隨機(jī)采樣一致性（RANSAC）算法優(yōu)化匹配結(jié)果。在相同的實(shí)驗環(huán)境中通過對尺度不變特征變換（scale invariant feature transform， SIFT）算法、SURF算法和提出的優(yōu)化算法進(jìn)行比較，優(yōu)化算法較SIFT算法和SURF算法分別減少匹配點(diǎn)對數(shù)38對和18對，剔除了誤匹配點(diǎn)，提高了匹配正確率并減少了算法的運(yùn)行時間。

關(guān)鍵詞：特征提??；加速魯棒特征；隨機(jī)采樣一致性

DOI：10.15938/j.jhust.2018.01.021

中圖分類號： TP391.4

文獻(xiàn)標(biāo)志碼： A

文章編號： 1007-2683（2018）01-0117-05

Abstract：Aiming at the problem of long running time and low matching accuracy in image matching process， random sample consensus （RANSAC） algorithm is used to optimize the speedup of robust features （SURF） optimization algorithm. As a result， an adaptable algorithm is proposed to optimize image matching. Firstly， the SURF operator is used for feature detection and feature description. Then the neighbor algorithm is used to prematch the feature points. Finally， the random sampling consistency （RANSAC） algorithm is used to optimize the matching results. The scale invariant feature transform （SIFT） algorithm， SURF algorithm， and the proposed optimization algorithm are compared in the same experimental environment. Compared with the SIFT algorithm and the SURF algorithm， the optimization algorithm reduces the number of matching point pairs to 38 and 18 pairs， excluding mismatched points， improving the matching accuracy， and reducing the running time of the algorithm.

Keywords：feature matching；speed up robust features；random sample consensus

0引言

特征點(diǎn)檢測、特征描述和特征匹配是基于局部特征點(diǎn)的圖像匹配技術(shù)的三個主要組成部分，廣泛地應(yīng)用在醫(yī)療、圖像檢索、目標(biāo)識別和增強(qiáng)現(xiàn)實(shí)技術(shù)中[1-5]。

目前，研究人員提出了許多不同的特征點(diǎn)檢測、描述算法，但由于圖像成像時往往會受到光照、模糊、角度等各種因素的影響，導(dǎo)致匹配速度慢、匹配精度差等問題。

DavidLowe在1999年發(fā)表了SIFT（scale invariant feature transform）算法[6-7]，并在2004年對其進(jìn)行完善。SIFT算法在空間尺度中尋找極值點(diǎn)，通過直方圖確定主方向，使其具有旋轉(zhuǎn)不變形，同時對光照、縮放等變換也有一定的魯棒性。但由于SIFT算法在檢測和描述過程中使用的算法復(fù)雜度高，使得算法的匹配速度慢，達(dá)不到實(shí)時的要求。在2006年，Bay和Ess等人對SIFT算子進(jìn)行改進(jìn)，提出了加速魯棒特征—SURF（Speed Up Robust Features）算法[8-10]，該算法通過H矩陣判別式的值來獲得極值點(diǎn)，并在不同尺度上計算近似Harr小波特征，即使是在多幅圖片下也可以具有良好的穩(wěn)定性。索春寶等人針對現(xiàn)有的幾種常用特征檢測和描述算子進(jìn)行性能對比，實(shí)驗結(jié)果表明，SURF算法是性能最為魯棒的局部特征算法[11-13]。對比于SIFT算法，該算法的描述符的維度下降了一倍，在二階微分模板的構(gòu)建過程中得以簡化，使得程序的運(yùn)行時間被縮短[14]。

本文通過SURF算法進(jìn)行圖像的檢測、描述，使用KNN（KNearest Neighbor）[15]算法進(jìn)行預(yù)匹配，在匹配過程中出現(xiàn)的錯誤匹配使用Ransac算法進(jìn)行優(yōu)化，更準(zhǔn)確的完成圖像匹配的整個過程。Ransac算法可以做到在匹配過程中降低不可靠的匹配點(diǎn)對數(shù)，確保匹配的正確率。

1.2SURF尺度空間及特征向量提取

在計算機(jī)視覺領(lǐng)域中，尺度空間需要對輸入圖像函數(shù)反復(fù)與高斯函數(shù)核進(jìn)行卷積并反復(fù)對其進(jìn)行二次抽樣，這種方法被稱為一個圖像金字塔。在SIFT算法的特征檢測過程中，構(gòu)建的金字塔中是有很多層的，并且在每個層中會有幾張尺度不同的圖片，下一組的圖像是由通過將上一組圖像按照隔點(diǎn)降采樣得到。這樣就使得每層圖像都要依賴于前一層的圖像，因此，在不斷的隔點(diǎn)采樣過程中會使得運(yùn)算量比較大，這樣在特征點(diǎn)的檢測過程中也就需要花費(fèi)更長的時間。而在SURF算法中是保持圖像的大小是一直不變的，SURF的不同層的圖像是通過改變高斯模糊的尺寸得到的，在尺度空間中可以實(shí)現(xiàn)多層圖像同時被處理，不需要對圖像進(jìn)行二次抽樣，減少了特征點(diǎn)檢測過程中的繁瑣過程，加快了檢測的速度。SIFT算法的金字塔結(jié)構(gòu)變化的是圖像的尺寸，通過不斷的隔點(diǎn)降采樣實(shí)現(xiàn)整個金字塔結(jié)構(gòu)，并且為了消除噪音，還需要反復(fù)使用高斯函數(shù)對子層進(jìn)行平滑處理，而SURF算法只是改變?yōu)V波器的大小，卻可以使原始圖像保持不變。其金字塔圖像如圖2所示。

SIFT算子的旋轉(zhuǎn)不變性是特征點(diǎn)的重要特性，SIFT通過統(tǒng)計梯度直方圖來確定特征點(diǎn)的主方向，在主方向確定后，依據(jù)其旋轉(zhuǎn)就可以確保旋轉(zhuǎn)不變性。梯度直方圖是按照每10度一個柱，這樣就可以統(tǒng)計36個柱中的直方圖最大值來作為特征點(diǎn)的主方向。在SURF算法中，特征點(diǎn)的主方向確定是以特征點(diǎn)為圓心、6s（s為特征點(diǎn)的尺度）為半徑的鄰域內(nèi)構(gòu)建的一個扇形面，得到x和y方向的Harris小波響應(yīng)，將不同的高斯權(quán)重系數(shù)賦給這些響應(yīng)值，這樣越靠近特征點(diǎn)，響應(yīng)的貢獻(xiàn)也就越大；然后以60°為基準(zhǔn)進(jìn)行統(tǒng)計扇形內(nèi)所有的點(diǎn)的水平方向harrx小波特征和垂直方向的harry小波特征的總和，Harris小波的尺寸變?yōu)?s，這樣扇形得到了一個值。然后60°扇形以一定間隔旋轉(zhuǎn)，最后扇形方向最大值就是作為特征點(diǎn)的主方向。

確定了特征點(diǎn)的主方向后，就可以進(jìn)行特征描述符的提取。在SIFT算法中計算關(guān)鍵點(diǎn)周圍16×16的窗口中每一個像素的梯度，在每個4×4的1/16象限中，直方圖有8個方向區(qū)間，將加權(quán)梯度值加到其中的一個方向區(qū)間上，計算出一個梯度方向直方圖。這樣就可以最后得到4×4×8=128維的向量作為該點(diǎn)的SIFT描述子。而在SURF中，是在特征點(diǎn)周圍取一個邊長為20s（s是所檢測到該特征點(diǎn)所在的尺度）的正方形框。該框的方向作為檢測出的主方向，正方框被分成為16個子區(qū)域，去統(tǒng)計每個區(qū)域25個像素的水平方向和垂直方向的Harris小波特征，分別記為dx和dy，再將權(quán)重系數(shù)通過高斯窗口函數(shù)賦給響應(yīng)值，得到一個四維的矢量：V=∑dx，∑dx，∑dy，∑dy，這樣就可以得到SURF的描述維數(shù)是4×4×4=64維。最后，對向量進(jìn)行歸一化處理，就進(jìn)一步去除了光照的影響，得到特征描述符，如圖3所示。

2特征匹配

根據(jù)上文，采用Hessian矩陣提取出適量特征點(diǎn)并得到其主方向，再通過Harris小波特征得到SURF的64維描述子。在匹配過程中，首先采用FLANN（Fast Library for Approximate Nearest Neighbors）算法，對特征點(diǎn)對進(jìn)行預(yù)匹配，匹配過程中出現(xiàn)的誤匹配再通過Ransac算法進(jìn)行剔除。

2.1特征點(diǎn)對預(yù)匹配

在OpenCv開源庫中，有兩種二維的特征點(diǎn)匹配常見的辦法，分別是Brute Force匹配和FLANN匹配，而本文采用的是FLANN匹配[17-18]。它們分別對應(yīng)BFMatcher和FlannBasedMatcher。之所以會選擇FLANN匹配是因為前者總是嘗試所有可能的匹配，從而使得它總能找到最佳匹配，但是會使得算法運(yùn)行時間長；而后者是一種近似法，算法更快。同時為了進(jìn)行高效匹配，本文還采用鄰近算法（KNN），選取與當(dāng)前點(diǎn)距離最小的n個點(diǎn)，本文中經(jīng)測試選定n值為2效果佳。

2.2RANSAC匹配

RANSAC算法[19-20] 最早由Fischler和Bolles于1981年提出，是一種魯棒的參數(shù)估計方法。該算法的數(shù)學(xué)模型參數(shù)估計是通過迭代方式完成的，即使在參數(shù)中會有包含“局外點(diǎn)”的數(shù)據(jù)集。本文中的“局外點(diǎn)”可能是在檢測、描述和預(yù)匹配過程中所產(chǎn)生的錯誤匹配或者誤差比較大的匹配所產(chǎn)生的。該算法可以接受在構(gòu)建金字塔過程中產(chǎn)生的圖像噪音，能較好的剔除誤匹配點(diǎn)，SURF匹配對通過RANSAC幾何校驗后可以有效濾除錯誤匹配，從而使得集合RANSAC的SURF性能更加優(yōu)良，應(yīng)用更加廣泛[21-22]。但它也有缺點(diǎn)，該算法是一種不確定的算法，是否可以得到合理的結(jié)果是未知數(shù)，所以為了提高得到合理結(jié)果的概率就需要提高迭代次數(shù)。該算法在計算參數(shù)的迭代次數(shù)時是沒有上限的，因為如果設(shè)置迭代次數(shù)的上限，可能會導(dǎo)致得到的結(jié)果不是最優(yōu)的結(jié)果，還可能得到錯誤的結(jié)果。在匹配過程中，迭代次數(shù)應(yīng)按照實(shí)際情況進(jìn)行選擇。為進(jìn)一步提高RANSAC的準(zhǔn)確度，可以對RANSAC算法進(jìn)行簡化。在簡化的過程中會減少匹配點(diǎn)數(shù)，提高匹配的正確率，本文采用的是雙向匹配。

匹配的過程是首先要分別讀入兩幅圖像1、2，對兩幅圖像分別進(jìn)行特征點(diǎn)檢測，得到特征點(diǎn)數(shù)組points1和points2。然后對每個points1中的點(diǎn)j在points2中找出對應(yīng)的點(diǎn)k，并在points2中的每個點(diǎn)m在points1中找對應(yīng)點(diǎn)n。判斷是否匹配的依據(jù)是在points1中的點(diǎn)j，如果在points2中的匹配點(diǎn)是k，并且points2中點(diǎn)k在points1中的匹配點(diǎn)也是j，那么判斷為匹配成功，這樣匹配的點(diǎn)對數(shù)會有所減少，但是匹配的準(zhǔn)確率會得到提高。

3仿真實(shí)驗

本文的算法對比結(jié)果均在CPU為英特爾i53470，3.20GHz，內(nèi)存為4.00GB的Lenovo 64位工作站上運(yùn)行得到。操作系統(tǒng)為Windows7，開發(fā)工具為VS2012 IDE，并采用Opencv2.4.10圖像處理庫。

本文使用兩組匹配圖像，圖4是老鼠圖形測試圖像，該圖像對存在一定的縮放變換，圖5是建筑物圖形的測試圖像，該圖像對存在一定的視角變換。文中通過對初始圖像作尺度、旋轉(zhuǎn)變化來觀察圖像在SIFT、SURF和本文算法中的圖像匹配結(jié)果。下面列出2組不同圖像的匹配結(jié)果。

本文實(shí)驗是在相同環(huán)境中對SIFT算法、SURF算法和本文所提出的算法從匹配的準(zhǔn)確性和運(yùn)行時間兩方面進(jìn)行比較。從表一中可以看出：對同一對測試圖像來說，SIFT檢測到的特征點(diǎn)總點(diǎn)數(shù)要多于SURF算法和本文優(yōu)化算法的特征點(diǎn)數(shù)，其中本文算法檢測到的特征點(diǎn)數(shù)最少；SIFT算法的運(yùn)行時間也要多于SURF算法和本文算法，其中本文算法的運(yùn)行時間最短。從表1中得到的結(jié)果可以反映出本文的優(yōu)化算法從匹配正確性和運(yùn)行時間兩方面的性能更優(yōu)。

圖4和圖5分別是老鼠和建筑物的圖像匹配結(jié)果，依次為SIFT算法、SURF算法和本文算法的匹配結(jié)果。從圖中可以看出：圖4和圖5中，本文算法較SIFT算法去除了不顯著的匹配點(diǎn)39個，較SURF算法去除了不顯著的匹配點(diǎn)18個，減少匹配點(diǎn)的數(shù)目，匹配率較SIFT算法和SURF算法分別提高了14.2%和6.4%。從表1中數(shù)據(jù)可以看出，本文算法的匹配點(diǎn)對數(shù)更少、匹配正確率更高并且匹配的時間有所減少。

4結(jié)論

本文首先用SURF算法進(jìn)行特征檢測和描述，再使用KNN算法進(jìn)行預(yù)匹配，在匹配過程中產(chǎn)生的誤匹配通過簡化的Ransac算法進(jìn)行剔除。通過對圖像進(jìn)行旋轉(zhuǎn)、縮放等圖像變化下的實(shí)驗數(shù)據(jù)分析，本文算法要優(yōu)于SIFT算法和SURF算法。未來的研究工作將在匹配效率上進(jìn)行改進(jìn)，圖像匹配是增強(qiáng)現(xiàn)實(shí)（Augmented Reality，簡稱AR）技術(shù)中的一個重要環(huán)節(jié)，希望今后的工作能實(shí)現(xiàn)增強(qiáng)現(xiàn)實(shí)過程中更快更穩(wěn)定的特征匹配。

參 考 文 獻(xiàn)：

[1]常青，張斌，邵金玲.基于SIFT和RANSAC的特征圖像匹配方法[J].華東理工大學(xué)學(xué)報：自然科學(xué)版，2012，38（6）：747-751.

[2]邱子鑒.基于改進(jìn)隨機(jī)蕨的增強(qiáng)現(xiàn)實(shí)跟蹤注冊算法的設(shè)計與實(shí)現(xiàn)[D].哈爾濱：哈爾濱理工大學(xué)學(xué)報，2014：8-11.

[3]邢春.基于多特征融合圖像檢索系統(tǒng)設(shè)計與實(shí)現(xiàn)[D].哈爾濱理工大學(xué)：哈爾濱理工大學(xué)學(xué)報，2012：13-18.

[4]王邦國.基于SIFT特征點(diǎn)精確匹配的圖像拼接技術(shù)研究[J].大連大學(xué)學(xué)報，2015，36（3）：23-26.

[5]曹健，陳紅倩，毛典輝，等.基于局部特征的圖像目標(biāo)三個i別問題綜述[J].中南大學(xué)學(xué)報，2013，44（2）：259-262.

[6]LOWE. DAVID G.Distinctive Image Features from Scaleinvariant Key Points[J]. International Journal of Computer Vision，2004，14（5）：91-110.

[7]LOWE. DAVID G.Object Recognition from Local ScaleInvariant Features[J].Computer Science Department University of Columbia，2004，10（6）：2-8.

[8]BAY Herbert. SURF： Speeded up Robust Features[J]. European Conference on Computer Vision（ECCV），2006，17（7）：404-417.

[9]YAN Yuanhui，XIA Haiying，HUANG Siqi，etc.An Improve Matching Algorithm for Feature Points Matching[J].College of electronic engineering，2014，15（6）：241-246.

[10]蔡佳，黃攀峰.基于改進(jìn)SURF和PKLT算法的特征點(diǎn)實(shí)時跟蹤方法研究[J].航空學(xué)報，2013，34（5）：1205-1211.

[11]索春寶，楊東清，劉云鵬.多種角度比較SIFT、SURF、BRISK、ORB、FREAK算法[J].北京測繪，2014，6（4）：22-26.

[12]蔣賢明，宋樹祥，王冬旭.局部圖像特征提取算法的性能比較[J].廣西物理，2014，35（1）：16-20.

[13]王燦進(jìn)，孫濤，陳娟.基于FREAK特征的快速景象匹配[J].電子測量與儀器學(xué)報，2015，8（29）：205-214.

[14]朱俊.基于幾何特征配準(zhǔn)的圖像魯棒拼接算法[J].南京理工大學(xué)學(xué)報，2014，7（9）：31-40.

[15]蔡佳，黃攀峰.基于改進(jìn)SURF和PKLT算法的特征跟蹤方法研究[J].航空學(xué)報，2013，32（6）：1205-1213.

[16]潘麗芳，楊炳儒.基于簇的K最近鄰（KNN）分類算法研究[J].計算機(jī)工程與設(shè)計，2009，30（18）：4260：4262.

[17]馮亦東，孫躍.基于SURF特征提取和FLANN搜索的圖像匹配算法[J].圖形圖像學(xué)報，2015，25（7）：651-654.

[18]趙璐璐，耿國華，李康，等.基于SURF和快速近似最近領(lǐng)搜索的圖像匹配算法[J].計算機(jī)應(yīng)用研究，2013，30（3）：922-925.

[19]FISCHER MA， BOLLS RC. Random Sample Consensus： A Paradigm for Model Fitting Matching with Applications to Image Analysis and Automated Cartography[J]. ACM Graphics and Image Processing，1981，25（6）：381-395.

[20]趙燁，蔣建國，洪日昌.基于RANSAC的SIFT匹配優(yōu)化[J].光電工程，2014，16（8）：59-67.

[21]陳藝蝦，孫權(quán)森，徐煥宇，等. SURF算法和RANSAC算法相結(jié)合的遙感圖像匹配方法[J].南京理工大學(xué)學(xué)報，2012，14（8）：823-827.

[22]谷宗運(yùn)，譚紅春，殷云霞，等.基于SURF和改進(jìn)的RANSAC算法的醫(yī)學(xué)圖像配準(zhǔn)[J].醫(yī)學(xué)影像工程學(xué)學(xué)報，2014，19（6）：471-475.

（編輯：王萍）