（计算数学专业论文）自适应canny算法研究及其在图像边缘检测中的应用.pdf

摘要 摘要 边缘包含了图像大部分信息，边缘检测是图像处理和分析的关键步骤，对后 续高层次的特征描述、匹配和识别等有着重大的影响。 本文首先对一些传统的边缘检测算法和近年来广泛受到关注的边缘检测算 法进行了综述，同时将其中传统的边缘检测算法进行了代码实现并给出相应的分 析。 然后分析了遗传算法的特点及其适用的问题，再将遗传算法应用到传统的 c a n n y 算法中，提出了一种基于改进遗传算法的自适应c a n n y 边缘检测算法。该 算法能够很好的解决传统算法中阈值难以自动选取的问题，提高了算法对不同图 像的自适应性。同时，改进后的c a n n y 算法在图像梯度幅值的计算方法和非极大 值抑制上都采用了新的方法，能够很好的提高图像边缘检测的精度和准确度，并 且一定程度上抑制了噪声对检测结果的影响。 在文章的最后，我们将改进的自适应c a n n y 算法在v i s u a lc + + 下进行编程 实现，并通过多个图像检测结果将其与传统算法进行了对比分析。 改进的自适应c a n n y 算法在保持了c a n n y 算法原有的定位准确、单边响应和 l 信噪比高等优点的基础上，提高了c a n n y 算法在提取图像边缘细节信息和抑制假 边缘噪声方面的性能。 关键词：边缘检测；改进c a n n y 算法；遗传算法；自适应性；阈值选取； a b s t r a c t a b s t r a c t e d 萨c o r c a m sam a j o r i t yo fi n f o r m a t i o no fi m a g e ，s oe d g ed e t e c t i o ni s ac r i t i c a l s t e p f o ri m a g ep r o c e s s i o na n da n a l y s i s ，w h i c hh a ss i g n i f i c a n ti n f l u e n c eo i lt h e c h a r a c t e r i s t i cd e s c r i p t i o n , m a t c h i n ga n dr e c o g n i t i o na f t e ri t i nt h i sp a p e r , t r a d i t i o n a lm e t h o d sa n ds o m en e we d g ed e t e c t i o nm e t h o d si s i n t r o d u c e d w ea l s or e a l i z ea n da n a l y s et h et r a d i o n a lm e t h o ds a f t e rt h a tw ed i s c u s st h ec h a r a c t e r i s t i ca n da p p l i c a t i o n so fg e n e t i ca l g o r i t h mi n i m a g ep r o c e s s i n gf i e l da n dp u tg a i n t ot r a d i t i o n a lc a n n ya l g o r i t h m t h e n , a na d a p t i v e c a n n ya l g o r i t h mo f e d g e d e t e c t i o nm e t h o db a s e do na ni m p r o v e dg e n e t i ca l g o r i t h m i s p r o p o s e d t h en e wm e t h o dh a sa d a p t i t u d ea n dc a n s o l v et h ep r o b l e mo f a u t os e l e c t i o n i nt h ee d g ed e t e c t i o no ft h et h r e s h o l d i nt h em e a nt i m e , t h en e wa l g o r i t h mu s e sn e w m e t h o di nt h ec o m p u t a t i o no ft h eg r a d sa n dn o n - r m x i m as u p p r e s s i o nt h a tc a n i p m r o v et h ep r e c i s i o no f t h ed e t e c t e de d g e i nt h el a s tp a r toft h i sp a p e r , w er e a l i z et h ei m p r o v e da d a p t i v ec a n n ya l g o r i t h m b a s e do n 垤u a lc + + a n dc o m p a r e dw i t ht r a d i t i o n a la l g o r i t h mb yd e t e c t i o nr e s u l t s t h ei m p r o v e da d a p t i v ec a n n ya l g o r i t h mn o to n l yk e e p st h ec a n n y se x c e l l e m p e r f o r m a n c ei ng o o dl o c a l i z a t i o n ，o n l yo n er e s p o n s et oas i n g l ee d g ea n dg o o d d e t e c t i o n ，b u ta l s oi m p r o v e st h ep e r f o r m a n c ei nt h ed e t a i le d g e d e t e c t i o na n dg o o d d e t e c t i o n k e yw o r d s ：e d 萨d e t e c t i o n ；i m p r o v e dc a n n ya l g o r i t l m a ；g e n e t i ca l g o r i t h m ； a d a p t i v e ；c h o s e no f t h r e s h o l d ； 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝江盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：彳，卅 签字日期：娜予年多月，日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘堂有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘鲎 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：沙叼年 l 各印f 厂r 勿月 弋日 、 聊躲狲 签字日期：枷口彳年6 月厂日 致谢 致谢 本论文的完成，首先要感谢我的导师吴庆标教授，是导师悉心的指导和帮助 才使我的论文得以顺利完成。吴老师自始至终给予了我无微不至的关怀，他在百 忙之中经常抽空关心我的课题和论文进展情况，并不断给予好的建议和思路。我 取得的每一点成绩都凝结着导师的辛勤汗水和培养，让我难以忘怀，他渊博的知 识和认真的治学态度使我受益非浅，在此向他表示深深的谢意。 在研究生两年的学习和最后的毕业设计期间，班级中多位同学都给予了我很 大的帮助，在此对所有同学表示由衷的感谢。 最后，我还要感谢我的父母和姐姐，我能完成今天的论文，离不开家人对我 在生活和学习上的支持和鼓励。 第一章概述 第一章概述 1 1 研究背景 图像是人类认识世界的重要信息来源。边缘存在于图像的不平稳现象和不规 则结构中，也存在于信号的突变点处，往往携带着图像的大部分信息。这些边缘 点能够大致的给出目标轮廓的位置，而这些轮廓常常包含着我们在图像处理时所 感兴趣目标的重要特征，是形状检测的基础，同时也是图像分割所依赖的重要特 征，它为人们描述或识别目标以及解译图像提供了重要的特征信息。 边缘检测是图像处理领域中最基本的问题，也是最经典的技术难题之一。该 问题的解决对于进行高层次的特征描述、特征提取、目标识别和图像理解等有着 重大的影响。因此，边缘检测在图像分割、计算机视觉、模式识别等众多方面都 有着非常重要的地位。但由于成像过程中的投影、混合和噪声等原因导致图像的 模糊和变形，边缘往往难以被检测，因此人们一直致力于构造具有良好性质的边 缘检测算子。对边缘检测的研究有着久远的历史，其原因一方面是由于课题本身 的重要性，另一方面也反映了这个课题的深度和难度。所以，对边缘检测方面的 研究有着十分重要的理论和实际运用意义。 所谓边缘是指那些其周围像素灰度值有阶跃性变化或屋顶状变化的那些像 素的集合。边缘存在于目标与背景、目标与目标、基元与基元、区域与区域之间。 因此它是图像分割所依赖的重要的根据，也是纹理特征的重要信息源和提取形状 特征的基础，而图像的纹理形状特征的提取又常常依赖于图像分割。图像的边缘 提取也是图像匹配的基础，因为它是位置的标志，对灰度的变化敏感，它可作为 匹配的特征点。 图像的大部分主要信息都存在于图像的边缘中，主要表现在图像中灰度变化 比较剧烈的地方，导致图像局部特征不连续性，也即我们通常所说的信号发生突 变的地方。奇异信号沿边缘走向的灰度变化剧烈，通常我们将边缘划分为有三种 ( 如下图所示) 。第一种是阶梯形边缘，即从个灰度值跳到比它高很多的另一 个灰度值。第二种是屋顶型边缘，它的灰度值慢慢地增加到定程度然后慢慢地 减小。第三种是线性边缘，它的灰度值从一个级别跳到另一个灰度级别然后再跳 第1 页 第一章概述 回来。 j j 屋顶式边缘 阶梯形边缘 图：边缘的三种类型 线性边缘 边缘具有方向和幅度两个特征。沿边缘走向，像素值的幅度变化比较平缓； 垂直边缘走向，像素值的幅度变化比较剧烈。这种剧烈的变化可能呈现出阶跃状， 也可能呈现出斜坡状。所以边缘上像素值的一阶导数较大；二阶导数在边缘处值 为零，呈现零交叉。 著名的“马赫带效应 指出：人的视觉对物体光度变化的部分有特殊的增强 效应，且在不同光强度区的边缘周围引起“过量调整 。物体边缘特征是与图像 中灰度突变的部分相对应的。因此，基于灰度的不连续性特征检测的方法成为图 像边缘检测的主要方法之一。在众多视觉模块计算中，通常把边缘检测作为视觉 计算的第一步，高层次计算机视觉处理能否成功极大地依赖于边缘检测算子的性 能是否优越。 最经典的、简单的边缘检测方法是对原始图像按像素的某邻域构造边缘检测 算子。由于原始图像往往含有噪声，边缘和噪声在空间域表现为灰度有比较大的 变化；而在频域则反应为同是高频分量，这就给边缘检测带来一定的困难。 m a r r 和h i l d r e t h 提出了一种十分有效的零交叉边缘检测方法，他们指出边缘 检测过程中的两点现象：其一，图像灰度值的突变会在一阶导数中产生一个极大 值或等价于二阶导数中产生一个零交叉；其二，图像中的强度变化是以不同的尺 度出现的，故应用若干大小不同的算子才能取得良好的检测效果。 第2 页 镕一 下圈是某国像及其边缘图像： 由于实际处理的闰像一般都是含有噪声的，所以在提取边缘的同时还需要考 虑运用的方法是否有较好的抗噪性，是否能够消除噪声干扰带来的伪边缘。由上 述可知，边缘检测方法的优劣直接影响着图像特征提取及其他后续处理，是图像 预处理中的关键。鉴于边缘检测技术的重要性，在此我们有必要对边缘检测技术 进行讨论。 1 2 边缘检测的发展与现状 边缘检渊的发展可追溯到2 0 世纪6 0 年代，r o b e r t s 提出的基于梯度的边缘检 测是迄今仍然适用的一种有效的算法。之后在2 0 世纪7 0 年代提出的p r e w i t t 算予， k i r s c h 算子，r o b i n s o n 算子等，也都是传统的基于梯度豹边缘检测算子，其大部 分为局域窗口梯度算子。由于它们对噪声很敏感，所以对实际图像的处理效果并 不是很理想。为了研究如何提取受噪声干扰严重的图像边缘，近十几年来缀多学 者采用不同的方法，如基于二阶导数的零交叉点定位边缘算法，利用梯度及局部 极大值的边缘检测算法，基于小波的边缘检测算法，基于神经网络及数学形态学 的边缘检测算法，基于仿射变换和特征空间的边缘检测等。其中1 9 8 6 年由c a n n y 提出的最佳边缘检测算子以其在处理受高斯白噪声污染的图像方面的良好效果 而成为其它边缘检测算子性能评价的标准。在本文中正是对传统的c a n n y 算法进 行改进，以提高其算法的自适应性。 第3 第一章概述 由于图像的多样性和复杂性，人们仍在不断的探索其它更有效的边缘检测算 子。其中第一个要解决的问题是图像边缘像素的不连续性，不连续的边缘构成的 图像没有任何实际的意义，所以必须用附加处理将边缘聚集成更适于解释过程的 连续边缘。同时还要解决边缘检测中的检测过度，伪检测等问题，例如在许多并 非边界的地方，常常出现伪边缘像素，相反，在真正有意义的边界处却缺少边缘 像素。边界检测算法中，往往以已有知识为前提，增加或简化处理过程和计算量， 以求得到好的效果。 从边缘检测研究的历史来看，可以看到对边缘检测的研究有以下几个趋势： ( 1 ) 不断改进原有算法。 ( 2 ) 对特殊图像边缘检测的研究。目前有很多针对3 维图像、彩色图像、多光 谱图像以及多视场图像分割的研究，也有对运动图像及视频图像中目标分割的研 究。还有包括对纹理( t e x t u r e ) 图像、计算机断层扫描( c t ) 图、核磁共振图像、 共聚焦激光扫描显微镜图像、合成孔雷达图像等特殊图像的边缘检测技术的研 究。 ( 3 ) 将新概念、新方法以及多种方法综合的运用到图像边缘检测中。人们逐 渐认识到现有的单一的边缘检测算法很难从一般图像中检测得到令人满意的边 缘图像，因此很多人在把新方法和新概念引入边缘检测领域的同时，也更加重视 把各种方法综合起来运用。如基于小波变换的边缘检测方法就是一种很好的方 法。 ( 4 ) 交互式检测研究的深入。由于很多交互式场合需要对目标图像进行边检 边分析，例如对医学图像的分析，因此需要进行交互式检测研究。并且交互式检 测技术有着很高的实用价值和广泛的应用。 ( 5 ) 对图像边缘检测评价的研究和对评价系数的研究。如何对一个边缘检测 算法给出量化的评价方法是人们一直关心的问题。 本文中所提到的算法就属于第一和第三类，我们在传统的c a n n y 算法上进行 改进并将遗传算法运用其中，以取得更好的效果。 第4 页 第一章概述 1 3 边缘检测过程 一般边缘检测算法的过程为： 1 对原始图像经过平滑滤波，得到平滑图像。 2 使用各种算法可以得到边缘增强的图像，得到的图像为2 5 6 灰度级的图像。 此时，图像灰度平滑平缓的区域已经没有了，图像中只剩下了灰度突变的地方。 3 运用算法对图像突变进行增强处理。 4 经过阈值分割，将2 5 6 级图像变成2 值图像，将边缘突变明显的显示出来， 就得到了边缘图像。 使用平滑过程是因为各类算法中的导数计算对噪声十分敏感，因此必须使用 滤波器来改善与噪声有关的边缘检测器的性能。 i 一1 _ ji 一i _ j - _ j 图：边缘检测过程 第5 页 第二章边缘检测算法 第二章边缘检测算法 2 1 传统边缘检测算子 2 1 1 基于梯度的边缘检测 梯度对应一阶导数，梯度算子就是一阶导数算子。对于一个灰度图像函数 m 川，其梯度可表示为一个向量：可k y ) = 圈= 苛 砂 反 差分算子能够精确的获得一阶差分和二阶差分的边缘，并且边缘都在差分值 最大处、最小处或过零点处发生。 图像可以表示成一个离散化的二维灰度值函数i ( x ，y ) ，边缘的强度就是在 该点处沿着灰度变化最剧烈的方向的灰度变化率，我们用梯度的二范数来度量边 缘的强度，即在点i ( x ，少) 处，梯度的幅值可用下式表示： 朋口g ( 夥) = + 嘭 “2 梯度向量的方向为： 嘶= a r c 伽 对每个像素都要进行以上各式的偏导数计算，在实际中常用区域模板对图像 进行卷积来近似计算。分别对q 和g ，各用一个模板，然后将两个结合起来就构 成一个梯度算子。根据模板不同的大小和不同的元素值构造不同的算子，常见的 有r o b e r t s ，s o b e l ，p r e w i t t 边缘检测算子等。 2 1 1 1r o b e r t s 边缘检测算子 根据任一个相互垂直方向上的差分都可用来估计梯度，r o b e r t 算了采用对 角方向相邻两像素之差，即 q - f ( x ，y ) - f ( x - 1 ，y - 1 ) 第6 页 第二章边缘检测算法 q2 【x - - 1 ，少j 一【x ，y 一1 j 其幅值：g ( x ，y ) = + g 珂2 佗 r o b e r t 梯度以( z j 1 ，y 一丢) 为中心，所以它度量的是( 工一j 1 ，少一丢) 点处相互 正交的4 5 。和1 3 5 。方向的像素灰度值变化。然后适当取阈值丁，当g ( x ，y ) 丁时， 则( 石，y ) 点为边缘点。 r o b e r t 边缘检测算子相当于用模板 二三 和 三二 对图像进行卷积。 2 1 1 2p r e w i t t 算子和s o b e l 算子 毋= ( ； = 三i 三i s = ；言； 足= 三三 分别用上述模板对图像做卷积，如果毋( 墨) 的响应是z ，b ( 是) 的响 应是y ，则可根据下式就出图像的幅值： 正2 + y 2 或l x l + l y i 第二章边缘检测算法 边三个像素( 像素1 ，像素2 和像素3 ) 的像素值的加权平均值f l 和右边三个像素 ( 像素4 ，像素5 和像素6 ) 的像素值的加权平均值f r 1 4 205 36 图l f l = 口l e + 吃e + e f r = q 只+ 口2 e + 瓦 其中， o ，待1 ，2 ，3 j l a , + + 鸭= 1 ，鼻为第i 点的像素值。然后用f r f l 估计 像素0 的水平方向的方向导数，由于我们关心的只是梯度的相对大小，因此可以 忽略模板的系数。这种方法要比仅仅使用单一的像素2 和像素5 处灰度值的差估计 像素0 处水平方向的方向导数要更加的稳健。因为单一像素的灰度值容易受到图 像的噪声的影响，从而影响到方向导数值的计算。相比之下，多个像素值的均值 要更加的稳定。 p r e w i t t 算子、s o b e l 算子和各向同性s o b e l 算子的区别仅仅在于它们加权时 采用的权重a i 不同。p r e w i t t 算子采用的是简单的平均，即像素1 、像素2 和像素3 使用相同的权重系数。从逼近论的角度上来说，离像素0 越近的像素对0 的差分估 计越准确，所以应该通过像素间距离的反比对像素值进行加权。s o b e l 算子使用 城市距离作为度量距离的方法，像素0 与像素1 、象素3 间的距离为2 ，与像素2 的 距离为1 。所以像素1 和像素3 的权重为1 ，像素2 的权重为2 。而之后也有人提出 i s o t r o p i cs o b e l 算子。该算子则是使用了欧氏距离，像素0 和像素1 、象素3 的距 离为互、和像素2 的距离为1 。所以像素1 和像素3 的权重为1 ，慷2 的权重为互， 因为i s o t r o p i cs o b e l 算子使用欧氏距离，所以具有各向同性性质。 2 1 2l o g 算法 第8 页 第= 章进缴检测算法 m a r t 和h i l d r e t h 将高斯滤波和拉普拉斯边缘检测结合在一起，形成l o g 算法， 也称之为拉普拉斯高斯算法( l a p l a c i a no fg a u s s i a n ) 。 二元函数f ( x ，y ) 的拉普拉斯变抉定义为： v 2 ，= ( 嘉+ 参 m 川= 笔笋+ 等垃 由于一阶导数对噪声是敏感的，所咀二阶导数对噪声会更加的敏感，因而更 不稳定。所以在做拉普拉斯变换之前做平滑是必需的。因此，我们首先用高斯函 数对图像进行平滑处理( 即低通滤波) ，再用拉普拉斯算子进行高通滤波，最后 根据图像的二阶导数过零点来检测图像的边缘。 高斯滤波函数：g ( y ) = 2 。1 ：唧【一! 。其图像如下 图：高斯溏波函数 j 是高斯滤波器标准方差，决定图像的平滑程度。 对平滑后的图像做拉普拉斯变换，得：g ( x ，y ) = v 2 g ( x ，y ) + ，( z ，) 。根 据卷积求导法则知道先对图像平滑，再进行拉普拉斯变换，等效于把拉普拉斯变 换作用于平滑函数，由此可以得到一个兼有平滑和二阶微分作用的模板，再与原 来的图像进行卷积。即：g ( 五y ) = 甲2 g y ) i ( x ，y ) 由炳舭滤波獠v 2 吣棚= 专b 刮e 冲( - 专爿 下图即为l o g 滤波器的图像，可看出其形状类似草帽，故又称之为草帽滤波 器。 第= 章边缎检测算法 图：l o g 滤波器 l o g 算法的基本特征： ( 1 ) 采用高斯滤波器作为平滑滤波器。 ( 2 ) 采用二维拉普拉斯函数进行图像增强。 ( 3 ) 边缘判断依据是二阶导数零交叉点并对应一阶导数的较大峰值。 用l o g 模板与图像进行卷积的优点在于摸板可阻预先算出在实际的计算过 程中我们可以直接调用计算好的模板对图像进行卷积即可。 2 13 实验结果及分析 对强上各个算子，将其在v c 60 t 编程实现。我们对两幅图像l e n a 和b l o o d 进行边缘检测。 第1 0 页 第= 章边缘检测算法 r o b e r t s 算子定位比较精确，但由于不包括平滑，所以对于噪声比较敏感， 并且容易丢失部分边缘。对灰度变化陡峭的低噪声图像处理效果较好，处理对比 度低且较暗圈像的能力较差。 ( 2 ) s o b e l 算子与p r e w i t t 算子处理结果 s o b e l 算子取阈值t = 5 0 第i 1 页 第二章边缘检测算法 p r e w i t t 算子取阈值t = 5 0 s o b e l 算法和p r e w i t t 算法都是一阶的微分算子对图像进行差分和滤波，前者 是平均滤波，后者是加权平均滤波。因此，对噪声具有一定抑制能力，但所得图 像会有些模糊。同时从图像中可看出边缘定位较准确且完整，但容易出现边缘多 像素宽度。 ( 3 ) l o g 算法 我们取5 乘5 的模板 24 _ 4o _ 48 40 之_ 4 - 4 4 2 8o4 2 48_4 8o-4 4o - 2 第1 2 页 作为l o g 滤波算子。 第二章边缘检测算法 取阈值- - 5 0 时 取阈值= 1 5 0 时 l o g 滤波器方法通过检n - 阶导数过零点来判断边缘点。l o g 滤波器中的标准 方差仃正比于低通滤波器的宽度。仃越大，平滑作用越显著，去除噪声越好，但 图像的细节也损失越大，边缘精度也就越低。所以在边缘定位精度和消除噪声之 间存在着矛盾，应该根据具体问题对噪声水平和边缘点定位精度要求适当选取。 但是l o g 方法没有解决如何组织不同尺度滤波器输出的边缘图为单一的、正确的 边缘图的具体方法。 2 2 新边缘提取方法 2 2 1 数学形态学方法 第1 3 页 第二章边缘检测算法 j s e r r a 将数学形态学方法运用到图像处理领域。在数学形态学中用于图像 处理的两种基本运算是腐蚀和膨胀，它们的不同组合形成开运算和闭运算。图像 经过边缘强度算子作用后，在屋顶边缘处形成凹谷，在跳跃边缘处形成凸脊，再 将其与原图像做差分则得到边缘。利用数学形态学方法进行边缘边缘，选择到合 适的结构元是十分重要的，结构元选得好，则噪声滤除得干净，同时边缘细节也 保存完好。 2 2 2 小波分析法 近年来小波分析在图像处理的各个方面都得到了应用。小波可以在不同的尺 度上得到信号的细节。用小波进行图像边缘检测的主要思想为：从信号处理的角 度上看，边缘表现为信号的奇异性。而从数学角度上看，奇异性由l i p s c h i t z 指 数标志。小波理论已经证明l i p s c h i t z 指数可由小波变换的跨尺度模极大值计算 得到，所以只要检测小波变换的模极大值即可检测出边缘。利用小波的多尺度特 性可以实现在大尺度下抑制噪声，可靠地识别边缘，在小尺度下精确定位。 2 2 3 神经网络法 神经网络算法有着强大的非线性表示能力，在模式识别等方面有较多成功的 应用，同样也运用到了图像边缘检测过程中。其主要思想为：先将输入图像映射 成某种神经网络，然后输入一定先验知识，即原始边缘图，再进行训练 ( t r a i n i n g ) ，直到学习过程收敛或用户满意。由于神经网络提取边缘利用了原始 图像的已有知识，是从宏观上认识对象，微观上提取细节，所以有很强的抗噪能 力。但是对于先验知识确的得到是一个难题。 第1 4 页 第三章遗传算法及其在图像处理的应用 第三章遗传算法及其在图像处理的应用 3 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ) 是模拟达尔文的遗传选择和自然淘汰的生物 进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由 美国教授j h o l l a n d 于1 9 7 5 年首先提出来的，并出版了颇具影响力的专著 a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ，才使遗传算法g a 这个名 称才逐渐为人所知，j h o l l a n d 教授所提出的g a 通常称为标准遗传算法( s g a ) 。 遗传算法是从需求解问题中可能潜在的解集的一个种群( p o p u l a t i o n ) 开始 的，一个种群则由经过基因( g e n e ) 编码的一定数目的个体( i n d i v i d u a l ) 组成。每 个个体实际上携带特征染色体( c h r o m o s o m e ) 的实体。染色体作为遗传物质的主要 载体，包含了多个基因的集合，其内部表现是某种基因组合，它决定了个体的形 状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定 的。因此，算法刚开始需要实现从表现型到基因型的映射编码工作。由于仿照基 因编码的工作很复杂，我们往往进行简化，如二进制编码。初代种群产生之后， 按照适者生存和优胜劣汰的原理，逐代( g e n e r a t i o n ) 演化产生出越来越好的近似 解。在每一代，根据问题域中个体的适应度( f i t n e s s ) 的大小选择( s e l e c t i o n ) 个体，并借助于遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异 ( m u t a t i o n ) ，产生出代表新的解集的种群。这个过程将使种群像自然进化一样， 后生代种群比前代更加适应于环境，将末代种群中的最优个体经过解码 ( d e c o d i n g ) ，即可以作为问题近似最优解。 3 1 1 适用的问题 由于遗传算法的优化搜索方法和整体搜索策略是不依赖于梯度信息或其它 辅助知识，而只需要知道搜索方向的目标函数和相应的适应度函数，所以遗传算 法提供了一种求解复杂系统问题的通用框架。它不依赖于问题的具体领域，对多 种问题有很强的鲁棒性，所以广泛应用于许多科学，下面介绍一下遗传算法应用 第1 5 页 第三章遗传算法及其在图像处理的应用 的一些主要领域： 1 、 函数优化 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算 例。许多人构造出了各种各样形式复杂的测试函数：离散函数和连续函数、低维 函数和高维函数、凸函数和凹函数、单峰函数和多峰函数等。对于一些非线性、 多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方 便的得到较好的结果。 2 、组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的 计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要 精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证 明，遗传算法对于组合优化中的n p 问题非常有效。例如遗传算法已经在求解背 包问题、图形划分问题、装箱问题等方面得到成功的应用。 此外，遗传算法在图象处理、机器人学、自动控制、生产调度问题、人工生 命、遗传编码和机器学习等方面获得了广泛的运用。 3 1 2 遗传算法流程 臣亟垂圜 i 第1 6 页 第三章遗传算法及其在图像处理的应用 遗传算法以编码空间代替问题的参数空间，以适应度函数为评价依据，以编 码群体为进化基础，以对群体中个体的遗传操作实现选择和遗传机制，建立起迭 代过程。在此过程中，通过随机重组编染色体中重要的基因，使新一代的染色体 集合优于老一代的染色体集合，群体的个体不断进化，逐渐接近最优解，最终达 到求解问题的目的。 遗传算法的计算流程如上图所示，具体求解步骤如下： ( 1 ) 初始化。选择合适的编码方案，对个体进行编码。同时确定合适的参数， 包括群体规模m 、交叉概率p c 和变异概率p m 。 ( 2 ) 个体评价函数确定。即确定适应值函数f ( x ) ，一般是求合适值最大，如 果求最小则可求- f ( x ) 最大，f ( x ) 应为正值，否则可以加上一个固定常数。 ( 3 ) 随机生成初始群体( 含m 个个体) 。 ( 4 ) 对每个个体计算适应值f i ，同时计算群体的总适应值： ，= j c ( 5 ) 选择操作，计算每一个个体的选择概率暑2 参累计概率吼2 善弓，以 轮盘赌法选择出一定数量的个体。 ( 6 ) 交叉操作 对每个个体产生【o ，1 】间随机数r ，若r p c ( 交叉概率) ，则该个体参 加交叉操作，否则不参加，如此选出参加交叉的一组后，随机配对； 对每一对，产生 o ，叫间的随机数以确定交叉的位置，然后在该位置 进行交叉操作。若进行多点交叉操作，则随机选定多个位置进行操作。 ( 7 ) 变异操作 0 对每个个体中的每位产生【o ，1 】间的随机数r ，若r - v 2 ，则m ( g ) 为极大值 点；否则m ( g ) 为非极大值。 插值方法二： 插值方法一实际上是用了梯度前后方向上的两个点进行插值。同样的，我们 还可以利用梯度方向的4 个点进行双线性插值。首先对于各个中心点m ( i ，- ，) 将 其周围领域点分成4 个象限，再根据中心点的梯度方向o ( i ，) 判断采用哪个象限 中的领域像素进行插值。区域的划分可以直接根据g x 与g y 的符号判断出来。即 当o ( i ，) 0 。时( g x 与g y 异号) ，m - 、四象限邻近4 个像素的双线性插值进行 比较；当9 ( f ，_ ) 0 。( 即g x 与g y 同号) 时，用一、三象限邻近4 个像素的双线 性插值进行比较。 a 当g x 与g y 同号时，采用第一、三象限4 点像素插值： 第2 8 页 第日章改进的自适应o n n y 算法研究 。第一象限x 方向利用m ( i ，+ 1 ) 与m ( i + i ，+ 1 ) ，m ( i ，) 与m ( i + i ，j ) 阻 及比例c o s p ( j ，j ) 进行插值： f = m p ，+ 1 ) + 8 口( f ，明 m o + k j + 1 ) 一m ( f ，+ l 妇 k - = m ( j ，j ) + o p o ，j ) m ( n l ，j ) 一m ( w ) y 方向利用蝇。与 矗，以及比例s i n p ( f ，明进行插值： m 1 = m l ，+ s l n o ( i ，明( ，一帆。) o 第三象限x 方向利用】l ，( 卜1 ) 与m ( i 一1 ，y - o ，m ( j ) 与m ( i - i ，j ) 以 及比例c o s p ( j ，y ) m e m m ： f = m ( 叫一1 ) + 8 口( ) 阻( 一l , j 一1 ) 一m ( j j 1 ) 旧：= m ( w ) + c o s p ( f ，j ) 材( z l ，j ) 一m ( ) y 方向利用 毛：与 t ：以及比例s m p ( f ，明进行插值： m 2 = m 。：+ s i n o ( i ，明( 屿：一蝇：) 通过o ，o 两个步骤即求出了需要和当前点m “) 进行比对的双线性擂值结果 m l 与m 2 。 第2 9 页 第四章改进的自适应o n n v 算法研究 b 当g x 与g y 异号时，采用第二、四象限4 点像素插值 。第二象限x 方向利用m ( i j + o - 与m ( i l ，+ i ) 盯“，) 与m ( i l ，) 以 及比例o o s p ( j ，) 进行插值： f = m ( b j + 1 ) + c o s 口( ) m ( 一u + 1 ) 一m ( b j + 1 ) 池，= m ( b j ) + c o s 8 ( 。，) x 阻( 一j ) 一村( b j ) y 方向利用m 。与峨，以及比例s m p ( f ，j ) m e m m ： m 3 = m l ，一s i n 吣明x ( ，一帆，) o 第四象限x 方向利用m ( i , j i ) 与m ( + i ，一1 ) ，肼“，) 与m ( i + i ，j ) 以 及比例c o s p ( f ，力 进行插值： 【= m “j 1 ) + c o s 烈k j ) 阻( ，+ u l 卜村( b j 1 ) 【= 盯( i ，j ) + t * p ( 1 j ) x m ( h u ) 一m ( b j ) y 方向利用m 。与地。以及比例咖 口( j ，j ) m 行m m ： m 4 = m l 。一s i n o ( i ，明( 帆一帆。) 再求出m 3 和m 4 之后就可以进行局部极大值的判断比对： 若m ( 一，j ) 盯l 且m ( r ，j ) m 2 ( 村“，) 2 m 且肘( f ，) m 4 ) ，则m ( i ，) 为极 第如 第四章改进的臼适应c a n n y 算法研究 大值点；否则m ( i ，) 为非极大值。 改进的非极大值抑制方法中，采用了插值的方法来将当前点与插值结果的点 进行比较，用以判断是否为局部最大值，更加精确的定位了边缘。 4 2 3 阈值自动选取 在阈值选择方法上，可以采用图像分割中由o s t u 提出的最大类间方差法。 该方法是在判决分析最小二乘法原理的基础上推导得出的，其基本思想是：把图 像中的像素按灰度值用阈值t 划分成目标类c 0 和背景类q ，c o 由灰度值在0 t 之间的像素组成，q 由灰度值在( f + 1 ) ( 一1 ) ( l 为图象主灰度级数) 之间的像 素组成，设仃( f ) 2 为类间方差，则最优阈值f 是使仃( f ) 2 取最大值时对应的灰度级， 即 万( r ) 2 = ( ，) 宰w 2 ( ，) 宰( ”。( r ) 一甜：( f ) ) 2 盯( ，+ 2 - - - - t 鼢) 仃( r ) 2 其中t 表示用来处理图像的阈值，啦( f ) 表示图像中灰度值小于阈值t 的像 素的个数，( f ) 表示图像中灰度值大于阂值t 的像素的个数，“。( f ) 表示图像中 的灰度值小于阈值t 的像素的平均灰度值，甜：( t ) 则表示图像中灰度值大于阈值 t 的像素的平均灰度值。 对于c a n n y 边缘检测算法中，我们需要处理的是已经计算好的梯度幅值图 像，并且我们需要的并不是灰度值阈值，而是梯度大小的阈值。所以对于上式中 的各个变量都有类似的定义。( f ) 表示梯度幅值图像中梯度值小于阈值t 的像 素的个数，w 2 ( f ) 表示梯度幅值图像中梯度值大于阈值t 的像素的个数，材。( f ) 表 示梯度幅值图像中的梯度值小于阈值t 的像素的平均梯度值，屹( t ) 则表示梯度 幅值图像中梯度值大于阈值t 的像素的平均梯度值。 可以看出最大类间方差是求一个全局最优解的问题，因此，我们可以利用遗 传算法在求解最优解的优势来解决问题。 钨3 1 面 第四章改进的自适应c a n n y 算法研究 我们的目标就是通过遗传算法，找出使得盯( f ) 2 最大的t 的值，作为我们边 缘检测的阈值。本算法中，我们选用仃( 矿= w l ( f ) 木w 2 ( f ) 木( 甜。( f ) - - u 2 ( f ) ) 2 作为遗 传算法中的适应度函数计算。 基本算法如下： 1 我们处理的都是2 5 6 级灰度图像，其各点梯度值不会超过1 0 2 4 ( 即使超 过也可统一修正到1 0 2 4 以下) ，故编码方式就采用十位二进制编码的方式。在 0 1 0 2 4 之间随即的生成2 0 个个体u 一。作为初始种群。 2 在选择的方式中我们采用轮盘赌方法选择需要进行杂交操作的个体，每次 选出两个。选出两个个体后，根据一定的杂交概率随机的选取在某一位开始进 行杂交运算，生成两个新个体。不断重复，直到生成新一代的群体u 一啄。 3 从u 。一中由一定的变异概率己随机的选择若干个个体，再随机的 在这若干个个体中选择某一位进行变异运算，形成群体u 一一。一。 4 判断是否达到指定生长代数，若尚未达到，则以u 一。作为新的群体转 至i f2 ，否贝i i 贝i i 停i 匕。 在生成的各代群体中我们采用一个最优保存策略：即为了防止杂交和变异操 作破坏上一代群体中的适应度最高的解，我们将上一代群体配一以。中适应度最 高的个体与群体n v , 一一【，加一中适应度最低的个体进行比较，若前者的适应度比 后者的适应度高，则用前者替换掉后者，否则什么也不做。这样做的目的是防止 种群的退化而导致收敛速度过慢，能显著的加快收敛速度。经过这一步，就形成 最终的新一代的群体抛一以。 但是传统的遗传算法会出现过早的收敛到局部最优解而并非全局最优解，即 所谓的“早熟 现象。为了避免“早熟 现象，对传统遗传算法进行一定的改进。 首先，我们利用上述基本的遗传算法进行较少次数的迭代以产生一个适应度较大 的个体u 一。然后我们在的一个u 区间【u 眦一u ，+ u 】内再次随机的生 第3 2 页 第四章改进的自适应c a n n y 算法研究 成初始种群，并且在利用传统的遗 寻得的是一个较好的准最优解，我们仍采用最优保存策略，将第二次寻优生 成的群体中适应度最大的个体与第一次寻优的进行比较，取其中适应度大的 个体作为最终的阈值。 随着种群的进化，部分高适应度的优良个体的指数级增长使得种群中大部分 个体的染色体基因趋于一致，使得种群的多样性逐渐减小。随着进化过程中种群 多样性的丧失，交叉操作的搜索能力开始减弱并逐渐失去作用，而标准遗传算法 中的变异操作概率一般较小，当种群出现过早收敛的趋势时，难以有效地增加种 群多样性，导致算法缺乏跳出局部最优解的能力，使早熟现象的发生。可见，种 群多样性的过早丧失是早熟现象发生的根本原因。而交叉概率，变异概率不变是 一个重要的原因。 若要使遗传算法本身具有自适应性，即在遗传算法中对每一代群体的交叉概 率和变异概率能够自动的选择，而非使用固定值。m s r i n i v a s 提出的自适应遗 传算法可以很好的解决这个问题。这种算法根据每代个体适应度的改变来自适应 地计算交叉概率和变异概率，在保护最优个体的同时，加快了较差个体的淘汰速 度。但是由于该算法于对每个个体都要分别计算交叉概率和变异概率，会影响程 序的执行效率。为了避免算法的复杂度过高，这里只是简单的提下，具体的在后 面讲述。 4 2 4 算法过程 通过上述改进之后，我们可以得到改进的自适应的c a n n y 算法，其主要算法 过程如下： 步骤l ：图像平滑，与原始算法相同。 步骤2 ：翮改进的3 x 3 领域模板对图像做卷积，求出相应梯度大小和方向。 步骤3 ：利用多点插值结果与中心像素比对进行非极大值抑制。 步骤4 ：将遗传算法运用到步骤2 中得到的梯度图像中，以选取适当的阈值。 第3 3 页 第四章改进的自适应c a n n y 算法研究 步骤5 ：对梯度图像进行双阈值处理，形成最后的边缘图像。 如果暂时忽视各个过程的具体实现，单从算法的过程上来看，与传统的 c a n n y 算法相比，新算法主要多了步骤4 ，即在阈值的自动选取上。 第3 4 页 第五章改进的自适应c an n y 算法实现及与传统算法的比较 第五章改进的自适应c a n n y 算法实现及与传统算法的比较 5 1 预备工作 对于传统的c a n n y 算法中，我们设定高斯滤波的标准方差为0 4 。对于高低 阈值的选择，由于对于各幅图像的梯度值范围都具体未知，因此我们采用一个高 低阈值比例以及高阈值占总像素比例的方式来确定两个阈值。但这两个比例值仍 需要事先人为指定好。在本试验中设定低阈值与