目標檢測二十年 | 乾貨（20180319更新）

07-17

「目標檢測是當前計算機視覺和機器學習領域的研究熱點。從Viola-Jones Detector、DPM等冷兵器時代的智慧到當今RCNN、YOLO等深度學習土壤孕育下的GPU暴力美學，整個目標檢測的發展可謂是計算機視覺領域的一部濃縮史。本文簡要回顧了從1994到2017一共二十餘年間目標檢測的發展歷程。」

—

A Road Map

從過去的十多年來看，自然圖像的目標檢測演算法大體上可以分為基於傳統手工特徵的時期（2013之前）以及基於深度學習的目標檢測時期（2013~今），如下圖所示。從技術發展上來講，目標檢測的發展則分別經歷了「包圍框回歸」、「深度神經網路興起」、「多參考窗口（Multi-References，又稱Anchors）」、「難樣本挖掘與聚焦」以及「多尺度多埠檢測」幾個里程碑式的技術進步。下面將分別對這些演算法和其中採用的技術逐一進行介紹。

自然圖像目標檢測演算法發展歷程圖

—

基於經典手工特徵的目標檢測演算法

早期的目標檢測演算法大多是基於手工特徵所構建的。由於在深度學習誕生之前缺乏有效的圖像特徵表達方法，人們不得不盡其所能設計更加多元化的檢測演算法以彌補手工特徵表達能力上的缺陷。同時，由於計算資源的缺乏，人們不得不同時尋找更加精巧的計算方法對模型進行加速。

【代表演算法1】Viola-Jones 檢測器[1]-[2]

【代表演算法2】HOG行人檢測器[3]

【代表演算法3】可變形部件模型[8]-[12]

Viola-Jones檢測器：

2001年Paul Viola和MichaelJones在CVPR上發表了一篇跨時代意義的文章[1]，後人將文章中的人臉檢測演算法稱之為Viola-Jones（VJ）檢測器。VJ檢測器在17年前極為有限的計算資源下第一次實現了人臉的實時檢測，速度是同期檢測演算法的幾十甚至上百倍，極大程度地推動了人臉檢測應用商業化的進程。VJ檢測器的思想深刻地影響了目標檢測領域至少10年的發展。

VJ檢測器採用了最傳統也是最保守的目標檢測手段——滑動窗口檢測，即在圖像中的每一個尺度和每一個像素位置進行遍歷，逐一判斷當前窗口是否為人臉目標。這種思路看似簡單，實則計算開銷巨大。VJ人臉檢測之所以器能夠在有限的計算資源下實現實時檢測，其中有三個關鍵要素：多尺度Haar特徵的快速計算，有效的特徵選擇演算法以及高效的多階段處理策略。

在多尺度Harr特徵快速計算方面，VJ檢測器使用積分圖對特徵提取進行加速。積分圖可以使特徵計算量與窗口的尺寸無關，同時也避免了處理多尺度問題時建圖像金字塔這一耗時的過程。

在特徵選擇演算法方面，與傳統意義上的手工特徵不同的是，VJ檢測器中使用的Harr特徵並非是人為事先設計好的。VJ檢測器使用了過完備的隨機Haar特徵，並通過Adaboost演算法從一個巨大的特徵池（約180k維）中進行特徵選擇，選取出對於人臉檢測最有用的極少數幾種特徵從而降低不必要的計算開銷。

在多階段處理方面，作者提出了級聯決策結構，並將其形象地稱之為「瀑布」（Cascades）。整個檢測器由多級Adaboost決策器組成，每一級決策器又由若干個弱分類決策樁（Decision Stump）組成。瀑布的核心思想是將較少的計算資源分配在背景窗口，而將較多的計算資源分配在目標窗口：如果某一級決策器將當前窗口判定為背景，則無需後續決策就可繼續開始下一個窗口的判斷。

HOG行人檢測器：

HOG特徵最早是為解決行人檢測問題所提出。HOG特徵可以認為是在梯度方向直方圖特徵基礎上的又一次重要改進，是所有基於梯度特徵的目標檢測器的基礎。HOG檢測器是沿用了最原始的多尺度金字塔+滑窗的思路進行檢測。為了檢測不同大小的目標，通常會固定檢測器窗口的大小，並逐次對圖像進行縮放構建多尺度圖像金字塔。為了兼顧速度和性能，HOG檢測器採用的分類器通常為線性分類器[3]或級聯決策分類器[7]等。

在圖像的特徵提取過程中，最重要的兩個概念是不變性（包括平移不變性、旋轉不變性、尺度不變性以及光照不變性等）和區分性（特徵的表達能力）。為了兼顧二者的特點，HOG特徵採用了如下的策略：將圖像所在區域劃分為不同的細胞單元（Cell），並在每個細胞內統計梯度方向直方圖信息。除此之外，為了進一步增強其光照不變性以及非線性表達能力，HOG特徵還首次引入了區塊（Block）的概念，將相鄰的Cell歸併為一個Block，並在Block內對Cell特徵進行局部歸一化。

可變形部件模型：

可變形部件模型（Deformable Part based Model，DPM）是基於經典手工特徵的檢測演算法發展的頂峰，連續獲得VOC07、08、09三年的檢測冠軍。DPM最早由芝加哥大學的P. Felzenszwalb等人提出[8]，後由其博士生R.Girshick改進[9]-[12]。2010年，P.Felzenszwalb和R. Girshick被VOC授予「終身成就獎」。DPM的主要思想可簡單理解為將傳統目標檢測演算法中對目標整體的檢測問題拆分並轉化為對模型各個部件的檢測問題，然後將各個部件的檢測結果進行聚合得到最終的檢測結果，即「從整體到部分，再從部分到整體」的一個過程。例如，對汽車目標的檢測問題可以在DPM的思想下分解為分別對車窗、車輪、車身等部件的檢測問題，對行人的檢測問題也可以類似地被分解為對人頭、四肢、軀幹等部件的檢測問題。

在模型結構方面，DPM可視為HOG檢測器在其結構上進行了拓展。整個DPM檢測器由基濾波器（Root-filter）和一系列部件濾波器（Part-filter）構成。這一部分工作由Felzenszwalb等人在07年提出[8]，並稱其為星型模型（Star-model）。後來Girshick又在星型模型的基礎上進一步將其拓展為混合模型（Mixture Model）[9]-[12]，用於解決真實世界中三維物體不同視角下的檢測問題。

在模型優化方面，由於DPM模型在訓練過程中並未要求詳細標註出各個部件的位置，所以採用了一種弱監督學習的策略。由於部件濾波器可以視為模型中的隱含變數，故Girshick進一步將其轉化為隱含變數結構SVM的優化問題，並結合難樣本挖掘和隨機梯度優化策略對該問題進行求解。

在模型加速方面，Girshick還曾將DPM中的線性SVM分類器「編譯」為一系列的級聯決策樁（Decision Stump）分類器，在不犧牲精度的前提下，將DPM加速了10倍。值得一提的是，這種加速策略本質上是借鑒了VJ檢測器快速檢測人臉的技術思路。

在演算法的後處理方面，DPM演算法採用包圍框回歸和上下文信息集成這兩個方法[10]-[12]進一步提升檢測準確率。其中，包圍框回歸的主要作用是將檢測得到的基濾波器以及部件濾波器所對應的包圍框進行整合併利用線性最小二乘回歸來得到最終精確的包圍框坐標。上下文信息集成的作用在於利用全局信息對檢測結果進行重新調整。從本質上來講，上下文信息反映了各個類別的目標在圖像中的聯合先驗概率密度分布，即哪些類別的目標可能同時出現，哪些類別的目標則不太可能同時出現。

雖然近幾年基於深度學習的檢測模型從精度上已遠遠超越了DPM，但DPM中的很多思想直到今天依然重要，例如混合模型、難樣本挖掘、包圍框回歸、上下文信息的利用等。時至今日，這些方法還都深深影響著目標檢測領域的發展。

—

基於深度學習的目標檢測演算法（上）

——基於Object Proposals的檢測演算法

Girshick曾提到[14]：「在過去的幾年中（2011-2013），目標檢測演算法的發展幾乎是停滯的，人們大多在低層特徵表達基礎上構建複雜的模型以及更加複雜的多模型集成來緩慢地提升檢測精度」。既然深度卷積網路能夠學習到非常魯棒且具有表達能力的特徵表示，那麼為何不將其引入目標檢測流程中用來提取特徵呢？當卷積神經網路在2012年ImageNet分類任務[19]中取得了巨大成功後，Girshick等人抓住了機會打破僵局，於2014年率先提出了區域卷積網路目標檢測框架（Regionswith CNN features，R-CNN）[14]。自此目標檢測領域開始以前所未有的速度發展。

隨著卷積神經網路層數的不斷加深，網路的抽象能力、抗平移能力和抗尺度變化能力越來越強。對於圖像分類任務來說這誠然是一件好事，然而對於檢測任務來說卻帶來了另一個問題：目標包圍框精準的位置越來越難以獲得。由此便出現了一個矛盾：如果想讓檢測演算法獲得更強的平移不變性和尺度不變性，那就必須一定程度地犧牲特徵在目標包圍框位置和尺度變化上的敏感性，即協變性；相反，如果想要獲得更精確的目標包圍框定位結果，就必須在平移不變性和尺度不變性上做一些妥協。所以，如果想要將卷積網路有效應用於目標檢測問題中，關鍵是如何有效解決深度網路的平移/尺度不變性和目標檢測問題中平移/尺度協變性要求的矛盾[20]。這迫使人們不得不放棄基於特徵圖+滑動窗口這一套檢測方案，從而將關注點轉向尋找更加定位精準的目標候選框檢測（Object Proposal Detection）演算法上來。

在過去的幾年裡，伴隨著深度學習目標檢測演算法的發展，有非常多的Object ProposalDetection演算法被提出，例如Selective Search[22]、Edge Boxes[23]、BING[24]等等。需要注意的是，基於Object Proposal並非是深度學習檢測演算法的專屬，早在傳統的手工特徵時期，Uijlings等人[22]就嘗試過使用Selective Search +詞袋（Bag of Words）特徵進行目標檢測。

下面將分別介紹幾種基於Object Proposal的深度學習目標檢測演算法。

【代表演算法1】Regions with CNN Features (R-CNN)[14]

【代表演算法2】Spatial Pyramid Pooling Networks (SPPNet)[15]

【代表演算法3】Fast-RCNN[16]

【代表演算法4】Faster-RCNN[17]

【代表演算法5】Feature Pyramid Networks

R-CNN：

R-CNN[14]使用了一種非常簡單的檢測策略，首先在圖像中提取Object Proposals，接下來把每個Proposal縮放到相同的大小後使用在ImageNet上訓練好的Alexnet網路[19]提取特徵，最後再使用SVM分類器進行虛警排除和類別判斷。R-CNN在VOC07數據集上取得了驚艷的效果，mAP由33.7%（DPM-v5[25]）提升至58.5%。雖然R-CNN取得了很大的進步，但其缺陷也很明顯：首先，其訓練是多階段的，較為繁瑣和耗時；其次，由於在高密度的候選區域上反覆進行特徵提取，其檢測速度很慢（GPU下每張圖40秒，640×480像素）。後來Kaiming He等人提出了SPPNet[15]，很好地解決這個問題。

SPPNet：

Kaiming He等人在2014年提出了SPPNet[15]，用來解決CNN網路提取特徵時要求輸入圖像尺寸固定的問題。與傳統的CNN網路模型相比，其創新點是，在卷積層和全連接層之間添加了一個空間金字塔池化（Spatial Pyramid Pooling, SPP）層。SPPNet可做到不經過候選區域的縮放操作就能實現任意大小、任意長寬比區域的特徵提取。在不損失精度的前提下，SPPNet是R-CNN的檢測速度的38倍。SPPNet有效解決了候選區域計算冗餘的問題，但是依然存在一些缺陷：首先，其訓練是仍然是多階段的；其次，SPPNet在微調網路時，只對其全連接層進行了微調，影響了特徵的準確性。後續提出的Fast R-CNN檢測器進一步地解決了這些問題。

Fast-RCNN：

2015年，Girshick等人在R-CNN和SPPNet的基礎上又提出了FastR-CNN檢測器[16]。Fast-RCNN最大的特點在於實現了一種多任務學習方式，實現了在網路微調的同時，對目標分類和包圍框回歸的同步訓練，且訓練速度是R-CNN的9倍，檢測速度是R-CNN的200倍。在VOC2007數據集上，Fast-RCNN將mAP由RCNN的58.5%提升至70.0%。Fast-RCNN成功地結合了R-CNN和SPPNet兩者的優點，但還是需要事先使用外部演算法來提取目標後選框，不能夠實現端到端的處理。那能不能將候選區域檢測這一操作同樣也交給網路去做呢？後來的Faster R-CNN解決了這個問題。

Faster-RCNN：

同樣是在2015年，在Fast-RCNN被提出後不久，Shaoqing Ren、Kaiming He以及Girshick等人又很快提出了Faster-RCNN演算法[17]。Faster-RCNN是第一個真正意義上的端到端的深度學習檢測演算法，也是第一個準實時（17幀/秒，640×480像素）的深度學習目標檢測演算法。Faster-RCNN在VOC07上在此將mAP由70.0%提升至78.8%。Faster-RCNN最大的創新點在於設計了候選區域生成網路（RegionProposal Network，RPN），並在其中設計了「多參考窗口」的機制，將Selective Search或Edge Boxes等外部Objectproposal檢測演算法融合到同一個深度網路中實現。從R-CNN到Fast RCNN再到Faster-RCNN，候選區域生成，特徵提取，候選目標確認和包圍框坐標回歸逐漸被統一到同一個網路框架之中。檢測精度由R-CNN的58.8%提升至Faster-RCNN的78.8%，檢測速度也由每幀幾十秒[14]提升至准實時檢測[17]速度。

Feature Pyramid Networks：

在2017年，Tsung-Yi Lin、Piotr Dollar、Ross Girshick和Kaiming He等人又在Faster RCNN的基礎上提出了Feature Pyramid Networks（FPN）檢測演算法。原有的目標檢測演算法通常都是只採用頂層特徵做檢測，原因是網路頂層特徵的語義信息比較豐富。然而，雖頂層特徵的語義信息豐富，但其中的目標位置信息卻比較粗略，不利於目標包圍框的準確定位；相反，雖然底層特徵的語義信息比較少，但其中目標的位置信息卻非常準確。因此，FPN的主要思想就是在網路前饋結束後，又將網路中最頂層的特徵圖像逐層地反饋並與前層的特徵圖進行融合，在此基礎上，再從網路中不同深度的位置引出多個檢測埠對其中的不同尺度的目標進行檢測。由於網路在前饋過程中天然形成了金字塔形狀的特徵圖，所以FPN對小目標以及尺度分布較大的目標具有天然的檢測優勢。FPN選擇在比VOC規模和難度更大的MSCOCO數據集上進行了測試，取得了當時最佳的檢測效果。

—

基於深度學習的目標檢測演算法（下）

——基於一體化卷積網路的檢測演算法

最近兩年基於深度學習的目標檢測演算法的發展有兩條主線，第一條是基於Object Proposal的檢測主線，這條主線基本是按照R-CNN >> SPPNet>>Fast-RCNN>>Faster-RCNN>>FPN發展的；另一條是最近一年提出的一體化卷積網路的檢測主線，這條主線基本是按照YOLO >> SSD >> Retina-Net發展的。在第二條主線中，人們拋棄了傳統的粗檢測+精檢測的檢測流程，經過單次檢測即可直接得到最終的檢測結果，因此有著更快的檢測速度。

一體化卷積網路檢測演算法最早可以追溯到上世紀九十年代[30]-[31]，當時Yann Lecun等人將其命名為「空間位移神經網路（Space Displacement Neural Network）」。最近兩年，一體化卷積網路檢測演算法受到了更多人的關注，在未來也會有更大的發展空間。下面將分別對這條主線下的YOLO、SSD、Retina-Net三種典型演算法進行介紹。

【代表演算法1】You Only Look Once (YOLO)[18]

【代表演算法2】Single Shot MultiBox Detector (SSD)[28]

【代表演算法3】Retina-Net[29]

YOLO：

YOLO[18]是第一個一體化卷積網路檢測演算法，由Joseph和Girshick等人在2015年提出。該演算法最大的優勢是速度快，徹底解決了基於深度學習速度上的痛點。該演算法的增強版本在GPU上速度為45幀/秒，快速版本速度為155幀/秒（640×480像素）。YOLO是「You Only LookOnce」的縮寫，從演算法的名字就能夠看出來作者徹底放棄了Proposal這一概念，直接將整張圖像作為網路的輸入，並僅通過一次前向傳播直接得到目標包圍框的位置和目標的類別。YOLO雖然有著非常快的檢測速度，但其精度與Faster-RCNN相比有所下降，尤其是小目標檢測效果較差，其定位的準確度也稍有不足。這主要是由於YOLO沒有採用類似FasterRCNN中的「多參考窗口」的機制處理多尺度窗口問題。後來提出的SSD演算法改善了這些問題。

SSD：

SSD[28]演算法由Wei Liu等人於2015年提出。SSD演算法吸收了YOLO速度快和RPN定位精準的優點，採用了RPN中的多參考窗口技術，並進一步提出在多個解析度的特徵圖上進行檢測。SSD在VOC07上取得了接近Faster-RCNN的準確率（mAP=72%），同時保持了極快的檢測速度（58幀/秒，640×480像素）。SSD與Faster-RCNN中不同之處有兩點：首先，SSD是在多個尺度下的特徵圖上設置多個參考窗口進行後選框的檢測，而Faster-RCNN僅僅是在一個尺度上進行處理；其次，Faster-RCNN是先利用提取目標後選框，然後再在後選框基礎上利用檢測網路和ROI Pooling進行後續判斷，SSD則直接分別在多個尺度的特徵圖上進行多尺度檢測和包圍框坐標回歸。此外，SSD在訓練過程中，還採用了難樣本挖掘操作來對圖像中難樣本進行聚焦。

Retina-Net：

一直以來，雖然基於一體化卷積網路的檢測模型的檢測速度都明顯快於基於Object Proposals的檢測演算法，其檢測精度卻一直略遜於後者。Tsung-Yi Lin、Priya Goyal、Ross Girshick以及Kaiming He等人對其背後的原因進行了研究，並與2017年提出了Retina-Net[29]檢測模型。Tsung-Yi Lin等人認為圖像中極為不均衡的目標-背景數據分布才是導致一體化卷積網路檢測精度較低的主要原因。Retina-Net對傳統的交叉熵損失函數進行修正，提出了「聚焦損失函數（Focal Loss）」。通過降低網路訓練過程中簡單背景樣本的學習權重，Retina-Net可以做到對難樣本的「聚焦」和對網路學習能力的重新分配，從而使一體化卷積網路檢測模型的檢測速度和精度全面超越基於Object Proposals的檢測模型。事實上，SSD中的難樣本挖掘操作也與Focal Loss有著類似思想和效果。

—

目標檢測中的關鍵技術

近年來，尤其是深度學習出現之後，自然圖像目標檢測領域取得了一系列突破性的進展。早期的目標檢測演算法[3],[1]-[2],[8]-[12]通常將檢測視為一個在圖像多個尺度上「滑動窗口遍歷+目標背景二分類」的問題。因此，人們常常重點解決特徵的表達能力、特徵提取的時間效率、多尺度問題的加速方法等問題。最近幾年提出的基於深度學習的檢測演算法[12]-[15],[25]則通常是在以下幾個問題上尋求技術突破：

【關鍵技術1】多尺度檢測方法

【關鍵技術2】包圍框坐標回歸

【關鍵技術3】加速策略

多尺度檢測方法：

目標檢測中的「多尺度」問題包含了「不同大小」和「不同長寬比」兩方面的內容。早期的目標檢測演算法，如VJ檢測器檢測人臉、HOG檢測器檢測行人都是針對特定長寬比目標所設計的檢測演算法，所以並沒有考慮「不同長寬比」這一層面的問題；而中後期的目標檢測演算法開始更多關注於一般性目標的通用檢測演算法，即開始關注檢測「不同長寬比」的目標。下圖顯示了自然圖像目標檢測的多尺度檢測方式發展流程。

目標檢測的多尺度檢測方式發展流程

從近20年的目標檢測工作來看，處理多尺度的問題採用的方法經歷了從最早的「多尺度積分圖特徵」，到之後的「特徵/濾波器金字塔遍歷」，再到後來的「Object Proposals」，最後到如今的依靠「深度網路暴力回歸」四個階段的發展歷程。

早期檢測演算法如VJ檢測器在處理多尺度問題時，並沒有採用「建塔」這一最直觀的思路。這是因為這種做法在計算能力有限的時代無法承受如此大的計算量。所以，VJ檢測器不得不採取積分圖這一種巧妙的方法來解決該問題。在VJ檢測器出現之後的幾年裡，隨著硬體計算能力不斷提升，更多的人嘗試使用更加複雜且表達能力更強的特徵進行目標檢測。但遺憾的是，高度非線性的特徵表示如HOG、LBP等並不具有積分圖特徵類似的性質，所以人們開始把思路轉向了「構建金字塔+滑窗遍歷」這一最直觀的處理方式。從HOG檢測器到DPM，甚至後來的深度學習檢測演算法Overfeat[32]都是通過這種方式構建的。

需要強調的是，通過建塔的方式只能處理特定長寬比目標的檢測問題，例如人臉檢測、行人檢測等。對於如VOC、MSCOCO等一般性目標檢測問題，如果構建不同長寬比、不同尺度的特徵金字塔，其計算量直到今天也是難以接受的。不過，DPM雖然沒有構建不同長寬比的金字塔，但卻可以處理一般性目標檢測問題。這是因為DPM採用了Mixture Model這種特殊的處理策略。

隨著人們需要檢測的目標類別越來越多，目標形態越來越多樣化，人們開始思考，是否能夠利用一種統一的「粗檢測」模型來處理不同長寬比和不同類別的目標？Object Proposals提供了一種很好的解決思路。Object Proposal的檢測指的是利用較低的計算量實現對圖像中所包含的一般性目標的包圍框進行準確定位（不局限與具體的目標類別，也不局限於固定的長寬比）。Object Proposals在近兩年基於深度學習的目標檢測演算法中起到了非常重要的作用。從R-CNN到Fast-RCNN再到Faster-RCNN，Object Proposals從最開始獨立的演算法模塊逐漸演變到最後與網路融為一體。

隨著GPU計算性能的提升，人們處理多尺度問題的方法變得越來越直接越來越暴力，而這種暴力在基於一體化卷積網路的檢測方法（如YOLO）中達到了頂峰。採用深度網路暴力回歸解決多尺度問題的思想非常簡單，即直接利用深度網路在目標對應位置提取的特徵對其包圍框的長寬進行回歸。這種做法的優點是設計簡單，計算量小，先提條件是圖像感受野足夠大且深度特徵表達能力足夠強，缺點是對小目標的包圍框定位不夠準確。

包圍框坐標的回歸：

特徵的平移、尺度不變性以及定位的準確性一直以來都存在著矛盾。早期的檢測演算法大多採用低層手工特徵，更多關注於圖像的邊緣、輪廓等信息。這類特徵的平移、尺度不變性較差，但對目標進行精確定位時有著天然的敏感性，可對目標邊界進行準確的定位。而基於深度學習的檢測演算法中採用的深度特徵由於其具有更強的平移不變性和尺度不變性，隨之帶來的問題是對目標包圍框定位的先天能力不足。下圖顯示了目標檢測中包圍框回歸技術的發展過程。

對於早期基於手工特徵的檢測演算法以及後來基於Object Proposals的檢測演算法（如DPM、R-CNN、Fast-RCNN）而言，包圍框坐標回歸僅僅是作為一種刷榜時提分的手段，這種操作對於檢測問題僅僅起到了錦上添花的作用，可有亦可無。然而從Faster-CNN開始，情況發生了轉變，這是由於包圍框回歸不再是一個單獨的後處理模塊，而是集成在了網路中，並採用多任務損失函數同分類任務一同進行訓練。現如今包圍框回歸已經是演算法流程中不可替代的一個標準環節。最近的一些演算法在包圍框回歸精度的提升方面取得了一些成果，比如多次包圍框坐標修正[40]、以及概率推斷在包圍框坐標預測中的應用[41]等。

目標檢測的包圍框回歸技術發展流程

加速策略：

目標檢測演算法的加速一直以來都是該領域一個非常重要的問題。一般來講，人們對演算法的加速通常體現在兩個層面，第一個層面是從演算法原理角度出發，設計低計算複雜度的演算法，並儘可能減少重複計算的開銷；第二個層面是從硬體實現層面出發，採用更高並行粒度的演算法，並通過多核並行計算提升計算速度，如利用GPU加速。早期的檢測演算法在目標檢測的計算原理方面做了很多加速工作，而後期的深度學習的檢測演算法的計算量雖然比早期演算法要大，但依靠硬體計算能力的提升已經可以輕鬆實現實時檢測的速度。下圖顯示了自然圖像目標檢測演算法的常見加速策略。

目標檢測演算法的加速策略一覽

通常在目標檢測演算法當中，特徵提取部分的計算開銷較其他環節的比重最大，所以近年來人們在特徵提取層面的加速工作最多，加速效果也最為顯著。傳統的基於滑動窗口的檢測器會在每個尺度的圖像上以一定步長移動，並在每個窗口上做特徵提取操作。由於相鄰滑窗之間通常有很大面積的交疊，因此交疊部分的特徵就會存在大量的計算重複。為了解決這個問題，通常在滑窗之前，都會在圖像上只整體計算一次特徵圖（Feature Map），以避免後面滑窗時對特徵進行重複提取。事實上，傳統目標檢測演算法中的「圖像金字塔」也可以理解為「特徵金字塔」，HOG檢測器和DPM都是在特徵金字塔上進行檢測的。值得一提的是，最近幾年基於深度學習的目標檢測演算法，除了R-CNN之外，其餘的也都利用了該加速思想。

除了特徵圖之外，積分圖也是早期目標檢測演算法中常見的加速策略。利用積分圖特徵進行加速的思想前面在介紹VJ檢測器已經介紹過，這裡再進行一些更加深入的探討。利用積分圖進行演算法加速的本質是利用了卷積操作的積分微分的可分離性[1]-[2]：

如果個g(x)"是稀疏的，那麼利用該性質就可以加速計算。事實上，早在VJ檢測器之前（1998年），LeCun等人就深入探討過利用該性質對CNN進行過加速[39]，並取得了10倍以上的加速效果。積分圖後來也有被用於加速行人檢測演算法的HOG特徵提取過程，在不損失精度的前提下取得了幾十倍的加速效果[7][33]。

未完待續……

參考文獻

[1] Viola P, Jones M. Rapid Object Detection Using a Boosted Cascade of SimpleFeatures [C]. IEEE Conference on Computer Vision and Pattern Recognitino, 2001,1:511.

[2] Viola P, Jones M J. Robust Real-Time Face Detection [J]. IEEEInternational Conference on Computer Vision 2004:747-747.

[3] Dalal N, Triggs B. Histograms of Oriented Gradients for Human Detection [C].IEEE Computer Society Conference on Computer Vision & Pattern Recognition.IEEE Computer Society, 2005:886-893.

[4] Turk M, Pentland A. Eigenfaces for recognition [J]. Journal of CognitiveNeuroscience, 1991, 3(1):71-86.

[5] Shotton J, Blake A, Cipolla R. Multiscale Categorical Object RecognitionUsing Contour Fragments [J]. IEEE Transactions on Pattern Analysis and MachineIntelligence, 2008, 30(7):1270-81.

[6] Opelt A, Pinz A, Zisserman A. A Boundary-Fragment-Model for ObjectDetection [C]. European Conference on Computer Vision 2006. Springer BerlinHeidelberg, 2006:575-588.

[7] Zhu Q, Yeh M C, Cheng K T, et al. Fast Human Detection Using a Cascadeof Histograms of Oriented Gradients [C]. IEEE Computer Society Conference onComputer Vision & Pattern Recognition. IEEE, 2006:1491-1498.

[8] Felzenszwalb P, Mcallester D, Ramanan D. A Discriminatively Trained, Multiscale,Deformable Part Model [C]. IEEE Computer Society Conference on Computer Vision &Pattern Recognition. 2008, 8::1-8.

[9] Felzenszwalb P F, Girshick R B, Mcallester D. Cascade Object Detection withDeformable Part Models [C]. IEEE Conference on Computer Vision & PatternRecognition. IEEE Computer Society, 2010:2241-2248.

[10] Forsyth D. Object Detection with Discriminatively Trained Part-BasedModels [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2010, 32(9):1627-45.

[11] Girshick R B, Felzenszwalb P F, Mcallester D. Object Detection withGrammar Models[J]. Nips, 2010, 33:442-450.

[12] Girshick R B. From Rigid Templates to Grammars: Object Detection with StructuredModels [J].A Dissertation Submitted to the Faculty of the Division of the PhysicalSciences, 2012.

[13] Girshick R, Iandola F, Darrell T, et al. Deformable Part Models Are ConvolutionalNeural Networks [J]. IEEE Conference on Computer Vision & PatternRecognition, 2015:437-446.

[14] Girshick R, Donahue J, Darrell T, et al. Rich Feature Hierarchies forAccurate Object Detection and Semantic Segmentation [C]. Computer Vision andPattern Recognition. IEEE, 2013:580-587.

[15] He K, Zhang X, Ren S, et al. Spatial Pyramid Pooling in DeepConvolutional Networks for Visual Recognition [J]. IEEE Transactions on PatternAnalysis and Machine Intelligence, 2015, 37(9):1904-16.

[16] Girshick R. Fast R-CNN [OL]. arXiv:1504.08083, 2015.

[17] Ren S, He K, Girshick R, et al. Faster R-CNN: Towards Real-Time ObjectDetection with Region Proposal Networks [OL]. arXiv:1506.01497, 2015.

[18] Redmon J, Divvala S, Girshick R, et al. You Only Look Once: Unified,Real-Time Object Detection [OL]. arXiv: 1506.02640, 2016.

[19] Krizhevsky A, Sutskever I, Hinton G E. ImageNet Classification with DeepConvolutional Neural Networks [J]. Advances in Neural Information ProcessingSystems, 25(2):2012.

[20] Dai J, Li Y, He K, et al. R-FCN: Object Detection via Region-based FullyConvolutional Networks [OL]. arXiv: 1605.06409, 2016.

[21] Hosang J, Benenson R, Dollar P, et al. What Makes for EffectiveDetection Proposals? [J]. IEEE Transactions on Pattern Analysis and MachineIntelligence, 2016, 38(4):814-830.

[22] Van d S K E A, Uijlings J R R, Gevers T, et al. Segmentation as SelectiveSearch for Object Recognition [C]. Proceedings IEEE International Conference onComputer Vision. 2011:1879-1886.

[23] Zitnick C L, Dollár P. Edge Boxes: Locating Object Proposals from Edges[C]. European Conference on Computer Vision, 2014:391-405.

[24] Cheng M M, Zhang Z, Lin W Y, et al. BING: Binarized Normed Gradients forObjectness Estimation at 300fps [J]. IEEE International Conference on ComputerVision 2014:3286-3293.

[25] Girshick R., Felzenszwalb P., and McAllester D. Discriminatively TrainedDeformable Part Models, release 5 [OL].http://www.cs.berkeley.edu/?rbg/latent-v5/.

[26] Zeiler M D, Fergus R. Visualizing and Understanding ConvolutionalNetworks [J]. 2014, 8689:818-833.

[27] Simonyan K, Zisserman A. Very Deep Convolutional Networks forLarge-Scale Image Recognition [J]. Computer Science, 2014.

[28] Liu W, Anguelov D, Erhan D, et al. SSD: Single Shot MultiBox Detector [OL].arXiv: 1512.02325, 2016.

[29] Lin T Y, Goyal P, Girshick R, et al. Focal Loss for Dense ObjectDetection [OL]. arXiv: 1708.02002, 2017.

[30] Vaillant R, Monrocq C, Cun Y L. An Original Approach for the Localizationof Objects in Images [C]. International Conference on Artificial NeuralNetworks. 1993:26-30.

[31] Lecun Y, Bottou L, Bengio Y, et al. Gradient-based Learning Applied to DocumentRecognition [J]. Proceedings of the IEEE, 1998, 86(11):2278-2324.

[32] Sermanet P, Eigen D, Zhang X, et al. OverFeat: Integrated Recognition,Localization and Detection using Convolutional Networks [C]. InternationalConference on Learning Representations, 2013.

[33] Benenson R, Mathias M, Timofte R, et al. Pedestrian Detection at 100 Framesper Second [C]. IEEE International Conference on Computer Vision2012:2903-2910.

[34] Alexe B, Deselaers T, Ferrari V. What is an Object? [C]. IEEEInternational Conference on Computer Vision and Pattern Recognition,2010:73-80.

[35] Ponttuset J, Arbelaez P, Barron J, et al. Multiscale CombinatorialGrouping for Image Segmentation and Object Proposal Generation [J]. IEEETransactions on Pattern Analysis and Machine Intelligence, 2015:1-1.

[36] Kong T, Yao A, Chen Y, et al. HyperNet: Towards Accurate Region ProposalGeneration and Joint Object Detection [C]. IEEE International Conference on ComputerVision and Pattern Recognition. 2016:845-853.

[37] Ghodrati A, Diba A, Pedersoli M, et al. DeepProposal: Hunting Objects byCascading Deep Convolutional Layers [C]. IEEE International Conference on ComputerVision and Pattern Recognition. 2015:2578-2586.

[38] Dollar P, Appel R, Belongie S, et al. Fast Feature Pyramids for ObjectDetection [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2014, 36(8):1532-45.

[39] Simard P Y, Bottou L, Haffner P, et al. Boxlets: A Fast Convolution Algorithmfor Signal Processing and Neural Networks [C]. Conference on Advances in NeuralInformation Processing Systems II. MIT Press, 1999:571-577.

[40] Yoo D, Park S, Lee J Y, et al. AttentionNet: Aggregating Weak Directionsfor Accurate Object Detection [J]. IEEE International Conference on ComputerVision. 2015:2659-2667.

[41] Gidaris S, Komodakis N. LocNet: Improving Localization Accuracy forObject Detection [C]. IEEE Conference on Computer Vision and PatternRecognition. 2016:789-798.