基于改进粒子群算法的多阈值图像分割_武燕

1、Microcomputer Applications Vol. 27, No.5, 2011 技术交流 微型电脑应用 2011年第27卷第5期 ·59·文章编号:1007-757X(201105-0059-03基于改进粒子群算法的多阈值图像分割武 燕,张 冰摘 要:提出了一种改进的粒子群算法,在初始化种群时采用相对基学习原理,以获得较优的初始候选解;在后期迭代过程中引入扩张模型,使粒子不易陷入局部极小值点,并将其用于多阈值图像分割。由最大熵阈值法得到所要优化的目标函数,用改进的粒子群算法对其进行优化,使其能够准确并迅速的得到分割的最佳阈值组合,并用该阈值组合对图像进行分割。

2、将此分割结果与遗传算法的多阈值分割结果相比较可以看出,该算法可更为准确快速的实现图像分割。关键词:粒子群优化算法;相对基学习;扩张模型;多阈值;图像分割中图法分类号:TP301 文献标志码:A0 引 言图像分割是目标识别的首要和关键步骤,其目的是将背景与目标分离,为计算机视觉的后续处理提供依据。图像分割的方法主要包括阈值法、边缘检测等1。其中,阈值分割因其快速简单使其成为图像分割中最基本最常用的方法。常用的阈值法有最大熵阈值法、最大类间方差阈值法及最小误差阈值法等。最大熵阈值法的原则使得总熵最大。所以确定阈值是阈值分割的关键,根据阈值的个数,图像阈值分割可以分为单阈值分割和多阈值分割。多阈值分

3、割问题可转化为一系列单阈值分割问题来进行解决,但此需要在全灰度范围内搜索一个最佳门限的组合,耗时较多,难于实际应用。为了简化计算,可以利用遗传、免疫等进化算法来搜索最佳阈值2。而在本文中,将改进的粒子群算法引入图像分割中的多阈值选择,对最大熵阈值法(ME进行了优化,使其能够准确并迅速地找到图像分割的最佳阈值,对图像进行多阈值分割。1 基于最大熵的多阈值图像分割最大熵阈值法的基本依据是使得图像中目标与背景分布的信息量最大,即通过测量图像灰度直方图的熵,找出最佳阈值。对于灰度范围在0,1L 的图像,其熵为:10ln L i ii H p p = (1i p 为灰度级i 出现的概率。对于灰度范围为0

4、,1,.,1L 的图像,设阈值t 将图像分成两部分, (/,(0(1i p h i N i L =,其中(h i 表示灰度值为i 的像素个数,N 表示图像中像素的总数。则图像的熵01(H t H H =+的最佳阈值t 使得总熵取最大值。其中,100t i i P =,10000ln t i i i P P H =,和11L i i t P =,1111ln L i i i t P P H =。扩展到多阈值分割,假设有c 个阈值,则图像的熵为: 1201(,.,.c c H t t t H H H =+ (2 其中1100t i i P =,110000ln t i i i P P H =; 2

5、111t i i t P =,211111ln t i i i t P P H =;1c L c i i t P =,11ln c L i i i t c c P P H =;找出最佳阈值c 维向量12,.,c t t t 使得熵最大。 这样,利用最大熵阈值法,图像的多阈值分割的阈值求解问题就可简单归纳为最佳阈值12,.c t t t 的优化问题。 2 改进的粒子群算法 2.1 粒子群算法 粒子群优化算法是由Eberhart 和Kennedy 共同提出的一种进化计算算法3,4,这种算法源于对鸟群捕食行为的研究。粒子群算法中每个粒子就是解空间中的一个可行解,它是根据粒子自己的飞行经验以及同伴的飞

6、行经验来调整自作者简介:武燕(1986-,女,江苏省常州市武进区,硕士研究生,研究方向:问信号处理理论与技术,212003;张冰(1967-,女,江苏省无锡市,博士,教授、硕士研究生导师,研究方向:控制理论与控制工程、信号与信息处理、智能控制,212003Microcomputer Applications Vol. 27, No.5, 2011 技术交流 微型电脑应用 2011年第27卷第5期 ·60·身的飞行。每个粒子在飞行过程中所经历的最好位置,叫做个体极值(pbest 。整个群体所经历的最好位置,叫做全局极值(gbest 。每个粒子都可以通过上述两个极值来不断更新自

7、己,从而产生新一代群体。粒子群算法的优势在于简单、易实现且参数较少,现已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其它遗传算法的应用领域。如果粒子的群体规模为M ,则第(1,2,.,i iM =个粒子的位置可表示为i X ,它所经过的“最好”位置记为pbest i ,速度用i V 表示,群体中“最好”粒子的位置的索引号用g 表示,那么粒子i 将根据下面的公式来更新自己的速度和位置:(1(i i i V V c RAND pbest i X =×+××(2(i c rand gbest g X +×× (3i i i X X V =+

8、(4其中,1c ,2c 为常数,称为学习因子;(RAND 和(rand 是0,1上的随机数;为惯性权重。由式(3和式(4可知,越大,微粒的飞行速度越大,微粒将以比较大的步长进行全局探测;越小,微粒的速度步长越小,微粒趋于进行精细的局部搜索。所以,在搜索过程中可以对进行动态调整:max minmax max iter iter =×。这样则可以保证在算法开始时,各微粒能以较大的速度步长在全局范围内探测到较好的结果;在搜索后期,较小的值则能保证微粒在极点周围做精细的搜索,从而使算法有较大的几率以一定精度收敛于全局最优值。学习因子1c ,2c ,通常取12 2.05c c =。最大迭代次数

9、max iter 和群体规模M 。另外,粒子在不断根据速度调整自己的位置时,还要受到最大速度max V 的限制,当i V 超过max V 时被限定为max V 。本文在上述粒子群算法的基础上对其进行了一些改进,提出了一种基于扩张模型的粒子群算法,并在算法中引入了相对基学习,避免早熟现象,免遭“维数灾”的困扰提高了算法的有效性5。2.2 相对基初始化相对基学习(Opposition-Based Learning 是Tizhoosh 于2005年提出的一种新的机器学习算法。它的主要思想是:在求解优化问题时,同时考察一个可行解和它的相对解,通过评价他们的优劣来获得较优的候选解。一般来说,在对解无任何

10、先验知识的情况下,通常我们是采用随机法初始化群体。本文将相对基学习嵌入到PSO 算法中,通过同时评价一个可行解及其相对解的优劣,以获得较优的初始候选解,从而提高收敛速度。具体方法如下: (1随机生成均匀分布的初始群体,1,2,.,i i X X V i N =; (2计算相对群体OX :分别对X 中的每个粒子按(3、(4式计算其相对粒子(包括位置和速度,构成相对群体,1,2,.,i i OX OX OV i N =;id d d id ox L U x =+ (5 min max id d d id ov V V v =+ (6 其中d L 和d U 分别表示第d 维分量取值范围的上下界(,i

11、d d d x L U ;每个粒子的速度限制在区间min max ,d d V V 内,一般地,min max d d V V =且max 0.1(d d d V U L =; (3最后根据个体适应度值从X 和OX 中选择N 个粒子作为初始种群 000,1,2,.,i i X X V i N =, 0ii i i i X X OX X OX =,优于,否 0i i i i i V X OX V OV =,优于,否(7 相对基初始化可以在一定程度上减少粒子群寻优的时间,提高搜索效率和精度。 2.3扩张模型 2.3.1 扩张的定义 所谓扩张模型是指粒子向前推移并保持运动方向不变,而运动粒子在空间中

12、发生了扩张性的变化6。例如粒子在三维空间中从点A (1,1,1到B (2,2,2生了带有强制性的扩张。相应的位置变化公式为:(1(x i x i x i +=+,本文中采用的为: (1(x i x i a x i +=+其中a 为扩张因子。 2.3.2算法特点 扩张算法具有以下的特性:强制性:即粒子被强行向前推移;不变性:被强行向前推移的粒子飞行方向不变;扩张性:即粒子保持运动方向不变而各个维数的值发生成倍的扩Microcomputer Applications Vol. 27, No.5, 2011 技术交流 微型电脑应用 2011年第27卷第5期 ·61·大或缩小;同一

13、性:即各个维数的值同时并统一发生成倍的扩大或缩小;有效性:为了提高粒子子的有效性,粒子的位置被最大位置和最小位置限制。为了加快搜索速度,发生扩张的对象,不仅是处于历史全局最优位置的一个粒子,而是所有与最优点适应度相等的粒子。由于这些粒子处于停滞状态且是来自各不同的方向,如果对它们同时采用扩张,便产生以最优点为中心向四周开花的“星火式”的变异效果。3 基于改进粒子群算法的多阈值图像分割3.1 实验算法粒子群算法寻找的是全局最小值,而本文所应用的阈值选择方法是最大化公式(1和(2.所以将适应度函数定义为:(112,.c Fit H t t t = (8粒子群算法的步骤如下:(1相对基初始化所有的粒

14、子(群体规模为M 。在允许的范围0,255内随机设置粒子的初始位置、速度、pbest 和gbest 。 (2评价每个粒子的适应值。将位置取整,根据式(9计算每个粒子的目标函数,如果优于pbest ,则pbest 被当前位置替换;如果所有粒子的pbest 中有优于gbest 的,则置为新的gbest 。 (3根据公式(3和(4调整粒子的速度和位置,检查速度和位置是否在允许范围之内,如果不在,将二者调整到允许范围之内。如果最优解不变,则对位置进行扩张。 (4检查终止条件,如果达到最大迭代次数就终止迭代,否则回到步骤(2。 3.2 实验结果 利用最大熵阈值法得到最佳多阈值图像分割函数后,再用粒子群算

15、法对函数进行优化取得最优分割阈值.本文中的处理对象为256×256的Lena 图像,群体规模M =20,最大叠代次数max iter =100,惯性权重参数min 0.4=,max 0.9=,扩张因子1a =。Lena 原始图像(见图2。实验结果如下,(见图3图4并将此算法与相同条件下的遗 传算法相比较,如表1所示: 图2. Lena原始图像 图3.粒子群最大熵4阈值 图4.粒子群最大熵5阈值表1 图像的多阈值分割最大熵四阈值 最大熵五阈值四阈值 最大熵 五阈值 最大熵 遗传算法 75,100,174,213 16.6792 73,100,157,174,213 18.5795 粒子

16、群算法 81,112,168,245 17.3137 83,114,149,184,225 19.1461比较以上实验结果可以看出,基于粒子群的多阈值图像分割方法可以找到更优的阈值,且优化结果稳定,从而有利于计算机视觉的后续处理,体现了粒子群算法在图像分割多阈值选取中的优越性。4 结语基于粒子群的多阈值图像分割方法能够充分利用粒子群算法的特点,较好地解决了多阈值选取中计算量过大的问题。实验结果表明,粒子群算法简单、参数少、鲁棒性好,与遗传算法相比,具有操作方便、可靠性好、不易陷入局部极值等优点,完全能够实现满意的多阈值图像分割。参考文献:1章毓晋.图像分割M.北京:科学出版社.2001. 2壬春柏,赵宝军,何佩琨.基丁免疫遗传算法的自适应图像分割方法J.红外与激光,2004,33(2:178.181 3SHI Yu-hui, EBERHART R.Parameter selection in particle swarm optimizationA.Evolutionary Programming VII: Proceedings of El98c.New York :Springer-Verlag,1998.591-600. 4SHI Yu-hui, EBERHART R. Empirical study of particle swarm optimi