改進ORB-SLAM算法在戶外離線即時導航的研究

鄒倩穎, 關杰文, 肖 航, 符鑫珺

(電子科技大學 成都學院 云計算科學與技術系，成都 611731)

0 引 言

隨著無人駕駛、無人勘探、AR/VR的應用日漸增多，優化并更有效應用ORB-SLAM算法成為亟需解決的問題。文獻[1]中使用一種處理灰度圖像的算法，利用自適應閾值選取算法，直接利用圖像灰度進行低層次圖像處理，且具有處理速度快等特點，但其在強高斯噪聲和椒鹽噪聲環境下，檢測效果較差。在FAST算法中，關鍵點又稱為角點[2]，若一個點的像素及灰度值與鄰域點的像素值差別較大或較小,那么它可能是角點。FAST算法以速度快而著稱，但在判斷特征點時使用的是固定閾值方法，不能很好地適應色彩變換較大的圖像。

文獻[3]中提出了另一種角點檢測算法，Harris算子是一種基于信號的特征點提取算子，由于受到自相關函數引導，通過計算圖像移動的灰度變化情況，對圖像灰度進行一階導數估算自相關矩陣來得出特征值，使Moravec算子具有了旋轉不變性和光照不變性。但Harris角點檢測算法僅對圖像進行一次高斯平滑，沒有解決單一尺度問題，對噪聲的抗性也不足，而非極大值抑制的關鍵在于閾值的選取，閾值過大會讓角點數量少;閾值過小會出現偽角點，精度方面自然不能保障。雖然后期的高斯尺度空間與Harris角點檢測算法的結合解決了尺度不變性問題，同時達到了去噪的效果，但卻大大增加了運算時間。同時，在戶外進行地圖路徑規劃時，實時性與特征點提取的精度也直接影響到了地圖路徑的規劃。

針對特征點提取時固定閾值選取算法靈活性不足和傳統的多尺度Harris角點檢測耗時過多的問題，提出一種基于自適應閾值選取和局部搜索算法的改進室外場景特征點提取算法。通過采用改進室外場景特征點提取算法，計算圖像局部點的灰度值與圖像平均灰度值的方差表示對比度，然后利用積分圖像求得局部灰度值的平均值，采用對比度與其局部灰度值的平均值來求得局部動態閾值，在計算卷積積分和拉普拉斯響應值篩選中通過局部搜索算法代替逐一比較的方法，降低了運算復雜度，使得實時處理制圖數據得以提升。

1 改進室外場景特征點提取算法

1.1 算法流程

本文算法流程如圖1所示,算法流程如下所示。

(1) 粗提取。特征點提取時，先進行閾值選取，劃定要判定點的區域,運用積分圖像進行局部平均閾值的計算。然后計算選取點的灰度值與局部圖像平均灰度值的方差近似于對比度，利用對比度以及圖像局部平均閾值的關系計算出最適宜于該點的閾值。

(2) 非極大值抑制。利用非極大值抑制來解決選取的多個特征點由于過于聚集形成特征塊的問題。為每個檢測到的特征點計算它的響應值。響應值是p點與它周圍16個點的絕對差值,尤其先考慮2個相鄰的特征點，并比較它們的值。響應值較低的點將會在選取的特征點中去除。

(3) ID3算法。將粗提取后的特征點作為一個訓練集，使用ID3算法查詢每個集合，訓練為一個決策樹，用于檢測其他相似圖片的OFAST檢測。

圖1 算法流程

(4) Harris角點檢測。將目標圖像進行高斯平滑處理，在x或y方向上取微分，決定了Harris角點當前尺度的變量和角點附近微分值變化的變量。為了判斷角點是否為該局部尺度下的特征點，對提取的角點進行響應值計算，然后在點的鄰域內進行響應值比較，搜索出響應值最大的點。

(5) 多尺度Harris角點檢測。對每個尺度都進行計算，對于位置空間的每個候選點進行拉普拉斯響應計算，并滿足絕對值大于給定的閾值條件。對滿足條件的點進行局部搜索算法進行比較，得出既滿足位置空間又適合尺度空間的Harris角點。

(6) BRIEF特征描述。在一定區域內取一對像素點，然后分別比較每對像素點的灰度大小并賦值于1或0，采用二進制編碼，用Hamming距離[4]進行描述子的比較與匹配。

1.2 局部動態閾值確定

在FAST算法中，閾值[5]所代表的就是在提取特征點是其與周圍鄰域的點的最小對比度，也是其所能消除噪聲的最大限量。閾值所選取的值直接影響了特征點提取的精準度。閾值越大，所提取的特征點也就越少;閾值越小，選取的特征點也就越少。在原有的FAST-12算法中采用的固定閾值的方法雖然在計算量上進行了一定的減少，但因為閾值是固定的，所以當在野外進行拍照完后，圖像中很可能存在陰影，由于突發噪聲等客觀因素，不能很好地使得閾值的選取能隨著全局圖像灰度以及噪聲的影響而隨之變化。本文中提出了采用動態設置局部閾值T的方法[6]對特征點進行提取。局部動態閾值T的選取能隨著局部不同特征點所具有的不同情況，得出一個對于特征點提取最適宜的閾值，以使得提取的特征點更加精確。

在FAST-12算法中，進行特征點的選取時實質上就是特征點的灰度值在于其周圍點灰度值對比度的衡量[7]。對比度可以簡單地理解為一幅圖像里圖像灰度反差的大小，也就是圖像中各點的灰度值與平均灰度值之間的差異大小。因此在粗提取的改進上本文根據局部閾值與對比度相關，建立函數，以此實現局部閾值跟隨局部圖像變化而變換的目的。在粗提取中分析了對比度與圖像閾值之間的關系，提出了圖像在不同區域L下自適應閾值的計算。在圖像上選取點為(x0，y0)，以(x0，y0)為中心取矩形區域，定義隨全局圖像變化而變化的閾值

(1)

式中：k為比例系數，根據相關實驗,k值范圍2.5～5.0時選取結果較為準確；

為所求選取區域內各點灰度值與區域內平均灰度值的方差，以此來近似表示該區域內的對比度;m(x0,y0)為局部區域內的平局灰度值。

本文采取Viola和Jones積分圖像定義快速地進行局部均值的計算，

(2)

式中：i(x,y)表示輸入圖像中的像素點；ii(x,y)表示積分圖像，

ii(x,y)=ii(x-1,y)+s(x,y)

(3)

s(x,y)=s(x,y-1)+i(x,y)

(4)

式中：s(x,y)表示點(x,y)的y方向上的所有原始圖像之和，而對于計算選取的任一區域L內的局部均值，

(5)

式中：iiL(x,y)表示在區域L內的圖像局部積分圖像，則局部均值,

(6)

m(x,y)表示在區域L內的局部積分圖像;(x-u)(y-v)表示區域L的面積。

1.3 非極大值抑制

在FAST算法中，關鍵點又稱角點，主要檢測局部像素灰度值變化明顯的地方，以速度快而著稱。角點的定義為如果一個點的像素及灰度值與鄰域點的像素值差別較大(過亮或過暗)，那么它可能是角點，即在選取的點周圍有足夠多的點的灰度值大于或小于它，那么就定義此點為一個特征點。

如圖2所示，在圖像中選取一點p，在其周圍形成一個圓形區域(半徑為3的Bresenham圓[8])，則圓心p被16個像素點包圍。在16個像素點形成的圓周上，如果有n個連續點的灰度值大于Ip+T或小于Ip-T，那么像素點p可以認為是一個候選特征點。n值通常選取為12時，能快速地排除一些非特征點，于是該算法[9]也被稱為FAST-12算法。算法步驟如下：

(1) 在圖像中選取像素點p，計算的灰度值，在圖像中每點顏色都由紅、綠、藍三基色組成，假如在圖像中任一點的顏色可以用坐標RGB(R，G，B)，那么該點坐標可計算出灰度值為：0.11B+0.59G+0.3R。

(2) 設置閾值T。

(3) 以像素p為中心，選取半徑為3的圓上的16個像素點。

圖2 FAST粗提取原理圖

假如選取圓上有連續N個點的灰度值大于Ip+T或者小于Ip-T，那么認定該點為一個特征點，循環以上3個步驟，并對每個選取點執行相同的操作。

1.4 ID3算法

ID3算法[10]利用信息論中信息熵下降速度為選擇標準，核心在于決策樹各個結點上最高信息增益屬性作為選擇特征，通過貪心策略遞歸構建決策樹，直到決策樹能很好地分類訓練集。

算法步驟如下所示。有輸入數據集S，特征集F，閾值M，通過遞歸運算計算并輸出決策樹R。

(1) 若數據集S中所有個體屬于同一類Ck，則R為單結點樹，并將Ck作為該結點的類標記，返回R。

(2) 若F為空集，則R為單結點樹，并將數據集S中個體數最大的類Ck作為該結點的類標記，返回R。

(3) 對特征集F中各特征對數據集S的信息選擇增益，選擇信息增益最大的特征Ag。

(4) 如果Ag的信息增益小于閾值M，則置R為單結點樹，并將數據集S中實例數最大的類Ck作為該結點的類標記，返回R。

(5) 對Ag的每一可能值Ai，依Ag=Ai將數據集S分割為若干個非空子集Si，將Si中實例數最大的類作為標記，構建子結點，由結點及其子結點構成樹R，返回R。

(6) 對第i個子結點，以Si為訓練集，以F-{Fg}為特征集，遞歸地調用步驟(1)～步驟(5)，得到子樹Ri，返回Ri。

1.5 Harris角點檢測

Harris[11]實現了旋轉不變性，Harris算子提出一種基于信號的點特征提取算子。由于受到自相關函數的啟發，通過平移窗口帶來變化的自相似性來衡量角點，Harris算子效率極高，操作簡單，只涉及一階導數，在紋理信息豐富區域，能夠提取出大量有用的特征點，通過Harris計算每個點的響應值并通過非極大值算法進行特征點的篩取，提取一定數量的優質特征點。若想要增多被檢測特征點數量，那么就減小α的值，并且角點響應值R將增大，角點檢測的靈活性將提高；反之，亦然。通過這種方法還能夠實現圖像旋轉不變性，對亮度和對比度變化不敏感性。

如圖3所示，若角點位置上的窗口倘若在其各方向上移動，區域內灰度值會發生較大變化，如果只在一個方向上移動時有較大變化，那么該點大概率在直線上；如果各個方向上移動都無變化，那么可能無角點。

圖3 窗口移動示例

窗口移動后自相似性衡量如下式所示：

I(u+Δx,v+Δy))2·w(u,v)

(7)

式中：W(x·y)是以(x,y)為中心的窗口;w(x,y)是以(x,y)為中心的高斯加權函數;I(u,v)是窗口函數;Δx是在水平方向上的微小偏移量;Δy是在豎直方向上的微小偏移量。

一階近似并化簡，

(8)

M(x,y)=

(9)

用字母代替，

(10)

則可將自相關函數視為一橢圓函數，

C(x,y,Δy,Δx)≈AΔx2+2CΔxΔy+BΔy2

(11)

Harris則利用角點響應值R來判斷角點，

R=detM-α(traceM)2

(12)

Harris角點檢測能夠做到實時性，但是該算法只能在單一尺度下檢測角點，而非極大值抑制的關鍵在于閾值的選取，閾值過大會讓角點數量少，閾值過小會出現偽角點，精度方面自然不能保障。

1.6 多出度Harris角點檢測

1.6.1 高斯尺度空間的構建

對輸入圖像和可靈活選擇多個尺度的高斯核函數[12]進行卷積運算，

L(x,y,σ)=G(x,y,σ)*I(x,y)

(13)

式中：σ表示尺度;L(x,y,σ)表示尺度空間;G(x,y,σ)表示高斯核函數;*表示卷積運算;I(x,y)表示輸入圖像。隨著圖像尺度的變化，原來的局部特征也會變化，可能會出現新的局部特征或者消失。

1.6.2 尺度響應值計算

對于尺度空間響應值計算構建一個點在領域內的梯度分布為

M=μ(x,y,σI,σD)=

(14)

式中：

Lx=I(x,y)*Gx(x,y,σ)

Ly=I(x,y)*Gy(x,y,σ)

x,y∈W(u,v)為圖像窗口中的坐標;σD,σI分別表示微分尺度和積分尺度，σI是決定Harris角點當前尺度的變量，σD是決定角點附近微分值變化的變量;Ly(x,y,σD)、Lx(x,y,σD)分別是對圖像進行高斯處理后對x或y方向取微分的結果;g(σI)表示尺度為σI的高斯卷積核。

檢測算法從預先定義一組尺度進行積分尺度搜索，其中，σI…σn=σ0…knσ0。

一般K取1.4，但為了減少復雜性，令σD=sσI，從而得到μ(x,y,σI,σD),隨后利用Harris角點進行響應判斷:

cornerness=det(μ(x,y,σD)-

αtrace2(μ(x,y,σD))>thresholdH

(15)

對于滿足式(9)的點進行周圍8領域非最大值抑制，對于滿足條件的每個尺度σn(n=1,2,…,n)都進行遍歷搜索，因為空間位置候選點未必是尺度空間候選點，進行尺度搜索，尋找局部結構的顯著尺度，

(16)

對于滿足式(16)的點進行鄰近兩個尺度空間的拉普拉斯響應值進行比較得到各空間上的顯著尺度值。

1.6.3 局部搜索算法

針對實時性繪圖效率以及精度問題，本文在文獻[13]基礎上進行改進，使用局部搜索算法來代替逐一比較方法，提高了效率，又剔除了大部分偽角點，能在局部范圍內提取更穩定特征點，達到了了實時性的效果。

對于閾值thresholdL進行適度降低，從而得到較多特征響應值，排除了閾值過高特征響應值較少的問題，從而保留了一定尺度上有極大概率有響應值與其匹配。

利用局部搜索算法[14]，具體算法步驟如下:將進行閾值比較后的特征響應值生成一個算子集{p}。

(1) 在p內生成初始的可能解xi，在xi∈p中如果有xi，執行步驟(2)，否則執行步驟(5)。

F(x,y,σn)>F(x,y,σl)

(17)

l∈{n-1,n+1}

對于滿足式(17)的尺度值就是改點的特征尺度值，則是空間和尺度空間都滿足的Harris角點。

1.7 BRIEF特征描述

BRIEF是對已檢測到的特征點進行一種二進制編碼描述，這種方法棄用了傳統通過局部區域灰度直方圖來描述特征點的方法。該方法特征描述符建立速度進行了提升，同時也一定程度上將特征匹配的時間進行了縮短，是一種非?？旖荩苡袧摿Φ乃惴?。

首先，將圖像進行處理，然后在特征點周圍選擇一個一定大小的局部區域，在這個局部區域內選擇出來m個點對。然后對于每一個點對(p,q)，通過比較這兩個點的亮度值(用N()函數表示)，如果N(p)N(q)，則這個點對生成了二值串中一個的值為1,否則為0。所有m個點對，都進行比較，就生成了一個m長的二進制串。

2 實驗結果及分析

2.1 實驗環境與數據集

本文選取Sturm等提供的數據源。通過使用搭載Kinect深度攝像機的Pioneer機器人采集的關于不同場景的數據集[15]驗證改進算法的性能。這些數據包含了豐富的常見物體，并具有良好的數據采樣光照度，可有效測試算法性能。本文程序基于VS2017的C++實現上述改進算法，所有實驗運行環境為Intel雙核2.30 GHz CPU計算機，運行系統為Ubuntu 16.04 LTS 。

2.2 結果分析

2.2.1 特征點提取個數對比

本文針對相同場景的不同圖像進行比較，通過改變圖像的亮度分別對SIFT算法(見圖4(a))，優化前的OFAST算法(見圖4(b))，以及優化后的OFAST算法(見圖4(c))特征點提取效果進行比較。

(a) SIFT算法

(b) OFAST算法

(c) 改進OFAST算法

實驗結果中SIFT算法提取特征點個數為206個，原有OFAST算法提取特征點個數為179個，改進后的OFAST算法體征點提取個數為116個；

改進OFAST算法相比較原有OFAT算法在特征點個數減少了35.2%。由此可見，本文中的算法所提取的特征點數量遠少于原OFAST算法和SIFT算法，其特征點匹配更為精準，制圖效果誤差大大減少。

2.2.2 平均時間對比

提取時間代表了算法在提取特征點的快慢，在野外環境進行導航時，時間是一大重點，時間越快,算法性能更強。

SIFT算法提取特征點時間為375.3 s，原有OFAST算法提取特征點時間為9.3 s，改進OFAST算法提取特征點時間為1.3 s。實驗證明,改進后OFAST比原有OFAST算法在提取特征點時效上提高了80.6%，而改進后OFAST比SIFT算法在提取特征點時效上提高了99.6%。由此可見，改進后的OFAST算法節省了大量的時間，其工作效率遠遠高于原OFAST算法和SIFT算法。

2.2.3 匹配正確率對比

提取特征點的匹配正確率對于后期制圖有著重要的作用，匹配正確率越高，對于后期制圖的效果更佳，對于路線規劃更為清晰。

SIFT算法正確率為15.2%，原有OFAST算法正確率為37.4%，改進OFAST正確率為51.8%,改進后OFAST算法相比原有OFAST算法正確率提高了14.4%，改進OFAST正確率為51.8%,改進后OFAST算法相比SIFT算法正確率提高了36.6%。由此可見,改進后的OFAST算法可以更精準地匹配特征點，且精準程度遠大于原OFAST算法和SIFT算法。

總而言之,原有的OFAST需要耗費大量時間來創建金字塔模型[16]，并對高斯差分圖像通過泰勒公式進行展開，消耗大量時間。本文利用局部搜索算法簡化局部特征點篩選，使得特征點更加顯著，效率更高，對于實時性繪圖精準度有所提升，能在較短時間內繪制出較高質量的圖像。

3 結 語

改進基于自適應閾值選取和局部搜索算法適應于場景比較復雜，圖像對比度多變的室外場景，在提高特征點精確度上相比原有OFAST算法提升了27.8%,在時效特征點提取算法相比原有OFAST算法提高了80.6%。改進后的ORB-SLAM可以廣泛應用于地理情景教學、戶外地形探索、建筑測繪領域。但改進后的OFAST算法雖然在特征點提取、平均時間響應、算法匹配正確率上有一定提升，但還未達到預期效果，未來將在粗提取方法進行進一步的優化。