DBSCAN聚类改进算法与支持向量机结合的道路路锥识别研究

王兆权,陈天炎,王水发,吴宁钰,吴海彬

(1.闽江学院 实验实训管理中心,福建 福州 350108；2.福建船政交通职业学院,福建 福州 350007；3.福州大学机械工程及自动化学院,福建 福州 350108)

1 引 言

路锥是确保道路施工安全重要的路标。当前公路上的路锥取放主要依靠人力,存在着危险性大,效率低的问题。利用自动化设备取代人工来完成路锥收取,成为了未来路面作业的趋势,其首要解决的便是路锥的检测问题。对于路锥的检测识别,最为常用的传感器为可见光摄像机,Lubing Zhou等[1]利用视觉的方式识别成对出现的路锥,并通过路锥轮廓外接矩形计算路锥深度值。王国胤等[2]提出了仅利用颜色特征检测路锥的方法。Chenjian Du[3]在基于颜色识别出路锥后,进一步通过摄像机投影模型完成对路锥的定位。但对于机器视觉,其容易受到背景颜色、光照强度、标定精度等因素的影响,特别是复杂多变的室外环境,将直接削弱视觉识别的鲁棒性[4-5]。

相比之下,激光雷达具有体积小,频率快,精度高的特点,且不易受到光照条件的影响,因此激光雷达在智能导航,障碍规避,目标探测与跟踪有着广泛的应用[6]。Robert A等[7]利用激光雷达来检测与预测移动对象的未来路径,使车辆碰撞系统预警和自主导航。王灿[8]应用激光雷达识别腿部几何信息,并对行人追踪进行了方法研究。杜华臻[9]在此基础上,提取人的腿部特征,用于训练分类器,进一步提升了人腿的识别效果。目前,关于利用雷达识别路锥的文献较少,吕能超等[10]发明了一款路锥自动取放车,其中使用雷达完成对路锥的定位,但对于路锥的识别机制未进行相关说明。HUANG Yong[11]通过单应矩阵将雷达数据与图像数据结合,应用于自动驾驶中的交通锥检测,但当目标间距较近时,两者数据容易相互干扰,造成无法识别,且对于雷达的检测算法并未作出相关阐述。

本文设计了一种基于低成本单线激光雷达的路锥检测识别方法,针对路锥点云特点,改进传统DBSCAN算法,该算法可快速定位出核心点并展开聚类。然后,提取用于表示路锥点簇的特征,进一步利用支持向量机(SVM)分类器训练多组雷达数据。最后,通过网格化搜寻与交叉验证的思想,选取正则项参数与惩罚系数,构建SVM模型,进行路锥识别。经过实验,表明了这种方法的有效性。

2 问题描述

如图1所示,路锥自动取放系统主要由工程车、机械臂、激光雷达三部分组成,激光雷达置于工程车尾部,用于感知车体后侧道路环境。机械臂位于车厢后部,且末端带有夹爪。车后雷达实时采集反射数据,经过识别算法计算,获取路锥方位,进而引导机械臂完成对路锥的抓取。雷达所检测的路锥对象如图2所示,为当前道路工程中最为常见的类型,主要用于交通隔离与警示。

图1 系统构成Fig.1 System composition

图2 交通路锥实物Fig.2 The appearance of road cone

3 获取聚类点簇

3.1 雷达数据预处理

激光雷达分为单线与多线型,多线雷达在检测距离与反射点数据量上优于单线雷达。但多线雷达价格要远高于单线雷达。考虑到雷达的性价比与适用性,本文采用单线型激光雷达作为路锥检测的传感器。

将激光雷达单次扫描的数据记为一帧数据,数据包含了雷达所在平面内所有反射点的二维信息,通常为反射点的在雷达坐标系中的角度值θ与距离值ρ。单线激光雷达数据主要有以下两个特点:

(1)在每个分辨率角度上仅存在最多一组数值。

(2)同一物体的反射数据密度与物体到雷达的距离成反比。

基于此,在获取一帧数据后,按照反射点角度值的递增规律对数据进行排序。如图1所示,雷达所放位置的一侧为车体,另一侧朝向路面,可将车体一侧的反射数据视为噪点,通过角度范围限定,对原始数据进行滤除,得到角度值在J1～J2(J1

3.2 DBSCAN算法

对点云数据的聚类属于无监督问题,聚类分析能够发现数据集自身隐含的内蕴结构信息,最终目的是将相似程度大的数据区域划分为一类[12]。通常将聚类方法分为树聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法[13]。DBSCAN算法是基于密度算法的经典代表,算法能够发现任意形状的点簇,且不易受噪音以及离群点的影响[14]。因此,DBSCAN算法在图像处理、点云数据处理等领域有着诸多应用。Minpts(聚类密度)与ε(聚类半径)为DBSCAN算法的两个重要参数,其主要思路为:

①首先将Q中所有反射点样本标记为Unvisited；

②任取一点qi,qi∈Q。若qi到其ε距离内的其余样本点数不少于Minpts个,则称qi为核心点。将qi以及ε距离内的所有样本点标记为Visited,并隶属于子集Qi(i=1,2,3,…,k),Qi∈Q。

③在剩余的Unvisited样本中任取一点,重复步骤2,继续判断该点是否为核心点。若该核心点ε距离内的样本中存在已隶属于先前形成子集Qj的情况,则将该核心点以及它的ε距离内所有样本包括进Qj；否则,将这些样本隶属于新的子集Ql。

④遍历所有的剩余Unvisited样本,获得Q中所有聚类子集,若qi不属于任何一个子集,则将其视为噪音点。

传统的DBSCAN算法对Unvisited核心点的寻找存在一定随机性,在数据量大时,难以避免效率低下的问题。若能快速寻找出核心点,并对核心点展开聚类,那么对于提升算法的运行效率具有重要意义。这里根据路锥反射点数据特点,提出改进的DBSCAN算法。

如图3所示,路锥所在雷达坐标系xoly内的截面理论上为一段圆弧,可知,所获得的路锥扫描截面总存在一个反射点qk,其距离项在路锥反射点簇中最小,即该点到雷达原点最近。对路锥特征点两侧依次展开,可发现其余反射点的距离逐渐变长。

图3 雷达反射点示意图Fig.3 Radar reflection point diagram

基于此,在一帧数据中,角度连续的三个反射点qk-1,qk,qk+1,若同时满足:

①中间点qk到雷达原点的距离ρk小于其余两点qk-1、qk+1到雷达原点的距离。即ρk<ρk+1,ρk<ρk-1；

②qk-1、qk+1到中间点qk的距离dk-1,k、dk+1,k均小于聚类半径εc。即dk-1,k<εc,dk+1,k<εc,其中:

dk-1,k=

(1)

距离dk+1,k同理。

反射点数据在同一个物体上具有一定角度连续性,因此,改变聚类规则,如下:

从NC中取一点qi,按照qi两侧角度展开搜索,若后搜索到的点与前搜索点的距离小于εc,则将后搜索到的点隶属于子集Qi,直到前后两点距离大于εc；检查其他核心点是否隶属于Qi,若有,应将这一类核心点从NC剔除；继续从NC中取点,重复上述搜索操作,直到遍历NC中所有点。通过简化寻找核心点的过程,可有效地减少计算次数,提升聚类效率。

4 SVM模型识别点簇

4.1 SVM原理

路锥主要在户外使用,考虑到长期在自然环境作用下,路锥表面会出现皱褶变化,并且路锥摆放远近也会对扫描数据造成影响。因此雷达扫描得到的路锥截面形状有时不能被简单地描述为一段圆弧。为了适应聚类点簇所存在的不确定性,这里采用机器学习的方式对聚类点簇进行训练,机器学习中常见的分类器有线性回归、逻辑回归、决策树、朴素贝叶斯、支持向量机(SVM)等算法。SVM算法可将多特征样本数据映射到高维空间,在高维空间搜索最佳分类超平面,使样本数据线性可分,从而解决了低维空间非线性分类问题。此方法非常适合小样本、高维、非线性分类[15]。本文采用SVM对聚类点簇进行识别分类。在二分类问题中,一个具有N个样本的k特征训练集表示为:

T={(X1,y1),(X2,y2)…(XN,yN)}>

(2)

(3)

SVM分类模型如图4所示,上下三角形分别表示负正训练样本,现用一个超平面α将样本分为两部分。

图4 本二分类示例Fig.4 Binary sample classification

超平面方程表达式为:

ωTX+b=0

(4)

所有的样本应满足决策条件:

f(Xi)=yi(ωTXi+b)≥1

(5)

(6)

其中,ξi为松弛变量;c为正则项参数,用于调节最优dmax的宽度,使模型具有一定的容错性。g(ω)为凸函数,根据强对偶定理,将原问题(6)转化为最终优化问题:

(7)

其中,αi为原问题中限制条件的权重因子,通过求解公式(7)获得最优平面方程参数,从而利用(5)判断测试样本的预测类别。为了使函数在样本非线性的情况下仍然适用,这里将低维空间不可分的样本数据X映射到高维空间φ(X),引入核函数:

K(X1,X2)=φ(X1)Tφ(X2)

(8)

式子(5)经过映射后的高维决策函数变为:

(9)

其中,K(X1,X2)为一个计算数值,无需知道核函数的具体映射关系φ(),便可通过输入样本预测标签值,完成二分类任务。

4.2 点簇特征提取

要对聚类后的点簇分类识别,需进一步提取点簇特征。路锥在距雷达不同距离时的反射点疏密程度不同,聚类后点簇Qi的数目leni与核心点距离ρi相关,因此选取leni与ρi作为SVM分类模型的样本特征。

路锥聚类点簇为弧形,弯曲率是衡量弧形点簇形态的另一重要特征。如图5(a)所示,这里采用以下计算公式定义Qi的弯曲率ciri:

(10)

(11)

(12)

其中,arci为Qi中每一个反射点依次用线段连接起来的总长度;dli为Qi的首个反射点与最后一个反射点连接起来的线段长度。ciri越大时表明该点簇的弯曲程度越明显。

环境中存在未知障碍物或者噪声,实际测试时,出现回收后的聚类点簇主体呈现“波动”状,如图5(b),导致点簇不为类弧状却有较大的弯曲率。因此,在这里定义核心点偏离率corei来描述Qi的整体“凸”特性:

图5 点簇特征Fig.5 The characteristic of point cluster

(13)

hi=

(14)

xj=ρjcosθj,(j=1,2,…,leni)

(15)

yj=ρjsinθj,(j=1,2,…,leni)

(16)

其中hi为核心点pi到dli的垂直距离。

以每一个点簇作为SVM模型的样本Xi,提取点簇的[ρi,leni,arci,coreiT作为SVM的4个样本特征[xi,1,xi,2,xi,3,xi,4T。

5 实验与分析

为验证本文路锥识别算法的有效性,搭建了如图6所示实验平台,平台由雷达、上位机、轮式载具构成。其中雷达为SLAMTEC公司生产的RPLIDAR-A3单线型激光雷达,其测量距离为0.2～25 m,角度范围为0～360°。上位机系统为win10 64 bit,采用python3编写算法程序。雷达模块放置在离地面 190 mm位置,将εc设为169 mm。

图6 实验平台Fig.6 Experimental platform

5.1 DBSCAN改进算法实验

为了充分展示算法有效性,移动载具在不同复杂环境下采集数据,设置传统DBSCAN算法的聚类密度为3,聚类半径亦为εc。雷达扫描面内有围挡、电动车、汽车、货车、绿化带、墙壁等干扰物,选取其中4个场景,如图7所示原始雷达反射点数据与算法改进前后的扫描效果,其中图(a)～(d)为场景1,图(e)～(h)为场景2,图(i)～(l)为场景3,图(m)～(p)为场景4。图8(a)统计了4个场景下聚类算法改进前后的点簇数量,可以看到,在不影响路锥点云聚类前提下,改进后算法在场景1中多滤除了8个点簇,场景3中更是多滤除了12个点簇,改进后的算法比传统算法多过滤掉20 %～33 %的噪声点簇,聚类后的点簇更具有针对性。

图7 点簇聚类效果图Fig.7 The effect of point clustering algorithm

进一步对算法改进前后的计算耗时进行比较,如图8(b)所示,传统算法对于场景1到场景4的聚类耗时均在37 ms以上,存在着计算量巨大、耗时长的问题,且对于越复杂的环境,算法消耗时间越大。改进后的聚类算法计算次数减少,总体上计算时间控制在18 ms内,节约了50 %以上的计算时间,在点簇数目、实时性上要远优于传统算法。

图8 聚类算法效果对比Fig.8 The contrast of the different clustering algorithm

5.2 SVM分类实验

改变路锥的个数与距离、障碍物的类型与位置,采集到80帧不同实验场景中的雷达扫描数据,经DBSCAN改进算法聚类后提取特征。总共得到2005组特征向量,部分结果如表1所示。其中属于路锥的特征向量为246个,标签值记为1,其余样本标签值为0。

表1 部分样本特征向量Tab.1 Some sample eigenvectors

前文所述,利用核函数将样本数据映射到高维空间能够有效地解决样本低维不可分的问题,在这里选用径向基函数(高斯核函数)作为核函数,高斯核函数可近似地将样本数据映射到无限高维,理论上可拟合任何非线性样本,其表达式如下:

K(X1,X2)=e-r‖X1-X2‖2

(17)

其中r为核函数的参数,规定r>0。r过大容易造成分类器过拟合,降低泛化能力。r过小导致平滑效应太大,造成欠拟合。在SVM分类模型中,核函数参数r与式(6)中的正则项参数c的设置直接影响分类器结果的准确率,为了选取较好的(c,r)参数组合,采取网格搜索法[16],预先给定(c,r)的数值范围以及步长,假设在c的数值范围内共有M个取值,在r的数值范围内共有N个取值,那么对于(c,r)共有M×N种参数组合,将所有参数组合进行交叉验证[17],选取准确率最高的一组作为SVM模型参数。这里给定lgc∈[-2,9],lgr∈[-9,2],步长为1。交叉验证折数为3。SVM参数的搜索过程如图9所示,图中高度值代表(c,r)组合下的模型准确率。可以看到,当参数为lgc=6,lgr=-5时准确率最高,为97.8 %,因此设置其为模型参数。

图9 网格化搜索参数Fig.9 Grid-based search parameters

利用训练好的SVM模型进行路锥识别实验。雷达采集数据,当累计输入100组样本时,计算一次识别准确率,随机进行6次准确率测试,结果如图10所示。其中有5次的准确率在95 %以上,准确率最低不小于93 %,表明模型具有较高的可靠性,能够较好地识别出路锥所在点簇。

图10 SVM模型测试结果Fig.10 The result of the SVM test

6 结 论

针对道路路锥识别问题,本文提出了一种基于激光雷达数据与机器学习相结合的路锥识别方法。通过对传统DBSCAN聚类算法进行改进,设计了一种快速搜索核心点的聚类方法,以获取当前帧数据的路锥潜在点簇；接着,提取点簇特征作为样本向量；最后,通过网格化搜索法选取SVM参数,并将训练后得到的SVM分类模型用于路锥点簇识别。

实验结果表明,改进的DBSCAN算法在计算效率上有了较大的提升,在不影响聚类效果的前提下能迅速地获取路锥潜在点簇。所搭建SVM模型,在经过大量样本训练后,能够较好地识别路锥点簇,具备一定实用价值。