張媛 施衛(wèi)

摘要：激光雷達(dá)作為自動駕駛不可或缺的傳感器，非地面點(diǎn)云聚類作為環(huán)境感知障礙物的重要環(huán)節(jié)，對自動駕駛汽車的安全至關(guān)重要。針對現(xiàn)有聚類方法出現(xiàn)的聚類不足、過度聚類和實(shí)時性差的問題，本文提出了一種從粗到細(xì)的聚類策略來平衡聚類的精度和速度。首先提出基于角度和距離判斷的聚類方法對點(diǎn)云進(jìn)行粗處理，然后采用基于斷點(diǎn)檢測的聚類方法對點(diǎn)云進(jìn)行細(xì)化，實(shí)現(xiàn)了目標(biāo)點(diǎn)云的精確分割。最后在公開的KITTI數(shù)據(jù)集上對本文提出的方法進(jìn)行了評估，實(shí)驗(yàn)結(jié)果表明，其分割準(zhǔn)確率達(dá)到82.2%，且分割時間較其他傳統(tǒng)算法明顯縮短，該算法具有良好的魯棒性。

關(guān)鍵詞：激光雷達(dá)；點(diǎn)云分割；聚類算法

中圖分類號：TP18? ? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2024）07-0008-04

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）

0 引言

隨著人工智能的發(fā)展，自動駕駛逐漸成為熱門話題。自動駕駛系統(tǒng)主要由感知、決策和控制三個模塊組成，是一個綜合性的智能控制系統(tǒng)[1]。其中，環(huán)境感知模塊是自動駕駛汽車的核心。它通過各種傳感器獲取汽車周圍的環(huán)境信息，為后續(xù)的信息處理提供數(shù)據(jù)基礎(chǔ)。

激光雷達(dá)作為自動駕駛非常重要的傳感器之一，它具有不受光干擾、信息豐富等優(yōu)點(diǎn)，其生成的點(diǎn)云數(shù)據(jù)具體處理流程如圖1所示。1） 點(diǎn)云濾波，去除干擾點(diǎn)云。2） 點(diǎn)云分割[2]：將濾波后的點(diǎn)云劃分為地面點(diǎn)和非地面點(diǎn)，再將非地面點(diǎn)云聚類為不同的簇。3） 檢測與識別[3]：地面點(diǎn)邊界提取，非地面點(diǎn)行人、車輛、建筑物等目標(biāo)的可行駛區(qū)域檢測與識別。4） 目標(biāo)跟蹤[4]：通過前后幀的相關(guān)性，利用卡爾曼濾波或粒子濾波對同一目標(biāo)進(jìn)行跟蹤。

分割作為處理原始點(diǎn)云數(shù)據(jù)的開始，聚類作為分割的一部分，其準(zhǔn)確性和時效性直接影響到整個自動駕駛。但在實(shí)際調(diào)查中，筆者發(fā)現(xiàn)由于點(diǎn)云數(shù)據(jù)量龐大且復(fù)雜，密度分布不均勻，實(shí)際駕駛場景復(fù)雜多變，現(xiàn)有的很多方法容易出現(xiàn)聚類過度和聚類不足的問題。

近年來，基于機(jī)器學(xué)習(xí)和深度學(xué)習(xí)的有監(jiān)督平面分割方法深受研究者青睞，Bichen Wu等人[5]利用卷積神經(jīng)網(wǎng)絡(luò)對LiDAR點(diǎn)云中的物體進(jìn)行語義分割，可以獲得實(shí)時性的結(jié)果。Qingyong Hu等人[6]引入了一種高效且輕量級的神經(jīng)架構(gòu)，該架構(gòu)使用隨機(jī)點(diǎn)采樣代替更復(fù)雜的點(diǎn)選擇方法來推斷大規(guī)模點(diǎn)云的逐點(diǎn)語義。GndNet[7]是一種新穎的端到端點(diǎn)云處理方法，它使用PointNet和Pillar特征編碼網(wǎng)絡(luò)來學(xué)習(xí)點(diǎn)特征，實(shí)現(xiàn)了對點(diǎn)云的實(shí)時語義分割。雖然深度學(xué)習(xí)方法可以實(shí)現(xiàn)較高的分割精度，且大部分都可以實(shí)現(xiàn)實(shí)時性，但基于深度學(xué)習(xí)的點(diǎn)云分割仍然存在很多問題，例如數(shù)據(jù)集的規(guī)模小，需要大量清晰的坐標(biāo)、強(qiáng)度和點(diǎn)云顏色的訓(xùn)練數(shù)據(jù)，導(dǎo)致無法在非結(jié)構(gòu)化的點(diǎn)云模型組成的場景中進(jìn)行分割。此外，深度學(xué)習(xí)的計算成本很高，需要專用的GPU設(shè)備實(shí)現(xiàn)。相比之下，傳統(tǒng)的無監(jiān)督方法在許多情況下仍然以其易于操作和高可靠性而受到青睞[8]。一般來說，無監(jiān)督平面分割方法可以分為三大類：區(qū)域生長法、基于模型擬合的方法和基于聚類的方法。

基于聚類的方法是不同方法的混合體，這些方法有一個共同的目標(biāo)：將具有相似幾何光譜特征或空間分布的點(diǎn)分組到相同的同質(zhì)神經(jīng)模式中。與區(qū)域增長和模型擬合不同，這些模式通常不是預(yù)定義的，因此基于聚類的算法可以用于不規(guī)則目標(biāo)分割，而且基于聚類的方法比監(jiān)督方法計算量少。

1 點(diǎn)云預(yù)處理

1.1 點(diǎn)云濾波

3D點(diǎn)云數(shù)據(jù)具有稀疏性、無序性、無結(jié)構(gòu)性和數(shù)據(jù)量大等特點(diǎn)。在分離障礙物點(diǎn)云之前，首先需要對激光雷達(dá)獲得的點(diǎn)云進(jìn)行濾波，去除無效目標(biāo)點(diǎn)云，降低點(diǎn)云數(shù)據(jù)的密度，以減少計算量和內(nèi)存占用[9]。下采樣濾波可用于去除點(diǎn)云數(shù)據(jù)中的冗余信息，提高點(diǎn)云數(shù)據(jù)的處理速度和效率。傳統(tǒng)的體素濾波是通過輸入的點(diǎn)云數(shù)據(jù)創(chuàng)建一個三維體素柵格，然后將每個體素內(nèi)所有的點(diǎn)都用該體素內(nèi)的代表點(diǎn)（重心）來近似，這樣可以大大減少數(shù)據(jù)量。體素濾波器旨在實(shí)現(xiàn)向下采樣，同時不破壞點(diǎn)云本身的幾何結(jié)構(gòu)，還可以去除一定程度的噪音點(diǎn)和離群點(diǎn)，但會移動點(diǎn)的位置。

本文采用均勻采樣濾波器[10]對原始點(diǎn)云進(jìn)行下采樣。通過構(gòu)建指定半徑為0.01m的球體對點(diǎn)云進(jìn)行下采樣濾波，將每一個球內(nèi)距離球體中心最近的點(diǎn)作為下采樣后的點(diǎn)輸出。與體素濾波相比，通過均勻采樣濾波器下采樣后，點(diǎn)云基本分布均勻，且沒有移動點(diǎn)的位置。如圖2所示，左圖為原始點(diǎn)云數(shù)據(jù)，右圖為濾波后的點(diǎn)云數(shù)據(jù)。

1.2 去除地面點(diǎn)云

對于濾除后的點(diǎn)云采用平面模型估計：[Ax+By+Cz+D=0]，即表示為[nTx=-d]，其中[n=a，b，cT]，[x=x，y，zT]，通過初始點(diǎn)集的協(xié)方差矩陣[c∈R3×3]來求解[n]，從而確定一個平面。筆者采用種子點(diǎn)集[S∈R3]作為初始點(diǎn)集，其協(xié)方差矩陣為：

[C=i=1：ssi-ssi-sT]

式中：[s]為所有點(diǎn)的均值，協(xié)方差矩陣[C]描述了種子點(diǎn)集的散布情況，其三個奇異向量可以通過奇異值分解（Singular Value Decomposition） 求得，這三個奇異向量描述了點(diǎn)集在三個主要方向的散布情況。由于是平面模型，垂直于平面的法向量n表示具有最小方差的方向，可以通過計算具有最小奇異值的奇異向量來求得，并將n代入平面方程后可求出D，進(jìn)而得到平面模型[11]。

得到平面模型以后，接著計算點(diǎn)云中每一個點(diǎn)到該平面的正交投影的距離，并且將這個距離與設(shè)定的閾值[Th]比較，當(dāng)高度差小于此閾值，認(rèn)為該點(diǎn)屬于地面，當(dāng)高度差大于此閾值，則為非地面點(diǎn)。經(jīng)過分類以后的所有地面點(diǎn)被當(dāng)作下一次迭代的種子點(diǎn)集，迭代優(yōu)化，最終得到去除地面點(diǎn)的目標(biāo)點(diǎn)云數(shù)據(jù)。

2 改進(jìn)聚類算法

本文提出了一種由粗到精的聚類策略，以達(dá)到準(zhǔn)確和實(shí)時的聚類結(jié)果。具體實(shí)施方法是輸入非地面點(diǎn)云，首先根據(jù)鄰域點(diǎn)的角度和距離準(zhǔn)則進(jìn)行粗聚類，然后再通過自適應(yīng)斷點(diǎn)檢測進(jìn)行聚類細(xì)化，最終輸出精細(xì)聚類結(jié)果。在這一部分中，主要是對去除地面點(diǎn)后剩下的點(diǎn)云進(jìn)行處理，將非地面點(diǎn)數(shù)學(xué)描述為：[Png=Pk=xk，yk，zk，k=1，2，…，n]。這樣可以充分發(fā)揮距離圖像鄰域關(guān)系清晰、獲取方便、計算速度快的優(yōu)點(diǎn)。

2.1 基于角度和距離判斷的粗聚類

首先，使用角度判斷非地面點(diǎn)云是否為我們所需要的點(diǎn)云，如圖3所示，圖像相鄰的兩個點(diǎn)P1、P2與激光雷達(dá)發(fā)射原點(diǎn)之間形成夾角，假設(shè)兩束光束中較長的光束所在直線為y軸，相鄰光束之間的夾角為α，α是激光雷達(dá)在水平或垂直方向上的角分辨率，這主要是由激光的型號決定的。

其中：OP1與OP2的長度表示相鄰點(diǎn)的深度值，分別為d1、d2。H為點(diǎn)P1在OP2線上的投影，角度[β]為P1P2與OP2的夾角，用于判斷P1和P2是否屬于同一聚類對象， [β]的大小可以用公式計算：

[β=arctanP1HP2H=arctand1sinad2-d1cosα]

通過大量計算圖像上任意行或列中P1和P2相鄰點(diǎn)對應(yīng)的[β]，發(fā)現(xiàn)相鄰點(diǎn)屬于不同聚類的[β]值一般較小，相鄰點(diǎn)屬于同一聚類的[β]值較大。對此方法[12]進(jìn)行優(yōu)化，加入距離判斷條件，即考慮相鄰點(diǎn)之間的距離差，距離差[Δd=d1-d2]。結(jié)合上述兩個判斷條件，預(yù)先定義角度閾值參數(shù)[θ]和距離閾值參數(shù)[dth]，因此，當(dāng)[β>θ]且[?d

加入深度距離判斷之后，在處理點(diǎn)云多平面場景聚類時，有效解決了部分平面過度分割的問題。然而，在目標(biāo)邊緣或多個目標(biāo)相接近時，仍然容易產(chǎn)生分割過度或者分割不足的情況。因此，在粗聚類的基礎(chǔ)上還要對聚類目標(biāo)進(jìn)行細(xì)化。

2.2 基于自適應(yīng)斷點(diǎn)檢測的聚類優(yōu)化

針對粗聚類會產(chǎn)生一個聚類被分割成多個目標(biāo)的過分割問題和兩個聚類錯誤聚在一起的欠分割問題，需要在聚類過程中進(jìn)一步融合滿足連通性要求的小聚類。在此過程中，主要使用基于鄰域策略的自適應(yīng)斷點(diǎn)檢測來改進(jìn)聚類。

KNN[13]算法因其簡單易操作受到廣泛的運(yùn)用，其工作原理可以簡單概括為：在一個已知類別的數(shù)據(jù)集中，對于未知類別的任意一個數(shù)據(jù)點(diǎn)，根據(jù)最近的[k]數(shù)據(jù)類別進(jìn)行投票，從而實(shí)現(xiàn)對未知數(shù)據(jù)的分類，通常取[k]為奇數(shù)值，以防止判別的模糊性。如圖4所示，問號中心點(diǎn)的類別可以根據(jù)[k]最近鄰點(diǎn)來確定。計算得到的距離值[dx，y]采用歐幾里得距離，公式如下：

[dx，y=x，-y12+x2-y22+…+xn-yn2]

[=i=1nxi-yi2]

在KNN算法運(yùn)行的過程中，需要計算所有鄰域點(diǎn)的距離，并預(yù)設(shè)合適的[k]值，才能獲得滿意的結(jié)果，耗時長且不方便。為了獲得快速的計算效率，本文沒有使用KNN算法，而是使用了更輕量級的RBNN算法[14]。它通過預(yù)定義的半徑[r]對未知數(shù)據(jù)點(diǎn)進(jìn)行分類，該算法的優(yōu)點(diǎn)是不需要對每個節(jié)點(diǎn)執(zhí)行最近領(lǐng)域搜索，不涉及圖像切割和重新排列圖形結(jié)構(gòu)。

在實(shí)際操作過程中發(fā)現(xiàn)，預(yù)設(shè)的[r]值難以獲得滿意的結(jié)果，而且部分兩點(diǎn)夾角比較小的點(diǎn)云難以準(zhǔn)確聚類?？梢詫r]值進(jìn)行相應(yīng)改進(jìn)，增加斷點(diǎn)檢測功能，在聚類過程中可以避免聚類不連續(xù)點(diǎn)出現(xiàn)。設(shè)置斷點(diǎn)標(biāo)志[kbn]，如果點(diǎn)[Pn]是斷點(diǎn)，那么標(biāo)志[kbn]和[kbn-1]都應(yīng)該設(shè)置為TRUE，可表述為：if[ pn-pn-1>Dmax]

then[Kbn]：=TURE，and[kbn-1]：=TURE

式中：[pn-Pn-1]為相鄰點(diǎn)[pn]和[pn-1]之間的歐幾里得距離，[Dmax]為距離閾值，這在RBNN算法中是一個常數(shù)，但很難滿足點(diǎn)云密度隨距離變化的特點(diǎn)。所以，筆者采用自適應(yīng)閾值檢測方法，如圖5所示，[pn-2]、[pn-1]和[pn]為相鄰點(diǎn)，以點(diǎn)[pn-1]定義一條虛線，該虛線相對于掃描方向[τn-1]產(chǎn)生的夾角[η]，可以推斷最差可接受范圍點(diǎn)[Pn]。在此約束條件下，設(shè)定第[n]個點(diǎn)的距離[rhn]與[rn-1]有關(guān)，用公式表示：

[rhnrn-1=sinηsinn-Δτ]

[Phn-Pn-1=rn-1·sinΔτsinn-Δτ]

式中：[Phn-Pn-1]為斷點(diǎn)檢測閾值，[Phn]為第n個假設(shè)斷點(diǎn)，并增加[3×σ]的冗余范圍，以處理檢測過程中可能出現(xiàn)的噪聲情況。因此，最終的自適應(yīng)閾值表示為：

[Dmax=Phn-Pn-1+3σ]

最終的自適應(yīng)斷點(diǎn)檢測器表示一個以點(diǎn)[Pn-1]為中心，半徑為[Dmax]的閾值圓，如果下一個[Pn]在閾值圓內(nèi)，則將[Pn]點(diǎn)添加到[Pn-1]集群中，得到最終的精細(xì)化結(jié)果。

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

為了驗(yàn)證本文提出的算法實(shí)際效果，在Linux平臺Ubuntu18.04上基于PCL1.9.1實(shí)現(xiàn)。實(shí)驗(yàn)所使用的數(shù)據(jù)來源是公開的KITTI數(shù)據(jù)集[15]，其數(shù)據(jù)采集是搭載一個Velodyne HDL-64E激光掃描儀，它以每秒10幀的速度旋轉(zhuǎn)，每個周期捕獲大約100k個點(diǎn)。

如圖6（a） 所示為原始點(diǎn)云鳥瞰圖，點(diǎn)云龐雜且混亂，因激光掃描目標(biāo)過多或激光雷達(dá)抖動造成的無效目標(biāo)點(diǎn)云。經(jīng)過本文采用的點(diǎn)云預(yù)處理方法，在沒有改變原始點(diǎn)云特性的基礎(chǔ)上，濾除了遠(yuǎn)處大量的離群點(diǎn)噪音點(diǎn)，且去除了不必要的地面點(diǎn)云，如圖6（b） 所示，只針對目標(biāo)點(diǎn)云進(jìn)行聚類算法的研究。

圖7為分別采用傳統(tǒng)的聚類分割算法和本文提出的聚類方法的結(jié)果，其對目標(biāo)點(diǎn)云的分割效果明顯不同。其中：（a） 為區(qū)域生長分割。（b） 為歐式聚類分割。（c） 為DBSCAN聚類分割。（d） 為本文方法的分割。其中區(qū)域生長分割和DBSCAN聚類分割存在分割不足的情況，而歐式聚類分割則存在過度分割的問題，本文提出的從粗到細(xì)的聚類方法分割效果更好，一定程度上解決了傳統(tǒng)聚類方法造成的分割不足或過度的問題。同時，對于點(diǎn)云目標(biāo)分割的準(zhǔn)確率和每種算法所消耗的時間如表1所示，本文提出的方法不僅分割準(zhǔn)確率更高，且耗時較短。

4 結(jié)束語

本文提出了一種基于改進(jìn)聚類算法的目標(biāo)點(diǎn)云分割方法。該方法針對非地面點(diǎn)云進(jìn)行處理，在距離圖像上利用快速鄰域搜索的特點(diǎn)，可以達(dá)到較高的粗聚類效率。自適應(yīng)斷點(diǎn)檢測可以解決粗糙聚類中聚類過度和聚類不足的問題。將本文所提方法與幾種常用的點(diǎn)云聚類分割方法進(jìn)行了比較，結(jié)果表明，所提方法聚類效果更好，耗時較短。

參考文獻(xiàn)：

[1] 王涔宇，張平.汽車自動駕駛關(guān)鍵技術(shù)分析[J].汽車實(shí)用技術(shù)，2021，46（23）：20-22，29.

[2] WANG W Q，YOU X，YANG J，et al.LiDAR-based real-time panoptic segmentation via spatiotemporal sequential data fusion[J].Remote Sensing，2022，14（8）：1775.

[3] 伍錫如，薛其威.基于激光雷達(dá)的無人駕駛系統(tǒng)三維車輛檢測[J].光學(xué) 精密工程，2022，30（4）：489-497.

[4] 顧立鵬，孫韶媛，劉訓(xùn)華，等.基于激光點(diǎn)云坐標(biāo)系的3D多目標(biāo)跟蹤算法研究[J].激光與紅外，2021，51（10）：1307-1313.

[5] WU B C，WAN A，YUE X Y，et al.SqueezeSeg：convolutional neural nets with recurrent CRF for real-time road-object segmentation from 3D LiDAR point cloud[C]//2018 IEEE International Conference on Robotics and Automation （ICRA）.ACM，2018：1887-1893.

[6] HU Q Y，YANG B，XIE L H，et al.RandLA-net：efficient semantic segmentation of large-scale point clouds[C]//2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition （CVPR）.June 13-19，2020.Seattle，WA，USA.IEEE，2020：11108-11117.

[7] PAIGWAR A，ERKENT ?，SIERRA-GONZALEZ D，et al.GndNet：fast ground plane estimation and point cloud segmentation for autonomous vehicles[C]//2020 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）.ACM，2020：2150-2156.

[8] CHEN H，LIANG M，LIU W Q，et al.An approach to boundary detection for 3D point clouds based on DBSCAN clustering[J].Pattern Recognition，2022，124：108431.

[9] 趙涵，劉永生，趙德鵬，等.基于混合濾波的點(diǎn)云去噪算法研究[J].應(yīng)用激光，2023，43（9）：147-155.

[10] 肖正濤，高健，吳東慶，等.一種基于體素網(wǎng)格的三維點(diǎn)云均勻降采樣方法[J].機(jī)械設(shè)計與制造，2023（8）：180-184.

[11] 丁鴿，燕立爽，彭健，等.基于RANSAC算法的隧道點(diǎn)云橫斷面提取[J].測繪通報，2021（9）：120-123.

[12] BOGOSLAVSKYI I，STACHNISS C.Fast range image-based segmentation of sparse 3D laser scans for online operation[C]//2016 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）.IEEE，2016：163-169.

[13] 楊曉文，王愛兵，韓燮，等.基于KNN-PointNet的點(diǎn)云語義分割[J].激光與光電子學(xué)進(jìn)展，2021，58（24）：272-279.

[14] KLASING K，WOLLHERR D，BUSS M.A clustering method for efficient segmentation of 3D laser data[C]//2008 IEEE International Conference on Robotics and Automation.May 19-23，2008.Pasadena，CA，USA.IEEE，2008：4043-4048.

[15] CORDTS M， OMRAN M， RAMOS S， et al. The cityscapes dataset[C]//CVPR Workshop on the Future of Datasets in Vision. sn， 2015， 2.

【通聯(lián)編輯：唐一東】