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

高棟南

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

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

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

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

1設備概述

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

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

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

2.1道邊檢測原理

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

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

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

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

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

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

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

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

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

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

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

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

使用K-means算法將有效道邊點集聚類為左道邊類與右道邊類，共計兩類，可以確定聚類個數為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算法相同。通過如上數據分割后，可以確保初始中心點的選擇更具代表性。

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

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

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

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

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

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

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

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

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

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

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

4結語

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

參考文獻：

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

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

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

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

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

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

[7]崔佳超.無人駕駛智能車在動態環境中的避障方法[D].西安：西安工業大學，2015.

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

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

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

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

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