多目標追蹤-初步調研

07-05

多目標追蹤-初步調研

本文內容參考於一篇多目標追蹤綜述的論文。

一. 簡介

多目標跟蹤(Multiple Object Tracking，MOT)的問題提出：有一段視頻，視頻是由 N 個連續幀構成的。從第一幀到最後一幀，裡面有多個目標，不斷地有出有進，不斷地運動。我們的目的是對每個目標，能跟其他目標區分開，能跟蹤它在不同幀中的軌跡。最經典的應用就是路口監控行人。

實際上，多目標跟蹤問題可以被理解為一個多變數估計問題，我們給出它的形式化定義。給定一個圖像序列， $s^i_t$ 表示第t幀第i個目標的狀態， $s_t = {s^1_t,s^2_t,...,s^{M_t}_t}$ 表示在第t幀下所有目標 $M_t$ 的狀態序列， $s^i_{i_s:i_e} = {s^i_{i_s},...,s^i_{i_e}}$ 表示第i個目標的狀態序列，其中 $i_s$ 和 $i_e$ 分別表示目標i出現的第一針和最後一針， $S_{1:t}={S_1,S_2,...,S_t}$ 表示所有目標從第1幀到第t幀的狀態序列。需要注意的是每一幀目標的ID都有可能不同。相應的，在最常用的tracking-by-detection或者detection based tracking(DBT)結構下， $o^i_t$ 表示第t幀第i個觀測目標， $O_t={o^1_t,o^2_t,...,o^{M_t}_t}$ 表示在第t幀下所有目標 $M_t$ 的觀測目標， $O_{1:t}={O_1,O_2,...,O_t}$ 表示所有目標從第1幀到第t幀的觀測目標序列。MOT的目的就是找到所有目標最好的狀態序列，在所有觀測目標的狀態序列上的條件分布上，可以通過使用MAP (maximal a posteriori)估計法泛化建模得到：

$hat{S}_{1:t}=mathop{argmax}_{S_{1:t}}P(S_{1:t}|O_{1:t})$ (1)

以往研究中提到的不同MOT演算法，其目的現在可以被認為是設計不同方法來解決上述的MAP問題。它們的方法要麼是基於概率預測方面的卡爾曼濾波(KF)，擴展卡爾曼濾波(EKF)以及粒子濾波(PF)等，要麼是基於決策優化方面的圖匹配，動態規劃，網路流，條件隨機場等。

基於概率預測的方法通常用兩步迭代演算法來解決式（1）的：

Predict: $P(S_{1:t}|O_{1:t-1}) = int{P(S_t|S_{t-1})P(S_{t-1}|O_{1:t-1})dS_{t-1}}$ ,

Update: $P(S_{1:t}|O_{1:t}) propto{P(O_t|S_t)P(S_t|O_{1:t-1})}$ 。

其中 $P(S_t|S_{t-1})$ 是動態模型， $P(O_t|S_t)$ 是觀測模型。

基於決策性優化的方法則是直接最大化概率函數 $L(hat{O}_{1:t}|S_{1:t})$ ，在觀測集 ${hat{O}^n_{1:t}}$ 上作為代表 $O(S_{1:t}|O_{1:t})$ ：

$egin{align*} hat{S}_{1:t}&=mathop{argmax}_{S_{1:t}}P(S_{1:t}|O_{1:t})\ &=mathop{argmax}_{S_{1:t}}L(S_{1:t}|O_{1:t})\ &=mathop{argmax}_{S_{1:t}}prod_{n}P(hat{O}_{1:t}|S_{1:t}) end{align*}$ (2)

或最小化能量函數 $E(hat{O}_{1:t}|S_{1:t})$ ：

$egin{align*} hat{S}_{1:t}&=mathop{argmax}_{S_{1:t}}P(S_{1:t}|O_{1:t})\ &=mathop{argmax}_{S_{1:t}}exp(-E(S_{1:t}|O_{1:t}))/Z\ &=mathop{argmin}_{S_{1:t}}E(S_{1:t}|O_{1:t}) end{align*}$ (3)

其中Z是歸一化因子，保證 $P(S_{1:t}|O_{1:t})$ 是一個概率分布。

二. MOT任務的分類

按照初始化方法劃分

按照如何對目標進行初始化可以將MOT任務分為兩類：Detection-Based Tracking(DBT)和Detection-Free Tracking(DFT)。

DBT：如Fig 1上層所示，首先檢測目標，然後鏈接到軌跡中。這種策略也通常被稱為「tracking-by-detection」。給定一個序列，在每幀中進行特定類型的目標檢測或運動檢測（基於背景建模），得到目標假設，然後進行順序或批量跟蹤，將檢測假設連接到軌跡中。有兩個問題值得注意：第一，由於提前訓練目標檢測器，DBT大部分關注特定的目標類型，如行人、車輛或人臉。第二，DBT的性能非常依賴於所採用的目標檢測器的性能。

DFT：如Fig 1下層所示，DFT需要在第一幀手動初始化一定數量的目標，然後在後續幀定位這些物體。

相對來說，DBT更受歡迎，因為它可以自動發現新目標、自動終止消失的目標。而DFT就不能處理新目標出現的情況，但它不需要提前訓練目標探測器。Table 3列出了DBT和DFT之間的主要差異。

2. 按照處理模式劃分

MOT也可以分為online跟蹤核offline跟蹤，其差別在於在處理當前幀時，後幾幀的觀測目標是否被利用到。Online，也成為causal，只依靠直到當前幀的前面的信息。相對的Offline則能使用未來幀的信息。

Online跟蹤：在online跟蹤中，圖像序列是一步步處理的因此該跟蹤方式也稱序列跟蹤。如Fig 2上層所示，a,b,c三個圈表示三個不同的目標，綠色箭頭表示過去的觀測目標，其結果由目標的位置和ID表示。

Offline跟蹤：Offline跟蹤利用一組幀來處理數據。如Fig 2下層所示，來自所有幀的觀測目標需要提前獲取，然後經分析計算組成最後的輸出。注意到由於計算複雜度和內存限制，不總是一次性處理所有幀，而是考慮將數據分成幾個短一點的視頻，對於每組分層或順序處理得到結果。Table 4列出了兩類處理模式的不同。

三. MOT的追蹤演算法

在設計MOT演算法的時候有兩個問題需要考慮：一個是怎樣測量幀內目標的相似性，另一個是基於這個相似性怎樣判斷幀間目標是否相同。前者主要包括外觀，運動，交叉，排斥和碰撞的建模問題，後者主要和數據關聯有關。

本節我們主要關注後一個問題，即給了很多幀間目標，我們怎麼做才能將他們相同的關聯起來，這就涉及到了追蹤演算法，也就是第一部分所提到的預測演算法。

概率預測

概率預測方法通常將目標狀態作為不確定的分布，而跟蹤演算法的目的是基於現有的觀測目標，用多種概率學方法去估計那個概率分布。這類演算法通常只需要過去或現在的觀測目標，所以它也特別適合online跟蹤。因為只有現存的觀測目標才被用於估計，所以可以很自然地在目標狀態序列中使用Markov特性假設，該假設包括兩方面，讓我們回顧第一部分提到的公式。

第一，當前目標狀態只依賴於之前的狀態，其次，當使用一階(first-order)Markov特性時則只依賴於最後一個狀態，即 $P(S_t|S_{1:t-1}) = P(S_t|S_{t-1})$ 。

第二，觀測目標只和它的狀態有關，也就是說，它是條件獨立的，即 $P(O_{1:t}|S_{1:t}) = prod_{i=1}^{t}P(O_t|S_t)$ 。

這兩方面各自和動態模型和觀測模型有關，前者與跟蹤策略相關，後者則提供有關目標狀態的觀測測量。預測(predict)一步是根據之前的觀測來估計當前的狀態，具體來說，當前狀態的後驗概率分布，是通過以動態模型來整合上一目標狀態空間，從而估計得到的。更新(update)一步是根據觀測模型得到的測量來更新狀態的後驗概率分布。

根據這些等式，目標狀態可以通過迭代計算predict和update兩步來得到，然而實際上，目標狀態分布不能不先簡化假設，因此沒有能計算得到完整狀態分布的解法。另外，對於多目標而言，狀態集的維數是非常大的，導致整合步驟更加困難，因此需要有對應的降維方法。

多種多樣的概率預測模型被用於多目標跟蹤中，例如卡爾曼濾波，擴展卡爾曼濾波以及粒子濾波。

卡爾曼濾波：適用於線性系統和服從高斯分布的目標狀態。

擴展卡爾曼濾波：通過泰勒展開估計，進一步適用於非線性系統。

粒子濾波：基於蒙特卡洛採樣的模型在粒子濾波演算法問世後風靡一時。該方法用一組有權重的粒子來對分布建模，從而通過改變自己的分布可以得到任意的假設。

2.確定性優化

相對於概率預測，確定性優化旨在是找到MOT最大的後驗解決(MAP)辦法。這種方法更適合offline跟蹤，因為需要提前獲得所有幀的觀測目標，然後全局性地將屬於同一目標的觀測目標串聯成一條軌跡，關鍵問題在於怎樣找到最優的連接。

圖匹配方法：通過將MOT問題建模成偶圖匹配，兩個不相交的結點集在online跟蹤中可以存在trajectories和新的檢測目標，或者在offline跟蹤中存在兩個tracklets集，結點間的權重則代表trajectories和檢測目標間的相似度，然後要麼使用貪心偶匹配演算法，要麼使用匈牙利優化演算法，來決定兩結點集如何進行匹配。

動態規劃：擴展動態規劃，線性規劃，二次布爾規劃，最短K路徑，集合覆蓋，都是被用於解決檢測目標和tracklets之間關聯問題的方法。

最小代價最大流：網路流是一個帶有權重邊的有向圖。對於MOT，圖中結點是檢測響應或tracklets，流是連接兩個結點的指示器，為了滿足流平衡的需求，需要增加源節點和匯聚節點，如Fig 6。一個trajectory對應一個流邊，從源節點轉移到匯聚節點的總流數等於trajectories的數目，轉移損耗是所有連接的假設的負對數似然，注意，全局最優解可以在多項式時間內得到，例如使用push-relabel演算法

條件隨機場：定義一個圖G=(V,E)，其中V是結點集，E是邊集，低層tracklets作為圖的輸入，每個結點表示觀測目標或者tracklets對，每個label通過預測得到，然後用來推斷都是觀測目標屬於哪些track跟蹤目標或者來連接哪些tracklets。

四. 小結

我們對MOT任務進行了初步的調研，為了更熟悉MOT目前的研究進展，在之後的工作中我們將深入到兩種追蹤演算法(KF,EKF,PF和條件隨機場)的具體細節之中。