視覺跟蹤(Visual Tracking)論文解讀之相關濾波(Correlation Filter)篇（1）數學基礎

08-11

來自專欄視覺跟蹤 Visual Tracking12 人贊了文章

第一次寫博文，誠惶誠恐。

視覺跟蹤這幾年發展很快。乘著這段時間在研究這個方面的機會，想把這方向的一些閱讀體會寫下。知乎有很多大神對論文解讀，可大多數都沒有補充論文的細節部分，而是原論文公式的重複。我正好最近在將視覺跟蹤的Matlab程序用C++實現（代碼鏈接：

rockkingjy/OpenTrackers?

github.com

以供對照閱讀），對細節的一些體會分享給大家，希望能對大家有點作用。

視覺跟蹤近年來主要分了兩個方向，一個是相關濾波，一個是深度學習。其中，相關濾波方向相對來說比較難，說這個方向比較難，是因為涉及到的數學點比較多，比較雜。但是，雖然難，只要一點點分解開來，也就不難了。武功要一招一式的學，視覺跟蹤也是。閑話少說，這個系列預計要逐步重點解讀的是這幾篇文章：

D. S. Bolme, J. R. Beveridge, B. A. Draper, and Y. M. Lui, 「Visual object tracking using adaptive correlation filters,」 in Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, pp. 2544–2550, IEEE, 2010.

此文可以看作這個方向的開山，類似於太祖努爾哈赤，演算法簡稱 MOSSE。

J. F. Henriques, R. Caseiro, P. Martins, and J. Batista, 「Exploiting the circulant structure of tracking-by-detection with kernels,」 in European conference on computer vision, pp. 702–715, Springer, 2012.

此文可以看作此方向之大成，類似於太宗皇太極，演算法簡稱CSK。

J. F. Henriques, R. Caseiro, P. Martins, and J. Batista, 「High-speed tracking with kernelized correlation filters,」 IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 3, pp. 583–596,2015.

此文和CSK很像，同一個作者，可以看作此方向之集大成者，可看成聖祖康熙爺，演算法簡稱KCF。

M. Danelljan, A. Robinson, F. Shahbaz Khan, and M. Felsberg, 「Beyond correlation filters: Learning continuous convolution operators for visual tracking,」 in ECCV, 2016.

很強悍的演算法，由大神Danelljan提出，可看作世宗雍正，演算法簡稱C-COT。

M. Danelljan, G. Bhat, F. Shahbaz Khan, and M. Felsberg, 「Eco: Efficient convolution operators for tracking,」 in CVPR, 2017.

是對C-COT的改進，同樣由Danelljan大神提出，是這一兩年最牛逼的演算法，可看作高宗乾隆，演算法簡稱ECO。

再往後的發展就是最近的了，重要的文章可能也會做些解說。這個方向從開山至今8年，雖然深度學習方法急追直上，但在我看來遠沒有結束。大清那江山也有三百年不是。

至於以上演算法的重要性和Nubility，可以參見

foolwood/benchmark_results?

github.com

此外，由於相關濾波的特徵非常重要，這個系列還會解讀三個重要的特徵（features）, 分別是：

HOG特徵:
N. Dalal and B. Triggs, 「Histograms of oriented gradients for human detection,」 in Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, vol. 1, pp. 886–893, IEEE, 2005.
P. F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan, 「Object detection with discrimina-tively trained part-based models,」 IEEE transactions on pattern analysis and machine intelligence, vol. 32,no. 9, pp. 1627–1645, 2010.
顏色特徵 CN(Color names):

J. Van De Weijer, C. Schmid, and J. Verbeek, 「Learning color names from real-world images,」 in Computer Vision and Pattern Recognition, 2007. CVPR』07. IEEE Conference on, pp. 1–8, IEEE, 2007.
深度特徵: K. Chatfield, K. Simonyan, A. Vedaldi, and A. Zisserman, 「Return of the devil in the details: Delving deep into convolutional nets,」 arXiv preprint arXiv:1405.3531, 2014.

不多評論，下面進入正文。高能預警，數學公式很多，但我也會從基礎的數學開始，儘可能清晰地說明，避免模糊不清的地方。

數學基礎

說是基礎，也需要同學們學過高等數學和線性代數。你說你沒學好？那沒關係，一邊看哪兒不懂一邊補就是了，天才才能一次學好呢，你是不是我不知道，至少我可不是天才。你說你沒學過？那有些難辦，還是先去補補再說吧。

函數空間 $L^2(T)$

$L^2(T): 以T為周期的函數的帶內積langle cdot , cdot angle的希爾伯特空間。內積定義為： langle g,h angle = frac{1}{T} int^{T}_{0} g(t) overline{h(t)} dt$

這是數學定義，下面說人話。

以T為周期的含義就是 $f(x)=f(x+T)$ 。

內積，是高中三角函數里學的那個「內積」的推廣，g和h相當於三角形的兩個邊，這裡內積定義中的h(t)上面一橫表示求復共軛，因為這裡的函數變數都是複數。

希爾伯特空間，是數學裡的概念，如果你不是數學系的，不用管它。筆者也是數學系出身，若有興趣可以私信我，我們慢慢聊。

為什麼一開始要討論這個「函數空間」？因為，這個「空間」限定了我們這篇文章里用到的函數，都是在哪個範圍里的，就像你踢世界盃，再怎麼踢也不能出了足球場，跑到觀眾席上去踢是吧。而這篇文章討論的函數的範圍，都是以T為周期的周期性函數，並且，任意兩個函數的內積（按照以上的定義）也在這個範圍內。

矩陣求導

文章省略了很多矩陣求導，直接給出最終的結果，這裡列出需要用到的公式，以備後用。至於公式的證明，相信學過線性代數的同學應該可以很快得出，或者不追究，記住即可。

$frac{partial}{partial m{x}}(m{x^Ha}) = frac{partial}{partial m{x}}(m{a^Hx})= m{a} ， frac{partial}{partial m{x}}(m{AB}) = frac{partial m{A}}{partial m{x}} m{B} + m{A} frac{partial m{B}}{partial m{x}} ，$

$frac{partial}{partial m{x}}(||{m{Ax}}||^2) = frac{partial}{partial m{x}} (m{x^HA^HAx} ) = m{A^HAx + A^HAx} = 2m{A^HAx}$

克羅內克乘積 $otimes$

$假設mathbf{A}是m imes n矩陣，mathbf{B}是p imes q矩陣，則：mathbf{A}otimesmathbf{B} = egin{bmatrix} a_{11} mathbf{B} & cdots & a_{1n}mathbf{B} \ vdots & ddots & vdots \ a_{m1} mathbf{B} & cdots & a_{mn} mathbf{B} end{bmatrix}_{mp imes nq}$

定義很清楚，也就是將矩陣A的每個項都和B乘，再形成一個超大矩陣。

弗羅貝尼烏斯範數（Frobenius norm）

$|A|_{ m F} = sqrt{sum_{i=1}^m sum_{j=1}^n |a_{ij}|^2}$

很簡單，也就是將所有的項的絕對值平方加起來，再做個開方就可以了。

傅立葉變換

傅立葉變換將函數從時域變換到頻域，而逆傅立葉變換則是從頻域變換到時域。為啥要變來變去？有啥好處？下面很快就能知道，先上公式。別忘了，這裡討論的都是周期函數的傅立葉變換。

$傅立葉變換：hat{g}[k] = langle g , e_k angle = frac{1}{T} int^{T}_{0} g(t)e^{-i 2pi kt/T} dt$

$逆傅立葉變換：g(t)=sum^{infty}_{-infty}hat{g}[k] e^{i 2pi kt/T}$

這裡有個疑問了，為啥正向傅立葉變換是連續的積分，而反向的卻用離散的求和？這是因為，這篇文章都是在頻域里進行實際的計算，而計算機目前都是離散的。

傅立葉變換三個重要性質

傅立葉變換有很多性質，這三個性質後面要用到，所以這裡列出來，不用到的就不列了。學過高等數學的應該很快能得出證明，也可以不追究，記住即可。

第一個性質：平移性質

$對於任意實數L，如果h(t)=g(t-L),則有：hat{h}[k]=e^{-2pi i L k} hat{g}[k]$

第二個性質：帕塞瓦爾定理（Parsevals formula）

$||g||^2_{L^2}=||hat{g}||^2_{l^2}, 這裡的||g||^2=langle g , g angle,||hat{g}||^2_{l^2}=sum^{infty}_{-infty}|{hat{g}[k]}|^2.$

第三個性質：珀松求和定理（Poisson summation formula）

$sum_{n=-infty}^infty f(n)=sum_{k=-infty}^infty hat fleft(k ight)$

由此不難推導出： $sum_{n=-infty}^{infty} s(t + nT)=sum_{k=-infty}^{infty} frac{1}{T}cdot hat sleft(frac{k}{T} ight)e^{i 2pi frac{k}{T} t }$

第一個性質，也就是說在時域裡面平移，相當於在頻域裡面乘了個虛指數。

而第二個性質，說明了時域和頻域的平方和相等。

第三個性質，文章里常用到，這裡知道即可。

卷積

時域里的卷積： $(g * h)(t) = frac{1}{T} int^{T}_{0} g(t-s) h(s) ds$

頻域里的卷積： $(f * g)[k] = sum_{l=-infty}^infty f[l] g[k - l] = sum_{l=-infty}^infty f[k-l] g[l]$

同樣在這裡，時域里的卷積是周期連續的，頻域里的卷積是離散的。

卷積性質

$widehat{g*h}=hat{g}hat{h}, widehat{gh}=hat{g}*hat{h}$

這倆性質非常重要，也是相關濾波方法（DCF）速度的關鍵。為啥？卷積的計算其實很耗時，看看現在風口的CNN，全名就是卷積神經網路，特點就是--慢！但是點乘的速度卻很快，這倆性質能把慢速的卷積變成快速的點乘，就是其妙處所在。再加上高速的傅立葉變換演算法FFT，即可大大提升速度。具體的複雜度分析，有空再談，或有興趣來私聊。

常對角矩陣（Toeplitz matrix）

文章的推導要用到將離散卷積標示為常對角矩陣：

$y = h ast x = egin{bmatrix} h_1 & 0 & ldots & 0 & 0 \ h_2 & h_1 & ldots & vdots & vdots \ h_3 & h_2 & ldots & 0 & 0 \ vdots & h_3 & ldots & h_1 & 0 \ h_{m-1} & vdots & ldots & h_2 & h_1 \ h_m & h_{m-1} & vdots & vdots & h_2 \ 0 & h_m & ldots & h_{m-2} & vdots \ 0 & 0 & ldots & h_{m-1} & h_{m-2} \ vdots & vdots & vdots & h_m & h_{m-1} \ 0 & 0 & 0 & ldots & h_m end{bmatrix}_{(m+n-1) imes n} egin{bmatrix} x_1 \ x_2 \ x_3 \ vdots \ x_n end{bmatrix}$

矩陣右下角標將行數和列數清楚地表示出來，以免模糊混淆，這個矩陣有m+n-1行和n列。

網格搜索（Grid Search）

所謂網格搜索，就是將一個連續的空間分成離散的網格，再在這個網格上進行搜索，找到極值。

C-COT和ECO用網格搜索求初步的極值，後面會詳細解釋。

牛頓法（Newtons Method）

C-COT和ECO用牛頓法來求精細極值。

高斯-牛頓法（Gauss-Newton Method）

ECO里有用高斯牛頓法做一次近似，後面用到的時候會詳細推導解釋。

共軛梯度法（Conjugate Gradient）

C-COT和ECO用共軛梯度法來求解稀疏線性方程。

以上是這篇文章的數學基礎（是否已崩潰），下一篇將正式進入開山之作MOSSE的解讀。

（未完待續）