RANSAC-Algorithmus

RANSAC (englisch random sample consensus, deutsch etwa „Übereinstimmung mit einer zufälligen Stichprobe“) ist ein Resampling-Algorithmus zur Schätzung eines Modells innerhalb einer Reihe von Messwerten mit Ausreißern und groben Fehlern. Wegen seiner Robustheit gegenüber Ausreißern wird er vor allem bei der Auswertung automatischer Messungen vornehmlich im Fachgebiet Computer Vision eingesetzt. Hier unterstützt RANSAC – durch Berechnung einer um Ausreißer bereinigten Datenmenge, des sogenannten Consensus Sets – Ausgleichsverfahren wie die Methode der kleinsten Quadrate, die bei einer größeren Anzahl von Ausreißern meist versagen.

RANSAC wurde offiziell 1981 von Martin A. Fischler und Robert C. Bolles in den Communications of the ACM vorgestellt. Eine interne Präsentation am SRI International, an dem beide Autoren arbeiteten,^[1][2] fand bereits im März 1980 statt.^[3] Eine Alternative zu RANSAC sind M-Schätzer. Diese sind im Vergleich zu anderen Schätzern wie etwa den Maximum-Likelihood-Schätzern robuster gegenüber Ausreißern. RANSAC beruht auf wiederholtem zufälligem Subsampling^[4].

1. ↑ Robert C. Bolles: Homepage beim SRI. (online [abgerufen am 11. März 2008]). 
2. ↑ Martin A. Fischler: Homepage beim SRI. (online [abgerufen am 11. März 2008]). 
3. ↑ Martin A. Fischler und Robert C. Bolles: Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. März 1980 (online [PDF; 301 kB; abgerufen am 13. September 2007]). 
4. ↑ Cantzler, H. "Random sample consensus (ransac)." Institute for Perception, Action and Behaviour, Division of Informatics, University of Edinburgh (1981). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3035&rep=rep1&type=pdf