SLAM aus algorithmischer Sicht (Teil 2)

Wie in Teil 1 erläutert, ist SLAM die gleichzeitige Schätzung der Position eines Roboterfahrzeugs in einem unbekannten Terrain und die schrittweise Kartierung dieses Terrains. SLAM-Algorithmen nutzen drei Hauptverfahren, nach denen sie katgeoriesiert werden können. Dabei handelt es sich um filterbasiertes SLAM, grafikbasiertes SLAM und auf tiefenlernbasiertes SLAM.

Filterbasiertes SLAM behandelt SLAM wie ein Zustandsschätzungsproblem. Hier wird in der Regel ein probabilistischer Filter wie der Extended Kalman Filter (EKF) oder der Unscented Kalman Filter (UKF) genutzt, um den Zustand des Roboters rekursiv zu schätzen und die Karte auf der Grundlage von Sensormessungen zu aktualisieren. Der Filter sagt den nächsten Zustand des Roboters auf der Grundlage seines Bewegungsmodells voraus und korrigiert diese Vorhersage dann anhand von Sensormessungen.

Beim grafikbasierten SLAM wird das Problem im Gegensatz zum filterbasierten SLAM als ein Grafikoptimierungsproblem betrachtet. Hier wird das SLAM-Problem grafisch ausgedrückt, wobei die Knoten Roboterposen oder Landmarken in der Umgebung darstellen und die Kanten die Messungen oder Begrenzungen zwischen ihnen. Ziel des grafikbasierten SLAM ist es, die Posen des Roboters und die Positionen der Landmarken so zu optimieren, dass die gemessenen Begrenzungen (z. B. Abstände zwischen Landmarken, relative Posen zwischen Roboterposen) möglichst genau erfüllt werden.

Tiefenlernbasierte SLAM-Verfahren nutzen neuronale Netzwerke, um Repräsentationen der Umgebung direkt aus Sensordaten zu erlernen, ohne sich auf handgefertigte Funktionen oder Modelle zu verlassen. Diese Verfahren können komplexe Zuordnungen zwischen Sensormessungen und der Roboterpose oder der Karte erlernen und so durchgehende SLAM-Lösungen ermöglichen.

Die Kernfunktionen von SLAM, Kartierung und Positionsbestimmung sind eng miteinander verknüpft, wobei der Roboter seine Karte auf der Grundlage von Sensordaten dauernd aktualisiert und seine Positionsschätzung entsprechend anpasst. Als modulares Werkzeug ermöglichen SLAM und seine Konzepte Austausch- und Änderungsvorgänge in der Pipeline. Daher werden sehr oft mehrere Algorithmen entwickelt und kombiniert, was die Verallgemeinerung und Erklärung von SLAM als einen einzigen Algorithmus schwierig macht. Der beste Weg, SLAM zu verstehen, ist also, sich auf eine bestimmte Implementierung von SLAM zu konzentrieren. Schauen wir uns daher das filterbasierte visuelle SLAM (vSLAM) einmal im Detail an.

Visuelles SLAM

Wie der Name schon sagt, verwendet vSLAM einen visuellen Sensor, eine Kamera, als primären Sensor. Dieser kann mit Encodern, einer Trägheitsmesseinheit und anderen Sensoren ergänzt werden. Ein allgemeines Blockdiagramm in Abbildung 1 veranschaulicht die Implementierung.

Abbildung 1: Vereinfachtes generisches Blockdiagramm des filterbasierten SLAM-Prozesses. (Bildquelle: kudan.io (bearbeitet))

Kameramessung

Die Kamera nimmt Bilder der Umgebung des Roboters auf, einschließlich von Merkmalen wie Landmarken, Rändern und Texturen. Die aufgenommenen Bilder müssen jedoch entzerrt werden, da die meisten Kameraobjektive eine gewisse Verzerrung aufweisen. Bei den verwendeten Kameras kann es sich um Stereo-, Mono- oder RGB-D-Kameras mit ToF-Sensoren (Time of Flight - Laufzeit) handeln. Der Vorteil von Stereo- und RGB-D-Kameras ist, dass Tiefeninformationen leicht verfügbar sind. Bei Mono-Kameras besteht die Schwierigkeit eines mehrdeutigen Maßstabs. Das heißt, SLAM mit einer Mono-Kamera kann die Länge der Translationsbewegung (Skalierungsfaktor) nicht allein anhand der Merkmalskorrespondenzen bestimmen. Es gibt Lösungsansätze hierfür, die jedoch den Rahmen dieses Beitrags sprengen würden.

Merkmalsextraktion

Nach der Aufnahme der Bilder mit einem Kamerasensor müssen wir ein Bild eindeutig identifizieren, indem wir die Merkmale eines bestimmten Bildes für den späteren Rückbezug bestimmen. Ein Merkmal ist in diesem Zusammenhang die Sammlung von Pixeln, die einzigartig sind und durchgängig identifiziert werden können. Anders gesagt, handelt es sich um markante Punkte in einem Bild, die sich bei Drehung, Skalierung und Verzerrung nicht verändern, so dass sie auch nach Bildmanipulationen leicht wiederzuerkennen sind. Da wir eine Stereo-Kamera als primären Sensor verwenden, sollten wir in der Lage sein, überlappende Merkmale der von der Kamera aufgenommenen Stereo-Bilder zu finden. Diese identischen Merkmale können dann verwendet werden, um den Abstand zum Sensor zu schätzen. Zuvor müssen wir jedoch, wie bereits erwähnt, gemeinsame Merkmale auf dem Stereo-Bildpaar identifizieren. Das geschieht mit Funktionen wie Detektoren und Matchern. Einige der gängigen Beispiele für Merkmalsdetektoren sind Scale-Invariant Feature Transform (SIFT), Oriented FAST und Rotated BRIEF (ORB) sowie Good Features to Track (GFTT). Abbildung 2 veranschaulicht die Merkmalserkennung mit einigen der gängigen Detektoren. Sobald die Merkmale erkannt wurden, werden sie mit Hilfe derselben Merkmalsdetektoren beschrieben. Das hilft dabei, diese Merkmale in Zukunft leicht wiederzufinden.

Abbildung 2: Mit a) GFTT und b) SIFT erkannte Schlüsselpunkte auf dem Bild des XRP-Roboters (Quelle: SparkFun Electronics)

Nachdem wir die Schlüsselpunkte ermittelt haben, stellen wir eine Korrespondenz zwischen diesen Punkten her, indem wir sie miteinander abgleichen. Einige der nutzbaren Algorithmen zum Merkmalsabgleich sind Brute Force Matcher oder Fast Library for Approximate Nearest Neighbors (FLANN). Abbildung 3 visualisiert den Abgleichsalgorithmus in Aktion. Linien verbinden die Übereinstimmungen und da wir Spiegelbilder verwendet haben, sollten wir im Idealfall nur horizontale (parallele) Linien erhalten, vorausgesetzt, das System ist perfekt. Leider sind die Algorithmen zum Merkmalsabgleich weit davon entfernt, perfekt zu sein, und führen daher zu falschen Übereinstimmungen, von denen einige durch schräge Linien dargestellt sind. Deshalb brauchen wir Werkzeuge zum Ausschluss von Ausreißern (Outlier) wie Random Sample Consensus (RANSAC).

Abbildung 3: Linien verbinden die mit FLANN ermittelten Merkmalsübereinstimmungen auf zwei invertierten Bildern. (Bildquelle: SparkFun Electronics)

RANSAC

Algorithmen wie RANSAC dienen zur Filterung dieser falschen Übereinstimmungen und sollen sicherstellen, dass nur so genannte „Inlier“ (richtige Übereinstimmungen) für die weitere Verarbeitung verwendet werden. Die Funktion von RANSAC besteht darin, ein Modell aus einer zufälligen Teilmenge der bereitgestellten Daten zu erstellen. Das heißt, wir betrachten einige zufällige Punkte als „Inlier“ und versuchen, alle übrigen Punkte auf der Grundlage dieser wenigen ausgewählten Punkte abzugleichen. Anschließend bewerten wir, wie gut das Modell auf den gesamten Datensatz passt. Dieser Prozess wird so lange wiederholt, bis ein Modell gefunden ist, das die Daten mit einem minimalen Fehler beschreibt, der durch eine Kostenfunktion bestimmt wird.

Verknüpfung von Merkmalen und Daten

In diesem Schritt werden die erkannten Merkmale und ihre geschätzte Position im Raum verwendet, um eine Karte dieser Merkmale zu erstellen. Mit Verarbeitung der Folgebilder verknüpft das System neue Merkmale mit bekannten Elementen der Karte und verwirft unsichere Merkmale.

Da die Bewegung der Kamera über aneinander anschließende Bilder verfolgt wird, erlauben die bekannten Merkmale Vorhersagen dazu, wie sie sich mit der Bewegung voraussichtlich verändern. Die Rechenleistung und die zeitlichen Beschränkungen, insbesondere bei Echtzeitanwendungen, setzen SLAM jedoch Grenzen. Da das System immer mehr Messungen zu Merkmalen durchführt und die Position/Pose fortlaufend aktualisiert, ist es unerlässlich, die Darstellung der Umgebung einzuschränken und zu optimieren.

Position, Pose und Kartenaktualisierung

Kalman-Filter

Im weiteren Verlauf des SLAM-Prozesses fällt vermehrt Rauschen an, das eine Unsicherheit zwischen den von der Kamera aufgenommenen Bildern und der damit verbundenen Bewegung verursacht. Durch die fortlaufende Vorhersage, Aktualisierung und Feinabstimmung des Modells anhand der durchgeführten Messungen können Kalman-Filter die Auswirkungen von Rauschen und Unsicherheiten zwischen verschiedenen Messungen verringern. Das hilft bei der Erstellung eines linearen Systemmodells. Für die eigentliche SLAM-Implementierung verwenden wir die erweiterten Kalman-Filter (EKF), die die Vorhersagen und Messungen nichtlinearer Systeme um deren Mittelwert linearisieren. EKF können Daten von mehreren Sensoren durch Sensorfusion (z. B. Kameras, Trägheitsmesseinheiten) integrieren, um die Genauigkeit der Zustands- und Kartierungsschätzungen zu verbessern. Diese Fusion von Datenquellen trägt dazu bei, zuverlässigere SLAM-Ergebnisse zu erzielen. Der Zustandsvektor im EKF-basierten SLAM umfasst die Roboterpose (Position und Ausrichtung) und die Positionen der Landmarken auf der Karte.

Keyframe-Auswahl

Aus den aufgenommenen Bildern werden so genannte Keyframes (Schlüsselbilder) ausgewählt, um den hohen Rechenaufwand für die Verarbeitung aller aufgenommenen Bilder zu reduzieren. Stattdessen wählen wir Bilder aus, die eine gute Darstellung der Umgebung bieten, und verarbeiten nur diese. Auch bei dieser Methode handelt es sich um einen Kompromiss zwischen Genauigkeit und Effizienz.

Fehlerkorrektur durch Schleifenabschluss und Relokalisierung

Mit der fortschreitenden Erstellung eines Umgebungsmodells kommt es zu einer allmählichen Anhäufung von Messfehlern und Sensordriften, die sich auf die erstellte Karte auswirken. Dem kann bis zu einem gewissen Grad durch den Abschluss der Schleife entgegengewirkt werden. Der Abschluss der Schleife erfolgt, wenn das System erkennt, dass es ein zuvor kartiertes Terrain erneut aufsucht. Durch den Abgleich der aktuellen Karte mit der zuvor erstellten Zuordnung desselben Terrains kann das SLAM-System den akkumulierten Fehler korrigieren.

Relokalisierung

Eine Relokalisierung, also eine Neubestimmung der Position, ist erforderlich, wenn das System seine Position und Ausrichtung (POSE) nicht mehr verfolgen kann. Jetzt müssen wir die Pose neu schätzen, indem wir die derzeit beobachtbaren Merkmale verwenden. Sobald das System die aktuell verfügbaren Merkmale erfolgreich mit der verfügbaren Karte abgeglichen hat, können wir mit dem SLAM-Prozess wie gewohnt fortfahren.

Fazit

SLAM ist die Schätzung der Position eines Roboterfahrzeugs bei gleichzeitiger Kartierung eines unbekannten Terrains. Zu den SLAM-Verfahren gehören filterbasierte, grafikbasierte und tiefenlernbasierte Methoden (unter Verwendung neuronaler Netzwerke). Visuelles SLAM setzt Kameras ein, um Bilder aufzunehmen, Merkmale zu extrahieren, diese abzugleichen und falsche Übereinstimmungen herauszufiltern. Das System erstellt eine Karte, indem es neue Merkmale mit bekannten Elementen verknüpft, die Position und Pose des Roboters mit Hilfe von Kalman-Filtern aktualisiert, Keyframes auswählt und Fehler durch den Abschluss einer Schleife und erneute Bestimmung der Position korrigiert.

Referenzen

1. Remote Sensing | Free Full-Text | SLAM Overview: From Single Sensor to Heterogeneous Fusion (mdpi.com)
2. Understanding how V-SLAM (Visual SLAM) works | Kudan global
3. Feature-based visual simultaneous localization and mapping: a survey | Discover Applied Sciences (springer.com)
4. Introduction to Visual SLAM: Chapter 1 —Introduction to SLAM | by Daniel Casado | Medium
5. Eine Einführung in die wichtigsten Algorithmen für SLAM - Technische Artikel (control.com)
6. Was ist SLAM (Simultane Lokalisierung und Kartierung) - MATLAB & Simulink (mathworks.com)
7. A survey of state-of-the-art on visual SLAM - ScienceDirect