（机械设计及理论专业论文）基于角点的实体重构及数值流形网格自动生成方法研究.pdf

摘要 反求工程是目前设计和制造领域新的研究方向，与传统的设计方法相比，它 是由产品到图纸的过程。反求工程的关键技术是测量和重构，常规的测量方法是 接触式的坐标测量法和层析法，前者的测量效率低，对测量设备的要求相当高， 不适用于软形体和大型体的测量，后者的测量是破坏性的。近年来，非接触式测 量得到很大的发展，计算机视觉测量方法是非接触式测量的一种，随着计算机技 术和信息处理技术的发展，这类测量方法日趋成熟。计算机视觉测量方法是应用 计算机视觉和图形图像处理技术，通过对二维图像的分析获取实体三维信息的一 种方法，这种方法的优点是方便且适合大型体的测量，通过一部或多部摄像机就 可实现测量。 本文在测量和重构过程中均采用角点作为对应点的匹配。本文对角点做了较 为深入的研究，研究了角点检测算法的评价、应用、分类，综述了现有的各类角 点检测算法。我们提出了一种基于聚类匹配的角点检测算法，该算法的基本思想 是角点产生于不同聚类之间，通过圆形窗口扫描图像，将窗口中不同的区域与图 像的各聚类分别比较，根据匹配关系可以判断角点的存在。我们将该算法应用于 二值图像，并与m i c 和h a r r i s 算法作了比较，结果表明，该算法仅在斜线方向产 生错误的角点反映，其他方面相当，但随着窗口的增加算法速度将会变得很慢。 视觉测量的核心就是相机标定问题，本文对线性标定、非线性标定和自标定 理论做了论述。我们建立了一套基于p c 的视觉测量系统，结合t s 址相机标定理 论，用了四个月的时间开发出了一套相机标定软件模块，我们进行反复的实验验 证，可以实现相对误差在千分之五以内。 我们将以上的测量模块应用于数值流形网格的自动生成系统中。在该系统中， 首先使用角点检测算法提取图像中的角点，将这些角点依次连接起来，这样就构 成了计算域的物理网格，通过相机标定技术可以得到各角点坐标。最后采用 d e l a u n a y 三角网格化得到计算域的数学网格。 本文研究的是二维实体的测量和重构问题，同时也为三维物体重建提供了一 般思路，对三维实体重构也具有借鉴意义。 关键词：反求工程角点检测相机标定数值流形网格化分 a b s t r a c t r e v e r s ee n g m e e r i n g ( r e ) i san e wf i e l do fc a d c a m w h n ec o n v e m i o n a l e n g i f l e 酬h g 劬吡s f o r f n se n g i n e e 血gc o n c e p t sa 1 1 dm o d e l si n t o r e a lp a n s ，i nr e v c r s e e n g i l l e 舐n gr e a lp a r t sa r e 虹a i l s f o n e di n t oc a d d a t at h a tc o m p u t e rc a nr e c o g m z eo r 扛a n s f o n nr e a lo b j e c t s 证t ov i r t u a lr e a l i t ye n v i r o 衄e n t s t h e r ea r et w o k e yt e c q u e s m r e ，o n ei sn l e a s u r e ，a i l dn l eo 也e ri sr e c o n 曲m c t i o n n o r m a lw a yo fm e a s u r ei s t o u c h e d - f o 啪，i l l c l u d i n gc o o r d m a t em e a s u r i r 唱m e t h o da r l dl a y e ra a l y s i sm e t h o d ，b u t i ti sn o tp r o p e rt om e a s u r eb i go b j e 吐d u et o p o o re m c i e n c ya n dm g ha c c u m c y r e q u i r e m e m o fh 盯d w a r e ，a n d 1 a y e r 姐a l y s i s m e t l l o dm a k e s o b j e c td e s t m y e d r e c e m l y ，谢mm ed e v e l o p m e mo fi l o n - t o u c h e dm e a s u r em e l o d ，c o m p u t e rv i s i o n m e a s u r em 孔o dh a sb e e np o p u l a r b a s e do nc o m p u t e rv i s i o na i l di m a g ep r o c e s s i n g m e o w c c a ng 血3 di i l f o m a t i o no f o 巧e c tt h r o u 曲p r o c e s s i n g2 di i m g e i ti sv 吖 c o 删e n tf o r b i go b j e c t st ol l s ec 锄e m s h 1t h i s p 印e r ，w em a t c hc o m e r sb e t 、e e no b j e c ta n di m a g et on l e a s u r e 趾d r e c o n s m l c to b j e c t w bh a v ea d e c p c r r e s e a r c ho f c o m e r d e t e c t i o n ，协c l u d i n ge v a l u a t i o n ， 印p l i c a t i o na n dc i a s s i 蛳n g w e 砷d u c ean e wc o m e rd e t e c d o na l g o r i t l l i i l c o m c rd e t e c t i o na l g o b a s e do nd u s t e r i n gm a t c h e d ，丘d ma ni d e am a tc o m e r s g c n e r a t eb e t 、e e ns o m ec l 删e r i n g w es c a i l 趿i m a g e 恤o u g l lu s i n gac i r c l l l a r 晰i l d o w 恤tb ed i 啊d e di n t o8u 】= l i t s ，t h e nw ec a i lf i n dc o m e r sa 矗e ra n a l y z ec o r e l a d o nb e 铆e e n e a c hl l l l i ta i l de a c hc l u s t e r i n gi ni r n a g e h p u ta b i n a r yi m a g e ，c o m p a r e d mm i c 缸d h a r r i sa l g o r i t h m ，t h i sn e w a l g o r i t l l mo n l yr e s p i o n s e sf 砒s ec o m e r si nd i a g o r l a ll i n e ，b u t s p c e d i sl o w e rw h e nm ec i r c u l a r 、i i l d o wi sb i g g e l c a l n e r ac a l i b r a t i o ni sa n c c e s s a r yp r o c e s si 1 1c o m p u t e rv i s i o nm e a s u r e h l 也i s p a p e r ，w e d e s c r i b em em e o r yo fl i n e a r c a l i b i m i o l l ，n o l l l i n e a rc a l i b 洲o n 锄d s e l f c a l i b 洲o n w bh a v ea s s e n l b l e dam a c i l i n ev i s i o ns y s t e mp c - b 嬲e d ，a i l dd e v c l o p e d as o r w a r em o d u l eu s i n gt s a ic a l i b r a t i o na l g o 捌瑚i l lf b u rm o n 缸w bt e s t 也i s m o d l l l ea g 血a n d a g a i n ，a tl a s tt h er e l 撕v ee r r o ri s 吼d e r5t h o u s 龇l d t h s i i w e s 吼u p as m a l lm e s ha u t o g e n e r a t o ns y s t e mo fn u m e r i c a lm a n i f o l dn 硷t h o d r nt h i ss y s t e m ，f i r s t l y w ec o n s t m c tp h y s i c a lm e s ht h r o u g hl i n k i n gc o r r l e rd c t e c t c db y m i c a l g o r h h mm t u m t h e nw ec a ng a i nr e a lc 0 0 r d 访a t e so fe a c hc o m e rb yc a m c r a c a l i b r a t i o n l a s t l y w ec a nu s ed e l a u m y 仃i a n g u l 砒i o n st og e n e r a t em e s h a sr e s u ho f t h i s ，w eg a i t lm 砒h c m a t i cm e s h o f n 啪e r i c a lm a n i f o l dm e t h o d i nt h i sp a p e r w eg i v es o m er e s e a r c ho f2 dm e a s u r e 吼dr c c o n s t r u c t i o n ，b u ti t h i n ki tw i l lh e l py o u 曲a s p e c to f 3 dm e a s u r e 锄dr e c o n s t m c t i o nt o o k e y w o r d s ：r e v e r s ee n g i n e e r i n g ，c o m e rd e t e c t i o n ，c a n 埘ac a l i b r a t i o n ， m e s h g e n e r 砒i o n o f n u l n e r i c a li n a n i f o l dm e t h o d 第一章绪论 _ _ _ _ - _ l _ e ! _ ! ! l _ 目l ! _ _ _ _ l l - - - _ l _ _ _ e _ - _ | l l ，l _ i _ - - _ _ _ l _ _ 自 第一章绪论 1 1 研究背景及国内外发展现状 自从上个世纪五十年代以来，全球制造业发生了很大的变化。计算机技术的 迅猛发展，信息化时代的来临，对这一变革起到了根本的作用。进入七十年代中 后期，直到八十年代，市场竞争转到如何全面提高t ( t i r n e ) 、q ( q u 址i 哆) 、c ( c o s t ) 、 s ( s e r v e l 上。作为一种新经济模式的知识经济的兴起，信息化带动制造业形成了新 的经济增长，所有这些为“机械设计及理论”、“先进制造技术”等提出了更新、 更高的要求。 传统的设计过程是图纸 产品的过程，即设计者根据二维图纸的要求操作 数控设备，经历不同的工序进而生产最终产品。与传统设计过程相比，反求工程 ( r e ：r e v e r s ee n g i n e e 血g ) 正好相反，它是在没有设计图纸或者设计图纸不完整以 及没有c a d 模型的情况下，按照现有零件原型，利用现有的数字化测量技术及 c a d 技术重新构造零件的c a d 模型的过程。反求工程是计算机科学、现代设计 与制造技术和精密测量技术相结合而发展起来的一个新领域。九十年代以来，反 求工程受到各国学术与工业界的重视，已经成为c a d c a m 领域新的研究热点。 反求工程的主要目的是改善技术水平，提高生产率，增强经济竞争力。在经济技 术发展中，应用反求工程可以消化吸收先进技术经验，大大促进了技术的进步。 据统计，反求工程可使产品研制周期缩短百分之四十以上，极大提高了生产率。 反求工程包括三个基本阶段：零件原型的数字化 提取零件原型的几何特 征 零件原型c a d 模型的重建，如图1 1 所示。 图卜1 反求工程的基本过程 f i g 1 - 11 1 1 ep r o c e s so f r e 零件原型的数字化，即获取零件原型表面点的三维坐标值： 零件原型的特征提取，即采用几何特征匹配与识别的方法来获取零件 原型所具有的设计与加工特征； 零件原型的c a d 建模，对零件表面进行重构，获取c a d 文件。 反求工程过程中的两大关键技术就是测量和重构。反求工程中的测量方法可 分成两类：接触式与非接触式。接触式测量方法包括坐标测量法和层析法，前者 对测量设备的要求相当高，不适用于软形体和大型体的测量，后者的测量是破坏 性的。非接触式测量以其显著的优点倍受重视，计算机视觉测量方法是一种新型 的非接触式测量方法，它通过一个或多个相机获取零件图像，通过图像上的各点 对应关系反推三维空间中的对应点的位置关系，从而达到测量目的，它综合了计 算机视觉和图形图像处理技术，具有广阔的发展前景。这种测量方法要求对摄像 机进行标定，取得摄像机的内外参数，进而计算三维空间点之间的关系，本文采 用的就是这种测量方法。重构技术类似于计算机视觉中的三维重建，通过拟合形 体中的典型几何特征来实现形体的整体的、连续的表达。本文采用d e l a l l l l a y 三角 剖分方法来实现形体的拟合。 1 2 研究内容及关键问题 计算机视觉和图像处理技术为反求工程提供了新的思考方法，本文主要是基 于此类方法。在生物视觉系统中，生物体对外界的视觉感知是通过感光细胞和神 经纤维将落在视网膜上物体的影像接收并传输到大脑，经过大脑的加工整理形成 生物体的感知。物体的表面特征( 包括：角点、边缘、纹理等) 是生物体识别外界 物体的重要内容，j a c o b 指出“凸凹和封闭特征是人类和机器视觉中的显著线索， 在判断目标和背景时起重要作用”l ，。在计算机视觉中，根据m a r r 的三层视觉理 论框架【4 】，抽取二维图像上的角点、边缘、纹理等基本特征是整个系统框架中的 第一步，这也被称为早期的视觉处理阶段。角点是图像中最基本的特征之一，它 集中了图像上的很多重要的形状信息，通过提取角点，可以构造基元图，进而可 以识别并重建三维物体。 角点检测技术可以用在物体的三维重建方面。通过提取图像中各基元的特征 点，通过相机标定技术和数学方法，利用计算机图形学实现物体表面的绘制。如 图1 2 所示，在研究数值流型网格的生成时，可以利用图像处理技术实现网格的 自动生成。首先采集被研究对象的若干图片( 通常是物体截面) ，对图像进行预处 理以去除噪声：其次提取图像中的角点( 通常是边缘处的特征点和裂纹、缝处的特 2 征点) ，对摄像机进行标定得到各角点的三维坐标值；最后利用曲线拟合技术重构 边界和裂纹，使用d e l a i l l l a y 三角网格划分算法生成数值流型网格，最终绘制图形。 在数值流型网格的自动生成过程中，影响因素有以下几个方面： 阻像噪声的影响，外部条件造成的图像质量差； 由于摄像机镜头等硬件原因，引起图像产生畸变； 伪角点对构造边界、裂纹的影响； 网格生成过程中的尖锐三角形的影响； 另外，在网格生成过程中，速度也是一个重要的因素，本文将重点讨论前三 个方面的影响因素。 图卜2 数值流形网格自动生成过程 f i g 1 2m e s ha u t o g 铋e r a t i o np m c 瞄sf o r m 瑚e r i c a lm a i l i f o l dm e i l l o d 本文着重在角点检测方面作了较为深入的研究，并提出了自己的思路；我们 将角点匹配技术应用在相机标定和实体重建过程中，并开发出了一套数值流型网 格自动生成的小型系统。本文拟解决以下关键技术： 利用角点匹配二维图片和三维空间的特征点，寻求一种优化的角点检测 技术： 立体视觉中的相机标定技术； 利用三角剖分方法拟合实体表面； 开发一个数值流型网格自动划分的小型系统； 利用计算机图形学可视化重构结果。 1 3 本文的研究意义及创新之处 立体视觉和3 d 重建技术在加工制造业中有着广泛的应用前景。本文利用这 种先进技术来实现加工制造中的反求工程原理，利用计算机视觉原理来解决反求 工程中的两个核心技术，即特征匹配和模型重建。具有以下重要意义： 利用角点拟合实体边界，对现有的角点检测算法进行了分类，综述各类 3 角点检测算法，并作了较为详细的比较，对目前图像处理领域研究的前 沿一一数学形态学角点检测做了介绍： 利用特征点的匹配，克服了在传统的零件原形模型重建过程中，零件原 形的尖边、锐角部分的重建效果不很理想，表现为棱角不明显、轮廓模 糊等缺点； 通过依靠数字图像处理技术对实体边界进行重构，近而使用网格划分技 术来实现数值流型单元的自动生成； 提出了一种新的基于聚类匹配的角点检测方法，实验证明，该算与其它 算法比较，具有相当效果： 本文针对数值流型网格的自动生成技术提出了具体的思路，这也为其他 领域的应用提供了借鉴和启示。 1 4 本文的主要工作和内容安排 本文对角点检测、相机标定及网格划分技术进行了探讨和研究，并将此项技 术应用在数值流型网格划分的具体应用上面，论文的主要结构如下： 第一章为绪论，从反求工程的角度出发，将数字图象处理技术应用于先进设 计与制造领域是一个新的研究方向，本节简要介绍了二者的基本概念和研究流程， 并详细说明了本课题的研究内容及需要解决的关键问题，同时也提出了本文的一 些新的想法和实现。 第二章为角点检测部分。本文对角点检测算法做了较为深入的研究，提出了 对现有的角点检测算法的分类方法。开始部分花了大量篇幅对角点检测算法做了 综述，并比较了各类算法的优劣，之后对目前数字图象研究领域的前沿一一数学 形态学，做了简单介绍，并对数学形态学角点检测算法做了讨论。本章最后提出 了一种新的基于聚类匹配的角点检测算法，本文针对二值图像，与目前流行的 h a 耐s 角点检测算法和m i c 角点检测算法作了比较。 第三章为相机标定部分。相机标定是实体重构和三维重建必不可少的步骤， 相机标定的主要作用就是确定在图像和三维空间点的关系。本章介绍了线性标定、 非线性标定和自标定的概念和典型算法。针对t s 刖相机标定算法，本文利用 v c + 十工具开发出了一套相机标定模块，实现标定相对精度控制在千分之五以内。 第四章介绍了本课题所开发出的一套数值流形网格自动生成系统。首先介绍 4 了该套系统的软硬件组成，随后介绍了d e l a u l l a y 三角网格生成技术，形成了一套 完整的网格生成系统。 第五章为结论和展望部分，总结了本文研究内容、需要改进的地方和下一步 值得探索的重点。 广东工业大学工学硕士学位论文 2 1引言 第二章角点检测技术 人们对角点的研究起始于对图像中凸凹线条的检测，在物体的图像中，各种 特征像素点总数要少的多，通过对这些局部特征处理，极大的提高了计算速度， 使得实时处理成为可能。角点是图像的一个重要的局部特征，它集中了图像上的 很多重要的形状信息。由于角点具有旋转不变性，几乎不受光照条件的影响，角 点只包含图像中大约0 0 5 的像素点，在没有丢失图像数据信息的条件下，角点 最小化了要处理的数据量，因此角点检测具有重要意义。 角点检测是早期视觉的一种图像处理方法，对中后期的视觉处理有重要作用。 本章开始部分详细介绍了基于边界特征的角点检测、基于点特征的角点检测和基 于模板的角点检测，并对各类算法进行了分析和比较；中间部分特别介绍了当今 流行的一种数学形态学的角点检测技术；最后本文提出了一种新的基于聚类匹配 技术的二值图像角点检测算法，并与h a r r i s 和m i c 算法作了比较。 2 1 1 角点的定义 角点，人们又称之为感兴趣点、特征点、连接点或显著点等。在计算机视觉 领域中，对于角点目前还没有很好的数学定义，一般认为：角点产生于两条或多 条相对直线交叉的区域。不同的检测方法对角点有不同的定义。a r o s e n f e l da n d e j o h n s t o n 提出，利用曲线上某点前后臂的夹角的余弦值来估算该点的曲率， 并将局部曲率最大点定义为角点；h f r e e 腑na n dl s d a v i s 【6 1 用相邻两点的 前臂与水平轴之间夹角的变化作为角点检测的依据；hm o r a v e c 定义角点为各个 方向亮度变化足够大的点。根据连接角点的相对直线的分布，可以将角点分为l ( 或 v ) 、t 、y 和x 型角点，如图2 一l 所示。 除了角点的交汇类型特征外，还有如下特征： 钝度( b l u n t n e s s ) ，指角点尖端的钝凸程度； 内角( i n t e r n a la n g l e ) ，目标中构成角点两相邻边界的夹角； 方向( o r i e n t a t i o n ) ，角点夹角的角平分线方向； 6 第二章角点检测技术 锐化度( s h a r p n e s s ) ，边界在角点处的连续程度； 对比度( c o n t r a s t ) ，角点附近目标与背景的灰度差异程度。 圈2 一l ( a ，b ，c ) l 型角点，( d ) t 型角点，( e ) y 型角点，( f ) x 型角点 f i g 2 1 ( a ，b ，c ) l - t y p ec o r n e r ，( d ) t t y p ec o h l e r ，( e ) y t y p ec o r n e r ，( f ) x t y p ec o r n e r 角点具有如此丰富的特征信息，但在具体的实际应用中，人们往往只考虑角 点的位置特征而忽视了角点的其它特征，这是造成角点检测算法中对角点误检、 漏检、多检的原因之一。 2 1 2 角点检测技术的具体应用 角点检测属于低层次的图像处理，它为图像的进一步处理提供了重要信息。 角点检测被广泛的使用，因为含有很高的信息量来反映图像的局部特征，能够更 可靠的匹配图像。角点检测主要在光流计算、运动估计、目标追踪、形状分析、 相机标定得到广泛应用，在3 d 重建、视觉的定位和测量等方面具有应用价值。 光流计算 所谓光流，= ( 主，是图像各点的二维瞬时运动，一旦给出图像的亮度模式， 就可以利用时间变化的特征点匹配来度量视差。把图像中的角点作为特征点，首 先在图像序列中检测和跟踪角点，然后记录角点在图像序列中的位置，这样可以 通过相邻图像帧之间角点的位移场来计算光流场。基于角点跟踪的光流场计算方 法由于图像噪声的影响，目前还没有满意的结果。 运动估计 将一帧图像中的一组结构作辨识，对另一帧作搜索，以寻找对应的结构，这 种运动分析和估计的方法叫匹配技术。角点匹配技术近年来已经得到人们的很大 重视。这是因为( 1 ) 利用角点匹配处理的数据量大大减少；( 2 ) 角点匹配的精度高。 7 通过检测多帧图像中目标的运动，提取运动参数，分析目标的运动规律。利用角 点匹配计算两帧图像之间的视差来估计物体运动的瞬时位置速度，获得运动参数， 是一种很好的方法。 形状分析 形状分析是指用计算机图像处理和分析系统对景物的诸目标提取形状特征， 对景物作识别、理解。而角点则体现了目标形状的本质特征，对形状分析具有很 大作用。对于简单的目标来说，在形状分析时，先提取目标图像的角点，然后通 过拟合的方式构造目标边界，从而估计出目标的形状。对于复杂形体的目标，可 以把区域分解成若干区域基元，再对每个区域基元构造边界，最后根据区域基元 的组合关系将每个区域基元构造边界合并，得到目标构造边界。 相机标定 相机标定技术是3 d 重建和视觉测量的必不可少的步骤，相机标定精度很大程 度上决定了3 d 重建和视觉测量的精度。相机标定需要标定内、外参数和畸变参数， 它的任务就是找出世界坐标和图像坐标之间的变换关系。采用标定靶标定时，必 须知道所标定点的图像坐标。要想知道标定靶图像中某些点的像素位置，利用角 点检测是一种很有效的方法。角点检测方法可以检测图像中特征点，从而可以得 到特征点的像素坐标，这样就为下一步相机参数标定提供了已知条件。利用角点 检测方法所获得的图像点的像素坐标精确，但受噪声干扰大，如果采用抗噪性较 好的算法，将会进一步改善标定的精确性和可靠性。 2 1 3 对角点检测算法的评价 对角点检测方法的评价目前还没有令人满意的定量的分析方法，在各种角点 检测算法纷杂的情况下，建立一套标准客观的评价准则是很重要的。 对角点检测算法评价遵循以下原则 1 0 j ： 角点检测算法必须满足哪怕再细微的角点也能检测出来，同时又能有效 的抑制噪声； 角点检测算法应该满足所检测出的角点尽可能靠近它的真实位置； 对同一场景的多幅图像处理时，所检测的角点的位置不应该变化； 算法应该能快速、自动的识别出所有角点。 根据以上原则，形成了一套评价标准：( 1 ) 一致性要求，包括算法的稳定和对 噪声的敏感性；( 2 ) 准确性要求，就是通过计算检测的角点与真实位置的角点的偏 差来评价算法：( 3 ) 复杂性要求，就是算法的运行速度、复杂性要满足实时任务的 需要。 c o r d c l i as c h i l l i d 呻1 等人提出了一种新的定量的评价标准：重复率和信息内容。 重复率用来比较在各种观察条件下一个给定景物的多幅图像之间角点的几何稳定 性，计算两幅图像之间的重复点与整个被检测点的数量之比。信息内容表示角点 的显著性，信息内容的值越大，算法的性能就越好。 2 1 4 角点检测算法分类 3 0 多年来，越来越多的学者对角点检测投入了研究，因此产生了很多算法。 可将这些算法分为： 基于边界特征的角点检测，它的基本思想是将角点看作是特殊的边缘点， 通过边界链码或边界曲率来检测角点，因为此类算法依赖边缘特征，在 边缘特征中的任何缺点和错误都将影响角点的检测； 基于点特征的角点检测，这类算法把角点看作是孤立的点，直接通过像 素点的灰度信息来检测角点； 基于模板匹配的角点检测； 数学形态学角点检测技术； 基于聚类匹配的角点检测方法，这是本文提出的一种全新的方法。 2 2 基于边界特征的角点检测 该类算法又分为基于边界链码的角点检测和基于边界曲率的角点检测。它们 的共同点就是将角点看成是边界的特殊点，通过搜索边界特征来检测角点。 2 2 1 基于边界链码的角点检测 这种检测的方法是，先分割图像，抽取边界的f r e e m a n 嘲链码，将方向改变 迅速的点标记为角点。 链式编码又称为弗里曼链码( f r e e m n ，1 9 6 1 ) 或边界链码。链式编码主要是记 录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示为：由某一 起始点开始并按某些基本方向确定的单位矢量链。如图2 2 ，使用8 个编码表示8 个基本方向。链式编码的前两个数字表示起点的行、列数，从第三个数字开始的 9 每个数字表示单位矢量的方向，八个方向以o 一7 的整数代表，由曲线起始点碣到 终点，整个链码的序列可写成，4 = 玎n 。a ：口3 ，其中口， o ，7 ) 。如图2 3 所示，可以使用f r e e m a n 链码来表示图中的区域：4 = 2 4 6 7 7 0 1 1 2 3 3 4 5 6 4 。 3 4 1 起始点伫，4 ) zl 0 产弋 声 旦j 6 、， 6 l 一 入y k 幽2 2f r e e t i l a r i 链码方向图2 3f r e e m a n 链式编码不意图 f i g 2 - 2f r e e r n a nc h a i nc o d ef i g 2 3f r e e m a nc h a i nc o d ec u r v e s f r e e m na n d d a v i s 利用直线段弓来扫描链码曲线，e 是连接s 个链节 ( 。，。，a 。，n ，) 端点的直线段，s 被推荐的值为5 到1 1 ；线段e 与x 轴的夹角 定义为，因此有如下定义： 茸：2 坠兰掣：一啄。， ( 2 1 ) 彤被称为递增曲率，当扫描到角点处时，口必不为零，这样就可以提取出角 点来。定义角点处递增曲率的和为矿；： = 鲜 ( 2 2 ) ，一j 考虑到小曲率情况，定义、乞， = m a x 口：j 工，( - ，) ，v 1 u 0 f 2 = m a x p ：酲。+ ，( 一，) ，v 1 u f ) 其中： ：a r c t a i l l s l 最后取得角点检测判断公式： 1 0 第= 章角点检测技术 k i ：e 艺67 厄 ( 2 3 ) 这样在链码边界的每个像素点处利用盯一曲率公式即可判断角点的存在。 在随后的研究中，b e u sa n dt i u 【1 4 1 改进了这个算法，他们采用了不同长度的 扫描线段计算出芷，然后取平均值。c 0 0 p e r 叫1 则利用链码处像素坐标估计最大曲 率值来寻找角点。而h s i n t e n ga n dh u 使用多边形近似边界链，然后把两边的 交点作为角点。 这类方法由于依赖于前期的区域分割，由于图像分割本身是一个很复杂的工 作，涉及到复杂的浮点运算和区域支持的选择，这样使得角点检测算法的复杂度 更大，并且在图像分割中出现的任何错误都有可能影响角点的检测，因此，目前该 法己基本被放弃。 2 2 2 基于边缘曲率的角点检测 这种方法的特点是通过各种方法计算边缘某点处的曲率，找出局部极值，再 通过闽值技术来进行角点检测。 k i t c h e na n dr o s e n f e l d 采用目标边缘梯度方向的曲率变化率来检测角点： 设可微图象为厂( 置y ) ，它在点( x ，y ) 处的梯度为 g ( 础) ：豢f + 要j ；力+ z _ ， ( 2 4 ) 麟卯 。 梯度方向角口的正切为 乜n 目= 著篆= z = z ( 2 s ) 梯度方向目相对x 的变化率为 口：- 娑：掣宴 ( 2 6 ) 积0 2 盘 由此容易算得 同理，有 哦= 警= 等等 ( 2 7 ) 瓯= 爹= 篆筹 工7 ) 度方向 ( 2 8 ) 图2 4k i t c h e n r o s e n f e l d 角点检测方法 f i g 2 _ 4k i 劬e n r o s e 峨1 dc o m c rd e t e c t i o na l g o m m 如图2 4 所示，由于梯度矢量g ( z ，y ) = 优，) 7 指向函数变化率最大的方向， 而矢量厅= ( 一，f ) 7 是和g 垂直的，所以其反映可能边界，的局部走向( 因，是否 为边界和其边界强度有关) 。梯度方向口的变化率( 或，口：) 在可能边界走向上的投 影反映了可能边界的尖锐程度。从而将梯度g 的方向目的变化率矢量口。= ( 哦，曰：) 7 在，上的投影即日( 形) 和梯度的幅值的乘积世作为角点存在性的判断依据， 足= 器似枷删2 = 盟等铲泣。， i 世l 越大，则角点存在的可能性就越大，当大于某个阈值时，就检测该点为角 点。 此法存在缺点是： 严重依赖二阶导数，对噪声极为敏感； 把某一方向上曲率很大的边缘点误判为角点； 角点定位性能差，所检测到的角点位置可能与实际位置相差甚远； 在随后的研究中，出现了几种类似于k i t c h e n r o s e n f e l d 的角点检测方法。 z u n i g a _ h a r a l i ck 【1 8 1 采用最小二乘法用三次多项式曲面拟合数字图像。先检测出 边界点，然后计算该点的梯度方向角在梯度方向的变化率，大于某阀值时，则认 为该边界点是角点；m e d i o n ia n dy a s u m o t o 利用卜样条拟合边界的方法来检 测角点，把计算得到的曲率最大值的点检测为角点。这类方法依赖图像目标边缘， 1 2 操作起来很麻烦。 a n ga n db r a d y 【“1 通过计算整幅图像的表面曲率超过某个阈值来判定角点。 先利用高斯滤波器卷积原始图像，然后计算图像的表面曲率。 可计算图像表面曲率 r a 警俩 ( 2 1 0 ) 其中：f 是经过高斯滤波后的灰度图像，a 2 州西2 是沿着边缘切线方向的二阶导数， i v f i 体现了边缘强度。可以通过判断表面曲率r 的大小检测角点，有下式 以 筝删2 s 眨 因此有 ( 斟叫v 棚 眨 s 是表示曲率平方的一个阈值。 利用以下公式来检测角点 r = ( 钎_ s | v 矸胁m 、1 等= 。 眨 l v f l 2 正，r 正| r 是角点响映函数( c r f ) ，正、正分别为定义在边缘和角点强度的两个阈值。就 可以通过设置合适的阈值来检测角点。w a n ga n db r a d y 算法优点是；算法简单， 速度快、实时性强。但如果大量噪声存在时，倾斜边缘上的点易被误判为角点。 小波变换是分析信号和图像的数学工具，其对图像局部特征分析十分有效， 被称为“数学显微镜”。在过去的十年中，基于小波变换的角点检测十分流行。利 用多尺度下的低通和高通滤波，小波变换可阻把一个输入信号分解为平滑的和详 细的两个部分，这样局部的偏差很容易在详细的分解区域中获得。 小波变换的角点检测的大致过程是：首先用边缘检测提取目标边缘，计算目 标轮廓线平滑后的方向角函数o ) 。然后在不同尺度下 = o ，l 2 ，1 ，3 2 ) 对庐( j ) 广东工业大学工学硕士学位论文 进行小波变换，当某一位置在多尺度下都出现模极大值时，把这一点检测为候选 角点，最后根据阈值技术除去伪角点，提取真正的角点。 2 3 基于点特征的角点检测 图像中的角点显著区别于其它点，角点处的灰度和曲率变化都是很显著的， 因此这类方法不依赖于目标的其它局部特征，利用角点本身的灰度或曲率变化特 点直接提取角点，实验证明这类算法速度快、实时性强。 2 3 1拓扑技术的角点检测 b e a u d e t 【2 2 1 较早的提出了这类算子，通过对图像函数，( x ，y ) 进行二阶导数的 泰勒展开，得到h e s s i a n 矩阵h ( x ，y ) = j h c x ，y ，i = i ；i ；：= 厶一； c z a ， 该矩阵具有旋转不变性，可以直接对灰度图像进行操作提取角点，把邻域内最 大值超过阈值的点检测为角点。 b e a u d e t 角点算子在当时是一种较为实用的角点检测技术，但也存在很大缺 点，评价如下： 响应函数的导数为零的点包括两类点：正的局部最大和负的局部最小； 该算法在角点的一边表现为一种标记，在另一边则是相反的标记，在真 正感兴趣的点上并没有给出标记，所以精度差，但它给出了所有方向上 的亮度变化，稳定性好； 在大噪声或边缘强度大时，易在斜边缘出错误地检测到负的局部最小值， 正的局部最大可以很好地检测出角点，但受噪声影响大； 使用单阈值，简单； 当图像大小为吖m ，计算梯度的窗口尺寸为_ ，该算子复杂度为 m 2 f 3 2 + 2 1 。 随后d e r i c h ea i l dg i r a l 甜o n i ”1 改善了这个算法。他们的做法是： 1 首先对两幅图像分别进行一次g a u s s i a i l 卷积( d 取不同值) ，这样得到 两幅不同的模糊图像； 2 使用b e a u d e t 算子分别对两幅图像进行角点检测，这样在第一幅图像 1 4 中检测到的角点，在第二幅图像中，把距离它最近的b e a u d e t 算子所 检测的角点作为它的对应点； 3 将第二步取得的一对角点按位置在源图像中用直线连接，定义这条直 线为角点轴线： 4 在源图像中，沿着角点轴线方向进行l a p l a c i a l l 变换，把其值为零的点 定义为角点。 改善后的算法在处理简单的图像时效果很好，但当图像的角点很密集时，处 理效果并不令人满意，算法较为复杂。 2 3 2 基于灰度变化的角点检测 正如上文指出，h r a v e 首先定义了角点为灰度变化较大的点，他提出了 通过设置一个方形窗口，扫描整幅图像，计算通过窗口中心4 个方向的亮度变化， 求得平均值，当平均值大于某个阈值时就把该点检测为角点。角点反映函数主要 考虑以下三种情况： 1 假如窗口在平坦区域时( 各点灰度值近乎相同) ，所有方向的亮度变化都很 小； 2 假如窗口横跨边缘，那么沿着边缘方向的亮度变化最小，垂直于边缘方向 的亮度变化最大； 3 假如窗口位于角点或孤立点处，所有方向的亮度变化都很大。 其角点反映函数为( 5 5 窗口) ： 43 水平方向c 见吒= 【，( x ，y ) 一厂( z ，y + 1 ) 】2 ( 2 1 5 ) j 0v = 0 34 垂直方向c r e = 【，( 五y ) 一厂o + 1 ，y ) 】2 ( 2 1 6 ) j ；0 l b o 33 对角方向c 峨= 【，( x ，y ) 一，( x + l ，y + 1 ) 】2 ( 2 1 7 ) r ov = 0 33 反对角方向c 兄= ，( x ，y ) 一，o + 1 ，) ，一1 ) 】2 ( 2 1 8 ) j = 0v = o 当以上所有方向的角点响应函数值均超过某个阈值，就判断该中心点为角点。 由于只考虑了四个方向的亮度变化，因此该算法把特殊的边缘点检测为角点，但 广东工业大学工学硕士学位论文 该算子实现简单、快速。 h a r r isa n ds t e p h e n s 【2 4 】算法是在h m o r a v e c 算法基础上通过自相关矩阵来 检测角点，该算法已经被广泛使用。h a r r i s 算法又称p 1 e s s e y 算法。 首先，该算法是基于h m o r a v e c 角点检测算法思想，通过一个体现方向信息 的交替坐标( x ，y ) ( 在m o r a v e c 角点检测算法中可以是( 1 ，o ) ，( 1 ，1 ) ，( o ，1 ) ，( 一1 ，1 ) ) 获得 亮度变化函数e ，有如下公式： e 。= 比，l l 。，+ ，一l ，1 2 ( 2 1 9 ) 其中w 表示矩形窗口，表示像素灰度；将灰度函数在交替坐标源点处进行一 阶泰勒展开，可得： = 孙降+ y 雾州叫2 础2 + z 匈彬 亿z 其中： 爿 b c w w o w 写成二次形： e ( 工，y ) = ( x ，y ) f ( x ，_ y ) 1 其悱陀翻 w 一般选高斯平滑函数，设口，为矩阵m 特征值， 成正比，这样可以形成对矩阵m 旋转不变的描述。 h a r r i sa n ds t e p h e n s 得出以下结论： ( 2 2 1 ) 则其与函数e ( x ，y ) 的主曲率 l 在平坦区域中( 区域的各点灰度值近乎相等) ，口，卢值相对较小； 2 在边缘处，a 值较大，口值近乎为零： 3 在角点处，口，值相对较大。 因此可以仅通过计算口，的值来实现角点检测，角点检测响应函数如下 1 6 o p心卜卜渤 甜一彘甜一钞甜一缸 ，l，、，l 第二章角点检测技术 r = d e t ( m ) 一七( 打讹p ( m ) ) 2 ( 2 2 2 ) 其中： d e t ( 0 = 伐+ p = a + b 加卯( m ) = 筇= 一b c 。 七：l 且兰 竺 ， t l t y t p l j 是由微分模板和高斯卷积函数所决定的变常数，通常为o 0 4 。当r 值为正时， 检测为角点；当r 值为负时，检测为边缘；当月值接近零时，检测为平坦区域。 h a r r i sa n ds t e p h e n s 角点检测算法有以下特点： 该算法执行过程优良，但定位精度差； 由于对伪角点采用常变量七进行抑制，所以算法的稳定性差； 该算法需要确定阈值、高斯函数的方差以及常变量七，复杂、费时； 当图像大小为m m ，计算梯度的窗口尺寸为，高斯滤波的窗口尺 寸为三三，该算子复杂度为m 2 f 2 2 + 3 r + 7 ) i 由于使用了三次高斯滤波，h a r r i sa n ds t e p h e n s 角点检测算法速度很慢， t r a j k o v i ca n dh e d l e y 认为通过排除较低梯度的像素点的办法可以加快速度。 s m i t h 等人提出了一种低层次图像处理小核值相似区的方法( 即s m a l l u n i v a l u es e g m e n ta s s i m “a t i n gn u c l e u s ，简称s u s a n 算法) 。经过大量的实际 应用，该算法对低层次图像处理有较好的