基于改進聚類算法的目標點云分割

張媛 施衛

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

關鍵詞：激光雷達；點云分割；聚類算法

中圖分類號：TP18? ? ? ? 文獻標識碼：A

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

開放科學（資源服務）標識碼（OSID）

0 引言

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

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

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

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

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

1 點云預處理

1.1 點云濾波

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

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

1.2 去除地面點云

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

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

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

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

2 改進聚類算法

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

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

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

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

[β=arctanP1HP2H=arctand1sinad2-d1cosα]

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

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

2.2 基于自適應斷點檢測的聚類優化

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

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

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

[=i=1nxi-yi2]

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

在實際操作過程中發現，預設的[r]值難以獲得滿意的結果，而且部分兩點夾角比較小的點云難以準確聚類?？梢詫r]值進行相應改進，增加斷點檢測功能，在聚類過程中可以避免聚類不連續點出現。設置斷點標志[kbn]，如果點[Pn]是斷點，那么標志[kbn]和[kbn-1]都應該設置為TRUE，可表述為：if[ pn-pn-1>Dmax]

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

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

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

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

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

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

最終的自適應斷點檢測器表示一個以點[Pn-1]為中心，半徑為[Dmax]的閾值圓，如果下一個[Pn]在閾值圓內，則將[Pn]點添加到[Pn-1]集群中，得到最終的精細化結果。

3 實驗結果與分析

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

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

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

4 結束語

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

參考文獻：

[1] 王涔宇，張平.汽車自動駕駛關鍵技術分析[J].汽車實用技術，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] 伍錫如，薛其威.基于激光雷達的無人駕駛系統三維車輛檢測[J].光學 精密工程，2022，30（4）：489-497.

[4] 顧立鵬，孫韶媛，劉訓華，等.基于激光點云坐標系的3D多目標跟蹤算法研究[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] 趙涵，劉永生，趙德鵬，等.基于混合濾波的點云去噪算法研究[J].應用激光，2023，43（9）：147-155.

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

[11] 丁鴿，燕立爽，彭健，等.基于RANSAC算法的隧道點云橫斷面提取[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的點云語義分割[J].激光與光電子學進展，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.

【通聯編輯：唐一東】