Elaborazione delle immagini - Algoritmi

Tecniche di elaborazione delle immagini

1 Binarizzazione automatica

FINALITÀ Si vuole ottenere l'immagine binaria (a due livelli) di una scena originale in scala di grigi a partire dal suo istogramma,

ad esempio per separare un soggetto dallo sfondo o produrre una maschera utile ad applicare elaborazioni successive.

 Caso ideale - L'istogramma della scena è chiaramente bimodale: presenta due picchi (mode) che rappresentano

distintamente lo sfondo e il soggetto da separare, sicché è possibile stabilire una soglia fissa in corrispondenza del valore

minimo tra i due.

 Caso comune - L'istogramma della scena è essenzialmente uniforme (per effetto di sfumature e gradazioni), pur

riguardando la rappresentazione di un soggetto su uno sfondo chiaramente distinguibile.

Per superare la difficoltà di stabilire a priori una soglia fissa ottimale, si vuole determinare automaticamente il valore che

( ) ( ),

partizioni l'istogramma della scena in due classi "omogenee" di pixel e destinate, rispettivamente, all'uno e all'altro

livello dell'immagine binarizzata.

1.1 Metodo di Otsu ( ) ( )

PRINCIPIO La soglia è determinata in modo tale da minimizzare la varianza entro le classi di pixel e che separa.

FORMULAZIONE ANALITICA ( )

● Data l'immagine originale in scala di grigi (a livelli di grigio).

● Si considera l'istogramma dell'immagine originale, che associa al generico livello di grigio il numero dei pixel che lo

assumono nell'immagine. { } { }

● Si considera l'istogramma normalizzato dell'immagine originale, che associa al generico livello di grigio la "probabilità"

che esso sia assunto dagli pixel (complessivi) dell'immagine..

{ } [ ]

( )

( )

● A prescindere dall'esatto valore della soglia , l'istogramma normalizzato può essere visto come la somma delle probabilità

che i pixel appartengano all'una o all'altra classe separate dalla soglia. La probabilità complessiva è naturalmente pari a .

( )] ( ) ∑ ( )

[

Probabilità della classe : ( )] ( ) ∑ ( )

[

Probabilità della classe : ( ) ( )

● Si considera il livello di grigio medio della funzione e si osserva che esso è pari alla somma dei livelli medi parziali di

ciascuna classe. Questi ultimi si ottengono normalizzando i valori corrispondenti ai livelli di grigio entro le classi rispetto alla

probabilità delle classi stesse. ∑ ( )

Livello medio globale: ( )] ( ) ∑ ( )

[

Media parziale classe : ( )

( )] ( ) ∑ ( )

[

Media parziale classe : ( )

( ) ( )

● Analogamente, si considera la varianza . ∑ ( ) ( )

Varianza globale: ( )] ( ) ∑ ( )] ( )

[ [

Varianza parziale classe : ( )

( )] ( ) ∑ ( )] ( )

[ [

Varianza parziale classe : ( )

● Si dimostra che la varianza globale risulta dalla somma di due termini chiamati, rispettivamente, within group variance

[ ] e between group variance [ ]. 1

Il primo termine corrisponde alla somma delle varianze parziali, pesate rispetto alla probabilità delle classi corrispondenti.

Il secondo termine corrisponde alla somma pesata degli scarti quadratici tra la media globale e le medie parziali.

( ) ( ) ( ) ( )

Within group variance: ( ) ( ) ( ) ( )

[ ] [ ]

Between group variance:

● In accordo con l'idea chiave del metodo di Otsu, la soglia ottimale deve essere tale da minimizzare la within group

variance, cioè la varianza entro le classi di pixel. Tuttavia, poiché la varianza globale non dipende dalla soglia ed è pari alla

somma dei termini e , minimizzare la within group variance equivale a massimizzare la between group variance.

Quest'ultima è semplificata attraverso semplici passaggi algebrici.

( ) ( )] ( )] ( )

[ [

ALGORITMO

Si calcola la between group variance per ogni soglia (con ) e si sceglie il valore che lo massimizza.

( ), ( ) ( ),

I termini e funzionali a e coinvolti nella computazione, possono essere calcolati al passo a partire

dall'iterazione precedente.

1.2 Metodo di Kapur ( ) ( )

PRINCIPIO La soglia è determinata in modo tale da massimizzare la somma delle entropie delle classi di pixel e

che separa.

NOTA - L’entropia di un’informazione si associa al concetto di incertezza ed è tanto maggiore quanto più è difficile prevedere il

verificarsi di un particolare evento.

FORMULAZIONE ANALITICA ( )

● Si considerano l'immagine originale in scala di grigi (a livelli di grigio) e il suo istogramma normalizzato .

● Si definiscono le nozione di informazione associata all'evento "estrazione di un pixel di livello dall'immagine" e di entropia.

( ) ( )

Informazione: ∑ ( ) ∑ ( ) ( )

Entropia dell’immagine:

NOTA - Porre che la probabilità del generico livello non sia nulla, equivale a richiedere che esista almeno un pixel

nell'immagine associato ad esso. ( ) ( )

● Le probabilità associate alle classi di pixel e corrispondono alla somma delle probabilità associate a ciascun

livello di grigio entro l’una o l’altra classe, e si possono rappresentare attraverso le rispettive distribuzioni.

( ) { }

Distribuzione classe : ( ) ( ) ( )

( ) { }

Distribuzione classe : ( ) ( ) ( )

NOTA – Per semplificare i calcoli, la probabilità della classe è espressa in funzione della probabilità complessiva (pari a ).

● È quindi possibile ricavare la formulazione dell’entropia associata alle classi.

( ) ( )

( )] ∑

[

Entropia classe : ( ) ( )

( )

∑ ( ) ( )]

[

( )

( ) ( )

∑ ( ) ( )]

[ ( ) ( )

∑ ( ) ( ) ∑ ( ) ( )

[ ]

( ) ( )

( )

( )] ( )]

[ [

Entropia classe : ( ) ( )

● In accordo con il principio del metodo di Kapur, si definisce la somma delle entropie parziali e si ricerca la soglia che

la massimizza. ( ) ( )] ( )] ( ) ( )]

[ [ [

( ) ( )

( ) ( ))]

[ (

( ) ( ) 2

ALGORITMO

Si calcola la somma delle entropie per ogni soglia (con ) e si sceglie il valore che lo massimizza.

( ),

L’entropia dell’immagine [ ] è calcolata una sola volta, mentre i termini e funzionali a e coinvolti nella

computazione, possono essere calcolati al passo a partire dall'iterazione precedente.

2 Clustering

FINALITÀ Si vuole segmentare un’immagine originale identificando gli oggetti che la compongono e raggruppandoli in classi (o

cluster) secondo un criterio di similarità.

CLUSTER Un cluster è, informalmente, un raggruppamento di oggetti simili.

Se ogni oggetto è caratterizzato da proprietà misurabili, esso può essere corrisposto a un vettore -dimensionale. Gli oggetti

di un’immagine sono quindi rappresentati attraverso i punti di uno spazio vettoriale -dimensionale chiamato spazio delle

caratteristiche.

I cluster sono insiemi di punti vicini (o collegati da una qualche altra relazione) nello spazio delle caratteristiche.

CRITERI DI SIMILARITÀ Sicuramente, è intuitivo classificare gli oggetti in cluster secondo una qualche nozione di distanza tra

punti nello spazio delle caratteristiche.

Occorre, però, ricordare che la scelta del criterio sulla base del quale si effettua il clustering è, in generale, determinante, poiché

può produrre informazioni rilevanti nell’ambito della procedura di raggruppamento. Ad esempio, la nozione di distanza euclidea

(particolarmente ovvia) impone che lo spazio delle caratteristiche sia isotropo, ossia che i cluster siano invarianti per

trasformazione lineare rispetto alle proprietà che li descrivono in forma vettoriale.

DEFINIZIONE DELLA FUNZIONE OBIETTIVO

{ }

● Si considera un insieme di oggetti (vettori) da raggruppare in sottoinsiemi disgiunti di .

Si vuole ottenere che i sottoinsiemi corrispondano ad altrettanti cluster di oggetti simili tra loro.

● Si definisce una funzione obiettivo che misuri la qualità del raggruppamento, quindi si ricerca la partizione che la massimizza

(o la minimizza, secondo la natura della funzione stessa).

Una funzione obiettivo piuttosto diffusa risulta dalla somma degli scarti quadratici che interessano gli elementi raggruppati,

{ },

nei sottoinsiemi di una generica partizione rispetto alla loro media.

La media ( ) è il vettore che meglio rappresenta gli elementi di ciascun sottoinsieme, poiché minimizza la somma delle loro

lunghezze al quadrato. ∑

Media dei campioni per l’ -esimo sottoinsieme (di elementi): ( ) ∑ ∑

Somma degli scarti quadratici per la partizione (funzione obiettivo):

NOTA - La funzione obiettivo corrispondente alla somma degli scarti quadratici è particolarmente indicata quando i campioni

considerati formano, nello spazio delle caratteristiche, “nuvole” di punti compatte e distinte l’una dall’altra.

La partizione ottimale minimizza la funzione obiettivo .

● La funzione obiettivo può essere derivata attraverso un procedimento alternativo, che considera le cosiddette matrici di

dispersione.

Si definisce la matrice , che rappresenta il tasso di dispersione all’interno di ciascun cluster.

∑ ( )( )

Dispersione all’interno del cluster -esimo:

Si definisce la matrice (within-class scatter matrix), che rappresenta la dispersione complessiva all’interno dei cluster

(corrispondendo alla somma delle dispersioni che caratterizzano ciascun raggruppamento).

∑

Within-class scatter matrix:

Si definisce la matrice (between-class scatter matrix), che rappresenta la dispersione tra i cluster, considerando la

differenza tra le medie dei cluster stessi e la media estesa a tutti gli elementi dell’insieme .

∑ ∑

Vettore medio complessivo: ∑ ( )( )

Between-class scatter matrix:

Si definisce, infine, la matrice di dispersione totale , che corrisponde, evidentemente, alla somma della dispersione interna

ai cluster (la matrice ) e della dispersione tra i cluster (la matrice ).

∑ ( )( )

Dispersione totale: 3

● La matrice di dispersione totale, considerando tutti gli elementi in gioco a prescindere da qualsiasi ripartizione, è costante,

mentre la within-class scatter matrix e la between-class scatter matrix variano, l’una a scapito dell’altra, in funzione della

particolare partizione per cui sono definite.

Per valutare la qualità delle partizioni occorre un termine scalare (in questo caso da minimizzare) che corrisponde alla traccia

della matrice e, finalmente, alla funzione obiettivo .

( ) ∑ ∑∑

NOTA - La traccia di una matrice è pari alla somma degli elementi che ne costituiscono la diagonale principale.

RICERCA DELLA PARTIZIONE OTTIMALE

Poiché non è possibile enumerare esaustivamente le partizioni, benché finite, di un numero di oggetti, si ricorre solitamente a

un metodo di ottimizzazione iterativa: definita una “buona” partizione iniziale, si considerano gli elementi in sequenza e li si

sposta da un cluster all’altro se ciò comporta il miglioramento della funzione obiettivo.

̂,

● Si considera una partizione generata a caso e un generico elemento (vettore) assegnato al cluster .

̂

Si vuole determinare se lo spostamento del vettore nel cluster comporti la diminuzione della funzione obiettivo .

̂

Media del cluster (di elementi) a spostamento avvenuto: ̂

Media del cluster (di elementi) a spostamento avvenuto:

NOTA - Si assume, naturalmente, . (∑ | | ) | |

̂

Somma degli scarti quad. per il cluster a spostamento avvenuto: | |

̂

(∑ ) ̂

Somma degli scarti quad. per il cluster a spostamento avvenuto: ̂

● Poiché la funzione obiettivo è pari alla somma degli scarti quadratici complessivi di ciascun cluster, lo spostamento del

̂

vettore è vantaggiose se e solo se l’incremento della somma degli scarti riferita al cluster è inferiore al decremento

della somma per il cluster . | |

̂ ̂

2.1 Basic Minimum Squared Error (o algoritmo ISO-data)

INPUT Un insieme di vettori e un numero intero di cluster.

1 Distribuisci gli vettori in cluster, ad ottenere una partizione iniziale.

2 Calcola i vettori media di ciascun cluster e la funzione obiettivo .

̂

3 Seleziona un vettore (dove è uno degli cluster).

4 Calcola il decremento della somma degli scarti quadratici relativamente al cluster e l’incremento della stessa

relativamente agli altri cluster. ̂

Decremento per il cluster : | |

̂

Incremento per il -esimo cluster ( ):

NOTA - Se il numero degli elementi nel cluster è pari a , occorre ricalcolare la media (6). ̂

5 Se l’incremento per un cluster (con ) è tale che e ( ), allora sposta il vettore nel cluster .

6 Ricalcola le medie , e la funzione obiettivo .

7 Se il valore della funzione non cambia da iterazione termina la procedura, altrimenti considera un nuovo vettore (3).

NOTA - La complessità della procedura dipende dall’ordine in cui sono considerati i cluster della partizione iniziale. Non

disponendo alcuna precauzione in tal senso, l’algoritmo si presta al clustering in tempo reale, basato su campioni acquisiti nel

corso della computazione. 4

2.2 Algoritmo K-Means (o LGB)

INPUT Un insieme di vettori , un numero intero di cluster, un numero reale .

1 Poni un indice e scegli vettori media .

2 Costruisci un cluster per ciascuna media.

( ) ( )

{ || | }

3 Ricalcola la media per ogni cluster determinato (passo ).

4 Se la differenza tra le nuove medie e il loro valore al passo precedente rientra nel termine di convergenza prestabilito ,

termina la procedura, altrimenti ricostruisci i cluster (2). ( ) ( )|

|

Valutazione di convergenza:

NOTA - Gli algoritmi K-Means e ISO-data sono particolarmente sensibili alla rispettiva condizione iniziale, secondo la quale

restituiscono un risultato variabile. Inoltre, entrambi richiedono che il numero dei cluster sia prestabilito.

2.3 Algoritmo di Arbib

{ },

INPUT Un insieme di vettori un numero massimo di cluster identificabili, uno scalare corrispondente

al tasso di apprendimento, il numero massimo delle “vittorie” consentite a ciascun vettore rappresentante, il numero

massimo dei vettori considerabili.

1 Crea l’unità rappresentativa corrispondente al vettore , pari alla media globale degli elementi in input.

∑

( )

Poni gli indici interi e .

2 Estrai a caso un vettore e determina quale, tra le unità definite, è la più vicina ad secondo la metrica euclidea

.

NOTA - Se due unità distinte sono ugualmente distanti, selezionane una a caso.

3 Chiamata l’unità scelta, ridefinisci il vettore corrispondente, che in baso al tasso di apprendimento sarà

quindi più prossimo all’elemento considerato. ( )

4 Incrementa il numero di vittorie dell’unità vincente .

( ) ( ) ( )

Se il numero di vittorie così incrementato risulta pari al numero massimo consentito (se ) e le unità

costruite sono meno del numero massimo dei cluster identificabili, crea una nuova unità associata al vettore

( ) ( ).

dell’unità vincente e azzera gli indici e

NOTA - Si definisce sdoppiamento la creazione di una nuova unità a partire dall’unità vincente precedentemente selezionata.

5 Incrementa l’indice ( ).

Se (massimo numero dei vettori considerabili), termina la procedura. In caso contrario, estrai un nuovo elemento

dell’insieme (2).

NOTA - Si definisce epoca il periodo (numero di iterazioni) che intercorre tra due sdoppiamenti.

OUTPUT Partizione dell’insieme di elementi , tale che ciascun cluster è associato a un’unità rappresentativa secondo la regola

seguente: .

NOTA - Le nuove unità sono posizionate laddove gli elementi in input sono più densi, poiché sono generate esclusivamente al

raggiungimento del massimo numero di vittorie da parte dell’unità precedentemente scelta.

5

SCELTA DEI PARAMETRI Un numero massimo di vittorie piuttosto alto produce una maggiore accuratezza, a patto che si

incrementi di conseguenza il numero massimo delle iterazio