點選藍字關注我們 Spring comes
計算機視覺研究院專欄
作者：Edison_G
掃描二維碼 關注我們
微信公衆号 : 計算機視覺研究院
知乎專欄：計算機視覺戰隊
SPEED-UP OF DETECTION
加速目标檢測一直是一個重要而又具有挑戰性的問題。在過去的20年裡，目标檢測領域已經發展了複雜的加速技術。這些技術大緻可以分為 “ 檢測管道提速 ”、“ 檢測引擎提速 ” 和 “ 數值計算提速 ” 三個層次，如下圖所示。
Feature Map Shared Computation
在目标檢測器的不同計算階段中，特征提取通常占主導地位。對于基于滑動窗的檢測器，計算備援從位置和尺度兩方面入手，其中位置備援是由相鄰視窗之間的重疊造成的，尺度備援是通過相鄰尺度間的特征關聯造成的。
Spatial Computational Redundancy and Speed Up
減少空間計算備援最常用的方法是特征圖共享計算，即，在滑動視窗前隻計算一次整個圖像的特征圖。傳統檢測器的 “ 圖像金字塔 ” 可以看作是一個 “ 特征金字塔 ”。例如，為了加快HOG行人檢測器的速度，研究者通常會将整個輸入圖像的 “ HOG map ” 進行累加，如下圖13所示。
然而，這種方法的缺點也很明顯，即， feature map 分辨率 ( 此 feature map 上滑動視窗的最小步長 ) 将受到單元格大小的限制。如果一個小對象位于兩個單元格之間，那麼所有檢測視窗都可能忽略它。解決這個問題的一個方法是建構一個完整的特征金字塔，這将在後面有介紹。
特征圖共享計算的思想在基于卷積的檢測器中也得到了廣泛的應用。一些相關的著作可以追溯到20世紀90年代。近年來大多數基于CNN的檢測器，例如，SPPNet、Fast-RCNN和Faster-RCNN都采用了類似的思想，實作了數十倍甚至數百倍的加速度。
Scale Computational Redundancy and Speed Up
為了減少尺度計算備援，最成功的方法是直接縮放特征而不是圖像，這種方法首次應用于VJ檢測器。然而，由于模糊效果，這種方法不能直接應用于類似于HOG的特性。對于這個問題，P. Dollar’等人通過廣泛的統計分析發現HOG相鄰尺度與積分通道特征之間存在很強的 ( log-linear ) 相關性。這種相關性可以通過近似相鄰尺度的特征圖來加速特征金字塔的計算。此外，建構 “ 檢測器金字塔 ” 是避免尺度計算備援的另一種方法，即，通過簡單地在一個feature map上滑動多個檢測器來檢測不同尺度的對象，而不是重新縮放圖像或feature。
Speed up of Classifiers
傳統的基于滑動視窗的檢測器，如HOG檢測器和 DPM，由于計算複雜度較低，更喜歡使用線性分類器而不是非線性分類器。核SVM等非線性分類器的檢測精度較高，但同時也帶來較高的計算開銷。作為一種标準的非參數方法，傳統的核函數法沒有固定的計算複雜度。當我們有一個非常大的訓練集時，檢測速度會變得非常慢。
在目标檢測中，有很多方法可以加快核分類器的速度，其中最常用的是“ 模型近似 ”。由于經典 核SVM 的決策邊界隻能由一小組訓練樣本 ( 支援向量 ) 确定，是以推理階段的計算複雜度與支援向量的個數成正比：O(Nsv)。約簡集向量是核SVM 的一種近似方法，其目的是用少量的合成向量來獲得一個等價的決策邊界。另一種提高 核SVM 在目标檢測中的速度的方法是将其決策邊界近似為分段線性形式，進而獲得一個恒定的推理時間。核方法也可以通過稀疏編碼方法來加速。
Cascaded Detection
級聯檢測是一種常用的目标檢測技術。它需要一個粗到精的檢測理念：使用簡單的計算過濾掉大部分簡單的背景視窗，然後用複雜的視窗處理那些更困難的視窗。VJ檢測器是級聯檢測的代表。在此之後，許多後續的經典對象檢測器，如HOG檢測器和DPM，都使用了這種技術來加速。
近年來，級聯檢測也被應用到基于深度學習的檢測器中，特别是針對 “ 大場景中的小對象 ” 的檢測任務，如人臉檢測、行人檢測等。除了算法加速外，級聯檢測還被應用于解決其他問題，如提高對困難樣本的檢測，整合上下文資訊，提高定位精度。
Network Pruning and Quantification
“ 網絡修剪 ” 和 “ 網絡量化 ” 是加速CNN模型的兩種常用技術，前者是指對網絡結構或權值進行修剪以減小其大小，後者是指減少激活值或權值的碼長。
Network Pruning
“ 網絡修剪 ” 的研究最早可以追溯到20世紀80年代。當時，Y. LeCun等人提出了一種稱為 “ 最優腦損傷（optimal brain damage） ” 的方法來壓縮多層感覺器網絡的參數。該方法利用二階導數逼近網絡的損失函數，進而去除一些不重要的權重。基于這一思想，近年來的網絡修剪方法通常采用疊代的訓練和修剪過程，即，在每個訓練階段後隻移除一小部分不重要的權重，并重複這些操作。傳統的網絡剪枝隻是簡單地去除不重要的權值，這可能導緻卷積濾波器中存在一些稀疏連接配接模式，不能直接應用于CNN模型的壓縮。解決這個問題的一個簡單方法是删除整個過濾器而不是獨立的權重。
Network Quantification
近年來網絡量化的研究主要集中在網絡二值化方面，其目的是通過量化網絡的激活值或權值為二進制變量，來加速網絡的速度(例如，0/1)，以便浮點運算轉換為AND，OR，NOT 邏輯運算。網絡二值化可以顯著加快計算速度，并減少網絡的存儲，進而更容易部署到移動裝置上。上述思想的一種可能實作是用最小二乘法通過二進制變量近似卷積。使用多個二進制卷積的線性組合可以得到更精确的近似。此外，一些研究人員進一步開發了GPU加速庫進行二值化計算，獲得了更顯著的加速結果。
Network Distillation
網絡蒸餾是将大型網絡 ( “ 教師網 ” ) 的知識壓縮成小型網絡 ( “ 學生網 ” ) 的一般架構。最近，這一思想被用于加速目标檢測。該思想的一種直接方法是使用教師網來指導 ( 輕量級 ) 學生網的訓練，以便後者可用于加速檢測。另一種方法是對候選區域進行變換，使學生網絡和教師網絡的特征距離最小化。該方法使檢測模型的速度提高了2倍，同時達到了相當的精度。
Lightweight Network Design
最後一組加速基于 CNN 的檢測器的方法是直接設計一個輕量級的網絡，而不是使用現成的檢測引擎。研究人員長期以來一直在探索網絡的正确配置，以便在有限的時間成本下獲得準确性。除了一些通用的設計原則如 “ 更少的通道，更多的層（fewer channels and more layers） ”，近年來也提出了一些其他的方法：1) 分解卷積，2) 群卷積，3) 深度可分離卷積，4) 瓶頸設計，5) 神經結構搜尋。
Factorizing Convolutions
分解卷積是建構輕量級CNN模型最簡單、最直接的方法。有兩類分解方法。
第一類方法是将一個大的卷積濾波器分解成一組空間維數較小的卷積濾波器，如上圖(b)所示。例如，可以将一個7x7過濾器分解為三個3x3過濾器，它們共享相同的接收域，但是後者效率更高。另一個例子是将 k×k 濾波器分解為k×1濾波器和1×k濾波器，這對于非常大的濾波器來說可能更有效，比如15x15。該思想最近被用于目标檢測。
第二類方法是将一大組卷積分解為信道維數較小的兩組，如上圖(c)所示。例如，可以用 d個濾波器近似卷積層，用d'個濾波器 + 一個非線性激活 + 另外d個濾波器 (d'<d)近似有c個通道的特征圖。在這種情況下，原始層的複雜度O(dk^2c)可以降低到 。
Group Convolution
群卷積的目的是通過将特征信道劃分為多個不同的組，然後分别對每個組進行卷積，進而減少卷積層中參數的數量，如上圖(d)所示。如果我們将特征信道平均分成m組，不改變其他構型，理論上卷積的計算複雜度将會降低到原來的1/m 。
Depth-wise Separable Convolution
上圖(e)所示的深度可分離卷積是近年來流行的一種建構輕量級卷積網絡的方法。當組數等于信道數時，它可以看作是群卷積的一個特例。
假設我們有一個帶有d個濾波器的卷積層，和一個 c 通道的特征圖。每個濾波器的大小為 k×k 。對于深度可分卷積，每個 k×k×c 濾波器首先被分割成 c 個片，每個片的大小為 k×k×1 ，然後在每個通道中對濾波器的每個片分别進行卷積。最後，一些 1x1 濾波器用于進行次元轉換，以便最終的輸出應該具有 d 通道。利用深度可分卷積，将計算複雜度從O(dk^2c)降低到O(ck^2)+O(dc)。該思想最近被應用于目标檢測和細粒度分類（fine-grain classification）。
Bottle-neck Design
與前一層相比，神經網絡中的瓶頸層隻包含很少的節點。它可以用來學習降維輸入的高效資料編碼，這在深度自編碼中得到了廣泛的應用。近年來，瓶頸設計被廣泛應用于輕量化網絡的設計。在這些方法中，一種常見的方法是壓縮檢測器的輸入層，以減少從檢測管道開始的計算量。另一種方法是壓縮檢測引擎的輸出，使feature map變薄，使其在後續檢測階段更加高效。
Neural Architecture Search
近年來，人們對利用神經結構搜尋 ( NAS ) 自動設計網絡體系結構而不是依賴于專家經驗和知識産生了濃厚的興趣。NAS 已應用于大規模圖像分類，目标檢測和圖像分割任務。NAS 最近在設計輕量級網絡方面也顯示出了很好的結果，其中在搜尋過程中考慮了預測精度和計算複雜度的限制。
Numerical Acceleration
在這一節中，我們主要介紹了四種重要的數值加速方法，它們在目标檢測中經常使用：1) 積分圖像加速，2) 頻域加速，3) 矢量量化，4) 降階近似。
Speed Up with Integral Image
積分圖像是圖像進行中的一種重要方法。它有助于快速計算圖像子區域的和。積分圖像的本質是信号進行中卷積的積分微分可分性：
其中，如果dg(x)/dx是一個稀疏信号，那麼卷積可以被方程右邊的部分加速。雖然 VJ 檢測器以積分圖像加速著稱，但在它誕生之前，積分圖像已經被用來加速 CNN 模型，并達到了10倍以上的加速度。
除了上面的例子，積分圖像還可以用來加速目标檢測中更一般的特征，例如顔色直方圖，梯度直方圖等。一個典型的例子就是通過計算積分HOG映射加速HOG。積分HOG映射不是在傳統的積分圖像中積累像素值，而是在圖像中積累梯度方向，如下圖所示。由于cell的直方圖可以看作是某一區域梯度向量的和，利用積分圖像可以計算任意位置和大小的矩形區域的直方圖，計算開銷是恒定的。積分HOG映射已被應用于行人檢測中，并在不損失任何精度的前提下實作了數十倍的加速度。
2009年晚些時候，P. Dollar’等人提出了一種新的圖像特征，稱為積分通道特征 ( ICF )，可以認為是積分圖像特征的一種更為普遍的情況，并已成功應用于行人檢測。ICF 在其所處的時間内，以接近實時的檢測速度實作了最先進的檢測精度。
Speed Up in Frequency Domain
卷積是目标檢測中的一種重要的數值運算形式。由于線性檢測器的檢測可以看作是特征圖與檢測器權值之間的視窗内積，是以該過程可以通過卷積來實作。
卷積可以在很多方面得到加速，傅裡葉變換是一個非常實用的選擇尤其是對于加速那些大的濾波器。頻域加速卷積的理論基礎是信号進行中的卷積定理，即在合适的條件下，兩個信号卷積的傅裡葉變換是其傅裡葉空間的點乘：
其中，F是傅裡葉變換，F-1是傅裡葉反變換，I和W是輸入圖像和濾波器，是卷積運算，是點乘運算。利用快速傅裡葉變換 ( Fast Fourier Transform，FFT )和快速傅裡葉反變換 ( Inverse Fast Fourier Transform，IFFT )可以加速上述計算。FFT 和 IFFT 現在經常被用來加速 CNN 模型和一些經典的線性目标檢測器，這使得檢測速度提高了一個數量級。下圖為在頻域中加速線性目标檢測器的标準管道 ( 如 HOG 和 DPM )。
Vector Quantization
矢量量化 ( VQ ) 是信号進行中的一種經典的量化方法，其目的是通過一組小的原型矢量來近似一組大資料的分布。它可用于資料壓縮和加速目标檢測中的内積運算。例如，使用VQ，可以将HOG直方圖分組并量化為一組原型直方圖向量。然後在檢測階段，通過查表操作實作特征向量與檢測權值之間的内積。由于該過程中沒有浮點乘法和除法，是以DPM和例化SVM檢測器（exemplar SVM detector）的速度可以提高一個數量級。
Reduced Rank Approximation
在深度網絡中，全連接配接層的計算本質上是兩個矩陣的乘法。當參數矩陣W較大時，檢測器的計算量較大。例如，在Fast RCNN檢測器中，将近一半的前向傳遞時間用于計算全連接配接層。降秩近似是一種加速矩陣乘法的方法。它的目的是對矩陣W進行低秩分解：
其中，U是由W的第一個t左奇異向量構成的u x t矩陣，∑t是一個包含W前t個奇異值的t x t對角矩陣，V是由W的第一個t右奇異向量構成的v x t矩陣。上述過程也稱為截斷 SVD（Truncated SVD），将參數uv從減少到t x (u+v)，當t遠小于min(u,v)時效果顯著。截斷 SVD 被用來加速 Fast RCNN 檢測器，達到 x2 的速度。
感謝
Zhengxia Zou等人的無私貢獻，本系列綜述引用于《Object Detection in 20 Years: A Survey》，有興趣的同學可以下載下傳慢慢品！
通知
計算機視覺戰隊正在組建深度學習技術群，歡迎大家私信申請加入！
加入“計算機視覺戰隊”，一起學習！
／End.
我們開創“計算機視覺協會”知識星球一年有餘，也得到很多同學的認可，我們定時會推送實踐型内容與大家分享，在星球裡的同學可以随時提問，随時提需求，我們都會及時給予回複及給出對應的答複。
如果想加入我們“計算機視覺研究院”，請掃二維碼加入我們。我們會按照你的需求将你拉入對應的學習群！
計算機視覺研究院主要涉及深度學習領域，主要緻力于人臉檢測、人臉識别，多目标檢測、目标跟蹤、圖像分割等研究方向。研究院接下來會不斷分享最新的論文算法新架構，我們這次改革不同點就是，我們要着重”研究“。之後我們會針對相應領域分享實踐過程，讓大家真正體會擺脫理論的真實場景，培養愛動手程式設計愛動腦思考的習慣！
計算機視覺研究院
長按掃描二維碼關注我們