（计算机软件与理论专业论文）形状匹配技术在文物复原中的研究与应用.pdf

摘要 形状匹配技术在文物复原中的研究与应用 杨洛斌 西北大学计算机科学系 摘要 1 形状匹配是计算机视觉和模式识别的一个基本问题，它是衡量形状间相似性的一种技 术，在众多领域得到了广泛的应用，如文字识别、目标识别、基于内容的图像检索和医疗诊 断等。本文主要研究了形状匹配技术在文物复原中的应用。把文物碎片看作是三维曲面，就 可以把形状匹配技术应用到文物复原中，这样，形状匹配就可以用来寻找文物碎片的原有拼 接关系进而实现文物碎片的匹配。1 本文首先介绍了形状匹配的概念，然后将该技术应用到文物复原技术中。针对这一应用 的几个主要部分作了讨论和研究，提出一系列的处理算法，实现了一个计算机辅助的文物复 原系统。这些研究工作主要包括： 1 构建了一个基于形状匹配技术的碎片复原模型分析了碎片复原的计算机技术可行 性。在模型中，将碎片曲面的拼台问题转化为曲面轮廓曲线的匹配问题并且采用了适当的 算法进行曲线匹配。 2提出了一种三维曲面的轮廓曲线提取算法该算法可以适用于任意三维自由曲面的 轮廓曲线提取，算法高效稳定：同时运用高斯函数对曲线作滤波处理、重采样减少了匹配 误差。 3 提出了一种基于相似矩阵的形状匹配算法，使得匹配更加准确，适用于二维、三维 曲线的匹配。针对大量的形状匹配问题，引入了多尺度技术，提高了计算效率。 4针对碎片合并的复杂问题，提出了合并曲线作为台并曲面的轮廓曲线的方法。该方 法将侧重点转移到曲线的拼合减少了曲面合并后重新提取轮廓曲线时引起的误差。 5 在碎片拼台过程中，使用了仿真显示，也提供了交互编辑手段，使得人工参预更加 方便，保证了结果的正确性。 本文研究工作是在国家“8 6 3 ”高科技计划，咀及国家自然科学基金资助项目的支持下 完成的。 鬻篡蒙碎片复原馘轮廓峨峙重黼曲面舱曲线撼匹配 算法，多尺度技术 1 1 r _ _ 。一1 _ _ - _ - _ 。一 亘韭查兰堡主兰堡堡兰 r e s e a r c ha n d i m p l e m e n t o f s h a p em a t c h i n g o nr e c o n s t r u c t i o n o f a r c h a e o l o g i c a lf r a g m e n t s y a n g l u o b i n d e p a m n e n to f c o m p u t e r s c i e n c e ，n o r t h w e s tu n i v e r s i t yx i a l l a b s t r a c t s h a p em a t c h i n gt h a tm e a s u r e st h es i m i l a r i t yb e t w e e ns h a p e si sa p p l i e di nm a n yf i e l d s ，f o r e x a m p l e ，c h a r a c t e rr e c o g n i t i o n ，o b j e c tr e c o g n i t i o n ，i m a g er e t r i e v a lb a s e do ns h a p ea n dd i a g n o s e t h i sp a p e ra i m sa tt h er e s e a r c ho ns h a p em a t c h i n g t e c h n i q u ea n d i t sa p p l i c a t i o ni nr e c o n s t r u c t i o n o fa r c h a e o l o g i c a l f r a g m e n t s t h eu s eo fs h a p em a t c h i n gf o rr e c o n s t r u c t i o no fa r c h a e o l o g i c a l f r a g m e n t si ss t r a i g h t f o r w a r di fw e c o n s i d e rf r a g m e n t sa s3 - ds u r f a c e s i nt h i sw a y , s h a p e m a t c h i n g c a nb eu s e dt of i n dr e - a s s e m b l y r e l a t i o n s h i po f a r c h a e o l o g i c a lf r a g m e n t s f i r s t l y , s h a p em a t c h i n gt e c h n i q u ei si n t r o d u c e d a ni m p o r t a n ta p p l i c a t i o no f s h a p em a t c h i n g t e c h n i q u ei nt h er e c o n s t r u c t i o no f a r c h a e o l o g i c a lf r a g m e n t si si m p o r t e dt h e n s u r r o u n d i n g t h i s a p p l i c a t i o n ，as e r i a lo f p r o c e s s i n ga l g o r i t h m si sp r e s e n t e d ；a na p p l i c a t i o no f c o m p u t e r a i d e d r e c o n s t r u c t i o no f a r c h a e o l o g i c a lf r a g m e n t si si m p l e m e n t e d t h er e s e a r c hw o r kc a l lb ec l a s s i f i e di n t h ef o l l o w i n gr e s p e c t s ： 1 w ep r e s e n t e dar e c o n s t r u c t i o nm o d e lo f a r c h a e o l o g i c a lf r a g m e n t sb a s e do ns h a p e m a t c h i n g ， d i s c u s s e dt h ef e a s i b i l i t yo f c o m p u t e ra i d e dr e c o n s t r u c t i o nf o ra r c h a e o l o g i c a lf r a g m e n t s i nt h e m o d e l t h ef r a g m e n tr e a s s e m b l yp r o b l e mw a sc o n s i d e r e da 5f r a g m e n to u t l i n e sm a t c h i n g ；8 i i e f f i c i e n ta l g o r i t h mw a sd e s c r i b e df o rs h a p em a t c h i n g 2 a ne f f i c i e n ta l g o r i t h mf o re x t r a c t i n gi n f o r m a t i o nf r o mf r a g m e n to u t l i n e sw a si n n o v a t i v e l y p r e s e n t e d ，t h a ti sa p p l i c a b l ef o ra n y2 d o r3 ds u r f a c e ；i no r d e rt or e d u c et h ed i f f e r e n c e ，g a u s s i a n f i l t e r i n ga n dr e s a m p l ew e r ea p p l i e do n t h eo r i g i n a li n f o r m a t i o n 3 w ep r e s e n t e das h a p em a t c h i n ga l g o r i t h mb a s e ds i m i l a r i t y m a t r i x , w h i c hm a k et h e m a t c h i n g m o r ev e r a c i t ya n dc a n _ d eu s e do nt h e2 do r3 dc u r v e m a t c h i n g i n o r d e rt o a s y m p t o t i c a l l yr e d u c et h e c o s to f m a t c h i n g ，w eu s e dm u l t i p l es c a l et e c h n i q u e 4t h em e t h o dt h a tw ec o n s i d e rm e r g ec u r v ea si n f o r m a t i o ne x t r a c t e do fm e r g es u r f a c ew a s p r e s e n t e df o rt h em e r g eo ff r a g m e n t s t h i sm e t h o de m p h a s i z e sp a r t i c u l a r l yo nm e r g eo f c u r et o r e d u c et h ed i f f e r e n c et h a tb er e s u l t e de x t r a c ti n f o r m a t i o nf r o mm e r g es u r f a c e 5 i nt h ep r o c e s so fr e a s s e m b l yo ff r a g m e n t s ，w ep r o v i d e dv i r t u a ld i s p l a ya n de d i tt e c h n i q u e t oa f r o r dc o n v e n i e n c ef o rl i s e ra n de n s u r et h er e s u l t t h i sr e s e a r c hi s s u p p o r t e db yt h en a t i o n a ln a t u r a l s c i e n c ef o u n d a t i o no fc h i n aa n dt h e n a t i o n a lh i g h t e c h n o l o g yd e v e l o p m e n t 8 6 3p r o g r a mo fc h i n a t h e s ek e yw o r d s ：s h a p em a t c h i n g ，r e c o n s t r u c t i o nm o d e lo fa r c h a e o l o g i c a lf r a g m e n t s ，c o n t o u r f i l t e r i n g ，r e s a m p l e ，m e r g eo f s u r f a c e ，m e 曙eo f c u r v e ，m u l t i p l e s c a l et e c h n i q u e ：1 、 ， _ 独创性声明 y 主2 9 7 6 0 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加咀标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果也不包含为获得盘超& ) 至或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名： 均盎丛 签字目期：趟兰年_ 月上日 第一章绪论 第一章绪论 1 1 课题来源及目前背景 本课题来源于国家“8 6 3 ”高科技计划( 机器人主题) 的子项目“计算机辅 助文物复原技术研究”，以及国家自然科学基金资助项目“基于形状匹配技术的 文物复原模型研究”。 目前，国内外对于文物的维护工作，主要是文物资料的储存、交换、查找 和管理。这些仅限于方便对原有的文物作保护，使其减少再次受损失，对已经 损失的则需要通过文物复原的方式来挽回。而文物复原方面，分了很多类：文 物的色彩恢复、文物的形状复原等。 在文物的色彩恢复方面，已经有一些研究例如，西安秦始皇兵马俑博物 馆与德国巴伐利亚洲文物保护局合作开展的文物色彩保护研究。又如，敦煌莫 高窟开展的古代壁画色彩恢复方法研究，该方法以敦煌莫高窟为应用背景，基于 类比的计算机辅助古代壁画色彩恢复方法，将色彩保持相对完好的壁画图像以 及描述壁画属性的特征参数作为壁画色彩恢复的类比源存入数据库，根据决定 和影响壁画色彩的不同因素和特征参数，进行图像数据库的类比检索。为了在 处理图像过程中与人的视觉保持一致，除r g b 颜色空间外，又选择了h s i 颜色空 间结合图像色彩区域提取、基于直方图的色彩转换等技术实现了壁画图像的色 彩复原工作。 而在文物的形状复原方面，主要指的是碎片的复原，又分为基于表面色彩、 纹理、材质、轮廓等特征的碎片复原等，甚至于将文物进行数字化模型显示， 以保留文物的原始面貌，目前都处于研究阶段。例如，在日内瓦研究所进行的 文物模型动画展示：日本a s a h ig l a s sf o u n d a t i o n ，做出了可在s g i 上运行 的s i l i c o ng r a p h i c s i n v e n t o r 软件，可进行交互式辅助文物复原工作。在 巴西h e l e n ac r i s t i n a 等人对于散乱碎片的自动化拼接问题作过研究，不过是 针对于二维图像处理做的工作。土耳其安卡拉的m i d d l ee a s tt e c h n i c a l 大学 的计算机工程学院，对于散乱碎片的自动重组问题作了深入的研究。还有另外 一些大学研究所，在这方面做了一些研究工作，但均只限于对碎片的二维图像 作模式识别，以实现碎片重组。 虽然碎片复原方面有些研究工作，但是至今为止，没有较为成熟的方法应 用于实际工作中。国内外的文物碎片复原多数还采用的是手工复原方式，其复 原速度不但满足不了需要，效率极低，而且在人工试粘合复原过程中，不可避 西北大学硕士学位论文 免的会造成文物碎片再次损坏，甚至使恢复有时根本无法进行下去。而计算机 形状匹配技术的已有研究成果已经用于工业制造方面的c a d 、c a m 中，并且在这 方面得到了很大成效，这些使得计算机辅助文物复原成为可能。结合文物复原 的过程，将之与计算机辅助文物复原技术的研究相结合，这是我们提出此课题研 究的源动力之所在。 1 2 研究的需要 我国古文物在世界上占有独特的地位，是其它任何一个国家所无法比拟的， 对几千年的中华灿烂文明史的研究，其相当一部分内容来自对古代文物的挖掘 研究之中，出土文物在某种程度上能更好地反映历史的真实性，而在已经发掘 出数量巨大的古文物中，许多文物已损坏破碎，在短时期内不能复原：埋藏在 地下亟待开发的大量古文物，也面临修复和复原问题。这些珍贵的国宝无法在旅 游者面前展示他们的异彩，更加妨碍了人们对古代历史文化的研究：另外，由 于缺乏先进的科学技术而无法仿真复原、仿制，而令世人j 廉羡的古文物大规模 展示，仿古文物产品的大量销售，应该成为发展旅游产业的两个拳头。鉴于我国 悠久而丰富的历史，古文物魅力吸引着大批游客，但古文物本身尚不能成为商品 因此，仿古文物制作为替代品有着巨大的潜在市场，仿古文物产业的形成也是势 在必然，其社会效益和经济效益都是难以估量的。而对古代历史的研究，包括古 代的政治、经济、军事、文化、社会生活等，都必须建立在完整或比较完整的 出土文物基础之上。因此采用计算机辅助对古文物进行复原，不仅有利于加速 文物复原本身，而且能为仿真和仿制技术的发展提供科学模型，更重要的是能极 大地推动对中华民族灿烂文化历史的研究和人类社会演化史的研究。 多年来，对破碎文物的复原大都采用手工的方式，而现代计算机在计算机 图形学方面有其独特之处，特别是形状匹配在其它领域的研究应用已有不少成 功经验。针对破碎文物形状的特殊性，结合形状匹配技术，进行破碎文物计算 机辅助复原的研究，提供文物计算机复原模型展示，具有重要的历史意义和现实 意义。而且该研究将为文物的复原、修复、仿制提供科学依据，还可以开辟计 算机辅助文物复原的新领域。 用计算机图形学、形状匹配技术和虚拟现实技术去处理传统考古问题是有 定可行性的。首先它是在不破环碎片和不受地理位置限制的情况下，进行挖 掘、复原和展示。其次，它是根据“w h a ti f ”的模式来复原文物这种方法与 传统的手工粘贴法有着本质的区别。传统方法可能会导致不可挽回的错误，而 虚拟现实复原法可使我们有机会预览各种可能性，可以重复试拼从而减少文 物再次损坏的机率，增加了灵活性。 第一章绪论 1 3 研究的意义 计算机视觉和形状匹配技术已经开始应用于碎片复原，根据文物数字图像、 数字化形状特征的识别信息来确定文物碎片的复原。形状是对目标范围的物体 的表示，可以看成是目标的轮廓，它是用于目标识别的重要特征。 在形状匹配的许多应用中，识别一条曲线和另外的一条曲线是否具有匹配 的目的是找出两条曲线上面相似的部分，称为匹配睦线段。各种匹配方法都是 使用对曲线的抽象描述来进行匹配比较的。这种描述一般是从各种曲线中提取 的特征，特征间的相似性被解释为物体本身之间的相似性。因此，两条曲线的 匹配曲线段的识别的准确，主要决定于其特征的选择。 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 1 。但是他们的算法仅仅是研究试验，没有 真正的应用于实际工作，而且计算量比较大。 m a r kl e v o y 等人为了实现碎片复原，基于碎片图像的二维轮廓提取，研究 了二维形状匹配技术。e y a lk i s h o n 和t r e v o rh a s t i e 等人就三维曲线方面做 了深入的研究，利用s p l i n e 曲线技术来匹配空间曲线，从而达到识别、拼图的 效果 1 6 。h e l e n ac r is t i n a 和j o r g es t o l f i 在二维碎片拼合面作了很多的工 作，他提出了把多尺度技术应用在了曲面匹配过程中 1 7 ，并且对于曲线的滤 波提出了一种几何特性的滤波方式 1 4 。 碎片复原问题类似于拼图，拼图在计算机视觉和机器人智能中已经得到了 不少的实验结果。典型的有，h w o l f s o n 和g c b u r d e a 开发的一个标准的拼图 游戏 1 2 ，可以自动寻找匹配的片，甚至控制一个机器手臂来做拼接工作。但是， 这些技术都依赖于这些拼图碎片的特殊形状，侧如光滑的轮廓线和明显的拐角， 这些在文物碎片中都是几乎没有的。 这个研究工作分了很多的部分包括了匹配的前期曲线的滤波处理，后期 的曲线合并。为了得到更好的匹配结果，有许多的人在曲线滤波等其它的方面 作了不少的研究。多数人在滤波的时候都考虑了g a u s s i a n 滤波器，另外还有 h e l e n ac r i s t i n a 等提出的几何滤波方式 1 4 。还有一些考虑曲率、拐点等的 滤波方式。 从大家的研究来看，目前的具体问题还是集中在轮廓曲线的形状匹配问题 上的了，在给出的两个轮廓曲线中识别它们的相似曲线段，即匹配曲线段，从 而可以在一大堆的轮廓曲线中找到一个和模板曲线最匹配的曲线与之合并。虽 然我们可以看到很多的人都在研究，但是大多数的人都停留在二维曲线的匹配 上，很少有人对于三维曲线的匹配做研究，而对于三维曲线来讲，和二维曲线 有着很大的区别。所以，在这方面的继续研究工作是很迫切需要的。 西北大学硕士学位论文 1 4 本文研究内容 针对目前文物复原的需要，围绕这形状匹配技术和虚拟可视化技术的不断 发展，在研究了国内外的最新的成果的同时，对一些技术进行了研究与实践， 并取得了一定的进展，具体有以下几个方面： 1 ) 就形状匹配技术及其特性方面，着重讨论了概念的定义、各种不同的几何 特征向量，对已有的算法作了简要的介绍。 描述了形状匹配的基本概念的定义；形状匹配的分类。 介绍了形状表示的各种分类：编码方式、轮廓线简化方式。 简要描述了各种不同的几何特征，包括矩、f o u r i e r 描绘子、小波描述 子、形状描述子，并就其应用的各种方法作了介绍。 2 ) 针对碎片复原问题建立了一个碎片复原模型，分析了碎片复原的计算机技 术的可行性，同时也提出了物体的理想模型、实际模型。对于模型的某些 特性给出了说明。 3 ) 对文物碎片的数据获取时，采用了比较好的三维数字化仪，提出了一种对 三维曲面的轮廓曲线提取的算法，该算法对任意的三维曲面均有很好的效 果，算法高效稳定。同时，在曲线的滤波方面作了一些研究工作。 4 ) 就三维曲线的匹配技术方面，着重研究了特征的提取和形状匹配的算法。 对特征的选取，就曲线基本论作了一定的研究，选取了合适的特征描述 曲线。 详细介绍了一种较好的基于相似矩阵的形状匹配算法，对实验结果比较 满意。 将多尺度技术引入了大量的形状匹配问题中。 5 ) 提出了利用合并曲线作为合并的曲面的轮廓曲线这一方法，减少了合并碎 片再次提取轮廓曲线时候得误差，都是为了将两个已经找出来的碎片合并， 为下一步的搜索匹配曲线段做了准备。 6 ) 在整个工作处理过程中，应用了计算机可视化技术对于碎片、曲面、曲线 作了仿真的显示，使得该工作模型更加真实感。同时，也提供了交互编辑 手段，使得人工参预更加方便，保证结果的正确性。 1 5 本文组织 全文共分七章。 第一章是本文的绪论部分，着重介绍了课题的来源和背景，研究的需要、 意义，并简介了本文的研究内容。 4 第章绪论 第二章详细研究形状匹配技术，简要介绍了现有的形状匹配算法。 第三章建立了一个碎片复原的过程模型，在该模型中，对于碎片的理想模 型，实际模型作了定义，同时，对于轮廓曲线豹特性、复原目标、过程模型都 作了简要的论述。 第四章就数据的来源、轮廓曲线的提取、曲线的滤波、曲线的重采样给出 的方法说明，提出了一种很好的轮廓曲线提取算法。 第五章依据曲线的基本理论，选取了相似不变量，同时介绍了基于相似矩 阵的形状匹配算法，并对该算法的时间复杂度作了估计，同时，将多尺度技术 引入到大量的匹配问题中。 第六章指出轮廓曲线匹配处理后，对于碎片曲面、轮廓曲线作的处理工作 主要是碎片曲面的拼合显示，轮廓曲线的拼接合并。 第七章是在技术研究过程中，对于算法、理论的实践、应用。简要介绍了 系统的主要工作和系统分析、应用。 第八章最后对本文中各个技术点作的总结，同时提出了进一步发展的可能 性，指出了可以继续展开工作的方面。 西北大学硕士学位论文 第二章形状匹配技术 形状匹配是计算机视觉和模式识别的一个基本问题，经常被应用到很多领 域，例如目标识别，基于内容的图像检索，文字识别，医疗诊断等。 2 1 形状匹配的基本概念 当观察周围环境时，人们首先注意到的是物体及其周围的颜色、纹理、形 状和空间关系等等，形状是物体最基本的有感觉意义的特征之一。在计算机视 觉和模式识别中，形状是对目标范围的二值图像表示，可以看成是目标的轮廓， 它是用于目标识别的重要特征。为了节省存储空间、易于特征计算，需要对形 状作进一步的表示，这些表示通常可以分为两类：编码方式，如链码、游程码、 f r e e m a n 码等；简化方式，如样条( b 样条，3 次，5 次样条) 、插值、多项式、 多边形逼近、和特征点检测等。另外还可以使用形状的骨架来描述形状。 形状描述是通过一些方法生成数值的描述子来描述形状，描述子应该在尽 可能区别不同目标的基础上对目标的平移、旋转和尺度变化不敏感。下面列出 了一些常用的形状描述子。 1 ) 基于几何特征：紧密度、实心度、偏心率、不规则度等： 2 ) 基于统计特征：粗糙度、均值、方差等； 3 ) 变换域特征：矩、f o u r i e r 描绘子、小波描绘子、形状描绘子等； 4 ) 仿射不变量：简比等； 5 ) 射影不变量：交臂等。 形状匹配就是通过按一定的度量准则来衡量形状间的相似性。在进行形状 匹配时必须处理各种各样的形状变化。 形状匹配可以根据不同标准进行分类，如：形状匹配是基于形状的边界还 是内部。这里根据匹配方法处理形变的能力将形状匹配方法分为两大类。一类 只能处理各种变换引起的形状变化，它们通过搜索在不同变换下的不变量： 1 ) 相似不变量距离、矩、角度、圆度、f o u r i e r 描绘子： 2 ) 仿射不变量一简比、弧长、包围面积、改进型f o u r i e r 描绘子； 3 ) 透视不变量交比及其延伸。 另一类方法可以处理更加复杂的形变，它们通过寻找目标和模型之间局部 特征的对应来使得匹配误差最小。为了获得最小值，人们使用了很多方法，诸 如广义，h o u g h 变换、动态绘划，神经网络、变形模板、遗传算法、以及解析 6 第二苹形状匹配技术 方法等。 2 2 形状表示 形状表示方法分为两类，类是编码方式，一类是对轮廓的简化表示形式。 简化轮廓就是提取一些重要的有意义的关键点。当今两大最流行的曲线近似方 法是多边形近似和样条近似，另外基于多尺度的特征点提取在最近二十年中得 到了密切的关注和研究。 2 2 1 链码 链码是一种非常常见的形状表示方式，它不能简化形状，但是能有效的表 示形状，用链码表示形状是f r e e m a n 1 8 在1 9 6 1 年引入的，并且推广了原来的 定义获得了广义链码。f r e e m a n 1 9 还利用链码来抽取关键点从而生成一种相对 于平移、旋转、尺度不变的旋转表示方法，他还总结了链码的各种方法与算法。 链码在第二代图像编码中获得了广泛的应用。r o s e n f e l d 2 0 也提出了一系列关 于链码的算法。人们利用链码来计算各种不同形状特征，轮廓平滑和相关也因 此变得简单了，f i s c h l e r 2 1 用它来检测关键点，m c k e e 2 2 甚至利用链码来识别 目标。 2 2 2 样条 样条曾经在函数插值和曲线近似方面是非常流行的。样条在形状设计、表 示和恢复上有很大的应用。样条有最小化曲率的优点，也就是用最小平均曲率 的曲线近似给定的函数曲线。样条函数在插值问题上的缺点是局部函数值的修 改会影响整个样条表示。b 样条的提出就是为了不将局部函数值的改变传播到 其它间隔中去，它也可以用作由参数方程确定的平面曲线间的插值，这样每一 条参数方程都可以独立插值。c o h e n 2 3 等人提出了一种基于b 样条的曲线表示 和匹配方法。i b ma l m a d e n 研究中心q b i c 研究小组，提出了基于伪正交样 条基和最小均方误差的曲线拟合方法 2 4 。s a i n t l v l a r c 2 5 1 等人使用四次b 样条 表示形状，并且由此判断形状的对称性。h a r m uo l k k o n e n 2 6 提出了离散b 样 条l a f e r r a r i 2 7 等人实现了广义b 样条的快速算法m i c h a e lu n s e r 2 8 提出了 快速b 样条变换。 基于多项式的形状简化方法也得到了广泛的应用，很多工作使用隐多项式 来表示形状，然后用代数或几何不变量来识别形状。开始时隐多项式被用来描 述三维光滑曲面的仿射不变量。g t a u b i n 开创性的概括了关于如何利用隐多项 西北大学硕士学位论文 式提取形状特征的关键技术，当这些特征值和另一条曲线的特征值相匹配时， 就确定了一个“内蕴参考帧”，两条曲线的多项式系数可在这个参数帧下比较。 有人提出了基于二次因子的新的饮食分解的方法，从而解决了曲线之间的关键 点对应的问题。d a n i e lk e r e n 等人提出了高次隐多项式的概念，增加了隐多项式 描述复杂形状的能力。因为正交多项式不能提供平移、旋转、尺度不变量，所 以x u 2 9 等人提出了广义正交多项式，获得了相似不变量。实际上其它函数拟 合曲线的方法还有很多，例如高斯函数拟合曲线。 插值既可以简化形状，也可以增加形状的边缘点数，从而达到调整数据的 目的，插值一般可以分成如下几大类：基于f f t 的插值、最近邻插值、样条插 值、线性插值等。插值是几何学的经典理论。 2 2 3 多边形逼近 多边形逼近是用多边形线段来近似形状边缘，即：是以最小误差、最小多 边形周长、最小多边形内部面积，或最小多边形外部面积作为近似准则，这些 误差量中最常用的是最大误差和平方积分误差。这类方法中最常用的是分裂和 合并法。在这个方法中，曲线分裂由几个线段来表示知道误差达到可以接受。 同时分裂的线段又有可能融合，如果融合后的线段同原始曲线的误差在允许的 最大误差范围内，线段即融合。p a v l i d s 3 0 使用平方和误差函数的偏导数来引导 牛顿法搜索最佳断点。、u 和l e o u 提出了另一种不同的准则来获取多边形逼近， 他们使用的多边形逼近准则是最大内部面积、最小外部面积、最小面积偏差。 b e n g t s s o n 和e k l u n d n 提出了一种层次化的多边形逼近方法。分裂和并方法经常 用于多边形逼近，尺度空间的方法则经常用于跟踪曲线上的点。不随尺度变化 的特征才是稳定的形状特征。w r i t h k i n 使用多项式近似来估计边缘点上的切线 方向，从而生成了曲线的多尺度表示。c h u n g 等人开发了一种基于h o p f i e l d 神 经网络的形状多边形逼近方法。这种方法是将多边形逼近定义为对神经网络能 量函数的最小化问题，就是最小化曲线和多边形的弧与弦之间的偏差。 2 2 4 基于尺度空间特征点提取技术 基于尺度空间的特征点提取技术是一种流行的形状简化方法。最常用的尺 度空间主要有：高斯尺度空间、小波尺度空间、形态尺度空间。另外s c h w a r z 尺度空间也是值得注意的。 w i t k i n 31 1 提出的基于g a u s s i a n 尺度空间表示突出目标特征的方法，通过跟 踪不同尺度下特征点的位置而给出形状的简化形式，依然存在简化表示形式中 的特征点被认为是目标显着的特征。b a b a u d 等人证明了g a u s s i a n 核是唯一的线 第二章形状匹配技术 性核，具有非常良好的保留本征特征点的特性，当尺度增加时，即滤波器带宽 增加时，那些本征特征点依然存在。g a u s s i a n 滤波器是唯一具有这一特性的滤 波器。a s a d a 和b r a d y 基于m a n ：提出的想法提出了一种称为曲率指纹图的新方 法，轮廓经过不同带宽的g a u s s i a n 滤波器从而获得形状边缘的多尺度表示，然 后在不同尺度计算曲率并且获得曲率指纹图。m o n k h t a r i a n 和m a c k w o r t h 3 2 将 尺度空间的方法应用到形状描述子中，沿着形状的轮廓，用不同带宽的g a u s s i a i l 核来平滑轮廓，然后计算曲率，蓝率函数在尺度空间中的图像被用作形状多层 描述子，他具有平移、旋转、尺度不变性。 多尺度的概念在形态学中也提出过，基于形态学的形状简化方法主要分为 两大类，一类是形态分解，另一类是形态细化。c h e n g 和y a h 使用可变尺度的 结构基元对图像进行各种形态操作。a n e l l i 等人运用了遗传算法，并且试图解 决结构基元的选择问题。l a g a n i e r e 则成功使用形态分解提取了角点。m o i s a n 提 出的仿射形态尺度空间，并且用仿射腐蚀来简化形状。r e i n h a r d t 等人比较了形 态分解和形态细化之间的差别。相对于四种不同的代价函数，形态分解的效率 比形态细化的效率高四倍。 基于小波尺度空间的形状简化方法和高斯尺度空间的原理一样，对曲线进 行不同尺度的滤波，不同之处在于小波尺度空间不是线性尺度空间，因此它无 法保证因果性，所以经常会出现奇异的角点，因而得不到广泛的应用。 s c h w a r z 尺度空间近年来也受到了关注，虽然不是线性尺度空间，但它的卷 积和类似高斯核可阱在频域中进行操作，因而速度非常快，尤其值得一提的是 它的内在几何度量表征了不同程度的光滑度，因而在尺度的自动选取方面有其 优势的。 2 3 基于各种不变量的形状匹配方法 在几何学和拓扑理论中，给出了很多关于各种变换的结果，据此人们提出 了许多处理各种变换的不变量。 2 。3 1 基于全局性的几何特征 在经典的几何理论中，面积、周长、长轴、短轴、主轴方向、凹凸面积、 紧密度、实心度、偏心率这些特征得到了广泛的应用 5 7 】。在此简单的介绍紧 密度、实心度、偏心率。紧密度是在一定程度描述区域紧凑型的全局性形状测 度，当形状为圆时，紧密度为最小值1 。它是个旋转、尺度、平移不变量， 又是一个非矢量的数值。区域形状的偏心率定义为它的主轴和次轴的比，它区 舟不同宽度目标的能力比较强，长而窄的物体和短而宽的物体偏心率差别很大。 9 西北大学硕士学位论文 当形状有一个或多个明显的凸凹时，实心度就是一个非常有用的特征，可以刻 划一个区域的凸凹性。任意集合0 的凸壳h 就是包含集合0 的最小凸包。实 心度定义为在h 同时也在集合0 中像素的数目的比例。实心的目标和空心的目 标在实心率上差别很大。 2 3 2 基于变换域特征 人们喜欢将信号转换到变换域，分解成对于不同的频率或基来分析特征。 作为最经典的变换方法，有各种不同的矩和f o u r i e r 描绘子，小波描绘子、形状 描绘子在过去的二十年中得到了广泛的研究。 2 3 2 1 矩 图像的矩函数在模式识别、目标分类中得到了广泛的应用。h u 3 3 1 在1 9 6 1 年首先基于代数不变量引入矩不变量。通过对几何矩的非线性组合，导出了一 组对于图像平移、旋转、尺度变化不变的矩，但是这种矩不能恢复图像。t e g u e 基于正交多项式提出了用正交矩来恢复形状，并且引入z e m i k e 矩，而且可以构 建任意高阶独立的矩不变量。也有人提出了基于l e g e n d e r 多项式的l e g e n d r e 正交矩。旋转矩保证了高阶矩的幅度不随着阶数的增加而明显降低，从而把矩 的定义扩展到了任意阶。复数矩是一种获得矩不变量的简单而又直接的方法。 矩方法的优点即：它是一种简练的数学表示：缺点是要建立起高阶矩和形状特 征f 司的联系是困难的，另外它不能检测形状的局部特征。 2 3 2 2f o u r i e r 描绘子 f o u r i e r 描绘子( f d ) 是经典的形状描绘方法。早在文献 3 4 1 就已给出f o u r i e r 描绘子的详细定义，后来p e r s o n 作了改进。该方法先用累加函数表示形状边界， 然后对角累加函数进行f o u r i e r 变换，用得到的系数来描述形状，就是f o u r i e r 描绘子。在一定条件下，它具有位移、旋转、大小、起点等不变性质。用f d 可以对2 一d 曲线进行编码、重建、或者分类。它的主要优点是易于实现，并且 建立在f o u r i e r 分析的成熟理论之上：缺点是f o u r i e r 变换不提供局部形状信息， 角累加函数的表示对噪声很敏感。 2 3 2 3 小波描绘子 在很多计算机视觉应用中为了改善准确率和提高对噪声的鲁棒性经常采 用多分辨率分析方法。形状的小波表示方法在粗尺度给出形状的全局信息，在 0 第二章形状匹配技术 细尺度上给出局部信息。由于小波变换提供了多分辨率表示，因此匹配或识别 可咀根据输入图像或者目标而灵活调整。小波变换的最大缺点就是依赖于目标 曲线的起始点。也就是说，同一目标的两条不同采样曲线的小波表示可能因为 起始点的不同而又很大差异。在模式识别应用中，尽管起始点可能会引起严重 的问题，但是在任何文献中都没有完全阐述过这个问题。c h u a n g 和k u o 假定输 入图像已经经过校正，“和k u o 通过了简单的最小化曲线幅值函数的质心来获 得起始点。t i e n g 和b o l e s 使用小波系数的零交叉点来匹配模型和未知目标。他 们使用冗余小波变换，即非十进小波变换来克服对起始点的依赖。由于非十进 小波表示方法需要的计算量很大，系数的数目非常大，所以用非十进小波进行 形状匹配非常慢。在文献 3 5 中将形状先转换到机极坐标中，作f o u r i e r 变换 抽取f o u r i e r 系数，然后对f o u r i e r 系数的幅值抽取小波系数作为特征用于分类。 文献 3 6 介绍了一种判断起始点的方法，从而保证了小波变换不受起始点约 束。章旒晋教授等人研究了小波描绘子在图像查询中的应用。 2 3 2 4 形状描绘子 最近十年基于形态学的形状描述方法得到了广泛的研究。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 等使用几何相关函数( g e o m e n t r i c a lc o r r e l a f i o l lf u n c t i o n ，g c f ) 表示二维 形状。g c f 是基于形态协方差的。文献 3 7 也使用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 m s t ) 的形状描述方法。m s t 方法主要使用基于结构基元的多分辨 率形态图像处理方法。这个方法试图把多分辨率图像处理和数学形态学的优势 结合。m s t 形状表示方法把复杂的形状分解为多个简单的特征形状，然后提取 多个分解后的形状的特征，而不是原始形状的特征。分解后的形状之所以被称 为特征形状，是因为在特征分解过程中，这些特征形状保留了原始形状的信息。 文献【3 8 】给出了一种基于m s t 的形状匹配算法，并使用遗传算法来挑选一个次 优的结构基元来计算m s t 的形状描绘子。对于来自同一类的形状，这个被选中 的次优结构基元可以给出很好的分类结果。 2 4 基于局部特性的形状匹配方法 上一节主要介绍了基于全局特征进行匹配的方法，但是如果形状发生形变 或者受到遮掩，那么全局特征就变得不可靠了。为了处理更加广泛的形变问题 西北大学硕士学位论文 和遮掩问题，学者们提出了很多基于形状局部特征的形状匹配算法。这类方法 主要是通过搜索最优点对应或者特征对应来判断形状是否匹配。它们的原始雏 形就是广义h o u g h 变换，而传统的动态规划等优化算法得到了广泛的应用，现 代优化算法如神经网络、遗传算法的应用，使得许多有遮挡问题和变形问题得 到了解决。当今解决形变问题最流行的方法是变形模板。实际上形状也可看作 一维随机信号，所以在语音识别中取得成功的许多算法也被广泛地应用到了形 状匹配中，如动态时间规整、隐l h r k o v 模型、自回归模型等。形状的凹凸结构 也是决定形状的视觉特征，也受到了广泛的关注。 由于我们在项目研究过程遇到的问题都是基于各种不变量的匹配的，所以， 关于这方面的研究，在这里将不再多讲，具体可以参详文献 3 9 。 1 2 第三章碎片复原模型 第三章碎片复原模型 为了更好的讨论描述，我们将构建一个基于形状匹配的，由散乱碎片重组 复原出完整的物体的模型。该模型可以应用到报多地方，例如壁画、陶瓷艺术 品、泥塑等的复原。 3 1 碎片理想模型 碎片复原模型主要是以根据碎片边缘提取的轮廓信息为基础的。在这里， 首先需要定义两个实体模型，一个是对碎片的理想模型，另一个就是碎片的实 际模型。 碎片理想化的模型可以概括如下：假定碎片物体具有较好的光滑表面，并 且表面厚度为0 。这个表面被理想碎裂曲线分成为两个或多个的部分，即理想 碎片，理想碎裂曲线是无规则的曲线。如果两个碎片共享一段碎裂曲线，则称 它们是相邻接的，认为它们是可以拼合的。碎片同时也将原始物体的边界曲线 分割成多个小的边界曲线，如图3 1 。 图3 一l碎片的理想筷型 碎片的碎裂曲线可以看作是一个画在物体表面的图g ，我们称作碎裂网。 如图3 2 ( d ) 。三个以上的边界曲线或碎裂曲线的交叉点，作为一个理想的交 点。一个理想碎片的边界是一个理想轮廓曲线，它连接着一个或多个的碎裂曲 线和边界曲线。 如果每个碎片是一个拓扑圆盘，那么，它的轮廓曲线就是一个独立闭合环。 但是，事实上，一个碎片可能不仅只有一条轮廓曲线的( 例如，当一个带柄或 圆柱状的容器被从两头打碎) ，我们假定在碎片边缘上的每个闭合回环都是一条 碎片轮廓曲线。 西北太学硕士学位论文 碎裂网( 忽略边界曲线) 的另一层拓扑是一个碎片邻接图g + 。每个碎片“ 对应一个顶点“+ ；每个碎裂曲线p ，分离碎片“和v ，这样，g