Tecniche di segmentazione

Quello che vogliamo fare è dividere la singola immagine in un insieme di regioni, o partizioni, che non si sovrappongano tra di loro; in queste regioni, i punti dell'immagine condividono tra loro una caratteristica, che può essere per esempio

• il colore
• la tessitura dell'immagine
• ...

Alcune caratteristiche di basso livello (low-level features, LLF) vengono combinate tra di loro all'interno dell'immagine, in una maniera tale da creare delle diverse regioni; per esempio, in un panorama, il cielo sarà azzurro, la chioma di un albero sarà verde ed il suo tronco marrone, ... gli algoritmi di segmentazione sono in grado di trovare le aree che hanno caratteristiche simili, ma non si occupano di interpretare le figure, non sono in grado di riconoscere, da una regione marrone ed una verde, se nell'immagine appare un albero o un qualsiasi altro oggetto.

Capire che oggetti contiene l'immagine è il passo successivo, l'etichettatura, attraverso la quale si potrà poi fare un'analisi semantica dell'immagine, cioè si potrà capire se l'immagine contiene un panorama piuttosto che un viso o chissà cos'altro.

${\text{Pixel}}\to {\text{Simboli}}\to {\text{Semantica}}$

La segmentazione dell'immagine è un'operazione strettamente collegata all'edge detection, la ricerca dei punti di bordo presenti nelle sequenze bidimensionali; la differenza fondamentale, però, è che con l'edge detection non si cercano delle regioni, i tratti ed i bordi risultanti da questi algoritmi non saranno, di norma, chiusi, non ci sarà una partizione dell'immagine. Al contrario, la segmentazione è quell'operazione che mira ad identificare gli oggetti nell'immagine, a dar loro un bordo chiuso e netto.

Per ottenere la segmentazione dell'immagine, dobbiamo domandarci qual è la caratteristica, la feature, che vogliamo indagare e che meglio ci permetterà di ottenere il risultato cercato; non sempre la luminanza ed i colori possono aiutarci in questa impresa. Il concetto fondamentale da comprendere è che la segmentazione di un'immagine non è univoca, indagando caratteristiche diverse si otterranno segmentazioni diverse, utilizzando algoritmi diversi si otterranno risultati diversi.

Segmentazione ad alto livello

La segmentazione si compone di due passaggi in cascata:

• individuazione delle caratteristiche dell'immagine, cioè si individuano delle caratteristiche che possono essere utili per segmentare l'immagine;
• etichettatura delle regioni, cioè si assegnano delle etichette, label, alle diverse regioni.

Alla fine del processo di etichettatura, otterremo una nuova sequenza bidimensionale $L[m,n]$ all'interno della quale avremo gli indici dell'insieme delle etichette,

$\mathbb {L} =\{l_{1},l_{2},\cdots ,l_{p}\}$

cioè

$L[m,n]=l_{i}\in \mathbb {L} \ \forall m,n\in D$

dove $D$ è il dominio di definizione dell'immagine originale,

$D=D\left(I[m,n]\right)=(1,2,\cdots ,M)\times (1,2,\cdots ,N)$

Tutti i punti di $L[m,n]$ con lo stesso valore identificano una regione $R_{i,j}$; ad ogni singolo pixel dell'immagine non può essere assegnata più di una etichetta, quindi ogni algoritmo di segmentazione restituirà un partizionamento univoco dell'immagine. Se i punti con la stessa etichetta sono vicini tra loro, allora è possibile definire le regioni $R_{i,j}$ che riassumono una zona dell'immagine; queste regioni contengono $N_{i}$ punti, è la loro cardinalità.

Grazie alla segmentazione, otteniamo che il dominio dell'immagine $D$ è separato in diverse regioni,

$D\left(I[m,n]\right)=\bigcup _{i=0}^{p}\left[\sum _{j=1}^{N_{i}}R_{i,j}\right]$

$R_{i,j}\cap R_{k,l}=\varnothing \ \forall i\neq k,j\neq l$

Esempio: Esempio di segmentazione

Abbiamo un'immagine, un panorama con un sole giallo, un albero verde e marrone, un prato verde ed un cielo azzurro. Assegnamo le etichette $V$ alle zone verdi, $M$ alle zone marroni, $A$ alle zone azzurre e $G$ alle zone gialle. Abbiamo

$\mathbb {L} =\{V=l_{1},M=l_{2},A=l_{3},G=l_{4}\}$

Queste etichette identificano più regioni:

• un prato verde, $R_{1,1}$;
• la chioma verde dell'albero, $R_{1,2}$
• il tronco marrone dell'albero, $R_{2,1}$
• il cielo azzurro, $R_{3,1}$
• il sole giallo, $R_{4,1}$

Si ha

$D=\left(R_{11}\cup R_{12}\right)\cup R_{21}\cup R_{31}\cup R_{41}$

Riassumendo, dobbiamo identificare:

• la caratteristica (feature) che vogliamo indagare; questo parametro dipende in maniera significativa dall'applicazione che abbiamo in mente (può essere il moto, il colore, la varianza dei dati, la tessitura,...);
• il criterio di omogeneità, che dipende a sua volta dall'applicazione.

Il criterio di omogeneità è quel criterio che ci permette di dire se due punti, con caratteristiche simili, possono essere considerati parte della stessa regione oppure no. Per esempio, dei criteri possono essere:

• la forma;
• la dimensione;
• il contesto;
• ...

Criteri di unione

Abbiamo due regioni, una vicina all'altra, e vogliamo capire se queste due regioni possono essere considerate un'unica regione oppure no. Come possiamo capire se le caratteristiche delle due regioni sono compatibili? la prima idea è quella di calcolare la distanza tra i valori medi delle regioni, per vedere se questa distanza supera un certo valore di soglia (threshold):

$C_{1}=\left|\mu ^{(0)}-\mu ^{(1)}\right|<T$

Questo criterio, molto semplice, sperimentalmente porta ad avere delle regioni molto piccole (rumore), separate tra loro da altre regioni molto grandi. Il criterio può essere migliorato tentendo in considerazione la cardinalità delle regioni, la loro dimensione:

$C_{2}=\left|N^{0}\cdot \mu ^{(0)}-N^{1}\cdot \mu ^{(0)}\right|$

Un ulteriore miglioramento può essere la distanza

$C_{3}=|\mu _{0}-\mu |$

dove definiamo

$\mu ={\frac {N_{0}\cdot \mu ^{0}+N_{1}\cdot \mu ^{1}}{N_{0}+N_{1}}}$

Utilizzando quest'ultimo metodo, le regioni più grandi andranno a conquistare le regioni più piccole: questo fatto può essere una cosa buona in alcune applicazioni, un disastro per altre.

Approcci alla segmentazione

La segmentazione può essere ottenuta con diversi algoritmi, che ricadono in una catalogazione di questo tipo:

• approccio stocastico

1. soglia sull'istogramma;
2. Markov random fields;

• approccio deterministico

1. top-down;
2. bottom-up;
3. unione dei due precedenti.

Soglia sull'istogramma

1. creare un istogramma che descrive la caratteristica scelta;

2. dividere l'istogramma in canali (bin) significativi, assegnando un'etichetta ad ognuno di questi canali;

3. per ogni punto $[m,n]$ dell'immagine, eseguire lo pseudoalgoritmo

 if (T[m,n] \in T_i)
 then
    L[m,n]=l_i</math>
 end

4. tutti i punti che hanno gli stessi $l_{i}$ definiscono una certa regione $R_{i,j}$.

Esempio:

Supponiamo di usare il valore dei pixel come caratteristica, possiamo dividere l'istogramma in tre canali uguali; si identificano due soglie $k_{0}$ e $k_{1}$ per identificare i tre canali $I_{0}$, $I_{1}$ e $I_{3}$.

L'algoritmo sarà

   if (I[m,n] < k_0)
      L[m,n]=l_1
   elseif (I[m,n] < k_1)
      L[m,n]=l_2
   else
      L[m,n]=l_3
   end

Approccio top-down

Il metodo top-down, come suggerisce il nome, prevede un approccio dall'alto verso il basso, cioè da una descrizione ad alto livello fino a scendere nel dettaglio.

Fit di equazioni

Un primo metodo può essere quello di trovare alcune regioni omogenee con una soglia sull'istogramma, per poi tentare di approssimare le regioni con delle equazioni, delle curve matematiche che descrivano in maniera compressa l'andamento del valore dei dati:

• piani;
• curve;
• figure geometriche;
• ...

Una volta generate le equazioni che meglio descrivono la regione trovata dal primo metodo, si procede alla misurazione del valore quadratico medio dell'errore tra il valore di ogni singolo punto e quello dell'equazione trovata: se l'errore è piccolo, allora si considera il punto come appartenente alla regione $R_{i}$, al contrario non si assegna alcuna etichetta.

Procedendo nella creazione di diverse curve per le varie regioni di partenza, si otterrà, alla fine, il risultato cercato.

Decomposizione ad albero

Uno schema ad albero.

Vogliamo schematizzare la suddivisione dello spazio delle immagini con uno schema ad albero; ad ogni iterazione, si dividerà il blocco di lavoro in più sottoregioni: se queste risultano omogenee tra loro, allora la segmentazione è finita e si può passare al ramo successivo dell'albero, mentre se queste regioni risultano non-omogenee allora si creano dei nuovi nodi ricorsivi che permettono di continuare l'albero.

Ci sono diversi metodi per dividere le regioni in esame:

• quad-tree decomposition

Si va a dividere il rettangolo in esame in 4 rettangoli uguali come in figura; alla fine dell'algoritmo ricorsivo, avremo un albero le cui foglie descrivono dei piccoli rettangoli all'interno dei quali la varianza dei dati è bassa.

Procedendo dall'alto verso il basso nello schema, si hanno rettangoli annidati sempre più piccoli tra loro.

• binary-tree decomposition

Con decomposizione binaria, ogni rettangolo viene diviso in due sottorettangoli, che possono avere caratteristiche diverse:

1. orizzontale oppure verticale;
2. soltanto orizzontale;
3. soltanto verticale;
4. con separatore non al centro del rettangolo.

La prima e l'ultima soluzione possono funzionare bene; nel primo caso avremo molto probabilmente una descrizione più articolata che quarto caso, ma comunque funzionante. Al contrario, per le soluzioni 2. 3., queste sono limitate ad applicazioni specifiche, perché non prevedono segmentazione rispettivamente verticale ed orizzontale.

Con questo approccio, la segmentazione finale difficilmente avrà una correlazione chiara con la natura fisica degli oggetti ritratti nell'immagine; inoltre, questa segmentazione dipenderà in maniera molto significativa dalla posizione e dalla dimensione degli oggetti, una proprietà davvero sgradevole.

Binary-space partition tree (BSP-tree)

Questo tipo di descrizione migliora la correlazione tra il risultato della segmentazione e l'oggetto effettivamente presente nell'immagine: le linee di segmentazione, infatti, possono essere posizionate in ogni luogo dell'immagine (non solo nel suo centro) e possono avere l'inclinazione preferita.

Spostando e ridimensionando la palla, si ottiene:

Come si può vedere, la segmentazione è all'incirca la stessa nei due casi, cambiano soltanto i parametri, ma l'aspetto e il posizionamento delle linee resta invariato.

Quello che si fa è usare delle linee rette per separare le due aree, nel blocco in esame, che sono meno omogenee tra loro; le rette dovranno essere scelte in maniera tale da essere aderenti ad eventuali bordi presenti nell'immagine: per questo motivo, la trasformata di Hough diventa uno strumento dell'algoritmo di segmentazione, proprio perché permette di trovare le rette che meglio separano le aree delle immagini.

È importante notare che, con questo algoritmo, è possibile che due aree tra loro omogenee vengano divise da una retta dominante: non vi è alcuna garanzia che queste due aree possano essere riconosciute come una singola regione, risulteranno a tutti gli effetti degli oggetti diversi.

Segmentazione tramite tessitura

Immaginiamo di avere un'immagine $I[m,n]$ con i valori medi locali costanti,

$\mu _{I}[m,n]\simeq E\left[I[m,n]\right]=\mu _{0}$

Ipotizziamo che anche la varianza locale sia costante,

$\sigma _{I}^{2}[m,n]\simeq E\left[\left(I[m,n]-\mu [m,n]\right)^{2}\right]=\sigma _{0}^{2}$

I valori $\mu _{I}$ e $\sigma _{I}^{2}$ sono i momenti associati ad una statistica del prim'ordine del processo casuale 2D. Abbiamo due strade per ottenere una segmentazione efficace a partire da un problema di questo tipo:

1. possiamo arricchire la statistica del prim'ordine attraverso istogrammi locali e modelli;
2. possiamo aumentare il grado della statistica, passando ai momenti del second'ordine.

Il primo metodo può funzionare, ma non c'è alcuna garanzia di affidabilità; al contrario, usando la statistica del second'ordine andiamo ad estrarre nuovi parametri che descrivono la struttura dell'immagine, esattamente come fa l'occhio umano, che va alla ricerca delle strutture ripetitive e regolari.

Definiamo l'autocorrelazione

$R_{I}[m',n']=E\left[I[m,n]-I[m+m',n+n']\right]$

Per ottenere l'effetto desiderato, possiamo impostare un banco di filtri, detti filtri di Hadamard, che permettono di calcolare:

• il valor medio, con

$h_{1}[m,n]=\left[{\begin{matrix}1&1\ 1&1\end{matrix}}\right]$

• il gradiente orizzontale, con

$h_{2}[m,n]=\left[{\begin{matrix}1&1\ -1&-1\end{matrix}}\right]$

• il gradiente verticale, con

$h_{3}[m,n]=\left[{\begin{matrix}1&-1\ 1&-1\end{matrix}}\right]$

• il gradiente diagonale, con

$h_{4}[m,n]=\left[{\begin{matrix}1&-1\ -1&1\end{matrix}}\right]$

Lo schema generale del banco di filtri sarà:

$I[m,n]\Rightarrow \left\{{\begin{aligned}\left[h_{1}[m,n]\right]\ \rightarrow &\ \left[2\downarrow \right]\ \rightarrow \left[x^{2}\right]\ \rightarrow \ \left[\int \right]\ \rightarrow \ E\left[\left(\sum _{i,j}w_{i,j}I[m,n]\right)^{2}\right]\\\left[h_{2}[m,n]\right]\ \rightarrow &\ \left[2\downarrow \right]\ \rightarrow \left[x^{2}\right]\ \rightarrow \ \left[\int \right]\ \rightarrow \ E\left[\left(\sum _{i,j}w_{i,j}I[m,n-j]\right)^{2}\right]\\\left[h_{3}[m,n]\right]\ \rightarrow &\ \left[2\downarrow \right]\ \rightarrow \left[x^{2}\right]\ \rightarrow \ \left[\int \right]\ \rightarrow \ E\left[\left(\sum _{i,j}w_{i,j}I[m-i,n]\right)^{2}\right]\\\left[h_{4}[m,n]\right]\ \rightarrow &\ \left[2\downarrow \right]\ \rightarrow \left[x^{2}\right]\ \rightarrow \ \left[\int \right]\ \rightarrow \ E\left[\left(\sum _{i,j}w_{i,j}I[m-i,n-j]\right)^{2}\right]\\\end{aligned}}\right.$

I quattro filtri del banco, idealmente, hanno una trasformata di questo tipo:

Ridge riding

L'algoritmo ridge riding (cavalca il bordo) è un metodo per la determinazione dei bordi delle immagini, in modo tale che queste possano essere segmentate; l'idea è che il bordo di un'immagine si può calcolare iterativamente, percorrendolo a poco a poco.

Questo tipo di algoritmo è da usare dopo una segmentazione a tessitura, in modo tale da rifinire i bordi delle aree trovate.

Approccio bottom-up

La strategia bottom-up (dal fondo a salire) è un metodo deterministico per creare una segmentazione delle immagini; invece di provare ad assegnare un'etichetta ad ogni punto dell'immagine, si va a controllare se i vicini di ogni singolo punto dell'immagine sono vicini al punto di partenza, cioè se la loro distanza è al di sotto di un certo valore di soglia.

 Quanto mi assomigliano, i punti che mi sono vicini?

Il risultato di questa operazione è che, se un punto è simile a quello di partenza, allora l'etichetta sarà identica.

Algoritmo bottom-up semplice

1. Si comincia da un punto casuale dell'immagine $T[m,n]$, che è l'immagine che mostra il parametro che abbiamo scelto come discriminante; solitamente, il punto di partenza è $(0,0)$, ma non è un fatto necessario.

2. Si calcola la distanza tra questo pixel ed i suoi vicini; i vicini possono essere 4 (nell'immagine, soltanto i pallini) oppure 8 (pallini e crocette), a seconda del criterio che abbiamo scelto:

3. Si centra l'algoritmo su ognuno dei punti che compaiono nella lista dei vicini, in modo tale da espandere la regione in maniera ricorsiva.

4. Quando la lista dei vicini è vuota, si prende un altro punto a caso che non è ancora stato etichettato, e si ricomincia ad eseguire l'algoritmo dal punto 2. in avanti, utilizzando una nuova etichetta.

Il risultato di questo algoritmo sarà un'immagine segmentata in diverse regioni grandi, più tante piccole regioni che, viste nel loro complesso, formano i punti di bordo, cioè i bordi delle figure che compaiono nell'immagine.

Region Adjacency Graph, RAG

Il RAG non è altro che un grafo che collega tra loro tutte le regioni dell'immagine; grazie a questo strumento, il risultato della segmentazione non dipenderà dal punto di partenza della scansione delle distanze.

1. Ogni regione (all'inizio, ogni punto) è il nodo di un grafo.

2. Ogni nodo del grafo deve essere collegato con i nodi che gli sono geograficamente vicini,

${\begin{matrix}53&60&41&21\\50&60&40&20\\51&42&47&30\\21&31&68&20\end{matrix}}$

3. Per ogni singolo nodo, si va a calcolare la caratteristica discriminante che abbiamo scelto, per esempio il valor medio dei punti.

4. Per ogni collegamento tra regioni adiacenti, si calcola la distanza: questo valore rispecchia la differenza tra due nodi; per esempio, la distanza potrebbe essere la differenza (in modulo) tra i valori medi delle due regioni vicine.

5. Si vanno ad unire le regioni adiacenti la cui distanza è minima, cioè che hanno la differenza più piccola.

6. Si ricalcolano le differenze tra le varie regioni che sono state fuse ed i nodi vicini.

7. Si torna al punto 5. fintanto che

• non ci sono più nodi;
• le differenze tra i nodi superano una certa soglia limite.

Questo algoritmo è stato inventato alla fine degli anni '80; per ragioni di efficienza, è meglio cominciare ad analizzare le immagini con un approccio di tipo top-down, almeno fintanto che le dimensioni delle regioni non sono sufficientemente piccola da poter essere trattare con l'approccio bottom-up , che richiede molta più memoria e calcolo computazionale.