（机械制造及其自动化专业论文）基于曲率特征信息的散乱点云数据预处理技术研究.pdf

西南交通大学硕士学位论文第1 页 于茼斐 随着非接触式测量设备精度的不断提高，非接触测量越来越多地应用于航空、航 天、造船、生物、装备制造等工程领域。由于非接触式测量所获得散乱点云数据易受 环境的影响，使得点云中存在误差点，而且由于设备测量精度高，也造成点云中存在 大量的冗余数据。误差点的存在会严重影响后续曲面重构的质量，而大量冗余数据会 使得整个重构工作耗费计算资源大、效率低、精度差，因此，散乱点云数据平滑和精 简是保证曲面重构质量不可或缺的数据预处理手段。 本文以高精度扫描所获得的散乱点云数据为具体研究对象，深入研究了一套能较 好保留曲面几何特征( 法矢、曲率) 的数据平滑和精简技术，编制相应的算法，用不 同数量规模、不同重构要求的散乱点集为实验数据，验证该算法的合理、有效性，并 将算法集成开发为一套功能完整的散乱点云数据平滑和精简预处理系统。 论文主要的研究内容如下： 1 基于空间分块技术，将通用的k 一邻域整体扩展搜索算法改进为自动寻找最近扩 展壁的单向扩展，确保快速完成k 个邻近点的搜索，提高搜索效率。 2 研究散乱点云重要的几何特征：法矢和曲率的获取方法，包括：法矢估算和修正 方法、曲率估算方法，为后续数据平滑和精简方法研究做好基础准备工作。 3 为避免数据平滑使得点云中关键的边界点信息丢失，将边界点识别和提取算法引 入进散乱点云数据平滑算法中，并以曲率估算得到的平均曲率为阈值，将散乱点集分 区，对不同曲率区域的点应用相适应的平滑算法，使得整套平滑算法不仅能很好地保 留边界信息和曲率变化的特征信息，而且数据点排列较为规则、有序，为曲面重构打 下良好的基础。 4 为了使数据精简算法在具有较高精简效率的同时，很好地保留原始点云曲率变化 信息，论文提出根据点集中不同曲率点的比例来自适应地设置平均曲率修正因子，动 态对数据分区进行合理地调整，同时论文将基于空间分割和曲率的数据精简方法相融 合，对不同曲率的数据分区应用不同的精简算法，并用实例验证了该精简算法对表面 特征复杂和表面曲率变化较为简单的散乱点集均有很好的适应性。 5 将所研究的k 邻域快速搜索、法矢估算及修正、曲率估算、边界点保留、数据 平滑和数据精简的算法整合在一起，运用基于c a a 的c a t i a 的二次开发技术，开发 出完整的散乱点云数据平滑和精简预处理系统。 关键词：k i 邻域；法矢估算；曲率估算；数据平滑；数据精简 a b s t r a c t w i t ht h ec o n t i n u o u s i m p r o v e m e n to fa c c u r a c yo ft h en o n c o n t a c tm e a s u r e m e n t e q m p m e n t ，n o n c o n t a c tm e a s u r e m e n ti s i n c r e a s i n g l y u s e di n a v i a t i o n ，a e r o s p a c e ， s h i p b u i l d i n g ，b i o t e c h n o l o g y , e q u i p m e n tm a n u f a c t u r i n ga n do t h e re n g i n e e r i n gf i e l d s o w i n g t ot h ea c c u r a c yo fs c a t t e r e d p o i n tc l o u dd a t aa c q u i r e db yn o n - c o n t a c tm e a s u r e m e n ti s v u l n e r a b l et ot h ei m p a c to ft h ee n v i r o n m e n t ，al o to fe r r o rp o i n t se x i s ti nt h ep o i n tc l o u d ， m e a n w h i l e ，b e c a u s eo ft h eh i g ha c c u r a c yo fe q u i p m e n t ，c a u s e st h e r ea r eal o to fr e d u n d a n t d a t ai nt h ep o i n tc l o u d t h ee x i s t e n c eo ft h ee r r o rp o i n t sw i l ls e r i o u s l ya f f e c tt h eq u a l i t yo f t h es u b s e q u e n ts u r f a c er e c o n s t r u c t i o n ，w h i l eal a r g en u m b e ro fr e d u n d a n td a t am a k e st h e w h o l er e c o n s t r u c t i o nw o r kr e q u i r e sa g r e a td e a lo fc o m p u t i n gr e s o u r c e s ，l o we f f i c i e n c y , p o o r a c c u r a c y , t h e r e f o r e ，t h es m o o t h i n ga n dr e d u c t i o no fs c a t t e r e dp o i n tc l o u dd a t aa r e i n d i s p e n s a b l em e a n so fd a t ap r e p r o c e s s i n gt oe n s u r et h eq u a l i t yo fs u r f a c er e c o n s t r u c t i o n b a s e do nt h es c a t t e r e dp o i n tc l o u dd a t ao b t a i n e d b yh i g h p r e c i s i o ns c a n n i n g ，t h e t e c h n o l o g yo fd a t as m o o t h i n ga n dr e d u c t i o nw h i c hc a nr e t a i nt h es u r f a c eg e o m e t r i c a l c h a r a c t e r i s t i c s ( t h en o r m a lv e c t o r , c u r v a t u r e ) d a t ae f f i c i e n t l yi ss t u d i e di nd e t a i l ，m o r e o v e r , t h ea l g o r i t h m so fd a t as m o o t h i n ga n dr e d u c t i o na r ep r o g r a m m e d ，a n ds c a t t e r e dp o i n tc l o u d w i t hd i f f e r e n ts c a l ea n d r e q u i r e m e n t sa r ep r o c e s s e di nt h i sp r o g r a mt ov a l i d a t et h er a t i o n a l i t y a n de f f e c t i v e n e s so ft h e s ea l g o r i t h m s f i n a l l y , as o f t w a r ew i t hc o m p l e t et h ea l g o r i t h m so f d a t as m o o t h i n ga n dr e d u c t i o ni sd e v e l o p e d t h em a j o rr e s e a r c hw o r ko f t h i st h e s i si sa sf o l l o w s ： 1 b a s e do ds p a c ep a r t i t i o nt e c h n o l o g y , t h en o r m a lkn e i g h b o r h o o ds e a r c ha l g o r i t h m w i t hw h o l ee x p a n s i o ni s i m p r o v e db yt h es e a r c h i n gt e c h n o l o g yo fa u t o m a t i co n es i d e e x p a n s i o n u s i n gt h et e c h n o l o g y , t h ekn e i g h b o r i n gp o i n t sc a nb es e a r c h e dm o r eq u i c k l y 2 t h ec o m p u t i n gm e t h o d so fg e o m e t r i cf e a t u r e so fs c a t t e r e dp o i n t c l o u d ，s u c ha s n o r m a lv e c t o ra n dc u r v a t u r e ，a r e r e s e a r c h e d ，i n c l u d i n g ：t h ee s t i m a t i o na n dc o r r e c t i o n a l g o r i t h mo fn o r m a lv e c t o r , t h ee s t i m a t i o na l g o r i t h mo fc u r v a t u r e t h e s ea l g o r i t h m sw i l lb e u s e di nt h es u b s e q u e n td a t as m o o t h i n ga n ds t r e a m l i n e dp r o c e s s 3 i no r d e rt oa v o i dt h ei m p o r t a n tb o u n d a r yp o i n t sl o s t ，t h ee x t r a c t i o na l g o r i t h mo f b o u n d a r yp o i n t sf r o mt h es c a t t e r e dp o i n tc l o u di si n t r o d u c e di n t ot h es m o o t h i n ga l g o r i t h m t h e n ，u s i n gt h ea v e r a g ec u r v a t u r ea sat h r e s h o l dv a l u et op a r t i t i o nt h es c a t t e r e dp o i n t si n t o s m o o t ha r e a sa n ds a l t a t i o na r e a s ，a n da d a p t i v es m o o t h i n ga l g o r i t h m sa r eu s e dt ot h e s ea r e a s t h ef u l ls e to fs m o o t h i n ga l g o r i t h mc a nn o to n l yr e t a i nt h ec h a r a c t e r i s t i ci n f o r m a t i o no ft h e b o u n d a r yg e o m e t r ya n di n f o r m a t i o no fc u r v a t u r ec h a n g e ，b u ta l s oa r r a n g e ss c a t t e r e dp o i n t s m o r e r e g u l a r , o r d e r l y t h e s e w o r k sl a yag o o df o u n d a t i o nf o rt h ef u t u r es u r f a c e r e c o n s t r u c t i o n 4 t h et e c h n o l o g i e so fc a l c u l a t i n g c o r r e c t i n gf a c t o ro ft h ea v e r a g ec u r v a t u r ea n d a d j u s t i n gd a t ap a r t i t i o nd y n a m i c a l l ya r es t u d i e di no r d e rt oi m p r o v ed a t ar e d u c t i o ne f f i c i e n c v a n dr e t a i nt h eo r i g i n a lg e o m e t r i cc h a r a c t e r i s t i ci n f o r m a t i o np r o p e r l y a tt h es a m et i m e t h e s p a c e b a s e ds e g m e n t a t i o nc u r v a t u r e b a s e dd a t ar e d u c t i o nm e t h o d sa r ei n t e g r a t e da n du s e dt o s m o o t ha r e a sa n ds a l t a t i o na r e a sr e s p e c t i v e l y b yu s i n gt h ed a t ar e d u c t i o na l g o r i t h mt o a l l k i n d so fs c a t t e r e dp o i n tc l o u d ，t h ee f f e c t i v e n e s so fa l g o r i t h mi sv a l i d a t e d 5 t h ea l ls t u d yr e s u l t s ，s u c ha st h ea l g o r i t h m so fk n e i g h b o r h o o ds e a r c h e s t i m a t i o n a n dc o r r e c t i o no ft h en o r m a lv e c t o r , e s t i m a t i o no fc u r v a t u r e ，e x t r a c t i o no ft h e b o u n d a r y p o i n t s ，d a t as m o o t h i n ga n dd a t ar e d u c t i o na r ea l li n t e g r a t e d w i t ht h eu s eo ft h es e c o n d a r y d e v e l o p m e n tt o o lc a a o fc a t i as o f t w a r e ，ap r o g r a mo fd a t ap r e p r o c e s s i n gi sd e v e l o p e d 。 k e yw o r d s ：k n e i g h b o r h o o d ；n o r m a lv e c t o rc o r r e c t i o n ；c u r v a t u r e e s t i m a t i o n ；d a t a s m o o t h i n g ；d a t ar e d u c t i o n 西南交通大学硕士学位论文第1 页 1 1 引言 第一章绪论 逆向工程中，数据采集是第一个环节，一般通过非接触式和接触式两种测量方法 采集实物几何信息。非接触式测量方法具有数据获取速度快、灵活性高、获取的信息 范围大等特点。随着其测量精度的日益提高，非接触式测量的应用已从快速获取复杂 零部件的表面精确形状 1 3 1 ，逐步延伸到捕捉动态数据 4 6 和获取零部件表面微观信息 7 8 领域，成为产品创新设计、零部件质量检测、动态信号检测的重要手段之一。 非接触式测量通常是利用光学原理开发的激光、c c d 、结构光等光学测量设备来 采集信息。利用光学原理来获取产品外观数据时存在一些缺陷：如非接触式测量获取 产品表面数据时受外界光的干涉和产品表面反射特性的影响，所以噪声较高；能快速、 且精准地完成产品表面中大面积的平缓表面上数据点采集，但对陡峭边线、深凹孔、 d , ；f l 以及不连续形状的处理较困难 9 ，1 0 ，加之测量过程中人为和随机因素的影响，使得 扫描获得的点云数据中存在噪声点或误差点是不可避免的，据统计，噪声数据约占点 数据总量的o 1 5 e 1 1 】，因而采集获取数据后的第一步处理是对原始数据点集进行过滤， 数据点集过滤一般包括删除误差点和数据平滑两部分。 另外，三维非接触式测量获取的产品外形信息量非常庞大，数据密集，单幅点云 数据量可以上万，而一般汽车覆盖件的数据量则多达上百万乃至上千万个数据点。随 着三维测量设备的精度越来越高，其获取的数据量也必然随之增大，存在大量的数据 冗余，如果对扫描的数据不加以精简，直接用于曲面模型重构，则会造成巨大的资源 和时间的消耗，建模效率很低，也很难保证重构后获得的曲面和实体模型的精度。因 此，在尽量保留产品点云数据表面特征信息的前提下，对原始点云数据进行精简【1 2 1 ， 称为点云精简，其目的是能用数量较少的、有序的和规则的点集代替原始数据。 在保证原始点云关键几何特征信息不丢失的条件下，对原始点云数据进行平滑滤 波和数据精简是确保得到高质量曲面重构模型的关键技术，也是逆向工程点云数据预 处理技术中的重要内容。 1 2 国内外发展现状 1 2 1k 邻域快速搜索技术的研究现状 非接触式测量扫描获得的数据点集是散乱、无序的，缺乏明显的拓扑关系1 3 ，通 西南交通大学硕士学位论文第2 页 过计算采样点的k 一邻域来确定散乱点云的几何拓扑关系是点云数据处理过程中最常见 的预处理方法，它被广泛应用于估算采样点的法向矢量大小【l 圳，噪声点的滤波处理5 | ， 曲面光顺处理 16 等过程中，是进行图形图像数据预处理的关键技术之一，也是相关研 究领域目前国内外学者的研究热点 1 7 - 1 9 。 随着激光扫描设备扫描精度提高，所获得的数据点集密度和数量也不断增加，建 立散乱测点之间邻接关系的数据结构，计算k 一邻域所消耗的计算资源和占用的计算时 间也必然会成倍增加。k 邻域搜索首先需要进行k 个最近点的计算，即在二维或三维 散乱数据集s = 矽，i = 1 ，2 ，船 中找到k 个与该点欧氏距离最近的点。计算某点的 k 个最近邻域的一般方法是求出候选点与其余聆一1 个点的欧氏距离，并按从d , n 大的顺 序排列，前面的k 个点即为候选点的k 一邻域1 2 。 通过非接触式三维扫描获得的原始点云数据量非常庞大，即以非常大，因而计算 数据点的k 个最近邻域必然会耗时巨大。最国内外许多学者从提高k 一邻域搜索速度的 角度出发，进行了大量研究，提出一些快速搜索算法，主要分为两类：( 1 ) 利用点集 v o r o n o i 图来进行k _ 邻域的搜索 2 卜2 4 1 ，但构造点集的v o r o n o i 图系统资源消耗高 2 4 1 ，若 为查询某样点的拓扑近邻而构造整个点云的v o r o n o i 图，需付出很大的计算代价 2 5 1 。( 2 ) 利用空间分块策略进行k 个最近点搜索，如p i e g l 2 6 , 2 7 研究了针对平面点集的k 邻域搜 索问题；周儒荣等研究了由散乱点云构建一个大的包围盒，将其按指定的准则分解为 许多子立方体，点云数据分布、并归于相应的子立方体中，进行候选点k 邻域搜索时， 当所在的子立方体不能够满足条件时，则将候选点所在的子立方体向其周围六壁方向 的2 7 个子立方体中搜索k 个最近点，这种搜索方法会大大增加搜索的数据量，所使用 的时间也会增多，本文对这一种环六壁方向的整体子空间扩展方法进行了算法编制， 实际验证其计算效率。熊邦书等 2 0 应用空间分块方法，在点云数据的体积、k 取值和 点云数据总点数的基础上，提出估算子立方体边长的k 一邻域搜索方法。卫炜 2 8 】等基于 空间分块的方法，将子立方体搜索方法改为空间球搜索方法。就目前研究现状来看， 国内外学者还在不断研究各种k 邻域快速搜索算法，虽然从文献上看，各种方法都会 做一定的比较，但何种搜索方式效率更高、搜索的准确度更高、是否对各种形状的数 据点集都适合，尚没有形成定论。 1 2 2 法向矢量计算方法的研究现状 点云数据预处理过程中，搜索k 一邻域的目的是为了实现法向矢量( 简称法矢) 估 算和拟合抛物面以求取曲率。顶点的法矢表示了重要的微分几何信息，点云所隐含的 最重要几何特征一曲率，也是通过法矢估算获得的，因此，在曲面分割、曲面拟合、 模型光顺等方面，把法矢作为一个已知的基础前提，而且顶点法矢计算准确与否严重 影响后续的计算结果 2 9 1 。法矢估算从计算方法来看，常用的有计算最d - - 乘平面、计 西南交通大学硕士学位论文第3 页 算移动最小二乘平面、构建局部三角网格 3 0 - 3 2 等。 计算移动最小二乘平面法计算开销较大，使用较少；构建局部三角形网格方法是 通过三维空间中由一系列相互连接的平面三角面片来组成曲面的离散逼近表达形式 p 引。平面三角网格来估算点的法矢有代表性的五种方法是：( 1 ) g o u r a u d 提出的三角 网格模型顶点法矢估算方法，其基本思想是认为顶点1 ，的1 - r i n g 三角形各法矢对于顶点 v f 的法矢n f 的贡献相等 3 4 j ；( 2 ) t h u r m e r 和w u t h r i c h 等在g o u r a u d 研究基础上提出用 各三角形在点1 ，f 的夹角加权对其进行修正 3 5 ；( 3 ) t a u b i n 在g o u r a u d 研究基础上按三 角形的面积对g o u r a u d 方法进行修正，面积越大的三角形，其对船；的贡献越大 3 6 ；( 4 ) 神会存等在方法2 和3 的基础上，提出面积与顶角加权的顶点法矢计算方法 3 3 ；( 5 ) m a x 认为三角形法矢对n ，的贡献受三角形连接边长和在其点v ，处的夹角的影响，提出 了修正计算公式 3 丌。就目前研究现状而言，局部网格三角形法矢计算方法在夹角、边 长、三角形面积对法矢计算的贡献，以及针对不同形状三角形权重如何取值等方面还 有许多值得研究的地方。 最小二乘平面法是首先在候选点附近选取一定数据的邻近的点，根据所选取的候 选点及其附近点的拓扑形状采用拟合微小平面或者二次曲面的方法来计算候选点的法 矢，即利用散乱数据点的k 邻域通过最小二乘平面拟合，对局部曲面中心点的法矢进 行估算 38 1 。一般算法设计上采取的具体做法是：基于k 一邻域中的点集，采用最小二乘 法拟合一个微切平面逼近离散点邻域中的点集，把该微切平面的单位法矢作为候选点 的法矢，该方法可适用于散乱点云数据顶点法矢求取，还能推广到任意给出的无规则 的空间散乱点进行法矢估算 3 叫1 1 。但该算法计算得到的散乱数据点法矢指向待建曲面 的内外方向不统一，曲面重建前需对数据点集的法矢方向进行调整，使得调整后的法 矢方向统一指向待重建曲面的同一侧。单独采用平面对点集进行拟合可能会造成所拟 合出的平面误差较大，因此也有学者采用“样条曲面”或“二次曲面”对空间离散点 进行曲面法矢估算 4 2 “3 1 ，可以得到方向一致的法矢值，但这类方法还只能用于规则的 数字曲面和排列规则、有序的离散点，要求采集的数据点是矩形阵列，不适用于无规 则的散乱点云数据。 1 2 3 数据过滤技术的研究现状 非接触式测量方式采集工件表面的数据时，数据精度易受两方面因素的影响：物体 表面的反射和环境的振动，如待测金属制品表面光洁度高就有可能引起测量噪声；此 外，由于某些测量方法受测量技术原理的限制，使测量数据在深孔、陡峭直壁、小孔 和尖锐棱边处采集的数据很不可靠，存在较大的噪声。因此，采集数据中存在噪声点 是难以避免的，只有预处理中通过合理的滤波方法降低其对曲面拟合的不良影响。 点云过滤目前尚未形成一种通用的方法，主要包括滤波处理和数据平滑两部分。 西南交通大学硕士学位论文第4 页 滤波的作用是去除异常点，也即是说，测量数据的预处理首先是从数据点集中找出可 能存在的异常点或误差点。若采用逐行扫描方式，则确定异常点的基本方法是：判断 同一截面的扫描点云数据是否存在一个点与其相邻的点偏距较大，这样的点可以认为 是异常点 4 4 , 4 5 。但对于散乱点云数据，滤波则复杂得多。目前，点云滤波方法主要有 以下几种：( 1 ) 弦高滤波法 46 | ，根据点云中相邻三点所确定三角形的高度与弦长比值 进行滤波，该方法只适用于扫描线型点云；( 2 ) 均值滤波法【4 7 j ，以点云局部型面中参 考数据的型心作为原始型面数据点进行滤波，该方法简单，对高斯噪声有较好的滤波 效果，但在点云边界及曲率较大区域，型面特征损失严重；( 3 ) 中值滤波m7 | ，以局部 拟合型面参考数据中型心的最近邻点代替原始型面数据点，该方法的滤波效果优于均 值和弦高滤波法，但点云型面特征的损失也无法绝对避免。还有一些国内外学者提出 基于非均匀热传导理论对散乱数据点云进行滤波【4 8 1 、加权中值滤波和加b 样条小波滤 波 4 9 等方法，但即使是成熟的商业反求软件，如用g e o m a g i c 软件来进行滤波和平滑， 也无法避免型面特征损失，多次迭代出现t l n 等现象，论文将在第三章对其进行更详 尽的分析。 点云数据平滑的目的是通过一定的手段改变点的位置，降低误差点对曲面拟合质 量的影响。常用的点云数据平滑方法可以分为空间域方法和频率域方法两类。空间域 方法直接针对点云数据自身的空间位置关系进行处理，频率域方法则将点云数据视为 灰度图像，以修改图像的傅氏变换来实现数据平滑 5 0 1 。空间域方法主要有拉普拉斯 ( l a p l a c i a n ) 算法、邻域平均法，自适应滤波法、多次测量平均法以及中值滤波法等。 频率域方法有高斯低通滤波、理想低通滤波等。目前最为常用的平滑处理方法主要是 针对多边形网格的，包括两类：全局能量法 5 1 , 5 2 和拉普拉斯( l a p l a c i a n ) 光顺法【5 3 ，5 4 j 。 全局能量法用所有顶点的坐标值作为参数对原始多边形网格定义一个全局能量函数， 由该函数求解来调整网格顶点。这种算法缺陷是：计算耗费时间，且整体的约束方程， 缺乏对网格局部细节的把握，局部形状比较难控制。拉普拉斯光顺法在标准权值法的 基础上，通过数据点集中每个顶点定义一个拉普拉斯算子来确定修正方向，然后沿该 方向以一定的速度移动顶点来调整网格。该方法能够有效把点云数据网格调整为规则 形状，网格密度与形状都得到改善，但无法避免模型被压缩 55 1 。其他国内外学者提出 一些算法来实现数据的平滑，如t a u b i n e 5 6 通过信号处理的理论分析提出了对拉普拉斯 算子交替使用两个相反因子进行迭代，有效平滑了抑制了噪声，并且且在一定程度上 抑制了调整后点云数据模型的变形。k u w a h a r a 滤波算法【57 j 是运用四个部分重叠的窗 口去划分深度图像中的一个对称的小区域，每一个窗含一个中心像素，中心像素的灰 度值被这四个窗口中灰度值变化最小的窗口平均值所替代，选择性地进行平滑。其他 一些学者提出平均曲率( m e a nc u r v a t u r e ) 法t 5 8 击们，建议在顶点方向按该点的近似平均曲 率值的大小来调整网格顶点，这种方法光顺效果较理想，但却无法控制网格形状，易 西南交通大学硕士学位论文第5 页 产生大量不规则三角片。 1 2 4 数据精简的国内外发展现状 随着近几年曲面信息采集技术的提高，采样点的精度达到亚毫米级，通过高精度 的三维扫描仪获得的曲面点云包含大量的点，使用这些点进行曲面重建以及后续建模 处理，会消耗大量计算时间和资源。因此，在保证能为模型重建提供必需信息的前提 下，精简测量数据点云是十分必要的。 国内外许多学者对三维散乱数据点集的精简进行了研究。点云数据的精简方法最 初是基于两点间距离或曲率等简单原则，后来许多学者将三角形的精简算法推广、应 用到点云数据精简算法中。目前点云数据精简的方法主要有两种：一类是基于空间区 域分割的精简方法，如三角形网格法，八叉树非均匀网格法、包围盒法、聚类分析法 等；另一类是基于曲率变化趋势的数据精简方法，如逐行搜索法、最小距离法等。 h a m a n n 【6 l j 提出了一种适用于s t l 文件的自动生成的方法，改方法根据三角面处 的曲率值来决定此三角面的精简与否，然后重新拟合成三角面片。h a m a n n 和c h e n 6 2 还提出了分别针对不同维数几何体信息的数据精简方法，如构建不同平面曲线、压缩 2 d 图像和可视化实体表面的精简数据点方法。该方法精简的程度不仅受被选取的点数 的控制，还受误差水平的控制。 p a u l y 等提出聚类分析方法【6 3 1 ，通过把点云数据分裂成多个相互无交集的子集，在 每个子集中保留一个代表性的点，删除其它点。目前，聚类分析方法已经被应用于计 算机图形领域用来减少三维物体的复杂性。例如r o s s i g n a c 和b o r r e l 6 4 j 使用聚类法来实 现复杂多边形模型的多分辨率逼近。标准聚类分析方法是把模型的包围盒细分成多个 网格单元，然后用一般性的描述网格单元来替代所有的采样点云，然而这种法有局限， 通过使用一个确定大小的网格单元并不能适应采样分布中存在不均匀采样的情况，而 且，如果网格单元太大的话，体积聚类分析也很容易把物体表面本不相连的部分划分 到一个网格单元内，从而严重改变物体的形状。 w e i r e 6 5 等提出采用体包围盒来约束点云，保留每个包围盒中离其中心最近的点， 其它点删除。由于最小包围的大小是用户定的，无法保证点云数据的表面特征不丢失。 2 0 0 1 年s u n 等 6 6 通过应用局部曲面插值来自动确定包围盒的大小来改进包围盒法，但 不足的是该方法只适应于表面特征简单的点云数据且效率比较低。 研究表明，若数据单纯采用基于空间区域分割的数据精简方法，如基于空间分割 的包围盒法、均匀方格法、三角形网格精简法，不能适应具有复杂特征和多样曲率的 高密度散乱点云的数据精简【67 | 。 另一类是基于曲率变化趋势的数据精简方法，如逐行搜索法 2 1 、邻域球搜索法 2 6 | 、 最小距离法 6 8 和角度偏差法 6 9 等。目前已有的曲率精简算法普遍存在邻域搜索范围小、 西南交通大学硕士学位论文第6 页 速度慢等缺陷。 除此之外，一些学者对据数据精简质量进行了研究，如张丽艳7 0 1 等人研究了用 r i e m a n n 图建立散乱点间的邻域关系的方法，在此基础上进行r i e m a n n 图的最优遍历 并计算散乱点处的最小二乘法拟合的平面，从而通过近似计算删除某一点引起的误差， 并提出了基于精简后点云数据中点的个数、点云数据中点的密度阈值及删除某一点引 起的法向误差的阂值准则。该方法在数据精简的结果和精简速度方面都取得较好的效 果，但缺点是过于依赖邻近点的个数k 的取值。k 的选取必须保证在点置的k 一邻域拟 合的曲面是单凸或单凹。 1 3 本课题研究的目的与意义 1 3 1 选题依据 由研究现状分析可知，点云数据的平滑和精简是保证曲面拟合和重构的重要预处 理技术。散乱点云本身是由大量无序的数据点集构成，虽然无法直观地建立点云与所 重构模型的设计意图、制造特征之间的直接联系，但点集的拓扑关系隐含了所构曲面 几何信息，因此采取不当的平滑和精简方法对后续产品的研发影响巨大。目前所研究 的数据平滑和精简算法侧重于研究算法本身的运算效率、收敛性和精确度等数学问题， 而对平滑或精简时如何很好地保留点集隐含的几何信息，不同数量规模、不同分布、 不同曲率变化的点集应采取何种预处理技术缺乏系统的分析，如描述复杂造型的艺术 品与描述汽车覆盖件所需数据点集规模、分布、变化形式都不一致，所采取的预处理 手段必然也应不同。目前的数据平滑、精简方法或强调计算效率，则难以保证重要的 特征信息不被损坏会丢失；或侧重保证点云的关键信息，则方法效率低、速度慢。成 熟的商品化反求软件也同样存在这个问题，如g e o m a g i cs t u d i o ，对散乱点云数据平滑 和精简时，迭代次数过多时就会出现数据表面特征( 如棱角、边界) 丢失的现象，而 究竟迭代多少次为合适，完全凭借人的经验来确定，很难控制。因此有必要深入研究 一种能适应各种外形，具有较快运算效率，而且能较好地保留点云关键几何特征的数 据预处理方法。 1 3 2 研究的目的与意义 本文将基于三维扫描所获得的海量散乱点云数据，深入分析不同外形产品所需的 平滑和精简方法，在参考相关文献的基础上，形成一套完整算法，集k _ 邻域快速搜索、 法矢估算及修正、数据平滑和数据精简于一体，并编制相应的数据预处理系统对算法 的有效性进行验证。 本研究在估算得到点云数据法矢和曲率等关键几何特征信息的基础上，形成一套 西南交通大学硕士学位论文第7 页 针对不同物体外形自适应地运用不同的数据平滑和精简算法，由此使得平滑和精简后 的点云数据在保证计算效率的同时，关键几何特征信息不丢失。具体来说，数据平滑 算法是将拉普拉斯和k u w a h a r a 平滑算法相结合，并加入了边界特征点提取及保留的算 法，从而保证去除异常点的同时，几何型面的关键特征信息不被平滑过程损坏；数据 精简算法则是通过动态调整曲率阈值，针对不同类型曲率自适应地运用基于空间分割 和曲率精简算法，从而避免了基于空间分割算法精简比例过大而造成的表面特征丢失 的现象和基于曲率算法计算效率低的缺陷，能够很好的适应于各种形状散乱点云数据， 实现精简算法的通用性。 最后，本文将各个算法有机衔接、融合，构成一套完整算法，并运用c a t i a 软件 的二次开发工具c a ac + + ，构建出一套散乱点云数据预处理系统，系统与c a t i ac a d 环境无缝集成，能有效地利用商业软件的显示、曲面重构等功能，直观地实现算法运 算结果的可视化。 1 4 本论文主要研究内容 本文的主要工作包括以下四个部分，论文的结构体系如图1 1 所示。 1 利用空间分块的方法对散乱点云数据进行k 邻域的搜索，获得所有散乱点云数 据点的k 一邻域。应用最小二乘法将k 邻域的点拟合成平面，求取该平面的法矢作为该 点的法矢，应用法矢传播调整法对法矢的方向进行调整，使所有点的法矢方向指向同 一侧。 2 研究散乱点云数据边界特征点提取方法，在应用k u w a h a r a 滤波算子和拉普拉斯 算子对散乱点云平滑的同时，对边界特征点予以保留。保证在平滑的过程中不会出现 特征点丢失的现象。 3 求取散乱点云数据的曲率，分析点云曲率组成，动态设定曲率阈值，将散乱点云 数据分为突变区域和平坦区域，不同的区域数据分别自适应地应用曲率精简法和空间 分割法。 4 基于c a t i a 二次开发构建一套散乱点云数据平滑和精简的预处理系统。 西南交通大学硕士学位论文第8 页 第一章绪论 上 第二章散乱点云法矢估算及修正 + 第三章 保留边界特征的散乱点石数据 平滑算法研究 0 第四章 i 散乱点云数据精简算法研究 上 第五章 程序的设计与实现 上 第六章结论及展望 + 一获取点云的几何特征信息 保留点云的几何特征信息，对不同 曲率点云运用不同的平滑算法 点云的几何特征信息，对不同外形 一点云自适应运用不同的精简算法 将前三章算法有机融合，开发完成 + 一系统 图1 1 论文体系结构 西南交通大学硕士学位论文第9 页 2 1 引言 第二章散乱点云数据法矢估算及修正 散乱点云中的数据点集本身是紊乱、无明显拓扑关系的，而拟合曲面最重要的两 个微分几何属性是法矢和曲率。顶点的法矢反映了曲面某点处重要的局部微分几何信 息，散乱点云曲率是通过法矢来求得的，而且顶点法矢的方向决定了数据点平均曲率 的方向，法矢方向的不统一会直接影响益率估算的准确性，进而影响以曲率为评判标 准的数据平滑和精简质量。因此，本章将系统阐述散乱点云数据的局部特征分析方法， 主要包括三个方面的研究内容： ( 1 ) k 一邻域快速搜索算法研究； ( 2 ) 法矢估算算法研究； ( 3 ) 法矢修正算法研究。 2 2k 邻域快速搜索算法 海量散乱点云数据的法矢计算中常采用k 邻域来确定散乱点云的几何拓扑关系。 一般地，散乱点云数据中，候选点尸的k 邻域是指点集中与p 欧氏距离最短的k 个数 据点，称为点p 的k 邻域，记为n ( p ) 。随着激光扫描设备扫描精度提高，激光扫描仪 采集的散乱点云数据非常密集，获得的散乱点云数据量非常庞大，计算散乱点云数据 点的k 邻域会耗费大量的时间。本文将针对此问题，在空间分块方法的基础上，通过 改进子空间的扩展方式，提高了搜索的速度，节约搜索时间，并采用遍历所有点来保 证每个数据点都能找到k 个最近数据点。 2 2 1 点云子空间的划分 k 一邻域搜索的基本思路是：根据读入的散乱点云数据，估算出子立方体的边长， 把空间分割成若干个大小相等的子立方体，并记录子立方体内包含的数据点的信息， 然后利用子立方体内点的信息对每个数据点进行k 一邻域的搜索。子立方体分割的流程 如图2 1 所示。 西南交通大学硕士学位论文第1 0 页 读入散乱点云数据 一r 估算子空间的边长 上 计算最小子空间立方体 0 划分子空间 上 计算候选点所在的子空间 c u b e i j k 上 把散乱点云数据序号存入相应 的子立方体c u b e i j k 图2 - 1 子立方体分割流程图 2 2 1 1 子空间分割的算法 子空间分割的算法主要包括三个步骤： s t e p l 首先计算包含所有数据的最小包络长方体。具体思路为：读入散乱点云数 据，查找散乱点云数据在坐标轴方向上x 、只z 的最大坐标值和最小坐标值，进而构 造一个与坐标轴平行的长方体，长方体以数据点集的最大和最小的x 、y 、z 坐标值作 为对角顶点，该长方体的边长为： j 三( x ) = 。一誓由。 l ( y ) = y 。a x 一少r n i 。 l 三( z ) 2 z 一一z 幽( 2 1 ) s t e p2 估算子立方体的边长三。具体思路为：设数据集的最小包络长方体分成拒 个子立方体空间( 简称子空间) ，则 吃出= f ( x o 。；一吐) 三 f - ( 。一y 。讧) l l f ( z 。k ) l ( 2 - 2 、 其中ll 表示向上取整。 假设每个子空间中平均数据点的个数是k 的函数，k 为k 邻域中临近点数的取值，则 有 西南交通大学硕士学位论文第1 1 页 n n 。6 。= a k ( 2 3 ) 其中玎为散乱点云总的点数、口是一个标量。为便于计算，把式( 2 2 ) 代入式( 2 3 ) ，整 理后可得到边长三的计算公式 l = p # 5 ( x m a x x m i n ) ( y 。a x 一i 。) ( z 。一z m i n ) ( 2 4 ) 其中，用于调节子立方体边长的大小，的最优值为0 8 1 2 2 0 1 。立方体边长三 确定后，最小包络长方体在x 、】，、z x ，y ，z 方向上的分辨率m ，f ，即三个轴向上 子空间的个数也相应确定： m = ( x m 。一x m i 。) 三 = ( y 。；一y 。i n ) 三 ，= ( z 。一) l ( 2 5 ) 至此将该最小包络长方体划分成mx nx 1 个小立方体子空间，如图2 2 所示： 图2 2 散乱点云数据空间划分示意图 s t e p3 完成子立方体划分，把点云数据的序号归入到相应的立方体子空间中，便 于后面工作中对散乱数据点的查找。 2 2 1 2 子空间分割算法的数组结构 子空间分割是为后续的k - 邻域搜索做准备工作。 由于k _ 邻域搜索过程中主要的操作是数据的检索，即检索出任一数据点坐标值、 序号及其所在的子立方体，以及任一子立方体空间所包含的数据点数。因此，本文点 云数据的存储采用了数组结构的方式，立方体空间是一个三维数组结构，各个数组结 构具体如下。 ( 1 ) 散乱点云数据数组。该数组中保存点云数据中每个点的x ，y ，z 坐标值，子立 方体序号，邻域点序号，以及数据点序号，所有的点按读入的顺序依次排列。 ( 2 )散乱数据点的子空间数组。该数组中保存各子空间中含有的散乱数据点的 个数，子空间的边界坐标值。 西南交通大学硕士学位论文第1 2 页 ( 3 ) 子空间内数据点的排序数组。该数组中临时存放子空间中除候选点外各点 的序号和这些点到