基于改進歐幾里得聚類的激光雷達障礙物檢測

張 陽，葛平淑，崔芳磊，周宏宇，張 濤

(大連民族大學(xué) 機電工程學(xué)院，遼寧 大連 116605)

障礙物檢測技術(shù)作為智能車輛和汽車輔助安全駕駛系統(tǒng)中的一項重要感知技術(shù)，其檢測精度的高低直接影響行車的安全。智能汽車的障礙物檢測根據(jù)傳感器類型主要分為兩類：基于機器視覺的障礙物檢測和基于激光雷達的障礙物檢測?；跈C器視覺的障礙物檢測成本較低，算法比較成熟，但易受光照的影響，在一些條件下檢測精度較低，不能實現(xiàn)全天候準(zhǔn)確檢測。激光雷達擁有檢測范圍廣、精度高、抗干擾能力強等優(yōu)點，如今已經(jīng)被廣泛應(yīng)用于障礙物檢測領(lǐng)域[1]。

基于激光雷達的障礙物檢測方法主要有以下三種：基于密度的聚類算法(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)、K-means聚類算法和歐幾里得聚類算法(Euclidean)[2]。DBSCAN聚類是比較具有代表性的基于密度的聚類算法，可以檢測出任意形狀的簇并識別噪聲點，但點云的密度會影響聚類效果，并且該方法對內(nèi)存的占用較大，如果點云數(shù)量較多會對處理器的性能提出更高的要求[3]。K-means算法原理簡單，速度快，聚類效果較好，但需要事先確定聚類的數(shù)目K，在復(fù)雜的交通環(huán)境中難以提前確定K值。歐氏聚類對于點云數(shù)據(jù)具有很好的分割效果，但需要輸入一個固定的距離閾值。由于激光雷達點云具有近處密集遠(yuǎn)處稀疏的特點，該方法在對點云進行障礙物檢測時檢測精度較低[4]。本文對傳統(tǒng)歐氏聚類進行改進，利用距離閾值動態(tài)選擇代替固定閾值，能有效改善傳統(tǒng)歐氏聚類由于點云密度不均導(dǎo)致的檢測精度不高的問題。

1 歐氏聚類分割

1.1 確定距離閾值

歐氏聚類即基于歐氏距離的聚類算法，針對點云中的n個點，需要確定一個歐氏距離d，使小于d的點合并為一類，并且經(jīng)過多次迭代合并同時計算剩余類之間的歐氏距離，直到所有類之間的歐氏距離都大于d，則聚類結(jié)束[5]。包含m個點的第i類和第j類之間的歐氏距離：

(1)

1.2 近鄰搜索算法

由于激光雷達點云數(shù)據(jù)量過大，以64線激光雷達為例，一幀點云圖中包含的點數(shù)在十萬以上，并且點云的分布不均，導(dǎo)致了算法搜索目標(biāo)點很難有較高的效率。在輔助安全駕駛系統(tǒng)以及無人車當(dāng)中，障礙物檢測需要在較短的時間內(nèi)完成。為了提高算法的實時性，需要在離散的點云之間建立一定的拓?fù)潢P(guān)系，從而對領(lǐng)域中的點或集群實現(xiàn)高速查找。在離散的點云之間建立拓?fù)潢P(guān)系主要有兩種方法:Octree(八叉樹)和KD-Tree[6]。

Octree是一種描述三維空間的樹狀數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點都表示一個正方體的體素，每個節(jié)點可以分為八個子節(jié)點。Octree通過對三維空間中的實體進行體元剖分，可以使每個體元都具有相同的時間和空間復(fù)雜度，從而得到一個具有根節(jié)點的方向圖。Octree的每一個葉子節(jié)點都由相同屬性的體素構(gòu)成，如果屬性不同則需要進一步拆分，直到葉子結(jié)點中只存在相同屬性的體素[7]。Octree的原理如圖1。

圖1 Octree原理

KD-Tree相當(dāng)于二叉樹的多維擴展，每個非葉子結(jié)點可以看做一個超平面，將空間分為兩個子空間，實現(xiàn)對多維數(shù)據(jù)的組織和存儲。如果葉子結(jié)點的數(shù)目達到了設(shè)定的閾值，則不再進行劃分，否則繼續(xù)劃分葉子結(jié)點。為能夠處理三維點云數(shù)據(jù)，需要建立三維KD-Tree[8]。KD-Tree的算法流程如圖2。

圖2 KD-Tree流程圖

為對比兩種鄰域搜索方法的效率，對同一幀點云構(gòu)建拓?fù)潢P(guān)系。當(dāng)點云數(shù)據(jù)量較少時兩種方法擁有相似的效率。當(dāng)數(shù)據(jù)量增大，每個點附近點增多，KD-Tree在離散點之間建立拓?fù)潢P(guān)系花費的時間更少，由于激光雷達點云數(shù)據(jù)量非常大，同時對實時性也有很高的要求，故本文選擇KD-Tree對點云進行鄰域搜索。

1.3 改進歐氏聚類算法

傳統(tǒng)的歐氏聚類算法適合密度均勻的點云數(shù)據(jù)，對于密度不均的點云數(shù)據(jù)處理效果不理想。為了對不均勻的點云數(shù)據(jù)進行處理，各國的學(xué)者提出了很多種方法。Francisco de A.T.等[9]提出了一種自適應(yīng)閾值的聚類算法，可以根據(jù)障礙物的形狀和大小動態(tài)設(shè)定閾值，但該方法只適用于點云數(shù)目和待測目標(biāo)均較少的情況，車載激光雷達掃描得到的數(shù)據(jù)量較大，判斷所有障礙物的形狀和大小需要花費較長時間，算法的實時性不好。劉暢等[10]以到激光雷達的距離為半徑劃分區(qū)域，不同的區(qū)域選擇不同的距離閾值，但該方法需要預(yù)先將點云按照半徑分割，有可能在分割的過程中將一個障礙物分割為兩個從而造成誤檢。本文針對點云密度不均的問題提出了動態(tài)選擇距離閾值的歐氏聚類算法，根據(jù)點到激光雷達的距離變化更改距離閾值的大小。

算法共分為四步：

(1)通過KD-Tree建立點云cloud中離散點之間的拓?fù)潢P(guān)系；

(2)初始化一個過渡聚類隊列nn_indices、一個種子隊列seed_queue、一個空的聚類列表clusterIndices，并將cloud中每一個點ci加入到seed_queue中；

(3)針對seed_queue中的第i個點ci，搜索半徑r小于距離閾值d內(nèi)的鄰域，將搜索到的點全部存放在nn_indices中，計算nn_indices中每一個點到ci的歐氏距離，將距離最小的點劃分到同一類中，并將得到的聚類存放在clusterIndices中，迭代循環(huán)多次，直到處理完seed_queue中的每一個點，每次循環(huán)都刷新nn_indices；

(4)計算clusterIndices中每一個聚類到其他聚類之間的歐氏距離，將歐氏距離最小的聚類合并為同一個聚類，經(jīng)過多次迭代循環(huán)，直到每一個聚類到其他聚類之間的歐氏距離都大于d為止。d是關(guān)于數(shù)據(jù)點坐標(biāo)的表達式：

(2)

式中：Xi和Yi是待搜索的點或待搜索的聚類中心點的坐標(biāo)；α和β是用來調(diào)整d的參數(shù)，與激光雷達的角分辨率和角度精度有關(guān)，角分辨率越小，角度精度越高，α和β的值越小，具體數(shù)值需通過多次實驗確定。

2 實驗驗證

實驗軟件環(huán)境為Windows10，編程語言為C++，以隨機抽取的一張點云圖為例，通過處理點云圖觀察實驗結(jié)果完成對算法的驗證。

在對點云圖進行聚類之前需要進行預(yù)處理，由于激光雷達點云數(shù)量較大，直接處理會占用大量的內(nèi)存，算法運行速度緩慢，不符合實時性的要求。所以需要先減少點云的數(shù)量，將實驗中沒有作用的點去除，提高算法速度的同時避免誤檢。預(yù)處理包括設(shè)置感興趣區(qū)域、下采樣、使用RANSCA去除地面點，可以有效減少點云數(shù)量的同時較好地保存障礙物點的特征。原始點云圖如圖3。

圖3 原始點云圖

由于桿之間距離較近，在側(cè)向容易將兩個桿誤看成一個，為方便觀察，預(yù)處理后的點云圖如圖4。

a)側(cè)視圖 b)俯視圖

本文任選十張預(yù)處理后的點云圖，共包含110個障礙物，分別使用改進歐氏聚類算法和傳統(tǒng)歐氏聚類算法進行聚類，對比兩種方法的準(zhǔn)確率。通過多次實驗找到傳統(tǒng)歐氏聚類的最佳距離閾值，準(zhǔn)確檢測到障礙物100個，準(zhǔn)確率為90.9%，準(zhǔn)確聚類的數(shù)量變化如圖5。

圖5 準(zhǔn)確聚類的數(shù)量變化

在傳統(tǒng)歐氏聚類的基礎(chǔ)上獲取改進歐氏聚類的距離閾值，經(jīng)過多次實驗使所有點云圖中距原點5 m以內(nèi)的障礙物得到準(zhǔn)確聚類，得到距離閾值d1，再使距原點25 m到30 m內(nèi)的障礙物得到準(zhǔn)確聚類，得到距離閾值d2。距原點5 m以內(nèi)的障礙物共25個，距原點25 m到30 m內(nèi)的障礙物共30個，準(zhǔn)確聚類的數(shù)量變化分別如圖6和圖7。

圖6 距原點5 m以內(nèi)準(zhǔn)確聚類的數(shù)量變化

將d1、d2及對應(yīng)的距原點距離帶入式2中，經(jīng)過調(diào)整得到動態(tài)距離閾值d，準(zhǔn)確檢測到的障礙物有107個，準(zhǔn)確率為97.3%。由此可見改進歐氏聚類算法相比傳統(tǒng)歐氏聚類算法有明顯的提升。

采用傳統(tǒng)歐氏聚類算法聚類后的結(jié)果如圖8，限制聚類的最小點數(shù)為10。可以看出對于距離激光雷達較近的障礙物聚類效果較好，但將雷達后方的車輛分成了兩個聚類。這是因為距離閾值選擇較小，車輛障礙物點云內(nèi)部間距大于距離閾值。

圖8 傳統(tǒng)歐氏聚類結(jié)果

為了解決這一問題增加距離閾值，聚類結(jié)果如圖9?？梢钥闯鼍嚯x激光雷達較遠(yuǎn)的障礙物聚類效果較好，但將激光雷達后方的兩根電線桿聚成了一類?？梢钥闯鰝鹘y(tǒng)歐氏聚類算法具有一定的局限性，難以同時對近處和遠(yuǎn)處的障礙物進行準(zhǔn)確聚類。

圖9 傳統(tǒng)歐氏聚類結(jié)果2

改進后的歐氏聚類算法聚類后的結(jié)果如圖10，經(jīng)過多次實驗對α和β進行調(diào)整，可以看出對于近處和遠(yuǎn)處的障礙物都有較好的聚類效果，算法的抗干擾能力有了一定的提高，沒有發(fā)生誤檢。

圖10 改進歐氏聚類結(jié)果

3 結(jié) 語

針對傳統(tǒng)歐氏聚類算法在對分布不均的點云進行處理時存在的弊端，本文提出了一種改進歐氏聚類算法，能夠?qū)⒕嚯x閾值與障礙物點到激光雷達的距離關(guān)聯(lián)起來，通過動態(tài)選擇距離閾值，解決了傳統(tǒng)歐氏聚類算法的弊端，可以對不同距離的障礙物實現(xiàn)準(zhǔn)確檢測。后續(xù)將在障礙物檢測的基礎(chǔ)上完成對障礙物的識別工作。