采用均匀网格的一种点云数据减少新方法

1、采用均匀网格的一种点云数据精简新方法摘要：由于三维扫描技术的不断发展， 点云数据量变得越来越大， 而且存在大量 的冗余数据。存储或处理这些数据会消耗大量的时间和计算机资源。在本文中， 提出了一种基于三维网格的点云数据精简方法。 它包括搜索 K 个近邻构建数据拓 扑结构，计算切平面的法向， 使用均匀三维网格重新采样点云数据并选择能满足 要求的数据点。 与传统方法相比， 该方法保留了更多的特征点， 而且它避免曲率 的估算。通过使用该方法和其他方法对不同的点云数据进行实验表明， 该方法可 以保留更多的细节，同时删除冗余的数据点。关键词：逆向工程，八叉树，法向之间的夹角， K 个近邻。1 简介在逆向工

2、程中， 三维扫描仪作为一种主要工具被广泛使用， 它可以得到的三 维点云数据，而无需触摸物体， 进而完成了模型的重建。 点云也可以称为无组织 的数据集， 点与点之间没有几何拓扑关系， 只是一个简单的三维点集。 这些点是 由x, y和z坐标来定义。点云数据通常是密集而松散的。简化点云的目的是尽量用较少的点来保持更多的模型信息。 简化点云的方法 根据是否建立点云的网状结构被分为两个大类： 基于网格的方法和基于点的方法。 基于网格的方法必须建立点云的三角形网格, 然后根据实际应用需要减少三角形 的数量。它通常是复杂且耗时的。基于点的方法, 避免了建立点云的三角网格。 它们是更简单和更快的。 这些 方法

3、包括随机抽样的方法, 包围盒的方法,均匀网格法等。随机抽样法是最简单、 容易的方法,它每一次产生一个比点的总数小的整数, 然后删除对应于整数的点。 这个方法有较大的随机性和相对较差的效果。包围盒方法首先建设一个网格结构, 并将输入点分配给相应的单元。 对于每 个非空单元格,最接近单元格的中心的点被选择代表该单元格中的所有各点。Martin 等人提出了一种使用均匀网格的点云数据缩减方法。 这种方法使用 “中值滤波”的原理，该原理已被广泛地应用于图像处理中。与包围盒算法不同，这种 均匀网格算法，被选择代表全部点云数据的中间点属于非空单元格。包围盒算法和均匀网格法克服了随机抽样法的局限， 但有由于使

4、用尺寸均匀的网格，可能在 捕获部分形状上有不敏感的缺点。曲率法是另一种基于点的精简方法，这个方法首先找出每个点的 K个近邻点, 然后再使用这些点的拟合成一个曲面。这个曲面的曲率可以被看作是所这些点的 估计值。其中曲率比较大的区域应保留更多的点。 此方法在特征区域保留更多的 细节，但曲率计算需要复杂的矩阵运算，尤其是当有大的点云数据处理是它耗时 比较多。Nonrt 电 Stimuli 測 dILL J - 一6潮皿“佃'匚二 灿啟也:讪恥曲率法的过程：法线估计和调整，曲率估计，基于点的提取和精简原则。除了上述方法，K. H. Lee等人提出了一种网格的尺寸可以根据局部的形状变 化的非均匀

5、网格压缩法。这个方法对于自由曲面比均匀网格法更加有效， 但仍难 以确定边界点。李凤霞等人提出了采用非线性最小二乘的点云简化方法。传统的方法，如随机抽样法，均匀网格法和包围盒算法不考虑点云数据的局 部特征，因而不能保持原始点云的细节。曲率法利用曲率估计可以保留点云的细 节，但曲率计算需要消耗太多的时间。 在本文中，提出一个新的点云数据压缩方 法可以克服以前方法的局限。2 一种新的采用均匀三维网格的压缩算法该方法包括六个步骤：1搜索每个点的K近邻；2计算每个点的单位法向量；3计算v'在下面的文本介绍；4使用三维网格将点云抽稀；5使用阈值将点云抽稀；6输出米样点A)方法的基础众所周知，对于曲

6、面上的点，在平坦的地方法线方向几乎是相同的，但 在起伏大的区域就有很大不同。因此，法线方向之间的角度可以使用在压缩 算法中。两个单位向量之间的夹角的余弦值可通过内积来表示。在本文中，该点 的法向量和它相邻的法向量的内积的平均值被选择为一个元素来决定这个点 是否被取样。在本文中这个平均值被称为 V。Pi点的单位法向量(vxi,vyi,vzi),它的k个临近的单位法向量是 (NX1,NY1,NZ1)(NXK,NYK,NZ，那么 Pi 的 V 为：V =(y* nx+阳* AT + 鬼 *川2 l)/Jt 厶:二 I iIi1*假定在局部区域中的点云数据是光滑的，Pi和其邻域之间的法线角度不大于90

7、度，计算出的内积是非负的。因此我们使用内积的绝对值进行计算。计算出来的V的值在0和1之间，V值越小意味着局部点云的起伏越剧 烈。使用V'1-V来进行后续计算，这样就意味着更小的 V代表局部区域越平 坦。在图2中，这些点被标记为不同的颜色。v'大于指定的阈值的点被标记 为红色，其他都标为白色。可以看出，红色点位于大多位于起伏较大的区域。vlO.OOlJ图2比较使用V'的不同的阈值的点之间进行区分。括号中的数字是阈值B）搜索K个近邻使用八叉树结构可以显著减少搜索每个点 k最近邻居的时间。八叉树被定义为：如果树不为空，在八叉树的任意节点的子节点的数目是0或8。八叉树是一种基于

8、递归分解的分层的树状结构。它是四叉树结构的扩展。八叉 树结构的原理与二叉树和四叉树是相同的。八叉树最初是用在三维实体建模 领域中，此后它作为一种有效指标被广泛用在三维空间领域。当创建一个八叉树时，首先创建根节点。这个节点表示包围点云的所有 点的最小立方体。然后立方体被分成八个较小的子立方体，每个对应于根的 一个子节点。如图3所示，继续使用这个规则分割的子立方体，直到没有必 要再次分割为止。八叉树的每个叶节点代表了空间的最小划分。点云的每个 点应该被插入到相应的叶节点上。Fig. 3 The wtitt structure当搜索Pi的K-最近邻时，只有在相同的叶节点或相邻的叶节点上的点需要被搜

9、索。C）单位法向量的计算三维扫描仪获得的点云数据通常含有的法线方向和反射强度信息。 通过光学 扫描仪获得的点云数据，除了空间坐标值以外一般不包含其他的信息。点的单位 法向矢量在程序中被计算。由于在我们的数据压缩算法中法线矢量精度要求不太高，所以我们使用由霍普等人在1992年提出的主成分分析（PCA法。假设样品表面是处处光滑的， 所以任何点的局部K邻域都可以很好的用一个曲面拟合。 对于任何一点Pi,用八 叉树结构获得了 K个邻域后，我们就可以估算切面 TP （PI）。这个平面TP （PI） 可以表示为如下：Tp（Pi） = argnunJfc 力二（n-在式（2）中，n是平面TP（ PI）的法线

10、矢量，d为Tp（ PI）的到坐标原点的 距离，P是 K个最近邻的质心。让切面TP（ PI）通过点P'，该法线向量n满足| n |= 1时，我们的目标是能 够转化为在公式3的正半定的协方差矩阵M的特征值分解。M .y Pi-巧（丹-卩（3）如果1表示与Vi的特征向量相关的M的最小特征值的绝对值，那么法向量 可以是Vi或-Vi。它通常需要调整每个点的法线方向。但是公式（1）中的V的计 算是建立在法线的角度假设是不大于 90度的基础上的，它并不需要知道真实法 线方向。我们使用的法线向量内积的绝对值，以避免方向的调整。估算单位法向量之后，我们就可以使用公式（1）计算V的值，因此V也是可知的。D

11、）使用三维网格进行点云采样如果使用V'来直接采样点云数据，当该点的V'值大于阈值时，这个点就应该 被采集。该阈值是由用户定义的。在平坦区域的这些点将被大规模地除去。如图2所示，这些白色的点将被删除，并且生成孔洞。所以，采样过程被分成两个步 骤。第一步骤是用均匀的三维网格进行点的采样。4-加色in pl in 客 pu lint u 対 Li】當 uid 3L> 営使用兔子点云作为一个例子，原始点云有35947个点。图4是使用三维网格 采样点后的结果。在建立包围盒后单元格的总数是262144。对于每一个不为空的单元格，则使用“中值滤波“的方法来计算中间点进行采样。有2619

12、个点被采样，这意味着259525个叶节点是空的。采样后，将得到的点均匀分布，但大 量的细节信息丢失。E）使用V'的阈值抽稀点云采样过程的第二步骤是使用V的阈值进行抽稀点云，对于未在步骤1被采集的点，比较其 V的值与阈值的大小，阈值是用户定义的。如果该点的V值大于阈值，那么它应该被采集。用户可以通过改变 V'的阈值控制压缩率。当阈值是0.03时，采样后点云的总数是6215,阈值是0和1之间。没有点被选定为采样点如果满足阈值大于1,而所有的点都被采样，如果阈值是小于0i l8 5pEmL U時 Lh©hoh!V'Hr h 血時山5站吋Ebe ilrqPLbg p血

13、I chuii图5是第二次采样后的结果。这些这次被采集的点大多分布在不同表面的交 接处。这些区域在点云的三维重建中非常重要。图6是采用简化后的兔子点云建 立的三角网格模型。在此步骤之后，压缩操作结束时，在最后输出简化的点云。3实验结果汽车模型的点云数据在图7（a）中展示，在不同的曲面上密度变化很大。图7（B，C，D，E），还展示了使用不同方法对汽车模型压缩的结果。在非特征区 域，我们的方法可以均匀的采集点云数据而且避免产生孔洞。在特征区域，我们的方法可以采集更多的点以保持去面的细节信息。a.f lut niiihde Ic.MitLiriding h%nxf)h. Kuindni sum 卩cXJ ur mihodf 76-,.5)图17所示：汽车模型使用不同的方法