Scan Matching
- Auch genannt: scan registration, point cloud registration
- Kategorie: State estimation & navigation › Localisation
- Schlagwörter: lidar, localization, slam, point-clouds, registration
Schätzung der Starrkörpertransformation, die einen Entfernungsscan mit einem anderen Scan oder einer Karte zur Deckung bringt; verwendet in LiDAR-Odometrie, Lokalisierung und SLAM, um rohe Entfernungsdaten in Posenschätzungen zu verwandeln.
Definition
Scan-Matching (scan matching) nimmt einen neuen Entfernungsscan eines LiDAR-, Sonar- oder Tiefensensors und bestimmt die Rotation und Translation, die ihn am besten mit einer Referenz zur Deckung bringen: dem vorherigen Scan, einer aktuellen lokalen Karte oder einer globalen Karte. Die resultierende Transformation ist eine Messung dafür, wie sich der Sensor bewegt hat oder wo er sich befindet. Sie ist die Kernoperation hinter LiDAR-Odometrie, kartenbasierter Lokalisierung radgetriebener Roboter und den Frontends der meisten LiDAR-SLAM-Systeme. Scan-zu-Scan-Matching ist einfach, akkumuliert aber schnell Drift; Scan-zu-Karte-Matching gleicht jeden neuen Scan mit einer akkumulierten Karte ab, was die Drift verringert und die Schätzung weniger empfindlich gegenüber dünn besetzten Einzelscans macht.
Es gibt mehrere Familien von Methoden. Punktbasierte Methoden wie Iterative Closest Point (ICP) und seine Point-to-Plane- und verallgemeinerten Varianten wechseln zwischen der Suche nach Korrespondenzen und dem Lösen nach der Transformation ab. Die Normal Distributions Transform (NDT), eingeführt von Biber und Straßer (2003), stellt die Referenz als Gitter lokaler Gauß-Verteilungen dar und maximiert die Likelihood des neuen Scans unter ihnen. Korrelatives Scan-Matching, beschrieben von Olson (2009), durchsucht eine diskretisierte Menge von Posen gegen ein Wahrscheinlichkeitsgitter und toleriert so schlechte Anfangsschätzungen. Merkmalsbasierte Methoden, bekannt geworden durch LOAM (Zhang und Singh, 2014), extrahieren Kanten- und Ebenenpunkte und gleichen sie mit Linien und Ebenen in der Karte ab, was den Rechenaufwand senkt. Gitterbasierte 2D-Matcher bilden auch den Kern von Laser-SLAM-Paketen wie Hector SLAM und Cartographer.
Die meisten Scan-Matcher konvergieren nur lokal und brauchen eine vernünftige Anfangsschätzung, meist aus der IMU, der Radodometrie oder einem Modell konstanter Geschwindigkeit. Sie versagen in vorhersehbaren Situationen: in langen Korridoren, Tunneln und auf offenem Feld, wo die Geometrie manche Richtungen schlecht einschränkt; bei bewegten Objekten, die wie Struktur aussehen; und bei Bewegungsverzerrung, wenn sich der Sensor während eines einzelnen Durchlaufs bewegt, was durch Entzerren der Punkte mit IMU-Daten korrigiert werden muss. Gute Systeme prüfen die Hesse-Matrix oder Kovarianz jedes Abgleichs, um schwach eingeschränkte Richtungen zu erkennen, und gewichten das Ergebnis bei der Fusion mit anderen Sensoren entsprechend.
Warum es wichtig ist
Entfernungssensoren liefern genaue Geometrie, aber keine direkte Pose. Scan-Matching macht aus dieser Geometrie Bewegungs- und Positionsschätzungen, daher bestimmen seine Genauigkeit und seine Fehlerbilder weitgehend die Leistung LiDAR-basierter Navigation.
Wichtige Anwendungen
- LiDAR-Odometrie und SLAM
- Lokalisierung von Lager- und Servicerobotern gegenüber einer vorhandenen Karte
- Überprüfung von Loop-Closure-Kandidaten zwischen weit entfernten Scans
- Ausrichten von Scans für 3D-Kartierung und Vermessung
- Extrinsische Kalibrierung zwischen mehreren LiDARs
In der Praxis
Bei einem Bodenroboter mit einem rotierenden 3D-LiDAR wird jeder Durchlauf zuerst mithilfe der von der IMU gemessenen Rotation entzerrt, dann werden Kanten- und Ebenenmerkmalspunkte extrahiert. Ausgehend von der durch die IMU vorhergesagten Pose werden die Merkmale des aktuellen Keyframes mit einer aus vergangenen Keyframes aufgebauten Merkmalskarte abgeglichen, und die gelöste Transformation geht als LiDAR-Odometrie-Faktor in den Schätzer ein, wie in LiDAR-visuell-inertialen Systemen wie LVI-SAM. In einem langen, merkmalsarmen Korridor schränkt der Abgleich die Bewegung entlang der Korridorachse nur schwach ein, daher prüft das Team die Eigenwerte der Hesse-Matrix des Abgleichs und lässt IMU- und visuelle Messungen diese Richtung tragen, bis sich die Geometrie verbessert.
Häufige Missverständnisse
- Scan-Matching und ICP sind dasselbe — ICP ist ein Scan-Matching-Algorithmus unter mehreren, neben NDT, korrelativen und merkmalsbasierten Methoden
- Ein guter Scan-Matcher funktioniert ohne Anfangsschätzung — die meisten Methoden konvergieren nur lokal und brauchen eine Vorabpose aus Odometrie oder IMU
- Scan-Matching schränkt alle Richtungen gleich stark ein — in Korridoren, Tunneln und offenen Bereichen kann die Geometrie manche Richtungen nahezu uneingeschränkt lassen
Wer das wissen sollte
- Ingenieure für LiDAR-SLAM und Lokalisierung
- Entwickler für die Navigation mobiler Roboter
- Wahrnehmungsteams für autonome Fahrzeuge
- Ingenieure für Vermessung und Kartierung
Verwandte Technologien
- Normal Distributions Transform (NDT)
- Generalized ICP
- LOAM
- Cartographer
- Point Cloud Library (PCL)
- KISS-ICP
Verwandte Begriffe
Verwandte Projekte
- 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
Videos
- SLAM Course - 12 - Scan-Matching in 5 Min - Cyrill Stachniss: Cyrill Stachniss