时颢,赖惠成,覃锡忠
新疆大学信息科学与工程学院,乌鲁木齐 830046
粒子群与K均值混合聚类的棉花图像分割算法
时颢,赖惠成,覃锡忠
新疆大学信息科学与工程学院,乌鲁木齐 830046
我国棉花种植地域广阔,所需棉花采摘劳动力极大,随着机器人在农业生产过程中的逐步应用,研究基于图像处理的采棉机器人技术具有相当大的实用价值和现实意义。棉花分割是采棉机器人视觉系统的关键技术之一,是采棉机器人中棉花匹配、三维重构技术的基础。迄今关于棉花图像分割的相关研究有:韦皆顶[1]等选取HSV模型中与亮度无关的S通道作为棉花图像的特征,一定程度去除了图像明暗变化对分割效果的影响,但由于分割模型过于简单,稳定性不高;王勇等[2]根据棉花与背景的色差信息,提出利用(R-B)、(B-G)的差值进行分割;王玲[3]研究了不同颜色空间下的棉花分割,发现在HIS和Lab颜色空间经阈值分割后噪声较低;董建明[4]提出了微粒群算法(PSO)优化最小误差分割算法,图像分割的效果和速度都得到了一定的提高。前人的这些方法算法复杂度低,但受光照和阴影的影响较大,难以准确分割各种复杂情况下的棉花。本文在上述研究的基础上提出了在YCbCr颜色空间下,利用粒子群优化(PSO)和K均值混合聚类算法进行分割,得到了较好的分割效果。
2.1 颜色空间的选择
在RGB颜色空间中,由于R、G、B分量之间有很高的相关性,对同一颜色属性,在不同光照条件下,R、G、B值很分散,色彩表示不均匀,两个颜色的差异不适合用该颜色空间中的两点之间的距离表示。HSV颜色空间能将亮度分量,但从RGB颜色空间转换到HSV颜色空间需要开方、反三角函数操作,复杂度高,所需计算量大,并且在亮度值和饱和度较低的情况下,采用HIS或者HSV颜色空间计算出来的H分量是不可靠的。YCbCr颜色空间由亮度分量Y,蓝色色度分量Cb和红色色度分量Cr组成。从RGB颜色空间到YCbCr颜色空间的转换公式如下:
基于YCbCr颜色空间中色度分量和亮度分量相互独立、YCbCr颜色空间与RGB颜色空间存在一种线性变换关系,不同亮度下,在YCbCr空间内亮度范围的变化量很大,而色度范围的变化量很小,有利于光照变化图像的处理,因此选择YCbCr颜色空间[5]。
2.2 粒子群算法介绍
粒子群算法(PSO)是基于群体智能理论的优化算法,通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。与进化算法类似[6],PSO先将系统初始化为一组随机解,然后通过迭代搜寻最优值,但是其采用的速度-位移模型操作简单,避免了复杂的遗传操作,它特有的记忆使其可以动态跟踪当前的搜索情况调整其搜索策略。由于每代种群中的解具有“自我”学习提高和向“他人”学习的双重优点,从而能在较少的迭代次数内找到最优解。
在PSO算法中,先将系统初始化为一组随机解,然后通过迭代搜寻最优值。粒子群在一个n维空间中搜索,其中的每个粒子所处的位置都表示问题的一个解。粒子通过不断调整自己的位置X来搜索新解。每个粒子都能记住自己搜索到的最好解,记做Pid,以及整个粒子群经历过的最好的位置,即目前搜索到的最优解,记做Pgd。在迭代过程中,微粒第d维速度与位置的迭代式为:
式中,ω为惯性权值,η1,η2为飞向自身最好位置方向和全局最好位置的学习因子,rand()为随机数生成函数。
从式(2)和式(3)可以看出,粒子的移动方向由三部分决定,自己原有的速度Vid,与自己最佳经历的距离(Pid-Xid)和与群体最佳经历的距离(Pgd-Xid),并分别由权重系数ω,η1和η2决定其相对重要性[7-9]。
2.3 K-means算法介绍
K均值聚类算法[10-11]是通过找到特征空间中像素值的空间聚类,并把每一个像素划分到不同的聚类中来实现图像的分割。假设一组数据包含K个聚类,其中每个聚类包含m个点,若聚类中心为Zk,则总的类间离散度和:
其中,Xi为d维模式向量,d(Xi,Zk)为样本到对应聚类中心距离,JC为各类样本到对应聚类中心距离的总和。这里d(Xi,Zk)为欧式空间的距离,即d(Xi,Zk)=‖Xi-Zk‖。而K均值聚类算法通过迭代,使总的类间离散度JC最小,即使每个类内距离尽可能小,而类间距离尽可能大。
K均值聚类算法的具体步骤如下:
(1)随机选取K个聚类中心。
(2)根据每个聚类对象的均值,计算每个像素到K个聚类中心的距离,找出最小距离,并且把该像素归为该聚类中心的类别。
(3)计算每个有变化聚类的均值,重新调整K个聚类中心。
(4)判断新的聚类中心是否和上次结果相同,若不同返回步骤(2),直到每个聚类不再发生改变为止。
K均值聚类算法因其算法简单、收敛速度快等优点,在数据挖掘、图像分割、模式识别、特征提取等诸多领域得到了广泛应用,然而传统的K均值算法存在两个固有的缺点:对初始值敏感,易陷入局部最优,PSO优化算法的出现为解决这一问题提供了新的思路。通过对以往文献分析发现,如何能充分利用PSO的全局搜索能力以及K均值算法精确的局部解搜索能力,且在提高解精度的同时加快算法的收敛速度是提高PSO+K均值混合聚类算法的关键所在。
3.1 粒子群优化算法
由文献[12]知,如果ω随算法迭代的进行而线性减小,将显著地改善算法的收敛性能[12-13]。初始化时设置最大加权系数ωmax,最小加权系数ωmin和算法最大迭代次数runMax,run为当前迭代次数,则有:
3.2 确定K均值算法操作时机
群体适应度方差反映的是粒子群中所有粒子的“收敛”程度[14]。σ2越小,则粒子群趋于收敛;反之,适应度不同粒
为了将PSO算法和K均值聚类算法有机结合,首先要确定K均值算法的操作时机。事实上当PSO算法在进行全局随机搜索阶段时,不需进行K均值算法,这样可以最大程度地利用PSO算法向着全局解子空间逼近,加快算法的收敛速度。当PSO算法进入收敛状态,此时引入K均值算法可以提高解的局部搜索能力,加快算法的收敛速度。于是真正实现PSO算法与K均值算法的有机结合的关键是确定PSO算法何时收敛。而PSO算法在收敛的情况下,粒子群中各粒子的位置一致即各粒子适应度相同。因此,研究PSO中所有粒子适应度的整体变化就可以跟踪粒子群的状态,判断算法是否收敛。
设粒子群的粒子数目为n,fi为第i个粒子的适应度,favg为粒子群目前的平均适应度,粒子群的群体适应度方差σ2的定义如下:子群则处于随机搜索阶段。因此,当群体适应度方差小于某一个阈值时,说明PSO算法进入收敛阶段这时开始执行K均值进行局部解精确搜索,这样既提高了混合聚类算法全局解搜索性能,加快了收敛速度,同时解的精度也随之增加。
3.3 算法结合具体操作流程
本文利用粒子群适应度方差来确定K均值算法操作时机,实现PSO算法与K均值算法的有机结合,增强算法局部搜索能力的同时加快了算法的收敛速度。
下面是算法的具体步骤:
(1)种群的初始化。在初始化粒子时,先将每个样本随机指派为某一类,作为最初的聚类划分,并计算各类的聚类中心、粒子的适应度,初始化粒子的速度,设置最大加权系数ωmax,最小加权系数ωmin和最大迭代次数runMax。
(2)对每个粒子,比较它当前位置的适应度值和它经历过的最好位置的适应度,如果更好,更新Pid。
(3)对每个粒子,比较它当前位置的适应度值和群体所经历的最好位置的适应度值,如果更好,更新Pgd。
(4)根据式(2)和式(3)调整粒子的速度和位置。
(5)根据式(6)判断当前粒子群是否到达收敛状态,若群体适应度方差σ2小于阈值,则粒子进入K均值优化阶段,否则转步骤(2)。
(6)K均值优化。
对于新一代粒子,按照以下的K均值算法进行优化:
①根据粒子的聚类中心编码,按照最近邻法则,来确定对应该粒子的聚类划分。
②按照聚类划分,计算新的聚类中心,更新粒子的适应度值,取代原来的编码值。由于K均值具有较强的局部搜索能力,因此引入K均值优化后的粒子群算法的收敛速度可以大大提高。
③如果达到结束条件(足够好的位置或最大迭代次数),则结束,否则转步骤②。
在使用粒子群算法的过程中,在第(6)步对新一代个体进行重新划分类别时,有可能会有空的聚类出现。如果出现空的聚类,则随机地从其他某个非空的聚类中取出距离聚类中心最远的模式向量,将该向量放入空聚类,重复这个过程,直到划分中没有空聚类为止。
本算法采用粒子群算法有较强的全局搜索能力的优势确定棉花图片的聚类中心,再根据K均值收敛速度快,局部搜索能力强的特点对图像进行分割,可以较好地解决粒子群算法收敛速度慢及K均值算法对初始聚类中心敏感的缺点。
3.4 连通域面积去噪
粒子群与K均值混合聚类后的图像存在着将背景多余信息错误分割出来的过分割区域,鉴于这部分误差在二值图中的面积相比于目标区域要小得多且不连通,因此本文采用连通域去噪的方法[15]。首先获取分割后图像中每一块白色连通区域的面积,通过统计确定一个阈值T,将面积小于阈值T的连通区域去除。为了去除棉花内部的噪声,将上述步骤得到的二值图像进行反色处理,再使用区域标记法去除噪声,最后再做一次反色处理得到分割图像。
为了评价分割效果,本文分别进行了两组对比,第一组为在YCbCr空间下将PSO聚类算法与本文算法进行比较,仿真后的分割图如图1所示。
图1 YCbCr空间下不同算法对比图
可以看出,PSO聚类算法在YCbCr颜色空间下虽然能完整地分割出棉花,但存在比较大的噪声,尤其是细节部分无法准确将棉荚、棉叶分割为背景,通过连通域面积去噪无法有效去除跟棉花相连处的噪声。
第二组为本文提出的粒子群与K均值混合聚类算法分别在HSV颜色空间和YCbCr颜色空间下进行分割对比,并选取棉花在阴影及强光照条件下的典型图像,仿真后的分割图如图2、图3所示。
图2 棉花在阴影条件下的情况
图3 棉花在强光照射下的情况
通过对比可知,自然条件下的棉花图片转换到HSV颜色空间下分割没办法很好地解决光照带来的影响,尤其是强光照下分割误差会更大,并且RGB颜色空间到HSV颜色空间的转换较复杂,影响分割效率。
由此可知,粒子群与K均值混合聚类算法在YCbCr颜色空间下能有效地解决这些问题,将棉荚、棉叶成功分割为背景,在强光照和阴影情况下都能对棉花图片准确地分割并很好地保留了细节特点。
YCbCr空间将亮度与色差分离并与RGB空间存在线性转换关系,本文在YCbCr颜色空间下对棉花图片进行粒子群与K均值混合聚类分割,能够有效克服光照、阴影带来的影响,实现了全局解搜索能力与收敛速度的平衡,其分割稳定性、分割精度优于传统PSO聚类的分割方法,可以将各种复杂环境下的棉花图像准确有效地分割,为采棉机器人自动化采摘奠定基础。
[1]韦皆顶,费树岷,汪木兰,等.基于HSV颜色模型的自然场景下棉花图像分割策略研究[J].棉花学报,2008,20(1):34-38.
[2]王勇,沈明霞,姬长英.采摘期成熟棉花不同部位颜色识别分析[J].农业工程学报,2007,23(4):183-185.
[3]王玲,王萍,陈兵林,等.基于颜色阈值的田间籽棉图像分割技术[J].作物学报,2010,36(3):503-507.
[4]董建明,胡觉亮.基于PSO算法的图像分割方法[J].计算机工程与设计,2006(18).
[5]刘金帅,赖惠成,贾振红.基于YCbCr颜色空间和Fisher判别分析的棉花图像分割研究[J].作物学报,2011,37(7).
[6]刘成洋,阎昌琪.粒子群遗传算法及其应用[J].核动力工程,2012,33(4).
[7]周驰,高海兵.粒子群优化算法[J].计算机应用研究,2003(12):7-12.
[8]高金雍,唐红梅.一种基于改进PSO和FCM的图像分割算法[J].河北工业大学学报,2011,40(6).
[9]张新娟,雷秀娟.改进PSO算法在二维最佳阈值图像分割中的应用[J].计算机工程与应用,2011,47(26):207-209.
[10]王易循,赵勋杰.基于K均值聚类分割彩色图像算法的改进[J].计算机应用与软件,2010,27(8):127-130.
[11]LiM J,Ng M K.Agglomerative fuzzy K-means clustering algorithm with selection of number of clusters[J].IEEE Τransactions on Knowledge and Data Engineering,2008,20(11).
[12]吕振肃,侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004,32(3).
[13]程万盛,臧希哲.面向Otsu阈值搜索的PSO惯性因子改进方法[J].光学精密工程,2008,16(10).
[14]陈茂源,吴国平.基于PSO改进的OΤSU图像分割方法[J].微计算机应用,2009(12).
[15]孙建成,曾培峰.二值图像的区域标识与噪声去除[J].天津工业大学学报,2006,25(1).
SHI Hao,LAI Huicheng,QIN Xizhong
School of Information Science and Engineering,Xinjiang University,Urumqi 830046,China
Image segmentation of cotton is the key step of the cotton picker robot vision system.In the complex environment of the cotton fields of the strong light,shadow,etc.accurately and effectively splitting cotton,helps to determine its position in threedimensional space.In accordance with the characteristics of cotton pictures,a method of Particle Swarm Optimization(PSO)and K-means hybrid clustering in YCbCr color space is proposed.Τhis approach reinforces the exploitation of global optimum of the PSO algorithm.In order to avoid the premature convergence and speed up the convergence,traditional K-means algorithm is used to explore the local search space more efficiently dynamically according to the variation of the particle swarm’s fitness variance.Τhe experiment results show that this method can segment cotton image with the complex background,and is more effective than the traditional PSO and K-means algorithm.
cotton segmentation;YCbCr color space;K-means algorithm;Particle Swarm Optimization(PSO)algorithm
棉花分割是采棉机器人视觉系统的关键步骤,在强光照、阴影等复杂的棉田环境下准确有效地分割棉花,有助于确定其在三维空间的位置。针对棉花图片的特点,提出在YCbCr颜色空间下,采用粒子群(PSO)和K均值混合聚类算法,提高了聚类算法的全局搜索能力,根据群体适应度方差来确定K均值聚类算法操作时机,增强算法局部精确搜索能力的同时缩短了收敛时间。通过对棉田环境中拍摄图像的分割实验表明:本方法对在阳光直射及阴影等干扰条件下的棉花图片也能准确分割,效果优于传统PSO和K均值算法。
棉花分割;YCbCr颜色空间;K均值算法;粒子群算法
A
ΤP391
10.3778/j.issn.1002-8331.1303-0397
SHI Hao,LAI Huicheng,QIN Xizhong.Image segmentation algorithm of cotton based on PSO and K-means hybrid clustering. Computer Engineering and Applications,2013,49(21):226-229.
新疆维吾尔自治区科学基金资助项目(No.2011211A010)。
时颢(1988—),女,硕士研究生,主要研究方向为图像处理;赖惠成(1963—),男,教授,主要研究方向为通信与信息系统,图像处理等;覃锡忠(1964—),副教授,硕士生导师,主要研究方向为信号与信息处理。E-mail:13579410640@163.com
2013-03-26
2013-05-06
1002-8331(2013)21-0226-04
CNKI出版日期:2013-05-29http://www.cnki.net/kcms/detail/11.2127.ΤP.20130529.1519.010.html