Lifted Disjoint Paths with Application in Multiple Object Tracking

Abstract

We present an extension to the disjoint paths problem in which additional \emph{lifted} edges are introduced to provide path connectivity priors. We call the resulting optimization problem the lifted disjoint paths problem. We show that this problem is NP-hard by reduction from integer multicommodity flow and 3-SAT. To enable practical global optimization, we propose several classes of linear inequalities that produce a high-quality LP-relaxation. Additionally, we propose efficient cutting plane algorithms for separating the proposed linear inequalities. The lifted disjoint path problem is a natural model for multiple object tracking and allows an elegant mathematical formulation for long range temporal interactions. Lifted edges help to prevent id switches and to re-identify persons. Our lifted disjoint paths tracker achieves nearly optimal assignments with respect to input detections. As a consequence, it leads on all three main benchmarks of the MOT challenge, improving significantly over state-of-the-art.

ICML 2020, Codebase available at https://github.com/AndreaHor/LifT_Solver

Cited by in corpus (16)

• FairMOT: On the Fairness of Detection and Re-Identification in Multiple Object Tracking
• ByteTrack: Multi-Object Tracking by Associating Every Detection Box
• SimpleTrack: Understanding and Rethinking 3D Multi-object Tracking
• Quasi-Dense Similarity Learning for Multiple Object Tracking
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking
• Towards Frame Rate Agnostic Multi-Object Tracking
• Learning a Proposal Classifier for Multiple Object Tracking
• Local Metrics for Multi-Object Tracking
• GIAOTracker: A comprehensive framework for MCMOT with global information and optimizing strategies in VisDrone 2021
• Split and Connect: A Universal Tracklet Booster for Multi-Object Tracking
• Looking Beyond Two Frames: End-to-End Multi-Object Tracking Using Spatial and Temporal Transformers
• Enhancing the Association in Multi-Object Tracking via Neighbor Graph
• Online Multiple Object Tracking with Cross-Task Synergy
• Multiple Object Tracking with Correlation Learning
• Uncertainty in Minimum Cost Multicuts for Image and Motion Segmentation
• A Generic Object Re-identification System for Short Videos