韓 旭，梁新美

(中國地質(zhì)大學(xué)(武漢),湖北 武漢 430074)

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

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

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

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

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

(1)

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

2 基于局部特征約束的點(diǎn)云分割

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

2.1 高程梯度定義

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

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

(2)

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

(3)

(3) 將結(jié)果除以點(diǎn)數(shù)，以得到投影變化率的平均值，得到梯度大小為

(4)

2.2 局部特征約束

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

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

(5)

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

(6)

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

3 多尺度聚類點(diǎn)云提取方法

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

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

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

利用八叉樹對點(diǎn)云劃分格網(wǎng)可以建立點(diǎn)之間的拓?fù)潢P(guān)系[15]，因此本文聚類前需先將點(diǎn)云劃分格網(wǎng)。本文借鑒二維圖像處理中基于遍歷標(biāo)記法的連通域分割算法，將二維像素標(biāo)記拓展到三維格網(wǎng)標(biāo)記，將4方向或8方向鄰域拓展到26方向鄰域。實現(xiàn)方法如下：

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

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

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

3.2 聚類尺度的確定

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

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

(7)

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

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

4 結(jié)構(gòu)化道路的道路簇和路坎簇提取

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

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

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

(8)

式中，Sdw,sml為小尺度下標(biāo)記的車道點(diǎn)集；Ssw,sml為小尺度下標(biāo)記的人行道點(diǎn)集；Srd,lg為大尺度下標(biāo)記的道路點(diǎn)集。

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

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

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

表1 道路簇表征參數(shù)

4.2 路坎簇提取

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

圖1 不同路坎結(jié)構(gòu)及最小外包盒示意圖

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

(9)

式中，X、Y、Z為簇內(nèi)點(diǎn)坐標(biāo)x、y、z值的最大差值，即最小外包盒的長、寬、高。

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

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

(10)

式中，Ai為簇內(nèi)點(diǎn)Pi的掃描角度；N為簇內(nèi)點(diǎn)的數(shù)量。

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

圖2 基于平均掃描角度的簇標(biāo)記

路坎簇標(biāo)記和提取公式為

(11)

5 實例驗算

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

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

圖3 局部特征約束目標(biāo)提取及標(biāo)記結(jié)果

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

從最終的提取結(jié)果(如圖4所示)來看，非目標(biāo)點(diǎn)云已經(jīng)濾除，而且提取的目標(biāo)點(diǎn)云保留較為完整。

圖4 目標(biāo)提取及標(biāo)記結(jié)果

6 結(jié) 語

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