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