SURF和RANSAC的特征圖像匹配

王衛兵　白小玲　徐倩

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

關鍵詞：特征提取；加速魯棒特征；隨機采樣一致性

DOI：10.15938/j.jhust.2018.01.021

中圖分類號： TP391.4

文獻標志碼： 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引言

特征點檢測、特征描述和特征匹配是基于局部特征點的圖像匹配技術的三個主要組成部分，廣泛地應用在醫療、圖像檢索、目標識別和增強現實技術中[1-5]。

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

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

本文通過SURF算法進行圖像的檢測、描述，使用KNN（KNearest Neighbor）[15]算法進行預匹配，在匹配過程中出現的錯誤匹配使用Ransac算法進行優化，更準確的完成圖像匹配的整個過程。Ransac算法可以做到在匹配過程中降低不可靠的匹配點對數，確保匹配的正確率。

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

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

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

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

2特征匹配

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

2.1特征點對預匹配

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

2.2RANSAC匹配

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

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

3仿真實驗

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

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

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

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

4結論

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

參 考 文 獻：

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

[2]邱子鑒.基于改進隨機蕨的增強現實跟蹤注冊算法的設計與實現[D].哈爾濱：哈爾濱理工大學學報，2014：8-11.

[3]邢春.基于多特征融合圖像檢索系統設計與實現[D].哈爾濱理工大學：哈爾濱理工大學學報，2012：13-18.

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

[5]曹健，陳紅倩，毛典輝，等.基于局部特征的圖像目標三個i別問題綜述[J].中南大學學報，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]蔡佳，黃攀峰.基于改進SURF和PKLT算法的特征點實時跟蹤方法研究[J].航空學報，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]王燦進，孫濤，陳娟.基于FREAK特征的快速景象匹配[J].電子測量與儀器學報，2015，8（29）：205-214.

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

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

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

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

[18]趙璐璐，耿國華，李康，等.基于SURF和快速近似最近領搜索的圖像匹配算法[J].計算機應用研究，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匹配優化[J].光電工程，2014，16（8）：59-67.

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

[22]谷宗運，譚紅春，殷云霞，等.基于SURF和改進的RANSAC算法的醫學圖像配準[J].醫學影像工程學學報，2014，19（6）：471-475.

（編輯：王萍）