《散乱点云的数据分割与特征提取技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
分类号：密级：ＵＤＣ：学号５９２６６１４０６８：４１南昌大学专业学位研究生学位论文散乱点宏的数据分割与特征提取技术研究ＲｅｓｅａｒｃｈｏｎＤａｔａＳｅｍｅｎｔａｔｉｏｎａｎｄＦｅａｔｕｒｅＥｘｔｒａｃｔｉｏｎｇＴｅｃｈｎｉｕｅｓｏｆＳｃａｔｔｅｒｅｄｑ张蓉培养单位（阮、系）；机电工程学院指导教师姓名、职称：吴禄慎教授指导教师姓名、职称：王运霄高级工程师专业学位种类：工程硕±专业领域名称：仪器仪表王程＇论文答辩日期＾；。《６年＾月為日＞答辩委员会卡席：／评阅人：２０１６年户月苗曰 学位论文独创性声明一论文独创植声明、学位本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果，除了文中特别加Ｗ标注和致谢的地方外，论文中不包含。据我所知其他人己经发表或撰写过的研究成果，也不包含为获得南昌大学或其他教育机一构的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名（手写签字日期：年Ｊｒ月＾日二、学位论文版权使用授权书本学位论文作者完全了解南昌大学有关保留、使用学位论文的规定，同意学校有权保留并向国家有关部ｎ或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权南昌大学可Ｗ将学位论文的全部或部分内容编入有关数据库进行检索，可Ｗ采用影印、缩印或扫描等复制手段保存、汇编本学位论社文。同时授权北京万方数据股份有限公司和中国学术期刊（光盘版）电子杂志将本学位论文收录到《中国学位论文全文数据库》和《中国优秀博硕±学位论＂文全文＂数据库》中全文发表，并通过网络向社会公众提供信息服务，同意按章程规定享受相关权益。学签位论文作者签名巧写导师签名字日期年月《日签字日期：刀？！＾备年月遂日论文题画喪也么巧教ｉｉ分書Ｉ為轉ｌＩＩＪｌ故Ｃ刮免辛个论姓名ＳｋＭ－Ｉ学号｜夺巧＾《／如处文级别Ｉ博±＾硕；吕Ｉ院／系／所抓也１铅遂暖专业化ｇ化若王愁ｍＥ＿ａｉｌ备注材卢４开□保密（向校学位办申请获批准为＂保密＂，年＿月后公开 摘要摘要逆向工程作为产品消化、吸收且快速开发的重要途径之一，得到了越来越多的重视。通过逆向工程技术，可用三维扫描仪获得实物的散乱点云模型来重建数字CAD模型。针对复杂模具的散乱点云数据，其数据分割与特征提取技术仍存在着适应性不强、自动化程度不高、计算速度慢及精度不足等问题。本文采用理论与实践相结合的方法从K邻域搜索、微分信息估算、数据分割和特征提取等方面进行理论研究与实验验证。论文主要研究内容如下：1.针对规则栅格搜索点云K邻域时容易遗漏局部特征点的问题，采用一种改进的点云K邻域搜索算法。该算法是在基于规则立体栅格空间划分中融入八叉树思想，根据初划分小立体栅格内的点云数目与引入的“点云阈值”关系自适应确定栅格棱长进行自适应空间二次划分；并以采样点的近似密度自适应确定初始空间球半径r和动态球的外切立方体改进空间球算法，实现自适应搜索采样点的K邻域。2.法向量计算误差往往会给曲率计算带来影响，并且难以估算高曲率区域曲率，本文提出一种基于稳健统计的移动最小二乘曲面计算曲率的方法。该方法通过变窗宽最大核密度估计得到最佳子点集，并以此点集拟合出最优移动最小二乘曲面，计算曲面曲率。3.针对B样条曲线拟合的特征线精度和效果与实物原始特征线偏差较大的问题，对3次B样条构造法进行改进。该改进法是将理论的控制点直接用实际控制点来表示进行插值拟合，并采用积累弦长参数化法求取节点向量，以提高拟合特征线的精度。选择不同K值，角度阈值，获得最优的特征提取效果。4.针对特征区域（高曲率）处数据分割误差大的问题，本文提出一种基于多种聚类相结合的混合分割法。采用改进的K均值聚类算法和基于高斯映射的均值漂移算法分别对点云的平坦区域和特征区域进行分割，对K均值聚类算法加入遗传算法避免分割时陷入局部极值；针对特征区域，利用计算出的单位法向量通过高斯映射，在单位球上形成高斯图，再结合自适应均值漂移法对高斯球进行聚类分割，最后根据高斯图与点云数据的对应关系，由分割后的高斯图实现零I 摘要件点云的分割。5.结合Microsoftvisualstudio2010和OpenGL对上述理论进行程序编写，再分别使用机械类零件与混合型的点云模型为实验对象进行研究，得到了相应的实验结果。分析实验结果，并与其他经典算法进行比较，验证了k邻域搜索、微分信息估算、特征提取和数据分割算法的有效性与适用性。关键词：k邻域搜索；微分信息估算；特征提取；数据分割；聚类算法II AbstractAbstractReverseengineering,asoneofanimportantwayforthedigestion,absorptionandrapiddevelopmentofproducts,hasbeendrawnmoreandmoreattentionrecently.Scatteredpoint-cloudmodelwhichobtainedfrom3DScannercanbeusedtoreconstructCADModelthroughreverseengineering.Regardingtoscatteredclouddataofcomplexmodel,thereisstillinflexible,lowdegreeofautomation,slowcomputationspeedandinsufficientaccuracyissuesfordatasegmentationandfeatureextractiontechnology.ThisthesisdoestheoreticalresearchandexperimentalverificationfromtheaspectsofKneighborhoodsearching,estimationofdifferentialinformation,datasegmentationandfeatureextractionbycombiningtheoryandpracticemethods.Themainresearchcontentsareasfollows:Firstly,animprovedpoint-cloudKneighborhoodsearchingalgorithmisputforwardinthisthesistodealwiththeproblemofeasyleavingoutlocalfeaturepointswhenaregulargridsearchspotsearchesthepointofKneighborhood.Torealizetheself-adaptedsearchinginsamplespots,theoctreethoughtiscombinedinthree-dimensionalgridspacedivisionfirstly.Thentheseconddivisionwillbedonebasingonthenumberofsmallpoint-cloudsoriginallydividedinthree-dimensionalgridandthe‘point-cloudthreshold’todeterminethelengthofrasterLninself-adaptivespace.Also,anapproximatedensityofsamplingpointsareself-adaptedtodeterminetheinitialdynamicradiusranddynamicballcircumscribedcubetoimprovethespaceballalgorithm.Secondly,inmostcases,theerrorsexistedinnormalvectorcalculationhaveimpactontheestimationofcurvature,whichalsomakeitdifficulttoestimatethecurvatureinregionswithhighcurvature.Themovingleast-squaresestimationofcurvaturebasedonrubuststatisticsisputforwardinthisthesistoestimatethecurvature.Throughestimationofthemaximumkerneldensityofvariablebandwidth,theoptionalchildsetofpointscanbegot,whichcanbeusedtofitouttheoptimalmovingleast-squaressurfacetocalculatethecurvatureofsurface.III AbstractThirdly,astheprecisionandeffectofcharacteristicslineofb-splinecurvefittingislargelydeviatedfromtheoriginalphysicalone,thisthesisdiscussesacontrolpointmethodtoconstruct3Bsplinefittingcharacteristicline.Inordertoimprovetheprecisionoffittingcharacteristiclines,theoreticalcontrolpointsaredirectlyinterpolatedwithrealcontrolpoints.AndaccumulatedchordlengthparametricmethodisadoptedtoCalculatethenodevector.ThenChoosingdifferentKvaluesandanglethresholdvaluesgetstheoptimalextractioneffect.Fourthly,thisthesispresentsthemethodofmixedsegmentationwiththecombinationofkindsofclustertohandletheproblemofdatapartitioningerrorwhichoccurredincharacteristicsline(highcurvature).Withtheimprovedk-meansclusteringalgorithmandthemeanshiftalgorithmbasedongaussianmappingrespectivelyontheflatareaandcharacteristicsofpointcloudregionsegmentation,jointhegeneticalgorithmofk-meansclusteringalgorithmtoavoiddividedintolocalminima;Inviewofthecharacteristicsofregional,usingtocalculatetheunitnormalvectorofthegaussmap,ontheunitspheregaussianisformed,combiningadaptivemeanshiftmethodofgaussianclusteringsegmentation,accordingtothegaussmap,thecorrespondingrelationshipbetweenthepointclouddatabygaussianfigureafterthesplitpointcloudsegmentationimplementationpart.Fifth,combinedwithMicrosoftvisualstudio2010andOpenGLprogrammingontheabovetheory,thenusepointcloudmodelofmechanicalpartsandhybridasexperimentalobjecttostudy,thecorrespondingexperimentalresultsareobtained.Analysisofexperimentalresults,andcomparingwithotherclassicalgorithms,verifythekneighborhoodsearch,differentialinformationestimation,effectivenessandapplicabilityofthefeatureextractionanddatasegmentationalgorithm.KeyWords:kNeighborhoodSearch;Differentialinformationtoestimate;Featureextraction;DataSegmentation;ClusteringAlgorithmIV 目录目录第1章绪论.................................................................................................................11.1课题来源.........................................................................................................11.2课题研究意义与背景.....................................................................................11.3国内外研究现状.............................................................................................31.3.1数据分割...............................................................................................41.3.2特征提取...............................................................................................61.4主要研究内容.................................................................................................71.5论文结构安排.................................................................................................81.6本章小结.........................................................................................................9第2章点云模型K邻域搜索..................................................................................102.1k邻域搜索概述.............................................................................................102.2相关算法研究现状.......................................................................................112.2.1索引树法.............................................................................................122.2.2立体栅格法.........................................................................................132.3本文的搜索算法...........................................................................................162.3.1点云空间划分.....................................................................................162.3.2K邻域搜索..........................................................................................182.4实验分析.......................................................................................................202.5本章小结.......................................................................................................23第3章散乱点云的微分信息估算...........................................................................243.1微分信息概述...............................................................................................243.2点云法向量估算...........................................................................................253.2.1光滑曲面法向量估算.........................................................................253.2.2迭代修正特征曲面法向量.................................................................263.3法向量方向调整...........................................................................................29V 目录3.3.1最小生成树改进方法.........................................................................303.3.2最小生成树调整法向量.....................................................................313.4点云曲率估算...............................................................................................323.4.1移动最小二乘曲面.............................................................................323.4.2自适应最大核密度估计.....................................................................343.4.3曲率估算.............................................................................................343.5实验分析.......................................................................................................353.5.1法向量估算实验.................................................................................353.5.2曲率估算实验.....................................................................................383.6本章小结.......................................................................................................40第4章点云的特征提取...........................................................................................414.1特征提取概述...............................................................................................414.2相关算法研究现状.......................................................................................424.3特征点提取...................................................................................................434.3.1边界特征点提取.................................................................................444.3.2尖锐特征点提取.................................................................................454.3.3构建最小生成树.................................................................................474.4特征线拟合...................................................................................................474.4.1B样条曲线的定义...............................................................................474.4.2求解节点向量.....................................................................................484.4.3过控制点拟合特征线.........................................................................504.5应用实例及分析...........................................................................................514.5.1简单模型的特征提取.........................................................................514.5.2复杂模型的特征提取.........................................................................544.6本章小结.......................................................................................................56第5章基于聚类的混合数据分割...........................................................................575.1数据分割概述...............................................................................................575.2相关算法研究现状.......................................................................................585.3聚类算法定义...............................................................................................59VI 目录5.3.1K均值聚类..........................................................................................595.3.2点集的高斯映射定义.........................................................................605.3.3均值漂移聚类算法.............................................................................615.4基于聚类的混合分割...................................................................................625.4.1基于遗传算法的K均值聚类............................................................625.4.2高斯球上的均值漂移聚类.................................................................645.4.3区域调整.............................................................................................645.5应用实例及分析...........................................................................................655.6本章小结本章...............................................................................................70第6章论文工作总结与展望...................................................................................716.1论文工作总结...............................................................................................716.2主要创新点...................................................................................................726.3展望...............................................................................................................72致谢.............................................................................................................................74参考文献.....................................................................................................................75VII 第1章绪论第1章绪论1.1课题来源1.国家自然科学基金：“汽车模具表面缺陷的逆向建模及特征识别理论与算法”（项目编号：51365037）2.国家自然科学基金：“汽车及飞机模具数字化快速修复与再制造技术”（项目编号：51065021）3.针对国家基金项目前期所做工作所存在的问题和课题组研究人员提出的工作展望，进行选题。1.2课题研究意义与背景汽车及飞机等大型设备各部件制造过程中的一些关键零部件，不仅体积较大，结构复杂，还对其质量要求严格，故制造这些关键零部件的模具所需时间较长，投入成本较多，若模具产生缺陷或失效，将对相关企业造成巨大的经济损失。由于将空气动力学运用在汽车造型上，使得人们在汽车造型审美方面也随之不停的改变；同时也因汽车各部件的日新月异，使得逐渐增高对其零件模具的设计要求，其主要表现在零件模具开发周期要求越来越短，设计制造质量越来越高，需求量也越来越大等[1-2]。因此车企需不停的对汽车造型进行修改，而结构复杂、尺寸大的模具，对其精度和质量要求都高，而且模具的研发和修复都极为耗时、耗成本[3]。汽车各零件模具的制造质量和开发周期不仅影响着汽车的产品质量和更新换代周期，还决定了其在同行业上的竞争力。因此，如何缩短零件模具的开发周期、提高零件生产效率、保证模具质量，是促进其企业及相关行业发展的重点问题。虽然近年来我国在汽车数字化设计和制造水平上得到迅猛发展，但是目前国内汽车制造商的一些关键模具都是依靠国外进口，一旦模具出现局部疲劳磨损或物理损伤后修复成本高，或者无法修复而须重新购买，这又极大的增加了制造成本，故迫切需要模具检测、三维模型重建、缺陷识别、缺陷修复的逆向工程1 第1章绪论理论知识和系统工具支持[4-5]。模具表面缺陷的逆向建模是逆向工程的一个典型应用。逆向工程的关键技术如图1.1所示，首先通过三维扫描仪扫描实物获得点云数据模型，接着对点云模型进行数据处理和曲面重构，最后得到其数字CAD模型，再在数字CAD模型的基础上进行快速制造与修复。相对于点云获取的研究，点云的数据处理更有待研究。点云的数据处理可如图1.1所示，可分为三块：坐标变换与数据对齐；数据精简与数据滤波；数据分割与特征提取。点云的数据分割与特征提取不仅是点云模型数据处理的两个必要步骤，也是后续处理的基础与关键。点云模型的数据分割是利用曲面的几何特性将点云模型剪切成若干个互不相交的点云集[6]；点云数据的特征提取是从散乱点数据中提取出模型的由边界特征点、尖锐特征点组成的特征线。接数数坐曲曲曲触据据标面面面测精滤变拼求裁量简波换接交剪数据采集数据处理曲面重构实体CAD模型非曲矩三数数特接面形角据据征触光域域对分提测顺曲面曲面齐割取量检查重构重构图1.1逆向工程的关键技术目前，随着汽车更新淘汰速率的加快，一种新型汽车在市场上的周期越来越短，制造该类汽车的各类零件模具也需频繁更换。同时，人们对汽车外型和质量的要求逐渐趋于个性化，多样化。这便要求相关企业能对用户的要求及时的做出反应，根据要求快速准确的设计出相应模具的数字化CAD模型。引入逆向工程技术，可快速、准确地得到各零件的CAD实体模型，这为实现零件模具的快速设计制造提供了一种新的方法，也丰富了模具的设计手段[6-7]。故对本课题的研究，不仅有利于提高数字CAD模型逆向建模的效率和质量，还对我国汽车及飞机等大型制造行业的制造、开发及发展有着重要的意义。2 第1章绪论1.3国内外研究现状逆向工程（反向工程）这一概念是由美国的UVP和3M公司以及日本名古屋工业研究所于二十世纪八十年代首次提出[8]。目前，逆向工程在理论和商用软件的开发都有显著的成绩。著名的逆向工程商用软件有：美国的Imageware系列和Geomagic系列，韩国的RapidForm，英国的CopyCAD等；同时一些CAD/CAM集成软件中也加入了类似的功能模块，如Pro/E中的Pro/SCAN功能、Cimatron90中的ReverseEngineering功能模块等[9]。当前，国外多家企业对逆向技术进行了研究和开发，并已形成具有一定规模的新型产业。他们的三维扫描仪可扫描测量的实物对象更广，得到的CAD实体模型精度更高，处理速度更快，操作更简单，并且其硬件和处理软件的价格比国内的低[10]。国内对逆向工程的研究起步较晚，并且主要集中在国内的高校，且大多数的研究仍处于实验室研究，并未投入社会使用。国内对逆向工程理论和商用软件的研究一直处于进步阶段，对此具有代表性的研究如表1-1和表1-2。表1-1国内理论研究代表高校名称研究人员研究名称西安交通大学何炳蔚，林志航基于线结构的光学坐标测量机研究[11]上海交通大学用神经网络进行散乱点的区域分割[12]史桂蓉，邢渊等模具CAD国家基于逆向工程进行分布式早期协同设计，并建立了张必强工程研究中心系统框架[13]研制出一套采用激光测距仪和彩色线性CCD相机并吴剑、丁海曙、清华大学同步获取实物对象表面的三维信息、反射率信息以及王广志等彩色RGB信息的三维扫描系统[9]。南京航空航天基于点云表面的几何信息自动建立海量散乱点云的张丽艳，周儒荣大学CAD/CAM三角网格模型[14]等工程研究中心三维孔洞多边形模型修复研究[15]华中科技大学孙世为，王耕耘曲面测量与重建[16]散乱数据点云边界特征自动提取算法[17]山东理工大学孙殿柱等基于点云K邻域密度提取散乱点云边界[18]肖双九，邱泽阳广义相容三角网格及其优化[19]西北工业大学等数据点处理、建模吴禄慎，陈华伟NURBS曲面重构与点云-曲面误差分析[20]南昌大学等基于采样点场力和NURBS提取散乱点云的边界[21]3 第1章绪论表1-2国内商用逆向软件代表企业名称地点研究内容及产品“开发、生产和销售三维扫描系统，陆续推出了天远三维扫描仪、北京天远三维人体三维测量系统以及三维摄影测量系统等三维逆向产品，并与北京科技有限公司北京大学、清华大学等高等院校共同合作研究了多项国家级项目”[9]“依靠中科院以及留学人员等科研优势，研发生产白光、激光和深圳市华郎科工件光学检测等系列的三维扫描与测量系统，主要产品有三维光深圳技有限公司栅式扫描仪、拍照式三维扫描仪、三维摄影测量系统、三维人体测量系统等”[9]杭州先临三维主要提供非接触三维成像技术的综合解决方案，自主研发可见光科技股份有限杭州照相式Shining3D—Scanner系列三维扫描仪[9]。公司虽然我国在研究逆向工程的理论与技术方面都已取得一定的成果，但仍然处于起步阶段。在逆向工程中，点云数据整体处理的简单流程如图1.2所示。点云数据的处理可简单的分为三个部分：数据预处理；数据分割与特征提取；曲面重构。本文重点放在点云的数据分割与特征提取，数据分割与特征提取不仅是数据处理的必要步骤，也是后续处理的关键与基础。图1.2点云数据简单处理流程1.3.1数据分割数据分割可分为基于测量的分割和自动分割。基于测量的分割是操作人员在对实物进行测量的过程中，根据其外形特征同时进行标记，这种方法只适用于具有明显曲面特征的实物以及接触式测量，且其分割结果质量的好坏主要受操作人员的水平和经验的影响[22]。点云数据的自动分割即获取点云数据之后根据某一规则对点云数据进行自4 第1章绪论动分割，根据分割方法不同主要分为三类[22]：（1）基于边缘的点云数据分割：根据点云的法向量和曲率特性提取特征点，然后以特征点构成的封闭轮廓作为数据分割的结果；（2）基于区域的点云数据分割：首先选择种子点，然后根据一定的生长规则进行延伸完成分割；（3）混合方法分割：将基于边的和基于区域的点云数据分割方法进行改进再结合，结合这两种方法的优点。基于边缘的分割算法是从点云微分信息角度出发，将法向量或曲率突变的测量点作为两个相交区域的边界，最终将这些测量点连接成封闭环而其环内的区域则是数据的分割结果。Yang等[23]利用拟合的局部二次曲面逼近点云求得曲率，并根据突变的曲率获取边界特征点实现数据的分割。Huang等[24]根据不同边界在与之相连的两个切面的曲率与曲面的连续性判断边界类型并提取特征点，最后采用一定的区域生长方法区分尖锐边和过渡边实现数据的分割。Woo等[25]用八叉树来组织根据法向偏差完成细划分的栅格，最后依据法向量提取点云特征完成数据分割。董明晓等[26]直接提取点云中曲率变化较大的点作为边界点，完成分割。柯映林等[27]利用栅格之间的曲率差值作为特征栅格的提取依据，最后从提取出的栅格中分离出边界以实现区域分割。莫堃等[28]构造符号距离函数估算曲率，提高分割对噪声的抵抗力，利用3D活动轮廓实现分割。受数据点噪声以及点云微分信息计算误差的影响，使获得的特征线具有较多的分支和不连续特征线，甚至孤立的特征点，不能得到完整封闭的边界线，最终得到准确度不高的分割结果。同时，基于边的方法难以提取相对光滑边界的特征点。基于区域的分割是根据曲面性质将相同性质的曲面分成一类，主要分为自下向上和自上向下两种。自下向上就是由种子点按一定的区域增长方式向外生长，判断种子点的邻域点集是否属于同一性质的曲面。Rabbani等[29]按照点云的法向量及其冗余进行区域增长实现点云的分割。吴世雄等[30]根据主曲率的变化提取点云边界，再按区域生长完成分割。自上向下是假设所有数据点都属于一个曲面，然后再利用八叉树[31]、KD树、包围盒树(OBB-Tree)等检验假设是否有效。区域生长过程需不断检验曲面的拟合误差，因而是非常耗时的。同时一般的数据分割还存在特征欠分割或过分割现象、难以选择初始种子点以及确定正确的区域边界等问题。基于边缘和基于区域的分割算法都有它们各自的优缺点。为了克服这些缺点，所以将这两种算法结合起来形成一种新的分割算法——混合分割算法。混合分割算法一般是将基于边的和基于面的这两种算法都进行一些改进，使得能有效结合在一起实现分割。Yokoya等[32]提出一种利用高斯曲率和平均曲率实现点5 第1章绪论云初分割的基于面的分割算法与另一种基于边缘的分割算法对初分割区域提取边界的混合分割方法。肖春霞等[33]用LevelSet方法计算出的测地线首尾连接成封闭轮廓作为分割边界，最后用LevelSet演化曲面的区域生长方法来获取分割区域内部点，实现最终分割。孙金虎等[6]采用Snake模型提取出分割区域边界曲线，再利用最小生成树的区域生长方式分离区域内部点，再拆分带状分割边界形成最终区域。但是所需操作者交互的地方仍比较多，分割的自动化程度不够，对交互点的选择要求高，需在目标分割曲线上，且计算量大，用时长。综上所述，基于散乱点云的数据分割仍存在以下问题：1)采用拟合曲线或曲面去判断并提取边界点或边界线的数据分割法，不仅拟合曲线或者曲面所耗时间多，并且难以准确的提取到正确的边界点（因为扫描点是由离散点组成的，而边界点常常不被包含在扫描点中），从而限制了区域分割算法的实用性。2)基于曲率分割的方法较实用，但是对噪声的抗干扰能力不强，在进行数据分割时容易受到由噪声引起的伪曲率影响，从而得到不准确的分割结果。3)数据分割的自动化程度不高，目前还没有能全自动完成数据分割的方法，或多或少都需要一些人机交互操作，从而也就会影响到分割的准确性。4)分割算法计算复杂度高，耗时较多，且对于复杂的领域具有太多的局限性，自适应程度较低。1.3.2特征提取点云的特征包含了实物模型的很多重要信息，如实物的外部曲线特征、孔洞特征以及裂纹特征等。目前，已有大量国内外学者都对散乱点云的特征提取技术进行了多方面研究。Emelyanov等[34]以三角网格为判断依据确定采样点是否为边界点，但点云数据的三角化过程复杂，还会产生四面体，计算量较大。Sarkar等[35]利用拉普拉斯算子判断点云边界点，但易受噪声的影响，提取出的边界线精度不高。MilroyM.J[36]和Yang[23]根据曲率极值识别边界点，该方法能有效识别较光滑、平坦区域的边界点，但对曲率变化较大的特征区域则效果不佳。Orriols等[37]利用最小二乘法提取点云边界特征点，但精度不够高。Bendels等[38]利用最小生成树识别点云边界特征点，但提取的边界线不完整。张献颖等[39]利用采样点邻域点集的三角网格边是否闭合判断边界点，但构建点云的三角网格过程复杂、难度较高。柯映林等[40]利用点云3R包围盒对不同类型分布（均匀分布和非均匀分布）6 第1章绪论的点云提取其特征点。孙殿柱等[41]利用R*-tree搭建点云之间的拓扑关系并得到采样点的K邻域点集，以采样点和局部参考点集到基准平面的距离为依据判断特征点，但易受曲率变化影响。刘立强等[42]根据重心点与最远点的距离识别边界特征点，但难以识别曲率变化较大区域的特征点。赵双玲等[43]由点云曲率得到体积积分不变量，并利用K均值聚类方法依据体积积分不变特性提取点云特征点。该算法不依赖网格拓扑结构，只与点的个数和位置有关。孙殿柱等[17]利用采样点的微切平面计算出法向量，并根据相邻法向量的最大夹角判断点云特征点。陈义仁等[44]利用点集(m个点)的场力大小之和与场力最大值m的比值判断特征点，并利用双向最近点搜索算法自动生成特征线。晏海平等[21]根据邻域点集（K个点）中每个点在X轴和Y轴的分场力大小之和分别与最大场力和值K的比值判断并提取特征点，并利用NUBRS曲线拟合特征线。面对不断增大的点云规模以及日益复杂的实体模型，逆向工程在特征提取方面仍存在着以下问题需要解决：1)算法对噪声较为敏感。2)自动化程度低，仍需要手动选择种子点。3)对法向量和曲率变化缓慢的边界难以识别。4)不能保证能形成完整的封闭边界。1.4主要研究内容针对数据分割与特征提取仍存在的问题，本文将重点从以下方面进行研究：1)K近邻域的快速搜索分析K邻域的立体栅格法，规则的立体栅格法容易遗漏点云的局部特征点，故在立体栅格法的划分空间的基础上引入八叉树思想，使划分后每个立体小栅格内含有适中数量的点云，尽量使在进行K邻域搜索时不错过点云局部特征点；引入自适应空间球，并利用空间球外切立方体搜索K邻域，提高搜索的精度和速度。2)散乱点云的微分信息估算研究基于散乱点云的微分信息估算，用PCA方法估算全局点云法向量，其特征曲面的法向量与标准法向量之间具有较大的偏差，针对特征曲面的法向量采用一种改进的迭代加权法修正其法向量。传统的曲率估算都需要基于法向量来拟合局部曲面，法向量若不准确会造成所估算出的曲率大大偏离标准曲率，而7 第1章绪论且难以估算高曲率区域或者尖锐特征附近点的曲率，从而影响后续操作的准确性，本文提出一种基于稳健统计的移动最小二乘曲面的方法估算曲率，使得算法能够直接从散乱点云中计算出曲率，避免法向量带来的间接误差，并提高对高曲率区域点云曲率的估算能力。通过实验在微分信息的准确性和计算速率上与其他方法进行比较并检验其有效性。3)点云特征的提取研究散乱点云的特征提取技术，根据平均曲率提取点云边界特征点的算法只适合于分布均匀的点云数据，用于分布不均匀的点云数据会产生较大的误差，本文采用一种基于多尺度检测法专用于提取点云的边界特征点，使其能解决不同分布状况的点云数据，提高算法的适应性；利用普通的B样条法拟合的曲线其控制点不在曲线上，使得拟合出的曲线的精度不高，本文对B样条特征线拟合法进行改进，使B样条曲线过控制点对特征线进行拟合，以提高拟合曲线的精度。计算拟合曲线与标准曲线之间的误差，与其他算法在准确性与提取速度进行比较并验证算法的有效性。4)点云数据分割研究散乱点云的数据分割，在特征区域（高曲率）容易造成较大的误差，无法根据点云的几何特征准确的进行数据分割，本文提出一种将多种聚类算法相结合的混合分割方法，分别对基于K均值聚类分割法和基于高斯映射的均值漂移聚类分割法进行改进，实现分别对平坦曲面和特征曲面的数据分割，使得能准确的根据点云的几何特征进行数据分割。为验证算法的有效性，将本文算法分别与K均值聚类分割和均值漂移分割相比较，分析算法的优缺点。1.5论文结构安排全文共六章，内容安排如下：第一章介绍本课题的研究背景与意义，散乱点云的数据分割与特征提取技术国内外的发展现状以及仍然存在的问题，提出本文的主要研究内容。第二章对散乱点云的K邻域搜索技术进行研究，介绍并分析已存在的搜索算法，采用一种改进的K邻域搜索算法，对立方栅格法和空间球算法进行改进。第三章估算散乱点云的微分信息，分析全局计算法向量存在的问题，改进一种迭代加权法修正特征点云的法向量；提出一种基于稳健统计的移动最小二乘曲面的曲率计算方法，并通过实验验证算法的有效性。8 第1章绪论第四章分析了散乱点云特征提取存在的问题，介绍特征提取的原理，采用一种改进的合特征线拟合法，详细介绍算法的实现步骤及实验结果。第五章分析散乱点云数据分割所存在的问题，提出一种基于聚类的混合分割法，详细介绍分割所需聚类算法的原理、改进的方法、实现的步骤以及实验结果。第六章工作总结和展望。论文结构图如图1.3所示：第一章绪论第二章K近邻域搜索第三章散乱点云的微分信息估算第四章散乱点云的特征边界提取第五章基于聚类的混合数据分割第六章总结与展望图1.3论文的结构图1.6本章小结本章分析和讨论了散乱点云的数据分割与特征提取技术的研究背景与意义，并分析了逆向工程关键技术的国内外发展状况，找出数据分割与特征提取仍存在的问题，提出了本课题的主要研究内容，给出了论文的结构安排。9 第2章点云模型K邻域搜索第2章点云模型K邻域搜索2.1k邻域搜索概述点云数据邻域的确定，是逆向工程数据处理中的关键技术之一。邻域是散乱点云数据间建立的拓扑结构，点云数据中各个点的邻域仅仅与其相邻点构建关系，能有效提高点云数据处理的速率[6,45]。数据精简、数据分割、点云特征提取等，数据处理的效果直接受点云邻域的搜索效率的影响；在对点云数据进行后期处理（如CAD数字模型重建）的过程中，也是有着很大的影响[46]。因此，为了保证数据处理效果的准确性和数据分割、特征提取算法的有效性，需搭建散乱点云之间的拓扑关系——邻域，并对邻域的搜索算法进行研究。目前点云模型的邻域分为欧氏邻域、Meanshift聚类邻域、投影邻域和K邻域四种。比较四种邻域：欧氏邻域只适合于分布均匀的点云数据；Meanshift聚类邻域和投影邻域的虽然能更准确详细的描述局部特征形状，但是搜索速度低；K邻域不仅能处理均匀点云，还能处理非均匀点云，而且搜索速度快[6]。综合邻域搜索的速度和效果，本文针对规模较大的散乱点云数据，选择K邻域来描述点云的局部特征形状，对K邻域算法进行研究。散乱点云的K邻域搜索过程即在三维空间点集中，寻找与采样点距离最近的K个数据点，如图2.1所图2.1K=10时的搜索效果图10 第2章点云模型K邻域搜索常用的K邻域算法如图2.2所示，分为：基于voronoi图论、立体栅格法和索引树法。基于voronoi图论的K邻域算法，在计算V集时需要对浮点进行计算，计算的浮点数量较多，致使整个过程的计算量偏大，导致搜索效率低[47]，故在K邻域算法方面经常使用立体栅格法和索引树法。在使用立体栅格法和索引树法进行K邻域搜索时，都需要先进行空间划分再进行K邻域搜索。立体栅格法结构简单，栅格获取方便，但需要较大的内存空间来储存大量的小立体栅格数据；索引树法只需要的较少的内存空间来存储较少的节点，但难以搜索不同层的相邻叶子节点，而且搜索耗时较长[6]。图2.2K邻域搜索算法本文采用一种改进的基于立体栅格的自适应K邻域混合搜索算法。对点云模型的空间划分分为初划分和精划分，初划分采用规则立体栅格法划分，在精划分时引入八叉树思想，对初划分结果进行再划分，以保证获得的立体小栅格中包含的数目适中的采样点。再引入自适应空间球算法完成对已经进行了空间划分的点云数据进行K邻域搜索，该算法增强了搜索的自动化程度和稳定性，并提高了搜索的速度。2.2相关算法研究现状常用的K邻域的搜索算法立体栅格法和索引树法都分为两步：空间划分和K邻域搜索。索引树法主要分为：四叉树、八叉树、KD树、R-树等[48-49]。立体栅格法K邻域搜索有：逐层搜索算法和空间球搜索算法[6,50-51]。11 第2章点云模型K邻域搜索2.2.1索引树法树索引属于面向对象的分割索引技术。索引树法中的任一子节点的区域范围都属于其中间节点，叶子结点包括其区域内的所有空间对象。常用的树结构空间索引技术方法中，具有代表性的索引树法有：四叉树索引、八叉树、KD树、R-树索引系列[49]。八叉树是点云在三维空间中从四叉树的基础上拓展而来。四叉树是在二维空间中对数据进行分析与分类，八叉树是四叉树在三维空间中的拓展。八叉树采用递归分解的方式，对物体三维空间信息按照树行的结构进行描述。其基本思想是：首先建立一个空间包围盒立方体，使其包含所有的三维数据集，将三维区域用三维栅格的方式表示；其次，依据数据属性，将包围盒立方体划分为八个小立方体，并为每一个小立方体分配一个或多个属性信息。将属性相同的区域划分到一块，有属性不同的复杂区域按一分为八的原则划分划分到不同的小块；若划分后的小块内的属性还不是相同的，则继续将小块划分为八个小立方体；最后，直到划分的小立方体达到设定的精度或规定的层次为止，划分结束。如图2.3所示，为八叉树划分三维空间示意图。图2.3八叉树划分结构根据八叉树的划分规律，其详细步骤如下[48]：1)设置最大的划分阈值；2)估算点云模型的空间最小立体包围盒；3)根据设置的划分阈值，对最小立体包围盒按照八等分原则进行划分，将12 第2章点云模型K邻域搜索空间包围盒划分成八个子立方体（即将点云数据划分到相应的子立方体中）；4)如果设置的阈值大于空间划分的数目，则结束划分；否则重复步骤(3)，直到达到设置的划分阈值。八叉树索引算法结构简单，容易构造并且集合运算简单，层次信息清楚明了且各结点分布均匀。采用八叉树划分，能够将三维点云模型中的各数据点准确的划分到相应的子立方体中，但是搜索难度高，耗时较长。2.2.2立体栅格法立体栅格法的基本思路是用横向和纵向线条将需要处理的三维数据区域分成若干网格，每个网格都有自己唯一的标示，并对每个网格中所包含的空间对象记性记录。当需要查询时，先检索出三维空间对象所处网格，再通过网格准确找到所需要的空间对象的具体位置。立体栅格法的本质是通过对数据空间进行分块，降低空间的维度以建立索引，之后按顺序对栅格进行存储，在搜索的过程中采用已有的顺序索引结构进行检索，在进行搜索时所访问的目标磁盘和访问数据都是一次性的，所以搜索的速度快[49]。立体栅格法需先进行空间划分，再对划分后的栅格应用不同的算法进行搜索。基于规则立体栅格的空间划分是指将点云的空间区域划分成M×N×L个立体栅格，为每个栅格中的空间对象建立相应的索引。首先计算出与检测区域相关联的网格，再对该网格内的对应对象进行检索，应用此索引方法可以在每次搜索时只需要检索整个关注区域的1(𝑀×𝑁×𝐿)，故能大大的提高搜索的效率。此索引结构由两部分组成，即网格类和索引数组。在索引结构中，每个栅格由列号、行号、网格所对应的目标索引数组（空间对象所在空间网格的标示）等信息组成唯一的编码。在进行邻域搜索时，首先要确定目标对象所属的栅格号，再从对应的索引数组中提取出相对应的对象，最后将目标对象表达出来。这种基于规则栅格的索引结构实现搜索简单，在点云分布均匀且规模不大的情况下，可以快速的得到良好的搜索效果。在对于规模较大的复杂点云数据时，容易出现数据冗余的情况，使得空间内存的实用率降低，而且规则的网格大小也会制约搜索的效果，即：网格边长过小时，数据跨越网格的几率增大，数据的冗余量大；网格边长过大时，又不能体现出空间分块搜索的优势。如图2.4所示，为规则立体栅格的划分示意图。13 第2章点云模型K邻域搜索图2.4规则立体栅格法划分示意图栅格的层数：设采样点𝑝𝑖为当前点，点𝑝𝑖所在的栅格为(𝑖0，𝑗0，𝑘0)。若栅格满足条件max(|𝑖−𝑖0|，|𝑗−𝑗0|，|𝑘−𝑘0|)=𝑑，则栅格(𝑖，j，k)相对于栅格(𝑖0，𝑗0，𝑘0)的层数为d，简称栅格(𝑖，j，k)的层数为d。其几何意义是以采样点𝑝𝑖所在的栅格为中心，逐渐向外扩散d层到达栅格(𝑖，𝑗，𝑘)。由此可知采样点𝑝𝑖所处栅格(𝑖0，𝑗0，𝑘0)的层数为0。1.逐层搜索算法逐层搜索是以采样点𝑝𝑖所处栅格为中心，在三维空间内逐步向外层扩散栅格并搜索其区域内的点云数目，直至搜索到K个距离采样点𝑝𝑖最近的点云为止。逐层搜索基本过程如下：1)初始化：按照采样点𝑝𝑖的坐标位置，估算其所处小立方栅格{𝑖0，𝑗0，𝑘0}。定义数组A=𝑝𝑖点的K邻域点集，将点集中的点按照与采样点𝑝𝑖的距离由近到远进行排列；d为数组A中的第j个点与𝑝𝑖的距离；其中𝑑𝑚𝑖𝑛为采样点𝑝𝑖与最外层立体栅格六面的最短距离。初始化A=∅，d=+∞，𝑑𝑚𝑖𝑛=0。2)搜索过程：以采样点所处栅格（第0层）为起点逐渐向外层扩散、搜索，直到找到包含点云数据最外层内的所有栅格，并计算这些点到𝑝𝑖的距离，并将这些距离按照由近到远的规则添加至数组A中；此时判断是否达到逐层搜索的停止要求，如果达到条件则停止，否则将持续向外层扩散并搜索。3)搜索停止要求：需同时满足两项要求：①数组A中点的个数大于K个；②更新距离d和𝑑𝑚𝑖𝑛，满足d<𝑑𝑚𝑖𝑛。两个搜索停止要求的作用各不相同：条件①确保能找到的邻域点数不少于K；条件②确保搜索到的K个邻域点集距离采样点最近。若只用条件①判断是否结14 第2章点云模型K邻域搜索束进程，搜索结果无法保证其准确性，但条件①只需记录点云数目，故搜索速率较快。针对逐层搜索算法搜索结果不准确以及搜索效率低的问题，有学者提出了最外层搜索法[6]和过滤无点云栅格[52]来增强准确性和搜索效率，但是搜索的效果仍然不够好。2.空间球搜索算法空间球算法是以点云模型中采样点𝑝𝑖为球心建立空间球，然后在空间球的内部栅格和边界栅格中搜索K邻域点集，如图2.5所示。空间球算法的一般步骤如下所示：1)初始化：初始化空间球的半径r是根据点云密度计算的；定义数组A=𝑝𝑖点的邻域点集，令A=∅。2)搜索过程：建立以采样点𝑝𝑖为中心，半径为r的初始空间球。先估算覆盖整个空间球的最小立体栅格层v，将这0~v层栅格视为空间球的影响栅格（内部栅格和边缘栅格），并将这些影响栅格中的点按与采样点的距离从小到大添加至数组A中；然后判断是否达到搜索停止要求，若达到则停止，否则将持续向外层扩展空间球进行搜索。3)搜索停止要求：需同时满足两项要求：①数组A中点的个数大于K个；②数组A中的第K个点到采样点𝑝𝑖的距离d，需满足d≤r。图2.5空间球栅格示意图两个终止条件与逐层搜索法终止条件作用一致。在空间球算法中，最关键的是初始空间球半径的选取以及其半径的更新方式。所以很多学者也是从这两方面来研究：卫炜等[53]对动态半径的更新方式进行了研究，将采样点𝑝到所在立体𝑖栅格(𝑖0，𝑗0，𝑘0)六面的距离进行排序以更新半径r，但无法保证K邻域点的准15 第2章点云模型K邻域搜索确性。赵俭辉等[51]提出一种新的求取初始空间球半径的方法，能直接提取出其精确的K邻域，虽可自适应的计算出各个采样点处的初始半径，但不能更新其半径，若半径过大，会使搜索范围过大，降低运算效率。刘越华等[50]解决了卫炜邻域不准确的问题，但空间球半径需频繁更新，搜索效率低。综合考虑K邻域搜索的效率、速率以及自动化程度，本文K邻域算法是基于八叉树和立体栅格的一种混合搜索算法，首先使用八叉树和立体栅格完成对点云空间区域的划分，再采用自适应动态空间球算法搜索K邻域点。2.3本文的搜索算法本文采用了一种改进的混合K邻域搜索算法，首先对散乱点云数据应用规则网格法进行初划分，得到若干个大小相等的规则空间网格；接着引入八叉树空间划分思想，对已有的规则空间网格进行二次划分，以点云数量小于给定阀值V为终止条件，停止划分，得到信息量相似的立体栅格；最后应用改进的自适应动态空间球算法实现对采样点K邻域的搜索。2.3.1点云空间划分空间划分是将点云模型的空间包围区域按一定的棱长进行规则划分，进而得到若干个相同小立体栅格，这是实现K邻域搜索的基础。本文的空间划分包括两个步骤：初划分和精划分。通过划分得到的小立体栅格内含有相似的曲面空间信息。具体的步骤如下：1.点云初划分点云模型的初级划分是按照规则立体栅格法完成的，设点云分布均匀，将点云模型的空间区域划分成𝑚×𝑛×𝑙个小立体栅格，再在每个小立体栅格中放入相应的点云。主要包括以下三个步骤：（1）计算点云模型的空间包围盒[𝑋𝑚𝑖𝑛,𝑋𝑚𝑎𝑥][𝑌𝑚𝑖𝑛,𝑌𝑚𝑎𝑥][𝑍𝑚𝑖𝑛,𝑍𝑚𝑎𝑥]。（2）计算初划分小立体栅格的棱长，再依据此棱长对点云模型的空间包围区域进行规则初划分。空间划分是否准确，将影响点云K邻域搜索的速率，初划分小立体栅格的边长L1通常由公式（2.1）确定：3𝐾(𝑋𝑚𝑎𝑥−𝑋𝑚𝑖𝑛)(𝑌𝑚𝑎𝑥−𝑌𝑚𝑖𝑛)(𝑍𝑚𝑎𝑥−𝑍𝑚𝑖𝑛)𝐿1=𝛼√（2.1）𝑁16 第2章点云模型K邻域搜索式中N为点云总数，α为调控小立体栅格边长的因子。小立体栅格分别在X轴方向，Y轴方向和Z轴方向上的总数为：𝑚=⌈(𝑋𝑚𝑎𝑥−𝑋𝑚𝑖𝑛)𝐿1⌉𝑛=⌈(𝑌𝑚𝑎𝑥−𝑌𝑚𝑖𝑛)𝐿1⌉（2.2）𝑙=⌈(𝑍𝑚𝑎𝑥−𝑍𝑚𝑖𝑛)𝐿1⌉式中⌈⌉表示向上取整。（3）给点云数据与其所处栅格之间构建相应关系。估算出点云模型中任意点𝑃𝑖=(𝑥𝑖,𝑦𝑖,𝑧𝑖)所处栅格的小立体栅格号：𝑖0=⌊(𝑥𝑖−𝑋𝑚𝑖𝑛)𝐿⌋𝑗0=⌊(𝑦𝑖−𝑌𝑚𝑖𝑛)𝐿⌋（2.3）𝑘0=⌊(𝑧𝑖−𝑍𝑚𝑖𝑛)𝐿⌋式中⌊⌋表示向下取整。同时记录每个栅格所包含的点的序号，完成对点云模型空间的初划分，其效果图如图2.6所示。图2.6空间初划分效果示意图2.点云精划分对于复杂模具的点云模型，通过初划分得到的小立体栅格，由于点云的密度不均匀，故每个栅格内所包含的信息差异特别大，若直接进行K邻域搜索，则容易遗漏模型的局部特征细节，导致搜索结果不准确。本文引进八叉树的思想，对初划分后的含有特征信息多的栅格再进行精划分。精划分的准则是：点云密度的密集程度与小栅格的边长成反比（密度越大边长越小）。对经过初划分得到的第一层级立体小栅格进行逐层精划分的主要步骤如下：17 第2章点云模型K邻域搜索（1）逐层计算初划分后的每一个小立体栅格中所包含的点云数目。（2）如果初划分得到的小立体栅格中的点云数量小于给定阈值V，则不再进行精划分，小立体栅格的边长为𝐿1。阈值V的设定原则如下：𝑉=𝑁𝑁𝑐𝑢𝑏𝑒（2.4）其中𝑁𝑐𝑢𝑏𝑒为初划分后含有采样点的小立体栅格数量。（3）如果小立体栅格中的点云数量大于阈值V，将对此栅格再进行精划分，棱长𝐿𝑛(𝑛=2,3⋯𝑛−1)的重新确定由下式确定：1𝐿𝑛=𝛼×(𝐾𝜌)3（2.5）（4）对于新生成的所有立体小栅格，重复上述处理过程，直到所有立体栅格不需要继续划分或者达到指定的最大划分程度，最终确定立体小栅格的边长为𝐿。最后重新以边长𝐿对整个点云模型的进行规则划分，得到𝑚′×𝑛′×𝑙′个𝑛𝑛立体小栅格。（5）最后对重新划分后的小立体栅格建立与之相对应的栅格号，对点云数据中的每一个点𝑃𝑖(𝑥𝑖,𝑦𝑖,𝑧𝑖)计算其所属栅格号：𝑖0=⌊(𝑥𝑖−𝑋𝑚𝑖𝑛)𝐿𝑛⌋𝑗0=⌊(𝑦𝑖−𝑌𝑚𝑖𝑛)𝐿𝑛⌋（2.6）𝑘0=⌊(𝑧𝑖−𝑍𝑚𝑖𝑛)𝐿𝑛⌋并记录下所有的立体小栅格的栅格号。这样得到的立体小栅格使得每个栅格中的点云数量相对均匀。2.3.2K邻域搜索本文的K邻域搜索算法主要应用自适应动态空间球算法对点云数据进行索引。完成空间划分后，首先以点的近似密度自适应确定初始动态半径r，再利用其外切立方体动态扩展并搜索K邻域点集。1.过滤无点云栅格在完成对点云模型的空间划分后，遍历一遍所有的立体小栅格，将没有点云的立体小栅格的栅格号记录入数组B中，并标记为已访问。2.确定动态半径对三维空间点云数据中的任一子空间S内某一点p，估算出其动态球的初始半径r，步骤如下：设采样点p所属三维子空间内点云数据分布均匀，将此空间18 第2章点云模型K邻域搜索内点云的密度作为采样点p的局部近似密度，根据采样点p的近似密度、所属子空间体积以及K值由式（2.7）计算其初始半径r，公式如下：33𝑟=0.5×√𝐾×𝑉𝑠𝑁𝑠=0.5×√𝐾×𝐿×𝐿×𝐿𝑁𝑠（2.7）其中Ns为空间S内采样点数目；Vs为空间S的体积。算法初始r只与子空间内点云数目N有关。3.K邻域候选点的计算建立以采样点p为圆心，半径为r的动态球𝑝𝑖。由包含动态球𝑝𝑖的最小栅格决定采样点的子空间范围；计算动态球的外切立方体，搜索处于外切立方体内的点，即为采样点的K近邻候选点。4.动态球的扩展若动态球𝑝𝑖外切立方体内的k近邻候选点数目小于设定值k或没有搜索到候选点，则继续扩展更新动态球，并重新计算动态球的外切立方，并根据新的外切立方体所定义的范围，重新计算k近邻候选点或对候选点重新进行搜索。(a)空间球搜索三维示意图(b)空间球扩展二维示意图图2.7空间球扩展方式19 第2章点云模型K邻域搜索由图2.7可知，以采样点𝑝𝑖为圆心的动态球及其外切立方体1为初始搜索范围，其搜索范围为外切立方体所占的空间栅格立方体覆盖面积，若在当前搜索不能满足终止条件，则计算外切立方体1的外接动态球2，并计算其外切立方体2，再进行搜索，若外切立方体内的点云数目达到K，则停止搜索，否则重复计算外切动态球及其外切立方体进行循环搜索。算法在外切立方体内点云数目K满足设定值k时，最多再向外扩充一次就能保证其k邻域搜索成功，这有效的减少了扩充的次数，提高了算法效率。2.4实验分析本文K邻域算法的整体流程如下：1)输入点云模型数据，对点云空间利用规则立体栅格法进行初划分；2)根据点云密度对点云空间进行二次精划分；3)利用公式计算采样点𝑝𝑖的初始半径r，根据动态球计算其外切立方体，并在外切立方体所覆盖的栅格区域内寻找采样点的K邻域候选点；4)计数K邻域候选点个数，若候选点小于K个，则重新设置动态半径，扩大搜索范围，直到搜索到的候选点个数达到K个为止；5)若K邻域候选点的数目达到K后，再分别算出这些候选点与采样点𝑝𝑖的距离，并把该点存入至相应数组内并进行标记，再次搜索时将直接忽略这些已标记的点。若d≤r，则将其保存至数组A中，否则不保存。若数组A中点云数小于K，说明邻域搜索失败，则按步骤4重新搜索，直到保存至数组A中的点大于或等于K为止。最后对最终数组A中的点与采样点的距离按升序进行排序，前k个点即为p𝑖的k邻近点；6)对点云空间中所有子空间进行上述的重复搜索，直到完成所有点的K邻域搜索。20 第2章点云模型K邻域搜索开始点云空间进行初划分和精划分采空间任意点p计算采样点的初始动态半径r并确定动态球对m个点按距离进行排序，前K个位采样点的K邻域点集搜索K邻域候选点，并记录个数k是是否搜索点集P(i)P(i)内的点搜扩展动态球并计算其内下一个点的Kk≤K索完成半径r邻域点集否否搜索K邻域候选点并记计算候选点与采样点之间的距离d对下一个子空录个数k所有子空间搜索完间进行K邻域搜成索d≤r的点计入数组A中，并记录个数m是否是结束扩展动态球，并计算m≥K其半径r图2.8K邻域搜索整体流程本文以经典模型猫和兔子的点云模型（如图2.9所示）为研究对象，在个人笔记本上根据上述原理及步骤完成对点云的K邻域搜索，测量的时间是完成点云模型内平均每点K邻域搜索的时间，单位为ms。图2.9(a)猫的点云模型(b)兔子的点云模型本文中的研究对象猫的点云模型总共10000个点，兔子的点云模型总共有31607个点，对于本文的算法，主要的影响参数是空间球搜索时子块内点云的数21 第2章点云模型K邻域搜索目𝑁𝑠，而子空间的点云数目𝑁𝑠由空间划分中的调节因子α决定，α受点云密度ρ影响，故本文对α分别取0.20、0.26、0.30，K值分别取10、20、30、50分别对上述两种模型进行K邻域搜索，其搜索结果如下表所示：表2-1本文算法采样点平均K邻域搜索时间（单位：ms）K算法模型α102030500.200.10870.13340.16350.1980猫模型本0.260.11280.12970.15910.2002（n=10000）文0.300.11330.13570.16580.2102算0.200.12080.12720.18760.2436兔子模型法0.260.11900.13820.19470.2570（n=31607）0.300.13360.14460.21020.2701由表2-1可知是本文算法对猫和兔子点云模型平均每点K邻域的搜索时间1结果，根据公式σ=√∑𝑁𝑖=1(𝑥𝑖−𝑥̅)2计算其搜索时间标准差，由实验结果可知，𝑁本文算法中猫模型K邻域搜索时间标准差分别为0.002524、0.003027、0.003404和0.006502，兔子模型的搜索时间标准差分别为0.007961、0.008792、0.011557和0.01325。本文算法对调控因子的稳定性较好；针对同一模型、同一调控因子的情况下，本文算法随着K值的增大，搜索时间也增大，但是增幅不大；针对不同模型，在同一调控因子和K值的情况下，随着点云模型的复杂程度和总数目的增大，搜索时间增加，但是由结果可知，本文算法的变化是相对稳定的。与其他算法相比，本文与八叉树算法、KD树算法和文献[46]的算法对猫模型（n=10000）进行K邻域搜索，且将本文算法的调控因子设为0.26，其搜索时间结果如表2-2所示。表2-2其他算法搜索结果（单位：ms）K值算法10203050八叉树0.21310.24010.38920.6780KD树0.22670.24560.39710.7688文献[46]0.1250.14390.18700.2105本文算法0.11280.12970.15910.200222 第2章点云模型K邻域搜索由表2-1和2-2可知，本文算法相对于其他算法对点云模型的K邻域搜索时间较短，同时对不同点云数量的点云模型对每个点的K邻域搜索所用时间都较为稳定，并对调控因子具有较好的稳定性。2.5本章小结本章对K邻域的搜索算法进行了研究，采用一种改进的K邻域搜索算法，在基于立体栅格法对点云模型进行划分空间时融入八叉树思想，以确保每个立体栅格中的点云数量相对均匀，使得在进行K邻域搜索时能准确捕捉点云局部特征点。通过过滤无栅格法和自适应空间球算法提高搜索速度，增强算法的自动化程度。用该算法对猫和兔子的点云模型建立拓扑关系，并搜索K邻域点集，得其搜索时间标准差，并与其他几种经典算法（八叉树、KD树和自适应空间球）相比较。本章算法适用于均匀和非均匀点云模型，有效的缩短了搜索的时间，提高了搜索效率，增强了算法的稳定性。23 第3章散乱点云的微分信息估算第3章散乱点云的微分信息估算3.1微分信息概述点云模型只有点云数据的三维坐标信息，没有任何的拓扑关系，所以需要根据采样点的空间坐标估算曲面的重要微分几何特性。这些微分信息不仅是点云精简、特征提取、数据分割等数据处理技术的重要依据，也是后续曲面重构、CAD建模的重要基础。点云的微分信息主要包括一阶微分量的法向量和二阶微分信息曲率（曲率有平均曲率、高斯曲率、主曲率和主方向）。目前点云的法向量和曲率的估算方法根据点云表现形式的不同分为基于网格的和基于散乱点云的两种估算方法，基于网格的估算方法需要先对点云模型进行简化，再建立相应的模型，优化调整模型后，用该模型计算出法向量和曲率代替点云模型的微分信息，这种方法对于大型复杂模具的点云模型建立的替代模型不仅建模困难，而且模型不能准确的表示点云数据间的拓扑关系，以致估算出的微分信息也是不准确的[54-55]；基于散乱点云的估算方法是直接在散乱点云模型上计算曲面的局部微分信息，主要采用的方法是在局部曲面拟合的方法，这种方法计算出的微分信息与模具真实的微分信息的误差极小[56-58]。对比两种方法，基于散乱点云的方法具有相对较高的精度和稳定性，本文采用基于散乱点云的方法估算微分信息。基于散乱点云的估算方法的局部曲面拟合法，一般是采样点𝑃𝑖及其K邻域𝑁𝑘(𝑃𝑖)构建点集{𝑃𝑖,𝑁𝑘(𝑃𝑖)}，再以构建的点集拟合微切平面和局部曲面，最后通过微切平面估算一阶微分量法向量或拟合曲面估算二阶导数曲率[59-60]。这个方法中，法向量的计算和参数曲面的拟合是解决局部微分信息的关键问题。点云模型的法向量估算主要包括无符号的法向量值估算和法向量方向的一致性调整两个步骤[6]，前者估算出点云上各点的无符号法向量值，确定法向量方向的大体范围，后者对无符号法向量值赋予符号，使得曲面内各点的法向量都指向点云曲面的同一侧。本章对法向量的估算分为两步走，先计算出光滑区域的法向量，再利用得到的光滑曲面的法向量去迭代修正特征区域的法向量，最终得到整个点云模型准24 第3章散乱点云的微分信息估算确的法向量；利用最小生成树对曲面分为“平坦点”和“非平坦点”进行法向量调整，而且仅在已调整点和未调整点的边界中搜索权值最小边，能有效的提高调整的效率与速率；采用稳健统计技术获得最佳的子点集，再于此点集基于移动最小二乘法（(Moving-leastsquare，简称为MLS）拟合点云的局部曲面，移动最小二乘曲面可以为点云提供一个高阶连续曲面，所得曲面具有良好的抗噪声能力和较高的拟合精度；最后使用二元多项式函数g局部逼近真实曲面，获得点云的移动最小二乘曲面MLS，通过去S曲面隐式函数进行微分变换，解析后得到点云模型的局部曲率，算法有效的减少了计算量，提高了稳定性。3.2点云法向量估算对于无符号的法向量值估算主要包括局部拟合方法、Voronoi方法以及基于稳健统计三种方法。比较这三种方法，局部拟合方法得到的法向量比其他两种方法更加准确，而且也更稳定。在局部拟合方法中，法向量的估算主要分为基于PCA变换和基于移动最小二乘拟合平面两种估算方法。本文针对散乱点云数据法向量的求取分为两步，首先用PCA变换法对光滑区域进行估算，再利用光滑曲面估算出的法向量对特征区域进行迭代修正。3.2.1光滑曲面法向量估算基于PCA（principalcomponentsanalysis）变换的法向量算法是Hoppe[61]于1992年提出的一种法向量的估算方法，也称为主成分分析方法或者微切平面法，它是基于局部表面拟合方法的代表。基于PCA变换估算法向量的主要思想是：假设点云的采样表面是光滑的（即产品表面的曲面是高阶连续的），对于曲面上任何点的切平面都可以用主成分分析对其K邻域计算一个最小二乘下的平面而得到，再将其协方差矩阵所对应最小特征值的特征向量作为采样点的法向量。PCA方法本质是低通滤波器，会产生过度的平滑，并且对散乱点敏感。因此，用PCA对于特征曲面估算法向量时就会容易将曲面特征过滤掉，使估算出的特征曲面的法向量与标准法向量相差较大；但是针对点云分布均匀，光滑且噪声变化尺度不大的曲面，基于PCA变换的方法能有效且准确的估算曲面的法向量。对于光滑曲面，给定点集{𝑝𝑖,𝑁𝑘(𝑝𝑖)}，点𝑝𝑖的K邻域𝑁𝑘(𝑝𝑖)，对点集中的任25 第3章散乱点云的微分信息估算一点𝑝𝑖及其K邻域拟合的最小二乘平面的表示为：𝑃𝑙(𝒏，𝑑)=𝑎𝑟𝑔𝑚𝑖𝑛∑𝑘(𝒏∙𝒑−𝑑)2（3.1）𝑖−1𝒊其中n为平面Pl的法向量，d表示邻域点到拟合平面的距离，法向量n需要满足条件：‖𝐧‖2=1由于PCA法求取法向量是将其协方差矩阵所对应最小特征值的特征向量作为采样点𝑝𝑖的法向量，因此对小二乘平面Pl的求解可以转化为对半正定协方差矩阵C的特征值分解，矩阵C最小特征值的特征向量可作为采样点𝑝𝑖的法向量。𝑝−𝑝1𝑇𝑝−𝑝1𝑝−𝑝2𝑝−𝑝2𝐶=[][]（3.2）⋮⋮𝑝−𝑝𝑛𝑝−𝑝𝑛C分解出三个分量𝑣0、𝑣1、𝑣2分别对应三个特征值𝜆0、𝜆1、𝜆2，且满足条件𝜆2>𝜆1>𝜆0。PCA方法在估算法向量时用来拟合最小二乘平面的邻域的形状和大小是两个关键的因素。所以Mitra提出在光滑的曲面下，在法向量误差内自适应选取不同位置采样点K邻域大小的解析方法，得到基于带权的协方差矩阵的多尺度分析：(𝑝))=∑(𝑝)(𝑝)𝑇‖𝑝𝑖−𝑝‖𝐶(𝑁𝑘𝑖𝑖𝜖𝑁𝑘(𝑝𝑖)𝑖−𝑢𝑘𝑖−𝑢𝑘𝜙(ℎ)（3.3）𝑘其中𝑢𝑘是K邻域𝑁𝑘(𝑝𝑖)内所有点的带权均值，ℎ𝑘是以点𝑝𝑖为球心包围K邻域的最小球半径。∅(𝑥)=𝑒𝑥𝑝(−𝑥2)，是单调正且递减的权函数。同样带权矩阵的三个分量对应三个特征值，最小的特征值对应的特征向量为平面的法向量，即𝒏=𝒗𝟎（3.4）用基于PCA方法计算出的法向量只是确定了法向量所在的直线位置，而并没有确定的指向模型表面的外侧或者内侧，所以仍然需要对法向量的方向进行全局调整。3.2.2迭代修正特征曲面法向量大型复杂模具的表面包括多个不同类型的曲面（曲面是高阶不连续的）和由多个曲面交界形成的过渡区组成的特征区域。所以用基于PCA变换去估算大型复杂模具点云模型的法向量容易过滤掉特征区域的特征性质，估算出的法向量26 第3章散乱点云的微分信息估算与标准法向量偏差很大，所以为了准确的计算出大型复杂模具的点云模型整体的法向量，利用3.1.1算出的光滑曲面的法向量对特征曲面的法向量进行迭代加权修正。由于特征曲面的高阶不连续曲面，故对特征区域通过K邻域拟合的微切平面与采样点所在的真实曲面存在较大偏差。所以针对迭代加权修正特征曲面的法向量的方法中主要是对采样点的邻域点迭代加权拟合微切平面进行改进。Hoppe[61]根据采样点的K邻域点拟合微切平面估算法向量，Pauly[62]对拟合平面的改进是对当前点的邻域加入高斯权重𝜔𝑑(𝑝𝑖)，自适应的控制邻域内不同位置点云对拟合平面的作用，即：当点云p离邻域点𝑝𝑖越远对拟合平面的作用越小，离得越近则对拟合平面的作用越大。所以对于拟合的微切平面Pl为：𝑃𝑙(𝒏，𝑑)=𝑎𝑟𝑔𝑚𝑖𝑛∑𝑘𝜔(‖𝑝−𝑝‖)(𝒏∙𝑝−𝑑)2（3.5）𝑖=1𝑑𝑖𝑖其中高斯权重𝜔𝑑(𝑝𝑖)=𝑒𝑥𝑝(−‖𝑝𝑖−𝑝‖𝜎𝑑2)，𝜎𝑑是距离带宽。但是对当前点的邻域加入高斯权重，拟合微切平面求得的特征曲面法向量与实际法向量仍然存在很大的偏差，因为只是考虑了当前点与邻域的距离，并没有改变邻域是各向同性的根本问题。Mederos[63]不仅加入了Pauly的高斯权重，还叠加了当前点的距离因子和到拟合平面的残差因子ρ(𝑝)。使得微切平面的表示为：𝑃𝑙(𝒏，𝑑)=𝑎𝑟𝑔𝑚𝑖𝑛(∑𝜌(𝑑+(𝑝−𝑝𝑖)𝑇𝒏)𝜔𝑑(𝑝𝑖))（3.6）𝜎2𝑟‖𝜎2))，𝜎其中残差因子ρ(𝑝)=(1−𝑒𝑥𝑝(−‖𝑝−𝑝𝑖𝑟𝑟是残差带宽。距离带2宽和残差带宽是用来控制各邻域点对当前点作用力大小的控制。但是加入高斯权重和残差因子的平面求解过程复杂、耗时。对此，Huber[64]用迭代加权平均法来求解该平面，迭代平均是通过对邻域点迭代加权来逐渐减小不在同一连续曲面的邻域点对拟合平面的作用，用迭代加权平均的相似平面替代求解：𝑃𝑙(𝑑𝑡，𝒏𝒕)=𝑎𝑟𝑔𝑚𝑖𝑛∑𝑟𝑡𝜔(𝑝)𝜔(𝑟𝑡−1)（3.7）𝑖𝑑𝑖𝑟𝑖其中第t次迭代时点𝑝的残差𝑟𝑡=𝑑𝑡+(𝑝−𝑥)𝑇𝐧𝐭，高斯权重函数𝜔(𝑟)=𝑖𝑖𝑖𝑟𝑖𝑒𝑥𝑝(−(𝑟𝑖𝜎𝑟)2)，平面中两个参数距离𝜎𝑑和残差带宽𝜎𝑟影响着法向量的准确性，但是却难以设定，替代平面每次迭代求解的法向量就是协方差矩阵𝐶2的特征向量。27 第3章散乱点云的微分信息估算𝑝1−𝑝−𝑢𝑇𝑝1−𝑝−𝑢𝑝2−𝑝−𝑢𝑝2−𝑝−𝑢𝐶2=[⋮][⋮]（3.8）𝑝𝑛−𝑝−𝑢𝑝𝑛−𝑝−𝑢∑𝜔𝑑(𝑝𝑖)𝜔𝑟(𝑟𝑖)(𝑝−𝑝𝑖)其中𝑢=，因为加入了残差因子，虽然距离和残差带宽难以∑𝜔𝑑(𝑝𝑖)𝜔𝑟(𝑟𝑖)设定，但是对特征区域估算出的法向量还是有明显的改善的。在此基础之上，wang[65]又加入了邻域点与当前点的法向偏差权重𝜔(𝐧)来控制不同法向偏差的𝑛邻域点对当前点的影响，再通过对邻域点多次迭代加权拟合微切平面，其微切平面为：𝑃𝑙(𝑑𝑘，𝒏𝒌)=𝑎𝑟𝑔𝑚𝑖𝑛∑𝑟𝑘𝜔(𝑝)𝜔(𝑟𝑘−1)𝜔(𝒏𝑘−1)（3.9）𝑖𝑑𝑖𝑟𝑖𝑛𝑖其中法向偏差权重𝜔𝑛(𝐧)=exp(−‖𝐧−𝐧𝐢‖𝜎𝑛2)，𝜎𝑛是法向偏差带宽，微切平面的协方差矩阵同样为𝐶2：𝑝1−𝑝−𝑢𝑇𝑝1−𝑝−𝑢𝑝2−𝑝−𝑢𝑝2−𝑝−𝑢𝐶2=[⋮][⋮]（3.10）𝑝𝑛−𝑝−𝑢𝑝𝑛−𝑝−𝑢∑𝜔𝑑(𝑝𝑖)𝜔𝑟(𝑟𝑖)𝜔𝑛(𝐧𝒊)(𝑝−𝑝𝑖)只是𝑢=，拟合平面的法向量是𝐶2最小特征值对应的∑𝜔𝑑(𝑝𝑖)𝜔𝑟(𝑟𝑖)𝜔𝑛(𝐧𝐢)特征向量，而且式中三个带宽都是随着曲面自适应更新的，提高了算法的自动化程度，该方法得到的特征区域的法向量比文献[63]的方法不仅更准确，而且对噪声的鲁棒性更好。所以本文根据邻域中的邻域点与当前点之间的法向夹角判断对当前点法向量修正作用的大小（法向偏差越大，作用越小，距离越远，作用力也越小），利用邻域中准确的法向迭代加权修正不准确的法向量，本文应用以下公式估算特征区域的法向量。∑𝜔𝑡)𝜔𝑡，𝑛𝑡)𝑛𝑡𝑝𝑗∈𝑁𝑏(𝑝𝑖)𝑑(𝑝𝑖，𝑝𝑗)𝜔𝑟(𝑟𝑖𝑛(𝑛𝑖𝑗𝑗𝑛𝑡+1=（3.11）𝑖∑𝑝𝜔𝑑(𝑝𝑖，𝑝𝑗)𝜔𝑟(𝑟𝑡)𝜔𝑛(𝑛𝑖𝑡，𝑛𝑡)𝑗∈𝑁𝑏(𝑝𝑖)𝑖𝑗22其中空间欧式距离核函数：𝜔𝑑(𝑝𝑖，𝑝𝑗)=𝑒𝑥𝑝(−(‖𝑝𝑖−𝑝𝑗‖)𝜎𝑑)；残差高斯核函数：𝜔(𝑟𝑡)=𝑒𝑥𝑝(−((𝑑𝑡+(𝑝−𝑝)𝑇𝑛𝑡)𝜎)2)；法向偏差核函数：𝜔(𝑛，𝑟𝑖𝑖𝑟𝑛𝑖2𝑛)=𝑒𝑥𝑝(−(‖𝑛−𝑛‖)𝜎2)。𝑗𝑖𝑗𝑛针对大型复杂点云模型的法向量计算，先用PCA算法初步对点云模型进行法向量估算得到初始迭代法向量，将初始法向量单位化且对初始法向量进行方28 第3章散乱点云的微分信息估算向调整，使法向量的方向调整至一致方向。再将平坦区域准确的法向量带入式（3.11）修正特征区域的法向量。3.3法向量方向调整无符号法向量估算出的结果只是曲面法向量的大小值，曲面法向量的方向却不一定（有的指向曲面内部，有的指向曲面外部，不具有一致性），如图3.1所示，相邻切平面法向量的方向指向。不定向的法向量会导致后续的特征提取和点云分割出现混乱，所以需要对法向量进行调整，使其具有全局一致性（法向量的方向全部指向曲面内部或则外部）。图3.1(a)调整前法向量示意图(b)调整后法向量示意图点云法向量的调整目前有最小生成树法（MinimumSpanningTree，MST）、光度立体视觉法和曲面重建法三种。最小生成树法[66]是用的最广泛的一种，其主要思想是：首先确定种子点，然后沿着路径遍历点云生成最小生成树，假设点𝑝𝑖和𝑝𝑗是路径上相邻的两点，且法向量分别是𝐧𝑖和𝐧𝑗，当𝑛𝑖∙𝑛𝑗<0时，需要将其中一个法向量进行倒转，最终使相邻点的法向量的内积为正，达到最终调整的效果。但是该算法计算效率低，不适合处理大规模点云，而且对具有相邻曲面等奇异情况的点云的法向量进行调整时容易出现错误；光度立体视觉法是利用光照几何和曲面发射等先验经验来计算曲面法向量的，曲面上的一点的法向量通过三个或则三个以上的光源照射来确定，但是算法容易受到材料伪影、遮挡或者镜面反射等影响，稳定性很差；曲面重建法是利用局部优化投影、自组织神经网络、自适应球面覆盖等方法对原始点云进行重采样，得到原始点云的均匀结构（例如：三角网格结构等），计算近似法向量，再由近似结构的法向量来调整原始点云的法向量。能够有效的对具有相邻曲面等奇异情况的点云进行正确的法向量调整，29 第3章散乱点云的微分信息估算但是计算相似结构的过程复杂、耗时多。3.3.1最小生成树改进方法本文采用改进的最小生成树法对法向量进行调整，主要是在Prim算法的基础上从减少查找权值c时所遍历的点数以及增加每次向外扩散的点数两方面进行改进[66]。1.减少遍历的点数权值c最小的边只会出现在已经处理点集U和未处理点集W的边界，所以对于U和W都可以分为内部点和边界点，U=𝑈1+𝑈2（其中𝑈1为已处理点集中的内部点，𝑈2为边界点）W=𝑊1+𝑊2（其中𝑊1是未处理点集中的内部点，𝑊2为边界点）。所以在找权值c最小的边时，只需再遍历一次点集𝑈2和𝑊2，这样就减少了遍历的点数。2.增加扩散的点数Prim算法在进行遍历时，点集U只能向外扩散一个点，这大大的降低了调整速率与效率。为增加每次扩散遍历的点数，预先为权值c设定阈值e，再在U和W之间查找满足c≤e的所有边，对其中属于W中的点可直接扩散，并标记为已处理点。若U和W之间所有边均满足c>e，多点同时扩散将无法进行，则采用单个点扩散来进行。表3-1权值c的取值尖角或尖锐棱边处的调整效序号权值c取值方式果准则一c为𝑢𝑗和𝑤𝑗两点间的距离可能会出现错误c=1−|𝑛𝑢𝑗∙𝑛𝑤𝑗|=1−|cos𝛼|；准则二正确调整α为𝑢𝑗与𝑤𝑗两点法向所在的夹角准则三c=w𝑗到u𝑗的法向距离正确调整本文选择准则二来确定权值c=1−|cos𝛼|，所以可以由α的阈值来决定权值c的权值。比如α=10°时，即在[0°,10°]或者[170°,180°]范围内可以同时多点扩散，而不再这个范围或者无法进行多点扩散时，则采用只一个点方式扩散。30 第3章散乱点云的微分信息估算3.3.2最小生成树调整法向量使用最小生成树法来调整法向量，处理解决遍历点的问题还需要解决的是：种子点的选择及其法向量方向的确定；怎样根据已处理点集U的法向量方向来调整未处理点𝑤𝑗的法向量的方向。1.种子点的选择目前关于种子点的选择有三种方法：1)选择点云模型的最高点作为初始种子点。2)先遍历点云中的所有点，选择与其K邻域的法向夹角方差值最小的点作为法向量调整的初始种子点。3)用户直接手动在较平坦的区域选择一点作为初始种子点。上述三种方法中，方法1能直接确定初始种子点的法向量方向，方法2和方法3初始点法向量方向都只能通过用户设置。本文选择方法1和方法2进行选择，优先采用方法1，对不符合的点云再采用方法2来重新选取。2.未处理点云法向量方向的确定对于相邻两点的法向量𝐧𝑈𝑗（已处理点的法向量）和𝐧𝑊𝑗（未处理点的法向量），主要根据两法向量的内积判断未处理点的法向量调整动态：若𝑛𝑈𝑗∙𝑛𝑊𝑗<0，那么将未处理点的法向量𝑛𝑊𝑗的方向颠覆；若𝑛𝑈𝑗∙𝑛𝑊𝑗>0，那么未处理点的法向量不需要调整。沿着最小生成树的延伸一直扩散，直到边上所有相邻点的法向量内积都为正，则完成调整，即所有的法向量均指向曲面的同一侧。以规则的圆柱点云模型为例，其完成法向量值计算之后，整个模型的法向量分布是混乱的，如图3.2（a）所示。采用上述方法将，对点云模型的法向量方向进行调整，使其全部指向曲面的一侧如图3.2(b)、(c)所示。图3.2(a)未调整的法向量(b)法向量全指向外侧(c)法向量全指向内侧31 第3章散乱点云的微分信息估算3.4点云曲率估算针对散乱点云数据的曲率估算主要使用的是拟合曲面法，其主要思想是：先对采样点建立K邻域点集，然后以点集拟合微切平面，求取微切平面的法向量作为曲面的法向量，再基于法向量建立局部坐标系局部拟合曲面，最后计算出曲率。这就要用到法向量，若法向量不准确就会导致曲率出现错误。要得到准确的曲率，要解决两个问题：一个是法向量的准确求解和提高拟合的曲面与实际曲面的相似性。所以本文在使用移动最小二乘法拟合曲面，再在拟合曲面的基础上加入稳健估算技术，可以在估算曲率的时候就不需要依赖法向量了，可以直接在拟合曲面上估算出曲率。首先，用移动最小二乘曲面拟合点云模型中采样点处的局部特征形状；接着，在该采样点的邻域点中任意选择一个子点集，多次重复拟合过程，通过变窗宽最大核密度估计，获得最佳的拟合曲面；最终，将采样点投影到该最佳的拟合曲面上，计算出投影点曲率信息，得出采样点曲率。3.4.1移动最小二乘曲面移动最小二乘曲面是基于移动最小二乘算法由散乱点数据建立的曲面，拟合曲面精度高，模型表达简单，还可以实现点云降噪(de-noising)、上采样(up-sampling)和下采样(down-sampling)等功能[60,67]。1.移动最小二乘曲面移动最小二乘法(Moving-leastsquare，记为MLS)是一种离散数据插值的方法。Levin首先提出了一种基于移动最小二乘曲面的算法，对数据集X={𝑥，x∈𝑅3}进行投影操作得到𝐶∞连续的曲面𝑆。如图3.3所示，为MLS示意图。𝑝图3.3MLS示意图32 第3章散乱点云的微分信息估算移动最小二乘曲面𝑆𝑝是由一系列经投影的点组成且其空间位置保持不变。𝑆𝑝={𝑥∈𝑅3/𝛹𝑝(𝑥)=𝑥}（3.12）其中Ψ𝑝表示投影操作，其投影可解释为采样点x沿法向量域n(𝑥)寻找能量函数E(𝑦，n(𝑥))最小值的过程，则移动二乘曲面𝑆𝑝可表示为：𝜕𝐸(𝑦，𝑛(𝑥))𝑆={𝑥∈𝑅3|𝐺(𝑥)=𝑛(𝑥)𝑇[|]}（3.13）𝑝𝑦=𝑥𝜕𝑦其中y为表示位置的向量。定义不同的法向量域n(𝑝𝑖)和能量函数E(𝑦，n(𝑝))，可产生不同变体的移动最小二乘曲面。本文采用Zwicker[68]的方𝑖法定义移动最小二乘曲面𝑆𝑝：𝑆={𝑥∈𝑅3|𝑔(𝑥)=∑2𝑒−‖𝑥−𝑝𝑖‖2ℎ2(𝑥−𝑝)𝑇𝑛(𝑥)=0}（3.14）𝑝𝑝⊂𝑃𝑖其中对法向量域和能量函数的定义如下：∑𝑝𝑖⊂𝑃𝑣𝑖𝜃𝑝(𝑥)𝑛(𝑥)=（3.15）‖∑𝑝𝑖⊂𝑃𝑣𝑖𝜃𝑝(𝑥𝑝𝑖)‖2𝐸(𝑦，𝑛(𝑥))=∑𝑝⊂𝑃((𝑦−𝑝𝑖)𝑇𝑛(𝑥))𝜃𝑝(𝑥)（3.16）其中向量𝑣𝑖为点𝑝𝑖的法向量，θ为高斯权函数。该方法定义的移动最小二乘法能够避免在计算时进行非线性优化的问题，计算效率更快，算法稳定且易于实现。2.局部投影由于噪声或法向量误差的影响，输入点𝑝𝑖不一定都位于移动最小二乘曲面上。因此在计算输入点的曲率时，首先应找到输入点在移动最小二乘曲面上对应的的投影点𝑝′，将𝑝′的曲率作为输入点p的曲率特性。𝑖𝑖𝑖投影过程如下：1)令迭代初始点𝑥0=𝑝𝑖，迭代步j=0；2)根据法向量域公式计算𝑥𝑗的法向量n(𝑥𝑗)；3)定义直线𝑙𝑖为沿着法向量n(𝑥𝑗)且过点x𝑗，沿直线𝑙𝑖可得到使能量函数最小𝑑𝐸(𝑦，n(𝑥𝑗))（即：=0）的点y=𝑦0。𝑑𝑡𝑙𝑖:𝑦(𝑡)=𝑥𝑗+𝑡𝑛(𝑥𝑗)，𝑡∈𝑅（3.17）4)令𝑥=𝑦。若|𝑥−𝑥|≤𝜀，ε=10−6则停止，𝑥则为点𝑝的投影点𝑗+10𝑗+1𝑗𝑗+1𝑖33 第3章散乱点云的微分信息估算𝑝′，否则重复2~4，直到满足等式|𝑥−𝑥|≤𝜀为止。𝑖𝑗+1𝑗𝑑𝐸(𝑦，n(𝑥𝑗))𝑔(𝑥𝑗)将=0，求得𝑡0=，将𝑡0带入直线得到能量最小的y(𝑡)，𝑑𝑡∑𝑝⊂𝑃𝜃𝑝𝑖(𝑥𝑗)及可得到新点：𝑥𝑗+1=𝑦(𝑡0)=𝑥𝑗+𝑡0𝑛(𝑥𝑗)（3.18）3.4.2自适应最大核密度估计自适应最大和密度估计[69]是稳健统计技术中的一种，其本质是对拟合的最小二乘曲面进行统计记分，重复迭代直到得到分数最大的曲面为止，作为最终的拟合曲面。自适应窗宽最大核密度估计需假设点云满足高斯分布，且占据相对多数。算法的步骤为：1)输入散乱点云数据点集P{𝑝𝑖，𝑝𝑖∈𝑃}，初始化采样点的核密度值，令其为0；2)对散乱点云随机选择一个子集𝑃𝑗{𝑃𝑗⊂𝑃}建立移动最小二乘曲面𝑆𝑝；3)根据建立的移动最小二乘曲面计算点云模型中所有点与拟合的曲面之间的残差；4)根据以下公式自适应的计算窗宽h:1243𝑅(𝑘)5ℎ=[2(]𝜎（3.19）35𝑛𝑢2𝑘)12(𝑥)𝑑𝑥(𝑘)=∫1𝑥2|𝑟𝜃|𝑘其中：R(𝑘)=∫−1𝑘，𝑢2−1𝑘(𝑥)𝑑𝑥，σ=𝜑−1(1+𝑘)，φ为正态累计密度函数的参数。5)根据以下公式计算子集𝑃𝑗概率密度值，以其作为拟合曲面分数：∗∗1∑𝑛𝑘(𝑟𝑖𝜃̂=𝑎𝑟𝑔𝑚𝑎𝑥𝑓̂𝜃，𝑓̂=𝑛ℎ𝑖=1ℎ)（3.20）6)重复步骤2-5m次，直到找到概率密度值最大𝑓̂∗的子集𝑃，再以子集𝑃𝑚𝑎𝑥𝑡𝑡‘‘重新开始拟合移动最小二乘曲面𝑆𝑝。即𝑆𝑝为最优拟合曲面。3.4.3曲率估算本文提出的曲率估算方法将稳健估计技术和移动最小二乘拟合曲面。其算法的一般思想为：首先对于散乱点云随机选取一点集进行拟合得到一个移动最34 第3章散乱点云的微分信息估算小二乘曲面，再根据点云与曲面之间的残差，计算该子集的概率密度值，直到找到概率密度值最大的子集，再以该子集拟合建立移动最小二乘曲面则为点云数据的最优曲面。得到移动最小二乘曲面𝑆𝑝:𝑆={𝑥∈𝑅3|𝑔(𝑥)=∑2𝑒−‖𝑥−𝑝𝑖‖2ℎ2(𝑥−𝑝)𝑇𝑛(𝑥)=0}（3.21）𝑝𝑝⊂𝑃𝑖则曲面的高斯曲率𝐾𝐺和平均曲率𝐾𝑚为：𝐻(𝑔(𝑥))𝛻𝑔(𝑥)𝐷𝑒𝑡[]𝛻𝑇𝑔(𝑥)0𝐾𝐺=−‖𝛻𝑔(𝑥)‖4（3.22）‖𝛻𝑔(𝑥)‖2𝑇𝑟𝑎𝑐𝑒(𝐻(𝑔(𝑥)))−𝛻𝑇𝑔(𝑥)×𝐻(𝑔(𝑥))×𝛻𝑔(𝑥)𝐾𝑚=‖𝛻𝑔(𝑥)‖3（3.23）其中Det[𝐴]和Trace(𝐴)分别表示矩阵A的行列式和迹；其中H(𝑔(𝑥))是隐式方程梯度∇g(𝑥)的Hessian矩阵(H(𝑔(𝑥))=∇(∇(𝑔(𝑥))))。其中隐式函数的梯度∇g(𝑥)的公式为：𝛻𝑔(𝑥)=∑2𝑒−‖𝑥−𝑝𝑖‖2ℎ2(−2(𝑥−𝑝)𝑇𝑛(𝑥)(𝑥−𝑝)+𝑛(𝑥)+𝛻𝑇(𝑛𝑝⊂𝑃ℎ2𝑖𝑖(𝑥)(𝑥−𝑝𝑖)))（3.24）由高斯曲率𝐾𝐺和平均曲率𝐾𝑚可得到采样点𝑝𝑖的主曲率𝑘1和𝑘2：𝑘1=𝐾𝑚+√𝐾𝑚2−𝐾𝐺𝑘2=𝐾𝑚−√𝐾𝑚2−𝐾𝐺（3.33）3.5实验分析3.5.1法向量估算实验本文法向量的算法分两步，首先使用PCA法全局计算点云模型的法向量，再采用邻域中准确的（平坦区域）法向量迭代加权修正不准确的（特征区域）法向量，本节关于法向量的重点在特征区域的法向量的修正。本算法中需要确定的参数有：建立拓扑关系时的K邻域值、法向量迭代加权中的点集邻域k值、距离带宽𝜎、残差带宽𝜎、法向偏差带宽𝜎以及迭代次数t。由袁小翠[70]可知PCA𝑑𝑟𝑛法中K值的取值范围为8~64，而k值的范围应比K大，所以k可为k=nK，35 第3章散乱点云的微分信息估算(𝑛>1)；距离带宽𝜎𝑑是取采样点到邻域点的最大距离；残差带宽𝜎𝑟不需用户设置，会根据曲面自适应确定。法向量带宽𝜎𝑛对过渡区域较平缓和尖锐的曲面分别取0.2和0.3时效果较理想。迭代次数t随曲面的尖锐程度变化（曲面越尖锐，迭代次数越大），根据实验可知，对于平缓区和尖锐区其迭代次数分别在4次和7次，且对不同类型的模型当迭代次数在最佳效果下继续增加，修正的法向量基本不再改变。本文以规则的圆柱点云模型（n=14193）为实验对象，其中的参考数据分别取值K=20、k=2.5K=50、𝜎𝑛=0.3、t=10进行法向量估算，并与全局PCA法、文献[64]、文献[69]进行比较，并通过法向偏差均方根R和法向偏差大于10°的坏点来估算误差，其结果如图3.4所示。21𝑅=√|𝑠|∑𝑥∈𝑆(𝑓(〈𝑛𝑒𝑠𝑡，𝑛𝑠𝑡𝑎〉))（3.34）〈𝑛𝑒𝑠𝑡，𝑛𝑠𝑡𝑎〉，〈𝑛𝑒𝑠𝑡，𝑛𝑠𝑡𝑎〉<𝜏𝑓(〈𝑛𝑒𝑠𝑡，𝑛𝑠𝑡𝑎〉)=𝜋（3.35）其他2阈值τ的取值，主要由估算法向与标准法向之间的夹角决定，Zhang等[71]去其夹角阈值为10°，则τ=0.9848。图3.4(a)PCA算法(b)文献[65](c)文献[70](d)本文算法图3.4中其红色部分则为法向偏差大于10°的坏点，由图直观的可以看出PCA算法在平坦区域的法向量估算是准确的，坏点全在模型特征点处且特征点处的法向量基本无法估算准确，文献[64]、文献[69]和本文算法都是针对特征点处的法向量进行改进且取得较好的效果。每种算法计算法向量的误差以及耗时如表3-2所示。表3-2误差分析结果表模型参数类型PCA文献[65]文献[70]本文算法R0.33180.05790.03140.0301圆柱体坏点数138381810（n=14193）时间（s）1.610.57.66.836 第3章散乱点云的微分信息估算由表3-2可知，相比于其他算法，本文针对算法在特征点处的法向量修正效果较好，能有效的、准确的估算出特征区域的法向量，并加快了计算速度。为了验证算法对噪声的抗干扰能力，本文对规则的圆柱体点云模型（n=14193）加入50dB和30dB的高斯噪声，取同样的参数对模型进行法向量估算，其结果如图3.5所示。同样以法向偏差均方根R和法向偏差大于10°的坏点作为算法误差分析的根据。计算其误差，其结果如表3-3所示。(a)信噪比50dB的圆柱模型(a)信噪比30dB的圆柱模型图3.5(1)PCA法(2)文献[65](3)文献[70](4)本文算法表3-3加入高斯噪声后的误差结果表模型误差参数PCA文献[65]文献[70]本文算法噪声比R0.35260.08790.04130．034650dB坏点6262876932噪声比R0.86130.52160.45610.314430dB坏点2199998671404由图3.5、表3-2和表3-3可知，本文算法得到的法向量比其他算法得到的法向量的法向偏差均方根都小，坏点所占比例相对低，证明本文算法能快速、有效的处理特征区域的法向量，且对噪声具有较强的抗干扰能力。37 第3章散乱点云的微分信息估算3.5.2曲率估算实验本章关于散乱点云的曲率估算主要分为两步：基于稳健估计技术寻找最优子集和基于移动二乘法估算曲率。通过寻找到的最优子集建立的移动最小二乘曲面认为是最优曲面，直接估算曲面的曲率作为散乱点云的曲率。本算法主要的参数有：高斯核函数的带宽h的选取、影响半径的选择以及自适应最大核密度函数估计中的带宽。自适应最大核密度函数估计中的带宽由标准差决定，所以是不需要用户设定。本文选择的是高斯核函数，高斯核函数的带宽由h=max(|𝑥−𝑥∈𝑁𝑏(𝑥)𝑥𝑖|)自适应确定，其影响半径r=3h。以圆环点云模型（n=4800）和球点云模型（n=10821）为实验对象，如图3.6所示。并与文献[60]、文献[67]和文献[69]的算法进行比较。图3.6圆环模型和球模型本文算法估算出的曲率结果如图3.7所示，本节用平均曲率和高斯曲率的平均计算误差判断算法估算曲率的准确性。其结果如表3-4所示。(a)主曲率k138 第3章散乱点云的微分信息估算(b)主曲率k2(c)高斯曲率𝐾𝐺(d)平均曲率𝐾𝑚图3.7本文算法求出的曲率表3-4曲率结果表模型类型计算误差文献[60]文献[67]文献[69]本文算法高斯曲率0.0080.0240.00670.0052圆环模型平均曲率0.0020.00450.00150.0012（n=4800）时间（s）4.9050.277325.53211.958高斯曲率0.010.0020.0120.0018球模型平均曲率0.0040.00210.000780.00064(n=10821)时间（s）11.0620.1937732.523477.833由上述结果可知，本文算法估算点云的曲率所花费的时间要比文献[60]和文献[67]多很多，但是得出的高斯曲率和平均曲率的平均误差比他们的算法要小很多，估算出的曲率更准确。39 第3章散乱点云的微分信息估算3.6本章小结本章对散乱点云模型的微分信息估算进行了研究，主要集中在曲面法向量的估算，法向量调整以及曲面曲率的估算。对于Prim估算特征区域法向量与标准法向量偏差较大的问题，提出一种用光滑区域准确的法向量迭代修正特征区域的法向量，以PCA估算的法向量作为初始迭代法向量，并对当前邻域进行迭代加权修正法向量，在权值的选取上除了高斯权重和残差因子还增加了法向偏差权重。对最小生成树调整法向量速率慢的问题，从减少查找权值c时所遍历的点数以及增加每次向外扩散的点数两方面进行改进，提高调整法向量的效率。对于求取曲面曲率存在的问题，提出一种基于稳健统计的移动最小二乘曲面法估算曲率，通过自适应窗宽最大核估算获得最佳点子集，以此子集拟合得最优移动最小二乘曲面，再求解得曲面曲率。通过分析法向量和曲率估计误差，并与其他经典算法进行比较，表明本章算法对曲率突变区域的微分信息估算具有较好的鲁棒性，并能准确的得到散乱点云的微分信息。本章计算出的微分信息是下面的边界特征提取以及数据分割的重要依据。40 第4章点云的特征提取第4章点云的特征提取4.1特征提取概述特征主要是指被扫描实物中的特征点、特征线以及特征面等，故点云的特征提取由以上三个方面所组成。点云的特征提取是各项工作以及应用的基础，比如：在快速成型中，用先获得的物体轮廓线输入快速成型机生产出实物模型；在点云配准中，用于不同坐标系间的点云配准；在点云处理中，约束着曲面重构等。点云模型特征线的提取是后续曲面重构的基础，所以本章主要研究点云的特征线提取。点云的特征提取根据点云模型的不同分为基于网格的特征提取与基于散乱点云的特征提取两种方法[72-73]。基于网格的特征提取是在对点云进行网格化后，再分析构成网格的三角面片的特征判断被测物体可能具有特征的地方，该方法不仅需要较多的人机交互操作，还容易在网格划分时切断尖锐边处的特征线，产生碎边，并且无法避免网格构造的繁琐；基于散乱点云的特征提取是指从散乱的点云数据中直接提取出具有一定规律的点、线、面等特征，是后续曲面重构的预处理，其效率和精度直接影响到曲面重构的速率与质量。相对于基于网格的特征提取，散乱点云的特征提取避免了网格构造的繁琐，以及特征线易切断的不足。故本章研究基于散乱点云的提取特征。目前国内外很多学者都对点云的特征提取进行了多方面的研究，但是在这一领域内仍然存在需要改进的地方：（1）算法对噪声较为敏感；（2）自动化程度低，仍需要手动选择种子点；（3）对法向量和曲率变化缓慢的边界特征难以识别；（4）不能保证能形成完整的封闭边界。针对以上问题本章对散乱点云的特征提取，其思路是先在散乱点云模型上使用第二章的搜索K邻域点集；再用第三章的方法进行法向量和曲率估算；再利用基于多尺度检测和平均曲率的特征权值分别对边界特征点和尖锐特征点进行提取，不仅提高算法的普遍适用性还增强了对噪声的抗干扰能力；最后采用过控制点的3次B样条拟合法对特征线进行拟合得到点云模型光滑且精确的特征边界。41 第4章点云的特征提取4.2相关算法研究现状基于散乱点云的特征提取不仅提取的速度快、结果准确，而且还避免了基于网格的特征提取的一系列不足。所以目前，国内外的许多学者都针对散乱点云模型的特征边界提取提出了很多种算法。国外学者Gumhold[74]于2001年首次提出直接基于散乱点云提取特征的方法，将曲面特征点分为平面点、折点、边界点和角点进行提取；Ioannis等[75]于2006年提出一种分区域提取特征的方法，该方法先将点云模型进行分块，再对各小分块分别进行分步提取特征，最后再将每一部分的信息汇总成整个曲面的特征；Kris等[76]于2008年利用优先次序分割的方法提取特征候选点，并连接成线来覆盖尖锐特征线，最后构建一个最小生成树，然后利用重接程序闭合特征线，该方法具有数据量小、高效、特征线闭合等特点。国内许多学者在这方面进行了细致的研究，胡鑫等[77]于2002年根据曲率极值判断并提取特征点；柯映林等[26]于2005年通过点云3R包围盒的思路完成对不同分布点云的边界提取；孙殿柱等[17-18,40]于2008年根据采相邻向量之间的最大夹角来识别特征点；还于2009年根据点集内各点到基准平面的距离与目标点到基准平面的距离进行比较，检测特征点；并于2013年根据k邻域点集核密度估计识别并提取的边界特征点。基于散乱点云的特征提取一般是以点云曲面的法向量、曲率及体积积分不变等为依据提取点云的特征点，这里详细介绍一个基于散乱点云特征提取的典型的算法[17]，来说明点云特征提取的一般流程。该算法其详细步骤如下：1)设有散乱点云集𝑃(𝑖=0,1,2⋯𝑛)，采用R*-tree建立散乱点云的拓扑关𝑖系，并查找采样点𝑝𝑖的k邻域𝑁𝑘(𝑝𝑖)得点集{𝑝𝑖，𝑁𝑘(𝑝𝑖)}；2)以采样点𝑝𝑖和k邻域点集{𝑝𝑖，𝑁𝑘(𝑝𝑖)}为依据，再采用最小二乘法拟合点集的微切平面𝑃𝑙，求取微切平面的法向量作为采样点的法向量n。3)将采样点𝑝𝑖及其K邻域点集{𝑝𝑖，𝑁j(𝑝𝑖)}(𝑗=0,1,2⋯𝑘−1)投影到微切平面𝑃𝑙上，得到投影点𝑝′和投影点集{𝑝′，𝑁′(𝑝)}(𝑗=0,1,2⋯𝑘−1)，再以投影𝑖𝑖𝑗𝑖点𝑝′为起点，连接𝑝′和𝑁′(𝑝)，得到投影向量𝐏′𝐍′，如图所示𝑖𝑖𝑗𝑖𝑖𝑗4)在投影向量中选取某一个投影向量作为基准，比如𝐏′𝐍′为例，再算出其𝑖1他投影向量与基准向量𝑃′𝑁′之间的夹角𝛼，以及除此之外的投影向量与微切平面𝑖1𝑗法向量n之间的夹角𝛽𝑗。𝛽𝑗的范围决定𝛼𝑗在0~360度的范围，若𝛽𝑗<90°，𝛼𝑗不变；若𝛽𝑗≥90°，𝛼𝑗=360°−𝛼𝑗。42 第4章点云的特征提取5)估算出相邻投影向量之间的夹角𝛾𝑗(𝑗=0,1,2⋯𝑘−1)，并将这些夹角按从小到大的顺序进行排列，获得最大的夹角𝛾𝑗。6)识别并提取点云模型的边界特征点。先设置判断边界特征点的阈值ε，若𝛾𝑗≥𝜀，则认为该点是边界特征点，并对其标记；若𝛾𝑗<𝜀，则认为该点不是边界特征点。7)对采样点k邻域点集内的点云数据执行循环操作步骤，直到点云模型中所有点都被识别完为止。由上述可知，要获得点云的特征边界的一般流程如下：先对散乱点云模型建立拓关系搜索采样点k邻域点集，依据采样点及其K邻域点集建立微切平面，获得点云的微分信息，再根据点云的微分信息提取出散乱点云的特征点。虽然国内外学者已经对散乱点云的特征提取做了大量的研究，但仍达不到理想的程度。比如：算法的抗噪声仍然有待提高；人机交互操作繁琐，需提高其自动化水平；算法对相对光滑的边界仍然难以识别，需改进特征提取的依据；算法有时难以确保提取边界的封闭性，需改进其稳定性和封闭性。4.3特征点提取散乱点云的特征点分为：平坦点、尖锐点以及边界点三类。本文主要是对散乱点云的尖锐点和边界点作为特征点进行提取。在进行特征点提取时，都会对每个采样点𝑝𝑖设置一个特征权值ω（该权值基于点云曲面平均曲率确定），该权值使采样点与其有可能成为特征点的概率成正比关系。由采样点的特征权值大小确定是否为特征点（即：特征权值越大，则采样点是特征点的可能性越大；特征权值越小，则是特征点的可能性越小）。但是边界点是一类特殊的特征点，因为边界点的邻域拓扑关系只有一侧，故在用基于平均曲率的特征权值判断非均匀点云的边界特征点时就容易出错[78]。所以，本文将先采用多尺度检测法对边界特征点进行检测识别，并进行标记，再对尖锐特征点进行检测。在对特征点提取前，应该对散乱点云进行一些预处理工作。首先是使用第二章的方法对散乱点云数据建立拓扑结构并进行K邻域搜索，得到点集{𝑝𝑖，𝑁𝑗(𝑝𝑖)}(𝑗=0,1,2⋯𝑘−1)；然后使用第三章中的方法计算点云的法向量n及其曲率（高斯曲率、平均曲率、主曲率等）。43 第4章点云的特征提取4.3.1边界特征点提取在散乱的点云模型上，对于其边界特征点，一般利用采样点与周围点的分布均匀性来识别边界特征点，即：采样点𝑝𝑖的邻域点的分布若偏向一侧，则认为𝑝𝑖为边界特征点；相反若其邻域点在采样点周围均匀分布，则不是边界点。但是该方法只使用于分布均匀的点云，为了也能处理分布不均匀的点云数据，本文采用多尺度检测法对边界点单独进行提取。在得到散乱点云的微切平面𝑃𝑙以及微切平面的法向量n的基础上，利用各向量与基准向量之间的向量夹角判断边界点。对边界特征点的提取步骤如下：1)将采样点𝑝𝑖及其k邻域点集{𝑝𝑖，𝑁𝑗(𝑝𝑖)}(𝑗=0,1,2⋯𝑘−1)投影在微切平面𝑃𝑙上，得到投影点𝑝′和𝑁′(𝑝)；𝑖𝑗𝑖2)以采样点的投影点𝑝′为起点，以其投影点𝑝′的邻域投影点𝑁′为终点，连𝑖𝑖𝑗接成向量⃗𝑃⃗⃗𝑖⃗′⃗⃗𝑁⃗⃗⃗𝑗′，得到向量集；3)计算各向量与基准向量之间的夹角，升序排列并计算夹角集L。4)计算L的最大角度差𝐿𝑚𝑎𝑥，若𝐿𝑚𝑎𝑥>𝛿，则ε++，再改变K值重复步骤1到步骤3；5)若ε=3则认为点𝑝𝑖为边界点，并标记，直到识别完所有边界特征点为止。首先将采样点𝑝𝑖及其K邻域点集𝑁𝑗(𝑝𝑖)(𝑗=0,1,2⋯𝑘−1)向其微切平面𝑃𝑙进行投影，得到𝑝′和𝑁′(𝑝)，其投影点如图所示成散乱分布。设采样点𝑝的坐标𝑖𝑗𝑖𝑖为(𝑥，𝑦，𝑧)(𝑖=0,1,2⋯𝑛)，则投影点𝑝′的坐标为(𝑥′，𝑦′，𝑧′)。则有方程：𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑥′−𝑥𝑦′−𝑦𝑧′−𝑧𝑖𝑖𝑖𝑖𝑖𝑖===𝑘（4.1）𝑎𝑏𝑐𝑎𝑥′+𝑏𝑦′+𝑐𝑧′+𝑑=0（4.2）𝑖𝑖𝑖解有：′(𝑏2+𝑐2)𝑥𝑖−𝑎𝑏𝑦𝑖−𝑎𝑐𝑧𝑖−𝑎𝑑𝑥𝑖=𝑎2+𝑏2+𝑐2′−𝑎𝑏𝑥𝑖+(𝑎2+𝑏2)𝑦𝑖−𝑏𝑐𝑧𝑖−𝑏𝑑𝑦𝑖=𝑎2+𝑏2+𝑐2（4.3）′−𝑎𝑐𝑥𝑖−𝑏𝑐𝑦𝑖+(𝑎2+𝑏2)𝑧𝑖−𝑐𝑑𝑧𝑖=𝑎2+𝑏2+𝑐2𝑎𝑥𝑖+𝑏𝑦𝑖+𝑐𝑧𝑖𝑘=√𝑎2+𝑏2+𝑐2求得投影点𝑝′的坐标。𝑖以投影点𝑝′为起点，连接其它邻域点集投影点𝑁′，得到投影向量𝐏′𝐍′，为了𝑖𝑗𝑖𝑗44 第4章点云的特征提取将投影点进行参数化，把距离𝑝′最近的投影点𝑁′(0≤𝑚≤𝑘−1)的投影向量𝑖𝑚𝐏′𝐍′作为基准方向（X轴），再以垂直该向量方向作为Y轴，得到投影点的参数𝐢𝑚化平面XP′′′iY，投影点𝑁𝑗参数化后的坐标为(𝑁𝑗𝑥，𝑁𝑗𝑦)。以投影向量𝑃′𝑁′为基准向量，分别计算由𝑃′到其他归一化后的投影点𝑁′的𝑖𝑚𝑖𝑗有向向量𝑃′𝑁‘之间的顺时针夹角：𝑖𝑗𝑆=(𝛼1，𝛼2，⋯，𝛼𝑘−1)（4.4）再对其夹角按升序排列得到新的角度序列：𝑆′=(𝛼′，𝛼′，⋯，𝛼′)（4.5）12𝑘−1最后计算出角度序列差：𝐿=𝛼′−𝛼′𝑖∈[0，1，⋯，𝑘]（4.6）𝑖+1𝑖角度序列差L是两个相邻线段之间的夹角，找到L中最大角𝐿𝑚𝑎𝑥，预先设定角度阈值δ，若最大角与阈值满足𝐿𝑚𝑎𝑥>𝛿，则认为采样点𝑝𝑖为边界特征点，一般阈值δ=2𝜋3。K邻域的数值K则是多尺度检测方法的检测窗口，并对每个采样点𝑝𝑖赋予一个尺度权值ε。4.3.2尖锐特征点提取散乱点云尖锐点的信息量可以准确的表示点云模型实物的形状特征，点云的平均曲率是曲面内主曲率之和的平均值，可以表明曲面的凹凸性，所以基于平均曲率的特征权值不仅能够有效的反映尖锐点的特征，还能有效的增强对噪声的抗干扰能力。局部特征权值与该处所含信息含量成正比，而信息量的大小又与采样点是否是尖锐特征点的可能性成正比，即采样点处的特征权值越大，则该点是尖锐特征点的可能性越大。提取尖锐特征点的具体步骤如下：1)对于散乱点云模型建立邻域并搜索得到K邻域点集𝑁𝑗(𝑝𝑖)(𝑗=1,2⋯𝑘)；2)采用第三章的方法以采样点𝑝𝑖及其K邻域点集为依据，拟合得到移动最小二乘曲面，再求得采样点𝑝𝑖的平均曲率𝐻𝑖；3)基于采样点的平均曲率̅𝐻̅̅𝑖，依据以下公式计算出采样点𝑝𝑖的局部特征权值：45 第4章点云的特征提取1𝑘22𝜔(𝑝𝑖，𝑘)=√𝑘∑𝑖(|𝐻𝑞𝑖|−𝐻̅)+√(𝐻𝑖−𝐻̅)（4.7）假设点集P中没有尖锐点，通过上述公式得到最大局部特征权值𝜔𝑚𝑎𝑥，且把𝜔𝑚𝑎𝑥作为判断阈值。其中散乱点集P的平均曲率𝐻̅:1𝑛𝐻̅=𝑛∑𝑖=1𝐻𝑖（4.8）4)采用固定特征检测率法对散乱点云进行判断，对于采样点K邻域中的任一点上的特征权值𝜔(𝑝𝑖，k)>𝜔𝑚𝑎𝑥，则该点为点云的尖锐特征点，并进行标记；5)重复步骤1~4，直到所有的尖锐特征点提取完成。采用固定特征检测率对散乱点云进行尖锐点特征提取，固定特征检测率是根据在不同区域，不同特征权值时，阈值也会随之自适应改变，以确保提取出的特征点云的基本规模不变。散乱点云之间不存在拓扑结构，所以提取的特征点呈现随机分布状态，故需要对提取出特征点进行排序以得到连续的特征线，方便点云的后续处理操作。本文采用钱锦峰等[79]最近点搜索算法完成特征点的排序，其详细操作步骤如下：1)任取所提取的特征点集中任的一点𝑝𝑖作为生长起点，以点集中距离采样点最近的点Pe并将其作为终点；2)对于𝑝𝑖(𝑝𝑒)端，查找距离𝑝𝑖(𝑝𝑒)的最近点P，计算P到𝑝𝑖和𝑝𝑒的距离𝑑𝑠和𝑑𝑒，如果𝑑𝑠(𝑑𝑒)≤𝑑𝑒(𝑑𝑖)，则将P插入到𝑝𝑖(𝑝𝑒)之前，并将点P作为新的起点(终点)；否则往另一端生长；3)以点集中所有点完成判断为标准，是则结束排序；否则转到步骤2。按照以上步骤完成对特征点集的排序，再将排序后的特征点用直线简单连接形成特征线，以便更好的反映出实物的原始边界特征。特征线分为边界线（外边界线与内边界线）和内部主要特征线，特征线的提取依据已经提取出的每个特征点的特征权值，建立最小生成树，连接特征点形成连通区域，最后通过对连通区域内的细碎特征线进行裁剪，则得到点云的主要特征线。特征线提取的具体步骤如下：1)判断边界点是外边界点还是内边界点，其中外边界点可能是不完全连通的；2)根据每个特征点的特征权值，建立最小生成树，构造成连通区域，将特征点连接成线；3)对细碎的特征线进行裁剪剔除，得到点云的主要特征线。46 第4章点云的特征提取4.3.3构建最小生成树根据采样点的特征权值，建立最小生成树，但是对于不是完全连通的外边界，需要设置一个距离阈值𝑑𝑚𝑎𝑥区别特征，所以建立最小生成树的详细步骤如下：1)计算提取出的特征点的特征取值，以具有最大特征权值的特征点作为种子点，加入最小生成树中，建立边集合；2)使集合中的所有边满足边长小于𝑑𝑚𝑎𝑥且两顶点中仅有一个点在最小生成树中，再搜索出该集合中具有最大特征权值的边；3)对于具有最大特征权值边的两个顶点，找到不在最小生成树中的顶点加入最小生成树，并更新边集合；4)重复以上三个步骤，当构建所有的边大于𝑑𝑚𝑎𝑥时则部分特征构造树结束；5)寻找新的特征区域，重复步骤一到步骤五搜索，直到所有的特征点搜索完成。6)将完成搜索的特征点连接成线，即得到特征线。在此方法重建的最小生成树中，存在着很多的短边使特征线出现毛刺的现象。为了不影响数据分割的效果、得到点云的主要特征线，往往将这些短边进行裁剪。本节主要采用裁剪树枝的方法对短边进行剔除，剔除的方式是从数的每个叶子节点开始，向树的根追溯，直到达到分支点，为每个分支点赋予一个相应的权重，权重小的则剔除。最后得到权重大的主要特征。4.4特征线拟合若直接将特征点集进行简单的直线连接以得到特征线，虽然该方法简单快捷，但得到的特征线只是简单的位置连续，并不光滑，不利于后续处理，而大多数复杂模具的边界线一般都是光滑的曲线。本节采用过控制点的B样条曲线构造法，把已提取到的特征点作为B样条曲线的控制点，计算出节点向量，反算出控制顶点和权因子，根据节点矢量、控制顶点等调整特征点进行参数特征线条拟合，实现特征线拟合。4.4.1B样条曲线的定义m阶（m-1次）B样条曲线的定义[80]为：47 第4章点云的特征提取𝐶(𝑢)=∑𝑛𝑑𝐵（4.9）𝑖=0𝑖𝑖，𝑘(𝑢)其中𝑑𝑖(𝑖=0，1，⋯，n)为控制顶点（又名德尔布点），B样条曲线对这n+1个控制顶点进行加权和定义并不通过这些控制顶点，将控制顶点依次连接得到B样条控制多边形，如图所示B样条曲线位于凸多边形的B样条控制多边形内。图4.1B样条控制多边形其中𝑢𝑖(𝑖=0，1，⋯，n)为节点向量，且满足𝑢0≤𝑢1≤⋯≤𝑢𝑛，节点向量定义了B样条曲线的方向。其中𝐵为B样条曲线的基函数，可以由节点向量通过德布尔-考克斯递𝑖，k(𝑢)推出：𝑢−𝑢𝑖𝑢𝑖+𝑚+1−𝑢𝐵=𝐵+𝐵（4.10）𝑖，𝑘(𝑢)𝑢𝑖+𝑚−𝑢𝑖𝑖，𝑚−1(𝑢)𝑢𝑖+𝑚+1−𝑢𝑖+1𝑖+1，𝑚−1(𝑢)其中m决定了B样条上影响曲线上一点取值的相邻控制点的个数（即一点取值的相邻控制顶点比B样条的阶次多1个），同时也是B样条的阶数；m越大，B样条曲线越光滑，但是计算量也越大。m一般取值为4，即为3次B样条曲线。在特殊情况下，规定m=0，并规定0=000𝑢𝑖≤𝑢≤𝑢𝑖+1𝐵={（4.11）𝑖，0(𝑢)1其他4.4.2求解节点向量节点向量本质上决定了B样条基函数，进而决定了对相应控制顶点的加权大小。一条m阶B样条曲线其节点最多可以重复m-1次，否则B样条曲线会被分割成两条不连续的曲线，所以节点向量中的第一个和最后一个节点通常重复48 第4章点云的特征提取m-1次，确保B样条曲线通过第一个控制点和最后一个控制点。m-1次（这里取m=4）B样条插值曲线由n+3个控制顶点𝑑𝑖(𝑖=0，1，⋯n+2)进行控制，它有n+7个节点向量𝑢𝑗(𝑗=0,1,2,⋯,𝑛+6)。针对节点向量的求解主要分为基于插值点和基于控制点确定节点向量两种[81]。本节主要是对已经提取出的特征点采用过特征点的B样条曲线构造法进行特征线拟合，即已有一序列的插值点（特征点），故本节节点向量的求取是基于插值点确定节点向量。基于插值点确定节点向量中，最常用的是均匀参数化。该方法使每个节点区间长度（用向前差分表示）：∆𝑢𝑖=𝑢𝑖+1−𝑢𝑖=正常数，𝑢𝑖=𝑖(𝑖=0,1,2,⋯,𝑛)，对节点向量进行规范化使𝑢′𝜖[0，1]，即𝑢′=0，𝑢′=1𝑖0𝑛′𝑖𝑢𝑖=(𝑖=1,2,⋯,𝑛−1)（4.12）𝑛这种参数化适用范围较小，只有在数据点多边形各边接近相等的情况下才能准确的求解；在相邻段弦长相差较大的情况下，生成的插值曲线，弦长较长的曲线段明显扁平，弦长较短的曲线段则模糊，甚至出现非连续的尖点或打圈自交的情况。为了避免上述方法存在的问题，准确反映真实数据点按弦长的分布情况，采用积累弦长参数化法。该方法使每个节点区间长度与对应的曲线上的两点之间的弦长对应起来。使：𝑢0=0𝑢𝑖=𝑢𝑖−1+|∆𝐶𝑖−1|𝑖=1，2，⋯，𝑛（4.13）其中∆𝐶𝑖−1=𝐶𝑖−𝐶𝑖−1是向前差分向量（又称为弦线向量），设弦长总和为d：𝑑=∑𝑛|𝐶−𝐶|（4.14）𝑖=1𝑖𝑖−1对节点向量进行规范化后得：𝑢0=0，𝑢𝑛=1（4.15）|𝐶𝑖−𝐶𝑖−1|𝑢𝑖=𝑢𝑖−1+（4.16）𝑑该方法得到的节点向量如实的反映了数据点按弦长的分布情况，且得到的拟合特征曲线也具有较好的光顺性。49 第4章点云的特征提取4.4.3过控制点拟合特征线B样条曲线具有居于性和光滑性，这样直接用B样条曲线拟合的特征线并不通过控制点，所以拟合的特征线的精度不高。所以本文采用一种过控制点的3次B样条曲线来拟合特征线。等距分布节点的3次B样条基函数为：0𝑥∈(𝑥𝑖，𝑥𝑖+4)12𝑢𝑥∈(𝑥𝑖，𝑥𝑖+1)61(1+3𝑢+3𝑢23)𝑥∈(𝑥𝐵𝑖，3(𝑢)=−3𝑢𝑖+1，𝑥𝑖+2)（4.17）61(4−6𝑢23)𝑥∈(𝑥+3𝑢𝑖+2，𝑥𝑖+3)613(1−𝑢)𝑥∈(𝑥𝑖+3，𝑥𝑖+4)3其中𝑢=𝑥−𝑥𝑗，u∈[0,1](𝑗=𝑖，𝑖+1，𝑖+2，𝑖+3)这种过控制点的B样条曲线构造法是将理论控制点直接用实际控制点表示，令用于插值n+1个数据点𝑝𝑖(𝑖=0,1,2,⋯,𝑛+3)的3次均匀B样条为：(𝑡)=1(1−3𝑡+3𝑡23)𝑑1(4−6𝑡23)𝑑1(1+3𝑡+3𝑃𝑖−𝑡𝑖++3𝑡𝑖+1+66623)𝑑13𝑡−3𝑡𝑖+2+𝑡𝑑𝑖+3（4.18）6且满足𝑃𝑖(0)=𝑝𝑖(𝑖=0,1,⋯,𝑛)带入上式得：121𝑑0+𝑑1+𝑑2=𝑝06361216𝑑1+3𝑑2+6𝑑3=𝑝1（4.19）⋯121𝑑𝑛−3+𝑑𝑛−2+𝑑𝑛−1=𝑝𝑛−3636其中，理论控制点是𝑑𝑖，实际控制点是𝑝𝑖，这里有n−2个方程和n个未知数，为了使方程有解，故再增加两个边界条件：𝑃0(0)=𝑞0，𝑃𝑛−3(0)=𝑞𝑛−3。带入公式即得：1(−𝑑0+3𝑑2)=𝑞021(−𝑑𝑛−3+3𝑑𝑛−1)=𝑞𝑛−3（4.20）2联合前面n-2个方程求解，得到过控制点的拟合B样条曲线，曲线也就是所50 第4章点云的特征提取求的特征线。4.5应用实例及分析本章提出的散乱点云特征提取算法，主要需要设定K邻域的值和多尺度检测法中的角度差阈值δ。为验证算法的可行性和有效性，在个人笔记本上以Mircosoftvisualstudio2010和OpenGL技术为实验平台，针对不同三维点云模型进行实验。4.5.1简单模型的特征提取1.特征点提取本文以汽车挡泥板点云模型（n=6208）为实验对象，如图4.2所示。取K=220和δ=𝜋对汽车挡泥板点云模型进行特征提取，并与文献[21]中的算法进行比3较。图4.2挡泥板点云模型原始点云本章算法首先依据第二章K邻域搜索的得到的K邻域点集和第三章中估算的法向量建立微切平面，采用多尺度检测法提取模型的边界特征点，其结果如图4.3（a）所示，文献[21]提取的边界结果图如图4.3（b）所示。51 第4章点云的特征提取(a)本文算法提取(b)文献[21]算法提取结果图4.3特征点提取结果图2.特征线拟合对于提取出的特征点排序后直接连接成的特征线，其效果很不好。本文提取出的特征点直接连接成特征线的结果如图4.4（a）所示，文献[21]直接连接的结果如图4.4（b）所示。52 第4章点云的特征提取局部放大图局部放大图(a)本文未拟合特征线结果(b)文献[21]未拟合特征线图4.4未拟合特征线结果由图4.4可知，直接连接特征点提取的特征线，无法得到光滑准确的特征线。本文采用过控制点3次B样条构造拟合特征线，文献[21]则是直接采用B样条曲线拟合，其拟合结果若图4.5所示。局部放大图局部放大图(a)本文算法拟合结果(b)文献[21]拟合结果图4.5拟合特征线本节用平均距离偏差𝑑̅和均方差σ对拟合的特征线进行误差分析。距离偏差53 第4章点云的特征提取即拟合的特征线与原始模标准型特征线之间的偏差，单位为mm。误差计算公式如下：1𝑛𝑑̅=𝑛∑𝑖=0𝑑𝑖，(𝑖=0,1,2,⋯,𝑛)（4.21）1𝑛2𝜎=√𝑛∑𝑖=0(𝑑𝑖−𝑑̅)（4.22）本文的误差结果如表4-1所示。表4-1误差结果表算法平均距离偏差（𝑑̅）mm均方差σmm时间ms文献[21]0.12980.111848本文算法0.09160.077635由上述结果可知，本章提出的基于散乱点云的特征提取算法在特征提取的时间以及拟合特征线的效果要比文献[21]较好，所以本章所提算法可快速、准确的提取散乱点云模型的特征。4.5.2复杂模型的特征提取为验证算法的有效性和适用性，再以机械零件点云模型（n=38573）为实验对象进行特征提取，如图4.6所示。图4.6点云原始模型2对模型进行特征提取，取参数K=20和δ=𝜋进实验，先提取模型的边界特3征点（823个特征点），如图4.7(a)所示；再提取到模型的尖锐特征点（901个特征点），如图4.7(b)所示。54 第4章点云的特征提取(a)边界特征点(b)尖锐点图4.7特征点提取结果再对所有提取的特征点云进行排序整合，其结果如图4.8所示。图4.8点云模型的特征点提取结果最后使用过控制点3次B样条构造对特征点进行特征拟合，其拟合结果如图4.9所示。图4.9特征线拟合结果该模型提取的特征线的误差结果，其平均距离偏差为0.1087mm，均方差为0.0967mm，共耗时215ms。由上述实验可知，本章提出的特征提取算法主要改进在于特征线拟合上，其拟合特征线的结果较好，速度较快，并且适用于不同类型的点云模型。55 第4章点云的特征提取4.6本章小结本章对基于散乱点云的特征点提取和特征线拟合展开了研究。提出一种基于多尺度边界检测和平均曲率的特征点提取方法与过控制点B样条拟合特征线的方法。对于特征点提取，用相邻法向偏差识别并提取边界特征点，再用基于平均曲率的特征权值识别尖锐点。以过控制点3次B样条曲线构造法进行特征线拟合，将理论的控制点直接用实际控制点来表示进行插值拟合。对不同模型进行实验验证了算法能准确、快速提取点云的特征点，并对噪声具有较高的抗干扰能力；在特征线的拟合方面有一定的改进，提取特征线能保证特征拟合的精度，并快速、准确的得到光滑的特征线。56 第5章基于聚类的混合数据分割第5章基于聚类的混合数据分割5.1数据分割概述实物模具的曲面通常由平面、球面、圆锥面等多种类型的曲面混合组成[82]。对于任何拓扑结构的点云模型而言，为了更好地处理点云数据，也为了获得更好的曲面重构模型，必须针对所得的点云数据按照不同的曲面类型进行分割，形成一个个代表不同曲面类型的数据域，即数据分割[83]。能否进行有效的数据分割直接关系着后续曲面重建的质量与效率。目前对于散乱点云的数据分割算法主要有以下四种：基于边的分割算法、基于面的分割算法、基于聚类的分割算法以及混合分割算法[84]。基于边的分割算法主要依据突变的法向量和曲率来识别边界，但是又不容易得到全封闭的边界；基于面的分割算法主要依赖种子点延伸的区域生长方式，将曲率、法向量相似的区域分割在一起，但是难以确定种子点以及其区域生长方式；基于聚类的分割算法是根据点云模型的几何特征将点云模型分割成具有相似属性的不同区域，该种分割方法既适用于网格模型也适用于点云模型；基于混合的分割方法主要是将基于边和基于面的结合起来，在一定程度上克服单独使用基于边或者基于面的分割方法所存在的不足。虽然针对这一领域已有学者做了较多的研究，但是仍然存在很多不足：（1）难以提取准确的边界点（尖锐边、跳跃边、过渡边）；（2）对噪声敏感；（3）自动化程度不高，仍需要人机交互操作，不能实现全自动化分割；（4）计算量大，耗时，自适应程度不高等。针对以上问题，本文在数据分割这一重要环节上，提出一种基于聚类的混合分割算法，利用改进的K均值算法对点云模型进行全局聚类粗分割，划分出平坦区域和含有特征点的区域；针对含有特征点的区域采用基于高斯球的均值漂聚类（Mean-shift）方法进行细分割；再运用区域生长对分割后的区域进行调整，最终获得较好的效果。57 第5章基于聚类的混合数据分割5.2相关算法研究现状聚类算法顾名思义即：依据某种相似属性按“物以类聚”的准则将数据进行归类[85]。其基本原理是：设定m个数据点，在m维空间中，定义点与点之间某一种特性的亲疏距离；设m个数据点组成n类（n≤m），接着定义距离最近的两类可分为一类，然后重新算出剩下类之间的距离，并进行迭代运算截至其中任意两类之间的距离均大于预定的域值，或者类的总数小于设定的个数[86]。目前，国内外学者总结了基于聚类的数据分割方法的研究现状，提出了多种改进的方法。2002年，Shlafman[87]利用k均值聚类法对点云模型实行数据分割，结果生成了凹状的边界线造成效果不佳。2003年，Katz[88]优化了Shlafman的方法，形成了模糊聚类的层次分解算法。2006年，Yu-Kun等[89]提出了一种自适应聚类的层次分解算法，利用积分不变量来计算局部特性，算法具有比较高的效率和健壮性。2012年，李海伦等[90]提出了基于遗传算法的模糊聚类法，该法能快速、有效的完成数据分割。2015年，王春晓等[91]采用密度聚类对点云数据进行分割，能快速有效的对不同模型的数据进行分割。本章详细介绍了基于模糊聚类的分割算法，其是基于最小二乘法，通过隶属度和欧氏距离构造一个目标函数，接着对该目标函数在隶属度极值约束条件下依次对隶属度和聚类中心进行求导，最终得到新的隶属度和聚类中心，并通过对目标函数进行迭代优化完成对数据的分类[92]。算法的详细步骤如下：1)对点云数据𝑝𝑖(𝑖=0,1,2,⋯,𝑛)构建K邻域；2)根据采样点及其K邻域点集信息拟合微切平面，得到点云的法向量；再拟合二次曲面求得到点云的曲率；3)对聚类中心进行编码并产生初始种群；4)对初始种群解码并按照适应度公式得到每点的适应度值；其值越大聚类的效果越好，因此常需要通过多次迭代获得最优的适应度值；5)确定点云数目n、聚类分区数c以及加权指数m，每一步用r标记，初始r=0；由步骤4得到的最优适应度值获得最小的目标函数，并得到初始聚类中心𝑋0={𝑥0，𝑥1，⋯，𝑥𝑐}；6)根据以下公式分别计算得到新的隶属度𝑈𝑟和新的聚类中心𝑋𝑟+1：2−1𝑐𝑑𝑖𝑘𝑚−1𝑢𝑖𝑘=[∑𝑗=1(𝑑)]（5.1）𝑗𝑘58 第5章基于聚类的混合数据分割1∑𝑛(𝑢)𝑚𝑥𝑖=∑𝑛(𝑢𝑚𝑘=1𝑖𝑘𝑝𝑘（5.2）𝑘=1𝑖𝑘)7)当‖𝑥𝑟−𝑥𝑟+1‖≤𝜀，则结束并输出隶属度矩阵U和聚类中心X，得到聚类结果。由上述可知聚类分割算法一般思想是首先需要对散乱点云数据进行预处理（建立K邻域、估算点云微分信息等），再根据点云不同的特征建立目标函数，再通过迭代得到最优的目标函数（得到最优的聚类中心和隶属度），从而得到数据的聚类结果实现对点云数据的分割。5.3聚类算法定义5.3.1K均值聚类K均值聚类是一种动态聚类算法，其基本思想为：在提前确定分区的初始个数K、初始聚类中心X、迭代次数c以及收敛条件的前提下，再根据相似性度量准则将每个数据点划分到最近的聚类区域内形成一个类，计算出每个类的重心做为其聚类中心，最后反复迭代直到目标函数收敛或者达到最大的迭代次数为止[86,93-94]。设有点云数据集P={𝑝，i=1,2,⋯,n}，将点云数据分成K个类，并𝑖有K个初始聚类中心X={𝑥𝑗,𝑗=1,2,⋯,𝑘}，则K均值聚类的目标函数为：𝐶=∑𝑘∑𝑑(𝑝，𝑥)（5.3）𝑖=1𝑗∈𝑥𝑗𝑖𝑗𝑖𝑗其中𝑑𝑖𝑗(𝑝𝑖，𝑥𝑗)表示任意采样点到该点所在类的聚类中心的距离。因为目标函数的值越小，代表聚类分割的效果越好，所以一般通过减小目标函数值来优化聚类。𝑗2𝑑𝑖𝑗(𝑝𝑖，𝑥𝑗)=‖𝑝𝑖−𝑥𝑗‖（5.4）𝑗其中𝑝𝑖表示采样点𝑝𝑖是属于第j个类中的点。K均值聚类的过程就是寻求目标函数的最小值，获得最优的聚类中心。当目标函数值最小时，将目标函数对聚类中心𝑥𝑗进行求导，并令其为零，推到出聚类中心的求解公式：1𝑛𝑗𝑗𝑥𝑗=𝑛∑𝑖=1𝑝𝑖（5.5）K均值聚类算法的难点在于：（1）点云分区个数K的取值；（2）聚类算法的初始聚类中心的确定；（3）容易陷入局部最优解。59 第5章基于聚类的混合数据分割5.3.2点集的高斯映射定义1.高斯映射的定义及性质正则曲面S=(𝑢,𝑣)⊂𝑅3，该曲面的法向量具有全局统一性（法向量全指向曲面的同一侧）。设曲面S上的任一区域w，以曲面w中任意一点P(𝑢,𝑣)处的单位法向量n(𝑢,𝑣)的始端为球心建立一个单位球𝑆2={(𝑥,𝑦,𝑧)∈𝑅3|𝑥2+𝑦2+𝑧2=1}，则单位法向量n(𝑢,𝑣)的末端则在单位球面上，设落在球面上的该点为𝑞。即P(𝑢,𝑣)∈𝑤与球面上法向量n(𝑢,𝑣)末端一一对应，则曲面S上的任一面积w与球面上固定的一面积𝑤′一一对应，则称这种对应关系为高斯映射G[95]，记为：𝑆→𝑆2。性质5.1：设Bc是分隔连通曲面S1和S2的尖锐边。则存在点p∈Bc的连通邻域U，满足G(U)不连通，G(U)=G(U1)∪G(U2)，且G(U1)∩G(U2)＝Ø，其中U1⊂S1，U2⊂S2。性质5.2：设Bt是分隔连通曲面S1和S2的过渡边，S1和S2沿Bt的高斯曲率值不等。则存在点p∈Bt的连通邻域U，满足U=U1∪U2，U1∩U2=Ø，且U1和U2的面积相等，而G(U1)和G(U2)的面积不相等，其中U1⊂S1，U2⊂S2。性质5.3：假如某一连通曲面的任意点为平点，那么这个曲面的高斯图是高斯球上的某一点；相反，假如某一连通曲面的高斯图是高斯球上的某一点，那么这个曲面的任意点都为平点。性质5.4：假如某一连通曲面的任意点为抛物点，那么这个曲面的高斯图是高斯球上的某一条曲线；相反，假如某一连通曲面的高斯图是高斯球上的某一条曲线，那么这个曲面的任意点都为抛物点。2.点集的高斯映射如果无法预先直到输入数据的曲面模型，那么必须将高斯映射从曲面拓宽到点集上。令点集P={𝑝,𝑖=1,2,⋯,𝑛}为曲面的点云数据，其中𝑝∈𝑅3，由于𝑖𝑖无法确定独立点的法向量，故需对该点及其近邻域通过最小二乘法拟合局部平面，将平面的单位法向量n(𝑝𝑖)称点𝑝𝑖处的法向量，通过第三章中法向量的估算方法求取所有点的法向量，再调整法向量使其具有全局一致性。则G(𝑃)={𝑛(𝑞)|𝑞∈𝑃}称为点集P的高斯图，映射G：P→G(𝑃)被称为点集P的高斯映射。定义点集P中一点q处的采样密度是：𝐷(𝑞)=∑𝑛ℎ(‖𝑝−𝑞‖2)𝜇(𝑝)（5.6）𝑖=1𝑖2𝑖60 第5章基于聚类的混合数据分割其中μ(𝑝𝑖)是点𝑝𝑖处的加权值，h(𝑥)为分段连续函数。且满足：∞∫ℎ(𝑥)𝑑𝑥<∞（5.7）0对于一点其高斯图的密度与该点附近区域所含的点数成正比，因此可以利用某点的密度来了解实物的特征，理论上平面与平面所形成的边界在高斯图中重合于一点，但是实际上因为在特征区域法向量的求取存在较大的偏差使得在高斯球上存在多点，影响了高斯图的形状[96]。5.3.3均值漂移聚类算法均值漂移聚类算法是一种高效统计迭代的无参聚类方法，是一个自适应梯度上升搜索采样点的密度极值获得聚类个数的过程[97-98]。设d维空间𝑅𝑑中采样点集P{𝑝𝑖，𝑖=1,2,⋯,n}，用核函数𝐾𝑝和带宽矩阵𝐻𝑖描述采样点的核密度𝑓̂𝑘(𝑝):11−𝑛−2𝑓̂𝑘(𝑝)=∑𝑖=1𝜔(𝑝𝑖)|𝐻𝑖|2𝐾(𝐻(𝑝−𝑝𝑖))（5.8）𝑖其中每个采样点的权重ω(𝑝𝑖)都为正，且满足∑𝜔(𝑝𝑖)=1；其中核函数K(𝑝)=𝑐𝑘‖𝑝‖2，且c为归一化的常数，核函数满足非负、非增及分段连续且积分为1的要求，一般的核函数包括高斯核函数、均值核函数以及Epanechnikov核函数；其中(𝑝−𝑝𝑖)是类重心p与采样点𝑝𝑖的偏移向量。故点云核密度的函数可表示为：1𝑛−2𝑓̂𝑘(𝑝)=∑𝑖=1𝜔(𝑝𝑖)|𝐻𝑖|2𝑐𝑘𝑘(‖𝑝−𝑝𝑖‖𝐻)（5.9）𝑖其中马哈拉诺比斯距离‖𝑝−𝑝‖2=(𝑝−𝑝)𝑇𝐻−1(𝑝−𝑝)。对每一点的核函𝑖𝐻𝑖𝑖𝑖𝑖数加权求和得到概率密度估计函数𝑓(𝑝)，并分别对密度函数和概率密度估计函数进行求导得到核密度函数的估计梯度∇̂𝑓𝑘(𝑝)和概率密度估计梯度∇𝑓̂𝑘(𝑝)：𝛻̂𝑓𝑘(𝑝)=𝛻𝑓̂𝑘(𝑝)（5.10）1𝑛𝑛−−12𝛻𝑓̂𝑘(𝑝)=∑𝑖=1𝜔(𝑝𝑖)𝛻𝐾(𝑝−𝑝𝑖)=2𝑐𝑘(∑𝑖=1𝜔𝑖|𝐻𝑖|2𝐻𝑖𝑔(‖𝑝−𝑝𝑖‖𝐻))∙𝑖𝑀𝐻(𝑝)（5.11）𝑖1𝑛−−12其中2𝑐𝑘(∑𝑖=1𝜔𝑖|𝐻𝑖|2𝐻𝑖𝑔(‖𝑝−𝑝𝑖‖𝐻))为采样点𝑝𝑖的无参数密度估算，其𝑖61 第5章基于聚类的混合数据分割中𝑀𝐻(𝑝)为均值漂移向量，是均值漂移的迭代公式。𝑖𝑀𝐻𝑖(𝑝)=𝑚𝐻𝑖(𝑝)−𝑝（5.12）1∑𝑛𝜔−2𝐻−1𝑔(‖𝑝−𝑝2)𝑝𝑖=1𝑖|𝐻𝑖|𝑖𝑖‖𝐻𝑖𝑖𝑚𝐻𝑖(𝑝)=1（5.13）∑𝑛𝜔−2𝐻−1𝑔(‖𝑝−𝑝2)𝑖=1𝑖|𝐻𝑖|𝑖𝑖‖𝐻𝑖通过上述公式可得均值漂移向量随概率密度估计梯度成正比，且比例系数为常数，故密度变化最大的方向与梯度的方向一致，即均值漂移向量沿着数据点分布密集的方向漂移。均值漂移算法收敛的充要条件是：如果核函数K(𝑝)满足有一个凸的、单调非增的轮廓函数k(𝑝)，则序列{𝑚𝑗}和{𝑓(𝑚𝑗)}是收敛的，并且{𝑓(𝑚𝑗)}单调递增。5.4基于聚类的混合分割本文提出一种基于多种聚类的混合分割算法，其主要思路为首先利用基于遗传算法的K均值聚类法对点云模型进行粗分割，分割出平坦区域与特征区域；针对特征区域采用基于高斯映射的自适应均值漂移聚类法进行特征细分割；再利用区域生长法对细分割后的区域进行调整，最后快速、准确的得到点云的数据分割。为了改善K均值算法容易陷入局部极值的缺点，本文引入了遗传算法，将两种算法进行融合可避免陷入局部极值；同时针对特征区域无法确定分割类个数的问题，本文提出采用无参聚类的均值漂移法对特征区域进行分割，可以快速、准确的得到点云的数据分割，同时可避免特征的过分割和欠分割现象。5.4.1基于遗传算法的K均值聚类基于遗传算法的K均值聚类算法，同时继承了K均值的局部最优解和遗传算法的全局最优解，使其能快速并准确的分割出平坦区与特征区。算法的难点在K区域个数的确定和初始种群等参数的确定。其算法的详细分割步骤如下：1)K邻域建立：根据第二章的方法以及自适应空间球算法对散乱点云数据建立邻域关系。2)微分信息估算：采用第三章的方法建立采样点的微切平面并拟合曲面，最终获得曲面的法向量、高斯曲率及平均曲率等微分信息；62 第5章基于聚类的混合数据分割3)编码与产生初始种群：将n个散乱点云分成K类，聚类中心集为X{𝑥𝑗，j=1,2,⋯,k}进行浮点数编码。每个聚类中心𝑥𝑗都有一组参数与之对应。4)采用K均值聚类：为了使目标函数获得最小值，采用类间距离𝑑𝑘=𝑖1𝑘1𝑛𝑗𝑗min𝑗[𝑑𝑖𝑗]作为收敛条件，利用公式𝑥𝑗=𝑛∑𝑖=1𝑝𝑖求出K个新的聚类中心；5)适应度值计算：适应度值的大小关系着下一种群的好坏及其数量，其值2越大，则分割的效果越好，即最小聚类中心间距‖𝑥𝑖−𝑥𝑗‖应大些，而平均聚类1𝑘𝑛𝑖2中心内距𝑘∑𝑗=1(∑𝑖=1‖𝑝𝑗−𝑥𝑖‖𝑛𝑗)应尽小些；2𝑚𝑖𝑛‖𝑥𝑖−𝑥𝑗‖𝑓=1𝑘𝑛𝑖2（5.14）𝑘∑𝑗=1(∑𝑖=1‖𝑝𝑗−𝑥𝑖‖𝑛𝑗)6)自适应生成K值：把种群中拥有最大适应度值的个体作为最佳聚类数的样本，其他个体的长度向其接近。假如K变大，则加入距离最大聚类中心最远的点；假如K变小，则当任两个聚类中心的间距达到最小值时，合并着两个聚类中心。此时聚类中心是原先两个聚类中心的平均值；7)遗传操作：a)选择：当子个体差异度大于原个体差异度时可选择进行遗传操作。差异度计算公式为：(𝑖))=𝑡∑𝑘∑𝑘‖𝑥𝑑(𝑥𝑗𝑘(𝑘−1)𝑥=1𝑦=1𝑥𝑖−𝑥𝑦𝑖‖（5.15）其中0
此文档下载收益归作者所有
