RANSAC
 |
RANSAC é uma abreviatura de "RANdom SAmple Consensus". É um método iterativo para estimar os parâmetros de um modelo matemático.[1][2][3][4][5][6][7]
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.
Exemplo[editar | editar código-fonte]
Como um exemplo simples, podemos considerar a tarefa de regressão linear em duas dimensões de um conjunto de dados. Assumindo que este conjunto contém tanto inliers, isto é, pontos que aproximadamente podem ser ajustados a uma função, e outliers, pontos que não podem ser ajustados a esta função, um método simples de mínimos quadrados resultará em uma função com um ajuste ruim para os dados, visto que o método dos mínimos quadrados procura ajustar uma linha entre todos os pontos sendo inliers ou outliers.
O RANSAC, por outro lado, tenta excluir os outliers e encontrar um modelo que utilize apenas os inliers em seu cálculo. Isso é feito ajustando o modelo a várias amostragens aleatórias dos dados e retornando o modelo que melhor se ajusta a um subconjunto dos dados. Dessa forma, um subconjunto aleatório que consista inteiramente de inliers terá o melhor ajuste do modelo. Entretanto na prática, não há garantia de que um subconjunto totalmente de inliers será amostrado aleatoriamente, e a probabilidade de sucesso do algoritmo depende da proporção de inliers nos dados, bem como da escolha de vários parâmetros do algoritmo.
-
Um conjunto de dados com muitos outliers para os quais uma linha deve ser ajustada. -
regressão linear com RANSAC; outliers não têm influência no resultado.
Ligações externas[editar | editar código-fonte]
- RANSAC Toolbox para MATLAB. Implementação de RANSAC para MATLAB.
- Exemplos de RANSAC em C++.
- RANSAC for Dummies Um tutorial com exemplos em MATLAB.
- 25 Anos de RANSAC
- Código fonte para RANSAC em MATLAB
Referências
- ↑ Martin A. Fischler, Robert C. Bolles (Junho 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography" (inglês). Comm. of the ACM, Vol 24, pp 381-395. Acessado em 18/08/2015.
- ↑ Martin A. Fischler and Robert C. Bolles (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 (2003). Computer Vision, a modern approach. [S.l.]: Prentice Hall. ISBN 0-13-085198-1
- ↑ Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in Computer Vision 2nd ed. [S.l.]: Cambridge University Press
- ↑ 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» (PDF). PhD Thesis. Consultado em 24 de novembro de 2011. Arquivado do original (PDF) em 16 de agosto de 2009
- ↑ Sunglok Choi, Taemin Kim, and Wonpil Yu (2009). «Performance Evaluation of RANSAC Family» (PDF). In Proceedings of the British Machine Vision Conference (BMVC)