基于DBSCAN聚类算法的激光扫描雷达可视化障碍物检测

张雨晨

北方工业大学城市道路交通智能控制技术北京市重点实验室，北京 100043

近年，人工智能时代的逐渐到来，无人驾驶技术高速发展，无人驾驶技术的安全性又一次被推到了风口浪尖上，行驶的无人驾驶汽车具有许多关键性难题，例如，对周围环境的感知、针对周围环境情况做出预测等，障碍物检测成为确保无人驾驶技术安全性的一个重要问题，只有实时并且精准地完成障碍物的检测才能确保无人驾驶车辆的安全问题。在周围环境不明的情况下，有效的信息采集对无人驾驶汽车等自动行驶机器人显得尤为重要，无人驾驶其中一个核心的技术就是采用何种传感器以及如何从传感器信号中获取有用的环境信息，并采取有效的信息处理技术，从而实现障碍物的检测。目前，相关企业在障碍物检测方面多使用热成像红外检测、摄像头检测等检测方法，这些技术存在数据量小、信息缺失、分辨率不高、抗干扰能力差、检测数据传输的实时性不强等问题，所以提出使用16线激光扫描雷达来进行障碍物信息检测。

1 激光扫描雷达数据采集

障碍物检测的难点是如何快速、准确的找到障碍，系统通过Velodyne公司的VLP-16三维激光雷达采集数据，VLP-16三维激光雷达如图1所示。

图1 VLP-16三维激光雷达实物图

1.1 雷达简介

VLP-16激光雷达是Velodyne公司生产的规格最小的雷达，可随时上传周围障碍物的反射情况和距离，并且实现了雷达的转速可调节。VLP-16激光雷达同时具有重量轻、易安装等优点，尤其适合安装在小型智能车、机器人等小型设备上面。如表1所示，VLP-16激光雷达的检测精度可达3cm以内，最远可达100m的远距离探测，扫描帧频最高可达10Hz，每秒高达30万个点数据检测，水平视角360°全方位扫描，-15～15°的垂直视角可完成低空障碍物检测。

表1 VLP-16三维激光雷达性能指标

1.2 数据采集并解析

VLP-16三维激光雷达采集的环境信息通过UDP（User Datagram Protocol）协议传输到上位机平台，数据包（Data Packet ）结构如图2所示，激光扫描雷达每次接收的一个数据包由占42个字节的协议头（Header）、12个数据块（Data Block）、时间戳（Time Stamp）、出厂标志（Factory Bytes）组成，VLP-16三维激光雷达出厂标志为固定值22h。

图2 数据包结构

每一个完整的数据包包含12个数据块，数据块结构如图3所示，来自16个激光发射器的数据信息包含在一个数据块中，每个数据块只返回一个水平方位角信息（Azimuth N），返回16个垂直方位角信息，将激光扫描雷达所在点上下的15°分为16个空间角度。解析数据包的旋转角度、测量距离和报告校准反射率，得出水平方位角及垂直方位角。

图3 数据块格式

如图4所示，采集出障碍物距离激光扫描雷达的距离信息后，在三维空间中建立立体模型，数据点距原点的距离为R，垂直夹角为W，水平夹角为a，数据点在三维立体空间模型中的X、Y、Z坐标由公式（1）、（2）、（3）可计算得出。在得出障碍点在三维空间模型中的X坐标、Y坐标、Z坐标后，数据采集完成。

图4 三维空间建模

1.3 空间环境搭建

在空间中搭建一个10m×10m×2m立体空间，如图5所示，该空间由100×100×20个小立方体组成，小立方体的长宽高分别为10cm，即激光扫描雷达的检测精度为10cm，符合实际障碍物检测情况。以该三维立体空间的质心为原点，若检测到某小立方体处有障碍物，则填“1”，否则填“0”。至此，三维空间环境搭建完成，并且将所有采集到的障碍物信息填充到该三维空间模型中。

图5 三维立体空间搭建

2 雷达数据可视化上位机软件搭建

数据可视化，即以数据为视角看待世界，清晰有效地传达与沟通信息，直观清晰地看出障碍物的大小，障碍物数据可视化主要使用dbscan算法和python编程语言中的matplotlib库实现，通过Pyqt创建一个GUI（图形用户界面）应用程序。

2.1 dbscan算法

基于密度的空间聚类算法（Density-basedspatial clustering of application with noise， DBSCAN）——在数据空间中将簇看作是被低密度区域分隔开的高密度对象区域。

2.1.1 DBSCAN算法思想

DBSCAN基本概念如下：

ϵϵ-邻域：Nϵ(xi)Nϵ(x→i)={xj∈D|distance(xi,xj)x→j∈D|distance(x→i,x→j)≤ϵ≤ϵ}，Nϵ(xi)Nϵ(x→i)包含了样本集DD中与xi(x→i)距离不大于ϵϵ的所有样本。

核心对象core object：若|Nϵ(xi)N∈(x→i)|≥MinPts≥MinPts，则称xi(x→i)是一个核心对象。即：若xi(x→i)的∈∈-邻域中至少包含MinPtsMinPts个样本，则称xi(x→i)是一个核心对象。

密度直达directly density-reachable：若xi(x→i)是一个核心对象，且xj∈x→j∈N∈(xi)N∈(x→i)，则称xj(x→j)由xi(x→i)密度直达，记作xi(x→i)-＞xj(x→j)。

密度可达density-reachable：对于xi(x→i)和xj(x→j)，若存在样本序列（p0, p1, p2, ..., pm, pm+1, p→0, p→1, p→2, ..., p→m，p→m+1）， 其 中p0(p→0)=xi(x→i)，pm+1(p→m+1)=xj(x→j)，ps∈D, s=1, 2, ..., m, p→s∈D, s=1, 2, ..., m。如果ps+1(p→s+1)由ps, s=1, 2, ..., m, p→s, s=1, 2, ..., m密度直达，则称xj(x→j)由xi(x→i)密度可达，记作xi(x→i)～＞xj(x→j)。

密度相连density-connected：对于xi(x→i)和xj(x→j)，若存在xk(x→k)，使得xi(x→i)和xj(x→j)均由xk(x→k)密度可达，则称xj(x→j)由xi(x→i)密度相连，记作xi(x→i)～xj(x→j)。

DBSCAN聚类思想如图6所示，ϵϵ用一个相应的半径表示，设MinPts=3，请分析Q，M，P，S，O，R这5个样本点之间的关系。根据以上概念知道：由于有标记的各点M、P、O和R的Eps近邻均包含3个以上的点，因此它们都是核对象；M是从P“直接密度可达”；而Q则是从M“直接密度可达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。类似地，S和R从O是“密度可达”的；O、R和S均是“密度相连”的。显然，DBSCAN聚类算法的目的是找到密度相连对象的最大集合。

图6 DBSCAN聚类算法示意图

2.1.2 dbscan算法聚类过程

DBSCAN聚类算法聚类过程如图7所示，首先初始化数据集和搜索集，然后依次遍历数据集中未归类的节点，检查数据集是否遍历完毕，若遍历完毕则聚类完成；若数据集未完成遍历，则判断未归类节点是否为核心对象，若为核心对象，则将未归类节点的邻域对象放入搜索集，接下来遍历搜索集中未归类的点，遍历完成后判断该点是否为核心对象，若为核心对象，则把该点的邻域对象放入搜索集中，将此两点视为同一类，继续进入下一个聚类过程，直到数据集遍历完成，结束聚类。

图7 DBSCAN聚类算法执行流程图

2.2 上位机软件搭建

使用pyqt5对上位机进行页面布局，设计障碍物可视化区以及障碍物距离显示区，对VLP-16三维激光雷达前后5m，上下1m的空间进行障碍物扫描检测。实际设计的图形界面如图8所示，横坐标为水平位置显示，单位长度为2m，纵坐标为竖直位置显示，单位长度为0.25m。

图8 上位机图形界面示意图

3 实际检测障碍物实验并分析结果

本文根据实际情况搭建系统测试环境，验证VLP-16三维激光雷达采集数据并实现可视化的运行效果。在实验VLP-16三维激光雷达前方放置两块相同的目标木板，上位机显示如图9所示，该雷达可以精准的扫描区分出不同障碍物，并实时显示其大小和位置，周围的障碍物点为实验场空间中的其余障碍物，更可以证明VLP-16三维激光雷达的准确性。

图9 上位机障碍物显示

多次改变其周围环境，观测上位机的障碍物显示情况，如表2所示。在周围环境复杂度不同的情况下进行障碍物检测，分别对比障碍物距离精度、聚类程度、显示实时性等特性。实验结果表明，即使在高度复杂的环境中，该设计也能很好地完成障碍物检测，达到高精度、实时显示的目的。

表2 不同环境下障碍物检测结果

4 结语

本文提出了一种使用VLP-16三维激光雷达采集障碍物信息，并且使用图形界面编程将障碍物信息实现可视化。主要解决了激光扫描雷达采集障碍物信息及使用DBSCAN聚类算法聚类的问题，为障碍物检测提供了一种行之有效的思路。首先，建立与VLP-16三维激光雷达的通信，解析数据包的旋转角度，测量距离等参数，然后由得到参数计算障碍物点X坐标、Y坐标、Z坐标，将其位置标记在建立的三维立体空间模型中，最后使用DBSCAN聚类算法完成障碍物点的聚类，显示到搭建的上位机平台。本文所述的障碍物检测并显示的方法具有数据采集速度快、分辨率高、抗干扰能力强等优点。该障碍物检测技术适合应用到小型智能机器人、无人驾驶汽车等设备，卓有成效地推动了无人驾驶技术的发展，一定程度地解决了无人驾驶的安全性问题，为障碍物检测识别等提供了一个良好的范本。