高精地圖是無人駕駛核心技術之一，精準的地圖對無人車定位、導航與控制，以及安全至關重要，本文首先介紹高精地圖與傳統地圖的區別，然后介紹其特點及制作過程。在了解高精地圖基礎知識后，探索其在無人駕駛場景中的應用。
電子地圖分類
我們日常使用的用于導航、查詢地理信息的地圖都屬于傳統電子地圖，其主要服務對象是人類駕駛員。而與傳統電子地圖不同，高精度電子地圖的主要服務對象是無人駕駛系統。本節討論兩者的不同。
傳統電子地圖
如圖1所示，我們日常使用的用于導航、查詢地理信息的地圖，如Google、百度、蘋果地圖等，都可以并入傳統電子地圖。盡管電子地圖出現還不到一百年，對傳統地圖的研究和開發已有幾千年歷史，并發展出“制圖學”這一門學科。在制圖學的基礎上，電子地圖的出現極大提高了檢索效率，并且能快速查找最優路徑，極大方便了人們出行。
圖1傳統電子地圖
傳統電子地圖是對路網的一種抽象：都將路網抽象成有向圖的形式——圖的頂點代表路口，邊代表路口與路口的連接。路名、地標以及道路骨架信息都可以被抽象成存儲于這些有向圖頂點或邊中的屬性。這種抽象的地圖表征形式能很好地適應人類駕駛員需求，其原因在于人類生來就有很強的視覺識別及邏輯分析能力。在駕駛過程中，人類駕駛員一般都能有效判別如下信息：識別路面及路面標示線，確定自己在路面的大致位置，尋找并辨認路標等。參照辨識出的信息，結合當前GPS(一般精度在5-10米)在當前電子地圖中的位置，人類駕駛員便大致知道自己在實際路網中的位置，并計劃下一步如何駕駛。
正是基于人類駕駛員的這些能力，傳統電子地圖可被極大精簡，比如一條彎曲的道路可以被精簡到用只有幾個點的線段來表示，只要大致輪廓符合現實路網結構，人類駕駛員即可結合駕駛信息定位自己的當前位置。
高精電子地圖
與傳統電子地圖不同，高精度電子地圖的主要服務對象是無人駕駛車，或者說是機器駕駛員。和人類駕駛員不同，機器駕駛員缺乏與生俱來的視覺識別、邏輯分析能力。比如，人可以很輕松、準確地利用圖像、GPS定位自己，鑒別障礙物、人、交通信號燈等，但這對當前的機器人來說都是非常困難的任務。因此，高精度電子地圖是當前無人駕駛車技術中必不可少的一個組成部分。高精度電子地圖包含大量行車輔助信息，其中，最重要的是對路網精確的三維表征(厘米級精度)。比如，路面的幾何結構，道路標示線的位置，周邊道路環境的點云模型等。有了這些高精度的三維表征，車載機器人就可以通過比對車載GPS、IMU、LiDAR或攝像頭數據來精確確認自己的當前位置。此外，高精地圖還包含豐富的語義信息，比如交通信號燈的位置及類型，道路標示線的類型，識別哪些路面可以行駛等。這些能極大提高車載機器人鑒別周圍環境的能力。此外，高精度地圖還能幫助無人車識別車輛、行人及未知障礙物。這是因為高精地圖一般會過濾掉車輛、行人等活動障礙物。如果無人車在行駛過程中發現當前高精地圖中沒有的物體，便有很大幾率是車輛、行人或障礙物。因此，高精地圖可以提高無人車發現并鑒別障礙物的速度和精度。
高精地圖特點
相比服務于GPS導航系統的傳統地圖而言，高精地圖最顯著的特點是其表征路面特征的精準性。傳統地圖只需要做到米級精度即可實現GPS導航，但高精地圖需要達到厘米級精度才能保證無人車行駛安全。
此外，高精地圖還需要比傳統地圖有更高的實時性。由于路網每天都有變化，如整修、道路標識線磨損及重漆、交通標示改變等。這些變化需要及時反映在高精地圖上以確保無人車行駛安全。實時高精地圖有很高的難度，但隨著越來越多載有多種傳感器的無人車行駛在路網中，一旦有一輛或幾輛無人車發現了路網的變化，通過與云端通信，就可以把路網更新信息告訴其他無人車，使其他無人車更加聰明和安全。
圖2高精電子地圖
數據特征類型
和傳統地圖相似，高精地圖也具有分層的數據結構。如圖3所示，最底層是基于紅外線雷達傳感器所建立的精密二維網格。一般這個二維網格的精度保證在5×5厘米左右。可以行駛的路面、路面障礙物，以及路面在激光雷達下的反光強度都被存儲于相應的網格當中。無人車在行駛的過程中，通過比對其紅外線雷達搜集到的數據及其內存中的高精二維網格，就能確定車輛在路面的具體位置。
圖3高精地圖二維網格表征。由于網格很細，我們可以從相應的雷達反射上清楚識別出路面及路面標識線的位置。綠色區域表示不可行駛的路面
除了底層的二維網格表征外，高精地圖還包含很多有關路面的語義信息。如圖4所示，在二維網格參照系的基礎上，高精地圖一般還包含道路標識線的位置及特征信息，以及相應的車道特征。由于車載傳感器可能會因為惡劣天氣、障礙物，以及其他車輛的遮擋不能可靠分析車道信息，高精地圖中的車道信息特征能幫助無人車更準確可靠地識別道路標識線，并理解相鄰車道之間是否可以安全并道。
圖4高精地圖中的車道信息
圖5高精地圖中的道路標識線及路牌信息
此外，如圖5所示，高精地圖還會標明道路標示牌、交通信號等相對于二維網格的位置，這些信息起兩方面作用：
提前預備無人車，告知其在某些特定的位置檢測相應的交通標示牌或交通信號燈，提高無人車的檢測速度。
在無人車沒有成功檢測出交通標示牌或信號燈的情況下，確保行車安全。
數據量估計
無人車使用的高精地圖是個2D網格，數據主要由激光雷達產生，由于激光雷達的精度大約是5厘米，所以地圖的最高精度可以達到每個網格5×5厘米。在如此高的精度下，如何有效管理數據是一大挑戰。首先，為了盡量讓地圖在內存里中，我們要盡量去掉不需要的數據。一般激光雷達可覆蓋方圓100米范圍，假設每個反光強度可以用一個字節記錄，那么每次激光雷達掃描可產生4MB數據。掃描會包括公路旁邊的樹木及房屋，但無人車行駛并不需要這些數據，只需記錄公路表面的數據即可。假設路面的寬度為20米，就可以通過數據處理把非公路表面的數據過濾掉，這樣每次掃描的數據量會下降到0.8MB。在過濾數據的基礎上，還可以使用無損壓縮算法，如LASzip壓縮地圖數據，可以達到超過10倍的壓縮率。經過這些處理后，1TB硬盤就可以存下全中國超過10萬公里的高精地圖數據。
高精地圖的生產
傳統電子地圖主要依靠衛星圖片產生，然后由GPS定位，這種方法可以達到米級精度。而高精地圖需要達到厘米級精度，僅靠衛星與GPS是不夠的。因此，其生產涉及多種傳感器,由于產生的數據量龐大，通常會使用數據采集車(如圖6所示)收集，然后通過線下處理把各種數據融合產生高精地圖。
圖6高精地圖數據采集車
所需要的傳感器種類
高精地圖的制作是個多傳感器融合的過程，包括了以下幾種：
陀螺儀（IMU）： 一般使用6軸運動處理組件，包含了3軸加速度和3軸陀螺儀。加速度傳感器是力傳感器，用來檢查上下左右前后哪幾個面都受了多少力(包括重力)，然后計算每個上的加速度。陀螺儀就是角速度檢測儀，檢測每個上的加速度。假設無人車以Z軸為軸心，在一秒鐘轉到了90度，那么它在Z軸上的角速度就是90度/秒。從加速度推算出運動距離需要經過兩次積分，所以，但凡加速度測量上有任何不正確，在兩次積分后，位置錯誤會積累然后導致位置預測錯誤。所以單靠陀螺儀并不能精準地預測無人車位置。
輪測距器（Wheel Odometer）： 我們可以通過輪測距器推算出無人車的位置。汽車的前輪通常安裝了輪測距器，分別會記錄左輪與右輪的總轉數。通過分析每個時間段里左右輪的轉數，我們可以推算出車輛向前走了多遠，向左右轉了多少度等?？墒怯捎谠诓煌孛娌馁|(比如冰面與水泥地)上轉數對距離轉換的偏差，隨著時間推進，測量偏差會越來越大。所以單靠輪測距器并不能精準預測無人車位置。
GPS：任務是確定四顆或更多衛星的位置，并計算出它與每顆衛星之間的距離，然后用這些信息使用三維空間的三邊測量法推算出自己的位置。要使用距離信息進行定位，接收機還必須知道衛星的確切位置。GPS接收機儲存有星歷，其作用是告訴接收機每顆衛星在各個時刻的位置。在無人車復雜的動態環境，尤其在大城市中，由于各種高大建筑物的阻攔。GPS多路徑反射(Multi-Path)的問題會更加明顯。這樣得到的GPS定位信息很容易就有幾十厘米甚至幾米的誤差，所以單靠GPS不可以制作高精地圖。
激光雷達（LiDAR）： 光學雷達通過首先向目標物體發射一束激光，然后根據接收-反射的時間間隔來確定目標物體的實際距離。然后根據距離及激光發射的角度，通過簡單的幾何變化可以推導出物體的位置信息。LiDAR系統一般分為三個部分：一是激光發射器，發出波長為600nm到1000nm的激光射線;二是掃描與光學部件，主要用于收集反射點距離與該點發生的時間和水平角度(Azimuth);三是感光部件，主要檢測返回光的強度。因此我們檢測到的每一個點都包括了空間坐標信息以及光強度信息。光強度與物體的光反射度(reflectivity)直接相關，所以從檢測到的光強度也可以對檢測到的物體有初步判斷。
高精地圖計算模型
下圖展示了通用的高精地圖制作流程。首先陀螺儀(IMU)及輪測距器(Wheel Odometer)可以高頻率地給出當前無人車的位置預測，但由于其精確度原因，位置可能會有一定程度偏差。為了糾正這些偏差，可以使用傳感器融合計技術(比如使用Kalman Filter)結合GPS與激光雷達(LiDAR)的數據算出當前無人車的準確位置。然后根據當前的準確位置與激光雷達的掃描數據，把新數據加入地圖中。
圖7高精地圖計算架構
公式1是個高度簡化的高精地圖計算模型, Q代表優化方程，z代表激光雷達掃描出的點，h為方程預測最新掃描點的位置與反光度，m為掃描到的點在地圖中的位置，x代表無人車當前位置。這個方程的目的是通過最小化J求出測量點在地圖中的準確位置。在計算模型中，m與x開始都是未知的，可以先通過多傳感器融合求x，再求出測量點在地圖中的準確位置m。
無人駕駛場景中的應用
如上文所述，高精度電子地圖包含大量的行車輔助信息，包括路面的幾何結構、標示線位置、周邊道路環境的點云模型等。有了這些高精度的三維表征，無人駕駛系統就可以通過比對車載GPS、IMU、LiDAR或攝像頭的數據來精確確認自己當前的位置，并進行實時導航。
定位
無人車對可靠性和安全性要求非常高，所以我們默認已由高精度LiDAR和多種傳感器融合建好了地圖，在這個前提下，再談一談無人車的跟蹤和定位技術。
無人車定位主要通過粒子濾波進行。所謂粒子濾波就是指：通過尋找一組在狀態空間中傳播的隨機樣本來近似表示概率密度函數，用樣本均值代替積分運算，進而獲得系統狀態的最小方差估計的過程，這些樣本被形象地稱為“粒子”，故而叫粒子濾波。比較常見的(如在Sebastian Thrun的經典無人車論文中)是粒子濾波維護一個姿態向量(x, y, yaw)，默認roll/pitch相對足夠準，運動預測可以從IMU中取得加速度和角速度。粒子濾波需要注意樣本貧化和其他可能的災難定位錯誤(catastrophic error)，一小部分粒子可以持續從現在GPS的位置估計中獲得。正如前文所說，對樣本數量的自適應控制也需要根據實際情況有效調整。
因為已經有了高精度LiDAR點云地圖，所以很自然地就可以用實時點云數據和已經建好的地圖進行匹配。而3D點云匹配必然要說到Iterative Closest Point (ICP)，ICP的目標是在給出兩組點云的情況下，假設場景不變，算出這兩組點云之間的pose。最早的ICP原理，就是第一組點云的每個點在第二組點云里找到一個最近的匹配，之后通過所有的匹配來計算均方誤差(MSE)，進而調整估計的pose，這樣進行多次迭代，最終算出兩組點云的相對pose。因此，預先有地圖的情況下，用實時的點云加上一個大概pose猜測就可以精準算出無人車的當前pose，且時間相鄰的兩幀點云也可以算出一個相對pose。
另一方面，因為無人車是個復雜的多系統融合，所以當前標配是LiDAR，Camera、IMU(六軸陀螺儀)都必須擁有。擁有了Camera和IMU，做各種VO (Visual Odometry)和最近的VIO(Visual Inertial Odometry)SLAM就是自然選擇。前面提到的粒子濾波，還有各種版本的卡爾曼濾波，加上Graph和關鍵幀概念，都屬于SLAM范疇。筆者之前曾詳細介紹了SLAM的各種應用探討和相對應的工程細節(參見《SLAM剛剛開始的未來》)，在此不再一一討論，但值得注意的是，多傳感器多信息源融合只要算法正確并工程實現扎實，效果一定會比單一傳感器要好。舉兩個具體的例子：ICP雖然后來有了很多改進(比如point-to-distance的測量改進，又比如用kd-tree加速查找改進)，但需要很好的初始化pose，否則ICP很容易掉入局部最優而搞不定全局最優，這時非常需要圖像視覺補充。圖像的特征點提取描述計算可以讓匹配更精準，速度也不慢，但距離太遠精準度會下降，而且有很多圖像視覺無法搞定的情況(比如無人車或者別的物體陰影，又比如光照變化，獲取illumination-invariant特征非常困難)，所以筆者認為，多傳感器多信息源融合不是“讓它變好”，而是“沒你不行”。更明顯的是，GPS在戶外已經很可靠，沒有理由不用它先告訴無人車的大概位置。
導航與控制
跟蹤和定位技術還是被動的感知方案，而真正意義的無人車也就是全自主駕駛而不是輔助駕駛需要無人車自己智能地來做路徑規劃，這里從技術層面略作探討。
路徑規劃是個范疇很大的話題，需要先做幾個限定：一是地圖已知，如果未知，就無“規劃”可言，機器人或無人車如果完全對世界未知，那么問題實際是“SLAM+探索”;二是對無人車領域來說，一般還是2D或2.5D地圖，而不是在3D地圖上六個自由度運動規劃(那是室內全自主無人機飛行);三是路徑規劃默認無人車按照規劃的路徑每一步執行后的pose準確，也就是說，這里刻意把定位和路徑規劃分開，但實際工程中這兩者緊密聯系，因為如果定位不準，路徑規劃一定會受影響。
即使有了這幾個設定，路徑規劃本身有多個教科書版本。這里簡單談有代表性又被廣泛應用的兩種。一是明確尋找最佳路徑的搜索A*算法，核心理念是：如果有最好的路徑便一定將其找到。如果單位路徑成本(cost)不一樣，最好的路徑不一定是最短的。A*是搜索了所有可能后，選擇了最好的，而且運用了啟發式算法來決定。其數據結構實現是priority queue，不停選取“最小成本”節點來擴建路徑。
另一類是基于抽樣(sampling based)的路徑規劃——并不知道最優路徑是什么，所以從起點開始隨機抽樣(怎么隨機很有講究)來擴建可能的路徑集。有一個很重要的因素可以加速抽樣——障礙物的檢測。若遇到障礙物，在其方向再擴建路徑便沒有意義。典型的算法是RRT (Rapidly-exploring Random Tree)。但需要注意，這種算法側重有效率地讓樹往大面積沒有搜索過的區域增長，實際運用中(特別是在無人車應用中)，如果有了啟發式算法，實時的路徑規劃很注重效率，需根據實際情況優化。這方面的研究包括RRT變種或兩類算法的結合(如A*-RRT)。
筆者想強調：在無人車工程實現中，路徑規劃一定要根據傳感器情況和地圖質量來做實際算法選擇和調整。無論地圖有多準，傳感器的數據質量如何，優化永遠需要在安全的前提下進行。
結論
高精度電子地圖的信息量與質量直接決定了無人駕駛系統的安全性、可靠性，以及效率。與傳統電子地圖不同，高精地圖更精準(厘米級)，更新更快，并且包含了更多信息(語義信息)。由于這些特性，制作高精地圖并不容易，需要使用多種傳感器互相糾正。在初始圖制作完成后，還需要進行過濾以降低數據量達到更好的實時性。在擁有了這些高精度地圖信息后，無人駕駛系統就可以通過比對車載GPS、IMU、LiDAR或攝像頭數據來確認當前的精確位置，并進行實時導航。
