基于加權網格運動統(tǒng)計的改進ORB算法

黨宏社， 李俊達， 張選德

(陜西科技大學 電氣與控制工程學院， 陜西 西安 710021)

0 引言

圖像特征匹配是計算機視覺領域的一項關鍵技術，通常用于視覺SLAM[1,2]、三維重建[3]、圖像檢索[4]、目標跟蹤[5]等領域.提高圖像特征提取的魯棒性，特征匹配的準確性和快速性是該領域的研究重點[6].圖像特征匹配的方法大致可分兩個步驟，首先提取兩幅待匹配圖的特征點，并用描述子對特征點進行描述，然后根據描述子比較特征點之間的相似程度，判斷是否匹配.

特征點提取算法，有經典的尺度不變特征轉換(Scale-Invariant Feature Transform，SIFT)、SURF(Speeded Up Robust Features)、ORB(Oriented FAST and Rotated BRIEF)、AKAZE(Accelerated-KAZE)[7-10]等算法.ORB算法是由Rublee等在2011年提出的，該算法計算速度是SURF的10倍，是SIFT的100倍[7,11]，能滿足大部分場景對實時性的要求，但是其提取的特征點較集中，且魯棒性不如SIFT.孫浩等[12]提出了區(qū)域劃分的方法，將圖像分成多個小區(qū)域，在每個區(qū)域上提取一定數量的特征點，使得特征點能夠更加均勻地分布，但其使用人為設定的閾值提取特征點，并未根據圖像像素特點自適應調整，光照變化時，提取特征點魯棒性較差.楊弘凡等[13]提出了自適應閾值的ORB算法，根據某像素周圍的其他像素亮度，計算該像素的閾值，但依然存在特征點重疊的問題，且逐像素計算閾值非常耗時，影響實時性.

特征點描述子粗匹配通常采用暴力匹配(Brute-Force)與快速最近鄰搜索庫(Fast Library for Approximate Nearest Neighbors，FLANN)[14].常用的誤匹配去除方法有RANSAC、松弛迭代法、最小中值法以及基于視差的濾波算法[15].粗匹配得到的結果效果較差，存在大量誤匹配，而常用誤匹配剔除方法需要多次迭代，計算量大，耗時長.

針對以上問題，本文提出一種基于加權網格運動統(tǒng)計的改進ORB算法.采用區(qū)域劃分的方法使特征點分布均勻，使用自適應閾值提取特征點，降低亮度變化的影響，利用加權網格運動統(tǒng)計剔除誤匹配，提高算法運行速度.

1 ORB算法原理

ORB算法主要分兩個步驟，FAST特征點檢測和Rotated Brief描述子計算.特征點即圖像中突出的部分，其周圍像素具有像素值急劇由淺色變?yōu)樯钌奶卣?以圖1為例，FAST特征點提取過程如下：

圖1 FAST特征點提取示意圖

(1)從圖中選擇像素點P，設其灰度值為Vp.

(2)設定閾值t.

(3)比較以像素P為圓心的圓周上16個像素的灰度值，若連續(xù)q個點的灰度值都大于Vp+t或都小于Vp-t，則認為P是一個特征點.

(4)獲得特征點后，使用Rotated Brief計算特征描述子.首先用高斯核對圖像進行平滑處理，然后以特征點P為圓心劃定鄰域，在鄰域中隨機選擇一對像素a和b，根據式(1)計算這一位的值.

(1)

式(1)中：τ是描述子這一位的值，V(a)和V(b)分別為像素a與b的灰度值，從像素P的鄰域中總共選擇n個像素對，最終構成n維Brief描述子：

(2)

(5)FAST提取的特征點本身不具備旋轉不變性，使用灰度質心法給特征點賦予方向[16].

2 改進ORB特征點匹配算法

改進ORB的圖像匹配算法流程如圖2所示.

圖2 改進ORB的特征點匹配算法流程圖

首先構建待匹配圖片和模板圖片的高斯差分金字塔，其次將金字塔各層圖像劃分成等大的幾個小區(qū)域，使用改進自適應閾值算法計算每個區(qū)域的閾值，然后提取每個區(qū)域的特征點并計算特征描述子，使用雙向匹配算法進行粗匹配，最后使用WGMS算法剔除誤匹配特征點對.

2.1 構建高斯差分金字塔

ORB算法提取到的特征點不具備尺度不變性，在匹配過程中會造成誤匹配或漏匹配的問題，因此，需構建高斯差分金字塔(DoG)，過程如圖3所示.

圖3 高斯差分金字塔構建過程

首先將讀取的圖像做H次下采樣，獲得H組不同大小的圖，構成圖像金字塔.然后使用式(3)所示的高斯函數對圖像金字塔的各層圖像做高斯濾波，式(3)中x，y為像素坐標，σ是平滑因子.

(3)

以第一組為例，選取固定的σ對第一層圖像做濾波，獲得第二層圖像，然后將σ乘以比例系數k，獲得新的平滑因子kσ，用它對第二層圖像濾波，結果作為第三層圖像，以此類推，最終得到L層圖像，每層圖像尺寸相同，平滑因子不同，平滑因子計算如式(4)所示.對圖像金字塔各組圖像執(zhí)行以上操作，最終獲得H組，每組L層的高斯金字塔.

σ(L)=kL-2σL≥2

(4)

最后構建高斯差分金字塔，其第一組第一層是由高斯金字塔的第一組第二層減第一層得到的，以此類推，第H組L層圖像是由高斯金字塔的第H組L+1層減第H組L層得到的，最終獲得H組，每組L-1層的高斯差分金字塔.

2.2 特征提取

通常，特征點越多，圖像匹配準確率越高，但FAST算法提取的圖像特征點存在分布密集、重疊的問題，對特征描述十分不利，而且會影響匹配精度[12].此外在傳統(tǒng)的FAST算法中，特征提取的閾值由人為設定，固定不變的全局閾值無法兼顧圖像的不同區(qū)域，也無法消除光照影響，會出現特征點誤提取和誤匹配的問題.針對以上問題，本文提出一種區(qū)域劃分自適應閾值的ORB算法，將圖像劃分為多個區(qū)域，采用自適應閾值在每個區(qū)域上提取特征點，提高特征點的魯棒性.

首先，將高斯差分金字塔中的每幅圖像均勻地劃分為M×N個相同大小的區(qū)域，M是分割的行數，N是分割的列數.然后，根據式(5)計算各個區(qū)域的閾值t.式中m為區(qū)域內像素個數， 為區(qū)域內每個像素的灰度值，Vmid為區(qū)域內像素灰度值的中位數，此處不采用平均值是為了防止亮斑或暗斑導致灰度值出現極值，對閾值計算結果產生不利影響.最后，根據閾值使用FAST算法提取每個圖像區(qū)域的特征點，然后計算Brief描述子，使用灰度質心法計算特征點的方向，差分金字塔所有特征點的集合即為圖片的特征點.

(5)

2.3 特征點粗匹配

使用改進ORB算法對模板圖和目標圖進行特征點提取，獲得兩幅圖像的特征點描述子集合.若采用暴力匹配算法進行特征點粗匹配，會引入大量的錯誤匹配，增大剔除誤匹配的工作量，故本文采用一種雙向匹配算法進行粗匹配，降低誤匹配率，提高匹配算法的準確率.算法步驟如下：

(1)選擇模板圖中的一個特征點Pmi，根據式6計算其與目標圖所有特征點之間的漢明距離d，c(i)和d(i)表示特征描述子每一位的值.

(6)

(2)選取目標圖中漢明距離到特征點Pmi最近的前兩個特征點，即最近鄰點Pti和次近鄰點Ptj，記他們到Pmi的距離為d1和d2.若d1/d2≤T，則認為Pmi和最近鄰點Ptj是一對匹配點，其中T是人為設定的閾值.

(3)遍歷模板圖中的特征點，執(zhí)行(1)、(2)兩步操作，得到匹配對集合Cm.反過來遍歷目標圖中的特征點，獲得匹配對集合Ct.判斷集合Cm中的某一對匹配對(Pmi,Ptj)與集合Ct的一對匹配對(Pti,Pmi)是否相同，如果滿足則保留該匹配對，否則刪除，最終獲得匹配對集合C={c1,c2,…,Cn}，其中cn=(Pmn,Ptn).

2.4 加權網格運動統(tǒng)計剔除誤匹配

通常采用隨機抽樣一致性(RANSAC)算法剔除粗匹配中的誤匹配點，但該方法需要多次迭代才能獲得較好的結果，存在運算量大的問題.RANSAC的改進算法漸進一致采樣(PROgressive SAmple Consensus，PROSAC)從不斷更新的最佳對應點集中進行采樣，節(jié)省了一定的計算量，但仍需多次迭代才能得到較好結果.GMS算法將運動平滑約束轉換為剔除錯誤匹配的統(tǒng)計量，采用基于網格的得分估計器，提高了算法的實時性.該算法基于貝葉斯法則，即兩幅圖像正確匹配對的鄰域內應該有多個支持它的匹配對，而錯誤匹配對的鄰域內支持它的匹配對很少甚至沒有[17].

2.4.1 網格運動統(tǒng)計算法原理

首先將模板圖和目標圖網格化如圖4所示.圖中3×3加粗網格代表的是網格a5的鄰域，點劃線表示一個正確的匹配對ci，實線表示該匹配對領域內正確的匹配對，虛線表示錯誤匹配對.

圖4 網格化示意圖

然后計算該匹配對的鄰域支持度S，設ci是匹配對，網格a5和b5鄰域9個網格中匹配對數量為ni(i=1,2,…,9)，則：

(7)

式(7)中：減一表示從總數中減去匹配對自身.由于匹配對是獨立分布的，S服從二項分布：

(8)

式(8)中：N表示鄰域總匹配對數量，Pt和Pf分別表示正確和錯誤匹配率.式(8)的期望和方差為：

(9)

(10)

由此可得概率評估函數P：

(11)

(12)

式(12)中：α是超參數，用于調節(jié)閾值，經驗值選擇4～6.當S大于τ時，cl是正確匹配，將其保留，否則為錯誤匹配，將其刪除.

2.4.2 加權網格運動統(tǒng)計算法

GMS算法的問題在于網格大小選取，如果網格很小，則僅僅考慮了很少的領域信息，算法性能降低，如果網格很大，則將包括很多不正確的對應關系，影響篩選結果.本文提出加權網格運動統(tǒng)計算法，將距離影響引入支持度計算中，使用泊松函數對網格進行加權，使得中心網格的權值最大，外圍網格的權值較小，可推導出其二維函數為：

(13)

以a5為中心點根據式(13)計算各網格的權值并作歸一化處理，得到3×3權系數矩陣，式(13)中λ要取非整數，以保證最大值唯一.

(14)

(15)

當S大于τ時，cl是正確匹配，將其保留，否則為錯誤匹配，將其刪除.

3 實驗與結果分析

為驗證本文提出算法的有效性，采用Kaggle平臺的Cat Vs Dog數據集以及自然場景下拍攝的圖像進行實驗，貓狗圖像各5 000張，所有實驗均在Intel?CoreTM i5-10400F CPU@2.9 GHz，32GB RAM硬件環(huán)境中，Windows10 PyCharm Community Edition 2020軟件環(huán)境中完成.

3.1 特征點提取實驗

對貓和狗的圖片使用傳統(tǒng)ORB算法和本文算法提取特征點，實驗結果如圖5所示.從圖5(a)可以看出，傳統(tǒng)ORB算法在提取特征點時出現了4處大量聚集，分別為狗耳朵、眼睛、牙齒以及狗的鏈子，而且沒有在狗腰臀部分提取到特征點.從圖5(b)可以看出，改進ORB消除了狗耳朵、牙齒和鏈子上的特征點聚集，狗眼睛部分的聚集也明顯緩解，同時在狗腰臀部分提取了一定數量的特征點,與圖5(c)中SIFT算法提取效果相近.從圖5(d)可以看出，特征點聚集在貓面部的眼睛和鼻子處，而圖5(e)中消除了貓面部大量重疊的特征點，同時在貓尾部提取到了一定數量的特征點，較圖5(f)提取了更多的特征點.綜上，本文算法使用的區(qū)域劃分方法，使得特征點分布更加均勻，避免了特征點聚集重疊，同時采用了自適應閾值的方法，使得固定閾值無法提取特征點的部位也能有效提取，提取效果與SIFT相近.

(a)、(d)傳統(tǒng)ORB算法提取效果(b)、(e)改進ORB算法提取效果(c)、(f)SIFT算法提取效果 圖5 算法特征提取效果對比

表1統(tǒng)計了三種算法的特征提取時間.可以看出本文算法特征提取時間較傳統(tǒng)ORB算法平均慢了13.86%，較SIFT算法快了399.19%.

表1 特征提取時間

為進一步驗證自適應閾值的有效性，人為調整圖片，在原圖的基礎上增加和減少亮度，實驗結果如圖6所示.圖片亮度變化后，傳統(tǒng)ORB算法提取的特征點依然存在大量重疊問題，亮度調暗的情況下在大部分區(qū)域無法提取到特征點，而改進ORB算法和SIFT算法在光線變換情況下依然可以穩(wěn)定提取特征點，且特征點分布均勻，從圖6(k)、(l)中可以看出,改進ORB算法在較暗的區(qū)域可以提取到特征點，效果優(yōu)于傳統(tǒng)ORB算法和SIFT算法.

(a)、(d)、(g)、(j)傳統(tǒng)ORB算法提取效果(b)、(e)、(h)、(k)改進ORB算法提取效果(c)、(f)、(i)、(l)SIFT算法提取效果圖6 亮度變化后特征提取效果對比

3.2 特征匹配實驗

改變數據集中圖片的亮度，對傳統(tǒng)ORB算法、ORB+RANSAC算法、ORB+GMS算法、SIFT算法、本文算法、文獻[12]和文獻[13]中算法進行測試比較.七種算法匹配結果如圖7所示.從圖7(a)和圖7(f)可以看出，傳統(tǒng)ORB和文獻[12]算法在光照改變的情況下，誤匹配對較多，左圖部分特征點與右圖另一只貓的特征點匹配上了，同一只貓身上也存在較多的誤匹配對，圖7(b)、(c)、(d)、(e)中誤匹配較少，只有少量特征點誤匹配到了另一只貓身上，同一只貓身上的誤匹配數量也明顯較少.

(a)傳統(tǒng)ORB算法 (b)ORB+RANSAC算法

(c)ORB+GMS算法 (d)SIFT算法

(e)本文算法 (f)文獻[12]算法

(g)文獻[13]算法圖7 特征匹配結果

表2統(tǒng)計了七種算法特征點匹配耗時以及匹配準確率.可以看出本文算法耗時較傳統(tǒng)ORB算法慢10.7%，較ORB+GMS算法慢1.1%，快于其他四種算法，算法實時性高，匹配準確率高于其他六種算法，較傳統(tǒng)ORB算法提高41.7%，較ORB+GMS算法提高5.5%.

表2 特征點匹配結果對比

4 結論

本文針對ORB特征點過于集中重疊的問題，提出了區(qū)域劃分的方法，使特征點分布更為均勻.針對ORB算法在亮度變化情況下特征點提取不穩(wěn)定，匹配準確率低的問題，提出了一種自適應閾值的方法提取特征點，提高了特征點提取的魯棒性.針對粗匹配結果差的問題，提出WGMS算法剔除誤匹配，提高了匹配準確率.實驗結果表明本文算法可以有效對抗光照干擾，在保證實時性的情況下提高特征匹配的準確率，對圖像識別，圖像拼接等領域研究具有良好的實用價值.