Globally-Optimal Greedy Algorithms for Tracking a Variable Number of Objects
We analyze the computational problem of multi-object tracking in video sequences. We formulate the problem using a cost function that requires estimating the number of tracks, as well as their birth and death states. We show that the global solution can be obtained with a greedy algorithm that sequentially instantiates tracks using shortest path computations on a flow network. Greedy algorithms allow one to embed pre-processing steps, such as nonmax suppression, within the tracking algorithm. Furthermore, we give a near-optimal algorithm based on dynamic programming which runs in time linear in the number of objects and linear in the sequence length. Our algorithms are fast, simple, and scalable, allowing us to process dense input data. This results in state-of-the-art performance.
Download: pdf
Text Reference
Hamed Pirsiavash, Deva Ramanan, and Charless C. Fowlkes. Globally-optimal greedy algorithms for tracking a variable number of objects. In IEEE conference on Computer Vision and Pattern Recognition (CVPR). 2011.BibTeX Reference
@inproceedings{PirsiavashRF_CVPR_2011,author = "Pirsiavash, Hamed and Ramanan, Deva and Fowlkes, Charless C.",
booktitle = "IEEE conference on Computer Vision and Pattern Recognition (CVPR)",
year = "2011",
title = "Globally-Optimal Greedy Algorithms for Tracking a Variable Number of Objects",
tag = "people"
}