RANSAC-Algorithmus

RANSAC (Random Sample Consensus, deutsch etwa Korrespondenzen von Zufallspunkten) ist ein mathematischer Algorithmus zur Detektion von Ausreißern beziehungsweise groben Fehlern innerhalb einer Menge von Datenpunkten. Er wurde 1981 von Martin A. Fischler und Robert C. Bolles vorgestellt.

Einleitung

Ausreißer:
Der Ausreißer zieht die Gerade nach oben

Oft liegen als Ergebnis einer Messung Datenpunkte vor, die physikalische Messwerte, 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 Erwartungen entsprechen.

Zum Anpassen der Modellkurve an die Datenpunkte dient zum Beispiel die Methode der kleinsten Quadrate. Dieses und andere Verfahren gehen von einer Normalverteilung der Messwerte aus und liefern zum Teil kein sinnvolles Ergebnis, wenn die Datenpunkte viele Ausreißer enthalten. Zusätzlich haben Außreißer meist einen überdurchschnittlich großen Einfluss auf die Modellparameter. Man erkennt in nebenstehender Zeichnung, wie ein einzelner Ausreißer unter 20 Datenpunkten die Lage der Ausgleichgsgerade beeinflusst. Mittels RANSAC können die Ausreißer detektiert werden. Somit ist es möglich, diese bei der Berechnung der Modellparameter auszuschließen und trotz vieler Fehler in den Daten ein richtiges Ergebnis zu erhalten.

Vorgehensweise

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

1. Wähle zufällig so viele Punkte aus den Datenpunkten, wie nötig sind, die Modellkurve 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 S der Datenpunkte, deren Abstand zur Modellkurve kleiner als ein bestimmter Wert d ist (diese Teilmenge wird „Consensus set“ genannt). Alle Punkte, die einen größeren Abstand haben, werden für dieses Modell als grobe Fehler angesehen und sind nicht in der Teilmenge enthalten. Sind ausreichend Punkte in der Teilmenge, speichere diese.
4. Wiederhole die Schritte 1–3 N mal.

Nach Durchführung der N Iterationen wählt man diejenige Teilmenge S, welche die meisten Punkte enthält (so denn eine gefunden wurde). Nur mit diesen berechnet man mit den üblichen Verfahren die Modellparameter.

Eine alternative Variante des Algorithmus prüft in Schritt 3 zusätzlich die Anzahl der Punkte im Consensus set. Sind es hinreichend viele, terminiert der Algorithmus und das Modell wird mit den gewählten Punkten berechnet. Diese Variante wird als präemptives – das heisst vorzeitig abbrechendes – RANSAC bezeichnet. Bei diesem Vorgehen muss im Vorfeld bekannt sein, wie groß der Ausreißeranteil etwa ist.

Pseudocode

Eingabe:

   r - Die benötigte Anzahl von Punkten, um die Parameter eines Modelles zu berechnen
   P - Eine Menge von Datenpunkten mit |P|>r
   N - Die Anzahl der Iterationen
   t - Die minimale Anzahl von passenden Punkte, die andeutet, dass ein gutes Modell gefunden wurde
   d - Fehlertoleranz zur Bestimmung, ob ein Punkt zum Modell passt. 

Ausgabe

   Parameter des Modells, welches am besten zu den Datenpunkten passt, oder false. 

Ablauf

   Wiederhole, bis N Iterationen durchgeführt wurden
       Ziehe eine Teilmenge $S_{1}$ aus P mit $|S_{1}|$=r
       Berechne mit $S_{1}$ das Modell, benenne es $M_{1}$
       Benutze $M_{1}$, um eine Teilmenge $S_{\text{N}}^{*}$ von P zu bestimmen, deren Punkte einen kleineren 
        Abstand von $M_{1}$ als d haben ($S_{1}^{*}$ wird consensus set von $S_{1}$ genannt)
       Speichere $S_{\text{N}}^{*}$, wenn $|S_{\text{N}}^{*}|$>t
   Ende
   Wenn mindestens ein $S_{\text{N}}^{*}$ gespeichert wurde, benutze das $S_{\text{N}}^{*}$ mit dem meisten Punkten und 
    berechne damit das Modell oder terminiere mit false.

Parameter

Der RANSAC-Algoritmus hängt im wesentlichen von drei Parametern ab:

1. der Größe des Consensus set t (Mindestanzahl der passenden Punkte, die keine groben Fehler sind und die andeuten, dass ein gutes Modell gefunden wurde),
2. der Fehlergrenze d (maximaler Abstand eines Datenpunkts vom Modell, um nicht als grober Fehler zu gelten) und
3. der Anzahl N der Iterationen.

Größe des Consensus set

Die Größe des Consensus set t wird meist analytisch oder experimentell bestimmt. Sie spielt dann eine entscheidende Rolle, wenn die im Abschnitt Vorgehensweise dargestellte Variante benutzt wird, also bei entsprechenden Größe des Consensus set abgebrochen wird. Eine gute Näherung für t ist, den prozentualen Anteil von Ausreißer ε zu nutzen, der in den Daten vermutet wird. Für n Datenpunkte gilt dann t=(1-ε)·n. Bei 12 Datenpunkten und 20% Ausreißern ist t=10.

Fehlergrenze

Auch diese Größe wird im Allgemeinen empirisch festgelegt. Unterliegt der Messfehler jedoch einer mittelwertfreien Normalverteilung mit der Standardabweichung σ, kann man die Fehlergrenze d berechnen. In diesem Fall ist das Quadrat des Punktabstandes eine Summe von quadrierten normalverteilten Variablen und unterliegt einer Chi-Quadrat-Verteilung mit m Freiheitsgraden. m ist dabei die Kodimension des Modells. Für eine Linie ist die Kodimension 1, da nur der senkrechte Abstand zur Linie gemessen wird. Ist das Modell ein Punkt, so ist die Kodimension 2, und das Quadrat der Distanz ist die Summe des quadrierten Abstandes in x- und y-Richtung. Soll nun ein Punkt mit einer Wahrscheinlichkeit α kein Ausreißer sein, so ergibt sich für d

$d^{2}=F_{m}^{-1}(\alpha )\sigma ^{2}$.

F ist dabei die kumulierte Chi-Quadrat-Verteilung: $F_{m}(k^{2})=\int _{0}^{k^{2}}\chi _{m}^{2}(\xi )d\xi$.

Anzahl der Iterationen

Man kann die Anzahl von Wiederholungen N so festlegen, dass mit der Wahrscheinlichkeit p mindestens einmal eine ausreißerfreie Teilmenge aus der Gesamtzahl der Datenpunkte s gezogen wird. Bezeichnet man mit ε den Anteil an Ausreißern in den Daten, benötigt man mindestens

${\text{N}}={\frac {\log(1-p)}{\log(1-(1-\epsilon )^{s})}}$ Wiederholungen.

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 p=99% festgelegt.

Anzahl der Datenpunkte	Ausreißeranteil
	5%	10%	20%	25%	30%	40%	50%
2	2	3	5	6	7	11	17
3	3	4	7	9	11	19	35
4	3	5	9	13	17	34	72
6	4	7	16	24	37	97	239
8	5	9	26	44	78	272	1177

Adaptive Bestimmung der Parameter

Der Anteil an Ausreißern in der Gesamtmenge der Datenpunkte ist oft unbekannt. Somit ist es nicht möglich, die benötigte Zahl der Iterationen N und die Größe des Consensus set t zu bestimmen. In diesem Fall wird der Algorithmus mit der Worst-Case-Annahme eines Ausreißeranteils von 50% initialisiert. Nach jeder Iteration passt man dann diesen Wert an, wenn eine größere konsistente Mengen gefunden wurde. Beginnt man zum Beispiel die Iterationen mit einem ε=50% und enthält der damit berechnete Consensus set aber 80% aller Datenpunkte, ergibt sich für die nächste Iteration ein verbessertes ε von 20%. Analog legt man N und t fest. Beide werden unter der Worst-Case-Annahme von ε=50% berechnet und nach jeder Änderung von ε neu bestimmt.

Beispiel

An eine Menge von 2D-Datenpunkte soll eine Gerade angepasst werden. Die Datenpunkte 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 dann 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.

Anwendungen

Häufige Anwendung findet RANSAC in der Bildverarbeitung bei der Berechnung von homologen Punkten zwischen zwei Bildern. Homolog sind zwei Punkte, wenn sie in zwei Bildern jeweils den gleichen Objektpunkt (z.B. die gleiche Hausecke) darstellen (sogenanntes Korrespondenzproblem). Zum Finden von homologen Punkten werden häufig automatische Verfahren eingesetzt, die im Allgemeinen viele Ausreißer produzieren. Hier dient RANSAC als Lösung, um diese auszufiltern. Das Ergebnis wird unter anderem dazu verwendet, Fotografien so zu modifizieren, dass ein Gesamtbild daraus zusammengesetzt werden kann (sogenanntes Stitching).

RANSAC wird auch dazu benutzt, in verrauschten dreidimensionalen Punktemengen geometrische Körper wie Zylinder oder ähnliches anzupassen oder automatisch Punktewolken zu segmentieren. Dabei betrachtet man alle Punkte, die nicht zum selben Segment gehören, als Ausreißer. Im ersten Schritt schätzt man zunächst robust den dominantesten Zylinder in der Punktwolke und entfernt alle zu diesem gehörende Punkte. Dieser Vorgang wird solange wiederholt, bis alle Zylinder in der Punktemenge gefunden wurden.

Erweiterung

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

LO-RANSAC

Modellgerade wird nicht durch alle Inliener unterstützt.

Es hat sich in Experimenten gezeigt, dass man mehr Iterationsschritte N als die theoretischen Anzahl benötigt. Der Grund ist folgender: berechnet man mit der minimalen Zahl von Punkten, von denen beide keine Ausreißer sind, ein Modell, so müssen nicht alle Inliener dieses Modell unterstützen (also einen kleineren Abstand als d zum Modell haben). Das Problem ist in nebenstehender Abbildung illustriert. Obwohl die Gerade mittels zweier Inliener 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 d ist. Erst diese wird gespeichert.

MLESAC

Ein Problem von RANSAC ist, dass das berechnete Modell sehr ungenau sein kann, wenn die Fehlerschranke d zu hoch angesetzt wurde. Das wird schon dadurch ersichtlich, dass RANSAC versucht, folgende Kostenfunktion zu minimieren:

$C=\sum _{i}p(e_{1}^{2})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}0&e^{2}<d^{2}\\{\text{konstant}}&e^{2}\geq d^{2}\end{array}}\right.$

(e ist dabei der Fehler des Messpunktes.) Das heisst, Inliener zählen nicht und Ausreißer zählen einen konstanten Wert. Je höher also d ist, desto mehr Lösungen haben gleiche Werte für C, was zu einer schlechten Schätzung tendiert. MLESAC (Maximum Likelihood Estimation SAmple Consensus) ist eine Erweiterung von RANSAC. Dabei wird nicht die nur die Zahl der Inliener maximiert, sondern auch deren Fehler. Dazu wird eine neue Minimierungsfunktion definiert:

$C=\sum _{i}p(e_{1}^{2})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}e^{2}&e^{2}<d^{2}\\d^{2}&e^{2}\geq d^{2}\end{array}}\right.$

Mit dieser Funktion erhalten Ausreißer eine bestimmte Strafe, doch werden Inliener jetzt danach gewichtet, wie gut sie zu den Messwerten passen.

Alternativen

Eine Alternative zu RANSAC sind beispielsweise M-Schätzer. 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 Apphcatlons to Image Analysis and Automated Cartography. Abgerufen am 6. August 2007. 

• Verschiedene Autoren: 25 Years of RANSAC, Workshop in conjunction with CVPR 2006. Abgerufen am 7. August 2007. 

• Peter Kovesi: RANSAC – Robustly fits a model to data with the RANSAC algorithm (Matlab-Implementation). Abgerufen am 6. August 2007. 

• Richard Hartley and Andrew Zisserman: Multiple View Geometry in computer vision. Cambridge University Press, 2003, ISBN 0-521-54051-8. 

• Volker Rodehorst: Photogrammetrische 3D-Rekonstruktion. Wissenschaftlicher Verlag Berlin, 2004, ISBN 3-936846-83-9.