帶你入門多目標跟蹤（三）匈牙利演算法&KM演算法
匈牙利演算法（Hungarian Algorithm）與KM演算法（Kuhn-Munkres Algorithm）是做多目標跟蹤的小夥伴很容易在論文中見到的兩種演算法。他們都是用來解決多目標跟蹤中的數據關聯問題。
對理論沒有興趣的小夥伴可以先跳過本文，進行下一篇的學習，把匈牙利演算法這些先當作一個黑箱來用，等需要了再回過頭來學習理論。但個人建議，至少要明白這些演算法的目的與大致流程。
如果大家用這兩種演算法的名字在搜索引擎上搜索，一定會首先看到這個名詞：二分圖（二部圖）。匈牙利演算法與KM演算法都是為了求解二分圖的最大匹配問題。
有一種很特別的圖，就做二分圖，那什麼是二分圖呢？就是能分成兩組，U,V。其中，U上的點不能相互連通，只能連去V中的點，同理，V中的點不能相互連通，只能連去U中的點。這樣，就叫做二分圖。
讀者可以把二分圖理解為視頻中連續兩幀中的所有檢測框，第一幀所有檢測框的集合稱為U，第二幀所有檢測框的集合稱為V。同一幀的不同檢測框不會為同一個目標，所以不需要互相關聯，相鄰兩幀的檢測框需要相互聯通，最終將相鄰兩幀的檢測框盡量完美地兩兩匹配起來。而求解這個問題的最優解就要用到匈牙利演算法或者KM演算法。
1. 匈牙利演算法（Hungarian Algorithm）
先介紹匈牙利演算法，引用百度百科的說法，匈牙利演算法是一種在多項式時間內求解任務分配問題的組合優化演算法，並推動了後來的原始對偶方法。美國數學家哈羅德·庫恩於1955年提出該演算法。此演算法之所以被稱作匈牙利演算法，是因為演算法很大一部分是基於以前匈牙利數學家Dénes K?nig和Jen? Egerváry的工作之上創建起來的。
https://blog.csdn.net/dark_scope/article/details/8880547#commentBox
這篇博文對匈牙利演算法進行了非常簡單清晰的解釋，我這裡引用它來說明一下匈牙利演算法的流程。
以上圖為例，假設左邊的四張圖是我們在第N幀檢測到的目標（U），右邊四張圖是我們在第N+1幀檢測到的目標（V）。紅線連起來的圖，是我們的演算法認為是同一行人可能性較大的目標。由於演算法並不是絕對理想的，因此並不一定會保證每張圖都有一對一的匹配，一對二甚至一對多，再甚至多對多的情況都時有發生。這時我們怎麼獲得最終的一對一跟蹤結果呢？我們來看匈牙利演算法是怎麼做的。
第一步.
首先給左1進行匹配，發現第一個與其相連的右1還未匹配，將其配對，連上一條藍線。
第二步.
接著匹配左2，發現與其相連的第一個目標右2還未匹配，將其配對。
第三步.
接下來是左3，發現最優先的目標右1已經匹配完成了，怎麼辦呢？
我們給之前右1的匹配對象左1分配另一個對象。
（黃色表示這條邊被臨時拆掉）
可以與左1匹配的第二個目標是右2，但右2也已經有了匹配對象，怎麼辦呢？
我們再給之前右2的匹配對象左2分配另一個對象（注意這個步驟和上面是一樣的，這是一個遞歸的過程）。
此時發現左2還能匹配右3，那麼之前的問題迎刃而解了，回溯回去。
左2對右3，左1對右2，左3對右1。
所以第三步最後的結果就是：
第四步.
最後是左4，很遺憾，按照第三步的節奏我們沒法給左4騰出來一個匹配對象，只能放棄對左4的匹配，匈牙利演算法流程至此結束。藍線就是我們最後的匹配結果。至此我們找到了這個二分圖的一個最大匹配。
再次感謝Dark_Scope的分享，我這裡只是把其中的例子替換成了多目標跟蹤的實際場景便於大家理解。
最終的結果是我們匹配出了三對目標，由於候選的匹配目標中包含了許多錯誤的匹配紅線（邊），所以匹配準確率並不高。可見匈牙利演算法對紅線連接的準確率要求很高，也就是要求我們運動模型、外觀模型等部件必須進行較為精準的預測，或者預設較高的閾值，只將置信度較高的邊才送入匈牙利演算法進行匹配，這樣才能得到較好的結果。
匈牙利演算法的流程大家看到了，有一個很明顯的問題相信大家也發現了，按這個思路找到的最大匹配往往不是我們心中的最優。匈牙利演算法將每個匹配對象的地位視為相同，在這個前提下求解最大匹配。這個和我們研究的多目標跟蹤問題有些不合，因為每個匹配對象不可能是同等地位的，總有一個真實目標是我們要找的最佳匹配，而這個真實目標應該擁有更高的權重，在此基礎上匹配的結果才能更貼近真實情況。
KM演算法就能比較好地解決這個問題，我們下面來看看KM演算法。
2.KM演算法（Kuhn-Munkres Algorithm）
KM演算法解決的是帶權二分圖的最優匹配問題。
還是用上面的圖來舉例子，這次給每條連接關係加入了權重，也就是我們演算法中其他模塊給出的置信度分值。
KM演算法解決問題的步驟是這樣的。
第一步
首先對每個頂點賦值，稱為頂標，將左邊的頂點賦值為與其相連的邊的最大權重，右邊的頂點賦值為0。
第二步，開始匹配
匹配的原則是隻和權重與左邊分數（頂標）相同的邊進行匹配，若找不到邊匹配，對此條路徑的所有左邊頂點的頂標減d，所有右邊頂點的頂標加d。參數d我們在這裡取值為0.1。
對於左1，與頂標分值相同的邊先標藍。
然後是左2，與頂標分值相同的邊標藍。
然後是左3，發現與右1已經與左1配對。首先想到讓左3更換匹配對象，然而根據匹配原則，只有權值大於等於0.9+0=0.9（左頂標加右頂標）的邊能滿足要求。於是左3無法換邊。那左1能不能換邊呢？對於左1來說，只有權值大於等於0.8+0=0.8的邊能滿足要求，無法換邊。此時根據KM演算法，應對所有衝突的邊的頂點做加減操作，令左邊頂點值減0.1，右邊頂點值加0.1。結果如下圖所示。
再進行匹配操作，發現左3多了一條可匹配的邊，因為此時左3對右2的匹配要求只需權重大於等於0.8+0即可，所以左3與右2匹配！
最後進行左4的匹配，由於左4唯一的匹配對象右3已被左2匹配，發生衝突。進行一輪加減d操作，再匹配，左四還是匹配失敗。兩輪以後左4期望值降為0，放棄匹配左4。
至此KM演算法流程結束，三對目標成功匹配，甚至在左三目標預測不夠準確的情況下也進行了正確匹配。可見在引入了權重之後，匹配成功率大大提高。
這篇文章可能信息量有點大，讀起來略費腦。不過筆者力求排除複雜的理論推導，使用形象的例子來說明這兩種演算法。至於具體的理論，有興趣的讀者可以再去搜尋，網上有很多資料，相信有了感性的理解後，對理論的掌握會更加容易。
最後還有一點值得注意，匈牙利演算法得到的最大匹配並不是唯一的，預設匹配邊、或者匹配順序不同等，都可能會導致有多種最大匹配情況，所以有一種替代KM演算法的想法是，我們只需要用匈牙利演算法找到所有的最大匹配，比較每個最大匹配的權重，再選出最大權重的最優匹配即可得到更貼近真實情況的匹配結果。但這種方法時間複雜度較高，會隨著目標數越來越多，消耗的時間大大增加，實際使用中並不推薦。
複雜的理論終於結束了，下一篇將是大家喜聞樂見的網路環節，輕鬆易懂不費腦，感謝大家的關注！
碼字倉促，文中若有錯誤，還請各位不吝指教。歡迎各位在評論區留言，大家互相交流學習。
轉載請聯繫作者並註明出處，侵權必究。
推薦閱讀：
