Marco Cristani Teorie e Tecniche del Riconoscimento1 Teoria e Tecniche del Riconoscimento Estrazione...

Marco CristaniTeorie e Tecniche del Riconoscimento 1

Teoria e Tecniche del Riconoscimento

Estrazione delle feature: Principal Component Analysis, Eigenfaces

Facoltà di Scienze MM. FF. NN.

Università di Verona

A.A. 2013-14

2

Principal Component Analysis• 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!!!

Teorie e Tecniche del Riconoscimento

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


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

)(

kTk

M

k

kkMk

k

a

a

aaJMk

k

• Troviamo quindi i coefficienti che minimizzano la distanza quadratica

Mkka ...1

)(


5

PCA• Sostituendo in otteniamo

, ossia mxe )()( kTka e,...1

)(1 Mk

kaJ

M

k

kTJ1

2)(1 mxSeee

e1J

• Minimizzare significa massimizzare tenuto conto che

, via moltiplicatori di Lagrange; ossia

M

k

kk

1

)()( 'mxmxS

e1J SeeT

1e 1 eeSee TTu

022

eSee

u

• Minimizzo;

eSe

Scatter matrix ≈ mat. di covarianza

A conti fatti:1. e deve essere autovettore;2. Poiché

deve essere massimo

eeSee TT


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?


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


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


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


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…


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.


12

Eigenfaces• Autovettori {e} (eigenfaces): in pratica?

1e 2e 3e

...


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


14

Eigenfaces - note

• Gli M autovalori di A’A corrispondono agli M autovalori più grandi di S (così come i corrispondenti autovettori)


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ω


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ω


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


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


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


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


21

Problemi eigenfaces (2)

• Funzionale solo per la rappresentazione di dati appartenenti ad un’unica classe

• Non separano classi differenti


Marco Cristani Teorie e Tecniche del Riconoscimento1 Teoria e Tecniche del Riconoscimento Estrazione...

Documents

Transcript of Marco Cristani Teorie e Tecniche del Riconoscimento1 Teoria e Tecniche del Riconoscimento Estrazione...