基于行人GPS軌跡提取路網(wǎng)信息的高效算法

1、基于行人GPS軌跡提取路網(wǎng)信息的高效算法引言當(dāng)今時(shí)代，數(shù)字地圖對(duì)于每一個(gè)人來(lái)說(shuō)都變得日益重要。普通用戶下載諸如Google地圖、百度地圖等類(lèi)似軟件來(lái)尋找目的地以及周?chē)木包c(diǎn)、住宿和餐旅等等。商家用來(lái)宣傳自己的品牌(Fathi and Krumm 2010)。但對(duì)國(guó)內(nèi)數(shù)字地圖而言，目前大部分都由特定的地圖供應(yīng)商通過(guò)專(zhuān)門(mén)部署GPS裝置的汽車(chē)在路上行駛并采集數(shù)據(jù)。數(shù)據(jù)獲取與更新成本的高昂意味著購(gòu)買(mǎi)這些這類(lèi)地圖數(shù)據(jù)需要花費(fèi)大量的資金。因此，國(guó)內(nèi)除了百度、高德、搜狗外，鮮有其他的地圖服務(wù)商。然而，隨著城市化進(jìn)程的加快與道路網(wǎng)的建設(shè)與完善，用戶卻面臨這樣的問(wèn)題：某個(gè)地方新修了一條道路，但因路網(wǎng)數(shù)據(jù)的更新不

2、及時(shí)而無(wú)法在地圖上找到這條路。如何縮短路網(wǎng)更新時(shí)間，盡可能滿足用戶的需求體驗(yàn)，則需要探索新的路網(wǎng)采集與更新方式。在帶有GPS裝置的移動(dòng)設(shè)備越來(lái)越普遍的背景下，如何通過(guò)合理的路網(wǎng)挖掘算法，有效利用這些普通用戶的定位數(shù)據(jù)，及時(shí)更新現(xiàn)有路網(wǎng)信息，這不僅極大降低路網(wǎng)更新的高昂成本，還將有力提升地圖服務(wù)的質(zhì)量與效率。這項(xiàng)技術(shù)的難點(diǎn)有二：一是大數(shù)據(jù)量。每天有成千上萬(wàn)的人通過(guò)搭載有GPS裝置的設(shè)備定位，假如按照每周一次更新的設(shè)想來(lái)獲取GPS軌跡數(shù)據(jù)，這個(gè)數(shù)據(jù)量也將輕松突破TB級(jí)。大數(shù)據(jù)的獲取與處理需要強(qiáng)有力的硬件支撐，但這不是本文的重點(diǎn)。二是合適的路網(wǎng)挖掘算法。將GPS數(shù)據(jù)轉(zhuǎn)換為數(shù)字化路網(wǎng)，并與原有路網(wǎng)匹配

3、，刪除已經(jīng)廢棄的道路，添加新增的道路。世界上最大的開(kāi)源地圖提供商O(píng)penStreetMap(Haklay and Weber 2008)采用一種讓志愿者攜帶GPS裝置記錄GPS軌跡來(lái)手動(dòng)更新地圖的方式，獲取的數(shù)據(jù)稱(chēng)為“志愿者地理信息”(Haklay 2008)。志愿者地理信息秉承“人人都是傳感器”的理念(Schroedl, Wagstaff et al. 2004)，將每個(gè)人不僅作為地理信息的使用者，更是生產(chǎn)者。參考上述理念，本次實(shí)驗(yàn)通過(guò)尋找志愿者，確定所需的實(shí)驗(yàn)區(qū)，采用步行的方式，邊走邊采集GPS點(diǎn)，形成了大約10萬(wàn)條GPS軌跡數(shù)據(jù)，建立GPS軌跡數(shù)據(jù)庫(kù)，并設(shè)計(jì)新型的路網(wǎng)挖掘算法，從中提取有

4、用的路網(wǎng)信息挖掘路網(wǎng)。國(guó)內(nèi)外研究現(xiàn)狀國(guó)外對(duì)于道路的提取算法研究比較成熟。這些算法大都基于算術(shù)幾何，有的以節(jié)點(diǎn)為核心，有的以特征追蹤為核心。這對(duì)于較為規(guī)則的車(chē)輛軌跡處理是高效而準(zhǔn)確的(Fathi, A. and J. Krumm ,2010)。這些算法之所以高效，一是因?yàn)樗惴ㄔO(shè)計(jì)的恰當(dāng)，另一方面則是因?yàn)楦卟蓸勇识碗S機(jī)性的GPS數(shù)據(jù)。這種通過(guò)專(zhuān)門(mén)的車(chē)載導(dǎo)航系統(tǒng)獲取的大量數(shù)據(jù)，數(shù)據(jù)特征規(guī)則且明顯(圖1)，算法難度不是很高。然而，VGI數(shù)據(jù)在實(shí)踐中往往是低采樣率的，大約為2-5分鐘有一個(gè)點(diǎn)，點(diǎn)與點(diǎn)之間相隔太遠(yuǎn)導(dǎo)致一些正常的匹配算法在面對(duì)VGI數(shù)據(jù)時(shí)低效，甚至有可能產(chǎn)生邏輯錯(cuò)誤。另外，專(zhuān)門(mén)采集數(shù)據(jù)處理

5、后得到的信息主要用于駕駛的道路網(wǎng)，而對(duì)于行人需要的步行網(wǎng)，例如天橋、地下通道等減少交通負(fù)擔(dān)的設(shè)施生成與更新方面研究不多。圖1 來(lái)自文獻(xiàn)1、3、4的原始數(shù)據(jù)，可以明顯的看出路網(wǎng)而無(wú)干擾國(guó)內(nèi)對(duì)于通過(guò)GPS軌跡挖掘新道路網(wǎng)的研究相對(duì)較少，大部分算法是將矢量軌跡數(shù)據(jù)轉(zhuǎn)換為柵格數(shù)據(jù)，然后利用圖像識(shí)別算法提取路網(wǎng)，方法簡(jiǎn)單高效，但只適用于那些特征明顯的軌跡的數(shù)據(jù)。由于這類(lèi)算法完全拋棄了矢量數(shù)據(jù)的優(yōu)點(diǎn)，在面對(duì)VGI時(shí)就顯得束手無(wú)措。值得注意的是國(guó)內(nèi)學(xué)者(陳琦，2011，廖順華，2007)在這方面開(kāi)展的一些研究。這些研究多針對(duì)傳統(tǒng)的路網(wǎng)采集方式，得到的GPS軌跡由專(zhuān)門(mén)的GPS裝置采集得到，數(shù)據(jù)量小，用來(lái)更新專(zhuān)

6、門(mén)的路段，比如陳漪的立交橋識(shí)別，實(shí)用性相對(duì)較小。為了解決上述存在的問(wèn)題，本文設(shè)計(jì)了一個(gè)用于挖掘步行GPS軌跡的并行算法。首先，需要先研究一下VGI數(shù)據(jù)。研究區(qū)數(shù)據(jù)實(shí)驗(yàn)研究區(qū)來(lái)自安徽省合肥市市區(qū)的一部分，周長(zhǎng)約20.12公里，面積約23.68平方公里。由于是在市區(qū)，道路網(wǎng)比較密集，人流量巨大，所以路網(wǎng)的更新對(duì)于這個(gè)地區(qū)來(lái)說(shuō)顯得尤為重要。同時(shí)也從百度公司獲得了以前的舊路網(wǎng)數(shù)據(jù)。圖2 研究區(qū)的路網(wǎng)數(shù)據(jù)(未經(jīng)更新)整體上看，大部分的道路網(wǎng)數(shù)據(jù)是正確的，但局部存在很多偏差(圖4)。圖3 路網(wǎng)與現(xiàn)實(shí)路網(wǎng)中的不匹配本次實(shí)驗(yàn)的VGI數(shù)據(jù)采集部分模仿了OpenStreetMap的路網(wǎng)數(shù)據(jù)采集方式，但是更加突出了

7、行人步行軌跡的無(wú)規(guī)律性，讓志愿者在研究區(qū)域攜帶GPS走動(dòng)，總共采集了將近10萬(wàn)條數(shù)據(jù)(圖4)。圖4 10萬(wàn)條軌跡數(shù)據(jù)整個(gè)實(shí)驗(yàn)區(qū)域的整體路網(wǎng)肉眼還是能夠清晰辨認(rèn)，但不同于以往專(zhuān)門(mén)采集的地理數(shù)據(jù)，路網(wǎng)存在很多錯(cuò)誤路徑和軌跡的不均勻分布。通過(guò)觀察圖的具體細(xì)節(jié)，可以看出步行軌跡不同于車(chē)輛軌跡的特點(diǎn)如下：(1)可以在統(tǒng)計(jì)意義上看出路網(wǎng)的形狀，但由于不是專(zhuān)門(mén)采集的數(shù)據(jù)，軌跡的方向幾乎可以說(shuō)毫無(wú)規(guī)律(圖6);(2)步行軌跡的終點(diǎn)容易集聚在一個(gè)地點(diǎn)，這些地點(diǎn)往往是一個(gè)景點(diǎn)入口，或者一個(gè)商城;(3) 由于步行的隨意性，道路兩旁很容易出現(xiàn)一些不是路網(wǎng)的稀疏路線;(4) 軌跡分布不均勻尤為明顯;(5) 更為重要的是

8、步行者的軌跡不僅僅會(huì)出現(xiàn)一些交通路網(wǎng)上，還有可能出現(xiàn)在其他可以自由步行的場(chǎng)合，比如操場(chǎng)。圖5 局部數(shù)據(jù)放大圖算法流程1.道格拉斯-普克線簡(jiǎn)化算法在本試驗(yàn)中，算法預(yù)處理步驟是后續(xù)步驟能否有效運(yùn)行的關(guān)鍵步驟。面對(duì)海量的步行軌跡數(shù)據(jù)，首先就是要將其中的不穩(wěn)定和錯(cuò)誤因素盡可能去除掉。一些經(jīng)常在數(shù)據(jù)中出現(xiàn)的軌跡錯(cuò)誤有下面幾個(gè)：(1) 不可估性。由于定位的不準(zhǔn)確，一些軌跡會(huì)偏離原本的道路。(2) 冗余性。步行軌跡的隨意性決定了一些軌跡會(huì)有自身的一些重復(fù)。(3) 跳躍性。志愿者GPS軌跡的不穩(wěn)定性，導(dǎo)致一些軌跡出現(xiàn)很奇 怪的轉(zhuǎn)彎或者跳躍。類(lèi)似橫穿街區(qū)，在非道路的地方的軌跡走動(dòng)。(4) 稀疏性。一些道路由于穿

9、過(guò)社區(qū)，或者由于采樣間隔的原因，使得軌跡點(diǎn)往往比較稀疏，但仍可能是一條步行道路。對(duì)于上述問(wèn)題，首先采用一種叫道格拉斯-普克線簡(jiǎn)化的算法對(duì)數(shù)據(jù)進(jìn)行處理。道格拉斯-普克算法(DouglasPeucker algorithm)，亦稱(chēng)為拉默-道格拉斯-普克算法、迭代適應(yīng)點(diǎn)算法或分裂與合并算法。該算法是將曲線近似表示為一系列點(diǎn)，以減少點(diǎn)的數(shù)量。道格拉斯-普克算法處理效果的關(guān)鍵就是閾值的選擇，本次實(shí)驗(yàn)綜合考慮各個(gè)因素，選取一般道路正常寬度的50%作為閾值，得到經(jīng)過(guò)線簡(jiǎn)化后的行人軌跡數(shù)據(jù)。線簡(jiǎn)化一方面糾正了一些行人軌跡的數(shù)據(jù)的軌跡錯(cuò)誤，另一方面也降低了數(shù)據(jù)量。2.細(xì)碎線段刪除在實(shí)驗(yàn)數(shù)據(jù)中能夠看到一些小的細(xì)碎

10、的線段，這些線段往往是沒(méi)有意義的，在大數(shù)據(jù)量的前提下，這些數(shù)據(jù)的刪除基本不會(huì)影響結(jié)果，而且還能減少帶來(lái)的誤差，降低數(shù)據(jù)量。本文取道路一般寬度的兩倍為閾值，將那些小于閾值的小線段從圖中剔除。算法并行遍歷每一條軌跡，計(jì)算軌跡長(zhǎng)度，如果長(zhǎng)度小于閾值，那么就將這條線段從數(shù)據(jù)中刪除。3. R樹(shù)索引由于需要匹配大量的軌跡數(shù)據(jù)，所以首先需要做的就是對(duì)道路數(shù)據(jù)建立空間索引。在GIS系統(tǒng)中，空間索引技術(shù)就是通過(guò)更加有效的組織方式，抽取與空間定位相關(guān)的信息組成對(duì)原空間數(shù)據(jù)的索引，以較小的數(shù)據(jù)量管理大量數(shù)據(jù)的查詢，從而提高空間查詢的效率和空間定位的準(zhǔn)確性。空間索引的方式很多17，大致有網(wǎng)格索引、R樹(shù)、K-D樹(shù)和四叉

11、樹(shù)等。本實(shí)驗(yàn)采用了R樹(shù)索引。R樹(shù)在數(shù)據(jù)庫(kù)等領(lǐng)域的功績(jī)非常顯著，很好得解決了高維空間搜索等問(wèn)題。R樹(shù)是B樹(shù)在高維空間的擴(kuò)展，是一棵平衡樹(shù)。每個(gè)R樹(shù)的葉子結(jié)點(diǎn)包含了多個(gè)指向不同數(shù)據(jù)的指針，這些數(shù)據(jù)可以是存放在硬盤(pán)中的，也可以是存在內(nèi)存中。4. 刪除已經(jīng)廢棄或不存在的路段依次對(duì)道路數(shù)據(jù)和軌跡數(shù)據(jù)建立R樹(shù)索引之后，首先要做的就是更新現(xiàn)有路網(wǎng)找到其中不存在的路網(wǎng)，把它刪除，刪除的目的一方面是為了減少數(shù)據(jù)的計(jì)算量，另一方面就是為以后的匹配減少?gòu)澛?，?jiǎn)化匹配的難度，讓軌跡點(diǎn)不會(huì)匹配到不存在的路上，思路很簡(jiǎn)單，只要分別遍歷路網(wǎng)，查詢周?chē)能壽E數(shù)據(jù)，如果軌跡數(shù)據(jù)小于一定的閾值，就可以把這段刪除。至于這個(gè)閾值怎么

12、定，往往需要一定的統(tǒng)計(jì)知識(shí)，本實(shí)驗(yàn)采用了總數(shù)據(jù)的2萬(wàn)分之一，即20條為臨界值，得出去除無(wú)效道路后的路網(wǎng)。5. 軌跡匹配經(jīng)過(guò)精簡(jiǎn)之后，計(jì)算的數(shù)據(jù)量就可以減少，同時(shí)也可以進(jìn)行軌跡匹配。軌跡匹配的大致過(guò)程是遍歷每一條軌跡，對(duì)每一條軌跡的每一個(gè)點(diǎn)在一定范圍進(jìn)行搜索，類(lèi)似對(duì)點(diǎn)做一個(gè)一定半徑長(zhǎng)的緩沖區(qū)，搜索在緩沖區(qū)內(nèi)的道路。如果搜索不到，則該點(diǎn)不做變化;如果搜索到一條道路，則將它匹配到該點(diǎn)到該道路的垂足上。偽算法：For each Trace t in VGIData DoFor each Point p in t DoResult=Search Roads within SomeDistanceIf R

13、esult.Count=0Do NoThingElse p=p. perpendicular(Result)End IfEnd ForEnd ForReturn new VGIData該算法主要思想正確，耗時(shí)也比較短。在本次試驗(yàn)的機(jī)器上，大約用時(shí)半分鐘便完成了對(duì)100,000條數(shù)據(jù)(處理過(guò)后大約50,000條)的處理。但處理結(jié)果雖然比起源數(shù)據(jù)已經(jīng)好很多，但是并不是令人滿意的(圖7)圖7 藍(lán)色為匹配生成的結(jié)果，下方為局部效果圖上可以看到大致明顯的道路輪廓已經(jīng)顯現(xiàn)，但是一旦放到局部就會(huì)出現(xiàn)軌跡在道路之間隨意“穿梭”的現(xiàn)象，原因顯而易見(jiàn)，就是如果點(diǎn)靠近兩條道路時(shí)候，由于一些誤差，導(dǎo)致點(diǎn)看上去離自己原

14、本那條路線更遠(yuǎn)，導(dǎo)致匹配到了另外一條道路上。這種現(xiàn)象會(huì)出現(xiàn)在平行的兩條道路上，也會(huì)出現(xiàn)在兩條路合并的路口。這個(gè)錯(cuò)誤是影響匹配結(jié)果的關(guān)鍵因素。這也是地圖匹配要完成的核心任務(wù)。對(duì)于這種錯(cuò)誤，解決的辦法就是當(dāng)距離容差內(nèi)找到的道路超過(guò)兩條時(shí)，在進(jìn)行地圖匹配時(shí)可以參考先前匹配過(guò)的點(diǎn)的方向，根據(jù)方向調(diào)整匹配的道路，匹配時(shí)本次實(shí)驗(yàn)采取利用下面的條件進(jìn)行匹配：如果一個(gè)點(diǎn)容差D之內(nèi)有兩個(gè)以上的匹配道路，那么這個(gè)點(diǎn)匹配到Max(0.8*方向因子+0.2*距離因子)的道路上。其中方向因子=0.5-三點(diǎn)形成的夾角余弦/2,距離因子=1-距離/D，如果前一點(diǎn)為空，方向因子=0。另外在匹配的時(shí)候要注意一些細(xì)節(jié)，由于在行人

15、軌跡的隨意性，一些行人的軌跡點(diǎn)并不在路上，如果錯(cuò)誤地將這些點(diǎn)匹配到兩旁的道路上，往往容易出現(xiàn)一些匹配錯(cuò)誤。匹配的結(jié)果如下(圖8)：圖8 匹配結(jié)果圖6.道路提取為了找出新的軌跡，可以用匹配后的軌跡與刪減后的路網(wǎng)做一個(gè)減法運(yùn)算，對(duì)于匹配后的軌跡的每一線段進(jìn)行判斷，判斷它是否在當(dāng)前路網(wǎng)內(nèi)，如果不在，則將其保留。判斷的條件有兩個(gè)：·沒(méi)有任何路網(wǎng)與其有交點(diǎn)，這種比較少見(jiàn)。·線段的一端與原路網(wǎng)的交點(diǎn)很多而另一端則沒(méi)有交點(diǎn)，表明這是在原路網(wǎng)上拓建的路，是新路網(wǎng)。這種情況占大多數(shù)。找出的新軌跡中有很多平行的道路，顯然這些指向同一條道路，因此需要將這些道路合并為一條道路。合并這些道路的算法思

16、路很簡(jiǎn)單，即找到那些平行的、相鄰的線段，將這些線段合并為一條線段，該條線段將位于這些線段的中間，并且斜率的大小為這些線段角度的平均值?；緜未a如下：List VisitedLine,FeatureSet NewWays,FeatureSet outPut;For Each Line in NewWaysIf (line.Fid Exsit in VisitedLine)Continue;End IfList FindIntersectRoad=NewWays.Intersect(line.Buffer(0.001);If (FindIntersectRoad.Length>=2)Lis

17、t SimilarRoads=FindIntersectRoad.FindAll(Where Element in it Whose Angleline.Angle);LineString newLine=SimilarRoads.MiddleLine;outPut.Add(newLine);ElseoutPut.Add(line);End IfEnd For通過(guò)上面的思路，得到了最終生成的新路網(wǎng)(圖9)。圖9 最終生成的新路網(wǎng)結(jié)果分析與討論圖10 最終生成的新路網(wǎng)細(xì)節(jié)比對(duì)上圖(圖10)列出了一些匹配正確的結(jié)果，這些新提取的道路已經(jīng)很好的匹配到了現(xiàn)實(shí)中道路，達(dá)到了預(yù)期的目標(biāo)，并且整個(gè)流程借助于索引與并行技術(shù)，耗時(shí)非常短，處理10萬(wàn)條數(shù)據(jù)包括預(yù)處理大概用時(shí)35s,這是非常高效的。本文針對(duì)大數(shù)據(jù)量的步行軌跡數(shù)據(jù)，提出一個(gè)從志愿者GPS軌跡中提取路網(wǎng)的初步解決方案。該方案首先運(yùn)用一些幾何算法對(duì)