廖 佳，俞薦中，李俊峰

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

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

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

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

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

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

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

1 地圖匹配基本理論

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

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

1.1 幾何分析法

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

圖1 點到點匹配缺陷

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

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

圖2 點到線匹配缺陷

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

(1)

1.2 拓撲分析法

基于道路網(wǎng)的拓撲分析方法首先需要的是建立道路網(wǎng)的拓撲關(guān)系。而所謂道路網(wǎng)的拓撲關(guān)系就是指節(jié)點、道路線、面之間的關(guān)系。拓撲分析法首先根據(jù)道路的拓撲關(guān)系及待匹配點的空間位置確定候選的匹配道路集合，然后通過歷史數(shù)據(jù)分析得到匹配道路。

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

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

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

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

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

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

圖3 匹配度計算

匹配度的計算公式如下

M=φD+μL

(2)

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

標準化距離因子的計算公式如下

(3)

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

標準化方向因子的計算公式如下

L=cos(θO-θT)

(4)

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

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

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

圖4 候選道路確定原理

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

改進后的匹配算法具體為：

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

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

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

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

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

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

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

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

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

圖5 匹配算法流程

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

圖6 匹配前軌跡點分布

圖7 匹配后軌跡點分布

4 結(jié) 語

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

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

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

[3] 張振輝. 車輛導航中地圖匹配算法與應用研究[D].鄭州：信息工程大學, 2006.

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

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

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

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

[8] 朱麗云,郭繼孚,溫慧敏,等.一種適用于復雜城市路網(wǎng)的浮動車實時地圖匹配技術(shù)[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—)，男，碩士，高級工程師，研究方向為地理信息、航測遙感和三維數(shù)字城市建設(shè)。E- mail：5664266@qq.com 通信作者： 李俊峰。E- mail: 553078256@qq.com

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

10.13474/j.cnki.11- 2246.2017.0100.

P208

A

0494- 0911(2017)03- 0124- 04