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

本资料包含pdf文件1个，下载需要1积分

为精确快速地获取工件表面的尺寸信息 ，非接触的三维光学扫描设备已被广泛应用在生产线上。由测量所得到的通常包含大量数据点的数据能很好地描述物体表面信息，但是大规模的点云给准确快速的三维重建或其他的后续处理带来 了很大的困难。为更有效地表达和绘制三维点云模型，需要对点云进行合理的简化↑年来 ，国内外学者提出了针对不同类型点云的简化算法。对于扫描线点云数据，可以采用均匀采样法、角度偏差法、弦高差和角度弦高法等 J。针对 网格点云数据，Chen等 提出了-种减少三角网格数 目，删除部分数据点的方法。针对目前最常见的散乱点云数据类型，Sun等 提出包围盒法简化数据。洪军 J改进了包围盒算法，利用包围盒法构造分割面，由分割面将数据点云处理成按扫描线存储的结构化”测量数据，再利用角度-弦高联合准则法逐线精简。

殷金祥 利用数据点周围以 为半径的球进行测量，得到测量球内的临近点数量作为该数据点面密度，以面密度确定曲面凹凸弯曲程度，进而确定点的简化距离阈值和精简数据点集。张丽艳 提出基于三种原则的简化算法，即按简化后的个数、点云密度以及删除-点后引起的法向偏差进行简化。Lee等 以数据点的法矢为判据，对点云进行空间栅格细分，在每个栅格上选择 1个特征点↑几年，有文献 提出了基于聚类和相似性的点模型简化方法。

笔者研究了-种在保留边界特征基础上简化点云的有效方法。该算法，首先利用三维栅格划分法计算出每个数据点的近邻，通过球拟合法计算出点的法向量和曲率，接着通过投影点个数比值法找到并保留点云边界，然后根据具体情况设定所需阈值，对非边界点进行分类，通过对点的曲率与平均曲率比较、近邻保留点与近邻点个数 比例，进行点云简化1 点云预处理1.1 点云的空间划分与邻域搜索测量得到的散乱数据只包含数据点的三维坐标值，点与点之间没有明显的几何分布信息，因此，必须建立数据点云之问的拓扑关系以及搜索每个点对应的k个最近邻域。文中采用空间栅格划分法搜索点的 k个邻域，此方法在求某点的k邻近时，不需要在整个点云中搜索，而只需在相应的小立方体栅格中搜索即可。

1.1.1 空间栅格划分数据点P的最近k个点称为P的k-邻域，记为Nbhd(P)。首先 ，读人点云数据，计算测量点云数据的 、y、 坐标的最小值和最大值，得到所有数据的最小长方体 空间 [ ， ]，[Y，Y ]，[z，z]，通过栅格边长 的设定，将长方体包围盒按三个坐标方向划分成 m x n x f个小立方体栅格，其中m( - )/L，n(Y -Y )/L，f(Z -Z ； )/ 。然后，把每个数据点分配到相应的小立方体栅格(m ，np，f )中，其中m ( - )/L，n (Y。-Y i )/，J，lp(Zp-z)/ 。

将数据点的序号追加到该立方体栅格对应的链表中。由于每个子空间内含有数据点的个数是未知的，为了节省存储空间采用链表的结构来存储。先给每个子空间分配-个固定长度的存储空间，如果存储空间不够可以动态地再次分配。

1.1.2 k最近邻域搜索方法首先，计算该点所在立方体栅格的索引号，然后，在其所在的立方体栅格及其顶点相邻的上下、左右、前后共 27个小立方体栅格中查找 k个最邻近的点，并按相邻点到 的距离 dist由小到大的顺序进行排序。如果在这 27个栅格中相邻点不够 k个，这样就必须继续搜索外层栅格，即与27个栅格外侧表面相邻的栅格，达到k个点便可以结束。

1.2 不需调整方向的点法向量与曲率计算在数据简化中，点云法 向量和曲率的计算是关键预备工作之-。测量数据很密集，在小范围内理想意义上所在的曲面应该是很光滑的，所以任何点的局部邻域都可以用平面或者曲面进行很好地拟合。但是拟合平面得到的法向量方向是两个方向，这样就需要对法向量方向进行适当的调整。曲率计算常见的方法是基于法向量的局部坐标系，利用最小二乘法拟合简化抛物面，计算得到拟合抛物面的两个主曲率，其中两个主曲率的平均值称为平均曲率。由于平均曲率更能反应曲面的弯曲特性，所以，-般取平均曲率作为曲面曲率的衡量标准。这样点 P的曲率定义为点 k近邻拟合抛物面的平均曲率。

上述介绍求取点云的法向量需要进行方向调整，常见计算曲率的方法也比较复杂。在曲率大的地方可用半径小的球面拟合，在曲率小的位置可用半径大的球面拟合，所以在近邻小范围内可选用球第1期 赵伟玲，等：保留边界特征的点云简化算法 85拟合。球面的法向量方向是唯-的，免去了法向量调整这-过程，也可以很简便得到对应点的曲率，为此，用球面拟合得到点的法向量和曲率。

点P的距离最近 k个点p ( ，Y ， )( 1，2，，k)称为P的 k-邻域，记为 Nbhd(p)。假设这 k个点以及点 P分布在-个球面上，理想的球面方程为( - o) ( -Y0) ( - 0) R ，式中： 0、Y0、Z0--球面参数；0 ( ，Yo， )--球心坐标；尺--球半径。

将球面方程展开可得其-般形式：F(x，y， ) y ax CZd0，可得 ：n -a/2，Y0 -b/2，0 -c/2，R/。 b c -4d/2，通过点 P及其 k个近邻点，利用最小二乘法拟合可以得到球心坐标和球半径。

推导过程：首先，计算M ∑∑xy∑∑N ∑xy∑Y∑yz∑Y∑拼∑yz∑∑∑∑Y∑k1- ∑( xy XZ )- ∑， yx yz )- ∑( 。z zy )- ∑( Y。Z2)通过判定可知，M 为实对称的半正定矩阵，可以求蓉阵的广义逆矩阵 ～。

然后，求 出 F M～·Ⅳ，假 设求 出 的 F [ 0) 1)厂(2) 3)] ，则。-f(0)/2，Y0-厂(1)/2，0- 2)/2，R y - 3)。

将点P及其k个近邻点，代人式(1)的球心坐标值和半径表达式，可求出参数 Y R∮着求出k个近邻点以及点P( 。，Yp，Zp)和的平均坐标P ( ，Y ， )，其中，k (∑ Xp)/( 1)，t lkY(∑Y )/( 1)，I IkZave (∑ )/( 1)，E： l则法向量为P 。-0。，相应的坐标为( - 。，Y -Y。，。 。-Z0)，则曲率为 1/R。

重复以上步骤，求出点云中每个数据点的法向量和曲率，并把法向量和曲率保存到相应的位置。

2 散乱点云简化算法2.1 边界提取由于点云的边界数据反映 了样件 的边界特征，而边界特征对于曲面重构是十分重要的，因而在点云数据简化过程中对边界数据点进行保护。

常见的边界提取方法是，把点近邻投影到拟合的最小二乘平面上 ，分析投影点之间分布的均匀性，提取边界。均匀性的判断标准是角度标准差 ，但是计算量很大，会耗费大量时间。故 ，文中基于这种思想，采用直接比较坐标值，这样可以节省大量计算时问。

按照点云预处理的空间栅格划分方法把三维点云数据分配到相应的栅格内，栅格 内有点云数据则设置为 1，没有点云数据则设置为 0，这样就把三维点云可以看成是三维图像。利用三维图像提取边界技术 ，提取出三维图像边界，图像边界对应的三维数据则是点云的粗边界。在粗边界的基础上进行三维数据边界提取 ，如图 1所示，通过点P的坐标及对应的法 向量，构造其对应的平面，并将点P的近邻投影到该平面上，然后过点P分别做图 1 点p边界点及投影Fig.1 Boundary points and projeetion of point P86 黑 龙 江 科 技 学 院 学 报 第23卷平行于xOy、xOz、yOz的三个平面 xpy、xpz、ypz，并计算出位于这三个平面两侧的点数，只要其中-个平面的两侧点数差与 k的比值大于设定阈值，则该点记为边界点。

2.2 点云简化算法数据简化最佳效果是使简化后的点云具有较少的数据量，同时又能保证不丢失物体表面的细节特征，且运算速度越快越好。数据点在简化后的疏密应该随着曲面曲率的变化而变化，即曲率变化越大，数据点应越多，反之曲率变化越小，数据点就应该越少。因此在简化过程 中，必须在保证被测物体几何特征的前提下，根据物体曲面的曲率变化对数据进行非均匀简化，文中提出保留边界的点云简化方法。

2.2.1 简化算法该算法首先构造散乱点云的局部拓扑信息，通过空间栅格法快速找到点的 k近邻；通过球面拟合得到该点相应的法向量和曲率，接着找到点云的边界点并保留；对非边界点，根据文中提出的曲率简化原则进行数据简化，直至遍历完点云数据的所有点。

该算法不仅可以完整保存实物模型整体轮廓，而且能够最大限度地保证模型区域特征。

2.2.2 曲率简化原则曲率反映了曲面的基本特性，曲率可作为点云数据简化的阈值准则。对曲率按照大续行排序，根据实际情况和结果要求设定阈值，对曲率分为几种不同等级，文中采用对曲率分为大中小三类曲率，从大到小区域标记为 1、2、3，进而便对点云数据进行对应的分类和分片处理。其中曲率小的区域 3是近似平面等-些变化平滑的区域，这部分可以删除较多的点；而曲率最大的区域 1则是变化比较尖锐的区域，说明有较多的特征区域，需要保留较多的点，所以在分区的每部分，设定的阈值是不同的。

在每-分区中，按照曲率从大到续行点云处理，并求取每-个点的 k近邻曲率平均值。如果点的k近邻点保留边界点和非边界点的个数之和已经超过近邻点总数的设定比例 1内，则删除此点。如果点的 近邻点保留边界点和非边界点的个数之和低于近邻点总数的设定比例 2内，则保留此点。如果点的曲率大于曲率平均值的系数，则保留此点，其中区域 1的曲率需要保留较多的点，因此，系数 1较小；区域3的变化比较平滑，系数 3较大，根据具体需要保留点的个数对系数 1、系数 3进行 自适应的调节。这样就在曲率较高的区域，保留了较多的点，相反则在曲率较小的区域保留了较少的采样点。

3 实例与结果分析使用 自主研发的设备对雕塑及某加工零件进行非接触式三维测量，对三维点云进行去噪、拼合等处理后，得到的三维点云作为文 中应用实例。

利用球面拟合算法得到有方向的法向量和曲率，以及利用文中提出的简化方法对点云数据进行了简化。图2是黑龙江科技学院自主研发的三维测量仪器照片，为了验证问题，对雕塑点云进行详细的分析。为了说明算法应用的普遍性，对某加工零件进行分析。

图2 自主研发的三维测量设备Fig.2 Independent development 3Dmeasuring equipment3.1 雕塑模型分析3.1.1 法向量的比较计算三维点云的法 向量和曲率 ，分别利用平面拟合以及球面拟合算法得到其结果。为了更加清晰的说明法向量方向性，选择-小部分点云的法向量进行比较说明。文中选择的是雕塑的帽子- 部位，图3是法向量的显示效果图，其中图3a是通过平面拟合得到法向量，但是没有调整方向的显示效果图，图3b是通过球面拟合得到的法向量显示效果 图。为了更加清晰看到该方法 的效果，特别选取-部分点云的两种法向量进行效果显示。图4是把两个方法得到的法向量进行方向性比较，其是带有点云序号的两种计算方法得到的法向量显示，图 4a的法向量方向基本-致，处于基本重合的状态。图4b法向量方向基本相反，两向量基本处于 180。。通过 比较分析可见，该算法得到的法向量和平面拟合调整后的法向量大轩本-致，误差在允许范围之 内，达到了预想 的效果，还可以节省所有点云数据法向量方向调整的时间，为数据处理节省了时间。

第1期 赵伟玲，等：保留边界特征的点云简化算法 87h图3 法向量显示效果Fig.3 Effect drawing of normal vector图4 两种法向量方向-陛比较Fig.4 Two normal vector directional comparison3.1.2 曲 率的 比较在简化过程中，点云曲率的计算是很重要的-个环节。通过平面拟合得到法向量曲面拟合方法得到的平均曲率作为点云的曲率，是-种常见计算点云曲率的方法，称为方法-。但是其过程复杂，还影响数据处理的速度，故选取文中的方法计算曲率。

表 1是把常见方法的计算的曲率和文中计算得到的曲率进行大小值的比较，可以看出曲率的误差在允许范围之内。

表 1 部分点云的曲率值比较及误差分析Table 1 Value comparison and error analysis ofcurvature about several points cloud3.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%。

～ 、 、 、 、- 、 、 、 、、 、 ～ 、、 、 、 、 、r ～ 、 、 、 、 、～ 、 、 、、 、 、 、、 、 。