摘 要： 圖像分割的處理速度成為大規(guī)模圖像數(shù)據(jù)處理的瓶頸。本文提出一種基于EnFCM的圖像聚類分割模型,，直接對圖像像素的灰度級進(jìn)行聚類,，能顯著提高圖像聚類分割的處理速度。為進(jìn)一步提高處理速度,，結(jié)合EnFCM圖像聚類分割模型特點,，設(shè)計了三種并行優(yōu)化策略——純MPI并行方法、MPI+OpenMP混合編程方法和CUDA并行架構(gòu)方法，使其適合于大規(guī)模圖像處理,。實驗結(jié)果表明,，提出的三種并行優(yōu)化策略都取得良好的加速效果。
關(guān)鍵詞： 圖像聚類分割,；FCM算法,；MPI+OpenMP；CUDA
0 引言
在圖像處理中圖像分割是不可或缺的關(guān)鍵步驟,，圖像分析與模式識別都是以圖像分割為基礎(chǔ)的,，因此圖像分割處理的速度將直接影響圖像處理和分析的速度。隨著圖像尺寸及處理規(guī)模的增大,，樣本集的數(shù)據(jù)也急劇增加,，導(dǎo)致聚類速度變慢，相應(yīng)地影響其圖像處理速度,，成為大規(guī)模圖像處理的一個瓶頸問題。
目前大量出現(xiàn)的集群和并行計算技術(shù)為這一問題提供了有效的解決方案,。利用強(qiáng)大的分布式并行處理能力,，可將圖像處理的任務(wù)分解，將子任務(wù)分配到多個處理器同時執(zhí)行,，能顯著提高大規(guī)模圖像處理速度,。本文將并行技術(shù)應(yīng)用到圖像聚類分割中，以提高其處理速度,。
1 相關(guān)工作
相關(guān)工作主要從基于FCM的圖像聚類分割和圖像分割并行實現(xiàn)兩方面進(jìn)行闡述,。
模糊C均值（Fuzzy C-Means，F(xiàn)CM）聚類廣泛用于模式識別,、圖像分割等領(lǐng)域中[1-4],。FCM算法應(yīng)用于圖像分割時，無需人為干預(yù)和設(shè)定閾值,，可以使圖像分割趨向于更自動化,。如參考文獻(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實現(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算法直接對圖像中的每一個像素點進(jìn)行聚類,，需要計算所有像素點對每個聚類中心的隸屬度，導(dǎo)致聚類速度變慢,。對此本文采用了基于EnFCM的圖像聚類分割算法,，它不是針對圖像像素本身進(jìn)行聚類，而是直接針對圖像像素的灰度級進(jìn)行聚類,，因為像素灰度級的個數(shù)L（通常是256）遠(yuǎn)遠(yuǎn)小于圖像像素的個數(shù)n,，所以將大大提高處理速度。利用這個特性,，設(shè)計出用于圖像分割的快速模糊聚類算法EnFCM,。
首先生成新圖像，如公式（1）所示,。
其中ξ是圖像的有效灰度級,，ξi是樣本點，x是圖像的像素灰度值,。
接下來只需要對生成的灰度直方圖進(jìn)行模糊聚類,，其目標(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.1 MPI并行架構(gòu)
在設(shè)計純MPI并行策略時,，充分考慮MPI的架構(gòu)特點,，將每一幅圖像通過MPI分發(fā)至一個核處理，這樣不需要核間通信,，避免了通信開銷,。因為每一幅圖像處理過程相對獨立，圖像之間的依賴度較?。ㄈ蝿?wù)之間相對獨立）,，因此節(jié)點之間的通信代價較小。MPI并行策略偽代碼如下：
The parallel strategy 1：Pure MPI
Input：原始圖像{a[0],，a[1],，…，a[N-1]}
Output：聚類分割后圖像
Begin
初始化,；
MPI任務(wù)劃分,，利用MPI_Bcast函數(shù)廣播給進(jìn)程
{b[0]，b[1],，…，b[p-1]},；
各子進(jìn)程接收主進(jìn)程發(fā)送來的數(shù)據(jù),，并進(jìn)行獨立計算；
各子進(jìn)程輸出處理結(jié)果圖像,，中止各子進(jìn)程,。
End
3.2 MPI+OpenMP混合編程并行模式
采用MPI+OpenMP模式時，MPI實現(xiàn)圖像的分發(fā),，聚類迭代過程使用OpenMP并行,。它不是對于每個CPU核開啟一個MPI進(jìn)程，而是每個節(jié)點只開啟一個MPI進(jìn)程,，這樣參與通信的進(jìn)程大量減少,，且同一節(jié)點上OpenMP線程通過共享內(nèi)存進(jìn)行交互，不需要進(jìn)程間的通信,，程序通信開銷會顯著降低,。
The parallel strategy2：OpenMP+MPI
Input：原始圖像{a[0]，a[1],，…,，a[N-1]}
Output：聚類分割后圖像
Begin
初始化,；
MPI任務(wù)劃分，利用MPI_Bcast函數(shù)廣播給進(jìn)程
{b[0],，b[1],，…，b[p-1]},；
MPI派生出OpenMP線程,；
OpenMP線程計算ξi與聚類中心vj的距離；
各子線程匯合至主線程,，并提交結(jié)果至MPI進(jìn)程,；
MPI各子進(jìn)程輸出處理結(jié)果圖像，終止各子進(jìn)程,。
End
3.3 CUDA并行計算架構(gòu)
CUDA并行計算架構(gòu)的優(yōu)勢在于GPU通過大量CUDA核共同運轉(zhuǎn),，提高整體吞吐率。但并不是所有的計算都在GPU上,，而是將邏輯性較強(qiáng)的模塊和串行部分交由CPU完成,，要并行的部分放在GPU，如圖1所示,。
在本文分割聚類算法中,，目標(biāo)函數(shù)值的計算、交替迭代更新聚類中心和模糊隸屬度矩陣的計算過程是高度并行的,，可以交由GPU負(fù)責(zé),，讀取硬盤數(shù)據(jù)，平均分配外鏈值是串行的,，所以剩下的交由CPU計算,。
4 實驗驗證
為驗證本文提出的三種并行方案的性能，設(shè)計了仿真實驗,，采用運行時間,、加速比和效率等三個指標(biāo)進(jìn)行評價。
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機(jī)上進(jìn)行,，其配置為：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沒有核間通信,。
4.3 加速比
在不同圖像規(guī)模時三種并行方案的加速比如圖3所示。
從圖3中測試結(jié)果看出,，三種并行方案加速比均表現(xiàn)較好,，至少都有7倍以上的加速，而且加速比隨圖像規(guī)模的增長而趨于線性,，這說明并行方案在圖像數(shù)據(jù)規(guī)模較大時能取得更好的效果,，證明了并行方案的有效性。
4.4 并行效率
并行效率在不同圖像規(guī)模情況下的表現(xiàn),，如圖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ù)間依賴性較強(qiáng)，則采用MPI+OpenMP混合編程結(jié)構(gòu)更為合適,，因為OpenMP通信開銷要小于MPI,。
參考文獻(xiàn)
[1] 丁震，胡鐘山,，楊靖宇,，等.FCM算法用于灰度圖像分割的研究[J].電子學(xué)報，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] 于楊,，崔天時，董桂菊.基于顏色特征與直方圖閾值相結(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é)報（自然科學(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].計算機(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 & Communication,， 2013,， 17（4）：191-200.