Abstract
We study the problem of multi-target tracking and data association in video. We formulate this in terms of selecting a subset of high-quality tracks subject to the constraint that no pair of selected tracks share a common detection. This paper introduces a sophisticated optimization framework for multi-target tracking that captures complex, higher-order object dynamics (like acceleration and appearance consistency) without sacrificing global optimality. By combining delayed column generation to manage an exponential number of possible tracks with row generation to tighten mathematical bounds, the authors achieve more accurate tracking and faster convergence than previous state-of-the-art relaxation methods.
Introduction
Multi-target tracking (MTT) is the task of identifying the trajectories of multiple objects across a video sequence. Mathematically, this is often framed as a "set packing" problem: selecting a group of high-quality tracks such that no two tracks share the same detection.
The challenge is two-fold:
- Complexity: The number of possible tracks grows exponentially with the number of detections, making it impossible to list them all.
- Modeling Power: Simple first-order models only look at pairs of detections, which is computationally easy but fails to model complex motions. Higher-order models (considering 3+ detections at once) are better but traditionally lead to NP-hard optimization problems that are slow to solve or require "greedy" heuristics that lose global context.
Methods
The authors formulate tracking as an Integer Linear Program (ILP) and solve its relaxation using two main techniques:
Delayed Column Generation
Instead of considering all possible tracks upfront, the algorithm starts with a small subset. It then uses Dynamic Programming (DP) to find the "most violated" track—the one that would most improve the current solution—and adds it to the pool. This approach allows the model to incorporate sophisticated motion priors by increasing the subtrack length ($K$).
Row Generation and Branch-and-Bound
Standard linear relaxations of tracking problems are often "loose," providing poor approximations of the true integer solution. The authors introduce "triplet constraints," which enforce that among any three detections, no more than one track can pass through two or more of them. These constraints are added only as needed to tighten the bound. When triplet constraints are active, the authors use a specialized Branch-and-Bound (B&B) approach to solve the "pricing problem" efficiently.
Experimental Results
The method was evaluated on the MOT 2015 Challenge (pedestrian tracking) and the Particle Tracking Challenge (PTC).
Convergence and Accuracy
On the TUD-Campus sequence, increasing subtrack length from $K=2$ to $K=4$ improved the Multiple Object Tracking Accuracy (MOTA) from 48.5% to 49.9% and reduced identity switches from 11 to 9. Compared to baseline Lagrangian relaxation methods, this approach reached a zero duality gap (proving optimality) significantly faster, especially on difficult problem instances.
Particle Tracking
The algorithm achieved a high Jaccard score of 0.924 on the PTC dataset, successfully identifying over 6,300 tracks in a high-density environment with very few false positives.
Key Insights and Conclusion
By increasing the subtrack length ($K$), the model incorporates more sophisticated motion priors, noticeably reducing identity switches and track fragmentation. A key insight is that even though theoretical complexity is high, the number of "active" constraints and tracks needed to reach the optimum is small in real-world tracking scenarios, allowing the algorithm to converge quickly.
While the current implementation is geared toward batch (offline) processing, the efficiency gains bring the method closer to real-time applicability. Future work may explore "generalized odd set inequalities" to tighten bounds further for even more complex combinatorial scenarios.
Summary updated