Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow

Asad A. Butt, Robert T. Collins; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013, pp. 1846-1853

Abstract


We propose a method for global multi-target tracking that can incorporate higher-order track smoothness constraints such as constant velocity. Our problem formulation readily lends itself to path estimation in a trellis graph, but unlike previous methods, each node in our network represents a candidate pair of matching observations between consecutive frames. Extra constraints on binary flow variables in the graph result in a problem that can no longer be solved by min-cost network flow. We therefore propose an iterative solution method that relaxes these extra constraints using Lagrangian relaxation, resulting in a series of problems that ARE solvable by min-cost flow, and that progressively improve towards a high-quality solution to our original optimization problem. We present experimental results showing that our method outperforms the standard network-flow formulation as well as other recent algorithms that attempt to incorporate higher-order smoothness constraints.

Related Material


[pdf]
[bibtex]
@InProceedings{Butt_2013_CVPR,
author = {Butt, Asad A. and Collins, Robert T.},
title = {Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2013}
}