摘 要： 图像分割的处理速度成为大规模图像数据处理的瓶颈。本文提出一种基于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.1 MPI并行架构
在设计纯MPI并行策略时，充分考虑MPI的架构特点，将每一幅图像通过MPI分发至一个核处理，这样不需要核间通信，避免了通信开销。因为每一幅图像处理过程相对独立，图像之间的依赖度较小（任务之间相对独立），因此节点之间的通信代价较小。MPI并行策略伪代码如下：
The parallel strategy 1：Pure MPI
Input：原始图像{a[0]，a[1]，…，a[N-1]}
Output：聚类分割后图像
Begin
初始化；
MPI任务划分，利用MPI_Bcast函数广播给进程
{b[0]，b[1]，…，b[p-1]}；
各子进程接收主进程发送来的数据，并进行独立计算；
各子进程输出处理结果图像，中止各子进程。
End
3.2 MPI+OpenMP混合编程并行模式
采用MPI+OpenMP模式时，MPI实现图像的分发，聚类迭代过程使用OpenMP并行。它不是对于每个CPU核开启一个MPI进程，而是每个节点只开启一个MPI进程，这样参与通信的进程大量减少，且同一节点上OpenMP线程通过共享内存进行交互，不需要进程间的通信，程序通信开销会显著降低。
The parallel strategy2：OpenMP+MPI
Input：原始图像{a[0]，a[1]，…，a[N-1]}
Output：聚类分割后图像
Begin
初始化；
MPI任务划分，利用MPI_Bcast函数广播给进程
{b[0]，b[1]，…，b[p-1]}；
MPI派生出OpenMP线程；
OpenMP线程计算ξi与聚类中心vj的距离；
各子线程汇合至主线程，并提交结果至MPI进程；
MPI各子进程输出处理结果图像，终止各子进程。
End
3.3 CUDA并行计算架构
CUDA并行计算架构的优势在于GPU通过大量CUDA核共同运转，提高整体吞吐率。但并不是所有的计算都在GPU上，而是将逻辑性较强的模块和串行部分交由CPU完成，要并行的部分放在GPU，如图1所示。
在本文分割聚类算法中，目标函数值的计算、交替迭代更新聚类中心和模糊隶属度矩阵的计算过程是高度并行的，可以交由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没有核间通信。
4.3 加速比
在不同图像规模时三种并行方案的加速比如图3所示。
从图3中测试结果看出，三种并行方案加速比均表现较好，至少都有7倍以上的加速，而且加速比随图像规模的增长而趋于线性，这说明并行方案在图像数据规模较大时能取得更好的效果，证明了并行方案的有效性。
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 & Communication， 2013， 17（4）：191-200.