文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.170392
中文引用格式: 段建民,王昶人,任璐,等. 基于多層激光雷達(dá)的可行駛區(qū)域信息提取算法[J].電子技術(shù)應(yīng)用,2017,43(10):78-82.
英文引用格式: Duan Jianmin,Wang Changren,Ren Lu,et al. Algorithm of driving area information extraction based on multi-layer lidar[J].Application of Electronic Technique,2017,43(10):78-82.
0 引言
隨著社會(huì)的不斷發(fā)展,世界各國(guó)越來(lái)越多的學(xué)者開(kāi)始對(duì)無(wú)人駕駛進(jìn)行研究[1-2],其中雷達(dá)技術(shù)更得到廣泛關(guān)注。文獻(xiàn)[3]利用路沿點(diǎn)數(shù)據(jù)斜率一致特性對(duì)路沿點(diǎn)進(jìn)行提取,但該算法容易受路面點(diǎn)和障礙物點(diǎn)的影響并且要分層處理,所以準(zhǔn)確性和實(shí)時(shí)性都不能達(dá)到要求。文獻(xiàn)[4]利用激光雷達(dá)返回高度數(shù)據(jù)的跳變提取路沿點(diǎn),這種方法受障礙物影響很不穩(wěn)定。而對(duì)于聚類算法,由于激光雷達(dá)數(shù)據(jù)主要是成簇出現(xiàn)的,所以基于密度的聚類方法適合于激光雷達(dá)數(shù)據(jù),其中OPTICS算法是典型的基于密度的聚類方法。文獻(xiàn)[5]利用結(jié)果序列重組織策略對(duì)OPTICS算法進(jìn)行改進(jìn),但是在實(shí)際應(yīng)用中,對(duì)于激光雷達(dá)數(shù)據(jù)點(diǎn)突然出現(xiàn)的噪點(diǎn)無(wú)法區(qū)分,導(dǎo)致障礙物提取效果不準(zhǔn)確。
本文首先利用數(shù)據(jù)區(qū)間密度分布提取路沿點(diǎn)并通過(guò)最小二乘法擬合出路沿區(qū)分可行駛區(qū)域,然后在可行駛區(qū)域中利用改進(jìn)的OPTICS算法對(duì)返回?cái)?shù)據(jù)進(jìn)行實(shí)時(shí)聚類。最后通過(guò)實(shí)車實(shí)驗(yàn)驗(yàn)證提出算法的有效性與實(shí)時(shí)性。
1 激光雷達(dá)數(shù)據(jù)預(yù)處理
1.1 激光雷達(dá)數(shù)據(jù)分析
本文應(yīng)用德國(guó)IBEO公司生產(chǎn)的IBEO LUX 2010型四線激光雷達(dá),該型號(hào)的雷達(dá)較單線激光雷達(dá)具有數(shù)據(jù)量大、檢測(cè)精度高、探測(cè)距離遠(yuǎn)等優(yōu)勢(shì)[6]。其主要參數(shù)如表1所示。
四線雷達(dá)返回的信息主要包含序號(hào)、掃描層數(shù)、距離以及位置坐標(biāo)信息。其特性分析如下:
(1)激光雷達(dá)是自左向右掃描的,每一幀返回的數(shù)據(jù)量基本相近;
(2)激光雷達(dá)返回的數(shù)據(jù)是根據(jù)前方場(chǎng)景的變化而變化的,每個(gè)障礙物的掃描點(diǎn)的數(shù)目及形狀不一;
(3)當(dāng)激光雷達(dá)掃描到路沿時(shí)返回的數(shù)據(jù)特點(diǎn)是x軸坐標(biāo)稀疏,y軸坐標(biāo)緊密排列。
1.2 數(shù)據(jù)預(yù)處理
為了檢測(cè)車輛前方的可行駛區(qū)域以及障礙物的信息,將激光雷達(dá)安放在車輛前方正中間的位置,根據(jù)以往經(jīng)驗(yàn),雷達(dá)的安裝高度設(shè)定為0.846 m。安裝位置示意圖如圖1所示。
2 激光雷達(dá)數(shù)據(jù)處理方法
2.1 一維數(shù)據(jù)區(qū)間密度分布
假設(shè)(x1,y1),(x2,y2),(x3,y3),…,(xn,yn),n∈R為雷達(dá)返回路沿點(diǎn)數(shù)據(jù),根據(jù)其特性,其中某一維數(shù)據(jù)D={y1,y2,y3,…,yn},n∈R是基本相近的,數(shù)據(jù)區(qū)間概率密度分布即雷達(dá)返回的數(shù)據(jù)落在某個(gè)區(qū)間[ω,ξ]的密度,其公式為:
式中,ω和ξ為某個(gè)區(qū)間的兩個(gè)端點(diǎn),num(yi)為落在某個(gè)區(qū)間數(shù)據(jù)的個(gè)數(shù),分母為數(shù)據(jù)個(gè)數(shù)之和;P為在某個(gè)區(qū)間數(shù)據(jù)個(gè)數(shù)占總體的概率。若將整體的數(shù)據(jù)分為j個(gè)區(qū)間,則其概率的總和為1。
2.2 OPTICS算法
OPTICS[7-9](Order Point to Identify the Cluster Structure)算法是一種基于密度的聚類算法。此算法是DBSCAN算法的擴(kuò)展,對(duì)數(shù)據(jù)對(duì)象集中的數(shù)據(jù)進(jìn)行排序,輸出一個(gè)有序的對(duì)象列表(cluster-ordering),在這個(gè)列表中包含了用來(lái)提取聚類的所有信息,即對(duì)數(shù)據(jù)對(duì)象進(jìn)行分類。以下是OPTICS算法中引入的兩個(gè)定義[10]:
定義1 核心距離(core-distance)
假設(shè)點(diǎn)P包含m個(gè)鄰近的最小半徑為min-distance(P),那么P點(diǎn)的核心距離就可以定義為:
定義2 可達(dá)距離(reach-distance,RD)
假設(shè)P是點(diǎn)o鄰近點(diǎn)之一,那么P與o相關(guān)的可達(dá)距離定義式為:
傳統(tǒng)的OPTICS聚類方法實(shí)現(xiàn)步驟如圖2所示,OPTICS算法的優(yōu)點(diǎn)是對(duì)輸入?yún)?shù)不敏感,但是輸入Eps與實(shí)際Eps差距較大時(shí),聚類效果依然被影響,而且該算法對(duì)于噪點(diǎn)也不能區(qū)分。
2.3 基于加權(quán)歐氏距離的KNN圖
在實(shí)際的雷達(dá)數(shù)據(jù)中對(duì)雷達(dá)數(shù)據(jù)進(jìn)行數(shù)據(jù)密度分布計(jì)算后提取各個(gè)峰值區(qū)域的點(diǎn)集,計(jì)算其橫、縱坐標(biāo)的方差值,就可以計(jì)算出數(shù)據(jù)點(diǎn)間的加權(quán)歐氏距離。
KNN即將實(shí)際雷達(dá)掃描到的數(shù)據(jù)點(diǎn)按照加權(quán)歐氏距離求取其距離矩陣Distk*k,然后將Distk*k中每一維按照升序排列形成sort(Distk*k),最后將sort(Distk*k)中的每一維數(shù)據(jù)繪制成KNN圖。
2.4 最小二乘法擬合
本文根據(jù)實(shí)驗(yàn)道路特性,由于實(shí)驗(yàn)道路兩側(cè)路沿點(diǎn)多呈線性分布,因此,使用最小二乘法對(duì)道路兩側(cè)提取的路沿點(diǎn)進(jìn)行線性擬合。最小二乘法[12-14]是一種數(shù)學(xué)優(yōu)化方法,它通過(guò)最小化誤差的平方和尋找數(shù)據(jù)的最佳函數(shù)匹配。其針對(duì)線性擬合常用的表達(dá)式為y=kx+h,以下則是參數(shù)k和h的求解公式:
式中,n表示待擬合的點(diǎn)的個(gè)數(shù),(xi,yi)為待擬合點(diǎn)的坐標(biāo)值,k為斜率,h為截距。
3 可行駛區(qū)域信息提取方法
3.1 基于加權(quán)歐氏距離改進(jìn)的OPTICS算法
傳統(tǒng)的OPTICS算法雖然能克服其他傳統(tǒng)聚類算法的一些問(wèn)題[15],但其自身仍然有一些不足之處,如OPTICS在實(shí)際的篩選核心點(diǎn)的過(guò)程中是通過(guò)選取合適的Eps來(lái)確定核心點(diǎn)的位置,而由于Eps選取不當(dāng)引入噪點(diǎn),這樣大大降低了算法對(duì)噪點(diǎn)的敏感程度,使得聚類不準(zhǔn)確。另外,如果盲目選擇Eps的范圍,同樣影響聚類效果。
為了改進(jìn)OPTICS的不足之處,本文提出了基于加權(quán)歐氏距離KNN改進(jìn)的OPTICS算法,此算法不需要輸入?yún)?shù)Eps,而是通過(guò)數(shù)據(jù)點(diǎn)間加權(quán)歐氏距離升序排序形成一個(gè)k-最近鄰圖(KNN)來(lái)確定聚類結(jié)果以及區(qū)分噪點(diǎn)。具體步驟如圖3所示。
根據(jù)圖3所示,改進(jìn)的OPTICS算法不需要選取Eps就可以直接進(jìn)行聚類。在流程圖中基于加權(quán)歐氏距離KNN分離噪點(diǎn)的具體步驟如下:
(1)求取每類數(shù)據(jù)點(diǎn)中每個(gè)點(diǎn)之間的加權(quán)歐式距離,形成距離矩陣Distk*k;
(2)將距離矩陣中各維度距離按照升序排序,形成sort(Distk*k);
(3)由于噪點(diǎn)與其他點(diǎn)的距離大于一個(gè)閾值,所以就要判定這個(gè)點(diǎn)與其他點(diǎn)之間距離最小距離是否大于threshold,若大于,則該點(diǎn)為噪點(diǎn)。
3.2 基于一維數(shù)據(jù)區(qū)間密度分布的路沿提取算法
通過(guò)對(duì)激光雷達(dá)返回的點(diǎn)云數(shù)據(jù)分析可知,在點(diǎn)云中包含有路面點(diǎn)、兩側(cè)路沿點(diǎn)、周圍花草景物點(diǎn)以及障礙物點(diǎn)。設(shè)定k個(gè)等距區(qū)間[ω,ξ],在此區(qū)間中利用式(2)求取雷達(dá)數(shù)據(jù)點(diǎn)在每個(gè)區(qū)間的密度。以橫軸零為分界點(diǎn),提取出兩側(cè)密度最大值及次大值所在區(qū)間。由經(jīng)驗(yàn)知,路面點(diǎn)與路沿點(diǎn)高度差大約為20 cm,根據(jù)此高度差可消除路面點(diǎn)。得到路沿點(diǎn)后,將路沿點(diǎn)使用改進(jìn)的OPTICS算法進(jìn)行聚類,最后利用最小二乘法擬合得到路沿,并計(jì)算得到路沿信息。
3.3 可行駛區(qū)域內(nèi)障礙物信息提取
通過(guò)得到的路沿信息,可判定出路面的路寬度。若假設(shè)左右路沿點(diǎn)的范圍分別為[a,b]和[c,d],則根據(jù)橫向定界及式(8)得到可行駛區(qū)域的范圍:
式中,Croad為可行駛區(qū)域,Cnoise為周圍環(huán)境。
根據(jù)無(wú)人駕駛車輛寬度信息和提取出可行駛區(qū)域的寬度信息結(jié)合,其表達(dá)式為:
提取出可行駛區(qū)域后,剩下的點(diǎn)為障礙物以及噪點(diǎn)。障礙物點(diǎn)主要有:行人、機(jī)動(dòng)車、自行車等。障礙物的主要屬性信息表示為距離、角度、中心點(diǎn)等。利用改進(jìn)的OPTICS算法將可行駛區(qū)域內(nèi)的障礙物進(jìn)行聚類,并提取出每類障礙物的距離、角度以及障礙物中心點(diǎn)x、y、z坐標(biāo)值。通過(guò)類內(nèi)計(jì)算得到障礙物的長(zhǎng)度、寬度、距離、角度以及速度等信息。
4 實(shí)車實(shí)驗(yàn)結(jié)果
4.1 實(shí)驗(yàn)條件及平臺(tái)
本文實(shí)驗(yàn)平臺(tái)為BJUT-IV(Beijing University of Technology Intelligent Vehicle)自主研發(fā)的無(wú)人駕駛車,在車輛的前端正中的位置安裝IBEO-LUX四線激光雷達(dá)來(lái)采集實(shí)驗(yàn)數(shù)據(jù)。雷達(dá)安裝高度為0.846 m。實(shí)驗(yàn)的場(chǎng)景為校園內(nèi)道路,如圖4所示。
4.2 可行駛區(qū)域路沿提取實(shí)驗(yàn)結(jié)果
可行駛區(qū)域路沿提取實(shí)驗(yàn)結(jié)果如圖5所示。
圖4左側(cè)為實(shí)驗(yàn)場(chǎng)景1,道路條件為無(wú)車輛通過(guò)。圖5(b)為原始數(shù)據(jù)點(diǎn),原始數(shù)據(jù)點(diǎn)中包含路沿點(diǎn)、路面點(diǎn),及周圍的樹(shù)木、鐵網(wǎng)。圖中雷達(dá)數(shù)據(jù)點(diǎn)分為4層,由圖中箭頭所指的點(diǎn)表示。圖5(a)為雷達(dá)返回?cái)?shù)據(jù)坐標(biāo)y值的數(shù)據(jù)密度分布直方圖,其中以零為分界點(diǎn),4個(gè)范圍中靠近零的兩個(gè)區(qū)間為路沿點(diǎn)區(qū)間,而另外兩個(gè)區(qū)間為球場(chǎng)邊界。根據(jù)密度直方圖可以清晰地分析出左側(cè)路沿點(diǎn)所在范圍[-3.92,-3.7],右側(cè)路沿點(diǎn)范圍為[6.4,6.8]。通過(guò)對(duì)區(qū)間密度的選取,就得到了如圖5(c)所示的情況,圖中的兩列點(diǎn)則為通過(guò)基于一維數(shù)據(jù)區(qū)間密度提取出的結(jié)果。圖5(d)是將提取出的路沿點(diǎn)通過(guò)基于加權(quán)歐式距離的KNN改進(jìn)的OPTICS算法進(jìn)行聚類,圖中橢圓形框是為了清楚表示兩類的聚類結(jié)果。最后通過(guò)最小二乘法將兩側(cè)提取出的路沿點(diǎn)進(jìn)行線性擬合,結(jié)果如圖5(e)所示。提取出的路沿結(jié)果顯示,道路的寬度為10.48 m,車輛左側(cè)與路沿距離為6.64 m,車輛右側(cè)與路沿距離為3.83 m。在實(shí)際的實(shí)驗(yàn)場(chǎng)景中通過(guò)測(cè)量得到實(shí)際的道路寬度約為10.5 m,提取結(jié)果與實(shí)際寬度僅差0.02 m,路面寬度信息檢測(cè)率為99.8%,符合實(shí)際應(yīng)用需要。
4.3 可行駛區(qū)域障礙物提取實(shí)驗(yàn)結(jié)果
可行駛區(qū)域障礙物提取結(jié)果如圖6所示,圖4右側(cè)為實(shí)驗(yàn)場(chǎng)景2,場(chǎng)景中有行人和汽車。圖6(a)為第47幀加權(quán)歐氏距離KNN圖,圖中稀疏部分為文中提到的噪點(diǎn),其他部分為聚類效果。圖6(b)為車輛行駛過(guò)程中第47幀數(shù)據(jù)利用傳統(tǒng)OPTICS算法檢測(cè)出路面的障礙物的情況。從圖中可以看出,由于在雷達(dá)掃描過(guò)程中第3層數(shù)據(jù)出現(xiàn)噪點(diǎn),所以影響了聚類效果,導(dǎo)致聚類準(zhǔn)確性降低。而圖6(c)為第47幀數(shù)據(jù)利用基于加權(quán)歐氏距離的KNN改進(jìn)OPTICS算法的效果,算法可以避免路面噪點(diǎn)的影響,而且可以對(duì)障礙物準(zhǔn)確的聚類,并且通過(guò)計(jì)算可以得到障礙物的主要屬性,檢測(cè)到行人的長(zhǎng)度length=0.1 m,寬度為width=0.3 m,檢測(cè)到車輛的長(zhǎng)度為length=3.3 m,寬度為width=1.7 m,包括雷達(dá)距離前方障礙物的距離,檢測(cè)結(jié)果與實(shí)際測(cè)量尺寸基本相符,滿足了檢測(cè)要求。
圖6(d)為第45幀傳統(tǒng)OPTICS算法檢測(cè)結(jié)果,圖中將路面噪點(diǎn)當(dāng)作障礙物,影響了聚類準(zhǔn)確性。圖6(e)為第45幀數(shù)據(jù)利用改進(jìn)OPTICS算法,效果良好。通過(guò)以上實(shí)驗(yàn)結(jié)果可以證明,本文提出的可行駛區(qū)域提取算法的有效性與實(shí)時(shí)性都得到提高。
5 結(jié)束語(yǔ)
本文提出的可行駛區(qū)域信息提取算法包括可行駛區(qū)域路沿提取和障礙物提取,在路沿提取中,利用一維數(shù)據(jù)區(qū)間密度分布對(duì)雷達(dá)數(shù)據(jù)進(jìn)行界定,并通過(guò)界定范圍提取路沿點(diǎn),這種方法根據(jù)數(shù)據(jù)密度提取路沿點(diǎn)排除了路面障礙物對(duì)路沿點(diǎn)提取的影響,并且對(duì)多層數(shù)據(jù)同時(shí)處理,減少了復(fù)雜度。通過(guò)基于加權(quán)歐氏距離的KNN改進(jìn)OPTICS算法將路面上的障礙物點(diǎn)云進(jìn)行聚類,并通過(guò)計(jì)算得到障礙物的位置、距離、尺寸等信息。改進(jìn)的OPTICS算法則不再受Eps的約束,而且可以準(zhǔn)確分辨出噪點(diǎn),增加了障礙物提取的準(zhǔn)確性。提出的算法可以有效感知無(wú)人駕駛車輛前方可行駛區(qū)域的信息,為無(wú)人駕駛決策層提供有效信息,同時(shí)也提高了無(wú)人駕駛車的安全性。
參考文獻(xiàn)
[1] DAHLKAMP H,KAEHLER A,BRADSKI G.Self-supervised monocular road detection in desert terrain[C].Proceedings of Robotics:Science and Systems.Philadelphia:MIT Press,2006:115-121.
[2] 王欣,李高,朱萬(wàn)力,等.并聯(lián)混合動(dòng)力汽車能量管理建模及優(yōu)化研究[J].控制工程,2014(3):357-360.
[3] 楊象軍.基于四線激光雷達(dá)的道路檢測(cè)與跟蹤[D].杭州:浙江大學(xué),2013.
[4] 劉梓,唐振民,任明武.基于3D激光雷達(dá)的實(shí)時(shí)道路邊界檢測(cè)算法[J].華中科技大學(xué)學(xué)報(bào)(自然科版),2011(S2):351-354.
[5] 曾依靈,許洪波,白碩.改進(jìn)的OPTICS算法及其在文本聚類中的應(yīng)用[J].中文信息學(xué)報(bào),2008(1):51-55,60.
[6] 莊秀華.基于單線激光雷達(dá)的障礙物檢測(cè)與跟蹤研究[D].長(zhǎng)沙:湖南大學(xué),2014.
[7] 黨秋月,陸月明.基于OPTICS可達(dá)圖的自動(dòng)識(shí)別簇方法[J].計(jì)算機(jī)應(yīng)用,2012(S2):19-21,47.
[8] 王品,黃焱.改進(jìn)的OPTICS算法在調(diào)制識(shí)別中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2011(16):141-143.
[9] 孫天宇,孫煒,薛敏.OPTICS聚類與目標(biāo)區(qū)域概率模型的多運(yùn)動(dòng)目標(biāo)跟蹤[J].中國(guó)圖像圖形學(xué)報(bào),2015(11):1492-1499.
[10] 陳燕俐,洪龍,金達(dá)文,等.一種簡(jiǎn)單有效的基于密度的聚類分析算法[J].南京郵電學(xué)院學(xué)報(bào),2005(4):24-29.
[11] 段建民,李龍杰,鄭凱華.基于車載4線激光雷達(dá)的前方道路可行駛區(qū)域檢測(cè)[J].汽車技術(shù),2016(2):55-62.
[12] 鄒樂(lè)強(qiáng).最小二乘法原理及其簡(jiǎn)單應(yīng)用[J].科技信息,2010(23):282-283.
[13] 丁克良,沈云中,歐吉坤.整體最小二乘法直線擬合[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)(自然科學(xué)版),2010(1):44-47.
[14] 程玉民.移動(dòng)最小二乘法研究進(jìn)展與述評(píng)[J].計(jì)算機(jī)輔助工程,2009(2):5-11,20.
[15] 段建民,鄭凱華,李龍杰,等.基于多層激光雷達(dá)的道路信息提取算法[J].控制工程,2016(4):468-473.
作者信息:
段建民,王昶人,任 璐,劉 丹
(北京工業(yè)大學(xué) 信息學(xué)部,北京100124)