Facoltà di Scienze MM. FF. NN.
Università di Verona
A.A. 2010-11
Teoria e Tecniche del Riconoscimento
Metodo di Fisher,
Principal Component Analysis
Marco Cristani
Teoria e Tecniche del Riconoscimento
1
La trasformata di Fisher
• Il problema è quello di ridurre la dimensionalità dello
spazio delle features in modo da rendere il problema di
classificazione computazionalmente trattabile.
• È in sostanza la proiezione delle feature caratterizzanti un
campione su una retta, cioè su una direzione (da un
problema d-dimensionale ad un problema 1-dimensionale).
Marco Cristani
Teoria e Tecniche del Riconoscimento
2
x2
x2
x
1
x
1
Marco Cristani
Teoria e Tecniche del Riconoscimento
3
• Si supponga di avere un insieme di N campioni ddimensionali x1, .., xN, di cui N1 classificati come 1 ed N2
classificati come 2.
• Si vuole cercare una trasformazione w, ossia una
combinazione lineare delle componenti di x tale da
generare i corrispondenti campioni (scalari) y1,..., yN:
wt x = y
• Geometricamente, se la norma di w è pari a 1 allora ogni yi
è la proiezione del campione xi sulla retta di direzione w.
Marco Cristani
Teoria e Tecniche del Riconoscimento
4
• Siccome si vuole separare le due classi anche nel nuovo spazio
monodimensionale allora si considera come misura di
separazione la differenza delle medie dei campioni. Quindi:
~  wt  m
m
1
1
~  wt  m
m
2
2
dove
1 N1 (1) 
m1 
  xi 
N 1 i 1

 medie prima della trasformazione
N
2 ( 2) 
1
m2 
  xi 
N 2 i 1

N1
1
(1) 
~
m1 
  yi 
N 1 i 1

 medie dopo la trasformazione
N
2 ( 2) 
1
~
m2 
  yi 
N 2 i 1

Marco Cristani
Teoria e Tecniche del Riconoscimento
5
y
1
2

x
• Si vuole ottenere che la differenza tra le medie delle due
classi (trasformate) sia grande rispetto alla deviazione
standard di ogni classe.
• Allora, si definisce il discriminante lineare di Fisher come
la funzione lineare wtx per la quale la funzione J è massima:
~ m
~
m
1
J w   ~ 2 ~ 22
s s
Marco Cristani
1
2
Teoria e Tecniche del Riconoscimento
6
dove ~
s1 e ~
s2 sono le dispersioni (scatter) dei campioni
classificati 1 ed 2, rispettivamente, definite come:
Ni
 (i ) ~ 
~

s2   y m
i


i
j
j 1
2
• Si vuole che le dispersioni siano abbastanza piccole, ossia,
che i campioni di una classe siano abbastanza concentrati
intorno al valore medio.
• Per ottenere J come una funzione esplicita di w si
definiscono le matrici di dispersione (scatter matrices) Si
ed Sw:
Ni
Si  
j 1



t
(i )
(i )
x j  mi x j  mi
S w  S1  S 2
Marco Cristani
Teoria e Tecniche del Riconoscimento
7
• Analogamente:
~
si 2 
Ni
2
Ni


2
 (i ) ~ 
t (i )
t
  y j  mi    w x j  w mi  w t Si w
j 1
j 1
• In tal modo:
~
s12  ~
s22  w t S w w
2
~
~
m1  m2   w t S B w
dove
SB = (m1 - m2)  (m1 - m2)t
• Quindi per ottenere J(w) massimo, si deve esplicitare J
in funzione diretta di w e quindi derivarlo rispetto a w
ed eguagliare a 0.
~ ~
t
m1  m2 w S B w
J w   ~ 2 ~ 2  t
s1  s2
w S ww
Marco Cristani
Teoria e Tecniche del Riconoscimento
8
• Derivando ottengo che:
J
 0  w  S w1  m1  m 2 
w
che è la trasformata di Fisher.
Marco Cristani
Teoria e Tecniche del Riconoscimento
9
PCA
• Il dato = un vettore
N-dimensionale di
valori di pixel
• Supponiamo N=2 
dati = punti 2D
Come posso
descrivere in modo
compatto questi M
punti?
• SOL 1: Con un punto (vettore) solo, che
minimizzi la distanza media quadratica con tutti
i pti
M
argmin J 0 (x )   x
(0)
x
(0)
(0)
x
(k ) 2
k 1
• Soluzione: il vettore media
1
m
M
M
(k )
x

k 1
10
PCA
• SOL2: Con una retta di proiezione, che minimizzi la distanza media
quadratica con tutti i pti
• In questo caso useremmo una dimensione per descrivere i dati (la
posizione sulla retta)!
Alcune vanno bene
...
altre no.
• Supp. una retta di
intuitivamente
proiezione nello
spazio
11
PCA
• Per convenienza, imponiamo passaggio dalla media, e specifichiamo
quindi i punti della retta come
x
(k )
x (k )
ma e
(k )
a (k )
 x1   m1 
 e1 
 x   m   a e 
 2  2
 2
x2
e
m
x1
• Troviamo quindi i coefficienti a ( k ) k 1... M che minimizzano la distanza
quadratica
 
argmin J1 a
a 
(k )
k 1...M
(k )

k 1... M

M


,e   m  a e  x
...  a ( k )  e' x ( k )  m

(k )
(k ) 2
k 1
12


PCA
 
• Sostituendo a ( k )  e' x ( k )  m in J1 a ( k )
J1 e , ossia
k 1... M

, e otteniamo
Scatter matrix ≈ mat. di covarianza
M
J1 e   e'Se   x
(k )
m
2
S   x ( k )  m x ( k )  m '
M
k 1
k 1
• Minimizzare J1 e  significa massimizzare e'Se tenuto conto che
e  1 , via moltiplicatori di Lagrange; ossia
u  e'Se   e'e 1
A conti fatti:
1. e deve essere autovettore;
2. Poiché
• Minimizzo;
u
 2Se  2e  0
e
Se  e
e'Se  e'e  

deve essere massimo
13
Esempio
• La matrice di covarianza è
0.617 0.615
S

0
.
615
0
.
717


• Ottengo 2 autovettori (e autovalori): quale prendo?
 0.678
 0.735
x2
e( 2)  
e (1)  


 0.735 
 0.678 
( 2)  1.284
  0.049
(1)
x1
14
Esempio - osservazioni
0.617 0.615
• La matrice di covarianza S  
è simmetrica, reale

0.615 0.717
 gli autovettori {e} sono ortogonali, formanti una base per lo spazio N
dimensionale
 0.735
e1  

0
.
678


1  0.049
 0.678
e2  

0
.
735


2  1.284
 gli autovalori più grandi si
hanno nelle direzioni di
massima dispersione dei dati
x2
x1
15
Esempio - osservazioni
• I coefficienti
ai( k ,) per i =1,...,N, sono le componenti del punto
x (k )per la base trovata
a
(k )
2
x (k )
a1( k )
m
D
• Quindi un punto può essere scritto come
x ( k )  m   ai( k )ei
i 1
16
Da PCA ad eigenfaces
• Dato un gruppo di punti, ho trovato la base che descrive lo scattering
dei punti
• Ogni punto puo’ essere mappato tramite i componenti della base
(numero componenti = numero dimensioni N)
• Usare meno componenti (le componenti principali) permette di
proiettare i punti in un sottospazio altamente informativo  riduzione
della dimensionalità dei punti
• Ora passiamo alle facce (...punti!)dataset di M facce, N dimensioni
x
(1)
 x1(1) 
 (1) 
x
 2 
  
 (1) 
 xN 
x
( 2)
 x1( 2 ) 
 ( 2) 
x
 2 
  
 ( 2) 
 x N 
…
x
(M )
 x1( M ) 
 (M ) 
x
 2 
  
 (M ) 
 xN 
N.B.:
di solito,
M<<N
17
Da PCA ad eigenfaces (2)
• Preprocessing – Le immagini devono contenere esclusivamente facce (no outliers)
– Le immagini devono essere ragionevolmente prive di rumore
– Le facce devono avere la stessa dimensione riscalamento
– Stesse condizioni di illuminazione, o compensazione
– Non ci deve essere sfondoritaglia le facce, catturale su sfondo neutro
(alternativa: background subtraction)
– In maniera automatica, utilizzo di un metodo di face detection
x (1)
 x1(1) 
 (1) 
x
 2 
  
 (1) 
 xN 
x ( 2)
 x1( 2 ) 
 ( 2) 
x
 2 
  
 ( 2) 
 x N 
…
x( M )
 x1( M ) 
 (M ) 
x
 2 
  
 (M ) 
 xN 
18
Eigenfaces - proiezioni
• Dopo aver ricavato gli autovettori {e} (eigenfaces) dalla matrice di
covarianza S, calcolo le componenti {a} (o proiezione) per la faccia x
e'1 x  m, e'2 x  m,..., e' N x  m ed ho
a1
x  m  a1e1  a2e 2 ,...,aN e N
aN
a2
• Le ricostruzioni, g, possono avvenire anche nei sottospazi descritti dalle
eigenfaces con eigenvalues più grandi – riduzione dimensionalità
x
m + a1e1  a2e 2  a3e3  a4e 4  a5e5  a6e6  a7e7  a8e8
n.
coeff. 10
20
30
50
70
gx
… aN e N
82
19
x
Eigenfaces
• Autovettori {e} (eigenfaces): in pratica?
e1
e2
e3
...
20
Eigenfaces - problema
 x1(1)
 (1)
x
• Sia A   2
NxM  
 (1)
 xN
x1( 2)
x2( 2)

xN( 2)
... x1( M ) 
(M ) 
... x2 
pertanto S = AA’

 
NxN
(M ) 
... xN 
• Con un’img 256 x 256 ho
S
: problemi di overflow!
65536 65536
• Trick: calcolo gli autovettori di
A' A , ossia ~
e , tenuto conto
M M
che di solito si usano 20-30 eigenfaces e che
A' A~
e  ~
e  AA ' A ~
e  A ~
e
 SA ~
e  A ~
e
quindi
e  A~
e
21
Eigenfaces - note
•
Gli M autovalori di A’A corrispondono agli M autovalori più grandi di S
(così come i corrispondenti autovettori)
22
Eigenfaces - algoritmo
1.
1
Sottraggo ad ogni immagine x(k) ,k=1...M, la media m 
M
(k )
~
A
ottenendo i vettori x
da cui costruisco la matrice
 
eˆ i i 1,..., M
Calcolo M autovettori
3.
Ricavo gli M autovettori più grandi di S = AA’, ossia e i 
4.
x
(k )
k 1
NM
2.
o in forma matriciale
M
di A' A
M M
formando la matrice
Aeˆ i
V
M M
U  A V
N M
N M M M
Ricavo i corrispondenti componenti (o coeff. di proiezione)
o in forma matriciale
 
ai( k )  e'i ~
x (k )
ω
(k )
M 1
 
(k )
 U' ~
x
M N
N 1
23
Proprietà chiave della rappresentazione ad
eigenfaces
Date
x1 , x 2 usate per costruire l’eigenspace
x1
ω1è la proiezione nell’eigenspace dell’img
ω 2è la proiezione nell’eigenspace dell’img
x2
• 2 immagini
•
•
allora,
|| ω2  ω1 ||  || x2  x1 ||
ossia, la distanza nell’eigenspace è approssimativamente
uguale alla distanza tra due immagini.
24
Riconoscimento con le eigenfaces
1.
Analizza il database d’immagini etichettato (<volti,identità>)
TRAINING
a)
b)
c)
d)
Esegui PCA — calcola le eigenfaces, formo U
Calcola i K coefficienti per ogni immagine x(k) k=1,...,M
Calcola le M proiezioni nello spazio delle eigenfaces ω(k) k=1,...,M
Calcolo la soglia

per j, k  1,..., M
RICONOSCIMENTO
  max ω ( j )  ω ( k )
2.
Data una nuova img (da riconoscere) x,
a)
b)
c)
Ne sottraggo la media del dataset di training m, ottengo
Proietto, ossia calcolo le K componenti
~
x  ω  a1 , a2 ,..., aK '
ossia
~
x
ω  U' ~
x
Calcolo il set di distanze
 
(k ) 2
 ω  ω( k )
2
per k  1,..., M
25
RICONOSCIMENTO
Riconoscimento con le eigenfaces
3.
Ricostruisco la faccia usando eigenfaces e componenti
K
~
g   ai ei oppure ~
g  Uω
i 1
4.
Calcolo la distanza tra la faccia di partenza incognita e la ricostruzione
  ~
g~
x
2
5.
Se
•
 
2
non è una faccia
•
  e  (k )   , k  1,..., M  è una nuova faccia
•
  e min  ( k )  
 
è una faccia conosciuta, la kbest-esima, dove
 
k best  argmin  ( k )
k
26
Dettagli pratici
• Quanti eigenvector usare?
• Controlla il decadimento degli
eigenvalues i 
• Dati “buoni” ossia trattabili hanno
poche dimensioni ad alta varianza
• Nel caso in cui tutti gli N autovalori
sono stati calcolati per un dataset
N-dimensionale vale
i=
K
M
 

K
 covered 
i 1
i
N
j 1
j
27
Problemi eigenfaces
•
Illuminazione: stessi soggetti con
differente illuminazione risultano lontani
nello spazio delle eigenfaces
Pose differenti :le componenti di un
volto frontale non servono per un
riconoscimento con profili
Allineamento differente
Espressione facciale differente
Outlier
•
•
•
•
–
–
Sample outliers = non facce
Intra-sample outliers = facce affette da
rumore
28
Problemi eigenfaces (2)
•
•
Funzionale solo per la rappresentazione di dati appartenenti ad
un’unica classe
Non separano classi differenti
29