鄭泰皓 方子彬

摘要：為了使機(jī)器人在陌生環(huán)境中能夠通過(guò)傳感器對(duì)環(huán)境進(jìn)行探測(cè)，并在對(duì)自身定位的同時(shí)得到周圍環(huán)境的三維重建地圖，視覺(jué)SLAM（Simultaneous Localization and Mapping），即時(shí)定位與地圖構(gòu)建應(yīng)運(yùn)而生。文章對(duì)視覺(jué)SLAM方法與特征匹配SIFT算法進(jìn)行了論述與提取效率分析。SIFT算法包含大量單指令多數(shù)據(jù)流模式的密集型計(jì)算，使用CPU+GPU混合異構(gòu)加速平臺(tái)在理論上能有效提高其執(zhí)行性能。通過(guò)對(duì)國(guó)內(nèi)外學(xué)者在GPU并行加速領(lǐng)域研究成果的分析，針

GPU加速SIFT算法展開(kāi)了分析與展望。

關(guān)鍵詞：視覺(jué)SLAM;自身定位;特征匹配;SIFT算法;GPU加速

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8228（2020）07-16-06

0引言

SLAM（Simultaneous Localization and Mapping）系統(tǒng)指的是在給定的環(huán)境中利用傳感器進(jìn)行探測(cè)，基本任務(wù)是確定自身的位置同時(shí)繪制環(huán)境地圖，也叫做“同時(shí)定位與地圖創(chuàng)建”系統(tǒng)。SLAM技術(shù)通常是指將攜帶相機(jī)傳感器的移動(dòng)機(jī)器人放置在一個(gè)未曾探索過(guò)的給定的一個(gè)環(huán)境中，利用其傳感器的特性，捕獲周圍環(huán)境圖像信息，從而對(duì)周圍環(huán)境進(jìn)行觀測(cè)感知，目的是為了確定當(dāng)前系統(tǒng)的位姿和運(yùn)動(dòng)過(guò)程產(chǎn)生的軌跡，來(lái)進(jìn)行自身的定位導(dǎo)航，并同時(shí)構(gòu)建出增量式地圖的一種技術(shù)，最常用在移動(dòng)機(jī)器人領(lǐng)域。

相機(jī)傳感器有著小巧的體積、低廉的成本和大幅縮小的重量，存儲(chǔ)的圖像信息同時(shí)也更為豐富，所以以相機(jī)作為外部傳感器的SLAM得到了快速的發(fā)展，這樣的SLAM被稱為視覺(jué)SLAM。而SIFT（scaleInvariant Feature Transform）算法也稱作尺度不變特征變換算法，是視覺(jué)SLAM中最基礎(chǔ)最經(jīng)典也是最重要的算法。

通過(guò)對(duì)SIFT算法進(jìn)行優(yōu)化，可以進(jìn)一步對(duì)視覺(jué)SLAM算法進(jìn)行加速。

1相關(guān)研究

1.1SLAM系統(tǒng)介紹

SLAM技術(shù)的關(guān)鍵問(wèn)題是要通過(guò)傳感器對(duì)環(huán)境進(jìn)行感知預(yù)測(cè)，了解到機(jī)器人準(zhǔn)確的位置和運(yùn)動(dòng)軌跡，從而才能構(gòu)建出準(zhǔn)確的環(huán)境地圖，而這些問(wèn)題的前提是要知道其所處位置的準(zhǔn)確地圖環(huán)境。

在機(jī)器人定位導(dǎo)航的過(guò)程中，最關(guān)鍵的三個(gè)方面分別是定位，建圖和路徑規(guī)劃，其中定位與建圖相互關(guān)聯(lián)與依賴。Durrant-Whyte和Baileyt全面回顧了SLAM技術(shù)的在1986年到2004年“經(jīng)典時(shí)期”的發(fā)展歷史，見(jiàn)證了該技術(shù)朝工業(yè)方向的轉(zhuǎn)變。

1.2 SLAM系統(tǒng)流程

到目前為止，有大量的國(guó)內(nèi)外研究學(xué)者對(duì)于開(kāi)源SLAM算法進(jìn)行了深入的研究，內(nèi)容包括但不限于特征檢測(cè)與特征匹配、閉環(huán)檢測(cè)、邊緣檢測(cè)與優(yōu)化、大規(guī)模環(huán)境場(chǎng)景等等關(guān)鍵技術(shù)。

實(shí)際上，整個(gè)視覺(jué)SLAM流程包括以下步驟。

（1）讀取傳感器圖像信息：機(jī)器人主要以相機(jī)作為外部傳感器，采集到的信息內(nèi)容主要是圖像，對(duì)這些信息進(jìn)行讀取同時(shí)做預(yù)處理操作。

（2）視覺(jué)里程計(jì)（VisualOdometry）：僅通過(guò)視覺(jué)輸入引起的圖像變化來(lái)估計(jì)相機(jī)運(yùn)動(dòng)，從而確定機(jī)器人的位置和姿態(tài)，是SLAM系統(tǒng)的構(gòu)建模塊。方法通常是利用ORB（Oriented FAST and Rotated BRIEF）算法來(lái)檢測(cè)與匹配特征。

（3）后端優(yōu)化（Optimization）：后端考慮不同時(shí)刻的軌跡與地圖準(zhǔn)確率問(wèn)題，會(huì)接收并使用一段時(shí)間內(nèi)的視覺(jué)里程計(jì)來(lái)更新相機(jī)位置與姿態(tài)以及避免回環(huán)檢測(cè)的問(wèn)題，從而進(jìn)行優(yōu)化，得到更加準(zhǔn)確的移動(dòng)路徑與地圖。

（4）回環(huán)檢測(cè)（LoopClosing）：在機(jī)器人進(jìn)行定位與繪圖的過(guò)程中，相機(jī)傳感器根據(jù)機(jī)器人的運(yùn)動(dòng)軌跡記錄下圖像信息。對(duì)這些軌跡圖像進(jìn)行計(jì)算比較，若相似度超過(guò)某一閾值，則認(rèn)為出現(xiàn)回環(huán)。即檢測(cè)機(jī)器人是否進(jìn)入同一地點(diǎn)。

（5）建圖（Mapping）：建立地圖。機(jī)器人感知信息規(guī)劃路線，通過(guò)預(yù)估的軌跡，構(gòu)建對(duì)應(yīng)任務(wù)的地圖。

整個(gè)過(guò)程如圖1所示。

1.3 SLAM系統(tǒng)的應(yīng)用

近二十年來(lái)SLAM方法在智能機(jī)器人領(lǐng)域無(wú)論是從基礎(chǔ)理論上，還是在應(yīng)用實(shí)例上，都已經(jīng)取得了極大的成功和突破，建立了一些穩(wěn)定實(shí)用的SLAM方法，并能很好地適用于各種不同的環(huán)境。例如，室內(nèi)環(huán)境（groundindoor）、室外（groundoutdoor）、空間（air-borne）和水下（underwater）等。

傳統(tǒng)的單目視覺(jué)SLAM則是借助于擴(kuò)展卡爾曼濾波器來(lái)實(shí)現(xiàn)軌跡規(guī)劃與定位繪圖的。在移動(dòng)機(jī)器人領(lǐng)域中，SLAM方法應(yīng)用越來(lái)越廣泛，算法越來(lái)越強(qiáng)大，其中便有經(jīng)典的期望最大化（ExpectationMaximi-zation，EM）算法。

傳統(tǒng)的算法計(jì)算量大，復(fù)雜度高，一直到2000年，對(duì)SLAM方法的研究重點(diǎn)逐漸從傳統(tǒng)的聲吶、激光等測(cè)距傳感器發(fā)展到視覺(jué)傳感器。視覺(jué)傳感器也逐漸有了專有名詞——VisualSLAM。視覺(jué)傳感器有著測(cè)距傳感器不可比擬的優(yōu)點(diǎn)，最大的特點(diǎn)即是低成本高作用，不僅提高了探測(cè)范圍，還擁有更好的環(huán)境適應(yīng)能力。

微軟研發(fā)出Kinect相機(jī)的原理是提取彩色圖像中具有深度信息的SIFT特征，用特定的方法計(jì)算出3D特征點(diǎn)的匹配信息，并結(jié)合ICP（Iterative ClosestPoint）算法進(jìn)行位姿的估計(jì)與優(yōu)化。

ICP算法基本流程如圖2所示。

相比于其他傳統(tǒng)的特征提取算法，SIFT算法的精確度高，對(duì)于噪聲或者其他不利因素的魯棒性也比較強(qiáng)。因此，通常會(huì)用SIFT算法作為視覺(jué)SLAM系統(tǒng)中的特征提取算法。

2SlFT算法原理

由于SIFT算法能夠提取局部特征，所以它的實(shí)質(zhì)便是在不同的尺度空間檢測(cè)這些局部特征點(diǎn)作為關(guān)鍵點(diǎn)，并且這些關(guān)鍵點(diǎn)為不會(huì)因光照、噪聲、雜物、旋轉(zhuǎn)等外界因素而受到影響的點(diǎn)，然后計(jì)算出這些關(guān)鍵點(diǎn)的特征方向和特征向量，從而建立圖像中點(diǎn)的對(duì)應(yīng)關(guān)系。

下面對(duì)SIFT算法具體步驟及其原理進(jìn)行簡(jiǎn)單的介紹。

2.1構(gòu)造DOG金字塔

首先需要構(gòu)造DOG（Difference of Gaussian）金字塔，中文全稱為高斯差分金字塔。要構(gòu)造DOG金字塔，需要以下幾步：

（1）構(gòu)造高斯金字塔

二維空間高斯函數(shù)為：

可以看出G（x，y，σ）是正態(tài)分布，將式（1）進(jìn)行化簡(jiǎn)計(jì)算，得到它的均值和方差分別為0和σ。對(duì)于二維圖像I（x，y），如公式（2）所示，利用高斯函數(shù)與圖像進(jìn)行卷積，得到其在不同尺度下的尺度空間表示。其中，L與σ與圖像平滑程度正相關(guān)，它們分別表示尺度空間與尺度因子。利用式（1）、式（2），建立高斯金字塔，得到高斯金字塔示意圖，如圖3所示。

其中，k為固定系數(shù)。由式（3）可知，計(jì)算要得到的函數(shù)差，便要對(duì)相鄰兩組尺度空間分別進(jìn)行高斯卷積，然后將得到的結(jié)果做減法運(yùn)算。

2.2DOG極值點(diǎn)檢測(cè)及篩選

在高斯金字塔中一共生成若干組和若干層不同尺度的圖像，這些不同的層和組就構(gòu)成了高斯金字塔的尺度空間。在該尺度空間中間層的基礎(chǔ)上除去上下兩層而只取中間層，在中間層選取某一點(diǎn)作為待檢測(cè)點(diǎn)，分別與上下層像素點(diǎn)與該點(diǎn)周圍的8個(gè)像素點(diǎn)進(jìn)行一一計(jì)算比較，記錄下該局部極值點(diǎn)的位置及其對(duì)應(yīng)尺度。然后通過(guò)SIFT算法泰勒展開(kāi)DOG函數(shù)，便可得到極值點(diǎn)的位置和維數(shù)。

將空間函數(shù)D（x，y，σ）在局部極值點(diǎn)（xo，yo，σ）處進(jìn)行泰勒展開(kāi)，得到泰勒展開(kāi)式，如公式（4）。

由此可得此展開(kāi)式的導(dǎo)數(shù)，并令其為0，得到精確的極值點(diǎn)位置Xmax。將Xmax帶入公式（4），只取前兩項(xiàng)，可得到公式（5）。

2.3生成SIFT特征向量

生成SIFT特征向量的第—步是確定特征點(diǎn)主方向，根據(jù)公式（6）可分別得到特征點(diǎn)的梯度值與梯度方向。

在得到特征點(diǎn)的梯度值與主方向后，以特征點(diǎn)為中心去除掉其所在的行與列，并選取一個(gè)8×8大窗口。將這個(gè)大窗口劃分為4個(gè)規(guī)模為4×4的小窗口，為每個(gè)小窗口計(jì)算8個(gè)方向的梯度方向直方圖，對(duì)得到的直方圖進(jìn)行分析，并將每個(gè)方向相對(duì)應(yīng)的幅值加起來(lái)以形成關(guān)鍵點(diǎn)。分配給關(guān)鍵點(diǎn)的方向并不直接是關(guān)鍵點(diǎn)的梯度方向，而是按照一種梯度方向直方圖的方式給出的。將這些樣本累積在方向直方圖中，每個(gè)箭頭對(duì)應(yīng)了每個(gè)方向，同時(shí)它在直方圖中的長(zhǎng)度對(duì)應(yīng)于小窗口內(nèi)該方向附近的梯度幅度之和。

由上述可知，每個(gè)小窗口對(duì)應(yīng)一個(gè)關(guān)鍵點(diǎn)，每個(gè)關(guān)鍵點(diǎn)具有8個(gè)方向矢量信息，這些信息可以生成4×4×8=128個(gè)元素的SIFT特征矢量。由于SIFT本身的特性，并且在選取特征點(diǎn)時(shí)特意選擇了受光照、縮放、噪聲影響較小的點(diǎn)作為關(guān)鍵點(diǎn)，因此此時(shí)的SIFT特征向量受外界幾何因素干擾較小，可以很好地描述圖像的特征。

3SIFT算法的GPU加速研究

SIFT算法功能強(qiáng)大，同時(shí)也伴有較高的算法復(fù)雜度和計(jì)算時(shí)間，無(wú)法滿足于一些實(shí)時(shí)需求，這使得加速圖像處理的過(guò)程成為學(xué)者們研究探討的熱點(diǎn)。而隨著技術(shù)的不斷突破，圖像處理領(lǐng)域強(qiáng)大的圖形處理器GPU（Graphics Processing Unit）技術(shù)的成熟，這一切都將成為可能。GPU的主要是對(duì)圖像信息進(jìn)行構(gòu)建和渲染，在浮點(diǎn)運(yùn)算與并行運(yùn)算方面，它的速度遠(yuǎn)遠(yuǎn)超過(guò)CPU。由于其高速運(yùn)算能力與強(qiáng)大并行計(jì)算能力，而受到了圖像處理領(lǐng)域的青睞。

針對(duì)SIFT特征提取的計(jì)算效率，國(guó)內(nèi)外許多學(xué)者進(jìn)行了大量研究。將GPU技術(shù)與多核CPU應(yīng)用于SIFT算法在近幾年來(lái)的熱度逐漸提升。Sinha等人在基于OpenGL和cg語(yǔ)言的NVIDIA 7900GTX顯卡上通過(guò)GPU并行操作實(shí)現(xiàn)了SIFT功能，但是由于當(dāng)時(shí)的硬件和軟件條件，一些步驟在GPU上并未執(zhí)行，從而導(dǎo)致大量數(shù)據(jù)傳輸在GPU和CPU之間轉(zhuǎn)換，花費(fèi)了大量時(shí)間。

SIFT算法包含了大量的單指令多數(shù)據(jù)流SIMD（Single Instruction Multiple Data）模式的計(jì)算，使用CPU+GPU混合架構(gòu)在理論上能減少重復(fù)運(yùn)算的運(yùn)行時(shí)間。下面通過(guò)引用的一些實(shí)驗(yàn)數(shù)據(jù)對(duì)SIFT算法的GPU加速進(jìn)行討論。

Zhang等在Intel 8核CPU上實(shí)現(xiàn)了SIFT算法，達(dá)到了6.4倍的性能加速效果，并對(duì)算法的可擴(kuò)展性進(jìn)行了詳細(xì)的分析和實(shí)驗(yàn)。

Feng等人在16核CPU和64核模擬器上實(shí)現(xiàn)了11倍的加速。事實(shí)上除了并行優(yōu)化外，其中還還包括達(dá)到2倍速度提升的局部串行優(yōu)化。

Warn等人在混合機(jī)群上，運(yùn)用多核CPU與GPU進(jìn)行了實(shí)驗(yàn)。結(jié)果表明，在8核處理器上只達(dá)到了2倍的加速，而GPU版本卻加速了13倍。

王蓓蕾等人基于CUDA編程模型實(shí)現(xiàn)了SIFT算法的GPU加速。并通過(guò)合理計(jì)算，利用CPU+GPU混合異構(gòu)來(lái)優(yōu)化算法。實(shí)驗(yàn)結(jié)果如表1所示（ms表示單位為毫秒）。

王化喆等人通過(guò)CPU+GPU混合異構(gòu)模式，對(duì)遙感圖像配準(zhǔn)的SIFT算法進(jìn)行了優(yōu)化。通過(guò)負(fù)載均衡計(jì)算，把大量的重復(fù)性計(jì)算放到GPU上進(jìn)行運(yùn)算，CPU上進(jìn)行邏輯判斷等運(yùn)算。實(shí)驗(yàn)采用了一幅6000×6000的遙感圖像，對(duì)SIFT算法的各個(gè)步驟分別進(jìn)行CPU以及CPU+GPU的運(yùn)行時(shí)間對(duì)比，實(shí)驗(yàn)結(jié)果如表2所示（ms表示單位為毫秒）。

實(shí)驗(yàn)結(jié)果表明，主方向模值梯度計(jì)算的加速比達(dá)到了10，遠(yuǎn)超過(guò)其他實(shí)驗(yàn)項(xiàng)目，所以它的并行效果最好。

付波等在GPU為NVIDIAGeForceGTX550Ti，顯存為1GB的環(huán)境下，得到了如表3的實(shí)驗(yàn)結(jié)果（ms表示單位為毫秒）。

可以看出，SIFT算法對(duì)于有不同分辨率的圖像處理速度也不同，而GPU優(yōu)化之后的SIFT算法效率明顯高于串行SIFT算法。不僅如此，在特征描述子的性能計(jì)算上，也得出了相應(yīng)的結(jié)果，實(shí)驗(yàn)結(jié)果如表4（ms表示單位為毫秒）。

分析可知，對(duì)于SIFT算法無(wú)論是在特征點(diǎn)計(jì)算性能、極值點(diǎn)檢測(cè)、主方向模值梯度計(jì)算，還是在尺度空間和差分尺度空間計(jì)算性能、特征描述子計(jì)算性能上，GPU加速都達(dá)到了很好的加速效果。采用GPU加速適合并行的部分，會(huì)對(duì)算法整體產(chǎn)生優(yōu)化效果。

這也證明了GPU加速SIFT算法是可行和有效的。未來(lái)，GPU優(yōu)化加速可以應(yīng)用到更多的算法以及應(yīng)用領(lǐng)域中。

4結(jié)束語(yǔ)

通過(guò)以上對(duì)基于特征的視覺(jué)SLAM方法及其一種特征提取算法SIFT的介紹，以及引用的論文中對(duì)SWT算法的GPU并行優(yōu)化實(shí)驗(yàn)結(jié)果分析，可以得出如下結(jié)論：

（1）視覺(jué)SLAM算法可以通過(guò)引.）kGPU來(lái)進(jìn)行并行優(yōu)化;

（2）合理考慮負(fù)載均衡問(wèn)題，采用CPU+GPU混合異構(gòu)系統(tǒng)能夠在一定程度上提高視覺(jué)SLAM算法的實(shí)時(shí)性;

（3）視覺(jué)SLAM算法關(guān)鍵幀的合理選取，特征檢測(cè)及匹配算法的選取，以及算法并行與串行部分所占的比重都會(huì)影響到整體的優(yōu)化效果。

綜上所述，對(duì)視覺(jué)SLAM算法進(jìn)行優(yōu)化時(shí)需考慮多方面的因素，特別是當(dāng)GPU存儲(chǔ)及計(jì)算資源不足時(shí)的負(fù)載均衡問(wèn)題，以及程序的并行粒度計(jì)算，都是值得研究的問(wèn)題。