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.
The Visual Dynamics Research Group home page
Page maintained by misard@robots.ox.ac.uk.
Last updated 30th September, 1998