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

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

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

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

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

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

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

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

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

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

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

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

12、定，往往需要一定的統(tǒng)計知識，本實驗采用了總數(shù)據(jù)的2萬分之一，即20條為臨界值，得出去除無效道路后的路網(wǎng)。5. 軌跡匹配經(jīng)過精簡之后，計算的數(shù)據(jù)量就可以減少，同時也可以進行軌跡匹配。軌跡匹配的大致過程是遍歷每一條軌跡，對每一條軌跡的每一個點在一定范圍進行搜索，類似對點做一個一定半徑長的緩沖區(qū)，搜索在緩沖區(qū)內(nèi)的道路。如果搜索不到，則該點不做變化;如果搜索到一條道路，則將它匹配到該點到該道路的垂足上。偽算法：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該算法主要思想正確，耗時也比較短。在本次試驗的機器上，大約用時半分鐘便完成了對100,000條數(shù)據(jù)(處理過后大約50,000條)的處理。但處理結果雖然比起源數(shù)據(jù)已經(jīng)好很多，但是并不是令人滿意的(圖7)圖7 藍色為匹配生成的結果，下方為局部效果圖上可以看到大致明顯的道路輪廓已經(jīng)顯現(xiàn)，但是一旦放到局部就會出現(xiàn)軌跡在道路之間隨意“穿梭”的現(xiàn)象，原因顯而易見，就是如果點靠近兩條道路時候，由于一些誤差，導致點看上去離自己原

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

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

16、路很簡單，即找到那些平行的、相鄰的線段，將這些線段合并為一條線段，該條線段將位于這些線段的中間，并且斜率的大小為這些線段角度的平均值。基本偽代碼如下：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通過上面的思路，得到了最終生成的新路網(wǎng)(圖9)。圖9 最終生成的新路網(wǎng)結果分析與討論圖10 最終生成的新路網(wǎng)細節(jié)比對上圖(圖10)列出了一些匹配正確的結果，這些新提取的道路已經(jīng)很好的匹配到了現(xiàn)實中道路，達到了預期的目標，并且整個流程借助于索引與并行技術，耗時非常短，處理10萬條數(shù)據(jù)包括預處理大概用時35s,這是非常高效的。本文針對大數(shù)據(jù)量的步行軌跡數(shù)據(jù)，提出一個從志愿者GPS軌跡中提取路網(wǎng)的初步解決方案。該方案首先運用一些幾何算法對