基于自適應(yīng)的AGAST 特征均勻化提取算法

張 猛， 唐清嶺， 蔣小菲

（貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院， 貴陽 550025）

0 引 言

即時(shí)定位與地圖構(gòu)建（Simultaneous Localization and Mapping， SLAM）作為機(jī)器人領(lǐng)域的關(guān)鍵技術(shù)，通過傳感器即時(shí)地獲取環(huán)境特征，進(jìn)而完成地圖構(gòu)建和自身定位，是機(jī)器人領(lǐng)域的重點(diǎn)研究方向［1］。視覺SLAM 以相機(jī)作為傳感器，因其成本低，采集圖像信息豐富，成為當(dāng)前的研究熱點(diǎn)。 其中，基于特征點(diǎn)法的視覺SLAM 系統(tǒng)的特征提取速度和均勻程度是后續(xù)位姿估計(jì)和地圖構(gòu)建的重要影響因素［2］。

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

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

1 AGAST 算法介紹

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

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

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

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

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

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

2 基于自適應(yīng)的AGAST 特征均勻化提取

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

圖3 算法結(jié)構(gòu)Fig. 3 Algorithm structure

2.1 自適應(yīng)提取閾值

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

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

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

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

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

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

2.3 網(wǎng)格劃分提取特征點(diǎn)

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

其中，R為求得的網(wǎng)格列數(shù)，width為圖像像素寬度。

此外，因?yàn)閷?shí)際獲取的圖像為矩形，還需根據(jù)劃分后的網(wǎng)格行數(shù)與列數(shù)，計(jì)算得到實(shí)際網(wǎng)格像素高度和像素寬度。 如式（5）所示：

其中，w為劃分后的網(wǎng)格寬度；round（） 函數(shù)的作用是對(duì)結(jié)果取整。

網(wǎng)格劃分結(jié)束后，采用由式（2）計(jì)算得到的初始閾值iniTH對(duì)每個(gè)網(wǎng)格進(jìn)行特征點(diǎn)檢測，提高特征點(diǎn)檢測效率。 若某網(wǎng)格內(nèi)檢測不到特征點(diǎn)，則將閾值降低為iniTH/2，繼續(xù)檢測；若網(wǎng)格內(nèi)還無法檢測到特征點(diǎn)，則采用最低閾值minTH＝7 檢測。 自適應(yīng)閾值和最低閾值相結(jié)合，不僅提高了算法的提取效率，還保證了在每個(gè)網(wǎng)格中都能提取到特征點(diǎn)。

2.4 四叉樹均勻化篩選

通過網(wǎng)格劃分提取的特征點(diǎn)還存在局部聚集現(xiàn)象，這里采用四叉樹的方法對(duì)其篩選使得特征點(diǎn)均勻分布在圖像上。 此處四叉樹算法以原始圖像作為初始節(jié)點(diǎn)，并將初始節(jié)點(diǎn)劃分成4 個(gè)子節(jié)點(diǎn)得到初始四叉樹結(jié)構(gòu)；接著計(jì)算每個(gè)子節(jié)點(diǎn)中的特征點(diǎn)數(shù)量，若大于1 則將此節(jié)點(diǎn)繼續(xù)劃分為4 個(gè)子節(jié)點(diǎn)，并刪除該節(jié)點(diǎn)；若等于1 則標(biāo)記該節(jié)點(diǎn)并不再對(duì)其劃分。 如此重復(fù)直到被標(biāo)記的節(jié)點(diǎn)數(shù)達(dá)到期望特征點(diǎn)數(shù)時(shí)，停止四叉樹劃分。

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

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

2.5 特征點(diǎn)方向和描述

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

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

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

（2）根據(jù)圖像塊B的各階矩，定義圖像塊的質(zhì)心C，可推得：

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

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

通過上述步驟為特征點(diǎn)增加了方向信息，實(shí)現(xiàn)了旋轉(zhuǎn)不變性。

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

（1）以特征點(diǎn)為中心，選取邊長為S的領(lǐng)域P（S通常取31） 。

（2）為了降低圖像噪聲對(duì)描述子的干擾，對(duì)領(lǐng)域P進(jìn)行高斯濾波。

（3）在鄰域P內(nèi)共選取n個(gè)點(diǎn)對(duì)N（x，y） ，并定義τ如下：

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

本實(shí)驗(yàn)在Ubuntu18.04 操作系統(tǒng)，計(jì)算機(jī)CPU為Intel（R）Core（TM）i5-7200U CPU ＠ 2.50 GHz，12 GB 內(nèi)存條件下完成。

3.1 提取速率實(shí)驗(yàn)

為了核驗(yàn)本算法在特征點(diǎn)提取速率上的提升，使用ORB 算法、QORB 算法、本文提出的QOARB 算法在Leuven、Graf、Ubc 和Bikes 四組圖集上進(jìn)行特征提取，設(shè)置提取特征點(diǎn)數(shù)量為1 000 個(gè)。 用單點(diǎn)提取時(shí)間對(duì)特征點(diǎn)提取速率進(jìn)行衡量。 不同算法在4 組圖像集上的特征提取實(shí)驗(yàn)結(jié)果見表1。

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

從表1 可以看出，在4 組對(duì)比實(shí)驗(yàn)中，本文提出的QOARB 算法相較于未對(duì)特征點(diǎn)均勻化處理的ORB 算法在提取速率上有更長的計(jì)算時(shí)間，但提取速率優(yōu)于QORB 算法。 這是因?yàn)镼ORB 算法與QOARB 算法均引入了四叉樹方法均勻管理特征點(diǎn)，增加了計(jì)算復(fù)雜度，但QOARB 算法根據(jù)圖像灰度自適應(yīng)提取特征點(diǎn)，提取耗時(shí)明顯低于QORB 算法。

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

圖5 提取速率對(duì)比Fig. 5 Extraction rate comparison

由以上實(shí)驗(yàn)數(shù)據(jù)可以看出，本文提出的QOARB算法相較于QORB 算法，特征點(diǎn)提取速率更高，證明算法在特征點(diǎn)提取速率上的優(yōu)勢。

3.2 均勻度實(shí)驗(yàn)

為了量化均勻度，采用以下計(jì)算方法［13］：首先將圖片沿水平、豎直、左斜、右斜及中心與外圍五個(gè)方向，將圖像平均劃分為10 個(gè)區(qū)域；其次，根據(jù)每個(gè)區(qū)域內(nèi)的特征點(diǎn)數(shù)量計(jì)算方差V；最后，根據(jù)評(píng)價(jià)函數(shù)公式（11）來計(jì)算均勻度u：

該數(shù)值越小，則劃分的各個(gè)區(qū)域中的特征點(diǎn)數(shù)目越接近，均勻程度越好。

對(duì)每個(gè)圖像組中的第一幅圖使用ORB 算法、QORB 算法和QOARB 進(jìn)行均勻度對(duì)比實(shí)驗(yàn)，如圖6所示。

圖6 特征提取結(jié)果Fig. 6 Feature extraction results

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

進(jìn)一步對(duì)圖像均勻度進(jìn)行量化統(tǒng)計(jì)，通過上述的特征點(diǎn)均勻度評(píng)價(jià)函數(shù)計(jì)算特征點(diǎn)在圖像上的均勻度，實(shí)驗(yàn)結(jié)果見表2。

表2 特征點(diǎn)均勻度Tab. 2 Uniformity of feature points

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

3.3 特征匹配實(shí)驗(yàn)

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

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

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

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

圖7 部分匹配結(jié)果Fig. 7 Partial matching results

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

綜合以上實(shí)驗(yàn)，本文提出的QOARB 算法提高了特征點(diǎn)的提取速率，實(shí)現(xiàn)了特征點(diǎn)的均勻化提取，同時(shí)在特征匹配上也具有優(yōu)勢。

4 結(jié)束語

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