PDI+VC · Ejercicio de Programación

EP02_04 — 📐 Transformada de Distancia en Imagen Binaria

2.12.4 EP02_04 📐 Transformada de Distancia en Imagen Binaria

Dada una imagen binaria donde los píxeles de valor 1 representan el objeto y los píxeles 0 representan el fondo, la distancia de un píxel de fondo recibe la menor distancia al píxel de objeto más cercano. Los píxeles de objeto reciben distancia 0. Para simplificar, considere que la imagen tiene solo un único objeto con un píxel de valor 1.

Problema: Lea una imagen binaria \(L \times C\) y una métrica, y calcule esa distancia simplificada aplicando una de las tres fórmulas:

\[d_{\text{Euclidiana}} = \sqrt{(\Delta r)^2 + (\Delta c)^2}\]

\[d_{\text{City-block}} = |\Delta r| + |\Delta c|\]

\[d_{\text{Chessboard}} = \max(|\Delta r|,\; |\Delta c|)\]

donde \(\Delta r\) es la diferencia de filas y \(\Delta c\) la diferencia de columnas entre dos píxeles.

2.12.4.1 🖼️ ¿Por qué es importante? - Aplicaciones de la DT

La Transformada de Distancia (DT) aparece en decenas de pipelines de visión por computadora:

Métrica Complejidad Aplicación típica
Euclidiana 🔴 \(O(n^2)\) ingenuo Esqueletización, emparejamiento de formas
City-block 🟡 \(O(n)\) con 2 pasadas Morfología, dilatación/erosión
Chessboard 🟢 \(O(n)\) con 2 pasadas Morfología, dilatación/erosión

2.12.4.2 📌 Requisitos Técnicos

  • Entrada: * Primera línea: \(L\) y \(C\) (enteros).
    • Segunda línea: nombre de la métrica (euclidean, cityblock o chessboard).
    • A continuación, la matriz binaria \(L \times C\) (valores 0 o 1).
  • Píxeles de objeto (1): distancia \(= 0\) (o \(0.00\) para euclidiana).
  • Píxeles de fondo (0): distancia al único píxel de objeto en la imagen.
  • Redondeo (euclidiana): imprimir con 2 decimales (formato :.2f). City-block y Chessboard producen enteros — imprimir sin decimales.
  • Salida: valores separados por espacio, una línea por fila de la matriz.
  • Ver en Figura 2.15 una simulación de este EP.

2.12.4.3 📌 Ejemplos

Entrada Salida Observación
4
4
chessboard
0 0 0 0
0 0 0 0
0 0 1 0
0 0 0 0		 2 2 2 2
2 1 1 1
2 1 0 1
2 1 1 1		 La distancia Chessboard es \(\max(\|dx\|, \|dy\|)\). El único píxel objeto es \((2,2)=0\); los demás almacenan su distancia mínima hasta él.

2.12.4.4 📌 Observaciones finales

  • Como la imagen tiene solo un objeto de un píxel, la distancia de cada píxel de fondo es simplemente la distancia de ese píxel al único punto objeto.
  • La implementación puede usar fuerza bruta (recorrer todos los píxeles de la imagen y calcular la distancia directamente), ya que \(L\) y \(C\) son pequeños en los casos de prueba.
  • Este problema es un calentamiento para la Transformada de Distancia general, que se trabajará en capítulos posteriores con múltiples objetos y algoritmos optimizados.
📐 Simulador EP02_04: Transformada de Distancia Interactiva Métricas: L₁, L₂ y L_∞

Haz clic sobre las celdas de la Imagen Binaria para alternar los píxeles del objeto (1) y observa el mapa de menor distancia calculado en la matriz resultante.

Métrica:
Imagen Binaria (Clic para Editar)
Transformada de Distancia
Cuadrícula 5×5 · 1 píxel(es) de objeto · Métrica: Chessboard (entero)
Figura 2.15: Simulador EP02_04: Transformada de Distância em Imagem Binária (Chessboard, City-block y Euclidiana) 
%%writefile EP02_04.py
# Código Python
Overwriting EP02_04.py
TestSuite("EP02_04.py").run()
✔️ EP02_04.cases ya existe en casos/
📋 5 caso(s) cargado(s) de casos/EP02_04.cases

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