Discrete-Continuous Energy Minimization for Multi-Target Tracking

The problem of multi-target tracking is comprised of two distinct, but tightly coupled challenges: (i) the naturally discrete problem of data association, i.e. assigning image observations to the appropriate target; (ii) the naturally continuous problem of trajectory estimation, i.e. recovering the trajectories of all targets. To go beyond simple greedy solutions for data association, recent approaches often perform multi-target tracking using discrete optimization. This has the disadvantage that trajectories need to be pre-computed or represented discretely, thus limiting accuracy. In this paper we instead formulate multi-target tracking as a discretecontinuous optimization problem that handles each aspect in its natural domain and allows leveraging powerful methods for multi-model fitting. Data association is performed using discrete optimization with label costs, yielding near optimality. Trajectory estimation is posed as a continuous fitting problem with a simple closed-form solution, which is used in turn to update the label costs. We demonstrate the accuracy and robustness of our approach with state-of-theart performance on several standard datasets.

Multi-Target Tracking by Discrete-Continuous Energy Minimization

A. Milan, K. Schindler and S. Roth
PAMI, 2016
bibtex | abstract | paper | video |

@article{Milan:2016:PAMI,
	author = {Milan, A. and Schindler, K. and Roth, S.},	
	title = {Multi-Target Tracking by Discrete-Continuous Energy Minimization},
	volume = {?},
	number = {?},
	journal = {IEEE TPAMI},
	year = {2016}
}
			

The task of tracking multiple targets is often addressed with the 
so-called tracking-by-detection paradigm, where the first step is to 
obtain a set of target hypotheses for each frame independently. Tracking 
can then be regarded as solving two separate, but tightly coupled 
problems. The first is to carry out data association, i.e. to determine 
the origin of each of the available observations. The second problem is 
to reconstruct the actual trajectories that describe the spatio-temporal 
motion pattern of each individual target. The former is inherently a 
discrete problem, while the latter should intuitively be modeled in 
continuous space. Having to deal with an unknown number of targets, 
complex dependencies, and physical constraints, both are challenging 
tasks on their own and thus most previous work focuses on one of these 
subproblems. Here, we present a multi-target tracking approach that 
explicitly models both tasks as minimization of a unified 
discrete-continuous energy function. Trajectory properties are captured 
through global label costs, a recent concept from multi-model fitting, 
which we introduce to tracking. Specifically, label costs describe 
physical properties of individual tracks, e.g. linear and angular 
dynamics, or entry and exit points. We further introduce pairwise label 
costs to describe mutual interactions between targets in order to avoid 
collisions. By choosing appropriate forms for the individual energy 
components, powerful discrete optimization techniques can be leveraged 
to address data association, while the shapes of individual trajectories 
are updated by gradient-based continuous energy minimization. The 
proposed method achieves state-of-the-art results on diverse benchmark 
sequences.
			

---

Detection- and Trajectory-Level Exclusion in Multiple Object Tracking

A. Milan, K. Schindler and S. Roth
CVPR 2013
bibtex | poster | video | data

@inproceedings{Milan:2013:DTE,
	Author = {Anton Milan and Konrad Schindler and Stefan Roth},
	Booktitle = {CVPR},
	Title = {Detection- and Trajectory-Level Exclusion in Multiple Object Tracking},
	Year = {2013}
}
			

---

Discrete-Continuous Optimization for Multi-Target Tracking

A. Andriyenko, K. Schindler and S. Roth
CVPR 2012
bibtex | poster | video | data

@inproceedings{Andriyenko:2012:DCO,
	Author = {Anton Andriyenko and Konrad Schindler and Stefan Roth},
	Booktitle = {CVPR},
	Title = {Discrete-Continuous Optimization for Multi-Target Tracking},
	Year = {2012}
}