# Tracking - Deep SORT
> [name=謝朋諺(Adam Hsieh)]
> [time=Wed, Jul 31, 2019 4:45 PM]
###### tags: `paper`,`IVA`,`track`

---

## Reference
> [论文翻译：Deep SORT: Simple Online and Realtime Tracking with a Deep Association Metric](https://blog.csdn.net/zjc910997316/article/details/83721573)
> [多目標跟踪(MOT)論文隨筆-SIMPLE ONLINE AND REALTIME TRACKING WITH A DEEP ASSOCIATION METRIC (Deep SORT)](https://www.cnblogs.com/yanwei-li/p/8643446.html)
> [多目标跟踪：SORT和Deep SORT](https://zhuanlan.zhihu.com/p/59148865)
> [【算法分析】SORT/Deep SORT 物体跟踪算法解析](https://blog.csdn.net/HaoBBNuanMM/article/details/85555547)
> [多目标跟踪方法：deep-sort](https://www.cnblogs.com/YiXiaoZhou/p/7074037.html)
> [DeepSort论文学习](https://blog.csdn.net/cdknight_happy/article/details/79731981)
> [[Github] Deep SORT](https://github.com/bendidi/deep_sort/tree/60e082dd132d89d2645f6a4d0c75353a05510176)

---

# Simple Online And Realtime Tracking With A Deep Association Metric
[論文連結](https://arxiv.org/pdf/1703.07402.pdf)
{%pdf https://arxiv.org/pdf/1703.07402.pdf %}

## 摘要
* 本文擴展了外觀的資訊以改進 SORT 的效能，由於這種擴充方法我們才可以更長時間的遮擋並繼續追蹤物件，從而有效地減少了身份轉換的數量。
* 實驗評估我們的方法可以減少 45% 的身份交換數量。

## Method
==Recursive Kalman Filtering==、==Frame-by-Frame Data Association==

### Track Handling and State Estimation
* 運動狀態估計：與 SORT 相似使用了 8 個參數 $(u,v,r,h,\dot x,\dot y,\dot r,\dot h)$ 來進行運動狀態的描述。
* $u,v$ 指的是 Bounding Box 的中心座標。
* $r$ 是長寬比。
* $h$ 是高度。
* 其餘四個變數表示對應在影像座標系中的速度資訊。
* 使用一個[==卡爾曼濾波器(Kalman)==](http://silverwind1982.pixnet.net/blog/post/167680859-%E5%8D%A1%E7%88%BE%E6%9B%BC%E6%BF%BE%E6%B3%A2-%28kalman-filter%29) 預測更新軌跡，該卡爾曼濾波器採用均速模型和線性觀測模型，其觀測變量為 $(u,v,r,h)$。
* 軌跡處理 (物件軌跡創建與移除)：對於每個軌跡 $k$ 都有一個 $a_k$ 用於紀錄從上一次成功匹配到當前時刻的 Frame 數，一旦一個物件的檢測結果與追蹤結果正確關聯之後，就將參數設為 0。
* 如果 $a_k$ 超過設置的最大閾值 $A_{max}$，則認為該物件的追蹤過程已結束。
* 對於新物件出現的判斷則是如果 Detection 結果始終無法與已經存在的 Tracker 進行關聯，那就是出現新物件，如果連續的 3 個 frame 中新的 Tracker 對物件位置的預測結果都能夠與檢測結果關聯，那就確認為新的物件軌跡，不能就予以刪除。
* 新生成的軌跡會被標註為 'tentative'，直到確認後才被標為 'confirmed'，否則就是假性軌跡，狀態標註為 'deleted'。

### Assignment Problem
* 傳統解決檢測結果與追蹤預測結果的關聯法方式是用[==匈牙利算法(Hungarian)==](https://blog.csdn.net/u014754127/article/details/78086014)。
* 本文結合了兩種適當的指標來整合 ==Motion== 和 ==Appearance== 資訊。
* **Motion 的關聯**：使用卡爾曼預測結果與檢測結果之間的馬氏距離進行關聯。
* 公式為：==$d^{(1)}(i,j)=(d_j-y_i)^TS_i^{-1}(d_j-y_j)$==
* 其中 $d_j$ 表示第 $j$ 個檢測框的位置 $(u,v,r,h)$。
* $y_i$ 表示第 $i$ 個 Tracker 對物件的預測位置。
* $S_i$ 表示檢測位置與平均追蹤位置之間的共變異數矩陣。
* 如果某次關聯的馬氏距離小於閾值 $t^{(1)}$，則設置 Motion 狀態的關聯成功。
* 函數公式為：==$b^{(1)}_{i,j}=\mathbb{1}[d^{(1)}(i,j)\leq t^{(1)}]$==。
* 如果第 $i$ 個 track 和第 $j$ 個檢測的關聯性是可接受的，則評估為 1。
* 閾值 $t^{(1)}$ 我們設為 9.4877。
* **Appearance 的關聯**：當運動的不確定性很低的話上述的馬氏距離匹配是一個合適的關聯度量方法。但是在影像空間中使用卡爾曼濾波進行運動狀態估計只是一個比較粗糙的預測，特別是相機本身也存在運動的話會使得馬氏距離失效，造成 ID switch 的現象。
* 對每一個檢測結果 $d_j$ 求特徵向量 $r_j$，並且限制 $||r_i||=1$。
* 對每一個追蹤物件創一個 gallery $R_k=\{r_k^{(i)}\}_{k=1}^{L_k}$，儲存每一個追蹤物件成功關聯的最近 100 個 Frame $L_k=100$ 的特徵向量。
* 也就是說計算第 $i$ 個 tracker 的最近 100 個成功關聯的特徵集與當前 Frame 第 $j$ 個檢測結果的特徵向量間的最小餘弦距離，公式為：
==$d^{(2)}(i,j)=min\{1-r_j^Tr_k^{(i)}|r_k^{(i)}\in R_i\}$==。
* 如果上面公式距離小於指定的閾值，那麼這個評估就是 1：
==$b^{(2)}_{i,j}=\mathbb{1}[d^{(2)}(i,j)\leq t^{(2)}]$==。
* 閾值是從訓練集中得到的。
* 這兩種指標提供不同指派方面的補充，==**馬氏距離**== 提供關於基於運動的可能物件位置，這對於短期預測特別有用，另一方面，==**餘弦距離**== 考慮外觀資訊，這對於長期遮擋之後恢復身份特別有用，因此我們使用==加權和==來組合這兩個度量方式：
==$c_{i,j}=\lambda d^{(1)}(i,j)+(1-\lambda )d^{(2)}(i,j)$==
* 代表第 i 個物體跟蹤和第 j 個物體檢測之間關聯的總公式。
* 如果他在不等式上的兩個指標區間內即代表是關聯，公式為：$b_{i,j}=\displaystyle\prod_{m=1}^2b_{i,j}^{(m)}$
* 可以通過參數 $\lambda$ 來控制每個度量對關聯成本的影響，在我們實驗中發現當存在相機運動的情況時，可以設置 $\lambda =0$，但是馬氏距離還是有幫助，因為若不滿足就不能進入融合階段。

### Matching Cascade
* 物體被遮擋一段時間後，卡爾曼濾波預測的不確定性大大增加並且狀態空間上可觀察性變得很低，並且馬氏距離更傾向於不確定性更大的 Track，這是由於減少了 Detection 的標準差距預計的軌跡的距離。因此這裡引入級聯匹配，優先匹配 Detection 與最近出現的 Track。

$T$ 是物體跟蹤集合
$D$ 是物體檢測集合
$A_{max}$ 是最大可接受跨 Frame 遮擋數量
1. $C$ 矩陣存放所有物體追蹤 $i$ 與物體檢測 $j$ 之間距離的計算結果。
2. $B$ 矩陣存放所有物體追蹤 $i$ 與物體檢測 $j$ 之間是否關聯的判斷 (0/1)。
3. 關聯集合 $M$ 初始化為空集合。
4. 將找不到匹配的物體檢測集合 $U$ 初始化為 $D$。
5. 從上一次匹配成功的 Tracker 跑迴圈到最多 $A_{max}$ 次沒有匹配的 Tracker。
6. 選擇滿足條件的 Tracker 集合 $T_n$。
7. 根據最小成本算法計算出 $T_n$與物體檢測 $j$ 關聯成功產生集合 $[x_i,j]$。
8. 更新 $M$ 為匹配成功的 (物體追蹤 $i$, 物體檢測 $j$) 集合。
9. 從 $U$ 中去除已經匹配成功的物體檢測 $j$。
10. 迴圈結束點。
11. 返回 $M,U$ 兩個集合。
* 核心思想就是 ==由小到大對消失時間相同的軌跡進行匹配==，這樣就首先保證了對==最近出現的物件賦予最大的優先權==。

### Deep Appearance Descriptor

* 我們的 CNN model 已經事先在大量 Person Re-Identification 訓練，其中包含超過 1,100,000 影像其中包含了 1,261 個行人。
* 我們採用一個 Wide Residual network，前面有兩個 CNN Layer，後面是六個 Residual Blocks。
* 在第十層時用 Dense Layer 計算維度為 128 的特徵映射。
* 最終層則用 L2 Normalization 映射特徵以未來作為餘弦計算所用。
* 參數共有 2,800,864，在 Nvidia GeForce GTX 1050 上 32 個 Bounding Box 大概要跑 30 毫秒。

## Experiment
* 實驗資料集採用的是 MOT16 的資料，檢測結果是拿 POI 那篇的而不是官網提供的，效果可以大大提升。
* 參數使用 $\lambda =0$, $A_{max} =30$ 進行測試序列的評估，而檢測結果是以信心水準 0.3 的閾值去設定，這點與 POI 那篇論文相同。
* 評估指標與 MOT16 官網相同：
* Multi-Object Tracking Accuracy（MOTA）：在 FP, FN 和身份切換方面的總體追蹤 Accuracy。
* Multi-Object Tracking Precision（MOTP）：根據真實答案和報告位置之間的邊界框重疊的總體追蹤 Precision。
* Mostly Tracked（MT）：大部分跟蹤到目標物件。在真實答案軌跡與預測軌跡重疊期間，其最少有 80％ 以上相同標籤的百分比。
* Mostly Lost（ML）：大部分失去目標物件。在真實答案軌跡與預測軌跡重疊期間，其最多只有 20％ 的百分比。
* Identity Switches（ID）：Track 標籤發生變化的次數。
* Fragmentation（FM）：Track 因為檢測缺失而中斷的次數。
* 從上表看出在 ID Switch 這邊從 1,423 降到 781，減少了大概 45% 的身份轉換。
* 在 FM 因為遮擋檢測器沒搜尋到的部分也因為本演算法而降低。
* 另外 MT 跟 ML 也都有往好的部分發展。
* 整體來說因為增加了外觀訊息的整合，即使有很長的遮擋也能成功地保持 ID，如下圖所示。
* 速度大概是 20 HZ 左右，有一半時間都在特徵生成上，但因為 GPU 是 1050 也許現在能夠更快速。
:::success
:fire: MOT16 中現在排名大概是全部資料集中 133 名的第 14 名，在 Private 的資料集中大概是 44 名中的第 14 名。
:::