一种基于体素网格的三维点云均匀降采样方法.pdf

机械设计与制造180Machinery Design&Manufacture第8 期2023年8 月一种基于体素网格的三维点云均匀降采样方法肖正涛12,高健,吴东庆”,张揽宇1（1.广东工业大学省部共建精密电子制造技术与装备国家重点实验室，广东广州510 0 0 6；2.广东工贸职业技术学院机电工程学院，广东广州510 510;3.仲恺农业工程学院计算科学学院，广东广州510 2 2 0摘要：降采样是三维点云预处理过程中的重要环节，体素网格法是一种被广泛使用的降采样方法。针对体素网格降采样方法存在着采样点分布不均匀的问题，提出了一种新的体素网格降采样方法。首先对点云建立轴向包围盒，然后以某一个等分距离对包围盒沿,y,z轴三个方向的边进行等分，使得每一个体素近似为一个正方体，然后计算每一个体素内所有点的重心，并将其作为该体素的采样值。实验结果表明，当点云包围盒在x,y，z 轴三个方向的边长相差非常悬殊时，该方法比传统的体素网格法获取的点云分布更均匀，而且该方法的计算效率比传统的体素网格法更高。关键词：体素网格；降采样；点云精简；均匀采样；包围盒中图分类号：TH16;TP391文献标识码：AA Uniform Downsampling Method for Three-DimensionalPoint Clouds Based on Voxel GridsXIAO Zheng-tao-2,GAO Jian,WU Dong-qing,ZHANG Lan-yu(1.State Key Laboratory of Precision Electronic Manufacturing Technology and Equipment,Guangdong University of Tech-nology,Guangdong Guangzhou 510006,China;2.School of Electromechanical Engineering,Guangdong Polytechnic ofIndustry and Commerce,Guangdong Guangzhou 510510,China;3.School of Computational Science,Zhongkai Universi-ty of Agriculture and Engineering,Guangdong Guangzhou 510220,China)Abstract:Downsampling is an important step in the preprocessing of three-dimensional(3D)point clouds,and the voxel grid is awidely used downsampling method.Aiming at the problem of uneven distribution of sampling points in the traditional voxel griddownsampling method,a new voxel grid downsampling method is proposed in this paper.Firstly,an axis-aligned bounding boxis established for the point cloud,and then the edges of the bounding box along the x,y,z axes are equivalently divided by a cer-tain distance,so that each voxel is approximately a cube.Then,the coordinate mean value of all points in each voxel are calculat-ed and taken as the coordinate sampling value of the voxel.The experimental results demonstrate that when the side lengths of thepoint cloud bounding box along the x,y and z axes are very different,the downsampling point cloud distribution obtained by theproposed method is more uniform than that obtained by the traditional voxel grid method.Furthermore,the computational effi-ciency of the proposed method is higher than that of the traditional voxel grid method.Key Words:Voxel Grid;Downsampling;Point Cloud Simplification;Uniform Sampling;Bounding Box文章编号：10 0 1-39 9 7(2 0 2 3)0 8-0 18 0-0 51引言随着三维激光扫描技术的快速发展和普及，三维点云的获取变得越来越容易。由于三维激光扫描技术具有非接触、高效率、高精度等优点，已被广泛应用在自动化加工生产线、虚拟现实、无人驾驶汽车等领域。由于实际得到的三维点云数据往往包含有大量的余数据，在使用点云数据前通常要进行降采样(Downs-Amplingl)处理，以提升点云的最终处理效率和效果。降采样，也称下采样，简而言之就是对点云进行精简2-3。点云降采样的方法有很多，通常分为不考虑点云细节特征和考虑点来稿日期：2 0 2 2-0 6-0 5基金项目：国家自然科学基金重点项目一广东省联合基金项目（U1601202)作者简介：肖正涛，（19 7 6-），男，湖北武汉人，博士研究生，主要研究方向：三维物体识别、机器人视觉；高健，（19 6 4-),女，山东青岛人，博士研究生，博士生导师，教授，主要研究方向：数字化制造与再制造技术、微电子封装装备与工艺等云细节特征两大类。不考虑点云细节特征的降采样方法有体素网格（VoxelGridl41）、系统采样（SystematicSampling5）、随机采样(Random Samplingl）、最远点采样(Farthest Point Sampling/7)等。考虑点云细节特征的算法一般会将点云的法向、曲率、是否位于边缘等信息结合在内。文献8 提出了一种基于栅格动态划分的点云精简方法，对不同的区域采取不同精简策略，该方法能较好地保持模型的细微特征。文献9 提出了一种能够保留边缘点的点云简化算法，通过八叉树建立k邻域，以法向量为依据检测并保留边缘特征点，该算法保留的边缘点大部分为模型的尖锐点。第8 期文献10 提出了一种自适应下采样深度学习网络，该方法能根据应用、任务和训练数据的不同，减少无序点云中的点数，同时保留重要点。文献提出了一种基于曲率泊松碟采样的散乱点云精简方法，该方法通过计算点云的曲率特征将点云划分为平坦区域和特征区域，然后对不同的区域使用不同的降采样策略，使得平坦区域能够均匀精简的同时最大化地保留点云的细节特征。这些不同的降采样方法通常有各自适合的应用场景。体素网格法是一种常用的降采样方法。该方法先对三维点云建立轴向包围盒（Axis-AlignedBoundingBox，简称AABB12），然后沿各个坐标轴方向将包围盒分成n等份，接着计算每一个体素中所有点的重心，并将其作为该体素的采样值。体素网格法计算效率高，当轴向包围盒在x,y，z 轴三个方向的边长相差不是太过悬殊的情况下，得到的采样点分布均匀，因而该方法被广泛使用。体素网格法存在着一个不足之处：当点云的轴向包围盒在x，y,z轴三个方向的边长相差较大的时候，体素网格法得到的点云就变得不均勾，在长边方向点的分布较稀，在短边方向点的分布变得密集。不均匀点云会影响点云的法向和曲率计算，进而影响点云的后续处理，如配准、特征计算等的效果。因而,确保降采样后的点云在空间分布均匀是一项非常重要的工作。针对传统体素网格法存在的不足，提出了一种新的体素网格法。该方法将点云轴向包围盒沿x,y，z 轴三个方向的边分成不同的份数，使得每一个体素近似是正方体而不是与包围盒相似的长方体，然后计算每一个体素内所有点的重心，并将其作为该体素的采样值。这样，无论轴向包围盒x，y，z 轴三个方向的边长是否相差悬殊,新的体素网格降采样方法皆可得到均匀分布的降采样点云。2一种新的体素网格法当点云轴向包围盒在x，y，z 轴三个方向的边长相差不是太过悬殊的情况下，传统体素网格法表现优异，不仅计算效率高，而且得到的采样点在空间分布也非常均匀。但当点云轴向包围盒在x,y,z轴三个方向的边长相差非常悬殊的时候，由于x,y,z轴三个方向的边都分成同样的份数，每一个体素皆是一个与包围盒相似的小长方体，因而每一个体素的边长同样也会相差悬殊，最终会导致包围盒最短边所在方向的采样点分布比最长边所在方向的点分布要密集得多，也即采样点在空间分布不均匀。针对传统体素网格法存在的问题,提出了一种新的体素网格降采样方法。该方法将点云轴向包围盒x，y，z 轴三个方向的边分成不同的份数，使得每一个体素是正方体而不是与包围盒相似的长方体。假设正方体体素的边长是den,则点云轴向包围盒x,y,z轴三个方向的边分成的份数如下：Ln,=round(dtenLny=roundden)Ln,=round(dun）式中：L、L,、L一轴向包围盒沿x,y，z 轴方向的边长；n、n,、n 一轴向包围盒x,y，z 轴三个方向的边分成的份数;round一四舍五人运算。肖正涛等：一种基于体素网格的三维点云均匀降采样方法索引到一维索引的转换公式如下：idx=i*(n,+1)(n,+1)+j*(n,+1)+h式中:idx一体素的一维索引,ie0,n,je0,n,e0,n,。这样,每一个三维索引(i,j,k)就唯一对应着一个一维索引idx。每一个一维索引idx也同样唯一对应着一个三维索引(i,j,h),从公式可推知一维索引到三维索引的计算公式如下：idxi=trunc(n,+1)(n.+1)(idx-i*(n,+1(n,+1)j=trunc(n.+1)k=idx-i*(n,+1)(n,+1)-j*(n,+1)式(3)和式(4)建立起了体素三维索引与体素一维索引的一一对应关系。新的体素网格降采样方法的算法过程是：首先对点云建立轴向包围盒，然后以某一个等分距离对包围盒沿x,y,z轴三个方向的边进行等分，使得每一个体素近似为一个正方体，然后计算每一个体素内所有点的重心，并将其作为该体素的采样值。整个算法，如算法1所示。算法1一种新的体素网格下采样方法Algorithm.1ANovel Voxel Grid Downsampling MethodInput：点云A,等分距离dLenOutput：降采样后的点云B1:计算点云A的轴向包围盒，获得包围盒x,y，z 轴三个方向的边长分别为L,L,L.L2:nround,nyrounddLendlenx，y，z 轴三个方向的边分成的份数。j-truncn,dd3:itrunc(cnLA中每一个点所属体素的三维索引4:idx*(n,+1)(n.+1)+*(n.+1)+k,将体素的三维索引转换为(1)一维索引5:for index=0:(n,+1)(n,+1)(n,+1)do6:if索引为index的体素不为空7:计算该体素内所有点的重心，并将其作为该体素的采样值8:end if9:end for10:return B181从公式可知，最终得到的每一个体素近似是一个正方体，如图1(a)所示。任意点所在体素的三维索引(ij,k)的计算公式,如式(2)所示。i=truncnLj=truncnydk=truncn式中：d、d,、d 一点到包围盒左侧面、前表面和下表面的距离；trunc一截断取整；其余符号表示的意义与公式中的相同。将所有体素的三维索引转换为一维索引,如图1(b)所示。如果按照先x轴方向，然后y轴方向，最后z轴方向的顺序，从三维(3)(4)LL,n,round，计算包围盒dLen,ktruncn,，计算点云(2)No.8182机械设计与制造,-1表1实验点云和轴向包围盒边长（mm）,-1(.j.A)n,-1-1(a)轴向包围盒的体素(b)将体素的三维索引近似为正方体转换为一维索引图1一种新的体素网格降采样方法Fig.1 A Novel Voxel Grid Downsampling Method3实验3.1实验环境和实验点云实验点云数据是用CREAFORMHandySCAN700手持式三维激光扫描仪获得，以OpenCV和PCL（Po i n t Cl o u d Li b r a r y)为计算平台，计算机配置是Intel酷睿I5-7200U,12GB内存。分别使用传统的体素网格降采样方法和新的体素网格降采样方法对三维点云进行降采样，从降采样的直观效果和数据分析对两种方法进行了比较和讨论。实验用的点云，如图2 所示。从两个场景扫描获得两个点云,两个场景中的物体主要是机加工零件。图2(a)中的零件包含有凸起和凹陷的平面、阶梯圆柱面、球冠面，还包含有凸起的文字和复杂曲面,其对应的点云,如图2(c)所示。图2(b)中有3个散乱放置的L形零件,其对应的点云,如图2(d)所示。图2(c)图2(d)在展示各个点云的同时，也展示出了各个点云的轴向包围盒。表1展示了两个实验点云各自包含的点数和尺寸，其中尺寸是指各个点云轴向包围盒在x,y,z轴三个方向的边长。结合图2(c)图2(d)和表1，可知两个点云轴向包围盒的边长比例皆不相同，其中点云二的包围盒在z轴方向的边长与在x,y轴方向的边长差异非常悬殊。3.2实验结果和分析使用新方法，等分距离取10 mm和15mm时，各个点云轴向包围盒在,y，z 轴方向等分的份数和降采样后的点数，如表2 所示。结合表1、表2 可知，由于各个点云轴向包围盒在x，y，z 轴方向的边长各不相等，因而用新方法对点云进行体素划分时，x,y,z方向的等分数也各不相同。(a)场景一(c)场景一对应的点云Fig.2Experimental Point CloudsAug.20232Tab.1 Experimental Point Clouds and the SideLength of the Axis-Aligned Bounding Box(mm)idx点云点数量点云一73598点云二67231表2 新方法降采样的结果（mm）Tab.2 Downsampling Results ofthe Proposed Method(mm)等分X方向Y方向乙方向点云点数距离等分数等分数等分数的点数10.038点云一73598点云二67231为了便于比较新方法和传统体素网格方法的降采样效果，使用传统体素网格降采样方法，选取不同的等分数对点云进行降采样，记录各个点云不同等分数对应的降采样后的点数，如表3所示。在表3中,无论等分数为多少,降采样后的点数量与表2 中新方法降采样后的点数量都不相同。因而，我们从表3中选取降采样后的点数量与表2 中降采样后的点数量接近的值,并在表3中加粗显示。同时,将表3中的这些数据摘抄出来,结合表2,并加上每种降采样方法所用的计算时间，如表4 所示。表3不同等分数对应的降采样后的点数Tab.3 The Number of Points After DownsamplingCorresponding to Different Subdivision点云一点云二等分数降采样后的点数2159022641236962473825806268572792928990291043301128O316323334(b)场景二图4 展示了用体素网格和新方法降采样后的点在原始点云中的实际效果，其中降采样后的点用粗点显示，原始点云用细点显示。从图4 中可见，对点云一，在降采样点数量接近的情况下，直观上看，体素网格方法和新方法降采样效果的差异不明显；对点云二来说，在降采样点数量接近的情况下，体素网格方法和新方法降采样效果有非常明显的差异。差异主要体现在三个L形的零件在z轴方向的采样点分布，体素网格方法得到的采(d)场景二对应的点云样点在z轴方向分布非常密集，而新方法得到的采样点在z轴方图2 实验点云向分布非常均匀。轴向包围盒边长XY375.633402.352365.432287.7384015.02510.03715.024等分数降采样后的点数164321748618545196132067121746227802388524936251012119026125927133228139329最长边与最短Z边之比168.9752.464.7895.6降采样后171245271129619410781187124713395961055464No.8Aug.2023计算降采样后的点云各个点到其最近点的距离，并绘制相应的频数分布图，如图5所示。图5中水平轴表示各点间的最近距离值,纵轴表示距离值在某个区间内的点的数量。为了便于比较分析，当降采样点云的点数接近时,对应的水平轴和纵轴的最大刻度和间隔皆取为相同。在图5(a)、图5(b)图5(e)图5(f)中，也即点云一，当降采样点云的点数接近时，靠近水平刻度0 的几个频数分布无明显差异，且频数都比较小，这表明体素网格方法和新方法得到的采样点都没有出现过于密集的问题，这与图4 中的实际效果是一致的。在图5(c）、图5(d)、图5(g）、图5(h)中,也即点云二，靠近水平刻度0 的几个频数分布有显著差异，体素网格方法得到的靠近水平0 刻度的几个频数分布直方图较高，而新方法对应的那几个频数直方图则非常低，这表明体素网格方法得到的采样点有相当一部分靠得非常近，而新方法则没有出现这个问题，这与图4 中的实际效果也是一致的。根据计算得到的降采样后的点云中各个点到其最近点的距离，接着计算出这些距离的平均值和标准差，并找出这些距离中的最小值、最大值，这些数值，如表5所示。从表5可知，对点云一,体素网格和新方法得到的降采样后的点云的距离平均值和标准差都非常接近，这说明两种方法得到的点云总体没有明显差异；对点云二，距离平均值则有显著差异，新方法得到的点云的距离平均值明显大于对应的体素网格法，而新方法的距离标准差皆小于对应的体素网格法，这说明新方法得到的点云在原始点云中的分布更均匀。从上面的实验数据和分析可见，当点云轴向包围盒在x，y，z轴方向的最长边与最短边的比值较小，比如点云一最长边与最短边比值为2.4,体素网格法和新方法降采样的效果差别较小；当点机械设计与制造0.350.300.25￥0.2 00.150.10Fig.3 Total Voxels and Computation Time体素网格法(a)等分数n=32(b)等分数n=21（c)等分数n=26（d)等分数n=17(e)等分距离10.0 mm图4 体素网格法和新方法降采样后的实际效果对比Fig.4 Comparison of the Actual Effects of theVoxel Grid and Proposed Methods点云一体素网格法183一一体系网格法一这里方法12(b)计算时间图3体素总数和计算时间(f)等分距(g)等分距离15.0 mm离10.0 mm点云二T1345点云二(h）等分距离15.0 mm6云轴向包围盒在x,y，z 轴方向的最长边与最短边的比值较大，比如点云二最长边与最短边比值为5.6，体素网格法和新方法降采样的效果差别非常明显，此时新方法优于体素网格法。将表4 中的体素总数和计算时间数据分别绘制出来，如图3所示。从图3明显可见，降采样的计算时间折线走势与体素总数曲线走势一致，可见降采样的计算时间与体素总数大致成线性关系，也即体素越多，降采样所需要的计算时间也越长。从图3我们还可看到，对同一个点云，当降采样后的点数相当时，新方法得到体素数量通常比体素网格法要少，因而新方法通常比体素网格法的计算速度更快。35000-30000-25000-数2 0 0 0 0体150 0 010000-50000-(a)等分数n=32新方法(e)等分距离10.0 mm表4 体素网格法和新方法降采样的结果对比，长度单位mm，时间单位sTab.4 Comparison of the Results of the Voxe一一体系网格法Grid and Proposed Methods,Length一一这里方法Unit in mm and Time Unit in Seconds体素网格法降采会数等等分总数的点时间距离向等向等向等体素样后计算总数的点时间数分数分数芬数数3270.31点3273568云982161175点266727612(a)体素总数(b)等分数n=21（c)等分数n=26（d)等分数n=17(f)等分距(h)等分距离15.0 mm离10.0 mm图5频数分布图Fig.5FrequencyDistribution新方法X方方方数2580.29125910.038401794340920.1759015.025271174255967479070.220.17107810.0372966438105527002034T(g)等分距离15.0 mm降采12450320.1656云311713494863680.1415.02419418244646890.12No.8184机械设计与制造表5体素网格法和新方法得到的点云中2 Dovrat O,Lang I,Avidan S.Learning to sample;proceedings of the Pro-各个点之间的最近距离，长度单位mmceedings of the IEEE Conference on Computer Vision and Pattern Rec-Tab.5 Nearest Distances Between Downsamplingognition,F,2019C.Points Obtained by the Voxel Grid and3邹鹏，李蓓智，龚菊贤，等.改进的RANSAC点云分割算法及其应用Proposed Methods,Length Unit in mmJ.机械设计与制造，2 0 2 0(11)：12 1-12 4.(Zou Peng,Li Bei-zhi,Gong Ju-xian,et al.Improved RANSAC point体素网格法新方法点云点数每边等分最小最大平均标准等分最小最大平均标准值值值差距离值值值数差0.888.616.051.243210.0点云7 3527661752575981.1017.28.872.102115.0106222693120.6214.16.4112.552610.0点云6 7 22599623964162二3117531867 7357364结论当点云轴向包围盒在x，y，z 轴三个方向的边长相差非常悬殊的时候，传统的体素网格降采样方法就存在着采样点分布不均匀的问题。这是因为传统的体素网格法不考虑轴向包围盒的边长差异，直接将点云的轴向包围盒沿各个坐标轴方向皆分成n等份，最终导致包围盒最短边所在方向的采样点分布比最长边所在方向的采样点分布要密集得多,也即采样点在空间分布不均匀。针对这一问题，提出了一种新的体素网格降采样方法。该方法首先对点云建立轴向包围盒,然后以某一个等分距离对包围盒沿x,y,z轴三个方向的边进行等分，使得每一个体素近似为一个正方体，然后计算每一个体素内所有点的重心,并将其作为该体素的采样值。从实验结果可见，当降采样后的点数大致相同时，若点云包围盒在x,y,z轴三个方向的边长相差不大，新方法和传统体素网格法获取的点云分布均匀程度相当，但若点云包围盒在x,y,z轴三个方向的边长相差非常悬殊，新方法比传统体素网格法获取的点云分布更均匀。而且,新方法的计算效率高于传统的体素网格法。参考文献1 Vidal J,Lin C-Y,Llado X,et al.A method for 6D pose estimation of free-form rigid objects using point pair features on range data JJ.Sensors,2018,18(8):2678.Aug.2023cloud segmentation algorithm and its application JJ.Machinery Design&Manufacture,2020(11):121-124.)4 Zhou Y,Tuzel O.Voxelnet:End-to-end learning for point cloud based3d object detection;proceedings of the Proceedings of the IEEE Confer-1.1110.06.061.470954140551842.5815.1 9.082.19101122548750.6411.87.92 2.123671737433431.6116.79.633.8215.041ence on Computer Vision and Pattern Recognition,F,2018c.5 Sayed A,Ibrahim A.Recent developments in systematic sampling:a re-viewJJ.Journal of Statistical Theory and Practice,2018,12(2):290-310.6 Sanders P,Lamm S,Hubschle-Schneider L,et al.Efficient parallel ran-dom sampling vectorized,cache-efficient,and onlineJJ.ACM Transac-3.4415.712.13.0025125792tions on Mathematical Software(TOMS),2018,44(3):1-14.7 Eldar Y,Lindenbaum M,Porat M,et al.The farthest point strategy for pro-gressive image sampling JJ.IEEE Transactions on Image Processing,1997,6(9):1305-1315.8】傅思勇，吴禄慎，陈华伟.空间栅格动态划分的点云精简方法J.光学学报,2 0 17,37(11):2 53-2 6 1.(Fu Si-yong,Wu Lu-shen,Chen Wei-hua.Point cloud simplificationmethod based on space grid dynamic partitioningJJ.Acta Optica Sinica,2017,37(11):253-261.)9 Han H,Han X,Sun F,et al.Point cloud simplification with preservededge based on normal vector J.Optik-International Journal for Lightand Electron Optics,2015,126(19):2157-2162.1o Nezhadarya E,Taghavi E,Razani R,et al.Adaptive Hierarchical Down-Sampling for Point Cloud Classification;proceedings of the Proceed-ings of the IEEE/CVF Conference on Computer Vision and Pattern Rec-ognition,F,2020C.11李琪琪，花向红，赵不钒，等，一种基于曲率泊松碟采样的散乱点云精简方法J.测绘通报，2 0 2 0(S1)：17 6-18 0.(Li Qi-qi,Hua Xiang-hong,Zhao Bu-fan,et al.A method for scatteredpoint cloud simplification based on curvature poisson dish samplingJ.Bulletin of Surveying and Mapping,2020(S1):176-180.)12李丽娟，李青政，刘涛.飞机插配零部件数字化装配碰撞检测研究J.机械设计与制造，2 0 2 0(2)：14 5-14 8.(Li Li-juan,Li Qing-zheng,Liu Tao.Research on digital assembly col-lision detection for insertingand fitting parts of aircraft JJ.MachineryDesign&Manufacture,2020(2):145-148.)(上接第17 9 页）(Sun Hao-yan.Research on pointer Instrument reading recognition sys-tem based on machine visionD.Changcun:Jilin University,2015.10 WANG Y,WU Z,DUAN X.Design of gear defect detection systembased on machine visionJ.IOP Conference Series:Earth and Environ-mental Science,2018,108(2):022025.11彭锐涛,降皓鉴,徐莹,等.刀具磨损的机器视觉监测研究J.机械科学与技术,2 0 19,38(8)：12 57-12 6 3.(Peng Rui-tao,Xiang Hao-jian,Xu Ying,et al.Research on machinevision monitoring of tool wearJ.Mechanical Science and Technology,2019,38(8):1257-1263.)12王文成.基于机器视觉的齿轮参数测量系统设计J.机械传动，2011,35(2):41-43.(Wang Wen-cheng.Design of gear parameter measurement systembasedon machine vision JJ.Mechanical Transmission,2011,35(2):41-43.)13张震，程伟伟，吴磊，等.基于不变矩和SVM的圆形交通标志识别方法研究J.电子测量与仪器学报，2 0 17,31(5)：7 7 3-7 7 9.(Zhang Zhen,Cheng Wei-wei,Wu Lei,et al.Research on recognitionmethod of circular traffic signs based on invariant moment and SVMJ.Journal of Electronic Measurement and Instrumentation,2017,31(5):773-779.)14 Trujllo-Pino A,Kr Issian K,Aleman-Flores M,et al.Accurate sub-pixel edge location based on partial area effect J.Image and VisionComputing,2013,31(1):72-90.15高丽芹.渐开线斜齿圆柱齿轮角的测算J.机械研究与应用，2013,26(2):159-161.(Gao Li-qin.Calculation of angle of involute helical cylindrical gearJJ.Mechanical Research and Application,2013,26(2):159-161.)