高棟南

摘要：為了讓智能汽車辨識(shí)可行駛區(qū)域，道邊檢測(cè)是前提。使用多線激光雷達(dá)，通過對(duì)大量道邊點(diǎn)數(shù)據(jù)進(jìn)行分析，提出一種道邊檢測(cè)與跟蹤算法。首先，通過分析掃描點(diǎn)特征，建立多閾值篩選算法，提取出有效道邊點(diǎn)集；其次，采用基于K-means改進(jìn)的聚類算法對(duì)有效道邊點(diǎn)集進(jìn)行聚類分析，得到左、右兩側(cè)的道邊點(diǎn)集；最后，使用最小二乘法擬合得到左右道邊。經(jīng)過實(shí)際驗(yàn)證，該算法道邊檢測(cè)準(zhǔn)確，處理每幀數(shù)據(jù)平均僅需34ms。

關(guān)鍵詞：激光雷達(dá)；無人駕駛；道邊檢測(cè)；K-means算法；直線擬合

DOI：10.11907/rjdk.173108

中圖分類號(hào)：TP306

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2018）007-0023-04

Abstract：Asthepreconditionofautonomousdriving，roadedgedetectionwascrucialforintelligentvehiclestorecognizethefreedrivingspace.Byanalyzingplentyofroadedgepointdata，weproposeanewroadedgedetectionandtrackingalgorithm.Firstly，amulti-thresholdalgorithmwasusedtoextractvalidroadedgepointbyanalyzingthecharacteristicofscanningpoint.Secondly，animprovedalgorithmbasedonK-meansalgorithmwasusedtoclassifyroadedgeintorightandleftroadedgepoints.Finally，tworoadedgeswerefittedbyleastsquarealgorithm.Experimentalresultsshowedthatthealgorithmcanaccuratelydetectroadedge，whichonlycosts34mstoprocessonedataframe.

KeyWords：laserradar；autonomousdriving；roadedgedetection；K-meansalgorithm；linearfitting

0引言

如今，無人駕駛技術(shù)發(fā)展迅速，該技術(shù)為緩解交通擁堵、減少交通事故提供了解決方案，其中道邊檢測(cè)是無人駕駛技術(shù)的重要組成部分。激光雷達(dá)作為一種探測(cè)距離遠(yuǎn)、范圍廣，且測(cè)距準(zhǔn)確的傳感器，被應(yīng)用于無人車輛道邊檢測(cè)。其中，基于多線激光雷達(dá)的道邊檢測(cè)成為道邊檢測(cè)的主要方式。

傳統(tǒng)的道邊檢測(cè)算法原理簡(jiǎn)單，多層掃描點(diǎn)數(shù)據(jù)通過提取道邊點(diǎn)呈直線排列特征，提取出有效道邊點(diǎn)[1-2]，經(jīng)過簡(jiǎn)單聚類后，擬合得到完整道邊。不足之處在于，道路兩側(cè)的樹木、墻面等干擾項(xiàng)生成的掃描點(diǎn)難以濾除[3]。此外，若不通過精確的聚類分析，難以清晰地將道邊點(diǎn)分類為左道邊點(diǎn)與右道邊點(diǎn)。

本文提出一種新的道邊檢測(cè)方法，通過多閾值篩選方法排除上述干擾項(xiàng)影響，得到有效道邊點(diǎn)集，并采用基于K-means的改進(jìn)算法，對(duì)道邊點(diǎn)集進(jìn)行聚類，得到左、右道邊點(diǎn)集。同時(shí)使用最小二乘法，對(duì)聚類后的道邊點(diǎn)實(shí)現(xiàn)道邊擬合。

1設(shè)備概述

本文選用IBEO-LUX2010四線激光雷達(dá)。該雷達(dá)擁有4條激光掃描線，掃描線之間的夾角為0.8°。雷達(dá)采用TOF算法（TimeofFlight）探測(cè)距離，通過直接測(cè)量以光速傳播的激光脈沖從發(fā)射時(shí)刻到接收到回波信號(hào)時(shí)刻之間的時(shí)間得到目標(biāo)距離。TOF算法原理簡(jiǎn)單，功耗小且量程遠(yuǎn)，僅用一次測(cè)量即可得到單點(diǎn)目標(biāo)距離[4]。激光雷達(dá)的掃描頻率為12.5Hz，水平掃描角度為-50°～35°。

激光雷達(dá)的4個(gè)掃描層從下到上分別用紅、藍(lán)、綠、黃表示，雷達(dá)安裝位置與掃描層結(jié)構(gòu)如圖1所示。激光雷達(dá)坐標(biāo)系如圖2所示，以雷達(dá)自身作為坐標(biāo)原點(diǎn)O，X軸代表坐標(biāo)系橫軸，水平向右；Z軸代表坐標(biāo)系縱軸，方向向前；Y軸根據(jù)右手定則，方向豎直向上。實(shí)驗(yàn)部分三維點(diǎn)云以此坐標(biāo)系構(gòu)建。

2基于多線激光雷達(dá)的道邊檢測(cè)

2.1道邊檢測(cè)原理

城市環(huán)境中，大部分道路有著清晰的道邊[5]，道路模型如圖3所示。道邊與路面相比，有顯著的高度特征。其中虛線表示雷達(dá)的一條掃描線，道邊上的掃描線由道邊點(diǎn)組成，路面與人行道的掃描線由非道邊點(diǎn)組成。

觀察圖3可知，只要找到道邊點(diǎn)，即可擬合出完整的道邊直線。

2.2多閾值篩選方法提取道邊點(diǎn)

通過分析大量掃描點(diǎn)中的道邊點(diǎn)數(shù)據(jù)，總結(jié)得到以下特征：①一條道邊的道邊點(diǎn)排列呈線性特征[6]，即可使用直線y=kx+b表示；②道邊掃描點(diǎn)是一組連續(xù)的點(diǎn)，連續(xù)兩點(diǎn)之間的距離與掃描頻率有關(guān)，應(yīng)該小于一個(gè)閾值；③道邊點(diǎn)略高于地面，其高度介于一定范圍之間；④道邊長(zhǎng)度滿足一定距離，可理解為略大于或小于數(shù)據(jù)標(biāo)定中的理論長(zhǎng)度。依據(jù)上述道邊點(diǎn)特征，處理步驟如下：

首先，道邊點(diǎn)選取范圍應(yīng)在道邊檢測(cè)時(shí)數(shù)據(jù)標(biāo)定的距離范圍內(nèi)，根據(jù)前面的標(biāo)定確定道邊檢測(cè)的起始距離S1與終點(diǎn)距離S2，單位為m，即道邊點(diǎn)距離必須符合閾值區(qū)間[S1，S2]。

其次，道邊點(diǎn)的位置高于地面，介于道邊上沿與道邊下沿（地面）之間。通過引入高度信息進(jìn)一步判斷：根據(jù)雷達(dá)掃描線的俯仰角a計(jì)算求出掃描點(diǎn)的高度信息[7]，記作height，其大小應(yīng)當(dāng)滿足閾值區(qū)間[h1，h2]，h1代表道邊下邊沿點(diǎn)高度，h2代表道邊上邊沿點(diǎn)高度（單位均為m）。利用閾值，可以有效剔除一些干擾點(diǎn)[8]，例如道邊以上的樹木和墻壁等掃描點(diǎn)。通過以上兩個(gè)閾值條件篩選，得到初步的道邊點(diǎn)。

最后，由初步道邊點(diǎn)中的第一個(gè)點(diǎn)開始，按順序依次選取n個(gè)點(diǎn)，連續(xù)兩點(diǎn)的點(diǎn)間距要小于閾值Pd（單位：m），該閾值依據(jù)雷達(dá)掃描頻率確定。建立該閾值以防止道邊探測(cè)出現(xiàn)路口或岔口等干擾因素時(shí)[9]，可能出現(xiàn)點(diǎn)之間距離過大，從而被誤判為一條完整道邊的情況。若大于閾值Pd，則從不滿足的點(diǎn)開始，迭代上述過程，直至找到彼此之間距離小于閾值的n個(gè)點(diǎn)，將此n個(gè)點(diǎn)作為一組點(diǎn)集保存，最終得到M組點(diǎn)集。

上述檢測(cè)產(chǎn)生M組點(diǎn)集，每組有n個(gè)點(diǎn)。在每組點(diǎn)集的n個(gè)點(diǎn)中取第一個(gè)與最后一個(gè)掃描點(diǎn)建立直線y=kx+b，然后判斷其余（n-2）個(gè)點(diǎn)到該直線的距離是否小于閾值Pld（單位：m），小于閾值則說明點(diǎn)距離直線非常近，可近似看作n點(diǎn)在同一條直線上。若小于閾值Pld，則保存這組點(diǎn)集；若大于閾值Pld，則摒棄該組點(diǎn)集，重新對(duì)下一組點(diǎn)集的n個(gè)掃描點(diǎn)迭代上述操作，直至M組點(diǎn)都處理完畢，得到符合要求的O組點(diǎn)集（O

對(duì)產(chǎn)生的O組點(diǎn)集，判斷每一組對(duì)應(yīng)直線的斜率是否屬于閾值區(qū)間（K1，K2），若不屬于該區(qū)間，則判定該組點(diǎn)無法構(gòu)成道邊直線，摒棄這組點(diǎn)集；若滿足該區(qū)間，則保存這組點(diǎn)集[12]。迭代上述過程，直至O組點(diǎn)集都處理完畢，得到符合要求的P組點(diǎn)集（P

通過上述步驟，得到P組有效的道邊點(diǎn)集。

2.3基于K-means的改進(jìn)聚類算法

對(duì)上述得到的P組點(diǎn)集進(jìn)行聚類，分為無人車輛左道邊點(diǎn)與右道邊點(diǎn)。K-means算法作為一種動(dòng)態(tài)規(guī)劃的聚類算法，具有計(jì)算速度快、消耗資源少的優(yōu)點(diǎn)，其時(shí)間復(fù)雜度為O（nkt），其中k為聚類個(gè)數(shù)，t為聚類迭代次數(shù)，n為總樣本數(shù)。算法基本流程如下：①首先給定樣本聚類個(gè)數(shù)k；②根據(jù)給定的k，隨機(jī)從樣本中選取k個(gè)聚類中心點(diǎn)；③計(jì)算剩余每個(gè)樣本到每個(gè)聚類中心點(diǎn)的歐式距離，將樣本歸為離其最近的中心點(diǎn)所在類；④重新計(jì)算k個(gè)類的中心點(diǎn)；⑤迭代執(zhí)行②、③步，直至中心點(diǎn)不再變化或小于設(shè)定閾值，即中心點(diǎn)收斂，聚類結(jié)束。

使用K-means算法將有效道邊點(diǎn)集聚類為左道邊類與右道邊類，共計(jì)兩類，可以確定聚類個(gè)數(shù)為2，但由于初始選取聚類中心點(diǎn)是隨機(jī)的，會(huì)導(dǎo)致聚類精度降低[10]。對(duì)于K-means算法的初始中心點(diǎn)選取作如下改進(jìn)：先求出每個(gè)道邊點(diǎn)之間的歐氏距離作為差異度，距離越大說明差異越大，反之，距離越小則說明越相似。

利用該差異度建立差異度矩陣。假設(shè)有n個(gè)道邊點(diǎn)，生成n*n維的差異度矩陣M，矩陣中的元素為兩個(gè)道邊點(diǎn)距離，記作d（i，j），表示第i個(gè)到第j個(gè)道邊點(diǎn)距離，矩陣公式如下：

遍歷矩陣元素，找到最大的d（i，j），記作dmax，說明其構(gòu)成的第i點(diǎn)與第j點(diǎn)差異性極大，即該兩點(diǎn)距離最遠(yuǎn)，由于只存在左、右兩類道邊點(diǎn)，第i點(diǎn)與第j點(diǎn)一定是屬于不同側(cè)道邊的兩點(diǎn)，可以將第i點(diǎn)作為第一個(gè)初始聚類簇中心點(diǎn)，而第j點(diǎn)可作為第二個(gè)初始聚類簇中心點(diǎn)。選出兩個(gè)初始聚類中心簇后，剩余聚類步驟與K-means算法相同。通過如上數(shù)據(jù)分割后，可以確保初始中心點(diǎn)的選擇更具代表性。

為驗(yàn)證改進(jìn)后的聚類精度變化，分別使用數(shù)據(jù)集Wine、Iris等對(duì)改進(jìn)前的K-means算法與改進(jìn)后的算法進(jìn)行10次聚類測(cè)試，對(duì)聚類效果進(jìn)行對(duì)比。數(shù)據(jù)集信息如表1所示，對(duì)比結(jié)果如表2、表3所示。

對(duì)聚類得到的左、右道邊點(diǎn)采用最小二乘法分別進(jìn)行擬合，得到兩條完整道邊所在直線的斜率與截距。最小二乘法通過最小化誤差的平方和尋找數(shù)據(jù)的最佳函數(shù)匹配[11]，可以求得直線方程中的系數(shù)。計(jì)算公式如下：

其中n是該側(cè)掃描點(diǎn)總數(shù)，xi、yi分別代表道邊點(diǎn)在雷達(dá)坐標(biāo)系的橫、縱坐標(biāo)。道邊檢測(cè)算法整體流程如圖4所示。

3道邊檢測(cè)實(shí)驗(yàn)結(jié)果及分析

試驗(yàn)場(chǎng)景如圖5所示，該場(chǎng)景左右兩側(cè)分別具有樹木及墻面等干擾項(xiàng)。

圖6是以雷達(dá)坐標(biāo)系中的xOz平面建立的柵格地圖，將雷達(dá)四層掃描原始數(shù)據(jù)點(diǎn)映射到柵格地圖中，兩條白色斜線形成的夾角代表雷達(dá)掃描區(qū)域。本文的道邊檢測(cè)算法僅使用最底層掃描點(diǎn)（紅色掃描點(diǎn)）進(jìn)行分析處理，最底層的原始數(shù)據(jù)點(diǎn)包含地面點(diǎn)、樹木、墻壁等多個(gè)干擾點(diǎn)。

圖7是使用道邊檢測(cè)算法后得到的圖像，通過提取有效道邊點(diǎn)，進(jìn)一步進(jìn)行聚類、直線擬合得到兩條完整的道邊直線，將道邊映射在柵格地圖上，用白色線段表示。其中實(shí)線部分代表實(shí)測(cè)道邊點(diǎn)構(gòu)成的道邊，虛線為擬合補(bǔ)全得到的道邊。實(shí)驗(yàn)證明，僅使用單層掃描點(diǎn)數(shù)據(jù)通過本文算法進(jìn)行檢測(cè)，結(jié)果較為準(zhǔn)確。

分析檢測(cè)算法對(duì)原始掃描點(diǎn)數(shù)據(jù)的處理過程，并比較處理結(jié)果：原始數(shù)據(jù)點(diǎn)云如圖8所示，多閾值算法提取道邊點(diǎn)處理結(jié)果如圖9所示。道邊點(diǎn)點(diǎn)云與原始數(shù)據(jù)點(diǎn)云相比，左、右側(cè)的部分干擾點(diǎn)，以及地面點(diǎn)已被排除。通過觀察圖8中的點(diǎn)云分布，與圖3中的道邊線形狀相符合。

得到有效道邊點(diǎn)后，使用基于K-means的改進(jìn)算法進(jìn)行聚類，得到位于雷達(dá)兩側(cè)的左右側(cè)道邊點(diǎn)，再將這些點(diǎn)映射到柵格地圖中，結(jié)果見圖10所示。對(duì)聚類后的兩類道邊點(diǎn)進(jìn)行直線擬合，得到完整道邊。將兩條完整道邊映射到柵格地圖中，處理結(jié)果如圖11所示。

使用檢測(cè)算法，對(duì)存在干擾項(xiàng)的1079幀掃描數(shù)據(jù)進(jìn)行檢測(cè)。通過驗(yàn)證檢測(cè)得到的道邊位置，獲取最高與最低準(zhǔn)確率，并求出平均準(zhǔn)確率與處理每幀數(shù)據(jù)的平均消耗時(shí)間，算法檢測(cè)效果如表4所示。

從處理數(shù)據(jù)的平均耗時(shí)與準(zhǔn)確率可看出，該算法耗時(shí)較少，檢測(cè)效果好，在試驗(yàn)場(chǎng)景存在干擾項(xiàng)的情況下，依然保持了較高準(zhǔn)確率。

4結(jié)語

本文提出一種基于多線激光雷達(dá)的道邊檢測(cè)算法，首先使用多閾值篩選算法，較好地剔除了諸多干擾點(diǎn)；其次，使用基于K-means的改進(jìn)聚類算法，精確地將道邊點(diǎn)聚類為左右側(cè)道邊；最后，使用最小二乘法，擬合出完整道邊。下一步工作可在利用道邊信息分割出“可行駛區(qū)域”后，對(duì)該區(qū)域中的動(dòng)態(tài)障礙物進(jìn)行聚類、跟蹤，提取障礙物相關(guān)信息。

參考文獻(xiàn)：

[1]段建民.多線激光雷達(dá)在無人駕駛車中的環(huán)境感知[J].北京工業(yè)大學(xué)學(xué)報(bào)，2014，10（12）：1891-1898.

[2]楊象軍.基于四線激光雷達(dá)的道路檢測(cè)與跟蹤[D].杭州：浙江大學(xué)，2013.

[3]ALOSHYNAV.基于多線激光雷達(dá)的道路和障礙物檢測(cè)[D].北京：北京工業(yè)大學(xué)，2016.

[4]史鵬波.基于單線激光雷達(dá)的道路特征檢測(cè)[D].南京：南京理工大學(xué)，2013.

[5]肖已達(dá).基于激光雷達(dá)的道路可通行區(qū)域檢測(cè)[J].機(jī)電一體化，2013，12（2）：62-70.

[6]ALBERTOB，PIETROC，MIRKOF.Thevislabintercontinentalautonomouschallenge：anextensivetestforaplatoonofintelligentvehicles[J].InternationalJournalofVehicleAutonomousSystems，2012，10（3）：147-164.

[7]崔佳超.無人駕駛智能車在動(dòng)態(tài)環(huán)境中的避障方法[D].西安：西安工業(yè)大學(xué)，2015.

[8]辛煜.無人駕駛車輛運(yùn)動(dòng)障礙物檢測(cè)、預(yù)測(cè)和避撞方法研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2014.

[9]王科.城市交通中智能車輛環(huán)境感知方法研究[D].長(zhǎng)沙：湖南大學(xué)，2013.

[10]朱學(xué)葵，高美娟，李尚年.一種智能汽車的實(shí)時(shí)道路邊緣檢測(cè)算法[J].北京聯(lián)合大學(xué)學(xué)報(bào)，2015，29（4）：1-7.

[11]田垅，劉宗田.最小二乘法分段直線擬合[J].計(jì)算機(jī)科學(xué)，2012，39（6）：482-486.

（責(zé)任編輯：黃?。?/p>