混沌粒子群算法在二维Fisher中的应用

混沌粒子群算法在二维Fisher图像分割中的应用叶志伟周欣（湖北工业大学计算机学院430068）摘要：针对二维Fisher算法在图像分割求解阈值时计算量大的特点，将混沌粒子群算法引入其中，利用混沌变量具有遍历性、随机性和规律性的特点有效的解决了计算效率以及传统粒子群算法的初始解质量、易陷入局部最优解的问题。通过实验证明将混沌粒子群算法引入二维Fisher图像分割算法提高了算法的速度和精度。关键词：混沌粒子群，二维Fisher，阈值，图像分割中图分类号：TP391文献标识码：A1引言图像分割是将图像中具有特殊意义的不同区域分开来，并使这些区域相互不相交且每个区域应满足特定区域的一致性条件。图像分割一直是计算机图像理解中一个十分活跃的研究领域。在图像分割中存在很多分割算法，本实验采用的二维Fisher图像分割算法，考虑了图像中目标和背景之间类间方差和类内方差在类别分离中的作用，有效地克服了经典Otsu阈值法当图像中目标的面积很小时产生的阈值“漂移”现象。由于二维Fisher算法计算量大，有学者提出了将粒子群算法结合二维Fisher图像分割算法，减少计算量，提高效率。但粒子群算法存在一些不足，主要体现在粒子群算法本身存在容易陷入局部最优的缺陷，初始解质量得不到保证。为了解决经典粒子群算法的这些不足，提出了混沌微粒群优化算法，此算法是近年来提出的一种优化算法，其基本思想是把变量从混沌空间变换到解空间，然后利用混沌变量的遍历性、随机性和规律性的特点进行搜索，混沌优化方法具有全局渐进收敛、易跳出局部极小点和收敛速度快的特点，在算法执行过程中对优秀个体混沌优化。本文用混沌粒子群算法实现二维Fisher图像分割阈值寻优。实验结果表明，基于混沌粒子群算法的图像分割方法具有较快的收敛效率和较高的收敛准确度。2混沌粒子群算法Kennedy和Eberhart于1995年提出的粒子群优化算法是一种基于群体智能的随机优化进化算法。这种算法的优点是简单易实现，并且有深刻的智能背景。经典粒子群算法的每次迭代速度和微粒位置的更新是通过以下两个公式完成的：vid(t+1)=w*vid(t)+c1rand()(pid(t)-xid(t))+c2rand()(pgd(t)-xgd(t))(1)xid(t+1)=xid(t)+vid(t+1)(2)其中w，c1，c2都是控制参数，xid和vid分别为微粒位置和速度，pgd为群体最优位置，xgd为个体最优位置。通过式(1)(2)来更新微粒。经典粒子群算法有它自身的其局限性，初始解没保障，收敛后期收敛速度慢，易陷入局部极值点。针对经典粒子群的这些不足，研究人员提出了一系列改进算法，其中混沌粒子群算法较好地弥补了经典粒子群算法的不足。一般将由确定性方程得到的具有随机性的运动状态称为混沌，呈现混沌状态的变量称为混沌变量。Logistic方程是一个典型的混沌系统：zi+1=uzi(1-zi)i=0，1，2…u∈(2,4](3)式中u为控制参量，方程(3)可以看作是一个动力学系统。u值确定后，任意初值z∈[0，1]，可迭代出一个确定的时间序列。一个混沌变量在一定范围内有如下特点：随机性，即它的表现同随机变量一样；遍历性，即它可以不重复地历经空间内的所有状态；规律性，即该变量是由确定的达代方程导出的。混沌优化方法是一种新颖的优化方法，它利用混沌系统特性来实现全局最优，而且它不要求目标函数具有连续性和可微性的性质。将混沌的思想引入粒子群算法就能够很好的克服经典粒子群算法的不足，从而更快更优地寻解。基本粒子群方法的基本步骤是：第一步：初始化粒子群；第二步：计算每个粒子的适应度；第三步：对每个粒子，比较它的适应值和它经历过的最好位置的适应值，若更好，更新当前最好位置；第四步：对每个粒子，比较它的适应值和群体所经历的最好位置的适应值，若更好，更新全局最好位置；第五步：根据式(1)和式(2)进化粒子速度和位置；第六步：如果达到结束条件（足够好的位置或最大迭代次数），则结束，否则转第二步。混沌粒子群优化算法步骤如下：混沌初始化。随机产生一个n维每个分量数值在0-1之间的向量z，根据式（3）得到n个z的值。将z的各个分量载波到优化变量的取值范围：xij=aj+(bj-aj)zij，计算目标函数，从N个初始群体中选择性能较好的m个解作为初始解，随机产生m个初始速度；根据当前位置和速度产生各个粒子的新的位置。随机产生一个n维每个分量数值在0-1之间的向量z0=(z01,z02,…z0n)；While(迭代次数k规定迭代次数)doFori-l：m按式(1)，更新自己的速度，并把它限制在vmax内；根据式(3)，产生z1，将z1的各个分量载波到混沌扰动范围[-B，B]内，扰动量△x=(△x1,△x2,…△xn)△x=-B+2Bz1j根据式（2）xid(t+1)=xid(t)+vid(t+1)x’=xid+△x计算这两个位置的适应值f和f’，若f’f，则1)(txid=x’。EndFor更新个体最优位置，群体最优位置；EndWhile输出群体最优位置。3二维Fisher图像分割算法由于传统的一维直方图仅仅反映了象素的灰度值分布，当图像的信噪比较小时，一维直方图不会出现明显的波峰和波谷，阈值较难选取。这时如果仅仅根据一维直方图进行分割则会产生严重的错误。针对这种情况，本文将使用二维Fisher准则函数法充分利用象素的邻域空间信息，对图像进行分割。定义二维直方图N(i,j)的值表示为象素灰度值f(x,y)=i且同时象素邻域平均灰度值g(x,y)=j的象素的个数，(i,j=0,1,…L)。设图像的灰度级为L(L=0,1,…,255)，f(x,y)为图像在(x,y)点的灰度值，g(x,y)为以(x,y)为中心，k×k邻域内的平均灰度值。2/2/2/2/2),(1),(kkmkknnymxfkyxg其中，1≤x≤M，1≤y≤N，M，N为图像的宽度和高度，k一般取3。无论图像的信噪比高低，二维直方图都有两个明显的波峰，选择一个合适的二维阈值(s,t)将物体和背景分割开，可以得到较好的分割效果，充分体现了二维直方图较强的抗噪声性能。将二维直方图分别在两个坐标上进行投影，分别表示为H(i)和W(j)，二维直方图Fisher准则函数的均值和方差：000(,)ji111(,)ji222000(,)ij222111(,)ij其中000*()()siisiiHiHi000*()()tjjtjjWjWj111*()()LiisLisiHiHi111*()()LjtjLjtjWjWj22000()*()siiiiHi22000()*()tjjjjWj21211()*()LiiisiHi21211()*()LjjjtjWj10()(,),0,1,...,1LjHiNijiL10()(,),0,1,...,1LiWjNijjL二维Fisher准则函数FJ(,st），则二维Fisher准则函数为：0011001122220011([,][,])*([,][,])(,)ijijijijTFijijJst(9)当(,)FJst取最大值时所对应的(,)st为最佳分割阈值：*(,)st＝ArgMax（(,)FstJ）（10）4混沌粒子群算法在二维Fisher算法中的实现为了验证本实验方法的有效性，采用本文方法对十幅图像进行分割实验。本文实验平台为VisualC++，对每幅图像分别采用穷举法，粒子群优化(PSO)，混沌粒子群优化(CPSO)对其进行比较。PSO算法中的参数设置如下w=1，c1=c2=2，xup=255，xdown=0，vmax=10，粒子规模为10。CPSO的参数和PSO算法相同，混沌控制参数u=4，B=5。十幅图像分割效果如下：(1)(2)(2)(4)(5)(6)以上六幅图像用穷举法需要搜索256*256=65536次，用PSO算法和CPSO算法搜索效率都可以得到极大提高。用PSO和CPSO两种方法分别对以上六幅图像进行优化，对每幅图像做100次实验，用两种方法得到最佳阈值迭代次数最小值，最大值和平均值的次数如下表所示。方法图像穷举法最佳阈值PSO算法迭代次数CPSO算法迭代次数最小值最大值平均值最小值最大值平均值192，932772298282023292，9021052028911388，862425276277327485，84229661052217744589，872129212146156128，13926603021301295实验结论本文提出了混沌粒子群算法优化二维Fisher图像分割算法。对经典粒子群算法进行了改进，利用了粒子群算法参数简单，易于实现的特点，加入混沌变量的遍历性，随机性和初值敏感性的优势，有效得对二维Fisher算法进行了优化，极大提高了搜索效率。从实验结果可以看出，经典粒子群算法和混沌粒子群算法都能够找到最优阈值，混沌粒子群算法比经典粒子群算法具有更高的效率。混沌粒子群算法在图像分割算法中具有广泛的应用前景。参考文献[1]LinyiLiandDerenLi,“Fuzzyentropyimagesegmentationbasedonparticleswarmoptimization”,ProgressinNaturalScienceVolume18,Issue9,10September2008,Pages1167-1171[2]Peng-YengYin,“Multilevelminimumcrossentropythresholdselectionbasedonparticleswarmoptimization”,AppliedMathematicsandComputationVolume184,Issue2,15January2007,Pages503-513[3]LongLiu,JunSun,DongxuZhang,GuochengDu,JianChen,WenboXu.,“CultureconditionsoptimizationofhyaluronicacidproductionbyStreptococcuszooepidemicusbasedonradialbasisfunctionneuralnetworkandquantum-behavedparticleswarmoptimizationalgorithm”,EnzymeandMicrobialTechnology,Volume44,Issue1,6January2009,Pages24-32[4]YuhuiShiandRussellEberhart,“AModifiedParticleSwarmOptimizer”,0-7803-4869-91981998IEEE[5]ZhouXian-cheng,ShenQun-tai,LIULi-mei,“Newtwo-dimensionalfuzzyC-meansclusteringalgorithmforimagesegmentation”,J.Cent.SouthUniv.Technol.(2008)15:882−887[6]GAOShang,YANGJing—Yu,“ResearchonChaosParticleSwarmOptimizationAlgorithm”,modeidentifyandartificialintelligence,April2006,Pages267-270[7]C.Praveen,R.Duvigneau,“LowcostPSOusingmetamodelsandinexactpre-evaluation:Applicationtoaerodynamicshapedesign”,ComputerMethodsinAppliedMechanicsandEngineering