（计算机软件与理论专业论文）文物碎片分类拼接及其并行算法.pdf

山东大学硕士学位论文 摘要 文物是古代社会生产、生活、科技、艺术等诸多信息的载体，是考古学重要 研究对象之一。由于自然和人为的原因，在考古挖掘现场通常出土成千上万的文 物碎片，如何从碎片快速拼接出一个个完整文物，是考古学家关心的问题。目前， 该工作主要靠手工完成，既耗费时间，也易于造成对文物的破坏。因此有必要计 算机辅助完成文物的分类拼接工作。一般地，计算机辅助的分类拼接主要根据获 取的文物碎片的几何、纹理等信息来进行，但由于文物碎片往往是大量存在的， 普通p c 机很难在短时间内完成该项工作，因此在并行环境下对程序进行改进是非 常必要的。 本文通过计算几何、图形学、并行算法等领域相关技术以及考古知识的应用， 研究实现了旋转体文物碎片分类拼接系统。首先根据i n s p e c k 三维扫描仪提取文 物碎片的三维点云信息估算碎片对应的旋转轴及其母线信息。根据母线的相似度 匹配来对碎片进行分类归档。对归为一档的碎片基于旋转轴及其母线等信息通过 旋转、平移等操作来进行拼接工作。这些工作都是基于c l u s t e r 并行实现的。本 文并对原拼接算法进行了改进，大大降低了拼接所需的时间。 本文主要贡献为： 1 研究实现了旋转体文物碎片的并行分类拼接系统 针对大量文物碎片进行分类拼接工作耗时较长的特点，采用肝i 消息传递机 制在c l u s t e r 环境下进行了并行化处理。并行算法采用主从模式，选取一节点为 主节点，其余节点为从节点。主节点首先负责将文物碎片分配给各个从节点，从 节点求取文物碎片的旋转轴及其母线信息，将结果返回主节点。主节点根据母线 相似性对碎片进行分类，并将归为一档的碎片分发给从节点，在从节点上完成拼 接工作。并将拼接结果返回主节点。 2 提出了新的基于母线相似度的碎片分类算法 根据母线特征点以及母线采样点曲率对碎片母线的相似度进行比较，将在设 定阀值内匹配的母线分为一档。该算法解决了碎片在纹理油彩特征丢失后的分类 问题。 3 提出了改进的求取碎片边缘轮廓以及拼接的算法 针对三维点云曲面边缘的特点提出了求取碎片边缘轮廓的算法。基于旋转体 文物的特点提出了新的文物碎片的拼接算法，该算法相对于已有算法大大提高了 运算效率。 关键词；文物拼接，旋转轴，母线，相似性，集群 l i 山东大学硕士学位论文 a b s t r a c t ac u l m r a lr e l i ci so n eo fi m p o n 锄to b j e c t sf o rr e a r c ho fa r c h a l o g yb e c a u 辩 a r c h a e o l o 舀s tc 锄o b t a i l li l l f b 珊撕o ns u c h 够p m d u c t i o l l ，l i f e ，s d e n c e & t e c t l i l o l o g y a r t 锄ds oo nf 而mc 山t i l 】r a lr e h c s b e c a u o fn a ：t u r e 缸dh l l l n a n g e n e r a 据df o r c e s ， n l e r e 喇s th u i l d r e d 锄d 也。呱锄出0 f 疔a g m e n t sa la r c h a e o l o 西c a le ) 【c a v 撕o ns i t e s 1 o w 协q u i c k l yr e c o n s 仃u c tc o m p l e t ec u l t l l r a l r e l i c sf 吣m 行a c d o n si saq u e s t i o n ， w i l i c h 缸c h o l o 画s t s 缸ei n t e r e s t e di n a tp r 骼e 1 1 _ l 量l i sw o r ki sf i i l i s h e dm a i l 蚵b y h a n dhi sn o to i l i yd m e c o n s 咖n & b l i ta l s o 也咀l a g e dt oc m 删陀l i c s s oi ti s e m e 喈e n tt od e v e l o pac o m pu t i 卅a i d e dr e c o n s 栅q c t i 锣s c 锄 e r a l l y ，c o m p m e r - a i d e dc l 罄s i f i c 砸o n 锄ds d t c ha r ep r i m a f i l yp e r f b 订n e do n m eb a s i so fg e o 咖，t 咖e t ci 响彻撕o no fr d i c 丘哼n 协h 0 w e v e r 鹊r e j i c 矗a g i n 锄_ t so f t l e i le 姬s ti i ll a i g eq l l 枷6 e s ；o f d i n a 巧p e r s o n a lc o r n p u t e ri sd i 伍c “tt 0 c o m p l e t et l l ew o r ki nas h o np e r i o do f 矗m e s op a r a l l e la l g o r i m mi s 舱c e s s a r yt ob e a d o p t e dt 0i m p r o v em ep r o c e d i l r e b 越e do nc o m p u t 撕o n a lg e o m e 臼c o m p u 妞g r a p h i c s 鹪w e l l 簪a r c h 0 1 0 矛c a l h l o w l e d g e ，w es t i l d i e da n dd 豁i g n e dac l 鹬s i f i c 撕o ns y s t e mo fr e l i cf a g m e n to f r o t 撕o nb o d yf i r 鸭3 ds c a 【1 i l e rh l s p e c ki sl l s e dt or e m e v e3 dp o i n tc 1 0 u di n f b m l 撕咀 谢t l l w 1 1 i c h r r e s p o n d i n g r o t a l i o na 妇s 锄dg e l l e 豫仃i xo f1 量l e s e 疗a g m 朗t sa f e e s t i m a t e d t h w em a t c h e d ，c l a s s i f i e d 瓤da r c l l i v e dt i e s e 仃a g 加e n ta c c o r d i n gt om e s h a p es i r n i l 撕母o fg e r 枷x f i n a l l y ，f o rm e 厅a 擎n e n t si i lt t l es 锄ed o c u m e m ，w e 如t c h e dt i l 锄b yr o 协d o n 锄d 仃锄s l 撕0 nm dp r e s e n t e d 锄l m p r o v e da l g o r i t h nw h i c h 掣e a n yr e d u c e dt l eo r i 萄n a ia l g o r i t h r n g 矗m ec o r n p l e ) d 够 n i a i nc o 耐b u “! sa f ea sf o l l o w s ： 1 c o m p l e t em ep 缸a l l e lc l 鹄s i f i c 撕o n 锄ds t i t c i l i n gs y s t e mo fr e l i c s 触g m 肌t a si tc o s 扭p l e n 哆o fd m et op i e c et o g e t i e ral a 唱e 锄l o 吼to fr e l i c s 丘a g 舢m t ， p a r a l l e lp r o c e s s i n gw 1 1 i c l lm a k eu s eo fm p im 舒s a g ep 越s i i l gm e c h a l l i 蛐i sa d o p t e d p r i n c i p a l s u b o r d i n 甜em o d ei se m p l o y e di i lp a r a l l e la l g o r i 血m ，w h i c hm e a l l san o d ei s p i c k e do u t 罄p 血c i p a ln o d e 舡1 dm eo m e r sa r es u b o r d i i l a _ t en o d 器t h ep 血c i p a ln o d e t a k 嚣c h a 唱eo fd i s 硒b “n gf e l i c s 疔a g m e mt os u b o r d i n a t en o d 既锄dg e t 础 o m a t i o n a b o l i ta ) 【i sa n dg e i l e r 撕xf 如ms u b o r d i n a t en o d e s c o n c r e t e l y 右r s t l yt h ep r i n c i p a l n o d ec l a s s i 丘e sr e l i c s 丘鸹m e n tb 嬲eo ng e n e r 枷xs i i i l i l a r i t ys e c o n d l y 血ep 抽c i p a l n o d ea s s i 弘sc o n g e n e rr e l i c st os u b o r d i n a l en o d e t h i r d l y ，丘a g m e mi ss 6 t c h e di n i i i s u b o r d i n a t en o d e f i n a l l y r 韶u i t sa r er e t l l m e dt ot 1 1 ep 咖c i p a ln o d e 2an e wc l a s s i f i c 撕o na l g o 一吐l i l lo ff a g n 瑚ti sp r e s 锄t e d b a s e do nt l l es i i i l i l 撕t y o fg e n e r a 缸xo fr e l i cf h g m e m a c c o r d i n gt o 也ef e g c u r ep o i ma 1 1 ds 锄p l i l l gc u r v a _ t l i r eo f 血ef a g i n 朗tg e n e r a t i 咄 w ec o m p a r et i l e s i i i l i l a r i t yo fg e n e f a t r i 墨龃dc l 笛s 毋t h o s em a t c h e d 埘“n 也e m r e s l o l dv a l u es 时i na d v a n c e 血t oo n ed o c u m e n tt h ea l g o r i 血ms o l u l 嚣st i l e c 1 鹅s i f i c 撕o i lp r o b l e m1 置l a tt e 舢ef 毫a t u r 鼹o f 矗a 粤n 髓t si si nm el o s s 3 ， a i l i m p r o v e dp r o f i l ec o m p 咖go ff a g m e n t 觚ds d 埘n ga l g o i i m mi s p r e s e n t e d a c c o r d i n gt 0f e a c i l r 贸o f3 dp o 疵c l o u ds i l | 髓c ep e r i p h e 觋w e 萄v ea i l 印p r o a c l l t 0c o m p u _ t et 王1 e n t o i l ro fr e l i c 丹a g m e n t s b a s e do nm em t 撕o nf e a 觚e so fr d i c s ，a n e w 妇t c h i n ga l g o r i 也mi s 百v e l l ，w 1 1 i c h 掣e 砒l yi m p r o v e de 伍c i e l l c yo fn l eo f i 百n a l k e yw o r d s ：f r a g m e n t - s d t c h i n g ，m t a r y ，g e n e r a t r i i ，s i m i i a t y ，c i u s 把r 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：j 邀确步日期： 关于学位论文使用授权的声明 盆 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名- 弪望鳓签名： ，。，。尘苎：垒耋童垦耋二叁曹垒耋_ - 。，一 1 1 研究背景 第一章绪论 古文物是先民文化累积的重要遗产，为考古学家充分了解古代的习俗、生产 力发展水平、生活状况提供了重要的佐证。尤其是古陶器，是考古发掘的断代器 物，陶器形制和装饰的变化反映了不同文化的地理分布和传播。特别是在尚未发 明文字的地区和时期，不同风格的陶器是理解该地区文化发展和变异的线索，是 一种最可靠的记时器。 但由于自然与人为原因，文物往往受到破坏，发掘现场中最常见的是各种各 样的文物碎片，需要进行文物修复。文物修复是指在确保文物安全的前提下，最 大程度地忠实复原本来残缺不堪的文物。文物修复需掌握化学、材料学、工艺美 术、历史等各领域的知识与技术，它的贡献不仅在于文物的修补，有益于进一步 的文物研究和鉴定，从长远的意义上来看更有利于人类文化遗产的持久保藏。目 前，文物的修复大部分是手工完成。 古陶瓷的修复对于考古和很多文物研究是必不可少和经常进行的工作，且文 物修复需要投入大量的人力和物力，仅一厘米左右的裂缝或缺口，就需要l o 天 左右的时间精心复原，工作量很大，而且易于造成对文物的破坏。 计算机技术的快速发展，尤其是计算机图形学、图像处理、计算几何、模式 识别技术以及硬件设备的普及，使得计算机辅助完成文物分类拼接成为可能。计 算机辅助工作一般需要以下四个主要步骤： ( 1 ) 预处理：包括数据的获取，几何、纹理等特征信息的提取等； ( 2 ) 分类：从大量的碎片中根据几何特征和颜色纹理等信息把来自同一文 物的碎片归为一类； ( 3 ) 拼接：在分类的基础上，对碎片进行局部匹配和全局匹配： ( 4 ) 修补：补全丢失的几何和纹理信息。 1 2 研究现状 目前，国内外许多大学和研究所都针对文物修复工作展开了研究。山东大学 对计算机辅助文物复原中的若干重要问题进行了研究，取得了不错的效果，本文 的工作就是以此为基础展开进行的。国内西北大学利用形状匹配技术已完成了计 算机辅助文物复原样机系统，实现了对破碎文物的自动匹配、三维复原，但仍需 自动拼接与手工调整相结合的方法。文献 1 中利用两条轮廓线的哈希矢量来分 析曲线段的相似性，解决空间瞄线匹配达到文物碎片复原的方法，并利用文物拼 接知识库提高碎片拼接的智能性。国外维也纳理工大学利用提取碎片轮廓线的颜 色特征和形状特征进行分类拼接 2 ：土耳其的安卡拉中东理工大学提出了基于 曲率和挠率的三维曲线匹配的方法，也可适用于有裂缝的碎片 3 ；雅典大学的 g p a p a i o a n n o u 和t t h e o h a r i s 在 4 中提出基于边界线和曲面匹配算法快速 拼接碎片的方法。b r o 哪大学s h 8 p e 实验室针对旋转体物体的拼接进行了研究。 该方法着重研究如何基于每片碎片的局部信息获取文物的整体特征，如对称轴， 旋转体的外形轮廓曲线等，并利用贝叶斯模型确定碎片的位置，完成对物体整体 模型的估计 5 。 关于碎片的分类检索技术，在l 渤n p e lm 8 的基于轮廓线的归档系统中，他 们在计算出旋转轴和轮廓线的基础上，根据考古学知识和轮廓线的曲率及分割点 ( 包括拐点，局部最大点，局部最小点，口缘点，曲率变化大点，底部点，轮廓 线和旋转轴相交点，起始点和结束点) ，把轮廓线按层次分割为颈部，身部和底 部，使用描述性语言描述轮廓线的基元及基元之间的关系。但是他们的轮廓线是 利用通过旋转轴的一个平面和碎片相交的点集拟合而成，这样估计出的轮廓线不 精确。a n s l l 唧黜r a z d a n 9 的基于几何模型的三维陶瓷碎片的归档检索系统包 括用参数曲面表示模型数据，提取特征，使用x 扎组织特征和基于草图和基于文 本特征的检索。其中，文中的特征特指形状特征，分为四类：点特征，曲线特征， 区域特征和体积特征。 1 0 中在分析三维物体碎片轮廓曲线的特征和表示的基础 上，研究多尺度小波轮廓描述符的计算，提出了一种多尺度下轮廓曲线特征提取 及基于多尺度分析的三维物体碎片拼接方法。 对于文物碎片的分类，在本文中将其转化为了二维曲线的匹配问题。 1 1 中 基于图像之间相似性度量的h a u s d o r f f 距离对轮廓进行匹配。 1 2 中利用破碎物 体的轮廓曲线进行形状复原，采用曲率和挠率来对轮廓进行匹配。 1 3 中轮廓线 用多边形逼近表示，将多边形的本质参数连接点作为匹配的特征集。 对于并行化的研究，近几年也大量应用在工业和科学研究中。 1 4 中研究基 于高性能并行计算的水利水电大型科学计算平台体系和构建。 1 5 中讨论了f f t 可在p c 机群环境下的婶i 并行算法的设计思路，并对实际运行效果比较分析。 1 6 在船舶电力系统仿真中引入船i 消息传递接口标准对并行算法进行实现，取得了 比较理想的仿真效果。文献 2 3 详细介绍了船i 并行编程原理及方法，并针对一 些经典问题，给出了其并行算法及其实验结果。另外j a v ag r a d e 论坛将姗i 与j a v a 语言相结合，给出了i j a v a 开发包，使得应用j a v a 语言编写的程序也很容易实 现并行化处理。其组织的职j a v a 工程，则给出了肝i j a v a 应用的很好的例程。 1 3 论文的主要工作 本文结合部分已有工作实现了完整的文物碎片分类拼接系统，并采用肝i 消 息传递机制，在c l u s t e r 环境下采取主从工作模式组织处理器节点，通过n e t 文件 的分发，旋转轴及母线的计算碎片的分类以及拼接4 个步骤完成了并行文物碎片 分类拼接系统，取得了不错的结果。并且通过输入不同数量的碎片以及变换运算 节点的个数来对试验结果进行了详细的分析。 本文还针对基于纹理的分类算法的局限性提出了新的基于母线相似度的碎 片分类算法。新算法在通用性以及准确性上都比原有算法更好。提出了求取碎片 边缘轮廓线的算法并基于旋转体文物的性质对已有拼接算法进行了改进，新的拼 接算法在执行效率上比原有算法有了大幅提高。 1 4 论文的组织结构 论文的组织结构如下： 第一章着重介绍了本文研究背景和研究现状以及论文的主要工作。 第二章主要介绍了文章中所涉及到的相关知识。展示了m p i 的工作原理以及 集群的结构、框架以及构建工作。 第三章具体介绍了并行化的文物碎片分类拼接工作。在该章中首先介绍了文 物碎片分类拼接的串行系统，然后介绍了并行算法、试验结果以及对试验结果的 分析工作。 第四章主要介绍了基于曲线匹配度的分类碎片。在该章中介绍了母线的离散 化方法、基于曲率的曲线匹配算法以及文物碎片分类归档流程。 第五章主要介绍了旋转体文物碎片的拼接算法以及与原算法时间复杂度方 面的比较。该章首先给出了求取碎片边缘轮廓的算法，然后介绍了已有拼接算法 以及对该算法的改进，继而对两种算法时间复杂度进行了比较。 第六章对全文进行总结并提出了工作展望。 4 2 1m p l 第二章集群知识介绍 m p i 是目前最重要的并行编程工具。它具有移植性好，功能强大，效率高等多 种优点，而且有多种不同的免费高效实用的实现版本。几乎所有的并行计算机厂 商都提供对它的支持，这是其它所有的并行编程环境都无法比拟的。m p i 于1 9 9 4 年产生，虽然产生时间相对较晚，由于它吸收了其它多种并行环境的优点，同时 兼顾性能功能移植性等特点，在短短的几年内便迅速普及成为消息传递并行编程 模式的标准。 由于仰i 是一个库而不是一门语言。因此对好i 的使用必须和特定的语言结合 起来进行。c 是目前使用最广泛的系统和应用程序开发的语言之一，因此在船i l 中提出了肝i 和c 语言的绑定，并且给出了通用接口和针对c 的专用接口说明。 2 2 集群系统 2 2 1 集群系统简介 集群( c l u s t e r ) 技术可如下定义：一组相互独立的服务器在网络中表现为单 一的系统，并以单一系统的模式加以管理。此单一系统为客户工作站提供高可靠 性的服务。大多数模式下，集群中所有的计算机拥有一个共同的名称，集群内任 一系统上运行的服务可被所有的网络客户所使用。c l u s t e r 必须可以协调管理各 分离的组件的错误和失败，并可透明地向c l u s t e r 中加入组件。 一个c l u s t e r 包含多台( 至少二台) 拥有共享数据存储空间的服务器。任何 一台服务器运行一个应用时，应用数据被存储在共享的数据空间内。每台服务器 的操作系统和应用程序文件存储在其各自的本地储存空间上。 c l u s t e r 内各节点服务器通过一内部局域网相互通讯。当一台节点服务器发 生故障时，这台服务器上所运行的应用程序将在另一节点服务器上被自动接管。 当一个应用服务发生故障时，应用服务将被重新启动或被另一台服务器接管。当 以上任一故障发生时，客户将能很快连接到新的应用服务上。 2 2 2 集群的种类 从上面的工作方式出发，我们可以把集群分为下面几种( 特别是两节点的集 群) ： 1 ) 主主( a 商v e a c t i v e ) 这是最常用的集群模型，它提供了高可用性，并且在只有一个节点在线时提 供可以接受的性能，该模型允许最大程度的利用硬件资源。每个节点都通过网络 对客户机提供资源，每个节点的容量被定义好，使得性能达到最优，并且每个节 点都可以在故障转移时临时接管另一个节点的工作。所有的服务在故障转移后仍 保持可用，但是性能通常都会下降。 2 ) 主从( a c t i v e p 嬲s i v e ) 为了提供最大的可用性，以及对性能最小的影响，a c t i v e p 翘s i v e 模型需要 一个在正常工作时处于备用状态，主节点处理客户机的请求，而备用节点处于空 闲状态，当主节点出现故障时，备用节点会接管主节点的工作，继续为客户机提 供服务，并且不会有任何性能上影响。 3 ) 混合型( 矽b r i d ) 混合是上面两种模型的结合，只针对关键应用进行故障转移，这样可以对这 些应用实现可用性的同时让非关键的应用在正常运作时也可以在服务器上运行。 当出现故障时，出现故障的服务器上的不太关键的应用就不可用了，但是那些关 键应用会转移到另一个可用的节点上，从而达到性能和容镨两方面的平衡。 2 2 3 集群的可扩展体系结构 计算机系统体系结构差别并不大，关键在于互联技术、结点的复杂度和耦合 程度的不同。典型的集群系统的结构如图2 1 所示： ，。，。，叁垒釜茎坠土叁堡圣望，。，。，一 并干j ：编程环境用户接口作业调度或其他子系统 单- 系统映像基础驶施 系统级可用性支持 特定o s 扩展或中削件层 棠群节点棠群节点 l 棠群节点 操咋系统操作系统 l 操作系统 lll i 互联部件 l 存储区敛分布式 敛i o 其他使件资源 l 域网格内存访问 2 2 4 集群系统的构建 图2 1 集群系统结构 l j n u x 操作系统不断走向成熟，它的健壮性不断增强，并且提供了g n u 软件 和标准化的p v m 、m p i 消息传递机制，最重要的是l j n u x 在普通p c 机上提供了对 高性能网络的支持，这样就大大推动了基于l n u x 的集体系统的发展。相对于 w i n d o w s 操作系统，l i n u x 系统具有廉价、高效、自由开放的特点，因此选择l j n u x 操作系统作为集群各节点机上的操作系统。 整个环境的搭建分为3 步： 1 在各个子节点上安装m p i ，m p u a v a 下载m p i c h 、m p u a v a 开发包以及hp j a v a 。在n u x 下通过t a r 命令解压各压 缩包，然后应用来安装上述3 个开发工具包。 2 放权 集群系统的各个节点间需要进行通讯。为了能够在多个不同的机器上运行 m p i 程序，首先需要其它机器对启动m p l 程序的机器放权，即启动m p i 程序的机器 能够访问其它的机器。采用的是。r h o s t s 文件来放权，即在m p i 程序所要运行的各 台机器上，运行该程序的帐户进行访问。比如在s d u v r 0 0 1 机器的n e v e r i a n d 帐 户下，如果允许s d u v r 0 0 2 机器上的n e v e r i a n d 帐户对它进行访问，则需要在 s d u v r 0 0 1 机器上的n e v e r i a n d 帐户的h o m e 文件夹下创建一个r h o s t s 文件，在 该文件下加入如下一行信息： s d u v r 0 0 2n e v e r l a n d 在实际运行的时候，在整个集群所用到的每个节点上部建立相同的帐户名使得 m p i 程序在相同的帐户下运行。 3 配置可用机器 最简单的m p l 运行命令是：m p i r u n n pnp r o g r a m 。其中n 是同时运行的 进程的个数，p r o g r a m 是可执行的m p i 程序名。在此情况下，需要对集群环境内 可用的机器进行配置，配置文件是： $ ( h o m e ) m p i c h u t i l m a c h i n e s m a c h i n e s u n u x 。在这个文件中，每一行 的内容为一个可用的机器名。比如 s d u v r o o1 s d u v r 0 0 2 0 s d u v r 0 0 3 s d u v r 0 0 4 s d u v r 0 0 5 这样就有5 个节点可供使用。这样启动程序的时候，可执行程序必须放在不 同机器的相同帐户的相同目录下。 第三章文物碎片并行分类拼接系统 3 1 串行系统介绍 预处理 分粪拼接 亿 塞+ 蠢主+ 羹一 峥曩+ 襄一藉一轮+ 平+ 旋 段 化 矍 廓 移转 nnn l 数据摩 i 圈3 一l 文物碎片分类拼接流程 系统框架如图3 - l 所示，文物碎片分类拼接系统分为三部分：预处理，分类， 拼接。 程序的输入口是碎片以点云方式存储的n e t 文件，程序的输出是对于输入的 n e t 文件，程序的输出是所输入的碎片哪些能够归为一挡，归为一挡的碎片又能 否拼接在一起。 在预处理部分，程序接受入口传来的n e t 文件，对于点云信息，应用二次曲 面拟合，估计碎片上每个点的法向量，根据旋转体上任一点的法向量必与旋转轴 相交的规律，可得到旋转体的旋转轴，然后计算点云上的点到旋转轴的距离，据 此得到碎片的母线信息。然后求取母线上的特征点。整个预处理部分得到的就是 旋转轴以及母线。 在得到旋转轴及母线之后，首先根据特征点匹配对碎片进行初步分类，然后 对于不符合特征点匹配的按照曲率信息进行分类。 对于归档为一类的文物碎片，首先根据碎片分类母线匹配时所得到的碎片间 的相对位置将碎片沿旋转轴平移到做为完整文物一部分时所在的高度位置。然后 求取碎片的边缘轮廓线，求取碎片拼接所需要旋转的角度值以及旋转的方向。 整个碎片拼接过程结束后，程序输出为碎片是否能够拼接，如果能够拼接， 则将显示出拼接的结果。 在将整个分类拼接系统实现之后，又实现了该系统在山东大学数字考古博物 馆平台上的展示。原程序采用j “a 语言编写，因此将其修改为a p p i e t 小程序在网 络上完成了展示。 主页面如图3 2 所示：该程序主要是在博物馆平台上向用户展示文物碎片分 类拼接的全部过程。因此，采用让用户自己输入碎片的方式。在用户界面的右下 角有个上传碎片的链接点击此链接，将会看到保存在服务器上的所有碎片的n e t 文件。从中选择一个，点击提交，就会在用户界面的左侧显示出该碎片的信息以 及求得的该碎片的旋转轴及其母线信息。点击界面上的检索分类，如果有碎片与 该碎片可归为一类的话，则会在右侧显示出该碎片，否则会提出警告信息。如果 找到可归为一类的碎片，“拼合”才会变成可用状态，点击该按钮，如果两块碎 片可以拼接在一起，则会显示出拼接的结果，否则，会提出警告信息。在完成该 过程后，拼接好的两块碎片经过坐标变换变成整体存储到数据库中，在下次的匹 配过程中当作一个碎片使用。 图3 2 文物碎片分类拼接系统 。，。舞量茎叁堡釜兰曹垒耋- _ ，。一 3 2 并行算法的设计 图3 3 并行沉程 整个并行开发的过程如图3 3 所示，下面将该流程详细说明一下： 1 ：n e t 文件的分发 在程序中定义一个节点为主节点，负责文件及数据的分发工作，其余节点为 从节点，负责运算工作。我们在主节点上运行程序，主节点的m p i r a n k 为o 。其 余各节点的m p l r a n k 都为非零值。 程序运行流程如下： 步骤1 ：对存储n e t 文件名的数组加一标志f l a g ，用于主节点对数组进行操作 时加锁。如果节点r a n k 为o ，则向所有从节点发送一“计算母线”的信息。 步骤2 ：若节点r a n k 不为o ，则向主节点发送请求( c o m m s e n d ) 获得n e t 文件。在接收( c o m m r e “) 到主节点的回复之后，向主节点发送一确认信息。 步骤3 ：若节点r a n k 为o ，则等待从节点发送的请求。当得到某节点发送的 请求后，将f i a g 设置为不可用，读取一个n e t 文件发送给从节点。待得到从节点 的确认信息后，设置f i a g 为可用状态。继续等待其余节点的请求。 2 ：预处理运算 步骤1 ：如果节点r a n k 不为o ，对于接受到的碎片求取其旋转轴及母线信息， 结果以一维数组的方式表示，并将结果传回主节点。 步骤2 ：如果节点r a n k 为o ，且得到从节点发送的旋转轴及母线信息，则查 看n e t 文件存储数组，如果数组不为空，则按序取一n e t 文件发送给该节点。 3 ：碎片的分类 步骤1 ：如果节点r a n k 为o ，且已得到从节点返回的旋转轴及母线信息，则 保存该结果。如果已有得到的母线，则进行母线相似度的比较。 步骤2 ：如果节点r a n k 不为o ，则请求主节点索要n e t 文件。如果请求不被允 许( n e t 文件处理完毕) ，则等待主节点新的任务分配。 这样当主节点接收到2 个以上的碎片旋转轴及母线信息后，就进行碎片的分 类工作，每传回一份碎片的旋转轴及母线的信息，就与所有已有的母线进行一次 母线的相似度匹配工作。由于碎片文件的数目肯定大大多余计算节点的数目，因 此，每传回一份母线信息，就在主节点上进行分类比较。可以是主节点和从节点 共同处于运算状态，而使主节点不只是处于监听从节点信息，以及分配任务的状 态。 4 ：碎片拼接工作 步骤1 ：如果节点r a n k 为0 ，向所有从节点发送“拼接碎片”的信息。并将 碎片分配给从节点。每个从节点得到的都是归为档的碎片。 步骤2 ：如果节点r a n k 不为0 ，且接收到主节点发送到的归档碎片，则完成 拼接工作。并将结果返回主节点。 步骤3 ：如果节点r a n k 为o ，且接收到从节点发送回的拼接结果，则查看是 否还有未进行拼接的归档碎片。若有，则将其发送给该从节点。 ，。，。上叁圣茎坠土釜堡垄二窑，。，一 3 3 预处理 在将原串行程序并行化的时候，首先对原程序做些最基本的改动。这些改动 包括： 1 二维数组的修改 由于m p l 中只支持一维数组的传递，因此需要将原程序中大量的二维数组转 换成一维数组。而对于好多数组，比如存储点云信息的数组，由于二维数组是依 照点云扫描栅格的行列值建立的，因此需要在新的一维数组内留下存储原点云扫 描栅格行列值的位置。比如对于一个碎片，如果其点云数据的行值为，洲，列值 为c d ，那么在原程序中需要采用一个n o a t ，洲】【i 1 的二维数组存储，而在新的 程序中其需要采用一，伽d m 的一维数组存储，其中数组前两个元素分别为，驯 和，的值。 2 数据库的修改 对于原串行程序，在响l d o 邺系统下运行，在数字博物馆s q l s e r v e r 数据库下 建立的库和表。在集群环境下，如果还是访问原数据库的话，无疑会增加通讯的 时间。因此，在l i i l u ) ( 系统下，采用同样属于开源产品的时s q l 数据库。在此采用 埘，s q l 主要是为了在l i n u x 环境下应用的便利。 3 4 试验结果 选取手工分割的5 0 块碎片作为程序的输入来进行测试，以其中的1 l 块碎片 来展示一下程序的运行结果，每块碎片都定义了一个唯一的颜色，借此来对碎片 进行区分。1 1 块碎片分别来源于3 个文物，但黄色和浅黄色的碎片属于干扰碎 片，分类的过程中能够找到各自的归档，但并不能和归为一档的碎片拼接在一起。 考虑到考古现场经常会发现很多同样大小形状的文物，碎片来源的那3 个文物 中，其中的两个文物具有同样的大小和形状。这样的话，在分类的过程中，这两 个文物所产生的碎片将会归为一类，但在拼接的过程中就会将其区别开来。通过 这样更好的展示了该系统处理各类型碎片的能力。该l l 块碎片如图3 4 所示： “1一 图3 4 输入碎片 对于输入的碎片，我们在c l l l s t e r 下使用m p i m n r s h 命令执行编译好的目标文 件m p 眦惦e u m p r o j e c t ，运行界面如图3 5 所示： | 墨l3 5 ，配n c t 支1 午适f - 卉同 该过程提取出碎片的旋转轴及母线信息，在主节点上完成分类工作。所有l l 块碎片被分为两档，因为本来它们来自于3 个完整文物，且其中两个文物的大小 形状相同，即两个文物具有同样的旋转轴及母线，所以这两个文物所产生的7 块 碎片被归为一档，如图3 6 所示。另一个文物所产生的4 块碎片归为另一档，如 1 4 图3 7 所示。 图3 6 归档碎片l 图3 7 归档碎片2 如上两图所示，将1 1 块碎片根据旋转轴及母线分为两档。分为一档的碎片 具有相同的母线信息。 对于分档好的碎片，主节点将分为一档的碎片分发到一个从节点上完成拼接 工作。如图3 8 所示。 图3 _ 8 主节点分配碎片进行拼接 图3 - 9 拼接结果 拼接结果如图3 9 所示，1 1 块碎片共拼接出3 个完整的文物，另外两块碎 片虽然和其他的碎片归为一档，但没有找到可以与其进行拼接的碎片。 3 5 性能分析 表3 1 并行加速比计算 碎片数量加速比 处理嚣 5 0l o o s p c e d u p ls p e e d u p 2 l2 1 9 3 4 9 6 4 5 2 1 7 9 21 o1 o 3u o 9 8 4 4 2 2 6 2 9 3 31 9 7 “1 9 9 8 2 47 5 s 6 2 71 5 5 4 8 9 6 2 8 9 1 42 9 0 8 1 55 7 6 3 1 61 1 7 4 0 2 63 8 0 6 l 3 8 5 1 5 64 7 0 3 2 49 6 8 0 5 74 6 6 3 8 4 6 7 l o 74 0 0 8 3 68 2 5 1 9 05 4 7 2 25 4 7 9 7 衡量并行程序效率的一个重要指标是并行加速比。并行计算中的加速比是用 并行前的执行速度和并行后的执行速度之比来表示的，它表示了在并行化之后的 效率提升情况。即加速比= 使用一个处理器的执行时间使用具有，衍处理器的多 处理机的并行执行时间。并行执行时间是由三部分组成的：计算时间、通信时间 和并行开销时间，在并行计算中，它们分别记作：t c o m p 、t c o m m 、t p a r a 。并 行开销时间主要包括操作系统进行进程管理、分组操作和进程查询操作等的时 间：通信时间则主要是处理器间进行信息、数据传递等所要的延迟。该并行程序 的并行加速比结果如表3 i 所示。该表给出了当输入碎片数为5 0 和1 0 0 ，相应的处 理器数目为1 、3 、4 、5 、6 、7 时程序的执行时间，以及并行加速比。比如当c i u s t e r 是由5 个节点组成时，首先，其对于固定数量的碎片，其运行时间并没有达到单 个节点碎片的1 5 。因为在并行程序的运行时间中，还占有了通信时间和并行开 销。比如主节点向从节点发送n e t 文件就为通信时间，从节点向主节点传送中间 结果的网络延迟就为并行开销时间。这些时间都是单机运行时不曾有的。所以随 着c p u 数目的增多，程序的运行时间将会随之缩短，但并不是按比例缩短。正如 表3 一l 所示，随着处理器的不同，对于同等数量的碎片，程序的执行时间并不与 处理器数目成严格的反比关系。产生这种现象的原因是c p u 数目越多，节点间的 通信以及数据传输延迟就会越多，额外增加的时间也就越多。其次，对于固定节 点的节点数目，随着输入文物碎片数量的增大，程序的并行加速比也就越大。这 是因为随着碎片数量的增多，而节点数目不变的情况下，相应的运算时间将会增 大，即通信时间和并行开销时间在整个执行时间中所占的分量将会减小，使程序 的并行加速比得以增大。 第四章母线相似度匹配 4 1 碎片分类算法的提出 对于文物碎片的分类工作，【2 9 】中曾提出了基于文物纹理特征进行分类的算 法。其对碎片相应的纹理图像进行二维小波变换，提取小波特征向量作为纹理特 征。该算法基于隶属于同一文物的碎片具有相同的纹理来进行的。而对于好多文 物碎片来说，由于年代久远，碎片所携带的纹理已经残缺不全甚至全部丢失。 针对这种情况，本文提出了基于母线相似度匹配的碎片分类算法。该算法首 先将母线进行离散化处理，根据母线上采样点的曲率信息计算母线间的相似度， 以此对碎片进行分类。 4 2 母线离散化处理 在经过预处理阶段之后，得到了碎片所对应的母线信息，该母线是原完整文 物母线的一部分。也就是每块破碎文物都携带了原文物母线的部分信息，如图4 1 所示。因此，我们可以应用碎片间母线的相似性来对碎片进行分类。这样，碎片 的分类问题就转换成了二维曲线的相似性比较问题。 图4 1 碎片携带原文物部分母线信息 ，。上叁釜茎坠釜垡釜窑，。一 4 3 曲率 对于二维曲线的相似性问题，现在国内外也有颇多的研究。对于二维益线一 个很重要的性质就是二维曲线各点所对应的曲率和该盐线的形状是相对应的。在 此，我采用的是将曲线进行离散化处理，求得每个采样点对应的曲率，然后对两 条曲线的曲率进行比较借此求得曲线的相似度。 设r = s ) 是曲线c 的参数方程，定义k ( s 产扩( s ) i 为曲线c 在s 点的曲率。 图4 2 曲率 设啦线c ：f r ( s ) 的每点有一个单位向量似s ) 。如图4 2 ，如果它是s 的可微的 鼬：盟i 向量函数，则有i 一( s ) i = 。“：厶，l 。其中e 表示叫s + s ) 与一s ) 的夹角。 我们可用l t 7 ( s ) l = ir “( s ) l 来表示曲线在其两相邻点s ，s + s 的两切向t ( s ) ， t ( s + s ) 之间的夹角与s 之比。当s 一 o 的变化情况，它度量了曲线在其两邻 近点的切向量的夹角对弧长的变化率，也就是说，它表达了曲线的弯曲度。且曲 率与曲线参数和空间直角坐标系的选取都是无关的，因此它属于曲线的几何不变 量。 4 4 曲线的相似度匹配 在预处理过程中，对得到的母线点云数据采用s d m 方法 2 0 1 进行了逼近。因 此得到的母线信息是以b 样条表示的一条曲线。在此，我们对母线进行离散化处 理，采用的方法就是按照高度对该b 样条进行采样。母线的高度即为母线的两个 端点向旋转轴投影所得到的距离值。比如每1 个高度单位内采样厅个数据点，那么 对于一个高度为h 的母线，在其上的采样点数量为 锄。在这里，之所以要对母线 进行按照高度采样，是因为当两条曲线进行相似性比较的时候，他们所需做的第 一个动作就是将旋转轴进行对齐，因此当找到它们相匹配的第一个点的时候，下 面依次要比较的点也必须是相对应的。而按照参数“平均采样所得到的点受该段 曲线的长度、形状的影响，这样两条曲线的采样点并不属于对应点。 具体方法就是先在母线界定的旋转轴上采样 物个点，然后对代表母线的b 样条曲线按照参数“进行一次平均采样，这