一個加速trick一種相關濾波解釋

先上圖，benchmark更新了，借用一下圖片，版權歸王強所有，來自這裡 foolwood/benchmark_results：

目標跟蹤階段性總結

截止CVPR 2017，tracking的目前發展如上圖，Tracking方向還是以相關濾波CF和深度學習DL兩大陣營為主：

1. 右半邊是相關濾波CORR. FILTER，根據特徵分兩小類：結合hand-craft特徵如HOG(Histogram of Oriented Gradient), CN(Color Names)或Color Histogram的相關濾波，速度可以做到很快，同時精度也很好，ECO-HC和Staple；結合CONV. FEAT.卷積特徵的相關濾波可以做到最好精度，而且預訓練CNN模型的卷積特徵非常強力，而且泛化能力非常優秀，但速度差一些，如ECO目前位於tracking領域的頂端。總結：相關濾波性能的提升離不開深度學習。
2. 左邊是深度學習Deap Learning，採用CNN+end2end traning，也可以分兩小類：以精度為主從CNN-SVM到MDNet，及擴展TCNN, ADNet, SANet，在測試集上可以比肩頂尖相關濾波演算法，但由於訓練集的限制，泛化能力可能尚有疑問（具體情況請等待VOT 2017的結果，去年的冠軍TCNN沒中任何會議~~）；速度為主的SiamFC，及擴展DCFNet, CFNet和HART，在GPU上能達到遠超實時的速度，尤其DCFNet和CFNet引入CF layer，相關濾波在CNN框架中實現end2end訓練，讓卷積特徵提取可以配合相關濾波檢測，實現聯動，讓CNN框架也可以實現密集檢測，精度和速度都能達到較高水平。總結：深度學習框架中可以加入相關濾波層端到端訓練。

綜上，CF和DL已經不是對立關係了，互相融合互相促進是發展方向，或許已不存在兩大陣營。

目前tracking領域亟待解決的難題，僅供參考：

1. 以HOG特徵為代表的相關濾波可以做到很快的速度，但HOG特徵的旋轉不變性很差，也就是說這類演算法對平面類旋轉基本無解。MD大神最新論文DCCO證明深層卷積特徵具有較好的旋轉不變性，但引入卷積特徵會損失速度優勢。如何保證速度的同時解決平面旋轉問題？
2. 不管是卷積特徵和端到端訓練的CNN框架，速度都是硬傷，forward passing time是設計網路的關鍵，搭建小網路代替常用的VGG-16以期實現CPU上實時，CNN模型的壓縮加速是目前研究的熱點之一；但CNN需要海量訓練數據，目前缺乏這樣的資料庫，做到訓練集和測試集嚴格獨立，才能保證演算法的泛化能力。如果引入深度學習後解決CPU上無法實時的問題？

ICCV 2017的相關論文過段時間再來分析，等VOT2017的結果出來吧，到時候論文代碼也應該就開源了，也留給我時間慢慢讀論文。。

最近專欄更新比較慢，一半是VOT結果還是沒出，另一半是我在學習其他方向，要與時俱進還是很不容易的。如果有必要，我也會和大家分享一些其他方向的乾貨論文，感謝支持。

***********************************分割線********************************

速度優化trick

很多人問我速度怎麼優化，真的沒有什麼秘密。這裡介紹一個在C-COT和ECO中大量使用的加速方法，保守估計該trick的加速比在20%以上，而且是完全沒有任何性能損失的trick，但在這兩篇論文中完全沒有提到，下面這段話來自C-COT的Supplementary Material：

Since the Fourier coefficients of a real function obey the Hermitian symmetry, we only need to process half the Fourier coefficients 0 ≤ k ≤ K. This effectively halves the computations and memory consumption of the training procedure.

相關濾波速度的來源之一就是濾波操作在傅里葉域進行，這一加速trick簡單來說就是利用實數傅里葉譜的共軛對稱性減少一半的計算量和內存消耗。

從基礎開始介紹。首先來分析圖像的傅里葉係數：

clearnclose allnnfys = imread(fys.bmp);nimg = rgb2gray(fys);nfigure(1),nsubplot(1,2,1),imshow(fys,[]);nsubplot(1,2,2),imshow(img,[]);nnfc = fft2(double(img));nfigure(2),nsubplot(1,3,1),imshow(log(real(fc)),[]);nsubplot(1,3,2),imshow(log(imag(fc)),[]);nsubplot(1,3,3),imshow(log(real(fc).^2 + imag(fc).^2),[]);nnfcc = fftshift(fc);nfigure(3),nsubplot(1,3,1),imshow(log(real(fcc)),[]);nsubplot(1,3,2),imshow(log(imag(fcc)),[]);nsubplot(1,3,3),imshow(log(real(fcc).^2 + imag(fcc).^2),[]);n

結果如下，首先是讀入圖像並灰度化：

然後計算傅里葉譜並顯示，依次是實部，虛部和幅值，這時候傅里葉譜的中心在左上角點，這時候可能很難看出對稱性：

fftshift移頻操作，將中心移動到圖像中心，這時候對稱性就非常清晰了，注意是共軛對稱性：

所以C-COT和ECO在計算圖像特徵的fft時會多了fftshift移頻操作，傅里葉正變換被封裝成這樣：

function xf = cfft2(x)nn% Find the data typendata_type_complex = complex(zeros(1, like, x));nn% calculate output sizenin_sz = size(x);nn% if both dimensions are oddnif all(mod(in_sz(1:2), 2) == 1)n xf = fftshift(fftshift(fft2(x), 1), 2);nelsen out_sz = in_sz;n out_sz(1:2) = out_sz(1:2) + mod(out_sz(1:2)+1,2);nn % allocaten xf = zeros(out_sz, like, data_type_complex);nn xf(1:in_sz(1),1:in_sz(2),:,:) = fftshift(fftshift(fft2(x), 1), 2);nn if out_sz(1) ~= in_sz(1)n xf(end,:,:,:) = conj(xf(1,end:-1:1,:,:));n endn if out_sz(2) ~= in_sz(2)n xf(:,end,:,:) = conj(xf(end:-1:1,1,:,:));n endnendn

傅里葉逆變化被封裝成這樣：

function x = cifft2(xf)nnif isa(xf, gpuArray)n x = real(ifft2(ifftshift(ifftshift(xf, 1), 2)));nelsen x = ifft2(ifftshift(ifftshift(xf, 1), 2), symmetric);nendn

有了對稱性，接下來在所有頻譜計算都只需要計算頻譜的一半，這部分直接降低計算量50%，特徵的頻譜係數在經過一些列預處理以後，直接壓縮為緊湊傅里葉係數如下代碼：

function xf = compact_fourier_coeff(xf)nn% Creates a compact fourier series representation by removing the strict rightn% half plane.nnif iscell(xf)n xf = cellfun(@(xf) xf(:,1size(xf,2)+1)/2,:), xf, uniformoutput, false);nelsen xf = xf(:,1size(xf,2)+1)/2,:);nendn

最後，計算好濾波器的頻譜係數之後，根據共軛對稱性補全頻譜係數就可以了，頻譜重構如下代碼：

function xf = full_fourier_coeff(xf)nn% Reconstructs the full Fourier series coefficients.nnif iscell(xf)n xf = cellfun(@(xf) cat(2, xf, conj(rot90(xf(:,1:end-1,:), 2))), xf, uniformoutput, false);nelsen xf = cat(2, xf, conj(rot90(xf(:,1:end-1,:), 2)));nendn

就是這麼簡單，這麼NIUBILITY，沒有任何代價的相關濾波加速技巧，並沒有出現的論文中，或許他認為太簡單了，MD大神只在C-COT的Supplementary Material 中section 3 的最後提了一下。

只要是相關濾波演算法，這一trick就是普適的，沒有理由不用，LETS MOVE!

**********************************分割線********************************

相關濾波的直觀解釋

近期一直在思考，如何以簡單易懂的方式向他人解釋相關濾波是什麼，為什麼能夠在tracking任務中work？以下是我參考各位大神的網上資源，給出的一種比較形象但並不嚴謹的思路，寫下來供大家參考，或許對理解相關濾波有點幫助。

乘積和：最簡單的相似度度量。將兩個離散信號對應位置相乘，結果越大，說明兩個信號越相似。單一數值的信號為例：

1. 兩個正數相乘或兩個負數相乘，結果都是正數；一正一負相乘，結果是負數。符號一致的信號相似度肯定比符號相反的信號更相似，對應乘積越大，滿足以上結論。
2. （5*5=25） > （4*6=24） > （3*7=21）。平均值相等的一組信號，兩個數值越接近的信號肯定越相似，對應乘積越大，也滿足以上結論。

這就是最簡單的信號相似度度量方法。如果是兩個一維或者二維離散信號，對應位置的數值相乘，再將所有乘積求和，乘積和就可用於表示這兩個信號的相似度。

常用的線性相關係數就有類似定義：

注意多了去均值和歸一化。

信號相關。為了方便理解，這裡只分析離散信號，連續信號積分相當於離散信號求和，就不重複說明了。離散信號x(t)和離散信號y(t)的互相關h的定義如下：

通過詳細分解各項可以看出，離散信號h中每一項的值h(a)，都是信號x和平移a單位後的信號y之間，對應位置離散值的乘積和。上面介紹過這乘積和表示兩個信號之間的相似度，所以得到直觀解釋：信號相關就是兩個信號經各種不同平移之後的相似度。

為什麼要這樣定義呢？舉個例子，要描述sin和cos這兩個離散信號之間的相似度，如果不平移，我們直接計算對應位置離散值的乘積和，只能得到的一個非常小的值，說明相似度很低；但事實上這兩個信號非常相似，根據上面互相關定義，計算不同平移後的乘積和，就能得到一組相似度值，反映不同時延下的相似度，這樣才能更加客觀公正的描述兩個信號的相似性。

信號相關要求計算很多很多次乘積和，速度肯定是難以接受的，萬幸我們有傅里葉變換，空域相關等價於頻域點乘，原本複雜的空域計算流程，轉換為將兩個信號分別傅里葉變換到頻域，然後點乘，結果逆變換回空域，就得到了互相關信號。

推廣到在tracking。將相關的定義推廣到二維，相關濾波類演算法在濾波器訓練和更新階段，通過最優化方法構建這樣一個相關濾波器h，其響應越大能表示與檢測目標越相似：

之後，檢測階段只需要計算相關濾波器和待檢測圖像塊之間的相關性，相關性的定義會幫助我們計算每個循環移點陣圖像塊和相關濾波器之間的相似度，最大響應點代表最相似位置，也就是目標所在的新位置。

傅里葉變換的相關性解釋。傅里葉變換其實就是計算目標信號與不同頻率正弦、餘弦信號的相關性，即傅里葉級數就是目標信號與不同頻率sin、cos信號之間的相似度。下面詳細解釋：傅里葉變換的定義如下圖：

根據wiki上離散傅里葉變換DFT的定義，稍作變形：

傅里葉係數的實部是信號x與不同頻率cos信號的對應位置離散值的乘積和，即x與不同頻率餘弦信號的相似度；

傅里葉係數的虛部是信號x與不同頻率sin信號的對應位置離散值的乘積和，即x與不同頻率正弦信號的相似度；

經過傅里葉變換，目標信號被分解為與一組基信號中每個信號的相似度，基信號包含不同頻率的正弦波和餘弦波。DFT過程與向量在正交坐標繫上的分解可以類比。

空域信號相關等價於頻域點乘，即對應頻率基信號的傅里葉係數相乘，相乘就是計算相似度，結果表示兩個信號在該頻率的相似度。

參考資料：

【圖片】【簡單向】用最簡單易懂的方式實現FFT【c語言吧】_百度貼吧

傅里葉分析之掐死教程（完整版）更新於2014.06.06