保留边界特征的点云简化算法.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：1.80M 资料格式：pdf 举报版权申诉

d4ce13aa-2006-4aa8-b52f-6fde83b70ccc.pdf-第1页.png

第1页 / 共7页

d4ce13aa-2006-4aa8-b52f-6fde83b70ccc.pdf-第2页.png

第2页 / 共7页

d4ce13aa-2006-4aa8-b52f-6fde83b70ccc.pdf-第3页.png

第3页 / 共7页

d4ce13aa-2006-4aa8-b52f-6fde83b70ccc.pdf-第4页.png

第4页 / 共7页

d4ce13aa-2006-4aa8-b52f-6fde83b70ccc.pdf-第5页.png

第5页 / 共7页

d4ce13aa-2006-4aa8-b52f-6fde83b70ccc.pdf-第6页.png

第6页 / 共7页

d4ce13aa-2006-4aa8-b52f-6fde83b70ccc.pdf-第7页.png

第7页 / 共7页

文本预览

第23卷第l期 2013年1月黑龙江科技学院学报 Joumal of Heilon商iang Institute of Science&Techn0109y V01．23 No．1 Jan．2013 保留边界特征的点云简化算法赵伟玲，谢雪冬， (黑龙江科技学院现代制造工程中心。程俊廷哈尔滨150027) 摘要：为有效简化点云数据，提出保留边界特征的点云简化算法。该算法利用三维栅格划分法建立散乱点云的空间拓扑关系，计算每个数据点的近邻，通过球拟合法求得其曲率和具有方向性的法向量，采用投影点个数比值法找到并保留点云边界，根据具体情况设定所需阈值，对非边界点进行分类，通过对点的曲率与平均曲率比较、近邻保留点与近邻点个数比例，完成，占、云简化。实验结果表明：该算法不仅能对点云进行直接有效地简化，而且还能很好地保留点云模型的细节特征。简化比例达25％一40％。该方法可以满足不同种类点云简化的要求，能够提高计算机运行效率。关键词：散乱点云；数据简化；法向量；曲率；边界特征提取 doi：10．3969／j．issn．167l一0118．2013．01．018 中图分类号：TH391．41 文章编号：167l一0118(2013)01—0083—06 文献标志码：A ReSearCh On pOInt ClOUd simplifiCatiOn with bOunda featU reS reSe r、，atiOn zHAo Wea汛g，xlE Xuedong。CHENG Jt‘nting (Modem Manufacture Engineering Center，Heilon西iang Institute of Science&Technology， Harbin 150027，China) Abstract：This paper pmposes a simpli6cation method for point cloud with boundary feature reserva— tion for efkctiVe simpli6cation of the point cloud．This algorithm eonsists of nrstly using the 3 D grid sub- division method to represent the spatial topology relationship of the scattered point cloud and calculate the 七一nearest neighbors for each data point，using the ball—fitting method to simply compute the curvature and the directional no瑚al Vector，and lhen identifying and reserving all￡he boundary points aceording to lhe ratio of the number of pr10jected points，setting the desired thresholds by the specific situations，and clas- sifying the non—boundary points thI．ough these thresholds，and 6nally simplifying the scattered point cloud according to compaTative study of curvature and mean cunature of the points and the proponion of re— senred points in their后·nearest neighbors．The algodthm is Veri6ed by reducing some typicaI point cloud cases with Various su—．ace features．rI'he expenmental results indicate that the algorithm，marked by set— ting the threshold size according to simpli6cation requirements，allows the direct and efkctive reduction of point cloud，while preserving detail fbature of point cloud model，with a simpli6cation proportion up to 25％～40％．This method can fumll the requirements for simplifying difbrent point cloud and improve the e侬ciency of computer operation． Key words：scattered point cloud；data simpli6cation；no珊al vector；cun，ature；boundary extraction 收稿日期：2013一01一06 基金项目：国家自然科学基金项目(51075128)；国家科技重大专项项目(2010zx04016一012)；博士后研究人员落户黑龙江科研启动资助金项目(LBH—Q12019) 第一作者简介：赵伟玲(198l一)，女，河北省保定人，讲师，硕士，研究方向：逆向工程、计算机视觉、数据处理，E—r11ail：weilin孕hao@126．com。万方数据

黑龙江科技学院学报第23卷 O 引言为精确快速地获取工件表面的尺寸信息，非接触的三维光学扫描设备已被广泛应用在生产线上。由测量所得到的通常包含大量数据点的数据能很好地描述物体表面信息，但是大规模的点云给准确快速的三维重建或其他的后续处理带来了很大的困难。为更有效地表达和绘制三维点云模型，需要对点云进行合理的简化。近年来，国内外学者提出了针对不同类型点云的简化算法。对于扫描线点云数据，可以采用均匀采样法、角度偏差法、弦高差和角度弦高法等…。针对网格点云数据．Chen等∽o提出了一种减少三角网格数目，删除部分数据点的方法。针对目前最常见的散乱点云数据类型，Sun等旧’提出包围盒法简化数据。洪军‘4 J 改进了包围盒算法，利用包围盒法构造分割面，由分割面将数据点云处理成按扫描线存储的“结构化” 测量数据，再利用角度一弦高联合准则法逐线精简。殷金祥【51利用数据点周围以R为半径的球进行测量，得到测量球内的临近点数量作为该数据点面密度，以面密度确定曲面凹凸弯曲程度，进而确定点的简化距离阈值和精简数据点集。张丽艳∞1提出基于三种原则的简化算法，即按简化后的个数、点云密度以及删除一点后引起的法向偏差进行简化。Lee 等【7 o以数据点的法矢为判据，对点云进行空间栅格细分，在每个栅格上选择1个特征点。近几年，有文献悼“叫提出了基于聚类和相似性的点模型简化方法。笔者研究了一种在保留边界特征基础上简化点云的有效方法。该算法，首先利用三维栅格划分法计算出每个数据点的近邻，通过球拟合法计算出点的法向量和曲率，接着通过投影点个数比值法找到并保留点云边界，然后根据具体情况设定所需阈值，对非边界点进行分类，通过对点的曲率与平均曲率比较、近邻保留点与近邻点个数比例，进行点云简化。 1 点云预处理 1．1 点云的空间划分与邻域搜索测量得到的散乱数据只包含数据点的三维坐标值，点与点之间没有明显的几何分布信息，因此，必须建立数据点云之间的拓扑关系以及搜索每个点对应的晟个最近邻域。文中采用空间栅格划分法搜索万方数据点的忌个邻域，此方法在求某点的矗邻近时，不需要在整个点云中搜索，而只需在相应的小立方体栅格中搜索即可。 1．1．1 空间栅格划分数据点p的最近矗个点称为p的知一邻域，记为 Ⅳ6M(_p)。首先，读入点云数据，计算测量点云数据的z、八z坐标的最小值和最大值，得到所有数据的最小长方体空间[并。i。，算。。；]，[y…，y。；]，[彳。∽ z。。。]，通过栅格边长￡的设定，将长方体包围盒按三个坐标方向划分成m×n×z个小立方体栅格，其中 m=(戈m。。一戈mi。)／L，n=()，m。。一)厂mi。)／L，Z=(彳max— z。i。)／L。然后，把每个数据点分配到相应的小立方体栅格(m，，n，，f，)中，其中m，=(戈，一菇岫)／￡，～= ()，，一ymi。)／￡，fP=(z，一zmi。)／￡。将数据点的序号追加到该立方体栅格对应的链表中。由于每个子空间内含有数据点的个数是未知的，为了节省存储空间采用链表的结构来存储。先给每个子空间分配一个固定长度的存储空间，如果存储空间不够可以动态地再次分配。 1．1．2忌最近邻域搜索方法首先，计算该点所在立方体栅格的索引号，然后，在其所在的立方体栅格及其顶点相邻的上下、左右、前后共27个小立方体栅格中查找后个最邻近的点，并按相邻点到戈。的距离瓠f由小到大的顺序进行排序。如果在这27个栅格中相邻点不够尼个，这样就必须继续搜索外层栅格，即与27个栅格外侧表面相邻的栅格，达到南个点便可以结束。 1．2不需调整方向的点法向量与曲率计算在数据简化中，点云法向量和曲率的计算是关键预备工作之一。测量数据很密集，在小范围内理想意义上所在的曲面应该是很光滑的，所以任何点的局部邻域都可以用平面或者曲面进行很好地拟合。但是拟合平面得到的法向量方向是两个方向，这样就需要对法向量方向进行适当的调整。曲率计算常见的方法是基于法向量的局部坐标系，利用最小二乘法拟合简化抛物面，计算得到拟合抛物面的两个主曲率，其中两个主曲率的平均值称为平均曲率。由于平均曲率更能反应曲面的弯曲特性，所以，一般取平均曲率作为曲面曲率的衡量标准。这样点p的曲率定义为点Ij}近邻拟合抛物面的平均曲率。上述介绍求取点云的法向量需要进行方向调整，常见计算曲率的方法也比较复杂。在曲率大的地方可用半径小的球面拟合，在曲率小的位置可用半径大的球面拟合，所以在近邻小范围内可选用球

第1期赵伟玲，等：保留边界特征的点云简化算法 85 拟合。球面的法向量方向是唯一的，免去了法向量调整这一过程，也可以很简便得到对应点的曲率，为此，用球面拟合得到点的法向量和曲率。点p的距离最近后个点p。(戈i，yi，彳。)(江1，2， …，．|})称为p的||}一邻域，记为Ⅳ6砌(p)。假设这矗个点以及点p分布在一个球面上，理想的球面方程为 (戈一戈o)2+()，一yo)2+(z一钿)2=R2，式中：x0、y0、彳o——球面参数； D。(‰，y0，％)——球心坐标；尺——球半径。值和半径表达式，可求出参数戈。、％、矶尺。接着求出后个近邻点以及点p(戈，，y，，乃)和的平均坐标 p。，。(戈。，。，y。，。，z。，。)，其中， ^ 茗。，。=(∑zi+戈，)／(矗+1)， l=I ^ 儿。=(∑yi+％)／(后+1)， l 2I ^ 二…=(∑盈+邵)／(七+1)，则法向量为p。，。一0。，相应的坐标为(戈…一菇。，y。。一 y。，z…一z。)，则曲率为1／R。重复以上步骤，求出点云中每个数据点的法向将球面方程展开可得其一般形式：量和曲率，并把法向量和曲率保存到相应的位置。 F(戈，)，，戈)=戈2+y2+z2+o戈+6y+c孑+d=0，可得：戈o=一口／2， yo=一6／2， zo=一c／21 R=√02+62+c2—4d／2，通过点p及其晟个近邻点，利用最小二乘法拟合可以得到球心坐标和球半径。推导过程：首先，计算 M= ∑戈y ∑y2 ∑弘 ∑，， ∑船 ∑弘 ∑z2 ∑彳 Z y Z l ∑∑∑_ ^ Ⅳ= 一∑(戈3+夥2+嬲2) 一∑(y3+p2+弘2) 一∑(z3+猫2+形2) 一∑(戈2+)，2+z2) 通过判定可知，M为实对称的半正定矩阵，可以求取矩阵的广义逆矩阵M～。然后，求出F=M～·Ⅳ，假设求出的F= [以0)八1)八2)八3)】1，则戈o=一八0)／2，扎=一八1)／2，％=一八2)／2， R=以再万孺丽。 2散乱点云简化算法 2．1边界提取由于点云的边界数据反映了样件的边界特征，而边界特征对于曲面重构是十分重要的，因而在点云数据简化过程中对边界数据点进行保护。常见的边界提取方法是，把点近邻投影到拟合的最小二乘平面上，分析投影点之间分布的均匀性，提取边界。均匀性的判断标准是角度标准差，但是计算量很大，会耗费大量时间。故，文中基于这种思想，采用直接比较坐标值，这样可以节省大量计算时间。按照点云预处理的空间栅格划分方法把三维点云数据分配到相应的栅格内，栅格内有点云数据则设置为1，没有点云数据则设置为0，这样就把三维点云可以看成是三维图像。利用三维图像提取边界技术，提取出三维图像边界，图像边界对应的三维数据则是点云的粗边界。在粗边界的基础上进行三维数据边界提取，如图l所示，通过点 p的坐标及对应的法向量，构造其对应的平面，并将点p的近邻投影到该平面上，然后过点p分别做面印y 图1点p边界点及投影将点p及其七个近邻点，代入式(1)的球心坐标 ng．1 Boundary poinb柚d proj∞6∞of point p 万方数据

86 黑龙江科技学院学报第23卷平行于z以、戈仇、y陇的三个平面例、率、嬲，并计算出位于这三个平面两侧的点数，只要其中一个平面的两侧点数差与尼的比值大于设定阈值，则该点记为边界点。 2．2点云简化算法数据简化最佳效果是使简化后的点云具有较少的数据量，同时又能保证不丢失物体表面的细节特征，且运算速度越快越好。数据点在简化后的疏密应该随着曲面曲率的变化而变化，即曲率变化越大，数据点应越多，反之曲率变化越小，数据点就应该越少。因此在简化过程中，必须在保证被测物体几何特征的前提下，根据物体曲面的曲率变化对数据进行非均匀简化，文中提出保留边界的点云简化方法。 2．2．1 简化算法该算法首先构造散乱点云的局部拓扑信息，通过空间栅格法快速找到点的后近邻；通过球面拟合得到该点相应的法向量和曲率，接着找到点云的边界点并保留；对非边界点，根据文中提出的曲率简化原则进行数据简化，直至遍历完点云数据的所有点。该算法不仅可以完整保存实物模型整体轮廓，而且能够最大限度地保证模型区域特征。 2．2．2曲率简化原则曲率反映了曲面的基本特性，曲率可作为点云数据简化的阈值准则。对曲率按照大小进行排序，根据实际情况和结果要求设定阈值，对曲率分为几种不同等级，文中采用对曲率分为大中小三类曲率，从大到小区域标记为l、2、3，进而便对点云数据进行对应的分类和分片处理。其中曲率小的区域3是近似平面等一些变化平滑的区域，这部分可以删除较多的点；而曲率最大的区域1则是变化比较尖锐的区域，说明有较多的特征区域，需要保留较多的点，所以在分区的每部分，设定的阈值是不同的。在每一分区中，按照曲率从大到小进行点云处理，并求取每一个点的血近邻曲率平均值。如果点的|j}近邻点保留边界点和非边界点的个数之和已经超过近邻点总数的设定比例1内，则删除此点。如果点的后近邻点保留边界点和非边界点的个数之和低于近邻点总数的设定比例2内，则保留此点。如果点的曲率大于曲率平均值的系数，则保留此点，其中区域1的曲率需要保留较多的点，因此，系数1较小；区域3的变化比较平滑，系数3较大，根据具体需要保留点的个数对系数1、系数3进行自适应的调节。这样就在曲率较高的区域，保留了较多的点， 3 实例与结果分析使用自主研发的设备对雕塑及某加工零件进行非接触式三维测量，对三维点云进行去噪、拼合等处理后，得到的三维点云作为文中应用实例。利用球面拟合算法得到有方向的法向量和曲率，以及利用文中提出的简化方法对点云数据进行了简化。图2是黑龙江科技学院自主研发的三维测量仪器照片，为了验证问题，对雕塑点云进行详细的分析。为了说明算法应用的普遍性，对某加工零件进行分析。图2 自主研发的三维测量设备 Fig．2 Independent deVeI叩ment 3D me嬲uring eqllipment 3．1雕塑模型分析 3．1．1 法向量的比较计算三维点云的法向量和曲率，分别利用平面拟合以及球面拟合算法得到其结果。为了更加清晰的说明法向量方向性，选择一小部分点云的法向量进行比较说明。文中选择的是雕塑的帽子一部位，图3是法向量的显示效果图，其中图3a是通过平面拟合得到法向量，但是没有调整方向的显示效果图，图3b是通过球面拟合得到的法向量显示效果图。为了更加清晰看到该方法的效果，特别选取一部分点云的两种法向量进行效果显示。图4是把两个方法得到的法向量进行方向性比较，其是带有点云序号的两种计算方法得到的法向量显示，图4a的法向量方向基本一致，处于基本重合的状态。图4b法向量方向基本相反，两向量基本处于180。。通过比较分析可见，该算法得到的法向量和平面拟合调整后的法向量大小基本一致，误差在允许范围之内，达到了预想的效果，还可以节省所有点云数据法向量方向调整的相反则在曲率较小的区域保留了较少的采样点。时间，为数据处理节省了时间。万方数据

第1期赵伟玲，等：保留边界特征的点云简化算法 87 表1 部分点云的曲率值比较及误差分析 Table l Value∞mpari∞n and ermr analysis of curva咖about辩Veral points cloud 图3法向量显示效果 Em圮t d均wing of nomlaI Vector Fig．3 ，、、、、、～、～、、、、、、、、、、、、、．、、、、～、、、、，，、、、、、、、、、、、～、、～、、、、、＼ tIl IIl I●I l●I_I l-11 ■■■t●●■I IlI IIl IfI f lll ●■●f●f I I IllI If●f 图4两种法向量方向性比较 Fig．4 Two∞mal vector mr∞tional compari鲫n 3．1．2 曲率的比较在简化过程中，点云曲率的计算是很重要的一个环节。通过平面拟合得到法向量曲面拟合方法得到的平均曲率作为点云的曲率，是一种常见计算点云曲率的方法，称为方法一。但是其过程复杂，还影响数据处理的速度，故选取文中的方法计算曲率。表1是把常见方法的计算的曲率和文中计算得到的曲率进行大小值的比较，可以看出曲率的误差在允许范围之内。万方数据 3．1．3 简化效果分析图5是某雕塑的点云数据通过调节设定阈值的大小得到不同简化程度的点云。图5a是原始点云含有279 610个点的效果图，图5b～d是简化后分别含有144 541、89 903、47 108个点的效果图，由图 5可见，设定阈值的大小决定了简化后点云数量的多少。从图5b和图5c简化的效果得到在鼻子、帽子、手等表面变化陡峭的部位保留了较多的点，而在面部等表面变化平缓的部位保留的点相对稀疏，但是图5b比图5c保留了较多的数据点；由图5d的效果图可见其丢失了一部分特征，这是因为阈值设定的不合适，删除掉了很多的点。具体采用多大阈值，需要根据预想效果去设定。对图5b～d 的点云个数和原始点云的个数进行比例计算，分别为51．7％、32．1％、16．8％。 3．2加工零件分析图6是某加工零件的点云数据通过调节设定阈值的大小得到不同简化程度的点云。图6a是原始点云含有391 715个点的效果图。图6b～d是简化后分别含有253 601、137 858、73 826个点的效果图，由图可见，使用文中的简化方法设定阈值很关键。从图6b和图6c简化效果看到圆孔、棱边界处等曲率变化大的地方保留了较多点，而在平坦处等曲率小的部位保留了较少点；图6b在比较平滑部位也保留了比较多的点。由图6d的效果图可见，因为阈值设定的不合适还是丢失了一部分特征。将图 6b～d的点云个数和原始点云的个数进行比例计算，分别为64．7％、35．2％、18．9％。

黑龙江科技学院学报第23卷 4 结束语利用三维栅格法可构造散乱点云的拓扑关系，通过球拟合计算点的法向量、曲率以及投影点个数比值，得到点云边界并保留边界点，然后对其余点进行分类。根据具体情况进行阈值设定，通过点的曲率与平均曲率、近邻保留点个数与近邻点个数的比较，实现了数据简化，并对具有不同表面特征的点云数据进行了验证。多组点云数据的实验简化比例为 25％～40％，在保留边界特征的基础上，曲率较大的地方保留相对多的点，曲率较小的地方保留相对少的点。结果表明：该算法易于实现，运行速度快，数据简化原则灵活，调节设定阈值可得不同简化程度的点云，能准确识别散乱点云的边界特征点，在保留几何特征基础上对点云数据具有很好的简化效果，在实际工程应用中具有一定的应用价值。参考文献： [1] 张舜德，朱东波，卢秉恒．反求工程中三维几何形状测量及数据预处理[J]．机电工程技术，200l(1)：7一10． [2] cHEN Y H，NEG c T，wANG Y Z．Data reduction in jnteg珀ted reverse enginee一“g and rapid prototypi”g[J]． Intemational Jour- nal ofComputerIntegrated MarIufacture，1999，12(2)：97—103． [3] suN w，BRADLEY c，zHANG Y F．cloud data modeling em— ploying a uni6ed non—redundant triangle mesh[J]． computer Ai- ded Design，200l，33(2)：183一193． [4] 洪军，丁玉成，曹亮，等．逆向下程中的测量数据精简技术研究[J]．西安交通大学学报，2004(7)：66l一664． [5]殷金祥，陈关龙．一种基于面密度概念的数据简化方法[J]．现代制造工程，2003，23(8)：39—40． [6] 张丽艳，周儒荣，蔡炜斌，等．海量测量数据简化技术研究 [J]．计算机辅助设计与图形学学报，200l，13(11)：1119—1023． [7] LEE K H，w00 H，suK T．Point data reduction using 3D鲥ds [J]．Advanced Manufacturing 7rechnolog)r，2001(18)：20l一2lo． [8] sONG H，FENG H Y．A dobal clustering appmach to pojnt cloud simpli6cation with a specified data reduction mtio[J]． computer Aided Design，2008(40)：28l一292． [9] 王仁芳，张三元，叶修梓．基于相似性的点模型简化算法 [J]．浙江大学学报：工学版，2009(3)：448—454． [10] 倪小军，姜晓峰，葛亮．特征保留的点云数据自适应精简算法[J]．计算机应用与软件，20lI(8)：38—39． [11] 黄文明，肖朝霞，温佩芝，等．保留边界的点云简化方法 [J]．计算机应用，20lO(2)：348—350． (编辑李德根) ，i争i笋0 i◇ ，j拿．避@j◇ 图6不同阈值加工零件简化效果 Fig．6 E脓t ofmachining pans siInp硒ed iIl di仃erent tlIr髂hoId 实验结果表明：该算法适用于多种三维点云的简化，在点云简化过程中，通过阈值设定的不同，得到不同的简化效果图以及不同的简化比例。通过简化效果的比较，可以得出，使用文中的简化方法设定阈值很关键，根据实际需求设定阈值并达到所需的简化要求。多组点云数据的简化实验可以看出，简化比例为25％一40％。通过对阈值进行合适的设定达到了在保留边界特征的基础上，在曲率较大的地方保留相对多的点，在曲率较小的地方保留相对少的点。该简化效果能够满足后期数据要求。万方数据

保留边界特征的点云简化算法作者：作者单位：刊名：赵伟玲，谢雪冬，程俊廷， ZHAO Weiling， XIE Xuedong， CHENG Junting 黑龙江科技学院现代制造工程中心,哈尔滨,150027 黑龙江科技学院学报 Journal of Heilongjiang Institute of Science and Technology 2013,23(1) 英文刊名：年，卷(期)：参考文献(11条) 1.张舜德;朱东波;卢秉恒反求工程中三维几何形状测量及数据预处理 2001(01) 2.CHEN Y H;NEG C T;WANG Y Z Data reduction in integrated reverse engineering and rapid prototyping 1999(02) 3.SUN W;BRADLEY C;ZHANG Y F Cloud data modeling employing a unified non-redundant triangle mesh 2001(02) 4.洪军;丁玉成;曹亮逆向工程中的测量数据精简技术研究 2004(07) 5.殷金祥;陈关龙一种基于面密度概念的数据简化方法 2003(08) 6.张丽艳;周儒荣;蔡炜斌海量测量数据简化技术研究 2001(11) 7.LEE K H;WOO H;SUK T Point data reduction using 3D grids 2001(18) 8.SONG H;FENG H Y A global clustering approach to point cloud simplification with a specified data reduction ratio 2008(40) 9.王仁芳;张三元;叶修梓基于相似性的点模型简化算法 2009(03) 10.倪小军;姜晓峰;葛亮特征保留的点云数据自适应精简算法 2011(08) 11.黄文明;肖朝霞;温佩芝保留边界的点云简化方法 2010(02) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_hljkyxyxb201301019.aspx

分享到：

赞收藏

资料库

保留边界特征的点云简化算法.pdf

相关推荐

课程资源

热门标签

最新资料