多目標跟蹤算法總結歸納

導讀 多目標跟蹤是計算機視覺領域中的一個重要任務，它旨在從視頻或圖像序列中準確地檢測和跟蹤多個移動目標。不過在落地部署時，有一些關鍵點需要解決。本文從快速應用部署的角度，和大家講解多目標跟蹤的實現方式，希望對大家有幫助。 實際應用中，做工程落地所遵從的原則是能夠在保證實現功能的情況下，以最快的速度實現，先出一版，后期再不斷迭代優化。所以定方案是最重要的，前期的調研工作做的好，對于后續的部署會極為方便，否則會走很多彎路。

回到本文的內容中來，目標檢測已產生出很多優秀的算法（這里提的都是基于神經網絡的算法，傳統的CV檢測算法不在考慮范圍內），類似的綜述性文章很多，無論單階段式的(ssd/yolo)，還是兩階段式的（faster rcnn）在實際工程中都有被應用，哪種框架用的熟練就用哪種框架，目標檢測這一塊就不過多討論； 多目標追蹤顧名思義就是跟蹤視頻畫面中的多個目標，得到這些目標的運動軌跡；核心在于目標檢測和數據關聯，即在每一幀進行目標檢測，再利用目標檢測的結果來進行目標跟蹤，后面一步一般稱之為數據關聯，數據關聯更多依賴于手工特征提取(外觀特征、運動特征、形狀特征)。下面就多目標跟蹤算法總結歸納為以下幾類：

一、以卡爾曼濾波和匈牙利、KM匹配的后端追蹤優化算法(代表性的應用有SORT、DEEP-SORT)

這類算法特點在于能達到實時性，但依賴于檢測算法效果要好，特征區分要好（有點互相甩鍋的味道，輸出最終結果的好壞依賴于較強的檢測算法，而基于卡爾曼加匈牙利匹配的追蹤算法作用在于能夠輸出檢測目標的id，其次能保證追蹤算法的實時性），這樣追蹤效果會好，id切換少。相關論文和代碼如下:

DeepSort: Wojke, Nicolai and Bewley, Alex and Paulus, Dietrich "Simple Online and Realtime Tracking with a Deep Association Metric" [paper] [code] In ICIP 2017

Sort: Bewley, Alex and Ge, Zongyuan and Ott, Lionel and Ramos, Fabio and Upcroft, Ben "Simple Online and Realtime Tracking"[paper] [code] In ICIP 2016.

二、基于多線程的單目標跟蹤器的多目標追蹤算法(代表性的算法有KCF、LEDS)

這類算法特點是跟蹤效果會很好，因為其為每一類物體都單獨分配了一個跟蹤器。但該算法對目標尺度變化要求較大，參數調試需要合理，同時該算法極耗cpu資源，實時性不高。相關論文和代碼如下:

KCF: "High-Speed Tracking with Kernelized Correlation Filters" [paper] [code] In TPAMI 2015

LEDS："Robust Estimation of Similarity Transformation for Visual Object Tracking" [paper] [code] In AAAI 2019.

三、 基于深度學習端到端的多目標跟蹤算法。(代表性的算法有SST)

現階段end-to-end的算法還不多，大多處于實驗室刷榜階段，有進一步落地應用的及時更新。相關論文和代碼如下:

DAN: "Deep Affinity Network for Multiple Object Tracking" [paper] [code] In TPAMI 2019.

MCSA: "Multi-Object Tracking with Multiple Cues and Switcher-Aware Classification" [paper] In CVPR 2019.

（這篇文章沒有開源，基于SiameseRPN單目標跟蹤器和行人ReID的多目標跟蹤算法，解決長期跟蹤下的目標漂移問題。利用SiameseRPN獲取短期的目標線索，利用ReID特征計算目標間的匹配置信度，基于該置信度構建二分圖，求解最小費用流得到長期的跟蹤結果）

上述文章參考來源：

github.com/SpyderXu/multi-object-tracking-paper-list

第一類算法原理介紹：

SORT 是一種實用的多目標跟蹤算法，引入了線性速度模型與卡爾曼濾波來進行位置預測，在無合適匹配檢測框的情況下，使用運動模型來預測物體的位置。匈牙利算法是一種尋找二分圖的最大匹配的算法，在多目標跟蹤問題中可以簡單理解為尋找前后兩幀的若干目標的匹配最優解的一種算法。而卡爾曼濾波可以看作是一種運動模型，用來對目標的軌跡進行預測，并且使用確信度較高的跟蹤結果進行預測結果的修正。

然而由于現實中目標運動多變且遮擋頻繁，該算法的身份轉換（Identity Switches）次數較高。于是衍生出帶有深度關聯特征的DeepSORT 方案，其沿用SORT中的卡爾曼濾波和逐幀數據關聯方法并整合外觀信息，使得身份轉換的數量減少了45％。所提方案為：

l 使用馬氏距離和深度特征余弦距離兩種度量；

l 采取級聯匹配，優先匹配距上次出現間隔短的目標；

l 第一級關聯以余弦距離作為成本函數，但設定馬氏距離和余弦距離兩個閾值約束；

l 第二級關聯與 SORT 中相同，嘗試關聯未確認和年齡為 n=1的不匹配軌跡；

l 同樣采用試用期甄別目標，但大幅提高軌跡壽命 Amax=30。

核心：軌跡處理和狀態估計、關聯問題、級聯匹配、特征描述器

Deepsort處理流程 實現應用：實際工程中存在一些硬性指標，必須考慮硬件平臺的資源（車載控制器iecu、Nvidia平臺、FPGA），cpu內存大小，是否有gpu，是否支持神經網絡(caffe)，是否支持部署在硬件端的編程語言(C++、verilog)。目前在學術界極受歡迎的pytorch框架，訓練模型可以，部署在硬件端不現實，底層調用的接口還是純正的c代碼?，F在各類網絡模型可以實現的框架很多，舉個例子：目標檢測網絡ssd可以用caffe框架實現，也可以用pytorch框架實現，按正常的想法，兩種最后訓練出來的模型精度、速度應該類似，實際情況是最后出來的效果是有差別的，部署在硬件端同樣有差別。另外用pytorch框架還需要轉成支持C++的語言，不過現在pytorch已經出了可以調用libtorch的c++接口，以及支持tensort轉換，方便基于pytorch的研究者們將代碼部署在硬件端。

多目標追蹤一般接在目標檢測后。在工業界目標檢測采用比較多的是ssd檢測網絡，單階段式，速度快，精度不差，修改其backbone，速度會進一步提升，部署在NV的平臺幀率可以達到30fps以上。所以要實現目標檢測代碼和多目標追蹤代碼集成的任務，需要先將兩者的框架統一，若采用C++的目標檢測網絡（Yolo,ssd均可），多目標追蹤也采用C++框架，這里因為都是跟實際工程打交道，就直接考慮C++語言了，訓練模型還是可以采用任意框架，最后轉成C++可以調用的模型即可。先實現目標檢測網絡，檢測的輸出結果主要是將檢測框的位置信息輸入到多目標追蹤算法中。在實驗室階段，看多目標跟蹤的效果即可。實際過程中，針對多目標跟蹤的輸出接口是有需求的，輸出的物體類別，對應類別物體的id，以及增加個數對應的id號，持續的幀數等，這些信息都會通過lcm通信的方式傳輸給智駕融合層。

Deep-Sort視頻效果展示

追蹤結果分析：淡綠色的檢測框為檢測的結果，紅色框為跟蹤后的結果，很明顯若檢測效果魯棒的話，對于追蹤的效果也會提升。在視頻中，遠處的檢測框會不穩定（這跟檢測的距離有關），距離靠近時還存在不太穩定的檢測框（如右轉的紅燈：檢測的淡藍色檢測框時而存在時而消失），而代表多目標追蹤的紅色框能夠繼續維持，說明多目標跟蹤起了維持檢測框軌跡的作用，確保其檢測框不消失，起到了跟蹤的作用。而且基本不耗時，實時性也能達到要求。

內存占用率: 0.4%;

耗時: 40fps;

準確率: 基本取決于檢測效果，能起到維持檢測框的作用。

第二類算法原理介紹：

多目標追蹤本質上是多個目標同時運動的問題，所以有提出將單目標跟蹤器引入到多目標追蹤的問題，為每一個目標分配一個跟蹤器，然后間接地使用匹配算法來修正那些跟蹤失敗或新出現的目標。代表性的單目標跟蹤算法為核相關濾波算法（KCF）,它于2014年提出，在精度和速度上能夠同時達到很高的水平，是當時單目標跟蹤最優秀的算法之一。后來的很多單目標跟蹤算法都是基于此做的改進，經典的還是最好的。實際工程不需要刷榜，能快速實現功能，更多的針對具體問題加一些邊界條件，約束條件，使得最終結果能夠滿足實際的需求。

核相關濾波（Kernelized Correlation Filter,KCF）是相關濾波算法的一種擴展。相關濾波是指在模板的一個鄰域內搜索和模板響應值最大的位置，可以視為一種模板匹配的方法，具有很高的實時性。將濾波器表示成一個權值向量，將濾波器和模板的響應值寫作權值和特征向量的內積：

其中w表示濾波器權重，z表示模板。求解一個最優的濾波器，使得濾波器的權值和模板特征向量的內積和標準響應圖的誤差最小，可以寫作：

X表示一個循環采樣的樣本集合。在頻域中可求得上式的解為：

實際應用過程中會為每個目標分配一個KCF跟蹤器并采用多線程的方式來組織這些跟蹤器。同時因為實際硬件條件的限制，不可能提供強大的計算力資源，會采用檢測器與跟蹤器交替進行的跟蹤策略。

多線程的單目標跟蹤方式

實際效果：采用多線程的單目標跟蹤器的方法，在該離線視頻上檢測框的維持效果還是不錯的，而且id幾乎沒有切換，很穩定；但實車測試的時候，將其移植于嵌入式端，由于檢測的幀率不高，使得跟蹤的維持效果出現滯后或框飄的現象較為嚴重，實用性不大。

實車驗證時嚴重的框飄現象

內存占用率: 10-20%;

耗時: 18-24fps(物體類別越多，速度越慢);

準確率: 車速較慢時，維持檢測框的效果很穩定; 但當車速較快時，這種跟蹤方法維持檢測框效果較差，會出現框飄的現象。

第三類算法原理介紹：

這篇文章是在目標檢測ssd的基礎上不斷改進迭代的，這里引用一些論文作者的觀點，

DAN is an end-to-end deep learning network during train phase, whose purpose is to extract the predetected objects' feature and performs pairing permutations of those features in any two frames to infer object affinities. Besides, DAN also accounts for multiple objects appearing and disappearing between video frames.

DAN網絡在訓練階段是一個端到端的神經網絡，它的目標是提取預先檢測到的對象特征，并在任意兩幀執行特征的配對序列，以得到物體的相似度。另外，DAN網絡也能很好處理兩幀之間出現和消失的多目標。

The network can be divided into two parts: feature extractor and affinity extractor. The feature extractor extracts each detected objects' features. The affinity extractor leverage those features to compute object data association matrix.

網絡可以分為兩部分：特征提取器和相似度提取器。特征提取器提取每個檢測對象的特征。相似度提取器利用這些特征來計算檢測對象數據關聯矩陣。

更詳細的原理分析可以參考：李元芳：Deep Affinity Network for Multiple Object Tracking

SST的檢測效果

實際效果：速度極慢，不適用于部署到嵌入式端，還是刷榜的存在，嘗試更換其backbone網絡，加快速度。同時可以考慮將檢測的特征與追蹤所需的特征融合，最終輸出一個權重文件。

內存占用率:15%;

耗時:3fps(速度極慢);

準確率:跟蹤效果還行，軌跡描繪良好。

多目標跟蹤算法對比

審核編輯：黃飛