一種利用網(wǎng)格劃分及方向加權(quán)的地圖匹配算法

廖 佳，俞薦中，李俊峰

(1. 寧波市測繪設(shè)計(jì)研究院，浙江 寧波 315042； 2. 寧波市規(guī)劃與地理信息中心，浙江 寧波 315042)

一種利用網(wǎng)格劃分及方向加權(quán)的地圖匹配算法

廖 佳1，俞薦中2，李俊峰1

(1. 寧波市測繪設(shè)計(jì)研究院，浙江 寧波 315042； 2. 寧波市規(guī)劃與地理信息中心，浙江 寧波 315042)

地圖匹配算法目的是將偏離道路的點(diǎn)糾正到正確位置上。本文基于傳統(tǒng)的點(diǎn)到線的地圖匹配算法，通過引入網(wǎng)格劃分的概念來確認(rèn)候選匹配道路，并且加權(quán)了方向因素來計(jì)算點(diǎn)到線的匹配程度。試驗(yàn)表明，改進(jìn)后的算法能夠提高其準(zhǔn)確性，并且一定程度上提高了算法的效率，具有一定的實(shí)用價(jià)值。

網(wǎng)格劃分；方向加權(quán)；地圖匹配

隨著移動(dòng)定位技術(shù)的發(fā)展及移動(dòng)定位終端的普及，每時(shí)每刻都積累著大量的定位數(shù)據(jù)。但由于定位精度的問題，必須將有誤差的數(shù)據(jù)進(jìn)行糾正，使其重新定位到正確的位置。地圖匹配算法正是為了解決這一問題而出現(xiàn)的。由于定位數(shù)據(jù)一般規(guī)模較大、道路數(shù)據(jù)也相對復(fù)雜，地圖匹配算法在準(zhǔn)確度與效率上很難達(dá)到理想的效果。本文通過網(wǎng)格劃分的思想，并加入方向權(quán)重，對傳統(tǒng)的點(diǎn)到線的匹配算法進(jìn)行改進(jìn)，成功提高了算法準(zhǔn)確度及效率。

1 地圖匹配基本理論

地圖匹配就是將偏離圖上道路的軌跡點(diǎn)數(shù)據(jù)糾正后，使其重新定位到正確的道路上的過程。由于出租車GPS采集到的位置點(diǎn)數(shù)據(jù)存在精度誤差，因此，軌跡點(diǎn)很可能偏離道路，落在不合理的地方，如道路旁的建筑物、廣場甚至河流湖泊等。而這樣的誤差對后期的數(shù)據(jù)挖掘工作有很大影響。因此，有必要對采集后的軌跡點(diǎn)數(shù)據(jù)進(jìn)行地圖匹配。

地圖匹配算法的一般步驟為：①確定車輛軌跡點(diǎn)所在的路段；②確定車輛軌跡點(diǎn)在該路段的具體位置。其中，確定車輛軌跡點(diǎn)所在路段最為關(guān)鍵。通常確定的原理是，在軌跡點(diǎn)的一定鄰域范圍內(nèi)搜索候選的待匹配道路，然后計(jì)算軌跡點(diǎn)與這些待匹配道路的匹配度(也稱為相似度)，最后選擇匹配度最大的路段作為匹配道路。典型的地圖匹配方法主要有以下幾種：

1.1 幾何分析法

幾何分析法又分為以下幾類：點(diǎn)到點(diǎn)的匹配，點(diǎn)到線的匹配，線到線的匹配。點(diǎn)到點(diǎn)的匹配，即搜索路網(wǎng)數(shù)據(jù)中所有的點(diǎn)，計(jì)算所有點(diǎn)與帶匹配點(diǎn)的距離，用距離最近點(diǎn)的坐標(biāo)替換帶匹配點(diǎn)原有的坐標(biāo)。點(diǎn)到點(diǎn)的匹配非常簡單便捷，幾乎是所有匹配算法中最簡單的。但是點(diǎn)到點(diǎn)的匹配與路段之間點(diǎn)的密集程度密切相關(guān)，當(dāng)出現(xiàn)路段長度較長且路段之間的點(diǎn)分布不多時(shí)，該算法的匹配精度大大降低。如圖1所示，P點(diǎn)應(yīng)該匹配到MN道路上，但是由于MN之間并沒有許多能夠匹配的點(diǎn)，而附近有一條相距更遠(yuǎn)的道路AG，并且P到點(diǎn)D上的距離最短，因此，按照點(diǎn)到點(diǎn)匹配算法，該點(diǎn)P將被匹配到AG道路上的D點(diǎn)位置上，由此產(chǎn)生了錯(cuò)誤匹配。

圖1 點(diǎn)到點(diǎn)匹配缺陷

點(diǎn)到線的匹配即計(jì)算待匹配點(diǎn)到候選匹配道路之間的距離，由最近距離確定匹配道路，而該點(diǎn)到道路的投影點(diǎn)即為匹配點(diǎn)。

該方法雖然與道路中間點(diǎn)的多少無關(guān)，但如果出現(xiàn)點(diǎn)到幾條道路距離相等，或十分接近的情況，也很難判斷應(yīng)該匹配到哪條道路上。如圖2所示，待匹配點(diǎn)P到道路A、B的距離相同，則無法判斷P應(yīng)該匹配到哪條道路上。

圖2 點(diǎn)到線匹配缺陷

線到線的匹配就是利用一段時(shí)間內(nèi)產(chǎn)生的點(diǎn)連成的軌跡線，與道路進(jìn)行擬合。擬合的標(biāo)準(zhǔn)是計(jì)算軌跡點(diǎn)連成的線與道路線之間的距離。而線與線的距離，通常有多種計(jì)算方法：①計(jì)算連續(xù)點(diǎn)之間的距離，求平均值；②兩條線函數(shù)相減求積分得到，公式如下

(1)

1.2 拓?fù)浞治龇?/p>

基于道路網(wǎng)的拓?fù)浞治龇椒ㄊ紫刃枰氖墙⒌缆肪W(wǎng)的拓?fù)潢P(guān)系。而所謂道路網(wǎng)的拓?fù)潢P(guān)系就是指節(jié)點(diǎn)、道路線、面之間的關(guān)系。拓?fù)浞治龇ㄊ紫雀鶕?jù)道路的拓?fù)潢P(guān)系及待匹配點(diǎn)的空間位置確定候選的匹配道路集合，然后通過歷史數(shù)據(jù)分析得到匹配道路。

1.3 基于概率統(tǒng)計(jì)算法

基于概率統(tǒng)計(jì)算法的基本思想是：根據(jù)對象的定位信息，將對象的實(shí)際位置確定在某一置信區(qū)間，根據(jù)接收到的GPS數(shù)據(jù)，將當(dāng)前對象所在位置確定在某一置信區(qū)域內(nèi)，依據(jù)已有的匹配結(jié)果的概率統(tǒng)計(jì)，經(jīng)過判斷后，確定GPS數(shù)據(jù)在這一置信區(qū)域內(nèi)的匹配道路。

2 網(wǎng)格及方向權(quán)重引入

本文研究的地圖匹配算法為幾何分析法中的點(diǎn)到線的匹配算法，該算法的匹配精確度并不高，且當(dāng)處理的數(shù)據(jù)集非常大時(shí)，匹配的效率也有一定問題。本文首先通過加入方向信息提高算法的匹配精確度，然后通過引入網(wǎng)格劃分的思想提高算法的效率。

2.1 結(jié)合方向信息的匹配度計(jì)算

傳統(tǒng)的點(diǎn)到線的匹配算法只考慮距離因素，而當(dāng)加入方向信息后，則能夠避免圖2中的錯(cuò)誤。引入匹配度概念，匹配度即表示點(diǎn)與道路的匹配程度，如圖3所示。

圖3 匹配度計(jì)算

匹配度的計(jì)算公式如下

M=φD+μL

(2)

式中，M表示匹配點(diǎn)與道路的匹配度；D表示標(biāo)準(zhǔn)化距離因子；L表示標(biāo)準(zhǔn)化后方向因子；φ表示距離權(quán)重；μ表示方向權(quán)重，權(quán)重范圍都在0～100%之間。

標(biāo)準(zhǔn)化距離因子的計(jì)算公式如下

(3)

式中，DT表示GPS一般最大誤差距離，本文取50 m(主要考慮到GPS的定位誤差一般不超過50 m)；DO表示匹配點(diǎn)到道路的距離。

標(biāo)準(zhǔn)化方向因子的計(jì)算公式如下

L=cos(θO-θT)

(4)

式中，θO表示道路方向角；θT表示匹配點(diǎn)速度方向角。

2.2 基于網(wǎng)格的候選匹配道路確定

使用網(wǎng)格首先需要對數(shù)據(jù)進(jìn)行預(yù)處理，使每一個(gè)待匹配點(diǎn)及道路節(jié)點(diǎn)都對應(yīng)一個(gè)網(wǎng)格編號。網(wǎng)格的劃分采用均勻的方格網(wǎng)格，并順序編號。主要原理如圖4所示：根據(jù)待匹配點(diǎn)P的坐標(biāo)，選擇一定長度L的搜索范圍，與搜索范圍框有交集的網(wǎng)格作為候選網(wǎng)格，而在候選網(wǎng)格內(nèi)有節(jié)點(diǎn)的道路均作為候選匹配道路。網(wǎng)格的使用大大減少了需要進(jìn)行匹配道路的數(shù)目，從而大大提高了算法的效率。

圖4 候選道路確定原理

3 算法實(shí)現(xiàn)及試驗(yàn)效果

改進(jìn)后的匹配算法具體為：

(1) 讀取所有待匹配軌跡點(diǎn)，包括經(jīng)緯度坐標(biāo)及網(wǎng)格編號。

(2) 判斷待匹配點(diǎn)在網(wǎng)格的什么位置。如果所在網(wǎng)格不是邊界網(wǎng)格，且位置在左上，則候選網(wǎng)格為所在網(wǎng)格，以及左邊相鄰、上邊相鄰、左上4個(gè)網(wǎng)格，依次類推位置在左下、右上、右下的候選網(wǎng)格；如果所在網(wǎng)格是邊界網(wǎng)格，則根據(jù)判斷的所在的是哪一邊相應(yīng)去掉那一邊的候選網(wǎng)格。

(3) 搜索在候選網(wǎng)格中的節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)查找節(jié)點(diǎn)所在的道路，得到候選道路集，并初始化匹配度(為0)及初始投影點(diǎn)坐標(biāo)。

(4) 選擇一條候選道路，計(jì)算待匹配點(diǎn)到道路的距離，以及待匹配點(diǎn)速度方向與道路速度方向的夾角。

(5) 根據(jù)步驟(4)計(jì)算得到的距離與方向夾角，按照公式計(jì)算得到匹配度。與前一個(gè)匹配度比較，若大于前一個(gè)匹配度，則更新匹配度。

(6) 計(jì)算待匹配點(diǎn)到道路的投影點(diǎn)坐標(biāo)。若投影點(diǎn)在道路上，則返回投影點(diǎn)坐標(biāo)；若投影點(diǎn)坐標(biāo)不在道路上(投影到道路延長線上)，則還需要判斷投影點(diǎn)到道路起點(diǎn)的距離與到終點(diǎn)的距離，選擇距離較短的點(diǎn)返回坐標(biāo)。

(7) 判斷匹配度有沒有更新，若有更新，則更新投影點(diǎn)坐標(biāo)；若未更新，則不更新投影點(diǎn)坐標(biāo)；重復(fù)步驟(2)—(7)，直到所有候選道路都進(jìn)行匹配。

(8) 重復(fù)步驟(1)—(7)，直到所有待匹配點(diǎn)都匹配。

地圖匹配算法的流程如圖5所示。

圖5 匹配算法流程

本文試驗(yàn)部分使用的數(shù)據(jù)為北京市部分出租車軌跡數(shù)據(jù)及路網(wǎng)數(shù)據(jù)，通過對其進(jìn)行預(yù)處理后(如網(wǎng)格劃分等)適用于本算法。本文算法在Visual Studio 2010平臺上，使用C#語言實(shí)現(xiàn)，并調(diào)用存儲于SQL Server 2008數(shù)據(jù)庫中的位置數(shù)據(jù)和路網(wǎng)數(shù)據(jù)。最終的匹配結(jié)果如圖6、圖7所示(圖中圈內(nèi)的點(diǎn)表示找不到候選匹配道路，算法將其作為噪聲刪除)。

圖6 匹配前軌跡點(diǎn)分布

圖7 匹配后軌跡點(diǎn)分布

4 結(jié) 語

地圖匹配算法能夠在一定程度上糾正GPS定位的誤差，為數(shù)據(jù)挖掘工作提供更準(zhǔn)確的數(shù)據(jù)支持，具有一定的研究價(jià)值。本文對傳統(tǒng)的點(diǎn)到線的地圖匹配算法進(jìn)行改進(jìn)，一定程度上提高了算法的匹配精度和效率，具有一定的實(shí)用價(jià)值。

[1] 李沛.車輛導(dǎo)航系統(tǒng)中地圖匹配的研究[D].北京：北京交通大學(xué), 2008.

[2] 夏州. GPS車輛導(dǎo)航中的數(shù)據(jù)處理與地圖匹配研究[D].北京：北京交通大學(xué), 2009.

[3] 張振輝. 車輛導(dǎo)航中地圖匹配算法與應(yīng)用研究[D].鄭州：信息工程大學(xué), 2006.

[4] 王慶祎.地圖匹配算法及軟件系統(tǒng)研究[D].天津：天津大學(xué), 2005.

[5] 袁正午,褚靜靜,鄧思兵，等.移動(dòng)終端定位技術(shù)發(fā)展現(xiàn)狀與趨勢[J]. 計(jì)算機(jī)應(yīng)用研究, 2007,24(11):1- 14.

[6] 劉春,楊超,范業(yè)明.基于流動(dòng)車數(shù)據(jù)的道路車速匹配與實(shí)時(shí)發(fā)布[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2010,35(4):394- 398.

[7] 李洋,張曉冬,鮑遠(yuǎn)律.多權(quán)值概率論實(shí)時(shí)地圖匹配[J].電子測量與儀器學(xué)報(bào). 2012,26(2):166- 170.

[8] 朱麗云,郭繼孚,溫慧敏,等.一種適用于復(fù)雜城市路網(wǎng)的浮動(dòng)車實(shí)時(shí)地圖匹配技術(shù)[J]. 交通與計(jì)算機(jī)，2007,25(6):81- 84.

[9] VELAGA N R, QUDDUS M A ,BRISTOW A L. Developing an Enhanced Weight- based Topological Map- matching Algorithm for Intelligent Transport Systems[J]. Transportation Re- search Part C(Emerging Technologies)，2009,17(6)：672- 683.

[10] CHENG L, WANG M. A New Path Planning Algorithm Based on Partitioned Urban Transportation Network[C]∥Proceedings of 2010 International Conference on Computer Application and System Modeling(ICCASM 2010). Taiyuan: IEEE, 2010: 13- 17.

A Map Matching Algorithm Based on Meshing and Direction Weighting

LIAO Jia1,YU Jianzhong2,LI Junfeng1

(1. Ningbo Institute of Surveying and Mapping, Ningbo 315042, China; 2. Ningbo Urban Planning & Geographic InformationCenter, Ningbo 315042, China)

Map- matching algorithm is to correct the point that deviated from the road to the correct location. The candidate matching road is confired through leading the concept of grid division and the degree of matching about a point to a line is calculated through weighting factors of the direction based on traditional point- to- line map- matching algorithm. The test shows that the improved algorithm can improve the accuracy of the algorithm and the efficiency of the algorithm to a certain extent. This Algorithm has some practical value.

meshing; weighted direction; map matching

2016- 07- 19 作者簡介： 廖 佳(1980—)，男，碩士，高級工程師，研究方向?yàn)榈乩硇畔?、航測遙感和三維數(shù)字城市建設(shè)。E- mail：5664266@qq.com 通信作者： 李俊峰。E- mail: 553078256@qq.com

廖佳，俞薦中，李俊峰.一種利用網(wǎng)格劃分及方向加權(quán)的地圖匹配算法[J].測繪通報(bào)，2017(3)：124- 127.

10.13474/j.cnki.11- 2246.2017.0100.

P208

A

0494- 0911(2017)03- 0124- 04