Politecnico di Torino - elite.polito.itelite.polito.it/files/thesis/fulltext/dettori.pdf · Si...

Politecnico di Torino

Facoltà di Ingegneria

Corso di laurea in Ingegneria Informatica

Dipartimento di Automatica e Informatica

L'Active Shape Model applicato all'Eye Tracking: analisi di immagini

Tesi di Laurea di Giovanni Dettori Relatori: Prof. Fulvio Corno

Prof. Laura Farinetti

Anno accademico 2005/2006


Ai miei genitori, a Olimpia

2


Sommario

La percezione visiva attraverso l'analisi di immagini bidimensionali acquisite da comuni

telecamere è l'obiettivo principale perseguito dalla computer vision: il riconoscimento

delle forme presenti aiuta a comprendere la scena ripresa e, di conseguenza, permette di

operare delle scelte. Risulta evidente che il raggiungimento di questo risultato espanderà

notevolmente i campi di utilizzo delle tecnologie informatiche.

In un'immagine la ricerca di pattern avviene attraverso l'individuazione di forme e di li

nee al suo interno. Un semplice oggetto, ripreso per più frame consecutivi, presenta delle

differenze anche tra un frame e l'altro e, con il variare della posizione, della forma e

dell'ambiente, il riconoscimento è reso ancora più difficoltoso.

Si cerca di ovviare a questa variabilità ricorrendo a informazioni ulteriori, acquisite a

priori, che possono maggiormente discriminare e migliorare la percentuale di riconosci

mento.

Scopo di questo lavoro è l'implementazione di un algoritmo di analisi di immagini che,

integrato con un modello di forme variabili prestabilite, possa essere utilizzato nel rico

noscimento della forma dell'occhio. Questa informazione permette di rilevare la direzio

ne verso cui guarda l'operatore e, pertanto, l'ausilio offerto all'utente nell'interfacciamen

to con l'elaboratore si potenzia notevolmente, attraverso l'utilizzo di queste tecniche,

aprendo nuovi scenari nell'interazione uomo-computer.

L'Active Shape Model è una tecnica di riconoscimento locale basata su un modello ma

tematico della forma da riconoscere e su un algoritmo di analisi delle immagini. L'algo

ritmo di gestione della forma (Shape) riceve ad ogni iterazione i risultati dell'algoritmo

analizzante e, in base a questi risultati, decide in quale direzione il modello debba muo

3


versi nello spazio dei suoi autovettori, per avvicinarsi ai risultati dell'analisi.

Il risultato di questo adattamento è l'input dell'algoritmo di analisi per la successiva ite

razione. Il ciclo si interrompe, sia al raggiungimento di una soglia minima, sia al supera

mento di un certo numero di iterazioni.

La tesi svolta ha cercato di elaborare un algoritmo in grado di implementare la parte di

analisi di immagini statiche a colori, nel rispetto di vincoli temporali e ambientali, per

l'individuazione dei punti che permettono la rilevazione della forma dell'occhio.

Dall'analisi della letteratura esistente è stato determinato l'algoritmo da implementare: la

semplice immagine RGB è stata elaborata con tecniche derivative e di normalizzazione,

finalizzate a filtrare la variabilità del mondo reale.

L'algoritmo è stato integrato nell'applicazione di Eye Tracking esistente, per verificarne

e ottimizzarne la funzionalità.

I risultati ottenuti dimostrano la validità della teoria e, quindi, una convergenza del mo

dello alla posizione dell'occhio in immagini reali. Si sono riscontrate delle difficoltà con

posizioni e con situazioni di luce non previste nel training-set, ma con l'utilizzo di ele

menti del training-set che meglio si adattavano alla situazione e l'introduzione di una

sorgente di luce costante, si è cercato di limitare l'influenza della variabilità ambientale.

4


Indice generale

1 Introduzione................................................................................................................................ 3

1.1 Struttura della tesi................................................................................................................5

2 Eye Tracking................................................................................................................................7

2.1 Potenzialità dell'Eye Tracking............................................................................................. 8

3 Computer Vision e approcci al riconoscimento di forme.........................................................12

3.1 Modello matematico per punti (PDM=Point Distribution Model)................................... 20

3.1.1 Analisi delle componenti principali (PCA)...............................................................22

3.2 Tecniche di Shape Learning.............................................................................................. 24

3.2.1 Applicazione dell'ASM: metodo di ricerca locale.................................................... 28

3.3 Conclusioni........................................................................................................................32

4 Studio del sistema Eye Tracking esistente e requisiti del progetto........................................... 33

4.1 Analisi del problema e dei requisiti...................................................................................33

4.2 Struttura generale del sistema............................................................................................38

4.2.1 Studio dell'applicazione “Training” ......................................................................... 40

4.2.1.1 Metodo per la creazione del training-set...........................................................41

5 Verifica...................................................................................................................................... 45

5.1 Algoritmi implementati .................................................................................................... 45

5.1.1 Metodo di creazione dei greylevel............................................................................ 45

5.1.2 Lunghezza e larghezza dei greylevel.........................................................................48

5.1.3 Greylevel derivato e normato.................................................................................... 50

5.1.4 Metodo di ricerca globale..........................................................................................51

5.1.4.1 Algoritmo di ricerca della forma.......................................................................51

5.1.4.2 Suddivisione della ricerca in due fasi............................................................... 53

5.1.4.3 Fase 1: ricerca della forma nell'immagine........................................................ 54

5.1.4.4 Fase2: affinamento della forma.........................................................................56

1


5.1.5 Metodo di ricerca locale: determinazione della forma..............................................61

5.1.6 Strutture dati per la ricerca del greylevel di confronto............................................. 66

5.1.6.1 Struttura ad albero............................................................................................. 66

5.1.6.2 Memoria associativa.........................................................................................70

5.1.7 Sviluppo del codice critico in Assembler..................................................................73

5.1.7.1 Set di istruzioni MMX e SSE............................................................................73

5.2 Valutazioni sperimentali e possibili sviluppi.................................................................... 79

5.2.1 Valutazione dell'efficacia del riconoscimento: distanza euclidea.............................79

5.2.2 Valutazione del funzionamento.................................................................................81

6 Conclusioni................................................................................................................................ 91

7 Bibliografia................................................................................................................................ 94

2


1 Introduzione

Riuscire a comunicare in modo naturale con i computer è un obiettivo perseguito dal

l'Information Tecnology per le grandi potenzialità che questo comporterebbe.

Chiunque sia il nostro interlocutore, per interagire correttamente, ha bisogno di com

prendere come è fatto il mondo che lo circonda: per i computer è necessaria l'implemen

tazione di una tecnologia finalizzata al riconoscimento delle immagini in modo che l'ela

boratore, analogamente a quanto facciamo noi esseri umani, riesca a capire il contesto e

la situazione in cui si trova.

Gli esseri umani agiscono e determinano i loro comportamenti anche in base alla valuta

zione della situazione, attraverso il riconoscimento di pattern, ossia di entità che posso

no essere suoni, sensazioni tattili, o attraverso la vista individuando le forme percepite.

Il canale visivo è senz'altro un canale prioritario, ricco di informazioni e molto variabile

nei suoi contenuti.

Interpretare le immagini per un computer diventa, quindi, un traguardo molto comples

so: una strada percorribile è la realizzazione, almeno all'inizio, di software che assolvano

parzialmente a questo compito.

La nostra strategia sarà quella di interpretare le immagini individuando forme al loro in

terno, e pertanto, visto il numero elevato di forme esistenti, è evidente quanto sia com

plesso questo traguardo.

In tale contesto il progetto generale, in cui si colloca il lavoro svolto con questa tesi, fo

calizza l'attenzione sulla ricerca di un sistema di puntamento basato sullo sguardo dell'u

tente. Una tappa obbligata per il raggiungimento di questo obiettivo consiste nell'indivi

duazione dei tratti significativi del volto e degli occhi.

3


Questa finalità associata agli ausili che si possono realizzare nella sfera dell'handicap ri

guarda l'implementazione di sistemi in grado di rendere più autosufficienti i disabili mo

tori gravi nelle loro attività espressive e di comunicazione. Le tecnologie possono ri

spondere ai bisogni specifici delle persone disabili con la realizzazione di software e

hardware che permettano l'accessibilità al computer per svolgere funzioni altrimenti pre

cluse.

La complessità di un sistema che favorisca l'interazione uomo-computer comporta una

suddivisione del problema, per concentrare le risorse su aspetti più specifici.

Quindi il lavoro ha come punto di partenza gli algoritmi e i programmi già sviluppati nel

progetto generale. Queste basi permettono una maggiore attenzione al problema specifi

co relativo allo sviluppo di un algoritmo che possa analizzare le immagini statiche, fina

lizzato alla ricerca dei contorni dell'occhio. Successivamente la soluzione sarà integrata

nel programma di Eye Tracking esistente per seguire i movimenti dell'occhio e dell'iride,

dai quali si possa estrapolare la direzione verso cui guarda l'operatore.

Poiché si intende minimizzare l'utilizzo di strumentazioni hardware sofisticate e, al tem

po stesso, si vuole ricercare una soluzione economica ma efficace, verranno studiate tec

niche inerenti alla computer vision.

Per quanto riguarda la soluzione da ricercare verranno valutate due tecniche di analisi di

immagini esistenti, l'Active Shape Model (ASM) e l'Active Appareance Model (AAM)

e, in base alle informazioni raccolte, si procederà con la più promettente, prevedendo

ulteriori approfondimenti in caso di un risultato non soddisfacente.

Si vuole dimostrare l'applicabilità del metodo anche al riconoscimento di forme molto

variabili, come quella dell'occhio, e si studieranno adattamenti e modifiche agli studi in

dicati, come per esempio attraverso l'introduzione di immagini a colori.

4


Poiché le due tecniche da studiare prevedono un modello della forma da riconoscere ge

nerato da un training-set, si proverà ad utilizzare singolarmente tutti gli elementi appar

tenenti ad esso per la ricerca della forma, in modo da massimizzare la percentuale di ri

conoscimento e adattamento alla shape reale.

Il problema della scelta dell'ambiente di sviluppo non si pone, in quanto il progetto è

stato sviluppato con l'ambiente Microsoft Visual Studio utilizzando il linguaggio C++ .

I programmi “Training”, per la creazione del training-set, ed “Eye Tracking”, per la ri

cerca della forma in real-time, sono il punto di partenza del lavoro e verranno studiati

per poter correttamente integrare la procedura di analisi da sviluppare.

L'uso di immagini a colori e la ricerca di una soluzione con tempistiche compatibili con

una applicazione reale impongono, per quanto possibile, un'attenzione particolare all'ot

timizzazione del codice: durante lo sviluppo si adotteranno algoritmi e strutture dati

idonee allo scopo.

1.1 Struttura della tesi

Il testo si articola in cinque capitoli i cui argomenti sono sviluppati seguendo un proce

dimento top-down. Dopo il capitolo introduttivo, il secondo espone brevemente le po

tenzialità delle attuali tecniche di Eye Tracking con qualche riferimento alle implemen

tazioni presenti sul mercato.

Nel terzo capitolo, dopo una panoramica delle tecniche di computer vision esistenti fi

nalizzate all'interpretazione di forme in immagini acquisite, viene affrontata la teoria

dell'Active Shape Model su cui si basa questa tesi.

Nel quarto capitolo si analizza il problema dell'Eye Tracking mettendo in evidenza i re

5


quisiti che l'algoritmo analizzante deve soddisfare per dimensionare correttamente il si

stema. Viene, inoltre, descritto il programma di Eye Tracking su cui è stato integrato

l'algoritmo di analisi sviluppato.

Il quinto capitolo descrive la realizzazione finale raggiunta in base ai requisiti preceden

temente definiti e riporta alcuni risultati sperimentali a dimostrazione degli obiettivi

conseguiti. Vengono descritte nel dettaglio le strutture dati utilizzate e i loro limiti ripor

tando il codice significativo che implementa le idee espresse. Inoltre, è stata effettuata

una valutazione delle potenzialità dell'algoritmo attraverso diversi test, per determinarne

le condizioni di massima efficacia.

Nel sesto capitolo vengono esposte le conclusioni a cui ha condotto questo lavoro, ri

prendendo sia gli obiettivi e le ipotesi qui introdotte, sia le considerazioni e gli eventuali

miglioramenti del programma.

6


2 Eye Tracking

Vista la centralità dell'informazione nelle attività umane si possono comprendere le

grandi potenzialità dell'Informatica: qualunque aspetto della nostra vita comporta un

processo di trattamento di informazioni costituito da una fase di acquisizione, una di ela

borazione ed un'eventuale fase di attuazione. Potenzialmente queste elaborazioni posso

no essere simulate dall'Informatica attraverso degli algoritmi più o meno complessi che,

in molte situazioni, producono risultati migliori di quanto non riesca a fare l'essere uma

no.

Esistono, però, ancora molte attività umane in cui l'Informatica non è competitiva per

ché, anche se in costante evoluzione, non dispone di quelle infrastrutture necessarie ad

implementare algoritmi capaci di simulare le attività più complesse dell'uomo.

L'evoluzione tecnologica include non solo il miglioramento dell'hardware, che si vuole

sempre più potente in termini di elaborazione e capacità di memorizzazione, ma com

prende anche l'aspetto gestionale di problemi complessi; basti pensare che per la realiz

zazione di un Sistema Operativo contemporaneo, necessario alla gestione fondamentale

del computer, debba lavorare un team composto da centinaia se non migliaia di persone.

L'orientamento dell'Informatica verso lo sviluppo di algoritmi in grado di simulare i pro

cessi cognitivi dell'essere umano ha come obiettivo principale il miglioramento della

qualità della vita dell'uomo, semplificando tutti quegli aspetti ripetitivi che lo distolgono

da attività più creative.

In questo senso l'Informatica può contribuire al nostro processo di evoluzione e, in mol

ti aspetti, può aiutare e accelerare lo sviluppo delle società. Ad esempio le forze dell'or

dine adottano frequentemente tecnologie informatiche, come nella catalogazione di im

7


pronte digitali per individuare gli autori di un crimine, o nell'uso di algoritmi in grado di

riconoscere i volti umani per individuare le persone al loro passaggio.

Questi obiettivi primari possono essere perseguiti per gradi e, certamente, uno di essi

consiste nel potenziamento delle modalità di interfacciamento con l'elaboratore.

La scienza che studia l'interazione tra uomo e computer è la Human Computer Interac

tion, il cui fine è l'incremento della produttività creativa dell'uomo attraverso un comple

to utilizzo delle potenzialità dei computer. Essa cerca soluzioni hardware e software che

possano migliorare l'interazione con il computer, sia negli aspetti strettamente ergonomi

ci, sia in quelli orientati all'organizzazione dei contenuti. Innanzitutto bisogna considera

re cosa rende più efficace e naturale un'interfaccia rispetto ad un'altra. Purtroppo non esi

ste una risposta univoca, visto che molti fattori socio-culturali possono influire nella so

luzione: l'intuitività di un'interfaccia grafica dipende dall'interpretazione individuale data

agli oggetti in essa contenuti.

Un canale prioritario nell'interazione uomo-computer è senza dubbio quello visivo, e in

questo contesto si colloca l'Eye Tracking che mira a interagire più efficacemente con il

computer e, al tempo stesso, ad acquisire molte informazioni utili in vari ambiti di se

guito accennati.

L'Eye Tracking è una tecnica che ha l'obiettivo di inseguire la posizione dell'occhio per

l'individuazione della direzione in cui l'utente guarda.

2.1 Potenzialità dell'Eye Tracking

L'Eye Tracking viene usata in molte attività di ricerca, come la Human Computer Inte

raction, la medicina, la pubblicità, l'aeronautica, la psicologia e nello studio di ausili per

8


persone con handicap motori gravi.

I movimenti oculari rilevanti si distinguono in tre categorie: la fissazione, vale a dire la

capacità di mantenere ferma la direzione verso cui guarda l'occhio, i movimenti di pur

suit (inseguimento), cioè la capacità dell'occhio di seguire un oggetto in movimento, e,

infine, i movimenti saccadici, ovvero movimenti volontari o involontari dell'occhio at

tuati per spostare l'attenzione da un punto a un altro.

Si comprende che si ottiene la maggior quantità di informazione in fase di fissazione,

nella quale l'occhio punta una zona ritenuta interessante.

Esistono diversi modi per catturare lo sguardo: il più usato e testato prevede l'utilizzo di

un emettitore ad infrarossi, le cui riflessioni sulle pupille degli occhi vengono rilevate

facilmente da una telecamera. L'analisi di queste immagini permette la localizzazione

dell'occhio, e una successiva triangolazione dei punti individuati consente di calcolare la

direzione verso cui guarda l'utente.

Un'altra tecnica di Eye Tracking consiste nell'analizzare con algoritmi di computer vi

sion l'immagine ripresa da una normale telecamera ed interpretarne il contenuto, per rile

vare la posizione e la forma dell'occhio e, al suo interno, la posizione della pupilla.

La maggior parte dei prodotti esistenti oggigiorno sul mercato si basa sulla tecnologia ad

infrarossi, anche se risulta relativamente costosa e si differenzia solo per il grado di in

vasività dei sistemi utilizzati nel rilevare la riflessione. La loro limitata sensibilità e pre

cisione di rilevamento comporta la necessità di ravvicinare il sensore al soggetto da con

trollare.

Alcuni prodotti invasivi usano un casco analogo a quello dei ciclisti su cui viene monta

ta la telecamera; altri addirittura impongono l'immobilità della testa in una struttura, in

modo da limitarne i movimenti e permettere al sistema di essere più preciso e stabile; al

9


tri ancora utilizzano degli occhiali su cui vengono fissati una mini-telecamera ed un

emettitore ad infrarossi.

I metodi non invasivi, anche se utilizzano sempre emettitori ad infrarossi, collocano la

telecamera in prossimità del monitor, rendendo di conseguenza i movimenti dell'utente

più naturali.

Questa spontaneità rende più significativa l'analisi dei comportamenti dell'operatore, dai

quali si può dedurre una serie di informazioni utili.

In medicina, per esempio, diventerà possibile la consultazione dei referti indicandoli con

lo sguardo e specificando verbalmente l'azione che si vuole fare: questo consentirà ai

medici di eseguire un'attività diretta sul paziente e, allo stesso tempo, di visionare i do

10

Illustrazione 2.1

Illustrazione 2.2


cumenti digitalizzati.

In campo pubblicitario, l'Eye Tracking permette di capire se una pubblicità suscita inte

resse e, in particolar modo, quali immagini al suo interno risultano più efficaci. Questa

analisi viene applicata anche nello studio delle interfacce di siti web, per comprendere

come si dovrebbero organizzare le pagine: vengono utilizzate le registrazioni di tutti i

movimenti oculari durante la navigazione, i cosiddetti scanpath, dai quali si deducono i

comportamenti collettivi relativi al modo di visitare il sito, individuando gli elementi di

maggior interesse. Inoltre, con queste informazioni, si riesce a capire come utilizzare le

aree della pagina web per stimolare più efficacemente gli utenti.

Le applicazioni di Eye Tracking nel campo delle interfacce uomo-computer iniziano ad

essere presenti con la funzione di sostituire il mouse come dispositivo di puntamento; ne

sono esempi la navigazione virtuale 3D, i video-games e la gestione di una casa domoti

ca, in cui è possibile effettuare le normali attività attraverso l'uso congiunto di voce e

sguardo. Nel contesto aeronautico-militare questa tecnologia è integrata nei caschi in

dotazione ad alcuni reparti e consente una velocità di azione maggiore, determinante ai

fini delle stesse missioni.

Si stanno sviluppando nuove applicazioni che permettono l'accessibilità alle tecnologie

anche a coloro che hanno bisogno di strumenti specifici per sopperire ad un deficit.

L'accesso alle tecnologie può contribuire a favorire l' autonomia dei disabili, per ridurre

in parte le loro difficoltà; ad esempio negli handicap motori gravi è possibile controllare

il mouse o la tastiera con le potenzialità del sistema visivo: l'Eye Tracking è inserita in

alcuni dispositivi per persone che non possono usare queste periferiche, consentendo

loro di utilizzare il computer per comunicare, lavorare e migliorare la qualità della loro

vita.

11


3 Computer Vision e approcci al riconoscimento di for

me

Lo sviluppo di tecnologie che consentono di interpretare le immagini acquisite da una

webcam proietta il computer in nuovi campi applicativi. Gli sforzi del mondo scientifico

nella computer vision sono imponenti e si iniziano a vedere i primi risultati, grazie an

che alle crescenti potenzialità dei computer utilizzati.

Per capire la funzione della Computer Vision può essere utile evidenziare un aspetto che

la differenzia dall'elaborazione di immagini digitali (Digital Image Processing). L'elabo

razione di immagini digitali ha come obiettivo la trasformazione di un'immagine, per

evidenziare qualche aspetto in essa contenuto e, quindi, il prodotto finale continua ad es

sere un'immagine digitale. Un esempio di trasformazione può produrre un'immagine con

un rumore ridotto, o con i contrasti accentuati, oppure può separare meglio gli oggetti

dallo sfondo.

La computer vision, invece, ha lo scopo di ricavare informazioni qualitativamente più

elevate con l'obiettivo di comprendere l'immagine per individuare, ad esempio, qualche

pattern in essa contenuto. L'output di questa elaborazione non è, quindi, un'immagine,

ma un'informazione contenuta, rendendo l'elaborazione simile ai processi cognitivi del

l'essere umano nella percezione visiva.

Una modalità di elaborazione inclusa nelle tecniche di computer vision è la Pattern Re

cognition che ha come obiettivo il riconoscimento di forme all'interno delle immagini

analizzate.

Nell'ambito del Pattern Recognition, per effettuare un riconoscimento, si deve anteporre

una fase di definizione della “classe” che, in qualche modo, distingue i pattern ad essa

12


appartenenti dal resto degli altri possibili.

Un altro aspetto da sottolineare è la difficoltà di assegnare questi pattern a classi distinte.

Il problema nella categorizzazione è dovuto a diversi fattori:

– l'interpretazione del contesto che determina molte volte il significato della stessa

forma. Per esempio nel riconoscimento di una bottiglia su un tavolo o di una botti

glia raffigurata in un quadro, la presenza della cornice nell'immagine rende il si

gnificato della stessa forma diverso;

– le differenze che due immagini dello stesso oggetto possono avere tra loro;

– le differenze di forma, posizione che l'oggetto può avere;

– il rumore generato dal contesto.

Queste problematiche determinano la difficoltà di associare un pattern ad una classe e,

di solito, si usa una o più soglie con le quali deciderne l'appartenenza o meno. Esiste

anche il problema dei falsi riconoscimenti e del non riconoscimento di pattern corretti

che, ovviamente, devono essere di numero esiguo.

In molte situazioni la complessità computazionale porta al compromesso, limitando le

forme da riconoscere, la risoluzione delle forme o le percentuali di falsi riconoscimenti.

La classificazione di pattern si può realizzare in vari campi, con il solo vincolo dettato

dai computer di trasformare in digitale l'entità da riconoscere. Per esempio possono esse

re dei pattern i suoni, i volti delle persone, degli oggetti in ambito industriale, delle lastre

ospedaliere o i segnali provenienti da sensori di movimento dislocati in un ambiente.

Esistono diverse metodologie per affrontare la complessità insita nel riconoscimento di

pattern. Questi metodi più o meno complessi si prestano a situazioni specifiche, quindi è

necessario valutare correttamente quale sia il metodo migliore per affrontare il problema

da risolvere.

13


Gli approcci al riconoscimento di forme sono quattro: Approccio Statistico, Approccio

Strutturale, Reti Neurali, Template Matching.

La tecnica dell'approccio statistico consiste nell'estrarre delle caratteristiche dagli oggetti

presenti nell'immagine, come il baricentro dell'oggetto, e con esse si decide se l'oggetto

da valutare appartiene o meno alla classe da ricercare. Per esempio, in immagini mono

cromatiche, dopo aver calcolato il baricentro, si misura l'estensione dell'oggetto in tutte

le direzioni e, in base a questo valore, si può discriminare tra oggetti lunghi e corti.

Queste tecniche vengono usate in contesti industriali in cui gli oggetti sono relativamen

te semplici, conosciuti nelle loro forme e facilmente osservabili.

L'approccio strutturale mira in una prima fase ad estrarre delle informazioni sulla morfo

logia dell'immagine da analizzare (componenti primitive); queste informazioni vengono

comparate con quelle presenti in un database. Un esempio di una possibile applicazione

di questa metodologia è il riconoscimento delle impronte digitali. Nell'analisi si valuta la

direzione delle linee appartenenti all'impronta e, in base al loro andamento, vengono in

dividuate delle aree accomunate da analoghi andamenti. I baricentri di queste aree for

mano un grafo strettamente associato all'impronta digitale: le comparazioni di queste

strutture individuano la compatibilità o meno con quelle presenti nel database.

14

Illustrazione 3.1


Le reti neurali sono un'implementazione in scala ridotta delle funzionalità possedute dal

le reti neuronali del cervello. Esistono diversi tipi di implementazioni, ma la maggior

differenza risiede nel tipo di apprendimento che può essere guidato da un training-set,

oppure ad autoapprendimento. Le connessioni sono simulate da un numero chiamato

“peso” che varia a seconda che si debba rafforzare o meno quella specifica connessione.

Le reti neurali trovano applicazioni in quelle situazioni in cui non si riesca a formalizza

re il problema con un idoneo algoritmo che normalmente ha tempi di risposta migliori e

determinati.

L'ultimo approccio è quello del Template Matching che si basa nella ricerca di una corri

spondenza tra immagini o forme (template) di riferimento, presenti in un database, e im

magini all'interno delle quali ricercare questi template.

L'appartenenza o meno di un template alla categoria ricercata avviene attraverso una

funzione di valutazione.

15

Illustrazione 3.2


La tecnica Template Matching si suddivide in due grandi categorie:

• Rigid Template Matching

• Deformable Template Matching

L'approccio rigido consiste nel ricercare una forma o un'immagine senza modificarla, ef

fettuando al massimo delle rotazioni e dei rapporti di scala. La ricerca viene fatta con

una misura di correlazione o con la trasformata di Hough.

La correlazione consiste, in termini matematici, nella Somma dei Quadrati delle Diffe

renze ed, operativamente, comporta un posizionamento ed una successiva comparazione

pixel per pixel tra l'immagine campione I e l'immagine da controllare C.

Formula 3-1

Esistono anche funzioni di correlazione che tengono conto della variabilità energetica

che possono avere le due immagini da correlare:

Formula 3-2

.

Esempi di applicazioni reali in cui è possibile attuare il confronto attraverso la correla

zione è il riconoscimento delle targhe automobilistiche che non sono soggette a defor

mazioni dei caratteri delle stesse, né a loro rotazioni. Con qualche difficoltà in più è pos

sibile riconoscere forme più variabili, come componenti elettronici che si possono pre

sentare anche ruotati rispetto all'immagine campione da ricercare. In questo caso prima

della ricerca con il metodo della correlazione è necessario ruotare matematicamente i pi

16

∥I−T∥2

∥I−T∥2/∥I∥∥T∥


xel dell'immagine campione.

Un'altra strada percorribile si basa sulla proprietà che fa equivalere la correlazione nel

dominio del tempo o dello spazio (x,y) ad una semplice moltiplicazione nel dominio

delle frequenze (u,v). Si deve comunque tener conto della complessità computazionale

dei due algoritmi e del fatto che la moltiplicazione nel dominio delle frequenze compor

ta una trasformata di Fourier, un calcolo in floating point ed un'antitrasformata di Fou

rier.

Formula 3-3

La trasformata di Hough è una tecnica di matching esatto e, quindi, idonea al riconosci

mento di pattern identici al modello e, prestandosi bene al riconoscimento di forme geo

metriche, risulta stabile ad occlusioni parziali, al rumore e a sfondi non uniformi.

Si parte dalla forma parametrica di un pattern da ricercare ( per esempio una circonfe

renza r2=x2−xc2y2−yc2 ) e dall'individuazione dei contorni (edge detection)

presenti nell'immagine. Ogni punto di questo contorno si assume potenzialmente appar

tenente alla forma da ricercare, e per ciascuno di essi si calcola con quanta probabilità

appartiene al pattern da ricercare. Nello spazio dei parametri n-dimensionale (nell'esem

pio r,xc,yc) discretizzato, a cui ogni punto corrisponde una forma, si determina a quali

punti può appartenere il pixel considerato: al termine il punto nello spazio dei parametri

(r,xc,yc) con il maggior numero di pixel associati, individua il pattern ricercato nell'im

magine. Il riconoscimento può essere affetto da errore e, quindi, si deve sempre stabilire

una soglia per decidere se il matching è attendibile.

17

corr f , gx , y=F−1{F u , v∗Gconiugata u , v}


Un altro approccio al riconoscimento di pattern impiega i template deformabili. Questo

metodo è necessario in quelle situazioni in cui i pattern da ricercare hanno una qualche

variabilità che deve essere ricercata o inseguita. Per questo motivo i template sono più

complessi e necessitano di un maggiore sforzo per essere implementati.

Schematicamente le tecniche con template deformabili si distinguono in:

– free form

– parametric

– analitic form

– shape learning

I template free-form sono dei modelli deformabili che possono evolvere liberamente in

base a certe regole.

Una di queste tecniche è L'Active Contour Model , il risultato del lavoro introdotto da

Kass et al. nel 1987 [rif 7].

Le curve utilizzate sono delle spline ( v(s)=[x(s),y(s)] ) che vengono inizialmente

posizionate sull'immagine e ad esse viene associata un'energia calcolata rispetto

all'immagine da analizzare: E(snake)=E(interna)+E(esterna)+E(forze di vincolo). La

forma si adatta all'immagine minimizzando l'energia totale.

• E(interna)=Somma di energia elastica e di energia di piegatura, che dipende dai para

metri della spline.

• E(esterna)=energia associata all'immagine di solito calcolata in base al suo gradiente

in un intorno della spline.

• E(forze esterne di vincolo)= energia associata ad altre eventuali componenti esterne.

18


Le tecniche parametriche

L'Analitic-Form based è un metodo basato su tecniche parametriche di controllo della

forma. Si descrive la forma e la sua deformabilità in modo matematico attraverso l'uso

di curve, linee, spline e loro combinazioni. Alcuni parametri ne permettono la modifica

e, quindi, l'adattamento di queste linee alla forma presente nell'immagine. [ A.L. Yuille,

P.W. Hallinan, and D.S. Cohen ].

L'ultima classificazione da valutare è quella relativa alle tecniche basate sull'acquisizio

ne della forma da riconoscere. Esistono almeno due tecniche che si basano sull'apprendi

mento della forma e sulla sua traduzione in un modello controllato da pochi parametri

che tiene conto della sua variabilità:

• Metodo per individuare oggetti 2d Region Based

• Active Appearance Model (AAM) [rif.4]

• Metodi per individuare oggetti 2d Contour Based

• Active shape models (Metodo di ricerca locale) [rif. 1]

Entrambe queste tecniche si basano sulla creazione di un modello matematico per punti

rappresentativo della forma. Il modello viene creato attraverso una fase di training, nella

quale vengono elaborate una serie di immagini contenenti la forma e la sua variabilità.

Questa dipendenza dalle immagini del training-set limita la deformabilità del modello,

rendendolo più stabile e specializzato, ma al contempo ne limita l'adattabilità alle situa

zioni non previste nel training-set.

19


3.1 Modello matematico per punti (PDM=Point Distribution Mo

del)

Cootes et al. (1991) [1] elaborano un modello idoneo a descrivere forme bidimensionali

e variabili, attraverso la definizione di alcuni punti che individuano il contorno della for

ma da modellare.

Questo modello vincola la deformabilità della shape da ricercare ma, non essendo rigi

do, permette una variabilità all'interno delle forme definite nel training-set, riuscendo a

prevedere anche forme intermedie.

Il modello che verrà definito ha origine da un set di immagini relativamente elevato e

varia a seconda della complessità del modello e delle variazioni che s'intende far rappre

sentare.

La forma viene evidenziata tracciando un contorno per punti su ogni immagine: queste

coordinate costituiscono la base di partenza per la definizione del modello. A questo

punto sorge il problema della metodologia di scelta dei punti.

Vengono individuati tre tipologie di punti:

1. tipo di punto che marca una parte dell'oggetto di significativa importanza, come

un estremo o un angolo;

2. tipo di punto indipendente dall'oggetto che delimita e che individua caratteristi

che generali, come per esempio il punto più in alto nell'immagine appartenente

alla forma;

3. tipo di punto ricavato come interpolazione di punti di tipo 1 o 2

Una volta definiti i punti fondamentali che caratterizzano la forma dell'oggetto si devono

picchettare gli stessi nelle varie immagini incluse nel training-set.

20


Questo passaggio permette di ricavare un vettore di coordinate bidimensionali per ogni

immagine. Evidentemente queste coordinate, relative alla posizione dei pixel nelle im

magini campionate, devono essere allineate per avere i punti della shape, relativi ad un

punto del modello, il più possibile vicini.

L'allineamento si realizza con roto-traslazioni e rapporti di scala, ottenendo una forma

media e una matrice degli scarti che indica la variazione di un punto del modello rispetto

agli altri.

L'algoritmo descritto segue i seguenti passi:

• ruota, scala e trasla ogni shape per allinearla alla prima shape del training-set

presa casualmente come shape media;

• ripete fino a convergere i seguenti punti

• calcolo della shape media relativa all'ultimo allineamento effettuato

• normalizzazione sull'orientamento, sulla scala o origine della shape

media ad un valore deciso di default (utile a far convergere l'algoritmo)

• riallineamento delle shape rispetto alla shape media appena calcolata.

• Ripeti il ciclo.

21

Disegno 3.1: tipologia dei punti di un modello

Illustrazione 3.3


La normalizzazione è necessaria per far convergere l'algoritmo avendo 4*(N-1) vincoli

con 4*N variabili (N= numero delle shape e i 4 parametri sono relativi alla rotazione θ,

scala s, e traslazione t x , t y ).

Dalle shape del training-set allineate si ottiene la shape media x , e la matrice di cova

rianza campionaria

dove dx i=xi−x . Quindi il modello si può rappresentare con la formula

x=xS xv dove x è il vettore medio del modello e xv è il vettore dei parametri

che permette di discostarsi dalla forma media e ottenere la shape desiderata x .

Questa rappresentazione ha lo svantaggio di dover agire su tutte le componenti del vetto

re xv per ottenere la deformazione desiderata dovuta all'intrinseca correlazione tra le

variabili del modello. Quindi, si procede ad un'analisi delle componenti principali (PCA)

perché permette di scorrelare le variabili del modello, ottenendo così alcuni vantaggi di

seguito descritti.

3.1.1 Analisi delle componenti principali (PCA)

Poiché la matrice di covarianza è simmetrica di dimensioni NxN con elementi reali

Amn=Anm si dimostra l'esistenza di una matrice diagonale Λ ed una ortogonale U tali

22

Formula 3-4

S= 1N∑

i=1

N

d xi d xiT


che

A=U ΛU T

Le colonne di U = ( u1 , ......., uN ) sono gli autovettori di A e i valori nella diago

nale di Λ, ( λ1 , ......., λN ) sono gli autovalori e valgono le relazioni

Auk=λkuk

e gli autovettori uk sono ortonormali rispetto al prodotto scalare, per cui il loro pro

dotto vale 1 solo quando un autovettore è moltiplicato per se stesso.

Questa trasformazione permette di raggiungere diversi obiettivi:

• rende indipendenti i movimenti dei punti del modello nel senso che le variabili

della nuova base rappresentano comportamenti complessivi dei punti: se il mo

dello nella sua variabilità ha un naturale spostamento lungo una certa direzione,

nella base di partenza per ottenerne uno spostamento lungo questa direzione si

deve agire su tutte le variabili della base, mentre nella nuova base è probabile

che il movimento sia ottenuto agendo solo su alcune variabili.

Questa è la principale caratteristica dell'analisi (PCA) poiché permette di indivi

23

Disegno 3.2


duare tipologie di comportamenti e di concentrarne il controllo su singole varia

bili;

• le variabili della nuova base hanno un peso decrescente nel definire gli sposta

menti dei punti e, quindi, considerando le principali componenti si riesce di soli

to a ottenere quasi tutta la rappresentatività del modello. In termini matematici si

può dire che la varianza espressa da ogni autovettore è proporzionale al valore

del suo autovalore. Questa caratteristica può essere usata per ridurre il numero di

parametri da controllare nella gestione della variazione del modello, anche se in

troduce un'approssimazione del modello inferiore ad un certo valore stabilito a

priori;

• in uno spazio bidimensionale, la matrice di covarianza ha dimensioni pari a 4

volte il quadrato del numero di punti n utilizzati nel modello e questo comporta

delle matrici di grosse dimensioni che aggravano il calcolo computazionale.

Come diretta conseguenza della proprietà esposta precedentemente, diminuendo

il numero di variabili nella nuova base, si ottiene una matrice degli scarti dimen

sionalmente ridotta portando notevoli benefici in termini di prestazioni.

3.2 Tecniche di Shape Learning

La prima tecnica di Shape learning, che si basa su un modello matematico dei punti, è

l'Active Appearance Model (AAM) che consiste in una classificazione della forma de

scritta nelle immagini del training-set, dei contorni e dei valori dei colori in essa conte

nuti. Considerando i vettori dei punti che definiscono i contorni indicati nelle immagini

del training-set xi e la loro media x si calcola dx i=xi−x . Quindi, con l'analisi

24


delle componenti principali (PCA) applicata alla matrice di covarianza campionaria

Formula 3-5

si costruisce un modello statistico dei contorni

Formula 3-6

dove x è il vettore medio del modello che descrive i contorni, P s è la matrice che

descrive le variazioni del modello nella nuova base calcolata dalle immagini del trai

ning-set e bs è il vettore dei parametri che permette di discostarsi dalla forma media e

ottenere la shape desiderata x .

Si procede allo stesso modo per creare un modello dei livelli di grigio contenuti nella

forma, ottenendo il modello lineare

Formula 3-7

A questo punto la forma e i greylevel interni possono essere rappresentati dai vettori pa

rametrici bs e bg , che possono essere concatenati per rappresentare il modello nel

suo complesso. Poiché si suppone vi sia una correlazione tra i punti della shape e i grey

level in essa contenuti, si ripete il metodo PCA sul vettore bsb g per i valori che assu

mono nel rappresentare tutte le forma appartenenti al training-set. Il risultato è un mo

dello lineare

25

S= 1N∑

i=1

N

d xi d xiT

x=xP sb s

g=gP gb g


Formula 3-8

che descrive tutti gli aspetti della forma attraverso il vettore parametrico c .

Una volta in possesso del modello si procede nella fase di ricostruzione e/o riconosci

mento di nuove shape. L'obiettivo è la ricostruzione di una forma mai vista dello stesso

tipo di quelle appartenenti al training-set. Agendo sui parametri del vettore c si ottie

ne una immagine Im e si calcola la differenza con l'immagine da riconoscere I i .

Formula 3-9

Il problema consiste nel minimizzare il valore della distanza tra i vettori, cioè

Δ=∣δ I∣2 al variare dei parametri del vettore δc . Questa relazione viene acquisita

empiricamente, alterando con minime roto-traslazioni le shape generate dal modello e

calcolando come debba variare il vettore c per minimizzarne la distanza.

Questo procedimento permette di calcolare la relazione tra δc e δI e precisamente

la matrice A tale che δc=AδI .

In questo modo, durante una fase di riconoscimento, dopo aver calcolato δI si può ri

salire alla variazione da apportare al vettore c per minimizzare le distanze tra le due

immagini.

Un'altra tecnica di Shape Learning che prenderemo in considerazione è l'Active Shape

Model. L'ASM è un metodo di ricerca locale di una forma variabile, come per esempio

una mano , un occhio o organi del corpo umano, e come l'AAM si basa su un modello

26

b=b sbg=Qc

δ I=I i−Im


della forma da ricercare.

Considerando i vettori dei punti che definiscono i contorni indicati nelle immagini del

training-set xi e la loro media x si calcola dx i=xi−x .

Quindi con l'analisi delle componenti principali (PCA) applicata alla matrice di cova

rianza campionaria

Formula 3-10

si costruisce un modello statistico dei contorni

Formula 3-11

dove x è il vettore medio del modello che descrive i contorni, P è la matrice diago

nale che descrive le variazioni del modello nella nuova base calcolata dalle immagini del

training-set, e b è il vettore dei parametri che permette di discostarsi dalla forma me

dia e ottenere la shape desiderata x .

Tutte le forme indicate nelle immagini del training-set vengono memorizzate in questo

modello e sono ricostruite per precisi valori dei pesi associati alle varie componenti del

vettore b : valori intermedi dei pesi permettono di ottenere anche forme intermedie,

non presenti direttamente in quelle indicate dal training-set.

Sulle immagini del training-set, oltre alle coordinate dei punti, vengono campionati i re

27

S= 1N∑

i=1

N

d xi d xiT

x=xP b


lativi valori dei pixel nella perpendicolare della tangente alla curva del modello. Questi

vettori di pixel, la cui lunghezza np è stabilita a priori, sono necessari per la fase di ri

cerca in nuove immagini e vengono chiamati greylevel, perché le immagini prese in con

siderazione sono monocromatiche.

I greylevel vengono anche derivati e normalizzati per essere invarianti a fattori di scala o

ad aggiunte di costanti.

Questa operazione limita gli errori in fase di riconoscimento e introduce una maggiore

robustezza a variazioni di luminosità ambientali.

Il modello ricavato dalle immagini del training-set viene modificato durante la fase di ri

cerca della forma da un algoritmo analizzante, per adattarsi alla forma presente nell'im

magine.

3.2.1 Applicazione dell'ASM: metodo di ricerca locale

Il modello di ricerca locale si applica nell'area dell'immagine che contiene la forma da ri

cercare e a grandi linee procede ad approssimazioni successive, partendo dal modello

posizionato sulla forma media, cioè quando il vettore dei parametri b vale 0.

L'algoritmo è stato ideato per riconoscere forme variabili monocromatiche su sfondo

uniforme, con la conseguenza di avere dei greylevel più semplici da trattare. La sempli

ficazione è dovuta ai campi applicativi prevalentemente medici in cui questa tecnica vie

ne applicata con immagini costituite da livelli di grigio.

Il metodo svolge una ricerca nell'immagine monocromatica e, determina lo spostamento

necessario per allineare il modello alla forma individuata. Le direzioni prese in conside

razione per i dx sono le perpendicolari alla tangente passanti per i punti del modello,

28


cioè le stesse considerate per la creazione dei greylevel dalle immagini del training-set

(Disegno 3.3).

Il metodo con il quale si effettua il confronto prevede una fase di pre-elaborazione nella

quale viene calcolato il greylevel derivato per ogni immagine e per ogni punto del mo

dello,

Formula 3-12

dove j indica l'immagine j-esima, i indica l'i-esimo punto del modello e k indica la posi

zione del pixel k-esimo del greylevel campionato nell'immagine lungo la retta perpendi

colare alla tangente nel punto i-esimo, y i indica il vettore del greylevel del punto i-

esimo e y ik indica lo specifico valore del pixel k-esimo del vettore.

Successivamente il greylevel viene normalizzato per risultare invariante a costanti intro

dotte da fattori ambientali, come una maggiore luminosità o un colore diverso della pel

29

Disegno 3.3

gijk=I j y ik1−I j yi k−1


le.

Formula 3-13

Con questi greylevel normalizzati di lunghezza np si calcolano le relative matrici

np∗n p degli scarti quadratici medi Sgi per ogni punto i del modello. Il calcolo di

queste matrici permette di descrivere statisticamente la variabilità dei greylevel del mo

dello.

Poiché durante l'analisi di nuove immagini si deve operare un confronto con valori trat

tati allo stesso modo, si devono derivare e normalizzare anche i greylevel campionati

nell'immagine da analizzare.

Per ogni punto del modello viene calcolata la distanza di Mahalanobis: si campionano

l pixel e ne vengono considerati np alla volta (lunghezza greylevel) con npl e

su di essi, dopo essere stati derivati e normati, viene calcolata la distanza.

Formula 3-14

dove hd è il greylevel calcolato sull'immagine centrato in d, g è il greylevel me

dio calcolato da tutti i greylevel del training-set relativi ad un punto del modello ed

S g−1 è l'inversa della matrice di covarianza dei greylevel del punto.

Il dx rispetto al punto di partenza che ottiene la migliore distanza viene segnalato come

spostamento da effettuare per quel punto. La formula indica la necessità di calcolare l'in

30

gij'=

gij

∑k=1

n p

∣gijk' ∣

f prof d=h d−gT Sg

−1h d−g


versa della matrice di covarianza e in contesti di real-time questo limita le dimensioni

che può avere un greylevel, visto l'onerosità computazionale che comporta sia il calcolo

ripetuto n volte per ogni frame di f prof d , sia il calcolo di S g−1 , anche se effet

tuata solo una volta in fase di pre-elaborazione.

Per aumentare la stabilità dell'algoritmo, si limita il valore di dx ricavato dall'analisi, im

pedendo che vada oltre un certo valore Dmax e dimezzandolo per valori compresi tra 0 e

Dmax.

L'ultimo problema consiste nel traslare la variazione dx sul nuovo spazio dei para

metri db in cui il modello è stato descritto.

Si deve premettere che il modello x=xP b porta con sé un'approssimazione dovuta

al numero limitato di parametri t<n utilizzati per semplificare la gestione e la complessi

tà computazionale.

Questa approssimazione analiticamente si può riassumere scrivendo

Formula 3-15

e considerando che PT=P−1 si ricava la relazione

Formula 3-16

Ne consegue che entro una certa approssimazione la variazione del modello si può otte

nere dai dx ricavati dall'algoritmo analizzante moltiplicati per la trasposta della matrice

31

xd x≈xP bdb ⇒ dx≈P d b

db≈P T dx


contenente i primi t autovettori.

I nuovi pesi forniscono una nuova forma, diversa da quella media iniziale, ma più vicina

alla forma da ricercare nell'immagine. La nuova shape viene inviata come parametro al

l'algoritmo analizzante, che la usa come punto di partenza per una ricerca più precisa. Il

ciclo termina quando si ha una valutazione della somiglianza inferiore ad una certa so

glia; tale somiglianza viene valutata attraverso la distanza di Mahalanobis applicata al

modello generale, e si impone un valore minore di Dmax .

Formula 3-17

3.3 Conclusioni

Tutte le tecniche elencate sono efficaci in analisi specifiche e, quindi, devono essere uti

lizzate o adattate alla risoluzione di problemi compatibili con esse.

Una valida scelta delle tecniche da usare per la risoluzione di problemi di computer vi

sion presuppone uno studio delle specifiche del problema. Nel prossimo capitolo verrà

fatta l'analisi che ci ha condotto a ritenere l'Active Shape Model la tecnica più idonea ad

implementare un algoritmo di Eye Tracking.

32

Dm=b−0 P−1 b−0=∑k=1

t

bk

2

λk Dmax


4 Studio del sistema Eye Tracking esistente e requisiti

del progetto

Il lavoro di questa tesi ha lo scopo di definire un algoritmo di analisi delle immagini sta

tiche campionate per l'individuazione dei punti del modello precedentemente definito.

Questo algoritmo, una volta sviluppato in base ai requisiti di seguito esposti, verrà inte

grato nell'applicazione Eye Tracking.

4.1 Analisi del problema e dei requisiti

L'Eye Tracking è una tecnica che permette l'inseguimento dei movimenti dell'occhio at

traverso il riconoscimento dei suoi contorni e consente di determinare la direzione verso

cui guarda l'operatore.

A tal fine si ritengono efficaci gli strumenti offerti dalla computer-vision nel riconosci

mento della posizione dell'occhio, riducendo di conseguenza l'hardware specifico relati

vo agli infrarossi delle soluzioni attualmente disponibili. Dal monitoraggio dei movi

menti dell'occhio si cerca di dedurre la zona osservata dall'utente, fornendo così una tec

nica alternativa di Eye Tracking rispetto a quelle accennate nel secondo capitolo.

Il problema dell'invasività degli strumenti di rilevazione, riscontrato in alcune tecniche

attuali, alimenta la ricerca di nuovi sistemi privi di contatti diretti con l'utente, in modo

da preservarne la libertà e la naturalezza dei movimenti.

Anche la dipendenza da ambienti studiati per ottenere una rilevazione più precisa da par

te del sensore è una forzatura che, seppur permetta nell'immediato di conseguire alcuni

33


risultati, non può essere la soluzione definitiva, dovendo questa risultare indipendente

dalle variabili ambientali che circondano l'operatore.

Le caratteristiche ideali di un Eye-Tracker dovrebbero essere l' economicità, la non inva

sività e l'indipendenza dal contesto: questo lavoro ha dato la priorità ad una soluzione

economica, garantendo la libertà di movimento dell'utente.

Innanzi tutto l'economicità del sistema prevede l'uso di personal computer che, oltre

a facilitare la fase implementativa, consentirebbe in futuro una diffusione maggiore del

le possibili applicazioni, in quanto si tratta di comuni strumenti utilizzati dagli utenti.

Inoltre, si prevede l'utilizzo di webcam con sensori CMOS e risoluzione VGA

(640x480), poiché facilmente reperibili sul mercato ad un costo contenuto. Tuttavia

esistono sensori con risoluzioni maggiori, usati prevalentemente in campi di ricerca me

dica o astronomica, ma in questo lavoro non sono stati presi in considerazione a causa

del loro costo elevato.

La soluzione potrebbe anche prevedere l'uso di due punti di acquisizione che, da un lato

porterebbero ad un maggior flusso di informazioni da elaborare, ma dall'altro, permette

rebbero una maggiore probabilità di rilevare correttamente la forma dell'occhio e la dire

zione verso cui guarda l'utente. La posizione che queste webcam possono assumere non

è un vincolo, ma è evidente la necessità di posizionarle il più possibile frontalmente e in

prossimità dell'occhio.

“Indipendenza dal contesto” significa ottenere analoghi risultati al variare di luminosità,

distanza dall'obiettivo, colore della pelle, degli occhi o altro ancora. Risulta evidente

come siano molti gli aspetti che influenzano il contesto, quindi una totale indipendenza

da esso appare un obiettivo difficile da realizzare pienamente. Si intende comunque

adottare qualche accorgimento o tecnica che possa ridurre al minimo gli effetti più rile

34


vanti evidenziati in questa analisi, quali l'indipendenza dalla luminosità e dal colore del

la pelle o degli occhi.

Un altro aspetto da considerare, dovuto alla necessità di implementare un sistema meno

invasivo, riguarda la dimensione che la forma dell'occhio occupa nell'immagine cam

pionata. Con le attuali webcam, che forniscono immagini con una dimensione di

640x480 pixel, un occhio può occupare dal 5% al 30% di questa superficie, a seconda di

quanto sia ravvicinata la ripresa. Quindi, gran parte dell'immagine non contiene informa

zioni significative, e l'algoritmo deve estrapolare la forma da un numero ridotto di pixel.

Si potrebbe pensare, in alternativa, ad un sistema di due webcam, di cui una dotata di

zoom e motorizzata, in modo da ottenere un'immagine dettagliata dell'occhio, senza ri

nunciare alla non invasività della soluzione.

Attraverso i valori assegnati ad alcuni parametri, l'algoritmo deve permettere una buona

flessibilità per valutare quali siano quelli ottimali.

Considerando oltretutto la natura dei dispositivi sui quali può avere applicazione questo

algoritmo come ausilio d'interfacciamento, una volta individuata la soluzione ottimale e

verificato il funzionamento, si dovrà trovare il giusto compromesso per non monopoliz

zare le risorse del personal computer.

Inoltre, l'applicazione dell'algoritmo in un flusso video a colori di almeno 5-10 frame al

secondo impone una velocità di elaborazione elevata e, vista la necessità di non poter

occupare eccessivamente il processore per i motivi suindicati, si ritiene opportuno svi

luppare le parti critiche del sistema con procedure in assembler, sfruttando maggiormen

te le potenzialità degli attuali processori. Questa specifica resta, comunque, subordinata

all'effettiva realizzazione di un sistema che soddisfi le restanti caratteristiche.

La variabilità della forma presa in esame e le specifiche indicate rendono necessario l'u

35


so della teoria utilizzata nelle tecniche di analisi dell'immagine del tipo “shape

learning”.

Vista l'onerosità computazionale maggiore nell'uso di immagini a colori rispetto a quelle

mocromatiche, tra le due teorie descritte nel capitolo precedente, l'Active Appareance

Model (AAM) e l'active Shape Model (ASM), la scelta ricade su quest'ultima, in quanto

permette un conseguimento dell'obiettivo con un minore consumo di risorse della CPU.

Questa tecnica, anche se applicata in immagini monocromatiche relativamente più sem

plici, risulta più promettente per la robustezza al rumore, alle occlusioni parziali e al fa

cile controllo del modello.

Si deve trovare una soluzione che adotti il principio contenuto nella tecnica dell'Active

Shape Model, ma che possa al tempo stesso utilizzare le informazioni di un'immagine a

colori.

Inoltre, poiché l'iride ha un'elevata motilità, si deve pensare ad una funzione che tenga

conto di questi repentini movimenti, prevedendo eventualmente l'uso di greylevel speci

fici alla particolare posizione assunta dall'occhio in un determinato momento.

Nell'algoritmo esposto da Cootes et al. vengono usati greylevel monocromatici monodi

mensionali, con lunghezza prefissata e relativamente limitata, ma in questo lavoro si in

tende valutare l'effetto di greylevel bidimensionali variabili a colori, in modo da valutare

l'efficacia dell'algoritmo alla loro variazione.

L'Eye Tracking in alcuni contesti, come l'impiego in campi militari per il puntamento di

obiettivi, deve possedere un alto grado di affidabilità, poiché da esso può dipendere la

vita di alcune persone. Da questa considerazione si deduce quanto sia importante una

valutazione oculata della scelta dei metodi e degli strumenti idonei a garantire il funzio

namento entro limiti predefiniti. Questo lavoro, non essendo destinato a campi specifici,

36


verrà valutato misurando la corrispondenza tra la shape ricavata dal modello al variare

del numero di iterazioni e la shape individuata manualmente, utilizzando, sia immagini

appartenenti al training-set sulle quali le forme sono già definite, sia immagini nuove

campionate sul momento. Successivamente, dai risultati ottenuti, si potranno individuare

le potenzialità dell'algoritmo e del sistema nel suo complesso.

37


4.2 Struttura generale del sistema

Il sistema fisicamente è costituito da una webcam e un personal computer. L'acquisizio

ne delle immagini a colori viene messa a disposizione del programma, senza subire par

ticolari pre-elaborazioni.

La webcam scelta, anche se di tipo economico, permette una buona visibilità in scarse

condizioni di luminosità e ha funzioni di auto-adattamento alla luminosità esterna, in

modo da fornire un'immagine ottimale. Questo adattamento fatto automaticamente dal

l'hardware rende il sistema più tollerante a variazioni luminose, facilitando al contempo

il processo di elaborazione. Quasi tutte le webcam in commercio, essendo studiate per

attività di videoconferenza, riescono con i loro driver ad autoregolare la luminosità e il

contrasto.

Durante la fase di acquisizione delle immagini è opportuno non introdurre errori siste

matici nel training-set, con la presenza di una luminosità scarsa o eccessiva: un'imma

gine molto luminosa introdurrà un offset nei valori dei pixel che può comportare una di

38

Illustrazione 4.1


minuzione dell'informazione in essa contenuta; con immagini RGB e una profondità di

24 bit, i valori ottenuti sarebbero tutti prossimi al loro valore massimo, ovvero 255, e ci

sarebbe un margine minore di valutazione e memorizzazione delle caratteristiche dei

greylevel.

Nella realtà, anche usando webcam con il bilanciamento automatico del bianco e intro

ducendo, come vedremo, algoritmi per diminuire il rumore causato da variazioni lumi

nose, si rende necessario adottare qualche accorgimento per migliorare la percentuale di

funzionamento del sistema; per esempio la luminosità ambientale con una sorgente di

luce indiretta.

Un altro aspetto da considerare è la relativa staticità dell'operatore durante l'acquisizione

delle immagini del training-set da cui verrà elaborato un modello dell'occhio. A tal fine è

necessario limitare la mobilità del viso per completare correttamente questa fase; se si

prevede una parziale mobilità della testa, allora è opportuno aggiungere una serie di im

magini nel training-set con queste posizioni, in modo da rendere il modello predisposto

ad esse in fase di utilizzo.

Lo studio di un algoritmo, che possa implementare una valida soluzione per la variazio

ne dei parametri di controllo dell'Active Shape Model, verrà sviluppato basandosi a due

applicazioni esistenti: la prima “Training”, utilizzata per creare il modello per punti dal

training-set e con la quale si sono ricavati i greylevel necessari, e la seconda “Eye Trac

king”, per elaborare e testare l'algoritmo di ricerca e valutarlo in nuove immagini acqui

site in tempo reale.

39


4.2.1 Studio dell'applicazione “Training”

L'applicazione Training, preesistente allo sviluppo di questo lavoro, è stata ideata per

acquisire le immagini e picchettare le forme dell'occhio in esse presenti.

Le shape acquisite costituiscono il training-set e permettono al programma di generare il

modello relativo.

Questa versione del programma utilizza le funzioni per l'acquisizione delle immagini da

webcam implementate nella libreria VFW32.lib (Video For Windows). La soluzione

adottata prevede una ram-disk su cui vengono salvate le immagini campionate e poi ca

ricate per le analisi successive. In questa fase di sviluppo, dovendo ricercare metodi di

analisi delle immagini con cui individuare la forma dell'occhio, si lavora su singoli fra

me, quindi non sono richieste particolari velocità di riconoscimento, poiché già l'analisi

presuppone un tempo di elaborazione non trascurabile.

Il programma è strutturato da un thread, che smista i messaggi generati dalla finestra

40

Disegno 4.1: diagramma a blocchi del sistema


principale, e da un thread “Supervisore”, che gestisce tutte le attività dell'applicazione:

attivazione e impostazione webcam, creazione picchettamenti e visualizzazione dei

greylevel finalizzati alla creazione del modello.

Per comprendere l'origine del modello si riporta la figura generata dal riallineamento e

dalla successiva sovrapposizione di un intero training-set. Si distinguono chiaramente le

zone dei punti del modello su cui si concentrano i vari picchettamenti effettuati su ogni

immagine del training-set.

4.2.1.1 Metodo per la creazione del training-set

Questa applicazione, oltre a generare un training-set e il modello relativo, integra una

nuova procedura sviluppata in questa tesi per la la creazione e il salvataggio dei greyle

vel.

Il primo passo consiste nel definire progettualmente il numero di punti e la posizione in

41

Illustrazione 4.2


cui collocarli nella sagoma dell'occhio. La rappresentazione grafica nel disegno 4.2 in

realtà è la media di un training-set reale, in cui sono evidenziate le posizioni e la tipolo

gia dei punti secondo quanto specificato nel capitolo 3.

La scelta dei punti, in totale 37, ha la funzione di definire tutti gli estremi del contorno

dell'occhio, dell'iride e della pupilla. Come esposto nel terzo capitolo i tratti principali

della forma dell'occhio sono punti di tipo 1 e i rimanenti, avendo funzione di completa

mento, sono di tipo 3 (disegno 4.2).

Prima di iniziare i campionamenti si deve stabilire:

1. dove fissare la webcam e l'eventuale sorgente luminosa;

2. la posizione della testa;

3. i punti di osservazione nelle immagini del training-set.

42

Disegno 4.2


La webcam si può posizionare su qualunque lato del monitor o del portatile, cercando,

però, di riprendere l'occhio completamente e in modo ravvicinato per non perdere troppi

particolari.

La sorgente luminosa, se usata, deve essere indiretta, per illuminare in modo uniforme

l'ambiente; con un livello luminoso inferiore si riesce a sfruttare tutta la sensibilità del

l'hardware, ottenendo dei greylevel con una profondità maggiore.

In fase di test l'utente, di conseguenza, dovrà assumere una postura simile a quella del

training-set.

Rimangono da definire i punti da osservare all'interno del monitor durante le fasi di ac

quisizione: con una griglia sovrapposta alla superficie dello schermo si ottiene un'equa

distribuzione spaziale dei punti. In fase sperimentale si è riscontrato un miglior funzio

namento con l'introduzione nel training-set di punti di osservazione esterni alla superfi

cie del monitor (illustrazione 4.3).

In tal modo si riesce a tollerare piccole variazioni della posizione del capo quando si os

servano delle parti periferiche dello schermo.

Per ogni posizione stabilita dalla griglia viene acquisita un'immagine e, successivamen

43

Illustrazione 4.3: griglia di riferimento

durante l'acquisizione del training-set


te, si procede al picchettamento di tutti i 37 punti presenti al suo interno. Questa fase ri

sulta molto delicata, poiché si possono commettere errori che potrebbero in un secondo

momento inficiare il modello generale.

Una volta acquisita la forma vengono generati i greylevel per tutti punti di ogni immagi

ne.

Tutti i gruppi dei vari punti del modello vengono normalizzati, scalati, traslati e ruotati,

per confrontarli e calcolare il modello statistico della forma.

Al termine di questa procedura si ottiene una serie di file che verranno elaborati sia dalla

applicazione Training per la generazione del modello, sia dall'applicazione Eye Tracking

per le fase di valutazione dell'algoritmo di analisi.

44

Diagramma 4.1


5 Verifica

5.1 Algoritmi implementati

Il lavoro svolto ha cercato un algoritmo che, dati i pesi relativi ad una forma assunta dal

modello, riesca ad individuare i migliori greylevel del training-set da utilizzare nel rico

noscimento.

La ricerca di questa soluzione parte da una limitazione della teoria esposta da Cootes et

al. [1] che non prevede casi di elevata variabilità del greylevel: la funzione di valutazio

ne, poiché considera per ogni punto un greylevel medio e la sua matrice di covarianza,

non discrimina tra le varie differenze che i greylevel del training-set possono avere per

ogni punto del modello.

5.1.1 Metodo di creazione dei greylevel

Il greylevel è la parte dell'immagine presa in considerazione per effettuare la classifica

zione dei punti del modello e viene usato per riconoscere aree simili in nuove immagini.

Le relative informazioni su tutti i punti del modello permettono il riconoscimento della

forma nel suo complesso.

Il greylevel (livelli di grigio) prende il nome dal fatto che in letteratura sono state usate

prevalentemente delle immagini in bianco e nero. Nel nostro caso, trattando immagini a

colori, per greylevel si intendono i valori delle tre componenti RGB dei pixel presenti in

un intorno del punto della shape.

45


Per contrastare parzialmente la variabilità ambientale sono state introdotte immagini a

colori che, con una maggiore quantità di informazioni, permettono minori margini di er

rore nel riconoscimento.

Per ogni immagine si genera un file di greylevel, in base alla lunghezza e larghezza im

postate, campionando sulle normali relative alle rette passanti per i due punti della forma

che precedono e seguono il punto considerato (disegno 3.2). Per alcuni punti della sha

pe, come per esempio il centro della pupilla, si stabilisce in modo arbitrario la relativa

perpendicolare, ma una volta fissata è necessario usare sempre la stessa.

46

Illustrazione 5.1

Illustrazione 5.2


Una volta stabilita la lunghezza dei greylevel, si procede al campionamento nell'immagi

ne del training-set, attraverso l'introduzione di una funzione analitica di una retta passan

te per un punto x p , y p con un determinato coefficiente angolare a0 :

Formula 5-1

si parte dal punto della shape x p , y p e si ricavano le coordinate al crescere e al de

crescere della x.

Il problema del campionamento non è un aspetto di secondaria importanza, in quanto è

soggetto a possibili errori nel calcolo delle coordinate generate dall'algoritmo. E' impor

tante campionare pixel consecutivi con almeno un valore delle coordinate incrementato

rispetto al pixel precedente, per evitare la presenza di tre pixel adiacenti in una regione

47

Diagramma 5.1

y=a0∗x−xpy p


2x2. In questo modo il greylevel è più allungato permettendo, a parità di pixel, la coper

tura di una porzione maggiore della retta perpendicolare.

Per ottimizzare la ricerca di queste coordinate e ottenere il risultato voluto, si incrementa

la variabile indipendente x con valori inversamente proporzionali al coefficiente della

retta perpendicolare. Inoltre, si evita un possibile salto di coordinate moltiplicando per

una costante di poco inferiore a 1.

Formula 5-2

5.1.2 Lunghezza e larghezza dei greylevel

Due costanti GREY_I e GREY_E indicano quanto il greylevel debba essere lungo all'e

sterno e all'interno rispetto alla forma globale dell'occhio. La lunghezza totale del vettore

sarà di Grey_I+GREY_E+1 pixel.

L'algoritmo permette, in questo modo, di formulare dei greylevel asimmetrici rispetto

48

Illustrazione 5.3: Esempio di campionamento corretto ed errato

X=X0,995∗1a


alla shape dell'occhio, indicando un valore di GREY_I diverso da GREY_E. Questa

proprietà va considerata nel caso venga cambiata la forma da riconoscere: si deve modi

ficare la classificazione dei punti per stabilire quali generano un greylevel interno al

crescere della x, e quali ne generano uno esterno.

Lo spessore del greylevel si sviluppa nella direzione perpendicolare alla retta in cui gia

ce il greylevel, ma per limitare la complessità computazionale si decide di considerare i

pixel adiacenti in una delle due direzioni dell'immagine. Vengono, quindi, considerati i

pixel orizzontali se il coefficiente della perpendicolare è maggiore di 1, e viceversa quel

li verticali se il coefficiente è minore o uguale a 1.

Dalla quantità maggiore di dati considerata ci si attende un aumento della stabilità nel ri

conoscimento del punto, ma anche un aumento del tempo computazionale complessivo.

49

Illustrazione 5.4


5.1.3 Greylevel derivato e normato

Durante le prime fasi di sviluppo si è formulato un algoritmo che effettuava la ricerca at

traverso una semplice comparazione dei valori dei pixel, ma la grande variabilità delle

immagini comportava un riconoscimento più instabile e approssimativo. Si è, quindi,

implementata la procedura descritta nel terzo capitolo relativa all'ASM per la generazio

ne dei greylevel.

Una volta campionato il greylevel si calcola il gradiente nella direzione della retta, attra

verso la differenza fra il valore precedente e quello successivo dei pixel. Il delta ricavato

viene assegnato al pixel centrale.

Formula 5-3

In questo modo il greylevel calcolato su n pixel genera n-1 valori, ma permette all'algo

ritmo di essere invariante a valori costanti presenti nell'immagine da analizzare, per

esempio a causa di una luce diversa nell'ambiente o per un diverso colore della pelle.

Il greylevel viene quindi normalizzato, dividendo per la somma totale di tutti i suoi valo

ri, in modo da ottenere la forma da riconoscere invariante a fattori di scala. Questa nor

malizzazione, però, comporta la gestione di un vettore floating-point e incrementa i tem

pi di elaborazione.

Formula 5-4

50

gijk=I j y ik1−I j yi k−1

gij'=

gij

∑k=1

n p

∣gijk' ∣


Una comparazione tra i greylevel del training-set gijk'

e quelli ricavati nei frames du

rante la fase di riconoscimento Gik'

viene svolta con l'utilizzo della distanza euclidea

Formula 5-5

dove j indica l'immagine j-esima del training-set , i indica l'i-esimo punto del modello, k

indica il pixel k-esimo del greylevel campionato nell'immagine lungo la retta perpendi

colare alla tangente nel punto i-esimo, e np indica il totale dei valori contenuti in un

greylevel.

La funzione di valutazione complessiva risulta essere la somma delle distanze di tutti i

punti del modello N.

Formula 5-6: Funzione di valutazione Totale

5.1.4 Metodo di ricerca globale

5.1.4.1 Algoritmo di ricerca della forma

L'algoritmo di analisi riceve come parametri le coordinate dei punti che individuano la

forma definita dal modello. In una prima fase queste coordinate vengono solidalmente

traslate per la ricerca dell'area in cui si trova l'occhio; in seguito si modificano per per

51

D=∑i=1

N

Disti .

Disti=∑k=1

n p

g ijk' −Gik

' 2


mettere ai punti del modello di assumere la forma specifica presente nell'immagine.

Ad ogni iterazione si campionano i greylevel sulle coordinate di questi punti.

Il calcolo del greylevel in real-time è un'operazione onerosa e dipende, sia dalle dimen

sioni dell'area, sia dal numero di punti che definiscono la shape.

Ognuno di questi greylevel, oltre ad essere estrapolato dall'immagine, viene anche deri

vato e normalizzato per essere comparato con i grelevel del training-set.

Queste problematiche vanno prese in considerazione al momento della realizzazione

pratica: per avere un flusso di elaborazione pari ad almeno 5-10 frame/s, si deve svilup

pare una versione dell'algoritmo in assembler, utilizzando le istruzioni SIMD dei proces

sori Pentium.

La procedura di comparazione utilizzata da Cootes et al.[2] crea un greylevel monocro

matico ed unico ricavato da tutti quelli delle immagini del training-set e, con la distanza

di Mahalanobis, valuta la somiglianza con il greylevel campionato.

Questo metodo, attraverso un greylevel che tiene conto solo del valore medio per pixel e

della distribuzione normale di questi nell'insieme del training-set, risulta poco efficiente

per quei punti del modello che hanno una grande variabilità, sia in termini di posizione,

sia in termini di greylevel associati. Quindi, è necessario determinare un metodo in gra

do di individuare un greylevel di comparazione mirato e specifico, per effettuare un rico

noscimento più preciso della forma e della posizione dell'occhio.

La soluzione individuata utilizza al massimo l'informazione contenuta nei greylevel del

training-set, rendendoli tutti potenziali termini di paragone. La scelta del greylevel di

confronto ritenuto più idoneo avviene durante il processo di riconoscimento, in base al

l'evoluzione della forma determinata dai parametri associati alle componenti princi

pali: per ogni forma del training-set, si associano i parametri del modello che la descri

52


vono ai relativi greylevel.

Sono state testate due strutture per realizzare questa associazione, che verranno esposte

in seguito.

5.1.4.2 Suddivisione della ricerca in due fasi

Non è stato possibile procedere nella ricerca in modo esaustivo per tutti i pixel dell'im

magine per l'elevato onere computazionale che comporterebbe. Per ridurre questo carico

senza penalizzare eccessivamente le potenzialità dell'algoritmo si è deciso di suddividere

la ricerca in due fasi:

• la prima ha il compito di individuare la forma dell'occhio in una grande area dell'im

magine e di determinarne in modo approssimativo la forma particolare;

• la seconda ha il compito di concentrare l'elaborazione nella ricerca più precisa della

forma.

I parametri (disegno 5.1) su cui agire per affinare la ricerca sono “x” e “y” che indicano

gli offset da aggiungere alle coordinate di tutti i punti della shape, “k” permette una ri

cerca del singolo greylevel nell'immagine spostando la posizione di un singolo punto del

modello di qualche pixel orizzontalmente o verticalmente, “z” indica di quanto può tra

slare il greylevel nella direzione perpendicolare alla forma per individuare la posizione

migliore e “q”, nella seconda fase dell'analisi, permette la scansione di un sottoinsieme

di greylevel tra quelli del training-set.

53


5.1.4.3 Fase 1: ricerca della forma nell'immagine

Come anticipato, la limitata capacità dei processori non permette la ricerca della forma

in tutta l'area dell'immagine e si è obbligati a limitarla in qualche modo.

Il problema è affrontato con l'adozione di due criteri: il primo consiste nel procedere a

passi prestabiliti nelle due direzioni dell'immagine agendo sui parametri “x” e “y” (fig.

5.1), in modo da coprire un'area maggiore senza aumentare il numero di iterazioni del

l'algoritmo; il secondo è più un limite che un criterio, poiché si stabilisce di non esami

nare tutta l'immagine, ma solo una zona circoscritta rispetto ad un punto indicato dall'o

peratore.

Questa ricerca avviene per un numero determinato di iterazioni, nelle quali si riduce gra

dualmente sia l'area presa in considerazione, sia il passo prestabilito delle variabili “x” e

“y”. Attraverso la funzione di valutazione definita in precedenza, che fornisce l'indica

zione della somiglianza tra i greylevel del training-set e le aree dell'immagine analizzate,

si individua la zona su cui concentrare l'analisi nella successiva iterazione (disegno 5.3).

54

Disegno 5.1


Mentre si modifica la posizione su cui effettuare la ricerca, si determina la forma dell'oc

chio attraverso l'utilizzo dei dati ricavati dall'analisi: per quanto non si valuti un insieme

di greylevel articolato, come nella seconda fase, l'applicazione dell'algoritmo, con il

greylevel a distanza minima, riesce in modo approssimativo ad adattarsi verso la forma

finale.

In questa prima fase sono disattivati i cicli che permettono la ricerca in un intorno dei

singoli punti del modello attraverso i parametri “k” e “z”, per non appesantire l'analisi

iniziale con delle variazioni utili solo quando si è sicuri di essere nell'area corretta.

Il numero di iterazioni da dedicare a questa ricerca viene determinato operativamente e

55

Disegno 5.3: affinamento della ricerca in una zona più ristretta

Disegno 5.2: Area coperta dall'analisi per un ciclo 3x3 e forma

parzialmente sovrapposta


stabilito in modo da ottenere un buon risultato parziale, senza rallentare troppo il tempo

di elaborazione totale di un frame.

5.1.4.4 Fase2: affinamento della forma

La seconda fase ha il compito di avvicinare il più possibile il modello alla forma presen

te nell'immagine. Pertanto si ipotizza che l'area di ricerca sia sovrapposta all'area del

l'immagine che contiene l'occhio. In questo modo i cicli associati ai parametri “x” e “y”

sono sostituiti con quelli gestiti dai parametri “k” e “q”, che permettono la variazione di

ogni coordinata dei punti del modello.

Il parametro “k” consente una ricerca locale del punto traslando il greylevel in orizzonta

le, se il modulo del coefficiente angolare dello stesso è minore di 1, o verticale in caso

contrario.

Ora, a differenza della prima fase di ricerca, il confronto con i greylevel campionati non

avviene con un singolo elemento del training-set, ma con un insieme determinato dalle

migliori distanze che i pesi relativi hanno rispetto a quelli assunti dal modello.

Durante la fase di sviluppo si è provato a variare i coefficienti angolari delle rette su cui

effettuare i campionamenti dei greylevel, ma non ottenendo nessun beneficio in termini

di riconoscimento, si è deciso di disattivare questa parte dell'algoritmo di analisi.

Si riporta la procedura che scansiona l'immagine e restituisce la predizione della shape:

PUNTO_DOUBLE * Analisi::trovashape6bis(PUNTO_DOUBLE * vet_in, double *Pesi)// questa proc cerca i best per ogni pto e li restituisce{// definizione delle variabili locali.........................

56


switch(Iterazione){

Modulazione della zona da analizzare ad ogni iterazione: in funzione della variabile “Iterazione” si assegnano i valori per i cicli dell'analisi

case 0:xin=-32; xfin=32; dx=32; yin=-32; yfin=32; dy=32;kin=0; kfin=0; stepk=2; z1=12; z2=6;break;

case 1:.....................

case 6:yin=-1; yfin=-1; dy=1; xin=-1; xfin=-1; dx=1;kin=0; kfin=0; stepk=2; z1=12; z2=6;break;

default:xin=0; xfin=0; dx=1; yin=0; yfin=0; dy=1;kin=0; kfin=0; stepk=1; z1=6; z2=3;

break;}

Controllo che la Shape no esca dall'immaginebest1.dist=DBL_MAX;

best1.X=INT_MAX; best1.Y=INT_MAX;nXSpot =(short)Bitmap->bmiHeader.biWidth;nYSpot =(short)Bitmap->bmiHeader.biHeight;

......................................for(i=0;i<DIMENSIONE;i++){

if(vet_in_int[i].X<minx)minx=vet_in_int[i].X;if(vet_in_int[i].X>maxx)maxx=vet_in_int[i].X;if(vet_in_int[i].Y<miny)miny=vet_in_int[i].Y;if(vet_in_int[i].Y>maxy)maxy=vet_in_int[i].Y;

}recx=maxx-minx;recy=maxy-miny;

// imposto il greylevel in funzione dei Pesi associati al modelloset_greylevel2(Pesi);if(Iterazione>STEP2){// Seconda fase: disattivo i cili su X e Y e attivo quelli su K e Z

xin=0; xfin=0; dx=1; yin=0; yfin=0; dy=1;kin=-1; kfin=1; stepk=1; z1=1; z2=1;qiniz=0; qfin=NUM_FILA_BEST; stepq=1;// attivo il for per ricercare con un gruppo di greylevel

}else{// prima fase: considero solo un greylevel.

qiniz=0; qfin=1; stepq=1;}

Imposto i vari cicli per l'iterazione corrente: q per i greylevel da usare, x e y per la

57


traslazione di tutta la shape e k per la traslazione di ogni punto del modello nella direzione della tangente alla shapefor(q=qiniz;q<qfin;q+=stepq){

for(x=xin;x<=xfin;x+=dx){for(y=yin;y<=yfin;y+=dy){

tot_tmp.dist=0.0;for(i=0;i<DIMENSIONE;i++){tmp.dist=DBL_MAX;// per ogni pto individua il best al variare di k

L'if seguente distingue la seconda fase dalla prima: se Iterazione > STEP2 imposto il q-esimo greylevel per l'analisi altrimenti considero un solo greylevel.

if(Iterazione>STEP2){// Seconda fase: imposto il q-esimo greylevel per l'analisigrey_c= &(associa[fila_best[q]].Cella[i]);

}else{// Prima fase: imposto il q-esimo greylevel per l'analisi

grey_c= &(associa[foglia].Cella[i]);}

// se il coefficiente del greylevel è >1 la larghezza del greylevel è sulle X altrimenti sulle Y

if(fabs(grey_c->coef)>1.0){

for(k=kin;k<=kfin;k+=stepk){// per i pti della pupilla considero z1 pixel (maggiore di z2) nella direzione del greylevel altrimenti z2 pixel

if(i>23){// pti della pupillaasm_analizzaDgreyNorm3(vet_in_int[i].X+k+x,vet_in_int[i].Y+y, z1, z1, cff, &(res[i]), grey_c);

}else{// gli altri punti del modello

asm_analizzaDgreyNorm3(vet_in_int[i].X+k+x,vet_in_int[i].Y+y, z2, z2, cff, &(res[i]), grey_c);}

// se ottengo un risultato migliore memorizzo la posizione relativaif(res[i].dist<tmp.dist){

tmp.dist=res[i].dist;best_res[i].dist=res[i].dist;best_res[i].X=res[i].X;best_res[i].Y=res[i].Y;

}}// fine for(k=kin;y<=kfin;k++)

}else{

// il coefficiente del greylevel è <=1 e la larghezza del greylevel è sulle Yfor(k=kin;k<=kfin;k+=stepk){

if(i>23){// pti della pupilla asm_analizzaDgreyNorm3(vet_in_int[i].X+x,vet_in_int[i].Y+k+y, z1, z1, cff, &(res[i]), grey_c);

}else{// gli altri punti del modello

58


asm_analizzaDgreyNorm3(vet_in_int[i].X+x, vet_in_int[i].Y+k+y, z2, z2, cff, &(res[i]), grey_c);}if(res[i].dist<tmp.dist){

tmp.dist=res[i].dist;// la uso per entrare quando ho un nuovo minimobest_res[i].dist=res[i].dist;best_res[i].X=res[i].X;best_res[i].Y=res[i].Y;

}}// fine for(k=kin;y<=kfin;k++)

}tot_tmp.dist+=best_res[i].dist;}// fine for(i=0;i<DIMENSIONE;i++)

Dopo ogni ricerca sull'immagine, se si trova una soluzione più soddisfacente, si memorizzano i risultati ottenuti

if(tot_tmp.dist<best1.dist){best1.X=x;//memorizzo il dx e dy del bestbest1.Y=y;best1.dist=tot_tmp.dist;dist=tot_tmp.dist;for(i=0;i<DIMENSIONE;i++){

Shape_out[i].X=best_res[i].X;Shape_out[i].Y=best_res[i].Y;

}if(Iterazione>STEP2){

foglia=fila_best[q];}

}}// fine for(y=-1;y<1;y++)

}// fine for(x=-1;x<1;x++)}//for(q=qiniz;q<NUM_FILA_BEST;q++)Iterazione++;// incremento il contatore relativo all'immagine settatareturn Shape_out;}

Come si deduce dal diagramma di flusso seguente, ad ogni iterazione si ordinano i mi

gliori elementi del training-set che, successivamente, vengono usati nella fase di calcolo

del best-match. L'utilizzo di un maggior numero di elementi del training-set aumenta la

coerenza del riconoscimento, rendendolo quasi indipendente dal punto iniziale dell'ana

lisi.

Di seguito si riporta uno schema esemplificativo della procedura che determina il vettore

59


dei migliori elementi del training-set da utilizzare nella fase di analisi dell'immagine,

mentre si rimanda al § 5.1.6.2 per la versione integrale.

60

Disegno 5.4: scelta del/dei greylevel per la successiva iterazione


5.1.5 Metodo di ricerca locale: determinazione della forma

Una volta indicata, tramite il mouse, la zona dell'immagine che contiene la forma da ri

cercare, si procede al suo riconoscimento impostando il modello al valore medio, e l'ele

mento di confronto del training-set in base ai valori dei pesi associati.

Nelle successive iterazioni la scelta del greylevel avviene come descritto nel paragrafo

5.1.4.4 e si procede nella modifica dei parametri di controllo del modello in base ai valo

ri restituiti dalla procedura di analisi. Questi valori, ovvero le coordinate del modello in

dividuate nella nuova immagine, non sono direttamente utilizzabili per il calcolo dei

nuovi pesi, ma vengono dapprima allineati alla shape media del modello e, in un secon

do momento, vengono usati per calcolare il vettore degli scarti dalla shape iniziale.

Per rendere più graduale l'avvicinamento alla forma finale, minimizzando gli effetti di

eventuali riconoscimenti errati, gli scarti dx ottenuti si limitano superiormente se

maggiori di una “soglia1”, si dimezzano se minori di “soglia1” e maggiori di “soglia2”,

e si lasciano inalterati se minori di “soglia2”.

Attraverso il vettore dx si ricavano gli incrementi da applicare ai pesi del modello

con la formula

db=P T dx

e in seguito si determinano i nuovi pesi calcolando

bnuovi=b precdb

Diverse iterazioni con parziali modifiche dei parametri di controllo permettono di avvi

61


cinare il modello alla posizione reale.

Questa convergenza è limitata, sia dalla variabilità ambientale delle immagini acquisite,

sia dalla difficoltà di poter rappresentare una nuova forma presente nell'immagine che

non rientra in quelle possibili previste dal training-set.

Di seguito viene riportata la procedura per il calcolo di una nuova shape da quella di par

tenza in base alla predizione dell'algoritmo analizzante. Questa procedura è il punto in

cui si è integrato il lavoro svolto nell'applicazione Eye Tracking esistente.

Il flusso dell'algoritmo svolge le seguenti operazioni:

62

Diagramma 5.2


Dal diagramma di flusso si nota una caratteristica importante dell'algoritmo: l'aggiorna

mento del modello avviene in modo incrementale, attraverso la variazione dei suoi pesi.

Il vantaggio di questa metodo rende l'algoritmo molto veloce per piccole variazioni tra

una shape e l'altra, poiché non deve adattarsi partendo dalla shape media. Questo vantag

gio si vanifica se la differenza tra una shape e la successiva è elevata.

Viene riportato il codice della procedura che realizza quanto descritto:

void Active::Step()

{PUNTO_DOUBLE gio_baricentro;int i,j,k;double Acc,Temp;

if(gio.Iterazione==0) // preparazione per le iterazioni di ricerca{vai=true;

// trovo il baricentro della forma mediaBaricentro.X = Baricentro.Y = 0;for(i=0;i<DIMENSIONE;i++){

Baricentro.X = Baricentro.X + Media[i].X;Baricentro.Y = Baricentro.Y + Media[i].Y;

}Baricentro.X = Baricentro.X / DIMENSIONE;Baricentro.Y = Baricentro.Y / DIMENSIONE;Copy(Shape,Media);for(i=0;i<DIMENSIONE;i++){

Shape[i].X = Posizione.X - (Baricentro.X - Shape[i].X);Shape[i].Y = Posizione.Y - (Baricentro.Y - Shape[i].Y);

}gio.best1.dist=DBL_MAX;// DEBUG:gio_baricentro.X=Posizione.X;gio_baricentro.Y=Posizione.Y;gio.set_immagine(pbmfh);for(i=0;i<NUMEROAUTOVALORI;i++){

Pesitot[i]=0;}

}else // non è la prima iterazione{

// trovo il baricentro della forma ShapeBaricentro.X = Baricentro.Y = 0;

63


for(i=0;i<DIMENSIONE;i++){

Baricentro.X = Baricentro.X + Shape[i].X;Baricentro.Y = Baricentro.Y + Shape[i].Y;

}Baricentro.X = Baricentro.X / DIMENSIONE;Baricentro.Y = Baricentro.Y / DIMENSIONE;for(i=0;i<DIMENSIONE;i++){

Shape[i].X = Posizione.X - (Baricentro.X - Shape[i].X);Shape[i].Y = Posizione.Y - (Baricentro.Y - Shape[i].Y);

}}

// calcolo i nuovi pesi come P=P(iterazione precedente)+dpfor(i=0;i<NUMEROAUTOVALORI;i++){

Pesitot[i]+=Pesi[i];}Copy(Predizione,Shape);

//Chiamata alla procedura ANALIZZANTECopy(Predizione,gio.trovashape6bis(Shape,Pesitot));

//allineo la shape alla predizione così mantengo la roto-traslazione della predizione e calcolo gli scarti per avere i pesi. Traslo la forma media sulla predizione

Copy(Base,Predizione);// Predizione e` la forma allineanteCopy(Sorg,Shape);// Shape e` la forma da allineareAllinea();Copy(Shape,Dest);for(i=0;i<DIMENSIONE;i++) // calcolo gli scarti dx{

Scarti[i].X = Predizione[i].X - Shape[i].X;Scarti[i].Y = Predizione[i].Y - Shape[i].Y;

// Attenuo l'effetto dell'algoritmo analizzante sul calcolo del nuovo modelloif(fabs(Scarti[i].X)<8){

Scarti[i].X/=2;}else{

Scarti[i].X=4;}if(fabs(Scarti[i].Y)<8){

Scarti[i].Y/=2;}else{

Scarti[i].Y=4;}

}// calcolo i nuovi pesi dp=trasposta(P)*dx

64


i = 0;Acc = 0;for(j=0;j<NUMEROAUTOVALORI;j++){

i = 0;Acc = 0;for(k=0;k<DIMENSIONE;k++){

Acc = Acc + Scarti[k].X*AutoVettori[i][j];i++;Acc = Acc + Scarti[k].Y*AutoVettori[i][j];i++;

}Pesi[j] = Acc;

}// deformo il modello con i nuovi pesi dp: si calcola in un primo tempo la variazione e poi si somma alla forma di partenza

for(i=0;i<DIMENSIONE;i++)Deviazione[i].X = Deviazione[i].Y = 0;

i = 0;for(k=0;k<DIMENSIONE;k++){

Temp = 0;for(j=0;j<NUMEROAUTOVALORI;j++)

Temp = Temp + AutoVettori[i][j]*Pesi[j];Deviazione[k].X = Temp;i++;Temp = 0;for(j=0;j<NUMEROAUTOVALORI;j++)

Temp = Temp + AutoVettori[i][j]*Pesi[j];Deviazione[k].Y = Temp;i++;

}Baricentro.X = Baricentro.Y = 0;for(i=0;i<DIMENSIONE;i++){

Baricentro.X = Baricentro.X + Shape[i].X;Baricentro.Y = Baricentro.Y + Shape[i].Y;

}Baricentro.X = Baricentro.X / DIMENSIONE;Baricentro.Y = Baricentro.Y / DIMENSIONE;

// Si aggiorna la shape sommando la variazione calcolatafor(i=0;i<DIMENSIONE;i++){

Shape[i].X = Shape[i].X + Deviazione[i].X;Shape[i].Y = Shape[i].Y + Deviazione[i].Y;

65


}// aggiorno la pos iniziale in base alla traslazione dx e dy avuta dalla shape complessivamente

Posizione.X+=gio.best1.X;Posizione.Y+=gio.best1.Y;

}

5.1.6 Strutture dati per la ricerca del greylevel di confronto

La prima struttura implementata è quella ad albero con la chiave di ricerca ricavata dai

valori dei pesi del modello, nelle cui foglie sono memorizzati i greylevel relativi.

La seconda implementazione è una semplice memoria associativa, introdotta per far

fronte ai limiti e alle difficoltà di selezione del greylevel evidenziate dalla struttura ad al

bero.

L 'obiettivo consiste nell'individuare il miglior greylevel per ogni iterazione dell'algorit

mo, in modo da far convergere il modello alla forma presente nell'immagine.

Di seguito verranno esposti i particolari implementativi delle due strutture riportando al

cune considerazioni sul loro funzionamento.

5.1.6.1 Struttura ad albero

Una struttura ad albero viene implementata attraverso dei nodi intermedi che determina

no quale ramo dell'albero debba essere percorso per arrivare alla foglia desiderata. Per

motivi di efficienza, la struttura è stata implementata da un vettore i cui elementi sono le

foglie dell'albero; si decide quale foglia debba essere considerata attraverso una funzione

che dipende dai valori assunti dai pesi del modello. Quindi, concettualmente è una strut

66


tura ad albero, ma l'accesso viene calcolato con una funzione che ricorda quella di una

tabella hash. Questa struttura si differenzia da una tabella hash, in quanto per il calcolo

del valore della funzione non vengono usati i greylevel stessi, ma altri dati ad essi asso

ciati; inoltre, se due greylevel del training-set ricadono nella stessa foglia, non si crea

una lista per contenerli tutti, ma viene semplicemente calcolato il loro valore medio.

Il vettore totale è diviso in un certo numero di sotto-vettori ( ramip0 ) a cui si associa un

intervallo (passo0=2*Range[0]/ramiP0) dei valori possibili assunti dal peso0; quindi il

primo sotto-vettore è associato ai valori del Peso0 nell'intervallo (-Range[0], -Range

[0]+passo0), il secondo nell'intervallo (-Range[0]+passo0, -Range[0]+2*passo0) e così

via.

In questo modo durante la fase di riconoscimento si considera sempre il sotto-vettore as

sociato in base al valore del peso0 .

Ogni sotto-vettore è suddiviso, a sua volta, in sotto-vettori in base al valore del peso1 e

del Range[1] relativo. Questo procedimento è ripetuto per tutti i pesi considerati nel mo

dello.

L'albero è stato implementato con 3 livelli di sotto-vettori, per ognuno è stata associata

una componente principale (Illustrazione 5.5).

L'inizializzazione della struttura avviene con l'inserimento dei greylevel appartenenti al

training-set e, poiché non sempre si ha un training-set capace di coprire tutte le foglie

dell'albero, si ricorre ad una assegnazione dei valori in base agli elementi vicini.

Durante il riconoscimento i pesi del modello, ottenuti dall'algoritmo che gestisce la sha

pe, vengono utilizzati per ricavare la posizione della foglia nell'albero.

67


Di seguito si riporta la procedura che ricava la foglia a partire dai pesi del modello:

inline int Analisi::trovafoglia( double *Pesi, unsigned long int E){

int i,j,k;/* il valore delle costanti definisce il numero di possibili ramificazioni dell'albero dei greylevel#define ramiP0 7 //=livelli del peso P1 del modello#define ramiP1 7 //=livelli del peso P2 del modello

68

Illustrazione 5.5


#define ramiP2 7 //=livelli del peso P2 del modello#define ramiENERGIA 7 //#define FOGLIE 349//=ramiP0*ramiP1*ramiP2#define FATTORE_L1 49//ramiP1*(ramiP2)#define FATTORE_L2 7//(ramiP2)*/temp_d=*(Pesi);temp_d+=Range[0];// per essere sempre positivo si aggiunge il fondoscalatemp_d/=passo0;// così varia tra 0 e 2*Range[0]i=(int)(temp_d);i*=FATTORE_L1;temp_d=*(Pesi+1);// prende il successivo doubletemp_d+=Range[1];// per essere sempre positivo si aggiunge il fondoscalatemp_d/=passo1;// così varia tra 0 e 2*Range[1]j=(int)(temp_d);i+=j*FATTORE_L2;temp_d=*(Pesi+2);// prende il successivo doubletemp_d+=Range[2];// per essere smpre positivo si aggiunge il fondoscalatemp_d/=passo2;// così varia tra 0 e 2*Range[2]k=(int)(temp_d);i+=k;foglia=i;if(i<0)

i=0;if(i>=FOGLIE)

i=FOGLIE-1;return i;}

Nell'applicazione di questo metodo si rileva un'instabilità nel riconoscimento e, di con

seguenza, una variabilità della forma individuata dal modello. Questo è da attribuirsi in

parte alla variabilità ambientale e in parte ad un limite dell'algoritmo: il risultato dipende

soprattutto dal punto iniziale della ricerca della shape.

Nel corso delle iterazioni l'algoritmo non riesce ad individuare sempre il miglior greyle

vel soffermandosi su uno di quelli intermedi. Infatti, ad ogni iterazione l'algoritmo indi

vidua la nuova forma da cui ricavare i valori dei pesi necessari alla determinazione del

greylevel da usare nella iterazione successiva.

Il programma Training è stato fondamentale per comprendere questo comportamento, in

quanto si può seguire l'evolvere del modello ad ogni iterazione.

Inoltre, l'impossibilità di iterare la ricerca per tutti i punti dell'immagine, per ovvi motivi

69


computazionali, ha prodotto dei risultati non soddisfacenti; pertanto è stato necessario

individuare un metodo alternativo di scansione e valutazione dell'immagine.

5.1.6.2 Memoria associativa

La memoria associativa è una struttura più semplice con una velocità di accesso ai dati

inferiore rispetto a quella della struttura ad albero descritta nel paragrafo precedente;

essa, però, permette l'individuazione dei dati inseriti al suo interno in modo arbitrario.

Purtroppo, la struttura ad albero non si è rivelata idonea per risolvere questo problema,

quindi è stata adottata la seguente procedura:

1) nelle prime iterazioni si considera solo il migliore greylevel determinato dai pesi as

sociati alla forma individuata nell'iterazione precedente;

2) nelle successive iterazioni si considerano i primi greylevel in base alla distanza che i

pesi del modello hanno rispetto a quelli del training-set: tra tutte le distanze calcolate

vengono prese le migliori N e i relativi greylevel sono utilizzati per la ricerca della

forma.

Di seguito si riporta la procedura integrale che determina il vettore dei migliori elementi

del training-set da utilizzare per la fase di analisi dell'immagine.

bool Analisi::set_greylevel2( double *Pesi_a){int i,j;// trovo l'elemento della memoria associativa con distanza minore rispetto ai pesi ricevutifloat temp,dist, bestdist;int best_elem,k,esci,z;if(Iterazione>STEP2){// FASE 2 per le iterazioni successive si cerca il best al veriare del greylevel for(k=0;k<NUM_FILA_BEST;k++){

70


fila_best_dist[k]=FLT_MAX; }// calcolo la distanza tra i pesi del modello e i pesi degli elementi del training-set for(i=0;i<NumeroFileGreylevel;i++){ dist=0; for(j=0;j<NUMEROAUTOVALORI;j++){ temp=(float)(associa[i].Pesi[j]-Pesi_a[j]); temp*=temp; dist+=temp; } esci=0; for(z=0;((z<NUM_FILA_BEST)&&(!esci));z++){ if(dist<fila_best_dist[z]) {// ho trovato un greylevel con una distanza dai pesi del modello valida quindi scalo di uno i best successivi

for(k=NUM_FILA_BEST-1;k>z;k--){ fila_best[k]=fila_best[k-1];

fila_best_dist[k]=fila_best_dist[k-1];}fila_best[z]=i; // memorizzo l'indice relativo al greylevel nel vettore dei migliori qfila_best_dist[z]=dist;esci=1;// interrompo la scansione del “for z” perché l'elemento i-esimo è stato inserito

} } } bestdist=fila_best_dist[0]; best_elem=fila_best[0];// è il miglior elemento della matrice.........}else // Fase =1 e quindi si individua solo il migliore dei greylevel del training-set{ bestdist=FLT_MAX; for(i=0;i<NumeroFileGreylevel;i++){ dist=0; for(j=0;j<NUMEROAUTOVALORI;j++){ temp=(float)(associa[i].Pesi[j]-Pesi_a[j]); temp*=temp; dist+=temp; } if(dist<bestdist){ bestdist=dist; best_elem=i;// è il miglior elemento della matrice } } foglia=best_elem;// var gloale per debug e visione del numero in esecuzione

71


}return true;}

Con N greylevel la ricerca non si sofferma su una zona dell'immagine o su una forma del

modello errata, riuscendo a convergere costantemente alla posizione e forma corretta.

La grande variabilità a cui è soggetto il riconoscimento di un pattern nell'immagine ha

reso necessario l'utilizzo di un insieme più ampio di elementi del training-set.

Questo metodo ha permesso una diminuzione della distanza finale ricavata dalla funzio

ne di valutazione fino al 75%, ma ha aumentato il tempo totale di elaborazione in modo

proporzionale al numero di elementi del training-set presi in considerazione.

Risulta evidente come questo parametro sarà oggetto di compromesso tra la precisione

del riconoscimento e la velocità di elaborazione desiderata.

La funzionalità è stata verificata con il programma Training che ha permesso di valutare

il risultato dell'analisi passo passo: sono stati svolti dei test con immagini del training-set

per verificare se l'algoritmo sia in grado di utilizzare il corretto greylevel e, in seguito, su

nuove immagini per verificare la capacità reale di riconoscimento.

72


Attraverso l'uso di immagini del training-set si è stata valutata la capacità di individuare

correttamente il greylevel da utilizzare per il riconoscimento dei contorni della forma.

Nel caso più sfavorevole, ossia quando l'algoritmo non riesce ad utilizzare il greylevel

associato all'immagine da analizzare, la procedura adotta comunque il greylevel di una

shape “vicina”, in basa alla griglia usata nella creazione del training-set.

5.1.7 Sviluppo del codice critico in Assembler

Durante la fase di sviluppo, l'imponente mole di dati da elaborare ha reso necessario po

tenziare la velocità di elaborazione, ricorrendo ad una implementazione di queste proce

dure in assembler. Inoltre, la disponibilità negli attuali processori di istruzioni specializ

zate per operazioni semplici e ripetute su grandi quantità di dati ha favorito la ricerca di

questa soluzione.

Il linguaggio di programmazione C++ permette di integrare facilmente queste istruzioni

attraverso l'uso della macro _asm{.........}. Nella fase iniziale è stato necessario un up

grade del compilatore integrato nel Visual Studio al fine di supportare “l'assembler inli

ne”.

5.1.7.1 Set di istruzioni MMX e SSE

I processori dei personal computer nel corso degli anni si sono evoluti aumentando il

grado di parallelismo per eseguire maggiori elaborazioni nell'unità di tempo. Oggigiorno

sono integrati due “core” all'interno dello stesso package, rendendo di fatto i personal

computer degli elaboratori multiprocessore.

73


Nel corso di questa evoluzione, quando i processori elaboravano un'istruzione alla volta

attraverso un upgrade dell'Aritmetic Logic Unit (ALU), sono state introdotte delle istru

zioni particolari che permettono di svolgere la stessa operazione su un gruppo di dati

contemporaneamente. Questo set di istruzioni rientra in un gruppo denominato con l'a

cronimo S.I.M.D. , cioè Single Intruction Multiple Data: grazie ad esse si possono elabo

rare grandi quantità di dati, sia nel formato intero, sia in quello floating-point.

L'utilizzo di queste istruzioni comporta la conoscenza dettagliata della struttura interna

del processore, pertanto sono stati consultati i databook della Intel sulle potenzialità e i

limiti di queste istruzioni. Per esempio un aspetto da considerare, quando si vuole imple

mentare una procedura in assembler, è la sovrapposizione fisica dei registri utilizzati

dalla Floating Point Unit (st0 – st7) con quelli usati dalle istruzioni SIMD sugli interi

(mmx0 – mmx7). Questa sovrapposizione non impedisce l'uso contemporaneo di en

trambi i set di istruzioni, ma comporta un tempo di ritardo necessario per lo switching

tra i due gruppi di registri. Quindi, l'utilizzo simultaneo di queste istruzioni potrebbe ri

durre i vantaggi ricercati.

I codici mnemonici impiegati per indicare uno degli otto registri delle istruzioni SIMD

intere sono mmx0 – mmx7, e i 64 bit che li compongono riescono ad elaborare fino ad 8

byte alla volta o, se raggruppati diversamente, 4 interi a 16 bit.

74


Con questi registri è possibile effettuare operazioni aritmetiche e logiche su gruppi di 8

byte, oppure 4 word o 2 doubleword a seconda delle istruzioni usate. In modo analogo

alle elaborazioni eseguite dalla Floating Point Unit, questi registri sono indirizzabili

come in uno stack e, quindi, quello in cima (mmx0) è interessato nella maggior parte

delle operazioni previste dal set di istruzioni. Questa struttura comporta il caricamento

preventivo nei registri degli operandi necessari per eseguire i calcoli.

ESEMPIO:

label3_p: fild X ;carica st0

fld st(2) ;metto st(2) in st(0)

frndint ; arrotondo st(0)

-

L'impiego del set di istruzioni STREAMING SIMD EXTENSIONS (SSE) comporta

l'introduzione di otto registri a 128 bit ( xmm0 – xmm7 ) con i quali si riescono a gestire

4 numeri in floating point nella notazione a 32 bit, oppure un floating point a 64 bit nella

parte meno significativa del registro.

Un'altra caratteristica importante di questi registri è la loro totale indipendenza da quelli

della FPU e da quelli “general-purpose”, consentendo un indirizzamento diretto con i

codici mnemonici XMM0 – XMM7.

75


Le operazioni in parallelo che si possono compiere su numeri reali floating point miglio

rano il processore come strumento di elaborazione per grandi quantità di dati scientifici.

Questa tesi ha utilizzato le istruzioni SSE per calcolare in real time dei greylevel derivati

e normalizzati, confrontandoli con i corrispondenti greylevel del training-set.

Per l'impiego delle istruzioni SSE si è proceduto per gradi e, in alcuni passaggi, è stato

necessario rivedere il flusso di elaborazione per adattarlo alle caratteristiche della pro

grammazione assembler: questo ha comportato uno studio del codice scritto in linguag

gio C++ relativo all'analisi dell'immagine. All'interno del codice sono state individuate

le parti critiche da ottimizzare, di conseguenza l'algoritmo è stato modificato nel seguen

te modo:

76


1. raggruppamento di tutto il codice che in qualche modo svolgeva elaborazioni

dell'immagine (pre-elaborazione, confronto, post-elaborazione);

2. riscrittura del codice per ottenere un'unica procedura generalizzata in grado di

elaborare i greylevel per tutti i punti del modello e trasformare in assembler una

sola funzione;

3. riorganizzazione delle operazioni svolte nell'algoritmo per favorire l'uso delle

istruzioni SSE sui dati.

Una volta riorganizzato il codice di alto livello, si è cercato di impiegare il più possibile

i registri interni, per limitare l'accesso alla memoria esterna e rendere, quindi, perfor

mante la procedura: i loop interni e le variabili più usate sono state assegnate ai registri

general-purpose liberi.

Al fine di disporre del numero massimo di registri ed evitare conflitti con il compilatore

C++ la procedura in assembler, come prima operazione, effettua un salvataggio dello

stato della macchina nello stack:

pushad

fnstcw control_word //{Save Current Control Word}

finit ;The FPU control word is set to 037FH (round to nearest, all exceptions ma

sked, 64-bit precision).

I registri vengono poi ricaricati al termine della procedura:

finit ; serve per azzerare lo stack della fpu e riportare le condizioni iniziali

fldcw control_word //{Restore Original Control Word}

popad

77


5.2 Valutazioni sperimentali e possibili sviluppi

Prima di riportare le modalità di valutazione dell'algoritmo è necessario descrivere il

metodo che esso impiega per valutare la presenza della shape nell'area dell'immagine

analizzata.

5.2.1 Valutazione dell'efficacia del riconoscimento: distanza eu

clidea

La teoria di Cootes et al.[1] utilizza nel confronto dei greylevel la distanza di Mahalano

bis, ipotizzando una distribuzione normale dei dati; essa, per ogni punto del modello,

misura la probabilità di avere il greylevel, ricavato dall'immagine reale, equivalente a

quello medio calcolato dal training-set.

Nel nostro caso il PDM ha una variabilità intrinseca rispetto alla forma media dovuta al

movimento della pupilla. Di conseguenza i greylevel del modello avrebbero, in quei

punti, una distribuzione normale con una varianza elevata in quanto ricavata da valori

molto variabili.

La funzione di valutazione deve riconoscere corretto un greylevel diverso rispetto alla

media, a causa della pupilla a destra o sinistra.

Quindi, la “mahalanobis distance”, applicata al riconoscimento dell'occhio, fornisce una

stima meno precisa di quella calcolata con un greylevel che tiene conto della posizione

della pupilla e delle palpebre.

Occorre una funzione più generica non vincolata al valore medio, che possa essere uti

lizzata in modo più specifico sui vari valori del training-set.

78


La distanza euclidea considera i singoli greylevel del training-set e li confronta con quel

li ricavati dall'immagine.

Nella seconda fase dell'analisi si effettua il confronto con un numero maggiore di greyle

vel del training-set, selezionati attraverso il calcolo della distanza tra i corrispondenti

pesi e quelli del modello.

79

Illustrazione 5.6 stesso punto del modello: variazione

del greylevel al variare della posizione dell'iride


5.2.2 Valutazione del funzionamento

Nella valutazione dell'algoritmo sviluppato è opportuno considerare tutti i fattori che in

cidono sulle prestazioni, come per esempio la robustezza del training-set, testando il ri

conoscimento su individui diversi o variando le condizioni ambientali.

Le principali limitazioni introdotte nell'algoritmo, per renderlo compatibile con i vincoli

temporali, determinano il numero di iterazioni possibili, il punto di partenza dell'analisi

e il numero di greylevel da considerare.

Vista la fase iniziale di sviluppo di questa ricerca, ci limiteremo ad una verifica dell'al

goritmo al variare dei fattori interni e non ci soffermeremo su altri fattori che sarebbe

prematuro considerare in questa fase.

La valutazione dell'algoritmo consisterà nel misurare la distanza tra i punti della shape,

indicati manualmente nell'immagine, e quelli che l'algoritmo individua al variare dell'ite

razione e del numero di greylevel considerati.

Nel corso dello sviluppo dell'algoritmo è stata rilevata una dipendenza del risultato dal

punto di partenza dell'analisi, quindi, si è ritenuto opportuno eseguire diversi test per

quantificare questa dipendenza.

Le due tabelle seguenti riportano i valori assegnati ai parametri più significativi dell'al

goritmo: sono stati svolti 8 test, ciascuno di essi ha valutato l'algoritmo con sei posizioni

di partenza casuali fissate in un intorno dell'occhio da individuare.

I cinque test iniziali hanno in comune una prima fase di ricerca con una griglia di scan

sione della zona da analizzare più fitta. Questo tipo di scansione comporta un tempo di

ricerca maggiore, ma aumenta la precisione di posizionamento della shape.

80


Gli altri test 6-7-8, ricercano l'occhio con una griglia di scansione meno fitta (-32, +32,

passo 32).

A loro volta, i test appartenenti ai due gruppi si differenziano per il numero di greylevel

del training-set da utilizzare nella seconda fase, 20 o 50, e per il loro spessore, 1 o 3.

La valutazione dell'efficacia dell'algoritmo in generale sarà misurata dalla capacità di

convergenza della shape del modello con quella reale nell'immagine, calcolando la som

ma delle distanze tra i corrispondenti punti.

Di seguito sono riportate le immagini iniziali e finali relative ad una delle sei prove ef

fettuate per ognuno degli 8 test svolti.

81

Test 1

Test 2


82

Test 3

Test 4

Test 5


83

Test 6

Test 7

Test 8


Vengono riportate le tabelle con il dettaglio dei test effettuati e i valori assegnati alle va

riabili dell'algoritmo. Per chiarezza la seconda riga delle tabelle indica i valori dei cicli

for per le traslazioni dx e dy nella fase1 impiegata per le prime 3 iterazioni (iter0-2); la

terza riga indica i valori per le variabili q e z nelle iterazioni 3-13.

Variabili \ test test1 test2 test3 test4 test5

Fase1 iter0-2 for x e y (+dv,-dv,step)=(-30,+30,10),(-5,5,5),(-2,2,2) Fase2 iter3-13 for q e z (+dv,-dv,step)=(-2,2,2) z1=6 z2=5spessore greylevel 1 1 1 3 3

lunghezza greylevel 41 41 41 41 41

numero shape 2a fase(fase2 dopo 3 iterazioni)

50 20 20 20 50

for su x e y 2a fase no no si no noUso Proc. ASM si si si si sinumero prove

(pto iniziale diverso)6 6 6 6 6

shape test 53 53 53 53 53numero iterazioni 13 13 13 13 13Dist. media finale 71,12 117.55 107,39 119,73 87,64

T per 13 iterazioni (sec) 3,495 1,552 12,048 3,785 8,903

84


Variabili \ test test6 test7 test8

Fase1 iter0-2 for x e y (+dv,-dv,step)=(-32,+32,32),(-16,16,16),(-8,8,8),(-4,4,4) Fase2 iter3-13 for k e z (+dv,-dv,step)=(-2,2,2) z1=6 z2=5spessore greylevel 3 1 1

lunghezza greylevel 41 41 41numero shape 2a fase

(fase2 dopo 4 iterazioni)=q50 50 50

for su x e y 2a fase no no noUso Proc. ASM si si nonumero prove

(pto iniziale diverso)6 6 6

shape test 53 53 53numero iterazioni 13 13 13Dist. media finale 129,41 494,17 126,2

T per 13 iterazioni (sec.) 8,032 3,105 3,185

Le condizioni che hanno dato il miglior risultato sono relative al test1, ma per compren

derne le ragioni è opportuno considerare i due test migliori, test1 e test5, perché hanno

in comune una fitta rete iniziale di ricerca e l'uso di un maggior numero (50) di greylevel

del training-set nella seconda fase. I test 6-7-8, pur avendo anch'essi 50 greylevel del

training-set per la fase2 , non hanno dato buoni risultati per la minore precisione della

griglia utilizzata nella ricerca della shape iniziale.

Da queste considerazioni si può concludere che per ottenere un buon risultato è necessa

ria una prima fase di ricerca, che posizioni correttamente la shape nell'immagine, e una

seconda fase di adattamento, che utilizzi un numero sufficiente di elementi del training-

set. Inoltre, i tempi di ricerca della prima fase possono essere annullati grazie all'adatta

mento incrementale della shape utilizzando quella ricavata nell'iterazione precedente. In

tal modo è possibile individuare la forma dell'occhio direttamente con la seconda fase

dell'algoritmo.

85


I grafici riportati descrivono l'andamento delle distanze tra la shape del modello e quella

reale al variare del numero di iterazioni. Poiché sono state effettuate sei prove per cia

scun test, si riportano nel grafico le medie dei loro valori.

Come si nota il test7 ha un valore medio a regime anomalo, ma non corrisponde ad un

valore rappresentativo. Infatti, analizzando le sei prove del test7 singolarmente, si osser

va una discreta convergenza per alcuni, mentre per gli altri una forte divergenza: la posi

zione di partenza è la causa del problema, in quanto è l'unica differenza esistente tra le

sei prove svolte.

Di seguito viene riportata la tabella dettagliata delle prove e la relativa media.

86

Disegno 5.5: grafico delle medie delle sei prove per gli 8 test effettuati

1 2 3 4 5 6 7 8 9 10 11 12 130

50100150200250300350400450500550600650700750800850900

Confronto

test1test2test3test4test5test6test7test8

iterazioni

dist

sha

pe


Per visualizzare meglio graficamente la differenza tra i vari test, si escludono i valori

medi relativi all'iterazione iniziale e tutti i valori del test7 che risultano anomali rispetto

agli altri.

87

Disegno 5.6: test7 - le sei prove e la loro media

posiz1 posiz2 posiz3 posiz4 posiz5 posiz6 Media0 1441,81 1037,25 1043,33 960,67 1492,66 973,76 1158,251 340,36 798,26 1043,81 2094,18 416,86 491,93 864,232 339,81 236,84 958,74 1474,4 420,29 371,27 633,563 259,07 173,62 1251,18 1182,43 111,66 234,73 535,454 165,03 175,87 1241,76 1020,97 196,55 243,69 507,315 149,06 167,08 1241,15 1022,88 178,69 226,54 497,566 144,3 165,01 1241,27 1023,35 172,22 216,99 493,867 139,21 164,71 1241,43 1024,01 170,58 216,78 492,798 138,73 164,1 1242,12 1024,83 170,41 211,02 491,879 138,66 163,42 1242,98 1026,6 171,53 211,19 492,410 138,65 163,19 1243,56 1026,66 173,56 211,81 492,9111 138,57 163,13 1243,98 1028,23 174,21 212,8 493,4912 138,39 163,1 1244,44 1028,45 174,83 214,06 493,8813 138,85 163,1 1244,81 1029,46 175,34 213,48 494,17

1 2 3 4 5 6 7 8 9 10 11 12 130

50

100

150

200

250

300

350

400

450

500

550

600

Confronto 1-2-3-4-5-6-8

test1test2test3test4test5test6test8

iterazione

dist

sha

pe


Dall'analisi dei grafici delle medie delle sei prove effettuate per ogni test, si rileva la ra-

pida convergenza della shape a quella reale: è possibile interrompere il processo di adat

tamento della forma dell'occhio alla quinta o sesta iterazione, poiché non si rilevano va

riazioni apprezzabili in quelle successive.

Inoltre, si evince che il primo e il quinto sono i due test migliori e si differenziano sol

tanto per lo spessore del greylevel. Diversamente da quanto previsto in fase di analisi del

problema, si nota che ad un aumento del numero di pixel considerati diminuiscono le

prestazioni in termini di riconoscimento finale della forma.

Per evidenziare il buon funzionamento visualizzato graficamente nei test 1 e 5 si riporta

no i dati raccolti in ognuna delle sei prove effettuate e la loro media.

88


posiz1 posiz2 posiz3 posiz4 posiz5 posiz6 Media0 1364,89 1117,26 1062,23 1340,35 933,45 911,41 1121,61 208,12 270,69 91,79 340,61 142,63 198,87 208,782 83,7 103,15 85,89 120,11 105,64 68,21 94,453 85,61 84,45 81,34 109,06 95,83 83,69 904 68,65 75,05 70,69 89,66 81,01 73,16 76,375 63,01 71,51 67,65 81,5 75,15 72,19 71,836 60,61 69,21 67,56 77,11 72,38 72,27 69,867 59,5 70,98 68,02 75,39 73,43 74,11 70,248 59,11 72,36 67,66 74,17 73,57 75,05 70,329 59,03 73,03 67,55 74,08 73,96 75,11 70,4610 58,88 73,55 67,5 74,79 74,2 75,41 70,7211 58,82 73,83 68,02 75,2 74,33 75,72 70,9912 58,8 74,03 67,73 75,48 74,4 75,89 71,0613 58,8 74,09 67,58 75,85 74,43 75,99 71,12


89


posiz1 posiz2 posiz3 posiz4 posiz5 posiz6 Media0 1463,42 1063,07 1060,34 1503,79 1011,06 1052,76 1192,411 462,56 106,02 76,82 412,8 89,67 265,28 235,522 206,6 117,67 70,21 262 93,28 100,5 141,713 144,24 111,35 87,41 172,62 89,75 90,48 115,974 120,45 89,73 73,98 176,14 72,19 68,63 100,195 113,49 75,7 71,58 164,89 65,62 62,91 92,376 112,01 66,84 71,58 169,33 64,71 63,22 91,287 111,33 64,38 72,68 156,05 65,13 63,44 88,838 111,71 63,65 74,1 152,42 65,67 63,93 88,589 110,36 63,76 74,63 149,08 66,04 63,95 87,9710 111,82 64,44 75,05 148,13 66,25 64,23 88,3211 110,58 64,9 75,28 146,32 66,35 64,15 87,9312 111,63 65,35 75,4 143,73 66,41 64,11 87,7713 111,37 65,55 75,47 142,9 66,44 64,09 87,64


6 Conclusioni

Questa tesi ha realizzato un algoritmo di analisi per immagini statiche a colori finalizza

to alla ricerca dei contorni dell'occhio, successivamente integrato nel programma di Eye

Tracking esistente per seguirne i movimenti.

Partendo dall'Active Shape Model di Cootes et al., è stata dimostrata la convergenza del

l'algoritmo verso la forma da riconoscere rispetto ai limiti stabiliti nella fase di valuta

zione. Tuttavia, la soluzione individuata considera tutti i greylevel del training-set per

la scelta del sottoinsieme da utilizzare nell'analisi dell'immagine.

Sono state testate due strutture dati per la memorizzazione della relazione tra i coeffi

cienti delle componenti principali del modello ( PCA ) e i valori dei greylevel relativi a

ciascun punto della forma.

La teoria di Cootes et al. si applica su immagini monocromatiche con forme variabili

che hanno dei greylevel relativamente uniformi nei contorni della shape al variare della

forma stessa. Con questo lavoro si è dimostrata l'applicabilità del metodo anche al rico

noscimento di forme con greylevel molto variabili, come quelli dell'occhio, attraverso

l'uso di immagini a colori. La soluzione individuata si è quindi differenziata dalla teoria

di base per l'uso di greylevel specifici, soprattutto per la grande variabilità degli stessi.

La determinazione del miglior insieme di elementi del training-set, da usare per ricono

scere correttamente i punti della forma, è il problema principale della fase di riconosci

mento. L'applicazione Training ha reso possibile non soltanto la valutazione del funzio

namento dell'algoritmo sviluppato, ma soprattutto ha permesso di ottenere la soluzione

finale corretta.

I risultati dei test di valutazione hanno dimostrato un miglioramento delle prestazioni

90


aumentando il numero di elementi del training-set impiegati: usando N elementi, al pas

sare del numero di iterazioni, il modello può evolvere in N diverse direzioni, compresa

quella della forma dell'occhio in esame.

Lo spessore dei greylevel durante l'analisi è un parametro da cui ci si aspettava un mi

glioramento delle prestazioni all'aumentare dello stesso, invece, l'algoritmo è meno pre

ciso nell'individuazione dei contorni dell'occhio utilizzando elementi del training-set

con greylevel più larghi.

Esistono molte variabili esterne non considerate che probabilmente riducono lo spazio di

applicabilità di questo algoritmo, come il variare dell'utente o del contesto in cui si cam

piona l'immagine e, in questa direzione, si potranno sviluppare versioni migliori dell'al

goritmo.

Un altro aspetto su cui è possibile introdurre dei miglioramenti riguarda la determinazio

ne della posizione dell'occhio: attualmente è necessario indicare con il mouse la zona in

cui è presente l'occhio e, come dimostrato dai test di verifica, il risultato finale dipende

molto dall'individuazione corretta dell'area in cui si trova. La ricerca di un algoritmo ge

netico può essere una valida soluzione al problema, peraltro già sperimentata in altri stu

di associati all'Eye Tracking.

Per definizione il training-set deve essere rappresentativo di tutta la popolazione dei pos

sibili pattern riconoscibili, quindi l'adattamento a nuovi pattern non rappresentati dal

training-set non può che essere parziale. Questo ostacolo in realtà è solo apparente, in

quanto è sufficiente aumentare il numero di pattern del training-set per rendere il model

lo più rappresentativo delle forme possibili.

Secondo il principio delle memorie associative si richiamano informazioni attraverso al

tre informazioni e, nel nostro caso, i pesi del modello sono i dati in ingresso e i greylevel

91


ad essi associati sono i dati in uscita. Ne consegue che un possibile miglioramento del

l'algoritmo sviluppato può realizzarsi attraverso l'applicazione di reti neurali per la deter

minazione del sottoinsieme di greylevel da utilizzare nella fase2 dell'algoritmo.

Attualmente, la scelta degli elementi del training-set avviene in base alle distanze che i

relativi pesi hanno da quelli del modello, ma si potrebbe ottenere un sottoinsieme otti

mizzato attraverso una rete neurale che abbia come input i pesi del modello, il numero di

iterazione o altri fattori da cui può dipendere questa scelta.

Infine questo programma, basato su un algoritmo di analisi e uno di gestione del model

lo della forma, può essere utilizzato più in generale per il riconoscimento di un'ampia

classe di forme. Tuttavia non può essere utilizzato in quelle situazioni in cui sia neces

sario un riconoscimento di forme a priori non conosciute, poiché non è possibile creare

il training-set relativo.

Il lavoro svolto si è inserito in un percorso più ampio che mira alla realizzazione di

software per favorire l' interazione uomo-computer; le potenzialità di questo progetto

hanno reso lo studio stimolante e gratificante.

92


7 Bibliografia

1. T.F. Cootes, C.J. Taylor, D.H. Cooper, and J. Graham: Active Shape Model –

Their Training and Application, Computer Vision and Image Understanding

Vol. 61, No.1, January, pp.38-59, 1995.

2. T.F. Cootes, A. Hill, C.J. Taylor and J. Haslam: The use of Active Shape Model

For Locating Structure in medical Images, Image and Vision Computing,

Vol.12, No.6, July 1994, pp.335-366.

3. T.F. Cootes, C.J. Taylor: Active Shape Model Search using Local Grey-Level

Models : A Quantitative Evaluation, Proc. British Machine Vision Conference

1993. BMVA Press, 1993, pp.639-648.

4. T. F. Cootes, G. J. Edwards and C. J. Taylor, Active appearance models, In Proc.

European Conf. on Computer Vision, volume 2, pages 484–498. Springer,

1998.

5. Davide Maltoni, Appunti del Corso di “Pattern Recognition”, 2000-2001 –

Università Bologna

6. A. A. Nielsen.

Analysis of Regularly and Irregularly Sampled Spatial, Multivariate, and Multi-

temporal Data, PhD thesis, Institute of Mathematical Modelling, Technical Uni

versity of Denmark, Lyngby, 1994.

7. M. Kass, A. Witkin, and D. Terzopoulos, Snakes: Active contour models, Inter

national Journal of Computer Vision. v. 1, n. 4, pp. 321-331, 1987.

8. A.L. Yuille, P.W. Hallinan, and D.S. Cohen. Feature Extraction from Faces

Using Deformable Templates. International Journal of Computer Vision, 99-111,

93


1992.

9. U. Grenander and D. M. Keenan, Towards Automated Image understanding, J.

Appl. Stat., 16 (1989).

10. Wikipedia.org per le definizioni di Eye Tracking, Human Computer Interaction,

Computer Vision e Pattern recognition

11. IA-32 Intel® Architecture Software Developer's Manual, Volumi 1-2A-2B: Basic Ar

chitecture-Instruction Set Reference

94

Politecnico di Torino - elite.polito.itelite.polito.it/files/thesis/fulltext/dettori.pdf · Si...

Documents

Transcript of Politecnico di Torino - elite.polito.itelite.polito.it/files/thesis/fulltext/dettori.pdf · Si...