Facoltà di Scienze MM. FF. NN.
Università di Verona
A.A. 2011-12
Teoria e Tecniche del Riconoscimento
Principal Component Analysis,
Metodo di Fisher
Marco Cristani
Teoria e Tecniche del Riconoscimento
1
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
2
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
3
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
4


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
5
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
6
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
7
Esempio - osservazioni
• I coefficienti
ai( k ,) per i =1,...,N, sono le componenti del punto
x (k )per la base trovata
(k )
1
a
x (k )
a2( k )
m
D
• Quindi un punto può essere scritto come
x ( k )  m   ai( k )ei
i 1
8
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
9
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 
10
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
11
x
Eigenfaces
• Autovettori {e} (eigenfaces): in pratica?
e1
e2
e3
...
12
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
13
Eigenfaces - note
•
Gli M autovalori di A’A corrispondono agli M autovalori più grandi di S
(così come i corrispondenti autovettori)
14
Eigenfaces - algoritmo
1.
2.
3.
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
 
Calcolo M autovettori ~
ei i 1,..., M di A' A
M M
4.
x
(k )
k 1
NM
formando la matrice
Ricavo gli M autovettori più grandi di S = AA’, ossia e i 
o in forma matriciale
M
A~
ei
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
15
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.
16
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
17
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
18
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
19
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
20
Problemi eigenfaces (2)
•
•
Funzionale solo per la rappresentazione di dati appartenenti ad
un’unica classe
Non separano classi differenti
21