Post on 01-May-2015
Marco CristaniTeoria e Tecniche del Riconoscimento 1
Teoria e Tecniche del Riconoscimento
Metodo di Fisher, Principal Component Analysis
Facoltà di Scienze MM. FF. NN.
Università di Verona
A.A. 2010-11
Marco CristaniTeoria e Tecniche del Riconoscimento 2
• 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).
La trasformata di Fisher
Marco CristaniTeoria e Tecniche del Riconoscimento 3
x
x2
1x
x2
1
Marco CristaniTeoria e Tecniche del Riconoscimento 4
• Si supponga di avere un insieme di N campioni d-dimensionali 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 CristaniTeoria e Tecniche del Riconoscimento 5
• 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:
dove
~
~
m
m
t
t1 1
2 2
w m
w m
m x
m x
11
1
1
22
2
1
11
1
1
22
2
1
1
1
1
1
1
2
1
2
N
N
mN
mN
ii
N
ii
N
ii
N
ii
N
( )
( )
( )
( )
~
~
medie prima della trasformazione
y
y
medie dopo la trasformazione
Marco CristaniTeoria e Tecniche del Riconoscimento 6
• 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:
x
y
1
2
2
22
1
21
~~
~~
ss
mmJ
w
Marco CristaniTeoria e Tecniche del Riconoscimento 7
dove sono le dispersioni (scatter) dei campioni classificati 1 ed 2, rispettivamente, definite come:
• 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:
21~ e ~ ss
~ ~( )s y mi j
i ii
j
N2
2
1
Si ji
i ji
it
j
N i
x m x m( ) ( )
121 SSSw
Marco CristaniTeoria e Tecniche del Riconoscimento 8
• Analogamente:
• In tal modo:
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.
~ ~ ( )s Sii
ij
Nt
ji t
ij
Nt
ij
i i2
2
1
2
1
y m( ) w x w m w w
ww wt Sss 2
22
1~~ ~ ~m m St
B1 22
w w
ww
www
wt
Bt
S
S
ss
mmJ
2
22
1
21
~~
~~
Marco CristaniTeoria e Tecniche del Riconoscimento 9
• Derivando ottengo che:
che è la trasformata di Fisher.
JSww
w m m 0 11 2
10
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
k
kJ1
2)()0()0(0 )( argmin
)0(
xxxx
• Soluzione: il vettore media
M
k
k
M 1
)(1xm
Problema
m poco espressivo!!!
11
PCA
• Supp. una retta di proiezione nello spazio
Alcune vanno bene ... altre no.intuitivamente
• 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)!
12
PCA• Per convenienza, imponiamo passaggio dalla media, e
specifichiamo quindi i punti della retta come
2
1
2
1
2
1
e
ea
m
m
x
x
1x
2x
)(kae
m
emx )()( kk a)(kx
mxe
xeme
)()(
1
2)()(...1
)(1
'...
, argmin...1
)(
kk
M
k
kkMk
k
a
a
aaJMk
k
• Troviamo quindi i coefficienti che minimizzano la distanza quadratica
Mkka ...1
)(
13
PCA• Sostituendo in otteniamo
, ossia mxe )()( ' kka e,...1
)(1 Mk
kaJ
M
k
kJ1
2)(1 mxSee'e
e1J
• Minimizzare significa massimizzare tenuto conto che
, via moltiplicatori di Lagrange; ossia
M
k
kk
1
)()( 'mxmxS
e1J See'1e 1 ee'See' u
022
eSee
u
• Minimizzo;
eSe
Scatter matrix ≈ mat. di covarianza
A conti fatti:1. e deve essere autovettore;2. Poiché
deve essere massimo
ee'See'
14
Esempio
1x
2x
717.0615.0
615.0617.0S
678.0
735.0)1(e
735.0
678.0)2(e
049.0)1( 284.1)2(
• La matrice di covarianza è
• Ottengo 2 autovettori (e autovalori): quale prendo?
15
Esempio - osservazioni
717.0615.0
615.0617.0S• La matrice di covarianza è simmetrica, reale
gli autovettori {e} sono ortogonali, formanti una base per lo spazio N dimensionale
gli autovalori più grandi si hanno nelle direzioni di
massima dispersione dei dati
678.0
735.01e
735.0
678.02e
049.01 284.12
1x
2x
16
Esempio - osservazioni
D
ii
ki
k a1
)()( emx
• I coefficienti , per i =1,...,N, sono le componenti del punto
per la base trovata
• Quindi un punto può essere scritto come
)(kia
)(kx
)(kx
m
)(2ka
)(1
ka
17
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
)1(
)1(2
)1(1
)1(
Nx
x
x
x
)2(
)2(2
)2(1
)2(
Nx
x
x
x
)(
)(2
)(1
)(
MN
M
M
M
x
x
x
x…
N.B.:di solito,M<<N
18
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 sfondoritaglia le facce, catturale su sfondo neutro (alternativa: background subtraction)
– In maniera automatica, utilizzo di un metodo di face detection
)1(
)1(2
)1(1
)1(
Nx
x
x
x
)2(
)2(2
)2(1
)2(
Nx
x
x
x
)(
)(2
)(1
)(
MN
M
M
M
x
x
x
x…
19
Eigenfaces - proiezioni• Dopo aver ricavato gli autovettori {e} (eigenfaces) dalla matrice
di covarianza S, calcolo le componenti {a} (o proiezione) per la faccia x
ed ho
• Le ricostruzioni, g, possono avvenire anche nei sottospazi descritti dalle eigenfaces con eigenvalues più grandi – riduzione dimensionalità
mxemxemxe N',...,',' 21
1a 2a Na
NNaaa eeemx ,...,2211
8877665544332211 eeeeeeee aaaaaaaa … NNa exxg
m +x
10 20 30 50 70 82n.
coeff.
20
Eigenfaces• Autovettori {e} (eigenfaces): in pratica?
1e 2e 3e
...
21
Eigenfaces - problema
• Sia pertanto S = AA’
• Con un’img 256 x 256 ho : problemi di overflow!
• Trick: calcolo gli autovettori di , ossia , tenuto conto
che di solito si usano 20-30 eigenfaces e che
)()2()1(
)(2
)2(2
)1(2
)(1
)2(1
)1(1
...
...
...
MNNN
M
M
xxx
xxx
xxx
A
N x M N x N
65536 65536S
MM 'AA e~
eAeSA
eAeAAAeeAA~ ~
~ ~'~ ~'
eAe ~ quindi
22
Eigenfaces - note
• Gli M autovalori di A’A corrispondono agli M autovalori più grandi di S (così come i corrispondenti autovettori)
23
Eigenfaces - algoritmo
1. Sottraggo ad ogni immagine x(k) ,k=1...M, la media
ottenendo i vettori da cui costruisco la matrice
2. Calcolo M autovettori di formando la matrice
3. Ricavo gli M autovettori più grandi di S = AA’, ossia
o in forma matriciale
4. Ricavo i corrispondenti componenti (o coeff. di proiezione)
o in forma matriciale
MN A
MM 'AA Mii ,...,1
ˆe
ii eAe ˆ
)()( ~' ki
kia xe
M
k
k
M 1
)(1xm
)(~ kx
MM V
MMMNMN VAU
)(
1
)(
1
~' k
NNM
k
M xUω
24
Proprietà chiave della rappresentazione ad eigenfaces
Date
• 2 immagini usate per costruire l’eigenspace
• è la proiezione nell’eigenspace dell’img
• è la proiezione nell’eigenspace dell’img
allora,
ossia, la distanza nell’eigenspace è approssimativamente uguale alla distanza tra due immagini.
21, xx
1ω
|||||||| 1212 xxωω
1x
2x2ω
25
Riconoscimento con le eigenfaces1. Analizza il database d’immagini etichettato (<volti,identità>)
a) Esegui PCA — calcola le eigenfaces, formo Ub) Calcola i K coefficienti per ogni immagine x(k) k=1,...,Mc) Calcola le M proiezioni nello spazio delle eigenfaces ω(k) k=1,...,Md) Calcolo la soglia
2. Data una nuova img (da riconoscere) x, a) Ne sottraggo la media del dataset di training m, ottengob) Proietto, ossia calcolo le K componenti
c) Calcolo il set di distanze
Mkjkj ,...,1,per max )()( ωω
TRAINING
',...,,~21 Kaaa ωx
Mkkk ,...,1per 2)(2)( ωω
xU'ω ~
x~
ossia
RICONOSCIMENTO
26
Riconoscimento con le eigenfaces3. Ricostruisco la faccia usando eigenfaces e componenti
4. Calcolo la distanza tra la faccia di partenza incognita e la ricostruzione
5. Se• non è una faccia
• è una nuova faccia
• è una faccia conosciuta, la kbest-esima, dove
~ oppure ~1
Uωgeg
K
iiia
RICONOSCIMENTO
~~ 22 xg
M1,...,k , e )(k
)(min e k
)(best argmin k
kk
27
Dettagli pratici
K Mi =
• Quanti eigenvector usare?• Controlla il decadimento degli
eigenvalues• 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
N
jj
K
i i
1
1covered
28
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
29
Problemi eigenfaces (2)
• Funzionale solo per la rappresentazione di dati appartenenti ad un’unica classe
• Non separano classi differenti