--關注回復“SOA”--
↓↓領取：面向智能車輛開發的開放性SOA方案↓↓
今天我們討論基于環境特征的地圖匹配定位。地圖匹配定位是根據車輛相對于當地地標的位置來進行定位。在許多情況下，我們有提供當地地標的地圖作為參考框架。基于先驗地圖，我們匹配歷史中最相似的地圖子集（圖像/點云/特征點），根據匹配到的地圖子集所提供的歷史位姿真值、特征點坐標真值，計算點對間的變換矩陣，求解當前定位。地圖匹配定位通常會輸出相對的XYZ坐標，滾動/俯仰/偏航數值，或表示方向和空間自由的四元數。最流行的地圖匹配定位算法有迭代最近點 (ICP) 以及正態分布變換 (NDT)。
為了進行地圖匹配定位，我們必須有某種形式的傳感器輸入，例如激光雷達，雷達，相機等。使用激光雷達，可以會得到相對于基于點云的地圖 (Point-cloud-based map) 的定位；使用雷達，可以得到相對于基于返回的地圖 (Return-cloud-based map) 的定位；使用具有分類和深度的相機的位置，可以得到相對于基于對象的地圖 (Object-based map) 的定位。
本文討論主要集中在基于點云地圖的 ICP 和 NDT 算法的原理和性能區別，以及相應拓展的深度學習?法。
基于點云的地圖匹配方法
自動駕駛汽車中，攝像頭被廣泛應用，基于大量圖像數據的深度學習應用的方式和功效已被廣泛研究。然而，由于相機拍攝的圖像只能記錄二維的環境，不能用于準確估計三維環境，激光雷達（LiDAR）因此引起了業界的關注。在適當條件下，相比其他環境傳感器，如攝像頭和雷達，激光雷達更加精確和穩健，能夠獲取誤差率在一厘米以內的三維距離信息。
在實際操作中，由于城市和郊區環境會不斷變化，會影響匹配算法的精度。這些變化發生在不同的時間尺度上，包括動態和短暫的對象（例如停放的汽車），季節性的變化（植被、雪、灰塵）和人類影響，例如建造。因此，算法面對這些真實環境變化時的魯棒性至關重要。其次，由于自動駕駛系統必須根據車輛行駛過程中環境變化做出實時決策，低延遲性極其關鍵。典型城市車速15~35mph，超過 100 毫秒的延遲將導致可能導致米級別的車輛位置不確定性，導致安全問題。因此，匹配算法需要同時考量精度和速度。
圖?1. a: 實際地圖?b: 點云地圖?
作為業界最流行的三維環境點云匹配算法，ICP 和 NDT 已廣泛用于地圖構建和三維重建。圖 2 展示了正態分布地圖與點云地圖之間的地圖匹配過程。該過程對點云中的所有點執行匹配過程并重復，直到獲得準確的汽車姿態估計。
圖?2. 地圖匹配流程?
圖?3. ICP（Udacity Self Driving Car Nanodegree）
圖?4. NDT（Udacity Self Driving Car Nanodegree）
相關的研究顯示，當在小范圍并有足夠數量的特征時，這兩種方法都表現得非常穩健，但 NDT 的運行速度比 ICP 快得多，并且定位誤差要小得多。與 ICP 中關注單個點相比，將環境進行三維像素概率化的表達使得 NDT 能夠獲得環境的整體認知而不只是細節。基于 NDT 的方法具有更好的能力來處理實際變化，包括靜態和動態的環境變化，以及計算效率更高。研究同時顯示，NDT 的性能很大程度取決于三維像素分辨率的選擇。換句話說，需要根據傳感器精度以及環境條件，仔細地調整三維像素的大小，才能保證其性能。
然而，在進行大規模的環境匹配時，ICP 和 NDT 作為傳統的點云匹配方法，都顯示無法勝任所需的通用性和可擴展性，計算上也缺乏效率。
圖?5. ICP 與 NDT 在不同像素下的性能對比
圖?6. ICP?與 NDT?在轉彎時的性能對比
地圖匹配深度學習
基于深度學習的地圖匹配一直存在著相當的挑戰性，這與現有解決方案中常用的模型的局限性有關。現有方案把地圖匹配理解為圖神經網絡（GNN）或序列到序列（seq2seq）結構，然而，這些方案無法完全捕捉 3D 點云中的空間分布和上下文線索，也無法進行并行處理，因而地圖匹配的精度和速度都不理想。而且，現有解決方案常常會對原始密集的 3D 點云進行下采樣操作，而導致局部幾何信息的退化。
深度學習的最新發展，尤其是在 Transformer 方面的研究，開始改變這個現狀。
Transformer 同時考慮數據點的內部相關性軌跡，以及輸入軌跡和輸出路徑之間的外部關系，通過并行的方式使用自我和多頭注意機制提取多組特征表達，從而實現更精確和快速的匹配。以下，我們將細節討論基于 Transformer 的 ICP 和 NDT 的深度學習模型。
圖?7. DCP 網絡架構
DCP 由三部分組成：
（1）DGCNN 模塊將輸入 3D 點云映射到固定的表征排列，
（2）基于 Transformer 的注意力模塊，結合指針網絡預測點云之間的軟匹配，
（3）奇異值分解層（SVD）預測運動轉變。
注意力模塊的加入使得 DCP 模型能足夠可靠地一次性提取對齊兩個輸入 3D 點云間的運動所需的對應關系，并且還可以通過經典 ICP 的迭代方法繼續提高。相應的實驗展示 DCP 不僅高效，而且優于 ICP 和它的變體。
圖?8. DCP 性能對比
NTD-Transformer：基于 Transformer 的 NDT
NDT-Transformer 可以實現基于 3D 點云的實時和大規模地點識別。它采用三維空間的概率分布變換來壓縮原始、密集的 3D 點云作為 NDT 單元，以提供幾何形狀描述表達。然后，利用 Transformer 網絡從一組 NDT 單元中學習全局描述表征。受益于 NDT 和 Transformer 網絡， NDT-Transformer 學習到的全局描述表征同時豐富了幾何和上下文信息，然后使用查詢數據庫進行表征匹配檢索，實現地點識別。與單獨的 NDT 相比，NDT-Transformer 性能有明顯的提升。
圖?9. NDT-Transformer 網絡架構
NDT-Transformer 主要由三部分組成：
1）由點變換和不確定性反向傳播組成的 NDT 表達模塊，
2）殘差 Transformer 編碼器，
3) 局部聚合描述表達的描述向量 (NetVLAD)。
在將 3D 點云 NDT 化之后，與大多數人的現有方法利用 KNN 分組對上下文信息建模的方法不同， NDT-Transformer 使用注意力機制來學習底層地標（NDT 單元）之間的上下文，并采用殘差 Transformer 編碼器聚合一個 NDT 單元與其他 NDT 單元的上下文線索，以增加表征的獨特性。
然后， NDT-Transformer 使用 NetVLAD 代替最大池化層來提高 3D 點云描述的排列不變性。NetVLAD 通過記錄本地特征與參照特征之間區別的統計信息以及總和，將一組本地描述聚合生成一個全局描述表征向量。最后使用一個多層感知器 (MLP)，將一組 NDT 單元描述表征融合為一個固定大小的全局描述表征向量。
NDT-Transformer 通過分層地聚合和增強局部特征，從而在運行時間和匹配結果上獲得極好的表現。在 Oxford Robocar 數據集上的實驗結果表明 NDT-Transformer 能夠成功地找到 SOTA 性能和運行時間之間的妥協。
圖?10. NDT-Transformer 性能對比
小結
現有的研究中，并沒有對都是基于 Transformer 的 DCP 和 NDT-Transformer 精確性進行直接對比，但理論上來講， NDT-Transformer 在計算效率上具有更高的通用性和可擴展性。雖然因為篇幅的原因，我們無法詳盡地含括所有的深度學習在地圖匹配方面的應有，但令人欣喜的是最新的深度學習發展，尤其是 Transformer，通過引入自注意力機制和上下文的信息提取，給地圖匹配算法提供了新的靈感和研究方向。
2.NDT-Transformer: Large-Scale 3D Point Cloud Localisation using the Normal Distribution Transform Representation，Zhicheng Zhou, Cheng Zhao, Daniel Adolfsson, Songzhi Su, Yang Gao, Tom Duckett and Li Sun, Arxiv, 2021.
3.Deep Closest Point: Learning Representations for Point Cloud Registration, Yue Wang and?Justin M. Solomon, Arxiv, 2019.
4.Map-Matching Algorithms for Robot Self-Localization: A Comparison Between Perfect Match, Iterative Closest Point and Normal Distributions Transform, Heber Sobreira, Carlos Miguel Correia da Costa, Ivo M. Sousa and Luís F. Rocha, Springer, 2019.
5.3D Scan Registration Based Localization for Autonomous Vehicles - A Comparison of NDT and ICP under Realistic Conditions, Su Pang, Daniel Kent, Xi Cai, Hothaifa Al-Qassab, Daniel Morris and Hayder Radha, Arxiv, 2018.
轉載自汽車電子與軟件，文中觀點僅供分享交流，不代表本公眾號立場，如涉及版權等問題，請您告知，我們將及時處理。
-- END --
