計算機視覺中，究竟有哪些好用的目标跟蹤算法（上）

相信很多來到這裡的人和我第一次到這裡一樣，都是想找一種比較好的目标跟蹤算法，或者想對目标跟蹤這個領域有比較深入的了解，雖然這個問題是經典目标跟蹤算法，但事實上，可能我們并不需要那些曾經輝煌但已被拍在沙灘上的tracker(目标跟蹤算法)，而是那些即将成為經典的，或者就目前來說最好用、速度和性能都看的過去的tracker。我比較關注目标跟蹤中的相關濾波方向，接下來我将介紹我所認識的目标跟蹤，尤其是相關濾波類方法，分享一些我認為比較好的算法，順便談談我的看法。

一

先來混個臉熟，大概了解一下目标跟蹤這個方向都有些什麼。一切要從2013年開始說起，那一年的冬天和往常一樣冷。如果你問别人近幾年有什麼比較niubility的跟蹤算法，大部分人都會扔給你吳毅老師的論文，OTB50和OTB100(OTB50這裡指OTB-2013，OTB100這裡指OTB-2015，感謝指正)：

Wu Y, Lim J, Yang M H. Online object tracking: A benchmark [C]// CVPR, 2013.

Wu Y, Lim J, Yang M H. Object tracking benchmark [J]. TPAMI, 2015.

頂會轉頂刊的頂級待遇，再加上引用量1200+200多，影響力不言而喻，已經是做tracking必須跑的資料庫了，測試代碼和序列都可以下載下傳： Visual Tracker Benchmark（http://cvlab.hanyang.ac.kr/tracker_benchmark/），OTB50包括50個序列，都經過人工标注：

論文在資料庫上對比了包括2012年及之前的29個頂尖的tracker，有大家比較熟悉的OAB, IVT, MIL, CT, TLD, Struck等，大都是頂會轉頂刊的神作，由于之前沒有比較公認的資料庫，論文都是自賣自誇，大家也不知道到底哪個好用，是以這個database的意義非常重大，直接促進了跟蹤算法的發展，後來又擴充為OTB100發到TPAMI，有100個序列，難度更大更權重威，我們這裡參考OTB100的結果，首先是29個tracker的情況(标出了一些性能速度都比較好的算法)：

接下來再看結果(更加詳細的情況建議您去看論文比較清晰)：

直接上結論：平均來看Struck, SCM, ASLA等算法的性能比較高，排在前三，着重強調CSK，第一次向世人展示了相關濾波的潛力，排第四還362FPS簡直逆天了。速度排第二的是經典算法CT(64fps)(這段時間是壓縮感覺大熱的時候，這裡能看到很多稀疏相關算法~都是曆史)。如果對更早期的算法感興趣，推薦另一篇經典的survey:

Yilmaz A, Javed O, Shah M. Object tracking: A survey [J]. CSUR, 2006.

2012年以前的算法基本就是這樣，自從2012年AlexNet問世以後，CV各個領域都有了巨大變化，是以我猜你肯定還想知道2013到2017年發生了什麼，抱歉我也不知道(容我賣個關子)，不過我們可以肯定的是，2013年以後的論文确定以及必定都會引用OTB50這篇論文，借助谷歌學術中的被引用次數功能，得到如下結果：

這裡僅列舉幾個排名靠前的，(注意引用量)依次是Struck轉TPAMI, 三大相關濾波方法KCF, CN, DSST, 和VOT競賽，這裡僅作示範，有興趣可以親自去試試。(這麼做的理論依據是：一篇論文，在它之前的工作可以看它的引用文獻，之後的工作可以看誰引用了它；雖然引用量并不能說明什麼，但好的方法大家基本都會引用的(表示認可)；之後還可以通過限定時間來檢視某段時間的相關論文，如2016-2017就能找到最新的論文了，至于論文品質需要仔細甄别；其他方向的重要論文也可以這麼用，順藤摸瓜，然後你就知道大牛是哪幾位，接着關注跟蹤一下他們的工作 )這樣我們就大緻知道目标跟蹤領域的最新進展應該就是相關濾波無疑了，再往後還能看到相關濾波類算法有SAMF, LCT, HCF, SRDCF等等。當然，引用量也與時間有關，建議分每年來看，這裡就不貼圖了(相關濾波類新論文也可以通過查引用KCF的論文去找)。此外，最新版本OPENCV3.2除了TLD，也包括了幾個很新的跟蹤算法 OpenCV: Tracking API（http://www.docs.opencv.org/3.2.0/d9/df8/group__tracking.html）：

TrackerKCF接口實作了KCF和CN，影響力可見一斑，這一點就可以說明很多問題了，還有個GOTURN是基于深度學習的方法，速度雖快但精度略差，竊以為太激進了...

二

總體介紹下目标跟蹤。這裡說的目标跟蹤，是通用單目标跟蹤，第一幀給個矩形框，這個框在資料庫裡面是人工标注的，在實際情況下大多是檢測算法的結果，然後需要跟蹤算法在後續幀緊跟住這個框，以下是VOT對跟蹤算法的要求：

通常目标跟蹤面臨幾大難點(吳毅在VALSE的slides)：外觀變形，光照變化，快速運動和運動模糊，背景相似幹擾：

平面外旋轉，平面内旋轉，尺度變化，遮擋和出視野等情況：

正因為這些情況才讓tracking變得很難，目前比較常用的資料庫除了OTB，還有谷歌學術找到的VOT競賽資料庫(類比ImageNet)，已經舉辦了四年，VOT2015和VOT2016都包括60個序列，所有序列也是免費下載下傳 VOT Challenge | Challenges（http://votchallenge.net/challenges.html）：

Kristan M, Pflugfelder R, Leonardis A, et al. The visual object tracking vot2013 challenge results [C]// ICCV, 2013.

Kristan M, Pflugfelder R, Leonardis A, et al. The Visual Object Tracking VOT2014 Challenge Results [C]// ECCV, 2014.

Kristan M, Matas J, Leonardis A, et al. The visual object tracking vot2015 challenge results[C]// ICCV, 2015.

Kristan M, Ales L, Jiri M, et al. The Visual Object Tracking VOT2016 Challenge Results [C]// ECCV, 2016.

OTB和VOT差別：OTB包括25%的灰階序列，但VOT都是彩色序列，這也是造成很多顔色特征算法性能差異的原因；兩個庫的評價名額不一樣，具體請參考論文；VOT庫的序列分辨率普遍較高，這一點後面分析會提到。對于一個tracker，如果兩個庫(最好是OTB100和VOT2016)都跑了且結果上佳，那性能肯定是非常優秀的(兩個庫調參你能調好，我服，認了~~)。如果隻跑了一個，(僅供參考)我比較認可的是VOT2016，因為序列都是精細标注，且評價名額我更加認可(人家畢竟是競賽，評價名額發過TPAMI的)，差别最大的地方，OTB是随機幀開始，或矩形框加随機幹擾初始化去跑，作者說這樣更加符合檢測算法給的框框；而VOT是第一幀初始化去跑，每次跟蹤失敗(預測框和标注框不重疊)時，5幀之後再次初始化，VOT以short-term為主，且認為跟蹤檢測應該在一起永不分離，detecter會多次初始化tracker。至于哪個更好，看你，和你的需求。

補充：OTB在2013年公開了，對于2013以後的算法是透明的，有調參的可能性，尤其是那些隻跑OTB，而且論文中有關鍵參數直接給出還精确到小數點後兩位的算法，建議您先實測再評價(人心不古啊~被坑的多了)，但VOT競賽的資料庫是每年更新，還動不動就重新标注，動不動就改變評價名額，對當年算法是不可見且難度很大的，是以結果更可靠。如果您認可以上看法，後面會推薦很多在我看來頂尖又快速的算法。如果您不認可以上看法，後面也就沒必要看下去了，謝謝！（看每篇論文都會覺得這個工作太好太重要了，如果沒有這篇論文，必會地球爆炸，宇宙重新開機~~是以就像大家都通過曆年ILSVRC競賽結果為主線了解深度學習的發展一樣，第三方的結果更具說服力，是以我也以競賽排名+是否公開源碼+實測性能為标準分析每個方法）

目标視覺跟蹤(Visual Object Tracking)，大家比較公認分為兩大類：生成(generative)模型方法和判别(discriminative)模型方法，目前比較流行的是判别類方法，也叫檢測跟蹤tracking-by-detection，為保持完整性，以下簡單介紹。

生成類方法，在目前幀對目标區域模組化，下一幀尋找與模型最相似的區域就是預測位置，比較著名的有卡爾曼濾波，粒子濾波，mean-shift等。舉個例子，從目前幀知道了目标區域80%是紅色，20%是綠色，然後在下一幀，搜尋算法就像無頭蒼蠅，到處去找最符合這個顔色比例的區域，推薦算法ASMSvojirt/asms（https://github.com/vojirt/asms）：

Vojir T, Noskova J, Matas J. Robust scale-adaptive mean-shift for tracking [J]. Pattern Recognition Letters, 2014.

ASMS是VOT2015的第20名官方推薦的實時算法，VOT2016的32名(中等水準)，平均幀率125FPS，在經典mean-shift架構下加入了尺度估計，經典顔色直方圖特征，加入了兩個先驗(尺度不劇變+可能偏最大)作為正則項，和反向尺度一緻性檢查。作者給了C++代碼，在相關濾波和深度學習盛行的年代，還能看到mean-shift打榜還有如此高的成本效益實在不容易(已淚目~~)，實測性能還不錯，如果您對生成類方法情有獨鐘，這個非常推薦您去試試。

判别類方法，OTB50裡面的大部分方法都是這一類，CV中的經典套路圖像特征+機器學習，目前幀以目标區域為正樣本，背景區域為負樣本，機器學習方法訓練分類器，下一幀用訓練好的分類器找最優區域(馬超在VALSE的slides)：

與生成類方法最大的差別，是分類器訓練過程中用到了背景資訊，這樣分類器就能專注區分前景和背景，是以判别類方法普遍都比生成類好。舉個例子，在訓練時告訴tracker目标80%是紅色，20%是綠色，還告訴它背景中有橘紅色，要格外注意别搞錯了，這樣的分類器知道更多資訊，效果也肯定更好。tracking-by-detection和檢測算法非常相似，如經典行人檢測用HOG+SVM，Struck用到了haar+structured output SVM，跟蹤中為了尺度自适應也需要多尺度周遊搜尋，差別僅在于跟蹤算法對特征和線上機器學習的速度要求更高，檢測範圍和尺度更小而已。這點其實并不意外，大多數情況檢測識别算法複雜度比較高不可能每幀都做，這時候用複雜度更低的跟蹤算法就很合适了，隻需要在跟蹤失敗(drift)或一定間隔以後再次檢測去初始化tracker就可以了。經典判别類方法推薦Struck和TLD，實時性能還行，Struck是2012年之前最好的方法，TLD是經典long-term的代表，即使效果差一點但思想非常值得借鑒：

Hare S, Golodetz S, Saffari A, et al. Struck: Structured output tracking with kernels [J]. IEEE TPAMI, 2016.

Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection [J]. IEEE TPAMI, 2012.

長江後浪推前浪，前面的已被拍在沙灘上，後浪就是相關濾波類方法(correlation filter簡稱CF，或discriminative correlation filter簡稱DCF，注意和後面KCF種的DCF方法差別，包括前面提到的那幾個，後面要着重介紹)，和深度學習(Deep ConvNet based)類方法，因為深度學習類并不了解就不瞎推薦了，除了Winsty的幾篇 Naiyan Wang - Home（http://www.winsty.net/），還有VOT2015的冠軍MDNet Learning Multi-Domain Convolutional Neural Networks for Visual Tracking（http://cvlab.postech.ac.kr/research/mdnet/）和VOT2016的冠軍TCNN（http://www.votchallenge.net/vot2016/download/44_TCNN.zip），速度方面比較突出的如80FPS的SiamFC SiameseFC tracker（http://www.robots.ox.ac.uk/~luca/siamese-fc.html）和100FPS的GOTURN davheld/GOTURN（https://github.com/davheld/GOTURN），注意是在GPU上。基于ResNet的SiamFC-R在VOT2016表現不錯，很看好後續發展，如果有興趣可以去VALSE聽作者自己講解 VALSE-20160930-LucaBertinetto-Oxford-JackValmadre-Oxford-pu（http://www.iqiyi.com/w_19ruirwrel.html#vfrm=8-8-0-1），至于GOTURN，效果比較差，跑100FPS又有什麼用呢，是以還不推薦，暫時持觀望态度。寫論文的同學深度學習類是特點也有巨大潛力。

Nam H, Han B. Learning multi-domain convolutional neural networks for visual tracking[C]// CVPR, 2016.

Nam H, Baek M, Han B. Modeling and propagating cnns in a tree structure for visual tracking. arXiv preprint arXiv:1608.07242, 2016.

Bertinetto L, Valmadre J, Henriques J F, et al. Fully-convolutional siamese networks for object tracking [C]// ECCV, 2016.

Held D, Thrun S, Savarese S. Learning to track at 100 fps with deep regression networks[C]// ECCV, 2016.

還有幾篇國人大作遇到了不要驚訝：MEEM, TGPR, CLRST, MUSTer，在VOT中能看到身影。最後，深度學習END2END的強大威力在目标跟蹤方向還遠沒有發揮出來，還沒有和相關濾波類方法拉開多大差距(速度慢是天生的我不怪你，但效果總該很高吧，不然你存在的意義是什麼呢。。革命尚未成功，同志仍須努力)

最後強力推薦@Qiang Wang維護的資源benchmark_results：大量頂級方法在OTB庫上的性能對比，各種論文代碼應有盡有，大神自己C++實作并開源的CSK, KCF和DAT，找不着路的同學請跟緊，别迷路foolwood/benchmark_results（https://github.com/foolwood/benchmark_results），還有他自己最新論文DCFNet論文加源碼，别錯過。

再隆重推薦@H Hakase維護的相關濾波類資源HakaseH/CF_benchmark_results（https://github.com/HakaseH/CF_benchmark_results），詳細分類和論文代碼資源，走過路過别錯過，是我見過的最詳盡的相關濾波資源，可見非常之用心！

三

接下來介紹幾個最經典的高速相關濾波類跟蹤算法CSK, KCF/DCF, CN。很多人最早了解CF，應該和我一樣，都是被下面這張圖吸引了：

這是KCF/DCF算法在OTB50上(2014年4月就挂arVix了, 那時候OTB100還沒有發表)的實驗結果，Precision和FPS碾壓了OTB50上最好的Struck，看慣了勉強實時的Struck和TLD，飙到高速的KCF/DCF突然有點讓人不敢相信，其實KCF/DCF就是在OTB上大放異彩的CSK的多通道特征改進算法。注意到那個超高速615FPS的MOSSE了吧(嚴重超速這是您的罰單)，這是目标跟蹤領域的第一篇相關濾波類方法，這其實是真正第一次顯示了相關濾波的潛力。和KCF同一時期的還有個CN，在2014'CVPR上引起劇烈反響的顔色特征方法，其實也是CSK的多通道顔色特征改進算法。從MOSSE(615)到 CSK(362) 再到 KCF(172FPS), DCF(292FPS), CN(152FPS), CN2(202FPS)，速度雖然是越來越慢，但效果越來越好，而且始終保持在高速水準：

Bolme D S, Beveridge J R, Draper B A, et al. Visual object tracking using adaptive correlation filters [C]// CVPR, 2010.

Henriques J F, Caseiro R, Martins P, et al. Exploiting the circulant structure of tracking-by- detection with kernels [C]// ECCV, 2012.

Henriques J F, Rui C, Martins P, et al. High-Speed Tracking with Kernelized Correlation Filters [J]. IEEE TPAMI, 2015.

Danelljan M, Shahbaz Khan F, Felsberg M, et al. Adaptive color attributes for real-time visual tracking [C]// CVPR, 2014.

CSK和KCF都是Henriques J F(牛津大學)João F. Henriques 大神先後兩篇論文，影響後來很多工作的嶺回歸，循環移位的近似密集采樣，還給出了整個相關濾波算法的詳細推導。還有嶺回歸加kernel-trick的封閉解，多通道HOG特征。

Martin Danelljan大牛(林雪平大學)用多通道顔色特征Color Names(CN)去擴充CSK得到了不錯的效果，算法也簡稱CN Coloring Visual Tracking 。

MOSSE是單通道灰階特征的相關濾波，CSK在MOSSE的基礎上擴充了密集采樣(加padding)和kernel-trick，KCF在CSK的基礎上擴充了多通道梯度的HOG特征，CN在CSK的基礎上擴充了多通道顔色的Color Names。HOG是梯度特征，而CN是顔色特征，兩者可以互補，是以HOG+CN在近兩年的跟蹤算法中成為了hand-craft特征标配。最後，根據KCF/DCF的實驗結果，讨論兩個問題：

1. 為什麼隻用單通道灰階特征的KCF和用了多通道HOG特征的KCF速度差異很小？

第一，HOG，作者用了HOG的快速算法fHOG，來自Piotr's Computer Vision Matlab Toolbox，C代碼而且做了SSE優化。如對fHOG有疑問，請參考論文Object Detection with Discriminatively Trained Part Based Models第12頁。

第二，HOG特征常用cell size是4，這就意味着，100*100的圖像，HOG特征圖的次元隻有25*25，而Raw pixels是灰階圖歸一化，次元依然是100*100，我們簡單算一下：27通道HOG特征的複雜度是27*625*log(625) = 47180,而單通道灰階特征的複雜度是10000log（10000）=40000 ，結果也是相差不多，符合表格(不知道這種算法對不對，如果有誤請指出，謝謝)。

看代碼你會發現，作者在擴充後目标區域面積較大時，會先對提取到的圖像塊做因子2的下采樣，到50*50這樣複雜度就變成了2500log（2500）=8495，下降了非常多。那你可能會想，如果下采樣再多一點，複雜度就更低了，但這是以犧牲跟蹤精度為代價的，再舉個例子，如果圖像塊面積為200*200，先下采樣到100*100，再提取HOG特征，分辨率降到了25*25，這就意味着響應圖的分辨率也是25*25，也就是說，響應圖每位移1個像素，原始圖像中跟蹤框要移動8個像素，這樣就降低了跟蹤精度。在精度要求不高時，你完全可以稍微犧牲下精度提高幀率(但真的不能再下采樣了)。

2. HOG特征的KCF和DCF哪個更好？

大部分人都會認為KCF效果超過DCF，而且各屬性的準确度都在DCF之上，然而，如果換個角度來看，以DCF為基準，再來看加了kernel-trick的KCF，mean precision僅提高了0.4%，而FPS下降了41%，這麼看是不是挺驚訝的呢？除了圖像塊像素總數，KCF的複雜度還主要和kernel-trick相關。是以，下文中的CF方法如果沒有kernel-trick，就簡稱基于DCF，如果加了kernel-trick，就簡稱基于KCF(劇透，基本兩類各占一半)。當然這裡的CN也有kernel-trick，但請注意，這是Martin Danelljan大神第一次使用kernel-trick，也是最後一次。

可能會有這樣的疑問，kernel-trick這麼強大的東西，怎麼才提高這麼點？這裡就不得不提到Winsty的另一篇大作：

Wang N, Shi J, Yeung D Y, et al. Understanding and diagnosing visual tracking systems[C]// ICCV, 2015.

一句話，别看那些五花八門的機器學習方法，那都是虛的，目标跟蹤算法中特征才是最重要的（就是因為這篇文章我成了WIN叔粉絲，哈哈），以上就是前三個首先推薦的高速算法，CSK, KCF/DCF和CN。

四

VOT2014競賽 VOT2014 Benchmark （http://votchallenge.net/vot2014/index.html）。這一年有25個精挑細選的序列，38個算法，那時候深度學習的戰火還沒有燒到tracking，是以也隻能CF獨霸一方了，下面是前幾名的具體情況：

前三名都是相關濾波CF類方法，第三名的KCF已經很熟悉了，這裡稍微有點差別就是加了多尺度檢測和子像素峰值估計，再加上VOT序列的分辨率比較高(檢測更新圖像塊的分辨率比較高)，導緻KCF的速度隻有24.23(EFO換算66.6FPS)。這裡的speed指的的EFO(Equivalent Filter Operations)，在VOT2015和VOT2016裡面也用這個參數衡量算法速度，這裡一次性列出來供參考(MATLAB實作的tracker實際速度要更高一些)：

其實前三名除了特征略有差異，核心都是擴充了多尺度檢測，概要如下：

尺度變化是跟蹤中比較基本和常見的問題，前面介紹的三個算法都沒有尺度更新，如果目标縮小，濾波器就會學習到大量背景資訊，如果目标擴大，濾波器就跟着目标局部紋理走了，這兩種情況都很可能出現非預期的結果，導緻漂移和失敗。

推薦SAMF ihpdep/samf（https://github.com/ihpdep/samf），來自浙大的工作，基于KCF，特征是HOG+CN，多尺度方法是平移濾波器在多尺度縮放的圖像塊上進行目标檢測，取響應最大的那個平移位置和響應所在尺度：

Li Y, Zhu J. A scale adaptive kernel correlation filter tracker with feature integration [C]// ECCV, 2014.

和Martin Danelljan的DSST Accurate scale estimation for visual tracking（http://www.cvl.isy.liu.se/research/objrec/visualtracking/scalvistrack/index.html），專門訓練類似MOSSE的尺度濾波器用于檢測尺度變化，開創了平移濾波+尺度濾波，之後轉PAMI做了一系列加速：

Danelljan M, Häger G, Khan F, et al. Accurate scale estimation for robust visual tracking[C]// BMVC, 2014.

Danelljan M, Hager G, Khan F S, et al. Discriminative Scale Space Tracking [J]. IEEE TPAMI, 2017.

簡單對比下這兩種多尺度方法：

DSST和SAMF所采用的尺度檢測方法哪個更好？

首先給大家講個笑話：Martin Danelljan大神提出DSST之後，他的後續論文就再沒有用過。

1、雖然SAMF和DSST都可以跟上普通的目标尺度變化，但SAMF隻有7個尺度比較粗，而DSST有33個尺度比較精細準确；

2、DSST先檢測最佳平移再檢測最佳尺度，是分布最優，而SAMF是平移尺度一起檢測，是平移和尺度同時最優，而往往局部最優和全局最優是不一樣的；

3、DSST看成兩個問題可以采用不同的方法和特征更加靈活，但需要額外訓練一個濾波器，每幀尺度檢測需要采樣33個圖像塊，分别計算特征，加窗，FFT，尺度濾波器還要額外訓練；SAMF隻需要一個濾波器，不需要額外訓練和存儲，每個尺度檢測就一次提特征和FFT，但在圖像塊較大時計算量比DSST高。

是以尺度檢測DSST并不總是比SAMF好，其實，在VOT2015和VOT2016上SAMF都是超過DSST的，當然這主要是因為特征更好，但至少說明尺度方法不差。雖然DSST比SAMF更具創新度，但SAMF也是很優秀的方法。(記得高中數學老師說過，“一個人一生能有一點點創新就非常了不起了”，是以我們才會看到那麼那麼多灌水論文，創新真的太難了，那些雖然創新力不夠但踏踏實實有效果，敢公開源碼經得起驗證的論文同樣值得欽佩)

DSST一定要33個尺度嗎？

如果你認真跑過實驗，就會發現DSST标配的33個尺度非常非常敏感，輕易降低尺度數量，即使你增加相應步長，尺度濾波器也會完全跟不上尺度變化。關于這一點我想到的可能解釋是，訓練尺度濾波器用的是一維樣本，而且沒有循環移位，這就意味着一次訓練更新隻有33個樣本，如果降低樣本數量，會造成訓練不足，分類器判别力嚴重下降，不像平移濾波器有非常多的移位樣本(如果不對或您有其他看法歡迎交流)。總之，請不要輕易嘗試大幅降低尺度數量，如果非要用尺度濾波器33和1.02就好。

以上就是兩種推薦的尺度檢測方法，以後簡稱為類似DSST的多尺度和類似SAMF的多尺度。如果您對尺度的要求不高而更看重速度，SAMF隻要3個尺度就可以粗略跟上尺度變化(比如VOT2014中的KCF)；如果您需要精确尺度跟蹤，則推薦DSST但速度稍慢，且DSST的尺度數量不能輕易減少；如果尺度變化不明顯則不推薦使用。

本文作者：Non