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

黃奕峰

(興天通訊技術(shù)有限公司，天津 301700)

?

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

黃奕峰

(興天通訊技術(shù)有限公司，天津 301700)

針對(duì)傳統(tǒng)導(dǎo)航系統(tǒng)的地圖匹配算法缺乏整體性考慮的缺點(diǎn)，且GPS浮動(dòng)車軌跡數(shù)據(jù)具有曲線整體趨勢(shì)特性，文中結(jié)合城市中對(duì)行車的約束限制，提出了一種基于GPS浮動(dòng)車軌跡數(shù)據(jù)的全局地圖匹配算法，該算法綜合考慮各種因素，從而達(dá)到較好地實(shí)現(xiàn)匹配效果的目的，如軌跡數(shù)據(jù)和網(wǎng)絡(luò)路徑進(jìn)行曲線擬合時(shí)的相似性、實(shí)際行車路徑與交通約束的連通性。對(duì)所提出的算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，從而促進(jìn)了GPS浮動(dòng)車軌跡數(shù)據(jù)的進(jìn)一步分析應(yīng)用。

GPS軌跡數(shù)據(jù)；浮動(dòng)車；行車約束；地圖匹配

GPS浮動(dòng)車數(shù)據(jù)即為包含有速度數(shù)據(jù)和方向信息的一系列軌跡點(diǎn)，但由于GPS位置精度有限，當(dāng)在進(jìn)行數(shù)字地圖分析處理時(shí)會(huì)產(chǎn)生軌跡點(diǎn)與道路有偏差的情況，則需要進(jìn)行地圖匹配以獲得無(wú)偏差軌跡描述。雖然傳統(tǒng)的地圖匹配算法研究較多[1-2]，但大多缺乏整體性考慮而導(dǎo)致復(fù)雜環(huán)境下的誤匹配，后又出現(xiàn)一些改進(jìn)的匹配算法，如使用差分GPS輔助設(shè)備、濾波等提高匹配準(zhǔn)確率[3-6]。GPS浮動(dòng)車軌跡數(shù)據(jù)具有曲線整體趨勢(shì)特性，利用全局思想保證軌跡的準(zhǔn)確性[7]。目前軌跡數(shù)據(jù)的地圖匹配方法大多基于全局匹配算法或復(fù)合匹配算法，全局匹配算法是基于曲線相似度，一般比較復(fù)雜，但匹配精度高[8]；復(fù)合匹配方法較為簡(jiǎn)單，但精度低[9]。在進(jìn)行算法匹配時(shí)，由于軌跡代表的路徑均是連通的路段，因此可根據(jù)道路拓?fù)渑c連通性設(shè)計(jì)地圖匹配算法[10-12]。實(shí)際生活中交通規(guī)則會(huì)限制車輛的行駛，據(jù)此本文提出了一種基于GPS浮動(dòng)車軌跡數(shù)據(jù)的全局地圖匹配算法，該算法綜合考慮各種因素，可達(dá)到較好地實(shí)現(xiàn)匹配效果的目的。

1 算法基本原理

本文算法的基本原理如圖1所示，是以GPS浮動(dòng)車數(shù)據(jù)采樣精度構(gòu)建緩沖區(qū)，并以此估計(jì)軌跡點(diǎn)所處位置，然后根據(jù)路段的連通性與交通約束來(lái)構(gòu)建和更新未匹配路徑，最后以曲線相似度準(zhǔn)則得到與浮動(dòng)車軌跡最接近的路徑，從而實(shí)現(xiàn)地圖匹配，其具體過(guò)程可描述如下。

圖1 地圖匹配算法的基本原理

(1)計(jì)算路段集Rc，其為當(dāng)前可能行駛路段的集合；(2)計(jì)算Rc與每一個(gè)階段最后一個(gè)路段的續(xù)段集交集Rinsect(i)；(3)根據(jù)交集Rinsect(i)更新總體路徑集PPathset；(4)處理完所有GPS點(diǎn)之后，計(jì)算GPS軌跡路徑與PPathset中路徑的曲線相似度，并選擇相似度最高的作為整體匹配路徑。

2 行車約束的備選全局路徑集的確定

本文由之前所構(gòu)建的緩沖區(qū)得到當(dāng)前可能路段的集合Rtpi，考慮實(shí)際情況中除了連通性之外的車輛行駛交通規(guī)則限制條件將會(huì)顯著提高算法的精度。如圖2所示，在交叉點(diǎn)處只能右轉(zhuǎn)，所以r1的后續(xù)路段只有r4。

圖2 道路的直接后續(xù)道路

Ti(topo)為路段對(duì)應(yīng)的拓?fù)浼s束，Ti(ru)為車輛行駛的交通規(guī)則，若用NRG(Ri)代表Ri的后續(xù)路段集，則Ri的直接可行路段集為

NR(Ri)={Ri∈NRG(Ri)|Ti(topo)∩Ti(ru)}

GPS采樣間隔變化會(huì)產(chǎn)生跨路段現(xiàn)象，為了解決此問(wèn)題，文獻(xiàn)[13]用Dijstra算法計(jì)算得到的最短路徑作為最終匹配解，文獻(xiàn)[14]則通過(guò)測(cè)量距離來(lái)獲得最接近真實(shí)路段的路徑。通過(guò)分析與總結(jié)，本文引入橢圓誤差概念，如圖3所示。兩個(gè)采樣點(diǎn)Pi、Pi+1在時(shí)間段內(nèi)可能經(jīng)過(guò)的路徑集可通過(guò)式(1)進(jìn)行計(jì)算

(1)

其中，Vpi為采樣點(diǎn)Pi的速度；tpi為采樣點(diǎn)Pi處的時(shí)間。

圖3 兩個(gè)采樣點(diǎn)間的可行橢圓區(qū)域

3 基于曲線相似度的匹配路徑選擇

判斷所有可行路徑集中路徑與GPS浮動(dòng)車軌跡數(shù)據(jù)的相似性是以曲線的整體走勢(shì)相似性進(jìn)行的，本文選擇的相似度計(jì)算方法為改進(jìn)的掃描線曲線相似度計(jì)算法[15]，具體步驟如下：

(1)對(duì)所有可行路徑按照軌跡延伸范圍進(jìn)行切割，如圖4所示；

(2)將總體路徑劃分為n個(gè)部分，其中n為總體路徑包含的路段數(shù)，然后掃描線法計(jì)算每部分的相似度。設(shè)X、Y方向的延伸范圍為ExtendX、ExtendY，若ExtendX>ExtendY，則掃描線方向平行于Y軸，若ExtendX

(3)最后根據(jù)式(2)計(jì)算總體路徑集中路徑PPathset(i)的曲線相似度scoresim，從而得到匹配路徑

(2)

圖4 掃描線法邊框的切割

4 算法驗(yàn)證

本文所使用的GPS浮動(dòng)車數(shù)據(jù)采樣間隔為10 s，重采樣間隔為60 s，重采樣是為了更有效的對(duì)實(shí)驗(yàn)進(jìn)行分析。地圖數(shù)據(jù)為武漢卓越科技提供的MapInfo格式的武漢道路數(shù)據(jù)。

4.1 時(shí)間效率分析

算法的基本步驟是首先構(gòu)造總體路徑集，然后采用改進(jìn)的掃描線曲線相似度計(jì)算方法進(jìn)行相似度計(jì)算，最終找到最匹配路徑?？傮w路徑集中數(shù)據(jù)量較小，本算法與點(diǎn)到線的匹配算法、基于弱Frechet距離全局匹配算法整體時(shí)間復(fù)雜度O(n)的比較，如表1所示。

表1 地圖匹配算法的時(shí)間復(fù)雜度與全局性比較

表中，n表示采樣點(diǎn)數(shù);m表示路段數(shù)。

4.2 地圖匹配的結(jié)果

用實(shí)驗(yàn)驗(yàn)證本文所提出的算法，在所得出的效果圖中GPS浮動(dòng)車軌跡點(diǎn)用黑點(diǎn)表示，匹配后的路徑則為高亮粗線條表示。如圖5所示，其為實(shí)驗(yàn)匹配效果圖。

圖5 地圖匹配的整體效果圖

實(shí)驗(yàn)結(jié)果1 平行雙線路。

傳統(tǒng)的地圖匹配算法在遇到平行雙線路時(shí)易發(fā)生誤匹配，而本文提出的算法在曲線相似性的基礎(chǔ)上加入實(shí)際情況的交通約束，從而減少了誤匹配情況的發(fā)生。如圖6中有兩條平行雙線路A(自西向東)、B(自東向西)，浮動(dòng)車軌跡點(diǎn)序列方向在圖中用箭頭所示，雖軌跡曲線形狀更貼近道路B，但本算法中的行車約束使算法得到正確解A。

圖6 平行雙線路情況下的地圖匹配結(jié)果

實(shí)驗(yàn)結(jié)果2 相鄰軌跡點(diǎn)跨路段。

當(dāng)車輛行駛速度過(guò)快或采樣間隔較大時(shí)，則相鄰點(diǎn)之間會(huì)出現(xiàn)中間路段，而本文提出的算法中運(yùn)用橢圓誤差與行車約束，得到兩點(diǎn)間可能的路徑集，從而結(jié)合整體路徑集進(jìn)行判斷可提高匹配準(zhǔn)確率。如圖7中的GPS采樣間隔分別為10 s、60 s，兩種情況均實(shí)現(xiàn)了正確匹配。

圖7 GPS采樣間隔不同時(shí)的匹配結(jié)果

4.3 算法匹配效果統(tǒng)計(jì)

為了對(duì)算法匹配效果進(jìn)行統(tǒng)計(jì)與分析，本文對(duì)采集到的32條軌跡數(shù)據(jù)進(jìn)行匹配，并將結(jié)果匹配率進(jìn)行統(tǒng)計(jì)，再與點(diǎn)到線的匹配算法、基于弱Frchet距離全局匹配算法的匹配率進(jìn)行比較，比較結(jié)果如表2所示。

表2 地圖匹配算法正確匹配率比較

5 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)導(dǎo)航系統(tǒng)的地圖匹配算法缺乏整體性考慮的缺點(diǎn)，且GPS浮動(dòng)車軌跡數(shù)據(jù)具有曲線整體趨勢(shì)特性，因此本文結(jié)合城市中對(duì)行車的約束限制，提出一種基于GPS浮動(dòng)車軌跡數(shù)據(jù)的全局地圖匹配算法，該算法綜合體現(xiàn)了道路拓?fù)渌惴ㄅc曲線匹配算法的優(yōu)點(diǎn)，改進(jìn)了點(diǎn)匹配算法中對(duì)各因素參數(shù)進(jìn)行設(shè)定的缺點(diǎn)，并最終通過(guò)GPS浮動(dòng)車與實(shí)際道路數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)，證明了該算法的有效性。

[1] Quddus M A.High integrity map matching algorithms for advanced transport telematics applications[D].London:University of London,2006.

[2] Quddus M A, Washington Y O,Robert B N．Current map-matching algorithms for transport applications：state-of-the art and future research directions[J].Transportation Research Part C,2007(15):312-328.

[3] Yang D,Cai B,Yuan Y.An improved map-matching algorithm used in vehicle navigation system[C].Shanghai:Intelligent Transportation Systems,2003.

[4] Li Z,Chen W.A new approach to map-matching and parameter correcting for vehicle navigation system in the area of shadow of GPS signal[C].Vienna:IEEE Intelligent Transportation Systems，2005.

[5] Najjar M E,Bonnifait P.A road—matching method for precise vehicle localization using kalman filtering and belief theory[J]．Autonomous Robots,2005,9(2):73-191.

[6] Obradovic D,Lenz H,Schupfner M.Fusion of mapand sensor data in a modern car navigation system[J]．Journal of VSLI Signal Processing,2006,45(1-2):112-122.

[7] Brakatsoulas S, Pfoser D, Salas R, et al. On map-matching vehicle tracking data[C].Norway:International Conference on Very Large Data Bases,2005.

[8] Yin H, Wolfson O. A weight-based map matching method in moving objects databases[C].Norway:International Conference on Scientific and Statistical Database Management, 2004.

[9] 章威,徐建閩,林綿峰.基于大規(guī)模浮動(dòng)車數(shù)據(jù)的地圖匹配算法[J].交通運(yùn)輸系統(tǒng)工程與信息,2007,7(2):39-45.

[10] Blazquez C A, Vonderohe A P.Simple map-matching algorithm applied to intelligent winter maintenance vehicle data[J].Transportation Research Record,2005(1):68-76.

[11] Meng Y．Improved positioning of land vehicle in ITS using digital map and other accessory information[D]．Hong Kong：Hong Kong Polytechnic University,2006.

[11] Amer I,Badawy W,Jullien G.A high-performance hardware implementation of the H.264 simplified 8×8 transformation and quantization[C].PF,USA:Proceeding IEEE International Conference on Acoustics, Speech and Signal Processing,2005.

[12] Chao Y C,Tsai H H,Lin Y H,et al.A novel design for computation of all transforms in H.264/AVC decoders[C].Marco:Proceeding IEEE International Conference Multimedia and Expo,2007.

[13] Amer I,Badawy W,Jullien G,et al.A simplied 8×8 transformation and quantization real-time IP-block for MPEG-4 H.264/AVC applications: a new design flow approach[J].Journal of Circuits, System, Computer,2007(16):1011-1026.

[14] Park J S,Ogunfunmi T.A new hardware implementation of the H.264 8×8 transform and quantization[C].France:Proceeding of IEEE International Conference Acoustics, Speech and Signal Processing,2009.

[15] Jang F, Kao J N,Yang J S,et al. A 0.8μm 100 MHz 2-D DCT core processor[J].IEEE Transactions on Consumer Electron,1994(40):703-710.

Research on Map Matching Algorithm Based on GPS

HUANG Yifeng

(Xingtian Communication Technology Co. Ltd., Tianjin 301700, China)

The map matching algorithm based on traditional navigation system lacks overall consideration, and the GPS floating vehicle trajectory data has the characteristics of the overall curve trend. This paper proposes a global map matching algorithm based on the GPS floating vehicle trajectory data, combined with the drive constraints of the city. For better matching effect, the algorithm considers various factors, such as the curve similarity between trajectory data and network path, and the connectivity between the actual traffic path and traffic restriction. The proposed algorithm is verified by experiments.

GPS trajectory data; floating car; drive constraints; map matching

2016- 10- 24

黃奕峰(1973- )，女，本科。研究方向：通信工程，智能終端設(shè)備及軟硬件管理平臺(tái)。

10.16180/j.cnki.issn1007-7820.2017.06.015

TN967.1；P228.4

A

1007-7820(2017)06-054-04