（计算机科学与技术专业论文）大规模点云模型几何造型技术研究.pdf

浙江大学博士学位论文 摘要 三维几何模型已成为继声音、图象和视频之后一种重要的数字媒体。点云模 型是以离散采样点为基元的几何模型，是三维几何模型的一种自然表示方式。点 云模型数据结构简单、存储空间紧凑，具有表达复杂表面细节的能力。随着三维 光学扫描设备的快速发展，大量高精度的光学扫描数据唾手可得。近年来，国内 外学者对以点云模型为研究对象的基于点的计算机图形学作了大量的基础研究， 取得了大量的研究成果。点云模型预处理、表示、渲染等研究领域取得了相当大 的进展。这些研究成果为基于点的图形学的继续深入研究及点云模型的应用奠定 了基础。几何造型是通过用户交互对三维几何模型进行编辑和变形的过程，是三 维几何模型应用的最重要的环节。由于各种原因，点云模型几何造型技术的发展 相对滞后。 本文以大规模点云模型为研究对象，研究了适用于大规模点云模型的表示、 特征分析、几何造型相关技术。本文的研究内容涵盖了建立一个点云模型几何造 型系统所必须的一些重要研究课题。在所研究的主题中取得了若干创新的研究成 果。本文的研究成果和创新点主要包括以下几个方面： 1 ) 点云模型预处理技术 本文提出了一种新的大规模点云模型简化算法。算法由两个阶段组成：第一 阶段根据几何近似原理将点云模型分割成与平面近似的多个分片；第二阶段在分 片的基础上进行层次空问分割简化。这种新的简化算法将分片技术与简化技术结 合，以分片作为层次空间分割的前处理步骤，能有效减少直接层次空间分割简化 所产生的几何误差，而且同时具有层次空间分割简化算法速度快的优点。 2 ) 点云模型分解与骨架提取 三维几何模型分解是计算机图形学研究的基础问题之一。本文提出了一种多 分辨率点云模型分解技术。首先构建点云模型带连接拓扑信息的简化表示。基于 该简化表示，本文将网格模型的模糊聚类层次分解方法思想推广至点云模型分 浙江大学博士学位论文 摘要 解。对于大规模点云模型，我们先在低分辨率下将模型进行粗分解；然后构建各 分解部分的高分辨率，并进行更深层次的分解。多分辨率技术与层次分解技术结 合，成功地解决了大规模点云模型分解速度和分解效果的矛盾。 本文还提出了一种新的大规模点云模型特征骨架提取算法。我们首先构建了 大规模点云模型的非流形简化表示。在此简化表示的基础上，依据m o r s e 理论， 通过选择合适的m o r s e 函数确定模型的中心点和各特征点。依次用最小测地线连 接中心点与各特征点，得到表面骨架。采用可见反力场方法，将表面骨架推至模 型内部并作光顺后处理得到位于模型内部的特征骨架线。我们的算法能直接处理 大规模点云模型，而且稳定性好、速度较快。 3 ) 点云模型几何造型技术 本文提出并实现了大规模点云模型融合造型方法。使用本文的融合造型方法， 用户可以采用点云模型表面拖拽的方式灵活选择融合位置完成融合，也可以选定 融合区域进行拼接融合。融合过渡区域由基于径向基函数隐式曲面构建，能获得 自然光滑的过渡效果。由于没有连接拓扑约束，我们用一种简洁的方式完成点云 模型的融合后处理。 骨架驱动的皮肤变形是一种重要的三维几何模型变形方法。本文提出了一种 弹性与刚性变形相结合的骨架驱动的皮肤变形分析方法。骨架驱动的皮肤变形分 为刚性变形和弹性变形两部分，刚性变形可由骨架的刚体旋转直接求得，仅局部 区域需进行弹性变形分析。由扩展的模态分析方法建立局部区域的弹性变形方 程，然后用无网格方法求解此方程。由于仅需要对局部区域作弹性分析，其求解 速度非常快。本文还提出一种骨架与点云模型之间的自动对应技术，免去用户指 定皮肤与骨架对应关系的过程。 关键词：点云几何造型，点云简化，点云分片，点云分解，点云骨架提取，点 云融合，骨架驱动的皮肤变形，m o r s e 函数，模态分析，无网格方法 浙江大学博士学位论文 a b s t r a c t 3 dg e o m e t r yi sb e c o m i n gi n c r e a s i n g l yi x y p u l a ra san e wf o r mo fd i g i t a lm e d i a f o l l o w i n gs o u n d ，i m a g ea n dv i d e o p o i n tc l o u dm o d e l ，ag e o m e t r i cm o d e lt a k i n gp o i m a sap r i m i t i v e , i saf a i r l yn a t u r er e p r e s e n t a t i o i no f 3 dg e o m e t r y p o i n tc l o u dm o d e lh a s a s i m p l es t r u c t u r e ，a n di ti sv e r yc o m p a c ti ns p a c e t h i sm a k e , p o i n tc l o u dm o d e lv e r y e f f i d e n ti nr e p r e s e n t i n gl a r g es c a l eg e o m e t r ym o d e l sw i t hr i c hd e t a i l s w i t ht h er a p i d d e v e l o p m e n to fd i 垂t a ls c a n n e r , p o nc l o u dm o d e l sa r eu b i q u i t o u s p o i n tb a s e d g r a p h i c s ( p b g ) i sg a i n i n gp o p u l a r i t yi nc o m p u t e rg r a p h i c s i tf o c u s 髂o np o i n tc l o u d p r e p r o c e s s i n g , m o d e lr e p r e s e n m t i o n , a n dr e n d e r i n g r e c e n t l y , m a n yr e s e a r c hp a p e r s0 1 1 p b gh a v eb e e np u b l i s h e di nt h ec o m p u t e rg r a p h i c sc o m m u n i t y m o s to ft h e r e s e a r c h e sa l ec o n c e n t r a t u do np o i n tc l o u dp r g p r o c e g s , r e n d e r i n ga n dr e p r e s e n m t i o n t h e s er e s e a r c h e sf o r mas t r o n gf u n d a t i o nf o rf u t u r er e s e a r c h e sa n da p p l i c a t i o no f p o i n t c l o u dm o d e l e d i t i n ga n dd e f o r m a t i o no fg e o m e t r i cm o d e l sa r ee r n t i a lf o rt h e a p p l i c a t i o no fg e o m e t r i cm o d e l s c u r r e n t l y , t h e r ea r er e l a t i v e l yf e wr e s e a r c h e so n s h a p em o d e l i n gf r o mp o i n tc l o u dm o d e l s t h i st h e s i sf o c u s e so nr e p r e s e n t a t i o n , f e a t u r ea n a l y s i sa n dg e o m e t r i cm o d e l i n go f l a r g es c a l ep o i mc l o u dm o d e l s t h ec o n t e n to f t h i st h e s i sc o v e r sk e yt o p i c sf o rb u i l d i n g as h a p em o d e l i n gs y s t e mf r o mp o i n tc l o u dm o d e l s c o n t r i b u t i o n so ft h i st h e s i s i n d u d e ： 1 ) p r e p r o c e s s i n go fp o m td o u dm o d e l s w e p r o p o s ea n g ws i m p l i f i c a t i o na l g o r i t h mf o rl a r g es c a l ep o i n tc l o u dm o d e l s t h e a l g o r i t h mi sc o n s i s t i n go ft w os t e p s i nt h ef i r s ts t e p ，t h ep o i n tc l o u dm o d e li s s e g m e n t e di n t os e v e r a la p p r o x i m a t e df l a tr e g i o n s i nt h es e c o n ds t e p t h e s er e g i o n sa t e h i e r a r c h i c a l l yp a r t i t i o n e d c o u p l i n gp o i n t c l o u ds e g m e n t a t i o n , 0 1 1 1 a l g o r i t h mc a n r e d u c et h eg e o m e t r i ce r r o r sr e s u l t e df r o ms i m p l i f i c a t i o nw i t h o u ts l o w i n gd o w nt h e p e r f o r m a n c ei nh i e r a r c h i c a lp a r t i t i o n 2 1 d e c o m p o s i t i o no fp o i n tc l o u d sa n de x t r a c t i o no fs k e l e t o n s 3 dg e o m e t r ys e g m e n t a t i o ni saf o u n d m e n t a lr e s e a r c ht o p i co f c o m p u t e rg r a p h i c s 浙江大学博士学位论文 a b s t r a c t w e p r o p am u l t i - r e s o l u t i o nh i e r a r c h i c a ld e c o m p o s i t i o nm e t h o dt od e c o m p o s el a r g o s c a l ep o i n tc l o u dm o d e l s f i r s t l y , ar e p r e s e n t a t i o nw i t hl i n kt o p o l o g yi sc o n s t r u c t e df o r l o wr e s o l u t i o np o i n tc l o u dm o d e l b a s e do nt h i sr e p r e s e n t a t i o n , w ee x t e n dm e s h d e c o m p o s i t i o na l g o r i t h m st op o 妇c l o u ds e g m e n t a t i o nw i t hs o m em o d i f i c a t i o n s f o r l a r g es c a l ep o i n tc l o u dm o d e l s ，w cf i r s td e c o m p o s et h em o d e li n t os e v e r a lp a r t sa t l o w e rr e s o l u t i o n , t h e nc o n s t r u c tah i g h e rr e s o l u t i o nm o d df o re a c hp a r t , a n dp e r f o r m f u r t h e rd e c o m p o s i t i o no nt h i sh i g h e rr e s o l u t i o np o i n tc l o u dm o d e l w ep r o p o s ean o wc o n t r o l l e ds k e l e t o ne x t r a c t i o nm e t h o df o rl a r g es c a l ep o i n t c l o u dm o d e l s w ef i r s tc o n s t r u c tas i m p l i f i e da n dn o - m a i n f o l dr e p r e s e n t i o nf o rt h e p o i n tc l o u dm o d e l b a s e do nt h i sr e p r e n t a t i o n , a f t e rc o n s t r u c t i n gam o r s ef u n c t i o n , t h ek e r n e lp o i n ta n df e a t u r ep o i n t so fm o d e la r ei d e n t i f i e d c o n n e c tk e r n e lp o i n tw i t h e a c hf e a t u r ep o i n t sb yg e o d i s cl i n e w eg e tt h es u r f a c es k e l e t o n s p u s h i n gt h e 飘l 以c c s k e l e t o n si n s i d ep o 砬c l o u dm o d e lb yv i s u a lr e p u l s i v ef o r c ea n dt h e ns m o o t h i n gt h e m , w eg e tt h ec o n t r o l l e ds k e l e t o n s o u rs k e l e t o ne x t r a c t i o nm e t h o dc a l lb ed i r e c t l ya p p l i e d t ol a r g es c a l ep o i n tc l o u dm o d e l sa n di sb o t hr o b u s ta n de f f i c i e n t 3 ) s h a p em o d e l i n go np o j n tc l o u dm o d e l s a ni n t e r a c t i v eb l e n d i n gp r o t o t y p es y s t e mf o rp o i n tc l o u dm o d e l si sd e v e l o p e d u s i n go u rb l e n d i n gm e t h o d , u s 盯nd ob l e n d i n gb yd r a g g i n g - a n d - d r o po n p o i n t c l o u dm o d e lo n t oa n o t h e rt og e tan e wp o i mc l o u dm o d e l ；o rb yc u r i n gt w o s u b - m o d e l st og l u et h e mi n t oan 删p o i n tc l o u dm o d e l t h et r a n s i t i o nb l e n d i n gr e g i o n i sc o n s t r u c e db yan a t u r a la n ds m o o t hi m p l i c i ts u r f a c eb a s e do nr a d i a lb a s i cf u n c t i o n t h ef a c tt h a ti tl a c k sl i n kt o p o l o g ym a k e sb l e n d i n go np o i n tc l o u dm e d a l ss e e m sm o r e n a t u r et h a no nm e s hm o d e l s s k e l e t o n q r i v e ns k i nd e f o r m a t i o ni sav e r yi m p o r t a n t3 dg e o m e t r yd e f o r m a t i o n m e t h o d w ep r o p o s ea ne l a s t a s t i cd e f o r m a t i o nm i x e d 丽l hr i 百dd e f o r m a t i o nm e t h o d f o rs k e l e t o n - d r i v e ns k i nd e f o r m a t i o na n a l y s i s t h ed e f o r m a t i o no fs k i ni sd i v i d e di n t o r i g i dr e g i o n sa n de l a s t a s t i cr e g i o n s r i g i dd e f o r m a t i o nc a nb ec a l c u l a t e db yr i g i d r o t a t i o no fs k e l e t o n s e l a s t a s t i cd e f o r m a t i o ni sp e r f o r m e du s i n gam o d a lw a r p i n g a n a l y s i st e c h n i q u e t h em o d a lw a r p i n gp r o b l e mi ss o l v e db a s e dam e s h 船em e t h o d o u rs k e l e t o n - d r i v e ns k i nd e f o r m a t i o nm e t h o di sv e r ye f f i c i e n t i tg i v e sv e r yr e a l i s t i c 浙江大学博士学位论文 r e s u l t s an e wm e t h o di sd e v e l o p e dt oa s s i g nt h ei n f l u e n c eo f s k e l e t o n so ns k i n k e y w o r d s ：p o i n tc l o u ds h a p em o d e l i n g , p o i n tc l o u ds i m p l i f i c a t i o n , p o 缸c l o u d s e g m e m t a t i o n , p o i n td o u dd e c o m p o s i t i o n , s k e l e t o ne x t r a o n , p o i n tc l o u db l e n d i n g , s k e l e t o n - d r i v e ns k i nd e f o r m a t i o n , m o r s ef u n c t i o n , m o d a lw a r p i n ga n a l y s i s ，m e s hf r e e m e t h o d 浙江大学博士学位论文 图表目录 图表目录 图1 1 点云模型的计算机处理流程 图1 2r o b u s tm l s 去噪。 图1 3 交互式点云模型修复。 图1 4 裁剪s p l a t 图1 5 e w a 反走样 图1 6 绘制s p l a t 的不同改进 3 6 7 l o 1 3 图1 7 修正渲染缝隙1 4 图1 8 点云模型集成于基于o p e n g l 的复杂场景 图1 9 交互式点云模型编辑系统 图1 1 0 点云模型的表面纹理1 7 图1 1l 点云模型几何造型系统 图1 1 2 点云模型的c s g 几何造型。 1 8 图1 1 3 高塑性变形和柔性断裂的点云模型动画模拟2 0 图1 1 4 点云模型的碰撞检测处理2 l 图2 1 直接层次二分与先分片后层次二分效果对比2 7 图2 2 分片自适应层次分割简化算法流程2 8 图2 3 点采样曲面s 和r 的距离度量3 l 图2 4 分片平面近似结果3 3 图2 5c a r 模型与n e p t u n e 模型的分片结果 图2 6c a r 模型的层次细节表示一3 6 图2 7n e p t u n e 模型的不同简化结果3 7 图2 8 c a r t e r 模型的层次细节表示3 8 图2 9 不同简化算法对各模型的简化时闻比较3 9 图2 1 0 与网格简化方法的几何误差对比4 0 图3 1 几种常用的体包围盒4 6 图3 2 两种常用的b v h 4 6 图3 3 计算o b b 。4 7 图3 4 模型的o b b t ( p ) 和m ( o b b t ( p ) ) 。4 8 图3 5 不对称的邻域关系5 0 图3 7f e m a l e 模型多分辨率层次分解过程5 5 图3 8 不同模型的第一层分解效果5 5 图4 1 中值线、中值面与线骨架5 8 图4 2 点云模型骨架提取算法框架6 l 图4 f 3 平均测地距函数和特征点6 3 图4 4 空间均匀分布的光线与球面均布的点( m = 1 0 0 ) 6 5 图4 5 基于角度聚类的骨架光顺结果6 6 i v 浙江大学博士学位论文图表目录 图4 6 c y b e r w a r eh o r s e 在n = 1 2 0 时分片和骨架6 7 图4 7n e p t u n e 模型的骨架提取结果6 8 图4 8 点云模型线骨架提取实验结果。6 9 图4 9 本章算法与l e v e l - s e t 方法效果对比。7 0 图5 1 融合造型过程7 4 图5 2 将耳朵拖拽到人头的合适位置。7 6 图5 3 中心缩放与等距缩放7 7 图5 4 确定参与融合区域7 7 图5 5 基于边界的快速对其算法7 8 图5 6 融合后处理过程8 3 图5 7 抠去包围区域。8 4 图5 8 f e m a l e 模型和d o l l p h 模型拼接融合得美人鱼模型8 5 图5 9s o i d c r 模型h e l m e t 融合8 6 图5 1 0f e l i n e 模型与h o r s e 模型黏附融合得飞马模型。8 7 图5 1 1n e p t u n e 模型与d r a g o n 的手融合8 7 图6 1 关节点计算9 2 图6 2 确定骨架与皮肤对于关系9 4 图6 3 弹性变形区域与力学模型。9 5 图6 4 由多个关节旋转得到a r m a d i l l o 变形1 0 1 图6 5h o r s e 模型的多个变形姿态1 0 1 图6 6 结合变形和融合操作完成n e p t u n e 的一个动作造型1 0 2 表2 1 各简化算法的误差比较 表4 1 实验结果数据统计 表5 1 算法处理时间 v 3 9 ，6 7 8 5 浙江大学博士学位论文第1 章绪论 第1 章绪论 1 1 课题背景 三维几何模型是继一维的声音数据、二维的图像数据以及视频数据之后的一 种创新的数字多媒体数据。与传统的多媒体数据相比较，三维几何模型以其强烈 的真实感更符合人类对自然世界直观认识，受到了工业界和学术界的广泛关注。 基于三维几何模型的产品设计以及物理模拟已经逐渐取代二维设计和常规的实 验手段，在工业界获得广泛应用；以三维游戏为主体的数字娱乐近年来更是发展 得如火如荼；电子商务方面，三维产品展示成为促其发展的新动力；以三维数字 扫描为基础的三维模型重建和修复技术可以帮助历史文物返回原貌。总之，三维 几何模型已经对社会生活的各个领域产生了深远的影响。随着数据获取设备、计 算机硬件的迅速发展，加上与计算机网络技术日益融合，面向三维几何模型的数 字几何处理已成为计算机图形学、计算机视觉、数字信号处理等学科的前沿研究 领域和热门课题。 1 1 - 1 三维几何模型的表现形式 在三维几何模型快速发展与应用的几十年里，其基本问题之一，三维几何模 型的表现形式一直处于发展之中。三维几何模型的主要表现形式包括非均匀有理 b 样条曲面( n u r b s ) 、隐式曲面、网格模型。不同的表现形式在不同的应用领 域各具优势，使得三维几何模型的几种表现形式长期并存。如汽车、飞机等工业 领域采用n u r b s 表示；医学应用等领域采用隐式曲面表示；而数字娱乐、电子 商务等领域广泛采用的是网格模型表示。近十几年来，网格模型恃其结构简洁以 及较强的表达能力，得到了广泛的应用，成为主流的三维几何模型表现形式。 点云模型是一种新兴的三维几何模型表现形式。与网格模型相比，点云模型 无需繁琐的三角化过程，可直接表示和处理光学扫描数据；而且由于无需维护连 接拓扑信息，点云模型精简紧凑的数据结构使其具备表达丰富表面细节三维几何 模型的能力。 浙江大学博士学位论文第l 章绪论 点云模型直接以点为几何基元。在点云模型中，点基元被称为采样点。研究 以点为基元的点云模型的表示、处理、渲染、以及几何造型技术的学科被称为基 于点的图形学( p b g ：p o i n tb a s e dg r a p h i c s ) 。自2 0 0 2 年以来，每年的欧洲计算机 图学年会( e u t o g r a p h i c s ) 都有一个专门的p b g 研讨会，基于点的图形学引起了 国内外众多研究学者的研究兴趣。 1 1 2 点云模型研究内容及面临的挑战 点云模型的数字几何处理包括数据扫描、预处理、基于点的表示以及点云模 型的编辑和几何造型，最后对结果进行渲染( 图1 1 ) 。 扫描及预处理 点云模型的预处理，包括配准、去噪、简化、修补等技术。这些预处理技术 最初在以扫描数据为处理对象的逆向工程研究中得到广泛关注。p b g 的预处理技 术与逆向工程的预处理技术的内容与要求基本一致。目前，这些预处理技术已经 发展得较为成熟。 点云模型表示 点云模型是由没有连接拓扑信息的离散采样点组成的。s u r f c l 和s p l a t 是点云 模型最简捷的表示和绘制方式。为了研究点云模型所确定的曲面的性质，人们研 究了由点云模型的采样点集所确定的曲面，即点集曲面( p s s ：p o i n t s e t s u r f a c e ) 。 这种基于移动最d , - 乘( m l s ：m o v i n gl e a s ts q u a r e ) 投影所定义的移动流形曲 面为研究点云模型定义的曲面性质奠定了坚实的数学基础。 点云模型渲染技术 点云模型通常采用基于点的绘制技术进行渲染，基于点的绘制技术甚至比 p b g 的概念出现的更早。i 七v o y 和w l l i t t e d 【i 】首次提出直接用点作为基元绘制复杂 的三维几何模型。十多年后，g r o s s m a n 和d a l l y l 2 1 进一步完善了基于点的绘制技 术。q s p l a t 系绀3 】将基于点的绘制技术和多分辨率技术结合使得基于点的绘制技 术能够渲染顶点规模高达1 0 亿的三角网格模型。p b g 概念出现后，基于点的绘 制技术成为点云模型的标准渲染技术。点云模型渲染技术目前无论是从渲染的速 浙江大学博t 学位论文 第1 章绪论 度抑或渲染的效果上来看，均已发展地较为完善【4 “。 点云模型几何造型技术 几何造型技术是指对三维几何模型进行编辑和变形，得到符合用户设计意图 的三维几何模型的新形态或者新的三维几何模型。几何造型技术使三维几何模型 从模拟和表现物理世界提升到了改造和创新物理世界这个更高的层面上。正是因 为有从自由变形( f f d ： f r e ef o r md e f o r m a t i o n ) 到微分网格变形等几何造型技 术的不断发展，j 促进了网格模型的广泛应用。比较而言，在点云模型计算机处 理的各流程中，几何造型技术的发展较慢。研究点云模型几何造型技术，特别是 能直接处理大规模点云模型的几何造型技术，是促进点云模型应用的关键所在。 网譬 原始模型 。j 描及预处理基于点的表示几何造型 图1 1 点云模型的计掉机处理流样 点云模型几何造型技术发展滞后，一方面是因为几何造型技术必须建立在点 云模型表示和渲染基础之上；另一方面，点云模型几何造型技术研究也有其客观 存在的困难。我们认为，点云模型研究存在以下的挑战： 为了表达具有丰富表面细节的复杂对象，点云模型的数据规模非常大。 凭其紧凑的数据结构，点云模型表示和渲染这样的大规模数据时具有网 格模型无法比拟的优点，但如何对山点云模型表示的犬规模数掘进行数 字几何处理仍然是非常具有挑战性的工作。 在研究三维几何模型分解和骨架提取等基础性问题时，嘲格模型因为具 有稳定的连拓扑接信息，人们可以依赖连接拓扑信息提出有_ ； ! 【的算法： 而点云模型是由离散的采样点组成的，虽然可以借助采样点之洲的邻域 ?。 、 舻。 k鬻、 - 浙江大学博士学位论文 第1 章绪论 信息，但邻域信息是一种不稳定的信息。因此，在点云模型分解和骨架 提取等基础性问题上提出有效的算法仍然是非常困难的 点云模型在几何造型过程中由于无需考虑网格模型连接拓扑的约束，可 以根据需要灵活地向下或向上重采样，以减少数据处理的规模或获得更 丰富的表面细节。在点云模型几何造型技术中，如何将重采样技术与几 何造型技相结合，以获得高效高质量的造型效果是点云模型几何造型研 究所面临的困难。 1 2 相关研究 近几年以来，基于点的图形学的研究得到了广泛的关注本节我们回顾近年 来p b g 方面的相关研究工作。 1 2 1 点云模型预处理技术 由三维扫描设备获得的扫描数据一般不能赢接用于点云模型的数字几何处 理。必须对扫描数据傲必要的前处理，这些处理手段包括配准、去噪、修补以及 简化。 1 2 1 1 配准 光学扫描仪可以在数秒钟内直接获得被测物体表面的点云数据，但因光的线 性传播特性，在一个视角下扫描仪只能采集到物体某一部分表面的数据，物体整 个表面的数据需要从不同视角对物体进行多次测量来完成。每一次扫描都是在当 前坐标系下进行的，所以为得到被测物体完整的数据模型，需要确定一个合适的 坐标变换，将从各个视角得到的点集合并到一个统一的坐标系下，这就是点云数 据的配准。 目前，三维数据配准技术主要分两大类【7 】： 1 1 机器配准：采用经过高精度定标的仪器获取的多视点数据以及它们之间 的原始变换关系，来进行数据问的配准计算； 2 1 自动配准：利用数据中的变换信息或利用在数据获取的同时引入的其他 4 浙江大学博士学位论文 第1 章绪论 信息，对三维数据进行配准计算。其中自动配准技术与硬件无关，得到 了研究学者的广泛关注。 自动配准技术一般分为初始配准和精确配准两步 初始配准的方法有：标签法嘲，即在测量时人为地贴上一些特征点，然后使 用这些特征点进行定位，该方法仍依赖于测量和仪器；特征提取法，即通过提取 轮廓曲绀町作为对齐的基准，该方法要求点云有比较明显的特征。此外朱掣州通 过计算点云模型的法向和曲率信息，建立模型的几何哈希，然后进行初始配准， 也获得了较好的效果。 最近点迭代算法( i c p ：i t e r a t i v ec l o s e s tp o i n t ) 是经典的精确配准算法【l l j 。但 i c p 算法计算效率不高，国内外许多研究学者都为改进i c p 算法做出了努力【啪 o h e n 等【1 3 l 提出了用点的切平面来逼近点云，最后归结为求点到切平面的最小二 乘距离的方法，但其计算速度比较慢。b l a i s 等f 1 4 1 结合了逆向定标法和随机搜寻法 来提高速度，但会对配准精度产生一定的影响。l i 等【1 5 1 提出了一种迭代最近线方 法( i c l ：i t e r a t i v ec l o s e s tl i n e ) 算法，通过直接对两个点云中的点连线并寻找对应 线段进行配准。 1 2 1 2 去嗓 点云模型扫描过程中难免会产生一些噪声，因而去噪是点云模型预处理的一 个非常重要的处理手段。点云模型去噪的困难在于将无规则的噪声数据剔出的同 时。还需要有效地保持模型的特征，防止顶点漂移以及保体积等。p a u l y 掣1 6 】通 过将点云模型表面先分块，然后对每一块通过局部高度场逼近进行重采样，从而 把图像中基于f o u r i e r 的谱分析方法应用于点云模型。该方法通过对点云模型进行 谱分析和滤波，达到去噪的目的。a l e x a 掣1 7 】采用m l s 曲面逼近原始点集模型， 然后将点移到其对应的曲面上来消除噪声。m l s 曲面的高阶连续性使得该方法能 获得较好的去噪效果。但由于求解m l s 曲面需要解非线性优化问题，因此该方 法效率不商。f l c i s l 蚰缸等【1 8 】将图像双边滤波去噪函数拓展至二维流形表面，提 出了保特征的网格去噪算法。该算法不依赖连接拓扑信息，因此可推广至点云模 浙江大学博i 。学位论文第1 章绪论 型。胡因飞提出了基于三维m e a n s h i f t 过程的各向异性点云模型去噪算法。该 方法将顶点法向和曲率作为特征分量，顶点坐标值作为空间分量，通过m e a n s h i f t 过程寻找其局部模式，并进行自适应聚类和邻域的自适应选取，在此基础上提出 顶点估计的三边滤波器，在获得去噪效果的同时能有效地保持特征。肖春霞2 0 】 提出了一种凝于动态i f 衡曲率流方程的各向异性的点云模型光顺算法。其动态平 衡曲率流方程包含一个各向异性的曲率流算子和一个保持体积的强迫项。通过在 这两项之问建立一个平衡算予，使得曲面的特征雨i 噪声获得不同的处理方法，在 圳除噪声的刚时，能有效地保持了曲面特征。 f l e i s h m a n 等1 2 i l 提出了一种健壮的m l s 曲面重建方法。该方法能从有噪声的 点云模型重建出分段线性的光滑曲而。这种改进的m l s 重建方法不但能够有效 地之除点云模型f i 的噪，矗，而h 能有效地从点云模，弘中准确地蕈建出尖锐特征 ( 图1 2 ) 。最近，s c h a l l 等 2 2 1 将图像处理中的非局部邻域过滤fn o n 1 0 c a l n e i g h b o r h o o df i l t e r i n g ) 算法j h 于点云模型去噪，获得了理想的去噪效粜，算法同 样具有恢复点厶模型几何特征的能力。 盛摩 1 2 1 3 修复及补洞 i 维 _ i 描仪从物体表面采样时，获得的扫描数据会出现孔涮。原因有二，其 足遮挡、扫描仪的位置摆放等各种人为原因；其二源自一些需要扫描的物体r 如 雕像等) 山于保存的历史时川太久，自身有+ 些残缺。通常，点云模型的孔洞可 以：嘶咂建过槲一h3 咀过插值的方法构建光滑帅l 啊。似a m e n t a 等指出，处理 浙江大学博t 学位论文第1 章绪论 向基函数的 云模型的局 扫描数据时，大部分曲面重建算法仅能修复较小的孔洞。采用基于径 隐式曲面重构方法由于将整个点云模型当作一个隐式方程，能够在点 部空洞构建出光滑的过渡曲面【2 牝“，从而修复较大的孔洞。 夼凳奔套 图13 交互式点云模型修复 ( a ) 有缺陷的模型( b ) 确定孔洞( c ) 选择用丁修复的区域( d ) 修复结果 曲而重建方法修补孔洞的优点是在曲面重建过程中自动修复孔洞，f ：需要特 别的算法检测孔洞或人工干预：其缺点在于仅能根据点云模型的形态在t l # m 处形 成一个光滑修复面，对于有丰富细节和几何特征的点云模型而言，这种方法的修 复结果没有保证孔洞与其附近曲面特征的一致性，因而显得不自然。为解决此问 题，s h m - f 等2 7 1 提出了一种基于内容的模型修复方法。通过分析模型的几何特征， 采用纹理合成的思想修复模型。陔方法需要采用m p u 局部重建曲面，汁算量较 大。如果点云模型表面有纹理，点云模型修复过程时不但需要修复i u l 何信息而 且还要修复模型表面的颜色纹理信息。p a r k 等【28 】通过为要修复的区域构造一个局 部参数化，然后将图像p o i s s o n 方程推广到点云模型上，获得j l f g h 纹理颜色修 复结果( 图1 3 ) ，通过适当的人机交互，能够进一步增强修复效果( 图1 3 c ) 。 x i a o 等1 2 9 1 提出了一种新的在点采样，l 何上进行基于全局优化的表面颜色纹理修 复和基于上下文的几何修复的算法。算法以曲面上已知纹理为样本，通过最小化 一个带约束的全局能量函数实现对纹理的修复。 浙江大学博士学位论文 第1 章绪论 1 2 1 4 压缩 随着三维扫描设备的扫描精度的不断提高，人们已经能够轻易地获取海量的 测量数据。点云模型压缩成为高效的点云模型表示、传输、渲染和处理的必要手 段。与网格模型压缩类似，点云模型压缩可分为两类：单精度压缩编码( s i n g l e - r a t e c o d e r s ) 【捌和渐进压缩编码( p r o g r e s s i v ec o d e r s ) 【3 1 侧。与单精度压缩编码相比， 渐进压缩编码允许模型以渐进的方式传输和重构模型，因而更适于网络应用。 k r u g e r 掣3 5 】的处理方式不能简单地归为单精度或渐进压缩编码，虽然点云模型采 用渐进的方式编码，但是粗糙层次的字节流( b i t s t r e a m ) 没有嵌入到模型精细的 层次表示中。此外，一些点云模型算法仅能处理从流形曲面获得采样集 3 2 1 ，大部 分的点云模型压缩算法能够处理从任意拓扑对象的表面所获取的点云模型 为每个模型建立一棵预测树【研可以帮助预测和建立熵编码，但这种预测树并 不适用于渐进编码。f l e i s h m a n 等【3 6 l 建立了多层次的点云模型表示，为了提高编 码效率，首先将模型从三维降低到一维，然后再重建起多层次表示。o c h o t t a 等【3 2 】 先将三维模型划分然后为每个分片建立一个高度场，从而采用二维小波图象编码 压缩三维模型，这种方法的局限性在于无法处理非流形曲面。 大部分的点云模型压缩算法都是以八叉树为基础的。给定要压缩的点云模型 p 的包围盒，从点云模型中构建叶节点层数为上的八叉树d ，然后将点云模型p