El consenso de muestra aleatoria ( RANSAC ) es un método iterativo para estimar parámetros de un modelo matemático a partir de un conjunto de datos observados que contiene valores atípicos , cuando los valores atípicos no deben tener influencia en los valores de las estimaciones. Por lo tanto, también se puede interpretar como un método de detección de valores atípicos. [1] Es un algoritmo no determinista en el sentido de que produce un resultado razonable solo con una cierta probabilidad, con esta probabilidad aumentando a medida que se permiten más iteraciones. El algoritmo fue publicado por primera vez por Fischler y Bolles en SRI International. en 1981. Usaron RANSAC para resolver el Problema de Determinación de Ubicación (LDP), donde el objetivo es determinar los puntos en el espacio que se proyectan en una imagen en un conjunto de puntos de referencia con ubicaciones conocidas.
Una suposición básica es que los datos consisten en "inliers", es decir, datos cuya distribución puede explicarse por algún conjunto de parámetros del modelo, aunque pueden estar sujetos a ruido, y "outliers" que son datos que no se ajustan al modelo. Los valores atípicos pueden provenir, por ejemplo, de valores extremos del ruido o de mediciones erróneas o hipótesis incorrectas sobre la interpretación de los datos. RANSAC también asume que, dado un conjunto (generalmente pequeño) de inliers, existe un procedimiento que puede estimar los parámetros de un modelo que explica o ajusta de manera óptima estos datos.
Ejemplo
Un ejemplo simple es ajustar una línea en dos dimensiones a un conjunto de observaciones. Suponiendo que este conjunto contiene tanto inliers, es decir, puntos que aproximadamente pueden ajustarse a una línea, como atípicos, puntos que no pueden ajustarse a esta línea, un método simple de mínimos cuadrados para el ajuste de líneas generalmente producirá una línea con un mal ajuste a los datos, incluidos los inliers y los valores atípicos. La razón es que se ajusta de manera óptima a todos los puntos, incluidos los valores atípicos. RANSAC, por otro lado, intenta excluir los valores atípicos y encontrar un modelo lineal que solo utilice los valores atípicos en su cálculo. Esto se hace ajustando modelos lineales a varios muestreos aleatorios de los datos y devolviendo el modelo que tiene el mejor ajuste a un subconjunto de los datos. Dado que los inliers tienden a estar más relacionados linealmente que una mezcla aleatoria de inliers y outliers, un subconjunto aleatorio que consta completamente de inliers tendrá el mejor ajuste de modelo. En la práctica, no hay garantía de que se muestreará aleatoriamente un subconjunto de inliers, y la probabilidad de que el algoritmo tenga éxito depende de la proporción de inliers en los datos, así como de la elección de varios parámetros del algoritmo.
Un conjunto de datos con muchos valores atípicos para los que se debe ajustar una línea.
Línea equipada con RANSAC; los valores atípicos no influyen en el resultado.
Descripción general
El algoritmo RANSAC es una técnica de aprendizaje para estimar parámetros de un modelo mediante muestreo aleatorio de datos observados. Dado un conjunto de datos cuyos elementos de datos contienen tanto inliers como outliers, RANSAC usa el esquema de votación para encontrar el resultado de ajuste óptimo. Los elementos de datos del conjunto de datos se utilizan para votar por uno o varios modelos. La implementación de este esquema de votación se basa en dos suposiciones: que las características ruidosas no votarán consistentemente por un solo modelo (pocos valores atípicos) y hay suficientes características para acordar un buen modelo (pocos datos faltantes). El algoritmo RANSAC se compone esencialmente de dos pasos que se repiten iterativamente:
- En el primer paso, se selecciona al azar un subconjunto de muestra que contiene elementos de datos mínimos del conjunto de datos de entrada. Un modelo de ajuste y los parámetros del modelo correspondientes se calculan utilizando solo los elementos de este subconjunto de muestra. La cardinalidad del subconjunto de la muestra es la más pequeña y suficiente para determinar los parámetros del modelo.
- En el segundo paso, el algoritmo verifica qué elementos de todo el conjunto de datos son consistentes con el modelo instanciado por los parámetros estimados del modelo obtenidos en el primer paso. Un elemento de datos se considerará un valor atípico si no se ajusta al modelo de ajuste instanciado por el conjunto de parámetros estimados del modelo dentro de algún umbral de error que define la desviación máxima atribuible al efecto del ruido.
El conjunto de inliers obtenido para el modelo de ajuste se denomina conjunto de consenso. El algoritmo RANSAC repetirá iterativamente los dos pasos anteriores hasta que el consenso obtenido en cierta iteración tenga suficientes inliers.
La entrada al algoritmo RANSAC es un conjunto de valores de datos observados, una forma de ajustar algún tipo de modelo a las observaciones y algunos parámetros de confianza . RANSAC logra su objetivo repitiendo los siguientes pasos:
- Seleccione un subconjunto aleatorio de los datos originales. Llame a este subconjunto los inliers hipotéticos .
- Un modelo se ajusta al conjunto de inliers hipotéticos.
- Luego, todos los demás datos se comparan con el modelo ajustado. Los puntos que se ajustan bien al modelo estimado, de acuerdo con alguna función de pérdida específica del modelo , se consideran parte del conjunto de consenso .
- El modelo estimado es razonablemente bueno si se han clasificado suficientes puntos como parte del conjunto de consenso.
- Posteriormente, el modelo puede mejorarse volviéndolo a estimar utilizando todos los miembros del conjunto de consenso.
Este procedimiento se repite un número fijo de veces, cada vez que produce un modelo que se rechaza porque muy pocos puntos forman parte del conjunto de consenso, o un modelo refinado junto con el tamaño del conjunto de consenso correspondiente. En el último caso, mantenemos el modelo refinado si su conjunto de consenso es mayor que el modelo guardado previamente.
RANSAC: Inliers y Outliers.
Algoritmo
El algoritmo genérico RANSAC funciona de la siguiente manera:
Dado: datos: un conjunto de observaciones. modelo: un modelo para explicar los puntos de datos observados. n: número mínimo de puntos de datos necesarios para estimar los parámetros del modelo. k: número máximo de iteraciones permitidas en el algoritmo. t: valor de umbral para determinar los puntos de datos que se ajustan bien al modelo. d - Número de puntos de datos cercanos necesarios para afirmar que un modelo se ajusta bien a los datos.Regreso: bestFit: parámetros del modelo que mejor se ajustan a los datos (o nulos si no se encuentra un buen modelo)iteraciones = 0bestFit = nulobestErr = algo realmente grandemientras que las iteraciones < k hacen maybeInliers: = n valores seleccionados al azar de los datos maybeModel: = parámetros del modelo ajustados a maybeInliers alsoInliers: = conjunto vacío para cada punto en los datos que no están en maybeInliers hacen si el punto se ajusta a maybeModel con un error menor que t agregar punto a alsoInliers end porque si el número de elementos en alsoInliers es> d entonces // Esto implica que podemos haber encontrado un buen modelo // ahora prueba qué tan bueno es. betterModel: = parámetros del modelo ajustados a todos los puntos en maybeInliers y alsoInliers thisErr: = una medida de qué tan bien betterModel se ajusta a estos puntos si thisErrentonces bestFit: = betterModel bestErr: = thisErr terminar si terminar si incrementar iteracionesterminar mientrasvolver bestFit
Parámetros
El valor de umbral para determinar cuándo un punto de datos se ajusta a un modelo t , y el número de puntos de datos cercanos necesarios para afirmar que un modelo se ajusta bien a los datos d se determinan en función de los requisitos específicos de la aplicación y el conjunto de datos, y posiblemente en base a datos experimentales. evaluación. Sin embargo, el número de iteraciones k se puede determinar como una función de la probabilidad de éxito deseada p utilizando un resultado teórico. Sea p la probabilidad deseada de que el algoritmo RANSAC proporcione un resultado útil después de la ejecución. RANSAC devuelve un resultado exitoso si, en alguna iteración, selecciona solo inliers del conjunto de datos de entrada cuando elige los n puntos a partir de los cuales se estiman los parámetros del modelo. Dejar ser la probabilidad de elegir un inlier cada vez que se selecciona un solo punto, es decir,
- = número de inliers en los datos / número de puntos en los datos
Un caso común es que no se conoce bien de antemano, pero se puede dar algún valor aproximado. Suponiendo que los n puntos necesarios para estimar un modelo se seleccionan de forma independiente,es la probabilidad de que todos los n puntos sean inliers yes la probabilidad de que al menos uno de los n puntos sea un valor atípico, caso que implica que se estimará un mal modelo a partir de este conjunto de puntos. Esa probabilidad elevada a la potencia de k es la probabilidad de que el algoritmo nunca seleccione un conjunto de n puntos que son todos inliers y esto debe ser lo mismo que. Como consecuencia,
que, después de tomar el logaritmo de ambos lados, conduce a
Este resultado supone que los n puntos de datos se seleccionan de forma independiente, es decir, un punto que se ha seleccionado una vez se reemplaza y se puede volver a seleccionar en la misma iteración. A menudo, este no es un enfoque razonable y el valor derivado de k debe tomarse como un límite superior en el caso de que los puntos se seleccionen sin reemplazo. Por ejemplo, en el caso de encontrar una línea que se ajuste al conjunto de datos ilustrado en la figura anterior, el algoritmo RANSAC normalmente elige dos puntos en cada iteración y calcula maybe_model
como la línea entre los puntos y luego es fundamental que los dos puntos sean distintos. .
Para ganar confianza adicional, la desviación estándar o sus múltiplos pueden agregarse a k . La desviación estándar de k se define como
Ventajas y desventajas
Una ventaja de RANSAC es su capacidad para realizar estimaciones sólidas [2] de los parámetros del modelo, es decir, puede estimar los parámetros con un alto grado de precisión incluso cuando hay un número significativo de valores atípicos en el conjunto de datos. Una desventaja de RANSAC es que no existe un límite superior en el tiempo que lleva calcular estos parámetros (excepto el agotamiento). Cuando el número de iteraciones calculadas es limitado, la solución obtenida puede no ser óptima, y puede que ni siquiera se ajuste bien a los datos. De esta manera, RANSAC ofrece una compensación; al calcular un mayor número de iteraciones, aumenta la probabilidad de que se produzca un modelo razonable. Además, RANSAC no siempre puede encontrar el conjunto óptimo, incluso para conjuntos moderadamente contaminados y, por lo general, funciona mal cuando el número de inliers es inferior al 50%. Se propuso el RANSAC óptimo [3] para manejar ambos problemas y es capaz de encontrar el conjunto óptimo para conjuntos muy contaminados, incluso para una relación interior inferior al 5%. Otra desventaja de RANSAC es que requiere el establecimiento de umbrales específicos del problema.
RANSAC solo puede estimar un modelo para un conjunto de datos en particular. En cuanto a cualquier enfoque de un modelo cuando existen dos (o más) instancias de modelo, es posible que RANSAC no encuentre ninguno. La transformada de Hough es una técnica alternativa de estimación robusta que puede ser útil cuando está presente más de una instancia de modelo. Otro enfoque para el ajuste de modelos múltiples se conoce como PEARL, [4] que combina el muestreo de modelos a partir de puntos de datos como en RANSAC con la reestimación iterativa de los inliers y el ajuste de modelos múltiples que se formula como un problema de optimización con una función de energía global que describe el calidad de la solución global.
Aplicaciones
El algoritmo RANSAC se usa a menudo en visión por computadora , por ejemplo, para resolver simultáneamente el problema de correspondencia y estimar la matriz fundamental relacionada con un par de cámaras estéreo; ver también: Estructura de movimiento , transformación de características invariantes de escala , unión de imágenes , segmentación de movimiento rígido .
Desarrollo y mejoras
Desde 1981, RANSAC se ha convertido en una herramienta fundamental en la comunidad de procesamiento de imágenes y visión por computadora . En 2006, con motivo del 25 aniversario del algoritmo, se organizó un taller en la Conferencia Internacional sobre Visión por Computador y Reconocimiento de Patrones (CVPR) para resumir las contribuciones y variaciones más recientes al algoritmo original, principalmente destinadas a mejorar la velocidad del algoritmo. , la robustez y precisión de la solución estimada y para disminuir la dependencia de las constantes definidas por el usuario.
RANSAC puede ser sensible a la elección del umbral de ruido correcto que define qué puntos de datos se ajustan a un modelo instanciado con un determinado conjunto de parámetros. Si dicho umbral es demasiado grande, entonces todas las hipótesis tienden a clasificarse por igual (buenas). Por otro lado, cuando el umbral de ruido es demasiado pequeño, los parámetros estimados tienden a ser inestables (es decir, simplemente agregando o quitando un dato al conjunto de inliers, la estimación de los parámetros puede fluctuar). Para compensar parcialmente este efecto indeseable, Torr et al. propusieron dos modificaciones de RANSAC llamadas MSAC (Ejemplo y consenso del estimador M) y MLESAC (Ejemplo y consenso de estimación de máxima verosimilitud). [5] La idea principal es evaluar la calidad del conjunto de consenso (es decir, los datos que se ajustan a un modelo y un cierto conjunto de parámetros) calculando su probabilidad (mientras que en la formulación original de Fischler y Bolles el rango era la cardinalidad de tal colocar). Tordoff propone una extensión de MLESAC que tiene en cuenta las probabilidades previas asociadas al conjunto de datos de entrada. [6] El algoritmo resultante se denomina Guided-MLESAC. De manera similar, Chum propuso orientar el procedimiento de muestreo si se conoce alguna información a priori con respecto a los datos de entrada, es decir, si es probable que un dato sea un valor inlier o un outlier. El enfoque propuesto se denomina PROSAC, ejemplo de consenso progresivo. [7]
Chum y col. También propuso una versión aleatoria de RANSAC llamada R-RANSAC [8] para reducir la carga computacional para identificar un buen conjunto de consenso. La idea básica es evaluar inicialmente la bondad del modelo instanciado actualmente utilizando solo un conjunto reducido de puntos en lugar de todo el conjunto de datos. Una estrategia sólida dirá con gran confianza cuándo es el caso de evaluar el ajuste de todo el conjunto de datos o cuándo el modelo puede descartarse fácilmente. Es razonable pensar que el impacto de este enfoque es más relevante en los casos en que el porcentaje de inliers es grande. El tipo de estrategia propuesta por Chum et al. se llama esquema de preferencia. Nistér propuso un paradigma llamado Preemptive RANSAC [9] que permite una estimación robusta en tiempo real de la estructura de una escena y del movimiento de la cámara. La idea central del enfoque consiste en generar un número fijo de hipótesis para que la comparación ocurra con respecto a la calidad de la hipótesis generada en lugar de contra alguna métrica de calidad absoluta.
Otros investigadores intentaron hacer frente a situaciones difíciles en las que no se conoce la escala de ruido y / o están presentes múltiples instancias del modelo. El primer problema ha sido abordado en el trabajo de Wang y Suter. [10] Toldo y col. representar cada dato con la función característica del conjunto de modelos aleatorios que se ajustan al punto. Luego, varios modelos se revelan como grupos que agrupan los puntos que apoyan el mismo modelo. El algoritmo de agrupamiento, llamado J-linkage, no requiere una especificación previa del número de modelos, ni tampoco un ajuste manual de los parámetros. [11]
RANSAC también se ha diseñado para aplicaciones de estimación de estado recursivas, donde las mediciones de entrada se corrompen por valores atípicos y los enfoques de filtro de Kalman, que se basan en una distribución gaussiana del error de medición, están condenados al fracaso. Este enfoque se denomina KALMANSAC. [12]
Métodos relacionados
- MLESAC (Consenso de la muestra de estimación de máxima verosimilitud): maximiza la probabilidad de que los datos se generen a partir del modelo ajustado por muestra, por ejemplo, un modelo mixto de valores inliers y outliers
- MAPSAC (máximo consenso de una muestra posterior): amplía MLESAC para incorporar una probabilidad previa de los parámetros que se ajustarán y maximiza la probabilidad posterior.
- KALMANSAC - inferencia causal del estado de un sistema dinámico
- Remuestreo (estadísticas)
Notas
- ^ Ajuste de datos e incertidumbre, T. Strutz, Springer Vieweg (segunda edición, 2016)
- ^ Estadísticas sólidas, Peter. J. Huber, Wiley, 1981 (republicado en rústica, 2004), página 1.
- ^ Anders Hast, Johan Nysjö, Andrea Marchetti (2013). "RANSAC óptimo - hacia un algoritmo repetible para encontrar el conjunto óptimo". Revista de WSCG 21 (1): 21–30.
- ^ Hossam Isack, Yuri Boykov (2012). "Ajuste multimodelo geométrico basado en energía". Revista Internacional de Visión por Computador 97 (2: 1): 23-147. doi : 10.1007 / s11263-011-0474-7 .
- ^ PHS Torr y A. Zisserman, MLESAC: Un nuevo estimador robusto con aplicación para estimar la geometría de la imagen , Journal of Computer Vision and Image Understanding 78 (2000), no. 1, 138-156.
- ^ BJ Tordoff y DW Murray, Guided-MLESAC: Estimación de transformación de imagen más rápida mediante el uso de anteriores coincidentes , IEEE Transactions on Pattern Analysis and Machine Intelligence 27 (2005), no. 10, 1523-1535.
- ^ Coincidencia con PROSAC - consenso de muestra progresiva , Actas de la Conferencia sobre Visión por Computadora y Reconocimiento de Patrones (San Diego), vol. 1, junio de 2005, págs. 220–226
- ^ O. Chum y J. Matas, Randomized RANSAC with Td, d test, 13th British Machine Vision Conference, septiembre de 2002. http://www.bmva.org/bmvc/2002/papers/50/
- ^ D. Nistér, RANSAC preventivo para la estimación de movimiento y estructura en vivo , IEEE International Conference on Computer Vision (Niza, Francia), octubre de 2003, págs. 199–206.
- ^ H. Wang y D. Suter, Estimación robusta del modelo paramétrico de escala adaptativa para visión por computadora ., Transacciones IEEE sobre análisis de patrones e inteligencia de máquina 26 (2004), no. 11, 1459-1474
- ^ R. Toldo y A. Fusiello, Estimación robusta de estructuras múltiples con enlace J , Conferencia europea sobre visión por computadora (Marsella, Francia), octubre de 2008, págs. 537–547.
- ^ A. Vedaldi, H. Jin, P. Favaro y S. Soatto, KALMANSAC: filtrado robusto por consenso , Actas de la Conferencia Internacional sobre Visión por Computador (ICCV), vol. 1, 2005, págs. 633–640
Referencias
- Martin A. Fischler y Robert C. Bolles (junio de 1981). "Consenso de muestra aleatoria: un paradigma para el ajuste de modelos con aplicaciones de análisis de imágenes y cartografía automatizada" (PDF) . Comm. ACM . 24 (6): 381–395. doi : 10.1145 / 358669.358692 . S2CID 972888 .
- David A. Forsyth y Jean Ponce (2003). Visión por computadora, un enfoque moderno . Prentice Hall. ISBN 978-0-13-085198-7.
- Richard Hartley y Andrew Zisserman (2003). Geometría de vista múltiple en visión artificial (2ª ed.). Prensa de la Universidad de Cambridge.
- Strutz, T. (2016). Ajuste de datos e incertidumbre (una introducción práctica a los mínimos cuadrados ponderados y más) . 2ª edición, Springer Vieweg. ISBN 978-3-658-11455-8.
- PHS Torr y DW Murray (1997). "El desarrollo y comparación de métodos robustos para estimar la matriz fundamental". Revista Internacional de Visión por Computador . 24 (3): 271–300. doi : 10.1023 / A: 1007927408552 . S2CID 12031059 .
- Ondrej Chum (2005). "Estimación de geometría de dos vistas por muestra aleatoria y consenso" (PDF) . Tesis de Doctorado .
- Sunglok Choi; Taemin Kim y Wonpil Yu (2009). "Evaluación del desempeño de la familia RANSAC" (PDF) . En Actas de la Conferencia Británica de Visión Artificial (BMVC) .
- Anders Hast; Johan Nysjö; Andrea Marchetti (2013). "Optimal RANSAC - Hacia un algoritmo repetible para encontrar el conjunto óptimo" (PDF) . Revista de WSCG . 21 (1): 21-30.
- Hossam Isack; Yuri Boykov (2012). "Ajuste multimodelo geométrico basado en energía" (PDF) . Revista Internacional de Visión por Computador . 97 (2: 1): 23-147. CiteSeerX 10.1.1.381.2434 . doi : 10.1007 / s11263-011-0474-7 . S2CID 5461268 .