多假設(shè)多目標(biāo)跟蹤算法

王 巖，蒿興華，楊順云

（解放軍31108 部隊(duì)，南京 210016）

多假設(shè)多目標(biāo)跟蹤算法（MHT）是非常經(jīng)典的多目標(biāo)跟蹤算法，由Reid 在對雷達(dá)信號的自動跟蹤研究中提出，本質(zhì)上是基于Kalman 濾波跟蹤算法在多目標(biāo)跟蹤問題中的擴(kuò)展。定義在k 時刻之前的檢測為Zk，多假設(shè)跟蹤的目標(biāo)是基于已有軌跡對這種觀測關(guān)聯(lián)進(jìn)行條件概率建模，把似然關(guān)聯(lián)假設(shè)Θik 劃分為當(dāng)前關(guān)聯(lián)假設(shè)Θi（K）和k-1時刻的假設(shè)集合Θik（m）。可以利用貝葉斯推理得到關(guān)于關(guān)聯(lián)假設(shè)的后驗(yàn)概率公式。

其中公式右側(cè)第一項(xiàng)表示基于前期假設(shè)集合和當(dāng)前假設(shè)的觀察似然概率，即在歷史關(guān)聯(lián)的基礎(chǔ)上，當(dāng)關(guān)聯(lián)Θivartheta_{I}（K）成立時，表現(xiàn)出當(dāng)前觀測Z（k）的概率；第二項(xiàng)表示當(dāng)前假設(shè)的似然概率，即在歷史關(guān)聯(lián)的基礎(chǔ)上，當(dāng)前關(guān)聯(lián)假設(shè)的概率；第三項(xiàng)表示前期假設(shè)集合后驗(yàn)概率。c 是貝葉斯公式中的分母，對于當(dāng)前觀測已知的條件，可以認(rèn)為是一個常數(shù)。總體的假設(shè)后驗(yàn)概率可以表示為此三項(xiàng)的乘積。而公式第三項(xiàng)表示k-1時的后驗(yàn)概率，因此，只考慮第一項(xiàng)和第二項(xiàng)就可以得到一個遞推公式。

如何對第一項(xiàng)和第二項(xiàng)進(jìn)行建模？MHT 采用了二個概率模型：用均勻分布和高斯分布對關(guān)聯(lián)對應(yīng)的檢測觀察建模；用泊松分布對當(dāng)前假設(shè)的似然概率建模。

前者表示，當(dāng)觀測是來自一個軌跡T 時，它符合T 的高斯分布，否則觀測是一個均勻分布的噪聲。后者表示，在誤檢和新對象出現(xiàn)概率確定的情況下，出現(xiàn)當(dāng)前關(guān)聯(lián)的可能性可以通過泊松分布和二項(xiàng)分布的乘積表示。在以上假設(shè)下，關(guān)聯(lián)假設(shè)的后驗(yàn)分布是歷史累計(jì)概率密度的連乘，轉(zhuǎn)化為對數(shù)形式，可以看出總體后驗(yàn)概率的對數(shù)是每一步觀察似然和關(guān)聯(lián)假設(shè)似然的求和。因此，選擇最佳的關(guān)聯(lián)假設(shè)，轉(zhuǎn)化為觀察似然和關(guān)聯(lián)假設(shè)似然累計(jì)求和的最大化。在進(jìn)行具體實(shí)現(xiàn)和優(yōu)化的時侯，I.J.Cox 等人提出了一種基于假設(shè)樹的優(yōu)化算法，如下圖所示。

圖中：左圖為k-3時刻三個檢測觀察和兩條軌跡的可能匹配。對于這種匹配關(guān)系，可以繼續(xù)向前預(yù)測兩幀，如圖右。得到一種三層的假設(shè)樹結(jié)構(gòu)，對于假設(shè)樹根枝干的剪枝，得到k-3時刻的最終關(guān)聯(lián)結(jié)果。

對于k 時刻的關(guān)聯(lián)對數(shù)似然概率，可以認(rèn)為是k 時刻之前關(guān)聯(lián)觀察似然概率的對數(shù)求和，由于任何時刻都可能存在多種假設(shè)關(guān)聯(lián)，因此到k 時刻的假設(shè)構(gòu)成了一種組合假設(shè)樹的層次關(guān)系。例如圖中左邊表示的是2個軌跡和3個觀測之間可能形成的關(guān)聯(lián)假設(shè)，可能存在的假設(shè)有{觀測23=＞軌跡1，觀測22=＞軌跡2，觀測21=＞新軌跡}或者{觀測22=＞軌跡1，觀測21=＞軌跡2，觀測23=＞新軌跡}，因此產(chǎn)生2個假設(shè)分支。圖中右側(cè)是從這2個關(guān)聯(lián)假設(shè)出發(fā)的三層假設(shè)樹關(guān)系，可以看出隨著假設(shè)層數(shù)的增多，關(guān)聯(lián)假設(shè)出現(xiàn)組合爆炸的可能。因此進(jìn)行必要的剪枝減少假設(shè)空間的數(shù)目是必須的步驟。那么如何選擇最佳的關(guān)聯(lián)呢？I.J.Cox 采用了2個步驟來實(shí)現(xiàn)。首先，限制假設(shè)樹的層數(shù)為3層。其次，是對每個分支的葉節(jié)點(diǎn)概率對數(shù)進(jìn)行求和，最大的分支進(jìn)行保留，即選擇邊緣概率最大的那個分支假設(shè)作為最后選擇的關(guān)聯(lián)。

采用基于均勻分布、泊松分布以及高斯分布的模型，可以高效快速計(jì)算選擇k-3時優(yōu)化的假設(shè)關(guān)聯(lián)。這種基于似然概率對數(shù)累加的方法雖然方便迅速，但是存在一個主要的限制，即假定觀測關(guān)聯(lián)符合高斯模型，并且在每一步選擇關(guān)聯(lián)假設(shè)之后，需要利用Kalman 濾波更新軌跡狀態(tài)。通過對MHT 基本公式的擴(kuò)展，可以建立不同的概率模型描述這種多假設(shè)關(guān)聯(lián)的全局概率，例如Kim 等人在ICCV2015和ECCV2018通過歸一化的最小均方差優(yōu)化算法引入表觀模型來擴(kuò)展MHT 算法，取得不錯的多行人跟蹤結(jié)果。