基于改進(jìn)歐式聚類的三維激光雷達(dá)點云目標(biāo)分割方法

姚紹華， 賀 松， 涂園園

（貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院， 貴陽 550025）

0 引 言

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

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

為了滿足目標(biāo)點云分割算法的準(zhǔn)確性要求，本文基于傳統(tǒng)歐幾里得聚類算法，提出了一種優(yōu)化算法來分割目標(biāo)。 由于點云數(shù)據(jù)具有近密遠(yuǎn)疏的特點，將距離閾值變?yōu)楦鶕?jù)距離改變的可變閾值，并同時考慮距離閾值與角度閾值，增加分割的可靠性。

1 基本工作

1.1 數(shù)據(jù)預(yù)處理

1.1.1 下采樣

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

1.1.2 地面去除

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

（1）多尺度網(wǎng)格構(gòu)建。 激光雷達(dá)掃描得到的點云數(shù)據(jù)是一系列無序的點，但每個點都包含了相應(yīng)的空間坐標(biāo)信息，由此可以引入虛擬網(wǎng)格概念。 多尺度網(wǎng)格的示意圖如圖1 所示。

圖1 多尺度網(wǎng)格示意圖Fig.1 Multi-scale grid diagram

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

點云網(wǎng)格間的索引關(guān)系計算公式為：

其中，X，Y為網(wǎng)格號；x，y為點云的平面坐標(biāo)；xmin，ymin為整個數(shù)據(jù)集的最小平面坐標(biāo)；m為網(wǎng)格單元的尺度；INT 表示對計算結(jié)果向下取整。

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

1.2 聚類

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

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

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

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

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

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

圖3 相鄰目標(biāo)欠分割問題Fig.3 Adjacent target under-segmentation problem

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

2 實驗結(jié)果與分析

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

在數(shù)據(jù)集中隨機(jī)抽取20 張激光雷達(dá)數(shù)據(jù)進(jìn)行試驗，在對數(shù)據(jù)進(jìn)行聚類之前，先進(jìn)行預(yù)處理，原始點云圖如圖5 所示，預(yù)處理后的點云圖如圖6 所示。

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

圖6 預(yù)處理后的點云圖Fig.6 Point cloud after pretreatment

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

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

圖7 點云目標(biāo)分割結(jié)果Fig.7 Point cloud target segmentation results

其中，S1是準(zhǔn)確分割的數(shù)量，S是總目標(biāo)數(shù)量。

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

表1 傳統(tǒng)算法與本文算法結(jié)果比較Tab.1 Comparison of results between traditional algorithm and this algorithm

3 結(jié)束語

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