鄒 斌，王 磊

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

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

1 算法概述

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

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

圖1 智能車平臺Fig.1 Smart car platform

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

圖3 實際路況Fig.3 Actual road conditions

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

1.2 算法流程

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

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

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

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

圖5 人工標記圖Fig.5 Manual marking

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

1.3 掃描單線提取

計算出每個數(shù)據(jù)對應的掃描角度：

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

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

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

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

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

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

（1）對于數(shù)據(jù)集 χ＝｛x1，…，xn｝，利用 AIC 準則[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ù)集中隨機選取一個樣本作為初始聚類中心c；

（3）首先計算每個樣本與當前已有聚類中心之間的距離：

接著計算每個樣本被選為下一個聚類中心的概率：

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

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

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

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

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

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

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

（7）計算標準測度函數(shù)，當滿足函數(shù)收斂，則算法終止，如果不滿足則返回步驟5。對于函數(shù)收斂，本文定義畸變函數(shù)：

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

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

2.2 算法檢驗

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

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

2.2.2 檢測結果分析

為驗證本文算法的可行性和準確性，將本文算法和K-means算法在上述數(shù)據(jù)集分別進行多次獨立重復試驗，平均聚類精度如表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 算法平均聚類結果Tab.2 Algorithm average clustering results

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

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

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

2.2.3 單線數(shù)據(jù)運行結果

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

圖11 改進K-means算法聚類結果Fig.11 Improved K-means algorithm clustering results

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

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

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

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

圖12 障礙物判定準則Fig.12 Obstacle determination criteria

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

圖13 障礙物點集Fig.13 Obstacle point set

2.4 利用密度特征提取路沿

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

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

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

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

2.5 道路分割提取結果

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

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

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

3 試驗結果

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

圖16 算法識別結果ⅠFig.16 I algorithm identification results

圖17 算法識別結果ⅡFig.17Ⅱalgorithm identification results

圖18 耗時周期Fig.18 Time-consuming cycle

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

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

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

圖19 準確率Fig.19 Accuracy rate

4 結語

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

[1]陳慧巖.無人駕駛汽車概論[M].北京：北京理工大學出版社，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聚類算法研究及圖形演示的實現(xiàn)[J].信息技術，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].長沙：國防科學技術大學，2010.

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

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

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