Teoria e Tecniche del Riconoscimento
-
Upload
thaddeus-farrell -
Category
Documents
-
view
37 -
download
3
description
Transcript of Teoria e Tecniche del Riconoscimento
![Page 1: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/1.jpg)
Marco CristaniTeoria e Tecniche del Riconoscimento 1
Teoria e Tecniche del Riconoscimento
Principal Component Analysis,Metodo di Fisher
Facoltà di Scienze MM. FF. NN.
Università di Verona
A.A. 2012-13
![Page 2: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/2.jpg)
2
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!!!
![Page 3: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/3.jpg)
3
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)!
![Page 4: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/4.jpg)
4
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
)(
![Page 5: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/5.jpg)
5
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'
![Page 6: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/6.jpg)
6
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?
![Page 7: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/7.jpg)
7
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
![Page 8: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/8.jpg)
8
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
)(1ka
)(2ka
![Page 9: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/9.jpg)
9
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
![Page 10: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/10.jpg)
10
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…
![Page 11: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/11.jpg)
11
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.
![Page 12: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/12.jpg)
12
Eigenfaces• Autovettori {e} (eigenfaces): in pratica?
1e 2e 3e
...
![Page 13: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/13.jpg)
13
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
![Page 14: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/14.jpg)
14
Eigenfaces - note
• Gli M autovalori di A’A corrispondono agli M autovalori più grandi di S (così come i corrispondenti autovettori)
![Page 15: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/15.jpg)
15
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ω
![Page 16: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/16.jpg)
16
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ω
![Page 17: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/17.jpg)
17
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
![Page 18: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/18.jpg)
18
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
![Page 19: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/19.jpg)
19
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
![Page 20: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/20.jpg)
20
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
![Page 21: Teoria e Tecniche del Riconoscimento](https://reader030.fdocumenti.com/reader030/viewer/2022032709/5681315b550346895d97d0e5/html5/thumbnails/21.jpg)
21
Problemi eigenfaces (2)
• Funzionale solo per la rappresentazione di dati appartenenti ad un’unica classe
• Non separano classi differenti