Detecting and Tracking Cells using Network Flow Programming

Engin Türetken, Xinchao Wang, Carlos J. Becker, Pascal Fua

Abstract

We propose a novel approach to automatically tracking cell populations in time-lapse images. To account for cell occlusions and overlaps, we introduce a robust method that generates an over-complete set of competing detection hypotheses. We then perform detection and tracking simultaneously on these hypotheses by solving to optimality an integer program with only one type of flow variables. This eliminates the need for heuristics to handle missed detections due to occlusions and complex morphology. We demonstrate the effectiveness of our approach on a range of challenging sequences consisting of clumped cells and show that it outperforms state-of-the-art techniques.

Introduction

Cell tracking is fundamental to biological research, enabling the study of processes such as mitosis, migration, and apoptosis. However, automated tracking faces significant hurdles. First, complex morphology and clumping often lead to under-segmentation, where multiple cells are erroneously identified as a single object. Second, biological events like division and disappearance break standard point-to-point tracking logic. Traditional "track-by-detection" methods are fragile because they rely on a single, potentially flawed segmentation step. If the initial detector fails to separate clumped cells, the subsequent tracker cannot recover. This work addresses these issues by integrating detection and tracking into a global optimization framework.

Methods

The proposed framework utilizes a three-stage pipeline designed for robustness against clumping and occlusions.

Hierarchical Hypothesis Generation

Instead of committing to a single segmentation, the method generates an "over-complete" set of competing detection hypotheses. For every connected component identified by a pixel classifier, a robust ellipse-fitting algorithm creates a hierarchy of potential cell configurations. This hierarchy represents different interpretations of the same image region—for instance, a single blob could be interpreted as one large cell, two medium cells, or three small cells.

Hierarchical hypothesis generation process: from raw image to a hierarchy of potential cell configurations (ellipses).

Spatio-Temporal Graph and Integer Programming

A graph is constructed where nodes represent these potential ellipses across all time frames. Edges represent biological transitions such as migration, division, appearance, and disappearance. The tracking problem is then formulated as a constrained Bayesian inference problem, cast as a network flow problem.

Crucially, the authors simplify the formulation into an integer program (IP) using only a single type of binary flow variable. Constraints ensure flow conservation and enforce "exclusion," meaning only one hypothesis from a hierarchical set can be active for a given image region. The resulting IP is solved to global optimality using the Gurobi optimizer, ensuring the most likely set of trajectories is found across the entire video sequence.

Results

The method was evaluated on ten sequences from the ISBI Cell Tracking Challenge, including the HeLa (dense populations), SIM (simulated baseline), and GOWT (low contrast) datasets.

Comparison of tracking results between the proposed method (OURS) and state-of-the-art baselines (CT, JST, KTH) against Ground Truth over time steps t=76 to t=78.

The proposed method consistently outperformed state-of-the-art baselines like Conservation Tracking (CT), Joint Segmentation and Tracking (JST), and KTH. On the HeLa-1 dataset, it achieved a division detection F-measure of 0.85, compared to 0.77 for CT. In the challenging GOWT-2 dataset characterized by heavy clumping, the method achieved a perfect 1.0 detection F-measure, whereas CT scored only 0.03. Overall, the method ranked highest or second-highest across MOTA (Multiple Object Tracking Accuracy) and TRA (Tracking Precision) metrics. Despite the IP's complexity—reaching up to 8 million variables—the solver remained efficient, typically reaching solutions within seconds to a few minutes.

Conclusion

By treating detection and tracking as a simultaneous global optimization problem, this framework effectively handles the challenges of cell clumping and complex morphology. The use of hierarchical ellipses provides a powerful geometric primitive for regularizing cell shapes. While the method currently depends on initial foreground-background segmentation, future work could explore modeling group dynamics or scaling to even larger 3D+time datasets.

Summary updated

Abstract

We propose a novel approach to automatically tracking cell populations in time-lapse images. To account for cell occlusions and overlaps, we introduce a robust method that generates an over-complete set of competing detection hypotheses. We then perform detection and tracking simultaneously on these hypotheses by solving to optimality an integer program with only one type of flow variables. This eliminates the need for heuristics to handle missed detections due to occlusions and complex morphology. We demonstrate the effectiveness of our approach on a range of challenging sequences consisting of clumped cells and show that it outperforms state-of-the-art techniques.
BibTeX
@misc{turetken2015detecting,
  author = {Engin Türetken and Xinchao Wang and Carlos J. Becker and Pascal Fua},
  title = {{Detecting and Tracking Cells using Network Flow Programming}},
  year = {2015},
  eprint = {1501.05499},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1501.05499},
}
Figure