Abstract
Interacting and annealing are two powerful strategies that are applied in different areas of stochastic modelling and data analysis. Interacting particle systems approximate a distribution of interest by a finite number of particles where the particles interact between the time steps. In computer vision, they are commonly known as particle filters. Simulated annealing, on the other hand, is a global optimization method derived from statistical mechanics. A recent heuristic approach to fuse these two techniques for motion capturing has become known as annealed particle filter. In order to analyze these techniques, we rigorously derive in this paper two algorithms with annealing properties based on the mathematical theory of interacting particle systems. Convergence results and sufficient parameter restrictions enable us to point out limitations of the annealed particle filter. Moreover, we evaluate the impact of the parameters on the performance in various experiments, including the tracking of articulated bodies from noisy measurements. Our results provide a general guidance on suitable parameter choices for different applications.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alspach, D., Sorenson, H.: Nonlinear Bayesian estimation using Gaussian sum approximations. IEEE Trans. Autom. Control 17(4), 439–448 (1972)
Chigansky, P., Liptser, R.: Stability of nonlinear filters in nonmixing case. Ann. Appl. Probab. 14(4), 2038–2056 (2004)
Crisan, D., Doucet, A.: A survey of convergence results on particle filtering methods for practitioners. IEEE Trans. Signal Process. 50(3), 736–746 (2002)
Crisan, D., Grunwald, M.: Large deviation comparison of branching algorithms versus resampling algorithms: application to discrete time stochastic filtering. Technical report, Statistical Laboratory, Cambridge University, UK, 1999
Crisan, D., Del Moral, P., Lyons, T.: Discrete filtering using branching and interacting particle systems. Markov Process. Relat. Fields 5(3), 293–319 (1999)
Deutscher, J., Blake, A., Reid, I.: Articulated body motion capture by annealed particle filtering. In: Proc. Conf. Computer Vision and Pattern Recognition, vol. 2, pp. 1144–1149 (2000)
Deutscher, J., Reid, I.: Articulated body motion capture by stochastic search. Int. J. Comput. Vis. 61(2), 185–205 (2005)
Doucet, A., de Freitas, N., Gordon, N. (eds.): Sequential Monte Carlo Methods in Practice. Springer, New York (2001)
Gall, J., Rosenhahn, B., Brox, T., Seidel, H.-P.: Learning for multi-view 3d tracking in the context of particle filters. In: Int. Symposium on Visual Computing (ISVC). Lecture Notes in Computer Science, vol. 4292, pp. 59–69. Springer, Berlin (2006)
Gidas, B.: Metropolis-type Monte Carlo simulation algorithms and simulated annealing. In: Topics in Contemporary Probability and Its Applications, pp. 159–232. CRC Press, Boca Raton (1995)
Le Gland, F., Oudjane, N.: Stability and uniform approximation of nonlinear filters using the Hilbert metric and application to particle filters. Ann. Appl. Probab. 14(1), 144–187 (2004)
Gordon, N., Salmond, D., Smith, A.: Novel approach to non-linear/non-Gaussian bayesian state estimation. IEE Proc. F 140(2), 107–113 (1993)
Hammersley, J., Handscomb, D.: Monte Carlo Methods. Methuen, London (1967)
Hastings, W.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97–109 (1970)
Isard, M., Blake, A.: Contour tracking by stochastic propagation of conditional density. In: Proc. European Conf. on Computer Vision, vol. 1, pp. 343–356 (1996)
Jazwinski, A.: Stochastic Processes and Filtering Theory. Academic Press, London (1970)
Julier, S., Uhlmann, J.: A new extension of the Kalman filter to nonlinear systems. In: Int. Symposium on Aerospace/Defence Sensing, Simulation and Controls (1997)
Kalman, R.: A new approach to linear filtering and prediction problems. J. Basic Eng. 82, 35–45 (1960)
Kanazawa, K., Koller, D., Russell, S.: Stochastic simulation algorithms for dynamic probabilistic networks. In: Proc. of the Eleventh Annual Conf. on Uncertainty in AI (UAI), pp. 346–351 (1995)
Kirkpatrick, S., Gelatt, C. Jr., Vecchi, M.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Kitagawa, G., Gersch, W.: Smoothness Priors Analysis of Time Series. Lecture Notes in Statistics, vol. 116. Springer, New York (1996)
MacCormick, J.: Probabilistic models and stochastic algorithms for visual tracking. PhD thesis, University of Oxford (2000)
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E.: Equations of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087–1092 (1953)
Del Moral, P.: Nonlinear filtering: Interacting particle solution. Markov Process. Relat. Fields 2(4), 555–580 (1996)
Del Moral, P.: Measure-valued processes and interacting particle systems. Application to nonlinear filtering problems. Ann. Appl. Probab. 8(2), 438–495 (1998)
Del Moral, P.: Feynman–Kac Formulae. Genealogical and Interacting Particle Systems with Applications. Springer, New York (2004)
Del Moral, P., Doucet, A.: On a class of genealogical and interacting metropolis models. In: Séminaire de Probabilités XXXVII. Lecture Notes in Mathematics, vol. 1832. Springer, New York (2003)
Del Moral, P., Guionnet, A.: On the stability of interacting processes with applications to filtering and genetic algorithms. Ann. Inst. Henri Poincaré, B Probab. Stat. 37(2), 155–194 (2001)
Del Moral, P., Miclo, L.: Branching and interacting particle systems approximations of Feynman–Kac formulae with applications to nonlinear filtering. In: Séminaire de Probabilités XXXIV. Lecture Notes in Mathematics, vol. 1729, pp. 1–145. Springer, New York (2000)
Del Moral, P., Miclo, L.: Annealed Feynman–Kac models. Commun. Math. Phys. 235, 191–214 (2003)
Neal, R.: Annealed importance sampling. Stat. Comput. 11, 125–139 (2001)
Robert, C., Casella, G.: Monte Carlo Statistical Methods. Springer, New York (2002)
Rogers, L., Williams, D.: Diffusions, Markov Processes and Martingales, vol. 1, 2nd edn. Cambridge University Press, Cambridge (2001)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gall, J., Potthoff, J., Schnörr, C. et al. Interacting and Annealing Particle Filters: Mathematics and a Recipe for Applications. J Math Imaging Vis 28, 1–18 (2007). https://doi.org/10.1007/s10851-007-0007-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-007-0007-8