姚晉晉，張鵬超，王 彥，羅朝陽，李海婷

(1.陜西理工大學(xué) 機械工程學(xué)院，陜西 漢中 723000；2．陜西理工大學(xué) 陜西省工業(yè)自動化重點實驗室，陜西 漢中 723000；3．陜西理工大學(xué) 電氣工程學(xué)院，陜西 漢中 723000)

0 引 言

同步定位與構(gòu)圖(simultaneous localization and mapping，SLAM)作為一項機器人底層技術(shù)，需要通過傳感器對周圍環(huán)境進行感知的同時完成對自身的定位，是機器人領(lǐng)域一個重要的研究方向[1]。視覺SLAM的前端根據(jù)視覺傳感器信息粗略估計相機運動，其中基于特征法的前端對于特征提取的均勻度和提取效率有極強的依賴，使得特征提取成為當(dāng)前視覺SLAM算法的研究熱點。

傳統(tǒng)ORB(oriented FAST and rotated BRIEF)特征提取算法已經(jīng)在SLAM系統(tǒng)中得到廣泛應(yīng)用[1]，雖然可以滿足SLAM系統(tǒng)對于實時性的要求，但是ORB特征點在圖像平面仍然分布不均勻，容易出現(xiàn)聚集現(xiàn)象，降低了后續(xù)特征匹配與位姿估計的精度，為此Mur-Arta等[2,3]在ORB-SLAM系統(tǒng)中提出用四叉樹來提高特征分布的均勻度，明顯改善了特征點的均勻度，但是提取時間明顯增加；禹鑫燚等[4]在此基礎(chǔ)上對其進行改進提出了Qtree_ORB算法，有效地剔除了冗余的特征點，但仍采用傳統(tǒng)的四叉樹結(jié)構(gòu)，計算效率有待提高；范新南等[5]提出一種自適應(yīng)角點閾值提取方法，但是仍然含有人工設(shè)定的參數(shù)，無法真正達到自適應(yīng)提取。

故本文針對以上研究者所用方法的缺點，提出一種基于改進四叉樹的ORB特征均勻分布算法，在提取特征點時考慮圖像的整體對比度，并且根據(jù)不同金字塔層設(shè)定四叉樹的深度，從而減少冗余特征點的計算，提高特征提取的效率。

1 傳統(tǒng)ORB算法

傳統(tǒng)ORB算法主要包括兩個步驟，F(xiàn)AST角點檢測和Rotated BRIEF描述子計算。其中FAST算法通過選定元素與周圍元素像素灰度的差值來檢測角點。文獻[2]采用FAST-9算法，以像素p為例，在以p為中心半徑為3個像素的圓上共有16個像素點，如果這16個像素中有連續(xù)9個像素與p的灰度差值大于設(shè)定閾值t，則判定p為FAST角點。計算如式(1)所示

(1)

其中，I(x) 為圓周上任意一點的像素值，I(p) 是待檢測的像素灰度值，t為角點檢測閾值，F(xiàn)AST-9中N=9。此外，為了剔除邊緣點，采用Harris響應(yīng)值取代FAST響應(yīng)值，并且為了提高特征的魯棒性，通過構(gòu)建金字塔實現(xiàn)尺度不變性，為特征點添加了主方向?qū)崿F(xiàn)了旋轉(zhuǎn)不變性，為了避免角點集中問題，采用非極大值抑制對其進行一次篩選[4]。對于其特征點方向的計算具體如下：

(1)在一個圖像塊中，定義圖像塊的矩為

(2)

其中，I(x,y) 是圖像灰度。

(2)通過矩找到圖像塊的質(zhì)心

(3)

θ=arctan(m01/m10)

(4)

對于特征點的描述采用Rotation BFIEF，它是一種二進制描述子，其描述向量由多個0和1組成，文獻[2]中采用256維向量對角點進行描述，并且做了平滑處理，在特征點附近31×31的像素區(qū)域內(nèi)用5×5的子窗口的灰度值之和作為判斷描述子的依據(jù)，得到描述子分段函數(shù)，具體計算如式(5)所示

(5)

其中，p(x)、p(y) 分別為點x和點y處的像素灰度值，τ即為描述子的值，x和y處的灰度值即上述子窗口的灰度值之和。此外將式(4)中計算的方向加入到描述子中，使得描述子具有良好的旋轉(zhuǎn)不變性。

2 基于改進四叉樹的ORB特征提取

改進算法首先針對FAST角點提取抗干擾能力差的問題，根據(jù)不同圖像的灰度值計算來代替人工設(shè)定值；其次在Mur-Arta[2，3]提出的方法上，根據(jù)不同的金字塔層為四叉樹加入不同的深度檢測，以限制四叉樹過度分割，減少冗余特征計算，從而提高算法的計算效率。算法結(jié)構(gòu)如圖1所示。

圖1 算法結(jié)構(gòu)

(1)對于FAST角點的提取是根據(jù)待檢測像素與周圍像素的灰度差進行的，但是比較閾值無論是傳統(tǒng)算法還是后續(xù)Mur-Arta等提出的算法均是人工設(shè)定的，并沒有考慮圖像自身的全局信息，而范新南等[5]提出的自適應(yīng)閾值中仍然含有人工設(shè)定的比例因子，本文算法根據(jù)圖像灰度信息計算出一種不同的自適應(yīng)閾值用于FAST角點檢測，計算方法如式(6)所示

(6)

(2)圖像金字塔，為了使ORB特征具有尺度不變性，為圖像構(gòu)建了八層金字塔，同時按照比例因子計算每一層所需的期望特征點數(shù)量。記所需特征點總數(shù)為m，尺度因子為s，第1層所需特征數(shù)為a，則有

(7)

(3)劃分網(wǎng)格提取FAST角點，為了使角點均勻分布在整個圖像，對圖像進行網(wǎng)格劃分，初始化網(wǎng)格為邊長為30像素的正方形，然后根據(jù)圖像的分辨率計算出分割出的行數(shù)L與列數(shù)R，由于圖像并非正方形而是矩形，所以再根據(jù)所計算的行數(shù)與列數(shù)計算網(wǎng)格的寬和高。以計算網(wǎng)格的寬為例，圖像的寬為width，則分割的列數(shù)為

R=width/30

(8)

再由列數(shù)求出實際網(wǎng)格寬

w=round(width/R)

(9)

其中，w為最終網(wǎng)格的寬，round()的作用是對函數(shù)結(jié)果取整，實踐驗證以30像素為初始化邊長可以滿足提取點數(shù)量的要求且具有較高的計算效率。

劃分網(wǎng)格完成后采用第(1)步計算所得的iniT作為初始提取閾值進行角點提取，如果該網(wǎng)格內(nèi)沒有提取到角點，就降低閾值為minT=iniT/4， 繼續(xù)在網(wǎng)格內(nèi)進行角點提取，直到遍歷圖像中的所有網(wǎng)格，通過該方法完成角點的粗提取，使得圖像的每個網(wǎng)格中都存在角點。

(4)構(gòu)建四叉樹，通過第(3)步所得的角點存在大量的冗余，需要四叉樹對其進行進一步的篩選。四叉樹的思想是將數(shù)據(jù)區(qū)域分為4個象限，在特征點的篩選中，首先設(shè)定初始化節(jié)點為整張圖片，得到的原始四叉樹節(jié)點，之后在每個節(jié)點中檢測角點的數(shù)量，如果大于1，則繼續(xù)分裂子節(jié)點，如果等于1，則不再分裂并將該節(jié)點存儲；當(dāng)節(jié)點數(shù)量到達期望特征點數(shù)量時，四叉樹分裂完成，不再繼續(xù)分裂。

但上述步驟中由于沒有對四叉樹深度進行限制，造成分割次數(shù)過多，降低了算法的計算效率，本文在此基礎(chǔ)上根據(jù)不同金字塔層的期望特征點數(shù)設(shè)置不同的深度，以提取500個特征為例，第一層最大深度設(shè)置為5即可滿足要求，而第8層最大深度設(shè)置為3即可，不同金字塔層不同深度的設(shè)計有助于減少冗余特征的計算，從而提高計算效率，具體算法流程如圖2所示。

圖2 改進四叉樹節(jié)點管理

圖2中，d為當(dāng)前四叉樹深度，Dmax為該金字塔層設(shè)定最大深度，Num_kp為節(jié)點中特征點的數(shù)量，Num_j為存儲節(jié)點數(shù)量，Set_Kp為該層期望特征點數(shù)。最大深度與該層節(jié)點數(shù)量關(guān)系如式(10)所示

4Dmax≥Num_j

(10)

(5)計算特征點的方向與描述子，本文仍然采用傳統(tǒng)的計算方法，在此不再贅述。

3 實驗結(jié)果

本實驗在Ubuntu16.04 LTS操作系統(tǒng)上進行，計算機CPU為i5-4258U，8 GB內(nèi)存，通過在不同數(shù)據(jù)集上的測試檢驗特征均勻度與計算效率。

為了量化均勻度，采用以下計算方法[8]。首先從豎直、水平、45°和135°這4個方向以及中心和外圍對圖像進行區(qū)域劃分，得到了上、下、左、右、左上、右下、右上、左下、中心和外圍10個區(qū)域；接著統(tǒng)計出每個區(qū)域內(nèi)的特征點的數(shù)目，并根據(jù)這些數(shù)據(jù)計算出改組數(shù)據(jù)的方差V，最后均勻度u計算公式為

u=101log(V)

(11)

該數(shù)值越小，則不同區(qū)域內(nèi)的特征點數(shù)量差別越小，分布均勻度越好。

為了驗證該算法對于提高均勻度和計算效率上的有效性，以及對于不同條件下的適應(yīng)性，采用K.Mikolajczyk和C.Schmid創(chuàng)建的數(shù)據(jù)庫中的圖像進行驗證[5]，該數(shù)據(jù)庫中包含不同分辨率，不同模糊程度，不同視角以及不同亮度的圖像，本文采用其中的5組數(shù)據(jù)集，其中bike數(shù)據(jù)集是一組不同模糊程度的圖像，leuven數(shù)據(jù)集是一組不同對比度的圖像，bark是一組背景單一且占用較多幅面的圖像，trees是一組前景復(fù)雜且占用較多幅面的圖像，ubc是一組不同壓縮度的圖像，在這些數(shù)據(jù)集中，分別采用傳統(tǒng)ORB算法、Mur-Arta在ORB_SLAM中提出的特征提取算法以及本文算法進行對比實驗，并且為不失一般性，對于每組數(shù)據(jù)集均進行30次實驗，以平均值作為實驗結(jié)果。

圖3為3種ORB特征提取算法對同一圖片的提取500個特征點的結(jié)果，圖3(a)為傳統(tǒng)ORB算法的提取結(jié)果，實驗采用OpenCV3.4.1中的ORB算法作為傳統(tǒng)提取算法，圖3(b)采用Mur-Arta等改進的ORB提取算法，圖3(c)采用本文改進的ORB特征提取算法，圖中不同大小的圓為提取的特征點，可以看到傳統(tǒng)ORB算法所提取到的特征分布極不均勻，集中在車身和門框等區(qū)域內(nèi)，而Mur-Arta的算法與本文算法所提取的特征均勻分布于整個圖像。3種算法對于bike數(shù)據(jù)集的實驗結(jié)果見表1，表1中MA算法為Mur-Arta算法的簡寫。

為了量化特征的分布情況，實驗采用分布均勻度函數(shù)[8]進行計算，均勻度的數(shù)值越小，均勻分布的效果越好，并為了檢驗算法對于計算效率的提升，同時計算了提取特征所需時間。3種算法在bike數(shù)據(jù)集下的均勻度與提取時間實驗結(jié)果見表1。由表1分析可知，Mur-Arta的算法與本文算法均對特征的均勻度有較大的提高，而Mur-Arta算法與本文算法在分布均勻度上的差距不大，最大相差約2%；同時在提取時間上，本文算法與Mur-Arta算法均比傳統(tǒng)算法多，這是因為這兩種算法均加入了四叉樹對特征點的管理，但是本文算法比Mur-Arta算法耗時明顯減少，平均減少時間12.12%。

圖3 不同算法對bike數(shù)據(jù)集中img1的特征提取結(jié)果

為了驗證本文算法對于不同光照條件的適應(yīng)性，在數(shù)據(jù)集leuven上進行了測試，分別計算了3種算法在不同明暗條件下的特征均勻度與提取時間，實驗結(jié)果如圖4和表2所示。

圖4分別為本文算法在數(shù)據(jù)集leuven上6張圖像的特征提取結(jié)果，結(jié)果表明即使在明暗差距較大的情況下，本文算法仍然能夠取得良好的特征均勻化效果，具體均勻度與提取時間見表2。

表1 3種算法均勻度與耗時比較

圖4 本文算法在leuven上的特征提取結(jié)果

表2 3種算法在leuven上的均勻度與耗時比較

從表2可以看出，本文算法在特征分布均勻度上與MA算法相差無幾，但是在耗時上有明顯減少，平均減少時間10.43%，并且由于FAST角點的提取閾值是根據(jù)圖像信息計算所得，所以算法對于不同對比度的圖像抗干擾能力更強。

其余組的數(shù)據(jù)如圖5和圖6所示。圖中橫坐標為不同數(shù)據(jù)集的圖像序號，圖5為不同數(shù)據(jù)集下3種算法的均勻度實驗結(jié)果，圖6為不同數(shù)據(jù)集下3種算法的特征提取時間結(jié)果。

圖5 3種算法在不同數(shù)據(jù)集下均勻度對比

圖6 3種算法在不同數(shù)據(jù)集上提取時間對比

如圖5所示，在3種不同的數(shù)據(jù)集下，Mur-Arta的算法與本文算法在均勻度的表現(xiàn)上相差無幾，并且均大幅優(yōu)于傳統(tǒng)的ORB特征提取算法，但是本文算法在背景復(fù)雜且占用較大幅面的bark數(shù)據(jù)集中，均勻度計算結(jié)果均略優(yōu)于Mur-Arta的算法，在前景復(fù)雜且占用圖像較多幅面的trees數(shù)據(jù)集中，本文算法的均勻度亦略優(yōu)于Mur-Arta的算法，而在ubc數(shù)據(jù)集下的實驗結(jié)果則沒有明顯的優(yōu)勢，兩種算法在處理壓縮度較高的圖像時均勻度相差不大。

由圖6分析可得，3種不同的數(shù)據(jù)集下，傳統(tǒng)ORB特征提取算法的提取時間最快，而Mur-Arta的算法以及本文算法的提取時間均高于傳統(tǒng)ORB算法，后兩者的耗時主要是因為提高均勻度而做的計算。更重要的是本文算法相對于使用廣泛的Mur-Arta的算法在提取時間上有大幅提高，在bark數(shù)據(jù)集下本文算法提取時間比Mur-Arta平均減少18.10%，在trees數(shù)據(jù)集下平均減少時間16.73%，在ubc數(shù)據(jù)集下平均減少時間16.30%，提取效率大幅提高。

綜合以上實驗數(shù)據(jù)，本文所提出的ORB特征提取算法在不同背景、不同模糊程度、不同光照以及不同壓縮程度的條件下，特征均勻度和提取時間上均有更為優(yōu)越的表現(xiàn)。

4 結(jié)束語

針對傳統(tǒng)ORB算法分布不均、聚集現(xiàn)象明顯的問題，提出一種基于改進四叉樹的ORB特征提取算法，解決了FAST角點的自適應(yīng)提取閾值選擇問題，并針對不同金字塔層所需的期望特征點數(shù)設(shè)置每層的四叉樹深度，最后選取多組公開數(shù)據(jù)集進行實驗驗證。實驗結(jié)果表明，該算法相對于傳統(tǒng)ORB算法均勻度有明顯提高，并且比Mur-Arta提出的算法具有更高的計算效率，由于對不同金字塔層增加了自適應(yīng)深度檢測，減少了冗余特征點的計算，特征提取時間平均減少10%以上，對SLAM后續(xù)特征匹配和位姿估計都具有一定的應(yīng)用價值。