RANSAC

De Wikipedia, la enciclopedia libre

Random sample consensus (RANSAC) es 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 solo 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 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, 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[editar]

Un ejemplo sencillo es la inserción de una línea 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 solo está calculado con los inliers, siempre que la probabilidad de elegir solo los inliers sea suficientemente alta. No hay ninguna garantía de que se cumpla esta situación, sin embargo, hay una serie de parámetros del algoritmo que deben elegirse cuidadosamente para mantener el nivel de probabilidad razonablemente alta.

Resumen[editar]

La entrada al algoritmo RANSAC está 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.

Algoritmo[editar]

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

Parámetros[editar]

Los valores de los parámetros y , 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 (número de iteraciones), sin embargo, se puede determinar a partir de un resultado teórico. El valor determina la probabilidad de que el algoritmo RANSAC seleccione solo inliers a partir del conjunto de datos de entrada cuando se eligen puntos con los que se estiman los parámetros del modelo. Cuando esto sucede, el modelo resultante probablemente es útil de modo que es la probabilidad que el algoritmo produzca un resultado útil. es la probabilidad de elegir un inlier cada vez que se selecciona un solo punto.

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

Un caso común es que no se conozca de antemano, pero se puede conocer algún valor. Suponiendo que los puntos necesarios para la estimación de un modelo se seleccionan independientemente, es la probabilidad de que todos los n puntos son inliers y 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 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 . Por consiguiente,

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

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 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 . La desviación típica de se define como

Ventajas y desventajas[editar]

Una ventaja de RANSAC es su capacidad para hacer una estimación robusta[1]​ 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 solo 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,[2]​ 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[editar]

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 y mejoras[editar]

Desde 1981 RANSAC se ha convertido en una herramienta fundamental en la comunidad de la visión por computador y procesamiento de imágenes. 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).[3]​ 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.[4]​ 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.[5]

Chum también propuso una versión aleatoria de RANSAC llamada R-RANSAC[6]​ para reducir la carga computacional para identificar una buena CS. La idea básica es evaluar inicialmente la eficacia del modelo actualmente instanciado utilizando solo 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[7]​ 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.[8]​ 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.[9]

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.[10]

Notas[editar]

  1. Robust Statistics, Peter. J. Huber, Wiley, 1981 (republished in paperback, 2004), page 1.
  2. 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.
  3. P.H.S. Torr and A. Zisserman, MLESAC: A new robust estimator with application to estimating image geometry, Journal of Computer Vision and Image Understanding 78 (2000), no. 1, 138–156.
  4. B. J. Tordoff and D. W. Murray, Guided-MLESAC: Faster image transform estimation by using matching priors, IEEE Transactions on Pattern Analysis and Machine Intelligence 27 (2005), no. 10, 1523–1535.
  5. Matching with PROSAC - progressive sample consensus, Proceedings of Conference on Computer Vision and Pattern Recognition (San Diego), vol. 1, June 2005, pp. 220–226
  6. O. Chum and J. Matas, Randomized RANSAC with Td,d test, 13th British Machine Vision Conference, September 2002.
  7. D. Nistér, Preemptive RANSAC for live structure and motion estimation, IEEE International Conference on Computer Vision (Nice, France), October 2003, pp. 199–206.
  8. H. Wang and D. Suter, Robust adaptive-scale parametric model estimation for computer vision., IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2004), no. 11, 1459-1474
  9. R. Toldo and A. Fusiello, Robust multiple structures estimation with jlinkage, European Conference on Computer Vision (Marseille, France), October 2008, pp. 537–547.
  10. A. Vedaldi, H. Jin, P. Favaro, and S. Soatto, KALMANSAC: Robust filtering by consensus, Proceedings of the International Conference on Computer Vision (ICCV), vol. 1, 2005, pp. 633–640

Referencias[editar]

Enlaces externos[editar]