COMP9517: Computer Vision
Tracking
Week 7 COMP9517 2021 T1 1
Motion Tracking
• Tracking is the problem of generating an inference about the motion of an object given a sequence of images
Week 7 COMP9517 2021 T1 2
Applications
• Motion capture
– Record motion of people to control cartoon characters in animations
– Modify the motion record to obtain slightly different behaviours
• Recognition from motion
– Determine the identity of a moving object
– Assess what the object is doing
• Surveillance
– Detect and track objects in a scene for security
– Monitor their activities and warn if anything suspicious happens
• Targeting
Week 7
COMP9517 2021 T1 3
– –
Decide which objects to shoot in scene Make sure the objects get hit
•
• • • • • • •
Difficulties in Tracking
Lossofinformationcausedbyprojectionofthe 3D world on a 2D image
Noise in images
Complexobjectmotion Non-rigidorarticulatednatureofobjects Partialandfullobjectocclusions Complexobjectshapes Sceneilluminationchanges Real-timeprocessingrequirements
Week 7
COMP9517 2021 T1 4
Example Tracking Problem
Single moving microscopic particle
• Imaged with signal-to-noise ratio (SNR) of 1.5 Human visual motion perception
• Not so accurate and reproducible in quantification
• Good at integrating spatial and temporal information
• Powerful in making associations and predictions
Computer vision challenges
• Integration of spatial and temporal information
• Modeling and incorporation of prior knowledge
• Probabilistic rather than deterministic approach
Bayesian estimation methods…
Week 7
COMP9517 2021 T1 5
Motion Assumptions
• Whenmovingobjectsdonothaveuniquetextureor colour, the characteristics of the motion itself must be used to connect detected points into trajectories
• Assumptionsabouteachmovingobject: – Locationchangessmoothlyovertime
Week 7
COMP9517 2021 T1 6
– – –
Velocity (speed and direction) changes smoothly over time Can be at only one location in space at any given time
Not in same location as another object at the same time
Topics
• Bayesianinference
Using probabilistic models to perform tracking
• Kalmanfiltering
Using linear model assumptions for tracking
• Particlefiltering
Using nonlinear models for tracking
Week 7 COMP9517 2021 T1 7
Bayesian Inference
Week 7 COMP9517 2021 T1 8
Problem Definition
• Amovingobjecthasastatewhichevolvesovertime
Random variable: Xi Specific value: xi
can contain any quantities of interest (position, velocity, acceleration, shape, intensity, colour, …)
• Thestateismeasuredateachtimepoint
Random variable: Yi Specific value: y
in computer vision the measurements are typically features computed from the images
i
• Measurementsarecombinedtoestimatethestate Week 7 COMP9517 2021 T1 9
Three Main Steps
• Prediction: use the measurements ( y , y , …, y
)
01 i−1 up to time i −1 to predict the state at time i
P(X|Y=y,Y=y,…,Y =y ) i 0 0 1 1 i−1 i−1
• Association:selectthemeasurementsattimei that are related to the object state
• Correction:usetheincomingmeasurement to update the state prediction
yi P(X|Y=y,Yy,…=,Y y,Yy=)
i 0 0 1 1 i−1 i−1 i i Week 7 COMP9517 2021 T1
10
Independence Assumptions
• Currentstatedependsonlyontheimmediatepast
P(Xi |X0,X1,…,Xi−1)=P(Xi |Xi−1)
• Measurementsdependonlyonthecurrentstate
P(Y,Y ,…,Y |X )=P(Y |X )P(Y ,…,Y |X ) ijkiiijki
These assumptions imply the tracking problem has the structure of inference on a hidden Markov model
Yi-1
Xi-1
Yi Yi+1
Xi Xi+1
Week 7 COMP9517 2021 T1
11
Tracking by Bayesian Inference • Prediction
P(X|y,y,…,y )=∫ dX
i 0 1 i−1 i−1
=∫P(X |X ,y ,y,…,y )P(X |y ,y,…,y )dX
i i−1 0 1 i−1 i−1 0 1 i−1 i−1
=∫P(X|X )P(X |y,y,…,y )dX
i i−1 i−1 0 1 i−1 i−1
Week 7
COMP9517 2021 T1 12
dynamics model
posterior of previous time
P(X,X |y,y,…,y ) i i−1 0 1 i−1
P(Xi,Xi−1 | y0,y1,…,yi−1)= P(Xi,Xi−1,y0,y1,…,yi−1) P(y0, y1,…, yi−1)
=P(Xi |Xi−1,y0,y1,…,yi−1)P(Xi−1,y0,y1,…,yi−1) P(y0, y1,…, yi−1)
=P(Xi |Xi−1,y0,y1,…,yi−1)P(Xi−1,y0,y1,…,yi−1) P(y0, y1,…, yi−1)
=P(Xi |Xi−1,y0,y1,…,yi−1)P(Xi−1 |y0,y1,…,yi−1)
Tracking by Bayesian Inference • Correction
P(X |y,y,…,y)=P(X,y,y,…,y) i01ii01i
P(y ,y,…,y) 01i
=P(y|X,y,y,…,y )P(X |y,y,…,y )P(y,y,…,y ) ii01 i−1 i01 i−1 01 i−1
P(y ,y,…,y) 01i
=P(y |X )P(X |y ,y,…,y )P(y ,y,…,y ) i i i 0 1 i−1 0 1 i−1
∝P(y|X)P(X|y,y,…,y ) i i i 0 1 i−1
P(y ,y,…,y) 01i
constant
Week 7
COMP9517 2021 T1 13
measurement model
prediction of current state
Tracking by Bayesian Inference
In summary, tracking by Bayesian inference is done by interative prediction and correction:
• Prediction
P(X |Y )=∫P(X |X )P(X |Y )dX
i 0:i −1 i i −1 i −1 0:i −1 i −1
Posterior at time 𝑖𝑖 − 1 P(X|Y)∝P(Y|X)P(X|Y )
• Correction
i 0:i i i i 0:i−1
Posterior at time 𝑖𝑖
Week 7
COMP9517 2021 T1 14
Y =(Y y=,Y y,…,Y= y) 0:k 0 0 1 1 k k
Tracking by Bayesian Inference
To make tracking by Bayesian inference work in practice you need to design two models:
• Dynamics model P(Xi | Xi−1)
• Measurement model P(Y | X )
The specific design choices are application dependent
Week 7 COMP9517 2021 T1 15
ii
Tracking by Bayesian Inference
Final estimates are computed from the posterior:
• Example1:expectedaposteriori(EAP) xˆ = ∫ x P ( X x | Y ) d=x
i i i i 0:i i
• Example 2: maximum a posteriori (MAP)
xˆ = a r g m a x P ( X = x | Y ) i xiii0:i
These are the most popular ones but others are possible
Week 7 COMP9517 2021 T1 16
Tracking by Bayesian Inference
P(X =x |Y ) i i 0:i
xi
Week 7
COMP9517 2021 T1
17
xˆ E A P xˆ M A P ii
Bayesian Tracking Example
Estimating the coordinates of a moving particle:
t
Posterior computed from the image
x
y
t = i +4 t = i +3
t = i +2 t = i t = i 1+
P ( X | Y ) i 0:i
Week 7
COMP9517 2021 T1
18
Kalman Filtering
Week 7 COMP9517 2021 T1 19
Probability Density Propagation
dynamics model
Week 7 COMP9517 2021 T1
20
measurement model
noise
Linear / Gaussian Assumption
If we assume the dynamics (state transition) model and the measurement model to be linear, and the noise to be additive Gaussian, then all the probability densities will be Gaussians
x N(μ,Σ)
• The state is advanced by multiplying with some known matrix
and then adding a zero-mean normal random variable
xi = Axi−1 qi−1 +
• The measurement is obtained by multiplying the state by some
matrix and then adding a zero-mean normal random variable
y=Hx r+ iii
Week 7 COMP9517 2021 T1 21
xi ~ N(Axi−1,Q) yi ~N(Hxi,R)
Kalman Filtering
Correction
1. Compute Kalman gain
K =P−HT(HP−HT +R)−1 iii
2. Correct state with measurement
x=+x− K(−y Hx−) iiiii
3. Correct covariance
P=(I K−H)P− iii
Prediction
1. Predict state
x− = Ax
i i−1
2. Predict covariance
−T
P=APA Q i i−1
Week 7
+
i → i +1 COMP9517 2021 T1
22
Particle Filtering
Week 7 COMP9517 2021 T1 23
Probability Density Propagation
dynamics model
Week 7 COMP9517 2021 T1
24
measurement model
noise
Non-Linear / Non-Gaussian Case
• Represent the conditional state density by a set of samples (particles) with corresponding weights (importance)
P(X |Y )→{s(n),π(n)}N
i 0:i i i n=1
Week 7 COMP9517 2021 T1 25
Particle Filtering
• Propagate each sample using the dynamics model and obtain its new weight using the measurement model
Week 7 COMP9517 2021 T1 26
Particle Filtering Algorithm
Week 7 COMP9517 2021 T1 27
Example Application Tracking of active contour representations of objects
Particle filtering is also known variously as sequential Monte Carlo (SMC) filtering, bootstrap filtering, the condensation algorithm…
Week 7 COMP9517 2021 T1 28
Example Application
Tracking of object location in the presence of clutter
Walking pedestrian represented by a state vector consisting of a center position and a bounding box:
si =(x,y,w,h)i
s(n) i
sˆi
s i
(samples) (estimated) (truth/annotated)
Week 7
COMP9517 2021 T1
29
Example Application Tracking of object location in the presence of clutter
Week 7 COMP9517 2021 T1 30
References and Acknowledgements
• Chapters5and8ofSzeliski2010
• Chapter18ofForsythandPonce2011
• Chapter9ofShapiroandStockman2001
• PaperbyM.IsardandA.Blake1998 CONDENSATION: Conditional density propagation for visual tracking
Available online via the UNSW Library
• Imagesdrawnfromtheabovereferences
Week 7 COMP9517 2021 T1 32