完整搜尋頁面 →

匈牙利演算法:最佳的一對一指派

選讀・DLCV 07・物件追蹤:從單一物件到多物件 的補充資料(第 3/4 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。

導覽:本頁與本系列: 導覽:本頁與本系列

本頁內容

補充資料 · 4

  1. 更多 Re-ID 模型:強基線、質心與 CLIP-ReID
  2. MOSSE:在傅立葉域學習的相關濾波器
  3. 匈牙利演算法:最佳的一對一指派
  4. 點追蹤模型:TAPIR 與 CoTracker 系列

論文導讀 · 1

  1. 追蹤綜述論文的細節

電腦視覺深度學習

  1. 02 · 深度影像分類
  2. 03 · 物件偵測:從 R-CNN 到 DETR
  3. 09 · 深度影像復原:低階視覺
查看完整課程樹 →

四位工人各自對四件工作開價,每件工作恰好需要一位工人。若讓工人依序各自拿走剩下最便宜的工作,最後一位工人可能只剩下很糟的工作。匈牙利方法 [31] 找出總價最低的完整指派:它替每位工人與每件工作各記一張「價格標籤」,只有在標籤證明不可能有更便宜的指派時,才接受一組配對。

取方形代價矩陣 C∈Rn×n\mathbf{C} \in \mathbb{R}^{n \times n}(nn 條軌跡、nn 個偵測),CkjC_{kj} 是軌跡 kk 配偵測 jj 的代價。正文的指派問題是找出使 ∑k,jCkjXkj\sum_{k,j} C_{kj}X_{kj} 最小的排列矩陣 X\mathbf{X}。它的對偶問題替每條軌跡指定勢能(potential)uku_k,替每個偵測指定 vjv_j:

max⁡u,v ∑kuk+∑jvjs.t.uk+vj≤Ckj  對所有 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{ 對所有 } k, j,

其中 u∈Rn\mathbf{u} \in \mathbb{R}^n 與 v∈Rn\mathbf{v} \in \mathbb{R}^n 收集所有勢能。定義約化代價(reduced cost)Cˉkj=Ckj−uk−vj≥0\bar C_{kj} = C_{kj} - u_k - v_j \ge 0,並稱 Cˉkj=0\bar C_{kj} = 0 的邊為緊邊(tight edge)。對任何指派,∑CkjXkj≥∑kuk+∑jvj\sum C_{kj}X_{kj} \ge \sum_k u_k + \sum_j v_j,因為被選中的 nn 組配對各自滿足 Ckj≥uk+vjC_{kj} \ge u_k + v_j,而且每條軌跡與每個偵測都恰好出現一次。如果某個指派只用緊邊,等號成立,它就一定是最佳解。演算法要找的正是這張「證明」:

  1. 維持可行的勢能,以及一個只由緊邊構成的部分匹配。
  2. 挑一條尚未配對的軌跡,長出一棵交替樹(alternating tree):從軌跡出發沿緊邊走到偵測;從已配對的偵測沿它的配對邊走回它的軌跡。
  3. 如果樹碰到未配對的偵測,就把這條路徑上的邊翻轉(已配對的變成未配對,反之亦然),匹配多一組。
  4. 否則令 δ\delta 為「已到達的軌跡」到「未到達的偵測」的最小約化代價;把已到達軌跡的勢能加上 δ\delta,已到達偵測的勢能減去 δ\delta。可行性維持不變,而且至少多出一條緊邊,然後回到步驟 2。

nn 次擴增每次在稠密矩陣上花 O(n2)O(n^2),總共 O(n3)O(n^3),所以每格幾十到幾百個物件的計算量很小。這個方法對你給它的代價是精確的;它不看其他影格,所以代價矩陣若設計不好,配對結果仍然不好。

矩形與閘控的情形。 當 K≠NK \ne N 時,求解器回傳 min⁡(K,N)\min(K, N) 組配對,其餘留著不配;這等同於在 C\mathbf{C} 補上虛擬的列或行。SciPy 的 linear_sum_assignment 直接接受矩形矩陣,實作的是修改過的 Jonker–Volgenant 最短擴增路徑演算法 [54]、[55]。上文的 associate 函式是在求解之後才拒絕超過門檻的配對。另一種做法是在問題裡面就把禁止的配對設成非常昂貴,讓求解器優先保留盡可能多的有效配對;兩者可能不一致,程式最後幾行會示範。

下面的程式實作上述四個步驟(一次加入一條軌跡),並在一個元素恰為 1 到 16 的 4×44 \times 4 矩陣上與 SciPy 比對。

程式碼 · Python · 59 行
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])

兩個求解器都回傳配對 (0, 0)、(1, 1)、(2, 3)、(3, 2),總代價 20;貪婪法的代價是 25。勢能為 u=(7,5,10,5)\mathbf{u} = (7, 5, 10, 5)、v=(−4,0,−3,0)\mathbf{v} = (-4, 0, -3, 0),總和同樣是 20,最小約化代價為 0,所以對偶證明與指派剛好相遇。拿掉最後一個偵測(4 條軌跡、3 個偵測)後,得到三組配對、總代價 10,軌跡 2 沒有配到。在門檻為 0.6 的 2×22 \times 2 閘控範例中,事後拒絕只留下一組配對 (1, 0),把閘控放進問題裡則留下兩組 (0, 0) 與 (1, 1):最便宜的完整匹配是 {(0,1),(1,0)}\{(0, 1), (1, 0)\},總代價 0.95,另一個是 1.05,事後拒絕就把其中超過門檻的 (0, 1) 丟掉。

參考文獻

  1. Shyandram,〈物件追蹤Object Tracking 簡介〉,Medium 文章,2023;2026 年更新。連結
  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