EDI+VA · Esercizio di Programmazione

EP08_05 — 🟡 Etichettatura dei Componenti Connessi: Segmentazione delle Istanze

8.14.5 EP08_05 🟡 Etichettatura dei Componenti Connessi: Segmentazione delle Istanze

L’esempio di segmentazione classica di questo capitolo ha separato le “istanze” delle monete semplicemente tramite la loro disconnessione spaziale nella maschera binaria risultante dalla sogliatura di Otsu. Questa fase finale — etichettare ogni componente connesso con un identificatore di istanza — è esattamente ciò che ti è stato richiesto di implementare qui, da zero, su una maschera binaria già pronta (0 = sfondo, 1 = oggetto), come se fosse una reimplementazione manuale di cv2.connectedComponents.

Questo esercizio mette inoltre in luce, in modo molto concreto, la limitazione discussa nel capitolo: il risultato dipende interamente da come si definisce la “vicinanza” tra i pixel — e, come vedrai nel secondo esempio, due pixel in diagonale possono essere considerati la stessa istanza o istanze diverse, dipendendo esclusivamente dalla connettività scelta, non da alcuna nozione semantica di oggetto.

8.14.5.1 📋 Linee Guida di Implementazione

  1. Input: Leggere le dimensioni \(H \times W\) della maschera binaria e i suoi \(H \times W\) valori (\(0\) o \(1\)).
  2. Connettività: Leggere l’intero \(c \in \{4, 8\}\). Con connettività \(4\), i vicini di \((i,j)\) sono \((i{-}1,j)\), \((i{+}1,j)\), \((i,j{-}1)\) e \((i,j{+}1)\). Con connettività \(8\), si aggiungono le quattro diagonali: \((i{-}1,j{-}1)\), \((i{-}1,j{+}1)\), \((i{+}1,j{-}1)\) e \((i{+}1,j{+}1)\).
  3. Scoperta dei componenti: Scorrendo la maschera in scansione riga per riga, da sinistra a destra e dall’alto verso il basso, ogni volta che si incontra un pixel di valore \(1\) non ancora etichettato, questo dà inizio a una nuova componente: assegnagli la prossima etichetta disponibile (la prima componente scoperta riceve l’etichetta \(1\), la seconda l’etichetta \(2\), e così via) e propaga la stessa etichetta a tutti i pixel di valore \(1\) raggiungibili da esso tramite una catena di vicini (secondo la connettività scelta) — tramite ricerca in ampiezza, in profondità, o union-find, a tua scelta.
  4. Pixel di sfondo: rimangono con etichetta \(0\) e non appartengono a nessuna istanza.
  5. Output: Prima, stampare la mappa completa delle etichette — \(H\) righe con \(W\) interi ciascuna. Successivamente, per ogni etichetta \(\ell\) da \(1\) a \(K\) (nell’ordine di scoperta), stampare Istanza l: A pixel, dove \(A\) è la quantità di pixel con quella etichetta. Infine, stampare Totale istanze: K.

8.14.5.2 📌 Vincoli Computazionali

  • Ordine di scoperta = ordine di scansione: le etichette sono numerate nell’ordine in cui ogni nuova componente viene trovata dalla scansione riga per riga, non per dimensione o posizione.
  • Connettività esplicita: due pixel di valore \(1\) appartengono alla stessa istanza solo se esiste una catena di vicini secondo \(c\) che li collega — non usare per errore la connettività opposta.
  • Maschera binaria pura: tutti i valori di input sono esattamente \(0\) o \(1\).

8.14.5.3 🧠 Fondamenti Teorici

Elemento Ruolo nella segmentazione classica delle istanze
Sogliatura (Otsu, Cap. 4) Fase precedente che produce la maschera binaria a partire dall’immagine di intensità
Componente connessa Ogni istanza è definita solo dalla connettività spaziale dei pixel dell’oggetto, senza alcuna nozione di forma, classe o aspetto
Connettività 4 vs. 8 Parametro che altera il risultato: con connettività 8, due blob uniti solo in diagonale diventano un’unica istanza
Limitazione centrale La tecnica fonde istanze che si toccano o si sovrappongono (anche se sono oggetti chiaramente distinti), poiché non c’è nozione di “oggetto” — solo di “regione connessa”

8.14.5.4 📦 Specifica di Input e Output (VPL)

Input:

  • Riga 1: Interi \(H\) e \(W\).
  • Prossime \(H\) righe: \(W\) interi (\(0\) o \(1\)) ciascuna.
  • Ultima riga: Intero \(c\) (\(4\) o \(8\)).

Output:

  • \(H\) righe con \(W\) interi ciascuna (la mappa delle etichette).
  • Una riga per istanza, nell’ordine di scoperta: Istanza l: A pixel.
  • Ultima riga: Totale istanze: K.

8.14.5.5 📌 Esempi

Input Output Osservazione
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
Istanza 1: 4 pixel
Istanza 2: 4 pixel
Totale istanze: 2		 Due blocchi \(2\times2\) chiaramente separati: il risultato è lo stesso con connettività 4 o 8.
2 2
1 0
0 1
8		 1 0
0 1
Istanza 1: 2 pixel
Totale istanze: 1		 Con connettività 8, i due pixel in diagonale appartengono alla stessa istanza. Ripeti questo esempio con \(c=4\): il risultato diventa 2 istanze di 1 pixel ciascuna — puramente per il cambiamento di connettività, senza alcuna differenza nella maschera.
🎮 Simulatore EP08_05: Componenti Connessi (Connettività 4 vs. 8) Stessa Maschera → Etichette Diverse
La stessa maschera (due pixel in diagonale) — alterna la connettività e osserva il numero di istanze e i colori delle etichette cambiare.
–
Figura 8.19: Simulatore EP08_05: Etichettatura delle Componenti Connesse — Connettività 4 vs. 8 
%%writefile EP08_05.py
# Codice Python
Overwriting EP08_05.py
TestSuite("EP08_05.py").run()
✔️ EP08_05.cases esiste già in casos/
📋 6 caso/i caricato/i da casos/EP08_05.cases

🔍 Test di Python: EP08_05.py
⚠️ EP08_05.py: file vuoto (meno di 3 righe). Test saltati.