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

赵伟玲， 谢雪冬， 程俊廷

(黑龙江科技学院 现代制造工程中心，哈尔滨 150027)

0 引言

为精确快速地获取工件表面的尺寸信息，非接触的三维光学扫描设备已被广泛应用在生产线上。由测量所得到的通常包含大量数据点的数据能很好地描述物体表面信息，但是大规模的点云给准确快速的三维重建或其他的后续处理带来了很大的困难。为更有效地表达和绘制三维点云模型，需要对点云进行合理的简化。近年来，国内外学者提出了针对不同类型点云的简化算法。对于扫描线点云数据，可以采用均匀采样法、角度偏差法、弦高差和角度弦高法等[1]。针对网格点云数据，Chen等[2]提出了一种减少三角网格数目，删除部分数据点的方法。针对目前最常见的散乱点云数据类型，Sun等[3]提出包围盒法简化数据。洪军[4]改进了包围盒算法，利用包围盒法构造分割面，由分割面将数据点云处理成按扫描线存储的“结构化”测量数据，再利用角度—弦高联合准则法逐线精简。殷金祥[5]利用数据点周围以R为半径的球进行测量，得到测量球内的临近点数量作为该数据点面密度，以面密度确定曲面凹凸弯曲程度，进而确定点的简化距离阈值和精简数据点集。张丽艳[6]提出基于三种原则的简化算法，即按简化后的个数、点云密度以及删除一点后引起的法向偏差进行简化。Lee等[7]以数据点的法矢为判据，对点云进行空间栅格细分，在每个栅格上选择1个特征点。近几年，有文献[8－10]提出了基于聚类和相似性的点模型简化方法。

笔者研究了一种在保留边界特征基础上简化点云的有效方法。该算法，首先利用三维栅格划分法计算出每个数据点的近邻，通过球拟合法计算出点的法向量和曲率，接着通过投影点个数比值法找到并保留点云边界，然后根据具体情况设定所需阈值，对非边界点进行分类，通过对点的曲率与平均曲率比较、近邻保留点与近邻点个数比例，进行点云简化。

1 点云预处理

1.1 点云的空间划分与邻域搜索

测量得到的散乱数据只包含数据点的三维坐标值，点与点之间没有明显的几何分布信息，因此，必须建立数据点云之间的拓扑关系以及搜索每个点对应的k个最近邻域。文中采用空间栅格划分法搜索点的k个邻域，此方法在求某点的k邻近时，不需要在整个点云中搜索，而只需在相应的小立方体栅格中搜索即可。

1.1.1 空间栅格划分

数据点p的最近k个点称为p的k－邻域，记为Nbhd(p)。首先，读入点云数据，计算测量点云数据的x、y、z坐标的最小值和最大值，得到所有数据的最小长方体空间[xmin，xmax]，[ymin，ymax]，[zmin，zmax]，通过栅格边长L的设定，将长方体包围盒按三个坐标方向划分成m×n×l个小立方体栅格，其中m=(xmax－ xmin)/L，n=(ymax－ ymin)/L，l=(zmaxzmin)/L。然后，把每个数据点分配到相应的小立方体栅格(mp，np，lp)中，其中mp=(xp－xmin)/L，np=(yp－ymin)/L，lp=(zp－ zmin)/L。

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

1.1.2 k最近邻域搜索方法

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

1.2 不需调整方向的点法向量与曲率计算

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

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

点 p 的距离最近 k 个点 pi(xi，yi，zi)(i=1，2，…，k)称为p的k－邻域，记为Nbhd(p)。假设这k个点以及点p分布在一个球面上，理想的球面方程为

式中:x0、y0、z0——球面参数;

Op(x0，y0，z0)——球心坐标;

R——球半径。

将球面方程展开可得其一般形式:

F(x，y，x)=x2+y2+z2+ax+by+cz+d=0，可得:

通过点p及其k个近邻点，利用最小二乘法拟合可以得到球心坐标和球半径。

推导过程:首先，计算

通过判定可知，M为实对称的半正定矩阵，可以求取矩阵的广义逆矩阵M－1。

然后，求出 F=M－1·N，假设求出的 F=[f(0)f(1)f(2)f(3)]T，则

将点p及其k个近邻点，代入式(1)的球心坐标值和半径表达式，可求出参数 x0、y0、z0、R。接着求出k个近邻点以及点 p(xp，yp，zp)和的平均坐标pave(xave，yave，zave)，其中，

则法向量为 pave－Op，相应的坐标为(xave－x0，yavey0，zave－z0)，则曲率为 1/R。

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

2 散乱点云简化算法

2.1 边界提取

由于点云的边界数据反映了样件的边界特征，而边界特征对于曲面重构是十分重要的，因而在点云数据简化过程中对边界数据点进行保护。常见的边界提取方法是，把点近邻投影到拟合的最小二乘平面上，分析投影点之间分布的均匀性，提取边界。均匀性的判断标准是角度标准差，但是计算量很大，会耗费大量时间。故，文中基于这种思想，采用直接比较坐标值，这样可以节省大量计算时间。

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

图1 点p边界点及投影Fig.1 Boundary points and projection of point p

2.2 点云简化算法

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

2.2.1 简化算法

该算法首先构造散乱点云的局部拓扑信息，通过空间栅格法快速找到点的k近邻;通过球面拟合得到该点相应的法向量和曲率，接着找到点云的边界点并保留;对非边界点，根据文中提出的曲率简化原则进行数据简化，直至遍历完点云数据的所有点。该算法不仅可以完整保存实物模型整体轮廓，而且能够最大限度地保证模型区域特征。

2.2.2 曲率简化原则

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

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

3 实例与结果分析

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

图2 自主研发的三维测量设备Fig.2 Independent development 3D measuring equipment

3.1 雕塑模型分析

3.1.1 法向量的比较

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

图3 法向量显示效果Fig.3 Effect drawing of normal vector

图4 两种法向量方向性比较Fig.4 Two normal vector directional comparison

3.1.2 曲率的比较

在简化过程中，点云曲率的计算是很重要的一个环节。通过平面拟合得到法向量曲面拟合方法得到的平均曲率作为点云的曲率，是一种常见计算点云曲率的方法，称为方法一。但是其过程复杂，还影响数据处理的速度，故选取文中的方法计算曲率。表1是把常见方法的计算的曲率和文中计算得到的曲率进行大小值的比较，可以看出曲率的误差在允许范围之内。

表1 部分点云的曲率值比较及误差分析Table 1 Value comparison and error analysis of curvature about several points cloud

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%。

图5 不同阈值某雕塑简化效果Fig.5 Effect of sculpture simplified in different threshold

图6 不同阈值加工零件简化效果Fig.6 Effect of machining parts simplified in different threshold

实验结果表明:该算法适用于多种三维点云的简化，在点云简化过程中，通过阈值设定的不同，得到不同的简化效果图以及不同的简化比例。通过简化效果的比较，可以得出，使用文中的简化方法设定阈值很关键，根据实际需求设定阈值并达到所需的简化要求。多组点云数据的简化实验可以看出，简化比例为25%～40%。通过对阈值进行合适的设定达到了在保留边界特征的基础上，在曲率较大的地方保留相对多的点，在曲率较小的地方保留相对少的点。该简化效果能够满足后期数据要求。

4 结束语

利用三维栅格法可构造散乱点云的拓扑关系，通过球拟合计算点的法向量、曲率以及投影点个数比值，得到点云边界并保留边界点，然后对其余点进行分类。根据具体情况进行阈值设定，通过点的曲率与平均曲率、近邻保留点个数与近邻点个数的比较，实现了数据简化，并对具有不同表面特征的点云数据进行了验证。多组点云数据的实验简化比例为25% ～40%，在保留边界特征的基础上，曲率较大的地方保留相对多的点，曲率较小的地方保留相对少的点。结果表明:该算法易于实现，运行速度快，数据简化原则灵活，调节设定阈值可得不同简化程度的点云，能准确识别散乱点云的边界特征点，在保留几何特征基础上对点云数据具有很好的简化效果，在实际工程应用中具有一定的应用价值。

[1]张舜德，朱东波，卢秉恒.反求工程中三维几何形状测量及数据预处理[J].机电工程技术，2001(1):7－10.

[2]CHEN Y H，NEG C T，WANG Y Z.Data reduction in integrated reverse engineering and rapid prototyping[J].International Journal of Computer Integrated Manufacture，1999，12(2):97－103.

[3]SUN W，BRADLEY C，ZHANG Y F.Cloud data modeling employing a unified non-redundant triangle mesh[J].Computer Aided Design，2001，33(2):183－193.

[4]洪 军，丁玉成，曹 亮，等.逆向工程中的测量数据精简技术研究[J].西安交通大学学报，2004(7):661－664.

[5]殷金祥，陈关龙.一种基于面密度概念的数据简化方法[J].现代制造工程，2003，23(8):39－40.

[6]张丽艳，周儒荣，蔡炜斌，等.海量测量数据简化技术研究[J].计算机辅助设计与图形学学报，2001，13(11):1119－1023.

[7]LEE K H，WOO H，SUK T.Point data reduction using 3D grids[J].Advanced Manufacturing Technology，2001(18):201 －210.

[8]SONG H，FENG H Y.A global clustering approach to point cloud simplification with a specified data reduction ratio[J].Computer Aided Design，2008(40):281－292.

[9]王仁芳，张三元，叶修梓.基于相似性的点模型简化算法[J].浙江大学学报:工学版，2009(3):448－454.

[10]倪小军，姜晓峰，葛亮.特征保留的点云数据自适应精简算法[J].计算机应用与软件，2011(8):38－39.

[11]黄文明，肖朝霞，温佩芝，等.保留边界的点云简化方法[J].计算机应用，2010(2):348－350.