【CV】帶你入門多目標跟蹤（二）SORT&DeepSORT
本文將帶大家解析一下SORT和DeepSORT的基本思路，廢話不多說，開始正題。
1. SORT
首先要說明一點，現(xiàn)在多目標跟蹤算法的效果，與目標檢測的結果息息相關，因為主流的多目標跟蹤算法都是TBD（Tracking-by-Detecton）策略，這里不再贅述，有不懂的小伙伴可以去看本系列的第一篇領域綜述。
在SORT論文的一開始，作者也強調(diào)了這一點。作者原話是說通過更換檢測器可以將跟蹤效果提高18.9個百分點。說這點是為了給做工程的朋友們一個啟示，用再花哨的跟蹤算法，有時也不如用針對性訓練的檢測器來的效果好。在實際工程中，為了提高多目標跟蹤的效果，可以從檢測器處多做文章（比如多收集一些對應任務的數(shù)據(jù)來訓練檢測器），跟蹤的效果也會水漲船高。
拋開檢測不談，我們來看SORT的跟蹤思路。SORT采用的是在線跟蹤的方式，不使用未來幀的信息。在保持100fps以上的幀率的同時，也獲得了較高的MOTA（在當時16年的結果中）。
SORT的貢獻主要有三：
利用強大的CNN檢測器的檢測結果來進行多目標跟蹤
使用基于卡爾曼濾波（Kalman filter）與匈牙利算法（Hungarian algorithm）的方法來進行跟蹤
開源了代碼，為MOT領域提供一個新的baseline
現(xiàn)在看可能不覺得有什么，思路并不新奇也并不復雜，但在當時還是作出很大的貢獻的，有力推動了MOT的發(fā)展。
其中卡爾曼濾波（Kalman filter）與匈牙利算法（Hungarian algorithm）對于大家來說可能是兩個新名詞。先簡單解釋一下，匈牙利算法是一種尋找二分圖的最大匹配的算法，在多目標跟蹤問題中可以簡單理解為尋找前后兩幀的若干目標的匹配最優(yōu)解的一種算法。而卡爾曼濾波可以看作是一種運動模型，用來對目標的軌跡進行預測，并且使用確信度較高的跟蹤結果進行預測結果的修正，是控制領域常用的一種算法。有熟悉無人機飛控算法的小伙伴應該會對這個感到很親切。
可能初次接觸的小伙伴還不是非常理解，不用擔心，我們存疑，后文還會更詳細地講到。
至于具體的跟蹤過程，SORT在以往二階段匹配算法的基礎上進行了創(chuàng)新。
以往二階段匹配算法是先使用匈牙利算法對相鄰幀之間的目標進行匹配生成很多tracklets，之后使用這些tracklets進行二次匹配，以解決遮擋等問題引起的軌跡中斷。但這種二階段匹配方式弊端也很明顯，因為這種方式先天地要求必須以Offline的方法進行跟蹤，而無法做到Online。
SORT將這種二階段匹配算法改進為了一階段方法，并且可以在線跟蹤。
具體而言，SORT引入了線性速度模型與卡爾曼濾波來進行位置預測，先進行位置預測然后再進行匹配。在無合適匹配檢測框的情況下，運動模型的結果可以用來預測物體的位置。
在數(shù)據(jù)關聯(lián)的階段，SORT使用的依舊是匈牙利算法逐幀關聯(lián)，不過作者還引入了IOU（Intersection-Over-Union）距離。不過SORT用的是帶權重的匈牙利算法，其實就是KM算法，用IOU距離作為權重（也叫cost矩陣）。作者代碼里是直接用sklearn的linear_assignment實現(xiàn)，有興趣的話也可以去看看這個函數(shù)的實現(xiàn)細節(jié)，我下一篇文章會稍微講講匈牙利算法和KM算法的原理，這里不懂可以先存疑。并且當IOU小于一定數(shù)值時，不認為是同一個目標，理論基礎是視頻中兩幀之間物體移動不會過多。作者在代碼中選取的閾值是0.3，
不過我個人在實驗中對這一點不是完全認同，雖然兩幀之間物體的運動量可能不大，但由于檢測器自身檢測結果不準，目標框偏移可能較大，還是會造成IOU過小，這時再用論文中這種方法，會導致誤判引起的軌跡中斷。具體案例在MOT的DPM檢測結果中很容易找到。說起DPM，真可謂是MOT研究者的夢魘了……衷心希望MOT19能拋棄DPM。
2. DeepSORT
一年之后，原團隊發(fā)布了SORT的續(xù)作DeepSORT，到現(xiàn)在都有很多人在用這個跟蹤器。
整體框架沒有大改，還是延續(xù)了卡爾曼濾波加匈牙利算法的思路，在這個基礎上增加了Deep Association Metric。Deep Association Metric其實就是在大型行人重識別網(wǎng)絡上學習的一個行人鑒別網(wǎng)絡。目的是區(qū)分出不同的行人。個人感覺很類似于典型的行人重識別網(wǎng)絡。輸出行人圖片，輸出一組向量，通過比對兩個向量之間的距離，來判斷兩副輸入圖片是否是同一個行人。
此外還加入了外觀信息（Appearance Information）以實現(xiàn)較長時間遮擋的目標跟蹤。
跟蹤流程延續(xù)上作，在卡爾曼濾波的預測結果的基礎上，繼續(xù)使用了匈牙利算法進行目標分配，但在這個過程中加入了運動信息和外觀信息。這個說起來簡單，實現(xiàn)起來比較復雜，感興趣的讀者可以細看論文和代碼。在這里就不贅述了。
其他方面沒有太多變化，還是使用了標準的卡爾曼濾波和固定速度模型等來進行預測。
最終實現(xiàn)了較好的跟蹤效果（MOTA61.4@MOT16），并且能夠?qū)崟r運行（40FPS）。
代碼和論文可以在以下鏈接獲得。感謝SpyderXu的整理。
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.
github.com/SpyderXu/mul
這一篇和大家一起過了一遍SORT這個經(jīng)典的算法，雖然思路并不復雜，但還是值得細細品味的。當然其中還有幾點概念沒有說清，下一篇將帶大家繼續(xù)深入。
下一篇將著重講解MOT中常用的一些算法，比如匈牙利算法和KM算法等。打下一個良好的基礎，才能走的更遠，朋友們下篇見！
往期精彩回顧
獲取本站知識星球優(yōu)惠券，復制鏈接直接打開：
https://t.zsxq.com/qFiUFMV
本站qq群704220115。
加入微信群請掃碼：