基于OpenStreetMap的地圖匹配算法研究

蔣宗禮+李娟

摘 要：借助OpenStreetMap （以下簡稱OSM）開源組織，分析研究了OSM相關的數據結構和使用方法，構建了地圖服務系統，為研究地圖匹配算法提供了基礎。通過研究地圖匹配算法，實現了基于幾何投影法的地圖匹配研究項目，為進行更復雜的地圖匹配算法研究提供了依據。

關鍵詞：地圖匹配算法；開源地圖數據；地圖數據服務系統；OpenStreetMap；地圖匹配系統

DOIDOI：10.11907/rjdk.171147

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2017）007-0052-03

0 引言

隨著計算機的普及以及地理信息科學的發展，地理信息系統（ Geographic Information System，GIS）得到了廣泛應用，在電子導航、交通旅游、城市規劃以及電力、通訊等管網、管線布局設計中發揮了重要作用[1]。

地圖服務是國家安全資源[2]，傳統的地圖匹配算法[3]，由于沒有地圖數據資源，大都利用模型進行驗證，實際應用效果不佳。OpenStreetMap不僅開放了地圖數據資源，還提供了許多工具來構建完善的地圖服務系統，對深入研究地圖匹配算法提供了良好支撐。

1 地圖基礎服務構建

地理數據構建是地圖服務的基礎。然而，地理數據一般都加密不對外公開 [4]。迄今為止，數字地圖市場被控制，開發人員只能通過付費購買有限的地圖數據使用權[5]。互聯網技術的發展提供了很多基于地圖服務的開放平臺，如Google地圖、百度地圖、高德地圖、騰訊地圖等，但是這些服務非常有限，用戶通過服務接口只能得到有限的數據服務，這對基于地圖服務的研究帶來了很大的局限性。

OSM是一個網上地圖協作計劃，目標是創造一個能自由獲取內容且能編輯的世界地圖，是當今最精確和完善的矢量地圖數據集[1]。OSM的數據開源，可以自由下載使用，人們可以通過OSM的規范來構建自己的地圖電子數據庫，構建自己的路網信息服務系統。

1.1 OSM數據結構

OSM提供了路網信息數據服務，是一種類似于XML結構的文檔數據類型，包含3種空間數據類型節點，分別是node、way和relation，構成了整個地圖畫面[4]。圖1是一張OSM描繪的北京工業大學附近的路網地圖。從中可以比較清楚地看到路網信息的組織方式，以及每個節點、道路和建筑物等。成千上萬的節點信息如果用一個way進行保存數據會很大，不方便計算，可將way拆分，用relation關聯。關于node、way和relation這3種類型的節點，參考文獻[1]中進行了詳細描述。

與北京工業大學附近路網信息地圖相對應的OSM文檔實例元數據部分內容如下：

從OSM文件可以看到一個relation包含了很多的member，每個member可以是單獨的節點，也可以是一條新的道路信息。一個個node、way和relation共同組成了路網信息。

1.2 OSM應用

OSM是一種類似XML格式的文件，可以解析OSM文件獲取相應的數據信息。參考文獻[1]采用正則表達式來實現此功能，做法是提取way中的數據信息， node和relation信息也必須解析利用。OSM不僅僅是數據服務的開源，還提供了許多可利用的開源工具幫助解析OSM，Osmapi就是其中一種。Osmapi是一種針對OSM結構的解析工具，能夠解析并獲取OSM文件中的數據信息，有著完善的功能服務。除此之外，OSM還提供了很多開源工具供開發者利用，具體參考http：//wiki.openstreetmap.org/wiki/Frameworks。關于Osmapi的資料比較少，這里只對其進行簡單的事例說明：

可直接通過maven使用Osmapi。在pom文件中添加如下引用：

de.westnordost

osmapi

1.4

利用Osmapi解析OSM數據文件具體代碼可參考OSM官方網址： http：//wiki.openstreetmap.org/wiki/Java_Access_Example，其中給出了Osmapi的使用方法。

2 地圖匹配算法設計與實現

地圖匹配是一種通過軟件方法校正導航定位誤差的技術。建立數據模型，將GPS位置信息轉化為矢量地圖的坐標位置信息，從而將地圖和GPS坐標點相匹配，形成地圖匹配功能。本文以最實用的幾何投影法進行地圖匹配實現。

2.1 候選路段選取法

獲取GPS位置信息后，需要從整個路網拓撲信息中獲得候選路段。路網拓撲信息的數據量非常龐大，獲取候選路段信息需要與每個路段進行最短距離計算。為了快速實現路段匹配，采用geohash算法，為路網拓撲信息劃分網格。當GPS位置確定后，可找出網格中的相關路段進行計算，避免了多余節點的計算量，原理見圖2。

如圖2所示，每個網格對應一個唯一編號（0000，0001…），根據路網的經緯度劃分得到，這個編號稱為geocode。每個網格中都有路網數據，每段路網數據記錄在網格編號中。當得到GPS位置信息時，首先獲取GPS網格編號，通過網格編號查詢該網格中相關路段有哪些，然后在計算GPS位置與當前路段的最短路徑時獲取候選路段。

2.2 投影法匹配定位點

獲取候選路段后，如果要找到P點所在的路段及其所處的位置，可根據投影法進行匹配點計算，見圖3。

2.3 幾何法地圖匹配算法描述

地圖匹配過程：準備候選集，計算候選路段，確定最終路段，運行幾何匹配算法，確定匹配位置。

（1）讀取OSM地圖數據，構建路網拓撲信息RL。路段信息用Ri表示，i表示路段編號。Ri中保存本路段的所有坐標點信息。設置表示位FLAG用來表示當前行駛路段RT是否確認。

（2）利用geohash算法劃分路網，給每個路段信息Ri添加geocode編號屬性，表示該路段所在的geohash區域可以包含多個geocode。參照候選路段選取法進行geohash區域劃分。

（3）獲取當前的GPS位置坐標點P，讀取標志位FLAG，判斷路網信息是否確認。如果確認直接跳轉步驟（5），否則繼續步驟（4）。

（4）根據坐標點P計算出該坐標點的geocode，根據geocode找出相關的候選路段信息。利用最短距離法，計算當前P點到各個路段的最短距離信息，確認當前行駛路段RT，修改標志位FLAG。

（5）應用地圖匹配算法計算P點到當前道路軌跡的匹配點。

（6）將匹配后的點輸出，描繪到地圖道路軌跡中。

3 實驗

本文通過分析OSM的數據結構以及OSM的使用方法，利用Osmapi解析獲取OSM中的路網信息數據，實現了簡易的路網信息服務系統。通過分析地圖匹配算法，借助OSM提供的地圖數據服務實現了基于幾何投影法的地圖匹配算法。為了驗證實現效果，采用一段GPS軌跡信息，如圖4所示，該GPS位置信息坐標點為車輛行駛軌跡，表現出沒有匹配到道路的誤差樣本，期望利用OSM實現的地圖匹配系統來進行修正。圖中紅色帶箭頭的軌跡路徑為未經過匹配的行駛軌跡。

從圖5可以看出，地圖匹配過程基本可以將車輛的行駛軌跡匹配到正確的道路上去。但是幾何地圖匹配算法存在一定的不精確性，實驗過程中仍會存在誤差。

4 結語

本文通過研究OSM的數據結構和使用方法，構建了地圖服務系統，能夠提供地圖相關的應用和計算。實現了基于幾何投影法的地圖匹配系統，能夠將車輛的行駛軌跡匹配到正確的道路中。但幾何投影法的地圖匹配過程還不是很精確，存在很多需要改進的地方。更加精確的地圖匹配算法是今后努力的方向。

參考文獻：

[1] 張英輝，張水平，張鳳琴，等.基于OpenStreetMap 最短路徑算法的分析與實現[J].計算機技術與發展，2013，23（11）：36-41.

[2] 張絳麗，張笑非，徐丹，等.基于OpenStreetMap 的智能交通路網數據的構建 [J].2014，14（1）：41-47.

[3] 陸文昌，張迎，陳龍，等.基于計算幾何的地圖匹配算法研究[J].機械設計與制造，2012 （1）：43-45.

[4] HASHEMI M，KARIMI H.A critical review of real-timemap matching algorithms：current issues and future directions[J].Computers，Environment and Urban Systems，2015（11）：153-165.

[5] QUDDUS M，WASHINGTON S.Shortest path and vehicletrajectory aided map—matching for low frequency GPSdata[J].Transportation Research Part C：Emerging Technologies，2015（6）：328-339.

[6] 趙東保，劉雪梅，郭黎.網格索引支持下的大規模浮動車實時地圖匹配方法[J].計算機輔助設計與圖形學學報，2014，26（9）：1550-1556.

[7] 肖維麗，岳春生，奚玲.基于高程的改進D.s證據理論地圖匹配算法[J].計算機應用與軟件，2015（3）：262-265.

[8] YANG J，MENG L.Feature selection in conditional random fields for map matching of GPS trajectories[J].Springer International Publishing，2015，23（4）：121-135.

[9] 李清泉，黃練.基于GPS軌跡數據的地圖匹配算法[J].測繪學報，2010，39（2）：7-13.

[10] YIN H，WOLFSON O.A weight-based map matching method in moving objects databases[J].Proc Ssdbm Con 2004，16（5）：437-438.

[11] 曹凱，唐進軍，劉汝成.基于Fr6chet距離準則的智能地圖匹配算法[J].計算機工程與應用，2007，43（2）：223-226.

[12] 雷健.基于分布式架構的智能車輛管理系統設計與實現[D].杭州：浙江大學，2015.