La segmentazione può avere obiettivi diversi a seconda della specifica applicazione. Le due letture principali viste a lezione sono:
La segmentazione oggetto/sfondo può essere un compito a volte semplice ma talvolta anche molto complesso: un oggetto scuro su fondo chiaro uniforme si separa con una soglia; un oggetto di colore e tessitura variabili, su fondo strutturato e con illuminazione non uniforme, richiede tutto l'arsenale di questo capitolo (e, per i casi difficili, le reti del capitolo 11).
Attenzione a non confondere questa segmentazione — di basso livello, basata su proprietà fotometriche — con la semantic segmentation del capitolo 11, che assegna a ogni pixel una classe di un insieme predefinito. Qui separiamo regioni omogenee, lì attribuiamo significato. Sono due problemi con lo stesso nome e obiettivi diversi.
Nel caso di una singola soglia globale T (per esempio quando c'è un solo oggetto), il metodo consiste nell'impostare a 0 i pixel la cui intensità è inferiore a T e a 1 i rimanenti:
⎧ 0 se I(x,y) < T
NewI(x,y) = ⎨
⎩ 1 se I(x,y) ≥ TSebbene molto semplice, il metodo presenta tre problemi ben precisi:
La mini-immagine 10×8 contiene un oggetto scuro su fondo chiaro, con l'opzione di aggiungere un gradiente di illuminazione e rumore. Cerca una soglia che funzioni in tutti i casi: nel caso col gradiente non esiste.
Il colore è spesso l'informazione più discriminante. L'esempio visto a lezione è la localizzazione del volto e delle sue componenti interne: nello spazio RGB le diverse regioni del volto non sono spazialmente raggruppate, mentre in HSI si notano cluster ben evidenti per bocca, occhi, pelle. È quindi relativamente semplice isolare tali caratteristiche — a patto di scegliere lo spazio colore giusto.
L'utilizzo di tecniche empiriche per estrarre le regioni dello spazio colore che contengono gli oggetti da segmentare non è raccomandabile (tranne nei casi molto semplici), per due ragioni:
50 < R < 60, 100 < G < 120, 90 < B < 140 — non porta a risultati molto accurati: la regione "vera" nello spazio colore non è quasi mai una scatola allineata agli assi.Molto meglio etichettare manualmente (per esempio racchiudendo con poligonali) le regioni di interesse su alcune immagini di training e lasciare a un classificatore il compito di individuare la sottoregione — anche non connessa — dello spazio colore. Terminato il training, il classificatore addestrato potrà essere utilizzato per segmentare nuove immagini. I vantaggi:
Nell'esempio del volto, i pixel di foreground sono definiti come i pixel interni a 3 poligoni marcati a mano, quelli di background come i pixel interni a 4 poligoni marcati a mano. Visualizzando il training set in una vista 2D (RG) dello spazio RGB si vedono le due nuvole, foreground in rosso e background in blu. Un classificatore bayesiano parametrico con distribuzioni multinormali viene addestrato a separare le due classi in RGB e applicato a una nuova immagine; il risultato si sovrappone all'immagine originale.
Lo stesso schema è stato applicato al problema del verde pubblico in un quartiere di Cesena: si etichettano a mano aree "verde pubblico" e aree "non verde pubblico" sullo stesso quartiere, si addestra il classificatore bayesiano in RGB e lo si applica a una nuova immagine.
Il punto da saper argomentare non è "quale classificatore", ma perché un classificatore batte una regola a soglie: le soglie indipendenti per canale definiscono un parallelepipedo allineato agli assi, mentre la regione di interesse nello spazio colore è tipicamente obliqua, curva e persino non connessa. Il classificatore la apprende dai dati e si riadatta rietichettando pochi esempi quando cambiano le condizioni.
La morfologia matematica, derivata dalla teoria degli insiemi, offre strumenti che consentono di estrarre informazioni utili per rappresentare la forma degli oggetti e di rimuovere particolari irrilevanti. Lavora solitamente su immagini binarie (foreground/background) — tipicamente il risultato di una binarizzazione come quella della sezione 2.
Gli operatori morfologici modificano il contenuto dell'immagine binaria applicando un elemento strutturante S, che può avere una qualsiasi forma rappresentabile tramite una maschera digitale; solitamente si utilizzano elementi strutturanti circolari o quadrati.
| Operatore | Definizione formale | Effetto |
|---|---|---|
| Erosione | F ⊖ S = { q | S_q ⊆ F } |
L'immagine risultante ha valore di foreground nei pixel q tali che, traslando in essi S, l'intero elemento strutturante è contenuto in F. Contrae gli insiemi connessi di pixel di foreground: assottiglia gli oggetti, separa oggetti debolmente connessi. |
| Dilatazione | F ⊕ S = { q | (S^r)_q ∩ F ≠ ∅ } |
L'immagine risultante ha valore di foreground nei pixel q tali che, traslando in essi S^r (il riflesso di S), almeno uno dei suoi elementi è contenuto in F. Espande gli insiemi connessi di foreground: aumenta le dimensioni degli oggetti, riempie buchi o zone vuote. |
Clicca le celle per disegnare la tua forma binaria (nero = foreground), poi applica gli operatori. Prova a costruire un oggetto con un buco e un sottile ponte, poi confronta opening e closing.
Combinando erosione e dilatazione si ottengono due operazioni derivate, che sono quelle davvero usate nella pratica:
| Operazione | Composizione | Effetto |
|---|---|---|
| Apertura (opening) | erosione + dilatazione | Separa oggetti debolmente connessi e rimuove regioni piccole. |
| Chiusura (closing) | dilatazione + erosione | Riempie buchi e piccole concavità, e rafforza la connessione di regioni unite debolmente. |
La logica è: la prima operazione produce l'effetto voluto (rimuovere il piccolo, oppure riempire il buco), la seconda ripristina approssimativamente la dimensione originale dell'oggetto. Per questo opening e closing sono preferibili all'erosione o alla dilatazione usate da sole.
Nei casi in cui lo sfondo è sufficientemente uniforme ma gli oggetti non sono caratterizzati da intensità (grigi) o colori uniformi, l'impiego di edge può aiutare nella segmentazione: un oggetto screziato non ha un'intensità caratteristica, ma ha comunque un contorno. La pipeline mostrata a lezione:
Un'ultima avvertenza vista a lezione: la segmentazione in presenza di rumore è sensibilmente più difficile. Il rumore produce falsi edge e falsi foreground; l'opening morfologico è lo strumento standard per rimuovere le piccole componenti spurie prima di ogni analisi successiva.
Gli oggetti di interesse possono essere individuati applicando algoritmi di clustering, per esempio K-Means. Il punto decisivo è che la scelta dello spazio delle feature è fondamentale.
Supponiamo di utilizzare solo il valore di intensità: lo spazio delle feature è monodimensionale e ogni pixel è un punto su una retta. I migliori centroidi sono quelli che minimizzano la Sum of Squared Distances:
SSD = Σ Σ ‖ p_j − c_i ‖
cluster C_i p_j ∈ C_iK-means si fonda su due domande complementari, che l'algoritmo risolve alternandole: conoscendo i centroidi, quali punti saranno assegnati a ogni cluster? e conoscendo l'attribuzione ai cluster, come determinare i centroidi?
Alterna manualmente i due passi dell'algoritmo e osserva la SSD scendere. Cambiando K o reinizializzando si vede anche il difetto principale: la sensibilità alla scelta iniziale dei centroidi.
Un feature space più rappresentativo consente di ottenere risultati migliori: usando la sola intensità si perdono le distinzioni cromatiche; usando il colore (RGB) la segmentazione migliora sensibilmente. Resta però un problema: oggetti distanti possono essere assegnati allo stesso cluster, perché nello spazio delle feature non c'è nulla che dica dove si trovano nell'immagine. La soluzione è codificare nello spazio delle feature anche informazioni spaziali (e volendo anche tessitura, gradiente, ...): il vettore di ciascun pixel diventa per esempio (R, G, B, x, y).
| K-means: pro | K-means: contro |
|---|---|
|
|
Mean Shift nasce per rimuovere due dei difetti di K-means: la necessità di fissare k e il vincolo dei cluster sferici. L'idea: ricercare i massimi locali di densità nello spazio delle feature.
Mean Shift è un algoritmo iterativo che considera lo spazio delle feature come una densità di probabilità empirica. L'input è un insieme di punti che possono essere considerati come campioni estratti dalla densità di probabilità in oggetto. Se esistono regioni dense (cluster) di punti, esse corrispondono alla moda (massimo locale) della distribuzione di probabilità; scopo dell'algoritmo è individuare questi punti di massimo locale.
Il vettore che va dal centro della finestra al centro di massa dei punti che contiene è il mean shift vector: seguirlo significa salire lungo il gradiente della densità. Le finestre (kernel) più usate sono Epanechnikov, uniforme e gaussiana.
Ogni finestra parte centrata su un punto (segmenti blu in alto). Premendo "Itera" ciascuna si sposta sulla media dei punti che contiene. Con una finestra piccola trovi molte mode; allargandola i cluster si fondono: la dimensione della finestra è l'unico parametro, e determina tutto.
Il cluster è definito come l'insieme dei punti che si trovano nello stesso bacino di attrazione di un massimo locale. L'algoritmo di segmentazione è quindi:
| Mean Shift: vantaggi | Mean Shift: svantaggi |
|---|---|
|
|
K-means e Mean Shift si scambiano un parametro con un altro: in K-means devi dire quanti cluster ci sono; in Mean Shift devi dire quanto sono larghi. Nessuno dei due elimina la scelta — ma la larghezza della finestra è spesso una grandezza fisica su cui si ha un'intuizione (quanto varia il colore dentro un oggetto), mentre il numero di oggetti in una scena, in generale, non lo si conosce.
1) La scelta automatica della soglia ottimale. 2) La non corretta gestione di sfondi a intensità variabile (es. gradienti di luce): una sola soglia non può funzionare su tutta l'immagine. 3) L'incapacità di segmentare oggetti non uniformi: se l'oggetto contiene sia pixel chiari sia scuri, nessuna soglia globale lo isola.
Perché range del tipo 50 < R < 60, 100 < G < 120, 90 < B < 140 definiscono un parallelepipedo allineato agli assi, che approssima male la regione di interesse nello spazio colore; inoltre l'approccio è difficilmente generalizzabile e richiede tarature manuali a ogni cambio di condizioni. Meglio etichettare a mano alcune regioni su immagini di training e lasciare a un classificatore (es. bayesiano parametrico con distribuzioni multinormali) il compito di individuare la sottoregione — anche non connessa — dello spazio colore.
Perché nello spazio RGB le diverse regioni del volto non sono spazialmente raggruppate, mentre in HSI si notano cluster ben evidenti per bocca, occhi e pelle: separare le classi diventa quindi relativamente semplice. È un esempio di come la scelta dello spazio di rappresentazione conti quanto l'algoritmo di classificazione.
Erosione: F ⊖ S = {q | S_q ⊆ F}, cioè il pixel q è foreground se traslando in esso l'elemento strutturante S questo è interamente contenuto in F; contrae gli insiemi di foreground. Dilatazione: F ⊕ S = {q | (S^r)_q ∩ F ≠ ∅}, cioè q è foreground se traslando in esso il riflesso S^r almeno un suo elemento cade in F; espande gli insiemi di foreground.
Opening = erosione seguita da dilatazione: separa oggetti debolmente connessi e rimuove regioni piccole. Closing = dilatazione seguita da erosione: riempie buchi e piccole concavità e rafforza la connessione di regioni unite debolmente. In entrambi i casi la seconda operazione serve a ripristinare approssimativamente la dimensione originale degli oggetti.
Conviene quando lo sfondo è uniforme ma gli oggetti non lo sono (intensità o colori non uniformi). Passi: 1) gradiente e binarizzazione; 2) dilatazione morfologica per chiudere il contorno; 3) riempimento dei buchi; 4) eliminazione delle componenti che toccano il bordo dell'immagine ed erosione morfologica per ripristinare le dimensioni.
Minimizza la Sum of Squared Distances: SSD = Σ_{cluster C_i} Σ_{p_j ∈ C_i} ‖p_j − c_i‖. Algoritmo: 1) inizializza casualmente i centri dei cluster; 2) assegna ogni punto p al cluster c_i più vicino; 3) ricalcola ogni c_i come media dei punti assegnati; 4) se i cluster sono cambiati, ripeti dal passo 2.
Pro: algoritmo molto semplice; converge a un minimo locale della funzione errore. Contro: elevata complessità computazionale; necessità di definire k; sensibilità alla scelta iniziale dei centroidi; sensibilità agli outlier; individua cluster di forma "sferica", non ottimale per alcune distribuzioni di pattern.
Perché lo spazio delle feature (per esempio la sola intensità, o il solo colore) non contiene informazione spaziale: due pixel dello stesso colore sono lo stesso punto, ovunque si trovino. La soluzione è codificare nello spazio delle feature anche informazioni spaziali — e all'occorrenza tessitura o gradiente — per esempio usando vettori (R, G, B, x, y).
1) Fissa una finestra attorno a ciascun punto; 2) calcola la media dei dati all'interno della finestra; 3) sposta la finestra centrandola sulla nuova media; 4) ripeti fino a convergenza. Lo spostamento è il mean shift vector e conduce la finestra verso il massimo locale di densità (la moda). Kernel tipici: Epanechnikov, uniforme, gaussiano.
1) Codificare l'immagine tramite feature; 2) inizializzare le finestre di osservazione (es. gaussiane) in corrispondenza di ciascun feature vector; 3) eseguire mean shift fino a convergenza; 4) fondere le finestre (pixel) che si riferiscono allo stesso massimo locale. Un cluster è l'insieme dei punti nello stesso bacino di attrazione di un massimo locale.
K-means richiede di fissare k, è sensibile all'inizializzazione e agli outlier e trova cluster sostanzialmente sferici. Mean Shift individua automaticamente i massimi locali, richiede un solo parametro (la dimensione della finestra) e rileva cluster di forma arbitraria; i suoi limiti sono la difficoltà di scegliere la finestra ottimale e l'inadeguatezza per feature ad alta dimensionalità.