„RANSAC-Algorithmus“ – Versionsunterschied

RANSAC (Random Sample Consensus, deutsch etwa „Übereinstimmung mit einer zufälligen Stichprobe“) ist ein Algorithmus zur Detektion von Ausreißern und groben Fehlern innerhalb einer Reihe von Messwerten. Er wurde offiziell 1981 von Martin A. Fischler und Robert C. Bolles in den Communications of the ACM vorgestellt. Eine interne Präsentation (beide Autoren arbeiten bis heute am Stanford Research Institute) fand bereits im März 1980 statt.

Einleitung und Prinzip

Oft liegen als Ergebnis einer Messung Datenpunkte vor, die physikalische Messwerte wie Druck, Entfernung oder Temperatur, wirtschaftliche Größen oder Ähnliches repräsentieren. In diese Punkte soll eine möglichst genau passende, parameterabhängige Modellkurve gelegt werden. Die gemessenen Datenpunkte können Ausreißer enthalten. Das sind diejenigen Werte, die nicht in die erwartete Messreihe passen oder allgemein nicht den Erwartungswert entsprechen.

Messungen wurden bis zur Entwicklung der Digitaltechnologie im Allgemeinen manuell durchgeführt. Entsprechend war oft auf Grund des Aufwandes die Anzahl der Messwerte klein. Gleichzeitig war aber durch die Kontrolle durch den Operateur der prozentuale Anteil der Ausreißer meist gering. Die damals verwendeten Auswertealgorithmen wie die Methode der kleinsten Quadrate sind darauf angepasst: sie versuchen, mit der Gesamtheit der Datenpunkte das Modell zu bestimmen und im Nachhinein die wenigen Ausreißern zu detektieren und zu entfernen. Voraussetzung all dieser Verfahren ist, dass mehr Datenpunkte vorliegen als zur Ermittlung der Parameter notwendig sind, das Modell also überbestimmt ist.

Ausreißer:
Der eine Ausreißer zieht die Ausgleichsgerade nach oben

Mit der Entwicklung der Digitaltechnik ab Anfang der 1980er Jahre (so stellten zum Beispiel im Jahre 1981 IBM den ersten Personal Computer, Apple den Apple III und Sony mit der Mavica die erste Digitalkamera vor) änderten sich jedoch die Grundlagen. Durch die neuen Möglichkeiten wurden zunehmend automatische Messverfahren vor allem im Bereich des maschinellen Sehens eingesetzt. Als Ergebnis liegen hier oft eine große Anzahl an Werten vor, die jedoch meist viele Ausreißern enthalten. Die traditionellen Verfahren gehen jedoch von einer Normalverteilung der Messwerte aus und liefern zum Teil kein sinnvolles Ergebnis, wenn die Datenpunkte viele Ausreißer enthalten. Dies ist in nebenstehender Darstellung illustriert. Es soll eine Gerade (das Modell) an die Punkte (Messwerte) angepasst werden. Der einzelne Ausreißer unter den 20 Datenpunkten kann einerseits durch traditionelle Verfahren vor Bestimmung der Gerade nicht ausgeschlossen werden. Andererseits beeinflusst er auf Grund seiner Lage die Ausgleichgsgerade unverhältnismäßig groß (sogenannter Hebelpunkt). Die vorhandenen Algorithmen konnten somit bei automatisch durchgeführten Messungen nur begrenzt eingesetzt werden.

Der 1981 präsentierte RANSAC-Algorithmus verfolgt gegenüber den herkömmlichen Methoden einen neuen iterativen Ansatz. Anstelle alle Messwerte gemeinsam auszugleichen, werden lediglich so viele zufällig ausgewählte Messwerte benutzt, wie nötig sind, die Modellparameter zu berechnen (im Fall der Geraden rechts wären das zwei Punkte). Das geschieht in der Hoffnung, das die ausgewählten Werte frei von Ausreißern sind. Zur Überprüfung wird die Distanz jedes Messwertes (also nicht nur der ursprünglich ausgewählten) zum Modell berechnet. Ist diese kleiner als ein bestimmter Schwellwert, dann ist dieser Messwert in Bezug auf das Modell kein grober Fehler. Er unterstützt es somit. Je mehr Messwerte das Modell unterstützen, desto wahrscheinlicher enthielten die zufällig zur Modellberechnung ausgewählten Werte keine Ausreißer.

Diese drei Schritte – zufällige Auswahl von Messwerten, Berechnung der Modellparameter und Bestimmung der Unterstützung – werden mehrmals wiederholt. In jeder Iteration wird gespeichert, welche Messwerte das jeweilige Modell unterstützen. Diese Menge wird Consensus set genannt. Aus dem größten Consensus set, der im Idealfall keine Ausreißer mehr enthält, wird abschließend mit einem der traditionellen Ausgleichsverfahren die Lösung ermittelt.

Anwendungen

Wie erwähnt treten viele Ausreißer vor allem bei automatischen Messungen auf. Diese werden häufig im Bereich des Maschinellen Sehens durchgeführt, so dass RANSAC vor allem hier weit verbreitet ist. Im Folgenden werden einige Anwendungen vorgestellt.

Panoramabild von Alcatraz

In der Bildverarbeitung wird RANSAC bei der Bestimmung von homologen Punkten zwischen zwei Kamerabildern eingesetzt. Homolog sind die zwei Bildpunkte, die ein einzelner Objektpunkt in den beiden Bildern erzeugt. Die Zuordnung homologer Punkte wird Korrespondenzproblem genannt. Das Resultat einer automatischen Analyse enthält meist eine größere Anzahl Fehlzuordnungen. Verfahren, die auf dem Ergebnis der Korrespondenzanalyse aufsetzen, benutzen dann RANSAC, um die Fehlzuordnungen auszuschließen. Ein Beispiel für diese Vorgehensweise ist die Erstellung eines Panoramabildes aus verschiedenen kleineren Einzelaufnahmen (sogenanntes Stitching). Ein weiteres ist die Berechnung der Epipolargeometrie. Das ist ein Modell aus der Geometrie, das die geometrischen Beziehungen zwischen verschiedenen Kamerabildern des gleichen Objekts darstellt. Hier dient RANSAC zur Bestimmung der mathematischen Beschreibung, Fundamentalmatrix genannt.

Bei der DARPA Grand Challenge, einem Wettbewerb für autonome Landfahrzeuge, wurde RANSAC dazu benutzt, die Fahrbahnebene zu bestimmen sowie die Bewegung des Fahrzeuges zu rekonstruieren.

Der Algorithmus wird auch dazu verwand, in verrauschten dreidimensionalen Punktmengen geometrische Körper wie Zylinder oder ähnliches anzupassen oder automatisch Punktewolken zu segmentieren. Dabei werden alle Punkte, die nicht zum selben Segment gehören, als Ausreißer betrachtet. Nach einer Schätzung des dominantesten Körpers in der Punktwolke werden alle zu diesem Körper gehörenden Punkte entfernt. Dieser Vorgang wird solange wiederholt, bis alle Körper in der Punktmenge gefunden wurden.

Vorgehensweise und Parameter

Voraussetzung für RANSAC ist, dass mehr Datenpunkte vorliegen, als zur Bestimmung der Modellparameter notwendig sind. Der Algorithmus besteht aus folgenden Schritten:

1. Wähle zufällig so viele Punkte aus den Datenpunkten, wie nötig sind, die Parameter des Modells zu berechnen. Das geschieht in Erwartung, dass diese Menge frei von Ausreißern ist.
2. Ermittle mit den gewählten Punkten die Modellparameter.
3. Bestimme die Teilmenge Messwerte, deren Abstand zur Modellkurve kleiner als ein bestimmter Grenzwert ist (diese Teilmenge wird „Consensus set“ genannt). Alle Punkte, die einen größeren Abstand haben, werden als grobe Fehler angesehen. Enthält die Teilmenge eine gewisse Modestanzahl an Werten, wurde vermutlich ein gutes Modell gefunden und der Consensus set gespeichert.
4. Wiederhole die Schritte 1–3 mehrmals.

Nach Durchführung von mehreren Iterationen wird diejenige Teilmenge gewählt, welche die meisten Punkte enthält (so denn eine gefunden wurde). Nur mit diesen werden mit einem der üblichen Ausgleichsverfahren die Modellparameter berechnet. Eine alternative Variante des Algorithmus beendet die Iterationen vorzeitig, wenn im Schritt 3 genügend Punkte das Modell unterstützen. Diese Variante wird als präemptives – das heißt vorzeitig abbrechendes – RANSAC bezeichnet. Bei diesem Vorgehen muss im Vorfeld bekannt sein, wie groß in etwa der Ausreißeranteil ist, damit eingeschätzt werden kann, ob genügend Messwerte das Model unterstützen.

Der Algorithmus hängt im Wesentlichen von drei Parametern ab:

1. der Größe des Consensus set, also der Mindestanzahl der mit dem Modell konsistenten Punkte, die keine groben Fehler sind und die andeuten, dass ein gutes Modell gefunden wurde,
2. den maximaler Abstand eines Datenpunkts vom Modell, um nicht als grober Fehler zu gelten und
3. der Anzahl der Iterationen.

Größe des Consensus set

Die Mindestgröße des Consensus set wird meist analytisch oder experimentell bestimmt. Eine gute Näherung ist die Gesamtmenge der Messwerte abzüglich des prozentualen Anteils an Ausreißern $\epsilon$, der in den Daten vermutet wird. Für $n$ Datenpunkte ist die Mindestgröße gleich $(1-\epsilon )\cdot n$. Beispielsweise ist bei 12 Datenpunkten und 20 % Ausreißern die Mindestgröße näherungsweise 10.

Maximaler Abstand eines Datenpunkts vom Modell

Auch diese Größe wird im Allgemeinen empirisch festgelegt. Unterliegt der Messfehler jedoch einer mittelwertfreien Normalverteilung mit einer bekannten Standardabweichung, kann die Fehlergrenze mittels den Gesetzen der Wahrscheinlichkeitsverteilung berechnet werden.

Anzahl der Iterationen

Die Anzahl von Wiederholungen kann so festgelegt werden, dass mit einer bestimmten Wahrscheinlichkeit $p$ mindestens einmal eine ausreißerfreie Teilmenge aus den Datenpunkten gezogen wird. Ist $s$ die Anzahl der Datenpunkte, die zur Berechnung eines gültigen Modells notwendig sind und $\epsilon$ der Anteil an Ausreißern in den Daten, werden mindestens

${\frac {\log(1-p)}{\log(1-(1-\epsilon )^{s})}}$

Wiederholungen benötigt.

In nachstehender Tabelle ist die notwendige Anzahl von Wiederholungen bei einer bestimmten Anzahl von Datenpunkten und Ausreißeranteil dargestellt. Die Wahrscheinlichkeit, eine ausreißerfreie Teilmenge aus allen Datenpunkten auszuwählen, ist dabei mit 99 % festgelegt.

Beispiel	Anzahl der Datenpunkte	Ausreißeranteil
		10 %	20 %	30 %	40 %	50 %	60 %	70 %
Linie	2	3	5	7	11	17	27	49
Fläche	3	4	7	11	19	35	70	169
Fundamentalmatrix	8	9	26	78	272	1177	7025	70188

Adaptive Bestimmung der Parameter

Der Anteil der Ausreißern an der Gesamtmenge der Datenpunkte ist oft unbekannt. Somit ist es nicht möglich, die benötigte Zahl der Iterationen und die Mindestgröße eines Consensus set zu bestimmen. In diesem Fall wird der Algorithmus mit der Worst-Case-Annahme eines Ausreißeranteils von beispielsweise 50 % initialisiert und die Zahl der Iterationen und die Größe des Consensus set entsprechend berechnet. Nach jeder Iteration werden die beiden Werte angepasst, wenn eine größere konsistente Menge gefunden wurde. Wird zum Beispiel der Algorithmus mit einem Ausreißeranteil von 50 % gestartet und enthält der berechnete Consensus set aber 80 % aller Datenpunkte, ergibt sich ein verbesserter Wert für den Ausreißeranteil von 20 %. Die Zahl der Iterationen und die Größe des Consensus set werden dann neu berechnet.

Beispiel

An eine Menge von Punkten in der Ebene soll eine Gerade angepasst werden. Die Punkte sind im ersten Bild dargestellt. Es werden in jeder Iteration zufällig zwei Punkte ausgesucht und aus diesen eine Gerade berechnet. Im Bild 2 ist diese bei verschiedenen Durchgängen eingezeichnet. Rote Punkte sind zu der Gerade passende Punkte (Inliers) und blaue Punkte diejenigen, deren Abstand zur Gerade größer ist als die Fehlerschranke. Das dritte Bild zeigt die Lösung nach 1000 Iterationsschritten.

• RANSAC zum Anpassen einer Geraden an Datenpunkte
• 
  1. Original-Datensatz.
• 
  2. Animation mehrerer Iterationen.
• 
  3. Ergebnis nach 1000 Iterationen.

Weiterentwicklungen

Es existieren einige Erweiterungen von RANSAC, von denen hier zwei wichtige vorgestellt werden.

LO-RANSAC

Modellgerade wird nicht durch alle Inlier unterstützt.

Es hat sich in Experimenten gezeigt, dass im Allgemeinen mehr Iterationsschritte als die theoretisch ausreichende Anzahl nötig sind: wird mit einer fehlerfreien Menge von Punkten ein Modell berechnet, so müssen nicht alle anderen fehlerfreien Werte dieses Modell unterstützen. Das Problem ist in nebenstehender Abbildung illustriert. Obwohl die Gerade mittels zweier fehlerfreier Werte berechnet wurde (schwarze Punkte), werden einige andere offensichtlich richtige Punkte rechts oben im Bild als Ausreißer (blaue Sterne) klassifiziert.

Aus diesem Grund wird der ursprüngliche Algorithmus bei LO-RANSAC (local optimised RANSAC) im Schritt 3 erweitert. Es wird die Teilmenge der Punkte bestimmt, die keine Ausreißer sind, und mit diesen eine Optimierung durchgeführt. Von diesem optimierten Modell wird nochmals die Teilmenge berechnet, deren Abstand zum Modell kleiner als die Fehlerschranke ist. Erst diese wird gespeichert.

MSAC

Bei RANSAC wird das Modell ausgewählt, welches durch die meisten Messwerte unterstützt wird. Dies entspricht der Minimierung einer Summe $C$, bei der alle fehlerfreien Werte mit 0 und alle Ausreißer mit einem konstanten Wert eingehen:

$C=\sum _{i}p({\text{Fehler}})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}0,{\text{wenn}}&{\text{Fehler}}<{\text{Fehlerschranke}}\\{\text{konstant, wenn}}&{\text{Fehler}}\geq {\text{Fehlerschranke}}\end{array}}\right.$

Das berechnete Modell kann sehr ungenau sein kann, wenn die Fehlerschranke zu hoch angesetzt wurde – je höher diese ist, desto mehr Lösungen haben gleiche Werte für $C$. Im Extremfall, wenn alle Werte einen Fehler kleiner als die Fehlerschranke besitzen, ist die Summe immer 0. Damit tendiert RANSAC zu einer schlechten Schätzung.

MSAC (M-Estimator SAmple Consensus) ist eine Erweiterung von RANSAC. Dabei wird nicht nur die Zahl der fehlerfreien Messwerte maximiert, sondern deren Fehler mit in die Berechnung mit einbezogen. Dazu wird eine neue Minimierungsfunktion definiert:

$C=\sum _{i}p({\text{Fehler}})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}{\text{Fehler, wenn}}&{\text{Fehler}}<{\text{Fehlerschranke}}\\{\text{konstant, wenn}}&{\text{Fehler}}\geq {\text{Fehlerschranke}}\end{array}}\right.$

Mit dieser Funktion erhalten Ausreißer eine bestimmte Strafe (die größer als die Fehlerschranke sein muss). Fehlerfreie Werte werden jetzt danach gewichtet, wie gut sie zu den Messwerten passen. Dadurch wird das angesprochene Problem beseitigt.

Alternativen

Eine Alternative zu RANSAC ist die Verwendung von M-Schätzern. Diese sind im Vergleich zu anderen Schätzern wie etwa den Maximum-Likelihood-Schätzern robuster gegenüber Ausreißern.

Literatur

• Martin A. Fischler und Robert C. Bolles: Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. 1981, abgerufen am 11. März 2008. 
• Verschiedene Autoren: 25 Years of RANSAC, Workshop in conjunction with CVPR 2006. 2006, abgerufen am 11. März 2008. 
• Peter Kovesi: RANSAC – Robustly fits a model to data with the RANSAC algorithm (Matlab-Implementation). 2007, abgerufen am 11. März 2008. 
• Richard Hartley and Andrew Zisserman: Multiple View Geometry in computer vision. Cambridge University Press, Cambridge 2003, ISBN 0-521-54051-8. 
• Volker Rodehorst: Photogrammetrische 3D-Rekonstruktion. Wissenschaftlicher Verlag Berlin, Berlin 2004, ISBN 3-936846-83-9.