SLIC超像素分割的并行化实现

陈相廷，张偌雅（河南大学计算机与信息工程学院，开封　475000）

SLIC超像素分割的并行化实现

陈相廷，张偌雅
（河南大学计算机与信息工程学院，开封475000）

数字图像处理往往信息量大，算法复杂度高。SLIC超像素分割算法在图像预处理阶段，通过相邻像素的关联特征，将单一像素点聚类为超像素块，有效过滤高相似度重复信息。根据聚类过程相对独立的特性，并行化实现SLIC超像素分割算法，有效降低算法时间复杂度。

数字图像处理；超像素；并行计算

0　引言

图像较文字、语言等方式可更加生动地展现所描述对象的空间分布、形态结构、纹理色泽等特征［1］。数字图像因其易存储、易处理、便于传输等多种优势，现已广泛应用于生物医疗、航空航天、工业生产、军事公安、环境检测等多个领域。与此同时，为满足多种需求，数字图像处理技术得到飞速发展。随着处理数据量的日益增长，如何快速高效地得出结果已成为当代数字图像处理技术的研究重点。

图像预处理可最大限度简化图像数据，增强后期处理所需敏感区域的特征信息。以单一像素为单位的处理方式，迭代次数多，数据冗余大，重复信息多，这会大大增加整个处理过程的时间消耗，降低了处理效率。利用冗余信息的关联性将同类单一像素合并为超像素是当前研究的热点，合并后的超像素块有效突出了关键信息，成为处理算法快速实现的前提［2］。同时，基于每个聚类核心的迭代聚类过程相对独立，关联性较低，能较好地适用并行计算，从而可并行化地实现超像素分割过程，极大提高处理效率。

1　SLIC超像素分割模型

2003年由Ren等人最早研究并提出了超像素的概念，超像素是将信息敏感度较低的单一像素通过局部纹理形态特征的关联，将高相似特征值的像素点聚类为像素块即超像素［3］。纹理边界作为视觉识别的重要线索，可直接体现图像中梯度变化较大的感兴趣区域。超像素分割模型弱化梯度差异较小部分，增强图像边界部分，可快速定位目标处理区域。

SLIC超像素分割算法是一种基于梯度下降的分割算法，该算法最早由Achanta等人于2010年提出［4］。该算法通过归类聚合的方式首先将RGB色域空间量映射至LAB色域空间，之后根据空间相位、色泽差异、亮度明暗等相似特征，把原图单一像素聚合为以离散分布在原图中的聚类核心为中心的超像素［5］。该方法较基于图论的方法可更好地控制分割所得超像素块的边缘形状，平滑度及数量。SLIC算法通过原图像素对应XY轴坐标值及LAB色域空间对应特征分量所组成的5阶特征矩阵，标定聚类核心附近处的聚合阈值［6］。主要步骤如下：

（1）聚类核心初始化。在原图中离散地生成聚类核心，将原图中所有K个像素点聚合成形态规则，边界平滑且分布集中的Q个超像素块，即每个超像素聚合量为K/Q，理想状态下聚类核心空间相邻距离近似为H=

（2）聚类核心校准。通常情况下，聚类核心分布在梯度变化较大处时聚合过程会产生较大误差。为避免该情况出现，通常采用的方法是设定窗口，取聚类核心n×n（n取值通常为3）邻域内梯度最小处坐标代替原核心坐标。同时为避免后续步骤重复该操作，将分配一个单独标号给新的聚类核心。

（3）聚类阈值计算。任取原图中的两个像素点e和f，利用像素点对应LAB色域空间映射值及对应XY轴坐标值计算相似度，公式如下：

其中dlab表示像素点e，f的色差值；dxy为像素点e，f的空间相位距离；DH表示像素聚类阈值，H是邻域聚类核心的距离；m表示调节因子，用来平衡色差值和空间相位距离在聚类阈值计算中所占比重，变化区间为［1，20］，通常为10。计算所得DH值与像素关联度正相关，即随着DH值增大，像素关联度也随之增高。

（4）算法优化。为提高聚合过程的效率，SLIC算法搜索以聚类核心为基准，2H×2H的邻域范围，如图1所示。

图1　

将聚类核心邻域范围内相似度大于聚类阈值的像素合并，同时将聚类核心的标号分配给超像素内的每个像素。重复聚合过程直至所有超像素收敛，超像素分割算法完成。

2　并行实现

在实际应用中，SLIC超像素分割算法往往用于处理多领域海量图像，处理数据量大，运行时间较长。随着高性能多核计算机的快速发展，并行计算已广泛应用于大规模工程与科研运算，并行化实现算法已成为趋势。MPI（Message Passing Interface，MPI）是并行开发中的常用模型，该模型基于消息传递机制，适用于低关联度执行过程的并行实现［7］。

SLIC超像素分割算法在初始化分布聚类核心后，聚核校准与迭代聚类的过程关联度较小，适用于并行计算，可通过分配独立的内存堆栈并行完成。最后将所生成单一超像素块整合。并行实现效果如图2所示。

图2　

3　实验结果及分析

本文对算法的并行实现是基于Windows7（64位）平台，硬件配置为Intel Core i7处理器，内存为8GB。MPI的实现采用的是MPICH2。算法的执行环境为Microsoft Visual Studio 2012。通常并行计算的衡量指标为加速比和效率，定义如下：

其中S表示加速比，Ts表示单一进程执行时间，Tp表示并行计算所用时间，E表示效率，P为并行进程数。将图2中a，c两图设为实验样本一号和二号，程序运行结果如表1所示。

通过表1可以得出，并行化实现SLIC超像素分割算法可大幅降低算法运行所耗时间。随着处理数据量的提升，算法并行效率提升也越发显著。但随着进程数的增加，并行效率明显降低，原因是并行计算中用于进程间通信和数据交互的系统开销会随着进程数增大而相应增加。所以在工程实践中应根据硬件配置来设定进程数，以达到最佳效率。

表1　SLIC算法并行运算效果

4　结语

SLIC超像素分割算法根据图像相位、纹理、色泽等特征将高相似度像素聚合为边界平滑，分布均匀的超像素块，可有效在预处理阶段突出图像边缘轮廓信息，降低后续处理数据量。同时，并行化实现SLIC算法可大大降低算法时耗，提高运行效率。未来研究将致力于继续降低算法复杂度，提高并行效率，为大规模工程与科研运算提供支持。

［1］刘丽，匡纲要.图像纹理特征提取方法综述［J］.中国图象图形学报，2009，14（04）：622-635.

［2］陈相廷，张偌雅，渠星星，等.SLIC超像素分割在医学图像处理中的应用［J］.现代计算机：普及版，2015（35）：52-56.

［3］Malik J.Learning a Classification Model for Segmentation［C］.null.IEEE Computer Society，2003：10-17 vol.1.

［4］Achanta R，Shaji A，Smith K，et al.SLIC Superpixels［J］.Epfl，2010.

［5］Bergh M V D，Boix X，Roig G，et al.SEEDS：Superpixels Extracted via Energy-Driven Sampling［J］.International Journal of Computer Vision，2013，111（3）：298-314.

［6］王春瑶，陈俊周，李炜.超像素分割算法研究综述［J］.计算机应用研究，2014，01：6-11.

［7］吕捷，张天序，张必银.MPI并行计算在图像处理方面的应用［J］.红外与激光工程，2004，33（05）：496-499.

Digital Image Processing；Superpixels；Parallel Computing

Parallel Implementation of SLIC Superpixels Segmentation

CHEN Xiang-ting，ZHANG Ruo-ya
（College of Computer and Information Engineering，Henan University，Kaifeng 475000）

Digital image processing always has a large amount of information and high algorithm complexity.SLIC superpixels segmentation algorithm uses adjacent pixels correlation feature，clustering single pixel for superpixels.It can filter the high similarity duplicate information effectively in image pre-processing stage.According to the relatively independent characteristics of the clustering process，realizes the SLIC superpixels segmentation algorithm in parallel，which reduces the time complexity of the algorithm effectively.

1007-1423（2016）29-0075-03

10.3969/j.issn.1007-1423.2016.29.018

陈相廷（1991-），男，河南安阳人，硕士研究生，研究方向为数字图像处理张偌雅（1993-），女，河南信阳人，硕士研究生，研究方向为数字图像处理

2016-08-03

2016-10-10