Sistema di riconoscimento facciale basato su nuove tecniche di classificazione Pca-Lda

Capitolo1. Analisi del problema 
 1
Capitolo 1 
 
Analisi del Problema 
 
 
 
1.1 Il volto come parametro biometrico 
 
 
Negli ultimi anni l’informatica ha introdotto molte innovazioni nella vita di tutti i 
giorni: bancomat, carte di credito, posta elettronica, telefonini, acquisti via 
Internet, possibilità di archiviare enormi quantità di dati in spazi ridottissimi, ecc. 
A tale pervasività si è via via affiancato un importante problema: la sicurezza. La 
nostra vita è piena di password, pin, codici da ricordare, da non smarrire e da 
tenere fuori della portata di possibili truffatori. 
Non è un caso che, negli ultimi anni, si siano affermate discipline come la 
biometria, ossia sulla possibilità di sfruttare parti del corpo o comportamenti 
(psico-fisici) al fine di ricavare “codici” che permettano di riconoscere 
univocamente un individuo. 
Gli obiettivi principali dei sistemi biometrici sono: 
 ξ  un maggior livello di sicurezza 
 ξ  una maggior comodità per gli utenti 
 ξ  abbassamento dei costi di gestione 
Le tecniche oggi più diffuse si basano su impronte digitali e sul riconoscimento 
facciale. Altri parametri biometrici di elevato interesse, anche se meno comuni, 
sono quelli estraibili dall’analisi di: iride, retina, mano, firma autografa, odore, e 
modo di battere i tasti sulla tastiera. 
 
 
Capitolo1. Analisi del problema 
 2
1.2 Il riconoscimento facciale 
 
Il riconoscimento facciale consiste nella verifica dell’identità di un individuo 
attraverso l’analisi dei tratti del viso, proprio come avviene tra persone, in un 
incontro “faccia a faccia”. 
Le logiche che regolano l’intelligenza nei processi cognitivi sono oggetto di 
studio da parecchi anni: in molte università e centri di ricerca sin dagli anni ’60 si 
stanno sperimentando tecniche automatizzate di riconoscimento facciale, ma solo 
di recente la capacità di calcolo dei computer e gli algoritmi più efficienti hanno 
reso questa tecnica realmente utilizzabile su larga scala. 
Il riconoscimento è un processo mentale così istintivo per il cervello umano, che 
avviene senza il minimo sforzo apparente. Biologicamente ogni memorizzazione 
visiva consiste nell’eccitazione di una “traccia” di neuroni della corteccia 
cerebrale. Ogni percezione visiva genera una nuova “traccia” o ne rafforza una 
esistente. Al ripresentarsi di uno stimolo visivo già memorizzato nel passato il 
cervello recupera le informazioni (associazione immagine-entità) in maniera tanto 
più rapida quanto più la traccia è rimasta impressionata sulla corteccia. 
Il cervello umano, durante il riconoscimento,  lavora per schemi associativi ed è 
proprio su questo che l’intelligenza artificiale si basa per tentare di riprodurre tale 
comportamento nelle macchine. Già da anni sono disponibili strumenti largamente 
utilizzati, che si basano sull’associazione quali, ad esempio, i programmi OCR 
(per il riconoscimento di testo in un’immagine), ed i programmi di Speech 
Processing (per l’interazione vocale uomo-macchina). Se il riconoscimento di 
impronte digitali o di caratteri è semplificato dal fatto che le relative immagini 
sono mappe binarie di pixels (bianco/nero), per il trattamento di fotografie occorre 
considerare numerosi fattori interferenti, quali: ampie variazioni cromatiche, 
angoli di vista differenti e risoluzioni diverse. Nella fattispecie del riconoscimento 
di un volto le cose si complicano ulteriormente: il volto deve essere riconosciuto 
anche se presenta una diversa capigliatura, porta gli occhiali, cambia espressione,  
non ha più la barba, è illuminato diversamente, ecc. Si noti che le difficoltà sono 
analoghe a quelle che si incontrano nel riconoscimento vocale: il timbro di voce 
Capitolo1. Analisi del problema 
 3
cambia da persona a persona, ma anche in relazione allo stesso individuo in 
momenti e situazioni diverse. 
Da un punto di vista tecnico il riconoscimento facciale non è altro che un 
particolare problema di “Object Recognition” nel quale gli oggetti da riconoscere 
presentano particolari proprietà che li accomunano (es. posizione di occhi, bocca e 
naso) ed altre, più sottili, che permettono di distinguerli (es. lineamenti e forma 
del viso). 
 
 
Capitolo1. Analisi del problema 
 4
1.3 Settori di utilizzazione 
 
 
Il riconoscimento facciale, come ogni altra tecnica biometrica, interessa 
oggigiorno gran parte delle società alle prese con i sistemi di sicurezza. In 
particolar modo, il riconoscimento facciale è molto apprezzato per la caratteristica 
di non richiedere una particolare collaborazione da parte dell’utente. 
Non più la scomodità dei tesserini magnetici, di digitare password, o l’imbarazzo 
di appoggiare il dito su un sensore, ma il semplice sguardo verso una telecamera 
(eventualmente anche involontario). Inoltre, molto spesso, le postazioni PC 
standard sono già dotate di tutti i requisiti necessari. L’unico costo aggiuntivo può 
essere quello di una videocamera.  
Le modalità di riconoscimento utilizzate nelle tecnologie biometriche possono 
essere distinte in: 
 ξ  autenticazione (one-to-one matching) 
 ξ  identificazione (one-to-many matching) 
Da notare che allo stato attuale, oltre ai volti, solo le impronte digitali e l’analisi 
dell’iride consentono un efficace riconoscimento one-to-many. 
Alcuni esempi di utilizzo possono essere: 
- login su computer. 
- autenticazione dell’accesso ai siti web. 
- verifica di tessere personali: carte di credito, passaporti, patenti di guida, 
carta d’identità. 
- identificazioni in ambienti (affollati) da proteggere, e sorveglianza 
notturna: negozi, banche, stazioni, aeroporti, ecc. 
- accesso ad aree riservate: ospedali, uffici governativi o militari. 
- accesso a sportelli bancari automatici ATM (Automatic Teller Machine). 
- sistemi di apprendimento a distanza. Ad esempio nei corsi di laurea on 
line, oltre al reperimento di appunti e lezioni in Internet, sarebbe anche 
possibile sostenere gli esami senza necessariamente raggiungere la sede 
universitaria. 
Capitolo1. Analisi del problema 
 5
- in ambito finanziario, sia per le operazioni di borsa sia per le vendite di 
prodotti via Internet, la possibilità di riconoscere con certezza l’utente 
collegato in un dato momento assume una importanza vitale. Fino ad ora, 
questo tipo di servizi si limitava a verificare che l’utente collegato fosse in 
possesso di una data informazione (password) o di un determinato oggetto 
(tesserino magnetico) e di una informazione ad esso associata (codice pin). 
Il livello di sicurezza offerto da questo tipo di autenticazione si è 
dimostrato in più occasioni inadeguato. 
- identificazione rapida di segnalazioni fotografiche (es.: criminali) 
- interfacciamento uomo-macchina per le più svariate applicazioni 
interattive 
 
 
 
Capitolo1. Analisi del problema 
 6
1.4 Strutturazione della tesi 
 
Il capitolo 2 si occupa di dare una visione panoramica dello stato dell’arte 
raggiunto dalla ricerca nell’ambito del riconoscimento dei volti  
 
Il capitolo 3 offre una descrizione dettagliata delle tecniche PCA e LDA come 
strumento per il riconoscimento facciale. 
 
Il capitolo 4 introduce le nozioni ed i parametri fondamentali su cui si basa il  
sistema progettato. 
 
Il capitolo 5 descrive dettagliatamente l’algoritmo usato per il riconoscimento 
facciale esponendo i problemi riscontrati nell’analisi classica PCA+LDA che 
hanno spinto alla soluzione proposta. 
 
Nel capitolo 6 si discutono i risultati sperimentali rilevati in fase di test del 
sistema realizzato. 
 
Nel capitolo 7 si riportano, infine, le conclusioni ed una discussione sugli sviluppi 
futuri. 
  
 
 
 
 
 
 
Capitolo 2. Le tecniche di riconoscimento facciale 
 7
 
 
Capitolo 2 
 
 
Le tecniche di riconoscimento facciale 
 
 
La letteratura disponibile sul riconoscimento automatico dei volti si concentra 
principalmente sull’analisi dell’immagine frontale di un individuo. E’ da 
sottolineare come la maggior parte della letteratura assunta come base per questo 
lavoro di tesi, si concentri negli ultimi 5 anni. Questo suggerisce che si tratta di 
una moderna tendenza di ricerca a livello mondiale che non ha ancora trovato una 
definitiva sistematizzazione degli approcci disponibili e dei loro molteplici ambiti 
di applicazione. 
Questo capitolo descrive alcuni degli algoritmi più usati per il riconoscimento 
facciale sviluppati negli ultimi anni. 
 
 
Capitolo 2. Le tecniche di riconoscimento facciale 
 8
2.1 Le fondamenta teoriche 
 
Nei paragrafi successivi si illustraranno le basi matematiche e metodologiche che 
supportano le tecnologie di riconoscimento facciale illustrate a partire dal 
paragrafo 2.2 . 
 
 
2.1.1 Stating Matching 
 
Una singola immagine facciale viene confrontata con l’archivio degli individui a 
disposizione (campioni), le cui immagini sono riprese nelle medesime condizioni 
di luminosità. In un tipico database inoltre, le immagini sono già segmentate, 
automaticamente o manualmente, perciò la posizione di occhi risulta ben definita. 
La foto del soggetto da riconoscere (candidato), invece, viene ripresa senza 
controllo ottimale di luce, posa ed espressione. 
 Un sistema di riconoscimento facciale dovrebbe fornire una misura della 
vicinanza fra il candidato ed i campioni del database. 
 Molti sistemi di riconoscimento facciale producono un vettore multidimensionale 
che caratterizza un volto. Eseguendo un confronto vettoriale tramite distanza 
cartesiana, si ottiene appunto una misura della vicinanza. 
 
 
 
2.1.2 Rappresentazione e confronto 
 
Il successo nel riconoscimento facciale dipende dalla soluzione di due problemi: 
rappresentazione e confronto. Questi due aspetti saranno discussi 
dettagliatamente, proponendo in tal modo una struttura decisionale e statistica 
unificata per ogni tecnica descritta in seguito. 
Capitolo 2. Le tecniche di riconoscimento facciale 
 9
Per una data rappresentazione sono importanti il potere discriminante (quanto 
distano le facce secondo la rappresentazione adottata) e l’efficienza (quanto è 
compatta la rappresentazione). 
A livello elementare, l’immagine di un volto è un array bidimensionale di numeri 
(ad esempio, pixels a livelli di grigio) che può essere espresso in tre modi 
alternativi: 
1.  ⊥ Sixx
i
    ,  dove S è una griglia quadrata. 
2. 
T
n
xxxx ],.....,,[
21
   dove x è un vettore colonna costituito da righe di pixels 
concatenate, dove n è il numero totale di pixels nell’immagine e quindi x è un 
punto nello spazio euclideo n-dimensionale. 
3. 
T
m
xfxfxfxf ])(....,,)(,)([)(
21
   dove f(x) è detto vettore di features e dove 
f
1
 (x) , f
2
 (x) , …., f
m
 (x) sono funzioni lineari o non lineari. 
 
E’ importante notare che un’efficiente rappresentazione non ha necessariamente 
un buon potere discriminante. 
 
La fase del confronto si occupa di rintracciare un volto candidato x nell’insieme 
dei K campioni c
i
 . 
Ci sono molti metodi per il confronto: calcolo della distanza euclidea, calcolo 
della distanza di Mahalanobis, confronto basato su misure di correlazione o di 
covarianza, ecc. Una descrizione dettagliata di alcuni criteri di confronto viene 
data nel paragrafo 4.4.2.1, in cui vengono spiegate quelle usate nel sistema 
implementato in questa tesi. 
 
 
Capitolo 2. Le tecniche di riconoscimento facciale 
 10
2.1.3 Confronto fra Features e Templates 
 
Brunelli e Poggio [3] hanno confrontato l’approccio geometrico (feature-based 
matching) con quello olistico (Template Matching). A monte di entrambi i 
procedimenti viene illustrata una serie di normalizzazioni da eseguire 
sull’immagine per prepararla al confronto. Questo lavoro rappresenta una pietra 
miliare nell’ambito del riconoscimento di volti. 
 
2.1.3.1 Features based matching 
 
Nei sistemi che si basano su questo approccio [1] [2], vengono individuate le 
carattestiche facciali più significative (occhi, naso, bocca, ecc.) e le distanze tra 
esse, assieme ad altre caratteristiche geometriche del volto. Tutti i dati raccolti 
vengono combinati in “vettori di caratteristiche”, che sono usati per rappresentare 
un volto. 
Per effettuare il riconoscimento di un volto occorrerà: 
 ξ  calcolare i vettori delle caratteristiche dell’immagine di test ed i vettori 
delle caratteristiche di ogni immagine presente nel database. 
 ξ  scegliere una misura di similitudine (o più spesso un criterio di distanza 
minima)  tra tali vettori, per poter determinare l’identità di una faccia. 
Se le singole caratteristiche facciali non sono sufficientemente dettagliate, il 
riconoscimento rimane possibile se la configurazione geometrica complessiva 
delle caratteristiche facciali è sufficientemente discriminante. 
Brunelli e Poggio si occupano del confronto dell’immagine frontale del viso, 
perciò propongono features come: la posizione e la dimensione dei componenti 
facciali principali (occhi, sopracciglia, naso, bocca e contorno del viso). 
Il set di caratteristiche deve comunque soddisfare i seguenti requisiti: 
 ξ  la loro stima deve essere la più semplice possibile; 
 ξ  la dipendenza dalle condizioni di illuminazione deve essere bassa; 
 ξ  la dipendenza dalle piccole variazioni di espressioni facciali deve essere 
contenuta; 
 ξ  il contenuto informativo deve essere molto elevato. 
Capitolo 2. Le tecniche di riconoscimento facciale 
 11
 
Fig 2.1 Esempio di Feature Based Matching (con ellisse ideale) 
 
 
2.1.3.2 Strategia Template matching 
 
Tale approccio fa uso di un unico vettore delle caratteristiche che rappresenta 
l’intera sagoma facciale, piuttosto che un vettore diverso per ogni singola 
caratteristica facciale (come invece avviene nei metodi basati sulle caratteristiche 
geometriche). 
L’immagine, rappresentata come array bidimensionale (a valori di intensità), 
viene confrontata, tramite una metrica opportuna, con un singolo template 
(sagoma) che rappresenta l’intera faccia. Al template vengono associate alcune 
maschere a livelli di grigio, relative alle diverse parti del volto (dalle sopracciaglia 
verso il basso). 
 
 
Fig. 2.2 Esempio di Template Matching con quattro maschere 
Capitolo 2. Le tecniche di riconoscimento facciale 
 12
 
Una tecnica che fa uso della strategia Template-Matching è il Correlation Based 
Method. 
Si basa sul calcolo di un coefficiente C
N
 di cross-correlazione normalizzato, 
definito da: 
 
)()(
][][][
TI
TEIETIE
C
T
TT
N
 ς ς
  
   
dove: 
I
T
 è la parte di immagine che deve essere confrontata con la sagoma T 
I
T
T rappresenta il prodotto pixel per pixel 
E è l’operatore di media (expectation) 
 ς è la deviazione standard relativo all’area di confronto. 
In [3] [4] [5], gli autori descrivono un metodo basato sulla correlazione sia per il 
face detection che per il face recognition basato su viste frontali. 
In questi metodi, il primo passo consiste nel localizzare le carattestiche 
significative del volto (come occhi, naso e bocca) ad ognuna delle quali sarà 
associata una sagoma. 
Presa un’immagine di test, ogni sagoma corrispondente ad una caratteristica 
facciale viene confrontata con la corrispondente sagoma di tutte le immagini 
presenti nel database e viene restituito un vettore dei risultati di match (ha tante 
componenti quante sono le caratteristiche facciali) riguardanti l’intero volto. 
Chiaramente il confronto tra due sagome viene effettuato calcolando l’indice di 
cross-correlazione normalizzato. 
I punteggi di similarità di caratteristiche differenti vengono agglomerati per 
ottenere un punteggio globale che verrà usato per il riconoscimento. 
 
 
Capitolo 2. Le tecniche di riconoscimento facciale 
 13
2.1.3.3 Conclusioni 
 
Nei tests eseguiti con gli algoritmi implementati dagli autori sopra menzionati, il 
Template matching si rivela superiore in termini di tasso di riconoscimento e di 
facilità di applicazione. D’altro canto il Feature-based matching offre un 
riconoscimento veloce ed un’occupazione di memoria molto contenuta. 
Il punto critico in entrambi gli approcci è la localizzazione degli occhi e 
l’associata normalizzazione automatica della scala e dell’orientamento 
dell’immagine. Da questo punto di vista si può leggere una presenza 
dell’approccio feature-based nel template matching: la caratteristica “occhi” è 
usata per normalizzare l’immagine e il template matching è eseguito 
separatamente su un set di features distinto (occhi, naso bocca). 
E’ perciò ragionevole concludere che una efficace architettura per il 
riconoscimento di oggetti combini aspetti di entrambe le tecniche. 
 
 
 
2.2   Hidden Markov Model 
 
 
2.2.1 HMM e EHMM 
 
La tecnica dell’”Hidden Markov Model” è nata con l’obiettivo di riconoscere le 
sequenze di proteine nel DNA, ma poi ha fornito ottimi risultati anche per 
problemi di OCR e di riconoscimento vocale. 
I modelli di Markov sono uno strumento statistico in grado di riprodurre 
l’evoluzione di un sistema non deterministico mediante l’uso di stati. 
Le probabilità associate ad ogni transizione tra stati, vengono memorizzate in una 
“matrice di transizione dello stato” A . I valori probabilistici possono essere 
calcolati osservando il comportamento del sistema durante una fase di 
apprendimento (training).