- 相關(guān)推薦
基于圖形處理器的可變形部件模型算法的并行化
摘要：目前目標識別領(lǐng)域，在人體檢測中精確度最高的算法就是可變形部件模型(DPM)算法，針對DPM算法計算量大的缺點，提出了一種基于圖形處理器(GPU)的并行化解決方法。采用GPU編程模型OpenCL，對DPM算法的整個算法的實現(xiàn)細節(jié)采用了并行化的思想進行重新設(shè)計實現(xiàn)，優(yōu)化算法實現(xiàn)的內(nèi)存模型和線程分配。通過對OpenCV庫和采用GPU重新實現(xiàn)的程序進行對比，在保證了檢測效果的前提下，使得算法的執(zhí)行效率有了近8倍的提高。
關(guān)鍵詞：可變形部件模型;OpenCL;人體檢測;圖形處理器
引言
目前，在無人駕駛、智能監(jiān)控、智能交通等人工智能領(lǐng)域中，人工智能正在發(fā)揮越來越重要的作用，正在逐漸使人類從繁瑣重復(fù)的工作中解放出來。目前在這些領(lǐng)域中，由于這些場景都需要實時監(jiān)測，所以最為普遍的需求是對算法進行并行化加速，以提高算法的執(zhí)行效率，實現(xiàn)實時化處理。
本文將重點介紹一種目標識別算法――可變形部件模型(Deformable Part Model， DPM)算法[1]，目前DPM算法是一個檢測精度非常高的算法，在目標檢測和人臉識別等方面都有很好的應(yīng)用，但是該算法也有計算量非常大、無法完成實時性處理等缺點。本文采用并行化編程模型OpenCL，重新設(shè)計DPM算法的并行化實現(xiàn)，提高算法的執(zhí)行效率，使DPM算法應(yīng)用在實時檢測成為可能。
一、相關(guān)工作
目標檢測一直是計算機視覺領(lǐng)域內(nèi)的難題，尤其是像人體這種非剛性物體，文獻[1]中提到，這類目標外表和目標大小千差萬別，不同角度下人體姿勢也是千變?nèi)f化，由于這類目標不是剛性物體且容易產(chǎn)生形變，所以這類目標檢測起來的難度更大。
2005年，Dalal等[3]兩位法國科學家提出了使用梯度方向直方圖(Histogram of Oriented Gradient， HOG)來描述人體的方法，此方法使用基于HOG特征的單一模板來表示目標，采用HOG+支持向量機(Support Vector Machine，SVM)分類的方法進行人體檢測。使用此模板在圖像的多個尺度和圖像中所有位置上進行人體檢測，進而判別該區(qū)域是否包含人體。目前對HOG算法的并行化已經(jīng)比較成熟，OpenCV中也已經(jīng)提供了HOG算法的并行化版本。
文獻[1]中詳細介紹了DPM算法的實現(xiàn)細節(jié)，包含訓(xùn)練和檢測兩部分的細節(jié)實現(xiàn)，訓(xùn)練部分介紹關(guān)于隱藏變量支持向量機(Latent Support Vector Machine， LSVM)分類器的訓(xùn)練， 目前已成為眾多分類器、分割、人體姿態(tài)和行為分類的重要部分。DPM算法的實現(xiàn)較為復(fù)雜，考慮到根和部件的兩方面，人體的整體作為根，四肢、頭部和肩部等可以作為部件，通過模型，考慮到部件的懲罰，可以最終算出一個根和部件的總分，這樣檢測效果顯著提高，但是由于算法復(fù)雜性的提高，導(dǎo)致執(zhí)行時間大幅增加。然而對于DPM算法的并行化研究工作依然比較少。
2012年，歐洲計算機視覺國際會議(Europeon Conference on Computer Vision， ECCV)，來自美國伯克利大學的團隊，所作的研究就是對DPM算法進行優(yōu)化，使之能滿足實時性要求。該團隊提出一種稀疏模型，使DPM算法的計算量減少，結(jié)合圖形處理器(Graphics Processing Unit， GPU)加速運算，使算法完全滿足實時性的要求，而且在物體的模型訓(xùn)練上也比較全面，檢測精度也非常高。
文獻[2]介紹了基于計算統(tǒng)一設(shè)備架構(gòu)(Compute Unified Device Architecture， CUDA)實現(xiàn)DPM算法并行化的工作，并獲得了10倍的加速比。但是基于CUDA的并行化程序只能運行在Nvidia的獨立顯卡上，無法實現(xiàn)通用性。而OpenCL作為行業(yè)標準，具有通用性。因此，本文考慮采用OpenCL編程模型完成DPM算法的并行化移植。
文獻[3]介紹了梯度方向直方圖(HOG)算法的原理，可變形部件模型(DPM)算法的原理是HOG算法的優(yōu)化，在算法的原理上具有相似的實現(xiàn)原理。文獻[4-9]介紹了基于GPU的算法優(yōu)化和實現(xiàn)原理，以及對算法的改進和DPM算法在不同領(lǐng)域的應(yīng)用。
其中，文獻[1]中詳細介紹了DPM算法的實現(xiàn)細節(jié)，包含訓(xùn)練和檢測兩部分的細節(jié)實現(xiàn)，訓(xùn)練部分介紹關(guān)于LSVM分類器的訓(xùn)練。一系列的關(guān)于算法并行化的工作也已經(jīng)實現(xiàn)，文獻[4-7]中也提到一些基于GPU的算法并行化，以及算法的改進優(yōu)化， 參考文獻[8-9]等可以看出，國內(nèi)很多領(lǐng)域都對DPM算法進行研究并應(yīng)用，文獻[9]中將DPM算法應(yīng)用在人臉檢測中，DPM在人臉檢測中的檢測精度也是非常高的，特別適合人臉檢測的應(yīng)用領(lǐng)域。
通過分析發(fā)現(xiàn)，DPM算法雖然檢測精度高，但卻因計算量巨大而無法對圖像進行實時性檢測。通過對算法的實現(xiàn)細節(jié)進行分析研究，發(fā)現(xiàn)DPM算法特別適合作并行化計算，而且其應(yīng)用前景和領(lǐng)域非常廣泛，所以它的并行化也就顯得十分重要，下面詳細介紹算法的并行化實現(xiàn)。
二、算法的概述
DPM算法是基于HOG的改進，它使用基于根和n個部件間的位置關(guān)系來描述目標的結(jié)構(gòu)，通過根來描述目標的整體輪廓，通過n個部件來描述組成部分，對于人體這種容易發(fā)生形變的目標，再通過部件的偏移進行部件懲罰，使目標檢測更加準確。DPM可以理解為一種星型結(jié)構(gòu)，此模型由1個根濾波器和n個部件濾波器組成，用整個模型來描述一個目標，目標的得分等于根得分加n個部件得分。在計算部件得分時，由于人體等非剛性目標的可變形，所以計算部件得分時需要在每個部件的理想位置的周圍搜索部件的實際位置，部件在實際位置的最終得分等于部件在實際位置的特征值向量與濾波器的卷積得分減去部件實際位置相對于理想位置的偏移懲罰，用偏移懲罰來衡量目標的形變程度。根和部件的得分就是窗口特征值和濾波器的卷積。
含有n個部件的目標模型可以表示為一個(n+2)元組：(F0，P1，P2，…，Pn，b)，每個部件模型可以表示為一個三元組(Fi，vi，di)，其中： Pi表示第i個部件濾波器; vi是一個二維向量，表示第i個部件濾波器的錨點位置; di是一個四維向量，表示部件發(fā)生形變時的相對于錨點位置的變形懲罰。含有n個部件的目標模型的得分等于根濾波器分數(shù)加部件濾波器分數(shù)，減去部件濾波器相對于根位置的變形懲罰，再加上一個偏差值：
∑ni=0Fi・φ(H，pi)-∑ni=1di・φd(dxi，dyi)+b (1)
其中：H表示特征金字塔;pi=(xi，yi，l)代表計算的圖像金字塔l層坐標為(xi，yi)的窗口特征值;式(1)中的變量(dxi，dyi)=(xi，yi)-(2(x0，y0)+vi)，其中： (xi，yi)表示第i個部件濾波器的坐標，部件濾波器所在層的特征分辨率是根濾波器所在層的特征分辨率的2倍; (x0，y0)表示根濾波器的坐標;vi代表該部件的錨點位置，是一個二維向量。∑ni=1di・φd(dxi，dyi)是對部件的變形懲罰，具體系數(shù)會在訓(xùn)練好的分類器中。
三、DPM算法的GPU并行化實現(xiàn)
CPU多核架構(gòu)并不擅長于處理高清視頻圖像，但是GPU的眾核架構(gòu)在處理高清視頻圖像時具有非常大的優(yōu)勢。
通過利用參考文獻[13-14]中介紹的CUDA和OpenCL編程模型，本文針對GPU的架構(gòu)特點，對算法重新設(shè)計，無論是從執(zhí)行模式還是從數(shù)據(jù)的存儲模式，都需要針對并行化的方案進行重新設(shè)計�？勺冃尾考Ｐ退惴ǖ牟⑿谢唧w實現(xiàn)步驟如下。
3.1建立圖像金字塔
輸入圖像中人體尺寸的大小不一，而模型中檢測窗口的大小是固定的，所以，需要通過縮放圖像來適應(yīng)檢測窗口的大小，使算法能夠檢測到圖像中任意大小的人體。對某一尺度的圖像縮放時，圖像中所有像素點之間的處理沒有邏輯關(guān)系，非常適合并行化處理，為圖像中的所有坐標位置分配一個線程，所有線程完成對對應(yīng)坐標的像素點計算，通過不斷地調(diào)整縮放尺度，最終建立一個圖像金字塔。圖像金字塔每隔10層縮放為原圖像的一半。
3.2計算圖像金字塔的梯度方向
圖像金字塔建立完成后，將計算圖像中所有像素點的梯度方向和梯度幅值。本文采用濾波器[-1，0，1]以及其轉(zhuǎn)置來計算坐標為(x，y)處的像素點梯度幅值和方向。對于RGB彩色圖像來說，我們分別計算像素點每一通道的幅值和方向，選取幅值最大的那一通道的梯度幅值和方向作為當前像素點處的梯度幅值和方向。
Gx(x，y)=H(x+1，y)-H(x-1，y)(2
Gy(x，y)=H(x，y+1)-H(x，y-1)(3)
式中：Gx(x，y)，Gy(x，y)分別為當前坐標為(x，y)處像素點的水平方向梯度和垂直方向梯度。像素點(x，y)處的梯度幅值和梯度方向分別為：
G(x，y)=Gx(x，y)2+Gy(x，y)2(4
θ(x，y)=tan-1(Gx(x，y)Gy(x，y))(5
通過對上面的原理分析，可以看到，圖像中每個像素點對應(yīng)位置的梯度幅值和方向的計算均是獨立的，和鄰域內(nèi)的計算沒有任何邏輯關(guān)系，圖像中所有像素點對應(yīng)坐標可以并行計算，每個線程計算一個像素點對應(yīng)坐標的梯度方向和幅值，圖像邊緣可以將梯度幅值和方向賦固定值(比如0)。
3.3計算梯度方向直方圖
參考文獻[1-2]中的直方圖計算方法，將圖像按照8×8個像素點作為一個cell進行分割，根據(jù)之前計算的每個像素點對應(yīng)坐標的梯度方向和幅值，本文將以像素點的坐標(x，y)算出4個像素點的坐標; 然后依照當前像素點坐標(x，y)在其所處的8×8的cell當中的位置，分別算出對應(yīng)的4個像素點的權(quán)重，用4個像素點的梯度幅值分別乘以權(quán)重進行投票，進行直方圖歸一化操作，最終每個cell將得到一個梯度方向直方圖。
在設(shè)計GPU并行化解決方案時，考慮到線程之間的沖突和效率的原因，每個線程對應(yīng)一個像素點的計算，本文為每個線程分配了一個18維(一個18個元素的float型數(shù)組)的共享內(nèi)存，這樣每個線程就會得到一個18維的梯度方向直方圖，然后采用折半規(guī)約的方法進行規(guī)約，最終規(guī)約為每個cell一個梯度方向直方圖。
通過計算得到對比度敏感的18維的梯度方向直方圖和對比度不敏感的9維梯度方向直方圖。為實現(xiàn)梯度方向直方圖對偏置改變的不變性，本文將對得到的直方圖分別進行歸一化操作。根據(jù)當前cell的位置與周圍cell的位置關(guān)系，算出4個歸一化因子，對當前cell的9維和18維梯度方向直方圖分別進行歸一化操作和截斷(截斷因子設(shè)為0.2)，然后再將4個歸一化因子作為最后4維，得到最終的31維梯度方向直方圖。
在設(shè)計歸一化計算GPU實現(xiàn)時，本文為每個8×8的cell分配一個線程，每個線程都負責對當前cell的18維和9維的梯度方向直方圖分別進行歸一化，加上4個歸一化因子，最終得到當前cell的31維梯度方向直方圖。
3.4窗口區(qū)域特征值和濾波器的卷積
本文將在圖像金字塔的所有尺度的縮放圖像上進行人體檢測，檢測窗口的大小不一。對于根模型，本文使用三種大�。�9×8、11×7、11×4(均以cell為單位)，而對于部件模型，部件的大小均為6×6個cell組成。窗口的特征值即為該窗口內(nèi)包含的cell的特征值串聯(lián)起來，然后窗口的特征值和訓(xùn)練好的濾波器進行卷積，得到該窗口在圖像中該位置的分數(shù)，在圖像金字塔每一尺度上所有位置進行檢測，得到所有尺度所有位置處的窗口分數(shù)。這樣得到了圖像金字塔所有尺度上的所有位置的根分數(shù)和部件分數(shù)，下一步就是對根和部件進行鏈接，得到整個檢測窗口的分數(shù)。
在設(shè)計GPU并行化解決方案時，本文為每個檢測窗口分配一個線程，相鄰檢測窗口之間相隔1個cell，可以理解為檢測窗口的滑動步長為1個cell。在圖像金字塔的某一個尺度上進行計算時，當前層由M×N個cell組成，那么就分配M×N個線程，通過內(nèi)部的線程控制，使每個線程計算對應(yīng)窗口的濾波器和特征值卷積，至于block線程分配，本文采用每個block由8×8個線程組成，可以根據(jù)實際情況合理調(diào)整。同時，內(nèi)存的訪問對于核函數(shù)的執(zhí)行效率也有非常大的影響，本文在設(shè)計內(nèi)存存儲模型時，也嘗試了多種內(nèi)存的使用。最終，在上面的線程分配方案下，采用共享內(nèi)存的方式，將當前block內(nèi)的所有線程所需要的數(shù)據(jù)從全局內(nèi)存緩存到共享內(nèi)存中，然后線程進行計算，減少對全局內(nèi)存的訪問，大大提高了核函數(shù)的執(zhí)行效率。
3.5距離轉(zhuǎn)換
通過特征值和濾波器的卷積，得到圖像金字塔中所有層中所有位置處的根和部件的得分，然后將可變形部件模型中根和部件聯(lián)系起來，最終得到目標分數(shù)。首先部件位于圖像金字塔中2倍于根所在圖像大小的層，也就是部件所在層的特征分辨率是根所在層的特征分辨率的2倍，這樣部件就可以捕獲到相對于根更加精確的特征信息。目標的得分是根得分加一系列部件的得分之和，本文在計算部件得分時，將根坐標的2倍加錨點的位置，不同部件的錨點不同，這樣就會得到不同部件未發(fā)生形變時的理想位置，而對于人這種容易發(fā)生形變的目標，要在理想位置的一定范圍內(nèi)進行部件實際位置的搜索，根據(jù)偏移對部件的實際位置出進行懲罰，得到實際位置處部件的得分。
Di，l(x，y)=maxdx，dy(Ri，l(x+dx，y+dy)-
di・φd(dx，dy))(6
距離轉(zhuǎn)換將部件的變形懲罰考慮在內(nèi)，在進行搜索的過程中，如果其中某個位置偏離錨點位置越遠，則懲罰越嚴重，在部件的錨點附近尋找對部件濾波器響應(yīng)最高分的檢測窗口，這個窗口就是該部件的實際位置。
在設(shè)計GPU并行化解決方案時，通過分析可以看到，不同的根和部件的鏈接都是相互獨立計算的，之前沒有邏輯關(guān)系，所以本文的實現(xiàn)中為每一個根濾波器分配一個線程，每個線程負責處理在圖像中某個位置處的檢測窗口的根和部件的鏈接，同時負責在部件的錨點位置附近搜索部件的實際位置。從中可以看到，每個線程需要完成的計算量非常大，但是我們也嘗試了其他的線程分配方式，發(fā)現(xiàn)這種的線程分配方式是執(zhí)行時間最短的。
3.6包圍盒合并
本文檢測過程是對在圖像金字塔中所有尺度的所有位置進行檢測，這樣就會出現(xiàn)同一個目標被多個框體包圍的情況，本文使用非最大值抑制算法消除多余框體，根據(jù)框體的重疊面積，若重疊面積大于某一閾值，就貪心地保留分數(shù)較大的一個框體，實驗表明，這種去除多余框體的效果非常好。
關(guān)于這一部分的并行化設(shè)計，發(fā)現(xiàn)圖像金字塔的使用，不同層之間存在屬于同一目標的窗體，而且需要將不同層的框體恢復(fù)到原圖像中，依據(jù)框體所在的層數(shù)和當前檢測窗體的大小進行恢復(fù)，而且金字塔中大部分的位置是沒有人體的，如果采用并行化操作，肯定會大大增加計算量。所以本文將金字塔中的分數(shù)大于一定閾值的窗口信息拷回CPU端進行處理。本文將設(shè)計一個結(jié)構(gòu)體，結(jié)構(gòu)體中包含框體左上角坐標、寬高、分數(shù)、所處層數(shù)等信息，并且設(shè)置一個標志位，根據(jù)所有尺度下的窗體的重疊面積，若重疊面積大于某一閾值，根據(jù)兩個窗體的分數(shù)大小，將分數(shù)較小的窗體的標志位置為false。這種方法大大減少計算量，并且去除多余窗體的效果非常好。
四、實驗結(jié)果及分析
本文測試檢測效果和加速效果時，均是和OpenCV庫中的DPM算法進行對比，同時本文也分析了顯卡的資源使用情況。測試設(shè)備使用Intel Core i54460 CPU，內(nèi)存4GB，顯卡采用Intel集成顯卡HD Graphics 4600。
4.1DPM算法的效果測試
測試圖像中，本文選取比較有代表性的場景進行檢測。測試效果如圖1所示，在下面所有的基于OpenCV的檢測圖片中，每個檢測窗口上的數(shù)字代表了該檢測窗口的分數(shù)。
第1組測試的場景是單個行人且背景較為簡單的情況;第2組測試的場景是單個行人，背景復(fù)雜且人體被部分遮擋的情況;第3組測試的場景是人數(shù)較多且人體之間相互存在遮擋的情況;第4組測試的場景是背景較為復(fù)雜的實際路況的圖像，模擬車載攝像頭的工作環(huán)境。
由上面4組具有代表性的檢測圖片可以看出，本文基于GPU實現(xiàn)的DPM算法的并行化，在檢測效果上已經(jīng)和OpenCV庫接近一致，甚至要比OpenCV庫檢測效果更好。尤其是最后一張在車載攝像頭的情況下，本文算法實現(xiàn)依然有比較好的檢測效果。
4.2DPM算法加速效果分析
在檢測效果和OpenCV保持一致甚至更優(yōu)的前提下，本文將重點測試一下基于GPU的DPM算法相比OpenCV中CPU級聯(lián)實現(xiàn)的加速效果。本文的測試環(huán)境依然是在Intel集成顯卡HD Graphics 4600上進行測試。
由表1和圖2中的數(shù)據(jù)，結(jié)合上一節(jié)中的檢測效果可以看到，在保持檢測精度和OpenCV一致的前提下，本文算法的執(zhí)行效率有數(shù)倍的提高，并且在高清圖像的處理中，檢測效率有了近7倍的提高。由圖2可以看出，圖像越高清，數(shù)據(jù)量越大，利用GPU進行加速的效果越明顯。
4.3顯卡資源使用分析
對于集成顯卡HD Graphics 4600來說，流處理器數(shù)量為20，位寬64B，帶寬12.8GB/s，顯存類型DDR3，GPU默認時鐘頻率350MHz，顯存默認時鐘頻率800MHz。
通過表2中運行時參數(shù)變化可以看到：GPU的核心頻率在運行時由600MHz變?yōu)?100MHz;GPU Power表示顯卡功耗，由正常顯示時的0.2W變?yōu)檫\行時的9.0W;GPU load表示GPU的占用量，正常顯示時是5%甚至更低，運行DPM時是56%甚至更高到60%以上，還是有提高的空間。下面兩個分別為顯存的使用量，第一個為專用顯存使用量，可以看到幾乎沒有變化;第二個為動態(tài)顯存使用量由242MB變?yōu)?46MB，大概要增加300MB左右的動態(tài)顯存，這是因為對于集成顯卡來說，顯存是在內(nèi)存上動態(tài)分配的，所以在運行的時候，DPM算法在運行時需要較多的顯存空間，所以系統(tǒng)需要動態(tài)地為集成顯卡分配顯存。
五、結(jié)語
可變形部件模型算法是目前最好的目標檢測算法，本文通過對算法的并行化分析和實現(xiàn)，完成算法的GPU移植，使算法的執(zhí)行效率顯著提高，在某些特定情況下，結(jié)合其他算法，能夠?qū)崿F(xiàn)對小圖像實時檢測的要求。在模式識別領(lǐng)域中，進行目標檢測很重要的一環(huán)是分類器的訓(xùn)練，在接下來的工作中，我們將嘗試將GPU用在深度學習方面，通過GPU來訓(xùn)練分類器，使分類器的訓(xùn)練效率能夠有明顯提高，同時訓(xùn)練出自己的模型，使DPM算法能夠在人臉檢測等更多領(lǐng)域中有最好的檢測效果。
參考文獻：
[1]FELZENSZWALB P F， GIRSHICK R B， MCALLESTE D， et al. Object detection with discriminatively trained partbased models [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2010， 32(9)：1627-1645.
[2]GADESKI E， FARD H O， BORGNE H L. GPU deformable part model for object recognition[J]. Journal of RealTime Image Processing， 2014：1-13.
【基于圖形處理器的可變形部件模型算法的并行化】相關(guān)文章：
基于質(zhì)量技術(shù)特征改善率的并行優(yōu)化模型分析03-19
基于記憶多項式模型數(shù)字預(yù)失真算法的改進03-07
基于遺傳算法的模型在交通線路選擇中的應(yīng)用03-07
基于NNVD的網(wǎng)絡(luò)化軟件多步控制算法研究03-11
基于場源離散化方法的體內(nèi)微型診療裝置定位模型及驗證11-22
基于微處理器的FPGA配置方案03-07
基于DSP的信道譯碼算法優(yōu)化03-19