基于K均值聚类和粒子群优化的多核SVM图像分割①

吴迪,戴芳,郭文艳,胡胜(西安理工大学 理学院,西安 70054)(西安交通大学 机械制造系统工程国家重点实验室,西安 70049)



基于K均值聚类和粒子群优化的多核SVM图像分割①

吴迪1,戴芳1,郭文艳1,胡胜2
1(西安理工大学 理学院,西安 710054)
2(西安交通大学 机械制造系统工程国家重点实验室,西安 710049)

摘 要:图像分割是图像理解和计算机视觉的重要内容.针对单核SVM在进行图像分割过程中不能兼顾分割精度高和泛化性能好的问题,提出一种基于K均值聚类和优化多核SVM的图像分割算法.该算法首先运用K均值聚类算法自动选取训练样本,然后提取其颜色特征和纹理特征作为训练样本的特征属性,并使用其对构造的多核SVM分割模型进行训练,最后用粒子群优化算法对多核核参数、惩罚因子以及核权重系数联合寻优,使生成的多核SVM具有更好的分割性能.实验结果表明,本文方法在有效提取图像目标细节的同时,获得了更高的分割精度,与基于单核的SVM分割模型相比,具有更强的泛化能力.

关键词:图像分割; 核函数; 支持向量机; 粒子群优化; K均值聚类

图像分割是研究如何有效地将图像分割成各具特性的区域并提取目标区域,分割质量的好坏很大程度上决定着后续的图像分析和图像理解的效果[1,2].分割的实质就是对图像的像素进行分类,选择分类性能优良的智能算法对于图像分割具有重要意义.

SVM 在解决小样本、高维、非线性模式分类问题上具有良好的性能,有效解决了过学习、维数灾难等问题,具有较好的泛化能力[3-6].Yu等[7]利用SVM 的特性提出了改进SVM 算法,通过减少训练样本冗余而保留有效的支持向量,在显著减少耗时的同时有效保留了分割精度.Wang等人[8]则首先提取样本点的颜色特征和纹理特征,利用样本点的特征属性训练SVM ,然后运用训练好的 SVM 对彩色图像进行分割,由于文中仅采用局部高斯核函数且其相应的参数为人为设定,其泛化性能和分割精度均有待提高.Liu 等[9]提出了一种集成多尺度技术、混合模型和 SVM等方法的SAR 图像分割算法,其效果优于直接使用SVM分类器进行分割效果.Yang等[10]提出运用最小二乘支持向量机对彩色图像进行分割,该方法自动选取训练样本并提取其颜色特征与纹理特征,问题的关键在于支持向量机核函数的选择以及核参数的确定.

相关研究表明,在运用 SVM 进行图像分割时,其核函数的设计和选择尤为重要,核函数的选取和新核函数构造的好坏对SVM图像分割的效率和泛化性能产生巨大影响,且训练样本选取的方式也会影响SVM图像分割的质量.现有的基于 SVM方法分割图像核函数多为单核核函数,一定条件下表现出一定的学习和泛化能力.但 SVM 分割图像中的核函数构造和选择及相应参数的设定至今也没有一套完善的理论,通常可用的几种基本形式的核函数具有不同的映射特性,在不同的应用场合表现出很大的性能差异,运用SVM 方法分割图像时只采用单个核函数并非合理.鉴于此,为了克服SVM 算法在图像分割应用中的局限,提高分割精度.本文提出一种基于K均值聚类和优化多核SVM的彩色图像分割算法.通过粒子群算法对多核SVM各参数进行联合寻优,获取最优的多核支持向量机分类模型.同时,为了有效获取图像的特征信息,降低SVM模型的复杂度,自动选取训练样本,提取训练样本的颜色特征和纹理特征并将它们融合成特征向量集,基于特征向量集用优化的多核SVM模型对原图像进行分割.最后通过实验验证了优化多核SVM 图像分割算法的有效性.

1　K均值聚类提取图像特征

训练样本的选择在很大程度上影响了SVM的分类性能,传统的训练样本选取是随机选取降低了图像分割的自适应性.本文运用K-均值聚类自动提取SVM 的训练样本,将初始聚类数目设定为两类,即目标和背景.K均值聚类算法具体步骤如下:

1)设定聚类数目C={ck|k=1,2,…,c}(本文c=2),初始类簇中心δk(k =1,2)以及误差上界ξ; 找到距离设定的聚类中心最近的像素yi( i=1,2,…,n),并将该像素分配到该类中;

2)修正类簇中心: 计算每个类簇像素的均值,根据类簇的均值更新类簇中心,获得新的类簇中心σk(k=1,2,…,c);

自动选取训练样本之后,本文提取训练样本的六种特征属性,其中包括四种颜色特征: RGB颜色空间的 r,g,b 通道的像素值和亮度 i ; 两个纹理特征参量: 角二阶矩(ASM)和对比度.将其作为输入向量来训练多核核函数 SVM 分类器.

2　优化多核 SVM 图像分割方法

2.1SVM 多核核函数

在运用 SVM 对彩色图像进行分割时,核函数的选择和核参数的确定对数据的映射以及最终的决策效果发挥着至关重要的作用.通过引入核函数,可极大的提高机器学习的非线性处理能力,同时也保持了学习机器在高维空间中的内在线性,从而使得分割效果更好.

常见的核函数主要分为全局核函数和局部核函数两大类[11-13].而多项式核函数和高斯核函数分别作为全局核和局部核的典型代表成为 SVM 的核函数首选[14].图1给出不同类型的核函数在给定参数情形下函数值随测试点x的变化曲线.

图1　不同核函数的变化曲线

由图1 可知,对于任意单核函数,通过选择不同的参数,其呈现出不同的尺度效应.多项式核函数具有全局特性,泛化性能较强; 高斯核函数具有局部性,学习能力更优.而基于多核学习的方法的多核模型是一类灵活性更强的学习模型.利用多核代替单核,能增强决策函数的可解释性,并能获得比单核模型更优的性能.它同时具备两个单核的优点,即具有更好的学习能力和泛化能力.

为了验证多核核函数 SVM 图像分割相对于单核核函数 SVM 的优势,本文分别选取多项式核(全局核)和径向基核(局部核)进行凸组合,如下所示:

其中,Knew为新构造的多核函数,KPoly和KRbf分别为多项式核和径向基核,λi(i=1,2)为权重系数,满足λi≥0且λ1+λ2=1.

2.2基于粒子群的多核SVM参数优化算法

在选定SVM的核函数类型后,其权重系数和核参数的确定也会影响图像分割的效果.核参数或惩罚因子C选择不合理,就会降低SVM的图像分割精度; 而核参数s和权重系数l越小,响应区间越窄,得到的最优分类面经验风险也越小,但是结构风险增大,而且容易出现过拟合现象,导致SVM 的图像分割性能降低.所以多核核参数的选取对SVM图像分割性能起决定性作用.而粒子群优化算法[15]利用位置和速度的概念,避免了遗传、交叉和变异等操作,具有变量少、效率高等优点,被广泛应用于智能优化领域.为此本文选择粒子群算法对这几类参数进行联合优化,构建优化多核SVM分类器.

本文PSO粒子编码为(d,σ,C,λ1),其中d,σ,C分别为多项式核和径向基核的核参数,λ1为多项式核的权重,径向基核权重λ2=1-λ1.基于粒子群的多核SVM参数优化算法流程如下图2 所示.

图2　基于粒子群的多核SVM参数优化算法流程

2.3基于K均值聚类和优化多核SVM的图像分割

本文提出的图像分割算法分为三个处理阶段: 第一个阶段是基于K均值聚类训练样本的自动选取,将像素点分为前景和背景两类并提取其特征属性; 第二个阶段是优化多核 SVM 模型; 第三个阶段是基于优化多核 SVM 的图像分割.采用本文算法进行图像分割的流程如图3所示.

3　实验结果与分析

本文的所有实验均在软件 MATLAB R2012b 中进行的,运行环境为 CPU 3.2GHz 内存 2G,硬盘500G,操作系统是Windows 7.为了验证本文优化多核方法的有效性,同时增加分割的难度,以保证算法评价的实用性和客观性.分别选取三幅复杂背景下的图像进行实验,其图像尺寸大小为200*200.由于均是在自然光的条件下采集,部分反光呈白色斑点,且表面粘有杂质,它们之间呈现出目标边界模糊、目标不连续和目标灰度不均匀等特点.

图3　基于K均值聚类和粒子群优化的多核SVM图像分割算法流程

3.1训练样本选取图像分割效果对比

本文为了避免人工方法选取和标注训练样本的主观性不足,运用K均值聚类自动选取一定数目的训练样本,之后提取其特征属性用来训练优化的多核SVM.实验中多核 SVM 的参数通过粒子群算法进行寻优,不敏感系数e取0.1,PSO 基本参数设置如下:种群规模数20,最大遗传代数100,加速度因子C1= C2= 0.1,其迭代效果如下图4 所示.经过5次迭代时多核SVM达到最优效果.此时迭代得最优的多核SVM参数为d =2,C =5.0,σ= 1.8,λ1=0.6.将此优化多核的SVM模型对图像进行分割,实验效果如图 5所示.

图4　多核 SVM 参数寻优结果

图5　训练样本不同选取方式的优化多核SVM图像分割效果

由图5图可以看出,当训练样本人工选取时,其分割结果受主观因素影响很大,误将部分目标当作背景,将部分背景当作目标,导致分割结果不佳.而自动选取训练样本结合优化多核SVM分割方法则几乎精确将所有的目标均分割出来,分割结果既突出了目标,又保留了局部细节,获得了较理想的效果.

3.2不同核函数的SVM 图像分割效果对比

同时为了有效验证优化多核 SVM 的彩色图像分割相对于单核SVM的优越性,在相同的实验条件下分别选取多项式核(核参数=2)、径向基核(核参数=5.0,=1.8)进行效果比对,分割效果如图 6 所示.

图6　不同核函数的SVM 图像分割效果

如图6所示,原始图像中(b)和(c)的目标较多且分布零散,部分图像由于视觉较远看起来非常模糊且(b)图中花朵正下方的阴影部分区域颜色与背景和目标差别都不大,很容易误认为是目标,(d)图中左下角的花朵目标视觉极其模糊且与背景色差小,容易误判.在基于单核SVM模型的分割结果中将这些细节错分,分割效果不理想,其效果如图6中间两幅所示.而本文基于K均值聚类结合多核SVM的分割方法(见b3,c3 和d3所示)很好的表征了这些目标区域,精确的提取了图像目标,分割结果在突出了目标的同时又保留了局部细节,更加符合人们的主观分割效果.为了进一步分析实验结果,选取分割精度和分割时间作为衡量图像分割性能优劣的指标,其比较结果如表1所示.

表1　不同核函数支持向量机的分割精度和分割效率对比

由表1可以看出,对于给定的待分割图像,多核SVM 在训练精度上与单核核函数SVM 相当,但是在分割精度方面却有了一定幅度的提高.随着待分割图像的复杂度逐渐增加,三种核函数 SVM 算法的图像分割精度都有所降低,但是多核SVM 的降低幅度最小,说明了多核 SVM 相对于单核 SVM 具有更强的泛化能力.同时由于多核函数包含了局部核和全局核的综合特性,其算法的图像分割时间相对于其他两种单核均有所增加.

4　结语

本文提出了一种基于K均值聚类和优化多核SVM的彩色图像分割算法.该算法充分考虑全局核和局部核函数的优势,通过加权组合形成多核SVM并运行粒子群算法对其参数进行寻优,获取优化多核SVM,然后将提取的图像特征作为分类器的输入对其进行分割,同时训练样本的自动选取为多核SVM分割提供了良好的输入特征,克服了人工选取样本的主观性.实验结果表明,利用本文方法可以获得较理想的分割效果,相比单核支持向量机具有更高的分割精度和泛化性能.

参考文献

1Cheng HD,Jiang XH.Sun H,et al.Color image segmentation: Advances and prospects.Pattern Recognition,2001,34(12): 2259–2281.

2许新征,丁世飞,史忠植,等.图像分割的新理论和新方法.电子学报,2010,38(2):76–82.

3Vapnik V.The Nature of Statistical Learning Theory.2nd ed.,Springer Berlin,2000.

4Yu H,Chang CC.Scenery image segmentation using support vector machines.Fundamenta Informaticae,2004,61(3): 379 –388.

5徐海祥,喻莉,朱光喜,等.基于支持向量机的磁共振脑组织图像分割.中国图象图形学报,2006,10(10):1275–1280.

6黄建灯,陈庆全.基于支持向量机的红细胞彩色图像分割.计算机系统应用,2009,18(1):35–38.

7Yu Z,Wong HS,Wen G.A modified support vector machine and its application to image segmentation.Image and Vision Computing,2011,29(1): 29–40.

8Wang XY,Wang QY,Yang HY,et al.Color image segmentation using automatic pixel classification with support vector machine.Neurocomputing,2011,74(18): 3898–3911.

9 Liu T,Wen XB,Quan JJ,et al.Multiscale SAR image segmentation using support vector machines.Congress on Image and Signal Processing,2008.CISP’08.IEEE.2008,3.706–709.

10Yang HY,Wang XY,Wang QY,et al.LS-SVM based image segmentation using color and texture information.Journal of Visual Communication and Image Representation,2012,23(7): 1095–1112.

11Stricker MA,Orengo M.Similarity of color images.IS&T/SPIE’s Symposium on Electronic Imaging: Science & Technology.International Society for Optics and Photonics.1995.381–392.

12张学工.关于统计学习理论与支持向量机.自动化学报,2000,26(1):32–42.

13Cristianini N,Shawe-Taylor J.An introduction to support vector machines and other kernel-based learning methods.Mining Yor12 Conference,2000,32(8): 1–28.

14汪洪桥,孙富春,蔡艳宁等.多核学习方法.自动化学报,2010,36(8):1037–1050.

15Kennedy J.Particle swarm optimization.Encyclopedia of Machine Learning.Springer US.2010: 760–766.

Method for Image Segmentation Based on Optimized Multi-Kernel SVM and K-means Clustering

WU Di1,DAI Fang1,GUO Wen-Yan1,HU Sheng2
1(School of Science,Xi’an University of Technology,Xi’an 710054,China)
2(State Key Laboratory for Manufacturing Systems Engineering,Xi’an Jiaotong University,Xi’an 710049,China)

Abstract:Image segmentation is an important topic in image understanding and computer vision.When support vector machine (SVM)is used for image segmentation,the design of its kernel and selection of the parameters directly affect the segmentation effect.Considering the problem that SVM based on single kernel could not keep the balance between the segmentation accuracy and generalization performance,an image segmentation algorithm using optimized multi-kernel SVM (OMKSVM)based on K-means clustering was proposed in this paper.According to the multi-kernel learning theory,the new multi-kernel is constructed by a linear combination of single kernels.Firstly,the K-means clustering algorithm was applied to obtain the training samples for MKSVM automatically.Then color and texture features were extracted from the image as attributes of training samples of MKSVM,Particle Swarm Optimization (PSO)algorithm was employed to optimize the kernel parameters,the weight coefficient and the punishment coefficient of SVM simultaneously.Finally the OMKSVM was obtained to segment image.Three groups of complex color image were selected to verify the correctness of the proposed method.The results demonstrate that our method can segment the color images effectively,and has stronger generalization ability comparing with the single kernel SVM-based method.

Key words:image segmentation; kernel function; support vector machine (SVM); particle swarm optimization (PSO); K-means clustering

基金项目:①国家自然科学基金(91120014);陕西省教育厅科研计划(12JK0534)

收稿时间:2015-07-18;收到修改稿时间:2015-09-08