韓 旭，梁新美

(中國地質大學(武漢),湖北 武漢 430074)

隨著近年來無人駕駛、機器導航的出現和發(fā)展，對道路識別的研究日益受到重視，從原先基于單目影像的二維視覺逐步開始側重立體視覺方面[1]，三維激光點云數據的處理及基于點云數據提取道路要素的研究變得更加重要[2]。而車載點云數據作為道路兩側三維數據獲取的重要來源[3]，是道路提取的重點研究數據,從車載激光點云中準確提取道路結構，是三維建模領域需要首要解決的重要問題之一[4]。雖然在機載激光掃描點云數據中相關研究已經較為深入，但由于掃描方式、點云密度、幾何特征等不同，機載激光點云數據的處理方式并不完全適用于移動激光掃描點云數據[5]，相比前者，從后者提取道路更為艱難[6]。本文研究在不同層次對象提取不同特征的方法，在滿足一定精度的基礎上盡可能地提高效率。

1 點云預處理

常見的道路結構類型一般由車道、人行道及二者的連接結構路坎組成[7]。

車載掃描系統(tǒng)掃描軌跡線通常沿道路延伸方向獲取道路及其周邊的點云數據，且通常包含掃描角度信息[8]。另外，由于特征提取極為耗時[9]，因此可以通過掃描角度約束將點云分割，獲得感興趣區(qū)域，縮小處理范圍。約束公式為

SI={Pi|-45°≤θ(Pi)≤45°,Pi∈Spart}

(1)

式中，SI為掃描角度約束后的點集；Spart為車載掃描點云片段點集；θ(Pi)為點Pi的掃描角度。

2 基于局部特征約束的點云分割

點云的局部特征可以用來反映點云在極小范圍內掃描值的變化規(guī)律，從而對點云進行標識和分類。本文利用高程梯度約束方法將點云標記為道路點和路坎點兩類，然后進行點云的初步分割。

2.1 高程梯度定義

高程梯度可以用來反映點云局部高程變化的快慢，可區(qū)分立面點云和水平面點云。各點在局部的高程變化信息可用于區(qū)分道路和路坎。目前點云梯度并沒有明確的定義[10]，大多數點云梯度計算是投影到二維平面進行梯度計算，如Yang等[11]、Huang等[12]、Xia等[13]按各點值在坐標軸方向變化的最大值來分析變量變化的特征，Xu等[10]則是將二維Robert算子的定義從二維像素拓展到三維格網求梯度，直接將基于像素的圖像處理方法使用于基于格網的三維點云計算。本文采用圖像梯度及數學中函數梯度的定義和思想，對三維離散點直接計算梯度大小。

(1) 梯度定義中將點值變化量分別在x、y、z軸投影，得到3個方向的局部投影變化量Fx、Fy、Fz，再將投影變化量除以變化“距離”，得到局部投影變化率為

(2)

(2) 對所有鄰域點的投影變化率求和為

(3)

(3) 將結果除以點數，以得到投影變化率的平均值，得到梯度大小為

(4)

2.2 局部特征約束

依照本文對高程梯度大小的定義，在水平結構中高程變化接近0，位于立面結構的點云計算出的高程梯度值一般較大。結合實際經驗，選取不同的梯度閾值按式(5)和式(6)將點云分割為兩類，從而區(qū)分立面點云和水平點云。

Sh,l={Pi|Pi∈SI,Hgra(Pi)

(5)

Sf,l={Pi|Pi∈SI,Hgra(Pi)>Gv}

(6)

式中，Sh,l為近似的局部水平點集；Sf,l為近似的局部立面點集；Hgra(Pi)為點Pi的高程梯度。

3 多尺度聚類點云提取方法

通過局部特征約束分割后的點云仍包含較多的非目標點云，而它與目標點云在局部特征上表現相似，難以在單個點或局部點云中定義其他有效的特征進行分類。

由于經過局部特征約束后得到的道路備選點和路坎備選點在歐氏空間內成“塊”狀分布，因此進一步分割可先采用聚類算法在歐氏空間將點云分割成“簇”，并按其幾何特征提取包含目標點云的簇[14]。

3.1 基于26方向鄰域和遍歷標記法的連通域聚類分割方法

利用八叉樹對點云劃分格網可以建立點之間的拓撲關系[15]，因此本文聚類前需先將點云劃分格網。本文借鑒二維圖像處理中基于遍歷標記法的連通域分割算法，將二維像素標記拓展到三維格網標記，將4方向或8方向鄰域拓展到26方向鄰域。實現方法如下：

(1) 按特定尺度將待處理的已經過局部特征約束標記屬性(道路屬性、路坎屬性)的點云數據劃分格網，采用三元組編號，如第i列第j行第k層的格網編號為(i,j,k)，初始標記Label(i,j,k)=0。

(2) 按一定順序遍歷格網，格網(i,j,k)包含點云時，首先判斷該格網26個相鄰格網的標記類型：如果該格網鄰域內不包含任何類別的格網，則將該格網標記Label(i,j,k)加1，表示增加了一個臨時聚類類別；如果該格網鄰域內存在Label值不為零的格網，鄰域內Label集合中超過兩個元素，則將該格網Label值取為鄰域內最小的非零Label值，即Label(i,j,k)=min{鄰域內非零Label值}，且將此時該鄰域的所有非零Label值加入到新的集合類型I={鄰域內非零Label值}作為一個新的類型子集。

(3) 遍歷所有格網，將所有合并的Label集合I中的元素全部賦值為集合中最小的Label值，即Label∈I=min(I)。

3.2 聚類尺度的確定

該聚類算法需要首先將點云劃分格網，而格網的大小(尺度)會影響鄰接關系和類別的判斷，點云所屬的格網及其之間的鄰接關系也會發(fā)生變化，聚類所得到的類別也就不同。一般而言，使用越小的尺度聚類，分割程度越大，得到的簇越多，同一目標被分割成不同簇的可能性越大(過分割)，同時消耗的時間也就越多；反之，尺度越大則不同目標被分割成同一個簇的可能性越大(欠分割)，耗時越少。

綜上選擇合適的尺度進行聚類是實現聚類分類的關鍵，可以通過對樣本數據(包括了包含彎曲道路片段的點云、包含直線道路片段的點云、包含轉角道路片段的點云及道路結構特征不同的點云)在不同尺度下聚類進行分割情況統(tǒng)計獲得較好的尺度，用分割比Rseg表示，當Rseg<1時，表示欠分割，當Rseg>1時表示過分割。

(7)

式中，N為目標的理論結構個數(如車道N一般為1，人行道和路坎N一般大于2)；ni為理論個數為1時(單個結構)對應實際分割得到的個數，當簇中包含有非目標點云塊時(即聚類塊中有明顯的非路坎或非道路的點集，且這些點在采用更小的尺度時有較大可能被分割成不同的類別)，ni=0。

該統(tǒng)計結果僅作為尺度選取的參考，在實際處理中由于道路結構的不同、選取道路片段的長度不同，上述值也會有所差異。

4 結構化道路的道路簇和路坎簇提取

城市結構化道路中行車道與人行道類似，具有如下特點：①一般為平面狀；②路面坡度一般小于10%，坡面較為平緩，沿水平方向延伸；③道路表面較為平坦，高程變化點少；④路面面積較大，包含的點較多；⑤主干道路包含掃描角度為零的點云。路坎作為連接路面的分割面，與道路類存在拓撲關系，同時路坎具有如下特點：①形狀為細長狀；②延伸方向接近水平，且沿該方向高程變化平緩；③平均高程與道路相差較小；④路坎與道路鄰接，且位于人行道和車道之間；⑤路坎與掃描軌跡線形狀相似(切線方向變化規(guī)律一致)?；谏鲜鎏攸c，本文將對道路備選點提取形狀、尺度、姿態(tài)和位置特征，對路坎備選點提取形狀和姿態(tài)、空間分布特征，通過特征約束實現車道、人行道和路坎點云的提取。

4.1 多尺度聚類的道路簇提取

試驗表明，在小尺度下，車道點云一般處于連通域，不會被標記為多個類別，人行道點云在該尺度下位于不同的連通域，易被標記為多個類別；而在大尺度情況下，人行道則易與車道被標記為同一類別。據此，得到車道點集Sdw和人行道點集Ssw為

(8)

式中，Sdw,sml為小尺度下標記的車道點集；Ssw,sml為小尺度下標記的人行道點集；Srd,lg為大尺度下標記的道路點集。

由于被標記為同一個類別的所有格網一定是處于連通域的，因此，為了使得大尺度下人行道和車道被標記為同一類，應該有至少一組相鄰的格網同時包含車道點和人行道路點云。

為了更好地提取簇的幾何特征，采用隨機采樣一致性算法(random sample consensus,RANSAC)對平面擬合的思想，利用內點和外點判斷一個簇的平面性，從而避免最小二乘法擬合平面時非目標點的影響。具體計算中采用梅森旋轉算法采樣若干點(如1000個)，首先利用最小二乘法擬合平面，將距離該平面小于閾值(考慮道路面有弧度，本文取0.02 m)的點記為內點，其余記為外點，統(tǒng)計迭代30次內最大的內點數作為該簇最終的內點數，用于定義簇的形狀特征。

按照道路的特點，對聚類分割得到的每個簇提取形狀、尺度、姿態(tài)和位置特征見表1。

表1 道路簇表征參數

4.2 路坎簇提取

路坎的形狀、姿態(tài)特征可以使用最小外包盒(minimum bounding box,MBB)衡量，最小外包盒的各邊平行于坐標軸，圖1為幾種簡化的路坎結構。

圖1 不同路坎結構及最小外包盒示意圖

定義路坎的形狀和姿態(tài)描述特征量為

(9)

式中，X、Y、Z為簇內點坐標x、y、z值的最大差值，即最小外包盒的長、寬、高。

由于路坎(片段)在近似水平方向延伸，因此Sh值越小越有可能是路坎，限制Sh的最大閾值，可以去除汽車、樹木、行人等呈塊狀結構的簇和垂直結構的簇。

除此之外，為了去除一些與路坎在幾何形態(tài)上類似的簇，定義特征量An以描述簇的空間分布特征。

(10)

式中，Ai為簇內點Pi的掃描角度；N為簇內點的數量。

在結構化道路中，路坎在空間分布上的特征應該是位于車道和人行道之間，平均掃描角度一般情況下應在兩側人行道平均掃描角度所構成的區(qū)間內，如圖2所示。

圖2 基于平均掃描角度的簇標記

路坎簇標記和提取公式為

(11)

5 實例驗算

試驗數據由車載激光掃描系統(tǒng)在武漢大學掃描獲取。數據采集共包含約2.1×109個點，試驗數據為車載激光掃描在WGS-84坐標系下的原始數據。

為驗證本文算法的有效性，在分割的道路片段中選取數據測試。原始數據包含大量散亂樹葉及行人、汽車等非目標點云數據，點云分布十分密集。對數據按照本文的方法進行測試。其中局部特征約束的結果如圖3所示，聚類標記的結果如圖4所示。

圖3 局部特征約束目標提取及標記結果

由圖3可見，濾除了大量稀疏點，已基本不包含道路上方的枝葉、距離道路較遠的散亂獨立地物和一些離散的點云數據，但仍存在較多的樹干、行人及非道路地面點，該階段標記的道路備選點云多為在局部水平分布的點云，而標記的路坎備選點云多為局部垂直分布的立面點云。

從最終的提取結果(如圖4所示)來看，非目標點云已經濾除，而且提取的目標點云保留較為完整。

圖4 目標提取及標記結果

6 結 語

本文提供了一種基于局部特征和多尺度聚類的道路要素點云提取的完整方法。首先對點云提取局部特征和特征約束分割，并逐層計算特征值和濾除點，從而在點層次標記出道路備選點和路坎備選點；然后采用一種基于遍歷標記法的連通域聚類算法，分別將道路備選點和路坎備選點分割成不同的簇，在不同尺度上對每個簇提取對于識別目標(人行道、車道、路坎)有效的描述其形狀、尺度、姿態(tài)等特點的特征量，利用RANSAC算法提取簇的平面特性，結合不同目標的幾何特征，在簇層次標記出車道簇、人行道簇和路坎簇。結果表明，該方法效果較好，提取的車道點云、人行道點云和路坎點云具有較高的準確率和召回率，可以用于車載激光掃描數據的結構化道路目標的識別，并為無人駕駛等應用提供服務。