Estos días he estado pensando y trabajando en una extensión de RANSAC que permita sacar varios modelos buenos en vez de sólo uno. El resultado ha sido el diseño de una leve mejora que he implementado junto con el método RANSAC original y el ajuste por mínimos cuadrados (el típico).
Para el que esté perdido, estamos hablando de métodos para obtener modelos, en este caso de rectas (pero son aplicables a cualquier otra cosa), en función a muestras que se acercan (o no) a la recta (o lo que sea) real.
El ajuste por mínimos cuadrados se puede considerar casi óptimo cuando todas las muestras son válidas. Si todas las muestras de las que se parte pertenecen al modelo da muy buenos resultados. Esto es lo que se suele dar en estadística de primero de carrera.
RANSAC (de Random Sample Consensous en inglés) lo que hace es generar varios modelos y quedarse con el que menos errores provoque. La generación de los distintos modelos se hace iterativamente. Para ello se selecciona aleatoriamente un conjunto de muestras del tamaño mínimo para generar un modelo y se van añadiendo uno a uno los puntos que estén cerca del modelo, actualizándolo conforme se van añadiendo puntos.
Cuando, en una iteración, el conjunto inicial contiene algún punto que realmente no pertenece a la recta, es muy difícil que haya puntos que estén de acuerdo con el modelo inducido por las muestras iniciales y, de haberlos, lo más probable es que provoquen un error muy alto. Además, los modelos apoyados por menos de un número configurable de puntos se descartan.
El método deja de iterar cuando se ha llegado al número máximo de iteraciones o cuando se obtiene un error suficientemente pequeño. Sea como sea, el resultado es el mejor de los que hayan generado.
El problema que tiene el método RANSAC normal es que, como he dicho, devuelve un único modelo y, como se ve en la foto, a veces puede interesarnos obtener varios modelos si es que están presentes. De ahí viene el método que me he inventado en base a RANSAC.
Lo que hago es quedarme con todas las soluciones de todas las iteraciones del método RANSAC y procesarlas para ver cuales me gustan. Para empezar me quedo con la mejor de la soluciones (como hace el RANSAC normal). A partir de ahi voy viendo las demás en orden ascendente de error y voy recogiéndolas siempre que:
- No tenga un tanto por ciento configurable de muestras en común con alguna de las que ya me he quedado (que provocan ménos error).
- El error sea menor que otro valor configurable.
Los resultados que me está dando son bastante buenos pero no lo suficiente como para publicarlos en Nature, así que he preferido subir el código que me he currado en python.
¡Ahí va!Otro método para hacer lo mismo más o menos es usar el RANSAC normal una y otra vez, quitando de la población muestral los puntos que estén relacionados con las solución de cada ejecución de RANSAC. Esto no me gusta:
- Puede haber puntos que sean muestra de dos modelos reales. Por tanto, no tiene sentido quitarlos, simplemente limitar la cantidad de puntos en común para obtener varias soluciones parecidas como resultado.
- Ejecutar RANSCAC n veces tarda más que ejecutar RANSAC una vez.
Para leer una explicación de verdad sobre RANSAC (la extensión que he hecho está más o menos bien explicada pero sé que la parte del RANSAC normal se puede mejorar):
- Paper original (el de verdad): Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.
- Página de RANSAC en la Güiquipeya: aquí
Me voy a dormir.
