COMP9517: Computer Vision
Week 7 COMP9517 2021 T3 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 T3 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
COMP9517 2021 T3 3
Decide which objects to shoot in scene Make sure the objects get hit
• • • • • • •
Difficulties in Tracking
Lossofinformationcausedbyprojectionofthe 3D world on a 2D image
Noiseinimages
Complex object motion Non-rigidorarticulatednatureofobjects Partialandfullobjectocclusions Complex object shapes Sceneilluminationchanges Real-timeprocessingrequirements
COMP9517 2021 T3 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…
COMP9517 2021 T3 5
Motion Assumptions
• Whenmovingobjectsdonothaveuniquetextureor colour, the characteristics of the motion itself must be used to connect detected points into trajectories
• Assumptionsabouteachmovingobject:
COMP9517 2021 T3 6
Location changes smoothly over time
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
• Bayesianinference
Using probabilistic models to perform tracking
• Kalmanfiltering
Using linear model assumptions for tracking
• Particlefiltering
Using nonlinear models for tracking
• Trajectoryanalysis
Using measures to quantify motion
Week 7 COMP9517 2021 T3 7
Bayesian Inference
Week 7 COMP9517 2021 T3 8
Problem Definition
• Amovingobjecthasastatewhichevolvesovertime
Random variable: Xi Specific value: xi
can contain any quantities of interest (position, velocity, acceleration, shape, intensity, colour, …)
• The state is measured at each time point
Random variable: value: y
in computer vision the measurements are typically features computed from the images
• Measurements are combined to estimate the state Week 7 COMP9517 2021 T3 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: select the measurements at time i that are related to the object state
• Correction: use the incoming measurement 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 T3 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
Week 7 COMP9517 2021 T3
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
COMP9517 2021 T3 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
COMP9517 2021 T3 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 𝑖𝑖
COMP9517 2021 T3 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 T3 15
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
• Example2:maximumaposteriori(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 T3 16
Tracking by Bayesian Inference
P(X =x |Y ) i i 0:i
COMP9517 2021 T3
xˆ E A P xˆ M A P ii
Bayesian Tracking Example
Estimating the coordinates of a moving particle:
Posterior computed from the image
t = i +4 t = i +3
t = i +2 t = i t = i 1+
P ( X | Y ) i 0:i
COMP9517 2021 T3
Week 7 COMP9517 2021 T3 19
Probability Density Propagation
dynamics model
Week 7 COMP9517 2021 T3
measurement model
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:
𝑥𝑥 ∼ 𝑁𝑁(𝜇𝜇, Σ)
• 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 T3 21
xi ~ N(Axi−1,Q) yi ~N(Hxi,R)
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
2. Predict covariance
P=APA Q i i−1
i → i +1 COMP9517 2021 T3
Particle Filtering
Week 7 COMP9517 2021 T3 23
Probability Density Propagation
dynamics model
Week 7 COMP9517 2021 T3
measurement model
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 T3 25
Particle Filtering
• Propagate each sample using the dynamics model and obtain its new weight using the measurement model
Week 7 COMP9517 2021 T3 26
Particle Filtering Algorithm
Week 7 COMP9517 2021 T3
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 T3 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
(samples) (estimated) (truth/annotated)
COMP9517 2021 T3
Example Application Tracking of object location in the presence of clutter
Week 7 COMP9517 2021 T3 30
Trajectory Analysis
Week 7 COMP9517 2021 T3 31
Motion Features
https://doi.org/10.1016/B978-0-12-391857-4.00009-4
COMP9517 2021 T3 32
MSD Analysis
Distancebetweentrackpoints: d(pi,pj)=||pj pi−||2 MSDforagiventimelagt: MSD(t)= 1 ∑N−td2(pi,pi+t)
Directed + diffusion
2 MSD(t)=cDt (vt)+
N−t i=1 Normal diffusion
D = Diffusion coefficient v = Velocity magnitude c=4 (2D) c=6 (3D)
MSD(t)=cDt MSD(t)=cDtα
Anomalous Confined or constrained
COMP9517 2021 T3
References and Acknowledgements
• Chapters 5 and 8 of Szeliski 2010
• Chapter18ofForsythandPonce2011
• Chapter9ofShapiroandStockman2001
• Paper by M. Isard and A. Blake 1998 CONDENSATION: Conditional density propagation for visual tracking
Available online via the UNSW Library
• Some images drawn from the above references
Week 7 COMP9517 2021 T3 34