袁 华，庞建铿，莫建文

(桂林电子科技大学 信息与通信学院，广西 桂林 541004)

基于体素化网格下采样的点云简化算法研究

袁 华，庞建铿，莫建文

(桂林电子科技大学 信息与通信学院，广西 桂林 541004)

针对三维点云数据冗余量大、重建时间长、效率低等问题，提出一种基于体素化网格下采样的点云简化算法。该算法首先求出点云数据集的最小三维长方体包围盒，把点云数据划分进三维体素栅格中去；其次计算点云的k邻域，进行曲面法向量估计；然后，在三维体素栅格中选择满足要求的数据点，实现点云下采样；最后，调用Power Crust对下采样点云数据进行曲面重建，在三维可视化类库Visualization Toolkit(VTK)进行显示。实验结果表明，该算法能够加快三维点云数据的重建速度，较好地保持了点云特征，提高曲面重建的效率和鲁棒性，适合实时处理。

三维点云；体素化栅格；点云简化；Power Crust；曲面重建

随着激光扫描仪测量精度的不断提高，点云数据正以惊人的速度增长，产生大量冗余数据，存储、处理、显示这些点云数据会增加计算机处理的负担，占用较多的计算机资源，导致降低点云数据存储、操作的效率，尤其会影响到后续曲面重建的效率。因此，在保证能为曲面重建提供必要信息的条件下，简化采集得到的点云数据是十分必要的，已经成为了一项具有挑战性的问题。

目前，点云简化受到了国内外诸多学者的重视，提出了一些优秀的点云简化算法。Su等[1]提出了一种基于采样点云模型曲率感知的快速简化算法，该算法对点云进行特征区与非特征区的划分，可以较好保留曲面特征，对点云简化采取自适应调整，但对噪声和异常值比较敏感。Shi等[2]对点云数据使用k均值聚类，自适应调整点云简化，能够使得点云数据模型边界保持完整，但重建时间效率比较低。张飞飞等[3]提出了一种基于B样条曲线的简化算法，可以简化复杂的模型和大型点云数据，曲面拟合稳定，但曲率计算需要复杂的矩阵运算，随着点云数据规模的增多，重建运行时间增长。Wang等[4]将特征参数和均匀球面采样结合起来，对点云数据进行大规模简化，可以较好地保留原始数据模型的尖锐特征，但大规模精简容易使得点云模型出现空洞，导致点云数据模型重建质量变差。Lee等[5]将离散形态算子引入点云简化，进行点云数据模型特征提取，能够较好地保留点云数据模型的几何特征，但容易受到噪声的干扰。陈璋雯等[6]在点云简化中使用模糊熵迭代，保留点云数据模型较多的细节特征，从而可以更好地保持点云数据边界的完整性，但需要计算所有数据点的曲率，计算量比较大。史宝全等[7]提出了基于聚类的点云精简算法，该算法对点云进行栅格划分，选取代表点，进行聚类并依据法向量的变化对各类进行细分，最后进行均值漂移，生成模态点，能够保持点云特征。Zhao等[8]提出了采用均匀网格进行点云简化，该算法能够保留较多的点云特征，避免曲率估计，但对捕获模型的形状不够敏感。

通过对上述提及的简化算法进行分析，可以将它们分为两类：一类是计算反映曲面特征的参数值[1-6]，通过对点云数据的每个点的k近邻变化，计算反映曲面特征的参数值，从而达到点云简化的目的，能够保留较多的细节，但计算量大，耗费时间长；另一类是基于拆分[7-8]，将所有点云数据拆分到相应的单元中去，每个单元保留一个点来代表所在单元所有点，比较简单、有效，但使用尺寸网格等，对捕获模型的形状不够敏感，重建质量不是很好。为了克服以前的方法的限制，提出一种将两种相结合的体素栅格化下采样的点云简化算法：通过求出输入的三维点云数据的最小三维长方体包围盒，根据设定的边长将长方体空间划分成一系列小立方体(称为栅格)，把所有点云数据划分到栅格中去，求出每个点的k近邻，进行法向量估计，然后在此基础上选择靠近三维栅格中心集重心的最近点来代表体素栅格中其他点，从而实现点云简化。对简化后的点云调用Power Crust算法进行曲面重建，接着对曲面网格进行简化、平滑等处理，通过局部形状校正基础上获得三维可视化模型，并显示、实时交互。应用实例结果表明此算法有利于减少渲染时间和提高重建效率，重建曲面较为准确、光滑，可以很好防止点云特征信息的丢失，适合实时处理。

1 点云简化算法

体素化网格下采样[9-14]主要思路是：根据点云数据创建一个最小三维体素栅格，然后计算出需要划分的小立方栅格的边长L，根据L的大小将三维体素栅格分解成m×n×l个小栅格，栅格划分完毕后将点云数据放到相应的小栅格中，同时删除那些不包含数据点的小栅格，在每个小栅格中，将离小栅格重心最近的数据点保留下来，删除其余的数据点。该方法简单高效，容易实现，不需要建立复杂的拓扑结构，从整体上对点云数量进行简化，实现了简化点云，从而达到快速三维点云曲面重建的目的。其计算步骤如下：

1)小立方栅格的边长L的确定[9-10]。在体素化栅格下采样点云简化算法中，小立方体栅格边长L的选取十分重要：过大的栅格会降低搜索效率，过小的栅格则会出现空的栅格。小立方栅格的边长与邻近点个数k成正比，与点云的平均密度成反比，当点云的平均密度小时，表示在固定空间内的点云数量少，那么应将L取大些来提高k邻近搜索的范围，以保证有足够多点云进行k近邻的计算；当点云的平均密度大时，则表示在固定空间内的点云数量较多，应将L取小些，以保证在最适当的范围内搜索，降低搜索的时间。

小立方体栅格边长为

(1)

式中：α是比例因子，用来调节小立方体栅格的边长；s是比例系数；g是小栅格中点云数据的数目。

单位小栅格中包含的点云数据个数

n=N/V

(2)

式中：N表示点云数据中点的总数；V表示三维体素栅格的体积。

三维体素栅格的体积

V=LxLyLz

(3)

式中：Lx表示点云X轴方向最大范围；Ly表示点云Y轴方向最大范围；Lz表示点云Z轴方向最大范围。而为了方便后续的统计，应确保数据点不会出现在外接三维体素栅格的角、边和面上。因此，适当的将长方体向外扩大，增加距离λ对其修正。所以，三维体素栅格三边的长度应该是

(4)

将式(2)、(3)代入式(1)可得

(5)

2)将点云数据划分到小立方体栅格中。根据小立方体栅格的边长L，将点云数据划分为m×n×l个小立方体栅格，其中，m=ceil(Lx/L)，n=ceil(Ly/L)，l=ceil(Lz/L)。ceil(x)为取整函数，表示不小于x的最小整数。对于任一点pi，其所属小立方体栅格号为

(6)

在整个栅格编码中，点pi的栅格编码为(mpi,npi,lpi)，如果转换为一维编码的话，点pi的栅格编码为

Vpi=mpi×n×l+npi×l+lpi

(7)

3)根据式(6)或式(7)求出点云数据模型的每个数据点的栅格编码，且将编码放进哈希链表，建立点云数据间的空间拓扑关系后，确定出每个数据点pi的邻近点。数据点pi的邻近点是在它本身所在的小栅格和相邻小栅格中的数据点。而k邻域的确定是计算这些数据点到点pi的距离，并将按距离的远近，取出离点pi最近的前k个数据点，存入到哈希链表中，作为数据点pi的k邻域点。k的取值，要综合考虑物体表面的凹凸性和点云数据模型的密度，并且要确保重建得到的曲面在每个数据点的邻近范围内是单凸性或者单凹性的，故k取值范围一般为8～20。

4)散乱点云法向量的估算。利用最小二乘平面法来估计数据点的法向量，假设物体的采样表面是足够光滑的，则采样得到的物体表面的数据点就可以用最小二乘平面法来实现曲面拟合。根据点云数据模型中的每个数据点pi及其k近邻点，计算出每个数据点pi及其k近邻点的最小二乘局部平面H

(8)

(9)

5)代表点的选取及下采样实现。根据步骤3)求出的点云数据模型中每个点pi的邻域和步骤4)求出的点云数据模型中每个数据点pi的法向量，求出每个数据点pi的法向量与其邻近点法向之间的夹角。若法向量之间的夹角越大，则说明数据点pi在其k近邻附近的曲率变化比较大，存在尖锐的几何特征。相反，若法向量之间的夹角越小，则说明数据点pi在其k近邻附近的曲率变化比较小，存在稀疏的几何特征。因此，可以预先设定一个阈值，当数据点pi的法向量与其邻近点法向量之间的夹角大于阈值，则将该数据点视为特征点，调整边长比例因子α，使得立方体栅格边长变小，每个栅格点云数量变少，这样可以保留较多特征数据点。夹角小于阈值的点作为非特征点，调整边长比例因子α，使得立方体栅格变大，每个栅格点云数量变多，保留较少非特征数据点。每个小立方体栅格中，三维栅格中心集重心为

(10)

式中：g为小立方体栅格中点云数据个数。选取最靠近重心数据点保留下来，代表这个小立方体栅格所有数据点，实现点云下采样。

整个基于体素化栅格下采样的点云简化算法流程图如图1所示。

图1 基于体素化栅格下采样的点云简化算法流程图

2 实验结果及分析

为验证算法的有效性和健壮性，实例选用兔子、猫、马3组三维点云数据模型来进行测试。图2是3种三维点云数据模型的原始点云图，对应的调用Power Crust算法重建的效果图见图3；图4～图6是3种点云数据模型经过单位统一化为厘米后的栅格边长分别为(2 cm×2 cm×2 cm)、(3 cm×3 cm×3 cm)、(4 cm×4 cm×4 cm)3种体素栅格下采样后三维点云图，对应的调用Power Crust算法重建的效果图是图7～图9。表1～表3是3组点云数据的点云简化参数表。

图2 三维点云数据原始点云图

图3 三维点云Power Crust曲面重建效果图

图4 点云体素栅格(2 cm×2 cm×2 cm)下采样点云图

图5 点云体素栅格(3 cm×3 cm×3 cm)下采样点云图

图6 点云体素栅格(4 cm×4 cm×4 cm)下采样点云图

图7 点云体素栅格(2 cm×2 cm×2 cm)下采样后曲面重建效果图

图8 点云体素栅格(3 cm×3 cm×3 cm)下采样后曲面重建效果图

图9 点云体素栅格(4 cm×4 cm×4 cm)下采样后曲面重建效果图

点云名称对应栅格调节系数α近邻系数k点云个数三角形个数点数的简化率/%简化时间/s兔子原始点云100203593971858054299(2cm×2cm×2cm)下采样点云07520159033180044223599(3cm×3cm×3cm)下采样点云0552078561570421912754(4cm×4cm×4cm)下采样点云030204619922412907356

表2 猫点云点云简化参数表

点云名称对应栅格调节系数α近邻系数k点云个数三角形个数点数的简化率/%简化时间/s猫原始点云100201000019998016289(2cm×2cm×2cm)下采样点云065202934548829305262(3cm×3cm×3cm)下采样点云050201753351417503086(4cm×4cm×4cm)下采样点云0252080616088102241

表3 马点云点云简化参数表

点云名称对应栅格调节系数α近邻系数k点云个数三角形个数点数的简化率/%简化时间/s马原始点云100204848596938089008(2cm×2cm×2cm)下采样点云07020147562947630419272(3cm×3cm×3cm)下采样点云0552099461987020509868(4cm×4cm×4cm)下采样点云0352059461123212205846

体素栅格下采样点集的密度随着表面的细节变化而不同，所有的采样点都有很多的局部特征。从图7中兔子点云的曲面重建图中可以看出：兔子点云体素栅格下采样后点云依然密集的背部、后腿上部，这些地方特征点比较多，点云曲率变化明显；而在特征点比较少的地方，如腹部，与原始点云相比非常稀疏。从简化效果来看，在实现点云体素栅格下采样点云简化的同时，可以很好地保留点云的特征，防止特征信息的丢失。

栅格边长的调节系数α影响点云简化算法的效率，α取得越大时，栅格的边长就越长，对点云数据进行搜索耗费的时间就越长，同时由于栅格的边长越长，栅格内的点云的数目越多，每个点的法向量估算时间就越长，自然简化的时间就变长。

从三维点云曲面重建的效果图来看，图7和图8基本能够很好地反映了三维点云的立体效果，保持原始点云的曲面特征和拓扑结构没有太大变化。而图9点云曲面重建存在空洞，部分细节缺失。很明显，体素栅格边长选的过大，去除的点云过多，剩余点云不能体现原始点云的特征，重建曲面质量变差。

因此，应根据不同的三维点云数据模型，并考虑到点云数据模型的平均密度和实际情况的要求，选取合适的体素栅格边长。图7与图8的曲面重建质量较好，但图7对应的3种点云数据平均简化率为34.64%，图8对应的3种点云数据平均简化率为19.97%，相应的图7的曲面重建时间比图8的长。根据简化率、复杂度、曲面重建时间和曲面重建效果图等因素综合考虑，在这3种模型中选择(3 cm×3 cm×3 cm)作为体素栅格边长较为合适，在保持重建质量下，重建效率有较好的提高。

3 结语

在分析了现有的点云简化技术基础上，基于对点云数据的栅格化，结合每个点的法向量信息实现了体素栅格下采样。应用实例结果表明，该方法可以加快了基于Voronoi图和Delaunay三角剖分的Power Crust曲面重建效率，同时可以很好地保留的点云数据的特征信息，实现了快速三维点云曲面重建，具有较强鲁棒性，适合实时交互处理。这一方法在一定程度上提高了点云简化的效率和实时处理能力，可以很方便地应用在各个需要获取物体近似表面模型的领域，节约了后续曲面重建的执行时间和降低计算机的负担。相信在不久的将来，随着计算机技术的发展以及图像处理技术的深入研究，三维点云曲面重建将会拥有广泛的应用空间。

[1] SU Z，LI Z，CAO J. Curvature-aware simplification for point-sampled geometry[J]. Journal of Zhejiang University Science C，2011，12(3)： 184-194.

[2] SHI B Q， LIANG J， LIU Q. Adaptive simplification of point cloud using k-means clustering[J]. Computer-Aided Design， 2011， 43(8)： 910-922.

[3] FEIFEI Z， CHE X， ZUO W. A simplification algorithm for point cloud data based on B-spline curve[J]. Journal of Computational Information Systems， 2012， 8(5)： 1821-1828.

[4] WANG L， CHEN J， YUAN B. Simplified representation for 3D point cloud data[C]//Proc. 2010 IEEE 10th International Conference on Signal Processing(ICSP 2010). Beijing，China：IEEE Press，2010：1271-1274.

[5] LEE P F，HUANG C P. The DSO feature based point cloud simplification[C]//Proc. 2011 Eighth International Conference on Computer Graphics，Imaging and Visualization (ICCGIV 2011). Singapore，Singapore：IEEE Press， 2011：1-6.

[6] 陈璋雯，达飞鹏.基于模糊熵迭代的三维点云精简算法[J].光学学报，2013，33(8)：153-159.

[7] 史宝全，梁晋，张晓强，等.特征保持的点云精简技术研究[J].西安交通大学学报，2010，44(11)：37-40.

[8] ZHAO Y，LIU Y，SONG R，et al. A saliency detection based method for 3D surface simplification[C]//Proc. 2012 IEEE International Conference on Acoustics，Speech and Signal Processing(ICASSP 2012). Kyoto，Japan：IEEE Press，2012：889-892.

[9] YU H， WANG R， CHEN J， et al. Saliency computation and simplification of point cloud data[C]//Proc. 2012 2nd International Conference on Computer Science and Network Technology(ICCSNT 2012). Changchun，China：IEEE Press，2012：1350-1353.

[10] ZHAO X， WEN M H. Kd-tree based nonuniform simplification of 3D point cloud[C]//Proc.2009 3rd International Conference on Genetic and Evolutionary Computing(ICGEC 2009).Guilin，China：IEEE Press，2009：339-342.

[11] ORTS-ESCOLANO S， MORELL V， GARCIA-RODRIGUEZ J， et al. Point cloud data filtering and downsampling using growing neural gas[C]//Proc. 2013 International Joint Conference on Neural Networks(IJCNN 2013). Dallas，TX，USA：IEEE Press，2013：1-8.

[12] 邱春丽，许宏丽.一种散乱点云空间直接剖分算法[J].计算机科学，2014，41(2)：157-160.

[13] SANYUAN Z， FENGXIA L， YONGMEI L， et al. A new method for cloud data reduction using uniform grids[C]//Proc. 2013 International Conference on Advanced Computer Science and Electronics Information(ICACSEI 2013).Beijing，China：IEEE Press，2013：64-67.

[14] BENHABILES H， AUBRETON O， BARKI H， et al. Fast simplification with sharp feature preserving for 3D point clouds[C]//Proc. 2013 11th International Symposium on Programming and Systems(ISPS 2013). Algiers，Algeria：IEEE Press，2013：47-52.

[15] 应申，毛政元，李霖，等.利用3D Voronoi 图的兔子点云聚类分割[J].武汉大学学报：信息科学版，2013，38(3)：358-361.

[16] MENG X H， LI J G， YANG Q， et al. Complex conforming delaunay triangulation[J]. Science China Information Sciences，2010，53(6)：1130-1140.

袁 华(1975— )，讲师，硕士，主要研究方向为图像处理、智能图像处理；

庞建铿(1989— )，硕士研究生，主要研究方向为图像处理，本文通讯作者；

莫建文(1972— )，副教授，博士，硕士生导师，主要研究方向为模式识别、智能信息处理、图像处理。

责任编辑：时 雯

Research on Simplification Algorithm of Point Cloud Based on Voxel Grid

YUAN Hua，PANG Jiankeng，MO Jianwen

(SchoolofElectronicandTechnology，GuilinUniversityofElectronicTechnology，GuangxiGuilin541004，China)

Focus on the issue that high data redundancy， long reconstruction time and low efficiency exist in three-dimensional point cloud data，a simplification algorithm of point cloud based on 3D voxel grid is proposed. Firstly， the minimum three-dimensional rectangular bounding box is calculated， and point cloud are divided into the 3D voxel grid. Secondly， the k-nearest neighbors of point cloud is searched， and the surface normal vector is estimated. And then， sample points by using uniform 3D voxel grids to select the points that satisfy the requirement. Finally， using Power Crust algorithm reconstructing surface， and displaying in the three-dimensional visualization library VTK(Visualization Toolkit). The experimental results show that the proposed method can speed up the reconstructing rate of three-dimensional point cloud， retain geometric characteristics of original dates， improve the surface reconstructing efficiency and robustness， and be able to real time processing.

3D point cloud；voxel grid；point cloud simplification；Power Crust；surface reconstruction

广西自然科学基金项目(2013GXNSFAA019331；2014GXNSFDA118035)；桂林电子科技大学研究生教育创新计划资助项目(GDYCSZ201453)

TN919.85

A

10.16280/j.videoe.2015.17.011

2015-03-15

【本文献信息】袁华，庞建铿，莫建文.基于体素化网格下采样的点云简化算法研究[J].电视技术,2015，39(17).