一種顧及道路復雜度的增量路網構建方法

劉紀平，張用川，徐勝華，錢新林，仇阿根，張福浩

1. 武漢大學資源與環境科學學院，湖北 武漢 430079； 2. 中國測繪科學研究院, 北京 100830

隨著城市的日益擴張，道路不斷翻修或拓建，交通規則也不時更新，導致路網信息不斷變化。例如，對于北京、上海這樣的大城市，每年有40%以上的地圖內容應該得到更新，而采用傳統的測繪方法更新常常需要幾個月甚至半年以上的時間[1]，同時需要耗費大量的人力、物力[2]。隨著越來越多的公共交通工具都搭載GNSS定位設備，如出租車，公共汽車，以及其他公共服務車輛，產生大量GNSS軌跡數據。這些軌跡數據中蘊含了機動車行駛過道路的大量信息，為導航路網信息的實時收集和更新提供的新機遇。然而，從軌跡數據中提取導航地圖信息，并自動構建導航路網地圖是一項具有挑戰的工作[3]。首先，由于普通定位設備存在較大誤差，使得同一條道路行駛的不同車輛產生的軌跡也有較大差異，復雜的城市道路環境也導致接收到的衛星信號不穩定，加劇了誤差的擴大；其次，普通車輛軌跡往往采樣周期較長，使得相鄰軌跡點較難體現出車輛真正行駛軌跡；再者，在立交橋、隧道、路網密集區域等復雜道路環境，通常難以確定某一軌跡點是否產生于某特定道路。由于以上問題，現實中導航路網地圖生產仍然需要大量手工編輯[4]。

近年來，國內外許多學者開始探索從粗糙軌跡數據中自動獲取道路信息來構建路網[5-9]。文獻[10]提出了一種基于每條軌跡與道路中心線的距離和方向參數進行聚類的方法，基于高精度的DGPS設備采集到的軌跡數據和模擬數據驗證了方法的有效性。文獻[4]模擬物理引力模型對軌跡數據進行了除噪和預處理，然后通過逐步融合軌跡得到道路網，并用通勤車在微軟園區專門采集的軌跡數據對其方法可行性進行了驗證。文獻[11]提出了一種以圖像學為基礎的混合方法，先將海量軌跡數據轉換為圖像，用圖像學方法提取道路骨架進行提取，然后再對其進行優化，并用真實充滿噪聲數據進行了驗證。文獻[12]提出了交通路口識別及結構提取的方法，并用武漢市出租車軌跡數據進行試驗證明了方法的有效性。另外，文獻[13]提出基于樸素貝葉斯的方法，從低精度機動車軌跡數據中挖掘路網中的車道數量和車輛行駛方向等信息。文獻[14]從人類活動軌跡的角度識別和提取城市交通網中的關鍵位置。文獻[15]分析了軌跡數據的運動特征、幾何模式等信息，利用Delauany三角網提取了加油站信息。已有算法采用的方法大致可以分為4類，如表1所示：①基于軌跡聚類，該類方法基本原理是對輸入的原始軌跡數據利用諸如k-means等不同方法進行聚類，然后對聚類得到的道路片段進行融合，進而獲取道路的中心線和交叉路口；②基于增量軌跡合并，該類方法首先假設路網圖為空，然后遍歷所有軌跡，根據規則逐步合并點和邊，最終得到表示路網的一幅圖；③基于道路交叉點連接，該類算法首先探測路網交叉點，然后通過識別合適的路段將交叉點連接形成路網；④基于數字圖像處理算法，該類算法首先將軌跡數據轉化為數字圖像，利用數字圖像處理方法對軌跡圖像進行處理(如濾波去噪、形態學方法等)，然后由處理后的圖像提取骨架道路，最后再優化得到路網。另外，在評價算法自動構建路網的質量方面，構建路網與底圖數據進行疊加后觀察重疊度是常用的定性評價方法，F-score常用來定量比較構建道路的質量，也有學者利用有向Hausdorff距離、Frechet距離等度量來評估所構建路網的拓撲方面質量[16-17]。

表1 基于軌跡數據的道路構建算法分類

以上算法大多針對高精度(0～5 m)、密集采樣(1～5 s)的小數據(一般少于百萬個軌跡點)，而對數據量巨大(數以億計)、粗糙定位(>5 m)、稀疏采樣(>15 s)的實際軌跡數據的處理情況少有研究。另一方面，現實中彎曲道路、立交橋和十字路口等復雜路口需要被描述得更為詳細，而簡單道路(如直線道路)可以用少量幾個點表示，以上算法也未考慮這一因素，導致計算量的增加，也使得道路復雜路段得不到詳細表達。筆者提出了一種顧及道路復雜度的增量路網構建算法，能有效地通過海量粗糙定位數據自動構建路網地圖，并用海量真實軌跡數據進行試驗，驗證了其有效性。

1 定 義

定義1：粗糙軌跡數據，車輛在城市道路移動過程中，被所搭載GNSS接收裝置按時間順序連續記錄的一系列位置原始坐標的集合。本文中，粗糙軌跡數據用集合C表示，其中任意位置點用p=(唯一標識號，時間,經度,緯度)表示。

定義2：規范軌跡，同一車輛行駛過程中連續記錄的原始位置坐標序列經過濾選得到的子集traj={p1,p2,…pi,…,pn}，其中pi為位置點，該子集滿足中軌跡濾選模型設定的系列約束條件。

定義3：道路復雜度，指路網在數量、方向、交疊等方面的復雜程度。通常意義上，一個區域內道路的交叉口越多，立交橋越多，高架橋越多，那么該區域的道路網絡就越復雜。本文通過計算一定區域內各道路方向角的信息熵來描述道路復雜度，其具體計算方法將在下面給出。

定義4：路網地圖。路網地圖為一幅有向圖G=〈V,E〉，V表示道路節點或交叉點，E表示道路，E的方向表示道路的方向，道路的拓撲規則隱含在有向圖中，E的屬性表示道路平均速度和交通流量等信息。

本文提出的路網地圖自動構建方法包含軌跡濾選和路網增量構建兩步：第1步通過構建空間、時間、邏輯約束的規則模型，在消除數據中噪音和冗余的同時，將原始軌跡進行分割，篩選形成規范軌跡集合T；第2步利用信息熵計算軌跡點周圍道路的復雜度以自動調節道路分割參數，不斷將新產生的路段加入到路網，同時，計算道路平均交通流量和速度，遍歷各軌跡的定位點重復以上處理過程，最終得到完整路網。

2 規范軌跡濾選

通常，粗糙軌跡數據存在大量質量問題：①GNSS接收機可能存在故障，產生大量定位異常軌跡；②在高建筑物、樹蔭、隧道、立交橋等區域，受衛星信號的影響，產生大量定位噪聲，也稱為漂移點；③車輛停靠或者特慢速行駛時，在局部區域產生大量軌跡冗余點，增加了數據處理計算量；④其他原因產生時間間隔較長定位點，其連線不能反映真實的道路情況。如圖1所示，按時間順序直接連接出租車行駛產生的原始軌跡點會產生大量不合理的“路徑”，這些不合理路徑在道路的交叉口表現明顯，見圖1(b)。以上問題給數據分析帶來困難，影響路網提取結果的質量[25]，需要對原始軌跡數據進行濾選和分割。

圖1 粗糙的軌跡數據與OpenStreetMap地圖(昆明市人民中路附近區域)Fig.1 Coarse trajectory data vs map from OpenStreetMap (around Kunming People’s Middle Road)

根據經驗和大量試驗分析，一條良好的軌跡應具有以下特征：①軌跡中兩連續定位點的時間間隔Δt應等于設定的采樣點間隔ζ；②兩連續點間的距離Δd應小于某一距離閾值δ0。例如，規定城市高速路上車輛速度小于Vmax_speed，則兩點間間隔一般小于Vmax_speed×Δt；③在數據不冗余情況下，任意兩連續點間距離Δd應大于某距離閾值δ1；④軌跡內任意兩點間距離的最大值dmax應大于某一閾值δ2。本文根據以上經驗知識，提出一種基于規則模型的軌跡濾選方法對粗糙軌跡進行處理，濾選模型構建如下：

(1) 如果Δt≥3ζ，則將從這兩點間將其劃分為兩條不同的軌跡。

(2) 如果Δd≥δ0，則將從這兩點間將其劃分為兩條不同軌跡。

(3) 如果Δd≤δ1，則只保留前一個軌跡點。

(4) 如果dmax≤δ2，將軌跡刪除。

該模型處理粗糙軌跡數據的流程如圖2所示。通過該模型處理后，可以大幅度消除誤差和漂移點，減少數據冗余，最終將粗糙的軌跡數據C組織為規范軌跡集合T={traj1,traj2,…,trajn}，每條規范軌跡中，點方向角由其前后兩軌跡點連線方向代替，首尾點方向由其相鄰點連線方向角代替。

圖2 基于規則模型的軌跡濾選流程Fig.2 Flowchart of trajectory filtering based on rule model

3 增量路網構建

軌跡濾選處理后，得到規范的軌跡集合T，將作為增量路網構建處理的輸入，顧及道路復雜度的增量路網構建思路是：首先初始化代表路網的有向圖G為空，然后遍歷所有軌跡中的定位點，根據所遍歷定位點周圍道路的復雜度，自動計算閾值，根據閾值大小，將定位點插入到有向圖中，或者與有向圖中已構建點進行合并，更新節點之間的連接邊，同時計算有向圖中邊的速度和其他屬性信息，最終得到一幅交通路網圖，方法的流程如圖3所示，下文對流程中的重點進行闡述。

判斷待處理點是否應該與已構建到道路網邊融合。基于在同一條道路上行駛產生的軌跡數據有著相似性這一事實，這里主要考察兩個參數：待處理軌跡點的方向與欲合并邊的方向角差異ΔA；待處理點與擬融合邊的距離Δh，這里取其投影距離。如果待處理點與擬合并邊的方向角小于某一閾值θ，同時其投影點在邊上，投影距離小于某一閾值φ，便將點與邊融合，否則不融合。

p點周圍道路軌跡復雜度計算。在給出軌跡點所處道路環境復雜度計算公式之前，首先約定路段p與路段l的方向距離Da(p,l)，其計算如式(1)所示

Da(p,l)=sin(Ap-Al

(1)

式中，Ap為路段p的方向角；Al為路段l的方向角。從式(1)中容易看出，當兩路段路方向相同或者相反時候，兩者的方向距離為0，當兩路段垂直時，兩者的方向距離達到最大值1。

在任意待處理軌跡點鄰域σ范圍內，路段p方向上信息熵計算如式(2)所示

(2)

(3)

Hσ作為σ鄰域內道路的復雜度，容易證明，當所有路段方向一致或者相反時，Hσ=0，隨著道路復雜度的增加，如道路數量、道路角度的分布差異等增加，Hp,A值遞增，其最大值為log(n)。

圖3 顧及道路復雜度的增量路網構建流程Fig.3 Flowchart of incremental road network construction considering road complexity

設定分割閾值δsplite_dist大小。分割閾值δsplite_dist控制著構建路網中邊的平均長度，即路網的詳細程度。這里基于道路復雜度設定分割閾值δsplite_dist，待處理軌跡點周圍區域σ由其半徑r確定，其取值需綜合道路的寬度和路網密度(一般城市道路取100 m左右)，其計算如式(4)所示

(4)

式中，Lmax為最大分割長度，其值一般不會大于相鄰軌跡點之間的距離。從式中不難看出，當軌跡點方向與已構建道路方向相同或相反，分割閾值為Lmax；當軌跡點與周圍道路較復雜，δsplite_dist值將會越小，已構建道路將會被分割得越細，路網表達將會越詳細。

p點與其臨近點v融合。由于定位誤差和車輛行駛時候的特點不同，軌跡線之間存在較大的差異，單條軌跡線難以準確地表示實際道路的中心線位置，所以需利用后加入軌跡的信息對先前構建的路網進行修正。新加入點與已構建邊進行融合的過程中，可以實現對已有路網的修正。本文采用加權平均位置，權重由該點所包含的已融合點個數確定。同時，更新相關邊的交通流量和速度信息。

路網增量構建的過程示例見圖4，traj1={P1，P2，P3，P4}為輸入的一條待處理的軌跡。G=〈V,E〉={{V1，V2，…,V8},{e1,e2,…,e7}}為已構建路網，其中，P1已與V2合并，P2為待處理軌跡點，其方向為P1P3方向。對P2點的主要的處理過程如下：

(1) 首先查找點P2周圍閾值δ3范圍內的所有已構建道路作為候選邊，如圖4中e2、e3、e6、e7。

(4) 如果①②③條件全部滿足，將P2點與e2融合,并計算d1、d2中較小的值dmin=min(d1,d2),這里dmin=d1。

(5) 如果dmin小于分割閾值δsplite_dist，將P2點與e2中離投影點較近的端點V3合并，并重新計算合并到V3中所有點位置的重心更新V3位置。

(6) 如果dmin大于分割閾值δsplite_dist，用P2點對V2V3進行分割，P2加入到V∈G中，V2P2，P2V3加入到E∈G中,刪除V2V3，并更新相應邊的交通流量和速度屬性。

(7) 判斷P2的前一軌跡點P1(已合并到V2)是否為空(顯然不為空)，且在已構建路網中存在5步內連接到合并點V3的道路，所以不用增加連接路徑。

(8) 更新判斷點P2為前判斷節點prevNode。再循環步驟(1)—(8)， 處理軌跡traj1中剩余軌跡點,直到所有軌跡點處理完畢。讀取其他軌跡，循環以上過程，直到所有軌跡處理完畢。

圖4 路網構建過程Fig.4 Road network construction process

4 試驗分析

4.1 試驗環境與數據

運用Python2.7.15對本文方法進行了實現，試驗硬件環境為一臺Intel Xeon CPU E7-4807@1.87 GHz*2，64 GB內存的服務器。

試驗數據為2016年11月昆明市200輛搭載GPS設備的出租車日常運營行駛所產生，覆蓋昆明市約1000 km2區域。GPS軌跡點數據采樣間隔為15～45 s不等，數據的定位精度為5～30 m不等，全部點數據約為6851萬條，主要包括車輛ID、時間、經度、緯度等字段。考慮到數據的可獲取性，試驗對比數據選用OpenStreetMap地圖數據。

4.2 試驗結果與分析

軌跡濾選結果受采樣間隔ζ，兩連續點間的距離閾值下限δ0，距離間隔閾值上限δ1和出行最小范圍閾值δ2影響，各閾值具體的選擇取決于軌跡數據自身的特點，對試驗數據描述性統計分析,結果見表2。

表2 對原始軌跡數據描述性統計

根據以上統計信息，試驗選擇各閾值ζ=15 s，δ0=5 m，δ1=200 m，δ2=500 m，共耗時2 min 9 s完成試驗，產生約43.67萬條軌跡，每條軌跡線平均包含137個軌跡點。試驗結果顯示，隨著ζ增加，不合格的軌跡增加，隨著ζ減小，軌跡數量增多，且每一條軌跡中包括更多的定位點；隨著δ0減小，每條軌跡中的包含路段長度減小，包含軌跡點量增多；隨著δ1的增加，會產生無效軌跡；隨著δ2增加，更多軌跡點被刪除，導致最終結果不平滑。圖5顯示軌跡濾選的整體結果，圖5(a)為研究區域的OpenStreetMap背景地圖。圖5(b)中，直接將粗糙軌跡數據按照時間順序連接，從圖中觀察到道路網骨架，但其中包括大量雜亂模糊的噪聲。圖5(c)展示經過軌跡濾選處理后的結果,從整體和局部放大的圖可以觀察到大量明顯噪聲數據已經被濾去，經過軌跡濾選后的軌跡能夠更清楚表達道路結構。然而，由于軌跡定位誤差等原因的存在，位于同一條道路的眾多軌跡彼此不能完全重疊，道路的方向和幾何拓撲關系也沒有表現出來，十字路口周圍也有大量雜亂線段，這些問題將在路網構建中得到解決。

在經過規范軌跡濾選處理后，得到規范的軌跡數據，再進行增量路網構建，路網構建的質量受軌跡融合條件參數方向角差異閾值θ、投影距離閾值φ、待處理點環境周邊半徑r、最大分割閾值Lmax的影響。經過大量試驗，發現當θ=30°，φ=50 m，r=100 m，Lmax=1200 m時，本文提出方法能取得較好的試驗結果。表3展示了上述參數取值情況下，經過路網構建得到結果的統計信息和文獻[4]報道方法所得結果比較，包括路網中節點的數量、路段數量、路段的平均長度、整個路網的平均行駛速度信息。從表中可以看出，對于同一區域，本文方法能大量減少構建路網所需的節點數量和路段數量，平均路段長度有所增加，而平均速度變化不大。這是因為通過本文提出的道路復雜度H(σ)，對分割閾值δsplite_dist進行了動態設定，一方面雖然在交叉路口等復雜路段區域增加了節點數量，但增加了復雜路段區域的詳細程度，另一方在直線類型簡單道路中大量減少了節點數量。試驗表現出來總節點數量減少，但路網的質量得到提升。

表3 生成路網地圖統計結果比較

圖6(a)展現了試驗構建的交通路網概況，綠色實線表示道路，黃色箭頭表示道路方向，實線的粗細表示道路上的交通流量大小。結果與OSM地圖數據疊加對比，可以發現生成的路網良好展現了試驗區域內的大部分的路網、路網連通性等路網拓撲信息和道路的行駛規則，在類直線型的簡單道路上節點較少，在拐彎情形等復雜路段使用了較多的節點進行表達。圖6(b)展示了生成路網的與OSM地圖的疊加效果，圖中綠色線段為生成的路網，可以觀察到生成路網與OSM地圖能實現很好重合。

上述試驗結果表明，本文描述基于規則模型的軌跡濾選方法可有效消除原始數據中存在的噪聲，濾選出規范軌跡，極大地提升后續路網構建的質量；引入道路復雜度對分割閾值進行自動調節，能在減少路網整體節點的同時增強所構建路網的質量。另外，該方法也存在部分問題有待進一步解決問題：①某些路段在OSM地圖中存在，在生成的路網中并不存在，一方面是因為軌跡數據的覆蓋度有限，試驗軌跡不能覆蓋所有區域，尤其是機動車禁止行駛的步行道路，另一方面，試驗數據為2016年昆明市軌跡數據，不能反映目前最新的道路狀況；②生成的路網地圖中將立交橋識別為十字路口，這是因為本文將路網建模為平面圖，未來工作中可進一步研究立交橋、十字路口等復雜路網的精確提取；③某些交叉路口周圍仍存在一些雜亂邊，這是由于GNSS定位過程中存在系統誤差，且路網較為復雜。未來工作中可嘗試引入典型交叉路口模型，或者利用模式識別算法訓練交叉路口軌跡點樣本來解決這一問題。

5 結 論

通過粗糙軌跡數據自動構建導航交通路網，可作為傳統實地測繪方法以及從遙感影像提取信息方法的有力補充，在減少導航信息采集成本、縮短導航地圖信息更新時間、減少制圖工作量方面有著重要意義。顧及道路復雜度的增量路網構建方法，由基于規則模型的軌跡濾選和考慮道路復雜度的增量路網構建兩部分組成。試驗結果表明，該軌跡濾選算法能有效消除噪聲，濾選出規整軌跡，基于信息熵提出的路網的復雜度在構建路網時，能根據待處理軌跡點周圍已構建道路的復雜度自動調節合并參數，在路網復雜的區域更為詳盡地提取路網信息，最終自動構建完整道路網的幾何骨架和拓撲信息。此外，該方法在構建路網幾何信息同時，還計算了路網的平均交通流量和平均速度。與類似路網構建算法相比，本文方法能用更少的節點和路段，構建更高質量的路網。未來研究將會致力于提高本方法的運行效率，利用F-score，Hausdorff距離、Fréchet距離等度量方法對所路網的拓撲和幾何屬性進行定量評估，以及結合自動駕駛需求的導航地圖自動構建。

圖5 GNSS車輛軌跡濾選結果Fig.5 Results of GNSS vehicle trajectories filter