摘 要： 圖像分割的處理速度成為大規(guī)模圖像數(shù)據(jù)處理的瓶頸。本文提出一種基于EnFCM的圖像聚類分割模型，直接對圖像像素的灰度級進行聚類，能顯著提高圖像聚類分割的處理速度。為進一步提高處理速度，結(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ù)也急劇增加，導致聚類速度變慢，相應(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)用于圖像分割時，無需人為干預和設(shè)定閾值，可以使圖像分割趨向于更自動化。如參考文獻[1]將FCM聚類用于彩色和灰度圖像分割算法研究中。一些改進的FCM算法可進一步提高FCM分割聚類算法效率[5]，如參考文獻[6]提出了一種融合結(jié)構(gòu)特征的增強型FCM圖像（EnFCM）分割算法，但它們側(cè)重于提高圖像分割的精度，而不是處理速度。
目前有很多圖像處理并行化的研究，參考文獻[7]采用多線程和MPI實現(xiàn)了遙感影像數(shù)據(jù)的均值漂移算法并行化，解決均值漂移不能處理過大影像、處理速度慢的問題。參考文獻[8]研究了云計算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)，其中包括圖像分割技術(shù)。
在圖像分割并行處理方面，現(xiàn)有研究多采用CUDA并行結(jié)構(gòu)[9-10]，參考文獻[10]采用了CUDA架構(gòu)實現(xiàn)了FCM算法來加速圖像分割。但它僅給出了分割結(jié)果和完成時間，沒有對并行效果給出更詳細的分析，如加速比和并行效率等。而現(xiàn)有研究中使用EnFCM圖像聚類分割方法實現(xiàn)并行的研究則不多見。
2 基于EnFCM的圖像聚類分割問題模型
FCM算法直接對圖像中的每一個像素點進行聚類，需要計算所有像素點對每個聚類中心的隸屬度，導致聚類速度變慢。對此本文采用了基于EnFCM的圖像聚類分割算法，它不是針對圖像像素本身進行聚類，而是直接針對圖像像素的灰度級進行聚類，因為像素灰度級的個數(shù)L（通常是256）遠遠小于圖像像素的個數(shù)n，所以將大大提高處理速度。利用這個特性，設(shè)計出用于圖像分割的快速模糊聚類算法EnFCM。
首先生成新圖像，如公式（1）所示。
其中ξ是圖像的有效灰度級，ξi是樣本點，x是圖像的像素灰度值。
接下來只需要對生成的灰度直方圖進行模糊聚類，其目標函數(shù)如公式（2）所示。
其中rk統(tǒng)計有效灰度級級數(shù)，參數(shù)m是模糊性加權(quán)指數(shù)，用來決定聚類結(jié)果的模糊程度，n為待分割圖像的灰度級級數(shù)（聚類樣本個數(shù)），L是像素灰度級的個數(shù)，c是預定義的聚類類別數(shù)目，uji是模糊隸屬度矩陣元素，vj是聚類中心。
聚類過程中需交替迭代更新聚類中心和模糊隸屬度矩陣，如公式（4）、（5）所示。
EnFCM算法的聚類迭代過程類似于FCM算法，但它是作用于新生成的圖像數(shù)據(jù)上，且聚類樣本數(shù)取決于圖像的灰度級數(shù)目，明顯降低了FCM算法的分割時間，當面對大尺寸的圖像時，這種優(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ù)廣播給進程
{b[0]，b[1]，…，b[p-1]}；
各子進程接收主進程發(fā)送來的數(shù)據(jù)，并進行獨立計算；
各子進程輸出處理結(jié)果圖像，中止各子進程。
End
3.2 MPI+OpenMP混合編程并行模式
采用MPI+OpenMP模式時，MPI實現(xiàn)圖像的分發(fā)，聚類迭代過程使用OpenMP并行。它不是對于每個CPU核開啟一個MPI進程，而是每個節(jié)點只開啟一個MPI進程，這樣參與通信的進程大量減少，且同一節(jié)點上OpenMP線程通過共享內(nèi)存進行交互，不需要進程間的通信，程序通信開銷會顯著降低。
The parallel strategy2：OpenMP+MPI
Input：原始圖像{a[0]，a[1]，…，a[N-1]}
Output：聚類分割后圖像
Begin
初始化；
MPI任務(wù)劃分，利用MPI_Bcast函數(shù)廣播給進程
{b[0]，b[1]，…，b[p-1]}；
MPI派生出OpenMP線程；
OpenMP線程計算ξi與聚類中心vj的距離；
各子線程匯合至主線程，并提交結(jié)果至MPI進程；
MPI各子進程輸出處理結(jié)果圖像，終止各子進程。
End
3.3 CUDA并行計算架構(gòu)
CUDA并行計算架構(gòu)的優(yōu)勢在于GPU通過大量CUDA核共同運轉(zhuǎn)，提高整體吞吐率。但并不是所有的計算都在GPU上，而是將邏輯性較強的模塊和串行部分交由CPU完成，要并行的部分放在GPU，如圖1所示。
在本文分割聚類算法中，目標函數(shù)值的計算、交替迭代更新聚類中心和模糊隸屬度矩陣的計算過程是高度并行的，可以交由GPU負責，讀取硬盤數(shù)據(jù)，平均分配外鏈值是串行的，所以剩下的交由CPU計算。
4 實驗驗證
為驗證本文提出的三種并行方案的性能，設(shè)計了仿真實驗，采用運行時間、加速比和效率等三個指標進行評價。
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幅（圖像大小基本相同，有大量重復圖像）。
4.2 執(zhí)行時間
由于實驗環(huán)境不同，分別在兩個實驗環(huán)境下使用單CPU串行執(zhí)行，取10次運行的平均值，同時實現(xiàn)了FCM聚類分割算法與本文方法，對比結(jié)果如圖2所示。
由圖2知，串行執(zhí)行時間隨圖像規(guī)模增大而增加，F(xiàn)CM的串行時間遠大于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)一樣令人滿意，最差情況也達到了70%。三種并行方案在并行效率方面的表現(xiàn)與加速比類似，由同樣的因素導致，不再贅述。
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].電子學報，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].東北大學學報（自然科學版），2013，34（7）：922-926.
[7] 沈占鋒，駱劍承，吳煒，等.遙感影像均值漂移分割算法的并行化實現(xiàn)[J].哈爾濱工業(yè)大學學報，2010，42（5）：811-815.
[8] 于戈，谷峪，鮑玉斌，等.云計算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)[J].計算機學報，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.