SLAM的主要分類及在實際中的應用

SLAM剛剛開始的未來2016-07-07 14:39
　　作者：張哲，紐約州立大學機器人方向博士，清華大學自動化系本科。研發(fā)方向：地圖重建、位置跟蹤、機器人自主避障導航、設備端和云端的算法優(yōu)化。2009-2014年在微軟，2014-2016年初在Magic Leap工作。
　　責編：周建?。▃houjd@csdn.net）
　　本文為《程序員》原創(chuàng)文章，未經(jīng)允許不得轉載，更多內(nèi)容請訂閱2016年《程序員》
　　SLAM技術隨著最近幾年機器人、VR、AR的火爆而為人所知，在傳感器、算法、軟件、硬件等方向都有不同的進展。本文簡要解釋了SLAM的定義和分類，具體分析了當前VR、AR、機器人等各種應用需要什么類別的SLAM，探討了在實際應用中實現(xiàn)SLAM的一些工程細節(jié)，并展望了SLAM剛剛開始的未來。
　　什么是SLAM
　　SLAM是什么？根據(jù)Wikipedia的介紹：“Simultaneous Localization and Mapping （SLAM） is the computational problem of constructing or updating a map of an unknown environment while simultaneously keeping track of an agent’s location within it.”最簡單而又直指本質的理解，SLAM指的是當某種設備（如機器人、VR設備等）來到一個完全陌生的環(huán)境時，它需要精準地建立時間和空間的對應關系，并能完美地回答以下一系列問題：我剛才在哪里，現(xiàn)在在哪里？我看到了什么，現(xiàn)在看到的和之前看到的有哪些異同？我過去的行走軌跡是什么？我現(xiàn)在看到的世界是什么樣子，和過去相比有怎樣的變化？我的軌跡抖嗎，我的位置飄嗎？我還能跟蹤到自己的軌跡嗎，如果我丟了應該怎么辦？我過去建立的對世界的認識還有用嗎？我能在已有世界的抽象里快速對我現(xiàn)在的位置進行定位嗎？
　　SLAM的主要分類
　　robotic SLAM
　　從最早期軍事用途的雛形到后來的機器人應用，業(yè)界對SLAM有了進一步的研究。robotic SLAM主要包括卡爾曼濾波和粒子濾波。卡爾曼濾波在很多工程領域中都有應用，最早期用于機器人的卡爾曼濾波，默認系統(tǒng)是線性的且?guī)Ц咚狗植嫉脑胍簦?jīng)典的卡爾曼濾波可以直接給出最優(yōu)解，但現(xiàn)實比這復雜太多，所以有了卡爾曼濾波的很多變種。而如果不是線性系統(tǒng)或噪音不是高斯分布，那么粒子濾波算法生成很多粒子，并且每個粒子是模型狀態(tài)的一種可能，再根據(jù)觀察和更新得到粒子群的狀態(tài)趨于一致的收斂結果。當然粒子濾波也有實際的問題，比如經(jīng)典的粒子衰減問題（particle depletion），和工程上如何控制準確性和收斂速度很好平衡的問題。
　　PTAM
　　PTAM（Parallel Tracking and Mapping）架構更多的是系統(tǒng)上的設計，姿態(tài)跟蹤（Tracking）和建立地圖（Mapping）兩個線程是并行的，這實質上是一種針對SLAM的多線程設計。PTAM在當前SLAM領域看來是小兒科，但在當時是一個創(chuàng)舉，第一次讓大家覺得對地圖的優(yōu)化可以整合到實時計算中，并且整個系統(tǒng)可以跑起來。具體而言，姿態(tài)跟蹤線程不修改地圖，只是利用已知地圖來快速跟蹤；而在建立地圖線程專注于地圖的建立、維護和更新。即使建立地圖線程耗時稍長，姿態(tài)跟蹤線程仍然有地圖可以跟蹤（如果設備還在已建成的地圖范圍內(nèi)）。這是兩個事情并行來做的一個好處，但很現(xiàn)實的問題是如果地圖建立或優(yōu)化過慢，跟蹤線程很容易會因為沒有最新的地圖或者沒有優(yōu)化過的地圖而跟丟。另外比較實際的工程問題是地圖線程的最新地圖數(shù)據(jù)應該lock還是copy data between threads以及threading的實現(xiàn)質量。
　　sparse SLAM
　　現(xiàn)在常說的sparse SLAM從架構上主要分為兩大類：filter based和keyframe based。這里的濾波比早年的robotic SLAM的濾波已經(jīng)復雜很多，比較有代表性的是EKF SLAM，核心的思想是對非線性系統(tǒng)進行線性近似。最簡單的例子，如果是一個變量，那么就用當前模型值和導數(shù)來表達；如果多個變量，那么表達就是Jacobian Matrix。filter based的full scale SLAM需要注意filter state和計算時間的平衡，以及實際工程實現(xiàn)里面的矩陣分塊更新（高維度的稀疏矩陣取逆直接就爆了）。keyframe based SLAM的核心思想是關鍵幀（keyframe）的概念——因為每一張圖都用來建立或更新地圖計算量太大，從image stream里面選擇一些好的關鍵幀來建立并更新地圖——PTAM里的地圖建立就是從關鍵幀生成地圖。這種思路已經(jīng)被業(yè)內(nèi)普遍接受。但關鍵幀的提取本身就是一門很大的學問，伴隨而來的還有局部地圖和全局地圖的維護、更新和效率平衡。
　　dense SLAM
　　dense SLAM是另外一大類SLAM。這里說的sparse或dense指的是地圖點的稀疏或稠密程度。舉個簡單的例子，sparse map都是通過三角測量法算出來的，在一個臥室里有一千個點足夠了；但dense map一般是某種主動光源的深度傳感器（depth sensor，如英特爾的RealSense里面是ASIC）產(chǎn)生的，假設depth sensor每一幀的分辨率是640x480，即使有2/3的invalid depth，仍然有十萬個3D點，所以通常所說的sparse map和dense map相比至少差了兩個數(shù)量級。因為dense SLAM有足夠多的地圖信息，所以很適合用來做精細的3D重建。而如果dense SLAM要實時地從0到1邊建地圖邊跟蹤，就要把每一幀的可用像素的深度數(shù)據(jù)全部用來貢獻到建立地圖和跟蹤上。dense SLAM的代表是Kinect Fusion，到目前已經(jīng)有很多變種和進化，如ElasticFusion和DynamicFusion等。
　　近年來的SLAM“變種人”
　　DTAM - Dense Tracking and Mapping
　　DTAM繼承了關鍵幀的架構，但對關鍵幀的處理和傳統(tǒng)的特征點提取有很大的不同。相比傳統(tǒng)方法對每一幀進行很稀疏的特征點提取，DTAM的direct method在默認環(huán)境亮度不變（brightness consistancy assumption）的前提下，對每一個像素的深度數(shù)據(jù)進行inverse depth的提取和不斷優(yōu)化來建立稠密地圖并實現(xiàn)穩(wěn)定的位置跟蹤。用比較直觀的數(shù)字對比來說明DTAM和PTAM的區(qū)別：DTAM的一個關鍵幀有30萬個像素的深度估計，而PTAM一般的做法是最多一千個。DTAM的優(yōu)缺點很明顯（具體對比見圖1）：準、穩(wěn)，但速度是問題，每一個像素都計算，確實容易通過GPU并行計算，但功耗和產(chǎn)品化的難度也都隨之升高。
　　
　　圖1 兩種關鍵幀處理方式的比較
　　（圖片來自Jakob Engel在ICCV 2015的PPT）
　　Semi-Dense LSD SLAM - Semi-Dense Large Scale Direct SLAM
　　這里要特別說明，LSD SLAM里semi的是像素數(shù)量，也就是說，只估計“有信息”的區(qū)域，而不是像DTAM那樣每個像素都估計，更簡單形象（但不是100%學術嚴謹）地說，只估計“有紋理”的地方，不估計令每一個做SLAM的人都害怕的終極大魔頭——“大白墻”部分。參見圖2，右上是semi-dense， 左下是sparse approach，右下是dense approach。估計深度的部分在原理上也是direct method，和DTAM類似，這里不做過多描述。速度上，semi-dense在一臺只有酷睿i7處理器的電腦上是可以做到實時的。