Particle Filter and Mean Shift tracking

 

Hybrid tracking schema

Particle filter is the name given to the sample-based (i.e., Montecarlo) approximation of the Bayes recursion. The algorithm is a popular substitute for the Kalman filter in presence of non-Gaussianity of the noise statistics and non-linearity  of the relationships between consecutive state and between state and measurements.

Unlike Kalman filter and its variants (e.g., Extended and Unscented Kalman filters), trackers based on a Particle filter can use multi-modal likelihood functions and propagate multi-modal posterior distributions like those occurring in case of temporary occlusions and background clutter. Despite these advantages the number of samples required, and therefore the complexity of the algorithm, grows exponentially with the dimensionality of the estimated state space. This limits the application of the basic Particle Filter variety where samples are drawn from the prior to relatively small tracking problems.

One could achieve optimal sampling efficiency by drawing the particles from the posterior. However the posterior is also the distribution we aim at estimating and thus we have a clear example of chicken and egg problem. Markov chain Monte Carlo methods provide better performance that sampling from the prior, however they still require a large number of particles to converge.

When computational efficiency is of utmost importance deterministic methods are a better alternative that sample based probabilistic filters. In the specific case of video tracking with histogram models a deterministic approach like colour Mean Shift has been proven successful. Mean Shift is a kernel based gradient descent procedure that finds the local maxima/minima of a function. Dorin Comaniciu derived a special algorithm that minimises the distance between a model histogram representing the target and candidate histograms computed on the current frame. Colour Mean Shift is a very efficient tracker but is unable to cope with occlusions and in general with tracking ambiguities that lead to running the optimisation procedure over a multi-modal objective function.

To overcome these problems, we proposed a hybrid tracker tracker that combines Particle Filter and Colour Mean Shift and obtains the best of both worlds. As the baseline Particle Filter the tracker first produces a small number of random samples from the tracking prior  and then refines the sample-set by applying Mean Shift to each particle. The result is an improved approximation of the posterior around regions of the state space where the target is more likely to be.

http://emayvision.com/wp-content/uploads/2011/06/tracking_comparison.flv

As shown in the video above the combined tracker outperforms both Particle Filter and Mean Shift in terms of tracking accuracy and reliability. Large improvements are achieved in case of fast and abrupt movements where the shift is larger than the basin of attraction of the Mean Shift step and the target is on the tails of the prior distribution as estimated by baseline Particle Filter. More information on this tracking method is available in the publications listed below.


Related publications

Maggio, Emilio; Cavallaro, Andrea (2011): Video tracking: theory and practice. Wiley, 2011. (Type: Book | Links | BibTeX)
Maggio, Emilio; Cavallaro, Andrea (2009): Accurate appearance-based Bayesian tracking for maneuvering targets. In: Computer Vision and Image Understanding, 113 (4), pp. 544–555, 2009. (Type: Journal Article | Links | BibTeX)
Maggio, Emilio; Cavallaro, Andrea (2005): Hybrid Particle Filter and Mean Shift tracker with adaptive transition model. In: IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Philadelphia, PA, USA, 2005. (Type: Inproceeding | Links | BibTeX)

Links


4 Responses to Particle Filter and Mean Shift tracking

  1. liuxuan says:

    hello, I am a chinese graduate.I find your method very excellent and want to have a try .By the way ,could you please provide your code for me because I want to compare yours and mine.Thank you .

    • Emilio says:

      Dear Liu Xuan,

      unfortunately the code is not publicly available. However in my papers I have used sequences that are publicly available, you can find some extra information on datasets at videotracking.org

  2. Ahmad says:

    Hello Sir, I would like to watch your lecture (if ever recorded) in the ICIP 2011 “Spatio‐temporal filtering for multi‐object tracking in image sequences”, that was presented by Prof. Andrea Cavallaro and yourself. Thank you

Leave a Reply