基于GPU的卷積檢測模型加速

劉　琦　黃　咨　陳璐艷　胡福喬

(上海交通大學自動化系系統控制與信息處理教育部重點實驗室　上海 200240)

?

基于GPU的卷積檢測模型加速

劉琦黃咨陳璐艷胡福喬

(上海交通大學自動化系系統控制與信息處理教育部重點實驗室上海 200240)

摘要近年來，形變部件模型和卷積神經網絡等卷積檢測模型在計算機視覺領域取得了極大的成功。這類模型能夠進行大規模的機器學習訓練，實現較高的魯棒性和識別性能。然而訓練和評估過程中卷積運算巨大的計算開銷，也限制了其在諸多實際場景中進一步的應用。利用數學理論和并行技術對卷積檢測模型進行算法和硬件的雙重加速。在算法層面，通過將空間域中的卷積運算轉換為頻率域中的點乘運算來降低計算復雜度；而在硬件層面，利用GPU并行技術可以進一步減少計算時間。在PASCAL VOC數據集上的實驗結果表明，相對于多核CPU，該算法能夠實現在單個商用GPU上加速卷積過程2.13～4.31倍。

關鍵詞卷積檢測模型計算機視覺GPU

0引言

目標檢測是計算機視覺領域中一項計算密集的工作。現實生活中的絕大多數應用，如智能監控中的行人檢測、汽車安全中的車輛檢測和圖像檢索中的特定類別目標檢測等，都要求檢測速度足夠快以便達到實時性，同時也希望盡可能降低誤報率。近年來，研究人員提出了一批優秀的卷積檢測模型CDM(Convolution-based detection model)，并在諸如PASCAL VOC[1]、ImageNet[2]等極具挑戰性的標準評測數據集上取得了出色計算性能。這些模型以卷積運算為基礎，用特定的模板與輸入圖像或特征圖進行卷積得到響應圖，進而通過最大響應值確定目標位置或將其作為特征圖再次進行卷積運算，如圖1所示。然而，盡管卷積檢測模型簡單有效，但卷積運算高強度的計算消耗阻礙了其在現實生活中的應用。

圖1　卷積檢測模型中的卷積運算流程

針對卷積運算耗時這一問題，一種有效的方法是利用卷積定理將空間域中的卷積運算通過傅里葉變換到頻率域中更為高效的點乘運算，進而顯著地降低計算復雜度[3]。盡管如此，在面對實際尺寸目標檢測任務時，即使采用多線程并行技術，這種方法在CPU平臺上的運行效率依然低下。而隨著高性能計算技術的快速發展，GPU的通用科學計算能力得到了越來越多的重視。快速傅里葉變換和點乘運算中蘊含了豐富數據獨立性，使得GPU上的計算并行化成為可能，可以進一步提高計算效率，節省處理時間。

本文從算法加速和硬件加速兩個角度入手，首先將卷積定理推廣至卷積檢測模型，通過對比應用卷積定理前后的模型計算復雜度，從數學上論證了算法有效性。接下來，本文分析了算法的并行性，在此基礎上提出了基于OpenCL的GPU加速策略并進行實現。實驗結果表明，本文算法能夠有效利用GPU的計算能力，相對于多線程CPU實現，取得了2.13～4.31倍的加速比。

1相關工作

一直以來，卷積操作在統計、信號處理、計算機視覺等領域都是最基礎的數學算子之一，在空間域上通常以滑動窗口的形式實現。在許多早期的研究工作中，卷積算子常被用來調整信號的頻率特性，如高斯平滑、平均平滑和Sobel濾波等。此后，模板匹配利用卷積算子在空間域上搜索特定的模式，這被認為是一種簡單的檢測模型。然而，這類模型難以在包含諸多類別的靜態圖片中準確地定位特定目標。為解決目標檢測中存在的姿態和形態各異的問題，絕大多數常用的檢測模型都采用了大量的模板和卷積運算，如形變部件模型DPM(Deformable partbased models)和卷積神經網絡CNN(Convolutional neural networks)。盡管這類模型的檢測效果顯著提升，但其計算量也隨卷積算子的增加而線性增長。

1.1形變部件模型

Felzenszwalb等人[4]提出的形變部件模型采用HOG (Histograms of oriented gradient)描述子[5]作為底層特征，使用樹狀圖模型[6]來表示目標結構，并據此將根模板和若干可形變部件模板組合到一起，形變部件用于反映目標局部形態特性。該模型通過滑動窗口的方式，在HOG特征金字塔上逐層卷積估計目標可能出現的位置。這種計算方式需要處理全部的搜索空間，從而運行效率非常低下。

為了解決此問題，Felzenszwalb等人[7]進一步提出了采用部分假設剪枝策略的級聯實現。但由于級聯中存在過多控制流和負載不均衡等問題，難以適用于GPU架構。Song等人[8]和Hirabayashi等人[9]進行了形變部件模型的CUDA實現，但同時也將其應用局限于Nvidia GPU平臺。De Smedt等人[10,11]對構建HOG特征金字塔進行了OpenCL實現，將卷積遺留在CPU端，以流水線在CPUs/GPUs異構體系下實現形變部件模型。相較于特征提取，形變部件模型中的卷積運算計算量更大，也更適于采用GPU并行計算架構。

1.2卷積神經網絡

卷積神經網絡[12,13]源于對動物視覺皮層的研究，是多層感知器MLP(Multilayer perceptions)的變形。不同于形變部件模型采用固定的HOG特征，卷積神經網絡將模板直接運用于原始圖像上，通過大量卷積操作模擬視覺識別系統。卷積層和采樣層是卷積神經網絡的核心。卷積層主要用于產生不同層次的特征編碼，在前饋和反向傳播過程中都消耗了絕大部分的計算資源。采樣層通過降采樣操作，針對局部畸變和簡單幾何變換等問題實現了一定的不變形。

實際上，形變部件模型也是一種卷積神經網絡。Girshick等人[14]簡化了由Krizhevsky[15]等人提出的參數規模非常龐大的卷積神經網絡，用于構建特征金字塔，以替代HOG特征。同時他們將距離變換推廣為采樣層，將形變部件模型的推斷過程重構為一個卷積神經網絡。

受限于網絡深度和計算速度，卷積神經網絡很難應用于實際尺寸的目標檢測任務中。當前主流的卷積神經網絡庫都是使用CUDA實現GPU加速，如Caffe[16]等。Cecotti等人[17]將傅里葉變換引入到卷積神經網絡，但其主要目的是為了便于腦電信號分析而非加速。

2頻率域算法加速

為加速線性目標檢測系統的評估速度，Dubout等人[3]引入傅里葉變換，實現了6～8倍的加速比。我們可以將此方法進行推廣，用于加速卷積檢測模型。

算法加速的核心思想是傅里葉變換的卷積定理，即原始信號在空間域的卷積可由其對應的傅里葉變換乘積的反變換求得，可表示為:

f*g=F-1(F(f)×F(g))

(1)

算法加速的基本流程主要包括以下3個步驟：

(1) 計算所有空間域特征圖和模板的傅里葉變換；

(2) 將頻率域特征圖和模板進行點乘和累加運算，得到頻率域響應圖；

(3) 計算傅里葉逆變換得到空間域響應圖。

為深入分析算法加速的有效性，假定卷積檢測模型的輸入為具有L維特征的J張尺寸為M×N的特征圖和K個尺寸為P×Q的模板。同時，將特征圖和模板的第l維分別標記為xl∈RM×N和yl∈RP×Q，則由特征圖和模板卷積而得的響應圖z∈R(M-P+1)×(N-Q+1)可表示為:

(2)

卷積運算的計算復雜度為O(MNPQ)。由于特征圖和模板的每個系數之間都需要進行一次乘法和一次加法運算，因此每一維所需的浮點數運算量為:

Cconv=2MNPQ

(3)

假定每張特征圖都需要與所有K個模板進行卷積，則每張特征圖所需的浮點數運算量共為:

Cspatial=KL(Cconv+MN)

(4)

其中，MN表示最終為得到1維響應圖而進行的累加運算數。為簡便起見，假定響應圖的大小仍然保持為M×N。

為了在頻率域中順利進行點乘運算，首先需要在傅里葉變換之前將模板填補成與對應特征圖同一大小。對于實數傅里葉變換，其變換結果滿足Hermitian冗余，即其中一半的變換結果與另一半共軛。因此傅里葉變換后的特征圖與模板大小均為M×(N+2) ，共包含M×(N/2+1)個復數系數。同樣，簡記其大小為M×N，共包含M×N/2個復數系數。

兩維傅里葉變換的計算復雜度為O(M2N2)，快速變換算法可將其降低至O(MNlog2MN)。根據文獻[18,19]，可得到每一維實數特征圖傅里葉變換所需的浮點數運算量為:

CFFT=2.5MNlog2MN

(5)

對于頻率域中的點乘和累加運算，特征圖和模板對應位置上的復數系數之間需要各進行一次復數乘法(6次浮點數運算)和復數加法(2次浮點數運算)，故總運算量為:

Cmul+acc=4MN

(6)

在實際系統中,通常只需要載入一次模板即可，因此模板的傅里葉變換可以離線進行。同時，根據傅里葉變換的線性特性，多維響應的累加運算可以在頻域進行，故只需要計算一維的逆變換。因此，引入傅里葉變換后，對于每張特征圖，共需要進行L次正變換、K次逆變換和KL次點乘和累加運算，所需的浮點數運算量共為:

Cfrequency=LCFFT+KLCmul+acc+KCFFT

(7)

對比空間域和頻率域的浮點數運算量，則理論上的加速比為:

(8)

根據式(8)，易知若模板數量越多，特征維度越高，即KL?K+L，則能夠獲得越高的加速比。同時，對于更大的模板也能夠獲得更高的加速比。這兩點都是當前主流卷積檢測模型的共同特性。

3GPU硬件加速

圖2　利用卷積定理進行算法加速的基本流程

為了進一步加速卷積檢測模型，本文在GPU上基于OpenCL對前述算法進行了并行實現，使硬件加速不再受限于GPU平臺類型。OpenCL是一個面向異構系統，用于通用并行計算的免費開放標準，也是一個統一的編程環境，可廣泛適用于各類不同架構的CPU、GPU、DSP及FPGA等并行處理器。

圖2所示的算法加速的串行實現偽代碼如算法1所示。

算法1頻率域算法加速的串行實現

輸入：特征圖F、模板T

輸出：響應圖R

FORTj∈TDO

fTj=forwardFFT(Tj)

//模板正變換

END

FORFi∈FDO

fFi=forwardFFT(Fi)

//特征圖正變換

FORfTj∈fTDO

fSij=fFi·fTj

//頻率域點乘

fRij+=fSij

//頻率域累加

Rij=backwardFFT(fRij)

//響應圖逆變換

END

END

在算法1中，存在十分明顯的并行性，主要有兩個方面：

(1) 數據并行性：無論是傅里葉變換、點乘，還是累加，這些基于像素的運算之間都不存在數據依賴性。因此，可以將輸入數據映射到OpenCL的NDRange索引空間，利用一個線程處理一個像素的運算過程。

(2) 任務并行性：算法1中同類型的任務之間不存在數據依賴性，如所有模板的傅里葉變換。而同一FOR循環內的不同類型任務則需要順序執行，如點乘、累加和響應圖傅里葉逆變換。

通過調整FOR循環的順序，可以使算法1更適宜GPU并行化，如算法2所示。將同一FOR循環中的任務依次發送至GPU，插入到不同的OpenCL命令隊列，可以使之并行執行。若存在數據依賴性，則將其插入同一命令隊列，并通過OpenCL事件進行通信，保證執行次序。不同FOR循環間通過同步命令保證內存的一致性。

算法2頻率域算法加速的并行實現

輸入：特征圖F、模板T

輸出：響應圖R

FORTj∈TDO

event=writetoGPU(Tj)

fTj=fFFTkernel(Tj,event)

//模板正變換

END

Synchronization()

FORFi∈FDO

event=writetoGPU(Fi)

fFi=forwardFFT(Fi,event)

//特征圖正變換

END

Synchronization()

FORfFi∈fF&fTj∈fTDO

fRij=mul&acckernel(fFi,fTj)

//點乘、累加

END

Synchronization()

FORfRij∈fRDO

Rij,event=backwardFFT(fRij)

//響應圖逆變換

readtoCPU(Rij,event)

END

Synchronization()

3.1快速傅里葉變換

N點一維離散傅里葉變換(DFT)可表示為:

(9)

(10)

圖3　以2、3、5為基的30點DFT快速計算流程

由于輸出并非順序，Cooley-Tukey算法中存在顯式位反轉操作，這并不適合在GPU上實現。Stockhan算法[21]通過在每次分解中穿插進行多維轉置，可以避免這一問題而直接得到順序輸出，適于GPU實現[22]。

在利用GPU并行計算2維FFT時，通常的方法是使用1維FFT分別變換其所有行和列。在分解完成后，FFT核函數將數據從顯存加載到寄存器中，利用GPU的局部內存存儲中間數據，每個線程遞歸地計算一個基的FFT。

3.2拼接策略和優化

前文曾提及需要在傅里葉變換之前將模板填補成與對應特征圖同一大小。而簡單的填補方法或將導致過高的內存開銷，或需要消耗較多的計算資源，特別是對于部分需要構建特征金字塔的卷積檢測模型。

對于上述問題，可以通過利用一種快速啟發式左下裝箱算法[23]拼接特征圖來解決。其基本思路是將所有特征圖組合成為若干特征拼圖，后將模板填補成同一大小[3]，如圖4所示。特征拼圖的大小通常等同于最大的特征圖。

圖4　特征拼圖示意圖及基本流程

為避免GPU產生不必要的調度開銷，不僅需要控制GPU上任務的數量，也需要合理設置每個OpenCL核函數運行時所啟動的線程數。因此，本文將特征圖和模板的點乘運算和累加運算合并到一個核函數中，使用3維NDRange索引空間，每一個工作組計算一個像素上L維特征的相關運算。這樣不僅可以避免過多的調度開銷，還能夠更為規律地進行內存合并訪問。同時有計劃地發送任務，適當的同步也可降低調度開銷。

4實驗結果與分析

本文選擇形變部件模型作為基礎，進行OpenCL實現，GPU上的FFT計算使用clMath數學庫中的clFFT函數庫。基準CPU多線程實現為Idiap研究所的FFLD[3]，其使用CPU SIMD指令集和OpenMP實現多線程并行計算，FFT計算使用FFTW函數庫，矩陣運算使用Eigen函數庫。

本文在兩個不同硬件平臺上進行了實驗，一個配置為Intel Core i7 3770(3.4 GHz,4核)和Intel HD Graphics 4000(0.35 GHz,128 個流處理器)；另一個配置為Intel Core i5 3570K (超頻4.2 GHz， 4核)和Nvidia GeForce GTX 670(超頻1.17GHz，1344個流處理器)。

測試數據來自PASCAL VOC 2007數據集，檢測模板來自基準CPU實現。以自行車為例，其檢測模板共54個，模型構建的32維HOG特征金字塔共17層，組成6個特征拼圖。根據算法2可將整個卷積過程(從輸入特征圖和模板到輸出響應圖)分為四部分：模板正變換、特征圖正變換、點乘和累加以及響應圖逆變換。表1給出了各部分總的計算時間，包括GPU計算時間、數據傳輸時間，以及各類在CPU上進行的預處理或后處理的計算時間，以便更客觀地對比本文算法的加速效果。

表1　CPU多線程實現與GPU實現的性能對比

在Intel GPU平臺上，點乘和累加運算上取得了4.26倍的加速比，而其他三部分則更慢一些，模板正變換、特征圖正變換和響應圖逆變換的計算時間分別為基準的0.58、0.83和0.23倍。同樣地，在Nvidia GPU平臺上，本文實現了25.16倍的點乘和累加運算加速，而其他三部分則分別為基準的0.91、0.94和0.25倍。

實驗結果表明，點乘和累加運算能夠充分利用GPU中的大量流處理器，從而實現較高的加速比。而有關FFT運算的其他三部分較基準更慢的一個主要原因是其中數據傳輸以及CPU上的各類預處理或后處理操作所需的計算時間較高。例如，響應圖逆變換速度遠慢于基準的原因便是分解響應拼圖操作中數據傳輸耗時較多。另一個主要原因在于所選用的FFT函數庫。由于目前便于使用的以OpenCL實現的FFT函數庫較少，本文選用的clFFT函數庫仍處于開發初期，其功能和效率還有待提升。事實上，基準CPU實現所使用的FFTW函數庫能夠利用批處理操作，同時精確計算32維HOG特征圖和模板的快速傅里葉變換。而clFFT函數庫在HD 4000上卻只能同時精確計算5維，在GTX670上也不過增加至11維。對此，在具體實現中不得不先將特征圖和模板進行拆分，計算FFT后再將其融合。

另外，GTX 670上的各部分計算時間均少于HD 4000，加速比分別為1.83、1.41、5.45和1.25倍。這主要得益于GTX 670擁有更高的工作頻率和更多的流處理器，能夠產生更多的并發線程。

由于模板的傅里葉變換可以離線進行，所以若從實際應用的角度出發，可將特征圖正變換、點乘和累加，以及響應圖逆變換這三部分計算時間的總和作為標準，來衡量卷積在線流程的性能。在HD 4000上，卷積在線流程的計算時間由2097 ms降至984 ms，提速2.13倍，其中點乘和累加運算的計算時間占比從80.88%降至40.45%，如圖5所示，其中餅圖的面積表示卷積在線流程所需要的計算時間。在GTX 670上，卷積在線流程的計算時間由2162 ms降至502 ms，提速4.31倍，而點乘和累加運算的占比更是明顯下降，由84.97%降至14.54%，如圖6所示。

圖5　HD 4000上卷積在線流程的性能對比

圖6　GTX 670上卷積在線流程的性能對比

綜上所述，盡管在OpenCL實現中所選用的第三方函數庫的效率并不理想，從而導致部分運算時間較CPU實現有所增加。但從整體上來看，對于卷積檢測模型本文的GPU實現在不同硬件平臺上仍然能夠取得不錯的加速效果。

5結語

本文提出了將傅里葉變換推廣至卷積檢測模型，通過將空間域中的卷積運算轉換到頻率域中的點乘運算以大幅降低計算復雜度，并從數學上論證了其有效性。同時，本文在GPU上使用OpenCL實現了進一步的硬件加速。實驗結果表明，盡管本文所選用的第三方函數庫效率并不理想，但本文的GPU實現仍然能夠在不同架構的硬件平臺上取得不錯的加速效果。相對于4核CPU平臺下的多線程實現，本文的GPU實現能夠達到2.13～4.31倍的加速比。

未來的工作將主要集中于研究目前耗時較多的預處理或后處理操作的加速、提高FFT運算效率等問題，同時將本文所提出的加速方法應用于卷積神經網絡。

參考文獻

[1] Everingham M,Van Gool L,Williams C K I,et al.The pascal visual object classes (voc) challenge[J].International journal of computer vision,2010,88(2):303-338.

[2] Deng J,Dong W,Socher R,et al.Imagenet:A large-scale hierarchical image database[C]//Computer Vision and Pattern Recognition,2009.CVPR 2009.IEEE Conference on.IEEE,2009:248-255.

[3] Dubout C,Fleuret F.Exact acceleration of linear object detectors[C]//Computer Vision-ECCV 2012.Springer Berlin Heidelberg,2012:301-311.

[4] Felzenszwalb P F,Girshick R B,McAllester D,et al.Object detection with discriminatively trained part-based models[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2010,32(9):1627-1645.

[5] Dalal N,Triggs B.Histograms of oriented gradients for human detection[C]//Computer Vision and Pattern Recognition,2005.CVPR 2005.IEEE Computer Society Conference on.IEEE,2005,1:886-893.

[6] Felzenszwalb P F,Huttenlocher D P.Pictorial structures for object recognition[J].International Journal of Computer Vision,2005,61(1):55-79.

[7] Felzenszwalb P F,Girshick R B,McAllester D.Cascade object detection with deformable part models[C]//Computer vision and pattern recognition (CVPR),2010 IEEE conference on.IEEE,2010:2241-2248.

[8] Song H O,Zickler S,Althoff T,et al.Sparselet models for efficient multiclass object detection[C]//Computer Vision-ECCV 2012.Springer Berlin Heidelberg,2012:802-815.

[9] Hirabayashi M,Kato S,Edahiro M,et al.GPU implementations of object detection using HOG features and deformable models[C]//Cyber-Physical Systems,Networks,and Applications (CPSNA),2013 IEEE 1st International Conference on.IEEE,2013:106-111.

[10] De Smedt F,Struyf L,Beckers S,et al.Is the game worth the candle? Evaluation of OpenCL for object detection algorithm optimization[C]// International Conference on PECCS,2012:284-291.

[11] De Smedt F,Van Beeck K,Tuytelaars T,et al.Pedestrian detection at warp speed:Exceeding 500 detections per second[C]//Computer Vision and Pattern Recognition Workshops (CVPRW),2013 IEEE Conference on.IEEE,2013:622-628.

[12] LeCun Y,Bottou L,Bengio Y,et al.Gradient-based learning applied to document recognition[J].Proceedings of the IEEE,1998,86(11):2278-2324.

[13] Ouyang W,Wang X.Joint deep learning for pedestrian detection[C]//Computer Vision (ICCV),2013 IEEE International Conference on.IEEE,2013:2056-2063.

[14] Girshick R,Iandola F,Darrell T,et al.Deformable Part Models are Convolutional Neural Networks[R/OL].Berkeley,CA,USA:UC Berkeley,2014 [2014-10-01].http://arxiv.org/abs/1409.5403.

[15] Krizhevsky A,Sutskever I,Hinton G E.Imagenet classification with deep convolutional neural networks[C]//Advances in neural information processing systems.2012:1097-1105.

[16] Jia Y,Shelhamer E,Donahue J,et al.Caffe:An open source convolutional architecture for fast feature embedding[CP/OL].2014.http://caffe.berkeleyvision.org.

[17] Cecotti H,Graeser A.Convolutional neural network with embedded fourier transform for EEG classification[C]//Pattern Recognition,2008.ICPR 2008.19th International Conference on.IEEE,2008:1-4.

[18] Frigo M,Johnson S G.The design and implementation of FFTW3[J].Proceedings of the IEEE,2005,93(2):216-231.

[19] Li Y,Zhang Y Q,Liu Y Q,et al.MPFFT:an auto-tuning FFT library for OpenCL GPUs[J].Journal of Computer Science and Technology,2013,28(1):90-105.

[20] Cooley J W,Tukey J W.An algorithm for the machine calculation of complex Fourier series[J].Mathematics of computation,1965,19(90):297-301.

[21] Stockham Jr T G.High-speed convolution and correlation[C]//Proceedings of the April 26-28,1966,Spring joint computer conference.ACM,1966:229-233.

[22] Dotsenko Y,Baghsorkhi S S,Lloyd B,et al.Auto-tuning of fast fourier transform on graphics processors[J].ACM SIGPLAN Notices.ACM,2011,46(8):257-266.

[23] Chazelle B.The bottomn-left bin-packing heuristic:An efficient implementation[J].Computers,IEEE Transactions on,1983,100(8):697-707.

CONVOLUTION-BASED DETECTION MODELS ACCELERATION BASED ON GPU

Liu QiHuang ZiChen LuyanHu Fuqiao

(KeyLaboratoryofSystemControlandInformationProcessing,MinistryofEducationofChina,DepartmentofAutomation,ShanghaiJiaoTongUniversity，Shanghai200240,China)

AbstractIn recent years,convolution-based detection models (CDM),such as the deformable part-based models (DPM) and the convolutional neural networks (CNN),have achieved tremendous success in computer vision field.These models allow for large-scale machine learning training to achieve higher robustness and recognition performance.However,the huge computational cost of convolution operation in training and evaluation processes also restricts their further application in many practical scenes.In this paper,we accelerate both the algorithm and hardware of convolution-based detection models with mathematical theory and parallelisation technique.In the aspect of algorithm,we reduce the computation complexity by converting the convolution operation in space domain to the point multiplication operation in frequency domain.While in the aspect of hardware,the use of graphical process unit (GPU) parallelisation technique can reduce the computational time further.Results of experiment on public dataset Pascal VOC demonstrate that compared with multi-core CPU,the proposed algorithm can realise speeding up the convolution process by 2.13 to 4.31 times on single commodity GPU.

KeywordsConvolution-based detection modelComputer visionGPU

收稿日期：2014-11-24。國家自然科學基金項目(61175009);上海市產學研合作項目(滬CXY-2013-82)。劉琦，碩士生，主研領域：計算機視覺，并行計算。黃咨，碩士生。陳璐艷，碩士生。胡福喬，副教授。

中圖分類號TP3191

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.057