Particle filters

A particle filter is a technique used in computer vision to estimate the state of a system, given noisy data from fallible sensors. The underlying idea is called a hidden markov model, and looks something like this:

The assumption is that any state of the system is dependant on it’s previous state (and thus all previous states) and this state is something we can never know directly, only via observations. There are two very different sources of inaccuracy or noise. One originates in the state change process – as it’s assumed we can never have a complete model of this (a good bet in the case of human actions for example). The other source of noise is in the observation process itself, which comes from the way the sensors work. This is more predictable, and filters of this type are built to allow you to account for this.

Particle filters maintain a multitude of hypotheses of the hidden state of the system at the same time. They attempt to model state changes in some basic way, for instance the velocity of a moving object. They also model the observation process, for example a distance/angle reading of an object in x,y space. Each time a new observation arrives, the system grades each particle’s simulated observation against the incoming one and weights them accordingly.

This is a frame from some particle filter code I’ve written which is tracking an object as described above. The line is pointing to the current estimation which is based on readings from a radar like sensor. I’ve told the system that the heading sensor is less reliable than the distance sensor, and so the particles are spread out in a vague crescent shape accordingly. This shape is called the probability distribution function (or pdf) and it’s a strength of particle systems to model complex pdfs such as this effectively.

One thought on “Particle filters”

Leave a Reply

Your email address will not be published. Required fields are marked *