基于蚁群模糊聚类算法的图像边缘检测

1、第38卷第5期2005年10月武汉大学学报(工学版)EngineeringJournalofWuhanUniversityVol.38No.5Oct.2005文章编号:167128844(2005)052124204基于蚁群模糊聚类算法的图像边缘检测苗京,黄红星,程卫生,袁启勋(武汉大学数学学院,湖北武汉430072)摘要:提出了一种基于蚁群动态模糊聚类算法的图像边缘检测,的能力,克服了FCM算法对初始化的敏感,动态地确定了聚类数目和中心;,再进行FCM聚类弥补蚁群算法的不足.,进的目标函数聚类分析.最后将该算法应用到图像边缘检测,边缘检测能力.关键词:数据挖掘;蚁群算法;模糊C2中图分类号:

2、TP181:AanalysisbasedonantcolonyalgorithmforimageedgedetectionMIAOJing,HUANGHong2xing,CHENGWei2sheng,YUANQi2xun(SchoolofMathematics,WuhanUniversity,Wuhan430072,China)Abstract:Thispaperproposesamethodofdynamicfuzzyclusteringanalysisbasedonantcolonyalgo2rithmforimageedgedetection.Thealgorithmmakesuseof

3、thegreatabilityofantcolonyalgorithmfordisposinglocalextremumfirstly,whichovercomessensitivitytoinitializationoffuzzyclusteringmethod(FCM)andfixesonthenumbersofclusteringaswellasthecentersofclusteringdynamically.Andthentheresultsfrompreviousforfuzzyclusteringmethodcanmakeupthedeficiencyofantcolonyalg

4、o2rithm.Inthisway,wecombineantcolonyalgorithmwithfuzzyC2meansclusteringorganicallyandfindthewholedistributingoptimizationclusteringandachieveclusteringanalysisbasedonimprovedfunc2tion.Atlast,theapplicationofthealgorithmproposedtoimageedgedetectionandcomparativeexperi2mentsshowthatthealgorithmhavegre

5、atabilityofdetectionthefuzzyedgeandexiguousedge.Keywords:datamining;antcolonyalgorithm;fuzzyC2meansclustering;edgedetection数据挖掘(datamining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的但又是潜在有用的信息和知识的过程.聚类(clustering)是数据挖掘发现的重要模式之一.聚类就是将数据对象分组成为多个类或簇,使得在同一个簇中的对象具有较高的相似度,而在不同簇中的对象差异较大1.传统的聚类分析是一种硬划分,它把每个待辨识的对象严

6、格地划分到某个类中,具有非此即彼的性质,因此这种分类的类别界限是分明的.而实际上大多数对象并没有严格的属性,它们在性态和类属方面存在着不确定性,适合进行软划分.模糊集(roughSet)理论为这种软划分提供了有力的分析工具,人们开始用模糊的方法来处理聚类问题,即模糊聚类(fuzzyclustering).由于模糊聚类建立起了样本对于类别的不确定性的描述,能更客观地反映现实世界,从而成为聚类收稿日期:2004212215作者简介:苗京(19572),男,河南济源市人,副教授,主要从事数据库与信息系统等方面的研究.第5期苗京等:基于蚁群模糊聚类算法的图像边缘检测125分析研究的主流2.蚁群算法(a

7、ntcolonyalgo2rithm)是由意大利学者M.Dorigo,V.Maniezzo,A.Colorni等人在20世纪初首先提出来的3,它2,c是X的C个聚类中心的集合;uik是样本点xk相对聚类中心i的隶属度;dik=xk-i为样本点xk与聚类中心i的距离,通常取欧氏距离;n为样本点个数,C为聚类的个数,1<C<n;m为加权幂指数,1m<,它影响隶属度矩阵U的模糊度.这样,FCM算法的实质是由初始参变量集X,U,V,C,m确定最终的U和V,使得J最小.是继模拟退火算法、遗传算法、禁忌搜索算法、神经网络算法等启发式搜索算法以后的又一种应用于组合优化问题的进化算法.该算法

8、不但具有智能搜索、全局优化能力,而且具有鲁棒性、正反馈、并行分布式计算等特点.已经应用于旅行商问题(TSP)、分配问题(QAP)、调度问题(JSP)等经典NP中4,而且在解决大规模集成电路综合布线、基于以上分析,FCM算法描述如下:输入:样本集X,聚类个数C和加权幂指数m.网络路由选择与流量负载等实际问题方面也有进展.本文用蚁群算法实现了基于改进的目标函数的模糊聚类,解决了动态确定聚类数目问题,并在图像的边缘检测实验中验证了这一算法的有效性.输出:最佳划分矩阵UV和最小的.:0,迭代步l=0和V()U(l):1模糊聚类,如、基于模糊图论方法,该方法可以转化为优化问题而利用数学的非线性规划理论求

9、解,并且可以在计算机上编程或借助其他优化辅助工具实现.这样,可以用数学语言描述模糊聚类问题:对于给定有限集X=x1,x2,xn,将其划分为C个模糊子集S1,S2,Sc,用uik表示xk隶属于Si的程度,于是得到集合X的模糊C2划分U=uikc若j,k,djkl>0,则c()u(l)ik()=1j=1(l)djk()(l)m-1若j,k,djkl=0,则令ujkl=1且对ij,uikl=0.(3)计算V(l+1):()对i,n(l+1)nvi=k=1uikxk(l)ik(l)mum(4)若V(l+1)-V(l)<,算法停止;否则,令|1ic,1kn,其中ni=1uci=1ik=1,1

10、<k<n;0ikl=l+1,转(2).上述算法也可以从初始隶属度矩阵U(0)开始=1是指欧氏C2<k=1uik<n,1iC.uik迭代,方法类似.该算法是收敛的,其解为问题minJm(U,V)的局部最小点或鞍点.空间中的超平面,即每个元素属于C个模糊子集n的隶属度总和为1;0<k=1u<n是指每个子集2蚁群算法一群蚂蚁很容易找到从蚁巢到食物源的最短路径,而单个蚂蚁却不能.大量实验观察和研究表明,蚂蚁个体之间是通过在其所经过的路径上释放一种称为信息素(pheromone)的物质来进行信息传递的.随后的蚂蚁不仅能检测出该物质的存在以及其强度,而且根据信息素的强度

11、来指导自己前进的方向;经过蚂蚁越多的路径其信息素就越强,同时信息素也会随时间的推移而逐渐挥发.因此,某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.这样,蚂蚁群体行为表现出了一种信是非平凡子集,即任意子集不是空集或全集.因此,最佳的模糊聚类就是寻求在一定条件下的最佳划分矩阵U.模糊C2均值(fuzzyclusteringmeans)聚类是模糊聚类分析中应用最广泛的聚类算法,在理论上为其他聚类算法奠定了基础.FCM算法采用误差的平方和函数作为目标函数,即ncmikJm(U,V)=k=1i=1udik其中:U是有限集X的模糊C2划分矩阵;V=1,126武汉大学学报(工学版)2005息正反

12、馈现象.蚂蚁个体之间就是通过这种信息交流寻求通向食物源的最短路径.蚁群算法正是模拟了这样的生物运动优化机制,即通过个体之间的相互协作和信息交流最终找到最优解.应用蚁群算法解决问题的一般步骤如下:(1)分析问题:将要解决的问题抽象成蚂蚁觅食的过程,赋予问题空间参变量在此过程中的具体意义.(2)初始化:给各参变量赋初值,相当于蚂蚁匀在蚁巢,等待出发.(3)优化过程:蚂蚁根据给定路径长度和信息素强度做动态选择,并在运动中释放信息素.(4)终止条件:对于给定条件,若满足,则算法停止;否则,转步(3).第(3)步是一个自适应过程,法的本质:基于以上分析,用蚁群算法实现基于目标函数的动态模糊聚类的方法(A

13、C2FCM算法)如下:(1)分析问题:将样本点视为蚂蚁,聚类中心视为食物源,则聚类的过程即觅食过程.(2)初始化:给定样本点集X=x1,x2,xn,迭代代数N,迭代次数l=0,初始时刻t=0,(l)(l)(l)各路径信息素;计算dkiki(t)=0,初始中心V=xk-vil.(3)优化过程:()选择机制:.设簇(l)半径为r,若dikr,则(l)(l)(ki()=1;ki.ki(tt时刻蚂蚁kkvi:l)(l)(l)(l)(l)ki(t)kj(t)jK(l)3用FCM又称交替的迭代优化法.迭代优化本质上属于局部搜索的爬山法,很容易陷入局部极值点,因此对初始化很敏感.通常是根据一定的经验准则选取

14、初始参数,这样计算结果与初始参数设置是否恰当密切相关.特别是在数据量较大和高维情况下,设置合理的参数非常困难,只能通过多次实验比较选定.由于初始聚类中心和样本的输入次序对最终的结果有重大影响,往往是用若干不同的初始中心和聚类数目分别聚类,然后选择最满意的聚类作为最终的结果.这种方法实验次数和耗时往往是令人难以接受的,而且也不能保证全局最优化.鉴于此,我们应用蚁群算法对样本进行模糊聚类.一方面,蚁群算法的鲁棒性(稳定性)可以有效地克服FCM算法对初始化的敏感;另一方面,它的并行分布式计算可以加速收敛,提高聚类效率.最重要的是该算法的智能搜索和自适应特点可以达到全局最优.但是,蚁群算法主要是利用正

15、反馈原理,当进化到一定代数后,就会由于最优路径的信息素不断增强而使蚂蚁大量聚集于少数的几条路径上,从而出现早熟、停滞现象.因此,单纯的蚁群算法并不能完全有效实现模糊聚类.另外,FCM算法的目标函数中是基于类内距离和,当聚类数与样本数相等时,显然目标函数为0,这已是最小值.这样,当聚类数不确定时就必须对目标函数进行改进.其中:K为蚂蚁k下一步可以选择的样本点的下(l)(l)标的集合;的启kj(t)为t时刻蚂蚁k由xk选vi(l)发信息,可取为1/dki;和分别为残留信息和启发信息的重要程度.()()更新机制:经过tl时刻,t=t+tl,l=l+1,完成一次路径搜索.则路径(k,i)的信息素更新为

16、(l)(l-1)(l-1)(t-t(l-1)+ki(t)=kiki(l-1)(l-1)=Q/dkiki为01之间的常数,表示信息素的持久强其中:(l)度;1-表示信息素的挥发程度;ki表示第k个蚂蚁在时间tt+t(l)之间,在边(k,i)上的信息素改变量;Q是一常量,表示蚂蚁完成一次路径搜索所释放的信息素总量.然后计算新的聚类中心(l)(l)V和样本点到该新的聚类中心的距离dik.(4)终止条件:可以使用下列两种终止条件之(l+1)()一:V-Vl<迭代次数l大于给定迭代代数N.否则转步(3).(5)FCM聚类:这里,由于聚类数目不确定,采用类内距和类间距之和作为目标函数,即ncmikc

17、ciJm(U,V)=k=1i=1udik+2i=1vj=i-vj2表示类内距离的权重,将蚁群算法得到的聚类个数C和聚类中心V=v1,v2,vc代入该目标函数,然后调用FCM聚类过程.4实验分析为了说明算法的性能,采用256×256的Lena第5期苗京等:基于蚁群模糊聚类算法的图像边缘检测127图(如图1)作演示实验.实验环境为Celeron2.66G,512M内存,WindowsXPProfessional,VisualC+.NET5.在FCM算法中分别取C=3和C=6,其聚类结果如图2所示;在ACFCM算实验结果表明,在聚类个数相同的情况,AC2FCM算法得到的图像处理结果比FCM

18、算法的处法中取=0.85,Q=100,N=50,=20,与FCM相对应的聚类结果如图3所示.理结果轮廓更加明显,细节更加清晰,边缘检测的效果更好(如帽沿和脸部的连续性等),随着聚类个数的增多,更细微的边缘信息也可以被检测到6.5结束语本文提出了一种基于蚁群算法的模糊聚类分析,动态地确定了聚类数目,并基于FCM算法的改进目标函数,且在图像的,;而,随着.如来并应用于实际问题将是研究的重要方向.参考文献:1JiaweiHan,MichelineKamber.Datamining:con2ceptsandtechniquesM.北京:高等教育出版社,2000.2高新波,谢维信.模糊聚类理论发展及应用的研究进展J.科学通报,1999,44(21):224122251.3DorigoM,ManiezzoV,ColorniA.Antsy