EP02_04 — 📐 Trasformata di Distanza in Immagine Binaria

2.12.4 EP02_04 📐 Trasformata di Distanza in Immagine Binaria

Data un’immagine binaria in cui i pixel di valore 1 rappresentano l’oggetto e i pixel 0 rappresentano lo sfondo, la distanza di un pixel di sfondo riceve la minore distanza al pixel dell’oggetto più vicino. I pixel dell’oggetto ricevono distanza 0. Per semplicità, si consideri che l’immagine ha un solo oggetto con un singolo pixel di valore 1.

Problema: Leggere un’immagine binaria \(L \times C\) e una metrica, e calcolare questa distanza semplificata applicando una delle tre formule:

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

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

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

dove \(\Delta r\) è la differenza di righe e \(\Delta c\) la differenza di colonne tra due pixel.

2.12.4.1 🖼️ Perché è importante? - Applicazioni della DT

La Trasformata di Distanza (DT) compare in decine di pipeline di visione artificiale:

Metrica	Complessità	Applicazione tipica
Euclidea	🔴 \(O(n^2)\) ingenuo	Scheletrizzazione, matching di forme
City-block	🟡 \(O(n)\) con 2 passaggi	Morfologia, dilatazione/erosione
Scacchiera	🟢 \(O(n)\) con 2 passaggi	Morfologia, dilatazione/erosione

2.12.4.2 📌 Requisiti Tecnici

Input: * Prima riga: \(L\) e \(C\) (interi).
- Seconda riga: nome della metrica (euclidean, cityblock o chessboard).
- Successivamente, la matrice binaria \(L \times C\) (valori 0 o 1).
Pixel dell’oggetto (1): distanza \(= 0\) (o \(0.00\) per euclidea).
Pixel di sfondo (0): distanza all’unico pixel dell’oggetto nell’immagine.
Arrotondamento (euclidea): stampare con 2 cifre decimali (formato :.2f). City-block e Scacchiera producono interi — stampare senza decimali.
Output: valori separati da spazio, una riga per ogni riga della matrice.
Vedere in Figura 2.15 una simulazione di questo EP.

2.12.4.3 📌 Esempi

Input	Output	Osservazione
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 distanza Scacchiera è \(\max(\\|dx\\|, \\|dy\\|)\). L’unico pixel oggetto è \((2,2)=0\); gli altri memorizzano la loro distanza minima fino ad esso.

2.12.4.4 📌 Osservazioni finali

Poiché l’immagine ha un solo oggetto di un pixel, la distanza di ogni pixel di sfondo è semplicemente la distanza di quel pixel all’unico punto dell’oggetto.
L’implementazione può usare la forza bruta (percorrere tutti i pixel dell’immagine e calcolare la distanza direttamente), poiché \(L\) e \(C\) sono piccoli nei casi di test.
Questo problema è un riscaldamento per la Trasformata di Distanza generale, che verrà affrontata nei capitoli successivi con più oggetti e algoritmi ottimizzati.

📐 Simulatore EP02_04: Trasformata della Distanza Interattiva Metriche: L₁, L₂ e L_∞

Clicca sulle celle dell'Immagine Binaria per alternare i pixel dell'oggetto (1) e osserva la mappa della distanza minima calcolata nella matrice risultante.

Metri: Chessboard (L_∞) City-block (L₁) Euclidea (L₂)

Immagine Binaria (Clicca per Modificare)

Trasformata della Distanza

      Griglia 5×5 · 1 pixel di oggetto · Metrica: Chessboard (intero)
    

Figura 2.15: Simulatore EP02_04: Trasformata della Distanza in Immagine Binaria (Scacchiera, City-block ed Euclidea)

%%writefile EP02_04.cpp
// your solution

Overwriting EP02_04.cpp

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

✔️ EP02_04.cases esiste già in casos/
📋 5 caso/i caricato/i da casos/EP02_04.cases

🔍 Test di C++: EP02_04.cpp
⚠️ EP02_04.cpp: file vuoto (meno di 3 righe). Test saltati.