基于二维直方图和粒子群优化的边缘检测.doc

文库下载 免费文档下载/本文档下载自文库下载网，内容可能不完整，您可以点击以下网址继续阅读或下载：/doc/e1c4c4bc1a37f111f1855bab.html基于二维直方图和粒子群优化的边缘检测第29卷第7期2007年7月文章编号:10012506X(2007)0721192205系统工程与电子技术SystemsEngineeringandElectronicsVol.29No.7Jul.2007基于二维直方图和粒子群优化的边缘检测朱炜,徐玉如,万磊,吕春旺(哈尔滨工程大学水下机器人实验室,黑龙江哈尔滨)摘要:,到图像分割中,提出了一种新的边缘检测算法,适应搜索最优解,。通过对水下图像处理的实验证明,和传统检测方法相比,具有更好的抗噪性能。关键词:;二维直方图;水下图像中图分类号:文献标志码:AEdgedetectionbasedontwo2dimensionalhistogramandparticleswarmoptimizationZHUWei,XUYu2ru,WANLei,LChun2wang(UnderwaterVehicleTechnologyLab,HarbinEngineeringUniv.,Harbin150001,China)Abstract:Duetotheassimilationofthewaterandunevenlightness,theunderwaterimagewouldhavelowS/Nandtheedgeisfuzzy.Ifthetraditionalmethodsbasedonone2dimensionalhistogramareusedtodisposeitdirectly,theresultisnotexpected.Thetwo2dimensionalmaximumentropymethodnotonlyconsidersthedis2tributionofthegrayinformation,butalsotakesadvantageofthespatialneighborinformationderivedfromthetwo2dimensionalhistogramoftheimages.Asaglobalthresholdm/doc/e1c4c4bc1a37f111f1855bab.htmlethod,itoftengetsidealsegmentationre2sults.However,itstime2consumingcomputationisoftenanobstacleinrealtimeapplicationsystems.Inthispaper,theedgedetectionapproachbasedontheparticleswarmoptimizationalgorithmandthetwo2dimensionalgrayscalehistogramisproposedtodealwithunderwaterimage.Intheproposedmethod,theparticleswarmoptimizationalgorithmisrealizedsuccessfullyintheprocessofsearchingtheoptimalsolution(s,t)inthetwo2dimensionalgrayscalespace.Thentheoptimalsolution(s,t),wheresisathresholdforpixelintensityandtisanotherthresholdforthelocalaverageintensityofpixels,isselectedasthethresholdofedgedetectionopera2tors.Theexperimentsofsegmentingtheunderwaterimagesareillustratedtoshowthattheproposedmethodiseffective.Comparingwiththetraditionalmethods,thisapproachshowsbetteradaptiveandnoiserestrainingperformance.Keywords:edgedetection;particleswarmoptimization;two2dimensionalmaximumentropy;underwaterim2age0引言://doc/e1c4c4bc1a37f111f1855bab.html边缘是图像的重要特征之一,正确提取边缘既能大大减少图像处理的信息量,又能描述物体的形态特性,为进一步分析提供了基础。目前,作为一种有效的图像分割和特征提取方法,边缘检测已经成为许多领域的研究重点,基于边缘的图像分割算法是最早的图像分割算法之一并且仍然收稿日期:20060809;修回日期:20061011。是非常重要的一种。它依赖于边缘检测算子检测出的图像边缘,这些常用的算子有Robert,Sobel,Kirsch,LoG和Canny等。这种方法能提取出连续的边缘,而且不需要任何先验知识,但是阈值的选取是关键。Pun1提出用后验熵的概念来选取阈值,Kapur2对他的算法作了修正和改进,提出了基于一维直方图的最大熵阈值分割算法。但是当图像的信噪比较低或图像背景较为复杂时,一维最大熵阈值作者简介:朱炜(1979),男,博士研究生,主要研究方向为水下图像处理,目标识别,群体智能。E2mail:第7期朱炜等:基于二维直方图和粒子群优化的边缘检测?1193?分割的效果不佳。近年来,一些研究人员提出利用图像的二维灰度直方图(像素的灰度分布及其邻域的平均灰度分布所构成的直方图)的方法来进行阈值选取和图像分割3。由于这些方法利用了图像的像素灰度信息和像素邻域的空间相关信息,能够有效地抑制噪声,得到较高精度的分割图像,但运算速度慢,复杂性高,如果没有快速算法很难应用于实时处理。粒子群优化(particleswarmoptimization,PSO)算法是一种基于群体智能方法的演化计算技术47化算法在二维灰度空间上搜索最优解,使得二维熵最大化;然后将搜索到的阈值作为边缘检测算子的门限,再对图像进行阈值变换后,便可得到表示原图像主要特征的分割结果。通过对水下图像的处理,取得了较好的效果。1水下图像特点,在不同光,。,使得采,图像对比度大幅度下降,细节模糊;另外在图像采集和传输过程中,由于/doc/e1c4c4bc1a37f111f1855bab.html噪声污染,图像质量也有所下降;其他还有一些由于摄像机镜头的几何形状造成的图像部分失真现象等等。图1是几幅比较典型的水下图像。我们可以看到,水下图像的对比度都比较低,此外受到采集时光照条件的影响,右边两幅图像的模糊性更强,存在明显的灰白效应。,同遗传算法一样是一种迭代优化算法,变异。系统初始化为一组随机粒子,;值法有机的结合起来,提出了一种基于二维直方图和PSO的边缘检测算法。算法首先根据像素的灰度分布及其邻域的平均灰度分布定义二维直方图,然后利用粒子群优图1水下目标图像2粒子群优化算法(PSO)文献4引用了生物社会学家E.O.Wilson关于生物群体的一段话“,至少在理论上,一个生物群体中的一员可以从这个群体中所有其他成员以往在寻找食物过程中积累的经验和发现中获得好处。只要食物源不可预知的分布于不同地方,这种协作带来的优势可能变成决定性的,超过群体中个体之间对食物竞争所带来的劣势”。这段话的意思是说生物群体中信息共享会产生进化优势,这也正是粒子群优化算法的基本思想。PSO就是从这种模型中得到启示并用于解决优化问题决定了每个粒子的适应值,并且知道它到目前为止发现的最优位置(XpBest)和现在的位置Xi。除此之外,每个粒子还知道目前为止整个群体中所有粒子发现的最优位置(XgBest)。每个粒子通过跟踪这两个“最优值”不断调整自己的速度和位置vidk 1kk=w?vid c1?r()?(pid-xid) kc2?r()?(pgd-xid)(1)(2)xidkk 1=xid vidkk 1(2)中,i=1,M,M是群体的粒子总数。在式(1)、vid:第k次迭代粒子i速度矢量的第d维分量;xid:第k次迭代粒子i/doc/e1c4c4bc1a37f111f1855bab.html位置矢量的第d维分量;pid:粒子i个体最优位置的第d维分量;pgd:群体最优位置的第d维分量;r():随机函数,产生0,1间的随机数。k的5。在一个PSO系统中,包含一定数量个体(称为粒子)的群体在搜索空间中运动,其中每个粒子表示针对一个特定优化问题的潜在解。群体中每个粒子的位置受到其本身运动过程中最优位置的影响(即个体经验)和其邻域中最优粒子的位置的影响(即邻域经验)。当粒子的邻域是整个粒子群体时,邻域的最优位置则对应了全局最优粒子,此时算法称为全局PSO算法。相应的如果在算法中利用了较小的邻域,通常称它为局部PSO算法。此外在不同的优化问题中,还需要一个特定的适应函数来衡量每个粒子的性能。将第i个粒子在N维空间里的位置用Xi=(x1,xN)来表示,速度用Vi=(v1,vN)表示。同时由适应函数在图2中,描述了粒子在二维空间里,根据迭代公式(1)和(2)从位置Xk运动到Xk 1的原理。图2二维空间粒子运动示意图?1194?系统工程与电子技术N第29卷(3)w是惯性权重函数,它对于PSO算法的收敛性起到很大作用,通过调整w的大小来控制以前速度对当前速度的影响,使其兼顾全局搜索与局部搜索的一个折中。通常w由下式来确定w=wmax=iteritermaxL-1L-1pij=i同时pij还满足i=0pj=0ij=1。假设图像由目标和背景组成,用最大熵原理确定像素灰度邻域平均灰度组成的最优阈值(s,t),可使真正代表目标和背景的信/doc/e1c4c4bc1a37f111f1855bab.html息量最大(s,t),其中s表t。根pij,而阈t)(图3)。由于区域3和4,因此在计算中可以忽略不计,而区域1和2则对应着图像中的目标和背景,它们可以被看作是独立分布的。此外为保证每个区域的总概率等于1,还需要对每个区域的概率累积分布做归一化的处理。这里根据Shannon熵函数,定义离散二维熵为H=-其中wmax,wmin分别是w的最大最小值;iter,itermax分别是当前迭代次数和最大迭代次数。w大,速度v就大,有利于粒子搜索更大的空间,可能发现新的解域;而w小,则速度v就小,代开始时设w=wmax,wwmin。,得到合适的种子,。c1,c2可看作是加速度常量,其中c1反映了单个粒子本身运动过程中所记忆的最好位置对其运动速度的影响,称为“认知系数”;c2反映了整个粒子群体所记忆的最好位置对单个粒子运动速度的影响,称为“社会系数”。大量实验证明,c1与c2之和近似等于4.1,通常取c1=c2=2。此外,如果群体规模M越大,则算法的寻优能力越强,但计算代价也越大;同时在某些实际应用中,还需要对粒子的最大运动速度进行限制,控制每次迭代时粒子的运动步长,从而提高算法的稳定性和减小计算代价。pijijlogpij(4)3二维最大熵阈值分割原理阈值法是图像分割中最常用的一种技术。在过去的20年里,已经提出了很多阈值技术。其中基于信息论的图3阈值划分后的二维直方图区域1和2的概率累计分布为stL-1L-1方法利用了图像的直方图及一个根据直方图定义的目标函数来选取最优分割阈值,图像的信息熵反映了图像的总体概貌。若图像中包含目标,则在目标与背景可分割的交界处信息量(即熵)最大。Pun首先提出基于最大熵原则来选择阈值,/doc/e1c4c4bc1a37f111f1855bab.html将图像的灰度直方图分成独立的类,使得各类的总熵最大。从信息论角度来说,就是使这样选择阈值获得的信息量最大。Pun的一维最大熵阈值算法在图像质量较好和背景稳定变化时,可以取得比较理想的分割结果。但当图像的信噪比较低或图像背景较为复杂时,其效果不佳。因此,Abutaleb3P1=i=0pj=0ij,P2=i=s 1j=t 1pij(5)且由于假设边缘和噪声忽略不计,所以P11-P2。根据式(4),可分别定义对应目标和背景的离散二维熵StLLH1=-i=1pj=1ijlogpij,H2=-i=s 1j=t 1pijlogpij(6)从而图像总熵的判别函数可通过变换定义为(s,t)=H1 H2=logP1(1-P1) H1/P1 (HL-H1)/(1-P1)(7)在1989年提出了二选取的最优阈值(s3,t3)应满足(s3,t3)=max(s,t)LL维最大熵图像分割算法,算法采用像素灰度和邻域平均灰度构成的二维直方图搜索阈值,充分利用了图像像素的灰度分布信息和各像素间的空间相关信息,分割效果较好。设一mn的图像的灰度级数为L,图像kk邻域的平均灰度也有L级灰度,总像素点数为N(N=mn),其二维直方图为h(i,j)=pij,0i,jL-1,其中i为像素灰度,j为邻域平均灰度。如fij为图像中点灰度为i及/doc/e1c4c4bc1a37f111f1855bab.html其邻域灰度均值为j的像素点数,则pij可由下式确定其中HL=-(8)i=1pj=1ijlogpij。4基于PSO优化的阈值选择二维最大熵法本质上是在二维灰度空间上搜索参数,使得目标函数式(7)取得最大值的优化问题。从上面的分析可以看出,对于每个(s,t)对,都要从头开始计算P1和H1,运算过程是一个4重循环,计算比较耗时。实际应用中,为了提高运算速度,必须对二维最大熵法进行优化。第7期朱炜等:基于二维直方图和粒子群优化的边缘检测?1195?综合考虑二维最大熵原理和PSO优化算法,在二维空间Q=(s,t)|0s,tL-1里,设置点(s,t)作为粒子的位置,熵函数式(7)作为评价粒子的适应函数,通过迭代寻找最优解,也就是让图像二维熵最大的点(s3,t3)。获取最优阈值的基本流程如下。步骤1初始化:在LL的二维灰度空间中随机选取n个点(s,t)作为初始化粒子的位置,同时也是开始时每个良好的灰度阈值,使得图像的二值化处理能达到最佳效果。如果灰度图像用f(i,j)表示,T表示分割阈值,则二值化过程可以表示如下f(i,j)=1如果f(i,j)T0其它f(i,j)T(9)由于受成像环境的影响,干扰严重,PSO,效果有需要的是图像的边界特,PSO优化算法在,然后以它作为边缘检测算子判别像素点是否为边界点的门限,再经过阈值变换来实现对图像的分割。现以Sobel算子为例,具体描述本文算法如下:步骤1根据给定图像,计算得到其二维直方图;步骤2利用全局PSO算法在二维灰度空间寻找最优阈值(S3,t3),使得目标函数式(5)取最大值;步骤3对图像所有33窗口,用Sobel算子计算梯/doc/e1c4c4bc1a37f111f1855bab.html度;步骤4将最优阈值中的s3作为边缘检测算子中判别目标点是否为边界点的门限T;步骤5按照式(9),对图像进行二值分割。粒子个体最优位置(pBest),并随机初始化每个粒子的初始速度。根据式(7)计算出每个粒子的个体极值(适应度值),全局极值就是个体极值中最大的,录该最大值的序号,)子当前位置。步骤2:(7)计算每一个粒子的适应度值,如果好于该粒子当前位置的个体极值,则将pBest设置为该粒子的当前位置,且更新个体极值。如果所有个体极值中最大的好于当前全局极值,则gBest设置为该粒子的位置,记录该粒子的位置并更新全局极值。步骤3粒子的更新:用式(1)和式(2)对每一个粒子的位置和速度进行更新。步骤4如果达到最大循环次数或其他停止准则,就退出程序,gBest指向的粒子就是最优阈值点(s,t)。否则转到步骤2。336实验结果与分析在我们的仿真实验里,目标球体、椭球体以及三棱柱和立方体四个不同类型的物体被固定在水下1.5m处,在无流静止、有侧面透光干扰及无辅助照明的情况下,利用Ma2troxCoronaII图像采集卡从不同角度和距离采集图像(图1)。图4和图像5分别给出了两幅在水下采集到的大小为576768,具有256个灰度级的图像。为验证本文算法的5基于二维熵和边缘检测的分割算法图像的边缘是图像的最基本特征,所谓边缘是指其周围像素灰度有阶跃变化或屋顶变化的那些像素的集合。物体的边缘是由灰度不连续性所反映的,经典的边缘提取方法是考察图像的每个像素在某个邻域内灰度的变化,利用边缘附近一阶或二阶方向导数变化规律。如果一个像素落在图像中某一个物体的边界上,那么它的邻域将成为一个灰度级的变化带。对这种变化最有用的两个特征是灰度的变化率和方向,它们分别以梯度向量的幅度和方向来表示。常用的边缘检测算子有Roberts算子,Sobel算子,Prewitt算子/doc/e1c4c4bc1a37f111f1855bab.html以及Kirsch算子。一种好的分割技术能够识别图像的边缘并且确定目标的边界。图像分割的过程也就是选择合适的阈值对图像进行二值化的过程,而二值化算法的核心在于如何获得一个有效性,采用两种不同的边缘检测算子,Sobel和Kirsch算子来与本算法进行比较(运行环境:Vc 6.0,CPU为P43.0G,内存为0.98G)。结果显示利用PSO在二维灰度空间搜索最优阈值比利用穷举法搜索阈值在运算时间上提高了10倍以上,而且分割效果比传统检测算子处理效果要好,由于考虑了图像的空间信息,从而对噪声的抑制能力较强。处理结果如图4、图5所示,实验结果表明本算法的性能要优于前两种算法。图4图像A实验结果?1196?系统工程与电子技术第29卷图5图像B本文算法还涉及到PSO利用PSO,子数的选择问题,一般的问题,20左右。随着粒子个数的增加,算法的复杂度也随之增大,另一方面会使得解有多次重复,不利于算法的收敛性。根据Shi和Eberhart的研究7,PSO的性能对粒子数目大小并不敏感。但是通过对水下图像的处理,我们发现选取粒子数目在10-12之间为最佳,粒子数目一旦超过12个,不但运算时间增加,同时获得最优解的几率也降低了。此外惯性权重以及加速度常量对算法的性能也很关键,根据VandenBergh的研究8,为保证算法收敛,惯性权重和加速因子c1,c2需要满足,具有很好的抗噪性,这两点对于实时性要求很高的水下任务来说显得尤为重要,因此对水下图像处理及识别系统的研究有很大的意义。参考文献:1PunT.Entropicthresholding:anewapproachJ.ComputerVisionGraphicsandImageProcess,1981,16(2):210239.2KapurJN,SahooPK,WongAK/doc/e1c4c4bc1a37f111f1855bab.htmlC.Anewmethodforgray2levelpicturethresholdingusingtheentropyofthehistogramJ.ComputerVisionGraphicsImageProcess.1985,29(3):273285.3AbutalebAS.Automaticthresholdingofgray2levelpicturesu2singtwo2dimensionentropyJ.ComputerVisionGraphicsandImageProc.,1989,47(1):222-132.4KennedyJ,EberhartRC.ParticleswarmoptimizationCProc.oftheIEEEInternationalConferenceonNeuralNet2works,1995:19