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

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

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

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

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

0　引言

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

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

1　相關(guān)工作

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

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

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

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

2　基于EnFCM的圖像聚類分割問題模型

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

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

其中ξ是圖像的有效灰度級，ξi是樣本點，x是圖像的像素灰度值。

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

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

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

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

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

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

3.1MPI并行架構(gòu)

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

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

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

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

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

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

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

4　實驗驗證

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

4.1實驗設(shè)置及參數(shù)

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

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

4.2執(zhí)行時間

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

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

圖2　執(zhí)行時間

4.3加速比

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

圖3　加速比

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

4.4并行效率

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

圖4　并行效率

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

5　結(jié)論

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

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

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

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

［4］于楊，崔天時，董桂菊.基于顏色特征與直方圖閾值相結(jié)合的田間青椒圖像分割算法 ［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)特征的增強型 FCM圖像分割算法［J］.東北大學(xué)學(xué)報（自然科學(xué)版），2013， 34（7）：922-926.

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

［8］于戈，谷峪，鮑玉斌，等.云計算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)［J］.計算機學(xué)報，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］.微型機與應(yīng)用，2015，34（15）：55-58.

2015-05-29）

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

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

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

茂名市科技計劃項目（2014015）