Lifted Disjoint Paths with Application in Multiple Object Tracking
This work addresses identity switches and re-identification in multiple object tracking, which is crucial for applications like surveillance and autonomous driving, representing a novel method for a known bottleneck.
The authors tackled the multiple object tracking problem by introducing lifted edges to the disjoint paths problem, which helps prevent identity switches and re-identify persons. Their tracker achieves nearly optimal assignments and leads on all three main MOT challenge benchmarks, showing significant improvements over state-of-the-art methods.
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.