Marco Cristani Teoria e Tecniche del Riconoscimento1 Metodo di Fisher, Principal Component Analysis...

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


• 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


x

x2

1x

x2

1


• 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.


• 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


• 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


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


• 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

~~

~~


• 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

Marco Cristani Teoria e Tecniche del Riconoscimento1 Metodo di Fisher, Principal Component Analysis...

Documents

Transcript of Marco Cristani Teoria e Tecniche del Riconoscimento1 Metodo di Fisher, Principal Component Analysis...