視頻目標追蹤算法是機器視覺中一項很實用重要的算法，視頻目標追蹤算法應用場景很廣，比如智能監控、機器人視覺系統、虛擬實境（人體跟蹤）、醫學診斷（細胞狀態跟蹤）等。本文由滴普科技2048團隊AI產品部算法工程師朱曉麗介紹基於機器視覺的典型多目標追蹤算法應用實踐。
一、追蹤算法概述
目標追蹤算法分為單目標追蹤SOT（single-object track）和多目標追蹤MOT(multi-object track)。在單目標跟蹤中，使用給定的目標定位，在後續視頻幀中對給定的目標定位的物體進行位置預測。而多目標跟蹤算法，大部分都是不考慮目標定位，目標可自行進出。對目前小組項目而言只需用到MOT，所以本文提到的追蹤默認為MOT。【1】【2】
MOT的一般結構和分類：a. TBD(Tracking-by-Detection)與DFT（Detection-Free Tracking）也即基於檢測的多目標跟蹤與基於目標外形的先驗知識無需檢測器的多目標跟蹤。TBD是目前學界業界研究的主流。b. 在線跟蹤(online)與離線跟蹤(offline)。在Online跟蹤中，只能使用當前幀及之前幀的信息來進行當前幀的跟蹤。而在Offline跟蹤中則沒有了這個限制，對每一幀的預測，都可以使用整個視頻的信息，這樣更容易獲得一個全局最優解。兩種方式各有優劣，一般視應用場合而定，Offline算法的效果一般會優於Online算法。而介於這兩者之間，還有一種稱之為Near-Online的跟蹤方式，即可以部分利用未來幀的信息。關於Online，還有一點需要補充，Online跟蹤是不允許修改以往的跟蹤結果的，這一點也不難理解，因為一旦修改，算法自然就不再符合Online跟蹤不能利用未來幀的要求了，變成了Near-Online或者Offline。需要特別注意，online不等於real-time，real-time一定是online的，但絕大部分online算法還太慢，不足以支持real-time environment. 尤其是應用了深度學習的算法，往往都計算密集。MOT相關的數據來源：行人追蹤經典數據來源MOT challengeKITTYMOT常用評價標準：
表1. classical metrics
另外兩種評價方式CLEAR MOT metrics與ID scores，它們是通過IOU來進行ground truth和predictions的對應。這裡不做詳細介紹。
MOT的難點：MOT有兩個難點：1）遮擋，這也是ID交換和軌跡分段的主要原因。2）兩個軌跡非常靠近，ID容易匹配不準，出現錯位或丟失。目前MOT經典的算法：MOT最常用的類別是Tracking-by-Detection與online，對應的算法步驟：a.檢測b.特徵提取、軌跡預測c.計算相似度d.數據匹配。優化的方向圍繞著這四個步驟，如：運用private dataset，挑選合適檢測模型，提升檢測精度；特徵提取不局限於一般的CNN，還有Siamese network等網絡；特徵間的相似度，不再是簡單的distance metric，也開始運用CNN、RNN、LSTM等；數據關聯匹配除了傳統經典的Hungarian algorithm，也可以當作圖優化的問題。目前比較常用的效果較好的有以下幾種：
1）sort(simple online and realtime tracking)
2）deep sort(deep simple online and realtime tracking)
3）fairmot(a simple baseline for multi-object tracking)
另外最新的追蹤算法中，有嘗試利用圖神經網絡完成追蹤，屬於Tracking-by-Detection與offline的類別，4）graphnn multi-object trachking。不考慮時間問題，效果精度還不錯，後面簡寫為graphnn-mot
四種算法詳細的介紹見「二」節。
二、經典的追蹤算法介紹：
sort是deep sort的簡化版，著重介紹deep sort。1)原文源碼deep sortSimple Online and Realtime Tracking with a Deep Association Metric.https://arxiv.org/pdf/1703.07402.pdfhttps://github.com/KeyForce/Cascade-RCNN-Tracking簡單流程
圖1. Deep sort算法的簡單流程圖
原理：算法模塊，根據目前MOT常用的算法步驟：a.檢測b.特徵提取、軌跡預測c.計算相似度d.數據匹配，deep sort算法就這四個步驟，按序簡介涉及到的核心知識點五個：detection、reID model、kalman filter、iou與餘弦距離、hungarian algorithm。Detection:常用的檢測網絡，如faster rcnn、yolov4、ssd等，可根據實際項目對精度或時間的要求挑選。本文復現時，上面的幾種網絡都有嘗試，原始碼使用了商湯的mmdetection框架下的cascade-rcnn，但項目考慮時間和精度，最終使用了yolov4[3]作為檢測來源。reID model:原始碼使用了多重粒度網絡（Mutiple Granularity Network）,是以resnet50作為backbone，以softmax_2048分支作為id特徵。考慮到2048維特徵過大，數據關聯時，時間會長，本文項目採用了mobileNetv2[4]作為主幹網絡，id特徵維度下降到751。kalman Filter:卡爾曼濾波，預測confirmed id在下一幀的中心點位置以及box的size。iou與餘弦距離：用於計算數據匹配的代價矩陣。1-iou的值作為box間的距離值，餘弦距離函數值作為id特徵值間的距離。hungarian algorithm:匈牙利匹配算法用於目標預測與目標檢測的關聯匹配，確定目標的軌跡。sort比起deep sort少了reID model與餘弦距離，所以ID切換的過於頻繁，精度要低很多。速度幾乎只取決於detection模型的預測速度。如果對速度要求很高的，可以考慮用sort。具體的細節不再敘述，參考deep sort。fairmot原文源碼FairMOT: On the Fairness of Detection and Re-Identification in Multiple Object Tracking.https://arxiv.org/pdf/2004.01888.pdfhttps://github.com/ifzhang/FairMOT簡單流程：
圖2. Fairmot算法的簡單流程圖
原理：Fairmot算法重點突破：a. 比起之前兩步（先檢測後re-id）的追蹤算法，fairmot完成檢測與re-id共享網絡參數，減少算法推理時間，速度大幅度提升。b. 比起之前單步的追蹤算法JDE，存在的一些不足，如：一個物體可能被多個anchor負責並進行檢測，或實際物體的中心可能與負責對該物體進行檢測的anchor中心有偏差，都會導致id頻繁變換。fairmot針對這些不足，不用anchor-based的檢測方式，以anchor-free目標檢測範式代替。涉及到的核心知識點：一個有效簡潔的網絡結構DLA34、kalman filter、iou與餘弦距離、hungarian algorithm。下面詳細介紹DLA34網絡，至於kalman，distance metrixes， hungarian algorithm同deep sort的內容一致，這裡不多做解釋。fairmot旨在將檢測與re-id揉在一個網絡結構裡，且需要是anchor-free的目標檢測方式，所以DLA34網絡結構必需要預估目標中心點的位置和對應目標的features。DLA34的backbone是resnet34[5]，resnet網絡結構是裡程碑似的出現，比起一般的plain network， resnet直接使用stride=2的down sample並且用global average pool層替換全連接層，保持了網絡的複雜度，並有效解決了深度網絡的退化問題。DLA34[6]是對resnet34加強，除了down sample，還有up sample，有點類似FPN[7]的網絡結構，跨層添加features，使得多層融合，跨層stride=4。detection heads:heatmap head、box offset and size head、Re-ID branch；heatmap head：用於預估目標中心位置，使用了與focal loss類似的損失函數，詳情推導見源文。Box offset head：目的是使得預估的目標位置更精準，輔助目標中心位置的預估。Box size head：對每個預估了的目標中心，預估其對應的box的長和寬。offset與size兩個頭加入在一個l1 loss函數裡面。Re-ID branch：一個分類任務，旨在對每個預估出的目標中心產生64維的features，通過features用於後續計算前後幀的目標的相似度。使用了通用的softmax損失函數。簡單的網絡結構圖如下：
圖3. Fairmot網絡結構圖
graphnn-mot原文源碼Learning a Neural Solver for Multiple Object Tracking.https://arxiv.org/pdf/1912.07515.pdfhttps://github.com/selflein/GraphNN-Multi-Object-Tracking簡單流程：
圖4. Graphnn-mot算法的簡單流程
原理：該論文是基於圖神經網絡[8]的離線MOT，利用圖結構同時執行特徵提取和數據關聯匹配，提出了時間感知信息傳遞網絡對節點和連接邊信息的更新。涉及到的核心知識點：圖構造、特徵編碼、信息傳遞、軌跡預測。圖構造：對需檢測的所有圖片（圖片之間要有時間關聯，最好是視頻），進行目標檢測。構建圖，其中節點對應檢測目標，邊對應檢測目標之間的連接。對圖中的每條邊引入了一個二元變量，如果某些邊連接了屬於同一條跟蹤軌跡且在同一條跟蹤軌跡上是時間連續的節點，那麼其標籤為1，否則為0。一個節點不會屬於超過一個跟蹤軌跡。論文提出直接學習預測圖中的哪條邊被激活，即邊上的二元變量的最終值，為此將這個任務視為邊上的二分類任務，標籤就是二元變量值y。特徵編碼：在邊界框圖像上應用一個卷積神經網絡，初始化節點的外觀特徵嵌入。對於每一條邊也就是不同幀的每一對檢測，我們計算一個具有編碼了他們的邊界框之間的相對大小，位置以及時間差的特徵的向量。然後將其輸入到一個多層感知器中得到邊的幾何嵌入。信息傳遞：我們在整個圖上執行了一系列的信息傳遞步驟。對於每一輪的信息傳遞，節點會與他們的連接邊分享外觀信息，邊會與他們的伴隨節點分享幾何信息。最後，能夠獲得節點和邊的更新嵌入信息，其包含了依賴於整個圖結構的高階信息。軌跡預測：根據最後的所有邊嵌入預測的連續的二元結果，獲得最終的跟蹤軌跡。三、復現環境和數據集環境配置：ubuntu 20.04.4LTS 單卡GTX1060 CUDA Version 10.1.python=3.8.3 opencv-python=4.3.0.36 pytorch=1.4 torchvision cudatoolkit=10.1.243數據集：public dataset: MOT2017-MOT2020 crowdhuman 用於detection模型訓練和測試CUHK03 Market1501 DukeMTMC-reID MSMT17用於reID模型訓練四、實際測試時間和精度對比
表2. 追蹤算法實際測試的時間和精度
五、實際算法測試分析
如第四小節所示，無論時間還是精度，farimot更有優勢。影響精度的原因主要是兩個：
檢測目標聚集，被遮擋，ID switches頻率太高。三種追蹤算法都有出現這類情況，嚴重程度graphnn mot >deep sort>fairmot，可見下面擁擠場景例圖：
組圖1：擁擠場景中的graphnn mot追蹤算法
組圖2：擁擠場景中的deep sort追蹤算法
組圖3：擁擠場景中的farimot追蹤算法
如上圖紅上衣人為例，graphnn mot對應的id號為：無->15->20，id號連續變換；deep sort對應的id號：32->32->48，id號部分變換，只在最聚集的地方變換了id號；fairmot對應的id號：30->30->30，id號一直很穩定。
2.目標檢測精度不高，漏檢與誤檢。主要是graphnn mot算法有明顯漏檢，可見下面例圖：
組圖4：graphnn追蹤算法目標檢測漏檢示例圖
對於目前最常使用的追蹤算法，都是tracking-by detection，所以目標檢測的精度直接影響追蹤的精度。
六、總結
1. 目前精度時間最合適的追蹤算法：
目前來說對跟蹤效果影響最大的是目標檢測的性能，相對於公開的檢測，私有檢測提升幅度巨大。
對於跟蹤模塊，目前來說更好的解決方案，比如使用MOTDT，此算法在DeepSort的基礎上加入了軌跡評分的機制，目前像FairMOT、JDE使用的跟蹤模塊都是MOTDT，從精度和速度上此算法表現都是不錯的。
2. 對圖神經網絡的追蹤算法的看法：
圖神經網絡在追蹤上的運用，是初嘗試。是offline且detection與reid沒有融合，所以速度方面，沒有優勢，會關注基於圖神經網絡的追蹤的後續優化。
目前以上追蹤算法正用於滴普的某養殖企業養殖場豬計數項目和某地產企業施工地段安全帽的檢測預警項目。詳細項目場景歡迎進入滴普科技官網了解（http://www.deepexi.com）。
七、參考文獻
[1]Multiple Object Tracking: A Literature Review. https://arxiv.org/abs/1409.7618
[2]Deep Learning in Video Multi-Object Tracking: a Survey. https://arxiv.org/pdf/1907.12740.pdf
[3] YOLOv4: Optimal Speed and Accuracy of Object Detection. https://arxiv.org/pdf/2004.10934v1.pdf
[4] MobileNetV2: Inverted Residuals and Linear Bottlenecks. https://arxiv.org/abs/1704.04861
[5]Deep Residual Learning for Image Recognition. https://arxiv.org/abs/1512.03385
[6]Deep Layer Aggregate. https://arxiv.org/pdf/1707.06484.pdf
[7] Feature Pyramid Networks for Object Detection. https://arxiv.org/pdf/1612.03144.pdf
[8] A Comprehensive Survey on Graph Neural Networks. https://arxiv.org/abs/1901.005