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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
N. Ayache and O. Faugeras, Maintaining representations of the environment of a mobile robot,IEEE Trans. Robotics Autom. 5(6): 804–819, 1989.
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.
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.
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.
Y. Bar-Shalom and T.E. Fortmann,Tracking and Data Association, Academic Press: San Diego, CA, 1988.
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.
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.
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.
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.
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.
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.
J.B. Collins and J.K. Uhlmann, Efficient gating in data association with multivariate Gaussian distributions,NRL, 1992.
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.
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.
R.O. Duda and P.E. Hart.Pattern Classification and Scene Analysis. Wiley: New York, 1973.
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.
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman: New York, 1979.
R.W. Hockney and J.W. Eastwood,Computer Simulation Using Particles. Adam Hilger: Bristol, UK, 1988.
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.
J.E.W. Mayhew and J.P. Frisby, Psychophysical and computational studies towards a theory of human stereopsis,Artificial Intelligence, 17, 1981.
C.L. Morefield, Application of 0-1 interger programming to multitarget tracking problems,IEEE Trans. Autom. Contr. AC-22(6), June 1977.
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.
F.P. Preparata and M.I. Shamos,Computational Geometry: An Introduction. Springer-Verlag: New York, 1985.
D.B. Reid, An algorithm for tracking multiple targets.IEEE Trans. Autom. Contr. AC-24(6): 843–854, December 1979.
I. Rock and S. Palmer, The legacy of gestalt psychology,Scientific American 263(6): 84–90, December 1990.
H.M. Salkin,Integer Programming. Addison-Wesley: Reading, MA, 1975.
P. Smith and G. Buechler, A branching algorithm for discriminating and tracking multiple objects,IEEE Trans. Autom. Contr. AC-20: 101–104, 1975.
C.W. Therrien,Decision Estimation and Classification: An Introduction to Pattern Recognition and Related Topics. Wiley: New York, 1989.
J.K. Uhlmann, Adaptive partitioning strategies for ternary tree structures,Patt. Recog. Ltts. 12: 537–541, 1991.
J.K. Uhlmann, Satisfying general proximity/similarity queries with metric trees, Inform. Process. Ltts. 40: 175–179, 1991.
J.K. Uhlmann, Algorithms for multiple-target tracking.American Scientist 80: 128–141, 1992.
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.
B. Zhou,Multitarget Tracking in Clutter: Algorithms for Data Association and State Estimation. Ph.D. thesis, Pennsylvania State University, 1992.
Author information
Authors and Affiliations
Rights 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
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01440847