1

Sistemi avanzati per il riconoscimento

Dr. Marco Cristanie-mail: marco.cristani@univr.itufficio: Stanza 47, Ca Vignal 2

Università di VeronaFacoltà di Scienze MM.FF.NN.

Lezione 6 – Tracking e analisi di traiettorie

2

Obiettivi - Tracking• Definizioni equivalenti

– Capire come si spostano gli oggetti in una sequenza– Inseguire gli oggetti distinti nella scena durante il loro

movimento, stimandone la traiettoria• nel 3D della scena• nel piano immagine

• Opzioni per la telecamera:– statica-mobile– unica-multipla

3

Passi fondamentali• Inizializzazione, cattura nuovi soggetti

entranti nella scena• Inseguimento

– insegue gli oggetti nella scenamantenendone l’identità• metodologia “forza bruta”

– correlazione– correlazione + vincoli

• metodologia classica1. predizione2. verifica, associazione

4

Inizializzazione• Trovare un oggetto da seguire• Metodologie

– Template matching• Output di un classificatore

– Face detector, hand detector, altro

• Cross-correlazione normalizzata

– Sottrazione del background– Metodi ibridi

5

Inseguimento – metodo forza bruta

• Due immagini: Zt e Zt-1

• Associa ad ogni oggetto Oi,t-1 ilcorrispondente Oi,t dove i=1,...,K

t-1 t

come scegliere le associazioni??

6

Correlazioni• Soluzioni: 1. esaustivamente (lento, impreciso)2. con vincoli

– definire/stimare le caratteristiche degli oggetti• visuali• spaziali• di moto

– velocità (intensità, direzione), accelerazione

– predirre la posizione di un oggetto al passo t– pesare la correlazione

7

Condensation• Particle filtering

– Metodi di Montecarlo

• Condensation classico• Bramble: Condensation multi-oggetto

Visual Motion Analysis by Probabilistic Propagation of Conditional Density, Michael Isard, D.Phil. Thesis, Oxford University, 1998

8

Particle filtering - Assunzioni• Assumiamo che

– lo stato del sistema che stiamo osservando al tempo t sia definito da• xt

– La posizione di un singolo oggetto puntiforme

• Xt = {x1,t, x2,t,…, xM,t}– La forma di un oggetto, definita da M punti definiti sulla sua

silhouette– M oggetti puntiformi

– la storia (discreta!!!) del sistema fino al tempo t sia Xt = {X1, X2,…, Xt}

9

Particle filtering - Assunzioni– lo stato del sistema fino al tempo t sia osservabile

da un set di osservazioni Zt = {Z1, Z2,…, Zt}

• La presenza di una storia indica un’evoluzione del sistema nel tempo

• Assumiamo l’evoluzione del sistema come– un processo stocastico– Markoviano tempo-indipendente di ordine 1

P(Xt|Xt)=P(Xt|Xt-1)• Esempio 1D

P(xt|xt-1)= ( )21 121exp −−− −tt xx

10

Particle filtering - Assunzioni– lo stato del sistema fino al tempo t sia osservabile

da un set di osservazioni Zt = {Z1, Z2,…, Zt}, le quali• non modificano lo stato del sistema

• sono indipendenti

11

Particle filtering - Obiettivi• stimare lo stato

– più probabile– atteso

del sistema Xt date tutte le osservazioni Zt

• per fare questo, è necessario valutare la distribuzione su tale probabilità, ossia recuperare p(Xt|Zt)

• Eseguendo questo controllo ad ogni istante t, ciò corrisponde a valutare l’evoluzione di una distribuzione nel tempo

12

Particle filtering - Obiettivi• Tramite la regola sulla legge condizionale

(provate con t=3)

dove

13

Algoritmo di Condensation• Assumo uno campo di esistenza R dello stato del

sistema – 1D – finito

• Il sistema è una particella puntiforme su R• Ho un set di campioni n=1,…,N che

rappresentano possibili stati del mio sistema (quindi posizioni in R) al tempo t-1

{ })(1

nts −

State x

14

Algoritmo di Condensation -Inizializzazione

• Ogni campione rappresenta un intorno spaziale locale

• Per modellare il fatto che in alcuni punti ho maggiore probabilità di avere il mio sistema, peso le particelle 1-1 con un set di pesi n=1,…,N

{ })(1

nt−π

15

Algoritmo di Condensation -Inizializzazione

• A questo punto posso stimare una densità su tutto R

16

Tracking via Condensation• Supponendo di partire da questa conoscenza,

il particle filtering fa evolvere il set di particelle• 3 passi:

1. Selezione o campionamento• campiono (estraggo) N campioni da • il campione viene selezionato con probabilità

{ })(1

nts −

)(1

nts −

)(1

nt−π

17

11 1 12p( | , ) ( 0 8 ). ,t tt tt xx x xG xx σ− −− − = +& &

Tracking via Condensation (2)2. Applicazione della dinamica – per tutte

le particelle• Applico alla particella un moto composto da

due componenti:– Deterministica (deterministic drift)

• Basato sulla storia della particella da cui è stata estratta

• Basata su un’unica dinamica pesata su tutte le particelle (vedi seguito)

– Probabilistica (diffuse) aggiungo del rumore per modellare l’incertezza sul moto

)(nts

)(nts

),0( 2dσΝ

Ν

)~(1

nts −

ESEMPIO:

18

Tracking via Condensation (3)

•In tal maniera ottengo la parte predittiva (= a priori) della formulazione Bayesiana del filtro

19

Tracking via Condensation (4)3. Valutazione/pesatura

• Calcolo la likelihood di ogni nuovo campione basandomi sulle osservazioni

• Le osservazioni rappresentano la possibilità di osservare localmente la realtà della scena

• Nel caso di moto monodimensionale, le osservazioni sono la possibilità di osservare l’intorno

( ) [ ] ℜ∈+−= h ,, )()()( hshssI nt

nt

nt

20

Tracking via Condensation(5)• Formalmente, si calcola • Nel caso 1D, si puo’ utilizzare una funzione di lik.

Gaussiana

)|( )()( nt

nt szp

),|()|( 2)()()()(w

nt

nt

nt

nt szszp σμ ==N

21

Tracking via Condensation (6)• Attenzione:

altrimenti si perde l’obiettivo.• La likelihood ottenuta serve per la creazione dei

nuovi pesi associati alle particelle, ossia

• In questo modo, prese tutte le particelle, si realizza la parte di likelihood del filtro bayesiano

22dw σσ >

)(ntπ )|( )()( n

tn

t szp= (+ normalizzazione)

22

Tracking via Condensation - definizione dell’obiettivo

• Decisione fondamentale: dove si trova l’oggetto all’istante t?

– Due soluzioni (generali nel caso multi-dim.):• Media pesata

• Maximum A Posteriori (MAP)

( )[ ] ⎟⎟⎠

⎞⎜⎜⎝

⎛= )|(maxarg )()(

)(

nt

nt

st xspffM

nt

X

con

23

Riassunto grafico

24

Dimostrazione

)|p( 1:11 −− tt ZX

)|p( :1tt ZX

)|p( :1tt ZX

)|p( 1:1 −tt ZX

)|p( 1−tt xx)|p( tt XZ

)|p( :11 tt ZX +

)|p( 11 ++ tt XZ)|p( 1 tt XX +

25

Richiamo al Kalman Filter

Kalman Condensation

26

Dettagli: come campionare?• Metodo della funzione di ripartizione

– Prendo tutti i pesi dei campioni

– Ne faccio la somma cumulativa, ottenendo i coeff.

{ })(ntπ

{ })(ntc

)1(tc )2(

tc )(Ntc

27

Dettagli: come campionare?– Ossia

– Dopodiché (in modo efficiente – O(NlogN))

28

Stato del sistema:• Non esclusivamente una posizione 1D:

– Posizione multidimensionale– Setdi coefficienti di B-spline, per modellare una

forma

29

Note – multi-object tracking– Cosa accade nel caso in cui ci siano piu’ di un

oggetto da inseguire?

30

Note – multi-object tracking– L’algoritmo tende effettivamente a seguire un solo

oggetto.

31

Importanza della dinamica• Una dinamica errata porta a perdere l’oggetto

• Soluzione: si stima la dinamica in modo robusto, off-line– manualmente, via correlazione esaustiva su tutto il piano immagine

32

Condensation multi oggetto -Bramble

• Bayesian Multiple-BLob (BraMBLe) tracker èl’evoluzione di Condensation.

• Al solito, stima

),...,,|p( 11 ZZZX −ttt

Stato all’istante t Sequenza di immaginiNumero,Posizioni,Forme,Velocità,…

BraMBLe: a Bayesian multiple-blob tracker, M Isard, J Maccormick. ICCV 2001. Proceedings. Eighth IEEE InternationalConference on, Vol. 2 (2001), pp. 34-41 vol.2.

33

Bramble - ingredienti• Stato del sistema X

( )mttt m xxX ...,,, 1=

Numero di oggettiStato

dell’oggetto1tx

2tx

3tx

3=m

34

Bramble - ingredienti

( )svlx ,,,i=Identità

LocazioneVelocità

Appearance

Stato dell’oggetto

• Gestione delle occlusioni (grazie al 3D) ( )svlx ,,,1 i= ( )svlx ,,,2 i=

35

Bramble - ingredienti• Lo stato del sistema si approssima con un set di

N particelle-configurazioni

...N particelle:

N Weights: 1tπ

2tπ

1Ntπ− N

tπ

{ })()( , nt

ntt πSX ≈

)1(tS )2(

tS )( NtS

36

Bramble - ingredienti• Osservazioni Z

– sottocampione la matrice video in un set di G filtri zgcon una granularità spaziale sufficiente a potervalutare tutti i filtri in tempo reale

– Ogni filtro corrisponde ad una determinata posizione3D

37

Bramble - fasi1. Selezione o campionamento : la stessa di

Condensation: si estraggono configurazioni grazie aipesi. In più

– Ogni oggetto ha una probabilità variabile (in funzione della posizione) e costante rispetto al tempo di uscire dalla scena,

– Esiste una probabilità variabile (in funzione dellaposizione) e costante rispetto al tempo di entrarenella scena

alta probabilità

)(loutτ

)(linτ

38

Bramble - fasi2. Applicazione della dinamica: simile a

Condensation – la dinamica di ogni oggetto di ogniconfigurazione è determinata in base

1. alla sua etichetta2. alla storia precedente (media pesata di tutte le particelle) di

quella etichetta

39

Bramble - fasi• Valutazione/pesatura

– La valutazione di una configurazione avviene controllandosequenzialmente i filtri, assunti indipendenti tra loro

la produttoria si cambia in sommatoria logaritmica per stabilitànumerica

– la valutazione tiene presente della posizione

( ).|p)|p( )()( ∏= gn

gn SzSZ

( )svlx ,,,1 i= ( )svlx ,,,2 i=

40

Bramble - fasi• Dopo l’osservazione

=)(ntπ ( ).|p)|p( )()( ∏= g

ng

n SzSZ(+ normalizzazione)

Risultati

41

Analisi di traiettorie

• Una volta eseguito il tracking, ricaviamo un set ditraiettorie etichettate {O}

• O può essere di varia natura– solo posizioni nel tempo (e quindi velocità orientate)– caratteristiche ereditate dal tracking– caratteristiche stimate tramite post processing sulle traiettorie

• accelerazione• curvatura locale

• Le traiettorie possono essere modellate come punti in unospazio multidimensionale– perdita di informazione

42

Hidden Markov Model (HMM) • Modelli generativi statistici [Rabiner89,

Eickeler98]• Possono essere visti come modelli

Markoviani in cui l’informazione sullo statocorrente non è deterministica, ma affettada incertezza, deducibile attraverso unaserie di simboli d’osservazione.

• Ogni stato ha associata una funzione didensità di emissione che descrive la probabilità che un certo simbolo sia statoemesso da uno stato determinato

? ? ?

Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.

43

Hidden Markov Model (HMM): notazione• Un HMM è definito da:

– Un set S={S1,S2,…,SN} di stati nascosti;

– Una distribuzione di probabilità di transizione A={aij}, cherappresenta la probabilità tempo-invariante di andaredallo stato Si to Sj

– Un set V={v1,v2,…,vM} di simboli d’osservazione;

– Una distribuzione di probabilità di emissione B={bjk}, cheindica la probabilità di emissione di un simbolo vk quantolo stato nascosto è Sj.

– An distribuzione di probabilità iniziale π ={πi}, cherappresenta la probabilità di avere un determinato statoiniziale

• Denotiamo un HMM come una triplettta λ=(A, B, π)

Ot

St

44

Applicazioni su HMM1. LIKELIHOOD: Data una stringa d’osservazione O, calcolare la

likelihood P(O| λ).

2. VITERBI: Data una stringa d’osservazione O e un modello λ, calcola la sequenza di stati più probabile S1…Sn che ha generato la sequenza O.

3. TRAINING: Data un set di osservazioni{Ol}, determinare il migliormodello λ, i.e. il modello per cui P(O| λ) è massimizzata

V1

Diapositiva 44

V1 Viterbi?Vittorio; 12/02/2007

45

Classificazione con HMM• Data una sequenza sconosciuta O

– calcola, per ogni modello λi, P(O| λi) – classifica O come appartenente alla classe per

cui il modello mostra la più alta probabilitàP(O| λi)

46

Esempio – forme/traiettorie chiuse

47

I modelliShape Emission Probability Transition Probability

0.94 0.00 0.06 0.00 0.00 0.96 0.00 0.04 0.02 0.00 0.96 0.02 0.00 0.02 0.02 0.96

0.98 0.01 0.010.03 0.97 0.000.02 0.00 0.98

48

I modelli (2)Shape Emission Probability Transition Probability

0.92 0.00 0.00 0.08 0.000.00 0.97 0.01 0.02 0.000.00 0.00 0.89 0.04 0.070.09 0.11 0.00 0.80 0.000.00 0.00 0.09 0.00 0.91

0.91 0.00 0.00 0.090.00 0.95 0.05 0.000.00 0.06 0.92 0.020.08 0.00 0.08 0.83

49

Invarianze

• Usando una descrizione basata sucurvatura, si ottiene invarianza rispettoalla rotazione

•