UNIVERSITA DEGLI STUDI DI TRENTO` - tev-static.fbk.eu · Grazie a loro adesso non sono piu` cos`ı...

UNIVERSITA DEGLI STUDI DI TRENTOFacolta di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea in Informatica

Tesi di Laurea

Algoritmi parametrici per lasegmentazione di immagini digitalibasati sull’analisi congiunta delle

caratteristiche di colore e tessitura.

Relatore:Prof. Francesco De NataleResponsabile esterno: Laureando:Dott. Stefano Messelodi Lorenzo Dematte

Anno accademico 2001–2002

2

Ringraziamenti

Il primo gruppo di persone che desidero ringraziare sono i ricercatoridel gruppo TeV-SSI dell’ Istituto di Ricerca Scientifica e Tecnologica(ITC-IRST). Ringrazio principalmente due persone, Carla Maria Modenae Stefano Messelodi, per avermi introdotto con pazienza i concetti dell’ImageProcessing, per avermi spiegato e fatto capire un sacco di cose e per averfatto veramente un ottimo lavoro per render leggibile e corretta questa tesi.Grazie a loro adesso non sono piu cosı ignorante in questo campo.Voglio anche ringraziare Roberto Brunelli per le piacevoli discussioni sullaComputer Graphics, sul C++ e Java e sul Lego Mindstorm, MicheleZanin, Filippo Bertamini, Claudio Andreatta, Dimitri Giordani, AlessandroGiacomini 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 loropazienza, per avermi sopportato quando sono stato assente e scontroso inquesto periodo.

Infine, il ringraziamento piu grande ai miei genitori, a mio padre Maurizioe 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 senon ha la minima idea di cio di cui si parla.

Indice

1 Introduzione 7

2 Il colore 102.1 Rappresentazione del colore . . . . . . . . . . . . . . . . . . . 10

2.1.1 Il modello Fisico del colore . . . . . . . . . . . . . . . . 102.1.2 Il modello Percettivo del colore . . . . . . . . . . . . . 112.1.3 La teoria tricromatica . . . . . . . . . . . . . . . . . . 132.1.4 Conciliare le tre teorie . . . . . . . . . . . . . . . . . . 13

2.2 Spazi di colore in computer graphics e image processing . . . 172.2.1 RGB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2.2 RGBN (o r′g′b′) . . . . . . . . . . . . . . . . . . . . . . 182.2.3 YUV . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.4 XYZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.5 CIE L*a*b* . . . . . . . . . . . . . . . . . . . . . . . . 202.2.6 HSV (HSI, HSL, HSB) . . . . . . . . . . . . . . . . . . 21

2.3 Misure di similarita e differenza tra colori . . . . . . . . . . . . 232.3.1 Norma L1 e L2 . . . . . . . . . . . . . . . . . . . . . . 242.3.2 Vector Angle . . . . . . . . . . . . . . . . . . . . . . . 262.3.3 Combinazione . . . . . . . . . . . . . . . . . . . . . . . 26

2.4 Misure di similarita tra zone di immagini a colori . . . . . . . 282.4.1 Istogrammi e Signature . . . . . . . . . . . . . . . . . . 282.4.2 La Earth Mover’s Distance . . . . . . . . . . . . . . . . 30

3 La tessitura 323.1 Trasformata Wavelet . . . . . . . . . . . . . . . . . . . . . . . 34

3.1.1 Filtri per la trasformata . . . . . . . . . . . . . . . . . 363.1.2 Tipo di decomposizione . . . . . . . . . . . . . . . . . . 373.1.3 Estrazione caratteristiche e metriche . . . . . . . . . . 38

4 INDICE

4 Tecniche di segmentazione 434.1 Approcci basati su misure di discontinuita . . . . . . . . . . . 464.2 Approcci basati su misure di omogeneita . . . . . . . . . . . . 47

4.2.1 Histogram thresholding . . . . . . . . . . . . . . . . . . 474.2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 474.2.3 Region splitting & merge e Region growing . . . . . . . 48

5 L’algoritmo proposto 505.1 Scelta iniziale dei semi . . . . . . . . . . . . . . . . . . . . . . 535.2 Strategia di growing . . . . . . . . . . . . . . . . . . . . . . . 585.3 Metriche di distanza . . . . . . . . . . . . . . . . . . . . . . . 605.4 Implementazione . . . . . . . . . . . . . . . . . . . . . . . . . 62

6 Risultati sperimentali 67

7 Conclusioni 817.1 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

7.1.1 Il framework . . . . . . . . . . . . . . . . . . . . . . . . 817.1.2 Il colore . . . . . . . . . . . . . . . . . . . . . . . . . . 817.1.3 La tessitura . . . . . . . . . . . . . . . . . . . . . . . . 827.1.4 Selezione dei candidati . . . . . . . . . . . . . . . . . . 827.1.5 Selezione dei semi . . . . . . . . . . . . . . . . . . . . . 82

7.2 Lavori futuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . 837.2.1 Miglioramenti dell’algoritmo . . . . . . . . . . . . . . . 837.2.2 Utilizzi dell’algoritmo . . . . . . . . . . . . . . . . . . . 83

A Edge detection 84A.1 Difference Vector . . . . . . . . . . . . . . . . . . . . . . . . . 84A.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 Una sfera ombreggiata . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Risposta dei tre tipi di coni al variare della lunghezza d’onda . 14

2.3 Test percettivo per il color-matching . . . . . . . . . . . . . . 14

2.4 Funzioni di color matching per i primari RGB . . . . . . . . . 15

2.5 Funzioni di color matching per i primari XYZ . . . . . . . . . 16

2.6 Lo spazio di colore RGB visto lungo la diagonale principaledal bianco (0,0,0) al nero (1,1,1) e dal nero (1,1,1) al bianco(0,0,0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.7 Una fetta dello spazio di colore CIE XYZ . . . . . . . . . . . . 19

2.8 Lo spazio di colore CIE Lab . . . . . . . . . . . . . . . . . . . 21

2.9 Lo spazio di colore HSV . . . . . . . . . . . . . . . . . . . . . 22

2.10 Piani di RGB a luminosita differente . . . . . . . . . . . . . . 25

2.11 La signature dell’immagine Lena e i rispettivi pesi . . . . . . . 30

3.1 La trasformata wavelet discreta (DWT, sopra) e la trasformatawavelet a pacchetti (PKWT, sotto) . . . . . . . . . . . . . . . 36

3.2 L’immagine flower garden . . . . . . . . . . . . . . . . . . . . 37

3.3 La trasformata wavelet a pacchetti (PKWT) dell’immagineflower garden . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.4 La mappa delle classi di texture ottenuta dall’applicazionedell’algoritmo proposto sull’immagine flower garden . . . . . . 40

3.5 Recenti ricerche psicofisiche hanno dimostrato che la percezionedel colore nel sistema visivo umano dipende dalle frequenzespaziali fra i colori. Questo, tuttavia, era gia stato intuito daipittori impressionisti cento anni prima. . . . . . . . . . . . . . 42

5.1 Lo schema dell’algoritmo di region growing proposto edimplementato. . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6 ELENCO DELLE FIGURE

5.2 Il metodo adottato per estrarre regioni dalla signature uni-forme (regioni con texture) . . . . . . . . . . . . . . . . . . . . 56

5.3 Metodo per la selezione dei semi provenienti da criteri diversi. 575.4 Algoritmo per il growing basato sulla strategia proposta . . . . 595.5 Calcolo della distanza tra pixel e regione . . . . . . . . . . . . 615.6 Il digramma delle classi UML relativo alle classi che imple-

mentano le metriche . . . . . . . . . . . . . . . . . . . . . . . 635.7 Il digramma delle classi UML; per questo digramma, piuttosto

complesso, e stata adottata l’estensione basata sul coloreproposta per UML 2.0. L’utilizzo del colore aggiunge unadimensione al digramma, rendendone piu facile la compren-sione. I colori adottati sono quelli proposti: giallo per le classicentrali, quelle che rivestono un ruolo centrale nel digramma;blu per le classi che rappresentano dati; arancione per i puntidi estensibilita; verde per le classi che nel digramma rivestonoun ruolo secondari; grigio per le classi provenienti da librerie . 64

5.8 Il digramma di sequenza UML relativo alle fasi di scelta inizialedei semi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.1 L’immagine di test baboon . . . . . . . . . . . . . . . . . . . . 696.2 Le prestazioni dell’algoritmo proposto a confronto con quelle

di JSEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706.3 L’immagine di test flower garden . . . . . . . . . . . . . . . . 716.4 L’immagine di test parrots . . . . . . . . . . . . . . . . . . . . 726.5 L’immagine di test house . . . . . . . . . . . . . . . . . . . . . 736.6 L’immagine di test hand . . . . . . . . . . . . . . . . . . . . . 736.7 L’immagine di test houses . . . . . . . . . . . . . . . . . . . . 756.8 L’immagine di test newspaper . . . . . . . . . . . . . . . . . . 766.9 L’immagine di test newspaper (continua) . . . . . . . . . . . . 776.10 L’immagine di test flowers2 . . . . . . . . . . . . . . . . . . . 786.11 L’immagine di test house2 . . . . . . . . . . . . . . . . . . . . 796.12 L’immagine di test geneva1 . . . . . . . . . . . . . . . . . . . 80

A.1 Gli indici dei pixel in un intorno 3x3 . . . . . . . . . . . . . . 84

C.1 I primi passi della prima fase . . . . . . . . . . . . . . . . . . . 92C.2 Due esempi di ciclo . . . . . . . . . . . . . . . . . . . . . . . . 93C.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 e un problema chiave nella computervision. La segmentazione e un processo che permette di suddividerel’immagine in regioni significative che corrispondono a oggetti, o partidi oggetti, in essa rappresentati, un primo passo verso l’estrazione diinformazioni semantiche da una scena. In principio (fino ai primi anni ’80) laricerca si e 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 dacaratteristiche di basso livello dell’immagine, a prescindere dal contenutosemantico.Una segmentazione “perfetta” in oggetti significativi non e ottenibile senzauna conoscenza di alto livello dell’immagine. La ricerca di oggetti nella scenaha portato allo sviluppo di tecniche basate su modelli, come gli active contoursnakes o il template matching. Queste tecniche, dette top–down, permettonodi ottenere dei buoni risultati se applicate a problemi specifici.Spesso la conoscenza a priori della scena non e sufficiente, o non e disponibile,e quindi c’e bisogno di un metodo per estrarre delle regioni primitive cheforniscano la base di partenza per i modelli utilizzati dalle tecniche top–down.

8 Introduzione

Nell’estrazione delle regioni primitive, che costituiscono una segmentazionedi primo livello, i metodi bottom–up giocano un ruolo fondamentale. L’ac-curatezza della segmentazione iniziale influenza in maniera pesante le fasisuccessive.Per questi motivi il metodo di segmentazione iniziale deve essere flessibile,cioe deve fornire risultati soddisfacenti quando applicato a tipi di immaginidifferenti, e deve fornire una segmentazione il piu accurata possibile,cercando di evitare la sotto-segmentazione (fusione nella stessa zona di oggettisemanticamente diversi) e di limitare la sovra-segmentazione (divisione inzone diverse di un oggetto unico dal punto di vista semantico).

La segmentazione primaria di un’immagine, non presuppone nessunaconoscenza semantica della scena, e quindi non e possibile garantire chequesti vincoli siano soddisfatti. Tuttavia si puo garantire la suddividivisionedi un’immagine in regioni differenti in modo che ogni regione sia omogenea ouniforme rispetto a un dato criterio e che l’unione di due regioni non lo sia.In [9] e data la seguente definizione formale del problema: Detto P ()un predicato di omogeneita definito su un gruppo di pixel connessi, lasegmentazione e la partizione dell’insieme F in sottoinisiemi connessi -oregioni- (S1, S2, ..., Sn) non vuoti tali che:

n⋃

i=1

Si = F Si ∩ Sj = ® (i 6= j)

Con il predicato P (Si) = true per ogni regione Si e P (Si ∪ Sj) = false con(i 6= j) e Si, Sj regioni confinanti.Facendo cosı si sposta il concetto di segmentazione dalla identificazione deglioggetti semantici ad un requisito di omogeneita sulle regioni (insiemi di pixelconnessi).

Per ottenere una segmentazione primaria il piu vicina possibile a quelladesiderata e fondamentale la scelta, spesso dettata dall’ambito applicativo,del predicato di omogeneita. Infatti la partizione di un’immagine in regioniomogenee 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 dellasegmentazione di immagini e un problema di percezione psico-fisica e quindinon e risolubile in maniera completamente analitica). Il problema dellasegmentazione automatica (non supervisionata) di immagini e mal definito,

9

proprio a causa del fatto che gli oggetti semantici spesso non corrispondonoa zone omogenee rispetto a caratteristiche di basso livello (colore, tessitura,...). Tuttavia, se misuriamo la similarita tra zone in maniera simile a quelladell’occhio umano, cioe usiamo misure di similarita e di omogeneita di regionicorrette da un punto di vista percettivo, possiamo avvicinarci al risultato. E’stato dimostrato che la percezione del colore e della tessitura e fondamentalenella visione umana [2].L’approccio migliore quindi sembra quello di seguire e cercare di imitare nelmodo piu fedele possibile il sistema visivo umano, utilizzando le informazionicongiunte di colore e tessitura per ottenere delle misure di similarita eomogenita corrette da un punto di vista percettivo.

Negli ultimi anni sono state introdotte nuove metriche per la misuradella distanza tra colori [31] e della distanza colorimetrica tra immaginio tra regioni all’interno di un’immagine [23], nuovi approcci a tecniche disegmentazione esistenti [18, 33, 30] e nuovi metodi per l’analisi, la descrizionee la classificazione di tessiture [1, 25, 19].Ai progressi nei singoli campi, non ha fatto riscontro un uguale progressonell’utilizzo combinato di questi strumenti applicati alla segmentazione diimmagini.Questo lavoro di tesi si propone di fare un passo in avanti in questa direzione,introducendo un nuovo algoritmo per la segmentazione, basato sulla tecnicadel region growing e sull’utilizzo congiunto di caratteristiche di colore etessitura. Il capitolo 2 introduce gli aspetti piu importanti legati all’analisidel colore, con un breve accenno alla teoria del colore, la descrizione dai varispazi di colore esistenti, la presentazione delle metriche usate per misurarela distanza colorimetrica tra colori e tra zone di un’immagine. Nel capitolo 3viene dato un ragguaglio sulle varie tecniche di estrazione di caratteristicheda una tessitura, con particolare attenzione ai metodi di analisi nello spaziodelle frequenze usando le Wavelet.Nel capitolo 4 viene fornita un’introduzione al problema della segmentazionecon i vari approcci utilizzati in letteratura. L’algoritmo proposto per lasegmentazione basata su colore e tessitura viene illustrato in dettaglio nelcapitolo 5. Il capitolo 6 e dedicato ai risultati sperimentali, e le conclusionisono presentate nel capitolo 7.

Capitolo 2

Il colore

“Le ombre non sono nere; nessun ombra e nera. La natura conosce solo icolori. Bianco e nero non sono colori”A. Renoir

2.1 Rappresentazione del colore

Il primo aspetto da prendere in esame e quello di come rappresentare i coloriin modo corretto sia da un punto di vista fisico che percettivo.A questo scopo vengono introdotte le tre maggiori teorie sulla rappresen-tazione dei colori e dello spazio in cui s ono inseriti: il modello Fisico delcolore, 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 proprieta della luce e delcolore si chiama colorimetria.La colorimetria specifica il colore usando tre coefficienti: la lunghezza d’ondadominante, la purezza e la luminanza.Come e noto, la luce e energia elettromagnetica nella regione dello spettro cheha lunghezza d’onda compresa tra 400 e 700 nm, che e percepita dall’occhio

2.1 Rappresentazione del colore 11

umano come colore dal viola al rosso.Un colore e quindi rappresentabile tramite una distribuzione spettrale dienergia nella zone del visibile.Volendo campionare uno spettro di energia senza perdita di informazionesi dovrebbe utilizzare un numero praticamente infinito di livelli, tuttaviapossiamo 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 univocamenteun’unica distribuzione: molte distribuzioni di energia differenti produconolo stesso colore, “sembrano” uguali, e sono descritte dalla stessa tripletta.La relazione tra distribuzioni e triplette e dunque di molti-a-uno.

2.1.2 Il modello Percettivo del colore

Una volta introdotto lo spazio di colore fisico, e necessario fare un’osser-vazione importante: il colore non e una proprieta fisica degli oggetti, come illoro peso o il loro volume. Il colore e una rappresentazione percettiva delladistribuzione di energia elettromagnetica emessa o riflessa da un oggetto, unprodotto del sistema visivo umano [3].Lo spazio di colore percettivo e la rappresentazione che la nostra mente daalla percezione del colore, a come i colori sono in relazione l’uno con l’altroe che posizione occupano relativamente agli altri colori.La percezione intuitiva e umana del colore solitamente si poggia su trequantita, chiamate hue, saturazione e luminosita (hue si puo tradurreapprossimativamente con “tinta”, ma per evitare confusioni in questa tesisi fa riferimanto ad essa con il termine originale).Questi tre termini corrispondono grossomodo alle nozioni fisiche di lunghezzad’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 e distante daun grigio della stessa intensita. Per esempio, il rosso e molto saturo, il rosapoco, e in generale i colori pastello sono poco saturi. La luminosita indica(indipendentemente dalla lunghezza d’onda), l’intensita della luce riflessa oemessa da un oggetto; per fare un esempio, un oggetto illuminato in modonon uniforme, come la sfera in figura 2.1, ha hue e saturazione costanti maintensita variabile.

Per poter avere un’utilita 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. Perfare cio possiamo confrontare visivamente un campione di colori “sconosciuti”(cioe non ancora classificati) con un insieme di campioni standard. I campionie i colori sconosciuti vanno osservati sotto una luce standard, visto che ilcolore riflesso da un oggetto dipende sia dal colore della superficie che daquello della luce. Uno spazio di colore costruito usando questa tecnica elo spazio di colore di Munsell, uno spazio 3D che ha come dimensioni lahue, la saturazione e la luminosita. In questo spazio i colori sono ordinatiin modo da avere un’uguale distanza percettiva dai vicini. Uno spazio dicolore che rispetta questa proprieta e detto color-order system. Da questomodello si puo anche notare come il colore aggiunga una notevole quantitadi informazione rispetto alla scala di grigio: la sola luminosita veicola lastessa quantita di informazione di un valore in scala di grigio, e in piu si haa disposizione l’informazione di altre due componenti che rappresentano lacrominanza.Infine e necessario fare un appunto: si e gia detto che la rappresentazionedello spazio di colore di Munsell e soggettiva.Questo significa che, se da un lato questa rappresentazione e percettivamentecorretta, dall’altro il posizionamento e la distinzione tra colori dipendono dalgiudizio di un osservatore, dall’illuminazione, dalla grandezza dei campionida confrontare e dagli altri colori presenti nella scena, come lo sfondo.Potrebbe quindi essere problematico definire in modo univoco e quantitativolo spazio di colore di Munsell.


2.1.3 La teoria tricromatica

La teoria tricromatica si basa sulla constatazione che all’interno della retinanell’occhio umano ci sono tre tipi di recettori sensibili al colore.Questi recettori, detti coni, hanno sensibilita massima a radiazione dilunghezza d’onda diversa, corrispondenti circa a quelle della luce rossa, verdee blu.Questa teoria e molto attraente, in quanto porta a un modello di rappresen-tazione del colore, il modello tricromatico, che e molto semplice e conosciuto.Questo modello e basato sull’idea che la somma in parti diverse di rosso, verdee blu (i tre colori fondamentali, detti primari) possa generare l’intero spaziodei colori.Questa assunzione e quasi vera: con questo modello e possibile generare unanumero notevole di colori differenti (altrimenti i monitor CRT, basati suquesta tecnica, non funzionerebbero), ma non tutti. Alcuni colori nella zonadel viola non possono essere riprodotti con una mistura additiva di rosso,verde e blu.

Tuttavia lo spazio di colore piu noto e usato in computer graphics e lospazio basato su questo modello, lo spazio RGB. Questo spazio e molto noto eusato perche la maggior parte dei sensori fisici alla luce colorata (come i coninell’occhio umano o i sensori CCD nelle telecamere) usano questo modello,cosı come i monitor CRT. Si puo 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 rappresentazionedello spazio di colore in apparente contrasto tra di loro, ognuna con i suoipunti di forza e le sue debolezze: il modello fisico da una descrizione oggettivae quantitativa dei colori; il modello percettivo segue il modo umano dirappresentare il colore come composizione di hue, saturazione e luminositaed e quindi percettivamente corretto; il modello tricromatico si basa sullanatura tristimolare della retina, dei sensori CCD e dei monitor CRT ed equindi 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 e dato dadue 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 luceassorbita) dei tre tipi di coni presenti nella retina umana al variare dellalunghezza d’onda della radiazione elettromagnetica all’interno dello spettrodel 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 quantita di luce rossa, verde e blu necessaria per un


osservatore medio per avere un colore che corrisponda esattamente a un coloreC di luminanza costante, per ogni valore di lunghezza d’onda dominante nellospettro del visibile.In pratica, per ogni colore di riferimento se ne crea un altro miscelando lucerossa, verde e blu nelle quantita necessarie per avere un colore uguale sia daun 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 laquantita di luce necessaria al campione.Questo risultato conferma l’affermazione fatta in precedenza: ci sono colorinon ottenibili come combinazione lineare additiva di rosso, verde e blu.Per risolvere questo problema la commissione CIE (Commission Internationalde l’Eclairage creo nel 1931 un nuovo spazio di colore, lo spazio XYZ. Questoe 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 umanosiano rappresentabili tramite una combinazione lineare di essi: ogni colorevisibile C avente distribuzione spettrale d’energia P (λ), e definito come

C = XX + Y Y + ZZ

dove:

X = k∫

P (λ)xλdλ

Y = k∫

P (λ)yλdλ

16 Il colore

Z = k∫

P (λ)zλdλ

Le funzioni di color-matching xλ, yλ e zλ sono state ricavate da osservazionisperimentali e tabulate a intevalli di 1nm. Inolter il primario Y ha associatauna funzione di matching che corrisponde alla risposta percettiva allaluminosita dell’occhio umano.Ricordo che una funzione di color-matching e una funzione che indica laquantita di ogni primario (X, Y , Z o R, G, B) neccessaria a un osservatoremedio per avere un colore che corrisponda esattamente a un colore C diluminanza costante, per ogni valore di lunghezza d’onda dominante nellospettro del visibile.E’ interessante notare che le tre funzioni color-matching dello spazio CIE sonocombinazioni lineari delle funzioni color-matching per i tre primari di RGB.Ma, mentre le funzioni color-matching dello spazio RGB hanno valori negativi(cioe non tutti i colori sono rappresentabili tramite addizione di rosso, verdee blu), le funzioni color-matching dello spazio XYZ sono positive (cioe tuttii 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, ela distanza tra il colore C2(X2, Y2, Z2) e il colore C2 + ∆C.La distanza misurabile e la stessa, ma la distanza percepita e spesso

2.2 Spazi di colore in computer graphics e image processing 17

differente.Da qui sorge la necessita di avere uno spazio percettivamente uniforme,uno spazio in cui colori che sono ugualmente distanti siano percepiti comeugualmente distanti da un osservatore umano.Nel 1976 e negli anni seguenti sono stati sviluppati dal CIE due spazi chepossiedono questa caratteristica, ottenibili come trasformazione non linearedello spazio XYZ. Questi spazi sono lo spazio CIE L*a*b* e lo spazio CIEL*u*v*.Per dettagli sullo spazio Lab e su come sia stato dimostrato che questo spazioe 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 tristimo-lare del colore, vediamo in dettaglio gli spazi di colore piu significativi e usatiin computer graphics e nell’ image processing.

2.2.1 RGB

Lo spazio di colore RGB e considerato lo spazio nativo della computergraphics (la codifica su file, i monitor CRT, i sensori CCD di telecameree scanner e la parte di rasterizzazione delle schede grafiche solitamente usanoquesto modello), ed e quindi il piu diffuso.RGB impiega un sistema di coordinate cartesiane, e puo essere rappresentatocome un cubo unitario, con bianco e nero sui vertici della diagonale principalee i livelli di grigio sulla diagonale principale (figura 2.6).

RGB e un buon spazio per la computer graphics, ma non per l’imageprocessing and analysis.I suoi difetti maggiori sono l’alta correlazione tra i tre canali (variandol’intensita, tutte e tre le componenti cambiano) e il fatto che non epercettivamente uniforme.Tuttavia, questi difetti possono essere mitigati o resi nulli da una sceltaaccurata della metrica, come viene spiegato in seguito.

18 Il colore

Figura 2.6: Lo spazio di colore RGB visto lungo la diagonale principale dalbianco (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 e che e subito disponibile e nonnecessita di nessuna trasformazione.

2.2.2 RGBN (o r′g′b′)

Questo spazio di colore deriva direttamente da RGB, togliendo uno dei suoidifetti: la forte dipendenza ai cambiamenti di intensita.Questo risultato e ottenuto normalizzando i colori, rendendo cosı uniformile variazioni di intensita attraverso la distribuzione spettrale. Lo spazio dicolore normalizzato e 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’intensita e molto bassa, i colorinormalizzati sono molto rumorosi: piccole variazioni producono oscillazioninotevoli.


2.2.3 YUV

Questo e il secondo spazio, dopo RGB, che puo essere definito “hardware-oriented”. La sua realizzazione e la sua diffusione, infatti, sono legatia dispositivi hardware, in questo caso televisori, telecamere e schede diacquisizione video.Lo spazio YUV e infatti quello preferito per la trasmissione di video, siaanalogico che digitale. Anche gli algoritmi di compressione JPEG e MPEGsi appoggiano su questo spazio di colore per compiere le loro elaborazioni[28].Esistono diverse formule per ricavare YUV da RGB; tutte sono trasformazionilineari, ma differiscono per i coefficienti usati. In questo lavoro sono stateadottate 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 e gia parlato nei paragrafi precedenti. I suoi tre primari sonoX, Y , Z e, come si e visto in precedenza, le funzioni di color-matching diXYZ sono combinazioni lineari di quelle di RGB; i colori di XYZ sono quindiottenibili 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 cor-risponde esattamente alla funzione di risposta alla luminosita dell’occhioumano.La luminosita e quindi ottenibile direttamente da Y, applicando unatrasformazione che tenga conto della risposta non lineare dell’occhio umano:

L∗ = 116( Y

Y0

) 13 − 16

Y

Y0

> 0.008856

L∗ = 116(7.787 · Y

Y0

+ 0.13793)− 16

Y

Y0

≤ 0.008856 (2.1)

E’ importante notare che la trasformazione da RGB a XYZ, e anche da XYZagli altri spazi CIE, dipende dalla scelta del “punto di bianco”, cioe dellecoordinate (X0, Y0, Z0) del colore definito come bianco.CIE definisce diversi punti di bianco, a seconda della temperatura e dellanatura della sorgente luminosa: ci sono punti di bianco per la luce naturale,per lampade fluorescenti, a filamento e anche per sorgenti a emissione comemonitor o televisori.In questo lavoro e stato usato il punto di bianco D65, che corrisponde alpunto di bianco per i monitor CRT con temperatura di colore di 6500k e cheviene 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 cheLab e uno spazio percettivamente uniforme.Questa proprieta di Lab e stata provata anche in maniera sperimentaleusando il metodo delle JND (Just noticeable difference, differenze appenanotabili).A un osservatore vengono proposte una serie di coppie di tavole, e questideve dire quali gli sembrano indistinguibili. I colori indistinguibili vengonoraggruppati in blocchi e la posizione di questi blocchi viene individuataall’interno dello spazio colore.Se questi blocchi sono piccoli, di forma ellissoidale, e con misure simili tra

di loro, lo spazio e percettivamente uniforme [3].I risultati dell’esperimento dimostrano che Lab e percettivamente uniformequando come misura di distanza tra i colori viene usata la distanza euclidea(vedi il prossimo paragrafo), ma solo se le distanze sono piccole, altrimenti


Figura 2.8: Lo spazio di colore CIE Lab

tutto quello che si puo dire del confronto tra due colori e che sono diversi.Lab e ottenibile a partire dallo spazio CIE XYZ tramite delle trasformazioninon lineari.

L∗ = 116( Y

Y0

) 13 − 16

Y

Y0

> 0.008856

L∗ = 116(7.787 · Y

Y0

+ 0.13793)− 16

Y

Y0

≤ 0.008856 (2.2)

a∗ = 500(( X

X0

) 13 −

( Y

Y0

) 13

)

b∗ = 200(( Y

Y0

) 13 −

( Z

Z0

) 13

)

Si noti che L* e la luminosita 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 ladefinizione della luminosita.V , I, L e B infatti indicano rispettivamente Value, Intensity, Luminance eBrightness.Questo spazio e derivato direttamente dallo spazio di colore di Munsell (vediparagrafo “Il modello percettivo”) ed e quindi intuitivo e orientato all’utente,piuttosto che all’hardware [11].

22 Il colore

Lo spazio HSV e rappresentato geometricamente attraverso un sistema dicoordinate cilindriche, e il sottoinsieme dello spazio all’interno del quale ilmodello e definito e una piramide a base esagonale o un cono.Delle tre coordinate cilindriche, la hue e l’angolo, la luminosita (value) el’altezza e la saturazione e il raggio.

Figura 2.9: Lo spazio di colore HSV

H = arctan( √

3(G−B)

(R−G) + (R−B)

)

V = max{R,G, B}

S =V −min{R,G, B}

V

Osservando la figura 2.9 si nota che il rosso si trova a 0 gradi, il verde a120 e cosı via; colori complementari sono scostati di 180 gradi.Lo spazio HSV e diffuso e usato in image processing, e presenta notevolivantaggi pratici.Per segmentare oggetti in base al colore, senza preoccuparci di ombreggiatureo lucentezze, possiamo applicare algoritmi noti per le immagini a scala digrigio 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 e particolarmente utile in presenza di effetti dovuti alla geometriae all’illuminazione. E’ stato dimostrato che se l’illuminazione proviene daluce bianca, la hue e invariante rispetto a ombre, ombraggiature e lucentezze(shadows, shading and highlights).

2.3 Misure di similarita e differenza tra colori 23

Purtroppo questo spazio presenta anche alcuni seri svantaggi che ne pregiu-dicano o ne rendono problematico l’utilizzo.Infatti, per valori di V prossimi o uguali a 0, la hue e la saturazione non sonodefiniti e per valori di S (saturazione) prossimi o uguali a 0, la hue non edefinita.Questa ultima singolarita della Hue vicino all’asse del cilindro/piramide none eliminabile, e una piccola variazione nei valori di input R, G o B puoportare a un grande salto nei valori trasformati.Infine valori della hue vicino alle singolarita sono numericamente instabili,e le singolarita possono portare a discontinuita nella rappresentazione deicolori.

2.3 Misure di similarita e differenza tra colori

Un passo importante che va affrontato quando si passa da immagini a scaladi grigio a quelle a colori e la definizione di una metrica (o misura) per ladistanza. In un’immagine a scala di grigio, la distanza tra due valori si puoesprimere con una semplice differenza, visto che i valori sono scalari.Lo stesso non vale per immagini a colori, i cui valori sono vettori compostidalle tre componenti cromatiche. L’operazione di differenza e sı definitaanche su vettori, ma il risultato non ci da una misura della distanza. Occorrequindi usare metriche differenti.In letteratura sono state adottate diverse misure: la piu usata e la distanzaeuclidea, ma e molto diffuso anche il metodo di effettuare misure basate sulladifferenza di intensita 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 odistanza angolare).

L’obiettivo e sempre quello di copiare la percezione umana, il concettoumano di distanza e similarita tra colori. Quindi la bonta di una metricava misurata in termini di fedelta alla percezione umana del colore. Colorivicini per un osservatore devono dar luogo a misure piccole (distanza ridotta),mentre colori dissimili devono produrre distanze grandi.E’ evidente che la bonta di una metrica dipende dallo spazio di colore su cuie applicata. Se i colori sono disposti nello spazio in modo che colori similisiano vicini, la distanza euclidea e una buona misura di similarita.

24 Il colore

Spazi che godono di questa proprieta si dicono percettivamente uniformi.Lab, per esempio, e uno spazio percettivamente uniforme (si veda il paragrafoprecedente).

2.3.1 Norma L1 e L2

La norma L1 e una misura molto semplice, definita come la somma del valoreassoluto delle differenze tra i componenti.E’ una misura piuttosto diffusa perche e semplice e veloce da calcolare,tuttavia in questo lavoro non sara esaminata approfonditamante perche moltedelle considerazioni che saranno fatte a proposito della norma L2 valgonoanche per la norma L1. Si e quindi preferito concentrarsi sulla distanzaeuclidea, che e piu complessa e dovrebbe garantire risultati leggermentemigliori rispetto alla norma L1.Questa misura e usata di solito per calcolare la distanza in uno spazio a Ndimensioni. E’ definita come:

DE(~v1, ~v2) = ‖~v1 − ~v2‖ (2.3)

dove ‖x‖ e la norma L2. Per uno spazio di colore tricromatico (a trecomponenti) la formula diventa:

DE(~v1, ~v2) =√

(v1,1 − v2,1)2 + (v1,2 − v2,2)2 + (v1,3 − v2,3)2 (2.4)

Il problema della distanza euclidea e che in spazi come RGB (ma anche inHSV e, in misura minore, anche in Lab), e molto sensibile alle variazionidi luminosita. Infatti la distanza euclidea rappresenta nello stesso momentodifferenze in luminosita, saturazione e tinta.

Lo spazio di colore RGB puo essere rappresentato con un cubo unitario,la cui altezza, larghezza e profondita sono le tre componenti RGB. Un singolocolore quindi puo 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 luminositalasciando inalterata la tinta (figura 2.10).

~v2 = α · ~v2

La distanza euclidea tra i due vettori cambia in modo notevole, visto chetutte e tre le componenti sono cambiate.


Figura 2.10: Piani di RGB a luminosita differente

Questa caratteristica puo essere desiderabile o meno, a seconda che sivogliano cogliere le differenze tra due colori con la stessa tinta ma luminositadifferente.In generale questo non e molto desiderabile dato che la percezione umana delcolore e molto piu sensibile alle differenze di tinta che a quelle di luminosita.Inoltre, essendo molto legata alla luminosita, la distanza euclidea su RGB emolto sensibile a ombreggiature, ombre e lucentezze degli oggetti. Questo eun problema particolarmente rilevante quando si progettano algoritmi edgedetection o segmentazione, com’e spiegato in seguito.

In altri spazi di colore la distanza euclidea si comporta in modo differente.Come gia detto in precedenza, in Lab per piccole differenze la distanzaeuclidea e significativa e rispecchia le differenze percettive.Anche in spazi come RGBN, dove l’intensita e stata in qualche modo rimossa,sembra che le differenze tra colori siano caratterizzate piuttosto bene.

26 Il colore

2.3.2 Vector Angle

Questa misura, la distanza angolare tra vettori, e definita e illustata daWesolkowski [30].Wesolkowski definisce questa metrica come:

DV A = sin θ =

(1−

(~v1

T ~v2

‖~v1‖ · ‖~v2‖

)2) 12

Nel suo lavoro, e mostrato come la distanza angolare sia insensibilealle variazioni di illuminazione (intensita) nello spazio RGB, ma sensibilea differenze in tinta e saturazione. Il suo uso come metrica nello spazio dicolore RGB porta a notevoli risultati.Tuttavia, come gia visto per lo spazio HSV, spazi o misure basate su angolimostrano 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 luminositasono basse.Inoltre, il comportamento in altri spazi di colore come Lab e HSV non esensibilmente migliore a quello della distanza euclidea. Anzi, il vector anglequando e applicato a immagini RGB sembra comportarsi meglio di quandoe applicato a immagini Lab.

2.3.3 Combinazione

Per risolvere il problema dell’instabilita del Vector Angle a bassi valori diintensita e della sua indefinitezza a bassi valori di saturazione sono stateimplementate e usate in questo lavoro di tesi delle metriche che combinanola misura ottenuta con la norma L2 con la misura ottenuta con il VectorAngle.Infatti le due combinazioni sono ottenute calcolando sia il Vector Angle che ladistanza euclidea e usando come discriminante la luminosita o la saturazione.Combinare le due metriche e vantaggioso: insieme tengono conto sia dellavariazioni in intensita (o luminanza) che di quelle in crominanza.Inoltre la combinazione ha il vantaggio di evitare l’uso del Vector Anglequando uno dei due colori che devono essere confrontati ha una bassaintensita o saturazione; infatti questa metrica non funziona bene per valoribassi di intensita o saturazione, poiche con tali valori nello spazio RGB piccolevariazioni in una delle tre componenti producono grandi differenze nell’angolo


tra i due colori.Carron e Lambert [4] hanno dimostrato che per valori di saturazione bassi,l’intensita e piu rilevante della tinta, mentre per valori di saturazione piuelevati e la tinta ad avere il peso maggiore. Visto che il Vector Angle euna metrica studiata per cogliere le differenze di tinta e la distanza euclideaattribuisce maggior peso all’intensita, combinare le due metriche usando laprima per valori di saturazione elevati e la seconda per valori bassi dovrebbegarantire buoni risultati.

La rilevanza data ad una misura piuttosto che all’altra puo esser calcolatacome segue: dati due colori, su ognuno di essi si calcola separatamente ilvalore di intensita o saturazione e si sfrutta questo valore per stabilire il pesodi una metrica rispetto all’altra mediante la seguente formula:

α(value) =1

1 + eslope(value−offset)

dove value e il valore di intensita o saturazione del colore, offset il puntocentrale della transizione (quello in cui le due misure hanno lo stesso peso) eslope descrive l’inclinazione in quel punto.Man mano che value cresce, l’output della funzione α cambia da 0 (influenzamassima della distanza Euclidea) a 1 (influenza massima del Vector Angle).

Comunque, visto che per ogni operazione di misura sono presi inconsiderazione due colori e noi desideriamo evitare l’uso del Vector Anglequando uno dei due colori ha intensita o saturazione bassi, dobbiamo definireuna funzione di influenza che sia la combinazione dell’ α dei due colori.

ρ(value1, value2) =√

α(value1) · α(value1)

La misura di distanza tra due colori combinata basata sulla luminosita risultaessere 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 e definita come:

DCombSaturation(C1, C2) =(1− ρ

(S(C1), S(C2)

))·DE(C1, C2) +

ρ(S(C1), S(C2)

)·DV A(C1, C2) (2.6)

28 Il colore

2.4 Misure di similarita tra zone di immagini

a colori

Il problema appena affrontato -dare una misura dell’omogeneita di unaregione di un’immagine a colori- apre le porte a un problema piu ampio:dare una metrica di similarita o differenza tra due zone di immagini a colori.In che misura due zone sono simili rispetto al colore? Oppure in che misuradue intere immagini sono simili rispetto al colore?Il problema, che puo essere esteso ad altre caratteristiche di un’immagineoltre al colore, e quello di introdurre una metrica tra due distribuzioni.Tipicamente le distribuzioni su cui si va ad operare sono istogrammi;in seguito, saranno introdotte forme piu versatili di distribuzione dette“signature” (firme).Per semplicita di notazione, parlando della posizione i− esima all’interno diun istogramma usero il termine inglese bin i (cesto i).

Sono state proposte molte misure di similarita tra due istogrammi, chepossiamo dividere in due categorie.Le misure di similarita bin-by-bin confrontano solo la quantita delle carat-teristiche che occupano la stessa posizione all’interno dei due istogrammi.Le misure di similarita cross-bin invece confrontano anche termini cheappartengono a posizioni differenti; per questo, le misure cross-bin fannouso 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 spiegatocome le misure di entrambe le classi siano spesso insoddisfacenti; questemetriche, sebbene siano state usate con successo in altri campi, in questocaso 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 usatispesso nell’image processing per descrivere e riassumere le caratteristiche di

2.4 Misure di similarita tra zone di immagini a colori 29

un’immagine. Nelle immagini a scala di grigio, l’istogramma monodimension-ale delle intensita descrive il contenuto totale di luminosita di un’immagine,e viene usato in molti algoritmi, specie quando si tratta di stimare dei valoridi soglia.Nelle immagini a colori, lo stesso compito puo essere assolto con una dis-tribuzione tridimensionale; comunque, in questo caso, conviene approssimarela distribuzione originale con una descrizione piu compatta: nello spazioRGB, per esempio, se si considerano 256 livelli per ciascuna banda si hannopiu di sedici milioni di colori differenti.Usare una distribuzione che tenga conto di ogni colore e sia inefficiente daun punto di vista dell’uso delle risorse (memoria e potenza di calcolo) cheinefficace per quanto riguarda la corrispondenza percettiva (nessuno puodistinguere il verde RGB(5, 165, 97) dal verde RGB(6, 165, 97)).Per questo motivo le distribuzioni multidimensionali vengono compressepartizionando lo spazio sottostante in un numero fisso di partizioni, chiamatebin, che di solito hanno dimensione prefissata. La struttura dati risultante equantizzata e puo essere rappresentata da un istogramma, come si fa con leimmagini a scala di grigio.Resta comunque il fatto che solo una piccola percentuale dei bin di unistogramma contiene informazione significativa. Per esempio, se abbiamo unafoto di una pianura verde sovrastata dal cielo azzurro, bastano pochi coloriper descriverla efficacemente. In questo caso un istogramma quantizzatofinemente e piuttosto inefficiente, e avra molti bin vuoti.D’altra parte, nel caso di una foto di una composizione floreale con unamoltitudine di colori differenti, un istogramma quantizzato grossolanamentesarebbe inadeguato.In breve, gli istogrammi sono stutture dati a dimensione fissa, che difficil-mante si possono adattare bene per la descrizione di immagini dal contenutodifferente.

Uso di signature

In [23] e proposta una soluzione a questo problema: viene introdotta unanuova descrizione della distribuzione tridimensionale del colore detta signa-ture (firma). Queste signature sono formate prendendo dalla distribuzioneoriginale i cluster (cioe i gruppi di colore) piu significativi.Una signature e quindi un insieme di cluster, ognuno dei quali rappresentatodal colore dominante e da un peso che da un’indicazione sulla grandezza

30 Il colore

relativa o assoluta del cluster.Immagini semplici hanno signature corte, immagini complesse le hanno piulunghe.Nell’implementazione fatta durante questo lavoro, i cluster vengono ricercatitra i bin non nulli della distribuzione tridimensionale del colore.Viene lasciata grande flessibilita, in quanto e 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 nellasignature: 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 vieneconsiderato nullo (per esempio, per non includere nella signature tuttii cluster con peso minore dello 0.1% );

57846 3870 77750778 1794 76840600 1548 74421432 1304 69517406 1120 58013068 1118 48612420 987 3468954 950 2878580 918 2828046 786 2666201

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 distanzae similarita tra colori e stato illustrato e discusso in precedenza (paragrafo

2.4 Misure di similarita tra zone di immagini a colori 31

2.4).Questo problema diventa piu evidente quando si presenta la necessita diconfrontare insiemi di caratteristiche piuttosto che singoli colori.In [23] e dimostrato come una metrica che voglia essere fedele alla distanzapercettiva tra insiemi di caratteristiche debba gestire le corrispondenze che cipossono essere tra posizioni diverse dell’istogramma (da qui in poi, indicatecon bin).Sempre in [23], e proposta una metrica basata sul matching di grafi bipartitiche e definita come il costo minimo necessario per far corrispondere i bindi un istogramma con quelli di un altro. Questa metrica e chiamata EarthMover’s Distance (EMD).Intuitivamente, date due distribuzioni, una puo essere vista come una seriedi mucchi di terra sparsi nello spazio, e l’altra come una serie di buche dariempire. La distanza tra i mucchi di terra e le buche e la distanza percettivatra i colori che rappresentano i vari bin delle distribuzioni. La EMD misurala quantita di lavoro minimo necessaria per riempire le buche con la terra.Per calcolare l’EMD e sufficiente risolvere il problema del trasporto, per lacui soluzione sono noti algoritmi efficienti. Il problema del trasporto e cosıformulato: si supponga di avere un insieme di fornitori, ognuno dei qualiha un dato ammontare di beni, che deve fornire un insieme di consumatori,ognuno dei quali ha una data necessita. Il costo di trasporto di un bene perogni coppia fornitore-consumatore e considerato noto.Il problema e quello di trovare il piu economico flusso di beni tra fornitori econsumatori che soddisfi la domanda dei consumatori.Come si puo intuire, il problema della Earth Mover’s Distance e quello deltrasporto sono analoghi.In Appendice B e descritto l’algoritmo implementato per risolvere entrambii problemi.

Prima di concludere il discorso sugli spazi di colore e sulle metriche,e necessaria un’ultima considerazione. La necessita di una buona metricae di uno spazio di colore appropriato deriva anche dal fatto che i metoditradizionali per l’edge detection e la segmentazione di immagini a coloririlavano troppi edge “fantasma” o regioni errate a causa degli effetti otticidovuti all’iterazione tra la luce e il materiale dell’oggetto. L’uso di spazi comeHSV o di metriche come il Vector Angle, che riducono il peso della luminosita,permettono di ridurre il numero di edge o regioni spurie. Infatti, e possibiledimostrare [30] come alcuni spazi di colore e metriche siano invarianti rispettoa shadows (ombre), shading (ombreggiatura), e highlights (lucentezze).

Capitolo 3

La tessitura

“...quando guarda tutto l’insieme non si sogna di contare quante sono lescaglie del salmone, le vede come piccole perle argentate contro il grigio e ilrosa [...]. E l’uva! Vuol contare gli acini? Certamente no. Quello checolpisce e 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, contessitura) e legata alle proprieta intrinseche delle superfici ma, al pari delcolore, non e essa stessa una proprieta delle superfici, bensı un prodotto delsistema visivo umano, che la associa a superfici che hanno caratteristiche dicolore, intensita e ruvidezza variabili.

Avendo gia a disposizione l’informazione sul colore, ci si potrebbe chiedereperche ci sia bisogno anche di informazioni sulla tessitura per fornire misuredi distanza e omogeneita che ci consentano di raggruppare i pixel in regionidalle caratteristiche uniformi.Innanzitutto, come gia asserito nel capitolo 1, le caratteristiche di tessiturasono fondamentali nel sistema visivo umano, che le utilizza durante il processodi image analysis compiuto di continuo dalla corteccia.La cosa piu importante, pero, e che la percezione del colore nel sistema visivoumano dipende dalle frequenze spaziali fra i colori. Colori che compaiono

33

in un pattern multicolore sono percepiti come differenti dagli stessi coloripresenti in un’area uniforme. Questo fatto e stato dimostrato da recentiricerche psicofisiche [34], anche se bisogna dire che questa assunzione eraormai 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 coloridiversi (verde smeraldo, ocra, giallo, blu), che singolarmente non percepiamocome il colore del mare, ma che accostati ci danno l’impressione di essere uncolore diverso, quello del mare appunto.

E’ difficile dare una definizione di texture, probabilmente a causa del fattoche quello ci texture e un concetto fortemente intuitivo, legato a propietaanch’esse intuitive e pertanto non facilmente misurabili come la ruvidezza,la regolarita e la granularita.Partendo da questi concetti, si puo comunque azzardare una definizione ditexture come zona di un’immagine che presenta caratteristiche di ruvidezza,regolarita e granularita simili.Una definizione simile e data in [13], mentre in [24] ne viene data una piurigorosa:

Una regione all’interno di un’immagine possiede una tessituracostante se un’insieme di statistiche locali o di altre proprietalocali alla regione sono costanti, poco variabili o approssimativa-mente periodiche.

Per una raccolta di ulteriori definizioni, si veda [29].

In letteratura e stata proposta una gran varieta di metodi per l’analisidelle tessiture, che possono essere raggruppati in quattro categorie [29]:

1. Statistici: i primi lavori si basavano su statistiche del secondo ordineper le tessiture. I metodi statistici (che si basano di solito su matrici dico-occorrenza) ricercano correlazioni locali tra i pixel di un’immaginesu scala fissa.

2. Geometrici: i metodi strutturali o geometrici generano una de-scrizione della tessitura estraendone delle primitive (dette texton) eapplicando delle regole sintattiche a quest’ultime.

3. Basati su Modelli: negli anni ’80 sono stati sviluppati dei modellidi texture basati su Gaussian Markov Random Fields (GMRF) edistribuzioni di Gibbs.

34 La tessitura

4. Basati su analisi del segnale: negli ultimi anni, i modelli basati sull-analisi del segnale visivo con metodi multicanale e multifrequenza han-no ricevuto molta attenzione, in quanto hanno mostrato un’affidabilitae un’efficienza di gran lunga superiori a quelle dei metodi precedenti.

I buoni risultati nel campo della teoria dei segnali applicata all’analisidi tessitura -che e ancora campo di ricerca- suggeriscono che le principalidifficolta nell’ottenere buoni risultati sia dovute alla mancanza di unostrumento di anali adeguato, che sembra esser stato finalmente trovato neimetodi di analisi nello spazio delle frequenze, come i filtri di Gabor o letrasformate Wavelet.

In questo lavoro di tesi si e scelto di concentrarsi sullo studio el’implementazione di metodi basati sulla trasformata Wavelet.

3.1 Trasformata Wavelet

La trasformata Wavelet opera la decomposizione atomica multi-livello di unsegnale, rappresentando il segnale di input come la sovrapposizione di unafamiglia di funzioni di base dette appunto Wavelet. Traslare o dilatare lamother Wavelet (Wavelet madre, la funzione scelta come punto di partenzaper costruire l’insieme delle funzioni base) porta a generare un’insieme difunzioni base. Il segnale e fatto passare attraverso un filtro passa-bassoseguito da un filtro passa-alto. Gli output dei filtri sono sottocampionatiper il prossimo livello di decomposizione, permettendo cosı all’informazioneportata dal segnale di essere rappresentata a diverse scale. Una descrizionepiu precisa dal punto di vista matematico esula dagli scopi di questa tesi;per avere un ragguaglio piu preciso si consigliano [14], [29] e [25]. In questasede, basti sapere che, analogamente alla trasformata di Fourier e alla FFT,esistono metodi efficienti di calcolare la trasformata Wavelet di un’immaginea partire dalla coppia di filtri di cui sopra. Questi algoritmi prendono il nomedi DWT per la trasformata Wavelet piramidale e di PKWT per trasformataPacket Wavelet (vedi sotto).

Le ragioni che hanno portato alla scelta della trasformata Wavelet comestrumanto 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 peruna localizzazione precisa.Le trasformate Wavelet, a differenza di altri metodi per l’analisi delsegnale come le trasformate di Fourier, sono localizzate sia nellospazio che in frequenza. Inoltre il compromesso tra la risoluzionenello spazio e quella in frequenza e buono, e quindi la segmentazionebasata su caratteristiche calcolate a partire dai coefficienti Waveletdovrebbe garantire buoni risultati, anche se piuttosto grossolani perquanto riguarda la localizzasione spaziale; questo e uno dei motivi percui non e possibile offrire una segmentazione basata esclusivamentesui coefficienti della trasformata Wavelet, ma e necessario semprecombinare questa tecnica con altre.

- Studi psicofisici [34] hanno dimostrato che il sistema visivo umanoanalizza le immagini in modo multiscalare; la prima elaborazioneeffettuata dal cervello e un’analisi di frequenza spaziale, che attivaneuroni diversi nella parte della corteccia adibita alla visione a secondadella frequenza e dell’orientamento.Inoltre, quando e necessario il riconoscimento di forme e oggetti,l’occhio umano analizza il segnale visivo in modo approssimato, e poiguarda i dettagli per avere una corrispondenza piu precisa [2].La trasformata wavelet permette di procedere all’analisi di un’immag-ine in maniera simile, dividendo le immagini in sottobande diverse aseconda della frequenza, dando ad ognuna diverse caratteristiche difrequenza e orientazione.

- Anche i filtri di Gabor permettono di ottenere il medesimo risulatato,e sono stati applicati per anni all’analisi di texture. Tuttavia leWavelet si comportano altrettanto bene (specie su consideriamo lepacket wavelet, vedi sotto) e sono molto meno costose dal punto divista computazionale.

Durante la preparazione di questa tesi sono state presi in considerazionee studiati diversi modi di utilizzare il potenziale delle trasformate Waveletper ottenere una segmentazione dell’immagine.Infatti, una volta deciso di usare le Wavelet come strumento per l’analisidelle texture, e necessario scegliere:

36 La tessitura

Regioneprimaria

Regioneprimaria

HL

HHLH

LL

C H1

V1 D

C H1 H2 H3

V1

V2

V3

LLL LHL

LLHLHHHL

HHLH

Figura 3.1: La trasformata wavelet discreta (DWT, sopra) e la trasformatawavelet 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 effettuarel’analisi dell’immagine, non e neccesario che la ricostruzione sia perfetta-cioe non e richiesto che l’applicazione della trasformata inversariproduca l’esatta immagine di partenza-, quindi possiamo usare anchefiltri 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 anchepacket wavelet, figura 3.1 sotto).

3. Una volta ottenuti i coefficienti, come utilizzare l’informazione adessi associata -cioe a quali delle diverse caratteristiche estraibili daicoefficienti affidarsi per la descrizione della tessitura- e come misurarela 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 daimpiegare con la trasformata Wavelet: un filtro biortogonale 9/7, un filtro diDaubechies (daub4, si veda [22]), entrambi dal supporto compatto, nonche


ortogonali e separabli, e un filtro SPLINE, i cui filtri passa-basso e passa-alto h0 = [1/4 3/4 3/4 1/4] e h1 = [-1/4 -3/4 3/4 1/4] sono separabili e dalsupporto compatto e quindi utilizzabili con la DWT e la PKWT, anche senon sono ortogonali.Quest’ultimo in particolare estrae le caratteristiche di tessitura moltoefficacemente [1] ed e quindi stato scelto per esser utilizzato nell’algoritmoproposto.

Figura 3.2: L’immagine flower garden

3.1.2 Tipo di decomposizione

Per quanto riguarda il secondo punto, quale tipo di decomposizione usare, eormai stato provato in numerosi lavori - [25], [19], [1] - che la decomposizionepacket wavelet offre performance superiori grazie a una analisi piu appro-fondita di tutte le bande. In particolare, usando la trasformata Waveleta pacchetti, si produce un’immagine composta da diverse sottobande,ognuna con le sue caratteristiche di frequenza e orientamento. Si osservila figura 3.3: in rosso sono evidenziate le sottobande che rappresentanoalte frequenze verticali, cioe carateeristiche orizzontali, in blu le sottobandeche rappresentano alte frequenze orizzontali, cioe caratteristiche verticali,mentre le altre sottobande -evidenziate in bianco- rappresentano un misto diinformazione 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 e piu sensibile lungo le direzioni orizzontale

38 La tessitura

e verticale, e che gran parte dell’informazione e convogliata nelle sottobandeorizzontale e verticali (indicate rispettivamente come bande Hi e V i, i =1, .., n− 1) e possibile utilizzare le sole bande Hi e V i per l’analisi.

Figura 3.3: La trasformata wavelet a pacchetti (PKWT) dell’immagine flowergarden

3.1.3 Estrazione caratteristiche e metriche

Il terzo punto, che riguarda quali caratteristiche estrarre dai coefficienti perla descrizione della tessitura e come fornire una misura di distanza tra leregioni che sia percettivamente corretta, e un problema molto complesso eancora aperto. In questa tesi sono stati presi in considerazione le seguenticaratteristiche e misure di similarita.

Direzionalita, regolarita e granularita

Inizialmente si e pensato di poter sfruttare delle misure di direzionalita, rego-larita e granularita definite in [1], che si basano sull’analisi dell’istogrammadella matrice di co-correlazione tra righe e colonne delle bande orizzontalie verticali. Queste dimensioni sono le piu importanti da un punto di vistapercettivo; usando una metrica basata su di esse, la classificazione delle zonesi sarebbe basata su caratteristiche simili a quelle percepite dal sistema visivo


umano. Esperimenti condotti in questo senso hanno dimostrato che in effettiqueste misure caratterizzano molto bene le texture, ma che non sono adatteallo scopo di segmentare l’immagine.In primo luogo il metodo basato su matrice di co-correlazione fornisce buonirisultati 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 piu quadrata, di una sigola texture.In pratica quindi questo metodo e molto buono per lo scopo per cui estato ideato, la classificazione di texture, e potrebbe anche essere estesoall’estrazione di features da regioni con texture per l’image retrieval, main questo caso si richiede una previa segmentazione dell’immagine. Propriocio che si sta cercando di ottenere.

Energia locale

La soluzione piu frequente in letteratura e quella di usare come caratteristicaper la descrizione della tessitura l’energia locale di ogni coefficiente.L’energia locale EV

i dei coefficienti wavelet {cV i} alla posizione (x, y) edefinita come

EVj (x, y) =

∑

r,s∈Z

(cV j(r, s))2K(x− r, y − r)

dove Z e un’intorno di (x, y) e K(x, y) e un kernel, positivo e dalla forma acampana, di solito un kernel Gaussiano. L’energia locale EH

i e definita nellostesso modo.

L’energia locale caratterizza bene la tessitura ([26], [29]), e quindi comecaratteristica della tessitura nell’intorno del pixel (x, y) il si puo utilizzare ilvettore:

[ log EV1 (x, y), log EH

1 (x, y), log EV2 (x, y), log EH

2 (x, y), ...,

log EVn (x, y), log EH

n (x, y)] (3.1)

Come metrica di distanza e utilizzabile una semplice distanza bin-by-bintra i due vettori: la distanza tra due vettori di caratteristiche e la sommadelle distanze (calcolate tramite norma L1 o L2) tra elementi del vettore in

40 La tessitura

posizioni corrispondenti. Se f1 e f2 sono due vettori delle caratteristichedefiniti come sopra la distanza d tra di loro e pari a:

dW =n∑

i=1

‖f1i − f2i‖

Analogamente, utilizzando vettori composti dalla media delle energie deipixel dalla regione, e possibile ottenere una metrica di distanza tra regioni.

Texture map

Figura 3.4: La mappa delle classi di texture ottenuta dall’applicazionedell’algoritmo proposto sull’immagine flower garden

In [5] viene descritto un nuovo modo per utilizzare l’informazioneassociata ai coefficienti Wavelet ed estrarne caratteristiche misurabili, ac-creditato di buoni risultati. Questo metodo consiste nel realizzare unasegmentazione grossolana dell’immagine basandosi sull’energia locale deipixel, classificandoli in 2(2n−1)·2 classi, dove n e il numero di decomposizionieffettuate dalla trasformata (per esempio, l’immagine in figura 3.3 e statarelizzata con due decomposizioni, quindi i sui pixel saranno classificati in 64classi).Questo modo di calcolare il numero di classi e fondato.Infatti la classificazione avviene prendendo in considerazione le sottobandeHi (che sono 2n − 1) e V i, (che sono 2n − 1, in totale numero di classim = (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


ognuna delle m bande. Questa partizione in due categorie per ognuna dellebande considerate porta appunto a 2m classi totali (si veda la figura 3.4).

Il risultato di questa segmentazione “grossolana” viene combinato conl’informazione sul colore in un modo molto semplice ma sorprendentementeefficace: la metriche sui colori vengono “influenzate” dalla classificazionedelle texture, che viene usata come un peso: se due pixel appartengonoalla stessa classe di texture, il peso (Klow) e minore di 1.0 e quindi laloro distanza diminuisce, mentre se i due pixel appartengono a classi ditexture diverse la distanza viene leggermente aumentata moltiplicandola perun 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 percezionedel colore nel sistema visivo umano dipende dalle frequenze spaziali fra icolori. Questo, tuttavia, era gia stato intuito dai pittori impressionisti centoanni prima.

Capitolo 4

Tecniche di segmentazione

“Quicquid est in intellectu praesse debere in sensu.”(Bisogna avere esperienza di tutto cio che e nell’intelletto)Gassendi“Nec scire fas est omnia.”(Non e concesso sapere tutto)Orazio, Odi

La segmentazione e il processo di suddivisione di un’immagine in regionidistinte in modo tale che ogni regione sia omogenea rispetto ad una datacaratteristica, e che l’unione di due regioni adiacenti non lo sia. La loro unionedeve essere l’intera immagine di partenza. Il processo di segmentazionee un passo fondamentale nell’ambito dell’image analysis e della patternrecognition, il cui scopo e di scomporre un’immagine in parti che sonosignificative rispetto a una particolare applicazione.

La segmentazione e una fase critica nell’analisi dell’immagine: la preci-sione e la qualita del risultato della segmentazione possono influenzare moltopesantemente le fasi successive.La segmentazione puo trarre molti vantaggi dall’uso del colore, perche spessoun oggetto e formato da parti colorate identificabili dalla segmentazione. Lasegmentazione nelle immagini a scala di grigio si basa su criteri legati al

44 Tecniche di segmentazione

valore di luminosita nell’immagine, che puo corrispondere sia a variazioni ditinta che a cambiamenti di illuminazione. In scala di grigio e impossibiledistinguere tra i due, mentre con le immagini a colori questo e possibile. Peresempio, utilizzando spazi di colori appropriati (come HSV, paragrafo 2.2.6)o metriche studiate appositamente (come il Vector Angle sugli spazi RGB oRGBN, vedi paragrafo 2.3.2 a pagina 26) si possono distinguere zone in cui ilcolore varia a causa di un cambiamento di tinta da zone in cui il colore variaa causa di un cambiamento di luminosita dovuto alla geometria dell’oggettoe all’illuminazione.Inoltre, come gia sottolineato in precedenza, il colore e predominante nelsistema di visione umano: l’occhio distingue migliaia di colori, ma solo pochetonalita di grigio. Un sistema che simuli da vicino il modello umano non puoche portare a risulatati che corrispondono maggiormente alle aspettative diun osservatore umano.Un buon metodo di segmentazione dovrebbe soddisfare i seguenti criteri:

- Le regioni devono essere il piu possibile omogenee

- I confini delle regioni devono essere compatibili con le variazioni dellamisura di similarita adottata.

- Aree percettivamente uniformi non dovrebbero essere divise in piuparti. In particolare questo si applica a regioni con ombreggiaturagraduale e a regioni con tessitura.

- Piccoli dettagli, se ben definiti in forma e contrasto, non dovrebberoessere fusi con le regioni confinanti.

Sono note molte tecniche di segmentazione, sia per quanto riguarda leimmagini a scala di grigio che per quanto riguarda le immagini a colori.Queste tecniche si differenziano per la definizione del criterio di omogeneitatra regioni e per l’algoritmo usato per costruire queste regioni.

Le prime tecniche di segmentazione studiate sono state sviluppate pertrattare immagini a scala di grigio, e solo in tempi relativamente recenti illavoro si e esteso anche alle immagini a colori.La scelta di usare immagini a scala di grigio presenta non solo il vantaggiodi trattare con un volume di dati molto minore, ma anche di considerare leimmagini come funzioni scalari a due dimensioni su cui sviluppare algoritmi

45

computazionalmente piu semplici.

Gli approcci per la segmentazione di immagini monocromatiche sonobasati su misure di discontinuita o omogeneita nei livelli di grigio del-l’immagine. I metodi basati sulla rilevazione di discontinuita partizionanol’immagine rilevando punti isolati, edge, linee e contorni, mentre gli approccibasati sull’omogeneita includono l’histogram thresholding, clustering, regionsplitting and merging e region growing.Questi ultimi possono essere ulteriormente suddivisi in tecniche di raggrup-pamento rispetto alle sole caratteristiche dei pixel (che tengono cioe inconsiderazione solo i valori dei singoli pixel) e tecniche basate sul rilevamentodi regioni (e che quindi combinano informazioni sui valori dei pixel coninformazioni spaziali).

La maggior parte degli algoritmi studiati per le immagini monocromatichepossono essere estesi all’utilizzo con immagini a colori applicando il metodoseparatamente ad ogni componente dello spazio di colore scelto, combinandoi risultati ottenuti tramite un criterio ad hoc per ottenere la segmentazionefinale.Tuttavia e necessario notare che nel caso di immagini a colori, e importantesfruttare per ogni pixel l’informazione sul colore nella sua interezza. Quandoil valore del pixel e proiettato sulle tre componenti, l’informazione sul coloreviene frantumata e l’informazione sul colore cosı come viene percepita dagliesseri umani e persa. Il sistema visivo umano, infatti, non percepisceun’immagine separata per ogni componente di colore, ma usa l’informazionesul colore nella sua interezza.Un approccio migliore e quello di definire delle metriche opportune nellospazio di colore che giocano il ruolo dell’operazione di differenza usata neglialgoritmi grayscale, nei criteri di omogeneita basati sulla distanza (come ilMAD) e nelle misure di discontinuita.

Prima di passare alla descrizione del metodo oggetto di studio in questatesi, e utile una breve rassegna dei principali metodi di segmentazionebottom–up. Questi metodi sono stati inizialmente studiati e realizzati peril trattamento di immagini in scala di grigio, ma sono stati in seguito estesianche all’utilizzo con immagini a colori. In [6] sono analizzate le varie tecnicheche sono illustrate brevemente nei paragrafi sequenti.


4.1 Approcci basati su misure di discontinu-

ita

L’approccio basato sul rilevamento delle discontinuita e meglio noto con ilnome di edge detection (letteralmente“rilevamento dei bordi”).Questo approccio consente di trovare i contorni delle regioni costituenti lasegmentazione dell’immagine. In un’immagine monocromatica, un edge edefinito come una discontinuita nel livello di grigio, e quindi e rilevato dovesono presenti differenze significative nella luminosita.Nelle immagini a colori le informazioni sui bordi sono molto piu ricche: peresempio, si puo rilevare un edge tra due zone con stessa luminosita ma tintadifferente. In un’immagine a colori un edge e definito come una discontinuitalocale calcolata nello spazio colore tridimensionale. Tenendo presente questaaffermazione, e possibile seguire almeno tre approcci per l’edge detection [6]:

1. trattare l’immagine a colori come se fosse composta da tre immaginimonocromatiche, applicare su ognuno dei tre piani separatamente unalgoritmo specifico per l’edge detection su immagini a livelli di grigio,quindi combinare i risultati.Lo svantaggio e che cosı facendo si perde l’informazione sulla corre-lazione tra le tre componenti e, in alcuni casi, si puo arrivare a risultatidifficili da combinare (per esempio quando i tre gradienti per un pixelhanno lo stesso valore ma direzioni differenti, o quando un edge sipresenta su uno solo dei tre piani);

2. per mezzo di una misura di similarita e definita valida nello spazio dicolore, rilevare le discontinuita tra le distanze per determinare gli edge.Anche questo metodo tiene poco conto del fatto che siamo in uno spaziovettoriale, ma riesce comunque a catturare edge dovuti a differenze diluminosita, tinta e saturazione;

3. considerare l’immagine come un campo vettoriale bidimensionale; conquesto approccio il valore dell’immagine in una locazione data e unvettore in R3. Quindi si definisce una misura del gradiente che siasignificativa nel campo vettoriale, e si calcola la derivata seconda. Ipunti in cui la derivata seconda e nulla (zero-crossing) sono gli edge.Questo approccio e stato introdotto in [7] da Cumani sulla base di unlavoro di DiZenzo [8].

4.2 Approcci basati su misure di omogeneita 47

Va sottolineato il fatto che l’edge detection in generale non genera unasegmentazione dell’immagine ma fornisce informazioni utili sui confini trale regioni a moduli di piu alto livello, o puo essere usato in combinazione conaltri approcci, come quelli basati su regioni.

4.2 Approcci basati su misure di omogeneita

4.2.1 Histogram thresholding

Histogram thresholding significa letteralmente “sogliatura dell’istogramma”.Qesto approccio assume che l’immagine sia composta da regioni che dif-feriscono tra loro per l’intervallo di valori dei pixel che le compongono, cosıche l’istogramma di un immagine presenti dei picchi in corrispondenza diquesti valori. I valori che corrispondono a valli nell’istogramma sono utilizzaticome soglie per distinguere le regioni tra di loro.

4.2.2 Clustering

Clustering: raggruppamento in sottoinsiemi di oggetti con caratteristichesimili, puo essere usato come tecnica di segmentazione considerando il livellodi grigio come caratteristica rispetto alla quale raggruppare i pixel. Lasegmentazione ottenuta con il clustering trascura la relazione spaziale tra ipixel. E’ necessaria una fase successiva in cui si tiene conto delle informazionispaziali per formare le regioni: pixel adiacenti appartenenti alla stessa classecostituiscono una regione omogenea.L’algoritmo piu diffuso per il clustering di dati e l’algoritmo K-means, che sicompone 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 alpunto 3


5. se i centri sono stabili (non sono cambiati dopo il passo 4 o si sonosposatati di poco) ci si ferma, altrimenti si torna al punto 3.

Al terzo passo la classificazione e realizzata mediante un algoritmo 1–NN(1–nearest neighbor, il dato appartiene alla classe a cui e piu vicino) usandola distanza euclidea come unita di misura.

4.2.3 Region splitting & merge e Region growing

Gli approcci basati su regioni sono fra i piu diffusi e usati, poiche permettonodi considerare allo stesso tempo informazioni sui valori (livello di grigio ocolore) e dettagli spaziali. Essi comprendono region splitting & merge eregion growing.

Nell’approccio originale del region splitting, la regione di partenza (ilseme) e costituita dall’intera immagine. Se il seme non rispetta il criterio diomogeneita viene suddiviso in quattro semi. Questa procedura viene iteratafino a quando tutte le regioni sono omogenee. Solitamente al processo displitting viene fatto seguire un processo di merging per fondere le regioniuniformi che a causa del processo di splitting erano state erroneamente divise.Lo svantaggio principale di questa tecnica e che tende a produrre regionitroppo quadrate, spigolose. 1

In generale, in un algoritmo di region growing, viene scelto un insieme dipiccole regioni di partenza dette seeds (semi), che sono espanse per includeretutti i pixel confinanti che rispettano un criterio di omogeneita; il processo eripetuto finche ogni pixel dell’immagine e assegnato ad una regione.

1questo e l’algoritmo originale. Piu in generale, un algoritmo di split & merge sicompone di due fasi:

1. La fase di split si applica all’intera immagine. Se essa e omogenea rispettoal predicato la segmentazione termina, essendo costituita dall’intera immagine.Altrimenti essa viene suddivisa ricorsivamente in parti fino ad ottenere un insiemedi regioni che soddisfano il predicato.

2. Nella fase di merge vengono analizzate tutte le coppie di regioni adiacenti,verificando il predicato di omogeneita sull’unione, in modo da garantire lamassimalita delle regioni.

4.2 Approcci basati su misure di omogeneita 49

Lo svantaggio principale di questa tecnica sta nella difficolta di scegliere leregioni iniziali. L’algoritmo infatti non aumenta ne diminuisce il numerodi regioni, che quindi devono essere una buona base di partenza per i passisuccessivi.

Capitolo 5

L’algoritmo proposto

“Nec minor est virus quam quaerere parta tueri.”(Ne minore abilita del trovare le cose nuove e nel saper conservare le giaacquisite.)Ovidio

Tutte le tecniche presentate nel capitolo precedente sono state studiate alungo. In questo lavoro di tesi si e deciso di implementare una variante delregion growing, poiche si e dimostarata una delle tecniche con il piu grandepotenziale per poter raggiungere i requisiti delineati nel capitolo 1.

Il fuzionamento di base del region growing e piuttosto semplice dadescrivere: dato un insieme di punti o regioni iniziali, queste regioni vengonoespanse inglobando in esse i pixel limitrofi che superano un test di similaritacon la regione. Se un pixel e candidato per entrare a far parte di due regioni,cioe confina con piu di una regione, viene inglobato nella regione a cui e piuvicino per somiglianza.

Recentemente sono stati introdotti alcuni algoritmi basati sul paradigmadel region growing nell’ambito della segmentazione di immagini a colori:

- In [32] si presenta un algoritmo di region growing classico, in cui siusa il Vector Angle (si veda 2.3.2) come misura di similarita tra i

51

colori, e la componente principale (PC) della matrice di covarianzacome colore “caratteristico” della regione, con l’obiettivo di fornire unasegmentazione in regioni percettivamente corretta.

- In [10] si utilizza un algoritmo di region growing abbinato a unalgoritmo di edge detection. Dopo aver ottenuto la mappa degli edge, icentroidi delle regioni delineate dagli edge sono presi come semi perl’algoritmo di region growing che utilizza una misura di similaritatra colori. Infine, il risultato dell’algoritmo di region growing vieneintegrato con il risultato dell’edge detection per avere dei confini chiusie piu accurati.

- In [33] viene proposto un metodo per la segmentazione automatica diregioni caratterizzate da colore e tessitura, chiamato JSEG. Il metodosi articola in due passi: quantizzazione dei colori e segmentazionespaziale. Nel primo passo i pixel vengono suddivisi in varie classibasandosi esclusivamente sull’informazione di colore. Nel secondo passosi utilizzano la mappa delle classi prodotta al passo precedente e uncriterio per valutare l’omogeneita di un pattern di colore-tessitura(detto J): applicando il criterio a una finestra locale per ogni elementodella mappa delle classi si produce una “J-image” i cui valori di minimoe massimo corrispondono a possibili confini delle regioni. Si procedequindi con un algoritmo di region growing, che si basa sulle informazionidelle “J-image” per produrre la segmentazione finale.

Di questi tre approcci, solo JSEG utilizza anche informazioni sullatessitura: questo lo rende uno degli algoritmi piu interessanti ed utilizzati(per esempio in sistemi di image retrieval, o in algoritmi di compressione cherichiedono l’identficazione di zone e oggetti come MPEG-7); per le prestazionidi quest’algoritmo si veda [33].

Esistono tuttavia numerose altre varianti della tecnica di region growing,che differiscono tra loro in uno o piu dei seguenti passi:

Scelta iniziale dei semi: la scelta iniziale dei semi puo esser vista comeuna procedura di segmentazione incompleta in cui pixel sono assegnatia delle regioni se questo puo esser fatto con alta confidenza. I semipossono esser selezionati con differenti criteri, ognuno dei quali mostrabuone capacita nel rilevare regioni dalle caratteristiche differenti;

52 L’algoritmo proposto

per esempio un criterio per trovare regioni omogenee rispetto allaluminosita o ad un colore e quello di specificare una soglia sulla mappadel gradiente di un’immagine: le componenti connesse formate dai pixelche stanno al di sotto di questa soglia costituiscono i semi.

Strategia di growing: ad ogni iterazione dell’algoritmo i pixel confinanticon le regioni presenti formano un insieme, detto insieme dei candidati,all’interno del quale vengono selezionati alcuni pixel per l’accrescimentodelle regioni. I candidati sono un sottoinsieme dei pixel non assegnatiche meritano di essere analizzati per accrescere le regioni. La modalitadi selezione dei pixel dall’insieme dei candidati e il numero di pixelselezionati per l’accrescimento dipendono dalla strategia di growingadottata.In letteratura si trovano principalmente due strategie:

1. Selezionare per l’accrescimento e inserire nelle rispettive regioni diappartenenza tutti i pixel dell’insieme dei candidati che superanoun test basato sulle metriche di distanza (vedi sotto). Questastrategia presenta due debolezze: dipendenza dall’ordine in cuivengono considerate le regioni e scarso controllo sulla direzionedella crescita delle regioni. Questi difetti portano all’assegnazionedi pixel alle regioni sbagliate.

2. Selezionare per l’accrescimento e inserire nella regione di ap-partenenza esattamente un pixel per regione, il pixel tra icandidati per quella regione che si rivela piu vicino alla regione inaccordo alla metrica di distanza usata. Questo metodo garantisceun miglior controllo sulla direzione di crescita delle regioni,tuttavia l’assegnazione di pixel a regioni errate e ancora possibile.Seguendo questa strategia, infatti, le regioni tendono espandersitutte in ugual misura, un pixel alla volta, cosı e molto probabileche le regioni piu piccole si espandano piu del dovuto a spese delleregioni confinanti.

I problemi propri di queste due strategie possono esser risolti usandouna diversa strategia di growing, che e stata implementata comeparte dell’algoritmo proposto, e quindi verra illustarata nella prossimasezione.

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 vannofusi con le regioni confinanti. Le metriche di distanza forniscono unamisura della distanza tra il pixel canditato e la regione, cioe dannoun’indicazione di quanto il pixel candidato sia adatto a far parte diquella regione.In letteratura sono state proposte varie metriche, basate su misure didiscontinuita, similirata o omogeneita.Le metriche basate su misure di discontinuita prendono in consid-erazione il pixel candidato e uno dei pixel appartenenti alla regionedesignata, quello adiacente al candidato. Per questi due pixel vengonocalcolate certe caratteristiche dell’immagine, come per esempio ilcontrasto [15] o il gradiente. Se la caratteristica e continua tra i duepixel, allora la metrica fornisce un valore di distanza basso, in modoche il candidato abbia un’idoneita elevato e un’alta probabilita di esserselezionato per l’accrescimento dalla strategia di growing. Nel caso incui invece ci sia una discontinuita nella caratteristica, a metrica fornisceun valore di distanza elevato, in modo che sia probabile che il pixelcandidato non venga accorpato alla regione.Le metriche basate su misure di similarita misurano la distanza tra ilpixel e la regione secondo metriche definite su caratteristiche estraibilida un pixel o da una regione. Le metriche basate su misure diomogeneita, infine, misurano l’omogeneita della regione prima e dopoche il pixel candidato e stato assegnato alla stessa. La variazione diomogeneita della regione e usata come criterio per stabilire l’idoneitadel pixel alla fusione con la regione.

Per l’algoritmo proposto in questa tesi sono stati considerati questi trepunti e per ognuno di essi si e studiata e implementata la soluzione che sie rivelata migliore o piu promettente. Lo schema dell’algoritmo di growingproposto ed implementato e raffigurato in figura 5.1.

5.1 Scelta iniziale dei semi

I risultati ottenuti con un algoritmo di region growing dipendono pesante-mente dal numero e dalla posizione delle regioni iniziali, dette seeds (semi).Questo perche la fase di growing dell’algoritmo non aumenta ne diminuisceil numero di zone in cui viene segmentata un’immagine: se una regione nonviene rappresentata da un seed fin dall’inizio questa e persa, in quanto i pixel


Preprocessing

Immagine

Seed selection

Region growing

Segmentazione

Merging

Small seed selection

Flat seed selection

Texture seed selection

Figura 5.1: Lo schema dell’algoritmo di region growing proposto edimplementato.

che la compongono vengono assegnati alle regioni limitrofe, producendo cosıuna sotto–segmentazione.Al contrario, se i semi sono troppo numerosi, l’algoritmo dividera zonepercettivamente uniformi in piu regioni, creando un problema si sovra–segmentazione.Anche la collocazione spaziale e la dimensione dei semi influenzano molto lebuone prestazioni dell’algoritmo.In particolare, un numero scarso di semi dall’area ridotta porta a una perditadi efficienza dell’algoritmo, in quanto il maggior numero di pixel da assegnarerende piu 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, siprendono come regioni iniziali i pixel connessi che stanno al di sottodi questa soglia. Le regioni ottenute sono prive di forti discontinuitanell’illuminazione o, in generale, nel colore e quindi possono essereconsiderate uniformi. Questo criterio e affidabile se le regioni trovatesono piuttosto grandi, altrimenti potrebbero essere state generate daminimi locali dovuti al rumore. Usando questo criterio quindi regioni


piccole (come caratteri di un testo, particolari di un vestito) potrebberoesser trascurate e quindi produrre una sotto–segmentazione.

- Negativo della mappa degli edge:come gia detto in precedenza (capitolo 4) gli edge detectors da soli nonbastano per fornire una segmentazione dell’immagine. Questo perchespesso tendono a tralasciare bordi importanti, a generare bordi nonchiusi e quindi a creare poche grandi componenti connesse. Tuttavia,possiamo utilizzare la mappa degli edge per cercare piccole regioniche hanno un perimetro chiuso. Gli esperimenti condotti provano chequesto metodo e efficace nel trovare regioni piccole molto contrastateai bordi.

Questi criteri si prestano bene a generare i semi per un algoritmo di regiongrowing su immagini a colori, pero presentano entrambi degli svantaggi:il primo criterio non cattura le regioni piccole, il secondo criterio falliscenell’estarazione di regioni grandi e poco contrastate ai bordi; entrambi nonsono adatti a trovare regioni caratterizzate da una tessitura.

Durante il lavoro di studio di questa tesi e stato sviluppato e realizzatoil seguente criterio per l’estrazione di semi che si comporta bene sia nel casodi regioni caratterizzate da una tessitura che di regioni uniformi:

- L’immagine viene suddivisa in quadratini piuttosto piccoli (6×6, 8×8o 10 × 10) pixel a seconda della dimensione dell’immagine) e su taliquadratini viene calcolata la signature utilizzando l’algoritmo descrittoin [23] e riassunto in 2.4.1.

- I quadratini vengono ulteriormente suddivisi in 4 zone, e per ognuna diesse viene calcolata la signature. Quindi, usando la EMD, vengonocalcolate le distanze tra le signature di due zone adiacenti, comeillustrato in Figura 5.2, e tra la zona e l’intera piastrella.

- Se la distanza massima e inferiore a una soglia T , allora la signatureall’interno del quadratino e considerata uniforme, e quindi o la regioneha colore omogeneo, o e costituita da un pattern regolare formato daicolori presenti nella signature (figura 5.2). Tali regioni costituiscono isemi.


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 regioniuniformi anche in presenza di rumore, mentre il primo metodo richiede cheil rumore sia preventivamente ridotto, per esempio tramite un’operazione dismoothing.Sebbene questo terzo criterio sembri offrire risultati migliori rispetto agli altridue, presenta anch’esso lo svantaggio di non rilevare regioni relativamentepiccole, con altezza o larghezza inferiori alla dimensione del quadratino.

Cio porta a considerare che un singolo metodo per la selezione dei seminon e sufficiente: se esistesse un metodo cosı potremmo probabilmente usarlo


direttamente per segmentare l’immagine.La soluzione proposta in questa tesi e quella di adottare una procedura diselezione dei seed che combini i semi provenienti da sorgenti diverse.La decisione di quale semi selezionare e presa sulla base di un valore di fitness,calcolato su ogni regione a partire dall’area della stessa, e sul vincolo che dueregioni differenti non devono sovrapporsi. In Figura 5.1 e formalizzato ilmetodo per la selezione dei semi ottenuti con criteri diversi.

Cosı facendo non solo si ha il vantaggio di avere seed scelti con criteridifferenti che comprendano regioni dalle caratteristiche differenti, sia regionipiccole e uniformi che grandi e caratterizzate da una tessitura, ma silascia spazio anche ad estensioni future che utilizzano tecniche differentiper la selzione dei seed. Per esempio, un’estensione dell’algoritmo potrebbeselezionare seed le regioni con hue uniforme, al fine di diminuire il numero diartefatti dovuti alla presenza di ombreggiature, ombre e lucentezza (si vedaa proposito il paragrafo 2.2.6).

SeedPriorityQueue region queue;SeedRegionSet region set;

for each SeedSelector ss.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.


5.2 Strategia di growing

Nella parte introduttiva del capitolo era stata introdotto il concetto distrategia di growing ed erano state presentate due diverse startegie e le lorocarenze; in particolare, la dipendenza dall’ordine in cui vengono consideratele regioni e lo scarso controllo sulla direzione della crescita delle regioni.Queste debolezze portano all’assegnamento di pixel al regioni errate. Questoproblema e stato risolto introducendo una terza strategia di selezione deipixel tra i candidati.Questa strategia, proposto in [18], seleziona per l’accrescimento e inseriscenella relativa regione esattamente un pixel per iterazione, scelto tra tuttii candidati. Rispetto alle altre strategie, viene introdotto un ordinamentoglobale sull’insieme dei candidati, basato sulla metrica di distanza adottata:i pixel sono ordinati sulla base della loro distanza della regione con cuiconfinano.Il pixel scelto dalla strategia e quello piu vicino alla relativa regione, e quindiil piu promettente tra i candidati: questo assicura che l’espansione procedanella direzione e sulla regione migliori per quell’iterazione.

Questo strategia puo esser implementata in maniera efficiente usando unacoda di priorita globale: i pixel sono ordinati all’interno della coda a secondadella loro priorita, che corrisponde alla distanza dalla regione per cui sonocandidati. La coda viene inizializzata all’inizio dell’algoritmo inserendovi ipixel sul bordo esterno dei semi. Durante l’esecuzione dell’algoritmo, quandoun pixel viene selezionato dalla strategia per essere assegnato, viene toltodalla coda e i suoi vicini (4- oppure 8-connessi) vengono inseriti alla posizionecorretta, data dalla loro distanza dalla regione. Questo garantisce che ad ogniistante nella coda a priorita vi siano tutti i pixel del bordo esterno di tuttele regioni, ordinati secondo la metrica data dal criterio di growing adottato.

Il vantaggio maggiore di questo approccio, descritto dallo pseudo-codicein figura 5.2, e quello di combinare in modo elegante informazioni locali (ladistanza del pixel dalla regione) con informazioni globali (l’ordine dei pixel).Inoltre l’accorgimento di mantenere i pixel all’interno della coda tra un’it-erazione e la successiva, aggiungendo e togliendo solo i pixel interessatidall’assegnamento, porta notevoli vantaggi in termini di efficenza: adogni 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

priorita realizzata tramite heap, le operazioni di estrazione dell’elementocon priorita minima, di cancellazione dell’elemento con priorita minimae di inserimento di un elemento possono esser realizzate in modo moltoefficente, con complessita pari a O(1), O(log n) e O(log n) rispettivamente.Tuttavia, questo accorgimento porta anche uno svantaggio che potrebbedare origine ad errori nell’assegnamento dei pixel: la priorita del pixel(e quindi la sua posizione all’interno della coda) e quella calcolata almomento del suo inserimento nella coda. Tra il momento dell’inserimentoe quello dell’estrazione possono passare diverse iterazioni; cambiamenti nellecaratteristiche delle regioni dovute all’accrescimento delle stesse potrebberoaver modificato la distanza del pixel dalla regione. In realta, da un puntodi vista pratico, la differenza tra la distanza al momento dell’inserimento equella al momento dell’estrazione e molto ridotta, trascurabile ai fini di unacorretta 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 forend while

Figura 5.4: Algoritmo per il growing basato sulla strategia proposta


5.3 Metriche di distanza

Le strategie di growing presentate in questo capitolo si appoggiano su dellemetriche di distanza per stabilire quali tra i pixel candidati vadano fusi conle regioni confinanti e in che ordine debbano esser considerati. Le metrichedi distanza forniscono una misura della distanza tra il pixel canditato e laregione, cioe danno un’indicazione di quanto il pixel candidato sia adatto afar parte di quella regione.Nei capitoli precedenti sono state introdotte misure di similarita tra regionibasate sul colore (come la EMD, vedi capitolo 2.4.2) e sulla tessitura(vedi capitolo 3.1.3). Queste misure di similarita estraggono un vettore dicaratteristiche dalle regioni interessate e calcolano la distanza tra i due vettoriusando una metrica definita su di essi. Possiamo utilizzare queste metricheanche per misurare la distanza tra un pixel e una regione, basta avere unmetodo per estrarre il vettore di caratteristiche da un singolo pixel. Il metodoimpiegato in questo lavoro e 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 facilita usando i metodi giadiscussi (vedi capitoli 2.4.1 e 3.1.3).

Un discorso a parte lo meritano le metriche basate su misure didiscontinuita, come il contrasto o il gradiente. In questo lavoro, per esempio,e stata implementata una metrica di distanza basata sul gradiente: inquesto caso, come gia accennato in precedenza, si misura la differenza trala caratteristica calcolata per il pixel in esame e per il pixel della regioneconfinante con esso (figura 5.5(b)).

Solitamente per l’algoritmo di growing viene scelta una tra questemetriche; tuttavia, analogamente a quanto osservato per la strategia di sceltadei semi, una sola metrica non basta a cogliere tutte le differenze da un puntodi vista percettivo. Come rilevato nel capitolo 1, sia il colore che la tessiturasono fondamentali per il sistema visivo umano, quindi si e deciso di usare piumisure tramite una combinazione lineare.

dEMD(p,R): distanza EMD tra signature di colore calcolate sulla regione Re 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 regioneR 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 regione

pixel intorno

(a) usando un intornodel pixel

pixel candidato

pixel regione

pixel confinante

(b) usando le caratter-istiche del pixel confi-nante

Figura 5.5: Calcolo della distanza tra pixel e regione

dgrad(p, R): distanza tra il valore del gradiente calcolato con l’operatoreDifference Vector Gradient al pixel candidato p e al pixel confinantedella regione R (vedi figura 5.5(b) e appendice A).

Per una misura di distanza complessiva:

d(p,R) = dEMD(p,R) + dW (p,R) + dgrad(p,R)

I risultati ottenuti, pero, non sono stati quelli attesi: mentre le misurefornite dalle metriche basate sulla signature di colore e dalle metrichebasate sulla differenza di gradiente si sono rivelate confrontabili, le misurericavate dalle metriche basate sulla distanza tra i coefficienti wavelet non losono. I risultati di tutte le misure sono stati moltiplicati per un’oppurtunacostante in modo da rientrare tutti nell’intervallo (0, 1), ma mentre irisultati per le misure dEMD e dgrad sono distribuite in modo quasi uniformelungo l’intervallo, con una concentrazione maggiore nel primo 10-15%, irisultati della misura dW (p,R) sono distribuiti in modo molto diverso, conconcentrazioni piu elevate attorno ad alcuni valori e per di piu in modo moltodipendente dall’immagine.


Si e quindi scelto di ricorrere a una misura di distanza diversa, checomprendesse comunque l’informazione proveniente da tutte e tre le fonti(signature di colore, coefficienti Wavelet e valore del gradiente):

d(p,R) = (dEMD(p, R) + dgrad(p,R))× dtexture(p,R)

dove dtexture e pari a:

dtexture(p,R) =

{Klow se classe(p) = classe(R)Khigh altrimenti

La classe di p e R e calcolata a partire dalla mappa delle texture introdottanel capitolo 3, e le due costanti Klow e Khigh sono calcolate in manieraempirica (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 omogeneita ediscontinuita) sono stati implementati nell’algoritmo proposto come parte diquesto lavoro di tesi.

Uno dei requisiti che sono stati ritenuti necessari per un’utilizzo praticodell’algoritmo e per rendere agevole la sperimentazione e l’utilizzo per lavorifuturi e che questo fosse parametrico e modulare in ogni suo aspetto.Un altro requisito essenziale e l’efficienza: le immagini sono strutturedati di grandi dimensioni, l’eleborazione e molto dispendiosa in terminicomputazionali, quindi e necessario evitare ogni possibile overhead.

Tali requisiti sono stati soddisfatti in massima parte utilizzando laprogrammazione generica e i template.In particolare per che incapsulano le immagini sono tutte parametrichesullo spazio di colore e ogni funzione che manipola immagini e a sua voltaparametrica sul tipo di immagine.Inoltre le funzioni che necessitano di una metrica per compiere la loroelaborazioni sono parametrici sul tipo di metrica. Le metriche sonoimplementate come classi e sono a loro volta indipendenti dallo spazio dicolore utilizzato (vedi diagramma UML in figura 5.6).

5.4 Implementazione 63

Combined

color_tdist_t

CombSaturation

color_tdist_t

L2_Norm

color_tdist_t

CombLuma

color_tdist_t

VectorAngle

Figura 5.6: Il digramma delle classi UML relativo alle classi cheimplementano le metriche

Tutto questo consente di avere lo stesso algoritmo e la stessa implemen-tazione operanti su una qualsiasi combinazione di tipo di immagine, spaziodi colore e metrica e rende possibile aggiungere nuove metriche e nuovi spazidi colore con sforzo minimo.Dovrebbe esser chiaro come questa scelta porti notevoli vantaggi dal puntodi vista della modularita e della estensibilita.Per quanto rigurada l’efficienza, l’inlinig delle funzioni e il polimorfismostatico permesso dei template rendono il codice molto efficiente. Per ulterioridettagli si veda l’Appendice B.

Come supporto all’illustrazione dell’implementazione dell’algoritmo hoincluso i digrammi UML relativi alle classi realizzate per l’algoritmo.In particolare, sono presenti il digramma delle classi relativo alla partecentrale dell’algoritmo (figura 5.7), il diagramma UML delle classi usate perimplementare le metriche di distanza tra colori (figura 5.6) e i diagrammi disequenza relativi alle fasi di selezione delle regioni iniziali (figura 5.8) e digrowing.


image_t

FlatSeedSelector

image_t

WaveletSignature

image_t

GradSignature

image_t

FlatTexSeedSelector

image_tmetric_t

ColorSignature

image_t

EdgeSmallSeedSelectorcolor_tcmp

EMDColorDistance

ColorSiganture<EMDColorDistance>

SignatureBase<image_t>

image_t

RegionFeatures

CandidateSeed

T

ImageRegion

uchar

std::priority_queue<CandidatePixel>

image_t

RegionGrowing

std::priority_queue<CandidateSeed>

std::vector<RegionFeatures>

ImageRegion<uchar>

image_t

CandidatePixel

image_t

SignatureBase

clone()merge()distance()compute_signatu...

<<interface>>

std::vector<SignatureBase*>

Figura 5.7: Il digramma delle classi UML; per questo digramma, piuttostocomplesso, e stata adottata l’estensione basata sul colore proposta per UML2.0. L’utilizzo del colore aggiunge una dimensione al digramma, rendendonepiu facile la comprensione. I colori adottati sono quelli proposti: giallo perle classi centrali, quelle che rivestono un ruolo centrale nel digramma; bluper le classi che rappresentano dati; arancione per i punti di estensibilita;verde per le classi che nel digramma rivestono un ruolo secondari; grigio perle classi provenienti da librerie

Come si vede dal diagramma UML in figura 5.7 la classe piu imporantee la classe SignatureBase. Questa classe, che esporta le funzioni merge,clone, distance e compute signature e l’interfacca usata dall’algoritmoper accedere alle informazioni sulle features di un pixel o di una zona a piulivelli:

Durante la fase di selezione dei semi, per calcolare le features della re-gione coperta da ogni seme, utilizzando il metodo compute signature.

5.4 Implementazione 65

Durante la fase di growing dell’algoritmo, per per calcolare le featuresdei pixel candidati, utilizzando il metodo compute signature, e la lorodistanza (priorita) utilizzando il metodo distance.

Durante la fase finale di merge, per calcolare la distanza tra due regionicandidate per la fusione, utilizzando il metodo distance e la nuovasegnatura della regione in caso di fusione, utilizzando il metodomerge.

Tutti le classi che incapsulano una feature o caratteristica (come laclasse ColorSignature, che rappresenta una segnatura di colore comedescritta nel capitolo 2.4.2, o la classe WaveletSignaure, che rappresentala classe di texture di un pixel o di una regione, utilizzando la mappadescritta nel capitolo 3) sono derivate da SignatureBase, in modo da fornireall’algoritmo la medesima interfaccia. Questo permette all’algoritmo diaccedere alle funzioni di queste classi senza doverne conoscere la classe, masolo l’interfaccia. Aggiungere all’algoritmo un nuovo criterio di omogeneita odiscontinuita, come pure un nuovo tipo di feature per caratterizzare pixel eregioni, diventa cosı molto semplice: e sufficiente ereditare una nuova classeda SignatureBase e implementarne i metodi.

Fornire un nuovo algoritmo per la selezione iniziale dei semi e altrettantosemplice: le classi per la scelta iniziale dei semi (*SeedSelector) imple-mentano un metodo -select- che crea un insieme di classi ImageRegion,rappresentanti i seed iniziali, e le inserisce nelle coda a priorita della classecentrale, la classe RegionGrowing.

E’ interessante notare come questa caratteristica di modularita dell’algo-ritmo, che permette di avere diversi criteri di scelta iniziale dei semi e diusare differenti criteri di growing, renda possibile implementare l’algoritmoJSEG -introdotto nel capitolo 2 e descritto in [33]- in termini dell’algoritmostesso.


:RegionGrowing

:FlatTexSeedSelector

:EdgeSmallSeedSelector

:EMDColorDistance

NewRegion :CandidateSeed

:std::priority_queue<CandidateSeed>

select()

select()

distance()

new

push(NewRegion)

select_seeds( )

NextSeed := top()

Figura 5.8: Il digramma di sequenza UML relativo alle fasi di scelta inizialedei semi

Capitolo 6

Risultati sperimentali

“Vita brevis, ars longa, occasio praeceps, experimentum periculosum,jiudicium difficile”.(La vita e breve, l’arte durarura, l’occasione fuggevole, lo sperimentarepericoloso, il giudicare difficile.)Ippocrate

Esperimenti e test sulla segmentazione sono stati effettuati su vari tipi diimmagini, sia naturali che artificiali. Sebbene il metodo proposto consentadi impostare numerosi parametri per ottimizzare la segmentazione in basea tipi di immagini differenti, si e scelto di condurre tutti gli esperimenticon le stesse soglie e gli stessi parametri. Questa scelta e stata dettatadal fatto che l’algoritmo studiato e stato concepito come un’algoritmo perl’utilizzo generico, adatto ad ogni tipo di immagine, come richiesto in molticampi di ricerca attuale (per esempio il context-based image retrieval, si vedal’introduzione).

Il problema della valutazione degli algoritmi per la segmentazione delleimmagini e forse ancora piu complesso (e sicuramente e maggior causa didibattito) del problema della segmentazione stesso.Non esistono criteri per definire una “buona segmentazione” che sianoindipendenti 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 deglialgoritmi su immagini naturali: tutti i test attuali si basano su immaginiartificiali 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 irisultati della sua applicazione a una serie di immagini di test, confrontandolecon le immagini ottenute con un algoritmo esistente (JSEG, si veda [33]).Sono forniti anche i dati sulla prestazioni, sempre a confronto con leprestazioni ottenute da JSEG. Parte delle immagini usate durante i testsono riportate nelle pagine successive. Di alcune di esse, dove si e ritenutoche siano significativi, sono riportati anche i risultati di alcuni passeggiintermedi effettuati dall’algoritmo proposto. In particolare, le immaginiWavelet map si riferiscono alla mappa delle tessiture introdotta nel capitolo5, le immagini Edge map visualizzano i semi ricavati mediante il metodobasato sulla mappa degli edge (sezione 5.1), le immagini prima del mergee dopo il merge sono le immagini della segmentazione fatta dall’algoritmo.L’immagine Segmentazione e equivalente all’immagine dopo il merge; leregioni sono le stesse, ma sono presentate in modo diverso (con una mappa deicolori principali e tracciando i contorni delle regioni sull’immagine originale,rispettivamente).

La prima caratteristica che si nota esaminando le immagini di test e latendanza 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 e costituito da immagini “standard” per il test dialgoritmi di segmentazione.Nell’immagine baboon (figura 6.1(e)) si nota come l’algoritmo propostodivida in piu zone il pelo del viso, in zone che hanno una predominza dicolore diversa: grigio, verde, giallo, azzurro. Questo risulta in una sovra–segmentazione dal punto di vista semantico, tuttavia le zone riconosciute sonoeffettivamente differenti da un punto di vista percettivo. Le zone piu rilevanti(occhi, muso, naso) sono tutti riconosciuti come elementi distinti. In questocaso 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 unnumero minore di zone.

69

(a) L’immagine di test baboon (b) Wavelet map

(c) Prima del merge (d) Dopo il merge

(e) Segmentazione (algoritmoproposto)

(f) Segmentazione (JSEG)

Figura 6.1: L’immagine di test baboon


Nell’immagine flower garden (figure 6.3(e), 6.3(e)) si nota invece unamigliore segmentazione di JSEG, sia nella definizione del bordo del prato(nella parte bassa dell’immagine), sia per quanto riguarda la divisione inzone: l’algoritmo proposto tende a suddividere le piante di fiori in piu zone,dividendo le zone composte in prevalenza da fiori dalle zone composte inprevalenza da foglie (parte centrale dell’immagine). In compenso, l’algoritmoproposto riesce a isolare la cornice della finestra dal muro di mattoni (asinistra), dove JSEG li considera come una regione unica.Nell’immagine parrots (figure 6.4(e), 6.4(e)) la situazione cambia: stavoltae JSEG a presentare un problema di sovra–segmentazione. L’algoritmoproposto produce un numero inferiore di regioni, specialmente per quel cheriguarda lo sfondo. In compenso, JSEG presenta una migliore definizione deicontorni: si noti il becco del pappagallo giallo, o l’ala destra del pappagallorosso.In immagini di test piu semplici, come house o hand, figure 6.5 e 6.6, lasegmentazione e quasi perfetta: in hand i tre oggetti principali (mano,anello, sfondo con tessitura) vengono riconosciuti con localizzazione dei bordiprecisa, in house vengono rilevati parecchi particolari della casa (finestre,tetto) e il prato e riconosciuto come una regione uniforme e separata. Solonegli alberi si ripresenta la sovra–segmentazione.

Immagine Algoritmo proposto JSEG Dimensionibaboon 1:29 2:41 512× 512hand 0:23 0:22 303× 243flower garden 2:12 4:21 756× 504house 0:14 0:10 205× 192parrots 1:44 4:00 768× 512

Figura 6.2: Le prestazioni dell’algoritmo proposto a confronto con quelle diJSEG

71

(a) L’immagine di test flowergarden

(b) Trasformata Wavelet (c) Wavelet map

(d) Prima del merge (e) Dopo il merge

(f) Segmentazione (algoritmoproposto)

(g) Segmentazione (JSEG)

Figura 6.3: L’immagine di test flower garden


(a) L’immagine di test parrots

(b) Edge regions map (c) Wavelet map

(d) Prima del merge (e) Dopo il merge

(f) Segmentazione (algoritmoproposto)

(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


Oltre a questi test preliminari, i cui risultati sono stati confrontati conJSEG, si sono condotti ulteriori test su immagini di natura diversa, pertestare le capacita dell’algoritmo con immagini di natura differente. Si prendaper esempio la figura 6.7: in quest’immagine si nota come siano rilevati tuttii piccoli particolari, come le finestre, i panni appesi alle finestre, i tendonial livello della strada e le barche nell’acqua. Molti di questi particolari sonoestratti usando la mappa delle texture e la mappa degli edge (figure 6.7(c) e6.7(d)).

Un’ultima immagine su cui vale la pena spendere qualche parola el’immagine newspaper. Questa immagine e stata acquisita con uno scanner,ed e la pagina di un giornale a colori stampato con la tecnica del diethering. Ilproblema nel segmentare queste immagini sta nel fatto che le regioni stampatecon questa tecnica, “uniformi” da un punto di vista percettivo, non hanno inrealta un colore uniforme. Infatti, i punti con cui sono composte le immagininon solo hanno intensita differente, come accade nella maggior parte delletessiture, ma anche tinta diversa. Inoltre, bisogna distinguere queste zonedalle zone di testo: e importante ai fini dell’elaborazione del documentonelle fasi successive che i caratteri stampati siano conservati (riconoscendolicome regioni distinte), ma il diethering sia rimosso (riconoscendo le regionistampate con questa tecnica come uniformi). Questo e reso possibile grazieai due metodi di selezione dei seed implementati: il metodo delle “piastrelle”(figura 6.8(b)) consente di individuare le regioni con diethering, mentre ilmetodo basato sul negativo della mappa degli edge (figura 6.8(c)) consentedi 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


(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)


(a) flowers2 (b) Prima del merge


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


(a) geneva1 (b) Prima del merge


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 varieconclusioni

7.1.1 Il framework

Nell’implementare l’algoritmo di region growing basato sulle tessiture e statoelaborato e sviluppato un framework efficiente e riusabile, adatto all’utilizzocome base di partenza per la sperimentazione e l’implementazione di variantidell’algoritmo.

7.1.2 Il colore

Le prove sono state condotte utilizzando RGB come spazio di colore e ilVector Angle combinato con la distanza euclidea sulla base dell’informazionedi luminosita come metrica.Alcuni esperimenti condotti sulle prime implementazioni dell’algoritmohanno mostrato come questa metrica rappresenti il miglior compromesso:come previsto nel capitolo 2 il solo utilizzo della distanza euclidea porta arisultati percettivamente non corretti ed a un alto numero di falsi positividovuti alle ombre.D’altra parte, l’uso del Vector Angle da solo si rivela problematico inimmagini naturali, dove zone con bassa luminosita o saturazione fanno

82 Conclusioni

emergere l’instabilita numerica di questa metrica per certi valori. Usando unacombinazione delle due metriche con trade-off dato dalla luminosita risolvecompletamente il secondo problema e in maniera parziale anche il primo.Putroppo, cosı facendo l’algoritmo ritorna ad essere piuttosto sensibile alleombre, 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 grazieall’analisi wavelet, con le informazioni sul colore, ricavate dalla signaturedi una zona, si e rivelato il compito piu arduo di questo lavoro di tesi. Irisultati iniziali basati sulla distanza tra gli istogrammi dei coefficienti wavelet(vedi capitolo 3) sono stati deludenti: le due metriche, quella per le tessituree quella per il colore, fornivano risultati distribuiti in maniera diversa neirispettivi intervalli, cosa che ne rende impossibile il confronto. Cosı si eoptato per una piu semplice, ma efficace, suddivisione delle zone in pocheclassi di texture.

7.1.4 Selezione dei candidati

Il sistema di selezione dei candidati tramite coda di priorita possiede lacaratteristica di rendere solo un pixel disponibile per il growing ad ogniiterazione. Questo rende il processo growing piu ordinato e prevedibile,rendendo la localizzazione degli edge piu precisa.

7.1.5 Selezione dei semi

La selezione dei semi usando criteri multipli, come il negativo della mappadegli edge, permette di avere un numero maggiore di regioni di partenza adisposizione. Questo, se da un lato permette di evitare il problema dellasottosegmentazione e la perdita di dettagli significativi, dall’altro favoriscela sovrasegmentazione. L’algoritmo proposto tende infatti a generare unnumero elevato di regioni; spesso questa caratteristica e desiderabile rispettoalla sottosegmentazione, e puo essere mitigata modificando opportunamentei parametri. Tuttavia il problema resta. Tra le possibili estensioni a questatesi, a mio avviso la piu importante riguarda lo studio di un algoritmo dimerging piu efficiente che permetta di risolvere questo problema.

7.2 Lavori futuri 83

7.2 Lavori futuri

7.2.1 Miglioramenti dell’algoritmo

Vanno ancora condotti esperimenti per impostare in maniera piu precisai parametri e diminuire l’effetto di sovra-segmentazione che si riscontra inmolte immagini.Questo effetto, molto probabilmente, e causato anche dall’uso di un algoritmodi merging non ottimale, nell’ultima fase del procedimento. Lo studioe l’implementazione di un algoritmo che sfrutti in modo piu completo leinformazioni a dispozione (area, signature, classe di tessitura della zona,nonche seed selector di provenienza) e necessario.

Le performance dell’algoritmo, sebbene soddisfacenti per gli scopi attualie superiori a quelle di JSEG (vedi capitolo 6), possono essere migliorate,in particolar modo per quanto riguarda il calcolo della EMD, che risultapesare per circa il 50% sul tempo totale di computazione (dati del profileralla mano).

7.2.2 Utilizzi dell’algoritmo

Visto il gran numero di features e caratteristiche importanti dal punto di vistapercettivo estratte dall’algoritmo, un suo uso in sistemi di image retrievalsembra indicato.La segmentazione, la descrizione delle caratteristiche di colore per ogni zona,la mappa delle classi di tessitura, sono tutte features molto importanti perstabilire la corrispondenza tra immagini e forniscono una buona base dipartenza 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 siappoggiano sulla mappa del gradiente dell’immagine e sulla mappa degli edgederivata da quest’ultima. Per il calcolo del gradiente di un’immagine a colorie 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 gradientemassimo attraverso il pixel centrale.

1 2 3

4

567

8 X

Figura A.1: Gli indici dei pixel in un intorno 3x3

GDV = maxi=1...4

{D(~vi, ~vi+4}

dove i rappresenta una tra le prime quattro (tra le otto possibili) posizioniattorno 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 ottieneuna 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 delgradiente che devono essere binarizzate per ottenere una mappa degli edge,usando una soglia: data l’immagine a scala di grigio del gradiente, bisognastabilire un valore di soglia che funga da spartiacque; al di sopra di questovalore il pixel appartiene a un edge, al di sotto no.Una soluzione e quella di chiedere all’utente di fornire un valore per la soglia:questo e possibile quando si ha a che fare con sistemi interattivi, tuttaviaspesso e desiderabile (e in sistemi automatici necessario) fornire una sogliaautomatica e adattiva, che cioe sia scelta in modo ottimo da un algoritmosulla base della mappa del gradiente e del contenuto dell’immagine.Come parte del lavoro svolto durante la preparazione di questa tesi, e statoimplementato un metodo basato sulla massimizzazione dell’entropia.Questa tecnica e usata spesso per il problema della classificazione dei dati indue classi. Il problema consiste nel dividere un insieme di valori in due partifacendo in modo che l’errore sia minimo.Per assicurare cio, si cerca di dividere i dati in due insiemi in modo chel’entropia totale (la somma dell’entropia delle due partizioni) sia massima.Brevemente: poniamo che il gradiente (l’intensita di un edge) sia compresonell’intervallo [0,M ] e che nell’immagine ci siamo fi pixels che hanno intensitauguale a i, con i ∈ [0,M ]. Data una certa soglia T , si puo definire ladistribuzione di probabilita per le due classi (pixel di edge (e), pixel nondi edge (n)).Visto che un pixel non puo essere sia di edge che no, le due distribuzioni sonoindipendenti.Quindi la probabilita per i pixel non di edge data la intensita i puo esseredefinita come:

Pn(i) =fi∑T

h=0 fh

, 0 ≤ i ≤ T (A.1)

86 Edge detection

analogamente la probabilita per i pixel di edge data la intensita i e definitacome:

Pe(i) =fi∑M

h=T+1 fh

, T + 1 ≤ i ≤ M (A.2)

Ora che abbiamo la probabilita ci e possibile definire l’entropia per le dueclassi di pixel:

Hn(T ) = −T∑

i=0

Pn(i) log Pn(i), 0 ≤ i ≤ T (A.3)

He(T ) = −M∑

i=T+1

Pn(i) log Pn(i), 0 ≤ i ≤ T (A.4)

E quindi la soglia ottimale T per la classificazione di un pixel come di edgeo di non edge e quella che soddisfa la seguente funzione:

H(T ) = maxT=0...M

{Hn(T ) + He(T )} (A.5)

Cercare il massimo globale di questa funzione ha complessita O(M2), maesiste un algoritmo veloce che richiede tempo lineare. Quest’ultimo algoritmoe 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 basatisull’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 funzioniche 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 didato utilizzato. Si ha invece il polimorfismo quando il linguaggio adoperatoconsente di scrivere funzioni che possono operare su un numero infinito ditipi, purche questi rispettino alcune proprieta.Si noti che in questa definizione rientrano sia il polimorfismo per inclusione(quello classico nella OOP) che il polimorfimo parametrico (quello dellaprogrammazione generica).Il C++ permette di programmare usando entrambi i paradigmi. Il primoviene implementato tramite le funzioni virtuali, e viene anche chiamatopolimorfismo 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 puristidell’OOP considerano migliore il primo approccio [21], ma sulla scia dell’STL(la libreria standard del C++) sono nate molte librerie che sfruttano laprogrammazione generica. In questo lavoro e stata usata la programmazionegenerica (e quindi il polimorfismo statico) per svariate ragioni, tra cuiconviene sottolinearne una: l’efficienza.Il principale svantaggio delle funzioni virtuali e il loro costo: la perdita di

88 Polimorfismo statico vs. polimorfismo dinamico

efficienza dovuta alla chiamata di una funzione virtuale (contro la chiamataa una funzione normale o parametrica) e del 20-30%.Questo overhead e dovuto a due cause: la chiamata tramite v-table el’impossibilita di fare l’inlining delle funzioni virtuali.Quando nel codice si presenta una chiamata a funzione virtuale, il compi-latore non sa (e non puo sapere, visto che per fortuna ai compilatori C++,di per se gia pittosto complessi, non viene richiesto di fare un’analisi staticadel flusso del codice) che funzione sara chiamata a run-time, perche non saa quale classe appartiene l’oggetto su cui e 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) verra chiamata la f() di C o di B? Il binding e sconosciuto a compile-time, 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 ognifunzione virtuale presente nella classe. Questa tabella di puntatori a funzioneviene detta v-table.Purtroppo, questo significa che invece di una semplice istruzione assemblercall il compilatore deve generare il codice per recuperare il puntatore e poifare la chiamata, aggiungendo due accessi alla memoria.Inoltre la mancanza di conoscenza a compile time della funzione che verrainvocata rende impossibile farne l’inlining.Usando i template, invece, il compilatore genera del codice eseguibile diversoper ogni tipo di dato su cui viene invocata la funzione. Questo permette diinserire direttamente nel codice compilato l’indirizzo della funzione, oppureil 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 puntidi origine a n punti di destinazione lungo m ∗ n percorsi diretti dall’originealla destinazione.Ognuno degli m punti di origine (fornitori) ha a disposizione merci in quantitaa1, ..., am e ognuno degli n punti di destinazione (consumatori) ha domandapari 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 consumatorie uguale alla somma delle merci rese disponibili dai fornitori (

∑mi=1 ai =∑n

j=1 bj), e il problema e quindi detto bilanciato.Per procedere con l’algoritmo, abbiamo bisogno di una matrice di appoggioi ∗ j, che denotiamo con x, che conterra via via la quantita di merce che ilfornitore i-esimo deve consegnare al destinatario j-esimo.

Questo e un problema di ottimizzazione, e l’algoritmo e basato sullatecnica della ricerca locale. E’ quindi necessario cercare una soluzione inizialepercorribile, che verra poi ottimizzata dalla seconda fase dell’algoritmo.

91

La scelta di una buona soluzione iniziale e desiderabile, in quanto consentedi diminuire il numero di passi necessari per trovare l’ottimo nella secondafase dell’algoritmo.Per questo lavoro si e scelto di implementare una semplice tecnica greedy.

Prima di iniziare a descrivere l’algoritmo, e necessario intrudurre duetermini: si dicono celle di base le celle della matrice della soluzione parzialex che hanno un flusso positivo -che hanno cioe della merce allocata lungo quelpercorso-, mentre si dicono celle non di base quello il cui flusso e attualmentepari a zero.L’algoritmo procede come segue:

La prima fase consiste nel costruire una soluzione iniziale percorribileusando una tecnica greedy:

1. se la porzione ancora valida dell’array consiste di una singola rigao 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 piu basso, poniamoche 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 colonnaj-esima (se min(ai, bj) = bj): questa non sara piu consideratanella scelta della variabile al passo 2;

• si riducono la domanda bj e l’offerta ai di min(ai, bj); sinoti che una delle due variabili (quella sulla riga/colonnacancellata) verra posta a zero;

La seconda fase consiste nel determinare una variabile entrante tra le cellenon di base. Se tutte le celle non di base soddisfano la condizione diottimalita, ci si ferma; altrimenti si va alla terza fase:

92 L’algoritmo del trasporto

14 13 12 11 21

100017 23 16 22 15

150019 18 20 23 24

2000

500 1500 800 1000 700

14 13 12 11 21

1000 X17 23 16 22 15

150019 18 20 23 24

2000

500 1500 800 0 700

14 13 12 11 21

1000 X17 23 16 22 15

700 80019 18 20 23 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 i-esima e alla colonna j-esima della matrice della soluzione parzialex;

2. si calcolano ui e vj; per ogni cella di base xij deve valere la relazioneui + vj = cij, quindi:

• si pone ui = 0;

• si determinano di conseguenza i restanti ui e vj risolvendo unsistema 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 cij = ui + vj − cij;

4. si seleziona come variabile entrante la cella non di base xij con cij

massimo;

La terza fase consiste nel determinare una variabile uscente tra le celledi base attualmente nella soluzione, e di trovare una nuova soluzione.Quindi si torna alla seconda fase.Prima di procedere in dettaglio con la descrizione e necessrio dare unadefinizione:Una sequenza ordinata di celle distinte e detta un ciclo se:

- Ogni coppia di celle consecutive giace nella stessa riga o nellastessa colonna.

- Non ci sono tre celle consecutive nella stessa riga o colonna.

- L’ultima cella della sequanza ha una riga o una colonna in comunecon la prima cella della sequenza (figura C.2).

94 L’algoritmo del trasporto

14 13 12 11 21

500 500

17 23 16 22 15

1000 500

19 18 20 23 24

300 1000 700

14 13 12 11 21

500 500

17 23 16 22 15

1000 500

19 18 20 23 24

X 300 1000 700

entrante uscente

14 13 12 11 21

-300 +300

500 500

17 23 16 22 15

-300 +300

1000 500

19 18 20 23 24

+300 -300

X 300 1000 700

14 13 12 11 21

200 800

17 23 16 22 15

700 800

19 18 20 23 24

300 1000 700

Figura C.3: Uno scambio variabile uscente-entrante

1. si costruisce un ciclo costituito dalla variabile entrante scelta nellaseconda fase e da sole celle di base (Nota: si puo dimostrare cheper ogni cella non di base -come la variabile d’entrata- si puocostruire 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 entranteuguale 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 ilflusso 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 spazioRGB, viste le sue proprieta e i buoni risultati conseguiti.Uno degli svantaggi derivanti dall’uso di questa metrica sono le sue perfor-mance, indubbiamente inferiori rispetto a quelle della piu semplice distanzaeuclidea.Il metodo, infatti, richiede una buona mole di calcoli, tra cui tre operazionidi estrazione di radice quadrata. Visto che alcune delle operazioni (somma,elevamento al quadrato...) vanno effettuate su tutte e tre le componenti deidue colori di cui si sta misuerando la distanza, si e pensato di aumentare leperformance usando istruzioni SIMD (Single Instruction Multiple Data).Questo tipo di istruzioni, quando sono supportate dal processore, consentonodi effettuare la stessa operazione su un blocco di dati al costo di una singolaistruzione, aumentando notevolmente il parallelismo.Sulle architetture Intel a 32 bit (IA-32) sono presenti, a partire dal processorePentium 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 e stato possibile aumentare leperformance 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] = (float)a.C1();



acf1[3] = (float)0.0f;

acf2[0] = (float)b.C1();



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. Mojsilovic. Wavelet Domain Features fo TextureDescription, Classification and Replicability Analysis. In IEEEInternational Conference on Image Processing (ICIP), volume 4, pages440–444, 1999.

[2] B.A.Wandell. Foundations of Vision. Sinauer Assocites Inc., 1995.

[3] S. Boker. The representation of color metrics and mappings in perceptualcolor space. Paper, Department of Psychology, The University ofVirginia, Charlottesville, Virginia 22903, 1994.

[4] T. Carron and P. Lambert. Color Edge Detector Using Jointly Hue,Saturation, and Intensity. In International Conference on ImageProcessing, volume 3, pages 977–98, 1994.

[5] J. Chen, T. Pappas, A. Mojsilovic, and B. Rogowitz. Adaptive imagesegmentation based on color and texture. In International ConferenceImage 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. ComputerVision, Graphics and Image Processing: Graphical Models and ImageProcessing, 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. PatternRecognition, 29:1277–1294, 1993.

100 BIBLIOGRAFIA

[10] J. Fan, D. Yau, A. Elmagarmid, and W. Aref. Automatic ImageSegmentation by Integrating Color-Edge Extraction and Seeded RegionGrowing. IEEE Trans. On Image Processing, 10(10):1454–1456, 2001.

[11] Foley, V. Dam, Feiner, and Hughes. Computer Graphics, Principles AndPractice, 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. Addison-Wesley, 1992.

[14] A. Graps. An introduction to Wavelet. IEEE Computational Scienceand 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. Intel ArchitectureOptimization: Reference manual, 1999.

[17] Intel Corporation, Mt. Prospect, Illinois. IA-32 Intel ArchitectureSoftware Developer’s Manual Volume 2: Instruction set reference, 2002.

[18] U. Kthe. Primary Image Segmentation. In DAGM-Symposium, pages554–561, Berlin, Deutschland, 1995.

[19] A. Lou. Texture Images Classification Using Tree-structuredWavelet Decomposition. Project technical report, Computer ScienceDepartment, 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 Distanceas 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. IEEETransactions on Systems, Man, and Cybernetics, (8):237–247, 1978.

[25] S.Livens and P. et al. Wavelet-based Texture Analysis. InternationalJournal Computer Science and Information management, December1997.

[26] N. Suematsu and Y. I. et al. Region-Based Image Retrieval usingWavelet Transform. In 15th International Conference on VisionInterface, 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. Prentice HallInternational, 1997.

[29] A. Wah. A General Multiscale Scheme for Unsupervised ImageSegmantation. University of Cambridge, 2000.

[30] S. Wesolkowski. Color Image Edge Detection and Segmentation: AComparison of the Vector Angle and the Euclidean Distance ColorSimilarity Measures. Systems Design Engineering, University ofWaterloo, Canada, 1999.

[31] S. Wesolkowski and E.Jernigan. Color Edge Detection in RGB UsingJointly Euclidean Distance And Vector Angle. In Vision Interface ’99,Trois-Rivieres, Canada, 1999.

[32] S. Wesolkowski and P. Feiguth. Color Image Segmentation Using a NewRegion 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 Segmentationof 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 DigitalColor Image Reproduction. Journal of the Society for InformationDisplay, 5(1):61–63, 1997.

UNIVERSITA DEGLI STUDI DI TRENTO` - tev-static.fbk.eu · Grazie a loro adesso non sono piu` cos`ı...

Documents

Transcript of UNIVERSITA DEGLI STUDI DI TRENTO` - tev-static.fbk.eu · Grazie a loro adesso non sono piu` cos`ı...