（机械设计及理论专业论文）基于点的散乱点云处理技术的研究(1).pdf

华 中 科 技 大 学 博 士 学 位 论 文 摘要 基于点的点云处理技术是随着数据测量技术的进步而迅速发展起来的一门新兴技 术。该项技术以点作为曲面绘制和造型的基本元素，在提高模型绘制与重建的速度、 加 强处理超大规模点云的能力和简化计算量等方面体现出 独特的优势，目 前己 成为反求工 程的一个研究热点。 本文针对该项技术中的若千关键问题， 结合国家十五重点科技攻关 项目“ 产品设计c a d( 项目 编号:2 0 0 1 b a 2 0 1 a 0 2 )进行了深入研究。 点集简化是点云处理中首要的预处理环节。为尽量避免损失被测物体的工程信息， 提出了一种基于模糊聚类的简化算法。 通过引入几何相似性隶属度来表征被测物体形状 的自 然变化， 使简化点集倾向 于聚集在曲 面的陡峭区域， 降 低简化可能导致的形状损失; 同时以 强制约束相似性隶属度反映设计者的工程和设计要求， 能 有效抑制工程信息和设 计信息的缺失。 特征线提取是点云处理中另一项重要的预处理工作。为保证特征线提取的稳定性及 精度要求， 提出了一种基于数字图像薄化的多尺度特征线提取算法。 利用局部墒和重复 度描述采样点在不同尺度下属于某个特征的可能性大小， 保证算法的稳定性; 通过将提 取的 特征点云映射为数字图像和进行薄化处理， 获取光滑的特征线， 能在一定程度上处 理密度分布不均的点云，并保证特征线的质量。 曲面重建是点云处理的核心。为加快曲面重建的前处理速度，避免因采样点的少量 丢失而导致重建表面出现缝隙， 探讨了一种基于曲面单元分解的重建算法。 借鉴推进波 前法， 基于子域环的构造和中心环的推衍， 使所有点的法向 指向被测物体的外侧， 可缩 短法矢检验的时间; 在各采样点处建立相互交迭的曲面单元，以近似包围在点云内部的 空间， 可得到质量良 好的重建表面。 曲 面编辑是点云处理不可缺少的研究内容。为获取灵活的曲 面编辑能力，设计了一 种基于超二次曲面的约束变形算法。 建立基于超二次曲 面的一般约束变形模型， 使物体 在多种类型的约束下按指定的曲线位移产生多样化的变形; 采用局部墒加权的方式， 使 采样点能自 动估计变形的程度， 并在采样不足的区域插补适当数目 的点， 保证点云在变 形前后的采样率基本一致。 在上述理论研究成果的基础上，研制开发了基于点的三维散乱数据处理原型系统， 并已 作为一个模块嵌入三维c a d 系统一 i n t e s o l i d 中。 关键词:散乱点模糊聚类局部嫡曲 面重建约束变形 华 中 科 技 大 学 博 士 学 位 论 文 ab s t r a c t a d v a n c e s i n 3 d s c a n n i n g t e c h n o l o g i e s h a v e p r o m o t e d t h e e m e r g e n c e a n d r a p i d d e v e l o p m e n t o f p o i n t - b a s e d t e c h n i q u e s . p o i n t - b a s e d t e c h n i q u e s , b y w h i c h p o i n t s a r e u s e d a s s u r f a c e m o d e l in g a n d r e n d e r i n g p r i m i t i v e s , h as b e c o m e a n i m p o r t a n t r e s e a r c h f i e l d o f r e v e r s e e n g i n e e r i n g . t h e p a r t i c u l a r d o m i n a n c e o f p o i n t - b a s e d t e c h n i q u e s i n c l u d e s t h e e ff i c i e n c y a t r e c o n s t r u c t i n g a n d r e n d e r i n g v e r y c o m p l e x o b j e c t s a n d e n v i r o n m e n t s , c a p a b i l i t y o f d e a li n g w i t h d e n s e s c a tt e r e d p o i n t c l o u d , a n d s i m p l i c i t y o f r e n d e r i n g a l g o r i t h m s . b ase d o n t h e o v e r v i e w o f p o i n t - b ase d t e c h n i q u e s , s e v e r a l k e y i s s u e s i n c l u d i n g d a t a r e d u c t i o n , f e a t u r e l i n e e x t r a c t i o n , s u r f a c e m o d e l i n g a n d e d i t i n g a r e s t u d i e d i n t h i s d i s s e rt a t i o n , w h i c h i s s p o n s o r e d b y t h e n a t i o n a l k e y r e s e a r c h p r o j e c t o f t h e 1 0 t h f i v e - y e a r - p l a n o f c h in a ( g r a n t n o . 2 0 0 1 b a 2 0 1 a 0 2 ) . d a t a r e d u c t i o n i s t h e f i r s t p r e p r o c e s s i n g s t e p o f p o i n t - b as e d d a t a t r e a t m e n t . t o a v o i d l o s s o f e n g in e e r i n g i n f o r m a t i o n h i d d e n i n t h e m e as u r e d o b j e c t , a d a t a r e d u c t i o n a l g o r i t h m o n t h e b a s i s o f f u z z y c l u s t e r i n g a n a l y s i s i s p r o p o s e d . b y i n t r o d u c i n g g e o m e t r i c s i m i l a r i t y m e m b e r s h i p , s u r f a c e v a r i a t i o n c a n b e n a t u r a l l y r e p r e s e n t e d , f o r c i n g s a m p l e s t o g a t h e r i n r e g i o n s w h e r e s u r f a c e v a r i e s d r a s t i c a l l y . a n d i m p e r a t i v e c o n s t r a in t s i m i l a r i t y m e m b e r s h ip i s i n t r o d u c e d t o r e fl e c t e n g i n e e r i n g d e m a n d o f d e s i g n e r s , w h i c h i s i n f a v o r o f r e t a i n i n g e n g i n e e r i n g d e t a i l f e a t u r e s . f e a t u r e l i n e e x tr a c t i o n fr o m a p o i n t c l o u d i s a n o t h e r n e c e s s a r y p r e p r o c e s s i n g s t e p f o r s u r f a c e r e c o n s t r u c t i o n . t o s a t i 吻 t h e d e m a n d f o r s t a b i l i t y a n d a c c u r a c y o f f e a t u r e l in e e x t r a c t i o n , a m u l t i - s c a l e f e a t u r e l i n e e x t r a c t i o n a l g o r i t h m b a s e d o n d i g i t a l i m a g e t h i n n i n g i s p r e s e n t e d . l o c a l e n t r o p y a n d r e p e a t a b i l i t y r a t e a r e in t r o d u c e d t o c l a s s i f y p o i n t s a c c o r d i n g t o t h e l i k e l i h o o d t h a t t h e y b e l o n g t o s o m e f e a t u r e a t d i f f e r e n t s i z e o f l o c a l w i n d o w , w h i c h a c h i e v e s r o b u s t a n d s t a b l e f e a t u r e p o i n t d e t e c t i o n f o r n o i s y s u r f a c e s . b y m a p p i n g t h e e x t r a c t e d f e a t u r e p o i n t c l o u d i n t o 2 d d i g i t a l i m a g e s a n d t h i n n i n g t h e i m a g e s , s m o o t h f e a t u r e l i n e s a r e r e c o v e r e d . s c a n t y d a t a c a n b e d e a l t w i t h a n d t h e t o p - q u a l it y f e a t u r e l i n e s c a n b e r e c o v e r e d s u r f a c e r e c o n s t r u c t i o n i s t h e k e y p r o b l e m o f p o i n t - b a s e d d a t a t r e a t m e n t . t o s a v e t ime o n s u r f a c e r e c o n s t r u c t i o n a n d a v o i d g a p s o f t h e r e c o n s t r u c t e d s u r f a c e w h e n p a r t s o f t h e d a t a g e t l o s t d u r i n g t r a n s m i s s i o n , a n e w s u r f a c e r e c o n s t r u c t i o n a l g o r i t h m b y u s e o f d e c o m p o s i t i o n o f 华 中 科 技 大 学 博 士 学 位 论 文 s u r f a c e e l e m e n t s i s d i s c u s s e d . s i m i l a r t o t h e t h e o r y o f a d v a n c i n g f r o n t me t h o d , t h e c o n s i s t e n t t a n g e n t p la n e e s t i m a t i o n o f e a c h s a m p l e i s p e r f o r m e d b y c o n s t r u c t i n g l o c a l l o o p s a n d a d v a n c i n g t h e c e n t e r l o o p . t h e v o l u m e e n c l o s e d b y t h e g i v e n p o i n t c l o u d i s a p p r o x i m a t e d w i t h t h e s e t o f o v e r l a p p i n g s u r f a c e e l e m e n t s b u i l t a t e a c h s a m p l e p o in t . s u r f a c e e d it i n g i s i n d i s p e n s a b l e i n p o i n t - b a s e d d a t a t r e a t m e n t . t o a c h i e v e a f l e x i b le c a p a b i l i t y f o r s u r f a c e e d it i n g , a s u p e r q u a d r i c - b a s e d g e n e r a l c o n s t r a i n e d d e f o r m a t i o n a l g o r it h m i s d e s i g n e d . b y b u i l d i n g a s u p e r q u a d r i c - b a s e d g e n e r a l c o n s t r a in e d d e f o r m a t i o n m o d e l , s u r f a c e c a n b e d e f o r m e d a c c o r d in g t o u s e r - s p e c i f i e d c u r v i l i n e a r d i s p l a c e m e n t u n d e r c o n s t r a i n t s , w h i c h c a n c o n s i s t o f p o i n t s , l i n e s , s u r f a c e s a n d v o l u m e s . d u r i n g s u r f a c e e d i t in g , n e w s a m p l e s a r e i n s e r t e d t o t h e o r i g i n a l p o i n t c l o u d a n d l o c a t e d i n p r o p e r p o s i t i o n s b y u s i n g w e i g h t e d l o c a l e n t r o p y m e t h o d t o p r e s e r v e t h e o v e r a l l s a m p l i n g d e n s i t y . o n t h e b a s i s o f t h e a b o v e t h e o r e t i c a c h i e v e m e n t , a p o i n t - b a s e d d a t a t r e a t i n g s y s t e m fr o m 3 d u n o r g a n i z e d d a t a p o i n t s i s d e v e l o p e d a n d e m b e d d e d i n 3 d c a 工 ) s y s t e m一 i n t e s o li d . k e y w o r d s : u n o r g a n i z e d d a t a p o i n t s , f u z z y c lu s t e r i n g , l o c a l e n t r o p y , s u r f a c e r e c o n s t r u c t i o n , c o n s t r a i n e d d e f o r ma t i o n t o 独 创 性 声 明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。 尽我所知，除文中己经标明引用的内容外，本论文不包含任何其他个人或集体已 经发表或撰写过的 研究成果。 对本文的研究做出贡献的个人和集体， 均己在文中以明确 方式标明。本人完全意识到本声明的法律结果由本人承担。 学 位 论 文 作 者 签 名 : 戳 训 浓 日 期 : d o 年午 月 d 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、 使用学位论文的规定，即:学校有权保留 并向国 家有关部门 或机构送交论文的复印 件和电 子版， 允许论文被查阅 和借阅。 本人授 权华中科技大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索， 可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口， 在_年解密后适用本授权书。 本论文属于 不 保 密 贰 学 位 论 文 作 者 签 名 : 武 4 6 v 指 导 教 师 签 名 日 期 :4 - 4 4 月 。 年 日 日 期 户 砷 弃 今 月 确 华 中 科 技 大 学 博 士 学 位 论 文 1绪论 1 . 1引言 随着计算机技术的发展和普及，计算机辅助设计与制造技术 ( c a d / c a m)也得到 迅 猛 发 展， 并 推 动了 反 求工 程 技 术 的 产 生 与 发 展。 反 求 工 程( r e v e r s e e n g in e e r in g ) 1 i-4 1 作为数字化与敏捷制造的一项重要技术，是在无设计图纸或图纸不完整以及无c a d模 型的条件下，从己 有零件或产品出发， 利用各种数字化技术重新构造原形c a d模型的 过程。它的出现改变了传统产品设计 ( 即产品的正设计)中从图纸到实物的设计模式， 将现代坐标测量设备作为产品设计的前置输入装置，结合快速成型制造技术( r a p i d p r o t o t y p e ma n u f a c t u r e ) ，形成产品设计制造的闭 环系统， 可有效 提高产品的决 速响应能 力， 丰富几何造型方法和产品设计手段， 并己广泛应用于机械、 航空、 汽车、家电等领 域。图1 . 1 和 1 .2 分别显示了产品的正设计与反向设计 ( 即反求)的流程图。 产品 图 . 1产品的正设计过程流程图 满意 图 纸 斗 c a m 产品 不满意 图1 . 2产品的反向设计过程流程图 产品反求的 体系结构由 离散数据获取、 数据预处理、 c a d模型重建以 及快速制造四 部分组成 ( 见图1 .3 ) 。 其中， 离散数据获取是关键的第一步， 是曲 面重建及快速制造的 基础， 也是进行误差分析、曲 面比较等分析工作的前提。 根据数据获取方式的不同可得 不同的初始点集， 相应的数据预处理和曲 面重建方法也各不相同。 本文所处理的测点没 有明 显的几何分布特性， 称散乱点云， 为方便起见， 简称点云( p o i n t c l o u d ) 。 数据预处 理与模型重建是产品反求的核心内容， 预处理的效果和模型的选择影响着重建曲面的品 质和精度，决定最终产品的c a d模型的优劣。 点云的处理技术仅对数据预处理和模型重建这两部分展开研究 ( 见图 工 .3中的阴影 部分) ， 它以 获取的离散数据为输入，以 物体的曲 面模型为输出，即解决如何根据测量 华 中 科 技 大 学 博 士 学 位 论 文 所得点云构建物体的几何表达的问题。 它又可分为基于网格的点云处理技术和基于点的 占 云处理技术 ( p o i n t - b a s e d t e c h n i q u e s ) 两大类。 高傲数据获取 图 1 .3产品反求的体系结构图 1 .2基于网格的点云处理技术 基于网格的点云处理技术是一种传统的点云处理方式，其突出特征在于以网格作为 中介来表达离散点之间的相互连接关系， 将点云组织成一个整体， 恢复被测曲 面。网格 简 化 【5 -7 1 、 特 征 提 取 8 -10 1 、 曲 面 重建 1 1-2 5 1 等 均 是以 网 格 节 点 或网 格 边 作为问 题 考 虑的 基 本 出发点， 它的优点在于以网格显式表达物体的拓扑结构， 表示方法简单、直观， 能表现 形状任意复杂的物体，目 前己得到广泛的应用。 随着数据获取技术的飞速发展和几何物体日 益增长的复杂性要求，基于网 格的点云 处理技术日 益暴露出以下不足: 1 、对于具有上百万测量数据的点云而言，不仅网格的建立十分复杂和繁琐，保证网格 的拓扑正确也是非常困难的; 2 、网格模型需同时记录点信息和点间连接关系的信息，导致存储量大、处理时间长、 难以 进 行拓扑 修改 2 6 1 ， 当网 格的自 适应 细 化可能改 变拓扑时， 可能需完全 重建网格; 2 华 中 科 技 大 学 博 士 学 位 论 文 3 、网格模型侧重于对离散点的分割，是一种自 底向上的过程; 4 、曲面在绘制之前，需分解为三角面片。为了加强场景的真实感，所建物体模型的复 杂 度不断提高， 导 致三角片的 数量增加很快2 7 1 ， 对大量三角 片的 处理导致了 带宽 瓶 颈和过度的浮点计算量。 近年来发展起来的基于点的点云处理技术无需建立网格，直接以点作为曲面绘制和 造型的基本元素，逐渐受到越来越广泛的关注。 1 . 3基于点的点云处理技术 基于点的点云处理技术以点作为曲面绘制和造型的基本元素，处理那些用一组点采 样表示物体曲面的几何对象。 与基于网格的技术相比， 基于点的处理技术具有下列优点: 1 ,能克服网格方法的高度复杂性和低鲁棒性: z 、无需显式存储拓扑，可实现简单而几乎连续的层次多细节 ( l e v e l - o f - d e t a i l, l o d ) 控制，可方便地改变曲面拓扑; 3 、 物体的点采样可自 顶向下的 生成，能够快速实 现物体曲 面的 粗糙表达2 6 1 . 4 、对存储空间的需求少，能实现对复杂物体和环境的有效绘制: 5 、具有高度的数据局部性，且无需反馈，易于实现并行处理，可形成一条简单而有效 的绘制途径; 6 、 无需三角带参予绘制， 而三角带对于非静态网 格的控制来说 是非常复杂的2 6 1 基于点的点云处理包括基于点的数据预处理和基于点的曲 面重建与编辑等内容，下 面分别介绍相关的研究现状。 1 . 3 . 1数据预处理 数据预处理是曲 面重建的基础，其目 标是用较少的规则化的 数据点集、最高精度地 取代原始点云数据。 数据预处理的一般流程是: 测量数据的缺损修补今数据简化今数据 平滑、排除噪声数据和异常数据令特征提取以及数据分块等。 1 .3 . 1 . 1测量数据的修补 在产品反求中，实物表面的局部破损以 及测量中可能存在的阻塞和可及性问题，都 会产生测量数据的缺损， 造型之前必须对点云进行修补。 可采用局部补测的方法加以解 决， 也可使用推导算法， 从实物模型出发， 从几何和产品的功能角度分析并推测数据缺 损部分与现存部分的关系。 目 前一般采用抛物线切向 延拓的方法 进行数据修补2 8 ， 如果 缺 损区 域 较 大， 则 精 度不易 保 证。 g u p 2 9 提出了 一 种利 用b p 神 经网 格的 强 非线 性逼 近 能力和抑制样本噪声等优点来修补数据的方法， 但易陷入局部极小， 训练过程缓慢， 结 华 中 科 技 大 学 博 士 学 位 论 文 果往往难以 达到理想要求。 孙玉文3 0 利用遗传算法与b p 算法的结合辅助设计神经网 络， 提高了 鲁棒性， 在生成修补数据的精度方面也得到很大提高。 瞿建武3 1 则 提出了 三种测 量数据补充方法， 通过实物填充、 补充设计和自 动补充算法共同克服测量空洞及恢复缺 损部分的曲面形状。 1 . 3 . 1 .2数据简化 为精确恢复被测物体的曲面，测量所得数据量通常很大，难以直接进行曲面重建， 因此，需适当简化，以减少冗余点。 点云简化最常用的是采样法，其基本原理是:按一定规则，从原始点云中抽取部分 数据点，未抽取到的数据将被忽略。典型的方法有以下几种: ( 1 )均匀采样法 该法根据数据点的存储顺序， 每隔m 一 1 个点保留一个点， 其它点都被忽略， 其中m 为采样率。将均匀采样法应用于有序数据， 便成为等间距采样法，而当其应用于无序数 据时， 则成为随机采样法。 该法无需搜索数据点的邻域，因而速度很快， 但其稳定性受 测量方法和测量点存储方式的影响，稳定性不高。 ( 2 )倍率缩减法 该法按给定的点个数进行简化，在每一次遍历中，需遍历所有数据点的 邻域，并去 除点云中 相距最近的两个点中的一个， 直至达到用户指定的数目 。 该法由于遍历次数多， 导 致 算 法的 时间 复 杂 度高 (3 2 ( 3 )弦偏离法 该法有两个控制参数: 极限弦偏离值s 和最大弦长l ， 其采样过程是: 在最大弦长l 内， 所有弦偏离小于s 的数据点都被忽略，即只有达到最大弦长l 的点或弦偏离不小于 s的点才会被采样到。均匀采样和倍率缩减法都是以比较均匀的方式减小点云密度，而 弦偏离法可根据法矢的变化简化数据点，当设置合适的s 和l 时，该法还能采样到扫描 方向的 边界线和轮廓线。 但这种方法只能应用于顺序排列的数据。 对于散乱点集，因相 邻存储的三个点往往会超出s 或l，几乎所有点都被采样到，因而通常无法达到数据简 化 的 目 的 3 3 ( 4 )栅格法 该法是基于几何信息的三维算法，与数据的组织形式无关。 该法以 初始栅格数和法 矢背离容限为控制参数， 利用八叉树将点云划分为栅格， 求取每个栅格内所有点的法矢 的平均值，并保留 每个栅格中法矢最接近法矢平均值的点。对于密集且较平坦的点云， 该法效果较好，但简化后的点集也是接近均布的。 以上基于采样法的简化算法多适用于有序点云，对无序点云的简化往往难以保证效 华 中 科 技 大 学 博 士 学 位 论 文 果， 且简化后多为均布， 不符合不均匀布点理论的要求，即不易 根据离散点的曲 率变化 自 适应地在尖锐处多分布点，同时在平坦处少布点。 近年来出 现的 基于点采样曲 面的简 化算法则能较好地解决上述问题。 基于点采样曲面的简化算法以采样点的空间近似替代网格模型中的边信息，在简化 点 云 的同 时 保 证简 化曲 面的 质 量 3 4 1 . p a u ly m p s 1 提出 通过 傅立叶 转 换 和 频 谱技 术 进行点 云简化的框架。 该法将模型曲 面分裂成一组定义于平面域的面片， 采用频谱分解技术分 别对这些面片重采样， 通过直接将信号处理技术应用于点采样几何，获得一种快速、 通 用的点云简化方法，对频谱系数的直接分析和操纵能实现高效的滤波、重采样、 频谱分 析和局部误差控制;l l n s e n l 3 6 1 利用信息含量作为简化的依据， 通过计算和比 较采样点 所包含的关于物体形状特征的信息量， 不断删除那些包含信息量最少的采样点， 最终以 原 始 点 集的 子 集 作 为 简 化点 集; p a u ly m 3 4 3 则 通 过 估 计 局 部曲 面 变 分 和 利 用 二 次 误 差 矩 阵来消除简化导致的近似误差， 可在曲面的高曲率处排布更多采样点， 他分析和定量比 较了四种简化算法:递增式分簇法、 层次式分簇法、 迭代简化法和基于粒子仿真的简化 算法， 提出了 基于移动最小二乘曲 面 ( m o v e i n g l e as t s q u a r e s , m l s )的简化曲 面误差测 量方 法， 可实 现基于点的多 分辨 率造型3 7 1 。 基 于点 采样曲 面的 简 化 算法在 保留 点 云的 尖 锐特征方面可获得较为良 好的效果。 1 .3 . 1 .3数据平滑和滤波 由 于受到不可避免的测量误差和人为因素 ( 如测量中的异常振动、光学式测量仪的 电 器误差等) 的影响， 采样点云并非完全落在原物体上， 易出现“ 疵点” ( e x t r a n e o u s d a t a 1 5 1 ) ， 并往往带有许多无用信息， 这些噪声数据将直接影响重建曲 面的品质。 数据平滑可 降低或消除测量过程中人为或随机因素引起的误差， 常用的方法有标准高斯法、 平均滤 波法 或中 值滤波算法 i 3 8 , 3 9 1 ， 其中 高 斯滤 波法能 较好地保持原数 据的 形貌， 中 值 滤波法 则在消除数据的毛刺方面效果较好。尽管滤波的方法很多， 但其使用将破坏数据的 “ 尖 锐性” ，使边界点失去 “ 锐化”效果，可能给后续的特征点鉴别带来严重问题，因此， 应将其应用于点云处理的哪个具体阶段仍处于一个两难境界 1 l 1 .3 . 1 .4特征提取与数据分块 特征提取就是从测量点云中 辨识曲面的关键几何形状。对于形状复杂的物体，其曲 面通常是由特征线分割而成的不同曲 面片组合而成的，因此，由 特征线构成的线特征往 往是这类曲面最重要的特征。 特征线能够作为网格构造、 数据分割以及各向异性光顺的 输入， 对可视化领域中三维物体的语义增强也可起到重要的作用。 对基于点的处理技术 而言， 特征的 提取主要集中于特征线的 提取。 p a u l y m指出， “ 特征线近似沿着最大形变 的脊线走， 通过估计曲 面变分可捕捉到特征线” 4 0 。 尽管如此 由 于被测曲 面未知， 特 华 中 科 技 大 学 博 士 学 位 论 文 征线的提取仍属于 “ 黑色”技巧，难度较大。 目 前 对基 于点的 特征 线 提取 算 法的 研 究尚 不 多 见， c h o i s n , g u m h o ld s , p a u ly m 等人对此进行了一定的 研究。 c h o i s n g l 的p o w e r c r u s t 算法通过将几何 特征附近的曲 面 延 展并 计 算其交线， 处理 尖锐边和角 特征， 但提 取效果 易 受噪声 影响。 g u m h o l d s 4 1 1 用 椭球拟合采样点周围的邻域点， 获取曲 面曲率和最大张角的近似值，并作为一种标准为 采样点指定罚权值， 描述该点不属于某个特征的程度，同时以罚权重作为邻域图的边权 值， 通过从邻域图中提取子图，使边权值最小，生成一组特征模式，最后用样条拟合法 恢复 特征线。 该法可提取不同 模式的特征， 如折痕( c r e a s e ) 、 环 l o o p ) 、 角 特征( c o r n e r ) 等，能克服噪声影响，然而在精度及光顺度的灵活性和控制方面效果不理想。类似地， p a u l o m 4 1 3 采 用协 方 差 分 析，以 最小 生 成 树( m in im u m s p a n n i n g t r e e , m s t ) 为 特征节 点， 将g u m h o l d s的方法扩展到基于多尺度的特征分类， 进一步支持噪声曲 面的特征提 取， 利 用主动蛇 模型 ( a c t iv e c o n t o u r m o d e l ) 4 3 性成光 滑的 特征 线， 可获 得 对光 滑度的 更多控制。该法自 动化程度较高，不过， 蛇模型对初始轮廓线的位置十分敏感， 算法稳 定性不易保证。以上基于点的特征线提取算法均是针对自由曲面物体的研究， 未涉及对 机械零件的特征线提取，使其应用受到限制。 特征线的提取与数据分块实际上是相互联系的。利用提取的特征线可方便地将点集 分割成不同部分， 而若先将数据分块， 则分割而成的数据块之间的交线即可作为特征线。 1 .3 . 2曲 面重建与编辑 曲面重建是点云处理的关键内容，也是最重要和最困难的问 题之一。重建曲面的品 质和精度直接影响最终产品的c a d模型的优劣。曲面重建的目的在于寻找某种数学描 述形式， 精确、简洁地描述一个给定物理曲面的形状，并以此为依据对曲面本身进行分 析、计算、 修改和绘制4 4 1 基于点的重建 ( p o i n t - b as e d m o d e l i n g ) 用于表示那些基于点来表示、 处理和编辑曲 面的技术， 该项技术的实施可建立一条从数据获取 三维扫描设备) 到可视化 ( 基于点 的绘制)的完整的几何处理途径。基于点的曲面表达允许直接将点云当作曲面来处理: 人们可以对其进行光线跟踪、光顺或其它形式的曲面修改。目前a k a l a i a h , l i n s e n l , a le x a m , m z w ic k e r , p a u ly m等 人 在 这 方 面 展开了 一 定的 研究。 a k a l a i a h 4 1 ,4 6 1 的 差分点 ( d i ff e r e n t i a l p o i n t , d p ) 将基于点的 造型方 法的 简 洁与基于 网格的造型方法的效率相结合， 用一组差分点表示曲面。 其中每个差分点都包含了曲率 信息， 即能够捕捉到该点邻域内的局部差分几何信息。 该法的优点在于: 大大减少了用 于表达曲面所需的点体素的数目; 在缺乏连通性信息的条件下， 也可获得硬件加速效果。 l i n s e n l 3 6 1 提出 一种基于点的多分辨 率造型框架。内 容涵盖曲 面光顺、点云简化和 华 中 科 技 大 学 博 士 学 位 论 文 多分辨率分解，可实现多分辨率曲面形状的修改和布尔操作。 a l e x a m4 1 提出 基于点的曲 面定义， 采用移动最小二乘方法将曲 面的构造转化为用 局部多项式对点集进行拟合， 拟合结果是一个光滑的二维流形面。 为了绘制点表达的曲 面，该法利用移动最小二乘法建立曲面误差矩阵， 通过迭代地施加点删除操作， 根据图 像分辨率来评价和动态调整点云的密度，获取对曲面表达保真度的良好控制:s f l e i s h m a n 4 8 1 以 移动最小二乘法为 基础表达点采样曲 面的多分辨率， 不过， 他们的工作主 要集中于空间有效的累进编码 ( 点集编码) ，并非多分辨率编辑。 p o i n t s h o p 3 d 4 9 1 是 一 个 基 于 点 的 编 辑 系 统， 该 系 统以 不 规 则 三 维 采 样 点 作 为 三 维图 像 元素， 将二维图形编辑器推广到三维，除了能够实现传统图像编辑器中的效果之外， 还 可对三维物体模型进行贴纹理、 雕塑等操作， 将基于三维几何的 雕塑与基于二维图形的 照片编辑有机结合起来。但m z w i c k e : 指出， “ 该系统并非基于点的造型系统，曲面几 何的 编 辑 仅限 于曲 面 法 矢的 位 移 和曲 面结 构的 微小 变 化” . p a u ly m 3 则 在 基于点 的 多 分 辨率造型框架下设计了一种直观编辑器，可实现不同比例的造型操作，该法类似 f f d 方法，且变形控制更加灵活，但仅能进行整体变形。 1 . 3 . 3基于点的绘制 绘制的目的是将所建立的物体模型显示在屏幕上，为用户提供对物体的直观印象， 事实上， 基于点的绘制方法的出现就是为了以最快的速度将形状复杂的物体模型显示出 来。 基于点的 绘制 ( p o i n t - b a s e d r e n d e r i n g ) 抛弃了 三角形表示方 法， 将点 表示以 连续曲 面的形式显示在屏幕上， 是一种与视点无关的、以物体为中心而非以图像为中心的表示 方法，相当于一个二维曲面数据场，维数的降低大大加快了绘制速度。 基 于点 的 绘 制技 术 这一 概 念最 初由m l e v o y 和t w h itt e d s o 1提出 ， 他们 认为， 用 三 角面片显示复杂物体将失去扫描线绘制的效率， 而点绘制除具有简单的特性， 还足以对 任何物体造型。 他们用抛雪球法 s p l a tt i n g ) 绘制a, 并在绘制前将物体转换成点表示， 以 避 免为 每 个图 形 体素 写 一 个 专 用 绘 制 算 法。 类 似思 想也 在r e y e s 5 1 体 系中 实 现。 1 9 9 2 年， r s z e l i s k i 借鉴弹性曲面模型的变形能思想，基于交互粒子系统的弹性曲面，用有 向 粒 子( o r i e n t e d p a r tic le ) 进 行 曲 面 造 型 和 交 互 编 辑 5 2 1 ， 但 他 们 是 用 椭 圆 绘 制 体 素 并 构 造三角网 格， 而非以 基于点的绘制技术观察有向 粒子。 类似地， a p w i t k i n 5 3 1采用有向 粒子实现了隐式曲 面的 采样和交互形状控制。 1 9 9 8 年， j p g r o s s m a n 15 4 重新提出点绘制， 其目的是设计一种对输出敏感的绘制算法来实现复杂物体的实时和高质量绘制， 并支持 动 态 光 照。 2 0 0 0 年， 随 着s u r f e l 系 统 5 5 和q s p l a t 系 统 5 6 的 出 现 ， 基 于 点 的 绘 制 开 始 真 正繁荣起来。 h p f i s t e r 5 5 扩展了g r o s s m a n 的 1作，以“ 面元 ( s u r f a c e e l e m e n t , s u r f e l ) ”为基本元 华 中 科 技 大 学 博 士 学 位 论 文 素， 采 用l d c 树( l a y e r e d d e p t h c u b e ) 5 7 )存 储 采 样点， 可实 现l o d控 制， 但 最 终的 系 统十分 类 似基于图 像的 绘制( i m a g e - b a s e d r e n d e r i n g , i b r ) o s r u s i n k i e w i c z 5 6 设计了另一 种树状层次包围 球数据结构， 进行层次l o d和可见性剔除， 用s p l a tt i n g 方法重建曲 面， 保留了i b r的影响， 该法最大的特点在于采用高度压缩的数据结构， 使该算法能快速显 示大数据量的网格模型，并保证绘制图像的质量。 2 0 0 1 年， 人 们 提出e w a ( e l l ip ti c a l w e ig h t e d a v e r a g e ) 曲 面 抛雪 球法 5 8 1 ， 该 法 将m l e v o 尹 0 1 的 思 想 与p s h e c k b e r t 的 重 采 样 5 9 相 结 合 ， 得 到 高 质 量 的s p l a tt i n g 技 术 ， 实 现 了各向异性的纹理滤波、边的反走样和与次序无关的透明度。随后，人们针对 era, q s p la t 和s u r f e l 方 法 相 继 作 出 不 少 改 进。 如s r u s in k i e w ic z 6 0 提出 扩 展 的q s p l a t ， 可 支 持 中速网络条件下的传输几何;d l u e b k e 6 p 用知觉标准控制的多细节层次选择;m b o t s c h 6 2 用层次的变形和定量化的消隐实现点采样物体的空间有效层次表示;l c o c o n u 6 3 采 用 硬 件 加 速e w a s p l a tt in g ; r a s a n e n 6 4 用 随 机 采 样， 改 进e w a s p la tt i n g 方 法; m z w i c k e r 6 5 则提出了e w a曲 面和体抛雪球法的 统一框架。 b c h e n 的 混合多 边形 一 点绘 制系统 6 6 , 6 7 干脆 遗弃了 单独以 点为绘制体素的 思 想， 其 算法的基本出发点是: 点在投影到小屏幕空间区域时效率更高， 否则多边形的效率更高。 t k d e y 6 s 】基于v o r o n i。 曲 面 重建 技术 提出 混 合多 边 形 一 点 绘 制， 他用 局 部 几 何 特 征尺 寸 来选择合适的体素， 而非以点在屏幕的 投影作为选择点 或多 边形的标准。 m w a n d r6 9 1 提 出了混合的点一 多边形绘制技术进行关键帧动画。 1 . 3 .4基于点的加工轨迹生成 传统的点云处理技术以获得被测体的 c a d模型为目 标，以 便于加工或快速原型制 造， 对基于点的处理技术来说，在缺少c a d模型的条件下同样可实现零件的加工。 基 于点 的 加工 轨迹生 成 ( p o i n t - b as e d t o o l - p a t h g e n e r a t i o n ) 就是 这样一类无 需建 立c a d模 型， 直 接 从点 云 生 成 加 工 轨 迹的 方 法。 l in 7 0 1提出 用点 云 构造z - m a p 模 型， 并 利 用基 于 象素的偏移量方法计算粗加工区域， 同时采用高度修正法避免精加工刀具