一种新的大规模图像数据集分割方法*

王建玺，张国平

（平顶山学院软件学院，平顶山467000）

一种新的大规模图像数据集分割方法*

王建玺，张国平

（平顶山学院软件学院，平顶山467000）

图像分割是图像识别过程中的一个重要步骤，在计算机视觉研究中占有非常重要的地位，图像分割的好坏直接影响图像识别的效果。为提高大规模图像数据集的分割效果，实现自动、快速、高质量分割，首先采用均值漂移算法对大规模图像进行预分割以降低图像规模，然后根据图像的颜色特征使用层次聚类算法对分割后的小区域进行聚类处理，以实现快速分割图像。实验结果表明，该方法能够有效减少图像分割时的运算时间和空间复杂度，提高图像分割效率，获取良好的图像分割效果，为后续图像分析、理解和识别打下基础。

均值漂移算法；层次聚类算法；大规模图像数据集；图像平滑；预分割；图像识别

1 引 言

图像分割是图像识别过程中的一个重要环节，在计算机视觉研究中占有非常重要的地位。图像分割的好坏对后续图像分析、理解和识别至关重要［1］。目前，电子成像技术不断提高，电子设备拍摄的图像像素量增长很快，使用聚类算法处理大像素图像能够获得较好的分割效果，但单独使用聚类算法对图像进行分割需要的时间太长，且较高的时间复杂度和空间复杂度要求使分割实现起来极其困难，在某些情况下几乎是无法实现的。目前，一般使用复杂度比较低的聚类算法进行预处理，随后再使用较高复杂度的聚类算法进行二次聚类处理。例如分水岭算法与谱聚类算法相结合［2］，轮廓波变换与改进模糊C均值聚类相结合［3］，均值漂移算法与归一化算法相结合［4］，标记分水岭和区域合并算法相结合［5］，EHMM－HMT与MSWHMT相结合［6］，边缘流引导的各向异性扩散算法与归一化算法相结合［7］等。在这类图像分割方法中，都是采用复杂度低的算法先把原始图像划分成较多的小区域，然后以这些小区域为样本，选取这些小区域的某方面的特征进行二次聚类处理，最后实现大规模图像数据集的分割。通过这种预处理方式有效减少了二次处理的图像集的数据量，实现了整体算法复杂度的降低和处理速度的提高。为此，研究中提出了一种新的图像分割方法，首先对大规模图像数据集采用均值漂移算法进行预分割，再使用层次聚类算法对预分割的图像结果进行二次聚类处理，二者结合起来能快速有效的对大规模图像集进行分割，且分割效果比较好。

2 预分割

采用均值漂移算法进行图像分割其实是图像平滑的扩展，因彩色图像数据量较大，故以彩色图像为例，来介绍图像平滑的过程。彩色图像任一点用一个五维的向量来表示，表达式为x＝（xs，xr），这里xs表示彩色图像二维地址空间坐标，xr表示彩色图像的三维特征向量。其核函数公式为：

公式（1）中，C是归一化常量；p、d表示的是空间维度（其中p＝3，d＝2）；hs表示该核函数的半径，指空域的核大小；hr表示特征空间半径，表示值域的核大小。这里假设参数M为划分区域像素数目最小值，xi表示d维原始输入图像中的数据点，zi表示经均值漂移预处理后的点，基于均值漂移算法的图像平滑步骤如下：

步骤1：初始化，令j＝1且yi，1＝xi，从需要处理图像的第一个像素点开始进行计算，并把偏移过程核函数的中心位置记录下来，直至整幅图像处理完毕；

步骤2：根据均值漂移算法计算出的yi，j＋1值，一直到此次迭代满足收敛条件结束，并记录下该收敛值yi，c；

在使用均值算法进行图像分割时，根据图像平滑的结果，把在同一密度极大值点收敛的全部像素作为同一类，对该类中的所用像素点赋予相同的标号，如果得到某个类的点数量小于最小值M，把该类去除。具体分割过程如下：

步骤1：在图像平滑处理过程中，根据记录下来的五维向量的收敛点，把收敛于同一个点的像素划归同一个类中；

步骤2：根据hs和hr参数的值，把空间域中距离小于hs及特征空间中距离小于hr的全部点zi划分到同一类中，如果最终划分为m类，则用｛Cn｝n＝1，…，m表示；

步骤3：标记图像，Li＝｛n｜zi∈Cn｝，并把区域像素少于M的区域合并到与它相邻的小区域中。

预分割后存在过分割现象，图像被分割成很多比较小的区域，目标物体被分割的较细致，物体的边界信息都得到了很好的保留。在图像分割中，hr、hs这两个参数的选择直接影响分割结果，在具体操作过程中要根据解析度要求给出具体的值。

3 二次聚类分割

3．1 图像特征选择

研究中采用层次聚类算法对图像进行二次聚类处理。因为彩色图像中的颜色是最主要特征，所以把图像的颜色信息作为特征空间，其中任一点的颜色可以用三维向量Xi表示，Xi＝（x1i，x2i，x3i），不同像素点之间的颜色差异公式为：

经过预分割后，图像被划分成y个区域，任一区域用Ri（i＝1，2，…，m）表示，则任一区域的颜色向量可以用表示，这里表示第y个区域全部像素的各颜色分量的均值。为得到最佳的分割效果，选用Luv颜色模型，该模型具有线性映射特性，L表示像素点的亮度，u、v表示像素点的色度坐标，故被分割的区域间颜色差异可用如下公式表示：

3．2 图像分割过程

在使用层次聚类算法进行二次聚类处理时，把预分割后的每个区域当作一个簇，其均值用XRi表示，用计算出的每个簇之间的差异度构成区域的邻近度矩阵。并采用ward算法实现对簇的合并，因为该算法合并的效果比其他层次聚类算法好。它采用全局目标函数实现层次聚类，首先计算邻近度矩阵中所有邻近簇的误差平方和（SSE），然后合并平方和的增量最小的两个邻近簇，合并后更新邻近度矩阵，共经过n－k次邻近簇合并，最终产生k个簇。假设合并后的簇C*的质心用u*表示，而ni、ui、nj、uj分别表示簇Ci，Cj的大小与均值。则簇Ci，Cj的邻近度更新计算公式为：

则两个簇的误差平方和为：

故簇Ci，Cj的距离为：

在对图像进行全部分割后，在图像中还会存在一些孤立的没有被合并的区域，这些孤立的区域可以采用四邻加权法进行处理，处理后的图像得到一定的平滑，其中一些细小的噪声点可以去除。

下面对结合均值漂移和层次聚类算法实现图像分割的过程进行描述。首先是预分割，采用均值漂移算法对输入的彩色图像进行分割，产生较多的小区域；接着根据预分割的结果，计算所划分区域像素点的颜色均值，将每个区域的颜色均值作为层次聚类算法需要输入的一个数据点；然后根据层次聚类算法，将每个区域的均值数据当作一个簇，构成图像的邻近度矩阵；根据距离函数计算相邻簇的误差平方和，选择误差平方和增量最小的相邻两个簇合并，并更新邻近度矩阵，重复这一步n－k次，直到满足设定的分割类别数k；最后应用加权算子进行分割后处理，去除图像中的孤立噪点。

4 实验结果与分析

在MATLAB2013b环境下进行实验。预分割时均值漂移算法的参数设置为hs＝9，hr＝8，，M＝60，hs表示空域带宽，hr表示值域带宽，M表示区域像素的下限值。图像均从Berkeley的标准彩色图像库BSDS500中进行选择［8］。在使用均值漂移算法分割之后，图像被划分成很多小区域，但是分割的区域数已经远远小于原始图像的像素数目，但分割的区域仍较多，再应用层次聚类算法进行二次聚类处理，把需要合并的区域合并之后，分割效果就比较好了。运用研究中提出的算法进行图像分割时，考虑到原始图像的整体情况，分割后的孤立点很少，分割的边缘很平滑，得到的分割效果较好，图1是实验分割效果图。

图1 分割结果Fig．1 Segmentation results

通过实验可知，图像分割所花费的时间主要在预分割阶段，花费时间在0．6s左右，而聚类合并阶段速度较快，花费时间不到0．1s。对150×200像素的图像来说，图像的像素点数为30000，如果直接采用层次聚类算法进行分割，产生的邻近度矩阵为30000×30000，对该矩阵的运算需要特别大的内存空间，一般的机器是无法运行的。研究中采用的这种方法，用分割得到的小区域代替图像像素点，一般情况下分割的区域不超过300，可见对不超过300的数据组成的矩阵进行处理能够有效降低层次聚类算法输入的数据规模，使二次聚类合并的运算时间和空间复杂度得到有效降低，实验数据证明提出的方法在进行大规模数据集处理时是可行的。

5 结束语

研究中把均值漂移和层次聚类算法结合起来对大规模图像数据集进行分割，既达到了预期的分割效果，又提高了分割速度，且分割效果较好，是一种大规模图像数据集分割的有效方法。

［1］ 许新征，丁世飞，史忠植，等．图像分割的新理论新方法［J］．电子学报，2010，38（2A）：6－82．XU Xin－zheng，DING Shi－fei，SHI Zhong－zhi，et al．New Theories and Methods of Image Segmentation［J］．Acta Electronica Sinica，2010，38（2A）：6－82．

［2］ 马秀丽，焦李成．基于分水岭－谱聚类的SAR图像分割［J］．红外与毫米波学报，2008，27（6）：452－456．MA Xiu－Li，JIAO Li－Cheng．SAR IMAGE SEGMENTATION BASED ON WATERSHED AND SPECTRAL CLUSTERING［J］．Journal of Infrared and Millimeter Waves，2008，27（6）：452－456．

［3］ 刘刚，梁晓庚，张京国．基于轮廓波变换和改进模糊c均值聚类的红外图像分割［J］．系统工程与电子技术，2011，33（2）：443－448．LIU Gang，LIANG Xiao－geng，ZHANG Jing－guo．Contourlet transform and improved fuzzy c－means clustering based infrared image segmentation［J］．Systems Engineering and Electronics，2011，33（2）：443－448．

［4］ Wenbing Tao，Hai Jin，Yimin Zhang．Color Image Segmentation Based on Mean Shift and Normalized Cuts［J］．IEEE Transactions on Systems，Man，and Cybernetics－Part B：Cybernetics，2007，37（5）：1382－1389．

［5］ 余旺盛，侯志强，宋建军．基于标记分水岭和区域合并的彩色图像分割［J］．电子学报，2011，39（5）：1007－1012．YU Wang－sheng，HOU Zhi－qiang，SONG Jian－jun．Color Image Segmentation Based on Marked－Watershed and Region－Merger［J］．Acta Electronica Sinica，2011，39（5）：1007－1012．

［6］ 陈蓉伟，刘芳，郝红侠．基于EHMM－HMT和MSW HMT的多尺度纹理图像分割［J］．软件学报，2010，21（9）：2206－2223．CHEN Rong－Wei，LIU Fang，HAO Hong－Xia．Multi－Scale Texture Image Segmentation Based on EHMMHMT and MSWHMT Models［J］．Journal of Software，2010，21（9）：2206－2223．

［7］ 徐丽燕，张洁玉，孙权森，等．结合EFD与NCut的彩色图像分割方法［J］．模式识别与人工智能，2010，23（5）：671－677．XU Li－Yan，ZHANG Jie－Yu，SUN Quan－Sen，et al．Color Image Segmentation Approach by Combining EFD and NCut［J］．Pattern Recognition and Aitificial Intelligence，2010，23（5）：671－677．

［8］ Arbeláez Pablo，Maire Michael，Fowlkes Charless，et al．Contour detection and hierarchical image segmentation［J］．IEEE Trans Pattern Anal Mach Intell，2010，33（5）：898－916．

A New Segmentation Method of Large Scale Image Datasets

Wang Jianxi，Zhang Guoping
（Software Institute，Pingdingshan University，Pingdingshan 467000，China）

：Image segmentation，as an key part in the process of image recognition，performs the important effect on the research of computer vision because the image segmentation will affect the result of image recognition．To improve the segmentation effect of large scale image datasets and realize segmentation in automatic，high speed and high quality，this paper first uses the mean shift algorithm for large scale image datasets segmentation to reduce the image size，then，according to the color of the images features，uses hierarchical clustering algorithm to perform clustering processing for the small area after segmentation in order to quickly achieve segmentation of images．The test results show that this method can effectively reduce the operation time and space complexity，improve the efficiency of image segmentation，obtain good image segmentation effect，and lay the foundation for analysis，understanding and recognition of the image．

Mean Shift Algorithm；Hierarchical Clustering Algorithm；Large Scale Image Datasets；Image Smooth；Pre－segmentation；Image Recognition

10．3969／j．issn．1002－2279．2015．04．016

TP391．4

A

1002－2279（2015）04－0061－03

河南省科技厅科技发展计划项目（134300510037）

王建玺（1981－），女，河南社旗人，硕士研究生，讲师，主研方向：模式识别、图像处理等。

2014－12－26