海量采样点集法向聚类并行估计及增量统一算法*

张 硕，孙殿柱，李延瑞，梁增凯

(1.山东理工大学 机械工程学院，山东 淄博 255049；2.西安交通大学 机械工程学院，西安 711049)

0 引言

近年来，点采样集合作为一种新的曲面表示方式，受到了广泛的关注，与基于网格技术相比，它无需存储和维护全局一致的拓扑信息，能对复杂的三维模型进行高效的绘制[1]和灵活的几何处理，因此在处理复杂或动态改变形状的模型时，具有更高的灵活性。而法向量作为点云的重要属性之一，其计算准确性直接影响到点云模型处理的有效性。如隐式表面重建算法[2-4]，重建结果的准确性很大程度上取决于法向计算的精确性。

目前常用的点云法向估计算法主要有三种：基于局部表面拟合的算法[5]，基于 Delaunay/Voronoi[6]的算法与基于鲁棒性统计[7]的算法。李宝等[8]对这三种方法及其改进算法[3，9]的原理与关键技术进行了详细分析。王醒策等[10]利用改进移动最小二乘曲面实现局部曲面拟合，增加法向估计的准确性。Alexandre[11]利用卷积神经网络算法与改进的霍夫变换算法提高样点法向估计的鲁棒性。以上算法虽然能较好的完成法向估计，但在处理海量采样点模型时，计算量过大，传统的串行计算不能满足计算能力的要求，因此需要借助于并行计算的支持。

随着软硬件技术的发展，并行计算的门槛不断降低。在海量点云处理中的应用也越来越广泛。Dey[12]利用八叉树对海量点云划分，并利用并行计算进行Delaunay 剖分。Bolitho等[13]在曲面重建中应用并行计算，充分利用多核处理器的计算性能与分布式内存管理框架，提高了程序执行的效率。基于OpenMP 框架的并行分层算法[14]将拓扑结构的遍历过程与层面轮廓的提取过程并行化计算，取得了接近处理器核心数目的加速比，分层时间明显降低。Boltcheva等[15]将并行计算用于Voronoi计算中，算法执行效率提高两个数量级以上。

针对现有法向估计算法在进行海量点云法向估计时效率低下，内存消耗大的问题，本文结合局部平面拟合和并行计算，提出了一种海量采样点集法向聚类并行估计及增量统一算法。即采用空间分解的方法进行并行计算。首先通过聚类算法将海量样点全集分成多个点云规模较小的样点子集；然后将各样点子集的法向量估计过程并行化计算；最后，选择初始样点子集，采用增量算法实现样点子集的法向统一。实验表明，利用该算法对海量采样点集进行法向估计，内存消耗明显降低且计算效率显著提高。

1 空间划分

本文采用一种简单的聚类方法对点云P进行空间划分。首先对点云P建立 kd 树，从 kd 树的根结点开始，选取前l层结点作为聚类中心, 记为O；则聚类中心的个数为m=2l-1。然后根据欧氏距离将P中所有样点分类，得到距离每个聚类中心最近的点集：

Si=p∈Prpoi,oj<ξ,i≠j.,ξ>0,oi,oj∈O

式中，rpoi,oj=poi-poj表示样点p与oi,oj的欧氏距离差，ξ为分界阈值，控制分界带的宽度。ξ越大，分界带的宽度越大。当0

(a)原始点云模型 (b)空间划分结果示意图

(c)ξ = 50 (d)ξ = 100图1 空间划分示意图

2 法向估计

经空间划分后形成的样点子集Si相互独立，具有高度并行性,可采用并行化的框架对样点子集进行法向并行估计。对每个样点子集Si派生出一个线程，同时进行法向估计计算。法向并行估计流程如图2所示：

图2 法向并行估计流程

由法向并行估计流程可知，利用局部平面拟合算法对子集Si进行法向并行估计。将Si作为独立计算单元，对p∈Si的k邻域集合进行局部平面拟合，并将该平面的法向量np作为p的法向量。

(a)k近邻示意图 (b)法向量示意图图3 法向估计示意图

如图3所示，np的准确性取决于k邻域集合是否能更准确的反映样点p周围采样面的形状信息。设λp表示样点p∈Si的k近邻集合，若p为非分界样点，即p位于Si内部，则λp分布于p周围，近似高斯分布；λp能很好的反映p周围区域的形状，因此，可利用该邻域拟合平面的法向量代表p的法向量。若p为边界样点，即p∈Uij,则λp的分布偏向于一侧，无法准确反映实物表面目标样点周围区域的形状，增大法向估计误差。因此，对于分界样点p∈Uij，可在P中搜索p的k近邻集合λp，并以λp作为p周围区域的样本计算法向量。

经上述计算得到的法向量具有二义性，即只得到了法向量所在的直线，而没有确定法向量的朝向。利用 Hoppe的法向统一算法实现样点子集内部法向的统一。

3 法向统一

经法向估计后的样点子集内部的法向朝向一致，但不同样点子集的法向量朝向不一，无法判断各子集的法向量指向模型的内部还是外部，导致样点全集的法向朝向不一。

采用增量算法对各样点子集间进行法向统一。首先选择Si作为初始样点子集T,如图4b中亮灰色区域所示。然后在已完成统一的集合T的基础上利用分界样点的特性，查询子集Sj与T的位置关系，即判断Sj是否与T相邻接。若Sj与T相邻接，将Sj并入集合T，此时Sj与T的分界样点退化成T的内部样点，Sj中的部分分界样点更新成T的分界样点。从Sj与T的分界样点集合中任选一点p，若np∈Sj·np∈T<0，说明Sj与T中样点法向量的朝向不同，则翻转Sj内的法向量，使集合T中样点的法向量始终保持一致，这一计算过程可表示为一个迭代的计算过程，直到S中所有子集全部并入T中, 则停止计算。法向统一过程如图4所示。

(a)未统一法向示意图 (b)选取初始样点子集

(c)选取增量子集 (d)完全统一示意图图4 法向统一过程示意图(浅灰色区域表示为统一的样点子集，亮灰色区域表示统一后的样点子集,黑色区域表示样点子集的分界样点)

4 实验与分析

为验证本文所提出算法的法向估计效果，在硬件配置为 HPxw8600 Workstation(4 ×2.5GHz, 4.0GB DDR2 内存)，操作系统为 GNU/Linux 的测试环境中，并行框架采用 OpenMP, 版本为 4.5。CGAL 版本为 4.10。应用 CGAL中的法向估计模块。分别利用法向并行估计算法与串行算法对不同规模的数据进行测试。

本文算法所涉及到的主要参数l，ξ，k，其中l控制聚类簇的数目，l越大，则空间划分的簇数越多。从kd树的根结点开始，选取的前l层结点作为聚类中心，则聚类中心的个数为:m=2l-1。l越大，法向估计时间缩短，但聚类时间增加，且l>7程序执行时间收敛。经大量实验验证，当5

表1 串行计算与并行计算时间对比

观察dragon模型(58M)在实验过程中的内存与CPU的使用状况。如图5所示，折线图表示程序运行过程中内存的使用情况：oa1，oa2段为数据读入阶段，内存消耗无明显差别。a1b1段为空间划分阶段，因此，在此阶段内存消耗大于串行算法。b1c1段为法向并行估计阶段，其中，内存消耗量呈现无规律性波动，这是因为计算机在进行并行估计过程中，计算中的样点子集的规模存在差异及线程切换产生的波动。c1d1段与d1e1段分别为写入文件阶段与内存释放阶段，内存消耗基本维持不变。在串行计算内存消耗过程中，a2b2为法向估计阶段，内存消耗量有所增加，但增加的速度较缓慢。b2c2段为法向统一阶段，无向图的构建与最小生成树的生成消耗大量内存，因此，在此阶段，内存消耗量急剧增加，内存消耗峰值约为 53%。

图5 串行计算与并行计算内存消耗与CPU使用率对比图

如图5中柱状数据显示，在t=100s时对并行算法中的CPU进行监控，其中，4个核心的负载均接近最大值，处于平衡状态，在96%～99%范围内波动。在t=300s是对串行算法中的CPU测得数据中，其中，仅有1个核心的负载达到峰值，参与程序执行过程。

为验证不同算法对该模型的法向估计效果，以不同算法所得法向信息作为输入，并利用文献[15]中的 poisson算法对该模型进行曲面重建，依据重建效果判断法向估计结果的准确性。重建结果如图6所示。对局部尖锐区域进行放大显示，从图中可看出，采用法向并行估计与串行估计所得结果无明显差距。

(a)串行计算 (b)并行计算图6 dragon采样数据与不同算法所得法向的 曲面重建效果

5 结论

本文利用聚类算法将海量采样点集分解成多个样点子集，利用并行计算进行各样点子集的法向估计，并采用增量算法完成样点子集间的法向统一，提出一种海量采样点集法向聚类并行估计及增量统一算法。主要有以下特点：

(1) 应用并行法向估计算法能充分利用多核处理器的计算优势，显著降低采样点集法向估计时间。

(2) 对分解后的样点子集得计算实现并行化，有效提高程序执行过程中的内存利用率，减少空间复杂度，可以处理更大规模的点云数据。

(3) 将并行计算应用于海量点云的法向估计，保证了对采样点集法向估计的准确性不低于现有算法，但无明显提高，后续工作可尝试改进法向估计算法，以此实现法向的正确估计。