基于EnFCM的海量圖像聚類分割算法的并行研究*

左利云，羅成煜，左右祥（1.廣東石油化工學(xué)院 實(shí)驗(yàn)教學(xué)部，廣東 茂名 55000；.華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006；.汕頭大學(xué) 廣東省數(shù)字信號(hào)與圖像處理技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣東 汕頭51506）

基于EnFCM的海量圖像聚類分割算法的并行研究*

左利云1，2，羅成煜2，左右祥3
（1.廣東石油化工學(xué)院 實(shí)驗(yàn)教學(xué)部，廣東 茂名 525000；
2.華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006；
3.汕頭大學(xué) 廣東省數(shù)字信號(hào)與圖像處理技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣東 汕頭515063）

圖像分割的處理速度成為大規(guī)模圖像數(shù)據(jù)處理的瓶頸。本文提出一種基于EnFCM的圖像聚類分割模型，直接對(duì)圖像像素的灰度級(jí)進(jìn)行聚類，能顯著提高圖像聚類分割的處理速度。為進(jìn)一步提高處理速度，結(jié)合EnFCM圖像聚類分割模型特點(diǎn)，設(shè)計(jì)了三種并行優(yōu)化策略——純MPI并行方法、MPI+OpenMP混合編程方法和CUDA并行架構(gòu)方法，使其適合于大規(guī)模圖像處理。實(shí)驗(yàn)結(jié)果表明，提出的三種并行優(yōu)化策略都取得良好的加速效果。

圖像聚類分割；FCM算法；MPI+OpenMP；CUDA

0　引言

在圖像處理中圖像分割是不可或缺的關(guān)鍵步驟，圖像分析與模式識(shí)別都是以圖像分割為基礎(chǔ)的，因此圖像分割處理的速度將直接影響圖像處理和分析的速度。隨著圖像尺寸及處理規(guī)模的增大，樣本集的數(shù)據(jù)也急劇增加，導(dǎo)致聚類速度變慢，相應(yīng)地影響其圖像處理速度，成為大規(guī)模圖像處理的一個(gè)瓶頸問(wèn)題。

目前大量出現(xiàn)的集群和并行計(jì)算技術(shù)為這一問(wèn)題提供了有效的解決方案。利用強(qiáng)大的分布式并行處理能力，可將圖像處理的任務(wù)分解，將子任務(wù)分配到多個(gè)處理器同時(shí)執(zhí)行，能顯著提高大規(guī)模圖像處理速度。本文將并行技術(shù)應(yīng)用到圖像聚類分割中，以提高其處理速度。

1　相關(guān)工作

相關(guān)工作主要從基于FCM的圖像聚類分割和圖像分割并行實(shí)現(xiàn)兩方面進(jìn)行闡述。

模糊C均值 （Fuzzy C-Means，F(xiàn)CM）聚類廣泛用于模式識(shí)別、圖像分割等領(lǐng)域中［1-4］。FCM算法應(yīng)用于圖像分割時(shí)，無(wú)需人為干預(yù)和設(shè)定閾值，可以使圖像分割趨向于更自動(dòng)化。如參考文獻(xiàn)［1］將FCM聚類用于彩色和灰度圖像分割算法研究中。一些改進(jìn)的FCM算法可進(jìn)一步提高 FCM分割聚類算法效率［5］，如參考文獻(xiàn)［6］提出了一種融合結(jié)構(gòu)特征的增強(qiáng)型FCM圖像（EnFCM）分割算法，但它們側(cè)重于提高圖像分割的精度，而不是處理速度。

目前有很多圖像處理并行化的研究，參考文獻(xiàn)［7］采用多線程和MPI實(shí)現(xiàn)了遙感影像數(shù)據(jù)的均值漂移算法并行化，解決均值漂移不能處理過(guò)大影像、處理速度慢的問(wèn)題。參考文獻(xiàn)［8］研究了云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)，其中包括圖像分割技術(shù)。

在圖像分割并行處理方面，現(xiàn)有研究多采用CUDA并行結(jié)構(gòu)［9-10］，參考文獻(xiàn)［10］采用了 CUDA架構(gòu)實(shí)現(xiàn)了FCM算法來(lái)加速圖像分割。但它僅給出了分割結(jié)果和完成時(shí)間，沒(méi)有對(duì)并行效果給出更詳細(xì)的分析，如加速比和并行效率等。而現(xiàn)有研究中使用EnFCM圖像聚類分割方法實(shí)現(xiàn)并行的研究則不多見(jiàn)。

2　基于EnFCM的圖像聚類分割問(wèn)題模型

FCM算法直接對(duì)圖像中的每一個(gè)像素點(diǎn)進(jìn)行聚類，需要計(jì)算所有像素點(diǎn)對(duì)每個(gè)聚類中心的隸屬度，導(dǎo)致聚類速度變慢。對(duì)此本文采用了基于EnFCM的圖像聚類分割算法，它不是針對(duì)圖像像素本身進(jìn)行聚類，而是直接針對(duì)圖像像素的灰度級(jí)進(jìn)行聚類，因?yàn)橄袼鼗叶燃?jí)的個(gè)數(shù) L（通常是 256）遠(yuǎn)遠(yuǎn)小于圖像像素的個(gè)數(shù) n，所以將大大提高處理速度。利用這個(gè)特性，設(shè)計(jì)出用于圖像分割的快速模糊聚類算法EnFCM。

首先生成新圖像，如公式（1）所示。

其中ξ是圖像的有效灰度級(jí)，ξi是樣本點(diǎn)，x是圖像的像素灰度值。

接下來(lái)只需要對(duì)生成的灰度直方圖進(jìn)行模糊聚類，其目標(biāo)函數(shù)如公式（2）所示。

其中rk統(tǒng)計(jì)有效灰度級(jí)級(jí)數(shù)，參數(shù)m是模糊性加權(quán)指數(shù)，用來(lái)決定聚類結(jié)果的模糊程度，n為待分割圖像的灰度級(jí)級(jí)數(shù)（聚類樣本個(gè)數(shù)），L是像素灰度級(jí)的個(gè)數(shù)，c是預(yù)定義的聚類類別數(shù)目，uji是模糊隸屬度矩陣元素，vj是聚類中心。

聚類過(guò)程中需交替迭代更新聚類中心和模糊隸屬度矩陣，如公式（4）、（5）所示。

EnFCM算法的聚類迭代過(guò)程類似于 FCM算法，但它是作用于新生成的圖像數(shù)據(jù)上，且聚類樣本數(shù)取決于圖像的灰度級(jí)數(shù)目，明顯降低了FCM算法的分割時(shí)間，當(dāng)面對(duì)大尺寸的圖像時(shí)，這種優(yōu)勢(shì)更為明顯。

3　基于EnFCM的海量圖像聚類分割算法并行實(shí)現(xiàn)

本文基于EnFCM聚類分割模型提出三種并行策略：純MPI的并行方式、MPI+OpenMP混合編程方法模式和CUDA并行計(jì)算架構(gòu)方法。

3.1MPI并行架構(gòu)

在設(shè)計(jì)純MPI并行策略時(shí)，充分考慮MPI的架構(gòu)特點(diǎn)，將每一幅圖像通過(guò)MPI分發(fā)至一個(gè)核處理，這樣不需要核間通信，避免了通信開(kāi)銷。因?yàn)槊恳环鶊D像處理過(guò)程相對(duì)獨(dú)立，圖像之間的依賴度較?。ㄈ蝿?wù)之間相對(duì)獨(dú)立），因此節(jié)點(diǎn)之間的通信代價(jià)較小。MPI并行策略偽代碼如下：

3.2MPI+OpenMP混合編程并行模式

采用MPI+OpenMP模式時(shí)，MPI實(shí)現(xiàn)圖像的分發(fā)，聚類迭代過(guò)程使用OpenMP并行。它不是對(duì)于每個(gè)CPU核開(kāi)啟一個(gè)MPI進(jìn)程，而是每個(gè)節(jié)點(diǎn)只開(kāi)啟一個(gè)MPI進(jìn)程，這樣參與通信的進(jìn)程大量減少，且同一節(jié)點(diǎn)上OpenMP線程通過(guò)共享內(nèi)存進(jìn)行交互，不需要進(jìn)程間的通信，程序通信開(kāi)銷會(huì)顯著降低。

3.3CUDA并行計(jì)算架構(gòu)

CUDA并行計(jì)算架構(gòu)的優(yōu)勢(shì)在于GPU通過(guò)大量CUDA核共同運(yùn)轉(zhuǎn)，提高整體吞吐率。但并不是所有的計(jì)算都在GPU上，而是將邏輯性較強(qiáng)的模塊和串行部分交由CPU完成，要并行的部分放在GPU，如圖1所示。

圖1　CUDA并行架構(gòu)實(shí)現(xiàn)框圖

在本文分割聚類算法中，目標(biāo)函數(shù)值的計(jì)算、交替迭代更新聚類中心和模糊隸屬度矩陣的計(jì)算過(guò)程是高度并行的，可以交由GPU負(fù)責(zé)，讀取硬盤(pán)數(shù)據(jù)，平均分配外鏈值是串行的，所以剩下的交由CPU計(jì)算。

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

為驗(yàn)證本文提出的三種并行方案的性能，設(shè)計(jì)了仿真實(shí)驗(yàn)，采用運(yùn)行時(shí)間、加速比和效率等三個(gè)指標(biāo)進(jìn)行評(píng)價(jià)。

4.1實(shí)驗(yàn)設(shè)置及參數(shù)

實(shí)驗(yàn)采用了兩個(gè)環(huán)境，方案一、二采用第一種集群環(huán)境：有10個(gè)可用節(jié)點(diǎn)，每節(jié)點(diǎn)2個(gè)物理封裝共16個(gè)CPU核心 32線程，Intel（R）Xeon（R）CPU E5-26700 2.60 GHz主頻，62 GB內(nèi)存。方案三在單臺(tái)PC機(jī)上進(jìn)行，其配置為：Intel 3470 3.20 GHz CPU，Nvida GeForce GTX 660的GPU，4 GB×2內(nèi)存。

實(shí)驗(yàn)采用256像素點(diǎn)的黑白圖像，圖像規(guī)模分別從5 000增至 20 000幅（圖像大小基本相同，有大量重復(fù)圖像）。

4.2執(zhí)行時(shí)間

由于實(shí)驗(yàn)環(huán)境不同，分別在兩個(gè)實(shí)驗(yàn)環(huán)境下使用單CPU串行執(zhí)行，取10次運(yùn)行的平均值，同時(shí)實(shí)現(xiàn)了FCM聚類分割算法與本文方法，對(duì)比結(jié)果如圖2所示。

由圖2知，串行執(zhí)行時(shí)間隨圖像規(guī)模增大而增加，F(xiàn)CM的串行時(shí)間遠(yuǎn)大于EnFCM算法。三種并行方案明顯比各自串行時(shí)間有大幅降低，其中以CUDA并行方案最好，MPI次之，MPI+OpenMP稍差，這是因?yàn)镺penMP并行時(shí)增加了通信開(kāi)銷，而MPI沒(méi)有核間通信。

圖2　執(zhí)行時(shí)間

4.3加速比

在不同圖像規(guī)模時(shí)三種并行方案的加速比如圖3所示。

圖3　加速比

從圖3中測(cè)試結(jié)果看出，三種并行方案加速比均表現(xiàn)較好，至少都有7倍以上的加速，而且加速比隨圖像規(guī)模的增長(zhǎng)而趨于線性，這說(shuō)明并行方案在圖像數(shù)據(jù)規(guī)模較大時(shí)能取得更好的效果，證明了并行方案的有效性。

4.4并行效率

并行效率在不同圖像規(guī)模情況下的表現(xiàn)，如圖4所示。

圖4　并行效率

由圖4所示，并行效率表現(xiàn)一樣令人滿意，最差情況也達(dá)到了70％。三種并行方案在并行效率方面的表現(xiàn)與加速比類似，由同樣的因素導(dǎo)致，不再贅述。

5　結(jié)論

圖像分割的處理速度是圖像處理的瓶頸，本文在EnFCM的基礎(chǔ)上實(shí)現(xiàn)了海量圖像聚類分割的并行化。由實(shí)驗(yàn)結(jié)果知，并行策略取得了良好的加速效果，其中以CUDA最優(yōu)，純MPI次之，MPI+OpenMP稍差。這是由于CUDA中的GPU部分并行實(shí)現(xiàn)了大部分計(jì)算量，證明了這種CPU+GPU結(jié)構(gòu)的優(yōu)勢(shì)及本文實(shí)驗(yàn)方案的有效性。另外OpenMP混合編程結(jié)構(gòu)中由于線程間通信開(kāi)銷的影響，反而不如純MPI結(jié)構(gòu)的效果好。說(shuō)明對(duì)于較獨(dú)立的任務(wù)采用純MPI的結(jié)構(gòu)要比MPI+OpenMP混合編程結(jié)構(gòu)更好。如果任務(wù)間依賴性較強(qiáng)，則采用MPI+OpenMP混合編程結(jié)構(gòu)更為合適，因?yàn)镺penMP通信開(kāi)銷要小于MPI。

［1］丁震，胡鐘山，楊靖宇，等.FCM算法用于灰度圖像分割的研究［J］.電子學(xué)報(bào)，1997，25（5）：39-43.

［2］湯官寶.基于量子粒子群的改進(jìn)模糊聚類圖像分割算法［J］.微型機(jī)與應(yīng)用，2014，33（15）：40-42.

［3］趙憲強(qiáng)，王希常，劉江.一種自適應(yīng)的模糊 C均值聚類圖像分割方法［J］.微型機(jī)與應(yīng)用，2012，31（20）：33-35.

［4］于楊，崔天時(shí)，董桂菊.基于顏色特征與直方圖閾值相結(jié)合的田間青椒圖像分割算法 ［J］.微型機(jī)與應(yīng)用，2010，23（4）：51-53.

［5］MOHAMMAD A H，KIM J M.An enhanced fuzzy c-means algorithm for audio segmentation and classification［J］.Multimedia Tools and Applications，2013，63（3）：485-500.

［6］崔兆華，張萍，李洪軍，等.融合結(jié)構(gòu)特征的增強(qiáng)型 FCM圖像分割算法［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2013， 34（7）：922-926.

［7］沈占鋒，駱劍承，吳煒，等.遙感影像均值漂移分割算法的并行化實(shí)現(xiàn)［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2010，42（5）：811-815.

［8］于戈，谷峪，鮑玉斌，等.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1753-1766.

［9］LI H Y，YANG Z F，HE H Z.An improved image segmentation algorithm based on GPU parallel computing［J］.Journal of Software，2014，9（8）：1985-1990.

［10］ZDZISAWA R，JAROSAW G.CUDA based fuzzy C-means acceleration for the segmentation of images with fungus grown in foam matrices［J］.Image Processing＆amp；Communication，2013，17（4）：191-200.

Paralleled segmentation cluster algorithm based on EnFCM for large-scale image

Zuo Liyun1，2，Luo Chengyu2，Zuo Youxiang3
（1.Experiment Teaching Department，Guangdong University of Petrochemical Technology，Maoming 525000，China；
2.School of Computer Science＆amp；Engineering，South China University of Technology，Guangzhou 510006，China；3.Key Lab of Digital Signal and Image Processing of Guangdong Province，Shantou University，Shantou 515063，China）

The processing speed of image segmentation is the bottleneck for large image data processing.An image clustering segmentation model is proposed based on EnFCM.It directly clusters grayscale of image pixel，clustering can significantly improve the image segmentation processing speed.In order to further improve the processing speed，three parallel design optimization strategies are designed by combining model features of EnFCM image clustering segmentation，they are pure MPI parallel method，MPI+ OpenMP hybrid programming and CUDA parallel architecture.These parallel methods are suitable for large-scale image processing.Experimental results show that the proposed parallel optimization strategies have achieved good acceleration effect.

image segmentation clustering；FCM algorithm；MPI+OpenMP；CUDA

TP393

A

1674-7720（2015）15-0055-04

左利云，羅成煜，左右祥.基于 EnFCM的海量圖像聚類分割算法的并行研究［J］.微型機(jī)與應(yīng)用，2015，34（15）：55-58.

2015-05-29）

左利云（1980-），女，碩士，副教授，主要研究方向：云計(jì)算、并行計(jì)算。

羅成煜（1989-），男，碩士，主要研究方向：并行計(jì)算。

左右祥（1990-），男，碩士，主要研究方向：數(shù)字圖像處理。

茂名市科技計(jì)劃項(xiàng)目（2014015）