Network Flow Optimization for Multi Object Tracking

134 concepts103 papers1 proposal

When tracking multiple moving objects in a video—whether they are pedestrians on a street, cells under a microscope, or birds migrating across a continent—the traditional approach relies on frame-by-frame decisions. A local tracker takes the detections from frame $t$, compares them to the detections in frame $t+1$, and makes a greedy match using algorithms like the Hungarian method or a Kalman filter.

While computationally fast, this local approach is inherently fragile. If an object is temporarily occluded by a tree, blurs due to sudden motion, or passes close to an identical-looking object, a local tracker easily falters. It might permanently lose the target's identity, switch the identities of two nearby objects, or fragment a single trajectory into multiple broken pieces. As noted by Benjamin Risse et al. in Comparison of two 3D tracking paradigms for freely flying insects, probabilistic causal filters frequently suffer from track fragmentation in dense environments, making global optimization methods far superior for maintaining long-term identity.

To solve this, a powerful paradigm shift treats tracking not as a sequence of immediate choices, but as a global optimization problem. By looking at an entire video sequence simultaneously, information from the future can be used to resolve ambiguities in the past.

The Graph Abstraction: From Detections to Networks

The core intuition behind global trajectory optimization is to transform the physical space-time arena of a video into a directed graph.

Imagine a graph where every single object detection across all frames is represented as a node. We then draw directed edges between nodes in consecutive frames (or across small temporal gaps) to represent plausible movements.

Frame t-1        Frame t        Frame t+1
  (Det A) ------> (Det B) ------> (Det C)
     \                             ^
      \___________________________/  (Occlusion Bypass)

Each edge is assigned a cost or affinity score. This cost is derived from how likely the transition is, factoring in spatial proximity, motion consistency, and visual appearance. For instance, if a detection in frame $t+1$ is miles away or looks completely different from a detection in frame $t$, the edge connecting them will have an exceptionally high cost.

Once this graph is constructed, the multi-object tracking problem changes completely: it becomes the task of finding the most mathematically optimal set of paths through this graph.

Hamed Pirsiavash demonstrated in Globally-optimal greedy algorithms for tracking a variable number of objects that structuring these temporal detections as a Directed Acyclic Graph (DAG) is incredibly powerful. Because time flows strictly forward, the graph cannot contain loops. This acyclic property allows researchers to use highly efficient, greedy successive shortest-path algorithms to find mathematically exact global tracking optima in polynomial time, bypassing the need for heavy, slow combinatorial search tools.

The Power of Flow Conservation

To make this graph formulation work, we need a mechanism that prevents paths from doing physically impossible things—like splitting into two distinct objects or vanishing into thin air. This is where network flow optimization comes in.

By introducing a virtual "Source" node where trajectories can begin and a virtual "Sink" node where trajectories can end, we can treat tracking as pushing units of "flow" through the network. We enforce a strict rule at every detection node called flow conservation: the total amount of flow entering a node must exactly equal the total amount of flow leaving it.

[Source] ---> (Detection Node) ---> [Sink]

If we restrict the capacity of each detection node to a maximum of $1$, a beautiful property emerges: a single unit of flow entering the network at the source must trace a continuous, non-overlapping path through the detections over time before exiting at the sink. This unit of flow represents the complete lifetime trajectory of a single physical object.

This elegant mapping was utilized by Daniel Sheldon et al. in Collective Inference on Markov Models for Modeling Bird Migration. They showed that mapping sequential state transitions onto a layered trellis graph converts a highly complex probabilistic inference task into a well-defined minimum-cost flow problem. By minimizing the total edge cost across the network while satisfying node capacity constraints, the optimization algorithm automatically uncovers the most probable trajectories of the entire population.

Bridging the Gaps: Handling Occlusions

One of the greatest strengths of global network flow is its natural resilience to occlusions. If a pedestrian walks behind a pillar in frame $t$ and re-emerges in frame $t+5$, a local tracker will fail because there is no detection node in frame $t$ to link to.

In a global flow network, we simply introduce "long-range" edges that skip intermediate frames. The optimization algorithm evaluates the cost of skipping those frames against the cost of starting a brand new trajectory. Because starting a new trajectory incurs a high entry penalty (a "source cost"), the solver will naturally choose to bridge the gap via the long-range edge if the appearance and motion vectors before and after the occlusion match.

To push this concept further, Andrea Hornáková et al. introduced the concept of Lifted Disjoint Paths in Lifted Disjoint Paths with Application in Multiple Object Tracking. Traditional network flow models only evaluate costs between immediate neighbors in the graph, losing track of long-range history. By adding "lifted edges" that penalize or reward connections based on information from distant frames, the authors allowed the optimization framework to maintain strict identity consistency across massive temporal gaps.

Similarly, when multiple targets merge into a single detection cluster (such as a swarm of insects or a crowd of people), standard unit-capacity networks can struggle. To resolve this, Zheng Wu 0003 et al. proposed a framework in Efficient track linking methods for track graphs using network-flow and set-cover techniques that applies minimum-flow algorithms to track graphs. By allowing nodes to support variable flow capacities, their system mathematically estimates the exact number of objects moving within a merged track segment, ensuring that the count of trajectories entering and exiting an occlusion remains perfectly balanced.

Enforcing Global Consistency: Advanced Formulations

While standard min-cost flow models are highly efficient, they operate under a "Markovian" assumption: the choice of which edge to take out of a node depends only on that node, not on where the flow came from. In complex scenarios, we need non-Markovian constraints to ensure that an object's behavior remains globally consistent over its entire lifespan.

To enforce these stricter constraints, researchers often upgrade the optimization problem from simple network flows to Integer Linear Programming (ILP) or graph partitioning problems.

  • Multi-Commodity Flows: In standard network flow, all units of flow are identical. Afshin Dehghan et al. bypassed this limitation in Target Identity-aware Network Flow for online multiple target tracking by reframing tracking as a multi-commodity network flow problem. By treating each target as a unique "commodity" with its own specific source and sink, the optimization explicitly prevents different targets from swapping identities mid-sequence.
  • Global Clique Partitioning: Another approach eliminates the concept of sequential paths entirely. Afshin Dehghan et al. demonstrated in GMMCP tracker: Globally optimal Generalized Maximum Multi Clique problem for multiple object tracking that data association can be framed as finding a set of disjoint cliques in a multi-partite graph. By optimizing the affinity between all pairs of detections within a temporal window simultaneously, identity switches are resolved globally rather than frame-by-frame.
  • Graph Multicuts: Instead of searching for paths, we can view tracking as a clustering problem. Siyu Tang et al. introduced this perspective in Subgraph decomposition for multi-target tracking, modeling tracking as a Minimum Cost Subgraph Multicut Problem. Detections are represented as nodes in a massive graph, and the algorithm finds the optimal way to cut edges to partition the graph into disjoint clusters, where each cluster represents a complete, globally consistent trajectory.

Learning the Costs End-to-End

A global optimization solver is only as good as the costs assigned to its edges. If the affinity scores between nodes are inaccurate, the solver will perfectly optimize for a flawed trajectory.

Early iterations of global tracking relied on hand-crafted geometric distances or basic appearance heuristics. Modern architectures, however, integrate deep learning directly into the optimization loop.

Laura Leal-Taixé et al. pioneered this integration in Learning by Tracking: Siamese CNN for Robust Target Association by utilizing a Siamese Convolutional Neural Network to extract rich features from object appearances and motion boundaries. These deep features are converted into highly accurate matching probabilities that serve as the edge costs for a linear programming tracker.

Historically, the neural network extracting features and the linear programming solver optimizing the trajectories were isolated components. This created a disconnect: the neural network was trained to minimize local classification errors, not to optimize the final global tracking result.

To bridge this gap, Shuai Li et al. developed a fully differentiable tracking framework in Learning of Global Objective for Network Flow in Multi-Object Tracking. By framing tracking as a bi-level optimization task, they enabled the system to backpropagate tracking errors directly through the network flow solver. This allows the neural network to learn feature representations that are explicitly tuned to maximize global trajectory consistency, resulting in unparalleled robustness in crowded, highly occluded environments.

Key Foundational Work

Collective Inference on Markov Models for Modeling Bird Migration (2007) — contributed 2 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_global_trajectory_optimization_6fc8ea02_v2,
  title = {global trajectory optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-trajectory-optimization/rdr_6fc8ea0269264632a286fb43a47a5086/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake