（水利工程专业论文）逆向工程中点云数据分区的算法研究.pdf

华北水利水电学院工程硕上学位论文 逆向工程中点云数据分区的算法研究 摘要 随着现代工业的发展，对逆向工程( r e v e r s ee n g i n e e r i n g r e ) 技术有着迫切的需 求。所谓逆向工程就是指按照现有零件的模型或实物，利用数字化技术，构造c a d 模型 的过程。其中点云数据分区是其关键和难点问题。 本文分别利用模糊聚类( f c i ) 、自组织特征映射神经网络( s o f m ) 和它们的组合算 法进行分区，选用点云的位置矢量、法向量、平均曲率和高斯曲率作为输入向量，采用 加权距离取代传统的欧氏距离。通过实验对三种方法的有效性、抗噪性和效率进行了对 比。实验结果表明：三种算法均可以实现自动分区，其中模糊聚类算法的有效性和抗噪 性最佳，效率也较高。 本文主要成果如下： ( 1 ) 实现了基于模糊聚类的点云数据分区。 ( 2 ) 实现了基于自组织特征映射神经网络的点云数据分区。 ( 3 ) 实现了基于f c m 与s o f m 组合方法的点云数据分区。 ( 4 ) 对3 种分区方法的性能进行了比较，分析了各自的优缺点。 关键字：逆向工程，模糊聚类，神经网络，f c m ，s o f m ，点云数据分区 逆向工程中点孟数据分区的算法研究 a l g o r i t h ms t u d yo ft h ep o i n t - c l o u dd a t as e g m e n t a t i o n i nr e v e r s e e n g i n e e r i n g w i t ht h ed e v e l o p m e n to fm o d e r ni n d u s t r y , t h ea p p l i c a t i o no fr e v e r s ee n g i n e e r i n gi n c k o | c 心嚏b e c o m e sw i d e ra n dm o r ei m p o r t a n tt h a ne v e t r e v e r s ee n g i n e e r i n gi sak i n do f c a dm o d e w h i c ht a k e su s co fd i g i t a lt e c h n o l o g ya n dc o n s t r u c t sp a r t sp r o t o t y p ea c c o r d i n gt o t h es h a p eo f 商罟i n a lp a r t so ro b j e c t a st h ek e yt e c h n o l o g y , t h ep o i n t - c l o u dd a t as e g m e n t a t i o n i sq u i t ed i f f i c u l ta n dh o tf o r t h ep e o p l ei nt h er e s e a r c ho fr e v e r s ee n g i n e e r i n g 1 1 l i sa r t i c l ec a i r i e so u tt h es e g m e n t a t i o n si st h r o u g ht h ef u z z yc - m e a n s ( f c m ) ，t h e s e l fo r g a n i z ef e a t u r em a p ( s o f m ) ，a n dt h ec o m b i n a t i o na l g o r i t h mo ff c ma n ds o f m ， r e g a r d st h ec o o r d i n a t eo ft h ed a t ap o i n t , n o r m a lv e c t o r , a v e r a g ec u r v a t u r ea n dg a u s s c u r v a t u r ea s i n p u tv e c t o r , a n d t a k e st h ep l a c eo ft r a d i t i o n a le u c l i d d i s t a n c ew i t h w e i g h t e d d i s t a n c e t h r o u g h t h e e x p e r i m e n t s ，t h ec o m p a r i s o n s a r ec a r r i e do u ti n a c c u r a c y a n t i n o i s e e f f i c i e n c ya m o n gt h et h r e ea l g o r i t h mm e t h o d sa b o v e n 忙r e s u l to ft h e e x p e r i m e n t si n d i c a t e st h a tt h et h r e ek i n d so fa l g o r i t h mm e t h o d sc a ns e g m e n ta u t o m a t i c a l l y , a n dt h ea c c u r a c y a n t i - n o i s eo ft h ea l g o r i t h mm e t h o do ff c mi st h eb e s ta n dt h ee f f i c i e n c yo f i ti sb e t t e ra n m n gt h e m f r o mt h ew o r k , w eg e tf o l l o w i n ga c h i e v e m e n t s ： ( 1 ) r e a l i z e st h ep o i n t - c l o u dd a t as e g m e n t a t i o nb a s e do nt h ef u z z yc - m e a n s ( f c m ) ( 2 ) r e a l i z e st h ep o i n t - c l o u dd a t as e g m e n t a t i o nb a s e do ns e l fo r g a n i z ef e a t u r em a p ( s o f m ) ( 3 ) r e a l i z e st h ep o i n t - c l o u dd a t as e g m e n t a t i o nb a s e d0 1 1t h ec o m b i n a t i o no ff c m a n d s o f m ( 4 ) c o m p a r e sc h a r a c t e r i s t i c so ft h et h r e ek i n d so fa l g o r i t h mm e t h o d s ，a n a l y z e st h e m e r i t sa n dd e m e r i t so ft h e m k e yw o r d s ：r e v e r s ee n g i n e e r i n g , f u z z yc l u s t e r i n g , n e u r a ln e t w o r k , f c m ，s o f m ， p o i n t - c l o u dd a t as e g m e n t a t i o n 2 华北水利水电学院工程硕上学位论文 主要符号说明 第f 个样品第，个变量的观测值记为； 第j 个变量的平均值； 任意样本屯对i 类的隶属度； 第k 个样本到第f 类聚类中心的距离； 权重指数； 阈值； 最大迭代步数： 初始化隶属度矩阵： 聚类中心； 平均曲率； 高斯曲率； 法向量的权值； 曲率的权值； 输出神经元，与输入层单元i 之间的连接的权值； i 神经元的输出； 激发函数； 时刻； 学习效率； 总的学习次数； 学习速度函数； t 时刻输入层第f 个神经元的输出； 输入节点与每个输出神经元节点连接权矢量的距离； 能量函数； 可一_ 如腕。，日k 4口呦姐肌，嘶r俐埘面刚 独立完成与诚信声明 本人郑重声明：所提交的学位论文，是本人在指导教师的指导下，独立进行研究 工作所取得的研究成果并撰写完成的。没有剽窃、抄袭等违反学术道德、学术规范的侵 权行为。文中除已经标注引用的内容外，本学位论文中不包含其他人或集体已经发表或 撰写过的研究成果，也不包含为获得华北水利水电学院或其它教育机构的学位或证书所 使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确的说明 并表示了谢意。本人完全意识到本声明的法律后果由本人承担。 学位论文作者躲韩号、三 签字眺口- 7 盯，活 保证川导师燧名汤1掷期。7 咖 学位论文版权使用授权书 本人完全了解华北水利水电学院有关保管、使用学位论文的规定。特授权华北水 利水电学院可以将学位论文的全部或部分内容公开和编入有关数据库提供检索，并采用 影印、缩印或扫描等复制手段复制、保存、汇编以供查阅和借阅。同意学校向国家有关 部门或机构送交论文原件或复印件和电子文档。( 涉密的学位论文在解密后应遵守此规 定) 学位敝储妊韩专三导师虢学位论文作者签名：珲书寰三 导师签名： 签字日期： 口7 口岁汐 签字日期： 钏锄 1 。6 | 华北水利水电学院工程硕上学位论文 1 1 逆向工程的概述 1 绪论 制造业作为一个国家支柱性产业，如何面对日趋激烈的国际竞争，不仅关系到企业 的生死存亡，而且事关一个国家的持续发展和综合国力的提高。创新是制造业发展的主 旋律，只有重视新产品开发、增强市场竞争能力，我国制造业才能在经济全球化竞争中 立于不败之地。 为缩短新产品开发周期、提高产品的设计和制造质量、增强企业对市场的快速响应 能力，一系列新的产品快速开发技术应运而生，如c a d c a m c a e 技术、逆向工程技术、 快速成型技术、快速模具技术、虚拟设计技术以及并行工程等。其中，逆向工程( r e v e r s e e n g i n e e r i n g ，r e ) 技术历经几十年的研究与发展，已经成为新产品快速开发过程中的核 心技术，它与计算机辅助设计、优化设计、设计方法学等有机组合构成了现代设计理论 和方法的整体。 在新产品快速开发过程中，前面提到的所有先进技术与思想都建立在计算机辅助 ( c a x ) 技术基础之上。其中，产品数字模型( c a d 模型) 是连接这些先进技术的纽带，如何 快速获得产品c a d 模型对于实现产品快速开发具有重大意义。随着计算机、测量技术的 高速发展及逆向工程中新原理、技术的不断引入，计算机辅助逆向工程技术( c o m p u t e r a i d e dr e v e r s ee n g i n e e r i n g ，c a r e ) 在产品数字化建模过程中越来越受到人们重视 传统的产品开发过程遵从正向工程( 或正向设计) 的思维进行，是从收集市场需求信 息着手，按照“产品功能描述( 产品规格及预期目标) 至产品概念设计至产品总体设计及 详细的零部件设计至制定生产工艺流程至设计、制造工夹具、模具等零部件加工及装配 至产品、检验及性能测试”这样的步骤开展工作，是从未知到己知、从抽象到具体的 图1 - 1 正向工程流程图 f i l l - 1 f o r w a r de n g i n e e r i n gf l o wc h a r t 逆向t 程中点云数据分区的算法研究 过程，正向工程基本流程图如图卜i 所示。 然而在产品开发和制造过程中，有许多产品最初并不是由计算机辅助设计( c a d ) 模 型描述的，设计和制造者面对的是实物样件。为了利用先进制造技术，需要通过一定途 径将实物样件转化为c a d 模型，这种从实物样件获取产品数学模型，进而开发出同类的 先进产品的技术就是“逆向工程”( r e v e r s ee n g i n e e r i n g 缩写为r e ) ，或称反向工程、 反求工程等“埘逆向工程是一个与正向工程相反的过程。逆向工程是近年来发展起来 的引进、快速消化、吸收和提高先进技术的一系列分析方法和应用技术的组合。它以已 有的产品或技术为研究对象，以现代设计理论、生产工程学、材料学、计量学、计算机 技术及计算机图形学和有关专业知识为基础，运用设计人员的工程设计经验和创新思 维，以解剖、掌握对象的关键技术为目的，最终实现对研究对象的认识、再现及创造性 地开发。也就是说逆向工程是指在没有设计图纸及c a d 模型的情况下，按照现有零件的 模型或实物，利用各种数字化技术形成一系列的空间离散点，即“点云”数据，然后应 用计算机辅助设计的有关技术，构造零件原形的c a d 模型，逆向工程基本流程图如图卜2 所示。 图卜2 逆向工程流程图 f i g 1 - 2 r e v e r s ee n g i n e e r i n gf l o wc h a r t 在很多场合下产品的初始信息状态不是c a d 模型，而是各种形式的物理模型或实物 样件，若要进行仿制或再设计，必须对实物进行三维数字化处理，数字化手段包括传统 测绘及各种先进测量方法，将获得的三维离散数据作为初始素材，借助专用曲面处理软 件和c a d 系统构造实物的c a d 模型，利用输出的n c 加工指令或s t l 文件驱动n c 或快速成型 机制造出产品或原型。 一般意义上，逆向工程( 亦称反向工程、反求工程) 指的是针对已有产品原型，消 化吸收和挖掘蕴含其中的涉及产品设计、制造和管理等各个方面的一系列分析方法、手 段和技术的综合。它以产品原型、实物、软件( 图纸、程序、技术文件等) 或影像( 图片、 照片等) 等作为研究对象，应用系统工程学、产品设计方法学和计算机辅助技术的理论 华北水利水电学院工程硕士学位论文 和方法，探索并掌握支持产品全生命周期设计、制造和管理的关键技术，进而开发出同 类的或更先进的产品。广义逆向工程的研究内容十分广泛，概括起来主要包括产品设计 意图与原理的逆向，美学审视和外观逆向、几何形状与结构逆向、材料逆向、制造工艺 逆向及管理逆向等诸多方面，是一个复杂的系统工程。自2 0 世纪6 0 年代逆向工程的概 念产生以来，经过几十年的研究和实践，逆向工程的内涵与外延都发生了深刻变化。目 前逆向工程的研究集中在几何形状逆向，即几何模型重建( r e c o n s t r u c t i o n ) 方面。狭义 的逆向工程，也就是几何形状逆向，可以看作一种自动化、智能化几何模型造型方法。 当今的时代己经是信息对代，全球统一市场逐渐形成，这加剧了世界市场的竞争， 使得市场对产品的价格和性能更为敏感，产品的生命周期变得越来越短，产品的更新换 代频繁，生产批量减小。如何降低成本高效率地开发出新产品，己成为赢得市场竞争的 首要因素。逆向工程技术作为消化吸收先进技术和产品快速开发的重要支撑技术，已成 为制造业关注的热点。 1 2 逆向工程的关键技术 在对实物模型的几何形状进行逆向的过程中，最终希望建立已有样件的数字化实体 模型。逆向工程一般可以分为五个步骤嘲：1 ) 数据测量：2 ) 数据预处理；3 ) 数据分 区与曲面重构；4 ) 建立c a d 模型；5 ) 重构模型后处理等五个步骤。 1 2 1 数据测量 数据测量是逆向工程c a d 建模的首要环节。数据测量方法主要依据测量设备( 数字化 测量仪) 的不同而不同。目前逆向工程所采用的数字化测量仪主要有机械接触式坐标测 量机、光学坐标测量机、激光坐标测量机。根据不同的测量设备以及获取数据的不同方 法，我们可以把测量分为接触式和非接触式两大类。 按照测量数据的组织方式可将测量数据分为四类：( 1 ) 散乱数据：测量点没有明 显的几何分布特征，呈散乱无序状态；( 2 ) 扫描线数据：测量数据由一组扫描线组成， 扫描线上点在扫描平面内有序排列；( 3 ) 网格化数据：点云中所有点都与参数域中一 个均匀网格的顶点对应；( 4 ) 多边形数据：测量点分布在一系列平行平面内，用小线 段将同一平面内距离最小的若干相邻点依次连接可形成一组有嵌套的平面多边形 逆向t 程中点数据分区的算法研究 1 2 2 数据的预处理 由测量设备采集的数据点通常比较密集，因而形象地称作点云( p o i n tc l o u d ) ，点 云可分为有序点云和散乱点云。为了消除误差对后序建模的影响，有必要对测量的“点 云”数据进行预处理。目的是获得完整、正确的测量数据以方便后续的造型工作。对测 量点云数据进行的预处理一般包括：异常点处理、数据平滑、多视拼合、数据精简等。 异常点处理是指处理数据中的“跳点”和“坏点”。“跳点”通常是由于测量设备 的标定参数发生改变和测量环境突然变化造成的，在手工测量时，还可能是由于操作误 差形成的。因此，数据预处理要先从点云中找出可能存在的“跳点”，并对其进行处理。 数据平滑即是要对“点云”进行平滑、滤波。由于实际测量过程中受到各种人为和 随机因素的影响，使得测量结果包含噪声。为了降低或消除噪声对后续建模质量的影响， 有必要对测量点云进行平滑滤波，数据平滑通常采用高斯、平均或中值滤波。 在逆向工程实际过程中，由于众多的激光扫描设备的局限性，要获得物体的完整采 样，从一个方向进行采样是不可能的，在扫描过程中，需要调整物体位置或者旋转激光 头的角度，从多个方向对物体进行扫描，得到多张视图数据，然后通过点的聚合，对它 进行拼接，从而得到完整的采样数据点集。多视拼合的任务就是将多次装夹获得的测量 数据融合到统一坐标系中。 随着测量设备的发展，测量效率得到了极大的提高，因此在测量过程中，得到了包 含样件更多细节特征的大量数据，在此数据中存在大量的冗余数据。如此庞大的数据量， 会严重影响后序建模的效率和质量，因此在满足建模质量的条件下，要对数据进行精简， 以减少数据的处理量。 1 2 3 数据分区与曲面重构 在进行c a d 造型之前还要进行的一个重要的工作是数据分区( s e g m e n t a t i o n ) 。数 据分区是将点云数据分割成属于不同曲面片的数据子集。在逆向工程中，产品表面往往 无法由一张曲面进行完整描述，而是有多张曲面片组成，因而必须将测量数据进行分区， 然后对各数据分别构造曲面模型。 4 华北水利水电学院工程硕上学位论文 曲面重构的目的是要满足精度和光顺性的要求，并与相邻的曲面光滑拼接的曲面模 型。根据曲面拓扑形式的不同，可以将曲面重构方法分为两大类：一是基于四边域网格 曲面重构，它主要面向有序数据点的曲面重构，其中n u r b s 方法作为流行的四边域曲面 重构技术，已经成为产品外形几何定义的工业标准；二是基于三角域曲面重构，它是面 向散乱数据点的曲面重构。 1 2 4c a d 模型构造 若用完整的面、边、点信息来表示模型的位置和形状，由于重构的曲面之间可能存 在着裂缝，或者缺少曲面边界信息等因素，使得表示产品模型的几何信息和拓扑信息不 完整。因此必须使用其它的手段对c a d 模型构造，比如利用延伸、求交、裁剪、过渡、 缝合等信息的高级计算功能，建立模型完整的面、边、点信息。 1 2 5 重构模型后处理 重建模型中由于受数据测量误差、以及数字误差和逼近等若干不精确因数的影响， 经过逆向工程的各个环节，获得的是一个近似于物理对象的数字模型。对于模型中潜在 的结构规律，在重构模型中则只能被近似地表现。而对于面向再设计应用，这种潜在的 规律应该精确的体现出来，所以必须对重构模型进行后处理。 1 3 逆向工程的应用 逆向工程作为一种新的设计方法和理念，在实际中有着广泛的应用，主要表现为以 下一些方面： 1 在缺乏二维设计图纸或者原始设计参数情况下，需要将实物零件转化为计算机表 达的c a d 模型，以便充分利用现有的计算机辅助分析( ( c a e ) 、计算机辅助制造( ( c a m ) 等 先进技术。 2 复制产品。某些情况下，需要对某一产品进行复制，但又没有其图纸或c a d 数据。 用传统的方法完成测量和重画需要花费很多时问，对于具有复杂自由曲面产品的复制更 为困难。逆向工程处理这种情况非常适合。 3 还原产品。某些大型设备，如航空发动机、汽轮机组，常会因为某一零部件的损 5 逆向丁程中点孟数据分区的算法研究 坏而停止运行，通过逆向工程手段，可以快速生产这些零部件的替代件。 4 改进产品。借鉴别人的成功设计，进行再创新设计是在激烈竞争中赶超同行先进 水平的一个捷径。 5 试验产品。有些零件有较高的美学、空气动力学要求，难以在计算机上直接造型。 设计时往往首先制作比例模型，然后进行各种实验，如风洞实验等一旦外形确定，需要 使用逆向工程技术将其转化为c a d 模型。 随着逆向工程技术的不断发展，其应用的领域已相当广泛。除了在机械领域内包括 汽车、航空、家电等的广泛应用，在其它工程学科中，逆向工程也得到应用。在医学领 域，人工关节的成功设计和制造需要对周围骨骼的精确认识和数字化c a d 模型，使用c t 技术可以得至出骨骼结构的轮廓，然后重构出曲面模型供人工关节设计使用。在虚拟现实 研究中，逆向工程还可以用来构造虚拟环境，通过数字化和c a d 建模可得到物体的数学 表示，以创造一个更真实且细腻的虚拟世界。 逆向工程是一个很有前途的技术方向。逆向工程软件正在向集成化的逆向工程软件 系统方向发展。有望以软件的智能化来减少或取代人工干预的影响。逆向工程软件最终 会实现r e r p 之间的信息集成和系统集成，从而形成一个集设计、制造、检测于一体的 快速反馈设计系统，这将是未来制造业技术的一大发展方向。 1 4 本文内容及结构 本文主要研究逆向工程中点云数据分区的方法。研究了基于模糊聚类( f c l i ) 的点 云数据分区、基于自组织特征映射神经网络( s o f m ) 的点云数据分区，以及将模糊聚类 ( f c m ) 与自组织特征映射神经网络( s o f m ) 组合的点云数据分区，并对三种分区方法 的正确性、分区速度和抗噪性进行比较。 本文共有六章，第l 章介绍了逆向工程的原理、关键技术及逆向工程的应用。 第2 章介绍点云数据的分区方法，主要介绍自动分区方法中基于边的分区方法、基 于面的分区方法和基于聚类的分区方法，以及各种方法的优缺点。 第3 章是模糊聚类( f c m ) 及基于f c m 的点云数据分区。介绍了聚类的基本知识、 基本参数，模糊c 均值( f c m ) 算法的原理和算法流程，讨论了基于f o i 的点云数据分 区的方法、过程及优缺点。 6 华北水利水电学院工程硕土学位论文 第4 章是自组织特征映射神经网络( s 0 刚) 及基于s o f m 的点云数据分区。介绍了 神经网络的基本知识、学习方法和竞争原理，自组织特征映射( s o f m ) 的结构、原理和算 法，讨论了基于s o f m 的点云数据分区的方法、过程及优缺点。 第5 章尝试用f c m 与s o f m 组合的方法进行点云数据分区。介绍了f c m 与s o f m 相结 合的算法、流程，讨论了该算法中一些参数的选择、算法的改进以及该算法的优缺点。 第6 章通过实例对这三种方法的分区质量进行比较，如分区的正确性、分区速度和 抗噪性。 逆向下程中点云数据分区的算法研究 2 1 概述 2 点云数据分区 逆向工程的目标是根据离散的数据点集构造出分段、光滑的c a d 模型。实际的产品 中，只由一张曲面构成的情况不多，产品形面往往由多张曲面混合而成，因此点云数据 分区与曲面重建技术是逆向工程的关键技术。 无论是通过三维坐标测量仪还是激光扫描仪，将物体数字化后得到的是一大批的数 据点云，数目庞大，不便于直接进行曲面拟合；实际的曲面模型往往含有多个曲面几何 特征，如果利用“点云”数据直接进行拟合，则造成曲面模型的数学表示和拟合算法处 理的难度加大，甚至无法用较简单的数学表达式描述曲面模型。所以在进行模型重构之 前必须对数据进行数据分区。 目前逆向工程中，一般是按照原型所具有的特征将数据点划分成具有单一几何特征 的拓扑结构区域分别拟合出不同的曲面片，然后应用曲面片求交或曲面问光滑过渡等方 法，将不同的曲面片拼接起来构成一个整体，最后，通过曲面间的几何、拓扑运算构建 c a d 模型。每个拓扑区域主要包含几何信息、拓扑信息包两方面信息，在重构盐面或曲 面局部修改时，能用简单的数学模型表示，而且能提高曲面模型重构效率。因此，点云 数据分区是曲面重构中的关键环节之一。点云数据分区作为此求解策略中的关键步骤， 其效率和精度直接决定了模型的质量。 2 2 国内外研究动向 2 2 1 国外研究动向 国外对点云数据分区的研究较多，其代表人物有：匈牙利计算与自动化研究院几何 造型实验室的v d r a d y 和b e n k o 、德国c h e m n i t z 技术大学的g a n c o 等。代表性研究：t a i 等 提出了基于设计思想的点云数据预处理算法；b a n k o 等提出了一种直接分割法，利用特 征曲面的几何特性在分割的过程中动态识别区域的特征类型。f l o f f m a n 和j a i n 把图像划 分为多个面片，并把这些面片归类为平面，凸面和凹面形状，然后进行曲率值和边界值 分析；采用了数据点的坐标和法向量六维特征向量实现聚类分区；k o h o m e 模仿大脑皮层 8 华北水利水电学院工程硕士学位论文 的结构特点提出了自组织神经网络；j e a n - k 取坐标、法向量和平均曲率、高斯曲率八维 特征向量，通过多层自组织特征映射神经网络实现对深度图像进行数据分区。 2 2 2 国内研究动向 国内方面，西安交通大学的何炳蔚和林志航，根据线激光测量方式和三维点群分布 的特点，通过树形的空间结构完成对密集散乱点群空间分割，由此实现对散乱点群数据 的几何分区。 f a n 州等用局部曲面曲率性质来识别点数据域的明显边界；c h e n 和l i u 嗍用切片的方 法划分c 删数据点区域，并把切片所得的数据拟合成二维n u r b s 样条曲线，最后通过计 算n u r b s 曲线的最大曲率的方法来识别边界点；y a n g 和l e e 嗍认为边界点具有曲率极值， 于是首先估算曲面曲率获取边界点，在获得边界点后，然后提出邻域边链的算法来构建 边界曲线。刘胜兰”1 提出的三角网格模型区域分割方法，取一个三角片作为生长点，沿 着边界向外扩展“生长”，将具有相同类型的三角片组成一个连通的块；柯映林闻提出 建立基于空间栅格的边界提取模型，通过边界栅格识别和生长算法以及空间拓扑构型推 理算法，实现从点云数据中直接获取边界信息，实现点云的区域分区。为了提高参数化 建模的效率，柯映林还提出一种基于微分几何量统计分析的区域自动分区算法 上海交通大学的史桂蓉和胡鑫采用两阶段学习算法，首次将神经网络方法用于“点 云”数据分区，利用自组织特征映射神经网络( s e l f - o r g a n i z i n gf e a t u r em a p s 0 f m ) 实现无监督的特征聚类，利用s o f m 的无监督聚类特性根据特征向量的内在相似性实现自 动的数据区域分区。 刘雪梅老师分别利用s o f m ”1 、m l s o f m 叫实现逆向工程中点云数据分区，通过改进s o f m 网络初始权值方法以及引进能量函数控制迭代次数，提高了s o f m 的分区效率。 从国内外研究动向及进展可以看到神经网络在点云数据的区域分割中发挥着很大 的作用，但是神经网络存在一些缺陷：正确率低、抗噪性不好。所以怎样保证正确率、 提高分区的抗噪性，本文研究了逆向工程中基于f c m 和s o f m 组合的点云数据分区的方 法。 2 3 点云数据分区方法“1 9 逆向丁程中点i 数据分区的算法研究 c a d 模型重建一般是通过插值或拟合一系列离散点，利用原型的几何及拓扑信息构 建一个近似模型来逼近原型。而大多数机械零件产品都是按一定特征设计制造的，产品 表面往往不是由单张曲面构成，而是由大量初等解析曲面( 如平面、圆柱面、圆锥面、 球面等) 及自由曲面组成，因此，需要将测量数据分割成具有各个相似几何曲面特征的 子域数据，识别子域数据隐含的产品几何特征参数，从而完成曲面特征重建。 点云数据分区亦称区域分割，就是将点云数据转变为具有不同特征的区域数据，将 测量数据划分为特征单一、互不重叠的区域。把要进行几何建模的数据集r 细分为多个 子集尺，r 2 , ，月h 使r 可以用一个曲面方程表达。 目前，点云数据分区方法有基于测量的分区和自动分区两种方法，其中自动分区是 常用的方法。自动分区按数据分区大体可以分为基于边( e d g e - b a s e d ) 的方法，基于面 ( f a c e - b a s e d ) 的方法和基于群簇( c l u s t e r i n g - b a s e 功的方法。 2 3 1 基于边的分区方法 基于边的分区方法是试图找到曲面边界上的点，构成曲面片的边，边相互连接形成 的封闭区域就是砸。基于边的分区方法是从纯数学的理论出发，首先从数据点集中，根 据组成曲面片的边界轮廓特征、两个曲面片之间的相交、过渡特征，以及形状表面片之 间存在的棱线或脊线特征，确定出相同类型曲面片的边界点，连接边界点形成边界环， 将封闭边界包围的区域作为最终的分区结果，把整个数据集分割为独立的多个点集，从 而实现数据分区。基于边的分区方法根据边检测方案的不同可以分为边操作法、边区域 法和曲面曲率法分割。 各种基于边的区域分割方法的区别主要在于特征线提取的规则不同，已有的特征线 提取规则很多，例如：基于曲率极值的；基于平面度的；通过在局部范围内拟合曲面的， 每一种规则有一定的适用范围，可以处理特定的情形。 基于边界的分区方法的主要优点是可以非常方便地根据点、线以及面的连接关系确 定模型的拓扑结构；基于边的分区方法可有效实现具有棱边的点云数据分块。但由于基 于边的分区方法，只用到点云中边界附近的数据，点云中的大量数据没有用到，所以这 种方法易受到测量噪声的影响，对噪音数据和计算误差敏感。基于边的分区方法，容易 产生对点的错误跟踪，不能完成保证构成封闭的区域。由于以上原因，限制了该方法的 发展。 1 0 华北水利水电学院工程硕上学位论文 2 3 2 基于面的方法”m 基于面的方法是试图找出相互邻接、具有相同特性的点( 如平面的法矢相同，球面 的曲率相同) ，将它们归属于一个面，边界可由面的相交或其它方法获得。基于面的分 区是根据指定的曲面方程拟合数据点集，将具有相似几何特征的空间点划分为同一区 域，此过程是一个迭代的过程。其迭代过程可以分为自底向上( b o t t o m - u p ) 、自顶向 下( t o p - d o w n ) 两种分法。 自底向上的区域分区方法以若干个简单表面片作为种子区域，首先选取一个种子点 ( s e e dp o i n t s ) ，从种子点开始根据表面片的微分几何性质来判断其周围的数据点是 否属该表面片，将与之有相似几何性质的点划入该种子区域，并更新与种子区域对应的 表面片的类型；而后基于给定的相容阈值，直到在其邻域不存在连续的点集为止，最后 将这些小区域( 领域) 组合在一起得到相关的区域。自底向上当在该表面片周围没有几 何性质一致的时候，种子区域停止生长。但应用该方法时须注意以下几个问题：( 1 ) 种子区域的选择与分布，这将影响到分区计算的效果与效率；( 2 ) 在区域生长过程中， 区域的类型可能发生变化，因此要判断出与当前区域对应的表面类型；( 3 ) 采用何种 依据来判断测量点是否属于一个区域将产生不同的分区结果。这些问题造成了分区算法 的复杂性。 自顶向下的分区方法：首先假设所有的数据点属于同一个表面区域，然后根据提出 的性能指标做统计分析，进行假设检验，若假设成立，则分区结束；否则，将数据点集 进行划分，并对各个子集重新做假设检验，直至各个区域满足性能指标。应用该方法存 在的问题是：( 1 ) 子区域划分方法的选择，如采用四叉树等分区方式，有时会产生过 分割的结果，此时需作反向的融合过程；( 2 ) 如将区域表面拟合的精度作为依据，则 在每次分区后，测量数据点需重新参数化，使整个过程计算量增大。 基于面的方法有更好的稳定性，分区依据具有明确的几何意义，因而应用更为广泛， 是目前较为常用的分区方法。基于面的方法是找出光滑的曲面域，这种方法要用到点云 中的所有数据，所以分区结果受噪声的影响小、可靠性高，分区结束后各个区域之间的 关系也随之确定。但基于面的分区法无法直接得到模型的拓扑结构，模型的拓扑结构需 要根据曲面拟合结果通过曲面求交得到，从而带来一些不确定性，增加了处理的难度。 逆向下程中点云数据分区的算法研究 在含噪声数据和曲率估算的基础上，选择合适的分裂或合并标准是至关重要而又十分困 难的，如何准确地估算出分片连续曲面的曲率是基于面分割方法的瓶颈。 为了克服以上两种方法的限制，有研究人员将基于边和基于面的两种方法相结合： 先提取一些边界线，然后寻找一些“生长点”，当区域生长至边界线处就停止。 2 3 3 基于群簇的分区方法 基于群簇的分区法，即聚类方法( c l u s t e r i n g ) 是通过聚类技术把局部几何特征参数 相似的数据点聚集为一类。基于群簇的分区方法是将几何特征应作为输入向量，设计基 于向量量化的数据分割算法。为了反映点的位置和拓扑信息，特征向量包括位置向量、 法向量和曲率。首先选择特征向量，在分区之前，必须计算出每一点的法向量、高斯曲 率和平均曲率等几何量。 基于群簇的分区方法的主要优点是使分区法的有效性不必依赖复杂的判断控制机 制。但在基于群簇的分区法中，向量的量化容易造成位置上的不连续，选取坐标和法向 量六维特征向量容易出现细碎面片，往往要对碎片进一步处理。到目前为止，大多采用 单层的s o f m 网络。单层s o f m 网络的主要缺点是分区数目( 输出节点的数目) 需要预先给 出，然而分区数目取决于不同的处理对象，这使得单层的s 0 f m 网络在用于数据分区时 有很大的局限性。 基于边的分区方法、基于面的分区方法和基于群簇的分区方法各有其优缺点，因此， 许多研究方案将三者结合起来目的是综合三种方法的优点来提高区域分区的准确性。 本文研究了基于模糊聚类( f c w ) 分区方法、基于自组织特征映射神经网络( s o f m ) 的分区方法，实现了模糊聚类( f c m ) 分区和自组织特征映射神经网络( s o f m ) 组合的 点云数据分区方法。 华北水利水电学院工程硕士学位论文 3 模糊聚类( f c m ) 及基于f c m 的点云数据分区 3 1 聚类基础知识 3 1 1 聚类分析概述 “聚类( c l u s t e r i n g ) ”，顾名思义是要将相近或相似的对象聚成类。聚类是一个 将一群( s e t ) 物理的或抽象的对象，根据它们之间的相似程度，分为若干组( g r o u p ) ，其 中相似的对象构成一组，这一过程就称为聚类过程。聚类分析是非监督模式识别的一类 重要方法，它按照某种相似性度量，将样本空间划分成不同的类别。 从某种意义上看，聚类分析可以这样定义：将一组数据分组，使其具有最大的组内 相似性和最小的组问相似性，也就是说，最后的结果要达到不同聚类中的数据尽可能地 不同，同一聚类中的数据进尽可能地相似。相似或不相似的度量通常就是利用( 各对象 间) 距离来进行描述的，从模式识别或空间的角度来看，对象就是数据点。为此需要确 切地描述和度量有关属性，并从中比较对象间的相似程度，把最接近的对象归并成类。 人们对聚类的研究已经有相当长的历史。1 9 6 3 年，由r o b e r ts o k a l 和p e t e rs n e a t h 合著的 p r i n c i p l e so fn u m e r i c a lt a x o n o m y 一书对聚类的研究起了很大的推动和促 进作用。数据聚类分析是一个正在蓬勃发展的领域。聚类分析所涉及的领域包括：数据 挖掘、统计学、机器学习、空间数据库技术、生物学和市场学等。由于各应用数据库所 包含的数据量越来越大，聚类分析已成为数据挖掘研究中个非常活跃的研究课题。 3 1 2 中心化变换 设聚类问题中有口个样品( 个体) ；x ；- o ，x ：，) ，对每个样品选择了於变量， 用间隔尺度测定后，第外样品第j 个变量的观测值记为勘，则棚、样品所有p 个变量的观 测值可排成如下矩阵： 逆向t 程中点。数据分区的算法研究 石一 x l lx 1 2 x 2 l 工 x lj 。2 ( 3 1 ) 式( 3 - 1 ) 称为样本数据矩阵。其中第价样品口个变量的观测值为向量x 可记为： 而一g j l t 2 ，石* ) 7 为了确保各变量在分析中的地位相同，可以对数据进行中心化与标准化变换。数据 变换将施于每个变量在各个样品上的观测值，通常是在观测值上减去相应变量的平均 值，记第j 个变量的平均值为： 巧言砉勃卢l 加二p ( 3 - 2 ) 第外变量打个数据实施中心化变换： x ；一x q x l i 2 】，2 ，1 73 - 3 ) 经此变换后各个变量的均值将为0 ，即各变量的取值都有相同的基点。 3 1 3 标准化变换 所谓标准化是在中心化的基础上再作交换，它要使各种变量的变化范围相等。内用 不同的方法衡量变化范围时，就有不同的标准化变换方法。常用的标准化方法有1 ： 1 标准差标准化 记第j 个变量的标准差为： 卟两 则下式表示对第j 个变量疗个数据实施标准差标准化： 牛等 经变换后各变量的均值为0 ， 2 极差标准化 记第外变量的极差为： i = 1 2 n 标准差均为1 。 1 4 ( 3 4 ) ( 3 5 ) 如；如 华北水利水电学院工程硕士学位论文 r j m a x 瓴，) 一m i n 阮) h l d 鄱 则下式表示对第j 个变量疗个数据实施极差标准化： v x t i x i 如f 经变换后各变量的均值为0 ，标准差均为1 。 3 极差正规化 它的变换式为； x l i - - m i n ( x i j ) 蜀- 1 尹一 经标准化变换后，各变量基点相同，变化范围也相等了。 3 1 4 距离 ( 3 - 6 ) ( 3 - 7 ) ( 3 8 ) 为了度量分类对象之间的接近与相似程度，需要定义一些分类统计量，用作分类的 数量指标，从而可以定性地进行分类。距离是聚类分析常用的分类统计量，对于有阶 变量的样品来说，玲样品可以视为p 维空间中的厅个点，常用缘示第价样品与第。p 个 样品间的距离。作为点间距离应满足以下条件： ( 1 ) 非负性。即对所有的拜日恒有以o 。同时，当且仅当两个样品的p 个变量 对应相等时，其等式才成立。 ( 2 ) 对称性即对所有的瘌工恒有d i _ 以。 ( 3 ) 满足三角不等式。即对所有的j 、j 和盘恒有函d d j 。 聚类问题实质上是一个优化问题，即通过一种迭代运算使得系统的目标函数达到一 个极小值，该目标函数为评价函数。通常采用距离作为评价的划分标准，在聚类分析中， 最常用的有以下距离伽，名氏( h a m m i n g ) 距离： of d e 国) 一( 艺防n x 声f ) 石 q 0 ( 3 9 ) 当矿1 时，名氏距离即为绝对距离： 逆向下程中点数据分区的算法研究 嘞( 1 ) 一弘n 一石业 ( 3 一1 0 ) 当q = 2 时，为欧氏( e u c l i d ) 距离： d “c z ，。( 薹伍* 一z 业) 2 ) 7 2 ( 3 - 1 1 ) 当q = 一时，为切比雪夫距离： 如( ) 一m a x , 一x 业l ( 3 1 2 ) 在距离中，通常最著名、最常用的是欧氏( e u c l i d ) 距离，其特点是对坐标进行平 移和旋转之后，欧式距离保持不变，对象仍然保持原来的相似结构。对数值属性主要采 用欧式( e u c l i d ) 距离，而对符号属性则采用h a r m i n g 距离。 3 2 模糊c 均值聚类( f c m ) 3 ，2 1 模糊c 均值( f c m ) 概述 模糊c 一均值( f u z z yc - - m e a n s f c m ) 聚类也被称为k 均值聚类。模糊聚类的思想 来源于r a s p l i 于1 9 6 9 年提出的h c m ( h a r dc m e a n s ) 硬聚类，d u n n 在此基础上把最小方 差聚类过程概括成一种模糊i s o d a t a 聚类方法，并由b e z d e k 等于1 9 8 7 年进行推广。 f c m 是一种基于目标函数和聚类原型的递归算法。它通过将传统的硬c 一均值聚类 ( h a r dc m e a n sc l u s t e r i n g ，h c m ) 的隶属函数的取值由 0 ，1 二值扩展到 0 ， 1 区间，将硬聚类( 一个对象只能被分配到一个聚类，聚类与聚类之间不相互连接， 并且也不相互重叠) 发展为软聚类( 一个对象可以属于多个聚类，允许聚类之间的重 叠，可以找出连接的聚类) ，使得聚类的结果更为合理。其中的c 和k 代表了需要预先 设定的聚类子区间数目，即将所有数据点归于多少个类中。 模糊c 一均值( f c m ) 算法是在数据集的聚类数目已知的情况下，寻找最佳的数据划分， 使得聚类性能指标为最优。硬c 一均值聚类，每个数据项唯一地属于一个聚类中心；模糊 c 一均值( f u z z yc - - m e a n s f c m ) 聚类，每个数据的所属聚类中, bf h 隶属度函数来确定 f c m 用模糊划分，使得每个给定数据点用值在 0 ，1 问的隶属度来确定其属于各个组的 华北水利水电学院t 程顾l ：学位论文 程度。与引入模糊划分相适应，隶属矩阵