PDI+VC · Ejercicio de Programación

EP08_01 — 🟢 Distancia de Hamming y Correspondencia de Descriptores Binarios

8.14.1 EP08_01 🟢 Distancia de Hamming y Correspondencia de Descriptores Binarios

ORB, utilizado en el Proyecto Práctico 1 de este capítulo, describe la vecindad de cada punto de interés como una secuencia de bits — y, por ello, la comparación entre dos descriptores no utiliza la distancia euclidiana del k-NN del Capítulo 7, sino la distancia de Hamming: el número de posiciones en que los bits difieren. Antes de llamar a cv2.BFMatcher(cv2.NORM_HAMMING), se te encargó implementar manualmente esta correspondencia (matching) por fuerza bruta — la misma etapa que, ejecutada internamente por OpenCV, precede a la estimación robusta de la homografía mediante RANSAC.

8.14.1.1 📋 Directrices de Implementación

  1. Cantidades: Leer los enteros \(N\) y \(M\) — número de descriptores extraídos de la imagen A y de la imagen B, respectivamente.
  2. Descriptores de A: Leer \(N\) líneas, cada una conteniendo un descriptor binario (una cadena de caracteres 0 y 1, todos de la misma longitud).
  3. Descriptores de B: Leer \(M\) líneas, en el mismo formato.
  4. Umbral: Leer el entero \(\tau\) — distancia de Hamming máxima aceptable para considerar una correspondencia válida.
  5. Distancia de Hamming: Para dos descriptores binarios \(a\) y \(b\) de igual longitud, \[ d_H(a, b) = \sum_{k} \mathbb{1}[a_k \neq b_k], \] es decir, el conteo de posiciones en que los bits difieren.
  6. Correspondencia por vecino más cercano: Para cada descriptor \(a_i\) de A (\(i\) en el orden de lectura, comenzando en \(0\)), calcula su distancia de Hamming a todos los descriptores de B y encuentra el de menor distancia. En caso de empate entre dos o más descriptores de B con la misma distancia mínima, elige el de menor índice.
  7. Filtrado por umbral: Si la menor distancia encontrada es \(\le \tau\), la correspondencia es válida; de lo contrario, \(a_i\) no posee correspondencia.
  8. Salida: Para cada \(i\) de \(0\) a \(N-1\), en el orden de lectura, imprimir una línea: i j d si hay correspondencia válida (donde \(j\) es el índice del descriptor de B elegido y \(d\) su distancia), o i -1 en caso contrario. Al final, imprimir Total correspondencias válidas: X.

8.14.1.2 📌 Restricciones Computacionales

  • Misma longitud: todos los descriptores (de A y de B) tienen exactamente el mismo número de bits.
  • Fuerza bruta: compara cada descriptor de A con todos los de B — no se necesita ningún tipo de indexación ni estructura de aceleración.
  • Desempate por menor índice en B, y nunca por orden de lectura de A (que ya es natural, pues cada \(a_i\) se trata de forma independiente).

8.14.1.3 🧠 Fundamentación Teórica

Elemento Papel en la correspondencia ORB
Descriptor binario (BRIEF) Cada bit es el resultado de una comparación de intensidad entre dos píxeles de la vecindad
Distancia de Hamming Métrica de disimilitud entre cadenas binarias; mucho más rápida de calcular que la distancia euclidiana (operación XOR + conteo de bits)
Vecino más cercano Criterio de correspondencia: cada punto de A se empareja con el punto de B cuyo descriptor sea más similar
Umbral \(\tau\) Filtra correspondencias poco confiables incluso antes del RANSAC — pero, como se discutió en el capítulo, algunas correspondencias incorrectas aún pasan, exigiendo la robustez del RANSAC

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

Entrada:

  • Línea 1: Enteros \(N\) y \(M\).
  • Siguientes \(N\) líneas: un descriptor binario por línea (cadena de 0s y 1s).
  • Siguientes \(M\) líneas: un descriptor binario por línea, en el mismo formato.
  • Última línea: Entero \(\tau\).

Salida:

  • \(N\) líneas, una por descriptor de A, en el formato i j d o i -1.
  • Última línea: Total correspondencias válidas: X.

8.14.1.5 📌 Ejemplos

Entrada Salida Observación
3 3
10101010
11110000
00001111
10101011
00001110
11111111
2		 0 0 1
1 -1
2 1 1
Total correspondencias válidas: 2		 El descriptor 11110000 no encuentra correspondencia: su vecino más cercano está a distancia 4, por encima del umbral \(\tau=2\).
🎮 Simulador EP08_01: Distancia de Hamming entre Descriptores Binarios Descriptores de 8 Bits
Haz clic en cualquier bit del Descriptor B para invertirlo y observa cómo cambia la distancia de Hamming en tiempo real.
Descriptor A (Fijo)
Descriptor B (Clic para Invertir)
–
Figura 8.15: Simulador EP08_01: Distancia de Hamming entre Dos Descriptores Binarios 
%%writefile EP08_01.py
# Código Python
Overwriting EP08_01.py
TestSuite("EP08_01.py").run()
✔️ EP08_01.cases ya existe en casos/
📋 6 caso(s) cargado(s) de casos/EP08_01.cases

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