一種依據點云法向量相似度的結構化道路提取方法

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

(1. 長安大學地質工程與測繪學院，陜西 西安 710054； 2. 陜西省交通規劃設計研究院，陜西 西安 710065； 3. 地理國情監測國家測繪地理信息局工程技術研究中心，陜西 西安 710064)

高精度、準確、現勢性強的道路三維信息對于道路維護、交通管理、城市規劃等具有重要作用[1]。近年來，以車輛為搭載平臺，集成GPS、INS、激光掃描儀、CCD相機等多種傳感器，在傳感器同步控制的基礎上，能夠獲取城市街道、建筑物立面的幾何數據和紋理信息，為道路信息快速獲取、更新及三維道路環境自動提取開辟了新的途徑[2]。

目前，國內外從車載點云數據中提取道路信息的研究方法主要可以歸納為從點云投影的特征圖像中間接提取和從離散點云直接提取兩類。

在點云投影的特征圖像中提取方面，主要依據城市環境中路面與鄰域之間的高程或密度差異，將原始點云數據轉換成特征圖像[3-6],再結合圖像處理的相關算法進行道路信息的提取。此類算法需要將離散點云轉換成格網，降低了原始數據的精度和分辨率。

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

本文結合道路面的點云法向量分布特征，提出一種依據點云法向量相似度的結構化道路提取方法。

1 車載點云的道路提取方法

1.1 非地面點濾波

城鎮道路環境通常比較復雜，原始車載點云中包括道路兩側大量的樹木、路燈、電線桿及路面上的汽車等非路面目標，這些非地面點會對點云局部法向量的準確計算和道路提取的效率、準確度帶來干擾，因此需要對原始點云濾波剔除非地面點。

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

圖1 CSF算法模擬示意圖

1.2 法向量及曲率估算原理

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

點云數據缺乏離散點間的幾何拓撲信息，為了實現基于鄰域關系的快速近鄰查找，要建立原始點云離散點間的拓撲關系。KD-tree由Bentley[12]于1975年首先提出，是一種分割k維數據空間的數據結構，其本質是帶有約束條件的二分查找樹，主要應用于多維空間數據中的近鄰搜索(KNN)和范圍搜索(FDN)。KD-tree在三維空間的結構如圖2所示。

圖2 三維KD-tree空間分割

1.2.2 基于PCA的法向量估算

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

對點云數據中每個點pi={xi,yi,zi}，通過鄰域查找獲得k個鄰域點，然后根據距離最小二乘準則計算出該點的局部擬合平面P，平面P可以用如下數學方程表示

(1)

式中，n為平面P的法向量；d為P到坐標原點的距離；argmin為目標函數取最小值時的變量值。

通過計算可知，k個近鄰點的三維質心位于平面P上，且法向量n為單位向量，滿足nTn=1。運用主成分分析方法(principal component analysis, PCA)，將求解點云法向量的問題轉化成k個近鄰點構建的協方差矩陣C特征值分解的問題。協方差矩陣C最小特征值對應的特征向量即為需要求解的法向量。

(2)

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

(3)

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

(4)

1.3 改進的區域生長算法

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

針對傳統區域生長法通常隨機選取種子點，容易導致過分分割且效率低下的問題，結合路面提取目標，對種子點的選取準則進行改進。結構化道路的空間特征如圖4所示，表現為局部比較平坦，同時路面點高程一般略低于周圍人行橫道等其他地物。因此，本文首先對原始點云按高程進行升序排列，再選擇其中曲率最小的點作為道路種子點。算法具體流程如下：

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

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

(3) 若法向量夾角Si

(4) 當前種子點出隊，若種子點隊列不為空，選出新種子點，回到步驟(2)。

上述分割過程結束后，聚類結果除路面區域外可能還有一些近似平面點群區域。道路路面所在區域一般為最大連通區域，且區域平均高程較小。因此可以設置閾值參數剔除非路面區域而得到道路面點云。

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

2 試驗與分析

2.1 試驗數據

試驗采用某車載移動測量系統獲取的兩組不同城鎮環境下比較典型的點云數據。數據1為城市高架，共包含3 689 279個激光點，長度約為300 m，道路寬度比較規則，路面呈坡狀，主要為彎曲道路，如圖5(a)所示；數據2為街區主干道，共包含1 519 065個激光點，長度約為120 m，道路寬度在局部不一致，路面整體比較平坦，如圖5(b)所示。兩組數據中均包含道路、行道樹、路燈、電力設施及汽車等地物。

圖5 原始車載點云數據

2.2 試驗結果與分析

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

圖6 濾波后地面點

然后，對濾波后點云數據使用C++語言，在VS2013環境下編程實現本文提出的道路面提取方法。其中，法向量計算時點云鄰域查找方式為KNN，查找點數量參數設置為30；區域生長時鄰域搜索參數也設置為30，兩組數據曲率閾值Kt均為0.04，數據1法向量夾角閾值Sθ為8°，數據2為5°。最后，兩組數據的道路面提取結果如圖7、圖8所示。

圖7 數據1路面提取結果

圖8 數據2路面提取結果

準確性p、完整性r和檢測質量q是用于評估道路提取精度廣泛使用的定量指標[16]。為了對試驗結果進行客觀分析與評價，筆者通過手工從原始點云中選取出路面點云作為參考數據，并結合試驗提取的非路面點計算上述3個評價指標，公式定義如下

p=TP/(TP+FP)

(5)

r=TP/(TP+FN)

(6)

q=TP/(TP+FP+FN)

(7)

式中，TP為試驗中正確提取的路面點數量；FP為提取的非路面點數量；FN為未提取的道路點數量。

對試驗提取的路面點統計分析結果見表1，兩組數據進行道路提取的準確性p、完整性r和檢測質量q均在93%以上。其中，兩組數據提取的路面在局部邊緣處存在少量缺失，是由路面車輛等障礙物的遮擋所致。試驗結果表明，本文方法可以在復雜的城市環境下進行結構化道路面的提取，并且受道路寬度及形狀的影響不大。

表1 試驗結果分析 (%)

3 結 語

本文充分利用結構化道路點云的法向量分布特征，提出了一種基于點云法向量相似度的道路面提取方法。通過對試驗提取的道路面點云進行目視評價及定量分析，結果表明該方法適用于城鎮環境下的結構化道路面提取。對車輛和行人等遮擋造成的路面局部邊緣的缺失進行修補，以及進一步精細化提取道路標線和標志是下一步的主要研究工作。