Skip to main content
SpringerLink
Log in

A review of statistical data association techniques for motion correspondence

  • Published:
International Journal of Computer Vision Aims and scope Submit manuscript

Abstract

Motion correspondence is a fundamental problem in computer vision and many other disciplines. This article describes statistical data association techniques originally developed in the context of target tracking and surveillance and now beginning to be used in dynamic motion analysis by the computer vision community. The Mahalanobis distance measure is first introduced before discussing the limitations of nearest neighbor algorithms. Then, the track-splitting, joint likelihood, multiple hypothesis algorithms are described, each method solving an increasingly more complicated optimization. Real-time constraints may prohibit the application of these optimal methods. The suboptimal joint probabilistic data association algorithm is therefore described. The advantages, limitations, and relationships between the approaches are discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. N. Ayache and O. Faugeras, Maintaining representations of the environment of a mobile robot,IEEE Trans. Robotics Autom. 5(6): 804–819, 1989.

    Google Scholar 

  2. H.A.P. Blom, R.A. Hogendoorn, and B.A. van Doorn, Design of a multisensor tracking system for advanced air traffic control. In Y. Bar-Shalom, ed.,Multitarget-Multisensor Tracking: Advanced Applications. Artech House: Norwood, MA, vol. 2, pp. 31–63, 1992.

    Google Scholar 

  3. Y. Bar-Shalom, K.C. Chang, and H.A.P. Blom, Automatic track formation in clutter with a recursive algorithm. In Y. Bar-Shalom, ed.,Multitarget-Multisensor Tracking: Advanced Applications, Artech House: Norwood, MA, pp. 25–42, 1990.

    Google Scholar 

  4. Y. Bar-Shalom, K.C. Chang, and H.A.P. Blom, Tracking splitting targets in clutter by using an interacting multiple model joint probabilistic data association filter. In Y. Bar-Shalom, ed.,Multitarget-Multisensor Tracking: Advanced Applications, Artech House: Norwood, MA, vol. 2, pp. 93–110, 1992.

    Google Scholar 

  5. Y. Bar-Shalom and T.E. Fortmann,Tracking and Data Association, Academic Press: San Diego, CA, 1988.

    Google Scholar 

  6. Y. Bar-Shalom and A.G. Jaffer, Adaptive nonlinear filtering for tracking with measurements of uncertain origin,Proc. 11th IEEE Conf. on Decision and Control, pp. 243–247, 1972.

  7. Y.L. Chang and J.K. Aggarwal, 3d structure reconstruction from an ego motion sequence using statistical estimation and detection theory,IEEE Workshop in Visual Motion, pp. 268–273, 1991.

  8. I.J. Cox and J.J. Leonard, Probabilistic data association for dynamic world modeling: A multiple hypothesis appraoch,Proc. Intern. Conf. Advanced Robotics, Pisa, Italy, 1991.

  9. I.J. Cox and J.J. Leonard, Unsupervised learning for mobile robot navigation using probabilistic data association,Workshop on Computer Learning and Natural Learning, Berkeley, CA, 1991.

  10. I.J. Cox, J.M. Rehg, and S. Hingorani, A Bayesian multiple hypothesis approach to contour segmentation,Proc. 2nd Europ. Conf. Comput. Vis., pp. 72–77, Italy, 1992.

  11. J.L. Crowley, P. Stelmaszyk, and C. Discours, Measuring image flow by tracking edge-lines,Proc. Intern. Conf. Comput. Vis., pp. 658–664, Tampa, FL, 1988.

  12. J.B. Collins and J.K. Uhlmann, Efficient gating in data association with multivariate Gaussian distributions,NRL, 1992.

  13. M.R.W. Dawson, The how and why of what went where in apparent motion: Modeling solutions to the motion correspondence problem,Psychological Review 98(4): 569–603, 1991.

    Google Scholar 

  14. R. Deriche and O. Faugeras, Tracking line segments. In O. Faugeras, ed.,Proc. Europ. Conf. Comput. Vis., pp. 259–268. Springer-Verlag: New York, 1990.

    Google Scholar 

  15. R.O. Duda and P.E. Hart.Pattern Classification and Scene Analysis. Wiley: New York, 1973.

    Google Scholar 

  16. T.E. Fortmann, Y. Bar-Shalom, and M. Scheffe, Sonar tracking of multiple targets using joint probabilistic data association,IEEE J. Ocean. Engineer. OE-8(3): 173–184, 1983.

    Google Scholar 

  17. M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman: New York, 1979.

    Google Scholar 

  18. R.W. Hockney and J.W. Eastwood,Computer Simulation Using Particles. Adam Hilger: Bristol, UK, 1988.

    Google Scholar 

  19. T. Kurien, Issues in the design of practical multitarget tracking algorithms. In Y. Bar-Shalom, ed.,Multitarget-Multisensor Tracking: Advanced Applications, pp. 43–83, Artech House: Norwood, MA, 1990.

    Google Scholar 

  20. J.E.W. Mayhew and J.P. Frisby, Psychophysical and computational studies towards a theory of human stereopsis,Artificial Intelligence, 17, 1981.

  21. C.L. Morefield, Application of 0-1 interger programming to multitarget tracking problems,IEEE Trans. Autom. Contr. AC-22(6), June 1977.

  22. M.J.L. Orr, J. Hallam, and R.B. Fisher, Fusion through interpretation. In G. Sandini, ed.,Second European Conference on Computer Vision, pp. 801–805. Springer-Verlag: New York, 1992.

    Google Scholar 

  23. F.P. Preparata and M.I. Shamos,Computational Geometry: An Introduction. Springer-Verlag: New York, 1985.

    Google Scholar 

  24. D.B. Reid, An algorithm for tracking multiple targets.IEEE Trans. Autom. Contr. AC-24(6): 843–854, December 1979.

    Google Scholar 

  25. I. Rock and S. Palmer, The legacy of gestalt psychology,Scientific American 263(6): 84–90, December 1990.

    Google Scholar 

  26. H.M. Salkin,Integer Programming. Addison-Wesley: Reading, MA, 1975.

    Google Scholar 

  27. P. Smith and G. Buechler, A branching algorithm for discriminating and tracking multiple objects,IEEE Trans. Autom. Contr. AC-20: 101–104, 1975.

    Google Scholar 

  28. C.W. Therrien,Decision Estimation and Classification: An Introduction to Pattern Recognition and Related Topics. Wiley: New York, 1989.

    Google Scholar 

  29. J.K. Uhlmann, Adaptive partitioning strategies for ternary tree structures,Patt. Recog. Ltts. 12: 537–541, 1991.

    Google Scholar 

  30. J.K. Uhlmann, Satisfying general proximity/similarity queries with metric trees, Inform. Process. Ltts. 40: 175–179, 1991.

    Google Scholar 

  31. J.K. Uhlmann, Algorithms for multiple-target tracking.American Scientist 80: 128–141, 1992.

    Google Scholar 

  32. Z. Zhang and O.D. Faugeras, Three-dimensional motion computation and object segmentation in a long sequence of stereo frames,Intern. J. Comput. Vis. 7(3): 211–241, 1992.

    Google Scholar 

  33. B. Zhou,Multitarget Tracking in Clutter: Algorithms for Data Association and State Estimation. Ph.D. thesis, Pennsylvania State University, 1992.

Download references

Author information

Authors and Affiliations

  1. NEC Research Institute, 4 Independence Way, 08540, Princeton, NJ

    Ingemar J. Cox

Authors
  1. Ingemar J. Cox
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cox, I.J. A review of statistical data association techniques for motion correspondence. Int J Comput Vision 10, 53–66 (1993). https://doi.org/10.1007/BF01440847

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01440847

Keywords

Search

Navigation