CONDENSATION—Conditional Density Propagation for Visual Tracking

CONDENSATION (Conditional Density Propagation) is a visual tracking algorithm introduced by Michael Isard and Andrew Blake of the University of Oxford. It was first published as “Contour Tracking by Stochastic Propagation of Conditional Density” at the 4th European Conference on Computer Vision (ECCV) in Cambridge in 1996, and in full as “CONDENSATION—Conditional Density Propagation for Visual Tracking” in the International Journal of Computer Vision in 1998. The journal paper calls the conference paper its short form, so this article treats them as one publication. The method represents the distribution over an object’s outline by weighted random samples carried from frame to frame by a learned motion model. It brought what is now called the particle filter into computer vision, and the conference paper won a best paper award at ECCV 1996 and the Koenderink Prize in 2008.

Problem

The paper’s task is tracking object outlines, modeled as curves, through heavy clutter at or near video frame rate. Background edges can resemble parts of the object, and in the worst case the background contains objects like the target, such as a person walking past a crowd.

Curve trackers of the time, including the authors’ own, used the Kalman filter, which describes the state by a single Gaussian (its origins are covered in Kalman’s 1960 paper). In clutter, several features near the predicted outline suggest different positions, so the state distribution has several peaks that a unimodal Gaussian cannot hold. Combinatorial data-association methods handle clutter for points and corners, but the authors argue that they do not apply naturally to curves.

Contribution

The paper starts from the general Bayesian filtering recursion, which it pictures as drift and diffusion of the density followed by reinforcement near measured features:

$$p(\mathbf{x}_t \mid Z_t) = k_t \, p(\mathbf{z}_t \mid \mathbf{x}_t) \, p(\mathbf{x}_t \mid Z_{t-1}), \qquad p(\mathbf{x}_t \mid Z_{t-1}) = \int p(\mathbf{x}_t \mid \mathbf{x}_{t-1}) \, p(\mathbf{x}_{t-1} \mid Z_{t-1}) \, d\mathbf{x}_{t-1},$$

where $Z_t = \{\mathbf{z}_1, \ldots, \mathbf{z}_t\}$ is the measurement history and $k_t$ a normalizing constant. The Kalman filter evaluates this exactly only in the linear-Gaussian case.

The key idea is to approximate the recursion with factored sampling, a method that Grenander, Chow and Keenan (1991) had used for interpreting single static images. In factored sampling, samples $\mathbf{s}^{(1)}, \ldots, \mathbf{s}^{(N)}$ are drawn from a prior, and each is weighted in proportion to the observation density,

$$\pi^{(i)} = \frac{p(\mathbf{z} \mid \mathbf{x} = \mathbf{s}^{(i)})}{\sum_{j=1}^{N} p(\mathbf{z} \mid \mathbf{x} = \mathbf{s}^{(j)})},$$

so that the weighted set approximates the posterior increasingly well as $N$ grows. CONDENSATION applies factored sampling at every frame, using the previous frame’s weighted set, pushed through the dynamics, as the prior. The authors stress that, despite its generality, it is simpler than the Kalman filter: it needs no Riccati equation for the covariance, only repeated sampling.

The journal paper notes that the same sampling strategy had been developed elsewhere, citing Gordon, Salmond and Smith (1993) and Kitagawa (1996), where it was presented as a development of Monte Carlo methods. The conference paper cites neither. The distinct contribution was the combination of this recursion with learned shape and motion models and a clutter-aware observation model, demonstrated on real video.

Method

Algorithm. Each time step builds a new set of $N$ samples in three steps. Select: draw a sample from the old set with probability equal to its weight, using cumulative weights and binary search. Predict: apply the dynamical model with random noise, so duplicates split apart. Measure: weight each new sample by the observation density and normalize. A fixed $N$ bounds the computation per frame; the paper gives the cost as $O(N \log N)$, reducible to $O(N)$.

Shape space. As in the authors’ earlier Kalman-filter trackers, an outline is a parametric B-spline curve whose control points are restricted to a low-dimensional linear shape space around a template, $\mathbf{Q} = W\mathbf{X} + \bar{\mathbf{Q}}$, with $W$ of much lower rank than the number of control-point coordinates. Shape spaces came from affine transformations of a template, key frames, or principal component analysis of training outlines.

Learned dynamics. Motion is a second-order linear autoregressive process,

$$\mathbf{x}_t - \bar{\mathbf{x}} = A(\mathbf{x}_{t-1} - \bar{\mathbf{x}}) + B\mathbf{w}_t,$$

where the state $\mathbf{x}_t$ stacks the shape vectors of two consecutive frames and $\mathbf{w}_t$ is standard normal noise, giving damped oscillators driven by random accelerations. $A$, $B$ and $\bar{\mathbf{x}}$ are estimated by maximum likelihood from training sequences, which the authors call essential to the work. Training data typically came from a Kalman-filter tracker run on footage with little clutter, often bootstrapped: a tracker with default dynamics follows part of a sequence, and the model learned from it tracks more.

Observation model. Measurements are high-contrast edges found along a fixed number of normals to the hypothesized curve. Along each normal, the paper models clutter as a Poisson process, the true edge as detected with Gaussian error, and allows the target to be missed. It approximates this by a penalty on the distance to the nearest feature, capped when no feature is close, and multiplies the terms over all normals. The cap lets a good hypothesis survive brief occlusions.

Results

The journal paper reports four experiments; the conference version contains the first three.

• Three people in a cluttered room (70 frames). A tracker designed for one person, with an affine head-and-shoulders template and $N = 1000$, developed a distribution with three peaks, one per person, and kept them through temporary occlusion. The authors note that this gave multi-person tracking for free.
• A dancer against clutter (500 fields, 10 seconds). With only $N = 100$ samples, CONDENSATION followed the head throughout, while a Kalman filter with the same motion model was distracted by clutter after about 0.8 seconds and never recovered. At one point the distribution split into two peaks, the stronger on a background computer screen, and recovered within a few fields, showing that multimodality matters even for one target.
• A flexing hand over a cluttered desk (500 fields), in a 12-dimensional shape space covering finger flexion and palm rotation, with $N = 500$ after a start at 1500.
• A camouflaged leaf on a bush in wind (600 fields), where the background consists of similar leaves. With $N = 1200$ the tracker ran at 6.5 Hz on an SGI Indy workstation; reducing $N$ to 200 reached video rate (25 Hz) at the cost of occasional misalignments.

The results are qualitative: stills, density plots, and centroid trajectories, with no quantitative accuracy benchmark.

Impact

CONDENSATION introduced sample-based Bayesian tracking to computer vision and is widely cited. It showed on real video that a tracker can keep several hypotheses alive through clutter at near frame rate, and later vision trackers kept its loop of resampling, prediction, and reweighting while changing the models inside it.

The PAMI Technical Committee lists the conference paper as one of two ECCV 1996 best papers, alongside Cham and Cipolla’s paper on symmetric contours. The European Computer Vision Association lists it as a 2008 Koenderink Prize winner, together with Faugeras, Luong and Maybank’s ECCV 1992 paper on camera self-calibration.

Limitations

• Hand-specified observation model. The authors note that the observation density is assumed rather than learned, and that treating its normalizing factor as independent of the state is an unverified assumption.
• Sampling efficiency. Factored sampling becomes inefficient when the observation density has narrow peaks, and 100 samples cannot cover a broad initial distribution, so the dancer was initialized by hand. Importance sampling is raised as a remedy, with the difficulty that the prediction can only be sampled, not evaluated pointwise.
• Summarizing the density. For multimodal distributions the mean outline is not a useful estimate; the paper calls for mode finders and other ways to query sample sets.
• Dependence on learned dynamics. Every experiment relies on motion models trained on representative, preferably clutter-free sequences, often in several bootstrap stages.
• Dimensionality. The experiments stop at 12 dimensions, and the paper does not examine how the required $N$ grows beyond that, a general weakness of particle filters (see the particle filter article).

What Came After

Isard and Blake addressed sampling efficiency in ICONDENSATION (ECCV 1998), which added importance sampling: a fast color segmentation found skin-colored blobs that guided where samples were placed, while the contour model supplied fine shape detail. Their hand tracker ran in real time and reinitialized automatically. The conclusion’s suggestion of mixed discrete and continuous states, switching between motion models, became their mixed-state tracker at ICCV 1998.

Later trackers replaced edge measurements with other likelihoods. Pérez, Hue, Vermaak and Gangnet (2002) placed a color-histogram distance inside a particle filter to cope with background color clutter and brief complete occlusions, and color- and appearance-based particle trackers became common in object tracking. The particle filter article covers the method as understood today and its uses beyond vision.