FACTOID # 8: Bookworms: Vermont has the highest number of high school teachers per capita and third highest number of librarians per capita.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > 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 you might imagine, tracking a red ball bouncing around on a white background is a fairly easy problem. As scenes get more complex, tracking the object becomes increasingly difficult. Condensation is a probabilistic algorithm that proposes a solution to this problem. Computer vision is the study and application of methods which allow computers to understand image content or content of multidimensional data in general. ... A randomized algorithm is an algorithm which is allowed to flip a truly random coin. ...

The algorithm itself is described in detail in Isard and Blake published 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.

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

Result of particle filtering (red line) based on observed data generated from the blue line ( Much larger image) Particle filter methods, also known as Sequential Monte Carlo (SMC), are sophisticated model estimation techniques based on simulation. ...

## References

Condensation homepage

Results from FactBites:

 Density Propagation (339 words) The most obvious difficulties of the visual tracking lie in modeling the uncertainty of the shape - or the probability density of the "state", which is commonly used in the control community. Kalman filtering deals with the uncertainty of the state by carrying the covariance matrices of the states and the measurements, and it works optimally when the noise is Gaussian. CONDENSATION algorithm is one simulation method, which works very well even in the severe visual clutter in the image.
More results at FactBites »

Share your thoughts, questions and commentary here