EP08_05 — 🟡 Rotulação de Componentes Conectados: Segmentação de Instâncias

8.14.5 EP08_05 🟡 Rotulação de Componentes Conectados: Segmentação de Instâncias

O exemplo de segmentação clássica deste capítulo separou “instâncias” de moedas simplesmente pela sua desconexão espacial na máscara binária resultante da limiarização de Otsu. Essa etapa final — rotular cada componente conectado com um identificador de instância — é exatamente o que você foi encarregado de implementar aqui, do zero, sobre uma máscara binária já pronta (0 = fundo, 1 = objeto), como se fosse uma reimplementação manual de cv2.connectedComponents.

Este exercício também expõe, de forma muito concreta, a limitação discutida no capítulo: o resultado depende inteiramente de como se define “vizinhança” entre pixels — e, como você verá no segundo exemplo, dois pixels em diagonal podem ser considerados a mesma instância ou instâncias diferentes, dependendo exclusivamente da conectividade escolhida, não de qualquer noção semântica de objeto.

8.14.5.1 📋 Diretrizes de Implementação

Entrada: Ler as dimensões \(H \times W\) da máscara binária e seus \(H \times W\) valores (\(0\) ou \(1\)).
Conectividade: Ler o inteiro \(c \in \{4, 8\}\). Na conectividade \(4\), os vizinhos de \((i,j)\) são \((i{-}1,j)\), \((i{+}1,j)\), \((i,j{-}1)\) e \((i,j{+}1)\). Na conectividade \(8\), somam-se as quatro diagonais: \((i{-}1,j{-}1)\), \((i{-}1,j{+}1)\), \((i{+}1,j{-}1)\) e \((i{+}1,j{+}1)\).
Descoberta de componentes: Percorrendo a máscara em varredura linha a linha, da esquerda para a direita e de cima para baixo, sempre que um pixel de valor \(1\) ainda sem rótulo for encontrado, ele inicia um novo componente: atribua a ele o próximo rótulo disponível (o primeiro componente descoberto recebe o rótulo \(1\), o segundo o rótulo \(2\), e assim por diante) e propague esse mesmo rótulo a todos os pixels de valor \(1\) alcançáveis a partir dele por uma cadeia de vizinhos (de acordo com a conectividade escolhida) — por busca em largura, profundidade, ou union-find, à sua escolha.
Pixels de fundo: permanecem com rótulo \(0\) e não pertencem a nenhuma instância.
Saída: Primeiro, imprimir o mapa de rótulos completo — \(H\) linhas com \(W\) inteiros cada. Em seguida, para cada rótulo \(\ell\) de \(1\) a \(K\) (na ordem de descoberta), imprimir Instância l: A pixels, onde \(A\) é a quantidade de pixels com aquele rótulo. Por fim, imprimir Total de instâncias: K.

8.14.5.2 📌 Restrições Computacionais

Ordem de descoberta = ordem de varredura: os rótulos são numerados na ordem em que cada novo componente é encontrado pela varredura linha a linha, não por tamanho ou posição.
Conectividade explícita: dois pixels de valor \(1\) só pertencem à mesma instância se existir uma cadeia de vizinhos de acordo com \(c\) ligando um ao outro — não use a conectividade oposta por engano.
Máscara binária pura: todos os valores de entrada são exatamente \(0\) ou \(1\).

8.14.5.3 🧠 Fundamentação Teórica

Elemento	Papel na segmentação clássica de instâncias
Limiarização (Otsu, Cap. 4)	Etapa anterior que produz a máscara binária a partir da imagem de intensidade
Componente conectado	Cada instância é definida apenas por conectividade espacial dos pixels de objeto, sem qualquer noção de forma, classe ou aparência
Conectividade 4 vs. 8	Parâmetro que altera o resultado: sob conectividade 8, dois blobs unidos apenas na diagonal tornam-se uma única instância
Limitação central	A técnica funde instâncias que se tocam ou se sobrepõem (mesmo que sejam objetos claramente distintos), pois não há noção de “objeto” — apenas de “região conectada”

8.14.5.4 📦 Especificação de Entrada e Saída (VPL)

Entrada:

Linha 1: Inteiros \(H\) e \(W\).
Próximas \(H\) linhas: \(W\) inteiros (\(0\) ou \(1\)) cada.
Última linha: Inteiro \(c\) (\(4\) ou \(8\)).

Saída:

\(H\) linhas com \(W\) inteiros cada (o mapa de rótulos).
Uma linha por instância, na ordem de descoberta: Instância l: A pixels.
Última linha: Total de instâncias: K.

8.14.5.5 📌 Exemplos

Entrada	Saída	Observação
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 Instância 1: 4 pixels Instância 2: 4 pixels Total de instâncias: 2	Dois blocos \(2\times2\) claramente separados: o resultado é o mesmo sob conectividade 4 ou 8.
2 2 1 0 0 1 8	1 0 0 1 Instância 1: 2 pixels Total de instâncias: 1	Sob conectividade 8, os dois pixels em diagonal pertencem à mesma instância. Repita este exemplo com \(c=4\): o resultado passa a ser 2 instâncias de 1 pixel cada — puramente pela mudança de conectividade, sem qualquer diferença na máscara.

🎮 Simulador EP08_05: Componentes Conectados (Conectividade 4 vs. 8) Mesma Máscara → Rótulos Diferentes

A mesma máscara (dois pixels na diagonal) — alterne a conectividade e observe o número de instâncias e as cores dos rótulos mudarem.

–

Figura 8.19: Simulador EP08_05: Rotulação de Componentes Conectados — Conectividade 4 vs. 8

%%writefile EP08_05.py
# Código Python

Writing EP08_05.py

TestSuite("EP08_05.py").run()

✔️ EP08_05.cases já existe em casos/
📋 6 caso(s) carregado(s) de casos/EP08_05.cases

🔍 Testando Python: EP08_05.py
⚠️ EP08_05.py: Arquivo sem conteúdo (menos de 3 linhas). Testes ignorados.