摘 要： 圖像分割的處理速度成為大規(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)化策略都取得良好的加速效果。
關(guān)鍵詞： 圖像聚類分割；FCM算法；MPI+OpenMP；CUDA
0 引言
在圖像處理中圖像分割是不可或缺的關(guān)鍵步驟，圖像分析與模式識(shí)別都是以圖像分割為基礎(chǔ)的，因此圖像分割處理的速度將直接影響圖像處理和分析的速度。隨著圖像尺寸及處理規(guī)模的增大，樣本集的數(shù)據(jù)也急劇增加，導(dǎo)致聚類速度變慢，相應(yīng)地影響其圖像處理速度，成為大規(guī)模圖像處理的一個(gè)瓶頸問題。
目前大量出現(xiàn)的集群和并行計(jì)算技術(shù)為這一問題提供了有效的解決方案。利用強(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í)，無需人為干預(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ù)的均值漂移算法并行化，解決均值漂移不能處理過大影像、處理速度慢的問題。參考文獻(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算法來加速圖像分割。但它僅給出了分割結(jié)果和完成時(shí)間，沒有對(duì)并行效果給出更詳細(xì)的分析，如加速比和并行效率等。而現(xiàn)有研究中使用EnFCM圖像聚類分割方法實(shí)現(xiàn)并行的研究則不多見。
2 基于EnFCM的圖像聚類分割問題模型
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是圖像的像素灰度值。
接下來只需要對(duì)生成的灰度直方圖進(jìn)行模糊聚類，其目標(biāo)函數(shù)如公式（2）所示。
其中rk統(tǒng)計(jì)有效灰度級(jí)級(jí)數(shù)，參數(shù)m是模糊性加權(quán)指數(shù)，用來決定聚類結(jié)果的模糊程度，n為待分割圖像的灰度級(jí)級(jí)數(shù)（聚類樣本個(gè)數(shù)），L是像素灰度級(jí)的個(gè)數(shù)，c是預(yù)定義的聚類類別數(shù)目，uji是模糊隸屬度矩陣元素，vj是聚類中心。
聚類過程中需交替迭代更新聚類中心和模糊隸屬度矩陣，如公式（4）、（5）所示。
EnFCM算法的聚類迭代過程類似于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.1 MPI并行架構(gòu)
在設(shè)計(jì)純MPI并行策略時(shí)，充分考慮MPI的架構(gòu)特點(diǎn)，將每一幅圖像通過MPI分發(fā)至一個(gè)核處理，這樣不需要核間通信，避免了通信開銷。因?yàn)槊恳环鶊D像處理過程相對(duì)獨(dú)立，圖像之間的依賴度較小（任務(wù)之間相對(duì)獨(dú)立），因此節(jié)點(diǎn)之間的通信代價(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)行獨(dú)立計(jì)算；
各子進(jìn)程輸出處理結(jié)果圖像，中止各子進(jìn)程。
End
3.2 MPI+OpenMP混合編程并行模式
采用MPI+OpenMP模式時(shí)，MPI實(shí)現(xiàn)圖像的分發(fā)，聚類迭代過程使用OpenMP并行。它不是對(duì)于每個(gè)CPU核開啟一個(gè)MPI進(jìn)程，而是每個(gè)節(jié)點(diǎn)只開啟一個(gè)MPI進(jìn)程，這樣參與通信的進(jìn)程大量減少，且同一節(jié)點(diǎn)上OpenMP線程通過共享內(nèi)存進(jìn)行交互，不需要進(jìn)程間的通信，程序通信開銷會(huì)顯著降低。
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線程計(jì)算ξi與聚類中心vj的距離；
各子線程匯合至主線程，并提交結(jié)果至MPI進(jìn)程；
MPI各子進(jìn)程輸出處理結(jié)果圖像，終止各子進(jìn)程。
End
3.3 CUDA并行計(jì)算架構(gòu)
CUDA并行計(jì)算架構(gòu)的優(yōu)勢(shì)在于GPU通過大量CUDA核共同運(yùn)轉(zhuǎn)，提高整體吞吐率。但并不是所有的計(jì)算都在GPU上，而是將邏輯性較強(qiáng)的模塊和串行部分交由CPU完成，要并行的部分放在GPU，如圖1所示。
在本文分割聚類算法中，目標(biāo)函數(shù)值的計(jì)算、交替迭代更新聚類中心和模糊隸屬度矩陣的計(jì)算過程是高度并行的，可以交由GPU負(fù)責(zé)，讀取硬盤數(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í)增加了通信開銷，而MPI沒有核間通信。
4.3 加速比
在不同圖像規(guī)模時(shí)三種并行方案的加速比如圖3所示。
從圖3中測(cè)試結(jié)果看出，三種并行方案加速比均表現(xiàn)較好，至少都有7倍以上的加速，而且加速比隨圖像規(guī)模的增長而趨于線性，這說明并行方案在圖像數(shù)據(jù)規(guī)模較大時(shí)能取得更好的效果，證明了并行方案的有效性。
4.4 并行效率
并行效率在不同圖像規(guī)模情況下的表現(xiàn)，如圖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)中由于線程間通信開銷的影響，反而不如純MPI結(jié)構(gòu)的效果好。說明對(duì)于較獨(dú)立的任務(wù)采用純MPI的結(jié)構(gòu)要比MPI+OpenMP混合編程結(jié)構(gòu)更好。如果任務(wù)間依賴性較強(qiáng)，則采用MPI+OpenMP混合編程結(jié)構(gòu)更為合適，因?yàn)镺penMP通信開銷要小于MPI。
參考文獻(xiàn)
[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 & Communication， 2013， 17（4）：191-200.