Tracking
Definition of Tracking
Tracking:
Generate some conclusions about the motion of
the scene, objects, or the camera, given a
sequence of images.
Knowing this motion, predict where things are
going to project in the next image, so that we
dont have so much work looking for them.
Why Track?
Detection and
C
recognition are expensive
If we get an idea of
Scene
where an object is in
A B
the image because we
Image Sequence
have an idea of the
motion from previous
C
images, we need less Detection
+ recognition
work detecting or
Tracking
recognizing the object.
(less detection,
no recognition)
New
person
Tracking a Silhouette by
Measuring Edge Positions
Observations are positions of edges along normals to tracked contour
Why not Wait and Process the
Set of Images as a Batch?
In a car system, detecting and tracking
pedestrians in real time is important.
Recursive methods require less computing
Implicit Assumptions of
Tracking
Physical cameras do not move instantly
from a viewpoint to another
Object do not teleport between places
around the scene
Relative position between camera and scene
changes incrementally
We can model motion
Related Fields
Signal Detection and Estimation
Radar technology
The Problem: Signal Estimation
We have a system with parameters
Scene structure, camera motion, automatic zoom
System state is unknown (hidden)
We have measurements
Components of stable feature points in the
images.
Observations, projections of the state.
We want to recover the state components from
the observations
Necessary Models
We use models to describe a priori knowledge about
the world (including external parameters of camera)
the imaging projection process
Previous State
System Dynamics
Model
Next State
Measurement
Model (projection)
State
(u, v)
Measurement
A Simple Example of Estimation
by Least Square Method
Measurement
x
Goal: Find estimate a of state a
such that the least square
error between measurements
and the state is minimum State variable
n
a
1
2
C=
(x
2
i =1
a)
C
= 0 = ( xi a ) = xi n a
a
i =1
i =1
a
n
1
a = xi
n i =1
n
x
xi-a
xi
ti
Recursive Least Square Estimation
We dont want to wait until
all data have been collected
to get an estimate a of the
depth
We dont want to reprocess
old data when we make a
new measurement
Recursive method: data at
step i are obtained from a
data at step i-1
Measurement
x
State variable
a
x
xi
ai 1 ai
Recursive Least Square Estimation 2
Recursive method: data at
step i are obtained from a
data at step i-1
i
i 1
xi
1
1
1
ai = xk = xk + xi
i 1
1
i k =1
i k =1
i
a
=
x
1
k
i 1
1
i 1 k =1
ai =
ai 1 + xi
i
i
1
ai = ai 1 + ( xi ai 1 )
i
Recursive Least Square Estimation 3
Gain
Actual
measure
Predicted
measure
1
ai = ai 1 + ( xi ai 1 )
i
Estimate at step i
Innovation
Gain specifies how much
do we pay attention
to the difference
between what we expected
and what we actually get
Least Square Estimation of the
State Vector of a Static System
x1 H1
1. Batch method
x2 H 2
xi = H i a
=
a
H1
measurement equation ... ...
xn H n
x1
x = Ha
that minimizes
Find estimate a
1
T
C = (X H a) (X H a)
2
T
1
T
We find a
= (H H) H X
Hi
x2
xi
H2
H1
Hi
Least Square Estimation
of the State Vector x
of a Static System 2
xi
2. Recursive method
x2
H2
Calculation is similar to calculation of running average
1
We had: ai = ai 1 + ( xi ai 1 )
i
i
Now we find: a
with
Predicted measure
= a i -1 + K i (X i H i a i -1 )
Gain matrix
K i = Pi H i
T
T 1
Pi = (H i H i )
Innovation
Xi
Dynamic System
X i = X i 1 + Vi 1 t
Vi = Vi 1 + Ai 1 t
Ai = Ai 1 + w
X i 1 t
V = 0 1
i
Ai 0 0
State of rocket
a i Vi
Ai
Measurement
xi
0 X i 1 0
Tweak factor
t Vi 1 + 0
ai = a i-1 + w
1 Ai 1 w
State equation for rocket
Xi
xi = [1 0 0] Vi + V
Ai
Noise
xi = H a i + V
Measurement equation
Recursive Least Square
Estimation for a Dynamic System
(Kalman
Filter)
Tweak factor for model
State equation
a i = i a i -1 + w i-1
Measurement equation
xi = Hi ai + v i
w i ~ N (0, Q i )
Measurement noise
v i ~ N (0, R i )
Prediction for ai
a i = i a i -1 + K i (x i H i ia i -1 ) Prediction for xi
T
T
-1
K i = P'i H i ( H i P'i H i + R i ) Gain
P'i = i Pi -1 + Q i -1
T
i
Covariance matrix for
prediction error
Pi -1 = (I K i-1 H i -1 )P'i -1
Covariance for estimation error
Estimation when System Model
is Nonlinear
(Extended Kalman Filter)
State equation
Measurement equation
a i = f ( a i -1 ) + w i -1
xi = Hi ai + v i
a i = f ( a i -1 ) + K i (x i H i f(a i -1 ))
K i = P'i H i ( H i P'i H i + R i )
T
f
f
P'i =
Pi -1
+ Q i -1
a i
a i
T
Jacobian Matrix
Pi -1 = (I K i -1H i -1 )P'i-1
-1
Differences compared to
regular Kalman filter are
circled in red
Tracking Steps
Predict next state as i a i-1 using
previous step and dynamic model
Predict regions N ( H i i a i -1 , P'i )
of next measurements using
measurement model and
uncertainties
Prediction
Make new measurements xi in
region
predicted regions
Measurement (u, v)
Compute best estimate of next state
a i = i a i -1 + K i (x i H i ia i -1 )
Correction of predicted state
Recursive Least Square Estimation for
a Dynamic System (Kalman Filter)
x
Measurement xi
State vector ai
i
Estimation a
Tracking as a Probabilistic
Inference Problem
Find distributions for state vector ai and for
measurement vector xi. Then we are able to
compute the expectations a i and x i
Simplifying assumptions (same as for HMM)
P (a i | a1 , a 2 ,L , ai -1 ) = P (a i | a i -1 )
(Only immediate past matters)
P(x i , x j , K, | a i ) = P(x i | a i ) P(x j | a i ) K P(x k | a i )
(Conditional independence of
measurements given a state)
Tracking as Inference
Prediction
P (a i | x 1 , L , x i -1 ) = P(a i | a i-1 ) P (a i-1 | x1 , L , x i-1 )da i -1
Correction
P (a i | x 1 , L , x i ) =
P ( x i | a i ) P (a i | x1 , L , x i -1 )
P(x
| a i ) P (a i | x1 , L , x i -1 ) da i
Produces same results as least square approach if
distributions are Gaussians: Kalman filter
See Forsyth and Ponce, Ch. 19
Kalman Filter for 1D Signals
State equation
ai = f ai-1 + wi-1
Measurement equation
xi = h ai + vi
Tweak factor for model
wi ~ N (0 ,q )
Measurement noise
vi ~ N (0,r )
Prediction for ai (a priori estimate)
ai = f ai-1 + K i ( xi h f ai-1 )
2
-1
K i = p' i h (h p'i + r ) Gain
p'i = f pi 1 + q
2
Prediction for xi
Standard deviation for
prediction error
for estimation error
pi-1 = (1 K i 1 h ) p 'i-St.d.
1
Applications: Structure from Motion
Measurement vector components:
Coordinates of corners, salient
points
State vector components:
Camera motion parameters
Scene structure
xi
Is there enough equations?
N corners, 2N measurements
N unknown state components from structure
(distances from first center of projection to
3D points)
6 unknown state components from motion
(translation and rotation)
More measurements than unknowns for every
frame if N>6 (2N > N + 6)
Batch methods
Recursive methods
(Kalman filter)
Problems with Tracking
Initial detection
If it is too slow we will never catch up
If it is fast, why not do detection at every frame?
Even if raw detection can be done in real time, tracking
saves processing cycles compared to raw detection.
The CPU has other things to do.
Detection is needed again if you lose tracking
Most vision tracking prototypes use initial
detection done by hand
(see Forsyth and Ponce for discussion)
References
Kalman, R.E., A New Approach to Linear Prediction
Problems, Transactions of the ASME--Journal of Basic
Engineering, pp. 35-45, March 1960.
Sorenson, H.W., Least Squares Estimation: from Gauss to
Kalman, IEEE Spectrum, vol. 7, pp. 63-68, July 1970.
http://www.cs.unc.edu/~welch/kalmanLinks.html
D. Forsyth and J. Ponce. Computer Vision: A Modern
Approach, Chapter 19.
http://www.cs.berkeley.edu/~daf/book3chaps.html
O. Faugeras.. Three-Dimensional Computer Vision. MIT
Press. Ch. 8, Tracking Tokens over Time.
