（机械制造及其自动化专业论文）基于支持向量机的点云曲面建模的研究.pdf

西南科技大学硕士研究生学位论文第1 页 摘要 点云的曲面重建是反求工程中的重要研究内容，重建模型的速度和精度 是实现快速制造的重要保证。因此本文主要研究利用支持向量机处理点云的 曲面重建中的一些重要问题。 对于点云数据精简问题，本文实现了将支持向量回归问题视为最小包闭 球问题( m e b ) ，实现了海量点云数据中支持向量的多级提取，用更高一级密度 的支持向量逼近原模型，以消除上级逼近后的残留误差，使重建得到的模型 可以满足不同精度的要求。 应用s 一支持向量回归机拟合点云数据，回归出用于逼近原模型的显式和 隐式函数模型，引入s 不敏感损失函数不仅使算法具有鲁棒性，而且使回归 函数的解具有稀疏性。实验证明了本算法在拟合函数曲面上的有效性和快速 性。 应用m a r c h i n gc u b e s 方法绘制回归得到的隐式函数模型，根据不同的显 示精度需要，实现了隐式函数模型不同分辨率的曲面重建。对比实验证明， 本算法具有在保证一定精度的情况下具有速度快的优点。 针对模型存储空间过大问题，提出了一种基于支持向量的存储方式，仅 需存储支持向量的坐标与隐式函数模型系数。与传统的网格存储方式相比， 这种方式不但可以满足多分辨率显示的需要，而且可以有效的降低模型存储 空间。 用v c + + 和0 p e n g l 开发了用于演示和验证本文算法的实验平台，能直观 的对曲面重建过程进行观察和处理，可以输出建模结果。 关键词：曲面重建点云 支持向量回归机反求工程 西南科技大学硕士研究生学位论文第1 i 页 a b s t r a c t t h eq u e s t i o na b o u ts u r f a c er e c o n s t r u c t i o no fp o i n tc l o u dd a t a s i sa ni m p o r t a n tr e s e a r c h i n gc o n t e n ti nr e v e r s ee n g i n e e r i n g t h e p r e c i s i o na n ds p e e do fm o d e l i n gp l a yas i g n i f i c a n tg u a r a n t e ei n m a n u f a c t u r i n gh i g hq u a l i t yp a r t sq u i c k l y s o t h i sp a p e rm a i n l y c o n c e r e do nt h er e s e a r c ho fs o m ec r u c i a lq u e s t i o n si nt h ep r o c e s so f s u r f a c er e c o n s t r u c ti o n t os 0 1 v et h es i m p l i f i c a t i o no fp o i n tc o l u dd a t a s ，t h es v rq u e s t i o n i m p l e m e n ta st h em e ba l g o r i t h m ， m u l t i c a ls c a l e sn u m b e r so fs u p p o r t v e c t o ra r ed is t i1 1 e d f r o m1 a r g ep o i n tc l o u dd a t a sf o rc o r r e s p o n d i n g p r e c i s i o nt ob er e q u i r e d ：t h em o r es u p p o r tv e c t o r sc a na p p r o m i n a t et h e r u d i m e n t a la f t e rt h el e s so n e s a p p r o m i n a t i o n a n i n s e n s i t i v el o s sf u n c t i o ns u p p o r tv e c t o rr e g r e s s i o n ( s v r ) m a c h i n eh a sb e e n u s e dt or e g r e s s i o nt h ee m e r g e i m p li c i tf u n c t i o n a l m o d e lo fp o i n tc l o u dd a t a s t oi n t r o d u c i n gt h e i n s e n s i t i v e1 0 s s f u n c t i o n ， t h er e g r e s s i o nf u n c t i o n sa r er o b u s tt on o i s e s ，a n d t h e s o l u t i o n sa r ew i t hs p a r s i t y t h r o u g ht h ee x p e r i m e n t ， t h es u r f a c eo f p o i n tc o u l ds e t sa r er e c o n s t r u c t e dd i r e c t l yw i t ht h eb e n e f i t so fh i g h e f f i c i e n c y b a s e do nt h ei m p l i c i t i n gf u n c t i o nr e s u l t i n gf r o ms u p p o r tv e c t o r r e g r e s s i o n( s v r ) ，m a r c h i n gc u b e s( m c )a l g o r i t h mh a s b e e n u s e dt o c o n s t r u c ts u r f a c em o d e lw i t hd i f f e r e n tr e s o l u t i o n s c o m p a r i s o nt o o t h e ra l g o r i t h m s ，t h eo n ep r o p s e di nt h i sp a p e rd i dw e l li ns p e e d f o rs l o v i n gt h eq u e s t i o na b o u tl a g es a v i n gs p a c eo ft h em o d e l ， w ep r o p o s e dam e t h o dw h i c hc a nr e d u c et h es a v i n gs p a c ee f f i c i e n t l yb y s a v i n gt h es u p p o r tv e r c t o r sa n dc o r r e s p o n d i n gc o e f f i c i e n t si nt h e f u n c t i o n c o m p a r i n gw i t h t h ec l a s s i c a lm e t h o d so fs a v e i n gt r i a n 9 1 e m e s h s ， t h en e wo n ea r ee x c e l1 e n ti nr e d u c es a v i n gs p a c ea n dr e s u l ti n d i f f e r e n tr e s 0 1 u t i o n sv i s i o n as o f t w a r ef o rt e s t i n gt h ea l g o r i t h m si nt h i sp a p e ri sd e v e l o p e d ， i tc a no b s e r v ea n dd i s p o s et h ep r o c e s so fs u r f a c er e c o n s t r u c t i o n 西南科技大学硕士研究生学位论文第1 i i 页 v i s u a l l y ， a n do u t p u tt h er e s u l t s k e y - o r d s ： s u r f a c er e c o n s t r u c t i o n ； p o i n tc l o u d ； s v r ； r e v e r s ee n g in e e r 独创性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得西南科技 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 刽话 黾凝：口8 6 。l 弓 关于论文使用和授权的说明 本人完全了解西南科技大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文的复印件，允许该论文被查阅和借阅；学校可以公布 该论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 名：糟龇曝屯? 1 ) 西南科技大学硕士研究生学位论文第l 页 1 绪论 1 1反求工程概述 随着计算机技术的迅猛发展，计算机辅助设计( c o m p u t e ra i d e dd e s i g n ， c a d ) 与计算机辅助制造( c o m p u t e ra i d e dm a n u f a c t u r e ，c a m ) 也得到广泛应 用，在这样的形势下，反求工程( r e v e r s ee n g i n e e r i n g ，r e ) 应运而生，反求 工程也常被称为逆向工程或逆向反求工程。反求工程1 ，是数字化与敏捷制造 的一项重要技术，它的本质是：在无设计图、无c a d 模型或设计图纸不完整 的条件下，从已有零件或产品出发，利用数字化技术重新构造原型。反求工 程的出现改变了传统产品设计( 正向设计) 中从图纸到实物的设计模式，将现 代坐标测量设备作为设计的前端输入装置，与快速成型、快速制造技术相结 合，从而得到产品设计制造的一个闭环系统。该系统可有效缩短产品周期， 从很大程度上丰富了几何造型方法，率先在机械制造领域有了成功应用的案 例，并逐步延伸至家电、国防、交通运输以及航空航天等领域。 目前，关于反求工程的研究主要集中在几何反求上，即如何从实物或样 件上准确高效地采集复杂三维表面数据，进而快速地获取其c a d 模型。由于 测量设备采集的三维表面数据通常比较密集，因而形象地称作点云( p o i n t c l o u d ) ，是三维点坐标( x ，y ，z ) 的集合。 反求工程的基本流程是：对实物样件进行坐标数据采集，得到表面几何 数据；然后对这些数据进行补缺、简化、平滑等预处理；由于测量模型通常 由多个面组成，因而需要对测量数据进行分块，再进行曲面拟合，在曲面模 型的基础上可进一步建立产品的c a d 模型。 反求工程涉及的内容非常广泛，本文仅研究其中的曲面模型重建问题。 1 2基于点云的曲面重建的意义和研究现状 通过激光三维扫描仪等信号采集设备，可以方便地获取物体表面信息， 这些信息通过大量的点来表达，往往形成包含几百万个数据的大型数据包， 通常称为点云。通过对点云的处理，可以得到物体的表面表达，与数控加工。 中心结合，能直接将处理结果用于加工生产，从而达到避免设计、修改图纸 的繁琐过程的目的。此外，根据点云数据能直接实现三维建模，因此能事先 西南科技大学硕士研究生学位论文第2 页 检测出机械部件的运行情况和机构运行时是否会发生干涉，在虚拟组装和虚 拟加工中具有重要意义。 数据预处理与模型重建是产品反求的核心内容，预处理的效果和模型的 选择将直接影响曲面重建的质量，并决定最终的c a d 模型的优劣。点云的处 理以点云数据作为输入，以曲面模型为输出，即解决根据点云构建物体的几 何表达的问题。它又可分为基于网格的点云处理技术和基于点的点云处理技 术两大类。 。 1 2 1基于网格的点云处理技术 基于网格的点云处理技术是一种传统的点云处理方式，由于其表示方法 简单、直观，能表现形状任意复杂的物体等优点，目前已得到广泛的应用。 它以网格作为中介来表达离散点之间的相互连接关系，将点云组织成一个整 体，恢复被测曲面。网格简化“、特征提取 儿，、曲面重建等均是以网格 节点或网格边作为问题考虑的基本出发点。 随着数据获取技术的飞速发展和几何物体日益增长的复杂性要求，基于 网格的点云处理技术日益暴露出以下不足： ( 1 )对于具有上百万测量数据的点云而言，不仅网格的建立十分复杂和 繁琐，保证网格的拓扑正确也是非常困难的； ( 2 )网格模型需同时记录点信息和点间连接关系的信息，导致存储量 大、处理时间长、难以进行拓扑修改，当网格的自适应细化可能改变拓扑时， 可能需完全重建网格； ( 3 )曲面在绘制之前，需分解为三角面片。为了加强场景的真实感，所 建物体模型的复杂度不断提高，导致三角片的数量增加很快，对大量三角片 的处理导致了带宽瓶颈和过度的浮点计算量n ”。 近年来发展起来的基于点的点云处理技术无需建立网格，直接以点作为 曲面绘制和造型的基本元素，逐渐受到越来越广泛的关注。 1 2 2基于点的点云处理技术 基于点的点云处理技术以点作为曲面绘制和造型的基本元素，处理那些 用一组点采样表示物体曲面的几何对象。与基于网格的技术相比，基于点的 处理技术具有下列优点： 西南科技大学硕士研究生学位论文第3 页 ( 1 )能克服网格方法的高度复杂性和低鲁棒性； ( 2 )无需显式存储拓扑，可实现简单而几乎连续的层次多细节控制，可 方便的改变曲面拓扑： ( 3 )对存储空间的需求少，能实现对复杂物体和环境的有效绘制： ( 4 )具有高度的数据局部性，且无需反馈，易于实现并行处理，可形成 一条简单而有效的绘制途径”。 下面介绍基于点的曲面重建的研究现状。 1 2 3基于点的曲面重建的研究现状 曲面重建是点云处理的关键内容，也是最重要和最困难的问题之一。重 建曲面的品质和精度直接影响最终产品的c a d 模型的优劣。曲面重建的目的 在于寻找某种数学描述形式，精确、简洁地描述一个给定物理曲面的形状， 并以此为依据对曲面本身进行分析、计算、修改和绘制n ”。 基于点的重建用于表示那些基于点来表示、处理和编辑曲面的技术，该 项技术的实施可建立一条从数据获取( 三维扫描设备) 到可视化( 基于点的 绘制) 的完整的几何处理途径。基于点的曲面表达允许直接将点云当作曲面 来处理。 目前已有较多研究人员在这方面做了大量的研究工作： 彭林法提出的针对残缺点云建模算法，该方法生成的曲面c a d 模型可 满足曲面连续性和光顺性的要求，但在处理曲率较大的问题时存在不足。 k a l a i a h 幢町心的差分点将基于点的造型方法的简洁与基于网格的造型方 法的效率相结合，用一组差分点表示曲面。其中每个差分点都包含了曲率信 息，即能够捕捉到该点邻域内的局部差分几何信息，但仅在曲率较小的地方 取得了较好的效果。 l i n s e n 亿2 ，提出一种基于点的多分辨率造型框架。内容涵盖曲面光顺、点 云简化和多分辨率分解，可实现多分辨率曲面形状的修改和布尔操作，但此 方法效率较低且处于进一步实现阶段。： ， a 1 e x 扩叫提出基于点的曲面定义，采用移动最小二乘方法将曲面的构造转 化为用局部多项式对点集进行拟合，拟合结果是一个光滑的二维流形面。为 了绘制点表达的曲面，该法利用移动最小二乘法建立曲面误差矩阵，通过迭 代的施加点删除操作，根据图像分辨率来评价和动态调整点云的密度，但对 海量点云数据的处理效率较低。 西南科技大学硕士研究生学位论文第4 页 f l e i s h m a n 他，以移动最小二乘法为基础表达点采样曲面的多分辨率，不 过，其工作主要集中于空间有效的累进编码，并非多分辨率编辑。 这方面的研究工作较多，限于篇幅，这里仅列举了其中的一部分。总的 来说，这些方法对操作人员经验的依赖度较高，因此在建模的效率、造型方 法的简洁与所建模型的连续性方面未能实现较好的折衷。 1 3支持向量机算法的提出和概述 模式识别、密度估计以及回归分析等问题，其共同的特点都是从部分数 据( 样本) 中学习知识、获取信息，即根据对己知数据的分析尽可能总结出对 整个数据集都适用的普遍规律。但是，在模式识别问题中，如何针对已有的 有限样本找到最佳的分类面? 在回归分析中，如何有效地控制回归函数的容 量，来实现最优的数据拟合? 面对这些问题，传统的理论和方法无法给出令 人满意的答案。近年来，在这些问题的推动下，随着对机器学习研究的不断 深入，统计学习理论( s t a t i s t i c sl e a r n i n gt h e o r y ，s l t ) 及建立在该理论基 础之上的支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 得到了飞速发展和广泛 应用。 统计学习理论的v c 维理论和结构风险最小化原则的提出都为支持向量 机算法打下了理论基石。 1 9 9 2 年，b o s e r ，g u y o n 和v a p n i k 等人在at r a i n i n ga 1 9 0 r i t h mf o r o p t i m a lm a r g i nc l a s s i f i e r s 一书中，提出了最优边界分类器算法，这也 是支持向量机算法的最初模型。1 9 9 3 年，c o r t e s 和v a p n i k 在t h es o f t m a r g i nc 1 a s s i f i e r 一书中，进一步探讨了非线性情况下的最优边界分类问 题心副。接着，v a p n i k 在1 9 9 5 年发表的t h en a t u r eo fs t a t i s t i c a ll e a r n i n g t h e o r y 一书中，完整地提出了基于统计学习理论的支持向量机学习算法。 1 9 9 7 年，v a p n i k ，g o k o w i c h 和s m 0 1 a 发表的s u p p o r tv e c t o rm e t h o d f o r f u n c t i o n a p p r o x i m a t i o n ，r e g r e s s i o n e s t i m a t i o n ， a n d s i g n a l p r o c e s s i n g 一文中，详细介绍了基于支持向量机方法的回归估计方法 ( s u p p o r tv e c t o rr e g r e s s i o n ，s v r ) 和信号处理方法m 】。 支持向量机成功地解决了高维问题和局部极值问题。支持向量机使用大 间隔因子来控制学习机器的训练过程，使其只选择具有最大分类间隔的分类 超平面，又叫最优超平面( 在不可分情况下，又引入松弛因子来控制经验风 险) ，从而使其在满足分类要求的情况下，又具有最高的推广能力。寻找最优 西南科技大学硕士研究生学位论文第5 页 超平面的过程最终转化为二次型优化问题( q u a d r a t i cp r o g r a m m i n g ，q p ) ，从 理论上说，得到的是全局最优解。 在处理非线性分类问题上，与传统的学习机器不同的是，支持向量机是 将输入空间映射到高维的特征空间，仍然使用大间隔因子在高维特征空间中 寻找最大间隔超平面。事实上，高维特征空间中的超平面对应着输入空间中 的非线性分类面。实际中，支持向量机的优化过程并没有真正在高维特征空 间中进行，而是通过一些具有特殊性质的核函数陋”圳，将高维特征空间中的内 积运算转化为原始空间中核函数的运算，从而巧妙地避免了在高维特征空间 中处理问题的困难。 作为统计学习理论中v c 维理论和结构风险最小化原则的具体实现方式， 支持向量机集优化、核、最佳推广能力等特点于一身。支持向量机方法的几 个主要优点有： ( 1 )它是专门针对有限样本情况的，其目标是得到现有信息下的最优解 而不仅仅是样本数趋于无穷大时的最优值； ( 2 )算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将 是全局最优解，解决了在神经网络方法中无法避免的局部极值问题； ( 3 )算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r e s p a c e ) ，在高维特征空间中构造线性判别函数来实现原始空间中的非线性判 别函数，特殊性质的核函数能保证机器有较好的推广能力，同时也巧妙地解 决了高维问题，其算法的复杂度与样本维数无太大相关； ( 4 )由于其优化目标是结构风险最小化，同时考虑了经验风险和置信范 围的最小化，因而支持向量机具有非常好的推广能力。 1 4课题来源目的及意义 本文研究课题来源于国家自然科学基金项目：复杂几何结构的虚拟组装 与辐射输运数值计算系统的耦合研究( 项目编号：1 0 5 7 6 0 2 7 ) 的一部分。 点云的曲面建模是反求工程的重要研究内容，造型的精度和速度是实现 快速制造高质量零件的重要保证。因此研究基于扫描点云的自由曲面造型技 术具有重要的理论意义和实用价值。 目前，很多学者在点云建模方面做了大量的研究工作，已有的研究主要 是基于启发式方法的，即根据先验知识，特别是根据工程应用的要求设计某 种工程技巧对点云数据进行处理，对操作人员的经验依赖度较高”。这种启 西南科技大学硕士研究生学位论文第6 页 发式方法虽然取得了一些进展，目前能达到或完成工程应用的要求，但由于 缺乏坚实的数学基础，从理论的长远发展来看是有局限性的。 通过对支持向量机优点的分析，我们考虑把基于统计学习理论的支持向 量回归机方法引入到该领域，以弥补这方面的不足。因此本课题不但是对国 家自然科学的支撑，而且对未来的反求工程软件的发展有现实的意义，也是 对基于点的曲面表达方法的积极探索。 1 5 论文的组织结构 本文主要研究利用支持向量机处理点云的曲面重建中的一些重要问题。 对海量点云中支持向量的提取，利用支持向量机对点云数据模型的函数曲面 回归，应用m a r c h i n gc u b e s 算法的曲面绘制，以及重建模型的存储方式等方 面进行了一些有益的探索。 全文共分五章，具体安排如下： 第一章介绍了论文涉及的理论和课题的国内外研究现状，以及本文选题 的目的和意义； 第二章研究了支持向量机的基本原理，而且说明了核函数在处理线性不 可分问题时的重要性，介绍了常用的核函数。对支持向量回归机的基本原理 的推导，说明了其对线性回归问题的有效性，是后续各章的数学基础。 第三章首先在分析和研究了现有点云精简算法的基础上，利用最小包闭 球( m e b ) 思想，将支持向量回归问题视为最小包闭球问题，实现了从海量点云 数据中，根据精度要求分级提取相应数量的支持向量，从而实现了海量点云 数据的简化过程。 第四章利用支持向量回归机在处理非线性回归问题的优越性，实现了应 用s 不敏感损失函数的支持向量回归机算法拟合点云数据。文中分别建立了 对低密度、小样本点云数据的显式函数和隐式函数模型。此模型是下一章中 曲面重建算法的基础。 第五章首先分析了曲面重建的方法和要求，然后实现了由显式函数模型 拟合出b 样条网格点，并由3 次b 样条算法得到曲面。应用m a r c h i n gc u b e s 方法实现了隐式函数模型的不同分辨率的曲面绘制。对于重建得到的模型存 储空间过大的问题，提出了一种基于支持向量的模型存储方式，可以有效的 降低模型存储占用的空间。最后对验证本文算法的实验平台做了简介。 在文章的最后对本文进行了总结，并对下一步的研究工作做出展望。 西南科技大学硕士研究生学位论文第7 页 2 支持向量机的理论基础 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 是统计学习理论中最实用 的部分。由于其自身特点的原因，有广阔的发展前景，目前已经成为机器学 习领域中新的研究热点，并逐步的应用于各个领域。本章简要地介绍支持向 量机分类和回归估计饽，一“算法。 2 1支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ) 简称s v m ，其核心内容是1 9 9 2 年到1 9 9 5 年v a p n i k 提出的结构风险最小化原则”瑚一，它能够提高学习 机的泛化能力，既可以由有限的训练集样本得到小的误差，又能保证对独立 的测试集保持小的误差。而且，由于支持向量机算法是一个凸优化问题，因 此局部最优解一定是全局最优解。s v m 的主要思想可以概括为两点： ( 1 )它是针对线性可分情况进行分析，对于线性不可分的情况，通过使 用非线性映射算法，将低维输入空间线性不可分的样本转化为高维特征空间 使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进 行线性分析成为可能； ( 2 )它基于结构风险最小化理论之上在特征空间中建构最优分割超平 面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概 率满足一定上界。 支持向量机方法是从线性可分情况下的最优分类超平面发展而来的。所 谓最优分类超平面，是指最靠近分类超平面的两类样本点到分类超平面的距 离和最大。这个距离值通常称作分类间隔。 求解最优分类超平面是一个典型的数学规划问题，描述如下： 设给定样本集为：( 薯，只) = 1 ，x r d ，y 十l ，一1 ，如这力个样本是线性 可分的，则必然存在某个超平面： w x + 6 = 0 ( 2 1 ) 将两类样本完全分开。不失一般性，设样本点到超平面的最近距离为， 即i i l i n l w x + 6 l = ，则超平面方程满足下面的约束条件： 西南科技大学硕士研究生学位论文第8 页 y f ( w 暑+ 6 ) 1 ，= 1 ，2 ，拧 注意到任何一个点五到超平面的距离为： 蚺钟 ( 2 2 ) ( 2 3 ) 这里| 1 i | 表示欧氏空间的2 一范数。设超平面( 2 一1 ) 对应的分类间隔为，则： 扣l 驰1 d ) + 船。j d ( t ) = 鹧，帮+ 鹛，销 = 赫职，1 w 掣6 i + ；骋，h + 6 f 阻4 ) 一三 因此求解最优分类超平面等价于求解如下规划问题： 曲剀w l l 2 占j 影( w x + 6 ) l ，f = l ，2 ，刀 ( 2 5 ) 上述优化问题的解，对应着下列l a g r a n g e 函数的鞍点： 三( 吡a 日小善口， 州 ( 2 - 6 ) 式中，a ，为拉格朗日乘子。求解该函数的鞍点，得到的是原问题的对偶问题： 掣脚) 2 掣侉p 三毫蚂圳) ) n 善鹏，- 0 ( 2 7 ) 【口，o ，f = 1 ，刀 求解( 2 6 ) 得到最优的l a g r a n g e 乘子，那些对应于l a g r a n g e 乘子大 于零( 即a ，0 ) 的训练样本被称为支持向量( s u p p o r tv e c t o r s ) 。 最后得到的最优超平面方程为： 西南科技大学硕士研究生学位论文第9 页 厂( x ) = s 印( 矿。x ) + 6 = s 印t 善a - y t 。t + 工) + 6 ， ( 2 8 ) i ，皇lj ，9 一q 、 i ，= a ， t 其中，矿为最优分类面的权系数向量，口? 为式( 2 7 ) 的最优解，6 为阈 值。 1 1 1 i n 劲硎2 + c 窆量 s j ? ! 一。工十6 ) 1 一髻，f ：1 ，2 ，刀 峰o 一7 ( 2 9 ) 当样本集线性不可分时，此时某些训练样本不能满足式( 2 2 ) ，可以在约 束条件中引入松弛变量。此时求解广义最优分类面的规划问题变为式( 2 9 ) ， 式中c 0 是一个正则化常数，它控制对错分样本的惩罚程度。通过引入 l a g r a n g e 乘子，相应的对偶规划问题变为： 警缈c a ，= 警 o ) ，其中d ( x ，j ) 表示某种 “距离 函数； ( 4 ) s i g m o i d 核：k ( x ，安) = t a n h ( y ( x ，i ) + c ) ，( y ，c r ) 。 除以上介绍的常用核外，还可以从己知的核函数可以构造新的核，具体 参见文献 5 5 ， 5 6 。 西南科技大学硕士研究生学位论文第1 1 页 2 3支持向量回归机 s v m 方法首先从事解决分类( 模式识别) 问题发展起来的，随着v a p n i k 将不敏感损失函数的引入n ”，将该方法推广到回归问题时，提出了支持向量 回归算法( s u p p o r tv e c t o rr e g r e s s i o n ，简称s v r ) 。s v r 具有较好的推广能 力和非线性处理能力，尤其在处理高维数据时，有效的解决了“维数灾难 问题 ”。在非线性系统辨识、预测预报、建模与控制等领域得到了广泛应 用。 假设给定一组独立同分布的训练样本： d = ( ，咒) l x ，r d ，只匕j = 1 ，咒) ( 2 一1 3 ) 以及假设函数集： f = 厂i 厂：r d r ) ( 2 1 4 ) 回归问题的目标就是通过对样本的训练，找到一个函数厂，使得在 该函数下训练样本的值与其实际值的误差不大于给定的偏差s 。为叙述方便 起见，设函数厂有如下线性形式( 对于非线性情况，可以通过前述核技巧直接 扩展即可) ： 厂( x ) 2 w x + 6 ( 2 一1 5 ) 其中，w r d ，6 r 表示阈值。 根据s r m 原则，求解函数厂归结为如下的规划问题： 幽如叫1 2 + c 窆( c ( 毛) + c ( 刊 ( 2 _ 1 6 ) l 乃一w 毛一6 s + 磊 s j w 葺+ 6 一咒+ 考j 峰，考，o ，f = 1 ，2 ，刀 其中，c 0 ，我们的算法为： ( 1 ) 初始化岛，c o ，r ( 2 )当给定的散乱点集中不再有点z 满足式( 3 10 ) 时程序结束跳出，否 则继续 l l 万( z ) 一q l l 2 + 仃? ( 1 + ) 足 ( 3 一l o ) ( 3 )找到与映射莎( z ) 对应的点z ，其为距离中心q 的最远点。令 s + l = 墨u z ， ( 4 ) 由式( 3 6 ) 确定新的最小包闭球尬b ( 墨+ 。) ，由式( 3 4 ) 确定 c ，“2 ( )坞“。咧跏) ( 5 )令f = ，+ l 转到第( 2 ) 步继续。 最后，由本算法所得到的核集中的元素，我们称之为支持向量，将用于 曲面的生成。而且，文献 6 0 中已经证明了，用这种核方法的复杂度是与训 练样本的大小无关的。 3 3 3多级提取 西南科技大学硕士研究生学位论文第2 2 页 为了满足重建曲面的不同精度的需要，在提取支持向量的时候我们采用 了一种多级提取的方法。这种算法的思想是，算法开始用设定最小包闭球的 最大半径，在下一步减小包闭球半径，这样就可以得到高一级别等级的支持 向量。用更高一级密度的支持向量逼近原模型，以消除上级逼近后的残留误 差。最后回归得到的函数是各级回归函数的一种组合( 具体的函数回归算法参 见第4 章) 。 如我们要回归的函数形式是厂f z l = 0 ，在初始精度( 1 级精度) 的时候实验 得到曲面与点之间的误差为q 。我们令输出为q ，构造新的回归函数五( z 1 ， 因此对于2 级的精度的回归来说，隐式函数的回归方程就变为 ( z ) 一石( 工) = o ，由此循环至第i 级精度回归得到误差q ，构造出新的回归 函数，( z ) ，而新的隐式回归函数变为厂( x ) 一z ( x ) = o ，从而实现了多级回 归。 需要注意的是，有时在实验中，我们在重建函数曲面时，取更多的支持 向量得到的精度反而下降。那么我们将去除上一级精度用到的支持向量，再 进行函数曲面回归，这样就能保证本算法的有效性。从而使本算法可以满足 不同精度的需要。 3 3 4 实验及结果 为了和目前比较成熟的方法比较我们选用了斯坦福大学的兔子和龙模 型。用我们自己开发的实验平台实验，具体的实验平台将在最后一章中介绍。 表3 1实验电脑的基本配置 t a b ie 3 1 c o n f j g u r a t i o no fc o m p u t e rt ob eu s e d ine x p e ri m e n t 指标性能参数 c p u 内存 显卡 主板 硬盘 p 4 d3 4 0 g h z 5 1 2 m b 2 5 6 m b ，g e f o r c e7 3 0 0 ，n v i d i a i n t e l9 2 5 1 6 0 g b w d 实验中，由于要对比不同方法的处理速度，因此实验电脑的性能参数很 重要。实验电脑的基本配置如表3 1 所示。 西南科技大学硕士研究生学位论文第2 3 页 3 341 支持向量提取实验 我们用文中提到将支持向量回归问题视为最小包闭球问题的算法，提取 出支持向量。图3 2 ( a ) 显示了兔子的点云模型，( b ) 、( c ) 、( d ) 分别显示了 利用上述算法提取出的3 个级别的4 7 8 个、2 6 0 5 个和1 6 k 个支持向量，图 3 3 ( a ) 显示了龙的点云模型，( b ) 显示了提取出的5 0 7 6 个支持向量点。 t 气蔷 ：曩：o ? 蠢j 孑 壤嚣； a ) 点云模型b ) 支持向量( 16 k 个点) c ) 支持向量( 2 6 0 5 个点) d ) 支持向量( 4 7 8 个点) 图3 2兔于的点云模型殛支持向量 f ie3 2p tc i o u do fb u n n ya n di t ss u p p or tv e c t or s a ) 点云模型b ) 支持向量 圈3 3龙的点云模型及支持向量 f i g3 3 p o i n tc i o u do fd r a e n di t s s u p p o r to e c t ors 由于在本文用于曲面重建的算法包括两个步骤，即支持向量的提取和应 用m a r c h i n gc u b e s 方法对曲面的表示。所以本文中分别统计了各个阶段的时 间，由于在文中使用了对最小包闭球法的逐级逼近方法，通过限定最小包闭 球半径为最大值为原晟小包闭球的1 2 ，进而实现对支持向量的分级提取。 根据不同的精度要求可以提取出不同数量等级的支持向量。表32 中列 出了对兔子的三个精度级别的支持向量的提取结果和运算时间。 西南科技大学硕士研究生学位论文第2 4 页 表3 2获得不同级别的支持向量的运算时间 t a b i e 3 2 d i f f e r e n tt i m ei nc o m p u t in gt h es u p p o r tv e c t o r si n dif f e r e n ts c aie s 从实验的结果可以看出，随着采样级别的升高确定的支持向量的数量也 随之增多，同时用于训练支持向量的时间也增长。 3 3 4 2对比实验 为了更好的验证本文中算法的有效性，通过均匀网格法、迭代法和c a t i a 中的两种点云精简处理方法做对比实验，同样的兔子模型提取出约4 7 8 个支 持向量( 点) 时。对比实验证明了本文中算法的快速性，并保证相对较小的误 j 左。 表3 3获得不同级别的支持向量的运算时间 t a ble 3 3dif f e r e n ttim einc o m p u tin gt h es u p p o r tv e c t o r sin djf f e r e n ts c aie s 方法原始点支持向量提取时间误差范围 ( 秒)( 皿m ) 均匀网格法3 5 ，9 4 7 4 7 8 8 9 60 6 4 3 一0 。2 5 3 迭代法3 5 ，9 4 74 7 84 6 7o 1 8 0 一o 2 9 0 c a t i a 中按公差球简化3 5 ，9 4 7 4 7 83 0 50 1 2 6 一o 1 0 0 c a t i a 中按弦偏差简化3 5 ，9 4 74 7 82 1 3o 4 7 0 一o 3 7 2 本文算法3 5 ，9 4 74 7 82 7 8 4o 5 8 一o 9 表3 3 说明了本文中的算法在大规模点云数据中确定支持向量的有效性 和快速性。 本文所指的误差是将简化后的各点云数据在i m a g e w a r e 中拟合成曲面分 西南科技大学硕士研究生学位论文第2 5 页 别与原始点云拟合的曲面进行误差比较。 由于支持向量回归的速度和回归算法中的参数选择有关，所以本文中的 时间是在经过多次实验后获得，固定一种参数选择后测试所得到的结果。如 果对公式( 2 9 ) 中的c 值和s 不敏感损失函数中s 取值的不同，优化时间也会 不一样。 3 4本章小结 本章分析和研究了目前常用的点云数据精简算法及它们的特点，分析了 c a t i a 软件中反求模块对点云精简实现的基本原理。 在研究现有算法的基础上，实现了一种基于最小包闭球( m e b ) 原理由海量 点云数据中支持向量的多级提取算法。通过均匀网格法、迭代法和c a t i a 中 的两种点云精简处理方法对比实验证明了本文中算法的快速性，并保证相对 较小的误差。 西南科技大学硕士研究生学位论文第2 6 页 4 函数曲面重建 目前，由密集的点集重建曲面的方法有很多种“”，在前文中已经介绍过。 将散乱点云数据用函数拟合重建的优点是计算简单，容易实现；其主要缺点 是精度低，数据量大时计算不稳定。本章首先介绍了算法的推导过程，并以 三维复杂函数曲面为例，在小样本的条件下，应用本文中的算法直接在随机 分布的小样本条件下对函数曲面进行重建，通过实验证明本章所介绍的算法 的有效性。本章回归得到的显式隐式是下一章算法的基础。 4 1 暑不敏感损失函数 在本节中将引入一种损失函数( 称为s 不敏感损失函数) ，它不但使支持 向量回归估计具有鲁棒性，而且它是稀疏的。解的稀疏性对在高维空间中用 大量数据估计依赖性关系是非常重要的。 以往的基于经验风险最小化的回归估计中，采用的是形如的二次损失函 数： m ( y ，厂( x ，口) ) = ( y 一厂( x ，口) ) 2 ( 4 1 ) 在y 是一个回归函数加上正态加性噪声考的测量结果的条件下，这是经验风 险最小化原则提供回归函数( 毛口。) 的一个有效估计子。然而，如果加性噪声 不是正态分布的，则对回归函数的较好逼近需采用其他的损失函数。 因此，为了构造针对实函数集的支持向量回归模型，必须使用一类新的 损失函数，即s 不敏感损失函数，函数如式( 4 2 ) 所示。 m ( y ，厂( 础) ) = 三( 1 y 一厂( 挪) l 。) ( 4 2 ) 其中，令 乒弛卜徭j 嘴毳 式( 4 2 ) 、( 4 3 ) 所定义的损失函数描述了不敏感模型： 观测值之间的偏差小于s ，则损失等于零。 ( 4 3 ) 如果预测值与 西南科技大学硕士研究生学位论文第2 7 页 三( i 少一厂( 五a ) i 。) = i 少一( 毛口) l 。 ( 4 4 ) 三( 1 少一厂( x ，a ) i 。) = l j ，一厂( x ，a ) i ( 4 5 ) 圳川酬户毪铡蠢l 端气刊 图4 1 线性s 不敏感损失函数 f i g 4 1 li n e a ri t y s i n s e n s i t i v ef u n c t i o n 4 2非线性函数的回归 作为线性函数回归( 详见2 3 节) 的拓展，对非线性函数的回归是通过 某一非线性函数妒( x ) 将输入样本向量x 映射到一个高维特征空间中。然后在 这个高维特征空间中，进行线性函数的逼近，如式( 4 7 ) 所示。 西南科技大学硕士研究生学位论文第2 8 页 ( x ) = w 妒( z ) + 6 ( 4 7 ) 仍以形如( 2 9 ) 的独立分布的训练样本为前提，最小化问题变为最小化式 ( 4 8 ) ： 曲帅2 + c ( 和剥 ， j = l，= l p 一( 州( 薯) ) 一6 岛+ 岳 豇( w 呦( ) ) + 6 一咒q + 喜 陪磊巩 【f 1 ，2 ，行 ( 4 8 ) 类似线性情况，最终可得到w o 】f e 对偶最优化问题如( 4 9 ) 式 一去( 口，飞) ( 口厂a ，) k ( 薯，_ ) j = 1 + 咒( 倪卜a ，) 一毛( 口，+ 引 ( a ，一口j - ) = o j = 1 s j o a - c ，o 口，c ( 4 9 ) 其中k ( 而，一) = 咖( 薯) 咖( 一) 为满足m e r c e r 条件的核函数k ( 薯，) ，利用核函 数把特征空间的内积转化为输入空间中某些计算，从而就不必知道非线性转 换函数妒f 工) 的具体形式，也避免了各种复杂的计算。最终回归逼近函数为式 ( 2 2 0 ) 的形式。 在优化回归结果的过程中，可以按照一些成熟的支持向量机方法按照式 ( 4 9 ) 修改优化目标函数和约束条件即可。 4 3三维函数曲面重建 散乱测量数据点可用三维坐标( t ，少，刁) ，江1 ，2 ，胛来表示，利用s v r 对 这些测量数据点重建三维