基于自適應閾值的循環增長地面點云分割算法

董濤濤, 宋宇博

(蘭州交通大學機電技術研究所, 蘭州 730070)

在傳感器技術發展的推動下無人駕駛技術迅猛發展。激光雷達因受光線影響較小,具有視野廣闊、距離信息精度高、獲取目標物體三維信息豐富的特點而被廣泛應用[1-4]。由于點云數據中包含有大量的被視為冗余信息[5]的地面點云等背景點,所以在簡化數據時,濾除地面點云具有重要意義[6]。目前地面點云分割算法依據分割策略大致分為基于掃描線和基于空間劃分兩大類[7]。

激光雷達在理想平面掃描時,形成的掃描線接近于圓形,當遇到障礙物時掃描線就會發生變化。利用這一特點,基于掃描線的分割方法通過分析掃描線上點之間的變化和掃描線之間的差異來分割點云。文獻[8]針對矮小障礙物設計了通過計算單束激光線上相鄰點間距離及高度差特征、曲率特征來分割地面點云的方法。為避免特征值的復雜計算,文獻[9]分析了相鄰激光線間距離特征,提出將距離小于閾值的掃描線分為障礙物的分割方法,此方法提高了分割實時性,但是分割精度與魯棒性較差。文獻[10]結合道路分布特征和激光雷達線束分布特征的將點云劃分多區域完成地面分割,該方法能有效改善分割效果,卻由于計算多個平面模型參數導致實時性較差。文獻[11]將掃描線分割與窗口濾波相結合,利用移動窗口算子逐行對非接地點濾波,但是窗口大小對濾波效果影響較大。文獻[12]按照掃描線將點云劃分為扇形網格,并將網格內最低點作為種子,利用坡度與高程特征生長形成地面,該方法只適用于較明顯障礙物場景下。由于掃描線的分割方法對道路平坦度較敏感,在平坦城市道路中可以取得較好分割效果,但在崎嶇道路中掃描線分布不均,對分割精度與分割效率影響較大。

基于空間劃分的方法是將點云數據劃分為不同網格,通過計算不同特征值進行點云數據分割。二維網格分割方法是基于空間劃分分割方法的重要應用。文獻[13]在二維柵格內利用平均高度進行閾值分割,而文獻[14]則利用高程差進行分割,兩種方法均為單一閾值分割。文獻[15]為解決單一閾值影響分割精度的問題,提出了一種集高度差、平均高度、高度方差3種分割指標為一體的快速分割方法,然而對于一個指標就可判斷的柵格進行多個指標的計算會產生冗余計算,存在不必要的耗時。文獻[16]在柵格地圖的基礎上利用徑向距離、梯度、高程差判斷各個節點屬性尋找基準鏈,然后進行地面屬性蔓延,在一定程度上提高了算法的實時性。文獻[17]為解決柵格法中局部信息突出,忽略全局信息的問題,提出一種基于標準差閾值圓增長判斷的方法,但是對存在較大平面障礙物的場景會造成過分割,魯棒性不足。

針對坡度和路面起伏不平的場景中點云分割存在的問題,現提出一種改進的柵格法。利用循環增長判斷法兼顧局部特征與全局特征的能力解決傳統柵格法對柵格大小敏感的問題。利用標準差擬合地面波動幅度,從而構建自適應高度閾值,并且設計觸發式雙特征判斷機制,解決柵格法中單一閾值敏感性不足和多閾值帶來冗余計算的問題。

1 分割算法

提出的分割算法包括數據預處理、點云分割兩個階段。預處理階段主要工作是從原始點云中篩選出初始地面點集,然后進行柵格儲存。分割階段則首先是給柵格儲存的點云確定自適應閾值,然后利用觸發式判斷機制進行循環增長判斷,從而合理分割出地面點云與非地面點云。

1.1 點云預處理

點云預處理階段的目的就是減少數據量,并且將點云數據進行柵格存儲。包含數據獲取、初始地面點集篩選、柵格存儲3個部分。

1.1.1 數據獲取

原始數據為三維激光雷達單幀點云數據,每幀數據約包含幾萬甚至十幾萬個點。設第i幀點云為Ai={a1,a2,…,aN},其中:N為點云數據點總數;

ai={xi,yi,zi}為第i個數據點在激光雷達坐標系下的三維坐標,單位為m。每幀數據中包含前景與背景兩個部分,背景點主要指地面數據,它不僅占用大量內存,并且影響后續障礙物點云分割精度,因此對地面點云的分割過濾在整個點云數據處理中是必要步驟。

1.1.2 初始地面點集篩選

激光雷達檢測距離最遠可達上百米,但在實際應用中,距離過遠會產生點云稀疏,過于稀疏的點云會造成目標特征丟失,因此需要縮小處理范圍,減小數據量,提高點云數據后續處理精度。

定義x軸正方向為車輛前進方向,y軸方向為垂直于車輛前進方向水平方向,z軸方向為垂直地面方向。在x軸方向上,假設目標物體為具備理想反射表面的立方盒子,反射面高寬比為a∶b。設雷達水平方向上相鄰激光束夾角為α,z軸方向上的夾角為θ,則距離為S的目標物理想反射點數可由式(1)粗略估計[18],表達式為

(1)

已知α=0.09°,θ=0.4°,假設a=2.1,b=1.8,則距離60 m的目標物理想反射總數約為100個。但是由于在實際場景中反射點數還受目標顏色、表面凹凸程度等多種因素影響,所以實際點云數量為30～50個。因此為保證行車安全視距和分割精度,設置感興趣范圍最遠距離不超過60 m。在y軸方向上,根據行車左右安全視距分析,確定取左右各20 m。

地面點云高度一般分布在[-h-κ,-h+κ],h為激光雷達的安裝高度,κ為波動對點云高度影響,路面波動越大κ越大[19]。為減小后期點云分割計算量,在此定義高度z滿足z≤-h+κ的所有點云為初始地面點集,為保證包含所有地面點云,κ取值可略大一些,取為0.5 m。

直通濾波器使用閾值作為通過標準,在指定維度上過濾掉不在取值范圍的點,是一種粗裁剪方式,可以快速完成點云有效范圍的裁剪。利用直通濾波器快速分割的特性,選用3個直通濾波來快速確定感興趣區域,預分割前后對比如圖1所示。

圖1 預分割前后對比圖Fig.1 Comparison before and after pre-segmentation

1.1.3 柵格儲存點云

選擇XOY面作為投影平面,將預分割出的初始地面點集進行二維投影。對數據集2D投影是為了快速建立水平最小邊界框,選擇XOY面投影是因為與其他平面相比它在形狀、大小上產生的失真更小。將確定的最小邊框內部空間網格化,形成Lx×Ly的正方形柵格?？紤]分割算法的速度與精度的均衡性,網格大小選為Lx=Ly=6 m,如圖2所示。

圖2 柵格化示意圖Fig.2 Rasterized diagram

遍歷全部點云(此處及下文所說全部點云為預分割后的點云),讀取每個點云的(x,y,z)信息,計算當前點云的柵格編號,并將其儲存到相應柵格矩陣內。柵格編號(row,col)計算公式為

(2)

式(2)中:ceil()表示向下取整運算;xi、yi分別為第i個點的橫、縱坐標;yBound為感興趣范圍中y軸正負方向的距離,大小為20 m;Lx、Ly為柵格邊長。定義左下方第一個柵格編號為(0,0),將全部點云儲存在柵格矩陣中。

1.2 自適應閾值確定

無人駕駛車輛上的激光雷達檢測的點云高度會隨行駛地面的波動而波動,地面起伏的不確定性導致地面點云分割充滿了不確定性,進而影響著點云的分割精度。目前常用分割閾值對柵格儲存后的點云進行地面點云分割,從而獲得地面點和非地面點。在分割過程中,固定統一的高度閾值與地面起伏波動不適應,而閾值過大會造成過分割,過小又會造成欠分割。

由圖3可以看出,統一的高度閾值只適用于平坦路面B段場景,在含有矮小障礙物的A段場景和斜坡C段場景,統一閾值并不適用。

圖3 統一高度閾值分割圖Fig.3 Unified height threshold segmentation map

通過上述分析發現,高度閾值與地面波動幅度和理想地面高度存在關聯,因而用起始高度表征理想地面高度,并利用柵格內點云高度標準差擬合地面波動幅度來自適應確定合適的高度閾值能夠改進點云的分割效果。自適應高度閾值包含理想地面高度和波動幅度兩部分,表達式為

ω=τ+kf

(3)

式(3)中:τ為理想地面高度;f為地面波動幅度;k為波動調節系數,取2.6。

標準差是反映數據波動情況的重要指標,在某一柵格內所有點云的高度標準差可以反映當前柵格內點云的高度分布。利用標準差對數據分布的擬合能力,實現地面波動的擬合,進而自適應確定高度閾值。因為地面具有連續性,地面點云高度會在理想地面高度附近波動,而波動幅度在一定高度的限制下接近于當前柵格的點云高度的離散程度,在數值上等于點云高度的標準差。基于上述分析,只需增加波動調節系數便可擬合地面點云的波動,波動調節系數的加入提高了自適應高度閾值的準確性與普適性。設f表示當前柵格整體點云高度的波動幅度,計算公式為

(4)

式(4)中:n為當前柵格中點云數量;zi為柵格內第i個點的高度;μ為柵格內點云的高度均值。

起始高度的選擇是點云分割需要考慮的另一個影響因素。大多數學者選擇點云的高度平均值作為起始高度,很好地緩解了異常點對分割結果的影響,但并沒有徹底消除影響。例如,一組點云數據如圖4所示,不同初始點存在如下問題:一是使用平均值替代最低點,無形中增加了最低點高度,會導致過分割概率增大。二是并非所有柵格中都存在異常點,若所有柵格均采用均值替代,就會導致分割的地平面高于真實地面,造成過分割。在選擇起始高度時設計了先驗后取值的方法,更為科學地實現了起始點高度的取值。

圖4 不同初始點對應起始高度對比圖Fig.4 Different initial points correspond to the initial height comparison diagram

先驗后取值的方法是指對柵格內最低點采用箱線圖分析法進行異常值檢驗,若為異常值則選用統計值替代,若非異常值則選用最低點。箱型圖判斷異常值的方法以四分位數和四分位距為基礎,四分位數具有魯棒性。25%的數據可以變得任意遠并且不會干擾四分位數,可以有效抑制異常值對這個標準的影響。因此,箱型圖法識別異常值比較客觀,且有一定的優越性。箱線圖識別異常值標準表達式為

(5)

式(5)中:di為待檢測值;outliers為異常值;nooutliers為非異常值;QL為下四分位數,表示全部觀察值中有1/4的數據取值比它小;QU為上四分位數,表示全部觀察值中有1/4的數據取值比它大;IQR為四分位數間距,是上四分位數QU與下四分位數QL的差值,包含了全部觀察值的一半。

當最低點為異常值時則用統計值代替,利用高度最小的20個點云中的眾數替換統計值。眾數適用于具有離散特點的數據,點云數據符合這一特征,并且一定范圍內的眾數更能表示最低點的真實分布,由圖4也能看出選取眾數更接近真實地面高度,更具優勢。

1.3 雙特征循環增長判斷

目前主要采用基于二維網格的地面濾波算法對網格劃分后的點云進行地面點云分割,該方法的主要思想是在固定大小的網格內選擇特征值進行閾值分割,網格的大小、分割特征的選擇與取值是該算法的重要影響因素。網格過小,忽略了地面的連續性特點,網格過大,雖然考慮到了全局信息,但特征值計算的復雜性急劇增加,導致分割效率過低。 單一分割閾值敏感性不足,多閾值的簡單組合又會出現冗余計算。針對以上問題,提出雙特征循環增長判斷的分割算法,該方法利用循環增長判斷對局部特征與全局特征的兼顧性能實現地面點云的合理分割。

對于圖5中不同類型的障礙物,不同高度閾值標準下的識別結果如表1所示。

表1 不同分割標準對比表Table 1 Comparison table of different segmentation criteria

圖5 不同類型障礙物模型圖Fig.5 Models of different types of obstacles

利用高度閾值與標準差閾值分割的互補性,構建了觸發式標準差閾值和高度閾值雙特征判斷機制,使得分割算法的計算時間更為合理。

粗分割后的初始地面點集儲存在柵格矩陣,對每個柵格分別進行分割。每個柵格矩陣的元素(Lx×Ly大柵格)以左下角為起始點定義一個邊長為l的小正方形柵格,對小柵格內提取的點云數據應用觸發式雙特征判斷機制進行判斷分割。

雙特征循環增長判斷的分割算法需要首先計算小柵格內點云高度分布標準差σ,若σ大于設定標準差閾值Zσ則判為非地面點,并移動小柵格進行下一次判斷;若小于設定標準差閾值Zσ則觸發第二判斷依據。然后計算小柵格內點云平均高度μ,判斷是否小于所在柵格的高度閾值ω,若μ小于高度閾值ω,則判定小柵格內的全部點為地面點,否則為障礙物點。判斷機制表達式為

(6)

式(6)中:Pk為第k個小柵格內的點云集合;ground為地面點;noground為非地面點;高度閾值ω(i,j)為柵格矩陣中第i行第j列大柵格的自適應高度閾值。

當前小柵格判斷完成后,中心點沿y軸平移l/2個單位形成新的小柵格,繼續進行參數計算與判斷,當小柵格移動到網格右下角時,中心點則沿x軸向上平移l/2個單位,如此循環,直到整個大柵格全部遍歷完。循環方式如圖6所示,可以看出,小柵格對稱軸平分的四部分點云,每一部分都會在臨近柵格內再次加入判斷,使得相鄰柵格之間的點云緊密聯系。單獨小柵格內凸顯局部特征,相鄰柵格緊密聯系兼顧了全局特征。

圖6 循環判斷示意圖Fig.6 Loop judgment diagram

2 實驗分析

為測試算法的分割精度及實時性,采用文獻[20]公開的數據集。10個場景均包含不同程度的坡度路面與起伏路面。實驗電腦配置為:i7 12700H處理器、GTX3060顯卡及16 GB內存,系統環境為Windows 11,采用MATLAB R2016編程。實驗參數參考文獻[17]和多次實驗的最優值,具體設置如表2所示。

表2 實驗參數取值Table 2 Experimental parameter value

2.1 實驗分析指標

對于分割精度,采用真陽性率(TPR)、假陽性率(FPR)、準確性(ACC)和運行時間(t)4個指標來比較算法性能。式(7)定義了各個指標。

(7)

式(7)中:各參數含義如表3所示。

表3 定性指標參數含義Table 3 Parameter meaning of qualitative indicator

2.2 實驗結果

10個不同場景點云數據的分割結果如表4所示。由表4可以看出,本文算法在10種場景下均具有90%以上的真陽率和準確率,且假陽率均低于3%。

表4 本文算法對不同場景的分割結果Table 4 The segmentation results of different scenes by the algorithm in this paper

為驗證循環判斷對傳統柵格法改進的有效性,對比了不同分割條件下的傳統柵格法與改進的柵格法,實驗結果如表5所示。

表5 柵格法改進效果對比Table 5 Comparison of improved effect of grid method

由表5可以看出,對傳統柵格法的改進具有明顯優勢,不僅精度得以提升,分割效率更有明顯提升。循環判斷法在大柵格內嵌套小柵格循環判斷,小柵格內凸顯局部特征,相鄰柵格緊密聯系又兼顧了全局特征,其對局部信息與全局信息的兼顧性有效提高了分割精度。大柵格有效限制了循環范圍,小柵格內局部信息突出,點云特征明顯,且特征值計算量小,使得分割效率大幅提升。

為驗證本文算法的有效性與優越性,分別與單一高度閾值、單一標準差閾值、固定雙閾值方法和文獻[20]方法進行比較,具體計算指標如表6所示。

表6 不同方法分割效果對比Table 6 Comparison of segmentation effect of different methods

由表6可看出,本文算法較改進前的3種方法在真陽率、假陽率、準確率和運行時間上均有較大提升。觸發判斷機制的建立減少了大量的冗余計算,使得分割時間大幅縮短。與文獻[20]方法相比較,雖然真陽率略有下降,但本文算法的準確率比其高出3.27%。假陽率的降低為后續點云處理有效的保留了障礙物特征信息。

選擇具有坡度路面數據,本文算法與其他方法的分割效果在視覺上的對比如圖7所示。

圖7 分割效果對比圖Fig.7 Segmentation effect comparison diagram

由圖7 (b)可以看出,單一的高度閾值分割帶坡度場景時,閾值過大會導致坡下高度較小的障礙物被誤分割為地面點;閾值過小會出現未被識別,如圖7(b)中大橢圓區域的地面點云。因此,單一的高度閾值受限較嚴重,易造成過分割和欠分割。

圖7(c)是單一標準差閾值的分割結果。由于高度標準差特征較小,對包含較大平面障礙物柵格造成了過分割。雖然雙閾值彌補了單一閾值分割時精準度對閾值選取嚴重依賴的問題,但在點云稀疏且坡度較大的區域存在嚴重的欠分割,如圖7(d)所示。本文算法的分割結果如圖7(e)所示,與標準地面點云和其他分割方法的分割結果對比可知,本文算法解決了單一閾值和多閾值存在的過分割和欠分割問題,無論是對坡度路面,還是小目標點云都能實現較好分割。

3 結論

在坡度和路面起伏不平的場景中,針對地面點云分割算法單一閾值的敏感性不足,多閾值存在冗余計算和閾值選擇魯棒性不足的問題,提出了一種基于自適應閾值循環增長分割地面點云的方法。該方法利用循環增長判斷法克服了傳統柵格法分割對柵格大小敏感的問題,建立觸發式雙特征判斷機制提高了分割算法的時效性。利用標準差對數據離散程度的擬合能力,實現對地面波動幅度的擬合,構建的自適應高度閾值解決了柵格法分割閾值敏感的問題。 經過仿真驗證,本文方法可在不同起伏程度和不同傾斜角度的斜坡場景中實現地面點與非地面點的合理分割,通過與改進前各方法和文獻[20]算法對比分析可知,本文算法具有較高的準確性和時效性,為點云分割方法的應用提供了另外一種選擇方案。