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.
Download source code of a simple implementation of the Condensation algorithm.
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.
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.
Here are some pages featuring work related to Condensation in computer vision, and also references to other research on similar algorithms.