鄭泰皓 方子彬

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

GPU加速SIFT算法展開了分析與展望。

關鍵詞：視覺SLAM;自身定位;特征匹配;SIFT算法;GPU加速

中圖分類號：TP391 文獻標識碼：A 文章編號：1006-8228（2020）07-16-06

0引言

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

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

通過對SIFT算法進行優(yōu)化，可以進一步對視覺SLAM算法進行加速。

1相關研究

1.1SLAM系統(tǒng)介紹

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

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

1.2 SLAM系統(tǒng)流程

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

實際上，整個視覺SLAM流程包括以下步驟。

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

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

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

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

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

整個過程如圖1所示。

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

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

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

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

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

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

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

2SlFT算法原理

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

下面對SIFT算法具體步驟及其原理進行簡單的介紹。

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

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

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

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

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

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

2.2DOG極值點檢測及篩選

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

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

由此可得此展開式的導數(shù)，并令其為0，得到精確的極值點位置Xmax。將Xmax帶入公式（4），只取前兩項，可得到公式（5）。

2.3生成SIFT特征向量

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

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

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

3SIFT算法的GPU加速研究

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

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

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

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

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

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

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

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

實驗結(jié)果表明，主方向模值梯度計算的加速比達到了10，遠超過其他實驗項目，所以它的并行效果最好。

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

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

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

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

4結(jié)束語

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

（1）視覺SLAM算法可以通過引.）kGPU來進行并行優(yōu)化;

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

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

綜上所述，對視覺SLAM算法進行優(yōu)化時需考慮多方面的因素，特別是當GPU存儲及計算資源不足時的負載均衡問題，以及程序的并行粒度計算，都是值得研究的問題。