（计算数学专业论文）基于hausdorff距离的轮廓线匹配.pdf

论文题目：基于h a u s d o r f f 距离的轮廓线匹配 学科专业：计算数学 研究生：王文成签名： 指导教师：赵风群教授签名： 戴芳尉教授签名： 摘要 随着科学技术的迅猛发展，形状匹配技术已成为信息处理，特别是图像信息处理领域 中的一项非常重要的技术，并在计算机视觉、资源分析、医学图像配准、气象预报、交通 管理、文字识别等领域得到了广泛的应用。在机器识别事物的过程中，经常需要将己知图 像的轮廓与陌生图像的轮廓全部或者部分在空间上配准，根据已知模式( 通常是人们感兴 趣的对象) 的形状在一幅陌生图像中寻找对应该模式的子现状，这个过程就是形状匹配。 本文主要研究了基于h a u s d o r f f 距离的轮廓线匹配算法。首先介绍形状匹配的概念， 然后阐述如何将该技术应用到轮廓曲线匹配中。针对这一应用的几个主要部分作了讨论和 研究，提出了两个轮廓匹配算法。主要内容包括： 1 研究利用曲率来提取轮廓线上的特征点，以特征点及其两侧的若干点构成特征段， 用特征段对轮廓进行分段描述，进而以h a u s d o r f f 距离为相似度量准则来度量分段轮廓之 间的相似性，获得匹配结果。该算法充分利用轮廓线的几何特征信息，既保证了较好的匹配 精度，又能显著提高算法速度。 2 对拐点和切点的问题，研究通过曲率角和曲率符号分别提取轮廓线上的角点、切 点与拐点，然后以特征点为中心，r 为半径的邻域内的若干点构成特征段，用特征段对轮 廓进行分段描述。该算法特征点提取精度高，有很好的检测和定位能力，并且算法的适应 性强，对拐点和切点频繁出现的轮廓曲线匹配率高达9 8 。 关键词：轮廓匹配：h a u s d o r f f 距离；特征点；曲率；曲率角 迸笠 西安理工大学硕士学位论文 t i t l e ：c o n t o u rm a t c h i n gb a s e do nh a u s d o r f fd i s t a n c e m a j o r ：c o m p u t a t i o n a lm a t h e m a t i c s n a m e ：w e n c h e n gw a n g s u p e r v i s o r ：p r o f f e n g q u nz h a o a s s o c i a t ep r o f f a n gd a i a b s t r a c t s i g n a t u r e ：堕i i 驾 w i t ht h er a p i dd e v e l o p m e n to fs c i e n t i f i ct e c h n i q u e ，s h a p em a t c h i n gb e c o m eav e r yi m p o r t a n t t e c h n i q u ei ni n f o r m a t i o np r o c e s s i n gf i e l d ，e s p e c i a l l yi ni m a g ep r o c e s s i n gf i e l d i th a sb e e n e x t e n s i v e l ya p p l i e di nc o m p u t e rv i s i o n ，r e s o u r c ea n a l y s i s ，m e d i c a li m a g em a t c h i n g , w e a t h e r r e p o r t ，t r a f f i cm a n a g e m e n ta n dc h a r a c t e rr e c o g n i t i o n w h e nt h eo b j e c t sa r er e c o g n i z e db yt h e m a c h i n e ，t h ec o n t o u r so fk n o w ni m a g en e e dt ob em a t c h e dw i t ht h eu n k n o w ni m a g ep a r t l yo r e n t i r e l yi ns p a c e t h ep r o c e s st h a tf i n d i n gt h es u b p r e s e n to ft h em o d et h a ti sk n o w nb a s e do n t h es h a p eo ft h ek n o w nm o d e ( g e n e r a l l yi st h eo b j e c tt h a tp e o p l ef o n do oi st h es h a p em a t c h i n g f i r s t l y , t h ed e f m i t i o no fs h a p em a t c h i n gi si n t r o d u c e d t h e n ，t h i st e c h n i q u ei sa p p l i e d t o c o n t o u rm a t c h i n g t h ed i s c u s s i o na n dr e s e a r c hi sd e v e l o p e da b o u tt h i sa p p l i c a t i o n ，a n dt w o c o n t o u rm a t c h i n ga l g o r i t h m sa r cp r o p o s e d t h er e s e a r c hw o r km a i n l yc o n t a i n s ： t h ef i r s ta l g o r i t h m ，f e a t u r ep o i n t sa r ed e t e c t e db yu s i n gc u r v a t u r e f e a t u r ep o i n t sa n dp o i n t o nb o t l ls i d e so ft h e mm a k eu po ft h ef e a t u r es e g m e n t t h e nf e a t u r es e g m e n ti su s e dt od e s c r i b e t h ec o n t o u rs e g m e n tb ys e g m e n t f i n a l l y , t h er e s u l to fm a t c h i n gi sg a i n e db yd e s c r i b i n gt h e s e g m e n tc o n t o u rb yt h es t r u c t u r es e g m e n t sa n dm e a s u r i n gt h ec o m p a r a b i l i t yo ft h es e g m e n t c o n t o u r st a k i n gt h eh a u s d o r f fd i s t a n c ea st h em e a s u r e m e n to ft h ec o m p a r a b i l i t y f o r g e o m e t r i c a lc h a r a c t e r so ft h ec o n t o u ri t s e l fh a v eb e e nt a k e ng o o da d v a n t a g e ，t h ea l g o r i t h m e n s u r e sp r e f e r a b l em a t c h i n gp r e c i s i o n ，a n da c c e l e r a t e sc o m p u t a t i o n a ls p e e d t h es e c o n da l g o r i t h ma i m sa tp r o b l e mo ft h ei n f l e x i o na n dt a n g e n tp o i n t a n g l ep o i n t ， i n f l e x i o na n dt a n g e n tp o i n to fc o n t o u rl i n ea r es e p a r a t e l yd e t e c t e dt h r o u g hs t u d yo fc u r v a t u r e a n g l ea n dc u r v a t u r es y m b 0 1 t r e a t i n gt h ef e a t u r ep o i n ta sc e n t e ra n dra sr a d i u s ，f e a t u r e s e g m e n ti sm a k ef r o ms e v e r a lf e a t u r ep o i n t si ni t sn e i g l l b o r h o o d t h i sa l g o r i t h mi sv e r yp r e c i s e a td e t e c t i n gt h ef e a t u r ep o i n t s i th a sas t r o n ga b i l i t yo fd e t e c t i o na n do r i e n t a t i o nf e a t u r ep o i n t s i i 摘要 t h em a t c h i n gr a t eo fc o n t o u rl i n ef o rw h i c hi n f l e x i o na n dt a n g e n tp o i n t so c c u rf r e q u e n t l yo a n r e a c h9 8 k e yw o r d s ：c o n t o u rm a t c h i n g ：h a u s d o r f fd i s t a n c e ；f e a t u r ep o i n t ：c u r v a t u r e ；c u r v a t u r ea n g l e r i l l 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢的地 方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所论述的工作和成 果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文作者签名：a 。玺区、口净弓月五己日 学位论文使用授权声明 本人：砬2 ：氩在导师的指导下创作完成毕业论文。本人已通过论文的答辩，并 已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权 西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定提交 印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 为教学和 科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览。 本入学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，适用本授权说明) 论文作者签名：壶翟埝。导师签名： nhn 五7 年岁月j 叠日 f 第一章绪论 1 绪论 1 1 形状匹配的研究意义 随着科学技术的迅猛发展，形状匹配技术已成为信息处理，特别是图像信息处理领域 中的一项非常重要的技术，并在计算机视觉、航空摄影测量、资源分析、医学图像配准、 光学和雷达跟踪、飞行器巡航制导、导弹地形匹配及投射系统的目标制导等领域得到了广 泛的应用，同时也对形状匹配提出了更高和更广泛的要求。它不仅要求将若干多边形拼合 成整体，而且要求使拼合体形成整体协调的画面。因此，开展形状匹配技术的研究具有重 要的理论意义和实用价值。 形状匹配综合利用了计算机图形算法、图像技术、三维图形与图像数据库技术，以及 模式识别与匹配理论等。形状匹配技术实际上是研究一种基于特征分析和内容查找的七巧 板的自动拼合技术，这种技术是通过客观存在的物理碎片的图形、图像及其他属性信息的 采集、分析和建档，建立具有多维信息的七巧板模型的计算机表示。 计算机和计算机科学技术的出现，在理论推导与科学实践方面为形状匹配拼合算法的 发展提供了可能。1 9 9 8 年自动化图像协会关于机器视觉的报告中指出，大约有4 0 的机器 视觉应用中需要用到形状匹配技术。形状匹配技术所涉及的应用领域很广泛，从工业检测 可以推广到导弹的地形和地图匹配、飞机导航、武器投射系统的制导、光学和雷达的图像 模板跟踪、工业流水线的自动监控、工业仪表的自动监控、资源分析，气象预报、医疗诊 断、交通管理、文字识别、图像数据库检索以及景物分析中的变化检测等等。匹配研究涉 及到了许多相关知识领域，图像预处理、图像采样、图像分割、轮廓特征提取、特征存储、 特征查询、匹配方法等，并且将计算机视觉、多维信号处理和数值计算方法等紧密结合在 一起。 在形状匹配检索中，经常需要判断在一组轮廓曲线中是否存在已知模式，如果存在， 进一步判断该模式在物体形状轮廓中的位置，旋转角度等。匹配问题转化成寻找模板到物 体形状的一个变换，使得模板和形状轮廓之间相似性度量最大。在实际应用场合中，影响 形状匹配的主要因素有： ( 1 ) 传感器噪声； ( 2 ) 传感器位置变化或者载物平台抖动： ( 3 ) 目标对象的平移，旋转，交形或者膨胀等； ( 4 ) 成像光照条件的变化以及阴影遮挡等； ( 5 ) 不同传感器成像造成的匹配困难； ( 6 ) 具体应用场合的匹配速度要求。 鉴于上述情况，可以知道：由于多种影响匹配因素的存在，不可能将一种匹配方法一 成不变应用于所有的场合，在设计匹配算法时，要根据其具体的应用场合和要求来制定， 西安理工大学硕士学位论文 所以在把一种算法用于其他应用场合之前，一定要考虑到实际应用环境的改变对算法提出 的新要求。图卜l 是形状匹配系统图。从图中可以看出该系统主要由形状预处理，提取特 征，选择特征点，特征集合和形状匹配算法这五个模块组成。其中形状预处理模块主要是 对待匹配图形做平滑去噪预处理；提取特征模块是通过某种特征提取算法来提取图像上描 述特征的量；选择特征点模块是从已提取的特征量中选取匹配时需要的特征点；特征集合 模块是特征提取后的特征量以某种方式做成集合；形状匹配算法模块是将得到的特征点或 特征集合应用匹配算法进行匹配的过程。整个形状匹配系统中提取特征模块和形状匹配算 法是最关键的模块，对形状匹配过程起着决定性的作用。 图1 - 1 形状匹配系统图 f i g 1 1t h es y s t e mo fs h a p em a t c h i n g 1 2 形状匹配及其研究进展 当观察周围环境时，人们首先注意到的是物体及其周围环境的颜色、纹理、形状和空 间关系等等，形状是物体最基本的有感觉意义的特征之一。在计算机视觉和模式识别中， 形状是对目标范围的二值图像表示，可以看成是目标的轮廓，是用于目标识别的重要特征。 为了节省存储空间、易于特征计算，需要对形状作进一步的表示，这些表示通常可以分为 三类： ( 1 ) 编码方式，如链码、游程码、f r e e m a n 码等； ( 2 ) 简化方式，如样条( b 样条，3 次样条，5 次样条) 、插值、多项式、多边形逼近 和特征点检测等； ( 3 ) 形状的骨架描述方式。 形状描述是通过一些方法生成数值的描述子来描述形状，描述子应在尽可能区别不同 目标的基础上对目标的平移、旋转和尺度变化不敏感。下面列出了一些常用的形状描述子。 ( 1 ) 基于几何特征：紧密度、实心度、偏心率、不规则度等； ( 2 ) 基于统计特征：租糙度、均值、方差等； 第一章绪论 ( 3 ) 变换域特征：矩、f o u r i e r 描述子、小波描述子、形态描述子等； ( 4 ) 仿射不变量：定比等； ( 5 ) 射影不变量：交比等； ( 6 ) 基于几何不变量：曲率、挠率等。 形状匹配就是通过按一定的度量准则来衡量形状间的相似性。在进行形状匹配时必须 处理各种各样的形状变化引起变化的原因主要有： ( 1 ) 成像系统中的噪声： ( 2 ) 成像系统中的不同视角引起的变化； ( 3 ) 部分遮掩，包括自遮掩和互遮掩； ( 4 ) 同类对象间的变化。 这些原因的表述可以概括为计算机视觉的术语：信号中的噪声；各种变换( 相似变换，仿 射变换，射影变换，以及各种高阶变换) ；遮挡( 自遮挡，互遮挡) ；变形( 局部变形和全局 变形) 。显然，图像系统中的噪声可以用信号处理的方法来处理。在传统计算机视觉中已 经获得了许多很好的关于变换( 包括仿射变换、射影变换) 的结果。最近十年中变形模板受 到了很大的关注，在一定情形下获得了很好的结果。人们对有遮掩情况下的形状匹配进行 了大量实验，但由于该问题的本质是病态的，所以在目前的方法框架下，如果没有额外的 先验知识，人们是无法处理很严重的遮掩问题的。 形状匹配可以根据不同标准进行分类，如匹配是基于形状的边界还是内部。形状匹配 的另一种分类是按分析的结果是数字还是非数字形式分类的。第三种分类是基于保留信息 的分类，利用这种方法可以通过形状的描述对其进行重构。根据匹配方法处理形变的能力 将形状匹配方法分为两大类“1 。一类只能处理各种变换引起的形状变化，它们通过搜索在 不同变换下的不变量： ( 1 ) 相似不变量：距离、矩、角度、圆度、f o u r i e r 描述子； ( 2 ) 仿射不变量：定比，弧长、包围面积、改进型f o u r i e r 描述子、曲率、挠率； ( 3 ) 透视不变量：交比及其延伸。 另一类方法可以处理更加复杂的形变，通过寻找目标和模型之间局部特征的对应来使得匹 配误差最小。为了获得最小值，人们使用了很多方法，诸如广义r o u g h 变换强”、动态规 划1 4 5 神经网络地”、变形模板1 8 , 9 1 遗传算法1 ”以及解析方法n 1 ”等。 一个典型的形状匹配分析系统的输入是一个包含目标的形状图。为了能够了解图中的 内容有必要搞清图中目标的位置。目标的形状是一个二值图，表示对象的轮廓，有许多图 像方面的应用都会简化为对形状的分析。形状分析方法分析背景图像中的对象，我们关注 形状分析中的形状表示法及形状描述。形状表示法是对原始图像的非数字表示并且保留图 像中的主要特征。形状描述是对形状的数字表示，要比形状表示更深入一步。一个形状描 述方法总体来说就是给定图像的形状描述向量( 也叫特征向量) 。形状描述的目标是用描述 向量来唯一化形状的特征。形状描述的特征就是对形状的转换，旋转，缩放的操作。使用 西安理工大学硕士学位论文 这三种方法是因为它们不会改变对象的轮廓特征。形状匹配与识别所指的是形状比较的方 法。它主要用于基于模型的对象识别，一组己知的对象与一个未知对象相比较。基于这一 目的的形状描述方案就是确定每一个己知模型和未知形状的描述向量。未知形状通过对形 状描述向量的比较与某个模型形状相匹配。国内外目前正在研究的几个重点是： ( 1 ) 形状匹配中轮廓曲线的描述方法： ( 2 ) 匹配中相似特征对的提取和表述； ( 3 ) 寻找匹配的快速算法； ( 4 ) 匹配策略的优化方法。 形状匹配中相似特征的提取和表述通常是基于各种不变量或局部特性的，其中基于各 种不变量的特征提取在实际实现中比较广泛。 常用的形状表示方法有两类，一类是编码方式，一类是对轮廓的简化表示形式。简化 轮廓就是提取一些重要的有意义的关键点。当今两大最流行的曲线近似方法是多边形近似 和样条近似，另外基于多尺度的特征点提取在最近二十年中得到了密切的关注和研究。 在形状匹配的许多应用中，识别一条曲线和另外的一条曲线是否具有匹配的目的是找 出两条曲线上面相似的部分，称为匹配曲线段。各种匹配方法都是使用对曲线的抽象描述 来进行匹配比较的。这种描述一般是从各种曲线中提取的特征，特征间的相似性被解释为 物体本身之间的相似性。因此，两条曲线的匹配曲线段的识别的准确，主要决定于其特征 的选择。 g o k t u r ku c o l u k 和i s m a i lh a k k it o r o s l u ，提出了识别碎片的轮廓线算法 1 3 1 , 根据 轮廓线的形状匹配进行碎片复原。但是他们的算法仅仅是研究试验，没有真正的应用于实 际工作，而且计算量比较大。 w o l f s o n 等人为了实现碎片复原，提出了基于碎片图像的二维形状匹配技术e 1 4 。e y a l k i s h o n 和t r e v o rh a s t i e 等人就三维盐线方面“”做了深入的研究，利用样条曲线技术来 匹配空间曲线，从而达到识别、拼图的效果。h e l e n ac r i s t i n a 和j o r g es t o l f in ”7 在 二维碎片拼合方面做了很多的工作，提出了把多尺度技术应用于曲面匹配过程中，并且对 于曲线的滤波提出了一种几何特性的滤波方式。 形状匹配问题类似于拼图，拼图在计算机视觉和机器人智能中已经得到了不少的实验 结果。典型的有，h w o l f s o n 和g c b u r d e a 开发的一个标准的拼图游戏1 ，可以自动寻 找匹配的片，甚至控制一个机器手臂来做拼接工作。但是，这些技术都依赖于这些拼图碎 片的特殊形状，例如光滑的轮廓线和明显的拐角，这些在文物碎片中都是几乎没有的。这 项研究工作分了很多的部分，包括了匹配的前期曲线的滤波处理，后期的曲线合并。为了 得到更好的匹配结果，许多人在曲线滤波等其它的方面作了不少的研究。多数人在滤波的 时候都考虑了g a u s s i a n 滤波器，另外还有h e l e n ac r i s t i n a 等提出的几何滤波方式l i g , 还有一些考虑曲率、拐点等的滤波方式。 就目前的研究现状，主要问题集中在轮廓曲线的形状匹配上，在给出的两个轮廓曲线 4 第一章绪论 中识别它们的相似曲线段，即匹配曲线段，从而可以在一组轮廓曲线中找到一个和模板曲 线最匹配的曲线与之合并。 计算机和计算机科学技术的出现，在理论推导与科学实践方面为图形匹配技术提供了 有力的支撑。例如，在考古研究方面，大量出土的人类文化遗产对人类学的研究是十分珍 贵的。但有许多出土文物，包括陶器、瓷器、石器、人及动植物的骨骼和化石等，是破碎 或残缺的，需要考古研究者大量的时间和工作来对这些考古发现进行整理、修复。而有许 多极其珍贵的考古碎片由于数量较大、相互混杂，依靠简单的人工测量和比对无法完成这 样的整理和修复。如何把这些数目较多的碎片拼接修复，至今仍是一个难题。借助于光学 三维摄像技术、测量建模技术及图形图像拼合算法的发展，将有可能在计算机上使该问题 获得解决。另外，对楔形文字、甲骨文字的修复整理保存也可以应用该项技术。又如，硅 藻是一种单细胞的藻类植物，由于它们由硅构成的细胞壁具有极其多样和精美的结构而成 为精微结构研究的热点。另外，由于在湖泊和海洋系统中存有大量的硅藻化石，硅藻也是 现代生态学和进化学研究的重要工具。通过显微照相技术获得硅藻的三维数据，建立网络 环境下的图形图像数据库，对硅藻结构进行修复、空间对称等，对于深入研究、利用、共 享硅藻资源，推动相关学科研究的发展是十分重要的。 具有色彩和纹理等其他属性的三维几何模型相对于单纯的图像信息而言，是对客观世 界更加真实的模拟。三维图形可以在计算机上做任意的旋转、放大或缩小，进行任意视角 和各种比例的观察。而且，目前几何测量的范围和手段以惊人的速度发展，基于光学、声 学、磁学、卫星遥感、三维微观摄像等的测量设备，能够获得大如星球、天体，小如细胞 分子结构的各种三维数据，这为三维图形技术在多个不同领域中的应用提供了必要的数据 来源。因此，以具有色彩和纹理等属性的三维图形为基础开展研究是许多领域技术发展的 必然，而且具有广泛的应用。 1 3 本文的主要研究内容 本论文从形状匹配的现状、轮廓特征点的提取以及通过h a u s d o r f f 距离对轮廓线进行 匹配等几个方面进行了轮廓线匹配技术的研究。研究的主要任务是将图形技术、图像技术 等领域的一些研究成果融合在一起，从二维图形的研究着手，对轮廓匹配问题计算机求解 中的关键问题进行研究，完成二维曲线的检测查询匹配，实现轮廓曲线的匹配。主要内容 有： ( 1 ) 在形状匹配技术及其特征提取方面，着重讨论了形状匹配的概念、各种不同的 几何特征向量。介绍了形状匹配分类，形状表示的分类：编码方式、轮廓线简化方式。简 要描述了各种不同的几何特征描述子，包括矩、f o u r i e r 描述子、小波描述子、形状描述 子，并对形状匹配研究进展进行了综述。 ( 2 ) 研究利用曲率来提取轮廓线上的特征点，以特征点及其两侧的若干点构成特征 段，用特征段对轮廓进行分段描述，进而以h a u s d o r f f 距离为相似度量准则来度量分段轮 西安理工大学硕士学位论文 廓之间的相似性，获得匹配结果。该算法充分利用轮廓线的几何特征信息，既保证了较好的 匹配精度，又能显著提高算法速度。 ( 3 ) 针对切点与拐点的提取问题，提出了一种结合曲率与曲率角对轮廓线匹配算法。 在以轮廓点为中心的支撑区域内定义了曲率角，并根据定义的曲率角及曲率符号，采用模 板匹配技术，提取出候选的轮廓特征点。然后以特征点为中心，矗为半径的邻域内的若干 点构成特征段，用特征段对轮廓进行分段描述。最后计算特征段之间曲率的h a u s d o r f f 距 离，通过h a u s d o r f f 距离来度量分段轮廓之间的相似性。该算法特征点提取精度高，有很 好的检测和定位能力，并且算法的适应性强，对拐点和切点频繁出现的轮廓曲线匹配率高 达9 8 。 6 第二章形状匹配与h a u s d o r f f 距离 2 形状匹配与h a u s d o r f f 距离 2 1 轮廓曲线的表示 ( 1 ) 链码 链码是一种非常常见的形状表示方式，它不能简化形状，但是能有效的表示形状。用 链码表示形状是f r e e m a n 在1 9 6 1 年引入的，并且推广了原来的定义获得了广义链码。 f r e e m a n 还利用链码来抽取关键点从而生成一种相对于平移、旋转、尺度不变的旋转表示 方法，他总结了链码的各种方法，并使用链码来描述边界，找出关键点来形成对边界的描 述，具有对平移、旋转、缩放不变性。他还给出了另一个关于形状重心轮廓的链码方法， 重心轮廓是质心到边界点距离的结构。链码在第二代图像编码中获得了广泛的应用。 r o s e n f e l d 也提出了一系列关于链码的算法。人们利用链码来计算各种不同形状特征，轮 廓平滑和光顺也因此变得简单了。f i s c h l e r 用它来检测关键点m 1 ，u c k e e 甚至利用链码 来识别目标 2 1 | o ( 2 ) 样条 样条在函数插值和曲线逼近方面是非常流行的。样条有最小化曲率的优点，也就是用 最小平均曲率的曲线逼近给定的函数曲线。换句话说，它们近似表示了一个具有最小平均 曲率的曲线的函数。这使得它成为曲线自然表示法中的最好选择。它的缺点是插值问题， 也就是说局部函数发生改变则会影响全部的样条的逼近表示。b 样条逼近则在局部函数发 生改变的时候不影响整体的表示法。b 样条逼近通过参数方程被用于平面曲线的插值法 中。在这里，每个参数方程内插值具有独立性。样条函数在插值问题上的缺点是局部函数 值的修改会影响整个样条表示。b 样条的提出就是为了不将局部函数值的改变传播到其它 区间中去。它也可以用作由参数方程确定的平面曲线间的插值，这样每一条参数方程都可 以独立插值。c o h e n 等人提出了一种基于b 样条的曲线表示和匹配方法1 。基于多项式的 形状简化方法也得到了广泛的应用，很多工作使用隐式方程来表示形状，然后用代数或几 何不变量来识别形状。开始时隐式方程被用来描述三维光滑曲面的仿射不变量。g t a u b i n 开创性的概括了关于如何利用隐多项式提取形状特征的关键技术。当这些特征值和另一条 曲线的特征值相匹配时，就确定了一个“内蕴参考帧”，两条曲线的多项式系数可在这个 参考帧下比较。d a n i e l k e r e n 等人提出了高次隐式方程的概念啪1 ，增强了隐多项式描述复 杂形状的能力。因为正交多项式不能提供平移、旋转、尺度不变量，所以k u 等人提出了 广义正交多项式”1 ，获得了相似变换不变量。实际上用其他函数拟合曲线的方法还有很 多，插值既可以简化形状，也可以增加形状的边缘点数，从而达到调整数据的目的。 ( 3 ) 多边形逼近 多边形逼近是用多边形线段来近似形状边缘，是以最小误差、最小多边形周长、最小 多边形内部面积和平方积分误差或最小多边形外部面积作为近似准则。这些误差度量中 7 西安理工大学硕士学位论文 最常用的是最小误差和平方积分误差。多边形逼近中最常用的是p a v l i d i s 提出的分裂和 合并法“1 。在这个方法中，曲线分裂由几个线段来表示直到误差达到可以接受的程度。 同时分裂的线段又有可能融合，如果融合后的线段同原始曲线的误差在允许的最大误差范 围内，线段即融合。 ( 4 ) 基于尺度空间的特征点提取技术 基于尺度空间的特征点提取方法是一种流行的形状简化方法。最常用的尺度空间有： 高斯尺度空间、小波尺度空间、形态尺度空间。w i t k i n 提出的基于g u a s s i a n 尺度空间表 示突出目标特征的方法协1 ，通过跟踪不同尺度下特征点的位置而给出形状的简化形式， 依然存在于简化表示形式中的特征点能够用来描述目标的显著特征。b a b a u d 等人证明了 6 a u s s i a n 核是唯一的线性核”1 ，具有非常良好的保留本征特征点的特性，当尺度增加时， 即滤波器带宽增加时，那些本征特征点依然存在。曲率函数在尺度空间中的图像被用作形 状多层描述子，它具有平移、旋转、伸缩不变性。多尺度的概念在形态学中也提出过。 ( 5 ) 字符文法技术 结构化描述可以被看成是图表或者类似的用形式语言可以明确表达的形式，它们试图 仿效h v s 的结构和层次特征。字符文法技术的优点就是它的形式语言的理论，是该技术的 基础，是一个具有良好前景的领域。主要的缺点是形状必须被编码然后输入到分析程序当 中去。很显然，一个图像的简单分解都会分成不同种类的线，弧和角度。所获得的边界特 征被表示成一个字符串s 一，j ：，字符串的元素墨可以由不同的实体来代表，比如 链码元素，近似多边形的边或者一个弧。然后根据语法来解析这个字符串，从而对对象的 形状进行识别。除了确定的语法外，还给出了随机的语法。 形式语言的理论是由n o 锄c h o m s k y 建立的，已经被应用于许多领域，例如编译器的 设计、自动控制理论、计算机语言，模式识别和图像处理。字母表是一系列的字母。词可 以构成句子。所谓的语言就是由这些词构成的句子组成的。形式语言使用语法来定义。语 法是一系列的文法规则，描述用一个给定的词汇表怎样生成句子。语法g 是一个等式 g 一( z ，p ，$ ，n 表示非终极符集合，表示终极符集合，p 是生成式集合，s e n 是 起始符。语言z ( g ) 是由语法g 所生成句子的集合，句子有下列特性： ( a ) 每个句子只能由终极符构成。 ( b ) 每一个句子都能按着一定的顺序由s 开始通过生成式p 来形成。 形式语言的语法分成4 类。0 型语法是生成式中形式不严格的文法。l 型是上下文有 关文法。2 型是上下文无关文法，3 型是规则文法。上下文无关文法和规则文法是应用比 较多的。 ( 6 ) 边界分解 边界分解是将形状边界分解成曲线段。h l i ua n dm s r i n a t h ”1 开发了一个利用轮廓 匹配对形状进行分类的程序。程序的输入是一个对象的形状。s o b e l 边缘检测算子被用于 计算边界的方向梯度以及切线角。曲线匹配由两步构成。第一步比较两个形状的独立的线 8 $ - - 章形状匹配与h a u s d o r f f 距离 段。第二步，一组曲线进行比较，如果少于三个连续的曲线可以匹配，则这组曲线被视为 无效。后一步是来衡量两个形状的差距。这需要使用3 4 斜面距离转换。1 来进行，并且 用它来近似欧几里得距离转换的效果非常好。第一个边界使用3 4 斜面距离转换来计算： 将第二个边界叠加到第一个边界的距离转换上，并计算出平均距离值。 2 2 轮廓特征点 2 2 1 特征点的分类 在计算机视觉中，轮廓特征点的提取有着十分重要的意义。轮廓特征点是最基本的表 征目标形状的特征基元，根据它可以将平面曲线分割成有意义和紧凑的形式，以利于高层 视觉处理( 模式识别、形状匹配、尺寸检测等) 。 轮廓特征点包括角点、切点和拐点。 ( 1 ) 角点是目标轮廓线上曲率超过一定阈值的局部极大值点； ( 2 ) 切点是圆弧和直线的平滑过渡点，如图2 - 1 ； ( 3 ) 拐点是凹圆弧和凸圆弧的平滑过渡点，如图2 - 2 。 图2 - 1 切点 f i g 2 - 1t a n g e n tp o i n t so f c o n t o u x 图2 之拐点 f i g 2 - 2i n f l e c t i o np o i n t so f c o n t o u r 由于角点、切点和拐点对目标形状起着决定作用，一旦找到了目标的这些轮廓特征点也就 大致掌握了目标的形状。因此说在形状表征、形状分析、图像匹配及目标识别中，角点、 9 西安理工大学硕士学位论文 切点及拐点是最基本的表征目标形状的特征基元。 2 2 2 特征点的提取 轮廓特征点提取方法都是利用相邻的一组轮廓点来计算轮廓线上各点的曲率或两近 似直线段的夹角( 将轮廓点近似看作是两直线段的交点) 来判定轮廓特征点的，角点的曲 率较大，比较容易提取。而对于切点和拐点，它们的曲率较小，较难提取。以角点为主的 这种提取方法的优点是运算量小，但最大缺点是受图像数字化及噪声干扰极大( 尤其对于 切点和拐点的提取) ，因此在提取前需要进行预处理。 轮廓特征点的提取还可以通过轮廓线支撑区域( 相邻的一组轮廓点构成的区域) 内中 心点两侧轮廓点的几何中心值计算轮廓线的曲率角及曲率符号，从而提取轮廓特征点，这 种方法的优点有抗干扰性好、运算量小、定位准。 2 3 基于各种不变量的形状匹配方法 在几何学和拓扑理论中，给出了很多关于各种变换的结果，据此人们提出了许多处理 各种变换的不变量。 ( 1 ) 基于全局性几何特征的形状匹配方法 在经典的几何理论中，面积、周长、长轴、短轴、主轴方向、凹凸面积、紧密度、实 心度、偏心率这些特征得到了广泛的应用。在此简单介绍紧密度、实心度、偏心率。紧密 度是在一定程度上描述区域紧凑型的全局性形状测度，当形状为圆时，紧密度为最小值1 。 它是一个旋转、尺度、平移不变量，又是一个非矢量的数值。区域形状的偏心率定义为它 的主轴和次轴的比，它区分不同宽度目标的能力比较强，长而窄的物体和短而宽的物体偏 心率差别很大。当形状有一个或多个明显的凸凹时，实心度就是一个非常有用的特征，可 以刻划一个区域的凸凹性。任意集合4 的凸壳日就是包含集合4 的最小凸包。实心度定 义为在日同时也在集合4 中像素的数目的比例。实心的目标和空心的目标在实心度上差 别很 大。 ( 2 ) 基于变换域特征的形状匹配方法 人们喜欢将信号转换到变换域，分解成不同的频率或基来分析特征。作为最经典的变 换方法，有各种不同的矩和f o u r i e r 描述子，小波描述子、形态描述子在过去的二十年中 得到了广泛的研究。 ( a ) 矩 矩在模式识别、目标分类中得到了广泛的应用。某种条件下矩不依赖形状的位置、方 向、以及比例大小，但是这类矩不能恢复图像。复数矩是一种获得矩不变量的简单而又直 接的方法。矩方法是一种简练的数学表示、计算很简单；缺点是要建立起高阶矩和形状特 1 0 第二章形状匹配与h a u s d o r f f 距离 征间的联系是困难的，另外它不能检测形状的局部特征。另一种转换是采用形状的傅立叶 变换。其优点是保持了不依赖形状的位置、方向、以及比例大小的性质，缺点也是无法检 测形状的局部特征。 ( b ) f o u r i e r 描述子 f o u r i e r 描述子是经典的形状描述方法。在一定条件下，它具有位移、旋转、大小、 起点等不变性质。当进行傅立叶变换以后，形状的局部信息都被分配到了所有的系数当中， 已经不存在于频域当中了。但是切线角与弧长的方法会受到噪声的干扰，因为它很难确定 切线角的噪声范围。对边界函数进行傅立叶变换，变换结果的系数用来描述形状。由于对 弧长进行了标准化，所以形状的描述对于比例的变化具有不变性。形状描述对于位置的变 化也具有不变性。物体形状的旋转只能引起傅立叶变换中相位的变化，然而傅立叶变换的 系数的数量级可以保证这种方法的旋转不变性。用f o u r i e r 描述子可以对2 - d 曲线进行编 码、重建、或者分类。它的主要优点是易于实现，并且建立在f o u r i e r 分析的成熟理论之 上；缺点是f o u r i e r 变换不提供局部形状信息。 ( c ) 小波描述子 在很多计算机视觉应用中，为了改善形状准确率和提高对噪声的鲁棒性经常采用多分 辨率分析方法。形状的小波表示方式在粗尺度给出形状的全局信息，在细尺度上给出局部 信息。由于小波变换提供了多分辨率表示，因此匹配或识别可以根据输入图像或者目标而 灵活调整。小波变换的最大缺点就是依赖于目标曲线的起始点，也就是说，同一目标的两 条不同采样曲线的小波表示可能因为起始点的不同而有很大差异。c h u a n g 和k u o 假定输入 图像已经经过校正啪。l i 和k u o 通过简单的最小化曲线幅值函数的质心来获得起始点“”。 t i e n g 和b o l e s 使用小波系数的零交叉点来匹配模型和未知目标哪! 。他们使用冗余小波变 换，即非十进小波变换来克服对起始点的依赖。由于非十进小波表示方法需要的计算量很 大，系数的数目也非常大，所以用非十进小波进行形状匹配非常慢。在文献 3 3 1 中将形 状先转换到极坐标中，作f o u r i e r 变换抽取f o u r i e r 系数，然后对f o u r i e r 系数的幅值抽取 小波系数作为特征用于分类。文献【3 4 】介绍了一种判断起始点的方法，从而保证了小波 变换不受起点约束。 ( d ) 形态描绘子 最近十年，基于形态学的形状描述方法得到了广泛的研究。m a r a g o s 首先提出了模式 谱的概念。s h i h 和p u 拓展了g o u t s i a s 和s c h o n f e l d 的工作，并且提出了另外一种称为g 一谱 的谱变换，这种方法是从形态协方差的概念中得出来的。l o u 等使用几何相关函数 ( 6 e o m e n t r i c a lc o r r e l a t i o nf u n c t i o n ) 表示二维形状。几何相关函数是基于形态协方差 的。文献 3 5 】也使用g c f 进行形状描述和匹配。这种表示方法是旋转平移不变的，加上 预处理还可以获得尺度不变性。l o n c a r i c 和d h a w a n 开发了一种称为形态特征变换 ( m o r p h o l o g i c a ls i g n a t u r e t r a n s f o r m ) 的形状描述方法。形态特征变换方法主要使用基于 结构基元的多分辨率形态图像处理方法。这个方法试图把多分辨率图像处理和数学形态学 西安理工大学硕士学位论文 的优势结合。形态特征交换表示方法把复杂的形状分解为多个简单的特征形状，然后提取 多个分解后的形状的特征，而不是原始形状的特征。分解后的形状之所以被称为特征形状， 是因为在特征分解过程中，这些特征形状保留了原始形状的信息。l o n c a r i c 和d h a w a n 开发 了一种基于形态特征变换的形状匹配算法珏1 ，并使用遗传算法来挑选一个次优的结构基 元来计算m s t 的形状描绘子。对于来自同一类的形状，这个被选中的次优结构基元可以给 出很好的分类结果。 ( 3 ) 基于局部特性的形状匹配方法 前面介绍的基于全局特征进行匹配的方法，但是如果形状发生形变或者受到遮掩，那 么全局特征就变得不可靠了。为了处理更加广泛的形变问题和遮掩问题，学者们提出了很 多基于形状局部特征的形状匹配算法。这类方法主要是通过搜索最优点对应或特征对应来 判断形状是否匹配。它们的原始雏形就是广义h o u g h 变换。传统的动态规划等优化算法得 到了广泛的应用。现代优化算法如神经网络、遗传算法的应用，使得许多遮挡问题和变形 问题得到了解决。当今解决形变问题最流行的方法是变形模板。实际上形状也可看作一维 随机信号，所以在语音识别中得到许多成功的算法也被广泛地应用到了形状匹配中，如动 态规划、隐m a r k o v 模型、自回归模型等。形状的凹凸结构也是决定形状的视觉特征，受 到了广泛的关注。 ( a ) 广义r o u g h 变换 r o u g h 首先提出了称为r o u g h 交换的区域外形边界变换的形状描述方法。r o u g h 变换 的目标是寻找一种从区域边界( 空间域) 到参数空间的变换，用大多数边界点所满足的对应 参数来描述这个区域的边界。在复杂场景且外点很多的情况下，这种方法对尺度变化处理 得不太好。 ( b ) 基于神经网络的匹配方法 神经网络是近年发展起来的优化方法，并被广泛的应用到有遮掩形状的匹配问题中， 其中h o p f i e l d 神经网络是形状匹配中最常用的。预处理以后的形状是由一组关键点表示， 目标的每个点和模型的每个点结成点对，每个点对由一个神经元表示，那么每个目标点只 能和一个模型点匹配就是行约束，每个模型点只能与一个目标点匹配就是列约束，整体