A Hybrid Data Association Framework for Robust Online Multi-Object Tracking

Min Yang, Yuwei Wu, Yunde Jia

Abstract

Global optimization algorithms have shown impressive performance in data-association based multi-object tracking, but handling online data remains a difficult hurdle to overcome. In this paper, we present a hybrid data association framework with a min-cost multi-commodity network flow for robust online multi-object tracking. We build local target-specific models interleaved with global optimization of the optimal data association over multiple video frames. More specifically, in the min-cost multi-commodity network flow, the target-specific similarities are online learned to enforce the local consistency for reducing the complexity of the global data association. Meanwhile, the global data association taking multiple video frames into account alleviates irrecoverable errors caused by the local data association between adjacent frames. To ensure the efficiency of online tracking, we give an efficient near-optimal solution to the proposed min-cost multi-commodity flow problem, and provide the empirical proof of its sub-optimality. The comprehensive experiments on real data demonstrate the superior tracking performance of our approach in various challenging situations.

Introduction: The Local vs. Global Dilemma

Multi-Object Tracking (MOT) typically follows two paradigms: local and global association. Local association links detections frame-by-frame, which is computationally efficient and suitable for real-time applications. However, it is prone to failure during occlusions or noisy detections, often resulting in identity switches (IDS). Conversely, global association optimizes trajectories over an entire video batch. While robust, this approach is typically "offline," introducing significant latency and scaling poorly as the number of objects increases.

This paper introduces a hybrid framework that bridges the gap between these two paradigms. By formulating tracking as a min-cost multi-commodity network flow problem within a sliding temporal window, the authors achieve the robustness of global optimization with the low latency required for online tracking.

A Hybrid Data Association Framework

The core of the proposed method is a hybrid association strategy that combines target-specific local consistency with global optimization over a short temporal window.

Conceptual comparison of local, global, and hybrid association paradigms.

Min-Cost Multi-Commodity Flow

The system models detections as nodes in a graph where edges represent potential movements. Unlike standard flow models where all units are identical, this framework treats each existing trajectory as a unique "commodity." This allows the use of target-specific costs, where the cost for a specific target to move to a detection is based on its unique appearance history. A "dummy commodity" is also introduced to handle new objects entering the scene.

Online Appearance Learning and Optimization

To maintain discriminative power, the framework uses region-based CNN features and an incremental triplet-loss update. As the tracker follows an object, it constantly updates its model to distinguish the target from the background and other nearby objects. To solve the NP-hard multi-commodity flow problem efficiently, the authors employ Dantzig-Wolfe decomposition and Column Generation, providing a near-optimal solution rapidly.

Key Insights: Finding the "Goldilocks" Window

A critical finding of this research is the impact of the temporal window size ($\Delta t$) on tracking performance. The authors identified a "sweet spot" around 10 to 15 frames.

Tracking performance metrics (MOTA, IDS, FG) as a function of the temporal window length.

As shown in the performance plots, a window that is too small behaves like local association, suffering from high identity switches. Conversely, a window that is too large can degrade performance because online appearance models may become less accurate when compared to detections too far in the future. At the optimal window size, the framework achieves a balance that maximizes MOTA (Multiple Object Tracking Accuracy) while minimizing Identity Switches (IDS) and Fragments (FG).

Experimental Results

The framework was evaluated on the PETS 2009 and MOTChallenge 2015 benchmarks. On MOTChallenge 2015, the "HybridDAT" method achieved a MOTA of 35.0%, outperforming several state-of-the-art methods. Notably, the method significantly improved identity stability; on the PETS dataset, increasing the window size from 1 (purely local) to 10 slashed identity switches by more than half. Furthermore, the Column Generation solver proved to be roughly 3.4x faster than standard Integer Linear Programming (ILP) solvers in crowded scenes.

Conclusion

The hybrid data association framework effectively combines the strengths of local and global tracking. By leveraging target-specific appearance models within a computationally efficient multi-commodity flow optimization, it provides a robust solution for online multi-object tracking in complex environments. Future work may involve integrating more complex motion and shape cues to further enhance robustness in extremely crowded scenarios where appearance alone may be ambiguous.

Summary updated

Abstract

Global optimization algorithms have shown impressive performance in data-association based multi-object tracking, but handling online data remains a difficult hurdle to overcome. In this paper, we present a hybrid data association framework with a min-cost multi-commodity network flow for robust online multi-object tracking. We build local target-specific models interleaved with global optimization of the optimal data association over multiple video frames. More specifically, in the min-cost multi-commodity network flow, the target-specific similarities are online learned to enforce the local consistency for reducing the complexity of the global data association. Meanwhile, the global data association taking multiple video frames into account alleviates irrecoverable errors caused by the local data association between adjacent frames. To ensure the efficiency of online tracking, we give an efficient near-optimal solution to the proposed min-cost multi-commodity flow problem, and provide the empirical proof of its sub-optimality. The comprehensive experiments on real data demonstrate the superior tracking performance of our approach in various challenging situations.
BibTeX
@article{yang2017hybrid,
  author = {Min Yang and Yuwei Wu and Yunde Jia},
  title = {{A Hybrid Data Association Framework for Robust Online Multi-Object Tracking}},
  journal = {IEEE Trans. Image Process.},
  year = {2017},
  url = {https://openreview.net/forum?id=3silinojaO},
}
Figure