基于四叉樹的ORB特征階梯分布算法

季莘翔，王宇鋼，林一鳴

（遼寧工業大學 機械工程與自動化學院，遼寧 錦州 121001）

0 引言

視覺同步定位與建圖（Visual Simultaneous Localization And Mapping，V-SLAM）因為其體積小、性價比高、信息豐富的優點，已成為機器視覺的重點研究方向[1-2]。其中ORB算法因其計算速度快的優勢，被應用于SLAM當中，對計算相機位姿起著決定性的作用[3-4]。

ORB-SLAM中的ORB算法由Mur-Artal等[5]提出。該算法具有尺度不變性、旋轉不變性和計算速度快的優勢，但其提取特征點的數量有限，且在圖片中分布過于密集，影響匹配精度[6-7]。因此學者基于此算法進行了改進。王通典等[8]采用多尺度網格化的方法提取ORB特征點并利用四叉樹均勻分配特征點。姚晉晉等[9]通過對不同的圖片灰度值檢測，計算出適應不同圖片的閾值算法，該算法具有更強的抗干擾能力，但仍需要大量運算時間。于雅楠等[10]提出了一種特征點法視覺里程計自適應優化算法，該算法有助于改善光照條件變化時圖像特征的穩定性，但提取的特征點數量不足，特征重疊明顯。

針對上述情況，本文提出了一種基于四叉樹的ORB特征階梯算法。采用四叉樹算法對圖片進行分割，基于特征點分布的疏密程度劃分區域，對每個區域設置遞減的四叉樹深度；通過設置閾值middleThFAST，提取出成階梯趨勢數量的特征點，在保證圖片特征點均勻性的同時提升提取效率和特征點數量。此外，本文提出了一種客觀評價標準——覆蓋均勻度，對圖片特征點的分布均勻性進行量化評價。

1 階梯ORB算法

1.1 傳統ORB算法

ORB 算法結構包括oFAST 檢測和rBRIEF（rotation BRIEF）描述子計算[11-12]。從FAST算法改進得到的oFAST算法能夠使特征點在圖像中具有方向信息。該算法通過比較待測像素點p與周圍16個像素點的灰度值差值，來判斷該點是否為角點。如果16個像素點中有9個以上大于設定的閾值，則判定為角點，如式（1）所示：

式中：I（x）為范圍內16個像素點中的任意一個點的灰度值，I（p）為待確定的點的灰度值，t為設定的閾值。

當以設定的閾值（iniThFAST）提取的特征點數量不滿足設定值時，會降低閾值至minThFAST再次提取特征點。

使用灰度質心法使特征點具有方向。計算步驟具體如下。

1）在一個圖片中，定義點（x，y）鄰域矩為

式中：I（x，y）為圖像灰度值，n為特征點的鄰域。

2）鄰域的質心坐標可表示為

圖像的幾何中心O與特征點鄰域內的質心C相連，即得到特征點的方向：

rBRIEF是為了解決BRIEF不具備旋轉不變性而改進的二進制描述子，并對角點進行平滑處理。在特征點附近邊長為31的正方形像素區域內采用邊長為5的正方形子窗口的灰度值之和作為判斷描述子的依據，得到描述子分段函數，計算式如（5）：

式中：p（x）為點x的像素灰度值，p（y）為點y處的像素灰度值，τ即為描述子。

此外，為了使描述子具有較好的旋轉不變性，再將特征點的方向加入到其中。使得最終描述子公式為

其中，A是對于任意n位置坐標（xi，yi），構造2×n矩陣。

1.2 階梯ORB算法

針對傳統ORB算法在提取時特征點分布不均的問題，采用四叉樹算法劃分出特征點疏密不同的區域，對特征點集中區域多次分割，使特征點分布在整幅圖片上；根據特征點數量，由高至低依次降低分割次數。同時針對分割區域，分別設置兩個高數量區域和兩個低數量區域，使特征點分布呈階梯性，從而提高單幅圖片的特征點數量和均勻性。

傳統ORB算法中minThFAST太低會導致計算次數過多，增加運行時間；minThFAST太高會導致在灰度值差值較小的區域提取不到特征點，特征點數量下降。因此，本文算法在iniThFAST和minThFAST中間加入middleThFAST，實現對劃分區域的FAS角點的自適應提取，既能夠提取到足夠的特征點，又可以提升特征點提取效率。算法步驟如下：

1）設置參數，分別設定iniThFAST、middleThFAST和minThFAST，分割次數i=0；

2）用四叉樹算法分割圖片，按照特征點數量確定兩個高數量區域和兩個低數量區域，分割次數i=i+1；

3）對兩個高數量區域，根據iniThFAST 和middleThFAST分別按38%和32%提取特征點，對兩個低數量區域，根據middleThFAST和minThFAST閾值分別按17%和13%提取特征點；

4）判斷是否為高數量區域，如果是則轉到步驟5），否則轉到步驟6）進行圖像拼接；

5）分割次數i是否小于4，如果是則執行步驟2），對高數量區域進行再次分割，否則不再分割圖片，轉到步驟6）；

6）將步驟4）和步驟5）的圖片分割區域進行拼接，構建描述子。

經試驗確定，當本文算法分割次數大于3次時提取特征點分布結果不再明顯變化，但運算時間會隨分割次數顯著增加。因此，本文將最大分割次數設定為3次。算法流程如圖1所示。

2 覆蓋均勻度

文獻[13]提出了一種基于區域統計信息計算特征點分布均勻性的方法，即分布均勻度評價標準。研究表明該標準可以客觀反映特征點的分布均勻程度，分布均勻度越低，說明特征點越均勻地分布在圖片中。目前此標準已被廣泛用于特征點分布均勻性評價。

但在部分圖片中，該標準無法準確反映圖像特征點的分布均勻性。以相框圖片為例，當相框按照1.50、1.00、0.75的比例縮放時，圖2為對應特征點提取結果。圖2中（a）、（b）和（c）的特征點在圖幅中面積占比分別是47%、25%和20%。

從主觀判斷，圖2（a）的特征點均勻性最好，圖2（b）和圖2（c）相近。由表1可知，圖2（a）和圖2（c）分布均勻度數值相近，圖2（b）分布均勻度數值比圖2（a）和圖2（c）低50%。由于圖2（b）的特征點恰好密集地分布在各個區域的分界線上，導致特征點雖然密集，但分布均勻度的數值卻很低，因此沒有反映出特征點分布均勻性特征。

因此，本文提出了一種新的特征點分布均勻性評價標準——覆蓋均勻度，即從分布均勻度和覆蓋面積兩個方面對圖片特征點分布均勻性進行綜合評價。覆蓋均勻度越低，表明分布均勻性越好。覆蓋均勻度計算過程如圖3所示。

圖3 覆蓋均勻度計算過程

1）將圖片分為10個區域，分別為上、下、左、右、右上、左下、左上、右下、中心和外圍，統計各區域特征點數量的方差，得到分布均勻度，計算式為

式中：U為分布均勻度，v為方差。

2）對特征點進行膨脹，將所有距離相近的特征點相連，再進行圖片腐蝕，把每個特征點膨脹后多余的面積腐蝕掉，得到覆蓋面積。最后統計覆蓋面積覆蓋的像素。

3）分布均勻度與特征點覆蓋面積的比值即為覆蓋均勻度，計算式為

式中：P為覆蓋均勻度，U為分布均勻度，np為被覆蓋特征點像素，na為圖片總像素。

由表1可知，圖2（b）的分布均勻度是最低的，圖2（a）和圖2（c）的分布均勻度基本一致；圖2（a）覆蓋均勻度為最低，圖2（b）次之，圖2（c）為最大。覆蓋均勻度結果真實反映了圖片特征點的分布均勻性，也與人的主觀判別是一致的，而分布均勻度未能有效評價特征點的分布均勻性。因此覆蓋均勻度比分布均勻度評價結論更客觀。

3 試驗與分析

試驗運行環境：操作系統為VM 虛擬機Ubuntu18.04LTS，CPU為Intel(R)Core(TM)i7-10875H，主頻為2.30 GHz，內存為8G，開發語言為C++。本文采用Mikolajczyk數據庫進行試驗驗證，選取其中在特征點分布具有代表性的5組數據集：模糊程度不同的數據集（bike）、對比度不同的數據集（leuven）、單一背景且占用大部分圖幅的數據集（bark）、環境復雜且占用大部分圖幅的數據集（trees）和不同壓縮程度的數據集（ubc）[14]。

針對以上數據集分別采用傳統ORB算法、Mur-Artal算法（MA算法）和本文的階梯ORB算法進行對比試驗，以驗證本文算法有效性。試驗參數：特征 點 提 取 數 量 為500；iniThFAST、middleThFAST、minThFAST值分別為8、14、20。對每組數據集進行24次試驗，去掉其中兩個最大值、兩個最小值，取剩余20組數據的平均值作為試驗結果。

圖4為3種算法在bark數據集的部分提取結果，圖中不同大小的圓和紅點為提取的特征點位置。由圖可知，傳統ORB算法提取特征點時，提取到的特征點數量有限，主要集中在圖片中間的石頭縫隙部分，綠色樹葉提取到的特征點卻很少，分布極不均勻；本文算法提取到的特征點比傳統ORB算法和MA算法更多，而且分布在整幅圖片上，對綠色樹葉也提取到更多數量的特征點。

圖4 bark數據集img1、3、4提取結果

算法對bark數據集的試驗結果如表2所示。由表2可知，在bark數據集中，本文算法運算時間比MA算法平均節省18%；提取的特征點數量比傳統ORB算法平均多出15%，比MA算法平均多2%；在均勻性方面，本文算法分布均勻度要比傳統OEB算法平均低14%，覆蓋均勻度比傳統ORB算法平均低28%，比MA算法平均低3%。因此本文算法對單一背景圖片能提取出更多的特征點，運算效率更高，特征點分布更均勻。

表2 bark數據集試驗結果

圖5為高模糊數據集bikes的img5和img6圖片提取結果。由圖5可知，傳統ORB算法提取的特征點不僅集中在摩托車區域附近，而且特征點數量少。本文算法提取的特征點既均勻分布在整幅圖片，數量又遠高于傳統ORB算法。

圖5 bikes數據集img5和img6提取結果

表3為bike數據集的試驗結果。由表3可知，在時間方面本文算法比MA算法平均節省18%；在特征點數量方面，對序號1～4的低模糊圖片，本文算法和MA算法的特征點提取數量比傳統ORB算法平均多6%，對序號5和6的高模糊圖片，本文算法特征點提取數量比傳統ORB算法平均多110%；在均勻性方面，本文算法分布均勻度比傳統ORB算法平均低10.3%；覆蓋均勻度比傳統ORB算法平均低53%，比MA算法平均低5%。因此本文算法對高模糊圖片有更強的抗干擾能力，能提取出更多的特征點，運行效率更高，特征點分布更均勻。

表3 bike數據集試驗結果

數 據 集leuven、ubc、trees分別包含6張圖片，在運行時間、特征點提取數量、分布均勻度和覆蓋均勻度的試驗結果分別如圖6～圖9所示。

圖6 運行時間的試驗結果

由圖6可知，在運算時間方面，本文算法比傳統ORB算法有所增加，但與MA算法相比大幅減少。如圖6 所示，對leuven、ubc和trees數據集，本文算法分別平均減少20.57%、25.74%和15.32%。

由圖7可知，特征點提取數量因為trees數據集紋理平均，3種算法所提取到的數量相差不到6%。在ubc和leuven數據集中，本文算法特征點數量比傳統ORB平均多10.45%，比MA算法平均多3.22%。

圖7 特征點提取數量的試驗結果

在均勻性方面，由圖8可知，因為本文算法具有階梯性，所以每組數據集的分布均勻度比MA算法平均高4.23%，比傳統ORB算法平均低14.66%。由圖9可知，因為綜合了分布均勻度和覆蓋面積，本文算法的覆蓋均勻度比傳統ORB算法平均低20%。雖然本文算法在均勻性上略高于MA算法，但在時間和特征點數量上表現優異。用少量的均勻性提高換取計算效率和匹配精度的提高是極具性價比的。

圖8 分布均勻度的試驗結果

圖9 覆蓋均勻度的試驗結果

綜上所述，對不同條件下的圖片數據集，本文算法的均勻性比傳統ORB算法平均低17%；特征點提取數量平均多10.45%。與應用廣泛的MA算法相比，運算時間大幅降低了20.54%。在特征分布均勻性方面，覆蓋均勻度的評價結果與分布均勻度的評價結果基本一致，表明本文算法比傳統ORB算法和MA算法均有提升。

4 結語

為了解決傳統ORB算法特征點數量不足、特征點分布呈集中性的問題，本文提出一種基于四叉樹的ORB特征階梯分布算法。對于特征點疏密不同的區域，設置呈階梯性的分割次數和特征點數量。試驗結果表明，本文算法比傳統ORB算法提取的特征點平均多10.45%，特征點的分布均勻性平均低30%，運行時間比MA算法平均降低了20.54%。本文算法提取的特征點數量更多，分布更均勻，計算效率更高。因此，本文算法對SLAM后續的位姿估計以及建圖具有實際應用價值。