核化相關濾波器高速跟蹤：KCF(2015PAMI)

論文下載地址：paper。代碼下載地址：code。本人水平有限，難免有理解不到位的地方，請大家批評指正哈哈～

個人認為，這篇論文是近年來跟蹤界最經典的論文，沒有之一。主要思想就是利用了循環矩陣對角化等性質，使得核化之後的計算變得十分簡單。原理很複雜（原文中公式竟然有60多個啊+_+），代碼很簡單（少到令人感動）。下面廢話不多說，談談論文的主要思想。

1.總體思路：所謂的相關濾波方法就是根據當前幀的信息和之前幀的信息訓練出一個相關濾波器，然後與新輸入的幀進行相關性計算，得到的置信圖就是預測的跟蹤結果，顯然，得分最高的那個點（或者塊）就是最可能的跟蹤結果。由於KCF里並沒有任何的流程圖，所以我們藉助Kaihua Zhang的STC[1]中的配圖來理解一下，看著配圖應該能理解主要的流程了。這裡要說一下，為什麼能用其它論文的配圖，因為我們介紹的這篇KCF和STC都是對12年CSK[2]的改進，不同的是，KCF是在CSK基礎上加了HOG特徵使得效果大大提升了，STC是在貝葉斯的框架下對CSK進行解釋並在其中加入了上下文（context）信息的應用。所以本質上來說，這幾個都是一樣的流程。

1.1上面的部分就是利用之前幀的跟蹤結果圖片訓練出相關濾波器。我們將原始的問題表述為：

優化函數由凸優化里最簡單的最小二乘和正則項組成，也就是最常用的嶺回歸方法：

這裡的理想回歸期望（標籤）假設是高斯型，直觀上理解就是離上一幀跟蹤結果越近，那麼它是這一幀的跟蹤結果的概率也就越大。如下圖，下一幀中心點的位置在黃色點周圍的可能性大，不會跑太遠，所以理想回歸函數也就是中間大周圍小。

因為最小二乘類的優化方法已經很成熟了，所以我們可以直接用公式求解（其實就是求偏導令其等於0）：

看起來比較複雜，又是共軛轉置又是求逆的，所以要簡化一下。那麼本文也是常規思路，把非線性問題轉化為線性問題，所以就想到了SVM中也用到的核技巧（注意我們這裡推導的時候用的是點積核，但其實核函數還有多項式核、徑向基核及高斯核等），引入核函數後能夠把參數訓練問題簡化：

這裡的K是兩個矩陣的核相關性。看起來似乎已經簡化了很多了，但是，還是有求逆！求逆殺傷力太強了，不行，一定還要簡化。怎麼辦呢？這時循環矩陣對角化的性質派上用場了，利用循環矩陣的性質，使得訓練過程進一步簡化。

這裡頂上的符號是復域的意思。不管你信不信，反正我是信了，竟然如此簡單，這裡詳細的推導過程放在後面的部分。

1.2下面的部分就是對新輸入的幀進行檢測，其實就是跟濾波器計算出相關性再乘上回歸係數，如果是新手聽不懂沒關係，後面會再講的哦。右下角的置信圖（就是各個點是跟蹤結果的可能性）用公式來表達就是如下：

沒錯，就是這麼簡單就能求出輸入幀的跟蹤結果了。如上圖右下角所示，新的跟蹤結果比原跟蹤結果往右上方移了一些，直觀上來看紅色框中David的臉確實往右上方移動了一些，所以結果應該是對的，當然這只是我們肉眼看到的結果，真正結果好不好還要看在數據集上跑的結果，KCF的結果會在之後的實驗部分講，結果是相當好的，當然那是在2014年的時候。

那麼這裡得到的響應矩陣（置信圖）該怎麼理解呢？便於理解，故放一張圖。這裡也是循環採樣的精髓之處。

如上圖，最後得到的響應矩陣其實可以理解成一種密集的採樣對應的響應矩陣，左上角（上圖中第1行第1列）的響應值就是預測的當前輸入幀以這個點為中心的可能性，當然這個點的預測值肯定是很低的，因為我下一幀很難跑到那裡去。以此類推，MxN個響應對應的就是MxN種循環移位。下面一句話是重點，所謂的循環矩陣到這裡就大顯身手了，仔細想想，第ij塊表示原圖下移i行右移j列，那麼換句話說，好像我所有的這MxN個循環移位的矩陣只要用一個量就可以表示了。

有沒有一種熟悉的感覺？對，就是基波和諧波。類比一下，我用一個基波和一個倍數就能表示所有的諧波了，這裡的原圖就是基波，而位移之後的圖就是諧波。自然地，既然那麼像，那我們就試試傅立葉變換唄，一試就成了，因為需要計算的量很少，所以速度快，因為密集採樣樣本大大增加，所以跟蹤的效果又很好。

如果你不是做跟蹤這行的話，可能會問，右下角t+1幀的時候為什麼紅色框的中心（也就是黃色小點）不是David的鼻子那裡，那是因為這個紅色框是根據上一幀的跟蹤結果來畫的，這個小黃點的位置其實是上一幀David（David也算是個數據集中的明星0.0）鼻子的位置，這也是常見做法，先用上一幀的結果在當前輸入幀框出一個大框，然後跟最新的濾波器做相關性計算，相關性最大的就是鼻子那塊，也就是當前輸入幀的跟蹤結果。

2.其實講到這裡已經把精髓講完了，下面講一些推導細節，加深理解。

2.1循環矩陣對角化有神奇效果，大大降低了運算量。首先舉個例子，來展現它神奇的效果。就拿上文出現的嶺回歸公式當例子吧，看看能把它簡化成什麼樣。

原始公式：

在復域中(H表示共軛轉置)即：

化簡過程：

這是我早前推的，比起他的公式，我個人更喜歡他的代碼嘻嘻。這個公式推下來並沒有用，只是讓我們見識一下循環矩陣化簡的威力，真正用到代碼里去的是下面3個推導。

2.2大家是否還記得我們這裡實際上用到的是核化的嶺回歸啊？也就是比普通的稍微簡化了一些的，所以推導起來也比較容易。

原始公式：

化簡過程：

嗯，好像看起來還不錯哦，既沒有求逆又沒有很多矩陣乘法運算。它的代碼其實更感人。

簡單的不能再簡單了，至此，訓練過程結束。下面看檢測過程，同樣化簡得面目全非。

2.3檢測出跟蹤結果，就是當前輸入的幀和濾波器求相關性，相關性最大的即為跟蹤結果。

原始公式：

化簡過程：

嗯，這篇論文真是不斷地感動著我們這些吃瓜群眾，原來可以這麼簡單。看著公式，代碼閉著眼睛都能編了。

現在只剩一個問題了，那就是核相關性怎麼求。

2.4核相關性的化簡。好像解決了這個就完美了，那這個核相關性好求嗎？如果不好求的話，就空虧一簣了，放心，跟蹤界的allstar Henriques（葡萄牙人的名字我至今不會讀）當然已經幫我們解決好了，依然簡單。

原式公式：

化簡過程：

我們這裡只推導點積核。剩下的多項式核，徑向基核，高斯核類比就能得到。論文里效果最好的是高斯核。

注意，代碼里第2行是使用HOG特徵的關鍵，他把31層HOG特徵全部加起來了，這個簡單的操作使得之前的CSK能用很多高維特徵，故性能大增。

3.實驗。我在OTB50上跑了0.514，因為加入了形狀特徵HOG，所以抗光照等性能驟升，當時（2014年）能排世界第3，由於實現起來非常簡單，在很多人眼裡是近年來跟蹤界當之無愧的最佳論文（其實是在我眼裡）。

本人跑的結果：

作者論文中的對比實驗結果：

4.總結

本論文使用了HOG特徵+核函數法把相關濾波器領域又推到了一個新的高度上。KCF是原理很複雜，實現很簡單的代表作之一。

[1] K. Zhang, L. Zhang, Q. Liu, D. Zhang, and M.-H. Yang. Fast visual tracking via dense spatio-temporal context learning. In Proceedings of the European Conference on Computer Vision, 2014.

[2] J. F. Henriques, R. Caseiro, P. Martins, and J. Batista. Exploiting the circulant structure of tracking-by-detection with kernels. In Proceedings of the European Conference on Computer Vision, 2012.

推薦閱讀：