Lifted Disjoint Paths with Application in Multiple Object Tracking

Andrea Hornakova, Roberto Henschel, Bodo Rosenhahn, Paul Swoboda
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:4364-4375, 2020.

Abstract

We present an extension to the disjoint paths problem in which additional 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-hornakova20a, title = {Lifted Disjoint Paths with Application in Multiple Object Tracking}, author = {Hornakova, Andrea and Henschel, Roberto and Rosenhahn, Bodo and Swoboda, Paul}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {4364--4375}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/hornakova20a/hornakova20a.pdf}, url = {https://proceedings.mlr.press/v119/hornakova20a.html}, abstract = {We present an extension to the disjoint paths problem in which additional 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.} }
Endnote
%0 Conference Paper %T Lifted Disjoint Paths with Application in Multiple Object Tracking %A Andrea Hornakova %A Roberto Henschel %A Bodo Rosenhahn %A Paul Swoboda %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-hornakova20a %I PMLR %P 4364--4375 %U https://proceedings.mlr.press/v119/hornakova20a.html %V 119 %X We present an extension to the disjoint paths problem in which additional 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.
APA
Hornakova, A., Henschel, R., Rosenhahn, B. & Swoboda, P.. (2020). Lifted Disjoint Paths with Application in Multiple Object Tracking. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:4364-4375 Available from https://proceedings.mlr.press/v119/hornakova20a.html.

Related Material