原文：http://blog.csdn.net/zwlq1314521/article/details/50427038
Henriques, João F., et al. “High-speed tracking with kernelized
correlation filters.” Pattern Analysis and Machine Intelligence, IEEE
Transactions on 37.3 (2015): 583-596.
本文的跟蹤方法效果甚好，速度奇高，思想和實作均十分簡潔。其中利用循環矩陣進行快速計算的方法尤其值得學習。另外，作者在首頁上十分慷慨地給出了各種語言的實作代碼。
本文詳細推導論文中的一系列步驟，包括論文中未能闡明的部分。請務必先參看這篇簡介循環矩陣性質的部落格。
思想
一般化的跟蹤問題可以分解成如下幾步：
1. 在 It 幀中，在目前位置 pt 附近采樣，訓練一個回歸器。這個回歸器能計算一個小視窗采樣的響應。
2. 在 It+1 幀中，在前一幀位置 pt 附近采樣，用前述回歸器判斷每個采樣的響應。
3. 響應最強的采樣作為本幀位置 pt+1 。
循環矩陣表示圖像塊
在圖像中，循環位移操作可以用來近似采樣視窗的位移。
訓練時，圍繞着目前位置進行的一系列位移采樣可以用二維分塊循環矩陣 X 表示，第ij塊表示原始圖像下移i行右移j列的結果。類似地，測試時，前一幀結果附近的一系列位移采樣也可以用 X 表示。
這樣的 X 可以利用傅裡葉變換快速完成許多線性運算。
線性回歸訓練提速
此部分頻繁用到了循環矩陣的各類性質，請參看這篇部落格。
線性回歸的最小二乘方法解為：
w=(XHX+λI)−1XHy
根據循環矩陣乘法性質， XHX 的特征值為 x^⊙x^∗ 。 I 本身就是一個循環矩陣，其生成向量為 [1,0,0...0] ，這個生成向量的傅裡葉變換為全1向量，記為 δ 。
w=(Fdiag(x^⊙x^∗)FH+λFdiag(δ)FH)−1XHy
=(Fdiag(x^⊙x^∗+λδ)FH)−1XHy
根據循環矩陣求逆性質，可以把矩陣求逆轉換為特征值求逆。
w=F⋅diag(1x^⊙x^∗+λδ)⋅FHXHy
w=F⋅diag(1x^⊙x^∗+λδ)⋅FH⋅Fdiag(x^∗)FH⋅y
利用 F 的酉矩陣性質消元：
w=F⋅diag(x^∗x^⊙x^∗+λδ)⋅FH⋅y
分号表示用1進行對位相除。
反用對角化性質： Fdiag(y)FH=C(F−1(y)) ，上式的前三項還是一個循環矩陣。
w=C(F−1(x^∗x^⊙x^∗+λδ))⋅y
利用循環矩陣卷積性質 F(C(x)⋅y)=x^∗⊙y^ ：
F(w)=(x^∗x^⊙x^∗+λδ)∗⊙F(y)
由于 x^⊙x^∗ 的每個元素都是實數，是以共轭不變：
F(w)=x^x^⊙x^∗+λδ⊙F(y)=x^⊙y^x^⊙x^∗+λδ
論文中，最後這一步推導的分子部分寫成 x^∗⊙y^ ，是錯誤的。但代碼中沒有涉及。
線性回歸系數 ω 可以通過向量的傅裡葉變換和對位乘法計算得到。
核回歸訓練提速
不熟悉核方法的同學可以參看這篇部落格的簡單說明。核回歸方法的回歸式為：
f(z)=αTκ(z)
其中 κ(z) 表示測試樣本 z 和所有訓練樣本的核函數。參數有閉式解：
α=(K+λI)−1y
K 為所有訓練樣本的核相關矩陣： Kij=κ(xi,xj) 。如果核函數選擇得當，使得 x 内部元素順序更換不影響核函數取值，則可以保證 K 也是循環矩陣。以下核都滿足這樣的條件：
設核相關矩陣的生成向量是 k 。推導和之前線性回歸的套路非常類似：
α=(Fdiag(k^)FH+Fdiag(λδ)FH)−1y=(Fdiag(k^+λδ)FH)−1y
=Fdiag(1k^+λδ)FHy=C(F−1(1k^+λδ))y
利用循環矩陣卷積性質 F(C(x)⋅y)=x^∗⊙y^ ：
α^=(1k^+λδ)∗⊙y^
這裡 k 是核相關矩陣的第一行，表示原始生成向量 x0 和移位了 i 的向量 xi 的核函數。考察其處于對稱位置上的兩個元素：
ki=κ(x0,xi),kN−i=κ(x0,xN−i)
兩者都是同一個向量和自身位移結果進行運算。因為所有涉及到的核函數都隻和位移的絕對值有關，是以 ki=kN−i ，即 k 是對稱向量。
舉例： x0=[1,2,3,4] ， x1=[4,1,2,3] ， x3=[2,3,4,1] 。使用多項式核 κ(x,y)=xTy ，容易驗證 κ(x0,x1)=κ(x0,x3) 。
對稱向量的傅裡葉變換為實數，有：
α^=(1k^+λδ)⊙y^=y^k^+λδ
論文中，利用 k 的對稱性消除共轭的步驟沒有提及。
線性回歸系數 α 可以通過向量的傅裡葉變換和對位乘法計算得到。
核回歸檢測提速
所有待檢測樣本和所有訓練樣本的核相關矩陣為 K ，每一列對應一個待測樣本。可以一次計算所有樣本的響應（ N×1 向量）：
y′=KTα
利用循環矩陣的轉置性質性質， C(k) 的特征值為 k^∗ ：
y′=C(k)T⋅α=C(k^∗)⋅α=k∗∗α
利用循環矩陣的卷積性質：
y′=(k∗)∗α=k∗α
兩邊傅裡葉變換：
y′^=k^⊙α^
論文中，利用轉置消除共轭的步驟沒有提及。
所有侯選塊的檢測響應可以通過向量的傅裡葉變換和對位乘法計算得到。
核相關矩陣計算提速
無論訓練還是檢測，都需要計算核相關矩陣 K 的生成向量 k 。除了直接計算每一個核函數，在某些特定的核函數下可以進一步加速。
多項式核
κ(x,y)=f(xTy)
其中 f 為多項式函數。寫成矩陣形式：
K=f(XTY)
f 在矩陣的每個元素上單獨進行。根據循環矩陣性質， XTY 也是一個循環矩陣，其生成向量為 F−1(y^⊙x^∗) 。是以核相關矩陣的生成向量為：
k=f(F−1(y^⊙x^∗))
RBF核
κ(x,y)=f(||x−y||2)
其中 f 是線性函數。簡單展開：
κ(x,y)=f(||x−y||2)=f(||x||2+||y||2+2xTy)
由于 X 中的所有 x 都通過循環移位獲得，故 ||x||2 對于所有 x 是常數，同理 ||y||2 也是。是以核相關矩陣的生成向量為：
k=f(||x||2+||y||2+F−1(y^⊙x^∗))
其他核
有一些核函數，雖然能保證 K 是循環矩陣，但無法直接拆解出其特征值，快速得到生成向量。比如Hellinger核： ∑ixiyi−−−√ ，Intersection核： ∑imin(xi,yi) 。
多通道
在多通道情況下（例如使用了HOG特征），生成向量 x 變成 M×L ，其中 M 是樣本像素數， L 是特征次元。在上述所有計算中，需要更改的隻有向量的内積：
xTy=∑l(xl)Tyl
注：非常感謝GX1415926535和大家的幫助，發現原文一處錯誤。(21)式中不應有轉置，應為：
f(z)=Kzα