DBSCAN聚類改進算法與支持向量機結合的道路路錐識別研究

王兆權,陳天炎,王水發(fā),吳寧鈺,吳海彬

(1.閩江學院 實驗實訓管理中心,福建 福州 350108；2.福建船政交通職業(yè)學院,福建 福州 350007；3.福州大學機械工程及自動化學院,福建 福州 350108)

1 引 言

路錐是確保道路施工安全重要的路標。當前公路上的路錐取放主要依靠人力,存在著危險性大,效率低的問題。利用自動化設備取代人工來完成路錐收取,成為了未來路面作業(yè)的趨勢,其首要解決的便是路錐的檢測問題。對于路錐的檢測識別,最為常用的傳感器為可見光攝像機,Lubing Zhou等[1]利用視覺的方式識別成對出現(xiàn)的路錐,并通過路錐輪廓外接矩形計算路錐深度值。王國胤等[2]提出了僅利用顏色特征檢測路錐的方法。Chenjian Du[3]在基于顏色識別出路錐后,進一步通過攝像機投影模型完成對路錐的定位。但對于機器視覺,其容易受到背景顏色、光照強度、標定精度等因素的影響,特別是復雜多變的室外環(huán)境,將直接削弱視覺識別的魯棒性[4-5]。

相比之下,激光雷達具有體積小,頻率快,精度高的特點,且不易受到光照條件的影響,因此激光雷達在智能導航,障礙規(guī)避,目標探測與跟蹤有著廣泛的應用[6]。Robert A等[7]利用激光雷達來檢測與預測移動對象的未來路徑,使車輛碰撞系統(tǒng)預警和自主導航。王燦[8]應用激光雷達識別腿部幾何信息,并對行人追蹤進行了方法研究。杜華臻[9]在此基礎上,提取人的腿部特征,用于訓練分類器,進一步提升了人腿的識別效果。目前,關于利用雷達識別路錐的文獻較少,呂能超等[10]發(fā)明了一款路錐自動取放車,其中使用雷達完成對路錐的定位,但對于路錐的識別機制未進行相關說明。HUANG Yong[11]通過單應矩陣將雷達數(shù)據與圖像數(shù)據結合,應用于自動駕駛中的交通錐檢測,但當目標間距較近時,兩者數(shù)據容易相互干擾,造成無法識別,且對于雷達的檢測算法并未作出相關闡述。

本文設計了一種基于低成本單線激光雷達的路錐檢測識別方法,針對路錐點云特點,改進傳統(tǒng)DBSCAN算法,該算法可快速定位出核心點并展開聚類。然后,提取用于表示路錐點簇的特征,進一步利用支持向量機(SVM)分類器訓練多組雷達數(shù)據。最后,通過網格化搜尋與交叉驗證的思想,選取正則項參數(shù)與懲罰系數(shù),構建SVM模型,進行路錐識別。經過實驗,表明了這種方法的有效性。

2 問題描述

如圖1所示,路錐自動取放系統(tǒng)主要由工程車、機械臂、激光雷達三部分組成,激光雷達置于工程車尾部,用于感知車體后側道路環(huán)境。機械臂位于車廂后部,且末端帶有夾爪。車后雷達實時采集反射數(shù)據,經過識別算法計算,獲取路錐方位,進而引導機械臂完成對路錐的抓取。雷達所檢測的路錐對象如圖2所示,為當前道路工程中最為常見的類型,主要用于交通隔離與警示。

圖1 系統(tǒng)構成Fig.1 System composition

圖2 交通路錐實物Fig.2 The appearance of road cone

3 獲取聚類點簇

3.1 雷達數(shù)據預處理

激光雷達分為單線與多線型,多線雷達在檢測距離與反射點數(shù)據量上優(yōu)于單線雷達。但多線雷達價格要遠高于單線雷達?？紤]到雷達的性價比與適用性,本文采用單線型激光雷達作為路錐檢測的傳感器。

將激光雷達單次掃描的數(shù)據記為一幀數(shù)據,數(shù)據包含了雷達所在平面內所有反射點的二維信息,通常為反射點的在雷達坐標系中的角度值θ與距離值ρ。單線激光雷達數(shù)據主要有以下兩個特點:

(1)在每個分辨率角度上僅存在最多一組數(shù)值。

(2)同一物體的反射數(shù)據密度與物體到雷達的距離成反比。

基于此,在獲取一幀數(shù)據后,按照反射點角度值的遞增規(guī)律對數(shù)據進行排序。如圖1所示,雷達所放位置的一側為車體,另一側朝向路面,可將車體一側的反射數(shù)據視為噪點,通過角度范圍限定,對原始數(shù)據進行濾除,得到角度值在J1～J2(J1

3.2 DBSCAN算法

對點云數(shù)據的聚類屬于無監(jiān)督問題,聚類分析能夠發(fā)現(xiàn)數(shù)據集自身隱含的內蘊結構信息,最終目的是將相似程度大的數(shù)據區(qū)域劃分為一類[12]。通常將聚類方法分為樹聚類算法、劃分式聚類算法、基于密度和網格的聚類算法和其他聚類算法[13]。DBSCAN算法是基于密度算法的經典代表,算法能夠發(fā)現(xiàn)任意形狀的點簇,且不易受噪音以及離群點的影響[14]。因此,DBSCAN算法在圖像處理、點云數(shù)據處理等領域有著諸多應用。Minpts(聚類密度)與ε(聚類半徑)為DBSCAN算法的兩個重要參數(shù),其主要思路為:

①首先將Q中所有反射點樣本標記為Unvisited；

②任取一點qi,qi∈Q。若qi到其ε距離內的其余樣本點數(shù)不少于Minpts個,則稱qi為核心點。將qi以及ε距離內的所有樣本點標記為Visited,并隸屬于子集Qi(i=1,2,3,…,k),Qi∈Q。

③在剩余的Unvisited樣本中任取一點,重復步驟2,繼續(xù)判斷該點是否為核心點。若該核心點ε距離內的樣本中存在已隸屬于先前形成子集Qj的情況,則將該核心點以及它的ε距離內所有樣本包括進Qj；否則,將這些樣本隸屬于新的子集Ql。

④遍歷所有的剩余Unvisited樣本,獲得Q中所有聚類子集,若qi不屬于任何一個子集,則將其視為噪音點。

傳統(tǒng)的DBSCAN算法對Unvisited核心點的尋找存在一定隨機性,在數(shù)據量大時,難以避免效率低下的問題。若能快速尋找出核心點,并對核心點展開聚類,那么對于提升算法的運行效率具有重要意義。這里根據路錐反射點數(shù)據特點,提出改進的DBSCAN算法。

如圖3所示,路錐所在雷達坐標系xoly內的截面理論上為一段圓弧,可知,所獲得的路錐掃描截面總存在一個反射點qk,其距離項在路錐反射點簇中最小,即該點到雷達原點最近。對路錐特征點兩側依次展開,可發(fā)現(xiàn)其余反射點的距離逐漸變長。

圖3 雷達反射點示意圖Fig.3 Radar reflection point diagram

基于此,在一幀數(shù)據中,角度連續(xù)的三個反射點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同理。

反射點數(shù)據在同一個物體上具有一定角度連續(xù)性,因此,改變聚類規(guī)則,如下:

從NC中取一點qi,按照qi兩側角度展開搜索,若后搜索到的點與前搜索點的距離小于εc,則將后搜索到的點隸屬于子集Qi,直到前后兩點距離大于εc；檢查其他核心點是否隸屬于Qi,若有,應將這一類核心點從NC剔除；繼續(xù)從NC中取點,重復上述搜索操作,直到遍歷NC中所有點。通過簡化尋找核心點的過程,可有效地減少計算次數(shù),提升聚類效率。

4 SVM模型識別點簇

4.1 SVM原理

路錐主要在戶外使用,考慮到長期在自然環(huán)境作用下,路錐表面會出現(xiàn)皺褶變化,并且路錐擺放遠近也會對掃描數(shù)據造成影響。因此雷達掃描得到的路錐截面形狀有時不能被簡單地描述為一段圓弧。為了適應聚類點簇所存在的不確定性,這里采用機器學習的方式對聚類點簇進行訓練,機器學習中常見的分類器有線性回歸、邏輯回歸、決策樹、樸素貝葉斯、支持向量機(SVM)等算法。SVM算法可將多特征樣本數(shù)據映射到高維空間,在高維空間搜索最佳分類超平面,使樣本數(shù)據線性可分,從而解決了低維空間非線性分類問題。此方法非常適合小樣本、高維、非線性分類[15]。本文采用SVM對聚類點簇進行識別分類。在二分類問題中,一個具有N個樣本的k特征訓練集表示為:

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

(2)

(3)

SVM分類模型如圖4所示,上下三角形分別表示負正訓練樣本,現(xiàn)用一個超平面α將樣本分為兩部分。

圖4 本二分類示例Fig.4 Binary sample classification

超平面方程表達式為:

ωTX+b=0

(4)

所有的樣本應滿足決策條件:

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

(5)

(6)

其中,ξi為松弛變量;c為正則項參數(shù),用于調節(jié)最優(yōu)dmax的寬度,使模型具有一定的容錯性。g(ω)為凸函數(shù),根據強對偶定理,將原問題(6)轉化為最終優(yōu)化問題:

(7)

其中,αi為原問題中限制條件的權重因子,通過求解公式(7)獲得最優(yōu)平面方程參數(shù),從而利用(5)判斷測試樣本的預測類別。為了使函數(shù)在樣本非線性的情況下仍然適用,這里將低維空間不可分的樣本數(shù)據X映射到高維空間φ(X),引入核函數(shù):

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

(8)

式子(5)經過映射后的高維決策函數(shù)變?yōu)?

(9)

其中,K(X1,X2)為一個計算數(shù)值,無需知道核函數(shù)的具體映射關系φ(),便可通過輸入樣本預測標簽值,完成二分類任務。

4.2 點簇特征提取

要對聚類后的點簇分類識別,需進一步提取點簇特征。路錐在距雷達不同距離時的反射點疏密程度不同,聚類后點簇Qi的數(shù)目leni與核心點距離ρi相關,因此選取leni與ρi作為SVM分類模型的樣本特征。

路錐聚類點簇為弧形,彎曲率是衡量弧形點簇形態(tài)的另一重要特征。如圖5(a)所示,這里采用以下計算公式定義Qi的彎曲率ciri:

(10)

(11)

(12)

其中,arci為Qi中每一個反射點依次用線段連接起來的總長度;dli為Qi的首個反射點與最后一個反射點連接起來的線段長度。ciri越大時表明該點簇的彎曲程度越明顯。

環(huán)境中存在未知障礙物或者噪聲,實際測試時,出現(xiàn)回收后的聚類點簇主體呈現(xiàn)“波動”狀,如圖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°。上位機系統(tǒng)為win10 64 bit,采用python3編寫算法程序。雷達模塊放置在離地面 190 mm位置,將εc設為169 mm。

圖6 實驗平臺Fig.6 Experimental platform

5.1 DBSCAN改進算法實驗

為了充分展示算法有效性,移動載具在不同復雜環(huán)境下采集數(shù)據,設置傳統(tǒng)DBSCAN算法的聚類密度為3,聚類半徑亦為εc。雷達掃描面內有圍擋、電動車、汽車、貨車、綠化帶、墻壁等干擾物,選取其中4個場景,如圖7所示原始雷達反射點數(shù)據與算法改進前后的掃描效果,其中圖(a)～(d)為場景1,圖(e)～(h)為場景2,圖(i)～(l)為場景3,圖(m)～(p)為場景4。圖8(a)統(tǒng)計了4個場景下聚類算法改進前后的點簇數(shù)量,可以看到,在不影響路錐點云聚類前提下,改進后算法在場景1中多濾除了8個點簇,場景3中更是多濾除了12個點簇,改進后的算法比傳統(tǒng)算法多過濾掉20 %～33 %的噪聲點簇,聚類后的點簇更具有針對性。

圖7 點簇聚類效果圖Fig.7 The effect of point clustering algorithm

進一步對算法改進前后的計算耗時進行比較,如圖8(b)所示,傳統(tǒng)算法對于場景1到場景4的聚類耗時均在37 ms以上,存在著計算量巨大、耗時長的問題,且對于越復雜的環(huán)境,算法消耗時間越大。改進后的聚類算法計算次數(shù)減少,總體上計算時間控制在18 ms內,節(jié)約了50 %以上的計算時間,在點簇數(shù)目、實時性上要遠優(yōu)于傳統(tǒng)算法。

圖8 聚類算法效果對比Fig.8 The contrast of the different clustering algorithm

5.2 SVM分類實驗

改變路錐的個數(shù)與距離、障礙物的類型與位置,采集到80幀不同實驗場景中的雷達掃描數(shù)據,經DBSCAN改進算法聚類后提取特征?？偣驳玫?005組特征向量,部分結果如表1所示。其中屬于路錐的特征向量為246個,標簽值記為1,其余樣本標簽值為0。

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

前文所述,利用核函數(shù)將樣本數(shù)據映射到高維空間能夠有效地解決樣本低維不可分的問題,在這里選用徑向基函數(shù)(高斯核函數(shù))作為核函數(shù),高斯核函數(shù)可近似地將樣本數(shù)據映射到無限高維,理論上可擬合任何非線性樣本,其表達式如下:

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

(17)

其中r為核函數(shù)的參數(shù),規(guī)定r>0。r過大容易造成分類器過擬合,降低泛化能力。r過小導致平滑效應太大,造成欠擬合。在SVM分類模型中,核函數(shù)參數(shù)r與式(6)中的正則項參數(shù)c的設置直接影響分類器結果的準確率,為了選取較好的(c,r)參數(shù)組合,采取網格搜索法[16],預先給定(c,r)的數(shù)值范圍以及步長,假設在c的數(shù)值范圍內共有M個取值,在r的數(shù)值范圍內共有N個取值,那么對于(c,r)共有M×N種參數(shù)組合,將所有參數(shù)組合進行交叉驗證[17],選取準確率最高的一組作為SVM模型參數(shù)。這里給定lgc∈[-2,9],lgr∈[-9,2],步長為1。交叉驗證折數(shù)為3。SVM參數(shù)的搜索過程如圖9所示,圖中高度值代表(c,r)組合下的模型準確率?？梢钥吹?當參數(shù)為lgc=6,lgr=-5時準確率最高,為97.8 %,因此設置其為模型參數(shù)。

圖9 網格化搜索參數(shù)Fig.9 Grid-based search parameters

利用訓練好的SVM模型進行路錐識別實驗。雷達采集數(shù)據,當累計輸入100組樣本時,計算一次識別準確率,隨機進行6次準確率測試,結果如圖10所示。其中有5次的準確率在95 %以上,準確率最低不小于93 %,表明模型具有較高的可靠性,能夠較好地識別出路錐所在點簇。

圖10 SVM模型測試結果Fig.10 The result of the SVM test

6 結 論

針對道路路錐識別問題,本文提出了一種基于激光雷達數(shù)據與機器學習相結合的路錐識別方法。通過對傳統(tǒng)DBSCAN聚類算法進行改進,設計了一種快速搜索核心點的聚類方法,以獲取當前幀數(shù)據的路錐潛在點簇；接著,提取點簇特征作為樣本向量；最后,通過網格化搜索法選取SVM參數(shù),并將訓練后得到的SVM分類模型用于路錐點簇識別。

實驗結果表明,改進的DBSCAN算法在計算效率上有了較大的提升,在不影響聚類效果的前提下能迅速地獲取路錐潛在點簇。所搭建SVM模型,在經過大量樣本訓練后,能夠較好地識別路錐點簇,具備一定實用價值。