基于ORB特征的誤匹配點剔除算法*

趙 輝， 于春梅,2

(1.西南科技大學 信息工程學院，四川 綿陽 621010；2.特殊環境機器人技術四川省重點實驗室， 四川 綿陽 621000)

0 引 言

特征點匹配在機器人領域中有著廣泛的應用[1,2]，其中,ORB算法的效率，是SIFT和SURF的10倍以上。ORB算法結合了FAST特征點檢測與BRIEF特征描述子，并在此基礎上作出了改進，具有了旋轉與尺度不變的特性[3～6]。但特征點在匹配過程中不可避免地存在著誤匹配[7]。對此，人們提出了很多相關的誤匹配點剔除算法。文獻[8]結合ORB與SURF算法，提取了SURF-ORB特征點，并對圖像進行分塊處理，然后通過Hamming距離進行初步剔除，再結合順序采樣一致性[9](progressive sample consensus,PROSAC)算法進一步剔除；該算法具有一定的準確性及實時性，但是在Hamming初剔除階段，沒有通過實驗設計選取最優閾值，因此后續階段的處理未能得到最優點對。文獻[10]采用K最近鄰算法，對前后2幀特征點進行雙向匹配，再通過PROSAC算法進一步提純，該算法具有較高的精度且具有一定的實時性，但是算法未能運用在復雜場景下，對光照變化以及噪聲影響下未做相應分析，有一定的不足。文獻[11]雖然在算法中融入了特征點周圍的灰度信息，但是也僅僅涉及了特征點周圍區域的灰度整體信息，如方差、均值等。特征點周圍的局部區域相對較為穩定，是可以充分利用的信息。

本文在ORB特征的基礎上，針對匹配過程中存在的大量誤匹配點對[12]以及上述文獻中的不足，提出一種新的特征點誤匹配剔除算法并做了補充實驗，相較于傳統的隨機采樣一致性[13](random sample consensus,RANSAC)算法，提高了圖像特征點匹配的準確性。

1 ORB特征點匹配

1.1 特征點提取

1)在圖像中選取像素點p，比較p和以p為圓心半徑為3的圓周上16個點的灰度值的大小，若差值足夠大的點數超過設定的閾值，則認為p為角點[14]。2)計算FAST角點Harris響應值并進行排序，選取前N個點。3)構建尺度金字塔，在金字塔上的每一層檢測角點，對特征點添加尺度的描述。

局部區域矩為

(1)

質心為

C=(m10/m00,m01/m00)

(2)

特征點的方向為

θ=arctan(m01/m10)

(3)

1.2 特征點描述子

ORB算法采用rBRIEF描述子對檢測到的特征點進行描述。其基本思想是：根據高斯分布，在特征點周圍31像素×31像素的鄰域內，選取n對5×5的子窗口，比較2個窗口的灰度積分值[15]，從而對特征點進行描述。表達式為

(4)

式中Ip，Iq為角點鄰域內p和q的窗口灰度函數，則n對子窗口比較而形成描述子的計算為

(5)

式中n的取值可以為128,256等。

ORB算法將角點方向作為BRIEF描述子的方向，使其具有了旋轉不變性。定義一個2×n的矩陣K為

(6)

對K矩陣進行旋轉變換得到新的矩陣

(7)

所得描述子結果為

gn(P,θ)=fn(p)|(pi,qi)∈Kθ

(8)

1.3 特征點匹配

得到待匹配2幅圖像中的所有特征點描述子后，分別計算出一幅圖像中每一個特征點的描述子到另一幅圖像中每一個特征點的描述子的Hamming距離，Hamming距離越小，即兩個特征點越相似[16]，當漢明距離小于一定閾值時，即認為兩個特征點匹配。

2 匹配點對提純的算法

2.1 粗剔除

根據漢明距離初步剔除誤匹配時，選擇閾值過小則剩余的匹配點對數量過少，不利于后續圖像處理；閾值過大則剩余的誤匹配點對較多，后續工作誤差過大。本文通過設計實驗選取一個合適的閾值。

根據Hamming距離定義，對于任意一個閾值T，可以得到最大距離dmax與dmin最小距離，定義一個變量s和匹配正確率p

T=s(dmax+dmin)，p=nture/nall

(9)

通過控制變量法，改變s的值，并統計每一次總匹配點對數nall和正確匹配點對數nture，根據所得的結果繪制出折線統計圖，分析并確定變量s的最佳值。采用該最佳值對匹配點對進行重新篩選，將所得匹配點對記為粗略匹配點對，進行精剔除。

2.2 精剔除

為更好地利用特征點周圍的像素信息，對剩下的匹配點對，以特征點為中心，定義5×5的窗口，計算窗口外層16個像素點與特征點像素值的差值，差值ri=|g(p)-g(xi)|，i=1,2,…,16,其中，g(p)為特征點p的像素值，為了進一步反映p的特征，構造特征點p的16×16鄰接矩陣A，其元素

(11)

因A是一個實對稱矩陣，故對A進行奇異值分解，可獲得16個實特征值

λ1(p)≥λ2(p)≥…≥λ16(p)

(12)

定義P=[λ1(p)/‖λ‖,λ2(p)/‖λ‖,…,λ16(p)/‖λ‖]為特征點p的描述向量，同理，與p相匹配的點q的描述向量為Q=[λ1(q)/‖λ‖,λ2(q)/‖λ‖,…,λ16(q)/‖λ‖]。其中，‖·‖為L—2范數。

由空間矢量的余弦定理可知

r=cosθ=P·Q/‖P‖‖Q‖

(13)

式中 cosθ的取值范圍為[-1 1]，也即當值越接近1，則兩個向量越相關。設定一個閾值ST，當r>ST時，保留該匹配點對，否則剔除。將所有點對計算對比后，得到最優點對集。

算法流程如下：

1)采用ORB算法分別對待匹配圖像A、B進行特征提取，根據Hamming距離采用暴力匹配算法對2幅圖片進行匹配。

2)構造閾值函數T=s(dmax+dmin))和匹配正確率函數p=nture/nall，隨機選取9組圖片，改變系數s的值，統計并分析變化曲線圖，選擇最優s值。

3)若Hamming距離小于閾值T，保留匹配點對，反之則剔除。保留的特征點對進入下一階段計算。

4)根據特征點及鄰域點像素值，構造差值矩陣，對差值矩陣進行奇異值分解，重新描述特征點。

5)根據空間矢量余弦定理，當r值大于一定閾值時，判別是正確匹配點對，反之,則剔除。最終得到正確匹配點對。

2.3 算法性能分析

1)旋轉不變性:文中的特征向量主要是利用特征點的鄰域點像素值構造差值矩陣，通過對該矩陣進行奇異值分解獲得由奇異值組成的描述向量，而該矩陣的奇異值分解具有置換不變性，因此該特征描述具有旋轉不變性。

(14)

3 實驗結果分析

本文實驗的編程環境為Microsoft Visual Studio 2013，操作系統采用的是Windows7 64位[Intel(R)Core i5—2430M CPU 2.4 GHz，4 G內存]。

實驗1：s的最優值選取。將18張不同角度的圖片隨機分成9組進行試驗，s值取0.1～0.9，改變s值并統計匹配正確率。實驗的最終目標是確定一個s值使匹配在獲得較多匹配點對的同時最大化正確匹配率。圖1為s值的變化曲線。

圖1 不同s值與p值的變化

從圖1可以看出，當s在0.1～0.4之間不斷增大時，p值變化較慢且值普遍在0.9以上。當s在0.4～0.5之間時，變化幅度較大，在0.5之后又開始趨于平緩，因此，取s=0.45作為最優值。用測試組10進行閾值測試，結果表明,當s取0.45時，正確率p為94.6 %，滿足要求。

實驗2：改進算法與RANSAC算法效果對比。為了驗證改進算法可以有效剔除誤匹配點對，對2張位于不同位置角度的圖片作對比試驗，如圖2。

圖2 不同算法剔除效果比對

對比各組圖像可以看出，新算法下的粗剔除可以有效地剔除大部分錯誤的匹配，為精匹配減少了計算量。而對比精匹配與RANSAC的效果發現，兩者的剔除效果都比較好，但新算法剩余的點對較RANSAC算法剩余的點對具有多樣性與靈活性。

為了更加精確地比較兩種算法的準確度，隨機選取5組不同環境下的圖像對，并對其進行編號。對比各組采用RANSAC與新算法下的剔除結果，結果如表1。可以看出，RANSAC算法的精確度為90.99 %，而新算法的精確度高達98.97 %。

實驗3：窗口大小對剔除精度的影響。若僅僅利用特征點及其周圍16個領域點來構造差值矩陣，則對特征點的描述也不完全充分。因此，可取以特征點為中心(2n+1)×(2n+1)的窗口構造差值矩陣，則對應的矩陣階數為8n，n=1,2,…,k，但當n的取值較大時，則矩陣的奇異值分解需要很高的計算代價。隨機選取5組圖像進行匹配，改變窗口的大小，統計每一次的正確數，表2反映的是隨著窗口的變化，剔除的精度的變化。

從表2可以看出，隨著窗口的變大，匹配點對的精度也在增加，當窗口大小為15×15時，匹配精度達到99.12 %，因此，本算法在誤匹配點對的剔除應用中具較好的效果。

表2 窗口大小與匹配精度的變化對比

4 結 論

通過選取合適的Hamming閾值，再構造并求解像素差值矩陣用以重新描述特征點，消除了直接用二進制方法難以剔除的誤匹配點對，同時該算法對光照、旋轉以及噪聲具有一定的魯棒性。但由于該算法是利用特征點的鄰域點構造描述向量，因此,當圖片發生尺度變化時，剔除效果會受到一定的影響，今后擬尋找更好的描述方法，以確保算法在尺度變化上的效果有所改進。