Globally Optimal Cell Tracking using Integer Programming

Engin Türetken, Xinchao Wang, Carlos Becker, Carsten Haubold, 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

Tracking individual cells in dense, dividing populations is a cornerstone of modern biomedical imaging. However, it remains one of the most persistent challenges in the field. In a perfect scenario, a cell detector would identify every cell in every frame, and a tracker would simply link these dots. In reality, microscopy images are often messy: cells frequently clump together (occlusion), making multiple cells appear as a single large blob to standard detectors. Furthermore, biological processes like mitosis (division) and apoptosis (death) break traditional tracking-by-detection logic.

Existing methods typically address these issues with brittle heuristics—rules such as "if a blob is twice the average size, assume it is two cells." These rules often fail to provide a mathematically optimal solution across an entire image sequence. This paper, presented by researchers from EPFL and the University of Heidelberg, proposes a joint detection and tracking framework that handles cell clumping by generating an "over-complete" set of overlapping hypotheses and solving the resulting problem to global optimality.

Methodology

The proposed approach, titled Globally Optimal Cell Tracking, breaks the tracking process into three main stages:

1. Over-complete Hypothesis Generation

Instead of committing to a single segmentation early on, the algorithm generates a hierarchy of possible cell locations. It uses a pixel classifier to find foreground areas and then fits multiple, potentially conflicting ellipses to those areas using hierarchical clustering of "contourlets" (points of high curvature).

Hierarchical generation of over-complete cell detection hypotheses. (a-c) show the initial segmentation and contourlets. (d-h) illustrate the hierarchy of competing elliptical hypotheses across four levels.

As shown in Figure 1, this creates a "menu" of possible cell configurations for every frame. By keeping conflicting hypotheses (e.g., "this blob is one cell" vs. "this blob is two cells") until the optimization stage, the algorithm can use temporal evidence—how objects move over time—to resolve spatial ambiguity.

2. Spatio-temporal Graph Construction

These hypotheses are organized into a graph where nodes represent the ellipses and edges represent potential movements between frames. Special "source," "sink," and "division" nodes are added to account for cells appearing, dying, or splitting.

3. Integer Programming (IP) Optimization

This is the core innovation of the paper. The authors formulate the tracking problem as a network flow problem. Unlike previous joint methods that required complex factor graphs with many variable types, this model uses only one type of binary flow variable ($f_{ij}$).

Constraints ensure that "flow" is conserved (a cell cannot vanish into thin air), and exclusion constraints ensure the solver does not pick two overlapping ellipses to represent the same cell. The resulting IP is solved to global optimality using the Gurobi optimizer, finding the mathematically "best" set of trajectories for the entire sequence simultaneously.

Key Results and Evaluation

The method was evaluated on three challenging datasets from the international Cell Tracking Challenge: HeLa cancer cells, simulated nuclei (SIM), and mouse stem cells (GOWT).

Qualitative comparison of tracking results against state-of-the-art methods (CT, JST, KTH) on the HeLa dataset. The proposed method (OURS) more accurately matches the Ground Truth, especially during complex clumping events.

As illustrated in Figure 2, the proposed method (OURS) significantly outperforms state-of-the-art baselines like Conservation Tracking (CT) and Joint Segmentation and Tracking (JST). Key performance highlights include:

  • Superior Division Detection: On the HeLa-1 dataset, the authors achieved a Division F-measure of 0.85, compared to 0.65 for JST and 0.77 for CT.
  • Robustness to Clumping: In the GOWT-2 dataset, where cells are hard to distinguish, the method achieved a perfect 1.0 in detection and division accuracy.
  • Efficiency: Despite the global optimization, the tracker is highly scalable. For a dataset with 1.1 million variables, the IP solver finished in just 2 seconds. Even for complex sequences with 8 million variables, it completed in roughly 4 minutes.

Conclusion

By delaying spatial decisions and leveraging a compact, single-variable mathematical formulation, this approach provides a robust solution for tracking in dense tissues. While the method currently relies on an initial pixel-based foreground segmentation, its ability to resolve complex clumping and division events to global optimality marks a significant advancement in automated bioimage analysis. Future work may involve explicitly modeling how groups of cells form and unform to further improve tracking in extremely dense environments.

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{turetken2015globally,
  author = {Engin Türetken and Xinchao Wang and Carlos Becker and Carsten Haubold and Pascal Fua},
  title = {{Globally Optimal Cell Tracking using Integer Programming}},
  year = {2015},
  eprint = {1501.05499},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1501.05499},
}
Figure