×

Scott: shape-location combined tracking with optimal transport. (English) Zbl 1482.92047

Summary: Optimal transport (OT) is a prominent framework for point set registration, that is, to align points in two sets. Point set registration becomes particularly difficult when points are organized into objects and the correspondence among the objects is to be established. The registration of pixels must maintain consistency at the object level despite the possibility of object division, merging, and substantial alteration in size and shape over time. Existing approaches in OT exploit either similarity in shape for the entire set of points or spatial closeness of individual points, but not the two simultaneously. We propose a new weighted Gromov-Wasserstein distance (WGWD) to combine both sources of information. Importantly, we use a bipartite graph partitioning strategy to regularize OT in order to achieve object-level consistency and to enhance computational efficiency. We apply the method to cell tracking, specifically, the task of associating biological cells in consecutive image frames from time-lapse image sequences. We call the system SCOTT (shape-location combined tracking with optimal transport). By establishing a pixel-to-pixel correspondence, our method can effectively detect intricate scenarios including cell division and merging (overlapping). Experiments show that our method achieves high accuracy in tracking the movements of cells and outperforms existing methods in the detection of cell division and merging. Location information is shown to be more useful than shape information, while the combination of the two achieves optimal results.

MSC:

92C55 Biomedical imaging and signal processing

Software:

ilastik; GitHub; MOT16; POT; EMD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Adanja, O. Debeir, V. Mégalizzi, R. Kiss, N. Warzée, and C. Decaestecker, Automated tracking of unmarked cells migrating in three-dimensional matrices applied to anti-cancer drug screening, Exp. Cell Res., 316 (2010), pp. 181-193.
[2] O. Al-Kofahi, R. J. Radke, S. K. Goderie, Q. Shen, S. Temple, and B. Roysam, Automated cell lineage construction: A rapid method to analyze clonal development established with murine neural progenitor cells, Cell Cycle, 5 (2006), pp. 327-335.
[3] J. Altschuler, J. Weed, and P. Rigollet, Near-linear time approximation algorithms for optimal transport via sinkhorn iteration, in Advances in Neural Information Processing Systems, MIT Press, Cambridge, MA, 2017, pp. 1964-1974.
[4] S. Baker, D. Scharstein, J. Lewis, S. Roth, M. J. Black, and R. Szeliski, A database and evaluation methodology for optical flow, Int. J. Comput. Vis., 92 (2011), pp. 1-31.
[5] J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré, Iterative Bregman projections for regularized transportation problems, SIAM J. Sci. Comput., 37 (2015), pp. A1111-A1138, https://doi.org/10.1137/141000439. · Zbl 1319.49073
[6] K. Bernardin and R. Stiefelhagen, Evaluating multiple object tracking performance: The Clear Mot metrics, EURASIP J. Image Vide., 2008 (2008), 246309.
[7] S. Bonneau, M. Dahan, and L. D. Cohen, Single quantum dot tracking based on perceptual grouping using minimal paths in a spatiotemporal volume, IEEE Trans. Image Process., 14 (2005), pp. 1384-1395.
[8] F. Bunyak, A. Hafiane, and K. Palaniappan, Histopathology tissue segmentation by combining fuzzy clustering with multiphase vector level sets, in Software Tools and Algorithms for Biological Systems, Springer, New York, 2011, pp. 413-424.
[9] J. Chen, C. W. Harvey, M. S. Alber, and D. Z. Chen, A matching model based on earth mover’s distance for tracking Myxococcus xanthus, in Proceedings of the International Conference on Medical Image Computing and Computer-Assisted Intervention, Springer, Berlin, Heidelberg, 2014, pp. 113-120.
[10] S. Coraluppi and C. Carthel, Modified scoring in multiple-hypothesis tracking, J. Adv. Inf. Fusion, 7 (2012), pp. 153-164.
[11] M. Cuturi, Sinkhorn distances: Lightspeed computation of optimal transport, in Advances in Neural Information Processing Systems, MIT Press, Cambridge, MA, 2013, pp. 2292-2300.
[12] O. Debeir, P. Van Ham, R. Kiss, and C. Decaestecker, Tracking of migrating cells under phase-contrast video microscopy with combined mean-shift processes, IEEE Trans. Med. Imaging, 24 (2005), pp. 697-711.
[13] R. L. Dobrushin, Prescribing a system of random variables by conditional distributions, Theory Probab. Appl., 15 (1970), pp. 458-486, https://doi.org/10.1137/1115049. · Zbl 0264.60037
[14] A. Dufour, R. Thibeaux, E. Labruyere, N. Guillen, and J.-C. Olivo-Marin, 3\em-D active meshes: Fast discrete deformable models for cell tracking in \textup3-D time-lapse microscopy, IEEE Trans. Image Process., 20 (2011), pp. 1925-1937. · Zbl 1372.92052
[15] P. Dvurechensky, A. Gasnikov, and A. Kroshnin, Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm, in Proceedings of the 35th International Conference on Machine Learning, 2018.
[16] O. Dzyubachyk, W. A. Van Cappellen, J. Essers, W. J. Niessen, and E. Meijering, Advanced level-set-based cell tracking in time-lapse fluorescence microscopy, IEEE Trans. Med. Imaging, 29 (2010), pp. 852-867.
[17] R. Flamary and N. Courty, POT Python Optimal Transport Library, https://github.com/rflamary/POT (accessed 2019/04/01).
[18] S. Gerber and M. Maggioni, Multiscale strategies for computing optimal transport, J. Mach. Learn. Res., 18 (2017), pp. 2440-2471. · Zbl 1435.65095
[19] A. Gramfort, G. Peyré, and M. Cuturi, Fast optimal transport averaging of neuroimaging data, in Proceedings of the International Conference on Information Processing in Medical Imaging, Springer, Cham, 2015, pp. 261-272.
[20] L. G. Hanin, Kantorovich-Rubinstein norm and its application in the theory of Lipschitz spaces, Proc. Amer. Math. Soc., 115 (1992), pp. 345-352. · Zbl 0768.46012
[21] B. X. Kausler, M. Schiegg, B. Andres, M. Lindner, U. Koethe, H. Leitte, J. Wittbrodt, L. Hufnagel, and F. A. Hamprecht, A discrete chain graph model for 3d,+ t cell tracking with high misdetection robustness, in Proceedings of the European Conference on Computer Vision, Springer, Berlin, Heidelberg, 2012, pp. 144-157.
[22] T. Kirubarajan, Y. Bar-Shalom, and K. R. Pattipati, Multiassignment for tracking a large number of overlapping objects [and application to fibroblast cells], IEEE Trans. Aerosp. Electron. Syst., 37 (2001), pp. 2-21.
[23] B. C. Ko, J.-W. Gim, and J.-Y. Nam, Automatic white blood cell segmentation using stepwise merging rules and gradient vector flow snake, Micron, 42 (2011), pp. 695-705.
[24] F. Li, X. Zhou, J. Ma, and S. T. Wong, Multiple nuclei tracking using integer programming for quantitative cancer cell cycle analysis, IEEE Trans. Med. Imaging, 29 (2010), pp. 96-105.
[25] K. Li, E. D. Miller, M. Chen, T. Kanade, L. E. Weiss, and P. G. Campbell, Computer vision tracking of stemness, in Proceedings of the IEEE International Symposium on Biomedical Imaging: From Nano to Macro, 2008, pp. 847-850.
[26] X. Lou and F. A. Hamprecht, Structured learning for cell tracking, in Advances in Neural Information Processing Systems, MIT Press, Cambridge, MA, 2011, pp. 1296-1304.
[27] K. E. Magnusson and J. Jaldén, A batch algorithm using iterative application of the Viterbi algorithm to track cells and construct cell lineages, in Proceedings of the IEEE International Symposium on Biomedical Imaging (ISBI), 2012, pp. 382-385.
[28] K. E. Magnusson, J. Jaldén, P. M. Gilbert, and H. M. Blau, Global linking of cell tracks using the Viterbi algorithm, IEEE Trans. Med. Imaging, 34 (2014), pp. 911-929.
[29] M. Maška, V. Ulman, D. Svoboda, P. Matula, P. Matula, C. Ederra, A. Urbiola, T. Espan͂a, S. Venkatesan, D. M. Balak, P. Karas, T. Bolcková, M. Štreitová, C. Carthel, S. Coraluppi, N. Harder, K. Rohr, K. E. G. Magnusson, J. Jaldén, H. M. Blau, O. Dzyubachyk, P. Křížek, G. M. Hagen, D. Pastor-Escuredo, D. Jimenez-Carretero, M. J. Ledesma-Carbayo, A. Mun͂oz-Barrutia, E. Meijering, M. Kozubek, and C. Ortiz-de-Solorzano, A benchmark for comparison of cell tracking algorithms, Bioinformatics, 30 (2014), pp. 1609-1617.
[30] E. Meijering, O. Dzyubachyk, and I. Smal, Methods for Cell and Particle Tracking, Method Enzymol. 504, Elsevier, Amsterdam, 2012, pp. 183-200.
[31] F. Mémoli, Gromov-Wasserstein distances and the metric approach to object matching, Found. Comput. Math., 11 (2011), pp. 417-487. · Zbl 1244.68078
[32] A. Milan, L. Leal-Taixé, I. Reid, S. Roth, and K. Schindler, Mot16: A Benchmark for Multi-object Tracking, preprint, https://arxiv.org/abs/1603.00831, 2016.
[33] B. Pass, Multi-marginal optimal transport: Theory and applications, ESAIM Math. Model. Numer. Anal., 49 (2015), pp. 1771-1790. · Zbl 1330.49050
[34] D. Pastor-Escuredo, M. A. Luengo-Oroz, L. Duloquin, B. Lombardot, M. Ledesma-Carbayo, P. Bourgine, N. Peyrieras, and A. Santos, Spatio-temporal filtering with morphological operators for robust cell migration estimation in “in-vivo” images, in Proceedings of the IEEE International Symposium on Biomedical Imaging (ISBI), 2012, pp. 1312-1315. · Zbl 1373.94266
[35] G. Peyré, M. Cuturi, and J. Solomon, Gromov-Wasserstein averaging of kernel and distance matrices, in Proceedings of the International Conference on Machine Learning, 2016, pp. 2664-2672.
[36] U. Pferschy and J. Schauer, The maximum flow problem with disjunctive constraints, J. Comb. Optim., 26 (2013), pp. 109-119. · Zbl 1275.90120
[37] D. H. Rapoport, T. Becker, A. M. Mamlouk, S. Schicktanz, and C. Kruse, A novel validation algorithm allows for automated cell tracking and the extraction of biologically meaningful parameters, PloS One, 6 (2011), e27315.
[38] Y. Rubner, C. Tomasi, and L. J. Guibas, The earth mover’s distance as a metric for image retrieval, Int. J. Comput. Vis., 40 (2000), pp. 99-121. · Zbl 1012.68705
[39] L.-P. Saumier, B. Khouider, and M. Agueh, Optimal transport for particle image velocimetry: Real data and postprocessing algorithms, SIAM J. Appl. Math., 75 (2015), pp. 2495-2514, https://doi.org/10.1137/140988814. · Zbl 1330.76111
[40] M. Schiegg, P. Hanslovsky, C. Haubold, U. Koethe, L. Hufnagel, and F. A. Hamprecht, Graphical model for joint segmentation and tracking of multiple dividing cells, Bioinformatics, 31 (2014), pp. 948-956.
[41] M. Schiegg, P. Hanslovsky, B. X. Kausler, L. Hufnagel, and F. A. Hamprecht, Conservation tracking, in Proceedings of the IEEE International Conference on Computer Vision, 2013, pp. 2928-2935.
[42] T. Sixta, J. Cao, J. Seebach, H. Schnittler, and B. Flach, Coupling Cell Detection and Tracking by Temporal Feedback Software, http://celltrackingchallenge.net/participants/CVUT-CZ/ (accessed 2019/04/01).
[43] C. Sommer, C. N. Straehle, U. Koethe, and F. A. Hamprecht, Ilastik: Interactive learning and segmentation toolkit, in Proceedings of the IEEE International Symposium on Biomedical Imaging: From Nano to Macro, 2011, pp. 230-233.
[44] T. Takaki, K. Trenz, V. Costanzo, and M. Petronczki, Polo-like kinase \textup1 reaches beyond mitosis-cytokinesis, DNA damage response, and development, Curr. Opin. Cell Biol., 20 (2008), pp. 650-660.
[45] M. Thery and M. Bornens, Cell shape and cell division, Curr. Opin. Cell Biol., 18 (2006), pp. 648-657.
[46] E. Türetken, X. Wang, C. J. Becker, C. Haubold, and P. Fua, Network flow integer programming to track elliptical cells in time-lapse sequences, IEEE Trans. Med. Imaging, 36 (2017), pp. 942-951.
[47] V. Ulman, M. Maška, K. E. Magnusson, O. Ronneberger, C. Haubold, N. Harder, P. Matula, P. Matula, D. Svoboda, M. Radojevic, I. Smal, K. Rohr, J. Jaldén, H. M. Blau, O. Dzyubachyk, B. Lelieveldt, P. Xiao, Y. Li, S. Y. Cho, A. C. Dufour, J. C. Olivo-Marin, C. C. Reyes-Aldasoro, J. A. Solis-Lemus, R. Bensch, T. Brox, J. Stegmaier, R. Mikut, S. Wolf, F. A. Hamprecht, T. Esteves, P. Quelhas, Ö. Demirel, L. Malmström, F. Jug, P. Tomancak, E. Meijering, A. Mun͂oz-Barrutia, M. Kozubek, and C. Ortiz-de-Solorzano, An objective comparison of cell-tracking algorithms, Nat. Methods, 14 (2017), pp. 1141-1152.
[48] C. Villani, Topics in Optimal Transportation, Grad. Stud. Math. 58, American Mathematical Society, Providence, RI, 2003. · Zbl 1106.90001
[49] C. M. Waterman-Storer, A. Desai, J. C. Bulinski, and E. Salmon, Fluorescent speckle microscopy, a method to visualize the dynamics of protein assemblies in living cells, Curr. Biol., 8 (1998), pp. 1227-1230.
[50] M. Werman, S. Peleg, and A. Rosenfeld, A distance metric for multidimensional histograms, Comput. Vis. Graph. Image Process., 32 (1985), pp. 328-336. · Zbl 0624.68060
[51] S. Wienert, D. Heim, K. Saeger, A. Stenzinger, M. Beil, P. Hufnagl, M. Dietel, C. Denkert, and F. Klauschen, Detection and segmentation of cell nuclei in virtual microscopy images: A minimum-model approach, Sci. Rep., 2 (2012), 503.
[52] F. Yang, M. A. Mackey, F. Ianzini, G. Gallardo, and M. Sonka, Cell segmentation, tracking, and mitosis detection using temporal context, in Proceedings of the International Conference on Medical Image Computing and Computer-Assisted Intervention, Springer, Berlin, Heidelberg, 2005, pp. 302-309.
[53] H. Zha, X. He, C. Ding, H. Simon, and M. Gu, Bipartite graph partitioning and data clustering, in Proceedings of the Tenth ACM International Conference on Information and Knowledge Management, 2001, pp. 25-32.
[54] L. Zhang, Y. Li, and R. Nevatia, Global data association for multi-object tracking using network flows, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2008, pp. 1-8.
[55] C. Zimmer, E. Labruyere, V. Meas-Yedid, N. Guillén, and J.-C. Olivo-Marin, Segmentation and tracking of migrating cells in videomicroscopy with parametric active contours: A tool for cell-based drug testing, IEEE Trans. Med. Imaging, 21 (2002), pp. 1212-1221.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.