Tracking Objects with Higher Order Interactions via Delayed Column Generation

Shaofei Wang, Steffen Wolf, Charless Fowlkes, Julian Yarkony
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1132-1140, 2017.

Abstract

We study the problem of multi-target tracking and data association in video. We formulate this in terms of selecting a subset of high-quality tracks subject to the constraint that no pair of selected tracks is associated with a common detection (of an object). This objective is equivalent to the classic NP-hard problem of finding a maximum-weight set packing (MWSP) where tracks correspond to sets and is made further difficult since the number of candidate tracks grows exponentially in the number of detections. We present a relaxation of this combinatorial problem that uses a column generation formulation where the pricing problem is solved via dynamic programming to efficiently explore the space of tracks. We employ row generation to tighten the bound in such a way as to preserve efficient inference in the pricing problem. We show the practical utility of this algorithm for pedestrian and particle tracking.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-wang17c, title = {{Tracking Objects with Higher Order Interactions via Delayed Column Generation}}, author = {Wang, Shaofei and Wolf, Steffen and Fowlkes, Charless and Yarkony, Julian}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {1132--1140}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/wang17c/wang17c.pdf}, url = {https://proceedings.mlr.press/v54/wang17c.html}, abstract = {We study the problem of multi-target tracking and data association in video. We formulate this in terms of selecting a subset of high-quality tracks subject to the constraint that no pair of selected tracks is associated with a common detection (of an object). This objective is equivalent to the classic NP-hard problem of finding a maximum-weight set packing (MWSP) where tracks correspond to sets and is made further difficult since the number of candidate tracks grows exponentially in the number of detections. We present a relaxation of this combinatorial problem that uses a column generation formulation where the pricing problem is solved via dynamic programming to efficiently explore the space of tracks. We employ row generation to tighten the bound in such a way as to preserve efficient inference in the pricing problem. We show the practical utility of this algorithm for pedestrian and particle tracking.} }
Endnote
%0 Conference Paper %T Tracking Objects with Higher Order Interactions via Delayed Column Generation %A Shaofei Wang %A Steffen Wolf %A Charless Fowlkes %A Julian Yarkony %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-wang17c %I PMLR %P 1132--1140 %U https://proceedings.mlr.press/v54/wang17c.html %V 54 %X We study the problem of multi-target tracking and data association in video. We formulate this in terms of selecting a subset of high-quality tracks subject to the constraint that no pair of selected tracks is associated with a common detection (of an object). This objective is equivalent to the classic NP-hard problem of finding a maximum-weight set packing (MWSP) where tracks correspond to sets and is made further difficult since the number of candidate tracks grows exponentially in the number of detections. We present a relaxation of this combinatorial problem that uses a column generation formulation where the pricing problem is solved via dynamic programming to efficiently explore the space of tracks. We employ row generation to tighten the bound in such a way as to preserve efficient inference in the pricing problem. We show the practical utility of this algorithm for pedestrian and particle tracking.
APA
Wang, S., Wolf, S., Fowlkes, C. & Yarkony, J.. (2017). Tracking Objects with Higher Order Interactions via Delayed Column Generation. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:1132-1140 Available from https://proceedings.mlr.press/v54/wang17c.html.

Related Material