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.

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

Links

• Additional results
• Dorin Comaniciu’s webpage