RANSAC
- También llamado: Random Sample Consensus
- Categoría: Sensing › Perception outputs
- Etiquetas: robust-estimation, computer-vision, point-cloud-processing, outlier-rejection, model-fitting
Random Sample Consensus: un método de ajuste robusto que ajusta repetidamente un modelo a pequeños subconjuntos aleatorios de los datos y conserva el modelo con el que concuerdan más puntos, ignorando los valores atípicos.
Definición
RANSAC (Random Sample Consensus), introducido por Fischler y Bolles en 1981, estima los parámetros de un modelo a partir de datos que contienen muchos valores atípicos (outliers). El ajuste por mínimos cuadrados usa todos los puntos, así que unos pocos errores groseros pueden alejar mucho el resultado de la verdad. RANSAC, en cambio, repite un bucle sencillo: toma el número mínimo de puntos necesario para definir el modelo (dos para una recta, tres para un plano, un número fijo pequeño para una pose de cámara o una matriz fundamental), ajusta el modelo a ellos y cuenta cuántos de todos los puntos de datos quedan dentro de un umbral respecto a él. Esos puntos son el conjunto de consenso, o inliers. Tras un número de iteraciones, se conserva el modelo con el mayor conjunto de consenso, que normalmente se reajusta a todos sus inliers por mínimos cuadrados.
El número de iteraciones se deduce de la probabilidad. Si w es la fracción de inliers y s el tamaño de la muestra, una muestra aleatoria contiene solo inliers con probabilidad wˢ, así que el número de iteraciones k necesario para obtener al menos una muestra limpia con confianza p es k = log(1 − p) / log(1 − wˢ). Este número crece rápidamente cuando baja la fracción de inliers o aumenta el tamaño de la muestra, por lo que en visión importan los solucionadores mínimos que necesitan menos puntos, como el de pose relativa de cinco puntos. El umbral de inliers es el otro parámetro clave: debe corresponder al ruido esperado de los verdaderos inliers y hay que fijarlo en las unidades del residuo que se mide.
Muchas variantes mejoran el bucle básico. MSAC y MLESAC puntúan las hipótesis con un coste robusto en lugar de un recuento bruto de inliers, PROSAC muestrea primero las correspondencias más prometedoras, LO-RANSAC refina localmente las buenas hipótesis y las versiones adaptativas actualizan k a medida que se estima la fracción de inliers. En robótica, RANSAC se usa para la segmentación de planos y primitivas en nubes de puntos, el filtrado de correspondencias de características en odometría visual y SLAM, la estimación de pose Perspective-n-Point, el registro de nubes de puntos a partir de correspondencias de características y la calibración. Como el procedimiento es aleatorio, los resultados pueden diferir entre ejecuciones salvo que se fije la semilla aleatoria.
Por qué importa
Los datos reales de los sensores están llenos de valores atípicos: correspondencias de características erróneas, reflejos, objetos en movimiento y puntos que pertenecen a otras superficies. RANSAC es la forma estándar de ajustar modelos geométricos a pesar de ellos, y forma parte de la mayoría de las cadenas de procesamiento de odometría visual, SLAM, calibración y segmentación de nubes de puntos.
Aplicaciones clave
- Segmentación de planos, cilindros y esferas en nubes de puntos
- Rechazo de valores atípicos en correspondencias de características en odometría visual y SLAM
- Estimación de la pose de la cámara con Perspective-n-Point
- Estimación de matrices fundamentales, esenciales y de homografía
- Registro global de nubes de puntos a partir de correspondencias de características
- Ajuste de rectas y modelos de calibración a datos ruidosos de sensores
En la práctica
Un manipulador móvil necesita encontrar el tablero de una mesa en una nube de puntos de una cámara de profundidad antes de colocar objetos. El software submuestrea la nube y ejecuta un ajuste de plano con RANSAC: toma repetidamente tres puntos, calcula el plano que pasa por ellos y cuenta los puntos dentro de un umbral de distancia fijado ligeramente por encima del ruido de profundidad del sensor. El plano con más inliers se reajusta por mínimos cuadrados, se eliminan sus inliers y los puntos restantes por encima de él se agrupan en objetos. Los ingenieros comprueban que la normal del plano apunte aproximadamente hacia arriba, porque con una pared o un suelo grandes a la vista RANSAC puede devolver esa superficie en su lugar, y fijan la semilla aleatoria en las pruebas para que los resultados sean repetibles.
Ideas erróneas comunes
- RANSAC encuentra el modelo óptimo — devuelve la mejor hipótesis que le tocó muestrear, así que los resultados son probabilísticos y pueden diferir entre ejecuciones
- Más iteraciones compensan un umbral mal elegido — el umbral decide qué cuenta como concordancia, y una mala elección sesga el resultado por muchas iteraciones que se hagan
- RANSAC soporta cualquier proporción de valores atípicos — las iteraciones necesarias crecen rápidamente al bajar la fracción de inliers, y con muy pocos inliers puede fallar o fijarse en una estructura espuria
- RANSAC solo puede encontrar un modelo — el algoritmo básico encuentra uno, pero las variantes secuenciales y multimodelo extraen varias estructuras eliminando inliers y repitiendo
Quién debería saberlo
- Ingenieros de percepción y de visión por computadora
- Desarrolladores de SLAM y de odometría visual
- Ingenieros que procesan nubes de puntos para manipulación
- Ingenieros de calibración y metrología
Tecnologías relacionadas
- Ajuste por mínimos cuadrados (Least-Squares Fitting)
- M-estimadores (M-Estimators)
- MSAC y MLESAC
- PROSAC
- Transformada de Hough (Hough Transform)
- Point Cloud Library
Términos relacionados
- Point Cloud
- Perspective-n-Point
- Visual Odometry
- Iterative Closest Point
- Bundle Adjustment
- Extrinsic Calibration
Proyectos relacionados
- pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
- AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
- MRPT: Comprehensive C++ toolkit for mobile robotics, SLAM, and sensor-based navigation
- PULP-Dronet: Visual navigation for nano-drones with CNN inference onboard a PULP processor.
- OpenWeedLocator: Low-cost Raspberry Pi weed detector that uses computer vision for precision spot spraying
Vídeos
- RANSAC - 5 Minutes with Cyrill: Cyrill Stachniss
- Dealing with Outliers: RANSAC | Image Stitching: First Principles of Computer Vision