郭 芮，許 鋼，李若楠，趙春葉，江娟娟

(安徽工程大學 檢測技術與節(jié)能裝置安徽省重點實驗室，安徽 蕪湖 241000)

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

LAWE[4]等人于1999年提出了尺度不變的特征變換SIFT(Scale-invariant Feature Transform)算法，該算法基于特定興趣點而與圖像大小和旋轉無關，對于圖像旋轉、尺度縮放具有較好的穩(wěn)定性，同時對亮度、視角等條件的微小變化魯棒性強，但該算法的局部特征點檢測和描述子特征是建立在高維的基礎上，這使得整個過程計算量龐大、消耗時間多，難以滿足實時性的要求。為了克服上述不足，2006年BAY[5]等人基于SIFT的基礎上提出一種加速魯棒性特征SURF(Speeded Up Robust Feature)算法，由于SURF算法最大的特點在于采用了哈爾特征以及積分圖像的概念，這使得典型的SURF算子比SIFT算子快大概3倍左右，大大加快了程序執(zhí)行效率。機器視覺技術的發(fā)展使得人們更加關注特征匹配算法在執(zhí)行效率方面的性能，有大量學者研究表明，ORB算法的運行速度比上述兩種算法快至少一個數(shù)量級。該算法于2011年由RUBLEE[6]等人在ICCV上提出，它在特征點質量和性能間取得了較好的折中。從實時性角度評測，它是目前運行速度較快的算法。ORB是一種局部不變特征檢測子，即圖像發(fā)生旋轉變換時仍可以保持很好的魯棒性，但對于圖像尺度變化較大的圖像，傳統(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算法的匹配質量，從而達到不失精度的條件下滿足實時匹配的目的。

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

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

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

(2)建立特征描述符：ORB算子采用具備旋轉角度的改進BRIEF算法，即rBRIEF算法。其主要思想是依據(jù)像素點灰度值的大小，利用隨機選點機制在某個特征點的周邊選取一定數(shù)量的像素點對測試集，生成二進制串描述符；

(3)特征點粗匹配：以Hamming距離作為相似性度量準則對描述子進行比較，若滿足一定的條件則認為該特征點匹配對是正確的。該方法原理簡單易于操作。

2 改進的ORB特征匹配算法

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

圖1 改進ORB算法流程圖Fig.1 Improved ORB algorithm flow chart

首先借鑒A-KAZE[8]算法原理利用FED數(shù)值分析框架來求解可變傳導擴散方程，進而完成非線性尺度空間的構建；其次采用FAST-9算法在非線性尺度空間的每一層進行特征點的檢測并計算特征點的質心方向；再次結合之前獲取的具有方向特性的特征點，采用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)算法?？梢酝ㄟ^非線性偏微分方程來描述傳導方程：

(1)

式(1)中，div和L分別為散度與圖像L的梯度求解操作，c(x,y,t)為傳導擴散函數(shù)；L為圖像的亮度矩陣；時間t為尺度因子，其值越大代表圖像越簡單且尺度越大；其中傳導方程中引用的函數(shù)c依賴于圖像局部差分結構形式的張量或標量，使得擴散能夠自適應于圖像局部特性，公式定義如下：

c(x,y,t)=g(|Lσ(x,y,t)|)

(2)

(3)

(4)

(5)

式(3)～(5)中參數(shù)λ為閾值，是控制擴散級別的對比度因子，決定了圖像平滑過程中保留邊緣信息量的多少，其值與保留的邊緣信息量呈負相關。本文的參數(shù)λ取值為70%比例的梯度直方圖。根據(jù)大量實驗得知式(4)所表示的擴散系數(shù)比較容易計算，所以也很常用。

2.1.2快速顯示擴散算法

A-KAZE算法的尺度空間構造與SIFT類似，該算法提出的FED集顯式和半隱式理論的優(yōu)勢于一體。此外，采用顯式理論分解盒子濾波[14]來近似高斯濾波器,該技術的實現(xiàn)借鑒了積分圖像的思想原理，使得計算的復雜度降低，更加便于應用。其本質思想是將圖像金字塔分為O個組和S個組內子層，M=O×S是濾波后整個尺度空間包含的圖像總量。且在M次循環(huán)操作中每次循環(huán)皆為一個n次的迭代過程，我們定義第j次的迭代步長為：

(6)

式(6)中τmax為顯示求解穩(wěn)定條件范圍內的最大閾值步長。利用FED算子可以將(1)式用矢量化矩陣表示為：

(7)

式(7)中，τ為常量，控制顯示擴散的穩(wěn)定條件；A(Li)為圖像亮度在第i層上的傳導矩陣，且在整個循環(huán)過程中保持不變。

由于非線性偏微分方程不存在解析解，采用FED算法求得(1)式近似解為：

Li+1,j+1=(I+τjA(Li))Li+1,j,j=0,1,…,n-1

(8)

式(8)中，I為單位矩陣，n為顯示擴散步數(shù)，圖像亮度初始化設置為：Li+1,0=Li。

2.1.3非線性尺度空間的構造

采用FED算法來完成尺度空間的創(chuàng)建，該尺度級別按對數(shù)遞增，與SIFT不同之處是對圖像不用進行下采樣，它的各個層級均取用與原始圖像相同的分辨率。對應的尺度參數(shù)σi為：

(9)

由于熱傳導擴散模型是以時間為單元，故需將以像素為單位的參數(shù)σi轉化為時間單元。在高斯尺度空間下，使用標準差為σ的高斯核對圖像進行卷積，相當于對圖像進行持續(xù)時間為t=σ2/2的濾波。根據(jù)式(9)求出兩者的轉換公式：進化時間ti。

(10)

最后再結合式(7)求得相應的尺度圖像。這樣就可以得到一個O組，每組S層的圖像金字塔了。

2.2 特征點檢測

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

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

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

(11)

式(11)中I(x)為圓周上任意一個像素點的灰度值，I(p)為圓心像素點的灰度值，對于給定的閾值N0一般取9或12。當N>N0，則認為P為一個角點。重復上述步驟，對除P以外的每一個像素點執(zhí)行相同的操作，最終找出所有的角點。

(3)增加尺度信息：FAST算子沒有提供多尺度特性，這里的改進方法是將上節(jié)構建的非線性尺度空間，在其包含的O組，每組S層的圖像金字塔上，對每層圖像分別進行FAST特征提取，從而形成尺度空間。

圖2 FAST角點檢測Fig.2 FAST feature detection

(4)確定圖像矩的主方向：ORB采用Rosin灰度質心法使得描述算子具備旋轉不變特性。

在一個小的圖像塊中定義矩為：

(12)

式(12)中，I(x,y)為(x,y)點的灰度表達式。根據(jù)式(12)可以得到0階矩m00和1階矩m01、m10，通過矩可以找到圖像塊的質心：

(13)

連接圖像塊的幾何中心O和質心C，得到一個方向向量OC，特征點方向用公式定義為：

(14)

通過以上方法，F(xiàn)AST角點便具備了尺度和旋轉的信息。

2.3 特征點描述

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

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

(15)

式(15)中，p(x)為經過高斯平滑后的像素點x=(u,v)T的灰度函數(shù)，p(y)同理。

(2)按照一定準則在候選區(qū)域內選取n個(xi,yi)點對，即可輸出一個由n維二進制字符串表示的描述向量：

(16)

(3)考慮到上述的描述向量沒有方向信息，ORB的解決方法是將式(14)的主方向作為特征向量的主方向。對于任意n個待測試點集，引入一個2×n的矩陣Q：

(17)

(4)對矩陣Q進行旋轉變換。結合之前通過方向角θ求得相應的旋轉矩陣Rθ，就能得到帶有方向信息的特征點描述矩陣Qθ：

(18)

(5)得到具有旋轉角度的特征描述子：

gn(p,θ)=fn(p)|(xi,yi)∈Qθ

(19)

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

2.4 特征點匹配

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

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

(1)計算粗匹配后的點對集合S中每對匹配點間的距離，根據(jù)距離大小對S中的點對進行降序排列；

(2)選取前m個高質量的匹配點對，構成新的樣本集S'；

(3)在樣本集S'中選取4組質量最高的點對，計算單應矩陣Η；

(5)計算當前內點數(shù)量t，若tT，則內點數(shù)量更新為t；

(6)內點數(shù)量更新為t后，用當前內點集再次計算單應矩陣Η并完成剔除誤匹配的工作。

3 實驗設置、結果及分析

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

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

圖3 第一組尺度變化下的測試結果圖Fig.3 The first set of test results under the scale changes

圖4 第二組尺度變化下的測試結果圖Fig.4 The second set of test results under the scale changes

通過圖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。

表1 ORB算法與改進算法的匹配質量比較Tab.1 Comparison of matching quality between ORB algorithm and improved algorithm

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

圖5 第一組尺度旋轉變化下的測試結果圖Fig.5 The first set of test results under the change of scale rotation

圖6 第二組尺度旋轉變化下的測試結果圖Fig.6 The second set of test results under the change of scale rotation

圖5、圖6是針對圖像旋轉、多尺度的綜合測試效果圖。表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，但不影響實際應用中算法的實時性。

表2 ORB算法與改進算法的匹配質量比較Tab.2 Comparison of matching quality between ORB algorithm and improved algorithm

實驗二：為了進一步驗證改進算法的性能，通過復現(xiàn)率[16]來檢測在不同尺度下提取特征點的魯棒性。復現(xiàn)率是指兩幀圖像上提取到的相同點對數(shù)量占總提取點對數(shù)的百分比，評測公式如下：

(20)

式(20)中，min(di,dj)為基準圖、待匹配圖中提取的特征點數(shù)目的最小值；Dij為兩幅圖的重復點數(shù)。復現(xiàn)率越高表示特征匹配算法的魯棒性越強，即該算法越穩(wěn)定。實驗二是對取自室外的圖像(柯基圖)進行實驗，檢測不同尺度σ(σ∈[1,3])下的角點，實驗結果如下：

圖7 不同尺度下復現(xiàn)率比較Fig.7 Comparison of recurrence rates at different scales

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

4 結語

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