吳 濤，向隆剛，龔健雅

1. 中南大學地球科學與信息物理學院，湖南 長沙410083； 2. 武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢430079； 3. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079

?

路網(wǎng)更新的軌跡-地圖匹配方法

吳 濤1，向隆剛2,3，龔健雅2,3

1. 中南大學地球科學與信息物理學院，湖南 長沙410083； 2. 武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢430079； 3. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079

全面準確的路網(wǎng)信息作為智慧城市的重要基礎(chǔ)之一，在城市規(guī)劃、交通管理以及大眾出行等方面具有重要意義和價值。然而，傳統(tǒng)的基于測量的路網(wǎng)數(shù)據(jù)獲取方式往往周期較長，不能及時反映最新的道路信息。近幾年，隨著定位技術(shù)在移動設(shè)備的廣泛運用，國內(nèi)外學者在研究路網(wǎng)信息獲取時逐漸將視野轉(zhuǎn)向移動對象的軌跡數(shù)據(jù)中所蘊含的道路信息。當前，基于移動位置信息的路網(wǎng)生成和更新方法多是直接面向全部軌跡數(shù)據(jù)施加道路提取算法，在處理大規(guī)模軌跡或者大范圍道路時，計算量極大。為此，本文基于軌跡地圖匹配技術(shù)，提出一種采用“檢查→分析→提取→更新”過程的螺旋式路網(wǎng)數(shù)據(jù)更新策略。其主要思想是逐條輸入軌跡，借助HMM地圖匹配發(fā)現(xiàn)已有路網(wǎng)中的問題路段，進而從問題路段周邊局部范圍內(nèi)的軌跡數(shù)據(jù)中提取并更新相關(guān)道路信息。該方法僅在局部范圍內(nèi)利用少量軌跡數(shù)據(jù)來修復(fù)路網(wǎng)，避免了對整個軌跡數(shù)據(jù)集進行計算，從而有效減少了計算量?；贠penStreetMap的武漢市區(qū)路網(wǎng)數(shù)據(jù)以及武漢市出租車軌跡數(shù)據(jù)的試驗表明，本文提出的路網(wǎng)更新方法不僅可行，而且靈活高效。

地圖匹配;問題路段;局部更新

道路網(wǎng)絡(luò)作為一個城市的骨架，是整個城市的“生命線”，是城市社會經(jīng)濟活動、交通運輸賴以進行的物質(zhì)載體。準確的路網(wǎng)信息不但是城市建設(shè)、交通規(guī)劃管理、緊急事件響應(yīng)等基礎(chǔ)建設(shè)的根基，而且為人們?nèi)粘３鲂谢蛐谐桃?guī)劃提供了必要的輔助。我國的城鎮(zhèn)化進程推進了道路的建設(shè)與完善，使路網(wǎng)結(jié)構(gòu)處于快速變化之中，導(dǎo)致了城市路網(wǎng)數(shù)據(jù)現(xiàn)勢性相對滯后[1]。常見的路網(wǎng)信息提取和更新方法，或基于專業(yè)GPS設(shè)備的地表測量[2]，需要專業(yè)的道路測量車輛與數(shù)據(jù)采集人員，信息獲取周期長，后期提取工作量大，且維護費用昂貴；或基于高清遙感影像的圖像處理[3-4]，受限于圖像處理技術(shù)，難以進行自動化作業(yè)，提取效率不高。近年來，伴隨著移動端定位技術(shù)的日趨成熟，國內(nèi)外研究者逐漸開始研究基于日常民用低成本GPS設(shè)備軌跡數(shù)據(jù)的路網(wǎng)信息提取方法，追蹤裝載GPS設(shè)備的大眾交通工具可以方便快捷地收集到覆蓋整個道路網(wǎng)絡(luò)的大眾出行軌跡數(shù)據(jù)，加以處理計算可以快速提取路網(wǎng)信息。

現(xiàn)有的軌跡數(shù)據(jù)路網(wǎng)信息提取方法大致分為基于軌跡數(shù)據(jù)的路網(wǎng)信息重建與基于軌跡數(shù)據(jù)的路網(wǎng)信息改進兩類。前者直接從軌跡數(shù)據(jù)集提取整個路網(wǎng)的幾何特征。比如文獻[5]基于AI聚類技術(shù)結(jié)合“劃窗”算法，將原始軌跡采樣點逐個連接構(gòu)成軌跡線，通過連接多條軌跡線增量繪制整個未知區(qū)域的路網(wǎng)結(jié)構(gòu)；文獻[6—7]對軌跡進行聚類提取道路中心線，并以行進路徑和交叉點最終確定路網(wǎng)結(jié)構(gòu)；文獻[8]提出了基于Delaunay三角網(wǎng)的時空軌跡融合與路網(wǎng)生成方法。后者通過計算軌跡數(shù)據(jù)來改進已有地圖中的道路信息，比如文獻[9—11]基于初始地圖與軌跡數(shù)據(jù)來改進路網(wǎng)中指定道路的中心線。然而，前文中提到的眾多從軌跡數(shù)據(jù)中提取路網(wǎng)信息的方法存在一定的局限性。首先，直接從浮動車軌跡數(shù)據(jù)中提取信息重建整個路網(wǎng)需要處理海量軌跡數(shù)據(jù)，導(dǎo)致巨大的計算資源消耗，尤其是當路網(wǎng)中存在較大的交叉區(qū)域或者重疊區(qū)域時，計算復(fù)雜度更高。其次，目前對于已有路網(wǎng)信息的改進，或通過整體重建路網(wǎng)后進行比對確定更新，計算成本太高；或依賴人工識別后選定區(qū)域更新，無法實現(xiàn)自動化批量處理。

由此，本文提出了一種新的螺旋式路網(wǎng)數(shù)據(jù)更新方法，在“檢查-分析-提取-更新”這一過程中，檢查路網(wǎng)中潛在的問題路段，將參與計算的軌跡數(shù)據(jù)限定在問題路段所屬的局部區(qū)域內(nèi)，從而避免對整個軌跡數(shù)據(jù)集的計算。文章首次將軌跡地圖匹配技術(shù)引入路網(wǎng)數(shù)據(jù)更新中，設(shè)計了基于軌跡-地圖匹配的路網(wǎng)更新框架。結(jié)合路網(wǎng)數(shù)據(jù)和軌跡行為的特點，設(shè)計基于HMM模型的路網(wǎng)檢查方法，以軌跡-路網(wǎng)匹配過程中的斷點來發(fā)現(xiàn)并鎖定路網(wǎng)中潛在問題路段的位置，并對問題路段進行分類分析。在此基礎(chǔ)上，建立問題路段鄰域，針對鄰域內(nèi)問題路段的不同類型，設(shè)計相應(yīng)的路段信息糾正方案，并根據(jù)鄰域局部范圍內(nèi)獲取的相關(guān)軌跡數(shù)據(jù)子集，采用不同的路段信息提取方法，進而探討了局部范圍內(nèi)路網(wǎng)更新標準，最終結(jié)合原有路網(wǎng)基線完成對現(xiàn)有路段信息的改進和更新。該方法不再直接將算法施加于海量的軌跡數(shù)據(jù)集，只針對原有路網(wǎng)中問題路段所屬小范圍鄰域內(nèi)的部分軌跡數(shù)據(jù)子集進行計算，減少了計算量的同時，也減輕了整個路網(wǎng)數(shù)據(jù)更新過程對人工干預(yù)的依賴，大大提高了效率。

1 基于軌跡地圖匹配的路網(wǎng)更新策略

在軌跡地圖匹配過程中，由于路網(wǎng)數(shù)據(jù)本身存在問題(比如路段缺失)將導(dǎo)致匹配發(fā)生中斷，即軌跡地圖匹配的中斷能夠直接反映路網(wǎng)數(shù)據(jù)中存在的問題?；谶@一認識，本文設(shè)計了一種螺旋向前推進的路網(wǎng)更新策略，采用“檢查→分析→提取→更新”過程進行螺旋式迭代(如圖1(a)所示)。該螺旋式過程使得系統(tǒng)可以把問題分散到各個軌跡所經(jīng)過的局部范圍內(nèi)，沿著螺線進行若干次迭代完成路網(wǎng)更新，避免將大量計算資源消耗在處理整個軌跡數(shù)據(jù)集上。螺旋式更新框架的另一個優(yōu)勢在于其執(zhí)行上的靈活性，既可以對軌跡數(shù)據(jù)集所覆蓋的路網(wǎng)區(qū)域進行多次螺旋式迭代檢測更新，也可以指定某一條軌跡對特定路線進行檢測更新。在詳細介紹路網(wǎng)更新框架之前，首先給出相關(guān)的基本概念。

定義1：路網(wǎng)，G=(N,L)，是由邊(L)和節(jié)點(N)兩類NDM基本元素的集合組織表達的道路網(wǎng)絡(luò)(如圖1(b)所示)。其中，N=(ni|i=1,2,…,K)是路網(wǎng)中路段節(jié)點的集合，L=(lj|j=1,2,…,H)是路段在路網(wǎng)中所對應(yīng)弧段的集合。

定義2：軌跡，T=(Pi|i=1,2,…,M)，為多個GPS采樣點Pi組成的序列。其中，Pi包含移動對象在該采樣點的位置和時間信息。

路網(wǎng)表現(xiàn)在二維空間上是由多個路段相互連接、交叉或者并行所組成的一個整體(圖1(b))，軌跡數(shù)據(jù)是移動對象運動過程的空間位置采樣點序列。軌跡地圖匹配則是將軌跡采樣點序列轉(zhuǎn)換為具有空間語義信息的路段序列。當路網(wǎng)G中的某位置缺少路段的信息，或路段的信息有錯誤時，則認為該路網(wǎng)的這一位置存在問題路段。例如，實際路網(wǎng)中的路段a和b之間有連通關(guān)系(即存在節(jié)點)，如果相關(guān)路網(wǎng)數(shù)據(jù)中沒有記錄a或者b(缺少路段的信息)，或者沒有記錄a與b之間的連通關(guān)系(路段的信息有錯誤)，則a(或者b)被視為問題路段，軌跡地圖匹配在a與b之間發(fā)生中斷。

整個更新框架始于從OSM獲取基于“節(jié)點-邊”通用網(wǎng)絡(luò)模型NDM[9](network data model)組織的原始路網(wǎng)數(shù)據(jù)G，隨后進入螺旋式更新過程(如圖1(c)所示)螺旋中每輪迭代，讀入單條軌跡數(shù)據(jù)T檢查地圖匹配中斷，如未發(fā)生中斷則結(jié)束本輪操作，從軌跡數(shù)據(jù)集中讀入下一條軌跡開始新一輪迭代；否則，針對各中斷所在位置分別建立問題路段鄰域，分析問題路段類型，進而從軌跡數(shù)據(jù)中提取路段幾何信息等對路網(wǎng)進行更新，然后等待進入下輪迭代。如果后續(xù)未有待匹配軌跡讀入，則視為整個螺旋過程結(jié)束。

圖1 路網(wǎng)更新框架流程Fig.1 Flowchart of road network renewal

2 基于軌跡-地圖匹配的路網(wǎng)檢測

2.1 基于HMM模型的地圖匹配

本節(jié)重點討論基于HMM模型的軌跡-地圖匹配技術(shù)的路網(wǎng)檢查方法。軌跡-地圖匹配方法大致可分為4種類型[12]：基于幾何特征的地圖匹配[13]、基于拓撲的地圖匹配[14]、基于概率的地圖匹配[15]以及基于高階技術(shù)的地圖匹配(基于高階技術(shù)的地圖匹配，泛指那些使用更精致概念(morerefinedconcepts)的地圖匹配方法，例如卡爾曼濾波[16]、隱馬爾科模型[17-22]等)。

本文選取一階HMM(隱馬爾科夫模型)模擬軌跡在路網(wǎng)中的移動，將軌跡在路網(wǎng)中的移動定義為在路段兩個節(jié)點之間移動的馬爾科夫過程，以采樣點到節(jié)點的大圓距離(greatcircledistance)為判定依據(jù)，提取與采樣點最鄰近的n個節(jié)點為潛在匹配候選路段節(jié)點?；贖MM的地圖匹配過程中，問題路段會導(dǎo)致單次匹配的馬爾科夫過程不連續(xù)，進而造成匹配路徑中的斷點，最終引發(fā)的匹配中斷。

如圖2所示，沿觀測值序列方向，取軌跡采樣點各自最鄰近的n個節(jié)點建立HMM模型進行地圖匹配。整個匹配過程分別有兩個斷點導(dǎo)致中斷：第一次在采樣點為P4到P7，軌跡經(jīng)過了一條未被路網(wǎng)數(shù)據(jù)記錄的道路，導(dǎo)致P5和P6這兩點到候選路段節(jié)點的觀測概率極低；第二次在采樣點P9到P10，軌跡路徑所對應(yīng)道路在路網(wǎng)數(shù)據(jù)中間存在拓撲錯誤，導(dǎo)致P9對應(yīng)路段對其后可能路段的轉(zhuǎn)移概率為0或非常小。通常這種中斷會影響地圖匹配輸出結(jié)果的質(zhì)量，因此會在匹配過程中被當成噪聲或者異常值通過算法處理后選擇性跳過(這些也是造成地圖匹配結(jié)果誤差的原因)，然而本文則反向關(guān)注到了匹配中斷與問題路段的相關(guān)性，即這些匹配中斷的背后所反映出來的問題很大程度上就是路網(wǎng)數(shù)據(jù)的問題。由此，本文接下來將利用這一點，以匹配過程中斷來定位路網(wǎng)中問題路段所在的位置。

圖2 基于HMM地圖匹配的中斷Fig.2 Breaks of map-matching based on HMM

2.2 問題路段分析與檢查

基于HMM的地圖匹配過程使得對路網(wǎng)數(shù)據(jù)的檢查變成了可能，本節(jié)將對可能探測到的問題路段進行分析，以便在后續(xù)處理中能針對不同特點的問題路段采用相應(yīng)的處理方法。結(jié)合路網(wǎng)數(shù)據(jù)自身特點，可將問題路段劃分為兩大類：

2.2.1 路段信息錯誤

通過大眾采集數(shù)據(jù)在線協(xié)同繪制的路網(wǎng)數(shù)據(jù)(如本文中所使用的OpenStreeMap數(shù)據(jù))往往會因為上傳用戶采集數(shù)據(jù)的質(zhì)量而造成種種問題，常見的是路段間的拓撲錯誤，即本應(yīng)相互連接的路段沒有閉合等。

2.2.2 路段信息缺失

新道路信息的采集相對于城市建設(shè)的滯后往往會造成路網(wǎng)數(shù)據(jù)中道路或部分路段的缺失。例如，移動對象經(jīng)過了一條新建的路段或者城市中某一區(qū)塊(如小區(qū)或者公園)，而現(xiàn)有路網(wǎng)數(shù)據(jù)沒有及時更新該路段的信息。

給定一條軌跡T與路網(wǎng)G，當且僅當軌跡T上單個或者連續(xù)多個采樣點位置與路網(wǎng)匹配過程的中斷滿足以下任一條件時，則稱該中斷所在位置存在問題路段：

(1) 軌跡采樣點到所有道路的觀測概率都非常小或為0(即采樣點到最近路段的距離遠大于某一距離閾值)。

(2) 軌跡上連續(xù)兩個采樣點對應(yīng)的匹配路段間轉(zhuǎn)移概率都非常小或為0。

(3) 軌跡上連續(xù)采樣的所匹配路段距離與采樣間隔時間的比值(即軌跡匹配后的平均移動速度)超過路段本身實際速度限制(或預(yù)設(shè)的某一速度閾值)。

如果問題路段鄰近區(qū)域內(nèi)軌跡采樣點與路網(wǎng)信息同時滿足以下條件時，判定為路段信息錯誤(其余判定為路段信息缺失):

(1) 最大觀測概率的節(jié)點之間狀態(tài)轉(zhuǎn)移概率非常小。

(2) 最大觀測概率的節(jié)點間的大圓距離遠小于其路徑距離。

(3) 觀測點間的實際均速度遠低于完成對應(yīng)節(jié)點間轉(zhuǎn)移所需要的平均速度。

基于以上概念，本文設(shè)計的問題路段檢測算法，關(guān)鍵步驟如圖3所示。從軌跡起點開始檢查初始概率(initialprobability)，如果滿足閾值設(shè)定的條件則繼續(xù)向后檢查；否則將其標記為中斷點，然后以下一采樣點為起點，重新計算初始概率，繼續(xù)檢查過程。如果檢查未到軌跡終點，發(fā)生上述任意一種情況都會視為當前匹配檢查的一個中斷，即主動終止對當前采樣點位置的檢查，以下一個采樣點為起點，開始新一輪檢查。需要注意的是，軌跡本身存在較大噪聲時也可能造成匹配中斷，因此需要預(yù)先對軌跡數(shù)據(jù)本身進行篩選去噪。

圖3 問題路段檢查算法Fig.3 The algorithm of find breaks

3 基于軌跡數(shù)據(jù)的局部-地圖匹配的路網(wǎng)檢測

本節(jié)首先基于問題路段建立路段鄰域，進而判定問題路段類型，然后依據(jù)所發(fā)現(xiàn)問題路段的類型特點有針對性地設(shè)計處理方法，最終完成對路網(wǎng)信息的更新。針對路段信息錯誤，依據(jù)鄰域內(nèi)軌跡數(shù)據(jù)與非問題路段進行修正；針對路段信息缺失，依據(jù)問題路段鄰域內(nèi)軌跡數(shù)據(jù)分布情況的不同，文中采用PAM聚類的道路特征點提取或基于緩沖區(qū)的道路骨架線提取兩種方法從GPS軌跡數(shù)據(jù)中提取路段幾何信息。

3.1 問題路段分析處理

如圖4所示，本文設(shè)定以發(fā)生匹配中斷的軌跡采樣點(稱之為分裂點，breakpoint)為中心，以其沿軌跡上前后兩個最鄰近的有效匹配采樣點(pre-breakpoint與post-breakpoint)之間的最大距離為半徑建立的圓形區(qū)域，設(shè)為問題路段鄰域。

圖4 問題路段鄰域Fig.4 The neighborhood of a condemned road segment

依照先易后難的原則，優(yōu)先對路段信息錯誤進行處理，檢查問題路段鄰域內(nèi)原有路段之間的連通關(guān)系，判定breakpoint前后有效匹配的采樣點所對應(yīng)的最大觀測概率節(jié)點間的最短距離，拉伸合并已有路段使之符合最短距離，最后更新交疊信息。針對路段信息缺失，設(shè)計從問題路段鄰域內(nèi)的多條子軌跡中提取缺失路段的幾何信息進行修補，從而避免單條軌跡稀疏可能導(dǎo)致的信息丟失。顯然，道路提取的方法受制于軌跡數(shù)據(jù)本身的采樣情況，根據(jù)問題路段鄰域內(nèi)軌跡數(shù)據(jù)分布情況的不同分別采用相應(yīng)的提取方法。從數(shù)據(jù)庫中提取落入問題路段鄰域內(nèi)的子軌跡數(shù)據(jù)，以之前用于路網(wǎng)檢查的軌跡采樣點為中心，以平均道路寬度為半徑，計算其周邊范圍內(nèi)所包含的軌跡點數(shù)量，即子軌跡采樣點密度。如果采樣點密度不滿足密度閾值minPts，則采取緩沖區(qū)骨架提取方法，否則默認使用PAM聚類方法。前者更適合處理多條內(nèi)子軌跡路徑為網(wǎng)狀結(jié)構(gòu)(即問題鄰域內(nèi)與之前用于檢查的軌跡路徑相似的子軌跡較少)；后者處理多條內(nèi)子軌跡路徑單一的情況時(即問題鄰域內(nèi)其他子軌跡與之前用于檢查的軌跡路徑相似)，效果比較理想。

3.2 基于PAM聚類的路段信息提取

基于聚類的道路信息提取是通過聚類方法將沿道路分布的軌跡采樣點按一定的約束條件聚合成具有相似行為的簇，提取代表各個簇的聚類點作為反映道路幾何特征的關(guān)鍵點擬合道路中心線。在研究了已有的眾多聚類方法之后，筆者認為PAM(partitioningaroundmedoids，k-medoids)聚類方法比較適用于局部范圍內(nèi)的少量軌跡數(shù)據(jù)的道路提取計算。PAM聚類是對k-means算法的改進，它先對n個對象給出k個類簇劃分，然后通過反復(fù)計算類簇內(nèi)除中心點之外的各點到其他所有點的聚類最小值來找出更合適的中心點，對于較小的數(shù)據(jù)集非常有效。該方法不再使用k-means的幾何中心點，轉(zhuǎn)而在簇內(nèi)的真實采樣點中尋找中心點，最小化了簇內(nèi)所有采樣點之間的差值，從而能較好地排除異常值對于分簇結(jié)構(gòu)的影響[24]，即對于軌跡采樣點的噪聲和異常值不敏感。結(jié)合這些特點，本文選定歐式距離判定聚類參數(shù)，對問題路段鄰域范圍內(nèi)的軌跡數(shù)據(jù)進行PAM聚類，提取問題路段信息。

基于軌跡點PAM聚類的局部道路信息提取具體分為以下3個步驟：

(1) 確定參與PAM聚類的軌跡點數(shù)n，計算聚類點的輪廓(silhouette)[22]確定合適的聚類數(shù)k。

(2) 以任意k個軌跡點為中心開始，與其他n-k個軌跡點進行迭代計算，判定參加聚類行為的邊界，以及替換中心點。

(3) 遍歷所有聚類點，基于相鄰間聚類點的轉(zhuǎn)向角θ與距離D，設(shè)定閾值轉(zhuǎn)角與距離閾值篩選結(jié)果，提取道路中心線。

3.3 基于緩沖區(qū)骨架的路段信息提取

基于軌跡線緩沖區(qū)提取骨架的方法通過融合問題路段鄰域內(nèi)多條軌跡數(shù)據(jù)的軌跡線所生成緩沖區(qū)，從中提取融合后的緩沖區(qū)的骨架線作為道路中心線。緩沖區(qū)的骨架線與緩沖區(qū)多邊形面本身保持一致的連通性和拓撲結(jié)構(gòu)，可以在一定程度上反映道路的幾何特征[25]。目前已有多種多邊形的骨架線的提取方法較為成熟，考慮到軌跡數(shù)據(jù)的特點，以及算法本身的執(zhí)行效率，本文選取簡單易行的水平(或垂直)切割線中點來提取軌跡緩沖區(qū)的骨架線，依據(jù)軌跡緩沖區(qū)的形狀可以大致確定切割線方向，在此基礎(chǔ)上求取每條切割線與緩沖區(qū)邊界的交點，最后計算每組交點的中心點，將其連接形成該緩沖區(qū)的骨架線。

局部道路骨架提取方法具體分為以下3個步驟：

(1) 將軌跡采樣點數(shù)據(jù)分別依照各自的時間順序連接形成多條軌跡線。

(2) 設(shè)置緩沖區(qū)半徑，為每條軌跡線建立緩沖區(qū)，將生成的多個緩沖區(qū)融合成一個緩沖區(qū)。

(3) 判別緩沖區(qū)水平和垂直方向的投影，以較短的投影方向作為切割線方向，等間距切割緩沖區(qū)，提取中點連接線作為道路中心線。

3.4 局部路網(wǎng)數(shù)據(jù)更新

前面已經(jīng)從軌跡數(shù)據(jù)中提取了路網(wǎng)中缺失道路的幾何信息，需要將新生成的路段數(shù)據(jù)添加到原路網(wǎng)中，并對原有路網(wǎng)中相應(yīng)區(qū)域的道路信息的拓撲關(guān)系進行更新。兩步操作處理路段信息錯誤和路段缺失的相關(guān)數(shù)據(jù)更新：①處理不閉合路段信息；②更新交疊信息。

3.4.1 更新交疊信息

檢測新增路段與其周邊領(lǐng)域內(nèi)原有路段之間的連通關(guān)系，如果存在gap(如圖5(a)中虛線圓標出區(qū)域)，則根據(jù)閾值(本文以道路寬度或者兩倍道路寬度作為閾值)判定新增路段端點與原有路段的最短距離，將滿足閾值條件的端點沿著最短距離路徑拉伸至已有路段。

3.4.2 處理不閉合路段信息

新生成的路段數(shù)據(jù)會改變原路網(wǎng)數(shù)據(jù)中的拓撲關(guān)系，如圖5(b)所示，在新增路段與原有路段之間形成了新的交疊關(guān)系，需要對路網(wǎng)中的相關(guān)路段重新分割，生成新的路網(wǎng)節(jié)點與之相互連接。

圖5 局部路網(wǎng)數(shù)據(jù)更新Fig.5 Renewal of local road network

4 試驗示例

4.1 試驗環(huán)境與真實數(shù)據(jù)

本文選擇64位Windows8.1操作系統(tǒng)作為試驗平臺，以VisualStudio2012(64位版)為開發(fā)環(huán)境，基于ArcGIS10.2提供的路網(wǎng)數(shù)據(jù)的處理基礎(chǔ)工具，讀取GPS軌跡，由地圖匹配獲取路段缺失位置，對缺失區(qū)域進行局部路網(wǎng)信息更新，并將最終結(jié)果顯示在電子地圖上。試驗所用PC機的硬件環(huán)境為：Inteli7四核處理器、8GDDR3內(nèi)存、NVIDIAQuadro600顯卡。

本文從已有的LBSN(location-basedsocialnetwork)中選取OSM(openstreetmap)作為數(shù)據(jù)源，獲取武漢市城區(qū)的路網(wǎng)數(shù)據(jù)，主要采用的軌跡數(shù)據(jù)包括武漢市100輛出租車軌跡輔以部分自行采集的軌跡。所用出租車軌跡數(shù)據(jù)的采樣周期為30～60s，行進過程中有效GPS衛(wèi)星連接數(shù)在3～6之間。所有原始軌跡數(shù)據(jù)首先經(jīng)過預(yù)處理階段，以有效衛(wèi)星、水平精度、距離、速度等閾值進行篩選。經(jīng)過預(yù)處理之后，有17.3%的軌跡采樣點被移除(其中包括異常點和冗余點等)。

4.2 試驗結(jié)果與分析

試驗選取8條軌跡數(shù)據(jù)對路網(wǎng)數(shù)據(jù)進行路段信息缺失檢測，共發(fā)現(xiàn)了12處問題路段并建立對應(yīng)鄰域(如圖6(b)所示)，提取局部范圍內(nèi)的20條軌跡進行路段信息提取后生成了圖6(c)中所示的新增路段。

圖6 路網(wǎng)數(shù)據(jù)更新Fig.6 Renewal of road network

分別依據(jù)鄰域內(nèi)軌跡數(shù)據(jù)的分布情況，選用基于PAM聚類方法(聚類后軌跡提取率約為30%)與緩沖區(qū)骨架線方法，提取反映該區(qū)域內(nèi)路段幾何信息的軌跡聚類點。每提取完一個問題路段鄰域的道路幾何信息，更新程序就增量處理一次路網(wǎng)數(shù)據(jù)更新，依據(jù)上文介紹的兩種不同情況，在更新路網(wǎng)數(shù)據(jù)時，分別對生成路段端點以及交點處進行了處理。根據(jù)試驗中用到的車載GPS的數(shù)據(jù)采集精度以及道路寬度，本文選定的距離閾值取武漢市除大道以外的主、次干道平均寬度2倍值，即30m。

圖6(d)中將更新后的路網(wǎng)數(shù)據(jù)與遙感影像進行比對，可以發(fā)現(xiàn)自軌跡數(shù)據(jù)提取的新增道路結(jié)構(gòu)與實際路網(wǎng)結(jié)構(gòu)基本一致，僅在個別軌跡數(shù)據(jù)極其稀疏的路段出現(xiàn)較明顯的偏差，仍存在有處于問題路段鄰域內(nèi)的路段沒有被提取，這是因為試驗中所收集到的軌跡數(shù)據(jù)沒有覆蓋這些路段。試驗也從定量的角度分析計算了更新后路段與路網(wǎng)基線相應(yīng)區(qū)域路段之間的幾何完成度與拓撲完成度。

幾何完成度=新生成路段中匹配路段長度/新生成路段總長度

拓撲完成度=新生成交點中匹配的個數(shù)/新生成交點總個數(shù)

本文設(shè)定新生路段的某一段與基線路段間的最大投影距離小于閾值(本文選10m)，且方位角最大偏差在30°以內(nèi)，則認定新路段中的該段與基線匹配；新生交點與路段基線交點間距離小于閾值(本文選3m)，則認定新交點與基線匹配。12個問題路段鄰域中更新后的路段相較于路網(wǎng)基線，平均幾何完成度是78.4%，平均拓撲完成度是63.3%。平均拓撲完成度相對較低，是因為本文在處理不閉合情況時，將滿足閾值條件的不閉合端點沿最短路徑投影拉伸至已有路徑，而實際情況下，可能該段并不是沿最短路徑延伸的。后續(xù)可以通過改進不閉合的處理方法來提高拓撲完成度。其次，某些新路段內(nèi)部的交點由于軌跡數(shù)據(jù)中在該鄰域內(nèi)運動的軌跡稀少，極個別路段上只存在1輛車的采樣數(shù)據(jù)，且受周邊高層建筑影響，軌跡數(shù)據(jù)質(zhì)量不高，從而影響更新路段質(zhì)量。

5 結(jié) 論

本文提出了一種基于軌跡地圖匹配的路網(wǎng)數(shù)據(jù)更新方法。該方法以螺旋式過程推進，每次迭代通過軌跡地圖匹配技術(shù)，快速探測到路網(wǎng)數(shù)據(jù)中存在的問題路段，進而有的放矢、有針性地建立問題路段鄰域，提取軌跡數(shù)據(jù)中的路段幾何信息，完成路網(wǎng)數(shù)據(jù)更新。更新過程以基于HMM軌跡地圖匹配方法檢測問題路網(wǎng)，以落入問題路段鄰域內(nèi)的軌跡數(shù)據(jù)為源，根據(jù)軌跡數(shù)據(jù)覆蓋特點，分別采用PAM聚類和緩沖區(qū)骨架線兩類方法，從軌跡數(shù)據(jù)中提取局部范圍內(nèi)的路段幾何信息，進而依據(jù)路段的拓撲特征開始討論，最終完成對原有路網(wǎng)數(shù)據(jù)的更新。文中提出的基于地圖匹配的路網(wǎng)數(shù)據(jù)更新方法相對于其他已有路網(wǎng)數(shù)據(jù)更新應(yīng)用，具有以下4個特點：

(1) 針對整個路網(wǎng)的更新是一個螺旋推進的迭代過程，每次的更新都建立在前一次的基礎(chǔ)上，不斷改進原有路網(wǎng)數(shù)據(jù)質(zhì)量。

(2) 以軌跡的地圖匹配過程作為探測手段，能迅速查找并鎖定路網(wǎng)中存在的問題路段并記錄其位置。

(3) 軌跡數(shù)據(jù)對于路網(wǎng)數(shù)據(jù)而言，所提取的路段幾何信息僅在問題路段處有意義，在此基礎(chǔ)上建立問題路段鄰域，限定路段信息提取區(qū)域范圍，以此最小化參與計算的軌跡數(shù)據(jù)，從而有效減少了路段提取的計算量。

(4) 在問題路段鄰域的基礎(chǔ)上，靈活選取PAM聚類和緩沖區(qū)骨架線兩種不同的提取方法，增強了對于軌跡數(shù)據(jù)的實際覆蓋情況的適應(yīng)性。

本文研究重心在于設(shè)計并驗證文中提出的螺旋式路網(wǎng)更新策略，并未對研究道路信息提取算法進行優(yōu)化，計算結(jié)果在一定程度上受限于軌跡本身精度，但仍可作為路網(wǎng)研究者以及實測工作人員快速發(fā)現(xiàn)問題路段，進而提取道路信息的重要輔助。后續(xù)的研究工作將在此更新策略的基礎(chǔ)上，進一步探究基于軌跡數(shù)據(jù)的道路信息提取算法，并考慮基于本文提出的方法研究個性化局部路網(wǎng)數(shù)據(jù)生成和更新方法。

[1] EKPENYONG F, PALMER-BROWN D, BRIMICOMBE A. Extracting Road Information from Recorded GPS Data Using Snap-drift Neural Network[J]. Neurocomputing, 2009, 73(1-3): 24-36.

[2] CAO Lili, KRUMM J. From GPS Traces to a Routable Road Map[C]∥Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, Washington: ACM, 2009: 3-12.

[3] HU Jiuxiang, RAZDAN A, FEMIANI J C, et al. Road Network Extraction and Intersection Detection from Aerial Images by Tracking Road Footprints[J]. IEEE Transactions on Geoscience and Remote Sensing, 2007, 45(12): 4144-4157.

[4] DAL POZ A P, ZANIN R B, DO VALE G M. Automated Extraction of Road Network from Medium-and High-Resolution Images[J]. Pattern Recognition and Image Analysis, 2006, 16(2): 239-248.

[5] BRüNTRUP R, EDELKAMP S, JABBAR S, et al. Incremental Map Generation with GPS Traces[C]∥Proceedings of 2005 IEEE Conference on Intelligent Transportation Systems. Vienna: IEEE, 2005: 574-579.

[6] SCHROEDL S, WAGSTAFF K, ROGERS S, et al. Mining GPS Traces for Map Refinement[J]. Data Mining and Knowledge Discovery, 2004, 9(1): 59-87.

[7] EDELKAMP S, SCHR?DL S. Route Planning and Map Inference with Global Positioning Traces[M]∥KLEIN R, SIX H W, WEGNER L. Computer Science in Perspective. Berlin Heidelberg: Springer, 2003: 128-151.

[8] 唐爐亮, 劉章, 楊雪, 等. 符合認知規(guī)律的時空軌跡融合與路網(wǎng)生成方法[J]. 測繪學報. 2015, 44(11): 1271-1276. DOI: 10.11947/j.AGCS.2015.20140591. TANG Luliang, LIU Zhang, YANG Xue, et al. A Method of Spatio-temporal Trajectory Fusion and Road Network Generation Based on Cognitive Law[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(11): 1271-1276. DOI: 10.11947/j.AGCS.2015.20140591.

[9] ROGERS S, LANGLEY P, WILSON C. Mining GPS Data to Augment Road Models[C]∥Proceedings of the fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, California: ACM, 1999: 104-113.

[10] GUO Tao, IWAMURA K, KOGA M. Towards High Accuracy Road Maps Generation from Massive GPS Traces Data[C]∥Proceedings of 2007 IEEE International Geoscience and Remote Sensing Symposium. Barcelona: IEEE, 2007: 667-670.

[11] KASEMSUPPAKORN P, KARIMI H A. A Pedestrian Network Construction Algorithm Based on Multiple GPS Traces[J]. Transportation Research Part C: Emerging Technologies, 2013, 26: 285-300.

[12] MURRAY C. Oracle Spatial and Graph Topology Data Model and Network Data Model Graph Developer’s Guide, 12c Release 1 (12.1)[M]. 2013: 26-27.

[13] Wikipedia. Map Matching[EB/OL]. [2015-04-21]. http:∥en.wikipedia.org/wiki/Map_matching.

[14] JAWAD A, KERSTING K. Kernelized Map Matching for Noisy Trajectories[J]. Sig Spatial, 2010: 454-457.

[15] BERNSTEIN D, KORNHAUSER A. An Introduction to Map-matching for Personal Navigation Assistants[EB/OL]. [2002-06-19]. http:∥www.njtude.org/reports/mapmatchintro.pdf.

[16] KAPLAN E D, HEGARTY C J. Understanding GPS: Principles and Applications[M]. Boston: Artech House, 2006.

[17] OCHIENG W Y, QUDDUS M A, NOLAND R B. Map-matching in Complex Urban Road Networks[J]. Brazilian Journal of Cartography, 2004, 55(2): 1-14.

[18] YANG Dakai, CAI Baigen, YUAN Yifang. An Improved Map-matching Algorithm Used in Vehicle Navigation System[C]∥Proceedings of 2003 IEEE Intelligent Transportation Systems. IEEE, 2003, 2: 1246-1250.

[19] RAYMOND R, MORIMURA T, OSOGAMI T, et al. Map Matching with Hidden Markov Model on Sampled Road Network[C]∥Proceedings of the 21st International Conference on Pattern Recognition. Tsukuba: IEEE, 2012: 2242-2245.

[20] LOU Yin, ZHANG Chengyang, ZHENG Yu, et al. Map-matching for Low-sampling-rate GPS Trajectories[C]∥Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, Washington: ACM, 2009: 352-361.

[21] GOH C Y, DAUWELS J, MITROVIC N, et al. Online Map-matching Based on Hidden Markov Model for Real-time Traffic Sensing Applications[C]∥Proceedings of the 15th International IEEE Conference on Intelligent Transportation Systems. Anchorage: IEEE, 2012: 776-781.

[22] KAUFMAN L, ROUSSEEUW P J. Clustering by Means of Medoids[M]∥DODGE Y. Statistical Data Analysis Based on the L1-Norm and Related Methods. Berlin Heidelberg: Springer, 1987: 405-416.

[23] LI Yang, HUANG Qixing, KERBER M, et al. Large-scale Joint Map Matching of GPS Traces[C]∥Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Orlando, Florida: ACM, 2013: 214-223.

[24] KAUFMAN L, ROUSSEEUW P J. Finding Groups in Data: An Introduction to Cluster Analysis[M]. Hoboken: John Wiley & Sons, 1990: 68-123.

[25] 杜世宏, 杜道生, 樊紅, 等. 基于柵格數(shù)據(jù)提取主骨架線的新算法[J]. 武漢測繪科技大學學報, 2000, 25(5): 432-436. DU Shihong, DU Daosheng, FAN Hong, et al. A New Raster-based Algorithm for Extracting Main Skeleton Line of Polygon[J]. Journal of Wuhan Technical University of Surveying and Mapping, 2000, 25(5): 432-436.

(責任編輯：陳品馨)

測繪地理信息與導(dǎo)航高端論壇——《測繪學報》創(chuàng)刊60周年學術(shù)研討會通知(第一號)

時間：2017年10月21日 地點：深圳

當前，新一輪科技創(chuàng)新和產(chǎn)業(yè)發(fā)展正在深度融合，以互聯(lián)網(wǎng)+為代表的信息技術(shù)飛速發(fā)展，泛在測繪與位置服務(wù)的發(fā)展已經(jīng)進入大數(shù)據(jù)時代，智能、快捷服務(wù)已經(jīng)滲透到我國各個行業(yè)，測繪地理信息行業(yè)資本融合勢頭迅猛。國家測繪地理信息局也在《測繪地理信息“十三五”規(guī)劃》中，確立了新型基礎(chǔ)測繪、地理國情監(jiān)測、應(yīng)急測繪、航空航天遙感測繪、全球地理信息資源開發(fā)“五大業(yè)務(wù)”，形成了公益性保障與地理信息產(chǎn)業(yè)市場化服務(wù)協(xié)同發(fā)展和深度融合的工作布局?！稖y繪學報》長期致力于推動測繪地理信息的基礎(chǔ)理論與技術(shù)應(yīng)用發(fā)展，為全國測繪地理信息行業(yè)的科研機構(gòu)、高等院校、生產(chǎn)單位等提供學術(shù)交流與合作的平臺。為進一步促進新理論、新技術(shù)、新方法、新思想的交流，總結(jié)和發(fā)展近年來我國測繪地理信息行業(yè)的最新成果，《測繪學報》編委會定于2017年10月21日在深圳舉辦“測繪地理信息與導(dǎo)航高端論壇——《測繪學報》創(chuàng)刊60周年學術(shù)研討會”，具體事宜通知如下。

一、會議主題

泛在測繪與智能服務(wù)

二、會議時間與地點

會議時間：2017年10月21日

報到時間：2017年10月20日全天

地 點：廣東省深圳市

三、組織機構(gòu)

主辦單位： 中國測繪地理信息學會《測繪學報》 編委會

中國地圖出版集團

深圳大學

深圳市測繪地理信息學會

協(xié)辦單位： 中國測繪科學研究院 測繪遙感信息工程國家重點實驗室 武漢大學測繪學院 武漢大學遙感信息工程學院 武漢大學資源與環(huán)境科學學院 同濟大學測繪與地理信息學院 中國科學院測量與地球物理研究所 西安測繪研究所 中南大學地球科學與信息物理學院 中國礦業(yè)大學環(huán)境與測繪學院 信息工程大學地理空間信息學院 信息工程大學導(dǎo)航與空天目標工程學院 長安大學地質(zhì)工程與測繪學院 海軍工程大學導(dǎo)航工程系 海軍大連艦艇學院海洋測繪系 深圳市數(shù)字城市工程研究中心

承辦單位： 《測繪學報》編輯部 深圳大學智慧城市研究院 深圳大學空間信息智能感知與服務(wù)深圳市重點實驗室

深圳大學海岸帶地理環(huán)境監(jiān)測國家測繪地理信息局重點實驗室

媒體支持： 中國測繪報 武漢大學學報·信息科學版 測繪通報 泰伯網(wǎng) 慧天地 中國測繪新聞網(wǎng) 測繪科技信息網(wǎng) GeoTalks 測繪之家

四、會議日程安排

時間上午下午10月20日(周五)論壇參會人員全天報到10月21日(周六)開幕式,院士報告分論壇

五、會務(wù)相關(guān)事項

會議專用郵箱：agcs2017@163.com

會議QQ群：496372706

會議聯(lián)系人：宋啟凡 電話：010—68531322

注：會務(wù)注冊、參會費用、會議具體地點、住宿安排等具體事宜，將在后續(xù)通知中發(fā)布。

Renewal of Road Networks Using Map-matching Technique of Trajectories

WU Tao1,XIANG Longgang2,3,GONG Jianya2,3

1. School of Geosciences and Info-physics,Central South University,Changsha 410083, China； 2. State Key Laboratory of Information Engineering in Surveying Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China； 3. Collaborative Innovation Center of Geospatial Technology, Wuhan 430079, China

The road network with complete and accurate information, as one of the key foundations of Smart City, bears significance in fields like urban planning, traffic managing and public traveling, et al. However, long manufacturing period of road network data, based on traditional surveying methods, often leaves it in an inconsistent state with the latest situation. Recently, positioning techniques ubiquitously used in mobile devices has been gradually coming into focus for domestic and overseas scholars. Currently, most of approaches, generating or updating road networks from mobile location information, are to compute with GPS trajectory data directly by various algorithms, which lead to expensive consumption of computational resources in case of mass GPS data covering large-scale areas. For this reason, we propose a spiral update strategy of road network data based on map-matching technology, which follows a “identify→analyze→extract→update” process. The main idea is to detect condemned road segments of existing road network data with the help of HMM for each trajectory input, as well as repair them, on the local scale, by extracting new road information from trajectory data.The proposed approach avoids computing on the entire dataset of trajectory data for road segments. Instead, it updates information of existing road network data by means of focalizing on the minimum range of potential condemned segments. We evaluated the performance of our proposals using GPS traces collected on taxies and OpenStreetMap(OSM) road networks covering urban areas of Wuhan City.

map-matching; condemned road segments; partial update

The National Natural Science Foundation of China(Nos.41001296；60903035)

WU Tao (1984—), male, PhD candidate, majors in trajectory processing and analyzing.

吳濤，向隆剛，龔健雅.路網(wǎng)更新的軌跡-地圖匹配方法[J].測繪學報，2017,46(4)：507-515.

10.11947/j.AGCS.2017.20150479. WU Tao,XIANG Longgang, GONG Jianya.Renewal of Road Networks Using Map-matching Technique of Trajectories[J]. Acta Geodaetica et Cartographica Sinica,2017,46(4):507-515. DOI:10.11947/j.AGCS.2017.20150479.

P208

A

1001-1595(2017)04-0507-09

國家自然科學基金(41001296；60903035)

2015-09-30

吳濤(1984—)，男，博士生，主要研究方向為軌跡數(shù)據(jù)處理與分析。

E-mail： blackender@163.com

修回日期： 2016-12-15