基于改進歐式聚類的三維激光雷達點云目標分割方法

姚紹華， 賀 松， 涂園園

（貴州大學 大數據與信息工程學院， 貴陽 550025）

0 引 言

三維激光雷達有著較高的測量準確性、較大的探測范圍以及不受光照條件影響的抗干擾能力，這些優勢使其成為了環境主動感知領域的一項關鍵技術，在智能駕駛、移動機器人等領域得到廣泛的應用［1］。 三維激光雷達掃描產生的點云是一系列無序的點，點與點之間無拓撲關系，要實現對環境周圍目標的識別，首先，關鍵內容就是要對點云進行聚類分割，使其成為一個個獨立的子集，每個子集都有相對照的物理目標，這為后續的目標分類或識別提供了重要基礎。 進一步也表明分割的準確程度將直接影響后續的處理效果。 因此研究一種能提高分割準確率的分割方法是非常有必要的。

目前，點云分割算法主要基于從幾何約束和統計規則出發制定的嚴格的人工設計的特征。 分割的主要過程是將原始3D 點分組為非重疊區域。 這些區域對應于一個場景中的特定結構或對象。 由于這種分割過程不需要有監督的先驗知識，因此所得到的結果沒有很強的語義信息。 這些方法可以分為基于邊緣的、基于區域增長的、基于模型擬合的和基于聚類的4 種方法［2］。 其中，基于邊緣的分割方法是通過定位亮度快速變化的點，這類似于一些二維圖像分割方法。 此方法雖然可以簡單快速運行，但只適用于簡單場景，對于密集和大面積的點云數據集處理效果不佳。 基于區域增長的分割方法是一種經典的分割方法，通過將2 個點或2 個區域單元之間的特征相結合，以測量像素（2D）、點（3D）或體素（3D）之間的相似性，并將其合并在一起。 此算法的精度依賴于種子的生長準則和位置，且計算量大，不利于智能駕駛系統的實時性。 模型擬合的核心思想是將點云與不同的原始幾何圖形進行匹配，通常被認為是一種形狀檢測或提取方法。 RANSAC 技術就是一種流行的模型擬合方法，但該算法必須手動定義或選擇模型，通常是平面、球體或其他可以用代數公式表示的幾何圖元，不適用于交通道路上的障礙物分割［3］。 基于聚類的方法廣泛應用于無監督分割任務［4］，該算法是具有相同目標的不同方法的混合，即將具有相似幾何譜特征或空間分布的點組合成相同的均勻模式。 與區域生長和模型擬合不同，這些模式通常沒有預先定義，因此基于聚類的算法可用于不規則對象分割。 對于每種聚類方法，可以選擇具有不同特征的幾個相似性度量，包括歐幾里德距離、密度和法向量。

為了滿足目標點云分割算法的準確性要求，本文基于傳統歐幾里得聚類算法，提出了一種優化算法來分割目標。 由于點云數據具有近密遠疏的特點，將距離閾值變為根據距離改變的可變閾值，并同時考慮距離閾值與角度閾值，增加分割的可靠性。

1 基本工作

1.1 數據預處理

1.1.1 下采樣

通過車載激光掃描系統獲取的車載LiDAR 點云數據是海量的，且存在數據冗余，為了便于后續處理，需對點云數據進行下采樣，減少點云數量，以減少后續處理時間。

1.1.2 地面去除

本文認為需要檢測的目標均在地面之上，目標點云與地面點云相連接，若直接進行分割操作，可能造成分割結果不理想。 因此將地面移除后，目標點云會相互分離，再利用聚類算法對目標點云進行聚類分割。 傳統的地面點云去除算法是將地面建模為一個固定平面或者二次曲面，但大都依賴于固定閾值［5］，而且現實情況下的路面點云并不是一個標準的曲面模型。 本文采用多尺度網格的點云濾波算法，通過找到地面種子點并將其他點的高度與其比較，判斷網格中的點是否為地面點，從而分離點云數據中的地面點和非地面點。 對此擬做探討闡釋如下。

（1）多尺度網格構建。 激光雷達掃描得到的點云數據是一系列無序的點，但每個點都包含了相應的空間坐標信息，由此可以引入虛擬網格概念。 多尺度網格的示意圖如圖1 所示。

圖1 多尺度網格示意圖Fig.1 Multi-scale grid diagram

圖1（a）中，黑點表示點云數據，長方體表示相應尺度的網格；圖1（b）中，即為在虛擬網格內將三維坐標點投影到X - Y平面，方格的顏色深淺表示虛擬網格尺度的大小。 由此可知，將點云數據按照其X-Y坐標建立網格索引，這樣每個點均可通過索引快速查詢。

點云網格間的索引關系計算公式為：

其中，X，Y為網格號；x，y為點云的平面坐標；xmin，ymin為整個數據集的最小平面坐標；m為網格單元的尺度；INT 表示對計算結果向下取整。

（2）地面去除。 點云網格化處理后，在每個網格內搜尋最低點作為種子點，并通過將網格中的其他點與種子點比較判斷該點是否為地面點。 為了防止最低點在地面以下，即非地面點，本文將最低點加上0.13 作為種子點的高度，再進行比較。 然后保留非地面點，最終實現對地面點云的去除。

1.2 聚類

聚類算法是一種無監督算法，由于不需要訓練集，而且算法簡單快速，已經廣泛應用于圖像處理、數據挖掘以及模式識別等領域。 歐式聚類是一種基于歐式距離度量的聚類算法［6］，基于KD-Tree 的近鄰查詢算法，計算鄰域點到該點的歐氏距離，將在閾值范圍內的點聚為一類，通過反復迭代，直到沒有新點加入為止［7］。 具體數學公式可寫為：

其中，qi，pi∈Q，Q是一個點云集。 歐式聚類流程步驟如圖2 所示。

圖2 歐式聚類流程圖Fig.2 Euclidean clustering flowchart

通過歐氏聚類進行分割的效果主要由設置的距離閾值決定，當設置的閾值過大時，會出現過分割現象，反之，則出現欠分割情形［8］。 同時點云數據具有近密遠疏的特點，如何設置合適的閾值成為一個關鍵問題。 本文根據目標到激光雷達的距離動態的選擇閾值，來避免使用同一閾值產生的過分割或欠分割問題。 動態閾值可根據式（3）來設置：

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

然而僅通過距離閾值判斷，在相鄰的行人目標上還是容易出現欠分割問題，如圖3 所示。 由于激光雷達中的多個激光器水平掃描周圍環境中的物體［9］，相鄰2 個行人腿部之間形成的夾角相較于屬于同一物體內點與點之間形成的夾角要大一些，如圖4 所示。 研究中可以充分利用這一特點，在高度小于行人腿部的種子點進行聚類時設置一角度閾值，將小于角度閾值的點歸于同一物體，這樣同時利用動態距離閾值和角度閾值可較好地處理相鄰行人目標的欠分割問題。

圖3 相鄰目標欠分割問題Fig.3 Adjacent target under-segmentation problem

圖4 行人點云Fig.4 Pedestrian point cloud

2 實驗結果與分析

為驗證本文方法的有效性，利用自動駕駛領域內比較知名的KITTI 數據集。 數據集由1 臺車載Velodyne HDL-64E 激光所采集，掃描頻率10 Hz，64線，角度分辨率0.09°探測精度2 cm，每秒130 萬點數，探測距離120 m。 計算所使用的電腦配置為：Intel 4.1 GHz i5-10600 CPU，16 GB 內存。 編程環境為C++。

在數據集中隨機抽取20 張激光雷達數據進行試驗，在對數據進行聚類之前，先進行預處理，原始點云圖如圖5 所示，預處理后的點云圖如圖6 所示。

圖5 原始點云圖Fig.5 Original point cloud

圖6 預處理后的點云圖Fig.6 Point cloud after pretreatment

通過多次實驗將點云圖中離原點5 m 以內的障礙物能得到較好聚類結果的閾值0.1 設為d1， 再將使距原點10 m 到20 m 內的障礙物能得到較好聚類結果的閾值0.25 設為d2。 將d1、d2以及對應范圍到原點的距離代入式（3）中， 經過調整得到相應的α和β的值。 即：

接著進行歐式聚類，當聚類的中心點的高度小于0.3 m 時加入角度閾值，使角度小于0.4°且滿足對應歐式距離閾值的點聚類為一類。 傳統歐氏聚類結果和改進的歐氏聚類結果如圖7 所示，不同的目標用不同的顏色顯示。 傳統歐式聚類算法依賴固定閾值，一些相鄰目標并沒有被分割開，出現了欠分割問題。 而由圖7（b）可以看出，本文提出的算法可將相鄰行人較好地分割開來。 為了使結果更可靠，通過對點云數據選取200 個目標進行人工標記，以此作為準確率Acc計算的參考。 準確率的計算如下：

圖7 點云目標分割結果Fig.7 Point cloud target segmentation results

其中，S1是準確分割的數量，S是總目標數量。

分別通過傳統歐式聚類算法和本文提出算法進行處理，計算2 種算法的準確率。 2 種算法的結果見表1。 由表1 結果可知，本文提出的算法準確率達到了86%，而傳統歐式聚類算法的準確率只有83.5%，本文提出算法的準確率提高了約2.5%。 但對于行人目標來說，本文提出的算法準確率達到了88.02%，相傳較于傳統歐式聚類算法82.6%的準確率，提升了約5.4%。 說明本文提出算法能夠有效地提高點云目標分割的準確度，并且與分割汽車目標相比對行人目標的分割具有更好的分割效果。

表1 傳統算法與本文算法結果比較Tab.1 Comparison of results between traditional algorithm and this algorithm

3 結束語

提出了一種基于歐幾里得聚類的改進算法，將原始點云圖下采樣后經過多尺度網格去除地面點云，然后根據預處理后的點云圖中目標到原點的距離動態地選擇距離閾值，同時加入角度閾值一同判斷，較好地克服了相鄰行人目標的欠分割問題。 通過實驗進行驗證，結果表明本文提出方法在分割目標上準確度提高約2.5%，而在對行人目標的分割上提升了約5.4%，為點云目標的分割提供了一種新思路，是一種較為有效的方法。 但在處理時間上并未取得較好效果，實時性不足，如何改進算法減少分割時間將是下階段研究的重點。