EP02_04 — 📐 Transformada de Distância em Imagem Binária

2.12.4 EP02_04 📐 Transformada de Distância em Imagem Binária

Dada uma imagem binária onde pixels de valor 1 representam o objeto e pixels 0 representam o fundo, a distância de um pixel de fundo recebe a menor distância ao pixel de objeto mais próximo. Pixels de objeto recebem distância 0. Para simplificar, considere que a imagem tem apenas um único objeto com um pixel de valor 1.

Problema: Leia uma imagem binária \(L \times C\) e uma métrica, e calcule essa distância simplificada aplicando uma das três 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|)\]

onde \(\Delta r\) é a diferença de linhas e \(\Delta c\) a diferença de colunas entre dois pixels.

2.12.4.1 🖼️ Por que isso importa? - Aplicações da DT

A Transformada de Distância (DT) aparece em dezenas de pipelines de visão computacional:

Métrica	Complexidade	Aplicação típica
Euclidiana	🔴 \(O(n^2)\) ingênuo	Esqueletização, matching de formas
City-block	🟡 \(O(n)\) com 2 passes	Morfologia, dilatação/erosão
Chessboard	🟢 \(O(n)\) com 2 passes	Morfologia, dilatação/erosão

2.12.4.2 📌 Requisitos Técnicos

Entrada: * Primeira linha: \(L\) e \(C\) (inteiros).
- Segunda linha: nome da métrica (euclidean, cityblock ou chessboard).
- Em seguida, a matriz binária \(L \times C\) (valores 0 ou 1).
Pixels de objeto (1): distância \(= 0\) (ou \(0.00\) para euclidiana).
Pixels de fundo (0): distância ao único pixel de objeto na imagem.
Arredondamento (euclidiana): imprimir com 2 casas decimais (formato :.2f). City-block e Chessboard produzem inteiros — imprimir sem decimais.
Saída: valores separados por espaço, uma linha por linha da matriz.
Ver na Figura 2.15 uma simulação deste EP.

2.12.4.3 📌 Exemplos

Entrada	Saída	Observação
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	A distância Chessboard é \(\max(\\|dx\\|, \\|dy\\|)\). O único pixel objeto é \((2,2)=0\); os demais armazenam sua distância mínima até ele.

2.12.4.4 📌 Observações finais

Como a imagem tem apenas um objeto de um pixel, a distância de cada pixel de fundo é simplesmente a distância desse pixel ao único ponto objeto.
A implementação pode usar força bruta (percorrer todos os pixels da imagem e calcular a distância diretamente), pois \(L\) e \(C\) são pequenos nos casos de teste.
Este problema é um aquecimento para a Transformada de Distância geral, que será trabalhada em capítulos posteriores com múltiplos objetos e algoritmos otimizados.

📐 Simulador EP02_04: Transformada de Distância Interativa Métricas: L₁, L₂ e L_∞

Clique sobre as células da Imagem Binária para alternar os pixels do objeto (1) e observe o mapa de menor distância calculado na matriz resultante.

Métrica: Chessboard (L_∞) City-block (L₁) Euclidiana (L₂)

Imagem Binária (Clique para Editar)

Transformada de Distância

      Grade 5×5 · 1 pixel(s) de objeto · Métrica: Chessboard (inteiro)
    

Figura 2.15: Simulador EP02_04: Transformada de Distância em Imagem Binária (Chessboard, City-block e Euclidiana)

%%writefile EP02_04.cpp
// sua solução

Overwriting EP02_04.cpp

TestSuite("EP02_04.cpp").run()

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

🔍 Testando C++: EP02_04.cpp
⚠️ EP02_04.cpp: Arquivo sem conteúdo (menos de 3 linhas). Testes ignorados.