吳 濤,向隆剛,龔健雅
1. 中南大學(xué)地球科學(xué)與信息物理學(xué)院,湖南 長(zhǎng)沙410083; 2. 武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北 武漢430079; 3. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心,湖北 武漢 430079
?
路網(wǎng)更新的軌跡-地圖匹配方法
吳 濤1,向隆剛2,3,龔健雅2,3
1. 中南大學(xué)地球科學(xué)與信息物理學(xué)院,湖南 長(zhǎng)沙410083; 2. 武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北 武漢430079; 3. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心,湖北 武漢 430079
全面準(zhǔn)確的路網(wǎng)信息作為智慧城市的重要基礎(chǔ)之一,在城市規(guī)劃、交通管理以及大眾出行等方面具有重要意義和價(jià)值。然而,傳統(tǒng)的基于測(cè)量的路網(wǎng)數(shù)據(jù)獲取方式往往周期較長(zhǎng),不能及時(shí)反映最新的道路信息。近幾年,隨著定位技術(shù)在移動(dòng)設(shè)備的廣泛運(yùn)用,國(guó)內(nèi)外學(xué)者在研究路網(wǎng)信息獲取時(shí)逐漸將視野轉(zhuǎn)向移動(dòng)對(duì)象的軌跡數(shù)據(jù)中所蘊(yùn)含的道路信息。當(dāng)前,基于移動(dòng)位置信息的路網(wǎng)生成和更新方法多是直接面向全部軌跡數(shù)據(jù)施加道路提取算法,在處理大規(guī)模軌跡或者大范圍道路時(shí),計(jì)算量極大。為此,本文基于軌跡地圖匹配技術(shù),提出一種采用“檢查→分析→提取→更新”過程的螺旋式路網(wǎng)數(shù)據(jù)更新策略。其主要思想是逐條輸入軌跡,借助HMM地圖匹配發(fā)現(xiàn)已有路網(wǎng)中的問題路段,進(jìn)而從問題路段周邊局部范圍內(nèi)的軌跡數(shù)據(jù)中提取并更新相關(guān)道路信息。該方法僅在局部范圍內(nèi)利用少量軌跡數(shù)據(jù)來修復(fù)路網(wǎng),避免了對(duì)整個(gè)軌跡數(shù)據(jù)集進(jìn)行計(jì)算,從而有效減少了計(jì)算量?;贠penStreetMap的武漢市區(qū)路網(wǎng)數(shù)據(jù)以及武漢市出租車軌跡數(shù)據(jù)的試驗(yàn)表明,本文提出的路網(wǎng)更新方法不僅可行,而且靈活高效。
地圖匹配;問題路段;局部更新
道路網(wǎng)絡(luò)作為一個(gè)城市的骨架,是整個(gè)城市的“生命線”,是城市社會(huì)經(jīng)濟(jì)活動(dòng)、交通運(yùn)輸賴以進(jìn)行的物質(zhì)載體。準(zhǔn)確的路網(wǎng)信息不但是城市建設(shè)、交通規(guī)劃管理、緊急事件響應(yīng)等基礎(chǔ)建設(shè)的根基,而且為人們?nèi)粘3鲂谢蛐谐桃?guī)劃提供了必要的輔助。我國(guó)的城鎮(zhèn)化進(jìn)程推進(jìn)了道路的建設(shè)與完善,使路網(wǎng)結(jié)構(gòu)處于快速變化之中,導(dǎo)致了城市路網(wǎng)數(shù)據(jù)現(xiàn)勢(shì)性相對(duì)滯后[1]。常見的路網(wǎng)信息提取和更新方法,或基于專業(yè)GPS設(shè)備的地表測(cè)量[2],需要專業(yè)的道路測(cè)量車輛與數(shù)據(jù)采集人員,信息獲取周期長(zhǎng),后期提取工作量大,且維護(hù)費(fèi)用昂貴;或基于高清遙感影像的圖像處理[3-4],受限于圖像處理技術(shù),難以進(jìn)行自動(dòng)化作業(yè),提取效率不高。近年來,伴隨著移動(dòng)端定位技術(shù)的日趨成熟,國(guó)內(nèi)外研究者逐漸開始研究基于日常民用低成本GPS設(shè)備軌跡數(shù)據(jù)的路網(wǎng)信息提取方法,追蹤裝載GPS設(shè)備的大眾交通工具可以方便快捷地收集到覆蓋整個(gè)道路網(wǎng)絡(luò)的大眾出行軌跡數(shù)據(jù),加以處理計(jì)算可以快速提取路網(wǎng)信息。
現(xiàn)有的軌跡數(shù)據(jù)路網(wǎng)信息提取方法大致分為基于軌跡數(shù)據(jù)的路網(wǎng)信息重建與基于軌跡數(shù)據(jù)的路網(wǎng)信息改進(jìn)兩類。前者直接從軌跡數(shù)據(jù)集提取整個(gè)路網(wǎng)的幾何特征。比如文獻(xiàn)[5]基于AI聚類技術(shù)結(jié)合“劃窗”算法,將原始軌跡采樣點(diǎn)逐個(gè)連接構(gòu)成軌跡線,通過連接多條軌跡線增量繪制整個(gè)未知區(qū)域的路網(wǎng)結(jié)構(gòu);文獻(xiàn)[6—7]對(duì)軌跡進(jìn)行聚類提取道路中心線,并以行進(jìn)路徑和交叉點(diǎn)最終確定路網(wǎng)結(jié)構(gòu);文獻(xiàn)[8]提出了基于Delaunay三角網(wǎng)的時(shí)空軌跡融合與路網(wǎng)生成方法。后者通過計(jì)算軌跡數(shù)據(jù)來改進(jìn)已有地圖中的道路信息,比如文獻(xiàn)[9—11]基于初始地圖與軌跡數(shù)據(jù)來改進(jìn)路網(wǎng)中指定道路的中心線。然而,前文中提到的眾多從軌跡數(shù)據(jù)中提取路網(wǎng)信息的方法存在一定的局限性。首先,直接從浮動(dòng)車軌跡數(shù)據(jù)中提取信息重建整個(gè)路網(wǎng)需要處理海量軌跡數(shù)據(jù),導(dǎo)致巨大的計(jì)算資源消耗,尤其是當(dāng)路網(wǎng)中存在較大的交叉區(qū)域或者重疊區(qū)域時(shí),計(jì)算復(fù)雜度更高。其次,目前對(duì)于已有路網(wǎng)信息的改進(jìn),或通過整體重建路網(wǎng)后進(jìn)行比對(duì)確定更新,計(jì)算成本太高;或依賴人工識(shí)別后選定區(qū)域更新,無法實(shí)現(xiàn)自動(dòng)化批量處理。
由此,本文提出了一種新的螺旋式路網(wǎng)數(shù)據(jù)更新方法,在“檢查-分析-提取-更新”這一過程中,檢查路網(wǎng)中潛在的問題路段,將參與計(jì)算的軌跡數(shù)據(jù)限定在問題路段所屬的局部區(qū)域內(nèi),從而避免對(duì)整個(gè)軌跡數(shù)據(jù)集的計(jì)算。文章首次將軌跡地圖匹配技術(shù)引入路網(wǎng)數(shù)據(jù)更新中,設(shè)計(jì)了基于軌跡-地圖匹配的路網(wǎng)更新框架。結(jié)合路網(wǎng)數(shù)據(jù)和軌跡行為的特點(diǎn),設(shè)計(jì)基于HMM模型的路網(wǎng)檢查方法,以軌跡-路網(wǎng)匹配過程中的斷點(diǎn)來發(fā)現(xiàn)并鎖定路網(wǎng)中潛在問題路段的位置,并對(duì)問題路段進(jìn)行分類分析。在此基礎(chǔ)上,建立問題路段鄰域,針對(duì)鄰域內(nèi)問題路段的不同類型,設(shè)計(jì)相應(yīng)的路段信息糾正方案,并根據(jù)鄰域局部范圍內(nèi)獲取的相關(guān)軌跡數(shù)據(jù)子集,采用不同的路段信息提取方法,進(jìn)而探討了局部范圍內(nèi)路網(wǎng)更新標(biāo)準(zhǔn),最終結(jié)合原有路網(wǎng)基線完成對(duì)現(xiàn)有路段信息的改進(jìn)和更新。該方法不再直接將算法施加于海量的軌跡數(shù)據(jù)集,只針對(duì)原有路網(wǎng)中問題路段所屬小范圍鄰域內(nèi)的部分軌跡數(shù)據(jù)子集進(jìn)行計(jì)算,減少了計(jì)算量的同時(shí),也減輕了整個(gè)路網(wǎng)數(shù)據(jù)更新過程對(duì)人工干預(yù)的依賴,大大提高了效率。
在軌跡地圖匹配過程中,由于路網(wǎng)數(shù)據(jù)本身存在問題(比如路段缺失)將導(dǎo)致匹配發(fā)生中斷,即軌跡地圖匹配的中斷能夠直接反映路網(wǎng)數(shù)據(jù)中存在的問題。基于這一認(rèn)識(shí),本文設(shè)計(jì)了一種螺旋向前推進(jìn)的路網(wǎng)更新策略,采用“檢查→分析→提取→更新”過程進(jìn)行螺旋式迭代(如圖1(a)所示)。該螺旋式過程使得系統(tǒng)可以把問題分散到各個(gè)軌跡所經(jīng)過的局部范圍內(nèi),沿著螺線進(jìn)行若干次迭代完成路網(wǎng)更新,避免將大量計(jì)算資源消耗在處理整個(gè)軌跡數(shù)據(jù)集上。螺旋式更新框架的另一個(gè)優(yōu)勢(shì)在于其執(zhí)行上的靈活性,既可以對(duì)軌跡數(shù)據(jù)集所覆蓋的路網(wǎng)區(qū)域進(jìn)行多次螺旋式迭代檢測(cè)更新,也可以指定某一條軌跡對(duì)特定路線進(jìn)行檢測(cè)更新。在詳細(xì)介紹路網(wǎng)更新框架之前,首先給出相關(guān)的基本概念。
定義1:路網(wǎng),G=(N,L),是由邊(L)和節(jié)點(diǎn)(N)兩類NDM基本元素的集合組織表達(dá)的道路網(wǎng)絡(luò)(如圖1(b)所示)。其中,N=(ni|i=1,2,…,K)是路網(wǎng)中路段節(jié)點(diǎn)的集合,L=(lj|j=1,2,…,H)是路段在路網(wǎng)中所對(duì)應(yīng)弧段的集合。
定義2:軌跡,T=(Pi|i=1,2,…,M),為多個(gè)GPS采樣點(diǎn)Pi組成的序列。其中,Pi包含移動(dòng)對(duì)象在該采樣點(diǎn)的位置和時(shí)間信息。
路網(wǎng)表現(xiàn)在二維空間上是由多個(gè)路段相互連接、交叉或者并行所組成的一個(gè)整體(圖1(b)),軌跡數(shù)據(jù)是移動(dòng)對(duì)象運(yùn)動(dòng)過程的空間位置采樣點(diǎn)序列。軌跡地圖匹配則是將軌跡采樣點(diǎn)序列轉(zhuǎn)換為具有空間語義信息的路段序列。當(dāng)路網(wǎng)G中的某位置缺少路段的信息,或路段的信息有錯(cuò)誤時(shí),則認(rèn)為該路網(wǎng)的這一位置存在問題路段。例如,實(shí)際路網(wǎng)中的路段a和b之間有連通關(guān)系(即存在節(jié)點(diǎn)),如果相關(guān)路網(wǎng)數(shù)據(jù)中沒有記錄a或者b(缺少路段的信息),或者沒有記錄a與b之間的連通關(guān)系(路段的信息有錯(cuò)誤),則a(或者b)被視為問題路段,軌跡地圖匹配在a與b之間發(fā)生中斷。
整個(gè)更新框架始于從OSM獲取基于“節(jié)點(diǎn)-邊”通用網(wǎng)絡(luò)模型NDM[9](network data model)組織的原始路網(wǎng)數(shù)據(jù)G,隨后進(jìn)入螺旋式更新過程(如圖1(c)所示)螺旋中每輪迭代,讀入單條軌跡數(shù)據(jù)T檢查地圖匹配中斷,如未發(fā)生中斷則結(jié)束本輪操作,從軌跡數(shù)據(jù)集中讀入下一條軌跡開始新一輪迭代;否則,針對(duì)各中斷所在位置分別建立問題路段鄰域,分析問題路段類型,進(jìn)而從軌跡數(shù)據(jù)中提取路段幾何信息等對(duì)路網(wǎng)進(jìn)行更新,然后等待進(jìn)入下輪迭代。如果后續(xù)未有待匹配軌跡讀入,則視為整個(gè)螺旋過程結(jié)束。
圖1 路網(wǎng)更新框架流程Fig.1 Flowchart of road network renewal
2.1 基于HMM模型的地圖匹配
本節(jié)重點(diǎn)討論基于HMM模型的軌跡-地圖匹配技術(shù)的路網(wǎng)檢查方法。軌跡-地圖匹配方法大致可分為4種類型[12]:基于幾何特征的地圖匹配[13]、基于拓?fù)涞牡貓D匹配[14]、基于概率的地圖匹配[15]以及基于高階技術(shù)的地圖匹配(基于高階技術(shù)的地圖匹配,泛指那些使用更精致概念(morerefinedconcepts)的地圖匹配方法,例如卡爾曼濾波[16]、隱馬爾科模型[17-22]等)。
本文選取一階HMM(隱馬爾科夫模型)模擬軌跡在路網(wǎng)中的移動(dòng),將軌跡在路網(wǎng)中的移動(dòng)定義為在路段兩個(gè)節(jié)點(diǎn)之間移動(dòng)的馬爾科夫過程,以采樣點(diǎn)到節(jié)點(diǎn)的大圓距離(greatcircledistance)為判定依據(jù),提取與采樣點(diǎn)最鄰近的n個(gè)節(jié)點(diǎn)為潛在匹配候選路段節(jié)點(diǎn)。基于HMM的地圖匹配過程中,問題路段會(huì)導(dǎo)致單次匹配的馬爾科夫過程不連續(xù),進(jìn)而造成匹配路徑中的斷點(diǎn),最終引發(fā)的匹配中斷。
如圖2所示,沿觀測(cè)值序列方向,取軌跡采樣點(diǎn)各自最鄰近的n個(gè)節(jié)點(diǎn)建立HMM模型進(jìn)行地圖匹配。整個(gè)匹配過程分別有兩個(gè)斷點(diǎn)導(dǎo)致中斷:第一次在采樣點(diǎn)為P4到P7,軌跡經(jīng)過了一條未被路網(wǎng)數(shù)據(jù)記錄的道路,導(dǎo)致P5和P6這兩點(diǎn)到候選路段節(jié)點(diǎn)的觀測(cè)概率極低;第二次在采樣點(diǎn)P9到P10,軌跡路徑所對(duì)應(yīng)道路在路網(wǎng)數(shù)據(jù)中間存在拓?fù)溴e(cuò)誤,導(dǎo)致P9對(duì)應(yīng)路段對(duì)其后可能路段的轉(zhuǎn)移概率為0或非常小。通常這種中斷會(huì)影響地圖匹配輸出結(jié)果的質(zhì)量,因此會(huì)在匹配過程中被當(dāng)成噪聲或者異常值通過算法處理后選擇性跳過(這些也是造成地圖匹配結(jié)果誤差的原因),然而本文則反向關(guān)注到了匹配中斷與問題路段的相關(guān)性,即這些匹配中斷的背后所反映出來的問題很大程度上就是路網(wǎng)數(shù)據(jù)的問題。由此,本文接下來將利用這一點(diǎn),以匹配過程中斷來定位路網(wǎng)中問題路段所在的位置。
圖2 基于HMM地圖匹配的中斷Fig.2 Breaks of map-matching based on HMM
2.2 問題路段分析與檢查
基于HMM的地圖匹配過程使得對(duì)路網(wǎng)數(shù)據(jù)的檢查變成了可能,本節(jié)將對(duì)可能探測(cè)到的問題路段進(jìn)行分析,以便在后續(xù)處理中能針對(duì)不同特點(diǎn)的問題路段采用相應(yīng)的處理方法。結(jié)合路網(wǎng)數(shù)據(jù)自身特點(diǎn),可將問題路段劃分為兩大類:
2.2.1 路段信息錯(cuò)誤
通過大眾采集數(shù)據(jù)在線協(xié)同繪制的路網(wǎng)數(shù)據(jù)(如本文中所使用的OpenStreeMap數(shù)據(jù))往往會(huì)因?yàn)樯蟼饔脩舨杉瘮?shù)據(jù)的質(zhì)量而造成種種問題,常見的是路段間的拓?fù)溴e(cuò)誤,即本應(yīng)相互連接的路段沒有閉合等。
2.2.2 路段信息缺失
新道路信息的采集相對(duì)于城市建設(shè)的滯后往往會(huì)造成路網(wǎng)數(shù)據(jù)中道路或部分路段的缺失。例如,移動(dòng)對(duì)象經(jīng)過了一條新建的路段或者城市中某一區(qū)塊(如小區(qū)或者公園),而現(xiàn)有路網(wǎng)數(shù)據(jù)沒有及時(shí)更新該路段的信息。
給定一條軌跡T與路網(wǎng)G,當(dāng)且僅當(dāng)軌跡T上單個(gè)或者連續(xù)多個(gè)采樣點(diǎn)位置與路網(wǎng)匹配過程的中斷滿足以下任一條件時(shí),則稱該中斷所在位置存在問題路段:
(1) 軌跡采樣點(diǎn)到所有道路的觀測(cè)概率都非常小或?yàn)?(即采樣點(diǎn)到最近路段的距離遠(yuǎn)大于某一距離閾值)。
(2) 軌跡上連續(xù)兩個(gè)采樣點(diǎn)對(duì)應(yīng)的匹配路段間轉(zhuǎn)移概率都非常小或?yàn)?。
(3) 軌跡上連續(xù)采樣的所匹配路段距離與采樣間隔時(shí)間的比值(即軌跡匹配后的平均移動(dòng)速度)超過路段本身實(shí)際速度限制(或預(yù)設(shè)的某一速度閾值)。
如果問題路段鄰近區(qū)域內(nèi)軌跡采樣點(diǎn)與路網(wǎng)信息同時(shí)滿足以下條件時(shí),判定為路段信息錯(cuò)誤(其余判定為路段信息缺失):
(1) 最大觀測(cè)概率的節(jié)點(diǎn)之間狀態(tài)轉(zhuǎn)移概率非常小。
(2) 最大觀測(cè)概率的節(jié)點(diǎn)間的大圓距離遠(yuǎn)小于其路徑距離。
(3) 觀測(cè)點(diǎn)間的實(shí)際均速度遠(yuǎn)低于完成對(duì)應(yīng)節(jié)點(diǎn)間轉(zhuǎn)移所需要的平均速度。
基于以上概念,本文設(shè)計(jì)的問題路段檢測(cè)算法,關(guān)鍵步驟如圖3所示。從軌跡起點(diǎn)開始檢查初始概率(initialprobability),如果滿足閾值設(shè)定的條件則繼續(xù)向后檢查;否則將其標(biāo)記為中斷點(diǎn),然后以下一采樣點(diǎn)為起點(diǎn),重新計(jì)算初始概率,繼續(xù)檢查過程。如果檢查未到軌跡終點(diǎn),發(fā)生上述任意一種情況都會(huì)視為當(dāng)前匹配檢查的一個(gè)中斷,即主動(dòng)終止對(duì)當(dāng)前采樣點(diǎn)位置的檢查,以下一個(gè)采樣點(diǎn)為起點(diǎn),開始新一輪檢查。需要注意的是,軌跡本身存在較大噪聲時(shí)也可能造成匹配中斷,因此需要預(yù)先對(duì)軌跡數(shù)據(jù)本身進(jìn)行篩選去噪。
圖3 問題路段檢查算法Fig.3 The algorithm of find breaks
本節(jié)首先基于問題路段建立路段鄰域,進(jìn)而判定問題路段類型,然后依據(jù)所發(fā)現(xiàn)問題路段的類型特點(diǎn)有針對(duì)性地設(shè)計(jì)處理方法,最終完成對(duì)路網(wǎng)信息的更新。針對(duì)路段信息錯(cuò)誤,依據(jù)鄰域內(nèi)軌跡數(shù)據(jù)與非問題路段進(jìn)行修正;針對(duì)路段信息缺失,依據(jù)問題路段鄰域內(nèi)軌跡數(shù)據(jù)分布情況的不同,文中采用PAM聚類的道路特征點(diǎn)提取或基于緩沖區(qū)的道路骨架線提取兩種方法從GPS軌跡數(shù)據(jù)中提取路段幾何信息。
3.1 問題路段分析處理
如圖4所示,本文設(shè)定以發(fā)生匹配中斷的軌跡采樣點(diǎn)(稱之為分裂點(diǎn),breakpoint)為中心,以其沿軌跡上前后兩個(gè)最鄰近的有效匹配采樣點(diǎn)(pre-breakpoint與post-breakpoint)之間的最大距離為半徑建立的圓形區(qū)域,設(shè)為問題路段鄰域。
圖4 問題路段鄰域Fig.4 The neighborhood of a condemned road segment
依照先易后難的原則,優(yōu)先對(duì)路段信息錯(cuò)誤進(jìn)行處理,檢查問題路段鄰域內(nèi)原有路段之間的連通關(guān)系,判定breakpoint前后有效匹配的采樣點(diǎn)所對(duì)應(yīng)的最大觀測(cè)概率節(jié)點(diǎn)間的最短距離,拉伸合并已有路段使之符合最短距離,最后更新交疊信息。針對(duì)路段信息缺失,設(shè)計(jì)從問題路段鄰域內(nèi)的多條子軌跡中提取缺失路段的幾何信息進(jìn)行修補(bǔ),從而避免單條軌跡稀疏可能導(dǎo)致的信息丟失。顯然,道路提取的方法受制于軌跡數(shù)據(jù)本身的采樣情況,根據(jù)問題路段鄰域內(nèi)軌跡數(shù)據(jù)分布情況的不同分別采用相應(yīng)的提取方法。從數(shù)據(jù)庫中提取落入問題路段鄰域內(nèi)的子軌跡數(shù)據(jù),以之前用于路網(wǎng)檢查的軌跡采樣點(diǎn)為中心,以平均道路寬度為半徑,計(jì)算其周邊范圍內(nèi)所包含的軌跡點(diǎn)數(shù)量,即子軌跡采樣點(diǎn)密度。如果采樣點(diǎn)密度不滿足密度閾值minPts,則采取緩沖區(qū)骨架提取方法,否則默認(rèn)使用PAM聚類方法。前者更適合處理多條內(nèi)子軌跡路徑為網(wǎng)狀結(jié)構(gòu)(即問題鄰域內(nèi)與之前用于檢查的軌跡路徑相似的子軌跡較少);后者處理多條內(nèi)子軌跡路徑單一的情況時(shí)(即問題鄰域內(nèi)其他子軌跡與之前用于檢查的軌跡路徑相似),效果比較理想。
3.2 基于PAM聚類的路段信息提取
基于聚類的道路信息提取是通過聚類方法將沿道路分布的軌跡采樣點(diǎn)按一定的約束條件聚合成具有相似行為的簇,提取代表各個(gè)簇的聚類點(diǎn)作為反映道路幾何特征的關(guān)鍵點(diǎn)擬合道路中心線。在研究了已有的眾多聚類方法之后,筆者認(rèn)為PAM(partitioningaroundmedoids,k-medoids)聚類方法比較適用于局部范圍內(nèi)的少量軌跡數(shù)據(jù)的道路提取計(jì)算。PAM聚類是對(duì)k-means算法的改進(jìn),它先對(duì)n個(gè)對(duì)象給出k個(gè)類簇劃分,然后通過反復(fù)計(jì)算類簇內(nèi)除中心點(diǎn)之外的各點(diǎn)到其他所有點(diǎn)的聚類最小值來找出更合適的中心點(diǎn),對(duì)于較小的數(shù)據(jù)集非常有效。該方法不再使用k-means的幾何中心點(diǎn),轉(zhuǎn)而在簇內(nèi)的真實(shí)采樣點(diǎn)中尋找中心點(diǎn),最小化了簇內(nèi)所有采樣點(diǎn)之間的差值,從而能較好地排除異常值對(duì)于分簇結(jié)構(gòu)的影響[24],即對(duì)于軌跡采樣點(diǎn)的噪聲和異常值不敏感。結(jié)合這些特點(diǎn),本文選定歐式距離判定聚類參數(shù),對(duì)問題路段鄰域范圍內(nèi)的軌跡數(shù)據(jù)進(jìn)行PAM聚類,提取問題路段信息。
基于軌跡點(diǎn)PAM聚類的局部道路信息提取具體分為以下3個(gè)步驟:
(1) 確定參與PAM聚類的軌跡點(diǎn)數(shù)n,計(jì)算聚類點(diǎn)的輪廓(silhouette)[22]確定合適的聚類數(shù)k。
(2) 以任意k個(gè)軌跡點(diǎn)為中心開始,與其他n-k個(gè)軌跡點(diǎn)進(jìn)行迭代計(jì)算,判定參加聚類行為的邊界,以及替換中心點(diǎn)。
(3) 遍歷所有聚類點(diǎn),基于相鄰間聚類點(diǎn)的轉(zhuǎn)向角θ與距離D,設(shè)定閾值轉(zhuǎn)角與距離閾值篩選結(jié)果,提取道路中心線。
3.3 基于緩沖區(qū)骨架的路段信息提取
基于軌跡線緩沖區(qū)提取骨架的方法通過融合問題路段鄰域內(nèi)多條軌跡數(shù)據(jù)的軌跡線所生成緩沖區(qū),從中提取融合后的緩沖區(qū)的骨架線作為道路中心線。緩沖區(qū)的骨架線與緩沖區(qū)多邊形面本身保持一致的連通性和拓?fù)浣Y(jié)構(gòu),可以在一定程度上反映道路的幾何特征[25]。目前已有多種多邊形的骨架線的提取方法較為成熟,考慮到軌跡數(shù)據(jù)的特點(diǎn),以及算法本身的執(zhí)行效率,本文選取簡(jiǎn)單易行的水平(或垂直)切割線中點(diǎn)來提取軌跡緩沖區(qū)的骨架線,依據(jù)軌跡緩沖區(qū)的形狀可以大致確定切割線方向,在此基礎(chǔ)上求取每條切割線與緩沖區(qū)邊界的交點(diǎn),最后計(jì)算每組交點(diǎn)的中心點(diǎn),將其連接形成該緩沖區(qū)的骨架線。
局部道路骨架提取方法具體分為以下3個(gè)步驟:
(1) 將軌跡采樣點(diǎn)數(shù)據(jù)分別依照各自的時(shí)間順序連接形成多條軌跡線。
(2) 設(shè)置緩沖區(qū)半徑,為每條軌跡線建立緩沖區(qū),將生成的多個(gè)緩沖區(qū)融合成一個(gè)緩沖區(qū)。
(3) 判別緩沖區(qū)水平和垂直方向的投影,以較短的投影方向作為切割線方向,等間距切割緩沖區(qū),提取中點(diǎn)連接線作為道路中心線。
3.4 局部路網(wǎng)數(shù)據(jù)更新
前面已經(jīng)從軌跡數(shù)據(jù)中提取了路網(wǎng)中缺失道路的幾何信息,需要將新生成的路段數(shù)據(jù)添加到原路網(wǎng)中,并對(duì)原有路網(wǎng)中相應(yīng)區(qū)域的道路信息的拓?fù)潢P(guān)系進(jìn)行更新。兩步操作處理路段信息錯(cuò)誤和路段缺失的相關(guān)數(shù)據(jù)更新:①處理不閉合路段信息;②更新交疊信息。
3.4.1 更新交疊信息
檢測(cè)新增路段與其周邊領(lǐng)域內(nèi)原有路段之間的連通關(guān)系,如果存在gap(如圖5(a)中虛線圓標(biāo)出區(qū)域),則根據(jù)閾值(本文以道路寬度或者兩倍道路寬度作為閾值)判定新增路段端點(diǎn)與原有路段的最短距離,將滿足閾值條件的端點(diǎn)沿著最短距離路徑拉伸至已有路段。
3.4.2 處理不閉合路段信息
新生成的路段數(shù)據(jù)會(huì)改變?cè)肪W(wǎng)數(shù)據(jù)中的拓?fù)潢P(guān)系,如圖5(b)所示,在新增路段與原有路段之間形成了新的交疊關(guān)系,需要對(duì)路網(wǎng)中的相關(guān)路段重新分割,生成新的路網(wǎng)節(jié)點(diǎn)與之相互連接。
圖5 局部路網(wǎng)數(shù)據(jù)更新Fig.5 Renewal of local road network
4.1 試驗(yàn)環(huán)境與真實(shí)數(shù)據(jù)
本文選擇64位Windows8.1操作系統(tǒng)作為試驗(yàn)平臺(tái),以VisualStudio2012(64位版)為開發(fā)環(huán)境,基于ArcGIS10.2提供的路網(wǎng)數(shù)據(jù)的處理基礎(chǔ)工具,讀取GPS軌跡,由地圖匹配獲取路段缺失位置,對(duì)缺失區(qū)域進(jìn)行局部路網(wǎng)信息更新,并將最終結(jié)果顯示在電子地圖上。試驗(yàn)所用PC機(jī)的硬件環(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,行進(jìn)過程中有效GPS衛(wèi)星連接數(shù)在3~6之間。所有原始軌跡數(shù)據(jù)首先經(jīng)過預(yù)處理階段,以有效衛(wèi)星、水平精度、距離、速度等閾值進(jìn)行篩選。經(jīng)過預(yù)處理之后,有17.3%的軌跡采樣點(diǎn)被移除(其中包括異常點(diǎn)和冗余點(diǎn)等)。
4.2 試驗(yàn)結(jié)果與分析
試驗(yàn)選取8條軌跡數(shù)據(jù)對(duì)路網(wǎng)數(shù)據(jù)進(jìn)行路段信息缺失檢測(cè),共發(fā)現(xiàn)了12處問題路段并建立對(duì)應(yīng)鄰域(如圖6(b)所示),提取局部范圍內(nèi)的20條軌跡進(jìn)行路段信息提取后生成了圖6(c)中所示的新增路段。
圖6 路網(wǎng)數(shù)據(jù)更新Fig.6 Renewal of road network
分別依據(jù)鄰域內(nèi)軌跡數(shù)據(jù)的分布情況,選用基于PAM聚類方法(聚類后軌跡提取率約為30%)與緩沖區(qū)骨架線方法,提取反映該區(qū)域內(nèi)路段幾何信息的軌跡聚類點(diǎn)。每提取完一個(gè)問題路段鄰域的道路幾何信息,更新程序就增量處理一次路網(wǎng)數(shù)據(jù)更新,依據(jù)上文介紹的兩種不同情況,在更新路網(wǎng)數(shù)據(jù)時(shí),分別對(duì)生成路段端點(diǎn)以及交點(diǎn)處進(jìn)行了處理。根據(jù)試驗(yàn)中用到的車載GPS的數(shù)據(jù)采集精度以及道路寬度,本文選定的距離閾值取武漢市除大道以外的主、次干道平均寬度2倍值,即30m。
圖6(d)中將更新后的路網(wǎng)數(shù)據(jù)與遙感影像進(jìn)行比對(duì),可以發(fā)現(xiàn)自軌跡數(shù)據(jù)提取的新增道路結(jié)構(gòu)與實(shí)際路網(wǎng)結(jié)構(gòu)基本一致,僅在個(gè)別軌跡數(shù)據(jù)極其稀疏的路段出現(xiàn)較明顯的偏差,仍存在有處于問題路段鄰域內(nèi)的路段沒有被提取,這是因?yàn)樵囼?yàn)中所收集到的軌跡數(shù)據(jù)沒有覆蓋這些路段。試驗(yàn)也從定量的角度分析計(jì)算了更新后路段與路網(wǎng)基線相應(yīng)區(qū)域路段之間的幾何完成度與拓?fù)渫瓿啥取?/p>
幾何完成度=新生成路段中匹配路段長(zhǎng)度/新生成路段總長(zhǎng)度
拓?fù)渫瓿啥?新生成交點(diǎn)中匹配的個(gè)數(shù)/新生成交點(diǎn)總個(gè)數(shù)
本文設(shè)定新生路段的某一段與基線路段間的最大投影距離小于閾值(本文選10m),且方位角最大偏差在30°以內(nèi),則認(rèn)定新路段中的該段與基線匹配;新生交點(diǎn)與路段基線交點(diǎn)間距離小于閾值(本文選3m),則認(rèn)定新交點(diǎn)與基線匹配。12個(gè)問題路段鄰域中更新后的路段相較于路網(wǎng)基線,平均幾何完成度是78.4%,平均拓?fù)渫瓿啥仁?3.3%。平均拓?fù)渫瓿啥认鄬?duì)較低,是因?yàn)楸疚脑谔幚聿婚]合情況時(shí),將滿足閾值條件的不閉合端點(diǎn)沿最短路徑投影拉伸至已有路徑,而實(shí)際情況下,可能該段并不是沿最短路徑延伸的。后續(xù)可以通過改進(jìn)不閉合的處理方法來提高拓?fù)渫瓿啥?。其次,某些新路段?nèi)部的交點(diǎn)由于軌跡數(shù)據(jù)中在該鄰域內(nèi)運(yùn)動(dòng)的軌跡稀少,極個(gè)別路段上只存在1輛車的采樣數(shù)據(jù),且受周邊高層建筑影響,軌跡數(shù)據(jù)質(zhì)量不高,從而影響更新路段質(zhì)量。
本文提出了一種基于軌跡地圖匹配的路網(wǎng)數(shù)據(jù)更新方法。該方法以螺旋式過程推進(jìn),每次迭代通過軌跡地圖匹配技術(shù),快速探測(cè)到路網(wǎng)數(shù)據(jù)中存在的問題路段,進(jìn)而有的放矢、有針性地建立問題路段鄰域,提取軌跡數(shù)據(jù)中的路段幾何信息,完成路網(wǎng)數(shù)據(jù)更新。更新過程以基于HMM軌跡地圖匹配方法檢測(cè)問題路網(wǎng),以落入問題路段鄰域內(nèi)的軌跡數(shù)據(jù)為源,根據(jù)軌跡數(shù)據(jù)覆蓋特點(diǎn),分別采用PAM聚類和緩沖區(qū)骨架線兩類方法,從軌跡數(shù)據(jù)中提取局部范圍內(nèi)的路段幾何信息,進(jìn)而依據(jù)路段的拓?fù)涮卣鏖_始討論,最終完成對(duì)原有路網(wǎng)數(shù)據(jù)的更新。文中提出的基于地圖匹配的路網(wǎng)數(shù)據(jù)更新方法相對(duì)于其他已有路網(wǎng)數(shù)據(jù)更新應(yīng)用,具有以下4個(gè)特點(diǎn):
(1) 針對(duì)整個(gè)路網(wǎng)的更新是一個(gè)螺旋推進(jìn)的迭代過程,每次的更新都建立在前一次的基礎(chǔ)上,不斷改進(jìn)原有路網(wǎng)數(shù)據(jù)質(zhì)量。
(2) 以軌跡的地圖匹配過程作為探測(cè)手段,能迅速查找并鎖定路網(wǎng)中存在的問題路段并記錄其位置。
(3) 軌跡數(shù)據(jù)對(duì)于路網(wǎng)數(shù)據(jù)而言,所提取的路段幾何信息僅在問題路段處有意義,在此基礎(chǔ)上建立問題路段鄰域,限定路段信息提取區(qū)域范圍,以此最小化參與計(jì)算的軌跡數(shù)據(jù),從而有效減少了路段提取的計(jì)算量。
(4) 在問題路段鄰域的基礎(chǔ)上,靈活選取PAM聚類和緩沖區(qū)骨架線兩種不同的提取方法,增強(qiáng)了對(duì)于軌跡數(shù)據(jù)的實(shí)際覆蓋情況的適應(yīng)性。
本文研究重心在于設(shè)計(jì)并驗(yàn)證文中提出的螺旋式路網(wǎng)更新策略,并未對(duì)研究道路信息提取算法進(jìn)行優(yōu)化,計(jì)算結(jié)果在一定程度上受限于軌跡本身精度,但仍可作為路網(wǎng)研究者以及實(shí)測(cè)工作人員快速發(fā)現(xiàn)問題路段,進(jìn)而提取道路信息的重要輔助。后續(xù)的研究工作將在此更新策略的基礎(chǔ)上,進(jìn)一步探究基于軌跡數(shù)據(jù)的道路信息提取算法,并考慮基于本文提出的方法研究個(gè)性化局部路網(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] 唐爐亮, 劉章, 楊雪, 等. 符合認(rèn)知規(guī)律的時(shí)空軌跡融合與路網(wǎng)生成方法[J]. 測(cè)繪學(xué)報(bào). 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]. 武漢測(cè)繪科技大學(xué)學(xué)報(bào), 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.
(責(zé)任編輯:陳品馨)
測(cè)繪地理信息與導(dǎo)航高端論壇——《測(cè)繪學(xué)報(bào)》創(chuàng)刊60周年學(xué)術(shù)研討會(huì)通知(第一號(hào))
時(shí)間:2017年10月21日 地點(diǎn):深圳
當(dāng)前,新一輪科技創(chuàng)新和產(chǎn)業(yè)發(fā)展正在深度融合,以互聯(lián)網(wǎng)+為代表的信息技術(shù)飛速發(fā)展,泛在測(cè)繪與位置服務(wù)的發(fā)展已經(jīng)進(jìn)入大數(shù)據(jù)時(shí)代,智能、快捷服務(wù)已經(jīng)滲透到我國(guó)各個(gè)行業(yè),測(cè)繪地理信息行業(yè)資本融合勢(shì)頭迅猛。國(guó)家測(cè)繪地理信息局也在《測(cè)繪地理信息“十三五”規(guī)劃》中,確立了新型基礎(chǔ)測(cè)繪、地理國(guó)情監(jiān)測(cè)、應(yīng)急測(cè)繪、航空航天遙感測(cè)繪、全球地理信息資源開發(fā)“五大業(yè)務(wù)”,形成了公益性保障與地理信息產(chǎn)業(yè)市場(chǎng)化服務(wù)協(xié)同發(fā)展和深度融合的工作布局?!稖y(cè)繪學(xué)報(bào)》長(zhǎng)期致力于推動(dòng)測(cè)繪地理信息的基礎(chǔ)理論與技術(shù)應(yīng)用發(fā)展,為全國(guó)測(cè)繪地理信息行業(yè)的科研機(jī)構(gòu)、高等院校、生產(chǎn)單位等提供學(xué)術(shù)交流與合作的平臺(tái)。為進(jìn)一步促進(jìn)新理論、新技術(shù)、新方法、新思想的交流,總結(jié)和發(fā)展近年來我國(guó)測(cè)繪地理信息行業(yè)的最新成果,《測(cè)繪學(xué)報(bào)》編委會(huì)定于2017年10月21日在深圳舉辦“測(cè)繪地理信息與導(dǎo)航高端論壇——《測(cè)繪學(xué)報(bào)》創(chuàng)刊60周年學(xué)術(shù)研討會(huì)”,具體事宜通知如下。
一、會(huì)議主題
泛在測(cè)繪與智能服務(wù)
二、會(huì)議時(shí)間與地點(diǎn)
會(huì)議時(shí)間:2017年10月21日
報(bào)到時(shí)間:2017年10月20日全天
地 點(diǎn):廣東省深圳市
三、組織機(jī)構(gòu)
主辦單位: 中國(guó)測(cè)繪地理信息學(xué)會(huì)《測(cè)繪學(xué)報(bào)》 編委會(huì)
中國(guó)地圖出版集團(tuán)
深圳大學(xué)
深圳市測(cè)繪地理信息學(xué)會(huì)
協(xié)辦單位: 中國(guó)測(cè)繪科學(xué)研究院 測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室 武漢大學(xué)測(cè)繪學(xué)院 武漢大學(xué)遙感信息工程學(xué)院 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院 同濟(jì)大學(xué)測(cè)繪與地理信息學(xué)院 中國(guó)科學(xué)院測(cè)量與地球物理研究所 西安測(cè)繪研究所 中南大學(xué)地球科學(xué)與信息物理學(xué)院 中國(guó)礦業(yè)大學(xué)環(huán)境與測(cè)繪學(xué)院 信息工程大學(xué)地理空間信息學(xué)院 信息工程大學(xué)導(dǎo)航與空天目標(biāo)工程學(xué)院 長(zhǎng)安大學(xué)地質(zhì)工程與測(cè)繪學(xué)院 海軍工程大學(xué)導(dǎo)航工程系 海軍大連艦艇學(xué)院海洋測(cè)繪系 深圳市數(shù)字城市工程研究中心
承辦單位: 《測(cè)繪學(xué)報(bào)》編輯部 深圳大學(xué)智慧城市研究院 深圳大學(xué)空間信息智能感知與服務(wù)深圳市重點(diǎn)實(shí)驗(yàn)室
深圳大學(xué)海岸帶地理環(huán)境監(jiān)測(cè)國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室
媒體支持: 中國(guó)測(cè)繪報(bào) 武漢大學(xué)學(xué)報(bào)·信息科學(xué)版 測(cè)繪通報(bào) 泰伯網(wǎng) 慧天地 中國(guó)測(cè)繪新聞網(wǎng) 測(cè)繪科技信息網(wǎng) GeoTalks 測(cè)繪之家
四、會(huì)議日程安排
時(shí)間上午下午10月20日(周五)論壇參會(huì)人員全天報(bào)到10月21日(周六)開幕式,院士報(bào)告分論壇
五、會(huì)務(wù)相關(guān)事項(xiàng)
會(huì)議專用郵箱:agcs2017@163.com
會(huì)議QQ群:496372706
會(huì)議聯(lián)系人:宋啟凡 電話:010—68531322
注:會(huì)務(wù)注冊(cè)、參會(huì)費(fèi)用、會(huì)議具體地點(diǎn)、住宿安排等具體事宜,將在后續(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].測(cè)繪學(xué)報(bào),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
國(guó)家自然科學(xué)基金(41001296;60903035)
2015-09-30
吳濤(1984—),男,博士生,主要研究方向?yàn)檐壽E數(shù)據(jù)處理與分析。
E-mail: blackender@163.com
修回日期: 2016-12-15