基于無人機的道路點云數(shù)據(jù)分割提取算法①

駱 磊, 馬榮貴, 薛 昊

(長安大學 信息工程學院, 西安 710064)

LiDAR 測量技術(shù)現(xiàn)在廣泛用于三維數(shù)字城市建設(shè)[1-3]、道路安全設(shè)施檢測[4,5]、公路勘察設(shè)計等方面[6,7], 車載LiDAR 測量具有數(shù)據(jù)采集的高精度、高效率和高密度等特性[8,9], 但是車載LiDAR 移動速度較慢, 影響道路使用, 而且當路況不好的時候, 車輛無法駛?cè)? 對于特殊狀況想要對道路進行檢測則力不從心; 機載LiDAR測量則是有快速度、高效率, 受天氣、路況影響小, 數(shù)據(jù)生產(chǎn)周期短等特性, 該測量方式可分為高空掃描和低空掃描, 相比于高空掃描, 低空掃描點云數(shù)據(jù)間隙小,精度更高[10], 更適合用于對道路的養(yǎng)護.因此本文使用低空飛行的無人機對特定的道路進行掃描.

道路數(shù)據(jù)的提取方法, 文獻[9]中提出了使用曲線擬合道路數(shù)據(jù)的算法, 但是只將路面的坡度走勢進行擬合, 并不能提高路面的提取精度, 文獻[11]提出以點云的區(qū)域分布特性為基礎(chǔ), 通過對數(shù)據(jù)進行主成分分析(PCA), 構(gòu)建點云平面基元檢測的新模型, 雖然能將平面進行分割, 但是由于道路細節(jié)近似拱形, 所以效果并不理想, 文獻[12]使用種子區(qū)域生長算法提取道路,但是需要手動確定種子點, 而且提取精度較粗, 不能將路面的坑槽有效提取.

綜上所述, 通過對上述算法的汲取和改進, 主要創(chuàng)新部分在于使用了聚類的算法來確定道路數(shù)據(jù)的種子點, 改進了半自動確定道路的方法, 并且用動態(tài)擬合的方式提取道路.

本文使用基于無人機的道路點云分割提取算法,主要內(nèi)涵在于無人機低空掃描提高數(shù)據(jù)精度和動態(tài)擬合分割提高提取精度, 其整體流程如圖1 所示, 使用無人機低空掃描路面獲取精度較高的點云數(shù)據(jù), 計算點云數(shù)據(jù)的法向量, 豐富數(shù)據(jù)信息, 為后續(xù)的聚類算法提供多維樣本數(shù)據(jù), 之后使用聚類算法根據(jù)點云數(shù)據(jù)的高程信息和法向量信息確定種子數(shù)據(jù), 再對斷面進行擬合, 利用數(shù)據(jù)動態(tài)擬合分割提取路面數(shù)據(jù)和非路面數(shù)據(jù), 最后對非路面數(shù)據(jù)使用區(qū)域生長算法進行分割.

圖1 算法流程圖

1 豐富點云數(shù)據(jù)信息

本文采用無人機裝載激光掃描設(shè)備的方法, 無人機低空沿道路方向飛行, 掃描指定路段, 為方便后續(xù)說明, 記y 軸方向為道路方向, x 軸方向為道路橫截面方向, z 軸為道路高程信息, 道路三維點云數(shù)據(jù)作為集合P.

后續(xù)聚類算法需要使用點云的法向量信息, 就要確定其法向量, 本文使用主成分分析法(Principal Component Analysis, PCA)[13-17], 用來計算點云數(shù)據(jù)的法向量.對于道路的點云數(shù)據(jù)集合P, 由于它是無序的, 所以在對集合P 進行處理之前, 需要為其建立拓撲關(guān)系,本文使用K-D 樹(K-Dimensional 樹的簡稱)[18-20]數(shù)據(jù)結(jié)構(gòu)建立點云之間的拓撲關(guān)系, 之后再用PCA 計算法向量.PCA 計算方法如下:

設(shè)集合P 中的點pi的k 鄰域點集為Nk(pi), 構(gòu)造關(guān)于點pi的3×3 協(xié)方差矩陣如式(1)所示:

矩陣C 表示了點集Nk(pi)的點的分布情況, 即鄰域點與質(zhì)心點p 的偏離程度, pk為k 鄰域點集中的點,p 為數(shù)據(jù)點pi及其k 鄰域所構(gòu)成集合的質(zhì)心.

矩陣C 為對稱半正定矩陣, 有3 個非負實數(shù)特征值, 設(shè)為λ0, λ1, λ2, 且λ0≤λ1≤λ2, 其對應的特征向量分別為v0, v1, v2.最小特征值λ0對應的特征向量v0即可近似為點pi的法向量ni, 為方便表示, 記單位法向量ni=(x, y, z).

2 路面及資產(chǎn)分割提取

2.1 多滑動窗口的均值漂移聚類算法確定種子數(shù)據(jù)

利用聚類算法提取道路信息, 存在3 個問題, 一是由于激光在掃描的時候存在噪聲, 所以并不是所有的點的法向量都接近聚類中心, 結(jié)果只能提取道路上的部分數(shù)據(jù); 二是如果對所有斷面都采用聚類算法, 雖然可以提取道路, 但是非常耗時; 三是針對路面上高程信息不明顯的數(shù)據(jù), 同樣需要提取, 而聚類算法并不能提取出來.

根據(jù)上述問題, 本文結(jié)合數(shù)據(jù)高程信息和法向量作為聚類算法的樣本點, 多滑動窗口的均值漂移聚類算法[21-23]確定擬合道路的種子數(shù)據(jù), 之后利用動態(tài)擬合提取所有路面.

因為高程信息與法向量的信息比例不同, 所以需要將高程數(shù)據(jù)范圍限定在0 到1, 則使用高程數(shù)據(jù)在高程區(qū)間的相對值h 做樣本空間的高程信息, h 值的計算公式如式(2)所示:

其中, zi為當前點的高程信息, Z 為所有數(shù)據(jù)點的高程信息集合.由式(1)得到數(shù)據(jù)點pi的法向量ni=(x, y, z),將這兩類數(shù)據(jù)投到特征空間, 則點pi在特征空間的向量為qi=(x, y, z, h).

得到標準化后的有n 個樣本點的特征空間Q=(q1,q2, …, qn)后, 使用多滑動窗口的均值漂移算法確定中心點, 在特征空間Q 中隨機選取10 個點作為初始中心點, 其滑動窗口半徑為r, 半徑r 的取值越大則對路面數(shù)據(jù)的要求越寬泛, 越小則越嚴格, 本文依據(jù)數(shù)據(jù)點到距離其最近的10 個點的距離來確定r 值, 公式如式(3):

其中, Si為數(shù)據(jù)點qi的最近鄰10 個樣本點的歐氏距離的集合.

由式(3)得到高維區(qū)域的歐氏距離半徑, 由高維區(qū)域內(nèi)的所有樣本點可以確定各個窗口的偏移均值, 其計算公式如式(4)所示:

其中, ci為窗口中心, Sr 為以ci為中心, 半徑為r 的高維區(qū)域, qj為區(qū)域內(nèi)的點, mi為區(qū)域內(nèi)qj的數(shù)量,M(ci)為以ci為窗口中心的偏移均值.

根據(jù)式對10 個滑動窗口進行中心更新, 更新公式如式(5)所示:

當中心點不再變化時, 停止更新滑動窗口的中心,則高維區(qū)域內(nèi)點數(shù)最多的兩個窗口內(nèi)的點分別為人行道和機動車道的數(shù)據(jù)點.通常, 人行道的高度要高于機動車路面, 因此兩個密度中心可以用高程信息來區(qū)分,高程信息低的是機動車路面, 高的是人行道路面.

2.2 對路面數(shù)據(jù)動態(tài)擬合

通過對道路數(shù)據(jù)點的觀察并結(jié)合實際, 機動車路面一般是中間稍高于兩側(cè), 這樣利于排除雨水.同樣,兩邊的人行道, 也存在一定弧度.可以將路面粗略描述為光滑曲面, 針對這種形狀, 采用四次多項式擬合路面橫斷面曲線, 使用最小二乘法計算多項式系數(shù).

擬合函數(shù)定義如下:

其中, a 為多項式系數(shù), x 為路面橫截橫坐標.由式(6)得到均方誤差, 均方誤差如式(7)所示:

為求式(7)的極小值, 得到方程如式(8)所示:

解方程得到a0, a1, a2, a3, a4帶入式(6)可以得到當前斷面的擬合函數(shù)f (x), 用當前斷面的擬合函數(shù)f (x)判斷下一斷面的點是否符合式(9).

符合式(9)的則為道路數(shù)據(jù)點, 不符合的則為非道路數(shù)據(jù)點.

其中, a 的計算公式如式(10)所示, 因為需要考慮道路的坡度問題, 根據(jù)《城市道路工程設(shè)計規(guī)范》內(nèi)容, 坡度最大不會超過11%, 所以對提取范圍修正.d 由式(11)計算求得, Di為數(shù)據(jù)點pi的最近鄰10 個點距離的集合, v 為無人機的移動速度, n 為激光掃描儀每秒掃描的次數(shù), 11%為國家規(guī)定公路最大坡度.

所謂動態(tài)擬合, 是將所有符合式的道路數(shù)據(jù)點進行如式擬合, 得到新的擬合函數(shù)f (x), 對下一斷面進行重復操作, 達到提取所有道路數(shù)據(jù)點的目的.

在利用擬合曲線提取機動車道和人行道路面數(shù)據(jù)時, 為避免使用擬合曲線時將周圍環(huán)境信息誤提, 需要對擬合曲線的區(qū)間進行約束.

通常情況下可以利用上一層斷面的數(shù)據(jù)確定機動車路面和人行道路面的范圍, 但是, 在有遮擋物的情況下計算的范圍會受到遮擋物影響, 而且不止會使當前路面的提取受到影響, 還會波及后面的計算, 所以, 準確的計算出路面的范圍是非常有必要的.針對這種情況, 提出基于寬度的路面范圍修正算法.

根據(jù)現(xiàn)實考慮, 因為左右兩邊人行道同時邊沿被遮擋的幾率很小, 所以可以利用左右兩邊人行道的寬度比修正左右兩邊, 利用靠墻點作為基準對寬度進行修正, 設(shè)計修正算法如下:

其中, ω′的值為兩邊人行道寬度的敏感程度, 越小越敏感, 越大越不敏感, 這里取 ω′為0.3, ω的確定公式如式(12)所示, x 的計算公式如式(13)所示:

經(jīng)過區(qū)間約束, 和路面擬合, 就可以利用上一斷面的擬合函數(shù)和區(qū)間約束來提取當前路面.

取某一斷面數(shù)據(jù)為例, 說明四次多項式可以很好的描述路面橫斷面的曲線.做出如表1 所示的以確定系數(shù)R-square 作為對比標準的擬合效果對比表:.

通過表可以看出, 無論是路面還是左右兩側(cè)的人行道, 當擬合次數(shù)達到四次時, 都可以有很好的擬合效果, 而當擬合次數(shù)達到五次時, 雖然略有提高, 但是變化不大, 在滿足擬合精確的前提下, 為保證算法運算速度, 防止出現(xiàn)過擬合現(xiàn)象, 確定使用四次擬合.

表1 擬合效果對比表

使用四次多項式擬合得到的擬合曲線, 為使圖像明顯, 對點云數(shù)據(jù)的橫坐標比例進行了縮放, 如圖2(a)、圖2(b)所示, 可以看到曲線在點云區(qū)間擬合效果很好.

2.3 改進區(qū)域生長算法對非路面數(shù)據(jù)分割

通過上述動態(tài)數(shù)據(jù)擬合的算法, 可以將路面數(shù)據(jù)提取出來, 達到將路面數(shù)據(jù)與非路面數(shù)據(jù)的分割, 對路面與非路面數(shù)據(jù)分割后, 再使用基于改進的區(qū)域生長三維點云分割算法[24]將非路面的各部分分別提取.其過程為先計算各個點的平均曲率Kn, 計算公式如式(14)所示:

式中, n 為法向量, Amin為p 周圍一個無限小的區(qū)域,αij、βij分別為連接pi和pj邊的對角.選取點云數(shù)據(jù)中曲率最小的點設(shè)置為種子點.

因為路面上的行人, 車輛以及資產(chǎn)之間距離較大,所以僅用距離作為閾值就可以將各部分分割, 選用式(11)的d 作為閾值, 判斷鄰近點與種子面之間的生長半徑是否小于閾值d, 將小于閾值的點添加到當前區(qū)域, 當再無點可以添加時, 則開始分割下一區(qū)域.

圖2 道路數(shù)據(jù)擬合圖

3 實驗結(jié)果分析

對西安市神州六路部分路段作為無人機數(shù)據(jù)獲取的實驗區(qū), 利用無人直升機Scout B1-100 搭載RIEGL VUX-1HA 激光掃描儀系統(tǒng)對實驗區(qū)進行掃描, 獲取道路點云數(shù)據(jù), 激光掃描儀的基本參數(shù)如表2 所示.

表2 激光掃描儀參數(shù)表

將本算法與區(qū)域生長提取路面算法對比, 驗證算法的效果.該路段效果如圖3 所示, 紅色部分為機動車道, 綠色部分為人行道, 藍色部分為路上資產(chǎn)和路面坑包, 黑色部分為路邊環(huán)境.

從圖3 中可以看出, 兩個算法很好的將道路上的路燈, 樹坑, 墻, 藍色部分兩邊為遮擋墻, 藍色豎線為路燈, 綠色人行道上的幾個藍色小塊為樹坑.通過圖3(a)路面上有些藍色點, 人行道上有一片土包可以看出, 本文算法可以將路面上的一些細節(jié)提取出來, 而且對于曲率變化較小的土包也可以提取出來, 而圖3(b)中的區(qū)域生長算法, 對路面上的細節(jié)卻不敏感, 而且對于曲率變化較小的土包也無法提取.用識別路面上的樹坑,土包, 凹槽數(shù)量作為對比說明兩種算法的效果, 列出表3.

為驗證該算法的適用性, 對西安市神州六路多處路段進行算法驗證, 結(jié)果如圖4 所示, 同樣, 紅色部分為機動車道, 綠色部分為人行道, 藍色部分為路上資產(chǎn)和路面坑包, 黑色部分為路邊環(huán)境, 對于多處路段, 都可以很好的將路面進行提取, 并且受周圍環(huán)境影響較小.當路面上有車輛時, 如圖4(b)、圖4(d)無論車輛是在提取路面的初始斷面, 還是在后續(xù)斷面, 都不會影響到路面的提取.

圖3 算法對比

表3 算法效果對比表

綜上所述, 本文算法可以很好的將路面數(shù)據(jù)進行識別, 將路面上的資產(chǎn)進行提取, 相比于傳統(tǒng)的使用區(qū)域生長算法識別路面, 本文算法對路面細節(jié)更加敏感.所以在路面養(yǎng)護和路上資產(chǎn)管理方面有很好的效果.

4 結(jié)語

本文在處理道路信息時, 比較依賴于掃描的起始位置, 雖然對遮擋物的抗干擾能力強, 但是, 對于遮擋物太多, 道路信息過少的情況下, 并不能很好的將道路數(shù)據(jù)的中心通過聚類算法聚類出來; 另外, 在對數(shù)據(jù)進行分割的時候, 對于雜糅在一起的數(shù)據(jù)也無法進行分割, 后續(xù)可以利用聚類算法, 或者神經(jīng)網(wǎng)絡(luò)對數(shù)據(jù)進行更好的分割; 最后對于和路面的高程數(shù)據(jù)差過小的數(shù)據(jù)也無法提取出來, 這種淹沒在噪聲中的有用數(shù)據(jù)提取難度很大, 需要后續(xù)仔細研究.

圖4 實驗結(jié)果