Multiple Object Tracking (MOT)

###### tags: `2022Q2技術研討`, `tracking` # Multiple Object Tracking (MOT) ## Introduction 物件追蹤包含兩個部分: * 物件偵測 (Object detection) * 物件偵測在眾多算法百家爭鳴下，其準確度已經高到一個境界，舉凡 YOLO, SSD, Retinanet, CenterNet, …都是很好的選擇，它的功用就是要抓到 image 內的 bounding box 以及物件classification * 追蹤器 (tracker) * 追蹤器要做的事呢基本上就是==判斷前後 frame 抓到的 object 是否屬於同一個==，若是則 assign 相同 ID，若否則 assign 新的 ID。如下圖，frame t 檢測到的 3 個 objects (黃、藍、紅)，frame t+1 檢測到 4 個(灰色框)，而要如何把前後 frame 的框關連起來就是物件追蹤要做的事 ![](https://i.imgur.com/sN8F43X.png) ## 追蹤器 (tracker) ### Central tracker 最直觀的做法就是直接把他 assign 給距離最近的框，而距離算法可以是歐式距離或 IoU * 找出 bounding box 的中心點位，算各中心的最短距離，再去 mapping (OpenCV 就可以做了) ![](https://i.imgur.com/kUFFhDs.png) 參數有兩個要設定 * 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 Kalman filter (卡爾曼濾波器) * 對於移動的物體，可以根據過去框的軌跡 (.., t-1, t) ==預測 t+1 框的位置==，以克服快速移動造成的距離誤差 * 如果只有追蹤一個框 (人或車)，使用 Kalman filter 預測 t+1 框，找到 t+1 observed 最接近的框很簡單 (nearest distance). 比較複雜是同時要做多個框，而且必須是一一對應，整體的 error distance 需要最小，所以需要 Hungarian algorithm 的幫忙~ :::spoiler 公式 ![](https://i.imgur.com/DekaGem.jpg) 但基本上就是用物理的定律，從前幾幀去計算他的方向、加速度等，還會加入 noisy 去評估~ ::: Hungarian algorithm (匈牙利演算法) * ==最佳化分配演算法==: 假設有 N 個人和 N 個任務，每個任務可以任意分配給不同的人，已知每個人完成每個任務要花費的代價不盡相同，那麼如何分配可以使得總體代價最小 * 以 object tracking 為例，Row 代表 observed bounding boxes; column 代表 predicted bounding boxes，其中的數值可以是歐式距離或是 IoT，得出的分配結果如下~ ![](https://i.imgur.com/327tjxg.png =480x200) 統整 SORT 的流程 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 演化而來，SORT 的主要問題是無法有效解決 ID switches 的問題，這個缺點主要是在 tracking through occlusions (遮擋) 容易發生錯誤，==而 deep sort 再加入了外觀的訊息== (appearance information) 來匹配前後 frame 的 object 降低錯誤 Deep SORT 和 SORT 主要的關鍵差異就是 cost matrix. SORT 的 cost matrix 一般是 IoU or 歐式距離。 Deep SORT 的 cost matrix 則是合併 motion & appearance metric 得到 ![](https://i.imgur.com/vj8QkE0.png) * Motion Metric * 使用馬氏距離 (Mahalanobis distance) 而非歐式距離計算 distance * 馬氏距離的優點主要是多考慮的其他維度的特徵 (又或者說其他特徵之間的關係)，計算距離時會先進行空間轉換~ * Appearance Metric * 比對 kalman filter 預測的框和下個 frame object detection 得到的框兩者間圖像的相似度，而圖像的相似度是透過 CNN 將 image embedding 到一個 128d 的空間並限制長度為1，然後計算cosine distance 最後再將兩個 metric 透過一個權重加權起來，總結來說 deep sort 比 sort 大大減少了ID switch 的問題，但最大問題是速度頗慢，因為跑了兩個類神經網路，而且偵測到的人越多就需要越多次 inference，==無法達到 real-time detection== 如果沒有遮擋問題的話，Sort 的表現已經相當不錯，且速度上可以達到 real-time --- ### JDE (Jointly Detector and Embedding model), 2019 為了達到更快速的 MOT 算法，JDE 將 object detect 和 appearance embedding 融合在同一個網路裡一起訓練 ![](https://i.imgur.com/kXq5k4g.png =640x280) * (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 後面全靠演算法合併框，所以速度非常快~ ![](https://i.imgur.com/F72mZuP.png =600x400) ![](https://i.imgur.com/GmTTpy3.png =400x150) **MOT 評估指標 (很多種)** * Re-ID (Re-Identification) * 給定一張切好的行人圖像 (probe image, 即圖像大部分內容只包含這個人), 從一大堆切好的圖像 (gallery images) 中找到跟 probe image 中同一身份的人的圖像。這些圖像通常是由不同攝像頭拍攝的不連續幀 * MOTA (Multiple Object Tracking Accuracy) * 最基本的指標，用於統計在跟踪中的誤差累積情況，數值越大越好 * 檢測缺漏數量 (某一個 id 應該要配對，但沒人跟他配對) * 誤判的數量 (不同 id 卻分配再一起) * 誤配的數量 (同一個 id 卻有分配不同 id，檢測遮擋) ![](https://i.imgur.com/lDz7N44.png =300x80) * 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): 第一次匹配，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): 第二次匹配，剩餘的 bboxes, 使用低分框計算 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 參數 ![](https://i.imgur.com/qDpLYSi.jpg =600x500) * (a) 為原本偵測到的框框和分數 * (b) 為一般追蹤器的預測結果 (使用高分框) * (c) 在使用低分框去追蹤~