多傳感器特征融合—匈牙利匹配算法原理

描述

最近在做特征級(jí)別的感知結(jié)果融合算法。我的工作目的，是要將多種不同傳感器的感知結(jié)果，通過一定的機(jī)制融合起來(lái)，得到融合后的感知結(jié)果。

為此看了一些資料，了解到Apollo中使用了匈牙利匹配算法，之前不懂就學(xué)習(xí)了一下。

創(chuàng)建ROS工作環(huán)境

匈牙利算法（Hungarian Algorithm），該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法，是一種能夠在多項(xiàng)式時(shí)間內(nèi)解決分配問題的組合優(yōu)化算法。

網(wǎng)上有些作者比喻得很貼切，一句話先簡(jiǎn)單理解下匈牙利算法吧：有100個(gè)男人和100個(gè)女人，使用匈牙利算法可以湊出更多的夫妻（一男一女…）。

為了更深的理解算法是如何運(yùn)行的，我們需要補(bǔ)充一些圖論知識(shí)：比如，什么是二分圖，什么又是增廣矩陣，等等。（圖論中非相關(guān)知識(shí)自行學(xué)習(xí)）

二、算法所需的圖論知識(shí)

二分圖

一個(gè)圖中的所有頂點(diǎn)可劃分為兩個(gè)不相交的集合 U 和 V ，使得每一條邊都分別連接U、V中的頂點(diǎn)。如果存在這樣的劃分，則此圖為一個(gè)二分圖，又稱二部圖。

“這個(gè)二分圖可以理解為某個(gè)世界，在該世界中人非男即女。那么每個(gè)人其實(shí)都是這個(gè)圖中的一個(gè)頂點(diǎn)，男人集合和女人集合彼此割裂，男人就是男人，女人就是女人，男人可以和女人結(jié)合，這實(shí)際上就是一個(gè)二分圖?！?/p>

匹配

二分圖中的一個(gè)匹配，就是此時(shí)二分圖中一些邊的集合，這個(gè)邊集合中的任意兩條邊沒有公共的頂點(diǎn)，也構(gòu)不成一個(gè)圈。

“100個(gè)男人和100個(gè)女人組成的二分圖中，如果可以任意結(jié)婚，那么就會(huì)有很多種結(jié)婚組合。我們把其中的一種結(jié)婚組合的可能性，稱為一次匹配。在這次匹配中，任意一對(duì)夫妻都是合法夫妻，沒有任何性別的第三者存在哈哈?！?/p>

最大匹配

一個(gè)圖的所有匹配中，所含匹配邊數(shù)最多的匹配，稱為這個(gè)圖的最大匹配。最大匹配數(shù)，就是最大匹配時(shí)邊的數(shù)目。

“100個(gè)男人和100個(gè)女人，在平行時(shí)空下肯定有很多種結(jié)婚的組合啊，也就是有很多種匹配。

那么，在所有匹配中，結(jié)婚對(duì)數(shù)最多的那次匹配，就是這個(gè)二分圖的最大匹配。匈牙利算法是個(gè)月老和丘比特，他的目標(biāo)就是要湊出最多的新人”

完美匹配

如果一個(gè)圖的某個(gè)匹配中，所有的頂點(diǎn)都是匹配點(diǎn)，那么它就是一個(gè)完美匹配。

顯然，完美匹配一定是最大匹配（完美匹配的任何一個(gè)點(diǎn)都已經(jīng)匹配，添加一條新的匹配邊一定會(huì)與已有的匹配邊沖突）。但并非每個(gè)圖都存在完美匹配。

“100個(gè)男人和100個(gè)女人，每個(gè)男人都和一個(gè)女人結(jié)婚了，而且他們都是沒有重婚罪的合法夫妻，這就是這個(gè)圖的完美匹配。顯然，這是一次最大匹配了。

如果100個(gè)男人和99個(gè)女人構(gòu)成的二分圖，即使匈牙利算法再厲害，也還是會(huì)有個(gè)單身狗，并不存在完美匹配。”

三、算法原理

匈牙利算法有兩個(gè)重要概念，先介紹一下。

交錯(cuò)路徑

給定圖G的一個(gè)匹配M，如果一條路徑的邊交替出現(xiàn)在M中和不出現(xiàn)在M中，我們稱之為一條M-交錯(cuò)路徑。

增廣路徑

如果一條M-交錯(cuò)路徑，它的兩個(gè)端點(diǎn)都不與M中的邊關(guān)聯(lián)，我們稱這條路徑叫做M-增廣路徑。增廣路徑有一個(gè)重要特點(diǎn)：非匹配邊比匹配邊多一條。

我畫了一幅圖，我們有一幅8個(gè)頂點(diǎn)構(gòu)成的圖G。其中有一種匹配，是圖中的黑線表示的2和4兩條邊，這兩條邊加上8個(gè)頂點(diǎn)，構(gòu)成了圖G的一種匹配M。

為了方便理解，我將圖中的8個(gè)頂點(diǎn)按照二分圖進(jìn)行劃分，綠色點(diǎn)表示男人，黃色點(diǎn)表示女人。

顯然匹配M的意思就是，8個(gè)人中，由邊2和邊4代表的兩對(duì)男女結(jié)成了夫妻。

按照交錯(cuò)路徑的概念，1234、2345、12345都是M-交錯(cuò)路徑（123456都不是，因?yàn)?和6均不在匹配M中，01234同理），而在這三個(gè)交錯(cuò)路徑中，只有12345才是M-增廣路徑。那么，找出匹配M的增廣路徑意義合在呢？

我們會(huì)發(fā)現(xiàn)，在路徑12345中，還存在著另外一種匹配1、3、5，它的匹配數(shù)是3，要大于匹配M的匹配數(shù)2。

那么我們就得到了新的一個(gè)匹配N，它比匹配M更優(yōu)。按照同樣的方式，我們來(lái)尋找N-增廣路徑，會(huì)發(fā)現(xiàn)0123456是匹配N的增廣路徑，它的匹配數(shù)是4。

因此圖G的最大匹配，實(shí)際上是由0、2、4、6等四條邊構(gòu)成的匹配。

因此，研究增廣路徑的意義就是改進(jìn)匹配模式，只要把增廣路徑中的匹配邊和非匹配邊的身份交換就可以了。身份交換后，圖中的匹配邊數(shù)目，將比原來(lái)增多 1 條。

匈牙利算法的核心，就是通過不斷尋找原有匹配M的增廣路徑，來(lái)增加匹配中的匹配邊和匹配點(diǎn)，從而達(dá)到該圖下的最大匹配。

四、算法流程

概念

飽和

設(shè)一個(gè)圖為G，G中一些不相鄰的邊組成了一個(gè)集合M，這個(gè)集合M就是G的一個(gè)匹配。匹配M中的每條邊都有兩個(gè)端點(diǎn)，這兩個(gè)端點(diǎn)都稱為是M飽和的。

“有一些男人一些女人婚姻關(guān)系未明（一個(gè)圖G），一些男女結(jié)成了夫妻（一種匹配關(guān)系M），結(jié)婚的男女都算已婚了（M飽和）”

綜上，就把飽和——理解成已婚，比較好理解我下面的分析。

4.1 匈牙利算法單邊飽和

第0步

10個(gè)男人，9個(gè)女人，怎么飽和？如果10個(gè)男人，有10個(gè)及以上的女人，存在飽和的可能性，任選一種匹配M，準(zhǔn)備去找一個(gè)飽和X匹配。

第1步

如果當(dāng)前匹配M，已經(jīng)X飽和了，10個(gè)男人都匹配了老婆，算法停止；否則，任取一個(gè)沒老婆的男人x（取X中一個(gè)M非飽和點(diǎn)x），這個(gè)男人放進(jìn)集合S中，并設(shè)一個(gè)集合T為空集。

集合S中會(huì)存儲(chǔ)已經(jīng)結(jié)婚的男人+這個(gè)單身狗，集合T是這些男人的已婚配偶。

第2步

如果集合S中的位于匹配頂點(diǎn)的男人，他們可以匹配的女人（頂點(diǎn)的臨接頂點(diǎn)N(S)），全部是已婚配偶（∈T），那么算法停止，當(dāng)前的圖就是會(huì)有男人找不到老婆。

否則，我們找到了一個(gè)沒有在當(dāng)前路徑的女人y（y∈N(S)-T），當(dāng)然了這個(gè)女人可能有老公（也在匹配M中，只不過是不同路徑），也有可能是硬拆散的（算法首次進(jìn)入第2步，由于集合T為空，會(huì)強(qiáng)拆掉一組夫妻），也有可能壓根就是未婚的。

第3步

如果上一步選擇的女人y，她是有老公z的（y是M飽和的，yz∈M）。我們暫時(shí)先把他們拆開，老公z放進(jìn)集合S中，女人y放進(jìn)集合T中，然后去執(zhí)行第2步。

去執(zhí)行第2步，意味著也許也許也許…拆掉現(xiàn)有的一對(duì)夫妻，這對(duì)夫妻中的老婆能解決之前狼少肉多問題的同時(shí)，老公還能找到新的老婆。

否則，如果上一步選擇的女人y，是沒有老公的。我們找到了新的一種結(jié)婚方案（一條增廣路P(x,y)），這個(gè)方案里讓單身狗x去娶一個(gè)已婚的女人，然后原匹配夫妻中每個(gè)已婚男人都去娶別人老婆，剩下的一個(gè)已婚男人去娶這個(gè)小姑娘y。大家都很happy……h(huán)ahahaha（增廣路取反）

4.2 二部圖最大匹配的匈牙利算法

這里可以自行按照上面的分析，去理解算法。雖然真正理解算法較為困難，也不再這里贅述。

總結(jié)

這篇文章清晰明了的介紹了下匈牙利算法。如何與多傳感器融合特征算法相結(jié)合，會(huì)在以后的文章中介紹。

審核編輯：劉清