首發——Large Margin Object Tracking with Circulant Feature Maps

01-27

作者：和傻牛一起闖天下

著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。

歡迎各位對目標跟蹤領域有所體會或是有所心得的朋友投稿。

---------------------------------------------------------LMCF--------------------------------------------------------

文章鏈接：Large Margin Object Tracking with Circulant Feature Maps

LMCF(HOG+CN) and DeepLMCF(CNN) OTB100,OTB50結果，歡迎下載比較：

Download password: 7q1g

終於有機會在專欄介紹一下自己的工作Large Margin Object Tracking with Circulant Feature Maps （LMCF），歡迎大家討論、拍磚。

在Tracking這個領域，我覺得可以分成兩大類，第一類主要關注效果的提升，比如MDNet，TCNN，他們確實把效果做的很好，在數據集上的結果刷的很高，但是速度非常慢，無法滿足實時性要求。另一類則比較關注跟蹤速度，比如Staple，GOTURN。當然了，在保證的速度的同時也要保證效果。我之前比較關注第二類，主要是考慮到跟蹤的實時性應該是第一考慮要素，在此基礎上做了LMCF，比較幸運地被CVPR 2017接收。目前正在思考第一類工作，並思考如何將這兩類更好地結合。本篇文章主要還是在介紹我們LMCF的工作。

1. Motivation

1.1 整個演算法思路： 結構化SVM與傳統SVM相比有著強大的判別力，而相關濾波有著速度上驚人的優勢，是否能夠結合這兩者，得到一種既高速又高效的跟蹤演算法呢？

在相關濾波（KCF [1]）或者說它的前身CSK出來之前（當然最早用相關濾波的是MOSSE [2]），結構化SVM（Struck [3]（2011 ICCV））是一種效果很好的跟蹤演算法，主要是由於其強大的判別特性（Discrimination）。Struck用Structured output SVM作為分類器，也就是結構化SVM。這是一種輸出空間可以是任意的複雜形式的SVM分類器，比如說序列、樹等。在Struck中，輸出空間是目標相對於上一幀的平移位置信息（ $Delta$ x, $Delta$ y），確實在當時取得了非常好的效果。

但是由於在求解結構化SVM時計算複雜度較高，為了跟蹤的實時性，Struck只能用簡單的Haar特徵來表示目標，採樣的數量也比較稀疏。即便如此，Struck速度還是很慢，大概10FPS左右。但是結構化SVM是一個很強的判別器，在Struck提出時，其跟蹤效果可以說是當時最佳的。

在基於相關濾波(Correlation Filter)演算法出現之後，通過循環採樣大大增加了樣本數量，為一直以來困擾跟蹤領域的稀疏採樣問題提供了新的解決思路，並且可以用快速傅里葉變換FFT快速求解，因此可以在保證速度的前提下用一些維度較高的特徵來做跟蹤，比如KCF用到了HOG特徵。KCF用簡單的嶺回歸作為分類器，但是由於用到了高維的HOG特徵以及稠密採樣，使得它的效果還是非常好的，並且速度在170FPS左右，這也使得KCF變成了大量演算法的baseline。

到這裡就出現了LMCF的第一個最重要的motivation了，我們想用循環矩陣來突破結構化SVM的稀疏採樣問題，更想藉助CF來突破結構化SVM的跟蹤速度。

1.2 針對前向跟蹤：多峰前向檢測。這一點是用來解決相似物體干擾的。在目標周圍有特徵相似的干擾物體時，響應圖會有多個峰值，且最高的那一個有可能是干擾物體的，這時候可能就會引起誤判。

1.3 針對模型更新：如何判斷跟蹤器跟蹤的不好，或者說如何判斷當前幀出現了遮擋、甚至目標丟失？一旦能夠判斷這一點，模型更新的準確性就可以有較大提升。

先前做了關於KCF的大量實驗，我們觀察到KCF的響應圖（response map）。在跟蹤準確的時候是一個峰值很明顯，接近理想的二維高斯分布圖，如圖一的第一行所示。而在跟蹤的不好的情況中，尤其是遮擋、丟失、模糊等，響應圖會劇烈振蕩，如圖一第二行所示。因此我們提出了一種新的判據來判斷是否出現了振蕩，當判斷出現振蕩時，不進行模型的更新。這個判據的初始版本是我用在另一篇做機器人跟蹤的文章中，Real-time 3D Human Tracking for Mobile Robots with Multisensors (ICRA 2017)。

圖一：遮擋

2. LMCF Algorithm

2.1 問題描述

在LMCF中，我們的分類器是一個結構化SVM，循環採樣的目標框作為訓練樣本，因此輸出空間 $Y = left{ {left. {left( {w,h} right)} right|w in left{ {0,...,W - 1} right},h in left{ {0,...,H - 1} right}} right}$ ，其中 $W,H$ 分別是目標的寬、高。輸入空間是一個與目標框成比例的圖像塊 $xin X$ 。輸入-輸出對即為 $left( {{bf{x}},{{bf{y}}_{w,h}}} right)$ ， ${{bf{y}}_{w,h}} in Y$ 表示循環位移量， $x$ 表示以此為中心的圖像塊， $Psi left( {{bf{x}},{{bf{y}}_{w,h}}} right)$ 為對應的聯合特徵圖（joint feature map）。用來衡量 $left( {{bf{x}},{{bf{y}}_{w,h}}} right)$ 為目標的可能性的函數 $F:X times Y to mathbb{{R}}$ 定義為線性形式 $Fleft( {{bf{x}},{bf{y}};{bf{w}}} right) = leftlangle {{bf{w}},Psi left( {{bf{x}},{bf{y}}} right)} rightrangle$ ，那麼跟蹤的目標函數為：

$fleft( {{bf{x}};{bf{w}}} right) = mathop {arg max }limits_{{bf{y}} in Y} Fleft( {{bf{x}},{bf{y}};{bf{w}}} right)$ (1)

為了求解 $bf{w}$ ，我們的優化目標是這樣的：

$&mathop {min }limits_{bf{w}} frac{1}{2}{left| {bf{w}} right|^2} + Csumlimits_{w = 1}^{W - 1} {sumlimits_{h = 1}^{H - 1} {xi _{w,h}^2} } &{text{s}}{text{.t}}{text{.}}forall w,forall h,forall {{bf{y}}_{w,h}} in Ybackslash {{bf{y}}_{0,0}}: &Fleft( {{{bf{x}}},{{bf{y}}_{0,0}};{bf{w}}} right) - Fleft( {{{bf{x}}},{{bf{y}}_{w,h}};{bf{w}}} right) geqslant sqrt {Delta left( {{{bf{y}}_{0,0}},{{bf{y}}_{w,h}}} right)} - {xi _{w,h}}$ （2）

其中 $Delta left( {{{bf{y}}_{0,0}},{{bf{y}}_{w,h}}} right)$ 是衡量預測為 ${{bf{y}}_{w,h}}$ 相對於真實位置 ${bf{y}}_{0,0}$ 的損失函數，定義為： $Delta left( {{{bf{y}}_{0,0}},{{bf{y}}_{w,h}}} right) = mleft( {{{bf{y}}_{0,0}}} right) - mleft( {{{bf{y}}_{w,h}}} right)$ ，其中 $mleft( bullet right)$ 設計為高斯函數，在目標位置響應最大。

具體求解過程可以移步文章內容，有疑問可以再討論，有時間我會再補充進來的。

2.2 多峰目標檢測

每當新來一幀時， $bf{s}$ 是基於上一幀目標位置的圖像塊，目標的位置 ${bf{y}}=fleft( {{bf{s}};{bf{w}}} right)$ 可以通過(1)計算得到。通過循環採樣得到的整張響應圖可以這樣計算：

$Fleft( {{bf{s}},{bf{y}};{bf{w}}} right) = {{mathcal F}^{ - 1}}left( {hat Psi _{{bf{s}}0}^* circ {bf{hat w}}} right) = {{mathcal F}^{ - 1}}left( {{{{bf{hat k}}}^{{Psi _{{bf{x}}0}}{Psi _{{bf{s}}0}}}} circ {bf{hat alpha }}} right)$ (3)

其中 $Psi left( { bullet ,{{bf{y}}_{0,0}}} right)$ 縮寫為 ${Psi _{ bullet 0}}$ 。如圖二所示，當目標周圍有相似特徵的區域時，可能會出現最高的峰值是干擾的情況。為了進一步提高定位精度，我們進行多峰檢測。

圖二：

對於（3），多個峰值可以通過 $Pleft( {bf{s}} right) = Fleft( {{bf{s}},{bf{y}};{bf{w}}} right) circ {bf{B}}$ 得到，其中 ${bf{B}}$ 是一個只有局部最高點是1，其餘為0的矩陣。當這些峰值與最高點的比例超過一個閾值時，我們對這些峰值進行二次檢測，最後目標定義為所有響應圖的最高點。

2.3 高置信度模型更新策略

如何判斷跟蹤結果是否準確是一個沒有定論的問題，但又是一個非常重要的問題。因為這決定著模型的更新策略。KCF，DSST，DSSVM，Staple等許多演算法是不進行跟蹤結果可靠性的判定的，每一幀的結果都用來更新，或者像MDNet或者TCNN那樣每隔N幀更新一次。這樣是有風險的，特別是當目標被遮擋，或者跟蹤器已經跟的不好的時候，再去更新模型，只會使得跟蹤器越來越無法識別目標，這就是模型漂移問題，model drift。

由於想要保證跟蹤速度，我們就需要一種簡單有效的模型更新策略，最好能夠通過已經獲得的一些資源來進行判斷，而不需要進行太多複雜的計算。首先最容易想到的就是response map的最高點的值 ${F_{max }}$ ，一般來說這個值越大說明跟蹤的結果越好，但也有例外，比如圖三中第一行第三列，在目標被幾乎完全遮擋的時候最高響應值是0.94，這個值是高於整個視頻最高響應值的均值的，如果只用這一個判據進行了模型的更新，就會讓模型漂移到遮擋物體上，如圖三第二行第三列，最後丟失了目標。

響應最高點並不能反映響應圖的振蕩程度。在圖三中，雖然最高點的值 ${F_{max }}$ 依然高，但是響應圖在被遮擋時振蕩劇烈，是可以通過振蕩程度來避免錯誤更新的。因此我們提出了一個新的判據APCE：

$APCE = frac{{{{left| {{F_{max }} - {F_{min }}} right|}^2}}}{{meanleft( {sumlimits_{w,h} {{{left( {{F_{w,h}} - {F_{min }}} right)}^2}} } right)}}$ (3)

其中 ${F_{max }},{{F_{min }}},{{F_{w,h}}}$ 分別表示響應最高、最低和 $(w,h)$ 位置上的響應。這個判據可以反映響應圖的振蕩程度，當APCE突然減小時，就是目標被遮擋，或者目標丟失的情況，如圖三第一行中目標被遮擋後，APCE相對於這段視頻APCE的歷史均值就減小的很明顯，因此在這種情況下我們選擇不更新模型，從而避免了模型的漂移。

只有當APCE和 ${F_{max }}$ 都以一定比例大於歷史均值的時候，模型才進行更新，這樣一來大大減少了模型漂移的情況，二來減少了模型更新的次數，達到了加速的效果。

3. Experiments

3.1 自身對比實驗

我們分別用傳統特徵（HOG+CN）和CNN特徵實現了LMCF和DeepLMCF，另外比較了不用多峰檢測的LMCF-Uni，不用模型更新策略的LMCF-NU，以及兩者都不用的LMCF-N2，在OTB50測試了效果。當然除了速度之外，各個指標都是DeepLMCF最好。可見模型更新策略和多峰檢測策略都帶來了一定的提升。

3.2 LMCF對比實驗

左邊一列是OTB50，右邊是OTB100。跟用傳統特徵的比較新的方法做了比較，方法和對應年份、出處都在圖例裡面，用的結果都是各個作者自己公布的結果。我們的平均速度在80FPS以上。

3.3 DeepLMCF對比實驗

我們還做了一組實驗，將特徵換成CNN特徵，跟最新的用了深度特徵的演算法作比較。在提交的前幾天看到了MD大神ECCV的新作C-COT，他公布了結果，所以也拿來比較了一下。效果確實比我的好一些，但是速度差別很明顯，我們的速度是10FPS左右，而C-COT的速度是0.25FPS左右（這是我們自己測試的速度）。

通過上面的實驗，我們驗證了LMCF的高效性。

4. Conclusion

總結一下，這篇文章中，我們用了結構化SVM作為分類器，有著強大的判別能力，並引入了相關濾波，通過循環採樣增加了訓練樣本的數量同時進行加速。我們利用多峰檢測避免了相似物體和背景干擾。針對模型更新環節，提出了簡單有效的模型更新策略，大大減少了模型漂移的情況，同時減少了模型更新的次數，達到了再次加速的效果。我們的方法不依賴於具體特徵，可以根據實際情況使用傳統特徵或者深度特徵。在實驗中，我們驗證了LMCF的高效和高精度。

[1] J. F. Henriques, R. Caseiro, P. Martins, and J. Batista. Highspeed tracking with kernelized correlation ?lters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(3):583–596, 2015

[2] D. S. Bolme, J. R. Beveridge, B. A. Draper, and Y. M. Lui. Visual object tracking using adaptive correlation ?lters. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, pages 2544–2550. IEEE, 2010.

[3] S. Hare, A. Saffari, and P. H. Torr. Struck: Structured output tracking with kernels. In 2011 International Conference on Computer Vision, pages 263–270. IEEE, 2011.