Visuelles Objekttracking: Einführung

• Objekttracking: Verfolgung von Objektkonfigurationen in Bildsequenzen

• Objektkonfiguration z.B. Position, Größe, Orientierung, Deformation, etc.

• Echtzeitfähigkeit (40ms!)• Anwendungen

– Mensch-Maschine-Schnittstelle– Autonome

Fahrerassistenzsysteme– RoboCup– Lokalisation– Motion Capture– Videoüberwachung

• Objektzustand• Bildbeobachtungen

• Formulierung des Tracking-Problems:

Beobachtungswahrscheinlichkeit (Messmodell)Dynamisches Modell

• Markov-Annahme: aktuelle Beobachtung unabhängig von vorangegangenen Beobachtungen und Zuständen

Objekttracking: Einführung

( )ttt XXXXX ,...,, , 21=

( )ttt ZZZZZ ,...,, , 21=

ttttttt

tttttt

dXZXpXXpZXp

ZXpXZpZXp

)|()|()|(

)|()|()|(

11

11111

∫ ++

+++++

=

∝

)|( 11 ++ tt XZp

)|( 1 tt XXp +

Objekttracking: Einführung

Vier Grundelemente von Trackingalgorithmen

• Objektrepräsentation (Farbe, Form,Template, etc.)• Repräsentation der Beobachtungen (Features im

Bild: Farbe->Histogramme, Form->Kanten, etc.)• Generierung von Hypothesen (Kalmanfilter:

Hypothesen unter Annahme einer Gaußverteilung)• Messung von Hypothesen (z.B. Template-Matching)

Condensation: Algorithmus

Initialisierung

Resampling

Vorhersage

Messung

Terminierung ?nein

ja

• Conditional density propagation (Isard,Blake ‘96)• Partikelfilter

• Sampleset repräsentiert

Tracking = Entwicklung der Samples

Schätzung: z.B. gewichteterMittelwert der Samples

)|( tt ZXp

( ) Nis it

it

it ...1 ,, )()()( == πx

∑=

=N

i

it

ittX

1

)()(ˆ xπ

Condensation: Algorithmus

Condensation: Algorithmus

• Initialisierung: z.B. zufällig, „region of interest“, etc.• Messung: p(z|x) -> Gewichtung• Resampling: proportional zur Gewichtung

„cumulative weight“

• generiere Zufallszahl• finde kleinstes j mit• Selektiere

• Vorhersage: dynamisches Modell z.B.Markov-Prozess

0 ,...1 , )0()()1()( ==+= −t

nt

nt

nt cNncc π

]1,0[∈rrc j

t ≥−)(1

)(1

)( jt

nt −= xx

Condensation: Eigenschaften

• Multimodale Verteilungen, mehrere Hypothesen in jedem Zeitschritt

• Multiobjekttracking• Einfacher Algorithmus• Garantierte Laufzeit über Anzahl der Partikel• Einfache Objektmodelle• Robustheit in verrauschten Umgebungen• Erhöhter Zeitbedarf verglichen mit Kalmanfilter

Beispiel: Farbtracking 1

• State-Vektor• Dynamisches Modell: brownsche Bewegung

• Gewichtung

( )Tyxyx vvpp ,,,=x

ttt Bwx Ax += −1

=

1000

0100

010

001

T

T

A)1,0(~ Ntw

Beispiel: Farbtracking 1

Beispiel: Farbtracking 2

( )Tyx spp ,,=x• Pérez, et.al 2002• State-Vektor• Gewichtung ->Histogramm-Template

∑∈

−−=)(

])([|)(|);(xRu

tt nubduwKxnq δ

)( :Template 00∗∗ = tt xqq

)](,[exp)|( 2tttt xqqDxzp ∗−∝ λ

2/1

1

);()(1)](,[

−= ∑

=

∗∗N

ntt xnqnqxqqD

Beispiel: Farbtracking 2

Mehrteiliges Farbmodell

Pérez et. al. 2002

• Objektmodell: Kopf-Schulter-KonturenSpline-Template

shape-space-Transformation:

shape-Vektor x: 4 dimensional

Konturtracking

=

=

−xN

x

x

x

y

x

t

t

t

1

1

0

... , T

T

TT

T XWQ +=

TT

xy

yx

)1,...1,1( ,)0,...0,0( , ==

−= 10

TT10

TT01W

Konturtracking

( )

Θ+ΘΘ−Θ

=Θ−Θ=

==

+==

==

yx

yxT

T

T

T

TT

TTQX

2TQX

0

1TQX

TQX

cossin

sincos :)sin,1cos,0,0(

:)0,1,0,0(

:)0,0,0,1(

:0,0,0,0

î −Κ

=

−∝ ∑

−

=

sonst

gefunden Kante |)()(|)(

)(1

exp)|(1

02

ξψ

ψσizi

i

iXZpn

i

• Gewichtung:

)(iK

)(iz

Konturtracking

Condensation vs. Kalmanfilter

Isard, Blake 1998

Multimodale Verteilungen

Isard, Blake 1998

Erweiterungen: Importance Sampling

• Problem: Sampleset kann degenerieren und repräsentiert nicht mehr

• Importance-Funktion z.B. optischer Fluss, Farbsegmentierung etc.

• Resampling:a) Initialisierung: Sampling aus

b) Sampling ausc) Standard Condensation-Sampling

• Gewichtung:

1 ),( (n)t =λtt Xg

( )tt ZXp |

q<αrqq +<≤α

rq +≥α)(/)( ),( )()((n)

tn

ttn

tttt xgxfXg =λ1(n)

t =λ

∑=

−−− ===N

j

jtt

ntt

jt

ntt xXxXpxf

1

)(11

)()(1

)( )|()( π

)( tt Xg

)1,0[∈= rndα

)()()( nt

nt

nt πλπ ←

Erweiterungen: Mixed State Dynamics

• Mehrere dynamische Modelle

-> Modellswitching

• Erweiterung „mode of motion“

• Übergangswahrscheinlichkeiten

• Vorhersageschritt: 1. Modell wählen, 2. Modell anwenden

• Bespiel: Springender BallModell 1: Ballistische BewegungModell 2: Bewegungsumkehr

{ }Stt

tt Ny

y,...,1, ∈

=+ x

x

jitt TiyjyP ,)|( ===

10 ,01

1<<<

−= ε

εεT

Isard, Blake 1998

Visuelle Lokalisation mit Partikelfiltern

Gross, et.al. 2002

Visuelle Lokalisation mit Partikelfiltern

• State-Vektor: Roboterposition • Vorhersage: Bewegungsmodell des Roboters• Gewichtung: Bildähnlichkeiten

Gross, et.al. 2002

),,( ϕyx pp=x

Visuelle Lokalisation mit Partikelfiltern

Gross, et.al. 2002

Wolf et.al. 2002

Visuelle Lokalisation mit Partikelfiltern