基于深度投影的三维点云目标分割和碰撞检测

王张飞，刘春阳，2*，隋 新，杨 芳，马喜强，陈立海，2

(1.河南科技大学 机电工程学院，河南 洛阳 471003；2.机械装备先进制造河南省协同创新中心，河南 洛阳 471003；3.河南省机械设计及传动系统重点实验室，河南 洛阳 471003)

1 引 言

随着无人驾驶技术的兴起，三维激光雷达凭借其测距精度高、抗干扰能力强、全方位扫描等优点，越来越广泛的应用在无人驾驶车辆中，成为无人驾驶车辆地形测绘、环境感知、三维目标识别、防碰撞检测的重要传感器[1-3]。

激光雷达采集的三维点云具有无序性和稀疏性特点[4]，对三维点云进行聚类分割是后续碰撞检测的关键。目前常用的基于特征对点云分割的方法，通常在三维空间中构建复杂的几何特征，然后根据聚类算法对点云进行分割，这类方法虽然可以取得较好的分割效果，但是计算时间过长，往往不能满足点云分割的实时性要求[5-6]。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法是经典的基于密度的聚类方法，通过指定邻域半径和最小数据点阈值对点云进行聚类，但在密度不均匀集上的聚类质量不高。为了提升点云目标分割的准确性，秦佳睿等[7]提出一种自适应选择局部半径的密度聚类算法，通过确定密度峰值点，自适应选择聚类的局部邻域半径；Bogoslavskyi等[8]利用深度图像角度值进行点云目标分割，通过扫描线中的角度差判断是否为同一物体；刘志青等[9]提出信息向量机对LiDAR点云数据分类的方法，点云目标分割的准确度较高，但分割时间效率仍有提升空间。

在无人驾驶汽车的目标检测中，对物体间的碰撞检测是一项重要任务，其中，包围盒算法是一种较为常用的方法，用体积较大而几何特征简单的包围盒近似描述复杂的几何对象，只需对包围盒重叠的对象进行进一步碰撞检测，该方法在满足测量精度要求的前提下，大大减少了运算时间[10]。目前主要研究的三维点云包围盒包括轴对齐包围盒 (Axis-Aligned Bounding Box， AABB)和有向包围盒 (Oriented Bounding Box， OBB)等，然而这些包围盒在碰撞检测速度和精度上往往相互矛盾。

本文提出一种基于深度投影的点云目标实时分割方法，首先对原始点云进行预处理，去除噪声点和地面点，然后进行深度投影，采用广度优先搜索法搜索临近点，根据激光雷达和不同点云之间的角度对目标进行分割，利用自适应角度阈值的方法，根据不同的激光雷达扫描范围设定不同的角度阈值，提高点云目标分割的准确性和实时性。最后使用混合层次包围盒算法对分割后的点云目标进行碰撞检测，采用AABB包围盒算法快速滤除相距较远且不可能碰撞的对象，对于AABB包围盒存在相交的对象，则进一步采用紧密性较好的OBB包围盒检测碰撞状态，大大提高了碰撞检测的精度和效率。

2 点云处理方法

2.1 点云处理流程

图1为激光雷达点云目标分割和碰撞检测总体流程图。首先用激光雷达采集点云数据，然后使用体素化滤波去除外点和噪声点，采用渐进式形态学滤波方法对地面点进行移除，建立非地面点云与深度投影图像的映射关系，利用深度投影图像的自适应角度阈值的方法对非地面点云进行目标分割，最后使用混合层次包围盒算法进行碰撞检测。

图1 激光雷达数据处理流程图Fig.1 Flowchart of LiDAR data processing

2.2 点云滤波

在无人驾驶车辆行驶过程中，激光雷达采集的三维点云通常是密度非均匀、非结构化分布、包含有噪声和外点的无序点云。使用体素化滤波方法，不仅可以减少点云数量，而且可以保持点云数据的形状特征[11]。进行体素化滤波首先需要确定点云数据的范围，求出点云数据集的最小三维长方体包围盒，将点云数据划分到三维体素栅格中[12]，用体素内所有点集pI的坐标平均值替换当前体素内所有点集的坐标值。假设体素大小为a，则点云在三个坐标轴方向上的体素个数为：

(1)

式中：floor函数为返回数字的下舍整数，xmax，ymax，zmax和xmin，ymin，zmin分别表示点云在激光雷达坐标系中三个坐标轴方向扫描的最远和最近距离。

此外，无人驾驶车辆采集的点云数据需要对地面点和非地面点进行分类，采用渐进式形态学滤波方法可以有效去除地面点[13-14]，避免后续非地面点云目标分割和包围盒碰撞检测时发生干涉。

2.3 深度投影图像建立

点云数据进行体素化滤波和地面点去除后，根据非地面点云的空间几何特征，基于深度投影图像的自适应角度阈值进行点云目标分割。首先将三维点云数据通过深度投影转化为深度投影图像[15]，通过激光雷达采集的点云数据可计算出每个激光束到目标的距离值，然后将三维点云进行深度投影，其中，深度投影图像的每个像素点存储了激光雷达与扫描对象之间的空间距离值，深度投影图像的行数Rr取决于垂直方向上激光器的数目，深度投影图像的列数Rc取决于激光雷达水平角度的分辨率[8]。三维点云与深度投影图像之间的映射关系如图2所示。

(a)原始点云(a)Original point cloud(b)深度投影图像(b)Depth projection image

(c)场景图(c)Scene map图2 三维点云投影到深度图Fig.2 3D point cloud projection to depth map

三维点云空间直角坐标点(x，y，z)可通过坐标变换转化为深度投影图像二维坐标点(R，C)，转化公式为：

(2)

2.4 非地面点云目标分割

三维点云转化为深度投影图像后，根据深度投影图像计算激光雷达与不同点云之间的角度值。图3(a)为激光雷达扫描线与不同点云之间的角度示意图，假设激光雷达位于O点，扫描线OA，OB表示激光束与物体相交于A，B两点，OA和AB之间的夹角为β，点A和点B之间的连线可估计扫描对象的表面[16]。如图3(b)所示，两个相邻物体已被标注为不同的颜色(彩图见期刊电子版)，当三维激光雷达扫描周围环境时，在同一物体上点云分布较为密集，两个相邻点A和B到激光雷达的距离差值较小，所以β角度较大，而相邻物体之间，由于存在间隔，两个相邻点A和B(点A和B分别取自两个相邻物体)到激光雷达的距离差值较大，所以β角度较小。因此，基于激光雷达与不同点云之间的角度值β可以判断是否为同一物体。OA和AB之间夹角β的计算公式为：

β=arctan(|BH|/|HA|)= arctan((d2sinα)/(d1-d2cosα))，

(3)

式中：α为扫描线OA和OB之间的夹角，d2和d1分别为OA和OB的距离。

(a)点云之间的角度(a)Angle between point clouds

(b)相邻点云目标分割(b)Adjacent point cloud object segmentation图3 点云之间的角度和点云目标分割示意图Fig.3 Angle between point clouds and point cloud object segmentation

设定角度阈值为θ，当夹角β>θ时，认为两点代表同一物体，根据不同的应用场景选择不同的角度阈值θ，可以起到较好的分割效果。本文主要针对城市道路环境进行测试，使用激光雷达采集多组城市道路环境的点云数据，通过实验发现，设定最小角度阈值θmin=0.114 rad时具有较好的点云分割效果。为了进一步提高点云目标分割的准确度，降低噪声点的干扰，在点云目标分割算法中设置最大和最小点云数量阈值，去除不满足数量要求的点云目标。

由于激光雷达点云数据的密度会随着扫描距离的变化而变化，扫描距离近的点云密度较高，扫描距离远的点云密度较低，所以在同一应用场景下，角度阈值θ不应是固定值，而应是随着扫描距离而变化的自适应参数。本文根据激光雷达扫描距离进行分段，如图4所示，根据不同的扫描距离设定不同的角度阈值，最终利用回归分析扫描距离和角度阈值的关系建立回归方程。通过回归方程，自适应角度阈值θ为：

(4)

式中：l为激光雷达扫描距离，由于激光雷达扫描距离有效范围为0～100 m，所以，0

图4 激光雷达扫描距离和角度阈值Fig.4 Lidar scan distances and angle thresholds

2.5 激光雷达和无人驾驶车辆的位置标定

激光雷达与无人驾驶车辆位置的标定过程，实际上是求解激光雷达坐标系与车辆坐标系之间的坐标变换矩阵[17-18]，本文将激光雷达安装在车辆的顶部位置，并标定激光雷达与车辆坐标系方向相一致，如图5所示，激光雷达的坐标系的x轴指向车头，z轴垂直车身向上，y轴与x，z轴相互垂直。因此，无人驾驶车辆只需要构建AABB包围盒。为起到预防碰撞的效果，可将无人驾驶汽车包围盒按一定比例进行放大，生成体积较大的包围盒。

图5 激光雷达与无人驾驶车辆位置标定Fig.5 Lidar and unmanned vehicle position calibration

3 点云数据混合层次包围盒算法描述

3.1 混合层次包围盒算法流程概述

在预处理阶段，采用自顶向下的方法为几何对象构建包围盒层次二叉树[19]，具体分为两层，分别是X层的AABB包围盒和Y层的OBB包围盒，三维激光雷达和无人驾驶车辆标定在同一坐标系下，且坐标轴方向相同，所以无人驾驶车辆只需构建AABB包围盒，对检测对象分别构建AABB和OBB包围盒。本文所采用的混合层次包围盒算法，在碰撞检测阶段，对同一物体最多进行两次包围盒检测：AABB与AABB包围盒碰撞检测、AABB与OBB包围盒碰撞检测。

3.2 AABB与AABB包围盒碰撞检测

AABB包围盒的各轴方向与坐标轴的方向平行，所以AABB碰撞检测只需要判断包围盒在三个坐标轴上投影是否相交，若三个轴上的投影都相交，则认为发生碰撞[20]。否则，认为不发生碰撞，最多需要判断3次。碰撞检测效果如图6所示。

图6 AABB与AABB包围盒碰撞检测Fig.6 AABB and AABB bounding box collision detection

3.3 AABB与OBB包围盒碰撞检测

AABB和OBB包围盒采用分离轴定理进行碰撞检测[21]，假设存在包围盒A和B，其中，Ai，Bi(i=1，2，3)分别是A，B两个包围盒长、宽、高的一半，Ci，Di(i=1，2，3)分别是包围盒A，B长、宽、高的单位向量，T是两包围盒中心的方向向量，L是分离轴的方向向量[22]。φA和φB分别是包围盒A和B长、宽、高的一半在L上投影距离相加的和。A，B两个包围盒在分离轴上的投影距离为|T·L|。则有：

(5)

(6)

3.4 包围盒碰撞检测方法对比分析

如图7所示，A表示无人驾驶车辆的AABB包围盒，B表示道路转弯处物体的OBB包围盒，C表示道路转弯处物体的AABB包围盒，D表示无人驾驶车辆的运动轨迹。当包围盒A与包围盒C发生碰撞时，检测包围盒A与包围盒B是否碰撞，如果包围盒A与包围盒B未发生碰撞，则该区域是安全的。反之，两者发生碰撞。

4 实验与分析

实验环节使用的运算平台为Jetson TX2，搭载NVIDIA的Tegra处理器和8 GB内存，算法采用Python编程实现，并使用OpenGL进行显示。

为验证本文所提出的点云目标分割和碰撞检测算法的准确性和实时性，实验中使用KITTI公开的Velodyne-64线激光雷达数据集作为算法测试样本，从数据集中随机抽取210帧点云数据进行试验，获取的原始点云数据如图8(a)所示。对点云数据进行预处理，去除噪声点和地面点的效果如图8(b)所示，地面点去除效果比较明显。

(a)AABB and AABB

(b)AABB and OBB

(c)Proposed algorithm图7 包围盒碰撞检测对比分析Fig.7 Contrast analysis of bounding box collision detection

(a)原始点云(a)Original point cloud

(b)去除地面点和噪声点(b)Ground point and noise point extraction图8 点云数据预处理Fig.8 Point cloud data preprocessing

目标分割中常用的区域增长算法是通过判断点云的法向量和曲率对点云进行聚类，欧式聚类算法是根据不同点云间的空间欧几里得距离对点云聚类。图9为区域增长算法、欧式聚类算法和本文所提出的基于深度投影图像的自适应角度阈值的点云目标分割方法进行检测的对比图。

在点云目标分割过程中，区域增长算法和欧式聚类算法较为依赖参数值的设定，图9(a)中将激光雷达附近的汽车分割成多个目标，出现过分割问题，如①所框选的目标所示；图9(b)中将距离激光雷达较远的汽车分割成多个目标，并出现多处过分割问题，如①、②和③处所框选的目标所示；而本文所提出的方法较好地分割了周围点云目标，如图9(c)所示，其中①为柱子、②为无人驾驶汽车包围盒、③为汽车。

选取区域增长算法、欧式聚类算法和本文所提出的算法对点云目标进行分割，并通过混合层次包围盒算法对分割后的点云目标进行碰撞检测，在实验数据中并未出现碰撞情况。

(a)区域增长点云目标分割算法(a)Region growing point cloud object segmentation algorithm

(b)欧式聚类算法(b)European clustering algorithm

(c)本文所提点云目标分割算法(c)Point cloud object segmentation algorithm图9 点云目标分割和碰撞检测效果Fig.9 Point cloud target segmentation and collision detection effects

图10为欧式聚类算法、区域增长算法和本文提出的方法点云数据处理时间的对比图，欧式聚类算法和区域增长算法的平均运行时间分别为992 ms和1 734 ms。本文所提出的基于深度投影图像的自适应角度阈值的点云目标分割方法平均运行时间为73 ms，时间效率上约为区域增长算法的23倍，并且相对欧式聚类算法和区域增长算法，该方法处理单帧点云数据的时间效率稳定，可满足点云数据处理的实时性和稳定性要求。

图10 分割算法的时间效率对比Fig.10 Time efficiency comparison of segmentation algorithms

为了分析点云目标分割算法的准确度，实验中通过对激光雷达点云数据随机选取442个目标进行人为手动标记，以P作为目标分割的准确率，通过点云目标分割算法准确分割点云目标的数量Sa占总目标数量的比例为：

(7)

对点云数据分别采用三种目标分割算法进行处理，计算每种算法正确分割的目标数量Sa，最后分别计算三种算法目标分割的准确率。本文所提算法的准确率为78.82%，欧式聚类算法的准确率为72.62%，区域增长聚类算法的准确率为75.11%，所提算法相对欧式聚类算法的准确率提高了约6%，相对区域增长算法的准确率提高了约4%，能够更准确地对点云目标进行分割，取得了较好的效果。

5 结 论

本文针对无人驾驶车载激光雷达的点云目标分割和碰撞检测算法进行研究，首先将采集的点云数据使用体素化滤波方法去除噪声点，减少点云数量的同时，保持点云的形状特征，再采用点云渐进式形态学滤波方法去除地面点云，然后使用基于深度投影图像的自适应角度阈值的方法对点云目标进行分割，根据不同的点云扫描距离设置不同的角度阈值，有效降低了点云目标的过分割问题，最后使用混合层次包围盒算法对分割之后的点云进行碰撞检测。通过实验发现，本文所提出的点云目标分割方法相对于区域增长算法，时间效率上提高了大约23倍，相对于欧式聚类算法，准确率提升了约6%。通过混合层次包围盒算法对分割后的点云目标绘制包围盒，并进行碰撞检测，相较于传统包围盒算法，混合层次包围盒算法在满足准确度要求的前提下，大大提高了碰撞检测时间效率。

点云目标分割研究主要根据点云空间几何特征进行目标分割，绝大多数算法都是针对特定场景提出的，提高算法的自适应性将是未来研究的关键。