安瑤軍，陳曉軒，隋立春,3，周榮榮

(1. 長(zhǎng)安大學(xué)地質(zhì)工程與測(cè)繪學(xué)院，陜西 西安 710054； 2. 陜西省交通規(guī)劃設(shè)計(jì)研究院，陜西 西安 710065； 3. 地理國(guó)情監(jiān)測(cè)國(guó)家測(cè)繪地理信息局工程技術(shù)研究中心，陜西 西安 710064)

高精度、準(zhǔn)確、現(xiàn)勢(shì)性強(qiáng)的道路三維信息對(duì)于道路維護(hù)、交通管理、城市規(guī)劃等具有重要作用[1]。近年來(lái)，以車(chē)輛為搭載平臺(tái)，集成GPS、INS、激光掃描儀、CCD相機(jī)等多種傳感器，在傳感器同步控制的基礎(chǔ)上，能夠獲取城市街道、建筑物立面的幾何數(shù)據(jù)和紋理信息，為道路信息快速獲取、更新及三維道路環(huán)境自動(dòng)提取開(kāi)辟了新的途徑[2]。

目前，國(guó)內(nèi)外從車(chē)載點(diǎn)云數(shù)據(jù)中提取道路信息的研究方法主要可以歸納為從點(diǎn)云投影的特征圖像中間接提取和從離散點(diǎn)云直接提取兩類(lèi)。

在點(diǎn)云投影的特征圖像中提取方面，主要依據(jù)城市環(huán)境中路面與鄰域之間的高程或密度差異，將原始點(diǎn)云數(shù)據(jù)轉(zhuǎn)換成特征圖像[3-6],再結(jié)合圖像處理的相關(guān)算法進(jìn)行道路信息的提取。此類(lèi)算法需要將離散點(diǎn)云轉(zhuǎn)換成格網(wǎng)，降低了原始數(shù)據(jù)的精度和分辨率。

在離散點(diǎn)云數(shù)據(jù)直接提取方面，閆利等[7]分析了道路點(diǎn)云法向量的分布特征，結(jié)合模糊聚類(lèi)算法對(duì)道路面點(diǎn)云進(jìn)行濾波；方莉娜等[2]提出了一種結(jié)構(gòu)化道路自動(dòng)提取方法，適合道路邊緣點(diǎn)較為突出的道路；Yuan[8]按掃描線進(jìn)行模糊聚類(lèi)的方法提取近似水平的長(zhǎng)直線作為路面，但當(dāng)路面有遮擋時(shí)算法的準(zhǔn)確性不高；Smadja等[9]基于隨機(jī)抽樣一致性算法(RANSAC)提取路面點(diǎn)云；Zhan等[10]通過(guò)解算每個(gè)點(diǎn)的法向量、法向量殘差、離散度等特征，利用支持向量機(jī)(SVM)的方法將點(diǎn)云數(shù)據(jù)分為地面、斜坡及樹(shù)木等。

本文結(jié)合道路面的點(diǎn)云法向量分布特征，提出一種依據(jù)點(diǎn)云法向量相似度的結(jié)構(gòu)化道路提取方法。

1 車(chē)載點(diǎn)云的道路提取方法

1.1 非地面點(diǎn)濾波

城鎮(zhèn)道路環(huán)境通常比較復(fù)雜，原始車(chē)載點(diǎn)云中包括道路兩側(cè)大量的樹(shù)木、路燈、電線桿及路面上的汽車(chē)等非路面目標(biāo)，這些非地面點(diǎn)會(huì)對(duì)點(diǎn)云局部法向量的準(zhǔn)確計(jì)算和道路提取的效率、準(zhǔn)確度帶來(lái)干擾，因此需要對(duì)原始點(diǎn)云濾波剔除非地面點(diǎn)。

本文采用Zhang[11]提出的基于布料模擬的濾波算法(CSF)，該地形濾波算法穩(wěn)健性較強(qiáng)，參數(shù)較少且速度快，適用于車(chē)載點(diǎn)云濾波。布料模擬濾波算法的濾波過(guò)程類(lèi)似于一種簡(jiǎn)單的物理過(guò)程模擬。假如地形表面正上方有塊虛擬布料，在重力作用下覆蓋在地形表面上，如果布料足夠柔軟，則布料的最終形狀就是數(shù)字表面模型(DSM)。同理可得，如果把原始地形翻轉(zhuǎn)過(guò)來(lái)，同時(shí)布料具有一定的硬度,則在同樣的重力作用下布料最終的形狀就是數(shù)字高程模型(DEM)。布料模擬的原理如圖1所示。

圖1 CSF算法模擬示意圖

1.2 法向量及曲率估算原理

1.2.1 基于KD-tree的k鄰域搜索

點(diǎn)云數(shù)據(jù)缺乏離散點(diǎn)間的幾何拓?fù)湫畔ⅲ瑸榱藢?shí)現(xiàn)基于鄰域關(guān)系的快速近鄰查找，要建立原始點(diǎn)云離散點(diǎn)間的拓?fù)潢P(guān)系。KD-tree由Bentley[12]于1975年首先提出，是一種分割k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，其本質(zhì)是帶有約束條件的二分查找樹(shù)，主要應(yīng)用于多維空間數(shù)據(jù)中的近鄰搜索(KNN)和范圍搜索(FDN)。KD-tree在三維空間的結(jié)構(gòu)如圖2所示。

圖2 三維KD-tree空間分割

1.2.2 基于PCA的法向量估算

離散點(diǎn)云中每個(gè)激光點(diǎn)的法向量可以采用局部鄰域擬合的切平面的法向量近似表示。Hoppe等采用局部切平面擬合方法來(lái)估算某點(diǎn)的局部法向量[13]，原理如圖3所示。

對(duì)點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)pi={xi,yi,zi}，通過(guò)鄰域查找獲得k個(gè)鄰域點(diǎn)，然后根據(jù)距離最小二乘準(zhǔn)則計(jì)算出該點(diǎn)的局部擬合平面P，平面P可以用如下數(shù)學(xué)方程表示

(1)

式中，n為平面P的法向量；d為P到坐標(biāo)原點(diǎn)的距離；argmin為目標(biāo)函數(shù)取最小值時(shí)的變量值。

通過(guò)計(jì)算可知，k個(gè)近鄰點(diǎn)的三維質(zhì)心位于平面P上，且法向量n為單位向量，滿足nTn=1。運(yùn)用主成分分析方法(principal component analysis, PCA)，將求解點(diǎn)云法向量的問(wèn)題轉(zhuǎn)化成k個(gè)近鄰點(diǎn)構(gòu)建的協(xié)方差矩陣C特征值分解的問(wèn)題。協(xié)方差矩陣C最小特征值對(duì)應(yīng)的特征向量即為需要求解的法向量。

(2)

C·vi=λi·vi,j∈{0,1,2}

(3)

由于特征值λ0<λ1<λ2分別代表了點(diǎn)在3個(gè)主方向上的變化程度，因此點(diǎn)pi的曲率Ki可以用下式近似估算

(4)

1.3 改進(jìn)的區(qū)域生長(zhǎng)算法

結(jié)構(gòu)化道路路面區(qū)域點(diǎn)云的法向量分布較為集中，總體呈豎直方向，且在道路邊緣處與路緣石等地物的法向量方向存在顯著性差異。因此利用路面點(diǎn)云的法向量方向相似性作為約束條件，采用區(qū)域生長(zhǎng)[14-15]的算法分割出道路面點(diǎn)云。

針對(duì)傳統(tǒng)區(qū)域生長(zhǎng)法通常隨機(jī)選取種子點(diǎn)，容易導(dǎo)致過(guò)分分割且效率低下的問(wèn)題，結(jié)合路面提取目標(biāo)，對(duì)種子點(diǎn)的選取準(zhǔn)則進(jìn)行改進(jìn)。結(jié)構(gòu)化道路的空間特征如圖4所示，表現(xiàn)為局部比較平坦，同時(shí)路面點(diǎn)高程一般略低于周?chē)诵袡M道等其他地物。因此，本文首先對(duì)原始點(diǎn)云按高程進(jìn)行升序排列，再選擇其中曲率最小的點(diǎn)作為道路種子點(diǎn)。算法具體流程如下：

(1) 對(duì)輸入的原始點(diǎn)云按高程進(jìn)行升序排列，計(jì)算各點(diǎn)的法向量ni與曲率Ki，再對(duì)曲率Ki進(jìn)行排序，將曲率最小的點(diǎn)確定為種子點(diǎn)。

(2) 對(duì)當(dāng)前種子點(diǎn)搜索其鄰域點(diǎn)(KNN或FDN)，并計(jì)算鄰域點(diǎn)的法向量與當(dāng)前種子點(diǎn)的法向量夾角Si及各鄰域點(diǎn)的曲率值Ki。

(3) 若法向量夾角Si

(4) 當(dāng)前種子點(diǎn)出隊(duì)，若種子點(diǎn)隊(duì)列不為空，選出新種子點(diǎn)，回到步驟(2)。

上述分割過(guò)程結(jié)束后，聚類(lèi)結(jié)果除路面區(qū)域外可能還有一些近似平面點(diǎn)群區(qū)域。道路路面所在區(qū)域一般為最大連通區(qū)域，且區(qū)域平均高程較小。因此可以設(shè)置閾值參數(shù)剔除非路面區(qū)域而得到道路面點(diǎn)云。

圖4 道路空間特征分布示意圖

2 試驗(yàn)與分析

2.1 試驗(yàn)數(shù)據(jù)

試驗(yàn)采用某車(chē)載移動(dòng)測(cè)量系統(tǒng)獲取的兩組不同城鎮(zhèn)環(huán)境下比較典型的點(diǎn)云數(shù)據(jù)。數(shù)據(jù)1為城市高架，共包含3 689 279個(gè)激光點(diǎn)，長(zhǎng)度約為300 m，道路寬度比較規(guī)則，路面呈坡?tīng)睿饕獮閺澢缆?，如圖5(a)所示；數(shù)據(jù)2為街區(qū)主干道，共包含1 519 065個(gè)激光點(diǎn)，長(zhǎng)度約為120 m，道路寬度在局部不一致，路面整體比較平坦，如圖5(b)所示。兩組數(shù)據(jù)中均包含道路、行道樹(shù)、路燈、電力設(shè)施及汽車(chē)等地物。

圖5 原始車(chē)載點(diǎn)云數(shù)據(jù)

2.2 試驗(yàn)結(jié)果與分析

首先，使用開(kāi)源點(diǎn)云數(shù)據(jù)處理軟件CloudCompare中的布料模擬濾波算法對(duì)兩組原始車(chē)載點(diǎn)云進(jìn)行濾波。數(shù)據(jù)1整體為坡度地形，因此硬度參數(shù)設(shè)為2、大格網(wǎng)分辨率為1.5 m、距離閾值為0.5 m、迭代次數(shù)為150次，同時(shí)選中坡度擬合因子進(jìn)行邊坡后處理。數(shù)據(jù)2整體比較平坦，因此硬度參數(shù)設(shè)為1，其余參數(shù)保持不變。兩組數(shù)據(jù)使用布料模擬濾波后的結(jié)果如圖6所示，濾波后的點(diǎn)云數(shù)據(jù)主要包括道路和道路兩旁的人行道區(qū)域，其中出現(xiàn)的空洞是車(chē)輛被濾波去除后所致。

圖6 濾波后地面點(diǎn)

然后，對(duì)濾波后點(diǎn)云數(shù)據(jù)使用C++語(yǔ)言，在VS2013環(huán)境下編程實(shí)現(xiàn)本文提出的道路面提取方法。其中，法向量計(jì)算時(shí)點(diǎn)云鄰域查找方式為KNN，查找點(diǎn)數(shù)量參數(shù)設(shè)置為30；區(qū)域生長(zhǎng)時(shí)鄰域搜索參數(shù)也設(shè)置為30，兩組數(shù)據(jù)曲率閾值Kt均為0.04，數(shù)據(jù)1法向量夾角閾值Sθ為8°，數(shù)據(jù)2為5°。最后，兩組數(shù)據(jù)的道路面提取結(jié)果如圖7、圖8所示。

圖7 數(shù)據(jù)1路面提取結(jié)果

圖8 數(shù)據(jù)2路面提取結(jié)果

準(zhǔn)確性p、完整性r和檢測(cè)質(zhì)量q是用于評(píng)估道路提取精度廣泛使用的定量指標(biāo)[16]。為了對(duì)試驗(yàn)結(jié)果進(jìn)行客觀分析與評(píng)價(jià)，筆者通過(guò)手工從原始點(diǎn)云中選取出路面點(diǎn)云作為參考數(shù)據(jù)，并結(jié)合試驗(yàn)提取的非路面點(diǎn)計(jì)算上述3個(gè)評(píng)價(jià)指標(biāo)，公式定義如下

p=TP/(TP+FP)

(5)

r=TP/(TP+FN)

(6)

q=TP/(TP+FP+FN)

(7)

式中，TP為試驗(yàn)中正確提取的路面點(diǎn)數(shù)量；FP為提取的非路面點(diǎn)數(shù)量；FN為未提取的道路點(diǎn)數(shù)量。

對(duì)試驗(yàn)提取的路面點(diǎn)統(tǒng)計(jì)分析結(jié)果見(jiàn)表1，兩組數(shù)據(jù)進(jìn)行道路提取的準(zhǔn)確性p、完整性r和檢測(cè)質(zhì)量q均在93%以上。其中，兩組數(shù)據(jù)提取的路面在局部邊緣處存在少量缺失，是由路面車(chē)輛等障礙物的遮擋所致。試驗(yàn)結(jié)果表明，本文方法可以在復(fù)雜的城市環(huán)境下進(jìn)行結(jié)構(gòu)化道路面的提取，并且受道路寬度及形狀的影響不大。

表1 試驗(yàn)結(jié)果分析 (%)

3 結(jié) 語(yǔ)

本文充分利用結(jié)構(gòu)化道路點(diǎn)云的法向量分布特征，提出了一種基于點(diǎn)云法向量相似度的道路面提取方法。通過(guò)對(duì)試驗(yàn)提取的道路面點(diǎn)云進(jìn)行目視評(píng)價(jià)及定量分析，結(jié)果表明該方法適用于城鎮(zhèn)環(huán)境下的結(jié)構(gòu)化道路面提取。對(duì)車(chē)輛和行人等遮擋造成的路面局部邊緣的缺失進(jìn)行修補(bǔ)，以及進(jìn)一步精細(xì)化提取道路標(biāo)線和標(biāo)志是下一步的主要研究工作。