匈牙利算法（Hungarian Algorithm）與KM算法（Kuhn-Munkres Algorithm）是用來(lái)解決多目標(biāo)跟蹤中的數(shù)據(jù)關(guān)聯(lián)問(wèn)題，匈牙利算法與KM算法都是為了求解二分圖的最大匹配問(wèn)題。
有一種很特別的圖，就做二分圖，那什么是二分圖呢？就是能分成兩組，U,V。其中，U上的點(diǎn)不能相互連通，只能連去V中的點(diǎn)，同理，V中的點(diǎn)不能相互連通，只能連去U中的點(diǎn)。這樣，就叫做二分圖。
可以把二分圖理解為視頻中連續(xù)兩幀中的所有檢測(cè)框，第一幀所有檢測(cè)框的集合稱為U，第二幀所有檢測(cè)框的集合稱為V。同一幀的不同檢測(cè)框不會(huì)為同一個(gè)目標(biāo)，所以不需要互相關(guān)聯(lián)，相鄰兩幀的檢測(cè)框需要相互聯(lián)通，最終將相鄰兩幀的檢測(cè)框盡量完美地兩兩匹配起來(lái)。而求解這個(gè)問(wèn)題的最優(yōu)解就要用到匈牙利算法或者KM算法。
1.匈牙利算法
匈牙利算法是一種在多項(xiàng)式時(shí)間內(nèi)求解任務(wù)分配問(wèn)題的組合優(yōu)化算法。美國(guó)數(shù)學(xué)家哈羅德·庫(kù)恩于1955年提出該算法。此算法之所以被稱作匈牙利算法，是因?yàn)樗惴ê艽笠徊糠质腔谝郧靶傺览麛?shù)學(xué)家Dénes K?nig和Jen? Egerváry的工作之上創(chuàng)建起來(lái)的。
我們以目標(biāo)跟蹤的方法介紹匈牙利算法，以下圖為例，假設(shè)左邊的四張圖是我們?cè)诘贜幀檢測(cè)到的目標(biāo)（U），右邊四張圖是我們?cè)诘贜+1幀檢測(cè)到的目標(biāo)（V）。紅線連起來(lái)的圖，是我們的算法認(rèn)為是同一行人可能性較大的目標(biāo)。由于算法并不是絕對(duì)理想的，因此并不一定會(huì)保證每張圖都有一對(duì)一的匹配，一對(duì)二甚至一對(duì)多，再甚至多對(duì)多的情況都時(shí)有發(fā)生。這時(shí)我們?cè)趺传@得最終的一對(duì)一跟蹤結(jié)果呢？我們來(lái)看匈牙利算法是怎么做的。
首先給左1進(jìn)行匹配，發(fā)現(xiàn)第一個(gè)與其相連的右1還未匹配，將其配對(duì)，連上一條藍(lán)線。
接著匹配左2，發(fā)現(xiàn)與其相連的第一個(gè)目標(biāo)右2還未匹配，將其配對(duì)
接下來(lái)是左3，發(fā)現(xiàn)最優(yōu)先的目標(biāo)右1已經(jīng)匹配完成了，怎么辦呢？
我們給之前右1的匹配對(duì)象左1分配另一個(gè)對(duì)象。
（黃色表示這條邊被臨時(shí)拆掉）
可以與左1匹配的第二個(gè)目標(biāo)是右2，但右2也已經(jīng)有了匹配對(duì)象，怎么辦呢？
我們?cè)俳o之前右2的匹配對(duì)象左2分配另一個(gè)對(duì)象（注意這個(gè)步驟和上面是一樣的，這是一個(gè)遞歸的過(guò)程）。
此時(shí)發(fā)現(xiàn)左2還能匹配右3，那么之前的問(wèn)題迎刃而解了，回溯回去。
左2對(duì)右3，左1對(duì)右2，左3對(duì)右1。
所以第三步最后的結(jié)果就是：
最后是左4，很遺憾，按照第三步的節(jié)奏我們沒(méi)法給左4騰出來(lái)一個(gè)匹配對(duì)象，只能放棄對(duì)左4的匹配，匈牙利算法流程至此結(jié)束。藍(lán)線就是我們最后的匹配結(jié)果。至此我們找到了這個(gè)二分圖的一個(gè)最大匹配。最終的結(jié)果是我們匹配出了三對(duì)目標(biāo)，由于候選的匹配目標(biāo)中包含了許多錯(cuò)誤的匹配紅線（邊），所以匹配準(zhǔn)確率并不高。可見(jiàn)匈牙利算法對(duì)紅線連接的準(zhǔn)確率要求很高，也就是要求我們運(yùn)動(dòng)模型、外觀模型等部件必須進(jìn)行較為精準(zhǔn)的預(yù)測(cè)，或者預(yù)設(shè)較高的閾值，只將置信度較高的邊才送入匈牙利算法進(jìn)行匹配，這樣才能得到較好的結(jié)果。
可以使用：
scipy.optimize.linear_sum_assignment(cost_matrix)
實(shí)現(xiàn)匈牙利算法，其中const_matrix表示代價(jià)矩陣。比如第一幀有a,b,c,d四個(gè)目標(biāo)，第二幀圖像有p,q,r,s四個(gè)目標(biāo)，其相似度矩陣如下所示：
from scipy.optimize import linear_sum_assignment
import numpy as np
# 代價(jià)矩陣
cost =np.array([[1,2,3,4],[2,4,6,8],[3,6,9,12],[4,8,12,16]])
# 匹配結(jié)果
row_ind,col_ind=linear_sum_assignment(cost)
#對(duì)應(yīng)的行索引
print("行索引：\n{}".format(row_ind))
#對(duì)應(yīng)行索引的最優(yōu)指派的列索引
print("列索引：\n{}".format(col_ind))
#提取每個(gè)行索引的最優(yōu)指派列索引所在的元素，形成數(shù)組
print("匹配度：\n{}".format(cost[row_ind,col_ind]))
輸出結(jié)果為：
匈牙利算法的流程大家看到了，有一個(gè)很明顯的問(wèn)題相信大家也發(fā)現(xiàn)了，按這個(gè)思路找到的最大匹配往往不是我們心中的最優(yōu)。匈牙利算法將每個(gè)匹配對(duì)象的地位視為相同，在這個(gè)前提下求解最大匹配。這個(gè)和我們研究的多目標(biāo)跟蹤問(wèn)題有些不合，因?yàn)槊總€(gè)匹配對(duì)象不可能是同等地位的，總有一個(gè)真實(shí)目標(biāo)是我們要找的最佳匹配，而這個(gè)真實(shí)目標(biāo)應(yīng)該擁有更高的權(quán)重，在此基礎(chǔ)上匹配的結(jié)果才能更貼近真實(shí)情況。
KM算法就能比較好地解決這個(gè)問(wèn)題，我們下面來(lái)看看KM算法。
2.KM算法
KM算法解決的是帶權(quán)二分圖的最優(yōu)匹配問(wèn)題。
還是用上面的圖來(lái)舉例子，這次給每條連接關(guān)系加入了權(quán)重，也就是我們算法中其他模塊給出的置信度分值。
KM算法解決問(wèn)題的步驟是這樣的。
首先對(duì)每個(gè)頂點(diǎn)賦值，稱為頂標(biāo)，將左邊的頂點(diǎn)賦值為與其相連的邊的最大權(quán)重，右邊的頂點(diǎn)賦值為0。
匹配的原則是只和權(quán)重與左邊分?jǐn)?shù)（頂標(biāo)）相同的邊進(jìn)行匹配，若找不到邊匹配，對(duì)此條路徑的所有左邊頂點(diǎn)的頂標(biāo)減d，所有右邊頂點(diǎn)的頂標(biāo)加d。參數(shù)d我們?cè)谶@里取值為0.1。
對(duì)于左1，與頂標(biāo)分值相同的邊先標(biāo)藍(lán)。
然后是左2，與頂標(biāo)分值相同的邊標(biāo)
然后是左3，發(fā)現(xiàn)與右1已經(jīng)與左1配對(duì)。首先想到讓左3更換匹配對(duì)象，然而根據(jù)匹配原則，只有權(quán)值大于等于0.9+0=0.9（左頂標(biāo)加右頂標(biāo)）的邊能滿足要求。于是左3無(wú)法換邊。那左1能不能換邊呢？對(duì)于左1來(lái)說(shuō)，只有權(quán)值大于等于0.8+0=0.8的邊能滿足要求，無(wú)法換邊。此時(shí)根據(jù)KM算法，應(yīng)對(duì)所有沖突的邊的頂點(diǎn)做加減操作，令左邊頂點(diǎn)值減0.1，右邊頂點(diǎn)值加0.1。結(jié)果如下圖所示。
再進(jìn)行匹配操作，發(fā)現(xiàn)左3多了一條可匹配的邊，因?yàn)榇藭r(shí)左3對(duì)右2的匹配要求只需權(quán)重大于等于0.8+0即可，所以左3與右2匹配
最后進(jìn)行左4的匹配，由于左4唯一的匹配對(duì)象右3已被左2匹配，發(fā)生沖突。進(jìn)行一輪加減d操作，再匹配，左四還是匹配失敗。兩輪以后左4期望值降為0，放棄匹配左4。
至此KM算法流程結(jié)束，三對(duì)目標(biāo)成功匹配，甚至在左三目標(biāo)預(yù)測(cè)不夠準(zhǔn)確的情況下也進(jìn)行了正確匹配。可見(jiàn)在引入了權(quán)重之后，匹配成功率大大提高。。
最后還有一點(diǎn)值得注意，匈牙利算法得到的最大匹配并不是唯一的，預(yù)設(shè)匹配邊、或者匹配順序不同等，都可能會(huì)導(dǎo)致有多種最大匹配情況，所以有一種替代KM算法的想法是，我們只需要用匈牙利算法找到所有的最大匹配，比較每個(gè)最大匹配的權(quán)重，再選出最大權(quán)重的最優(yōu)匹配即可得到更貼近真實(shí)情況的匹配結(jié)果。但這種方法時(shí)間復(fù)雜度較高，會(huì)隨著目標(biāo)數(shù)越來(lái)越多，消耗的時(shí)間大大增加，實(shí)際使用中并不推薦。
總結(jié)：
- 匈牙利算法和KM算法是進(jìn)行二分圖最大匹配的算法，在目標(biāo)追蹤用于進(jìn)行目標(biāo)關(guān)聯(lián)
from scipy.optimize import linear_sum_assignment
import numpy as np
# 代價(jià)矩陣
cost =np.array([[1,2,3,4],[2,4,6,8],[3,6,9,12],[4,8,12,16]])
# 匹配結(jié)果
row_ind,col_ind=linear_sum_assignment(cost)
#對(duì)應(yīng)的行索引
print("行索引：\n{}".format(row_ind))
#對(duì)應(yīng)行索引的最優(yōu)指派的列索引
print("列索引：\n{}".format(col_ind))
#提取每個(gè)行索引的最優(yōu)指派列索引所在的元素，形成數(shù)組
print("匹配度：\n{}".format(cost[row_ind,col_ind]))
# 行索引：
# [0 1 2 3]
# 列索引：
# [3 2 1 0]
# 匹配度：
# [4 6 6 4]result=linear_sum_assignment(cost)
print(np.array(list(zip(*result))))
# [[0 3]
# [1 2]
# [2 1]
# [3 0]]"""
匈牙利算法（Hungarian Algorithm）與KM算法（Kuhn-Munkres Algorithm）1.匈牙利算法與KM算法：都是用來(lái)解決多目標(biāo)跟蹤中的數(shù)據(jù)關(guān)聯(lián)問(wèn)題2.匈牙利算法與KM算法：都是為了求解二分圖的最大匹配問(wèn)題二分圖1.有一種很特別的圖，就做二分圖，那什么是二分圖呢？就是能分成兩組，U,V。其中，U上的點(diǎn)不能相互連通，只能連V中的點(diǎn)，同理，V中的點(diǎn)不能相互連通，只能連U中的點(diǎn)。這樣，就叫做二分圖。2.可以把二分圖理解為視頻中連續(xù)兩幀中的所有檢測(cè)框，第一幀所有檢測(cè)框的集合稱為U，第二幀所有檢測(cè)框的集合稱為V。同一幀的不同檢測(cè)框不會(huì)為同一個(gè)目標(biāo)，所以不需要互相關(guān)聯(lián)，相鄰兩幀的檢測(cè)框需要相互聯(lián)通，最終將相鄰兩幀的檢測(cè)框盡量完美地兩兩匹配起來(lái)。而求解這個(gè)問(wèn)題的最優(yōu)解就要用到匈牙利算法或者KM算法。匈牙利算法1.匈牙利算法是一種在多項(xiàng)式時(shí)間內(nèi)求解任務(wù)分配問(wèn)題的組合優(yōu)化算法。2.我們以目標(biāo)跟蹤的方法介紹匈牙利算法，以下圖為例，假設(shè)左邊的四張圖是我們?cè)诘贜幀檢測(cè)到的目標(biāo)（U），右邊四張圖是我們?cè)诘贜+1幀檢測(cè)到的目標(biāo)（V）。紅線連起來(lái)的圖，是我們的算法認(rèn)為是同一人的可能性較大的目標(biāo)。由于算法并不是絕對(duì)理想的，因此并不一定要保證每張圖都有一對(duì)一的匹配，出現(xiàn)一對(duì)二甚至一對(duì)多的情況，再甚至多對(duì)多的情況都時(shí)有發(fā)生。這時(shí)我們?cè)趺传@得最終的一對(duì)一跟蹤結(jié)果呢？我們來(lái)看匈牙利算法是怎么做的。 3.匈牙利算法1.第一步：首先給左1進(jìn)行匹配，發(fā)現(xiàn)左1與其相連的第一個(gè)目標(biāo)右1還未匹配，將其配對(duì)，連上一條藍(lán)線。 2.第二步：接著匹配左2，發(fā)現(xiàn)左2與其相連的第一個(gè)目標(biāo)右2還未匹配，將其配對(duì)，連上一條藍(lán)線。3.第三步：1.接下來(lái)匹配左3，發(fā)現(xiàn)左3與其相連的第一個(gè)目標(biāo)(最優(yōu)先的目標(biāo))右1已經(jīng)匹配給左1了，怎么辦呢？那么我們給之前右1匹配的對(duì)象左1分配給另外一個(gè)對(duì)象，即把左1和右1的匹配關(guān)系取消掉，黃色線表示這左1和右1的匹配關(guān)系被臨時(shí)拆掉。2.可以與左1匹配的第二個(gè)目標(biāo)是右2，但右2此時(shí)也已經(jīng)有了其匹配對(duì)象左2，怎么辦呢？我們?cè)俳o之前右2的匹配對(duì)象左2分配給另一個(gè)對(duì)象(注意這個(gè)步驟和上面是一樣的，這是一個(gè)遞歸的過(guò)程)，即把左2和右2的匹配關(guān)系取消掉，黃色線表示這左2和右2的匹配關(guān)系被臨時(shí)拆掉。3.此時(shí)發(fā)現(xiàn)左2還能匹配與其相連的第二個(gè)目標(biāo)右3，發(fā)現(xiàn)左1還能匹配與其相連的第二個(gè)目標(biāo)右2，最終左2匹配右3，左1匹配右2，左3匹配右1。4.第四步：最后是左4，很遺憾，按照第三步的節(jié)奏我們沒(méi)法給左4騰出來(lái)一個(gè)匹配對(duì)象，只能放棄對(duì)左4的匹配，匈牙利算法流程至此結(jié)束。藍(lán)線就是我們最后的匹配結(jié)果。至此我們找到了這個(gè)二分圖的一個(gè)最大匹配。最終的結(jié)果是我們匹配出了三對(duì)目標(biāo)，由于候選的匹配目標(biāo)中包含了許多錯(cuò)誤的匹配紅線(邊)，所以匹配準(zhǔn)確率并不高。可見(jiàn)匈牙利算法對(duì)紅線連接的準(zhǔn)確率要求很高，也就是要求我們運(yùn)動(dòng)模型、外觀模型等部件必須進(jìn)行較為精準(zhǔn)的預(yù)測(cè)，或者預(yù)設(shè)較高的閾值，只將置信度較高的線(邊)才送入匈牙利算法進(jìn)行匹配，這樣才能得到較好的結(jié)果。 實(shí)現(xiàn)匈牙利算法1.API：scipy.optimize.linear_sum_assignment(cost_matrix)其中 const_matrix 表示代價(jià)矩陣。比如第一幀有a,b,c,d四個(gè)目標(biāo)，第二幀圖像有p,q,r,s四個(gè)目標(biāo)，其相似度矩陣如下所示.2.例子： from scipy.optimize import linear_sum_assignmentimport numpy as np# 代價(jià)矩陣cost =np.array([[1,2,3,4],[2,4,6,8],[3,6,9,12],[4,8,12,16]])# 匹配結(jié)果row_ind, =linear_sum_assignment(cost)#對(duì)應(yīng)的行索引print("行索引：\n{}".format(row_ind))#對(duì)應(yīng)行索引的最優(yōu)指派的列索引print("列索引：\n{}".format(col_ind))#提取每個(gè)行索引的最優(yōu)指派列索引所在的元素，形成數(shù)組print("匹配度：\n{}".format(cost[row_ind,col_ind])) 打印結(jié)果：行索引：[0 1 2 3]列索引：[3 2 1 0]匹配度：[4 6 6 4] 3.結(jié)論：匈牙利算法的流程，有一個(gè)很明顯的問(wèn)題，按這個(gè)思路找到的最大匹配往往不是我們心中的最優(yōu)。匈牙利算法將每個(gè)匹配對(duì)象的地位視為相同，在這個(gè)前提下求解最大匹配。這個(gè)和所研究的多目標(biāo)跟蹤問(wèn)題有些不合，因?yàn)槊總€(gè)匹配對(duì)象不可能是同等地位的，總有一個(gè)真實(shí)目標(biāo)是我們要找的最佳匹配，而這個(gè)真實(shí)目標(biāo)應(yīng)該擁有更高的權(quán)重，在此基礎(chǔ)上匹配的結(jié)果才能更貼近真實(shí)情況。KM算法就能比較好地解決這個(gè)問(wèn)題。
KM算法KM算法解決的是帶權(quán)二分圖的最優(yōu)匹配問(wèn)題。還是用上面的圖來(lái)舉例子，這次給每條連接關(guān)系加入了權(quán)重，權(quán)重也就是我們算法中其他模塊給出的置信度分值。
KM算法解決帶權(quán)二分圖的最優(yōu)匹配問(wèn)題的步驟：1.左右兩邊的圖匹配的原則是：左右兩邊的圖只和"權(quán)重與左邊圖的分?jǐn)?shù)(頂標(biāo))相同的"邊進(jìn)行匹配，若左邊圖根據(jù)與其分?jǐn)?shù)(頂標(biāo))相同的最大權(quán)重的線(邊)所連接到的右圖已經(jīng)被分配了某個(gè)左圖的話，那么產(chǎn)生沖突，解決的方式是對(duì)產(chǎn)生沖突的左邊的兩個(gè)圖的頂標(biāo)減d，然后令產(chǎn)生沖突的右邊的一個(gè)圖的頂點(diǎn)值加d。參數(shù)d我們?cè)谶@里取值為0.1。2.實(shí)現(xiàn)具體步驟：1.第一步首先對(duì)左右兩邊的每個(gè)圖(頂點(diǎn))進(jìn)行賦值，該值分?jǐn)?shù)稱為頂標(biāo)。將左邊的每個(gè)圖(頂點(diǎn))賦值為與其相連的線(邊)的最大權(quán)重，右邊的每個(gè)圖(頂點(diǎn))賦值為0。2.第二步：1.對(duì)于左1，與左1的頂標(biāo)分值相同的最大權(quán)重的邊先標(biāo)藍(lán)，左1連接右1。2.對(duì)于左2，與左2的頂標(biāo)分值相同的最大權(quán)重的邊先標(biāo)藍(lán)，左2連接右3。3.對(duì)于左3，與左3的頂標(biāo)分值相同的最大權(quán)重的邊所連接的右1已經(jīng)與左1配對(duì)，左3無(wú)法直接連接右1，此時(shí)產(chǎn)生沖突。1.首先想到的是讓左3更換匹配對(duì)象，然而根據(jù)匹配原則，只有權(quán)值大于等于(左圖頂標(biāo)加右圖頂標(biāo))0.9+0=0.9的邊能滿足左3連接右1的要求，否則無(wú)法換邊。那么于是左3無(wú)法換邊。那左1能不能換邊(更換匹配對(duì)象)呢？對(duì)于左1來(lái)說(shuō)，只有權(quán)值大于等于(左圖頂標(biāo)加右圖頂標(biāo))0.8+0=0.8的邊能滿足左1連接右1的要求，否則無(wú)法換邊。2.此時(shí)根據(jù)KM算法，應(yīng)對(duì)產(chǎn)生沖突的左右兩邊的圖的頂點(diǎn)做加減操作，首先令產(chǎn)生沖突的左邊的兩個(gè)圖的頂點(diǎn)值減0.1，然后令產(chǎn)生沖突的右邊的一個(gè)圖的頂點(diǎn)值加0.1。3.此時(shí)發(fā)現(xiàn)左3多了一條可匹配的邊，因?yàn)榇藭r(shí)左3連接右2的匹配要求能滿足權(quán)重大于等于(左圖頂標(biāo)加右圖頂標(biāo))0.8+0=0.8，所以左3與右2匹配。4.最后進(jìn)行左4的匹配，由于左4唯一的可匹配對(duì)象右3已被左2匹配，此時(shí)發(fā)生沖突。左右兩邊發(fā)生沖突的圖進(jìn)行一輪加減d的操作，再進(jìn)行匹配，此時(shí)左四還是匹配右3失敗。當(dāng)經(jīng)過(guò)一共兩輪的加減d的操作后發(fā)現(xiàn)左4的頂標(biāo)降為0，左4放棄繼續(xù)匹配。3.至此KM算法流程結(jié)束，三對(duì)目標(biāo)成功匹配，甚至在左三目標(biāo)預(yù)測(cè)不夠準(zhǔn)確的情況下也進(jìn)行了正確匹配。可見(jiàn)在引入了權(quán)重之后，匹配成功率大大提高。最后還有一點(diǎn)值得注意，匈牙利算法得到的最大匹配并不是唯一的，預(yù)設(shè)匹配邊、或者匹配順序不同等，都可能會(huì)導(dǎo)致有多種最大匹配情況，所以有一種替代KM算法的想法是，我們只需要用匈牙利算法找到所有的最大匹配，比較每個(gè)最大匹配的權(quán)重，再選出最大權(quán)重的最優(yōu)匹配即可得到更貼近真實(shí)情況的匹配結(jié)果。但這種方法時(shí)間復(fù)雜度較高，會(huì)隨著目標(biāo)數(shù)越來(lái)越多，消耗的時(shí)間大大增加，實(shí)際使用中并不推薦。
"""
總結(jié)
以上是生活随笔為你收集整理的智慧交通day02-车流量检测实现07：匈牙利算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
