An accessible yet rigorous exposition of particle filtering and the condensation algorithm.

An accessible yet rigorous exposition of particle filtering and the condensation algorithm.

1 Introduction and background.- 1.1 Overview.- 1.2 Active contours for visual tracking.- 2 The Condensation algorithm.- 2.1 The basic idea.- 2.2 Formal definitions.- 2.3 Operations on particle sets.- 2.4 The Condensation theorem.- 2.5 The relation to factored sampling, or "where did the proof go?".- 2.6 "Good" particle sets and the effective sample size.- 2.7 A brief history of Condensation.- 2.8 Some alternatives to Condensation.- 3 Contour likelihoods.- 3.1 A generative model for image features.- 3.2 Background models and the selection of measurement lines.- 3.3 A continuous analogue of the contour likelihood ratio.- 4 Object localisation and tracking with contour likelihoods.- 4.1 A brief survey of object localisation.- 4.2 Object localisation by factored sampling.- 4.3 Estimating the number of targets.- 4.4 Learning the prior.- 4.5 Random sampling: some traps for the unwary.- 4.6 Tracker initialisation by factored sampling.- 4.7 Tracking using Condensation and the contour likelihoods.- 5 Modelling occlusions using the Markov likelihood.- 5.1 Detecting occluded objects.- 5.2 The problem with the independence assumption.- 5.3 The Markov generative model.- 5.4 Prior for occlusions.- 5.5 Realistic assessment of multiple targets.- 5.6 Improved discrimination with a single target.- 5.7 Faster convergence using importance sampling.- 5.8 Random samples using MelvIe.- 5.9 Calculating the partition functions.- 5.10 Further remarks.- 6 A probabilistic exclusion principle for multiple objects.- 6.1 Introduction.- 6.2 A generative model with an exclusion principle.- 6.3 Tracking multiple wire-frame objects.- 6.4 Tracking multiple opaque objects.- 7 Partitioned sampling.- 7.1 The need for partitioned sampling.- 7.2 Weighted resampling.- 7.3 Basic partitioned sampling.-7.4 Branched partitioned sampling.- 7.5 Performance of partitioned sampling.- 7.6 Partitioned sampling for articulated objects.- 8 Conelusion?.- Appendix A.- A.1 Measures and Metrics on the configuration space.- A.2 Proof of the interior-exterior likelihood.- A.3 Del Moral's resampling lemma and its consequences.- Appendix B.- B.1 Summary Of Notation.

A central problem in computer vision is to track objects as they move and deform in a video sequence. Stochastic algorithms -- in particular, particle filters and the Condensation algorithm -- have dramatically enhanced the state of the art for such visual tracking problems in recent years. This book presents a unified framework for visual tracking using particle filters, including the new technique of partitioned sampling which can alleviate the "curse of dimensionality" suffered by standard particle filters. The book also introduces the notion of contour likelihood: a collection of models for assessing object shape, colour and motion, which are derived from the statistical properties of image features. Because of their statistical nature, contour likelihoods are ideal for use in stochastic algorithms. A unifying theme of the book is the use of statistics and probability, which enable the final output of the algorithms presented to be interpreted as the computer's "belief" about the state of the world. The book will be of use and interest to students, researchers and practitioners in computer vision, and assumes only an elementary knowledge of probability theory.