主流網絡模型之目标跟蹤

什麼是目标追蹤（Visual Object Tracking）？

跟蹤就是在連續的視訊幀中定位某一物體。

• 跟蹤VS檢測

1.跟蹤速度比檢測快

當你跟蹤在上一幀中檢測到的對象時，你會非常了解目标的外觀。你也知道在前一幀中的位置和它的運動的方向和速度。是以，在下一幀中，可以使用所有這些資訊來預測下一幀中目标的位置，并對對象的預期位置進行小範圍搜尋，以準确定位目标。是以，在設計高效的系統時，通常在每n幀上運作對象檢測，而在其間的n-1幀中采用跟蹤算法。

2.當檢測失敗時跟蹤來幫助

3.跟蹤保留身份資訊

目标檢測的輸出是包含目标的矩形數組。 但是，沒有辨別附加到對象。

•  幾大難點

外觀變形，光照變化，快速運動和運動模糊，背景相似幹擾：

平面外旋轉，平面内旋轉，尺度變化，遮擋和出視野等情況：

• 資料集

OTB50 & OTB100  (2013)

涉及到灰階圖像和彩色圖像，均可以免費下載下傳，涉及到目标跟蹤的11個屬性，包括光照變化、尺度變化、遮擋、形變、運動模糊、快速運動、平面内旋轉、平面外旋轉、出視野、背景幹擾、低像素。

VOT2013 - VOT2018 (競賽資料集,Each Year)

每年公開的60個序列，官方會對公開序列的前10名在隐藏資料集上測試，進而選出最終的winner，難度高于OTB。

• 評價名額

1、平均重疊期望（EAO）是對每個跟蹤器在一個短時圖像序列上的非重置重疊的期望值，是VOT評估跟蹤算法精度的最重要名額。

2、準确率（Accuracy）是指跟蹤器在單個測試序列下的平均重疊率（兩矩形框的相交部分面積除以兩矩形框的相并部分的面積。（MeanIOU）

3、魯棒性（Robustness）是指單個測試序列下的跟蹤器失敗次數，當重疊率為0時即可判定為失敗。

具體看一下這張圖就能明白：

目标追蹤的算法分類（Common Methods）

生成(generative)模型方法

生成類方法，在目前幀對目标區域模組化，下一幀尋找與模型最相似的區域就是預測位置，比較著名的有卡爾曼濾波，粒子濾波，mean-shift等。舉個例子，從目前幀知道了目标區域80%是紅色，20%是綠色，然後在下一幀，搜尋算法到處去找最符合這個顔色比例的區域。算法效果并不理想，是以現在用的很少。

判别(discriminative)模型方法

OTB50裡面的大部分方法都是這一類，經典套路，圖像特征+機器學習。

目前幀以目标區域為正樣本，背景區域為負樣本，機器學習訓練分類器，下一幀用訓練好的分類器找最優區域。

與生成類方法最大的差別，是分類器訓練過程中用到了背景資訊，這樣分類器專注區分前景和背景，判别類方法普遍都比生成類好。  經典判别類方法有Struck和TLD（Performace well in long-term task）。 判别類方法的最新發展就是相關濾波類方法，correlation filter簡稱CF，或discriminative correlation filter簡稱DCF，和深度學習(Deep ConvNet based)類方法，而DCF+CNN的做法成為最近VOT刷榜的标配。2018年的VOT，基于全卷積孿生網絡（SiamNet）的方法大崛起，憑借超越DCF方法的準确度和端到端訓練的優勢，成為目标追蹤新的研究方向。

CF算法示意圖

下圖是GitHub上釋出的2018VOT系統分支結構，上述算法都含在其中了。

北京飛搜科技&北京郵電大學代表隊送出的結果（CFWCR）獲得VOT 2017競賽公開的60個評測序列中第二名。方法基于業界流行的相關濾波的架構，使用了單CNN特征的多尺度追蹤方案。現有很多追蹤器融合了CNN特征和傳統的機器學習特征，如hog特征，CN顔色特征等。在他們的實驗中，發現CNN的淺層特征具有物體輪廓的資訊，高層的深度特征具有物體的語義資訊，将CNN的淺層和高層特征進行融合，能使追蹤器具有很好的性能。

VOT 2018 内測結果

· 相關濾波算法（CF）

Correlation Filter 最早應用于信号處理，用來描述兩個信号之間的相關性，或者說相似性，對于兩個資料 f 和g，則兩個信号的相關性為：

其中 f∗表示 f 的複共轭，這是和卷積的差別（相關性 與 卷積 類似，差別就在于裡面的共轭）。

對于圖像來講，問題描述為要找到一個 濾波模版 h，與輸入圖像 f 求相關性，得到相關圖 g。

模闆與圖形的相關運算

為了加快計算速度，這裡引入了傅裡葉變換，根據卷積定理（correlation版本）可知，函數互相關的傅裡葉變換等于函數傅裡葉變換的乘積：

CF的流程圖

· HCF（CF+CNN，Since 2015）

2015開始，深度學習開始進軍跟蹤領域，使用深度學習可以更好的提取目标的特征，對目标進行更好的表達。低層特征有較高的分辨率能夠對目标進行精準的定位，高層特征包含更多的語義資訊，能夠處理較大的目标變化和防止跟蹤器漂移，能夠對目标進行範圍定位。但是深度學習的缺點就在于網絡的訓練和速度，即使如HCF等使用離線的訓練速度仍然慢。

深度學習+CF

· SiamFC（Pure CNN）

SiamFC的結構

上面一支可以看做是一個模闆。其中z是第一幀所給出的目标框，φ 表示一種特征提取方法，SiamFC提取的是深度特征，經過全卷積網絡後得到一個6X6X128的feature map φ(z)。

下面一支x可以看為目前幀的搜尋區域，同樣提取了深度特征之後得到一個22X22X128的feature map φ(x)。

兩支的交彙是一個互相關層，可以看成是φ(z)在φ(x)上滑動搜尋，最後得到一個響應圖，圖上最大值對應的點就是算法認為的目标中心所在位置。

SiamRPN & DaSiamRPN

就像DSST之前的衆多相關濾波跟蹤算法一樣，SiamFC難以應對物體尺度的變化。SiamRPN[10]（CVPR18, B. Li et al.）則借鑒了目标檢測領域常用的RPN（Region Proposal Network，區域生成網絡）用于預測新圖像中目标的尺度。

SiamRPN在 x 和 z 經過孿生CNN得到各自的特征圖後，沒有直接對二者進行互相關運算，而是将這兩個特征圖各自放入RPN部分的兩個分支中，每個分支中的兩個特征圖分别經過一個CNN再進行互相關運算。RPN部分的兩個分支分别用于進行目标機率的預測和目标邊框的回歸，并且同樣借鑒了目标檢測領域的anchor方法，進而降低了目标邊框回歸的訓練難度。

SiamRPN（圖檔來源：[10]）

SiamRPN之後，作者又緊接着提出了改進版——DaSiamRPN[11]（ECCV18, Z. Zhu et al.），對訓練資料進行了增強以提升模型對同類别物體幹擾的判别能力（一般的模型往往着重于前景與背景的判别，而對相似物體的判别性較差）。另外，DaSiamRPN加入了增量學習的Distractor-aware子產品，在運作時采樣并更新模型的參數。使得模型能更好的遷移到目前視訊的域中。

DaSiamRPN在VOT實驗上的性能超越了ECO，同時還能跑到160FPS以上的速度。深度學習單目标跟蹤方法可以說得上是“風生水起”。

CIR (SiamDW)

SiamDW[12]的作者認為，較深的卷積神經網絡的感受域過大，這降低了特征的判别性和定位的準确性。另外，多層的padding使得孿生網絡的學習産生偏移。作者對網絡主幹的各種性質（padding，stride，感受域大小等）進行了系統性的研究分析，并得出了以下結論：1)孿生網絡跟蹤器傾向于更小的stride；2)感受域大小應取決于目标模闆圖像 z 的大小，一般60%到80%最佳；3)stride、感受域大小和輸出響應圖大小互相有很強的依賴，應當共同考慮；4)全卷積的孿生網絡應當盡可能消除 x 和 z 在感覺上的不一緻性。

針對上述結論，作者提出了CIR（Cropping-Inside-Residial）子產品以取代ResNet中的基本子產品，基本做法就是下圖中每個塊的addition之後的crop操作，除去受padding影響的邊緣部位。使用CIResNet-22作為主幹的改進版SiamFC和SiamRPN都有了不小的性能提升，隻是似乎這樣的做法依然無法讓網絡變得很深？

各種CIR block（圖檔來源：[12]）

SiamRPN++

SiamRPN++[13]是SiamRPN的作者在其基礎上的改進。主要改進有以下四點：1)使用了微調版的ResNet-50主幹，極大地優化了特征的提取；2)對ResNet-50的3、4、5階段的特征分别使用RPN進行邊框回歸與目标定位，并使用帶權重的融合方法結合三者的結果；3)使用了depth-wise互相關運算，減少參數量，加速了RPN部分的運算；4)最重要地，提出了一種spatial-aware的采樣政策，進而打破了目标跟蹤對CNN的嚴格平移不變性限制。

作者分析認為，隻有無padding的網絡才具有嚴格的平移不變性，而加深CNN又無法避免padding的出現。但是通過在訓練樣本中人工加入服從均勻分布的随機平移可一定程度上打破這種嚴格平移不變性限制。從模型的預測結果上來看，如果訓練資料在一定範圍内服從均勻分布，那麼理想情況下跟蹤器預測的結果也應該更接近均勻分布。作者通過定量實驗發現，加入像素範圍為32的随機平移後，最終得到的目标位置熱圖更接近均勻分布，說明預測的結果更接近實際測試目标的分布情況。

SiamRPN++（圖檔來源：[13]）

加入了以上幾點改進的SiamRPN++成為了OTB2015、VOT2018、UAV123、LaSOT和TrackingNet上的第一名，基于深度學習的方法終于在跟蹤準确度上領先一步了。

PS：從這幾年頂會的VOT論文數量看，基于深度學習方法也确實領先一步了……

PPS：除了上述的方法之外，基于深度學習的目标跟蹤還有不少值得一提的文章，如MDNet[14]，TCNN[15]，SANet[16]，CREST[17]，VITAL[18]等等，恕不能一一介紹。

PPPS：以上的相關濾波方法中大部分工作都包含相當複雜的數學推導，而本文沒有過多涉及，一來本人能力有限，二來篇幅也不宜過長。對其推導有興趣的同學請參考原文。

· FlowTrack

《End-to-end Flow Correlation Tracking with Spatial-temporal Attention》（2018CVPR，商湯）

閱讀筆記

背景：

①DCF方法很火（KCF、SAMF、LCT、MUSTer、SRDCF、CACF），但是  應用人工設定的特征使得這一類算法精度魯棒性都較差；

② 受深度學習影響，很多結合CNN的算法（DeepSRDCF、HCF、SiamFC）出現，它們都隻應用到目前幀的資訊而很少關注幀間存在的互資訊,并  且CNN的機制導緻了tracker在目标遇到運動模糊或者部分遮擋的時候，  性能隻能依靠離線train的特征的品質，魯棒性很難保證。

③ 盡管一些追蹤器用到了光流特征，但是這些模型是離線的，非端到端  的，是以結果是非最理想的。

  本文提出FlowTrack網絡，應用到flow information和appearance features，有機結合到端對端的網絡中，在VOT2015和VOT2016任務中，EAO屬性排名第一，速度為12FPS。

FlowTrack的網絡架構

結構是一個基于Siamese的雙流訓練網絡。分為historical branch和current branch. 在historical branch裡面，進行Flow的提取和warp操作融合階段，作者設計了一種spatial-temporal attention的機制。 在current branch，隻提取feature. Siamese結構兩支出來的feature送進DCF layer, 得到相應輸出。 總結來說，他們把Flow提取，warp操作，特征提取和融合，CF tracking都做成了網絡的layer，端到端地訓練它們。其中需要注意的是，wrap是指的是一種點到點的映射關系，實作flownet出來的光流圖到高階特征的映射。在從t-1到t-n的特征融合階段，設計了一種spatial-temporal attention的機制。在spatial attention中，是對空間位置上每一個待融合的點配置設定權重，具體采用餘弦距離衡量，結果就是和目前幀越相似配置設定的權重越大，反之越小；這麼做的問題是目前幀的權重永遠最大，是以本文借鑒SENet的思想進而設計了temporal attention，即把每一幀看做一個channel，設計一個品質判斷網絡。

(1)跟蹤使用的特征由Feature CNN提取；

Feature CNN：由三個卷積層構成(3x3x128, 3x3x128, 3x3x96)。

特征提取

(2)光流資訊由FlowNet提取；

FlowNet：2015年被提出，是用來提取光流場的深度網絡，9層卷積。

FlowNet的9層光流提取模型

(3) Warp操作按特征通道進行：

其中m表示通道，p表示原始圖像上點的坐标，δp表示點的光流，q表示特征圖上點的坐标，K是雙線性插值核。

 (4)Spatial-temporal attention給各通道特征賦予權值；

Spatial attention + Temporal attention

                                      空間             +            時間

時空提取attention子產品

Spatial 的提取：

計算Spatial attention，并融合特征。其中上标e表示通過Bottleneck結構（降維到特定空間）找到的嵌入層特征，p表示原始Feature map上的點坐标。總的來說，這個部分的實體意義是，對與t-1幀特征不相似的特征賦予低權重，反之，與其相似的賦予高權重。

temporal的加入：Spatial Attention的問題是目前幀的權重永遠最大，解決方法引入Temporal 機制，設計一個品質判斷網絡：從Spatial attention輸出來的權重map，輸入Temporal attention結構，經過一個類似SE-Net（ImageNet Classification Champion，2017，Momenta）的結構，得到通道重要性權值，可以看作是對Spatial attention的二次調整。

實驗結果

多政策的對比

VOT 2016 1st

VOT 2017 2rd

DeepSort

Deep SORT是多目标跟蹤(Multi-Object Tracking)中常用到的一種算法，是一個Detection Based Tracking的方法。這個算法工業界關注度非常高，在知乎上有很多文章都是使用了Deep SORT進行工程部署。筆者将參考前輩的部落格，結合自己的實踐(理論&代碼)對Deep SORT算法進行代碼層面的解析。

在之前筆者寫的一篇Deep SORT論文閱讀總結中，總結了DeepSORT論文中提到的核心觀點，如果對Deep SORT不是很熟悉，可以先了解一下，然後再來看解讀代碼的部分。

由于知乎對文章篇幅有限制，是以分上下篇發。

上篇将梳理SORT、Deep SORT，以類圖為主，講解DeepSORT代碼部分的各個子產品。

下篇主要是梳理運作的流程，對照流程圖進行代碼層面了解。以及最後的總結+代碼推薦。

1. MOT主要步驟

在《DEEP LEARNING IN VIDEO MULTI-OBJECT TRACKING: A SURVEY》這篇基于深度學習的多目标跟蹤的綜述中，描述了MOT問題中四個主要步驟：

• 給定視訊原始幀。
• 運作目标檢測器如Faster R-CNN、YOLOv3、SSD等進行檢測，擷取目标檢測框。
• 将所有目标框中對應的目标摳出來，進行特征提取（包括表觀特征或者運動特征）。
• 進行相似度計算，計算前後兩幀目标之間的比對程度（前後屬于同一個目标的之間的距離比較小，不同目标的距離比較大）
• 資料關聯，為每個對象配置設定目标的ID。

以上就是四個核心步驟，其中核心是檢測，SORT論文的摘要中提到，僅僅換一個更好的檢測器，就可以将目标跟蹤表現提升18.9%。

2. SORT

Deep SORT算法的前身是SORT, 全稱是Simple Online and Realtime Tracking。簡單介紹一下，SORT最大特點是基于Faster R-CNN的目标檢測方法，并利用卡爾曼濾波算法+匈牙利算法，極大提高了多目标跟蹤的速度，同時達到了SOTA的準确率。

這個算法确實是在實際應用中使用較為廣泛的一個算法，核心就是兩個算法：卡爾曼濾波和匈牙利算法。

卡爾曼濾波算法分為兩個過程，預測和更新。該算法将目标的運動狀态定義為8個正态分布的向量。

預測：當目标經過移動，通過上一幀的目标框和速度等參數，預測出目前幀的目标框位置和速度等參數。

更新：預測值和觀測值，兩個正态分布的狀态進行線性權重，得到目前系統預測的狀态。

**匈牙利算法：**解決的是一個配置設定問題，在MOT主要步驟中的計算相似度的，得到了前後兩幀的相似度矩陣。匈牙利算法就是通過求解這個相似度矩陣，進而解決前後兩幀真正比對的目标。這部分sklearn庫有對應的函數linear_assignment來進行求解。

SORT算法中是通過前後兩幀IOU來建構相似度矩陣，是以SORT計算速度非常快。

下圖是一張SORT核心算法流程圖：

Detections是通過目标檢測器得到的目标框，Tracks是一段軌迹。核心是比對的過程與卡爾曼濾波的預測和更新過程。

流程如下：目标檢測器得到目标框Detections，同時卡爾曼濾波器預測目前的幀的Tracks, 然後将Detections和Tracks進行IOU比對，最終得到的結果分為：

• Unmatched Tracks，這部分被認為是失配，Detection和Track無法比對，如果失配持續了

  

  次，該目标ID将從圖檔中删除。
• Unmatched Detections, 這部分說明沒有任意一個Track能比對Detection, 是以要為這個detection配置設定一個新的track。
• Matched Track，這部分說明得到了比對。

卡爾曼濾波可以根據Tracks狀态預測下一幀的目标框狀态。

卡爾曼濾波更新是對觀測值(比對上的Track)和估計值更新所有track的狀态。

3. Deep SORT

DeepSort中最大的特點是加入外觀資訊，借用了ReID領域模型來提取特征，減少了ID switch的次數。整體流程圖如下：

可以看出，Deep SORT算法在SORT算法的基礎上增加了級聯比對(Matching Cascade)+新軌迹的确認(confirmed)。總體流程就是：

• 卡爾曼濾波器預測軌迹Tracks
• 使用匈牙利算法将預測得到的軌迹Tracks和目前幀中的detections進行比對(級聯比對和IOU比對)
• 卡爾曼濾波更新。

其中上圖中的級聯比對展開如下：

上圖非常清晰地解釋了如何進行級聯比對，上圖由虛線劃分為兩部分：

上半部分中計算相似度矩陣的方法使用到了外觀模型(ReID)和運動模型(馬氏距離)來計算相似度，得到代價矩陣，另外一個則是門控矩陣，用于限制代價矩陣中過大的值。

下半部分中是是級聯比對的資料關聯步驟，比對過程是一個循環(max age個疊代，預設為70)，也就是從missing age=0到missing age=70的軌迹和Detections進行比對，沒有丢失過的軌迹優先比對，丢失較為久遠的就靠後比對。通過這部分處理，可以重新将被遮擋目标找回，降低被遮擋然後再出現的目标發生的ID Switch次數。

将Detection和Track進行比對，是以出現幾種情況

1. Detection和Track比對，也就是Matched Tracks。普通連續跟蹤的目标都屬于這種情況，前後兩幀都有目标，能夠比對上。
2. Detection沒有找到比對的Track，也就是Unmatched Detections。圖像中突然出現新的目标的時候，Detection無法在之前的Track找到比對的目标。
3. Track沒有找到比對的Detection，也就是Unmatched Tracks。連續追蹤的目标超出圖像區域，Track無法與目前任意一個Detection比對。
4. 以上沒有涉及一種特殊的情況，就是兩個目标遮擋的情況。剛剛被遮擋的目标的Track也無法比對Detection，目标暫時從圖像中消失。之後被遮擋目标再次出現的時候，應該盡量讓被遮擋目标配置設定的ID不發生變動，減少ID Switch出現的次數，這就需要用到級聯比對了。

視訊來源：目标跟蹤初探（DeepSORT）

目前主流的目标跟蹤算法都是基于Tracking-by-Detecton政策，即基于目标檢測的結果來進行目标跟蹤。DeepSORT運用的就是這個政策，上面的視訊是DeepSORT對人群進行跟蹤的結果，每個bbox左上角的數字是用來辨別某個人的唯一ID号。

這裡就有個問題，視訊中不同時刻的同一個人，位置發生了變化，那麼是如何關聯上的呢？答案就是匈牙利算法和卡爾曼濾波。

• 匈牙利算法可以告訴我們目前幀的某個目标，是否與前一幀的某個目标相同。
• 卡爾曼濾波可以基于目标前一時刻的位置，來預測目前時刻的位置，并且可以比傳感器（在目标跟蹤中即目标檢測器，比如Yolo等）更準确的估計目标的位置。

匈牙利算法（Hungarian Algorithm）

首先，先介紹一下什麼是配置設定問題（Assignment Problem）：假設有N個人和N個任務，每個任務可以任意配置設定給不同的人，已知每個人完成每個任務要花費的代價不盡相同，那麼如何配置設定可以使得總的代價最小。

舉個例子，假設現在有3個任務，要分别配置設定給3個人，每個人完成各個任務所需代價矩陣（cost matrix）如下所示（這個代價可以是金錢、時間等等）：

怎樣才能找到一個最優配置設定，使得完成所有任務花費的代價最小呢？

匈牙利算法（又叫KM算法）就是用來解決配置設定問題的一種方法，它基于定理：

如果代價矩陣的某一行或某一列同時加上或減去某個數，則這個新的代價矩陣的最優配置設定仍然是原代價矩陣的最優配置設定。

算法步驟（假設矩陣為NxN方陣）：

1. 對于矩陣的每一行，減去其中最小的元素
2. 對于矩陣的每一列，減去其中最小的元素
3. 用最少的水準線或垂直線覆寫矩陣中所有的0
4. 如果線的數量等于N，則找到了最優配置設定，算法結束，否則進入步驟5
5. 找到沒有被任何線覆寫的最小元素，每個沒被線覆寫的行減去這個元素，每個被線覆寫的列加上這個元素，傳回步驟3

繼續拿上面的例子做示範：

step1 每一行最小的元素分别為15、20、20，減去得到：

step2 每一列最小的元素分别為0、20、5，減去得到：

step3 用最少的水準線或垂直線覆寫所有的0，得到：

step4 線的數量為2，小于3，進入下一步；

step5 現在沒被覆寫的最小元素是5，沒被覆寫的行（第一和第二行）減去5，得到：

被覆寫的列（第一列）加上5，得到：

跳轉到step3，用最少的水準線或垂直線覆寫所有的0，得到：

step4：線的數量為3，滿足條件，算法結束。顯然，将任務2配置設定給第1個人、任務1配置設定給第2個人、任務3配置設定給第3個人時，總的代價最小（0+0+0=0）：

是以原矩陣的最小總代價為（40+20+25=85）：

sklearn裡的linear_assignment()函數以及scipy裡的linear_sum_assignment()函數都實作了匈牙利算法，兩者的傳回值的形式不同：

import numpy as np 
from sklearn.utils.linear_assignment_ import linear_assignment
from scipy.optimize import linear_sum_assignment
 

cost_matrix = np.array([
    [15,40,45],
    [20,60,35],
    [20,40,25]
])
 
matches = linear_assignment(cost_matrix)
print('sklearn API result:\n', matches)
matches = linear_sum_assignment(cost_matrix)
print('scipy API result:\n', matches)
 

"""Outputs
sklearn API result:
 [[0 1]
  [1 0]
  [2 2]]
scipy API result:
 (array([0, 1, 2], dtype=int64), array([1, 0, 2], dtype=int64))
"""
           

在DeepSORT中，匈牙利算法用來将前一幀中的跟蹤框tracks與目前幀中的檢測框detections進行關聯，通過外觀資訊（appearance information）和馬氏距離（Mahalanobis distance），或者IOU來計算代價矩陣。

源碼解讀：

#  linear_assignment.py
def min_cost_matching(distance_metric, max_distance, tracks, detections, 
                      track_indices=None, detection_indices=None):
    ...
    
    # 計算代價矩陣
    cost_matrix = distance_metric(tracks, detections, track_indices, detection_indices)
    cost_matrix[cost_matrix > max_distance] = max_distance + 1e-5
    
    # 執行匈牙利算法，得到比對成功的索引對，行索引為tracks的索引，列索引為detections的索引
    row_indices, col_indices = linear_assignment(cost_matrix)
 
    matches, unmatched_tracks, unmatched_detections = [], [], []
 
    # 找出未比對的detections
    for col, detection_idx in enumerate(detection_indices):
        if col not in col_indices:
            unmatched_detections.append(detection_idx)
     
    # 找出未比對的tracks
    for row, track_idx in enumerate(track_indices):
        if row not in row_indices:
            unmatched_tracks.append(track_idx)
    
    # 周遊比對的(track, detection)索引對
    for row, col in zip(row_indices, col_indices):
        track_idx = track_indices[row]
        detection_idx = detection_indices[col]
        # 如果相應的cost大于門檻值max_distance，也視為未比對成功
        if cost_matrix[row, col] > max_distance:
            unmatched_tracks.append(track_idx)
            unmatched_detections.append(detection_idx)
        else:
            matches.append((track_idx, detection_idx))
 
    return matches, unmatched_tracks, unmatched_detections
           

卡爾曼濾波（Kalman Filter）

卡爾曼濾波被廣泛應用于無人機、自動駕駛、衛星導航等領域，簡單來說，其作用就是基于傳感器的測量值來更新預測值，以達到更精确的估計。

假設我們要跟蹤小車的位置變化，如下圖所示，藍色的分布是卡爾曼濾波預測值，棕色的分布是傳感器的測量值，灰色的分布就是預測值基于測量值更新後的最優估計。

Kalman Filter

在目标跟蹤中，需要估計track的以下兩個狀态：

均值(Mean)：表示目标的位置資訊，由bbox的中心坐标 (cx, cy)，寬高比r，高h，以及各自的速度變化值組成，由8維向量表示為 x = [cx, cy, r, h, vx, vy, vr, vh]，各個速度值初始化為0。

協方差(Covariance )：表示目标位置資訊的不确定性，由8x8的對角矩陣表示，矩陣中數字越大則表明不确定性越大，可以以任意值初始化。

卡爾曼濾波分為兩個階段：(1) 預測track在下一時刻的位置，(2) 基于detection來更新預測的位置。

下面将介紹這兩個階段用到的計算公式。（這裡不涉及公式的原理推導，因為我也不清楚原理(ಥ_ಥ) ，隻是說明一下各個公式的作用）

預測

基于track在t-1時刻的狀态來預測其在t時刻的狀态。

在公式1中，x為track在t-1時刻的均值，F稱為狀态轉移矩陣，該公式預測t時刻的x'：

矩陣F中的dt是目前幀和前一幀之間的差，将等号右邊的矩陣乘法展開，可以得到cx'=cx+dt*vx，cy'=cy+dt*vy...，是以這裡的卡爾曼濾波是一個勻速模型（Constant Velocity Model）。

在公式2中，P為track在t-1時刻的協方差，Q為系統的噪聲矩陣，代表整個系統的可靠程度，一般初始化為很小的值，該公式預測t時刻的P'。

源碼解讀：

#  kalman_filter.py
def predict(self, mean, covariance):
    """Run Kalman filter prediction step.
    
    Parameters
    ----------
    mean: ndarray, the 8 dimensional mean vector of the object state at the previous time step.
    covariance: ndarray, the 8x8 dimensional covariance matrix of the object state at the previous time step.
 
    Returns
    -------
    (ndarray, ndarray), the mean vector and covariance matrix of the predicted state. 
     Unobserved velocities are initialized to 0 mean.
    """
    std_pos = [
        self._std_weight_position * mean[3],
        self._std_weight_position * mean[3],
        1e-2,
        self._std_weight_position * mean[3]]
    std_vel = [
        self._std_weight_velocity * mean[3],
        self._std_weight_velocity * mean[3],
        1e-5,
        self._std_weight_velocity * mean[3]]
    
    motion_cov = np.diag(np.square(np.r_[std_pos, std_vel]))  # 初始化噪聲矩陣Q
    mean = np.dot(self._motion_mat, mean)  # x' = Fx
    covariance = np.linalg.multi_dot((self._motion_mat, covariance, self._motion_mat.T)) + motion_cov  # P' = FPF(T) + Q
 
    return mean, covariance
           

更新

基于t時刻檢測到的detection，校正與其關聯的track的狀态，得到一個更精确的結果。

在公式3中，z為detection的均值向量，不包含速度變化值，即z=[cx, cy, r, h]，H稱為測量矩陣，它将track的均值向量x'映射到檢測空間，該公式計算detection和track的均值誤差；

在公式4中，R為檢測器的噪聲矩陣，它是一個4x4的對角矩陣，對角線上的值分别為中心點兩個坐标以及寬高的噪聲，以任意值初始化，一般設定寬高的噪聲大于中心點的噪聲，該公式先将協方差矩陣P'映射到檢測空間，然後再加上噪聲矩陣R；

公式5計算卡爾曼增益K，卡爾曼增益用于估計誤差的重要程度；

公式6和公式7得到更新後的均值向量x和協方差矩陣P。

源碼解讀：

#  kalman_filter.py
def project(self, mean, covariance):
    """Project state distribution to measurement space.
        
    Parameters
    ----------
    mean: ndarray, the state's mean vector (8 dimensional array).
    covariance: ndarray, the state's covariance matrix (8x8 dimensional).

    Returns
    -------
    (ndarray, ndarray), the projected mean and covariance matrix of the given state estimate.
    """
    std = [self._std_weight_position * mean[3],
           self._std_weight_position * mean[3],
           1e-1,
           self._std_weight_position * mean[3]]
        
    innovation_cov = np.diag(np.square(std))  # 初始化噪聲矩陣R
    mean = np.dot(self._update_mat, mean)  # 将均值向量映射到檢測空間，即Hx'
    covariance = np.linalg.multi_dot((
        self._update_mat, covariance, self._update_mat.T))  # 将協方差矩陣映射到檢測空間，即HP'H^T
    return mean, covariance + innovation_cov


def update(self, mean, covariance, measurement):
    """Run Kalman filter correction step.

    Parameters
    ----------
    mean: ndarra, the predicted state's mean vector (8 dimensional).
    covariance: ndarray, the state's covariance matrix (8x8 dimensional).
    measurement: ndarray, the 4 dimensional measurement vector (x, y, a, h), where (x, y) is the 
                 center position, a the aspect ratio, and h the height of the bounding box.
    Returns
    -------
    (ndarray, ndarray), the measurement-corrected state distribution.
    """
    # 将mean和covariance映射到檢測空間，得到Hx'和S
    projected_mean, projected_cov = self.project(mean, covariance)
    # 矩陣分解（這一步沒看懂）
    chol_factor, lower = scipy.linalg.cho_factor(projected_cov, lower=True, check_finite=False)
    # 計算卡爾曼增益K（這一步沒看明白是如何對應上公式5的，求線代大佬指教）
    kalman_gain = scipy.linalg.cho_solve(
            (chol_factor, lower), np.dot(covariance, self._update_mat.T).T,
            check_finite=False).T
    # z - Hx'
    innovation = measurement - projected_mean
    # x = x' + Ky
    new_mean = mean + np.dot(innovation, kalman_gain.T)
    # P = (I - KH)P'
    new_covariance = covariance - np.linalg.multi_dot((kalman_gain, projected_cov, kalman_gain.T))
        
    return new_mean, new_covariance
           

DeepSort工作流程

DeepSORT對每一幀的處理流程如下：

檢測器得到bbox → 生成detections → 卡爾曼濾波預測→ 使用匈牙利算法将預測後的tracks和目前幀中的detecions進行比對（級聯比對和IOU比對） → 卡爾曼濾波更新

Frame 0：檢測器檢測到了3個detections，目前沒有任何tracks，将這3個detections初始化為tracks

Frame 1：檢測器又檢測到了3個detections，對于Frame 0中的tracks，先進行預測得到新的tracks，然後使用匈牙利算法将新的tracks與detections進行比對，得到(track, detection)比對對，最後用每對中的detection更新對應的track

檢測

使用Yolo作為檢測器，檢測目前幀中的bbox：

#  demo_yolo3_deepsort.py
def detect(self):
    while self.vdo.grab():
	...
	bbox_xcycwh, cls_conf, cls_ids = self.yolo3(im)  # 檢測到的bbox[cx,cy,w,h]，置信度，類别id
	if bbox_xcycwh is not None:
    	    # 篩選出人的類别
    	    mask = cls_ids == 0
  	    bbox_xcycwh = bbox_xcycwh[mask]
  	    bbox_xcycwh[:, 3:] *= 1.2
   	    cls_conf = cls_conf[mask]
            ...
           

生成detections

将檢測到的bbox轉換成detections：

#  deep_sort.py
def update(self, bbox_xywh, confidences, ori_img):
    self.height, self.width = ori_img.shape[:2]
    # 提取每個bbox的feature
    features = self._get_features(bbox_xywh, ori_img)
    # [cx,cy,w,h] -> [x1,y1,w,h]
    bbox_tlwh = self._xywh_to_tlwh(bbox_xywh)
    # 過濾掉置信度小于self.min_confidence的bbox，生成detections
    detections = [Detection(bbox_tlwh[i], conf, features[i]) for i,conf in enumerate(confidences) if conf > self.min_confidence]
    # NMS (這裡self.nms_max_overlap的值為1，即保留了所有的detections)
    boxes = np.array([d.tlwh for d in detections])
    scores = np.array([d.confidence for d in detections])
    indices = non_max_suppression(boxes, self.nms_max_overlap, scores)
    detections = [detections[i] for i in indices]
    ...
           

卡爾曼濾波預測階段

使用卡爾曼濾波預測前一幀中的tracks在目前幀的狀态：

#  track.py
def predict(self, kf):
    """Propagate the state distribution to the current time step using a 
       Kalman filter prediction step.
    Parameters
    ----------
    kf: The Kalman filter.
    """
    self.mean, self.covariance = kf.predict(self.mean, self.covariance)  # 預測
    self.age += 1  # 該track自出現以來的總幀數加1
    self.time_since_update += 1  # 該track自最近一次更新以來的總幀數加1
           

比對

首先對基于外觀資訊的馬氏距離計算tracks和detections的代價矩陣，然後相繼進行級聯比對和IOU比對，最後得到目前幀的所有比對對、未比對的tracks以及未比對的detections：

#  tracker.py
def _match(self, detections):
    def gated_metric(racks, dets, track_indices, detection_indices):
        """
        基于外觀資訊和馬氏距離，計算卡爾曼濾波預測的tracks和目前時刻檢測到的detections的代價矩陣
        """
        features = np.array([dets[i].feature for i in detection_indices])
        targets = np.array([tracks[i].track_id for i in track_indices]
	# 基于外觀資訊，計算tracks和detections的餘弦距離代價矩陣
        cost_matrix = self.metric.distance(features, targets)
	# 基于馬氏距離，過濾掉代價矩陣中一些不合适的項 (将其設定為一個較大的值)
        cost_matrix = linear_assignment.gate_cost_matrix(self.kf, cost_matrix, tracks, 
                      dets, track_indices, detection_indices)
        return cost_matrix

    # 區分開confirmed tracks和unconfirmed tracks
    confirmed_tracks = [i for i, t in enumerate(self.tracks) if t.is_confirmed()]
    unconfirmed_tracks = [i for i, t in enumerate(self.tracks) if not t.is_confirmed()]

    # 對confirmd tracks進行級聯比對
    matches_a, unmatched_tracks_a, unmatched_detections = \
        linear_assignment.matching_cascade(
            gated_metric, self.metric.matching_threshold, self.max_age,
            self.tracks, detections, confirmed_tracks)

    # 對級聯比對中未比對的tracks和unconfirmed tracks中time_since_update為1的tracks進行IOU比對
    iou_track_candidates = unconfirmed_tracks + [k for k in unmatched_tracks_a if
                                                 self.tracks[k].time_since_update == 1]
    unmatched_tracks_a = [k for k in unmatched_tracks_a if
                          self.tracks[k].time_since_update != 1]
    matches_b, unmatched_tracks_b, unmatched_detections = \
        linear_assignment.min_cost_matching(
            iou_matching.iou_cost, self.max_iou_distance, self.tracks,
            detections, iou_track_candidates, unmatched_detections)
	
    # 整合所有的比對對和未比對的tracks
    matches = matches_a + matches_b
    unmatched_tracks = list(set(unmatched_tracks_a + unmatched_tracks_b))
    
    return matches, unmatched_tracks, unmatched_detections


# 級聯比對源碼  linear_assignment.py
def matching_cascade(distance_metric, max_distance, cascade_depth, tracks, detections, 
                     track_indices=None, detection_indices=None):
    ...
    unmatched_detections = detection_indice
    matches = []
    # 由小到大依次對每個level的tracks做比對
    for level in range(cascade_depth):
	# 如果沒有detections，退出循環
        if len(unmatched_detections) == 0:  
            break
	# 目前level的所有tracks索引
        track_indices_l = [k for k in track_indices if 
                           tracks[k].time_since_update == 1 + level]
	# 如果目前level沒有track，繼續
        if len(track_indices_l) == 0: 
            continue
		
	# 匈牙利比對
        matches_l, _, unmatched_detections = min_cost_matching(distance_metric, max_distance, tracks, detections, 
                                                               track_indices_l, unmatched_detections)
        
	matches += matches_l
	unmatched_tracks = list(set(track_indices) - set(k for k, _ in matches))
    return matches, unmatched_tracks, unmatched_detections
           

卡爾曼濾波更新階段

對于每個比對成功的track，用其對應的detection進行更新，并處理未比對tracks和detections：

#  tracker.py
def update(self, detections):
    """Perform measurement update and track management.
    Parameters
    ----------
    detections: List[deep_sort.detection.Detection]
                A list of detections at the current time step.
    """
    # 得到比對對、未比對的tracks、未比對的dectections
    matches, unmatched_tracks, unmatched_detections = self._match(detections)

    # 對于每個比對成功的track，用其對應的detection進行更新
    for track_idx, detection_idx in matches:
        self.tracks[track_idx].update(self.kf, detections[detection_idx])
    
	# 對于未比對的成功的track，将其标記為丢失
	for track_idx in unmatched_tracks:
        self.tracks[track_idx].mark_missed()
	
    # 對于未比對成功的detection，初始化為新的track
    for detection_idx in unmatched_detections:
        self._initiate_track(detections[detection_idx])
    
	...
           

參考：

Deep Sort with PyTorch deep_sort_pytorch

Deep SORT多目标跟蹤算法代碼解析(上)

Deep SORT多目标跟蹤算法代碼解析(下)

CenterNet+ deepsort實作多目标跟蹤

Centernet+deepsort代碼 https://github.com/kimyoon-young/centerNet-deep-sort

CenterTrack

論文連結：https://arxiv.org/pdf/2004.01177.pdf

項目連結：https://github.com/xingyizhou/CenterTrack

研究者将其跟蹤器命名為 CenterTrack，該方法對一對圖像應用檢測模型，并利用前一幀的檢測結果。給定最小輸入，CenterTrack 可以定位目标，并預測它們和前一幀的關聯。CenterTrack 就是這麼簡單、線上（不窺探未來）、實時。

從效果上來看，CenterTrack 在 MOT17 資料集上以 22 FPS 運作，達到了 67.3% 的 MOTA 值；在 KITTI 跟蹤基準上以 15 FPS 運作，取得了 89.4% 的 MOTA 值，在這兩個資料集上均取得了新的目前最優結果。

此外，CenterTrack 很容易擴充到單目 3D 跟蹤，隻需恢複額外的 3D 屬性即可。以單目視訊作為輸入，以 28 FPS 運作，CenterTrack 在新釋出的 nuScenes 3D 跟蹤基準上實作了 28.3% [email protected]，顯著超過單目基線方法。

基于深度學習端到端的多目标跟蹤算法。(代表性的算法有SST)

現階段end-to-end的算法還不多，大多處于實驗室刷榜階段，有進一步落地應用的及時更新。相關論文和代碼如下:

· DAN: "Deep Affinity Network for Multiple Object Tracking" [paper] [code] In TPAMI 2019.

· MCSA: "Multi-Object Tracking with Multiple Cues and Switcher-Aware Classification" [paper] In CVPR 2019.

（這篇文章沒有開源，基于SiameseRPN單目标跟蹤器和行人ReID的多目标跟蹤算法，解決長期跟蹤下的目标漂移問題。利用SiameseRPN擷取短期的目标線索，利用ReID特征計算目标間的比對置信度，基于該置信度建構二分圖，求解最小費用流得到長期的跟蹤結果）

上述文章參考來源：

github.com/SpyderXu/multi-object-tracking-paper-list

多目标跟蹤算法對比

最新進展

工業界青睐的算法在學術界其實并不重視，一方面是因為開源的原因，另一方面可以看到頂會的算法都不是注重速度的，通常用了很複雜的子產品和trick來提升精度。

而且這些trick不是一般意義的trick了，是針對這個資料集的或者說針對糟糕檢測器的一些trick， 對于實際應用幾乎沒有幫助。

第一篇論文是基于DeepSORT改進的，它的創新點在于引入了軌迹評分機制，時間越久的軌迹可信度就越高，基于這個評分就可以把軌迹産生的預測框和檢測框放一起做一個NMS，相當于是用預測彌補了漏檢。

第二篇論文是今年9月份發在arxiv上的一篇論文，它的工作是把檢測網絡和嵌入網絡結合起來，追求的是速度和精度的trade off。