基于激光雷達(dá)道路可通行區(qū)域的檢測與提取

鄒 斌，王 磊

（武漢理工大學(xué) 現(xiàn)代汽車零部件技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室 汽車零部件技術(shù)湖北省協(xié)同創(chuàng)新中心，武漢 430070）

無人駕駛車輛是利用車載傳感系統(tǒng)來感知車輛周圍環(huán)境，自行規(guī)劃行車路線控制車輛成功抵達(dá)目的地的智能車[1]。無人駕駛車輛一般裝有激光雷達(dá)和攝像頭作為車載傳感器，用于檢測道路區(qū)域和障礙區(qū)域。由于視覺傳感器受環(huán)境因素影響較大，而單線激光雷達(dá)的探測范圍十分有限，因此三維激光雷達(dá)在智能駕駛中得到了廣泛的應(yīng)用。目前的三維激光雷達(dá)處理算法主要是基于柵格地圖的分割算法和基于圖的地面檢測兩大類[2-5]。相比柵格類的算法，基于圖的分割算法精度更高，但容易受到噪點(diǎn)的干擾，算法魯棒性差。本文提出一種新的聚類方法，利用改進(jìn)的K-means算法獲取最優(yōu)聚類點(diǎn)集，基于高度特征和密特征分割雷達(dá)掃描單線，提取可通行區(qū)域。算法在滿足運(yùn)行速度實(shí)現(xiàn)實(shí)時(shí)性的同時(shí)，也能保證很高精度和穩(wěn)定性。

1 算法概述

1.1 數(shù)據(jù)預(yù)處理

本文試驗(yàn)平臺(tái)為智能車平臺(tái)，平臺(tái)如圖1所示，數(shù)據(jù)來自Velodyne16線激光雷達(dá)，安裝于車頂。雷達(dá)垂直掃描角度為-15°～15°，掃描精度為 2°。雷達(dá)在垂直掃描范圍內(nèi)發(fā)射16根激光線，在水平方向上掃描360°獲取周邊環(huán)境信息，水平分辨率為0.1°～0.4°。雷達(dá)以 10 Hz頻率采樣，每幀約采集 2萬個(gè)點(diǎn)，某幀實(shí)際場景如圖2所示，對(duì)應(yīng)的實(shí)際路況如圖3所示。

圖1 智能車平臺(tái)Fig.1 Smart car platform

圖2 數(shù)據(jù)點(diǎn)集在地面的投影Fig.2 Projection of data points on the ground

圖3 實(shí)際路況Fig.3 Actual road conditions

Velodyne16線三維激光雷達(dá)獲取的數(shù)據(jù)具有不同的組織結(jié)構(gòu)和先后順序，為了便于處理，將點(diǎn)從雷達(dá)坐標(biāo)系轉(zhuǎn)化成車輛坐標(biāo)系。由于安裝激光雷達(dá)不能保證絕對(duì)水平，掃描傾角會(huì)產(chǎn)生一定誤差，本文對(duì)此進(jìn)行修正，使得點(diǎn)投影角度和原始數(shù)據(jù)掃描角度達(dá)到統(tǒng)一。

1.2 算法流程

本文取前方為研究對(duì)象，由于雷達(dá)精度受限，距離越遠(yuǎn)，單線間距越大。因此，本文選取車輛前方20 m和左右側(cè)各10 m范圍作為研究區(qū)域。規(guī)定激光雷達(dá)所在的點(diǎn)為（0，0），車輛前方為x軸正方向，右側(cè)為y軸正方向。

本文只研究路面情況，但雷達(dá)掃描范圍過大會(huì)產(chǎn)生較多噪點(diǎn)比如路面周圍樹木枝葉。因此，將高度大于3 m的點(diǎn)濾去，在將剩余的點(diǎn)投影到XY平面中，效果如圖4所示。

圖4 過濾后的投影效果Fig.4 Filtered rendering

圖中可以看出，障礙物區(qū)域和可通行區(qū)域具有明顯差異，在兩個(gè)區(qū)域交界處會(huì)出現(xiàn)折角或者斷開狀態(tài)。將圖4進(jìn)行人工標(biāo)記如圖5所示。為了得到可通行區(qū)域，本文首先提取激光雷達(dá)掃描單線。據(jù)此，提出基于掃描單線的聚類算法，流程如圖6所示。

圖5 人工標(biāo)記圖Fig.5 Manual marking

圖6 算法流程Fig.6 Algorithm flow chart

1.3 掃描單線提取

計(jì)算出每個(gè)數(shù)據(jù)對(duì)應(yīng)的掃描角度：

式中：θ為數(shù)據(jù)點(diǎn)的仰角弧度。

本文將角度閾值設(shè)定為0.5°，在此范圍下，提取出數(shù)據(jù)認(rèn)定為同一根單線數(shù)據(jù)。圖4中數(shù)據(jù)經(jīng)過處理后提取出的單線如圖7所示。

圖7 激光雷達(dá)掃描單線Fig.7 Laser rader scanning single line

2 道路通行區(qū)域提取

2.1 改進(jìn)K-means算法獲取最優(yōu)聚類集合

K-means算法[6]是輸入聚類個(gè)數(shù)，以及包含n個(gè)對(duì)象的數(shù)據(jù)庫，輸出滿足方差最小標(biāo)準(zhǔn)k個(gè)聚類的一種算法。該算法對(duì)大數(shù)據(jù)有較高效率并可收縮、實(shí)現(xiàn)過程快速簡單，但該算法聚類結(jié)果易受噪聲數(shù)據(jù)影響，而且算法只能保證收斂到局部最優(yōu)結(jié)果，導(dǎo)致對(duì)最初選擇點(diǎn)非常敏感。本文針對(duì)這個(gè)問題提出一種對(duì)初始聚類中心進(jìn)行改進(jìn)的算法。算法實(shí)現(xiàn)的具體流程為

（1）對(duì)于數(shù)據(jù)集 χ＝｛x1，…，xn｝，利用 AIC 準(zhǔn)則[7]獲取最優(yōu)聚類數(shù)目：

式中：k為聚類數(shù)目；n為觀察數(shù)；SSR為數(shù)據(jù)集殘差平方和。增加自由參數(shù)可提高擬合的優(yōu)良性，為避免出現(xiàn)過度擬合，優(yōu)先考慮AIC最小的的模型，據(jù)此得到最優(yōu)聚類數(shù)目k。

（2）從數(shù)據(jù)集中隨機(jī)選取一個(gè)樣本作為初始聚類中心c；

（3）首先計(jì)算每個(gè)樣本與當(dāng)前已有聚類中心之間的距離：

接著計(jì)算每個(gè)樣本被選為下一個(gè)聚類中心的概率：

式中：D（x）為與最近聚類中心的距離。

式中：xi為樣本總體；Cj為聚類中心；Ui為樣本 xi與k個(gè)類中距離最近的類，且1≤Ui≤k。

（6）重新計(jì)算有變化聚類的中心：

最后按照輪盤法選擇下一個(gè)聚類中心，即概率大的聚類中心被選擇的概率大；

（4）重復(fù)第2步直到選擇出共k個(gè)聚類中心C=｛C1，C2，…，Ck｝；

（5）針對(duì)數(shù)據(jù)集中每個(gè)樣本xi，計(jì)算每個(gè)樣本與這些聚類中心的距離并將其分到距離最小的聚類中心所對(duì)應(yīng)的類中：

式中：ti為變化后類別的質(zhì)心。

（7）計(jì)算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足函數(shù)收斂，則算法終止，如果不滿足則返回步驟5。對(duì)于函數(shù)收斂，本文定義畸變函數(shù)：

式中：J函數(shù)為每個(gè)樣本點(diǎn)到其質(zhì)心的距離平方和。

算法目標(biāo)將J值調(diào)整到最小，由于已經(jīng)對(duì)聚類中心進(jìn)行優(yōu)化，避免出現(xiàn)局部最優(yōu)的結(jié)果，保證了取得的最小值是全局最小值，獲得的聚類為全局最優(yōu)類別。

2.2 算法檢驗(yàn)

2.2.1 檢測數(shù)據(jù)集

為驗(yàn)證算法的可靠性，本文采用人工和真實(shí)據(jù)集來檢驗(yàn)算法獲取最優(yōu)聚類集合的效果。測試數(shù)據(jù)集包括UCI機(jī)器數(shù)據(jù)庫數(shù)據(jù)集Iris和fisheriris和三個(gè)服從高斯分布的數(shù)據(jù)集A1，A2，A3，數(shù)據(jù)集特征如表1所示，高斯分布數(shù)據(jù)集如圖8～圖10所示。

2.2.2 檢測結(jié)果分析

為驗(yàn)證本文算法的可行性和準(zhǔn)確性，將本文算法和K-means算法在上述數(shù)據(jù)集分別進(jìn)行多次獨(dú)立重復(fù)試驗(yàn)，平均聚類精度如表2所示。

表1 測試數(shù)據(jù)特征描述Tab.1 Test data feature description

圖8 服從高斯分布的人造數(shù)據(jù)集A1Fig.8 Artificial data set A1 which obeys the gauussian distribution

圖9 服從高斯分布的人造數(shù)據(jù)集A2Fig.9 Artificial data set A2 which obeys the gauussian distribution

圖10 服從高斯分布的人造數(shù)據(jù)集A3Fig.10 Artificial data set A3 which obeys the gauussian distribution

表2 算法平均聚類結(jié)果Tab.2 Algorithm average clustering results

從仿真結(jié)果來看，本文算法較傳統(tǒng)K-means算法有較大改進(jìn)，在尋找最佳聚類數(shù)目方面，可以得到最優(yōu)聚類數(shù)目；在準(zhǔn)確率方面，可以精確對(duì)數(shù)據(jù)集進(jìn)行劃分，獲取最優(yōu)聚類點(diǎn)集。

表3是以fisheriris數(shù)據(jù)集為例，兩種算法初始聚類中心和最終聚類中心之間的關(guān)系。

表3 兩種算法中心之間的關(guān)系Tab.3 Relationship between the two algorithm center

2.2.3 單線數(shù)據(jù)運(yùn)行結(jié)果

基于改進(jìn)K-means算法對(duì)已經(jīng)提取出的雷達(dá)掃描單線數(shù)據(jù)進(jìn)行聚類處理，得到的結(jié)果如圖11所示。

圖11 改進(jìn)K-means算法聚類結(jié)果Fig.11 Improved K-means algorithm clustering results

2.3 利用高度特征提取障礙物

上節(jié)只是分割結(jié)果，要達(dá)到提取可通行區(qū)域的目的還要對(duì)障礙進(jìn)行檢測，從聚得類別中挑出屬于障礙的類。本文基于高度特征對(duì)凸障礙進(jìn)行提取[8]。

首先對(duì)雷達(dá)單線數(shù)據(jù)進(jìn)行屬性統(tǒng)計(jì)，計(jì)算出每個(gè)類別的高度均值和方差：

相對(duì)于地面，障礙物所屬類別應(yīng)該具有一定的高度，而且障礙物的數(shù)據(jù)點(diǎn)集高度方差較小。障礙物判斷準(zhǔn)則如圖12所示。

圖12 障礙物判定準(zhǔn)則Fig.12 Obstacle determination criteria

本文將障礙物的最小高度取為30 cm。類別中高度均值大于這個(gè)值的點(diǎn)集判定為障礙物，判定結(jié)果如圖13所示。

圖13 障礙物點(diǎn)集Fig.13 Obstacle point set

2.4 利用密度特征提取路沿

DBSCAN算法是基于密度的聚類算法，能夠把具有特定密度的區(qū)域劃分為簇并可在噪聲的數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。算法定義Eps和Minpts兩個(gè)參數(shù)，根據(jù)DBSCAN算法的定義與引理[9]可知，每一個(gè)簇都是密度相連點(diǎn)的最大集合，由核心點(diǎn)唯一確定。

DBSCAN算法的聚類思想是掃描整個(gè)數(shù)據(jù)集，任意選擇點(diǎn)p開始，向周圍查找所有密度可達(dá)的點(diǎn)。若p為核心點(diǎn)，則在其半徑為Eps的領(lǐng)域內(nèi)，所有點(diǎn)與p屬同一簇，再通過查找與候選點(diǎn)密度可達(dá)的點(diǎn)不斷擴(kuò)充簇，直至形成一個(gè)完整的簇；若p不為核心點(diǎn)，則p被標(biāo)注成噪點(diǎn)。重復(fù)上述過程，直至所有點(diǎn)都被聚類成簇或者標(biāo)注為噪點(diǎn)。

基于激光雷達(dá)掃描到路沿地段產(chǎn)生的數(shù)據(jù)點(diǎn)的密度會(huì)大于平常地面的特征，運(yùn)行DBSCAN算法可以將路沿識(shí)別出來。圖14為算法對(duì)某一雷達(dá)掃描單線的聚類擬合結(jié)果。

圖14 掃描單線聚類擬合結(jié)果Fig.14 Results of scanning single-line cluster fitting

2.5 道路分割提取結(jié)果

對(duì)于已經(jīng)提取出來的屬于可通行區(qū)域的點(diǎn)集利用最小二乘法[10]進(jìn)行多項(xiàng)式曲線擬合[11]，結(jié)果如圖15所示。

圖15 可通行道路區(qū)域Fig.15 Passable road area

經(jīng)過多幀檢測，本文提供算法可在復(fù)雜路面實(shí)時(shí)有效地提取可通行區(qū)域。校園道路停放多輛汽車的識(shí)別結(jié)果如圖16所示，校園道路上出現(xiàn)行人的識(shí)別結(jié)果如圖17所示。

3 試驗(yàn)結(jié)果

本文使用的智能車試驗(yàn)平臺(tái)，激光雷達(dá)安裝于智能車頂部。在Ubuntu系統(tǒng)安裝機(jī)器人操作系統(tǒng)；用C++編寫傳感器節(jié)點(diǎn)，接收激光雷達(dá)原始數(shù)據(jù)；用Python編程數(shù)據(jù)節(jié)點(diǎn)，處理傳感器輸入的距離數(shù)組，用道路提取算法進(jìn)行運(yùn)算。在校園道路測量1000幀，道路提取算法平均每幀耗時(shí)55 ms，單幀最大耗時(shí)80 ms，最小耗時(shí)42 ms，低于激光雷達(dá)工作周期100 ms，如圖18所示，擁有很好的實(shí)時(shí)性。

圖16 算法識(shí)別結(jié)果ⅠFig.16 I algorithm identification results

圖17 算法識(shí)別結(jié)果ⅡFig.17Ⅱalgorithm identification results

圖18 耗時(shí)周期Fig.18 Time-consuming cycle

為了驗(yàn)證地面區(qū)域判斷的可靠性，連續(xù)運(yùn)行100幀數(shù)據(jù)，計(jì)算分割提取的準(zhǔn)確率，通過R（準(zhǔn)確率）對(duì)算法的結(jié)果與人工標(biāo)記的真值進(jìn)行量化對(duì)比：

式中：NA為每幀有效掃描單線數(shù)目；NTA為每條單線被正確標(biāo)記的地面點(diǎn)數(shù)目；NTB為每條單線被誤判為每幀地面點(diǎn)的障礙點(diǎn)數(shù)目；NTC為每條單線誤判為障礙點(diǎn)的地面點(diǎn)數(shù)目；NTE為每條單線被正確標(biāo)記的障礙點(diǎn)數(shù)目；ei為修正系數(shù)。

對(duì)100幀進(jìn)行準(zhǔn)確率計(jì)算，得到準(zhǔn)確率平均值為94.17%，如圖19所示，道路的提取效果滿足后續(xù)規(guī)劃要求。

圖19 準(zhǔn)確率Fig.19 Accuracy rate

4 結(jié)語

本文提出了一種基于三維激光雷達(dá)的道路分割提取的算法，利用改進(jìn)K-means算法對(duì)掃描單線進(jìn)行聚類，結(jié)合高度特征和密度特征提取可通行區(qū)域。試驗(yàn)結(jié)果表明，本文算法具有較高魯棒性，可以實(shí)時(shí)精確地為車輛提供路面區(qū)域信息。在校園內(nèi)經(jīng)過實(shí)車測試，無人駕駛車輛能在道路上自主行駛，具有良好的穩(wěn)定性。但由于算法需要根據(jù)路沿信息提取路面區(qū)域，對(duì)于無路沿的道路存在局限性，需要結(jié)合其它傳感器信息改進(jìn)算法。

[1]陳慧巖.無人駕駛汽車概論[M].北京：北京理工大學(xué)出版社，2014.

[2]LIU J，LIANG H W，WANG Z L，et al.A framework for applying point clouds grabbed by multi-beam LIDAR in perceiving the driving environment[J].Sensors，2015，15（9）：21931-21956.

[3]GUO C，SATO W，HAN L，et al.Graph-baswd 2D road represention of 3Dpoint clouds for intelligent vehicles[C]//Intelligent Vehicles Symposium（IV）.Detroit：IEEE，2011：715-721.

[4]MONTEMERLO M，BECHER J，BHAT S，et al.Junior：The Stanford entry in the urban challenge[J].Journal of Field Robotics，2008，25（9）：569-597.

[5]DOUILLARDB，UNDERWOOD J，KUNTZN，etal.Onthe segmentation of 3D LIDAR point clouds[C]//International Conference on Robotics and Automation（ICRA）.Shanghai：IEEE，2011：2798-2805.

[6]蔣慶豐.K-Means聚類算法研究及圖形演示的實(shí)現(xiàn)[J].信息技術(shù)，2010，10（3）：22-25.

[7]A kaike.A Bayesian analysis of the minimum AIC procedure[J].ANN.Inst.Statist.Math.30（1978）.

[8]萬忠濤.基于激光雷達(dá)的道路與障礙檢測研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2010.

[9]馮少榮，肖文俊.DBSCAN聚類算法的研究與改進(jìn)[J].中國礦業(yè)大學(xué)學(xué)報(bào)，2008，27（1）：105-111.

[10]謝友寶.最小二乘法分段直線擬合[J].南昌航空工業(yè)學(xué)院學(xué)報(bào)，1992（2）：19-25.

[11]張東林.分段最小二乘法曲線擬合[J].沈陽大學(xué)學(xué)報(bào)，1994（2）：80-83.