Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Condensation algorithm
open-in-new
<p>The condensation algorithm (Conditional Density Propagation) is a <a href="/facts/Computer_vision/Tl2Yyk66">computer vision</a> algorithm. The principal application is to detect and <a href="/facts/Video_tracking/nVh8FB3E">track</a> the contour of objects moving in a cluttered environment. Object tracking is one of the more basic and difficult aspects of computer vision and is generally a prerequisite to <a href="/facts/Object_recognition/cdLpak1I">object recognition</a>. Being able to identify which pixels in an image make up the contour of an object is a non-trivial problem. Condensation is a <a href="/facts/Probabilistic_algorithm/Fngl1zgk">probabilistic algorithm</a> that attempts to solve this problem. </p><p>The algorithm itself is described in detail by Isard and <a href="/facts/Andrew_Blake_(scientist)/EzSUgwLn">Blake</a> in a publication in the <i>International Journal of Computer Vision</i> 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 are supported naturally by the probabilistic nature of the approach. The evaluation 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. </p><p>The algorithm’s creation was inspired by the inability of <a href="/facts/Kalman_filtering/wNK7rnbk">Kalman filtering</a> to perform object tracking well in the presence of significant background clutter. The presence of clutter tends to produce probability distributions for the object state which are <a href="/facts/Multimodal_distribution/wYBCJ67S">multi-modal</a> and therefore poorly modeled by the Kalman filter. The condensation algorithm in its most general form requires no assumptions about the probability distributions of the object or measurements. </p>