基于共享單車軌跡的精細(xì)路網(wǎng)更新方法

郭 文 峰，萬 義 良*，金 瑞，黃 金 彩，張 睿 媛

(1.湖南師范大學(xué)地理科學(xué)學(xué)院，湖南 長沙 410081；2.地理空間大數(shù)據(jù)挖掘與應(yīng)用湖南省重點實驗室，湖南 長沙 410081；3.湖南大學(xué)城鄉(xiāng)規(guī)劃系，湖南 長沙 410082；4.中南大學(xué)大數(shù)據(jù)研究院，湖南 長沙 410083)

0 引言

路網(wǎng)數(shù)據(jù)是城市交通系統(tǒng)的重要基礎(chǔ)地理數(shù)據(jù)，如何快速、精準(zhǔn)地更新路網(wǎng)數(shù)據(jù)以保持路網(wǎng)的現(xiàn)勢性，對緩解城市交通擁堵、保障居民出行效率具有重要意義。傳統(tǒng)測繪生產(chǎn)及遙感影像提取[1]等途徑獲取變更道路數(shù)據(jù)存在成本高、路網(wǎng)易被遮擋等問題。近年來，隨著GPS設(shè)備的普及，眾源軌跡數(shù)據(jù)憑借其成本低、覆蓋率高、現(xiàn)勢性強等優(yōu)勢，為道路數(shù)據(jù)的提取與更新提供了新的研究思路[2-4]，如何利用海量軌跡數(shù)據(jù)有效且準(zhǔn)確提取和更新道路信息[5]，已成為當(dāng)今地理信息領(lǐng)域研究的熱點。

現(xiàn)有利用軌跡數(shù)據(jù)更新路網(wǎng)方法可分為全局重建法和局部增量更新法兩大類，前者可分為柵格細(xì)化法[6,7]、軌跡聚類法[8-10]、增量軌跡合并法[11,12]和混合法[4,13,14]4個子類,一般需要高頻高精度軌跡作為數(shù)據(jù)支撐，后者優(yōu)勢在于聚焦原始道路變化路段的局部更新。趙東保等[15]創(chuàng)建原始路網(wǎng)緩沖區(qū)，并將緩沖區(qū)外的GPS采樣點識別為原始路網(wǎng)的附加變化，之后將失配的采樣點轉(zhuǎn)換為二值圖像，通過提取柵格骨架作為新增道路；楊偉等[16]以道路緩沖區(qū)為研究單元，結(jié)合軌跡幾何特征和交通語義信息進行道路變化檢測，然后利用Delaunay三角網(wǎng)方法提取變化道路后進行道路更新。上述基于緩沖區(qū)的檢測方法高效、直接，但緩沖區(qū)閾值較難確定。唐爐亮等[17]利用軌跡交通方向、拓?fù)浜蛶缀侮P(guān)系約束檢測原始路網(wǎng)變化，然后使用多項式曲線擬合算法生成新道路的中心線；Wu等[18]基于隱馬爾可夫模型(Hidden Markov Model，HMM)地圖匹配進行失配軌跡檢測，利用失配軌跡進行局部道路更新,雖能準(zhǔn)確檢測變化路段，但針對大規(guī)模軌跡數(shù)據(jù)計算效率較低;Tang等[19]利用軌跡幾何特征匹配路段檢測新增道路，運用圖自適應(yīng)聚類算法[20]提取新增道路，最后基于形態(tài)學(xué)算法完成路網(wǎng)更新。綜上，現(xiàn)有基于車輛軌跡自動提取道路的方法多為全局路網(wǎng)拓?fù)浣Y(jié)構(gòu)提取，采樣頻率和道路覆蓋率低，難以滿足多樣化導(dǎo)航位置服務(wù)的需求，且全局路網(wǎng)重建會造成大量計算冗余，計算效率低。

相比機動車軌跡數(shù)據(jù)，共享單車軌跡多分布于道路兩側(cè)，包含的出行信息更精細(xì)，直接使用上述方法更新道路效果欠佳。鑒于此，本文基于局部路網(wǎng)更新的檢測—提取—更新思想，提出一種分段—聚類—聚合增量軌跡數(shù)據(jù)自動生成道路方法，以期降低路網(wǎng)數(shù)據(jù)更新成本，快速感知城市交通路網(wǎng)動態(tài)。

1 研究方法

本文利用共享單車軌跡數(shù)據(jù)提取道路更新路段，并依據(jù)新增路段與原始道路數(shù)據(jù)的拓?fù)湟?guī)則更新道路數(shù)據(jù)，具體實現(xiàn)流程(圖1)為：對共享單車軌跡數(shù)據(jù)進行預(yù)處理，運用歷史道路緩沖面進行初步增量軌跡分區(qū)；基于垂距限值法進行完整軌跡分段并進一步檢測增量軌跡；采用改進的多特征閾值密度聚類算法進行子軌跡聚類，采用最小外包矩形(Minimum Bounding Rectangle，MBR)骨架線法提取增量道路中心線，基于拓?fù)湟?guī)則將新增道路與原始道路融合，最終完成路網(wǎng)更新。

圖1 總體技術(shù)路線Fig.1 Overall technical route

1.1 軌跡數(shù)據(jù)預(yù)處理

原始的共享單車軌跡數(shù)據(jù)多存在異常點、噪聲點、漂移軌跡點等問題，因此在挖掘分析前通常要對數(shù)據(jù)進行預(yù)處理，主要包括：1)軌跡提取。初始共享單車數(shù)據(jù)主要包含車輛ID、時間戳、經(jīng)度、緯度4個字段，數(shù)據(jù)量大、信息雜亂，難以直接使用，需對其按研究范圍經(jīng)緯度進行去零、篩選、排序及分組以提取同一輛單車的運動軌跡。2)軌跡清洗。為剔除數(shù)據(jù)中的異常點和噪聲點，常用相鄰軌跡點之間的平均速度閾值將一些長時間停留點、定位異常點以及由于工作人員單車回收及調(diào)動產(chǎn)生的無用軌跡點剔除。軌跡平均采樣時間間隔為3 s，結(jié)合單車騎行特性及實際數(shù)據(jù)分析，通過前后相鄰軌跡點之間的歐氏距離閾值和平均速度閾值進行判斷。3)單車行程篩選及軌跡平滑。對于同一輛單車軌跡數(shù)據(jù)，依據(jù)相鄰兩軌跡點之間的距離和時間間隔判斷中間軌跡點是否為打斷點，完成軌跡行程的篩選。由于采樣點的隨機誤差，完整軌跡中存在噪聲點(尖銳點)，本文采用滑動中值濾波消除部分噪聲點，以達到平滑軌跡的效果。

1.2 軌跡分段和多特征融合軌跡聚類

對完整軌跡線段直接聚類不能較好地獲取道路的局部特征，因此本文提出一種針對單車軌跡數(shù)據(jù)的分段—聚類—聚合道路信息提取方法(圖2)。

圖2 分段—聚類—聚合式道路提取方法Fig.2 Road extraction method based on segmentation-clustering-aggregation strategy

1.2.1 軌跡分區(qū)塊索引 使用空間索引處理大規(guī)模軌跡數(shù)據(jù)，能夠減少計算量，提高算法效率。利用歷史路網(wǎng)數(shù)據(jù)建立緩沖區(qū)，緩沖區(qū)距離參考現(xiàn)行道路寬度技術(shù)標(biāo)準(zhǔn)[21]。利用道路緩沖面將研究區(qū)分割，將屬于區(qū)塊內(nèi)的軌跡數(shù)據(jù)視為增量變化軌跡，賦予其對應(yīng)區(qū)塊的空間索引。

1.2.2 軌跡特征點提取及分段 本文使用垂距限值法[22]提取軌跡特征點，利用特征點進行軌跡分段。相較于經(jīng)典的全局壓縮Douglas-Peucker算法[23]，垂距限值法能更好地保留軌跡的局部特征，算法原理(圖3)為：從點B開始，計算點A到B、C所連直線的距離dtr：若dtr大于閾值d0，則保留B，計算C到B、D所連直線的距離dtr；若dtr小于閾值d0,則舍棄點B，計算C到A和D所連直線的距離dtr;依次類推，直至計算到曲線上倒數(shù)第二個點。經(jīng)上述處理后，仍有部分軌跡在現(xiàn)有道路上。因此，在軌跡分段后，利用軌跡線段與道路間的幾何特征閾值進一步篩選增量軌跡，幾何特征包括軌跡線段與鄰近道路間的距離閾值d′、角度閾值α′。當(dāng)軌跡線段和鄰近道路間距離與角度同時滿足在距離與角度閾值之內(nèi)，表明這類軌跡線段是緩沖區(qū)法漏判的非增量軌跡，將其剔除；否則予以保留。

圖3 軌跡特征點提取示意Fig.3 Schematic diagram of trajectory feature points extraction

1.2.3 多特征閾值子軌跡聚類 本研究運用線段密度聚類思想，在Traclus方法[24]基礎(chǔ)上得到一種改進多特征閾值聚類算法。為度量軌跡相似性，使用中點距離特征dcenter、角度特征θ、軌跡長度距離特征dlen描述軌跡線段距離(式(1)-式(4))。為避免軌跡間連續(xù)角度偏移導(dǎo)致聚類結(jié)果誤差過大，設(shè)角度閾值的約束條件為中心軌跡線段同時與前后子軌跡線段比較，均在角度閾值內(nèi)。子軌跡聚類算法詳見算法1。算法執(zhí)行后，利用歷史路網(wǎng)數(shù)據(jù)對軌跡聚類簇進行篩選，再根據(jù)軌跡簇的平均長度去除短軌跡聚類簇，得到有效的新增道路軌跡聚類簇。

dcenter(Li，Lj)=‖centeri-centerj‖

(1)

(2)

dlen(Li，Lj)=|Li|-|Lj|

(3)

N(Li)={Lj∈T|dcenter(Li,Lj)≤ε,θ(Li,Lj)≤α,θ(Lj-1,Lj)≤α,dlen(Li,Lj)≤ρ}

(4)

式中：dcenter(Li,Lj)為軌跡線段Li與Lj中點距離；centeri和centerj分別為Li、Lj中點坐標(biāo)；θ(Li,Lj)為Li與Lj的夾角；dlen(Li,Lj)為Li、Lj的長度距離；N(Li)表示3種特征閾值都滿足的相似軌跡鄰域。

算法1 子軌跡聚類算法

輸入:軌跡線段集合T={l1,l2,l3，…，ln},聚類閾值ε、α、ρ，密度閾值m

輸出:聚類簇集合O={C1,C2,C3，…，Cn}

//Stage 1:初始化

1:設(shè)置初始聚類ID=0；

2:將T中所有軌跡標(biāo)記為未分類；

//Stage 2：子軌跡聚類

3:遍歷每個線段l(l∈T):

4: ifl為未分類線段：

5: ifdcenter(li,lj)≤ε,θ(li,lj)≤α,θ(lj-1,lj)≤α,dlen(li,lj)≤ρ：

6: 計算l的鄰域N(l)；

7: iflen(N(l))≥m:

8: 將ID分配給l∈N(l);

9:N(l)-{l} 插入 隊列Q;

10: 拓展分別計算Q每條線段的鄰域；

11: ID+=1；

12: else:

13: 標(biāo)記l為噪聲軌跡；

14:將線段l∈分配到聚類C{ID}中；

//Stage 3:返回結(jié)果

15:forCinO(C∈O):

16: iflen(C)

17: 從O集合中刪除集合C，剔除小簇；

18:returnO

1.3 路網(wǎng)精細(xì)拓?fù)浣Y(jié)構(gòu)更新

1.3.1 MBR骨架線法道路提取 目前將軌跡簇聚合成道路中心線的方法較成熟，本文在張莉婷等[25]利用緩沖區(qū)提取道路中心線的基礎(chǔ)上，提出一種基于最小外包矩形(MBR)骨架線提取新增道路中心線方法：首先，對新增軌跡聚類簇按聚類簇寬度生成最小外包矩形；然后，遍歷每個最小外包矩形的四至坐標(biāo)，計算出短邊的中點坐標(biāo)，作為道路中心線的起止點坐標(biāo)，連接兩個中點即為新增道路中心線。

1.3.2 新增道路拓?fù)涓?將提取的新增路段合并到原始路網(wǎng)中，即在新增路段的端點和原路網(wǎng)之間建立拓?fù)潢P(guān)聯(lián)，以形成更新的完整路網(wǎng)。本研究采用基于拓?fù)湟?guī)則的方法更新路網(wǎng)(圖4)，具體過程為：1)對于新增路段的端點以R為半徑作鄰域，如果鄰域內(nèi)有道路拓?fù)潼c，則認(rèn)為新增路段端點與該拓?fù)潼c相連，如圖4路段②的下端點A；2)如果鄰域內(nèi)存在道路但沒有道路拓?fù)潼c，則認(rèn)為新增路段端點直接與道路連接；3)如果兩個新增路段鄰域相交，則認(rèn)為兩個端點在兩者中點處相連，如圖4路段④的下端點B；4)如果鄰域內(nèi)不存在道路，則認(rèn)為新增路段端點在路網(wǎng)中與原始路網(wǎng)不相連，如圖4路段⑤的右端點C。

圖4 道路拓?fù)溥B接示意Fig.4 Schematic diagram of road topology connection

2 實驗與結(jié)果分析

2.1 實驗區(qū)域與數(shù)據(jù)

本文以64位Windows 10操作系統(tǒng)為實驗平臺，PC機硬件配置為：Intel core i7-10750H處理器、16 G DDR4內(nèi)存，在Python 3.7和ArcGIS 10.2開發(fā)環(huán)境下實現(xiàn)。選取廣州市2019年6月10日共享單車軌跡作為研究區(qū)數(shù)據(jù)，包含28萬個采樣點，約9 500條軌跡。軌跡數(shù)據(jù)字段包含共享單車ID號、GPS點的采樣時間和經(jīng)緯度，軌跡點的采樣間隔為3 s左右；以2019年OSM道路作為歷史道路更新數(shù)據(jù)，以天地圖影像、2020年高德地圖道路數(shù)據(jù)作為實驗檢驗數(shù)據(jù)，研究區(qū)軌跡路網(wǎng)數(shù)據(jù)如圖5所示。

圖5 研究區(qū)共享單車軌跡數(shù)據(jù)和路網(wǎng)Fig.5 Trajectory data of shared bikes and road network in the study area

2.2 實驗流程

對共享單車軌跡數(shù)據(jù)進行數(shù)據(jù)清洗，當(dāng)距離閾值為100 m、時間閾值為48 s時，軌跡行程篩選效果最佳。處理后軌跡點數(shù)為69 060個，包含7 685條軌跡，軌跡壓縮比為75.17%，在保留軌跡信息的同時，較大程度上減少了軌跡冗余，有利于提高算法的效率。

利用2019年歷史OSM路網(wǎng)數(shù)據(jù)，依據(jù)現(xiàn)行國家道路寬度建設(shè)標(biāo)準(zhǔn)建立8 m緩沖區(qū)，對研究區(qū)進行區(qū)塊劃分，將不在緩沖區(qū)范圍內(nèi)的單車軌跡數(shù)據(jù)用于提取增量軌跡(圖6a)；多次重復(fù)實驗發(fā)現(xiàn)，設(shè)置垂距限值距離d0為5 m進行軌跡分段能較好保留道路信息，軌跡分段結(jié)果如圖6b所示；軌跡分段后，依據(jù)文獻[19]設(shè)置軌跡線段與鄰近道路之間的距離閾值為50 m、角度閾值為15 °，利用軌跡線段與道路之間的幾何特征完成增量軌跡篩選。對增量軌跡進行聚類，經(jīng)多次實驗選出最優(yōu)聚類參數(shù)：中點距離閾值為10 m，角度閾值為12°，長度距離閾值為10 m，最小軌跡數(shù)為7條。子軌跡聚類完成后，對軌跡聚類簇進行后處理，剔除小簇及道路邊沿簇。最后，根據(jù)空間位置關(guān)系將屬于一條新增道路的軌跡簇合并，最終得到18個軌跡簇(圖6c)。

圖6 軌跡預(yù)處理、分段、聚類結(jié)果示意Fig.6 Schematic diagram of trajectory pre-processing,segmentation,clustering results

2.3 道路提取與更新結(jié)果分析

為與本文最小外包矩形骨架線道路提取法相對比，采用柵格細(xì)化法[26]對軌跡聚類簇進行柵格細(xì)化并提取道路中心線。為保證軌跡簇轉(zhuǎn)柵格后不出現(xiàn)空隙，對軌跡線生成8 m緩沖區(qū)(圖7a)；將軌跡簇面轉(zhuǎn)換為柵格數(shù)據(jù)后采用經(jīng)典Zhang-Suen算法[27]得到柵格中心線(圖7b)，并將柵格中心線基于拓?fù)湟?guī)則進行道路更新(圖7c)。利用本文方法對軌跡聚類簇分別生成最小外包矩形及其長邊方向中心線，利用拓?fù)湟?guī)則將得到的中心線與原始道路構(gòu)建拓?fù)溥B接以完成道路更新(圖7d-圖7f)。比較兩種方法得到的道路中心線，發(fā)現(xiàn)柵格細(xì)化法的新增道路在兩端表現(xiàn)不佳，在進行后續(xù)拓?fù)溥B接時所需端點拓?fù)渌阉鬣徲蚋螅瑥亩绊懜陆Y(jié)果質(zhì)量。

圖7 文獻[26]及本文方法道路提取和更新結(jié)果對比Fig.7 Comparison of road extraction and update results of the method in literature[26] and the proposed method in this paper

在新增道路拓?fù)涓码A段，依據(jù)城市道路等級中支路路寬[28]并結(jié)合單車GPS點定位誤差[19]，將提取的道路中線端點鄰域半徑R依次設(shè)為10 m、20 m、30 m，分別對兩種方法獲取新增道路中心線進行拓?fù)涓聦嶒灒髮?次實驗結(jié)果進行拓?fù)溴e誤檢查。由表1可知，道路端點鄰域半徑為10 m時，本文方法拓?fù)溥B接錯誤數(shù)為2個，拓?fù)溴e誤率僅為6.67%，在鄰域半徑為20 m和30 m時，本文方法未出現(xiàn)拓?fù)溴e誤；文獻[26]方法在鄰域半徑為10 m和20 m時拓?fù)溴e誤率均高達50%左右。考慮兩種方法的參數(shù)及拓?fù)湟恢滦裕x取30 m作為道路端點鄰域半徑，對比兩種方法拓?fù)涓潞蟮缆方Y(jié)果(圖7c和圖7f)可知，本文方法提取的新增路段較直。因此，本文方法在道路兩端表現(xiàn)比柵格細(xì)化法更優(yōu)，能夠在較小的端點鄰域內(nèi)保證道路更新結(jié)果的拓?fù)溥B接性及準(zhǔn)確性，且形狀更符合真實情況。

表1 文獻[26]及本文方法更新道路拓?fù)溴e誤檢查Table 1 Road topology errors based on the method in literature[26] and the proposed method in this paper

2.4 精度評價

為驗證本文方法對于歷史路網(wǎng)的新增路段變化檢測及更新的有效性和準(zhǔn)確性，對更新的道路結(jié)果分別進行定性及定量精度評價。

2.4.1 定性評價 借鑒文獻[28]中疊加谷歌衛(wèi)星影像進行目視解譯的方法，本文將更新后道路數(shù)據(jù)疊加到天地圖衛(wèi)星影像、OSM電子地圖和高德地圖路網(wǎng)進行定性可視化檢測。通過對比發(fā)現(xiàn)，本文方法構(gòu)建的新增道路與天地圖衛(wèi)星影像中的真實道路匹配良好(圖8a)，與OSM電子地圖、高德地圖路網(wǎng)數(shù)據(jù)(圖8b、圖8c)基本相符，部分區(qū)域提取的道路中心線幾何精度較高。從衛(wèi)星圖像可以發(fā)現(xiàn)，基于共享單車軌跡能夠有效提取出機動車難以覆蓋的新增道路數(shù)據(jù)，如學(xué)校、居民區(qū)、街道社區(qū)等半封閉區(qū)域的小路(圖8a中區(qū)域A、B、C、D、E)，解決了細(xì)尺度道路機動車軌跡覆蓋不足的問題，體現(xiàn)了本文方法使用共享單車軌跡的優(yōu)勢。

圖8 新增道路可視化比較Fig.8 Visualization comparison of updated roads

2.4.2 定量評價 為定量評估道路更新結(jié)果的準(zhǔn)確性以及本文方法的穩(wěn)定性，本研究采用線要素緩沖區(qū)相似度法[29]評價兩種方法的精度及數(shù)據(jù)量對方法的敏感性。

(1)以2020年高德地圖道路數(shù)據(jù)作為第三方數(shù)據(jù)，檢驗新增道路的精度，依次建立2 m、5 m、7 m和10 m緩沖區(qū)，實際提取的道路中心線落在緩沖區(qū)內(nèi)的長度占提取道路總長度的百分比即為提取精度，定量評價結(jié)果如圖9所示。可以看出，在2 m和5 m更精細(xì)尺度的緩沖區(qū)范圍內(nèi)，本文方法比柵格細(xì)化法的精度提高了14%左右；在7 m和10 m兩種尺度下，本文方法提取新增道路覆蓋精度達90%以上，特別是在10 m緩沖區(qū)范圍內(nèi)，提取新增道路覆蓋精度達96%以上。由于文中所用的柵格細(xì)化法是針對軌跡聚類簇進行的，基本過濾了噪聲軌跡線段，故柵格細(xì)化法在10 m尺度的緩沖區(qū)范圍內(nèi)也能達到較好的精度。

圖9 兩種方法精度定量對比Fig.9 Comparison of quantitative accuracy evaluation of the two methods

(2)為從數(shù)據(jù)量方面分析本文方法的魯棒性，探究不同數(shù)據(jù)量對方法穩(wěn)定性的影響，隨機篩選20%、40%、60%、80%和全體軌跡數(shù)據(jù)進行實驗，并對道路更新結(jié)果進行精度評價(圖10)。在2 m、5 m緩沖區(qū)范圍內(nèi)，更新道路提取精度僅在40%、60%和80%的軌跡數(shù)據(jù)量時表現(xiàn)較平穩(wěn)；而在7 m和10 m緩沖區(qū)范圍內(nèi)，不同數(shù)據(jù)量情景下的新增道路提取精度均較平穩(wěn)，表明本文方法在7 m和10 m兩種尺度下的魯棒性較好。

圖10 不同數(shù)據(jù)量下結(jié)果精度檢驗Fig.10 Accuracy test of results with different data volume

3 結(jié)論與展望

本文基于共享單車軌跡數(shù)據(jù)更新歷史道路，提出一種基于軌跡分段—子軌跡聚類—簇聚合的增量道路提取方法。利用路段緩沖區(qū)進行軌跡分區(qū)，并結(jié)合軌跡—路網(wǎng)幾何特征確定增量變化軌跡；利用垂距限值法對增量軌跡進行分段能較好保持路段的局部信息，采用多約束閾值密度聚類算法，通過MBR骨架線提取法提取軌跡簇道路中心線，最后基于拓?fù)湟?guī)則進行增量道路信息更新。利用廣州市共享單車真實軌跡數(shù)據(jù)集將本文方法與傳統(tǒng)的柵格細(xì)化法進行對比實驗，結(jié)果表明：本文方法不僅能有效更新道路網(wǎng)絡(luò)且精度更高，在2 m和5 m精細(xì)尺度范圍內(nèi)精度提升14%左右，在7 m和10 m兩種尺度范圍內(nèi)精度達90%以上，特別是在10 m緩沖區(qū)內(nèi)精度達96%以上，驗證了本文方法的有效性和準(zhǔn)確性。閾值參數(shù)檢驗及魯棒性分析表明，本文方法能較好地保持道路拓?fù)溥B通性，且魯棒性較強，具有更高的實際應(yīng)用價值。

利用軌跡數(shù)據(jù)進行路網(wǎng)更新具有充分的現(xiàn)勢性和可行性。本文方法將推動自行車行駛路網(wǎng)更新技術(shù)的發(fā)展，但受共享單車軌跡數(shù)據(jù)自身精度和覆蓋度的影響，軌跡數(shù)據(jù)在更新路網(wǎng)結(jié)果的精度以及完整性上仍具有一定局限。今后可融合公交數(shù)據(jù)、出租車軌跡、手機信令等更高精度的多源時空數(shù)據(jù)，實現(xiàn)更完整的城市精細(xì)路網(wǎng)提取。