（计算数学专业论文）非规则平面碎片匹配关键技术研究.pdf

论文题目： 专业： 硕士生： 指导教师： 非规则平面碎片匹配关键技术研究 计算数学 李星秀( 签名) 康宝生( 签名) 摘要 非规则碎片匹配复原技术是模式识别、计算机视觉等领域中的重要研究课 题，它开辟了模式识别新的应用领域，同时具有广泛的实用价值，例如在考古学、 古生物学、医学等领域得到了广泛的应用，不久的将来还会被应用到诸如机器零 件的接口技术等新的工程领域中去。本文结合图像处理、微分几何、形状匹配、 模式识别等相关理论，对平面非规则碎片匹配的几项关键技术展开研究。用碎片 轮廓曲线的不变特征量曲率描述碎片的形状，从而将碎片匹配问题转化为轮 廓曲线的匹配问题。本文的主要工作如下： 1 研究了实物碎片的数字化方法、碎片图像的轮廓提取技术及对轮廓数据 的预处理方法。针对本文研究的碎纸片，首先对碎片图像进行轮廓提取，然后对 轮廓数据进行滤波和重采样，得到适合进一步分析、匹配的数字轮廓。 2 在分析已有角点检测算法的基础上，提出种分步提取轮廓曲线角点的 算法。该算法既避免了单尺度算法只能检测出某个特定尺度下的角点特征，又克 服了多尺度算法缺乏几何直观性及在尺度参数选择上要进行多次试探的缺点。 3 鉴于已有轮廓拟合算法或计算量大( 插值) 或逼近精度低( 最小二乘逼 近) 的缺点，提出一种带约束的b 样条拟合轮廓算法。该算法通过插值角点逼 近其余数据点得到拟合曲线，更适合实际碎片轮廓的情形。实验表明算法是有效 的。 4 ，给出两种计算轮廓皓线不变特征量曲率的方法。一是基于轮廓的b 样条拟合，通过计算拟合b 样条曲线在各采样点处的曲率4 士算轮廓点的曲率； 另一是利用一点处曲率与密切圆的关系，直接估算各轮廓采样点处的曲率，算法 精度高、计算量小。 5 针对实际匹配碎片的数量众多、匹配段的起点确定困难等问题，提出基 于角点匹配引导的匹配段查找算法。算法首先基于r 0 b e na 和m i c h a c lj 【蚰】的计 算两字符串编辑距离算法，找到两待匹配轮廓的所有匹配角点，再利用陈宏吲3 9 l 的方法查找任意两相邻匹配角点间的最长公共子串，实现两碎片间匹配段的查 找。 关键词：数据采样，角点提取，曲线拟合，数字曲率，编辑距离，字符串匹配， 最长公共子串，形状匹配 m a s t e rd e g f e ed i s s e n a l i o n o nt h ei r r e g u l a rp l a n a rf r a g m e n t sm a t c h i n g u 】【i n g 蛆u ( d e p a r t m e to fm a t h e m a t i c s ，n o n h w e s tu n i v 盯s “y ，) ( i a n7 1 0 0 6 9 ) s u p e r v i s o r ： p r o f e s r 悄gb a o s h 钮g a b s t i 墨c t l e g u l a r 丘a g | i l e n t sm a t c h i n ga l l df e s t o r i n gi sa ni m p o r l a n ti s 蛐e0 fp a t t e m r e c 0 印i t i o 趾dc o m p u t e rv i s i o ne t c 1 tw i d c n st h e 印p l i c 砒i 盯e ao fp a t t e m r e c o g n i t i o n f u n h e 咖o r e ，“i so fw i d e s p r dp r a c t i c a lu s ei nm ea r c h a e o l o g y ， p a l e o n t o l o g y ，m e d i d n ee t c b a s e do nh l l a g ep r o c e s s i n 岛d i 骶呦t i a lg e o m e t 嘎 p a t t e mr e c o g n i t i o na n d s h a p em a t c h j n g ，t h i st | l e s i ss t u d i e ss o m ek e yp r o b l e m so ft l i e i e g u l a rp l a l l a r 劬g m e n t sm a t c h i n g t h e 纳g m e n t s s h a p ei sd e s c r i b e db yt h e u n c h a n g e a b l ec h a r a c t e t i s t i co fc t o u r s 蛔r d i n g l y 丘a g m e m sm a 州n gc a nb e c o i i v e n e dt oc i l r v em a t c h j n g t h er e s e a r c hw o r kc a nb es u m m a f i z e da sf o l l o w s ： 1 t h em e t h o d sa b o u tf i a g m e n t sd i g i t a l ，e x t r a c t i n g 柚dp r e - p i d o e s s i n g6 _ a g m e n t s o u u i n c sa f ei n 仃o d u c e d f o ft h es c r 印鼯o ft h ep a p e rs t u d i e di nt h el h e s i s ，t l l ei m a g c b o u n d a “e so ff r a g m 曲t sa r ef i r s te x t r a c t e d ，姐dt h e nt h ec o n t o u r sa r ef i l t e f e da n d r e s a m p l e 2 o nt h eb a s i so fa | l a l y z i n gl h ep r c v j o u sa l g o r i t h m so fc o m e rd e t c c t i o n ，as t a g e d m e t h o do fd e t c c t i n gc o m e rp o i n t so fc o n t o u r sj sp r c s e n t e d t 1 l em e t h d d0 v e r c o m e st h e s h o n c o m i n go fs i n g l c s c a l et e c h j q u ew h i c hc a no n l yd e t e c tf e a t u r ep o i n t so ns o m e s p e c i a ls c a l ea n do ft h em u l t i s c a l ea l g o r i t h mw h i c hl a c k sg e o m c t t i cv i s i b i l i t ya n d n e e d ss e l e c t i o no ft h es c a l ep a r a i n e t e 3 d u et ot h a tt h ei n t e r p o l a t i n gm e l h o d sh a v el a r g ec a l c u l a t i n gq u a n t “y ，a n dt h e p r e c i s i o no ft h el e a s t - s q u a r em e t h o d sj sc o m p a f a t i v e l yl o w ，a na l g o r i t h mf i t t i n gt h e t t t c o n t o u rw i t hc o n s t r a i n e db - s p l j n ec u l v ej sp r e s e n t e d t h e 矗t t i n gc u r v ei n t e r p o l a t e s t h ec o f n e f sa n da p p r o x i m a t e so t h c rp o i n t si nm e s e n s eo fl e a s t s q u a r e 1 飞e 强a i i l p k s i n d i c a t em ea 1 9 0 r j t h mi se f f c c t i v e 4 粕om c t h o d so fc o m p u t i n gd i 9 c f e t e 咖v a t u r e 锄p r e n t e d o n ei sb a s e d o n t h eb - s p l i 酩舶i n gt ot h cc o n t o u f s ；t h eo t 栅c o m p u t e st h ec l l r v a t w ed i f 嘣l yt a k i n g a d v a n t a g co ft h er e l a t i o no fc i l r v a t u r ca do s c u l a t i n gc i r d e n ea 1 9 0 f i t h mi se a s ya n d v e r yp r e c i s e 5 af f a g m p n tm a i c h 协ga i g o f i t h m sg - v c n f i f s t ，a l lm a t c h i n gc o m c rp o i n t s b e 俩e c nt w 0 行a 舯c n t sa r ed e t e c t c db yc o m p u t i n gt h ee d i t d i s t a n c co ft l l et w o c u f v a t u r es t r i l l 黟w i t hl h em e t h o df r o mr o b e r ta a n d 施c h 醒l j i 蛐】1 1 1 e nd e t e c tt h e l o n g e s tc o m m o ns u b - s t f i n gb e t w e e n 蛐yt w oa d j o i l l i n g c o m e rp o i n t sw i t hc l l e n h o n g m i n g s 1 3 9 lm e t l l o d k e yw o r d s ：d a t as a m p l c ，c o m e rd e t e c t i o n ，c u ef i t t i l l g d i g i t a l c u n r a t u r c ，e d i t d i s t a n c e ，s t d n gm a l c h i n g ， t h el o n g e s tc o m m o ns u b s t r i g ，s h 印e m a t c h i n g l v 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名：瑾逞查指导教师签名 稗犹 哥以年6 月弓日1 和f 年石月岁日 西北大学掌位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名： 年月 日 第一章绪论 1 1 研究背景、意义 如果不小心把一张纸币撕坏了，我们可以很容易用手工把它们拼接复原，这 是因为纸币碎片的数量很少，且我们对纸币的形状、色彩及纹理都很熟悉。然而， 在考古研究方面有许多出土文物碎片包括陶器、瓷器、石器、人及动植物的骨 骼和化石碎片等，它们的整理和修复耗费了考古研究者大量的时间和精力，更有 许多极其珍贵的考古碎片由于数量较大、相互混杂，依靠简单的人工测量和比对 无法完成这样的整理和修复。典型的是秦始皇兵马俑的破碎复原问题，成千上万 的兵马俑，历经战火与年代的磨难，成为断臂缺肢的瓦砾，人工复原数量大，周 期长。从挖掘至今，历时3 0 余年，复原不过十之一二，而且容易对文物造成二 次损伤。碎片的拼接复原问题不仅在文物复原领域中存在，在其它领域中也遇到 了类似的问题，如：公安机关破案系统中的碎照片识别拼接，破碎的珍贵艺术品 的还原，破碎的古纸钱币、古壁画的还原等。 随着计算机技术的发展，利用计算机进行碎片复原成为可能。事实上，从上 世纪7 0 年代开始，考古学家就利用计算机对文物碎片按色彩、纹理、材质、形 状等进行分组归类。此后，计算机视觉和图像处理技术就被用于自动提取碎片图 像的索引特征l 】。但在这些研究中，计算机处理并不能完全地代替手工拼接， 只是缩小了伪候选匹配的数量，使手工匹配变得更容易。然而对于大量的碎片， 即便使用这些方法仍然会有许多伪候选匹配存在。因此，只有用计算机实现碎片 的自动拼合，才能真j 下将人们从繁琐的手工拼接中解脱出来。 从理论上来讲，碎片复原技术的核心问题是碎片匹配拼接问题，它属于模式 识别的范畴，但越出了传统模板匹配的界限。一般的模板匹配都有标准的模板库， 把需要识别的物体与模板库中的标准模板进行比较，其中最匹配的就定为被匹配 物体的模板。如胡红俊的指纹识别1 5 j 刘斌的血液细胞的识别f 6 i ，m i c h lb o s h f a 的模式重认1 7 】，陶亮的人脸识别【8 l 等。而解决碎片匹配问题时，没有一个固定的 标准的模板，任何一片碎片都可以作为模板。因此，碎片的匹配拼接是模式谈别 技术的一个新的拓展， 非规则碎片的匹配是学术研究的前沿问题，对其进行研究将开辟模式识别新 的应用领域，促进模式识别方法的发展。同时，在不久的将来会应用到新的工程 领域中去，比如说机器零件的接几技术。因此，从现实与理论的角度来看，本文 的研究工作都具有重要的意义。 1 2 碎片匹配复原概述 碎片匹配属于图形匹配的范畴，图形匹配是通过客观存在的物理碎片的图 形、图像及其他属性信息的采集、分析和建档，建立具有多维信息模型的计算机 表示，运用一定的匹配算法完成对图形的匹配。它综合利用了图形算法、图像技 术、三维图形与图像数据库技术，以及模式识别与匹配理论等，研究一种基于特 征分析和内容查找的自动拼合技术。常见的是类似七巧板的拼合，是由若干平面 多边形拼合而成；另有一些还在每个子片上配有图画，游戏者除了要寻找各子片 边界的完全匹配之外，还必须使拼合在一起的七巧板形成整体协调的画面。当子 片数目较大，各片上的图案差异不很明显的情况下，完成这样的七巧板拼合是有 一定难度的。如果七巧板的子片不是简单的平面多边形，而是具有任意的空间几 何形状、任意的空间边界曲线，以及具有色彩、纹理、材料、厚度等多种其它属 性，则这一问题就更加具有挑战性。 碎片匹配复原可以分为许多类。如，按碎片特征可分为基于色彩【9 】、纹理、 材质、轮廓形状等特征的碎片匹配复原；按目标可分为有目标和无目标的匹配复 原；按形状特征可分为规则碎片和不规则碎片的匹配复原；按空间可以分为二维 和三维碎片的匹配复原；此外，还包含夹杂噪声和碎片残缺的匹配复原等。 形状是物体最基本的有视觉意义的特征之一，在计算机视觉和模式识别中， 形状是对目标范围的二值图像表示，可以看成是目标的轮廓，它是目标识别的重 要特征。将形状特征运用到碎片复原研究中，主要是根据碎片的轮廓曲线的识别 信息来确定碎片的匹配关系。为了节省存储空间、易于特征计算，需要对碎片的 轮廓形状作进一步的表示和描述。形状表示方法一般有编码方式和对轮廓的简化 表示形式两类，另外基于多尺度的特征点提取在近二十年中得到了密切的关注和 研究。有关形状表示的具体内容，我们将在第四章中予以详细介绍。 形状描述是基于形状的表示方式，通过一些方法生成数值的描述子来描述形 状。描述子应在尽可能区别不同目标的基础上对目标的平移、旋转和尺度变化不 敏感。这种描述一般是从曲线中提取的特征量，特征间的相似性可以表示碎片本 身的相似性，通过比较特征量的相似程度来判断碎片之间的匹配程度。下面是一 些常用的形状描述子： 1 ) 基于几何特征：紧密度、实心度、偏心率、不规则度等； 2 ) 基于统计特征：粗糙度、均值、方差等： 3 ) 变换域特征： 4 ) 仿射不变量： 5 ) 射影不变量： 6 ) 几何不变量： 矩、f o u r i e r 描述子、小波描述子、形态描述子等 定比等； 交比等； 曲率、挠率等。 获得了形状的特征描述，就可按一定的度量准则来衡量形状间的相似性，完 成形状匹配。形状匹配一般可为全局匹配和局部匹配两种情形，如果要检验目标 物体a 是否与目标物体b 在形状上相同或者相似，则需进行全局匹配，如谢萍 等的一种快速复杂多边形匹配算法l 加】。这时对于两个物体的任何一个对应的局 部而言，都应具有相同的几何特性。当然，这两个物体也有可能只有局部相同或 者相似，这种即称为局部匹配。如林增剐等的基于不变特征量的空间三维曲线匹 配【1 1 j 。如果进行全局匹配，则对目标物体采用全局类型的描述方式较为合适，因 为这样可以使用较简单的方式快速地计算两个目标物体是否( 全局) 匹配，但全 局描述往往会降低对目标局部特征的表示。一般而言，局部描述可以更大程度上 地增强对目标局部特征的表示，其缺点是有大量的局部细节需要记录、描述、计 算。如果两个相似目标物体可用全局描述方式判定其完全相同或相似的话，那么 局部描述一定也可以实现这样的判定。反之，两个局部相似的目标物体可用局部 描述子实现判定，而全局描述则不一定。采用怎样的形状表示方法和描述方式还 要依据具体应用而定。本文主要研究的是基于瞌率表示的非规则平面碎片的局部 匹配问题。 由于非规则碎片的匹配难度比较大，不能从整体上把碎片一步匹配完毕，而 只能把一块碎片的一部分与另一块碎片的一部分相匹配。因此，要解决这个问题 需要一系列相关技术的支撑，包括：数据来源、边界检测技术、边界表示方法、 边界描述方法、特征点检测技术、匹配技术，以及在这个过程中要用到的计算机 相关技术：包括开发平台和数据库技术等。其中特征点检测技术、边界表示方法、 边界描述方法和匹配技术是难度比较大的关键技术，本文围绕这些技术问题而展 开。 1 3 国内外研究现状 近几十年来，国内外学者在碎片匹配方面作了丰富细致的研究，我们从以下 几个方面加以介绍： ( 1 ) 形状表示与分析 s k l a n s k y 通过最小多边形周长决定轮廓多边形的顶点；s k l a n s k v 和 g o n z a l e z 提出了个快速的扫描算法，分段线性逼近到平面数字曲线，目标函 数为从轮廓线上的点到多边形边上的最大距离最小：张习文等【1 4 j 提出了基于遗 传算法的以线段和圆弧为基元的曲线拟合方法；s h i n n y i n gh o 等人f 1 5 1 提出了一 种有效地基于遗传算法的多边形精确逼近算法；dam i t z j a s 等人提出了一种 基于神经网络的多边形快速逼近技术用于形状识别；b i m a lk u m a rr a v 等人【1 7 j 利 用l 范数决定数字f f l 线的最佳逼近多边形；m a h e ra l k h a i v a t 等人【1 8 1 提出一种 运用同心圆来表示平面曲线的技术。 w i t k i n 【1 9 1 提出的基于g 踟s s 尺度空问表示突出目标特征的方法，通过跟踪不 同尺度下特征点的位置而给出形状的简化形式，依然存在于简化表示形式中的特 征点被认为是目标显著的特征；b a b a u d 等人证明了g a u 姻核是惟一的线性核， 具有非常良好的保留本征特征点的特性。当尺度增加时，即滤波器带宽增加时， 那些本征特征点依然存在；g a u s s 滤波器是惟一具有这一特性的滤波器。a s a d a 和b m d v l 2 1 】提出了一种称为曲率指纹图的新方法，通过对轮廓用不同带宽的 g a u s s 滤波器滤波，获得形状边缘的多尺度表示，然后计算各尺度上轮廓的曲率 从而获得曲率指纹图；m o k h t a f i a n 和m 咖n h l 2 2 l 将尺度空间的方法应用到形 状描述子中，沿着形状的轮廓，用不同带宽的g 叫s s 核来平滑轮廓，然后计算曲 率。曲率函数在尺度空间中的图像被用作形状多层描述子，它具有平移、旋转、 伸缩不变性。 ( 2 ) 特征点的检测 k w 柚g l l o o ns 0 1 l 吲基于曲率估计的角点检测技术首先介绍了几种前人的曲 率估计算法，然后介绍了一个对噪声的平滑算法，最后介绍了角点提取算法。角 点的提取分为两种情况：一种是经过卷积仍然保持角点特征的，一种是尖点的提 取，两种角点共用3 个门限值分阶段进行提取。 pr e c h e f 2 4 j 基于轮廓上局部向量的角点提取方法的主要思想是，根据弧长与 对应弦长的差值，在每个轮廓点的左侧和右侧分别寻找最长的弧长，直到该差值 大于某个阈值为止，轮廓点和它的左右两个弧长最长的对应点形成两个向量，以 这两个向量为基础估计每个轮廓点曲率，然后把基于曲率估计得到的尖点和极值 点作为角点。该方法的优点是在同类算法中比较稳定。总体来讲，这是一种典型 的计算边界曲线切向不连续性的方法，但这类检测角点算法建立在边界切向的剧 烈改变的基础上，它们忽视了边界的形状，而边界的形状比切向的不连续更重要。 因此，这些算法或者检测到假角点，或者遗失了应该检测到的角点。另一方面， 这个算法的计算量并不比多尺度算法的计算量少。 l i y u a nl i l 2 5 j 使用模糊推理的平面曲线角点提取算法的主要思想是从人类认 识局部几何图形出发，建立角点的模糊模型集合，然后确定曲线上的极值点，通 过模糊推理的三个阶段：估计、分类、确定位置来提取角点。 a r a t t a r a n g s i i 驯从人类视觉认识出发提取角点。在分类的时候引入了模式识 别的语义识别方法，这种算法比较注重于细节，也容易理解。与一般的单尺度算 法相比，其稳定性和适应性较好，细小的角点的提取比较好，且具有一定的抗噪 声能力，不过忽略了粗的轮廓特征。 d a n e at e f c r a 【”l 角点检测的，l 何方法原理是把角点作为两条以上直线的或 并曲线的交点，通过曲线段与物体质心的关系和曲线段与角点的关系得到一个角 点的递推关系式，然后用迭代算法使角点线性收敛于某个点。这是一个比较具有 理论意义的算法，实践中由于在求取角点的过程中要采用一系列近似方法，并且 最后收敛的数据点也极可髓是一个近似点，因此该算法在实际可操作性方面存在 问题。此外，依靠迭代算法得到的角点的位置肯定存在误差。 王展f 2 8 j 利用小波变换结果的局部极大值信息检测和定位图像的角点。 彭晓明【冽在一种基于小波变换的多尺度角点提取方法中，利用在几个尺度上 小波变换模极大值和曲率理论提取角点。 f a r z i nm 0 1 d l t 盯i a l l 【3 0 1 的图像角点提取算法是基于曲率尺度空间的表示方法， 把绝对曲率的极大值作为图像的角点。在一个粗的曲率尺度空间检测角点，在一 个细的曲率尺度空间提高角点的具体位置的准确性。 ( 3 ) 曲线匹配 张文景等人i 3 1 】提出将h a u s d o r f f 距离作为物体轮廓相似性的测度，并用遗传 算法进行最佳形状匹配的快速搜索。 谢萍等人【1 0 l 提出了一种能够快速进行复杂形状多边形匹配的算法。该算法 基于正切空间表示，先对复杂多边形进行离散曲线演化，再将得到的简化多边形 分为一系列最大凸凹弧线，并选择每段最大凸弧线的起点作为匹配的起始点进 行匹配。 y i n gs h 如等【3 2 】提出了一种概率框架的曲线匹配算法，根据特征点间的相似 性和特征点与邻域的距离得到初始概率，然后不断的迭代，直到特征点的概率达 到稳定值。 k i t a o 等【3 3 】采用动态规划的方法计算边界轮廓中的不匹配对，根据b a y e s 分 析确定了一个临界判别条件。经过该算法获得的匹配对的数量比真实存在的匹配 对数量少了很多，因此虽然初步实现了匹配对的查找，但是可靠性依然有待提高。 g 0 k t u r ku c o l u k 和ih a l 【i 【jt o r o s l u l 3 4 j 采用一种穷举搜索的方法解决碎片轮廓 线的最优匹配问题，主要研究了最优匹配的查找问题，且计算量比较大。 吕科等1 3 5 l 提出了基于f o u r i e r 变换的曲线匹配算法，通过比较两条曲线的 h a s h 矢量来分析曲线段的相似度。从理论上给出了判断曲线匹配的性质，如果 曲线段之间的距离越小则h a s h 矢量之问的距离也越小。 hjw o i f s o n 等【3 6 】研究了平面曲线匹配的问题，提出了将曲线形状转化到信 号域，运用串匹配的技术查询最长匹配子串，从丽实现曲线的匹配。该方法主要 用于解决复杂场景中重叠物体的识别和定位问题。 sng a n e b n i k h 等 3 7 】使用信息传输理论的堆算法对数字化的碎片进行快速分 类和分群，这种方法使用字典式的参考模式来识别输入模式，而且强调快速搜索 弓输入模式相似的参考模式：同时，这种方法可以用来处理平面碎片的分类问题。 周石林i 3 驯提出了一种基于角点特征匹配的非规则碎片匹配的方法，该方法 通过提取平面非规则曲线的角点，匹配角点来寻找初始匹配点，同时利用对应点 的曲率相等或者等价的几何特性来匹配平面非规则曲线。该匹配算法的稳定性取 决于角点提取位置的准确性和角点曲率计算的精确性。 从国内外研究现状来看，在碎片匹配复原技术的研究中已经取得了一定的成 果，但其中也存在很多改进的方面，如：一些关于角点检测的研究，存在角点检 测不完全，丢失重要角点的问题，或是算法缺乏几何直观性；在舞片轮廓的b 样条拟合研究中，没有针对碎片数据的特殊性提出相适应的算法：关于数字曲线 曲率的计算精度问题，也始终没有得到很好的解决；另外，由于碎片的数量成千 上万，如何设计快速的匹配算法也不容忽视。因此。本文从这些方面入手，研究 解决了碎片匹配复原问题中的几个关键技术。 1 4 论文的内容与安排 本文的研究工作主要针对以下凡个闻题展开： 1 碎片轮廓曲线特征点的提取； 2 轮廓曲线的b 样条拟合： 3 特征不变量的选取与计算； 4 碎片匹配算法的设计。 全文的内容安排如下： 第一章绪论介绍了论文研究的背景、意义以及碎片匹配复原技术的基本知 识，分析了国内外的研究现状，并对本文的研究内容予以安排， 第二章数据的采集和预处理主要研究了碎片的数字化方法、图像边界的提 取技术及边界数据的滤波、重采样方法。针对本文研究的具体情形，采用相适应 的方法进行处理。 第三章轮廓角点的提取简要介绍了角点检测技术，分析了角点检测的研究 现状。在此基础上提出一种轮廓曲线角点的分步提取算法，即先提取轮廓的尖锐 角点，再分段提取其它角点。最后对算法进行了实现和分析。 第四章轮廓曲线的b 样条拟合对形状表示的各种方法进行了研究，分析 了轮廓b 样条拟合的各种方法，提出了带约束的轮廓点集b 样条拟合算法，并 对算法进行了实现和分析。 第五章轮廓曲线数字曲率的计算就已有的数字曲线曲率计算方法进行了 分析，在平面曲线基本理论研究的基础上，给出适合本文研究问题的两种数字曲 率计算方法，对算法进行了实现和分析。 第六章平面碎片的匹配理论与技术在对非规则碎片复原的模型和相关问 题进行分析，及对碎片匹配需要遵从的准贼进行探讨的基础上，给出基r 字符串 匹配的非规则碎片匹配算法。 第七章总结与展望对论文研究的内容进行了总结，并对今后可能开展的研 究工作加以展望。 论文的内容与结构关系如图1 1 所示： 图1 1 论文的结构 第二章数据的采集和处理 2 1 碎片的数字化 碎片的匹配拼接是以实物碎片为参考依据进行的，建立描述实物的计算机模 型是碎片匹配拼接的关键技术之一，因此首先需要对实物碎片进行数字化。 实物数字化是通过特定的测量设备和测量方法获取实物表面的数据，如果仅 需碎片的色彩、材质等特征，可以用照相、摄影等技术得到，但实际情况中往往 需要碎片的空间几何数据。对于一些平面物体，诸如纸片、壁画、油画等，直接 用平面扫描仪扫描后经相应地处理便可获得，而另外一些非平面的物体，例如陶 瓷、瓦罐、兵马俑等的碎片，它们数据的获取就比较麻烦了。最早的时候，通过 对物体多角度照相，获得多角度的图像，然后利用立体感视觉技术得到物体的曲 面数据模型。三维数字照相是9 0 年代初期开始发展起来的测量手段，主要适合 于三维自由表面的测量，可以在几秒钟内测量得到百万以上的数据点，也可以直 接输出三角网格模型，而且有些产品能够自动完成多视测量的数据集拼合，从而 输出一个整体的点云形式或三角网格形式的数字化样件。 现在的三维数字化手段多是采用三维数字化仪来实现，根据测量探头或传感 器是否和实物接触，分为接触式和非接触式两大类，见表2 1 f 3 9 】。其中，三坐标 测量机( c m m ) 和激光扫描测量是广泛采用的两种测量方法。c m m 测量通用 性强、测量范围大、精度高，可手动测量和编程规划扫描路径进行点位测量，适 合于具有复杂内部型腔的工件和几何复杂的外形曲面测量，以及复杂边界、特征 棱线的测量。但总体上，三坐标机测量速度慢，工作量大，测量精度受环境温度、 噪声等的影响，数据还需进行测头半径补偿。激光测量是最近发展起来的测量技 术，其速度快，精度较高，应用比较广泛。 裹2 1 数据获取方法 本文研究的是碎纸片的匹配问题，数据的采集是利用平面扫描仪对碎纸片扫 描得到的。 2 2 碎片的轮廓提取 得到碎片的图像信息后，我们需对碎片进行轮廓提取，也就是要提取碎片图 像的边界线。所谓图像的边界线就是其周围的像素灰度发生或阶跃变化或屋顶变 化或钉子变化的那些像素的集合。任何物体都是有边界线的，因此它是图像的一 个重要特征。 由于边界是认识目标物体最关键的因素之一，计算机视觉中的许多图像处理 和图像分析问题，如模式识别、模式匹配、三维重建、纹理分析、图像分割等都 必须以边界为基础。在本文的平面非规则边界匹配问题中，第一步就需要碎片的 边界数据，因此提取图像的边界具有重大的意义。本节我们首先介绍三种边界模 型及几种常用的边界检测方法。 图像边界两边的灰度级别截然不一样，理想的边界模型有三种：阶跃模型、 屋顶模型、钉子模型i 柏l ，如图2 ，1 。阶跃边界指边界两边的像素值有着显著的不 同：屋顶边界是指它位于图像的灰度值从增加到减少的变化的转折点；而钉子模 型边界是指边界两边的灰度值差不多，在边界处灰度突然增大。 阶跃模型 屋顶模型 钉子模型 图2 1 边界灰度变化模型 常用的边界检测算子主要有r o b e n s 算予、s o b e l 算子、p 陀w i l t 算子、r s c h 算子、g a u s s l a p l a c c 算子、m a r r 算子、f f e i 和c h e n 算子及jc a n n y 算子。在 此，我们一一进行简单的介绍。 r 0 b e r b 算子 r o b e n s 边缘检测算子是一种利用局部差分算子寻找边缘的算子。它由下式 给出： g o ，y ) t f f 而两一打丙i 而可】2 + f 打耳西i 一仃两丽】2 t ，z ( 2 1 ) 其中倚，) ，) 是具有整数像素坐标的输入图像，平方根运算使该处理类似于在人类 视觉系统中发生过程。 s o b e i 算子 下面所示的两个卷积核形成了s o b e l 边缘算子，图像中的每个点都与这两 个核做卷积，一个核通常刈垂直边缘影响最大，而另个对水平边缘影响最犬。 肾卅 眩2 ， 州 眨。， ( 三立三 j 【；i 立三】，【；i ! 卦【三i ； 。：舢 【孑；孑】， 亨；卦匡! ；萝【三三三】 g a 哪s h p l a c e 算子 算子如下所示。l a p l a c e 算子是一个二阶导数，它将在边缘处产生一个陡峭的零 二i ： ， 三i 三；：】 c 2 - s ， 1 9 8 0 年，m a r f 和h i l d r e t h 把g a u s s 函数和l a p l a c e 变换结合起来作为对图 黼( ”) l ( 蔷+ 斋) 去e x p ( 一芋) ( 2 6 ) l o 初步结果再进行l 砷l a c e 卷积。当图像的边缘不是呈局部线性变化现象的时候， m a r r 函数检测效果不好。另外，该函数将梯度的局部极大和极小值点都作为图 像的边缘，然而，实际上只有局部的极大值点才是边缘线。因此，把一些非边 界点当作了边界点，还有一点，m a f r 算子对噪声非常敏感。 b 专卦【i 蚤】， 一羔言荨】 善罩一蔓 【 】，【；i 三】 c z 7 ， ! 】， ! 习，i i i 厂。至】 眩s ， g = c o s ( 2 9 ) 其中：6 - c ；了觑c f 。 _ 然后把g 与门限值比较，当g 小于门限值时，该中心点为边缘点，否则不 是。 j c a n y 算子 jc a n n y 边界检测是最重要的边界检测方法。对图像进行边界检测需要减 少数据的数量，过滤掉无用的信息，同时保留图像中的重要特性。c a n n y 边界 检测用三个准则提高了边界检测方法的性能：第一个是低错误率；第：个是边 界点的定位要准确，也就是边界像素点和和实际边界点的距离是最短；第三个 是对同一条边界检测出来的边界线只有一个，这个准则存在的原因是上面两条 不能保证对同一边界不产生多条边界线。 c a 加v 边界检测的主要思想是用g a u s s 掩模平滑图像并且消除噪声，计算 图像区域的灰度函数梯度，并且找到区域中梯度的最大值，然后跟踪这些区域 抑制其中的非最大值，剩下的梯度数组减少了。在确定边界方向以后，在边界 跟踪过程中用到两个门限值。在跟踪过程中，如果某点梯度比最小的门限值小， 那么把该点的梯度设为零；如果某点的梯度大于最大的门限值，那么把这个点 令为边界点；如果在两个门限值之间，除非该点在两个边界点之间，否则，该 点的梯度值为零。 c a 肋y 边界检测成功地运用了g 髓稿掩模平滑图像噪声的功能。并且继承 了前人的根据梯度检测灰度突变的方法，运用边界元素的方向检测边界和跟踪 图像，运用门限值排除非边界点，同时消除断点。鉴于c 锄n y 算子的这些优点， 我们运用c 细n y 检测算子来提取碎片的边界轮廓。图2 2 为我们对碎片图像用 c 锄n y 算子提取边界并进行轮廓跟踪后得到轮廓图。 e d g q 矾攀 e d g 忡 e 姆嘲 图2 2 碎片轮廓图 2 3 碎片轮廓数据处理 通常由于各种因素的影响，如物理的因素( 小的碎片的丢失、磨损、边缘的 腐蚀以及表面的不规则) ，仪器的因素( 视觉、阴影、图像的量化) 等，由采样 点组成的碎片数字轮廓线会存在各种误差。如不消除，这些误差数据将会直接影 响重建模型的质量，从而影响匹配。因此在模型重建之前，需要对数字曲线进行 滤波等处理，以达到简化和光顺数据的效果。 2 3 1 去除噪音 数字轮廓线中包含各种不理想的数据。对错误的数据，可用交互处理的方法 进行去除：对于误差数据，大体可分为毛刺数据和噪音两种。对于毛刺数据，可 以直接删除，或将其移到一个中值点，也可以将其沿某一方向移动一段距离。 直接针对数据点的滤波方法很多f 钮，本文实现的有序数据的滤波与数据的 组织形式无关，主要基于“邻近的建立p 9 】。滤波后的数据点的新点可用矢量表 示为： b 一= 只埘+ 扣僻“) ( 2 。1 0 ) 其中，d ( p ) 为所调整的距离向量，d 为调整的步长参数。 过待滤波的数据点p 作切线，一为轮廓在p 点处的法向量，则七邻近点集 x - 假，p 2 ，只) 中的数据点鼻到此切线的有向距离为两蓐。通过对有向距离 两一的滤波，可实现数据点p 的滤波。滤波器的阶可取不大于七的整数。 ( 1 ) 平均滤波 平均滤波也叫均值滤波，是一种简单的线性滤波。一次滤波后，数据点p 的法矢取为点集盖的数据点的法矢的平均值；相应地，式( 2 1 0 ) 中的有向距离 向量d 可取为： d 睁畴善厦帅 2 1 1 ) 实际计算中，采用取均值的方法进行简化。值得注意的是：当七的取值很大 时，均值滤波会使数据趋于平坦，丢失匹配的信息，但可以通过调整d 的取值， 在细节保留与滤波效果之间达到平衡。 ( 2 ) 中值滤波 中值滤波也是一种简单的线性滤波f 4 3 】。与均值滤波相比，此时新的法矢取 为点集丑+ 研的数据点的法矢的中间值，式( 2 1 0 ) 中的有向距离向量d ( p ) 取 为点集中的数据点只到切线的有向距离两一的一个中间值： d ( p ) = ( 哩p ( 鹧h ) ) n ( 2 1 2 ) 法矢的中间值通过点集j + p 中数据点的法矢与数据点p 法矢的夹角来 实现，取为与央角的l 】削值相对应的点集x 中的数据点的法矢。当数据点的法 矢为正则化的单位法矢时，法矢之间的夹角可等价地转化为法矢差的模来实现。 由于最大和最小值都不会被选中，因而中值滤波能有效的去除毛刺数据以及大幅 值噪声数据的影响，能很好地保持模型的细节特征。 g a u s s 滤波是一种加权的线性滤波，其权值是由g 卸s s 分布函数得到的权值 烈“州一生挚m e 唰一争 ( 2 1 3 ) 饥去稍巾z 司 眨 由连续g a u s s 分布求离散模板，需经采样、量化和模板归一化等操作，由于 阶数m - 2 x 幻2 + 1 的一维g 硼蟠滤波器的未归一化模板正好为杨辉三角形分布， 啬【! 】 ( 2 1 5 ) 如1 6 阶g a u s s 滤波器为q - 去【l 51 01 05 1 】，据此也不难得出6 6 阶g a u s s 滤波器6 g - q 7 q 。 具体滤波时，根据用户交互选择的滤波器阶数mt t ，生成1 m 阶g a u s s 滤 波器，由于点集z 中的数据点只是按到数据点p 的距离从小到大排序的( 将这 些距离值视为g a u s s 函数中的y2 ，按照离数据点p 远的数据点分配较小的g a u s s 权值的原则，对石+ p ) 中的前m 个数据点的法矢进行g a u s s 加权求和，即为滤 波后数据点p 的法矢开。同样，可对这州个数据点到切线的距离进行g a u s s 加权 求和，便能得到式( 2 1 0 ) 中的调整距离向量d c p ) 。 g a u s s 滤波能避免平均滤波的缺点，较好地消除噪声数据的影响，同时它的 滤波阶数也为重新采样提供了统一的步长( 见n y q u i s t 采样) ，所以本文采用 图2 3 是滤波前后的轮廓。 图2 3 滤波前后的数字轮廓 2 3 2 重采样 在保证图形不失真的情况下，为了简化计算，提高运算速度，滤波后要重新 进行采样，采样的方法有以下几种。 1 均匀采样法 均匀采样法是根据数据点的存储顺序，每隔掰一1 个数据点取个数据点， 其它的数据点都被忽略，这里的小称为采样问隔( 或采样率) 。 当均匀采样法应用于有序数据( 如扫描线数据) 时，便成为等间距采样法； 而应用于非有序数据时，由于数据排列的无规律性模拟了均匀采样的随机性，因 而成为随机采样法。对于稠密的数字化样件，均匀采样法是一种常用的快速简化 方法，在本文中可以采用。 2 弦偏离采样法 弦偏离采样法有两个控制参数；极限弦偏离值j 和最大弦长工。此方法的采 样过程为，在最大弦长l 内，所有弦偏离小于s 的数据点都被忽略，换句话说， 只有达到最大弦长的数据点或弦偏离值不小于s 的数据点才会被采样到。 实际上，若用累积弧长代替上述算法中的弦长参数，在数据抖动大的地方， 采样率提高，能采相对多的点，这对于后续的轮廓匹配是有益的。因而，对于数 据质量本来就不是很高的数字化样件，这种处理方式更有效，可用于毛刺较多的 场合。 3 卜y q u i s t 采样 滤波以后所要进行重新采样，根据n y q u i s t 频普特性m l ，即要从抽样信号中 无失真的恢复原信号，采样频率应大于2 倍信号最高频率，即n y q u i s t 采样频率 为信号最高频率的两倍。工程上的采样频率一般为n y q u i s t 采样频率的2 。3 倍。 设轮廓的长度为l ，有魄个采样点，轮廓的滤波阶数是a ，经过g a u s s i a n 滤波后 的最高频率为 4 【4 5 】，则 驴击x 2 。半 ( 2 1 6 ) ， 上式可以写成 ( 2 1 7 ) 所以采样步长d 为 扣告。酽 眩1 8 ) 由此可以看出，各轮廓的采样点如的范围可能各不相同，采样点的步长可 以用这个特性，采用统一的步长，这为轮廓的匹配提供了很好的相同条件。 2 4 本章小结 本章首先对碎片的数字化过程作了简单的介绍，接着介绍了几种常用的图像 边界检测算子，指出c a 仰y 算子是较为理想的检测算子。随后对得到的碎片轮 廓数据进行预处理，比较了常用的几种滤波算法，指出g a u s s i 锄滤波能避免平 均滤波的缺点，较好地消除噪声数据的影响，同时它的滤波阶数也为重新采样提 供了统一的步长。接着对滤波后的轮廓线进行重采样，从而简化计算，提高运算 速度。 第三章轮廓角点检测 人类的视觉系统