高棟南

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

關鍵詞：激光雷達；無人駕駛；道邊檢測；K-means算法；直線擬合

DOI：10.11907/rjdk.173108

中圖分類號：TP306

文獻標識碼：A文章編號：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引言

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

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

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

1設備概述

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

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

2基于多線激光雷達的道邊檢測

2.1道邊檢測原理

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

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

2.2多閾值篩選方法提取道邊點

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

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

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

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

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

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

通過上述步驟，得到P組有效的道邊點集。

2.3基于K-means的改進聚類算法

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

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

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

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

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

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

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

3道邊檢測實驗結果及分析

試驗場景如圖5所示，該場景左右兩側分別具有樹木及墻面等干擾項。

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

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

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

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

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

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

4結語

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

參考文獻：

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

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

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

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

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

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

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

[8]辛煜.無人駕駛車輛運動障礙物檢測、預測和避撞方法研究[D].合肥：中國科學技術大學，2014.

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

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

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

（責任編輯：黃?。?/p>