計算機視覺中，目前有哪些經典的目標跟蹤演算法？

11-25

我所知道的有tld、compressive tracking、struck。還望補充！

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

1.圖片來自某些slides和paper，如有侵權請提醒刪除。

2.以下內容主要是論文的簡單總結，代碼分析和個人看法，不涉及任何公司內部資料。

3.轉載請註明出處，謝謝。

4.如有錯誤歡迎指出，非常感謝。有問題可以私信我，也可以在評論區提出，時間有限但也都會盡量回復，同時感謝各位道友幫忙解答。

第一部分：目標跟蹤速覽

先跟幾個SOTA的tracker混個臉熟，大概了解一下目標跟蹤這個方向都有些什麼。一切要從2013年的那個資料庫說起。。如果你問別人近幾年有什麼比較niubility的跟蹤演算法，大部分人都會扔給你吳毅老師的論文，OTB50和OTB100(OTB50這裡指OTB-2013，OTB100這裡指OTB-2015，50和100分別代表視頻數量，方便記憶)：

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.

頂會轉頂刊的頂級待遇，在加上引用量1480+320多，影響力不言而喻，已經是做tracking必須跑的資料庫了，測試代碼和序列都可以下載： Visual 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)(與SCM, ASLA等都是那個年代最熱的稀疏表示)。如果對更早期的演算法感興趣，推薦另一篇經典的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等等。當然，引用量也與時間有關，建議分每年來看。此外，最新版本OPENCV3.2除了TLD，也包括了幾個很新的跟蹤演算法 OpenCV: Tracking API：

TrackerKCF介面實現了KCF和CN，影響力可見一斑，還有個GOTURN是基於深度學習的方法，速度雖快但精度略差，值得去看看。tracking方向的最新論文，可以跟進三大會議(CVPR/ICCV/ECCV) 和arXiv。

第二部分：背景介紹

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

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

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

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

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%是綠色，然後在下一幀，搜索演算法就像無頭蒼蠅，到處去找最符合這個顏色比例的區域，推薦演算法ASMS vojirt/asms：

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

ASMS與DAT並稱「顏色雙雄」(版權所有翻版必究)，都是僅顏色特徵的演算法而且速度很快，依次是VOT2015的第20名和14名，在VOT2016分別是32名和31名(中等水平)。ASMS是VOT2015官方推薦的實時演算法，平均幀率125FPS，在經典mean-shift框架下加入了尺度估計，經典顏色直方圖特徵，加入了兩個先驗(尺度不劇變+可能偏最大)作為正則項，和反向尺度一致性檢查。作者給了C++代碼，在相關濾波和深度學習盛行的年代，還能看到mean-shift打榜還有如此高的性價比實在不容易(已淚目~~)，實測性能還不錯，如果您對生成類方法情有獨鍾，這個非常推薦您去試試。(某些演算法，如果連這個你都比不過。。天台在24樓，不謝)

判別類方法，OTB50裡面的大部分方法都是這一類，CV中的經典套路圖像特徵+機器學習，當前幀以目標區域為正樣本，背景區域為負樣本，機器學習方法訓練分類器，下一幀用訓練好的分類器找最優區域：

與生成類方法最大的區別是，分類器採用機器學習，訓練中用到了背景信息，這樣分類器就能專註區分前景和背景，所以判別類方法普遍都比生成類好。舉個例子，在訓練時告訴tracker目標80%是紅色，20%是綠色，還告訴它背景中有橘紅色，要格外注意別搞錯了，這樣的分類器知道更多信息，效果也相對更好。tracking-by-detection和檢測演算法非常相似，如經典行人檢測用HOG+SVM，Struck用到了haar+structured output SVM，跟蹤中為了尺度自適應也需要多尺度遍歷搜索，區別僅在於跟蹤演算法對特徵和在線機器學習的速度要求更高，檢測範圍和尺度更小而已。這點其實並不意外，大多數情況檢測識別演算法複雜度比較高不可能每幀都做，這時候用複雜度更低的跟蹤演算法就很合適了，只需要在跟蹤失敗(drift)或一定間隔以後再次檢測去初始化tracker就可以了。其實我就想說，FPS才TMD是最重要的指標，慢的要死的演算法可以去死了(同學別這麼偏激，速度是可以優化的)。經典判別類方法推薦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，注意和後面的DCF演算法區別，包括前面提到的那幾個，也是後面要著重介紹的。深度學習（Deep ConvNet based）類方法，因為深度學習類目前不適合落地就不瞎推薦了，可以參考Winsty的幾篇 Naiyan Wang - Home，還有VOT2015的冠軍MDNet Learning Multi-Domain Convolutional Neural Networks for Visual Tracking，以及VOT2016的冠軍TCNN http://www.votchallenge.net/vot2016/download/44_TCNN.zip，速度方面比較突出的如80FPS的SiamFC SiameseFC tracker和100FPS的GOTURN davheld/GOTURN，注意都是在GPU上。基於ResNet的SiamFC-R(ResNet)在VOT2016表現不錯，很看好後續發展，有興趣也可以去VALSE聽作者自己講解 VALSE-20160930-LucaBertinetto-Oxford-JackValmadre-Oxford-pu，至於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.

最後，深度學習END2END的強大威力在目標跟蹤方向還遠沒有發揮出來，還沒有和相關濾波類方法拉開多大差距(速度慢是天生的我不怪你，但效果總該很好吧，不然你存在的意義是什麼呢。。革命尚未成功，同志仍須努力)。另一個需要注意的問題是目標跟蹤的資料庫都沒有嚴格的訓練集和測試集，需要離線訓練的深度學習方法就要非常注意它的訓練集有沒有相似序列，而且一直到VOT2017官方才指明要限制訓練集，不能用相似序列訓練模型。

最後強力推薦兩個資源。王強 @Qiang Wang 維護的benchmark_results foolwood/benchmark_results：大量頂級方法在OTB庫上的性能對比，各種論文代碼應有盡有，大神自己C++實現並開源的CSK, KCF和DAT，還有他自己的DCFNet論文加源碼，找不著路的同學請跟緊。

@H Hakase 維護的相關濾波類資源 HakaseH/CF_benchmark_results ，詳細分類和論文代碼資源，走過路過別錯過，相關濾波類演算法非常全面，非常之用心！

(以上兩位，看到了請來我處交一下廣告費，9折優惠~~)

第三部分：相關濾波

介紹最經典的高速相關濾波類跟蹤演算法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的快速演算法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，單通道灰度特徵的複雜度是10000*log(10000)=40000，理論上也差不多，符合表格。

看代碼會發現，作者在擴展後目標區域面積較大時，會先對提取到的圖像塊做因子2的下採樣到50*50，這樣複雜度就變成了2500*log(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，推薦。

第四部分：14年的尺度自適應

VOT與OTB一樣最早都是2013年出現的，但VOT2013序列太少，第一名的PLT代碼也找不到，沒有參考價值就直接跳過了。直接到了VOT2014競賽 VOT2014 Benchmark 。這一年有25個精挑細選的序列，38個演算法，那時候深度學習的戰火還沒有燒到tracking，所以主角也只能是剛剛展露頭角就獨霸一方的CF，下面是前幾名的詳細情況：

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

其實前三名除了特徵略有差異，核心都是KCF為基礎擴展了多尺度檢測，概要如下：

尺度變化是跟蹤中比較基礎和常見的問題，前面介紹的KCF/DCF和CN都沒有尺度更新，如果目標縮小，濾波器就會學習到大量背景信息，如果目標擴大，濾波器就跟著目標局部紋理走了，這兩種情況都很可能出現非預期的結果，導致漂移和失敗。

SAMF ihpdep/samf，浙大Yang Li的工作，基於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，只用了HOG特徵，DCF用於平移位置檢測，又專門訓練類似MOSSE的相關濾波器檢測尺度變化，開創了平移濾波+尺度濾波，之後轉TPAMI做了一系列加速的版本fDSST，非常+非常+非常推薦：

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之後，他的後續論文就再沒有用過(直到最新CVPR的ECO-HC中為了加速用了fDSST)。

雖然SAMF和DSST都可以跟上普通的目標尺度變化，但SAMF只有7個尺度比較粗，而DSST有33個尺度比較精細準確；
DSST先檢測最佳平移再檢測最佳尺度，是分步最優，而SAMF是平移尺度一起檢測，是平移和尺度同時最優，而往往局部最優和全局最優是不一樣的；
DSST將跟蹤劃分為平移跟蹤和尺度跟蹤兩個問題，可以採用不同的方法和特徵，更加靈活，但需要額外訓練一個濾波器，每幀尺度檢測需要採樣33個圖像塊，之後分別計算特徵、加窗、FFT等，尺度濾波器比平移濾波器慢很多；SAMF只需要一個濾波器，不需要額外訓練和存儲，每個尺度檢測就一次提特徵和FFT，但在圖像塊較大時計算量比DSST高。

所以尺度檢測DSST並不總是比SAMF好，其實在VOT2015和VOT2016上SAMF都是超過DSST的，當然這主要是因為特徵更好，但至少說明尺度方法不差。總的來說，DSST做法非常新穎，速度更快，SAMF同樣優秀也更加準確。

DSST一定要33個尺度嗎？

DSST標配33個尺度非常非常敏感，輕易降低尺度數量，即使你增加相應步長，尺度濾波器也會完全跟不上尺度變化。關於這一點可能解釋是，訓練尺度濾波器用的是一維樣本，而且沒有循環移位，這就意味著一次訓練更新只有33個樣本，如果降低樣本數量，會造成訓練不足，分類器判別力嚴重下降，不像平移濾波器有非常多的移位樣本(個人看法歡迎交流)。總之，請不要輕易嘗試大幅降低尺度數量，如果非要用尺度濾波器33和1.02就很好。

以上就是兩種推薦的尺度檢測方法，以後簡稱為類似DSST的多尺度和類似SAMF的多尺度。如果更看重速度，加速版的fDSST，和僅3個尺度的SAMF(如VOT2014中的KCF)就是比較好的選擇；如果更看重精確，33個尺度的DSST，及7個尺度的SAMF就比較合適。

第五部分：邊界效應

接下來到了VOT2015競賽 VOT2015 Challenge | Home ，這一年有60個精挑細選的序列，62個tracker，最大看點是深度學習開始進擊tracking領域，MDNet直接拿下當年的冠軍，而結合深度特徵的相關濾波方法DeepSRDCF是第二名，主要解決邊界效應的SRDCF僅HOG特徵排在第四：

隨著VOT競賽的影響力擴大，舉辦方也是用心良苦，經典的和頂尖的齊聚一堂，百家爭鳴，多達62個tracker皇城PK，華山論劍。除了前面介紹的深度學習和相關濾波，還有結合object proposals(類物體區域檢測)的EBT(EBT：Proposal與Tracking不得不說的秘密 - 知乎專欄)排第三，Mean-Shift類顏色演算法ASMS是推薦實時演算法，還有前面提到的另一個顏色演算法DAT，而在第9的那個Struck已經不是原來的Struck了。除此之外，還能看到經典方法如OAB, STC, CMT, CT, NCC等都排在倒數位置，經典方法已經被遠遠甩在後面。

在介紹SRDCF之前，先來分析下相關濾波有什麼缺點。總體來說，相關濾波類方法對快速變形和快速運動情況的跟蹤效果不好。

快速變形主要因為CF是模板類方法。容易跟丟這個比較好理解，前面分析了相關濾波是模板類方法，如果目標快速變形，那基於HOG的梯度模板肯定就跟不上了，如果快速變色，那基於CN的顏色模板肯定也就跟不上了。這個還和模型更新策略與更新速度有關，固定學習率的線性加權更新，如果學習率太大，部分或短暫遮擋和任何檢測不準確，模型就會學習到背景信息，積累到一定程度模型跟著背景私奔了，一去不復返。如果學習率太小，目標已經變形了而模板還是那個模板，就會變得不認識目標。

快速運動主要是邊界效應(Boundary Effets)，而且邊界效應產生的錯誤樣本會造成分類器判別力不夠強，下面分訓練階段和檢測階段分別討論。

訓練階段，合成樣本降低了判別能力。如果不加餘弦窗，那麼移位樣本是長這樣的：

除了那個最原始樣本，其他樣本都是「合成」的，100*100的圖像塊，只有1/10000的樣本是真實的，這樣的樣本集根本不能拿來訓練。如果加了餘弦窗，由於圖像邊緣像素值都是0，循環移位過程中只要目標保持完整，就認為這個樣本是合理的，只有當目標中心接近邊緣時，目標跨越了邊界的那些樣本是錯誤的，這樣雖不真實但合理的樣本數量增加到了大約2/3(一維情況padding= 1)。但我們不能忘了即使這樣仍然有1/3(3000/10000)的樣本是不合理的，這些樣本會降低分類器的判別能力。再者，加餘弦窗也不是「免費的」，餘弦窗將圖像塊的邊緣區域像素全部變成0，大量過濾掉了分類器本來非常需要學習的背景信息，原本訓練時判別器能看到的背景信息就非常有限，我們還加了個餘弦窗擋住了背景，這樣進一步降低了分類器的判別力(是不是上帝在我前遮住了簾。。不是上帝，是餘弦窗)。

檢測階段，相關濾波對快速運動的目標檢測比較乏力。相關濾波訓練的圖像塊和檢測的圖像塊大小必須是一樣的，這就是說你訓練了一個100*100的濾波器，那你也只能檢測100*100的區域，如果打算通過加更大的padding來擴展檢測區域，那樣除了擴展了複雜度，並不會有什麼好處。目標運動可能是目標自身移動，或攝像機移動，按照目標在檢測區域的位置分四種情況來看：

如果目標在中心附近，檢測準確且成功。
如果目標移動到了邊界附近但還沒有出邊界，加了餘弦窗以後，部分目標像素會被過濾掉，這時候就沒法保證這裡的響應是全局最大的，而且，這時候的檢測樣本和訓練過程中的那些不合理樣本很像，所以很可能會失敗。
如果目標的一部分已經移出了這個區域，而我們還要加餘弦窗，很可能就過濾掉了僅存的目標像素，檢測失敗。
如果整個目標已經位移出了這個區域，那肯定就檢測失敗了。

以上就是邊界效應(Boundary Effets)，推薦兩個主流的解決邊界效應的方法，其中SRDCF速度比較慢，並不適合實時場合。

Martin Danelljan的SRDCF Learning Spatially Regularized Correlation Filters for Visual Tracking，主要思路：既然邊界效應發生在邊界附近，那就忽略所有移位樣本的邊界部分像素，或者說限制讓邊界附近濾波器係數接近0：

Danelljan M, Hager G, Shahbaz Khan F, et al. Learning spatially regularized correlation filters for visual tracking [C]// ICCV. 2015.

SRDCF基於DCF，類SAMF多尺度，採用更大的檢測區域(padding = 4)，同時加入空域正則化，懲罰邊界區域的濾波器係數，由於沒有閉合解，採用高斯-塞德爾方法迭代優化。檢測區域擴大(1.5-&>4)，迭代優化(破壞了閉合解)導致SRDCF只有5FP，但效果非常好是2015年的baseline。

另一種方法是Hamed Kiani提出的MOSSE改進演算法，基於灰度特徵的CFLM Correlation Filters with Limited Boundaries 和基於HOG特徵的BACF Learning Background-Aware Correlation Filters for Visual Tracking，主要思路是採用較大尺寸檢測圖像塊和較小尺寸濾波器來提高真實樣本的比例，或者說濾波器填充0以保持和檢測圖像一樣大，同樣沒有閉合解，採用ADMM迭代優化：

Kiani Galoogahi H, Sim T, Lucey S. Correlation filters with limited boundaries [C]// CVPR, 2015.
Kiani Galoogahi H, Fagg A, Lucey S. Learning Background-Aware Correlation Filters for Visual Tracking [C]// ICCV, 2017.

CFLB僅單通道灰度特徵，雖然速度比較快167FPS，但性能遠不如KCF，不推薦；最新BACF將特徵擴展為多通道HOG特徵，性能超過了SRDCF，而且速度比較快35FPS，非常推薦。

其實這兩個解決方案挺像的，都是用更大的檢測及更新圖像塊，訓練作用域比較小的相關濾波器，不同點是SRDCF的濾波器係數從中心到邊緣平滑過渡到0，而CFLM直接用0填充濾波器邊緣。

VOT2015相關濾波方面還有排在第二名，結合深度特徵的DeepSRDCF，因為深度特徵都非常慢，在CPU上別說高速，實時都到不了，雖然性能非常高，但這裡就不推薦，先跳過。

第六部分：顏色直方圖與相關濾波

VOT2016競賽 VOT2016 Challenge | Home，依然是VOT2015那60個序列，不過這次做了重新標註更加公平合理，今年有70位參賽選手，意料之中深度學習已經雄霸天下了，8個純CNN方法和6個結合深度特徵的CF方法大都名列前茅，還有一片的CF方法，最最最重要的是，良心舉辦方竟然公開了他們能拿到的38個tracker，部分tracker代碼和主頁，下載地址：VOT2016 Challenge | Trackers (以後媽媽再也不用擔心我找不到源碼了~)，注意部分是下載鏈接，部分是源碼壓縮包，部分源碼是二進位文件，好不好用一試便知，方便對比和研究，需要的趕快去試試。馬上來看競賽結果(這裡僅列舉前60個)：

高亮標出來了前面介紹過的或比較重要的方法，結合多層深度特徵的相關濾波C-COT排第一名，而CNN方法TCNN是VOT2016的冠軍，作者也是VOT2015冠軍MDNet，純顏色方法DAT和ASMS都在中等水平(其實兩種方法實測表現非常接近)，其他tracker的情況請參考論文。再來看速度，SMACF沒有公開代碼，ASMS依然那麼快，排在前10的方法中也有兩個速度比較快，分別是排第5的Staple，和其改進演算法排第9的STAPLE+，而且STAPLE+是今年的推薦實時演算法。首先恭喜Luca Bertinetto的SiamFC和Staple都表現非常不錯，然後再為大牛默哀三分鐘(VOT2016的paper原文)：

This was particularly obvious in case of SiamFC trackers, which runs orders higher than realtime (albeit on GPU), and Staple, which is realtime, but are incorrectly among the non-realtime trackers.

VOT2016竟然發生了烏龍事件，Staple在論文中CPU上是80FPS，怎麼EFO在這裡只有11？幸好公開代碼有Staple和STAPLE+，實測下來，雖然我電腦不如Luca Bertinetto大牛但Staple我也能跑76FPS，而更可笑的是，STAPLE+比Staple慢了大約7-8倍，竟然EFO高出4倍，到底怎麼回事呢？

首先看Staple的代碼，如果您直接下載Staple並設置params.visualization = 1，Staple默認調用Computer Vision System Toolbox來顯示序列圖像，而恰好如果您沒有這個工具箱，默認每幀都會用imshow(im)來顯示圖像，所以非常非常慢，而設置params.visualization = 0就跑的飛快(作者你是孫猴子派來的逗逼嗎)，建議您將顯示圖像部分代碼替換成DSST中對應部分代碼就可以正常速度運行和顯示了。

再來看STAPLE+的代碼，對Staple的改進包括額外從顏色概率圖中提取HOG特徵，特徵增加到56通道(Staple是28通道)，平移檢測額外加入了大位移光流運動估計的響應，所以才會這麼慢，而且肯定要慢很多。

所以很大可能是VOT舉辦方把Staple和STAPLE+的EFO弄反了，VOT2016的實時推薦演算法應該是排第5的Staple，相關濾波結合顏色方法，沒有深度特徵更沒有CNN，跑80FPS還能排在第五，這就是接下來主要介紹的，2016年最NIUBILITY的目標跟蹤演算法之一Staple (直接讓排在後面的一眾深度學習演算法懷疑人生)。

顏色特徵，在目標跟蹤中顏色是個非常重要的特徵，不管多少個人在一起，只要目標穿不用顏色的一幅就非常明顯。前面介紹過2014年CVPR的CN是相關濾波框架下的模板顏色方法，這裡隆重介紹統計顏色特徵方法DAT Learning, Recognition, and Surveillance @ ICG ，幀率15FPS推薦：

Possegger H, Mauthner T, Bischof H. In defense of color-based model-free tracking [C]// CVPR, 2015.

DAT統計前景目標和背景區域的顏色直方圖並歸一化，這就是前景和背景的顏色概率模型，檢測階段，貝葉斯方法判別每個像素屬於前景的概率，得到像素級顏色概率圖，再加上邊緣相似顏色物體抑制就能得到目標的區域了。

如果要用一句話介紹Luca Bertinetto(牛津大學)的Staple Staple tracker，那就是把模板特徵方法DSST(基於DCF)和統計特徵方法DAT結合：

Bertinetto L, Valmadre J, Golodetz S, et al. Staple: Complementary Learners for Real-Time Tracking [C]// CVPR, 2016.

前面分析了相關濾波模板類特徵(HOG)對快速變形和快速運動效果不好，但對運動模糊光照變化等情況比較好；而顏色統計特徵(顏色直方圖)對變形不敏感，而且不屬於相關濾波框架沒有邊界效應，快速運動當然也是沒問題的，但對光照變化和背景相似顏色不好。綜上，這兩類方法可以互補，也就是說DSST和DAT可以互補結合：

兩個框架的演算法高效無縫結合，25FPS的DSST和15FPS的DAT，而結合後速度竟然達到了80FPS。DSST框架把跟蹤劃分為兩個問題，即平移檢測和尺度檢測，DAT就加在平移檢測部分，相關濾波有一個響應圖，像素級前景概率也有一個響應圖，兩個響應圖線性加權得到最終響應圖，其他部分與DSST類似，平移濾波器、尺度濾波器和顏色概率模型都以固定學習率線性加權更新。

另一種相關濾波結合顏色概率的方法是17CVPR的CSR-DCF，提出了空域可靠性和通道可靠性，沒有深度特徵性能直逼C-COT，速度可觀13FPS：

Luke?i? A, Vojí? T, ?ehovin L, et al. Discriminative Correlation Filter with Channel and Spatial Reliability [C]// CVPR, 2017.

CSR-DCF中的空域可靠性得到的二值掩膜就類似於CFLM中的掩膜矩陣P，在這裡自適應選擇更容易跟蹤的目標區域且減小邊界效應；以往多通道特徵都是直接求和，而CSR-DCF中通道採用加權求和，而通道可靠性就是那個自適應加權係數。採用ADMM迭代優化，可以看出CSR-DCF是DAT和CFLB的結合演算法。

VOT2015相關濾波還有排第一名的C-COT(別問我第一名為什麼不是冠軍，我也不知道)，和DeepSRDCF一樣先跳過。

第七部分：long-term和跟蹤置信度

以前提到的很多CF演算法，也包括VOT競賽，都是針對short-term的跟蹤問題，即短期(shor-term)跟蹤，我們只關注短期內(如100~500幀)跟蹤是否準確。但在實際應用場合，我們希望正確跟蹤時間長一點，如幾分鐘或十幾分鐘，這就是長期(long-term)跟蹤問題。

Long-term就是希望tracker能長期正確跟蹤，我們分析了前面介紹的方法不適合這種應用場合，必須是short-term tracker + detecter配合才能實現正確的長期跟蹤。

用一句話介紹Long-term，就是給普通tracker配一個detecter，在發現跟蹤出錯的時候調用自帶detecter重新檢測並矯正tracker。

介紹CF方向一篇比較有代表性的long-term方法，Chao Ma的LCT chaoma99/lct-tracker：

Ma C, Yang X, Zhang C, et al. Long-term correlation tracking[C]// CVPR, 2015.

LCT在DSST一個平移相關濾波Rc和一個尺度相關濾波的基礎上，又加入第三個負責檢測目標置信度的相關濾波Rt，檢測模塊Online Detector是TLD中所用的隨機蔟分類器(random fern)，在代碼中改為SVM。第三個置信度濾波類似MOSSE不加padding，而且特徵也不加cosine窗，放在平移檢測之後。

如果最大響應小於第一個閾值(叫運動閾值)，說明平移檢測不可靠，調用檢測模塊重新檢測。注意，重新檢測的結果並不是都採納的，只有第二次檢測的最大響應值比第一次檢測大1.5倍時才接納，否則，依然採用平移檢測的結果。
如果最大響應大於第二個閾值(叫外觀閾值)，說明平移檢測足夠可信，這時候才以固定學習率在線更新第三個相關濾波器和隨機蔟分類器。注意，前兩個相關濾波的更新與DSST一樣，固定學習率在線每幀更新。

LCT加入檢測機制，對遮擋和出視野等情況理論上較好，速度27fps，實驗只跑了OTB-2013，跟蹤精度非常高，根據其他論文LCT在OTB-2015和 VOT上效果略差一點可能是兩個核心閾值沒有自適應，關於long-term，TLD和LCT都可以參考。

接下來介紹跟蹤置信度。跟蹤演算法需要能反映每一次跟蹤結果的可靠程度，這一點非常重要，不然就可能造成跟丟了還不知道的情況。生成類(generative)方法有相似性度量函數，判別類(discriminative)方法有機器學習方法的分類概率。有兩種指標可以反映相關濾波類方法的跟蹤置信度：前面見過的最大響應值，和沒見過的響應模式，或者綜合反映這兩點的指標。

LMCF(MM Wang的目標跟蹤專欄：目標跟蹤演算法 - 知乎專欄 )提出了多峰檢測和高置信度更新：

Wang M, Liu Y, Huang Z. Large Margin Object Tracking with Circulant Feature Maps [C]// CVPR, 2017.

高置信度更新，只有在跟蹤置信度比較高的時候才更新跟蹤模型，避免目標模型被污染，同時提升速度。第一個置信度指標是最大響應分數Fmax，就是最大響應值(Staple和LCT中都有提到)。第二個置信度指標是平均峰值相關能量(average peak-to correlation energy, APCE)，反應響應圖的波動程度和檢測目標的置信水平，這個(可能)是目前最好的指標，推薦：

跟蹤置信度指標還有，MOSSE中的峰值旁瓣比(Peak to Sidelobe Ratio, PSR)，由相關濾波峰值，與11*11峰值窗口以外旁瓣的均值與標準差計算得到，推薦：

還有CSR-DCF的空域可靠性，也用了兩個類似指標反映通道可靠性，第一個指標也是每個通道的最大響應峰值，就是Fmax，第二個指標是響應圖中第二和第一主模式之間的比率，反映每個通道響應中主模式的表現力，但需要先做極大值檢測：

第八部分：卷積特徵

最後這部分是Martin Danelljan的專場，主要介紹他的一些列工作，尤其是結合深度特徵的相關濾波方法，代碼都在他主頁Visual Tracking，就不一一貼出了。

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

在CN中提出了非常重要的多通道顏色特徵Color Names，用於CSK框架取得非常好得效果，還提出了加速演算法CN2，通過類PCA的自適應降維方法，對特徵通道數量降維(10 -&> 2)，平滑項增加跨越不同特徵子空間時的代價，也就是PCA中的協方差矩陣線性更新防止降維矩陣變化太大。

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

DSST是VOT2014的第一名，開創了平移濾波+尺度濾波的方式。在fDSST中對DSST進行加速，PCA方法將平移濾波HOG特徵的通道降維(31 -&> 18)，QR方法將尺度濾波器~1000*17的特徵降維到17*17，最後用三角插值(頻域插值)將尺度數量從17插值到33以獲得更精確的尺度定位。

SRDCF是VOT2015的第四名，為了減輕邊界效應擴大檢測區域，優化目標增加了空間約束項，用高斯-塞德爾方法迭代優化，並用牛頓法迭代優化平移檢測的子網格精確目標定位。

Danelljan M, Hager G, Shahbaz Khan F, et al. Adaptive decontamination of the training set: A unified formulation for discriminative visual tracking [C]// CVPR, 2016.

SRDCFdecon在SRDCF的基礎上，改進了樣本和學習率問題。以前的相關濾波都是固定學習率線性加權更新模型，雖然這樣比較簡單不用保存以前樣本，但在定位不準確、遮擋、背景擾動等情況會污染模型導致漂移。SRDCFdecon選擇保存以往樣本(圖像塊包括正，負樣本)，在優化目標函數中添加樣本權重參數和正則項，採用交替凸搜索，首先固定樣本權重，高斯-塞德爾方法迭代優化模型參數，然後固定模型參數，凸二次規劃方法優化樣本權重。

Danelljan M, Hager G, Shahbaz Khan F, et al. Convolutional features for correlation filter based visual tracking [C]// ICCVW, 2015.

DeepSRDCF是VOT2015的第二名，將SRDCF中的HOG特徵替換為CNN中單層卷積層的深度特徵(也就是卷積網路的激活值)，效果有了極大提升。這裡用imagenet-vgg-2048 network，VGG網路的遷移能力比較強，而且MatConvNet就是VGG組的，MATLAB調用非常方便。論文還測試了不同卷積層在目標跟蹤任務中的表現：

第1層表現最好，第2和第5次之。由於卷積層數越高語義信息越多，但紋理細節越少，從1到4層越來越差的原因之一就是特徵圖的解析度越來越低，但第5層反而很高，是因為包括完整的語義信息，判別力比較強(本來就是用來做識別的)。

注意區分這裡的深度特徵和基於深度學習的方法，深度特徵來自ImageNet上預訓練的圖像分類網路，沒有fine-turn這一過程，不存在過擬合的問題。而基於深度學習的方法大多需要在跟蹤序列上end-to-end訓練或fine-turn，如果樣本數量和多樣性有限就很可能過擬合。

Ma C, Huang J B, Yang X, et al. Hierarchical convolutional features for visual tracking [C]// ICCV, 2015.

值得一提的還有Chao Ma的HCF，結合多層卷積特徵提升效果，用了VGG19的Conv5-4, Conv4-4和Conv3-4的激活值作為特徵，所有特徵都縮放到圖像塊解析度，雖然按照論文應該是由粗到細確定目標，但代碼中比較直接，三種卷積層的響應以固定權值1, 0.5, 0.02線性加權作為最終響應。雖然用了多層卷積特徵，但沒有關注邊界效應而且線性加權的方式過於簡單，HCF在VOT2016僅排在28名（單層卷積深度特徵的DeepSRDCF是第13名）。

Danelljan M, Robinson A, Khan F S, et al. Beyond correlation filters: Learning continuous convolution operators for visual tracking [C]// ECCV, 2016.

C-COT是VOT2016的第一名，綜合了SRDCF的空域正則化和SRDCFdecon的自適應樣本權重，還將DeepSRDCF的單層卷積的深度特徵擴展為多成卷積的深度特徵（VGG第1和5層），為了應對不同卷積層解析度不同的問題，提出了連續空間域插值轉換操作，在訓練之前通過頻域隱式插值將特徵圖插值到連續空域，方便集成多解析度特徵圖，並且保持定位的高精度。目標函數通過共軛梯度下降方法迭代優化，比高斯-塞德爾方法要快，自適應樣本權值直接採用先驗權值，沒有交替凸優化過程，檢測中用牛頓法迭代優化目標位置。

注意以上SRDCF, SRDCFdecon，DeepSRDCF，C-COT都無法實時，這一系列工作雖然效果越來越好，但也越來越複雜，在相關濾波越來越慢失去速度優勢的時候，Martin Danelljan在2017CVPR的ECO來了一腳急剎車，大神來告訴我們什麼叫又好又快，不忘初心：

Danelljan M, Bhat G, Khan F S, et al. ECO: Efficient Convolution Operators for Tracking [C]// CVPR, 2017.

ECO是C-COT的加速版，從模型大小、樣本集大小和更新策略三個方便加速，速度比C-COT提升了20倍，加量還減價，EAO提升了13.3%，最最最厲害的是， hand-crafted features的ECO-HC有60FPS。。吹完了，來看看具體做法。

第一減少模型參數，定義了factorized convolution operator(分解卷積操作)，效果類似PCA，用PCA初始化，然後僅在第一幀優化這個降維矩陣，以後幀都直接用，簡單來說就是有監督降維，深度特徵時模型參數減少了80%。

第二減少樣本數量， compact generative model(緊湊的樣本集生成模型)，採用Gaussian Mixture Model (GMM)合併相似樣本，建立更具代表性和多樣性的樣本集，需要保存和優化的樣本集數量降到C-COT的1/8。

第三改變更新策略，sparser updating scheme(稀疏更新策略)，每隔5幀做一次優化更新模型參數，不但提高了演算法速度，而且提高了對突變，遮擋等情況的穩定性。但樣本集是每幀都更新的，稀疏更新並不會錯過間隔期的樣本變化信息。

ECO的成功當然還有很多細節，而且有些我也看的不是很懂，總之很厲害就是了。。ECO實驗跑了四個庫(VOT2016, UAV123, OTB-2015, and TempleColor)都是第一，而且沒有過擬合的問題，僅性能來說ECO是目前最好的相關濾波演算法，也有可能是最好的目標跟蹤演算法。hand-crafted features版本的ECO-HC，降維部分原來HOG+CN的42維特徵降到13維，其他部分類似，實驗結果ECO-HC超過了大部分深度學習方法，而且論文給出速度是CPU上60FPS。

最後是來自Luca Bertinetto的CFNet End-to-end representation learning for Correlation Filter based tracking，除了上面介紹的相關濾波結合深度特徵，相關濾波也可以end-to-end方式在CNN中訓練了：

Valmadre J, Bertinetto L, Henriques J F, et al. End-to-end representation learning for Correlation Filter based tracking [C]// CVPR, 2017.

在SiamFC的基礎上，將相關濾波也作為CNN中的一層，最重要的是cf層的前向傳播和反向傳播公式推導，兩層卷積層的CFNet在GPU上是75FPS，綜合表現並沒有很多驚艷，可能是難以處理CF層的邊界效應吧，持觀望態度。

第九部分：2017年CVPR和ICCV結果

下面是CVPR 2017的目標跟蹤演算法結果：可能MD大神想說，一個能打的都沒有！

https://github.com/martin-danelljan/ECO (二維碼自動識別)

仿照上面的表格，整理了ICCV 2017的相關論文結果對比ECO：哎，還是一個能打的都沒有！

第十部分：大牛推薦

湊個數，目前相關濾波方向貢獻最多的是以下兩個組(有創新有代碼)：

牛津大學：Joao F. Henriques和Luca Bertinetto，代表：CSK, KCF/DCF, Staple, CFNet (其他SiamFC, Learnet).

林雪平大學：Martin Danelljan，代表：CN, DSST, SRDCF, DeepSRDCF, SRDCFdecon, C-COT, ECO.

國內也有很多高校的優秀工作就不一一列舉了。

我大三（09年）開始做跟蹤方面的事情，到畢業工作之後兩年陸續還會做一些跟蹤相關的問題。

跟蹤是一個很混亂的方向。

比如TLD、CT、Struct這些效果不錯的Tracker其實都不是單純的Tracker了。09年的時候我記得比較流行的是Particle Filtering，或者一些MeanShift/CamShift的變形，比如特徵變了，比如對問題的假設變了。

後來突然出現一些tracking by detection的方法，之前的很多朋友就覺得這是耍流氓。比如TLD，嚴格的跟蹤演算法也許只是裡面的Forward/Backward Opitcal Flow的部分，但是效果很Impressive，所以不管怎樣，一下就火了。

之後所謂的跟蹤就不再是一個傳統的跟蹤問題，而是一個綜合的工程問題。online learning，random projection ，sparse learning的東西都加進來，大家其實到底是在做跟蹤還是在做檢測或者online learning，其實已經不重要，因為衡量的標準是你在某些public dataset上的精度。

但這些對實際的項目有沒有幫助呢？

這是個很有意思的地方，在很多時候，我們之所以需要跟蹤演算法，是因為我們的檢測演算法很慢，跟蹤很快。基本上當前排名前幾的跟蹤演算法都很難用在這樣的情況下，因為你實際的速度已經太慢了，比如TLD，CT，還有Struct，如果目標超過十個，基本上就炸了。況且還有些跟蹤演算法自己drift掉了也不知道，比如第一版本的CT是無法處理drift的問題的，TLD是可以的，究其原因還是因為檢測演算法比較魯棒啊……

實際中我覺得速度極快，實現也簡單的純跟蹤演算法居然是NCC和Overlap。

NCC很簡單，這個是對點進行的，對於區域也有很多變種，網上有一些相關的資源。

Overlap是我取的名字，一般用在視頻裡面，假如你的攝像頭是靜止的，背景建模之後出來的前景可以是一個一個的blob，對相鄰兩幀的blob檢測是否Overlap就可以得到track。在一些真實場景下，這個演算法是非常有效的。關於背景template的問題在真實的視頻裡面也是很好解決的。

坐在電腦前面調試代碼tuning 各種閾值讓跟蹤演算法在某一個視頻幀下面不要drift的事情我是再也不想幹了。

以上說的跟蹤是指給定一個視頻幀中的物體區域，然後跟蹤住這個物體。其他地方也有一些跟蹤，比如SLAM里，但是問題域不一樣。略去。

歡迎來看看我們最近的打臉文：http://arxiv.org/abs/1504.06055 HOG+LR 輕輕鬆超過90%paper的結果

Tracking這個坑太爛了，比Detection落後至少5年以上。我就不吐槽了

寫的非常不錯。不過我想解釋一下我的那兩個方法CT和STC，這兩個方法都是在benchmark 出來之前做的，其中STC雖然發表於ECCV14，但是其實實在12年就做出來，只是一直沒有中，偶然中了ECCV14. 確實在benchmark出現之後，單純從benchmark上的性能來看結果是已經落後了，但是說句實在的，tracking這個方向已經偏離實際越來越遠了，這裡面benchmark的功勞很大，不刷benchmark已經無法發論文了，但是刷上去benchmark的性能又有何意義呢？無非是為了刷而刷。

benchmark 2015版：Visual Tracker Benchmark 不過這些演算法都比較新要看老的話主要是06年這篇paper http://crcv.ucf.edu/papers/Object%20Tracking.pdf 和09年有一篇暫時忘記paper名字了
古老的方法比如optical flow，kalman filter(後面的particle filter)……了解不多不瞎扯了

目前tracking主要是兩種，discriminative 和 generative，當然也有combine兩個的比如SCM。你提到的都是前者，就是演算法裡面基本有一個classifier可以分辨要追蹤的物體。這類除了你說的最近比較火的還有速度極佔優勢的CSK（後來進化成KCF/DCF了）
另一種generative的方法，大致就是用模版（或者sparse code）抽一堆feature，按距離函數來匹配。L1，ASLA，LOT，MTT都是。

最近才開始了解tracking，所以說得可能並不是很對，僅供參考

KCF你值得擁有！
-------------------------------------------------------
在上課，下課回去吹！
-------------------------------------------------------
KCF全稱，相關濾波kernel correlation filter
文章出處 http://arxiv.org/abs/1404.7584
這個是我現在主要看的演算法，目標跟蹤的演算法是有很多了，如果想一個一個全部研究的話，可以在這裡Visual Tracker Benchmark
Benchmark，包含了現在流行的演算法，並進行了分析，這就是目標跟蹤演算法的一個綜述！
——————————————————————————————————————————
2016年11月14日補充
KCF主要的特點就是速度快，主要原因是因為在使用了輪換矩陣和快速傅里葉變換。輪轉矩陣可以經過變化之後為對角矩陣，傅里葉變化的話可以做按元素乘，把運算降低了好幾個量級。之後使用嶺回歸，文中對損失最小化的求取使用的是L2正則化來計算Loss。
——————————————————————————————————————————
太多的細節需要朋友們自己去研究，我能說的也就是這個演算法的核心思想，代碼的話還是需要自己去研究。
Jo?o F. Henriques這裡可以下載代碼。大家有什麼不懂的可以私信我或者直接評論區，我所知道的都會給大家解答的~~~
———————————————————————————————————————————
2016年12月8號
近段時間一直有朋友問我關於一些細節的東西，我正在思考怎麼把這些東西寫成一個文檔或者博客的形式，等我寫出來之後會在這裡公布一下地址的。

博客地址：http://blog.csdn.net/crazyice521/article/details/53525366
大家可以看看，算是一個對論文基本的梳理了解，並沒有涉及公式和細節講解的部分，沒有什麼不能理解的，就像我在博客中說的一樣，按照我這個順序看完KCF基本上你能對這個有個大概的了解，但是跟蹤演算法博大精深，有待大家進一步的研究。有什麼問題歡迎大家隨時諮詢~~~

之前寫過一些tracking的東西，把最近看的比較流量的演算法寫一下：個人覺得值得仔細研究的tracking演算法包括：

Mean-shift, Particle Filter, Ensemble Tracking

TLD, 壓縮感知跟蹤，KCF Tracker及其改進

速度慢於50fps的跟蹤演算法就沒有必要搞了，基本上沒有可能做到實時的。

鑒於很多朋友問另一篇，之前寫的比較早，複製過來放到一起，供大家參考。（有些圖片和文檔沒辦法一併複製過來，請見諒）

Trakcing Algorithms Papers for Survey

2010_Adaptive Feature Extraction with Haar-like Features for Visual Tracking.pdf

Haar-like features to replace HOG in ensemble tracking can dealing with appearance changes, illumination variations and occlusions

http://note.youdao.com/yws/res/2749/BEE69D4BAA0140F3A304F65AD4C91E0A特徵數量p和特徵尺寸s都根據需要改變可以參考

ECCV2002_Color-based Probabilistic Tracking.pdf

Extension to multi-part color modeling(a gross spatial layout)Color Model N = Nh*Ns + Nv bins HistogramHSV color space (decouple chromatic information from shading layout)Large motions, important motion blur, dramatic shape changes, partial occlusionsBackground ModelingColor Model 和 Background Model 也許可以參考

ECCV2008_Semi-Supervised On-line Boosting for Robust Tracking.pdf (好文章，有時間仔細研讀)

Drifting Problem for faces

CVPR2007_Fast keypoint recognition in ten lines of code.pdf (pixel pairs)

PAMI2004_The template update problem.pdf (template trackers)

CVPR2007_Learning features for tracking.pdf (geometric model)Labeled data (or a previously trained model) is used as a prior and the data collected during tracking as unlabeled samplesSemi-supervised learning usedBoth labedata X = XL led XL and unlabeled XUand XU論文中提到的關於解決Drifting和Ocllusion問題的部分值得參考和論文的閱讀
Human Face Detection and Tracking using Skin Color Modeling and Connected Component Operators.pdfSkin color analysis and connected operatorsYCbCr Color Space and CbCr-Planehttp://note.youdao.com/yws/res/1391/E77BF5A9CD224975B8670E9598179FD0Skin Probability ImageCompactness, Solidity and Orientation可以參考，關鍵在於分析ATM應用場景中的YCbCr Color Model是否滿足，至於Connected Component Operators可以再仔細考慮

ICCV2009_Robust Visual Tracking using L1 Minimization.pdfhttp://note.youdao.com/yws/res/1398/2BBBF9E9B9CF40B0A4BF14D77ABBC25Fhttp://note.youdao.com/yws/res/1396/E203595B69B04F7AB2625F32DBFBF3E7在其他地方沒準兒可以應用

ICIP2012_Active Drift Correction Template Tracking Algorithm.pdf暫時未發現有用處
IJCV2007_Incremental Learning for Robust Visual Tracking.pdfIncrementally learns a low-dimensional subspace representationA method for correctly updating the sample meanA forgetting factor to ensure less modelling power is expended fitting older observationsThe subspace representation provides a compact notion of the 「thing」 being tracked rather than treating the target as a set of independent pixels有些東西沒有理解，但總體來說是一個很好的演算法，需要進一步學習
NeuCom2011_Recent advances and trends in visual tracking a review.pdf

好文，仔細學習
CVPR2006_TR2005_Covariance Tracking using Model Update Based on Lie Algebra.pdf好文，Covariance Matrix是一種非常好的對所跟蹤物體的描述Lie Algebra需要仔細研究，沒看明白性質Covariance Matrix有著很好的特性如：Rotation Invariant演算法測試對雜訊和關照變化有很好的表現
Using Segmentation to Verify Object Hypotheses.pdfhttp://note.youdao.com/yws/res/1421/75DF165348BD420CA799CDB46215D6D4http://note.youdao.com/yws/res/1423/46B02B63BB6D4C54BA5DA80E7D3FE700A good way for us to use prior information of shape

CMU-RI-RT2003_On-line Selection of Discriminative Tracking Features.pdf

A good way to do on-line selection of features可以把這種方法融合到Ensemble Tracking當中非常值得參考

CVPR2007_Tracking in Low Frame Rate Video A Cascade Particle Filter with Discriminative Observers of Different Lifespans.pdf

如果需要在低的幀率或者有劇烈運動情況下可以考慮演算法中引入Multi-Obeserver(detector)的方法可以參考，非常不錯需要詳細了解基本的PF的原理，結合方式也比較新穎

CVPR2007_Capturing People in Surveillance Video.pdfLearning Adaptive features沒有看懂Key Frame Selection的方法非常不錯，可以參考；尤其是加入的Person Classifier部分
備註1：在ZenoIntel關於人臉跟蹤的報告http://note.youdao.com/yws/res/1604/9D7C5F6C4F6D4C37AA996BD7B1A5C972http://note.youdao.com/yws/res/1605/AEC7123B20DC4356973CFD1B19021EE9http://note.youdao.com/yws/res/1825/0A5A1AFF6B0D4B5C9FA3A26A7D1FDA3C

備註2：關於視頻跟蹤技術的一個總結目前比較流行的跟蹤演算法，每一個需要仔細閱讀並了解原理，常用演算法需要能夠Coding實現。
1、Standard mean shift tracker（MS）CVPR-00「Real-time tracking of non-rigid objects using mean shift」

2、Mean shift tracker（MS）PAMI-03「Kernel-based object tracking」

3、Covariance tracker（CV）CVPR-06「Covariance tracking using model update based on lie algebra」

好文，Covariance Matrix是一種非常好的對所跟蹤物體的描述，Covariance Matrix有著很好的特性如：Rotation Invariant，仔細考慮如何構造好的Covariance Matrix會很有好處。Lie algebra需要仔細研究，方能夠明白如何進行更新的。總體來說，演算法測試對雜訊和關照變化有很好的表現。

4、Appearance adaptive particle tracker（AAPF）TIP-04「Visual Tracking and recognition using appearance-adaptive models in particle filters」

5、Ensemble tracker（ES）CVPR-05「Ensemble Tracking」

Ensemble Tracking的核心在於在線學習，能夠應對目標非顯著的變化；但演算法過多的依賴於顏色（R, G, B）信息，論文中使用到的HOG信息個人認為是雞肋，沒有多少實際的用處...可以考慮對顏色空間進行變化的方式。

基本原理是利用tracking的目標矩形框，以及他外邊的矩形框構成特徵向量的矩陣A，使用最小二乘A*x = B構造分類器，每次構造分類器之後更新樣本權重然後再次訓練，最後形成Boosting結構。

在Confidence Map上面使用Mean-shift演算法一定程度上解決掉了漂移的問題，但容易掉入局部最優解。

對Ensemble Tracking的幾個改進：

6、L1 tracker ICCV-09「Robust Visual Tracking using L1 minimization」

7、Visual tracker sampler（VTS）ICCV-11「Tracking by sampling trackers」

8、MCMC-method PAMI-05「MCMC-based particle filtering for tracking a variable number of interacting targets」

9、Incremental Visual Tracking（IVT）IJCV-08「Incremental Learning for robust visual tracking」

10、Multiple Instance Learning（MIL）CVPR-09「Visual tracking with online multiple instance learning」

11、Visual Tracking Decomposition（VTD）CVPR-10「Visual Tracking Decomposition」

12、Frag tracking CVPR-06「Robust fragments-based tracking using the integral histogram」

13、WSL tracker PAMI-03「Robust online appearance models for visual tracking」

14、TLD tracker PAMI-12「Tracking-Learning-Detection」

關於TLD跟蹤演算法的理解，可以參考：http://blog.csdn.net/zouxy09/article/details/7893011

15、Online boosting BMVC-06「Real-time Tracking via On-line Boosting」

16、Semi-boost tracker ECCV-08「Semi-Supervised On-line Boosting for Robust Tracking」

一篇最新的Tracking演算法survey的文章：http://note.youdao.com/yws/res/11486/FB8321B79A2542A5A86A49A40386A9C5從實驗效果的角度來做survey，可以仔細參考論文。
The End

可以參考這個有道雲筆記的分享鏈接：

http://note.youdao.com/noteshare?id=e8b09b17964bfac51b6e2161ebeb759d

貌似有人把跟蹤(tracking)和計算機視覺中的目標跟蹤搞混了。

前者更偏向數學，是對狀態空間在時間上的變化進行建模，並對下一時刻的狀態進行預測的演算法。例如卡爾曼濾波，粒子濾波等。

後者則偏嚮應用，給定視頻中第一幀的某個物體的框，由演算法給出後續幀中該物體的位置。最初是為了解決檢測演算法速度較慢的問題，後來慢慢自成一系。因為變成了應用問題，所以演算法更加複雜，通常由好幾個模塊組成，其中也包括數學上的tracking演算法，還有提取特徵，在線分類器等步驟。

在自成一系之後，目標跟蹤實際上就變成了利用之前幾幀的物體狀態(旋轉角度，尺度)，對下一幀的物體檢測進行約束(剪枝)的問題了。沒錯，它又變回物體檢測演算法了，但卻人為地把首幀得到目標框的那步剝離出來。在各界都在努力建立end-to-end系統的時候，目標跟蹤卻只去研究一個子問題，選擇性無視"第一幀的框是怎麼來的"的問題。我想，目標跟蹤的下一步應該是成為目標檢測的一步，充分利用物體特性，建成一個視頻中目標檢測的大系統，而不是自成體系，只在自己的小圈子裡做研究。

答主並非是做目標跟蹤方向研究的，但導師在博士期間是做的這個方向，因此也跟著有所涉獵。先匿了，如果有說的不對的地方，還請指正。

deep learning tracking 效果不錯，就是太慢了，目前難實時。@Naiyan Wang

既然問的經典演算法，那就幾乎可以毫不猶豫地回答camshift、meanshift、Kalman filter、Optical flow之類的了
凡是低版本的OpenCV裡面提供的函數，肯定用的都是最基礎或者最經典的演算法了。
即使有些過時，但是作為ad hoc方案或者最底層的處理演算法還是不錯的。

舉兩個我自己做過的例子
Kalman filter：
原本是想估算下雲的速度，無意中發現了一架戰鬥機。。。紅圈裡面的
出現

中途

飛離

Optical flow追蹤車輛：

追蹤綠色區域也就是四個路口的車輛通過情況並計數。
主要追蹤演算法就是optical flow
當然preprocessing以及其他輔助演算法也是需要的。
左圖就是背景抽離＋區塊融合的中間效果。
右圖是實時追蹤的效果。

MIL,SCM,DCF,KCF,l1APG,等等好多。你可以看一下Wuyi的online benchmark那篇論文，裡面講了好多tracking的演算法的對比~

particle filter不應該是最經典跟蹤演算法之一嗎

TLD已經是5年前的方法了吧，在跟蹤精度和速度上都遠遠比不上近兩年的方法。從13年的CVPR出來那個benchmark之後，這兩三年object tracking的發展是飛速的，大家有了公認的可以比較的benchmark和指標，就會推動這個領域的發展。
目前效果好的主要兩大類吧，一種基於CNN，一種基於correlation filter，的確效果很不錯，但是前者受硬體限制，也受速度限制，後者更輕量級，效果和速度也很贊。
入tracking坑快一年了，大牛們速度驚人，這兩年發展很迅速。

看了大家的回答，感覺受益匪淺啊。我現在的論文題目就是目標跟蹤相關的，也查閱搜索了一些資料，個人看法，其實目標檢測與跟蹤是不相同的，檢測跟識別差不多，重在找到目標，而跟蹤是指找到目標後進行連續不斷的搜索達到跟蹤目的。近幾年比較火的好像就是在TLD基礎上的一些改進，不過對於多目標的跟蹤還有待於大家發展研究。

先扯兩句占著坑。cv方向的看幾個頂會就知道現在大牛們都在做什麼了。tracking不光是發展緩慢，如naiyan大神所說落後detection很多，而且很雞肋，沒有直接的應用方向（本人就是做tracking這個方向的，這不是噴，是無奈當初選錯了坑）。回答樓主問題吧，不考慮用deep learning的tracking，現在最主流的方法是基於correlation filter（就是前面有人提到的kcf），這個必成經典。今年cvpr和iccv都有至少3篇文章吧，Tao Dacheng老師有一個綜述：http://arxiv.org/pdf/1509.05520.pdf。從這類方法在benchmark上的測試結果看，feature才是王道啊，換個特徵或者搞幾個特徵融合一下性能立馬上去了。
有時間再更新吧。知乎首答。

看到上面有人已經提到了discriminative 和 generative兩種處理跟蹤的思路，分別推薦兩篇經典的兩個方向上對應的論文："Incremental Learning for Robust Visual Tracking"和"Visual Tracking with Online Multiple Instance Learning"。這兩篇論文提出的IVT跟蹤演算法和MIL跟蹤演算法分別成為generative tracking和discriminative tracking方面的代表作。後續l1-tracker，CT等演算法都在遵循這兩篇文章定下的大致處理框架。
另外推薦CVPR 2013的文章"Online object tracking: A benchmark"，裡面除了對主流跟蹤演算法性能進行比較外，還有對眾多的演算法進行分類，可以更系統的了解跟蹤界的研究狀況。

當然如果非要說視覺跟蹤界最經典的最有用的，那必是particle filter無疑了~~

1. 上了一學期的Computer Vision，關於視覺相關的Tracking演算法只記得第一個就提到了Optical flow，通過視頻幀與幀之間的像素點對比來計算移動的物體。
2. 那位上CV課的老師自己創造了一套Tracking演算法，叫做Motion History Image。如圖所示

3. 然後當年考試的最後一道題目就是「你們知道誰發明了Motion History Image演算法嗎？」
4. 我整張卷子答得很一般，但是最後那題答對了，於是拿了A

我的研究方向就是目標跟蹤，目前比較流行的是相關濾波演算法的跟蹤 kcf及其各種改進版。如果應用於工業的話建議看下tld和光流跟蹤方面的演算法，tld有redetection功能是目前工業界應用最廣的演算法
現在深度學習已經攻佔了這個領域，精度前兩位的演算法都是基於深度學習的。

單目標，無分割:
oab, semib, fct, ivt, mil, vtd, df, tld, l1t, mtt, struck, apg, frag, vts
手機打字，著名的暫時想到這些，有贊再繼續補充~
⊙﹏⊙

Tracking 跟視覺目標跟蹤的確是兩個不同的問題，前者致力於解決測量和關聯的不確定性。考慮到的場景為雷達檢報，當然擴展目標跟蹤的場景為激光雷達，與視頻類似。
後者側重於視頻幀中物體的跟蹤。
儘管傳統的前者的諸多演算法如RFS能應用在後者上，但後者似乎已發展出如TLD之類的自成體系的高效演算法，不知道說的對不對。