基于四叉樹的ORB-LBP改進算法*

陳易文，儲開斌，張 繼，馮成濤

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

0 引 言

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

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

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

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

1 傳統ORB算法

ORB是一種局部特征提取方法，它利用加速分割測試特征（features from accelerated segment test，FAST）［11］關鍵點檢測器提取圖像特征關鍵點，利用BRIEF［12］描述子提取圖像特征描述子。

1.1 FAST角點檢測算法

以待檢測像素為圓心，3 個像素值為半徑，做一個圓，與圓相交的共有16 個像素，檢測16 個像素中與中心點的像素差大于某個閾值T 時，計數n 加1，若16 個點檢測完成時n ＞N（N 一般取11 或者9），則認為該待檢測像素為角點，然后循環此過程檢測每一個像素［11］。

1.2 BRIEF描述子

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

圖1為傳統ORB的特征點檢測結果，可以看出所檢測到的特征點都容易集中于部分區域，特征點分布極度不均勻；只有在一部分特征明顯的區域存在密集的特征點，而在大部分區域都未能檢測到特征點，因此會導致后續匹配精度差。

圖1 傳統ORB特征點檢測

圖2為傳統ORB特征點結合暴力匹配得到的匹配結果，可以看出：所匹配的精度不高，匹配效果差，多處出現了誤匹配現象。

圖2 傳統ORB特征點匹配

2 基于融合描述子的改進ORB算法

圖3為算法整體流程。首先，構建圖像金字塔，通過劃分網格計算角點提取閾值來提取FAST角點；其次，通過構建四叉樹使角點分布均勻；然后，通過融合BRIEF-LBP的方法對提取的角點進行特征描述；最后，利用隨機抽樣一致性（random sampling consistency，RANSAC）的方法進行特征匹配。

圖3 本文算法流程

2.1 構建圖像金字塔

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

圖4為不同金字塔層所檢測的特征點結果，分別建立了7層、5層、3層金字塔，可以看出在不同層數金字塔下圖像所提取到的角點都有所區別。通過實驗，最終建立3層金字塔層，達到效果最優。

圖4 不同金字塔層特征點

2.2 角點提取

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

式中 α為一個自適應變量，本文α取1.2；m為網格內像素點數量。在每個網格中對各像素與閾值T 進行比較，進行角點提取，若在該網格中未提取到角點，則將閾值T降低為原有的1／2，再進行角點提取。遍歷所有網格，直至提取到的角點數量滿足設定的角點數量。

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

圖5 角點提取

2.3 構建四叉樹

首先，通過2.2節的方法對整張圖像進行角點檢測；然后，將整個圖像空間劃分為4個相同的子空間，若在子空間內檢測到的角點數量大于1，則繼續將該子空間分裂為4個新的子空間繼續檢測；但若特征點數量太多，會導致四叉樹的深度過深，在進行空間檢索時效率會比較低下。因此，本文限制了四叉樹的深度為4 層，若深度達到4 層后子空間內的角點數量仍大于1，則留取子空間內響應值最大的角點，舍棄其他角點，如圖6所示。

圖6 四叉樹示意

2.4 BRIEF-LBP融合描述子

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

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

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

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

其次，以特征點為中心，半徑為R 做圓形區域。一個中心像素點（x，y）周圍的其他像素點gk的坐標（xk，yk）可以表示為

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

本文將得到的256 位BRIEF 描述子與128 位LBP 描述子級聯得到新的384 位的二進制描述符，將該新的描述子作為特征點的描述子。

2.5 特征匹配

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

3 實驗驗證

所用的實驗平臺配置為Intel?CoreTMi5—8265U，內存1.60 GHz。采用了EuRoC公開數據集［14］中的圖片，該數據集包括了視覺（雙相機）測量得到的數據。將本文算法與ORB算法、SIFT算法以及文獻［9，10］中改進的ORB 算法進行對比實驗驗證，分別做了特征點分布均勻度實驗，算法耗時實驗和算法匹配召回率實驗。本文采用了基于區域統計信息計算分布均勻度的方法［15］，如圖8 所示。通過將圖像劃分為上、下、左、右、左上、右下、左下、右上、中心和外圍10個區域。統計每個區域所檢測到的特征點數量，然后統計每個區域分布向量的方差V。計算所得特征點的分布均勻度u如下

圖8 圖像分割示意

式（4）為朱海峰等人［15］給出的特征點分布均勻性的客觀評價標準，利用式（4）可以計算得到整幅圖像內特征點的分布均勻度，該數值越小，就表示不同區域內的特征點數量差別越小，分布均勻度越好。

對實驗結果進行均勻化可視化計算，本文選取了Eu-Roc數據集中的部分圖像進行特征點均勻化實驗以及耗時實驗，實驗結果分布記錄于表1 和表2。由表1 分析可知，對比傳統的ORB算法和文獻［9，10］改進算法，本文算法對特征的均勻度有較大的提高。

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

表2 不同算法時間比較

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

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

圖9 特征點提取結果

選取EuRoc數據集，并將數據集中的圖像做明暗度變化、縮放、旋轉操作，通過本文算法提取400 個特征點進行匹配實驗，實驗結果如圖10所示。圖10（a）為原始圖像匹配結果，圖10（b）為改變圖像明暗度后匹配結果，圖10（c）為圖像縮小50%后的匹配結果，圖10（d）為旋轉90°后的匹配結果。匹配實驗結果可以看出，本文算法對于特征匹配結果質量高，匹配結果都未出現誤匹配。結果表明：本文算法對于圖像明暗度變化、圖像縮放、旋轉等操作都具有較強的魯棒性。

圖10 本文算法匹配結果

本文通過大量實驗比較了5 種算法的平均所用時長，結果如表3。結果表明，SURF 算法所用時間最長，ORB 算法所用時間最短，本文算法略高于ORB 算法，仍遠低于SURF算法，對比文獻［9，10］改進ORB 算法，本文算法速度更快。

表3 不同算法平均所用時間 s

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

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

4 結束語

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