arXiv (Cornell University) · 2020 · 84 citations · 0 references
ComputingComputer ScienceAlgorithmsComputer VisionMachine VisionAssignment ProblemsConstraint ProgrammingConstraint SatisfactionInteger ProgrammingObject DetectionVisual TrackingDisjoint PathsDisjoint Paths ProblemEfficient Global OptimizationInteger FlowMulti-object TrackingMulti-target TrackingMulticommodity FlowMultiple Object Tracking
The lifted disjoint path problem is a natural model for multiple object tracking and allows an elegant mathematical formulation for long‑range temporal interactions. The authors extend the disjoint paths problem by adding lifted edges to provide path‑connectivity priors and propose linear inequalities that yield a high‑quality LP relaxation to enable practical global optimization. The lifted disjoint paths problem is defined by adding lifted edges to the standard formulation, and the authors develop efficient cutting‑plane algorithms for these linear inequalities, with lifted edges preventing ID switches and enabling re‑identification. The authors prove the lifted disjoint paths problem is NP‑hard, demonstrate that their tracker achieves near‑optimal assignments on detections, and show it significantly outperforms state‑of‑the‑art on all three main MOT challenge benchmarks.
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.