（模式识别与智能系统专业论文）逆向工程中散乱点云数据预处理算法研究.pdf

西南科技大学硕士研究生学位论文第1 页 摘要 逆向工程实现了由实物模型直接构建计算机模型，是当今制造业领域 一项重要技术手段。从实物模型采集而来的点云数据通常数据量庞大且杂 乱无序，影响后续处理的效率和精度。因此，在进行后续处理之前，散乱 点云数据预处理显得尤为重要。 在点云数据预处理算法研究基础上，本文将转台拼接算法、排序算法 及拓扑构建算法作为主要研究内容，对算法存在的问题提出相应改进。 在转台拼接算法研究中，针对现有的圆柱拟合算法应用于低密度点云 数据时所得转台转轴精度降低，提出基于投影的圆柱拟合算法，并结合四 元素法实现转台拼接。实验表明，基于投影的圆柱拟合算法对低密度点云、 残缺点云均有良好的拟合结果，转台转轴和转台拼接的精度得到有效保 证。 在排序算法研究中，权衡保留形貌信息和排序速度，提出基于希尔排 序的点云全排法。实验表明，基于希尔排序的点云排序算法排序速度得到 提高。 在拓扑构建算法研究中，针对k d 树构建过程中分裂点的选取涉及大 量排序而导致算法复杂、耗时，提出基于三坐标映射的均衡k d 树构建方 法，并在均衡k d 树基础上实现查询、k 近邻搜索、序列化及反序列化。 实验表明，基于三坐标映射的均衡k d 树构建算法时间复杂度降低。 实验表明改进算法是可行的，提高了点云预处理算法的速度和精度。 关键词：转台拼接圆柱拟合希尔排序k d 一树 a b s t r a c t r e v e r s e e n g i n e e r i n g i s a l l i m p o r t a n tt e c h n o l o g yi n m a n u f a c t u r i n g i n d u s t r yt h a tc o n s t r u c t sc o m p u t e rm o d e l sd i r e c t l yf r o mp h y s i c a lp r o d u c t s t h ep o i n tc l o u dg a t h e r e db ym e a s u r e m e n te q u i p m e n t sa r eu s u a l l vm a s sa n d d i s o r d e rd e c r e a s i n gt h ee f f i c i e n c ya n d a c c u r a c yo ff o l l o w i n gp r o c e s s i n g s o ， p o i n tc l o u dp r e 。p r o c e s s i n gi si m p o r t a n tb e f o r et h ef o l l o w i n gd a t ap r o c e s s i n g o nt h es y s t e m a t i cs t u d yo fp o i n tc l o u dp r e p r o c e s s i n g ，a l g o r i t h m ss u c h a st u r n t a b l em o s a i c s ，s o r ta n dt o p o l o g yc o n s t r u c t i o n a r e ，a r em a i n l ys t u d i e d i nt h i st h e s i s a d v a n c e ds o l u t i o n sa r ep r o p o s e df o re x s i t i n gp r o b l e m s i nt h er e s e a r c ho ft u r n t a b l em o s a i c s ，t os o l v et h e p r o b l e mt h a tt h e e x i s t i n gc y l i n d r i c a lf i t t i n ga l g o r i t h m sa r en o tf i tw i t hl o w d e n s i t yp o i n tc l o u d m a k i n gd e r i v a t i o no ft u r n t a b l es h a f ti n a c c u r a t e ，a d v a n c e dc y l i n d r i c a lf i t t i n g a l g o r i t h mb a s e do np r o j e c t i o ni s p r o p o s e d t h e n ，t u r n t a b l em o s a i c sa r e a c h i e v e db a s e do nq u a t e r n i o nm e t h o d t h r o u g he x p e r i m e n t ss a t i s f i e df i t t i n g r e s u l t sa r eg a i n e db yc y l i n d r i c a lf i t t i n ga l g o r i t h mf o rl o w d e n s i t yp o i n tc l o u d a n di n c o m p l e t ep o i n tc l o u dm a k i n g e f f e c t i v e l yg u a r a n t e ef o rt u r n t a b l es h a f t a n dt u r n t a b l em o s a i c s i nt h er e s e a r c ho fs o r t ，w e i g h i n gr e t a i n i n gm o r p h o l o g yi n f o r m a t i o na n d i m p r o v i n gs o r ts p e e d ，a l g o r i t h mo fs o r tf o ra l lp o i n tc l o u dw i t hh i l ls o r ti sp u t f o r w a r d t h ee x p e r i m e n t a lr e s u l t sp r o v et h a tt h es p e e do fp o i n tc l o u ds o r ti s i m p r o v e db yh i l ls o r t i nt h er e s e a r c ho ft o p o l o g yc o n s t r u c t i o n ，b a l a n c e dk d t r e ec o n s t r u c t i o n a l g o r i t h mw i t hc o o r d i n a t em a p p i n gi sr a i s e dt od e c r e a s eh i g ht i m ec o m p l e x i t y c a u s e db ym a s ss o r tf o r s p i l tp o i n t t h e na l g o r i t h m s ，i n c l u d i n gi n q u i r y ， k 。n e a r e s tn e i g h b o r ss e a r c h ，s e r i a l i z a t i o na n d ，d e s e r i a l i z a t i o n a r es t u d i e do n t h eb a l a n c e dk d t r e e t h et i m ec o m p l e x i t yo f a l g o r i t h mo fb a l a n c e dk d t r e e c o n s t r u c t i o ni sr e d u c e d t h ee x p e r i m e n t a lr e s u l t sp r o v et h ef e a s i b i l i t yo ft h es o l u t i o n sb yw h i c h t h ee f f i c i e n c ya n da c c u r a c yo fp o i n tc l o u dp r e p r o c e s s i n ga r ei m p r o v e d k e y w o r d s ：t u r n t a b l em o s a i c s ；c y l i n d r i c a lf i t t i n g ；h i l ls o r t ；k d t r e e ，、，、_ 一一一。 _l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得西南科技大学或其它教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示了谢意。 签名：璐日期：泗7 ，p 关于论文使用和授权的说明 本人完全了解西南科技大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文的复印件，允许该论文被查阅和借阅；学校可以公布该论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：路档 导师躲尚蕊却日期： 炒夕多 ， 西南科技大学硕士研究生学位论文第1 页 l 绪论 随着科学技术的飞速发展使产品更新换代的步伐不断加快，激烈的市 场竞争要求产品研制生产周期越来越短，同时消费者的需求日趋个性化， 社会对产品多样化的要求日益加强，多品种、中小批量生产的比重明显增 加。因此，制造部门为适应瞬息万变的需求，快速地、灵活地组织生产， 提出了许多新的制造技术。逆向工程就是其中之一，这项新技术的出现缩 短了产品的研发周期，尤其对产品外形的设计。 点云数据预处理技术通过去噪、拼接、排序、分割等为后续处理提供 纯净、有序的点云数据。研究点云数据预处理具有重要的现实意义。 本章首先介绍逆向工程概念及其体系结构，然后着重阐述逆向工程中 点云数据预处理技术的重要性及研究现状，然后阐明本课题研究意义和研 究内容，最后介绍论文的章节安排。 1 1课题研究背景 1 1 1逆向工程概述 近几十年来，随着计算机技术的发展，c a d ( 计算机辅助设计1 技术己 经广泛地应用于新产品的研制开发。但由于多种因素的限制，现实世界中 的很多物体形状并不能用以c a d 设计的方法进行描述。因而，出现了逆 向工程( r e v e r s ee n g i n e e r i n g ) 的概念 i , 2 i p 它是2 0 世纪8 0 年代初分别由 美国3 m 公司、日本名古屋工业研究所以及美国u v p 公司提出。逆向工程 是指通过各种测量手段和三维几何建模方法，将己有的零件或实物原型转 化为计算机上的三维数字模型的过程，是测量技术、计算机软硬件技术、 现代产品设计与制造技术的综合应用h ，。因此，逆向工程技术可以认为是 将产品样件转化为c a d 模型的相关数字化技术和几何模型重建技术的总 称。从流程上看，逆向工程流程与传统造型流程正好相反，如图1 1 所示。 西南科技大学硕士研究生学位论文第2 页 l 产品功能 上 i 概念设计 0 c a d 系统 上 c a d 模型 i 制造与检测 上 实物 a ) 传统造型流程b ) 逆向工程流程 图1 - 1传统造型流程与逆向工程流程图 f ig 1 1f i o wc h a t so ft r a d i t i o n a im o d e ii n ga n dr e v e r s ee n g i n e e ri n g 逆向工程的主要目的是为了改善技术水平、提高生产率和增强经济竞 争力。世界各国在机械行业中，应用逆向工程消化吸收先进技术和经验， 给了人们很多有益的启示。据统计，世界各国7 0 以上的技术源于国外， 逆向工程作为掌握新技术的一种手段，可使产品研制和制造周期缩短 4 0 9 0 。逆向工程的应用领域极为广泛，主要包括【孓，l ： ( 1 ) 机械设计制造领域，可用于航空、航天、汽车、摩托车、模具等行 业的产品c a d 设计与制造； ( 2 ) 医学领域，可以利用逆向工程对人体中的骨头、关节、牙齿的复制 以及假肢的制造； ( 3 ) 可以利用逆向工程对破损的艺术品进行修复、对考古文物等进行复 制。 除此之外，逆向工程在自然景物的数字化、计算机辅助检测等领域也 有广泛的应用。 西南科技大学硕士研究生学位论文第3 页 1 1 2逆向工程体系结构 逆向工程主要分为数据获取、数据预处理及曲面建模三个环节。 ( 1 ) 数据获取 数据获取是逆向工程的第一阶段，可以通过多种手段m ，对物体进行测 量，得到物体表面点的三维坐标值。根据测量的方式可分为接触式测量和 非接触式测量两大类，接触式测量主要有坐标测量机和层析法【，1 。非接触 式测量，根据测量原理的不同可分为光学测量、计算机视觉、超声波测量 和电磁测量等。其中h o r n n0 1 提出了阴影恢复形状的实现原理并做了详细的 研究。 由于非接触测量方法有着自动化程度高、速度快和测量简便等优点， 在逆向工程中得到了广泛地应用。不管采用何种测量方法，测量数据都要 尽可能地把物体的表面形状完整表现出来，特别是物体表面的细节特征。 ( 2 ) 数据预处理 实物模型经过测量得到的往往是以散乱点形式无序排列的大量点云。 基于物体复杂程度不同，实体点云的数据量有很大区别，就整体而言，从 c a d c a m 处理的角度，这些点云的数据量庞大；并且由于测量仪器和其 他诸如环境因素的影响，不可避免地引入噪声点。因此在进行后续的操作 一一特征提取及模型重建前，需要对数据进行预处理，如噪声点去除、冗 余数据精简。数据预处理是逆向工程中的重点和难点，数据预处理的质量 直接影响产品的加工质量。点云数据预处理技术显得尤为重要。其主要的 处理工作包括点云去噪、点云拼接、点云精简、点云排序、拓扑构建、点 云分割、点云派生等。 图1 - 2点云数据预处理 f i g 1 2p r e - p r o c e s s i n go fp c ；n t c i c u d 图1 2 列出点云预处理的主要环节，并且各环节顺序根据实际情况而 变。例如转台拼接可在无序的点云数据上进行，故点云排序可在点云拼接 西南科技大学硕士研究生学位论文第4 页 之后；而借助于标记点的软件拼接算法需要点云数据有序，因此在进行拼 接之前需要进行点云排序。 ( 3 ) 曲面建模 模型重构是利用测量的数据来重构被测物体的曲面模型，是实现逆向 工程的重要环节，通过建模可以由离散的测量数据重构连续变化的曲面。 曲面拟合包括曲面插值和曲面逼近。曲面插值要求插值后的曲面严格地通 过数据点，通常将曲面插值分为整体插值和局部插值。曲面逼近是基于离 散数据构造出一个曲面，使这些点在某种意义下最为接近所构造的曲面， 它可以平滑随机误差，但所构造曲面与离散的点之间有一定误差。 1 2点云预处理技术及研究现状 1 2 1点云概念与分类 点云数据，是使用各种三维数据采集设备得到的空间上离散的几何 点，是由物体模型表面上一系列空间采样点构成的、对模型描述的表示。 构成点云的最基本单位为点。每一个离散点可以存储几何信息，如三维坐 标、大小和法向量等，也可以存储物体的其他表面属性，如纹理、光照参 数和透明度等，用户还可以附加其它的表面性质。 为了有效的处理各种形式的点云，根据点云中点的分布特点( 如排列方 式、密度等1 将点云可分为2 ，： ( 1 ) 散乱点云：测量点没有明显的几何分布特征，呈散乱无序状态。随 机扫描方式下的c m m ( 三坐标测量机) 、激光点测量等系统的点云呈现散 乱状态。 ( 2 ) 扫描线点云：点云由一组扫描线组成，扫描线上的所有点位于扫描 平面内。c m m 、激光点三角测量系统沿直线扫描的测量数据和线结构光 扫描测量数据呈现该特征。 ( 3 ) 网格化点云：点云中所有点都与参数域中一个均匀网格的顶点对 应。将c m m 、激光扫描系统、投影光栅测量系统及立体视差法获得的数 据经过网格化插值后得到的点云即为网格化点云。 ( 4 ) 多边形点云：测量点分布在一系列平行平面内，用小线段将同一平 面内距离最小的若干相邻点依次连接可形成一组有嵌套的平面多边形。莫 尔等高线测量、工业c t 、层切法、磁共振成像等系统的测量点云呈现多 西南科技大学硕士研究生学位论文第5 页 边形特征。 在本文中，主要研究的是散乱的点云所通用的处理方法。对于特殊类 型的点云，除了通用的方法外，还可以根据点云本身的特点灵活变化采用。 此外，测量点云按点的分布密度可分为高密度和低密度点云。低密度 点云，通常在几十到几千个点。高密度点云一般为几百万点。本文研究对 象为几万至几十万点。 1 2 2 点云预处理技术 由数据采集设备得到的三维数字化的结果是空间上离散的几何点，因 此在c a d 模型重建之前应进行数据预处理，目的是获得完整、准确的测 量数据以方便以后的造型工作。其主要的处理工作包括点云去噪、点云拼 接、点云排序、拓扑构建、数据精简、点云分割、点云派生等。 ( 1 ) 点云去噪 测量中由于测量仪器以及其他方面的因素，不可避免地引入噪声点， 降低模型重构的精度。故在进行点云数据操作之前，先进行消除噪声的工 作。 目前通常是采用标准高斯、平均或中值滤波算法。其中高斯滤波能较 好地保持原数据的形貌，中值滤波消除数据毛刺的效果较好“”。因此在选 用时应该根据数据质量和建模方法灵活选择滤波算法。 ( 2 ) 点云拼接 逆向工程技术进行数据采集时，由于受到测量设备和环境的限制，物 体表面完整测量数据的获得往往需要通过多次测量完成。由于每次测量得 到的点云数据往往只覆盖物体部分表面，并且可能出现平移错位和旋转错 位，因此为了得到物体完整表面的点云数据，需要对这些局部点云数据进 行拼接。 三维数据拼接是逆向工程中数据处理的重要组成部分，很多文献都1 ， 对这项技术做了深入细致的研究。目前，三维数据拼接主要分为两大类】 第一类方法是采用经过高精度定标的仪器获取的多片数据以及它们之间 的原始变换关系来进行数据拼接，第二类方法则是利用数据中的变换信息 或利用获取数据时引入的其它信息对三维数据进行拼接。 对于第一类拼接方法，t a m a sv a r a d f l7 ，介绍了一种转台定位法，将测量 物体放置在转台上，测头固定不动，通过被测物体和转台同步旋转的方式 西南科技大学硕士研究生学位论文第6 页 来调整物体的位置，得到多个角度的点云数据，然后根据转台旋转角度完 成多个角度点云的拼接。b e s 提出了迭代最近邻点( 1 t e r a t i v ec l o s e tp o i n t ， i c p ) 拼接算法，此方法属于第二类拼接方法。c h e d 川和z h a n g t ”，对i c p 算 法进行了改进，但仍存在着两个问题：初值选取和在每一步迭代过程中确 定对应点对，初值选取不当，算法将会形成局部最小化，对应点对的确定 直接影响到算法的精度。 本文研究第一类拼接方法一一转台拼接技术。不同时刻获得的数据需 要通过转轴方程经过一定的旋转实现拼接，因此转台转轴方程的准确获取 是转台拼接的关键。转台转轴方程可转化为圆柱体轴线方程的获取。在圆 柱体的拟合算法中，有l u k c i c s 拟合算法和高斯映射算法。这两种算法获 取拟合初值时对点云的稠密度有较高要求，不适用于稀疏点云。然而，实 际转台转轴获取过程中，靶标平面上的点组成的圆柱体通常为稀疏点云， 因此寻找稀疏点云的圆柱拟合算法是本文研究的重点之一。 ( 3 ) 点云排序 通过测量仪器获得的数据通常是大量的散乱点云，为进一步对点云进 行处理( 如拓扑构建、获得特征线和构造平滑曲面等) ，应该对其进行排序， 打破其原始无序状态，以便构造拓扑关系。 参与排序的点云数据可以为全部点云数据或截线云数据 ”，对应排序 方法分别称为全排法和截线云法。前者保留了点云数据的全部形貌信息， 但数据量大，排序速度降低；后者点数较少，适合于局部征变化不明显的 点云数据。基于保留数据原貌的考虑，本文采用全排法。 在排序的具体实现算法中，基本排序算法有插入排序、选择排序、快 速排序及基数排序算法。目前数量通常在万级及以上的点云数据排序算法 常选用直接插入法，因其算法简单，易实现，但是大量的记录移动及比较 次数使得点云排序仍然耗时。在保留数据原貌的基础上提高排序速度是本 文研究内容的所在。 ( 4 ) 拓扑构建 拓扑构建幢引是散乱点云数据预处理的重要环节。拓扑构建旨在寻找点 的邻接关系，从而实现点的局部区域访问，实现三角剖分、曲面重建等。 常见的拓扑构建方法有空间栅格法心“、八叉树法幢7 ，及k d 树法心”。空间 栅格法算法简单，缺点也很明显，其一，固定的栅格尺寸不适用于非均匀采 样，其二，栅格尺寸较大时会导致本来不相连的模型局部连接在一起。为了 克服这些缺点，通常采用基于曲面几何性质的群集构造方法，即根据模型表 西南科技大学硕士研究生学位论文第7 页 面不同的采样密度划分群集h 一一八叉树法与k d 树法。八叉树法将指定的 三维空间区域分成八个卦限，每个非叶子结点处存储八个卦限信息。但是八 叉树存在冗余，所需存储空间较大。k d 树最早由b e n t l y e b 引通过将二叉查找 树扩展到高维空间提出，后来f r e i d m a nr 3 和s p r o u w ”，等人对其进行了发展。 k d 树非常适合于存储空间中的位置和大小信息，也具有较高的查询和 搜索效率，但k d 树构建时分裂点的选取涉及多次排序，k d 树构建时问复 杂度高，耗时。如何提高k d 树的构建速度是本文研究的重点之一。 ( 5 ) 数据精简 测量获得的数据十分庞大，使后续处理在时间和空间上增加额外开 销，因此数据精简十分必要。数据精简通过过滤、采样等使滤除冗余点云。 点云精简的工作在基于实体结构允许的误差范围内进行，否则就会丢失有 用的数据信息，如尖锐角、棱线以及曲率变化大的区域数据。 不同类型的“点云”可采取不同的精简方式，如散乱点可选择随机采 样、均匀网格、三角网格方法b 钔；扫描线和多边形点云可采用等间距缩减、 倍率缩减、等量缩减、弦高差等方法；网格化点云可采用等分布密度法和 最小包围区域法等。精简算法的效果从精度、简度和速度上衡量。精简的 最佳效果是使精简后的数据点云具有较少的数据量，不丢失物体表面的细 节特征，速度快。 ( 6 ) 点云分割 对于复杂、曲率变化大的实体，为了更好地提取区域特征以提高模型 重构精度，通常将点云数据进行分割。按照分割的依据不同，点云分割可 以分为基于边的分割、基于面的分割及群簇分割。 ( 7 ) 点云派生 在后续建模中，需要在原有点云的基础上构造新的点云，即点云派生。 点云派生方法有很多种，如镜像原始点云、对原始点云按比例缩放、对原 始点云加密、原始点云对齐到新坐标系、抽取原始点云扫描线等。 1 3 课题研究内容及意义 数据拼接可以解决对复杂物体完整测量，数据排序使杂乱无序点云变 得有序，而拓扑关系构建则更进一步确定点的邻接关系，为逆向工程中后 续的吐面重建奠定必要基础。研究逆向工程中的数据拼接、数据排序及拓 扑关系构建具有重要的现实意义。 西南科技大学硕士研究生学位论文第8 页 本文主要研究内容如下： ( 1 ) 转台拼接算法研究。转轴方程精确与否对转台拼接有很大影响。 在转轴方程获取过程中，现有圆柱拟合方法不适应于稀疏点云而导致拟合 初值不能准确代表原始点云的几何特性，拟合精度降低。在稀疏点云情况 下如何获得较好的拟合初值以提高圆柱拟合精度是本文的研究内容之一。 ( 2 ) 散乱点云数据排序算法研究。研究参与排序的数据量的选取，分 析比较全排法和截线云法的优缺点，全排法耗时但保留点云全部形貌信 息，截线云法速度快但丢失形貌信息；研究多种排序实现方法及其性能分 析，包括插入排序、快速排序、选择排序和基数排序等；研究现有的基于 直接插入法的点云数据排序方法。直接插入法实现简单，在大量数据时排 序速度慢；如何保留数据原貌信息同时提高排序速度是本文的研究内容之 一o ( 3 ) k d 树拓扑关系构建研究。在点云的拓扑结构中，k d 树是便于搜 索的多维二进制树。在k d 树的构建过程中，分裂点的选取涉及排序，使 得k d 树的构建过程变得复杂、耗时。如何简化分裂点的获取、提高k d 树的构建速度是本文的研究内容之一。 1 4 章节安排 全文共分六章，章节安排和主要内容如下： 第一章绪论。本章主要介绍了逆向工程技术，点云数据预处理技术 及研究现状，以及本文的研究内容。 第二章点云数据预处理相关数学基础。本章主要介绍点云数据预处 理相关的数学知识，包括最小二乘法、l m 算法、点云邻域类型，协方差 分析与点云法矢，点云曲率的计算等。 第三章点云数据转台拼接算法研究。本章首先介绍转台拼接技术及 相关算法，分析现有转轴获取时圆柱拟合算法存在的问题；第二阐述基于 投影的l m 圆柱拟合算法；第三是实验数据与分析，第四是小结。 第四章点云数据排序算法研究。本章首先研究参与排序数据量的选 取；第二介绍点云排序算法，包括基本排序算法及其性能分析( 如插入排 序、快速排序、选择排序及基数排序等) 及现有点云排序算法原理及存在 问题；第三阐述本文提出的希尔全排法算法原理及实现；第四是实验数据 与分析，最后是小结。 西南科技大学硕士研究生学位论文第9 页 第五章点云数据拓扑构建算法研究。本章首先介绍多种拓扑构建方 式，包括栅格法、八叉树法及k d 树法，并分析各自性能；第二详细介绍 改进的均衡k d 树拓扑构建方法；第三介绍基于k d 树的查询和k 近邻搜 索；第四介绍k d 树的序列化及反序列化算法原理，第五介绍基于k d 树 的点云分割算法。第六是实验数据与分析，最后是小结。 最后是结论，总结本论文的主要研究工作和成果，及对今后工作的展 望。 西南科技大学硕士研究生学位论文第1 0 页 2 点云数据处理相关数学基础 本章介绍点云数据预处理相关的数学知识。点云局部曲率是在 k n e a r e s tn e i g h b o r s 邻域基础上利用最小二乘法原理结合法矢、抛物面主 曲率等算法获得，是点云分割的依据；非线性最小二乘法应用于在转台拼 接算法中圆柱拟合。 2 1最小二乘法 最小二乘法n 5 1 通常是通过求得目标函数，o ) 的最小残差平方和来解 决超定方程组问题，即 f ( x ) = 罗( 厂 ) ) 2 = r a i n ( 2 1 ) 胃 其中，王。o 。，x ：，。) r ，厂& ) ：一p i r x 一以，a ；【；：，；：，；二】7 ，云。 b x ，b ：，k 】r 残差平方和对各参数的偏微分方程组称为法线方程。相对于法线方程 具有线性方程组和非线性方程组两种形式，最小二乘法也分为线性和非线 性两种方法。 ( 1 ) 线性最小二乘法 线性最小二乘法一般有三种变化形式，分别是法方程法m n e 、奇异 值分解法s v d 和特征向量估计法e v e 。 设有n 个数据点，可以得到方程组a x b ； 当a 为非奇异矩阵时，系数矩阵可以通过方程x 。似r 彳) 以a r b 求解得 到，这种方法称为法方程法。 当a 为奇异矩阵时，为了避免臼r 彳) ，将矩阵a 分解为u w v f ，其中缈 为非负值的对角阵，u ，y 都是正交矩阵，即wa d i a g ( w f ) 】，u r u v ? v = i 。 从而系数矩阵x 可以通过方程工av d i a g ( 1 w ，) r b 求到，这种方法成为奇 异值分解法。 当方程变为a x = 0 ，o 丁么) 。矩阵的为零或近似为零的特征值所对应的 西南科技大学硕士研究生学位论文第1 1 页 特征向量即为系数矩阵x 。这种方法称为特征向量估计法。 ( 2 ) 非线性最小二乘法 非线性方程组求解通常采用递归搜索寻找最优解，x ( “1 ) 。x 仕+ a k d ( ， 其中，d 似) 为下降方向。递归运算速度和结果与未知参数的初值估计息息 相关，初始值离最后估算值相差太大，不仅减缓了优化的速度，而且由于 最后结果陷入局部最小，致使整个优化过程不收敛。 非线性最小二乘法常采用两种迭代方法：高斯牛顿法g a u s s n e w t o n 法 和l e v e n b e r g m a r q u a r d t 法。g a u s s n e w t o n 对初始近似要求比较苛刻，且 在求解下降d 方向时，d = 一研；4 ) 。1 a l l n ，有时会出现矩阵群4 奇异 或接近奇异，使得求解d 。遇到很大困难，甚至根本不能进行。 l e v e n b e r g m a r q u a r d t 法对此进行了修正，改变原彳。特征值结构，使其 变成条件数较好的对称正定矩阵，成为有效的修正最小二乘法之一。 2 2 l e v e n b e r g m a r q u a r d t 算法 在l e v e n b e r g m a r q u a r d t 算法b ”中，令 d 耻= 一似；4 + a t ，) - 1 彳；，忙 ( 2 - 2 ) 其中，为n 阶单位矩阵，口。是一个正实数。当吼= o 时，d ( ) 与 g a u s s n e w t o n 法中下降方向一样。当口t 充分大时，逆矩阵4 + 吼，) 。1 主 要取决于，这时d 接近f o ) 在点石处的最速下降方向。吼的取值太 小不能保证d ( ) 为下降方向，取值太大则减慢收敛速度。根据经验，a 。初 始值口，= 0 0 1 ，其增长因子= 1 0 。 归纳上述过程，l e v e n b e r g m a r q u a r d t 算法的计算步骤如下： ( 1 ) 给定初始点工n ，初始参数，增长因子卢，允许误差 0 ，计算 ，o 1 ) ，置o l 一，k 一1 。 ( 2 ) 置口= c t 卢，计算 ；( l ( x ) ，厶o ”r a t = 矾0 )a ，1 0 ) 缸1缸。 吮o )吮0 ) 缸l觑。 ( 2 - 3 ) 西南科技大学硕士研究生学位论文第12 页 ( 3 ) 解方程 似；4 + 口t o d 肚；衫 ( 2 4 ) 求得方向d t ，令 工( “1 ) ；x ( + d t ( 2 - 5 ) ( 4 ) 计算f ( x ( “1 ) 。若 f ( x t k m ) o ，帆( i ) 一p i l s | p n ( i + ，) 一p ”【1 n - 1 1 ( 2 7 ) 则：是点p 的k 邻域的点的索引集合。有： ； n ( 1 ) ，n ( 2 ) ，。n ) ( 2 - 8 ) 同时索引集定义了一个半径为= 忙n ( 。) 一p l l ，中心在p 的球昂k ，p i 在 球内，当且仅当i n k p 。 以下讨论的两种邻域类型是基于k n e a r e s tn e i g h b o r s 投影到位于p 点 的切平面耳上的点集，即给定肿，则投影点q 。巧助。；。 ( 2 ) b s pn e i g h b o r s 定义子空间噩 西南科技大学硕士研究生学位论文第13 页 b i ：忸elq - q ；) ( p q ，) 则b s p ( b i n a r ys p a c ep a r t i t i o n ) n e i g h b o r s 定义为索引集 n ；l y e , ，i 二则f ；且g i n 曰， j n ( 2 - 9 ) ( 2 - 1 0 ) ( 3 ) v o r o n o in e i g h b o r s 设v 是点q i , ie n e k 的v o r o n o i 图，则点q f 的v o r o n o i 区域为： k - 甚乃l 忙一q 。0s 睁一q 川，w ；，一f ( 2 11 ) 若咋是包含点p 的v o r o n o i 区域，则点p 的v o r o n o in e i g h b o r s 定义为： ；当f ；且f ；，kn 咋一西 ( 2 1 2 ) a ) k - n e a r e s tb ) b s pn e i g h b o r s 图2 - 1邻域类型 f i g 2 1 n ei g h b o r h o o dt y p e 本文采用k n e a r e s tn e i g h b o r s 作为邻域表示，计算点云曲率，法矢都 应用此种表示。计算k n e a r e s tn e i g h b o r s 将在5 3 节中讨论。 2 4协方差分析与点云法矢 基于邻域中点的关系，以点p 为中心的邻域小面可通过最小二乘法的 方法拟合，从而可计算点云在该点p 位置的法矢。另一种简单的计算方法 是根据点p 以及邻域内点的位置，构造协方差矩阵，分析其特征值、特征 向量，可得该点及小面的法矢。 设p 是p 点和它邻域内所有点的中心点，即 西南科技大学硕士研究生学位论文第14 页 石= 1 袁 ( 2 砌) 胪p 丢既 蟛叫 从而可得点p 的3 x 3 协方差矩阵 cl i b 【0 f 1 - p ) ，p 故- p ) 】【o ；，- p ) ，o 醍一p ) 】r ，f ，( 2 一l4 ) 矩阵表示点p 邻域内采样点的分布情况一一点与中心点p 平方距离的 累积。考虑下式的特征向量问题： c ，f = v pz 0 ，1 ，2 ( 2 1 5 ) 既然c 是对称正定矩阵，所以所有的特征值是实数、特征向量是正交 的。跟据点p 。到中心点的平方距离和总的变化可由下式表示： l p 。一万1 2 一九峨+ 九( 2 - 1 6 ) 店 ( 1 ) 法矢估计 假设 s 厶sa ：，则下式： 丁o ) ：o p ) ，o = 0 ( 2 一1 7 ) 可得可近似邻域小面在点p 处法矢刀p ，而 ，和y 2 则是切平面在点p 处的两个伸展方向。 ( 2 ) 法矢方向 根据协方差矩阵可计算出每个点的法矢，但是各个点的法矢朝向各不 相同，有点向内，有点向外。n 引提出了用最小生成树法规整所有点的法矢。 算法是通过具有最大z 坐标的点开始，考虑在最小生成树上的点，相邻点 的法矢之间的夹角大于：r 2 。则需要反向，如图2 2 所示。 图2 - 2法矢最小生成树归一化 f i g 2 - 2 r l o r l ；t a iv e c t o rn o r m a iiz a t i o nb ym in i i i l u b is p a n n in gt r e e 西南科技大学硕士研究生学位论文第15 页 2 5点云曲率 由微分几何可知”，曲面上一点处有无数个包含曲面法矢的密切平面， 密切平面与曲面交线的曲率就是曲面在该点的法曲率，法曲率的极小值和 极大值称为主曲率，主曲率所在密切平面的方向为主方向。曲面在某一 点的主曲率、高斯曲率、平均曲率可由曲面的第一和第二基本量计算出， 与曲面的参数无关。主曲率是该点局部形状的体现；高斯曲率可以确定曲 面上点的性质，表明该点是椭圆点或抛物点或双曲点；平均曲率是主曲率 之和的平均值，可表明曲面的凸凹。任意方向的法曲率可有e u l e r 公式决 定。 设点p 的k - 邻域为n b ( e ) = 只，足，只) ，为计算该点曲率，通过参数 二次曲面来估算曲率。首先建立二次曲面的参数方程： 2 r ( m ，y ) a g h ，7 ( 2 一l8 ) l ，j 。u 并令 w = 阻o v o , u o v i , u o ，2 , u 1 i j o ，u l y l , u 1 y 2 ，h 2 v 0 , 2 ，i , u2 y 2 r a = 【a o a , a o 】，口佗，a 】o ，a 1 】，a 1 2 ，a 2 0 ，a 2 1 ，a 2 2 】r b - i b ，b 0 1 ，b o ：，包o ，b l l ，b 1 2 ，b 2 0 ，b 2 1 ，b 2 2 】r ( 2 1 9 ) c = k ，c 0 1 ，c 0 2 ，c l o ，c l l ，c 1 2 ，c 2 0 ，c 2 1 ，c 2 2 】r q = 【口，b ，c 】 得到参数方程： r ( u ，v ) = o ，y ) ，y ( u ， ，) ，z ，y ) ) a ( r a ，w r b ，w r c ) = w r q ( 2 2 0 ) 式2 2 0 是本文应用最小二乘法求解曲率的基本公式，下面对邻域内的 点进行参数化。邻域n b ( p ) 的隐含曲面被一个局部基面逼近，本文选择点p 处的切平面丁( p ) 作为逼近m ( p ) 的局部基面，如图2 3 所示。将邻域内的 点云垂直投影到切平面上，得到投影域p r ( 一= e ，罡，只) 中，求解离p 最远点只。 西南科技大学硕士研究生学位论文第16 页 a ) k 邻域n b ( p )b ) 局部参数化 图2 - 3局部坐标系 f i g 2 - 3 i o c a ic o o r d i n a t es y s t e m 如图2 3 所示，建立局部坐标系。连接p t 、两点的直线方向作为u 方向，垂直于u 方向的直线作为v 方向，接着是将p r ( 尸) 中的每一点 o = l 2 ，k ) 都与p 相连，得到k 条有向线段。把这些线段变换到u v 新坐 标系下。具体做法如下：将这些有向线段分别与u 矢量作点积，记为d ， 得到的值进行排序，把最大值记为d 嘣，最小值记为d 坷。，通过式2 2 1 进 行参数化： m i 。孚粤，f ；1 ，k ，七 ( 2 2 1 ) a 嘣一口墒 这样就求出e r ( p ) 中各点的u 的参数值。用类似的方法可以得到投影 域中p r ( p ) 中各点的v 参数值。把所求得p r ( p ) 的参数应用到对应帕( p ) 上 去，从而实现了局部散乱数据的参数化。引入两个数据矩阵： f x o y o h ，卜 i 【吒 y i w = 【心，一，嵋】r ( 2 2 2 ) 式2 - 2 2 中点p 的坐标为e ( x 。，y o ，z o ) ，这里k 8 。逼近曲面和测点的误 差函数为： e = w q 一日 对式2 2 3 运用最小二乘法，推导出系数矩阵q 为： q 。缈r 矽) 。1 w r h ( 2 - 2 3 ) ( 2 - 2 4 ) 西南科技大学硕士研究生学位论文第1 7 页 从而得到曲面r ( u ，y ) 的偏导数乙，l ，曲面的单位法矢为： 以。三鼍 ( 2 2 5 ) n 0 l 根据曲面的第一和第二基本公式”： ，= e d u 2 + 2 f d u d v + g d v 2 ( 2 2 6 ) 口：l d “2 + 2 m d u d v + n d v 2 上式中的系数均为已知量，求出高斯曲率k 和平均曲率h 为： k ；l n - m = _ 2 e g f 2 ( 2 2 7 ) h ；l g - 2 m f + _ - n e 2 ( e g f ) 一 由主曲率、高斯曲率、平均曲率的关系式： k 也：h 瓢 ( 2 2 8 ) 得到主曲率k ik 2 ，相应的主方向为： m 1 。( d u ，咖) 2 ( r v n k 2 r r v ，r n 一七2 吒吒) ( 2 2 9 ) m 2 = ( 幽，咖) = ( ，0 忍一七l 吒厂v ，吒。n 一七1 吒吒) 西南科技大学硕士研究生学位论文第18 页 3 点云数据转台拼接技术研究 转台拼接是借助高精度测量设备，通过一定的变换关系对不同角度下 获取的点云数据进行整体拼接的技术“。转台拼接技术实现由“分片 点 云到整体形貌拼接，是后续数据处理如拓扑构建、点云分割的基础。 本章首先介绍转台拼接技术及其应用，介绍转台拼接算法，包括转台 拼接模型、转换矩阵额测定及圆柱拟合算法。第二，分析现有圆柱拟合算 法在稀疏点云情况下所遇到的问题，阐述本文提出的基于投影的圆柱拟合 算法。第三是实验数据与分析。最后是本章小结。 3 1转台拼接技术 3 1 1转台拼接技术及其应用 ( 1 ) 转台拼接技术 罗转台转轴 闩 u 摄像机 转台 a ) 物体随转台旋转b ) 不同角度下的点云c ) 旋转拼接 图3 - 1转台拼接示意图 f i g 3 1s c h e m a t i co ft u r n t a b i em o s a i c s 点云数据采集过程中，由摄像机单次获取的点云数据是物体在某一角 国二国二b一 一；：；|：r。；。 西南科技大学硕士研究生学位论文第1 9 页 度下的测量数据。物体3 6 0 度的完整点云数据则需要将各个角度下的点云 数据拼接在一起。转台拼接是利用转台转轴对不同角度下的点云数据进行 旋转拼接的技术，如图3 - l 所示。 ( 2 ) 转台拼接技术在视觉测量系统的应用 转台拼接因其可以灵活转动物体、减少测量死角而广泛应用于视觉测 量系统中。以下就线结构光测量系统为例介绍转台拼接技术的应用， 线结构光视觉测量系统“”由转台、三维运动机构和线结构光测头组成。 转台与置在其上的物体