Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-08T00:31:22.207Z Has data issue: false hasContentIssue false

Tri-track: Free Software for Large-Scale Particle Tracking

Published online by Cambridge University Press:  01 March 2013

Pascal Vallotton*
Affiliation:
CSIRO, Division of Mathematics, Informatics, and Statistics. Locked Bag 17, North Ryde NSW 1670, Australia
Sandra Olivier
Affiliation:
CSIRO, Division of Animal, Food and Health Sciences. Riverside Corporate Park, 11 Julius Avenue, North Ryde NSW 2113, Australia
*
*Corresponding author. E-mail: [email protected]
Get access

Abstract

The ability to correctly track objects in time-lapse sequences is important in many applications of microscopy. Individual object motions typically display a level of dynamic regularity reflecting the existence of an underlying physics or biology. Best results are obtained when this local information is exploited. Additionally, if the particle number is known to be approximately constant, a large number of tracking scenarios may be rejected on the basis that they are not compatible with a known maximum particle velocity. This represents information of a global nature, which should ideally be exploited too. Some time ago, we devised an efficient algorithm that exploited both types of information. The tracking task was reduced to a max-flow min-cost problem instance through a novel graph structure that comprised vertices representing objects from three consecutive image frames. The algorithm is explained here for the first time. A user-friendly implementation is provided, and the specific relaxation mechanism responsible for the method's effectiveness is uncovered. The software is particularly competitive for complex dynamics such as dense antiparallel flows, or in situations where object displacements are considerable. As an application, we characterize a remarkable vortex structure formed by bacteria engaged in interstitial motility.

Type
Software, Techniques, and Equipment Development
Copyright
Copyright © Microscopy Society of America 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Andriyenko, A. & Schindler, K. (2010). Globally optimal multi-target tracking on a hexagonal lattice. In ECCV 2010, Proceedings of the 11th European Conference on Computer Vision: Part I, vol. 6311, pp. 466479.Google Scholar
Arfken, G.B. & Weber, H.J. (1995). Mathematical Methods for Physicists. San Diego, CA: Academic Press.Google Scholar
Berclaz, J., Fleuret, F. & Fua, P. (2009). Multiple object tracking using flow linear programming. In 12th IEEE International Workshop on Performance Evaluation of Tracking and Surveillance, pp. 18.Google Scholar
Bugeau, A. & Pérez, P. (2008). Track and cut: Simultaneous tracking and segmentation of multiple objects with graph cuts. EURASIP Journal on Image and Video Processing 2008, 317278-1–14.CrossRefGoogle Scholar
Chen, Z.X., Chen, L., Cetin, M. & Willsky, A.S. (2009). An efficient message passing algorithm for multi-target tracking. In Fusion: 2009 12th International Conference on Information Fusion, Vols 1–4, pp. 826833.Google Scholar
Chia, A.Y.S. & Huang, W.M. (2006). Multiple objects tracking with multiple hypotheses dynamic updating. In 2006 IEEE International Conference on Image Processing, ICIP 2006, pp. 569572. New York.Google Scholar
Cox, I.J. & Hingorani, S.L. (1996). An efficient implementation of Reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking. IEEE T Pattern Anal 18(2), 138150.Google Scholar
Dalziel, S.B. (1992). Decay of rotating turbulence—Some particle tracking experiments. Appl Sci Res 49(3), 217244.Google Scholar
Goldberg, A.V. (1997). An efficient implementation of a scaling minimum-cost flow algorithm. J Algorithms 22(1), 129.Google Scholar
Hadjidemetriou, E., Grossberg, M.D. & Nayar, S.K. (2001). Histogram preserving image transformations. Int J Comput Vision 45(1), 523.Google Scholar
Hichcock, F.L. (1941). The distribution of a product from several sources to numerous localities. J Math Phys 20, 224230.CrossRefGoogle Scholar
Ingham, C.J. & Ben Jacob, E. (2008). Swarming and complex pattern formation in Paenibacillus vortex studied by imaging and tracking cells. BMC Microbiol 8, 36.Google Scholar
Labonte, G. (2000). On a neural network that performs an enhanced nearest-neighbour matching. Pattern Anal Appl 3(3), 267278.Google Scholar
Li, L., Huang, W., Gu, I.Y., Luo, R. & Tian, Q. (2008). An efficient sequential approach to tracking multiple objects through crowds for real-time intelligent CCTV systems. IEEE T Syst Man Cy B 38(5), 12541269.Google ScholarPubMed
Liu, L., Zheng, H., Williams, L., Zhang, F., Wang, R., Hertzberg, J. & Shandas, R. (2008). Development of a custom-designed echo particle image velocimetry system for multi-component hemodynamic measurements: System characterization and initial experimental results. Phys Med Biol 53(5), 13971412.Google Scholar
Ma, Y.Q., Yu, Q. & Cohen, I. (2009). Target tracking with incomplete detection. Comput Vis Image Underst 113(4), 580587.CrossRefGoogle Scholar
Massoudi, A., Semenovich, D. & Sowmya, A. (2012). Cell tracking and mitosis detection using splitting flow networks in phase-contrast imaging. In 34th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC'12), pp. 53105313.Google Scholar
Nichol, D. & Fiebig, M. (1991). Tracking multiple moving-objects by binary object forest segmentation. Image Vis Comput 9(6), 362371.Google Scholar
Padfield, D., Rittscher, J. & Roysam, B. (2011). Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis. Med Image Anal 15(4), 650668.CrossRefGoogle ScholarPubMed
Reid, D.B. (1979). Algorithm for tracking multiple targets. IEEE T Automat Contr 24(6), 843854.Google Scholar
Sbalzarini, I.F. & Koumoutsakos, P. (2005). Feature point tracking and trajectory analysis for video imaging in cell biology. J Struct Biol 151(2), 182195.Google Scholar
Sedgewick, R. (2002). Algorithms in C++. Boston: Addison-Wesley.Google Scholar
Semmler, A.B.T., Whitchurch, C.B. & Mattick, J.S. (1999). A re-examination of twitching motility in Pseudomonas aeruginosa . Microbiology-Sgm 145, 28632873.Google Scholar
Sethi, I.K. & Jain, R. (1987). Finding trajectories of feature points in a monocular image sequence. IEEE T Pattern Anal 9(1), 5673.Google Scholar
Shafique, K. & Shah, M. (2005). A noniterative greedy algorithm for multiframe point correspondence. IEEE T Pattern Anal 27(1), 5165.Google Scholar
Smal, I., Draegestein, K., Galjart, N., Niessen, W. & Meijering, E. (2008). Particle filtering for multiple object tracking in dynamic fluorescence microscopy images: Application to microtubule growth analysis. IEEE T Med Imaging 27(6), 789804.Google Scholar
Vallotton, P., Mililli, L., Turnbull, L. & Whitchurch, C. (2010). Segmentation of dense 2D bacilli populations. In International Conference on Digital Image Computing: Techniques and Applications, pp. 8286.Google Scholar
Vallotton, P., Ponti, A., Waterman-Storer, C.M., Salmon, E.D. & Danuser, G. (2003). Recovery, visualization, and analysis of actin and tubulin polymer flow in live cells: A fluorescent speckle microscopy study. Biophys J 85(2), 12891306.Google Scholar
Zheng, D.Y., Xiong, H.K. & Zheng, Y.F. (2011). A structured learning-based graph matching for dynamic multiple object tracking. In 2011 18th IEEE International Conference on Image Processing, pp. 23332336.Google Scholar
Zhou, C.A. & Hura, G.S. (2002). Two-dimensional occluded object matching using Petri nets. Int J Intell Syst 17(3), 303320.Google Scholar
Supplementary material: File

Vallotton Supplementary Material

Vallotton Supplementary Material 1

Download Vallotton Supplementary Material(File)
File 376 Bytes
Supplementary material: File

Vallotton Supplementary Material

Vallotton Supplementary Material 2

Download Vallotton Supplementary Material(File)
File 82.1 KB
Supplementary material: File

Vallotton Supplementary Material

Vallotton Supplementary Material 3

Download Vallotton Supplementary Material(File)
File 37.6 KB
Supplementary material: File

Vallotton Supplementary Material

Vallotton Supplementary Material 4

Download Vallotton Supplementary Material(File)
File 43.7 MB
Supplementary material: File

Vallotton Supplementary Material

Vallotton Supplementary Material 5

Download Vallotton Supplementary Material(File)
File 3.6 MB
Supplementary material: File

Vallotton Supplementary Material

Vallotton Supplementary Material 6

Download Vallotton Supplementary Material(File)
File 170.2 MB