（计算机应用技术专业论文）平面碎片匹配复原技术研究.pdf

摘要平面碎片匹配复原技术的研究有着重要的理论和现实意义，己成为模式识别、计算机视觉等领域的重要研究课题。本文运用数字图像处理、图形学、微分学和模式识别等领域的知识，在研究前人已有理论成果的基础上，不仅对碎片匹配过程中的数据采集、边界提取、特征分析、匹配和拼接等技术进行了比较全面的综述，而且提出、改进了一些新的思想和算法。本文做的研究工作主要包括：1 介绍了实物碎片的数字化、预处理和边界提取过程。发现了物体碎片厚度引起的平面碎片图像的双边缘问题，补充了碎片实际模型与理想模型的差别。明确了提取的碎片边界应具有连续性、封闭性和零宽度特性，并以此判断所提取边界的优劣，改进了边界跟踪算法。2 在边界曲线的特征分析检测方面，鉴于离散点曲率计算复杂且存在精确度低的问题，本文在分析各种角点检测方法的基础上，提出了基于斜率变化不连续性的多尺度角点检测算法，提出了将向量模作为边界曲线的不变特征量的特征分析方法。3 根据向量模的坐标变换不变性，提出了基于向量模的碎片匹配算法。并把最长公共子序列问题的思想及其动态规划算法应用到基于斜率变化量的边界曲线匹配问题中。4 在分析基于旋转平移的碎片两两拼接方法的基础上，提出了碎片的隐式旋转平移拼接方法，并把广度优先和深度优先的思想应用到多碎片拼接问题中，提出了基于广度优先和深度优先的多碎片拼接策略。关键词：平面碎片匹配，特征分析，斜率变化量，向量模，拼接r e s e a r c ho nt h ep l a n a rf r a g m e n t sm a t c h i n ga b s t r a c tt h er e s e a r c ho ft h ep l a n a rf r a g m e n t sm a t c h i n gi sv a r yi m p o r t a n to nt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c ea n dh a sb e c o m eav e r yi m p o r t a n tr e s e a r c ht o p i ci np a t t e mr e c o g n i t i o n ，c o m p u t e rv i s i o na n do t h e rf i e l d s i nt h i sp a p e r , o nt h eb a s i so fl e a r n i n gp r e v i o u st h e o r e t i c a lr e s u l t s ，t h ew h o l ep r o c e s sf r o md a t aa c q u i s i t i o n ，e d g ed e t e c t i o n , f e a t u r ea n a l y s i s ，m a t c h i n gt ot h el a s ts p l i c i n ga l es u m m a r i z e d ，a n ds o m en e wi d e a sa n da l g o r i t h m sa r ep u tf o r w a r do ri m p r o v e db yu s eo ft h ek n o w l e d g ei nt h ef i e l d so fd i g i t a li m a g ep r o c e s s i n g ，g r a p h i c s ，d i f f e r e n t i a ls t u d ya n dp a t t e r nr e c o g n i t i o n t h er e s e a r c hw o r km a i n l yi n c l u d e st h ef o l l o w i n g1 t h em e t h o d so ft h ed i g i t i z a t i o no ff r a g m e n t s , p r e - p r o c e s s i n ga n de d g ed e t e c t i o na l ei n t r o d u c e d t h ep r o b l e mo fd o u b l ee d g e so ft h ep l a n a ri m a g e rd u et o t h et h i c k n e s so ff r a g m e n t si sd i s c o v e r e d ，a n dt h ed i f f e r e n c e sb e t w e e nt h ei d e a lf r a g m e n t sm o d e la n dt h ea c t u a lf r a g m e n t sm o d e la r ea d d e d t h ec o n t i n u o u s ，c l o s e da n dz e r o w i d t ha t t r i b u t e so fd e t e c t e de d g e sa r ec l e a r e da n db eu s e dt od e t e r m i n et h em e r i t sa n dd e m e r i t so ft h ed e t e c t e de d g e s i na d d i t i o n , t h ee d g et r a c k i n ga l g o r i t h mi si m p r o v e d 2 a tt h ef e a t u r ea n a l y s i sa n de x t r a c t i o no ft h ee d g ec u r v e , i nv i e wo ft h ec o m p u t a t i o n a lc o m p l e x i t yo fd i s c r e t ep o i n t so fc u r v a t u r ea n dt h ee x i s t e n c eo ft h ep r o b l e mo fl o wa c c u r a c y ,t h i sp a p e ra n a l y z e sav a r i e t yo fc o r n e rd e t e c t i o nm e t h o d s ，a n dp r e s e n t st h en e wm u l t i s c a l ec o r n e rd e t e c t i o nm e t h o db a s e do nt h ed i s c o n t i n u i t yo fc h a n g e so fs l o p e ，a l s op r e s e n t san e wm e t h o do ff e a t u r ea n a l y s i sw h i c hv e c t o rm o d u l ei su s e da st h ef e a t u r ei n v a r i a n to ft h ee d g ec u r v e 3 a c c o r d i n gt ot h ei n v a r i a n c eo fv e c t o rm o d u l ei nc o o r d i n a t et r a n s f o r m a t i o n , an e wm a t c h i n ga l g o r i t h mb a s e do nm a t r i xo fm o d u l ev a l u ei sp r e s e n t e d t h ei d e ao ft h ep r o b l e mo ft h el o n g e s tc o m m o ns u b s e q u e n c ea n di t sa l g o r i t h mb a s e do nd y n a m i cp r o g r a m m i n ga r ea p p l i e dt ot h ec h iv em a t c h i n gp r o b l e mb a s e do nt h ev a r i a t i o no fs l o p e 4 o nt h eb a s i so fa n a l y z i n gt h em e t h o d so fs p l i c i n gt w of r a g m e n t sd e p e n d i n go nt r a n s l a t i o na n dr o t a t i o n ，t h i sp a p e rg i v e san e wi m p l i c i tr o t a t i n gt r a n s l a t i o n a ls p l i c i n gm e t h o d s ，1 l la p p l i e st h ei d e ao fb r e a d t h - f i r s ta n dd e p t h - f i r s tt ot h es p l i c i n gp r o b l e mi nm a n yf r a g m e n t s ，a n dp r e s e n t st w os p l i c i n gs t r a t e g i e so nm a n yf r a g m e n t sw h i c ha r et h eb r e a d t h - f i r s to n ea n dt h ed e p t h f i r s to n e k e yw o r d s ：p l a n a rf r a g m e n t sm a t c h i n g ，f e a t u r ea n a l y s i s ，t h ev a r i a t i o no fs l o p e ，v e c t o rm o d u l e ，f r a g m e n t ss p l i c i n g西北大学学位论文知识产权声明书本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论文收录到中国学位论文全文数据库或其它相关数据库。保密论文待解密后适用本声明。学位论文作者签名：。( | 年6 洲e l指导教师签名：蚤匕么bd 气年6 只f 蓦日西北大学学位论文独创性声明本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学撇作糍：陟如。罗年7 月召日两北大学硕l = 学位论文1 1 研究背景及意义第一章绪论生活中人们偶尔会遇到粘合撕碎的重要票据或纸币的情况，此时碎片数量较少，可以根据其上的文字、形状、纹理、色彩等可以很快将它们拼接成功。但是，来看下面的一篇报道。在1 9 9 0 年1 0 月3 日德国统一前夕，前东德情报机构“斯塔西官员将大量绝密文件撕成6 亿多块碎纸片后丢进1 6 0 0 0 多个垃圾袋。1 9 9 5 年，德国政府委托一组档案专家还原遭撕毁的“斯塔西 文件。在8 年时间罩，包括数名前“斯塔西 雇员在内的1 5 名工作人员一直在用镊子、胶带等工具试图拼凑这些碎纸片。但是工作进度极其缓慢。他们平均每天只能拼凑1 0 份文件，总共只拼凑了约2 5 0 袋、共计5 0 万张碎片。专家估计，按照这种速度，想要拼完全部碎片，将耗费4 0 0 年时间。除此之外，考古学家遇到的古代留下来的破碎的珍贵文物，公安机关破案遇到的破碎照片，司法技术鉴定工作中遇到的大量破碎纸质证物，保密机构获得的破碎的重要文献和图片，珍贵的破碎的艺术品等等。显然，当碎片的数量很少的时候，可以用纯手工的办法把碎片拼起来，但是当碎片的数量增大到几百上千块以上的时候，如果仍然依靠手工完成，不但耗费大量的人力、物力，还可能对碎片造成一定的损坏，而且这种繁琐的重复劳动在有效时间内也许根本无法完成。这种状况与信息时代的步调格格不入，如果用计算机来代替重复而繁重的工作，情况就会变得容易的多。接着上面的报道来看，2 0 0 3 年1 1 月2 2 日每同电讯报报道，德国科学家宣布，依靠他们最新研制出的先进仪器，可以在短短5 年内将1 6 0 0 0 个垃圾袋中的碎纸全部拼凑成形，从而使这批绝密“斯塔西 文件重见天日。目前，在国际上，德国等发达国家对破碎文件的自动修复技术已经进行了相当长时间的研究。但是由于技术封锁的原因，能够得到的资料微乎其微。而在国内，还没有相对成功的研究成果问世。碎片匹配仍然是学术研究的前沿问题，这个问题研究成功会开辟诸多新的应用领域，促进模式识别等很多学科的发展。因此，结合以上应用背景，把计算机视觉和模式识别应用于碎片复原，开展对碎片匹配技术的研究具有重要的理论和现实意义。1 2 碎片匹配技术的研究现状目前碎片匹配复原的实际工作大部分还是在靠人工的方式完成。这种落后的无奈之第一章绪论举和信息时代高效的现实需求之i 日j 的矛盾愈来愈明显，也引起相关理论界的高度关注，越来越多的人开始研究碎片匹配技术。王敏把碎片物体分为长方形、正方形、圆形、直角三角形、非直角三角形、类似半圆形等并对这些规则碎片匹配进行了研究。而实际应用中，这些规则碎片的匹配复原问题占的比例很少，而且比较容易求解，非规则碎片匹配问题是这个领域的难点和重点。国外方面，y i n gs h a n t 2 】等提出的算法主要思想是根据特征点的相似性和与邻域的距离得到初始概率，然后不断地迭代，直到特征点的概率达到稳定值，提出的这种概率框架的曲线匹配算法，也适合于平面曲线的匹配。c h r i s t i a nm e n a r da n dr o b e r ts a b l a t n i g t 3 l把物体看成由对称轴旋转而来，通过旋转轴按自底向上的顺序重新恢复古文物的轮廓，由此把考古碎片按其轮廓的相似性进行自动分类。m a h e ra 1k h a i y a ta n df a r h a dk a m a n g a r l 4 】提出先把曲线用同心圆的角度的集合重新表征，并要求两条曲线匹配的条件是对应的同心圆的角度集合必须相等，并以此条件进行曲线匹配。h e l a n ac r i s t i n ad ag a m aa n dj o r g es t o l f i l 5 】把轮廓线先进行曲率编码，实质上也就是用特征量曲率重新表征轮廓线，然后比较经曲率编码的轮廓线是否匹配，其使用了动态规划算法以减少搜索代价，在不断增加的尺度上进行轮廓线比较。g o k t u r ku e o l u ka n dl s m a i lh a k k it o r o s l u 6 】提出了通过识别碎片的轮廓线，进行轮廓线的形状匹配完成碎片复原，但其算法仅仅是研究试验，没有真正的应用于实际工作，而且计算量比较大。e y a lk i s h o n ，t r e v o rh a s t i ea n dh a i mw o l f s o n 7 】等人就三维曲线方面做了深入的研究，利用s p l i n e 曲线技术来匹配空间曲线，从而达到识别、拼图的效果。h e l e n ac r i s t i n ad ag a m al e i t a o i 剐在二维碎片拼合方面做了很多工作，他提出了把多尺度技术应用在曲面匹配过程中。在国内，近几年也有一些研究成果。如陈海掣9 】利用改进遗传算法实现图像特征点的匹配，其算法是一种匹配策略或框架。王展【lo 】提出用小波变换结果的局部范围内的极大值进行信息检测和定位，从而提取图像的角点。彭晓明【l l 】也提出基于小波变换的多尺度角点提取方法，主要是根据曲率理论，利用在几个尺度上进行小波变换的极大值进行角点提取。吕科等i l2 l 提出基于f o u r i e r 变换的曲线匹配算法，通过比较两条曲线的h a s h矢量来分析曲线段的相似度。周石林f 1 3 】在其博士论文中结合插值方法提出一种新的离散点的曲率计算方法，并以此构造了新的多尺度角点检测算法，提出了基于角点的平面碎片匹配算法。此外还研究了三维曲线匹配原理，提出与点的曲率和挠率密切相关的三个不变量，最后提出了基于特征点的三维碎片的匹配算法。朱延娟1 1 4 1 等提出基于h a u s d o r f f距离的多尺度轮廓匹配算法等。2西北人学硕士学位论文从国内外碎片匹配的研究发展现状可以大致归纳如下：碎片匹配的研究方法从原始的分类，如碎片原料的粘土、颜色、表面的纹理等特性、碎片挖掘出土的位置等，逐渐发展到使用信息论堆算法来对数字化碎片进行较快的分类和分群，再逐步发展到按照碎片的轮廓形状信息进行计算机自动分类，然后发展到具有初步意义的自动匹配。从哲学意义上讲，以上发展过程实际上就是一个从事物现象到本质地逐渐深入地认识和实践的过程，随着研究者认识实践活动的不断深入，更好地解决问题的思路和方法必然会被提出来，问题最终将会被圆满地解决，这是哲学发展观不可违背的客观规律。从技术特征上来看，这是一个从手工劳动到信息化的发展过程，随着科学技术水平的进步，问题的解决速度将会越来越快。当然，从以上国内外研究现状来看，虽然碎片匹配技术研究已经取得了一定的成果，但其中还存在很多需要改进和深入研究的方面，比如，已有成果中，大部分将曲率作为碎片匹配的不变量，理论性很强，但是离散点的曲率计算存在近似，计算的精度问题始终没有得到很好的解决；虽然有很多论文提出新的角点检测方法，但仍存在算法原理复杂、速度慢、角点检测不完全等问题；碎片的数量成千上万，设计快速高效的匹配算法也至关重要；另外，很多研究中提出的方法缺少实验验证，只是理论框架，离实际应用还差很远等等。本文试图在非规则碎片匹配的研究工作中，从以上方面改进提高。1 3 碎片匹配技术概述由于非规则碎片的匹配问题比较复杂，至少目前的科技水平下还没有哪种方法能从整体上把碎片一步匹配完毕，而只能把一块碎片的一部分与另一块碎片的一部分相匹配，也就是先局部拼接，然后采取不同的策略完成所有碎片的复原。这样，匹配就会有不同的思路，就像玩过的拼图游戏一样，拿着它的第一反应就是按照碎片的纹理图案、颜色、线条、文字的内容等进行拼合，实际就是基于内容的匹配。基于这种考虑的匹配难度比较大，因为这就要求计算机掌握很多先验知识，涉及更多的人工智能因素，目前很难解决。更多的研究采用另一种思路。因为图像的边缘对人的视觉具有重要意义，一般而言，当人们看一个有边缘的物体时，首先感觉到的是边缘。两个原本属于一体的( 匹配的)碎片必然有相同的边缘。从这个角度考虑，可以基于碎片的边缘曲线进行匹配而不考虑碎片的内容，那么解决这个问题需要一系列相关技术的支撑，包括：碎片数据采集、边界提取、特征分析检测、匹配和拼接技术等，其框架模型如图1 1 所示，其中提取边界3第一章绪论技术、特征分析检测技术和匹配技术是难度较大的关键技术，本文也围绕这些技术问题进行研究。实物碎片0碎片数字化上图像预处理0提取边界上特征分析检测上找匹配段0拼接复原图1 1 碎片匹配问题的技术框架模型( 1 ) 本论文的数据来源将主要利用扫描仪对碎片进行扫描，保证碎片被扫描的一面在原始位置中属于同一面，且每次扫描的分辨率都是一样的。为了提高域值分割的精度，对同一次扫描，使用相同的背景颜色，将扫描结果以图像的形式保存下来。( 2 ) 边界检测技术涉及到很多具体问题。首先，既然是基于边界曲线匹配的方法，提取边界就是基础，要明确提取出具有怎样特性的边界才符合匹配拼接工作的需要，从而也为边界提取算法优劣定下一个尺度。接下来要考虑碎片的理想模型和实际模型之间存在的差异，要把理论设想应用到实际模型中可能需要大量的改进处理工作。碎片图像检测出的边缘并不等同于实际目标的真实边缘，再加上成像过程中的光照不均和噪声等因素的影响，使得有边缘的地方不一定能被检测出来，检测出来的边缘也不一定代表实际的边缘。这时要用较好的方法预处理，去除噪声影响、锐化边缘。图像的边缘有方向和幅度两个属性，沿方向像素值变化平缓，垂直于边缘的方向像素值变化剧烈，边缘上的这种变化可以用微分算子检测出来。可以用来检测的微分算子包括r o b e r t s 算子、s o b e l算子、p r e w i t t 算子、l a p l a c i a n 算子、l o g 算子、c a n n y 算子等。要选择一种合适的算4两北大学硕j ：学位论文子并予以改进以更好的检测边界。在某些情况下，由于噪声等因素的影响，获得的边缘点有可能不连续，这时还可能要用到边界跟踪技术及该技术的改进方法以将它们转化为有意义的边缘信息，便于后续处理。( 3 ) 特征分析检测技术。提取或选择特征是模式识别的非常重要的一步，抓住了特征就抓住了事物的要害。在本论文的边界匹配问题中，特征分析是找出边界曲线的特征，找出曲线匹配中的不变量。比如，检测边界曲线上的特征点，包括：角点、拐点、切点。角点在匹配中有着非常重要的地位，很多学者在这方面展开研究。在角点检测时，在每个尺度下给出一个绝对的阈值是很困难的，因为“角点 的概念具有相对性。当局部边界曲线段上存在尖锐的点时，尖角的曲率系数一定较大，因此被当作角点，而该点从全局来看，仍然可能只是平缓圆滑地逐渐改变其方向的部分，可能不应该被当作角点，这种相对性决定了角点需要在不同尺度下进行检测，所以如何设计出多尺度下准确高效的角点检测算法也是本文研究的重点。( 4 ) 匹配技术。碎片匹配时，涉及到一个重要的数学问题就是曲线的匹配。曲线匹配技术的关键点是确定匹配依据不变量( 坐标变换中具有不变性的量) ，用不变量重新表征边界曲线。相应的，匹配工作主要表现为在用特征不变量表征的两条边界曲线的特征不变量序列中找公共序列，可以要求严格的对应相同，但这可能不符合实际模型的情况，所以可以把最长公共子序列问题的思想应用其中。( 5 ) 拼接技术。这块技术的内容主要是将已知匹配的碎片拼接复原以还原出其本来的模样，最大程度减少人为参与的工作，给计算机自动匹配任务划一个完美的句号。要考虑的问题包括两两碎片拼接方法和多碎片拼接策略。1 4 论文的研究内容本文主要针对平面非规则碎片匹配复原技术进行研究，在以下各方面做工作：1 介绍实物碎片的数字化、预处理和边界提取过程。发现实际模型中物体碎片厚度引起的平面碎片图像的双边缘问题，将碎片实际模型与理想模型的差别补充完整。明确提取的碎片边界应具有连续性、封闭性和零宽度特性，并以此判断所提取边界的优劣，改进边界跟踪算法。2 在边界曲线的特征分析检测方面，鉴于离散点曲率计算复杂且存在精确度低的问题，本文在分析各种角点检测算法的基础上，提出基于斜率变化不连续性的多尺度角点检测算法，并提出将向量模作为边界曲线的不变特征量的特征分析方法。5第一章绪论3 根据向量模的坐标变换不变性，提出基于向量模的碎片匹配算法。并把最长公共子序列问题的思想及其动态规划算法应用到基于斜率变化量的边界曲线匹配问题中。4 在分析基于旋转平移的碎片两两拼接方法的基础上，提出碎片的隐式旋转平移拼接方法，并把广度优先和深度优先的思想应用到多碎片拼接问题中，提出基于广度优先和深度优先的多碎片拼接策略。1 5 论文的章节安排本论文将分为5 章：第一章是绪论。叙述课题研究的背景、意义以及碎片匹配问题的国内外研究发展状况，对碎片匹配技术做概括性介绍。第二章是碎片边界提取技术。包括碎片的数字化处理，为便于后续工作的处理进行必要的数字图像预处理，然后提取碎片图像的边界。在这里明确提取的边界应具备的三大特征，并且分析一些算法在此方面的优劣。改进边界跟踪算法，使之能得出有意义的碎片边界，同时给出实验结果。第三章是特征分析检测技术。在这章中着重研究边界曲线的特征分析提取，一方面研究把角点作为特征的分析检测方法，对角点检测的单尺度、多尺度算法进行介绍，提出新的基于斜率变化的不连续性的多尺度角点检测方法。另一方面，提出把向量模作为边界曲线的特征不变量的特征分析方法。第四章是匹配技术。该章的第一部分提出基于向量模值矩阵的匹配算法及给出实验结果；第二部分主要将最长公共子序列问题的思想及其动态规划算法应用到基于斜率改变量的匹配算法中，分析讨论各种匹配算法的性能。第五章是拼接复原技术。该章的第一部分着重研究碎片两两拼接方法，介绍基于旋转平移的拼接方法和提出隐式旋转平移拼接方法；第二部分介绍多碎片拼接复原的策略。6西北人学硕士学位论文2 1 模式识别概述第二章碎片边界提取技术模式识别i l5 】( p a t t e r nr e c o g n i t i o n ) 是指对表征事物或现象的各种形式的( 数值的、文字的和逻辑关系的) 信息进行处理和分析，以对事物或现象进行描述、辨认、分类和解释的过程，是信息科学和人工智能的重要组成部分。模式识别的研究主要集中在两方面，一是研究生物体( 包括人) 是如何感知对象的，属于认识科学的范畴，二是在给定的任务下，如何用计算机实现模式识别的理论和方法。前者是生理学家、心理学家、生物学家和神经生理学家的研究内容，后者通过数学家、信息学专家和计算机科学工作者近几十年来的努力，已经取得了系统的研究成果。模式识别问题指的是对一系列过程或事件的分类与描述，具有某些相类似的性质的过程或事件就分为一类。模式识别问题一般可以用统计方法( 又称为决策理论方法) 、句法方法( 又称为结构方法或语言学方法) 和神经网络方法进行分析处理。其中统计方法是发展比较早也比较成熟的一种经典方法，在图像模式识别中有着非常广泛的应用。一个计算机模式识别系统基本上是由三部分组成的，即数据采集、数据处理和分类决策或模型匹配。任何一种模式识别方法都首先要通过各种传感器把被研究对象的各种物理变量转换为计算机可以接受的数值或符号( 串) 集合。习惯上，称这种数值或符号( 串) 所组成的空间为模式空间。为了从这些数字或符号( 串) 中抽取出对识别有效的信息，必须对它进行处理，其中包括消除噪声，排除不相干的信号以及与对象的性质和采用的识别方法密切相关的特征的计算( 如表征物体的形状、周长、面积等等) 及必要的变换( 如为得到信号功率谱所进行的快速傅里叶变换) 等。然后通过特征选择和提取或基元选择形成模式的特征空间。以后的模式分类或模型匹配就在特征空间的基础上进行。图像碎片匹配问题属于模式识别的范畴，所以碎片匹配问题的处理，也是由数据采集开始，再进行数据处理和模式匹配等后续工作的。本章要讨论的重点就是数据采集。本文认为碎片匹配问题的数据采集有狭义和广义之理解，狭义的数据采集指的将实物碎片数字化，表示成适合计算机处理的形式。而本文所说的广义的数据采集是指进行特征分析提取的数据处理工作之前的所有数据准备工作，也就是说从碎片数字化到提取出边界都是数据采集的过程。本文把对碎片数字化后的图像进行去噪等前期操作称为图像预7第二章碎 边界提取技术处理，其目的是使提取的碎片边界更精确。所以本文的数据采集工作的第一步是进行碎片数字化，然后进行图像预处理。图像预处理之后，再进行边界提取，其流程如图2 1所示。叵亟婶匹堕m 臣堕口图2 1 碎片边界提取流程2 2 碎片数字化将实物碎片进行数字化是碎片匹配复原的第一步工作。所谓实物的数字化就是指通过特定的测量设备和测量方法获取实物离散点的几何坐标数据。实物数字化的目的就是为了将待处理实物表示成适合计算机处理的形式。目前的实物数字化方法，根据测量探头或传感器是否和实物接触，可分为接触式和非接触式两大类【l 甜。接触式如：机器手、三坐标测量机( c m m ) ；非接触式如：光学测量、声波测量、电磁测量。它们各有优缺点，其中三坐标测量机( c m m ) 、激光扫描测量和三维数字照相是使用比较广泛的几种测量方法。三坐标测量机通用性较强、测量范围较广、精度高，可以手动测量也可以通过编程规划扫描路径进行点位测量，具有复杂内部型腔的工件和几何复杂的外形曲面，以及具有复杂边界、特征棱线的物体比较适合使用该仪器测量。但是，三坐标测量机存在工作量大，测量速度慢，环境温度、噪声等对测量精度影响较大，数据还需进行测量头半径补偿等缺点。激光扫描测量是近些年发展起来的普及很广的测量技术，扫描仪器可以分为二维扫描测量仪和三维扫描测量仪，还可分为平板式扫描仪、手持式扫描仪、鼓式扫描仪、笔式扫描仪等等，其扫描速度快，精度较高。三维数字照相是9 0 年代开始发展起来的测量手段，近年发展速度很快，普及率很高，主要适合于二维和三维自由表面的测量，测量速度快，效率高，可以在几秒钟内得到百万以上的数据点，可以直接输出三角网格模型，而且有些高端产品能够自动完成多视角测量的数据集拼合，从而输出物体整体的点云形式或三角网格形式的数字化样件，其缺点是，数字化样件可能存在需要进行尺度变换的问题。本文利用平板式扫描仪扫描二维纸张碎片进行数字化，从而获取碎片图像数据。扫描过程中，保证所有碎片被扫描的一面在原始位置中属于同一面，且每次扫描的分辨率都相同，对所有扫描碎片使用相同的背景颜色，并用相同大小保存扫描结果图像，这些做法都是为了保证碎片图像的后续提取边界等处理工作能顺利进行。扫描结果图像如图8西北大学硕i 学位论文2 2 所示。扫描原始碎片1扫描原始碎片2扫描原始碎片32 3 图像预处理田2 2 扫描原始碎片通过测量设备所测得的数字化样件受很多因素的影响，包括仪器的因素和物理的因素。其中仪器因素包括视觉、阴影、光线、噪声以及图像的采样量化等。物理因素包括小碎片的遗失、边缘的腐蚀、磨损、表面的不规则以及物体厚度引起的双边缘问题等。由采样点组成的碎片数字边界曲线会受以上两种因素影响产生各种误差，如不消除，这些误差数据将会直接影响重建图像边界模型的质量，进而影响匹配效果。所以对数字化图像进行必要的数据预处理是模型重建之前非常重要的一步工作，预处理的目的包括两层意义，是去除噪声数据、异常数据、数据平滑、压缩和归并冗余数据、遗失点补齐等，二是对图像进行加工以得到对提取碎片边界工作来说视觉效果更好或更有用的图像，使得边界提取更容易。去除噪声常用的方法包括空域滤波方法和频率滤波方法，将在下面做详细介绍。数据平滑常用方法包括标准高斯、平均或中值滤波算法，高斯滤波对保持原数据的形貌效果较好，中值滤波对消除数据毛刺效果较好，应用时可灵活选择滤波算法。数据简化是减少数字化样件中存在的大量冗余数据，有序数据可采用等间距采样法等简化算法。本文主要考虑滤波去除噪声和锐化边缘处理。2 3 1 去障噪声鼓字图像的噪声主要来源于图像获取和传输过程，通常认为噪声是有概率密度函数( p d f ) 表示的随机函数。图像处理中常见的噪声有：高斯噪声、瑞利噪声、伽马噪声，指数噪声、均匀噪声、椒盐噪声( 脉冲噪声) 等1 1 7 1 。将这些噪声消除并恢复原图常用的空域滤波方法包括：( 1 ) 均值滤波嚣均值滤波器包括算术均值滤波器、几何均值滤波器、谐波均值滤波器和逆谐波均值第一二章碎片边界提取技术滤波器。令表示中心为点( x ，y ) 、尺寸为m xn 的矩形图像窗口，g ( x ，y ) 表示受噪声影响后的图像，夕( x ，y ) 表示滤波器输出图像。下面列出各种滤波器的i o 方程：算术均值滤波器：夕( 工，y ) ：一i g ( j ，f )几何均值滤波器：夕c 五y ，： 。硝1 - k i g c s 丁”谐波均值滤波器：氕五力。_ ( ，魅g ( s ，f )g ( s ，) q + 1 厂逆谐波均值滤波器：a 墨力= 型赫( 2 1 )( 2 2 )( 2 3 )( 2 4 )( s ，) e 算术均值滤波器简单地平滑了一幅图像的剧本变化，在模糊了结果的同时减少了噪声；几何均值滤波器所达到的平滑度可以和算术均值滤波器相比，但在滤波过程中会丢失更少的图像细节；谐波均值滤波器善于处理类似高斯噪声那样的噪声，它对正脉冲( 盐点) 噪声效果较好，但不适于负脉冲( 胡椒点) 噪声；逆谐波滤波器适合减少或消除椒盐噪声。( 2 ) 顺序统计滤波器顺序统计德汲的输出基于葡滤波器包围的图像区域中像素点的排序，滤波器在任伺点的输出由排序结果决定。一般包括中值滤波器、最大值滤波器、最小值滤波器和中点滤波器，其d 方程为：。中值滤波器：夕( 五) ，) = m e d i a n g ( s ，f ) l( 2 5 )i 。i ，c d ，最大值滤波器：夕( 五 = m 悱a 。x 。 g ( s , ，) ( 2 - 6 )最小值滤波器：夕( t 川= m ，i 。n 。 ，g ( s , ，) ( 2 7 )中点滤波器：，c 副，= 三 。粤麓 g ( 蹦) + 。墨翌 g ( 蹦) ( 2 8 )其中最著名的是中值滤波器，它对很多随机噪声都有良好的去噪能力，且在相同尺寸下比线性平滑滤波器引起的模糊更小。最大值滤波器发现图像中的最亮点时非常有l o西北人学硕士学位论文用，同时特别适用于消除胡椒噪声；而最小值滤波器在发现图像中的最暗点时非常有效，同时特别适合于消除盐噪声；中点滤波器将顺序统计和求均值相结合，对于高斯和均匀随机分布噪声有很好的效果。空域滤波方法还有一种基于统计特征提出的自适应滤波器，它优于前两种滤波器的性能，在提高滤波能力的同时也带来滤波器的复杂性。此外，消除噪声也可用频域滤波方法，比如振铃现象不明现的巴特沃斯低通滤波器，此处不再详述。2 3 2 图像锐化去除噪声的同时可能使得图像模糊而退化，为使边缘和轮廓更清晰，需要进行图像锐化处理。从数学上看，图像模糊的实质就是图像受到平均或者积分运算的影响，因此对其进行逆运算( 如微分运算) 就可以使图像清晰，下面介绍常用的图像锐化运算。( 1 ) 梯度算子法对图像f ( x ，y ) ，在其点( x ，少) 上的梯度可以定义一个二维列向量：g t 厂c x ，y ，= 置 =劭o x对o x，其模值g o 【厂( x ，y ) 】小虿五琴=，近似梯度值瓯叭圳讪q 和q 用近似值辟震：二篇出扣得到直接差分算子如图2 3 所示：卜l上田园( a ) 直接差分示意图( b ) 直接差分算子图2 3 直接差分法q 和q 用近似值黔磐碱端储删助吼s 算子硝示：第_ 二章碎j i 边界提取技术q 和g 用近似值田田( a ) 交差差分示意图( b ) r o b e r t s 算子图2 4 交差差分法g ，= ( ( f ( x - 1 ，y - 1 ) + 2 f ( x - 1 ，y ) + f ( x - 1 ，y + 1 ) )一( 厂( x + l ，y - 1 ) + 2 f ( x + l ，j ，) + ( x + l ，y + 1 ) )g 。= ( ( ( x 一1 ，y 一1 ) + 2 f ( x ，y 1 ) + 厂( x 十1 ，y 一1 ) )一( ( x 一1 ，y + 1 ) + 2 f ( x ，少+ 1 ) + 厂( x + 1 ，y + 1 ) )代替得s o b e l 算子如图2 5 所示：12l00o121图2 5s o b e l 算子( 2 ) 拉普拉斯算子法圜口( a j 控誓拉奠穗 子国) 控瞽拽斯扩戴苒子图2 6 拉普拉斯算子模板及扩展模板加上对角线元素的离散函数f ( x ，力的拉普拉斯算子可以表示为：v 2 f ( x ，y ) = 【f ( x + l ，y 一1 ) + ( x + l ，y + 1 ) + 厂( 工一1 ，j ，+ 1 ) + 厂( x l ，y 一1 ) +f ( x + 1 ，y ) + ( z 一1 ，j ，) + f ( x ，y + 1 ) + 厂( x ，少一1 ) 卜8 厂( x ，y ) 】由此得如图2 6 所示的拉普拉斯算子模板。拉普拉斯算子比较适合用于改善因光线的漫反射而造成的图像模糊。此外可以在频域进行图像锐化，比如可以使用常用的巴特沃思高通滤波器。2 4 提取边界2 4 1 碎片的理想模型与实际模型通常把碎片的模型分为理想模型和实际模型两种8 1 。理想模型如图2 7 所示，该模型中碎片表面光滑平整且表面厚度为0 ，这些表面被非规则的o 宽度裂纹曲线随意的分为多块碎片。一个理想碎片的边界是一条理想的轮廓曲线，理想碎片的边界线可能是由1 2西北人学硕十学位论文于破碎造成的碎裂线，也可能是原始物体边界线的一部分。如果两块碎片共享同一段裂纹线，则该裂纹线称为公共边，称该两块碎片是相邻碎片。三条及三条以上的碎片边界线的相交点构成一个理想角点。理想碎片重新拼接复原后的实体和原来的物体完全一致，不存在缺损和误差。理想角- ， 、，、，一，、，一，、一一7，、! 、?、，一一、i _ _ - ，?、，、i、图2 7 理想碎片模型理想碎片模型毕竟只是理想的情况，不符合实际情况。实际上，由于自然的或是人为的原因会造成细小碎片的遗失，自然磨损，以及数字化过程会造成视差、投影误差和采样误差等，从实物或数字化样件中提取的实际轮廓曲线通常和理想模型中的轮廓曲线有差别。如图2 8 所示，是真实情况下的碎片实际模型。碎片的实际轮廓曲线是碎片的条闭合的边界曲线。两条分别属于两个碎片的实际轮廓线上的部分曲线段在最大程度上具有相似性，就把这两条曲线段称为一对匹配曲线段或叫做最大匹配段，这两个曲线段所在的两个碎片互为对方的匹配碎片。图2 8 中碎片2 和碎片3 轮廓线的加粗部分曲线段在最大程度上具有相似性，故称碎片2 、3 轮廓曲线上加粗的两条曲线段为匹配曲线段或最大匹配段，碎片2 、3 互为对方的匹配碎片，两者构成一个匹配碎片对。碎片2的匹配碎片有碎片l 、3 和4 。匹配碎崩实际轮廓线图2 8 实际模型碎片由于诸多人为和自然的原因可能会导致碎片遗失的发生。通常把碎片的遗失分为两类：小碎片和大碎片的遗失。那些大碎片边缘部分的由于破碎过程和r 后磨损等原因造1 3第二章碎片边界提取技术成的小碎片遗失一般可以被当作噪声处理。而如图2 8 中所示的遗失碎片1 属于大碎片遗失，显然不能作为噪声处理，否则会带来错误，一般认为该碎片不存在或已遗失，被单独处理。此外，通常所说的二维碎片是指纸张、布匹等物体，其厚度在一定范围之内以至于可以忽略不计的情况下的二维碎片。实际上就不存在绝对的二维物体碎片。往往会发现厚度即使在一定范围内，但在研究碎片匹配问题时却带来麻烦使人们不能忽略不计，而不得不采取近似或使用经验阈值等措施将其考虑在内。如图2 9 所示，一张完整的纸被撕成两个碎片1 和2 ，撕裂时裂纹在其厚度上产生不一致从而使碎片1 、2 都有了两个边缘，这两个边缘的不一致使得在平面扫描时只扫描到其中一条，如图2 9 中两条加粗的黑实线是扫描所得边缘线，而实际与碎片2 中加粗黑实线边缘匹配的应该是碎片1 中的黑虚线边缘，显然这种情况下，用扫描图像所得碎片边缘线进行匹配是很难找到正确匹配结果的，当双边缘差别很大时就不可能找到正确的匹配而且可能引起和其它碎片的错误匹配的问题。本文把这种问题叫做物体碎片厚度引起的平面碎片图像的双边缘问题。厚度引起的碎片1 上的双边缘图2 9 物体碎片厚度引起的双边缘问题概括起来，实际碎片模型与理想碎片模型的差别主要表现在以下几个方面：1 ) 毛刺，如被撕破的纸的轮廓。2 ) 被磨损或腐蚀的轮廓。3 ) 有丢失的部分。4 ) 物体碎片厚度引起的平面碎片图像的双边缘问题。正是由于这些差别的存在，两块相匹配的碎片在匹配复原过程中邻接关系的确定变得相当困难。1 4两北大学硕上学位论文2 4 2 边界相关概念任何物体都是有边界线的，它是图像的一个重要特征。采取基于碎片的边界曲线进行匹配的策略，就先来讨论边界的相关概念。r a f a e lc g o n z a l e z 认为：令r 是图像中的像素子集，如果r 是连通集，则称r为一个区域。一个区域r 的边界是区域中像素的集合，该区域有一个或多个不在r 中的邻点。正常情况下，提到一个区域时，指的是一副图像的子集，并且区域边界中的任何像素都作为区域边界部分全部包含于其中。一个有限区域的边界形成一条闭合的通路，并且是“整体 的概念。而给边缘下合理的定义需要具有以某种有意义的方式测量灰度级跃变的能力。一条理想的边缘是一组相连的像素的集合，每个像素都处在灰度级跃变的垂直的台阶上，这样，边缘的概念是基于在不连续点进行灰度级测量的局部概念。直观上，一条边缘是一组相连的像素集合，这些像素位于两个区域的边界上。从根本上讲，边缘是一个“局部 的概念，而一个区域的边界更具有整体性的概念。周石林i l3 】在论文中提到：边界的提取包括散乱点的边界的提取和一般灰度图像的边界的提取。散乱点就是那些分布没有规律的点，对于散乱点而言，所谓边界是这样的曲线，它包围曲面内的所有点并且所包围的面积最小。灰度图像的边界提取是在图像中的像素点按单位长度的横坐标和纵坐标排列。所谓图像的边界线就是其周围的像素灰度发生阶跃变化或者屋顶变化的那些像素的集合。姚敏【1 刀认为：灰度或结构等信息的突变处称为边缘，是一个区域的结束也是另一个区域的开始。其他一些学者的相关论文中大都引用过这些概念，还有人提到碎片的轮廓的概念，但大都论述的比较模糊，没有明确给出边缘和边界的定义。本文认为在碎片匹配问题中，碎片的边界、边缘和轮廓是相同的概念，都是基于碎片数字化后的图像中包含碎片区域中所有像素点的像素组成的集合，且这些像素也属于该区域。无论怎样具体地定义它们，在边界曲线的碎片匹配问题中提取的碎片边界具有非常明显的根本特征，或者说，即使它们在定义时有一定的差别但它们必须具备的共性是：( 1 ) 像素点是连通的( 连续性) ；( 2 ) 是闭合的曲线( 封闭性) ：( 3 ) 边界点由单像素组成其边界宽度为0 ( 零宽度) 。具有这三个特点的边界是本文进行碎片匹配工作的基础。由于数字图像边界两边区域的灰度级存在较大差别，所以一般情况下把理想边界模型分为三种：阶跃模型、屋顶模型和钉子模型f 1 9 1 ，分别如图2 1 0 所示。阶跃模型边界指1 5第二章碎片边界提取技术边界两边的像素灰度值有着显著的不同；屋顶模型边界是指其位于图像中像素的灰度值从递增到递减变化的转折点处；而钉子模型边界是指边界两边的像素灰度值基本相同，但在边界处灰度值突然增大。阶跃模型屋顶模型钉子模型图2 1 0 边界灰度变化模型2 4 3 边缘检测图像的边缘沿水平于边缘的方向像素变化平缓，沿垂直于边缘的方向像素变化剧烈，这种变化规律可以用微分算子检测