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

姚紹華， 賀 松， 涂園園

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

0 引 言

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

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

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

1 基本工作

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

1.1.1 下采樣

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

1.1.2 地面去除

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

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

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

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

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

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

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

1.2 聚類

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

其中，qi，pi∈Q，Q是一個(gè)點(diǎn)云集。 歐式聚類流程步驟如圖2 所示。

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

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

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

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

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

圖4 行人點(diǎn)云Fig.4 Pedestrian point cloud

2 實(shí)驗(yàn)結(jié)果與分析

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

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

圖5 原始點(diǎn)云圖Fig.5 Original point cloud

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

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

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

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

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

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

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

3 結(jié)束語

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