The Hungarian algorithm: optimal one-to-one assignment
Optional · supplementary note 3 of 4 for DLCV 07 · Object Tracking: From Single-Object to Multi-Object. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.
Navigate: this page and this track: Navigate: this page and this track
Four workers each quote a price for four jobs, and every job needs exactly one worker. Letting each worker in turn grab the cheapest remaining job can leave the last worker with an awful job. The Hungarian method [31] finds the cheapest complete assignment. It does so by keeping a “price tag” on every worker and every job, and it accepts a pairing only when the tags prove that no cheaper assignment can exist.
Take a square cost matrix ( tracks, detections), where is the cost of pairing track with detection . The assignment problem of the main text asks for a permutation matrix minimizing . Its dual problem assigns a potential to every track and to every detection:
where and collect the potentials. Define the reduced cost and call an edge with tight. For any assignment, , because each of the chosen pairs satisfies and every track and detection appears exactly once. If an assignment uses only tight edges, equality holds and it must be optimal. The algorithm searches for exactly this certificate:
- Keep feasible potentials and a partial matching on tight edges.
- Pick an unmatched track and grow an alternating tree: from a track, follow tight edges to detections; from a matched detection, follow its matching edge back to its track.
- If the tree reaches an unmatched detection, flip the edges along that path (matched become unmatched and the reverse). The matching grows by one pair.
- Otherwise let be the smallest reduced cost from a reached track to an unreached detection. Add to the potentials of reached tracks and subtract it from those of reached detections. Feasibility is kept, and at least one new tight edge appears. Go back to step 2.
Each of the augmentations costs on a dense matrix, hence in total. Tens to hundreds of objects per frame are therefore cheap. The method is exact for the cost you give it; it does not look at other frames, so a poor cost matrix still yields a poor matching.
Rectangular and gated cases. With the solver returns pairs and leaves the rest unmatched; this is equivalent to padding with dummy rows or columns. SciPy’s linear_sum_assignment accepts rectangular matrices directly and implements a modified Jonker–Volgenant shortest-augmenting-path algorithm [54], [55]. The associate function above rejects over-threshold pairs after solving. An alternative is to make forbidden pairs very expensive inside the problem, so that the solver prefers to keep as many valid pairs as possible; the two can disagree, as the last lines of the snippet show.
The snippet implements the four steps (one track added at a time) and checks it against SciPy on a matrix whose entries are the numbers 1 to 16.
Code · Python · 59 lines
import numpy as np
from scipy.optimize import linear_sum_assignment
def hungarian(C):
"""Hungarian method (shortest augmenting paths, dual potentials); needs rows <= cols."""
n, m = C.shape
u, v = np.zeros(n + 1), np.zeros(m + 1) # row and column potentials (index 0 unused)
p = np.zeros(m + 1, int) # p[j] = row currently matched to column j
way = np.zeros(m + 1, int) # predecessor of column j in the search tree
for i in range(1, n + 1): # add one row at a time
p[0], j0 = i, 0
minv, used = np.full(m + 1, np.inf), np.zeros(m + 1, bool)
while True: # grow the alternating tree
used[j0] = True
i0, delta = p[j0], np.inf
for j in range(1, m + 1):
if not used[j]:
cur = C[i0 - 1, j - 1] - u[i0] - v[j] # reduced cost of edge (i0, j)
if cur < minv[j]:
minv[j], way[j] = cur, j0
if minv[j] < delta:
delta, j1 = minv[j], j
for j in range(m + 1): # move the duals by delta
if used[j]:
u[p[j]] += delta; v[j] -= delta
else:
minv[j] -= delta
j0 = j1
if p[j0] == 0:
break # reached a free column
while j0: # flip the alternating path
j1 = way[j0]; p[j0] = p[j1]; j0 = j1
return [(int(p[j]) - 1, j - 1) for j in range(1, m + 1) if p[j]], u[1:], v[1:]
C = np.array([[3., 12, 4, 11], [1, 5, 8, 6], [15, 13, 7, 10], [14, 9, 2, 16]])
pairs, u, v = hungarian(C)
rows, cols = linear_sum_assignment(C)
print("ours :", sorted(pairs), "cost", sum(C[i, j] for i, j in pairs))
print("scipy:", list(zip(rows.tolist(), cols.tolist())), "cost", C[rows, cols].sum())
print("duals: u", u, "v", v, "sum", u.sum() + v.sum())
print("min reduced cost", (C - u[:, None] - v[None, :]).min())
# greedy: repeatedly take the cheapest remaining pair
G, total = C.copy(), 0.0
for _ in range(4):
i, j = np.unravel_index(np.argmin(G), G.shape)
total += G[i, j]; G[i, :] = np.inf; G[:, j] = np.inf
print("greedy cost", total)
# rectangular: 4 tracks, 3 detections -> three pairs, one track left over
r3, c3 = linear_sum_assignment(C[:, :3])
print("rectangular:", list(zip(r3.tolist(), c3.tolist())), "cost", C[r3, c3].sum())
# gating inside the problem: forbidden pairs get a huge cost, then are dropped
Cg, gate = np.array([[0.50, 0.65], [0.30, 0.55]]), 0.6
r, c = linear_sum_assignment(Cg)
print("reject afterwards:", [(i, j) for i, j in zip(r.tolist(), c.tolist()) if Cg[i, j] <= gate])
r, c = linear_sum_assignment(np.where(Cg > gate, 1e6, Cg))
print("gate inside :", [(i, j) for i, j in zip(r.tolist(), c.tolist()) if Cg[i, j] <= gate])Both solvers return the pairs (0, 0), (1, 1), (2, 3), (3, 2) with total cost 20; the greedy rule costs 25. The potentials are and , whose sum is also 20, and the smallest reduced cost is 0, so the dual certificate and the assignment meet. Dropping the last detection (4 tracks, 3 detections) gives three pairs of total cost 10 and leaves track 2 unmatched. In the gating example with threshold 0.6, rejecting afterwards keeps one pair, (1, 0), while the gate-inside version keeps two, (0, 0) and (1, 1): the cheapest full matching is with total 0.95 against 1.05 for the other one, and rejecting afterwards then discards its over-threshold pair (0, 1).
References
- Shyandram, “物件追蹤Object Tracking 簡介” (Introduction to object tracking), Medium post (in Traditional Chinese), 2023; updated 2026. link
- G. Ciaparrone, F. Luque Sánchez, S. Tabik, L. Troiano, R. Tagliaferri and F. Herrera, “Deep learning in video multi-object tracking: A survey,” Neurocomputing, 2020. arXiv:1907.12740
- W. Luo, J. Xing, A. Milan, X. Zhang, W. Liu and T.-K. Kim, “Multiple object tracking: A literature review,” Artificial Intelligence, vol. 293, 2021 (arXiv 2014). arXiv:1409.7618
- M. Adžemović, “Deep learning-based multi-object tracking: A comprehensive survey from foundations to state-of-the-art,” arXiv:2506.13457, 2025. arXiv
- S. M. Marvasti-Zadeh, L. Cheng, H. Ghanei-Yakhdan and S. Kasaei, “Deep learning for visual tracking: A comprehensive survey,” IEEE Transactions on Intelligent Transportation Systems, vol. 23, 2022. arXiv:1912.00535
- J. Thangavel (Kugarajeevan), T. Kokul, A. Ramanan and S. Fernando, “Transformers in single object tracking: An experimental survey,” IEEE Access, vol. 11, 2023. arXiv:2302.11867
- M. Ye, J. Shen, G. Lin, T. Xiang, L. Shao and S. C. H. Hoi, “Deep learning for person re-identification: A survey and outlook,” IEEE TPAMI, vol. 44, 2022. arXiv:2001.04193
- J. Luiten, A. Ošep, P. Dendorfer, P. Torr, A. Geiger, L. Leal-Taixé and B. Leibe, “HOTA: A higher order metric for evaluating multi-object tracking,” International Journal of Computer Vision, 2020. arXiv:2009.07736
- K. Bernardin and R. Stiefelhagen, “Evaluating multiple object tracking performance: The CLEAR MOT metrics,” EURASIP Journal on Image and Video Processing, 2008. doi
- E. Ristani, F. Solera, R. S. Zou, R. Cucchiara and C. Tomasi, “Performance measures and a data set for multi-target, multi-camera tracking,” ECCV Workshop on Benchmarking Multi-Target Tracking, 2016. arXiv:1609.01775
- K. Peng, A. Mathur and A. Narayanan, “Mitigating dataset harms requires stewardship: Lessons from 1000 papers,” arXiv:2108.02922, 2021. arXiv
- L. Zheng, L. Shen, L. Tian, S. Wang, J. Wang and Q. Tian, “Scalable person re-identification: A benchmark,” ICCV, 2015. doi
- L. Wei, S. Zhang, W. Gao and Q. Tian, “Person transfer GAN to bridge domain gap for person re-identification,” CVPR, 2018. arXiv:1711.08565
- H. Luo, Y. Gu, X. Liao, S. Lai and W. Jiang, “Bag of tricks and a strong baseline for deep person re-identification,” CVPR Workshops, 2019. arXiv:1903.07071
- M. Wieczorek, B. Rychalska and J. Dąbrowski, “On the unreasonable effectiveness of centroids in image retrieval,” arXiv:2104.13643, 2021. arXiv
- S. Li, L. Sun and Q. Li, “CLIP-ReID: Exploiting vision-language model for image re-identification without concrete text labels,” AAAI, 2023. arXiv:2211.13977
- D. S. Bolme, J. R. Beveridge, B. A. Draper and Y. M. Lui, “Visual object tracking using adaptive correlation filters,” CVPR, 2010. doi
- J. F. Henriques, R. Caseiro, P. Martins and J. Batista, “High-speed tracking with kernelized correlation filters,” IEEE TPAMI, vol. 37, 2015. arXiv:1404.7584
- L. Bertinetto, J. Valmadre, J. F. Henriques, A. Vedaldi and P. H. S. Torr, “Fully-convolutional Siamese networks for object tracking,” arXiv:1606.09549, 2016 (ECCV 2016 workshops). arXiv
- B. Li, J. Yan, W. Wu, Z. Zhu and X. Hu, “High performance visual tracking with Siamese region proposal network,” CVPR, 2018. doi
- B. Ye, H. Chang, B. Ma, S. Shan and X. Chen, “Joint feature learning and relation modeling for tracking: A one-stream framework” (OSTrack), ECCV, 2022. arXiv:2203.11991
- X. Chen, H. Peng, D. Wang, H. Lu and H. Hu, “SeqTrack: Sequence to sequence learning for visual object tracking,” CVPR, 2023 (the arXiv entry was later extended as SeqTrackv2). arXiv:2304.14394
- N. Ravi, V. Gabeur, Y.-T. Hu, R. Hu, C. Ryali, T. Ma et al., “SAM 2: Segment anything in images and videos,” ICLR, 2025. arXiv:2408.00714
- C.-Y. Yang, H.-W. Huang, W. Chai, Z. Jiang and J.-N. Hwang, “SAMURAI: Adapting segment anything model for zero-shot visual tracking with motion-aware memory,” arXiv:2411.11922, 2024. arXiv
- N. Carion, L. Gustafson, Y.-T. Hu et al., “SAM 3: Segment anything with concepts,” ICLR, 2026. arXiv:2511.16719
- Y. Wu, J. Lim and M.-H. Yang, “Object tracking benchmark,” IEEE TPAMI, vol. 37, 2015. doi
- H. Fan, L. Lin, F. Yang, P. Chu, G. Deng, S. Yu et al., “LaSOT: A high-quality benchmark for large-scale single object tracking,” CVPR, 2019. arXiv:1809.07845
- L. Huang, X. Zhao and K. Huang, “GOT-10k: A large high-diversity benchmark for generic object tracking in the wild,” IEEE TPAMI, vol. 43, 2021. arXiv:1810.11981
- M. Müller, A. Bibi, S. Giancola, S. Al-Subaihi and B. Ghanem, “TrackingNet: A large-scale dataset and benchmark for object tracking in the wild,” arXiv:1803.10794, 2018 (ECCV 2018). arXiv
- R. E. Kalman, “A new approach to linear filtering and prediction problems,” Journal of Basic Engineering, vol. 82, no. 1, pp. 35–45, 1960. doi
- H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, pp. 83–97, 1955. doi
- A. Bewley, Z. Ge, L. Ott, F. Ramos and B. Upcroft, “Simple online and realtime tracking,” ICIP, 2016. arXiv:1602.00763
- N. Wojke, A. Bewley and D. Paulus, “Simple online and realtime tracking with a deep association metric,” ICIP, 2017. doi
- Y. Zhang, P. Sun, Y. Jiang, D. Yu, F. Weng, Z. Yuan, P. Luo, W. Liu and X. Wang, “ByteTrack: Multi-object tracking by associating every detection box,” ECCV, 2022. arXiv:2110.06864
- J. Cao, J. Pang, X. Weng, R. Khirodkar and K. Kitani, “Observation-centric SORT: Rethinking SORT for robust multi-object tracking,” CVPR, 2023. arXiv:2203.14360
- N. Aharon, R. Orfaig and B.-Z. Bobrovsky, “BoT-SORT: Robust associations multi-pedestrian tracking,” arXiv:2206.14651, 2022. arXiv
- Z. Wang, L. Zheng, Y. Liu, Y. Li and S. Wang, “Towards real-time multi-object tracking” (JDE), ECCV, 2020. arXiv:1909.12605
- Y. Zhang, C. Wang, X. Wang, W. Zeng and W. Liu, “FairMOT: On the fairness of detection and re-identification in multiple object tracking,” IJCV, 2021. arXiv:2004.01888
- P. Bergmann, T. Meinhardt and L. Leal-Taixé, “Tracking without bells and whistles” (Tracktor), ICCV, 2019. arXiv:1903.05625
- F. Zeng, B. Dong, Y. Zhang, T. Wang, X. Zhang and Y. Wei, “MOTR: End-to-end multiple-object tracking with transformer,” ECCV, 2022. arXiv:2105.03247
- Y. Zhang, T. Wang and X. Zhang, “MOTRv2: Bootstrapping end-to-end multi-object tracking by pretrained object detectors,” CVPR, 2023. arXiv:2211.09791
- R. Gao, J. Qi and L. Wang, “Multiple object tracking as ID prediction” (MOTIP), CVPR, 2025. arXiv:2403.16848
- S. Li, T. Fischer, L. Ke, H. Ding, M. Danelljan and F. Yu, “OVTrack: Open-vocabulary multiple object tracking,” CVPR, 2023. arXiv:2304.08408
- A. Milan, L. Leal-Taixé, I. Reid, S. Roth and K. Schindler, “MOT16: A benchmark for multi-object tracking,” arXiv:1603.00831, 2016 (MOT16/MOT17). arXiv
- P. Dendorfer, H. Rezatofighi, A. Milan, J. Shi, D. Cremers, I. Reid, S. Roth, K. Schindler and L. Leal-Taixé, “MOT20: A benchmark for multi object tracking in crowded scenes,” arXiv:2003.09003, 2020. arXiv
- P. Sun, J. Cao, Y. Jiang, Z. Yuan, S. Bai, K. Kitani and P. Luo, “DanceTrack: Multi-object tracking in uniform appearance and diverse motion,” CVPR, 2022. arXiv:2111.14690
- Y. Cui, C. Zeng, X. Zhao, Y. Yang, G. Wu and L. Wang, “SportsMOT: A large multi-object tracking dataset in multiple sports scenes,” ICCV, 2023. arXiv:2304.05170
- F. Yu, H. Chen, X. Wang, W. Xian, Y. Chen, F. Liu, V. Madhavan and T. Darrell, “BDD100K: A diverse driving dataset for heterogeneous multitask learning,” CVPR, 2020. arXiv:1805.04687
- C. Doersch, Y. Yang, M. Vecerik, D. Gokay, A. Gupta, Y. Aytar et al., “TAPIR: Tracking any point with per-frame initialization and temporal refinement,” ICCV, 2023. arXiv:2306.08637
- N. Karaev, I. Rocco, B. Graham, N. Neverova, A. Vedaldi and C. Rupprecht, “CoTracker: It is better to track together,” ECCV, 2024. arXiv:2307.07635
- N. Karaev, I. Makarov, J. Wang, N. Neverova, A. Vedaldi and C. Rupprecht, “CoTracker3: Simpler and better point tracking by pseudo-labelling real videos,” arXiv:2410.11831, 2024. arXiv
- Z. Tang, S. Wang, D. C. Anastasiu et al., “The 9th AI City Challenge,” ICCV Workshops, 2025. arXiv:2508.13564
- VOT Challenge organizers, “The Visual Object Tracking (VOT) challenge series,” website, 2013–present. votchallenge.net
- R. Jonker and A. Volgenant, “A shortest augmenting path algorithm for dense and sparse linear assignment problems,” Computing, vol. 38, no. 4, pp. 325–340, 1987. doi
- D. F. Crouse, “On implementing 2D rectangular assignment algorithms,” IEEE Transactions on Aerospace and Electronic Systems, vol. 52, no. 4, pp. 1679–1696, 2016. doi