KCF學習筆記【目標跟蹤】

04-06

第一篇學習的論文，理解不到位的，請各位大神指點迷津，論文(paper),代碼（code）核心思想：（1）本文利用任何循環矩陣可以被傅里葉矩陣對角化等性質，將矩陣的運算轉化為向量的Hadamad積，即元素的點乘，降低了計算量，提高運算速度，使演算法滿足實時性要求。

（2）將線性空間的領回歸通過核函數映射到非線性空間，在非線性空間通過求解一個對偶問題和某些常見的約束，同樣的可以使用循環矩陣傅里葉空間對角化簡化計算。

（3）加入多通道HOG特徵來代替單通道原始像素特徵，提高實驗的數據。

摘要：給定一個圖像塊目標，學習一個分類器來區分目標與周圍環境。為解決自然圖像中的變化，典型的方法是用平移和縮放的樣本塊（patches）來訓練分類器。這樣的樣本集充滿冗餘 將所有重疊的像素約束為相同的像素。基於這一簡單的觀察，為包含上千個平移的圖像塊的數據集提出了一分析模型。可用離散傅立葉變換對角化已有的循環矩陣，極大降低了存儲和計算量。有趣的是，對於線性回歸，我們的公式與相關濾波器等價；然而，對於核回歸，不同於其它核方法（複雜度與其線性部分相同），提出新的核化的相關濾波器（Kernelized Correlation Filter）。在核化的相關濾波器的基礎上，提出通過線性核，擴展線性相關濾波器至多通道，我們稱為「對偶的相關濾波器（Dual Correlation Filter）」。儘管每秒運行上百幀，且用到的代碼行數很少（方法 1），KCF和DCF仍在包含50個視頻的基準數據集上超越了Struck或TLD。為進一步發展，該跟蹤框架已開源。

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

接下來，來場酣暢淋漓的推導（想起湯家鳳老師），說起公式推導，剛拿到論文，發現有60+個公式，有點害怕，現在我來把重點的推導下，廢話不多說，開始我的表演！

一，嶺回歸

設訓練樣本 $left( x_{i},y_{i} ight)$ ,樣本和標籤都為列向量，線性回歸的函數 $fleft( x_{i} ight)=W^{T}x_{i}$ ,加入正則項 $lambda$ ，防止過擬合。嶺回歸即最小二乘加上一個正則項，本篇選擇這個loss,具有封閉解（解析解）對W求偏導，進一步的化簡，可以求出

推導：

在傅里葉域中 $X^{H}=(X^{*})^{T}$

二，循環矩陣

循環矩陣被傅里葉矩陣對角化性質很重要，推導可參考【PDF】，性質的推導：

進一步的推導，線性回歸係數 $W$ ,可以通過離散傅里葉變換得到點乘運算，免去了求逆計算，大大提高速度。推導結果原文中（12）不同，相關公式一起附上。

相乘：設C,B為循環矩陣，其乘積的特徵值等於特徵值的乘積：

相加：和的特徵值等於特徵值的和：

卷積：循環矩陣乘向量等價於生成向量的逆序和該向量卷積，注意卷積本身即包含逆序操作，另外利用了信號與系統中經典的「時域卷積，頻域相乘」。

傅式對角化簡化的嶺回歸：

三，非線性回歸

將線性轉化為非線性 $w=sum_{i}{x}_{i}psileft( x_{i} ight)$ , 使用核技法 $k$ 是核相關矩陣， $k_{ij}=kleft( x_{i},x_{j} ight)$

$fleft( z ight)=w^{T}z=sum_{i=1}^{n}{a_{i}}kleft( z,x_{i} ight)$ , 進一步的推導：

$alpha$ 的離散傅里葉變換，利用到 $K=C(k^{xx})$ ,進一步推導：

四，快速檢測

下面的部分就是對新輸入的幀進行檢測，其實就是跟濾波器計算出相關性再乘上回歸係數，檢測出跟蹤結果，就是當前輸入的幀和濾波器求相關性，相關性最大的即為跟蹤結果。置信圖（就是各個點是跟蹤結果的可能性）用公式來表達就是如下：

推到這，看退出來的結果，點乘，沒有逆的計算，矩陣也進一步簡化，提高了計算的速度，達到實時跟蹤的好的效果，也基本都推完了，推完公式後，重點和代碼的結合理解。

五，代碼分析

濾波器模板更新

檢測的最大響應

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

六，實驗數據

首次跑OTB50，跑通對我來說有點難度，真是掙紮好多天，但是成功率和精度圖畫出來的時候，感覺那圖是多麼漂亮啊。在這感謝我的師兄，同學，謝謝你們。魯棒性評估評估跟蹤器的傳統方式是，根據第一幀中的準確位置進行初始化，然後在一個測試序列中運行演算法，最後得出平均精確度或成功率的結果報告。我們把這種方法成為一次通過的評估（OPE）。然而跟蹤器可能對初始化非常敏感，並且在不同的初試幀給予不同的初始化會使其性能變得更差或更好。因此，我們提出兩種方式來評估跟蹤器對初始化的魯棒性，即在時間上（即在不同幀開始跟蹤）和空間上（即以不同的邊界框開始跟蹤）擾亂初始化。這兩個測試分別稱為時間魯棒性評估（TRE）和空間魯棒性評估（SRE）。

自己跑出的結果：

作者自己的圖：

本文採用hog特徵和循環矩陣特性以及核技法，又一次在使用相關濾波，將現在廣泛使用濾波器在跟蹤界打下了堅實的基礎。接下來要學習的一篇（Robust Visual Tracking via Hierarchical Convolutional Features ）

作者：Chao Ma, Jia-Bin Huang, Xiaokang Yang, and Ming-Hsuan Yang

有正在研究的大神，一起交流下。感謝！

[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.

KCF學習筆記 【目標跟蹤】

一， 嶺回歸