A fast approximate primal-dual solver for tracking-by-assignment cell-tracking problems

View the Project on GitHub vislearn/libct


Visualization of a Cell-Tracking Problem

Cell tracking plays a key role in discovery in many life sciences, especially in cell and developmental biology. So far, in the most general setting this problem was addressed by off-the-shelf solvers like Gurobi, whose run time and memory requirements rapidly grow with the size of the input. In contrast, for this solver the growth is nearly linear. Compared to solving the problem with Gurobi, we observe an up to 60 times speed-up, while reducing the memory footprint significantly.

For more a detailed report please see our AISTATS 2020 publication.

Publication and Citation

The creation of this solver was joint effort of multiple persons and research institutes. To cite our this work please use:

S. Haller, M. Prakash, L. Hutschenreiter, T. Pietzsch, C. Rother, F. Jug, P. Swoboda, B. Savchynskyy. A Primal-Dual Solver for Large-Scale Tracking-by-Assignment. AISTATS 2020. [pdf]

  title     = {A Primal-Dual Solver for Large-Scale Tracking-by-Assignment},
  author    = {Haller, Stefan  and  Prakash, Mangal  and  Hutschenreiter, Lisa  and  Pietzsch, Tobias  and  Rother, Carsten  and  Swoboda, Paul  and  Savchynskyy, Bogdan},
  booktitle = {Proceedings of Machine Learning Research},
  year      = {2020},
  series    = {Proceedings of Machine Learning Research},
  publisher = {PMLR},

libct – The Solver Library

Visualization of Solver Decomposition

We implemented the suggested solving scheme in a modern C++ library. The source code of this implementation is publicly available and we plan to incorporate further improvements in the future. To make the results presented in this paper reproducible, the repository holding the source code also contains a fixed version which we used during the preparation of the aforementioned publication.

Along with the library we provide Python 3 bindings which allow to feed a text file representation of cell-tracking problems into the native library to run the solver.

Additional information to various aspects of our implementation are available here:


Drosophila Melanogaster (Common Fruit Fly) Nucleus Tracking Dataset

We will make datasets and the generated model files that have been used for preparation of our AISTATS 2020 submission available here in the near future.