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

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

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

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

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

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

0　引言

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

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

1　相關工作

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

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

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

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

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

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

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

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

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

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

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

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

3　基于EnFCM的海量圖像聚類分割算法并行實現

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

3.1MPI并行架構

在設計純MPI并行策略時，充分考慮MPI的架構特點，將每一幅圖像通過MPI分發至一個核處理，這樣不需要核間通信，避免了通信開銷。因為每一幅圖像處理過程相對獨立，圖像之間的依賴度較小（任務之間相對獨立），因此節點之間的通信代價較小。MPI并行策略偽代碼如下：

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

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

3.3CUDA并行計算架構

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

圖1　CUDA并行架構實現框圖

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

4　實驗驗證

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

4.1實驗設置及參數

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

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

4.2執行時間

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

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

圖2　執行時間

4.3加速比

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

圖3　加速比

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

4.4并行效率

并行效率在不同圖像規模情況下的表現，如圖4所示。

圖4　并行效率

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

5　結論

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

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

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

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

［4］于楊，崔天時，董桂菊.基于顏色特征與直方圖閾值相結合的田間青椒圖像分割算法 ［J］.微型機與應用，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］崔兆華，張萍，李洪軍，等.融合結構特征的增強型 FCM圖像分割算法［J］.東北大學學報（自然科學版），2013， 34（7）：922-926.

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

［8］于戈，谷峪，鮑玉斌，等.云計算環境下的大規模圖數據處理技術［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＆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］.微型機與應用，2015，34（15）：55-58.

2015-05-29）

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

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

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

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