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.
1 Introduction and background.- 1.1 Overview.- 1.2 Active contours for visual tracking.- 1.2.1 Splines and shape space.- 1.2.2 Dynamical models using auto-regressive processes.- 1.2.3 Measurement methodology.- 2 The Condensation algorithm.- 2.1 The basic idea.- 2.2 Formal definitions.- 2.2.1 Technical detail: convergence of distribution-valued distributions.- 2.2.2 The crucial definition: how a particle set represents a distribution.- 2.3 Operations on particle sets.- 2.3.1 Multiplication by a function.- 2.3.2 Applying dynamics.- 2.3.3 Resampling.- 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.6.1 The survival diagnostic.- 2.6.2 From effective sample size to survival diagnostic.- 2.6.3 Estimating the weight normalisation.- 2.6.4 Effective sample size of a resampled set.- 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.1.1 The generic contour likelihood.- 3.1.2 The Poisson likelihood.- 3.1.3 The interior-exterior likelihood.- 3.1.4 The order statistic likelihood.- 3.1.5 The contour likelihood ratio.- 3.1.6 Results and examples.- 3.2 Background models and the selection of measurement lines.- 3.2.1 Discussion of the background model.- 3.2.2 Independence of measurement lines.- 3.2.3 Selection of measurement lines.- 3.3 A continuous analogue of the contour likelihood ratio.- 3.3.1 The continuous model.- 3.3.2 Likelihoods for HO and HB.- 3.3.3 Problems with the continuous ARP model.- 4 Object localisation and tracking with contour likelihoods.- 4.1 A brief survey of object localisation.- 4.2 Object localisation by factored sampling.- 4.2.1 Results.- 4.2.2 Interpretation of the gradient threshold.- 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.6.1 Kalman filter tracker.- 4.6.2 The Condensation tracker.- 4.7 Tracking using Condensation and the contour likelihoods.- 4.7.1 The robustified colour contour likelihood.- 4.7.2 Implementation of a head tracker.- 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.5.1 Explanation of results.- 5.5.2 Experimental details.- 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.2.1 Description of the generative model.- 6.2.2 Likelihoods derived from the generative model.- 6.2.3 Where does the "exclusion principle" come from?.- 6.2.4 The full likelihood.- 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.- 7.6.1 Results: a vision-based drawing package.- 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.
An accessible yet rigorous exposition of particle filtering and the condensation algorithm.