Open Source Robotics

Eine kuratierte Sammlung hochwertiger Open-Source-Robotikprojekte, Werkzeuge und Software für die Robotik-Community.

RANSAC

  • Auch genannt: Random Sample Consensus
  • Kategorie: Sensing › Perception outputs
  • Schlagwörter: robust-estimation, computer-vision, point-cloud-processing, outlier-rejection, model-fitting

Random Sample Consensus: ein robustes Anpassungsverfahren, das wiederholt ein Modell an kleine zufällige Teilmengen der Daten anpasst und das Modell behält, das mit den meisten Punkten übereinstimmt, wobei Ausreißer ignoriert werden.

Definition

RANSAC (Random Sample Consensus), 1981 von Fischler und Bolles eingeführt, schätzt die Parameter eines Modells aus Daten, die viele Ausreißer enthalten. Eine Anpassung nach der Methode der kleinsten Quadrate nutzt jeden Punkt, sodass wenige grobe Fehler das Ergebnis weit von der Wahrheit wegziehen können. RANSAC wiederholt stattdessen eine einfache Schleife: die minimale Anzahl von Punkten ziehen, die zur Festlegung des Modells nötig ist (zwei für eine Gerade, drei für eine Ebene, eine kleine feste Anzahl für eine Kamerapose oder eine Fundamentalmatrix), das Modell an sie anpassen und zählen, wie viele aller Datenpunkte innerhalb eines Schwellenwerts davon liegen. Diese Punkte sind die Konsensmenge, also die Inlier. Nach einer Anzahl von Iterationen wird das Modell mit der größten Konsensmenge behalten und meist mit der Methode der kleinsten Quadrate an alle seine Inlier neu angepasst.

Die Zahl der Iterationen folgt aus der Wahrscheinlichkeitsrechnung. Ist w der Anteil der Inlier und s die Stichprobengröße, so enthält eine Zufallsstichprobe mit Wahrscheinlichkeit wˢ nur Inlier, sodass die Zahl der Iterationen k, die nötig ist, um mit Konfidenz p mindestens eine saubere Stichprobe zu ziehen, k = log(1 − p) / log(1 − wˢ) beträgt. Sie wächst schnell, wenn der Inlier-Anteil sinkt oder die Stichprobengröße steigt, weshalb minimale Löser, die weniger Punkte brauchen, etwa die Fünf-Punkt-Methode für die relative Pose, im Bereich Computer Vision wichtig sind. Der Inlier-Schwellenwert ist der andere zentrale Parameter: Er sollte zum erwarteten Rauschen echter Inlier passen und muss in den Einheiten des gemessenen Residuums festgelegt werden.

Viele Varianten verbessern die Grundschleife. MSAC und MLESAC bewerten Hypothesen mit einer robusten Kostenfunktion statt mit einer reinen Inlier-Zählung, PROSAC zieht die vielversprechendsten Zuordnungen zuerst, LO-RANSAC verfeinert gute Hypothesen lokal, und adaptive Versionen aktualisieren k, während der Inlier-Anteil geschätzt wird. In der Robotik wird RANSAC für die Segmentierung von Ebenen und Grundformen in Punktwolken, das Filtern von Merkmalszuordnungen in visueller Odometrie und SLAM, die Posenschätzung mit Perspective-n-Point, die Registrierung von Punktwolken aus Merkmalskorrespondenzen und die Kalibrierung eingesetzt. Weil das Verfahren zufällig ist, können sich die Ergebnisse zwischen Läufen unterscheiden, sofern der Zufallsstartwert nicht festgelegt ist.

Warum es wichtig ist

Echte Sensordaten sind voller Ausreißer: falsche Merkmalszuordnungen, Reflexionen, bewegte Objekte und Punkte, die zu anderen Oberflächen gehören. RANSAC ist der Standardweg, geometrische Modelle trotz ihnen anzupassen, und steckt in den meisten Pipelines für visuelle Odometrie, SLAM, Kalibrierung und Punktwolkensegmentierung.

Wichtige Anwendungen

  • Segmentierung von Ebenen, Zylindern und Kugeln in Punktwolken
  • Ausreißerunterdrückung bei Merkmalszuordnungen in visueller Odometrie und SLAM
  • Kameraposenschätzung mit Perspective-n-Point
  • Schätzung von Fundamental-, Essential- und Homographiematrizen
  • Globale Punktwolkenregistrierung aus Merkmalskorrespondenzen
  • Anpassung von Geraden und Kalibriermodellen an verrauschte Sensordaten

In der Praxis

Ein mobiler Manipulator muss in einer Punktwolke einer Tiefenkamera eine Tischplatte finden, bevor er Objekte ablegt. Die Software dünnt die Punktwolke aus und führt eine RANSAC-Ebenenanpassung durch: Sie wählt wiederholt drei Punkte, berechnet die Ebene durch sie und zählt die Punkte innerhalb eines Abstandsschwellenwerts, der etwas über dem Tiefenrauschen des Sensors liegt. Die Ebene mit den meisten Inliern wird mit der Methode der kleinsten Quadrate neu angepasst, ihre Inlier werden entfernt, und die verbleibenden Punkte oberhalb von ihr werden zu Objekten geclustert. Die Ingenieure prüfen, dass die Normale der Ebene ungefähr nach oben zeigt, weil RANSAC bei einer großen Wand oder einem großen Boden im Sichtfeld stattdessen diese Fläche liefern kann, und sie legen in Tests den Zufallsstartwert fest, damit die Ergebnisse reproduzierbar sind.

Häufige Missverständnisse

  • RANSAC findet das optimale Modell — es liefert die beste Hypothese, die es zufällig gezogen hat, sodass die Ergebnisse probabilistisch sind und sich zwischen Läufen unterscheiden können
  • Mehr Iterationen gleichen einen schlechten Schwellenwert aus — der Schwellenwert entscheidet, was als Übereinstimmung zählt, und eine schlechte Wahl verzerrt das Ergebnis, ganz gleich, wie viele Iterationen laufen
  • RANSAC kommt mit jedem Ausreißeranteil zurecht — die nötigen Iterationen wachsen rasch, wenn der Inlier-Anteil sinkt, und bei sehr wenigen Inliern kann es scheitern oder sich auf eine Scheinstruktur festlegen
  • RANSAC kann nur ein Modell finden — der Grundalgorithmus findet eines, doch sequenzielle und Mehrmodell-Varianten extrahieren mehrere Strukturen, indem sie Inlier entfernen und wiederholen

Wer das wissen sollte

  • Ingenieure für Wahrnehmung und Computer Vision
  • Entwickler für SLAM und visuelle Odometrie
  • Ingenieure, die Punktwolken für die Manipulation verarbeiten
  • Ingenieure für Kalibrierung und Messtechnik

Verwandte Technologien

  • Anpassung nach der Methode der kleinsten Quadrate (Least-Squares Fitting)
  • M-Schätzer (M-Estimators)
  • MSAC und MLESAC
  • PROSAC
  • Hough-Transformation (Hough Transform)
  • Point Cloud Library

Verwandte Begriffe

  • Point Cloud
  • Perspective-n-Point
  • Visual Odometry
  • Iterative Closest Point
  • Bundle Adjustment
  • Extrinsic Calibration

Verwandte Projekte

  • pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
  • AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
  • MRPT: Comprehensive C++ toolkit for mobile robotics, SLAM, and sensor-based navigation
  • PULP-Dronet: Visual navigation for nano-drones with CNN inference onboard a PULP processor.
  • OpenWeedLocator: Low-cost Raspberry Pi weed detector that uses computer vision for precision spot spraying

Videos

  • RANSAC - 5 Minutes with Cyrill: Cyrill Stachniss
  • Dealing with Outliers: RANSAC | Image Stitching: First Principles of Computer Vision

Diese Website benötigt JavaScript. Bitte aktivieren Sie JavaScript, um unsere Open-Source-Robotikprojekte zu erkunden.