目標(biāo)跟蹤方法包括生成類(lèi)方法和判別類(lèi)方法。與生成類(lèi)方法最大的區(qū)別是，判別類(lèi)方法分類(lèi)器采用機(jī)器學(xué)習(xí)，訓(xùn)練中用到了背景信息洋只，這樣分類(lèi)器就能專(zhuān)注區(qū)分前景和背景，所以判別類(lèi)方法普遍都比生成類(lèi)好裳涛。本方法基于圖論進(jìn)行數(shù)據(jù)關(guān)聯(lián)并求解問(wèn)題木张。
在了解該方法前，需要有圖論的基本知識(shí)端三，包括圖的結(jié)構(gòu)，最短路徑求解（Bellman-Ford算法鹃彻，Dijkstra算法）郊闯，最小損耗流問(wèn)題求解等知識(shí)。
模型建立
對(duì)于對(duì)象數(shù)據(jù)關(guān)聯(lián)即可理解為最大化檢測(cè)到對(duì)象的軌跡預(yù)測(cè)正確率,公式表達(dá)：
其中
但該公式難以被直接優(yōu)化蛛株，通過(guò)一系列轉(zhuǎn)換（詳見(jiàn)論文 Global data association for multi-object tracking using network flows）团赁，公式1等價(jià)轉(zhuǎn)換為公式2：
其中：
而公式2可以直接轉(zhuǎn)換為最小損耗流問(wèn)題，模型便如下圖：
SSP及其優(yōu)化算法
該節(jié)內(nèi)容主要為論文FollowMe: Ef?cient Online Min-Cost Flow Tracking with Bounded Memory and Computation翻譯并加入自己的理解谨履，用以求解最小損耗流問(wèn)題欢摄，最后求取最優(yōu)軌跡。
SSP算法
SSP算法先使用Bellman-Ford算法找到最短路徑（如圖（d））,并進(jìn)行轉(zhuǎn)換（如圖轉(zhuǎn)換方法）笋粟，使所有路徑的損耗為非負(fù)怀挠，以保證接下來(lái)求最短路徑可以使用Dijkstra算法，接著對(duì)最短路徑邊緣反向害捕，獲取殘差圖绿淋，使用Dijkstra算法求最短路徑，再反向獲取殘差圖尝盼，通過(guò)循環(huán)吞滞，當(dāng)找不到最短路徑或最短路徑非負(fù)時(shí)算法結(jié)束，通過(guò)圖(g)(h)(i)將找到的最短路徑轉(zhuǎn)換為最優(yōu)的軌跡盾沫。（圖（g）中綠色軌跡表示最短路徑裁赠，將其反向變?yōu)閳D（h）,所有反向的節(jié)點(diǎn)邊便代表該圖的最優(yōu)軌跡）
仍然不是很了解的朋友們殿漠，可以再看看下面的SSP算法的求解步驟圖，但要注意基于跟蹤的圖每條邊可通過(guò)的流最大也只有1佩捞。下圖只是幫助大家更好理解SSP算法绞幌。
dSSP算法
在SSP中第一次找到最短路徑后，使用Dijkstra算法在殘差圖尋找最短路徑時(shí)失尖，需要重新遍歷所有節(jié)點(diǎn)啊奄。而SSP在第一次尋找最短路徑的過(guò)程中遍歷了所有的節(jié)點(diǎn)，而轉(zhuǎn)換后的殘差圖的部分節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)與轉(zhuǎn)換前的圖的節(jié)點(diǎn)完全一致掀潮，這就導(dǎo)致了計(jì)算量的重復(fù)菇夸。dSSP(動(dòng)態(tài)規(guī)劃SSP算法)只更新殘差圖中前驅(qū)節(jié)點(diǎn)中含有最短路徑中邊翻轉(zhuǎn)的節(jié)點(diǎn)，再對(duì)這行節(jié)點(diǎn)進(jìn)行松弛操作更新仪吧，最后找到新的最短路徑庄新。
mbodSSP算法
mbodSSP針對(duì)在線(xiàn)且內(nèi)存有限處理的情況。對(duì)于在線(xiàn)算法薯鼠，我們所面對(duì)的情況是新的觀(guān)測(cè)對(duì)象到來(lái)（在t幀時(shí)檢測(cè)到的一系列對(duì)象）择诈，我們需要重新使用直到t-1幀為止的最短路徑和軌跡算法獲得的計(jì)算。新的網(wǎng)絡(luò)包括之前的網(wǎng)絡(luò)和當(dāng)前幀所轉(zhuǎn)換的新增加的一些邊和節(jié)點(diǎn)出皇，因此它也有可能會(huì)重新優(yōu)化軌跡而與之前幀所優(yōu)化的原有軌跡不一致羞芍，圖（a）-（g）描述了在線(xiàn)算法的過(guò)程。
當(dāng)算法處理在線(xiàn)視頻時(shí)郊艘，針對(duì)目標(biāo)長(zhǎng)軌跡荷科，它需要使用很多幀前的數(shù)據(jù)去做優(yōu)化。同時(shí)對(duì)于一些時(shí)間序列極長(zhǎng)的視頻需要存儲(chǔ)數(shù)據(jù)的內(nèi)存空間是無(wú)止境的纱注，因此必須要對(duì)算法進(jìn)行優(yōu)化畏浆。優(yōu)化算法mbodSSP的核心思想是給予系統(tǒng)有限的計(jì)算和存儲(chǔ)空間，忽略較早時(shí)間幀的信息狞贱，只保留臨近幾幀的數(shù)據(jù)刻获。
實(shí)驗(yàn)結(jié)果
對(duì)于相鄰兩幀圖像特征選擇了檢測(cè)回歸框的大小、內(nèi)部顏色瞎嬉、位置蝎毡、IOU、相似度 佑颇，然后將特征相似度加權(quán)平均顶掉，作為節(jié)點(diǎn)間消耗f(i,j)，其中f(en)挑胸，f(ex)痒筒，f(i)都為設(shè)定值。
結(jié)果如下：
將原圖坐標(biāo)進(jìn)行透視變換可以獲取鳥(niǎo)瞰圖視角下的軌跡并可粗略估計(jì)行人相對(duì)車(chē)輛運(yùn)動(dòng)速度。
本篇文章源自本人畢業(yè)設(shè)計(jì)內(nèi)容且未發(fā)表簿透，因此部分內(nèi)容講解沒(méi)有很詳細(xì)移袍。如需轉(zhuǎn)載，請(qǐng)聯(lián)系本人＠铣洹Ｆ系痢！
