重磅乾貨，第一時間送達
作者丨Harlek@知乎
來源丨https://zhuanlan.zhihu.com/p/97449724
導讀
本文是一篇多目標跟蹤方向的調研報告，從相關方向、核心步驟、評價指標和最新進展等維度出發，對MOT進行了全面的介紹，不僅適合作為入門科普，而且能夠幫助大家加深理解。
最近做了一些多目標跟蹤方向的調研，因此把調研的結果以圖片加文字的形式展現出來，希望能幫助到入門這一領域的同學。也歡迎大家和我討論關於這一領域的任何問題。
相關方向
這些是我所了解的多目標跟蹤（MOT）的一些相關方向。其中單目標跟蹤（VOT/SOT）、目標檢測（detection）、行人重識別（Re-ID）都是非常熱門的方向。而偏視頻的相關方向就比較冷門。而且今年五月DukeMTMC因為隱私問題不再提供MTMCT的數據了，MTMCT的研究也是舉步維艱。
核心步驟
MOT算法的通常工作流程：(1)給定視頻的原始幀；(2)運行對象檢測器以獲得對象的邊界框；(3)對於每個檢測到的物體，計算出不同的特徵，通常是視覺和運動特徵；(4)之後，相似度計算步驟計算兩個對象屬於同一目標的概率；(5)最後，關聯步驟為每個對象分配數字ID。
因此絕大多數MOT算法無外乎就這四個步驟：檢測 特徵提取、運動預測 相似度計算 數據關聯。
其中影響最大的部分在於檢測，檢測結果的好壞對於最後指標的影響是最大的。
但是，多目標追蹤的研究重點又在相似度計算和數據關聯這一塊。所以就有一個很大的問題：你設計出更好的關聯算法可能就提升了0.1個點，但別人用一些針對數據集的trick消除了一些漏檢可能就能漲好幾個點。所以研究更好的數據關聯的回報收益很低。因此多目標追蹤這一領域雖然工業界很有用，但學術界裡因為指標數據集的一些原因，入坑前一定要三思。
評價指標
關於評價指標：
第一個是傳統的標準，現在已經沒人用了，就不介紹了。
第二個是06年提出的CLEAR MOT。現在用的最多的就是MOTA。但是這個指標FN、FP的權重佔比很大，更多衡量的是檢測的質量，而不是跟蹤的效果。
第三個是16年提出的ID scores。因為都是基於匹配的指標，所以能更好的衡量數據關聯的好壞。
數據集
數據集用的最多的是MOTChallenge，專注於行人追蹤的。
第二個KITTI的是針對自動駕駛的數據集,有汽車也有行人，在MOT的論文裡用的很少。
還有一些其他比較老的數據集現在都不用了。
15年的都是採集的老的數據集的視頻做的修正。
16年的是全新的數據集，相比於15年的行人密度更高、難度更大。特別注意這個DPM檢測器，效果非常的差，全是漏檢和誤檢。
17年的視頻和16年一模一樣，只是提供了三個檢測器，相對來說更公平。也是現在論文的主流數據集。
19年的是針對特別擁擠情形的數據集，只有CVPR19比賽時才能提交。
這個是MOT16公開檢測器上的結果。可以看到從17年開始，MOTA就漲的很慢了。關注一下這個幀率有20Hz的算法MOTDT也是我後面要講的一個。
這個是MOT16私有檢測器上的結果。可以看到檢測器性能的好壞對於結果的影響非常重要。SOTA算法換了私有檢測器後性能直接漲了快20個點。
這個是MOT17公開檢測器上這幾年比較突出的算法。注意因為這個數據集用了三個檢測器，所以FP、FN這些指標也都幾乎是16數據集的三倍。
SORT和DeepSORT
關鍵算法
從這兩個工業界關注度最高的算法說起。
SORT作為一個粗略的框架，核心就是兩個算法：卡爾曼濾波和匈牙利匹配。
卡爾曼濾波分為兩個過程：預測和更新。預測過程：當一個小車經過移動後，且其初始定位和移動過程都是高斯分布時，則最終估計位置分布會更分散，即更不準確；更新過程：當一個小車經過傳感器觀測定位，且其初始定位和觀測都是高斯分布時，則觀測後的位置分布會更集中，即更準確。
匈牙利算法解決的是一個分配問題。SK-learn庫的linear_assignment___和scipy庫的linear_sum_assignment都實現了這一算法，只需要輸入cost_matrix即代價矩陣就能得到最優匹配。不過要注意的是這兩個庫函數雖然算法一樣,但給的輸出格式不同。具體算法步驟也很簡單，是一個複雜度
的算法。
DeepSORT的優化主要就是基於匈牙利算法裡的這個代價矩陣。它在IOU Match之前做了一次額外的級聯匹配，利用了外觀特徵和馬氏距離。
外觀特徵就是通過一個Re-ID的網絡提取的，而提取這個特徵的過程和NLP裡詞向量的嵌入過程（embedding）很像，所以後面有的論文也把這個步驟叫做嵌入（起源應該不是NLP，但我第一次接觸embedding是從NLP裡）。然後是因為歐氏距離忽略空間域分布的計算結果，所以增加裡馬氏距離作為運動信息的約束。
SORT
這個SORT的流程圖非常重要，可以看到整體可以拆分為兩個部分，分別是匹配過程和卡爾曼預測加更新過程，都用灰色框標出來了。一定要把整個流程弄明白。後面的多目標追蹤的大框架基本都由此而來。
關鍵步驟：軌跡卡爾曼濾波預測使用匈牙利算法將預測後的tracks和當前幀中的detecions進行匹配（IOU匹配） 卡爾曼濾波更新
對於沒有匹配上的軌跡，也不是馬上就刪掉了，有個T_lost的保存時間，但SORT裡把這個時間閾值設置的是1，也就是說對於沒匹配上的軌跡相當於直接刪了。
關於這點論文裡的原話是：
首先，恆定速度模型不能很好地預測真實的動力學，其次，我們主要關注的是幀到幀的跟蹤，其中對象的重新識別超出了本文的範圍。
這篇文章的機翻在《SORT》論文翻譯
DeepSORT
這是DeepSORT算法的流程圖，和SORT基本一樣，就多了級聯匹配（Matching Cascade）和新軌跡的確認（confirmed）。
這篇文章的機翻在《DeepSORT》論文翻譯
關鍵步驟：軌跡卡爾曼濾波預測使用匈牙利算法將預測後的tracks和當前幀中的detecions進行匹配（級聯匹配和IOU匹配） 卡爾曼濾波更新
級聯匹配是核心，就是紅色部分，DeepSORT的絕大多數創新點都在這裡面，具體過程看下一張圖。
關於為什麼新軌跡要連續三幀命中才確認？個人認為有這樣嚴格的條件和測試集有關係。因為測試集給的檢測輸入非常的差，誤檢有很多，因此軌跡的產生必須要更嚴格的條件。
級聯匹配流程圖裡上半部分就是特徵提取和相似度估計，也就是算這個分配問題的代價函數。主要由兩部分組成：代表運動模型的馬氏距離和代表外觀模型的Re-ID特徵。
級聯匹配流程圖裡下半部分數據關聯作為流程的主體。為什麼叫級聯匹配，主要是它的匹配過程是一個循環。從missing age=0的軌跡（即每一幀都匹配上，沒有丟失過的）到missing age=30的軌跡（即丟失軌跡的最大時間30幀）挨個的和檢測結果進行匹配。也就是說，對於沒有丟失過的軌跡賦予優先匹配的權利，而丟失的最久的軌跡最後匹配。
論文關於參數λ（運動模型的代價佔比）的取值是這麼說的：
在我們的實驗中，我們發現當相機運動明顯時，將λ= 0設置是一個合理的選擇。
因為相機抖動明顯，卡爾曼預測所基於的勻速運動模型並不work，所以馬氏距離其實並沒有什麼作用。但注意也不是完全沒用了，主要是通過閾值矩陣（Gate Matrix）對代價矩陣（Cost Matrix）做了一次閾值限制。
關於DeepSORT算法的詳細代碼解讀我比較推薦：目標跟蹤初探（DeepSORT）
但關於卡爾曼濾波的公式講的不是很詳細，具體推導可以看看 Kalman Filter 卡爾曼濾波
改進策略
看到這個DeepSORT的流程圖不知道大家可以想到什麼優化的地方？其實有幾個點是很容易想到的。
第一點，把Re-ID網絡和檢測網絡融合，做一個精度和速度的trade off；
第二點，對於軌跡段來說，時間越長的軌跡是不是更應該得到更多的信任，不僅僅只是級聯匹配的優先級，由此可以引入軌跡評分的機制；
第三點，從直覺上來說，檢測和追蹤是兩個相輔相成的問題，良好的追蹤可以彌補檢測的漏檢，良好的檢測可以防止追蹤的軌道飄逸，用預測來彌補漏檢這個問題在DeepSORT裡也並沒有考慮；
第四點，DeepSORT裡給馬氏距離也就是運動模型設置的係數為0，也就是說在相機運動的情況下線性速度模型並不work，所以是不是可以找到更好的運動模型。
最新進展
這是最近比較新的一些方法。
工業界青睞的算法在學術界其實並不重視，一方面是因為開源的原因，另一方面可以看到頂會的算法都不是注重速度的，通常用了很複雜的模塊和trick來提升精度。
而且這些trick不是一般意義的trick了，是針對這個數據集的或者說針對糟糕檢測器的一些trick， 對於實際應用幾乎沒有幫助。
第一篇論文是基於DeepSORT改進的，它的創新點在於引入了軌跡評分機制，時間越久的軌跡可信度就越高，基於這個評分就可以把軌跡產生的預測框和檢測框放一起做一個NMS，相當於是用預測彌補了漏檢。
第二篇論文是今年9月份發在arxiv上的一篇論文，它的工作是把檢測網絡和嵌入網絡結合起來，追求的是速度和精度的trade off。
MOTDT
這是剛才列舉的第一篇論文（MOTDT）的流程圖，大概和DeepSORT差不多。這個圖畫的比較簡單，其實在NMS之前有個基於SqueezeNet的區域選擇網絡R-FCN和軌跡評分的機制。這兩個東西的目的就是為了產生一個統一檢測框和預測框的標準置信度，作為NMS的輸入。
這篇文章的翻譯在《Real-Time Multiple People Tracking With Deeply Learned Candidate Selection And Person Re-ID》論文翻譯
JDE
這是剛才第二篇論文（JDE）裡的結構圖。這個方法是基於YOLOv3和MOTDT做的。它網絡前面都和YOLOv3一樣的，主要就是在特徵圖裡多提取了一個嵌入（embedding）向量，採取的是類似於交叉熵的triplet loss。因為是多任務學習，這篇論文還用了一篇18年的論文提出來的自動學習損失權重方案：通過學習一組輔助參數自動地對非均勻損失進行加權。最後的結果是精度上差不太多，FPS高了很多。
這篇文章的翻譯在 《Towards Real-Time Multi-Object Tracking》論文翻譯
未來展望
最後用多目標追蹤未來的一些思考作為結尾，這句話是最近的一篇關於多目標追蹤的綜述裡的。
它在最後提出對未來的方向裡有這樣一句話，用深度學習來指導關聯問題。其實現在基於檢測的多目標追蹤都是檢測模塊用深度學習，Re-ID模塊用深度學習，而最核心的數據關聯模塊要用深度學習來解決是很困難的。現在有一些嘗試是用RNN，但速度慢、效果不好，需要走的路都還很長。
我個人覺得短期內要解決實際問題，還是從Re-ID的方面下手思考怎樣提取更有效的特徵會更靠譜，用深度學習的方法來處理數據關聯不是短時間能解決的。
參考文獻：
[1] Alex Bewley, Zongyuan Ge, Lionel Ott, Fabio Ramos, and Ben Upcroft. Simple online and realtime tracking. In2016 IEEE International Conference on Image Processing (ICIP), pages 3464–3468. IEEE, 2016.
[2] Nicolai Wojke, Alex Bewley, and Dietrich Paulus. Simple online and realtime tracking with a deep associationmetric. In2017 IEEE International Conference on Image Processing (ICIP), pages 3645–3649. IEEE, 2017.
[3] Chen Long, Ai Haizhou, Zhuang Zijie, and Shang Chong. Real-time multiple people tracking with deeplylearned candidate selection and person re-identification. InICME, 2018.
[4] Zhongdao Wang, Liang Zheng, Yixuan Liu, Shengjin Wang. Towards Real-Time Multi-Object Tracking. arXiv preprint arXiv:1909.12605
[5] Gioele Ciaparrone, Francisco Luque Sánchez, Siham Tabik, Luigi Troiano, Roberto Tagliaferri, Francisco Herrera. Deep Learning in Video Multi-Object Tracking: A Survey. arXiv preprint arXiv:1907.12740