基于共享單車軌跡的精細路網更新方法

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

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

0 引言

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

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

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

1 研究方法

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

圖1 總體技術路線Fig.1 Overall technical route

1.1 軌跡數據預處理

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

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

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

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

1.2.1 軌跡分區塊索引 使用空間索引處理大規模軌跡數據，能夠減少計算量，提高算法效率。利用歷史路網數據建立緩沖區，緩沖區距離參考現行道路寬度技術標準[21]。利用道路緩沖面將研究區分割，將屬于區塊內的軌跡數據視為增量變化軌跡，賦予其對應區塊的空間索引。

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

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

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

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中點坐標；θ(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:設置初始聚類ID=0；

2:將T中所有軌跡標記為未分類；

//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: 標記l為噪聲軌跡；

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

//Stage 3:返回結果

15:forCinO(C∈O):

16: iflen(C)

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

18:returnO

1.3 路網精細拓撲結構更新

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

1.3.2 新增道路拓撲更新 將提取的新增路段合并到原始路網中，即在新增路段的端點和原路網之間建立拓撲關聯，以形成更新的完整路網。本研究采用基于拓撲規則的方法更新路網(圖4)，具體過程為：1)對于新增路段的端點以R為半徑作鄰域，如果鄰域內有道路拓撲點，則認為新增路段端點與該拓撲點相連，如圖4路段②的下端點A；2)如果鄰域內存在道路但沒有道路拓撲點，則認為新增路段端點直接與道路連接；3)如果兩個新增路段鄰域相交，則認為兩個端點在兩者中點處相連，如圖4路段④的下端點B；4)如果鄰域內不存在道路，則認為新增路段端點在路網中與原始路網不相連，如圖4路段⑤的右端點C。

圖4 道路拓撲連接示意Fig.4 Schematic diagram of road topology connection

2 實驗與結果分析

2.1 實驗區域與數據

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

圖5 研究區共享單車軌跡數據和路網Fig.5 Trajectory data of shared bikes and road network in the study area

2.2 實驗流程

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

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

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

2.3 道路提取與更新結果分析

為與本文最小外包矩形骨架線道路提取法相對比，采用柵格細化法[26]對軌跡聚類簇進行柵格細化并提取道路中心線。為保證軌跡簇轉柵格后不出現空隙，對軌跡線生成8 m緩沖區(圖7a)；將軌跡簇面轉換為柵格數據后采用經典Zhang-Suen算法[27]得到柵格中心線(圖7b)，并將柵格中心線基于拓撲規則進行道路更新(圖7c)。利用本文方法對軌跡聚類簇分別生成最小外包矩形及其長邊方向中心線，利用拓撲規則將得到的中心線與原始道路構建拓撲連接以完成道路更新(圖7d-圖7f)。比較兩種方法得到的道路中心線，發現柵格細化法的新增道路在兩端表現不佳，在進行后續拓撲連接時所需端點拓撲搜索鄰域更大，從而影響更新結果質量。

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

在新增道路拓撲更新階段，依據城市道路等級中支路路寬[28]并結合單車GPS點定位誤差[19]，將提取的道路中線端點鄰域半徑R依次設為10 m、20 m、30 m，分別對兩種方法獲取新增道路中心線進行拓撲更新實驗，之后對3次實驗結果進行拓撲錯誤檢查。由表1可知，道路端點鄰域半徑為10 m時，本文方法拓撲連接錯誤數為2個，拓撲錯誤率僅為6.67%，在鄰域半徑為20 m和30 m時，本文方法未出現拓撲錯誤；文獻[26]方法在鄰域半徑為10 m和20 m時拓撲錯誤率均高達50%左右。考慮兩種方法的參數及拓撲一致性，選取30 m作為道路端點鄰域半徑，對比兩種方法拓撲更新后道路結果(圖7c和圖7f)可知，本文方法提取的新增路段較直。因此，本文方法在道路兩端表現比柵格細化法更優，能夠在較小的端點鄰域內保證道路更新結果的拓撲連接性及準確性，且形狀更符合真實情況。

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

2.4 精度評價

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

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

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

2.4.2 定量評價 為定量評估道路更新結果的準確性以及本文方法的穩定性，本研究采用線要素緩沖區相似度法[29]評價兩種方法的精度及數據量對方法的敏感性。

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

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

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

圖10 不同數據量下結果精度檢驗Fig.10 Accuracy test of results with different data volume

3 結論與展望

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

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