（光学工程专业论文）数字图像中基本几何形状检测算法的研究与应用.pdf

摘要 图像理解( 图像分析) 中，物体的形状是比较高级的信息。直线、圆和椭圆作为自 然界和人造物体中常见的几何形状，在数字图像中对它们进行准确的检测有着重要的意 义。它们是其他更复杂的几何形状的有效组成部分，也是后续更高级的计算机视觉处理 的基础。在工程图纸矢量化，机器人视觉，图像分割，人脸检测，计算机辅助设计，物 体定位，非接触式检测等方面有着广泛地应用。 本文主要研究了数字图像中，直线、圆和椭圆这三类基本几何形状的检测算法，并 将研究成果运用于实际的显微图像自动绘图与辅助绘图系统。完成的研究和创新工作主 要包括以下内容： ( 1 ) 介绍了图像理解的基本策略，并综述了国内外检测算法的发展状况。较为详细 地介绍了h o u g h 变换的原理，分析和总结了一些数字图像中直线、圆和椭圆的检测方 法。 ( 2 ) 提出了数字图像中，直线、圆和椭圆等几何形状检测时边缘检测算子的要求。 通过实验，完成对a d m 、c a n n y 、s o b e l - z e m i k e 、s u s a n 这四种边缘检测算子的评 价，挑选出符合系统要求的检测算子a d m 。 ( 3 ) 提出一种改进的基于最小二乘法的随机椭圆检测算法，完成与原算法和常用的 几种检测算法的比较。与原算法的比较实验表明该改进是有效的，改进之后算法在检测 的速度、稳定性和准确率上都有很大的提高，同时保留了原算法抗噪声的能力，改善了 算法对参数的依赖性；与常用的一些算法比较实验表明，本改进算法准确性高，适用范 围广。 ( 4 ) 初步完成了一种使用图像数据控制策略( b o t t o mu p ) ，基于边界跟踪和曲线分割 的，数字图像中直线、圆和椭圆检测方法。通过实验对该算法进行了分析，指出还需要 改进的地方。 ( 5 ) 结合a d m 边缘检测箅子，概率h o u g h 变换直线检测和基于最小二乘法的随机 圆和椭圆检测，以及直线、圆和椭圆的拟合算法，完成一套显微图像的自动绘图与辅助 绘图系统。实验表明，系统检测的结果有较高的稳定性，实测误差在3 左右，整套系 统能满足测量的要求。 关键词：边缘检测、h o u g h 变换、随机h o u g h 变换、直线检测、直接椭圆拟合、 随机圆检测、随机椭圆检测、轮廓跟踪、链码和 a b s t r a c t i nt h ef i e l do fi m a g eu n d e r s t a n d i n g ( i m a g ea n a l y s 哟，s h a p e sa r ev e r yu s e f u l , s e l x i o ri n - f o r m a t i o n a st h el i n e s , c i r c l e sa n d e l l i p s e sa r e c o n q n l o n g e o m e t r i cs h a p e si nn a t u r ea n d m a r lm a d e o b j e c t s , e x t r a c t i n gt h e mf r o md i g i t a li m a g e sh a sav e r yi m p o r t a n t r o l ei ni m a g eu n d e r s t a n d i n g o t h e rm o r ec o m p l e xs h a p e sc a nb ed e r i v e df r o mt h o s es i m p l e s t s h a p e s t h ee x t r a c t i n gp r o c e s s i n gi se s s e n t i a ls t e pi nc o m p u t e rv i s i o n e f f i c i e n tr e c o g - n i t - i o no fl i n e s , c i r c l e sa n de l l i p s e sh a v eb e e nw i d e l yu s e di nm a n ya p p l i c a t i o n s f o r e x a m p l e , e n g i n e e r i n gd r a w i n gv e c t o r i z a t i o n , r o b o tv i s i o n ，i m a g es e g m e n t a t i o n , f a c e d e t e c t i o n , c o m p u t e ra i d e dd e s i g n , o b j e c tl o c a t i n g , i m a g i n gb a s e dm e a s u r i n gs y s t e m e t c i nt h i st h e s i s , w es t a r t e dar e s e a r c ho nl i n e s , c i r c l e sa n de l l i p s e sd e t e c t i o ni nd i 萨 t a li m a g e sa n dm a d ea na u t o m a t i cd e t e c t i n ga n da i d e dd r a w i n gs y s t e mf o rm i c r o s c o p e b a s e do nt h er e s e a r c hr e s u l t s d e t a i lr e s e a r c hw o r k sa n ds e v e r a ln e wi d e a sc a nb ed e - s c r i b e da sf o l l o w i n g ： ( 1 ) p r e s e n t ss o m eb a s i cs t r a t e g i e so fi m a g eu n d e r s t a n d i n g s u m m a r i z e sa c a d e m i c a n de x p e r i m e n t a lr e s e a r c ha c c o m p l i s h m e n t so nl i n e s ，c i r c l e sa n de l l i p s e sd e t e c t i o n i n - t r o d u c e sa n da n a l y z e ss o m ea l g o r i t h m sw h i c ha r ec o m m o n l yu s e di nb a s i cg e o m e t r i c s h a p e sd e t e c t i o n ( 2 ) p r e s e n t sa ne d g ed e t e c t i o ng u i d el i n ef o rl i n e s , c i r c l e sa n de l l i p s e sd e t e c t i o n c h o o s e sa d m o p e r a t o ra st h eb e s te d g ed e t e c t i o na l g o r i t h m f o rb a s i cg e o m e t r i cs h a p e s d e t e c t i o nb yc o m p a r i n gt h ep e r f o r m a n c ew i t ht h r e eo t h e ro p e r a t o r s ：c a n n y , s o b e l - z e r n i k ea n ds u s a n ( 3 ) p r o p o s e sa ni m p r o v e dr a n d o m i z e de l l i p s e sd e t e c t i o nb a s e do nl e a s ts q u a r e s a p p r o a c h e x p e r i m e n t sw i t ho r i g i n a la l g o r i t h ms h o wt h a tt h ei m p r o v e m e n t sr e d u c e s t h ed e p e n d e n c eo np a r a m e t e r so fd e t e c t i o na l g o r i t h m , e n h a n c e st h es p e e d ，s t a b i l i t y a n da c c u r a c yo fe l l i p s ed e t e c t i o n , w h i l ep r e s e r v i n gt h ea n t i - n o i s ea b i l i t yo fo r i g i n a la l - g o r i t h r a e x p e r i m e n t sw i t ho t h e rp o p u l a ra l g o r i t h m ss h o wt h a tt h en e wm e t h o dh a s m u c hh i g h e ra c c u r a c ya n dc a nb eu s e di nm u c hw i d e rf i e l d s ( 4 ) g i v e s a c o n t o u r t r a c i n g ( b o u n d a r y t r a c i n g ) a n d c u r v e s e g m e n t a t i o n b a s e d l i n e s , c i r c l e sa n de l l i p s e sd e t e c t i o n a n a l y z e st h ep e r f o r m a n c ea n dp o i n t so u ts o m ew e a k - i i 浙江大学硕士学位论文 m n e s s e so ft h ea l g o r i t h m ( 5 ) m a k e sa r ta u t o m a t i cl i n e s , c i r c l e s , e l h p s e sd e t e c t i n ga n da i d e dd r a w i n gs y s t e m f o rm i c r o s c o p eb yn s i n ga d m o p e r a t o r , p r o b a b i l i s t i ch o u g h t r a n s f o r ml i n e sd e t e c t i o n , i m p r o v e dr a n d o m i z e dc i r c l e s , e u i p s e sd e t e c t i o nb a s e do nl e a s ts q u a r e sa p p r o a c h a n dl i n e , c i r c l e ，e n i p s ef i t t i n ga l g o r i t h m s e x p e r i m e n t ss h o wt h a tt h ea u t o m a t i cd e t e c t - i n gr e s u l t so ft h es y s t e ma r ev e r ys t a b l e , e r r o ro ft h em e a s u r e m e n ti sa b o u t 3 t h e w h o l es y s t e mc a nm e e tt h em e a s u r e m e n tr e q u i r e m e n t s k e yw o r d s ：e d g ed e t e c t i o n , h o u g ht r a n s f o r m , r a n d o mh o u g ht r a n s f o r m , l i n e s d e t e c t i o n , d i r e c te l l i p s ef i t t i n g , r a n d o m i z e dc i r c l e sd e t e c t i o n , r a n d o m i z e de l l i p s e sd e t e c t i o n , c o n t o u rt r a c i n g , c h a i nc o d es u m 1 1 课题背景及意义 第一章绪论 1 1 1 课题背景 数字图像处理的诞生起源于两个主要的应用领域：其一是为了便于人们分析而对图 像信息进行改进；其二就是为使机器自动理解而对图像数据进行存储、传输及显示。尽 管其发展历史并不长，但却已经引起各方面人士的广泛重视。首先，视觉是人类最重要 的感知手段，图像又是视觉的基础。数字图像成为心理学、生理学、计算机科学等诸多 领域内的学者们研究视觉感知的有效工具。其次，在军事、遥感、气象等大型应用中有 不断增长的需求。此外，伴随数字成像、图像打印机和数字印刷技术的快速发展，使得 图像处理设备已不再昂贵，给图像处理的发展提供了很好的条件。 本论文主要涉及图像理解( 图像分析) ，处于图像处理和计算机视觉两个学科之间的 领域。而从图像处理到计算机视觉这一过程，通常被认为是个连续的统一体，内部并 没有明确的界限。一般按照三种典型( 低级、中级和高级) 的计算处理来区分内部的学 科。在本文的讨论中，这三类典型计算处理都会有所运用。 1 1 2 课题意义 直线、圆和椭圆作为自然界和人造物体中常见的基本几何形状，在数字图像中对它 们进行准确的检测有着重要的意义。它们是其他更复杂的几何形状的有效组成部分，也 是后续更高级的计算机视觉处理的基础。在工程图纸矢量化f l l ，机器人视觉 2 , 3 1 ，图像 分割【4 l ，人脸检测暇，计算机辅助设计【6 l ，物体定位研，非接触式检测 8 , 9 1 等方面有着广 泛地应用。 1 2 图像理解基本策略 在图像理解( 图像分析) 过程中，图像信息采用不同的表述方式存储，在处理的时 候，有个很重要的问题就是这些信息用何种方式去控制。是由图像数据本身呢，还是 更加高层的结构呢? 继而分出两类不同的策略：基于模型的控制( t o pd o w n ) ；由图像 数据控制( b o t t o mu p ) 。 1 2 1 基于模型的控制( t o pd o w n ) 基于模型的控制策略其主要思想在于，模型的建立和模型的验证，是一种面向目标 】 2 第1 章绪论 的处理过程。通过模型的建立，将高层次的目标被转化为较低层次的子目标，而子目标 继续被分为更细的目标，直到最后出现能直接判断接受或者拒绝的子目标。也可以表述 为，通过模型将图像换空间上的数据转化到特征空间中去，在特征空间中接受或拒绝。 该策略在整个过程中都由模型来控制，从全局上出发来使用图像数据，通常有较强地抗 噪声能力，但是弱点也比较明显，其运算量l t 较大。基本框架如图1 - 1 。 f 目标模型( 目标的知识) i _ _ 圈毛丢至圭至泣圈 lil 圆圆圈 图1 - 1 基于模型的控制f l o pd o w n ) 1 2 2由图像数据控制( b o t t o mu p ) 由图像数据控制策略通常又称为自底向上控制策略。一般分三个步骤： 1 ) 预处理：变换原图像数据，找出可能有用的信息。 2 ) 分割：检测和分割图像中真实物体或其某一部分相对应的区域。 3 ) 理解：对分割出来的区域进行描述，并由目标模型进行分类。 持不变的，一般还是原来图像空问的表示方法。通常该策略要求输入的图像数据的质量 要比较好，如果比较差的话，只有当每个步骤的处理中。数据的缺陷或者是不可靠性不 足以带来实质性的错误时，才有可能得到好的结果。基本框架如图1 - 2 i 目标模型( 目标的知识) i 一 圈芝寒莎团 i 要竺耋皇i 浙江大学硕士学位论文3 1 3 国内外发展现状 国外这方面的理论研究主要集中在8 0 年代以前，国内在理论研究上相对较少，较 为薄弱。在9 0 年代之后，随着计算机的普及和处理能力的日渐增强，各类方法的应用 得到了有效的拓展，也有越来越多的改进加入到原有的算法之中。总的来说检测算法朝 着多元化方向发展，引入了很多数字图像处理中其他领域的方法。 1 3 1 直线检测 当前直线检测的常用方法集中在h o u g h 变换和r a d o n 变换，研究的重点在于检测 的精度和计算量的改进。 s o n g 1 0 1 提出的新方法同时利用了h o u g h 变换的参数空问和原始图像空间。在预 测图像梯度的基础上来加速累加过程，通过引入边界记录器在直线验证过程中减少多余 的处理，同时开发了基于图像的直线粗细检测算法。s h a p i r o 在文章【1 1 】中说明了标准 h o u g h 变换的投票过程对其检测精度的影响，并给出了个新的h o u g h - g r e e n 变换算 法，精度超越了标准h o u g h 变换，达到了连续h o u g h 变换的水平。 赵 1 2 1 利用r a d o n 变换能够检测直线和反映目标直线结构的能力，根据目标特征、 先验知识生成的规则，对图像r a d o n 变换结果进行有效分析，快速检测机场、港口等 直线性目标。然后采用基于假设检验策略的方法，经直线拟合得到直线段的精确位置。 解决了r a d o n 变换不能精确定位的问题。l o 和t s a i 1 3 1 综合了h o u g h 变换和r a d o n 变换给出了新的直线检测方法。 t s i t s i p i s 1 4 等人提出利用二维傅立叶变换，通过计算图像在各个方向上的能量。建 立关于斜率的能量谱来寻找图像中线性的部分。另外还有一些使用细化算法的直线检测 手段，多用于简单几何物体与工程图纸的矢量化。 1 3 2 圆检测 圆的检测主要为h o u g h 变换。多数方法都是采用分步的h o u g h 变换，先找出圆 心，然后再对半径进行投票。 d u q u e n o y 1 5 通过加快对图像的分析速度和对图像空间的降采样来提高基于 h o u g h 变换这类方法的收敛速度。此方法不仅适用于圆的检测，还可以扩展到任何 其他曲线的变换检测。c h i u 1 6 在文章中为标准h o u g h 变换给出了一个新的投票方 法，让每一个像素只对应一个候选圆参数，大大改善了计算复杂度，有效地减少了存 储空间。黎【6 】则使用受限随机h o u g h 变换的方法，在选取用来计算参数的点对上进 行合理的配对和筛选，解决了随机变换中无效采样的问题，提出了高效的多圆检测算 4 第1 章绪论 法。r a m i r e z 1 7 等人使用遗传算法( g e n e t i ca l g o r i t h m s ) 来检测圆。能够在图形中检测 出残缺的圆，检测结果的精确度能达到亚像素级别。 1 3 3 椭圆检测 常用的椭圆检测可分为类聚( 投票) 和最优化两大类方法。投票类的代表就是 h o u g h 变换 1 8 1 和r a n s a c 1 9 。最小二乘法与遗传算法都属于最优化方法。 椭圆由于参数众多，投票类研究的重点一般都在于数据点的筛选和椭圆几何性质 的利用。z h a n g 2 0 在论文中提出了“4 个点、2 个方向、1 交点( 4 - 2 - 1 ) ”的数据点筛选 ( 组合) 方法，完成了一个鲁棒、实时的椭圆检测算法，并成功地应用在实时人脸检测 上 5 1 。c h e n g 2 1 】提出的受限随机h o u g h 变换方法( r r h v ) ，限制了点选取的范围， 有效地减少了无效采样，提高了算法的效率。s e w i s y 2 2 提出利用椭圆对称性，通过直 线的h o u g h 变换来获得椭圆中心，然后利用椭圆上点关于椭圆中心的对称性，收集 数据点求出剩余的三个参数。屈 2 3 1 完成了弦中点h o u g h 变换椭圆检测方法。c h e n g 和l e e 2 4 根据二次曲线簇的几何特性开发出一种强有力的二次曲线簇的表示方法： 单参数组，解决了随机h o u g h 变换中多维参数空间分辨率选取和庞大的运算量的问 题。庞【3 】利用改进的二次曲线簇参数方程，并基于k - r a n s a c 的算法思想，对广义的 k r a n s a c 算法进行了改进，取得了良好的效果。 最优化类方法相对于类聚( 投票) 类方法在精确性上有较大的优势，不足之处在于其 一次只能处理一个图形，即事先要对图像进行分割。r o s i n 2 5 在文中给出一个不需要参 数，能使用各种不同曲线表述方式的分割方法。f i z g i b b o n 2 6 完成了原有图像处理中常 用的椭圆拟合算法的改进，提出直接椭圆拟合算法。随后h a l i r 和j a nf l u s s e r 2 7 完成 了更加稳定的椭圆直接拟合方法。李【2 8 】在此基础上结合随机h o u g h 变换的思想，引入 随机采样实现了对多个椭圆的检测。q i a o 2 9 完成了椭圆圆弧数据点的判断，提出一种 基于椭圆圆弧的检测方法，减少了椭圆检测的误判。 1 4 本课题研究的内容 本课题研究了数字图像中，直线、圆和椭圆等几何形状的检测算法与应用( 由于圆 可以作为椭圆的一个特例来处理，椭圆的检测方法在做一些修改之后基本都可以用于圆 的检测，本文中如果没有特别说明，那么提到的椭圆检测都是包括对圆的检测的) 。主 要完成以下内容： ( 1 ) 介绍了该课题在国内外的发展现状，分析和总结了一些数字图像中直线、圆和 椭圆的检测方法。 浙江大学硕士学位论文5 ( 2 ) 提出了数字图像中，直线、圆和椭圆等几何形状检测时边缘检测算子的要求。 完成对a d m 、c a n n y 、s o b e l - z e m i k e 、s u s a n 这四种边缘检测算子的评价，挑选出 符合系统要求的检测算子a d m 。 ( 3 ) 提出一个改进的基于最b - - - 乘法的随机椭圆检测算法，完成与原算法和常用的 几种检测算法的比较。实验表明该算法的改进是有效的，在检测准确性上远高于常用的 几种椭圆检测算法，算法适用范围较广。 ( 4 ) 完成基于边界跟踪和曲线分割的直线、圆和椭圆检测方法。通过实验对该算法 进行了分析，指出还需要改进的地方。 ( 5 ) 结合a d m 边缘检测算子，概率h o u g h 变换直线检测和基于最b - - - - 乘法的随机 圆和椭圆检测，以及直线、圆和椭圆的拟合算法，完成一套显微图像的自动绘图与辅助 绘图系统。 1 5 本章小结 本章介绍了图像理解的基本策略，阐述了数字图像中基本几何形状检测，即数字图 像中直线、圆和椭圆检测这一课题的意义，并综述了国内外检测算法的发展状况。最 后，给出了本文研究的主要内容。 第二章边缘检测算法的研究 2 1 边缘检测的要求 为了从数字图像中检测出直线、圆和椭圆等几何形状，我们首先要从数字图像中 抽取出有用的可靠的对象信息。通常分为两个步骤，1 ) 使用边缘检测算子获得边缘信 息；2 ) 加入后处理，移除边缘图片上多余的点。由此可见，为有效地检测出数字图像 中这些基本几何形状，我们选用的边缘检测算子得到的边缘信息要满足一定的数量与质 量。c a n n y 在文献 3 0 1 中提出，个好的边缘检测算子需要满足以下三条准则： 好的检测算法能尽可能多地标识出图像中的实际边缘。 好的定位标识出的边缘要尽可能与图像中的实际边缘接近。 最小响应图像中的边缘只能标识一次，并且可能存在的图像噪声不应标识为边缘。 但是当边缘检测算子运用在我们当前所要完成的基本几何形状检测的时候，此标准就变 得有些不适合。比如，图像中出现的一些纹理上的细节边缘部分，不但对我们的检测没 啥帮助，而且会消耗更多的运算。因此我们需要的边缘检测算子要满足以下四点要求： 唯一的边缘响应 适合检测物体轮廓 尽可能少的控制参数 高的运算效率 第一条保证获得的边缘是唯一的，这有利于我们减少后续检测的计算量和保持好的准确 率。第二条要确保检测出来的边缘是对物体边界的响应，而非图像纹理边界中的那些细 节性的边界( 不包括不同纹理之间的边界) ，有利于减少后续步骤的计算量。第三条是要 让边缘检测算子能适应不同质量图片的边缘检测要求，这也是后面几何形状检测算法能 否在实际环境下可靠地运行的最基本要求。第四条是出于对整体的考虑，后续的检测算 法需要较大的计算量，在满足一定质量的前提下，尽可能的使用复杂度小的检测算子显 然是人们追求的目标。 6 浙江大学硕士学位论文 7 2 2 各类边缘检测算子 边缘检测算子有多种分类方式，本文按照像素级边缘检测和亚像素级边缘检测 将其分为两大类。a d m ，c a n n y ，s u s a n 等都属于像素级的。亚像素边缘检测最早由 h u e c k e l 提出，现在已经发展为插值、几何矩、正交空间矩等多种检测方法。本文中将 提到的s o b e l z e m i k e 边缘检测算子就属于这一类。 下面我们将分别介绍这些边缘检测算子，并在最后通过实验挑选出最符合要求的算 子用于数字图像中，直线、圆和椭圆等基本几何形状的检测。 2 2 1a d m 检测算子 a d m 是绝对差异模板的简称( a b s o l u t ed i f f e f e n c em a s k ) 。严格意义上讲，该算子 属于利用一阶导数的大小来寻找边缘的一类检测算子。类似于s o b e l ，p r e w i t t ，但是又 和它们不同，不是简单的求解一阶导数然后设置阈值获取边缘。其过程主要分为三个部 分，1 ) 使用高斯平滑模板来处理原图像，减少随机噪声的影响。许多算法，如c a n n y 都有类似的过程。2 ) 遍历图像上的每一点，找到边缘强度与边缘方向信息。3 ) 使用一个 简单的非极大值抑制算法找出候选边缘点，最后通过阈值化得到最终的边缘图片。 1 高斯平滑模板 图2 - 1o r i g i n a la d mm a s k 图2 - 2g a u s s i a nc i r c l em a s k 文献【3 1 】中，作者为了在v l s i 中实现a d m 这一算法，对使用的高斯模板做了简 化，模板见图2 1 。为更有效地平滑图片，减少随机噪声的影响。我们将原文中的系数 昭 凹 驵 n 鼹 加 鲫 眦 毗 眦 盯 n n n n n n n n = | i i i i i = i i = = 7 6 5 4 3 2 l o g g g g g g g g 岛 瓯 研 岛 瓯 岛 吼 岛 岛 岛 岛 岛 国 囟 岛 瓯 岛 研 岛 q 岛 儡， 渐 m 矾 如 伪 曲 岱 m 侥 俄 铱 岛 瓯 岛 一弱 与5 石 筋 一m ，0 0 0 n 石一佰m。；2 占 。0 m l 仉 o 5000 5 屯 l 互 l m 与 m 。 2 占 一4 m 1 n o 一；|寻五 与 与 拍 m 0 0 0 n x 诺 8第2 章边缘检测算法的研究 换成公式2 - 1 求得的单位化了的值。同时将原来的5 x 5 模板转换成7 x 7 的一个圆形模 板，其半径为3 ，涉及3 7 个像素点，如图2 - 2 g ( x ，分) = a e 一( 护+ 矿) 2 伊a r + ，z ，y = 0 ，1 ，2 ，3 ( 2 - 1 ) 2 边缘强度计算 p 也( 2 ) p d t ( 1 ) 两( 2 ) 日l ( 1 ) k ( 2 ) k ( 1 ) 圈 d t i ( 1 ) n d u ( 1 ) 日( 1 ) 日t ( 2 ) n d t ( 1 ) k ( 1 ) p d l ( 1 ) 5 n d t ( 2 )m ( 2 ) p d t ( 2 ) 图2 - 3t h ea b s o l u t ed i f f e r e n c em a s k 边缘强度在一个5 x 5 的模板中计算。模板见图2 - 3 1 ) 先为计算点p c 甜) 在各个方向上的绝对差值做准备： k = k ( 1 ) + k ( 2 ) ，m = v i i i ) + m ( 2 ) 珥= 日r ( 1 ) + 珥( 2 ) ，竭= i t , ( 1 ) + 凰( 2 ) p d 。= 尸d u ( 1 ) + p d l ( 2 ) ，p d t = p d t ( 1 ) + e d , ( 2 ) d t = n d l ( 1 ) + n d l ( 2 ) ，n d l = n d z ( 1 ) + n d z ( 2 ) 2 ) 随后计算水平、垂直和正负对角线方向上的绝对差值： v = i k mj ，h = 珥一场i p d = i p d e 一p d t l ，h d = l n d t 一函i 3 ) 求出边缘强度和边缘方向： & = m a x ( k h ，p d ，n d ) 2 d i r e = d i r ( m i n ( v , 日，p d ，n d ) ) 负对角线方向n d 的d i r 值取1 ；正对角线方向p d 的d i r 值取3 ；水平方向日的d i r 值 取4 ；垂直方向y 的d i r 值取2 。 浙江大学硕士学位论文 9 3 边缘检测与定位 边缘检测与定位分为非极大值抑制与阈值处理两个过程。非极大值抑制过程主要是 候选边缘点查找，为下一步阈值处理提供数据。它通过比较3 3 模板( 如图2 4 ) 内中心 点与垂直于其边缘方向上的点的强度来判断中心点是否是可能的边缘。也就是可能边缘 点上的强度值要大于边缘垂直方向上点的强度值。例如：在d i r = 1 时，如果r p 1 并且p 5 p 9 ，则p 5 点保留原来的强度值和方向，否则置零。随后的阈值处理完成边 p l 易马 只p 5p 6 p 7 玮岛 图2 1 4 非极大值抑制时使用的模板( d e t e c t i o nm a s k ) 缘的定位，获得最终边缘检测的结果。本文中我们采用文献 3 2 】1 5 2 3 章节中介绍的阈 值选取方法：将边缘检测看作个假设检验问题，设p ( e d g e ) 和p ( n o e d g e ) 代表相应事 件的先验概率。则边缘检测过程可以表征为正确边缘检测的概率 f o o p d = p ( g l e d g e ) d g( 2 - 2 ) j t 错误边缘检测概率 f o o 斥= p ( g l n o e d 9 e ) d g( 2 - 3 ) j t 式中，t 是边缘检测阈值，p ( a l e d g e ) 和p ( g l n o e d g e ) 是边缘梯度g ( i ，j ) 的条件概率密 度。通常最优阈值会产生近似相等的误差概率( p r = 1 一尼) ) 。此时边缘检测阈值与信 噪比成线性比例关系，而一般情况下图像平均灰度的大小亦与信噪比的高低成线性比例 关系。因而有 t = s c a l e m e a n ( g ( x ，) )( 2 4 ) 其中s c a l e 是比例系数。 2 2 2c a n n y 检测算子 c a n n y 边缘检测算子是j o h nec a n n y 于1 9 8 6 年【3 0 】开发出来的一个多级边缘检测 算法。更为重要的是c a n n y 创立了边缘检测计算理论( c o m p u t a t i o n a lt h e o r yo fe d g e d e t e c t i o n ) 解释了这项技术是如何工作的。c a n n y 给出的最优边缘检测算法主要分四个 部分。 1 0第2 章边缘检测算法的研究 1 降噪 任何边缘检测算法都不可能在未经处理的原始图像上很好地工作，所以第一步是对 原始图像与指定标准差盯的高斯模板作卷积，得到的图像与原始图像相比有些轻微的模 糊。这样，单独的个像素噪声在经过高斯平滑的图像上变得几乎没有影响。 2 寻找亮度梯度 图像中的边缘可能会指向不同的方向，所以c a n n y 算法使用4 个模板检测水平、 垂直以及对角线方向的边缘。原始图像与每个模板所作的卷积都存储起来。对于每个点 我们都标识在这个点上的最大值以及生成的边缘的方向。这样我们就从原始图像生成了 图像中每个点亮度梯度图以及亮度梯度的方向。实际实现中可以用高斯模板来获得每个 点亮度梯度图以及亮度梯度的方向。 3 非极大值抑制 c a n n y 的非极大值抑制过程将非零点所在的区域细化为单像素的候选边缘，具体过 程如下：对于每一点p ( z ，可) ，我们选择两个毗邻的点( 一，矿) 和( ，矿) 。这两点是p 点 梯度方向与其8 - 连通邻域点所组成的矩形的交点，如图2 - 5 ，点上的值通过插值得到。 如果p 点的值大于这两个毗邻点的值，那么保留p 点原来的值，否则置零。 图2 - 5 非极大值抑制 8 e ( x ，y ) 矿矿、 4 滞后阈值处理 滞后阈值处理需要两个阈值，高阈值( t ) 与低阈值( t 1 ) 。通常如的值由图像中边缘 占的最低比例r a t i o 求出，这些点称之为强边缘像素。本文中t l 取0 5 t ，位于t f 和 “之间的点称之为弱边缘像素。最后通过将8 - 连通的弱像素集成到强像素，执行边缘连 接，得到最终的边缘图像。 2 2 3s o b e l - z e r n i k e 检测算子 z o m 正交矩( z e r n i k eo r t h o g o n a lm o m e n t ) 亚像素边缘检测算法最早由g h o s a l 和m e h r o t a 在1 9 9 3 年提出【3 3 】。算法的优点是定位精度较高，但算法运算时间较长。 浙江大学硕士学位论文 1 1 曲迎东和陈善本在2 0 0 3 年提出了利用s o b e l - z e m i k e 矩算子的快速亚像素边缘检测方 法 3 4 - 3 6 1 。对原来z e m i k e 矩算子的算法做了简化，并引入s o b e l 算子的预处理过程， 在保持准确性的同时，有效地减少了算法运行的时间。 1 s o b e l 算子粗略检测 s o b e l 算法参见文献【3 7 】，由于s o b e l 也是一种微分边缘检测方法，可以参考前面 a d m 算法中使用的策略来求取阈值t 。也就是使用公式2 _ 4 的值。 2 简化的z o m 算子 z e r n i k e 矩算子的基本思想是通过计算每个像素点的4 个参数来判断该像素点是否 为边缘点。像素点的4 个参数为：豇为灰度阶越高度；h 为背景灰度；z 为中心点到边缘 的距离；西为中心点到边缘垂线与z 轴的夹角，如图2 - 6 所示。 z 图2 - 6 平面亚像素边缘阶跃模型 = 半：( 。m 删 ( 2 - 5 ) 积分核的函数为。( p ，0 ) = 。( p ) 棚，符号+ 表示共轭。巩。( p ) 为： =n-台i,。1)2硒(_诵1)i(n_i)!pn_2i ( g h o s a l 在提出此算法的时候【3 3 】使用z ，七的信息来判断边缘，曲迎东改进的算法则直 1 2第2 章边缘检测算法的研究 响。2 ，七，a m p 由公式2 7 至2 - 1 1 求出。 = a r e t a n ( i m ( 历1 ) r e ( z 1 1 ) ) z l = p c e ( z n ) e o s ( o ) + i m ( z 1 1 ) s i n ( ) z = 忍o z i l 惫= 捣 a m p = v r e ( z l 1 ) x r e ( z l 1 ) + i m ( z l 1 ) x i m ( z 1 1 ) ( 2 7 ) ( 2 8 ) ( 2 - 9 ) ( 2 - 1 0 ) ( 2 - 1 1 ) 2 2 4s u s a n 检测算子 s u s a n 边缘检测算子基于对圆形邻域的非线性操作过程。给出一个图像点以及以 该点为中心的某一半径的圆，检测算子求出和中心点强度差在一定阈值t 范围内的点的 个数，再与圆形区域内大约3 4 的点数求差。若最后求得的值小于零，则中心点不是边 缘点，反之则是。其数学表达过程如下： 一而) ： 1 巧! “2 7 雪31 。( 2 - 1 2 ) c ( r ，r 0j = 。 10 i f i ，( 力一，怖) i t ， 犯( 而) = c e 而) ( 2 - 1 3 ) 骗) ： 9 。以神i l n ( r o ) g ( 2 - 1 4 ) 10o t h e r w i s e ， 其中而是圆形邻域中心的位置，刊睦其他位置上点的位置。竹( 而) 是强度差大于阈值t 的 点的个数，9 为几何阈值( g e o m e t r yt h r e s h o l d ) ，大小等于堡严，r ( 而) 为初始边缘结 果。实际上算法实现的时候通常将公式2 1 1 换成更为稳定的公式2 1 5 ，同时还要通过 二阶矩求得边缘方向信息，用于算法最后类似于c a n n y 的细化过程。检测之前还需要 用保持边缘的非线性去噪声算法对图像进行平滑。详细过程见文献 3 0 】 c ( t 而) ：e 一( 型1 盟) 6( 2 1 5 ) 2 3 实验与比较 2 3 1 实验内容 之前大多数边缘检测算法的评价，都是用由人工主观判断调节的指定边缘检测算子 获得的边缘信息作为标准边缘信息。本实验参考文献【3 8 】中的方法，使用4 0 幅背景为纹 浙江大学硕士学位论文1 3 理的人工物体或者自然物体的图片，标准的边缘信息由手工绘制得到。边缘描绘按照两 个标准：1 ) 是闭合的物体边缘轮廓或者是物体内部的轮廓；2 ) 两种不同纹理之间的边 界，例如天空和湖水。 图2 7 测试用图片和相应的标准边缘图片 设e d o 和1 3 d o 为标准边缘信息的轮廓像素点和背景像素点，e d 和b b 为边缘检 测算子求得的对应像素点。正确检测的边缘像素点定义为e = 五dne d o ；边缘检测算 子未检测到的边缘点定义为e f n = b dne d o ；边缘检测算子检测到的非边缘点定义为 e f p = e dnb d o 。边缘检测算予的准确性由公式2 1 6 获得。 p=可而numel(e雨)焉而，(2-16)numel(en u m e l ( e f pn u m e l ( e f n ) +) +) 其中n u m e l ( x ) 表示集合x 中元素的数量。 由于手工选择的边缘点和梯度极大值定位的边缘点不一定精确地位于同一个位置上 ( 人眼视觉受心理特性的影响) ，原文中使用7 x 7 的邻域去查找对应的边缘点，本文使用 形态学的方法来处理。过程如下，其中s e 是一个值全为一的7 x 7 矩阵，o 表示形态学 中的膨胀操作。 e = e a n ( e d o o s e ) f p = e x o r e a f = ( e d o n ( e o s e ) ) z d r e d o 实验中各个算子参数的取值范围如下： a d ms c a e 在1 5 到5 5 之间按一定间隔取4 0 个值。 c a n n y 盯= 2 k 2 ，k = 一l ，o ，1 ，2 ，3 ，4 ，5 ，6 t = 0 7 ，0 7 5 ，0 8 ，o 8 5 ，0 9 ( 2 - 1 7 a , i ( 2 - 1 7 b 1 i 2 - 1 7 c ) 箩 1 4第2 章边缘检测算法的研究 s o b e l - z e m i k es c a l e = 1 ，1 5 ，2 ，2 5 ，3 n 唧= 1 0 ，1 5 ，2 0 ，2 5 ，3 0 ，3 5 ，4 0 ，4 5 s u s a n 平滑模式，参数d = 2x2 k 2 ，七= 一1 ，0 ，1 ，2 ，3 ，4 ，5 ，6 边缘检测模式，参数t = 1 0 ，1 5 ，2 0 ，2 5 ，3 0 实验中先运行平滑模式去噪，随后用边缘检测模式获取边缘信息。 2 3 2 实验结果 1 ，各类算法比较 实验在一台c e l e r o n2g h z 的p c 机上用m a t l a b6 5 完成。算法边缘检测性能用盒 型图( b o xa n dw h i s k e r ) 画出，盒子中间横线是数据的中位数，封闭盒子的上下两横线 为上下四分位数，盒子上下两边各有一条纵向的线段，表明盒子外面点的分布。如果所 有样本点中的数据都在离四分位点1 5 倍盒子长度之内，则线的端点为最大和最小值， 超过这个范围的离群点单独绘出。图2 - 8 是挑选出来的典型实验数据，图2 - 9 为边缘 检测结果的例子。图2 - 1 0 为本实验过程中，各个算法在各幅图片上按照不同参数检测 时，算法运行的平均时间。 2 a d m 算子s c a l e 的值 图2 1 1 给出了a d m 算子在实验中对于各幅图片检测结果最优时使用的s c a l e 值， 可以看出算法的阈值参数是可以按照文献 3 2 1 中介绍的方法来求得。本次实验中s c a l e 的加权平均值为2 6