Complementi di Interazione...
Transcript of 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
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
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
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.
{ })(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
Bramble - ingredienti
( )svlx ,,,i=Identità
LocazioneVelocità
Appearance
Stato dell’oggetto
• Gestione delle occlusioni (grazie al 3D) ( )svlx ,,,1i= ( )svlx ,,,2
i=
35
Bramble - ingredienti
• 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
Bramble - ingredienti
• 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
•