###### tags: `2022Q2技術研討`, `tracking`

# Multiple Object Tracking (MOT)
## Introduction

物件追蹤包含兩個部分:
* <font color=#20639B>物件偵測</font> (Object detection)
* 物件偵測在眾多算法百家爭鳴下， 其準確度已經高到一個境界，舉凡 YOLO, SSD, Retinanet, CenterNet, …都是很好的選擇，它的功用就是要抓到 image 內的 bounding box 以及物件classification
* <font color=#20639B>追蹤器</font> (tracker)
* 追蹤器要做的事呢基本上就是==判斷前後 frame 抓到的 object 是否屬於同一個==，若是則 assign 相同 ID，若否則 assign 新的 ID。如下圖，frame t 檢測到的 3 個 objects (黃、藍、紅)，frame t+1 檢測到 4 個(灰色框)，而要如何把前後 frame 的框關連起來就是物件追蹤要做的事

## 追蹤器 (tracker)
### Central tracker

最直觀的做法就是直接把他 assign 給距離最近的框，而距離算法可以是歐式距離或 IoU
* 找出 bounding box 的中心點位，<font color=#20639B>算各中心的最短距離，再去 mapping</font> (OpenCV 就可以做了)


參數有兩個要設定
* max disappear frame
* 當一個 ID 沒被 assign 多少個 frame 後才被刪掉當做消失，這是用來避免短暫遮蔽或物件偵測不夠強導致 miss detect 的狀況
* max distance
* 一般物體不太會瞬間移動到太遠的位置，所以設定這個參數避免物體一出一進直接 transfer ID

:::spoiler 缺點
:::info
在單純的環境下 (物件交疊狀況少，方向單一) 這種作法應該就能表現不錯了，但這種算法擺到比較複雜，物件會交錯的環境時就能明顯發現物件交錯導致重複 counting (ID switch or re-ID)
:::

---

### SORT (Simple Online And Realtime Tracking), 2015

由兩種演算法所組成 Kalman filter + Hungarian algorithm

<font color=#20639B>Kalman filter (卡爾曼濾波器)</font>
* 對於移動的物體，可以根據過去框的軌跡 (.., t-1, t) ==預測 t+1 框的位置==，以克服快速移動造成的距離誤差
* 如果只有追蹤一個框 (人或車)，使用 Kalman filter 預測 t+1 框，找到 t+1 observed 最接近的框很簡單 (nearest distance). <font color=#EA0000>比較複雜是同時要做多個框，而且必須是一一對應</font>，整體的 error distance 需要最小，所以需要 Hungarian algorithm 的幫忙~
:::spoiler 公式
但基本上就是用物理的定律，從前幾幀去計算他的方向、加速度等，還會加入 noisy 去評估~
:::
<br>

<font color=#20639B>Hungarian algorithm (匈牙利演算法)</font>
* ==最佳化分配演算法==: 假設有 N 個人和 N 個任務，每個任務可以任意分配給不同的人，已知每個人完成每個任務要花費的代價不盡相同，那麼如何分配可以使得總體代價最小
* 以 object tracking 為例，Row 代表 observed bounding boxes; column 代表 predicted bounding boxes，其中的數值可以是歐式距離或是 IoT，得出的分配結果如下~

<font color=#20639B>統整 SORT 的流程</font>
1. (Frame t): object detection 得到所有 bboxes, 給每一個 bbox unique ID 並且計算每一個框的中心點
2. (Frame t): 利用 Kalman filter, predict 每一個 bbox 在 t+1 frame 的位置
3. (Frame t+1): object detection 得到新的 bboxes, 並計算 cost matrix using IoU or 歐式距離
4. (Frame t+1): 利用 Hungarian algorithm 將 predict bboxes 和新的 bboxes 進行匹配，assign ID to 新的 bboxes
5. (Frame t+1): 更新 Kalman 的 mean and variance 參數

:::spoiler 缺點
:::info
易有 ID switch 的狀況發生
* 當一個物體被遮擋後，Kalman filter 仍然會再前一幀預測他的下一個位置，但下一幀物體被遮擋不見，若此時多一個新物體出現，Hungarian algorithm 有可能會誤分配。且遮擋完畢原本的物體出現後，可能會被辨識為新的物體，就會造成計數不準確~
:::

---

### Deep SORT, 2017

由 SORT 演化而來，<font color=#EA0000>SORT 的主要問題是無法有效解決 ID switches 的問題</font>，這個缺點主要是在 tracking through occlusions (遮擋) 容易發生錯誤，==而 deep sort 再加入了外觀的訊息== (appearance information) 來匹配前後 frame 的 object 降低錯誤

Deep SORT 和 SORT <font color=#20639B>主要的關鍵差異就是 cost matrix</font>. SORT 的 cost matrix 一般是 IoU or 歐式距離。 Deep SORT 的 cost matrix 則是合併 motion & appearance metric 得到


* Motion Metric
* 使用馬氏距離 (Mahalanobis distance) 而非歐式距離計算 distance
* 馬氏距離的優點主要是<font color=#20639B>多考慮的其他維度的特徵</font> (又或者說其他特徵之間的關係)，計算距離時會先進行空間轉換~
* Appearance Metric
* 比對 kalman filter 預測的框和下個 frame object detection 得到的<font color=#20639B>框兩者間圖像的相似度</font>，而圖像的相似度是透過 CNN 將 image embedding 到一個 128d 的空間並限制長度為1，然後計算cosine distance

最後再將兩個 metric 透過一個權重加權起來，總結來說 deep sort 比 sort 大大減少了ID switch 的問題，但<font color=#EA0000>最大問題是速度頗慢</font>，因為跑了兩個類神經網路，而且偵測到的人越多就需要越多次 inference，==無法達到 real-time detection==

如果沒有遮擋問題的話，Sort 的表現已經相當不錯，且速度上可以達到 real-time

---

### JDE (Jointly Detector and Embedding model), 2019

為了達到更快速的 MOT 算法，JDE <font color=#20639B>將 object detect 和 appearance embedding 融合在同一個網路裡一起訓練</font>
* (a.) 就像 deep sort 將偵測到的圖片拿去跑 embedding network
* (c.) proposed method 一個網路直接算出 detection location, class, embedding feature

這種架構下網路需要 output 出三種東西: box classification, box regression, embedding feature，速度快也可以達到 real-time

---

### 近幾年較紅的演算法
* FairMOT (2020, encoder-decoder network)
* TransMOT (2021, Transformer)
* ByteTrack (2021, tracking BY associaTing Every detection box)
* 沒有用圖像相似度比對，跟 Sort 一樣只用 detect 後面全靠演算法合併框，所以速度非常快~

<br>

**MOT 評估指標 (很多種)**
* Re-ID (Re-Identification)
* 給定一張切好的行人圖像 (probe image, 即圖像大部分內容只包含這個人), 從一大堆切好的圖像 (gallery images) 中找到跟 probe image 中同一身份的人的圖像。這些圖像通常是由不同攝像頭拍攝的不連續幀
* MOTA (Multiple Object Tracking Accuracy)
* 最基本的指標，用於統計在跟踪中的誤差累積情況，數值越大越好
* 檢測缺漏數量 (某一個 id 應該要配對，但沒人跟他配對)
* 誤判的數量 (不同 id 卻分配再一起)
* 誤配的數量 (同一個 id 卻有分配不同 id，檢測遮擋)
* IDF1 (ID F1-score)
* IDP (precision) + IDR (recall) 的加權平均
* IDS (ID switches)
* ID轉變數，是指跟蹤軌跡中行人ID瞬間轉換的次數，通常能反應跟蹤的穩定性，數值越小越好

---

### ByteTrack (Tracking BY associaTing Every detection box), 2021

一般在做 tracking 會設一個門檻把 bbox 低的 confidence 篩掉 (當作是背景捨棄)，但 ByteTrack 會將他救回 (==能夠把低分數的框和背景分辨出來==，並且批配在一起)

流程 (大致與 SORT 相同):
1. (Frame t): 先分兩類，高分框 & 低分框
2. (Frame t): 利用 Kalman filter, predict 每一個 bbox 在 t+1 frame 的位置
3. (Frame t+1): <font color=#20639B>第一次匹配</font>，object detection 得到新的 bboxes, 並<font color=#EA0000>使用高分框</font>計算 cost matrix using IoU or 歐式距離
4. (Frame t+1): 利用 Hungarian algorithm 將 predict bboxes 和新的 bboxes 進行匹配，assign ID to 新的 bboxes
5. (Frame t+1): <font color=#20639B>第二次匹配</font>，剩餘的 bboxes, <font color=#EA0000>使用低分框</font>計算 cost matrix using IoU or 歐式距離
6. (Frame t+1): 利用 Hungarian algorithm 將 predict bboxes 和新的 bboxes 進行匹配，assign ID to 新的 bboxes
* 在分數較低的框框中，往往都是被遮擋的人或是模糊的人，這時候使用 Re-ID 反而偵測不好
7. (Frame t+1): 更新 Kalman 的 mean and variance 參數

* (a) 為原本偵測到的框框和分數
* (b) 為一般追蹤器的預測結果 (使用高分框)
* (c) 在使用低分框去追蹤~