Kalman e ConDensation in video-tracking - Sviluppo e comparazione dei due algoritmi per il...

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni

IntroduzioneGround Truth

Algoritmi

Model BasedTrackingKalman Filter

Condesation

EsperimentiVideo

Risultati

Conclusione

UNIVERSITÀ DEGLI STUDI DI FIRENZE

Facoltà di Ingegneria - Corso di laurea specialistica in INGEGNERIA INFORMATICA

Kalman e ConDensation in video-trackingSviluppo e comparazione dei due algoritmi per il

tracciamento di oggetti su video

Presentazione ElaboratoANALISI IMMAGINI E VIDEO

Docente:Prof. Pietro PalaAssistenti:Ing. Walter NunziatiIng. Andrew D. Bagdanov

Autori:Nicola Martorana

Iacopo MasiMarco Meoni

4 Luglio 2007

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Introduzione

DefinizioneTracking video è quel processo che, dato un flussovideo, localizza e segue uno o più oggetti che simuovono nella scena.È quindi possibile ricavare informazioni su:

1 posizione passata2 stato attuale3 previsione dello stato futuro

L’ ambito di utilizzo è da collocarsi in settori come:

Industria per la localizzazione di oggetti in movimentoSistemi di video sorveglianza intelligenteSistemi software per editing dei video

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Obiettivi

L’applicazione deve poter:1 Eseguire Tracking basato su modelli tramite:

Kalman FilterConDensation

2 Possibilità di scelta del blob da tracciare in caso ditracking multiplo.

3 Tracciare a video l’andamento dei due algoritmi.4 Fornire un output dei risultati al fine di ottenere una

rappresentazione grafica dell’accuratezza dei duemetodi.

5 Progettare e realizzare l’applicazione in maniera taleche possa essere compilata ed eseguita supiattaforme diverse (Win32, Linux).

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Ambiente di lavoro

Condizione OttimaleLa misura del centro del blob è ottenibile per ogni framedel video.Nella realtà questa condizione non è detto che siaverificata.

Requisiti dei Video:

1 Telecamera di ripresa fissa2 Deve possedere un numero determinato di frames

iniziali con esclusivamente il background della scena

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Background Subtraction

L’idea di base è conoscere il modello dello sfondo,segmentando ogni frame del video in una maschera diforeground e background.

TipologieMetodi di base

Running average

Distribuzione Unimodale - Running gaussian average

Mixture of Gaussian

Possibili problematiche sono:

Presenza di illuminazione che genera ombreOggetti in movimento che si inseriscono nella scenaOggetti rilevati come foreground che fermano il loromoto

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Mixture of Gaussian (1)

Di tipo statistico e onlineModella le informazioni di ogni pixel come processo difunzioni gaussianePermette il tuning dei parametri come:

Soglia di classificazioneNumero di Gaussiane per pixel

Algoritmo:1) Ogni pixel xt è rappresentato da un processo di KGaussiane nella forma P (µk, σk, ωk):

xt =k∑

j=1

ωi,t ·1√

2π · σ2j,t

· e−

(xt−µj,t)2

2σ2j,t

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Mixture of Gaussian (2)Online learning2) Il processo è valutato sull’intensità dei valori di grigio deipixel con:

|xt − µj,t| > 2.5 · σj,t per j = 1..k

e i pesi ωj vengono riaggiornati.Rilevamento del foreground3) Si ordinano le k distribuzioni partendo da quelle conmaggior peso e minor varianza (bg) fino a quelle con minorpeso e maggior varianza (fg). Il parametro risulta: rj,t = ωj,t

δj,t

4) Le prime B distribuzioni ottenute dalla seguente formulasono associate al bg viceversa le altre:

B = argminb

b−1∑j=0

rj,t > T

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Ground Truth

La blob detection è effettuata tramite la libreria OpenCVlibblob.

Caratteristiche1 I blobs sono identificati attraverso il seguente metodo:

sul foreground non viene applicata nessuna mascheraper correggerlocon una soglia di differenza fg/bg di 10 sui valori digrigio

2 Si sceglie il blob a distanza euclidea minima tra tutte ledistanza calcolate dal punto del click utente alcentroide di ogni blob.

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Introduzione al Model-based TrackingLa misura, ottenuta come dato campionato, rappresenta ilcentroide del blob nella forma:

x = [xc, yc] (1)

Una volta campionato l’oggetto di interesse, le osservazionisono inserite come input ad un algoritmo, che può essere:

1 Filtro di KalmanAnni ’50Per moti lineari e semplicioggetti puntiformi

2 ConDensationAnni ’90Per moti non lineariOggetti dalla forma complessa

In caso di tracking multiplo in contemporanea è necessario unmeccanismo di associazione dati tra blob.

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Model-based Tracking

I due filtri possono tracciare oggetti di qualsiasi natura, manecessitano di un modello che definisca il moto dell’oggettostudiato.

DefinizionePer modello si intende la rappresentazione di un oggettoche trovi corrispondenza col fenomeno modellato per il fattodi riprodurne le caratteristiche e i comportamentifondamentali.

Il modello può essere ricavato empiricamente oppureconosciuto a priori.Nel caso più generale possibile è possibile utilizzare lalegge del moto di Newton:

s(t) = s0 + v t +12a t2 (2)

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Kalman Filter

Il filtro di Kalman è un insieme di equazioni matematicheche si offre come strumento per la stima dello stato di unsistema dinamico, sulla base di misure soggette a rumore,anche quando la vera natura del sistema è sconosciuta.

E’ lo strumento più utilizzato nei problemi di tracciamento,anche se si dimostra veramente efficiente solo nei casi incui:

il moto è molto semplice (lineare)l’oggetto da tracciare possa essere rappresentatocome un punto in movimentoil rumore che incide sul sistema possa esserericondotto a rumore di tipo gaussiano.

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Le equazioni

xt = A · xt−1 + B · ut−1 + wt (3)

zt = H · xt + vt (4)

xt è lo stato dell’oggetto

zt è la scelta dei parametri misurati che riteniamo utile a descrivereil moto tenuto conto anche un certo errore sulla misura

wt e vt sono due processi gaussiani con media zero e covariazarispettivamente Q e R

xt−1 è la posizione dell’oggetto all’istante precedente

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

AlgoritmoLe equazioni del filtro di Kalman sono raggruppabili in duemacrocategorie associate a due momenti ben distintidell’algoritmo di predizione:

Figura: Ciclo di Kalman completo

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Il Modello - 1Per descrivere il moto dei nostri oggetti ci è sembrata lascelta più semplice rappresentare il generico moto di unpunto nel piano.

Figura: Esempio di vettori di stato moto sul piano

(x, y) è la posizione data secondo le coordinate(vx, vy) è la velocità rispettivamente orizzontale e verticaledell’oggetto nel punto (x, y)

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Il Modello - 2

x =

xyvx

vy

è il vettore di stato

A =

1 0 ∆t 00 1 0 ∆t

0 0 1 00 0 0 1

è la matrice di transizione del modello

But = 0 sull’oggetto non agiscono forze esterne

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Il modello - 3

Q =

ρ 0 0 00 ρ 0 00 0 ρ 00 0 0 ρ

covarianza del processo cherappresenta il rumore sul sistema

H =[1 0 0 00 1 0 0

]sceglie le componenti dello stato perconfrontarlo con la misura

R =[0.285 0.0050.005 0.046

]definisce il rumore associato alla misura

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Condensation - 1

E’ un’implementazione del Particle Filter, un filtro di tipoRicorsivo Bayesiano.

Conditional Density PropagationE’ un algoritmo di tipo probabilistico che risulta moltorobusto rispetto a dati rumorosi e a cambiamenti distato non lineari.Permette di essere utilizzato per lo studio di motidescritti anche da modelli complessi di tipo non lineare.Supporta previsoni di tipo multimodale.L’algoritmo utilizza un campionamento casuale eordinato delle posizioni assunte dall’oggetto nei variistanti di tempo per modellare funzioni di densità diprobabilità arbitrariamente complesse.

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Condensation - 2

Utilizza un numero N finito di campioni per approssimare lacurva che descrive la distribuzione dei dati p(xkz1:k).

Ciascun campione - sample - consiste di due valori: lo statoe il peso.

Chiamiamo con Ht il vettore dei samples all’istante t:

Ht = {−→s1(t), ...,−→sN (t)}

Dove:−→si (t) = {−→xi(t), p(xi(t))}−→xi(t) è la posizione associata al sample i all’istante t.p(−→xi(t)) è la probabilità associata alla posizione −→xi(t)che caratterizza il sample i

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Algoritmo - Inizializzazione

Al primo passo dell’algoritmo si inizializza tutti i samples:

Ciascuna posizione può essere scelta in modo casualesecondo una distibuzione uniforme.La probabilità associata a ciascun sample è invecedistribuita secondo una gaussiana standard centratanel valore medio tra il valore massimo e il valoreminimo assumibile per la posizione dell’oggetto e larelativa varianza.

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Algoritmo - passo tIl sample −→si (t) con probabilità maggiore è la predizioneper il Condensation al passo t.

Per passare dal vettore Ht al vettore Ht+1 si eseguonoquesti passi:

1 Si campiona la posizione reale dell’oggetto: −→z (t)

2 Si calcola la posizione per ciascun sample secondo lospostamento dato dal modello dinamico che descrive il motodell’oggetto:

−→xi(t + 1) = f(−→xi(t)) (5)

3 Si stima la probabilità p(−→z (t)) secondo la densità diprobabilità dei campioni all’istante t centrata in −→xi(t).

4 Per ogni sample è ricalcolata la probabilità condizionataapplicando il teorema di Bayes:

pi(−→xi(t + 1)) = p(−→xi(t) | −→z (t)) (6)

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Il Modello - 4

La nostra implementazione del Condensation rispettafedelmete l’algoritmo che è stato prima presentato.

Per quanto riguarda il modello dinamico associato si èutilizzata la stessa equazione valida per il tracciamento fattocon il filtro di Kalman:

xt+1 = Axt (7)

Dove:

A =

1 0 ∆t 00 1 0 ∆t

0 0 1 00 0 0 1

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Ciclo di lavoro

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Parametri degli esperimenti

Esperimenti: variazione di tre parametri nei tre video selezionati

Intervallo Frames Frames tra due applicazioni consecutive del TrackingAllontanamento dalle condizioni ottimali di lavoro,simulazione del comportamento dei tracker reali.

Q - Area Kalman Autovalori della matrice del rumore sul processo (Q)Ririsulta l’area di confidenza del filtro di Kalman, ovverol’area nella quale deve risiedere il blob al frameprecedente per poter continuare ad essere tracciatoall’esecuzione successiva.

Samples ConDensation Numero dei samples ad ogni esecuzioneÈ il numero totale di samples che utilizza il ConDensationper effettuare i calcoli statistici ad ogni esecuzione delTracking

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Output & Scripting

Il software produce sei files di output:coordinateReali.txt Coordinate reali dell’oggetto da tracciare

coordinateKalman.txt Coordinate previste da Kalman

coordinateCondensation.txt Coordinate previste dal ConDensation

distanzaKalman.txt δk Distanza tra le coordinate reali e la previsione di Kalman

distanzaCondensation.txt δc Distanza tra coord reali e previsione ConDensation

Risultati.txt distanza media, δk, δc, varianza media ConDensation(σx, σy).

I files ottenuti vengono processati da due script bashgplot.sh Invoca degli script GNUPlot che restituiscono dei grafici relativi

ai risultati ottenuti, consentendo una valutazione immediatadell’esperimento effettuato.

exp.sh Organizza i files di output e le immagini comparative disegnatenel filesystem, consentendo un facile riepilogo dei risultati eduna ordinata catalogazione di questi.

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Video selezionati

1 movie12.mjpeg (mjpeg/xvid)

- occlusione, moto circolare ecostante

- 640x480, 25fps, 50.4s

2 tappeto_nozoom.avi (avi/xvid)

- moto vario, repentine accelerazioni,oggetto entra ed esce dalla scena

- 320x240, 10fps, 59s

3 singlecar.avi (avi/xvid)

- moto costante, oggetto entra edesce dalla scena

- 648x484, 30fps, 33s

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

movie12.mjpeg - MOD:3, Q:1000, S:1000

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione


AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

tappetonozoom.avi - MOD:2, Q:1000, S:1000

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione


AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

tappetonozoom.avi - MOD:1, Q:0.001, S:1000

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione


AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

tappetonozoom.avi - MOD:1, Q:0.001, S:1000

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

ConclusioneFiltro di Kalman

Ottimo se eseguito ogni framePerde l’oggetto se fuori dall’area di confidenzaImpreciso su movimenti non lineariTentativo di predizione dell’oggetto non tracciato incaso di occlusione

ConDensation

Meno preciso di KalmanNon perde mai l’oggettoEfficiente su tracking non lineareOttimo tracciamento in caso di occlusione

Non è possibile elevare uno dei due approcci come migliore.Tuning dei parametri porta a conclusioni particolari.

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

Conclusione

Materiale: software, risultati, relazione, presentazione

Rilasciato con licenza GPLDisponibile su spazio SVN Google Codesvn checkout http://video-tracker.googlecode.com/svn/trunk/ video-tracker

Sviluppato e testato sui sistemi operativi:

Ubuntu/Kubuntu 6.10/7.04Microsoft Windows XP

Video utilizzati:Centro d’eccellenza MICC (Università di Firenze)Produzione autonoma

http://code.google.com/p/video-tracker/

AnalisiImmagini e

Video

N. MartoranaI. Masi

M. Meoni


Algoritmi


Condesation

EsperimentiVideo

Risultati

Conclusione

UNIVERSITÀ DEGLI STUDI DI FIRENZE

Facoltà di Ingegneria - Corso di laurea specialistica in INGEGNERIA INFORMATICA

Kalman e ConDensation in video-trackingSviluppo e comparazione dei due algoritmi per il

tracciamento di oggetti su video

Presentazione ElaboratoANALISI IMMAGINI E VIDEO

Docente:Prof. Pietro PalaAssistenti:Ing. Walter NunziatiIng. Andrew D. Bagdanov

Autori:Nicola Martorana

Iacopo MasiMarco Meoni

4 Luglio 2007

Kalman e ConDensation in video-tracking - Sviluppo e comparazione dei due algoritmi per il...

Technology

Transcript of Kalman e ConDensation in video-tracking - Sviluppo e comparazione dei due algoritmi per il...