The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Globally-optimal greedy algorithms for tracking a variable number of objects
Abstract
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
Network Flows: Theory, Algorithms, and Applications.
Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1994) · Journal of the Operational Research Society · doi:10.2307/2583863 · Cited by 8,121
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988
A discriminatively trained, multiscale, deformable part model
Felzenszwalb, P. F., McAllester, D., & Ramanan, D. (2008) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2008.4587597 · Cited by 2,972
Self-citationSonar tracking of multiple targets using joint probabilistic data association
Fortmann, T. E., Bar‐Shalom, Y., & Scheffe, M. M. (1983) · IEEE Journal of Oceanic Engineering · doi:10.1109/joe.1983.1145560 · Cited by 1,474
Pedestrian detection: A benchmark
Dollár, P., Wojek, C., Schiele, B., & Perona, P. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2009.5206631 · Cited by 1,351
Multiple Object Tracking Using K-Shortest Paths Optimization
Berclaz, J., Fleuret, F., Turetken, E., & Fua, P. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.21 · Cited by 1,015
Global data association for multi-object tracking using network flows
Zhang, L., Li, Y., & Nevatia, R. (2008) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2008.4587584 · Cited by 945
BraMBLe: a Bayesian multiple-blob tracker
Isard, M., & MacCormick, J. (2002) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2001.937594 · Cited by 633
Depth and Appearance for Mobile Scene Analysis
Ess, A., Leibe, B., & Van Gool, L. (2007) · 2007 IEEE 11th International Conference on Computer Vision · doi:10.1109/iccv.2007.4409092 · Cited by 540
The Hungarian Method for the Assignment Problem
Kuhn, H. W. (2009) · Springer eBooks · doi:10.1007/978-3-540-68279-0_2 · Cited by 454
Improving Data Association by Joint Modeling of Pedestrian Trajectories and Groupings
Pellegrini, S., Ess, A., & Gool, L. V. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15549-9_33 · Cited by 387
An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm
Goldberg, A. V. (1997) · Journal of Algorithms · doi:10.1006/jagm.1995.0805 · Cited by 386
A Linear Programming Approach for Multiple Object Tracking
Jiang, H., Fels, S., & Little, J. J. (2007) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2007.383180 · Cited by 323
Coupled Detection and Trajectory Estimation for Multi-Object Tracking
Leibe, B., Konrad Schindler, B., & Gool, L. V. (2007) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2007.4408936 · Cited by 281
Multi-Object Tracking Through Simultaneous Long Occlusions and Split-Merge Conditions
Perera, A. G. A., Srinivas, C., Hoogs, A. J., Brooksby, G. W., & Hu, W. (2006) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2006.195 · Cited by 262
Xing, J., Ai, H., & Lao, S. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2009.5206745 · Cited by 219
Robust Visual Tracking for Multiple Targets
Cai, Y., de Freitas, N., & Little, J. J. (2006) · Lecture notes in computer science · doi:10.1007/11744085_9 · Cited by 192
Evaluating Multi-Object Tracking
Smith, K., Gática-Pérez, D., Odobez, J., & Ba, S. (2006) · 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops · doi:10.1109/cvpr.2005.453 · Cited by 165
Multiple Target Tracking in World Coordinate with Single, Minimally Calibrated Camera
Choi, W., & Savarese, S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15561-1_40 · Cited by 132
PETS Metrics: On-Line Performance Evaluation Service
Young, D. P., & Ferryman, J. M. (2006) · doi:10.1109/vspets.2005.1570931 · Cited by 115
Multiple object tracking using flow linear programming
Berclaz, J., Fleuret, F., & Fua, P. (2009) · doi:10.1109/pets-winter.2009.5399488 · Cited by 112
Estimating Tracking Sources and Sinks
Stauffer, C. (2003) · IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw.2003.10036 · Cited by 108
Globally Optimal Multi-target Tracking on a Hexagonal Lattice
Andriyenko, A., & Schindler, K. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15549-9_34 · Cited by 98
Target tracking with incomplete detection
Ma, Y., Yu, Q., & Cohen, I. (2009) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2009.01.002 · Cited by 30
Evaluation of Algorithms for Tracking Multiple Objects in Video
Perera, A. G. A., Hoogs, A. J., Srinivas, C., Brooksby, G. W., & Hu, W. (2006) · doi:10.1109/aipr.2006.23 · Cited by 13
Research works printed but not linked: 2
- isard, 2001, Bramble: A bayesian multipleblob tracker, ICCV
- andriyenko, 2010, Globally optimal multitarget tracking on a hexagonal lattice, ECCV
Cited by
Sorted by citations
Simple online and realtime tracking with a deep association metric
Wojke, N., Bewley, A., & Paulus, D. (2017) · 2017 IEEE International Conference on Image Processing (ICIP) · doi:10.1109/icip.2017.8296962 · Cited by 5,286
Simple online and realtime tracking
Bewley, A., Ge, Z., Ott, L., Ramos, F., & Upcroft, B. (2016) · 2016 IEEE International Conference on Image Processing (ICIP) · doi:10.1109/icip.2016.7533003 · Cited by 4,433
Kalal, Z., Mikolajczyk, K., & Matas, J. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.239 · Cited by 3,332
Performance Measures and a Data Set for Multi-target, Multi-camera Tracking
Ristani, E., Solera, F., Zou, R., Cucchiara, R., & Tomasi, C. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-48881-3_2 · Cited by 3,104
Detection and tracking meet drones challenge
Zhu, P., Wen, L., Du, D., Bian, X., Fan, H., Hu, Q., & Ling, H. (2022) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2021.3119563 · Cited by 1,336
Metadata
- Authors
- Pirsiavash, H., Ramanan, D., & Fowlkes, C. C.
- Affiliations
- University of California, Irvine (US)
- Venue
- CVPR 2011
- Publisher
- IEEE
- Published
- 2011-06
- Pages
- 1201-1208
- OpenAlex
- W2016135469
- Cited by
- 790
- References
- 26
- Citations by year
- 2026: 4 · 2025: 14 · 2024: 17 · 2023: 37 · 2022: 39 · 2021: 59 · 2020: 73 · 2019: 87 · 2018: 95 · 2017: 79 · 2016: 90 · 2015: 81 · 2014: 48 · 2013: 40 · 2012: 22
- FWCI
- 27.44
- Type
- conference paper
- Language
- en
- Open access
- closed
- Funders
- Office of Naval Research
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Video Surveillance and Tracking Methods
- Physical Sciences › Engineering › Automotive Engineering › Autonomous Vehicle Technology and Safety
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Vision and Imaging
- Keywords
- multi-target tracking, video sequences, greedy algorithm, track initialization, flow networks, shortest path, dynamic programming, non-maximum suppression, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
