樓先濠，郭春生，宋少雷，齊利泉

(杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018)

?

基于CUDA的視頻運動目標檢測算法并行實現(xiàn)

樓先濠，郭春生，宋少雷，齊利泉

(杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018)

摘要：在視頻運動目標檢測的能量優(yōu)化算法中，引入目標先驗約束信息，能有效地提高目標檢測性能，同時也極大地增加了算法的復(fù)雜度.以CUDA平臺為基礎(chǔ)，從算法并行任務(wù)劃分，實現(xiàn)粗細粒度并行；從合理規(guī)劃GPU內(nèi)存分配，提高數(shù)據(jù)的吞吐率兩方面實現(xiàn)了帶約束的能量優(yōu)化視頻運動目標檢測算法的高效并行.實驗結(jié)果表明，算法的GPU并行實現(xiàn)與CPU串行實現(xiàn)相比，顯著提高了計算速度.

關(guān)鍵詞：目標檢測；能量優(yōu)化；并行計算；統(tǒng)一計算設(shè)備架構(gòu)

0引言

基于混合高斯背景建模的檢測算法在視頻運動目標檢測領(lǐng)域得到廣泛應(yīng)用，但存在目標空洞、目標偽裝和復(fù)雜背景適應(yīng)性等問題[1]，因此基于全局能量最小化的混合高斯背景建模的運動目標檢測算法得到關(guān)注[2].帶目標先驗信息約束的全局能量最小化運動目標檢測算法在改善運動目標檢測性能的同時，也帶來了計算量顯著增加的問題.例如，當(dāng)采用最大流/最小割的MATLAB實現(xiàn)對分辨率為768×576的視頻序列進行運動目標分割，網(wǎng)絡(luò)流參數(shù)計算和分配部分占全部計算時間的90%以上，嚴重影響了算法的計算效率.近年來，高重復(fù)性且運算量大的圖像視頻分析處理常利用GPU并行計算來改善計算效率.文獻[3]利用GPU加速實現(xiàn)了非參數(shù)背景建模實時運動目標檢測，文獻[4]則利用統(tǒng)一計算設(shè)備架構(gòu)(Compute Unified Device Architecture，CUDA)并行相應(yīng)算法實現(xiàn)了對高光譜圖像的實時異常檢測.本文通過分析帶目標先驗信息約束的全局能量最小化運動目標檢測算法中網(wǎng)絡(luò)流計算部分的并行性，結(jié)合CUDA存儲架構(gòu)特點，實現(xiàn)了算法的并行計算，提高了目標檢測的實時性.實驗中對分辨率為768×576的視頻序列進行測試，結(jié)果表明本算法的并行處理速度能夠接近實時.

1視頻運動目標檢測算法

本文采用的基于最大流/最小割的能量最小化方法，其能量函數(shù)表示為：

(2)

Pn,m為相鄰兩個像素點m，n受加權(quán)梯度約束時分屬于目標和背景的概率，定義為：

(3)

(4)

本文視頻運動目標檢測算法的整體流程如圖1所示.

圖1　視頻運動目標檢測算法流程圖

2算法并行化

2.1并行任務(wù)劃分

本文通過將網(wǎng)絡(luò)流參數(shù)計算中的概率密度值計算、高斯濾波、區(qū)域項計算、梯度計算以及梯度加權(quán)計算定義為功能獨立的CUDA內(nèi)核，以此實現(xiàn)算法并行.依據(jù)圖像按行連續(xù)排列存儲的特點以及CUDA線程模型的特點對各個內(nèi)核的計算任務(wù)做了粗細粒度的劃分.首先，以行作為劃分依據(jù)，按照行數(shù)H將視頻圖像劃分成優(yōu)先級一致的H組，實現(xiàn)粗粒度的并行；其次，各行圖像以像素為單位再劃分，實現(xiàn)細粒度的并行.

下面以計算概率密度值內(nèi)核為例具體分析內(nèi)核任務(wù)的劃分情況.內(nèi)核任務(wù)并行劃分如圖2所示，CUDA中的內(nèi)核是以線程網(wǎng)格(Grid)的形式組織，一個內(nèi)核對應(yīng)一個線程網(wǎng)格，線程網(wǎng)格包含若干個線程塊(Block)，線程塊又包含若干個線程(Thread)[5].內(nèi)核任務(wù)劃分對應(yīng)到上述線程模型：一幀視頻圖像即映射到網(wǎng)格上；一行視頻圖像即映射到一個線程塊；一行中的像素點即映射到線程塊中的線程.本文中網(wǎng)格和線程塊都設(shè)置為一維模式：一個網(wǎng)格包含H個線程塊，其中第i(1≤i≤H)個線程塊負責(zé)計算視頻圖像的第i行數(shù)據(jù)；每個線程塊中啟動S個線程，其中第j(1≤j≤S)號線程負責(zé)計算第j+S×k(k=0,1,2，…)個像素點(j+S×k≤圖像寬度W).圖2中，左下角圖像代表連續(xù)輸入的視頻圖像，任務(wù)劃分完成后，每一個CUDA線程都執(zhí)行相同的指令并按照自身的線程號索引來讀取數(shù)據(jù)，實現(xiàn)并行計算，最終得到右下角表示目標出現(xiàn)的概率密度圖.其他內(nèi)核任務(wù)劃分與上述內(nèi)核一致，都按照以行為單位的劃分方法進行了任務(wù)劃分.

2.2內(nèi)存規(guī)劃

本文從紋理內(nèi)存和共享內(nèi)存兩個方面對內(nèi)存進行規(guī)劃.首先，將輸入圖像數(shù)據(jù)綁定至紋理內(nèi)存，以此來優(yōu)化二維圖像的隨機讀取速度；其次，根據(jù)一個線程塊對應(yīng)一行數(shù)據(jù)的并行任務(wù)劃分方式規(guī)劃了共享內(nèi)存的使用；最后，結(jié)合紋理內(nèi)存和共享內(nèi)存一起使用來加速高斯濾波和梯度計算兩個內(nèi)核.本文算法在GPU中的整體內(nèi)存規(guī)劃如圖3所示.

圖2　“計算概率密度值”內(nèi)核任務(wù)并行劃分示意圖

圖3　并行算法內(nèi)存規(guī)劃及數(shù)據(jù)流轉(zhuǎn)示意圖

圖3中，數(shù)字標明了本文并行算法中數(shù)據(jù)在GPU內(nèi)存中的流轉(zhuǎn)順序.各個內(nèi)核計算得到的中間值被保存在全局內(nèi)存中，因此內(nèi)核在開始計算時，首先根據(jù)并行任務(wù)劃分方式從全局內(nèi)存將計算當(dāng)前行所需的數(shù)據(jù)存入共享內(nèi)存，這樣，塊內(nèi)線程就能以低延遲讀取共享內(nèi)存，從而加快計算速度.傳統(tǒng)內(nèi)存優(yōu)化方式僅使用了紋理內(nèi)存或者共享內(nèi)存，單使用紋理內(nèi)存速度沒有使用共享內(nèi)存快，單使用共享內(nèi)存不如使用紋理內(nèi)存方便.本文將紋理內(nèi)存和共享內(nèi)存結(jié)合起來使用，即提高了讀取速度，又能利用紋理特性來處理圖像邊界問題，達到以空間換時間的目的.

3實驗分析

為比較本文算法并行的有效性，本文做了另外兩種不同的實現(xiàn)：一是純MATLAB代碼實現(xiàn)，二是把網(wǎng)絡(luò)流參數(shù)計算部分轉(zhuǎn)化成C代碼串行實現(xiàn).本文將CUDA并行和C串行的代碼都編譯成MEX函數(shù)的形式，再由MATLAB調(diào)用執(zhí)行.CUDA-MEX、MATLAB和C-MEX分別代表3種實現(xiàn)方式.MEX函數(shù)由Microsoft Visual C++2010和CUDA5.5版本NVCC編譯器編譯.MATLAB為2012b 64位版本.

為測試本文并行算法在不同GPU上的加速能力，在兩個實驗平臺上做了對比分析.兩個平臺軟件環(huán)境一致，操作系統(tǒng)均為Windows7 64位版本，硬件配置不同之處如表1所示.

表1　實驗平臺硬件對比

實驗對不同分辨率大小的視頻作了對比分析，統(tǒng)計單幀圖像網(wǎng)絡(luò)流參數(shù)計算的時間，具體情況如表2所示.加速比Sp定義為Sp=Ts/Tp，Ts表示串行程序執(zhí)行時間，Tp表示并行程序執(zhí)行時間.表2中，以Sp1表示CUDA-MEX實現(xiàn)相對MATLAB實現(xiàn)的加速比，Sp2表示CUDA-MEX實現(xiàn)相對C-MEX實現(xiàn)的加速比.

表2　3種實現(xiàn)方法運算時間對比

從表2中的Sp1可以清晰地看到GPU并行實現(xiàn)帶來的巨大效果，對MATLAB實現(xiàn)來說高分辨率圖像甚至達到了上萬倍的加速效果.Sp2數(shù)據(jù)更加真實地反映了加速情況，從中可以看到平臺1的CUDA并行加速效果較為明顯.以432×288分辨率的視頻為例，平臺1的網(wǎng)絡(luò)流并行計算速度較平臺2快7.7倍(0.109/0.014)，而720×480分辨率快8.4倍(0.262/0.031)，這也反應(yīng)了平臺1的GPU計算能力較強.平臺2雖然計算能力只有1.2，但是隨著視頻分辨率增加也取得了一定的加速效果.兩個平臺在圖像尺寸為160×128的情況下，并行實現(xiàn)效果反而不如CPU串行實現(xiàn)，原因在于調(diào)用CUDA需要在主機和設(shè)備之間傳遞數(shù)據(jù)，而在計算量較小的情況下通過并行加速節(jié)省的時間還不足以掩蓋傳輸數(shù)據(jù)帶來的延遲.

4結(jié)束語

帶約束的能量最小化視頻運動目標檢測算法比普通目標檢測算法性能更優(yōu)，但是過高的算法復(fù)雜度限制了它的使用范圍.本文實現(xiàn)了一種基于CUDA并行計算的帶約束能量最小化視頻檢測算法.算法將計算任務(wù)劃分至多線程并行實現(xiàn)，同時充分利用了GPU中紋理內(nèi)存和共享內(nèi)存的特性，提高了數(shù)據(jù)吞吐量.實驗結(jié)果表明了本算法并行實現(xiàn)的高效性，在不同平臺上都取得了顯著的加速效果.

參考文獻

[1]BOUWMANST,ElBafF,VACHONB.Backgroundmodelingusingmixtureofgaussiansforforegrounddetection-asurvey[J].RecentPatentsonComputerScience, 2008, 1(3): 219-237.

[2]GUOC,LIUD,GUOYF,etal.Anadaptivegraphcutalgorithmforvideomovingobjectsdetection[J].MultimediaToolsandApplications, 2014, 72(3): 2633-2652.

[3]BERJOND,CUEVASC,MORANF,etal.GPU-basedimplementationofanoptimizednonparametricbackgroundmodelingforreal-timemovingobjectdetection[J].ConsumerElectronics,IEEETransactionson, 2013, 59(2): 361-369.

[4]TARABALKAY,HAAVARDSHOLMTV,K?SENI,etal.Real-timeanomalydetectioninhyperspectralimagesusingmultivariatenormalmixturemodelsandGPUprocessing[J].JournalofReal-TimeImageProcessing, 2009, 4(3): 287-300.

[5]NVIDIA.CUDACProgrammingGuide[EB/OL].[2015-09-01].http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html.

DOI：10.13954/j.cnki.hdu.2016.03.005

收稿日期：2015-10-16

基金項目：國家自然科學(xué)基金資助項目(61372157)

作者簡介：樓先濠(1990-)，男，浙江浦江人，碩士研究生，電子與通信工程.通信作者：郭春生副教授，E-mail：guo.chsh@gmail.com.

中圖分類號：TN911.73

文獻標識碼：A

文章編號：1001-9146(2016)03-0023-04

Parallel Implementation of Video Moving Object Detection Algorithm Based on CUDA

LOU Xianhao, GUO Chunsheng, SONG Shaolei, QI Liquan

(SchoolofCommunicationEngineering,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：In the energy optimization algorithm of video moving object detection, the introduction of object priori constraint information such as edge length helped to achieve a more robust detection, but also greatly increased the complexity of the algorithm. On the compute unified device architecture(CUDA) platform, this paper implemented a moving object detection algorithm based on constrained energy optimization with high efficiency by two aspects: multi-granularity parallelization by parallel task partition, elevated data throughput by optimized GPU memory allocation. Experimental results show that the parallel algorithm achieved a significant improvement of computing speed compared with the serial algorithm.

Key words：object detection; energy optimization; parallel implementation; compute unified device architecture