一種基于非線性尺度空間的ORB特征匹配算法研究

摘 要：ORB（Oriented FAST and rotated BRIEF）特征描述算法具有旋轉(zhuǎn)不變性、匹配速度快的特點，但沒有解決尺度不變性、誤匹配率高的問題。針對此缺陷，提出一種改進的ORB特征點匹配算法，完成特征點的檢測、匹配以及剔除誤匹配。改進算法首先借鑒了A-KAZE基于非線性擴散濾波構建尺度空間的方法;其次利用ORB特征檢測子在所構建的非線性尺度空間進行特征點的檢測;再次對采集到的特征點生成特征描述子;最后在使用Hamming距離匹配的基礎上再對其結果采用PROSAC算法剔除噪聲點。實驗結果表明，改進后的算法相較于原ORB算法，有效地解決了ORB算法不具備尺度不變性的問題，且匹配精度大幅提高，適用于尺度變化較大且實時性高的環(huán)境，具有較好的工程意義。

關鍵詞：改進ORB算法;A-KAZE;非線性擴散濾波;尺度不變性;特征點匹配

中圖分類號：TP181

文獻標識碼： A

近年來，科學技術迅猛發(fā)展，值此方興未艾之際，計算機視覺技術應運而生，正不斷滲透到人們的日常生活中，其中比較重要的內(nèi)容就是圖像中特征點匹配算法的研究，它廣泛應用于多個領域中[1-3]，例如移動機器人導航、圖像拼接、三維重建以及醫(yī)學圖像分析等計算機視覺領域的基礎研究。目前最為廣泛的特征點匹配算法有SIFT[4]、SURF[5]、ORB[6]等。

LAWE[4]等人于1999年提出了尺度不變的特征變換SIFT（Scale￣invariant Feature Transform）算法，該算法基于特定興趣點而與圖像大小和旋轉(zhuǎn)無關，對于圖像旋轉(zhuǎn)、尺度縮放具有較好的穩(wěn)定性，同時對亮度、視角等條件的微小變化魯棒性強，但該算法的局部特征點檢測和描述子特征是建立在高維的基礎上，這使得整個過程計算量龐大、消耗時間多，難以滿足實時性的要求。為了克服上述不足，2006年BAY[5]等人基于SIFT的基礎上提出一種加速魯棒性特征SURF（Speeded Up Robust Feature）算法，由于SURF算法最大的特點在于采用了哈爾特征以及積分圖像的概念，這使得典型的SURF算子比SIFT算子快大概3倍左右，大大加快了程序執(zhí)行效率。機器視覺技術的發(fā)展使得人們更加關注特征匹配算法在執(zhí)行效率方面的性能，有大量學者研究表明，ORB算法的運行速度比上述兩種算法快至少一個數(shù)量級。該算法于2011年由RUBLEE[6]等人在ICCV上提出，它在特征點質(zhì)量和性能間取得了較好的折中。從實時性角度評測，它是目前運行速度較快的算法。ORB是一種局部不變特征檢測子，即圖像發(fā)生旋轉(zhuǎn)變換時仍可以保持很好的魯棒性，但對于圖像尺度變化較大的圖像，傳統(tǒng)ORB算法的匹配效果卻不理想[7]，由于該算法尺度空間的構建環(huán)節(jié)不夠成熟，當圖像尺度發(fā)生突變時，圖像特征匹配的精度會受影響。文獻[8-10]分別通過結合SIFT和SURF檢測算子使得改進后的ORB算法擁有尺度不變特性，但實時性和匹配精度難以兼得，可見對ORB的研究仍具有非常大的意義。

本論文提出一種基于非線性尺度空間的ORB特征匹配改進算法，該算法借鑒A-KAZE[11]（Accelerated-KAZE）算法思想對ORB進行改進，通過構建非線性尺度空間提取顯著特征點，使其對尺度變換的圖像具備較強的表現(xiàn)。與此同時，使用PROSAC[12]（漸進一致性采樣）對匹配點對提純，進而提高ORB算法的匹配質(zhì)量，從而達到不失精度的條件下滿足實時匹配的目的。

1 傳統(tǒng)的ORB算法

ORB算法具有局部不變性，該算法采用以速度著稱的加速分割測試特征FAST[6]（Feature From Accelerated Segment Test）檢測特征點，利用旋轉(zhuǎn)二進制魯棒基元獨立特征BRIEF[6]（Binary robust independent elementary feature）算法生成描述符，再以Hamming距離為相似性度量準則比較描述符完成粗匹配。其主要步驟如下：

（1）關鍵點提?。翰捎胦-FAST算法進行關鍵點提取，加入Rosin灰度質(zhì)心法（Intensity Centroid）為其提供方向特性，使得后面的特征描述符具有方向信息;

（2）建立特征描述符：ORB算子采用具備旋轉(zhuǎn)角度的改進BRIEF算法，即rBRIEF算法。其主要思想是依據(jù)像素點灰度值的大小，利用隨機選點機制在某個特征點的周邊選取一定數(shù)量的像素點對測試集，生成二進制串描述符;（3）特征點粗匹配：以Hamming距離作為相似性度量準則對描述子進行比較，若滿足一定的條件則認為該特征點匹配對是正確的。該方法原理簡單易于操作。

2 改進的ORB特征匹配算法

本文提出的一種基于非線性尺度空間的改進ORB算子，其主要流程如1所示。

首先借鑒A-KAZE[8]算法原理利用FED數(shù)值分析框架來求解可變傳導擴散方程，進而完成非線性尺度空間的構建;其次采用FAST-9算法在非線性尺度空間的每一層進行特征點的檢測并計算特征點的質(zhì)心方向;再次結合之前獲取的具有方向特性的特征點，采用rBRIEF算法生成具有二進制字符串特點的特征描述子;最后使用FLANN方法計算漢明距離進行特征點的粗匹配，再對其匹配結果采用PROSAC算法（改進的RANSAC算法）剔除噪聲點，實現(xiàn)更加精準的匹配。

2.1 尺度空間的構建

由于傳統(tǒng)的ORB算法沒有很好的解決尺度不變性，所以在進行角點檢測之前要對其構建尺度空間。傳統(tǒng)的基于Gaussian尺度空間的構建存在最大的缺陷就是高斯濾波無法保留邊緣、邊界、細節(jié)信息，它會把所有尺度的細節(jié)和噪聲平滑到相同的水平，這導致其位置精度和獨特性大打折扣。而基于A-KAZE算法的非線性尺度分解有望解決上述不足。

2.1.1 非線性擴散

鑒于傳統(tǒng)的正向歐拉法在求解非線性方程數(shù)值時，迭代收斂步長非常短、消耗時間資源很大導致計算復雜度高。針對上述不足，本文在構建一個類似金字塔型的非線性尺度空間來求解非線性濾波擴散方程時，采用快速顯示擴散FED[13]（Fast explicit diffusion）算法。可以通過非線性偏微分方程來描述傳導方程：

2.2 特征點檢測

ORB算法采用改進的FAST算法（oFAST）進行角點檢測，早期的Harris和SIFT特征點提取算法都是基于自相關矩陣響應值的算法，一般會涉及到卷積運算，導致運算量龐大，F(xiàn)AST算法剛好克服了這方面的缺陷。ROSTEN等人于文獻[15]給出FAST的定義：在某個候選像素點的圓形范圍內(nèi)，通過比較該點與鄰域點的灰度差值來判別該點是否為特征點。具體的特征提取過程如下：

（1）確定檢測范圍：如圖2所示，以像素點P為圓心，以3個像素單位為半徑畫圓，選取圓上16個像素點為待檢測的點。

（2）設定合適閾值：將上述（1）中待檢測的16個像素點的灰度值與P點灰度值逐一比較，兩點灰度值之差的絕對值大于某一閾值εd，則認為這兩點是不同的點。特征點的響應函數(shù)如下：

2.3 特征點描述

ORB算法采用改進的BRIEF算法（rBRIEF）建立描述符，其核心思想是采用隨機選點機制在圖像中選取像素點，通過比較它們的灰度值從而得到描述符。其具體過程如下：

（1）為消除原BRIEF描述符以像素為測試點所帶來的噪聲影響，改進算法在特征描述過程中，是以特征點為中心設定鄰域為31×31像素的圖像塊，以此作為測試點集的候選區(qū)域。每次測試都是在一個5×5的子窗口內(nèi)隨機選取一個點對（x，y），使用如下準則進行二進制賦值：

通過greedy貪婪算法搜索出具有較高方差和較低相關性的n個（文獻[6]中n=256）點對作為最終的描述符，大的方差和不相關性有利于描述符保持較大區(qū)分性和描述能力的特性，為后續(xù)的特征匹配打好基礎。

2.4 特征點匹配

上節(jié)求得的特征描述符是一個二進制碼串，這里先對其采用Hamming距離快速近似最近鄰（FLANN）方法進行粗匹配。由于外界噪聲因素的影響，粗匹配后的結果仍存在很多偽匹配對，影響匹配效果。故采用PROSAC算法剔除外點，從而提高匹配質(zhì)量。

其中粗匹配中采用原理簡單、操作方便的FLANN算法，該算法在OpenCV庫中現(xiàn)已集成。由于RANSAC算法在剔除外點的過程中沒有考慮特征點間的差異性，其隨機抽樣模式會帶來迭代次數(shù)不穩(wěn)定、浪費大量計算資源等弊端。本文采用PROSAC算法對特征點粗匹配對進行優(yōu)化，該方法對包含較多離群點的數(shù)據(jù)仍然適用。其核心思想是依據(jù)一定準則將樣本點進行降序排列，在較高匹配率的粗匹配子集中計算模型，從而減少迭代次數(shù)，最優(yōu)估計解也會盡早出現(xiàn)。算法流程如下：

3 實驗設置、結果及分析

實驗一：針對本文所提出的改進算法，設計了兩類實驗：（1）尺度不變性對比實驗;（2）綜合不變性對比實驗，即尺度和旋轉(zhuǎn)角度同時改變的情況下進行的實驗。使用上述兩類實驗，分別對兩組圖像進行測試，其中輸入的原始圖像格式為.png，像素大?。?50×750，兩張圖像分別取自室內(nèi)和室外環(huán)境。

3.1 尺度不變性測試結果分析

通過圖3、圖4中的（a）、（b）對比實驗以及表1不難發(fā)現(xiàn)，采用ORB算法的測試效果圖中，未提純前成功匹配的特征點對數(shù)目偏少，分別為361、329，提純后正確匹配的點對數(shù)量分別為288、257，其正確匹配率分別為80%和78%。而采用改進算法的測試效果圖中，未提純前成功匹配的特征點對數(shù)目較多，分別為428、413，提純后正確匹配的點對數(shù)量分別為398、376，其正確匹配率分別為93%和91%。相較于原算法，改進算法采用快速的FED算子來提高尺度空間的構建速度，并且沿用了ORB特征檢測算法。在有效特征點數(shù)目增多的情況下，平均匹配精度提升了13%。但由于添加了PROSAC算法二次剔除誤匹配點，相較于原ORB算法，運行時間平均增加了21.2 ms。

3.2 綜合不變性測試結果分析

圖5、圖6是針對圖像旋轉(zhuǎn)、多尺度的綜合測試效果圖。表2是針對匹配精度和算法執(zhí)行時間方面進行的定量分析。結合表2和兩組（a）、（b）對比圖可以看出，采用原算法的測試效果圖中，未提純前成功匹配的特征點對數(shù)量分別為341、314，提純后正確匹配的點對數(shù)目分別為276、236，其準確率分別為81%和75%。而采用改進算法的測試效果圖中，未提純前成功匹配的特征點對數(shù)量分別為423、408，提純后正確匹配的點對數(shù)目分別為389、359，其準確率分別為92%和88%。由此可得，改進算法提取到的特征點更加豐富，且增加了二次提純特征點匹配對的環(huán)節(jié)，因此在匹配精度上平均提升了12%，在運行時間上平均增加了23.47 ms，但不影響實際應用中算法的實時性。

由圖7不難發(fā)現(xiàn)，改進算法相較于原ORB算法，在尺度不變性方面魯棒性更強，且角點檢測更加穩(wěn)定。

4 結語

本文針對ORB算法沒有解決尺度不變性、誤匹配率高等問題，提出優(yōu)化算法。首先通過借鑒A-KAZE算法原理構建非線性尺度空間，其次沿用ORB算子在每層尺度空間的圖像上進行特征提取并計算描述子，再次使用FLANN算子和PROSAC算法雙重篩選原則剔除誤匹配，最終得到匹配質(zhì)量較高的結果。實驗結果表明，改進算法有效地解決了尺度不變性的問題，提取到的特征點在細節(jié)和邊緣方面處理得更好，并且匹配精確度和算法效率得到了一定改善，適用于匹配精度高、尺度變化較大的應用場景。

參考文獻：

[1]SINHA S N， FRAHM J M， POLLEFEYS M， et al. Feature tracking and matching in video using programmable graphics hardware[J]. Machine Vision and Application， 2011， 22（1）： 207-217.

[2]丁文東，徐德，劉希龍，等. 移動機器人視覺里程計綜述[J]. 自動化學報，2018，44（03） ： 385-400.

[3]NASROLLAHI K， MOESLUND T B. Super￣resolution： a comprehensive survey [J]. Machine Vision and Applications， 2014， 25（6）： 1423-1468.

[4]LOWE D G. Distinctive image features from scale￣invariant keypoints [J].International Journal of Computer Vision，2004，60（2） ： 91-110.

[5]BAY H， ESS A， TUYTELAARS T， et al. Speeded￣up robust features （SURF） [J]. Computer Vision and Image Understanding， 2008， 110（3）： 346-359.

[6]RUBLEE E，RABAUD V，KONOLIGE K，et al.ORB： an efficient alternative to SIFT or SURF[C]// Proceedings ofnbsp; 2011 IEEE International Conference on Computer Vision. Washington： IEEE，2011： 2564-2571.

[7]ZHAO H Y， ZHAO H C， LV J F， et al. Multimodal image matching based on Multimodality Robust Line Segment Descriptor [J]. Neurocomputing， 2016， 177： 290-303.

[8]王健，于鳴，任洪娥. 一種用于圖像拼接的改進ORB算法[J]. 液晶與顯示，2018，33（06） ：520-527.

[9]鄧仕雄，王曉紅，劉繼庚，等. 基于SURF算法和極線約束的無人機影像匹配研究[J]. 貴州大學學報（自然科學版），2018，35（01）： 35-39.

[10]張明浩，楊耀權，靳渤文. 基于圖像增強技術的SURF特征匹配算法研究[J]. 自動化與儀表，2019，34（09）： 98-102.

[11]ALCANTARILLA P F， JESU N， BARTOLI A. Fast explicit diffusion for accelerated features in nonlinear scale spaces[C]. Electronic Proceedings of British Machine Vision Conference. Bristol： BMVC， 2013： 1-11.

[12]CHUM O， MATAS J. Matching with PROSAC￣progressive sample consensus[C]//2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR， 2005， 1： 220-226.

[13]WEICKERT J， GREWENIG S， SCHROERS C， et al. Cyclic schemes for PDE-based image analysis [J]. International Journal of Computer Vision， 2016， 118（3）： 275-299.

[14]GREWENIG S， WEICKERT J， BRUHN A. From box filtering to fast explicit diffusion [J]. Lecture Notes in Computer Science， 2010， 6376： 533-542.

[15]ROSTEN E，PORTER R，DRUMMOND T.Faster and Better： a machine learning approach to corner detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（1） ： 105-119.

[16]張巖，李建增，李德良，等. 快速穩(wěn)健的自適應非線性尺度特征檢測子[J]. 系統(tǒng)工程與電子技術，2016，38（11）： 2678-2684.

（責任編輯：于慧梅）