（信号与信息处理专业论文）基于遗传算法的图像边缘检测研究.pdf

西南交通大学硕士研究生学位论文 第1 页 摘要 边缘是图像最基本的特征之一，往往携带着一幅图像的大部分信息， 而这些信息对于人们对图像进行高层次的特征描述、识别和理解具有重要 的实用价值。 边缘检测是图像处理的重要内容，是图像分析的基础。对图像边缘检 测算法的研究已经有几十年的历史，这期间公开发表了大量的优秀论文， 边缘检测算法逐渐走向成熟，但仍不能满足图像分析的需要，依旧被列为 图像处理的经典技术难题之一。这是因为传统的边缘检测算法基本上是基 于梯度微分的，这些算法存在着不同程度的局限性。另外，在不同的应用 中，人们要实现的目标不同，因此对边缘的定义也不同，目标边缘、图像 纹理甚至噪声都可能成为有意义的边缘，因此很难找到一种普适性的边缘 检测算法。科技发展日新月异，促使人们尝试利用新技术去解决边缘检测 过程中出现的各种问题，新的算法不断涌现，如应用神经网络、遗传算法、 小波信号处理、数学形态学等技术进行边缘提取等，这些算法大都取得了 不错的应用效果。 本论文主要围绕遗传算法在边缘检测过程中的具体应用进行探讨，主 要研究内容包括： 1 ，首先对基于模板卷积的传统边缘检测算法进行了总结，分析了它们 在具体应用中的局限性。讨论了最佳边缘检测模板优化设计问题。进而研 究了一种以遗传算法为优化工具对模板系数进行寻优的方法并作了系列 仿真试验，结果表明该方法可以准确的在具有相同特征的图像上提取边 缘。 2 对遗传算法的基本策略及其收敛性进行了分析，重点研究了遗传算 法的收敛性评价准则，探讨了一种能够有效克服早熟收敛的遗传算法- 混 沌遗传算法。 3 基元提取问题是边缘检测的一个传统难题，现有的基元提取方法主 要采用著名的哈夫变换方法，但该方法个严重的缺陷是时间和空间丌销 极大，并且在基元提取前要对图像进行二值化预处理。针对此不足，本论 文研究了一种利用遗传算法直接在灰度图像上提取基元的方法，该方法采 用样本基元的缩放和旋转模扳在图像中进行匹配搜索，对虹膜的定位实验 表明该方法是一种有效的基元提取方法。 关键词：图像分割；边缘检测；遗传算法；基元提取； 西南交通大学硕士研究生学位论文第| | 页 a b s t r a c t b o u n d a r yi s o n eo ft h em o s tb a s i ci m a g ef e a t u r e sa n do f t e nc a r r i e sai o t o fi m a g ei n f o r m a t i o nt h a ti so fg r e a ti m p o r t a n c ei na n a l y z i n g ，d e s c r i b i n ga n d ， u n d e r s t a n d i n ga ni m a g ei nah i g hl e v e l b o u n d a r yd e t e c t i o np l a y s a n i m p o r t a n tr o l e i n i m a g ep r o c e s s i n g a n d a n a l y z i n g r e s e a r c ho nb o u n d a r yd e t e c t i o n h a sl a s tf o rt h e p a s t d e c a d e s d u r i n g t h i s p e r i o d ，al o t o fe x c e l l e n t p a p e r s h a v eb e e n p u b l i s h e da n dt h e b o u n d a r y d e t e c t i o n a l g o r i t h m s h a v e p r o g r e s s i v e l yd e v e l o p e d h o w e v e r ， b o u n d a r yd e t e c t i o na l g o r i t h ms t i l lr a n k sa sad i f f i c u l tp r o b l e mi nt h ei m a g e p r o c e s s i n g t h et r a d i t i o n a lb o u n d a r yd e t e c t i o na l g o r i t h m sa r eo nt h eb a s i so f g r a d i e n ta n dh a v em o r eo rl e s sl i m i t a t i o n s o nt h eo t h e rh a n d ，b o u n d a r yh a s d i f f e r e n td e f i n i t i o n sa c c o r d i n gt od i f f e r e n t a p p l i c a t i o n s s oi t i sn o te a s yt o f i n dau n i v e r s a lb o u n d a r yd e t e c t i o nm e t h o d w i t ht h ed e v e l o p m e n to f s c i e n c e a n dt e c h n o l o g y ，m a n yn e wb o u n d a r yd e t e c t i o n a l g o r i t h m sb a s e do nn e u r a l n e t w o r k ，g e n e t i ca l g o r i t h m ，w a v e l e t ，a n dm o r p h o l o g ya r ep r e s e n t e d 、 i nt h i st h e s i s ，r e s e a r c hw o r kf o c u s e so nh o w t ou s eg e n e t i ca l g o r i t h m st o s o l v eb o u n d a r yd e t e c t i o np r o b l e m s t h em a i nr e s e a r c h e sa r ea sf o l l o w s ： 1 t h et r a d i t i o n a l b o u n d a r yd e t e c t i o na l g o r i t h m s b a s e do nm a s k sa r e s u m m a r i z e da n di t sl i m i t a t i o n sa r ea l s oa n a l y z e d f u r t h e r m o r e t h ei s s u eo f h o wt o d e s i g nt h eb e s te d g ed e t e c t i o nm a s ki s d i s c u s s e da n dan o v e lm a s k d e s i g nm e t h o d b a s e do ng e n e t i ca l g o r i t h m si sr e s e a r c h e d t h es i m u l a t i o na n d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h eg i v e nm e t h o dc a ne f f e c t i v e l ye x t r a c tt h e b o u n d a r i e sf r o mt h eh o m o l o g o u si m a g e s 2 t h eb a s i cs t r a t e g ya n dc o n v e r g e n c eo fg e n e t i ca l g o r i t h m sa r ea n a l y z e d a n di t se v a l u a t i o nf u n c t i o n sa r er e s e a r c h e d t h ec h a o s g e n e t i ca l g o r i t h m ( c g a ) w h i c hc a ne f f e c t i v e l yo v e r c o m et h ep r e m a t u r ec o n v e r g e n c e i sa l s o d i s c u s s e d 3g e o m e t r i cp r i m i t i v ee x t r a c t i o ni sac l a s s i c a l p r o b l e m i nt h e i m a g e p r o c e s s i n ga r e n a 。h o u g ht r a n s f o r m ，w h i c hi so f t e nu s e di nb o u n d a r yd e t e c t i o n ， h a sas e r i o u sl i m i t a t i o nf o ri t sc o n s u m p t i o no ft i m ea n ds p a c e w h a tj sm o r e h o u g h t r a n s f o r mc a no n l ya p p l yo nb i n a r yi m a g e s t os o l v et h i sp r o b l e m ，o n e m e t h o db a s e do n g e n e t i c a l g o r i t h m s i s p r e s e n t e d t oe x t r a c t g e o m e t r i c p r i m i t i v e sd i r e c t l y f r o mt h e g r a yi m a g e s a n da l s o t e s t e d o nt h ei r i s l o c a l i z a t i o n s i m u l a t i o nr e s u l t ss h o wt h a tt h i sm e t h o di s e n c o u r a g i n ga n d 西南交通大学硕士研究生学位论文第| il 页 p r o m i s i n ga n d c a nb ee f f e c t i v e l yu s e do ng e o m e t r i cp r i m i t i v ee x t r a c t i o n k e yw o r d s ：i m a g es e g m e n t a t i o n ；b o u n d a r yd e t e c t i o n ；g e n e t i ca l g o r i t h m s g e o m e t r i cp r i m i t i v ee x t r a c t i o n 西南交通大学硕士研究生学位论文第1 页 1 1 选题背景及意义 第一章绪论 所谓边缘，是指周围像素灰度有阶跃变化或屋顶变化的那些像素的集 合，边缘与图像中物体的边界有关但又是不同的，边缘反映的是图像扶度 的不连续性，是图像最基本的特征之- - 1 ，2 1 ，往往携带着一幅图像的大部 分信息，而这些信息对于人们对图像进行高层次的特征描述、识别和理解 具有重要的实用价值。 定义边缘检测为：主要是图像的灰度变化的度量、检测和定位f 4 1 。边 缘检测是图像处理的重要内容，是图像分析的基础。边缘检测在图像分割、 模式识别、图像测量和机器视觉等应用中都有很重要的作用1 5 培j 。边缘广 泛存在于物体与背景之间、物体与物体之间，基元与基元之i | j 【j 】，因此它是 图像分割所依赖的重要特征。同时它也是纹理特征的重要信息源。图像匹 配也依赖于边缘信息【9 】，因为它是位鼋的标志，对灰度的变化很敏感，可 以作为匹配的起点。 模式识别的主要依据是图像的显著特征，而边缘携带了图像的大部分 信息，是图像最基本的特征，因此边缘对于模式识别具有特别重要的意义。 经验告诉我们，如果能得到图像的边缘，那么图像分析就会大大简化，图 像识别就会容易得多。 计算机视觉处理可以看作是为了实现某一任务从包含有大量的不相关 的变量中抽取不变量，总之就是简化信息。这就意味着要扔掉一些不必要 的信息而尽可能利用物体的不变性质。而边缘就是最童要的不交性质：光 线的变化显著地影响了一个区域的外观，但是不会改变它的边缘。更重要的 是人的视觉系统也是对边缘很敏感的。 边缘检测还是图像测最的重要基础，边缘检测的精度和准确度是图像 测量的关键指标。 对边缘检测算法的研究已经有几十年的历史，这期阳j 公丌发表了大量 的优秀论文，边缘检测算法逐渐走向成熟，但仍不能满足人们对图像分析 的需要，依旧被列为图像处理中的经典技术难题之- - i 3 , 1o 。这是因为传统 的研究方法基本上都是基于梯度微分算子的，导致这些算法存在很大的缺 西南交通大学硕士研究生学位论文第2 页 陷，即边缘定位精度和边缘检测尺度是一对矛盾问题；另外传统的边缘 检测算法还需要设定一个阈值，以区别哪些是边缘点哪些是噪声点，但如 何自适应的设定最佳阈值是人们研究的一个热点；再者，在不同的应用中， 人们要实现的目标不同，因此对边缘的定义也不同，目标边缘、图像纹理 甚至噪声都可能成为有意义的边缘，因此很难找到种普适性的边缘检测 算法【3j 。因此，根据具体应用要求，设计新的边缘检测方法或对现有的算 法进行改进，以得到满意的边缘检测结果依然是研究的主要方向。针对以 上问题和新兴技术的发展，近年来人们开始重新对边缘检测技术进行评 价，提出了许多新的边缘检测算法如应用神经网络、遗传算法、小波信 号处理、数学形态学等技术进行边缘提取，取得了不错的应用效果本文 主要集中于探讨如何利用遗传算法进行图像边缘检测及图像轮廓定位问 题。 遗传算法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计 算模型，最早由美国m i c h i g a n 大学的j h o l l a n d 教授于1 9 7 5 年提出 1 2 1 ， 它的主要特点是简单、通用、鲁棒性强，适用于并行分布处理，因此得到 了广泛的应用。从1 9 8 5 年在美国卡耐基梅隆大学召开的第一届国际遗传 算法会议( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m s ：i c g a 8 5 ) ，到 19 9 7 年5 月的i e e e 的t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) 9 刊，遗 传算法作为具有系统优化、自适应和学习的高性能计算和建模方法的研究 f i 趋成熟。 图像的边缘检测问题，其实可以转化为函数寻优问题，因此可以利用 遗传算法来进行优化【n 。6 1 。首先，可以利用遗传算法来优化现有的边缘检 测模板，根据具体问题设计优化参数，最后达到最佳的边缘检测效果：其 次，可以通过设定合适的适应度函数，利用遗传算法直接在图像上搜索边 缘，这样避免了传统算法中的模板尺度与定位精度的选择难题：再者，可 以利用遗传算法搜索最佳的边缘检测阈值，为边缘检测算法的自适应闽值 设置打下基础。另外，图像基元提取问题也是一爪 数优化问题【1 7 旧j ，同 样可以利用遗传算法得到很好的解决。 因此，选择基于遗传算法的图像边缘检测作为研究课题有其现实意义 及理论意义，本文的研究目的不仅在于利用遗传算法，解决传统边缘检测 算法中存在的缺陷，而且从寻优的角度对图像边缘提取进行了分析，为以 后的实际应用打下了基础。 西南交通大学硕士研究生学位论文第3 页 1 2 边缘检测算法研究概况 研究边缘检测的文章十分多。1 9 5 9 年，文献上最早提到边缘检测”。 1 9 6 5 年l gr o b e r t s 最早丌始系统研究边缘检测【2 0 。从那以后每年都会出 现很多关于边缘检测的文章。边缘检测的重要的文章大都发表在i e e e t r a n s o np a t t e r n a n a l y s i s a n dm a c h i n e i n t e l l i g e n c e ，c v g i p ：i m a g e p r o c e s s i n g ，i e e et r a n s o ni m a g ep r o c e s s i n g ， j o u r n a lo fl h ea c m 等上。 经典的边缘检测算法是基于图像梯度的微分算子方法，出于边缘发生 在图像灰度值变化比较大的地方，对应连续情形就是晓是函数梯度较大的 地方，所以研究比较好的求导算子就成为种思路。这种算子需要对每 个像素进行计算，实际应用中常用小区域模板卷积来进行近似计算。经典 的算子包括：r o b e r t s 模板 2 、s o b e l 模板f 2 孙、p r e w i t t 模板2 孙、k i r s c h 模 板1 2 、l a p l a c i a n 模板等。此类模板的典型特点是简单，方便，但抑制噪 声的能力较弱。 在梯度微分模板基础上发展起来的又考虑了对噪声点进行平滑的最优 滤波器设计有：l o g 算子【24 1 、c a n n y 算予【2 5 】。l o g 算子是按零交叉点检测 阶跃边缘的最佳算子。在实际图像中，高斯滤波的零交叉点不一定全部是 边缘点，还需要进一步确定真伪【2 6 】。另外，小面模型( f a c e tm o d e l ) e 2 7 1 本质 上也是利用二阶微分过零点来检测阶跃边缘的。19 8 6 年c a n n y ”】总结了以 往理论和实践的成果，提出边缘检测c a n n y 三准则：信噪比高、定位准确、 低边缘厚度，并给出了他们的数学表达式。在二维情况下，c a n n y 算子的 方向性质使边缘检测和定位性能比l o g 算予要好，具有更好的抗噪性能， 而且能产生边缘梯度方向和强度两个信息，为后续处理提供了方便。但也 存在不足之处：为了得到较好的结果通常需要使用较大的滤波尺度，容易丢 失一些细节。与c a n n y 算子密切相关的还有d e r i e h e 算子【2 8 1 和沈俊算子f 2 9 1 ， 它们在高层意义上是统一的。 近些年，随着新兴技术的兴起，利用新兴技术对图像进行边缘检测研 究引起了人们很大的兴趣，出现了基于模糊数学、神经网络、统计分析、 小波信号处理、遗传算法、数学形态学等等许多新的边缘检测方法，基于 新兴技术的边缘检测研究是现在边缘检测算法的主要研究方向。 统计方法检测边缘的原理主要是利用假设检验来检测边缘i3 0 】，r i s h ir ， r a k e s h 等在 3 i 】中利用对局部像素梯度的统计分析得到了图像中各个像素 西南交通大学硕士研究生学位论文 第4 页 是边缘的概率，并进而得到边缘检测的方案。 小波变换是近年来得到广泛应用的数学工具。作为多尺度分析工具， 小波变换为信号在不同尺度上的分析和表征提供了一个精确和统一的框 架 3 2 1 。信号突变点的检测及由边缘点重建原始信号是小波变换应用的一个 很重要的方面，许多学者开发了基于小波变换的各种边缘检测方法：文献 3 3 采用以零点为对称点的对称二进小波来检测屋顶边缘，用以零点为反 对称点的二进小波来检测阶跃边缘；正交小波【3 4j 也被用来提取多尺度边 缘；另外，b 样条小波 3 5 1 等也常被用于边缘检测。 模糊集合理论能较好的描述人类视觉中的模糊性和随机性，在模式识 别的各个层次都可以得到很好的应用。文献【3 6 】采用根据图像像素在各个 方向的灰度变化量进行模糊分类的方法，借鉴c a n n y 算子的理论，提出了 一种基于模糊竞争的边缘检测方法，取得了类似于c a n n y 算子的效果。文 献 3 7 】提出基于多特征和模糊推理的边缘检测算法。根据不同类别的边缘 点附近灰度分布的特点定义多种边缘特征；利用不同的边缘特征确定模糊 规则实现边缘检测，有效的抑制了噪声对检测效果的影响。文献 3 8 则提 出了一种快速模糊边缘检测算法。 近年来，用人工神经网络提取图像边缘成为图像检测领域的一个新的 热点。文献f 3 9 】提出了一种利用边缘的信息特征和人工样本作为优化训练 对象，采用b p 算法对前馈神经网络进行训练，得到了一种新的边缘检测 算法，该方法避免了传统算法中阙值设定的难题并具有很好的抑噪效果。 在各种神经网络模型中应用最广泛的一类是前馈神经网络，用于训练前馈 网络的最常用的方法是b p 算法。但是b p 网络收敛速度很慢，容易收敛 于局部极小点，且数值稳定性差，参数难以调整，很难满足实际应用的要 求【3 4 l 。对此情况，文献【4 0 】提出了利用k a l m a n 滤波算法的神经网络快速 学习算法，在边缘检测算法上的实验证明该算法成功地加快了神经网络的 收敛速度。另外，h o p f i e l d 神经网络 4 1 】在边缘检测算法中也得到了广泛 应用。 数学形态学是种应用于图像处理和模式识别领域的新方法，基本思 想是用具有一定形态的结构元素去度量和提取图像中的对应形状以达到 对图像分析和识别的目的【4 引。数学形态学的基本运算是腐蚀和膨胀，先腐 蚀后膨胀称为开运算，先膨胀后腐蚀成为闭运算。该算法简单，适于并行 处理，且易于硬件实现【4 ”。近年来，数学形态学与多尺度分析相结合的图 西南交通大学硕士研究生学位论文第5 页 像边缘检测算法也开始见渚于文献【“1 ，该算法具有更进一步的适辟j 性。 遗传算法，作为一种新发展起来的优化方法，是基于达尔文的适者， - 存理论和基因遗传学原理的搜索算法，特点以简单、鲁棒性和并行运算著 称，近年来在边缘检测中得到了广泛应用1 1 3 , - ”i 。这些方法基于不同的优化 模式，可以满足不同的检测目的。其中，文献 4 5 】方法以整幅图像为优化 目标，可以取得理想的边缘定位效果，但耗时过长；文献【15 则利用样本 图像和遗传算法优化边缘检测函数模扳，该算法类似于神经网络的训练方 法。基于遗传算法的边缘检测研究是本论文的重点，在后面章节还将予以 详述。 1 3 遗传算法研究概况 遗传算法的思想由来已久，早在2 0 世纪5 0 年代，一些生物学家就着 手于计算机模拟生物的遗传系统i t i j 2 l 。1 9 6 7 年，美国芝加哥大学的 h o l l a n d ，j h 教授在研究适应系统时。进一步设计进化演算的思考，并于 1 9 6 8 年提出模式理论。1 9 7 5 年，h o l l a n d 教授的专著自然界和人工系统 的适应性( a d a p t a t i o n i n n a t u r ea n d a r t i f i c a ls y s t e m s ) 问世，全面地介绍 了遗传算法，为遗传算法奠定了基础。同年d ej o n g 的博士论文“a n a n a l y s i so f t h eb e h a v i o ro fac l a s so fg e n e t i ca d a p t i v es y s t e m s ”完成。d e j o n g 博士对模式定理进行了深入地研究并作了大量严格的计算实验，给出 了明确的结论。他还建立了后来被广泛应用的五函数测试平台，定义了算 法的性能评价标准，并以函数优化为例，对遗传算法的六种方案的性能及 机理进行了详细的实验和分析，他的工作为遗传算法的进一步研究奠定了 坚实的基础。随后经过2 0 余年的发展，遗传算法无论在理论研究芨面， 还是在实际应用方面都有了长足的进展。特别是近年来世界范围内形成的 进化计算热潮，计算智能作为人工智能的重要研究方向，以及后来的人工 生命研究的兴起，使遗传算法得到了更为广泛的关注。从1 9 8 5 年在美国 卡耐基梅隆大学召开的第一届国际遗传算法会议( i n t e r n a t i o n a l c o n f e r e n c eo ng e n e t i ca l g o r i t h m s ：i c g a 8 5 ) 到19 9 7 年5 月的i e e e 的 t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) 仓刊，遗传算法作为具有系统优 化、自适应和学习的高性能计算和建模方法的研究日趋成熟。国内1 9 9 6 年也出版了第一本遗传算法专著遗传算法及其应用”，至此，遗传算 西南交通大学硕士研究生学位论文 第6 页 法的理论及应用在国内也全面展丌。 遗传算法的研究可分为理论研究和应用研究。理论研究主要包括算法 的编码策略研究、全局收敛性以及搜索效率的分析、算法的新结构研究、 基因操作策略及其性能研究、遗传算法参数的选择及与其它优化算法的综 合的比较研究等，而应用研究包括的内容非常广泛，典型的如函数优化， 最优控制等。 理论研究中，h o l l a n d 的模式理论1 4 6 1 奠定了遗传算法的数学基础，每一 代遗传有多少新模式产生是遗传算法效率的重要特性。 近几年，基于马尔科夫链的全局性收敛性分析是遗传算法的研究热点 之。现已证明，具有复制、交叉、变异操作的标准遗传算法不能收敛到 全局最优解，而采用了最优个体保留策略的遗传算法以概率全局收敛 1 4 7 , 4 8 , 4 9 。目前收敛性分析基于简单遗传算法模型，结合其它优化算法的遗 传算法的收敛性分析仍是目前及今后的研究难点。 模式定理是建立在二进制编码基础上的，这使得二进制编码得到了广 泛的研究，但是实数编码由于具有精度高，便于大空间搜索的优点，而得 到越来越多的重视1 5 0 , 5 1j 。目前实数编码遗传算法的研究已成为主流，并已 有马尔科夫链作为理论支撑。 遗传算法操作方式的研究也是一个主要的研究方面，占有相当大的比 重。文献1 5 2 提出用种群方差和熵来衡量遗传算法的种群多样性，并分析 了复制、交叉及变异操作对种群方差和熵的影响。复制操作的目的是为了 避免基因缺失，提高全局收敛性和效率，目前复制操作的主要算法有：轮 盘赌方式、排序方法、最佳个体保留、锦标褰方法等, 1 2 1 。交叉操作的作 用是组合出新的个休，在串空间进行有效搜索，同时降低对有效模式的破 坏概率。目前交叉策略有单点咬叉、双点交叉、多点交叉、算术交叉等。 变异的作用是产生没被发现的、或是丢失掉的个体，以避免遗传算法收敛 到局部最优解。目前的主要变异操作有：常规位变异、均匀变异、非均匀 变异、高斯变异、混沌变异垆列等。 另外，将遗传算法与其它优化算法结合起来，可以取长补短，构成性 能更好的综合算法。现有的综合性遗传算法有免疫遗传算法f 5 4 5 “、混沌遗 传算法 5 6 , 5 7 , 5 8 , 5 9 、量子进化算法 6 0 , 6 1 1 等。 由于遗传算法的鲁棒性和内在并行性，遗传算法得到了广泛的应用。 在许多情况下，遗传算法明显优于传统的优化方法。但是，对遗传算法应 西南交通大学硕士研究生学位论文第7 页 用的成败依赖于对遗传算法和所解决问题的深刻理解，因而其应用研究的 内容比理论研究更丰富。 函数优化是遗传算法应用的典型例子【6 ，文献 6 3 采用遗传算法训练 神经网络，文献f 6 4 把遗传算法用于纹理基元的分割。边缘检测也是遗传 算法的一个新的应用领域。 另外，遗传算法在自动控制、工程结构优化、计算数学、航空航天、 交通、计算机科学、通信、电子学、电力、材料科学等许多领域都得到了 应用。在这些应用中，许多研究者根据具体问题对遗传算法进行了改进。 1 4 论文主要工作 本文主要围绕遗传算法及其在图像边缘检测中的应用展开研究，主要 内容包括：( 1 ) 经典的边缘检测算法介绍及其缺陷分析；( 2 ) 遗传算法及 其收敛性分析、混沌遗传算法性能分析：( 3 ) 遗传算法在图像边缘检测及 基元提取中的应用。主要工作包括： ( 1 ) 给出了经典边缘检测算法中常用的几个边缘检测算子，并对他们 的性能及应用进行了分析，进一步指出了这些常用算子的局限性并指出了 可能的解决方案。 ( 2 ) 详细给出了遗传算法的原理、特点及其基本策略，分析了遗传算 法收敛性判断依据，并应用马尔科夫链理论分析了标准遗传算法和最佳保 留策略遗传算法的收敛性。研究了一种能有效克服早熟的算法：混沌遗传 算法。 ( 3 ) 分析了把图像边缘检测转化为函数寻优的方法，并利用遗传算法 进行了实现，另外根据传统边缘检测大都基于模板卷积的方法，考虑利用 遗传算法进行模板优化并作了实验仿真，给出了一些实验结果及分析，为 该算法进一步应用打下了基础。 ( 4 ) 基元提取问题是边缘检测中的一个传统难题，现有的基元提取 方法主要采用著名的哈夫变换方法，但该方法一个严重的缺陷就是时间和 空间开销极大，并且在基元提取前要对图像进行二值化处理。基于这一问 题，在前人利用遗传算法对二值图像基元提取的基础上，给出了利用遗传 算法直接在灰度图像上进行基元提取的方法，并成功的把该方法应用于虹 膜的定位研究。 西南交通大学硕士研究生学位论文 第8 页 第二章经典边缘检测算法及其性能分析 2 1 引言 在不同的应用中，人们要实现的目标不同，因此对边缘的定义也不同， 目标边缘、图像纹理甚至噪声都可能成为有意义的边缘，因此很难找到一 种普适性的边缘定义方法。一般来讲，边缘定义为：是指周围像素狄度有 阶跃变化或屋顶变化的那些像素的集合。边缘与图像中物体的边界有关但 又是不同的。边缘反映的是图像灰度的不连续性，是图像最基本的特征之 一，往往携带着幅图像的大部分信息，而这些信息对于我们对图像进行 高层次的特征描述、识别和理解具有重要的实用价值。 边缘一般包括：边沿( e d g e ) 、边界( b o u n d a r y ) 、轮廓( c o n t o u r ) 。三者之 间既有区别又有联系，在英文文献分的较清，在中文文献中有时边缘代表 了边沿，有时又代表了边界，这是阅读中英文文献需要注意的地方。 定义边缘检测为：主要是图像的灰度变化的度量、检测和定位。边缘 检测的研究内容主要包括：边沿检测、边缘定位、边缘细化、边缘链接、 轮廓提取等。 传统边缘检测一般包括的步骤为： r 鬲蕊虿小甭面百。谪矗磊哥丽丽；“五赢i 二五赢五 图2 - 1 边缘检测一般步骤 由于噪声的存在，可能产生虚假的边缘，平滑处理的目的是去除图像 中的噪声点的影响。通过计算梯度，得到图像中每一像素点的梯度值，一 般，边缘点的梯度较大，通过合理的设定阈值，就可以把边缘点过滤出来。 阈值的设定一般采用单一阈值方法，也可以采用双闽值法甚至局部自适应 多阈值法。通过以上程序检测到的边缘一般并不是单一像素宽度的，这时 还要进行细化，一般算子中采用非最大值抑制的方法实现。有些边缘算子 产生的往往是边缘片断，而不是完整的边缘，这时还要进行边缘链接，常 用的链接方法有h o u g h 变换等。 常见的边缘点有三种形式。第一种是阶梯形边缘( s t e p e d g e ) ，即从一个 灰度到比它高好多等级的另一个灰度。第二种是屋项型边缘( r o o f - e d g e ) ， 西南交通大学硕士研究生学位论文 第9 页 它的灰度是慢熳增加到一定程度然后慢慢减小。还有一种是线性边缘 ( f i n e e d g e ) ，它的灰度在某一线性区域独立存在。还有另外一种常见的边 缘为斜坡边缘( r a m p e d g e ) ，它其实是阶梯边缘在实际图像中的存在形式。 经典的边缘检测算法基本上都是基于图像梯度的，如图2 2 所示，从 图中可以看出，边缘位置的一阶和二阶导数具有明显的跳跃特征，利用图 像灰度拟合曲线的一阶和二阶导数就可以很容易的检测出边缘。 厂 丘矿 十+ 骱趺型边缘 i 跃型 苎锋 露像 蓄蔷 莓羹 l 弋一毒錾 鏖脊型边缘 如果用f ( x ，y ) 代表图像在坐标( 工，y ) 处的灰度值， 义为： v f ：晦，g 。 - 芭羁 。 斑却 这个向量的模值由下式给出： 梯度方向为 则图像的一阶微分定 ( 2 1 ) m a g ( v f ) ：g ( x , y ) = 厨丽 ：， 船= 藩房 ( 2 3 ) 同理，图像的二阶微分t 又称为图像的l a p l a c e 变换近似) 定义为 上十十一 西南交通大学硕士研究生学位论文 第1 0 页 v z ，：堕+ 型 。 缸2 钞2 ( 2 - 4 ) 上述定义方法是在假定图像灰度连续的情况下对图像灰度进行曲线拟 合的方法，但现实图像是由像素点组成的，所以图像灰度是离散的，这就 需要采用数字近似方法对连续梯度函数进行近似。而对于模拟函数的微 分，数字近似则采用图像离散点的差分计算。而正是因为近似方法的不同， 才产生了不同的经典边缘检测算子。 2 2 经典边缘检测算法 2 2 1r o b e , s 交叉算子 1 9 6 3 年r o b e r t s l 2 0 1 提出了边缘检测的这个简单算子。 r o b e r t s 算子是利用局部差分寻找边缘的箅子，它在2 x 2 邻域上计算对 角导数，定义梯度为： r ( x ，y ) = x ( f ( x ，y ) 一f ( x + l ，y + 1 ) ) 2 + ( 厂( x ，y + 1 ) 一，( x + l ，y ) ) 2 ( 2 - 5 ) 在实际应用中，为了简化计算，用梯度函数的绝对值近似： r ( x ，力= l ，( x ，力一f ( x + l ，y + 1 ) i + 1 ，( 五y 十1 ) 一f ( x + l ，y ) j ( 2 - 6 ) r o b e r t s 交叉算予的卷积模袄实现为： l 1o ll 01f ( 2 - 7 ) l ol jl 一1o j 由上面两个卷积算子对图像进行卷积运算后，带入( 2 - 6 ) 式，即可求 得图像梯度值，然后适当选择闽值t ，使得梯度值r ( x ，y ) t 的像素点置1 ， 否则置0 ，即为边缘图像，r o b e r t s 算子对h o u s e 图像的检测结果如图2 4 所示。r o b e r t s 算子是直观的和简单的，但效果不好，其主要问题是计算 邻域2 x 2 太小。以致对噪声过于敏感且检测韵边缘不具有连续性。 西南交通大学硕士研究生学位论文 第11 页 图2 - 3h o u s e 图像 图2 4r o b e r t s 算子检测结果 2 2 2s o b e l 算子 1 9 7 0 年左右s o b e l e 2 1 1 和p r e w i t t l 2 2 1 分别提出了一个算子，这就是p r e w i t t 算子和s o b e l 算子。 s o b e l 算子是以f ( x ，y ) 为中心计算3 x 3 邻域的x ，y 方向的偏导数，并为 了抑制噪声对中心点相应加了一定的权值，它的数字梯度近似方程为： g x = ，( x + 1 ，y 一1 ) + 2 f ( x + 1 ，y ) + ，( x + 1 ，y + 1 ) r ，殳、 - f ( x 一1 ，y 一1 ) + 2 f ( x 一1 ，y ) + 厂( x 一1 ，一1 ) 。2 。6 g 。 一f ；( ，x 。- x l 一, y ，+ 1 ) + 2 + f ( x , 1y - 1 ) 2 f ( x 耋十y ：! ：；二f 工( + x ： 1 + y ：! 毛， c z ， 一 ，( x 一， + ，一1 ) + ，一1 ) 其梯度大小一般为： 如y ) 2 + q 2 ( 2 1 0 ) 也可以取近似表示o g ( x ，y ) = i 瓯l + i q ( 2 1 1 ) ( 2 1 2 ) 如果我们用s o b e l 算子检测图像m 的边缘的话，我们可以用横向模板 和纵向模板分别与图像进行卷积，在不考虑边界的情况下，得到的是和原 0 o o o 2 j o ， n _ 一引u 0 0 o ：z l 舭卜卜h 子 算 板摸积卷的它 西南交通大学硕士研究生学位论文 第12 页 图像同样大小的两个有向梯度矩阵m 1 和m 2 ，然后把两个梯度相加得到总 的梯度值g ，然后就可以通过阂值处理得到图像边缘。其过程为： e d g e = ( ( m 。嚷) 2 + ( m 固g ，) 2 ) t h r p s h 2 ( 2 13 ) 图2 - 5 为采用s o b e l 算子对h o u s e 图像进行边缘检测的效果。其中，( a ) 图为未加噪声图像的边缘，( b ) 图为加有方差n 0 0 5 高斯噪声图像的边缘。 ( a ) ( b ) 图2 5s o b e l 算子的检测效果 s o b e l 算子利用像素点上下、左右相邻点的灰度加权算法，根据在边缘 点处达到极值这一现象进行边缘检测，由于s o b e l 算予的计算邻域相对 r o b e r t s 算子要大，因此s o b e l 算子有较好的抑制噪声效果，同时，s o b e l 算予的中心权值为2 ，加重了边缘点的重要性，有利于检测出较好的边缘。 但同时由于局部平均的影响，也可能检测出假的边缘。当对精度要求不高 时，s o b e l 算予是一种较常用的方法。 2 2 3p r e w i t t 算子 p r e w i t t 算子和s o b e l 算子的原理是一样的，都是基于3 3 邻域的有向差 分，但和s o b e l 算子不同的是，它在边缘像素方向设的权值为1 ，而s o b e l 算子的为2 ，这就使得p r e w i t t 算子更适合于具有随机噪声的边缘，而s o b e l 算子则对边缘方向外的噪声有更好的抑制作用。 p r e w i t t 算子的计算公式为： q = 厂 + l ，y 一1 ) + ，0 + l ，y ) + ，扛+ l ，y + 1 ) 、 一 f ( x - 1 ，y - i ) + f ( x - 1 ，y ) + f ( x 一1 ，y i ) ) 、“ q = f ( x l ，y + 1 ) + f ( x ，y + 1 ) + f ( x + l ，y + 1 ) )，、 - f ( x - l ，y 1 ) + 厂( x ，y 一1 ) + f ( x + 1 ，y 1 ) ) 、7 西南交通大学硕士研究生学位论文第13 页 其卷积模板为： 一1 0 1 i lol l 一1 o l j r 一1 1 1 1 fooo l1 ，j 。：啪， 纵向模板横向模板 p r e w i t t 算子的梯度计算公式与边缘检测过程和s o b e l 算子是一样的。 图2 - 6 是用p r e w i t t 算子对h o u s e 图像的检测效果。其中，图像( a ) 为没 有噪声图像的边缘，图像( b ) 为含有方差为o 0 0 5 的高斯噪声图像的边缘。 ( a )( b ) 图2 - 6p r e w i t t 算子的边缘检测效果 事实上，p r e w i t t 算子和s o b e l 算子有些共同的缺点，即： a 它们的结果对噪声很敏感： b ，可以通过先对图像做平滑以改善结果，但是又会产生一个问题：会把 一些靠在一起的边缘平滑掉，而且会影响对边缘的定位： c 用这些模板卷积后后得到的边缘厚度可能是跨跃好几个点而不是一 个点；为了改善这个问题，算法使用时还要做一些改进：边缘像素不仅要 大于闽值而且在梯度方向上要进行非极大值抑制，即在梯度方向上边缘 点梯度的大小要大于它的前者和它的后者； 2 2 4m a r r h i l d r e t h 零交叉点算子 1 9 8 0 年，m a r r 和h i l d r e t h l 2 4 1 提出了一种新的边缘检测理论和技术，称 为m a r r h i l d r e t h 算子，也称为l o g 算子。 一阶微分边缘检测算子虽然计算简单，但对于图像中的灰度渐变的区 西南交通大学硕士研究生学位论文第1 4 n 位边缘，我们可以用l a p l a c i a n 算子实现过零点检测。图像的l a p l a c i a n 微 妒厂= 警+ 孑 可o z f = 厂( x + l , y ) 一几，) ) _ m ，y ) 一( x - l , y ) 2 f ( x + l ，y ) + ，( x 一1 ，y ) 一2 f ( x ，y ) ( 2 - 18 ) 等= 叭w + 1 ) 一几，埘一 ，( w ) 一m 扩1 ) ) 2 厂 ，y + 1 ) + ，( z ，y 1 ) 一2 f ( x ，y ) ( 2 1 9 ) 墨习f 虽三- 1 亿：。， ( a )( b ) 上面两种模板都是以l a p l a c i a n 定义为基础的，只是符号不一样，但产 生同样的边缘检测效果。 对角线方向也可以加入到l a p l a c i a n 的定义中，即在两个对角线方向计 算二阶梯度差，同时在两个对角线方向还各包含一个2 f ( x ，y ) ，考虑了对 角线方向以后的边缘检测模板如下图所示： 西南交通大学硕士研究生学位论文 第1 5 页 | ；| 1 f - 1 1 1 1 i l8 一il l 一1 1 - 1 j ( 2 - 2 2 ) ( c )( d ) 从模板可以看出，不像一阶微分算子，l a p l a c i a n 算子是没有方向性的， 即是各向同性的。但l a p l a c i a n 算子也有缺点，正