Complementi di Interazione...

1

Complementi di Interazione Uomo-Macchina

Dr. Marco Cristani

e-mail: [email protected]

ufficio: Stanza 47, Ca Vignal 2

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

Corso di Laurea Specialistica in Sistemi Intelligenti e Multimediali

Lezione 4 – 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 loromovimento, stimandone la traiettoria

• nel 3D della scena

• nel piano immagine

• Opzioni per la telecamera:– statica-mobile

– unica-multipla

3

Passi fondamentali

• Inizializzazione, cattura nuovi soggettientranti nella scena

• Inseguimento– insegue gli oggetti nella scena

mantenendone l’identità• metodologia “forza bruta”

– correlazione

– correlazione + vincoli

• metodologia classica1. predizione

2. 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 XXXXt = {X1, X2,…, Xt}

9

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

da un set di osservazioni ZZZZt = {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|XXXXt)=P(Xt|Xt-1)

• Esempio 1D

P(xt|xt-1)= ( )2

1 12

1exp −−− −tt xx

10

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

da un set di osservazioni ZZZZt = {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 ZZZZt

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

• 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

n

ts −

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

n

t−π

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

n

ts −)(

1

n

ts −)(

1

n

t−π

17

11 1 1

2p( | , ) ( 0 8 ). ,t tt tt x

x 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

)(n

ts

)(n

ts

),0( 2

dσΝ

Ν

)~(

1

n

ts −

ESEMPIO:

18


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

19


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

n

t

n

t

n

t

20

Tracking via Condensation(5)• Formalmente, si calcola

• Nel caso 1D, si puo’ utilizzare una funzione di lik. Gaussiana

)|( )()( n

t

n

t szp

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

w

n

t

n

t

n

t

n

t 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

22

dw σσ >

)(n

tπ )|( )()( n

t

n

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 )()(

)(

n

t

n

ts

t xspffMn

t

X

con

23

Riassunto grafico

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.

{ })(n

tπ

{ })(n

tc

)1(

tc)2(

tc)( N

tc

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 immagini

Numero,

Posizioni,

Forme,

Velocità,

…

BraMBLe: a Bayesian multiple-blob tracker, M Isard, J Maccormick. ICCV 2001. Proceedings. Eighth IEEE International

Conference on, Vol. 2 (2001), pp. 34-41 vol.2.

33

Bramble - ingredienti

• Stato del sistema X

( )m

ttt m xxX ...,,,1

=Numero di oggetti

Stato

dell’oggetto1

tx

2

tx

3

tx

3=m

34


( )svlx ,,,i=Identità

LocazioneVelocità

Appearance

Stato dell’oggetto

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

i=

35


• Lo stato del sistema si approssima con un set diN particelle-configurazioni

...N particelle:

N Weights: 1

tπ 2

tπ 1N

tπ − N

tπ

{ })()( , n

t

n

tt πSX ≈

)1(

tS)2(

tS)( N

tS

36


• Osservazioni Z– sottocampione la matrice video in un set di G filtri zg

con 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 etichetta

2. alla storia precedente (media pesata di tutte le particelle) diquella 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( )()( ∏=g

n

g

nSzSZ

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

i=

40

Bramble - fasi• Dopo l’osservazione

=)(n

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

n

g

nSzSZ

(+ 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 modelliMarkoviani 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 miglior

modello λ, i.e. il modello per cui P(O| λ) è massimizzataV1

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

0.03 0.97 0.00

0.02 0.00 0.98

48

I modelli (2)Shape Emission Probability Transition Probability

0.92 0.00 0.00 0.08 0.00

0.00 0.97 0.01 0.02 0.00

0.00 0.00 0.89 0.04 0.07

0.09 0.11 0.00 0.80 0.00

0.00 0.00 0.09 0.00 0.91

0.91 0.00 0.00 0.09

0.00 0.95 0.05 0.00

0.00 0.06 0.92 0.02

0.08 0.00 0.08 0.83

49

Invarianze

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

•

Complementi di Interazione...

Documents

Transcript of Complementi di Interazione...