（航空宇航制造工程专业论文）二维碎片拼合技术研究(1).pdf

南京航守航天大学坝 学位论文 摘要 碎片拼合就是要把大量的不规则的碎片重新拼接成初始的完整模型。这一问题 在行器的失事分析、考古、古生物学以及壁画保存等方面具有广泛的应用。要从 成千上万的碎片中找到相互邻接的碎片，并最终拼接成完整的模型，没有计算机的 辅助是很难实现的。本文研究二维碎片的b m p 图片轮廓特征提取技术，并对这些 特征进行简化、分析，然后设计了碎片拼合算法，主要的研究工作如下： 研究了碎片的数据采样。在分析碎片b m p 图像的基础上，给出“栅格逆时 针运动”算法获耿碎片轮廓采样点。 研究了采样点的几何滤波( 均值滤波、中值滤波和高斯滤波) 和重新采样 方法，得到了方便拼合的碎片数字化模型。 基于a c i s 平台，对采样点进行b 样条曲线拟合，并获得各采样点的匹配 特征曲率。 用动态规划( d y n a m i cp r o g r a m m i n g ) 算法找出两轮廓的匹配点序列，实现 两碎片的拼合。 关键词：碎片拼合，数据采样，曲线拟合，特征提取 维碎片拼合技术研究 a b s t r a c t r e a s s e m b l i n gu n k n o w i n gb r o k e no b j e c t s f r o ma l a r g e c o l l e c t i o no fi r r e g u l a r f r a g m e n t sa r i s e si n s e v e r a lc o n t e x t ss u c ha sa r c h a e o l o g y , f a i l u r ea n a l y s i s ，p a l e o n t o l o g y , c o n s e r v a t i o n ( m u r a lp a i n t i n g ) a n ds oo n i ti s i m p o s s i b l ei ft h e r ea r en oc o m p u t e r st o a s s i s ti n r e a s s e m b l i n gt h e s e t e n so ft h o u s a n d so fr a n d o m l ys h a p e da n df e a t u r e l e s s f r a g m e n t s i nt h i st h e s i s ，t h ee x t r a c t i o no fc o n t o u rf e a t u r ei sr e s e a r c h e df r o mt h eb m p i m a g e s o f2 d f r a g m e n t s t h e s e f e a t u r e sa r e a n a l y z e d a n d p r e d i g e s t e d a n d t h e r e a s s e m b l i n ga l g o r i t h mo ff r a g m e n t si sd e s i g n e d i nb r i e f , t h ep r i m a r yc o n t e n t sa r ea s f o l l o w s ： s a m p l ep o i n t d a t aa r eo b t a i n e df r o m f r a g m e n ti m a g e s w i t h g r i d i n c o u n t e r c l o c k w i s es e n s ea l g o r i t h mg i v e ni nt h i st h e s i s s a m p l ep o i n t d a t aa r ef i l t e r e dw i t h g e o m e t r i cf i l t e r i n g ( m e d i a nf i l t e r i n g ，m e a n f i l t e r i n ga n dg a u s s i a nf i l t e r i n g ) a n dp r e d i g e s t e d b s p l i n e c u r v e f i t t i n g a n dc u r v a t u r e a n a l y s i s a r ed i s c u s s e di n d e t a i la n da r e i m p l e m e n t e d w i t ha c i s m a t c h i n gp o i n ts e q u e n c e sa r eo b t a i n e d o nt h eb a s i so fc u r v a t u r e a n a l y s i sb y a p p l y i n gt h ed y n a m i cp r o g r a m m i n ga l g o r i t h m k e yw o r d s ：f r a g m e n tr e a s s e m b l i n g ，d a t as a m p l e ，c u r v ef i t t i n g ，f e a t u r ee x t r a c t i o n 南京航空航天人学硕士学位论文 第一章绪论 1 1 图形匹配技术及其应用 图形匹配是通过客观存在的物理碎片的图形、图像及其他属性信息的采集、分 析和建档，建立具有多维信息的模型的计算机表示。它综合利用了计算机的图形算 法、图像技术、三维图形与图像数据库技术，以及模式识别与匹配理论等，研究一 种基于特征分析和内容查找的自动拼合技术。常见的是类似七巧板和拼合，是由若 干平面多边形拼合而成，另有一些还在每个子片上配有图画，游戏者除了要寻找各 子片边界的完全匹配以外，还必须使拼合在一起的七巧板形成整体i , ) j , n g j 【田i 。当 了片数目较大，各片上的图案差异不很明显的情况下，完成这样的七巧极拼合是有 一定难度的。如果七巧板的子片不是简单的平面多边形，而是具有任意的空间几何 形状、任意的空问边界曲线，而且具有色彩、纹理、材料、厚度等多种其他属性， 则这一问题就更加具有挑战性。利用图形技术、图像技术、数据库技术以及模式识 别技术等，实现该问题的计算机求解，是一个在理论上和应用上都具有重要意义的 新的研究课题。 碎片拼合的计算机求解具有十分广泛的应用前景。例如，在考古研究方面，人 量出土的人类文化遗产对人类学的研究是十分珍贵的。但有许多出上文物，包括陶 器、瓷器、石器、人及动植物的骨骼和化石等，是破碎或残缺的，需要考占研究者 大量的时间和工作来对这些考古发现进行整理、修复。而有许多极其珍贵的考占碎 片山于数量较大、相互混杂，依靠简单的人工测量和比对无法完成这样的整理和修 复。这方面的例子有著名的罗马大理石地图( f o r m au r b i sr o m a e ) 之谜。该地图 是大约公元前2 0 0 年古罗马的一个巨大的大理石地图，大小有6 0 4 5 英尺，卧i 】 刻有表示地理位置关系的各种符号和沟槽，是研究古罗马地形学唯一的最重要的资 料。然而目前出土的只是残缺不全的1 1 8 6 片碎片，如何把这些又大又重而且数目 较多的碎片拼接修复，至今仍是一个世界难题。借助于光学三维摄像技术、测量建 模技术及图形图像拼合算法的发展，将有可能在计算机上使该问题获得解决。另外， 对楔形文字、甲骨文字的修复整理保存也可以应用该项技术。又如，硅藻是种单 细胞的藻类植物，由于它们由硅构成的细胞壁具有极其多样和精美的结构而成为精 微结构研究的热点。另外，由于在湖泊和海洋系统中存有大量的硅藻化石，硅藻也 是现代生态学和进化学研究的重要工具。通过显微照相技术获得硅藻的三维数据， 建立刚络环境下的图形图像数据库，对硅藻结构进行修复、空间对称等，对于深入 研究、利用、共享硅藻资源，推动相关学科研究的发展是十分重要的。 维碎片拼台技术研究 相对于单纯的图像信息而言，具有色彩和纹理等其他属性的i 维几何模型足刈 客观世界更加真实的模拟。三维图形可以在计算机上做任意的旋转、放大或缩小， 进行任意视角和各种比例的观察。而月，目前几何测量的范围和手段以惊人的速度 发展，基于光学、声学、磁学、卫星遥感、三维微观摄像等的测量设备，能够状得 大如罩球、天体，小如细胞分子结构的各种三维数据，这为三维图形技术在多个不 同领域中的应用提供了必要的数据来源。因此，以具有色彩和纹理等属性的二维图 形为基础开展研究是许多领域技术发展的必然。由二维到三维图形加平面图像文件 的数据库建档、存储、基于特征的图形图像查找、拼合等将获得越来越广泛的应用。 1 2 论文选题的背景及研究内容 图形图像的匹配，国内外学者己逐步开始对相关问题从不同角度开展了研究。 美国斯坦福( s t a n f o r d ) 大学m l e v o y 教授在美国国家自然科学基金的资助下，进 行了数字化米丌朗基罗( m i c h e l a n g e l o ) 计划的研究【2 j 。该研究项目通过激光测量设 备多视角测量雕塑作品的三维数字化点，并对多视测量数据进行拼合，然后用基于 洲量数据的建模技术建立了米开朗基罗大部分著名雕塑作品的多面体表示的数字 化模型。该课题在超大规模测量数据的高精度数字化建模方面产生了广泛而重要的 影响。但在该项目中( 包括其他多视数据的拼合研究，如1 2 1 13 】) ，雕塑作品本身是完 整的，不同视角测量数据的拼合是在己知不同数据集间邻接关系的情况下进行的， 所要解次的问题是不同视角测量的数据集如何精确换算到一个统一的坐标系下。另 外，该课题组目前正在从事罗马大理石地图的研究工作【4 】，现已完成大部分碎块的 数据测量工作，并进行了部分碎块的登记整理工作。 图形的匹配是拼合算法中的一个重要线索之一。在图形数据库的组织及基于模 式的查找和合成方面，可以归纳为两类：一类是基于亮度的( 包括颜色和纹理) ， 另一类是基于几何内容的。国内外学术界对此已获得了长足的发展。例如m i t 的 b o n e t 等提出了结构驱动的图形数据的拼合方法 5 “。y a n g 7 】则运用多实例的学习机 制实现图形数据的查找。随着测量技术和三维几何建模技术的发展，三维图形数据 库( 3 d s h a p el i b r a r y ) 或称空间数据库( s p a t i a ld a t a b a s e ) 越来越受到重视。美困 亚利桑那( a r i z o n a ) 、h 立大学p r i s m 联合项目组正在进行一个称为“3 dk n o w l e d g e ” 的研究项目【8 ，该项目着力进行三维几何图形数据库的建档、查询、分析方面的研 究，以从三维图形中获得“三维知识”，从而为生命科学、生物技术及人类学领域 的研究提供基础。该项目目前针对考古容器建立了一个用于“概念论证”的简化的 3 d 图形数据库。由于容器类产品形状一般较为简单，可以用二维轮廓来描述基本 的特征信息，该课题组按二维轮廓将考古容器分类为四种基本形式，以辅助图形数 据文件的查找。对基于3 d 知识的碎片拼合尚没有富有成效的研究结果。而且用二 维轮廓来描述基本的特征信息，对形状更为复杂的器物是无能为力的。意大利卡拉 撕鹏豫( c a l a b r i a ) 大学n a p o l i 等h 提h j 了一种半自动的考古容器碎片的分类与识 别方法。媛方法也是首先用坐标测量设备采集考古碎片的几何坐标，然后通过对赢 鞭夔睾靛努撰著与标准镶板予等线羲裹赣篷零分京稳魄较，寒蘸定碎片懿其傣位 置。该方法并没有在数搿辩的支持下，通过特铤的全面分孝厅，避行碎片的计算辊壹 找和拼合。另外，由于该方法也是假定待识剐的容器为回转体，而且预先假定有儿 种模板形式，因此有较大的局限性。 在三维图形的匹配方耐，德国慕尼黑( m u n i c h ) 大学k r i e g e l 领导的研究组根 据单纯戆三维图形特征从缀艟分子数据霹中快遮查找几何形状襁似的蛋自质分子。 鬟出了鏊予三维形专爰黪疆虢强l 翻黧萋予鏊嚣遥l 霾网豹穗像毪疆索方法。该谍题组翡 研究鞘前来涉及附加有图象等其他信息的物体相似性分析以及具有共同割边的碎 片间的拼合问题。o s a d a 蒋 12 】则通过在三维网格模型表示的整个物体上进行采样， 以获得物体的整体几何分郝属性( s h a p ed i s t r i b u t i o n ) ，作为三维物体相似性的判断 依据，从而田以将诸如人物、汽车、植物等避蒋不同的三维模型区分开来。其研究 方法对本课题研究有一定僚鉴 乍逶。 溪翦，国内在本课题稳关领域也逶雩亍了一定的研究，南京簸空腕天丈学、浙江 大学、大连理工大学等都对基于实物的三维几何模型建立进行了研究。由西北大学 可视化技术研究所承担的、国家8 6 3 项目和国家自然科学基金资助的计算机辅助文 物复原技术研究最近通过围家验收。另外，据了解在白鹤梁石刻保护中，文物工作 者已尝试遥过计算枫技术建立自鹤梁石刻蛉三维模型，以辅助磷究最佳躲保护方 案。但在综合三维足嚣、二维图象、萁毽文字瓣瞧等多缍信惠遴抒黪体援述、分毒厅、 检索、拼合等方面还缺乏深入研究。 总之，通过最新研究报道及网上获取的大殿研究动态的分析可见，类似多维七 巧板阀题计算机求解的相关问题已引起了人们的广泛关注，但主嚣的关键技术研究 目的还处在概念论证或酊期准备的初始阶段。不少研究在不同的角度和侧面展开， 但还缺乏翻实酶学科阉瓣交叉融合，透露性豹麓够舞决具有多线笺合信患鳃七巧叛 攒含朗题鹃基砝方法还有褥深入磺究。 本选题旨在将图形技术、图像技术等领域的一些研究成果融合在一起，从二维 图形的研究着手，对七巧板问题计算机求解中的关键核心问题_ i 挠行多学科交叉研 究。作为历史悠久的文明古固，中国有着丰富的文物遗存。这些珍资文物历经百千 万年，已饱受自然侵损和人为破坏。尘封千古的文物出土后，如何落加修复，妥善 景存，延续毒冷? 魏楚农考畜发援中送行文物僚护，醚文耨糅护鼹逡考吉发掘? 藏 为摆在我国考吉工作面前的一个重要课题。以往对破碎文物的复藏多是采用手工方 式，而计算机在形状匹西己方面具有很多独特之她。 本文从以下几个方面谶行阐述二维碎片的拼接问题： 第“章绪论。简介阉形匹配技术及其应朋，简介选题背景和本文的主要内容。 第二章数据斡采集。分绍数据采集躲主蘩方法，以及本文联采用麴方法：从 维碎片拼合技术研究 bpm 【割像采集碎片的边界特征信息，并对采样点进行滤波处理和重新采样。 第三章基ta c i s 的数据处理。介绍了碎片轮廓的处理方法，阐述了用b 样 条曲线拟合轮廓，以便找出匹配的特征信息。调用a c i s 的函数拟合出轮廓曲线， 并求出特征点的曲率，简介a c i s 。 第四章匹配算法的提出。介绍了轮廓曲线的几何不变性，利_ | = ；h 曲率不变性， 给出碎片匹配简便算法，并在v c 中实现。 第五章总结与展望。讨论本文中给出的算法的不足，以及今后的重点研究方 向。 4 南京航空航天大学坝上学位港文 2 1 引言 第二章数据的采集处理 熙形匹配、碎片拼按的关键之是要建立能够描述实物的计辩枧模型，丽模型 黪鏊蚕窭是紊鑫实物幻数爨，所隧在鹜形篷醚中实魏鼗援的采集裁成为关篷缝昀阏 题。阁形的匹配和攒接，怒以实物模望为蕨始参考依据的。对于各种实物可以采用 刁i 1 刊的方法获得它们的数字信息，具体用何种方法取决于其本身的形状的复杂程度 和现有的设备。近年来有很多设备都可以获得实物的数字信息，其中、泛使用的激 光扫描工具( l a s e rs c a nt 0 0 1 ) 是取得高质鹫数字样件的理想设备，但它的可移动 性差，对较大蟾实物往往也是无毵为力。这时，蠲这些实物的黧像获褥数据信息是 - - q , - g 较好麓方法。本牵魏实物懿数字纯弱灏遂行论述。 2 2 碎片的数字化 2 。2 1 实物的数字纯介绍 实物的数字化是通过特定的测量设备鞠测摄方法获取实物离散点的几何坐标 数掘的过程。目前的实物数字化方法，根据测缀探头或传感器是否和实物接触，可 分为接触式和非接触式两大类，见表1 1 。其中三坐标测量机( c m m ) 和激光扫描 测量和三维数字照相是广泛采用的两种测量方法。c 肼测量通用性强、测量范围大、 糕发赢，瑶手动溅量羁缡缓艇娥扫稳路径遵嚣点位测量，适合予具有复杂内嫠型愁 静工 拳和几何复杂匏羚形裁 蠢：i 潮量，班及复杂边界、特征棱线的测繁。但总体上， 三坐标机测量速度慢，工作摄大，测量精度受环境温度、噪声等的影口吼数据还需 进行测头半径补偿。激光测摄是最近发展起来的测量技术，其速艘快，精度较高， 应用比较广泛。三维数字照相是9 0 年代初期开始发展起来的测趱手段，主要适合 子三维蠢由表露的测量，可以在几秒钟内测量褥到百万以上鲍数掇点，也可 盖直接 赣出三熊鼷穆模型，瑟显有些产品戆够垂动完簸多享燕溪量黥数据袋掰合，姨瑟辕出 一个繁体的点云形式或三角网格形式的数字化样件。 一维碎片拼台技术研究 通过测量设备所测得的数字化样件，需进行数据预处理 13 1 ，主要日的是型+ 据平 滑、排除噪声数据和异常数据、压缩和归并冗余数据、遗失点补齐、数据分块等。 数据平滑通常采用标准高斯、平均或中值滤波算法，高斯滤波能较好地保持原数据 的形貌，中值滤波消除数据毛刺的效果较好，应用时可根据数据质量和建模方法灵 活选择滤波算法【1 4 1 1 5 。数据简化是减少数字化样件中存在的大量冗余数据，由于数 字化样件的存在形式不同。对于不同的数据，可采取不同的简化方法，有序数据呵 采用等闻距采样法、倍率缩减法、弦偏离法等简化算法，这些简化方式将在2 9 节 中介绍；对于散乱的无序数据，可选择随机采样方法、均匀栅格法( 均匀分布密度 法) 等。 为了得到数字化样件的模型，我们需得到其相关的几何信息，如长方体的面、 边和顶点，圆柱的半径和高，某截面的截面线，复杂自由曲面的曲率分布图等。从 数字化样件中获取这些几何信息的过程被称为对数字化样件的虚拟测量。通过对数 字化样件的虚拟测量，进行模型的特征分析、识别和提取。 本文中数据的采集是对实物的b m p 图像进行分析处理后得到的。 2 2 2 利用碎片位图获取信息 2 2 2 1 位图文件的存储格式 图像处理技术已经渗透到人类生活的各个领域并得到越来越多的应用，图像处 理所涉及的图像格式有很多种，如t i f 、j e m p 、b m p 等等，工程应用中经常要处理 2 5 6 级的灰度b m p 图像。b m p 灰度图像作为w i n d o w s 环境下主要的图像格式之一， 以其格式简单，适应性强而倍受欢迎。这种文件格式就是每一个像素用8 h i t 表示， 显示出来的图像是黑白效果，最黑的像素的灰度( 也叫做亮度) 值为0 ，最白 的像素的灰度值为“2 5 5 ”，整个图像各个像素的灰度值随机地分布在0 到 “2 5 5 ”的区间中，越黑的像素，其灰度值越接近于0 ，越白( 即越亮) 的像素， 其灰度值越接近于“2 5 5 ”；与此对应的是在该文件类型中的颜色表项的各个r g b 分量值是相等的，并且颜色表项的数目是2 5 6 个。本文的数据采集是基于2 5 5 色的 南京航窀航天大学坝卜学位论文 b m p 位图文件。耍从b n i p 图像文件中获得碎片的采样数据，就要知道图像文件的数 据存储格式。 在进行图像处理时，操作图像中的像素值就要得到图像阵列：经过处理后的图 像的像素值需要存储起来；显示图像时要正确实现调色板、得到位图的尺寸信息等。 b m p 位图包括位图文件头结构b i t m a p f i i ，e h e a d e r 、位图信息头结构 b 1 1 、m a p l n f o h e a d e r 、位图颜色表r g b q u a d 和位图像素数据四部分。处理位幽时要根 据文件的这些结构得到位图文件大小、位图的宽、高、实现调色板、得到位图像素 值等等。位图文件的存储的主要结构如表2 一l 。 b m p 位图文件迂缩有压缩和未压缩两和，因为图像的数字化处理主要是对图像 中的各个像素进行相应的处理，而未压缩的b m p 图像中的像素数值正好与实际要处 理的数字图像相对应，这种格式的文件最合适我们对之进行数字化处理。 图像的像素值在文件中的存放顺序为从左到右，从下到上，也就是说，存b m p 文件中位图数据区首先存放的是图像的最后一行像素，最后才存储图像的第一行像 素，但对于同一行的像素，则是按照先左边后右边的顺序存储的：在v c 中只要得 到这些数据区的指针，就可以象操作数组一样获得像素点的狄度值。 表1 2 位图文件存储的主要数据和格式 偏移量大小内容 0 0 0 0 h 2 b y t e表示文件的格式，如“b m ”为位图文件 0 0 0 2 hl d w o r d 用字节表示整个文件的大小 文件头信息0 0 0 4 h 1 d w o r d 从文件开始到位图数据丌始之问的数据 偏移量 0 0 0 1 2 h1 d w o r d 位图的宽度，以像素为单位 0 0 0 1 6 h1 d w o r d 位图的高度，以像素为单位 0 0 i c h1 d w o r d 每个像素的位数 0 0 2 2 hl d w o r d 用字节数表示的位图数据的大小。该数 图像信息头 必须是4 的倍数 0 0 2 6 h1 d w o r d 用像素米表示的水平分辨率 0 0 2 a hl d w o r d 用像素米表示的垂直分辨率 调色板数据 0 0 3 6 h n * 4 b y t e 图像数据 0 0 4 3 6 hxb y t e 该域的大小取决于压缩方法，它包含所 有的位图数据字节，这些数据实际就是 彩色调色板的索引号 位图数据区记录了位图的每一个像素值或该对应像素的颜色表的索引值，图像 记录顺序是在扫描行内是从左到右，扫描行之间是从下到上。这种格式我们又称为 = 维碎片 f 台技术日f 究 b o t t o m _ u p 位图，当然与之相对的还有u p d o w n 形式的位图，它的记录顺序是从上 到下的，对于这种形式的位图，也不存在压缩形式。位图的一个像素值所占的字节 数：当h j b i t c o u n t1 时，8 个像素占1 个字节；当b i b i t c o u n t = 4 时，2 个像素占1 个字节；当b i b i t c o u n t = 8 时，1 个像素占1 个字节；当b i b i t c o u n t2 4 时，1 个像 素占3 个字节，此时图像为真彩色图像。当图像不是为真彩色时，图像文件中包含 颜色表，位图的数据表示对应像素点在颜色表中相应的索引值，当为真彩色时，每 一个像素用三个字节表示图像相应像素点彩色值，每个字节分别列应r 、g 、b 分量 的值，这利候图像文件中没有颜色表。w i n d o w s 规定图像文件中一个扫描行所占的 宁节数必须是4 的倍数( 即以字为单位) ，不足的以0 填充，图像文件巾一个扫描行 所占的字节数训算方法： d a t a s i z e p e r l i n e = ( b i w i d t h * b i b i t c o u n t + 3 1 ) 8 ：一个扫描行所i f 的字节 数 位图数据的大小按下式计算( 不压缩情况下) ： d a t a s i z o = d a t a s i z e p e r l i n e * b i h e i g h t 。 2 2 2 2 碎片图像的获取 获取碎片的图像有多种方法，它主要取决于碎片本身的特性。具有表面为平面 特征的可以使用扫描仪，如纸碎片、瓦片、壁画、油画等。另外还可以使用照片或 电视图像获取更多的碎片信息，如形状、颜色等。但对于一些三维的碎片，如陶器、 石头等，它们匹配的轮廓曲线是三维的，每个碎片就必须从不同的角度获得两个和 多个图像，根据光学三角形法恢复出轮廓的三维数据。在本文中只讨论平面碎片的 情况。 图2 1 碎片图像图2 2 分离出的单个碎片 南京航空航天大学硕f 学位论文 有时，当两个或多个碎片同时扫描或拍照时，首先要做的事是把这些幽像独立 地分离出米。在算法中使用以下的思想：设图片大小是k ”v ，其中h ，n v 分别 是水平和垂直方向的像素值，则r = o n ，一1 o n 。一l 】是该图像的像素域。设像素 位置p ( n x ，n v ) e r ，v ( p ) 为该象素点的灰度值( 强度) 。假设背景的狄度是 d 。 印。使用简单的阀值算法( t h r e s h o l d i n ga 1 9 0 t it h i n ) ，设存在一个唯一的 灰度值如印，当v ( p ) 瓦印则p 点属于背景上的象素点；当v ( p ) 氐印时，p 点 为碎片上的象素点。 在多个碎片的图像中，各个碎片不能有重叠现象，在多碎片的剀中各碎片应该 有明显的光环( 边界) 。 2 3 碎片的轮廓提取 2 3 1 理想模型与实际模型 本文的研究是基于对实物碎片的特征提取。我们把碎片的模型分为理想化模型 和实际模型两种。 理想化模型【1 6 1 可以概括为： 碎片的表面光滑，这些表面被裂纹随意地分成两片或更多片，它们之问的分割 线( 裂纹) 足任意的且没有宽度。 如果两片共用一段轮廓，定义它们为相邻的两片，即两片的边界匹配。 赢 ( a ) 碎片网络幽 c o ) 碎片邻接图 图2 3 碎片网络图和碎片邻接图 把碎片的理想边界线画在图上，把这个图称为碎片网络图( f r a c t u r en e t w o r k ) 如图2 3 。把三个或更多的裂纹或边界的交点叫做角点( i d e a lc o r n e r ) ：碎片 的边界称为轮廓( c o n t o u r ) ，它是由一个或多个裂线和边串联而成。 把这些碎，之间的关系看作是一个拓朴图，每个碎片的边是一封闭的轮廓， 即轮廓简单封闭，碎片之间的关系可以描述为如图2 3 ( b ) 所示。 理想的轮廓和裂纹线仅仅是一个抽象，它与实际的观察轮廓还有很大的不同。 把实际观察到的碎片的轮廓叫做观察轮廓( o b s e r v e dc o n t o u r ) ，它与理想轮廓的 不同主要有以下几个原因： ( 1 ) 存在着钩状毛或芒刺，如被撕破的纸的轮廓。 ( 2 ) 存在被磨损或腐蚀的轮廓。 ( 3 ) 可能有丢失的部分。 山于这此原因从而使相邻的两个碎片相匹配的轮廓有些小f 司。如图2 4 。图 25 中是一对相匹配的部分，它们分别属于两个观察轮廓，但对应于同一个理想的 裂纹线。 理想碎片 图2 4 观察轮廓 2 3 2 碎片轮廓的提取 片 图2 5 相匹配部分 当分离出单一的图像以后，就可以提取碎片的轮廓，它是一个封闭的多边形。 假设图像的背景的灰度是一致的，均为a m i n ，碎片上的灰度也是致的是氏a x 。根 据图形学的理论，颜色的变化是有一定梯度的 2 ”，边界的算法是：“栅格沿边界 逆时针移动”。 取边界上的灰度为 。j：8min_+-amaxa ，也就是说，在边缘附近取灰度为m 取边界上的灰度为 。d = _ 一，也就是说，在边缘附近取灰度为 鲥的象素点为碎片的轮廓所在点。 事实上，确定甜这个阀值很熏要，取得过大或过小都不能f 确反应实际边 界的情况。过大，会使采样的轮廓减小；过小会使采样的轮廓增大。如图2 - - 7 中 表明阀值耐对采样轮廓的影响。背景的灰度是：1 0 ，碎片的灰度是2 0 0 。 图2 6 占m 。d 阀值对轮廓的影响 图2 - 6 中a 轮廓线是在j 。= 1 0 5 获得，b 轮廓线是在占。= 2 0 0 获得，c 轮廓 线是在占。= 3 0 下获得的。 把所得的图与实际情况相比较，取耐= ( 1 0 + 2 0 0 ) 2 = 1 0 5 是比较合适的。 为了提取轮廓，假设有一栅格，它的边长为t ，栅格上相邻的点( a ，b ) ，其中a 点 在图像的碎片内，v ( “) 是a 点的灰度值( v ( a ) 鲥) ，b 在图像中的碎片外，v ( 6 ) 是“点的灰度值，( v ( 6 ) 甜) ，把栅格沿逆时针移动并保持这种状态。在栅格移 动过程中会依次出现以下的几种情况，如图2 - - 7 。 ( b ) ( c ) 图2 7 提取轮廓中可能的情形 对于上图中的图( a ) ，点a 在点b 的正上方，在算法中保证a 点在内，b 点在外 可能会出现以下几种情形： 。一 三竺壁! ! 丝立鎏娄竺! !一 _ _ _ _ _ _ _ _ h _ _ _ 。- _ _ _ _ _ _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ - _ 。_ _ _ _ _ _ _ _ 。一一 。一 ( a )( b ) ( c ) 幽2 8 对图2 7 ( a ) 改变步长的几种情形 在霾2 7 中翡其它溪瞧有类强弱德嚣。 椴据以上算法我们将得到有序的点对( q ，6 ，) ，其中的d 。( 满足v ( a ，) 民。) 沿 着轮廓在内侧，b i ( 满足v ( 岛) 民。) 沿轮廓在外侧，那么轮廓线上的点p ，可用 插值求出。在本算法中朋以下算式求出： 搬p 曛序边起来，就可以得到轮廓多边形p o ，a 以，这个多边形的边不是。 令窟氏，题是一个胰0 2 漆交长度，其中拶是疆敬壤捂载边长。 这萃孛蓥法的饶点是：碎片中心辩近一定区域内灰疫篮豹变化不会影响采样结 果； 遮个算法存在它的局限性： ( 1 ) 对于边缘存在毛刺、卷边或螺旋线的边就存在不确定性； ( 2 ) 在实际应鼹中，躲暴翦曩懿颜色( 磷冀簌色) 是随惹点褒变优蕊( 特爨 是吝边界附近) ，或是个点的函数，那么，瘸难一的磊l a x 柬代褥它，所产生静误 差就比较大。对于这种情况，计算就比较复杂，可以采用巧矗a x ( p ) 来代替d m a ) ( 。 “栅格沿边界逆时针移动”算法的伪代码如下： l o a d ( b it m a p ) ：读取位图文件 n x ：g e t w i d t h ( b i t m a p ) ； 诗算位图宽度，l 基像素点为单位 n y = g e t h i g h t h ( b i t m a p ) ；诗雾位强高度，以豫素点为攀位 1 p d i b b i t = g e t d i b b i t s ( b i t m a p ) ：获得位图数据区的指钳 t = s e t g r id 0 ： 设鼹栅格的连长t ，以鲸索作为单位 设定栅格的初始位鬣，p o 表示在碎片外的点，p i 表示在碎片内的点 s e t b e g i n ( b i t m a p ) ： 华华 茚 南京航卒航灭人学硕士学位论文 集 p o 0 = s e t b e g i n ( b i t m a p ) x ： p o i = s e t b e g i n ( b i t m a p ) y ： p i 0 = s e t b e g i n ( b i t m a p ) xt p l 1 = s e t b e g i n ( b i t m a p ) y - l 定义两个数组，a i n s id ebo u t s i d e ，分别表示碎片内的点集和碎片外的点 p o s i t i o n 一l r r a y a i n s i d e ： p o s n i o na r r a yb o u t s i d e ： d ( ) x o = p o 0 ： y o = p o 1 ： x i = p i 0 ： y i - p i 1 ： a _ in s i d e ，a d d ( p ( x i ，y i ) ) ： bo u t s i d e a d d ( p ( x o ，y o ) ： i f ( y o = - y i t )如图2 7 ( a ) ( 计算p o 0 p o i p i 0 p i 1 g e t p 0 0 ： g e t p i 0 ： ) e l s eif ( y o = = y i + t ) 如图2 7 ( b ) g e l p 0 0 ： g e t p i 0 ： ) e l s ei f ( x o = x i + t ) 如图2 7 ( e ) g e t p 0 0 ： g e t p i 0 ： e 1s ei f ( x o - x i1 ) 如图2 7 ( d ) 维碎片拼合技术科究 g e tp 0 0 o e tp i0 w h i l e “b e g i np o i n t 0 ) ； 下图是实际提取的轮廓。在v c 6 0 中通过o p e n g l 显示出米的。 图2 - 9 碎片实物照片 图2 1 0 采样 堕垒堕塞璺丕查兰婴主兰焦丝= 三； 图2 - 1 1 采撵 图2 一1 2 采样 二维碎片拼合技术研究 图2 。1 3 采样 图2 1 4 采样( c ) 中局部放大 6 南京航空航天大学硼叶+ 学位论文 2 4 碎片轮廓数据处理 2 。4 。1 丢失碎片与麓点的处理 在实际的碎片中往往存在有微小的碎片丢失，从而使获得的模型与理想模型有 一定的误差。可以把丢失的碎片的轮廓看成是具有噪音( n o i s e ) 的轮廓，如图 2 “1 5 ( a ) ，也可以看成是理想的碎片不完全旺黼，如图2 1 5 ( b ) 。可以在实际的算法 给予羚偿。 强2 一 5 不完全餮片模型 国) 在轮廓的匹配中较难的是确定匹配的起始点和终止点，大多数情况下是角点担 当起止点的角色，但有时并不能能精确的定义相匹配部分的角点。角点的不确定有 聪种情况： ( 1 ) 薅冀熬本身没有鞠鑫戆霭点； ( 2 ) 由于嗓音雨不能确定角点。这种情况下，算法就根据两个轮廓之间的匹 配条件，任意取起始点昔口终止点，然后看实际的匹配效果。 在实际相匹配中，碎片的角点最理想的情况是：是三条理想的裂纹线相交，或 一条裂纹线两个边界线稽交，形成y 形。但是，有的对候往往是两聚翰靡线接近1 8 0 0 ， 与篱三条线穗交，郄藏为i 形，这耱角点浚形戴，实舔上藏稿当予秘条壹线相交两 成。还有一种更糟糕的情形是，裂纹线没有明暇的相交( 或者说是潮弧过渡) ，根本 就不存在角点。所以基于以t 这几点，找角点从而得到匹配起止点有时是行不通的。 二维碎片拼台技术酬究 2 4 2 噪音的处理 螽l 采撵点所筮畿楚数字模型明佟数字撵馋。遘常，要黯获墩瀚羧亨鞲赣- 送行滤 波，滤波的主要目的怒：去除毛刺和嗓音。崮予受各种因素的影响，物理的因素( 小 的碎片的丢失，磨损、边缘的腐蚀以及表面的不规则) ，仪器的因索( 视觉、阴影、 图像的摄化) ，这样在数字样件中会存在各种隰麓( 如数据、噪音数据等) ，如不消 除，这挞误差数据将会直接影响重建模型的质量，从而影响匹配，因此在模型重建 之豁。竣要对数字进行滤波喾处理。数掘敬麓倔移数据敬光瞩是数爨预处理的瑟令 重要缀成部分。 数字化样件中包吉备种不理想的数据。对锚误韵数据，可用交互处理的方法进 行去除：对于误差数据，大体可分为毛刺数据和噪音两种。对于毛刺数据，可以1 ) 直接删除；2 ) 将这点移到一个中值点；3 ) 在允许的误差范围内，将其沿某一方向 移动一段距离。 现有憨直接管对数攒点黪滤渡方法镶多圈渊，本文实鬟载鸯澎数褒豹滤渡。j 数 据的缀织形式无关，其基镄是k 一邻近酌建立。滤波后的数据点的颛点可硝矢量表示 为： p 。= p 0 “+ d d ( e o u ) 其l 毒= ld ( p ) 为所调整的鼹离自量，d 为调熬戆步长参数。 ( 2 2 ) 待过滤波的数据点p 佟切线，弼k 邻近点粲x = 只，毪，k 中的数据点b 到 此切线的有向距离为西n 。通过对有向距离丽n 的滤波，可实现数据点p 的滤 波。滤波器的阶数据可取不大于k 的整数。 ( 1 ) 平均滤波 半均滤渡毪i 鼙均篷滤波，是一耱筏单懿线拣滤波。一次滤波螽数据点p 煎法矢 取为点集x 的数据点的法矢的平均值；相应地，式( 2 2 ) 中的有向踬离向量d ( p ) 可 取为： 1 一 d ( p ) = ( p e n 冷 ( 2 + 3 ) vi 在实际诗篓是采蘑毅均蜜兹方法送行笺纯。德褥注意赘是：当k 麴取缓缀夫嗣， 均值滤波会使数据趋予平黼，丢失匹配的信慰，但可以通过调整d 的取值，在细节 保留与滤波效果之问达到平衡。 ( 2 ) 中值滤波 中德滤波也是一种简荦的线性滤波d 剑。与均值滤波相比，这时新的法矢取为点 集x + p ) 的数据点的法矢的中问值，式( 2 2 ) 中的有向距离向量d ( p ) 驳为点集x 中的数据点b 剑切线的有向距离面n 的一个中间值： d ( p ) = ( m 。d ( p p i n ) ) n(d)：_ 2 e l 法矢的中间值通过点集工+ p 巾数据点的法矢与数据点p 的法欠的夹角来实 现，耿为与夹角的中间值相对应的点集x 中的数据点的法矢。当数据一( 的法矢为正 则化的单位法矢时，法矢之间的夹角可等价地转化为法矢差的模米实现。由于最大 如， = d e ( i h 2 c y 7 2 垒= a e 一上2 0 - 2 ( 2 5 ) 一般用小- p 2 盯2 的滤波器。仃2 = 当时，3 3 阶高斯滤波器为： 3 g 铂渊扣， 。， 山连续高斯分布求离散模板，需经采样、量化和模板归一化等操作，由丁阶数 。：2 。2 0 - 2 + 1 的一维高斯滤波器的未归一化模板正好为杨辉三角形分布，而被得到 。者( ! 二! ) ( 2 - 7 ) 如1 x 6 阶高斯滤波器为q = - 去( 1 51 0 1 05 1 ) ，据此也不难得出6 x 6 阶高 斯滤波器6 g ：q t q 。 山于点集巾的数据点p i 是按到数据点p 的距离从小到大排序的( 将这些距离值视 x 十f p j 巾的前m 个数据点的法欠进行高斯加权求和，即为滤波后数搦点p 的法矢 m 同样，可对这m 个数据点到切线的距离进行高斯加极求和，便能得到式( 2 ，2 ) 中 韵弱整距裹向餐d ( p ) 。 高新滤波能避免平均滤波的缺点，较好圭氇消除嗓声数据的影响，同时它的滤波 阶数也为濑新采样提供了统一的步氏( 见n y q u i sl 采样) ，所以本义采用高斯滤波。 图2 i 7 是通过滤波后得到的轮廓。 圈2 1 6 滤波前的原始采样离图2 一1 7 高斯滤波后的离散点 2 。4 。3 重薪采样 在保证图形不失真的情况下，为了简化计算，提高运算速度，滤波后要重新进 行采样，采样的方法有以下几种。 1 均匀采样法 均匀采槎法是掇摇数据点麴存镤颓序，每鹣掰一1 令鼗据点暴取一令数据点，其 它瓣鼗赛点鄂被忽略，这墨静m 称为采样闻隔( 或聚群率) 。 当均匀采样法应用于有序数据( 如扫描线数据) 时，便成为等间踞采样法；而 应用于非有序数据时，由于数据排列的无规律性模拟了均匀采样的随机性，因而成 为随机采样法。对于稠密的数字化样件，均匀采样法是一种常用的快遍简化方法。 在本文中出可以采用。 南京航空航天人学硕士学位沦文 2 弦偏离采样法 弦偏离采样法有两个控制参数：极限弦偏离值6 和最大弦长l 。此方法的采样 过程为，在最大弦长上内，所有弦偏离小于6 的数据点都被忽略，换句话说，只有 达到最大弦长的数据点或弦偏离值不小于6 的数据点才会被采样到，图2 5 是弦偏 离采样法的程序流程图。 实际上，若用累积弧氏代替上述算法中的弦长参数，在数据抖动大的地方，采 样率提高，能采相对多的点，这对于以后的轮廓匹配是有益的，囚而，对于数据质 量本来就不是很高的数字化样件，这种处理方式更有效。这可以用于毛刺较多的声 合。 图2 1 8 弦偏离采样法流程图 3 n y q u i s t 采样 滤波以后所要行重新进行采样，根据奈奎斯特( n y q u i s t ) 频普特一p i t 3 5 ，即要从抽 样信号中无失真的恢复原信号，采样频率应大于2 倍信号最高频率，即奈奎斯特采 样频率为信号最高频率的两倍。工程上的采样频率一般为奈奎斯特采样频率的2 - - 3 倍。设轮廓的长度为l ，有b 个采样点，轮廓的滤波阶数是 ，经过高斯滤波后的 最高频率为丑4 3 6 1 ，则 。三2 。 ，4 上式可以写成 二维碎h 拼合技术研究 r 8 三 心2 l 百f 所以采样步i j = = 为d 拈丢2 南瑶 ( 2 8 ) ( 2 9 ) 从这罩可以看出来，各轮廓的采点n 。的范围可能各不相同，采样点的步长可以 用这个特性，采用统一的步长，这为轮廓的匹配提供了很好的相同条件 2 5 本章小结 本章讨论了从实物图像到采集有效数据的过程。实物的数字化是计算机建模的 基础，获得准确、有效的特征信息对后续的碎片拼合算法是十分重要的。对碎片的 数据采集可根据碎片的几何特征和物理特征采取不同的方法，采取不同的方法，木 文中是针对平面碎片的轮廓数据提取，是利用碎片的图像进行数据采样，这种方法 是低成本高效率的方法。b m p 图片是工程中常用的图片，图片中的主要信息保存在 图片文件的数据区，它相当于一个阵列，在提取轮廓采样点的算法中可以作为数绢 进行操作。由于采样后的数据通常存在着毛刺和噪音，影响建模质量，因此要采用 滤波的方法来减小和消除噪音。通过比较几种滤波方法，作者认为，用高斯滤波比 较好。但滤波也使很多匹配特征丢失，使匹配的候选增加。所以在确定匹配日、，还 要逐渐减少滤波的阶数，以便在候选中确定真正的匹配。 南京航空航天大学硕上学位论文 3 1 引言 第三章轮廓的b 样条拟合 要实现图形的匹配，碎片的拼合，直接用用由图像获得的采样点是远远不够的。 一方面计算的空间复杂度和时问复杂度很大；