We present an approach for global multi-target tracking that integrates higher-order motion constraints such as constant velocity into a network flow framework. Our method represents tracking paths in a trellis graph where each node denotes a candidate pair of matching observations between consecutive frames. The original problem with higher-order constraints is NP-hard and cannot be solved by standard min-cost network flow. We employ an iterative solution method that relaxes these extra constraints using Lagrangian relaxation, resulting in a series of subproblems that ARE solvable by min-cost flow. The iterative procedure progressively tightens the relaxation, converging toward an optimal solution for the original problem. Experimental validation demonstrates superior performance compared to conventional network-flow approaches and competing algorithms.

Multi-target tracking aims to estimate the trajectories of multiple objects simultaneously across video frames. The tracking-by-detection paradigm first obtains per-frame detections and then solves a data association problem to link detections into trajectories. Min-cost network flow has become a popular framework for global data association, as it can be solved efficiently in polynomial time. However, standard network flow formulations only support pairwise (first-order) costs between consecutive detections, which cannot encode important motion constraints like velocity smoothness that involve three or more observations.

To overcome this limitation, we propose a trellis graph representation where nodes correspond to pairs of matched detections (observation pairs from consecutive frames) rather than individual detections. In this representation, higher-order motion constraints become pairwise constraints between trellis nodes, making them expressible in a flow framework. However, the trellis graph introduces additional consistency constraints (each detection can only participate in one pair) that violate the standard network flow structure. We handle this via Lagrangian relaxation, decomposing the intractable problem into a sequence of standard min-cost flow problems with modified edge costs.

Network flow-based tracking was popularized by Zhang et al., who showed that the minimum cost flow problem could globally optimize first-order data association costs. Subsequent works extended this framework with hierarchical association, occlusion handling, and appearance models. However, all standard flow formulations remain limited to pairwise terms. Alternative approaches for incorporating higher-order constraints include discrete optimization via CRFs and continuous optimization via trajectory smoothing, but these sacrifice the global optimality guarantees and polynomial-time solvability of network flow. Lagrangian relaxation has been applied in combinatorial optimization but is new to the multi-target tracking domain.

Given detections D_t in frame t, we construct the trellis graph as follows. Each trellis node (i, j) at time t represents a candidate matching between detection i in frame t-1 and detection j in frame t. A trellis edge connects nodes (i, j) at time t to (j, k) at time t+1, with a cost that encodes the second-order motion consistency: specifically, the deviation from constant velocity, computed as the acceleration magnitude ||v_{jk} - v_{ij}||. This representation naturally expresses velocity smoothness as a pairwise cost in the trellis graph, even though it is a higher-order constraint in the original detection graph. The key complication is the consistency constraint: each original detection must participate in exactly one incoming and one outgoing trellis node.

The consistency constraints prevent direct application of min-cost flow to the trellis graph. We handle this via Lagrangian relaxation: we move the consistency constraints into the objective function using Lagrange multipliers. For each original detection d, we introduce a multiplier lambda_d that penalizes violation of the constraint that d participates in exactly one trellis node pair. The resulting Lagrangian subproblem has the structure of a standard min-cost network flow problem with modified edge costs (original costs plus Lagrange multiplier contributions). This subproblem can be solved optimally in polynomial time using the successive shortest path algorithm. The Lagrangian dual provides a lower bound on the optimal objective value of the original problem.

We solve the Lagrangian dual using subgradient optimization. At each iteration: (1) solve the min-cost flow subproblem with current multipliers to get a lower bound and a relaxed solution; (2) project the relaxed solution to a feasible one by resolving conflicts (when a detection appears in multiple trellis nodes) using a greedy heuristic; (3) update the Lagrange multipliers using the subgradient direction with a diminishing step size. The feasible solution provides an upper bound, and the gap between upper and lower bounds measures solution quality. In practice, convergence is achieved within 20-50 iterations, and the optimality gap is typically below 1%, indicating near-optimal solutions.

We evaluate on the PETS 2009 benchmark and TUD-Stadtmitte pedestrian tracking dataset. Metrics include MOTA (Multiple Object Tracking Accuracy), MOTP (Multiple Object Tracking Precision), identity switches, and track fragmentations. Compared to standard min-cost flow (without velocity constraints), our method reduces identity switches by 25-40% and improves MOTA by 3-5 percentage points. The velocity smoothness constraint is most impactful in crowded scenes with frequent occlusions, where naive first-order association often swaps identities. Against discrete-continuous optimization methods that also model motion smoothness, our approach achieves comparable or better tracking accuracy with provable near-optimality guarantees (sub-1% gap). The runtime is approximately 3x slower than standard min-cost flow but remains tractable for practical sequences.

We have presented a Lagrangian relaxation approach for incorporating higher-order motion constraints into min-cost network flow tracking. The trellis graph representation enables expressing velocity smoothness as pairwise costs, and Lagrangian relaxation provides a principled way to handle the resulting consistency constraints. Our approach bridges the gap between efficient first-order network flow methods and expressive but intractable higher-order formulations, achieving near-optimal solutions with provable quality bounds. Future work includes extending to even higher-order constraints (e.g., curvature), integrating appearance models into the trellis framework, and scaling to large-scale tracking benchmarks.