基于gpu的粒子濾波并行算法

基于gpu的粒子濾波并行算法

貝葉斯估計(jì)目標(biāo)跟蹤問(wèn)題被抽象為系統(tǒng)狀態(tài)估計(jì)問(wèn)題。當(dāng)系統(tǒng)的狀態(tài)方程是線性的，噪聲是高噪聲的時(shí)，根據(jù)卡爾曼濾波方法可以獲得目標(biāo)狀態(tài)概率分布的分析解。然而，在實(shí)踐中，許多非常復(fù)雜的狀態(tài)估計(jì)問(wèn)題包括非線性因素，而不是高斯噪聲，因此很難獲得分析形式的解。顆粒濾波算法是一種基于蒙特卡羅模擬的波葉斯濾波算法。它不受系統(tǒng)線性和高噪聲的限制，廣泛應(yīng)用于定位導(dǎo)航、目標(biāo)跟蹤、建模等領(lǐng)域。近年來(lái)，我國(guó)對(duì)粒子濾波算法進(jìn)行了多方面的改進(jìn)，文獻(xiàn)改進(jìn)了粒子過(guò)濾的表觀模型、運(yùn)動(dòng)模型和重新采樣步驟，并在復(fù)雜場(chǎng)景（如累積涂層）下獲得了更好的跟蹤效果。采用自行時(shí)間分布模型，在目標(biāo)處表達(dá)顏色分布，并使用gpu算法快速計(jì)算疊加圖像以獲得更好的性能。在文獻(xiàn)中，我們提出了一種將各種特征整合到粒子濾波框架中的算法。一些文獻(xiàn)提出了一種高速高斯顆粒濾波算法。目前，nb和nb是一個(gè)通用的計(jì)算結(jié)構(gòu)，單個(gè)顆?？梢酝瑫r(shí)執(zhí)行多個(gè)線程。運(yùn)行過(guò)的程序稱為ktl（內(nèi)核函數(shù)）。cuda和gpu的組合可以分為電池和gpu。其中，cpu端程序是1946年接收頭，負(fù)責(zé)調(diào)用和控制gpu的計(jì)算。gpu是真正的并行計(jì)算部分，是刀片的端。本文基于GPU的粒子濾波并行算法,將傳統(tǒng)粒子濾波算法與GPU有效結(jié)合起來(lái),充分利用GPU并行運(yùn)算的性能,加快粒子濾波算法的計(jì)算速度.1實(shí)行并行算法粒子濾波就是采用一組加權(quán)采樣來(lái)表示狀態(tài)的后驗(yàn)概率密度函數(shù).在實(shí)際應(yīng)用中,一般采用目標(biāo)的梯度直方圖描述目標(biāo),采用Bhattacharyya距離計(jì)算候選區(qū)域顏色分布與目標(biāo)模板顏色分布的相似性.為了避免序貫重要性采樣后出現(xiàn)粒子退化問(wèn)題,粒子濾波算法中加入了重采樣(Resample)的過(guò)程.粒子濾波算法對(duì)圖像每一幀處理的流程大致可以分為重要性采樣、計(jì)算候選區(qū)域的顏色梯度直方圖并給粒子賦權(quán)值、重采樣以及最終目標(biāo)的狀態(tài)估計(jì)等步驟.縱觀整個(gè)算法流程,粒子濾波算法并行化最大的基礎(chǔ)是采樣Ns個(gè)粒子,并對(duì)每個(gè)粒子進(jìn)行相似的數(shù)據(jù)處理,因此重要性采樣以及狀態(tài)估計(jì)采用并行算法執(zhí)行;由于粒子賦權(quán)值、重采樣中存在數(shù)據(jù)相關(guān),因此串行執(zhí)行.基于GPU的粒子濾波并行算法流程如圖1所示.建立4個(gè)Kernel函數(shù)分別實(shí)現(xiàn)粒子濾波的4個(gè)步驟.a.Prediction-Kernel該線程執(zhí)行重要性采樣步驟,其Kernel線程數(shù)與粒子數(shù)Ns相同,每個(gè)線程采樣一個(gè)粒子.每個(gè)線程讀入粒子數(shù)據(jù),然后依據(jù)選取的重要性密度函數(shù)(這里采取隨機(jī)游走模型),各自獨(dú)立更改每個(gè)粒子的狀態(tài),完成對(duì)粒子的采樣.隨機(jī)游走模型中隨機(jī)數(shù)的產(chǎn)生采用平方取中法,各個(gè)粒子之間不會(huì)存在數(shù)據(jù)干擾,可以得到最大化的并行性.b.Weight-Kernel該線程計(jì)算Ns個(gè)粒子的權(quán)值,由2個(gè)步驟串行實(shí)現(xiàn):計(jì)算每個(gè)粒子所對(duì)應(yīng)區(qū)域的梯度直方圖;將每個(gè)粒子的梯度直方圖與初始化時(shí)建立的模板直方圖比較,求取巴特沃斯距離作為每個(gè)粒子的權(quán)值.這個(gè)步驟中的計(jì)算存在并行訪問(wèn)數(shù)據(jù)沖突,所以串行執(zhí)行.實(shí)驗(yàn)發(fā)現(xiàn),若將這部分放在CPU上運(yùn)行,則會(huì)大大增加內(nèi)存訪問(wèn)開(kāi)銷,運(yùn)行速度比在GPU上直接計(jì)算要慢.c.Resample-Kernel該線程執(zhí)行重采樣步驟.依據(jù)上面的算法,對(duì)Ns個(gè)粒子進(jìn)行重采樣時(shí),不可避免地會(huì)產(chǎn)生粒子間的數(shù)據(jù)關(guān)聯(lián),因此采用一個(gè)線程處理Ns個(gè)粒子的重采樣,此方法的實(shí)現(xiàn)速度也比在CPU上要快.d.Calc-Kernel該線程執(zhí)行目標(biāo)運(yùn)動(dòng)狀態(tài)估計(jì),即對(duì)重采樣后的粒子進(jìn)行加權(quán)平均作為目標(biāo)狀態(tài)的最后結(jié)果.這里采用經(jīng)典的并行規(guī)約求和算法,以充分發(fā)揮GPU的并行計(jì)算性能.相比其他串行求和算法,并行規(guī)約算法能夠最大程度并行執(zhí)行,從而有效加快運(yùn)算速度,很容易移植到CUDA平臺(tái).該步驟有Ns個(gè)線程,每個(gè)線程處理一個(gè)粒子.算法的其他部分則由CPU來(lái)完成.算法開(kāi)始時(shí),CPU將每一幀的圖像數(shù)據(jù)拷貝到GPU顯存中,而GPU完成計(jì)算后,將計(jì)算出來(lái)的狀態(tài)反饋給CPU,再由CPU在視頻中顯示出來(lái)并繪制該圖像.程序?qū)崿F(xiàn)中,采用紋理存儲(chǔ)器存儲(chǔ)每一幀圖像數(shù)據(jù),加快運(yùn)算速度.2傳統(tǒng)串歸系濾波算法跟蹤結(jié)果實(shí)驗(yàn)平臺(tái)采用酷睿E2160,2GB內(nèi)存,GPU采用NvidaGeForce8600GT,軟件平臺(tái)為VisualStdio2005.視頻測(cè)試序列來(lái)源于PETS標(biāo)準(zhǔn)測(cè)試序列,分別為車輛跟蹤(序列1,517幀)和人體跟蹤(序列2,217幀),圖像格式為CIF格式.對(duì)于視頻跟蹤而言,不同格式的圖像序列,會(huì)因?yàn)閳D像尺寸的不同,而導(dǎo)致算法執(zhí)行時(shí)間發(fā)生變化.圖像尺寸越大,算法執(zhí)行時(shí)間越長(zhǎng),因此這里只選用CIF格式的圖像序列進(jìn)行試驗(yàn).圖像顏色采用紅藍(lán)綠(RGB)空間,在第60幀手工完成初始化,真值由手工標(biāo)注得到.圖2和圖3分別是粒子數(shù)為512時(shí),傳統(tǒng)串行粒子濾波算法分別對(duì)序列1和序列2中運(yùn)動(dòng)物體的跟蹤結(jié)果.表1列出了當(dāng)粒子數(shù)分別為256和512時(shí),傳統(tǒng)串行粒子濾波算法對(duì)序列1的跟蹤誤差與跟蹤時(shí)間.表中:ex和ey分別為x和y軸坐標(biāo)的跟蹤誤差;tˉtˉ為平均每幀跟蹤時(shí)間.從實(shí)驗(yàn)結(jié)果可以看出:增加粒子濾波的采樣粒子數(shù)可以明顯提高跟蹤準(zhǔn)確率,但增加了計(jì)算量,導(dǎo)致每幀處理時(shí)間大大增加.圖4和圖5為粒子數(shù)為512時(shí),基于GPU的并行粒子濾波算法分別對(duì)序列1和序列2中運(yùn)動(dòng)物體的跟蹤結(jié)果.表2列出了當(dāng)粒子數(shù)分別為256和512時(shí)基于GPU的并行粒子濾波算法對(duì)序列1的跟蹤誤差與跟蹤時(shí)間.對(duì)比表1和表2可以看出:2種粒子濾波算法在跟蹤的準(zhǔn)確性上差別不大,但是基于GPU的并行粒子濾波算法極大減少了每一幀的處理時(shí)間,加速比達(dá)到2.5.從表2還可以看出:采樣粒子數(shù)對(duì)基于GPU的并行粒子濾波算法的跟蹤準(zhǔn)確性以及算法復(fù)雜度也有較大影響.進(jìn)一步分析2種平臺(tái)上粒子濾波算法每一步所用時(shí)間,結(jié)果見(jiàn)表3(測(cè)試序列為序列1).從表3可以看出:GPU上加速最明顯的是并行實(shí)現(xiàn)的重要性采樣和狀態(tài)估計(jì)2個(gè)步驟.雖然權(quán)值更新和重采樣步驟在GPU上串行實(shí)現(xiàn),但由于GPU強(qiáng)大的運(yùn)算能力,速度還是明顯快于在CPU上串行實(shí)現(xiàn).這2步也成為基于GPU的并行粒子濾波算法進(jìn)一步加快的瓶頸.充分利用GPU的并行處理能力,在GPU上實(shí)現(xiàn)了粒子濾波跟蹤并行算法,計(jì)算速度得到了明顯提升.但在GPU上執(zhí)行粒子濾波算法過(guò)程中,賦權(quán)