基于网格单元的点云降维处理算法.pdf

投稿网址:2023 年 第23 卷 第26 期2023,23(26):11182-06科 学 技 术 与 工 程Science Technology and EngineeringISSN 16711815CN 114688/T收稿日期:2022-11-16修订日期:2023-04-18基金项目:国家电网有限公司总部科技项目(kj2021-020)第一作者:段志国(1978),男,汉族,河北保定人,硕士,正高级工程师。研究方向:城市电网智能运检。E-mail:。引用格式:段志国,吴灏,侯阳,等.基于网格单元的点云降维处理算法J.科学技术与工程,2023,23(26):11182-11187.Duan Zhiguo,Wu Hao,Hou Yang,et al.Dimension reduction algorithm of point cloud based on grid cellJ.Science Technology and Engi-neering,2023,23(26):11182-11187.矿冶工程基于网格单元的点云降维处理算法段志国1,吴灏1,侯阳2,王少博1,辛庆山1,张明路2(1.国网石家庄供电公司,石家庄 050000;2.河北工业大学机械工程学院,天津 300401)摘 要 针对激光雷达采集数据时,由于会受到外界的干扰因素、扫描精度等负面影响,会使采集到的点云数据空间密度相差较大、存在着很大的噪声和孔洞,使得分析结果不能直接描绘实际物体的模型的问题,本文研究设计了一种基于二进制占网格的点云数据处理算法。首先将分割完成后的点云采用二进制网格的方式聚类进行降维处理,再将点云映射到网格单元中实现不同物体点云的快速聚集。最后,基于寻找出的点云主方向旋转点云从而.建立紧致随动的障碍物包围盒。通过实验验证,该方法能够在保证聚类精度的同时提高运算速度,其建立包围盒能够准确地反映障碍物的尺寸,具有良好的实时性与随动性,对移动机械臂自主避障提供了可靠的信息。关键词 点云聚类;包围盒;深度视觉;二进制占用网格中图法分类号 TG445;文献标志码 ADimension Reduction Algorithm of Point Cloud Based on Grid CellDUAN Zhi-guo1,WU Hao1,HOU Yang2,WANG Shao-bo1,XIN Qing-shan1,ZHANG Ming-lu2(1.State Grid Shijiazhuang Power Supply Company,Shijiazhuang 050000,China;2.School of Mechanical Engineering,Hebei University of Technology,Tianjin 300401,China)Abstract In view of the problem that when lidar collects data,due to the negative impact of external interference factors and scan-ning accuracy,the spatial density of the collected point cloud data will vary greatly,and there will be a lot of noise and holes,so thatthe analysis results can not directly describe the model of the actual object,a point cloud data processing algorithm was designed basedon binary grid occupation.First,the point cloud after segmentation was clustered by binary grid to reduce the dimension,and then thepoint cloud was mapped to the grid cell to achieve rapid aggregation of different object point clouds.Finally,the point cloud was rotatedbased on the main direction found Establish a closely followed obstacle bounding box.The experimental results show that this methodcan improve the operation speed while ensuring the clustering accuracy.Its bounding box can accurately reflect the size of obstacles,and has good real-time and follow-up performance.It provides reliable information for the mobile robot to avoid obstacles autonomously.Keywords point cloud clustering;bounding box;depth vision;binary occupancy grid 点云是实际物体三维信息的统计无序数集,包含了物体的三维坐标值,颜色值和灰度值1。近年来,学者们针对点云的预处理和障碍物包围盒的建立进行了大量的研究。密度聚类是一种无监督聚类算法,能在“噪声”数据中识别出任意形状的聚类2-7但由于密度聚类在去除点云噪声时需要对点云进行逐个遍历,利用欧式距离进行邻域点判断收敛时间较长,不适合海量点云的去噪处理。文献8用 K-means 聚类算法,根据点到聚类中心的欧式距离和临近点曲率变化判断每个类中的点是否为噪声点;文献9提出基于改进随机抽样一致的点云分割算法实现点云分割的同时有效去除噪声点;文献10通过枚举绕轴旋转的角度,对比旋转后的包围盒体积,最终获得体积最小的包围盒。虽然已有算法已经在一定程度上提高了点云聚类和包围盒建立的精度,但是仍然存在一些问题。例如,枚举算法的复杂度较高,一些算法对初始值较敏感,依赖法向量、曲率等信息,因此点云处理效果难以把控。针对上述问题,在点云分割完成的基础上,现提出一种高效的点云聚类与包围盒建立方法。该方法基于二进制占用网格对点云进行降维处理,将投稿网址:点云映射到网格单元中实现不同物体点云的快速聚集。并寻找点云轮廓生成的二进制占用网格主方向,基于主方向旋转点云从而建立更加紧致随动的包围盒。1 基于二进制占用网格的点云聚类点云分割完成后,需要将不同障碍物的散落点集集合成点云簇,将障碍物点云图形转化为若干个对象。采用二进制网格的方式聚类,通过对点云进行降维处理,再将点云映射到网格单元中,查找并分别储存已占用网格的连通域,从而实现不同物体点云的快速聚集。1.1 网格生成与点云储存对点云空间创建二维极坐标网格,极坐标网格划分包含扇形区域和子区域两个部分,首先将极坐标区域划分为扇形区域,取扇形圆心角 pl,将极坐标平面分割为 m 个扇形,公式为m=2pl(1)再继续对每个扇形区域划分子区域,取最大距离为rmax,步长距离为 rpl,将每一个扇形沿扇形半径均等划分为 n 份,公式为n=rmaxrpl(2)这样就对点云空间创建了一个 m n 的极坐标网格平面。网格划分完毕后,将点云储存到网格中,由于点云具有三维信息,将点云信息进行降维存储,即直接将点的坐标(x,y,z)简化为(x,y)。原因在于一方面点云聚类并不关心点云簇在 z 方向的排列与顺序,若两个点的 x、y 值一致而 z 不同,则视为两点在 z 方向叠加,它们属于同一障碍物的点云;另一方面能够加快聚类速度,满足聚类算法在动态变化的环境中的实时性要求。确定点 pi=(xi,yi,-)所属的扇形区域 sa,公式为s(pi)=atan2(yi,xi)pl(3)smina s(pi)smaxa(4)式中:atan2 为已将象限纳入考量的反正切函数,表示原点至点 pi的方位角;smina为扇形区域的下界;smaxa为扇形区域的上界。确定扇形区域后,再计算点 b(pi)所述的子区域 bb,公式为b(pi)=x2i+y2i(5)bminb b(pi)bmaxb(6)式中:bminb为子区域的下界;bmaxb为子区域的上界。将各点映射到网格中后,对网格进行赋值。若网格中未包含点,则记网格的值为 0,其像素颜色为黑色;若网格中包含点,则记网格的值为 1,其像素颜色为白色。从而生成二进制占用网格。这样就将三维点云处理转化为二维图像处理,并且二进制占用网格组成简单,占用空间小,处理难度大大降低。1.2 二进制占用网格膨胀处理对二进制图像进行图像膨胀处理,图像膨胀是将图像在保持原有形状不变的情况下,对图像的白色部分进行扩张。其主要目的是将白色区域内部孤立的黑色的像素点去除。定义一个大小为 3 3的正方形的核,其原点位于中心位置。设输入二进制图像像素集合为 A,核像素集合为 B,原点为中心点,则图像膨胀定义为A B=x|(B)x A (7)式(7)中:为空集。核的原点从二进制图像的原点出发,使核在图像上进行逐个像素点的移动,扫描其 3 3 范围内的图像像素点。若核中扫描的所有像素点都为 0,则锚点处的像素点记为 0,否则记为 1。遍历每一个像素点即可得到膨胀图像,与原图像相比它具有更大且更连续的白色区域。1.3 二进制占用网格连通区域分析连通区域分析是一种计算机图像分析与处理的常见方法,其目的是将前景目标物体从背景中提取出来以便后续处理的使用。连通区域一般是指图像中具有相同像素且位置相邻的像素点组成的图形区域,它是一个像素集合。连通区域分析是指将图像中的各个连通区域找出并标记。在对二值图像进行膨胀后,得到存放障碍物点云的白色像素块,下一步是识别不同障碍物的像素块并分类储存,使用连通区域分析算法中的种子填充法对二值图像进行进一步的处理。其步骤如下。(1)定义一个四邻域的像素相邻关系,它表示从目标像素点出发,对其上、下、左、右 4 个相邻的像素点进行检测。(2)从二值图像原点开始,逐个像素点扫描图像,直到当前扫描像素点 p1为白色像素点。对该白色像素点的位置赋予一个 label,label 是从 1 开始逐渐增大的自然数,被用来对白色像素点进行标记。(3)将 p1邻域内的点 p2、p3、p4、p5按先后顺序放入一个集合 M 中,如式(8)所示,从左到右分别代表放入的先后顺序,最后放入的点为 p5。M=p2,p3,p4,p5(8)(4)将 p5取出进行检测,若 p5为白色像素点,则对 p5赋予与 p1相同的 label,并将 p5中所有邻域内381112023,23(26)段志国,等:基于网格单元的点云降维处理算法投稿网址:的点按先后顺序加入 M;若 p5为黑色像素点,则舍弃 p5并取出 p4进行检测。(5)重复步骤(4),直到取出 M 中所有的点。此时便得到了 label=1 的一个连通区域。(6)重复步骤(2),当扫描结束时,就可以得到图像中的所有连通区域。查找每一 label 标记的点集分别标记上不同的颜色,得到不同障碍物的点云簇,点云聚类流程示意如图 1 所示。图 1 点云聚类流程示意图Fig.1 Schematic diagram of point cloud clustering process2 基于点云主方向旋转的包围盒建立2.1 基于二进制占用网格点云主方向识别点云主方向是指点云数据变化最大的朝向,它决定了包围盒的方向与大小,判定点云主方向关键在于如何得到点云边框在 x-y 平面内的最大分布。霍夫直线检测是一种经典的直线特征提取技术,它广泛应用于具有轮廓特征的二进制占用网格内,即从图像中获取直线。霍夫直线检测是通过累加器在特定类型的形状内找到直线,直线候选对象由累加数的局部极大值确定。霍夫直线检测不仅能检测出图像的直线轮廓,还能定位到该直线的位置和角度等。其检测方程为=xcos+ysin(9)式(9)中:与 为极坐标下点的极径与极角,霍夫直线检测的优点在于:给定 x-y 平面中的单个点,那么通过该点的所有直线的集合对应于-平面中的一条曲线,且点与曲线的对应关系是唯一的。两个或多个点形成的一条直线将产生在该线的(,)处交叉的一条或多条曲线。因此,检测共线点的问题可以转化为在-平面内找到曲线交点个数的问题。点云主方向的算法流程如下。(1)提取点云边框,因为点云是一种类似于空壳的图像,只反映被拍摄物体的表面信息,且对于一般障碍物而言,其横向尺寸变化不大。故去除 z方向较大的点云并投影到 x-y 平面后,可得到点云的边框图像。其判定如式(10)所示,保留满足式(10)的所有点 pi。z(pi)-zmin 0.7(zmax-zmin)(10)式(10)中:z(pi)为点的 z 方向大小。(2)在 x-y 平面内对点云边框进行栅格化处理,记录点云边框的所有点中 x、y 方向的最大值和最小值(xmaxf、xminf、ymaxf、yminf)计算出该栅格图在 x、y方向的范围为rx=xmaxf-xminf(11)ry=ymaxf-yminf(12)取边长为 g 的正方形建立栅格,则该栅格图的大小为 rx ry,将点云投影到栅格地图中将包含点的栅格值记为 1,未包含点的栅格值记为 0,生成点云边框的二进制占用网格。(3)读取点云边框二进制占用网格,扫描其像素值为 1 的像素点,并以栅格边长作为霍夫直线检测的变换步长,其总检测长度为点云边框的总周长,则检测次数 nt为nt=2(rx+ry)/g(13)(4)对霍夫空间设置累加器 Num(,)并初始化Num(,)=0。对于二进制占用网格中每一个像素点(x,y),在参数空间中找出所有满足 =xcos+ysin 的(,),然后令 Num(,)=Num(,)+1。(5)统计所有 Num(,)的大小,取出其最大值,该情况所对应的直线即为点云主方向对应直线。计算点云主方向对应直线与基坐标系的角度,则 为点云主方向。计算点云主方向流程示意如图 2 所示。2.2 包围盒顶点确定在得到了点云主方向以后,可以根据点云主方向建立包围盒。这种包围盒的特点是与障碍物之间贴合紧密,间隙较小,能够更准确地描述障碍物的尺寸与朝向。该过程可分为以下步骤进行。(1)计算障碍物点云集中心位置坐标(xc,yc),如式(14)所示,并计算出以中心点为起点指向点云集各点的向量 pi如式(15)所示,其中 xmax、xmin、ymax、ymin代表障碍物点云集在 x、y、z 方向上的最大值和最小值。48111科 学 技 术 与 工 程Science Technology and Engineering2023,23(26)投稿网址:图 2 计算点云主方向流程示意图Fig.2 Schematic diagram of main direction flow ofcalculation point cloud(xc,yc)=xmax+xmin2,ymax+ymin2()(14)pi=(xi-xc,yi-yc)(15)(2)将向量 pi绕中心点处 z 轴旋转-角得到向量 pi,使点云主方向对其基坐标 x 轴,即pi=cos(-)-sin(-)sin(-)cos(-)pi(16)(3)遍历旋转后的点云集,得到旋转后点云在x、y、z 方向的最大值和最小值 xmax、xmin、ymax、ymin、zmax、zmin得到包围盒的 8 个顶点坐标 boxi,即box1=(xmin,ymin,zmin)box2=(xmax,ymin,zmin)box3=(xmax,ymax,zmin)box4=(xmin,ymax,zmin)box5=(xmin,ymin,zmax)box6=(xmax,ymin,zmax)box7=(xmax,ymax,zmax)box8=(xmin,ymax,zmax)(17)(4)将得到的包围盒顶点坐标 boxi通过旋转变换回原点集,得到原点集包围盒的 8 个顶点坐标boxi,即boxi=cos-sinsincosboxi+xcyc(18)点云建立包围盒流程示意如图 3 所示。图 3 点云建立包围盒流程示意图Fig.3 Schematic diagram of point cloudbuilding bounding box process3 实验结果及分析实验采用 RS-LiDAR-M1 激光雷达进行环境采集并获取点云数据视频,该场景中包含两个小型路障,距激光雷达较近的记为小型路障 1,较远的记为小型路障 2。一辆大型货车和行人等 4 个障碍物,其中行人向着远离激光雷达的方向移动。其实验场景如图 4 所示,输出点云数据如图 5 所示。将地面点云去除,保留障碍物点云。取参数pl=0.65、rmax=200、rpl=0.2。任取点云视频中的多帧进行检验,经过二进制网格聚类后点云如图 6所示,从图 6 中可以看出,该方法能够有效分辨场景中障碍物的个数,并且不随帧数的变化而出现漏判或多判的情况。对视频中的各类障碍物进行点数统计并计算最大误差。由于行人随着时间的变换距离激光雷图 4 点云采集实验场景Fig.4 Point cloud collection experiment scenarios581112023,23(26)段志国,等:基于网格单元的点云降维处理算法投稿网址:达越来越远,因此行人点云的点数会随着时间的变化较大,故只对静态障碍物进行统计,从而检验聚类算法的准确性。统计结果如表 1 所示。图 5 输出点云数据Fig.5 Output point cloud data图 6 点云聚类结果Fig.6 Point cloud clustering results表 1 各障碍物聚类点数统计Table 1 Statistics of clustering points of each obstacle帧数小型障碍物 1点数统计小型路障 2点数统计大型货车点数统计256806325 3481856696455 3213776896515 4054596776485 3776216846555 355最大误差/%2.993.641.58由表 1 可以看出,随着点云帧数的变化,各静态障碍物的点数变化最大误差均在 5%以内,说明基于二进制占用网格的聚类算法能准确地将不同障碍物所属的点集进行聚类。此外大型货车聚类最大误差为 1.58%,而小型障碍物的聚类误差为2.99%和 3.64%,说明该算法对于点数越多的障碍物,其聚类效果越好。基于二进制占用网格的聚类算法与传统欧式聚类算法对比如表 2 所示,两种算法均能检测出场景中的 4 个障碍物,但基于二进制占用网格的聚类方法运算更迅速,所需时间更短。原因在于一方面对点云采用降低维度的方式进行处理,即由三维点云处理转换为二维图像处理,且二进制占用网格是一种非常简单的二维图像;另一方面该算法无需迭代,只需要对二进制占用网格进行扫描,大大降低了时间复杂度,对于场景中运动状态变换较快的物体具有良好的实时性。两种算法对比如表 2 所示。对聚类后的障碍物建立包围盒如图 7 所示,其中数字代表障碍物的标号。从图 7 中可以看出,随着帧数的改变,包围盒能始终跟随并包络障碍物点云,且标号保持一致,具有良好的随动性。对于静态障碍物来说,由于主方向不发生改变,其包围盒的朝向与大小未发生改变。而对于行人这类动态障碍物来说,由于在行走过程中存在位置和速度改变,故点云主方向也随之变动,图 7 中显示该包围盒建立方法能够实时测量点云主方向的变换,进而改变包围盒的朝向和大小,使得包围盒始终紧密贴合行人点云,证明了该方法的有效性。基于点云主方向旋转的包围盒建立算法与AABB 包围盒算法对比如表 3 所示,AABB 包围盒是直接以障碍物点集在 x、y、z 方向上的最大和最小值为顶点建立包围盒。从表 3 可以看出,两类算法的包围效果与包围盒高相差不大,但基于点云主方向旋转的包围盒长、宽均小于 AABB 包围盒算法,证明该方法所建立包围盒更加紧致,能够更精确地反映障碍物的大致尺寸,证明了该方法的优越性。表 2 二进制占用网格聚类与欧式聚类算法性能比较Table 2 Performance comparison between binaryoccupancy grid clustering and Europeanclustering algorithm项目二进制占用网格聚类欧式聚类平均每帧计算时间/ms29387迭代次数51障碍物类数4468111科 学 技 术 与 工 程Science Technology and Engineering2023,23(26)投稿网址:图 7 障碍物包围盒建立Fig.7 Establishment of obstacle bounding box表 3 点云主方向旋转包围盒与 AABB 包围盒对比Table 3 Comparison between point cloud main directionrotation bounding box and AABB bounding box编号点云主方向旋转包围盒包围百分比/%长/m宽/m高/mAABB 包围盒包围百分比/%长/m宽/m高/m098.570.480.450.7697.830.570.530.77199.310.610.561.7598.350.770.691.75298.750.510.460.7498.920.640.590.73397.561.590.543.1098.131.750.663.124 结论提出了基于二进制占用网格的点云聚类算法,首先对点云进行降维处理,将三维点云简化为二维像素图像处理,并且对点云轮廓生成二进制占用网格从而寻找点云主方向,基于主方向旋转点云从而建立包围盒。实验结果表明,该方法能够在保证聚类精度的同时大大提高运算速度,其建立包围盒能够更加准确的反应障碍物的尺寸,具有良好的实时性与随动性,对之后的机械臂自主避障提供了可靠的信息。参考文献1 杜超.基于激光雷达的点云数据处理研究D.西安:西安工业大学,2022.Du Chao.Research on point cloud data proce-ssing based on lidarD.Xian:Xian University of Technology,2022.2 Cao H Z,Ma Y X,Zhan R H,et al.Adaptive surface fitting con-volution for 3D point cloud analysisC/Proceedings of 5th Inter-national Conference on Automation,Control and Robotics Engineer-ing(CACRE 2020).Xian:CACRE,2020:757-763.3 何广焕,唐诗华,王文贯,等.一种基于 CSF-WOA-LSSVM 的匹配点云土石方量计算方法J.科学技术与工程,2022,22(30):13194-13201.He Guanghuan,Tang Shihua,Wang Wenguan,et al.A calculationmethod of matching point cloud earthwork volume based on CSF-WOA-LSSVM J Science Technology and Engineering,2022,22(30):13194-13201.4 王春香,孟宏,张勇.散乱点云的孔洞识别和边界提取算法研究J.机械设计与制造,2019(3):74-76.Wang Chunxiang,Meng Hong,Zhang Yong.Research on holerecognition and boundary extraction algorithm of scattered pointcloud J.Mechanical Design and Manufacturing,2019(3):74-765 吕富强,唐诗华,何广焕,等.基于密度噪声应用空间聚类算法的机载激光雷达建筑物点云提取与单体化J.科学技术与工程,2022,22(9):3446-3452.L Fuqiang,Tang Shihua,He Guanghuan,et al.Airborne lidarbuilding point cloud extraction and monomer based on density noiseapplication spatial clustering algorithm J.Science and Technolo-gy and Engineering,2022,22(9):3446-3452.6 侯思祖,韩思雨,韩利钊,等.适合多密度的 DBSCAN 改进算法J.传感器与微系统,2018,37(8):137-139Hou Sizu,Han Siyu,Han Lizhao,et al.DBSCAN improved algo-rithm for multi density J.Sensors and Microsystems,2018,37(8):137-139.7 He S W,Liu B L.Review of bounding box algorithm based on 3Dpoint cloudJ.International Journal of Advanced Network,Moni-toring and Controls,2021.DOI:10.21307/IJANMC-2021-003.8 苏本跃,马金宇,彭玉升,等.基于 K-means 聚类的 RGBD 点云去噪和精简算法 J.系统仿真学报,2016,28(10):2329-2334.Su Benyue,Ma Jinyu,Peng Yusheng,et al.RGBD point cloud de-noising and simplification algorithm based on K-means clusteringJ.Journal of System Simulation,2016,28(10):2329-23349 赵夫群,马玉,戴翀.基于改进随机抽样一致的点云分割算法J.科学技术与工程,2021,21(22):9455-9460.Zhao Fuqun,Ma Yu,Dai Chong.Point cloud segmentation algo-rithm based on improved random sampling consistency J.ScienceTechnology and Engineering,2021,21(22):9455-9460.10 胡志刚,秦启飞.基于凸包的最小体积有向包围盒生成算法J.湖南大学学报(自然科学版),2019,46(2):105-111.Hu Zhigang,Qin Qifei.Algorithm for generating minimum volumeoriented bounding box based on convex hull J.Journal of HunanUniversity(Natural Science Edition),2019,46(2):105-111.781112023,23(26)段志国,等:基于网格单元的点云降维处理算法