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

蔣宗禮+李娟

摘 要：借助OpenStreetMap （以下簡(jiǎn)稱OSM）開(kāi)源組織，分析研究了OSM相關(guān)的數(shù)據(jù)結(jié)構(gòu)和使用方法，構(gòu)建了地圖服務(wù)系統(tǒng)，為研究地圖匹配算法提供了基礎(chǔ)。通過(guò)研究地圖匹配算法，實(shí)現(xiàn)了基于幾何投影法的地圖匹配研究項(xiàng)目，為進(jìn)行更復(fù)雜的地圖匹配算法研究提供了依據(jù)。

關(guān)鍵詞：地圖匹配算法；開(kāi)源地圖數(shù)據(jù)；地圖數(shù)據(jù)服務(wù)系統(tǒng)；OpenStreetMap；地圖匹配系統(tǒng)

DOIDOI：10.11907/rjdk.171147

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）007-0052-03

0 引言

隨著計(jì)算機(jī)的普及以及地理信息科學(xué)的發(fā)展，地理信息系統(tǒng)（ Geographic Information System，GIS）得到了廣泛應(yīng)用，在電子導(dǎo)航、交通旅游、城市規(guī)劃以及電力、通訊等管網(wǎng)、管線布局設(shè)計(jì)中發(fā)揮了重要作用[1]。

地圖服務(wù)是國(guó)家安全資源[2]，傳統(tǒng)的地圖匹配算法[3]，由于沒(méi)有地圖數(shù)據(jù)資源，大都利用模型進(jìn)行驗(yàn)證，實(shí)際應(yīng)用效果不佳。OpenStreetMap不僅開(kāi)放了地圖數(shù)據(jù)資源，還提供了許多工具來(lái)構(gòu)建完善的地圖服務(wù)系統(tǒng)，對(duì)深入研究地圖匹配算法提供了良好支撐。

1 地圖基礎(chǔ)服務(wù)構(gòu)建

地理數(shù)據(jù)構(gòu)建是地圖服務(wù)的基礎(chǔ)。然而，地理數(shù)據(jù)一般都加密不對(duì)外公開(kāi) [4]。迄今為止，數(shù)字地圖市場(chǎng)被控制，開(kāi)發(fā)人員只能通過(guò)付費(fèi)購(gòu)買有限的地圖數(shù)據(jù)使用權(quán)[5]。互聯(lián)網(wǎng)技術(shù)的發(fā)展提供了很多基于地圖服務(wù)的開(kāi)放平臺(tái)，如Google地圖、百度地圖、高德地圖、騰訊地圖等，但是這些服務(wù)非常有限，用戶通過(guò)服務(wù)接口只能得到有限的數(shù)據(jù)服務(wù)，這對(duì)基于地圖服務(wù)的研究帶來(lái)了很大的局限性。

OSM是一個(gè)網(wǎng)上地圖協(xié)作計(jì)劃，目標(biāo)是創(chuàng)造一個(gè)能自由獲取內(nèi)容且能編輯的世界地圖，是當(dāng)今最精確和完善的矢量地圖數(shù)據(jù)集[1]。OSM的數(shù)據(jù)開(kāi)源，可以自由下載使用，人們可以通過(guò)OSM的規(guī)范來(lái)構(gòu)建自己的地圖電子數(shù)據(jù)庫(kù)，構(gòu)建自己的路網(wǎng)信息服務(wù)系統(tǒng)。

1.1 OSM數(shù)據(jù)結(jié)構(gòu)

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

與北京工業(yè)大學(xué)附近路網(wǎng)信息地圖相對(duì)應(yīng)的OSM文檔實(shí)例元數(shù)據(jù)部分內(nèi)容如下：

從OSM文件可以看到一個(gè)relation包含了很多的member，每個(gè)member可以是單獨(dú)的節(jié)點(diǎn)，也可以是一條新的道路信息。一個(gè)個(gè)node、way和relation共同組成了路網(wǎng)信息。

1.2 OSM應(yīng)用

OSM是一種類似XML格式的文件，可以解析OSM文件獲取相應(yīng)的數(shù)據(jù)信息。參考文獻(xiàn)[1]采用正則表達(dá)式來(lái)實(shí)現(xiàn)此功能，做法是提取way中的數(shù)據(jù)信息， node和relation信息也必須解析利用。OSM不僅僅是數(shù)據(jù)服務(wù)的開(kāi)源，還提供了許多可利用的開(kāi)源工具幫助解析OSM，Osmapi就是其中一種。Osmapi是一種針對(duì)OSM結(jié)構(gòu)的解析工具，能夠解析并獲取OSM文件中的數(shù)據(jù)信息，有著完善的功能服務(wù)。除此之外，OSM還提供了很多開(kāi)源工具供開(kāi)發(fā)者利用，具體參考http：//wiki.openstreetmap.org/wiki/Frameworks。關(guān)于Osmapi的資料比較少，這里只對(duì)其進(jìn)行簡(jiǎn)單的事例說(shuō)明：

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

de.westnordost

osmapi

1.4

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

2 地圖匹配算法設(shè)計(jì)與實(shí)現(xiàn)

地圖匹配是一種通過(guò)軟件方法校正導(dǎo)航定位誤差的技術(shù)。建立數(shù)據(jù)模型，將GPS位置信息轉(zhuǎn)化為矢量地圖的坐標(biāo)位置信息，從而將地圖和GPS坐標(biāo)點(diǎn)相匹配，形成地圖匹配功能。本文以最實(shí)用的幾何投影法進(jìn)行地圖匹配實(shí)現(xiàn)。

2.1 候選路段選取法

獲取GPS位置信息后，需要從整個(gè)路網(wǎng)拓?fù)湫畔⒅蝎@得候選路段。路網(wǎng)拓?fù)湫畔⒌臄?shù)據(jù)量非常龐大，獲取候選路段信息需要與每個(gè)路段進(jìn)行最短距離計(jì)算。為了快速實(shí)現(xiàn)路段匹配，采用geohash算法，為路網(wǎng)拓?fù)湫畔澐志W(wǎng)格。當(dāng)GPS位置確定后，可找出網(wǎng)格中的相關(guān)路段進(jìn)行計(jì)算，避免了多余節(jié)點(diǎn)的計(jì)算量，原理見(jiàn)圖2。

如圖2所示，每個(gè)網(wǎng)格對(duì)應(yīng)一個(gè)唯一編號(hào)（0000，0001…），根據(jù)路網(wǎng)的經(jīng)緯度劃分得到，這個(gè)編號(hào)稱為geocode。每個(gè)網(wǎng)格中都有路網(wǎng)數(shù)據(jù)，每段路網(wǎng)數(shù)據(jù)記錄在網(wǎng)格編號(hào)中。當(dāng)?shù)玫紾PS位置信息時(shí)，首先獲取GPS網(wǎng)格編號(hào)，通過(guò)網(wǎng)格編號(hào)查詢?cè)摼W(wǎng)格中相關(guān)路段有哪些，然后在計(jì)算GPS位置與當(dāng)前路段的最短路徑時(shí)獲取候選路段。

2.2 投影法匹配定位點(diǎn)

獲取候選路段后，如果要找到P點(diǎn)所在的路段及其所處的位置，可根據(jù)投影法進(jìn)行匹配點(diǎn)計(jì)算，見(jiàn)圖3。

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

地圖匹配過(guò)程：準(zhǔn)備候選集，計(jì)算候選路段，確定最終路段，運(yùn)行幾何匹配算法，確定匹配位置。

（1）讀取OSM地圖數(shù)據(jù)，構(gòu)建路網(wǎng)拓?fù)湫畔L。路段信息用Ri表示，i表示路段編號(hào)。Ri中保存本路段的所有坐標(biāo)點(diǎn)信息。設(shè)置表示位FLAG用來(lái)表示當(dāng)前行駛路段RT是否確認(rèn)。

（2）利用geohash算法劃分路網(wǎng)，給每個(gè)路段信息Ri添加geocode編號(hào)屬性，表示該路段所在的geohash區(qū)域可以包含多個(gè)geocode。參照候選路段選取法進(jìn)行g(shù)eohash區(qū)域劃分。

（3）獲取當(dāng)前的GPS位置坐標(biāo)點(diǎn)P，讀取標(biāo)志位FLAG，判斷路網(wǎng)信息是否確認(rèn)。如果確認(rèn)直接跳轉(zhuǎn)步驟（5），否則繼續(xù)步驟（4）。

（4）根據(jù)坐標(biāo)點(diǎn)P計(jì)算出該坐標(biāo)點(diǎn)的geocode，根據(jù)geocode找出相關(guān)的候選路段信息。利用最短距離法，計(jì)算當(dāng)前P點(diǎn)到各個(gè)路段的最短距離信息，確認(rèn)當(dāng)前行駛路段RT，修改標(biāo)志位FLAG。

（5）應(yīng)用地圖匹配算法計(jì)算P點(diǎn)到當(dāng)前道路軌跡的匹配點(diǎn)。

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

3 實(shí)驗(yàn)

本文通過(guò)分析OSM的數(shù)據(jù)結(jié)構(gòu)以及OSM的使用方法，利用Osmapi解析獲取OSM中的路網(wǎng)信息數(shù)據(jù)，實(shí)現(xiàn)了簡(jiǎn)易的路網(wǎng)信息服務(wù)系統(tǒng)。通過(guò)分析地圖匹配算法，借助OSM提供的地圖數(shù)據(jù)服務(wù)實(shí)現(xiàn)了基于幾何投影法的地圖匹配算法。為了驗(yàn)證實(shí)現(xiàn)效果，采用一段GPS軌跡信息，如圖4所示，該GPS位置信息坐標(biāo)點(diǎn)為車輛行駛軌跡，表現(xiàn)出沒(méi)有匹配到道路的誤差樣本，期望利用OSM實(shí)現(xiàn)的地圖匹配系統(tǒng)來(lái)進(jìn)行修正。圖中紅色帶箭頭的軌跡路徑為未經(jīng)過(guò)匹配的行駛軌跡。

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

4 結(jié)語(yǔ)

本文通過(guò)研究OSM的數(shù)據(jù)結(jié)構(gòu)和使用方法，構(gòu)建了地圖服務(wù)系統(tǒng)，能夠提供地圖相關(guān)的應(yīng)用和計(jì)算。實(shí)現(xiàn)了基于幾何投影法的地圖匹配系統(tǒng)，能夠?qū)④囕v的行駛軌跡匹配到正確的道路中。但幾何投影法的地圖匹配過(guò)程還不是很精確，存在很多需要改進(jìn)的地方。更加精確的地圖匹配算法是今后努力的方向。

參考文獻(xiàn)：

[1] 張英輝，張水平，張鳳琴，等.基于OpenStreetMap 最短路徑算法的分析與實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（11）：36-41.

[2] 張絳麗，張笑非，徐丹，等.基于OpenStreetMap 的智能交通路網(wǎng)數(shù)據(jù)的構(gòu)建 [J].2014，14（1）：41-47.

[3] 陸文昌，張迎，陳龍，等.基于計(jì)算幾何的地圖匹配算法研究[J].機(jī)械設(shè)計(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] 趙東保，劉雪梅，郭黎.網(wǎng)格索引支持下的大規(guī)模浮動(dòng)車實(shí)時(shí)地圖匹配方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，26（9）：1550-1556.

[7] 肖維麗，岳春生，奚玲.基于高程的改進(jìn)D.s證據(jù)理論地圖匹配算法[J].計(jì)算機(jī)應(yīng)用與軟件，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軌跡數(shù)據(jù)的地圖匹配算法[J].測(cè)繪學(xué)報(bào)，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] 曹凱，唐進(jìn)軍，劉汝成.基于Fr6chet距離準(zhǔn)則的智能地圖匹配算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（2）：223-226.

[12] 雷健.基于分布式架構(gòu)的智能車輛管理系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].杭州：浙江大學(xué)，2015.