Abstract

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

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  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]

2010 (3)

M. Nagy, Z. Ákos, D. Biro, and T. Vicsek, "Hierarchical group dynamics in pigeon flocks," Nature 464, 890-893 (2010).
[CrossRef] [PubMed]

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]

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]

2009 (6)

Anonymous, "No fruit fly an island?" Nat. Methods 6, 395 (2009).
[PubMed]

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]

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]

I. Couzin, "Collective cognition in animal groups," Trends Cogn. Sci. 13, 36-43 (2009).
[CrossRef]

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]

Q. Zhao, and Y. Chen, "High Precision Synchronization Of Video Cameras Using A Single Binary Light Source," J. Electron. Imaging 18, 040501 (2009).
[CrossRef]

2008 (3)

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]

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]

D. Grover, J. Tower, and S. Tavaré, "O fly, where art thou? " J. R. Soc. Interface 5, 1181-1191 (2008).
[CrossRef] [PubMed]

2006 (1)

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]

2004 (1)

M. Piccardi, "Background subtraction techniques: a review," IEEE Trans. Syst. Man Cybern. 4, 3099-3104 (2004).

2002 (1)

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]

2001 (1)

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]

1995 (1)

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]

1993 (1)

H. Kuhn, P. Haas, I. Ilyas, G. Lohman, and V. Markl, "The Hungarian method for the assignment problem," Masthead 23, 151-210 (1993).

1987 (3)

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]

R. Jonker, and A. Volgenant, "A shortest augmenting path algorithm for dense and sparse linear assignment problems," Computing 38, 325-340 (1987).
[CrossRef]

C. Reynolds, "Flocks, herds and schools: A distributed behavioral model," Comput. Graph. 21, 25-34 (1987).
[CrossRef]

Ákos, Z.

M. Nagy, Z. Ákos, D. Biro, and T. Vicsek, "Hierarchical group dynamics in pigeon flocks," Nature 464, 890-893 (2010).
[CrossRef] [PubMed]

Anderson, D.

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]

Anonymous,

Anonymous, "No fruit fly an island?" Nat. Methods 6, 395 (2009).
[PubMed]

Balch, T.

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]

Bender, J.

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]

Ben-Jacob, E.

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]

Biro, D.

M. Nagy, Z. Ákos, D. Biro, and T. Vicsek, "Hierarchical group dynamics in pigeon flocks," Nature 464, 890-893 (2010).
[CrossRef] [PubMed]

Branson, K.

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]

Cavagna, A.

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]

Chen, Y.

Q. Zhao, and Y. Chen, "High Precision Synchronization Of Video Cameras Using A Single Binary Light Source," J. Electron. Imaging 18, 040501 (2009).
[CrossRef]

Cheong, F.

Cimarelli, A.

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]

Cohen, I.

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]

Couzin, I.

I. Couzin, "Collective cognition in animal groups," Trends Cogn. Sci. 13, 36-43 (2009).
[CrossRef]

Cox, I.

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]

Czirók, A.

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]

Dankert, H.

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]

Dellaert, F.

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]

Dickinson, M.

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]

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]

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]

Fry, S.

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]

Giardina, I.

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]

Grier, D.

Grover, D.

D. Grover, J. Tower, and S. Tavaré, "O fly, where art thou? " J. R. Soc. Interface 5, 1181-1191 (2008).
[CrossRef] [PubMed]

Haas, P.

H. Kuhn, P. Haas, I. Ilyas, G. Lohman, and V. Markl, "The Hungarian method for the assignment problem," Masthead 23, 151-210 (1993).

Hager, G.

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]

Hingorani, S.

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]

Hoopfer, E.

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]

Ilyas, I.

H. Kuhn, P. Haas, I. Ilyas, G. Lohman, and V. Markl, "The Hungarian method for the assignment problem," Masthead 23, 151-210 (1993).

Jonker, R.

R. Jonker, and A. Volgenant, "A shortest augmenting path algorithm for dense and sparse linear assignment problems," Computing 38, 325-340 (1987).
[CrossRef]

Khan, Z.

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]

Krishnatreya, B.

Kuhn, H.

H. Kuhn, P. Haas, I. Ilyas, G. Lohman, and V. Markl, "The Hungarian method for the assignment problem," Masthead 23, 151-210 (1993).

Lee, C.

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]

Liang, C.

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]

Lohman, G.

H. Kuhn, P. Haas, I. Ilyas, G. Lohman, and V. Markl, "The Hungarian method for the assignment problem," Masthead 23, 151-210 (1993).

Maimon, G.

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]

Markl, V.

H. Kuhn, P. Haas, I. Ilyas, G. Lohman, and V. Markl, "The Hungarian method for the assignment problem," Masthead 23, 151-210 (1993).

Nagy, M.

M. Nagy, Z. Ákos, D. Biro, and T. Vicsek, "Hierarchical group dynamics in pigeon flocks," Nature 464, 890-893 (2010).
[CrossRef] [PubMed]

Parisi, G.

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]

Perona, P.

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]

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]

Piccardi, M.

M. Piccardi, "Background subtraction techniques: a review," IEEE Trans. Syst. Man Cybern. 4, 3099-3104 (2004).

Rasmussen, C.

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]

Reynolds, C.

C. Reynolds, "Flocks, herds and schools: A distributed behavioral model," Comput. Graph. 21, 25-34 (1987).
[CrossRef]

Robie, A.

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]

Rohrseitz, N.

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]

Santagati, R.

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]

Shochet, O.

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]

Stefanini, F.

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]

Straw, A.

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]

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]

Tavaré, S.

D. Grover, J. Tower, and S. Tavaré, "O fly, where art thou? " J. R. Soc. Interface 5, 1181-1191 (2008).
[CrossRef] [PubMed]

Tower, J.

D. Grover, J. Tower, and S. Tavaré, "O fly, where art thou? " J. R. Soc. Interface 5, 1181-1191 (2008).
[CrossRef] [PubMed]

Tsai, R.

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]

Viale, M.

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]

Vicsek, T.

M. Nagy, Z. Ákos, D. Biro, and T. Vicsek, "Hierarchical group dynamics in pigeon flocks," Nature 464, 890-893 (2010).
[CrossRef] [PubMed]

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]

Volgenant, A.

R. Jonker, and A. Volgenant, "A shortest augmenting path algorithm for dense and sparse linear assignment problems," Computing 38, 325-340 (1987).
[CrossRef]

Wang, C.

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]

Wang, L.

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]

Zhao, Q.

Q. Zhao, and Y. Chen, "High Precision Synchronization Of Video Cameras Using A Single Binary Light Source," J. Electron. Imaging 18, 040501 (2009).
[CrossRef]

Appl. Phys. Lett. (1)

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]

Comput. Graph. (1)

C. Reynolds, "Flocks, herds and schools: A distributed behavioral model," Comput. Graph. 21, 25-34 (1987).
[CrossRef]

Computing (1)

R. Jonker, and A. Volgenant, "A shortest augmenting path algorithm for dense and sparse linear assignment problems," Computing 38, 325-340 (1987).
[CrossRef]

Curr. Biol. (1)

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]

IEEE J. Robot. Autom. (1)

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]

IEEE Trans. Pattern Anal. Mach. Intell. (3)

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]

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]

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]

IEEE Trans. Syst. Man Cybern. (1)

M. Piccardi, "Background subtraction techniques: a review," IEEE Trans. Syst. Man Cybern. 4, 3099-3104 (2004).

J. Electron. Imaging (1)

Q. Zhao, and Y. Chen, "High Precision Synchronization Of Video Cameras Using A Single Binary Light Source," J. Electron. Imaging 18, 040501 (2009).
[CrossRef]

J. Neurosci. Methods (1)

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]

J. R. Soc. Interface (1)

D. Grover, J. Tower, and S. Tavaré, "O fly, where art thou? " J. R. Soc. Interface 5, 1181-1191 (2008).
[CrossRef] [PubMed]

Masthead (1)

H. Kuhn, P. Haas, I. Ilyas, G. Lohman, and V. Markl, "The Hungarian method for the assignment problem," Masthead 23, 151-210 (1993).

Nat. Methods (3)

Anonymous, "No fruit fly an island?" Nat. Methods 6, 395 (2009).
[PubMed]

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]

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]

Nature (1)

M. Nagy, Z. Ákos, D. Biro, and T. Vicsek, "Hierarchical group dynamics in pigeon flocks," Nature 464, 890-893 (2010).
[CrossRef] [PubMed]

Opt. Express (1)

Phys. Rev. Lett. (1)

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]

Proc. Natl. Acad. Sci. U.S.A. (1)

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]

Trends Cogn. Sci. (1)

I. Couzin, "Collective cognition in animal groups," Trends Cogn. Sci. 13, 36-43 (2009).
[CrossRef]

Other (11)

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.

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.

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]

T. Vicsek, and A. Zafiris, "Collective motion," Arxiv preprint arXiv:1010.5017 (2010).

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.

R. Hartley, and A. Zisserman, Multiple View Geometry in Computer Vision, (Cambridge University Press, 2003).

D. Forsyth, and J. Ponce, Computer Vision: a Modern Approach, (Prentice-Hall, 2002).

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.

B. Anderson, J. Moore, and J. Barratt, Optimal filtering, (Prentice-Hall, 1979).

S. Blackman, and R. Popoli, Design and Analysis of Modern Tracking Systems, (Artech House, 1999).

Y. Bar-Shalom, Tracking and Data Association, (Academic Press Professional, 1987).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (12)

Fig. 1
Fig. 1

Measuring 3D individual trajectory of large numbers of moving particles is challenging. As red color illustrates, tracking moving groups is difficult in the presence of occlusions, newly entering targets and clutters etc. Meanwhile, when individuals resemble each other, epipolar constraint (green line denotes the epipolar line) alone is insufficient to reduce matching ambiguity. Four images here were chosen from our Drosophila tracking experiments below.

Fig. 2
Fig. 2

Experimental setup and the diagram of the proposed method. When matching tracks across various camera views in the second step, two tracks with the same color correspond to a matched pair.

Fig. 3
Fig. 3

(a): Epipolar constraint: given a calibrated image pair, matching candidates for point p1 in 1st view must lie on the associated epipolar line l in the 2nd view. Image rectification is the process of projecting the planes of two views, Π1 and Π2, onto a common plane Π′ so that the epipolar lines l map to horizontally aligned lines l′ in the rectified views. The following image pairs are supposed to be calibrated and rectified. (b): Projections of the same particle on 2D image planes will submit to epipolar constraint. Γ 1 i and Γ 2 j denote two tracks obtained from two video sequences and the dashed horizontal line represents the epipolar line. (c): 2D tracks matching. Each matched point pair is marked by the same color. Unmatched point pair is generally caused by tracking errors. (d): Grey band denotes the matching tolerance band, and any point pair falling in this band is considered to be matched. Note that near the head or tail of two matched tracks, two truly unmatched points may still fall in the tolerance band for several frames.

Fig. 4
Fig. 4

Linking 3D tracklets. Tracklet Γ1 has two linking candidates, Γ2 and Γ3. Γ2 starts several frames after Γ1 terminates, and Γ3 overlaps Γ1 several frames. The linking cost between Γ1 and Γ2, denoted by C(1, 2) is computed according to Eq. (22) and Eq. (24), while C(1, 3) is computed according to Eq. (22) and Eq. (23). Grey dots denote the predicted particle positions.

Fig. 5
Fig. 5

Performance of compared methods on two evaluation metrics: (a) TFF and (b) TCF. One can see that TraMaL, the proposed method, performs best.

Fig. 6
Fig. 6

Matching and linking results of simulated particle swarms. For clarity, only partial results are shown here. (a) and (b) represent the left and right camera view, respectively. Because of tracking errors, parts of two tracks in (a), namely 1 and 2, are both matched with one track in (b). As a result, two 3D trajectory segments are obtained as shown in (c). After performing tracklet linking, a correct and complete trajectory is acquired as shown in (d).

Fig. 7
Fig. 7

3D trajectory acquisition results of the proposed method on simulated particle swarms under different particle densities. From left to right, the particle number is 40, 60, 80 and 100, respectively. The missed and erroneous trajectories are displayed by red color.

Fig. 8
Fig. 8

Tracking fruit flies through occlusions (zooming in for more details). Enlarged parts of frame 18–29 of left view are shown here. Dashed circles suggest the occurrence of occlusions. One can see that the identities of fruit fly were correctly maintained, although the occlusions last for several successive frames. Different colors represent different tracks. Triangle represents the location in current frame and fruit flies failing to be detected because of occlusions etc. are denoted by squares.

Fig. 9
Fig. 9

Linking 3D track segments into complete trajectories (axis units: mm). Left: 120 linking candidates in all. Right: After performing linking module, 54 complete trajectories are obtained. One can see that these linked trajectories are seamlessly smooth at the adjoining points. Trajectory beginning point is marked by a round dot.

Fig. 10
Fig. 10

(a):458 3D trajectories of the Drosophila group were finally acquired. (b): 73 trajectories which are longer than 100 frames are demonstrated here. Trajectory of the same fruit fly is marked by the same colour. (c): 22 trajectories which are longer than 150 frames are coloured by velocity magnitude. (axis unit: mm).

Fig. 11
Fig. 11

(a): Comparison between the ground truth and acquired trajectories. The proposed method successfully recovered 96.9% of the ground truth. (b): Frequency distributions of the errors between ground truth and acquired trajectories. The mean error is 0.08 mm.

Fig. 12
Fig. 12

(a) : Errors between 5 acquired trajectories and the ground truth shown in (b). To detail the difference between them, (c) shows the zooming-in part of the rectangle region in (b).

Tables (2)

Tables Icon

Table 1 Model parameter settings

Tables Icon

Table 2 Compared methods

Equations (27)

Equations on this page are rendered with MathJax. Learn more.

x ( t ) = Fx ( t 1 ) + w ( t )
z ( t ) = Hx ( t ) + u ( t )
x ^ ( t ) = Fx ( t 1 ) , F = [ 1 0 Δ t 0 0 1 0 Δ t 0 0 1 0 0 0 0 1 ]
x ( t ) = x ^ ( t ) + G [ z ( t ) H x ^ ( t ) ]
G = [ α 0 0 α β Δ t 0 0 β Δ t ] , 0 α , β 1 , H = [ 1 0 0 0 0 1 0 0 ]
C ( i , j ) = | | z i ( t ) H x ^ j ( t ) | |
A ( i , j ) = { 1 if z i ( t ) is assigned to H x ^ j ( t ) 0 otherwise
A = argmin A i = 1 m j = 1 n C ( i , j ) A ( i , j )
subject to j = 1 n A ( i , j ) = 1 , i = 1 m A ( i , j ) = 1
Γ 1 i , Γ 2 j = { t | | | y 1 i ( t ) y 2 j ( t ) | | ɛ , t { 𝒯 1 i 𝒯 2 j } }
= { 1 , 2 , , N }
p = { p ( b ) , p ( b ) + 1 , , p ( e ) }
p + 1 ( b ) p ( e ) 2
MECL ( Γ 1 i , Γ 2 j ) = max { | p | } p = { 1 , , N }
C ( Γ 1 i , Γ 2 j ) = MECL ( Γ 1 i , Γ 2 j )
MECL ( Γ 1 i , Γ 2 j ) = max { | p | } ( 1 𝒯 1 i + 1 𝒯 2 j ) p = { 1 , , N }
C ( Γ 1 i , Γ 2 j ) = 2 MECL ( Γ 1 i , Γ 2 j )
Γ k a = Γ k i ( 𝒯 k i ( b ) : ˜ ( b ) 1 + τ )
Γ k b = Γ k i ( ˜ )
Γ k c = Γ k i ( ˜ ( e ) + 1 τ : 𝒯 k i ( e ) )
k { 1 , 2 } , τ , τ 0
C t ( i , j ) = { 1 1 𝒯 j ( b ) 𝒯 i ( e ) δ 1 0 𝒯 i ( e ) 𝒯 j ( b ) τ otherwise
C k ( i , j ) = Σ t = 𝒯 j ( b ) 𝒯 i ( e ) | | r i ( t ) r j ( t ) | | 𝒯 i ( e ) 𝒯 j ( b ) + 1
C k ( i , j ) = Σ t = 𝒯 i ( e ) 𝒯 j ( b ) | | r ˜ i ( t ) r ˜ j ( t ) | | 𝒯 j ( b ) 𝒯 i ( e ) + 1
v ( t + 1 ) = θ v ( t ) + n
D ( Γ EXP i , Γ GT j ) = 1 | O ( i , j ) | t O ( i , j ) | | r EXP i ( t ) r GT j ( t ) |
TFF = Σ j | A ˜ ( Γ GT j ) | | { Γ GT j | A ˜ ( Γ GT j ) } | ; TCF = Σ j Σ i | A ( i , j ) = 1 | O ( i , j ) | Σ j | 𝒯 GT j |

Metrics