Globally-optimal greedy algorithms for tracking a variable number of objects

By Hamed Pirsiavash, Deva Ramanan, Charless C. Fowlkes. Computer Vision and Pattern Recognition, 2011

888 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/417a1990a0b2017fe0b932673776a970295afa00

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

IntPhys: A Framework and Benchmark for Visual Intuitive Physics Reasoning (2018, background): “This is a well-studied problem with its own literature [51, 44, 55, 9] and challenges [32, 34].”
Online Multi-Object Tracking with Dual Matching Attention Networks (2018, background): “Numerous approaches [37,39,58,47,45,51,48] use detections from past and future frames for batch processing.”
Online Multi-Target Tracking Using Recurrent Neural Networks (2016, methodology): “Here, the problem is cast as a linear program and solved via relaxation [3, 18], shortest-path [14,16] or max-flow algorithms [4].”
Watch and learn: Semi-supervised learning of object detectors from videos (2015, methodology): “They do so at the cost of using a detector trained on additional training data, e.g., [41] uses a DPM [14] trained on images from PASCAL [13].”
High-Speed tracking-by-detection without using image information (2017, methodology): “Other approaches include using a globally optimal and locally greedy method and integer linear programming [12] and online discriminative appearance learning [3].”
Multiple object tracking: A literature review (2014, methodology): “Some examples (Zhang et al. 2008; Choi and Savarese 2012; Wu et al. 2012; Butt and Collins 2013; Pirsiavash et al. 2011) adopt this for MOT problem.”
Deep Affinity Network for Multiple Object Tracking (2018, methodology): “Recent methods in this direction cast data association into a network flow problem [42], [43], [44], [45].”
Video Instance Segmentation Tracking With a Modified VAE Architecture (2020, methodology): “Detection-based tracking [27, 67, 63, 20, 49, 13, 4, 61, 32, 42], on the other hand, generally requires objects being detected followed by a tracker that links the detection regions to form trajectories of the targets.”
Online Multi-object Tracking Using CNN-Based Single Object Tracker with Spatial-Temporal Attention Mechanism (2017, methodology): “With the development of object detection methods [8, 14, 15, 37, 38], data association [22, 39, 33, 2] has become popular for MOT.”
Motion Trajectory Segmentation via Minimum Cost Multicuts (2015, methodology): “Unlike in the multi-object tracking scenario [31, 38, 37], we assume that we are directly given long point trajectories on objects and background.”
Detection and Tracking of Occluded People (2014, methodology): “Note that the tracker of Pirsiavash et al. (2011) is also conceptually similar to the tracker used in”
Joint Graph Decomposition & Node Labeling: Problem, Algorithms, Applications (2016, background): “Multiple object tracking [3, 4, 6, 9, 17, 22, 24, 35, 36] can be seen as a task requiring two classes of decisions: For every point in an image, one needs to decide whether this point depicts an object or background.”
Unsupervised Object Discovery and Tracking in Video Collections (2015, methodology): “Conventional object tracking methods [41] usually require annotations for at least one frame [13, 15, 40], or object detectors trained for target classes in a supervised manner [1, 2, 26].”
A Unified Framework for Multi-target Tracking and Collective Activity Recognition (2012, methodology): “Note that the number of nodes in [15, 16] is usually in the order of tens or hundreds of thousands.”
Joint Graph Decomposition and Node Labeling by Local Search (2016, background): “This problem offers a common mathematical abstraction of seemingly unrelated computer vision tasks: Multiple object tracking[2, 3, 4, 7, 13, 17, 19, 29, 30] can be seen as the task of deciding, for every point in an image, whether this point depicts an object, and of deciding, for every pair of poin”