Full search page →

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

On this page

Supplementary notes · 4

  1. More Re-ID models: a strong baseline, centroids and CLIP-ReID
  2. MOSSE: a correlation filter learned in the Fourier domain
  3. The Hungarian algorithm: optimal one-to-one assignment
  4. Point tracking models: TAPIR and the CoTracker line

Paper guides · 1

  1. The tracking surveys in more detail

Deep Learning for Computer Vision

  1. 02 · Deep Image Classification
View the whole course tree →

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 C∈Rn×n\mathbf{C} \in \mathbb{R}^{n \times n} (nn tracks, nn detections), where CkjC_{kj} is the cost of pairing track kk with detection jj. The assignment problem of the main text asks for a permutation matrix X\mathbf{X} minimizing ∑k,jCkjXkj\sum_{k,j} C_{kj}X_{kj}. Its dual problem assigns a potential uku_k to every track and vjv_j to every detection:

max⁡u,v ∑kuk+∑jvjs.t.uk+vj≤Ckj  for all k,j,\max_{\mathbf{u}, \mathbf{v}}\ \sum_k u_k + \sum_j v_j \quad \text{s.t.}\quad u_k + v_j \le C_{kj}\ \text{ for all } k, j,

where u∈Rn\mathbf{u} \in \mathbb{R}^n and v∈Rn\mathbf{v} \in \mathbb{R}^n collect the potentials. Define the reduced cost Cˉkj=Ckj−uk−vj≥0\bar C_{kj} = C_{kj} - u_k - v_j \ge 0 and call an edge with Cˉkj=0\bar C_{kj} = 0 tight. For any assignment, ∑CkjXkj≥∑kuk+∑jvj\sum C_{kj}X_{kj} \ge \sum_k u_k + \sum_j v_j, because each of the nn chosen pairs satisfies Ckj≥uk+vjC_{kj} \ge u_k + v_j 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:

  1. Keep feasible potentials and a partial matching on tight edges.
  2. 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.
  3. 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.
  4. Otherwise let δ\delta be the smallest reduced cost from a reached track to an unreached detection. Add δ\delta 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 nn augmentations costs O(n2)O(n^2) on a dense matrix, hence O(n3)O(n^3) 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 K≠NK \ne N the solver returns min⁡(K,N)\min(K, N) pairs and leaves the rest unmatched; this is equivalent to padding C\mathbf{C} 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 4×44 \times 4 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 u=(7,5,10,5)\mathbf{u} = (7, 5, 10, 5) and v=(−4,0,−3,0)\mathbf{v} = (-4, 0, -3, 0), 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 2×22 \times 2 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 {(0,1),(1,0)}\{(0, 1), (1, 0)\} with total 0.95 against 1.05 for the other one, and rejecting afterwards then discards its over-threshold pair (0, 1).

References

  1. Shyandram, “物件追蹤Object Tracking 簡介” (Introduction to object tracking), Medium post (in Traditional Chinese), 2023; updated 2026. link
  2. 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
  3. 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
  4. M. Adžemović, “Deep learning-based multi-object tracking: A comprehensive survey from foundations to state-of-the-art,” arXiv:2506.13457, 2025. arXiv
  5. 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
  6. 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
  7. 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
  8. 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
  9. K. Bernardin and R. Stiefelhagen, “Evaluating multiple object tracking performance: The CLEAR MOT metrics,” EURASIP Journal on Image and Video Processing, 2008. doi
  10. 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
  11. K. Peng, A. Mathur and A. Narayanan, “Mitigating dataset harms requires stewardship: Lessons from 1000 papers,” arXiv:2108.02922, 2021. arXiv
  12. L. Zheng, L. Shen, L. Tian, S. Wang, J. Wang and Q. Tian, “Scalable person re-identification: A benchmark,” ICCV, 2015. doi
  13. 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
  14. 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
  15. M. Wieczorek, B. Rychalska and J. Dąbrowski, “On the unreasonable effectiveness of centroids in image retrieval,” arXiv:2104.13643, 2021. arXiv
  16. 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
  17. D. S. Bolme, J. R. Beveridge, B. A. Draper and Y. M. Lui, “Visual object tracking using adaptive correlation filters,” CVPR, 2010. doi
  18. 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
  19. 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
  20. B. Li, J. Yan, W. Wu, Z. Zhu and X. Hu, “High performance visual tracking with Siamese region proposal network,” CVPR, 2018. doi
  21. 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
  22. 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
  23. 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
  24. 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
  25. N. Carion, L. Gustafson, Y.-T. Hu et al., “SAM 3: Segment anything with concepts,” ICLR, 2026. arXiv:2511.16719
  26. Y. Wu, J. Lim and M.-H. Yang, “Object tracking benchmark,” IEEE TPAMI, vol. 37, 2015. doi
  27. 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
  28. 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
  29. 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
  30. 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
  31. H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, pp. 83–97, 1955. doi
  32. A. Bewley, Z. Ge, L. Ott, F. Ramos and B. Upcroft, “Simple online and realtime tracking,” ICIP, 2016. arXiv:1602.00763
  33. N. Wojke, A. Bewley and D. Paulus, “Simple online and realtime tracking with a deep association metric,” ICIP, 2017. doi
  34. 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
  35. 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
  36. N. Aharon, R. Orfaig and B.-Z. Bobrovsky, “BoT-SORT: Robust associations multi-pedestrian tracking,” arXiv:2206.14651, 2022. arXiv
  37. Z. Wang, L. Zheng, Y. Liu, Y. Li and S. Wang, “Towards real-time multi-object tracking” (JDE), ECCV, 2020. arXiv:1909.12605
  38. 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
  39. P. Bergmann, T. Meinhardt and L. Leal-Taixé, “Tracking without bells and whistles” (Tracktor), ICCV, 2019. arXiv:1903.05625
  40. 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
  41. Y. Zhang, T. Wang and X. Zhang, “MOTRv2: Bootstrapping end-to-end multi-object tracking by pretrained object detectors,” CVPR, 2023. arXiv:2211.09791
  42. R. Gao, J. Qi and L. Wang, “Multiple object tracking as ID prediction” (MOTIP), CVPR, 2025. arXiv:2403.16848
  43. S. Li, T. Fischer, L. Ke, H. Ding, M. Danelljan and F. Yu, “OVTrack: Open-vocabulary multiple object tracking,” CVPR, 2023. arXiv:2304.08408
  44. 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
  45. 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
  46. 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
  47. 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
  48. 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
  49. 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
  50. 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
  51. 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
  52. Z. Tang, S. Wang, D. C. Anastasiu et al., “The 9th AI City Challenge,” ICCV Workshops, 2025. arXiv:2508.13564
  53. VOT Challenge organizers, “The Visual Object Tracking (VOT) challenge series,” website, 2013–present. votchallenge.net
  54. 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
  55. 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