Tracking Objects with Higher Order Interactions using Delayed Column Generation
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 tracking problems in natural and biological video datasets.
Download: pdf
Text Reference
Shaofei Wang, Steffen Wolf, Charless Fowlkes, and Julian Yarkony. Tracking objects with higher order interactions using delayed column generation. In IEEE Conference on Artificial Intelligence and Statistics. 2017.BibTeX Reference
@INPROCEEDINGS{WangWFY_AISTATS_2017,author = "Wang, Shaofei and Wolf, Steffen and Fowlkes, Charless and Yarkony, Julian",
title = "Tracking Objects with Higher Order Interactions using Delayed Column Generation",
booktitle = "IEEE Conference on Artificial Intelligence and Statistics",
year = "2017"
}