最近有緣碰到了人流計算的題目，便著手看了一些有關物件追蹤的東西。此篇簡單的介紹基本的追蹤概念及方法到經典的 deep sort 以及接近 real-time tracking的 Jointly Detector and Embedding model(JDE)。
What is Multiple Object Tracking?
物件追蹤包含兩個部分: 物件偵測(Object detection)以及追蹤器(tracker)。
物件偵測在眾多算法百家爭鳴下， 其準確度已經高到一個境界，舉凡YOLO, SSD, Retinanet, CenterNet, …都是很好的選擇，它的功用就是要抓到image 內哪裡(bounding box regression)有哪種物件(classification)。
而追蹤器要做的事呢基本上就是判斷前後frame 抓到的object 是否屬於同一個，若是則assign 相同ID，而沒有assign到的則給予新的ID。如下圖，frame t 檢測到的 3 個objects(黃、藍、紅)，frame t+1 檢測到4個(灰色框)，而要如何把前後frame的框關連起來就是物件追蹤要做的事!
Central tracker:
要做到上述的事，最直觀就是直接把他assign給距離最近的框，而距離算法可以是歐式距離或 IoU。
在單純的環境下(物件交疊狀況少，方向單一) 這種作法應該就能表現不錯了(在物件偵測的準確率夠高的條件下)。以下我參考 pyimagesearch 的central tracker 並且搭配 YOLOv3 來做車流計算:
其中這種算法有兩個條件要設定: 第一是max disappear frame，也就是當一個ID沒被 assign 多少個frame後才被刪掉當做消失，這是用來避免短暫遮蔽或物件偵測不夠強導致miss detect 的狀況；第二就是max distance，因為一般物體不太會瞬間移動到太遠的位置，所以設定這個參數避免物體一出一進直接 transfer ID。
但這種算法擺到比較複雜，物件會交錯的環境時就能明顯發現物件交錯導致ID switch or re-ID 導致重複 counting。以下是把central tracker 套用到 Oxford 的 Town Centre Dataset，可以看到數到後面整個炸裂 (當然YOLOv3 也表現的不大穩定)。
Deep Sort :
deep sort 是由 sort(Simple Online And Realtime Tracking) 演化來的，sort 由 Kalman Filter, Hungarian Algorithm 組成，而deep sort 再加入了外觀的訊息來批配前後frame的object。Deep sort 是2017年發表的，到現在仍是一套經典的算法。(paper: https://arxiv.org/abs/1703.07402)
Kalman Filter 和匈牙利演算法比較數學一點，我也了解不深XD，在這篇有概述其方法，更細節的部分可以看youtube上的教學課程。
總之呢 ~ kalman filter 大概就是個可以對狀態變化中的物體進行下個狀態的預測，並且再根據下個狀態的觀測值update 模型(mean & covariance matrix) 來做下下次的預測。白話的說就是它可以預測物體下個 frame 的位置 !
Hungarian Algorithm 則是一個任務分配的組合最佳化演算法，大概是解決像以下維基百科的例子:
套用到追蹤的問題時，人和工作的匹配就變成前個frame 和下個frame 的物件匹配。cost matrix 在 sort 裡是直接使用IoU來得到，在deep sort裡則是合併 motion & appearance metric 來得到cost，分別為下:
motion metric:
使用馬氏距離(Mahalanobis distance)來計算 distance between predicted Kalman states and newly arrived measurements
表示第j個detection 和第 i 的 tracker 的motion distance.。
其中dj 是第j個detection bounding box，yi 是第 i 個軌跡由kalman filter 預測的位置(目標位置的均值資訊)，Si 是 kalman filter 當下 measurement space 的convariance matrix(目標位置的不確定性).
appearance metric:
當物體移動的不確定性較高時，馬氏距離會有大量的不能匹配(kalman filter 預測的不確定性增大，狀態間關連性變小，covariance matrix反矩陣變大)，故而使得motion metric 失效。因此導入appearance metric，顧名思義就是比對kalman filter預測的框和下個frame object detection得到的框兩者間圖像的相似度，而圖像的相似度是透過 CNN 將 image embedding 到一個 128d 的空間並限制長度為1，然後計算cosine distance。
該篇paper CNN 網路架構如下:
最後再將兩個metric 透過一個權重加權起來:
兩個metric 各有長項，互相搭配，在不同環境的task 上調整搭配的權重
the Mahalanobis distance provides information about possible object locations based on motion that are particularly useful for short-term predictions. On the other hand, the cosine distance considers appearance information that are particularly useful to recover identities after longterm occlusions, when motion is less discriminative.
最後，在聯集匹配後未批配到的track 和unconfirmed 且time_since_update 為 1 的track 進行 IoU association。 This helps to to account for sudden appearance changes, e.g., due to partial occlusion with static scene geometry, and to increase robustness against erroneous initialization.
總結來說 deep sort 比 sort 大大減少了ID switch的問題(據paper上的說法是少了45%)。
看起來是有比上面的central tracker改善，但還是不大理想，且速度頗慢(on 1080ti)，畢竟跑了兩個類神經網路，而且偵測到的人越多就需要越多次推論，要達到real-time detection還差了一大步。
Jointly Detector and Embedding model(JDE)
為了達到更快速的跟蹤算法，JDE 將object detect 和 appearance embedding 融合在同一個網路裡一起訓練，這簡直就和one-stage的物件偵測概念雷同!
上圖的(a)就像deep sort 將偵測到的圖片拿去跑embedding network，而(b)是類似 Faster RCNN 共享低階特徵萃取的network，(c) proposed method 一個網路直接算出detection location, class, embedding feature
該篇說能達到18~24FPS 並且準確率在MOT-16挑戰中達到64.4% MOTA ,趨近於目前state-of-art tracker。
這種架構下一個網路需要 output出3件事: box classification, box regression, embedding feature。採用的架構是 Darknet-53 + FPN 也就是跟YOLOv3 是一樣的XD 只是最後predict 各channel代表的意義不同而已，如下圖
prediction head 的channel數為 6A+D ，其中A為anchor 數，D為 embedding dimension。
由於目標是偵測行人，所以anchor的比例設置為1:3，total 12 個anchor，各scale 預測4個anchor (A=4)
而 loss 的部分，box classification 用的是cross-entropy，regression用 smooth-L1 loss，embedding則是使用 triplet loss；最後將三個loss 加權起來。這邊引入了一個automatic loss balancing 的技術(還沒看內容，總之三個loss的權重也可以透過網路來學習)
作者在他 github 上有提供行人的pre-train model 直接拿來套用:
可以看到不只ID-switch的狀況較好，數量也較正確外，檢測框也比YOLOv3 (coco pretrain weight) 穩定，而且在1080ti上 fps 達到 16，可以說是real-time detection了。
上述的追蹤方法，原作都有開放資源在 github 上，想玩的人可以自己去找來跑跑看或用一些進一步打包起來的wrapper 如 eyewitness 方便使用~
Reference
Simple object tracking with OpenCV
Simple Online and Realtime Tracking with a Deep Association Metric
