UNIVERSITÀ DEGLI STUDI DI TRENTO
Facoltà di Scienze Matematiche, Fisiche e Naturali
Corso di Laurea in Informatica
Tesi di Laurea
Algoritmi parametrici per la
segmentazione di immagini digitali
basati sull’analisi congiunta delle
caratteristiche di colore e tessitura.
Relatore:
Prof. Francesco De Natale
Responsabile esterno:
Dott. Stefano Messelodi
Laureando:
Lorenzo Dematté
Anno accademico 2001–2002
2
Ringraziamenti
Il primo gruppo di persone che desidero ringraziare sono i ricercatori
del gruppo TeV-SSI dell’ Istituto di Ricerca Scientifica e Tecnologica
(ITC-IRST). Ringrazio principalmente due persone, Carla Maria Modena
e Stefano Messelodi, per avermi introdotto con pazienza i concetti dell’Image
Processing, per avermi spiegato e fatto capire un sacco di cose e per aver
fatto veramente un ottimo lavoro per render leggibile e corretta questa tesi.
Grazie a loro adesso non sono più cosı̀ ignorante in questo campo.
Voglio anche ringraziare Roberto Brunelli per le piacevoli discussioni sulla
Computer Graphics, sul C++ e Java e sul Lego Mindstorm, Michele
Zanin, Filippo Bertamini, Claudio Andreatta, Dimitri Giordani, Alessandro
Giacomini e Oswald Lanz per l’amicizia e la pazienza dimostratami e i miei
“compagni d’avventura” Alessandro Roat e Alessandro Santuari.
Desidero ringraziare tutti i miei amici per il loro supporto e per la loro
pazienza, per avermi sopportato quando sono stato assente e scontroso in
questo periodo.
Infine, il ringraziamento più grande ai miei genitori, a mio padre Maurizio
e mia madre Licia, che hanno sempre creduto in me, e a mia sorella Chiara,
che ha letto questa tesi correggendo tutti gli accenti e gli apostrofi anche se
non ha la minima idea di ciò di cui si parla.
Indice
1 Introduzione
7
2 Il colore
2.1 Rappresentazione del colore . . . . . . . . . . . . . . .
2.1.1 Il modello Fisico del colore . . . . . . . . . . . .
2.1.2 Il modello Percettivo del colore . . . . . . . . .
2.1.3 La teoria tricromatica . . . . . . . . . . . . . .
2.1.4 Conciliare le tre teorie . . . . . . . . . . . . . .
2.2 Spazi di colore in computer graphics e image processing
2.2.1 RGB . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 RGBN (o r0 g 0 b0 ) . . . . . . . . . . . . . . . . . .
2.2.3 YUV . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4 XYZ . . . . . . . . . . . . . . . . . . . . . . . .
2.2.5 CIE L*a*b* . . . . . . . . . . . . . . . . . . . .
2.2.6 HSV (HSI, HSL, HSB) . . . . . . . . . . . . . .
2.3 Misure di similarità e differenza tra colori . . . . . . . .
2.3.1 Norma L1 e L2 . . . . . . . . . . . . . . . . . .
2.3.2 Vector Angle . . . . . . . . . . . . . . . . . . .
2.3.3 Combinazione . . . . . . . . . . . . . . . . . . .
2.4 Misure di similarità tra zone di immagini a colori . . .
2.4.1 Istogrammi e Signature . . . . . . . . . . . . . .
2.4.2 La Earth Mover’s Distance . . . . . . . . . . . .
3 La tessitura
3.1 Trasformata Wavelet . . . . . . . . . . . . .
3.1.1 Filtri per la trasformata . . . . . . .
3.1.2 Tipo di decomposizione . . . . . . . .
3.1.3 Estrazione caratteristiche e metriche
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
10
10
11
13
13
17
17
18
19
19
20
21
23
24
26
26
28
28
30
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
32
34
36
37
38
.
.
.
.
.
4
INDICE
4 Tecniche di segmentazione
4.1 Approcci basati su misure di discontinuità . . . .
4.2 Approcci basati su misure di omogeneità . . . . .
4.2.1 Histogram thresholding . . . . . . . . . . .
4.2.2 Clustering . . . . . . . . . . . . . . . . . .
4.2.3 Region splitting & merge e Region growing
5 L’algoritmo proposto
5.1 Scelta iniziale dei semi
5.2 Strategia di growing .
5.3 Metriche di distanza .
5.4 Implementazione . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
46
47
47
47
48
.
.
.
.
50
53
58
60
62
6 Risultati sperimentali
7 Conclusioni
7.1 Conclusioni . . . . . . . . . . . . .
7.1.1 Il framework . . . . . . . . .
7.1.2 Il colore . . . . . . . . . . .
7.1.3 La tessitura . . . . . . . . .
7.1.4 Selezione dei candidati . . .
7.1.5 Selezione dei semi . . . . . .
7.2 Lavori futuri . . . . . . . . . . . . .
7.2.1 Miglioramenti dell’algoritmo
7.2.2 Utilizzi dell’algoritmo . . . .
67
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
81
81
81
81
82
82
82
83
83
83
A Edge detection
84
A.1 Difference Vector . . . . . . . . . . . . . . . . . . . . . . . . . 84
A.2 Entropy Thresholding . . . . . . . . . . . . . . . . . . . . . . . 85
B Polimorfismo statico vs. polimorfismo dinamico
87
C L’algoritmo del trasporto
90
D Utilizzo di istruzioni SIMD
96
Elenco delle figure
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
3.1
3.2
3.3
3.4
3.5
5.1
Una sfera ombreggiata . . . . . . . . . . . . . . . . . . . . .
Risposta dei tre tipi di coni al variare della lunghezza d’onda
Test percettivo per il color-matching . . . . . . . . . . . . .
Funzioni di color matching per i primari RGB . . . . . . . .
Funzioni di color matching per i primari XYZ . . . . . . . .
Lo spazio di colore RGB visto lungo la diagonale principale
dal bianco (0,0,0) al nero (1,1,1) e dal nero (1,1,1) al bianco
(0,0,0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Una fetta dello spazio di colore CIE XYZ . . . . . . . . . . .
Lo spazio di colore CIE Lab . . . . . . . . . . . . . . . . . .
Lo spazio di colore HSV . . . . . . . . . . . . . . . . . . . .
Piani di RGB a luminosità differente . . . . . . . . . . . . .
La signature dell’immagine Lena e i rispettivi pesi . . . . . .
.
.
.
.
.
12
14
14
15
16
.
.
.
.
.
.
18
19
21
22
25
30
La trasformata wavelet discreta (DWT, sopra) e la trasformata
wavelet a pacchetti (PKWT, sotto) . . . . . . . . . . . . . . .
L’immagine flower garden . . . . . . . . . . . . . . . . . . . .
La trasformata wavelet a pacchetti (PKWT) dell’immagine
flower garden . . . . . . . . . . . . . . . . . . . . . . . . . . .
La mappa delle classi di texture ottenuta dall’applicazione
dell’algoritmo proposto sull’immagine flower garden . . . . . .
Recenti ricerche psicofisiche hanno dimostrato che la percezione
del colore nel sistema visivo umano dipende dalle frequenze
spaziali fra i colori. Questo, tuttavia, era già stato intuito dai
pittori impressionisti cento anni prima. . . . . . . . . . . . . .
36
37
38
40
42
Lo schema dell’algoritmo di region growing proposto ed
implementato. . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6
ELENCO DELLE FIGURE
5.2
5.3
5.4
5.5
5.6
5.7
5.8
Il metodo adottato per estrarre regioni dalla signature uniforme (regioni con texture) . . . . . . . . . . . . . . . . . . . .
Metodo per la selezione dei semi provenienti da criteri diversi.
Algoritmo per il growing basato sulla strategia proposta . . . .
Calcolo della distanza tra pixel e regione . . . . . . . . . . . .
Il digramma delle classi UML relativo alle classi che implementano le metriche . . . . . . . . . . . . . . . . . . . . . . .
Il digramma delle classi UML; per questo digramma, piuttosto
complesso, è stata adottata l’estensione basata sul colore
proposta per UML 2.0. L’utilizzo del colore aggiunge una
dimensione al digramma, rendendone più facile la comprensione. I colori adottati sono quelli proposti: giallo per le classi
centrali, quelle che rivestono un ruolo centrale nel digramma;
blu per le classi che rappresentano dati; arancione per i punti
di estensibilità; verde per le classi che nel digramma rivestono
un ruolo secondari; grigio per le classi provenienti da librerie .
Il digramma di sequenza UML relativo alle fasi di scelta iniziale
dei semi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1 L’immagine di test baboon . . . . . . . . . . . . .
6.2 Le prestazioni dell’algoritmo proposto a confronto
di JSEG . . . . . . . . . . . . . . . . . . . . . . .
6.3 L’immagine di test flower garden . . . . . . . . .
6.4 L’immagine di test parrots . . . . . . . . . . . . .
6.5 L’immagine di test house . . . . . . . . . . . . . .
6.6 L’immagine di test hand . . . . . . . . . . . . . .
6.7 L’immagine di test houses . . . . . . . . . . . . .
6.8 L’immagine di test newspaper . . . . . . . . . . .
6.9 L’immagine di test newspaper (continua) . . . . .
6.10 L’immagine di test flowers2 . . . . . . . . . . . .
6.11 L’immagine di test house2 . . . . . . . . . . . . .
6.12 L’immagine di test geneva1 . . . . . . . . . . . .
. . . . . .
con quelle
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
56
57
59
61
63
64
66
. 69
.
.
.
.
.
.
.
.
.
.
.
70
71
72
73
73
75
76
77
78
79
80
A.1 Gli indici dei pixel in un intorno 3x3 . . . . . . . . . . . . . . 84
C.1 I primi passi della prima fase . . . . . . . . . . . . . . . . . . . 92
C.2 Due esempi di ciclo . . . . . . . . . . . . . . . . . . . . . . . . 93
C.3 Uno scambio variabile uscente-entrante . . . . . . . . . . . . . 94
Capitolo 1
Introduzione
“E’ giunto il momento -disse il Tricheco- di parlare di molte cose”
L.Carrol, Alice nel paese delle meraviglie
La segmentazione delle immagini è un problema chiave nella computer
vision. La segmentazione è un processo che permette di suddividere
l’immagine in regioni significative che corrispondono a oggetti, o parti
di oggetti, in essa rappresentati, un primo passo verso l’estrazione di
informazioni semantiche da una scena. In principio (fino ai primi anni ’80) la
ricerca si è concentrata su tecniche volte ad estrarre il contorno degli oggetti,
come l’edge detection, o a separare porzioni di oggetti, come il thresholding.
Queste tecniche, dette bottom–up, realizzano la segmentazione partendo da
caratteristiche di basso livello dell’immagine, a prescindere dal contenuto
semantico.
Una segmentazione “perfetta” in oggetti significativi non è ottenibile senza
una conoscenza di alto livello dell’immagine. La ricerca di oggetti nella scena
ha portato allo sviluppo di tecniche basate su modelli, come gli active contour
snakes o il template matching. Queste tecniche, dette top–down, permettono
di ottenere dei buoni risultati se applicate a problemi specifici.
Spesso la conoscenza a priori della scena non è sufficiente, o non è disponibile,
e quindi c’è bisogno di un metodo per estrarre delle regioni primitive che
forniscano la base di partenza per i modelli utilizzati dalle tecniche top–down.
8
Introduzione
Nell’estrazione delle regioni primitive, che costituiscono una segmentazione
di primo livello, i metodi bottom–up giocano un ruolo fondamentale. L’accuratezza della segmentazione iniziale influenza in maniera pesante le fasi
successive.
Per questi motivi il metodo di segmentazione iniziale deve essere flessibile,
cioè deve fornire risultati soddisfacenti quando applicato a tipi di immagini
differenti, e deve fornire una segmentazione il più accurata possibile,
cercando di evitare la sotto-segmentazione (fusione nella stessa zona di oggetti
semanticamente diversi) e di limitare la sovra-segmentazione (divisione in
zone diverse di un oggetto unico dal punto di vista semantico).
La segmentazione primaria di un’immagine, non presuppone nessuna
conoscenza semantica della scena, e quindi non è possibile garantire che
questi vincoli siano soddisfatti. Tuttavia si può garantire la suddividivisione
di un’immagine in regioni differenti in modo che ogni regione sia omogenea o
uniforme rispetto a un dato criterio e che l’unione di due regioni non lo sia.
In [9] è data la seguente definizione formale del problema: Detto P ()
un predicato di omogeneità definito su un gruppo di pixel connessi, la
segmentazione è la partizione dell’insieme F in sottoinisiemi connessi -o
regioni- (S1 , S2 , ..., Sn ) non vuoti tali che:
n
[
Si = F
Si ∩ Sj = ® (i 6= j)
i=1
Con il predicato P (Si ) = true per ogni regione Si e P (Si ∪ Sj ) = f alse con
(i 6= j) e Si , Sj regioni confinanti.
Facendo cosı̀ si sposta il concetto di segmentazione dalla identificazione degli
oggetti semantici ad un requisito di omogeneità sulle regioni (insiemi di pixel
connessi).
Per ottenere una segmentazione primaria il più vicina possibile a quella
desiderata è fondamentale la scelta, spesso dettata dall’ambito applicativo,
del predicato di omogeneità. Infatti la partizione di un’immagine in regioni
omogenee non garantisce la suddivisione in oggetti semantici: citando [12],
“The image segmentation problem is basically one of psycophysical perception,
and therefore not susceptible to a purely analytical solution” (il problema della
segmentazione di immagini è un problema di percezione psico-fisica e quindi
non è risolubile in maniera completamente analitica). Il problema della
segmentazione automatica (non supervisionata) di immagini è mal definito,
9
proprio a causa del fatto che gli oggetti semantici spesso non corrispondono
a zone omogenee rispetto a caratteristiche di basso livello (colore, tessitura,
...). Tuttavia, se misuriamo la similarità tra zone in maniera simile a quella
dell’occhio umano, cioè usiamo misure di similarità e di omogeneità di regioni
corrette da un punto di vista percettivo, possiamo avvicinarci al risultato. E’
stato dimostrato che la percezione del colore e della tessitura è fondamentale
nella visione umana [2].
L’approccio migliore quindi sembra quello di seguire e cercare di imitare nel
modo più fedele possibile il sistema visivo umano, utilizzando le informazioni
congiunte di colore e tessitura per ottenere delle misure di similarità e
omogenità corrette da un punto di vista percettivo.
Negli ultimi anni sono state introdotte nuove metriche per la misura
della distanza tra colori [31] e della distanza colorimetrica tra immagini
o tra regioni all’interno di un’immagine [23], nuovi approcci a tecniche di
segmentazione esistenti [18, 33, 30] e nuovi metodi per l’analisi, la descrizione
e la classificazione di tessiture [1, 25, 19].
Ai progressi nei singoli campi, non ha fatto riscontro un uguale progresso
nell’utilizzo combinato di questi strumenti applicati alla segmentazione di
immagini.
Questo lavoro di tesi si propone di fare un passo in avanti in questa direzione,
introducendo un nuovo algoritmo per la segmentazione, basato sulla tecnica
del region growing e sull’utilizzo congiunto di caratteristiche di colore e
tessitura. Il capitolo 2 introduce gli aspetti più importanti legati all’analisi
del colore, con un breve accenno alla teoria del colore, la descrizione dai vari
spazi di colore esistenti, la presentazione delle metriche usate per misurare
la distanza colorimetrica tra colori e tra zone di un’immagine. Nel capitolo 3
viene dato un ragguaglio sulle varie tecniche di estrazione di caratteristiche
da una tessitura, con particolare attenzione ai metodi di analisi nello spazio
delle frequenze usando le Wavelet.
Nel capitolo 4 viene fornita un’introduzione al problema della segmentazione
con i vari approcci utilizzati in letteratura. L’algoritmo proposto per la
segmentazione basata su colore e tessitura viene illustrato in dettaglio nel
capitolo 5. Il capitolo 6 è dedicato ai risultati sperimentali, e le conclusioni
sono presentate nel capitolo 7.
Capitolo 2
Il colore
“Le ombre non sono nere; nessun ombra è nera. La natura conosce solo i
colori. Bianco e nero non sono colori”
A. Renoir
2.1
Rappresentazione del colore
Il primo aspetto da prendere in esame è quello di come rappresentare i colori
in modo corretto sia da un punto di vista fisico che percettivo.
A questo scopo vengono introdotte le tre maggiori teorie sulla rappresentazione dei colori e dello spazio in cui s ono inseriti: il modello Fisico del
colore, il modello Percettivo del colore e la teoria tristimolare.
2.1.1
Il modello Fisico del colore
La branca della fisica che si occupa di descrivere le proprietà della luce e del
colore si chiama colorimetria.
La colorimetria specifica il colore usando tre coefficienti: la lunghezza d’onda
dominante, la purezza e la luminanza.
Come è noto, la luce è energia elettromagnetica nella regione dello spettro che
ha lunghezza d’onda compresa tra 400 e 700 nm, che è percepita dall’occhio
2.1 Rappresentazione del colore
11
umano come colore dal viola al rosso.
Un colore è quindi rappresentabile tramite una distribuzione spettrale di
energia nella zone del visibile.
Volendo campionare uno spettro di energia senza perdita di informazione
si dovrebbe utilizzare un numero praticamente infinito di livelli, tuttavia
possiamo descrivere l’effetto visivo di ogni distribuzione con una tripla
(lunghezza d’onda dominante, purezza e luminanza).
E’ importante notare che una tripletta non rappresenta univocamente
un’unica distribuzione: molte distribuzioni di energia differenti producono
lo stesso colore, “sembrano” uguali, e sono descritte dalla stessa tripletta.
La relazione tra distribuzioni e triplette è dunque di molti-a-uno.
2.1.2
Il modello Percettivo del colore
Una volta introdotto lo spazio di colore fisico, è necessario fare un’osservazione importante: il colore non è una proprietà fisica degli oggetti, come il
loro peso o il loro volume. Il colore è una rappresentazione percettiva della
distribuzione di energia elettromagnetica emessa o riflessa da un oggetto, un
prodotto del sistema visivo umano [3].
Lo spazio di colore percettivo è la rappresentazione che la nostra mente dà
alla percezione del colore, a come i colori sono in relazione l’uno con l’altro
e che posizione occupano relativamente agli altri colori.
La percezione intuitiva e umana del colore solitamente si poggia su tre
quantità, chiamate hue, saturazione e luminosità (hue si può tradurre
approssimativamente con “tinta”, ma per evitare confusioni in questa tesi
si fa riferimanto ad essa con il termine originale).
Questi tre termini corrispondono grossomodo alle nozioni fisiche di lunghezza
d’onda dominante, purezza e luminanza.
Infatti la hue indica il colore puro a cui si fa riferimento, come rosso,
giallo, verde, viola. La saturazione indica quanto il colore è distante da
un grigio della stessa intensità. Per esempio, il rosso è molto saturo, il rosa
poco, e in generale i colori pastello sono poco saturi. La luminosità indica
(indipendentemente dalla lunghezza d’onda), l’intensità della luce riflessa o
emessa da un oggetto; per fare un esempio, un oggetto illuminato in modo
non uniforme, come la sfera in figura 2.1, ha hue e saturazione costanti ma
intensità variabile.
Per poter avere un’utilità pratica nell’analisi di immagini, i colori devono
12
Il colore
Figura 2.1: Una sfera ombreggiata
essere messi in relazione tra di loro all’interno di uno spazio e misurati. Per
fare ciò possiamo confrontare visivamente un campione di colori “sconosciuti”
(cioè non ancora classificati) con un insieme di campioni standard. I campioni
e i colori sconosciuti vanno osservati sotto una luce standard, visto che il
colore riflesso da un oggetto dipende sia dal colore della superficie che da
quello della luce. Uno spazio di colore costruito usando questa tecnica è
lo spazio di colore di Munsell, uno spazio 3D che ha come dimensioni la
hue, la saturazione e la luminosità. In questo spazio i colori sono ordinati
in modo da avere un’uguale distanza percettiva dai vicini. Uno spazio di
colore che rispetta questa proprietà è detto color-order system. Da questo
modello si può anche notare come il colore aggiunga una notevole quantità
di informazione rispetto alla scala di grigio: la sola luminosità veicola la
stessa quantità di informazione di un valore in scala di grigio, e in più si ha
a disposizione l’informazione di altre due componenti che rappresentano la
crominanza.
Infine è necessario fare un appunto: si è già detto che la rappresentazione
dello spazio di colore di Munsell è soggettiva.
Questo significa che, se da un lato questa rappresentazione è percettivamente
corretta, dall’altro il posizionamento e la distinzione tra colori dipendono dal
giudizio di un osservatore, dall’illuminazione, dalla grandezza dei campioni
da confrontare e dagli altri colori presenti nella scena, come lo sfondo.
Potrebbe quindi essere problematico definire in modo univoco e quantitativo
lo spazio di colore di Munsell.
2.1 Rappresentazione del colore
2.1.3
13
La teoria tricromatica
La teoria tricromatica si basa sulla constatazione che all’interno della retina
nell’occhio umano ci sono tre tipi di recettori sensibili al colore.
Questi recettori, detti coni, hanno sensibilità massima a radiazione di
lunghezza d’onda diversa, corrispondenti circa a quelle della luce rossa, verde
e blu.
Questa teoria è molto attraente, in quanto porta a un modello di rappresentazione del colore, il modello tricromatico, che è molto semplice e conosciuto.
Questo modello è basato sull’idea che la somma in parti diverse di rosso, verde
e blu (i tre colori fondamentali, detti primari) possa generare l’intero spazio
dei colori.
Questa assunzione è quasi vera: con questo modello è possibile generare una
numero notevole di colori differenti (altrimenti i monitor CRT, basati su
questa tecnica, non funzionerebbero), ma non tutti. Alcuni colori nella zona
del viola non possono essere riprodotti con una mistura additiva di rosso,
verde e blu.
Tuttavia lo spazio di colore più noto e usato in computer graphics è lo
spazio basato su questo modello, lo spazio RGB. Questo spazio è molto noto e
usato perchè la maggior parte dei sensori fisici alla luce colorata (come i coni
nell’occhio umano o i sensori CCD nelle telecamere) usano questo modello,
cosı̀ come i monitor CRT. Si può dire che lo spazio RGB sia quello “nativo”
per la computer graphics.
2.1.4
Conciliare le tre teorie
Fino a questo punto sono state introdotte tre teorie della rappresentazione
dello spazio di colore in apparente contrasto tra di loro, ognuna con i suoi
punti di forza e le sue debolezze: il modello fisico dà una descrizione oggettiva
e quantitativa dei colori; il modello percettivo segue il modo umano di
rappresentare il colore come composizione di hue, saturazione e luminosità
ed è quindi percettivamente corretto; il modello tricromatico si basa sulla
natura tristimolare della retina, dei sensori CCD e dei monitor CRT ed è
quindi molto semplice da descrivere e usare con un computer.
Vediamo come i tre modelli delineati da queste terorie possano essere concliati
14
Il colore
tra loro.
Il modello fisico e la teoria tristimolare: lo spazio XYZ
L’anello di giunzione tra il modello fisico e la teoria tristimolare è dato da
due funzioni chiamate spectral-response (risposta spettrale) e color-matching
(corrispondenza di colore).
Figura 2.2: Risposta dei tre tipi di coni al variare della lunghezza d’onda
La prima funzione (figura 2.2) indica la risposta (in percentuale di luce
assorbita) dei tre tipi di coni presenti nella retina umana al variare della
lunghezza d’onda della radiazione elettromagnetica all’interno dello spettro
del visibile.
Questa funzione ci permette di costruire la seconda, la funzione di color-
Figura 2.3: Test percettivo per il color-matching
matching, che indica la quantità di luce rossa, verde e blu necessaria per un
2.1 Rappresentazione del colore
15
osservatore medio per avere un colore che corrisponda esattamente a un colore
C di luminanza costante, per ogni valore di lunghezza d’onda dominante nello
spettro del visibile.
In pratica, per ogni colore di riferimento se ne crea un altro miscelando luce
rossa, verde e blu nelle quantità necessarie per avere un colore uguale sia da
un punto di vista percettivo che fisico. (figura 2.3).
Purtoppo osservando la figura 2.4 si nota che ci sono dei valori negativi: per
Figura 2.4: Funzioni di color matching per i primari RGB
ottenere certi colori si dovrebbe “sottrarre” luce di uno dei tre colori primari.
Questo non fisicamente possibile: per definire il digramma si aggiunge la
quantità di luce necessaria al campione.
Questo risultato conferma l’affermazione fatta in precedenza: ci sono colori
non ottenibili come combinazione lineare additiva di rosso, verde e blu.
Per risolvere questo problema la commissione CIE (Commission International
de l’Eclairage creò nel 1931 un nuovo spazio di colore, lo spazio XYZ. Questo
è uno spazio colore tridimansionale come RGB, ma i suoi tre colori primari
(X, Y e Z) sono definiti in tale che tutti i colori percepiti dall’occhio umano
siano rappresentabili tramite una combinazione lineare di essi: ogni colore
visibile C avente distribuzione spettrale d’energia P (λ), è definito come
C = XX + Y Y + ZZ
dove:
Z
X=k
P (λ)x̄λ dλ
Z
Y =k
P (λ)ȳλ dλ
16
Il colore
Z
Z=k
P (λ)z̄λ dλ
Le funzioni di color-matching x̄λ , ȳλ e z̄λ sono state ricavate da osservazioni
sperimentali e tabulate a intevalli di 1nm. Inolter il primario Y ha associata
una funzione di matching che corrisponde alla risposta percettiva alla
luminosità dell’occhio umano.
Ricordo che una funzione di color-matching è una funzione che indica la
quantità di ogni primario (X, Y , Z o R, G, B) neccessaria a un osservatore
medio per avere un colore che corrisponda esattamente a un colore C di
luminanza costante, per ogni valore di lunghezza d’onda dominante nello
spettro del visibile.
E’ interessante notare che le tre funzioni color-matching dello spazio CIE sono
combinazioni lineari delle funzioni color-matching per i tre primari di RGB.
Ma, mentre le funzioni color-matching dello spazio RGB hanno valori negativi
(cioè non tutti i colori sono rappresentabili tramite addizione di rosso, verde
e blu), le funzioni color-matching dello spazio XYZ sono positive (cioè tutti
i colori visibili sono ottenibili tramite addizione di X, Y e Z).
Figura 2.5: Funzioni di color matching per i primari XYZ
Il modello percettivo e lo spazio colore XYZ: L*a*b* e L*u*v*
Lo spazio XYZ riesce a combinare il modello fisico e la teoria tristimolare.
Tuttavia rimane un problema nel sistema della CIE.
Consideriamo la distanza tra il colore C1 (X1 , Y1 , Z1 ) e il colore C1 + ∆C, e
la distanza tra il colore C2 (X2 , Y2 , Z2 ) e il colore C2 + ∆C.
La distanza misurabile è la stessa, ma la distanza percepita è spesso
2.2 Spazi di colore in computer graphics e image processing
17
differente.
Da qui sorge la necessità di avere uno spazio percettivamente uniforme,
uno spazio in cui colori che sono ugualmente distanti siano percepiti come
ugualmente distanti da un osservatore umano.
Nel 1976 e negli anni seguenti sono stati sviluppati dal CIE due spazi che
possiedono questa caratteristica, ottenibili come trasformazione non lineare
dello spazio XYZ. Questi spazi sono lo spazio CIE L*a*b* e lo spazio CIE
L*u*v*.
Per dettagli sullo spazio Lab e su come sia stato dimostrato che questo spazio
è percettivamente uniforme, si veda le sezione successiva.
2.2
Spazi di colore in computer graphics e
image processing
Dopo questa introduzione sulle rappresentazioni fisica, percettiva e tristimolare del colore, vediamo in dettaglio gli spazi di colore più significativi e usati
in computer graphics e nell’ image processing.
2.2.1
RGB
Lo spazio di colore RGB è considerato lo spazio nativo della computer
graphics (la codifica su file, i monitor CRT, i sensori CCD di telecamere
e scanner e la parte di rasterizzazione delle schede grafiche solitamente usano
questo modello), ed è quindi il più diffuso.
RGB impiega un sistema di coordinate cartesiane, e può essere rappresentato
come un cubo unitario, con bianco e nero sui vertici della diagonale principale
e i livelli di grigio sulla diagonale principale (figura 2.6).
RGB è un buon spazio per la computer graphics, ma non per l’image
processing and analysis.
I suoi difetti maggiori sono l’alta correlazione tra i tre canali (variando
l’intensità, tutte e tre le componenti cambiano) e il fatto che non è
percettivamente uniforme.
Tuttavia, questi difetti possono essere mitigati o resi nulli da una scelta
accurata della metrica, come viene spiegato in seguito.
18
Il colore
Figura 2.6: Lo spazio di colore RGB visto lungo la diagonale principale dal
bianco (0,0,0) al nero (1,1,1) e dal nero (1,1,1) al bianco (0,0,0)
Il vantaggio principale di questo spazio è che è subito disponibile e non
necessita di nessuna trasformazione.
2.2.2
RGBN (o r0 g 0 b0 )
Questo spazio di colore deriva direttamente da RGB, togliendo uno dei suoi
difetti: la forte dipendenza ai cambiamenti di intensità.
Questo risultato è ottenuto normalizzando i colori, rendendo cosı̀ uniformi
le variazioni di intensità attraverso la distribuzione spettrale. Lo spazio di
colore normalizzato è definito come:
r=
R
R+G+B
g=
G
R+G+B
b=
B
R+G+B
Tuttavia RGBN ha un altro problema: se l’intensità è molto bassa, i colori
normalizzati sono molto rumorosi: piccole variazioni producono oscillazioni
notevoli.
2.2 Spazi di colore in computer graphics e image processing
2.2.3
19
YUV
Questo è il secondo spazio, dopo RGB, che può essere definito “hardwareoriented”. La sua realizzazione e la sua diffusione, infatti, sono legati
a dispositivi hardware, in questo caso televisori, telecamere e schede di
acquisizione video.
Lo spazio YUV è infatti quello preferito per la trasmissione di video, sia
analogico che digitale. Anche gli algoritmi di compressione JPEG e MPEG
si appoggiano su questo spazio di colore per compiere le loro elaborazioni
[28].
Esistono diverse formule per ricavare YUV da RGB; tutte sono trasformazioni
lineari, ma differiscono per i coefficienti usati. In questo lavoro sono state
adottate le seguenti formule:
y = 0.299r + 0.587g + 0.114b
u = (b − y) ∗ 0.565
v = (r − y) ∗ 0.713
2.2.4
XYZ
Di XYZ si è già parlato nei paragrafi precedenti. I suoi tre primari sono
X, Y , Z e, come si è visto in precedenza, le funzioni di color-matching di
XYZ sono combinazioni lineari di quelle di RGB; i colori di XYZ sono quindi
ottenibili con una trasformazione lineare da RGB.
Figura 2.7: Una fetta dello spazio di colore CIE XYZ
20
Il colore
E’ interessante notare che Y ha una funzione di color-matching che corrisponde esattamente alla funzione di risposta alla luminosità dell’occhio
umano.
La luminosità è quindi ottenibile direttamente da Y, applicando una
trasformazione che tenga conto della risposta non lineare dell’occhio umano:
L∗ = 116
³ Y ´1
3
− 16
Y0
´
Y
+ 0.13793 − 16
L∗ = 116 7.787 ·
Y0
³
Y
> 0.008856
Y0
Y
≤ 0.008856
Y0
(2.1)
E’ importante notare che la trasformazione da RGB a XYZ, e anche da XYZ
agli altri spazi CIE, dipende dalla scelta del “punto di bianco”, cioè delle
coordinate (X0 , Y0 , Z0 ) del colore definito come bianco.
CIE definisce diversi punti di bianco, a seconda della temperatura e della
natura della sorgente luminosa: ci sono punti di bianco per la luce naturale,
per lampade fluorescenti, a filamento e anche per sorgenti a emissione come
monitor o televisori.
In questo lavoro è stato usato il punto di bianco D65, che corrisponde al
punto di bianco per i monitor CRT con temperatura di colore di 6500k e che
viene comunemente usato come simulazione della luce solare.
2.2.5
CIE L*a*b*
Il principale vantaggio per l’uso di Lab nell’image processing sta nel fatto che
Lab è uno spazio percettivamente uniforme.
Questa proprietà di Lab è stata provata anche in maniera sperimentale
usando il metodo delle JND (Just noticeable difference, differenze appena
notabili).
A un osservatore vengono proposte una serie di coppie di tavole, e questi
deve dire quali gli sembrano indistinguibili. I colori indistinguibili vengono
raggruppati in blocchi e la posizione di questi blocchi viene individuata
all’interno dello spazio colore.
Se questi blocchi sono piccoli, di forma ellissoidale, e con misure simili tra
di loro, lo spazio è percettivamente uniforme [3].
I risultati dell’esperimento dimostrano che Lab è percettivamente uniforme
quando come misura di distanza tra i colori viene usata la distanza euclidea
(vedi il prossimo paragrafo), ma solo se le distanze sono piccole, altrimenti
2.2 Spazi di colore in computer graphics e image processing
21
Figura 2.8: Lo spazio di colore CIE Lab
tutto quello che si può dire del confronto tra due colori è che sono diversi.
Lab è ottenibile a partire dallo spazio CIE XYZ tramite delle trasformazioni
non lineari.
L∗ = 116
³
L∗ = 116 7.787 ·
∗
³ Y ´1
3
Y0
Y
> 0.008856
Y0
Y
≤ 0.008856
Y0
− 16
´
Y
+ 0.13793 − 16
Y0
a = 500
µ³
X ´ 13
b∗ = 200
−
X0
µ³ ´ 1
Y
3
Y0
−
(2.2)
³ Y ´1 ¶
3
Y0
³ Z ´1 ¶
3
Z0
Si noti che L* è la luminosità come definita in (2.1).
2.2.6
HSV (HSI, HSL, HSB)
Questi quattro spazi di colore sono molto simili tra di loro: cambia solo la
definizione della luminosità.
V , I, L e B infatti indicano rispettivamente Value, Intensity, Luminance e
Brightness.
Questo spazio è derivato direttamente dallo spazio di colore di Munsell (vedi
paragrafo “Il modello percettivo”) ed è quindi intuitivo e orientato all’utente,
piuttosto che all’hardware [11].
22
Il colore
Lo spazio HSV è rappresentato geometricamente attraverso un sistema di
coordinate cilindriche, e il sottoinsieme dello spazio all’interno del quale il
modello è definito è una piramide a base esagonale o un cono.
Delle tre coordinate cilindriche, la hue è l’angolo, la luminosità (value) è
l’altezza e la saturazione è il raggio.
Figura 2.9: Lo spazio di colore HSV
H = arctan
³
√
´
3(G − B)
(R − G) + (R − B)
V = max{R, G, B}
V − min{R, G, B}
V
Osservando la figura 2.9 si nota che il rosso si trova a 0 gradi, il verde a
120 e cosı̀ via; colori complementari sono scostati di 180 gradi.
Lo spazio HSV è diffuso e usato in image processing, e presenta notevoli
vantaggi pratici.
Per segmentare oggetti in base al colore, senza preoccuparci di ombreggiature
o lucentezze, possiamo applicare algoritmi noti per le immagini a scala di
grigio solo alla hue.
Possiamo anche applicare efficacemente soglie separate ai tre componenti,
per formare regioni di partenza per un algoritmo di region growing.
La Hue è particolarmente utile in presenza di effetti dovuti alla geometria
e all’illuminazione. E’ stato dimostrato che se l’illuminazione proviene da
luce bianca, la hue è invariante rispetto a ombre, ombraggiature e lucentezze
(shadows, shading and highlights).
S=
2.3 Misure di similarità e differenza tra colori
23
Purtroppo questo spazio presenta anche alcuni seri svantaggi che ne pregiudicano o ne rendono problematico l’utilizzo.
Infatti, per valori di V prossimi o uguali a 0, la hue e la saturazione non sono
definiti e per valori di S (saturazione) prossimi o uguali a 0, la hue non è
definita.
Questa ultima singolarità della Hue vicino all’asse del cilindro/piramide non
è eliminabile, e una piccola variazione nei valori di input R, G o B può
portare a un grande salto nei valori trasformati.
Infine valori della hue vicino alle singolarità sono numericamente instabili,
e le singolarità possono portare a discontinuità nella rappresentazione dei
colori.
2.3
Misure di similarità e differenza tra colori
Un passo importante che va affrontato quando si passa da immagini a scala
di grigio a quelle a colori è la definizione di una metrica (o misura) per la
distanza. In un’immagine a scala di grigio, la distanza tra due valori si può
esprimere con una semplice differenza, visto che i valori sono scalari.
Lo stesso non vale per immagini a colori, i cui valori sono vettori composti
dalle tre componenti cromatiche. L’operazione di differenza è sı̀ definita
anche su vettori, ma il risultato non ci da una misura della distanza. Occorre
quindi usare metriche differenti.
In letteratura sono state adottate diverse misure: la più usata è la distanza
euclidea, ma è molto diffuso anche il metodo di effettuare misure basate sulla
differenza di intensità sui singoli piani per poi combinare il risultato.
In questo lavoro sono state studiate e implementate tre misure di distanza:
norma L1 , norma L2 (la distanza euclidea) e Vector Angle (angolo vettore o
distanza angolare).
L’obiettivo è sempre quello di copiare la percezione umana, il concetto
umano di distanza e similarità tra colori. Quindi la bontà di una metrica
va misurata in termini di fedeltà alla percezione umana del colore. Colori
vicini per un osservatore devono dar luogo a misure piccole (distanza ridotta),
mentre colori dissimili devono produrre distanze grandi.
E’ evidente che la bontà di una metrica dipende dallo spazio di colore su cui
è applicata. Se i colori sono disposti nello spazio in modo che colori simili
siano vicini, la distanza euclidea è una buona misura di similarità.
24
Il colore
Spazi che godono di questa proprietà si dicono percettivamente uniformi.
Lab, per esempio, è uno spazio percettivamente uniforme (si veda il paragrafo
precedente).
2.3.1
Norma L1 e L2
La norma L1 è una misura molto semplice, definita come la somma del valore
assoluto delle differenze tra i componenti.
E’ una misura piuttosto diffusa perché è semplice e veloce da calcolare,
tuttavia in questo lavoro non sarà esaminata approfonditamante perché molte
delle considerazioni che saranno fatte a proposito della norma L2 valgono
anche per la norma L1 . Si è quindi preferito concentrarsi sulla distanza
euclidea, che è più complessa e dovrebbe garantire risultati leggermente
migliori rispetto alla norma L1 .
Questa misura è usata di solito per calcolare la distanza in uno spazio a N
dimensioni. E’ definita come:
DE (v~1 , v~2 ) = kv~1 − v~2 k
(2.3)
dove kxk è la norma L2 . Per uno spazio di colore tricromatico (a tre
componenti) la formula diventa:
q
DE (v~1 , v~2 ) =
(v1,1 − v2,1 )2 + (v1,2 − v2,2 )2 + (v1,3 − v2,3 )2
(2.4)
Il problema della distanza euclidea è che in spazi come RGB (ma anche in
HSV e, in misura minore, anche in Lab), è molto sensibile alle variazioni
di luminosità. Infatti la distanza euclidea rappresenta nello stesso momento
differenze in luminosità, saturazione e tinta.
Lo spazio di colore RGB può essere rappresentato con un cubo unitario,
la cui altezza, larghezza e profondità sono le tre componenti RGB. Un singolo
colore quindi può esser visto come un punto in questo spazio tridimenzionale,
o come un vettore che congiunge l’origine (0, 0, 0) a questo punto.
Moltiplicando questo vettore per una costante α si aumenta la luminosità
lasciando inalterata la tinta (figura 2.10).
v~2 = α · v~2
La distanza euclidea tra i due vettori cambia in modo notevole, visto che
tutte e tre le componenti sono cambiate.
2.3 Misure di similarità e differenza tra colori
25
Figura 2.10: Piani di RGB a luminosità differente
Questa caratteristica può essere desiderabile o meno, a seconda che si
vogliano cogliere le differenze tra due colori con la stessa tinta ma luminosità
differente.
In generale questo non è molto desiderabile dato che la percezione umana del
colore è molto più sensibile alle differenze di tinta che a quelle di luminosità.
Inoltre, essendo molto legata alla luminosità, la distanza euclidea su RGB è
molto sensibile a ombreggiature, ombre e lucentezze degli oggetti. Questo è
un problema particolarmente rilevante quando si progettano algoritmi edge
detection o segmentazione, com’è spiegato in seguito.
In altri spazi di colore la distanza euclidea si comporta in modo differente.
Come già detto in precedenza, in Lab per piccole differenze la distanza
euclidea è significativa e rispecchia le differenze percettive.
Anche in spazi come RGBN, dove l’intensità è stata in qualche modo rimossa,
sembra che le differenze tra colori siano caratterizzate piuttosto bene.
26
2.3.2
Il colore
Vector Angle
Questa misura, la distanza angolare tra vettori, è definita e illustata da
Wesolkowski [30].
Wesolkowski definisce questa metrica come:
Ã
DV A
Ã
v~1 T v~2
= sin θ = 1 −
kv~1 k · kv~2 k
!2 ! 1
2
Nel suo lavoro, è mostrato come la distanza angolare sia insensibile
alle variazioni di illuminazione (intensità) nello spazio RGB, ma sensibile
a differenze in tinta e saturazione. Il suo uso come metrica nello spazio di
colore RGB porta a notevoli risultati.
Tuttavia, come già visto per lo spazio HSV, spazi o misure basate su angoli
mostrano un comportamento instabile vicino agli estremi dello spazio RGB
(0, 0, 0) e (1, 1, 1) e portano a valori casuali se la saturazione o la luminosità
sono basse.
Inoltre, il comportamento in altri spazi di colore come Lab e HSV non è
sensibilmente migliore a quello della distanza euclidea. Anzi, il vector angle
quando è applicato a immagini RGB sembra comportarsi meglio di quando
è applicato a immagini Lab.
2.3.3
Combinazione
Per risolvere il problema dell’instabilità del Vector Angle a bassi valori di
intensità e della sua indefinitezza a bassi valori di saturazione sono state
implementate e usate in questo lavoro di tesi delle metriche che combinano
la misura ottenuta con la norma L2 con la misura ottenuta con il Vector
Angle.
Infatti le due combinazioni sono ottenute calcolando sia il Vector Angle che la
distanza euclidea e usando come discriminante la luminosità o la saturazione.
Combinare le due metriche è vantaggioso: insieme tengono conto sia della
variazioni in intensità (o luminanza) che di quelle in crominanza.
Inoltre la combinazione ha il vantaggio di evitare l’uso del Vector Angle
quando uno dei due colori che devono essere confrontati ha una bassa
intensità o saturazione; infatti questa metrica non funziona bene per valori
bassi di intensità o saturazione, poiché con tali valori nello spazio RGB piccole
variazioni in una delle tre componenti producono grandi differenze nell’angolo
2.3 Misure di similarità e differenza tra colori
27
tra i due colori.
Carron e Lambert [4] hanno dimostrato che per valori di saturazione bassi,
l’intensità è più rilevante della tinta, mentre per valori di saturazione più
elevati è la tinta ad avere il peso maggiore. Visto che il Vector Angle è
una metrica studiata per cogliere le differenze di tinta e la distanza euclidea
attribuisce maggior peso all’intensità, combinare le due metriche usando la
prima per valori di saturazione elevati e la seconda per valori bassi dovrebbe
garantire buoni risultati.
La rilevanza data ad una misura piuttosto che all’altra può esser calcolata
come segue: dati due colori, su ognuno di essi si calcola separatamente il
valore di intensità o saturazione e si sfrutta questo valore per stabilire il peso
di una metrica rispetto all’altra mediante la seguente formula:
1
α(value) =
slope(value−of
f set)
1+e
dove value è il valore di intensità o saturazione del colore, offset il punto
centrale della transizione (quello in cui le due misure hanno lo stesso peso) e
slope descrive l’inclinazione in quel punto.
Man mano che value cresce, l’output della funzione α cambia da 0 (influenza
massima della distanza Euclidea) a 1 (influenza massima del Vector Angle).
Comunque, visto che per ogni operazione di misura sono presi in
considerazione due colori e noi desideriamo evitare l’uso del Vector Angle
quando uno dei due colori ha intensità o saturazione bassi, dobbiamo definire
una funzione di influenza che sia la combinazione dell’ α dei due colori.
q
ρ(value1 , value2 ) =
α(value1 ) · α(value1 )
La misura di distanza tra due colori combinata basata sulla luminosità risulta
essere quindi:
µ
´¶
³
DCombLuma (C1 , C2 ) = 1 − ρ L(C1 ), L(C2 )
³
· DE (C1 , C2 ) +
´
ρ L(C1 ), L(C2 ) · DV A (C1 , C2 )
(2.5)
Similmente, quella basata sulla saturazione è definita come:
µ
³
´
DCombSaturation (C1 , C2 ) = 1 − ρ S(C1 ), S(C2 )
³
!
· DE (C1 , C2 ) +
´
ρ S(C1 ), S(C2 ) · DV A (C1 , C2 )
(2.6)
28
2.4
Il colore
Misure di similarità tra zone di immagini
a colori
Il problema appena affrontato -dare una misura dell’omogeneità di una
regione di un’immagine a colori- apre le porte a un problema più ampio:
dare una metrica di similarità o differenza tra due zone di immagini a colori.
In che misura due zone sono simili rispetto al colore? Oppure in che misura
due intere immagini sono simili rispetto al colore?
Il problema, che può essere esteso ad altre caratteristiche di un’immagine
oltre al colore, è quello di introdurre una metrica tra due distribuzioni.
Tipicamente le distribuzioni su cui si va ad operare sono istogrammi;
in seguito, saranno introdotte forme più versatili di distribuzione dette
“signature” (firme).
Per semplicità di notazione, parlando della posizione i − esima all’interno di
un istogramma userò il termine inglese bin i (cesto i).
Sono state proposte molte misure di similarità tra due istogrammi, che
possiamo dividere in due categorie.
Le misure di similarità bin-by-bin confrontano solo la quantità delle caratteristiche che occupano la stessa posizione all’interno dei due istogrammi.
Le misure di similarità cross-bin invece confrontano anche termini che
appartengono a posizioni differenti; per questo, le misure cross-bin fanno
uso di una distanza dij tra le caratteristiche del bin i e del bin j.
In [23] sono presentate varie misure bin-by-bin e cross-bin e viene spiegato
come le misure di entrambe le classi siano spesso insoddisfacenti; queste
metriche, sebbene siano state usate con successo in altri campi, in questo
caso non rappresentano bene la somiglianza percettiva.
2.4.1
Istogrammi e Signature
Prima di introdurre una nuova metrica che si comporti in modo soddisfacente,
conviene fermarsi un attimo sui concetti di distribuzione, istogramma e
“signature”.
Uso di istogrammi
Le distribuzioni multidimensionali, e in particolare gli istogrammi, sono usati
spesso nell’image processing per descrivere e riassumere le caratteristiche di
2.4 Misure di similarità tra zone di immagini a colori
29
un’immagine. Nelle immagini a scala di grigio, l’istogramma monodimensionale delle intensità descrive il contenuto totale di luminosità di un’immagine,
e viene usato in molti algoritmi, specie quando si tratta di stimare dei valori
di soglia.
Nelle immagini a colori, lo stesso compito può essere assolto con una distribuzione tridimensionale; comunque, in questo caso, conviene approssimare
la distribuzione originale con una descrizione più compatta: nello spazio
RGB, per esempio, se si considerano 256 livelli per ciascuna banda si hanno
più di sedici milioni di colori differenti.
Usare una distribuzione che tenga conto di ogni colore è sia inefficiente da
un punto di vista dell’uso delle risorse (memoria e potenza di calcolo) che
inefficace per quanto riguarda la corrispondenza percettiva (nessuno può
distinguere il verde RGB(5, 165, 97) dal verde RGB(6, 165, 97)).
Per questo motivo le distribuzioni multidimensionali vengono compresse
partizionando lo spazio sottostante in un numero fisso di partizioni, chiamate
bin, che di solito hanno dimensione prefissata. La struttura dati risultante è
quantizzata e può essere rappresentata da un istogramma, come si fa con le
immagini a scala di grigio.
Resta comunque il fatto che solo una piccola percentuale dei bin di un
istogramma contiene informazione significativa. Per esempio, se abbiamo una
foto di una pianura verde sovrastata dal cielo azzurro, bastano pochi colori
per descriverla efficacemente. In questo caso un istogramma quantizzato
finemente è piuttosto inefficiente, e avrà molti bin vuoti.
D’altra parte, nel caso di una foto di una composizione floreale con una
moltitudine di colori differenti, un istogramma quantizzato grossolanamente
sarebbe inadeguato.
In breve, gli istogrammi sono stutture dati a dimensione fissa, che difficilmante si possono adattare bene per la descrizione di immagini dal contenuto
differente.
Uso di signature
In [23] è proposta una soluzione a questo problema: viene introdotta una
nuova descrizione della distribuzione tridimensionale del colore detta signature (firma). Queste signature sono formate prendendo dalla distribuzione
originale i cluster (cioè i gruppi di colore) più significativi.
Una signature è quindi un insieme di cluster, ognuno dei quali rappresentato
dal colore dominante e da un peso che dà un’indicazione sulla grandezza
30
Il colore
relativa o assoluta del cluster.
Immagini semplici hanno signature corte, immagini complesse le hanno più
lunghe.
Nell’implementazione fatta durante questo lavoro, i cluster vengono ricercati
tra i bin non nulli della distribuzione tridimensionale del colore.
Viene lasciata grande flessibilità, in quanto è possibile:
- usare come base di partenza una distribuzione quantizzata oppure no,
specificando il livello della quantizzazione;
- specificare il numero massimo di cluster che si vuole includere nella
signature: in questo caso, se i cluster superano il numero specificato,
vengono scartati i meno significativi;
- specificare una soglia al di sotto della quale il peso del cluster viene
considerato nullo (per esempio, per non includere nella signature tutti
i cluster con peso minore dello 0.1% );
57846
50778
40600
21432
17406
13068
12420
8954
8580
8046
6201
3870
1794
1548
1304
1120
1118
987
950
918
786
777
768
744
695
580
486
346
287
282
266
Figura 2.11: La signature dell’immagine Lena e i rispettivi pesi
2.4.2
La Earth Mover’s Distance
Il problema di trovare una metrica che rispecchi il concetto umano di distanza
e similarità tra colori è stato illustrato e discusso in precedenza (paragrafo
2.4 Misure di similarità tra zone di immagini a colori
31
2.4).
Questo problema diventa più evidente quando si presenta la necessità di
confrontare insiemi di caratteristiche piuttosto che singoli colori.
In [23] è dimostrato come una metrica che voglia essere fedele alla distanza
percettiva tra insiemi di caratteristiche debba gestire le corrispondenze che ci
possono essere tra posizioni diverse dell’istogramma (da qui in poi, indicate
con bin).
Sempre in [23], è proposta una metrica basata sul matching di grafi bipartiti
che è definita come il costo minimo necessario per far corrispondere i bin
di un istogramma con quelli di un altro. Questa metrica è chiamata Earth
Mover’s Distance (EMD).
Intuitivamente, date due distribuzioni, una può essere vista come una serie
di mucchi di terra sparsi nello spazio, e l’altra come una serie di buche da
riempire. La distanza tra i mucchi di terra e le buche è la distanza percettiva
tra i colori che rappresentano i vari bin delle distribuzioni. La EMD misura
la quantità di lavoro minimo necessaria per riempire le buche con la terra.
Per calcolare l’EMD è sufficiente risolvere il problema del trasporto, per la
cui soluzione sono noti algoritmi efficienti. Il problema del trasporto è cosı̀
formulato: si supponga di avere un insieme di fornitori, ognuno dei quali
ha un dato ammontare di beni, che deve fornire un insieme di consumatori,
ognuno dei quali ha una data necessità. Il costo di trasporto di un bene per
ogni coppia fornitore-consumatore è considerato noto.
Il problema è quello di trovare il più economico flusso di beni tra fornitori e
consumatori che soddisfi la domanda dei consumatori.
Come si può intuire, il problema della Earth Mover’s Distance e quello del
trasporto sono analoghi.
In Appendice B è descritto l’algoritmo implementato per risolvere entrambi
i problemi.
Prima di concludere il discorso sugli spazi di colore e sulle metriche,
è necessaria un’ultima considerazione. La necessità di una buona metrica
e di uno spazio di colore appropriato deriva anche dal fatto che i metodi
tradizionali per l’edge detection e la segmentazione di immagini a colori
rilavano troppi edge “fantasma” o regioni errate a causa degli effetti ottici
dovuti all’iterazione tra la luce e il materiale dell’oggetto. L’uso di spazi come
HSV o di metriche come il Vector Angle, che riducono il peso della luminosità,
permettono di ridurre il numero di edge o regioni spurie. Infatti, è possibile
dimostrare [30] come alcuni spazi di colore e metriche siano invarianti rispetto
a shadows (ombre), shading (ombreggiatura), e highlights (lucentezze).
Capitolo 3
La tessitura
“...quando guarda tutto l’insieme non si sogna di contare quante sono le
scaglie del salmone, le vede come piccole perle argentate contro il grigio e il
rosa [...]. E l’uva! Vuol contare gli acini? Certamente no. Quello che
colpisce è il tono d’ambra chiara e la polvere che ne modella le forme”
E. Manet
La texture (traducibile in italiano, anche se in modo approssimativo, con
tessitura) è legata alle proprietà intrinseche delle superfici ma, al pari del
colore, non è essa stessa una proprietà delle superfici, bensı̀ un prodotto del
sistema visivo umano, che la associa a superfici che hanno caratteristiche di
colore, intensità e ruvidezza variabili.
Avendo già a disposizione l’informazione sul colore, ci si potrebbe chiedere
perchè ci sia bisogno anche di informazioni sulla tessitura per fornire misure
di distanza e omogeneità che ci consentano di raggruppare i pixel in regioni
dalle caratteristiche uniformi.
Innanzitutto, come già asserito nel capitolo 1, le caratteristiche di tessitura
sono fondamentali nel sistema visivo umano, che le utilizza durante il processo
di image analysis compiuto di continuo dalla corteccia.
La cosa più importante, però, è che la percezione del colore nel sistema visivo
umano dipende dalle frequenze spaziali fra i colori. Colori che compaiono
33
in un pattern multicolore sono percepiti come differenti dagli stessi colori
presenti in un’area uniforme. Questo fatto è stato dimostrato da recenti
ricerche psicofisiche [34], anche se bisogna dire che questa assunzione era
ormai assodata da tempo. A tal proposito si veda la figura 3.5: il pittore
(Claude Monet, Le piramidi di Port-Coton, 1886) accosta sulla tela colori
diversi (verde smeraldo, ocra, giallo, blu), che singolarmente non percepiamo
come il colore del mare, ma che accostati ci danno l’impressione di essere un
colore diverso, quello del mare appunto.
E’ difficile dare una definizione di texture, probabilmente a causa del fatto
che quello ci texture è un concetto fortemente intuitivo, legato a propietà
anch’esse intuitive e pertanto non facilmente misurabili come la ruvidezza,
la regolarità e la granularità.
Partendo da questi concetti, si può comunque azzardare una definizione di
texture come zona di un’immagine che presenta caratteristiche di ruvidezza,
regolarità e granularità simili.
Una definizione simile è data in [13], mentre in [24] ne viene data una più
rigorosa:
Una regione all’interno di un’immagine possiede una tessitura
costante se un’insieme di statistiche locali o di altre proprietà
locali alla regione sono costanti, poco variabili o approssimativamente periodiche.
Per una raccolta di ulteriori definizioni, si veda [29].
In letteratura è stata proposta una gran varietà di metodi per l’analisi
delle tessiture, che possono essere raggruppati in quattro categorie [29]:
1. Statistici: i primi lavori si basavano su statistiche del secondo ordine
per le tessiture. I metodi statistici (che si basano di solito su matrici di
co-occorrenza) ricercano correlazioni locali tra i pixel di un’immagine
su scala fissa.
2. Geometrici: i metodi strutturali o geometrici generano una descrizione della tessitura estraendone delle primitive (dette texton) e
applicando delle regole sintattiche a quest’ultime.
3. Basati su Modelli: negli anni ’80 sono stati sviluppati dei modelli
di texture basati su Gaussian Markov Random Fields (GMRF) e
distribuzioni di Gibbs.
34
La tessitura
4. Basati su analisi del segnale: negli ultimi anni, i modelli basati sullanalisi del segnale visivo con metodi multicanale e multifrequenza hanno ricevuto molta attenzione, in quanto hanno mostrato un’affidabilità
e un’efficienza di gran lunga superiori a quelle dei metodi precedenti.
I buoni risultati nel campo della teoria dei segnali applicata all’analisi
di tessitura -che è ancora campo di ricerca- suggeriscono che le principali
difficoltà nell’ottenere buoni risultati sia dovute alla mancanza di uno
strumento di anali adeguato, che sembra esser stato finalmente trovato nei
metodi di analisi nello spazio delle frequenze, come i filtri di Gabor o le
trasformate Wavelet.
In questo lavoro di tesi si è scelto di concentrarsi sullo studio e
l’implementazione di metodi basati sulla trasformata Wavelet.
3.1
Trasformata Wavelet
La trasformata Wavelet opera la decomposizione atomica multi-livello di un
segnale, rappresentando il segnale di input come la sovrapposizione di una
famiglia di funzioni di base dette appunto Wavelet. Traslare o dilatare la
mother Wavelet (Wavelet madre, la funzione scelta come punto di partenza
per costruire l’insieme delle funzioni base) porta a generare un’insieme di
funzioni base. Il segnale è fatto passare attraverso un filtro passa-basso
seguito da un filtro passa-alto. Gli output dei filtri sono sottocampionati
per il prossimo livello di decomposizione, permettendo cosı̀ all’informazione
portata dal segnale di essere rappresentata a diverse scale. Una descrizione
più precisa dal punto di vista matematico esula dagli scopi di questa tesi;
per avere un ragguaglio più preciso si consigliano [14], [29] e [25]. In questa
sede, basti sapere che, analogamente alla trasformata di Fourier e alla FFT,
esistono metodi efficienti di calcolare la trasformata Wavelet di un’immagine
a partire dalla coppia di filtri di cui sopra. Questi algoritmi prendono il nome
di DWT per la trasformata Wavelet piramidale e di PKWT per trasformata
Packet Wavelet (vedi sotto).
Le ragioni che hanno portato alla scelta della trasformata Wavelet come
strumanto per l’analisi delle tessiture sono molteplici:
- Il metodo di segmentazione ideale richiede sia l’identificazione precisa
3.1 Trasformata Wavelet
35
delle caratteristiche di una texture che un’alta risoluzione spaziale per
una localizzazione precisa.
Le trasformate Wavelet, a differenza di altri metodi per l’analisi del
segnale come le trasformate di Fourier, sono localizzate sia nello
spazio che in frequenza. Inoltre il compromesso tra la risoluzione
nello spazio e quella in frequenza è buono, e quindi la segmentazione
basata su caratteristiche calcolate a partire dai coefficienti Wavelet
dovrebbe garantire buoni risultati, anche se piuttosto grossolani per
quanto riguarda la localizzasione spaziale; questo è uno dei motivi per
cui non è possibile offrire una segmentazione basata esclusivamente
sui coefficienti della trasformata Wavelet, ma è necessario sempre
combinare questa tecnica con altre.
- Studi psicofisici [34] hanno dimostrato che il sistema visivo umano
analizza le immagini in modo multiscalare; la prima elaborazione
effettuata dal cervello è un’analisi di frequenza spaziale, che attiva
neuroni diversi nella parte della corteccia adibita alla visione a seconda
della frequenza e dell’orientamento.
Inoltre, quando è necessario il riconoscimento di forme e oggetti,
l’occhio umano analizza il segnale visivo in modo approssimato, e poi
guarda i dettagli per avere una corrispondenza più precisa [2].
La trasformata wavelet permette di procedere all’analisi di un’immagine in maniera simile, dividendo le immagini in sottobande diverse a
seconda della frequenza, dando ad ognuna diverse caratteristiche di
frequenza e orientazione.
- Anche i filtri di Gabor permettono di ottenere il medesimo risulatato,
e sono stati applicati per anni all’analisi di texture. Tuttavia le
Wavelet si comportano altrettanto bene (specie su consideriamo le
packet wavelet, vedi sotto) e sono molto meno costose dal punto di
vista computazionale.
Durante la preparazione di questa tesi sono state presi in considerazione
e studiati diversi modi di utilizzare il potenziale delle trasformate Wavelet
per ottenere una segmentazione dell’immagine.
Infatti, una volta deciso di usare le Wavelet come strumento per l’analisi
delle texture, è necessario scegliere:
36
La tessitura
LL
HL
LLL LHL
HL
LLH LHH
Regione
primaria
LH
HH
C
H1
V1
D
Regione
primaria
LH
C
HH
H1 H2 H3
V1
V2
V3
Figura 3.1: La trasformata wavelet discreta (DWT, sopra) e la trasformata
wavelet a pacchetti (PKWT, sotto)
1. Quale tipo di filtro usare per la trasformata Wavelet. In questo caso,
visto che la trasformata viene effettuata al solo scopo di effettuare
l’analisi dell’immagine, non è neccesario che la ricostruzione sia perfetta
-cioè non è richiesto che l’applicazione della trasformata inversa
riproduca l’esatta immagine di partenza-, quindi possiamo usare anche
filtri non ortogonali (vedi [14]).
2. Quale tipo di decomposizione usare, se una decomposizione piramidale
(vedi figura 3.1 sopra) o una decomposizione ad albero (detta anche
packet wavelet, figura 3.1 sotto).
3. Una volta ottenuti i coefficienti, come utilizzare l’informazione ad
essi associata -cioè a quali delle diverse caratteristiche estraibili dai
coefficienti affidarsi per la descrizione della tessitura- e come misurare
la distanza tra queste caratteristiche in modo percettivamente corretto.
3.1.1
Filtri per la trasformata
Per quanto riguarda il primo punto, sono stati analizzati vari filtri da
impiegare con la trasformata Wavelet: un filtro biortogonale 9/7, un filtro di
Daubechies (daub4, si veda [22]), entrambi dal supporto compatto, nonchè
3.1 Trasformata Wavelet
37
ortogonali e separabli, e un filtro SPLINE, i cui filtri passa-basso e passaalto h0 = [1/4 3/4 3/4 1/4] e h1 = [-1/4 -3/4 3/4 1/4] sono separabili e dal
supporto compatto e quindi utilizzabili con la DWT e la PKWT, anche se
non sono ortogonali.
Quest’ultimo in particolare estrae le caratteristiche di tessitura molto
efficacemente [1] ed è quindi stato scelto per esser utilizzato nell’algoritmo
proposto.
Figura 3.2: L’immagine flower garden
3.1.2
Tipo di decomposizione
Per quanto riguarda il secondo punto, quale tipo di decomposizione usare, è
ormai stato provato in numerosi lavori - [25], [19], [1] - che la decomposizione
packet wavelet offre performance superiori grazie a una analisi più approfondita di tutte le bande. In particolare, usando la trasformata Wavelet
a pacchetti, si produce un’immagine composta da diverse sottobande,
ognuna con le sue caratteristiche di frequenza e orientamento. Si osservi
la figura 3.3: in rosso sono evidenziate le sottobande che rappresentano
alte frequenze verticali, cioè carateeristiche orizzontali, in blu le sottobande
che rappresentano alte frequenze orizzontali, cioè caratteristiche verticali,
mentre le altre sottobande -evidenziate in bianco- rappresentano un misto di
informazione verticale e orizzontale, orientate a diversi gradi (per esempio,
le sottobande sulla diagonale sono orientate a 45o di direzione).
Visto che il sistema visivo umano è più sensibile lungo le direzioni orizzontale
38
La tessitura
e verticale, e che gran parte dell’informazione è convogliata nelle sottobande
orizzontale e verticali (indicate rispettivamente come bande Hi e V i, i =
1, .., n − 1) è possibile utilizzare le sole bande Hi e V i per l’analisi.
Figura 3.3: La trasformata wavelet a pacchetti (PKWT) dell’immagine flower
garden
3.1.3
Estrazione caratteristiche e metriche
Il terzo punto, che riguarda quali caratteristiche estrarre dai coefficienti per
la descrizione della tessitura e come fornire una misura di distanza tra le
regioni che sia percettivamente corretta, è un problema molto complesso e
ancora aperto. In questa tesi sono stati presi in considerazione le seguenti
caratteristiche e misure di similarità.
Direzionalità, regolarità e granularità
Inizialmente si è pensato di poter sfruttare delle misure di direzionalità, regolarità e granularità definite in [1], che si basano sull’analisi dell’istogramma
della matrice di co-correlazione tra righe e colonne delle bande orizzontali
e verticali. Queste dimensioni sono le più importanti da un punto di vista
percettivo; usando una metrica basata su di esse, la classificazione delle zone
si sarebbe basata su caratteristiche simili a quelle percepite dal sistema visivo
3.1 Trasformata Wavelet
39
umano. Esperimenti condotti in questo senso hanno dimostrato che in effetti
queste misure caratterizzano molto bene le texture, ma che non sono adatte
allo scopo di segmentare l’immagine.
In primo luogo il metodo basato su matrice di co-correlazione fornisce buoni
risultati solo se applicato a regioni relativamente grandi. In secondo luogo,
il metodo presuppone di avere come base di partenza una singola immagine,
e per di più quadrata, di una sigola texture.
In pratica quindi questo metodo è molto buono per lo scopo per cui è
stato ideato, la classificazione di texture, e potrebbe anche essere esteso
all’estrazione di features da regioni con texture per l’image retrieval, ma
in questo caso si richiede una previa segmentazione dell’immagine. Proprio
ciò che si sta cercando di ottenere.
Energia locale
La soluzione più frequente in letteratura è quella di usare come caratteristica
per la descrizione della tessitura l’energia locale di ogni coefficiente.
L’energia locale EiV dei coefficienti wavelet {cV i } alla posizione (x, y) è
definita come
EjV (x, y) =
X
(cV j (r, s))2 K(x − r, y − r)
r,s∈Z
dove Z è un’intorno di (x, y) e K(x, y) è un kernel, positivo e dalla forma a
campana, di solito un kernel Gaussiano. L’energia locale EiH è definita nello
stesso modo.
L’energia locale caratterizza bene la tessitura ([26], [29]), e quindi come
caratteristica della tessitura nell’intorno del pixel (x, y) il si può utilizzare il
vettore:
[ log E1V (x, y), log E1H (x, y), log E2V (x, y), log E2H (x, y), ...,
log EnV (x, y), log EnH (x, y)]
(3.1)
Come metrica di distanza è utilizzabile una semplice distanza bin-by-bin
tra i due vettori: la distanza tra due vettori di caratteristiche è la somma
delle distanze (calcolate tramite norma L1 o L2 ) tra elementi del vettore in
40
La tessitura
posizioni corrispondenti. Se f 1 e f 2 sono due vettori delle caratteristiche
definiti come sopra la distanza d tra di loro è pari a:
dW =
n
X
kf 1i − f 2i k
i=1
Analogamente, utilizzando vettori composti dalla media delle energie dei
pixel dalla regione, è possibile ottenere una metrica di distanza tra regioni.
Texture map
Figura 3.4: La mappa delle classi di texture ottenuta dall’applicazione
dell’algoritmo proposto sull’immagine flower garden
In [5] viene descritto un nuovo modo per utilizzare l’informazione
associata ai coefficienti Wavelet ed estrarne caratteristiche misurabili, accreditato di buoni risultati. Questo metodo consiste nel realizzare una
segmentazione grossolana dell’immagine basandosi sull’energia locale dei
n
pixel, classificandoli in 2(2 −1)·2 classi, dove n è il numero di decomposizioni
effettuate dalla trasformata (per esempio, l’immagine in figura 3.3 è stata
relizzata con due decomposizioni, quindi i sui pixel saranno classificati in 64
classi).
Questo modo di calcolare il numero di classi è fondato.
Infatti la classificazione avviene prendendo in considerazione le sottobande
Hi (che sono 2n − 1) e V i, (che sono 2n − 1, in totale numero di classi
m = (2n − 1) · 2) e classificando il pixel in due categorie (sarebbe a dire,
come rilevante o non rilevante per quel dato orientamento e frequenza), per
3.1 Trasformata Wavelet
41
ognuna delle m bande. Questa partizione in due categorie per ognuna delle
bande considerate porta appunto a 2m classi totali (si veda la figura 3.4).
Il risultato di questa segmentazione “grossolana” viene combinato con
l’informazione sul colore in un modo molto semplice ma sorprendentemente
efficace: la metriche sui colori vengono “influenzate” dalla classificazione
delle texture, che viene usata come un peso: se due pixel appartengono
alla stessa classe di texture, il peso (Klow ) è minore di 1.0 e quindi la
loro distanza diminuisce, mentre se i due pixel appartengono a classi di
texture diverse la distanza viene leggermente aumentata moltiplicandola per
un fattore maggiore di 1.0 (Khigh ) .
(
dtexture (p, R) =
Klow se classe(p) = classe(R)
Khigh altrimenti
42
La tessitura
Figura 3.5: Recenti ricerche psicofisiche hanno dimostrato che la percezione
del colore nel sistema visivo umano dipende dalle frequenze spaziali fra i
colori. Questo, tuttavia, era già stato intuito dai pittori impressionisti cento
anni prima.
Capitolo 4
Tecniche di segmentazione
“Quicquid est in intellectu praesse debere in sensu.”
(Bisogna avere esperienza di tutto ciò che è nell’intelletto)
Gassendi
“Nec scire fas est omnia.”
(Non è concesso sapere tutto)
Orazio, Odi
La segmentazione è il processo di suddivisione di un’immagine in regioni
distinte in modo tale che ogni regione sia omogenea rispetto ad una data
caratteristica, e che l’unione di due regioni adiacenti non lo sia. La loro unione
deve essere l’intera immagine di partenza. Il processo di segmentazione
è un passo fondamentale nell’ambito dell’image analysis e della pattern
recognition, il cui scopo è di scomporre un’immagine in parti che sono
significative rispetto a una particolare applicazione.
La segmentazione è una fase critica nell’analisi dell’immagine: la precisione e la qualità del risultato della segmentazione possono influenzare molto
pesantemente le fasi successive.
La segmentazione può trarre molti vantaggi dall’uso del colore, perché spesso
un oggetto è formato da parti colorate identificabili dalla segmentazione. La
segmentazione nelle immagini a scala di grigio si basa su criteri legati al
44
Tecniche di segmentazione
valore di luminosità nell’immagine, che può corrispondere sia a variazioni di
tinta che a cambiamenti di illuminazione. In scala di grigio è impossibile
distinguere tra i due, mentre con le immagini a colori questo è possibile. Per
esempio, utilizzando spazi di colori appropriati (come HSV, paragrafo 2.2.6)
o metriche studiate appositamente (come il Vector Angle sugli spazi RGB o
RGBN, vedi paragrafo 2.3.2 a pagina 26) si possono distinguere zone in cui il
colore varia a causa di un cambiamento di tinta da zone in cui il colore varia
a causa di un cambiamento di luminosità dovuto alla geometria dell’oggetto
e all’illuminazione.
Inoltre, come già sottolineato in precedenza, il colore è predominante nel
sistema di visione umano: l’occhio distingue migliaia di colori, ma solo poche
tonalità di grigio. Un sistema che simuli da vicino il modello umano non può
che portare a risulatati che corrispondono maggiormente alle aspettative di
un osservatore umano.
Un buon metodo di segmentazione dovrebbe soddisfare i seguenti criteri:
- Le regioni devono essere il più possibile omogenee
- I confini delle regioni devono essere compatibili con le variazioni della
misura di similarità adottata.
- Aree percettivamente uniformi non dovrebbero essere divise in più
parti. In particolare questo si applica a regioni con ombreggiatura
graduale e a regioni con tessitura.
- Piccoli dettagli, se ben definiti in forma e contrasto, non dovrebbero
essere fusi con le regioni confinanti.
Sono note molte tecniche di segmentazione, sia per quanto riguarda le
immagini a scala di grigio che per quanto riguarda le immagini a colori.
Queste tecniche si differenziano per la definizione del criterio di omogeneità
tra regioni e per l’algoritmo usato per costruire queste regioni.
Le prime tecniche di segmentazione studiate sono state sviluppate per
trattare immagini a scala di grigio, e solo in tempi relativamente recenti il
lavoro si è esteso anche alle immagini a colori.
La scelta di usare immagini a scala di grigio presenta non solo il vantaggio
di trattare con un volume di dati molto minore, ma anche di considerare le
immagini come funzioni scalari a due dimensioni su cui sviluppare algoritmi
45
computazionalmente più semplici.
Gli approcci per la segmentazione di immagini monocromatiche sono
basati su misure di discontinuità o omogeneità nei livelli di grigio dell’immagine. I metodi basati sulla rilevazione di discontinuità partizionano
l’immagine rilevando punti isolati, edge, linee e contorni, mentre gli approcci
basati sull’omogeneità includono l’histogram thresholding, clustering, region
splitting and merging e region growing.
Questi ultimi possono essere ulteriormente suddivisi in tecniche di raggruppamento rispetto alle sole caratteristiche dei pixel (che tengono cioè in
considerazione solo i valori dei singoli pixel) e tecniche basate sul rilevamento
di regioni (e che quindi combinano informazioni sui valori dei pixel con
informazioni spaziali).
La maggior parte degli algoritmi studiati per le immagini monocromatiche
possono essere estesi all’utilizzo con immagini a colori applicando il metodo
separatamente ad ogni componente dello spazio di colore scelto, combinando
i risultati ottenuti tramite un criterio ad hoc per ottenere la segmentazione
finale.
Tuttavia è necessario notare che nel caso di immagini a colori, è importante
sfruttare per ogni pixel l’informazione sul colore nella sua interezza. Quando
il valore del pixel è proiettato sulle tre componenti, l’informazione sul colore
viene frantumata e l’informazione sul colore cosı̀ come viene percepita dagli
esseri umani è persa. Il sistema visivo umano, infatti, non percepisce
un’immagine separata per ogni componente di colore, ma usa l’informazione
sul colore nella sua interezza.
Un approccio migliore è quello di definire delle metriche opportune nello
spazio di colore che giocano il ruolo dell’operazione di differenza usata negli
algoritmi grayscale, nei criteri di omogeneità basati sulla distanza (come il
MAD) e nelle misure di discontinuità.
Prima di passare alla descrizione del metodo oggetto di studio in questa
tesi, è utile una breve rassegna dei principali metodi di segmentazione
bottom–up. Questi metodi sono stati inizialmente studiati e realizzati per
il trattamento di immagini in scala di grigio, ma sono stati in seguito estesi
anche all’utilizzo con immagini a colori. In [6] sono analizzate le varie tecniche
che sono illustrate brevemente nei paragrafi sequenti.
46
Tecniche di segmentazione
4.1
Approcci basati su misure di discontinuità
L’approccio basato sul rilevamento delle discontinuità è meglio noto con il
nome di edge detection (letteralmente“rilevamento dei bordi”).
Questo approccio consente di trovare i contorni delle regioni costituenti la
segmentazione dell’immagine. In un’immagine monocromatica, un edge è
definito come una discontinuità nel livello di grigio, e quindi è rilevato dove
sono presenti differenze significative nella luminosità.
Nelle immagini a colori le informazioni sui bordi sono molto più ricche: per
esempio, si può rilevare un edge tra due zone con stessa luminosità ma tinta
differente. In un’immagine a colori un edge è definito come una discontinuità
locale calcolata nello spazio colore tridimensionale. Tenendo presente questa
affermazione, è possibile seguire almeno tre approcci per l’edge detection [6]:
1. trattare l’immagine a colori come se fosse composta da tre immagini
monocromatiche, applicare su ognuno dei tre piani separatamente un
algoritmo specifico per l’edge detection su immagini a livelli di grigio,
quindi combinare i risultati.
Lo svantaggio è che cosı̀ facendo si perde l’informazione sulla correlazione tra le tre componenti e, in alcuni casi, si può arrivare a risultati
difficili da combinare (per esempio quando i tre gradienti per un pixel
hanno lo stesso valore ma direzioni differenti, o quando un edge si
presenta su uno solo dei tre piani);
2. per mezzo di una misura di similarità e definita valida nello spazio di
colore, rilevare le discontinuità tra le distanze per determinare gli edge.
Anche questo metodo tiene poco conto del fatto che siamo in uno spazio
vettoriale, ma riesce comunque a catturare edge dovuti a differenze di
luminosità, tinta e saturazione;
3. considerare l’immagine come un campo vettoriale bidimensionale; con
questo approccio il valore dell’immagine in una locazione data è un
vettore in R3 . Quindi si definisce una misura del gradiente che sia
significativa nel campo vettoriale, e si calcola la derivata seconda. I
punti in cui la derivata seconda è nulla (zero-crossing) sono gli edge.
Questo approccio è stato introdotto in [7] da Cumani sulla base di un
lavoro di DiZenzo [8].
4.2 Approcci basati su misure di omogeneità
47
Va sottolineato il fatto che l’edge detection in generale non genera una
segmentazione dell’immagine ma fornisce informazioni utili sui confini tra
le regioni a moduli di più alto livello, o può essere usato in combinazione con
altri approcci, come quelli basati su regioni.
4.2
4.2.1
Approcci basati su misure di omogeneità
Histogram thresholding
Histogram thresholding significa letteralmente “sogliatura dell’istogramma”.
Qesto approccio assume che l’immagine sia composta da regioni che differiscono tra loro per l’intervallo di valori dei pixel che le compongono, cosı̀
che l’istogramma di un immagine presenti dei picchi in corrispondenza di
questi valori. I valori che corrispondono a valli nell’istogramma sono utilizzati
come soglie per distinguere le regioni tra di loro.
4.2.2
Clustering
Clustering: raggruppamento in sottoinsiemi di oggetti con caratteristiche
simili, può essere usato come tecnica di segmentazione considerando il livello
di grigio come caratteristica rispetto alla quale raggruppare i pixel. La
segmentazione ottenuta con il clustering trascura la relazione spaziale tra i
pixel. E’ necessaria una fase successiva in cui si tiene conto delle informazioni
spaziali per formare le regioni: pixel adiacenti appartenenti alla stessa classe
costituiscono una regione omogenea.
L’algoritmo più diffuso per il clustering di dati è l’algoritmo K-means, che si
compone dei seguenti passi:
1. si sceglie il numero delle classi, k
2. si scelgono i rappresentanti iniziali dei clusters
3. si classifica ogni dato
4. si calcolano i nuovi centri dei clusters usando i risultati ottenuti al
punto 3
48
Tecniche di segmentazione
5. se i centri sono stabili (non sono cambiati dopo il passo 4 o si sono
sposatati di poco) ci si ferma, altrimenti si torna al punto 3.
Al terzo passo la classificazione è realizzata mediante un algoritmo 1–NN
(1–nearest neighbor, il dato appartiene alla classe a cui è più vicino) usando
la distanza euclidea come unità di misura.
4.2.3
Region splitting & merge e Region growing
Gli approcci basati su regioni sono fra i più diffusi e usati, poichè permettono
di considerare allo stesso tempo informazioni sui valori (livello di grigio o
colore) e dettagli spaziali. Essi comprendono region splitting & merge e
region growing.
Nell’approccio originale del region splitting, la regione di partenza (il
seme) è costituita dall’intera immagine. Se il seme non rispetta il criterio di
omogeneità viene suddiviso in quattro semi. Questa procedura viene iterata
fino a quando tutte le regioni sono omogenee. Solitamente al processo di
splitting viene fatto seguire un processo di merging per fondere le regioni
uniformi che a causa del processo di splitting erano state erroneamente divise.
Lo svantaggio principale di questa tecnica è che tende a produrre regioni
troppo quadrate, spigolose. 1
In generale, in un algoritmo di region growing, viene scelto un insieme di
piccole regioni di partenza dette seeds (semi), che sono espanse per includere
tutti i pixel confinanti che rispettano un criterio di omogeneità; il processo è
ripetuto finchè ogni pixel dell’immagine è assegnato ad una regione.
1
questo è l’algoritmo originale. Più in generale, un algoritmo di split & merge si
compone di due fasi:
1. La fase di split si applica all’intera immagine. Se essa è omogenea rispetto
al predicato la segmentazione termina, essendo costituita dall’intera immagine.
Altrimenti essa viene suddivisa ricorsivamente in parti fino ad ottenere un insieme
di regioni che soddisfano il predicato.
2. Nella fase di merge vengono analizzate tutte le coppie di regioni adiacenti,
verificando il predicato di omogeneità sull’unione, in modo da garantire la
massimalità delle regioni.
4.2 Approcci basati su misure di omogeneità
49
Lo svantaggio principale di questa tecnica sta nella difficoltà di scegliere le
regioni iniziali. L’algoritmo infatti non aumenta nè diminuisce il numero
di regioni, che quindi devono essere una buona base di partenza per i passi
successivi.
Capitolo 5
L’algoritmo proposto
“Nec minor est virus quam quaerere parta tueri.”
(Né minore abilità del trovare le cose nuove è nel saper conservare le già
acquisite.)
Ovidio
Tutte le tecniche presentate nel capitolo precedente sono state studiate a
lungo. In questo lavoro di tesi si è deciso di implementare una variante del
region growing, poiché si è dimostarata una delle tecniche con il più grande
potenziale per poter raggiungere i requisiti delineati nel capitolo 1.
Il fuzionamento di base del region growing è piuttosto semplice da
descrivere: dato un insieme di punti o regioni iniziali, queste regioni vengono
espanse inglobando in esse i pixel limitrofi che superano un test di similarità
con la regione. Se un pixel è candidato per entrare a far parte di due regioni,
cioè confina con più di una regione, viene inglobato nella regione a cui è più
vicino per somiglianza.
Recentemente sono stati introdotti alcuni algoritmi basati sul paradigma
del region growing nell’ambito della segmentazione di immagini a colori:
- In [32] si presenta un algoritmo di region growing classico, in cui si
usa il Vector Angle (si veda 2.3.2) come misura di similarità tra i
51
colori, e la componente principale (PC) della matrice di covarianza
come colore “caratteristico” della regione, con l’obiettivo di fornire una
segmentazione in regioni percettivamente corretta.
- In [10] si utilizza un algoritmo di region growing abbinato a un
algoritmo di edge detection. Dopo aver ottenuto la mappa degli edge, i
centroidi delle regioni delineate dagli edge sono presi come semi per
l’algoritmo di region growing che utilizza una misura di similarità
tra colori. Infine, il risultato dell’algoritmo di region growing viene
integrato con il risultato dell’edge detection per avere dei confini chiusi
e più accurati.
- In [33] viene proposto un metodo per la segmentazione automatica di
regioni caratterizzate da colore e tessitura, chiamato JSEG. Il metodo
si articola in due passi: quantizzazione dei colori e segmentazione
spaziale. Nel primo passo i pixel vengono suddivisi in varie classi
basandosi esclusivamente sull’informazione di colore. Nel secondo passo
si utilizzano la mappa delle classi prodotta al passo precedente e un
criterio per valutare l’omogeneità di un pattern di colore-tessitura
(detto J): applicando il criterio a una finestra locale per ogni elemento
della mappa delle classi si produce una “J-image” i cui valori di minimo
e massimo corrispondono a possibili confini delle regioni. Si procede
quindi con un algoritmo di region growing, che si basa sulle informazioni
delle “J-image” per produrre la segmentazione finale.
Di questi tre approcci, solo JSEG utilizza anche informazioni sulla
tessitura: questo lo rende uno degli algoritmi più interessanti ed utilizzati
(per esempio in sistemi di image retrieval, o in algoritmi di compressione che
richiedono l’identficazione di zone e oggetti come MPEG-7); per le prestazioni
di quest’algoritmo si veda [33].
Esistono tuttavia numerose altre varianti della tecnica di region growing,
che differiscono tra loro in uno o più dei seguenti passi:
Scelta iniziale dei semi: la scelta iniziale dei semi può esser vista come
una procedura di segmentazione incompleta in cui pixel sono assegnati
a delle regioni se questo può esser fatto con alta confidenza. I semi
possono esser selezionati con differenti criteri, ognuno dei quali mostra
buone capacità nel rilevare regioni dalle caratteristiche differenti;
52
L’algoritmo proposto
per esempio un criterio per trovare regioni omogenee rispetto alla
luminosità o ad un colore è quello di specificare una soglia sulla mappa
del gradiente di un’immagine: le componenti connesse formate dai pixel
che stanno al di sotto di questa soglia costituiscono i semi.
Strategia di growing: ad ogni iterazione dell’algoritmo i pixel confinanti
con le regioni presenti formano un insieme, detto insieme dei candidati,
all’interno del quale vengono selezionati alcuni pixel per l’accrescimento
delle regioni. I candidati sono un sottoinsieme dei pixel non assegnati
che meritano di essere analizzati per accrescere le regioni. La modalità
di selezione dei pixel dall’insieme dei candidati e il numero di pixel
selezionati per l’accrescimento dipendono dalla strategia di growing
adottata.
In letteratura si trovano principalmente due strategie:
1. Selezionare per l’accrescimento e inserire nelle rispettive regioni di
appartenenza tutti i pixel dell’insieme dei candidati che superano
un test basato sulle metriche di distanza (vedi sotto). Questa
strategia presenta due debolezze: dipendenza dall’ordine in cui
vengono considerate le regioni e scarso controllo sulla direzione
della crescita delle regioni. Questi difetti portano all’assegnazione
di pixel alle regioni sbagliate.
2. Selezionare per l’accrescimento e inserire nella regione di appartenenza esattamente un pixel per regione, il pixel tra i
candidati per quella regione che si rivela più vicino alla regione in
accordo alla metrica di distanza usata. Questo metodo garantisce
un miglior controllo sulla direzione di crescita delle regioni,
tuttavia l’assegnazione di pixel a regioni errate è ancora possibile.
Seguendo questa strategia, infatti, le regioni tendono espandersi
tutte in ugual misura, un pixel alla volta, cosı̀ è molto probabile
che le regioni più piccole si espandano più del dovuto a spese delle
regioni confinanti.
I problemi propri di queste due strategie possono esser risolti usando
una diversa strategia di growing, che è stata implementata come
parte dell’algoritmo proposto, e quindi verrà illustarata nella prossima
sezione.
Metrica di distanza: le strategie appena descritte si appoggiano su delle
5.1 Scelta iniziale dei semi
53
metriche di distanza per stabilire quali tra i pixel candidati vanno
fusi con le regioni confinanti. Le metriche di distanza forniscono una
misura della distanza tra il pixel canditato e la regione, cioè danno
un’indicazione di quanto il pixel candidato sia adatto a far parte di
quella regione.
In letteratura sono state proposte varie metriche, basate su misure di
discontinuità, similiratà o omogeneità.
Le metriche basate su misure di discontinuità prendono in considerazione il pixel candidato e uno dei pixel appartenenti alla regione
designata, quello adiacente al candidato. Per questi due pixel vengono
calcolate certe caratteristiche dell’immagine, come per esempio il
contrasto [15] o il gradiente. Se la caratteristica è continua tra i due
pixel, allora la metrica fornisce un valore di distanza basso, in modo
che il candidato abbia un’idoneità elevato e un’alta probabilita di esser
selezionato per l’accrescimento dalla strategia di growing. Nel caso in
cui invece ci sia una discontinuità nella caratteristica, a metrica fornisce
un valore di distanza elevato, in modo che sia probabile che il pixel
candidato non venga accorpato alla regione.
Le metriche basate su misure di similarità misurano la distanza tra il
pixel e la regione secondo metriche definite su caratteristiche estraibili
da un pixel o da una regione. Le metriche basate su misure di
omogeneità, infine, misurano l’omogeneità della regione prima e dopo
che il pixel candidato è stato assegnato alla stessa. La variazione di
omogeneità della regione è usata come criterio per stabilire l’idoneità
del pixel alla fusione con la regione.
Per l’algoritmo proposto in questa tesi sono stati considerati questi tre
punti e per ognuno di essi si è studiata e implementata la soluzione che si
é rivelata migliore o più promettente. Lo schema dell’algoritmo di growing
proposto ed implementato è raffigurato in figura 5.1.
5.1
Scelta iniziale dei semi
I risultati ottenuti con un algoritmo di region growing dipendono pesantemente dal numero e dalla posizione delle regioni iniziali, dette seeds (semi).
Questo perchè la fase di growing dell’algoritmo non aumenta nè diminuisce
il numero di zone in cui viene segmentata un’immagine: se una regione non
viene rappresentata da un seed fin dall’inizio questa è persa, in quanto i pixel
54
L’algoritmo proposto
Immagine
Preprocessing
Flat seed selection
Seed selection
Small seed selection
Texture seed selection
Region growing
Merging
Segmentazione
Figura 5.1: Lo schema dell’algoritmo di region growing proposto ed
implementato.
che la compongono vengono assegnati alle regioni limitrofe, producendo cosı̀
una sotto–segmentazione.
Al contrario, se i semi sono troppo numerosi, l’algoritmo dividerà zone
percettivamente uniformi in più regioni, creando un problema si sovra–
segmentazione.
Anche la collocazione spaziale e la dimensione dei semi influenzano molto le
buone prestazioni dell’algoritmo.
In particolare, un numero scarso di semi dall’area ridotta porta a una perdita
di efficienza dell’algoritmo, in quanto il maggior numero di pixel da assegnare
rende più lunga la fase di growing.
Per la selezione dei semi di partenza [18] propone i seguenti criteri:
- Soglia sulla mappa del gradiente di un’immagine:
specificando una soglia sulla mappa di gradiente dell’immagine, si
prendono come regioni iniziali i pixel connessi che stanno al di sotto
di questa soglia. Le regioni ottenute sono prive di forti discontinuità
nell’illuminazione o, in generale, nel colore e quindi possono essere
considerate uniformi. Questo criterio è affidabile se le regioni trovate
sono piuttosto grandi, altrimenti potrebbero essere state generate da
minimi locali dovuti al rumore. Usando questo criterio quindi regioni
5.1 Scelta iniziale dei semi
55
piccole (come caratteri di un testo, particolari di un vestito) potrebbero
esser trascurate e quindi produrre una sotto–segmentazione.
- Negativo della mappa degli edge:
come già detto in precedenza (capitolo 4) gli edge detectors da soli non
bastano per fornire una segmentazione dell’immagine. Questo perchè
spesso tendono a tralasciare bordi importanti, a generare bordi non
chiusi e quindi a creare poche grandi componenti connesse. Tuttavia,
possiamo utilizzare la mappa degli edge per cercare piccole regioni
che hanno un perimetro chiuso. Gli esperimenti condotti provano che
questo metodo è efficace nel trovare regioni piccole molto contrastate
ai bordi.
Questi criteri si prestano bene a generare i semi per un algoritmo di region
growing su immagini a colori, però presentano entrambi degli svantaggi:
il primo criterio non cattura le regioni piccole, il secondo criterio fallisce
nell’estarazione di regioni grandi e poco contrastate ai bordi; entrambi non
sono adatti a trovare regioni caratterizzate da una tessitura.
Durante il lavoro di studio di questa tesi è stato sviluppato e realizzato
il seguente criterio per l’estrazione di semi che si comporta bene sia nel caso
di regioni caratterizzate da una tessitura che di regioni uniformi:
- L’immagine viene suddivisa in quadratini piuttosto piccoli (6 × 6, 8 × 8
o 10 × 10) pixel a seconda della dimensione dell’immagine) e su tali
quadratini viene calcolata la signature utilizzando l’algoritmo descritto
in [23] e riassunto in 2.4.1.
- I quadratini vengono ulteriormente suddivisi in 4 zone, e per ognuna di
esse viene calcolata la signature. Quindi, usando la EMD, vengono
calcolate le distanze tra le signature di due zone adiacenti, come
illustrato in Figura 5.2, e tra la zona e l’intera piastrella.
- Se la distanza massima è inferiore a una soglia T , allora la signature
all’interno del quadratino è considerata uniforme, e quindi o la regione
ha colore omogeneo, o è costituita da un pattern regolare formato dai
colori presenti nella signature (figura 5.2). Tali regioni costituiscono i
semi.
56
L’algoritmo proposto
Figura 5.2: Il metodo adottato per estrarre regioni dalla signature uniforme
(regioni con texture)
E’ interessante notare come questo metodo sia capace di rilevare regioni
uniformi anche in presenza di rumore, mentre il primo metodo richiede che
il rumore sia preventivamente ridotto, per esempio tramite un’operazione di
smoothing.
Sebbene questo terzo criterio sembri offrire risultati migliori rispetto agli altri
due, presenta anch’esso lo svantaggio di non rilevare regioni relativamente
piccole, con altezza o larghezza inferiori alla dimensione del quadratino.
Ciò porta a considerare che un singolo metodo per la selezione dei semi
non è sufficiente: se esistesse un metodo cosı̀ potremmo probabilmente usarlo
5.1 Scelta iniziale dei semi
57
direttamente per segmentare l’immagine.
La soluzione proposta in questa tesi è quella di adottare una procedura di
selezione dei seed che combini i semi provenienti da sorgenti diverse.
La decisione di quale semi selezionare è presa sulla base di un valore di fitness,
calcolato su ogni regione a partire dall’area della stessa, e sul vincolo che due
regioni differenti non devono sovrapporsi. In Figura 5.1 è formalizzato il
metodo per la selezione dei semi ottenuti con criteri diversi.
Cosı̀ facendo non solo si ha il vantaggio di avere seed scelti con criteri
differenti che comprendano regioni dalle caratteristiche differenti, sia regioni
piccole e uniformi che grandi e caratterizzate da una tessitura, ma si
lascia spazio anche ad estensioni future che utilizzano tecniche differenti
per la selzione dei seed. Per esempio, un’estensione dell’algoritmo potrebbe
selezionare seed le regioni con hue uniforme, al fine di diminuire il numero di
artefatti dovuti alla presenza di ombreggiature, ombre e lucentezza (si veda
a proposito il paragrafo 2.2.6).
SeedPriorityQueue region queue;
SeedRegionSet region set;
for each SeedSelector s
s.CalculateRegions();
region queue.push(s.Regions);
end for
while ( not region queue.empty() )
region = region queue.top();
if ( region set ∩ region = ®)
region set.add(region);
end if
end while
Figura 5.3: Metodo per la selezione dei semi provenienti da criteri diversi.
58
5.2
L’algoritmo proposto
Strategia di growing
Nella parte introduttiva del capitolo era stata introdotto il concetto di
strategia di growing ed erano state presentate due diverse startegie e le loro
carenze; in particolare, la dipendenza dall’ordine in cui vengono considerate
le regioni e lo scarso controllo sulla direzione della crescita delle regioni.
Queste debolezze portano all’assegnamento di pixel al regioni errate. Questo
problema è stato risolto introducendo una terza strategia di selezione dei
pixel tra i candidati.
Questa strategia, proposto in [18], seleziona per l’accrescimento e inserisce
nella relativa regione esattamente un pixel per iterazione, scelto tra tutti
i candidati. Rispetto alle altre strategie, viene introdotto un ordinamento
globale sull’insieme dei candidati, basato sulla metrica di distanza adottata:
i pixel sono ordinati sulla base della loro distanza della regione con cui
confinano.
Il pixel scelto dalla strategia è quello più vicino alla relativa regione, e quindi
il più promettente tra i candidati: questo assicura che l’espansione proceda
nella direzione e sulla regione migliori per quell’iterazione.
Questo strategia può esser implementata in maniera efficiente usando una
coda di priorità globale: i pixel sono ordinati all’interno della coda a seconda
della loro priorità, che corrisponde alla distanza dalla regione per cui sono
candidati. La coda viene inizializzata all’inizio dell’algoritmo inserendovi i
pixel sul bordo esterno dei semi. Durante l’esecuzione dell’algoritmo, quando
un pixel viene selezionato dalla strategia per essere assegnato, viene tolto
dalla coda e i suoi vicini (4- oppure 8-connessi) vengono inseriti alla posizione
corretta, data dalla loro distanza dalla regione. Questo garantisce che ad ogni
istante nella coda a priorità vi siano tutti i pixel del bordo esterno di tutte
le regioni, ordinati secondo la metrica data dal criterio di growing adottato.
Il vantaggio maggiore di questo approccio, descritto dallo pseudo-codice
in figura 5.2, è quello di combinare in modo elegante informazioni locali (la
distanza del pixel dalla regione) con informazioni globali (l’ordine dei pixel).
Inoltre l’accorgimento di mantenere i pixel all’interno della coda tra un’iterazione e la successiva, aggiungendo e togliendo solo i pixel interessati
dall’assegnamento, porta notevoli vantaggi in termini di efficenza: ad
ogni iterazione, sono necessarie solo una lettura dalla testa della coda,
un’estrazione del minimo e 4 (oppure 8) inserzioni. Per una coda di
5.2 Strategia di growing
59
priorità realizzata tramite heap, le operazioni di estrazione dell’elemento
con priorità minima, di cancellazione dell’elemento con priorità minima
e di inserimento di un elemento possono esser realizzate in modo molto
efficente, con complessità pari a O(1), O(log n) e O(log n) rispettivamente.
Tuttavia, questo accorgimento porta anche uno svantaggio che potrebbe
dare origine ad errori nell’assegnamento dei pixel: la priorità del pixel
(e quindi la sua posizione all’interno della coda) è quella calcolata al
momento del suo inserimento nella coda. Tra il momento dell’inserimento
e quello dell’estrazione possono passare diverse iterazioni; cambiamenti nelle
caratteristiche delle regioni dovute all’accrescimento delle stesse potrebbero
aver modificato la distanza del pixel dalla regione. In realtà, da un punto
di vista pratico, la differenza tra la distanza al momento dell’inserimento e
quella al momento dell’estrazione è molto ridotta, trascurabile ai fini di una
corretta segmentazione.
PixelPriorityQueue pixel queue;
SeedRegionSet region set;
for each ( Pixel p ∈ region set.boudaries() )
CalculateFitnessValue(p);
pixel queue.push(p);
end for
while ( not pixel queue.empty() )
candidate pixel = pixel queue.top();
region set.assign(candidate pixel);
for each ( pixel p ∈ Neighborhood(candidate pixel) )
CalculateFitnessValue(p);
pixel queue.push(p);
end for
end while
Figura 5.4: Algoritmo per il growing basato sulla strategia proposta
60
5.3
L’algoritmo proposto
Metriche di distanza
Le strategie di growing presentate in questo capitolo si appoggiano su delle
metriche di distanza per stabilire quali tra i pixel candidati vadano fusi con
le regioni confinanti e in che ordine debbano esser considerati. Le metriche
di distanza forniscono una misura della distanza tra il pixel canditato e la
regione, cioè danno un’indicazione di quanto il pixel candidato sia adatto a
far parte di quella regione.
Nei capitoli precedenti sono state introdotte misure di similarità tra regioni
basate sul colore (come la EMD, vedi capitolo 2.4.2) e sulla tessitura
(vedi capitolo 3.1.3). Queste misure di similarità estraggono un vettore di
caratteristiche dalle regioni interessate e calcolano la distanza tra i due vettori
usando una metrica definita su di essi. Possiamo utilizzare queste metriche
anche per misurare la distanza tra un pixel e una regione, basta avere un
metodo per estrarre il vettore di caratteristiche da un singolo pixel. Il metodo
impiegato in questo lavoro è semplice: invece di considerare il singolo pixel,
si considera una regione costituita da un piccolo intorno del pixel in esame
(figura 5.5(a)). Su questa regione, i vettori delle caratteristiche (per esempio,
la signature di colore) possono esser calcolati con facilità usando i metodi già
discussi (vedi capitoli 2.4.1 e 3.1.3).
Un discorso a parte lo meritano le metriche basate su misure di
discontinuità, come il contrasto o il gradiente. In questo lavoro, per esempio,
è stata implementata una metrica di distanza basata sul gradiente: in
questo caso, come già accennato in precedenza, si misura la differenza tra
la caratteristica calcolata per il pixel in esame e per il pixel della regione
confinante con esso (figura 5.5(b)).
Solitamente per l’algoritmo di growing viene scelta una tra queste
metriche; tuttavia, analogamente a quanto osservato per la strategia di scelta
dei semi, una sola metrica non basta a cogliere tutte le differenze da un punto
di vista percettivo. Come rilevato nel capitolo 1, sia il colore che la tessitura
sono fondamentali per il sistema visivo umano, quindi si è deciso di usare più
misure tramite una combinazione lineare.
dEM D (p, R): distanza EMD tra signature di colore calcolate sulla regione R
e l’intorno del pixel p(vedi figura 5.5(a) e capitolo 2.4.2).
dW (p, R): distanza bin-by-bin tra i vettori dei coefficinti wavelet della regione
R e dell’intorno del pixel p (vedi figura 5.5(a) e capitolo 3.1.3).
5.3 Metriche di distanza
61
pixel candidato
pixel candidato
pixel regione
pixel regione
pixel intorno
pixel confinante
(a) usando un intorno
del pixel
(b) usando le caratteristiche del pixel confinante
Figura 5.5: Calcolo della distanza tra pixel e regione
dgrad (p, R): distanza tra il valore del gradiente calcolato con l’operatore
Difference Vector Gradient al pixel candidato p e al pixel confinante
della regione R (vedi figura 5.5(b) e appendice A).
Per una misura di distanza complessiva:
d(p, R) = dEM D (p, R) + dW (p, R) + dgrad (p, R)
I risultati ottenuti, però, non sono stati quelli attesi: mentre le misure
fornite dalle metriche basate sulla signature di colore e dalle metriche
basate sulla differenza di gradiente si sono rivelate confrontabili, le misure
ricavate dalle metriche basate sulla distanza tra i coefficienti wavelet non lo
sono. I risultati di tutte le misure sono stati moltiplicati per un’oppurtuna
costante in modo da rientrare tutti nell’intervallo (0, 1), ma mentre i
risultati per le misure dEM D e dgrad sono distribuite in modo quasi uniforme
lungo l’intervallo, con una concentrazione maggiore nel primo 10-15%, i
risultati della misura dW (p, R) sono distribuiti in modo molto diverso, con
concentrazioni più elevate attorno ad alcuni valori e per di più in modo molto
dipendente dall’immagine.
62
L’algoritmo proposto
Si è quindi scelto di ricorrere a una misura di distanza diversa, che
comprendesse comunque l’informazione proveniente da tutte e tre le fonti
(signature di colore, coefficienti Wavelet e valore del gradiente):
d(p, R) = (dEM D (p, R) + dgrad (p, R)) × dtexture (p, R)
dove dtexture è pari a:
(
dtexture (p, R) =
Klow se classe(p) = classe(R)
Khigh altrimenti
La classe di p e R è calcolata a partire dalla mappa delle texture introdotta
nel capitolo 3, e le due costanti Klow e Khigh sono calcolate in maniera
empirica (e sono pari rispettivamente a 0.8 e 1.5 per l’algoritmo proposto).
5.4
Implementazione
Tutti i concetti analizzati e studiati nei paregrafi precedenti (spazi di colore,
metriche, trasformate Wavelet, criteri di growing, misure di omogeneità e
discontinuità) sono stati implementati nell’algoritmo proposto come parte di
questo lavoro di tesi.
Uno dei requisiti che sono stati ritenuti necessari per un’utilizzo pratico
dell’algoritmo e per rendere agevole la sperimentazione e l’utilizzo per lavori
futuri è che questo fosse parametrico e modulare in ogni suo aspetto.
Un altro requisito essenziale è l’efficienza: le immagini sono strutture
dati di grandi dimensioni, l’eleborazione è molto dispendiosa in termini
computazionali, quindi è necessario evitare ogni possibile overhead.
Tali requisiti sono stati soddisfatti in massima parte utilizzando la
programmazione generica e i template.
In particolare per che incapsulano le immagini sono tutte parametriche
sullo spazio di colore e ogni funzione che manipola immagini è a sua volta
parametrica sul tipo di immagine.
Inoltre le funzioni che necessitano di una metrica per compiere la loro
elaborazioni sono parametrici sul tipo di metrica. Le metriche sono
implementate come classi e sono a loro volta indipendenti dallo spazio di
colore utilizzato (vedi diagramma UML in figura 5.6).
5.4 Implementazione
63
color_t
dist_t
VectorAngle
color_t
dist_t
L2_Norm
Combined
color_t
dist_t
CombLuma
color_t
dist_t
CombSaturation
Figura 5.6: Il digramma delle classi UML relativo alle classi che
implementano le metriche
Tutto questo consente di avere lo stesso algoritmo e la stessa implementazione operanti su una qualsiasi combinazione di tipo di immagine, spazio
di colore e metrica e rende possibile aggiungere nuove metriche e nuovi spazi
di colore con sforzo minimo.
Dovrebbe esser chiaro come questa scelta porti notevoli vantaggi dal punto
di vista della modularità e della estensibilità.
Per quanto rigurada l’efficienza, l’inlinig delle funzioni e il polimorfismo
statico permesso dei template rendono il codice molto efficiente. Per ulteriori
dettagli si veda l’Appendice B.
Come supporto all’illustrazione dell’implementazione dell’algoritmo ho
incluso i digrammi UML relativi alle classi realizzate per l’algoritmo.
In particolare, sono presenti il digramma delle classi relativo alla parte
centrale dell’algoritmo (figura 5.7), il diagramma UML delle classi usate per
implementare le metriche di distanza tra colori (figura 5.6) e i diagrammi di
sequenza relativi alle fasi di selezione delle regioni iniziali (figura 5.8) e di
growing.
64
L’algoritmo proposto
image_t
SignatureBase<image_t>
<<interface>>
SignatureBase
clone()
merge()
distance()
compute_signatu...
image_t
metric_t
ColorSignature
image_t
GradSignature
image_t
WaveletSignature
std::vector<Sign
atureBase*>
T
ImageRegion
image_t
ColorSiganture<EM
DColorDistance>
std::vector<Reg
ionFeatures>
RegionFeatures
ImageRegio
n<uchar>
image_t
color_t
cmp
EdgeSmallSeedSelector
image_t
std::priority_queue<
CandidatePixel>
EMDColorDistance
image_t
CandidatePixel
FlatTexSeedSelector
image_t
FlatSeedSelector
image_t
RegionGrowing
std::priority_queue<
CandidateSeed>
CandidateSeed
Figura 5.7: Il digramma delle classi UML; per questo digramma, piuttosto
complesso, è stata adottata l’estensione basata sul colore proposta per UML
2.0. L’utilizzo del colore aggiunge una dimensione al digramma, rendendone
più facile la comprensione. I colori adottati sono quelli proposti: giallo per
le classi centrali, quelle che rivestono un ruolo centrale nel digramma; blu
per le classi che rappresentano dati; arancione per i punti di estensibilità;
verde per le classi che nel digramma rivestono un ruolo secondari; grigio per
le classi provenienti da librerie
Come si vede dal diagramma UML in figura 5.7 la classe più imporante
è la classe SignatureBase. Questa classe, che esporta le funzioni merge,
clone, distance e compute signature è l’interfacca usata dall’algoritmo
per accedere alle informazioni sulle features di un pixel o di una zona a più
livelli:
Durante la fase di selezione dei semi, per calcolare le features della regione coperta da ogni seme, utilizzando il metodo compute signature.
uchar
5.4 Implementazione
65
Durante la fase di growing dell’algoritmo, per per calcolare le features
dei pixel candidati, utilizzando il metodo compute signature, e la loro
distanza (priorità) utilizzando il metodo distance.
Durante la fase finale di merge, per calcolare la distanza tra due regioni
candidate per la fusione, utilizzando il metodo distance e la nuova
segnatura della regione in caso di fusione, utilizzando il metodomerge.
Tutti le classi che incapsulano una feature o caratteristica (come la
classe ColorSignature, che rappresenta una segnatura di colore come
descritta nel capitolo 2.4.2, o la classe WaveletSignaure, che rappresenta
la classe di texture di un pixel o di una regione, utilizzando la mappa
descritta nel capitolo 3) sono derivate da SignatureBase, in modo da fornire
all’algoritmo la medesima interfaccia. Questo permette all’algoritmo di
accedere alle funzioni di queste classi senza doverne conoscere la classe, ma
solo l’interfaccia. Aggiungere all’algoritmo un nuovo criterio di omogeneità o
discontinuità, come pure un nuovo tipo di feature per caratterizzare pixel e
regioni, diventa cosı̀ molto semplice: è sufficiente ereditare una nuova classe
da SignatureBase e implementarne i metodi.
Fornire un nuovo algoritmo per la selezione iniziale dei semi è altrettanto
semplice: le classi per la scelta iniziale dei semi (*SeedSelector) implementano un metodo -select- che crea un insieme di classi ImageRegion,
rappresentanti i seed iniziali, e le inserisce nelle coda a priorità della classe
centrale, la classe RegionGrowing.
E’ interessante notare come questa caratteristica di modularità dell’algoritmo, che permette di avere diversi criteri di scelta iniziale dei semi e di
usare differenti criteri di growing, renda possibile implementare l’algoritmo
JSEG -introdotto nel capitolo 2 e descritto in [33]- in termini dell’algoritmo
stesso.
66
L’algoritmo proposto
:
RegionGrowing
:
FlatTexSeedSelector
:
EdgeSmallSeedSelector
:
EMDColorDistance
NewRegion :
CandidateSeed
:
std::priority_queue<CandidateSeed>
select()
distance()
new
push(NewRegion)
select()
select_seeds( )
NextSeed := top()
Figura 5.8: Il digramma di sequenza UML relativo alle fasi di scelta iniziale
dei semi
Capitolo 6
Risultati sperimentali
“Vita brevis, ars longa, occasio praeceps, experimentum periculosum,
jiudicium difficile”.
(La vita è breve, l’arte durarura, l’occasione fuggevole, lo sperimentare
pericoloso, il giudicare difficile.)
Ippocrate
Esperimenti e test sulla segmentazione sono stati effettuati su vari tipi di
immagini, sia naturali che artificiali. Sebbene il metodo proposto consenta
di impostare numerosi parametri per ottimizzare la segmentazione in base
a tipi di immagini differenti, si è scelto di condurre tutti gli esperimenti
con le stesse soglie e gli stessi parametri. Questa scelta è stata dettata
dal fatto che l’algoritmo studiato è stato concepito come un’algoritmo per
l’utilizzo generico, adatto ad ogni tipo di immagine, come richiesto in molti
campi di ricerca attuale (per esempio il context-based image retrieval, si veda
l’introduzione).
Il problema della valutazione degli algoritmi per la segmentazione delle
immagini è forse ancora più complesso (e sicuramente è maggior causa di
dibattito) del problema della segmentazione stesso.
Non esistono criteri per definire una “buona segmentazione” che siano
indipendenti dall’algoritmo e dal tipo di immagine, sebbene esistano criteri
68
Risultati sperimentali
studiati ad-hoc per alcuni algoritmi (si veda [33]), e tantomeno test degli
algoritmi su immagini naturali: tutti i test attuali si basano su immagini
artificiali che non presentano tessiture.
Un test quantitativo dei risultati va quindi oltre lo scopo di questa tesi.
Di seguito, viene dato un giudizio qualitativo dell’algoritmo analizzando i
risultati della sua applicazione a una serie di immagini di test, confrontandole
con le immagini ottenute con un algoritmo esistente (JSEG, si veda [33]).
Sono forniti anche i dati sulla prestazioni, sempre a confronto con le
prestazioni ottenute da JSEG. Parte delle immagini usate durante i test
sono riportate nelle pagine successive. Di alcune di esse, dove si è ritenuto
che siano significativi, sono riportati anche i risultati di alcuni passeggi
intermedi effettuati dall’algoritmo proposto. In particolare, le immagini
Wavelet map si riferiscono alla mappa delle tessiture introdotta nel capitolo
5, le immagini Edge map visualizzano i semi ricavati mediante il metodo
basato sulla mappa degli edge (sezione 5.1), le immagini prima del merge
e dopo il merge sono le immagini della segmentazione fatta dall’algoritmo.
L’immagine Segmentazione è equivalente all’immagine dopo il merge; le
regioni sono le stesse, ma sono presentate in modo diverso (con una mappa dei
colori principali e tracciando i contorni delle regioni sull’immagine originale,
rispettivamente).
La prima caratteristica che si nota esaminando le immagini di test è la
tendanza dell’algoritmo a produrre una sovra–segmentazione dell’immagine.
Questo si nota specialmente in flower garden e geneva1. Al contrario JSEG,
con i parametri di default, tende a sotto–segmentare le immagini.
Il primo set di immagini è costituito da immagini “standard” per il test di
algoritmi di segmentazione.
Nell’immagine baboon (figura 6.1(e)) si nota come l’algoritmo proposto
divida in più zone il pelo del viso, in zone che hanno una predominza di
colore diversa: grigio, verde, giallo, azzurro. Questo risulta in una sovra–
segmentazione dal punto di vista semantico, tuttavia le zone riconosciute sono
effettivamente differenti da un punto di vista percettivo. Le zone più rilevanti
(occhi, muso, naso) sono tutti riconosciuti come elementi distinti. In questo
caso JSEG (6.1(f)) non riesce a riconoscere alcune di queste caratteristiche:
manca un occhio e parte del naso. Tuttavia, il pelo viene suddiviso in un
numero minore di zone.
69
(a) L’immagine di test baboon
(b) Wavelet map
(c) Prima del merge
(d) Dopo il merge
(e) Segmentazione (algoritmo
proposto)
(f) Segmentazione (JSEG)
Figura 6.1: L’immagine di test baboon
70
Risultati sperimentali
Nell’immagine flower garden (figure 6.3(e), 6.3(e)) si nota invece una
migliore segmentazione di JSEG, sia nella definizione del bordo del prato
(nella parte bassa dell’immagine), sia per quanto riguarda la divisione in
zone: l’algoritmo proposto tende a suddividere le piante di fiori in più zone,
dividendo le zone composte in prevalenza da fiori dalle zone composte in
prevalenza da foglie (parte centrale dell’immagine). In compenso, l’algoritmo
proposto riesce a isolare la cornice della finestra dal muro di mattoni (a
sinistra), dove JSEG li considera come una regione unica.
Nell’immagine parrots (figure 6.4(e), 6.4(e)) la situazione cambia: stavolta
è JSEG a presentare un problema di sovra–segmentazione. L’algoritmo
proposto produce un numero inferiore di regioni, specialmente per quel che
riguarda lo sfondo. In compenso, JSEG presenta una migliore definizione dei
contorni: si noti il becco del pappagallo giallo, o l’ala destra del pappagallo
rosso.
In immagini di test più semplici, come house o hand, figure 6.5 e 6.6, la
segmentazione è quasi perfetta: in hand i tre oggetti principali (mano,
anello, sfondo con tessitura) vengono riconosciuti con localizzazione dei bordi
precisa, in house vengono rilevati parecchi particolari della casa (finestre,
tetto) e il prato è riconosciuto come una regione uniforme e separata. Solo
negli alberi si ripresenta la sovra–segmentazione.
Immagine
baboon
hand
flower garden
house
parrots
Algoritmo proposto
1:29
0:23
2:12
0:14
1:44
JSEG
2:41
0:22
4:21
0:10
4:00
Dimensioni
512 × 512
303 × 243
756 × 504
205 × 192
768 × 512
Figura 6.2: Le prestazioni dell’algoritmo proposto a confronto con quelle di
JSEG
71
(a) L’immagine di test flower
garden
(b) Trasformata Wavelet
(c) Wavelet map
(d) Prima del merge
(e) Dopo il merge
(f) Segmentazione (algoritmo
proposto)
(g) Segmentazione (JSEG)
Figura 6.3: L’immagine di test flower garden
72
Risultati sperimentali
(a) L’immagine di test parrots
(b) Edge regions map
(c) Wavelet map
(d) Prima del merge
(e) Dopo il merge
(f) Segmentazione (algoritmo
proposto)
(g) Segmentazione (JSEG)
Figura 6.4: L’immagine di test parrots
73
(a) L’immagine di test house
(b) Prima del merge
(c) Dopo il merge
(d) Segmentazione
Figura 6.5: L’immagine di test house
(a) L’immagine di test hand
(b) Segmentazione
Figura 6.6: L’immagine di test hand
74
Risultati sperimentali
Oltre a questi test preliminari, i cui risultati sono stati confrontati con
JSEG, si sono condotti ulteriori test su immagini di natura diversa, per
testare le capacità dell’algoritmo con immagini di natura differente. Si prenda
per esempio la figura 6.7: in quest’immagine si nota come siano rilevati tutti
i piccoli particolari, come le finestre, i panni appesi alle finestre, i tendoni
al livello della strada e le barche nell’acqua. Molti di questi particolari sono
estratti usando la mappa delle texture e la mappa degli edge (figure 6.7(c) e
6.7(d)).
Un’ultima immagine su cui vale la pena spendere qualche parola è
l’immagine newspaper. Questa immagine è stata acquisita con uno scanner,
ed è la pagina di un giornale a colori stampato con la tecnica del diethering. Il
problema nel segmentare queste immagini sta nel fatto che le regioni stampate
con questa tecnica, “uniformi” da un punto di vista percettivo, non hanno in
realtà un colore uniforme. Infatti, i punti con cui sono composte le immagini
non solo hanno intensità differente, come accade nella maggior parte delle
tessiture, ma anche tinta diversa. Inoltre, bisogna distinguere queste zone
dalle zone di testo: è importante ai fini dell’elaborazione del documento
nelle fasi successive che i caratteri stampati siano conservati (riconoscendoli
come regioni distinte), ma il diethering sia rimosso (riconoscendo le regioni
stampate con questa tecnica come uniformi). Questo è reso possibile grazie
ai due metodi di selezione dei seed implementati: il metodo delle “piastrelle”
(figura 6.8(b)) consente di individuare le regioni con diethering, mentre il
metodo basato sul negativo della mappa degli edge (figura 6.8(c)) consente
di individuare i caratteri stampati.
75
(a) houses
(b) Trasformata Wavelet
(c) Wavelet map
(d) Edge region map
(e) Prima del merge
(f) Dopo il merge
(g) Segmentazione
Figura 6.7: L’immagine di test houses
76
Risultati sperimentali
(a) newspaper
(b) Texture map
(c) Edge region map
(d) Wavelet map
Figura 6.8: L’immagine di test newspaper
77
(a) Prima del merge
(b) Dopo il merge
(c) Segmentazione
Figura 6.9: L’immagine di test newspaper (continua)
78
Risultati sperimentali
(a) flowers2
(b) Prima del merge
(c) Dopo il merge
(d) Segmentazione
Figura 6.10: L’immagine di test flowers2
79
(a) house2
(b) Prima del merge
(c) Segmentazione
Figura 6.11: L’immagine di test house2
80
Risultati sperimentali
(a) geneva1
(b) Prima del merge
(c) Dopo il merge
(d) Segmentazione
Figura 6.12: L’immagine di test geneva1
Capitolo 7
Conclusioni
7.1
Conclusioni
Dal lavoro di ricerca presentato in questa tesi possono esser tratte varie
conclusioni
7.1.1
Il framework
Nell’implementare l’algoritmo di region growing basato sulle tessiture è stato
elaborato e sviluppato un framework efficiente e riusabile, adatto all’utilizzo
come base di partenza per la sperimentazione e l’implementazione di varianti
dell’algoritmo.
7.1.2
Il colore
Le prove sono state condotte utilizzando RGB come spazio di colore e il
Vector Angle combinato con la distanza euclidea sulla base dell’informazione
di luminosità come metrica.
Alcuni esperimenti condotti sulle prime implementazioni dell’algoritmo
hanno mostrato come questa metrica rappresenti il miglior compromesso:
come previsto nel capitolo 2 il solo utilizzo della distanza euclidea porta a
risultati percettivamente non corretti ed a un alto numero di falsi positivi
dovuti alle ombre.
D’altra parte, l’uso del Vector Angle da solo si rivela problematico in
immagini naturali, dove zone con bassa luminosità o saturazione fanno
82
Conclusioni
emergere l’instabilità numerica di questa metrica per certi valori. Usando una
combinazione delle due metriche con trade-off dato dalla luminosità risolve
completamente il secondo problema e in maniera parziale anche il primo.
Putroppo, cosı̀ facendo l’algoritmo ritorna ad essere piuttosto sensibile alle
ombre, anche se non in modo cosı̀ marcato come con la distanza euclidea.
7.1.3
La tessitura
Combinare in maniera efficace le informazioni sulla tessitura, ricavate grazie
all’analisi wavelet, con le informazioni sul colore, ricavate dalla signature
di una zona, si è rivelato il compito più arduo di questo lavoro di tesi. I
risultati iniziali basati sulla distanza tra gli istogrammi dei coefficienti wavelet
(vedi capitolo 3) sono stati deludenti: le due metriche, quella per le tessiture
e quella per il colore, fornivano risultati distribuiti in maniera diversa nei
rispettivi intervalli, cosa che ne rende impossibile il confronto. Cosı̀ si è
optato per una più semplice, ma efficace, suddivisione delle zone in poche
classi di texture.
7.1.4
Selezione dei candidati
Il sistema di selezione dei candidati tramite coda di priorità possiede la
caratteristica di rendere solo un pixel disponibile per il growing ad ogni
iterazione. Questo rende il processo growing più ordinato e prevedibile,
rendendo la localizzazione degli edge più precisa.
7.1.5
Selezione dei semi
La selezione dei semi usando criteri multipli, come il negativo della mappa
degli edge, permette di avere un numero maggiore di regioni di partenza a
disposizione. Questo, se da un lato permette di evitare il problema della
sottosegmentazione e la perdita di dettagli significativi, dall’altro favorisce
la sovrasegmentazione. L’algoritmo proposto tende infatti a generare un
numero elevato di regioni; spesso questa caratteristica è desiderabile rispetto
alla sottosegmentazione, e può essere mitigata modificando opportunamente
i parametri. Tuttavia il problema resta. Tra le possibili estensioni a questa
tesi, a mio avviso la più importante riguarda lo studio di un algoritmo di
merging più efficiente che permetta di risolvere questo problema.
7.2 Lavori futuri
7.2
7.2.1
83
Lavori futuri
Miglioramenti dell’algoritmo
Vanno ancora condotti esperimenti per impostare in maniera più precisa
i parametri e diminuire l’effetto di sovra-segmentazione che si riscontra in
molte immagini.
Questo effetto, molto probabilmente, è causato anche dall’uso di un algoritmo
di merging non ottimale, nell’ultima fase del procedimento. Lo studio
e l’implementazione di un algoritmo che sfrutti in modo più completo le
informazioni a dispozione (area, signature, classe di tessitura della zona,
nonchè seed selector di provenienza) è necessario.
Le performance dell’algoritmo, sebbene soddisfacenti per gli scopi attuali
e superiori a quelle di JSEG (vedi capitolo 6), possono essere migliorate,
in particolar modo per quanto riguarda il calcolo della EMD, che risulta
pesare per circa il 50% sul tempo totale di computazione (dati del profiler
alla mano).
7.2.2
Utilizzi dell’algoritmo
Visto il gran numero di features e caratteristiche importanti dal punto di vista
percettivo estratte dall’algoritmo, un suo uso in sistemi di image retrieval
sembra indicato.
La segmentazione, la descrizione delle caratteristiche di colore per ogni zona,
la mappa delle classi di tessitura, sono tutte features molto importanti per
stabilire la corrispondenza tra immagini e forniscono una buona base di
partenza per il query by context.
Appendice A
Edge detection
Nel capitolo 5 sono stati introdotti vari criteri per il calcolo delle regioni inziali
(seeds) per l’algoritmo di region growing proposto. Due di questi criteri si
appoggiano sulla mappa del gradiente dell’immagine e sulla mappa degli edge
derivata da quest’ultima. Per il calcolo del gradiente di un’immagine a colori
è stato usato un operatore che sfrutta le metriche introdotte nel capitolo 2.
A.1
Difference Vector
L’edge detector Difference Vector e’ un operatore 3x3 che calcola il gradiente
massimo attraverso il pixel centrale.
1
2
3
8
X
4
7
6
5
Figura A.1: Gli indici dei pixel in un intorno 3x3
GDV = max {D(~vi , ~vi+4 }
i=1...4
dove i rappresenta una tra le prime quattro (tra le otto possibili) posizioni
attorno al pixel centrale (figura A.1), e D rappresenta una metrica di
A.2 Entropy Thresholding
85
distanza tra quelle discusse nei paragrafi precedenti. Cosı̀ facendo si ottiene
una misura del gradiente lungo le quattro direzioni (orizzontale, verticale,
diagonale sinistra e diagonale destra) che passano attraverso il pixel centrale.
A.2
Entropy Thresholding
Tutti gli operatori di edge detection forniscono come risultato mappe del
gradiente che devono essere binarizzate per ottenere una mappa degli edge,
usando una soglia: data l’immagine a scala di grigio del gradiente, bisogna
stabilire un valore di soglia che funga da spartiacque; al di sopra di questo
valore il pixel appartiene a un edge, al di sotto no.
Una soluzione è quella di chiedere all’utente di fornire un valore per la soglia:
questo è possibile quando si ha a che fare con sistemi interattivi, tuttavia
spesso è desiderabile (e in sistemi automatici necessario) fornire una soglia
automatica e adattiva, che cioè sia scelta in modo ottimo da un algoritmo
sulla base della mappa del gradiente e del contenuto dell’immagine.
Come parte del lavoro svolto durante la preparazione di questa tesi, è stato
implementato un metodo basato sulla massimizzazione dell’entropia.
Questa tecnica è usata spesso per il problema della classificazione dei dati in
due classi. Il problema consiste nel dividere un insieme di valori in due parti
facendo in modo che l’errore sia minimo.
Per assicurare ciò, si cerca di dividere i dati in due insiemi in modo che
l’entropia totale (la somma dell’entropia delle due partizioni) sia massima.
Brevemente: poniamo che il gradiente (l’intensità di un edge) sia compreso
nell’intervallo [0, M ] e che nell’immagine ci siamo fi pixels che hanno intensità
uguale a i, con i ∈ [0, M ]. Data una certa soglia T , si può definire la
distribuzione di probabilità per le due classi (pixel di edge (e), pixel non
di edge (n)).
Visto che un pixel non può essere sia di edge che no, le due distribuzioni sono
indipendenti.
Quindi la probabilità per i pixel non di edge data la intensità i può essere
definita come:
fi
Pn (i) = PT
h=0
fh
,
0≤i≤T
(A.1)
86
Edge detection
analogamente la probabilità per i pixel di edge data la intensità i è definita
come:
fi
Pe (i) = PM
, T +1≤i≤M
(A.2)
h=T +1 fh
Ora che abbiamo la probabilità ci è possibile definire l’entropia per le due
classi di pixel:
T
X
Hn (T ) = −
Pn (i) log Pn (i),
0≤i≤T
(A.3)
i=0
He (T ) = −
M
X
Pn (i) log Pn (i),
0≤i≤T
(A.4)
i=T +1
E quindi la soglia ottimale T̄ per la classificazione di un pixel come di edge
o di non edge è quella che soddisfa la seguente funzione:
H(T̄ ) = max {Hn (T ) + He (T )}
T =0...M
(A.5)
Cercare il massimo globale di questa funzione ha complessità O(M 2 ), ma
esiste un algoritmo veloce che richiede tempo lineare. Quest’ultimo algoritmo
è stato implementato come parte di questo lavoro. Per dettagli si veda [10].
Appendice B
Polimorfismo statico vs.
polimorfismo dinamico
I linguaggi di programmazione tradizionali (Pascal, C, ecc) sono basati
sull’idea che le funzioni, e quindi i loro parametri, abbiano un solo tipo.
Questi linguaggi si dicono monomorfi.
Un linguaggio monomorfo costringe il programmatore a riscrivere funzioni
che usano lo stesso algoritmo ma operano su tipi di dati diversi (come sort,
swap, max...) e strutture dati (come liste, alberi, tabelle) per ogni tipo di
dato utilizzato. Si ha invece il polimorfismo quando il linguaggio adoperato
consente di scrivere funzioni che possono operare su un numero infinito di
tipi, purché questi rispettino alcune proprietà.
Si noti che in questa definizione rientrano sia il polimorfismo per inclusione
(quello classico nella OOP) che il polimorfimo parametrico (quello della
programmazione generica).
Il C++ permette di programmare usando entrambi i paradigmi. Il primo
viene implementato tramite le funzioni virtuali, e viene anche chiamato
polimorfismo dinamico, il secondo viene implementato tramite i template,
e viene detto anche polimorfismo statico.
Ci sono molti pro e contro sull’utilizzo entrambi i paradigmi; di solito i puristi
dell’OOP considerano migliore il primo approccio [21], ma sulla scia dell’STL
(la libreria standard del C++) sono nate molte librerie che sfruttano la
programmazione generica. In questo lavoro è stata usata la programmazione
generica (e quindi il polimorfismo statico) per svariate ragioni, tra cui
conviene sottolinearne una: l’efficienza.
Il principale svantaggio delle funzioni virtuali è il loro costo: la perdita di
88
Polimorfismo statico vs. polimorfismo dinamico
efficienza dovuta alla chiamata di una funzione virtuale (contro la chiamata
a una funzione normale o parametrica) è del 20-30%.
Questo overhead è dovuto a due cause: la chiamata tramite v-table e
l’impossibilità di fare l’inlining delle funzioni virtuali.
Quando nel codice si presenta una chiamata a funzione virtuale, il compilatore non sa (e non può sapere, visto che per fortuna ai compilatori C++,
di per sè già pittosto complessi, non viene richiesto di fare un’analisi statica
del flusso del codice) che funzione sarà chiamata a run-time, perché non sa
a quale classe appartiene l’oggetto su cui è invocata la funzione:
class A
{
public:
virtual void f() = 0;
};
class B : public A
{
public:
void f() { ... }
};
class C : public A
{
public:
void f() { ... }
};
int main()
{
A* a;
int i;
cin >> i;
if (i == 0)
a = new C();
//(1)
89
else
a = new B();
//(2)
a->f();
//(3)
return 0;
}
In (3) verrà chiamata la f() di C o di B? Il binding è sconosciuto a compiletime, e cosı̀ il compilatore memorizza all’interno di ogni oggetto creato (1,
2) un puntatore alla funzione corretta (C::f() in (1) e B::f() in (2)) per ogni
funzione virtuale presente nella classe. Questa tabella di puntatori a funzione
viene detta v-table.
Purtroppo, questo significa che invece di una semplice istruzione assembler
call il compilatore deve generare il codice per recuperare il puntatore e poi
fare la chiamata, aggiungendo due accessi alla memoria.
Inoltre la mancanza di conoscenza a compile time della funzione che verrà
invocata rende impossibile farne l’inlining.
Usando i template, invece, il compilatore genera del codice eseguibile diverso
per ogni tipo di dato su cui viene invocata la funzione. Questo permette di
inserire direttamente nel codice compilato l’indirizzo della funzione, oppure
il codice stesso nel caso si voglia l’inlining, quando questa viene invocata.
Appendice C
L’algoritmo del trasporto
L’algoritmo del trasporto minimizza il costo del trasporto di merci da m punti
di origine a n punti di destinazione lungo m ∗ n percorsi diretti dall’origine
alla destinazione.
Ognuno degli m punti di origine (fornitori) ha a disposizione merci in quantità
a1 , ..., am e ognuno degli n punti di destinazione (consumatori) ha domanda
pari a b1 , ..., bn .
Inoltre ognuno degli m ∗ n percorsi ha associato un costo cij , i = 1..m, j =
1..n.
Le tre strutture dati di input sono quindi:
1. Vettore delle forniture a
2. Vettore delle domande b
3. Matrice dei costi di consegna c
Nel caso di nostro interesse, la somma delle merci richieste dai consumatori
P
è uguale alla somma delle merci rese disponibili dai fornitori ( m
i=1 ai =
Pn
j=1 bj ), e il problema è quindi detto bilanciato.
Per procedere con l’algoritmo, abbiamo bisogno di una matrice di appoggio
i ∗ j, che denotiamo con x, che conterrà via via la quantità di merce che il
fornitore i-esimo deve consegnare al destinatario j-esimo.
Questo è un problema di ottimizzazione, e l’algoritmo è basato sulla
tecnica della ricerca locale. E’ quindi necessario cercare una soluzione iniziale
percorribile, che verrà poi ottimizzata dalla seconda fase dell’algoritmo.
91
La scelta di una buona soluzione iniziale è desiderabile, in quanto consente
di diminuire il numero di passi necessari per trovare l’ottimo nella seconda
fase dell’algoritmo.
Per questo lavoro si è scelto di implementare una semplice tecnica greedy.
Prima di iniziare a descrivere l’algoritmo, è necessario intrudurre due
termini: si dicono celle di base le celle della matrice della soluzione parziale
x che hanno un flusso positivo -che hanno cioè della merce allocata lungo quel
percorso-, mentre si dicono celle non di base quello il cui flusso è attualmente
pari a zero.
L’algoritmo procede come segue:
La prima fase consiste nel costruire una soluzione iniziale percorribile
usando una tecnica greedy:
1. se la porzione ancora valida dell’array consiste di una singola riga
o di una singola colonna
• si seleziona ogni cella rimanente in essa come una cella di base;
• si termina;
2. altrimenti
• si trova la variabile con il costo di consegna più basso, poniamo
che sia cij ;
• si marca la cella cij come cella di base;
3. per ogni cella di base cij scelta al passo precedente
• si assegna a cij il flusso massimo possibile, min(ai , bj );
• si cancellano la riga i-esima (se min(ai , bj ) = ai ) o la colonna
j-esima (se min(ai , bj ) = bj ): questa non sarà più considerata
nella scelta della variabile al passo 2;
• si riducono la domanda bj e l’offerta ai di min(ai , bj ); si
noti che una delle due variabili (quella sulla riga/colonna
cancellata) verrà posta a zero;
La seconda fase consiste nel determinare una variabile entrante tra le celle
non di base. Se tutte le celle non di base soddisfano la condizione di
ottimalità, ci si ferma; altrimenti si va alla terza fase:
92
L’algoritmo del trasporto
14
13
12
11
21
17
23
16
22
15
19
18
20
23
24
1000
1500
2000
500
1500
800
1000
14
13
12
17
23
19
18
700
11
21
16
22
15
20
23
24
1000
X
1500
2000
500
1500
14
800
13
0
12
700
11
21
15
1000
X
17
23
16
22
19
18
20
23
700
800
24
2000
500
1500
800
0
X
Figura C.1: I primi passi della prima fase
1. associamo due variabili ui e vj , dette moltiplicatori, alla riga iesima e alla colonna j-esima della matrice della soluzione parziale
x;
2. si calcolano ui e vj ; per ogni cella di base xij deve valere la relazione
ui + vj = cij , quindi:
• si pone ui = 0;
• si determinano di conseguenza i restanti ui e vj risolvendo un
sistema lineare in m + n − 1 variabili;
93
X
X
X
X
X
X
X
X
X
X
X
X
Figura C.2: Due esempi di ciclo
3. si calcolano i nuovi costi c̄ij = ui + vj − cij ;
4. si seleziona come variabile entrante la cella non di base xij con c̄ij
massimo;
La terza fase consiste nel determinare una variabile uscente tra le celle
di base attualmente nella soluzione, e di trovare una nuova soluzione.
Quindi si torna alla seconda fase.
Prima di procedere in dettaglio con la descrizione è necessrio dare una
definizione:
Una sequenza ordinata di celle distinte è detta un ciclo se:
- Ogni coppia di celle consecutive giace nella stessa riga o nella
stessa colonna.
- Non ci sono tre celle consecutive nella stessa riga o colonna.
- L’ultima cella della sequanza ha una riga o una colonna in comune
con la prima cella della sequenza (figura C.2).
94
L’algoritmo del trasporto
14
500
13
12
11
21
16
22
15
500
17
23
1000
19
500
18
20
300
14
500
13
24
700
12
11
21
16
22
15
500
17
23
1000
19
500
18
20
X
300
entrante
uscente
14
-300
13
23
1000
24
700
12
11
21
16
22
15
20
23
24
+300
500
500
17
23
-300
+300
1000
19
500
18
+300
-300
X
300
14
200
13
1000
700
12
11
21
16
22
15
800
17
23
700
19
300
23
1000
800
18
20
23
1000
24
700
Figura C.3: Uno scambio variabile uscente-entrante
1. si costruisce un ciclo costituito dalla variabile entrante scelta nella
seconda fase e da sole celle di base (Nota: si può dimostrare che
per ogni cella non di base -come la variabile d’entrata- si può
costruire uno e un solo ciclo);
2. si sceglie la variabile uscente come la cella di base appartenete al
95
ciclo con valore minimo;
3. si pone la variabile uscente a zero e si pone la variabile entrante
uguale al valore della variabile uscente
4. si marca la variabile uscente come cella non di base;
5. si marca la variabile entrante come cella di base;
6. si aggiustano la altre celle del loop aumentando o diminuendo il
flusso in modo da mantenere il bilanciamento;
7. si torna alla seconda fase (figura C.3);
Per un’approfondimento sull’algoritmo si vedano [27], [20].
Appendice D
Utilizzo di istruzioni SIMD
La metrica Vector Angle e stata usata intensivamente assieme allo spazio
RGB, viste le sue proprieta e i buoni risultati conseguiti.
Uno degli svantaggi derivanti dall’uso di questa metrica sono le sue performance, indubbiamente inferiori rispetto a quelle della più semplice distanza
euclidea.
Il metodo, infatti, richiede una buona mole di calcoli, tra cui tre operazioni
di estrazione di radice quadrata. Visto che alcune delle operazioni (somma,
elevamento al quadrato...) vanno effettuate su tutte e tre le componenti dei
due colori di cui si sta misuerando la distanza, si è pensato di aumentare le
performance usando istruzioni SIMD (Single Instruction Multiple Data).
Questo tipo di istruzioni, quando sono supportate dal processore, consentono
di effettuare la stessa operazione su un blocco di dati al costo di una singola
istruzione, aumentando notevolmente il parallelismo.
Sulle architetture Intel a 32 bit (IA-32) sono presenti, a partire dal processore
Pentium III, delle istruzioni SIMD dette SSE (Streaming Simd Extension)
[17]. Queste istruzioni permettono di effettuare alcune operazioni algebriche
(somma, sottrazione, moltiplicazione, divisione, estrazione di radice e altre)
su blocchi di 4 float (numeri a virgola mobile da 32 bit) [16].
Grazie all’uso di queste istruzioni assembler è stato possibile aumentare le
performance della metrica Vector Angle del 50% circa.
Codice C:
inline static dist_t distance(const color_t& a, const color_t& b)
97
{
double v1 = sqrt(sqr(a.C1()) + sqr(a.C2()) + sqr(a.C3()));
double v2 = sqrt(sqr(b.C1()) + sqr(b.C2()) + sqr(b.C3()));
double v3 = (a.C1() * b.C1() + a.C2() * b.C2() + a.C3() * b.C3());
.
.
.
}
Codice assembler SSE:
inline static dist_t distance(const color_t& a, const color_t& b)
{
//variabili
__declspec(align(16)) float acf1[4];
__declspec(align(16)) float acf2[4];
acf1[0]
acf1[1]
acf1[2]
acf1[3]
=
=
=
=
(float)a.C1();
(float)a.C2();
(float)a.C3();
(float)0.0f;
acf2[0] = (float)b.C1();
acf2[1] = (float)b.C2();
acf2[2] = (float)b.C3();
acf2[3] = (float)0.0f;
__asm
{
movaps xmm0, acf1;
movaps xmm1, acf2;
movaps xmm2, xmm0; xmm2 e xmm0 contengono a
mulps xmm2, xmm0; xmm2 = a * a
movaps xmm3, xmm1; xmm3 e xmm1 contengono b
mulps xmm3, xmm1; xmm3 = b * b
98
Utilizzo di istruzioni SIMD
mulps xmm0, xmm1; xmm0 = a * b
movaps xmm4, xmm2;
shufps xmm4, xmm3, 0x44;
movaps xmm1, xmm2;
shufps xmm1, xmm3, 0x11;
movaps xmm5, xmm2;
shufps xmm5, xmm3, 0xEE;
addps xmm1, xmm4;
addps xmm1, xmm5;
rsqrtps xmm6, xmm1;
rcpps xmm1, xmm6; xmm1[0] = v1, xmm1[2] = v2
movaps acf2, xmm1;
movaps acf1, xmm0;
}
float v3 = acf1[0] + acf1[1] + acf1[2];
float v1 = acf2[0];
float v2 = acf2[2];
.
.
.
}
Bibliografia
[1] L. Balmelli and A. Mojsilović. Wavelet Domain Features fo Texture
Description, Classification and Replicability Analysis.
In IEEE
International Conference on Image Processing (ICIP), volume 4, pages
440–444, 1999.
[2] B.A.Wandell. Foundations of Vision. Sinauer Assocites Inc., 1995.
[3] S. Boker. The representation of color metrics and mappings in perceptual
color space. Paper, Department of Psychology, The University of
Virginia, Charlottesville, Virginia 22903, 1994.
[4] T. Carron and P. Lambert. Color Edge Detector Using Jointly Hue,
Saturation, and Intensity. In International Conference on Image
Processing, volume 3, pages 977–98, 1994.
[5] J. Chen, T. Pappas, A. Mojsilovic, and B. Rogowitz. Adaptive image
segmentation based on color and texture. In International Conference
Image Processing, Rochester, New York, 2002.
[6] H. Cheng, X. Jiang, Y. Sun, and J. Wang. Color Image Segmentation:
Advances and Prospects. Pattern Recognition, 34(12):2259–2281, 2001.
[7] A. Cumani. Edge detection in multispectral images. Computer
Vision, Graphics and Image Processing: Graphical Models and Image
Processing, 53(1):40–51, January 1991.
[8] S. di Zenzo. A Note on the Gradient of a Multi-Image. Computer Vision,
Graphics and Image Processing, 33(1):116–125, January 1986.
[9] S. P. et al. A Review on Image Segmentation Techniques. Pattern
Recognition, 29:1277–1294, 1993.
100
BIBLIOGRAFIA
[10] J. Fan, D. Yau, A. Elmagarmid, and W. Aref. Automatic Image
Segmentation by Integrating Color-Edge Extraction and Seeded Region
Growing. IEEE Trans. On Image Processing, 10(10):1454–1456, 2001.
[11] Foley, V. Dam, Feiner, and Hughes. Computer Graphics, Principles And
Practice, 2nd Edition. Addison Wesley, 1992.
[12] K. Fu and J. Mui. A survey on image segmentation. Pattern Recognition,
13:3–16, 1981.
[13] R. Gonzales and R. E. Woods. Digital Image Processing. AddisonWesley, 1992.
[14] A. Graps. An introduction to Wavelet. IEEE Computational Science
and Engineering, 2(2), 1995.
[15] S. Hojjatoleslami and J. Kittler. Region Growing: A New Approach.
IEEE Trans. on Image Processing, 7(7):1079–1088, July 1998.
[16] Intel Corporation, Mt. Prospect, Illinois.
Optimization: Reference manual, 1999.
Intel Architecture
[17] Intel Corporation, Mt. Prospect, Illinois. IA-32 Intel Architecture
Software Developer’s Manual Volume 2: Instruction set reference, 2002.
[18] U. Kthe. Primary Image Segmentation. In DAGM-Symposium, pages
554–561, Berlin, Deutschland, 1995.
[19] A. Lou.
Texture Images Classification Using Tree-structured
Wavelet Decomposition. Project technical report, Computer Science
Department, University of California, Santa Cruz, California, 1999.
[20] K. Murty. The Balanced Transportation Problem. Lecture slides,
College of Engineering, University of Michigan, Ann Arbor, Michigan,
1999.
[21] C. Pescio. Programmazione ad Oggetti e Programmazione Generica.
IEEE Computational Science and Engineering, VII(62), October 1997.
[22] W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling.
Numerical Recipes in C++. Cambridge University Press, Cambridge
(UK) and New York, 2nd edition, 2002.
BIBLIOGRAFIA
101
[23] Y. Rubner, C. Tomasi, and L. Guibas. The Earth Mover’s Distance
as a Metric for Image Retrieval. Technical Report STAN-CS-TN-98-86,
Computer Science Department, Stanford University, September 1998.
[24] J. Sklansky. Image Segmentation and Feature Extraction. IEEE
Transactions on Systems, Man, and Cybernetics, (8):237–247, 1978.
[25] S.Livens and P. et al. Wavelet-based Texture Analysis. International
Journal Computer Science and Information management, December
1997.
[26] N. Suematsu and Y. I. et al. Region-Based Image Retrieval using
Wavelet Transform. In 15th International Conference on Vision
Interface, volume 1, Calgary, Canada, 2002.
[27] C. Sung. The Transportation Simplex Method. Lecture slides,
University of Illinois at Springfield, Springfield, Illinois, 2000.
[28] A. Tanenbaum. Computer Networks, 3rd Edition.
International, 1997.
Prentice Hall
[29] A. Wah.
A General Multiscale Scheme for Unsupervised Image
Segmantation. University of Cambridge, 2000.
[30] S. Wesolkowski. Color Image Edge Detection and Segmentation: A
Comparison of the Vector Angle and the Euclidean Distance Color
Similarity Measures.
Systems Design Engineering, University of
Waterloo, Canada, 1999.
[31] S. Wesolkowski and E.Jernigan. Color Edge Detection in RGB Using
Jointly Euclidean Distance And Vector Angle. In Vision Interface ’99,
Trois-Rivières, Canada, 1999.
[32] S. Wesolkowski and P. Feiguth. Color Image Segmentation Using a New
Region Growing Method. In 9th Congress of the Int. Colour Association,
Rochester, NY, USA, 2001.
[33] Y. Deng and B. S. Manjunath and H. Shin. Unsupervised Segmentation
of Color-Texture Regions in Images and Video. IEEE Trans. on PAMI,
2001.
102
BIBLIOGRAFIA
[34] X. Zhang and B. Wandell. A Spatial Extension of CIELAB for Digital
Color Image Reproduction. Journal of the Society for Information
Display, 5(1):61–63, 1997.