PDI+VC · Ejercicio de Programación

EP08_02 — 🟢 Homografía y RANSAC: La Votación por Inliers

8.14.2 EP08_02 🟢 Homografía y RANSAC: La Votación por Inliers

El RANSAC, presentado en la sección “Modelado Matemático: Homografía y RANSAC”, repite un ciclo de tres pasos — sortear una muestra mínima, estimar un modelo candidato y contar cuántas correspondencias son consistentes con él (los inliers) — manteniendo al final el modelo más votado. La etapa de estimación del modelo a partir de 4 puntos (paso 2) involucra álgebra lineal que queda fuera del alcance de este EP; aquí, recibes directamente un conjunto de homografías ya candidatas — como si cada una hubiera sido estimada a partir de una muestra aleatoria diferente — y tienes la tarea de reproducir exactamente el paso decisivo del algoritmo: aplicar cada modelo a todas las correspondencias y contar sus inliers, eligiendo al ganador.

8.14.2.1 📋 Directrices de Implementación

  1. Correspondencias: Leer el entero \(N\) y, a continuación, \(N\) líneas con cuatro reales cada una, \(x\ y\ x'\ y'\) — un punto de la imagen A y su correspondiente (posiblemente incorrecto) en la imagen B, exactamente como lo produce la etapa de matching del EP08_01.
  2. Modelos candidatos: Leer el entero \(K\) (número de homografías candidatas) y el real \(\varepsilon\) (umbral de error de reproyección). Luego, leer \(K\) líneas, cada una con nueve reales \(h_{11}\ h_{12}\ h_{13}\ h_{21}\ h_{22}\ h_{23}\ h_{31}\ h_{32}\ h_{33}\) — los elementos de la matriz \(H\) candidata, en orden de lectura por fila (row-major).
  3. Reproyección: Para cada correspondencia \((x,y,x',y')\) y cada modelo candidato \(H_k\), calcular el punto proyectado \[ \begin{bmatrix} \hat x \\ \hat y \\ \hat w \end{bmatrix} = H_k \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}, \qquad (\hat x / \hat w,\ \hat y / \hat w)\ \text{es el punto proyectado.} \]
  4. Error de reproyección: \(e = \sqrt{(\hat x/\hat w - x')^2 + (\hat y /\hat w - y')^2}\).
  5. Conteo de inliers: Una correspondencia es un inlier del modelo \(H_k\) si \(e \le \varepsilon\).
  6. Selección del mejor modelo: El modelo ganador es el que tiene mayor número de inliers; en caso de empate, elige el de menor índice \(k\) (el primero encontrado durante el ciclo iterativo del RANSAC).
  7. Salida: Para cada modelo \(k\) de \(0\) a \(K-1\), en el orden de lectura, imprime Modelo k: I inliers. Al final, imprime Mejor modelo: k_best con I_best inliers.

8.14.2.2 📌 Restricciones Computacionales

  • Comparación inclusiva: un error de reproyección exactamente igual a \(\varepsilon\) cuenta como inlier (\(e \le \varepsilon\)).
  • Sin estimación de \(H\): las matrices ya se proporcionan listas — no es necesario (ni esperado) resolver ningún sistema lineal.
  • Empate resuelto por el menor índice, reflejando el comportamiento natural de un algoritmo iterativo que recorre los modelos en orden y solo reemplaza al mejor encontrado hasta entonces cuando un nuevo modelo lo supera estrictamente.

8.14.2.3 🧠 Fundamentación Teórica

Elemento Papel en el RANSAC
Muestra mínima (4 pares) Suficiente para determinar los 8 grados de libertad de una homografía
Modelo candidato \(H_k\) Estimado a partir de una muestra mínima; puede ser bueno o malo, dependiendo de si la muestra contenía outliers
Error de reproyección Mide qué tan bien el modelo “predice” cada correspondencia observada
Inlier vs. outlier Correspondencias consistentes con el modelo ganador (inliers) vs. las demás, típicamente correspondencias incorrectas del matching
Refinamiento final En la práctica, tras elegir el mejor modelo, el RANSAC lo recalcula usando solo sus inliers — paso no exigido en este EP

8.14.2.4 📦 Especificación de Entrada y Salida (VPL)

Entrada:

  • Línea 1: Entero \(N\).
  • Siguientes \(N\) líneas: cuatro reales \(x\ y\ x'\ y'\).
  • Siguiente línea: Entero \(K\) y real \(\varepsilon\).
  • Siguientes \(K\) líneas: nueve reales (elementos de \(H_k\), row-major).

Salida:

  • \(K\) líneas en el formato Modelo k: I inliers.
  • Última línea: Mejor modelo: k_best con I_best inliers.

8.14.2.5 📌 Ejemplos

Entrada Salida Observación
5
0 0 0 0
1 1 2 2
2 0 4 0
0 2 0 4
5 5 1 1
2 0.5
2 0 0 0 2 0 0 0 1
1 0 0 0 1 0 0 0 1		 Modelo 0: 4 inliers
Modelo 1: 1 inliers
Mejor modelo: 0 con 4 inliers		 El Modelo 0 (escala ×2) explica correctamente 4 de las 5 correspondencias; la 5ª, \((5,5)\to(1,1)\), es un outlier que ninguno de los dos modelos explica bien.
🎮 Simulador EP08_02: RANSAC — Conteo de Inliers Modelo: Escala ×2
El modelo candidato mapea (x,y) → (2x,2y). Ajuste el umbral ε y vea qué correspondencias se vuelven inliers o outliers.
–
Figura 8.16: Simulador EP08_02: RANSAC — Votación por Inliers entre Modelos Candidatos 
%%writefile EP08_02.py
# Código Python
Overwriting EP08_02.py
TestSuite("EP08_02.py").run()
✔️ EP08_02.cases ya existe en casos/
📋 6 caso(s) cargado(s) de casos/EP08_02.cases

🔍 Probando Python: EP08_02.py
⚠️ EP08_02.py: archivo vacío (menos de 3 líneas). Pruebas omitidas.