基于自適應的AGAST 特征均勻化提取算法

張 猛， 唐清嶺， 蔣小菲

（貴州大學大數據與信息工程學院， 貴陽 550025）

0 引 言

即時定位與地圖構建（Simultaneous Localization and Mapping， SLAM）作為機器人領域的關鍵技術，通過傳感器即時地獲取環境特征，進而完成地圖構建和自身定位，是機器人領域的重點研究方向［1］。視覺SLAM 以相機作為傳感器，因其成本低，采集圖像信息豐富，成為當前的研究熱點。 其中，基于特征點法的視覺SLAM 系統的特征提取速度和均勻程度是后續位姿估計和地圖構建的重要影響因素［2］。

傳統的ORB 算法結合了FAST 角點和BRIEF描述子，具有計算速度快的優勢，被廣泛應用在SLAM 領域［1］，但算法提取的特征在圖像上分布不均勻，不利于后續的跟蹤和位姿估計。 Mur-Artal 等學者［3-4］提出了QORB 算法，利用四叉樹算法改善了傳統ORB 算法特征點提取不均勻的問題，但算法耗時有所增加。 Mair 等學者［5］對FAST 算法進行改進，提出了速度更快， 適應性更強的 AGAST（Adaptive and Generic Accelerated Segment Test）算法。 Tang 等學者［6］將AGAST 角點與BIREF 描述子結合，提出了OARB 算法，提高了特征點的提取速率，但特征點局部密集現象仍然存在。 王輝等學者［7］提出了一種改進的均勻化AGAST 特征提取算法，采用四叉樹算法均勻化提取特征點，但固定閾值的提取方式，提取大量冗余特征點，降低了特征點提取速率。 楊弘凡等學者［8］提出一種自適應閾值的提取方法，算法速度得到了提升，但仍需設定自適應參數，不是真正的閾值自適應。

基于以上分析，為了實現特征點的均勻提取，避免冗余點對位姿估計的影響，同時提高特征點提取速率，提出一種基于自適應的AGAST 特征均勻化提取算法。 首先，根據圖像灰度信息計算特征點的初始提取閾值，避免提取過多冗余點而降低計算效率；其次，構建圖像高斯金字塔，并在金字塔上提取得到多尺度的AGAST 特征點；然后，采用改進的四叉樹算法對特征點進行劃分和篩選，實現特征點的均勻分布；最后，用灰度質心法計算特征點的方向，實現特征點的旋轉不變性。

1 AGAST 算法介紹

AGAST 算法是FAST 算法的一種改進，在速度上得到了提升，且在復雜環境中有更好的魯棒性［9］。 本文提出的特征提取算法用AGAST 算法檢測角點。 FAST 特征提取如圖1 所示。 由圖1 可看到，與FAST 算法角點檢測判據一樣， 通過比較圓心像素“p”與Bresenham 圓上的16 個像素的灰度值進行判斷。 若有N個連續像素與像素“p”的灰度差的絕對值大于提取閾值，則像素“p”是一個角點。

為了使算法更快，首先將4 個像素（Bresenham圓上的1、5、9 和13）的灰度與“p”進行比較。 4 個像素中至少有3 個應該滿足閾值條件，才有可能判定為角點。 滿足此條件后，再對剩下的像素進行比較，當N≥12 時，則判定為角點。

AGAST 算法在FAST 算法的基礎上擴展了配置空間。 引入“不暗”與“不亮”的狀態對配置空間進行更詳細的描述。Sp→x為像素x對于像素p的狀態，像素狀態的分配可按式（1）進行計算：

其中，為前一個像素的狀態；Ip→x是像素x的灰度值；u表示該狀態仍然未知；t為特征點提取閾值。 原始配置空間被增加到了6N， 而616＝2×1012，所以將可能的節點N設置為16。 與FAST 算法一樣，閾值t越大，計算速度越快，檢測到的角點越準確，但角點數越少；閾值t越小，計算速度越慢，角點數越多。

FAST 采用的ID3 算法是一種貪婪算法，在尋找最優決策樹時表現很差，而AGAST 引入了后向歸納法，通過學習圖像的結構化區域和同質化區域，構建出的最優二叉決策樹如圖2 所示，在樹的末端根據葉節點的像素配置進行專用樹間的跳轉，進而將角點檢測問題轉換為二叉決策樹問題，并結合加速分割算法，提高特征提取效率。 此外，AGAST 算法在構建專用樹時，以離線的方式對葉節點進行評估，使得算法在決策樹間跳轉不需要額外的計算成本。

圖2 AGAST 算法示意圖Fig. 2 Schematic diagram of the adaptive and generic accelerated segment test

2 基于自適應的AGAST 特征均勻化提取

傳統視覺SLAM 算法采用FAST 算法對角點進行檢測。 因為AGAST 算法的速度在FAST 的基礎上得到了提升，但特征提取閾值仍依靠經驗設定，提取的特征點存在密集的現象。 本文提出了一種基于自適應的特征均勻化提取算法，首先，根據圖像灰度信息自適應計算提取閾值，提高算法在不同圖像上的適應性和提取效率；其次，構建圖像金子塔，并在每層金子塔上利用四叉樹算法均勻化提取具有尺度不變性的AGAST 特征點；然后，用灰度質心法計算特征點方向，并生成BRIEF 描述子，實現特征點的旋轉不變描述，為匹配提供支持。 算法結構如圖3 所示。

圖3 算法結構Fig. 3 Algorithm structure

2.1 自適應提取閾值

AGAST 角點與FAST 角點都是以提取像素與其周圍像素的灰度差作為特征檢測和提取的依據。 但無論是傳統提取算法、還是Mur-Artal 等學者［3］提出的提取算法的提取閾值均基于人工設定，每幀圖像的提取閾值相同，并沒有考慮圖像的灰度信息，提取效率降低。 若閾值設定較大，算法在紋理較弱和對比度較低的圖像上無法提取到足量的特征點［10］。因此為了在不同圖像上均能提取到足量特征點，通常傳統提取算法的提取閾值設定較低，而低閾值的提取方式雖能在不同圖像上提取到足量特征點，但對于紋理強和對比度高的圖像，算法會提取過多冗余特征點，降低了提取效率。

鑒于此，本文對特征點提取閾值進行改進，采用自適應的方式根據圖像灰度信息計算特征點提取閾值，在保證提取足量特征點的同時，避免以低閾值在高對比度和高紋理圖像上提取過多冗余點，從而提高算法的提取效率。 設計的自適應閾值計算方式見式（2）：

其中，iniTH為自適應計算所得的初始提取閾值；I（x） 表示第x個像素灰度值；為圖像上各像素灰度平均值；ni表示圖片像素總個數。 通過式（2）可以根據不同圖像信息計算出不同的提取閾值，使得算法有更好的適應性和計算效率。

2.2 構建圖像金字塔

AGAST 算法并不具備尺度不變性，這里通過對同一圖像采樣得到一組不同分辨率的圖像集合，構建高斯金字塔，在每層高斯金字塔上提取特征點，得到具有尺度不變性的特征點。 此處構建了8 層金子塔，同時為了在每層圖像上合理提取特征點，根據金字塔尺度因子計算得到每層圖像期望提取的特征點數。通過式（3）即可計算得到每層期望提取的特征點數：

其中，M為圖像需提取的特征點總數；s表示尺度因子；N表示第0 層期望提取的特征點數。

2.3 網格劃分提取特征點

為了均勻提取特征點，對每層圖像進行網格劃分，并在網格中提取特征點，從而保證在圖像各個區域都能提取到特征點。 根據輸入圖像分辨率，以30像素為邊長的正方形作為初始劃分依據，計算劃分后網格的行數與列數。 由此推得的公式見如下：

其中，R為求得的網格列數，width為圖像像素寬度。

此外，因為實際獲取的圖像為矩形，還需根據劃分后的網格行數與列數，計算得到實際網格像素高度和像素寬度。 如式（5）所示：

其中，w為劃分后的網格寬度；round（） 函數的作用是對結果取整。

網格劃分結束后，采用由式（2）計算得到的初始閾值iniTH對每個網格進行特征點檢測，提高特征點檢測效率。 若某網格內檢測不到特征點，則將閾值降低為iniTH/2，繼續檢測；若網格內還無法檢測到特征點，則采用最低閾值minTH＝7 檢測。 自適應閾值和最低閾值相結合，不僅提高了算法的提取效率，還保證了在每個網格中都能提取到特征點。

2.4 四叉樹均勻化篩選

通過網格劃分提取的特征點還存在局部聚集現象，這里采用四叉樹的方法對其篩選使得特征點均勻分布在圖像上。 此處四叉樹算法以原始圖像作為初始節點，并將初始節點劃分成4 個子節點得到初始四叉樹結構；接著計算每個子節點中的特征點數量，若大于1 則將此節點繼續劃分為4 個子節點，并刪除該節點；若等于1 則標記該節點并不再對其劃分。 如此重復直到被標記的節點數達到期望特征點數時，停止四叉樹劃分。

上述劃分步驟中沒有對四叉樹深度進行限制，造成四叉樹的過度分裂。 為了提高運行效率，這里根據每層金字塔圖像期望提取的特征點數計算最大劃分深度，從而限制四叉樹深度。 具體數學計算公式見式（6）：

其中，Di為四叉樹的最大劃分深度；i表示圖像金字塔的第i層；Ni為第i層圖像期望提取的特征點數；s為圖像金字塔的尺度因子。

2.5 特征點方向和描述

AGAST 算法與FAST 算法一樣，均無旋轉不變性，為了增加特征點在方向變化下的魯棒性，采用灰度質心法為每個由四叉樹均勻化篩選后的特征點計算方向。 計算步驟如下：

（1）以待計算方向的特征點為中心，選取圖像塊B，并計算出圖像塊的矩mpq，計算公式為：

其中，p和q表示圖像塊矩的階系數，I（x，y）為圖像中坐標是（x，y） 的像素灰度值。

（2）根據圖像塊B的各階矩，定義圖像塊的質心C，可推得：

其中，m10和m01為一階矩，m00為零階矩。

（3）連接圖像塊B的幾何中心O與質心C得到向量，向量朝向即為特征點的方向，定義特征點方向θ為：

通過上述步驟為特征點增加了方向信息，實現了旋轉不變性。

在對特征點計算方向以后，采用BRIEF 描述子［11］對特征點進行描述，方便后續的匹配。 BRIEF是一種由多個0 和1 組成的二進制向量。 其思想是在以特征點為中心選取的領域P內，按某種固定的模型選取n對點（n通常取256），通過比較每個點對的灰度值大小，使得該特征點生成了一個相對應的二進制字符串，將此二進制字符串作為特征點的描述子。 具體步驟如下：

（1）以特征點為中心，選取邊長為S的領域P（S通常取31） 。

（2）為了降低圖像噪聲對描述子的干擾，對領域P進行高斯濾波。

（3）在鄰域P內共選取n個點對N（x，y） ，并定義τ如下：

其中，p（x）、p（y） 分別為點x和點y處的像素灰度值，τ為描述子的值。

（4）選取n個點對后，根據式（10）計算每個點對的τ值，并將每個點對的τ值依次從最低位到最高位排列成一個二進制字符串，此二進制字符串即為特征點的描述子。

3 實驗結果與分析

為驗證本算法的優越性，使用傳統ORB 算法、QORB 算法以及本文提出的QOARB 算法，采用Mikolajczyk 等學者［12］創建的圖集中的4 組圖像對算法進行測試，依次對算法的特征提取速率、均勻化程度及匹配正確率進行比較。 測試圖集如圖4 所示。其中，Bikes 圖集是一組模糊程度不同的圖像，Leuven圖集是一組對比度不同的圖像，Ubc 圖集是一組壓縮程度不同的圖像，Graf 圖集是一組視角變換的圖像。為了避免實驗的隨機性，對所有實驗進行5 次測試，以平均值作為實驗結果。

圖4 測試圖集Fig. 4 Test image set

本實驗在Ubuntu18.04 操作系統，計算機CPU為Intel（R）Core（TM）i5-7200U CPU ＠ 2.50 GHz，12 GB 內存條件下完成。

3.1 提取速率實驗

為了核驗本算法在特征點提取速率上的提升，使用ORB 算法、QORB 算法、本文提出的QOARB 算法在Leuven、Graf、Ubc 和Bikes 四組圖集上進行特征提取，設置提取特征點數量為1 000 個。 用單點提取時間對特征點提取速率進行衡量。 不同算法在4 組圖像集上的特征提取實驗結果見表1。

表1 特征提取速率Tab. 1 Feature extraction rate

從表1 可以看出，在4 組對比實驗中，本文提出的QOARB 算法相較于未對特征點均勻化處理的ORB 算法在提取速率上有更長的計算時間，但提取速率優于QORB 算法。 這是因為QORB 算法與QOARB 算法均引入了四叉樹方法均勻管理特征點，增加了計算復雜度，但QOARB 算法根據圖像灰度自適應提取特征點，提取耗時明顯低于QORB 算法。

提取速率對比如圖5 所示，QOARB 算法與QORB 算法相比，在不同圖像組上的單點提取速率分別提高了6.80%、12.44%、14.70%、7.13%，平均提取速率提高10.65%。

圖5 提取速率對比Fig. 5 Extraction rate comparison

由以上實驗數據可以看出，本文提出的QOARB算法相較于QORB 算法，特征點提取速率更高，證明算法在特征點提取速率上的優勢。

3.2 均勻度實驗

為了量化均勻度，采用以下計算方法［13］：首先將圖片沿水平、豎直、左斜、右斜及中心與外圍五個方向，將圖像平均劃分為10 個區域；其次，根據每個區域內的特征點數量計算方差V；最后，根據評價函數公式（11）來計算均勻度u：

該數值越小，則劃分的各個區域中的特征點數目越接近，均勻程度越好。

對每個圖像組中的第一幅圖使用ORB 算法、QORB 算法和QOARB 進行均勻度對比實驗，如圖6所示。

圖6 特征提取結果Fig. 6 Feature extraction results

由圖6 可看出，QORB 算法與QOARB 算法提取的特征點均勻化效果明顯；傳統ORB 算法提取的特征點主要集中在圖像紋理密集的位置，出現了特征點局部聚集現象，均勻度差。

進一步對圖像均勻度進行量化統計，通過上述的特征點均勻度評價函數計算特征點在圖像上的均勻度，實驗結果見表2。

表2 特征點均勻度Tab. 2 Uniformity of feature points

由表2 分析可知，QORB 算法與QOARB 算法相較于傳統ORB 算法在特征的均勻度上有明顯的提高，QORB 算法與QOARB 算法在特征的均勻度上相差不大，平均相差約2.9%；相對于傳統ORB 算法，QORAB 算法均勻程度平均高16.4%。

3.3 特征匹配實驗

對圖像特征的提取是為了通過圖像的匹配完成位姿估計，因此匹配正確率（Correct Matching Rate，CMR）［14-15］也是衡量算法優越性的重要指標，匹配正確率計算公式如下：

其中，mc是由數據集中所包含的各個圖像間的變換矩陣計算得到的正確匹配個數，m為最近鄰與次近鄰距離算法篩選的匹配個數。CMR值越大，表示匹配效果越好。

本文對每個圖像組的圖片用ORB 算法、QORB算法及QOARB 算法進行匹配正確率測試，驗證本文提出的QOARB 算法在匹配正確率方面的有效性。 匹配效果見圖7 ，匹配正確率對比見表3。

表3 特征匹配正確率Tab. 3 Correct matching rate

圖7 部分匹配結果Fig. 7 Partial matching results

由圖7 和表3 可知，3 種算法在圖像集上的特征匹配正確率相差不大，QOARB 算法較ORB 算法提高約0.59%，較QORB 提高約1.01%。 ORB 算法的正確匹配數均高于QORB 算法和QOARB 算法，但是ORB 算法的匹配對聚集在紋理強的區域，特征匹配對冗余，不利于后期的位姿估計。 QOARB 算法與QORB 算法的匹配對均勻分布在圖像上，且本算法正確匹配數較QORB 算法提高約6%。

綜合以上實驗，本文提出的QOARB 算法提高了特征點的提取速率，實現了特征點的均勻化提取，同時在特征匹配上也具有優勢。

4 結束語

本文提出了一種基于自適應閾值的AGAST 特征均勻化提取算法，為了提升傳統視覺SLAM 算法的特征提取速率，改善特征點局部密集問題。 首先，根據圖像灰度信息自適應計算特征點提取閾值，并在生成的圖像金字塔上提取具有尺度不變性的AGAST 特征點；接著，采用限制深度的四叉樹算法將特征點均勻分布在圖像上；然后，計算特征點的方向并生成BRIEF 描述子。 在Mikolajczyk 等學者［12］的4 組特征對比實驗圖集上，對ORB 算法、QORB算法和本文提出的QOARB 算法進行了對比實驗，實驗結果表明：相較于傳統ORB 算法，QOARB 算法的特征點均勻度提高了16.4%；相較于QORB 算法，QOARB 算法特征點提取時間減少了10.65%，同時匹配正確率和正確匹配數分別提升1.01%和6%。證明了QOARB 算法具有一定優勢，可進一步應用到SLAM 算法中。