Lifted Disjoint Paths with Application in Multiple Object Tracking
arXiv:2006.14550
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 (7)
- Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking
- Learning a Proposal Classifier for Multiple Object Tracking
- Local Metrics for Multi-Object Tracking
- Online Multiple Object Tracking with Cross-Task Synergy
- Enhancing the Association in Multi-Object Tracking via Neighbor Graph
- Multiple Object Tracking with Correlation Learning
- A Generic Object Re-identification System for Short Videos