（应用数学专业论文）二维形状的描述和识别的研究.pdf

浙江走学硕士学位论文 摘要 在过去的几十年中，模式识别的研究发展很快。模式识别主要涉及由物质和 精神的过程所得的度量的描述和分析。为了提供有力而有效的模式描述，通常需 要用预处理消除噪声和多余信息，然后提取一组数值的或非数字的特征度量，通 过这些度量之间的关系来表示模式。在这个表示的基础上完成对特定目标的模式 分析( 分类或描述) 。本文研究了识别中的一个重要分支二维形状表示和识 别。 形状识别己深入地应用到字符识别，目标检测，医学诊断，机器人，勘察， 制图和建筑设计等方面。例如，在机器人中，影像目标的外形可以用适当的二维 形状表示来模式化，于是，这些目标的例子可通过它们在具体影像中的实际外形 弓由模式识别决定的预期的外形作比较进行识别和定量检测。 现实中形状有着多种变形，如尺度的放缩，方向的旋转等变化，而且形状的 边界隐藏着不确定的噪声，使得形状识别变得困难，很多传统的方法存在着各种 不足，不能满足各种识别问题的需要。本文主要对形状边界采用了连续描述和离 散捕述，并在这两种描述法的基础上提出了形状识别方法，取得了很好的识别效 果。 任何一种二维形状都对应着极坐标系下的”一组平而连续的曲线，这些曲线在 一定韵关系下组成了一个曲线等价类。形状的连续描述是通过曲线等价类来表示 形状，这种形状的表示方法具有平移、旋转、缩放不变的特性。而且在这表示 法的基础上定义了多尺度一f 曲线等价类之间的距离来反映形状间的相似度，根据 这一一距离的大小来判断两个形状是否相似。这种形状识别的方法对于边界的扰动 不敏感。 本文中的曲线离散表示是引入了一种有效的曲线编码和描述方法 曲线树来描述形状。曲线树中的树叶是有向相对高度值。任何一种曲线都与 一个曲线树一一对应，从树的根部开始，取其前几层得到的树，都是对该曲 线的粗略的描述，而且随着层数的增加，刻画曲线的精度就越高。这种方法 最大的个优点是它不随曲线平移、拉伸和旋转而变化。在这种曲线描述的 浙江太学硕士学位论文 基础上，我们进一步定义了两曲线的距离，用来衡量曲线问的相似程度，在 实际的应用。 i 形状识别效果很好。 关键词： 形状识别；形状描述；极坐标：曲线等价类；平行线截割法；形 状的距离；曲线描述：曲线树；二叉树：有向相对高度；曲线距离 i i 浙江大学硕士学住论丈 a b s t r a c t t h ei n t e r e s t si np a t t e r nr e c o g n i t i o nh a sb e e ni n c r e a s e dd u r i n gp a s tt e n sy e a r s p a t t e r nr e c o g n i t i o nm a i n l yr e f e r st ot h ed e s c r i p t i o na n da n a l y s i so fm a t e r i a la n ds p i r i t w ea l w a y sh a v et od oi m a g ep r e p r o c e s s i n go f s i l e n c i n go f n o i s e ，a n dt h e ne x t r a c tas e t o ff i g u r e so rn o n - f i g u r e st od e s c r i b et h es u b j e c tw ew a n tt o p r o c e s s b a s e do nt h e d e s c r i p t i o nw ea n a l y s i st h ev e r ys u b j e c t i nt h et h e s i sw ed e a lw i t ht h ei m p o r t a n t b r a n c ho f p a t t e r nr e c o g n i t i o n t h ed e s c r i p t i o na n dr e c o g n i t i o no f 2 d s h a p e s h a p er e c o g n i t i o ne x t e n d st h e i ra p p l i c a t i o ni n t oc h a r a c t e rr e c o g n i t i o n ，t a r g e t t r a c k ，m e d i c a ld i a g n o s i s ，i n t e l l i g e n tr o b o t ，e x p l o r a t i o n ，m a p p i n ga n da r c h i t e c t u r a l d e s i g n s u c ha si ni n t e l l i g e n tr o b o t ，t h ep r o f i l eo fo b j e c tc o u l db ed e s c r i b i n gi n2 d s h a p e a n dt h eo b j e c tc o u l db er e c o g n i z e da n dq u a n t i f i a b l yt e s t e db yc o m p a r i n gt h e r e a lp r o f i l ea n dt h ee x p e c t e ds h a p ei np a r e m r e c o g n i t i o n i nr e a lw o r l d ，s h a p eh a sm a n yd e f o r m a t i o n s ，s u c ha sz o o m ，r o t a t i o n ，s h e a ra n ds o o n a n dt h e r ei sag r e a td e a lo f u n c e r t a i nn o i s e si nt h eb o u n d a r yo f s h a p e ，w h i c hm a k e t h es h a p er e c o g n i t i o ne v e nm o r ed i f f i c u l t t r a d i t i o n a lm e t h o df o rs h a p er e c o g n i t i o n a l w a y sc a r l ts a t i s f yv a r i o u sr e c o g n i t i o np r o b l e m sw e l l i nt h i st h e s i s ，w ed e s c r i b et h e b o u n d a r yo fs h a p eb yc o n t i n u i t ya n dn o n - c o n t i n u i t ym e t h o d ，a n dp r o p o s es h a p e r e c o g n i t i o nm e t h o d sb a s e do nt h ed e s c r i p t o r s t h ee x p e r i m e n tr e s u l t ss h o wt h e m e t h o d sa r ee f f e c t i v e s h a p e so ft h es a m ek i n dc o r r e s p o n dt oas e to fc o n t i n u o u sc u r v e s ，t h ec u r v e s f o r mc u r v ee q u i v a l e n c ec l a s s e so na ne q u i v a l e n c er e l a t i o n i nt h i st h e s i s ，w eu s ec u r v e e q u i v a l e n c ec l a s s e st od e s c r i b es h a p e s s h a p e so fd i f f e r e n tk i n d sa r em a p p e dt oc u r v e e q u i v a l e n c ec l a s s e s t h i ss h a p ed e s c r i p t o ri si n v a r i a n tt ot r a n s l a t i o n ，s c a l e ，a n d r o t a t i o n b a s e do nt h i sd e s c r i p t o r ，w ed e f i n ead i s t a n c eb e t w e e nc u r v ee q u i v a l e n c e c l a s s e sa n dt h ed i s t a n c er e f l e c t st h es i m i l a r i t yb e t w e e nt h es h a p e s ，b yt h i sd i s t a n c ew e c a nf i g u r eo u tw h e t h e rt h e ya r es i m i l a r t h i sm e t h o df o r s h a p er e c o g n i t i o nh a s i m m u n i t yt on o i s ea n ds m a l lp e r t u r b a t i o n s an o v e la p p r o a c h ，c u r v et r e e ，i s p r o p o s e df o rc u r v er e p r e s e n t a t i o na n d 1 1 1 浙江大学硕士学位论疋 e n c o d i n g b i n a r y t r e e sc o m p o s e do fd i r e c t e dr e l a t i v eh e i g h t a r ea d o p t e dt o d e s c r i b ec u r v e s a n yc u r v ec o r r e s p o n d st oac u r v et r e e w em a y t a k et h ef i r s tn l e v e l so ft h ec u r v et r e e ，a n dt h e yc o m p o s eab i n a r yt r e er o u g h l yd e s c r i b i n gt h e c u r v e t h em o r el e v e l sw eg e t ，t h ef i n e ri td e s c r i b e st h ec u r v e - t h er e p r e s e n t a t i o n i si n v a r i a n tt or o t a t i o n ，s c a l i n g ，a n dt r a n s l a t i o n b a s e do nt h i sd e s c r i p t o r , c u r v e d i s t a n c ei sd e f i n e dt ow e i g ht h es i m i l a r i t yb e t w e e n c u r v e s k e yw o r d s ：s h a p er e c o g n i t i o n ，s h a p ed e s c r i p t o r , p o l a r c o o r d i n a t e s ，c u r v e e q u i v a l e n c ec l a s s e s ，t h em e t h o do fp a r a l l e lc u t t i n g ，d i s t a n c e o fs h a p e s ，c u r v e r e p r e s e n t a t i o n ，c u r v et r e e ，b i n a r yt r e e ，d i r e c t e dr e l a t i v eh e i g h t ，c u r v ed i s t a n c e 浙江大学硕士学位论支 第一章绪论 图像识别亦称模式识别，它是随着计算机的发展而兴起的一门新的学科。在 各种图像中，最重要的是通过人们视觉摄取的客观世界的灰度、彩色、形状、纹 理及空间等信息，并经过大脑高度综合加工而形成的各种图像形式，即视觉图像。 例如人看到个景物，能回答它是什么，看到个数字，能说出它是几，这是人 对物体的识别。随着计算机科学的发展，现在完全有可能通过计算机控制系统模 拟人的能力。本文选定图像识别中的个研究方向基于对象( 区域) 形状的识 别作为研究目标，即形状识别。 形状识别是计算机视觉和模式识别的一个基本问题，它被应用到很多领域， 如目标识别、基于内容的图像检索、文字识别、医疗诊断等。在过去的几十年中， 人们研究和开发了很多形状识别算法，每种算法各有其优缺点，本章介绍形状识 别的基本概念和一些代表性的形状描述和识别方法。 1 1 形状识别的基本概念 当观察周围环境时，人们首先注意到的是物体及周围环境的颜色、纹理、形 状和空间关系等等，形状是物体最基本的有感觉意义的特征之一。在计算机视觉 和模式识别【_ j ，形状是对目标范围的二值图像表示，可以看成是目标的轮廓，它 是用于目标识别的重要特征，为了节省存储空间、易于特征计算，需要对形状作 进一步的表示，即形状描述。形状描述是通过一些方法生成数值的描述子来描述 形状，描述子应在尽可能区别不同目标的基础上对目标的平移、旋转和尺度变化 不敏感。下面列出了一些常用的形状描述子。 【) 基于几何特征：紧密度、实心度、偏心率、不规则度等； 2 ) 基于统计特征：粗糙度、均值、方差等； 3 ) 变换域特征：矩、f o u r i e r 描述子、小波描述子、形态描述子等； 4 ) 仿射不变量：简比等； 5 ) 射影不变量：交比等。 实际卜_ 存在许多途径可以描述形状，而到底选用哪一一种则往往取决于形状参 浙江大学硕士学位论支 数的应用。在识别应用的问题中，形状描述只要包含足以区分可能遇到的类似形 状的那些信息就可以了，而不必要由这些形状参数去恢复原目标：当目标尺寸、 位置和方向发生变化时，描述目标的形状参数应当保持不变，这样才能有利于形 状识别中对不同尺度，方向的形状正确定位。 形状识别就是通过按一定的度量准则来衡量形状问的相似性。在进行形状识 别时必须处理各种各样的形状变换。m u m f o r d 2 概括了一些引起变化的原凼： 1 ) 成像系统中的噪声； 2 ) 成像系统中的不同视角引起的变化； 3 ) 部分遮掩，包括自遮掩和互遮掩： 4 ) 一个目标各部分的连续运动( 如：人的四肢) ； 5 ) “软”物体所具有的复杂的运动( 如：衣服) ： 6 ) 同类对象间的变化。 这些原因的表述可以概括为计算机视觉的术语：信号中的噪声；各种变换( 相似 变换，仿射变换，射影变换，以及各种高阶变换) ：遮挡( 自遮挡，互遮挡) ；变 形( 局部变形和全局变形) 。显然，图像系统中的噪声可以用信号处理的方法来 处理。在传统计算机视觉中已经获得了许多很好的关于变换( 包括仿射变换、射 影变换) 的结果。最近十年中变形模板受到了很大的关注，在1 定情形下获得了 很大良好的结果。人们对有遮掩情况下的形状识别进行了大量实验，但由于该问 题的实质是病态的，所以在目前的方法框架下，如果没有额外的先验知识，人们 是无法处理很严重的遮掩问题的。 形状识别可以根据不同标准进行分类，如：形状是基于形状的边界还是内部， 这里根据匹配方法处理形变的能力将形状匹配方法分为两大类。一类只能处理各 种变换引起的形状变化，它们通过搜索在不同变换下的不变量： 1 ) 相似不变量距离、矩、角度、圆度、f o u r i e r 描述子； 2 ) 仿射不变量简比、弧长、包围面积、改进型f o u r i e r 描述子； 3 ) 透视不变量交比及其延伸。 另一类方法可以处理更加复杂的形变，它们通过寻找目标和模型之间局部特 征的对应来使误差最小，为了获得最小值，人们使用了很多方法，诸如广义h o u g h 变换、动态规划、神经网络、变形模板、遗传算法以及解析方法等等。 浙江太学硕士学位论文 一般情况下，在选取形状参数时应该注意到图像中的物体有如下特点：( a ) 其 尺寸大小0 i 是统一的；( b ) 其方向刁i 是一致的；( c ) 在图像巾的相对位置是不一 致的。因此，特征参数的值应该不受或很少受物体的尺寸、方向和相对位置这三 个因素的影响，这样才能较好地进行识别。事实上，只要某个特征参数对其中任 何一个因素能保持恒定不变，就应该是可选形状参数。 针对实际问题我们需要选取“有效”的识别方法，这里“有效”不仅是指形 状识别的准确度，也指我们所能接受的识别速度。由于它的应用对象是比较大的 图像数据库，从中识别对应的形状，识别算法不但要求较高的精确度，而日必须 保证一定的速度，以满足实际的需要。有些时候，甚至需要在精度和速度之问作 一个折衷。 1 2 形状描述与识别的状况 识别通常是图像分析和计算机视觉的最终目标。随着英特网应用以及多媒体 技术的飞速发展，识别的任务也日益繁重。在很多图像识别中，颜色，纹理，甚 至是图像内灰度的变化特点等都列为识别的重要依据。形状识别是最常见也是最 具主导地位的图像识别的一个分支。 几十年来很多形状表示模型被提出，在图像识别的应用中取得了很好的成 果。但这些识别对于形状的外表有着特殊的要求，如对在户外运动的汽车，人物 的识别却显得力不从心了。最主要的困难在于这些物体的形状的多变性，如从不 同角度观察这些事物，它们的外观不同。本文我们主要研究形状识别是针对平面 的形状，只涉及到形状的旋转，平移和比例变换。 目前形状识别可以分为三类：利用形状不变量；形状分解：形状对准匹配f 3 】。 采用不变量识别形状就是利用形状中不随刚性变化和比例变换而改变的特 征，是形状识别的丰流方法。如傅立叶描述子 4 ，5 】，形状矩( 5 ，6 等，这些量 关于二维空问变换不变性。最近很多新的几何不变量的研究正在开展 7 。尽管 在很多领域中这种不变量的识别比较成功【8 ，但这种识别方法也存在着一些局 限，如对于一个给定的形状，如何寻找它的不变量，即使不变量找到，如何确定 它们的权重( 即对形状识别的重要程度) ，其次是这些不变量对于形状边界的扰 动，形状部分遮挡很敏感 1 0 1 ，最后是许多不变量与形状的类型之制的对应关系 浙江大学硕士学位论丈 并非一定是一一对应，很多时候会出现多对一的情形，即不同类型的形状对应的 不变量相同。 c o s m i ng r i g o r e r s c u 等曾用距离集表示形状，并进而识别，其实这也是利用 不变量识别形状的一种。它首先利用形状边界点的空间特征表示形状，形成相应 的距离集，在构造合适的距离集之间的距离来反映不同形状间的差异，从而得到 新颖的形状识别方法。这种基于距离集的形状识别对于复杂背景中的形状，甚至 是部分被遮挡的形状也有效的。 e n d e ro z c a n 在文献【l 】中采用不变特征，形状边界的线段长度，线段问的角 度表示形状，进而在此表示法的基础上采用遗传算法进行形状的匹配，识别。但 这种方法存在明显的缺陷，对于一般比较复杂的形状( 即边界不是由线段组成的 形状) 如何提取边界的线段，以及边界的线段提取受形状边界扰动等非常不稳定， 都可能给接下去的识别带来困难。 c s s 2 4 1 已广泛地应用于二维形状的表示。这种表示法对于形状平移，旋转， 比例缩放以及边界扰动都具有很好的鲁棒性。这种方法中形状的表示采用形状边 界最大曲率尺度的空间表示形状的边界，基于这种表示法的形状识别在实际应 用中具有很好的效果。 j z h a n g 1 5 】提出将形状以及它所有的简单变换后的形状表示成高维空间中 的点，从而得到形状空间，形状的识别通过计算两形状在形状空间中的测地距离 来实现。这种方法在二维形状识别中效果很好，而且它对于简单变换以及形状边 界的噪声和形状部分遮挡具有不变性。 形状分解方法中心思想就是将形状分解成一些简单基本的小形状【3 ，11 1 3 ， 如矩形，三角形，圆等，道过分解将形状表示成图，图的结点对应分解后的小形 状。这种方法可以表示复杂的形状并对其识别，而且由分解的小形状的空间关系 可以构造不变量。这种方法同样存在着欠缺，如在相对粗略的分解水平下，一些 不同的简单形状有相同的分解，而精确的分解会使对应的图非常复杂。而且这种 形状分解对自然界的物体来说往往不稳定，不唯一。 p e d r o 在文献 2 3 1 中提出了用三角形表示二维形状。这种表示法与形状的中轴 有密切的联系，它提供了平而形状分解成简单图形的方法。所有的三角形构成形 状，而且这些三角形形成了树结构，从而将形状的识别转换成三角形构成的树之 浙江太学硕士学住论支 间的匹配。这是一种很典型的形状分解法进行形状表示和匹配的方法。 形状对准匹配 3 】【14 的方法可能会涉及最优化理论而且耗时较长，因为它首 先是对形状进行图像处理，如旋转，放缩等。这种方法的优点是它利用了整个形 状的信息，而不是像上述两种方法采用局部或粗略的形状表示，所以相对而言可 能带来更好的识别效果。 h t ( h o u g ht r a n s f o r m ) 2 0 ，g h t ( g e n e r a l i z e dh o u g ht r a n s f o r m ) 2 l 】对于那些刚 性的没有太大变化的形状的识别效果非常好，它们不仅计算效率高，而且对于一 些边界部分丢失或变形的形状也具有良好的效果，这些方法主要应用于工业物体 的识别。但对于非刚性的形状，边界有很多扰动的形状，如自然界中的树叶等等， 无论选取哪个为模型形状，上述方法的效果都非常差，首要原因是h o u g h 的成 功基于待识别形状与模型形状问有足够的点完全吻合。针对上述出现的问题， a s h o ks a m a l 等提出g h t ( g e n e r a l i z e dh o u g ht r a n s f o r m ) 2 2 ，它是上述方法的扩 展，采用内边缘，外边缘同时表示形状，用落在线段上所有的点更新参数空间中 的值，g h t 在自然物形状识别中具有很好的鲁棒性，而且识别速度也相当快。 z h o n gx u e 【1 9 】是利用模糊数学的方法将形状对准比较，事实上是对m a r q u e 的方法的进一步拓展。在这个算法中点对应的模糊程度用来描述两点问的相关程 度，提供了一种有效的形状对准匹配的方法。 近几年了又出现很多新的形状识别方法。其实这当中的很多方法都介于上述 几种方法中，在实际问题中我们要根据实际情况选择合适的方法，甚至对已有的 方法进行改进，以便于更好地完成任务。 1 3 本文的主要成果 平面形状识别是最基本的模式识别问题，然而这个问题至今仍然未能很好地 解决。其困难在于形状的描述难满足形状识别的需要，而且对于给出两条曲线的 形状差别难以给出定量描述。本文对形状边晃分别采用连续描述和离散描述的方 法，并在这两种描述方法的摹础上模拟人的视觉特征给出了形状距离的定义判断 形状的相似度。 第一种方法是利用形状边界点的极半径的变化是否一致来判断它们是否 属于j 司一类型。一种二维形状都对应着极坐标系下的一组平面连续的曲线，这些 浙江大学硕士学位论丈 曲线在定的关系下组成了一个曲线等价类，我们用曲线等价类来表示形状，这 种形状的表示方法具有平移、旋转、缩放不变的特性。并且在这一表示法的基础 上定义了多尺度下曲线等价类之间的距离来反映形状的相似度，根据这一距离值 来判断两个形状是否相似。这种形状识别的方法对边界的扰动不敏感。 第二种方法提出了一种新的曲线描述和匹配的方法它采用数据结构中二 叉树来描述曲线，这里将该树称之为曲线树，树中的元素是与曲线曲率相联系的 有向相对高度这种方法在实际应用中可以根据曲线描述与匹配精度的需要来调 整树的层数，对同一曲线来说，曲线树的层数越多，对曲线刻画越精细这种描 述方法关于平移、旋转、拉伸以及对称变换有很好的不变性，而且对曲线上小的 扰动不敏感最后我们在这种曲线描述法的基础上引进了刻画曲线相似度的曲线 距离，并将其应用于形状匹配，取得了很好的效果 参考文献： 【1 】chc h e ，ps pw a n g p a l mr e c o g n i t i o na n dc o m p u t e rv i s i o nw o r l ds c i e n t i f i c ，2 0 0 4 2 m u m f o r dd a v i d m a t h e m a t i ct h e o r i e s o fs h a p e ：d ot h e ym o d e lp e r c e p t i o n ? i n ：p r o c g e o m e t r i c m e t h o d s i n c o m p u t e r v i s i o ns p l e ，1 9 9 1 ，1 5 7 0 ：2 - 1 0 3 】s u l l m a n h i g h - l e v e lv i s i o n ，m i tp r e s s ，c a m b r i a g e ，m a ，1 9 9 6 4 】ctz a h 工i i l z r o s k i e s ，f o u r i e rd e s c r i p t o r sf o rp l a nc l o s e dc u r v e s i e e et r a n sc o m p u t 1 9 7 2 ，2 1 ：2 6 9 - 2 8 1 5 1w kp r a t t ，d i g i t a li m a g ep r o c e s s i n g ，2 “e d i t i o n ，w i l e y , n e w y o r k ，1 9 9 1 【6 】mkh u ，v i s u a lp a u e mr e c o g n i t i o nb ym o m e n ti n v a r i a n t s ，i r et r a n si n f t h e o r y , 1 9 6 2 ， 8 ：1 7 9 1 8 7 7 】jlm u n a y , a z i s s e m a a n ( e d s ) ，g e o m e t r i cl n v a r i a n t s i nc o m p u t e rv i s i o n ，m i tp r e s s ， c a m b r i d g e ，m a ，1 9 9 2 8 r tc h i n ，crd y e r ，m o d e l - b a s e dr e c o g n i t i o ni nr o b o tv i s i o n ，a c mc o m ps u r v e y s ，1 9 8 6 ， 1 8 ：6 7 1 0 8 9 e n d e ro z c a n ，c h i l u k u r ikm o h a n p a r t i a ls h a p em a t c h i n gu s i n gg e n e t i ca l g o r i t h m s p a t t e r n 浙江大学硕士学位论文 r e c o g n i t i o nl e r e r s1 9 9 7 ，1 8 ：9 8 7 - 9 9 2 【1 0 s j a g g i ，m u l t i s c a l eg e o m e t r i c f e a t u r ee x t r a c t i o na n do b j e c tr e c o g n i t i o n ，m i tp h d t h e s i s ( l i d s - t h2 3 8 4 ) ，1 9 9 7 1 1 t ob i n f o r d ，i n f e r r i n gs u r f a c e s f r o m i m a g e s ，a r t i i n t e l l ，1 9 7 1 ，1 7 ：2 0 5 4 4 1 2 dm a n - , v i s i o n ，f r e e m a n ，s a nf r a n c i s c o ，1 9 8 2 【1 3 ib i e d e r m a n ，h u m a n i m a g eu n d e r s t a n d i n g ：r e c e n tr e s e a r c h a n da t h e o r y , c o m p v i s i o n g r a p h i m a g ep r o c e s s ，1 9 8 5 ，3 2 ：2 9 7 3 1 4 a s h o ks a m a l ，j o d ie d w a r d s g e n e r a l i z e dh o u g ht r a n s f o r m f o rn a t u r a ls h a p e sp a t t e r n r e c o g n i t i o nl e t t e r s ，1 9 9 7 ，1 8 ：4 7 5 - - , 4 8 0 1 5 】jz h a n g ，xz h a n go b j e c tr e p r e s e n t a t i o na n dr e c o g n i t i o ni ns h a p es p a c ep a r e mr e c o g n i t i o n ， 2 0 0 3 ，3 6 ：11 4 3 - 11 5 4 1 6 ug r e n a n d e r , d m k e e n a n t o w a r d sa u t o m a t e di m a g eu n d e r s t a n d i n g ，ja p p l s t a t i s t - ，1 9 9 3 ， 1 6 ：2 0 7 - 2 21 17 ug r e n a n d e le l e m e n t so fp a t t e r nt h e o r y , j o h n sh o p k i n su n i v e r s i t yp r e s s ，b a l t i m o r e ，m d ， 18 f a r z i nm o l d a t a r i a n ，s a g e g ha b b a s is h a p es i m i l a r i t yr e t r i e v a lu n d e ra f f i n et r a n s f o r m s p a t t e r n r e c o g n r i o n 2 0 0 2 3 5 ：3l 4 1 ( 1 9 z h o n gx u e ，d i n g g a n gs h e n ，e a mk h w a n gt e o h a ne f f i c i e n tf u z z ya 1 9 0 r i t h mf o ra l i g n i n g s h a p e su n d e ra f f i n e t r a n s f o r m a t i o n sp a r e m r e c o g n i t i o n ，2 0 0 i ，3 4 ：1 1 7 1 1 1 8 0 【2 0 b h a n d a r k a r ，sm af u z z yp r o b a b i l i s t i cm o d e lf o rg e n e r a l i z e dh o u g ht r a n s f o r m i e e et r a n s s y s t e m s ，m a nc y b e r n e r , 1 9 9 4 ，2 4 ：7 4 5 - 7 5 9 【2 1 b a l l a r d ，d h g e n e r a l i z i n g t h e h o u g ht r a n s f o r m t od e t e c t a r b i t r a r ys h a p e s p a t t e r n r e c o g n i t i o n ，1 9 8 1 ，1 3 ( 2 ) ：1 1 1 1 2 2 【2 2 a s h o ks a m a l ，j o d ie d w a r d s g e n e r a l i z e dh o u g ht r a n s f o r mf o rn a t u r a ls h a p e sp a t t e r n r e c o g n i t i o nl e t r e r s ，1 9 9 7 ，1 8 ：4 7 3 - 4 8 0 【2 3 p e d r off e l z e n s z w a l br e p r e s e n t a t i o na n dd e t e c t i o no fd e f o r m a b l es h a p e i e e et r a n so n p a t t e r na n a l y s i sa n dm a c h i n ei n t e l l i g e n c e ，2 0 0 5 ，2 7 ( 2 ) ：2 0 8 _ 2 2 0 2 4 f a r z i nm o k h t a r i a n ，s a a d e g ha b b a s i s h h n p es i m i l a r i t yr e t r i e v a lu n d e r a f t - m et r a n s f o r m s p a t t e r nr e c o g n i t i o n ，2 0 0 5 ，3 5 ：31 - 4 1 7 浙江大学硕士学位论支 2 5 w a n gr s i m a g eu n d e r s t a n d i n g b e i j i n g ：s c i e n c ep r e s s ，2 0 0 1 ( i nc h i n e s e ) ( 王润生图象理解北京：科学出版社，2 0 0 1 ) 2 6 d i n gx fe t c r e v i e wo ns h a p em a t c h i n g a c t aa u t o m a t i c as i n i c a 2 0 0 1 ，2 7 ( 5 ) ：6 7 8 _ 6 9 4 ( i n c h i n e s e ) “险峰等形状匹配综述自动化学报，2 0 0 1 ，2 5 ( 7 ) ：6 7 8 - 6 9 4 ) 8 浙江走擘硕士学位论文 第二章二维形状表示及识别 物体的形状是人的视觉系统分析和识别物体的基础。一般来说，我们对物体 的识别更注重于它们的形状，而物体的纹理，颜色次之，因此如何表示形状以及 比较形状问的差异在机器视觉的应用和研究领域具有非常重要的意义，诸如机器 人、勘察、制图和建筑设计中都有应用。例如，在机器人中，影像中的目标的外 形可以用合适的_ 维形状表示来模型化。于是，这些例子可以通过把它们在具体 影像中的实际外形与由模型决定的预期的外形作比较进行识别和定量检测。 形状表示可以基于形状的边界或区域的描述。第一种方法是用目标的边界和 边界的特征( 如边界长度，曲率，傅立叶描述子等) 来描述目标形状。这种方法 与边缘和直线检测有直接关系，得到的描述结果称为外部描述。外部形状描述简 洁，因而应用广泛。后一种方法是利用目标在图像内所覆盖的区域描述形状。这 种方法来自区域分割，其描述结果称为内部描述。表示可以是结构性的，即形状 ( 如它的边界和面积) 可分成段且段可以编码。它们也可以是整体的，这时，整 个形状可进行编码。最后，表示可以是单级的或多级的。多级的表示通常涉及在 多重、离散层次上的形状描述，而单级表示仅在单一层次上编码。 这一章对二维形状表示的研究作了一个概述。下面介绍了常见的几种形状表 示方法和识别法，其中前面几种为外部描述方法及有关识别方法，后几种是内部 描述方法和有关识别方法。 2 1 链码 假使二值图像中某一目标的边界用值为1 的象素构成的连通路径( 包括四连 通路径和八连通路径) 表示。这里路径可以看成是由连接两个相邻象素线段组成 的，如图2 1 所示。每一条线段都有一个方向，当沿着边界顺时针遍历目标边界 时，边界链上的方向码便构成了一个链码。如图2 1 所示的四连通路径的链码为： 0 0 3 0 0 3 3 3 2 1 2 2 3 2 2 1 1 0 1 1 ( 从路径的左上角开始) 。可以看出，链码的形式与起点 的设置有关。因为路径是闭合的，所以，由于起点的设置不同而得到的不同的链 码仍然表示同一形状。为了满足目标识别时单一性的要求，可以循环移动链码， 9 浙江大学硕士学位论文 使由链码构成的整数数值最小，取这个最小整数为确定的链码。用链码表示边界 的优点是具有平移不变性；缩放不变性，可以通过改变采样栅格的大小来实现； 旋转不变性可以用差分链码来实现，设x 。x ：h 为链码，d 1 4 氐为差分链码， 差分链码吐可按下式计算： f l f = 1 ( 2 1 ) 其中差分d 汐( ，葺一。) 是通过计算链码一相对于它的前点t 一。逆时针方向旋转 9 0 或4 5 t 角度的次数得到的。因为边界是封闭的，所以把n n - - + n n h 看作 第一个元素五的前点。差分链码代表方向差分，因而具有旋转不变性( 旋转石2 角度的整数倍时具有旋转不变性) 。在直角坐标栅格中旋转非特殊角度( 即不是 州2 角度的整数倍) ，会改变边界的形状，因此也改变了差分链码。 l 7 l + i c - 一 1r r l + l i 2 图2 1边界的链码表示 j 1r 1r 3 ( a ) 4 连通链码 04 图2 2边缘链码方向 222 3 3 3 j一 1 。 7 51 r67 ( b ) 8 连通链码 0 1 0 0 ) i h“0够蟛 r i j 、，l i i 4 浙江太擘硕士学位论丈 对于四连通链码，每个元素只需要2 位存储空间，而存储边界像素坐标则需 要2 字节空间，所以链码可以作为边缘描述的一种很好的压缩方法。链码还可以 用于计算边界的一些特征，如形状的长度，大小等与目标形状有关的计算，具体 可参考文献【1 。 用链码表示形状形式简洁，而且对于大部分形状来说，链码是形状边缘描述 的种很好的压缩方法，而且复原原始形状简单无误差，所以它是种很好的数 据保持方式。 链码能够简单实现形状4 5 n 度的旋转和整数倍的比例放缩。但由于用链码表 示形状时所采用的链码值的有限性，往往用4 或8 个值，而对于一线段来讲，它 的方向远远多于8 个值，从而使形状的其他角度的旋转存在一定的问题，同时一 些形状的放缩也存在一定的误差，这些问题的出现是链码值的有限性和本身形状 用链码表示的离散特点造成的。 基于链码提出的形状识别方法易受形状边界噪音的干扰。在参考文献 2 】中， p a r k 提出了边界链码直方图的方法匹配形状，有很好的抗边界扰动能力，但是它 是以误识率的提高为代价。这种表示方法主要思路是对不同形状的边界链码值进 行统计，并对直方图中4 ( 或8 ) 个值按值的大小进行排序，从而建立直方图， 设形状a ，b 的边界链码直方图中的4 ( 或8 ) 个值分别为c ( k ) ，q ( k ) ( k = o ，1 ，2 ，3 或k = 0 ，1 ，2 ，3 ，4 ，5 ，6 ，7 ) ，定义形状距离如下： d ( a ，b ) =鹰( 鳅】_ c 嘲) 2 n = 4 或8 在该算法中差异较大的形状间距离可能很小，即误识率较高，作者认为可以 对上述算法进一步修整，从而提高形状识别的准确率，其体如下：对形状边界的 链码值统计后，不排序，直接建立链码直方图。定义形状距离： ，n 一1 d ( a ，曰) = m i n j 2 ( q k l c t 卜口) 2 ，= 4 或8 u 1k0 d e o ，1 ，2 ，3 或d o ，1 ，2 ，3 ，4 ，5 ，6 ，7 。 其实从a 值可以估计两个形状方向的差异。 这种方法对于形状识别实现速度快，但不适合识别率要求较高的问题，因为 浙江是擘硕士学住论文 在构造链码直方图时丢失了很多边界信息，对于同一链码直方图有很多对应的形 状，故这种识别法仍具有一定的误识率，这种方法应用于形状识别前的粗识别效 果很好，不仅速度快，而且简化了形状后面的进一步识别。 2 2 多边形近似 在些应用中，数字图像边界提供的信息具有一定的冗余度，这时可以考虑 用近似方法描述边界。最常见的方法是逐段线性近似( 多边形近似) 方法。这种 方法用一个与原边界曲线相近的多边形来表示边界。为了获得满意的近似效果， 可采用某种误差指标来衡量多边形与原曲线相近的近似程度。假设从a 点到b 点的数字曲线用直线a b 来近似，如图2 3 所示。令x 。x ：，h 为数字曲线上象 素的坐标，t 一一，扛2 ，n