張 剛，馬震環(huán)，雷 濤，崔 毅，張三喜

(1.中國(guó)科學(xué)院大學(xué)，北京100049；2.中國(guó)科學(xué)院光電技術(shù)研究所，四川 成都 610209;3.中國(guó)華陰兵器試驗(yàn)中心，陜西 華陰 714200)

引言

在光電監(jiān)視系統(tǒng)中，運(yùn)動(dòng)目標(biāo)分割為進(jìn)一步實(shí)現(xiàn)目標(biāo)跟蹤、目標(biāo)識(shí)別、行為分析等高層應(yīng)用奠定了基礎(chǔ)。背景減除法是運(yùn)動(dòng)目標(biāo)分割的重要方法之一，其基本思想是通過(guò)建立一個(gè)背景模型，通過(guò)比較當(dāng)前視頻幀與背景模型的差異分割出前景物體。背景減除法大致可分為兩類，一類是基于參數(shù)模型的方法，另一類是基于非參數(shù)模型的方法。高斯混合模型[1]是一種經(jīng)典的參數(shù)模型算法，它通過(guò)多個(gè)高斯分布平滑地模擬像素的變化情況。PBAS算法[2]是一種廣泛使用的非參數(shù)模型算法，它是在ViBe算法[3]的基礎(chǔ)上，利用觀測(cè)到的像素點(diǎn)建立背景模型，為每個(gè)像素點(diǎn)分別設(shè)立單獨(dú)的判別閾值和學(xué)習(xí)率，根據(jù)背景的變化不斷更新背景模型。PBAS算法良好的性能是以計(jì)算復(fù)雜和參數(shù)量大為代價(jià)的。它需要計(jì)算圖像中每個(gè)像素點(diǎn)與背景模型中相應(yīng)像素點(diǎn)的歐氏距離，以一定概率自適應(yīng)更新背景模型和相關(guān)參數(shù)。為達(dá)到良好的性能，需要存儲(chǔ)30幀以上的圖像數(shù)據(jù)作為背景模型以及每個(gè)像素點(diǎn)的模型參數(shù)。因此，若不對(duì)其進(jìn)行并行優(yōu)化，難以達(dá)到對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行實(shí)時(shí)分割的要求。由于PBAS算法是對(duì)每個(gè)像素點(diǎn)獨(dú)立處理的，特別適合于在并行結(jié)構(gòu)的處理器上進(jìn)行實(shí)時(shí)實(shí)現(xiàn)。隨著多核處理器的不斷發(fā)展，具有強(qiáng)大并行計(jì)算能力的GPU越來(lái)越多的被應(yīng)用于高計(jì)算需求的領(lǐng)域。隨著CUDA(compute unified device architecture)[4-6]的推出，大大提高了GPU的可編程性，使得開(kāi)發(fā)人員能更好地把GPU大規(guī)模并行計(jì)算的能力發(fā)揮出來(lái)。因此，GPU是進(jìn)行PBAS算法并行優(yōu)化的理想處理器平臺(tái)。

本文通過(guò)分析PBAS算法和GPU的并行架構(gòu)特點(diǎn)，在數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、共享內(nèi)存使用、隨機(jī)數(shù)產(chǎn)生機(jī)制三個(gè)方面對(duì)PBAS算法進(jìn)行了并行優(yōu)化。在嵌入式GPU平臺(tái)Jetson TX2[7-8]上的實(shí)驗(yàn)結(jié)果表明，對(duì)于480×320像素分辨率的中波紅外視頻序列，該并行優(yōu)化方法可以達(dá)到132 fps的處理速度，滿足了實(shí)時(shí)處理的要求。

1 相關(guān)理論

1.1 PBAS算法原理

PBAS算法針對(duì)當(dāng)前幀每個(gè)像素點(diǎn)，統(tǒng)計(jì)N個(gè)相應(yīng)像素點(diǎn)的歷史值作為其背景模型，為每個(gè)像素點(diǎn)建立獨(dú)立的前景判別閾值和背景更新的相關(guān)學(xué)習(xí)參數(shù)，根據(jù)背景變化動(dòng)態(tài)地控制這些狀態(tài)變量。圖1是PBAS算法的結(jié)構(gòu)框圖。

圖1 PBAS算法結(jié)構(gòu)框圖Fig.1 Architecture of PBAS algorithm

前景/背景決策模塊主要完成輸入視頻序列與背景模型的背景減除，分割出前景物體，其實(shí)質(zhì)上是一個(gè)二分類器。在PBAS算法中，每個(gè)像素點(diǎn)xi的背景模型由N個(gè)背景像素點(diǎn)組成：

B(xi)={B1(xi),B2(xi),…,BN(xi)}

(1)

如果像素點(diǎn)xi的值I(xi)與背景模型中的N個(gè)像素點(diǎn)B(xi) 的距離小于決策閾值R(xi)的個(gè)數(shù)小于#min，則該像素點(diǎn)被判定為前景像素，否則為背景像素，即：

(2)

其中：F(xi)=1表示前景像素；F(xi)=0表示背景像素。有兩個(gè)參數(shù)：1) 針對(duì)每個(gè)像素點(diǎn)xi，決策閾值R(xi)是相互獨(dú)立且動(dòng)態(tài)變化的；2) 小于R(xi)的背景像素的個(gè)數(shù)#min，是全局固定參數(shù)，一般取值2。

對(duì)于背景模型的更新，當(dāng)某個(gè)像素點(diǎn)被判定為背景像素時(shí)，以概率1/T(xi)用當(dāng)前像素值I(xi)隨機(jī)更新背景模型中相應(yīng)的像素點(diǎn)B(xi)。更新率T(xi)決定了背景模型更新的速度，T(xi)越大，被更新的概率越小。在更新當(dāng)前像素點(diǎn)的相應(yīng)背景像素點(diǎn)時(shí)，同時(shí)隨機(jī)選取其鄰域內(nèi)的某個(gè)像素點(diǎn)yi，以相同的方式用當(dāng)前像素值I(yi)以概率1/T(xi)更新背景模型中某個(gè)隨機(jī)選取的像素點(diǎn)B(yi)。

(3)

其中Rinc/dec、Rscale為全局固定參數(shù)，一般分別取值0.05和5。

(4)

其中Tinc、Tdec為全局固定參數(shù)，一般分別取值1和0.05。同時(shí)，PBAS算法規(guī)定Tlower

1.2 GPU架構(gòu)

GPU是一種SIMT(single instruction multiple threads)架構(gòu)的并行處理器[9]，它的主要特點(diǎn)是多個(gè)線程并行執(zhí)行同一條指令，處理不同的數(shù)據(jù)。在本文的實(shí)驗(yàn)中，我們使用的是NVIDIA公司的嵌入式GPU-Jetson TX2，它包含2個(gè)SM，每個(gè)SM包含128個(gè)Pascal架構(gòu)的處理器內(nèi)核[7]。圖2是SM的內(nèi)部結(jié)構(gòu)圖。由圖可知，除了128個(gè)內(nèi)核外，SM還包括各種存儲(chǔ)單元、線程束調(diào)度器(warp scheduler)及其他功能單元等。

圖2 SM內(nèi)部結(jié)構(gòu)圖Fig.2 SM architecture overview

GPU并行編程的核心在于線程的調(diào)度，它依靠成千上萬(wàn)個(gè)線程的并行執(zhí)行來(lái)達(dá)到加速的目的[4]。線程束(thread warp)是線程并行執(zhí)行的基本單元，通過(guò)線程束調(diào)度器調(diào)度不同的線程束到內(nèi)核中執(zhí)行。

GPU的存儲(chǔ)器是一種多層異構(gòu)的存儲(chǔ)體系，如圖3所示。它提供了不同層次的若干區(qū)域供程序員存放數(shù)據(jù)。其中，寄存器和本地存儲(chǔ)器都是每個(gè)線程所獨(dú)有的存儲(chǔ)單元。共享內(nèi)存的訪問(wèn)速度與寄存器相當(dāng)，供線程束內(nèi)的線程共享數(shù)據(jù)使用。全局內(nèi)存位于GPU片外，CPU和GPU均可對(duì)其進(jìn)行訪問(wèn)，可作為它們之間數(shù)據(jù)交換的介質(zhì)。常量?jī)?nèi)存位于GPU片外，可對(duì)其進(jìn)行緩存加速，訪問(wèn)速度較快。紋理內(nèi)存是位于GPU片外的只讀存儲(chǔ)，它提供了地址映射和數(shù)據(jù)濾波等功能。GPU存儲(chǔ)結(jié)構(gòu)多層次的特點(diǎn)，對(duì)于不同的數(shù)據(jù)存儲(chǔ)需求來(lái)說(shuō)有著較強(qiáng)的適應(yīng)能力和靈活性，妥善地處理計(jì)算數(shù)據(jù)的存儲(chǔ)與訪問(wèn)對(duì)于GPU整體性能的發(fā)揮來(lái)說(shuō)非常重要。

圖3 GPU的存儲(chǔ)體系結(jié)構(gòu)Fig.3 Storage architecture of GPU

2 PBAS算法的實(shí)時(shí)優(yōu)化方法

2.1 全局內(nèi)存訪問(wèn)合并優(yōu)化

在GPU中，大量線程的并行涉及到頻繁的內(nèi)存讀寫，因此會(huì)造成內(nèi)存訪問(wèn)擁塞[10-11]。另外，GPU訪問(wèn)一次全局內(nèi)存的代價(jià)是相當(dāng)大的，讀寫延遲一般在400 ms～600 ms。為了提高全局內(nèi)存訪問(wèn)的效率，CUDA提供了對(duì)全局內(nèi)存的合并訪問(wèn)機(jī)制[12]。如圖4所示，當(dāng)線程訪問(wèn)連續(xù)對(duì)齊(以32位、64位或128位地址對(duì)齊)內(nèi)存塊時(shí)，GPU會(huì)對(duì)這些連續(xù)的內(nèi)存訪問(wèn)進(jìn)行合并，一次讀取所有線程所需的數(shù)據(jù)。

圖4 全局內(nèi)存訪問(wèn)合并原理圖Fig.4 Principle of memory coalescing

圖5 PBAS算法的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)Fig.5 Data storage architecture of PBAS algorithm

圖6給出了本文實(shí)驗(yàn)數(shù)據(jù)集[11]Sequence 1的第173幀圖像相關(guān)參數(shù)在全局內(nèi)存中排列的結(jié)果。

圖6 Sequence 1第173幀相關(guān)參數(shù)在內(nèi)存中的排列結(jié)果Fig.6 Data storage architecture of 173th frame in Sequence 1

2.2 共享內(nèi)存優(yōu)化

由于PBAS算法對(duì)每個(gè)像素點(diǎn)獨(dú)立處理，與鄰近像素?zé)o關(guān)。同時(shí)，第i幀某個(gè)像素點(diǎn)的計(jì)算結(jié)果會(huì)用于第i+1幀同一位置像素點(diǎn)的計(jì)算。因此，把視頻序列以M幀為一組，每幀劃分為K×K個(gè)大小的圖像塊，如圖7(a)所示，處理時(shí)序如圖7(b)所示。

圖7 共享內(nèi)存優(yōu)化Fig.7 Shared Memory Optimization

對(duì)于M幀視頻序列，首先從全局內(nèi)存讀取第1幀的第1個(gè)圖像塊的參數(shù)存入共享內(nèi)存，計(jì)算完成后，將共享內(nèi)存中的參數(shù)更新，用于下一幀第1個(gè)圖像塊的計(jì)算，按照此順序依次計(jì)算M幀圖像的第1個(gè)圖像塊，當(dāng)?shù)贛幀第1個(gè)圖像塊計(jì)算完畢后，將參數(shù)存入全局內(nèi)存。然后按照順序在下一時(shí)刻依次讀取M幀視頻序列的第2個(gè)～第N個(gè)圖像塊進(jìn)行計(jì)算。PBAS算法每個(gè)像素點(diǎn)的三個(gè)參數(shù)所占存儲(chǔ)空間為36字節(jié)(三通道圖像，每個(gè)參數(shù)為單精度浮點(diǎn)數(shù))，因此，每個(gè)SM最多可以存儲(chǔ)約1.7 K個(gè)像素點(diǎn)的參數(shù)。為了計(jì)算方便，我們?nèi)=32。如圖8所示，我們對(duì)不同的M值進(jìn)行了實(shí)驗(yàn)，當(dāng)M=8時(shí)加速比最大。

圖8 不同M取值時(shí)性能比較Fig.8 Performance comparison with different M

圖9給出了本文實(shí)驗(yàn)數(shù)據(jù)集[15]Sequence 1的某組視頻序列中的一個(gè)圖像塊的參數(shù)在共享內(nèi)存中存儲(chǔ)數(shù)值的變化。

圖9 不同時(shí)刻共享內(nèi)存中某個(gè)Block存儲(chǔ)數(shù)據(jù)的變化Fig.9 Data stored in shared memory of one block in different time

2.3 隨機(jī)數(shù)產(chǎn)生機(jī)制優(yōu)化

在PBAS算法的計(jì)算過(guò)程中，涉及到大量隨機(jī)數(shù)的使用，每個(gè)像素點(diǎn)的計(jì)算使用以下5個(gè)隨機(jī)數(shù)：1) 背景模型更新概率randT;2) 背景模型像素點(diǎn)選取概率randN;3) 鄰域像素更新概率randTN;4) 鄰域像素點(diǎn)X坐標(biāo)選取概率randX;5) 鄰域像素點(diǎn)Y坐標(biāo)選取概率randY。如果嚴(yán)格按照PBAS算法原理對(duì)每個(gè)像素點(diǎn)都使用上述不同的隨機(jī)數(shù)進(jìn)行計(jì)算，必然涉及到大量的隨機(jī)內(nèi)存訪問(wèn)，從而降低了線程并行執(zhí)行的效率。為了充分利用GPU的并行架構(gòu)[16-17]，我們展開(kāi)了如下兩種隨機(jī)數(shù)產(chǎn)生機(jī)制的實(shí)驗(yàn)：

1) 嚴(yán)格遵照算法，GPU對(duì)每幀圖像的每個(gè)像素點(diǎn)單獨(dú)產(chǎn)生一組(5個(gè))隨機(jī)數(shù)。

2) 每幀圖像的所有像素點(diǎn)使用同一組(5個(gè))隨機(jī)數(shù)，CPU提前產(chǎn)生M幀圖像的隨機(jī)數(shù)存入GPU的常量?jī)?nèi)存中。當(dāng)前M幀處理完畢，CPU重新產(chǎn)生M個(gè)隨機(jī)數(shù)進(jìn)行替換。

如表1所示，在我們自建的中波紅外數(shù)據(jù)集上的實(shí)驗(yàn)表明，第二種方法采用的隨機(jī)數(shù)產(chǎn)生機(jī)制，相比于第一種方法F-Mean指標(biāo)僅降低了2.083%。同時(shí)，實(shí)驗(yàn)結(jié)果表明第二種方法的執(zhí)行效率相比于第一種方法提升明顯。詳細(xì)的實(shí)驗(yàn)及結(jié)果分析見(jiàn)第3節(jié)。

表1 兩種隨機(jī)數(shù)產(chǎn)生機(jī)制性能比較Table 1 Comparison of two pseudo code generation methods

本文采用了CUDA提供的用于隨機(jī)數(shù)產(chǎn)生的函數(shù)curand_uniform()[18]和curandGenerateuniform()[18]，分別在GPU端和CPU端產(chǎn)生隨機(jī)數(shù)。

3 實(shí)驗(yàn)結(jié)果與分析

本文所使用的實(shí)驗(yàn)平臺(tái)為NVIDIA公司的嵌入式GPU平臺(tái)Jetson TX2，其硬件配置如表2所示。整個(gè)實(shí)現(xiàn)基于CUDA 8.0。實(shí)驗(yàn)數(shù)據(jù)集為自建中波紅外圖像數(shù)據(jù)集[15]，包含了12個(gè)視頻序列共1 263幀圖像，涵蓋了動(dòng)態(tài)背景、鬼影、相機(jī)抖動(dòng)、陰影、噪聲、高速和低速運(yùn)動(dòng)目標(biāo)等常見(jiàn)場(chǎng)景，分辨率為480×320像素。有關(guān)該數(shù)據(jù)集的詳細(xì)信息請(qǐng)參考[11]。

表2 實(shí)驗(yàn)平臺(tái)硬件配置Table 2 Hardware configuration

表3列出了在CPU和GPU上執(zhí)行PBAS算法的實(shí)驗(yàn)結(jié)果，從中可以得到如下結(jié)論：1) 在GPU執(zhí)行PBAS算法相比CPU有著明顯的加速效果。在處理480×320像素圖像時(shí)，加速比最高可達(dá)70.653倍，平均可達(dá)66.533倍，每秒可處理132幀圖像。這說(shuō)明設(shè)計(jì)的PBAS算法的并行結(jié)構(gòu)極大提升了算法執(zhí)行的效率。2) 采用2.3節(jié)第二種隨機(jī)數(shù)產(chǎn)生機(jī)制比第一種得到了明顯的加速效果，加速比提高了11.275%。這說(shuō)明規(guī)則的數(shù)據(jù)訪問(wèn)比隨機(jī)的數(shù)據(jù)訪問(wèn)能更好地發(fā)揮GPU的并行計(jì)算性能。

圖10給出了使用本文提出的PBAS并行優(yōu)化算法在中波紅外數(shù)據(jù)集上進(jìn)行運(yùn)動(dòng)目標(biāo)分割的結(jié)果，每組圖像由輸入圖像、運(yùn)動(dòng)目標(biāo)分割結(jié)果和相應(yīng)的背景圖像組成。由圖可知，該算法能較好分割出運(yùn)動(dòng)目標(biāo)，特別是遠(yuǎn)距離小目標(biāo)。同時(shí)，PBAS算法能夠很好地對(duì)背景圖像進(jìn)行建模。

表3 CPU和GPU耗時(shí)比較 msTable 3 Comparison of processing time between CPU and GPU

圖10 中波紅外數(shù)據(jù)集運(yùn)動(dòng)目標(biāo)分割結(jié)果Fig.10 Results of moving objects segmentation on medium-wave infrared video sequences

圖11是中波紅外數(shù)據(jù)集Sequnece 1的一組視頻序列圖像(第57幀～第64幀)及其分割結(jié)果。圖12是Sequnece 1第57幀～第64幀的第81個(gè)32×32大小的圖像塊的分割結(jié)果。由圖可知，并行優(yōu)化實(shí)現(xiàn)的PBAS算法能夠正確分割出運(yùn)動(dòng)目標(biāo)，由于背景下方存在動(dòng)態(tài)變化，分割結(jié)果有一些噪聲，這是由于PBAS算法本身的特點(diǎn)造成的。

圖11 Sequence 1第57幀～第64幀的輸入圖像和分割結(jié)果Fig.11 Frames 57～64 of input image and segmentation results in Sequence 1

圖12 Sequence 1第57幀～第64幀的第81個(gè)圖像塊Fig.12 The 81th block of each frame in frames 57～64 in Sequence 1

4 結(jié)論

本文通過(guò)對(duì)PBAS算法的分析，結(jié)合GPU的架構(gòu)特點(diǎn)，在數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、共享內(nèi)存使用、隨機(jī)數(shù)產(chǎn)生機(jī)制三個(gè)方面對(duì)其進(jìn)行了并行優(yōu)化。在嵌入式GPU平臺(tái)Jetson TX2上的實(shí)驗(yàn)表明，對(duì)于480×320分辨率的中波紅外視頻序列，該優(yōu)化方法可以達(dá)到132 fps的處理速度，是CPU處理速度的66.533倍。算法實(shí)現(xiàn)采用的技術(shù)具有通用性，可以供其它光電監(jiān)視系統(tǒng)中運(yùn)動(dòng)目標(biāo)分割算法并行優(yōu)化借鑒使用。