基于分数阶达尔文粒子群fodpso算法的图像分割-余胜威.pdf

《基于分数阶达尔文粒子群fodpso算法的图像分割-余胜威.pdf》由会员分享，可在线阅读，更多相关《基于分数阶达尔文粒子群fodpso算法的图像分割-余胜威.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、CN 431258TPISSN 1007130X计算机工程与科学Computer Engineering&Science第38卷第9期2016年9月V0138，No9，Sep2016文章编号：1007130X(2016)091836一07基于分数阶达尔文粒子群FODPSO算法的图像分割余胜威，曹中清(西南交通大学机械工程学院，四川成都6l0031)摘 要：图像分割主要用于提取用户感兴趣的目标，是图像分类和识别的基础。采用一种基于分数阶达尔文粒子群算法的图像分割方法，该算法采用分数阶微积分控制系统收敛性，能够对超尺度图像进行以一1个阈值寻优计算。实验结果表明，对比于APS0、CFPS0算法，该算

2、法具有收敛速度快、稳定性强、精度高、全局寻优等特点，有效地克服了传统算法易陷入局部最优和收敛速度慢等缺陷，可满足实际工程需求。关键词：多尺度分割；分数阶达尔文粒子群算法；类方差；算法对比中图分类号：TP3914 文献标志码：Adoi：103969jissn1007130X201609015Image segmentation based on fractionalorder1r、 J JDarWlnlanDartlCIe SWarm 0DtlmlZatlonYU Shengwei，CA0 Zhongqing(College of Mechanical Engineering，Southwest

3、 Jiaotong University，Chengdu 610031。China)Abst仡ct：Image segmentation mainly extracts the objectives users are interested in，and it is the basis for image classification and pattern recognition We present a novel image segmentation method basedon fractionalorder Darwinian particle swarm optimization，

4、caUed FODPSO The algorithm utilizes thefractional calculus strategy to control the convergence of particles and is able to determine the n一1 optimal for nlevel threshold on a given image Compared with the APSO and the CFPSO algorithms，testing results show that the FODPSO algorithm can enhance the pe

5、rformance in terms of conVergencespeed，stability，s01ution accuracy and global optimality，and greatly overcome the shortcomings of traditional methods，such as local optima and slow convergence speedHence，the FODPSO is applicable topractical projectsKey words：multiscale segmentation；fractionalorder Da

6、rwinian particle swarm algorithm；class variance；algorithm comparison引言图像分割在计算机视觉中占有重要地位叫，由于外界环境的多变性，使得图像包括很丰富的信息，因此有必要进行图像分割处理。图像分割是图像分析的基础，在图像识别和分类中应用广泛引。图像分割包括纹理特征分割、直方图阈值分割、聚类分割、区域分裂合并分割等3。其中图像阈值法是最常用最简单的一种方法(4剐。典型的阈值法有Ptile法、双峰法、最大类间方差法(Otsu法)、最小误差法、最大熵方法和梯度统计法等4。图像阈值法可分为阈值寻优法和基于图像属性的阈值法，前者通过现代智

7、能算法进行阈值全局寻优，后者则需要分析图像直方图，人为地设定分割阈值个数。*收稿日期：2015一05一14；修回日期：2015一0923通讯地址：610031四川省成都市二环路北一段111号西南交通大学机械工程学院Addre站：CoIIege of Mechanical Engineering，Southwest Jiaotong University，11l the First Section of the Second Ring Rd North，Chengdu 610031，Sichuan，PRChina万方数据余胜威等：基于分数阶达尔文粒子群FODPS0算法的图像分割 1837基于全局

8、阈值寻优算法23，有学者已做过双阈值分割方法，还有些学者研究多尺度阈值分割方法。对于双阈值问题5，通过寻优T。，满足(仃；(丁)最大化，其中，o丁，rl(1)其中，函数厂(z，y)表示图像坐标(z，y)处对应的灰度值，z对应宽度W坐标，y对应高度H坐标；F(z，y)为分割后的图像灰度值，图像分割成D。，D2，D。类。由式(1)可知，寻找到以一1个不同阈值尺度tj，即可将图像进行分割，如何寻找阈值的评价函数(适应度函数)成为接下来要处理的问题。最简单且最快速的阈值寻优方法是，直接找出不同类之间最大方差对应的灰度值，一般定义如万方数据1838 Computer Engineering&Scienc

9、e 计算机工程与科学 2016，38(9)下：盯待毗(膨一卢T)2 (2)J=1其中，歹代表一个具体的类，姒表示第歹类的概率，胁为第j类的均值，具体的D，Dz，D。类的训和p表示如下：弘2p。，歹一1，n=l户。，歹一竹m=f+1耋鲁护，。蔓十，鲁K j，。(9)矶(f+1)一删，()+f1 rl()(p。(f)一z。()+c2r2()(夕g()一zi(f) (10)其中，。、。分别表示叫的最大值和最小值，厂表示微粒当前的目标函数值，。和厂mi。分别表示当前所有微粒的平均目标值和最小目标值。32 CFPSO算法为了使算法达到全局探测与局部开采两者间的有效平衡，Clerc1妇构造了引入收缩因子的

10、PSO模型，采用了压缩因子，可确保PS0算法的收敛性，并可取消对速度的边界限制。速度公式如下：口f(t+1)=(妒(功(t)+c1 r1()(pi(f)一zi()+2r2()(p。()一工。(f) (11)其中P称为收缩因子9一Ii乏二商，00挖4。33 FODPSo算法PSO和其它的优化算法均存在一个普遍的问题就是容易陷入局部最优，以至于使得计算结果并不是非常让人满意，为了克服这个缺陷，一些学者提出PS0参数的调整，模糊逻辑PS0(FAPSO)、高斯PS0(GPS0)、达尔文PS0(DPS0)、混沌PSO(NCPS0)等2121算法，还有一些作者考虑了融合选择、变异、交叉和DE(差分进化法)

11、进PSO算法嗍等。采用融合自然选择算子的PSO算法，其中比较好的模型为DPSO引。DPSO算法中，当粒子寻优陷入局部最优时，放弃该搜索域，采用其他搜索域进行代替。基于此方法，每一次迭代循环中，好的种群将大量被选择并繁殖，差的种群将逐渐被淘汰。为了分析每一种群的状态，需要计算种群所有粒子的适应度值，更新个体最优值和邻居种群最优值。如果粒子找到一个新的更佳状态，该粒子将大量复制，如果种群不能找寻到下一个更佳状态，则粒子将被不断地淘汰。FODPsO是一种拓展型DPsO算法，其中分数阶次口被使用来控制算法的收敛速度。分数阶微积分(FC)已经应用于不同的领域，例如机械工程、计算数学、流体力学等9。对于序

12、列z()，基于Grnn、张1dLetnikov23的分数阶微积分定义如下： 驴瞰伽一击塞错器案黼(12)其中，分数阶次口Co押sf，11为伽玛函数，T为采样周期，r是截断阶次。GrnnwaldLetnikovi指出，FODPSO一个重要的性质：一个整数阶微积分表示一个有限级数，而一个分数阶微积分表示一个无限项级数。因此，整数阶微积分是局部算子，分数阶微积分则是对过去所有状态进行表征，而且随着时间的增长，过去的状态的影响逐渐减弱。由于分数阶微积分固有内在性质，因此能够很好地描述不可逆性和混沌性，使得粒子的寻优轨迹将更加适合全局最优情况。对于FODPSO，更新方程如下10：耽(+1)一1，1()(

13、户，()一z，()+f2 rz(f)(A(f)一z。()+删。(f)+寺删。(一1)+a(1口)口。(卜一2)+击口(1一口)(2一口)口。(f一3) (13)式(13)中系数取值可借助于(1+z)4=1+d+呜，+血之型z。+丛旦二n量篙兰幽zt+二项式的展开式来- 一M7、一理解，因此对于分数阶的智能算法改进可以有很多变形。式(13)对分数阶次达尔文PSO算法的实质进行了清晰化定义，实现过程类比于一般PS0算法。当口=1时，也就是系统没有过去一2和t一3的记忆，则FODPS0则变为DPS0，因此口的取值极大影响着惯性粒子。如果a的取值比较小时，粒子忽略了系统动态特性并且极容易陷入局部最优。

14、如果口的取值比较大时，粒子将表现一个多样化的行为，使系统能够找到全局最优值，因此在实际操作中，应加大口的取值。然而，如果a的取值过大，将使系统执行时间加长，基于初期的实验，当分数阶次口在o5，o8内时，算法能够获得更快的收敛速度1川，权衡系统各方面性能，口=O6系统最优2|。由式(1)可知，对于一幅图像而言，关键是寻找到咒一1个不同阈值尺度”使不同类间方差目标函数盯；最大。，等效为FoDPso算法中的粒子，盯；就是粒子的评价函数，即适应度函数。具体的求解流程如下：Step l 初始化个体屯=f+(一一f。i。)m玎d，mm一0，f。=L；step 2由式(2)计算初始化个体适应度值，打(岛)；

15、step 3计算种群内最优个体值A()以及种群最优个体值户。()，记录个体历史最佳位置；Step 4根据式(13)进行粒子速度更新；st叩5个体速度约束：f u，(f+1)uu(+1)=l础，让(+1)铆“Step 6由于考虑过去粒子对当前粒子的影响，对粒子进行速度更新如下：u(f一3)=(f一2)u(一2)=u。(一1)u。(一1)一u。()step 7个体位置更新如下：z：(+1)=z。()+u，(+1)step 8进行适应度值计算，并与上一代迭代最优适应度值比较，对种群最优适应度更新，直到达到循环迭代次数为IE。4在图像分割中的应用本文采用FODPS0、APSO、CFPSO算法实现图万方

16、数据1840 Computer Enginee“ng&Science 计算机工程与科学 2016，38(9)像分割，电脑配置为AMD A84500M(19 GHz)，274 GB可用内存，编程语言Matlab(2014a)。采用car、flower、concordaerial、tree、kids、scenery、river和palm图像进行测试，图像大小均为256256，图1为不同的图像及对应的直方图。醚鹕盛(xx) l(“)I 0(10 l 0f】0 L500 500 500 5加0匕=二) 0E= 0宦=：=， 0皇：二j0 】(X) 2 O l“】 !“) 0 l( 2f】0 0 100

17、 200曩霖 型5(X) _I 500一 500 一l 500ffx” Iff)()0f， 】0()o -1 000S(x】 50。| 500 500o匕=二 o匕二二 O：二j oE皇00 200 0 100 200 0 l200 0 100 2fl gLl rc l Hlsl()g ranl Oi(hfiurcnt lmagcs图1不同图像及对应的直方图初始化时，粒子速度设定为o，粒子的位置在满足约束条件的范围内随机地产生，搜索空间取决于图像灰度值的范围，也就是说如果图像是8位色图，那么粒子的寻值空间为o255。FODPSO、APSO、CFPSO是参数化的算法，具体参数设置如表1所示。Ta

18、ble l lnitial parameters for FODPSO、APSO、CFPS0表l FODPsO、APso、CF磷o参数初始化值注：本文中阈值尺度3”6。41 CPU处理时间因为算法是随机产生个体的，对于每一个尺度咒，分别采用FODPSO、APSO、CFPSO算法运行20次，统计各算法得到的适应度均值和标准偏差值和CPU计算时间。其中衡量算法有效性的一个重要指标就是CPU计算时间，CPU计算时间越小，算法越有可能应用于实际控制器，算法执行时间过长，则算法本身有待改进。表2为不同算法的处理时间对比。Table 2 CPU ti眦of diffe咖t aIgorith眦表2不同图像分

19、割算法的CPU处理时间万方数据余胜威等：基于分数阶达尔文粒子群FODPs0算法的图像分割 1841如表2所示，FODPSO算法表现出更好的性能，用时最短，其次是CFPSO，再次是APSO。为了直观地观察F()DPSO算法的分割结果，图2为不同尺度下的FODPSO算法分割结果。il斟】I t! l11：19I H 911H。nI；iIl()11 r ellI s(n=2，3，4，5 for image from left to right)图2图像分割结果(从左到右表示阈值个数为2，3，4，5)如图2所示，随着阈值个数的增加，图像分割得更加细致；其中当阈值个数为3时，图像分割效果较差，丢失特征较

20、多。当阈值个数为5时，即将图像分为6部分，图像显得更加平滑。42算法全局寻优能力分析考虑到所有的生物智能算法都具有随机性特点，即每一次算法运行得到的结果是不完全相同的，因此有必要进行算法的稳定性分析。为了定义算法的稳定性，采用标准偏差来衡量，如下式所示：厂可了sTD一，、半(14)f“ S丁D是标准偏方差，矾是第i次算法运行得到的适应度值，是盯的平均值，N是算法执行的次数，在此取N一20。STD值越小，则表示算法的稳定性越强。阈值取值分别为2、3、4、5，针对每一个阈值，算法均运行20次。图3表示采用不同算法，对不同尺度下的不同图像的适应度值标准偏差计算统计图。5：L 一o l -I 一-_m

21、nlN_附)(：N)11 Ig LI rc S、1 JLlc()f【111i。rcnf【n1lgcs hy th(1three algorithms(疗=2，3，4，5 for image from left to right)图3不同的图像不同的STD值(从左到右表示2，3，4，5个阈值)如图3所示，FODPSO算法是最稳定的，CFPS0、APS0算法寻优精度均低于FODPS0，且易陷入局部最优。由此可知，不管图像属性如何变化，粒子初始状态如何，FODPS0算法均能以较好的形态收敛。5 结束语本文采用一种新颖的图像分割算法(FODPSO)，对比于APSO、CFPSO算法，基于FODPSO的图

22、像分割算法实现了0tsu多级阈值下的图像分割方法，执行速度快，耗CPU时间短，能够克服生物智能算法的不足，如早熟现象等。本文中采用适应度值、S丁D、CPU计算时间作为不同算法的性能评价指标，结果表明，采用FODPS0算法比其他算法更加有效，并且随着阈值个数的增加，分割效果越好。FODPsO算法采用分数阶微积分去控制系统收敛性，采用系数口控制粒子探索捷径，从而保证系统能够实现全局寻优。由本文研究和国内外文献可知，分数阶达尔文PS0算法具有广泛的应用情景，例如遥感图像分割、实时视频分析等。参考文献：1 Liu Lei。Shi Zhiguo，su Haoru，et a1Image segmentat

23、ion伽伽珊瑚珊瑚啪万方数据1842 computer Engineering&Science计算机工程与科学 2016，38(9)based on higher order Markov random fieldJJournal ofComputer Research and DevelDpment，2013，50(9)：19331942(in Chinese)2 Ghamisi P，Couceiro M S，Benediktsson J A，et aIAn ef“cientmethod for segmentation of images based on fractional calcu

24、lus and natural selectionJEx”rt Systems with Applications，2012，39(16)：12407124173 B“nk A DMinimum spatial entropy threshold selectionJIEE Proceedings on Vision lmage and SignaI Processing，1995，142(3)：1281324 Huang Gang，Ii Jun，Pan JinguiA fast 2D()tsu image segmentation algorithm based on particle sw

25、am optimization a卜gorithmJJournal ofImage andGraphics，2011，16(3)：377381(in Chinese)5 Kulkarni R V，Venayagamoorthy G KBi0_inspired algorithms for autonomous deployment and localization of sensornodesJIEEE Transactions on systems，Man and Cybe卜netics Part C，2010。40(6)：6636756 0tsu NA thresh01d selectio

26、n method from gray-level histogramsJIEEE Transactions on Systems，Man and Cybernetics，1979，9(1)：62667 Kennedy J，Eberhart RParticle swarm optimizationCProc of IEEE International Conference on Neural Networks，1995二1942一】9488 Sathya P DKayalvizhi RPsO based tsallistresholding selection procedure for ima

27、ge segmentationJInternationalJournal of Computer Applications，2010，5(4)，39469 couceiro M s，Rocha R P，Fonseca Ferreira N M，et aIIntroducing the fractiona卜order Darwinian Ps0Jsignal，Imageand Video Processing，2012，6(3)：34335010 Guo Tong，Lan Julong，LI Yufeng，et a1Adaptive fractiona卜order Darwinian parti

28、cle swarm optimization algorithmJJournal of Communications，2014，35(4)：130一139(inChinese)11 Clerc M，Kennedy JThe particle swarrrl-explosion，stability，and convergence in a multidimensional complex spaceJIEEE Transactions on Evolutionary computation，2002，6(1)：5873附中文参考文献：1刘磊，石志国，宿浩茹，等基于高阶马尔可夫随机场的图像分割J计算机研究与发展，2013，50(9)：193319424黄港，李俊，潘金贵基于粒子群优化方法的2维0tsu快速图像分割算法口中国图象图形学报2011，16(3)：37738110郭通，兰巨龙，李玉峰，等自适应的分数阶达尔文粒子群优化算法J通信学报，2014，35(4)：130一139CA0 Zh仰qjng，bom in 1967，PhD，associate professor，his research interestincludes manufacturing information engineering万方数据