Global Graph Optimization for Multi-Object Tracking

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 293 papers108 conceptsfrozen 2026-10-04

In traditional multi-object tracking, we often think like a runner with blinkers on. We look at frame $t$, look at frame $t+1$, and try to make the best match possible between the detections we see. This "greedy" approach—often implemented via Kalman filters or simple bipartite matching—is fast, but it is brittle. If an object is occluded for a few frames or two similar-looking people cross paths, the local tracker often makes an irreversible mistake, leading to an "identity switch."

To solve this, a massive body of research has shifted the problem from a sequence of local decisions to a single global optimization problem. Instead of deciding who is who frame-by-frame, we wait to see a larger window of time (or the entire video) and then find the set of trajectories that is most consistent across the whole sequence.

Tracking as a Network Flow

The most intuitive way to frame this global view is as a minimum-cost network flow problem. Imagine every detection in every frame as a node in a graph. We draw edges between detections in consecutive frames, where the "cost" of an edge represents how unlikely it is that those two detections belong to the same person.

As Laura Leal-Taixé and colleagues demonstrated in Everybody needs somebody, we can then treat the objects as "flow" moving through this network. We want to send units of flow from the start of the video to the end such that the total cost is minimized. This formulation is powerful because it enforces conservation laws: if a person enters a detection node, they must also leave it. Martin Schiegg utilized this in Conservation Tracking to resolve complex biological scenarios like cell division, where one "flow" splits into two.

Bridging the Gaps with Integer Linear Programming

While simple network flow is efficient, it struggles with long-term occlusions. If a person disappears behind a pillar for ten frames, a standard flow network might lose them because there are no edges connecting frame $t$ to frame $t+10$.

To fix this, researchers like Andrea Hornáková and Paul Swoboda introduced Lifted Disjoint Paths. This framework adds "lifted edges" that provide connectivity priors across distant frames. By formulating the problem as an Integer Linear Program (ILP), the system can simultaneously optimize across the entire sequence, effectively "stitching" together broken segments that disappear and reappear. This same logic allows Yunjiao Lu to reconstruct trajectories of particles that move to the "dark side" of a cell surface in Probabilistic reconstruction of truncated particle trajectories.

From Paths to Graph Partitioning

An alternative perspective treats tracking not as finding paths, but as clustering. In this view, every detection in the video is a node, and we want to partition the entire graph into a set of disjoint clusters, where each cluster represents one unique object's life story.

Siyu Tang and Bernt Schiele framed this as a Minimum Cost Subgraph Multicut Problem. This approach is particularly robust in crowded scenes because it bypasses the need for early, error-prone decisions like Non-Maximum Suppression (NMS). Instead of picking the "best" detection box first, the multicut formulation jointly clusters multiple detection hypotheses, allowing the global context to decide which boxes are redundant and which are distinct individuals.

Incorporating Physics and Social Context

The beauty of global optimization is that it provides a "mathematical hook" to hang complex constraints on. Because we are solving for the whole trajectory at once, we can enforce rules that a frame-by-frame tracker couldn't easily handle:

  1. Physical Constraints: In What Players do with the Ball, Andrii Maksai uses Mixed Integer Programming to ensure a ball's trajectory follows the laws of gravity and constant velocity across the entire clip.
  2. Social Forces: Laura Leal-Taixé showed that we can add costs to the graph that penalize trajectories that move through each other or ignore grouping behaviors, effectively modeling how humans navigate crowds.
  3. Multi-Modal Fusion: Systems like mmMOT by Wenwei Zhang use global flow to fuse LiDAR and camera data, ensuring that even if one sensor fails momentarily, the global minimum cost path remains stable.

Scaling to the Real World

The primary challenge with global graph methods is computational complexity; solving an ILP or a Multicut problem is NP-hard. Recent work has focused on making these methods scalable. Guillem Braso and Laura Leal-Taixé introduced SUSHI, which uses a hierarchy of Graph Neural Networks to solve the partitioning problem recursively. By breaking the video into small chunks, solving them, and then merging the results, they achieve the benefits of global optimization on much longer sequences.

By moving from local "best guesses" to global "best fits," these researchers have transformed tracking from a noisy signal-processing task into a rigorous combinatorial optimization problem. The result is tracking that doesn't just see where an object is, but understands where it must have been.

Papers in this version

Showing 60 of 93 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 104 papers
  2. Version 1 · 2026-10-04 · 93 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_global_trajectory_optimization_6fc8ea02,
  title = {global trajectory optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-trajectory-optimization/rdr_6fc8ea0269264632a286fb43a47a5086},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_graph_optimization_for_multi_obje_6fc8ea02_v1,
  title = {Global Graph Optimization for Multi-Object Tracking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-graph-optimization-for-multi-object-tracking/rdr_6fc8ea0269264632a286fb43a47a5086/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}