計算機視覺研究院專欄
作者：Edison_G
今天帶來的這篇推送，估計您有讀過或試驗過，但是為了讓更多的科研學者知道這麼「牛」的內容知識，接下來就開始說說今天的主題——1000000類的快速精確檢測。
公眾號ID｜ComputerVisionGzq
學習群｜掃碼在主頁獲取加入方式
1 前景概要
今天帶來的這篇推送，估計您有讀過或試驗過，但是為了讓更多的科研學者知道這麼「牛」的內容知識，接下來就開始說說今天的主題——1000000類的快速精確檢測。
註：內容選於dengyafeng的博客
今天的主題最引起關注的是「1000000類」，比Base Line快了將近2000倍。但是任何一個好的東西都會有美中不足之處，之後我們在討論其缺陷。
今天說的這個模型主要優勢在於速度快，具體就是對於多類檢測問題，檢測速度可以做到和類別數目無關。
對於包含C類的物體檢測而言，一個基本的框架是，訓練C個分類器，對於每個候選位置，用每個分類器都判定一遍，然後做後處理融合。這樣的壞處就是速度太慢，處理速度和物體類別成反比。
今天說講的內容參考的Base Line算法是DPM模型，就是每個物體的模型由多個part（假定P個）的模型組成，每個part的模型可以看作是一個filter和該位置特徵的點積（整體上可以看作是一個convolution過程），然後根據可能的part候選的位置約束確定物體的位置。在實際中，最耗時的是convolution過程，每個物體分類器的filter（對應weight）都需要和候選位置的特徵進行一次點積處理，假定候選窗口數目為W個，候選窗口的feature dimension是M維，則運算複雜度為W*C*P*M。
今天講的內容工作者利用了之前的一個工作結果，可以將兩個向量的點積（其實點積和cos距離有非常強的關聯，如果預先對參與cos距離運算的兩個向量進行模的歸一化處理，則歸一化後兩向量的cos距離和點積是相同的）相似度轉化為兩個hash值的hamming距離。
距離將feature轉換為lsh hash的過程如下（得到的hash是LSH hash，也是WTA hash）：假定共M維feature，設K為保留的中間元素數目設定一個重排數組（隨機得到，個數為M，元素為0-M-1，每個元素的序號表示臨時feature對應原始feature中的序號），從而將原始feature轉變為一個臨時feature，取臨時featue的前K維，組成最終的新feature，則新feature中最大元素序號（新feature中）為k，將k表示為一個log(K)位的二進位數字串繼續設定共N個重排數組（隨機得到），則得到共N*log(K)位的二進位串，按照最前面的重排數組對應的串放在最低位的原則，得到一個hash值（N*log(K)位整數）。
對應的，兩個feature之間的點積轉化為兩個對應hash之間的hamming距離。
直觀上看，由於如此得到的數字只和數字之間的相互大小有關，且每次保留最大的序號的信息，因此，對於數字的擾動非常魯棒。因此，得到的兩個hash值之間的hamming距離所對應的相似度對於特徵值的變化更加魯棒，是更有效的表示。
（到底是否是這樣，無從得知，其他信息請參考J. Yagnik, D. Strelow, D. A. Ross, and R.-s. Lin. The powe of comparative reasoning. In IEEE International Conference on Computer Vision, 2011.）
由於計算兩個hash之間的hamming距離非常快速（還可以查表），因此最耗時的部分在計算每個窗口的feature以及計算hash值上，這個運算和類別數目無關。
上述可以用於點積衡量相似度的特徵，可以是各種各樣的特徵，在物體檢測裡面最常用的要數HOG特徵了。
下面以HOG特徵為例，說明Base Line 算法和本文提出的改進之間計算時間的對比：
Base Line算法的計算過程如下：
-
計算多尺度的邊緣強度和邊緣方向圖像；
-
對所有窗口進行遍歷，對於每個窗口，計算其高斯加權HOG直方圖特徵，分別計算HOG特徵和C類P個filter的點積；
-
將具有局部最大響應的窗口作為候選，得到可能的物體中心的分布累積，綜合得到最終的物體檢測結果。
改進算法計算過程如下：
事先計算得到C*P個filter對應的hash值
-
計算多尺度的邊緣強度和邊緣方向圖像；
-
對所有窗口進行遍歷，對於每個窗口，計算其高斯加權HOG直方圖特徵，計算特徵對應的hash值，分別計算HOG特徵hash值和C類P個filter的hash值的hamming距離；
-
將具有局部最大響應的窗口作為候選，得到可能的物體中心的分布累積，綜合得到最終的物體檢測結果。
對比可以看到，由於改進算法中，計算hamming距離的部分非常快，可以忽略，因此，最終得到的多類檢測器的運算量和類別數目無關。
進一步，為了快速運算，可以將上述的hamming距離計算轉換為查表運算，為了當累積相似度高於閾值時無需繼續計算，將hash值劃分為多個不同部分（這樣每個表也比較小）。
將N*log(K) bit的hash分為N/M組(band)，每組是一個M*log(K) bit的整數，對於每個類別每個part的filter（訓練模型），對應N/M組查找表（查找表的序號為當前窗口feature在該band上的hash值，查找表記錄的值為該featurehash值和模型hash值的相似度），從而避免了hamming距離計算過程。每個filter取到的N/M組查找表的值的累積和為對應的點積值（相似度）。對N/M組累積和計算，當計算發現相似度大於閾值時，則放棄後面的運算，直接對預估物體位置分布進行累積。
則最終得到物體位置分布累積最大的位置為檢測得到的物體位置。
提出的框架中還有一點值得討論的地方在於，100000類數據都是搜尋引擎爬取的，沒有經過人工標定，所以結果存在一定不準確的地方。但是定性上看，這樣做確實快了很多。
當然，相對Base Line算法，提出的算法在精度上還是降低一些的（見論文voc 2007的對比結果,mAP由0.26->0.24）。而耗費的20G內存，推測主要應該是查找表對應的內存。
2 新框架
3 實驗
表1 hash-based算法與Base Line算法準確率比較
從表中可以看出，只有3個表現的比較好，其餘的都表現一般甚至比Base Line更差。
mAP隨hash數量變化的情況
可以看出：
-
隨著hash數量增加，mAP隨之提高，但是到某一數量的時候趨於飽和，該實驗證明了達到了16的時候，效果最好；
-
當K=16時，在5KB/filter，mAP到達飽和，所有當有1000000類時，每類10個filters，則需要5G內存；
-
在5秒每張圖像的條件下，與Base Linr相比，加速將近增加了20倍。
表2 相同內存情況下，執行速度與準確率的關係
三種不同執行時間下，檢測目標數量和mAP的關係
從圖中可以看出：
-
關係曲線呈指數變化趨勢；
-
大概三分之一的樣本集的準確率為0.20;
-
大概五分之一的樣本集的準確率為0.30。
t=8時，檢測準確率最高的6中物體
在PASCAL VOC2007數據集中，內存給定，不同執行時間下，增加目標類，準確率的變化情況。
從上圖可以看出：執行速度越快，準確率越低。隨著類數增加，準確率迅速下降，這是由於哈希衝突或者哈希表的信息量達到飽和，值得注意的是紅色曲線，mAP下降最少，說明當增加計算時間後，hashing-base檢測器檢測大數據量級的目標類是可行的。
之前有提及框架的缺點，現在說說其缺點所在：
因為是在單機上進行類別檢測，所以速度不是很理想，單機處理一張圖像的速度需要20s，而且1000000類的mAP是0.16，從數據上看是很理想，但是距離實用性還有很長的距離。
4 啟發
-
這個思路，對於基本操作為點積（x*y）運算的，都可以加速，這個操作非常常見，比如線性SVM，COS距離，以及神經網絡和LR裡面的WX等等，都可以使用。一個比較容易想到的是可以應用於multi-model檢測框架中（比如多類別物體檢測，多姿態人臉/汽車檢測等等）；
-
對於多模型檢測，速度是一個非常重要的方面，一般的思路就是在提高單個模型速度（feature和分類器計算速度）的情況下，增加特徵共用（LAB feature image, vector boosting），其實，最理想的特徵共用是deep learning模型（只在最後一層不同，其它層都是共用的，每個隱節點可以看作是feature，所有類別共用feature，只在輸出層時，計算一個wh+b項，是非常理想的特徵共用），只可惜單個deep learning模型太慢，當遍歷多個檢測候選窗口時，最終的速度現在看太慢了。
補充：其實這個方法可能用於加速神經網絡模型（當然包括deep learning），難點在於點積變為hash距離的近似比較大，未必會有好的結果。
© THE END
轉載請聯繫本公眾號獲得授權
計算機視覺研究院學習群等你加入！
計算機視覺研究院主要涉及深度學習領域，主要致力於人臉檢測、人臉識別，多目標檢測、目標跟蹤、圖像分割等研究方向。研究院接下來會不斷分享最新的論文算法新框架，我們這次改革不同點就是，我們要著重」研究「。之後我們會針對相應領域分享實踐過程，讓大家真正體會擺脫理論的真實場景，培養愛動手編程愛動腦思考的習慣！
計算機視覺研究院
公眾號ID｜ComputerVisionGzq