（计算机科学与技术专业论文）点模型数字几何处理若干技术研究.pdf

浙江大学博士学位论文摘要 摘要 传统的多边形网格模型除存储模型的几何信息之外，还需维护庞大的拓扑连 接信息。而以离散点为表面表达方式的点模型，因具有数据获取方便、数据结构 简单且无需维护其全局一致的拓扑结构等优点，故以点模型为研究对象的数字几 何处理已成为计算机图形学中一个新兴的研究热点。三维点模型在医学辅助诊 断、数字娱乐、工业设计、航天模拟、文物保护和修复等行业中具有广泛的应用 前景。 本文以计算机图形学，计算机辅助几何设计，离散微分几何学和数字信号处 理为坚实的理论基础，对点模型数字几何处理的若干核心技术进行了深入研究， 提出了一些新的算法，初步形成了一个点模型数字几何处理框架。主要内容包括： 提出了基于采样保真性和基于相似性的两种点模型去噪算法。在基于采 样保真性的去噪算法中，通过m l s 计算出采样点的保真性，基于法向张 量投票测量采样点的特征性，并将两者相结合实现保持曲面几何特征的 点模型去噪。在基于相似性的去噪算法中，通过本文设计的三边滤波算 子计算采样点的几何强度，利用构建的均匀几何强度网格估算采样点间 几何强度的相似性；通过m e a ns h i f t 聚类法对点模型进行几何特征相似性 聚类；依据相似性实现点模型保持曲面特征的去噪。 提出了一种生成细节的点模型几何修复算法。我们通过r b f 曲面重建得 到残缺区域的光滑修复曲面；利用三边滤波算子获取已知采样点的几何 细节纹理；在孔洞光滑曲面上建立一个带约束的全局纹理合成能量方程， 并通过求解出一个全局的能量最小值获得孔洞光滑曲面的几何细节。 给出了两种曲率自适应的点模型简化方法。在基于几何图像的简化方法 中，通过将点模型的球面极坐标映射到平面上，构造其几何图像；为了 便于控制采样密度，将简化密度定义为简化时所允许的最大像素搜索半 径；将曲率阙值和简化密度相结合实现点模型的曲率自适应简化。在基 浙茳大学博士学位论文摘要 于相似性的简化方法中，通过法向张量投票方法将点模型分为强特征边 性和非黻特征边性两部分，利用m e a ns h i r 聚擞法对非强特征边性部分进 行表露隳域凡 毒特征相似性聚类，然后分别进行麓讫。 基予球甏参数佳，疆密7 一释鲁捧豹点模鼙渐变算法。透过球嚣参数辱 二 将源和秘标模型嵌入到单位球面上，在球面上自适应地对齐模型闻的相 应特械点之后，将球面映射到同一矩形参数域上，以建立模型间备采样 点的对成关系。在渐变过程巾，采用拉普拉斯辣子求解中间点模擞以傈 蔫模蘩瓣蹋繁，囊矮醐已s 避嚣动态叁逶应戆鬟采样激游除孛润模黧瓣袈 缝。 介绍了我们研发的点模型数字几何处理原型系统。该系统提供了个包 括数据获取、表示、处理以及绘制等技术在内的数字几何处理框架，并 着重奔缨秽实瑷了点模型戆绘制、点元预处理、点模型豹去噪、凡秘修 复、麓纯帮重采样、参数纯、渐变、点模型静纹璞陕身垂帮绞理合成等动 能模块。 点模型数字几何处理有着广桶黝研究前景，基于我 f 】研发豹原型系统，本文 豢嚣绘窭7 未来豹黟 究方彝。 关键词：微分属性，主元分析，移动最小二乘曲面，去嗓，法向张量投票，三边 滤波算子，m e a ns h i r 聚类，点模激参数化，几何修复，纹理合成，简化，渐变 浙江大学博士学位论文 a b s t r a c t a b s t r a c t t h et r a d i t i o n a lg e o m e t r yr e p r e s e n t a t i o n , s u c ha sp o l y g o n a lm e s h e s ，n e e d st os t o r e a n dm a i n t a i nt h ec o n n e c t i v i t yi n f o r m a t i o nb e t w e e nv e r t i c e sa sw e l la st h eg e o m e t r y i n f o r m a t i o n n e ya l eb o t l lm e m o r yc o n s u m i n ga n dc o m p u t a t i o n a l l ye x p e n s i v e d u et o c o n v e n i e n t3 dp o i n td a t aa c q u i r e m e n t , s i m p l ed a t as t r u c t u r ea n dn on e e dt om a i n t a i n t h eg l o h a l l yc o n s i s t e n tt o p o l o g y , h o w e v e r , p o i n t - s a m p l e dg e o m e t r yi s r e c e i v i n ga g r o w i n ga m o u n to fa t t e n t i o na san e wt y p eo fm e d i u ma n ds u r f a c ep r e s e n t a t i o ni n c o m p u t e rg r a p h i c s a c c o r d i n g l y , c o n s i d e r a b l er e s e a r c hh a sb e e nd e v o t e dt ot h ef i e l d o fd i g i t a lg e o m e t r yp r o c e s s i n go fp o i n t s a m p l e dm o d e l s p o i n t - s a m p l e dg e o m e t r yh a s t h u sb e e na p p l i e dt om a n yf i e l d s ，s u c ha sc o m p u t e r - a i d e dm e d i c a ld i a g n o s i s ，d i g i t a l e n t e r t a i n m e n t ，i n d u s t r i a ld e s i g n ，a v i a t i o ns i m u l a t i o n , p r o t e c t i o na n dr e s t o r a t i o no f c u l t u r a lr e l i c s ，e t o b a s e do nt h es o u n dt h e o r e t i c a lf o u n d a t i o no nc o m p u t e rg r a p h i c s ，c o m p u t e r - a i d e d g e o m e t r i cd e s i g n , d i s c r e t ed i f f e r e n t i a lg e o m e t r y , d i g i t a ls i g n a lp r o c e s s i n g t h i s d i s s e r t a t i o ni n v e s t i g a t e ss o m ek e yr e s e a r c ha r e af o rt h ed i g i t a lg e o m e t r yp r o c e s s i n go f p o i n t s a m p l e dm o d e l s ，a n dp r o p o s e san u m b e ro fn o v e la l g o r i t h m so nt h e m a tt h e s a m et i m e , w eh a v ep r e s e n t e dan e a r l yc o m p l e t eg e o m e t r yp r o c e s s i n gf r a m e w o r kf o r p o i n t - s a m p l eg e o m e t r y o u rm a i nc o n t r i b u t i o n sf o c u so nt h ef o l l o w i n gf i v ea s p e c t s ： b a s e do ns a m p l i n gl i k e l i h o o d ar o b u s td e n o i s i n ga l g o r i t h mf o rp o i n t - s a m p l e d 圈硼 a c e si sp r o p o s e d i nt e r m so fm o v i n gl e a s ts q u a r e ss u r f a c g , t h es a m p l i n g l i k e l i h o o df o re a c hp o i n to np o i n t s a m p l e ds u r f a c e si sc o m p u t e d b a s e do nt h e n o r m a lt e n s o rv o t i n g , t h ef e a t u r ei n t e n s i t yo fs a m p l ep o i n ti se v a l u a t e d i n c o m b i n a t i o nw i t l ls a m p l i n gl i k e l i h o o da n df e a t u r ei n t e n s i t y , t h ep o i n t s a m p l e d g e o m e t r yc a nb ee f f i c i e n t l ys m o o t h e dw h i l ep r e s e r v i n gt h es u r f a c ef e a t u r e s b a s e d o nt h es i m i l a r i t i e si n c l u d i n gg e o m e t r yi n t e n s i t ya n df e a t u r e so fs a m p l ep o i n t s ，a n o n - l o c a ld e n o i s i n ga l g o r i t h mf o rp o i n t - s a m p l e ds u r f a c e si sp r e s e n t e d b yu s i n g t h et r i l a t e r a l f i l t e r i n go p e r a t o r , t h eg e o m e t r yi n t e n s i t y o fs a m p l ep o i n ti s d e t e r m i n e d a c c o r d i n gt ot h e i rr e g u l a rg r i d so fg e o m e t r yi n t e n s i t y , t h es i m i l a r i t y 浙江丈学博士学位论文 o fg e o m e t r yi n t e n s i t yb e t w e e np o i n t si sm e b s u r c d b a s eo nm e a ns h i f tc l u s t e r i n g , t h e p o i n t - s a m p l e d s l l l f a 瞄a r ec l u s t e r e di n t oc l u s t e r s a c c o r d i n g t ot h e s u r f a c e - f e a t u r e ss i m i l a r i t y b yt h es i m i l a r i t i e s ，t h ef i l t e r e dp o i n t - s a m p l e dg e o m e t r y w i t ht h ef i n ef e a t u r e si sa t t a i n t e d am e t h o di s p r e s e n t e df o rp a t c h i n g h o l e so n p o i n t - s a m p l e d m o d e l a n d s y n t h e s i z i n gs u r f a c ew i t hd e t a i l s b yt h es l l r f a c er e c o n s t r u c t i o nb a s e do nr a d i a l b a s i sf u m c t i o n s ，t h eh o l ei sp a t c h e dw i t has m o o t hs u r f a c e u s i n gt h et r i l a t e r a l f i l t e r i n go p e r a t o r , t h eg e o m e t r yt e x 她r e so f t h ee x i s t i n gs a m p l ep o i n t sa r ep r o d u c e d a sa r e s u l t , t h eg e o m e t r i cd e t a i l so nt h e s m o o t hc o m p l e t e dp a t c ha r eg e n e r a t e db y o p t i m i z i n gac o n s t r a i n e d # o b a lt e x t u r ee n e r g yf u n c t i o n0 nt h ep o i n t - s a m p l e d s u r f a c e s b a s e do ng e o m e t r yi m a g e s a na d a p t i v ec u r v a t u r es i m p l i f i c a t i o nm e t h o df o r p o i n t - s a m p l e dm o d e li sp r o p o s e d b yp r o j e c t i n gi t ss p h e r i c a lp o l a rc o o r d i n a t e s o n t oap l a n e , t h ep o i n t - s a m p l e dm o d e li sr e p r e s e n t e da sg e o m e t r yi m a g e s t h e s i m p l ed e n s i t yi sd e f i n e da st h em a x i m u ms e a r c hr a d i u s0 1 1g e o m e t r yi m a g e si n o r d e rt oc o n v e n i e n t l yc o n t r o li t ，i nc o m b i n a t i o nw i mt h es u r f a c ev a r i a t i o na n d s i m p l ed e n s i t y , t h ep o i n t - s a m p l e ds u r f a c e sa r es i m p l i f i e d a n o t h e rs i m p l i f i c a t i o n a l g o r i t h mi s b a s e d0 ns i m i l a r i t yi n c l u d i n gs t r o n gf e a t u r e - e d g ei n t e n s i t ya n d s u r f a c ef e a t u r ea n i s o t r o p y u s i n gt h en o r m a lt e n s o rv o t i n g , t h ep o i n t - s a m p l e d s b r f a c e sa 黼s e g m e n t e di n t ot w op a r t s ，o n ef o rt h es t r o n gf e a t u r e - e d g ei n t e n s i t y a n da n o t h e rf o rt h en o n s t r o n gf e a t u r e - e d g e i n t e n s i t y b a s e o nm e a ns h i r c l u s t e r i n g , t h es e c o n dp a r ti st h e nc l u s t e r e di n t o c l u s t e r sa c c o r d i n gt ot h e f e a t u r e ss i m i l a r i t y t h ef i r s tp a r ta m 蠢lt h ec l u s t e r sa l er e s p e c t i v e l y s i m p l i f i e d b a s e do i l s p h e r i c a lp a r a m e t e r i z a t i o n a r o b u s tm o r p h i n ga l g o r i t h mf o r p o i n t s a m p l e dg e o m e t r yi sp r e s e n t e d s o u r c ea n dt a r g e tm o d e l sr e p r e s e n t e db y p o i n t - s a m p l e dg e o m e t r ya r ef i r s tp a r a m e t e r i z e do n t oas p h e r e , r e s p e c t i v e l y a f t e r 采i 罂薹i n gt h ec o r r e s p o n d i n gf e a t u r e so ft w om o d e l so nt h e i rs p h e r e s ，t w os p h e r e s a r ep r o j e c t e do n t oae o m m o nr e c t a n g l e - p a r a m e t e rd o m a i na n dt h ec o r r e s p o n d e n c e b e t w e e ns a m p l ep o i n t so nt h et w om o d e l si sb u i l tu s i n gt h i sr e c t a n g l ed o m a i n i n 浙江大学博士学位论文a b s t r a c t o r d e rt op r e s e r v et h eg e o m e t r i cd e t a i l so f p o i n ts e ts u r f a c e s ，t h ea b s o l u t eg e o m e t r y o ft h ei n b e t w e e nm o d e li sc o m p u t e db ym e a n so fl a p l a c i a no p e r a t o ra n di t s 飘l r f 嬲a l ed y n a m i c a l l yu p s a m p l e du s i n ga m o “n gl e a s ts q u a r e sm e t h o d s oa st o e l i m i n a t et h ee r a c k s a p r o t o t y p es y s t c mf o rd i g i t a lg e o m e t r yp r o c e s s i n go fp o i n t - s a m p l e dm o d e l si s i m p l e m e n t e da n di n t r o d u c e d t h es y s t e ma c t u a l l yi saf i a m e w o r ko f3 dg e o m e t r y a c q m s i f i o i l ，r e p r e s e n t a t i o n , p r o c e s s i n ga n dr e n d e r i n g t h em a i nc o m p o n e n t so f t h e s y s t e mi n c l u d ev a r i o u sn o v e la l g o r i t h m so nr e n d e r i n ge s t i m a t i o no fl o c a ls u r f a c e d i f f e r e n t i a l s ，d e n o i s i n g , g e o m e t r yc o m p l e t i o n , s i m p l i f i c a t i o na n du p - s a m p l i n g ， p a r a m e t e r i z a t i o n , m o r p h i n g , t e x t u r em a p p i n ga n ds y n t h e s i s a san 哪t y p eo fm e d i ad a t a , p r o m i s i n gp r e s e n t a t i o nf o r3 ds u r f a c e ， w o r ki nt h el a s tc h a p t e r t h ep o i n t - s a m p l e dg e o m e t r yi sa ne x t r e m e a n ds ow ed i s c u s ss o m ed i r e c t i o n sf o rf u t u r e k e y w o r d s ：s u r f a c ed i f f e r e n t i a l s ，p f i n c i p a lc o m p o n e n ta n a l y s i s ，m o v i n gl e a s ts q u a r e s s u r f a c e , d e n o i s i n g , n o r m a lt e n s o rv o t i n gt r i l a t e r a lf i l t e r i n go p e r a t o r , m e a ns h i f t c l u s t e r i n gp a r a m e t e r i z a t i o n , g e o m e t r yc o m p l e t i o n , t e x t u r es y n t h e s i s , s i m p l i f i c a t i o n , m o r p h i n g 浙江大学博士学位论文图目录 图目录 图1 1 b t m n y 的三角网格模型和点模型2 图1 2 点模型配准示意图5 图1 3 点模型特征提取8 图1 4 点模型的编辑和造型1 0 图2 1 采样点的肛最近邻域点集( a ) 及其协方差椭球体( b ) 1 6 图2 2k i t t e n 点模型的曲率可视化1 9 图2 3 可视化时使用的调色板。1 9 图2 4 点集以( 只) 的m l s 2 2 图2 5i g e a 噪声模型的可视化效果。2 3 图2 6 采样点a 的( 只) 2 4 图2 7f a n d i s k 噪声模型2 7 图2 8f a n d i s k 噪声模型去噪结果的比较2 7 图2 9d r a g o n h e a d 噪声模型2 8 图2 1 0d r a g o n h e a d 噪声模型去噪结果的比较2 8 图2 1 1i g e a 噪声模型去噪结果的比较2 9 图2 1 2b u s t e 点模型的去噪效果和平均曲率可视化3 0 图2 1 3f a c e 点模型的几何强度和m s 聚类3 2 图2 1 4 均匀几何强度网格g 的构建3 4 图2 1 5f a c e 噪声模型去噪结果的比较3 7 图2 1 6g a r g o 噪声模型去噪结果的比较3 9 图2 1 7b u s t e 噪声模型去噪结果的比较4 0 图3 1 本文几何修复算法流程4 4 图3 2 边界点判定的角度准则4 7 图3 3 边界点判定的半圆盘准则示意图4 7 i v 浙江大学博士学位论文图目录 图3 4 边界点的探测a 4 8 图3 5 边界点的探测b 4 9 图3 6m c 过程得到光滑修复采样点的2 d 图示5 3 图3 7 点集曲面单元块划分一5 6 图3 8 离散拉普拉斯算子5 7 图3 9 纹理网格g 的构建5 8 图3 1 0i g c a 点模型的几何修复6 l 图3 1 lr o c k a r m 点模型的几何修复6 2 图4 1f i s h 模型的几何图像6 6 图4 2d a v i d 点模型的简化及其点绘制图( 百分数为简去率) 7 2 图4 3p u l l e y 点模型简化8 8 及其点绘制图7 3 图4 4f i s h 点模型简化8 5 后简化结果的比较7 4 图4 5 误差和平均曲率可视化时使用的调色板。7 4 图4 6 点模型特征边性的可视化效果与强特征边性点集。7 6 图4 7 点模型i g e a 的局部模式点集及其聚类7 7 图4 8 i g e a 点模型简化9 0 及其点绘制图。8 0 图4 9d r a g o n 点模型简化9 2 及其误差可视化效果点绘制图8 l 图4 1 0f a n d i s k 噪声模型简化9 5 及其r b f 曲面重建8 2 图5 1 点模型b i m b a 、i g e a 和d a v i d 头像之间的渐变8 5 图5 2 本文渐变算法总流程8 6 图5 3自适应地移动特征点局部邻域。8 8 图5 4m l s 重采样效果9 l 图5 5 中间点模型的比较t = o 1 2 。9 2 图5 6 中间点模型的比较t = 0 8 9 2 图5 7 中间点模型的生成t = 0 3 0 。9 3 图5 8 点模型m o a i 、r a b b i t 和r a m c s s c s 之问的渐变9 3 图5 9 点模型f r o g 、d u c k 和h o r s e 之间的渐变9 4 v 浙江大学博士学位论文图目录 图5 1 0 点模型g a r g o y l e 、s p h e r e 和d o g 之间的渐变9 4 图6 1 本文点模型数字几何处理原型系统9 6 图6 2q s p l a t 算法与本文算法绘制效果的比较9 8 图6 3 本文算法的绘制效果9 9 图6 4 本文算法绘制的点模型透明效果1 0 0 图6 5 点元预处理可视化图1 0 2 图6 6 点模型的拉普拉斯去嗓和平均曲率流去噪1 0 3 图6 7 点模型的纹理映射( 矩形区域) 1 0 5 图6 8 点模型的纹理映射( 复杂区域) 1 0 5 图6 9 点模型的纹理合成1 0 5 图6 1 0c u p 模型的r b f 重采样效果1 0 6 v i 浙江大学博士学位论文 表目录 表目录 表2 1b l t 、m l s 和l h d 三种去噪算法的部分实验统计数据 表2 2 三种去噪算法相关参数的设置和相应的实验统计量 表4 1 本文算法p _ 2 、p = 4 与迭代法的比较 表4 2 三种简化算法的实验统计数据 表5 1 本文的实验统计数据 6 6 l o l 2 3 7 8 9 浙江大学博士学位论文第1 章绪论 第1 章绪论 近年来，继以三角网格模型为研究对象的网格数字几何处理后，以离散点为 表面表达方式的点模型由于其数据获取方便、数据结构简单等优点，已成为计算 机图形学中一个研究热点。点模型是一种新兴的几何曲面表达形式，因此与传统 的数字图像处理和视频处理等相当成熟的学科相比，点模型的数字几何处理尚处 在发展阶段。本文以计算机图形学，计算机辅助几何设计，离散微分几何学和数 字信号处理为坚实的理论基础，对点模型数字几何处理的若干核心技术进行深入 的研究，主要集中在点模型的去噪、几何修复、简化和重采样、渐变、绘制和纹 理映射及合成等领域：本文算法所实现的大量实例也证明了算法的有效性和实用 性。 本章的主要内容是对这些领域的相关研究工作进行回顾，并介绍本文的研究 工作概要。 1 13 d 数字模型的表示 选取合适的数学描述方式表示3 d 模型的表面是3 d 数字几何处理的一个核心 问题。在过去数十年中，面向不同的应用领域，提出了多种不同的曲面表示方式。 在c a d 领域主要采用参数曲面，如b e z i e r 曲面、n u r b s 血面和细分曲面等；在医 学应用领域常采用隐式曲面，如水平集( l e v e ls e t ) 、径向基函数( r a d i a lb a s i s f i m c f i o n ，r b f ) 和距离场( d i s t a n c ef i e l d ) 等；在游戏、电影等娱乐业领域主要 采用三角网格的表示方式以及在多种领域中最新采用的点模型表示方式。 近年来，由于三维扫描设备的普及和扫描技术所取得的重大进展，使得散乱 点云数据模型已在工业设计、艺术、考古、文物复原和保护、电子商务等多种领 域获得了广泛的关注和应用。对散乱点云而言，目前通常采用三角网格和点模型 两种表示方式( 如图1 1 所示) ；前者将散乱采样点( 点元) 三角网格化进而得到 模型的网格表示( 如图1 1 ( b ) 所示) ，而后者则是直接将模型表示为点元集合的形 浙江大学博士学位论文第1 章绪论 式( 如图1 1 ( c ) 所示) 。下面对这两种形式的模型进行简要的介绍。 ( a ) 真实感绘制( b ) 三角网格模型( c ) 点模型 图1 1b u n n y 的三角网格模型和点模型 1 1 1 三角网格模型 目前在计算机图形学中，三角网格是3 d 模型的主流表示方式，它的主要优 点在于： ( 1 ) 三角网格具有强大的表面表达能力。任何拓扑和任意形状的模型外表 面都能用三角网格进行表达，而且这种表达方式不需要满足复杂的片内光滑条 件。 ( 2 ) 对三角面片的几何处理和绘制已得到高速图形硬件的支持。 尽管三角网格作为一种简单实用曲面表示方式在几何造型等领域中表现出 其特有的优势，然而，随着现在实际使用的三角网格模型数据量越来越大，所表 现的几何模型越来越复杂，三角网格表示方法亦表现出它的局限性和不足： ( i ) 三角网格模型是通过对原始采样点云进行曲面重建而获得。 由于采样曲面上包含有噪声点和裂缝以及原始采样点数量巨大，所以现有的 曲面网格重建算法难以取得满意的效果且计算量巨大。 ( 2 ) 三角网格的几何处理算法大多需要维持二维流形表面的拓扑一致性。 拓扑信息的记录使得存储量加大；拓扑一致性的维持导致网格曲面的处理算 法变得复杂，当拓扑改变时，在某些情况下可能需完全重建网格以维护模型的拓 浙泼大学博士学位论文 第1 章绪论 矜信息。 ( 3 ) 网格模型的网格数量与驻示器的分辨率麓异巨大。 从绘制的角度来看，数百万个三角形的模型投影到屏幕上后，一个屏檠象素 霹缝会存多个德绘艇蛇三臻形，此黠，采用传统的累搬光攫化三角网格算法进行 绘制己失去了意义，导致现有的高速网格图形硬件滩以发挥其优势。因此对于高 度复杂熬足餐模登，基于纛戆绘毒l 穆是一耱更鳄静绘割算法。 1 1 。2 点模型 近年来，点模毅的数字几何处理弓l 起了学术界的极大关注，并进行了相当多 的研究工终。相关研究者之所玖对赢模墼产生极大兴趣，燕要是鬣圆如下：庞大 数爨级网楱模型拓扑关系的维持需要巨大的开销；近年来，激光扫描技术墩褥了 重大进展，3 d 激光扫描设备的精度己达到驻毫米缀l l 】，因此扫描得到的点模型由 匿大数量鲍3 d 采榉点缀威，于楚翘望能爨接基予这些离数采样点元来表承复杂 的几何模爨：点模型己拥静成熟的绘制技术，如q s p l a t 方法 2 1 ，椭圆加权平均 ( e w a ) 貉l 等。 点模型采用离散的采样点集来表示连续的模型外表面，即在连续的模裂外表 西上，按定静撬辩采样，产生一系弼表蔼采样点 a ，熊 ( 再为采样纛数) 。 每个采样点通常包禽几何信息( 如3 d 坐标和法向) 、表顾外观属性( 如：纹理 颜色) 及其它材料属性( 如反射率等) 。与其它表示方式相比，点模型具有两个 特点；( 1 ) 无拓扑连接信息期每令采样点都是孤立存德的敬魏点，这搜褥基于 扫描数据的曲面容易重构；( 2 ) j 均匀采样即模裂的表面采样点怒任意分布的， 这经褥熹袋邃瑟豹霪采襻攥捧篦较篱荸。蒸是这薅令特点( 优势) 键藏了杰模型 数字几何处理这一研究领域，与网格模型数字几何处理相比，点模挺数字几何处 理滏处在发震除段蠢方兴采艾，予是我 秘将本文静研究工豫集孛予这一领域。 1 2 点模型数字凡何处理熬研究巍容 点模缴获取之簸，便霹对其进行特征分柝和几姆造型等数字几侮处理。点摸 3 浙江大学博士学位论文 第l 章绪论 型数字几何处理的研究内容包括几何处理、几何造型和点模型的绘制。几何处理 主要有几何修复、曲面分析、滤波、重采样、简化压缩、分割、形状匹配、特征 提取等；造型的研究内容有布尔求交、自由变形、表面着色、纹理绘制、雕刻、 动画等。由此可见，点模型数字几何处理的研究内容十分广泛，我们按照数字几 何处理的流程将其大致分为五类，即：点模型的预处理、点模型几何属性的分析 和处理、点模型的几何编辑和造型、点模型的渐变( 动画) 和点模型的绘制。在 下面五节中，我们对点模型数字几何处理的已有工作进行回顾。 1 3 点模型的预处理 三维扫描设备的普及和扫描技术取得的重大进展，使得实物模型的3 d 扫描数 据的获取非常便利；然而，在扫描的过程中，由于各种因素使获得的点模型主要 存在着三种缺陷，即偏离于原始曲面的噪声、采样点问包含有重叠和模型曲面上 出现有孔洞。因此，必须对获得的点模型进行光顺去噪、模型配准和模型修复等 预处理操作【4 】。 1 3 1 点模型的光顺去噪 在点模型的去噪过程中，一个重要的问题是在剔除噪声获取离散曲面更高阶 光滑性的同时，如何能够有效地保持曲面的固有几何特征，并尽量防止体积收缩 和模型扭曲变形。 p a m y 等【5 】通过将采样点模型表面先分成块，然后对每一块通过局部高度场逼 近进行重采样，进而将图像中基于f o u r i e r 的光谱分析方法应用于采样点几何。该 方法通过对点模型进行光谱分析和滤波，达到去噪的目的。a l e x a 等【6 l 采用 m l s ( m o v i n gl e a s t s q u a r e s ) 方法逼近原始点模型，然后将点移到其对应的曲面上 来消除噪声，但由于求解m l s 曲面需要解一非线性优化问题，因此该方法的效率 不高。f l e i s h m a n 等f 7 l 等将图像双边滤波去噪函数拓展到用于二维流形表面上，提 出了保特征的网格去噪算法；由于该算法不需拓扑连接关系，因此也适用于点模 型的去噪，在去噪的同时能够有效地保持模型的特征。胡国飞等嘲提出了基于三 4 浙江大学博士学位论文 第1 章绪论 维m e a n s h i r 过程的各向异性点模型去噪算法，该方法将顶点法向和曲率作为特征 分量，顶点坐标值作为空间分量，通过m e a n s h i r 过程寻找其局部模式，并进行自 适应聚类和邻域的自适应选取，在此基础上提出顶点估计的三边滤波器，在获得 去噪效果的同时有效地保持了特征。肖春霞等【9 l 提出了基于动态平衡曲率流的去 噪算法，该方法有效地保持了曲面特征和约束了模型变形，但由于引入了约束体 积的强迫项，使得算法的复杂度较高。 1 3 2 点模型的配准 在扫描3 d 实体时，由于受到测量设备和环境的限制，物体表面完整测量数据 的获得往往需要通过多次测量完成。由于每次测量得到的点云数据往往只覆盖物 体部分表面，并且可能出现平移错位和旋转错位，因此为了得到实体完整表面的 点模型，需要对这些局部点云数据进行整合和配准【1 0 ，1 ”，如图1 2 所示。 ( a ) 原始数据 图1 2 点模型配准示意图 ( b ) 配准后的效果 常见的点云配准的方法有：标签法【1 2 】，即在测量时人为的贴上一些特征点， 然后使用这些特征点进行定位，这种方式仍然是依赖于测量和仪器的；提取特征 法如提取轮廓曲线【1 3 】等，这种方式要求点云有比较明显的特征；i c p ( i t e r a t i v e c l o s e s tp o i n t ) 算法【1 4 ，1 5 】，这种方式一般来说精度较高但速度较慢。 浙江大学博士学位论文第1 章绪论 1 3 3 点模型的修复 由于实体表面有可能存在各种缺陷，同时受到测量设备、测量方法自身的限 制，在表面数据获取的过程中会产生洞和裂缝的情况；同样，在对点模型数据进 行大规模形变的编辑处理时，模型亦会出现裂缝等现象。模型修复成为三维数据 获取或编辑之后的一个重要处理过程。 模型修复的目标是：不仅要对洞、裂缝等进行修复，同时对修复好的区域要 尽可能复现类似于周围区域的细节。点模型修复的常规方法是基于隐式曲面的修 复法，如c a r t 等使用全局紧支撑的径向基函数拟合离散点集、a h n 等【1 7 和w a n g 等【1 8 】分别进行m l s 曲面重建，以此实现孔洞的修复。尽管隐式曲面修复法，相对 简单，容易实现，但所构造的孔洞曲面是光滑的，故缺乏曲面的几何特征。s h a f t 等【1 9 1 提出了一种基于上下文的点模型修复方法，该方法通过分析模型的几何特 征，采用纹理合成的思想修复模型，获得了较好的修复效果，避免了因填充区域 过分光滑而产生的表面失真。但该方法需要采用m p u ( m u l t i 1 e v e lp a r t i t i o no f u n i t y ) 局部重建曲面，并对点集进行相似性匹配，因此计算量大且不稳定，难以做到实 用。 对于有颜色纹理的表面模型，不仅需要修复其几何还需要修复出模型表面的 颜色纹理信息。p a r k 等f 2 0 】通过为待修复的区域构造一个局部参数化，然后将图像 p