Condensation algorithm

The condensation algorithm (Conditional Density Propagation) is a computer vision algorithm. The principle application is to segment and track moving objects in a cluttered background. Image segmentation is one of the more basic and difficult aspects of computer vision and is generally a prerequisite to object recognition. Being able to identify which pixels in an image make up various objects is a non-trivial problem. As one might imagine, tracking a red ball bouncing around on a white background is a fairly easy problem. As scenes become more complex, however, tracking an object becomes increasingly difficult. Condensation is a probabilistic algorithm that provides a solution to this problem.

The algorithm itself is described in detail by Isard and Blake in a publication in the International Journal of Computer Vision in 1998. One of the most interesting facets of the algorithm is that it does not compute on every pixel of the image. Rather, pixels to process are chosen at random, and only a subset of the pixels end up being processed. Multiple hypotheses about what is moving where are supported naturally by the probabilistic nature of the approach. The evalution functions come largely from previous work in the area and include many standard statistical approaches. The original part of this work is the application of particle filter estimation techniques.

See also

• Particle filter - Condensation is the application of Sampling Importance Resampling (SIR) estimation to contour tracking

References

Condensation homepage