Segmentazione automatica di immagini di mosaici tramite tecniche di calcolo evoluzionistico -...

Universita degli studi di Trieste

Segmentazione automatica di immagini di mosaici tramitetecniche di calcolo evoluzionistico

Relatore

Prof. Eric Medvet

Correlatori

Prof. Gianfranco FenuProf. Felice Andrea Pellegrino

Candidato

Nicola Timeus

9 marzo 2016

Descrizione del problema

Segmentazione automatica di un mosaico:

I Si parte da un’immagine digitale rappresentante un mosaico.

I Si vogliono ottenere informazioni esplicite e strutturate sunumero, forma e dimensione dei tasselli.

2 of 45

Nicola Timeus - Segmentazione di mosaici tramite calcolo evoluzionistico

Descrizione del problema

Immagine originale Risultato desiderato

3 of 45


Motivazioni

I Una rappresentazione digitale consente di applicare le nuovetecnologie all’analisi, confronto e preservazione dei mosaici.

I La segmentazione manuale di un mosaico richiede molto tempo.

4 of 45


Motivazioni

In un lavoro precedente1 sono stati confrontati degli algoritmipresenti in letteratura utili a risolvere questo problema:

I Il confronto e stato effettuato tramite metriche oggettive.

I Il migliore algoritmo risulta essere TOS2.

I La differenza qualitativa tra i risultati dei vari algoritmi non esignificativa.

Sono state dunque sperimentate tecniche basate sul calcoloevoluzionistico.

1Fenu et al. 2015.2Benyoussef e Derrode 2008.

5 of 45


Algoritmi genetici

I Sono algoritmi di ottimizzazione che prendono spunto dallabiologia.

I Prevedono l’evoluzione di una popolazione di soluzioni ad undeterminato problema fino all’ottenimento di risultatisoddisfacenti.

6 of 45


Algoritmi genetici

Le soluzioni appartenenti alla popolazione sono dette individui.Ciascun individuo e contraddistinto da:

Fenotipo : Insieme delle caratteristiche esternamente visibili.

Genotipo : Insieme di parametri che identificano univocamente ilfenotipo soggetti a modifiche da parte degli operatoridi mutazione e crossover.

7 of 45


Algoritmi genetici

L’evoluzione e guidata dalla funzione di fitness

I Quantifica il grado di ottimalita di ogni individuo.

I Permette di stabilire dati due individui quale rappresenta lasoluzione migliore.

8 of 45


Segmentazione di un mosaico

I Il fenotipo di ogni individuo rappresenta una segmentazione.

I I tasselli vengono identificati da poligoni convessi.

I Il genotipo di ogni individuo e un insieme di geni gi , ciascunocodificante un poligono.

gi = (p1i , . . . , pki )

9 of 45


Genotipo

Sono stati sperimentati diversi formati per il genotipo:

I Specificano il numero e il significato dei parametri pij .

I Identificano una classe alla quale i poligoni devono appartenere.

I Specificano una procedura di conversione di ciascun gene in unarappresentazione indipendente dal formato (lista di vertici).

10 of 45


Formato basato su rettangoli

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

(xi,yi)

l1i

l2i

Φi

11 of 45


Formato basato su quadrilateri convessi

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

(xi,yi)

dx1i

dy1i

li

Φi

12 of 45


Funzione di fitness

Si e scelta una funzione di fitness vettoriale a due componenti:

I In-Tile Color Dissimilarity

I Out-Tile Color Dissimilarity

13 of 45


In-Tile Color Dissimilarity

Rappresenta la media sui tasselli della segmentazione dell’indicatore:

IT = σr + σg + σb

I Quantifica la variabilita del colore all’interno di un tassello.

I Da minimizzare.

14 of 45


Out-Tile Color Dissimilarity

I Quantifica la misura in cui il colore medio all’interno di un tassellosi discosta da quello presente in una regione esterna a ridosso delbordo.

I Da massimizzare.

15 of 45


Out-Tile Color Dissimilarity

Rappresenta la media sui tasselli della segmentazione dell’indicatore:

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

∣∣∣T e un poligono della segmentazione

T e un poligono ottenuto da T attraverso lo scalaggio diun fattore β = 1.2

16 of 45


In e Out Tile Color Dissimilarity

I Si e riscontrata correlazione tra il valore dei due indicatori e laqualita dei risultati ottenuti dai vari algoritmi.

I Forniscono informazione sulla difficolta intrinseca che si riscontranella segmentazione di un particolare mosaico.

17 of 45


Inizializzazione della griglia

1. Determinazione del baricentro (cxi , cyi ) e della dimensione diiniziali di ogni poligono (fase indipendente dal formato utilizzato).

2. Inizializzazione dei parametri pij di ogni gene a partire dai(cxi , cyi ) e di ottenuti dalla prima fase (fase dipendente dalformato).

18 of 45


Inizializzazione uniforme

I (cxi , cyi ) e di vengono inizializzati in modo tale da generare unagriglia uniforme di quadrati aventi la stessa lunghezza del lato

I Si richiede in ingresso un parametro davg che identifica ladimensione media dei tasselli.

I Il numero di poligoni e la relativa dimensione vengono calcolati inbase a davg.

19 of 45



Pro e Contro

3 Facile da implementare.

7 Non adatto ai casi in cui si riscontra un’elevata variabilita nelladimensione delle tessere.

20 of 45



21 of 45


Inizializzazione basata su preprocessing

Si tenta di individuare il valore dei parametri (cxi , cyi ) e di effettividel mosaico.

I Si utilizza un semplice algoritmo di blob detection multi scala.

I Si richiedono in ingresso i parametri rmin, rmax e rstep.

I Si ottiene una configurazione iniziale piu vicina a quella desideratarispetto al caso precedente.

22 of 45


Inizializzazione basata su preprocessing

23 of 45


Gestione delle intersezioni

I poligoni delle segmentazioni possono avere intersezione non vuota.

I Le intersezioni non sono state gestite durante l’evoluzione ma aposteriori.

I Si e utilizzato un algoritmo basato sulla programmazione lineare.

I Si rimuovono tasselli in modo da risolvere il problema delleintersezioni ottimizzando una funzione obiettivo lineare.

24 of 45


Valutazione della qualita delle segmentazioni

L’algoritmo ottenuto e stato testato sugli stessi mosaici consideratinel paper3.

I Per ciascun mosaico si ha a disposizione una segmentazioneground truth.

I Le segmentazioni ottenute sono state valutate con le metricheoggettive definite nel paper.

I I risultati sono confrontabili con quelli degli altri algoritmi.

3Fenu et al. 2015.

25 of 45


Metriche di valutazione oggettive

Data una segmentazione RI da valutare rispetto ad unasegmentazione ground truth TI

I RI deve contenere lo stesso numero di tasselli riscontrato in TI .

I I tasselli di RI devono contenere tutti e soli i pixel appartenenti aquelli di TI .

26 of 45


Errore sul conteggio

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

|TI |Quantifica in che misura il numero di tasselli di RI si discosta dalvalore risocontrato in TI .

27 of 45


Precision

Prec(RI ,TI ) =1

|TI |∑T∈Ti

maxR∈RI|R ∩ T ||R|

I I tasselli di RI devono contenere solo pixel appartenenti ai tassellidi TI .

28 of 45


Precision

T

R

T

R

29 of 45


Recall

Rec(RI ,TI ) =1

|TI |∑T∈Ti

maxR∈RI|R ∩ T ||T |

I I tasselli di RI devono contenere tutti i pixel appartenenti aitasselli di TI .

30 of 45


Recall

T

R

T

R

31 of 45


F-measure

L’indicatore f-measure e la media armonica degli indicatori precisione recall:

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

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

I Riassume i due indicatori in un singolo valore.

I Viene influenzato in misura maggiore dal peggior valore dei dueindicatori.

32 of 45


Procedura sperimentale

Finalizzata a:

I Valutare l’efficacia dell’algoritmo genetico nell’ottimizzare lafunzione di fitness.

I Verificare se esiste correlazione tra l’andamento della funzione difitness e le metriche di valutazione.

I Valutare l’influenza dei diversi parametri sulla qualita dellesegmentazioni.

I Confrontare i risultati ottenuti con quelli degli altri algoritmi.

33 of 45


Procedura sperimentale

I Sono state selezionate diverse varianti dell’algoritmo da testare.B Per variante si intende un insieme di parametri di configurazione.

I Per ogni mosaico e per ogni variante sono state effettuate piuesecuzioni utilizzando per ciascuna un random seed diverso.

34 of 45


Efficacia dell’algoritmo

0 2000 4000 6000 80000.16

0.18

0.2

0.22

0.24

0.26

0.28

0.3

Generation

In-T

ile D

issi

mila

rity

In-Tile DissimilarityGT In-Tile Dissimilarity

0 2000 4000 6000 8000-0.25

-0.24

-0.23

-0.22

-0.21

-0.2

-0.19

-0.18

GenerationO

ut-T

ile D

issi

mila

rity

Out-Tile DissimilarityGT Out-Tile Dissimilarity

35 of 45


Efficacia dell’algoritmo

Dai grafici si nota che:

I L’andamento della funzione di fitness e ”monotono“ decrescente.

I Il valore della funzione di fitness raggiunge e supera quelloriscontrato sulla ground truth.

Si puo concludere che l’algoritmo e efficace nell’ottimizzare lafunzione obiettivo.

36 of 45


Correlazione tra funzione di fitness e metricheoggettive

0 10000 20000 30000 400000.54

0.55

0.56

0.57

0.58

0.59

0.6

Generation

Pre

cisi

on

0 10000 20000 30000 400000.54

0.56

0.58

0.6

0.62

0.64

Generation

Rec

all

0 10000 20000 30000 400000.54

0.56

0.58

0.6

0.62

Generation

F-M

easu

re

37 of 45


Correlazione tra funzione di fitness e metricheoggettive

Dai grafici si nota una andamento ”monotono“ crescente di tutte lemetriche di valutazione.

I L’andamento dell’errore sul conteggio e stato trascurato in quantocostante.

I Tale tipo di andamento si verifica nella maggior parte delleesecuzioni in cui si e utilizzata l’inizializzazione uniforme.

I Utilizzando il preprocessing si riscontra un aumento dell’indicatoreprecision a discapito di recall.

38 of 45


Confronto con TOS

L’algoritmo ottenuto e stato confrontato con TOS

I Risulta il migliore tra quelli considerati nel paper precedentementecitato.

I Il confronto e stato effettuato con i risultati in termini di metricheoggettive presenti sullo stesso paper.

39 of 45


Confronto con TOS

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 40 of 45


Confronto con TOS

I I risultati in termini di f-measure sono simili.

I Per quanto riguarda l’errore sul conteggio l’algoritmo geneticosembra migliore.

I Non emerge chiaramente un vincitore.

41 of 45


Confronto con TOS

TOS GA

42 of 45


Confronto con TOS

TOS a differenza dell’algoritmo genetico fornisce come risultato unapartizione dell’immagine.

I I tasselli di un mosaico non formano una partizione dell’immagine.

I L’algoritmo genetico consente di identificare quali sono i pixel chenon appartengono ad alcun tassello, fornisce quindi piuinformazione.

I Fornire una partizione dell’immagine e vantaggioso rispetto allemetriche oggettive.

43 of 45


Immagine originale Segmentazione

44 of 45


Conclusioni

Applicando le tecniche basate sul calcolo evoluzionistico al problemadella segmentazione di un mosaico si e ottenuto un algoritmo che

I Fornisce risultati soddisfacenti sia in termini di qualita empiricache di metriche di valutazione.

I Fornisce informazioni in piu rispetto a TOS.

45 of 45


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 -...