Introduction
Multi-Object Tracking (MOT) typically follows the "tracking-by-detection" paradigm, where a detector identifies objects in each frame and a tracker links these detections over time. While the Hungarian algorithm has been the industry standard for online data association, it often fails in crowded environments. Its primary limitation is that it considers "affinity"—the similarity between a detection and a tracker—in isolation. In dense scenes, objects frequently overlap or collide, leading to identity switches or lost tracks when using simple affinity models. This paper introduces a robust online MOT framework that incorporates complex object interactions by formulating data association as a Quadratic Pseudo-Boolean Optimization (QPBO) problem.
Methodology
The proposed framework treats data association as a binary optimization problem. For every possible pair of (Tracker, Detection), a binary variable is assigned: 1 for a match and 0 otherwise. The system minimizes an energy function defined as:
$$E(v) = \text{Unary Costs} + \alpha(\text{Collision Interactions}) + \beta(\text{Overlapping Interactions})$$
1. Data Association Pipeline
As illustrated in the pipeline below, the process is divided into three distinct stages: Affinity, Interaction, and Update.
- Unary Term: This standard affinity model combines appearance features (SVM/LBP), motion estimation (Kalman filter), size consistency, and track reliability.
- Collision Interaction (Pairwise): To prevent a tracker from "stealing" a neighbor's detection, the system trains a temporary "auxiliary classifier" specifically to distinguish between two close-proximity objects. This high-specificity local modeling is key to resolving ambiguous matches.
- Overlapping Interaction (Pairwise): This term encourages the merging of redundant trackers. If two trackers consistently overlap in space and time, they likely represent the same physical object, and the system merges them into a single track.
2. Optimization Strategy
Because interaction terms make the problem non-submodular (NP-hard), the authors utilize QPBO combined with a simple greedy heuristic. This approach solves the majority of the graph using standard graph cuts and resolves remaining variables quickly, allowing the system to run at 3–12 frames per second (FPS).
Experimental Results
The model was evaluated on five standard MOT benchmarks, including PETS-S2L1, TUD-Crossing, and ETH-bahnhof.
Quantitative Performance
On the PETS-S2L1 dataset, the method achieved a MOTA (Multi-Object Tracking Accuracy) of 95.1%, outperforming several batch methods. The inclusion of interaction modeling significantly reduced identity switches (IDS), particularly in sequences with frequent pedestrian occlusions. The impact of these interaction terms is clearly visible in the ablation study results.
Key Insights
- Local Specificity: Training specific, temporary SVMs for colliding objects (auxiliary classifiers) provides better resolution than general person detectors.
- Efficiency: Despite the mathematical complexity of QPBO, the data association overhead is only 23% higher than the Hungarian algorithm, making it viable for real-time applications.
Conclusion
By moving beyond simple frame-to-frame matching and explicitly modeling object interactions, this QPBO-based framework achieves state-of-the-art accuracy in online MOT. While the system currently relies on traditional detectors like DPM, its modular nature allows for future integration with modern deep-learning-based detectors to further enhance performance in extremely dense environments.
Summary updated