（计算机应用技术专业论文）三维颅骨模型的孔洞修补算法研究.pdf

浙江工业大学硕士学位论文 三维颅骨模型的孑l 洞修补算法研究 摘要 三维模型的孔洞修补问题，一直是计算机图形学和可视化研究中的一个热点问题。 由于颅骨模型的特殊性，现有算法并不适用于颅骨模型的修补。三维颅骨孔洞修补是 一个崭新的研究课题，它是根据颅骨模型原有的几何和拓扑信息，借助计算机技术修 复颅骨破洞的虚拟3 d 技术。本文针对现有算法存在的问题，提出了一个颅骨表面模型 的孔洞自动修补算法。实验结果表明本文的方法较其它方法速度快，效果好，能更好 适应复杂和大的颅骨模型孔洞修补。主要工作体现在以下几个方面： ( 1 ) 提出了一个三维颅骨孔洞自动修补算法。对现有的孔洞修补算法进行了较为全 面的综述和分析，针对算法存在的不足和颅骨模型的特殊性，本文提出了一个颅骨孔洞自 动修补算法。算法首先搜索模型边界点进行自动孔洞检测，再在孔洞区域插入离散点并进 行三角剖分来对孔洞进行填充，接着对三角剖分后的网格进行网格细分，然后建立隐式曲 面来调整插入点的位置，最后用拉普拉斯平滑对修补网格进行平滑处理。 ( 2 ) 提出了一种推进式逐层求解法a l s ( a d v a i l c i n gl a y e r - w i s es o l u t i o n ) 。在对大孔洞 的修补中，传统的方法采用孔洞周围的点来控制内部区域，但内部的形状仅依靠有限的控 制点来进行调整很难得到理想的曲面形状，本文提出了一种推进式逐层求解法，弥补了传 统方法得到的修补曲面太过平坦的缺陷，使修补网格与原网格模型平滑拼接，获得了理想 的实验效果。 ( 3 ) 开发了一个三维颅骨孔洞修补原型系统s h r s ( s k u l lh 0 1 er e p a i r i n gs y s t e m ) 。 系统能实现颅骨孔洞修补的所有功能，并应用到三维颅面复原之中。系统对较小的孑l 洞直 接进行三角剖分，对于较大的孔洞则在内部插入离散点，然后再进行三角化；对于一般的 孔洞直接建立隐式曲面，对于大孔洞采用逐层求解法建立它的隐式曲面。 关键词：孔洞修补，隐式曲面，径向基函数，推进式逐层求解，拉普拉斯平滑 浙江工业大学硕士学位论文 ah o l e r e p a i r i n ga l g o r i t h mf o r3 d s k u l lm o d e l a b s t r a c t 1 1 eh o l e sr e p a i r i n go ft h e3 dm o d e li sa c h a h e n g i n gi s s u ei nt h ef i e l do fc o n l p u t e rg r a p h i c s b e c a u s eo ft h ep a r t i c u l a r i t yo ft 1 1 es k u l lm o d e l ，t h ep r e v i o u sa l g o r i t h m sa r en o ts u i t a b l ef o r m es k u l lh o l er e p a i 曲g 3 ds lh o l er e p a i r i n gi st ou s e3 d c o m p u t e rg r a p h i ct e c l l o l o g ) ，t 0 r 印a i rt 1 1 eh 0 1 eo fs k u l la u c c o r d i n gt ot 1 1 eg e o m 或r ya n dt o p o l o g yi n f o m a t i o no ft h es k u l l m o d e l a c c o r d i n gt o t l l el i m i t a t i o n so ft h ep r e v i o u s a l g o r i t h m s ， an o v e la u t o m a t i c h o l e - r 印a i r i n ga l g o r i t h mf o ra r b i 哪h o l e si nm e s hs u r f a c em o d e l so ft h e3 ds k u ui s p r o p o s e d t h ee x p 6 r i m e n t a lr e s u l t ss h o wm a to u rm e t h o di sm o r ee m c i e n ta i l dh a sb e t t e r r e s u l t sc o l p a r e dw i t hp r e v i o u sm e t h o d s ，e s p e c i a l l yf o r t h ec o m p l e xs k u l lh o l e s t h em a i n c o n t r i b u t i o n sa r ea sf o l l o w s ： ( 1 ) an o v e ls k u uh o l er e p a i r i n ga l g o r i t h mi sp r e s e n t e d a r e rr e v i e w i n ga n d 锄a l y z i n g t h ep r e v i o u sh o l er 印a i r i n ga l g o r i t l l r l l s ，、v ep r e s e n t e dar l o v e ls k u l lh o l er e p a i r i n ga l g o r i t l u n a c c o r d 地t ot h el i m i t a t i o n so f t h ea l g o r i t l l l i l se x i s t e da n dt h ep 甜i c u l 撕t yo ft h es k u l lm o d e l f i r s t l y ，t h eh o l e sa r ed e t e c t e db ys e a r c h i n gb o u n d a r yp o i n t so fm o d e la u t o m a t i c a l l y s e c o n d l y ，t h ed i s c r e t ep o i n t sa r ei n t e 印o l a t e di n t ot h eh o l ea 1 1 dt h e nt r i a j l g u l a t e d t h i r d l y ，t h e t r i a i l g u l a rm e s hi ss u b d i v i d e d f o u r n l l y ，a 1 1i m p l i c i ts u r f a c eo fh o l ei sg e n e r a t e dt oa 两u s tt h e p o s i t i o no ft h e s ei n t e 叩o l a t e dp o i n t s f i n a l l y ，t h ep a t c hm e s hi so p t i m i z e db yl a p l a c i a n l s m o o t h i n g ( 2 ) a na d v a n c i n gl a y e r - w i s es o l u t i o n ( a l s ) m e t h o di sp r o p o s e d i nl a r g eh o l e s r e p a i r i n g ，t h et r a d i t i o n a lh o l e sr 印a i r i n ga p p r o a c h e su s e t h ep o i n t so fh o l et oc o n t r o lt h e s h a p eo ft h ei n t e m a la r e a ，b u ti t sh a mt 0g e tt h ei d e a lp a t c hm e s hw h e nt h ei n t e m a ls h a p ei s a d j u s t e do n l yb yal i t t l ec o n t r 0 1p o i n t s i no r d e rt os o l v et h i sp r o b l e m ，a na d v a i l c i n g l a y e r 一、i s es o l u t i o n ( a l s ) m e t h o di sp r o p o s e dt oi m p r 0 v em el i m i t a t i o n so ft h et r a d i t i o n a l m e t h o d sw h i c hm a k et h ep a t c hm e s ht o on a t t h ea l sm e t l l o ds p l i c e st h ep a t c hm e s ha n d s o u r c em e s ho fm o d e ls m o o t h l y ，a n dg e t st h ei d e a le x p e r i m e n t a lr e s u l t 浙江工业大学硕士学位论文 ( 3 ) a3 ds k u l lh o l er e p a i m gs y s t e m ( s h r s ) i sd e s i g i l e da n di m p l e m e m e d ，w h i c h c o u l dr e a l i z em ea 1 1 缸l c t i o no fs k u l lh o l er e p a i r i n ga i l di sa p p l i e dt 03 dc r a i l i o f a c i a l r e c o n 蛐n 】c t i o ns y s t e m f 0 r 也es m a l lh o l e ，t h es y s t e m 仃i a i l g u l a t e st h eh 0 1 ed i r e c t l y ，a n df b r u l eb i gh o l e ，t l l ed i s c r e t ep o i n t sa r ei n t e 印o l a t e da n dt h e nt r i a n g u l a t e d t h es y s t e mc a i la d o p t m ei m p l i c i ts u r f j 黔et oa 由u s tt h ei n t e 印o l a t e dp o i n t s ，a i l df o rt h el a r g eh o l e ，t h ea l sm e t h o d i sa p p l i e dt og e n e r a t et h ei m p l i c i ts u r f a c e k e yw o r d s ： h o l er e p a i r i n g ，i r n p l i c i ts u 血c e ，r a d i a lb a s i s 缸l c t i o n ，a d v a n c i n g1 a y e r 埘s e s o l u t i o n ，1 a p l a c i a ns m o o t l l i n g l l i 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：日期：o 仵l 硐2 口日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 节 力日期：o 髟年 12 月 2 0 日 日期：蝣、1 月沪日 浙江工业大学硕士学位论文 第1 章绪论 1 1 研究背景和意义 从颅骨样本中恢复出入的面部模型，一直是医学图像可视化、计算机图形学和法医人 类学领域中重要的研究领域，它对考古学中古尸的面容复原、医疗脸部外科手术效果的预 测、真实感的人脸动画、以及刑事案件中的受害者入脸识别等应用领域具有重要的作用 n 训。计算机三维颅面复原技术已经成为了当前的研究热点。其中，颅骨模型的完整性是 计算机三维颅面复原技术的基础。 然而，颅骨本身因为岁月的流逝，经过环境和人为的破坏，很容易使其自身丢失一些 部分，导致孔洞的存在。这些孔洞的存在会极大的影响多种数字化计算机辅助工作。例如： 破损的颅骨模型曲面会影响计算机辅助颅骨面貌复原；孔洞会产生多余的曲面边界轮廓 线，影响自动边界匹配；孔洞的存在也无法再现破损文物的原貌。 其次，即使是完整的颅骨样本，在获取它的数字化模型时也会产生孔洞现象。一般， 颅骨模型的获取有以下几种方法嘲：用三维坐标测量仪或3 d 扫描仪直接扫描颅骨，然后在 计算机中重建三维数字化颅骨图像；或利用x 射线、核磁共振以及c t 等医疗检测设备， 由二维断层图像重建三维颅骨图像。但由于设备本身和人为操作等因素，通过这些方法获 取的模型经常会丢失一些模型面片信息，导致孔洞的存在。据r o s c o e 在文献隋1 中介绍， 有约1 7 的s t l 文件存在孔洞等缺陷。所以从颅骨样本获得的颅骨模型一般是不完整的， 必需在进行修复预处理后才能应用，这就迫切需要一种修补算法对颅骨模型进行孔洞修补 处理。 再次，颅骨修补也是医学界的一个重要应用3 。一方面随着经济发展，个人拥有并驾 驶汽车数量飞速增长，导致交通事故引起的颅骨损伤患者日益增多；另一方面脑肿瘤的发 病率也呈上升趋势，脑部手术伴随而来的就是颅骨修复，一般颅骨外伤及其手术造成的颅 骨缺损者占8 0 以上。在手术过程中，传统的纯手工方法对临床医生的技术要求较高，劳 动强度较大；另外由于医生是在临床现场制作，会受到心理和制作水平的影响，因此不易 制作出十分吻合的修复体。如果可以有一种修复方法可以在手术前制作出无论外型和联接 均符合的修复体，手术时只要把预先制作好的修复体安装上即可，可以大大缩短手术时间， 浙江工业大学硕士学位论文 减少手术风险，减轻病人的痛苦。 综上所述，如何对颅骨模型进行修复成了一个亟待解决的重要问题。本文在大量研究 分析现有的孔洞修补技术的基础上，提出了一种针对颅骨表面模型的孔洞自动修补算法。 它可被应用到诸如考古学、文物保护、颅骨修复等领域，既是应用领域的切实需要，又是 医学图像可视化、计算机图形学、考古学方面的基础性研究工作，具有重要的学术意义。 1 2 国内外研究现状 国内外学者对模型的孑l 洞修补技术已进行了不少研究，大致可以将这些方法分为两 类：基于体素的和基于曲面的。 基于体素的修补算法首先将输入模型转化为一种体表示( v o l u m e t r i c r e p r e s e n t a t i o n ) ，它由称为体素的离散体组成的，然后使用各种方法在体空间修补孔洞。 j u 订3 等使用一个八叉树网格来建立一个体数据场，并通过等高线( c o n t o u r i n g ) 来重构曲 面。j o s h u a 等陋1 使用最小切割算法将空间分为内部和外部，同时在全局感测方式下修补孔 洞。这类算法是典型的全自动算法，并能产生水密模型，适用于复杂孔洞的修补。但体之 间的转换会导致模型的重采样。它经常会引入走样混叠的孔洞( a l i a s i n ga r t i f a c t s ) 和 模型特征的丢失，破坏输入模型的结构。基于体素的修补算法输出的三角形数量通常远多 于输入模型，因此需要在后期处理中简化模型，而且输出的三角形的质量也会退化，必须 在后期进行改进。体表示法是内存密集的( m e m o r yi n t e n s i v e ) ，很难在高分辨率下运行。 基于曲面的修补算法直接处理输入数据，并显式地检测和修补曲面上的孔洞。s o r k i n e 等口3 使用最小二乘方网格( l s m ) 算法，通过计算网格的拉普拉斯矩阵，然后解一个稀疏 线性系统( s p a r s el i n e a rs y s t e m ) 来重构网格的几何结构( 见图卜1 ) ，但这种方法的 前提是假设能预先获取孔洞的拓扑信息。浙大的z h a o 等n 们用a f m ( a d v a n c i n gf r o n tm e s h ) 技术填补孔洞，然后计算每一个新增三角片的法向信息，再根据法向信息和孑l 洞边界点解 一个泊松方程( p o i s s o ne q u a t i o n ) ，从而调整新插入点的位置( 见图卜2 ) 。但当点较多 时，解泊松方程会比较费时。基于曲面的修补算法的优点是最低限度的扰动输入模型，并 能保存模型非孔洞区域的结构。此外，算法只引入了有限数量的额外三角形。但为了保证 有效( 正确) 的输出，算法通常要求输入模型满足确定的质量要求( 错误容限) 。平坦区 域的规则孔洞可以简单的通过平面域三角剖分来修补，但非规则区域的复杂孔洞的修补会 很难。由于孔洞检测要遍历整个模型，比较费时费空间。 一2 一 浙江工业大学硕十学位论文 矿肝广夕 ( a ) 原始的骆驼模型( b ) 在驼峰周罔标记丁控制点( c ) 重构后的模型 幽l - ll s m 方法的修补实例【9 】 黾5 a ) 原始模型( b ) 中间模型( c ) 中间模型( d ) 修补完成后的模删 图1 2a f m 方法的修补实例 通过对国内外孔洞修复技术研究情况的分析，可阻发现其特点是：以前的研究者较少， 现在已经成为一个研究的热点问题；以酊的研究是对二维网格剖析情况较多，三维暗况较 少；国外研究的较多，国内研究的较少。在国内，关于二维的区域填充研究的较多，三维 空旬的孔洞修补研究的较少i 关十已有散乱点三角剖分研究的较多在孔洞区域插入多个 离散点并建立三角剖分网格研究的较少。基于曲面的修补方法适用于对平坦区域孔洞的修 补，对于复杂孔洞的修补效果不太理想。基于体素的方法适用于复杂孔洞的修补，但这类 方法都很费时，而目有时会产生错误的拓扑信息。因此，寻求一种适台于复杂颅骨孔洞修 补的算法是颅面复原要解决的基本问题。 1 3 本文工作与内容安排 二维颅骨孔洞修补是个崭新的研究课题，直是计算机图形学中的突出难题。本课 题来源于三维颅面复原i ! i i 目，由于颅骨孔洞的复杂性和多样性，现有的算法并不适用于对 颅骨模型的修补，速度和精度成了许多算法的瓶颈，特别是对复杂的高曲率孔洞，修补效 果都不太理想，另外这些算法对于修补的孔洞未能进行光惜处理。本文提山一种面向颅骨 浙江工业大学硕士学位论文 的孔洞修补算法，通过建立孔洞隐式曲面和网格平滑处理解决了对非规则区域复杂孔洞的 修补，较好的满足了上述性质要求。具体包括以下几方面的内容： ( 1 ) 对现有的孔洞修补算法进行了较为全面的研究和分析，针对现有算法存在的不足 和颅骨模型的特殊性，本文很好的结合并改进了现有的技术，将它们应用到颅骨 的修补中，提出了一套较为完整的颅骨孔洞修补算法。算法首先搜索模型边界点 进行自动孔洞检测，再在孔洞区域插入离散点并进行三角剖分来对孔洞进行填充， 接着对三角剖分后的网格进行网格细分，然后建立隐式曲面来调整插入点的位置， 最后用拉普拉斯平滑对修补网格进行平滑处理。 ( 2 ) 在对大孔洞的修补中，传统的方法采用孔洞周围的点来控制内部区域，但内部的 形状控制仅依靠有限的控制点来进行调整很难得到理想的曲面形状。针对这个问 题，本文提出了推进式逐层求解法( a l s ) ，弥补了传统方法得到的修补曲面太平 坦的缺陷，能使修补网格与原网格模型平滑拼接，获得了理想的实验效果。 ( 3 ) 开发了一个三维颅骨孔洞修补原型系统s h r s ( s k u h o i er e p a i r i n gs y s t e m ) ，能 实现颅骨孔洞修补的所有功能，并将它应用到三维颅面复原中。系统可以对较小 的孔洞直接进行三角剖分，也可以对较大的孔洞在内部插入离散点，然后再进行 三角化：可以对一般的孔洞直接建立隐式曲面，也可以对大孔洞采用逐层求解法 建立它的隐式曲面。在考古学、文物保护、颅骨修复等方面具有一定的应用价值。 本文的内容安排如下： 第一章综述孔洞修补的背景，国内外研究现状以及本文所作的主要工作和论文的内 容安排。 第二章研究分析了对于孔洞修补的相关研究工作，指出了现有方法存在的问题。 第三章此章为本文重点，具体分析介绍了三维颅骨孔洞修补算法，对算法的各个步 骤进行了详细地阐述，包括孔洞检测、孔洞区域离散点插入和三角剖分、网格细分、孔洞 隐式曲面的建立和网格拉普拉斯平滑，同时提出了一种推进式逐层求解法( a l s ) ，并对 算法结果进行了分析和比较。 第四章介绍了三维颅骨孔洞修补原型系统s h r s ( s k u l lh o l er e p a i 曲gs y s t e m ) 的系 统功能，系统设计和用户界面。 浙江工业大学硕士学位论文 第五章对本文工作的总结以及对后续工作的一些展望。 浙江工业大学硕士学位论文 第2 章相关研究工作分析 对于模型的孔洞修补，已有人做了一定的工作。在对这些算法进行分类总结后，可以 发现现有的修补算法主要采用以下几种修补策略：直接三角剖分，新增采样点，采样点调 整和点云数据三角化。在本章我们先对这几种修补策略进行分析，然后给出有关颅骨孔洞 的修补算法，最后总结分析现有算法存在的问题。 2 1直接三角剖分的修补算法 早期的孔洞修补算法主要考虑如何对孔洞区域进行三角化。l e o n g 等u 1 化3 采用孔洞多 边形的顶点构造新的三角片，这种算法是直接对孔洞边界进行三角剖分，仅仅采用原有的 孔洞多边形顶点，没有增加新的三角片顶点，因而难以获得较好的用于填补孔洞的三角片 形状。而且算法略去了三角片的拓扑关系，采用遍历算法来处理，耗费大量的时间，效率 比较低。 三角剖分本质上是一个非线性优化问题。为了获得该问题的最优解，可以使用动态规 划算法、遗传算法、模拟退火算法等对孑l 洞区域进行剖分，以获得最优的二角化结果。但 这一过程的算法复杂性通常很高，如b a r e q u e t 等n 3 1 所采用的动态规划算法的时间复杂度 为0 ( n 3 ) 。张洁等“们采用了不同的思路来处理这一问题，提出一种用于三角网格模型的各 向异性孔洞修补算法( 见图2 一1 ) ：算法避免了高代价的孔洞多边形最优三角化求解过程， 对孔洞区域只进行一般的三角剖分，不需要满足任何最优化的约束条件。仅仅使用一个算 法复杂度近似于o ( 1 0 9 n ) 的递归函数就可以实现该过程；在此基础上，通过很少次数的迭 代过程对孔洞三角化后的网格进行细化和几何形态的调整使其和周边网格自然过渡。 浙江t 业大学硕士学位论文 a ) 带孔洞的模型 削2 2 分段修补算法实例 b ) 修补后的模型 张丽艳等人“”提出了一种三角片自然增长的修补算法，以孔洞边界为基准，向内生长 与原始而片尺寸相似的新而片( 见图23 ) 。该算法除了应用原有孔洞多边形上的顶点之 外，还根据需要补充新的顶点，从而歌得优化的新增三角片形状。算法通过建立空间孔7 h 多 边形的特征面，把对空间孔洞多边形的三角划分问题投影到平面上进行处理- 然后根据投 浙江工业大学硕士学位论文 影后的孔洞多边形边界的央角关系，每次寻找孔洞多边形中夹角最小的一对邻边，在孔洞 多边形特征面上构造新三角片，然后更新孔洞多边形，直到新增三角片完全覆盖了原有的 孔洞。此算法在孔洞多边形特征面上对新三角片进行方向合法性和位置合法性的检查，避 免了狭长和错误三角片的出现，因此可以获得三角片形状较为优化的修补结果。但是这种 修补方法的前提是假设空问孔i 同多边形接近平面多边形，如呆用f 修补盐面上曲率发生较 大变化处的孔洞时，则修补的部分与其周围的原网格曲面不能光滑连接，难以获得理想的 修补效果：而且此方法也没有给出非封闭结构孔洞检铡的算法。 钔孔洞修补前棋犁( b ) 孔洞修补后模型 c ) 修补前局部放大酗( d ) 修补衍局部放大圉 蚓2 3 二三角h 自然增长算法的修补实例i o 也可以重构曲线曲而，在曲线曲而上按等参数间距获得采样点。张丽艳等“”通过截平 面族与孔洞周田网格模型求交，对交点序列进行b 样条曲面插值，并对插值曲线进行重新 采样获得孔洞内部的新增采样点，最后通过对孔洞内部的新增采样点和孔洞边界组成的点 集进行一角化，从而较好地解决填充区域和模型的其他部分光滑过渡的问题。邱泽阳等 根据孔洞周围的局部离散点来建立一张曲面片，然后采用面上取点的策略补出孔洞部位所 缺的点。即先在孔洞附近交互拾取不妊线的3 个点构成一个三角形，然后将局部测量点向 泼三角形所在平面投影，如投影点落在该三角形内，则将其链接到葭三角形中，表示这些 点处于要逼近的曲面上。构造初始三角曲面片，并进行这代求精，然后在三角曲面片j i 进 行等参数间隔取点。 攀 浙江工业大学硕士学位论文 2 3 新增采样点调整的修补算法 陈老明等。“根据曲率来调整新增点的位置( 见图24 ) 。算法每次寻找孔洞多边形中 夹角最小的一对邻边构造新的初始三角片，再根据新增点和其邻点的法矢啕整新增点的 位置，然后更新孔洞多边形，直至覆盖整个孔洞。最后再根据需要对所有新增顶点作定 的调整。 a ) 修补前 1 ， ( b ) 修补后 圈2 4 基于曲率的修补算法实例 w a n g 等1 采用重建曲线曲来澜整新增点的位置，给出了基于移动最小二乘法的补点 方法。算法用三次b 样条曲线修复点云模型边界及特征线，将非封闭无特征空洞转化为封 闭无特征空洞，非封 j j 特征空洞转化为若干个封闭无特征空洞。然后使用移动最小二乘法 建立空洞区域的隐式曲而方程，在对投影空洞进行重新采样后，把新生成的点映射到曲面 上，使得最终修补的空洞曲面同其周围曲面保持良好的几何一致性。 d a v l s 等”= 。采用基于体素扩散方法束调整新增点的位置。即体数捌场融台的方法进行 孔洞修补，将测量点处的凸面用体表示法( v 0 1 u m 乱r l cr e p r e s e n t a t l o nj 来描述( 见图 25 ) 。该算法通过选代计算扩展体数据场的描述范围，撮终建立一个能够拙述整个孔洞及 其周围曲面的场函数再用m c ( m a r c h ln gc u b e ) 算法网格化显示整个模型。该算法用扩散 法在等值面上插入新的数据，实现三角剐格模型的复杂孔洞数据的修复r 并能取得较好的 修补效果，但由于要用m c 算法整体重新输出修补后的孔洞曲而，因此会改变原有的叫格 模型。 浙江r 业大学硕f 岸位论文 醚醚 殴，艮 a ) 孔洞模型( b ) 修补后的模 幽2 6 基_ 丁径向基函数的修朴实例 王宏涛1 采用神经网络的方法柬调整新增点地位置。浚方法首先榆测出孔洞，通过 对扎裥特征多边形实施三角化获得新增三角片顶点；在孔洞边界周围采集三角片顶点，将 其作为样术点集来训练r b f 网络；将训练好的r b f 刚络片j 于新增三角片顶坐标的优化，最 终实现孔洞的修补( 见图2 7 ) 。 浙江工业大学硕士学位论文 a ) 具有7 l 洞的原( b ) 其有孔洞的原( c ) 修补后的( d ) 修补后的 始点集模型始模型光照图模型放大图 图2 7 采用神经网结的孔洞修补实例 e ) 修补斤的 光照图 l1 e p a 1 先对孔洞多边形的边界直接用三角片进行连接填充，然后采用细分和边交换 方式消除形状不好的新增二角；最后采用网格光顺的方法，对新增三角片的顶点位置进 行调整( 见图2 8 ) 。因为在顶点位置调整时用到了孔洞周围三角片的位置信息，所以能够 得到比较光滑的修补效果，但是该算法在填充孔涮时需要不断计算填充三角片之间边长和 内角关系，来生成更多的三角片，并进行边界调整，固而运算较为费时。 a ，b ) 带 l 洞的斯坦福兔子模型 ( c ) 三角化厉( d ) 最终修补的结果 图2 8l 】印a 方法修补实例 2 4 对于残缺点云数据的修补算法 一般残缺点云数据的修补方法是将点云数据三角化为网格模型，利用网格模型的拓扑 关系完成数据的补测。但是这些三角化算法一般d ：测量数据比较均匀的情况下可以取得较 好的效果，如果测量数据分布不够均匀甚至存在孔洞，则无法得到令人满意的结果，数据修 补也将归丁失败。为了解决这个问题，陈飞舟等”提出了一种残缺点云数据修复算法，直 接对残缺点云本身进行数据补充( 见图29 ) 。该算法借助k d t r e e 寻找点云的缺陷边界， 确定点云的缺陷区域：然后利用二次曲而的特性参数化边界点列；最后，通过径向基函数 浙江r 业= 学硕士学位论文 表示的插值曲面计算位于残缺区域内部的数据点，实现残缺点云数据的修复。此算法能够 次性地自动提取残缺点云数掘的所有孔洞边界，对于封闭形态的点云数据无需任何用户 干预；对于开放( 非封闭) 形态的点云数据，也只需用户非常少的额外操作。并且计算出来 的补测数据和周围原有数据过渡自然融合效果较好。但此算法对噪声比较敏感，尤其是 当输入数据携带大量高频噪声和离群点噪声时，就不能准确地修补三维模型。 a ) 残缺的点云模型( b ) 三角化结果( c ) 朴测后的点云模型( d ) 三角化结果 削2 9 残缺点百数据修补实例 为了解决带噪声的点云数掘的高质量重建问题，杨军等“提出了种隐式重建算法。 该算法首先定义了光滑的概率密度函数，描述某个采样点应是模型表而上点的概率，基于 均值漂移算法的滤波算子将各个采样点沿桉密度函数的梯度方向移动：其次，将两个经典 的方法一一径向基函数法和单位分解法，结合起来，完成离散点数据的隐式重建，即去除 了噪声和离群点的输入数据先片j 由误差控制的自适应八义树划分为小的区域，然后在八叉 树的每个叶子单元用径向基函数的插值算法来求解局部曲面函数：最后，通过单位分解法 ( d a r t 儿1 0 no fu n n y ，p 0 u ) 对局部形状函数加权求和得到整个模型的全局隐吉数( 见目 2 一 o ) 。 a ) 带噪卢的s t a n m r db u n n v ( 3 6 2 + l0 3 个采样点)( b ) 算法的重建效果 圈21 0 带噪声的点五数据的隐式重建实例 浙江工业大学硕l 学位论文 2 5 针对三维颅骨模型的修补算法 现有的修补算法大部分都是一种通用的修补算法，很少有专门针对颅骨孔洞提出特定 的修补算法。最近，姚远等。”提出了一种面向颅骨损伤修补的缺损重建算法，算法通过双 环采样，投影构建代理曲面，然后通过合并环问区域及引入边缘约束的平滑，得到缺失实 体孔洞的上下缝合面。在此基础上，搜索出上下边界环之问的三角网格区域，利用几何约 束条件重建缺失实体。谈算法很大程度上依赖于缺损部位临域的几何特征，对于颅骨顶部 及后部中间部位的修复具有良好的效果，但对于曲率变化剧烈的部位，诸如处理靠近耳、 面部的缺损，不能获取满意的补缺效果。 l， ( 上缝台而( c ) f 缝台面 。蕊e d ) 环间区域( e ) 修复体( 0 修复对比幽 国2 1 1 姚近甜的修补算法实例 张景蒋。提出了一种基于逆向工程的缺损颅骨曲面模型重建方法。该方法通过ct 设 备获墩缺损颅骨的数据，同时提取出轮廓边缘的曲线数据，得到一系列包含断裂曲线在内 的曲线条。在进行修补片体的数字设计过程叶】，先使断裂曲线条完整化，即完成曲线桥接， 然后由这些完整曲线条构建出修补体曲面。但该方法是一种交互式操作，需要用户设置控 制参数。且在设计曲线桥接算法的过程中，主要是依据颅骨曲面的凸性而构出了“一般 b e z 。r 曲线”，而没有将其它类型的曲线构出。 飞搿 浙江i 业大学顼+ 学位论文 匿 a ) 缺损颅骨( b ) 缺损的线条 变囵 c ) 桥接后彤成完整线条( d ) 修补片体加载于缺损域 图2 1 2 张景涛的修补算法实倒1 2 ” 通过对相关研究工作的分析，可以发现一些研究在构造三角片时仅仅采用原有的j l 洞 多边形顶点，而没有增加新的三角片顶点，导致修补后的三角面片并不优良。9 ”。：没有很 好的解决空间孔洞与相邻曲面片的光滑连接问题，造成修补的网格与周围的三角片不能光 滑的过渡，修补效果不够理想，这只能算是某种意义卜的“填洞”，而不是“补洞”：对于 孔涮边缘部分破损的，提取不到完整的边界曲线情况没有进行很好的处理；大部分算法是 一种通用模型的修补算法，没有对颅骨孔洞这类复杂高曲率孔洞的修补给出特定的修补算 法，使得对这类孔洞的修补效果不太理想：现有的颅骨孔洞的修补算法对于曲率变化剧烈 的部位不能获取满意的补缺效果，有些算法还需要较多的人工交互。 个理想的孔洞填补算法应陵满足如下性质“。圳：( 1 ) 自动性。用户如果选择了孔洞， 交互应该尽可能简单。( 2 ) 效率性( e f f l c l e n c y ) 。台理的运行叫问，良好的交互速度。( 3 ) 准确性( a c c u r a c v ) 。用修补网格来填补孔洞，应该尽可能的和周围网格相融合，网格密 度和形状应苣和原孔洞边界相匹配。( 4 ) 鲁棒性( r o b u s t n e s s ) 。能够处理任意网格的任意 孔洞。比如，任意网格可能包含非流形边缘，任意孔洞可能非常不规则的，并且轮廓不是 平面的。 虽然对于网格模型的修补算法国内外学者已经做了一定的研究“”1 ，但现有的算 法没有能完全满足上述性质的，尤其是很难达到健壮性，因为现有的方法很难处理复杂的 高曲率7 l 嗣。针埘这些问题，本文通过对颅骨孔洞修补算法进行深 研究，提出了剀实可 行的解决方法，给出了一套完整的颅骨孔洞修补算法，并将理论研究与实际应用相结台， 丌发出一个维颅目孔洞修复原型系统( s h r s ，s k u l l h o l e r e p a i r i “gs y s t e m ) 。 浙江工业大学硕士学位论文 2 6 本章小结 本章详细分析了现有的孔洞修补策略，包括不添加新采样点的直接孔洞修补，添加采 样点的孔洞修补和对于残缺点云数据进行三角化的修补，并研究了现有的关于颅骨模型的 孔洞修补算法，指出了这些算法存在的问题，并针对这些问题提出了一套完整的颅骨孔洞 修补算法。 浙江工业大学硕士学位论文 第3 章三维颅骨孔洞修补算法 三维颅骨孔洞修补问题，一直是基于三维数字颅骨人脸复原研究中的难题。通过对现 有方法的总结分析，尽管有人已经做了一定的工作，然而，迄今为止，能够快速、准确地 修复颅骨模型仍然是一个难题，目前在这一领域的研究还没有取得满意的结果。本文针对 现有算法存在的问题，提出了一套完整的颅骨表面模型的孔洞自动修补算法，它是根据模 型原有的凡何和拓扑信息，借助计算机技术修复颅骨孔洞的虚拟3 d 技术，是一个比较新 的课题。在本章我们先给出在算法中涉及到的关于三角网格的一些基本概念，接着对算法 进行整体的概述，然后再对算法的各个步骤进行详细的分析。 3 1预备知识 一个三角网格定义为一组顶点和连接这些顶点的有向三角形，图3 一l 给出了三角网格 模型所涉及的一些基本概念。与某点相连的顶点称为该点的邻接点，与某点相连的边称为 该点的邻接边。如果某点是某一个三角形的一个顶点，则称这个三角形是该点的邻接三角 形。如果两个三角形共享某一边，那么它们也是邻接三角形。边界边是只有一个邻接三角 形的边，内部边是除了边界边以外的边。边界点是边界边上的点。如果两个点的连线为某 一边界边，则称这两个点为边界边邻接点。由边界边相连组成的空间多边形称为孔洞边界。 这里引入几个基本概念删： 邻接点：如果网格数据中的两个点的连接线断为某一三角网格的边，则称这两个点为 邻接点。点p 的邻接点v p = qi 存在t ，使p 属于t 且q 属于t ，q 是曲面 上异于p 的点，t 是曲面上的一个三角网格 。 邻接三角网格：对于网格数据中的点，如果它是某一个三角网格的一个顶点，则称这 个三角网格是这个点的邻接三角网格。点p 的邻接三角网格t p = t p 属于t ，t 是曲面上的三角网格) 。 边界边：如果存在某条边仅属于一个三角片，则该条边是构成孔洞多边形的一条边，我 们称之为边界边。 内部边：如果某条边属于两个三角片，则该条边为内部边。由边界边首尾相连组成的 封闭空间多边形称为孔洞边界。 浙江丁业 学硕士学位论文 边界边邻接点：如果刚格数据中的两个点的连接线断为某一三角网格的边界边，则称 这两个点为边界边邻接点。 孔洞边界：由边界边相连组成的空间多边形称为孔洞边界。 囵 o 。 e 接点 邻接边 oo 邻接三角形 图3 】三角网格模型相关概念 3 2 算法概述 算法输入为颅骨三角刚格模型，整个算法流程用图3 2 表示，丰要包括5 个步骤： ( 1 ) 孔洞检测。对输入的颅骨三角阚格模型进行孔洞分析，并对检测出的孔j l 司进行标 f 2 1 孔洞区域离散点的生成和三角剖分。用户选择需要修补的孔洞，在其中插入离散 点，然后对插入的离散点进行三角剖分。 f 3 1 网格细分。对三角剖分厉的网格进行网格细分。 f 4 1 孔洞隐式曲面的建立。利用径向基丽数( r b f ) 建立孔洞区域的隐式曲面，调整 插入点的位置。 f 5 1 网格平滑( 拉普拉斯平滑) 。用伞状算子( 拉普拉斯算子) 对隐式曲而进行平滑处 理。 降碍丁忑刊孺雾h 磊一h 藤刊一r m 蛭： l 一，、】 m 业l1 竺兰il j 一 曰一回一回一回一回一国 凹32 算法基本流群闰 浙江工业大学硕士学位论文 3 3 孔洞检测 要对模型进行修补，首先要准确的检测出孔洞。孔洞边界是由模型边界点相连组成的 空间多边形，所以孔洞检测是通过自动搜索模型边界点来完成的。我们采用两步来完成孔 洞的检测：模型边界点的提取和边界点的分类与排序。 ( 1 ) 模型边界点的提取 由前面的定义可知构成模型的边有两类：内部边和边界边。l 司理，可将构成模型的 点分为两类：内点和边界点。构成内部边的点为内点，而构成边界边的点为边界点。判断 边界点的过程就是判断该点是否是边界边上的点的过程。模型边界点的判断算法如下”： ( ”建立一个临时点数组t 鲫p ，井置为空。 ( 2 ) 对当前点的所有邻接三角网格上异于当前点的点作如下操作：如果t e m p 包含 此点，则从t e m p 中删除此点，否则，把此点加入到t e m p 中。 ( 3 ) 检查t e m p ，如果t e m p 为空，则当前点为内点；否则为边界点，并且t e m p 中的 点是当前点的边界边邻接点。 圈3 3 是一个网格模型的边界提取结果，其中( a ) 为模型的边界边，( b ) 为边界边 上的边界点。 凰 a ) 网格边界边( b ) 网格个边界边上的边界点 圈3 3 阿格边界点提取 ( 2 ) 模型边界点的分类和排序 模型边界点提取后得到的边界点集是无序的，且模型可能存在多个孔洞，所以还需要 对这些边界点进行分类和排序，找到每一个孔洞的边界点集。边界点的分类与排序算法如 r ： ( 1 ) 建直一个临时孔洞点集h ，并置为空。 浙江r 业人学矾一学位论文 ( 2 ) 从模型边界点集rc f ，取_ j 1 个电p l 加入 ，并将其从br 一删除。 ( 3 ) 赴b 。 ，杏找p l 的边界边邻接电- 、a “。若存在，则将其】t 八h - 并从b 山删绿， 令p 等jp 删j ，返hl3 ) 。酉则进入 4 ) 。 ( a ) 若b 为空，则亮成了边界点的分类删排序，结束：打则，返f ( 1 ) 根据以上算浊描述得剑了 个嗍格模p 的扎汇硷测结果，如巨34 ，其。 t 各孔洞用不 h 的渤i 色进行标记木尊浊也适用于非封羽孔洞的榆测。另外，我们世t ：鞍丁张献颖等 的一角捌格边弘提取的研究方法，曲者效事相盹， a ) 原摸掣b 、移 ：_ d t f ( cj 孔汇阿格局部放人剀 辱| 34 孔一d 梭删 34 孔洞区域离散点插入和三角剖分 a 强墩 。洞迎乒后利j ! l _ 了一纠离敞0 并点集，可通过f 尊敬- 的插入和角剖分 j 洞 进行坝觅如罔弘i 所示 qq 篷 削35 孔洞区域离散 插人a 一角剖分示意剀 ( 】) 孔洞区域离散点插入 山r 提，曲算法效率，并款得较好的效粜，找f f ：对不同的扎州采用小同的填充策诸 较“、的j 。制， 接趔行一角剖分：刑鞍大的孔洞我们先_ 玎! _ t i l 洞多边悻刚插入局敦专 j u 圈 、掣巧鳐嚣一 圈瓣、隧 一研 一 k 一o卜h 浙江工业大学硕士学位论文 后再进行三角化。为了确定插入点的位置，需要综合考虑该点两边界邻接边的内夹角e 和 平均长度，如图3 6 。 ( a ) 凸点 二二二 声 船、 图3 6 边界点p ，两邻接边的内夹角 设孔洞多边形的每两个相邻边都对应一个内角秒，且当前点为p ，其前一点为肋，后 一点为刃，e ：= b p ：，e 。= p ，p 。，”= 试：e 。，为基准法向量，作为法向量的基准方向。 则对于逆时针多边形，内角臼分为3 6 ( a ) 、( b ) 所示的两种情况，分别按如下方法计算： ( 1 ) 假如刀与同向，则p ，为凸点，臼 1 8 0 。 (