Usuario:Xavi.borras/Taller

Random sample consensus (RANSAC) és un método iterativo para calcular los parámetros de un modelo matemático de un conjunto de datos observados que contiene valores atípicos. Es un algoritmo no determinista en el sentido de que produce un resultado razonable sólo con una cierta probabilidad, mayor a medida que se permiten más iteraciones. El algoritmo fue publicado por primera vez por Fischler y Bolles SRI International en 1981.

Los datos consisten en "inliers", es decir, los datos cuya distribución se explica por un conjunto de parámetros del modelo, aunque pueden estar sujetos a ruido, y "valores atípicos", que son datos que no encajan en el modelo. Los valores atípicos pueden llegar, 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, dada un conjunto de inliers (generalmente pequeño), existe un procedimiento que puede estimar los parámetros de un modelo que explica de manera óptima o se ajusta a esta información.

Ejemplo

Un ejemplo sencillo es la inserción de una linea en dos dimensiones a un conjunto de observaciones. Asumiendo que este conjunto contiene todos los inliers, es decir, los puntos que se pueden insertar de forma aproximada en una línea, y los valores atípicos, puntos que no se pueden montar en esta línea. Si se utiliza el método de mínimos cuadrados ordinarios para el montaje de la línea generalmente producirá una línea con un mal ajuste de los inliers. La razón es que se monta de forma óptima a todos los puntos, incluyendo los valores atípicos. Por otro lado, RANSAC permite crear un modelo que sólo está calculado con los inliers, siempre que la probabilidad de elegir sólo los inliers sea suficientemente alta. No hay ninguna garantía de que se cumpla esta situacion, sin embargo, hay una serie de parámetros del algoritmo que deben elegirse cuidadosamente para mantener el nivel de probabilidad razonablemente alta.

• 
  Conjunto de datos con muchos valores atípicos.
• 
  Línea creada con RANSAC; los valores atípicos no tienen ninguna influencia en el resultado.

Resumen

La entrada al algoritmo RANSAC esta formado por un conjunto de valores de los datos observados, una forma de ajustar algún tipo de modelo a las observaciones, y algunos parámetros de confianza. RANSAC logra su objetivo mediante la repetición de los siguientes pasos:

1. Seleccionar un subconjunto aleatorio de los datos originales. Subconjunto llamado "inliers hipotéticos".
2. Un modelo se monta en el conjunto de inliers hipotéticos.
3. Todos los demás datos se prueban contra el modelo ajustado. Esos puntos que se ajustan al modelo estimado, de acuerdo con alguna función de pérdida de modelos específicos, se consideran como parte del conjunto de consenso.
4. El modelo estimado es bueno si se han clasificado suficientes puntos como parte del conjunto de consenso.
5. Después, el modelo puede ser mejorado volviendo a estimar usando todos los miembros del conjunto de consenso.

Este procedimiento se repite un número fijo de veces, produciendo o bien un modelo que es rechazado porque no hay suficientes puntos en el conjunto de consenso, o un modelo aceptado con suficientes puntos en el conjunto de consenso. En este último caso, mantenemos el modelo si su conjunto de consenso es más grande que el modelo guardado previamente.

• 
  RANSAC: Inliers y Outliers.

Algoritmo

El algoritmo RANSAC general funciona así:

Given:
    data - a set of observed data points
    model - a model that can be fitted to data points
    n - the minimum number of data values required to fit the model
    k - the maximum number of iterations allowed in the algorithm
    t - a threshold value for determining when a data point fits a model
    d - the number of close data values required to assert that a model fits well to data
Return:
    bestfit - model parameters which best fit the data (or nil if no good model is found)
iterations = 0
bestfit = nil
besterr = something really large
while iterations < k {
    maybeinliers = n randomly selected values from data
    maybemodel = model parameters fitted to maybeinliers
    alsoinliers = empty set
    for every point in data not in maybeinliers {
        if point fits maybemodel with an error smaller than t
             add point to alsoinliers
    }
    if the number of elements in alsoinliers is > d {
        % this implies that we may have found a good model
        % now test how good it is
        bettermodel = model parameters fitted to all points in maybeinliers and alsoinliers
        thiserr = a measure of how well model fits these points
        if thiserr < besterr {
            bestfit = bettermodel
            besterr = thiserr
        }
    }
    increment iterations
}
return bestfit

Parametros

Los valores de los parametros $t$ i $d$, tienen que ser determinados a partir de requisitos específicos relacionados con la aplicación y el conjunto de datos, posiblemente basados en la evaluación experimental. El parámetro $k$ (número de iteraciones), sin embargo, se puede determinar a partir de un resultado teórico. El valor $p$ determina la probabilidad de que el algoritmo RANSAC seleccione solo inliers a partir del conjunto de datos de entrada cuando se elijen $n$ puntos con los que se estiman los parámetros del modelo. Cuando esto sucede, el modelo resultante probablemente es útil de modo que $p$ es la probabilidad que el algoritmo produzca un resultado útil. $w$ es la probabilidad de elegir un inlier cada vez que se selecciona un solo punto.

$w$ = number of inliers in data / number of points in data

Un caso común es que $w$ no se conozca de antemano, pero se puede conocer algún valor. Suponiendo que los $n$ puntos necesarios para la estimación de un modelo se seleccionan independientemente, $w^{n}$ es la probabilidad de que todos los n puntos son inliers y $1-w^{n}$ es la probabilidad de que al menos uno de los n puntos es un caso atípico, esto implica que un mal modelo se estimó a partir de este conjunto de puntos. Esta probabilidad a la potencia de $k$ es la probabilidad de que el algoritmo nunca selecciona un conjunto de n puntos donde todos son inliers y esto debe ser el mismo que $1-p$. Por consiguiente,

$1-p=(1-w^{n})^{k}$

que, después de realizar el logaritmo de ambos lados, lleva a

$k={\frac {\log(1-p)}{\log(1-w^{n})}}$

Este resultado asume que los n puntos de datos se seleccionan independientemente, es decir, se sustituye un punto que ha sido seleccionado una vez y se puede seleccionar de nuevo en la misma iteración. Esto a menudo 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 ajusta al conjunto de datos, como se ilustra a la figura anterior, el algoritmo RANSAC típicamente elige dos puntos en cada iteración y calcula maybe_model como la línea entre los puntos, es fundamental que los dos puntos sean distintos.

Para ganar una confianza adicional, la desviación típica o sus múltiples estándares se pueden agregar a $k$. La desviación típica de $k$ se define como

$SD(k)={\frac {\sqrt {1-w^{n}}}{w^{n}}}$

Ventajas y desventajas

Una ventaja de RANSAC es su capacidad para hacer una estimación robusta​ de los parámetros del modelo, es decir, se pueden estimar los parámetros con un alto grado de precisión, incluso cuando están presentes en el conjunto de datos de un número significativo de valores atípicos. Una desventaja de RANSAC es que no hay tiempo máximo para calcular estos parámetros (excepto agotamiento). Cuando el número de iteraciones calculadas se limita a la solución obtenida puede no ser un resultado óptimo, y puede incluso no ajustarse a los datos. De esta manera RANSAC ofrece una solución de compromiso; mediante el cálculo de un mayor número de iteraciones se incrementa la probabilidad de encontrar un modelo razonable. Por otra parte, RANSAC no siempre es capaz de encontrar la configuración óptima incluso para conjuntos moderadamente contaminados y por lo general tiene un rendimiento pobre cuando el número de inliers es inferior al 50%. Optimal RANSAC se propuso para manejar estos dos problemas, es por eso que es capaz de encontrar el conjunto óptimo para conjuntos muy contaminados, incluso para una relación de inlier debajo del 5%. Otra desventaja de RANSAC es que requiere el establecimiento de umbrales de problemas específicos.

RANSAC sólo puede estimar un modelo para un conjunto de datos particular. Como para cualquier planteamiento de un modelo cuando existen dos (o más) instancias de modelo, RANSAC puede fallar para encontrar cualquiera de ellos. La transformada de Hough es una técnica de estimación robusta alternativa que puede ser útil cuando está presente más de una instancia de modelo. Otro multi-modelo es conocido como PEARL,​ que combina el modelo de muestreo de puntos de datos como en RANSAC con la re-estimación iterativa de inliers y el accesorio multi-modelo que se está formulado como un problema de optimización con un global de energía funcional que describe la calidad de la solución global.

Aplicaciones

El algoritmo RANSAC se utiliza a menudo en la visión por computador, por ejemplo, para resolver simultáneamente el problema de correspondencia y estimar la matriz fundamental relacionada con un par de cámaras estéreo.

Desarrollo i mejoras

Desde 1981 RANSAC se ha convertido en una herramienta fundamental en la comunidad de la visión por computador y procesamiento de imágene. En 2006, por el 25 aniversario del algoritmo, se organizó un taller en la Conferencia Internacional sobre la Visión por Computador y Reconocimiento de Patrones para resumir las aportaciones más recientes y las variaciones en el algoritmo original, principalmente destinada 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.

Como señala Torr, RANSAC puede ser sensible a la elección del umbral de ruido correcta que define qué puntos de datos se ajustan a un modelo instanciado con un cierto conjunto de parámetros. Si tal umbral es demasiado grande, entonces todas las hipótesis tienden a ser clasificadas por igual. Por otro lado, cuando el umbral de ruido es demasiado pequeño, los parámetros estimados tienden a ser inestables (es decir, simplemente añadiendo o quitando un dato para el conjunto de inliers, la estimación de los parámetros puede fluctuar). Para compensar parcialmente este efecto indeseable, Torr propone dos modificaciones de RANSAC llamadas MSAC (M-estimator SAmple and Consensus) y MLESAC (Maximum Likelihood Estimation SAmple and Consensus).​ La idea principal es evaluar la calidad del conjunto de consenso (es decir, los datos que se ajustan a un modelo y a un cierto conjunto de parámetros) calcular la probabilidad (mientras que en la formulación original de Fischler y Bolles el rango era la cardinalidad de tal conjunto). Una extensión para MLESAC que mantiene las probabilidades previas asociadas al conjunto de datos de entrada se propone por Tordoff.​ El algoritmo resultante es apodado Guided-MLESAC. En una línea similar, Chum propone guiar el procedimiento de muestreo si se conoce alguna información a priori con respecto a los datos de entrada, es decir, si un dato es probable que sea un inlier o un valor atípico. El enfoque propuesto se llama PROSAC, PROgressive SAmple Consensus.​

Chum también propuso una versión aleatoria de RANSAC llamada R-RANSAC ​ para reducir la carga computacional para identificar una buena CS. La idea básica es evaluar inicialmente la eficacia del modelo actualmente instanciado utilizando sólo un conjunto reducido de puntos en lugar de todo el conjunto de datos. Una estrategia de sonido le dirá con alta fiabilidad cuando es el caso para evaluar todo el conjunto de datos o cuando el modelo puede ser desechado 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 es llamado esquema de prevención. Nister propone un paradigma denominado Preemptive RANSAC​ que permite la 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 de manera que la comparación sucede con respecto a la calidad de la hipótesis generada.

Otros investigadores trataron de hacer frente a situaciones difíciles, donde la escala de ruido no se conocen y/o múltiples instancias de modelo están presentes. El primer problema se ha abordado en el trabajo de Wang y Suter.​ Toldo quiere representar cada punto de referencia con la función característica del conjunto de modelos aleatorios que se ajustan al punto. Entonces múltiples modelos se revelan como grupos que agrupan los puntos de apoyo del mismo modelo. El algoritmo de agrupamiento, llamado J-linkage, no requiere la especificación previa de la serie de modelos, ni se requieren parámetros de sintonización manual.​

RANSAC también se ha adaptado para aplicaciones de estimación de estado recursivo, donde las medidas de entrada se hayan corrompido por los valores atípicos y los enfoques de filtro Kalman, que se basan en una distribución de Gauss del error de medición, están condenados al fracaso. Este enfoque, es apodado KALMANSAC.​

Referencias

• 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 (2003). Computer Vision, a modern approach. Prentice Hall. ISBN 0-13-085198-1. 
• Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in Computer Vision (2nd edición). 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». PhD Thesis. 
• Sunglok Choi, Taemin Kim, and Wonpil Yu (2009). «Performance Evaluation of RANSAC Family». In Proceedings of the British Machine Vision Conference (BMVC). 

• Anders Hast, Johan Nysjö, Andrea Marchetti (2013). «Optimal RANSAC – Towards a Repeatable Algorithm for Finding the Optimal Set». Journal of WSCG 21 (1): 21-30. 
• Hossam Isack, Yuri Boykov (2012). «Energy-based Geometric Multi-Model Fitting». International Journal of Computer Vision 97 (2: 1): 23-147. doi:10.1007/s11263-011-0474-7. 

Enlaces externos

• RANSAC Toolbox for MATLAB. Investigación orientada a explorar el algoritmo RANSAC en MATLAB. Es altamente configurable y contiene las rutinas para resolver algunos problemas de estimación pertinentes.
• ransac.m El algoritmo RANSAC en MATLAB.
• optimalRansac.m El algoritmo óptimo RANSAC en MATLAB.
• Implementation in C++ plantilla genérica.
• Implementation in C++ como una plantilla genérica con ejemplos hiperplano y HyperSphere.
• RANSAC for Dummies Un tutorial sencillo, con muchos ejemplos que utiliza la Caja de herramientas RANSAC para MATLAB.
• El código fuente para RANSAC en MATLAB
• Ransac.js aplicación Javascript con representación visual de las iteraciones (Ejemplo de Línea 2D ajuste).
• ransac.py aplicación Python para SciPy / NumPy.
• Scikit-learn and Scikit-image contiene las implementaciones de Python.
• GML RANSAC Matlab Toolbox – conjunto de secuencias de comandos de MATLAB, implementar familia algoritmo RANSAC.
• RANSAC for estimation of geometric transforms - ejemplos de MATLAB y ayuda sobre el uso RANSAC en aplicaciones de Visión por Computador
• RANSAC Algorithm - Información general del algoritmo RANSAC
• Random Sample Consensus - Random Sample Consesnsus: un paradigma para el modelo de montaje con Apphcatlons para Análisis de Imágenes y Cartografía Automatizada
• ACM Digital Library - Biblioteca para comprar el artículo original
• PCL - Como utilizar Random Sample Consensus model

[[Category:Geometry in computer vision] [[Category:Statistical algorithms] [[Category:Statistical outliers] [[Category:Robust statistics] [[Category:SRI International]