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
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
