Scan Matching
- 又稱: scan registration, point cloud registration
- 類別: State estimation & navigation › Localisation
- 標籤: lidar, localization, slam, point-clouds, registration
估測讓一筆距離掃描與另一筆掃描或地圖對齊的剛體轉換;用於光達里程計、定位與 SLAM,把原始距離資料轉成姿態估測。
定義
掃描匹配(Scan matching)取來自光達、聲納或深度感測器的一筆新距離掃描,求出讓它與參考最佳對齊的旋轉與平移;參考可以是前一筆掃描、近期的局部地圖或全域地圖。所得的轉換,是對感測器如何移動或位於何處的一次量測。它是光達里程計、輪式機器人以地圖為基礎的定位,以及大多數光達 SLAM 系統前端背後的核心運算。掃描對掃描(scan-to-scan)的匹配很簡單,但漂移累積很快;掃描對地圖(scan-to-map)的匹配則把每筆新掃描與累積的地圖對齊,可減少漂移,並讓估測對稀疏的單筆掃描較不敏感。
方法分為幾大類。以點為基礎的方法,例如迭代最近點(ICP)及其點對平面與廣義變體,會在尋找對應關係與求解轉換之間交替進行。由 Biber 與 Straßer(2003)提出的常態分布轉換(NDT),把參考表示成局部高斯分布的網格,並在這些分布下最大化新掃描的概似。Olson(2009)描述的相關性掃描匹配,在機率格點上對離散化的姿態集合進行搜尋,能容忍較差的初始猜測。由 LOAM(Zhang 與 Singh,2014)推廣的以特徵為基礎的方法,會擷取邊緣點與平面點,並與地圖中的線與面匹配,以減少運算量。以格點為基礎的 2D 匹配器,也是 Hector SLAM 與 Cartographer 等雷射 SLAM 套件的核心。
大多數掃描匹配器只會局部收斂,需要合理的初始猜測,通常來自 IMU、輪式里程計或等速模型。它們會在可預期的情況下失效:長走廊、隧道與空曠場地,這些地方的幾何結構對某些方向的約束很弱;看起來像結構的移動物體;以及感測器在單次掃描期間移動所造成的運動畸變,必須利用 IMU 資料對點進行去歪斜校正。良好的系統會檢查每次匹配的 Hessian 矩陣或共變異數,找出約束較弱的方向,並在與其他感測器融合時據以為結果加權。
為何重要
距離感測器提供準確的幾何資訊,卻無法直接給出姿態。掃描匹配正是把這些幾何資訊轉成運動與位置估測的方法,因此其精度與失效模式,在很大程度上決定了以光達為基礎之導航的表現。
主要應用
- 光達里程計與 SLAM
- 倉儲與服務機器人相對於先驗地圖的定位
- 驗證相距遙遠的掃描之間的迴圈閉合候選
- 為 3D 建圖與測量對齊掃描
- 多台光達之間的外部參數校正
實際應用
在一台裝有旋轉式 3D 光達的地面機器人上,每次掃描先利用 IMU 量測到的旋轉做去歪斜,再擷取邊緣特徵點與平面特徵點。從 IMU 預測的姿態出發,把目前關鍵影格的特徵與由過去關鍵影格建立的特徵地圖匹配,求得的轉換作為光達里程計因子進入估測器,就像 LVI-SAM 等光達-視覺-慣性系統的做法。在一條又長又缺乏特徵的走廊中,匹配對沿走廊軸向的運動約束很弱,因此團隊檢查匹配 Hessian 矩陣的特徵值,在幾何條件改善之前,由 IMU 與視覺量測負責這個方向的估測。
常見誤解
- 掃描匹配與 ICP 是同一回事 — ICP 只是多種掃描匹配演算法之一,另外還有 NDT、相關性方法與以特徵為基礎的方法
- 好的掃描匹配器不需要初始猜測 — 大多數方法只會局部收斂,需要來自里程計或 IMU 的先驗姿態
- 掃描匹配對所有方向的約束都相同 — 在走廊、隧道與空曠區域,幾何結構可能讓某些方向幾乎不受約束
誰需要了解
- 光達 SLAM 與定位工程師
- 移動機器人導航開發者
- 自駕車感知團隊
- 測量與建圖工程師
相關技術
- 常態分布轉換(Normal Distributions Transform,NDT)
- Generalized ICP
- LOAM
- Cartographer
- 點雲函式庫(Point Cloud Library,PCL)
- KISS-ICP
相關術語
相關專案
- LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
- oomwoo: Open-source DIY robot vacuum: 3D-printed, ROS2 + 2D LiDAR, fully local.
- PCL: Industry-standard C++ library for point cloud processing in robotics perception
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
- FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
影片
- SLAM Course - 12 - Scan-Matching in 5 Min - Cyrill Stachniss: Cyrill Stachniss