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

段志国, 吴灏, 侯阳, 王少博, 辛庆山, 张明路

(1.国网石家庄供电公司, 石家庄 050000; 2.河北工业大学机械工程学院, 天津 300401)

点云是实际物体三维信息的统计无序数集,包含了物体的三维坐标值,颜色值和灰度值[1]。近年来,学者们针对点云的预处理和障碍物包围盒的建立进行了大量的研究。密度聚类是一种无监督聚类算法,能在“噪声”数据中识别出任意形状的聚类[2-7]但由于密度聚类在去除点云噪声时需要对点云进行逐个遍历,利用欧式距离进行邻域点判断收敛时间较长,不适合海量点云的去噪处理。文献[8]用K-means聚类算法,根据点到聚类中心的欧式距离和临近点曲率变化判断每个类中的点是否为噪声点;文献[9]提出基于改进随机抽样一致的点云分割算法实现点云分割的同时有效去除噪声点;文献[10]通过枚举绕轴旋转的角度,对比旋转后的包围盒体积,最终获得体积最小的包围盒。虽然已有算法已经在一定程度上提高了点云聚类和包围盒建立的精度,但是仍然存在一些问题。例如,枚举算法的复杂度较高,一些算法对初始值较敏感,依赖法向量、曲率等信息,因此点云处理效果难以把控。

针对上述问题,在点云分割完成的基础上,现提出一种高效的点云聚类与包围盒建立方法。该方法基于二进制占用网格对点云进行降维处理,将点云映射到网格单元中实现不同物体点云的快速聚集。并寻找点云轮廓生成的二进制占用网格主方向,基于主方向旋转点云从而建立更加紧致随动的包围盒。

1 基于二进制占用网格的点云聚类

点云分割完成后,需要将不同障碍物的散落点集集合成点云簇,将障碍物点云图形转化为若干个对象。采用二进制网格的方式聚类,通过对点云进行降维处理,再将点云映射到网格单元中,查找并分别储存已占用网格的连通域,从而实现不同物体点云的快速聚集。

1.1 网格生成与点云储存

对点云空间创建二维极坐标网格,极坐标网格划分包含扇形区域和子区域两个部分,首先将极坐标区域划分为扇形区域,取扇形圆心角αpl,将极坐标平面分割为m个扇形,公式为

(1)

再继续对每个扇形区域划分子区域,取最大距离为rmax,步长距离为rpl,将每一个扇形沿扇形半径均等划分为n份,公式为

(2)

这样就对点云空间创建了一个m×n的极坐标网格平面。

网格划分完毕后,将点云储存到网格中,由于点云具有三维信息,将点云信息进行降维存储,即直接将点的坐标(x,y,z)简化为(x,y)。原因在于一方面点云聚类并不关心点云簇在z方向的排列与顺序,若两个点的x、y值一致而z不同,则视为两点在z方向叠加,它们属于同一障碍物的点云;另一方面能够加快聚类速度,满足聚类算法在动态变化的环境中的实时性要求。确定点pi=(xi,yi,-)所属的扇形区域sa,公式为

(3)

(4)

确定扇形区域后,再计算点b(pi)所述的子区域bb,公式为

(5)

(6)

将各点映射到网格中后,对网格进行赋值。若网格中未包含点,则记网格的值为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中所有邻域内的点按先后顺序加入M;若p5为黑色像素点,则舍弃p5并取出p4进行检测。

(5)重复步骤(4),直到取出M中所有的点。此时便得到了label=1的一个连通区域。

(6)重复步骤(2),当扫描结束时,就可以得到图像中的所有连通区域。

查找每一label标记的点集分别标记上不同的颜色,得到不同障碍物的点云簇,点云聚类流程示意如图1所示。

图1 点云聚类流程示意图

2 基于点云主方向旋转的包围盒建立

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方向大小。

(11)

(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.2 包围盒顶点确定

在得到了点云主方向以后,可以根据点云主方向建立包围盒。这种包围盒的特点是与障碍物之间贴合紧密,间隙较小,能够更准确地描述障碍物的尺寸与朝向。该过程可分为以下步骤进行。

(1)计算障碍物点云集中心位置坐标(xc,yc),如式(14)所示,并计算出以中心点为起点指向点云集各点的向量pi如式(15)所示,其中xmax、xmin、ymax、ymin代表障碍物点云集在x、y、z方向上的最大值和最小值。

(14)

pi=(xi-xc,yi-yc)

(15)

(2)将向量pi绕中心点处z轴旋转-α角得到向量p′i,使点云主方向对其基坐标x轴,即

(16)

(3)遍历旋转后的点云集,得到旋转后点云在x、y、z方向的最大值和最小值x′max、x′min、y′max、y′min、z′max、z′min得到包围盒的8个顶点坐标box′i,即

(17)

(4)将得到的包围盒顶点坐标box′i通过旋转变换回原点集,得到原点集包围盒的8个顶点坐标boxi,即

(18)

点云建立包围盒流程示意如图3所示。

图3 点云建立包围盒流程示意图

3 实验结果及分析

实验采用RS-LiDAR-M1激光雷达进行环境采集并获取点云数据视频,该场景中包含两个小型路障,距激光雷达较近的记为小型路障1,较远的记为小型路障2。一辆大型货车和行人等4个障碍物,其中行人向着远离激光雷达的方向移动。其实验场景如图4所示,输出点云数据如图5所示。

图4 点云采集实验场景

图5 输出点云数据

将地面点云去除,保留障碍物点云。取参数αpl=0.65°、rmax=200、rpl=0.2。任取点云视频中的多帧进行检验,经过二进制网格聚类后点云如图6所示,从图6中可以看出,该方法能够有效分辨场景中障碍物的个数,并且不随帧数的变化而出现漏判或多判的情况。

图6 点云聚类结果

对视频中的各类障碍物进行点数统计并计算最大误差。由于行人随着时间的变换距离激光雷达越来越远,因此行人点云的点数会随着时间的变化较大,故只对静态障碍物进行统计,从而检验聚类算法的准确性。统计结果如表1所示。

表1 各障碍物聚类点数统计

由表1可以看出,随着点云帧数的变化,各静态障碍物的点数变化最大误差均在5%以内,说明基于二进制占用网格的聚类算法能准确地将不同障碍物所属的点集进行聚类。此外大型货车聚类最大误差为1.58%,而小型障碍物的聚类误差为2.99%和3.64%,说明该算法对于点数越多的障碍物,其聚类效果越好。

基于二进制占用网格的聚类算法与传统欧式聚类算法对比如表2所示,两种算法均能检测出场景中的4个障碍物,但基于二进制占用网格的聚类方法运算更迅速,所需时间更短。原因在于一方面对点云采用降低维度的方式进行处理,即由三维点云处理转换为二维图像处理,且二进制占用网格是一种非常简单的二维图像;另一方面该算法无需迭代,只需要对二进制占用网格进行扫描,大大降低了时间复杂度,对于场景中运动状态变换较快的物体具有良好的实时性。两种算法对比如表2所示。

表2 二进制占用网格聚类与欧式聚类算法性能比较

对聚类后的障碍物建立包围盒如图7所示,其中数字代表障碍物的标号。从图7中可以看出,随着帧数的改变,包围盒能始终跟随并包络障碍物点云,且标号保持一致,具有良好的随动性。对于静态障碍物来说,由于主方向不发生改变,其包围盒的朝向与大小未发生改变。而对于行人这类动态障碍物来说,由于在行走过程中存在位置和速度改变,故点云主方向也随之变动,图7中显示该包围盒建立方法能够实时测量点云主方向的变换,进而改变包围盒的朝向和大小,使得包围盒始终紧密贴合行人点云,证明了该方法的有效性。

图7 障碍物包围盒建立

基于点云主方向旋转的包围盒建立算法与AABB包围盒算法对比如表3所示,AABB包围盒是直接以障碍物点集在x、y、z方向上的最大和最小值为顶点建立包围盒。从表3可以看出,两类算法的包围效果与包围盒高相差不大,但基于点云主方向旋转的包围盒长、宽均小于AABB包围盒算法,证明该方法所建立包围盒更加紧致,能够更精确地反映障碍物的大致尺寸,证明了该方法的优越性。

4 结论

提出了基于二进制占用网格的点云聚类算法,首先对点云进行降维处理,将三维点云简化为二维像素图像处理,并且对点云轮廓生成二进制占用网格从而寻找点云主方向,基于主方向旋转点云从而建立包围盒。实验结果表明,该方法能够在保证聚类精度的同时大大提高运算速度,其建立包围盒能够更加准确的反应障碍物的尺寸,具有良好的实时性与随动性,对之后的机械臂自主避障提供了可靠的信息。