基于四叉樹(shù)的ORB-LBP改進(jìn)算法*

陳易文，儲(chǔ)開(kāi)斌，張 繼，馮成濤

（1.常州大學(xué) 微電子與控制工程學(xué)院，江蘇 常州 213164；2.常州大學(xué) 阿里云大數(shù)據(jù)學(xué)院，江蘇 常州 213164）

0 引 言

圖像的特征提取和匹配是同時(shí)定位與地圖構(gòu)建（simultaneous localization and mapping，SLAM）［1，2］的基礎(chǔ)問(wèn)題，影響著整個(gè)SLAM系統(tǒng)的效率與精度。Lowe D G在1999年首次提出尺度不變特征變換（scale-invariant feature transform，SIFT）算法［3］，并在2004 年進(jìn)一步改進(jìn)該算法。Bay H等人在2008 年借鑒SIFT 算法提出了加速魯棒特征（speeded up robust feature，SURF）算法［4］，在一定程度上解決了SIFT 算法計(jì)算復(fù)雜度高、計(jì)算時(shí)間長(zhǎng)等缺點(diǎn)；Rublee E 等人提出了定向二進(jìn)制簡(jiǎn)單描述符（oriented FAST and rotated BRIEF），ORB）描述算法［5］，該方法圖像匹配速度快，但其匹配效果較差。

近年來(lái)，出現(xiàn)了很多ORB算法的改進(jìn)方法。姚晉晉等人［6］提出了一種基于改進(jìn)四叉樹(shù)ORB 特征均勻算法，有效提高了特征提取的均勻度和效率；孫浩等人［7］通過(guò)區(qū)域劃分的方式，使提取到的特征點(diǎn)分布更為均勻，同時(shí)速度也有較大的提升；汪永生等人［8］通過(guò)改進(jìn)的ORB 特征描述子方法對(duì)待匹配的特征點(diǎn)進(jìn)行描述，有效提高了圖像匹配質(zhì)量；董永峰等人［9］在SURF 算法基礎(chǔ)上融合二值穩(wěn)健獨(dú)立基本特征（binary robust independent element feature，BRIEF）描述子，在提升匹配效率和準(zhǔn)確度的同時(shí)，可以滿足實(shí)時(shí)性的要求；Li S等人［10］提出一種融合BRIEF和FREAK描述子的改進(jìn)ORB算法，在尺度變化、明暗度變化時(shí)，特征匹配率和魯棒性都有了很大的提升。

上述改進(jìn)在一定程度上提升了ORB匹配精度，但ORB特征點(diǎn)在圖像平面仍然分布不均勻，在圖像變化不明顯的區(qū)域，不能檢測(cè)到特征點(diǎn)，而在一些圖像變化劇烈的地方容易出現(xiàn)特征點(diǎn)聚集現(xiàn)象，對(duì)后續(xù)特征匹配與位姿估計(jì)的精度會(huì)有巨大的影響。

本文針對(duì)特征點(diǎn)分布不均勻、匹配精度差的問(wèn)題，對(duì)ORB算法進(jìn)行了改進(jìn)，通過(guò)建立四叉樹(shù)及融合BRIEF—局部二值模式（local binary pattern，LBP）的方法，以期達(dá)到在少量增加計(jì)算時(shí)間的前提下，特征點(diǎn)分布更為均勻、匹配精度更高。

1 傳統(tǒng)ORB算法

ORB是一種局部特征提取方法，它利用加速分割測(cè)試特征（features from accelerated segment test，F(xiàn)AST）［11］關(guān)鍵點(diǎn)檢測(cè)器提取圖像特征關(guān)鍵點(diǎn)，利用BRIEF［12］描述子提取圖像特征描述子。

1.1 FAST角點(diǎn)檢測(cè)算法

以待檢測(cè)像素為圓心，3 個(gè)像素值為半徑，做一個(gè)圓，與圓相交的共有16 個(gè)像素，檢測(cè)16 個(gè)像素中與中心點(diǎn)的像素差大于某個(gè)閾值T 時(shí)，計(jì)數(shù)n 加1，若16 個(gè)點(diǎn)檢測(cè)完成時(shí)n ＞N（N 一般取11 或者9），則認(rèn)為該待檢測(cè)像素為角點(diǎn)，然后循環(huán)此過(guò)程檢測(cè)每一個(gè)像素［11］。

1.2 BRIEF描述子

以檢測(cè)到的角點(diǎn)附近框選一個(gè)方形窗口，在這個(gè)窗口內(nèi)隨機(jī)挑選出n組點(diǎn)對(duì)，再對(duì)每一個(gè)點(diǎn)比較亮度值，對(duì)所有n組點(diǎn)對(duì)都進(jìn)行比較后生成了一個(gè)長(zhǎng)度為n的二進(jìn)制字符串，即BRIEF描述子［12］。

圖1為傳統(tǒng)ORB的特征點(diǎn)檢測(cè)結(jié)果，可以看出所檢測(cè)到的特征點(diǎn)都容易集中于部分區(qū)域，特征點(diǎn)分布極度不均勻；只有在一部分特征明顯的區(qū)域存在密集的特征點(diǎn)，而在大部分區(qū)域都未能檢測(cè)到特征點(diǎn)，因此會(huì)導(dǎo)致后續(xù)匹配精度差。

圖1 傳統(tǒng)ORB特征點(diǎn)檢測(cè)

圖2為傳統(tǒng)ORB特征點(diǎn)結(jié)合暴力匹配得到的匹配結(jié)果，可以看出：所匹配的精度不高，匹配效果差，多處出現(xiàn)了誤匹配現(xiàn)象。

圖2 傳統(tǒng)ORB特征點(diǎn)匹配

2 基于融合描述子的改進(jìn)ORB算法

圖3為算法整體流程。首先，構(gòu)建圖像金字塔，通過(guò)劃分網(wǎng)格計(jì)算角點(diǎn)提取閾值來(lái)提取FAST角點(diǎn)；其次，通過(guò)構(gòu)建四叉樹(shù)使角點(diǎn)分布均勻；然后，通過(guò)融合BRIEF-LBP的方法對(duì)提取的角點(diǎn)進(jìn)行特征描述；最后，利用隨機(jī)抽樣一致性（random sampling consistency，RANSAC）的方法進(jìn)行特征匹配。

圖3 本文算法流程

2.1 構(gòu)建圖像金字塔

本文通過(guò)建立圖像金字塔，以最底層金字塔為原始圖像，每向上1層，進(jìn)行一定比例的縮放，得到不同分辨率的圖像，匹配不同金字塔層上的特征點(diǎn)，實(shí)現(xiàn)了尺度不變性。

圖4為不同金字塔層所檢測(cè)的特征點(diǎn)結(jié)果，分別建立了7層、5層、3層金字塔，可以看出在不同層數(shù)金字塔下圖像所提取到的角點(diǎn)都有所區(qū)別。通過(guò)實(shí)驗(yàn)，最終建立3層金字塔層，達(dá)到效果最優(yōu)。

圖4 不同金字塔層特征點(diǎn)

2.2 角點(diǎn)提取

將圖層劃分為M×N的網(wǎng)格，記錄每個(gè)網(wǎng)格中任意一個(gè)像素點(diǎn)的灰度值為Ip，網(wǎng)格平均值灰度值為Iq，并定義閾值T

式中 α為一個(gè)自適應(yīng)變量，本文α取1.2；m為網(wǎng)格內(nèi)像素點(diǎn)數(shù)量。在每個(gè)網(wǎng)格中對(duì)各像素與閾值T 進(jìn)行比較，進(jìn)行角點(diǎn)提取，若在該網(wǎng)格中未提取到角點(diǎn)，則將閾值T降低為原有的1／2，再進(jìn)行角點(diǎn)提取。遍歷所有網(wǎng)格，直至提取到的角點(diǎn)數(shù)量滿足設(shè)定的角點(diǎn)數(shù)量。

圖5為自適應(yīng)閾值下的角點(diǎn)提取，可以看出角點(diǎn)的分布情況較圖4（c）3 層金字塔提取到的特征點(diǎn)分布相比已經(jīng)有了改善，但提取到的角點(diǎn)在一定程度上仍會(huì)在部分網(wǎng)格內(nèi)密集分布。由于這部分角點(diǎn)對(duì)閾值的響應(yīng)較大，角點(diǎn)占據(jù)極大一部分所要求的角點(diǎn)數(shù)量，導(dǎo)致一些網(wǎng)格內(nèi)還未檢測(cè)到角點(diǎn)就結(jié)束角點(diǎn)提取操作。

圖5 角點(diǎn)提取

2.3 構(gòu)建四叉樹(shù)

首先，通過(guò)2.2節(jié)的方法對(duì)整張圖像進(jìn)行角點(diǎn)檢測(cè)；然后，將整個(gè)圖像空間劃分為4個(gè)相同的子空間，若在子空間內(nèi)檢測(cè)到的角點(diǎn)數(shù)量大于1，則繼續(xù)將該子空間分裂為4個(gè)新的子空間繼續(xù)檢測(cè)；但若特征點(diǎn)數(shù)量太多，會(huì)導(dǎo)致四叉樹(shù)的深度過(guò)深，在進(jìn)行空間檢索時(shí)效率會(huì)比較低下。因此，本文限制了四叉樹(shù)的深度為4 層，若深度達(dá)到4 層后子空間內(nèi)的角點(diǎn)數(shù)量仍大于1，則留取子空間內(nèi)響應(yīng)值最大的角點(diǎn)，舍棄其他角點(diǎn)，如圖6所示。

圖6 四叉樹(shù)示意

2.4 BRIEF-LBP融合描述子

ORB使用改進(jìn)的BRIEF進(jìn)行特征描述，減少了特征匹配所需的時(shí)間，但是其描述符的相關(guān)性仍然很大，使得圖像信息的利用不完整，容易導(dǎo)致特征點(diǎn)的不匹配。針對(duì)上述問(wèn)題本文將BRIEF描述子與LBP描述子融合的方法，其融合流程如圖7所示。

圖7 BRIEF-LBP描述子融合流程

首先，通過(guò)FAST 角點(diǎn)檢測(cè)算法進(jìn)行特征點(diǎn)的提取。以特征點(diǎn)為中心，選取S ×S的鄰域窗口，在窗口內(nèi)隨機(jī)選取2 ×2的像素點(diǎn)塊，比較兩者像素點(diǎn)塊像素平均值大小，進(jìn)行二進(jìn)制賦值，如式（2）所示

式中 I（r1，c1）和I（r2，c2）分別為（r1，c1）和（r2，c2）處像素的強(qiáng)度。如果I（r1，c1）小于I（r2，c2），則λ ＝1；否則，λ ＝0。重復(fù)操作，最終形成一個(gè)256位的二進(jìn)制編碼。

其次，以特征點(diǎn)為中心，半徑為R 做圓形區(qū)域。一個(gè)中心像素點(diǎn)（x，y）周?chē)钠渌袼攸c(diǎn)gk的坐標(biāo)（xk，yk）可以表示為

式中 R為圓形LBP 半徑，r 為第r 個(gè)采樣點(diǎn)，k 為樣本點(diǎn)數(shù)量。對(duì)計(jì)算得到的坐標(biāo)采用雙線性內(nèi)插值取整，以取整后的坐標(biāo)作為選取像素點(diǎn)的坐標(biāo)，比較中心像素點(diǎn)與選取像素點(diǎn)的灰度值，若中心點(diǎn)的灰度值大，則記為0，否則為1。重復(fù)操作，直至得到128 位二進(jìn)制值，并將此二進(jìn)制值循環(huán)排列直至得到最小的一組二進(jìn)制值便作為該像素點(diǎn)的LBP值。

本文將得到的256 位BRIEF 描述子與128 位LBP 描述子級(jí)聯(lián)得到新的384 位的二進(jìn)制描述符，將該新的描述子作為特征點(diǎn)的描述子。

2.5 特征匹配

本文采用暴力匹配方法對(duì)特征點(diǎn)的進(jìn)行匹配，對(duì)所有待匹配的特征點(diǎn)進(jìn)行漢明距離測(cè)試，舍棄漢明距離較大的特征點(diǎn)，對(duì)于剩下的匹配點(diǎn)利用RANSAC［13］方法進(jìn)行進(jìn)一步的剔除。

3 實(shí)驗(yàn)驗(yàn)證

所用的實(shí)驗(yàn)平臺(tái)配置為Intel?CoreTMi5—8265U，內(nèi)存1.60 GHz。采用了EuRoC公開(kāi)數(shù)據(jù)集［14］中的圖片，該數(shù)據(jù)集包括了視覺(jué)（雙相機(jī)）測(cè)量得到的數(shù)據(jù)。將本文算法與ORB算法、SIFT算法以及文獻(xiàn)［9，10］中改進(jìn)的ORB 算法進(jìn)行對(duì)比實(shí)驗(yàn)驗(yàn)證，分別做了特征點(diǎn)分布均勻度實(shí)驗(yàn)，算法耗時(shí)實(shí)驗(yàn)和算法匹配召回率實(shí)驗(yàn)。本文采用了基于區(qū)域統(tǒng)計(jì)信息計(jì)算分布均勻度的方法［15］，如圖8 所示。通過(guò)將圖像劃分為上、下、左、右、左上、右下、左下、右上、中心和外圍10個(gè)區(qū)域。統(tǒng)計(jì)每個(gè)區(qū)域所檢測(cè)到的特征點(diǎn)數(shù)量，然后統(tǒng)計(jì)每個(gè)區(qū)域分布向量的方差V。計(jì)算所得特征點(diǎn)的分布均勻度u如下

圖8 圖像分割示意

式（4）為朱海峰等人［15］給出的特征點(diǎn)分布均勻性的客觀評(píng)價(jià)標(biāo)準(zhǔn)，利用式（4）可以計(jì)算得到整幅圖像內(nèi)特征點(diǎn)的分布均勻度，該數(shù)值越小，就表示不同區(qū)域內(nèi)的特征點(diǎn)數(shù)量差別越小，分布均勻度越好。

對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行均勻化可視化計(jì)算，本文選取了Eu-Roc數(shù)據(jù)集中的部分圖像進(jìn)行特征點(diǎn)均勻化實(shí)驗(yàn)以及耗時(shí)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果分布記錄于表1 和表2。由表1 分析可知，對(duì)比傳統(tǒng)的ORB算法和文獻(xiàn)［9，10］改進(jìn)算法，本文算法對(duì)特征的均勻度有較大的提高。

表1 不同算法分布均勻度比較

表2 不同算法時(shí)間比較

表2為不同算法所耗時(shí)間比較，可以看出：本文算法比ORB算法所耗時(shí)間稍增加了一些，但比文獻(xiàn)［9，10］所改進(jìn)算法仍稍快一籌。

圖9為傳統(tǒng)ORB算法、SURF 算法和本文算法特征點(diǎn)提取結(jié)果，從圖中可以看出傳統(tǒng)ORB算法的提取結(jié)果極為不均勻，大部分都集中于一部分地區(qū)，無(wú)法有效得到整幅圖像的信息；SURF算法提取結(jié)果比與ORB算法相差不大；而本文算法提取到的特征點(diǎn)遍布整幅圖像。

圖9 特征點(diǎn)提取結(jié)果

選取EuRoc數(shù)據(jù)集，并將數(shù)據(jù)集中的圖像做明暗度變化、縮放、旋轉(zhuǎn)操作，通過(guò)本文算法提取400 個(gè)特征點(diǎn)進(jìn)行匹配實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖10所示。圖10（a）為原始圖像匹配結(jié)果，圖10（b）為改變圖像明暗度后匹配結(jié)果，圖10（c）為圖像縮小50%后的匹配結(jié)果，圖10（d）為旋轉(zhuǎn)90°后的匹配結(jié)果。匹配實(shí)驗(yàn)結(jié)果可以看出，本文算法對(duì)于特征匹配結(jié)果質(zhì)量高，匹配結(jié)果都未出現(xiàn)誤匹配。結(jié)果表明：本文算法對(duì)于圖像明暗度變化、圖像縮放、旋轉(zhuǎn)等操作都具有較強(qiáng)的魯棒性。

圖10 本文算法匹配結(jié)果

本文通過(guò)大量實(shí)驗(yàn)比較了5 種算法的平均所用時(shí)長(zhǎng)，結(jié)果如表3。結(jié)果表明，SURF 算法所用時(shí)間最長(zhǎng)，ORB 算法所用時(shí)間最短，本文算法略高于ORB 算法，仍遠(yuǎn)低于SURF算法，對(duì)比文獻(xiàn)［9，10］改進(jìn)ORB 算法，本文算法速度更快。

表3 不同算法平均所用時(shí)間 s

召回率可以反映匹配算法的查全率，即正確匹配占實(shí)際全部匹配的比例。本文經(jīng)過(guò)了多次實(shí)驗(yàn)，得到的結(jié)果如表4。對(duì)比ORB算法，本文算法的召回率有明顯的提升；比SURF算法仍有不足之處，因?yàn)镾URF 是構(gòu)造尺度空間，通過(guò)高斯微分函數(shù)識(shí)別興趣點(diǎn)，而不是直接提取角點(diǎn)，魯棒性好。文獻(xiàn)［10］改進(jìn)ORB算法對(duì)于正常的圖像，具有較高的召回率，但其對(duì)于旋轉(zhuǎn)的魯棒性較差。而本文算法在改變明暗度、對(duì)圖像進(jìn)行縮放、旋轉(zhuǎn)操作時(shí)，召回率變化不大，可以看出，本文算法對(duì)圖像明暗變化，縮放旋轉(zhuǎn)等操作時(shí)都有較強(qiáng)的魯棒性。

表4 不同算法平均召回率 %

4 結(jié)束語(yǔ)

本文算法通過(guò)構(gòu)建四叉樹(shù)和融合BRIEF-LBP 描述子的方法來(lái)實(shí)現(xiàn)ORB算法中特征點(diǎn)的均勻分布以及特征匹配的準(zhǔn)確性。首先，對(duì)輸入圖像構(gòu)建金字塔尺度空間，在每一圖層上進(jìn)行FAST關(guān)鍵點(diǎn)的檢測(cè)；其次，通過(guò)構(gòu)建四叉樹(shù)來(lái)限制特征點(diǎn)分布；最后，在生成描述子的過(guò)程中用128 位LBP描述算子融合BRIEF中256位描述子形成新的384位的特征描述子，新的描述子可以更充分的表達(dá)圖像信息，使得匹配結(jié)果更為精確。實(shí)驗(yàn)結(jié)果表明：對(duì)比傳統(tǒng)ORB，本文算法雖然在速度上比ORB算法降低了5%，但均勻度提升了66左右，召回率也提升了10%；與其他改進(jìn)算法［9，10］相比，本文算法速度提升了2%～5%的同時(shí)，特征點(diǎn)分布均勻度提升了48 和49，召回率也提升了36.63%和4.925%。實(shí)現(xiàn)了在少量增加計(jì)算量的同時(shí)，特征點(diǎn)均勻度和匹配精度方面效果有較大提升。