目標跟蹤方法包括生成類方法和判別類方法。與生成類方法最大的區(qū)別是，判別類方法分類器采用機器學習，訓練中用到了背景信息，這樣分類器就能專注區(qū)分前景和背景，所以判別類方法普遍都比生成類好。本方法基于圖論進行數(shù)據(jù)關(guān)聯(lián)并求解問題。

在了解該方法前，需要有圖論的基本知識，包括圖的結(jié)構(gòu)，最短路徑求解（Bellman-Ford算法，Dijkstra算法），最小損耗流問題求解等知識。

模型建立

對于對象數(shù)據(jù)關(guān)聯(lián)即可理解為最大化檢測到對象的軌跡預測正確率,公式表達：

公式1

其中

但該公式難以被直接優(yōu)化，通過一系列轉(zhuǎn)換（詳見論文 Global data association for multi-object tracking using network flows），公式1等價轉(zhuǎn)換為公式2：

公式2

其中：

而公式2可以直接轉(zhuǎn)換為最小損耗流問題，模型便如下圖：

SSP及其優(yōu)化算法

該節(jié)內(nèi)容主要為論文FollowMe: Ef?cient Online Min-Cost Flow Tracking with Bounded Memory and Computation翻譯并加入自己的理解，用以求解最小損耗流問題，最后求取最優(yōu)軌跡。

SSP算法

SSP算法先使用Bellman-Ford算法找到最短路徑（如圖（d））,并進行轉(zhuǎn)換（如圖轉(zhuǎn)換方法），使所有路徑的損耗為非負，以保證接下來求最短路徑可以使用Dijkstra算法，接著對最短路徑邊緣反向，獲取殘差圖，使用Dijkstra算法求最短路徑，再反向獲取殘差圖，通過循環(huán)，當找不到最短路徑或最短路徑非負時算法結(jié)束，通過圖(g)(h)(i)將找到的最短路徑轉(zhuǎn)換為最優(yōu)的軌跡。（圖（g）中綠色軌跡表示最短路徑，將其反向變?yōu)閳D（h）,所有反向的節(jié)點邊便代表該圖的最優(yōu)軌跡）

SSP

轉(zhuǎn)換方法

仍然不是很了解的朋友們，可以再看看下面的SSP算法的求解步驟圖，但要注意基于跟蹤的圖每條邊可通過的流最大也只有1。下圖只是幫助大家更好理解SSP算法。

SSP算法的求解步驟圖

dSSP算法

在SSP中第一次找到最短路徑后，使用Dijkstra算法在殘差圖尋找最短路徑時，需要重新遍歷所有節(jié)點。而SSP在第一次尋找最短路徑的過程中遍歷了所有的節(jié)點，而轉(zhuǎn)換后的殘差圖的部分節(jié)點的前驅(qū)節(jié)點與轉(zhuǎn)換前的圖的節(jié)點完全一致，這就導致了計算量的重復。dSSP(動態(tài)規(guī)劃SSP算法)只更新殘差圖中前驅(qū)節(jié)點中含有最短路徑中邊翻轉(zhuǎn)的節(jié)點，再對這行節(jié)點進行松弛操作更新，最后找到新的最短路徑。

dSSP

mbodSSP算法

mbodSSP針對在線且內(nèi)存有限處理的情況。對于在線算法，我們所面對的情況是新的觀測對象到來（在t幀時檢測到的一系列對象），我們需要重新使用直到t-1幀為止的最短路徑和軌跡算法獲得的計算。新的網(wǎng)絡包括之前的網(wǎng)絡和當前幀所轉(zhuǎn)換的新增加的一些邊和節(jié)點，因此它也有可能會重新優(yōu)化軌跡而與之前幀所優(yōu)化的原有軌跡不一致，圖（a）-（g）描述了在線算法的過程。
當算法處理在線視頻時，針對目標長軌跡，它需要使用很多幀前的數(shù)據(jù)去做優(yōu)化。同時對于一些時間序列極長的視頻需要存儲數(shù)據(jù)的內(nèi)存空間是無止境的，因此必須要對算法進行優(yōu)化。優(yōu)化算法mbodSSP的核心思想是給予系統(tǒng)有限的計算和存儲空間，忽略較早時間幀的信息，只保留臨近幾幀的數(shù)據(jù)。