Wissenschaft & Ideen · Erfindungen & Technik

Der Algorithmus, der die meisten Daten einfach wegwirft

RANSAC ist ein Verfahren, das aus einer Menge von Messwerten mit vielen Ausreißern trotzdem ein passendes Modell herausrechnet – etwa eine Gerade, die durch Punkte gelegt werden soll. Klassische Ausgleichsverfahren wie die kleinste-Quadrate-Methode scheitern, sobald zu viele grobe Fehler in den Daten stecken, weil ein einziger falsch liegender Punkt das Ergebnis stark verzerren kann. Fischler und Bolles stellten den Algorithmus 1981 vor, entwickelt hatten sie ihn im Umfeld automatischer Bildauswertung, wo solche Ausreißer durch fehlerhafte Messtechnik häufig vorkommen. Die Idee dahinter ist denkbar einfach: Man wählt wiederholt zufällig nur so viele Punkte aus, wie zur Berechnung des Modells nötig sind, prüft dann, wie viele der übrigen Punkte zu diesem Modell passen, und behält am Ende das Modell, das von den meisten Punkten unterstützt wird.

Eingesetzt wird RANSAC vor allem in der Computer Vision, etwa um einander entsprechende Punkte in zwei Kamerabildern zuzuordnen, Panoramen aus Einzelfotos zusammenzusetzen oder die geometrische Beziehung zwischen mehreren Aufnahmen desselben Objekts zu berechnen. Auch bei autonomen Fahrzeugen, etwa im DARPA-Wettbewerb für selbstfahrende Autos, half der Algorithmus dabei, aus verrauschten Sensordaten die Fahrbahnebene zu bestimmen. In dreidimensionalen Punktwolken lassen sich mit ihm zudem geometrische Körper wie Zylinder erkennen und einzelne Objekte nacheinander herausrechnen. Wie gut das gelingt, hängt stark von drei Stellschrauben ab: dem erlaubten Abstand eines Punktes vom Modell, der Anzahl der Wiederholungen und der Mindestgröße der als stimmig erkannten Punktmenge. Besonders die Fehlerschranke ist heikel, denn wird sie zu groß oder zu klein gewählt, liefert der Algorithmus im einen Fall zu nachsichtige, im anderen zu wenig unterstützte Modelle – meist muss sie daher experimentell festgelegt werden. Ist der Ausreißeranteil vorab unbekannt, lässt sich der Algorithmus auch adaptiv starten und passt seine Parameter während der Iterationen laufend an.

Weil in der Praxis oft mehr Durchläufe nötig sind als die Theorie vorhersagt, wurden Weiterentwicklungen vorgeschlagen. LO-RANSAC verfeinert das gefundene Modell noch einmal mit einem klassischen Ausgleichsverfahren, bevor die endgültige Punktmenge bestimmt wird, weil sonst eigentlich passende Punkte fälschlich als Ausreißer gelten können. MSAC wiederum ändert die Bewertungsfunktion: Statt Punkte innerhalb der Fehlerschranke pauschal mit null zu gewichten, geht ihr tatsächlicher Fehler in die Rechnung ein, was die Lösung robuster gegenüber einer zu großzügig gewählten Schranke macht. Als Alternative zum gesamten RANSAC-Ansatz nennt der Artikel sogenannte M-Schätzer, die ebenfalls widerstandsfähig gegenüber Ausreißern sind. Insgesamt zeigt sich RANSAC als vielseitig anpassbares Werkzeug, dessen praktischer Erfolg stark von der richtigen Wahl seiner wenigen, aber entscheidenden Parameter abhängt.

Veröffentlicht wurde RANSAC 1981 von Martin A. Fischler und Robert C. Bolles – intern gezeigt hatten sie ihn am SRI International aber schon im März 1980.

Den ganzen Artikel „RANSAC-Algorithmus“ auf Wikipedia lesen

Der Artikel stammt aus der Wikipedia und steht unter CC BY-SA 4.0. Die Einleitung oben ist unsere eigene.