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

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

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

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

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

1 歐氏聚類分割

1.1 確定距離閾值

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

(1)

1.2 近鄰搜索算法

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

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

圖1 Octree原理

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

圖2 KD-Tree流程圖

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

1.3 改進歐氏聚類算法

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

算法共分為四步：

(1)通過KD-Tree建立點云cloud中離散點之間的拓撲關系；

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

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

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

(2)

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

2 實驗驗證

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

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

圖3 原始點云圖

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

a)側視圖 b)俯視圖

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

圖5 準確聚類的數量變化

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

圖6 距原點5 m以內準確聚類的數量變化

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

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

圖8 傳統歐氏聚類結果

為了解決這一問題增加距離閾值，聚類結果如圖9。可以看出距離激光雷達較遠的障礙物聚類效果較好，但將激光雷達后方的兩根電線桿聚成了一類。可以看出傳統歐氏聚類算法具有一定的局限性，難以同時對近處和遠處的障礙物進行準確聚類。

圖9 傳統歐氏聚類結果2

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

圖10 改進歐氏聚類結果

3 結 語

針對傳統歐氏聚類算法在對分布不均的點云進行處理時存在的弊端，本文提出了一種改進歐氏聚類算法，能夠將距離閾值與障礙物點到激光雷達的距離關聯起來，通過動態選擇距離閾值，解決了傳統歐氏聚類算法的弊端，可以對不同距離的障礙物實現準確檢測。后續將在障礙物檢測的基礎上完成對障礙物的識別工作。