Segmentazione automatica di immagini di mosaici tramite tecniche di calcolo evoluzionistico

UNIVERSITÀ DEGLI STUDI DI TRIESTEDipartimento di Ingegneria e Architettura

Corso di Laurea in Ingegneria Informatica

Tesi di Laurea Magistralein

PROGRAMMAZIONE WEB

Segmentazione automatica diimmagini di mosaici tramite

tecniche di calcolo evoluzionistico

LAUREANDO RELATORE

Nicola TIMEUS prof. Eric MEDVET

CORRELATORI

prof. Gianfranco FENUprof. Felice Andrea PELLEGRINO

Anno Accademico 2014/2015

Alla mia famiglia, a Eleonora e a tutti coloro i quali mi hanno sostenutodurante la mia carriera universitaria e nello svolgimento di questo

lavoro

Indice

1 Introduzione 11.1 Descrizione del problema . . . . . . . . . . . . . . . . . . . 11.2 Motivazioni . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Algoritmi genetici 32.1 Genotipo . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Operatori genetici . . . . . . . . . . . . . . . . . . . . . . 42.3 Funzione di fitness . . . . . . . . . . . . . . . . . . . . . . 42.4 Struttura di un algoritmo genetico . . . . . . . . . . . . . 5

3 Descrizione del metodo 73.1 Descrizione del genotipo . . . . . . . . . . . . . . . . . . . 7

3.1.1 Formato basato su rettangoli . . . . . . . . . . . . 83.1.2 Formato basato su quadrilateri convessi . . . . . . 9

3.2 Funzione di fitness . . . . . . . . . . . . . . . . . . . . . . 103.3 Inizializzazione della griglia . . . . . . . . . . . . . . . . . 11

3.3.1 Inizializzazione uniforme . . . . . . . . . . . . . . . 113.3.2 Inizializzazione basata su preprocessing . . . . . . 123.3.3 Differenze di gaussiane . . . . . . . . . . . . . . . . 133.3.4 Scelta dei blobs . . . . . . . . . . . . . . . . . . . . 16

3.4 Descrizione dell’algoritmo genetico . . . . . . . . . . . . . 173.4.1 Operatore di crossover uniforme . . . . . . . . . . . 193.4.2 Operatore di mutazione uniforme . . . . . . . . . . 193.4.3 Operatore di mutazione gaussiano . . . . . . . . . 19

3.5 Scelta delle segmentazioni risultanti . . . . . . . . . . . . . 203.6 Gestione delle intersezioni . . . . . . . . . . . . . . . . . . 20

3.6.1 Variabili decisionali . . . . . . . . . . . . . . . . . . 213.6.2 Funzione obiettivo . . . . . . . . . . . . . . . . . . 213.6.3 Vincoli . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.7 Implementazione ed ottimizzazioni . . . . . . . . . . . . . 233.7.1 Strumenti utilizzati . . . . . . . . . . . . . . . . . . 233.7.2 Working sets . . . . . . . . . . . . . . . . . . . . . 23

v

INDICE vi

3.7.3 Manipolazione dei poligoni . . . . . . . . . . . . . 233.7.4 Manipolazione dei pixel . . . . . . . . . . . . . . . 243.7.5 Caching . . . . . . . . . . . . . . . . . . . . . . . . 25

4 Procedura sperimentale 274.1 Metriche di valutazione . . . . . . . . . . . . . . . . . . . . 27

4.1.1 Errore sul conteggio . . . . . . . . . . . . . . . . . 274.1.2 Precision . . . . . . . . . . . . . . . . . . . . . . . 284.1.3 Recall . . . . . . . . . . . . . . . . . . . . . . . . . 284.1.4 F-Measure . . . . . . . . . . . . . . . . . . . . . . . 29

4.2 Obiettivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.3 Organizzazione . . . . . . . . . . . . . . . . . . . . . . . . 30

4.3.1 Random seed . . . . . . . . . . . . . . . . . . . . . 32

5 Risultati 335.1 Efficacia dell’algoritmo . . . . . . . . . . . . . . . . . . . . 33

5.1.1 Andamento della funzione di fitness . . . . . . . . 335.1.2 Correlazione tra funzione di fitness e metriche di

valutazione . . . . . . . . . . . . . . . . . . . . . . 355.2 Modalità di evoluzione . . . . . . . . . . . . . . . . . . . . 385.3 Gestione delle intersezioni . . . . . . . . . . . . . . . . . . 395.4 Dimensione della popolazione . . . . . . . . . . . . . . . . 405.5 Fronte di Pareto . . . . . . . . . . . . . . . . . . . . . . . 415.6 Formato del genotipo . . . . . . . . . . . . . . . . . . . . . 435.7 Inizializzazione della griglia . . . . . . . . . . . . . . . . . 445.8 Confronto con TOS . . . . . . . . . . . . . . . . . . . . . . 45

5.8.1 Confronto attraverso le metriche di valutazione . . 455.8.2 Confronto empirico . . . . . . . . . . . . . . . . . . 46

6 Conclusioni e sviluppi futuri 49

Capitolo 1

Introduzione

1.1 Descrizione del problema

Questa tesi affronta il problema della segmentazione di un mosaico, il checonsiste nel ricavare delle informazioni strutturate ed esplicite riguardo alnumero, la posizione e la forma dei tasselli che lo compongono a partireda un’immagine digitale dello stesso.

Questo problema viene tradizionalmente risolto in maniera manualetracciando il contorno di ogni tassello su un foglio di carta semitrasparenteapplicato sopra il mosaico, operazione che necessita di molto tempo peressere svolta.

Avere a disposizione una rappresentazione digitale ottenuta in modoautomatico permette di risparmiare il tempo necessario ad effettuare lasegmentazione manuale e presenta diversi vantaggi. Ad esempio può es-sere utile agli archeologi, accademici e restauratori interessati allo studio,confronto e preservazione dei mosaici consentendo loro di avvalersi dellenuove tecnologie per svolgere al meglio il propro lavoro.

1.2 Motivazioni

In un lavoro precedente [3] sono stati confrontati attraverso delle metri-che non soggettive vari algoritmi presenti in letteratura utili a risolverequesto problema, tra cui diversi algoritmi general-purpose recenti per lasegmentazione di immagini e TOS [1] che per quanto a noi noto risultal’unico orientato esplicitamente alla segmentazione di un mosaico.

Dal lavoro sopra citato è emerso che quest’ultimo risulta migliore deglialtri anche se in maniera non significativa, lasciando il problema soloparzialmente risolto. Attraverso questa tesi si è sperimentato un nuovoapproccio alla segmentazione automatica dei mosaici basato su tecnichedi calcolo evoluzionistico.

1

Capitolo 2

Algoritmi genetici

Si descrivono ora brevemente i principali aspetti che caratterizzano ilcalcolo evoluzionistico e gli algoritmi genetici.

Gli algoritmi genetici sono degli algoritmi di ottimizzazione che pren-dono spunto dal mondo della biologia, in particolare dalle teorie sull’evo-luzione e dal principio della selezione naturale.

Secondo tali teorie in natura l’evoluzione di una specie avviene gra-zie al fatto che sono gli individui migliori appartenenti ad essa ad averemaggiore probabilità di riprodursi e trasmettere quindi il loro patrimo-nio genetico alle generazioni successive. Per individui migliori si intendequelli che hanno sviluppato delle caratteristiche che garantiscono loro unbuon grado di adattamento all’ambiente circostante. Lo sviluppo di nuo-ve caratteristiche negli individui di una specie avviene tramite mutazionicasuali del patrimonio genetico, tali caratteristiche possono essere sia fa-vorevoli che sfavorevoli. Il meccanismo della selezione naturale fa si chele prime vengano trasmesse alla generazione successiva con probabilitàmaggiore rispetto alle seconde.

Gli algoritmi genetici applicano i principi sopra descritti ai problemidi ottimizzazione, il loro funzionamento si basa infatti sulla generazionecasuale di un insieme di soluzioni e la successiva evoluzione dello stessofino all’ottenimento di soluzioni soddisfacenti per il problema considera-to. L’insieme sopra citato viene detto popolazione e le soluzioni ad essoappartenenti individui.

Ciascun individuo è contraddistinto dal relativo fenotipo e genotipo.Il primo è l’insieme delle caratteristiche e proprietà esternamente visibiliche costituiscono l’individuo, il secondo è invece un insieme di parame-tri che identifica univocamente un particolare fenotipo ed è soggetto amanipolazione da parte degli operatori tipici del calcolo evoluzionisticoquali la mutazione e il crossover. Questi operatori sono ispirati dalle ri-spettive controparti presenti nel mondo della genetica. Un altro aspetto

3

2. Algoritmi genetici 4

fondamentale è quello di poter definire una funzione di confronto tra dueindividui che consenta di individuare quello che rappresenta una soluzio-ne migliore per il problema in questione, tale funzione si dice funzione difitness.

Vengono ora descritti formalmente i concetti precedentemente intro-dotti.

2.1 Genotipo

Il genotipo di un individuo è identificato dal suo cromosoma C = {g1, . . . , gn}che rappresenta una sequenza ordinata di geni, ogni gene è un vettore diparamenti gi = (pi1, . . . , piki) con pij ∈ Aij , dove Aij è un generico insie-me. Ogni gene codifica un insieme di caratteristiche correlate del fenotipodi un individuo. La definizione del numero di geni presenti nel cromoso-ma, del numero di parametri pij e del significato degli stessi dipende dalparticolare problema ed è a discrezione dello sviluppatore dell’algoritmo.

2.2 Operatori genetici

La generazione di una nuova popolazione a partire da quella preesistenteviene effettuata mediante i seguenti operatori finalizzati alla manipola-zione del cromosoma degli individui.

Mutazione L’operatore di mutazione effettua la generazione di un nuovoindividuo figlio a partire da un genitore mediante la sostituzione diuno o più parametri pij presenti nel cromosoma del primo con unvalore casuale appartenente ad Aij .

Crossover L’operatore di crossover effettua la generazione di uno o piùindividui figli a partire da due o più genitori effettuando una ri-combinazione dei parametri corrispondenti presenti nel genotipo.I cromosomi dei figli sono caratterizzati dalla seguente proprietà:∀fij∃k : pkij = fij , dove fij rappresenta un generico parametro diuno dei figli e pkij rappresenta il valore del corrispondente parametrodel genitore k-esimo.

2.3 Funzione di fitness

La funzione di fitness ha il compito di esprimere quantitativamente la bon-tà di un determinato individuo come soluzione del problema in questione,tale funzione riceve in ingresso il fenotipo dell’individuo considerato ed

5 Struttura di un algoritmo genetico

ha valori in Rn. Se n = 1 tale funzione rende possibile ordinare la popo-lazione secondo il grado di ottimalità degli individui identificando anchequello migliore. Se n > 1 si è in presenza di un problema di ottimizza-zione multi obiettivo e l’ordinamento precedentemente descritto presentadelle complicazioni in più rispetto al caso unidimensionale. In questo casoil problema può essere affrontato ad esempio tramite l’ordinamento nondominato per fronti di Pareto descritto nel seguito.

2.4 Struttura di un algoritmo genetico

Una volta ottenuto un modello delle soluzioni di un problema in terminidi genotipo, implementati in modo opportuno gli operatori di mutazio-ne e crossover ed individuata una funzione di fitness l’evoluzione dellapopolazione avviene nel modo seguente:

1. Inizializzazione della popolazione.

2. Applicazione della funzione di fitness alla popolazione.

3. Ordinamento degli individui rispetto al loro grado di ottimalità.

4. Se gli individui ottenuti sono soddisfacenti l’algoritmo termina.

5. Generazione di una nuova popolazione a partire da quella pre-cedente applicando crossover e mutazione agli individui miglioriindividuati al punto precedente.

6. Passaggio al punto 2.

Capitolo 3

Descrizione del metodo

Il problema della segmentazione di un mosaico è stato affrontato medianteun algoritmo di ottimizzazione genetica multi obiettivo, si fornisce ora unadefinizione formale di segmentazione e si descrivono i vari aspetti specificiche caratterizzano tale algoritmo.

Definizione 1 Per segmentazione si intende un insieme S di insiemi dipixel appartenenti all’immagine originale. S è ottima se e solo se perogni tassello contenuto nell’immagine di input è presente uno ed uno soloinseme I ∈ S che contiene tutti e soli i pixel appartenenti al tassellostesso.

3.1 Descrizione del genotipo

Ogni individuo appartenente alla popolazione presenta un genotipo attoa codificare il relativo fenotipo, ossia una segmentazione S.

Invece di ottenere una rappresentazione di S direttamente dalla de-finizione 1 si è scelto di imporre ulteriori restrizioni tenendo conto del-le caratteristiche specifiche del problema al fine di ridurre lo spazio diricerca.

In particolare si impone che ogni I ∈ S venga identificato da un po-ligono convesso, un pixel appartiene ad I se questo è contenuto nellaregione dell’immagine originale identificata da tale poligono. Tale ap-prossimazione è ragionevole se si considera la forma tipica dei tasselli diun mosaico. Il requisito della convessità semplifica inoltre le operazionidi manipolazione dei tasselli e consente di introdurre delle ottimizzazionifinalizzate a ridurre il tempo di esecuzione.

Il cromosoma di ogni individuo è composto da un insieme di genicodificanti un poligono, il generico gene i-esimo gi è un vettore avente laseguente forma:

gi = (pi1, . . . , pik), pij ∈ Pij (3.1)

7

3. Descrizione del metodo 8

dove pij è un numero reale rappresentato mediante la codifica floatingpoint caratterizzante uno specifico parametro del poligono. Ciascun pijappartiene inoltre ad un intervallo Pij = [pmin

ij , pmaxij ] ⊂ R, definito in fase

di inizializzazione come illustrato in seguito. Gli operatori di mutazionee crossover devono garantire che la condizione pij ∈ Pij rimanga semprevalida nel corso dell’evoluzione.

Scopo degli intervalli di validità è quello di imporre che ciascun po-ligono possa essere collocato in una porzione circoscritta dell’immaginecontenente la posizione iniziale e che le sue dimensioni non discostinoeccessivamente da un valore iniziale.

Nel corso del lavoro sono stati sperimentati diversi formati per il geno-tipo, ciascuno dei quali identifica il numero e il significato dei parametripij e possiede un diverso grado di espressività. Ognuno di questi formatidefinisce una famiglia alla quale i poligoni devono appartenere e forni-sce alcune specifiche utilizzate dagli operatori di crossover e mutazioneattraverso gli intervalli di validità Pij .

A livello di codice i diversi formati sono stati implementati median-te specifiche classi ciascuna delle quali implementa una stessa interfac-cia. Tra le operazioni più importanti che queste classi devono svolgeretroviamo le seguenti:

• Generare la configurazione iniziale del gene i-esimo nel modo piùappropriato a partire dai parametri cxi, cyi e di forniti dal codiceresponsabile dell’inizializzazione della griglia. I primi due sono lecoordinate del baricentro del poligono ed il terzo va inteso comemetà lato del tassello ipotizzando che questo abbia forma quadrata.

• Definire gli intervalli di validità Pij .

• Tradurre i geni codificanti i poligoni in una rappresentazione indi-pendente dal particolare formato in uso che viene utilizzata dallealtre parti del codice, ossia una lista ordinata delle coordinate (x, y)dei vertici del poligono.

Vengono ora illustrati i due formati impiegati nella fase sperimentaledi raccolta dei risultati.

3.1.1 Formato basato su rettangoli

Questo formato prevede che i poligoni siano dei quadrati disposti ini-zialmente con i lati paralleli agli assi del sistema di riferimento ai qualisi consente di variare tramite crossover e mutazione posizione, rotazionee lunghezza di ciascuna coppia di lati paralleli. In particolare il genei-esimo ha la seguente forma:

gi = (xi, yi, φi, l1i, l2i) (3.2)

9 Descrizione del genotipo

dove xi e yi sono le coordinate del baricentro del rettangolo, φi rappre-senta l’angolo di rotazione rispetto alla configurazione iniziale ed l1i edl2i rappresentano la lunghezza di ciascuna coppia di lati paralleli.

Per quanto riguarda gli intervalli di validità dei parametri si imponeche:

xi ∈ [cxi − di, cyi + di] (3.3)yi ∈ [cxi − di, cyi + di] (3.4)φi ∈ [−π/2, π/2] (3.5)

l1i, l21 ∈ [di, 4di] (3.6)

Dove cxi, cyi e di sono i parametri definiti in fase di inizializzazione.

3.1.2 Formato basato su quadrilateri convessi

Questo formato prevede che a partire da un quadrato con i lati parallelial sistema di riferimento possa essere modificata la posizione del verticej-esimo mediante la somma di un offset (dxj , dyj) rispetto alla posizionedi partenza, con max(dxj , dyj) ≤ k = l/4, dove l è la lunghezza del lato.Si può dimostrare che così facendo si ottengono sempre poligoni convessie che l/4 è il massimo valore di k che conserva tale proprietà. Al terminedelle operazioni di perturbazione sopra descritte il poligono può essereruotato e/o traslato.

La struttura dei geni gi è la seguente:

gi = (xi, yi, φi, dx1i, dy1i, . . . , dx4i, dy4i) (3.7)

con

xi ∈ [cxi − di, cxi + di] (3.8)yi ∈ [cyi − di, cxi + di] (3.9)φi ∈ [−π, π] (3.10)

dx1i, dy1i, . . . , dx4i, dy4i ∈ [−1, 1] (3.11)

La generazione di un poligono a partire da un gene gi avviene nel modoseguente:

1. Si inizializzano i vertici del quadrato nel modo seguente:

v1i = (−di,−di)v2i = (di,−di)v3i = (di, di)

v4i = (−di, di)


2. Si somma al vertice k-esimo il vettore (dxki, dyki) · di/2.

3. Si ruota la configurazione risultante di φi radianti rispetto all’ori-gine in senso orario.

4. Si somma a ciascun vertice il vettore (xi + cxi, yi + cyi).

3.2 Funzione di fitness

Per effettuare l’ottimizzazione genetica si è impiegata una funzione difitness multi obiettivo composta da due valori che sono la media effettuatasull’intera segmentazione dei seguenti parametri calcolabili per ciascuntassello:

In-Tile Color Dissimilarity Questo parametro rappresenta la sommadelle deviazioni standard registrata sui diversi canali del colore cal-colate sui pixel appartenenti al poligono, ad esempio se si utilizzail colorspace RGB questo parametro assume la seguente forma

IT = σr + σg + σb (3.12)

ed è indice della variabilità del colore all’interno di un tassello.

Out-tile Color Dissimilarity Per calcolare questo parametro occorreconsiderare due diverse regioni, la prima è il poligono T appartenen-te alla segmentazione e la seconda è il poligono T avente lo stessobaricentro di T ottenuto scalando quest’ultimo di un fattore β > 1.

Il parametro out-tile color dissimilarity è definito come la normaeuclidea del vettore differenza tra il colore medio presente nellaregione T e quello presente nella regione T \ T :

OT =∣∣∣(µr, µg, µb)T − (µr, µg, µb)T\T

∣∣∣ (3.13)

Questo parametro quantifica la misura in cui il colore medio dellaregione interna ad un tassello si discosta da quello presente in unaregione esterna allo stesso situata a ridosso del bordo. Per quantoriguarda il valore del parametro β si è utilizzato β = 1.2.

Attraverso l’algoritmo genetico si è cercato di massimizzare il valoredella out-tile color dissimilarity media e di minimizzare il valore dellain-tile color dissimilarity media.

Questa strategia si basa sulle ipotesi che un tassello di un mosaico pre-senta solitamente una bassa variabilità del colore al suo interno mentrepresenta differenze significative tra il colore della regione interna allo stes-so e quella esterna a ridosso del bordo. Dal paper [3] è inoltre emersa una

11 Inizializzazione della griglia

correlazione tra il valore di questi indici e la qualità delle segmentazioniottenute dai vari algoritmi in termini della metrica oggettiva f-measure.Tali indicatori forniscono quindi informazione sulla difficoltà intrinsecache caratterizza la segmentazione di un particolare mosaico.

3.3 Inizializzazione della griglia

Come precedentemente anticipato, al fine di garantire una buona modu-larità e riutilizzo del codice, la procedura di inizializzazione della popo-lazione è stata suddivisa in due fasi:

1. La prima fase, che verrà descritta in dettaglio in questa sezione, è in-dipendente dal particolare formato del genotipo utilizzato e riguar-da l’impostazione del numero, posizione e dimensione dei tasselliche compongono le segmentazioni.

Come già accennato in questa fase si definiscono per ogni tassellole coordinate (cxi, cyi) del baricentro e il parametro di che equivalealla metà della lunghezza del lato dello stesso ipotizzando che abbiaforma quadrata.

2. La seconda fase, già descritta in precedenza nella sezione 3.1, ri-guarda invece l’inizializzazione dei parametri dei geni nel modopiù appropriato in riferimento al particolare formato del genotipobasandosi sui cxi, cyi e di ottenuti dalla prima fase.

Per quanto riguarda la prima fase sono stati considerati due approcciche verranno descritti nel seguito: l’inizializzazione uniforme della grigliae l’inizializzazione basata su un semplice algoritmo di blob detection.

Entrambe queste modalità richiedono in ingresso dei parametri facil-mente ottenibili dall’immagine del mosaico originale finalizzati a descri-vere grossolanamente le dimensioni medie dei tasselli.

3.3.1 Inizializzazione uniforme

Questa modalità di inizializzazione richiede in ingresso un singolo para-metro davg, denominato “dimensione media dei tasselli”. Tale parametropuò essere interpretato come il diametro medio delle tessere ed è ricava-bile mediante una rapida analisi dell’immagine originale, non è necessariaun’elevata accuratezza ma è sufficiente individuare l’ordine di grandezza.

Questo operatore fornisce alla procedura che implementa il genotipo idati utili a generare una griglia di quadrati avente dimensione bw/davgc×bh/davgc, dove w e h sono rispettivamente la larghezza e l’altezza in pixeldell’immagine da elaborare. Il valore dei parametri di viene fissato adavg/2 ∀i e i vari cxi e cyi vengono forniti in modo tale da generare una


Figura 3.1: Risultato dell’applicazione dell’inizializzazione uniforme, nella re-gione in basso a destra si può notare che il numero di tasselli nella griglia nonè sufficiente ad identificare tutti i tasselli presenti nel mosaico

griglia di quadrati aventi lo stesso lato ripartendo uniformemente lo spazioesterno ai poligoni lungo gli assi x ed y.

Questo tipo di inizializzazione è molto semplice da implementare mapresenta degli svantaggi nel caso in cui nel mosaico si riscontri un’ele-vata variabilità nelle dimensioni delle tessere. In particolare è frequenteil caso in cui nell’immagine sono presenti delle regioni caratterizzate dauna dimensione dei tasselli significativamente superiore oppure inferiorerispetto alla media. In questi casi se la griglia è inizializzata uniforme-mente si avrà a disposizione un numero rispettivamente troppo elevato otroppo basso di poligoni nella stessa regione e la configurazione iniziale sa-rà piuttosto lontana da quella ottima rendendo più difficile la convergenzadell’algoritmo.

3.3.2 Inizializzazione basata su preprocessing

Al fine di alleviare i problemi precedentemente esposti è stato implemen-tato un algoritmo di preprocessing finalizzato ad identificare in modogrossolano il numero, la posizione e la dimensione dei tasselli, consen-


tendo di stimare i valori di cxi, cyi e di effettivi del mosaico fornito iningresso. In questo modo si ottiene una griglia iniziale che approssima laconfigurazione ottima in modo migliore rispetto al caso precedente con-sentendo all’algoritmo genetico di concentrarsi sulla sola identificazionedella forma dei tasselli, riducendo lo spazio di ricerca.

L’algoritmo di inizializzazione basato sul preprocessing fornisce inuscita una lista di circonferenze aventi centri in (cxi, cyi) e raggi ri e ricevein ingresso tre parametri: rmax, rmin ed rstep con il seguente significato:

• rmax è il massimo raggio delle circonferenze in uscita.

• rmin è il minimo raggio delle circonferenze in uscita.

• rstep identifica la risoluzione che si desidera ottenere rispetto al rag-gio dei tasselli, in particolare il valore del raggio delle circonferenzeottenute apparterrà all’insieme

R = {rmin, rmin + rstep, rmin + 2rstep, . . . , rmin + brmax − rmin

rstepcrstep}

(3.14)

La fase di preprocessing è basata su un semplice algoritmo di blobdetection che utilizza la tecnica delle differenze di gaussiane, di seguitobrevemente descritta.

3.3.3 Differenze di gaussiane

Un metodo basato su forti fondamenti teorici per effettuare blob detectionprevede l’utilizzo di un filtro a convoluzione basato sul seguente kernel,detto laplaciano della gaussiana normalizzato (LoG):

LoG(x, y, t) , t∇2L(x, y, t) (3.15)

in cui L(x, y, t) è una funzione gaussiana avente la seguente forma:

L(x, y, t) =1√2πt

e−x2+y2

2t (3.16)

dove t = σ2 è detto parametro di scala.Data una funzione f(x, y) : R2 7→ R rappresentante un’immagine in

scala di grigi, il metodo prevede di identificare come blobs i punti (x, y, t)corrispondenti ai massimi e minimi locali del risultato del prodotto diconvoluzione

LoG(x, y, t) ∗ f(x, y) (3.17)


Il kernel LoG(x, y, t) può essere approssimato dalla differenza di duefunzioni gaussiane aventi deviazioni standard leggermente diverse:

LoG(x, y, t) ' DoG(x, y, t) , L(x, y, t)− L(x, y, t−∆t) (3.18)

con ∆t > 0.Dalla 3.18 si può notare che la convoluzione tra il kernel DoG(x, y, t)

e un’immagine può essere effettuata tramite la differenza del risultatodi due applicazioni di un filtro gaussiano, che gode della proprietà diseparabilità. Tale proprietà consente di ridurre il tempo necessario pereffettuare la convoluzione rispetto al caso in cui si utilizzi LoG(x, y, t),per questo motivo si è preferito utilizzare il primo kernel.

Si fornisce ora una breve dimostrazione del fatto che il kernel DoG(x, y, t)approssima LoG(x, y, t).

Poiché la gaussiana è soluzione dell’equazione di diffusione

1

2∇2L =

∂L

∂t(3.19)

si ha che

1

2∇2L(x, y, t) =

∂

∂tL(x, y, t)

' L(x, y, t)− L(x, y, t′ = t−∆t)

∆t=

DoG(x, y, t)

∆t

e quindi

DoG(x, y, t) ' 1

2∆t∇2L(x, y, t) (3.20)

In particolare se t′ = αt con 0 < α < 1 e quindi ∆t = (1 − α)t si hache

DoG(x, y, t) ' 1

2(1− α)t∇2L(x, y, t) =

1

2(1− α)LoG(x, y, t) (3.21)

e dunque DoG(x, y, t) risulta con un certo grado di approssimazioneproporzionale a LoG(x, y, t).

Effettuare la convoluzione tra un kernel gaussiano L(x, y, t) ed un’al-tra funzione f(x, y) : R2 7→ R rappresentante ad esempio un’immaginein scala di grigi corrisponde intuitivamente ad effettuare un filtraggiopassabasso nelle frequenze spaziali che attenua le features aventi raggioinferiore a

√t.

Effettuando la differenza tra due funzioni L(x, y, t1) ed L(x, y, t2 =t1 −∆t) con ∆t > 0 si ottiene un kernel che effettua un filtraggio passa-banda, in particolare fornisce risposte forti in presenza di blobs di colorescuro di raggio compreso tra

√t1 e√t2.


(a) Immagine originale (b) Risultato dell’applicazione delcomando edge

Figura 3.2: Particolare del mosaico university prima e dopo l’applicazione delcomando edge

Come precedentemente detto per localizzare dei blobs di colore scurocon bordo chiaro nell’immagine originale è possibile andare a ricercare imassimi locali rispetto ad x, y e alla scala t del risultato della convoluzioneDoG(x, y, t) ∗ f(x, y), ossia

argmaxlocalx,y,tDoG(x, y, t) ∗ f(x, y) (3.22)

Un problema da affrontare per poter utilizzare questo filtro è il fatto didover passare da un immagine a colori rappresentabile come una funzionef : R2 7→ Rc, dove c rappresenta il numero di dimensioni dello spazio dicolori utilizzato, ad una f : R2 7→ R avente un singolo valore per pixel.

Questo problema è stato affrontato mediante il comando edge dellalibreria ImageMagick, che fornisce in uscita un’immagine in scala di grigidove sono evidenziate con colore chiaro le zone in cui è presente un bordo.Tale approccio appare sensato in quanto in un mosaico tipicamente i bor-di dei tasselli sono ben definiti. L’effetto passa banda del filtro differenzedi gaussiane permette inoltre di ridurre l’influenza di eventuali bordi spu-ri dovuti ad imperfezioni sui tasselli aventi dimensione sufficientementelontana dell’intervallo di scala di interesse.

Per mettere in relazione la scala t di un massimo locale al parametro dida fornire in fase di inizializzazione si è assunto che i blob cercati siano dicolore scuro, di forma circolare e aventi un bordo chiaro di spessore moltominore al raggio. Tali ipotesi derivano dal fatto che si sta elaborandol’immagine in scala di grigi ottenuta mediante il comando edge.

In queste condizioni il filtro fornisce la risposta massima in posizione(cx, cy) corrispondente al centro del cerchio e alla scala tale che il contornodel blob si trova in corrispondenza della curva di forma circolare sullaquale il kernel presenta valore massimo.

Per individuare il raggio r di questa curva, vista la simmetria radialedel kernel si può considerare una restrizione dello stesso su una rettapassante per l’origine. In queste condizioni posto σ =

√t e con α definito


precedentemente si ricava che

r = σ

√6α2 log( 1

α)

1− α2(3.23)

A questo punto per fissare di si è considerata la lunghezza del lato delquadrato circoscritto ad una circonferenza di raggio r ossia 2r e quelladel lato del quadrato inscritto alla stessa, ossia 2r√

2e si è scelto

di =r

2

(1 +

1√2

)(3.24)

ossia pari alla media tra le metà dei lati dei due quadrati precedentementedescritti. Questa scelta ha dato buoni risultati in seguito a verifichesperimentali.

3.3.4 Scelta dei blobs

Da valutazioni sperimentali è emerso che inizializzare la griglia utilizzandotutti i massimi locali di DoG(x, y, t) ∗ f(x, y) porta ad un numero troppoelevato di poligoni nella segmentazione. Questo è dovuto al fatto chel’algoritmo di blob detection fornisce dei falsi positivi in alcune regioni incorrispondenza del filler ed in corrispondenza di alcune impurità presentisui tasselli di dimensioni che rientrano nell’intervallo di scale di interesse.

Per alleviare questo problema è stato implementato il seguente algo-ritmo:

Si costruisce la lista Lout dei blobs da utilizzare per inizializzare l’al-goritmo genetico, inizialmente vuota. Un generico elemento di Lout saràdella forma (x, y, r, g) dove:

• x ed y sono le coordinate del centro del blob.

• r rappresenta il raggio del blob.

• g = g(x, y, t(r)) = DoG(x, y, t(r)) ∗ f(x, y) è la risposta del kernelin corrispondenza di x,y e r.

Per ogni raggio ri ∈ R si effettua la seguente procedura partendo darmin e procedendo in ordine crescente:

1. Si ricava ti da ri utilizzando la 3.23.

2. Si calcola g(x, y, ti) = DoG(x, y, ti) ∗ f(x, y).

3. Si calcola l’insieme Bri delle quadruple (x, y, ri, g) dei massimi localirispetto ad x ed y di g(x, y, t(ri)).

17 Descrizione dell’algoritmo genetico

4. Per ogni b = (x, y, ri, g) ∈ Bri e per ogni

b′ = (x′, y′, r′, g′) ∈ Lout :∣∣(x, y)− (x′, y′)

∣∣ < β · ri

si effettua la seguente procedura:

(a) se r ≥ r′ e g > g′ allora b sostituisce b′ nella lista Lout.

(b) altrimenti se r > r′ e g > γ · g′ allora b sostituisce b′ nella listaLout.

(c) altrimenti se g < g′ b viene scartato.

se al termine di questi passi b non è stato già inserito in Lout e senon è stato scartato questo viene inserito in Lout.

Il parametro 0 < β < 1 è finalizzato alla gestione delle intersezioni edefinisce la distanza minima tollerabile tra i centri di due blob in funzionedei loro raggi.

Il parametro 0 < γ < 1 è finalizzato a dare la preferenza ai blob diraggio maggiore rispetto a quelli di dimensione minore posti a distanzanon tollerabile dai primi, anche se i secondi presentano un valore legger-mente superiore di g. Questo per tentare di eliminare eventuali blob spuridi dimensioni ridotte dovuti ad esempio ad imperfezioni del materiale deitasselli. In seguito a verifiche sperimentali si è impostato α = β = 0.9.

3.4 Descrizione dell’algoritmo genetico

La variante di algoritmo genetico utilizzata è NSGA2 [2], che realizza l’ot-timizzazione multi obiettivo tramite l’ordinamento non-dominato o perfronti di Pareto. Tale tipo di ordinamento è adatto ad affrontare proble-mi in cui il numero di componenti della funzione di fitness è maggiore diuno. In questo caso, poiché Rn con n > 1 risulta privo di una nozionedi ordinamento naturale risulta non immediato ordinare una popolazionerispetto al grado di ottimalità di ogni individuo.

Al fine di risolvere questo problema si ripartisce la popolazione in unasequenza di sottoinsiemi Fi detti fronti di Pareto. Se un individuo appar-tiene a Fi non esistono individui appartenenti a Fj con j ≥ i che domi-nano il primo, ossia che risultano migliori di questo contemporaneamenterispetto a tutte le componenti della funzione di fitness.

Esistono diverse varianti di algoritmo genetico che adottano questastrategia, quella utilizzata in questo lavoro, ossia NSGA2, presenta leseguenti caratteristiche distintive:


• Implementa un algoritmo di ordinamento non dominato efficientecon complessità computazionale O(MN2) dove M è il numero diobiettivi ed N è la dimensione della popolazione, complessità in-feriore rispetto a quella presentata dall’algoritmo di ordinamentotradizionale di NSGA, ossia O(MN3).

• Mantiene una buona diversità della popolazione durante l’evoluzio-ne: un algoritmo di ottimizzazione multi obiettivo basato sull’or-dinamento per fronti di Pareto fornisce in uscita un insieme di so-luzioni non dominate, è importante che queste presentino un buongrado di diversità e che siano distribuite uniformemente lungo ilfronte ottimo che caratterizza il problema.NSGA2 affronta questo aspetto introducendo la cosiddetta crow-ding distance, che rappresenta per ogni individuo una stima delperimetro del cuboide avente come vertici il valore della funzione difitness vettoriale presentata dei due individui adiacenti allo stessorispetto a ciascuno degli obiettivi. Un valore elevato di tale metri-ca indica che l’individuo considerato si trova in una regione pocoaffollata dello spazio della funzione di fitness.NSGA2 per selezionare gli individui da utilizzare per ottenere lagenerazione successiva adotta questi criteri:

1. Se due individui si trovano in diversi fronti di pareto vieneprivilegiato quello appartenente al fronte di indice minore (inquesto caso quest’ultimo domina l’altro).

2. Se due individui appartengono allo stesso fronte viene privi-legiato quello avente crowding distance più elevata, in modotale da garantire la diversità all’interno della popolazione.

Questo approccio presenta il vantaggio di non richiedere parametriall’utente come invece avviene nel caso di NSGA e presenta unacomplessità computazionale inferiore rispetto alla strategia utiliz-zata da quest’ultimo algoritmo.

• Introduzione dell’elitarismo: L’applicazione degli operatori di mu-tazione e crossover agli individui di una popolazione possono in-trodurre dei cambiamenti sfavorevoli negli individui migliori di unapopolazione. Al fine di impedire questo fenomeno si introduce ilconcetto di elitarismo, che consiste nel trasferire dalla generazioneprecedente a quella successiva gli individui migliori senza appor-tare loro alcuna modifica. Nel caso di una funzione di fitness adobiettivo singolo questo processo assicura che l’andamento nel tem-po del miglior valore della stessa all’interno della popolazione siamonotono.

19 Descrizione dell’algoritmo genetico

NSGA2 introduce l’elitarismo procedendo nel modo seguente: par-tendo dall’insieme Pt di dimensione N degli individui della gene-razione precedente si genera un altro insieme Qt di dimensione Nanch’esso tramite gli operatori di mutazione e crossover. A questopunto si applica l’algoritmo di ordinamento non dominato all’insie-me Pt ∪ Qt e si genera la nuova generazione Pt+1 selezionando gliN individui migliori da Pt ∪ Qt secondo i criteri precedentementedescritti.

Verranno ora illustrati gli operatori di mutazione e crossover utilizzatie i loro paramerti.

3.4.1 Operatore di crossover uniforme

Per quanto riguarda il crossover si è utilizzato un operatore di tipo uni-forme. Data una coppia di individui appartenenti alla generazione pre-cedente si ottiene un individuo figlio da inserire nella nuova popolazioneoperando con questa procedura:

Il gene i-esimo dell’individuo figlio gfi = (fi1, . . . , fik) si ottiene daicorrispondenti geni dei genitori g1

i = (p1i1, . . . , p

1ik) e g2

i = (p2i1, . . . , p

2ik)

come segue:

fij ←{p1ij : x ≤ 1

2

p2ij : x > 1

2

con x ∼ U(0, 1) variabile aleatoria distribuita uniformemente nell’inter-vallo [0, 1].

3.4.2 Operatore di mutazione uniforme

L’operatore di mutazione uniforme sostituisce il valore del parametro j-esimo pij del gene i esimo di un individuo come segue:

pij ← u (3.25)

con u ∼ U(pminij , pmax

ij ) variabile aleatoria distribuita uniformemente nel-

l’intervallo di validità Pij =[pminij , pmax

ij

]del parametro pij .

Si utilizza questo operatore per garantire una buona esplorazione dellospazio di ricerca riducendo la possibilità che un parametro converga adun minimo locale non ottimo.

3.4.3 Operatore di mutazione gaussiano

L’operatore di mutazione gaussiano sostituisce il valore del parametroj-esimo pij del gene i esimo di un individuo come segue:

pij ← pij + g (3.26)


con g ∼ N(0, σij) variabile aleatoria di distribuzione normale a medianulla e con deviazione standard σij definita in fase di inizializzazione.

Al termine di questa operazione si assicura che pij appartenga all’in-tervallo di validità Pij =

[pminij , pmax

ij

]aggiornandolo come segue:

pij ←

pminij : pij < pmin

ij

pmaxij : pij > pmax

ij

pij altrimenti

Si utilizza questo operatore per apportare aggiustamenti fini ai para-metri.

La nuova popolazione viene originata ottenendo nuovi individui par-tendo dalla popolazione precedente utilizzando i tre operatori preceden-temente descritti con probabilità diverse. In particolare un nuovo indi-viduo viene ottenuto attraverso l’operatore di crossover con probabilitàpcr = 0.8, attraverso l’operatore di mutazione uniforme con probabilitàpu = 0.1 ed attraverso l’operatore di mutazione gaussiana con probabi-lità pg = 0.1. La probabilità che un parametro p appartenente al genei-esimo subisca una mutazione vale 2

|S|·|g| , dove |S| rappresenta il numerodi poligoni presenti nella segmentazione e |g| è il numero di parametricontenuti in un gene. I valori di tali probabilità sono stati impostati inseguito ad analisi sperimentale.

La selezione degli individui ai quali applicare gli operatori per ottenerela nuova popolazione avviene secondo quanto specificato dall’algoritmoNSGA2.

3.5 Scelta delle segmentazioni risultanti

L’algoritmo NSGA2 fornisce in uscita un insieme di soluzioni che corri-spondono al primo fronte di Pareto F1 ottenuto dopo l’ultima generazionecalcolata.

Risulta dunque necessario selezionare quali soluzioni fornire in uscitadall’algoritmo di segmentazione all’interno di tale fronte. Si è risoltoquesto problema decidendo di fornire come risultato le segmentazioni SIed SO caratterizzate rispettivamente dalla migliore in ed out-tile colordissimilarity presenti all’interno di F1.

3.6 Gestione delle intersezioni

L’algoritmo precedentemente descritto non esclude la possibilità che duepoligoni appartenenti alla segmentazione abbiano intersezione non vuo-ta. Tale fenomeno ovviamente non si verifica nell’immagine originale in

21 Gestione delle intersezioni

quanto ogni pixel appartiene al più ad un singolo tassello e quindi vaevitato.

Allo stato attuale le intersezioni non sono state gestite nel corso dell’e-voluzione ma bensì a posteriori mediante un algoritmo di postprocessingbasato su tecniche di programmazione lineare.

Tale algoritmo riceve in ingresso una segmentazione e fornisce comerisultato una seconda segmentazione ottenuta dalla prima rimuovendo deipoligoni in modo tale da risolvere il problema delle intersezioni, ottimiz-zando contemporaneamente una funzione obbiettivo lineare descritta nelseguito.

3.6.1 Variabili decisionali

Si associa una variabile decisionale binaria xi al poligono i-esimo apparte-nente alla segmentazione: se xi vale uno il poligono viene conservato nellasegmentazione fornita in output, in caso contrario questo viene scartato.

3.6.2 Funzione obiettivo

Per gestire le intersezioni sono state sperimentate due diverse funzioniobiettivo:

• Massimizzazione della out-tile color dissimilarity: Viene mas-simizzata la somma degli indicatori out-tile color dissimilarity Oidei tasselli non scartati:

f1 : max∑i

Oixi (3.27)

• Massimizzazione dell’area totale ricoperta: Viene massimiz-zata la somma delle aree Ai dei tasselli non scartati:

f2 : max∑i

Aixi (3.28)

3.6.3 Vincoli

Oltre al vincolo di interezza delle variabili decisionali si introduce un’altrafamiglia di vincoli finalizzata alla gestione delle intersezioni.

In seguito a verifiche sperimentali è emerso che proibire completamen-te le intersezioni tra i poligoni delle segmentazioni ottenute dall’algoritmogenetico comporta la perdita di un numero troppo elevato di tasselli. Siè deciso dunque di consentire che due tasselli abbiano intersezione nonvuota purché il massimo rapporto tra l’area dell’intersezione e quella dei


due tasselli sia inferiore ad un certo parametro α. In seguito ad ana-lisi sperimentali si è concluso che utilizzare α = 0.1 porta a risultatisoddisfacenti.

La condizione sopra descritta può essere formalizzata dalla seguentefunzione:

c(i, j) =

{1 : max(

Ai∩jAi

,Ai∩jAj

) > α

0 altrimenti

dove Ai rappresenta l’area del poligono i-esimo, Aj l’area del poligonoj-esimo, ed Ai∩j l’area dell’intersezione dei due poligoni sopra citati.

Utilizzando tale funzione è possibile associare al poligono i-esimo pil’insieme Si degli indici dei poligoni che che presentano un’area dell’in-tersezione con pi non soddisfacente secondo il criterio precedentementedescritto:

Si = {j : c(i, j) = 1, i 6= j} (3.29)

Si impone ora la seguente famiglia di vincoli:

∀i xi = 1 =⇒∑j∈Si

xj = 0 (3.30)

che impone la condizione che se il poligono pi non viene scartato tuttii poligoni che presentano un’area dell’intersezione non soddisfacente conpi devono essere scartati.

Tale condizione può essere rappresentata mediante vicoli lineari nelmodo seguente:

Si associa ad ogni xi un’altra variabile decisionale binaria yi cherappresenta la negazione binaria di xi:

yi =

{1 : xi = 00 : xi = 1

il che è esprimibile dalla famiglia di vincoli

∀i xi + yi = 1 (3.31)

I vincoli 3.30 possono essere ora rappresentati nel modo seguente:

∀i∑j∈Si

xj − |Si| yi ≤ 0 (3.32)

dove |Si| rappresenta la cardinalità dell’insieme Si.

23 Implementazione ed ottimizzazioni

3.7 Implementazione ed ottimizzazioni

3.7.1 Strumenti utilizzati

Durante questo lavoro sono state utilizzate le seguenti librerie open-source:

• OpenBeagle1: Libreria general-purpose per l’ottimizzazione gene-tica.

• ImageMagik2: Libreria per la manipolazione delle immagini.

• lp_solve3: Solver per problemi di programmazione lineare.

3.7.2 Working sets

Un’ottimizzazione introdotta è quella di consentire che l’algoritmo ge-netico apporti modifiche ad ogni generazione tramite mutazione e cros-sover solamente ad un sottoinsieme ristretto dei poligoni della segmen-tazione. Tale sottoinsieme, denominato working set, viene cambiatoperiodicamente dopo un numero prefissato di generazioni.

Più formalmente dato il cromosoma di un individuo C = (g1, . . . , gn),dove gi è un generico gene appartenente ad esso, il working set correnteè un sottoinsieme Wk = (gk, . . . , gk∗) ⊆ C, k∗ = min(n, k + lws − 1) dovelws è la dimensione del working set, parametro configurabile dall’utente.

Il fatto che il working set sia costituito da un sottoinsieme di geniaventi indici consecutivi non implica necessariamente che i poligoni otte-nuti esprimendo gli stessi siano vicini nella segmentazione. Questo fattosi verifica ad esempio se la segmentazione è stata inizializzata in modouniforme e i poligoni appartengono tutti ad una stessa riga, ma non siverifica se la griglia è stata inizializzata tramite preprocessing.

Il working set corrente viene aggiornato ogni nws generazioni dovenws è un parametro configurabile dall’utente, l’aggiornamento avvienenel modo seguente:

k ← ((k − 1 + blws/2c) mod n) + 1 (3.33)

3.7.3 Manipolazione dei poligoni

L’operazione che ha il maggior impatto sul tempo di esecuzione dell’algo-ritmo è il calcolo degli indicatori in ed out-tile dissimilarity dei tasselli. Si

1https://github.com/chgagne/beagle2http://www.imagemagick.org/3http://lpsolve.sourceforge.net/


è quindi cercato di ottimizzare il più possibile la parte di codice finalizzataad effettuare un ciclo sui pixel interni ad un poligono.

Dato un poligono p = {v1, . . . , vk} rappresentato come una lista divertici vi = (xi, yi) ordinata in senso orario si procede nel modo seguente:

1. Si individuano due vertici vt, vb ∈ p tali che yt >= yi ∀i e yb <=yi ∀i ed aventi le coordinate xt e xb rispettivamente minima emassima possibile.

2. Si suddivide il contorno del poligono in due due spezzate sl ed sraventi come estremi i vertici vt e vb tali che per ogni punto p ∈ sle q ∈ sr sia verificata la condizione xp ≤ xq. A questo puntosi rimuovono eventuali segmenti orizzontali da sl ed sr in modotale che ciascuna contenga uno ed un solo punto r con xr = y∀y ∈ [yb, yt]. Le operazioni precedenti sono possibili se e solo se ilpoligono considerato contiene tutti i segmenti orizzontali che hannocome estremi punti appartenenti ad esso, condizione che è valida inparticolare per i poligoni convessi.

3. ∀y ∈ [yb, yt] ∩ N si individuano i punti l ∈ sl e r ∈ sr aventi coor-dinate yr = yl = y e si effettua un ciclo sui punti aventi coordinate(x, y) con x ∈ [xl, xr] ∩ N.

Procedendo in questo modo si visitano i punti interni al poligono perrighe, ossia allo stesso modo in cui l’immagine è memorizzata, questoporta ad una riduzione dei tempi di accesso alla memoria dovuti ad unmigliore sfruttamento delle cache. Per individuare i punti l ed r si puòconsiderare il fatto che ∀y questi apparterranno a due segmenti distinti,il primo appartenente alla spezzata sl ed il secondo a sr. Le coordinate led r sono calcolabili in modo efficiente a partire dal coefficiente angolaree dall’ordinata all’origine delle rette che contengono tali segmenti.

3.7.4 Manipolazione dei pixel

Per manipolare i pixel sono state utilizzate le estensioni SSE presenti sullamaggior parte delle CPU moderne con architettura x86 oppure x86_64.Tali estensioni prevedono la presenza di una serie di registri general pur-pose di grandi dimensioni (128 bit e oltre) che consentono l’esecuzione diistruzioni di tipo SIMD (Single Instruction Multiple Data).

Questi registri possono essere utilizzati per svolgere una stessa ope-razione in maniera parallela tra più dati contenuti all’interno degli stessi.Ad esempio su un registro a 128 bit è possibile caricare 4 numeri floating-point a 32 bit ed eseguire in parallelo una stessa operazione aritmeticaper ognuno di essi utilizzando un numero di cicli di clock inferiore rispettoal caso sequenziale.

25 Implementazione ed ottimizzazioni

Tali estensioni sono state utilizzate in questo lavoro per calcolare inmodo efficiente la media del colore dei pixel appartenenti ad una deter-minata regione, operazione realizzabile mediante una somma parallela suciascuno dei canali di colore.

3.7.5 Caching

Come precedentemente detto l’operazione che ha il maggior impatto sultempo di esecuzione dell’algoritmo è il calcolo degli indicatori in ed out-tile dissimilarity dei tasselli. Al fine di migliorare la performance è stataintrodotta una strategia di caching di tali indicatori che agisce nel modoseguente:

• Ogni qual volta si apportano delle modifiche ad un tassello tramitemutazione e crossover questo fatto viene memorizzato mediante unapposito flag.

• Ogni qual volta si calcolano gli indicatori per un tassello questivengono salvati e il flag di modifica viene resettato.

• L’aggiornamento degli indicatori viene effettuato solamente se iltassello è stato modificato dopo l’ultima volta che questi sono sta-ti calcolati (fatto segnalato dal flag sopra citato), altrimenti siriutilizzano i valori salvati precedentemente.

Capitolo 4

Procedura sperimentale

L’algoritmo ottenuto è stato confrontato sperimentalmente con gli stessialgoritmi ed utilizzando le stesse metriche considerate in [3] su una se-rie di mosaici per i quali è disponibile una segmentazione ground truthricavata manualmente. Vengono ora descritte brevemente le metriche divalutazione.

4.1 Metriche di valutazione

La valutazione di una segmentazione RI rispetto ad una segmentazioneground truth TI viene effettuata mediante quattro indicatori che quanti-ficano in che misura vengono soddisfatti i seguenti requisiti:

• Il numero di tasselli presenti in RI deve essere più vicino possibileal valore che caratterizza TI .

• I tasselli di RI devono contenere tutti e soli i pixel presenti contenutinei tasselli di TI .

4.1.1 Errore sul conteggio

L’errore sul conteggio è definito come segue:

Count(RI , TI) =abs(|TI | − |RI |)

|TI |(4.1)

e rappresenta il rapporto tra il valore assoluto della differenza del numerodi tasselli presenti nella segmentazione RI e il numero di tasselli presentinella ground truth TI rispetto a quest’ultimo valore.

27

4. Procedura sperimentale 28

4.1.2 Precision

L’indicatore precision è definito come segue:

Prec(RI , TI) =1

|TI |∑T∈Ti

maxR∈RI|R ∩ T |

|R|(4.2)

Questo indicatore esprime quantitativamente il requisito che i tassellidella segmentazione devono contenere solo pixel appartenenti alle tesseredi TI .

R3

T

R2

R1

Figura 4.1: Illustrazione grafica dei poligoni coinvolti nel calcolo dell’indicatoreprecision per un tassello della ground truth

In figura 4.1 si illustra graficamente la selezione dei tasselli che contri-buiscono all’indicatore precision per un tassello T della ground truth: èstato evidenziato in blu il tassello la cui area si trova al denominatore nelrapporto dell’equazione 4.2. Tra i tasselli Ri appartenenti alla segmenta-zione da valutare quello che presenta intersezione massima con T e cheè l’unico che contribuisce all’indice è stato rappresentato con il contornocontinuo.

4.1.3 Recall

Rec(RI , TI) =1

|TI |∑T∈Ti

maxR∈RI|R ∩ T |

|T |(4.3)

Questo indicatore esprime quantitativamente il requisito che i tassellidella segmentazione devono contenere tutti i pixel appartenenti ai tassellidi TI .

29 Metriche di valutazione

R3

T

R2

R1

Figura 4.2: Illustrazione grafica dei poligoni coinvolti nel calcolo dell’indicatorerecall per un tassello della ground truth

In figura 4.2 si illustra graficamente la selezione dei tasselli che con-tribuiscono all’indicatore recall per un tassello T della ground truth, consignificato dei simboli analogo al caso della figura 4.1.

4.1.4 F-Measure

Fm(RI , TI) = 2Prec(RI , TI)Rec(RI , TI)

Prec(RI , TI) + Rec(RI , TI)(4.4)

La f-measure è la media armonica degli indicatori precision e recall.Questo parametro riassume in un unico valore i primi due ed esprimequalitativamente il requisito che una buona segmentazione deve conte-nere tutti e soli i pixel che appartengono ai tasselli della ground truth.La f-measure è influenzata maggiormente dal peggiore tra i valori degliindicatori precision e recall.

Al fine di giudicare la bontà di una segmentazione è necessario con-siderare contemporaneamente almeno i valori dell’errore sul conteggio edella f-measure: tali valori se considerati singolarmente non fornisconoinfatti informazioni significative sulla qualità della stessa. Per convincer-si di questo fatto si può considerare ad esempio il caso in cui si confrontila ground truth di un mosaico con se stessa: in questo caso la f-measurevale 1, che è il massimo valore consentito. A questo punto se si aggiun-gono arbitrariamente tasselli ad una delle due segmentazioni il valore ditale parametro non cambia ma la qualità della segmentazione decresce, ètuttavia possibile accorgersi di questo fatto se si considera anche l’erroresul conteggio.


4.2 Obiettivi

La procedura sperimentale è finalizzata a valutare l’influenza dei diversiparametri sulla qualità delle segmentazioni risultanti espressa in terminidelle metriche sopra descritte e sul tempo di esecuzione, oltre che a con-frontare l’algoritmo ottenuto tramite questo lavoro con quelli valutati nelpaper [3].

Nello specifico gli obiettivi di questa analisi sono i seguenti:

• Verificare se l’algoritmo genetico è efficace nell’ottimizzare la fun-zione obiettivo.

• Valutare se esiste correlazione tra l’andamento rispetto al numerodi generazione della funzione di fitness e le metriche oggettive perla valutazione delle segmentazioni precedentemente descritte.

• Valutare l’influenza della dimensione della popolazione sulla qualitàdelle segmentazioni e sul tempo di esecuzione.

• Confrontare in termini di qualità delle segmentazioni e tempo diesecuzione il caso in cui si utilizzi la modalità di esecuzione basatasui working sets e quello in cui si consente di modificare l’interagriglia ad ogni generazione.

• Valutare la variabilità delle soluzioni all’interno del fronte di Paretoal termine dell’evoluzione e verificare se la scelta delle segmentazionida fornire come output è opportuna.

• Valutare come la procedura di gestione delle intersezioni impattasulle metriche di valutazione e sulla qualità empirica delle segmen-tazioni.

• Valutare l’influenza del formato del genotipo sulle metriche di va-lutazione e sulla qualità empirica delle segmentazioni.

• Confrontare la modalità di inizializzazione della griglia uniformerispetto a quella basata sull’algoritmo di preprocessing.

• Confrontare i risultati ottenuti utilizzando i migliori parametri conquelli degli altri algoritmi considerati nel paper [3].

4.3 Organizzazione

La procedura è stata organizzata nel modo seguente: sono state identifi-cate delle varianti dell’algoritmo da valutare, dove per varianti si intendeun insieme di parametri di configurazione.

31 Organizzazione

Per ogni mosaico tra quelli considerati dal paper [3] e per ogni variantesono state effettuate tre esecuzioni dell’algoritmo ciascuna con randomseed diverso.

Ognuna delle esecuzioni produce come risultato tre gruppi di segmen-tazioni di seguito descritti:

1. Segmentazioni caratterizzate rispettivamente dalla migliore out edin-tile color dissimilarity all’interno del fronte di Pareto (in totaledue segmentazioni).

2. Segmentazioni caratterizzate rispettivamente dai migliori e peggiorivalori degli indicatori precision, recall, f-measure riscontrati all’in-terno del fronte di Pareto (in totale sei segmentazioni). Questogruppo di segmentazioni è ottenibile solo avendo a disposizione laground truth associata al mosaico.

3. Per ognuna delle due segmentazioni appartenenti al gruppo 1 sonostate ottenute altre due segmentazioni applicando l’algoritmo di ge-stione delle intersezioni utilizzando ciascuna delle funzioni obiettivodescritte nella sezione 3.6.2 (in totale quattro segmentazioni).

Ciascuna delle segmentazioni ottenute è stata poi valutata rispetto allaground truth relativa al mosaico considerato.

La tabella seguente elenca le varianti testate e per ognuna di esse iparametri che la contraddistingue:

Tabella 4.1: Varianti e relativi parametri

Variante Modalità Dimensionepop. Preprocessing Formato

poligoni

1 griglia intera 20 si rettangoli2 griglia intera 20 si q. convessi3 griglia intera 20 no q. convessi4 griglia intera 100 si q. convessi5 griglia intera 20 no rettangoli6 griglia intera 50 si q. convessi7 working sets 20 no rettangoli

dove la colonna Modalità indica se nella variante è stata utilizzatal’ottimizzazione dei working sets oppure è stata consentita l’evoluzionedell’intera griglia ad ogni generazione.


4.3.1 Random seed

Per ogni esecuzione è stato utilizzato un random seed differente: in am-biente Linux la libreria di ottimizzazione genetica utilizzata inizializza ilproprio generatore di numeri pseudo-casuali con un seme ottenuto dalfile di dispositivo /dev/random. Tale file viene impiegato dal kernelcome interfaccia per fornire alle applicazioni sequenze casuali ad alta en-tropia ottenute in vari modi, ad esempio utilizzando rumore provenientedai dispositivi di input, da connessioni di rete ed altro.

Capitolo 5

Risultati

Vengono ora esposti i dati ottenuti dalle analisi relative a ciascun obiettivodella procedura sperimentale.

5.1 Efficacia dell’algoritmo

Si illustrano ora dei risultati utili a chiarire se l’algoritmo genetico è effica-ce nell’ottimizzare la funzione di fitness e se esiste correlazione tra l’anda-mento della stessa e le metriche di valutazione oggettive precedentementeesposte.

5.1.1 Andamento della funzione di fitness

Per valutare se l’algoritmo è efficace nello svolgere il processo di ottimizza-zione degli obiettivi della funzione di fitness sono stati ricavati dei graficiche mostrano l’andamento rispetto al numero delle generazioni delle duecomponenti della stessa. Per motivi legati alla semplicità di implemen-tazione si è impostato il problema come un problema di minimo rispettoad entrambi gli obiettivi e si quindi cambiato di segno il valore dell’indiceout-tile color dissimilarity, che va massimizzato.

Si riportano ora gli andamenti tipici del valor medio sulla popolazionedei due indicatori riguardanti un’esecuzione sul mosaico university nellaquale la griglia è stata inizializzata tramite preprocessing.

33

5. Risultati 34

0 2000 4000 6000 8000-0.25

-0.24

-0.23

-0.22

-0.21

-0.2

-0.19

-0.18

Generation

Out

-Tile

Dis

sim

ilarit

y

Out-Tile DissimilarityGround truth Out-Tile Dissimilarity

Figura 5.1: Esempio di andamento della out-tile color dissimilarity (cambiatadi segno) per un esecuzione riguardante il mosaico university

0 2000 4000 6000 80000.14

0.16

0.18

0.2

0.22

0.24

0.26

Generation

In-T

ile D

issi

mila

rity

In-Tile DissimilarityGround truth In-Tile Dissimilarity

Figura 5.2: Esempio di andamento della in-tile color dissimilarity per unesecuzione riguardante il mosaico university

Le serie di dati denominate “Ground truth Out-Tile Dissimilarity”e “Ground truth In-Tile Dissimilarity” rappresentano il valore di taliparametri riscontrato sulla ground truth.

Dai grafici si può notare che l’andamento dei due obiettivi rispetto alnumero di generazioni è in buona approssimazione monotono decrescentee che converge ad un valore limite, questo fatto è stato riscontrato pertutte le esecuzioni.

Si può notare inoltre che i valori della funzione di fitness caratteriz-zanti la ground truth vengono raggiunti e superati dai parametri medicorrispondenti presenti all’interno della popolazione. Questo fatto si ve-rifica in modo particolare nei casi in cui si è utilizzato l’algoritmo di

35 Efficacia dell’algoritmo

0 10000 20000 30000 40000 50000 60000-0.35

-0.3

-0.25

-0.2

-0.15

-0.1

-0.05

Generation

Out

-Tile

Dis

sim

ilarit

y


0 10000 20000 30000 40000 50000 600000.25

0.3

0.35

0.4

0.45

0.5

0.55

Generation

In-T

ile D

issi

mila

rity


Figura 5.3: Andamento tipico dei valori della funzione di fitness nel caso incui la griglia venga inizializzata in modo uniforme

preprocessing per inizializzare la griglia. Nel caso in cui si utilizzi l’algo-ritmo di inizializzazione uniforme l’algoritmo converge invece a dei valoripeggiori di tali parametri, come si vede in figura 5.3, ma l’andamentorisulta comunque monotono.

Da tali considerazioni si può concludere che l’algoritmo genetico ri-sulta efficace nello svolgere il processo di ottimizzazione.

5.1.2 Correlazione tra funzione di fitness e metriche divalutazione

Per valutare se esiste correlazione tra l’andamento della funzione di fitnesse quello delle metriche di valutazione sono stati ottenuti dei grafici chemostrano l’andamento rispetto al numero della generazione delle stesseriguardanti la soluzione che presenta la migliore out-tile dissimilarity al-l’interno del fronte di Pareto, tali grafici sono stati confrontati con quelliche mostrano l’andamento della funzione di fitness.

Si illustra ora l’andamento tipico riscontrato nel caso in cui la grigliadei tasselli venga inizializzata in maniera uniforme, in figura 5.3 e 5.4 simostrano rispettivamente gli andamenti della funzione di fitness e dellemetriche di valutazione per un’esecuzione rappresentativa riguardante ilmosaico bird.

Dai grafici si nota che esiste una buona correlazione tra l’andamen-to della funzione di fitness e tutte le metriche di valutazione oggettiva(l’indicatore count è stato trascurato in quanto rimane costante duran-te l’evoluzione), in quanto queste ultime presentano tutte un andamentomonotono crescente al trascorrere delle generazioni. Questa correlazionesi riscontra in quasi tutti i casi in cui si utilizza l’inizializzazione uniforme.

Consideriamo ora il caso in cui la griglia dei tasselli venga inizializzatamediante l’algoritmo di preprocessing.

Oltre agli andamenti aventi la tipologia descritta nel caso precedente,ossia crescita pressoché monotona di tutte le metriche di valutazione,

5. Risultati 36

0 10000 20000 30000 40000 50000 600000.46

0.47

0.48

0.49

0.5

0.51

0.52

Generation

Pre

cisi

on

0 10000 20000 30000 40000 50000 600000.6

0.605

0.61

0.615

0.62

0.625

Generation

Rec

all

0 10000 20000 30000 40000 50000 600000.52

0.53

0.54

0.55

0.56

0.57

0.58

Generation

F-M

easu

re

Figura 5.4: Andamento tipico delle metriche di valutazione nel caso in cui lagriglia venga inizializzata in modo uniforme

0 10000 20000 30000 40000 50000-0.3

-0.28

-0.26

-0.24

-0.22

-0.2

-0.18

-0.16

Generation

Out

-Tile

Dis

sim

ilarit

y


0 10000 20000 30000 40000 500000.24

0.26

0.28

0.3

0.32

0.34

0.36

Generation

In-T

ile D

issi

mila

rity


Figura 5.5: Andamento dei valori della funzione di fitness nel caso in cui lagriglia venga inizializzata tramite preprocessing

37 Efficacia dell’algoritmo

0 10000 20000 30000 40000 500000.66

0.665

0.67

0.675

0.68

Generation

Pre

cisi

on

0 10000 20000 30000 40000 500000.635

0.64

0.645

0.65

0.655

0.66

Generation

Rec

all

0 10000 20000 30000 40000 500000.655

0.656

0.657

0.658

0.659

0.66

Generation

F-M

easu

re

Figura 5.6: Andamento delle metriche di valutazione nel caso in cui la grigliavenga inizializzata tramite preprocessing

in questo caso si verificano anche gli andamenti riportati in figura 5.5e 5.6, da cui si nota un incremento dell’indicatore precision a discapitodell’indicatore recall, il che fa si che la f-measure risultante non vari dimolto durante al trascorrere delle generazioni. Il valore di tale parametrorisulta comunque significativamente superiore al caso precedente, fattoconfermato anche dalle analisi riportate in seguito.

Il fenomeno dell’incremento della metrica precision a discapito di re-call è dovuto probabilmente al fatto che solitamente i tasselli presentinelle segmentazioni ottenute dall’algoritmo sono interamente contenutiall’interno delle corrispondenti tessere della ground truth. Questo fattoimplica che i primi catturano nella maggior parte dei casi solo pixel ap-partenenti alle tessere del mosaico ma non tutti i pixel appartenenti allestesse.

L’intervallo di variazione di tali metriche risulta più ristretto rispettoal caso precedente in quanto utilizzando il preprocessing la configurazioneiniziale è più vicina a quella ottima.

Complessivamente si può concludere che la correlazione tra l’anda-mento della funzione di fitness e quella delle metriche di valutazione èsoddisfacente e che gli indicatori in ed out-tile color dissimilarity rappre-sentano dei buoni obiettivi da ottimizzare per effettuare la segmentazionedi un mosaico.

5. Risultati 38

5.2 Modalità di evoluzione

In questa sezione si espongono i risultati del confronto tra la modalità dievoluzione basata sui working sets e quella che prevede che possano essereapportate modifiche all’intera griglia di tasselli ad ogni generazione.

Per effettuare questo confronto sono stati considerati i dati riguardantile seguenti varianti:

Tabella 5.1: Varianti utilizzate per il confronto tra le due modalità dievoluzione


poligoni

5 griglia intera 20 no rettangoli7 working sets 20 no rettangoli

Si espongono ora i risultati ottenuti:

Tabella 5.2: Confronto tra le due modalità di evoluzione

Mosaico Mod. Evoluzione Prec Rec Fm T (s)

bird full 49.5 64.5 56.0 9608ws 48.4 63.8 55.0 8905

church full 42.6 64.2 51.2 8908ws 41.2 64.4 50.2 8685

flower full 60.3 62.5 61.4 10253ws 57.8 59.5 58.6 10335

museum full 48.4 72.5 58.1 197ws 48.0 69.9 56.9 188

university full 36.2 63.6 46.2 95ws 36.4 64.6 46.5 100

I valori presenti in tabella sono ottenuti effettuando delle medie sullediverse esecuzioni e sulle segmentazioni appartenenti al gruppo 1.

La colonna “Mod. Evoluzione” identifica la modalità di evoluzioneutilizzata ed i suoi valori hanno il seguente significato:

full Si consente di apportare modifiche all’intera griglia di tasselli ad ognigenerazione.

39 Gestione delle intersezioni

ws Si utilizza il metodo basato sui working sets.

Dai dati si osserva che usando il metodo basato su working sets siriscontra una leggera riduzione del tempo di esecuzione a scapito di unadiminuzione degli indicatori utilizzati nella valutazione, per questo motivosi è preferito utilizzare la modalità di esecuzione full per le altre varianticonsiderate.

5.3 Gestione delle intersezioni

Per valutare l’influenza della gestione delle intersezioni sulla qualità dellesegmentazioni sono stati considerati contemporaneamente i dati prove-nienti da tutte le varianti testate. I risultati in tabella riguardano i valoriottenuti dalla valutazione delle segmentazioni appartenenti ai gruppi 1 e3, ossia le segmentazioni aventi migliore in ed out-tile color dissimilaritypresenti all’interno del fronte di Pareto e le segmentazioni ottenute daqueste mediante gestione delle intersezioni.

Tabella 5.3: Confronto tra le varie modalità di gestione delle intersezioni

Mosaico Gestione Int. Count Prec Rec Fm

bird max Area 0.20 49.4 50.2 49.7max OTD 0.18 49.7 48.8 49.1nessuna 0.29 59.9 63.5 61.3

church max Area 0.33 40.3 47.9 43.7max OTD 0.31 40.2 46.3 42.8nessuna 0.09 49.0 61.3 54.1

flower max Area 0.21 59.4 48.2 53.1max OTD 0.20 59.1 47.2 52.4nessuna 0.19 67.2 57.1 61.5

museum max Area 0.25 56.2 57.4 56.2max OTD 0.25 55.7 55.8 55.3nessuna 0.04 63.0 67.8 64.5

university max Area 0.27 50.4 55.3 52.1max OTD 0.28 49.5 52.9 50.3nessuna 0.19 55.9 65.9 59.3

I parametri in tabella costituiscono le medie rispetto alle esecuzioni ealle varianti.

5. Risultati 40

Dai dati si riscontra in generale una diminuzione degli indicatori pre-cision, recall e di conseguenza f-measure in seguito all’applicazione dell’al-goritmo di gestione delle intersezioni. Questo è dovuto al fatto che i primidue indici sono ottenuti mediante degli operatori di massimo sui tasselli:per ogni tassello della ground truth è solamente il poligono appartenentealla segmentazione da valutare che presenta il massimo valore dell’areadell’intersezione con il primo che da un contributo non nullo all’indice,chiamiamo M l’insieme dei poligoni aventi questa propietà. Rimuovendoun poligono possono verificarsi due casi: se questo appartiene aM si veri-ficherà una diminuzione degli indici, in caso contrario questi rimarrannoinvariati. In ogni caso il loro valore dopo l’applicazione dell’algoritmosarà minore o uguale a quello di partenza.

Le considerazioni sopra citate non valgono invece per l’errore di con-teggio: il valore di tale indice può infatti migliorare se nella segmentazioneconsiderata sono presenti più tasselli rispetto alla ground truth, cosa chesi verifica nel caso del mosaico bird.

5.4 Dimensione della popolazione

Per valutare l’influenza della dimensione della popolazione sono staticonfrontati i dati relativi alle seguenti varianti:

Tabella 5.4: Varianti utilizzate per stimare l’influenza della dimensione dellapopolazione


poligoni

2 griglia intera 20 si q. convessi6 griglia intera 50 si q. convessi4 griglia intera 100 si q. convessi

Dalla tabella si osserva che tutti i parametri sono stati mantenuticostanti eccetto la dimensione della popolazione.

Si riportano di seguito i risultati ottenuti in termini di metriche divalutazione e tempo di esecuzione per i vari mosaici.

41 Fronte di Pareto

Tabella 5.5: Influenza della dimensione della popolazione sulle metriche divalutazione

Mosaico Dim. Pop. Prec Rec Fm T (s)

bird 20 67.6 63.5 65.4 698250 67.7 63.3 65.5 18936100 68.3 63.0 65.5 37051

church 20 53.8 59.7 56.6 717950 54.4 58.3 56.3 17910100 54.8 57.8 56.3 37258

flower 20 73.4 56.8 64.1 573250 73.4 54.5 62.5 14000100 73.9 52.6 61.5 28662

museum 20 74.0 66.0 69.8 21650 74.3 67.5 70.7 607100 74.2 66.6 70.2 1222

university 20 70.2 66.6 68.3 22350 71.0 67.2 69.1 635100 71.6 67.1 69.3 1184

I valori riportati in tabella si riferiscono alla media degli indicatorieffettuata sulle varie esecuzioni e sulle segmentazioni appartenenti al pri-mo gruppo (migliore in ed out-tile dissimilarity senza l’applicazione dellagestione delle intersezioni).

Dai risultati si evince che il valore dell’indicatore precision tende adaumentare a discapito dell’indicatore recall al crescere della dimensionedella popolazione. Questo fatto fa si che l’andamento del parametro f-measure risultante rimanga pressoché costante in media. Si riscontrainoltre che il tempo di esecuzione aumenta in modo lineare rispetto alladimensione della popolazione.

5.5 Fronte di Pareto

Per valutare come le soluzioni ottenute sono distribuite all’interno delfronte di Pareto sono stati considerati i dati ottenuti da tutte le variantitestate. Si riportano i risultati nella seguente tabella

5. Risultati 42

Tabella 5.6: Distribuzione delle soluzioni all’interno del fronte di Pareto

Mosaico Soluzione Count Prec Rec Fm

bird Max Fm 0.29 59.9 63.7 61.4Min ITD 0.29 60.0 63.2 61.2Max OTD 0.29 59.7 63.8 61.3Min Fm 0.29 59.8 63.4 61.2

church Max Fm 0.09 49.0 61.5 54.2Min ITD 0.09 49.1 61.0 54.1Max OTD 0.09 48.9 61.6 54.1Min Fm 0.09 48.9 61.2 54.0

flower Max Fm 0.19 67.2 57.5 61.7Min ITD 0.19 67.4 56.8 61.4Max OTD 0.19 67.1 57.4 61.5Min Fm 0.19 67.3 56.9 61.3

museum Max Fm 0.04 63.2 68.4 64.8Min ITD 0.04 63.4 67.2 64.4Max OTD 0.04 62.7 68.4 64.5Min Fm 0.04 63.0 67.4 64.2

university Max Fm 0.19 56.1 66.5 59.6Min ITD 0.19 56.1 65.4 59.1Max OTD 0.19 55.8 66.5 59.4Min Fm 0.19 55.8 65.5 59.0

I valori in tabella si riferiscono alle medie rispetto alle esecuzioni, edeffettuate sulle segmentazioni identificate dalla colonna “Soluzione”, i cuivalori hanno il seguente significato:

Max Fm Segmentazione avente la migliore f-measure presente all’inter-no del fronte di Pareto.

Min Fm Segmentazione avente la peggiore f-measure presente all’inter-no del fronte di Pareto.

Min ITD Segmentazione avente il miglior valore del parametro in-tilecolor dissimilarity presente all’interno del fronte di Pareto.

Max OTD Segmentazione avente il miglior valore del parametro out-tilecolor dissimilarity presente all’interno del fronte di Pareto.

43 Formato del genotipo

Dai risultati si evince che la variabilità all’interno del fronte di Paretonon è elevata e che la soluzione avente la massima out-tile color dissi-milarity risulta quasi sempre migliore rispetto a quella avente la minorein-tile color dissimilarity. In conclusione si può dire che la prima risultauna buona candidata ad essere la segmentazione da fornire come outputal termine dell’algoritmo genetico.

5.6 Formato del genotipo

Per valutare l’influenza del formato del genotipo sugli indicatori si sonoconsiderati i dati ottenuti dalle seguenti varianti:

Tabella 5.7: Varianti utilizzate per confrontare i due formati del genotipo


poligoni

1 griglia intera 20 si rettangoli2 griglia intera 20 si q. convessi

Si espongono ora i risultati ottenuti

Tabella 5.8: Confronto tra i due formati del genotipo impiegati

Mosaico Formato Poligoni Prec Rec Fm T (s)

bird Quad. Convessi 67.6 63.5 65.4 6982Rettangoli 66.3 64.4 65.3 6747

church Quad. Convessi 53.8 59.7 56.6 7179Rettangoli 52.8 61.4 56.8 6901

flower Quad. Convessi 73.4 56.8 64.1 5732Rettangoli 72.0 57.9 64.2 5033

museum Quad. Convessi 74.0 66.0 69.8 216Rettangoli 73.8 66.2 69.8 196

university Quad. Convessi 70.2 66.6 68.3 223Rettangoli 69.3 68.4 68.9 180

I valori in tabella sono ottenuti effettuando delle medie sulle esecuzionie sulle segmentazioni appartenenti al gruppo 1.

Dall’analisi dei risultati si evince che utilizzando il formato basato suiquadrilateri convessi si ottengono dei valori degli indicatori precision e

5. Risultati 44

recall rispettivamente superiori ed inferiori rispetto al formato rimanente.Non ci sono differenze significative per quanto riguarda il valore dellaf-measure risultante.

Per quanto riguarda il tempo di esecuzione si è riscontrato un valoreinferiore utilizzando il formato basato sui rettangoli, il che è probabil-mente dovuto al fatto che questo richiede un minor numero di parametrie specifica una più semplice procedura di espressione del genotipo.

5.7 Inizializzazione della griglia

Per confrontare le due modalità di inizializzazione della griglia, ossia quel-la uniforme e quella basata su preprocessing sono state considerate leseguenti varianti:

Tabella 5.9: Varianti utilizzate per confrontare le modalità di inizializzazionedella griglia


poligoni

2 griglia intera 20 si q. convessi3 griglia intera 20 no q. convessi

Si espongono ora i risultati ottenuti:

Tabella 5.10: Confronto tra le due modalità di inizializzazione della grigliadei tasselli implementate

Mosaico Inizializzazione Count Prec Rec Fm T (s)

bird Uniforme 0.44 49.5 64.5 56.0 9608Preprocessing 0.17 66.3 64.4 65.3 6747

church Uniforme 0.18 42.6 64.2 51.2 8908Preprocessing 0.03 52.8 61.4 56.8 6901

flower Uniforme 0.42 60.3 62.5 61.4 10253Preprocessing 0.01 72.0 57.9 64.2 5033

museum Uniforme 0.07 48.4 72.5 58.1 197Preprocessing 0.02 73.8 66.2 69.8 196

university Uniforme 0.19 36.2 63.6 46.2 95Preprocessing 0.19 69.3 68.4 68.9 180

45 Confronto con TOS

I valori in tabella sono ricavati effettuando delle medie sulle esecuzionie sulle segmentazioni del gruppo 1.

Dai risultati si riscontra un significativo miglioramento della f-measuree dell’errore sul conteggio su tutti i mosaici. Questo è dovuto al fattoche utilizzando il preprocessing si ottiene una configurazione iniziale piùvicina a quella ottima agevolando quindi la convergenza dell’algoritmo.

5.8 Confronto con TOS

5.8.1 Confronto attraverso le metriche di valutazione

Si effettua ora il confronto tra l’algoritmo sviluppato e TOS [1], che risultail migliore tra gli agoritmi valutati nel lavoro [3] utilizzando i risultaticontenuti nello stesso paper.

Tabella 5.11: Confronto tra l’algotitmo TOS e quello svluppato in questolavoro (GA), i risultati riguardanti TOS sono ottenuti utilizzando il valore delparametro principale che massimizza l’indice f-measure

Mosaico Metodo Count Prec Rec Fm

bird TOS 0.03 52.8 81.7 64.2GA 0.17 68.3 63.1 65.5

church TOS 0.54 56.4 71.9 63.2GA 0.03 54.8 58.0 56.3

flower TOS 0.06 49.4 67.8 57.2GA 0.01 73.8 52.9 61.6

museum TOS 0.14 64.4 87.3 74.1GA 0.02 74.2 67.3 70.6

university TOS 0.90 63.2 78.5 70.1GA 0.19 71.7 67.6 69.5

I risultati ottenuti dal paper riguardanti l’algoritmo TOS sono sta-ti ricavati impostando come valore del parametro principale quello chemassimizza l’indice f-measure. Un’analisi per individuare quali sono i pa-rametri che portano alla migliore f-measure per l’algoritmo genetico non èstata effettuata per motivi di tempo, quindi il confronto che ci si accingead effettuare non è completamente equo. I parametri utilizzati sono statiquelli che consentono di ottenere un ragionevole errore sul conteggio.

I risultati presenti in tabella 5.11 riguardanti l’algoritmo sviluppato inquesto lavoro sono ottenuti considerando i dati provenienti dalla seguentevariante:

5. Risultati 46

(a) TOS (b) GA

Figura 5.7: Confronto tra la segmentazione migliore ottenuta tramite TOSe la segmentazione proveniente dall’algoritmo genetico avente la migliore out-tile dissimilarity presente all’interno del fronte di Pareto, alla quale è stato poiapplicata la gestione delle intersezioni

Tabella 5.12: Variante utilizzata per il confronto con TOS


poligoni

4 griglia intera 100 si q. convessi

I valori in tabella sono ottenuti effettuando una media tra i valoriprovenienti dalle varie esecuzioni e sulla segmentazione avente la miglioref-measure riscontrata nel fronte di Pareto senza applicare la gestione delleintersezioni.

Dai risultati ottenuti si evince che i valori della f-measure registratinei due casi sono simili, per quanto riguarda l’errore sul conteggio invecel’algoritmo genetico fornisce risultati generalmente migliori, in ogni ca-so dal confronto effettuato utilizzando le metriche oggettive non emergechiaramente un vincitore.

5.8.2 Confronto empirico

In figura 5.7 vengono mostrati i risultati provenienti dai due algoritmiottenuti in termini di segmentazioni del mosaico university.

Dalle figure si può notare che TOS, come tutti gli algoritmi conside-rati nel paper [3], fornisce come risultato una partizione dell’immagine.Una segmentazione di questo tipo non è completamente appropriata perrappresentare un mosaico in quanto un pixel dell’immagine può anchenon appartenere ad alcun tassello ma bensì ad una regione in corrispon-denza del filler. L’algoritmo genetico sviluppato in questo lavoro tiene

47 Confronto con TOS

invece conto di questo aspetto e quindi fornisce informazioni in più, con-sentendo di stabilire anche quali sono i pixel che non appartengono adalcun tassello.

Il fatto di fornire come risultato una partizione dell’immagine è inol-tre vantaggioso per quanto riguarda i risultati ottenuti in termini dellemetriche di valutazione. In questo caso infatti ogni tassello della groundtruth presenta intersezione non vuota con almeno un tassello della seg-mentazione. Nel caso dell’algoritmo genetico può accadere invece chealcuni tasselli della ground truth rimangano scoperti portando un con-tributo nullo alle metriche, fatto che è inoltre più probabile se si applical’algoritmo a posteriori di gestione delle intersezioni.

Capitolo 6

Conclusioni e sviluppi futuri

In conclusione si può dire che attraverso questa tesi si è esplorata l’ap-plicazione di tecniche basate sul calcolo evoluzionistico alla risoluzionedel problema della segmentazione di un mosaico, ottenuto un algoritmoche fornisce buoni risultati in termini di qualità empirica e paragonabi-le al miglior algoritmo considerato nel paper [3] per quanto riguarda lemetriche di valutazione oggettive.

In futuro si può considerare il raffinamento di diversi aspetti dell’al-goritmo e l’introduzione di ulteriori migliorie, tra le quali:

• Passaggio a formati del genotipo più espressivi rinunciando even-tualmente al vincolo della convessità dei poligoni.

• Introduzione della gestione delle intersezioni durante l’evoluzione.

• Implementazione di operazioni di accorpamento/differenza tra po-ligoni per gestire le intersezioni al posto della rimozione degli stessi.

• Raffinamento dell’algoritmo di preprocessing per l’inizializzazionedella griglia.

49

6. Conclusioni e sviluppi futuri 50

(a) Immagine originale

(b) Segmentazione

Figura 6.1: Esempio di segmentazione ottenuta dall’algoritmo genetico. Itasselli sono stati riempiti del colore medio presente dell’immagine originale incorrispondenza degli stessi

Bibliografia

[1] Lamia Benyoussef and Stéphane Derrode. Tessella-oriented segmen-tation and guidelines estimation of ancient mosaic images. Journal ofElectronic Imaging, 17(4):043014–043014, 2008.

[2] Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and Tanaka Meyari-van. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii. In Parallel problem solving fromnature PPSN VI, pages 849–858. Springer, 2000.

[3] Gianfranco Fenu, Nikita Jain, Eric Medvet, Felice Andrea Pellegri-no, and Myriam Pilutti Namer. On the assessment of segmenta-tion methods for images of mosaics. In Computer Vision, Imagingand Computer Graphics Theory and Applications (VISAPP), 10thInternational Joint Conference on, pages 130–137, 2015.

51

Segmentazione automatica di immagini di mosaici tramite tecniche di calcolo evoluzionistico

Engineering

Transcript of Segmentazione automatica di immagini di mosaici tramite tecniche di calcolo evoluzionistico