基于CUDA的視頻運(yùn)動目標(biāo)檢測算法并行實(shí)現(xiàn)

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

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

?

基于CUDA的視頻運(yùn)動目標(biāo)檢測算法并行實(shí)現(xiàn)

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

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

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

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

0引言

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

1視頻運(yùn)動目標(biāo)檢測算法

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

(2)

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

(3)

(4)

本文視頻運(yùn)動目標(biāo)檢測算法的整體流程如圖1所示.

圖1　視頻運(yùn)動目標(biāo)檢測算法流程圖

2算法并行化

2.1并行任務(wù)劃分

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

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

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

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

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

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

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

3實(shí)驗(yàn)分析

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

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

表1　實(shí)驗(yàn)平臺硬件對比

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

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

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

4結(jié)束語

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

參考文獻(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

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

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

中圖分類號：TN911.73

文獻(xiàn)標(biāo)識碼：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