邊界效應與VOT2015

光陰荏苒歲月如流時間到了2015年，VOT2015競賽 VOT2015 Challenge | Home 如期而至，這一年有60個精挑細選的序列，62個tracker，最大看點是深度學習開始進擊tracking，MDNet直接拿下當年的冠軍，而結合深度特徵的相關濾波方法DeepSRDCF是第二名，主要解決邊界效應的SRDCF僅HOG特徵排在第四：

隨著VOT競賽的影響力擴大，舉辦方也是用心良苦，經典的和頂尖的齊聚一堂，百家爭鳴，多達62個tracker皇城PK，華山論劍。除了前面介紹的深度學習和相關濾波，還有結合object proposals(類物體區域檢測)的EBT(EBT：Proposal與Tracking不得不說的秘密 - 知乎專欄)排第三，Mean-Shift類顏色演算法ASMS是推薦實時演算法，還請注意另一個顏色演算法DAT，而第9的那個Struck已經不是OTB中的那個了。除此之外，你還能看到各種博文力推主打的CT (12ECCV)和STC (14ECCV)，分別排倒數第6和第8，還有其他經典演算法如OAB, IVT, NCC等，就目前（2017.5）以表格結果來說，這些演算法性能和速度都算比較差的，值得參考學習，但我不推薦這兩個演算法，更不推薦您用在產品中，當然，至少這個結果也可以證明VOT競賽非常激烈，就連CT和STC也只能排倒數。如果您不認可OTB和VOT的結果，權當瞎說，隨便看看就好。

接下來主要介紹相關濾波的邊界效應及解決方案，僅適合需要改進相關濾波類演算法或者需要對相關濾波演算法有更高要求的同學看，寫出來是為了全面，而且後續改進都是以犧牲幀率為代價的，效果雖好但很多演算法都無法實時了(任何演算法(人)都有優缺點，適合(你)的才是最好的)。

總體來說，相關濾波類方法對快速變形和快速運動情況的跟蹤效果不好。

快速變形主要因為CF是模板類方法。容易跟丟這個比較好理解，前面分析了相關濾波是模板類方法，如果目標快速變形，那基於HOG的梯度模板肯定就跟不上了，如果快速變色，那基於CN的顏色模板肯定也就跟不上了。這個還和模型更新策略與更新速度有關，固定學習率的線性加權更新，如果學習率太大，部分或短暫遮擋和任何檢測不準確，模型就會學習到背景信息，積累到一定程度模型跟著背景私奔了，一去不復返。如果學習率太小，目標已經變形了而模板還是那個模板，就會變得不認識目標。(舉個例子，多年不見的同學，你很可能就認不出了，而經常見面的同學，即使變化很大你也認識，因為常見的同學在你大腦裡面的模型在持續更新，而多年不見就是很久不更新)

快速運動主要是邊界效應(Boundary Effets)，而且邊界效應產生的錯誤樣本會造成分類器判別力不夠強，下面分訓練階段和檢測階段分別討論。

訓練階段，合成樣本降低了判別能力。如果不加餘弦窗，那麼移位樣本是長這樣的：

除了那個最原始樣本，其他樣本都是「合成」的，100*100的圖像塊，只有1/10000的樣本是真實的，這樣的樣本集根本不能拿來訓練。如果加了餘弦窗，由於圖像邊緣像素值都是0，循環移位過程中只要目標保持完整那這個樣本就是合理的，只有目標中心接近邊緣時，目標跨越邊界的那些樣本是錯誤的，這樣雖不真實但合理的樣本數量增加到了大約2/3(padding= 1)，即使這樣仍然有1/3(3000/10000)的樣本是不合理的，這些樣本會降低分類器的判別能力。再者，加餘弦窗不是「免費的」，餘弦窗將圖像塊的邊緣區域像素全部變成0，大量過濾掉分類器本來非常需要學習的背景信息，原本訓練時判別器能看到的背景信息就非常有限，我們還加了個餘弦窗擋住了背景，這樣進一步降低了分類器的判別力(是不是上帝在我前遮住了簾。。不是上帝，是餘弦窗)。

檢測階段，相關濾波對快速運動的目標檢測比較乏力。相關濾波訓練的圖像塊和檢測的圖像塊大小必須是一樣的，這就是說你訓練了一個100*100的濾波器，那你也只能檢測100*100的區域，如果打算通過加更大的padding來擴展檢測區域，那樣除了擴展了複雜度，並不會有什麼好處。目標運動可能是目標自身移動，或攝像機移動，按照目標在檢測區域的位置分四種情況來看：

1. 如果目標在中心附近，檢測準確且成功。

2. 如果目標移動到了邊界附近但還沒有出邊界，加了餘弦窗以後，部分目標像素會被過濾掉，這時候就沒法保證這裡的響應是全局最大的，而且，這時候的檢測樣本和訓練過程中的那些不合理樣本很像，所以很可能會失敗。

3. 如果目標的一部分已經移出了這個區域，而我們還要加餘弦窗，很可能就過濾掉了僅存的目標像素，檢測失敗。

4. 如果整個目標已經位移出了這個區域，那肯定就檢測失敗了。

以上就是邊界效應(Boundary Effets)，接下來簡單介紹解決邊界效應的方法，再次強調這些方法速度比較慢，相關濾波傲視群雄的高速已經不見了，但換來了可以匹敵深度學習方法的性能。

首先是VOT2015中最亮眼的相關濾波方法，Martin Danelljan大牛的SRDCF Learning Spatially Regularized Correlation Filters for Visual Tracking，主要思路：既然邊界效應發生在邊界附近，那就忽略所有移位樣本的邊界部分像素，或者說讓邊界附近濾波器係數為接近零：

• Danelljan M, Hager G, Shahbaz Khan F, et al. Learning spatially regularized correlation filters for visual tracking [C]// ICCV. 2015.

SRDCF基於DCF，類SAMF多尺度，採用更大的檢測區域(padding = 4)，同時加入空域正則化，懲罰邊界區域的濾波器係數，優化目標如下：

空域正則化函數w，傳統DCF響應和SRDCF響應對比圖如下(來自論文)：

邊界效應發生在原始樣本目標中心循環移位到邊緣附近時，所以越靠近邊緣區域，正則化係數越大，懲罰並抑制這裡的濾波器係數(有意忽略邊界附近的樣本值)。注意區分餘弦窗是加在原始圖像塊上的，之後進行移位產生樣本集；而空域正則化是加在樣本集中每個移位樣本上的。加正則項這種方法屬於傷筋動骨類方法，破壞了DCF的封閉解，所以SRDCF採用高斯-塞德爾方法迭代求解最優化，這也是是導致SRDCF比較慢的原因。padding=4檢測和訓練圖像塊更大，為了減小計算量SRDCF控制濾波器的大小不超過50*50，雖然速度只有5FPS，但實測對快速運動的提升非常明顯。

另一種方法是Hamed Kiani(前面提到過他MCCF，這位大牛專註改進MOSSE，好像世界的塵囂和他沒有一點關係)提出的基於灰度特徵MOSSE的CFLM Correlation Filters with Limited Boundaries 和基於HOG特徵的BACF，主要思路是採用較大尺寸檢測圖像塊和較小尺寸濾波器來提高真實樣本的比例，或者說濾波器填充0以保持和檢測圖像一樣大：

• Kiani Galoogahi H, Sim T, Lucey S. Correlation filters with limited boundaries [C]// CVPR, 2015.

• Kiani Galoogahi H,, Fagg A, Lucey S. Learning Background-Aware Correlation Filters for Visual Tracking [C]// arXiv preprint arXiv:1703.04590, 2017.

首先採用更大的檢測和訓練圖像塊，然後給循環移位樣本左乘一個0和1組成的掩膜矩陣P，以使真實訓練樣本的比例增加，優化目標如下：

掩膜矩陣其實就是從大圖像塊的循環移位樣本中裁切小圖像塊，一維樣本為例來說明：

5*1的原始樣本，經過循環移位產生5個新樣本，只有第五個是真實的，其他都是「合成」的，真實樣本數/總樣本數 = 1/5；給所有移位樣本左乘一個掩膜矩陣P後，雖然樣本尺寸變小為3*1，但第三、四、五都是真實樣本，真實樣本數/總樣本數 = 3/5，只有第一、二樣本有邊界效應，相當於裁切出了前三行。這就是從大尺寸樣本的循環移位樣本集中用掩膜矩陣裁切出真實的小尺寸樣本，提升真實樣本的比例，而且這樣的掩膜矩陣不止一個，P的循環移位矩陣也有類似效果，即P指定裁切哪個區域，而裁切不同區域的圖像塊都能提升這個真實樣本比例，而且原始樣本越大，裁切後樣本越小，則真實樣本比例越高。

CFLM和BACF都屬於傷筋動骨類方法，沒有閉合解，採用Alternating Direction Method of Multipliers(ADMM)迭代求解最優化。按照論文，僅灰度特徵的CFLM是基於MOSSE的，加了2倍padding用於裁切出原始目標大小的圖像塊(即相當於裁切後不加padding)，雖然性能真的很差，但速度有87.1FPS，而多通道HOG特徵的BACF，加入類SAMF多尺度，性能全面超過SRDCF，在OTB50上竟然超過了VOT2016排第一名的C-COT，速度竟然有35FPS，感覺比SRDCF方法更有潛力，具體細節等作者公開代碼實測 Hamed Kiani ，推薦先實測如果比較好再使用。

其實可以看出來這兩個解決方案挺像的，都出現在2015年，都是用更大的檢測區域，訓練作用域比較小的相關濾波器，要麼從中心到邊緣逐漸衰減到0，要麼在濾波器以外區域填充0。

在VOT2015中還有排在第二名的另一篇相關濾波方法，結合深度特徵的DeepSRDCF，因為深度特徵都非常慢，在CPU上別說高速，實時都到不了，所以放在最後面，和HCF、C-COT、最新ECO一起討論。
推薦閱讀：