The Condensation Algorithm
Background
Tracking objects
through highly cluttered scenes is difficult. We believe
that for tracking to be robust when following agile moving
objects, in the presence of dense background clutter,
probabilistic algorithms are essential. Previous algorithms,
for example the Kalman filter, have been limited in the
range of probability distributions they represent. We have
developed a new algorithm, the Condensation
algorithm (Conditional
Density Propagation) which
allows quite general representations of
probability. Experimental results show that this increased
generality does indeed lead to a marked improvement in
tracking performance. In addition to permitting high-quality
tracking in clutter, the simplicity of the
Condensation algorithm also allows the use
of non-linear motion models more complex than those commonly
used in Kalman filters. We have implemented a mixed
discrete/continuous tracker in the
Condensation framework which switches
between multiple continuous Auto-Regressive Process motion
models according to a discrete transition matrix. Also, by
using the statistical technique of importance
sampling it is possible to build a
Condensation tracker which runs in real
time, and we have implemented a real-time hand-tracker on a
low-end SGI workstation.
Sample Code
Download source code of a simple implementation of the Condensation algorithm.
Results
Here is an MPEG (2.3Mb) showing the
Condensation algorithm tracking a leaf blowing in the wind,
against a background of similar leaves.
Here is an MPEG (1.1Mb)
showing the Condensation algorithm tracking
a girl dancing vigorously
to a Scottish reel, against a cluttered background
scene.
Here is an MPEG (1.2Mb)
showing the Condensation algorithm tracking
a hand as it moves and flexes
its fingers, first against a plain background, and then
against a highly cluttered desk.
Here is an MPEG (1Mb)
showing a mixed-state Condensation tracker
following a hand as it draws
a picture of a house. The colour of the outline indicates
which discrete state the model is estimated to be in at each
timestep. Red indicates slow drawing motions, green a
scribbling motion for filling in areas such as the door of
the house, and blue indicates pauses when the hand is
stationary.
Here is an MPEG (8Mb) showing real-time tracking by a
Condensation tracker using importance
sampling to follow a hand as it
moves first over a very cluttered desk and then in front of
a moving cluttered background. The tracker runs at 30Hz on a
desktop SGI O2 workstation, and performs automatic
re-initialisation when a hand leaves then re-enters the
scene. A very crude colour-segmentation algorithm is used to
direct the importance sampling, and the circles shown in the
movie correspond to skin-coloured blobs detected by the
colour segmentation. Especially in the second part of the
sequence, where the background consists of a person, the
colour-segmentation reports many false positives, but
hand-tracking remains accurate.
The Condensation Algorithm Animation
Here is an MPEG (3.4Mb) showing an animation of the
Condensation algorithm produced using the
Obliq-3D
algorithm animation system developed at the Digital
Systems Research Center (SRC). The animation shows a few
cycles of the algorithm applied to a one-dimensional
system. The green spheres correspond to the members of the
sample set, where the size of the sphere is an indication of
the sample weight. The red line is the measurement density
function. Please refer to our paper CONDENSATION
-- conditional density propagation for visual tracking for
details of the Condensation algorithm.
Publications
- ICondensation: Unifying low-level and high-level tracking in a stochastic framework
-
Michael Isard and Andrew Blake
Proc 5th European Conf. Computer Vision, 1998
- A smoothing filter for Condensation
-
Michael Isard and Andrew Blake
Proc 5th European Conf. Computer Vision, 1998
- A mixed-state Condensation tracker with automatic model-switching
-
Michael Isard and Andrew Blake
Proc 6th Int. Conf. Computer Vision, 1998
- CONDENSATION -- conditional density propagation for visual tracking
-
Michael Isard and Andrew Blake
Int. J. Computer Vision, 29, 1, 5--28, (1998)
- Contour tracking by stochastic propagation of conditional density
-
Michael Isard and Andrew Blake
Proc. European Conf. on Computer Vision, vol. 1, pp. 343--356, Cambridge UK, (1996).
![[BEST PAPER]](images/best.gif)
Prize of the European Vision Society, 1996.
Related work
Here are some pages featuring work related to Condensation in computer vision, and also references to other research on similar algorithms.
- John MacCormick's research into observation densities and initialisation strategies for Condensation.
- Michael Black's Condensation-based gesture recognition.
- Minerva, a robot tourguide at the Smithsonian's National Museum of American History. This link describes how Minerva uses Condensation to determine where it is in the museum.
- The DRA Pattern and Information Processing Group papers. Neil Gordon's `bootstrap filter' is very similar to the Condensation algorithm.
- Genshiro Kitagawa's homepage. The `Monte Carlo filter' is very similar to the Condensation algorithm.
- Peter Clifford's homepage. The paper on `Prediction and Control in Non-linear Systems' deals with Condensation-like algorithms.
- Neil Shephard's homepage. The paper `Filtering via simulation: auxiliary particle filter' which can be found at this site deals with Condensation-like algorithms.
- Arnaud Doucet's homepage. The paper `On Sequential Simulation-Based Methods for Bayesian Filtering' outlines a sequential random-sampling framework which includes Condensation as a special case.
Back to
The Visual Dynamics Research Group home page
Page maintained by misard@robots.ox.ac.uk.
Last updated 30th September, 1998
