基于重心Voronoi剖分的点云均一化方法

摘要

基于重心Voronoi剖分的点云均一化方法，涉及三维点云。采用重心Voronoi剖分来对输出点进行位置的优化。由于输入的信息为单纯的点，需要利用点集求出最小二乘面从而建立简单的离散网格，以期获得相关计算参数。利用点与离散网格计算Voronoi图，然后在每个Voronoi单元中，进行Lloyd迭代操作，使得点的分布达到预想状态，即重心Voronoi图。该方法首先在输入的粗糙三维点云上采点，然后通过估计每个采样点的所在平面和计算每个采样点的Voronoi单元，计算出采样点的重心位置，将采样点移动到新的位置即进行Lloyd迭代，从而获得一个蜂窝状分布的点云结构。

说明书

技术领域

本发明涉及三维点云，尤其是涉及基于重心Voronoi剖分的点云均一化方法。

背景技术

点云是大量点的集合，随着扫描技术的日益发展，我们能利用扫描仪获取不规则物体的点云表达从而重构出该物体的网格信息，而后实现3D图像显示乃至3D打印等。

随着技术的发展，相关科技的成熟，Kinect、Sense等消费级扫描仪出现在了人们面前，人们可以在家就实现对物体的扫描，从而将物体转化为计算机上的模型。但是鉴于消费级的价格要求，设备的精度相对较低，扫描出来的点云存在分布过于密集、结构缺失、噪音等缺点。扫描仪程序一般会不会对扫描出的点云进行更多更好地优化，并且用户通常没有简单、快速和有效的办法对扫描点云进行处理，往往是扫描即所得。但是点云的分布情况直接影响了模型的好坏，最终影响了整个渲染显示的效果，所以对扫描信息的二次处理是十分必要和有意义的。

网格重构领域的重心Voronoi剖分方法，是将一个输入的初始网格进行重构，优化点的位置以得到一个性质更好的网格。但是该方法是建立在网格基础之上的一种方法，不适用于以点云为基础的数据。

发明内容

本发明的目的在于基于重心Voronoi剖分的点云均一化方法。

本发明包括以下步骤：

1)对所有的输入点建立kd-tree([2]Bentley J L.Multidimensional binary search trees used for associative searching[J].Communications of theACM,1975,18(9):509-517)，再查找k近邻，所述查找k近邻是给定一个坐标，查找与该坐标最接近的k个点的坐标；

2)对点云数据进行权值的赋值工作，具体方法如下：

首先进行5次拉普拉斯光顺，每一次普拉斯光顺的具体办法是：对每一个输入点，由步骤1)中提前建立的kd-tree求出距离kd-tree最近的10个输入点，然后将该点的曲率与这10个输入点的曲率求平均值，将该平均值作为该输入点的新权重；其次进行幂处理，即把每个输入点的权重再做一个实数的幂运算；

在步骤2)中，所述对点云数据进行权值的赋值工作，通常，每一个点的权重会被设置为其主曲率中较大的一个(设定权重的方法不限于此，具体根据用户的需求而定)，这样做的好处在使得输出点在物体表面尖锐处分布密集，在平滑处分布稀疏。权值设置完成后要进行曲率的光顺；所述实数的幂运算，可取2.5次幂。

3)用户指定一个所需要的输出点的数量n，然后根据权重在输入点集上进行点的采样，得到n个采样点；

在步骤3)中，所述点的采样的方式可为：

(1)求所有输入点的权重和，记为W；

(2)计算输出点的平均权重W_s，W_s＝W/n；

(3)设定一个累加器sum；

(4)遍历每一个输出点一次，每访问一个点，累加器sum就加上该点的权重，当累加器sum的值大于平均权重W_s时，即将当下遍历到的点加入采样点集Q中，同时sum减去W_s，如此操作后，将得到一个采样点集Q。

4)对采样点中的每一个点利用步骤1)中建立的kd-tree，查找该采样点在输入点中的k近邻，利用k近邻和该采样点计算最小二乘平面S，将该采样点投影到平面S上得到一个投影q*，以这个投影q*为中心，在平面S上生成一个正六边形的三角网格M，中心q*到正六边形的6个顶点的距离称为半径r，所述半径r的计算公式为：

r＝2(V_B-Box/n)^1/3

其中，V_B-Box为输入点云的包围盒体积，n为输出点个数，该正六边形网格被称作估计平面，那么每一个采样点对应一个正六边形的三角网格，记一个点-网格对为<q*,M>；

在步骤4)中，所述k可选为15。

5)如果点云模型没有边界，那么跳过此步骤；如果点云模型有边界，那么利用Point Cloud Library这个开源的代码库将边界提取出来，该边界称为外边界；

6)利用步骤4)中求出的所有点-网格对<q*,M>及步骤5)中提取的外边界计算Voronoi图，对于每一个点q*都将拥有一个Voronoi单元，Voronoi单元中含有其它点的网格，在计算Voronoi图时不需要考虑其它点的网格，仅需要考虑自己的网格，外边界只用于Voronoi单元的计算，其Voronoi单元中不需要计算多边形网格；

7)计算出Voronoi图后，对于每一个Voronoi单元中的多边形网格进行三角化操作，三角化操作是将网格中的多边形分解成多个三角形，三角化的目的在于计算不规则多边形的重心；

在步骤7)中，所述三角化操作可采用Delaunay三角化。

8)对每一个Voronoi单元，计算Voronoi单元的重心P，然后以该重心P作为采样点的新位置，重心P的计算公式如下：

其中，T表示一个Voronoi单元V中的三角形，i为该三角形的顶点，c_i表示点的权重，p_i表示点的坐标，A_T表示三角形T的面积；

9)将每一个点q*移动到新的Voronoi单元V的重心P后，计算的所有点-网格对及Voronoi图即失效，需要重新计算估计平面，即回到步骤4)估计平面，反复执行步骤4)～8)，即Lloyd迭代操作；

在步骤9)中，所述反复执行步骤4)～8)的次数最好为35～50。

10)如果对有边界的模型使用到步骤6)，那么在结束步骤9)时需要将外边界上面的部分点加入到最终的输出点中，具体方法是对步骤9)中得到的输出点再求一次边界，称为内边界，求出距离每一个内边界最近的外边界集合，将该外边界集合加入到最终的输出点中。

本发明采用重心Voronoi剖分来对输出点进行位置的优化。由于输入的信息为单纯的点，需要利用点集求出最小二乘面从而建立简单的离散网格，以期获得相关计算参数。利用点与离散网格计算Voronoi图，然后在每个Voronoi单元中，进行Lloyd迭代操作，使得点的分布达到预想状态，即重心Voronoi图([3]Qiang Du,Vance Faber,Max Gunzburger.Centroidal Voronoi Tessellations:Applications and Algorithms[J].Siam Review,1999,41(4):637-676)。

背景技术中提到扫描仪扫描出的点云数据就可以采用本发明进行优化，本发明的优势在于点云的简化、均一和去噪。其优点在于：

1)用较少的点去表达数量较多的输入点云想要表达的物体，将物体平滑表面的点更多地挪动到物体尖锐表面，有效降低扫描仪扫描出的冗余点；

2)对噪声有一定鲁棒性，扫描仪得到的数据一般是含有一定的噪声，造成生成的网格不够光滑等，本发明有对噪音数据的过滤作用；

3)使得输出点分布均一、呈现蜂巢状结构，视觉上呈现更好的观感，总体提升点的分布质量，为点云的进一步应用做出铺垫；

4)本发明利用网格重心Voronoi剖分相关技术进行了推广，使得其能直接处理建立在点云上面的数据；

5)采用重心Voronoi剖分来优化三维点云中点的位置信息。该方法首先在输入的粗糙三维点云上采点，然后通过估计每个采样点的所在平面和计算每个采样点的Voronoi单元，计算出采样点的重心位置，将采样点移动到新的位置即进行Lloyd迭代([1]Lloyd,S.P.Least squares quantization in PCM[J].IEEE Transactions on Information Theory 1982,28(2):129-137)，从而获得一个蜂窝状分布的点云结构。

附图说明

图1为本发明输入的不带边界的点云模型。

图2为本发明对输入点云进行采样后得到的采样点。

图3为本发明的单个估计平面示意图。

图4为本发明所有估计平面的示意图。

图5为本发明生成的Voronoi图和三角化的示意图。

图6为本发明最终输出点云结果。

图7为本发明输入的带边界的点云模型。

图8为一个边界提取的示意图。

图9为本发明利用边界进行Lloyd迭代的示意图。

图10为本发明对有边界的模型输出的结果。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

为了丰富结果，展示含有边界和不含边界两种情况，以下用2个实施例说明本发明，实施例1为不含有边界的模型，实施例2为含有边界的模型。并且实施例1在步骤S2中使用曲率作为权重，实施例2将权重全部设置为1。根据上述发明内容，实施例1执行除步骤S6和S10之外的8个步骤，实施例2执行全部步骤：

实施例1：

S1：输入原始点云，建立点云kd-tree。

读入一个约2.4万点的兔子点云模型(参见图1)，对所有点建立三维kd-tree。

S2：对点云的权重进行赋值，数值上等于点的主曲率较大的一个，并进行拉普拉斯光顺和幂处理。

S3：初始化输出点，采样。

指定输出3000个点，根据权重的采样结果如图2所示。

S4：计算估计平面。

单个估计平面如图3所示，将所有采样点的估计平面画出来将得到图4所示的分离网格(为了可视性，每个六边形的网格半径被适当缩小)。

S5：计算Voronoi图。

利用步骤S4中得到的所有点-网格对计算Voronoi图如图5(a)所示，一个Voronoi单元由一个多边形网格组成。

S6：无边界，此步跳过。

S7：计算出Voronoi图后，对于每一个Voronoi单元中的多边形网格进行三角化操作。

如图5(b)所示，将一个不规则多边形用许多小三角形表示。

S8：对每一个Voronoi图，计算单元的重心P，然后以该重心作为采样点的新位置。

即利用公式计算步骤S7中每一个不规则多边形的重心，然后将这个Voronoi单元的对应点移动到该重心。

S9：执行Lloyd迭代。

反复从步骤S4开始的操作，50次后，得到图6的输出点云。

S10：无边界，此步跳过。

实施例2：

S1：输入原始点云，建立点云kd-tree。

读入约12万个点的牙齿模型(图7)，对所有点建立三维kd-tree。

S2：对点云的权重进行赋值，权重全部为1。

S3：初始化输出点，采样。

指定输出10000个点。

S4：计算估计平面。

S5：计算Voronoi图。

S6：有边界，如图7所示的牙齿模型，对其进行边界提取操作，提取的边界如图8所示。边界被加入计算的示意图如图9所示，边界上的点参与Voronoi单元计算。

S7：计算出Voronoi图后，对于每一个Voronoi单元中的多边形网格进行三角化操作。

S8：对每一个Voronoi图，计算单元的重心P，然后以该重心作为采样点的新位置。

S9：执行Lloyd迭代。

反复从步骤S4开始的操作共50次。

S10：对于有边界的牙齿模型在步骤S9步后就需要将边界采样加入输出点，最终输出结果如图10所示。