基于八叉树和栅格法的点云简化算法

乔海峰　牛瑞涛

摘 要：随着大规模点云数据的大量涌现，点云简化问题成为数字几何处理领域的研究热点.为了提高实体反求的效率，提出一种点云简化方法。该方法通过划分栅格来建立采样点与空间栅格的拓扑关系，进而拟合出球面方程来估算该区域的曲率，并通过八叉树算法来保留曲率大的区域的点云，结果表明，该算法简单高效，所提出的点云精简算法能够对大量密集数据进行直接而有效的精简，并且对曲率变化大且含有较多细节特征的区域保留更多的细节信息

关键词：点云；简化；八叉树；栅格法

随着各种产品的极大丰富，从飞机到汽车到社会的各个方面，都要用到反求工程，而随着反求工程技术的发展，物体表面数据的采集方法越来越多样化，三维测量设备得到了长足的进步，设备的精度越来越高，得到的点云数据也越来越多，如果直接用海量的点云进行曲面重构，势必大大影响处理的速度和效率，所以，在不影响精度的条件下，对海量的点云进行简化就显的非常必要。近年来，人们对三维点云数据的简化进行了大量的研究，Hamann提出一种根据三角面处的曲率值决定该三角面的取舍，然后重新拟合出新的三维模型的方法，然而这方法只适用于STL文件的自动生成，不适用于对无序点云的精简。文献提出了平均距离精简法，但是这种方法容易丢失细节信息，且一般用于扫描线形式的点云数据。针对以上方法的不足，文章提出一种新的点云简化算法，该算法简单高效，适用于逆向工程中测量所得的散亂无序的点云数据，能够对大量密集数据进行直接而有效的精简，并且对曲率变化大且含有较多细节特征的区域保留更多的细节信息。

1 点云简化算法

文章提出的算法，是先通过栅格法，将海量的离散点云建立拓扑关系，并通过对各个栅格内的点云拟合出一个球面方程，来得到该栅格内点云的曲率；通过设置给定曲率值，来决定是否对栅格进行八叉树剖分，并在子栅格内进行拟合，进而达到高效的对曲率变化大且含有较多细节特征的区域保留更多的细节信息的目的。

由于离散点的分布缺少规律性，因此，在对点云进行简化等处理前应先建立点云的拓扑关系，文章通过对离散点云应用三维栅格法，来进行离散点云拓扑关系的建立。

文章主要是现给定合适的栅格宽度，和给定曲率对每个栅格内所有点拟合出球面方程，然后，根据拟合出的球面方程估算球面方程的曲率，并用估算出的球面方程的曲率和给定曲率比较，如果，则将与该栅格相邻的26个近邻进行合并，重新估算球面方程和曲率；如果，则对该栅格进行八叉树分解，并对八叉树中各个子栅格进行球面方程的拟合；直到八叉树各个子栅格内球面方程的曲率，通过子栅格内点云的质心与球心的连线来估算法矢，并对子栅格内的点云进行采样，从而实现点云的简化。

八叉树剖分算法流程

（1）将栅格进行八叉树剖分形成八个子栅格；

（2）若子栅格内点数大于等于4，则对该栅格内所有点分别拟合出球面方程并拟合出的球面方程的球心坐标及曲率，并继续（3），否则删除子栅格内的点转（4）；

（3）若曲率，估算出该栅格内所有点的质心坐标，计算出过球心坐标与质心坐标的方向矢量，并保留离质心坐标最近的点的数据，将方向矢量赋予给该点并转（4），否则转（1）；

（4）若还有子栅格没有被采样，则继续（2），否则，转（5）；

（5）若有上一级子栅格，则返回，并转（4），否则，转（6）；

（6）算法结束。

2 算法实例

为了验证文章算法的正确性和有效性，在测试硬件环境为Intel Core 2 Duo 2.0 GHz CPU，2GB内存，用C++语言在VC++6编译器上结合OpenGL库分别对某零件的点云模型进行了简化处理。图1为零件通过文章点云简化算法简化处理的效果。图1（a）为零件1的原始点云图，共有79629个点；图1（b）为栅格宽度和给定曲率时原始点云简化的效果图，共有49740个点，简化率为62.5%；图1（c）为栅格宽度和给定曲率时原始点云简化的效果图，共有28852个点，简化率为36.2%。从图中可以看出，简化点云不存在简化后点云的局部过密或局部过稀的情况，而且依然保留了原始点云的基本特征，没有出现形状的缺失，对于曲率变化较大区域特征区域表达依然清楚。

3 结语

文章提出了一种点云简化算法，该方法首先采用栅格法建立点云的空间拓扑关系，然后在此基础上拟合出球面方程，从而计算曲率值，并根据计算出的曲率值和给定的曲率值进行对比，决定是延伸到该栅格的26近邻还是进行八叉树剖分，并由此来对曲率较大出的区域保留较多的点，从而对点云进行简化。结果表明，该算法简单高效，所提出的点云精简算法能够对大量密集数据进行直接而有效的精简，并且对曲率变化大且含有较多细节特征的区域保留更多的细节信息。

参考文献

[1] Hamann B. A data reducation scheme for triangulated surfaces.Computer Aided Geometric Desig[J].1994，11（02）：197-214.

[2] 刘德平，陈建军.逆向工程中数据精简技术的研究[J].西安电子科技大学学报：自然科学版，2008，35（02）：334-339.