基于均衡化和K均值改进蚁群算法的边缘检测

1、第28卷 第1期文章编号:1006-9348(2011)01-0285-04计 算 机 仿 真2011年1月基于均衡化和K均值改进蚁群算法的边缘检测刘坤岭,周新志(四川大学电子信息学院,四川成都610064)摘要:研究图像特征的提取,边缘检测是图像处理中很重要的组成部分。在研究灰度图像的边缘检测问题中,根据像素灰度值的分布特点和图像的边缘特性,提出了一种基于直方图均衡化和K-均值改进蚁群算法相结合的边缘检测方法。采用直方图均衡对图像进行增强,以减小目标与背景的相似度,增大了反差,使图像细节清楚,另外采用模糊聚类的K-均值改进蚁群算法实现对图像边缘信息的快速提取。通过仿真表明方法收敛速度快,检测

2、效果好,具有较强的实用价值。关键词:图像边缘检测;直方图均衡化;蚁群算法;模糊聚类;K均值中图分类号:TP391 文献标识码:AImageEdgeDetectionBasedonHistogramEqualizationandK-meansImprovedAntColonyAlgorithmLIUKun-ling,ZHOUXin-zhi(CollegeofElectronicInformation,SichuanUniversity,ChengduSichuan610064,China)ABSTRACT:Imageedgedetectionisakeycomponentofimageproce

3、ssingsystemswhichhasstrongaffectsonthemageanalysisresultsi.Inthestudyofedgedetectionofthegray-scaleimage,bythepels distributingcharacteris ticandimageedgeattribute,acombinededge-detectingalgorithmisproposedbasedonhistogramequalizationandK-meansimprovedantcolonyalgorithm.First,theimagewasenhancedbyhi

4、stogramequalizationtoreducethesim ilarityofobjectivesandbackground,andthenthek-meansimprovedantcolonyalgorithmbasedFuzzyClusteringwasusedtoachieveimageedgeinformationabstractedfast.Themethodhasbeenshownfastconvergence,goodeffectandstrongpracticalvaluebyExperiments.KEYWORDS:Imageedgedetection;Histogr

5、amequalization;Antcolonyalgorithm;Fuzzyclustering;K-means1 引言边缘检测技术是图像特征提取中的重要技术之一,也是图像分割、目标区域识别、区域形状提取等图像分析领域的基础。经典的图像边缘检测算子有:Roberts边缘检测算子、Sobel边缘检测算子、Canny边缘检测算子等,虽然这些算子简单方便,但是它们只适用于检测有限类型的边缘,自适应性差4。传统的原始蚁群算法进行图像边缘检测时,虽然能够解决自适应差的问题,但由于聚类过程需要多次循环,当图像像素规模较大时,很难在较短的时间内完成对图像边缘特征的快速提取3。此外,有些图像在采集过程中由于

6、不均匀的光照造成图像较暗,灰度动态范围较低,从而会影响图像边缘提取的结果,存在边界不连续或边界不准确的问题,容易产生断裂的边缘。本文研究了在直方图均衡化的基础上采取K均值改进的蚁群聚类算法来对灰度图像进行边缘检测,首先通过对图像进行直方图均衡化的预处理来增加像素灰度值的动态范围,增强图像整体对比度,使图像细节清楚,以便于接下来的图像边缘提取。然后针对传统蚁群算法收敛速度慢的问题,利用K均值算法快速粗略地确定聚类中心,解决了传统蚁群算法收敛速度慢的问题。本文通过MATLAB软件编程与仿真与两种经典的边缘检测方法和传统蚁群边缘检测技术做比较,结果表明本文提出的算法准确率更高,自适应性更好,有较好的

7、检测效果,而且聚类收敛速度快。2 直方图均衡化2.1 直方图均衡化原理假设灰度级为归一化至范围0,1内的连续量,并令pr(r)表示某给定图像中的灰度级的概率密度函数(PDF),其下标用来区分输入图像和输出图像的PDF。假设对输入灰度级执行如下变换,得到输出灰度级s:s=T(r)=p(w)dwr0r(1)收稿日期:2009-12-04 修回日期:2009-12-21式中w是积分的哑变量。可以看出输出灰度级的概率密度函!数是均匀的,即ps(s)=1,0£s£10,其它(2)换言之,前述变换生成一副图像,该图像的灰度级较为均匀化,且覆盖了整个范围0,1。使用直方图并调用直方图均衡

8、化技术来处理离散灰度时,令pr(rj),j=1,2,L表示与给定图像灰度级相关的直方图,采用求和的方式,则均衡化变换为sk=T(rk)=#kpr(rj)=j=1#kj=1njn(3)图2均衡化后图像式中k=1,2,L,且sk是输出图像的亮度值,对应于输入图像的亮度值rk6。上述计算sk的公式实质上建立了一个变换,它能将非均匀分布变为均匀分布。在得到变换函数sk之后,即可建立灰度级映射对应关系:ksk%L2.2 直方图均衡化仿真分析利用MATLAB对直方图均衡化进行仿真分析:图1,3分别是大小为256%256的256级原始图像和直方图,可以看出这幅图像的特点是较暗且其动态范围较低,直方图偏向灰度

9、级较暗端。图2,4是均衡化后的图像和直方图,可以看出均衡化后平均亮度及对比度增强明显,均衡化后的直方图灰度间距拉大。图5是均衡化变换曲线。可得结论:经过直方图均衡化后,增加了像素灰度值的动态范围,从而达到增强图像整体对比度的效果,使图像细节清楚,以便于接下来的边缘提取。图3原始图直方图(4)图4均衡化直方图图1 原始图像3 K-均值改进蚁群算法的边缘检测技术3.1 传统蚁群算法边缘检测原理蚁群算法(AntColonyAlgorithm,ACA)是近几年发展起来的一种新型概率搜索算法,它利用生物信息激素作为蚂蚁选择后续行为的依据,并通过蚂蚁间的协同与交互来完成全局寻优搜索过程3。将蚁群算法用于图

10、像分割和边缘检测领域,主要分为三大类:1)基于图像边缘特征;2)基于模糊聚类;3)与其他算法的融合,如遗传算法Snake模型、Markov随机场等。本文所研究的是基于模糊聚类的蚁群算法,其主要思想是:给定原始图像X,将每个像素Xj(j=1,2,N)看图5 均衡化的变换曲线作一只蚂蚁,综合考虑图像中每个像素的灰度、梯度和邻域等特征,分别聚集到j个聚类中心Cj(j=1,2,k),设r为!聚类半径,phij为t时刻蚂蚁i到聚类中心Cj的路径上的信息素浓度,dij为样本与聚类中心的加权欧氏距离4。dij=均值算法收敛速度比蚁群聚类算法快5。通过K-均值快速粗略地确定聚类中心,从而确定各路径上的信息素,

11、信息素不必从0及相等常量开始训练,从而避免了传统蚁群算法初p1k(xik-xjk)2(5)始阶段学习缓慢的缺点有效的解决了蚁群算法早期收敛慢的问题5,改进后的算法流程为:Step1:任选K个初始化聚类中心:C1,C2C3,CKStep2:逐个将数据集X中各个数据对象按最小距离原则分配给K个聚类中心的某一个CjStep3:计算新的聚类中心C,2,K),即Cj(j=1j=1X,其中Nj为第j个聚类域Sj包含的个数NjX&Sj其中m为蚂蚁的维数,这里m为3,p为加权因子,根据像素各分量对聚类的影响程度设定。设r为聚类半径,phij为信息量,则:phij=1,dij£r0,dij&g

12、t;rij(6)Xi选择到Xj路径的概率为pij:ph(t) (t)pij=ij#phs&Sis(t) (t)is,若j£S(7)次数时转Step2C,2,K)j(Cj(j=1Step4:若且未快速分类到设定聚类效果阈值r或是指定Step5:nc0(nc为循环次数),由K-均值算法分类结果计算出聚类中心Cj(j=1,2,K),计算每个样本数据Xi到不同聚类中心Cj的初值phij(0)(i,j=1,2,N)给出!(信息量随时间的衰减程度),n(蚂蚁数)的值,随机给出分配方案Step6:对每个蚂蚁按转移概率pij选择下一个节点Step7:计算每个节点数据到聚类中心Cj(j=1,2

13、,K)的距离。由蚁群聚类式(8)修改信息量phij(t)Step8:若nc<预定的迭代次数且无退化行为(即找到的都是相同的解),则输出最优解,否则转Step60,否则式中, ij(t)是启发式引导函数, , 分别为像素聚类过程中所积累的信息以及启发式引导函数对路径选择的影响因子。S=Xs|dsj£r,s=1,2,N为可行性路径集合。随着蚂蚁的移动,各路径上信息量发生变化,经过一次循环,各路径上信息量根据下式进行调整:phij(t)=!phij(t)+phij中路径信息量的增量。phij=(8)其中,!为信息量随时间的衰减程度,phij为本次循环N#phkij(9)k=1phij

14、表示第i只蚂蚁在本次循环中留在路径中的信息量。3.2 K-均值对传统蚁群算法的改进蚁群算法中,蚂蚁行走是随机和盲目的,将图像的每个像素看作一只蚂蚁,假设图像大小为m%n,在循环搜索过程中,每个像素要和其余m%n-1个像素进行距离和路径选择概率计算,而且系统必须经过多次循环才能完成聚类过程,导致搜索时间长,整体计算量大。针对这一问题,文献4中根据图像分割特点给出初始聚类中心加以引导,这里引入K-均值聚类算法作为蚁群算法的预算过程,通过K-均值快速粗略地确定聚类中心。通过实验验证可知,K-4 仿真结果及分析为了验证本文提出的方法的有效性,从图像边缘检测效果及聚类算法的速度两个方面来进行实验比较。运

15、行环境为处理器:Intel(R)Petium(R)4CPU2.93GHZ,内存:1.5G,WindowsXP和Matlab7.0。图6是选取的待处理的三幅灰度值较低的图像,其中图像(a)像素为256%256,图(b),图(c)像素均为128%128。在传统蚁群算法和改进蚁群算法中使用的参数设置为: =1, =1,!=0.6,r=50,T=100。(a) (b) (c)图6 待处理的图像4.1 图像边缘检测效果分析比较实验结果图79中(a)、(b)、(c)分别为使用Sobel算子、Canny算子、原始蚁群算法对对图6中三幅图像未经过均衡化处理而进行的边缘提取,图79中(d)经过直方图均衡!化后用

16、K-均值改进蚁群算法进行提取的边缘。由图79中图像(a)可以看出Sobel算子对于灰度变化较小的部分检测效果不理想,边缘连续性较差。由图79中图像(b)可以看出Canny算子检测出的图像细节又太多,并且有些细节检测失真。图79中图像(c)是原始蚁群算法对未经过均衡化处理的图像进行的边缘提取,由于图像较暗,灰度值动态范围较低,可看到检测出的边缘存在边界不连续或边界不准确的问题,产生断裂的边缘,图8(c)头部较为明显。图79中图像(d)是经过直方图均衡化后用K-均值改进蚁群算法检测的效果,与上述方法得到的效果图对比可以看出检测的边缘连续性好,检测结果较为准确,不存在失真,效果良好。定聚类中心,聚类

17、速度快,适合用于图像的边缘快速提取。为了说明这一点,记录了对图6三幅原始图像分别用传统蚁群算法和本文改进的算法进行边缘提取所需的时间。表1是相关数据。表1 图像聚类分析相关数据图像编号图6(a)图6(b)图6(c)像素数目256%256128%128128%128原始蚁群算法耗时(T/ms)22.575.256.00改进蚁群算法耗时(T/s)190.2025.6726.13从表1中可以看出用原始蚁群算法边缘检测时需要花费较长时间,在图像像素为128%128时,耗时约为56ms,在图像像素为256%256时,需二十多分钟,也就是图像像素规模越大,就越难在较短的时间内完成对图像特征的提取,而经过改

18、进后的算法花费的时间分别为二十多秒和大约3分钟,对比可得本文提出算法明显优于原始传统蚁群算法。5 结语针对灰度图像,本文提出了一种基于直方图均衡化和K-均值改进蚁群算法的边缘检测方法,通过直方图均衡化,使原图的灰度间距拉大,增大反差,图像细节清楚,使得检测更为有效;改进的蚁群算法与原始蚁群算法相比,能够快速地确定聚类中心,极大降低了计算量,加速了聚类进程,是一4.2 聚类算法收敛速度分析比较本文提出的k-均值改进算法的特点是引入K-均值聚类作为蚁群算法的预算过程,通过K-均值快速粗略地确种有效的边缘检测方法。(下转第293页)!像。可以看出,kalman滤波器预测,Mean-shift算法结果

19、反馈给kalman滤波器继续预测,可以实现对目标较好地跟踪,当出现干扰时该算法仍然能准确地跟踪目标,实验结果表明该算法是可行有效的。他舰船、飞鸟等噪声影响,很好地跟踪目标。其中kalman滤波的预测值作为Mean-shift算法的初始跟踪窗口,缩小了窗口范围,减少了计算量,提高了跟踪效果的鲁棒性。参考文献:1 杜峥,张桂林,王超.红外弱小目标预处理及检测方法研究J.计算机与数字工程,2003,31(4):31-34.2 叶斌,彭嘉雄.基于形态学Top-Hat算子的小目标检测方法J.中国图象图形学报,2002,9A(7):638-642.3 沈晔青.精确制导中的图像匹配和跟踪算法研究D.南京航空

20、航天大学,2007.57-63.4 叶冠华.基于运动模型的红外多目标跟踪D.西安电子科技大学,2006.25-32.5 DComaniciu.Analgorithmfordata-drivenbandwidthselectionJ.PatternAnalysisandMachineIntelligence,2003,25(2):281-288.6 DComaniciu,PMeer.MeanShift:arobustapproachtowardfeaturespaceanalysisJ.PatternAnalysisandMachineIntelligence,2002,24(5):603-61

21、9.7 ChengYizong.Meanshift,modeseeking,andclusteringJ.PatternAnalysisandMachineIntelligence,1995,17(8):790-799.5 结束语本文采用最大类间方差法对红外目标进行检测,采用kalman滤波器预测与Mean-shift算法对目标进行跟踪,Kalman滤波是一个对动态系统的状态序列进行线性最小方差误差估计的算法,Mean-shift算法是一种基于核密度估计的无参数快速模式匹配算法,二者结合克服了使用单一算法的缺陷,在kalman滤波器预测的基础上利用Mean-shift算法寻找梯度最小核的位置,再反馈给预测,这样可以去除海面其作者简介刘 晔(1986-),女(汉族),北京市人,硕士研究生,主要研究领域为信号与信息处理;胡绍海(1964-),男(汉族),江西省人,工学博士,教授,研究方向为信号与信息处理;李向军(1962-),男(汉族),陕西省人,高级工程师,研究方向为信号与信息处理。(上接第288页)参考文献:1 MDorigo,VManiezzo,AColorn.iTheantsystem:optimizationbyacolonyofcooperati