基于模糊C均值聚類的大尺寸圖像目標(biāo)檢測加速方法*

陳玉虎,張臨杰**,郎海濤

(1.中國海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山東 青島 266100; 2.北京化工大學(xué)應(yīng)用物理系，北京 100029)

基于模糊C均值聚類的大尺寸圖像目標(biāo)檢測加速方法*

陳玉虎1,張臨杰1**,郎海濤2

(1.中國海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山東 青島 266100; 2.北京化工大學(xué)應(yīng)用物理系，北京 100029)

利用模糊C均值(FCM)聚類算法對大尺寸圖像進(jìn)行目標(biāo)檢測時(shí)，由于樣本數(shù)量巨大，算法運(yùn)行時(shí)間過長，不利于信息的及時(shí)處理。為提高大尺寸圖像檢測效率，給出了一個(gè)CPU+GPU平臺下的詳細(xì)加速方案。該方案利用CUDA并行技術(shù)，將FCM聚類等操作放在GPU端處理。同時(shí)，對只能在CPU端執(zhí)行的操作，利用OpenMP技術(shù)并行。對四幅大尺寸(15884×3171)全極化SAR圖像進(jìn)行檢測，平均加速約84.02倍。此外還利用MPI并行技術(shù)在雙節(jié)點(diǎn)上實(shí)現(xiàn)了對四幅全極化圖像的同時(shí)檢測。

FCM；CUDA；OpenMP；大尺寸圖像；目標(biāo)檢測

模糊C均值聚類(FCM)[1]是一種無監(jiān)督的聚類算法，其聚類過程不需要任何人工干預(yù)，在處理具有不確定性和模糊性的圖像上占有一定的優(yōu)勢，在圖像分割和目標(biāo)檢測已受到廣泛的重視[2-4]。但是隨著圖像尺寸的增大，樣本集(即圖像中所有像素值的集合)也急劇增大，導(dǎo)致聚類速度變慢，從而影響圖像檢測速度，不利于圖像信息的及時(shí)處理。利用并行技術(shù)，縮短FCM聚類時(shí)間是一種有效解決方法。

GPU卡的出現(xiàn)使得計(jì)算機(jī)的并行計(jì)算能力得到進(jìn)一步提升，已有研究者利用CUDA技術(shù)在GPU卡上實(shí)現(xiàn)FCM聚類算法的加速，日益受到研究者的研究興趣。例如ZDZISAWA R等[5]采用CUDA并行技術(shù)對FCM算法并行，在配備GeForce GTX560 GPU卡的單機(jī)上對像素?cái)?shù)約為280 000的圖像進(jìn)行分割，加速約10倍左右。左麗云等[6]利用CUDA并行技術(shù)在配備GeForce GTX660 GPU卡的單機(jī)上，對海量(5 000～20 000幅)圖像進(jìn)行處理，總圖像分割提速約10倍。

然而以上研究一方面所處理的圖像尺寸較小，未能充分體現(xiàn)GPU加速效率；另一方面沒有給出GPU端實(shí)現(xiàn)的詳細(xì)，例如線程網(wǎng)格和線程塊尺寸如何設(shè)置，歸約求和如何實(shí)現(xiàn)等，而這些實(shí)現(xiàn)的詳細(xì)將大大影響加速效果；此外未提及FCM聚類以外的其他操作的加速細(xì)節(jié)。

針對以上問題，本文詳細(xì)給出一個(gè)CPU+GPU平臺下基于FCM目標(biāo)檢測算法的加速方案。該方案將FCM聚類及其它可在GPU端執(zhí)行的操作利用CUDA技術(shù)進(jìn)行并行處理，充分發(fā)揮GPU計(jì)算優(yōu)勢。同時(shí)，為提高CPU的執(zhí)行效率，對無法在GPU端執(zhí)行的操作利用OpenMP技術(shù)在CPU端進(jìn)行并行處理。

本文構(gòu)成如下：首先是基于FCM的目標(biāo)檢測的介紹；隨后詳細(xì)給出CPU+GPU平臺下的加速方案；最后以四幅大尺寸(15 884×3 171)SAR極化圖像為例，在配備CPU+GPU硬件的單節(jié)點(diǎn)，和雙節(jié)點(diǎn)上分別進(jìn)行實(shí)驗(yàn)，驗(yàn)證本方案的加速效果。

1 基于FCM的目標(biāo)檢測

?i,kuik∈[0,1] ，

(1)

(2)

(3)

聚類中心pi∈RsP=(i=1，…，C)，P=(p1,…,pC)。目標(biāo)函數(shù)

(4)

用來衡量聚類劃分的好壞，值越小表示劃分越好。其中m為權(quán)重(一般取2)，

dik=‖xk-pi‖

(5)

為樣本xk到聚類i的中心pi的距離，一般使用歐幾里得距離，D=[dik]c×n為其距離矩陣。

聚類準(zhǔn)則是選取合適的聚類中心pi,(i=1,…,C)和隸屬矩陣U=[uik]C×n，使得目標(biāo)函數(shù)Jm(U,P)達(dá)到最小值。根據(jù)拉格朗日乘數(shù)法，Jm(U,P)達(dá)到最小時(shí)uik的解為

(6)

同理，根據(jù)拉格朗日乘數(shù)法，Jm(U,P)達(dá)到最小pi的解為

(7)

由此可知，對于給定樣本集X，只需指定聚類劃分?jǐn)?shù)C，權(quán)重m，迭代終止閾值ε，以及初始聚類中心P(0)，就能通過式(5)和式(6)計(jì)算出隸屬矩陣U(1),然后再使用U(1)和式(7)計(jì)算出新的聚類中心P(1)，并使用P(1)和式(5)、(6)計(jì)算出新的隸屬矩陣U(2)，以此類推，直至滿足迭代終止條件。也可以先給出初始隸屬矩陣U(0)，計(jì)算方法類似。

FCM算法在實(shí)現(xiàn)上有多種方式，其中較為常用的實(shí)現(xiàn)如下所示。

步驟1：b=b+1，若b>N則結(jié)束；

步驟2：利用式(5)計(jì)算距離矩陣D(b)；

步驟3：利用式(6)計(jì)算隸屬矩陣U(b)；

步驟4：利用式(7)計(jì)算新的聚類中心P(b)；

則結(jié)束，否則返回步驟1。

2 CPU+GPU平臺下的加速方案

為縮短圖像檢測時(shí)間，我們給出一個(gè)CPU+GPU平臺下的加速方案。多核CPU適用于邏輯運(yùn)算較復(fù)雜的處理，而GPU則適用于邏輯分支簡單、計(jì)算密集的處理。本文將逐一分析基于FCM的目標(biāo)檢測各環(huán)節(jié)，對適合在GPU端執(zhí)行的部分，采用CUDA技術(shù)進(jìn)行加速；對于無法在GPU端執(zhí)行的部分，為充分利用CPU多核資源，采用OpenMP技術(shù)對其進(jìn)行加速。為方便對該加速方案的詳細(xì)說明，先對CUDA多線程結(jié)構(gòu)和GPU顯存做一個(gè)簡單介紹。

2.1CUDA多級線程結(jié)構(gòu)和GPU顯存簡介

CUDA(ComputeUnifiedDeviceArchitecture)是一種通用并行計(jì)算架構(gòu)，該架構(gòu)使GPU能夠解決計(jì)算密集、邏輯分支簡單的大規(guī)模數(shù)據(jù)并行任務(wù)。在CUDA中，運(yùn)行在GPU上的CUDA并行計(jì)算函數(shù)稱為內(nèi)核函數(shù)(kernel)，內(nèi)核函數(shù)以線程網(wǎng)格(grid)的形式組織，每個(gè)線程網(wǎng)格由若干個(gè)線程塊(block)組成，而每個(gè)線程塊又由若干個(gè)線程(thread)組成，一般一個(gè)內(nèi)核函數(shù)只有一個(gè)線程網(wǎng)格[7]。圖1展示了線程網(wǎng)格、線程塊和線程之間的關(guān)系。圖中線程網(wǎng)格尺寸dimGrid為2維，dimGrid.x=2、dimGrid.y=2，線程塊尺寸dimBlock也是2維，dimBlock.x=2，dimBlock.y=2。線程網(wǎng)格和線程塊尺寸也可以是1維或3維。

在調(diào)用GPU核函數(shù)時(shí)，需指定線程網(wǎng)格和線程塊尺寸。依據(jù)任務(wù)特性及GPU本身硬件特性，合理設(shè)置線程網(wǎng)格和線程塊尺寸，有助于提高GPU端的線程執(zhí)行效率。

首先，線程網(wǎng)格和線程塊的維度應(yīng)與實(shí)際數(shù)據(jù)的維度保持一致，這樣便于編程時(shí)線程和數(shù)據(jù)的映射。因此在實(shí)際編程時(shí)，只需確定線程網(wǎng)格內(nèi)線程塊的數(shù)目和一個(gè)線程塊內(nèi)線程的數(shù)目即可。

其次，GPU上線程的執(zhí)行是以線程束(warp)為最小單元。一個(gè)線程塊內(nèi)包含的線程數(shù)最好是線程束的整數(shù)倍(Tesla架構(gòu)的GPU中線程束大小為32)。

圖1 CUDA線程層次結(jié)構(gòu)圖

按照CUDA線程執(zhí)行模型，各個(gè)線程塊會被分配到GPU的各個(gè)流多處理器SM(Streaming Multiprocessor)上執(zhí)行。一個(gè)線程塊只能在一個(gè)SM上執(zhí)行，但是一個(gè)SM可以執(zhí)行多個(gè)線程塊。如果一個(gè)SM上只并發(fā)執(zhí)行一個(gè)線程塊，那么當(dāng)這個(gè)線程塊中的線程訪問GPU顯存或者線程間進(jìn)行同步等待時(shí)，這個(gè)SM就會被閑置。因此活動線程塊的數(shù)目應(yīng)該至少大于SM數(shù)目的2倍。另外，線程塊尺寸應(yīng)該設(shè)置的大些，較大的線程塊有更多的線程可以進(jìn)行通信，可以獲得更多的指令流效率[8]。

除以上因素外，GPU存儲資源也是在設(shè)置線程格和線程塊尺寸時(shí)應(yīng)考慮的重要因素。GPU線程在執(zhí)行過程中可以訪問的存儲資源有寄存器、共享內(nèi)存(Shared memory)和全局內(nèi)存(Global memory)：

? 每個(gè)線程擁有獨(dú)立的寄存器；

? 每個(gè)線程塊都有其獨(dú)立的共享內(nèi)存，被線程塊中的所有線程共享；

? 全局內(nèi)存對所有CUDA線程都是可見的。

訪存速度由快到慢依次是：寄存器、共享內(nèi)存、全局內(nèi)存[9]。正是由于這三種存儲資源的訪存速度的差別，在實(shí)際應(yīng)用中，應(yīng)根據(jù)實(shí)際問題，調(diào)整線程塊尺寸，盡可能利用寄存器和共享內(nèi)存。

綜上所述，本文對線程網(wǎng)格尺寸和線程塊尺寸的設(shè)置建議如下：

建議一：維度與實(shí)際問題維度保持一致即可，僅需關(guān)心線程塊數(shù)(numBlock)，和一個(gè)線程塊內(nèi)的線程數(shù)(numThread)即可；

建議二：numThread應(yīng)滿足以下不等式

其中1個(gè)SM上最大活動線程塊數(shù)由硬件決定，1個(gè)SM上實(shí)際最大活動線程數(shù)為以下三者中的最小值：

c. 硬件所決定最大活動線程數(shù)上限。

建議三：numThread為一個(gè)線程束內(nèi)包含的線程數(shù)的倍數(shù)，且在滿足建議二的條件下設(shè)置的盡量大些；

建議四：numBlock≥SM數(shù)×2。

2.2 加速方案

計(jì)算距離矩陣D(b)：dik計(jì)算相互獨(dú)立，數(shù)量眾多，計(jì)算邏輯簡單，適合在GPU端執(zhí)行，可令GPU上每個(gè)線程計(jì)算C個(gè)dik(i=1，…，C)值。GPU顯存的使用方面，可以將聚類中心值pi從全局內(nèi)存拷貝至共享內(nèi)存，減少內(nèi)存存取的使用帶寬。樣本xk直接從全局內(nèi)存存取即可。

計(jì)算隸屬矩陣U(b)：與計(jì)算距離矩陣D(b)類似，Uik計(jì)算相互獨(dú)立，數(shù)量眾多，計(jì)算邏輯簡單，適合在GPU端執(zhí)行，可令GPU上每個(gè)線程計(jì)算C個(gè)uik(i=1,…,C)值。距離dik((i=1,…,C)直接從全局內(nèi)存存取即可。

StepⅡ：在各個(gè)線程塊內(nèi)利用柵欄同步和樹狀加法實(shí)現(xiàn)線程塊內(nèi)歸約，并將各線程塊內(nèi)的歸約求和結(jié)果拷貝至全局內(nèi)存的一維數(shù)組；

StepⅢ：再將上一步的一維數(shù)組拷貝至共享內(nèi)存，并在一個(gè)線程塊內(nèi)對其進(jìn)行最后的歸約。

以16個(gè)樣本，2個(gè)線程塊,4個(gè)線程(m=2)為例說明上述歸約流程(參見圖2)。在StepⅠ中，先對16個(gè)樣本兩兩求平方和，然后將結(jié)果存入共享內(nèi)存，這樣在共享內(nèi)存中僅需存儲8個(gè)數(shù)據(jù)；在StepⅡ中，每個(gè)線程塊負(fù)責(zé)四個(gè)數(shù)據(jù)的歸約，歸約結(jié)果存儲在第一個(gè)數(shù)據(jù)的存儲單元,然后拷貝回全局內(nèi)存(僅剩2個(gè)數(shù)據(jù))；在StepⅢ中，將這2個(gè)數(shù)據(jù)拷貝至共享內(nèi)存，并在一個(gè)線程塊內(nèi)做最后的歸約，從而得到最終歸約結(jié)果。

圖2 歸約示意圖(:全局內(nèi)存，:共享內(nèi)存，SS:平方求和，RS:規(guī)約求和，C:拷貝)

需要說明的是，上述規(guī)約步驟共有三次全局內(nèi)存和共享內(nèi)存之間的數(shù)據(jù)拷貝。第一次是在StepⅠ中將若干個(gè)數(shù)據(jù)求平方和后，拷貝至各線程塊的共享內(nèi)存；第二次是在StepⅡ中將各線程塊內(nèi)的歸約結(jié)果拷貝回全局內(nèi)存；第三次是在StepⅢ中，將上一步拷貝回全局內(nèi)存的各線程塊的歸約結(jié)果，再拷貝到某一個(gè)線程塊的共享內(nèi)存中，以便由這個(gè)線程塊完成最后的歸約。三次內(nèi)存間數(shù)據(jù)拷貝的目的是為了充分利用共享內(nèi)存，以實(shí)現(xiàn)線程塊內(nèi)線程間的高效數(shù)據(jù)共享。以本文數(shù)據(jù)實(shí)驗(yàn)中的圖像為例(樣本數(shù)15884×3171)，按上述步驟在共享內(nèi)存上歸約的時(shí)間是在全局內(nèi)存上歸約的44.75%。

此外，除FCM聚類外，在基于FCM聚類算法的圖像檢測中，一般還包含以下操作：

① 讀取文件；

② 數(shù)據(jù)歸一化；

③ 根據(jù)聚類結(jié)果計(jì)算閾值；

④ 圖像檢測；

⑤ 輸出檢測結(jié)果。

在FCM算法未被加速時(shí)，以上操作所占時(shí)間通?？梢院雎圆挥?jì)。以本文數(shù)據(jù)實(shí)驗(yàn)中的HH極化圖像為例，以上操作僅占總檢測時(shí)間的1.60%。但是利用上述方案對FCM算法加速后，以上操作所占比例增大，因此也要對其做相應(yīng)的并行化。

操作①和⑤涉及磁盤讀寫，由于GPU無法直接訪問磁盤，因此只能放在CPU端執(zhí)行。操作①中，若圖像文件為img等非壓縮格式，則圖像文件信息可直接讀入內(nèi)存數(shù)組，其速度取決于磁盤IO性能，不適合并行；若圖像文件為jpg等壓縮格式，則將圖像文件讀入內(nèi)存后，還需通過循環(huán)操作，解壓像素值信息并存入數(shù)組。此處的循環(huán)可以使用OpenMP并行加速。操作⑤類似，不再累述。由于本文的輸入輸出圖像均為jpg格式，因此可利用OpenMP對其加速。具體方法為在相應(yīng)for循環(huán)前插入以下OpenMP制導(dǎo)語句：

#pragmaompparallelfor

除操作①和⑤以外，其他操作相互獨(dú)立，涉及數(shù)據(jù)多，計(jì)算邏輯簡單，均適合在GPU端并發(fā)執(zhí)行：操作②數(shù)據(jù)歸一化和操作④圖像檢測的具體實(shí)現(xiàn)與計(jì)算距離矩陣相同、操作③與計(jì)算聚類中心相同?？傮w檢測流程圖見圖3。

3 數(shù)據(jù)實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

為說明上述加速方案的有效性，我們使用航天704研究所在2010年7月16日大連溢油事故期間獲取的四幅機(jī)載極化SAR圖像(圖4)為例。該數(shù)據(jù)工作在C波段，分辨率為3m，幅寬為5km，成像時(shí)飛機(jī)的飛行高度為3 000m。利用FCM聚類算法進(jìn)行圖像目標(biāo)檢測，圖像尺寸均為15884×3171。實(shí)驗(yàn)所用計(jì)算節(jié)點(diǎn)配置如下：

?CPU：CPUE5-2630V3 ×2，共16核心； 64G

內(nèi)存

?GPU：KeplerK40M×2，顯存12GB，核心數(shù)2 880

? 操作系統(tǒng)：RedHatEnterprise6.5

? 編譯環(huán)境：CUDA6.5

本實(shí)驗(yàn)對待檢測圖像中各像素點(diǎn)灰度值進(jìn)行三聚類。檢測閾值采用在實(shí)際檢測效果最好的計(jì)算方法(max{C1}+min{C2})/2，其中C1、C2和C3為聚類結(jié)果按灰度值降序排序。

本實(shí)驗(yàn)中共有7個(gè)核函數(shù)，每個(gè)核函數(shù)在調(diào)用時(shí)均需指定線程網(wǎng)格和線程塊的尺寸。在一一給出各核函數(shù)的設(shè)置說明之前，先列出本文所給建議中涉及的各硬件參數(shù)：

? 每個(gè)SM上最大活動線程數(shù)為2048

? 每個(gè)SM上寄存器總量65536

? 每個(gè)SM上共享內(nèi)存48KB

圖3 CPU+GPU平臺下的加速方案

圖4 實(shí)驗(yàn)用SAR全極化圖像(15 884×3 171)

? 每個(gè)SM上最大活動線程塊數(shù)為16

? 線程束內(nèi)的線程數(shù)為32

?SM數(shù)為15

計(jì)算聚類中心P(b)的核函數(shù)：通過編譯查詢可知每個(gè)線程使用的寄存器數(shù)量為37個(gè)，每個(gè)線程平均使用的共享內(nèi)存大小為48B。核函數(shù)所處理數(shù)據(jù)為一維，所以根據(jù)建議一，線程網(wǎng)格和線程塊維度均為一維。根據(jù)建議二和三，numThread應(yīng)在64～512之內(nèi)，應(yīng)為32的整數(shù)倍，且盡可能大一些。此外根據(jù)歸約特性，numThread應(yīng)為2的整次冪。由此可知，256和512都符合要求，實(shí)驗(yàn)表明兩種取法的計(jì)算時(shí)間幾乎沒有差別。本實(shí)驗(yàn)取numThread=256。確定numThread后，由建議四，numBlock大于30即可。注意到歸約最后一步，即StepⅢ所處理的數(shù)據(jù)個(gè)數(shù)即為線程格尺寸numBlock，因此根據(jù)歸約特性，numBlock也應(yīng)為2的整次冪，本實(shí)驗(yàn)為編程方便取numBlock等于numThread，即256。

計(jì)算距離矩陣D(b)：由于不涉及歸約操作，因此設(shè)置較為簡單，只需令總線程數(shù)等于樣本個(gè)數(shù)，第k個(gè)線程負(fù)責(zé)dik的計(jì)算即可。由于線程間無需通信，因此根據(jù)建議取numThread=256之后，令numGrid等于樣本數(shù)除以256上取整。

計(jì)算隸屬矩陣U(b)的核函數(shù)：與計(jì)算距離矩陣D(b)的核函數(shù)類似，每個(gè)線程負(fù)責(zé)一個(gè)uik的計(jì)算，采用相同設(shè)置。

歸一化的核函數(shù)：與計(jì)算距離矩陣D(b)的核函數(shù)類似，每個(gè)線程負(fù)責(zé)一個(gè)樣本數(shù)據(jù)的歸一化，采用相同設(shè)置。

計(jì)算檢測閾值的核函數(shù)：由于在計(jì)算檢測閾值時(shí)，需要用歸約操作統(tǒng)計(jì)聚類結(jié)果中的最大值和最小值，因此與計(jì)算聚類中心P(b)的核函數(shù)類似，采用相同設(shè)置。

根據(jù)閾值進(jìn)行圖像檢測的核函數(shù)：與計(jì)算距離矩陣D(b)的核函數(shù)類似，每個(gè)線程負(fù)責(zé)一個(gè)像素的檢測，采用相同設(shè)置。

3.2 加速前串行程序熱點(diǎn)分析

首先對加速前的串行程序進(jìn)行熱點(diǎn)分析。圖像檢測各步驟計(jì)算時(shí)間和所占比例見表1。由表1可以看出，平均98.89%的圖像檢測時(shí)間用于FCM聚類。

3.3 CPU+GPU平臺上加速

下面我們依據(jù)本文所給加速方案對圖像檢測進(jìn)行加速，檢測時(shí)間見表2，F(xiàn)CM檢測時(shí)間加速比見表3。對比表1和表2可以看出，加速后各環(huán)節(jié)執(zhí)行時(shí)間均有明顯減少，但“其他”(見表中倒數(shù)第2行)除外。這是因?yàn)榧铀俸蟀l(fā)生了申請和釋放GPU資源的額外開銷。對于四幅圖像，平均檢測時(shí)間由287.44 s縮短為3.37 s。與串行相比平均加速84.02。

表1 加速前串行程序各環(huán)節(jié)計(jì)算時(shí)間詳細(xì)

表2 加速后計(jì)算時(shí)間詳細(xì)

表3 CPU+GPU平臺上的加速比

注意到本實(shí)驗(yàn)所用的4幅圖像是同一場景的全極化圖像。在各極化圖像中，艦船目標(biāo)在4種極化圖像中均以較高的灰度值出現(xiàn)，而一些虛影在各極化圖像中的表現(xiàn)并不一致。因此在實(shí)際執(zhí)行艦船檢測任務(wù)時(shí)，經(jīng)常使用“與”操作融合各極化SAR圖像的檢測結(jié)果。

如果對4個(gè)極化圖像依次檢測，則總的檢測時(shí)間即為表2中各圖像檢測時(shí)間的和，再加上“與”操作融合時(shí)間，約為14.20 s?？紤]到這四個(gè)圖像的檢測完全獨(dú)立，因此在硬件條件允許的情況下，可以通過MPI并行執(zhí)行。

本實(shí)驗(yàn)有2個(gè)相同配置的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)配備2塊GPU卡，因此令進(jìn)程數(shù)等于4，每個(gè)節(jié)點(diǎn)分配2個(gè)進(jìn)程，每個(gè)進(jìn)程使用1塊GPU卡負(fù)責(zé)一幅實(shí)驗(yàn)圖像的檢測。待四幅圖像全部檢測完成后，對檢測結(jié)果進(jìn)行“與”操作?？倷z測時(shí)間4.63 s，詳見表4。最終融合后的檢測結(jié)果見圖5，與加速前完全一致。

表4 MPI并行時(shí)的檢測時(shí)間

4 結(jié)語

為提高基于FCM聚類算法的大尺寸圖像檢測效率，本文給出了一個(gè)CPU+GPU平臺下的加速方案。使用該加速方案對4幅大尺寸(15884×3171)全極化SAR圖像檢測，單節(jié)點(diǎn)CPU+GPU平臺下進(jìn)行檢測時(shí)，平均檢測時(shí)間由287.44 s縮短為3.37 s。利用MPI并行技術(shù)在雙節(jié)點(diǎn)CPU+GPU平臺下對這四幅極化圖像同時(shí)處理，并對各圖像的檢測結(jié)果進(jìn)行融合，總用時(shí)4.63 s。本文為基于FCM聚類的大尺寸圖像檢測提供了一個(gè)有效的快速解決方案。

圖5 最終艦船目標(biāo)檢測結(jié)果

[1] Bezdel J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York:Plenum Press:174-191,1981.

[2] 孫季豐,鄧曉暉.基于NSCT和FCM聚類的SAR圖像分割[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,39(2)：60-70.Sun Jifeng,Deng Xiaohui.Segmentation of SAR images based on NSCT and FCM clustering[J].Journal of South China University of Technology(Natural Science Edition),2011,39(2):60-70.

[3] 邵楨,翟宏宇,劉雪巖.基于SFCM及水平集方法的溢油圖像分割[J].長春理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,36(3-4):134-137.Shao Zhen,Zhai Hongyu,Liu Xueyan.Segmentation of oil spill images based on SFCM and level set methods[J].Journal of Changchun University of Science and Technology,2013,36(3-4):134-137.

[4] 趙暉，孫進(jìn)平,王文光,毛士藝.基于模糊聚類的SAR圖像道路檢測[J].遙測遙控,2009,30(2):34-39.Zhao Hui,Sun Jinping,Wang Wenguang,Mao Shiyi.Road detection in SAR images based on fuzzy clustering[J].Journal of Telemetry,Tracking,and Command,2009,30(2):34-39.

[5] ZDZISAWA R,JAROSAW G.CUDA based fuzzy C-means acceleration for the segmentation of images with fungus grown in foam matrices [J].Image Processing & Communication,2013,17(4):191-200.

[6] 左利云,羅成煜,左右祥.基于EnFCM的海量圖像聚類分割算法的并行研究[J].微型機(jī)與應(yīng)用,2015,34(15):55-58.Zuo Liyun,Luo Chengyu,Zuo Youxiang.Paralleled segmentation cluster algorithm based on ENFCM for large-scale image[J].Microcomputer & ITS Applications,2015,34(15):55-58.

[7] John Cheng,Max Grossman,Ty McKercher.Professional CUDA C Programming[M].John Wiley & Sons,23-34,2014.

[8] 張舒,褚艷麗.GPU高性能運(yùn)算之CUDA[M].北京：中國水利水電出版社:150-152,2009.Zhang Shu,Chu Yanli.CUDA High Performance Computing GPU[M].Beijing:China Water & Power Press,150-152,2009.

[9] 趙開勇,汪朝輝,程亦超.大規(guī)模并行處理器編程實(shí)戰(zhàn)[M].清華大學(xué)出版社,83-89,2013.Zhao Kaiyong,Wang Chaohui,Cheng Yichao.Programming Massively Parallel Processors:A Hands-on Approach[M].Tsinghua University Press,83-89,2013.

責(zé)任編輯 陳呈超

Acceleration of Fuzzy C-Means Clustering Based Target Detection for Large Size Image

CHEN Yu-Hu1,ZHANG Lin-Jie1,LANG Hai-Tao2

(1.College of Mathematical Science,Ocean University of China,Qingdao 266100,China；2.Physics & Electronics Department,Beijing University of Chemical Technology,Beijing 100029,China)

Fuzzy c-mean clustering method (FCM) is an unsupervised clustering algorithm,and its clustering process does not require any manual intervention.It has a certain advantage in images with uncertainty and fuzziness,and has been paid more and more attention in the field of target detection.However,with the increase of the size of the image,the sample set also increases dramatically,which leads to long computing time.Using CPU+GPU platform to accelerate the FCM clustering algorithm is an effective method to shorten the clustering time.A detailed acceleration scheme on CPU+GPU platform is given,in which the FCM clustering and other operations are arranged on GPU side,and the others are arranged on CPU side.CUDA and openMP parallel technologies are used to improve computation efficiency.In numerical experiments,we make use of 4 large full polar SAR images (15884×3171),the average detection time is shortened from 287.44 seconds to 3.37 seconds,and the average speedup is 84.02 on a single CPU+GPU node.And we also use MPI technology to detect these images in parallel on two CPU+GPU nodes.Experimental results show that under the CPU+GPU platform,our acceleration scheme can speed up the target detection time greatly.It provides an effective solution for FCM based target detection for large size images.

FCM； CUDA； OpenMP； large size images； target detection

山東省自然科學(xué)基金項(xiàng)目(ZR2013FQ026)；海洋公益性行業(yè)科研專項(xiàng)經(jīng)費(fèi)項(xiàng)目(201505002)；國家自然科學(xué)基金項(xiàng)目(11371333)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)(201362033,201564019)資助

Supported by “Shandong Provincial Natural Science Foundation,China”(ZR2013FQ026)；“Public Science and Technology Research Funds Projects of Ocean”(201505002)；“National Natural Science Foundation of China”(11371333)；“the Fundamental Research Funds for the Central Universities”(201362033,201564019)

2016-09-15;

2016-12-10

陳玉虎(1990-),男,碩士,現(xiàn)從事計(jì)算數(shù)學(xué)方向的研究。 E-mail:xiaohumengdie@163.com

** 通訊作者：E-mail:zhanglinjie@ouc.edu.cn

TP751

A

1672-5174(2017)02-094-07

10.16441/j.cnki.hdxb.20160324

陳玉虎,張臨杰,郎海濤.基于模糊C均值聚類的大尺寸圖像目標(biāo)檢測加速方法[J].中國海洋大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,47(2):94-100.

CHEN Yu-Hu,ZHANG Lin-Jie,LANG Hai-Tao.Acceleration of fuzzy C-means clustering based target detection for large size image[J].Periodical of Ocean University of China,2017,47(2):94-100.