改進(jìn)的均勻化AGAST特征提取算法

王 輝，袁 杰

(新疆大學(xué)電氣工程學(xué)院，烏魯木齊 830000)

0 引言

同步定位與建圖(Simultaneous Localization and Mapping，SLAM)技術(shù)因無人駕駛、機(jī)器人等應(yīng)用而逐步走入大眾視野。作為機(jī)器人底層技術(shù)，通過傳感器對周圍環(huán)境信息進(jìn)行采集，并進(jìn)行實(shí)時定位與建圖，是當(dāng)前機(jī)器人研究領(lǐng)域的重要研究方向[1-2]。其中，采用視覺傳感器的視覺SLAM技術(shù)由于具有更低的成本及更好的普適性而成為當(dāng)前的研究熱點(diǎn)。基于特征點(diǎn)的視覺SLAM算法，特征點(diǎn)提取的均勻度和提取速率將直接影響SLAM位姿估計(jì)效果。

LOWE[3]提出了尺度不變特征變換(SIFT)算法，該算法具有尺度、旋轉(zhuǎn)、亮度不變性，具有較高的精度，但其計(jì)算量大、運(yùn)行時間長，不適合實(shí)時SLAM；BAY等[4]提出了加速魯棒特征(SURF)算法，該算法性能優(yōu)于SIFT算法并具有更快的速度，但仍需要較長時間構(gòu)建描述子，實(shí)時性較差，不具備構(gòu)建SLAM系統(tǒng)的條件；RUBLEE等[5]提出了定向FAST角點(diǎn)與旋轉(zhuǎn)BRIEF描述(Oriented FAST and Rotated BRIEF，ORB)算法，該算法基于加速段檢驗(yàn)特征(FAST)角點(diǎn)和rBRIEF(rotation-aware BRIEF)描述子，具有非?？斓挠?jì)算速度，并具備旋轉(zhuǎn)不變性及描述子，但該算法提取的特征點(diǎn)存在嚴(yán)重的局部密集現(xiàn)象，在相機(jī)發(fā)生高速移動的情況下，易發(fā)生跟蹤丟失；MUR-ARTAL等[6-7]提出了基于四叉樹的ORB特征均勻(QORB)算法，與傳統(tǒng)ORB算法相比,其主要優(yōu)勢在于提取的特征點(diǎn)更加均勻；MAIR等[8]提出了加速段檢驗(yàn)的自適應(yīng)通用角點(diǎn)檢測(Adaptive and Generic Accelerated Segment Test，AGAST)算法，該算法是對FAST算法的一種改進(jìn)，主要提升了速度與亮度變化下的魯棒性，但沒有解決尺度不變性；TANG等[9]提出的幾何關(guān)聯(lián)網(wǎng)絡(luò)2代(Geometric Correspondence Network v2，GCNv2)算法是一種基于深度學(xué)習(xí)的特征提取算法，實(shí)時性較高，但對硬件平臺有較高要求；柴江龍等[10]提出變尺度因子的改進(jìn)ORB算法，提高特征點(diǎn)提取效率，但未對特征點(diǎn)進(jìn)行均勻化，特征點(diǎn)較為集中；禹鑫燚等[11]提出改進(jìn)的ORB均勻化特征提取方法，采用四叉樹方法進(jìn)行特征點(diǎn)均勻化，但所用四叉樹結(jié)構(gòu)較為傳統(tǒng)，實(shí)時性較差。

基于以上分析，為了實(shí)現(xiàn)特征點(diǎn)提取的均勻化，改善特征點(diǎn)的局部聚集問題，避免冗余點(diǎn)對位姿估計(jì)的影響，同時具有較高的特征點(diǎn)提取速率，擁有更高的實(shí)時性，提出一種改進(jìn)的AGAST特征提取算法。通過對圖像構(gòu)建高斯金字塔，實(shí)現(xiàn)特征點(diǎn)尺度不變性，采用四叉樹方法對AGAST算法提取的特征點(diǎn)進(jìn)行管理，實(shí)現(xiàn)特征點(diǎn)在圖像上的均勻分布，根據(jù)期望特征點(diǎn)數(shù)限制每層金字塔相應(yīng)四叉樹深度，減少冗余特征點(diǎn)，提高整體運(yùn)行效率。

1 改進(jìn)的AGAST算法

AGAST算法屬于FAST角點(diǎn)檢測算法的一種改進(jìn)，具有更高的特征點(diǎn)提取速率和更好的場景適應(yīng)性。但同時，該算法并沒有實(shí)現(xiàn)尺度及旋轉(zhuǎn)不變性，同時不生成描述子，無法進(jìn)行特征點(diǎn)匹配。本文采用四叉樹方法實(shí)現(xiàn)對AGAST特征點(diǎn)的均勻化提取，通過對輸入圖像構(gòu)建圖像金字塔，在構(gòu)建的圖像金字塔上逐層提取特征點(diǎn)并進(jìn)行四叉樹管理；采用灰度質(zhì)心法對每個特征點(diǎn)計(jì)算方向，提供特征點(diǎn)的旋轉(zhuǎn)不變描述；對每個最終選定的特征點(diǎn)生成與該點(diǎn)匹配的Brief描述子，為特征匹配提供支持。

1.1 特征點(diǎn)提取

FAST特征檢測算法是當(dāng)前特征點(diǎn)視覺SLAM方法中提取效率較高的算法[12]。AGAST特征檢測算法是針對FAST的一種改進(jìn)算法，具有更快的速度，在復(fù)雜場景圖像中有更好的表現(xiàn)[13]。如圖1所示，F(xiàn)AST算法將像素“p”與bresenham圓上的16個像素點(diǎn)進(jìn)行比較，選擇周圍半徑為3。若在bresenham圓上的16個像素點(diǎn)中存在連續(xù)的Num個像素，其灰度值與p點(diǎn)灰度值差的絕對值不小于所設(shè)定的閾值t，則認(rèn)為該點(diǎn)為特征點(diǎn)，一般取Num=12。

圖1 特征點(diǎn)檢測Fig.1 Feature point detection

作為FAST算法的改進(jìn)，AGAST算法提供了一種更詳細(xì)的配置空間,它采用“非較亮”與“非較暗”對原配置空間進(jìn)行擴(kuò)展。采用以下概念：Sn→x表示n→x的像素對于核n的狀態(tài)，分配如下

(1)

AGAST算法通過在擴(kuò)展的結(jié)構(gòu)空間中尋找最優(yōu)決策樹，結(jié)合加速分割算法，提高了特征點(diǎn)提取速率，如圖2所示。其中：小圓圈為當(dāng)前特征提取區(qū)域的像素，不同顏色表示像素之間的差異，白色為差異最小，黑色為差異最大；線條表示計(jì)算過程中連接關(guān)系。

圖2 自適應(yīng)分割Fig.2 Adaptive segmentation

通過在滿二叉構(gòu)型的樹中尋找最優(yōu)樹的方法，根據(jù)當(dāng)前圖像信息進(jìn)行決策樹動態(tài)分配，提高提取效率，可以動態(tài)適應(yīng)場景。AGAST算法提取的特征點(diǎn)可重用性高、較為穩(wěn)定，有利于提高位姿估計(jì)精度。

1.2 四叉樹均勻化

AGAST算法依然是角點(diǎn)檢測算法，同F(xiàn)AST算法類似，其提取的特征點(diǎn)依然存在一定程度的局部密集情況，為了使所提取的特征點(diǎn)更加均勻地分布于整幅圖像上，為后續(xù)的匹配操作提供更好的數(shù)據(jù)支撐，本文選用四叉樹方法對特征點(diǎn)提取過程進(jìn)行均勻化操作。

通過對同一幅圖像提取不同的空間尺度信息，得到圖像局部和全局尺度上的一系列多分辨率圖像集合，構(gòu)建高斯金字塔，再對每一層進(jìn)行AGAST角點(diǎn)檢測，從而解決AGAST算法本身沒有尺度不變特性的問題。算法流程如圖3所示。

圖3 算法流程Fig.3 Flow chart of the algorithm

具體計(jì)算過程如下。

1)為了實(shí)現(xiàn)特征的尺度不變性，對輸入的圖像進(jìn)行高斯金字塔構(gòu)建，此處選取金字塔層數(shù)為8。

2)對圖像進(jìn)行初始結(jié)構(gòu)劃分，首先以邊長30像素的正方形作為初始劃分的依據(jù)，同時根據(jù)輸入圖像的實(shí)際分辨率，計(jì)算劃分后的行數(shù)與列數(shù)，即

c=w/30

(2)

式中：c為所求列數(shù);w為圖像橫向分辨率。由于實(shí)際視覺傳感器多為矩形，根據(jù)所得行數(shù)與列數(shù)分別計(jì)算網(wǎng)格的高和寬，即

W=round(w/c)

(3)

式中，W為劃分網(wǎng)格寬度。劃分后，遍歷所有網(wǎng)格進(jìn)行特征點(diǎn)提??；若在某一個網(wǎng)格中無法提取到特征點(diǎn)，則對起始閾值Tinit進(jìn)行降低，直到降低至預(yù)設(shè)的最低閾值Tmint。此處取Tinit=20，Tmint=10。

3)步驟2)中所獲取的特征點(diǎn)存在局部密集現(xiàn)象，這些點(diǎn)之間位置接近、描述相似，稱為冗余特征點(diǎn)。使用四叉樹方法對特征點(diǎn)進(jìn)行管理，獲取均勻化特征提取結(jié)果。

初始化節(jié)點(diǎn)O，將圖像分為4個區(qū)域，獲得初始四叉樹結(jié)構(gòu)，稱為4個子節(jié)點(diǎn)；對每個子節(jié)點(diǎn)內(nèi)的特征點(diǎn)數(shù)量進(jìn)行統(tǒng)計(jì)，若子節(jié)點(diǎn)內(nèi)特征點(diǎn)數(shù)量大于1，則對該子節(jié)點(diǎn)繼續(xù)進(jìn)行分割；若子節(jié)點(diǎn)內(nèi)特征點(diǎn)數(shù)量小于1，則對該子節(jié)點(diǎn)進(jìn)行保存，稱為父節(jié)點(diǎn)。對各子節(jié)點(diǎn)不斷分割，直到父節(jié)點(diǎn)數(shù)量達(dá)到所設(shè)定的預(yù)期特征點(diǎn)數(shù)量，則停止分割。如圖4所示。

圖4 四叉樹特征點(diǎn)管理Fig.4 Feature point management by quadtree

根據(jù)預(yù)期提取特征點(diǎn)數(shù)，由設(shè)定的金字塔層數(shù)和尺度因子可計(jì)算得到每層相應(yīng)的預(yù)期特征點(diǎn)數(shù)。通過預(yù)期特征點(diǎn)數(shù)，對四叉樹深度進(jìn)行限制，即

(4)

式中：Dl為四叉樹分割深度；l為第l層金字塔；F為預(yù)期特征點(diǎn)數(shù)；s為尺度因子。

通過對四叉樹深度進(jìn)行限制，避免了四叉樹過度分割，可降低冗余點(diǎn)的產(chǎn)生，提高運(yùn)行效率。

1.3 特征點(diǎn)方向及描述子計(jì)算

同F(xiàn)AST特征點(diǎn)相同，AGAST特征提取算法不具備旋轉(zhuǎn)不變性，為了解決這個問題，采用灰度質(zhì)心法對經(jīng)過篩選的特征點(diǎn)進(jìn)行角度計(jì)算，增加旋轉(zhuǎn)描述。

特征點(diǎn)方向計(jì)算過程如下。

1)選取特征點(diǎn)，以該點(diǎn)為中心的圖像塊B的矩mp q為

(5)

式中：pq為矩的階數(shù)的系數(shù)；x和y為圖像塊B中像素點(diǎn)坐標(biāo)；I(x,y)為此像素點(diǎn)(x,y)處的灰度值。

2)由該點(diǎn)的矩mp q可得到該點(diǎn)的質(zhì)心C的坐標(biāo)為

(6)

式中：m00為圖像塊0階矩；m01和m10分別為圖像塊關(guān)于x軸與y軸的1階矩。

(7)

通過以上步驟得到特征點(diǎn)方向，實(shí)現(xiàn)特征點(diǎn)的旋轉(zhuǎn)不變性。

為實(shí)現(xiàn)特征匹配，需要為特征點(diǎn)匹配相應(yīng)描述子，BRIEF描述子[14]的核心思想是對選定的某一個特征點(diǎn)，選取該特征點(diǎn)的鄰域P，在鄰域P內(nèi)選取n個點(diǎn)對，并對各點(diǎn)對之間的灰度值進(jìn)行比較，進(jìn)而轉(zhuǎn)化為二進(jìn)制字符串，每個特征點(diǎn)均有相對應(yīng)的二進(jìn)制字符串，即為此特征點(diǎn)的描述子。由于在構(gòu)造時只考慮到單個像素處的像素值，因此對噪聲較為敏感，使用數(shù)字平滑技術(shù)對圖像進(jìn)行處理。通過高斯濾波方法對鄰域P進(jìn)行處理，可降低噪聲干擾，提高描述子的穩(wěn)定性和可重復(fù)性。

1)選取的特征點(diǎn)為中心、大小為S×S的鄰域P(S取31);

2)對鄰域P進(jìn)行高斯濾波，取標(biāo)準(zhǔn)差σ1=2，窗口大小為9×9;

3)在鄰域P內(nèi)共選取n個點(diǎn)對N(x,y)，并定義τ為

(8)

式中,p(x)為x點(diǎn)的像素值大小，綜合性能及效果考慮，選取n=256;

4)在選取n對特征點(diǎn)之后，對選取的每個特征點(diǎn)進(jìn)行計(jì)算，將256個結(jié)果從最低位到最高位依次排列成字符串fnd(p)，即

(9)

最終得到一個256位的二進(jìn)制字符串，即為選定特征點(diǎn)的描述子。

根據(jù)特征點(diǎn)的描述子，選擇漢明距離作為度量，實(shí)現(xiàn)特征點(diǎn)初次匹配，獲得初始匹配集。對某特征點(diǎn)，選取與漢明距離最短的一個特征點(diǎn)形成匹配對，遍歷所有特征點(diǎn)，得到匹配對集合。

由于噪聲等干擾因素存在，獲取的粗匹配集中不可避免地存在一些錯誤匹配的情況。采用隨機(jī)一致性檢測(RANSAC)來剔除錯誤匹配對。對于一個包含錯誤數(shù)據(jù)的集合，RANSAC算法將其中的數(shù)據(jù)分為“內(nèi)點(diǎn)”與“外點(diǎn)”，通過估算該數(shù)據(jù)集合的數(shù)學(xué)模型，剔除其中的錯誤數(shù)據(jù)“外點(diǎn)”，保留“內(nèi)點(diǎn)”，實(shí)現(xiàn)數(shù)據(jù)集的優(yōu)化篩選。

2 實(shí)驗(yàn)分析

為驗(yàn)證采用四叉樹改進(jìn)的均勻化AGAST算法(QAGAST算法)的優(yōu)越性，使用AGAST,QORB特征提取算法，在Mikolajczyk特征檢測評估數(shù)據(jù)集下的4組圖像對算法進(jìn)行評估。分別對提取速率及特征點(diǎn)均勻化程度進(jìn)行比較，如圖5所示。

圖5 測試圖集Fig.5 Test atlas

本實(shí)驗(yàn)在Ubuntu 16.04操作系統(tǒng)，CPU i5-10600KF-4.1 GHz，32 GiB內(nèi)存條件下完成。

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

使用AGAST,QORB,QAGAST特征提取算法對Boat,Graf,Bikes,Trees 4組數(shù)據(jù)集圖像進(jìn)行特征提取，設(shè)定預(yù)期提取特征點(diǎn)數(shù)為1000。

使用每點(diǎn)提取耗時來對特征點(diǎn)提取速率進(jìn)行衡量，如表1所示。

表1 特征點(diǎn)提取耗時Table 1 Time cost of feature point extraction μs

從表1可以看出，在4組對比實(shí)驗(yàn)中，改進(jìn)后的QAGAST算法提取相較于未進(jìn)行均勻化處理及方向、描述子計(jì)算的AGAST算法需要更長的計(jì)算時間，但提取速率優(yōu)于QORB算法。

將QAGAST算法與QORB算法的5組實(shí)驗(yàn)數(shù)據(jù)進(jìn)行繪制得到如圖6所示提取耗時對比情況，圖中，縱坐標(biāo)為算法提取單個特征點(diǎn)的平均耗時。

圖6 提取耗時對比Fig.6 Comparison of extraction time cost

如圖6所示，在4組圖像中，QAGAST算法相比于QORB算法，每個特征點(diǎn)提取速率分別快24.01%，4.27%，10.10%，9%，平均提取速率提高12.31%。

由上述實(shí)驗(yàn)可以看出，相較于QORB算法，改進(jìn)后的QAGAST算法具有更高的特征點(diǎn)提取速率，證明其高效性。

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

(10)

式中，L為均勻度指數(shù),該數(shù)值越低，則表示均勻度越好。

使用上述4個圖像測試組分別對AGAST算法、QORB算法、QAGAST算法進(jìn)行均勻度對比實(shí)驗(yàn)，如圖7所示。

圖7 均勻度對比實(shí)驗(yàn)Fig.7 Homogenization comparison experiment

統(tǒng)計(jì)圖像數(shù)據(jù)，并使用均勻度評價(jià)函數(shù)進(jìn)行計(jì)算，得到如表2所示均勻度指數(shù)。

表2 均勻度指數(shù)Table 2 Homogenization index

通過實(shí)驗(yàn)數(shù)據(jù)可以看出，采用了改進(jìn)四叉樹均勻化處理的QAGAST算法，在特征點(diǎn)提取均勻度上較未改進(jìn)的AGAST算法提升47.12%，較傳統(tǒng)四叉樹算法的QORB算法提升7.8%。

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

傳統(tǒng)特征點(diǎn)提取算法僅采用漢明距離進(jìn)行特征匹配，存在較多誤匹配情況，較多的匹配對數(shù)量也會對算法效率造成影響。為了實(shí)現(xiàn)更精確的特征匹配，采用RANSAC算法對特征匹配進(jìn)行篩選，可以有效剔除錯誤匹配對，保留正確匹配對，降低在SLAM位姿估計(jì)時的誤差。通過使用QAGAST算法、QORB算法及AGAST算法對Boat圖像進(jìn)行特征匹配實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 特征匹配實(shí)驗(yàn)Fig.8 Feature matching experiment

通過RANSAC算法實(shí)現(xiàn)了對特征匹配對的篩選，獲得了準(zhǔn)確度較高的匹配對集合。

3 結(jié)束語

本文針對特征點(diǎn)提取中存在的特征點(diǎn)局部密集問題，提出了一種改進(jìn)的AGAST特征提取算法。通過對AGAST算法進(jìn)行高斯金字塔構(gòu)建，實(shí)現(xiàn)特征點(diǎn)的尺度不變性；使用四叉樹方法對特征點(diǎn)進(jìn)行管理，實(shí)現(xiàn)了均勻度較高的特征點(diǎn)分布；根據(jù)不同預(yù)期特征點(diǎn)數(shù)和金字塔層數(shù)，對四叉樹深度進(jìn)行限制，減少了冗余點(diǎn)，提高了提取效率。通過與QORB算法進(jìn)行實(shí)驗(yàn)對比，結(jié)果表明，QAGAST算法特征點(diǎn)提取速率提高12.31%、均勻度提高了7.8%。采用RANSAC算法有效剔除了錯誤匹配，獲取精確匹配集。實(shí)驗(yàn)數(shù)據(jù)表明所提算法具有一定的優(yōu)越性。