Quarterly of Applied Mathematics

Quarterly of Applied Mathematics

Online ISSN 1552-4485; Print ISSN 0033-569X



Model-based tracking of moving objects in cluttered environments

Authors: Basilis Gidas, Fernando Carvalho Gomes and Christopher Robertson
Journal: Quart. Appl. Math. 60 (2002), 737-771
MSC: Primary 68T45; Secondary 62H35
DOI: https://doi.org/10.1090/qam/1939009
MathSciNet review: MR1939009
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We explore a coherent statistical/Bayesian framework for tracking rigid or non-rigid objects in highly cluttered environments. The procedure involves three basic models: (i) an object representation, (ii) a dynamic model, and (iii) a data or observation model. We employ two object representations -- deformable templates, and a hierarchical/syntactic model; the deformations of the template are parametrized by a finite number of global parameters viewed as generalized coordinates of the model; they determine the state space of the tracking problem. The dynamic model describes the evolution of the generalized coordinates (or the corresponding state vector); our dynamic model is a non-Gaussian Markov chain whose transition probabilities are derived from Lagrangian mechanics. We introduce two data models: one nonlinear and one linear (Gaussian); the design of the two models uses different image processing techniques. The nonlinear filtering problem induced by three models is solved both by the Extended Kalman Filter (EKF), and an iterative algorithm--to be referred to as the Monte Carlo Filter (MCF)-- introduced in the statistic literature and first employed in Computer Vision by Blake and Isard. We present several tracking experiments with real video sequences. In each experiment we implement both MCF and EKF, and their performances are compared. Overall, we find that MCF is more robust than EKF in situations with considerable clutter and/or occlusions, but EKF is comparable and sometimes more accurate than MCF in situations with less occlusion and degradation. Our studies also demonstrate that when the motion has sharp discontinuities in direction, nonlinearities in the dynamic model are key for successful tracking; put differently, the deficiencies of linear dynamics models cannot be easily compensated with more sophisticated data models.

References [Enhancements On Off] (What's this?)

  • [1] Brian D. O. Anderson and John B. Moore. Optimal Filtering. Prentice-Hall, 1979.
  • [2] Andrew Blake, Rupert Curwen, and Andrew Zisserman. A framework for spatio-temporal control in the tracking of visual contours, Int. J. Computer Vision, 11(2):127-145, 1993.
  • [3] Andrew Blake and Michael Isard. Active Contours. Springer-Verlag, 1998.
  • [4] R. Bajcsy and D. Jones. Multiresolution Elastic Matching, Computer Vision, Graphics, and Image Processing, 48, 1-21, 1989.
  • [5] Andrew Blake, Michael Isard, and David Reynard. Learning to track the visual motion of contours, Artificial Intelligence, 78:101-133, 1995.
  • [6] Arthur P. Boresi and Ken P. Chong. Elasticity in Engineering Mechanics. Elsevier Science Publishing Co., 1987.
  • [7] James Carpenter, Peter Clifford, and Paul Fearnhead. An Improved Particle Filter for Non-Linear Problems, IEE Proceedings - Radar, Sonar, and Navigation, 146(1), 2-7, 1999.
  • [8] P. Del Moral, Measure-valued processes and interacting particle systems. Application to nonlinear filtering problems, Ann. Appl. Probab. 8 (1998), no. 2, 438–495. MR 1624949, https://doi.org/10.1214/aoap/1028903535
  • [9] Robert J. Elliott, Lakhdar Aggoun, and John B. Moore, Hidden Markov models, Applications of Mathematics (New York), vol. 29, Springer-Verlag, New York, 1995. Estimation and control. MR 1323178
  • [10] Arthur Gelb (ed.), Applied optimal estimation, The MIT Press, Cambridge, Mass.-London, 1974. Written by the technical staff of The Analytic Sciences Corporation; Principal authors: Arthur Gelb, Joseph F. Kasper, Jr., Raymond A. Nash, Jr., Charles F. Price and Arthur A. Sutherland, Jr. MR 0345688
  • [11] Stuart Geman and Donald Geman. Stochastic Relaxation, Gibbs Distribution, and Bayesian Restoration of Images, IEEE Trans. PAMI, 6, 721-741, 1984.
  • [12] Jean Dickinson Gibbons and Subhabrata Chakraborti, Nonparametric statistical inference, 3rd ed., Statistics: Textbooks and Monographs, vol. 131, Marcel Dekker, Inc., New York, 1992. MR 1259049
  • [13] N. J. Gordon, D. J. Salmond, and A. F. M. Smith. Novel approach to nonlinear/non-Gaussian Bayesian state estimation, IEE Proceedings-F, 140(2):107-113, April 1993.
  • [14] Ulf Grenander, General pattern theory, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1993. A mathematical study of regular structures; Oxford Science Publications. MR 1270904
  • [15] Michael Isard. Visual Motion Analysis by Probabilistic Propagation of Conditional Density. Ph.D. Thesis 1998, Department of Engineering Science, Oxford University.
  • [16] Michael Isard and Andrew Blake. Contour tracking by stochastic propagation of conditional density, In Proc. European Conf. on Computer Vision, pages 343-356, 1996.
  • [17] Genshiro Kitagawa, Monte Carlo filter and smoother for non-Gaussian nonlinear state space models, J. Comput. Graph. Statist. 5 (1996), no. 1, 1–25. MR 1380850, https://doi.org/10.2307/1390750
  • [18] John MacCormick. Probabilistic Modeling and Stochastic Algorithms for Visual Localisation and Tracking, Ph.D. Thesis 2000, Department of Engineering Science, Oxford University.
  • [19] M. I. Miller, A. Srivastava, and U. Grenander. Conditional-expectation estimation via jump-diffusion processes in multiple target tracking/recognition, IEEE Transactions on Signal Processing, 43(ll):2678-2690, November 1995.
  • [20] Christopher Raphael and Stuart Geman. A grammatical approach to mine detection, SPIE Proceedings, Vol. 3079, 1997, pp. 316-332, Eds.: A. C. Dubey and R. L. Bamard.
  • [21] Christopher Nils Robertson, Tracking of objects from image sequences using Lagrangian dynamics and nonlinear filtering, ProQuest LLC, Ann Arbor, MI, 1998. Thesis (Ph.D.)–Brown University. MR 2697374
  • [22] Reinhardt M. Rosenberg, Analytical dynamics of discrete systems, Mathematical Concepts and Methods in Science and Engineering, vol. 4, Plenum Press, New York-London, 1977. MR 512893
  • [23] D. B. Rubin. Using the SIR Algorithm to Simulate Posterior Distributions, in Bayesian Statistics, 3, pp. 395-402, Oxford University Press, 1998, Eds.: J. M. Bernado, M. H. DeGroot, D. V. Lindley, and A. F. M. Smith.
  • [24] Ahmed A. Shabana, Dynamics of multibody systems, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. MR 1020760
  • [25] Ahmed A. Shabana. Variation of Discrete and Continuous Systems. Springer-Verlag, 1997.
  • [26] Demetri Terzopoulos and Dimitri Metaxas. Dynamic 3D models with local and global deformations: deformable superquadrics, IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(7):703-714, July 1991.
  • [27] Demetri Terzopoulos and Dimitri Metaxas. Tracking nonrigid 3D objects. In Andrew Blake and Alan Yuille, editors, Active Vision, chapter 5, pages 75-89. The M.I.T. Press, 1992.
  • [28] Demetri Terzopoulos and Richard Szeliski. Tracking with Kalman snakes. In Andrew Blake and Alan Yuille, editors, Active Vision, chapter 1, pages 3-20. The M.I.T. Press, 1992.
  • [29] Demetri Terzopoulos and Keith Waters. Analysis and synthesis of facial image sequences using physical and anatomical models, IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(6):569-579, June 1993.

Similar Articles

Retrieve articles in Quarterly of Applied Mathematics with MSC: 68T45, 62H35

Retrieve articles in all journals with MSC: 68T45, 62H35

Additional Information

DOI: https://doi.org/10.1090/qam/1939009
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society