RANSAC-Algorithmus
-
Hallo,
ich habe leider etwas Probleme, den RANSAC-Algorithmus zu verstehen und umzusetzen. Vielleicht kann mir ja hier jemand ein wenig auf die Sprünge helfen.
Ich habe eine Menge von 2D-Vektoren, die sich zum Beispiel in einem 2D-Koordinatensystem gut darstellen lassen. Schaut man sich den Plot dieser Vektoren an, so sieht man immer an einer bestimmten Stelle eine deutliche Häufung, die man als normalverteilt um einen bestimmten Mittelpunkt mit einer gewissen Standardabweichung ansehen kann. Zusätzlich habe ich aber eine Menge Ausreißer.
Der RANSAC-Algorithmus sollte hier genau der richtige Ansatz sein, um die Ausreißer zu eliminieren und die Parameter für Mittelwert und Standardabweichung ohne die Ausreißer zu berechnen.
Der Pseudocode unter http://de.wikipedia.org/wiki/RANSAC-Algorithmus spricht hier nun von Modell, welches ich aus einer Anzahl zufällig gewählter Punkte berechnen soll. Leider verstehe ich nicht, wie ich den Algorithmus auf mein Problem anwenden könnte.
Kann mir da vielleicht jemand auf die Sprünge helfen? Welches Modell soll ich berechnen? Wieviele Punkte wähle ich in jedem Schritt? Soll ich zwei Punkte wählen, für diese dann Mittelwert und Standardabweichung berechnen? Aber wie dann weiter? Ich steh hier irgendwie gerade auf dem Schlauch.
Viele Grüße, mbu.
-
Wenn ich den Text in der Wikipedia richtig verstanden habe, ist mit "Modell" die Kurve gemeint, auf der deine Punkte landen sollten. (zum Beispiel kannst du jeweils 2 Punkte auswählen und eine Gerade durch diese beiden Punkte als Grundlage verwenden)
In deinem Beispiel wäre das "Modell" wohl ein Kreis, der am Ende um deinen Häufungspunkt herum liegt (wobei ich nicht sicher bin, ob das Verfahren für deine Zwecke überhaupt geeignet ist).
-
Kurze Rückmeldung: Nach einigen Stunden Arbeit hab ich es jetzt hinbekommen. Jippie.
Der Algorithmus funktioniert. Unter http://de.wikipedia.org/wiki/RANSAC-Algorithmus#Anwendungen steht ja auch, dass der Algorithmus genau hier eine Anwendung findet:
RANSAC wird auch dazu benutzt, in verrauschten dreidimensionalen Punktmengen [...] automatisch Punktewolken zu segmentieren.
Das Problem hierbei war, dass der Pseudocode im deutschen Wikipedia-Eintrag etwas verwirrend war. Meiner Meinung nach fehlt da soger ein kleiner, aber wichtiger Punkt. Die Implementierung nach der englischen Version unter http://en.wikipedia.org/wiki/RANSAC#The_algorithm hat's dann tatsächlich gebracht.
Viele Grüße, mbu.