劉　琦　黃　咨　陳璐艷　胡福喬

(上海交通大學(xué)自動化系系統(tǒng)控制與信息處理教育部重點(diǎn)實(shí)驗(yàn)室　上海 200240)

?

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

劉琦黃咨陳璐艷胡福喬

(上海交通大學(xué)自動化系系統(tǒng)控制與信息處理教育部重點(diǎn)實(shí)驗(yàn)室上海 200240)

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

關(guān)鍵詞卷積檢測模型計(jì)算機(jī)視覺GPU

0引言

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

圖1　卷積檢測模型中的卷積運(yùn)算流程

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

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

1相關(guān)工作

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

1.1形變部件模型

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

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

1.2卷積神經(jīng)網(wǎng)絡(luò)

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

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

受限于網(wǎng)絡(luò)深度和計(jì)算速度，卷積神經(jīng)網(wǎng)絡(luò)很難應(yīng)用于實(shí)際尺寸的目標(biāo)檢測任務(wù)中。當(dāng)前主流的卷積神經(jīng)網(wǎng)絡(luò)庫都是使用CUDA實(shí)現(xiàn)GPU加速，如Caffe[16]等。Cecotti等人[17]將傅里葉變換引入到卷積神經(jīng)網(wǎng)絡(luò)，但其主要目的是為了便于腦電信號分析而非加速。

2頻率域算法加速

為加速線性目標(biāo)檢測系統(tǒng)的評估速度，Dubout等人[3]引入傅里葉變換，實(shí)現(xiàn)了6～8倍的加速比。我們可以將此方法進(jìn)行推廣，用于加速卷積檢測模型。

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

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

(1)

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

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

(2) 將頻率域特征圖和模板進(jìn)行點(diǎn)乘和累加運(yùn)算，得到頻率域響應(yīng)圖；

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

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

(2)

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

Cconv=2MNPQ

(3)

假定每張?zhí)卣鲌D都需要與所有K個模板進(jìn)行卷積，則每張?zhí)卣鲌D所需的浮點(diǎn)數(shù)運(yùn)算量共為:

Cspatial=KL(Cconv+MN)

(4)

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

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

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

CFFT=2.5MNlog2MN

(5)

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

Cmul+acc=4MN

(6)

在實(shí)際系統(tǒng)中,通常只需要載入一次模板即可，因此模板的傅里葉變換可以離線進(jìn)行。同時，根據(jù)傅里葉變換的線性特性，多維響應(yīng)的累加運(yùn)算可以在頻域進(jìn)行，故只需要計(jì)算一維的逆變換。因此，引入傅里葉變換后，對于每張?zhí)卣鲌D，共需要進(jìn)行L次正變換、K次逆變換和KL次點(diǎn)乘和累加運(yùn)算，所需的浮點(diǎn)數(shù)運(yùn)算量共為:

Cfrequency=LCFFT+KLCmul+acc+KCFFT

(7)

對比空間域和頻率域的浮點(diǎn)數(shù)運(yùn)算量，則理論上的加速比為:

(8)

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

3GPU硬件加速

圖2　利用卷積定理進(jìn)行算法加速的基本流程

為了進(jìn)一步加速卷積檢測模型，本文在GPU上基于OpenCL對前述算法進(jìn)行了并行實(shí)現(xiàn)，使硬件加速不再受限于GPU平臺類型。OpenCL是一個面向異構(gòu)系統(tǒng)，用于通用并行計(jì)算的免費(fèi)開放標(biāo)準(zhǔn)，也是一個統(tǒng)一的編程環(huán)境，可廣泛適用于各類不同架構(gòu)的CPU、GPU、DSP及FPGA等并行處理器。

圖2所示的算法加速的串行實(shí)現(xiàn)偽代碼如算法1所示。

算法1頻率域算法加速的串行實(shí)現(xiàn)

輸入：特征圖F、模板T

輸出：響應(yīng)圖R

FORTj∈TDO

fTj=forwardFFT(Tj)

//模板正變換

END

FORFi∈FDO

fFi=forwardFFT(Fi)

//特征圖正變換

FORfTj∈fTDO

fSij=fFi·fTj

//頻率域點(diǎn)乘

fRij+=fSij

//頻率域累加

Rij=backwardFFT(fRij)

//響應(yīng)圖逆變換

END

END

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

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

(2) 任務(wù)并行性：算法1中同類型的任務(wù)之間不存在數(shù)據(jù)依賴性，如所有模板的傅里葉變換。而同一FOR循環(huán)內(nèi)的不同類型任務(wù)則需要順序執(zhí)行，如點(diǎn)乘、累加和響應(yīng)圖傅里葉逆變換。

通過調(diào)整FOR循環(huán)的順序，可以使算法1更適宜GPU并行化，如算法2所示。將同一FOR循環(huán)中的任務(wù)依次發(fā)送至GPU，插入到不同的OpenCL命令隊(duì)列，可以使之并行執(zhí)行。若存在數(shù)據(jù)依賴性，則將其插入同一命令隊(duì)列，并通過OpenCL事件進(jìn)行通信，保證執(zhí)行次序。不同F(xiàn)OR循環(huán)間通過同步命令保證內(nèi)存的一致性。

算法2頻率域算法加速的并行實(shí)現(xiàn)

輸入：特征圖F、模板T

輸出：響應(yīng)圖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)

//點(diǎn)乘、累加

END

Synchronization()

FORfRij∈fRDO

Rij,event=backwardFFT(fRij)

//響應(yīng)圖逆變換

readtoCPU(Rij,event)

END

Synchronization()

3.1快速傅里葉變換

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

(9)

(10)

圖3　以2、3、5為基的30點(diǎn)DFT快速計(jì)算流程

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

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

3.2拼接策略和優(yōu)化

前文曾提及需要在傅里葉變換之前將模板填補(bǔ)成與對應(yīng)特征圖同一大小。而簡單的填補(bǔ)方法或?qū)?dǎo)致過高的內(nèi)存開銷，或需要消耗較多的計(jì)算資源，特別是對于部分需要構(gòu)建特征金字塔的卷積檢測模型。

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

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

為避免GPU產(chǎn)生不必要的調(diào)度開銷，不僅需要控制GPU上任務(wù)的數(shù)量，也需要合理設(shè)置每個OpenCL核函數(shù)運(yùn)行時所啟動的線程數(shù)。因此，本文將特征圖和模板的點(diǎn)乘運(yùn)算和累加運(yùn)算合并到一個核函數(shù)中，使用3維NDRange索引空間，每一個工作組計(jì)算一個像素上L維特征的相關(guān)運(yùn)算。這樣不僅可以避免過多的調(diào)度開銷，還能夠更為規(guī)律地進(jìn)行內(nèi)存合并訪問。同時有計(jì)劃地發(fā)送任務(wù)，適當(dāng)?shù)耐揭部山档驼{(diào)度開銷。

4實(shí)驗(yàn)結(jié)果與分析

本文選擇形變部件模型作為基礎(chǔ)，進(jìn)行OpenCL實(shí)現(xiàn)，GPU上的FFT計(jì)算使用clMath數(shù)學(xué)庫中的clFFT函數(shù)庫?；鶞?zhǔn)CPU多線程實(shí)現(xiàn)為Idiap研究所的FFLD[3]，其使用CPU SIMD指令集和OpenMP實(shí)現(xiàn)多線程并行計(jì)算，F(xiàn)FT計(jì)算使用FFTW函數(shù)庫，矩陣運(yùn)算使用Eigen函數(shù)庫。

本文在兩個不同硬件平臺上進(jìn)行了實(shí)驗(yàn)，一個配置為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個流處理器)。

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

表1　CPU多線程實(shí)現(xiàn)與GPU實(shí)現(xiàn)的性能對比

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

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

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

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

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

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

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

5結(jié)語

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

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

參考文獻(xiàn)

[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。國家自然科學(xué)基金項(xiàng)目(61175009);上海市產(chǎn)學(xué)研合作項(xiàng)目(滬CXY-2013-82)。劉琦，碩士生，主研領(lǐng)域：計(jì)算機(jī)視覺，并行計(jì)算。黃咨，碩士生。陳璐艷，碩士生。胡福喬，副教授。

中圖分類號TP3191

文獻(xiàn)標(biāo)識碼A

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