Saturday, February 12, 2011

Kalman Filter

The OpenCV book gives decent description of Kalman filter. I suspect there are quite a few typos at the equations though. My attempt to summarize the basic idea: Kalman Filter can be used to estimate motion for computer vision. User provides a model of the motion, measurement and Gaussian error co-variances. The Kalman filter updates the uncertainty parameters (mean, variances) of the model with each new measurement value. The model gives prediction on the next time-frame. The weight given to the new measurement is inversely proportional to its variance.

Cycle: Collect Data -> Make Prediction -> Update Model

Prediction must be made before model update. Prediction error is part of the update parameter.

Sample (kalman.cpp)
  • Predict the location of a 'pixel' moving in a circle of some changing angular velocity.
  • Visualization: red line drawn between 'real' and 'meansured'. yellow line drawn between 'real' and 'predict'. Seeing the 'yellow' line 'chasing' the 'red'.
  • Simple break-down:
    • User specified model parameters: (F, Q) that governs the pixel movement and (H, R) for measurement.
    • Real movements are simulated with (F + Q) [ never be known to the filter ]
    • Measurements are simulated with Real movements x H + R.
    • Kalman predicts a location (angle).
    • Kalman (mean, covar) is corrected with the measurement.
Applications

How to take advantage of this prediction? As demonstrated from the sample, the measurements are noisy, jumps around a lot, the estimation is more stable (slower to respond to direction or large changes). As the name tells it, the it is a signal filter. It reduces noise with a weighted sum of measurement history. It requires a model (transitional matrix) for action and noise.

I suppose it would help like in the case of road-side camera. The locations are observed(measured), find other aspects of the car motion that could be modeled with transitional-matrix (F), like the accelerator and steering wheel in the GPS application. The model is updated with camera measurements. This is also called sensor data fusion (from Wikipedia).

Kalman filter is also good performance. At each iteration it updates its 'last best model' instead of keeping the whole history. Simplifies weighted sum to only 2 terms (last+best + new).

Seems like it's popular for tracking in Augmented / Virtual Reality, which is a class of applications that requires real-time video tracking.

Resources
Reading
Learning OpenCV, O'Reilly.

Future Reading
  • High-Performance Wide-Area Optical Tracking, Welch, Bishop, et al.
  • Robust Optical User Motion Tracking Using a Kalman Filter, Dorfm¨ ullerUlhaas
  • Subject on Condensation (Particle Filter) Algorithm and application to non-linear and non-Gaussian motion

No comments:

Post a Comment