基于改进DBSCAN算法的激光雷达目标物检测方法＊

黄 钢 吴超仲 吕能超▲

（1.武汉理工大学智能交通系统研究中心 武汉430063；2.水路公路交通安全控制与装备教育部工程研究中心 武汉430063）

0 引 言

道路交通安全已经成为研究热点，特别是围绕车路协同系统［1－3］和智能汽车（intelligent vehicle）开发的汽车安全驾驶系统更是受到广泛关注。研究表明［4－6］，在国内外智能交通系统和智能车辆的研究领域中，有很多采用不同算法和手段进行前方路面障碍物探测的研究，如利用单目视觉、双目视觉、彩色CCD等进行探测。

典型的目标检测方法如基于图像的目标检测能在天气良好的情况下较好的检测出目标物，但识别精度受环境影响很大，容易误判和漏判，且处理图像过程繁杂，需花费大量时间检测与行人无关的区域，此外图像信息无法精确识别行人距离。而激光传感器则具有检测速度快、目标可靠、能提供距离信息等优点。

然而，激光传感器识别行人等障碍物目标时，扫描的数据是一些没有具体特征的平面点，且雷达数据有较多冗余，若不对激光数据进行处理，则很难识别出有效的目标物。目前，国内外众多研究者针对不同研究目的提出了许多改进的DBSCAN算法。如刘军等［7］人提出了基于 DBSCAN方法的交通事故多发点（段）的排查方法及其改进思路，并且结合J2EE技术，实现了1个Web环境下的交通事故数据挖掘系统，该方法并未用于目标检测，且聚类方法较为简单；冯少荣等［8］人针对“基于密度的带有噪声的空间聚类”（DBSCAN）算法存在的不足，提出“分而治之”和高效的并行方法对DBSCAN算法进行改进.通过对数据进行划分，利用“分而治之”思想减少全局变量Eps值的影响，利用并行处理方法和降维技术提高聚类效率，降低DBSCAN算法对内存的较高要求，并采用增量式处理方式解决数据对象的增加和删除对聚类的影响，该改进算法能起到较好的效果改进的聚类算法无论是在聚类质量还是在聚类效率上都得到了比较满意的结果，但算法较为复杂；又如国外学者Derya Birant等［9］人提出的1种ST-DBSCAN算法，在该算法中，作者提出基于识别核心点、噪声点、相邻簇的3种边缘扩展方法，该算法对比现有基于密度的聚类算法的优点是能够根据非空间、空间及时间数据集下物体的值寻找出不同的簇，但该算法的数据源为海洋数据，具有一定的特殊性。

笔者根据采集激光雷达数据点的特征，对数据精简处理，加快计算速度和提高激光雷达识别的精确性，从大量数据中提取有用信息，通过改进DBSCAN聚类算法进行有效的数据精简、数据去噪和障碍物识别，主要用于智能交通路侧目标物检测。

1 基于聚类算法的激光雷达目标物识别

激光雷达数据是分布于对象表面的一系列三维点坐标，在形式上呈离散分布，扫描带中数据分布不均匀——不同位置的光斑密度不同，尽管直接获取点三维坐标是激光雷达最显著的特点之一，但其数据类型并不局限于此。强度信号是另1个有用的信息源，它反映了地表物体对激光信号的响应。由于一些技术上的原因（如缺乏有效的定标手段），还没有得到多少实际应用。基于激光雷达点云数据的特点，为精确的辨识行人，需对激光雷达数据进行有效的聚类。

作为数据挖掘领域的1个重要研究方向，聚类分析已经广泛地应用于模式识别、图像处理以及数据分析等诸多领域。常用的聚类方法有：划分聚类法、层次聚类法、基于密度的聚类法、基于网络的聚类法以及基于模型的聚类方法等［10－12］。利用聚类算法，可将具有相同性质的数据点归为同一簇，根据簇的特点有效地判别目标物的种类。DBSCAN算法是1种具有代表性的基于密度的聚类算法。它能在存有噪声的空间数据中发现任意形状的类。

基于密度的聚类算法DBSCAN通过计算数据集中每个数据点的区域密度来进行聚类，需设置Eps和MinPts这2个参数。由DBSCAN算法的定义和引理［8］可知，1个簇就是密度相连的点的最大集合，且可以由其中任意1个核心点唯一确定。

基于上述事实，DBSCAN的算法思想是：从数据集中任意选择1个点p开始，查找数据集中所有从p密度可达的点。如果p为核心点，则其Eps邻域内的所有点与p属于同1个簇，将这些点作为即候选点，通过不断查找从候选点的密度可达的点来扩展该簇，直至找到1个完整的簇；如果p不是核心点，即没有对象从p密度可达，则p被暂时标注为噪声点。然后，算法对数据集中未被处理的点重复上述过程，进行其他簇的扩展。最后数据集中不属于任何簇的点即为噪声点。

2 基于改进DBSCAN算法的激光雷达数据处理

DBSCAN算法在聚类过程中存在以下不足之处。

1）对聚类半径、聚类邻域中对象个数等输入参数敏感。

2）聚类半径、聚类邻域中的对象个数是全局惟一确定的，对于不同密度分布时，聚类效果较差；

3）当聚类的核心对象确定后，以此核心对象为中心向外扩展，从而导致随着核心对象不断增多需要的内存也不断地增大。

研究所用的是IBEO-LUX 4线激光雷达，结合雷达的应用环境分析可知其数据有如下特点：①数据应转化成直角坐标系下的点，便于聚类分析；②雷达应用环境决定雷达数据聚类时，类的数目是变化的；③雷达数据的密度随着目标物距离的改变而改变。

笔者结合激光雷达二维数据和DBSCAN算法的特点，针对激光雷达应用对DBSCAN算法进行改进。

1）改进搜索速度。原始算法中，核心点的Eps邻域内所有的点都要重新搜索，而实际上起作用的点是该邻域内离核心点最远的数据点，这样必定会浪费较多的搜索时间。笔者提出的改进方法是选取有代表性的点作为扩展点，此时需要解决2个问题：①代表对象应该选多少；②如何选择代表对象。代表对象太多，算法的效率会很低；如果太少，则代表对象邻域难以比较完全地覆盖其他对象的邻域，从而造成对象“丢失”，影响到聚类质量和效率。不考虑扫描点的高度信息，在激光雷达数据点存在的二维平面内，可以选代表对象数为4［13］。此时以核心点为坐标原点建立1个直角坐标系，寻找该直角坐标系下4条半轴（X轴正负半轴和Y轴正负半轴）附近远离所选核心点最远的4个点，以这4个点为代表点向外扩展簇，能极大的缩短搜索时间。

2）改进输入参数。激光雷达的数据密度会随着扫描的距离变化而变化，距离激光雷达原点越近则数据密度越高，越远则数据密度越低。在该情况下，搜索半径即Eps的值应该随搜索点与激光雷达的距离而变化，而不是保持某个值不变。因此提出聚类半径Eps与扫描距离相关的函数如下。

式中：int（）为取整；α为聚类半径系数；（xi，yi）为该数据点在以激光雷达点为坐标原点建立的直角坐标系下的坐标；θs为激光雷达的扫描角分辨率；L为聚类区域步长。改进的DBSCAN算法流程图见图1。

图1 改进的DBSCAN算法流程图Fig.1 Algorithm flow chart of improved DBSCAN

算法步骤如下。

1）初始化，输入聚类数据。

2）任意选取1个数据点xi。

3）如果xi没有被划分到某1个簇，判断其是否为核心点。

4）若为核心点，则扩展以xi为核心对象的簇，开始搜索该数据点邻域，若不是核心点，则跳过该点。

5）搜索xi领域时，需检测邻域内与该点距离小于Eps值的点，Eps值大小见式（1）。

6）取出领域内的4个点（取点规则如前文所述）作为代表点，代表点入栈。

6）若栈非空，则取出栈顶数据，跳至步骤4）；若为空，则簇数增加1。

7）若所有的数据点均被处理，则结束；否则，转步骤2）。

3 实验结果与论证分析

采用德国IBEO公司提供的LUX4线激光雷达作为主传感器，正常使用时，该激光雷达安装在实验用车的保险杠部位，在激光雷达附近安装有摄像头，摄像头采集的图像信息作为后验信息，在VS2008下通过雷达的API接口获取并采集数据，激光雷达与图像数据均加入本地时间，这样便可找出每1帧激光雷达数据点对应的图像信息。为验证算法的实用性，在进行实车实验前，进行了模拟实验。如图2所示，将激光雷达固定在某处，摄像头放置在激光雷达上部，模拟行人站立于白板之前。

图2 激光雷达原始数据对应的实验行人示意图Fig.2 The pedestrians in experiment

3.1 简易实验环境下改进DBSCAN算法的精度与搜索速度分析

在Matlab中对激光雷达数据进行原始聚类以及利用改进后的算法进行聚类，对比图像信息分析2种算法的精确度，以及搜索时间。在采集的1 589帧激光雷达数据中随机选取10帧数据进行聚类，并从采集的图像数据中找到对应的目标物作为后验信息，选取有代表性的1帧数据为例，对比分析改进前后的聚类效果。激光雷达采集的原始数据如图3所示，所采集的数据点为一系列无规则的点集；改进前的聚类算法效果如图4所示，原始DBSCAN算法将目标简单的分为了4类，且把2个行人归为同一类，说明原始的算法在精度上存在较大误差，分类结果较粗；改进后的聚类算法效果如图5所示，改进后的DBSCAN算法将目标分成了包含噪声在内的7类，且能将2个行人及其后面的白板分成3个不同的簇，且对噪声的划分也更为精确。对比图4、图5可知，改进后的DBSCAN算法在精确度上有了很大的提高。

图3 激光雷达原始点Fig.3 The original points of laser rader

图4 未改进的DBSCAN算法聚类Fig.4 Clustering of DBSCAN before improving

图5 改进后的DBSCAN算法聚类Fig.5 Clustering of improved DBSCAN

改进前后10帧激光雷达的聚类算法搜索时间见表1。由表1可见，改进后的DBSCAN聚类算法的搜索时间比改进前均有较大幅度提高，提高了50%。

表1 改进前后DBSCAN聚类算法的搜索时间Tab.1 the searching time of unimproved and improvedDBSCAN

3.2 实车实验下改进DBSCAN算法的精度及搜索速度分析

在实车实验中，由于道路环境具有一定的复杂性，行人及噪声较多，无法同简易实验环境一样根据图像信息检验目标物的检测精度，因而需要对激光雷达数据的簇形状有一定的先验知识。研究表明［14］，激光雷达数据点聚类后，不同的簇形状可以代表不同的目标物。对于车辆行驶过程中，路面可能出现的目标，笔者在激光层根据聚类结果的激光轴数对目标做了如表2的分类。

表2 激光轴数与点的对应Tab.1 the corresponding of lidar axis and points

根据表2提供分类信息，结合图像信息提供后验检测，分析目标物的情况。该表亦验证了简易实验环境下改进DBSCAN算法的精度。由图5可以明显看出，激光雷达采集数据中应该包含2个行人以及1块白板，对比分析图4和图5可知，未改进的DBSCAN算法（见图4）把白板和行人都归到了同一类，而改进后的DBSCAN算法（见图5）则能很好的辨识2个人以及身后的白板。此外，改进后的算法还能很好的识别墙体（即单轴物体），说明该算法具有良好的检测精度。

将该算法应用与实车实验中，实验场景选在较为复杂的学校主干道上，激光雷达安装在车辆保险杠部位，摄像头安装在激光雷达正上方便于检验算法检测的精度。在选取的10帧激光雷达数据中，由图像信息可以检验出，激光雷达视角内共出现了21个行人，5辆汽车，其他不明显目标物10个，改进后的DBSCAN算法结合表2提供的先验知识能检测出17个行人，5辆汽车，行人检测率为80.95%，而原始的DBSCAN算法只能检测出13个行人，4辆汽车，行人检测率为61.90%，由此可以看出，在行人检测方面，改进的DBSCAN算法能较好的提高检测精度。

此外，改进的DBSCAN算法能较大的提高搜索速度。表1结果表明，在10帧数据中，改进后DBSCAN算法的搜索时间较改进前缩短了44.70%，说明该算法在提高搜索精度的同时也提高了搜索效率。

4 结束语

笔者结合LUX4线激光雷达数据特点，使用基于密度聚类的DBSCAN算法对激光雷达数据进行聚类，并对原有的DBSCAN算法进行了改进，主要修改了算法中的聚类半径以及搜索范围，使用同步图像数据作为后验信息检验激光雷达视角内的目标物，对比分析原始DBSCAN算法以及改进的DBSCAN算法，结果表明，改进后的激光雷达具有以下优点。

1）改进后的DBSCAN算法行人检测率达到了80.95%，极大的提高了DBSCAN算法的检测精度；

2）改进后DBSCAN算法的搜索时间较改进前缩短44.70%，较好的提高了目标物识别效率。

综上，笔者提出的改进的DBSCAN算法能较好地提高目标物识别的精度及效率，该算法可应用于交通领域目标物检测中，为道路交通安全提供有力的保障。在雷达数据处理方面，笔者所取的4个点，在一定程度上存在数据丢失问题，统计丢失率约为5%，因而，在激光雷达数据点代表点的选取上，仍需做更多的研究。

［1］ 陈超，吕植勇，付姗姗，等.国内外车路协同系统发展现状综述［J］.交通信息与安全，2011，29（1）：102-106.CHEN Chao，LYU Zhiyong，FU Shanshan，et al.Overview of the development in cooperative vehicle-infrastructure system home and abroad［J］.Journal of Transport Information and Safety，2011，29（1）：102-106.（in Chinese）

［2］ 黄罗毅，吴志周，杨晓光，等.基于仿真的IEEE802.11P在车路协同中的适应性研究［J］.交通信息与安全，2011，29（3）：123-126.HUANG Luoyi，WU Zhizhou，YANG Xiaoguang，et al.Simulation of the adaptability of the IEEE 802.11Pin intellidrive system［J］.Journal of Transport Information and Safety，2011，29（3）：123-126.（in Chinese）

［3］ 樊瑶，褚燕利.基于多传感器融合的智能车路协同仿真系统［J］.公路.2014，（10）：189-193.FAN Yao，CHU Yanli.Intelligent cooperative vehicle infrastructure simulation system based on multi-sensor Fusion［J］.Highway，2014，（10）：189-193.（in Chinese）

［4］ 张阳，刘伟铭，吴义虎.面向车载辅助驾驶系统的快速行人检测方法［J］.公路交通科技.2013.30（11）：131-138.ZHANG Yang，LIU Weiming，WU Yihu.A fast pedestrian detection method for vehicle auxiliary driving system［J］.Journal of Highway and Transportation Research and Development，2013，30（11）：131-138.（in Chinese）

［5］ 严新平，黄合来，马明.美国道路交通安全现状及研究热点［J］.交通信息与安全，2009，27（5）：1-9.YAN Xinping，HUANG Helai，MA Ming.Road Safety in the United States：State of the Art and the Practice［J］.Journal of Transport Information and Safety，2009，27（5）：1-9.（in Chinese）

［6］ 严新平，张 晖，吴超仲，等.道路交通驾驶行为研究进展及其展望［J］.交通信息与安全，2013，31（1）：45-51.YAN Xinping，ZHANG Hui，WU Chaozhong，et al.Research progress and prospect of road traffic driving behavior［J］.Journal of Transport Information and Safety，2013，31（1）：45-51.（in Chinese）

［7］ 刘军，艾力，马晓松.一种改进的DBSCAN聚类算法的研究与应用［J］.交通与计算机，2008，26（3）：60-64.LIU Jun，AI Li，MA Xiaosong.An improved DBSCAN clustering algorithm［J］.Traffic ＆ Computer，2008，26（3）：60-64.（in Chinese）

［8］ 冯少荣，肖文俊.DBSCAN聚类算法的研究与改进［J］.中国矿业大学学报，2008，27（1）：105-111.FENG Shaorong，XIAO Wenjun.An improved DBSCAN clustering algorithm［J］.Journal of China U-niversity of Mining ＆ Technology，2008，27（1）：105-111.（in Chinese）

［9］ BIRANT D，KUT A.ST-DBSCAN：An algorithm for clustering spatial-temporal data［J］.Data ＆Knowledge Engineering，2007，60：208-221.

［10］ WEN Shun，ZHAO Jieyu，ZHU Shaojun.Hierarchical clustering based on a bayesian harmony measure［J］.PR＆AI，2013，26（12）：1161-1168.

［11］ LU Zhimao，FENG Jinmei.Novel partitional clustering algorithm for large data processing［J］.Systems Engineering and Electronics，2014，36（5）：1010-1015.

［12］ 黄健斌，康剑梅，齐俊杰，等.一种基于同步动力学模型的层次聚类方法［J］.中国科学：信息科学，2013，43（5）：599-610.HUANG Jianbin，KANG Jianmei，QI Junjie，et al.A hierarchical clustering method based on a dynamic synchronization model［J］.Scientia Sinica：Informationis，2013，43（5）：599-610.（in Chinese）

［13］ 王桂芝，王广亮.改进的快速DBSCAN算法［J］.计算机应用，2009，29（9）：2505-2508.WANG Guizhi， WANG Guangliang.Improved fast DBSCAN Algorithm［J］.Journal of Computer Applications，2009，29（9）：2505-2508.（in Chinese）

［14］ BAR-SHALOM Y，TSE E.Tracking in a cluttered environment with probabilistic data association［J］.Automatic，1975，11（9）：451-460.