Algoritmo del taglio normalizzato per la segmentazione di immagini

semplicemente visualizzazioni di fenomeni, sono cioè riproduzione 
“vere”, “reali”, “oggettive”. Esse aiutano a osservare ed interpretare i 
vari processi che rappresentano.  
Per questo processo non è solitamente sufficiente la semplice 
osservazione. Spesso infatti richiede l’ausilio di modellizzazioni digitali 
oppure (o in aggiunta) può essere necessario isolare le informazioni da 
esaminare, togliendo il contesto, il “rumore di fondo”. In questi casi è 
utile ricorrere ad elaborazioni che consentano di dividere le varie parti di 
una immagine in aree ben distinte, ognuna rappresentante qualche 
oggetto o comunque avente caratteristiche di similarità interna. Tale 
processo viene chiamato segmentazione. Si tratta di un problema ben 
noto e lungamente studiato, per il quale esistono diverse soluzioni e 
procedure applicative, alcune delle quali saranno brevemente presentate 
nel Capitolo 1. 
L’algoritmo ottimo, se mai esistesse, non è stato tuttavia ancora 
trovato, lasciando quindi aperta la ricerca di nuovi e migliori metodi 
risolutivi. Tra questi, uno molto promettente è stato presentato da Jianbo 
Shi e Jitendra Malik in via prelimare nel 1997 [SM97] e definitiva nel 
corso del 2000 nel loro lavoro intitolato “Normalized Cuts and Image 
Segmentation”. Nello stesso anno i due ricercatori, insieme a Serge 
Belongie e Thomas Leung dell’Università di Berkeley hanno anche 
descritto una possibile strategia implementativa in “Contour and Texture 
Analysis for Image Segmentation” [MBLS00]. Una completa descrizione 
di tale algoritmo, tema fondamentale della presente tesi, verrà data nel 
Capitolo 3.  
Data la complessità matematica dell’algoritmo in questione si è 
ritenuto opportuno, nel Capitolo 2, riassumere molto brevemente alcuni 
concetti chiave che saranno necessari per una migliore comprensione del 
lavoro svolto. In particolare saranno trattati argomenti di algebra, calcolo 
numerico e teoria dei grafi. 
 Il Capitolo 4 presenta, invece, il codice in C++ e MATLAB che 
consente di applicare le nozioni teoriche apprese in un caso particolare 
ma significativo, quello delle immagini PGM in scala di grigio. Alcuni 
esempi commentati di utilizzo di questo codice saranno presentati nel 
Capitolo 5. 
 6
Capitolo 1  
Segmentazione di un’Immagine 
1.1 Introduzione 
Un’immagine digitale, indipendentemente dal metodo con cui è stata 
acquisita, risulta composta da elementi, chiamati pixel, ognuno dei quali 
rappresenta un singolo colore o livello di grigio. Normalmente un 
intervallo di luminosità (per ogni singolo colore) viene rappresentato con 
8 bit (il bit è la singola unità di memorizzazione dell’elaboratore, e può 
contenere solo i valori binari 0 o 1), per cui può assumere al massimo 
2
8
=256 valori. Tali valori sono normalmente bastanti affichè l’occhio 
umano percepisca l’immagine sufficientemente “nitida”.  
Nel caso di immagini in scala di grigio è possibile specificare un 
solo intervallo di luminosità. Sono perciò sufficienti 8 bit (ossia 1 byte) 
per ogni pixel. Al contrario, per immagini a colori questi si incrementano 
in base al numero di colori primari da registrare. Per esempio alle 
immagini RGB (tricromia) saranno necessari 3x8=24 bit, potendo quindi 
contare su 2
24
=16 miloni di colori possibili (un singolo colore è dato 
dalle diverse “gradazioni” dei 3 primari, in questo caso rosso, verde e 
blu).  
Considerando il pixel come l’unità singola di memorizzazione è 
possibile rappresentarlo dandone semplicemente la posizione (per 
esempio relativa il primo pixel in alto a sinistra) e i valori di luminosità 
relativi allo spazio considerato (uno solo per immagini in scala di grigio, 
tre per quello RGB, quattro per CMYK, ecc…). Per esempio in RGB il 
colore rosso sarà 255-0-0, il blu 0-0-255, l’azzurro cielo 128-128-255 il 
grigio chiaro 192-192-192, il quale nello spazio dato dalle immagini solo 
in scala di grigio sarà dato semplicemente dal valore 192. 
La segmentazione dell’immagine consiste nell’effettuare una 
partizione di questo insieme dei pixel. Segmentare un’immagine significa 
quindi individuare in essa le regioni (sottoinsiemi di pixel connessi) che 
rappresentano elementi significativi della scena. 
Benché il problema risulti di facile comprensione sfortunatamente 
esso è difficilmente automatizzabile. Per l’elaboratore, infatti, risulta 
 7
molto complesso trovare opportunamente le regioni. Per chiarire il 
concetto si veda l’immagine seguente (Fig. 1.1) 
 
 
Fig. 1.1 – Esempio di immagine 
 
Per l’uomo è abbastanza facile dividere l’immagine in parti che 
definiscono i diversi oggetti: il terreno, le nuvole, il sole, le piante, i 
tralicci. Per l’elaboratore questo è molto più complesso: come 
distinguere, per esempio, le piante dal terreno? Il livello di grigio è 
molto simile, quindi potrebbe essere molto complicato effettuare (si 
ricordi, in maniera automatica) tale divisione. Come se ciò non bastasse, 
si consideri inoltre che la divisione “ottimale” dipende fortemente da 
cosa si cerca. Nell’esempio di Fig. 1.1 potrebbe essere necessario 
individuare solo il confine tra l’area del cielo e quella della terra (linea 
dell’orizzonte), oppure si vorrà porre l’attenzione sulle nuvole (in una 
stazione metereologica) o alle piante (nel campo della biologia) e così 
via. 
Concludendo si può dire che la scelta della partizione ottimale è per 
un certo senso soggettiva. I principali algoritmi possono quindi essere 
usati, dopo attenta personalizzazione, solamente come traccia, un 
suggerimento che poi dovrà essere verificato dall’occhio umano in 
rapporto a ciò che ricerca. 
 
1.2 Principali tipi di segmentazione 
Nel corso degli anni sono state presentate numerose tecniche per il 
problema della segmentazione. Benché spesso siano molto diverse l’una 
dall’altra è tuttavia possibile classificarle in due categorie [MBLS00]: 
• basate sulle regioni 
• basate sul contorno 
 
Nel primo caso si cerca di dividere l’immagine in sottoinsiemi in cui 
i pixel abbiano una certa coerenza, per esempio un intervallo di 
luminosità o di colore. Nel secondo, al contrario, solitamente si inizia 
 8
riconoscendo i contorni (attraverso uno dei numerosi algoritmi esistenti), 
per poi “collegare” tali confini ottenendo delle continuità (generando 
quindi dei sottoinsiemi). Si può verificare che è possibile passare da un 
metodo di un tipo ad uno dell’altro scegliendo opportuni criteri [WE96]. 
 
Un’ulteriore classificazione può essere effettuata verificando se il 
metodo in esame utilizza dati esclusivamente locali oppure anche globali 
all’immagine. Altrimenti detto, se vengono esaminate esclusivamente 
caratteristiche (locali) dei pixel adiacenti oppure se si considerano anche 
qualità globali. In generale il tener conto di informazioni globali 
migliora notevolmente il processo di segmentazione, a costo tuttavia di 
una complessità computazionale nettamente superiore. L’utilizzo di 
entrambi i tipi di informazioni può essere l’approccio migliore al 
problema della segmentazione. Applicare ciò per esempio ad un metodo 
basato sul contorno può voler dire in una prima fase usare informazioni 
locali per trovare i contorni, che saranno poi successivamente collegati in 
base a dati globali all’immagine. 
 
A conclusione del paragrafo risulta utile accennare ad un problema 
di riconoscimento importante ed in qualche modo indipendente dal 
metodo utilizzato: quello delle trame (“texture”). Si pensi ad una tovaglia 
a righe o al mantello di una tigre: essi sono oggetti con una trama più o 
meno regolare, ma che devono essere interpretati per quanto possibile 
complessivamente. Sia gli approcci basati sulle regioni che quelli basati  
sul contorno rischiano di fallire miseramente in tali situazioni, se non 
utilizzando complesse informazioni globali a correzione del 
riconoscimento effettuato. 
 
1.3 La partizione ottimale 
E’ possibile individuare alcune caratteristiche che dovrebbe 
possedere una metodologia di segmentazione considerata ottimale (non 
ottima, si ricordi, in quanto questa in generale non esiste) [MBLS00]: 
• dovrebbe poter essere utilizzata con immagini generiche, 
quindi anche miste con texture e senza; 
• in termini di contorno, dovrebbe essere in grado di trovare sia 
differenze di luminosità o altre caratteristiche di pixel che 
contorni e linee; 
• dovrebbe essere possibile applicarlo ricorsivamente su parti di 
immagine che si desidera approfondire ulteriormente 
 
 9
Ricordando queste caratteristiche è ora possibile descrivere in modo 
più approfondito alcune strategie risolutive “classiche”, per passare poi, 
nel Capitolo 3, all’algoritmo oggetto di studio di questa tesi.  
Si noti, inoltre, che tutte le metodologie e gli esempi presentati nel 
proseguo si riferiscono a immagini a livelli di grigio. Esse sono tuttavia 
generalizzabili (previa opportuna modifica) anche per immagini a colori. 
 
1.4 Il Thresholding 
1.4.1 L’istogramma 
L’istogramma di un’immagine fornisce molte importanti 
informazioni circa la distribuzione dei livelli di grigio presenti. Si 
consideri un’immagine di dimensione N x M con G livelli di grigio (si è 
visto che normalmente G=256).  
L’istogramma è definito come una funzione da G a [0,NM] che ad 
ogni elemento di G associa il numero di pixel aventi quel determinato 
livello di grigio. 
Particolare importanza viene assunta dall’istogramma normalizzato, 
definito come: 
NM
n
h
i
i
=  
 
per ogni valore i∈ G, dove: 
• n
i
 è il numero di pixel di livello i; 
• NM è il numero totale di pixel presenti nell’immagine. 
 
L’istogramma normalizzato è quindi una distribuzione, e come tale è 
possibile calcolarne diversi valori notevoli, nonchè darne una 
rappresentazione grafica, indicando per esempio sull’asse delle ascisse il 
livello di grigio e sulle ordinate la percentuale (il valore h
x
).  
In Fig. 1.2 è riportato a titolo esemplificativo l’istogramma 
normalizzato dell’immagine di Fig. 1.1, ottenuto utilizzando l’apposita 
funzione all’interno del noto programma di fotoritocco Adobe 
Photoshop. Nella stessa figura sono riportati anche alcuni valori notevoli 
associati, quali la media (mean), la deviazione standard (std dev) e la 
mediana (median). 
 
 10
 Fig. 1.2 – Istogramma normalizzato dell’immagine di Fig. 1.1 
 
L’importanza di avere una precisa conoscenza delle percentuali dei 
diversi livelli di grigio sarà maggiormente compresa in seguito. Tuttavia, 
prendendo come riferimento la Fig. 1.2, è già facilmente verificabile 
come sia possibile migliorare la qualità dell’immagine intervenendo 
sull’istogramma. In Fig. 1.2 è infatti presente una zona (nel nero) dove 
non sono presenti pixel (la parte con valore y a 0 sulla sinistra). E’ 
quindi possibile “normalizzare” l’immagine di partenza per fare in modo 
che i pixel siano distribuiti su tutta l’ampiezza dei valori della scala. 
Questa semplice operazione consente di migliorare notevolmente la 
leggibilità dei dettagli, seppur, ovviamente, non aggiungendo alcuna 
informazione. Una semplice procedura di normalizzazione sarà realizzata 
nel Capitolo 4. 
 
1.4.2 Segmentazione tramite thresholding 
Il tipo più semplice di partizionamento utilizza la strategia del 
thresholding. 
Sia data un’immagine I di dimensioni N x M e G livelli di grigio. Si 
prenda un valore arbitrario K appartenente a G. Nel tresholding viene 
generata una nuova immagine T (sempre di dimensioni N x M) con pixel 
solo bianchi o neri. L’elemento T
i
 sarà ad esempio bianco se il 
corrispondente I
i
 è minore o uguale a K, altrimenti sarà nero.  
Questa semplice metodologia di segmentazione ha due grossi 
svantaggi: primo, non è possibile conoscere a priori in quanti 
sottoinsiemi verrà divisa l’immagine di partenza (è molto facile avere 
anche dei singoli punti “sparsi”); secondo, è in generale molto difficile 
individuare (se non per immagini molto semplici) un corretto valore 
soglia K. 
Un caso in cui risulta abbastanza semplice la scelta del valore soglia 
è dato dall’immagine di Fig. 1.1. Osservando il corrispondente 
istogramma normalizzato (Fig. 1.2) è possibile notare che esiste un punto 
di minimo posto nella parte sinistra della curva di distribuzione. 
 11
Utilizzando tale valore minimo come soglia K l’immagine viene 
suddivisa in due regioni, che corrispondono a cielo e terra (Fig. 1.4). 
 
 
Fig. 1.3 – Scelta del valore di soglia 
 
 
Fig. 1.4 – Risultato del threshold applicato all’immagine di Fig. 1.1 
 
E’ stato un caso fortunato, infatti è stata sostanzialmente mantenuta 
la linea dell’orizzonte, dividendo correttamente il cielo dalla terra. Se, 
invece, si fossero voluti altri particolari (quali gli alberi) la scelta del 
valore di soglia sarebbe stata molto più complicata. Per questo, nel corso 
degli anni, sono stati ideati moltissimi algoritmi di ricerca automatici, 
nessuno dei quali, tuttavia, risulta definitivo [WE96]. 
1.4.3 Threshold multilivello 
Il treshold multilivello si basa sullo stesso principio del tresholding 
semplice. Esso usa tuttavia più valori soglia (K
1
, K
2
, ecc…) generando 
quindi, come segmentata T, un’immagine in scala di grigio (con |G| = 
numero livelli).  
Si noti che il treshold multilivello non risolve nessuno dei problemi 
visti in precedenza, e non è quindi da considerarsi una buona strategia 
risolutiva del problema della segmentazione. 
1.5 Segmentazione basata sul contorno 
E’ possibile realizzare una segmentazione basandosi sulle figure 
presenti nell’immagine: dapprima si trovano i contorni “probabili” degli 
oggetti rappresentati, poi essi vengono “uniti” a formare una linea 
chiusa, che delimiterà una regione. I pixel che alla fine del processo 
(ripetuto per ogni singolo contorno) non saranno stati ancora inclusi in 
un’area verranno considerati facenti parte al sottoinsieme dello sfondo. 
 12
Per comprendere il funzionamento dell’algoritmo si consideri 
l’immagine come una funzione in due variabili che associa ad ogni punto 
dello spazio bidimensionale di coordinate (x,y) un valore f(x,y), il livello 
di grigio ad esso associato.  
Inoltre, bisogna definire cosa si intenda per contorno. Un contorno si 
può considerare tale quando esiste una certa discontinuità tra i livelli di 
grigio da una parte e quelli dall’altra della linea rappresentante il 
confine. 
 
Si vedrà anzitutto il problema della ricerca del contorno, per passare 
poi alla fase di tracing (unione).  
1.5.1 Point Detection 
Inizialmente si pensi a come trovare un singolo punto di 
discontinuità. 
Molte tecniche per l’estrazione dei pixel di bordo si basano 
sull’utilizzo di filtri lineari. Un esempio di filtro con regione di supporto 
3 x 3 è:  
 
-1 -1 -1 
-1 8 -1 
-1 -1 -1 
Fig. 1.5 – Tabella di filtro di ricerca di punti 
 
Come avvenga la sua applicazione è abbastanza intuitivo: si 
seleziona una parte dell’immagine di dimensioni identiche a quelle del 
filtro (3 x 3) e i valori di grigio dei pixel corrispondenti vengono 
moltiplicati per i fattori moltiplicativi del filtro stesso.  
Formalmente un’immagine data da f(x,y) subisce durante il processo 
la seguente trasformazione: 
 
 ƒ ƒ
==
+
+−+−=
2
0
2
0
)3(
)1,1(),(
ij
ij
Aiyjxfyxg  
 
dove A
i
 è l’iesimo valore della maschera del filtro (partendo da A
0
, 
valore alto sinistro). Considerando la funzione point(x,y) come il valore 
assoluto di g(x,y) (ossia point(x,y)=|g(x,y)|) è facile comprendere che 
esso è un livello di grigio direttamente proporzionale alla differenza di 
valore tra il pixel centrale e i suoi 8 vicini. 
 Point(x,y) ritorna un livello di grigio, mentre nel determinare se un 
pixel ha una differenza “sufficiente” di valore ci si aspetterebbe un 
 13
“vero” o “falso”. Per ovviare a tale inconveniente solitamente si applica 
il thresholding al risultato, considerando quindi punti di discontinuità 
solamente quelli per cui  
 
point(x,y)>K 
 
con K valore soglia scelto. 
 
1.5.2 Line Detection 
Estendendo il caso sopra esposto, per cercare un contorno di linee si 
dovranno applicare n filtri lineari, uno per ogni direzione cercata. In Fig. 
1.6 sono riportati alcuni esempi: 
 
 
 
-1 -1 -1
2 2 2
-1 -1 -1
-1 2 -1 
-1 2 -1 
-1 2 -1 
 
-1 -1 2
-12-1
2 -1 -1
 
2-1-1 
-1 2 -1 
-1 -1 2
 
Fig. 1.6 – Maschere di filtri per la ricerca di linee orizzontali, verticali, a 45° e 
135° 
 
Come si vede la prima matrice consente di trovare linee orizzontali, 
la seconda verticali e così via. Per ogni pixel viene quindi scelto come 
output la direzione della maschera che ha dato il risultato massimo, che 
sarà infine sottoposto a thresholding per lo stesso motivo visto nel caso 
dei punti. 
 
1.5.3 Edge Detection 
Il fatto che per trovare contorni qualunque si applichino delle 
maschere simili a quelle viste in precedenza non dovrà, a questo punto, 
sorprendere. In effetti in Fig. 1.7 sono rappresentate le tabelle (otto in 
tutto) che consentono di ottenere i contorni in due direzioni orizzontali, 
due verticali e quattro diagonali, conosciute come Kirsch edge detector. 
 
 14