基于粒子群优化算法的阈值图像分割研究

1、计算机应用 自动化技术与应用2007年第26卷第1o期 旦坐唑坐墅上耻韭壁旦堕一基于粒子群优化算法的阈值图像分割研究 汪筱红-,须文波2(1.无锡广播电视大学信息工程系,江苏无锡214021;2.扛南大学信息工程系,江苏无锡214021摘 要:研究将群体智能巾的粒了群优化算法应用到图像分割中,提r一种新的罔像分割算壮。新方法基于最佳熵阈值分割技 术,用粒子群优化算法白适应选取分割闽值。仿真实验针对Lella图像分割问题,将遗传箅法与粒子群优化算法分别独立运 行,对得到的闻俏以及均值、方差进行r比较,并将运行时问作为算法复杂度的泮价指标。统计结果晁示,沦文算怯不仅能 够对图像进行准确的分割.而且

2、运行时间明显较短。仿真结果表明,基丁粒子群优化的图像分割算法是可行的、有效的。 关键词:嗣像分割;粒子群优化算法;遗传算法中圄分类号:TP391.4l 文献标识码:B 文章编号:10037241(2007lO006卜03ThreshOld Irnage Segmentation Based On the ParticIe Sv组rm OptimizatiOn algor-thmw&NGao-h帅gl,xu win-b02(1.De恤0fC锄叩u缸Sdence锄dEngiIl嘟ing删RadioAndTvUmversi吼m函2140210】iIla; 2.脚Lofc0呐sci跚ce鼬dE

3、n曲赋血g,Ji籼allunjver8时,wu】【i214021c抽诅Abstract:A novel algonthm based on panicle swa珊optlmization is presented in t|Iis papeL n shows that the algotlm presented in this paper can nnd better solutions with much lit【Ie complexity E1p甜Inent wi血吐le kna image sh。ws Ehat this me山od js feasible and etf色ctive.

4、Key wOrds:image s。gmentation,particle swarm optlmIzation algorithm.gene【ic algodmm1引言图像分割是图像处理和前辅税觉中基本技术,是大多数圉 像分析和视觉系统的重要组成部分。图像分割应用一种或多种运 算将图像分成一些具有类似特性(如颜色,纹理,密度等的区域, 主要分为阈值方法,边缘检测法,区域跟踪法等“。其中阈值方 法是图像分割的常用方法。目前已经提出了众多的阈值图像分割 方法,如最小误差阈值法,最大类别方差法(0su法及最佳直方 图熵法等。根据shaoo等人利用均匀性参数和形状参数对标准图 分割结果作酬自的评测结

5、论:吼su祛,最佳熵法,Johamserl法, Biue法和T鼢i矩不变法是较好的方法。以上所述的方法均涉及 到寻优的问题,所【她口何快速有效地选取最优阀值是基于闽值方 祛图像分割技术的一个关键。粒子群优化算法(Panicleswam Opn渤tion,PsO是 由Knedy和Eberhart于1995年提出的一种基于群智能(sWa彻收稿日期:20070521 IntcLugence的演化计算技术脚。PsO的优点在于流程简单易实现, 算法参数简洁,无需复杂的调整,因此,自算法提出以来。PsO 被迅速地应用于函数优化、神经网络训练、模糊系统控制、数据 聚类等领域。实践证明PSo算法在收敛速度和性

6、能上较之前的智 能优化算法遗传算法,都有了明显的提高。本文将粒子群优化算法应用到图像分割中,提出了一种基 于最佳熵阈值分割技术的图像分割算法,仿真实验表明,新算法 不仅能够对图像进行准确的分割,而且与遗传算法相比,能够以 较少的计算代价得到最优阈值。2粒子群优化算法2.1算法原理粒子群算法将每个个体看作是D维搜索空间中的一个没有 体积没有质量的粒子,在搜索空间中以一定的速度飞行。井根据 对个体和集体的飞行经验的综合分析来动态调整这个速度。设群 体中第i个粒子为x=(ok,x。,它经历过的最佳位置为吾赢技术与应i赢7年第26黼10期 计算机应用 曼!苎e!皇鲤“!塑!P=m.R,j球。当前组成群

7、体的所有粒子经历过的最佳位置为:=蛾,已,j珞。粒子i的速度用Y=(7.t“表示。对每 一次迭代,粒子的进化方程为:vd(k+D=、(k+昭(也(k一x。(k+%q(kj一(1(的 (1 o(+D=+vdi=L卫_,M d=LZ一;D (2 其中,cl和c2为加速常数,它们使每个粒子向Pi和Pg位 置加速运动。rl,r2为f0,11范围内的随机数。此外,粒子的速 度vi被最大蝴maX所限制。如果当前对粒子的加速将导致它在某维的速度vid超过该维的最大速度vmaXd,则该维的速度 被限制为该维的最大速度vInaxd。它决定r粒子在解空间的搜 索精度,如果vmx太高,粒子可能会飞过最优解,如果V越

8、 太小,粒子陷人局部搜索空间而无法进行全局搜索。Yu smHui和Ru刚l Eberhar一首次提出了惯性权重 的概念,并对基本算法中的粒子速度更新公式(1进行了修正,如 式(3所示,以获得更佳的垒局优化效果:K时D=吼+啊啦飞坞瓴一k嘞 (3 其中为惯性权重(Iner幽w咄扭t,它缱粒子祭睁运动的 惯性,使其有能力探索新的区域。当个体察觉同事信念较好的时 候,它将进行适应陆地调整。其后的研究者普遍采用这种方式作 为系统粒子速度更新的基本方式,井在大量的应用问题中充分验 证了其合理眭。式(3中的第一部分为粒子先前的速度乘个权值 进行加速,表示粒子对当前自身运动状态的信任,依据自身的速 度进行愤

9、陆运动;第二部分为认知项(cogniuve Tem,表示粒 子本身的思考,即一个得到加强的随机行为在将来的出现几率增 大,从而实现一个增强学习过程。第三部分为社会项(social Tem,表示粒子间的信息共享与相互合作。2.2参数选择粒子群优化算珐模型中,cl反映了粒子飞行过程中所记忆 的最好位置对粒子飞行速度的影响,称为“认知系数”;c2反映 了整个微粒群所记忆的最好位置对粒子飞行速度的影响,称为 “社会学习系数”。大量实验证明,c1与c2之和最好接近4,通常 取cIc2=2.O严7。由式(3可知,m越大,粒子的飞行速度越大,微粒将眈较久 的步长进行全局探测;m越小,微粒的速度步长越小,微粒

10、将趋 于进行精细的局部搜索。实验发现,当me【09,12时,算法具有较 理想的搜索陛能。所以,在搜索过程中可以对m进行动态调整:=%一警×k (41o 一 其中jtcmax为最大迭代次数,这样可以保证在算法开始 时,各微粒能以较大的速度步长在全局范围内探测到较好的种子; 在搜索后赣,较小的。值保证微粒在极点周围做精细的搜索,从 而使算法有较大的儿率以一定精度收敛于全局最优值。群体规模M越大,算法的寻优能力越强,但计算量越大。本 文中选取M=20。3基于粒子群优化算法的最佳熵阈值图 像分割法3.1最佳熵阈值确定法嘲3.1.1单阈值分割将信息论中shallrIon熵概念应用于图像分割时,

11、依据是使 图像中目标与背景分布的信息量最大,通过分析图像灰度直方图 的熵,找到最佳阈值。对于灰度范围为O,l,L一1的图像, 假设图中灰度级低于t的像素点构成目标区域(0,灰度级高于 t的像素点构成背景(B,那么各个灰度级在本区的分布概率为: o区巴,i二1,2 ,tIB区。尚 i二t+1,t+2, L 1i其中,量=P对于数字图像中的目标和背景区域的熵分别为:比o=(斗7plgtP7p i_0,1.,t (5 m(,=哳,(1一P.(P,(1一时】i_t+1,t+2,L一1(6 则熵函数定必为:即=州。+m=岫(1一P+鲁+等半 7 H=画岫,H。=一B卸.当熵函数取得最大值时对应的灰度值t

12、幸就是所求的最佳阈 值,即t2AIg罂瑟“(3.1.2多阈值分割同一背景图像上有多个物体,可采用多阐值分割。最佳熵自动门限祛适台于多阕直(为k个阈值分割,此时:啭刚科n鼢埘一普式中s,s2,气是分割阈值,且有%c s2c c sk。最佳阈值 s:,s:为侥总熵取最大值,即;8k“。冬铲“小8,8:特别地,对于双阈值情况,即为s.cs:,则有照灿盼阱n阱紫一紫警,最佳阈值g t为使总熵值取最大值,即:S5衄景。H￥,-R、 (11 3.2用于图像分割的粒子群优化算法的步骤将粒子群优化算法应用于图像分割中,通过寻找使得总体 熵值最大的闻值作为图像的分割阈值,其具体步骤为:步骤l:初始化粒子群:设种

13、群规横为M。随机设置粒子的初 始位置和速度,并计算每个粒子的适应度值,其中单阈值采用式计算机应用 !宣垫堡堕查皇皇旦!墨蔓!查塑!塑 璺!塑日!皇PEI!型!堕(7,多阈值采用式(10。每个位置的P.设为初始位置,P.中的具 有最优适应度值的位置设为Pg;步骤2:分别根据粒子群优化算法的位置和速度更新公式调 整每一个粒子的位置和速度,得到新一代的粒子群,并评价每个 新粒子的适应度值,步骤3;更新新的P.和Pg,判断终止条件,如果达到最大迭 代次数或者最优解停滞不再变化,就终止迭代.否则回到步骤2; 步骤4:得到图像的最冼分割阈值进行阈值分割。3.3仿真试验结果及分析本试验将基于粒子群算1弦的最

14、佳熵阈值图像分割方法与基 于遗传算法的最佳熵阈值图像分割方法进行了对比。试验对象为 图l中的协图像,两种算法的种群规模均为20,最大迭代代数均为100。PS。算法的参数设置为c=c。=2.05,m作为迭代次数 的函数由1.2线性减小到0.9。GA的参数设置为交叉概率是O.8, 变异概率O.2,采用蒙特卡罗选择。对两种算法分别进行了10次 试验。图2和3分别为基于粒子群算祛的单阈值和双闻值图像分 割的结果。图1Lena原始圈图2单阈值分割结果图3双阈值分割结果 表1单阈值分割10次运行结果比较l 23567e 9lO均健 方差总运行时间A“赫舶脚甜甜船舶臂船盼“5t0越瑚盯甜惦瑚髓眠l也嘟 蚰基

15、盹誊 酷表1和袁丝台出了两种算法用于单闻值和多阈值图像分割时10次独立运行的结果。通过对运行结果的均值和方差进行统计比较, 并记录lo次运行所需时间来衡量算法的计算量,可以看出粒子群 算法lO次运行的均值比遗传算法更接近最优值,且方差远小于遗 传箅法的结果,运行时【司也远远叫、于遗传算法的结果。这充分说明 了粒子群算法的搜索精度,稳定陛和速度均优于相应的遗传算法。 襄2双阈值分割10次运行结果比较氐5舶糟柚¨¨,聃¨柏uJtml.髑舯瓣I盯n扫射舯7J“l&艟|鑫q¨赫耱旺nn¨盯l一。一皓*船赫赫"一奠蛔靠“TI一n-; :

16、4结束语 、 本文成功将群体智能算祛中的粒子群优化算法应用于最佳 熵阐值图像分割,并通过仿真实验将其与基于遗传算法的图像分 割技术进行比较,结果表明新分割算法能更好地收敛到撮佳熵闻 值,并.卧萄i时间明显少于相应的遗传算法,且稳定性也得到了较 大的提高。今后将进一步研究群体智能算法在图像分割中的应用。 参考文献:GONzALEz R.c,w00DS R.E.Digital irnage proo蝤ulg M1.3rd.ed.Addi”Wesley,L992.I 2】J.KENNEDY.BaIe bones part记1e gWa玎商c】.P代ceodm窖0f IEEEswam In坩ligen

17、ce symposium,2003:5357.(j龚声蓉,刘纯平,乇强数字图像处理与分析M J.北京:清 华大学出版社2006.74】刘直芳,王运琼,朱敏.数字图像处理与分析【M】.北京:清华火学出版社2006.85】王玫,朱云龙,何小贤群体智能研究综述f J】,计算机工程 2005.31(22:6】昊薇,基于最大模糊熵原理的多阈值图像分割新算法【J】,系统工程与电子技术,2005,27(2:作者简介:汪筱虹(1969一,女,江苏无锡人,上海交通大学电子信息与电气工程学院硕士、讲师,研究方向:计算智能,图像处理。(上接第31页根据上式我们求的最大的欧氏距离和对应的时间偏移f。 如果我们选择f=

18、o.4lo皇f枷,这时有叵:旧=扩O蝻=1.618l 再根据“找们可以得到这时最佳的错误概率为:只=Q(d 2n,2=Q(1r盯,2:2224×1035结束语本文讨论了高斯信道条件下PPM调制uwB脉冲信号波形 确定的方法。包括确定信号持续时间和PPM信号的时间偏移。 信号持续时间通过对信号的频谱要求来得到,而时间偏移可以 通过求信号欧氏距离的最大值来获得。这样确定的信号具有最 佳的错误概率。虽然本文仅讨论在高斯信道的情况下,并且没有考虑由于 多径效应带来的码间干扰。但对进一步讨论在多径效应下PPM 调制uwB信号的脉冲波形参数确定具有一定的参考价值。参考文献:1J党梅梅.超宽带无线

19、通信技术发展现状f】.中国多媒体通 信,2006.(11:3436【2】J.D TAYLoR,EDITOR.An Tn缸州uc曲n枷ultm Wideband Radar Tcchno】og列M】,Boca Raton:cRc Press,1995【3龚江涛,尚琴,陈金鹰.uwB技术与应用【J】.山东通信技 术,2006.9(3:2022,26【4】F.RAMIREZMIRI,Es,on Perfonnance of Ultra wldeband s岫1ak i11Gau商an Noi鸵arld Der磷Mul廿patll,”【JEEE Trans.Veh.Techn01.20叭.50(1】:244249作者简介:黄淑琼(1972一 ,女,广东高