基于改進(jìn)四叉樹的ORB特征均勻分布算法

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

(1.陜西理工大學(xué) 機(jī)械工程學(xué)院，陜西 漢中 723000；2．陜西理工大學(xué) 陜西省工業(yè)自動(dòng)化重點(diǎn)實(shí)驗(yàn)室，陜西 漢中 723000；3．陜西理工大學(xué) 電氣工程學(xué)院，陜西 漢中 723000)

0 引 言

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

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

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

1 傳統(tǒng)ORB算法

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

(1)

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

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

(2)

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

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

(3)

θ=arctan(m01/m10)

(4)

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

(5)

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

2 基于改進(jìn)四叉樹的ORB特征提取

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

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

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

(6)

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

(7)

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

R=width/30

(8)

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

w=round(width/R)

(9)

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

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

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

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

圖2 改進(jìn)四叉樹節(jié)點(diǎn)管理

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

4Dmax≥Num_j

(10)

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

3 實(shí)驗(yàn)結(jié)果

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

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

u=101log(V)

(11)

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

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

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

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

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

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

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

表1 3種算法均勻度與耗時(shí)比較

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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