流程
DeepSort流程如下：
- 檢測器得到 t 時間的 detection bbox，更新track set
- 經過卡爾曼濾波器預測 t + 1 時的prediction bbox
- 檢測器得到 t + 1的detection
- 使用匈牙利算法配對 t + 1的detection和prediction的bbox，更新track set
如此重複2~5步驟來進行目標追蹤，並把資訊都存放在track set中。可以看出它其實是分成三個問題，而DeepSort主要的貢獻在於2、3。
- 目標檢測器
- 追蹤
- 匹配
目標檢測器
DeepSort論文使用Faster RCNN + skip pooling + multi-region來當作它的檢測器，不過DeepSort的主要核心在於3，因此實務上可以搭配任意效果好的目標檢測器。詳情可以參考這篇論文：
POI: Multiple Object Tracking with High Performance Detection and Appearance Feature
追蹤
該論文使用卡爾曼濾波器 (Kalman Filter)進行追蹤，原理與在Sort中相同，DeepSort定義了8維度的state來表示bounding box (bbox)和其速度：
u, v代表bbox的x,y座標，r代表長寬比，h代表高度。剩下4個有點上標的是前述4個state分別的速度。這邊使用線性的卡漫濾波器，也就是假設物體是等速運動的。
Track更新規則：
- 每個track k都會計算連續匹配失敗的次數Age，若Age大於預先設定好的max Age，視為該目標已經離開，將k從track set刪除。如果被配對到，Age就歸0。
- 對於每個新目標，也就是沒有被配對到的detection，會初始化一個track，它在一開始的3個幀可以匹配，但是只能先得到暫時的分類，如果這3幀都成功配對到，該track就可以正式得到一個id，反之，如果前3幀其中1幀配對失敗，該目標就會被視為誤判，然後被刪除。
匹配
DeepSort論文的核心，匹配步驟如下，它使用了匈牙利演算法 (Hungarian Algorithm)來進行配對，不過不是所有detection和track一起配對，而是考慮到Age，分層配對，來解決遮擋對配對造成的問題。
試想當一個目標長時間被遮擋，卡爾曼濾波器的結果會非常不穩定，造成detection和track的距離很大。如果當兩個track競爭同一個detection時，馬氏距離會讓不確定性越大(分母越大)的track被配對到，這顯然會造成追蹤效果不好。為了解決這個問題，越近期有被配對到的track，應該更優先進行配對。反之，遮擋很久，很久沒被配對到的track，即便跟detection距離很小，配對的priority也應該降低。
針對不同Age進行分層匹配，每一層都先計算cost矩陣C與gate矩陣B，然後使用匈牙利演算法用來配對，剩下沒被配對到的detections會進入到下一層，跟Age更大的track配對。
匈牙利算法會依據代價矩陣C進行配對，這個C的計算就比較複雜了，我們用距離(相異程度)來表示代價，當detection和track的距離很大時，代表把他們配對在一起的代價很高，不應該被配對到。
相比於Sort，使用bbox的IOU作為距離來計算代價矩陣。DeepSort不僅使用了motion的距離，還加入了appearance的距離，來幫助配對，這也是DeepSort的主要賣點之一。那麼對於第i個track與第j個detection的代價(距離)，Ci,j的公式如下，是motion距離 d(1)和appearance距離d(2)的加權和：
對於第i個track與第j個detection的motion距離，使用馬氏距離去計算，馬氏距離的好處是有將狀態不確定性加入考量：
其中dj表示第j個detection的bbox，yi表示第i個track的bbox，bbox的狀態也就是前面說的卡爾曼濾波器使用的前4個狀態，x,y座標、長寬比、高度：
並且我們可以給它一個馬氏threshold，排除掉95%信賴區間外的track，因為它的不確定性太高了。
接下來來計算appearance距離，對於每個detection的bbox dj，我們都計算appearance descriptor rj，其實就是第j個detection的外觀特徵，由CNN進行特徵萃，得到維度為128且標準化過的外觀特徵向量，這個CNN是off-line事前訓練好的，推論的速度上還ok，可以用在real-time的目標追蹤。
同理也可以拿來計算第k個track的appearance descriptor rk，這邊沒有每個track都計算，而是給定Lk=100，只算最後100個track，我們把這個集合叫做Ri。因此，對於第k個track與第j個detection的appearance距離，以cosine similarity計算得到的公式如下：
同motion距離，我們也可以給appearance距離一個threshold，如果小於這個threshold，就可以接受用來配對。這個threshold是在off-line訓練CNN時，根據training data決定的。
代價矩陣Ci,j為motion、appearance距離的加權和，必須同時通過上述兩個threshold才能用來匹配，2個threshold的交集即為匹配步驟中的gate matrix B：
以上就是DeepSort的核心概念。
效能
以下數據中的DeepSort，是以lambda=0 (也就是只用appearance特徵，未使用motion特徵)，與max Age=30 frames進行測試。
雖然說以MOTA、MOTP來看，Sort和DeepSort表現差不多，然後POI顯著稱霸Online的方法。不知道是不是因為沒有用motion特徵，所以FP蠻高的。
DeepSort因為考量了Age進行分層匹配，以及加入了appearance特徵，因此相較Sort，大大改善了遮擋以及ID Switch的問題，所以在ID Switch、ML (mostly lost)上可以看到DeepSort改善非常顯著。
不過沒有遮擋問題的話，Sort的表現還是很好的，且速度上仍是最快。如果DeepSort有用上motion特徵的話，想必FPS又會拉更低。
