kalman filter illustrated with 2D example

Simple intro to Kalman Filter, using a simple 2D example.

1. Using Kalman Filter to
Track Particles
Saša Fratina
advisor:
Samo Korpar
2004-01-13

2. Overview
Motivation
Basic principles of Kalman Filter
example
Application to particle tracking
No big deal

3. R. E. Kalman
Born 1930 in Hungary
Studied at MIT / Columbia
Developed filter in 1960/61

4. i i + 1
Illustration example
Measuring parameters of a particle track in 2D
particle
track
parameters:
y, k
measurement:
m

5. System:
our
knowledge
of the
system
Kalman filter –KF
System
state:
unknown
system
parameters
model
measurement


noise
noise
?KF
When and where?

6. When and where?
Tracking and navigation
–Tracking missiles, aircrafts and spacecrafts
–GPS technology
–Visual reality
Tracking in
HEP experiments

7. KF assumptions
Linear system
–System parameters are linear
function of parameters at
some previous time
–Measurements are linear
function of parameters
White Gaussian noise
–White: uncorrelated in time
–Gaussian: noise amplitude
KF is the
optimal filter

8. KF description
System:
our
knowledge
of the
system
System
state:
unknown
system
parameters
model
measurement
KF
parameters
v
v
i = A v
i -1
m
i= H v
i


noise
noise
+ q
i
+ r
i
using vectors and matrices
estimation
of
parameters
v
^

9. KF description: example
System parameters: v
System model:
linear motion y = k x
v
i = A v
i -1
Measurement model:
m
i= H v
i1i
k
y
10
Δx1
i
k
y

























 i
k
y01
i
m














 i
k
y
i
v










10. Noise
Noise: e
Noise covariance matrix
System noise: v
i = A v
i –1+ q
iQ = E(qq
T
)
Measurement noise: m
i= H v
i + r
i
R = E(rr
T
)












)eE(e)eE(e
)eE(e)eE(e
)E(eeV
2212
2111
T
Gaussian E(e
2
) = σ
2

11. KF algorithm
Prediction: v
i
-
= A v
i –1
Correction: v
i = v
i
-
+ K (m
i–H v
i
-
)
v
i = A v
i –1 + q
m
i= H v
i + r
v
^
v KF
Kalman gain matrix
minimize the difference v -v
^
^
^ ^ ^
^

12. Kalman gain matrix
It is easy to show
K = V
-
H
T
(H V
-
H
T
+R)
-1
,
where V
i
-
= AV
i-1A
T
+ Q
Minimize the expected error
Limits:
–system noise << measurement noise v
i = v
i
–
–system noise >> measurement noise v
i = H
–1
m
i0
K
V
)eE(e)eE(e
)eE(e)eE(e
)E(eeV;vve
ab
ij
2212
2111
T


















^^
^

13. Error on parameters
Predictor: V
i
-
= AV
i-1A
T
+ Q
–Q: system noise
Corrector: V
i= (I -KH) V
i
-
–error reduced

14. Kalman filter
Least squares
Example
Simulation
y = k x
Implemented
KF
–prediction
–correction
Compare with
LS method
x
y

15. System noise
x
y
Kalman filter
Least squares

16. Matrix description of system state, model
and measurement
Progressive method
Proper dealing with noise
KF overview
prediction
correction

17. Application to particle tracking
Detector:
–Silicon vertex detector
–Central drift
chamber
Description
of track:
5 parameters

18. Advantages of using KF
in particle tracking
Progressive method
–No large matrices has to be inverted
Proper dealing with system noise
Track finding and track fitting
Detection of outliers
Merging track from different segments

19. Modifications of KF
(!) Non -linear
system extended
Kalman filter
Full precision only
after the last step
–Prediction
–Correction
–Smoothing
Kalman filter
Least squares
x
y

20. Conclusion
We have demonstrated the principles
predictor –corrector method
combining model and measurement
Very useful in tracking
For given assumptions, KF is theoptimal filter
Extensions for non-linear systems
Extensive application
To sum up…

21. Tracking in BELLE detector
Track finding
Track fitting
Track managing

22. Notation overview
v: vector of parameters
–v: our estimation
–v
-
: predicted value
m: vector of measurements
A: matrix describing linear system v
i = A v
i –1
H: matrix describing measurements m
i= H v
i
V: error (on parameter) covariance matrix
Q: system noise covariance matrix
R: measurement noise covariance matrix
K: Kalman gain matrix
^