OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 19, Iss. 8 — Apr. 11, 2011
  • pp: 7646–7663

Automated 3D trajectory measuring of large numbers of moving particles

Hai Shan Wu, Qi Zhao, Danping Zou, and Yan Qiu Chen  »View Author Affiliations

Optics Express, Vol. 19, Issue 8, pp. 7646-7663 (2011)

View Full Text Article

Enhanced HTML    Acrobat PDF (4515 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



Complex dynamics of natural particle systems, such as insect swarms, bird flocks, fish schools, has attracted great attention of scientists for years. Measuring 3D trajectory of each individual in a group is vital for quantitative study of their dynamic properties, yet such empirical data is rare mainly due to the challenges of maintaining the identities of large numbers of individuals with similar visual features and frequent occlusions. We here present an automatic and efficient algorithm to track 3D motion trajectories of large numbers of moving particles using two video cameras. Our method solves this problem by formulating it as three linear assignment problems (LAP). For each video sequence, the first LAP obtains 2D tracks of moving targets and is able to maintain target identities in the presence of occlusions; the second one matches the visually similar targets across two views via a novel technique named maximum epipolar co-motion length (MECL), which is not only able to effectively reduce matching ambiguity but also further diminish the influence of frequent occlusions; the last one links 3D track segments into complete trajectories via computing a globally optimal assignment based on temporal and kinematic cues. Experiment results on simulated particle swarms with various particle densities validated the accuracy and robustness of the proposed method. As real-world case, our method successfully acquired 3D flight paths of fruit fly (Drosophila melanogaster) group comprising hundreds of freely flying individuals.

© 2011 Optical Society of America

OCIS Codes
(110.6880) Imaging systems : Three-dimensional image acquisition
(120.0120) Instrumentation, measurement, and metrology : Instrumentation, measurement, and metrology
(150.6910) Machine vision : Three-dimensional sensing
(100.4999) Image processing : Pattern recognition, target tracking

ToC Category:
Imaging Systems

Original Manuscript: November 22, 2010
Revised Manuscript: January 16, 2011
Manuscript Accepted: January 23, 2011
Published: April 6, 2011

Virtual Issues
Vol. 6, Iss. 5 Virtual Journal for Biomedical Optics

Hai Shan Wu, Qi Zhao, Danping Zou, and Yan Qiu Chen, "Automated 3D trajectory measuring of large numbers of moving particles," Opt. Express 19, 7646-7663 (2011)

Sort:  Author  |  Year  |  Journal  |  Reset  


  1. T. Vicsek, and A. Zafiris, "Collective motion," Arxiv preprint arXiv:1010.5017 (2010).
  2. C. Reynolds, "Flocks, herds and schools: A distributed behavioral model," Comput. Graph. 21, 25-34 (1987). [CrossRef]
  3. T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, and O. Shochet, "Novel type of phase transition in a system of self-driven particles," Phys. Rev. Lett. 75, 1226-1229 (1995). [CrossRef] [PubMed]
  4. I. Couzin, "Collective cognition in animal groups," Trends Cogn. Sci. 13, 36-43 (2009). [CrossRef]
  5. M. Nagy, Z. Ákos, D. Biro, and T. Vicsek, "Hierarchical group dynamics in pigeon flocks," Nature 464, 890-893 (2010). [CrossRef] [PubMed]
  6. H. Hirschmuller, and D. Scharstein, "Evaluation of Cost Functions for Stereo Matching," in IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (2007), pp. 1-8.
  7. C. Rasmussen, and G. Hager, "Probabilistic data association methods for tracking complex visual objects," IEEE Trans. Pattern Anal. Mach. Intell. 23, 560-576 (2001). [CrossRef]
  8. I. Cox, and S. Hingorani, "An efficient implementation of Reid’s multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking," IEEE Trans. Pattern Anal. Mach. Intell. 18, 138-150 (2002). [CrossRef]
  9. Z. Khan, T. Balch, and F. Dellaert, "MCMC data association and sparse factorization updating for real time multitarget tracking with merged and multiple measurements," IEEE Trans. Pattern Anal. Mach. Intell. 28, 1960-1972 (2006). [CrossRef] [PubMed]
  10. A. Cavagna, A. Cimarelli, I. Giardina, G. Parisi, R. Santagati, F. Stefanini, and M. Viale, "Scale-free correlations in starling flocks," Proc. Natl. Acad. Sci. U.S.A. 107, 11865 (2010). [CrossRef] [PubMed]
  11. Z. Wu, N. I. Hristov, T. L. Hedrick, T. H. Kunz, and M. Betke, "Tracking a Large Number of Objects from Multiple Views," in IEEE 11th International Conference on Computer Vision, (2009), vol. 1.
  12. Anonymous, "No fruit fly an island?" Nat. Methods 6, 395 (2009). [PubMed]
  13. K. Branson, A. Robie, J. Bender, P. Perona, and M. Dickinson, "High-throughput ethomics in large groups of Drosophila," Nat. Methods 6, 451-457 (2009). [CrossRef] [PubMed]
  14. H. Dankert, L. Wang, E. Hoopfer, D. Anderson, and P. Perona, "Automated monitoring and analysis of social behavior in Drosophila," Nat. Methods 6, 297-303 (2009). [CrossRef] [PubMed]
  15. S. Fry, N. Rohrseitz, A. Straw, and M. Dickinson, "TrackFly: Virtual reality for a behavioral system analysis in free-flying fruit flies," J. Neurosci. Methods 171, 110-117 (2008). [CrossRef] [PubMed]
  16. G. Maimon, A. Straw, and M. Dickinson, "A simple vision-based algorithm for decision making in flying Drosophila," Curr. Biol. 18, 464-470 (2008). [CrossRef] [PubMed]
  17. D. Grover, J. Tower, and S. Tavaré, "O fly, where art thou? " J. R. Soc. Interface 5, 1181-1191 (2008). [CrossRef] [PubMed]
  18. A. Straw, K. Branson, T. Neumann, and M. Dickinson, "Multi-camera real-time three-dimensional tracking of multiple flying animals," J. R. Soc., Interface (2010). [PubMed]
  19. C. Wang, C. Liang, and C. Lee, "Three-dimensional nanoparticle tracking and simultaneously membrane profiling during endocytosis of living cells," Appl. Phys. Lett. 95, 203702 (2009). [CrossRef]
  20. F. Cheong, B. Krishnatreya, and D. Grier, "Strategies for three-dimensional particle tracking with holographic video microscopy," Opt. Express 18, 13563-13573 (2010). [CrossRef] [PubMed]
  21. M. Piccardi, "Background subtraction techniques: a review," IEEE Trans. Syst. Man Cybern. 4, 3099-3104 (2004).
  22. B. Anderson, J. Moore, and J. Barratt, Optimal filtering, (Prentice-Hall, 1979).
  23. S. Blackman, and R. Popoli, Design and Analysis of Modern Tracking Systems, (Artech House, 1999).
  24. Y. Bar-Shalom, Tracking and Data Association, (Academic Press Professional, 1987).
  25. R. Jonker, and A. Volgenant, "A shortest augmenting path algorithm for dense and sparse linear assignment problems," Computing 38, 325-340 (1987). [CrossRef]
  26. H. Kuhn, P. Haas, I. Ilyas, G. Lohman, and V. Markl, "The Hungarian method for the assignment problem," Masthead 23, 151-210 (1993).
  27. H. Du, D. Zou, and Y. Chen, "Relative Epipolar Motion of Tracked Features for Correspondence in Binocular Stereo," in IEEE 11th International Conference on Computer Vision, (2007), pp. 1-8.
  28. R. Hartley, and A. Zisserman, Multiple View Geometry in Computer Vision, (Cambridge University Press, 2003).
  29. D. Forsyth, and J. Ponce, Computer Vision: a Modern Approach, (Prentice-Hall, 2002).
  30. A. Perera, C. Srinivas, A. Hoogs, and G. Brooksby, "Multi-Object Tracking Through Simultaneous Long Occlusions and Split-Merge Conditions," in IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (2006), vol. 1.
  31. Q. Zhao, and Y. Chen, "High Precision Synchronization Of Video Cameras Using A Single Binary Light Source," J. Electron. Imaging 18, 040501 (2009). [CrossRef]
  32. R. Tsai, "A Versatile Camera Calibration Technique for High-Accuracy 3D Machine Vision Metrology Using Off-the-shelf TV Cameras and Lenses," IEEE J. Robot. Autom. 3, 323-344 (1987). [CrossRef]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited