RANSAC

RANSAC é uma abreviatura de "RANdom SAmple Consensus". É um método iterativo para estimar os parâmetros de um modelo matemático .

Dado um modelo que requer um mínimo de n pontos para instanciar seus parametros livres, e um conjunto de pontos P, tal que o numero de pontos em P é maior que n, seleciona randomicamente um subconjunto S1 de n pontos de P e instancia o modelo. Usa-se o modelo instanciado M1 para determinar o subconjunto S1* de pontos em P que estao dentro de um erro tolerável de M1. O conjunto S1* é chamado de conjunto consenso de S1.

Se o número de elementos de S1* é maior que certo limite t, que é função da estimativa do número de erros grosseiros em P, usar S1* para computar (possivelmente com Mínimos Quadrados) um novo modelo M1*.

Se o número de elementos de S1* é menor do que t, seleciona-se randomicamente um novo subconjunto S2 e repete-se o processo acima. Se, após um número predeterminado de tentativas, nenhum conjunto consenso com t ou mais membros tiver sido encontrado, ou soluciona-se o modelo com o maior conjunto consenso, ou termina-se com falha.

Referências

• Martin A. Fischler and Robert C. Bolles. (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography". Comm. of the ACM 24 (6): 381–395. DOI:10.1145/358669.358692.
• David A. Forsyth and Jean Ponce. Computer Vision, a modern approach. [S.l.]: Prentice Hall, 2003. ISBN 0-13-085198-1
• Richard Hartley and Andrew Zisserman. Multiple View Geometry in Computer Vision. 2nd ed. [S.l.]: Cambridge University Press, 2003.
• P.H.S. Torr and D.W. Murray. (1997). "The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix". International Journal of Computer Vision 24 (3): 271–300. DOI:10.1023/A:1007927408552.
• Ondrej Chum. (2005). "Two-View Geometry Estimation by Random Sample and Consensus". PhD Thesis.
• Sunglok Choi, Taemin Kim, and Wonpil Yu. (2009). "Performance Evaluation of RANSAC Family". In Proceedings of the British Machine Vision Conference (BMVC).

Ligações externas

• RANSAC Toolbox for MATLAB. A research (and didactic) oriented toolbox to explore the RANSAC algorithm in MATLAB. It is highly configurable and contains the routines to solve a few relevant estimation problems.
• Implementation in C++ as a generic template.
• RANSAC for Dummies A simple tutorial with many examples that uses the RANSAC Toolbox for MATLAB.
• 25 Years of RANSAC Workshop
• Source code for RANSAC in MATLAB