Online Multi-Object Tracking by Quadratic Pseudo-Boolean Optimization

Long Lan, Dacheng Tao, Chen Gong, Naiyang Guan, Zhigang Luo

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.

The proposed online MOT framework consists of three main stages: affinity measurement, interaction modeling (collision and overlapping), and track state 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.

Ablation study showing the impact of collision and overlapping interaction terms on MOTA and MOTP metrics.

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

Abstract

Online multi-object tracking (MOT) is challenging: frame-by-frame matching of detection hypotheses to the correct trackers can be difficult. The Hungarian algorithm is the most commonly used online MOT data association method due to its rapid assignment; however, the Hungarian algorithm simply considers associations based on an affinity model. For crowded scenarios, frequently occurring interactions between objects complicate associations, and affinity-based methods usually fail in these scenarios. Here we introduce quadratic pseudo-Boolean optimization (QPBO) to an online MOT model to analyze frequent interactions. Specifically, we formulate two useful interaction types as pairwise potentials in QPBO, a design that benefits our model by exploiting informative interactions and allowing our online tracker to handle complex scenes. The auxiliary interactions result in a non-submodular QPBO, so we accelerate our online tracker by solving the model with a graph cut combined with a simple heuristic method. This combination achieves a reasonable local optimum and, importantly, implements the tracker efficiently. Extensive experiments on publicly available datasets from both static and moving cameras demonstrate the superiority of our method.
BibTeX
@inproceedings{lan2016online,
  author = {Long Lan and Dacheng Tao and Chen Gong and Naiyang Guan and Zhigang Luo},
  title = {{Online Multi-Object Tracking by Quadratic Pseudo-Boolean Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure