The Condensation Algorithm


hand in clutter 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.


leaf Here is an MPEG (2.3Mb) showing the Condensation algorithm tracking a leaf blowing in the wind, against a background of similar leaves.

	  girl Here is an MPEG (1.1Mb) showing the Condensation algorithm tracking a girl dancing vigorously to a Scottish reel, against a cluttered background scene.

hand in
	  clutter 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.

	  drawing house 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.

hand in
	  clutter 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

	StillHere 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.


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] 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.

Back to

Michael Isard's index page

The Visual Dynamics Research Group home page

Page maintained by

Last updated 30th September, 1998

Valid HTML 4.0!