（教育技术学专业论文）点云模型的特征提取与数据优化.pdf

南京师范大学申请硕士学位论文 摘要 随着激光扫描和结构光扫描等三维扫描技术的不断发展和成熟，直接通过三维扫 描技术获取物体形体信息的方法得到了广泛的应用，点云模型成为一种新兴的数字媒 体表达方式，基于点的图形技术迅速成为国内外几何建模领域的研究热点。 基于坚实的理论分析和实验基础，本文对从点云几何性质的计算，到点云数据的 优化，再到点云模型谷脊特征的提取与增强等一系列问题进行了深入的研究，取得了 若干研究成果。 本文的工作主要包括五个方面： 给出了点云模型一系列几何属性的计算方法，通过k 近邻协方差分析方法计算 点云的法向，同时提出六源点法向传播方法为点云调整法向。此外本文通过移动 最小二乘方法计算点云的局部曲面拟合多项式，并为每个点计算曲率值、曲率场 信息等。 为点云模型提供一个滤除噪声和漂移点的方法。该方法基于k 近邻和平均的点 距值的思想，参考平均点距离值设置噪声点和漂移点的判断阈值，从而提高了点 云模型去噪算法的模型自适应性。 基于曲率自适应的k d 树分块思想，本文提出一种自适应的点云简化算法。该算 法利用协方差矩阵分析中特征值的比例关系估算点云中点的曲率，通过设置分块 点数阈值和曲率阈值的方法对点云进行k d 树分块，然后选择每块最有点实现点 云的简化。该方法能稳定的去除点云中的冗余数据。 提出一种基于移动最d - 乘拟合方法和局部v o r o n o i 构造的点云加密方法。构建 每个点的局部支撑平面并在局部支撑平面上构造邻点的v o r o n o i 图，寻找该点的 有效增加采样区域，建立栅格，通过将有效栅格点投影到局部最小二乘拟合曲面 上得到新的上采样点。通过调整采样栅格和采样控制函数可以满足不同的上采样 要求，为高分辨率绘制等提供支持。 为点云模型提供一个鲁棒的谷脊线提取算法。算法采用多步逼近的策略：首先根 据每个点的局部最小二乘拟合曲面多项式计算每个点的主曲率，并用绝对值较大 的主曲率标识出谷脊潜在特征点；然后通过将特征点投影到离其最近的潜在特征 线上得到增强的特征点；再对增强后的特征点进行平滑，选择合适的平滑点生成 特征折线；最后再对特征线进行进一步的扰动滤除等操作得到光滑的谷脊线。实 验结果表明，本文算法稳定、抗噪性强、能满足多分辨率的特征提取要求。 本文五个部分相互关联，又层层深入。大量的实验结果和分析，证明了本文中的 南京师范大学申请硕士学位论文 数字几何处理算法的强壮性和实用性，能为点云的其它处理提供稳定的支持。基于对 大量相关资料的深入研究以及大量实验分析，本文在结论部分给出了四个有意义的未 来研究方向。 关键词：点云，点云，几何分析，法向调整，数据优化，去噪，简化，增加采样，特 征提取与增强 h 南京师范大学申请硕士学位论文 a b s t r a c t w i t ht h er a p i d d e v e l o p m e n to f3 ds c a n n i n gt e c h n o l o g i e s ，m o d e l i n gd e t a i l e d3 d s h a p e sb ys c a n n i n gr e a lp h y s i c a lm o d e l si sb e c o m i n gm o r ea n dm o r ec o m m o n p l a c e a sa n e w t y p eo fm e d i ad a t a ，p o i n tc l o u di sp l a y i n gam o r ei m p o r t a n tr o l ei n3 dd i g i t a lg e o m e t r y r e p r e s e n t a t i o n p o i n tb a s e dg r a p h i c si sf a s tb e c o m i n gah o tt o p i ci n d i g i t a lg e o m e t r y p r o c e s s i n g b a s e do nt h es o u n dm a t h e m a t i c a lf o u n d a t i o na n de x p e r i m e n tf o u n d a t i o n ，w et a k ea d e e pr e s e a r c ho nas e r i e so fi s s u e sw h i c hr a n g e sf r o mt h eg e o m e t r i ca n a l y s i so fp o i n tc l o u d ， t op o i n td a t ao p t i m i z a t i o na n df e a t u r ee x t r a c t i o na n de n h a n c e m e n t t h em a j o rc o n t r i b u t i o n so ft h ed i s s e r t a t i o na r e - t h em e t h o d sf o rc o m p u t i n gg e o m e t r i ca t t r i b u t e sa r ep r o p o s e d b a s e do nc o v a r i a n c e m a t r i xa n a l y s i so v e rk n e a r e s tp o i n t s ，w ec o m p u t en o r m a l so f p o i n tc l o u d ，t h e na d ju s t t h en o r m a lo r i e n t a t i o nb yp e r f o r m i n gs i x s e e d s p r o p a g a t i o na l g o r i t h m b e s i d e st h a t ， o no b t a i n i n gl o c a lp o l y n o m i a lf i t t i n g sb ya p p l y i n gm o v i n gl e a s ts q u a r e sm e t h o d ，t h e c u r v a t u r e sa n d p r i n c i p a ld i r e c t i o n so fe v e r yp o i n tc a nb ec a l c u l a t e d r e m o v i n gn o i s ea n do u t l i e r sf o rp o i n tc l o u d b ya p p l y i n gk n e a r e s ta l g o r i t h ma n d a v e r a g es t a t i o nd i s t a n c e ，w es e tt h r e s h o l dv a l u ef o rn o i s ea n do u t l i e ra d j u s t m e n t a c c o r d i n gt oa v e r a g es t a t i o nd i s t a n c eo fp o i n tc l o u d ，s oa st oi m p r o v et h ea d a p t i v e l yo f t h ed e n o i s i n ga l g o r i t h m b a s e do nc u r v a t u r e a d a p t i v e k d t r e ec o n s t r u c t i o n a n a d a p t i v ep o i n t c l o u d d o w n s a m p l ea l g o r i t h m i s p r e s e n t e di n t h i sp a p e r t h ec u r v a t u r eo fp o i n ti s a p p r o x i m a t e db yc o m p u t i n gt h ep r o p o r t i o no fe i g e n v a l u e so fc o v a r i a n c em a t r i x ，a n d w ec o n s t r u c t i n gk d t r e ef o rs u b d i v i d i n gp o i n tc l o u db ys e t t i n gt w o t h r e s h o l d s ，o n ei s p o i n tn u m b e r , t h eo t h e ri sc u r v a t u r e ，a n dt h e nt h ep o i n tc l o u di sd o w n s a m p l e db y f i n d i n gar e p r e s e n t a t i v ep o i n tf o re a c hc l u s t e r r e d u c i n gt h ec o m p l e x i t yo fs u c h r e d u n d a n td a t as e t si so n eo ft h ek e y p r e p r o c e s s i n gt e c h n i q u e sf o rp o i n tc l o u d p r o p o s e a p o i n tc l o u du p s a m p l i n ga l g o r i t h mw h i c hb a s e do nm o v i n gl e a s ts q u a r e sa n d l o c a lv o r o n o ic o n s t r u c t i o n o nf i n d i n gal o c a lr e f e r e n c ed o m a i nf o re a c hp o i n ti np o i n t c l o u d ，av a l i du p - s a m p l i n gr e g i o ni sc a l c u l a t e df o re a c hp o i n tv i ac o n s t r u c t i n gl o c a l v o r o n o id i a g r a mo ft h ep o i n tw i t hi t sn e i g h b o r s b u i l ds a m p l e - 酣di nv a l i dr e g i o n ，w e g e tn e wu p 。s a m p l e dp o i n tb yp r o j e c t i n gg r i dp o i n to n t ot h el o c a ls u r f a c ef i a i n g p o l y g o n a l d i f f e r e n ta p p l i c a t i o n r e q u i r e m e n tc a nb es a t i s f i e db yu s i n gd i f f e r e n t 1 1 1 s 锄p i e g r i da n dd i f f e r e n tc o n t r o lf u n c t i o n ，a n di tu s e f u lf o rh i g h - r e s o l u t i o nr e n d e r i n g ar o b u s ta l g o r i t h mf o re x t r a c t i n gv a l l e y r i d g e sf o r mp o i n tc l o u d o u ra l g o r i t h mi s b a s e do nm u l t i s t e pr e f i n e m e n to p e r a t i o n s ：u s i n gm o v i n gl e a s ts q u a r em e t h o d ，w ef i ta s m o o t hp a t c hf o rn e i g h b o r h o o do fe a c hp o i n tt h e nc a l c u l a t et h ep r i n c i p a lc u r v a t u r ef o r e a c hd o i n t p o t e n t i a lv a l l e y r i d g ep o i n t sa r e i d e n t i f i e da c c o r d i n gt ot h eb i g g i s h p r i n c i p a lc u r v a t u r e a f t e re n h a n c i n gv a l l e y - r i d g ep o i n t sb yp r o j e c t i n go n t o t h e i rc l o s e s t p o t e n t i a lf e a t u r el i n e s ，w es m o o t h t h ep r o j e c t e dp o i n t s ，a n dg r o wp o l y l i n e st h r o u g ht h e s m o o t h e dp o i n t s f i n a l l y ，s m o o t hv a l l e y sa n dr i d g e sa r ea c h i e v e da f t e rr e s o l v i n gt h e r e s u l t s t h ee x p e r i m e n t si n d i c a t et h a t o u ra l g o r i t h mh a sw e l ls t a b i l i t ya n ds t r o n g a n t i n o i s ep e r f o r m a n c e ，a n di ta l s ol e a d sg o o dr e s u l t st om u l t i - r e s o l u t i o ne x t r a c t i o n s t h ea b o v ef i v ed i f f e r e n tr e s e a r c hi s s u e sa r ei n d e p e n d e n t ，w h i l ea l ea l s oi nc o n j u n c t i o n w i t he a c ho t h e r t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t e dt h eh i g hr o b u s t n e s s ，p r a c t i c a l i t y , a n dg e n e r a l i t yo fa l g o r i t h m si n t r o d u c e di nt h i st h e s i s a sd e e ps t u d yo nr e l a t e dd a t aa n d a n a l y s i so fe x p e r i m e n tr e s u l t s ，w eg i v e f o u rs i g n i f i c a n tt o p i c sf o rf u t u r ew o r ki n t h e c o n c l u s i o nc h a p t e r k e yw o r d s ：p o i n tc l o u d ，g e o m e t r i ca n a l y s i s ，n o r m a la d j u s t m e n t ，d e n o i s i n g ，d o w n 。s a m p l e ， u p s a m p l e ，f e a t u r ee x t r a c t i o n i v 南京师范大学申请硕j ：学位论文 第1 章引言 在数字化现实世界的过程中，随着三维扫描与建模技术的提高，以及计算机软硬 件环境的不断发展，三维数据已经逐渐结合到许多应用领域中，同时也促进了多学科 交叉的新型领域的发展，如数字博物馆、虚拟场景浏览、文物与历史遗迹保护、游戏 娱乐，逆向工程等。 通过三维扫描技术以一定密度采样物体表面所得到的所有点的集合，称为该物体 的点云模型，其中点基元被称为采样点。研究以点为基元的点云模型的表示、处理、 渲染、以及几何造型技术的学科被称为基于点的图形学( p b g ：p o i mb a s e dg r a p h i c s ) 。 自2 0 0 2 年以来，每年的欧洲计算机图学年会( e u r o g r a p h i c s ) 都有一个专门的p b g 研讨 会，基于点的图形学引起了国内外众多研究学者的研究兴趣。 1 1 点云数据的采集 点云数据的采集是逆向工程中一个非常基础且重要的工作，近年，随着新技术的 应用，测量技术得到了长足的发展，出现了各种不同的点云数据采集方法，主要分为 接触式和非接触式两大类【l 2 j 。 接触式数据采集设备是通过安装在机械臂末端的探头接触被测物体的表面来测 量数据的。三坐标测量机( c o o r d i n a t e m e a s u r i n g m a e h i n e ，c m m ) 是典型的接触式数据 采集设备。三坐标测量机在三个互相垂直的导轨上移动，探头以接触式的方式传递信 号，通过计算三个导轨的位置得到被测物体表面各点的坐标。三坐标测量机的优点是 准确性和可靠性高，不受被测物体材质、反射性以及表面颜色的影响。其缺点在于采 用接触式测量的方式，在测量过程中会因为摩擦力和弹性产生变形，不适用于测量软 质、易碎、易变形、超薄样件等，同时该方法还有测量效率较低的缺点。接触式数据 采集设备的典型代表是英国r e n i s h a w 公司生产的系列三坐标测量仪，如c y c l o n e 扫描仪。 目前常用的非接触式三维点云采集技术主要是利用光学、声学、磁学等领域的基 本原理，得到相应的物理模拟量并对其进行适当的换算转化为被测物体上点的坐标。 图像分析法是通过对被测物体进行多角度或者多次曝光拍摄，利用一点在多个图像中 的亮度，色度，相对位置等信息，通过视差计算距离，从而得到点在空间中的位置【3 j 。 结构光与图像分析法不同，该类方法需要向被测物体投射一定模式的光纹，如条形光、 栅格状光等，最典型的是m o i r e 干涉条纹法。a t o s 三维扫描仪是一种光栅投影式扫描 仪，通过捕获光被曲面反射后的图像以及对图像的分析获得三维点坐标【4 1 。在逆向工 第1 章引言 程中通常采用基于三角形的激光扫描仪，该方法利用光源与影像感应装置( 如摄像机) 间的位置与角度来推算点的空间坐标。根据激光照射方式可将激光三角移位传感器分 为两类，一类是斜射式，如日本的k e y e n c e 公司生产的l d 系列；另一类是直射式 的，有r e n i s h a w 公司生产的0 p 2 ，k e y e n c e 公司生产的l c 系列，l b 细类等多 种型号。上述三维扫描方法最大的优点是无接触，数据采集过程不会产生因为摩擦力 和接触压力所引起的形变测量误差、速度快、自动化程度高，且所测数据分辨率高， 能准确反映复杂形体的表面信息。缺点是该类方法容易受到被测物体表面材质和环境 的影响，如物体表面的颜色、反射率、环境光的干扰，同时基于上述物理模型的测量 方法大多数都不能通过单视点一次获取，而是需要将多次测量结果配准为一个整体垆j 。 1 2 点云数据的处理及点云系统 为得到被测模型的细节特征，需要使用较高分辨率的测量方式，这使得测量得到 的模型往往是规模较大的散乱点云。同时由于测量仪器和其它诸如环境因素的影响， 不可避免地存在噪声。使用存在大量冗余和噪声的点云数据会降低后续处理工作的效 率，所以原始点云需要进行如下数据处理，包括点云的几何分析、平滑去噪、重采样、 分块、压缩、特征提取等操作。 基于点的点云处理技术以点作为曲面绘制和造型的基本元素，处理那些用一组点 采样表示物体曲面的几何对象。与基于网格的技术相比，基于点的处理技术具有下列 优点： 1 没有显示的拓扑关系，可以实现几乎连续的层次多细节( l e v e l o f - d e t a i l ，l o d ) 控制，并可方便的改变曲面的拓扑。 2 无需存储边的连接信息，极大地减少了存储空间的需求，且满足复杂形体的 表示要求。 3 可以直接实现基于点的模型绘制，避免复杂的动态网格控制，在绘制过称中 节省了系统资源。 由于点云模型采样技术的提高以及点云强大的形状表现力、高效的显示机制，基 于点云的造型技术受到了众多学者的关注，许多点云处理系统也相继出现。 1 2 1 点云数据的优化 通过三维扫描所得到的原始点云模型通常还不能直接应用，还需要对其进行一些 数据优化的处理。 1 点云的几何分析 测量得到的原始点云数据仅包含点的坐标信息，要对点云进行进一步的操作就必 须对其进行微分几何性质的计算与分析，如点云的法向信息、点云曲面信息、点的 2 南京师范大学申请硕上学位论文 曲率信息等等。对点云进行几何分析是后续点云处理工作的基础。 2 噪声点的消除 测量中由于测量仪器以及其它方面的因素，噪声点的存在不可避免，而噪声点会 使重构出来的曲面出现较大的形变，故在进行点云数据操作之前，需先进行消除噪声 的工作。对于有序或者部分有序的点云，常用的去噪方法有维纳滤波、最小二乘滤波、 卡尔曼滤波、标准高斯滤波、平均滤波和中值滤波算法等，而对于无序点云的噪声点 处理则有拉普拉斯算法、平均曲率流和双边滤波器、均值漂移滤波算法等。 3 点云的简化 点云的简化是指用点数较少的点云来逼近原点数太多的点云。点云简化作为点云 处理的一个基础步骤，可以去掉原始点云数据中的冗余部分，得到一个精简的模型， 有利于点云的后续的处理和造型。 4 点云的加密 实体平滑地方，点云数据量比较少，不足以表达实体的细节信息，为充分获得实 体各部分特征，应对过于稀疏的点云数据进行加密处理，使最后构造的实体能达到最 小允许误差。 5 特征线提取 散乱点云的特征主要包括特征线、凹凸结构和边界等【6 】。目前离散点云的特征技 术主要是指特征线的提取及运算。特征提取过程可分为两步，首先根据形状变化的剧 烈程度从模型中抽取特征点，而后将特征点按模型的拓扑结构连接形成特征线。 6 点云分割 点云数据分割也是数据预处理的关键技术之一，数据分割是根据组成实物外形曲 面的子曲面的类型，将属于同一子曲面类型的数据成组，这样全部数据将划分成代表 不同曲面类型的数据域，为后续的曲面模型重建提供方便。特征线的提取与数据分块 实际上是相互联系的。利用提取的特征线可方便地将点集分割成不同部分，而若先将 数据分块，则分割而成的数据块之间的交线即可作为特征线。 7 曲面的构造 为更好地展示被测对象的形体结构，需要对点云模型进行曲面重建，目前曲面重 建的方法有基于网格的曲面重建、基于点的造型以及c a d 中的n u r b s 曲面等。文【7 】 研究讨论三种基于点云的曲面重构方法，m l s ( m o v i n gl e a s ts q u a r e s ) 8 1 ，r b f ( r a d i u s b a s i sf u n c t i o n ) 【9 】和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 i m p l i c i t s ) f 10 1 ，三种方法的建立方 式不同，因而生成的曲面表达式也不一样。最明显的区别是m l s 方法的生成结果仍 然是点云模型，而r b f 和m p u 方法则为曲面生成了三角网格【7 1 。 第1 章引言 1 2 2 点云系统及应用 自1 9 8 5 年l e v o y l l l 】等开创性地提出使用点基元进行曲面建模，点云模型的处理 受到越来越多研究学者的关注，国内外许多公司相继推出了自己的点云处理的商业化 软件，如i m a g e w a r e 公司的s u r f a c e r ，d e l c a m 公司的c o p y c a d 等。国内有浙江大 学推出的r e s o f t ，p a u l y 1 2 】等提出基于点云模型的曲面编辑建模方法，并建立了一个 系统p o i n t s h o p 3 d ，该系统是一个具有代表性的基于散乱点云的处理系统，具有较强 大的点云模型编辑功能。 虽然有众多学者投身于点云系统的研究，但是目前的点云系统在系统兼容性、特 征细节精确表达等方面还存在一定缺陷，这也严重限制了其在制造业中的应用。 1 3 课题的主要来源和主要工作 本论文课题来源于国家自然科学基金( 0 6 0 8 7 3 1 7 5 ) 、江苏省教育厅江苏高校自然 科学基础研究项目( 0 7 k j d 4 6 0 1 0 8 ) 、江苏省2 0 0 9 年度普通高校研究生科研创新计划 ( 点集模型的特征提取与强化技术研究，项目编号：c x 0 9 s0 0 9 r ) 以及2 0 0 9 南京师范 大学优秀学位论文培育项目，主要针对散乱点云模型对其进行数据优化和快速稳定的 点云谷脊线提取与增强等问题进行深入的研究，数据优化工作包括去除点云中的噪声 点和漂移点，点云数据的简化以及点云数据的增加采样等。点云谷脊特征线提取与增 强分为预处理运算与特征提取两个部分，预处理运算主要负责谷脊线提取的前期工 作，通过计算点云的微分属性为特征线的提取工作提供依据；特征提取主要按照提取 潜在特征点、优化特征点、生成特征线、优化特征线的思路最终得到点云模型光滑的 特征线。 1 4 本文主要内容及组织 本文针对点云模型的数据优化以及谷脊特征线的提取与增强展开了研究，论文共 包括五章。第一章就本文研究的意义以相关技术背景进行了叙述，概要的介绍了点云 数据的采集以及点云模型处理的基本工作。 第二章介绍了点云数据微分几何属性的计算与分析。具体包括：点云模型法向的 计算，并提出基于六源点的法向调整新思想，点云的最小二乘曲面拟合算法以及点云 中采样点曲率的计算等。 本文研究的主要内容和贡献在于第三章和第四章。在第三章中我们在深入研究已 有的去噪算法和简化算法，提出了改进的基于k 近邻的点云去噪算法和模型自适应的 点云简化方法。同时也研究提出了基于m l s 和局部v o r o n o i 区域栅格化的点云上采 样方法。 4 南京师范大学申请硕士学位论文 在第四章中，我们提出一种新的点云模型谷脊线提取与增强算法框架流程。该算 法首先通过协方差分析方法计算每个点的法向，然后通过拟合每个点的有限邻域计算 其最小二乘拟合曲面多项式，通过多项式计算每个点的绝对值最大主曲率，然后按照 潜在特征点提取，特征点增强，特征点的平滑，生成特征折线，特征线优化的步骤完 成谷脊线的提取。该算法抗噪性强，稳定且效率较高，为后续的点云模型处理如，自 适应简化，曲面编辑，特征强化等提供了技术支持。 在第五章，总结了本文的研究工作，分析了本文有关点云数据优化处理以及点云 谷脊线提取与增强方法的优点及其不足，并指出进一步的研究和探索计划。 第1 章引言 6 南京师范大学申请硕上学位论文 第2 章点云数据的几何性质【注】 点云数据的几何性质包括点云的法向、曲面表达式、点的曲率信息、曲率场信息 等，计算和分析点云的几何信息是点云简化、增加采样、特征提取等一系列点云处理 工作的基础。由于点云模型缺乏连接信息，要计算点云数据的几何性质，就需要利用 点云中点的邻域关系以及局部点的分布信息，通过估算方法计算点云的微分几何性 质。 2 1 曲面法向的计算与调整 点云法矢的求取对于曲面重建和曲面绘制，光照渲染等都至关重要。目前估算离 散点云法矢的方法主要有“点云曲面切平面逼近法”即通过计算逼近点云的切平面 的法矢来计算点的法矢量。h o p p e 等在文【1 3 j 中提出通过计算每个点的k 近邻点，并计 算其最小二乘拟合平面，拟合平面的法向即为该点的法向。这种方法在点采样不是很 均匀时不稳定，如果点云上的点呈规则行状分布，则点的k 邻近点可能分布在同一 条行上，造成拟合平面与实际切平面垂直，而此时，计算每个点r 半径内邻点的逼近 平面可能更加合适。还有一些学者1 1 4 。16 j 提出了其它一些邻点选择策略，如选择该点的 二分邻近点或者选择其v o r o n o i 邻点，然后直接计算所得邻点的逼近平面并计算其法 向，或者建立该点与所得邻点的三角剖分，计算该点邻近三角形的的法向平均值作为 该点的法向。文i l 卜1 9 】使用最d , - 乘法逼近离散点的邻近点集，得到一个微分切平面， 把微切平面的法矢作为该点的法矢，这种方法对任意给出的无规则的空间散乱点都可 进行法矢估计。 上述提到的算法都存在一个问题，即所得点云法矢有的指向待重建点云曲面的内 部，有的指向待重建点云曲面的外部。因而需要对点云的法矢进行朝向的调整，使得 调整后的法矢方向一致指向待重建曲面的外部或者内部。h o p p e 提出建立每个点阢与 其邻点p ，的r i e m a n n i a n 图，然后为每条边赋一个权重：设，? ，分别为只和p ，点的 法矢，则边p , p ，的权重为1 一h 刀，i 。当两个点的切平面接近平行时，两点连线边的权 重接近0 ，而两点切平面夹角越大则边的权重越大。以z 分量最大的点为根遍历 r i e m a n n i a n 图生成其最小生成树，然后按照深度优先遍历最小生成树完成点云法矢的 调整。该算法的基本思想是让法矢的调整沿着曲率最小的方向进行传播。 法向调整的难点在曲率变化大的地方法矢的传播的正确性受到挑战，所以要选择 注：本章主要内容发表于：t h ei n t e r n a t i o n a lc o n f e r e n c eo ni n f o r m a t i o nm a n a g e m e n t , i n n o v a t i o nm a n a g e m e n ta n d i n d u s t r i a le n g i n e e r i n g ( i c l l l 2 0 0 9 ) 以及t h ei n t e r n a t i o n a lc o n f e r e n c eo nc o m p u t a t i o n a li n t e l l i g e n c ea n ds o n w a r c e n g i n e e r i n g ( c i s e 2 0 0 9 ) 7 第2 章点云数据的几何性质 模型上曲率变化小的路径进行法矢传播 本文算法采用逼近切平面方法来计算每个点的法向。计算每个点及其一定半径邻 域内点的协方差矩阵，最小特征值对应的特征向量即为该点的法向。半径邻域太大时 法向计算误差大，半径太小则在密度小的区域容易出现法向计算错误，本文算法为弥 补该邻域选择方法的的不足，采用较大的半径，同时为减少计算误差，建立带权重的 协方差矩阵进行法向计算。不同于其它法矢调整算法，本文算法分别从 x ，+ x ，】，+ j ，z ，+ z 六个方向分量最大的点开始进行法矢传播。每个点与其邻点之间的 传播能力w 用两点单位法矢点乘值的绝对值来衡量，当w 大于一定阈值时，证明两点 的法矢变化小于一定角度，两点间可以进行法矢传播。 2 1 1 曲面法向的计算 设散乱点云p = p 。) ，i 1 ，) ，且p 点云中不含法向信息。 选择每个点p ，半径厂邻域内的点n b h d ( p ，) = p ) ，l lp ，一p ，i i r ，j = 1 ，七建立 带权重的协方差矩阵： b = ( p j p ，) ( 少，一p ，) 。e a ( p f ) p i e n b h d ( p ) e o ( p ，) 是一个正的单调递减函数，当p j 离p ，越近时点的权重越大，反之越小。 p ，一p ，为列向量，( p ，- p 。) r 为p ，一p ；的转置向量，b 为一个对称的半正定3 x 3 矩阵。 计算b 的特征值和特征向量，记矩阵召的特征值为气， ，五，( 五 如) ，特征值对 应的特征向量分别为，h ，v 2 ，记v o 为点p ，点的法向。 图2 1 兔子点云模型和人头模型法向调整前 从试验结果( 图2 1 ) 可以看出通过协方差分析方法所计算的点的法向有的指向点 云曲面的内部，有的指向点云曲面的外部，从而需要对法向进行调整使其统一指向点 云曲面内部或者外部。 囤 南京师范大学申请硕士学位论文 2 1 2 法向的调整 本文算法从点集p = p f 1 ，n ) 中选择六个稳定传播源点，分别为x 、y 、z 分量最大和最小的点。然后从这些传播源点出发对p 中每个点进行法向传播调整。p ； 点，半径内的点记为n b h d ( p ，) = p ，) ，j = o ，k ，相邻点p ，p ，的法向点乘绝对值缈，用 于标识两点之间的法向传播能力，即c o ，= | 聍，i ，刀，和刀，都是单位法向，所以 1 国，0 。当两点法向越接近平行则缈，越接近l ，表示两点间的传播能力越强。设置 传播阈值f ，本文取f = 0 6 ，当q f 时，表明p ，和p ，之问存在法向连续性，可进行 法向传播，即如果吩斑， 0 ，则n 取一玎，。当c o ， f 时证明p ，和p ，之间不能进行法向 传播。我们为p ，设置两个标志：b n o r m a l ，b n v i s i t e d ，分别表示该点是否完成法向调 整，以及该点，半径内的邻点是否全部完成法向调整。算法采用局部深度优先策略在 传播的过程中选择法向已经调整好但其厂半径内邻近点法向未全部被调整的点作为候 选传播源点压入堆栈，当一次传播终止后，从堆栈中弹出一个元素，作为下一次法向 传播的源点。多源点法向传播算法具体过程如下： 1 ) 调整六个稳定源点的法向，即使x 分量最大点的法向指向+ x ，x 分量最小 点的法向指向一x ，依此类推。 2 ) 建立六个堆栈c s x ，c s x ，c s y ，c s y ，c s z ，c s z ，用于存储从上述六 个源点出发传播过程中产生的候选传播源点。 3 ) 依次从六个源点p 进行法向传播，从n b h d ( p ) 中选择w ，f 且其b n o r a m l 标 记为f a l s e 的点，按照缈，的值，从大到小依次对p ，点的法向进行调整，并将其b n o r m a l 标识设置为t r u e 。同时按照p 邻近点法向传播的反顺序将p 压入其对应的堆栈( 如从x 分量最大源点出发，则将候选点压入堆栈c s x ) ，即缈i 值越大越后压入，缈i 最大的点 置于栈顶。如果n b h d ( p ) 中点的法向全部被调整过了，则将点p 的b n v i s i t e d 标记设 置为t r u e 。 4 ) 接着依次从六个堆栈弹出栈顶元素，如果弹出的栈顶点其b n v i s i t e d 为t r u e ， 则继续弹出下一个元素，如果弹出的栈顶点其b n v i s i t e d 为f a l s e 并且检测其厂半径内 邻近点未全部被调整则该点为源点，若检测其，半径内邻近点已全部调整，则将该点 的b n v i s i t e d 标记为t r u e ，并继续从该堆栈弹出点，直至找到满足条件的源点，然后 重复步骤3 ) 。 5 ) 直到六个堆栈都为空，再对整个点云进行检测，找到法向未被调整的点，按 照三次最近距离法【2 0 j 继续对其进行法向调整，直到所有点的法向都被调整完。 在极少数特殊情况下，六个源点中会有重合的点，排除重复点后再完成以上步骤。 图2 2 为调整后的效果。该法向调整算法适用于封闭模型，而对于其它类型的模型， 可以根据模型的特点选择合适的几个传播源点，如单片模型( 图2 3f r a n r g b 模型) ，则 使用一个方向的法向传播即可。 9 第2 章点云数据的几何性质 ( a ) 法向调整指向点云曲面外部( b ) 法向调整指向点云的内部 图2 2 法向调整后的兔子点云模型和人头点云模型 ( a ) 调整前的法向( b ) 法向调整前光照效果( c ) 调整后的法向( d ) 法向调整后光照效果 图2 3 人脸点云模型法向调整前和法向调整后 图2 4 其它模型的法向计算与法向调整 l o 南京师范大学申请硕上学位论文 2 2 最小二乘曲面拟合 曲面逼近又可以分为参数曲面逼近和隐式曲面逼近，前者主要用b e z i d r 曲面与 b 样条曲面等1 2 l j 进行曲面逼近计算；但目前最新的研究进展大多是基于隐式曲面逼近 的，如：m a r c o n i 2 2 1 ，j a l ( o n s e n 【1 3 ，2 3 1 ，以及b r e e n i 冽等均通过在点云模型的体网格上构 造距离场函数来得到点云模型的隐式曲面表示；f l e i s h m a n 【2 5 】，a l e x a l 2 6 1 和p a u l y 等 则是通过寻找逼近点云模型的曲面多项式或径向基函数等来拟合曲面。而g 醯l 等【2 8 】 使用代数逼近曲面来重建点云模型的光滑曲面模型。 移动最d , - 乘( m l s ，m o v i n gl e a s ts q u a r e s ) 点云模型曲面重构法【8 , 2 9 1 是基于点的 图形学中最重要的曲面重构方法，它包括支撑平面的计算和局部高阶多项式拟合两个 步骤。该方法基于严格的数学推导，能够较好地解决点云模型曲面重构过程中的去噪 与特征保留之间的矛盾；还可用于点云模型重采样和基于点的渲染。以下将对该方法 展开讨论研究。 问题描述：给定的一个不含有法向信息和任何连接信息的点云模型 p = 娩) ，p t r 3 , i 1 ，) ，计算点云中每个点的局部最j j n - - 乘拟合曲面。 2 2 1 支撑平面与局部坐标的建立 查找只点在厂半径内的邻近点n b h d ( p ，) = p ) ，| ip ，一p ，临，= o ，k ，建立 n b h d ( p ，) 的协方差矩阵， 口= e ( p j d ，) ( 乃一d p jc n b t t d ( p ) 其中 铲昙壹p ， q 2 i 缶p j 是n b h d ( p , ) 的重心，b 是一个对称的半正定3 x 3 矩阵。计算b 的特征值和特征 向量，设特征值为无，丑，丑，( 凡 a 的法向刀，进 行调整，然后在日，平面上建立局部坐标系 ，e 绣) ，q 为原心，局部坐标系的z 轴 为调整后的佛。 2 2 2 曲面拟合多项式 在局部坐标系( d ，u ，1 ，z ，) 内用二次多项式吕拟合而( p ，) ，使昌满足( 2 1 ) 式， 第2 章点云数据的几何性质 r a i n 2uj 。l p j e n b h d t p t 、 其中既表示髟沿着船，在多项式曲面上的投影。式( 2 1 ) 的意义是： 在拟合曲面上投影点的距离平方和最小。设吕表达式为 & ( “，1 ，) = a + b u + 卯+ 如v + p 甜2 + 声2 ( 2 1 ) 式可以改写成 ( 2 1 ) 使易点与其 ( 2 2 ) r a i n ( ( 乃一d f ) 力f - g ( u j ，v 埘2 ( 2 3 ) pj n b h d t p ( 甜，v ) 为易在局部坐标系内( 甜，1 ，) 平面上的坐标。f l _ | ( 2 3 ) 式对多项式的各个系数 求一阶导数得到六个线性方程，然后用高斯消元法计算出的各个系数。 2 2 3 点在坐标系之间的转换以及点在曲面上的投影 在最d , - - 乘的应用中经常需要将局部坐标系中的点转化到物体坐标系中，或者将 物体坐标系中的点转化到局部坐标系中，同时也可能需要计算已知局部坐标系( “，v ) 平面内的点求其在局部拟合曲面上的投影点，或者已知空间中的一点求其在局部曲面 上的投影点。 1 ) 从局部坐标系到物体坐标系 设局部坐标系( 0 ，就，v ，n ，) 中的点为g ，将该点转化到物体坐标系中，需要进行两 次旋转变换和一次平移。 首先对q 进行两次旋转，设v = 1 f z 2 + n j y 2 ，c o s l = n , z v ，s i n l = n , y v ， c o s 2 = v ，s i n 2 = 一胛i j 。设g 为g 旋转后的点。 g = g x ，g y ，q z f 0 c o s 2 l s i n 2 0 c o s l s i n l 得到g 后再对其进行平移，q = g + q ，q 即为点q 在物体坐标系中的坐标点。 2 ) 从物体坐标系到局部坐标系 设物体坐标系中的点为p ，将该点转化到局部坐标系( 0 ，“，v ，n ，) 的过程与1 ) 过 程正好相反，需要先进行一次平移操作然后进行两次旋转变换，转换过程如下： 将物体坐标系的原点平移到局部坐标系的原点p = p 一0 ，然后再对坐标进行两次 旋转运算。设v = 力，z 2 + 啊y 2 ，