PDI+VC · Ejercicio de Programación

EP08_05 — 🟡 Etiquetado de Componentes Conectados: Segmentación de Instancias

8.14.5 EP08_05 🟡 Etiquetado de Componentes Conectados: Segmentación de Instancias

El ejemplo de segmentación clásica de este capítulo separó “instancias” de monedas simplemente por su desconexión espacial en la máscara binaria resultante de la umbralización de Otsu. Esa etapa final — etiquetar cada componente conectado con un identificador de instancia — es exactamente lo que se te ha encargado implementar aquí, desde cero, sobre una máscara binaria ya preparada (0 = fondo, 1 = objeto), como si fuera una reimplementación manual de cv2.connectedComponents.

Este ejercicio también expone, de forma muy concreta, la limitación discutida en el capítulo: el resultado depende enteramente de cómo se define “vecindad” entre píxeles — y, como verás en el segundo ejemplo, dos píxeles en diagonal pueden considerarse la misma instancia o instancias diferentes, dependiendo exclusivamente de la conectividad elegida, no de ninguna noción semántica de objeto.

8.14.5.1 📋 Directrices de Implementación

  1. Entrada: Leer las dimensiones \(H \times W\) de la máscara binaria y sus \(H \times W\) valores (\(0\) o \(1\)).
  2. Conectividad: Leer el entero \(c \in \{4, 8\}\). En la conectividad \(4\), los vecinos de \((i,j)\) son \((i{-}1,j)\), \((i{+}1,j)\), \((i,j{-}1)\) y \((i,j{+}1)\). En la conectividad \(8\), se suman las cuatro diagonales: \((i{-}1,j{-}1)\), \((i{-}1,j{+}1)\), \((i{+}1,j{-}1)\) y \((i{+}1,j{+}1)\).
  3. Descubrimiento de componentes: Recorriendo la máscara en un barrido línea a línea, de izquierda a derecha y de arriba hacia abajo, siempre que se encuentre un píxel de valor \(1\) aún sin etiqueta, este inicia un nuevo componente: asígnale la siguiente etiqueta disponible (el primer componente descubierto recibe la etiqueta \(1\), el segundo la etiqueta \(2\), y así sucesivamente) y propaga esa misma etiqueta a todos los píxeles de valor \(1\) alcanzables desde él mediante una cadena de vecinos (de acuerdo con la conectividad elegida) — por búsqueda en anchura, en profundidad, o union-find, a tu elección.
  4. Píxeles de fondo: permanecen con etiqueta \(0\) y no pertenecen a ninguna instancia.
  5. Salida: Primero, imprimir el mapa de etiquetas completo — \(H\) líneas con \(W\) enteros cada una. A continuación, para cada etiqueta \(\ell\) de \(1\) a \(K\) (en el orden de descubrimiento), imprimir Instancia l: A píxeles, donde \(A\) es la cantidad de píxeles con esa etiqueta. Por último, imprimir Total de instancias: K.

8.14.5.2 📌 Restricciones Computacionales

  • Orden de descubrimiento = orden de barrido: las etiquetas se numeran en el orden en que cada nuevo componente se encuentra mediante el barrido línea a línea, no por tamaño ni posición.
  • Conectividad explícita: dos píxeles de valor \(1\) solo pertenecen a la misma instancia si existe una cadena de vecinos de acuerdo con \(c\) que los conecte entre sí — no uses la conectividad opuesta por error.
  • Máscara binaria pura: todos los valores de entrada son exactamente \(0\) o \(1\).

8.14.5.3 🧠 Fundamentación Teórica

Elemento Papel en la segmentación clásica de instancias
Umbralización (Otsu, Cap. 4) Etapa anterior que produce la máscara binaria a partir de la imagen de intensidad
Componente conectado Cada instancia se define solo por la conectividad espacial de los píxeles de objeto, sin ninguna noción de forma, clase o apariencia
Conectividad 4 vs. 8 Parámetro que altera el resultado: bajo conectividad 8, dos blobs unidos solo en diagonal se convierten en una única instancia
Limitación central La técnica fusiona instancias que se tocan o se superponen (aunque sean objetos claramente distintos), pues no hay noción de “objeto” — solo de “región conectada”

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

Entrada:

  • Línea 1: Enteros \(H\) y \(W\).
  • Siguientes \(H\) líneas: \(W\) enteros (\(0\) o \(1\)) cada una.
  • Última línea: Entero \(c\) (\(4\) o \(8\)).

Salida:

  • \(H\) líneas con \(W\) enteros cada una (el mapa de etiquetas).
  • Una línea por instancia, en el orden de descubrimiento: Instancia l: A píxeles.
  • Última línea: Total de instancias: K.

8.14.5.5 📌 Ejemplos

Entrada Salida Observación
6 6
0 0 0 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 1
0 0 0 0 1 1
8		 0 0 0 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 2 2
0 0 0 0 2 2
Instancia 1: 4 píxeles
Instancia 2: 4 píxeles
Total de instancias: 2		 Dos bloques \(2\times2\) claramente separados: el resultado es el mismo bajo conectividad 4 u 8.
2 2
1 0
0 1
8		 1 0
0 1
Instancia 1: 2 píxeles
Total de instancias: 1		 Bajo conectividad 8, los dos píxeles en diagonal pertenecen a la misma instancia. Repite este ejemplo con \(c=4\): el resultado pasa a ser 2 instancias de 1 píxel cada una — puramente por el cambio de conectividad, sin ninguna diferencia en la máscara.
🎮 Simulador EP08_05: Componentes Conexos (Conectividad 4 vs. 8) Misma Máscara → Etiquetas Diferentes
La misma máscara (dos píxeles en diagonal) — cambia la conectividad y observa cómo cambian el número de instancias y los colores de las etiquetas.
–
Figura 8.19: Simulador EP08_05: Etiquetado de Componentes Conectados — Conectividad 4 vs. 8 
%%writefile EP08_05.py
# Código Python
Overwriting EP08_05.py
TestSuite("EP08_05.py").run()
✔️ EP08_05.cases ya existe en casos/
📋 6 caso(s) cargado(s) de casos/EP08_05.cases

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