面向点云数据的复杂几何模型对象优化方法研究

曹 垚，王宗敏，2，李 健*

(1.郑州大学水利与环境学院，郑州 450001; 2.中原工学院，郑州 450007)

随着三维激光扫描点云精度的不断提高，点云数据被广泛用于铁轨变形监测、零件模具和医疗等对数据具有较高要求的行业[1].随着精度的提高，所获取的点云数据量也在激增，需要对点云数据进行精简才能够进行应用.通过对学者[2-4]精简数据重构网格进行分析，点云精简之后点云数据尤其是重建网格的精度降低，精简率越大精度损失越多，从而确实原始物体的细节信息.尤其特征突出、曲面结构复杂的几何模型，精简之后点云重建会损失更多精度.如何降低网格精度损失成为主要问题之一.

针对网格精度提升和质量优化，主要集中在两个方面：1)一类是几何优化，通过增加点法和移动点法来提升三维点云重构网格质量，Leif Kobbelt[5]等人将拉普拉斯算子应用到网格优化中，该方法具有高效高精度的优点，但是对于复杂模型支持较差；丁慧[6]改进拉普拉斯算法在网格优化的应用，该方法能有效提升网格质量；章雅娟[7]提出了一种自适应网格优化方法，该方法根据不同权重对定点进行调整，能有效降低网格噪声.2)另一类是拓扑优化，通过调整点与点的连接关系来提高网格质量.Hoppe等[8]通过调整网格拓扑关系提升网格质量；Canann等[9]针对网格几何形状问题进行优化，该方法去除了大量不符合几何要求的三角网格；上述方法均能对网格进行优化，第一种方法主要是提升网格的精度，但是该方法不适用复杂的几何模型；第二种方法能有效提升网格拓扑，但是对网格的精度提升较小.

本文针对基于精简后点云数据重构网格精度缺失问题，结合三角网格中重新还原点使得网格误差减少思想[10]提出了一种面向点云数据的复杂几何模型对象优化方法.其基本思路是根据距离度量方法计算精简后点云重构网格误差，然后以目标精度确定需要优化的区域，最后利用增点法和插入点点算法定位插入点位置，还原网格细节，提升网格质量.

1点云重建网格的局部优化

1.1重建网格误差分析

1.1.1构建拓扑信息 由于原始点云散乱无序的特性，并且与所构建的三角网格也无索引和拓扑关系，为了准确的评估点云所构建三角格网的精度，需要构建点云的索引以及建立点云与格网的拓扑关系.

本文采用八叉树的方法，首先计算原始点云和重建模型的外包围盒，然后对外包围盒进行剖分并对剖分结果进行编码，最后确定原始点云的点和三角面片对应的位置并进行相应的编码.

1.1.2重建网格误差控制 通过距离度量的方法计算重建网格法误差，确定网格精度.首先通过已经构建好的拓扑关系确定原始点云点P(x，y，z)的邻域进而确定相邻网格，然后将点P(x，y，z)投影到邻近网格上，最后计算点P(x，y，z)到网格距离.该距离就是原始点云到重建网格的误差.计算网格的法向n，原始点云数据点P(x，y，z)到重构网格欧式距离为[11-12]：

(1)

(2)

其中，P1、P2、P3为网格点坐标，d代表原始点云点到网格的欧式距离.

由于原始点云中存在一个或者多个点投影到同一个三角网格中，则将点到三角网格距离的最大值作为网格误差，公式如下所示：

δj=max(dj(P，Δi)).

(3)

由上述公式计算每个三角网格误差，进而确定重构网格最大误差.本文计算和分析了不同精简率点云网格的误差.如图1所示，点云的误差逐渐增大，并且误差损失的速度变大.

需要说明的是，在数据选取过程中，不同的三维激光扫描仪获取的数据精度不同，以及根据数据使用用途的不同，数据精度要求也存在差异.所以本文网格预期精度需要根据原始数据的精度和网格模型精度要求进行调整.

1.2局部网格细分方法

本文通过上述误差计算方法以及目标精度对误差较大网格进行网格细分.网格细分[10，13]方法包括：

1-2划分法：将一个三角网格划分成两个三角网格；

1-3划分法：将一个三角网格划分成三个三角网格；

1-4划分法：将一个三角网格划分成四个三角网格.

通过对上述网格细分方法分析：如图2(c)所示，1-3划分法核心思路是将一个三角形划分成三个，该方法不引发其它三角面变化，但是容易产生小角度三角面；如图2(d)所示，由于1-4划分法是在每边的中心增加点，能很好的保留三角形形状，但是会影响周围三角形连接方式.因此本文将利用两次1-2划分法，如图2(b)所示.

图1 不同精简度的重构网格误差Fig.1 Reconstructedmesh errors with different simplification degrees

图2 局部划分方法Fig.2 Local division method

在数学几何原理基础上，以最长边中点和包含最长边的两个三角的法向所构成的平面为约束平面，然后构建搜索圆，为了提升精度降低误差搜索半径为三角网格最大误差.

(4)

其中，a、b的取值范围为-δi到δi，step为∂/10，Pai为增加点坐标.

通过公式(4)确定插入点，接着利用增点将该点插入到三角网格中，然后重新计算该区域的误差，依次计算所有插入点构成的新区域的误差，最后将误差最小的点作为最终插入点.

1.3方法流程

综上所述，本文方法的流程图如图3所示，步骤如下.

Step1：将原始点云数据点、精简后点云和重建网格分别存入到r_Points、s_Points和s_Mesh中.

Step2：根据空间八叉树构建的拓扑关系，计算原始点对应的网格，利用上述方法计算每个三角网格的误差.

Step3：以目标精度作为阈值，对误差大于阈值的三角网格进行局部细分，直到三角网格误差小于阈值.

Step4：根据最长边确定约束平面和搜索圆，然后利用插入点公式确定所有预插入点，最后将误差最小的点作为最终插入点.

图3 方法流程图Fig.3 Flow chart of the method

2实验结果与分析

为了验证本文方法的可行性和有效性，采用经典的兔子点云和若干来源于斯坦福大学的高保真数据，原始数据精度为± 0.025 mm.分别利用Geomagic Studio软件和Crust算法对上述数据进行精简和三维重建.基于上述处理，计算了精简后点云重构网格的误差，并利用增点法对三角形进行细分，本文不仅计算了细分之后的误差，还计算了三角面片的正则度.

根据目标精度要求，以兔子点云目标精度0.15 mm和龙点云目标精度0.10 mm作为阈值，分别对兔子和龙的精简后点云重构网格进行网格细分.图4和表1是点云精简率为90%的网格局部细分结果，以及细分前后误差和正则度对比.图4(a)和(b)分别为细分区域在整体位置以及局部细分放大图.由图所示细分区域在几何结构复杂的脚上.分析图4和表1可以得出，该局部网格误差由0.81 mm降低到0.32 mm，正则度则分别为0.888 3和0.888 7，正则度基本保持不变.表2则是选取了误差较大的七组细分前后的数据，通过表2可以看出细分后误差减少，部分三角面片正则度提升.

表1 子网格误差最大的三角面片优化前后数据

表2 兔子网格优化前后数据Tab.2 Data before and after rabbit mesh optimization

表3是分别利用本文方法对目标精度为0.15 mm的兔子网格和目标精度为0.10 mm的龙点云优化前后的对比数据.分析可得，一次划分后龙的三角网格增加140，点数增加了70，最大误差由0.36降低到0.11；兔子的三角网格增加262，点数增加131，误差由0.81降低到0.47，网格精度提升.

表3 精简后点云数据重构网格优化前后对比Tab.3 Comparisons before and after mesh optimization for simplifing point cloud datareconstruction

3结论

针对高精简率点云重构网格仿真度低误差降低的问题，在高保真和高精度原始点云数据的基础上，结合三角网格中重新还原点使网格误差减少思想，提出了一种面向点云数据的复杂几何模型对象优化方法.首先构建点云的索引以及建立点云与格网的拓扑关系，用原始点云到重构网格的距离确定网格的误差，以目标精度为阈值，然后利用增点法对面片进行划分，最后根据插入点算法重新定位插入点.实验验证表明：通过该方法对部分三角面进行一次优化，误差降低明显，仿真精度得到了提升.需要注意的是，本文方法在优化过程中会产生少量狭长三角面片，为了保证三角网格质量，下一步需要探究狭长三角面片产生的原因和消除的方法.