EBT：Proposal與Tracking不得不說的秘密

01-25

感謝MM Wang邀請，開門見山。我來給大家分享下面這篇不太火爆的論文：

Zhu G, Porikli F, Li H. Beyond local search: Tracking objects everywhere with instance-specific proposals [C]// CVPR, 2016.

作者只給了實驗結果：GaoCode/EBT

VOT2016也只給了exe：http://www.votchallenge.net/vot2016/download/02_EBT.zip

直說吧，這是一篇沒有源碼的論文！我也一樣失望，exe配置比較麻煩也沒有跑過，原則上，沒有源碼的論文我內心是拒絕的，除非是大公司出品。。但這篇我就很有興趣了，主要是因為EBT在VOT競賽上的不凡表現。

在VOT2015是它第三名，在SRDCF之前，R(Robustness，健壯性)排第二：

在VOT2016它是第七名，Robustness這一指標依然很高排第三，Rrank竟然並列第一：

看到這裡您是不是也對這個Accuracy略低但Robustness爆高的偏科演算法有了一點興趣呢？

為防止您以前沒有看過這篇論文，以後也可能不會看(沒有SOURCE CODE)，這裡總體介紹一下EBT：

大多數檢測跟蹤方法(tracking-by-detection)，都假設前一幀跟蹤位置準確、目標運動軌跡平滑，當前幀在預測目標位置周圍進行局部窗搜索，採用計算能力允許的搜索半徑以獲得最大速度，半徑足夠小以減少誤匹配，但這一假設在變形遮擋，目標快速和不規則運動，尤其是目標超出搜索半徑時失效。
EBT跟蹤演算法，不局限於局部搜索窗，能夠高效搜索整幀，通過特例的類物體度量(instance-specific objectness measure)，生成少量「高質量」的提案(proposals)，用以現有檢測跟蹤方法為核心的tracker對它們進行評估。
在跟蹤過程中，關注由proposals提供的難誤檢樣本更新目標模型，有助於抑制困難背景雜波引起的干擾，並學習如何根據目標模型重排proposals。
由於大幅減少了需要tracker評估的候選樣本，EBT可以用更豐富的目標特徵和更強的分類器。

估計您已經看出來了，請原諒我翻譯了四句摘要。從摘要中我們得到兩個關鍵信息：

目的：整幀搜索代替局部搜索窗，這可能就是Robustness的源頭
方法：proposals減少候選樣本，作者好像還做了重排是創新點

tracking-by-detection都採用局部搜索，原因是：1. 全局搜索樣本數量會非常大，計算能力不允許；2. 圖像中有多個類似目標的物體時，背景干擾嚴重導致飄逸，而局部搜索可以避免較遠距離的背景干擾。相關濾波Corr. Filter的循環矩陣密集採樣在搜索半徑很大時非常慢，不適用於很大的負樣本空間。總的來說，局部搜索有很多缺點，tracking-by-detection類方法，尤其是相關濾波，對快速運動目標很難處理，所以EBT採用proposals進行整幀搜索解決這個問題。

就是這樣，如果您恰好了解object/detection/region proposal(類物體區域檢測，我傾向於這個翻譯，如果您有其他譯法歡迎討論)，想必您已經明白是怎麼回事了。如果您不是很了解，那麼請聽我細細道來，之後就很容易理解EBT到底幹了什麼。

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

話分兩頭。以前文章我也提到過，tracking-by-detection類跟蹤演算法就是比較「弱」的檢測演算法，跟蹤和檢測演算法都需要以多尺度滑窗(Multi-scale Sliding Window)的方式去檢測目標。做過檢測的都知道這種滑窗遍歷有多慢，如640*480的圖像，用已經訓練好的貓檢測器進行檢測，最小窗大小64*128，尺度縮放比例1.1，滑窗步長8，那麼需要對13473個候選樣本提特徵並判別是否有貓(以上數據來自博文)，如果為了檢測更加精細準確，需要同時減小縮放比例和滑窗步長，候選窗(樣本)數量將劇增，檢測速度必然會非常慢。在跟蹤問題中也一樣，如果我們擴大搜索區域，甚至整幀搜索，那需要檢測和更新的候選樣本數量就會非常非常恐怖，問題來了：那麼有沒有辦法減少候選樣本的數量，加速檢測和更新呢？

回到檢測問題，要在下面這幅圖中檢測貓，您可能會和我有一樣的看法：只需要多尺度滑窗檢測右半邊圖像，而左半邊完全可以忽略(紅框內部分連紋理都沒有，更別說貓了)。更直觀的感受是：如果某些候選樣本沒有紋理或者紋理很少，那就不太可能包含目標，我們就沒有必要滑窗檢測，再或者，如果我們的檢測目標是白貓，那圖像中大片深色區域就沒必要檢測。可見用一些簡單的約束就能排除那些完全沒有可能的區域，專業說法是，用簡單的分類器就能排除一些可能性極低完全沒必要檢測的候選樣本，這裡介紹兩種比較常見的檢測加速方法：cascade和proposal。(其實我就知道這兩種 -_-!，歡迎補充)

Cascade Classifier 級聯分類器：以VJ人臉檢測為例，訓練多個複雜度不一樣的分類器，先用最簡單也最快的分類器排除那些絕對不可能是人臉的候選窗，再用稍微複雜一點但也很快的分類器排除剩餘候選窗中不可能是人臉的那部分，以此類推，最後由那個最複雜最慢但最可靠的分類器確定經過層層篩選留下來的少量候選窗中有沒有人臉。在VJ中分類器用了boosting集成線性分類器，boosting集弱成強(強調任何弱分類器都可以經Boosting集成)，集成的線性分類器越多，判別力就越強但也越慢，可以非常方便地控制分類器複雜度和速度。級聯分類器用簡單快速的前端分類器過濾掉大量「低質量」的候選窗，從而提高檢測能力並有效控制計算量。

Viola P, Jones M. Rapid object detection using a boosted cascade of simple features [C]// CVPR, 2001.

Object/Detection Proposal 類物體區域檢測：以R-CNN為例，如果直接以多尺度滑窗方式，用ImageNet上訓練的CNN去做分類，速度絕對讓人抓狂(太~~慢~~~了~~~~)，RGB大神用region proposals加速檢測，流程如下圖：輸入圖像，首先用類物體區域檢測(這裡是Selective Search)生成~2k個類物體區域，然後依次對每個區域提取CNN特徵，再用SVM去分類識別就可以了。這樣不僅可以大幅提高速度，而且降低了誤檢率，因為那些沒有包含完整物體的候選窗連進入分類器的機會都沒有，更不可能分類錯誤了。

Girshick R, Donahue J, Darrell T, et al. Rich feature hierarchies for accurate object detection and semantic segmentation [C]// CVPR, 2014.

可以看出，Cascade和Proposal都用簡單方法過濾掉那些「低質量」的候選窗，從而提高檢測速度，不同點在於，Proposal是普適的，目標是過濾掉那些不包含完整物體的候選窗，而Cascade是針對特定任務專門訓練的，目標是過濾掉不可能包含檢測目標的候選窗。接下來簡單介紹幾個Object/Detection Proposal方法。

Selective Search：貪婪合併超像素生成proposals，沒有學習參數，手工設計特徵和相似度函數用於聚合超像素。特點是被RGB大神欽點過。

Uijlings J R R, Van De Sande K E A, Gevers T, et al. Selective search for object recognition [J]. IJCV, 2013.

BING：作者大家都很熟悉，出發點是具有明確邊界的通用對象可以通過觀察歸一化梯度來辨別。在邊緣特徵上訓練簡單分類器，以滑窗方式檢測類物體區域，特徵是專門設計的二值標準化梯度(BING)，分類器是linear SVM(強調SVM可以沒有kernal-trick)。特點是速度非常快，CPU上300fps，BING採用簡單分類器非常類似Cascade中的前端分類器。當然BING還是有點爭議的，如果您也喜歡看熱鬧，請自行搜索「Cracking bing and beyond」這篇論文。

Cheng M M, Zhang Z, Lin W Y, et al. BING: Binarized normed gradients for objectness estimation at 300fps [C]// CVPR, 2014.

EdgeBoxes：出發點是邊界框中包含完整輪廓的數量是邊界框包含物體的可能性指標，邊緣輪廓檢測之後，滑窗遍歷計算每個邊界框包含的輪廓數量得到類物體分數，最後返回分數最高的部分候選框(論文中~1k)。EdgeBoxes沒有學習參數，召回率和速度都不錯。這個作者就更厲害了，如果您不知道Piotr Dollár是誰，請回想一下您所用的fHOG。特點：我覺得這個方法最厲害，這也是EBT為什麼叫EBT的原因(EdgeBoxes Tracker)。

Zitnick C L, Dollár P. Edge boxes: Locating object proposals from edges [C]// ECCV, 2014.

前面介紹比較粗略，因為我也沒有仔細研究過這些方法，建議您有興趣直接看論文。這部分的最後，關於Object/Detection Proposal推薦一篇綜述論文：

Hosang J, Benenson R, Dollár P, et al. What makes for effective detection proposals? [J]. IEEE TPAMI, 2016.

總結和對比了從2010年Objectness到2014年的頂尖proposal方法，結果如下：

可以看出BING最快但性能很低，EdgeBoxes和SelectiveSearch總體性能最好，而EdgeBoxes也很快，所以最佳推薦當然是EdgeBoxes了。再推薦一個資源：Cloud-CV/object-proposals 大部分代碼都在這裡了，請自取~

當然，Object/Detection Proposal是從2010年開始的，發展比較短暫，尤其2014年Multibox就已經宣布深度學習佔領這個方向，到後來Faster R-CNN，用RPN以端到端的方式訓練proposal，獨立模塊的proposal就慢慢被object detection拋棄了。但CNN類proposal速度是硬傷，端到端訓練的網路也難在其他方面應用，最近也沒看到非CNN，速度快還比EdgeBoxes更好的方法出現。(或許只是我不知道，若有~望推薦)

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

終於要介紹EBT了，我自己都等的不耐煩了。簡單來說，EdgeBoxes就是從圖像中得到~1k個候選框，這些框包含物體的概率比較高，而且每個框都有類物體分數(objectness score)，可以簡單理解為這個框包含物體的置信度。有了Object Proposal就不需要多尺度滑窗了，EBT的整幀搜索只需要在排名靠前的200個候選框上進行目標檢測和模型更新，就可以提高幀率。

是不是很簡單？當然不可能這麼簡單，真這麼簡單效果好不好我不知道，但創新度太低論文肯定就要悲劇的。。。

EBT的主要貢獻是前面提到過的訓練特例DE類物體度量(instance-specific objectness measure)對proposals進行重排。通用檢測識別需要考慮所有不同類別不同大小的所有proposals，而目標跟蹤不同，因為跟蹤問題在輪廓和尺寸等幾何結構方面有強烈先驗，所以EBT沒有直接用EdgeBoxes給出的高分proposals，而是訓練分類器對proposals重新打分，根據得分重新排列proposals，然後用於目標檢測和模型更新，此外還加入連續幀平滑項約束決定目標位置。

具體流程：輸入圖像，EdgeBoxes檢測proposals，僅保留objectness scores大於0.005的候選框(樣本)；然後對每個框，在邊緣信息結構圖上計算10維的類Haar小波特徵，如圖(b)所示；接下來，用訓練好的linear SVM分類器對所有proposals重新打分，並重新排序，只取得分最高的200個候選框。linear SVM重排分類器每5幀更新一次，訓練細節請看論文3.3節，其實這個過程就是根據跟蹤目標先驗(特例屬性)，挑選出了那些與跟蹤目標在結構、尺寸方面比較相似的proposals，所以叫Instance-Specific Proposals。

EBT的基礎方法是Struck，檢測階段，只對Instance-Specific Proposals的候選樣本進行檢測，再加入連續幀平滑項約束確定目標位置，本文的公式來了：

最終檢測得分B由分類器響應f和平滑約束項s組成，平滑約束其實就是抑制離上一幀目標位置比較遠的候選框得分，即如果兩個高分候選框，一個位於上一幀目標位置附近，另一個位於距離較遠位置，那我們更加相信比較近的那個框，畢竟太快的快速運動還是比較少的。更新階段，訓練樣本同時採用了Instance-Specific Proposals給的全局候選樣本和目標位置附近的局部樣本(即原始Struck所用訓練樣本，半徑30像素內)，實驗結果表明這樣更好。

實驗結果：沒啥好說的，VOT上的結果已經證明了一切，EBT對快速和無規則運動，尤其是低幀率情況效果非常好。唯一值得一提的是，作者把object proposal方法的換成BING，實驗結果比不用proposal的基礎方法Struck還要差，前面也看到了，主要是BING的召回率太低了。

速度：作者給出基礎Struck是4.8fps，而加了proposals的EBT是4.4fps，單獨Instance-Specific Proposals的部分不到100ms，總體來說EBT是比較慢的方法。

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

總結一下：

EBT給出了proposal結合tracking的有效方法，尤其是Instance-Specific Proposals部分，從適合檢測識別的通用類物體區域檢測，到適合跟蹤的特例類物體區域檢測。
Object Proposal讓整幀搜索成為可能，而且自帶降低誤檢率屬性，這是EBT高Robustness的根本原因。
速度慢，沒source code是硬傷。

最後，感謝您看完，以上大部分是瞎寫的，歡迎批評指針。