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

王 巖，蒿興華，楊順云

（解放軍31108 部隊，南京 210016）

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

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

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

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

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

對于k 時刻的關(guān)聯(lián)對數(shù)似然概率，可以認為是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)組合爆炸的可能。因此進行必要的剪枝減少假設(shè)空間的數(shù)目是必須的步驟。那么如何選擇最佳的關(guān)聯(lián)呢？I.J.Cox 采用了2個步驟來實現(xiàn)。首先，限制假設(shè)樹的層數(shù)為3層。其次，是對每個分支的葉節(jié)點概率對數(shù)進行求和，最大的分支進行保留，即選擇邊緣概率最大的那個分支假設(shè)作為最后選擇的關(guān)聯(lián)。

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