趙海娜，吳遠(yuǎn)峰，高建威，張兵

(1.中國(guó)科學(xué)院 遙感與數(shù)字地球研究所 數(shù)字地球重點(diǎn)實(shí)驗(yàn)室，北京 100094；2.中國(guó)科學(xué)院大學(xué)，北京 100049)

1 引 言

當(dāng)今遙感技術(shù)正朝著更高空間分辨率、更高時(shí)間分辨率和更高光譜分辨率方向發(fā)展，這給海量遙感圖像分類帶來了新的挑戰(zhàn)，尤其在災(zāi)害監(jiān)測(cè)、戰(zhàn)場(chǎng)目標(biāo)探測(cè)以及智能衛(wèi)星系統(tǒng)等時(shí)效性要求較高的應(yīng)用領(lǐng)域的挑戰(zhàn)尤為突出[1-2]。

貝葉斯分類方法具有堅(jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)以及綜合先驗(yàn)信息和數(shù)據(jù)樣本信息的能力，是遙感圖像分類的實(shí)用方法[3-4]。但基于CPU的貝葉斯串行分類算法在處理較大圖像時(shí)非常耗時(shí)。

傳統(tǒng)遙感圖像分類加速處理多采用由CPU組成的分布式集群系統(tǒng)的處理模式[5-7]。但是集群系統(tǒng)價(jià)格昂貴、體積大、靈活性差，很難應(yīng)用到戰(zhàn)場(chǎng)或星上等要求低重、高靈活性等場(chǎng)景。

近幾年來，國(guó)內(nèi)外許多研究將GPU用在遙感影像融合、混合像元分解和實(shí)時(shí)目標(biāo)探測(cè)等領(lǐng)域，對(duì)算法進(jìn)行了加速處理，獲得高效的并行計(jì)算能力[8-10]。圖形處理器(Graphic Processing Unit，GPU)具有運(yùn)算密集、高度并行、體積小和性價(jià)比高等特點(diǎn)，為解決數(shù)據(jù)密集型的計(jì)算提供了有利條件[11]。本文針對(duì)貝葉斯分類算法面臨大數(shù)據(jù)量圖像處理速度問題，提出了基于GPU的貝葉斯并行分類算法，并從數(shù)據(jù)傳輸和核函數(shù)設(shè)計(jì)兩方面對(duì)并行算法進(jìn)行了優(yōu)化設(shè)計(jì)。實(shí)驗(yàn)結(jié)果表明，基于GPU的貝葉斯并行分類算法(以下簡(jiǎn)稱并行算法)與基于CPU的串行算法(以下簡(jiǎn)稱串行算法)相比，在保證分類精度的同時(shí)，分類效率明顯提高，能夠獲得25倍～54倍的加速比。

2 貝葉斯分類算法

2.1 算法流程

定義遙感圖像為X，band、sample和line分別代表波段數(shù)、列數(shù)和行數(shù)。x={a1,a2,…，am},(m=band)為其中的一個(gè)像元，ai為x的一個(gè)特征屬性；Y={y1,y2,…，yn}代表類別，n為類別數(shù)，D={d1,d2,…，dn}為訓(xùn)練樣本，其中di代表每一類的訓(xùn)練樣本的個(gè)數(shù)。貝葉斯分類方法[3-4]是一種基于統(tǒng)計(jì)模型的分類方法，并假設(shè)各對(duì)象之間是條件獨(dú)立的[12]，其原理是基于某地物的先驗(yàn)概率，利用貝葉斯公式計(jì)算出其后驗(yàn)概率，即該地物屬于某一類的概率，選擇具有最大后驗(yàn)概率的類作為該地物所屬的類。計(jì)算步驟如下：

①計(jì)算訓(xùn)練樣本中每個(gè)類別的先驗(yàn)概率

(1)

②計(jì)算訓(xùn)練樣本的均值μyi和標(biāo)準(zhǔn)差σyi；

③根據(jù)樣本均值、標(biāo)準(zhǔn)差計(jì)算每個(gè)類別條件下各個(gè)特征屬性條件概率

(2)

p(x|yi)p(yi)

=P(a1|yi)P(a2|yi)…P(am|yi)P(yi)

(3)

⑤用分類器進(jìn)行分類，選擇概率最大的類作為X的所屬類別，對(duì)每一像元進(jìn)行分類。

2.2 貝葉斯分類算法計(jì)算復(fù)雜度分析

2.1節(jié)中步驟①和步驟②計(jì)算了訓(xùn)練樣本各類別的先驗(yàn)概率以及均值和標(biāo)準(zhǔn)差，計(jì)算過程簡(jiǎn)單并且計(jì)算量很小，因此在整個(gè)算法中這兩步運(yùn)算的復(fù)雜度可以忽略不計(jì)。實(shí)驗(yàn)中將先驗(yàn)概率、訓(xùn)練樣本的均值標(biāo)準(zhǔn)差作為已知。

表1是步驟③～步驟⑤對(duì)于處理分類類別為n，圖像尺寸為line×sample×band的圖像的時(shí)間復(fù)雜度。從以上的分析可以看出，數(shù)據(jù)量對(duì)算法復(fù)雜度的影響非常大，數(shù)據(jù)量的增加會(huì)嚴(yán)重影響算法的計(jì)算效率。

表1 各處理過程計(jì)算時(shí)間復(fù)雜度

3 基于GPU的分類算法并行優(yōu)化

在CUDA架構(gòu)下，程序計(jì)算分為在CPU上執(zhí)行的host端和在GPU上執(zhí)行的device端。Host端負(fù)責(zé)算法流程的控制以及簡(jiǎn)單的計(jì)算；device端負(fù)責(zé)圖像的數(shù)據(jù)級(jí)并行計(jì)算[13]。根據(jù)上一節(jié)對(duì)貝葉斯算法復(fù)雜度的分析，基于CUDA對(duì)算法進(jìn)行并行設(shè)計(jì)時(shí)，將計(jì)算流程拆分成兩部分：①數(shù)據(jù)讀寫、GPU初始化、函數(shù)調(diào)用等流程控制邏輯由CPU執(zhí)行；②計(jì)算復(fù)雜度高的步驟③～步驟⑤由GPU執(zhí)行，算法流程如圖1所示。

圖1 基于CUDA的貝葉斯分類并行算法流程

圖1中，虛線框代表該部分計(jì)算在GPU上執(zhí)行，分配到GPU上并行計(jì)算的部分由處理流程中的Kernel函數(shù)(核函數(shù))完成，每個(gè)Kernel函數(shù)對(duì)應(yīng)CUDA計(jì)算模型上的一個(gè)GRID，GRID包含多個(gè)Block計(jì)算單元，Block由多個(gè)Thread線程具體執(zhí)行計(jì)算，將圖像像元映射到計(jì)算線程從而實(shí)現(xiàn)大規(guī)模的數(shù)據(jù)級(jí)并行計(jì)算。

在計(jì)算前，需要將圖像數(shù)據(jù)從主機(jī)內(nèi)存拷貝到GPU的設(shè)備內(nèi)存，計(jì)算完成后，再將分類后的數(shù)據(jù)從GPU的設(shè)備內(nèi)存拷貝回主機(jī)內(nèi)存。在這個(gè)過程中CPU與GPU的計(jì)算核心都處于空閑狀態(tài)。為了隱藏CPU和GPU間的數(shù)據(jù)傳輸時(shí)間，充分利用GPU的計(jì)算資源，本文通過CUDA創(chuàng)建流管理貝葉斯算法中的條件概率計(jì)算、后驗(yàn)概率計(jì)算以及分類器分類過程。流內(nèi)的操作是按順序執(zhí)行的，而流與流之間則是亂序執(zhí)行。實(shí)現(xiàn)一個(gè)流中數(shù)據(jù)傳輸與另一個(gè)流中核函數(shù)的執(zhí)行同時(shí)進(jìn)行，即GPU能夠持續(xù)地進(jìn)行計(jì)算，而不必等待數(shù)據(jù)。以3個(gè)流為例，每個(gè)流處理一塊圖像數(shù)據(jù)，異步優(yōu)化效果如圖2所示，不使用異步執(zhí)行時(shí)貝葉斯并行模型的計(jì)算時(shí)間為(執(zhí)行時(shí)間+傳輸時(shí)間)；而使用流和異步后，時(shí)間降為(執(zhí)行時(shí)間+傳輸時(shí)間/3)。

圖2 異步優(yōu)化示意圖

同時(shí)，由于Kernel的啟動(dòng)會(huì)占一定的時(shí)間開銷，為了提高并行算法的計(jì)算效率，本文盡可能將多個(gè)計(jì)算過程合并到一個(gè)Kernel函數(shù)中執(zhí)行。貝葉斯算法中的特征屬性條件概率計(jì)算、后驗(yàn)概率計(jì)算以及分類器分類都是針對(duì)整個(gè)遙感圖像進(jìn)行的，圖像像元與計(jì)算線程的映射相同，將以上三個(gè)過程合并到一個(gè)Kernel中進(jìn)行計(jì)算，從而可以避免不必要的時(shí)間開銷。

4 實(shí) 驗(yàn)

4.1 數(shù)據(jù)

所用的高光譜圖像是PHI航空成像光譜儀獲取的日本某地區(qū)的精細(xì)農(nóng)業(yè)數(shù)據(jù)，共80個(gè)波段，原始像幅為570×350。圖3為原始圖像假彩色合成影像以及地面樣本圖。經(jīng)主成分分析進(jìn)行特征提取，選取變換后包含信息量最大的6個(gè)波段作為實(shí)驗(yàn)數(shù)據(jù)。根據(jù)地面調(diào)查數(shù)據(jù)選取了中國(guó)白菜、日本白菜、蘿卜、生菜、牧場(chǎng)、薯、森林、無植被覆蓋區(qū)、地膜覆蓋區(qū)等9類地物作為分類的訓(xùn)練樣本。另外，為了分析不同數(shù)據(jù)量對(duì)算法加速比的影響，將原始圖像空間維重采樣，生成5幅不同空間分辨率的模擬影像，像幅分別為256×256，512×512，1024×1024，2048×2048，4096×4096。

圖3 PHI日本某地區(qū)的精細(xì)農(nóng)業(yè)數(shù)據(jù)

4.2 計(jì)算環(huán)境

本文的實(shí)驗(yàn)測(cè)試平臺(tái)參數(shù)為，中央處理器CPU是2.8GHz、12個(gè)計(jì)算核心的Intel(R) Xeon(R) X5660；圖形處理器是NVIDIA Quadro 5000 GPU，2.5GB全局存儲(chǔ)器，352個(gè)計(jì)算單元。操作系統(tǒng)是Windows 7 64位。

貝葉斯分類算法分別基于串行和并行計(jì)算環(huán)境實(shí)現(xiàn)，前者采用Microsoft Visual Studio 2008 C/C++編譯器實(shí)現(xiàn)，后者采用GPU的統(tǒng)一計(jì)算架構(gòu)CUDA4.0 C實(shí)現(xiàn)。

4.3 結(jié)果與分析

本文從分類精度和計(jì)算時(shí)間兩個(gè)方面對(duì)提出的并行算法的性能進(jìn)行分析，并與對(duì)應(yīng)的串行程序進(jìn)行比較。首先，對(duì)串行、并行優(yōu)化算法的分類精度進(jìn)行比較。從多組實(shí)驗(yàn)結(jié)果得出對(duì)于相同的實(shí)驗(yàn)數(shù)據(jù)串并行算法得到的分類精度是一致的，圖4給出了分類結(jié)果。

圖4 PHI數(shù)據(jù)分類結(jié)果

為了定量評(píng)價(jià)分類精度，本文根據(jù)地面調(diào)查數(shù)據(jù)分別在影像的不同位置選取了4個(gè)～6個(gè)均勻區(qū)域作為驗(yàn)證樣本，各類地物的驗(yàn)證樣本分別包含約200個(gè)～1000個(gè)像元。通過混淆矩陣計(jì)算了貝葉斯算法的分類精度，如表2所示。

表2 貝葉斯算法分類精度

接下來對(duì)兩種算法的分類效率進(jìn)行對(duì)比分析。實(shí)驗(yàn)時(shí)間統(tǒng)計(jì)結(jié)果如圖5、圖6所示。其中并行計(jì)算時(shí)間是指包括GPU分配顯存時(shí)間、數(shù)據(jù)拷貝時(shí)間以及核函數(shù)執(zhí)行時(shí)間在內(nèi)的總時(shí)間；由于采用了流異步執(zhí)行，核函數(shù)執(zhí)行時(shí)間包括了從設(shè)備端向主機(jī)端的數(shù)據(jù)拷貝時(shí)間。加速比是指串行算法與并行算法計(jì)算時(shí)間的比值。

由圖5可以看出，當(dāng)數(shù)據(jù)量比較小時(shí)，核函數(shù)執(zhí)行時(shí)間與并行計(jì)算時(shí)間基本相同，但隨著數(shù)據(jù)量的增大，并行計(jì)算時(shí)間與核函數(shù)執(zhí)行時(shí)間之間的差值不斷增大，原因是GPU顯存分配、主機(jī)端設(shè)備端數(shù)據(jù)拷貝時(shí)間隨著數(shù)據(jù)量的增大而不斷增加。

圖5 核函數(shù)執(zhí)行與并行計(jì)算時(shí)間在不同數(shù)據(jù)量下的比較

圖6為串并行計(jì)算時(shí)間以及加速比隨數(shù)據(jù)量變化圖。從圖6(a)中的串并行計(jì)算時(shí)間曲線可以看出，串并行計(jì)算時(shí)間隨數(shù)據(jù)量的增加均呈線性增長(zhǎng)。對(duì)于傳統(tǒng)CPU環(huán)境下，縱坐標(biāo)計(jì)算時(shí)間增量與橫坐標(biāo)數(shù)據(jù)量增量之比(秒每兆，s/M)超過1∶5，在這種情況下，如果數(shù)據(jù)量比較小，其分類的處理時(shí)間還能夠容忍，如果數(shù)據(jù)量增大，則計(jì)算時(shí)間隨之成倍增加；對(duì)于GPU環(huán)境下，縱坐標(biāo)計(jì)算時(shí)間的增量與橫坐標(biāo)數(shù)據(jù)量的增量之比小于1∶200，即由數(shù)據(jù)量急劇增加而引起的計(jì)算時(shí)間增長(zhǎng)十分緩慢。從圖6(b)中的加速比曲線來看，基于GPU并行計(jì)算的加速比隨數(shù)據(jù)量的增加呈增大趨勢(shì)，當(dāng)數(shù)據(jù)量達(dá)到一定量時(shí)，計(jì)算效率不再有較大的提升，加速比基本趨于穩(wěn)定，說明此時(shí)GPU線程達(dá)到滿載，即使增加數(shù)據(jù)量，加速比變化也不明顯；從多次實(shí)驗(yàn)結(jié)果可知，本文提出的并行算法能夠獲得25倍～54倍的加速比。

更進(jìn)一步，將本文提出的并行算法與ENVI軟件中的最大似然算法進(jìn)行對(duì)比。在處理4096×4096大小的圖像時(shí)，本文的并行算法計(jì)算時(shí)間是1.78s，而ENVI軟件中最大似然算法的計(jì)算時(shí)間大約是34.2s，本文的并行計(jì)算優(yōu)化方法比ENVI軟件同類功能的計(jì)算效率快19倍。

從以上實(shí)驗(yàn)結(jié)果分析可以得出結(jié)論如下：(1)本文提出的貝葉斯并行算法與串行算法的分類結(jié)果一致；(2)在保證分類結(jié)果正確的同時(shí)，并行算法的計(jì)算效率要遠(yuǎn)遠(yuǎn)高于串行算法，并能獲得25倍～54倍的計(jì)算加速比；(3)串行計(jì)算時(shí)間增量與數(shù)據(jù)量增量之比大于1∶5，并行計(jì)算時(shí)間增量與數(shù)據(jù)量增量之比小于1∶200，數(shù)據(jù)量增加時(shí)，串行計(jì)算時(shí)間增長(zhǎng)的更快；(4)加速比隨數(shù)據(jù)量的增大呈增大趨勢(shì)，當(dāng)數(shù)據(jù)量達(dá)到一定時(shí)，加速比趨于穩(wěn)定，此時(shí)GPU線程達(dá)到滿載。

圖6 串并行計(jì)算時(shí)間以及加速比隨數(shù)據(jù)量的變化

5 結(jié)束語

本文基于高光譜圖像貝葉斯分類算法的復(fù)雜度分析，給出了GPU并行優(yōu)化計(jì)算方法，并且采用PHI航空成像光譜儀獲取了日本某地區(qū)的精細(xì)農(nóng)業(yè)數(shù)據(jù)，在NVIDIA GPU上進(jìn)行了實(shí)驗(yàn)驗(yàn)證。結(jié)果表明，該并行分類算法在保證分類精度的同時(shí)能大大提高算法的計(jì)算效率，獲得25倍～54倍的計(jì)算加速比。研究表明，基于GPU實(shí)現(xiàn)遙感圖像并行分類算法是提高遙感圖像分類處理計(jì)算效率的有效途徑，可以為遙感大數(shù)據(jù)處理提供技術(shù)保障。同時(shí)，如何利用多GPU系統(tǒng)進(jìn)一步提高算法的計(jì)算效率也是下一步研究工作的重點(diǎn)。

參考文獻(xiàn)：

[1] ANTONIO P.Special issue on architectures and techniques for real-time processing of remotely sensed images[J].Journal of Real-Time Image Processing，2009，4(3)：191-193.

[2] 張兵.智能遙感衛(wèi)星系統(tǒng)[J].遙感學(xué)報(bào)，2011，15(3)：415-431.

[3] DOMINGOS P，PAZZANI M.On the optimality of the simple bayesian classifier under zero-one loss[J].Machine Learning，1997，29(2-3)：103-130.

[4] 彭興媛.樸素貝葉斯分類改進(jìn)算法的研究[D].重慶：重慶大學(xué)，2012.

[5] 劉曉云，康一梅，齊同軍，等.遙感圖像波譜角并行分類算法[J].計(jì)算機(jī)科學(xué)，2009，36(9)：267-270.

[6] LUO W，ZHANG B，JIA X.New improvements in parallel implementation of N-FINDR algorithm[J].Geoscience and Remote Sensing，IEEE Transactions on，2012，50(10)：3648-3659.

[7] PLAZA A J.Parallel techniques for information extraction from hyperspectral imagery using heterogeneous networks of workstations[J].Journal of Parallel and Distributed Computing，2008，68(1)：93-111.

[8] 盧俊，張保明，黃薇，等.基于 GPU 的遙感影像數(shù)據(jù)融合 IHS 變換算法[J].計(jì)算機(jī)工程，2009，35(7)：261-263.

[10] TARABALKA Y，HAAVARDSHOLM T V，KSEN I，et al.Real-time anomaly detection in hyperspectral images using multivariate normal mixture models and GPU processing[J].Journal of Real-Time Image Processing，2009，4(3)：287-300.

[11] 袁濤，馬艷，劉定生.GPU 在遙感圖像處理中的應(yīng)用綜述[J].遙感信息，2012，27(6)：110-117.

[12] KIM S，PARK S，WON D.Proxy signatures，revisited[J].Information and Communications Security，1997：223-232.

[13] NVIDIA.NVIDIA CUDA compute unified device architecture—programming guide[EB/OL].http：//developer.nvidia.com/cuda.