目标跟踪之相关滤波
一. 何為相關濾波？
? ? ? ?Correlation Filter 最早應用于信號處理，用來描述兩個信號之間的相關性，或者說相似性（有點像早期的概率密度），先來看定義：
? ? ? ?對于兩個數據 f 和 g，則兩個信號的相關性（correlation）為：
? ? ? ??? ??
? ? ? ?其中 f? 表示 f 的 復共軛，這是和卷積的區別（相關性 與 卷積 類似，區別就在于里面的共軛）。
? ? ? ? ? ?PS：復共軛是指 實部不變，虛部取反 (a + b i)* = a - b i； ?共軛矩陣是指 矩陣轉置后再對每個元素求共軛，不理解的童鞋請查閱百科。
?
二. ?CF 在圖像的引入 － MOSSE
?
? ? ? ?可以參考經典論文 MOSSE （Minimum Output Sum of Squared Error filter）
? ? ? ?論文下載：visual object tracking using adaptive correlation filters
? ? ? ?對于圖像來講，問題描述為要找到一個 濾波模版 h，與輸入圖像 f 求相關性，得到相關圖 g。
? ? ? ??
? ? ? ?為了方便理解，用一幅圖來進行說明（相關圖 g 描述目標響應，越接近時值越大）：
? ? ? ??
? ? ? ?為了加快計算速度，這里引入了傅里葉變換，根據卷積定理（correlation版本）可知，函數互相關的傅里葉變換等于函數傅里葉變換的乘積：
? ? ? ? ??
? ? ? ?通過上面的公式，將復雜的互相關計算轉換成 點乘。注意后面的 F（h） 是共軛，與卷積不同，公式可以簡化描述為：
? ? ? ??
? ? ? ?H* 就是我們要求的濾波器，MOSSE 提出的方法就是 最小化平方和誤差，也就是針對m個樣本 求最小二乘，描述為：
? ? ? ??
? ? ? ?上面公式是將圖像展開到像素，每個像素是獨立計算的，最小化上面的公式很簡單，就是求偏導=0，具體求解過程不再展開，得到最終的求解公式為：
? ? ? ? ? ??
? ? ? ?作者提出了一個更新算法，根據當前幀不斷進行調整，即在線更新策略，調整策略如下：
? ? ? ? ? ??
? ? ? ?其中?η 為學習率，一般設置為 0.1，通過分子分母分別更新。
?
三. 有一種速度叫 KCF
? ? ? ?KCF是一個非常經典的算法（kernelized correlation filters），速度極快，正常可以達到 100+ FPS。
? ? ? ?論文下載：High-speed tracking with kernelized correlation filters（ECCV 2012, TPAMI 2015）?
? ? ? ?Paper及源碼下載參考作者主頁：http://www.robots.ox.ac.uk/~joao/#
? ? ? ?關于 KCF 的介紹可以參考之前的博文：【?機器學習實踐系列之5 - 目標跟蹤?】
?
四. 品味經典之 DSST
? ? ? ?DSST（Discriminative Scale Space Tracker）是在 MOSSE 基礎上的改進，主要在應對尺度變化上（增加了一個 尺度 Correlation Filter），通過兩個 Filter 分別跟蹤?位置變化（translation）和尺度變化（scale estimation），Translation Filter 專門用于確定新的目標位置，Scale Filter 用來進行尺度估計。
? ? ? ?另外 DSST 將原來的灰度特征替換為 HOG 特征，能夠對目標特征更好的描述。
? ? ? ?論文下載：Accurate Scale Estimation for Robust Visual Tracking
? ? ? ? ? ? ? ? ? ? ? ?Discriminative Scale Space Tracking?
? ? ? ?工程及 Matlab 代碼可以參考【作者主頁】 ?CPP代碼參考（window c++11）【Github】
? ??> 4.1 Filter 合并
? ? ? ?DSST 組合成了一個三維的空間濾波器（M*N*S），其中 M*N對應輸入Sample寬高（Trans），S對應尺度（Scale）。當然說是組合，實際上是分開獨立計算的，先來看一幅圖：
? ?
1）Translation Filter
? ? ? 對應上圖（a），對于當前Sample框（2倍目標大小），對每個像素 提取 d維特征（d-1維的 hog特征 + 1維的灰度特征-最下patch），得到d個 Patch，?在不同特征維度l=[0,d) 上做基于最小二乘的目標函數：
? ? ? ??
? ? ? 公式中?λ 為正則項，降低 低權重系數的影響，濾波器 通過求偏導得到（公式推導可以看 Paper 的 Appendix）：
? ? ? ??
● 模型訓練過程：
? ? ? 為了簡化計算，作者采用了 Single Training Sample的方法，只訓練當前幀的輸入，通過和之前幀的加權平均學習到前面的數據（借鑒了 MOSSE 的參數更新策略）：
? ? ? ??
? ? ? 其中 A、B 分別對應分子、分母，通過上面的公式迭代求解，η 表示應學習率。
●?求解計算過程：
?? ? ?對于 輸入樣本 Z，根據 響應函數 Y=H* Z，并求 逆向 FFT 得到最大相關濾波響應值 y：
?? ? ? ?? ? ??
2）Scale Filter
? ? ? 對應上圖（b），按照目標位置?{w,h} 進行尺度縮放采樣，縮放尺度為 a^n，a=1.02，n=[-16,16]，對應采樣為 33級別（=S），構成了一個層數為S的金字塔。
? ? ? 對應在每層金字塔上，將 Patch 圖像縮放成統一尺寸，提取d維Hog特征，以該特征作為訓練樣本，得到相關濾波器 H，用來預測輸出尺度。
? ? ? 模型更新過程、濾波響應求解過程 與 Translation Filter 一致。
?
? ??> 4.2 算法描述
輸入（input）：
? ? ? a）t 時刻的圖像 I(t)
? ? ? b）上一幀 目標位置 P(t-1) 和尺度 S(t-1)
? ? ? c）上一幀的位置模型 A_trans(t-1)，?B_trans(t-1) 和 尺度模型?A_scale(t-1)，?B_scale(t-1)
輸出（output）：
? ? ? a）當前幀的 估計位置 P(t) 和估計尺度 S(t)
? ? ? b）更新后的位置模型 A_trans(t)，?B_trans(t) 和 尺度模型?A_scale(t)，?B_scale(t)
位置估計過程：
? ? ?1）根據上一幀目標位置 P(t-1) 和尺度 S(t-1)，在當前幀圖像 I 上，按照2倍目標大小采樣，得到 Search 樣本 Ztrans；
? ? ?2）根據上一幀位置模型 A_trans(t-1)，?B_trans(t-1)?，計算位置響應，公式為：
? ? ? ??
? ? ?3）得到目標位置?P(t) = max(y_trans)；
位置估計過程：
? ? ?4）提取不同尺度樣本 Ztrans（文中對應33個）；
? ? ?5）與上面同樣的方式計算出 y_scale，得到目標尺度 ?S(t) = max(y_scale)；
模型更新過程：
? ? ?6）從當前幀圖像 I(t) 提取 訓練樣本 f_trans 和 f_scale；
? ? ? ? ? ?提取對應Hog特征、灰度特征，構造對應尺度的高斯響應函數。
? ? ?7）更新模型?位置模型 和 尺度模型；
? ? ? ? ? ?參照上面的模型訓練過程。
? ? ? ?作者后續在 DSST基礎上進行改進，提出了 fDSST，旨在優化算法效率，轉發表在 PAMI上，幀率有了 成倍的提升。主要改進思路有兩點：一是 相關性插值（sub-grid interpolation of correlation scores），即通過 Coarse Grid 計算 Score，通過插值得到 全分辨率的 Score；二是 通過PCA降維來減少特征維度。都是比較簡單的Trick，本文不再展開（Paper 可以參考上面的鏈接）。
??
五. VOT2016 排名第一的 C-COT
? ? ? ?比賽說明實力，這篇文章來自于 2016年的ECCV，MD大神注定要在 CF 上死磕。
? ? ? ?論文下載：Beyond Correlation Filters: Learning Continuous Convolution Operators for Visual Tracking
? ? ? ?代碼下載：【Github】
? ? ? ?傳統的相關濾波方法只是用 灰度、Hog 做 Single Sample的特征提取和濾波訓練，也許很多人都能想到 要用金字塔，要結合CNN多尺度的卷積特征，思路沒錯，只是 MD 比你下手快而已。
? ? ? ??
? ? ? ?算法核心思想是：
1）對于Search Region，提取不同分辨率的特征（RGB＋Conv特征），對應 第一列；
2）通過針對不同層訓練的相關濾波器 進行計算，對應 第二列；
3）得到響應圖（Confidence Scores），對應第三列；
4）將響應圖 進行累加，得到多個分辨率置信度之和，即為最終的置信圖，對應最大值為目標位置；
? ? ? ?這篇文章算是過渡階段的產品，除了引入深度學習的元素之外，其實沒有太多的創新點，對于時間充裕的童鞋可以詳細看看，否則的話建議忽略。
總結
- 上一篇： 期待已久的2012年度最佳 jQuery
- 下一篇： Cisco交换机端口聚合、VTP、ACL