匈牙利演算法:最佳的一對一指派
選讀・DLCV 07・物件追蹤:從單一物件到多物件 的補充資料(第 3/4 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。
導覽:本頁與本系列: 導覽:本頁與本系列
四位工人各自對四件工作開價,每件工作恰好需要一位工人。若讓工人依序各自拿走剩下最便宜的工作,最後一位工人可能只剩下很糟的工作。匈牙利方法 [31] 找出總價最低的完整指派:它替每位工人與每件工作各記一張「價格標籤」,只有在標籤證明不可能有更便宜的指派時,才接受一組配對。
取方形代價矩陣 ( 條軌跡、 個偵測), 是軌跡 配偵測 的代價。正文的指派問題是找出使 最小的排列矩陣 。它的對偶問題替每條軌跡指定勢能(potential),替每個偵測指定 :
其中 與 收集所有勢能。定義約化代價(reduced cost),並稱 的邊為緊邊(tight edge)。對任何指派,,因為被選中的 組配對各自滿足 ,而且每條軌跡與每個偵測都恰好出現一次。如果某個指派只用緊邊,等號成立,它就一定是最佳解。演算法要找的正是這張「證明」:
- 維持可行的勢能,以及一個只由緊邊構成的部分匹配。
- 挑一條尚未配對的軌跡,長出一棵交替樹(alternating tree):從軌跡出發沿緊邊走到偵測;從已配對的偵測沿它的配對邊走回它的軌跡。
- 如果樹碰到未配對的偵測,就把這條路徑上的邊翻轉(已配對的變成未配對,反之亦然),匹配多一組。
- 否則令 為「已到達的軌跡」到「未到達的偵測」的最小約化代價;把已到達軌跡的勢能加上 ,已到達偵測的勢能減去 。可行性維持不變,而且至少多出一條緊邊,然後回到步驟 2。
次擴增每次在稠密矩陣上花 ,總共 ,所以每格幾十到幾百個物件的計算量很小。這個方法對你給它的代價是精確的;它不看其他影格,所以代價矩陣若設計不好,配對結果仍然不好。
矩形與閘控的情形。 當 時,求解器回傳 組配對,其餘留著不配;這等同於在 補上虛擬的列或行。SciPy 的 linear_sum_assignment 直接接受矩形矩陣,實作的是修改過的 Jonker–Volgenant 最短擴增路徑演算法 [54]、[55]。上文的 associate 函式是在求解之後才拒絕超過門檻的配對。另一種做法是在問題裡面就把禁止的配對設成非常昂貴,讓求解器優先保留盡可能多的有效配對;兩者可能不一致,程式最後幾行會示範。
下面的程式實作上述四個步驟(一次加入一條軌跡),並在一個元素恰為 1 到 16 的 矩陣上與 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。勢能為 、,總和同樣是 20,最小約化代價為 0,所以對偶證明與指派剛好相遇。拿掉最後一個偵測(4 條軌跡、3 個偵測)後,得到三組配對、總代價 10,軌跡 2 沒有配到。在門檻為 0.6 的 閘控範例中,事後拒絕只留下一組配對 (1, 0),把閘控放進問題裡則留下兩組 (0, 0) 與 (1, 1):最便宜的完整匹配是 ,總代價 0.95,另一個是 1.05,事後拒絕就把其中超過門檻的 (0, 1) 丟掉。
參考文獻
- Shyandram,〈物件追蹤Object Tracking 簡介〉,Medium 文章,2023;2026 年更新。連結
- 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