RANSAC

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de febrero de 2020; la verificación requiere 1 edición .

RANSAC ( abreviado como RANdom SAmple Consensus ) es un método estable para estimar los parámetros del modelo basado en muestras aleatorias . El esquema RANSAC es resistente a datos de entrada ruidosos. El método fue propuesto en 1981 por Fischler y Bolles.

A menudo hay una tarea de procesamiento de datos en la que es necesario determinar los parámetros del modelo, que deben satisfacer los datos iniciales. Todos los datos iniciales se pueden dividir en dos tipos: puntos buenos que satisfacen el modelo, “non-outliers” o “inlayers” ( inglés inlier ) y puntos falsos, los ruidos son inclusiones aleatorias en los datos originales, “outliers” o “outlayers” ( Inglés ) .outlier

Ejemplo

Considere el ejemplo más simple de cómo funciona el algoritmo: inscribir una línea recta en un punto 2D . Suponiendo que hay valores atípicos en los datos, la estimación de parámetros de forma estándar, como los mínimos cuadrados , dará como resultado que se calcule un modelo incorrecto, ya que el modelo se construye a partir de todos los puntos. El método RANSAC toma como base solo dos puntos necesarios para construir una línea recta y construye un modelo con su ayuda, después de lo cual verifica cuántos puntos corresponden al modelo utilizando una función de estimación con un umbral dado.

El conjunto de datos en el que se ajusta la línea. las emisiones son abundantes.
Recta propuesta por el algoritmo RANSAC. los valores atípicos no afectan el resultado.

Descripción del algoritmo

La entrada del algoritmo es:

conjunto de datos inicial $X$
una función que le permite calcular los parámetros del modelo a partir de un conjunto de datos de puntos $METRO$ $\ theta$ $PAGS$ $norte$
función para evaluar la correspondencia de puntos con el modelo resultante $mi$
umbral para la función de evaluación $t$
número de iteraciones del método $k$

Todo el algoritmo consta de un ciclo, cada iteración del cual se puede dividir lógicamente en dos etapas.

La primera etapa es la selección de puntos y el cálculo del modelo.
- Del conjunto de puntos iniciales , se seleccionan aleatoriamente n puntos diferentes. $X$
- Con base en los puntos seleccionados, los parámetros del modelo se calculan utilizando la función , el modelo construido generalmente se denomina hipótesis. $\ theta$ $PAGS$ $METRO$
El segundo paso es la prueba de hipótesis.
- Para cada punto se comprueba el cumplimiento de esta hipótesis mediante la función de evaluación y el umbral $mi$ $t$
- Cada punto está marcado con una capa interna o un valor atípico
- Después de comprobar todos los puntos, se comprueba si la hipótesis es la mejor en ese momento, y si lo es, se reemplaza la anterior mejor hipótesis.

Al final del ciclo, queda la última mejor hipótesis.

Los resultados del método son:

Parámetros del modelo $\ theta$ $PAGS$
Puntos de datos de origen etiquetados con capas o valores atípicos.

Evaluación de datos iniciales

El valor del parámetro debe determinarse según los requisitos específicos según los datos, en la mayoría de los casos, solo después de evaluaciones experimentales. El número de iteraciones se puede determinar antes de ejecutar el algoritmo mediante estimación teórica. Sea la probabilidad de que el algoritmo RANSAC en alguna iteración , eligiendo los puntos en los que se basa el modelo, tome solo capas internas del conjunto de datos inicial para los cálculos. En tal situación, es probable que el modelo construido a partir de estos puntos sea bastante preciso. Con base en esto, podemos usar la probabilidad p para estimar la precisión del algoritmo. Sea la probabilidad de elegir una capa interna del número total de puntos, es decir , donde es el número de capas internas y es el número total de puntos. En la mayoría de los casos, el porcentaje de capas internas no se conoce antes de que comience el algoritmo, pero casi siempre se puede hacer una estimación aproximada. La probabilidad de una elección independiente de n capas internas de los datos iniciales, en este caso, es , y la probabilidad de que al menos un punto del conjunto sea un valor atípico, es decir, que se construya un modelo incorrecto, es . La probabilidad de que durante las iteraciones el algoritmo nunca seleccione las capas internas es , esta situación significa que no se construirá el modelo exacto y la probabilidad de este evento es . De este modo $t$ $k$ $pags$ $norte$ $w$ $w=I/T$ ${\ estilo de visualización yo}$ $T$ $w$ $q=C_{I}^{n}/C_{T}^{n}=¡I!(Tn)!/(T!(En)!)$ ${\ estilo de visualización (1-q)}$ $k$ $norte$ ${\ estilo de visualización (1-q)^{k))$ $(1 p)$

{\ Displaystyle 1-p=(1-q)^{k))

Expresemos el número de iteraciones que necesitamos k

$k={\frac {\log(1-p)}{\log(1-q)))$

Ventajas y desventajas del algoritmo RANSAC

La ventaja del algoritmo RANSAC es su capacidad para brindar una estimación confiable de los parámetros del modelo, es decir, la capacidad de estimar los parámetros del modelo con alta precisión, incluso si hay una cantidad significativa de valores atípicos en el conjunto de datos original.

Una de las desventajas del método RANSAC es la ausencia de un límite superior en el tiempo requerido para calcular los parámetros del modelo. Si usamos el número máximo de iteraciones como límite de tiempo, la solución resultante puede no ser óptima, y también hay una probabilidad muy pequeña de que ningún modelo coincida con los datos originales. Se puede determinar un modelo exacto con una cierta probabilidad que aumenta cuantas más iteraciones se utilicen. Otra desventaja del método RANSAC es que es necesario establecer un valor de umbral específico para ejecutar el algoritmo. Finalmente, el método RANSAC puede determinar solo un modelo para un conjunto de datos en particular. Al igual que con cualquier enfoque de modelo único, existe un problema: cuando dos (o más) modelos están presentes en los datos de entrada, es posible que RANSAC no encuentre ninguno.

Aplicación

El algoritmo RANSAC se usa a menudo en visión por computadora , por ejemplo, para resolver el problema de la coincidencia de imágenes y la estimación de matriz fundamental para determinar los parámetros de posición de la cámara.

Enlaces

Martin A. Fischler y Robert C. Bolles. Consenso de muestras aleatorias: un paradigma para el ajuste de modelos con aplicaciones de análisis de imágenes y cartografía automatizada // Comm . De la ACM: diario. - 1981. - junio ( vol. 24 ). - P. 381-395 . -doi : 10.1145/ 358669.358692 .
David A. Forsyth y Jean Ponce. Computer Vision, un enfoque moderno (neopr.) . - Prentice Hall , 2003. - ISBN ISBN 0-13-085198-1 .
Richard Hartley y Andrew ZissermanGeometría de Vista Múltiple enVisión por Computador . — 2do. — Prensa de la Universidad de Cambridge , 2003.
PHS Torr y DW Murray. El desarrollo y la comparación de métodos robustos para estimar la matriz fundamental // Revista internacional de visión por computadora : diario. - 1997. - vol. 24 . - Pág. 271-300 . -doi : 10.1023/A : 1007927408552 .
Ondrej Chum (2005), Estimación de geometría de dos vistas por muestra aleatoria y consenso , tesis doctoral , < http://cmp.felk.cvut.cz/~chum/Teze/Chum-PhD.pdf > . Consultado el 30 de mayo de 2010. Archivado el 16 de agosto de 2009 en Wayback Machine .
Anton Konushin, Stable Algorithms for Estimating Model Parameters Based on Random Samples , Computer Graphics and Multimedia , < http://cgm.computergraphics.ru/content/view/47 > Archivado el 30 de enero de 2009 en Wayback Machine .