You are here

Multiobject tracking as maximum weight independent set

TitleMultiobject tracking as maximum weight independent set
Publication TypeConference Paper
Year of Publication2011
AuthorsBrendel, W., M. R. Amer, and S. Todorovic
Conference Name2011 IEEE Conference on Computer Vision and Pattern Recognition CVPR 2011
Pagination1273 - 1280
Date Published06/2011
Conference LocationColorado Springs, CO
ISBN Number978-1-4577-0394-2

This paper addresses the problem of simultaneous tracking of multiple targets in a video. We first apply object detectors to every video frame. Pairs of detection responses from every two consecutive frames are then used to build a graph of tracklets. The graph helps transitively link the best matching tracklets that do not violate hard and soft contextual constraints between the resulting tracks. We prove that this data association problem can be formulated as finding the maximum-weight independent set (MWIS) of the graph. We present a new, polynomial-time MWIS algorithm, and prove that it converges to an optimum. Similarity and contextual constraints between object detections, used for data association, are learned online from object appearance and motion properties. Long-term occlusions are addressed by iteratively repeating MWIS to hierarchically merge smaller tracks into longer ones. Our results demonstrate advantages of simultaneously accounting for soft and hard contextual constraints in multitarget tracking. We outperform the state of the art on the benchmark datasets.