（通信与信息系统专业论文）线性骨架相似性度量研究.pdf

华中科技大学硕士学位论文 摘要 随着计算机视觉应用的日益，。泛和自动化程度的进一步提高，图形识别问题已 成为当前的一个研究热点。在虚拟现实、工业模拟、科学计算可视化等领域，人们 对其相关技术的发展提出了迫切要求。本文以国家自然科学基金项目 ( n o 6 0 2 7 3 0 9 9 ) “基于广义条件骨架的三维图形识别新方法研究”为背景， 研究线性骨架相似性度量的相关问题。本文提出了一种用骨架树进行线性骨架拓扑 相似性度量的算法，对线性骨架形状相似性的度量也作了初步的研究，在骨架匹配 这一长期存在的难题上，取得了一些研究成果。 本文首先介绍了骨架的定义和提取等基本背景，综述了相似性度量的相关理论 以及当前的图形识别方法概况。 然后，建立了一种新颖的骨架树模型。将骨架映射到一种树状结构中，树的层 次和节点间的连接关系主要反映骨架的拓扑特性。对于用一般规则无法建立骨架树 的环状骨架进行了处理，给出了环状骨架的骨架树建立过程。对于拓扑较为复杂的 物体，由多尺度连续骨架算法建立多尺度骨架树由粗到精的反映物体的拓扑特征； 同时，通过对骨架收缩各种情况的讨论，建立了一套合理的根节点选暇准则，为多 尺度分级匹配奠定了基础。 本文给出了一种基于骨架树的线性骨架拓扑相似性度量算法。通过骨架树邻接 矩阵的特征向量和给出了拓扑标记向量的定义，用拓扑标记向量之差的二范数作为 两个骨架树匹配节点对的距离，构造两个骨架树节点之问的最佳匹配关系，将骨架 树的匹配距离定义为建立最佳匹配关系的节点对的距离之和。骨架之间的拓扑距离 则由骨架树的匹配距离来表示，并用该距离值的大小作为线性骨架拓扑相似性的度 量。在计算复杂度和时间复杂度均较低的情况下，对一般二维图形取得了较好的实 验结果。并提出利用多尺度骨架树对复杂物体进行多级匹配的思想从而使该算法具 有更广泛的适用性。 本文对线性骨架的形状相似性度量也作了研究，利用骨架的最大内切圆半径、 华中科技大学硕士学位论文 骨架枝上的骨架点数等重要的形状信息，对骨架进行坐标平移、旋转、拉伸等对齐 操作将骨架枝的曲线两个端点的连线变换到x 轴正向后，给出了骨架枝之问匹配距 离的定义，然后在两个骨架的骨架枝之间建立最佳匹配关系，将骨架的形状匹配距 离定义为建立最佳匹配关系的骨架枝的匹配距离之和。该形状匹配算法对简单二维 图j 眵取得了比较满意的实验结果。 最后，对全文进行了总结并指出了后续研究工作的方向。 关键词：骨架、相似性度量、骨架树、多尺度骨架树、拓扑标记向量 l i 华中科技大学硕士学位论文 a b s t r a c t w i t ht h ew i d e a p p l i c a t i o no fc o m p u t e rv i s i o na n dr a p i dd e v e l o p m e n ti na u t o m a t i o n ， g r a p h i c sr e c o g n i t i o nh a sb e c o m eaf o c u so fc u r r e n tr e s e a r c h p e o p l ea r ei n c r e a s i n g l y d e m a n d i n gi ni t sr e l a t e dt e c h n o l o g i e s ，e s p e c i a l l yi nv i r t u a lr e a l i t y , i n d u s t r i a ls i m u l a t i o n ， s c i e n c e c o m p u t i n gv i s u a l i z a t i o n ，e t c s u p p o r t e d b y t h en a t i o n a ln a t u r a l s c i e n c e f o u n d a t i o no fc h i n a ( n o 6 0 2 7 3 0 9 9 卜“n e wm e t h o d s t u d yo f3 dd a p h i c sr e c o g n i t i o n b a s e do ng e n e r a l i z e dc o n d i t i o n a ls k e l e t o n ”，t h ew o r ko ft h i sp a p e ri st od or e s e a r c ho n s i m i l a r i t y m e a s u r e m e n to fl i n e a rs k e l e t o n a ne f f e c t i v el i n e a rs k e l e t o n t o p o l o g i c a l s i m i l a r i t ym e a s u r ea l g o r i t h mb a s e do i ls k e l e t o nt r e em o d e la n dt h ee l e m e n t a r yr e s e a m h o fs h a p e s i m i l a r i t y m e a s u r e m e n ta r ep r e s e n t e di nt h i s p a p e lw h i c ha c h i e v e ds o m e c r e a t i v ef r u i t si nt h ed i f f i c u l tp r o b l e mo fs k e l e t o nm a t c h i n g i nt h i sd i s s e r t a t i o nt h eb a c k g r o u n do fs k e l e t o nd e f i n i t i o na n de x t r a c t i o n ，t h er e l a t e d t h e o r yo fs i m i l a r i t ym e a s u r e m e n ta n dc u r r e n tg r a p h i c sr e c o g n i t i o nm e t h o d sa r ef i r s t l y s u m m a r i z e d t h e nan o v e ls k e l e t o nt r e em o d e li se s t a b l i s h e d t r a n s f o r mt h es k e l e t o no fo b j e c t s i n t oat r e es t r u c t u r ei nw h i c ht h eh i e r a r c h yo ft h et r e ea n dt h ec o n n e c t i o nr e l a t i o n so ft 1 1 e n o d e sr e f l e c tt h es k e l e t o n st o p o l o g i c a lc h a r a c t e r i s t i c s e s p e c i a lr u l e sa r eg i v e nf o rt h e e s t a b l i s h m e n to fc i r c u l a rs k e l e t o nt r e e a sf o rc o m p l i c a t e do b j e c t sm u l t i - s c a l es k e l e t o n t r e e sa r ee s t a b l i s h e dt or e f l e c tt h eo b j e c t st o p o l o g i c a lc h a r a c t e r i s t i c sf r o m a p p r o x i m a t e l y t o p r e c i s e l y a t t h es a m et i m eas e r i e so fr o o tn o d e sc h o o s i n gr u l e sa r e g i v e nf o r m u l t i c l a s sm a t c h i n g a f t e rt h a tal i n e a rs k e l e t o n t o p o l o g i c a ls i m i l a r i t y m e a s u r ea l g o r i t h mb a s e do n s k e l e t o nt r e ei sd e t a i l e d d e f i n eat o p o l o g ys i g n a t u r ev e c t o rb yt h ee i g e n v a l u es u mo f t h es k e l e t o nt r e e sa d j a c e n c ym a t r i xa n d c o m p u t e t h ed i s t a n c eo fm a t c h i n gn o d e p a i rb y t h ed i f i e f e n c eo ft h et sv t h e ne s t a b l i s ht h eb e s tm a t c h i n gr e l a t i o n sb e t w e e ns k e l e t o n 华中科技大学硕士学位论文 t r e en o d e sa n dd e f i n et h e m a t c h i n gd i s t a n c eo ft w os k e l e t o nt r e e s a st h es u mo ft h e d i s t a n c eo fm a t c h e dn o d ep a i r s t h em a t c h i n gd i s t a n c eo fs k e l e t o nt r e e sr e p r e s e n t st h e t o p o l o g i c a ld i s t a n c eo fs k e l e t o n s t h et o p o l o g i c a ls i m i l a r i t yo fl i n e a rs k e l e t o n si sd e n o t e d b yt h i st o p o l o g i c a ld i s t a n c ev a l u e t h i sa l g o r i t h ma c h i e v e dg o o de x p e r i m e n tr e s u l t sf o r t h eg e n e r a lp l a n a rg r a p h i c si nl o wc o m p u t i n ga n dt i m ec o m p l e x i t y a sf o rc o m p l i c a t e d o b j e c t s ，t h e i d e ao fm u l t i - c l a s s m a t c h i n go fc o m p l i c a t e do b j e c t su s i n g m u l t i - s c a l e s k e l e t o nt r e e si sp u tf o r w a r dt om a k et h ea l g o r i t h mh a v ew i d e r a p p l i c a b i l i t y i na d d i t i o nt h e s h a p es i m i l a r i t y m e a s u r e m e n ti sr e s e a r c h e d + a f t e ras e r i e so f o r i e n t a t i o nt r a n s f o r m a t i o n si n c l u d i n gc o o r d i n a t et r a n s l a t i o n ，r o t a t i o na n ds c a l i n gt h e m a t c h i n gd i s t a n c ef u n c t i o no fs k e l e t o nb r a n c h e si s d e f i n e db ys o m ei m p o r t a n ts h a p e c h a r a c t e r i s t i c ss u c ha st h em a x i m u mr a d i u so fs k e l e t o n s i n s c r i b e dc i r c l e sa n dt h e n u m b e ro fs k e l e t o nn o d e si ns k e l e t o nb r a n c h e s t h e ne s t a b l i s ht h eb e s tm a t c h i n g r e l a t i o n sb e t w e e ns k e l e t o nb r a n c h e sa n dd e f i n et h es h a p em a t c h i n gd i s t a n c eo fs k e l e t o n s a st h es u mo ft h ed i s t a n c eo fm a t c h e ds k e l e t o nb r a n c h e s t h ee x p e r i m e n tr e s u l t so f s i m p l ep l a n a rg r a p h i c s a r es a t i s f a c t o r y f i n a l l y , t h i st h e s i sm a k e sas u m m a r i z a t i o no ft h ee n t i r ew o r ka n dp o i n t s o u tt h e i t l l r er e s e a r c hd i r e c t i o n k e y w o r d s ：s k e l e t o n 、s i m i l a r i t ym e a s u r e m e n t 、s k e l e t o n t r e e 、m u l t i s c a l es k e l e t o nt r e e 、 i b p o l o g ys i g n a t u r e v e c t o r 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对木文的研究做页献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 窄哮 日期：伽争年，月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关傈留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在 本论文属于 不保密口。 ( 请在以上方框内打“”) 学位论文作者签名：霉姊 日期：加4 年岁月7 e t 年解密后适用本授权书。 指导教师签名：专t 降 同期：跏锥厂月7 日 华中科技大学硕士学位论文 1 1 引言 1 绪论 物体识别是计算机视觉的重要组成部分，在c a d 、集成电路设计、机器人路径 规划、数字化城市、生物医学工程以及军事等领域有着广泛的应用前景【1 ，2 l 。物体的 识别过程简单概括起来可分为形状描述和识别匹配两个步骤，具体来说需要解次如 下几个关键问题：原始图形数据一数学表达一特征提取一识别匹配。 三维图形数据有两种生成方法，一种是用激光或毫米波传感器束获取真实物体 的三维数据；另一种是用c a d 软件工具在计算机上生成三维模型。目前的工业检测 和科学研究中普遍采用的是后一种方法。 如何用更规范化的数学形式描述三维图形是第二步的关键内容，根据描述物体 坐标系的刁i 同，可将三维物体表达方法分成以观察者为巾心( v i e w e rc e n t e r e d ) 和以 物体为中心的( o b j e c tc e n t e r e d ) 两个主要类别。以观察者为中心的表达方法依赖于 从某个或多个视角来确定物体的外观，通过选择几个视点拍摄多幅图像来合成完 整的三维信息，通常要求的特征视图或形态图的数量较大。以物体为中心的表达方 法则发展得更为成熟与完备，如拟合曲面法【3 , 4 】、广义法矢球法i 5 1 、网格表达法 6 3 1 、 体素表达法1 8 1 ，】、) t 3 l 树表达法峨构造实体几何法( c o n s t r u c t i v es o l i dg e o m e t r y ，c s g ) l 1 0 1 年l lj 。义柱( g e n e r a l i z e dc y l i n d e r ) 法1 1 1 】等。 三维图形的数学表达数据量十分庞大，并且带有冗余信息，如果直接用来进行 匹配操怍，运算量将相当繁重，并且特征表达不突出，匹配方法不容易设计。三维 图形的特征提取由此成为物体识别系统一个关键的步骤，其目的在于用更加精练的 模型来表示复杂三维物体的本质特征从而提高匹配效率。提取的模型需要能表征图 形最本质的拓t t , t u 形状信息，并具备仿射不变性；能适用于广泛种类的图形并对任 何图形的描述具备唯一性；具有规范简单的数据结构以便于后续的匹配过程。 三维图形的特征提取可分为代数特征和几何特征两大类。代数特征一般是对目 标进行数学描述后所计算出来的一些数学特性，例如曲面拟合多项式参数、f o u r i e r 华中科技大学硕士学位论文 描绘子、向量矩、交比等不变量特征，这类特征的缺点是几何特一阽不商观，对于数 学模型的理论研究要求较高。几何特托丰霭指的是罔形的j l j 何尺、j ，如 1 标的长度、 宽度、高度、而积等。几何特征在对图形特性的描述更力l j 直观一些，并且适用性更 加广泛，对于一些不规则的难以用方程表达的物体同样适用。 识别匹配过程就是将目标物体的描述与模型库中模型的描述进行相似性度量， 通过数值化的差值决定匹配结果的过程。匹配的方法很多，它主要由图形描述的方 法米决定。在用曲面的拟合函数来表达图形时，可采用最小方差匹配方法。这种基 于图形代数特征的匹配方法虽在二维图形处理中有广泛的应用，却不适于推广到三 维图形领域，因为三维图形结构和形状的几何意义复杂得多，代数特征表达这些性 质不够直观，且复杂度太高。因此在三维图形识别系统中，基于几何特征的树结构 匹配方法得到了深远的发展。此类方法度量图形时利用的是真实的三维信息而非二 维投影信息，且描述结果简单易操作，几何特征尤其是基本的拓扑特征表达突出， 在谚 别系统的应用中有着得天独厚的优势。 骨架就是一种能较好保留图形拓扑和形状信息的儿何特征描述。骨架是图形识 剐的一种有力于段，基于骨架的目标表示和识别技术成为物体识别和计算机视觉的 重要研究内容。该领域的关键技术是骨架的提取和基于骨架的目标表示，以及寻找 种能较好度量骨架之间距离的函数，实现对骨架进行快速准确的相似性度量。 1 2 骨架的概况 1 2 1 骨架的定义 骨架( s k e l e t o n ) ，又称中轴( m e d i a l a x i s ) ，是图形几何形态的一种重要拓扑描 述。骨架是一种线型的几何体，它居于图形的对称中心，有着与原图形相同的拓扑 结构，并可保留原图形的形状信息。图1 - 1 是几个简单图形及其骨架示例。 华中科技大学硕士学位论文 圜b 叁 图1 - 1 图形及其骨架 骨架的线型结构减少了图形中的冗余信息，方便对图形进行相似性度量和匹配， 是图形描述、图形识别和检索的一种重要方法。多尺度骨架则能由粗到精的表征图 形从憋体结构到局部形状的分层次信息，反映了目标的重要视觉线索，便于对复杂 物体的进行分级匹配。因此，骨架被广泛应用于计算机视觉、生物形状摇述、模式 识别、工业检测以及图形压缩编码等领域。 任何图形的骨架都是唯一确定的。图形学中对于骨架有着明确的定义，以下是 三种竣典型的定义： 】， 对于图形4 内的一点p ，若以p 点为圆心的图形内切圆( 球) d ，与爿的边 界至少有两个切点，则点p 是幽形a 的骨架点。1 9 6 7 年b l u m 最早给出了 该定义的物理描述，即火烧模型( g r a s s f i r e ) 的定义1 1 2 】。在f 一0 时刻，将 图形边界上所有的点同时点燃，火焰以相同速度向图形内部蔓延，当火焰 的前沿相遇时火焰熄灭，火焰熄灭处所有点的集合就构成了该图形的骨架。 骨架点即为图形边界点上的火源同时向图形内部各个方向等速燃烧的相遇 点。 2 ， b l u m 还给出了另一种最大圆( m a x i m a ld i s k ) 定义。设d 为图形s 的 一个内切圆( 至少有两点与图形边界相切) ，如果d 不是s 内部任何其它圆 的子集，则称d 为最大圆。最大圆即是完全包含在图形内部且不被图形内 其它任何圆所包含的圆。将骨架定义为图形内部所有最大圆圆心的集合。 3 s e r r a 从数学形态学( m o r p h o l o g y ) 的角度对骨架也进行了定义1 1 4 】，将骨 架定义为形态腐蚀和开运算：设集合xcz “，口为单位闭球，则集合x 的 骨架s k ( x ) 由一系列骨架子集暖) 组成，s k ( x ) = u ) 。其中 r z o s k ，( x ) = n ( x o r b ) ( x o 憎) 。 。 华中科技大学硕士学位论文 图卜2 给出了骨架两种定义的示意图，图卜2 ( a ) 是由火烧模型定义的骨架示倒 图卜2 b 是由最人圆定义的骨架示例。 威盐 t 火种传播詈架( b 最大圆盘骨架 图卜2 骨架的两种定义 可以证明以上三种定义是完全等效的。 以上定义均建立在连续空间，而实际研究中处理的大多数是离散图形，例如以 像素点集构成的二维图像、体素表达法描述的三维图形等。如何定义离散空间的骨 架是一个难点，并直接影响着骨架提取的效果。离散空间的骨架实际上是对连续域 骨架定义的近似，离散域骨架的定义过程往往是与具体的骨架算法相结合的。 另外，依照骨架定义，二维图形的骨架必定是一种线型的结构，而三维情况下 往往带有面型结构。面型结构给匹配过程带来很大的困难，因此，提取一种近似的 线型三维骨架是未来三维骨架识别的必然要求。 1 , 2 2 骨架的提取方法 根据骨架的定义，提取骨架的方法大致可以分为以下几种类型。 ( 1 ) 模拟火烧模型的方法。这类方法模拟火烧模型的物理过程，出图形的边界开 始向内演化，逐步搜索到中轴骨架的位置。细化法c i l f i n n i n g ) 是这类方法的一人分 支【1 5 , t 6 1 。其基本思想是逐层均匀的剥除图形的边界点，直至最里层不能再剥除( 否 则会影响连通性) 的部分就得到了图形的骨架。通常的实现手段是给出一种简单点 ( s i r e p l ep o i n t ) 的定义，此种简单点的移除不会影响原始图形的连通关系，简单点 的判断通过考察某点与其领域点的连通关系实现，每次迭代过程去除本轮的简单点， 循环执行迭代过程直至去除所有的简单点，剩余的点集即构成骨架的点集。细化法 华中科技大学硕士学位论文 的小足在于计算复杂度高和骨架点的位置不够精确。 模拟火烧模型的：疗法还有一类是基于蛇形活动边界模型( s n a k e ：a c t i v ec o n t o u r m o d e l ) 的1 1 7 , t 8 1 ，这类方法引入蛇形模型在建立了距离变换的图形内运动，从外围边 界在距离变换场乖引下向骨架位置演化。此类方法能保证较高的精确度，但是向三 维空问推广有一定的难度。 ( 2 ) 基于距离变换的方法【娉。l 。可以证明，前文所述的图形的最大圆定为图形 的内切圆。因此图形内切圆集合是最大圆集合的包集。骨架算法可以考察以某点为 圆心作的内切圆，如果该圆不被其它的任何内切圆包含，则此点作的内切圆是最大 圆，此点是骨架点。这就是基于距离变换的骨架算法的基本思路。距离变换记录了 图形内每个点到边界的最短距离，以任一点为圆心，以该点的距离变换值为半径作 的团就是以该点为圆心的图形内切圆。因此距离变换这一图形分析里的基本手段被 引入进了骨架算法的研究中，利用距离交换可以生成任一点的内切圆，然后比较所 有内切圆的包含关系就能判断哪些是最大圆。 基于距离变换的方法在骨架点的准确度上有明显的优势，但是这类方法很难保 证骨架的连通性和骨架结果的单像素特性，这将影响骨架拓扑特性的表达以及后续 的匹配过程。 f 3 ) v o r o n o i 图的方法1 2 4 粕】。v o r o n o i 图是计算几何领域里的一项重要工具。给出 空问里由n 个点组成的点集s ，对于点集s 中的点p i ，v o r o n o i 多面体表示到点a 距离小于到点集s 内任何其它点距离的空间区域。v o r o n o i 图是所有这些v o r o n o i 多 面体的集合。根据骨架的定义，最大圆( 球) 与图形边界是相切的，骨架点与至少 两个边界点的距离相等且取最小值。因此，图形边界点集的v o r o n o i 图能够给出部分 的骨架。v o r o n o i 图不完各之处在于v o r o n o i 图计算的是空间内到给定点集距离最小 的区域，因而不区分图形内外部分，在遇到有凹点的图形时与精确骨架有差别，可 知骨架是v o r o n o i 图的子集。 华中科技大学硕士学位论文 1 3 相似性度量简介 1 3 1 物体识别技术概论 物体识别方法辛要有以下几种类别：基于模型的物体识别( 广义柱法、图结构 法、曲面法等) ，基于特征矢量表示的物体识别( 统计识别法、神经网络法等) 和基 于知识的物体识别( 模糊数学法、模糊神经网络法) 等。 基于模型的识别方法所识别的目标是已知的，它利用计算机辅助设计( c a d ) 来 建立目标的几何模型，对模型的表面、边界及连接关系进行完整地描述，另一方面， 从传感器获得的真实物体的三维信息，经处理后也可得到一种表面、边界及连接关 系的描述。把来自模型的和来自传感器的这两种描述加以匹配，就可来识别三维物 体。基于c a d 模型识别方法的优点是：1 ) 可以唯一地描述三维物体；2 ) 精确地设 计几何模型；3 ) 可以得到三维物体的所有视角图像。它的缺点是：只能对已知形状 的目标进行识别，系统识别不具有学习能力。 基于特征矢量表示的识别，并不是将物体所有的信息完整的描述，而是选择一 部分与众不同的特征描述物体，这样可以使匹配的过程变得简单，由于特征矢量往往 足随机的，因此，可以用统计的方法设计识别方案，例如k 近邻法、b a y e s 法等。这 些方法对识别孤立的物体相当有效，对于识别有遮挡物体和三维物体，效果不很理想。 姿态聚类法是利用图像的几何特征来识别物体一种方法，它基于这样的原理：刚体 在三维空间所有的点、边等几何特征的变换，都可用一个变换矩阵来描述，这个矩阵 称为姿态变换矩阵。由于变换矩阵是从多个候选矩阵中检出来的，因此可在存在遮 挡、缺少某些特征、有噪声等情况下，识别物体及其成像姿态。神经网络法也是利 用物体的特征柬识别物体的，常用的b p 神经网络对样本的训练和学习是自动进行 的，它可用来识别未知的目标，并且具有一定的抗干扰和抗遮挡能力。 基于知识的识别方法是不考虑精确的数学描述，在专家经验和认识的基础上， 从所获得的大量数据和经验出发，利用模糊数学、人工智能及模糊神经网络等完成 识别过程。该方法要求设计人员要具有丰富的经验和知识，目前暂无较大的发展。 华中科技大学硕士学位论文 1 3 2 当前的图形识别方法 图形识别是计算机视觉的重要组成部分，在c a d 、集成电路设计、机器人路径 规划、数字化城市、生物医学、医疗诊断以及军事目标识别等领域有着广泛的应用 前景【2 8 】。物体之间的相似性度量在机器和人类视觉系统中都有着重要意义。 传统的相似性度量方法主要用于图形图像检索、目标识别和物体变形等。目前， 国际上二维物体的相似性度量方法较多，并且各有其特点，三维物体的相似性度量 方法则受到了方法上的限制，通常是其在某个方向的投影图之间的匹配，由于只能 利用物体的二维信息，仅依靠灰度和二维形状来识别物体传统的图像识别方法遇 到了很大困难，有些困难甚至是难以克服的。国际上已提出利用物体的三维信息来 识别物体，并提出了许多立体视觉系统，但离真实的三维物体识别还有相当距离。 自1 9 6 7 年b l u m 首先用骨架进行图形匹配以来，骨架就广泛应用于物体识别， 此时，往往先把骨架转化为特征关系图，然后对特征关系图进行匹配。h s u n d a r 等 人把物体的骨架用最小生成树的方法转化为骨架图1 2 ”，然后对其进行匹配。文献 f 3 0 3 1 1 则使用编辑距离来度量奇点图的相似度，而使用编辑距离来度量图的相似度 则需要解决编辑操作的完备性问题，文献 3 0 3 1 并没有给出这样的证明。d g e i g e r 等人则提出用中轴线树( s a - t r e e ) 1 3 2 - 3 3 l 进行物体的匹配，这种方法不能保持各节点 所在边的有序性，从而造成无法保留形状匹配结果的一致性。图的匹配是一个n p c 问题，基于以上特征关系图的匹配的计算复杂度很高。 另外提出的还有基于外围轮廓曲线的匹配方法【3 4 彻，其中较为典型的匹配是基 于一种最优相似变换实现特征点的一一对应，或者寻找从一条曲线到另一条曲线的 一种映射，通过惩罚变形中的伸长和弯曲能量获得最小化弹性势能。基于外围轮廓 的匹配方法通常具有以下若干种缺点：对两条曲线的非对称处理，抽样敏感性、不 具备旋转和尺度不变性、对关节和部分形变敏感等等。 还有一类形状描述方法通过建立形状轮廓的点集模型，并用一种分配算法实现 对形状的匹配。g o l d 等人采用g r a d u a t e d 算法【3 8 1 来匹配图像的边界特征。其后， b e l 0 1 q g i e 等人用h u g a r i a n 方法【3 9 】来匹配无序边界点，引入了表示剩余点相对位置的 华中科技大学硕士学位论文 粗略柱状图。这些方法具备无需有序边界点的优点，但是匹配不一定能保留形状的 一致性，因为在匹配过程中没有保留各部分形状阳j 的关系。 此外，还有一些局部形状匹配的方法，由于没有考虑整体拓扑信息，这类匹配 的对象范畴受到了限制，主要用于局部形状特征明显的图形的检索。 z h u 和y u i u e 提出一种f o r m s 框架【4 1 i 对运动物体进行匹配，通过种分枝和边 界策略比较它们的骨架图，这种骨架描述的内在不稳定性可以通过事先定义的模型 图得到解决。由于建模中需要选择初始点，该方法对于静l 上物体的适用性有限。 m a s a k i 等人提出的r e e bg r a p h 0 2 l 是一种可用来表示任意维物体的拓扑和骨架 特征的不含有高维分量的一维的图形结构。它通过个定义在物体表面的连续标量 函数“来创建，并且在其定义中引入了测地距离函数( g e o d e s i cd i s t a n c e ) 。浚方法对 于拓扑特征较明显的物体比较适用，但对于形状特征比较明显或拓扑简单的物体会 有较大的偏差。 k s i d d i q i 等人提出了一种著名的形状描述符奇点图s h o c kg r a p h 4 3 - 4 5 1 ，s h o c k g r a p h 实际上是赋有半径变化方向和速度的中轴。在奇点图的匹配中整合了物体形状 和拓扑的信息，较好的处理了边界噪声的影响。但由于奇点语法的复杂性，奇点图 的生成相对复杂，基于奇点图的匹配是一个计算复杂度很高的过程。对于多个物体 之间的匹配。如何降低匹配时间成为该方法的重要问题，且它对物体的形状细节丢失 较多，适合对物体做初始分类，但不适合检索。 下文将对r e e bg r a p h 和s h o c kg r a p h 两种较新的图形描述和识别方法进行相关 的介绍。 ( 1 ) r e e bg r a p h l 4 2 1 r e e bg r a p h 可用来表示任意维物体的拓扑和骨架特征且不合有高维分量的一维 图形结构。它通过一个定义在物体表面的连续标量函数来创建，并且在其定义中 引入了测地距离函数( g e o d e s t i cd i s t a n c e ) 。 华中科技大学硕士学位论文 图卜3 是一个二维的圆环和它的r e e bg r a p h ，其中函数口的取值网环上的点在 维平面的高度坐标 。 o ( r ，y ，z ) 。z 图卜3 圆环和其相应的r e e bg r a p h 物体表蕊s 上的点v 对应的函数群的定义如下： p ( v ) 2 j 二g ( v ，p ) d s ( 1 1 ) 其巾函数g ( v ，p ) 代表点v 和p 在s 上的测地距离，( v ) 则定义为点v 到s 面上所 有点的测地距离的总和，测地距离p ( v ) 由一种叫d i j k s t r a sa l g o r i t h m 的循环算法给 出。( v ) 越小表示该点到表面任意点的距离和越小，越靠近中心，球面具有一个恒 定的，。( 力值0 ，越不对称的物体( ，) 范围越大。 由于r e e bg r a p h 基于个连续的测地距离函数位，因此还可以进一步分解在不 同分辨率水平上以满足各种精度的要求。通过对区域进行基于函数的再分，并依 据一定规则构造2 系列的点( r n o d e ) 和边( r e d g e ) 来表示特定区域的连通分量 ( t - s e t ) ，从而得到多分辨率r e e bg r a p h ( m u l t i r e s o l u t i o n a lr e e bg r a p h ) ，m r g 是一组具有父子关系的节点和线段组成的树状图。 图卜4 给出了一个二维图形基于函数肛的再分所得到的m r g ，其中函数肛的取值 是图形上的点在二维平面的高度坐标：0 0 ，y ，z ) a 2 华中科技大学硕士学位论文 匾：匾覆 。口毒 + 坞- - 一n 0 7 f 、 ? 謦，j 气鼻i 7 、 k ： 。：- 嚆 图卜4 多分辨翠r e e b g r a p h 设m 为m r g 的一个节点( r n o d e ) ，m 的属性m 由参数口) 和t ( m ) 来定义： 鬲= ( 。) ，f ( 川) ) 其中，口) = 鬲l _ 竺丝篙l e n ) = m a x ) 一m i t ma r e a n 沏) 肌l jj 这艰，r n a m 足该m r g 划分的精度值，a r e a ( m 1 是m 对应的t - s e t 分量的面积， a r e a ( s ) 是整个表面s 的面积，l e n ( m ) 是m 所占据的心一) 的范围。 两个r n o d e 和n 之间的相似性有如下定义： s i m 面，i ) = m i n ( a ( m ) ，0 ) ) + ( 1 一o o m i n ( ( m ) ，o ) ) ( 是一个权值参数) ( 卜2 ) 两个m r g 图只和s 之间的相似性s i m ( r ，s ) 定义为： s i m ( r ，s ) 。盖咖( 磊，_ ) ( 相似性的具体计算是通过一种循环匹配算法来进行。其总体过程大致经过初始 化，寻找r n o d e 对进行匹配，再对之进行拆分，然后循环等步骤。匹配的过程依照 一定的准则从而保持着m r g 图的拓扑一致性。 在定义匹配函数之前先给出以下两个定义： l o s s ( m ，i ) 。丢 s i m ( m ，鬲) + s 咖( 孬，两 - s i m ( 一m ，二) ( 1 4 ) 该函数代表了经过匹配( m ，n ) 后相似性降低值的一个度量。 华中科技大学硕士学位论文 面( ) ，m ) = 孓n 。t f 长吐m ) ( 】一5 ) 该函数代表与m 点相邻且其。值的范围为【s ，t ) 的r n o d e 点集。 匹配函数则定义为： m a t ( _ ，磊) 一t o s s ( m ，二) 一罗，吣s ( 面( 嘶) ，n ) ) ( 1 6 ) m r g 可以在不同的精度要求下较好的表征物体的拓扑及骨架特征。基于m r g 的拓扑匹配算法可以由粗到精的计算出相似性。这种在不同精度下分级表征物体的 拓扑特征以及由粗到精的分级匹配思想，对于本文的骨架树匹配方案不失为一种良 好的借鉴。 基于m r g 的拓扑相似性度量除了可以将每个r n o d e 点的面积和长度属性引入 到相关性的计算中，还可以根据匹配准确读的需要将颜色，纹理，曲率等特性也引 入其巾，各个属性所占的权值可以根据需要进行调整。该算法不依赖于图形的具体 位黄或姿态，具有良好的变换和旋转不变性，并且对于栅格划分所引起的连通性改 变具有健壮性，能够抵抗微小噪声以及变形带来的影响。 基于m r g 的拓扑匹配算法对于拓扑特征较明显的物体比较适用，但对于拓扑简 单形状特征比较明显物体有较大的偏差，从而使该方法的适用性受到局限。 ( 2 ) 奇点图s h o c kg r a p h 4 3 4 6 】 k s i d d i q i 等人提出的一种类似于骨架的形状描述符奇点图s h o c kg r a p h ，它 和骨架有某种内在的联系，势且对于本文的骨架树模型的建立以及基于拓扑标记向 量的匹配函数定义有着良好的启发和借鉴作用。 通过将曲线( 曲面) 演化理论与能量最小化原理结合，人们提出了一些活动外围 模型( 如蛇形曲线) ，并将它们应用于视觉形状分析。这些模型的关键思想在于将二 维曲线或三维曲面在一定约束条件下进行演化，使其趋向亮度图像中我们感兴趣的 特征位置。沿着这种思路，k i m i a 、t a n n e n b a u m 和z u c k e r 从数理物理学理论出发， 提出了奇点图( s h o c kg r a p h ) 的概念。在一个反作用一传搔空问计算曲线演化过程 中形成的s h o c k ( 奇点) ，用它来描述图形的形状特征。并提出了如下演化方程，作用 华中科技大学硕士学位论文 于平面上的简单闭合曲线： c z ；( 1 + 乜k ) n (z-7、 c ( s ，o ) ；c 。o ) 这里c ( s ，f ) 是曲线的坐标向量，n ( s ，f 是内法矢，s 是路径参数，f 是曲线进化的时 间。常数az 0 控制曲率虾的正则化效果。当口比较大的时候，这个方程就是几何学 的热力方程：当c e 0 的时候，则等价于b l u m 的模拟火种传播模型。而后者正是我 们能够将骨架和s h o c k 联系起来的理论依据。文献中将这个模型扩展到三维。s h o c k 满足特定的拓扑和几何约束，可以依据特定的文法( s h o c kg r a p hg r a m m a r ) 由形状演 化生成。 我们忽视s h o c k 形成的动态过程，则s h o c k 的轨迹就是物体的骨架，s h o c k 即为物 体骨架上的点。但是和b l u m 骨架不同的是，s h o c k 也提供了轨迹以外的信息。如图 1 5 所示，四类s h o c k 分别反映了半径函数在局部范围内的不同变化趋势。 f ；r s l - o r d e rs o e o n d o 峭e r 图卜5s h o c k 的分类 在1 - s h o c k 处，半径函数单调变化，反映向外突出的变化过程；在2 - s h o c k 处， 半径函数达到局部最小值，如果移开2 - s h o c k ，就会使骨架变得不连续，所以这类s h o c k 反映了颈状特征：在3 - s h o c k 处，半径在一段距离内保持不变；在4 - s h o c k 处，半径 达到严格的局部最大，这也就是曲线进化过程中消失成一个单点或种子点的情况。 s h o c k 和骨架的以上联系，可以整理成如下形式。记x 为一条简单闭合曲线的开 内部，m e ( x ) 表示它的骨架，b ( x ，e ) 是中心在x e x ，半径为s 的最大开圆盘，r ) 华中科技大学硕士学位论文 表示x 内部最大丌圆盘的半径。用l v ( x ，e ) = m e ( x ) n b ( x ，e ) p ) 定义一个除去中心 点x 的x 的领域。则中轴点x m e ( x ) 为： a 3 类如聚j s 0 ，使得v y v ( x ， j ，柏r 啦) r ( y ) b 3 类，如果j ，0 ，使得v y e n ( x ，g ) 。k n ( x ，) 0 ，有尺0 ) = n ( y ) c 2 类，如果3 e ，0 ，使得b e n ( x ，) ，q ，) z 咖且g ，) 1 ；连续 有r ( x ) 1 ) 个父节点，将p 复制n 个副本：p 1 ，p 2 ，r ，把只与p 的第i 个父节点相连接，同时，p i 继承p 的所有子节点，其它的p f 则设置为叶子节 点。按以上操作处理完所有这样的节点后，便可得到该环形骨架对应的骨架树。 对环状骨架的这种处理方法目前仅是一种设想和尝试，将