RANSAC

10. RANSAC. Ajuste a
modelos geométricos

Universidad de Valladolid

RANSAC
RANSAC es una abreviatura de “RANdom
SAmple Consensus”, que podría traducirse
como “consenso de una muestra escogida al
azar”.
RANSAC es un algoritmo de estimación
robusta que permite hallar un modelo
matemático a partir de datos contaminados con
numerosos valores que no se ajustan al
modelo (datos atípicos).
• VisiónArtificial Industrial. Univ. Valladolid

RANSAC
El algoritmo fue publicado por Fischler y Bolles
en 1981 y desde entonces se ha aplicado
profusamente en el análisis de imágenes.
RANSAC presenta una extraordinaria
capacidad para proporcionar un buen ajuste
a partir de datos contaminados con grandes
proporciones de outliers, superiores incluso
al 50% que es el límite insalvable para otras
técnicas deestimación robusta como
LMedianaS
• Visión Artificial Industrial. Univ. Valladolid

RANSAC
El algoritmo RANSAC busca el mejor modelo
considerando todos los pixeles de contorno
incluidos aquellos que no se ajustan al modelo
buscado. Para ello, selecciona aleatoriamente
muestras de s de píxeles, siendo s los puntos
necesarios para establecer los parámetros del
modelo: (2 para una línea, 3 parauna
circunferencia, 5 para una elipse…).

• Visión Artificial Industrial. Univ. Valladolid

RANSAC
Una vez calculados los parámetros para cada
muestra, se evalúa el conjunto de consenso
que es el número de píxeles de la imagen de
contornos original próximos al modelo
calculado dentro de una tolerancia
preestablecida.
Si el nuevo resultado es mejor, entonces se
reemplaza el resultado almacenado porel
nuevo.
• Visión Artificial Industrial. Univ. Valladolid

Algoritmo RANSAC para la
detección de Rectas.
 

Se repiten los siguientes pasos K veces
I. Hipótesis
(i) Se selecciona aleatoriamente de entre todos los píxeles una muestra de 2 píxeles
(ii) Se calculan los parámetros de la recta que pasa por los 2 píxeles.
II. Verificación
(iii)Determinar el conjunto de consenso, es decir, los pixelesde la imagen que se
ajustan a la recta hallada con una tolerancia t.
(iv)Si el número de inliers en el conjunto de consenso es el más alto encontrado,
guardar el modelo actual.
 

• Visión Artificial Industrial. Univ. Valladolid

Algoritmo RANSAC para la
detección de Rectas.
Si el número de puntos cercanos al modelo es
superior a un umbral preestablecido d, entonces el
ajuste será válido.
Elalgoritmo puede también parar cuando se
encuentre un modelo con un consenso superior a
este umbral.
 

• Visión Artificial Industrial. Univ. Valladolid

Detección de Rectas.

Ajustar a una recta los puntos de esta imagen

Detección de Rectas.

Elegir al azar dos puntos

Detección de Rectas.

Calcular la recta y el conjunto de consenso

Detección de Rectas.

Elegir al azar dos puntos

Detección deRectas.

Calcular la recta y el conjunto de consenso

Detección de Rectas.

Elegir al azar dos puntos

Detección de Rectas.

Calcular la recta y el conjunto de consenso

Detección de Rectas.

Elegir al azar dos puntos

Detección de Rectas.

Calcular la recta y el conjunto de consenso

Detección de Rectas.

Si el conjunto de consenso es suficientemente
grande consideramos el modelo comoválido

Parámetros del algoritmo RANSAC
 

El algoritmo necesita por tanto de tres parámetros para
controlar el proceso de estimación del modelo:
• El número máximo de iteraciones K que tiene que
realizar el algoritmo.
• La tolerancia t para determinar cuándo un pixel se
ajusta a un modelo.
• El número de inliers d que garantiza que un modelo
es válido

• Visión Artificial Industrial. Univ. ValladolidParámetros. Núm. de iteraciones K
El número de iteraciones K puede determinarse
teóricamente a partir de la probabilidad P de encontrar al
menos una muestra de puntos no contaminada por
outliers.
RANSAC no es un algoritmo determinista y por tanto
el modelo que proporciona es válido sólo con una
determinada probabilidad y esta probabilidad aumenta a
medida que se llevan a cabo más iteraciones....