基于網格單元的點云降維處理算法

段志國, 吳灝, 侯陽, 王少博, 辛慶山, 張明路

(1.國網石家莊供電公司, 石家莊 050000; 2.河北工業大學機械工程學院, 天津 300401)

點云是實際物體三維信息的統計無序數集,包含了物體的三維坐標值,顏色值和灰度值[1]。近年來,學者們針對點云的預處理和障礙物包圍盒的建立進行了大量的研究。密度聚類是一種無監督聚類算法,能在“噪聲”數據中識別出任意形狀的聚類[2-7]但由于密度聚類在去除點云噪聲時需要對點云進行逐個遍歷,利用歐式距離進行鄰域點判斷收斂時間較長,不適合海量點云的去噪處理。文獻[8]用K-means聚類算法,根據點到聚類中心的歐式距離和臨近點曲率變化判斷每個類中的點是否為噪聲點;文獻[9]提出基于改進隨機抽樣一致的點云分割算法實現點云分割的同時有效去除噪聲點;文獻[10]通過枚舉繞軸旋轉的角度,對比旋轉后的包圍盒體積,最終獲得體積最小的包圍盒。雖然已有算法已經在一定程度上提高了點云聚類和包圍盒建立的精度,但是仍然存在一些問題。例如,枚舉算法的復雜度較高,一些算法對初始值較敏感,依賴法向量、曲率等信息,因此點云處理效果難以把控。

針對上述問題,在點云分割完成的基礎上,現提出一種高效的點云聚類與包圍盒建立方法。該方法基于二進制占用網格對點云進行降維處理,將點云映射到網格單元中實現不同物體點云的快速聚集。并尋找點云輪廓生成的二進制占用網格主方向,基于主方向旋轉點云從而建立更加緊致隨動的包圍盒。

1 基于二進制占用網格的點云聚類

點云分割完成后,需要將不同障礙物的散落點集集合成點云簇,將障礙物點云圖形轉化為若干個對象。采用二進制網格的方式聚類,通過對點云進行降維處理,再將點云映射到網格單元中,查找并分別儲存已占用網格的連通域,從而實現不同物體點云的快速聚集。

1.1 網格生成與點云儲存

對點云空間創建二維極坐標網格,極坐標網格劃分包含扇形區域和子區域兩個部分,首先將極坐標區域劃分為扇形區域,取扇形圓心角αpl,將極坐標平面分割為m個扇形,公式為

(1)

再繼續對每個扇形區域劃分子區域,取最大距離為rmax,步長距離為rpl,將每一個扇形沿扇形半徑均等劃分為n份,公式為

(2)

這樣就對點云空間創建了一個m×n的極坐標網格平面。

網格劃分完畢后,將點云儲存到網格中,由于點云具有三維信息,將點云信息進行降維存儲,即直接將點的坐標(x,y,z)簡化為(x,y)。原因在于一方面點云聚類并不關心點云簇在z方向的排列與順序,若兩個點的x、y值一致而z不同,則視為兩點在z方向疊加,它們屬于同一障礙物的點云;另一方面能夠加快聚類速度,滿足聚類算法在動態變化的環境中的實時性要求。確定點pi=(xi,yi,-)所屬的扇形區域sa,公式為

(3)

(4)

確定扇形區域后,再計算點b(pi)所述的子區域bb,公式為

(5)

(6)

將各點映射到網格中后,對網格進行賦值。若網格中未包含點,則記網格的值為0,其像素顏色為黑色;若網格中包含點,則記網格的值為1,其像素顏色為白色。從而生成二進制占用網格。這樣就將三維點云處理轉化為二維圖像處理,并且二進制占用網格組成簡單,占用空間小,處理難度大大降低。

1.2 二進制占用網格膨脹處理

對二進制圖像進行圖像膨脹處理,圖像膨脹是將圖像在保持原有形狀不變的情況下,對圖像的白色部分進行擴張。其主要目的是將白色區域內部孤立的黑色的像素點去除。定義一個大小為3×3的正方形的核,其原點位于中心位置。設輸入二進制圖像像素集合為A,核像素集合為B,原點為中心點,則圖像膨脹定義為

A⊕B={x|(B)x∩A≠?}

(7)

式(7)中:?為空集。

核的原點從二進制圖像的原點出發,使核在圖像上進行逐個像素點的移動,掃描其3×3范圍內的圖像像素點。若核中掃描的所有像素點都為0,則錨點處的像素點記為0,否則記為1。遍歷每一個像素點即可得到膨脹圖像,與原圖像相比它具有更大且更連續的白色區域。

1.3 二進制占用網格連通區域分析

連通區域分析是一種計算機圖像分析與處理的常見方法,其目的是將前景目標物體從背景中提取出來以便后續處理的使用。連通區域一般是指圖像中具有相同像素且位置相鄰的像素點組成的圖形區域,它是一個像素集合。連通區域分析是指將圖像中的各個連通區域找出并標記。

在對二值圖像進行膨脹后,得到存放障礙物點云的白色像素塊,下一步是識別不同障礙物的像素塊并分類儲存,使用連通區域分析算法中的種子填充法對二值圖像進行進一步的處理。其步驟如下。

(1)定義一個四鄰域的像素相鄰關系,它表示從目標像素點出發,對其上、下、左、右4個相鄰的像素點進行檢測。

(2)從二值圖像原點開始,逐個像素點掃描圖像,直到當前掃描像素點p1為白色像素點。對該白色像素點的位置賦予一個label,label是從1開始逐漸增大的自然數,被用來對白色像素點進行標記。

(3)將p1鄰域內的點p2、p3、p4、p5按先后順序放入一個集合M中,如式(8)所示,從左到右分別代表放入的先后順序,最后放入的點為p5。

M={p2,p3,p4,p5}

(8)

(4)將p5取出進行檢測,若p5為白色像素點,則對p5賦予與p1相同的label,并將p5中所有鄰域內的點按先后順序加入M;若p5為黑色像素點,則舍棄p5并取出p4進行檢測。

(5)重復步驟(4),直到取出M中所有的點。此時便得到了label=1的一個連通區域。

(6)重復步驟(2),當掃描結束時,就可以得到圖像中的所有連通區域。

查找每一label標記的點集分別標記上不同的顏色,得到不同障礙物的點云簇,點云聚類流程示意如圖1所示。

圖1 點云聚類流程示意圖

2 基于點云主方向旋轉的包圍盒建立

2.1 基于二進制占用網格點云主方向識別

點云主方向是指點云數據變化最大的朝向,它決定了包圍盒的方向與大小,判定點云主方向關鍵在于如何得到點云邊框在x-y平面內的最大分布。霍夫直線檢測是一種經典的直線特征提取技術,它廣泛應用于具有輪廓特征的二進制占用網格內,即從圖像中獲取直線。霍夫直線檢測是通過累加器在特定類型的形狀內找到直線,直線候選對象由累加數的局部極大值確定。霍夫直線檢測不僅能檢測出圖像的直線輪廓,還能定位到該直線的位置和角度等。其檢測方程為

ρ=xcosθ+ysinθ

(9)

式(9)中:ρ與θ為極坐標下點的極徑與極角,霍夫直線檢測的優點在于:給定x-y平面中的單個點,那么通過該點的所有直線的集合對應于θ-ρ平面中的一條曲線,且點與曲線的對應關系是唯一的。兩個或多個點形成的一條直線將產生在該線的(θ,ρ)處交叉的一條或多條曲線。因此,檢測共線點的問題可以轉化為在θ-ρ平面內找到曲線交點個數的問題。

點云主方向的算法流程如下。

(1)提取點云邊框,因為點云是一種類似于空殼的圖像,只反映被拍攝物體的表面信息,且對于一般障礙物而言,其橫向尺寸變化不大。故去除z方向較大的點云并投影到x-y平面后,可得到點云的邊框圖像。其判定如式(10)所示,保留滿足式(10)的所有點pi。

z(pi)-zmin<0.7(zmax-zmin)

(10)

式(10)中:z(pi)為點的z方向大小。

(11)

(12)

取邊長為g的正方形建立柵格,則該柵格圖的大小為rx×ry,將點云投影到柵格地圖中將包含點的柵格值記為1,未包含點的柵格值記為0,生成點云邊框的二進制占用網格。

(3)讀取點云邊框二進制占用網格,掃描其像素值為1的像素點,并以柵格邊長作為霍夫直線檢測的變換步長,其總檢測長度為點云邊框的總周長,則檢測次數nt為

nt=2(rx+ry)/g

(13)

(4)對霍夫空間設置累加器Num(θ,ρ)并初始化Num(θ,ρ)=0。對于二進制占用網格中每一個像素點(x,y),在參數空間中找出所有滿足ρ=xcosθ+ysinθ的(θ,ρ),然后令Num(θ,ρ)=Num(θ,ρ)+1。

(5)統計所有Num(θ,ρ)的大小,取出其最大值,該情況所對應的直線即為點云主方向對應直線。計算點云主方向對應直線與基坐標系的角度α,則α為點云主方向。

計算點云主方向流程示意如圖2所示。

圖2 計算點云主方向流程示意圖

2.2 包圍盒頂點確定

在得到了點云主方向以后,可以根據點云主方向建立包圍盒。這種包圍盒的特點是與障礙物之間貼合緊密,間隙較小,能夠更準確地描述障礙物的尺寸與朝向。該過程可分為以下步驟進行。

(1)計算障礙物點云集中心位置坐標(xc,yc),如式(14)所示,并計算出以中心點為起點指向點云集各點的向量pi如式(15)所示,其中xmax、xmin、ymax、ymin代表障礙物點云集在x、y、z方向上的最大值和最小值。

(14)

pi=(xi-xc,yi-yc)

(15)

(2)將向量pi繞中心點處z軸旋轉-α角得到向量p′i,使點云主方向對其基坐標x軸,即

(16)

(3)遍歷旋轉后的點云集,得到旋轉后點云在x、y、z方向的最大值和最小值x′max、x′min、y′max、y′min、z′max、z′min得到包圍盒的8個頂點坐標box′i,即

(17)

(4)將得到的包圍盒頂點坐標box′i通過旋轉變換回原點集,得到原點集包圍盒的8個頂點坐標boxi,即

(18)

點云建立包圍盒流程示意如圖3所示。

圖3 點云建立包圍盒流程示意圖

3 實驗結果及分析

實驗采用RS-LiDAR-M1激光雷達進行環境采集并獲取點云數據視頻,該場景中包含兩個小型路障,距激光雷達較近的記為小型路障1,較遠的記為小型路障2。一輛大型貨車和行人等4個障礙物,其中行人向著遠離激光雷達的方向移動。其實驗場景如圖4所示,輸出點云數據如圖5所示。

圖4 點云采集實驗場景

圖5 輸出點云數據

將地面點云去除,保留障礙物點云。取參數αpl=0.65°、rmax=200、rpl=0.2。任取點云視頻中的多幀進行檢驗,經過二進制網格聚類后點云如圖6所示,從圖6中可以看出,該方法能夠有效分辨場景中障礙物的個數,并且不隨幀數的變化而出現漏判或多判的情況。

圖6 點云聚類結果

對視頻中的各類障礙物進行點數統計并計算最大誤差。由于行人隨著時間的變換距離激光雷達越來越遠,因此行人點云的點數會隨著時間的變化較大,故只對靜態障礙物進行統計,從而檢驗聚類算法的準確性。統計結果如表1所示。

表1 各障礙物聚類點數統計

由表1可以看出,隨著點云幀數的變化,各靜態障礙物的點數變化最大誤差均在5%以內,說明基于二進制占用網格的聚類算法能準確地將不同障礙物所屬的點集進行聚類。此外大型貨車聚類最大誤差為1.58%,而小型障礙物的聚類誤差為2.99%和3.64%,說明該算法對于點數越多的障礙物,其聚類效果越好。

基于二進制占用網格的聚類算法與傳統歐式聚類算法對比如表2所示,兩種算法均能檢測出場景中的4個障礙物,但基于二進制占用網格的聚類方法運算更迅速,所需時間更短。原因在于一方面對點云采用降低維度的方式進行處理,即由三維點云處理轉換為二維圖像處理,且二進制占用網格是一種非常簡單的二維圖像;另一方面該算法無需迭代,只需要對二進制占用網格進行掃描,大大降低了時間復雜度,對于場景中運動狀態變換較快的物體具有良好的實時性。兩種算法對比如表2所示。

表2 二進制占用網格聚類與歐式聚類算法性能比較

對聚類后的障礙物建立包圍盒如圖7所示,其中數字代表障礙物的標號。從圖7中可以看出,隨著幀數的改變,包圍盒能始終跟隨并包絡障礙物點云,且標號保持一致,具有良好的隨動性。對于靜態障礙物來說,由于主方向不發生改變,其包圍盒的朝向與大小未發生改變。而對于行人這類動態障礙物來說,由于在行走過程中存在位置和速度改變,故點云主方向也隨之變動,圖7中顯示該包圍盒建立方法能夠實時測量點云主方向的變換,進而改變包圍盒的朝向和大小,使得包圍盒始終緊密貼合行人點云,證明了該方法的有效性。

圖7 障礙物包圍盒建立

基于點云主方向旋轉的包圍盒建立算法與AABB包圍盒算法對比如表3所示,AABB包圍盒是直接以障礙物點集在x、y、z方向上的最大和最小值為頂點建立包圍盒。從表3可以看出,兩類算法的包圍效果與包圍盒高相差不大,但基于點云主方向旋轉的包圍盒長、寬均小于AABB包圍盒算法,證明該方法所建立包圍盒更加緊致,能夠更精確地反映障礙物的大致尺寸,證明了該方法的優越性。

4 結論

提出了基于二進制占用網格的點云聚類算法,首先對點云進行降維處理,將三維點云簡化為二維像素圖像處理,并且對點云輪廓生成二進制占用網格從而尋找點云主方向,基于主方向旋轉點云從而建立包圍盒。實驗結果表明,該方法能夠在保證聚類精度的同時大大提高運算速度,其建立包圍盒能夠更加準確的反應障礙物的尺寸,具有良好的實時性與隨動性,對之后的機械臂自主避障提供了可靠的信息。