基于離散Fréchet距離的地圖匹配方法

鄭少波, 周國祥, 張本宏, 石 雷

(合肥工業大學 計算機與信息學院,安徽 合肥 230009)

基于離散Fréchet距離的地圖匹配方法

鄭少波, 周國祥, 張本宏, 石 雷

(合肥工業大學 計算機與信息學院,安徽 合肥 230009)

針對離散Fréchet距離可以用于近似估計Fréchet距離且易于計算的特點,文章引入了離散Fréchet距離來判別軌跡曲線與路網路徑的曲線間的距離,提出了一種基于離散Fréchet距離的全局地圖匹配方法,并使用基于云模型的不確定性推理方法,實現全球定位系統(global positioning system,GPS)軌跡數據的全局地圖匹配,并驗證了該算法的有效性和實用性。

車輛定位;全球定位系統(GPS)軌跡數據;地圖匹配;不確定性推理;規則發生器

車輛定位系統是由全球定位系統(global positioning system,GPS)和地理信息系統(geographic information system,GIS)組成,可以實現對車輛的跟蹤和定位[1]。由于GPS定位精度的影響,GPS定位數據在結合數字地圖的分析處理時會出現軌跡點偏離道路的現象,需要進行地圖匹配,從而獲得結合路網的行車軌跡[2]。

傳統的地圖匹配方法通常利用車輛行駛的方向與路網道路的夾角、車輛定位點到備選路段的距離長短等車輛信息來推算車輛當前的行車路段。文獻[3]提出的地圖匹配方法將方向、點到道路的距離等因素通過各自加權系數累加,運用權重的策略將點匹配到道路上。然而這種點到線的匹配由于缺乏對整體軌跡趨勢的考慮,在復雜路網環境下的匹配容易導致誤匹配。

GPS歷史軌跡數據提供了車輛整體的運動趨勢,目前大多數針對軌跡數據的地圖匹配方法采用基于曲線相似度的全局匹配方法[4]。曲線匹配和點與線的匹配有差異,它需要使用距離準則來定義2條曲線間的相似程度[4]。文獻[5]選擇Fréchet距離作為路段的權重,并構建網絡圖,計算最短路徑,最終獲得最佳的匹配路段,但是Fréchet距離是考慮距離集合中的最大值,因此它很容易受到異常的影響。文獻[6]使用平均Fréchet距離取代Fréchet距離用于曲線距離的評判,并利用智能云模型控制器完成地圖匹配,但是其平均Fréchet距離計算量龐大，且文中未給出具體的云模型推理算法。

本文提出了一種使用離散Fréchet距離判斷全局軌跡曲線和備選路徑之間距離的全局地圖匹配算法,離散Fréchet距離是在連續Fréchet 距離[7]的基礎提出的,提供了連續測量的估計值,可以有效地用一個簡單算法計算[7],簡化平均Fréchet距離的計算,然后使用基于云模型的不確定性推理方法,設計路徑云推理系統確定車輛實際行駛的道路,以期獲得較小的時間復雜度和較高的正確匹配率。

1 離散Fréchet距離和云推理方法

1.1 離散Fréchet距離

在連續Fréchet距離的基礎上,Eiter和Mannila提出了離散Fréchet距離的定義,提供了近似計算Fréchet距離的方法[7],其定義如下。

定義1 給定一個有n個至高點的多邊形鏈P={p1,p2,…,pn},一個沿著P的k步,分割P的至高點成為k個不相交的非空子集{Pi}i=1,…,k,使得Pi=〈pni-1+1,…,pni〉,0=n0

給定2個多邊形鏈A=〈a1,…,am〉和B=〈b1,…,bn〉,一個沿著A和B的組合步是由1個沿著A的k步{Ai}i=1,…,k和1個沿著B的k步{Bi}i=1,…,k組成,使得對于1≤i≤k,并且Ai和Bi中有1個恰好包含1個至高點[8]。1個沿著鏈A和B的組合步W={(Ai,Bi)}的花費為:

(1)

離散Fréchet距離不足以判別曲線的相似度,因為它表示的是曲線之間關鍵特征點的距離,故引入定義2作為本文使用的距離。

Eiter和Mannila在文中給出了離散Fréchet距離的偽代碼,并且論證了時間復雜度為O(pq)。算法使用動態規劃來實現,效率非常高,不需要復雜的數據結構,可以使用離散Fréchet距離來近似地計算Fréchet距離。

1.2 云推理方法

正向云發生器是從定性信息中獲得定量數據的分布情況和范圍[10],以下是一維正向正態云的實現算法。

輸入數據:N表示云滴數,(Ex,En,He)表示一維定性概念的數字特征。

輸出數據:x表示N個云滴的定量值,u表示概念的確定度。

(1) 以En為期望值,He為均方差,生成正態隨機數En′。

(2) 以Ex為期望值,En′為均方差,生成正態隨機數x。

(4) (x,u)作為論域中的1個云滴。

(5) 重復步驟(1)～步驟(4)直到產生N個云滴結束。

前件云發生器的定義是對于論域里面1個確定量值x,經過正向云發生器,獲得確定度u。其中u為x屬于定性概念的確定度。一維前件云發生器實現算法[10]如下。

輸入數據: (Ex,En,He)表示一維定性概念的數字特征,x表示定量值。

輸出數據:u表示確定度。

(1) 以En為期望值,He為均方差,生成正態隨機數En′。

對于確定度u∈[0,1],通過正向云發生器生成定性概念上滿足確定度u的定量值x,稱為后件云發生器[11]。后件云發生器實現算法[10]如下。

輸入數據: (Ex,En,He)表示一維定性概念的數字特征,確定度為u,u∈[0,1]。

輸出數據:x表示定量值。

(1) 以En為期望值,He為均方差,生成正態隨機數En′。

2 算法描述

本文算法按照GPS車輛軌跡采樣點的定位精度構建緩沖區,獲取當前車輛可能行駛的路段,按照曲線匹配距離準則計算整體車輛行車軌跡與備選路段曲線的距離,將各個距離和行車信息作為輸入,用基于云模型的不確定性推理方法獲取匹配度XB,實現地圖匹配。算法基本步驟如下：

(1) 計算當前定位點可能行駛的路段集合R。

(2) 計算R中各條可能路徑與GPS軌跡路徑的離散Fréchet距離。

(3) 獲取車輛的當前信息,定位點與帶匹配道路的距離d,定位點定位時刻行車方向與路段的正北方向角差值θ。

(4) 將上述2個信息和離散Fréchet距離帶入基于云模型不確定性推理方法中獲取路段的匹配度XB,根據各條路段匹配度選擇車輛當前最可能行駛的路段。

2.1 備選路徑集合的確定

本文采用采樣誤差橢圓的方法獲取備選全局路段集合。假設相鄰的2個軌跡點Pi和Pi+1,橢圓區域包含了2個軌跡點時間段內可能經過的所有路徑,具體公式如下:

(2)

(3)

(4)

(5)

其中,vPi為軌跡點Pi處的速度;tPi為Pi處的時間,計算Pi至Pi+1所有可能的路徑,得到備選路段集合R;a為所有可能路徑的最大值;c為所有可能路徑的最小值。

2.2 離散Fréchet距離的計算

離散Fréchet距離的計算步驟如下。

(1) 將備選路徑曲線和路段曲線的至高點與至低點表示成A=〈a1,…,am〉和B=〈b1,…,bn〉,ai和bi分別為至高點和至低點,且m≤n,若n-m>5,則兩曲線不相似,否則轉到步驟(2)。

(2) 設曲線A至高點和至低點較少,將曲線B割分成m步,割分必須確保相同時刻的至高點和至低點相對應,設有k種劃分,對于每種割分Wj={(Ai,Bi)}(1≤i≤m,1≤j≤k)。

(3) 對于每個割分,查找每步全部對應點之間的距離,找出距離中的最大值,再查找這種割分的全部步中最大距離,找出最大值[12]。

(4) 查找全部割分方法中的距離,找出最小值,當成兩曲線的離散Fréchet距離。

(5) 計算得出峰谷點和峰頂點的最小離散Fréchet距離,這2個距離相減后取絕對值即為離散Fréchet距離。

2.3 三條件單規則發生器

三條件單規則發生器由三維前件云發生器與一維后件云發生器組合構成[13]。規則后件實際輸出分成多種情況。三條件單規則發生器算法如下。

輸入數據:前件三維定性概念的數字特征(ExA1,ExA2,ExA3)、(EnA1,EnA2,EnA3)、(HeA1,HeA2,HeA3)以及定量值(xA1,xA2,xA3),后件定性概念的數字特征(ExB,EnB,HeB)。

輸出數據:滿足確定度u的后件定性概念的定量值xB。

(1) 以EnA1為期望值,HeA1為均方差,生成正態隨機數EnA1′。

(2) 以EnA2為期望值,HeA2為均方差,生成正態隨機數EnA2′。

(3) 以EnA3為期望值,HeA3為均方差,生成正態隨機數EnA3′。

(4) 計算確定度,具體公式如下:

(5) 以EnB為期望值,HeB為均方差,生成正態隨機數EnB′。

(7) 若是其他情況,則有：

當xA1≤ExA1,xB1計算式取負號,當xA1>ExA1,xB1取正號;xB2,xB3計算式正負號選取同理。

2.4 通過路徑云推理系統確定匹配道路

本文使用的路徑云推理系統實現步驟如下:獲取導航定位點到候選道路的距離d、車輛行駛方向與路段方向角度差值θ以及上文所計算的離散Fréchet距離,定義路徑云推理系統輸入變量d、θ、離散Fréchet距離、路徑云推理系統輸出變量P;將路徑云推理系統各變量表示為P={很小,小,中,大,很大},θ={小,中,大},d={小,中,大},離散Fréchet距離={小,中,大}。分別用云模型表示距離d中的3個定性概念為:

A1=(0,10/3,0.01),

A2=(10,10/3,0.01),

A3=(20,10/3,0.01)。

用云模型表示其他變量的定性模型如下:

B1=(0,10,0.01),B2=(30,10,0.01),

B3=(60,10,0.01);C1=(0,10/3,0.01),

C2=(10,10/3,0.01),C3=(20,10/3,0.01);

D1=(40,5,0.01),D2=(55,5,0.01),

D3=(70,5,0.01),D4=(85,5,0.01),

D5=(100,5,0.01)。

三維云模型推理規則見表1所列。由表1可以看出，如果方向角度差值θ越小,定位點到候選道路的距離d越小,離散Fréchet距離越小,那么P越大。

表1 三維云模型推理規則

將輸入(xA1,xA2,xA3)看成3個云滴定量值,對于27條規則,則可構造27個發生器,且均為三條件單規則。(xA1,xA2,xA3)分別作為每個發生器輸入,使用三條件單規則發生器算法分別計算27條三維前件云發生器的確定度u。若確定度u>0,則此條規則被激活了;若確定度u=0,則沒有激活這條規則。

(6)

其中,M為激活的規則的數目。

xB即為所求的綜合匹配度,xB越大則該備選路徑與所行駛的路段匹配度越高,至此可以得到匹配的路段。

3 實驗結果與分析

為了測試該算法在實際應用中的效果,本文使用合肥協力公司2015年3月28日提供的GPS車輛定位數據,采樣間隔為30 s,車輛經過明珠路-集賢路-蘆花路-石楠路-銘傳路-香樟大道,路網數據采用合肥市城市路網數據。文中以相鄰采樣點作誤差橢圓獲得候選道路集合,最終獲得車輛當前最大概率行駛的道路。

車輛行駛軌跡如圖1所示。圖1中虛線上的點表示匹配之前GPS定位位置;虛線代表車輛行駛軌跡;實線表示實際匹配的道路。

圖1 車輛行駛軌跡匹配效果圖

由圖1可以看出,在考慮了歷史行車軌跡點后,車輛行車軌跡較為準確地匹配到最大可能行駛的道路上,文中算法對車輛行車路段的匹配精度有了很大提高。

本文算法與基于弱Fréchet距離全局匹配算法在時間復雜度上的結果見表2所列,其中，p表示軌跡曲線的采樣點數目；q表示道路網的路徑數目。

對采集到的軌跡數據進行地圖匹配,統計正確匹配率,與點到線的匹配算法以及基于弱Fréchet距離全局匹配算法的匹配效果比較見表2所列。

由表2可以看出,綜合考慮了歷史軌跡信息和離散Fréchet距離后,匹配的總體精度獲得了明顯的提高。本文算法簡化了弱Fréchet距離計算的同時保留了弱Fréchet距離計算曲線相似度的準確性,比傳統點到線匹配算法的正確匹配率高出很多。

表2 地圖匹配算法的時間復雜度和正確匹配率

4 結 論

本文提出了一種考慮車輛歷史行車軌跡的全局匹配方法,并利用云模型的不確定性推理綜合考慮了車輛的實時行車數據,使得算法的效率在時間復雜度和匹配準確性上均有所提高。通過實際數據的測試可以看出,本文算法具有實時性好、效率高、較好的匹配準確性等優點,一定程度上降低了地圖匹配的誤匹配率。

[1] 陶庭葉,高飛,吳兆福,等.利用高斯平滑法提取GPS觀測序列中的結構振動監測信號[J].合肥工業大學學報(自然科學版),2010,33(1):106-109.

[2] 陶帥,孫克文.GPS信號捕獲策略的研究[J].合肥工業大學學報(自然科學版),2015,38(5):631-634.

[3] YANG Jian,MENG Liqiu.Feature selection in conditional random fields for map matching of GPS trajectories[M]//Progress in Location-Based Services 2014:Lecture Notes in Geoinformation and Cartography.Switzerland:Springer International Publishing,2015:121-135.

[4] 李清泉,黃練.基于GPS軌跡數據的地圖匹配算法[J].測繪學報,2010,39(2):7-13.

[5] YIN H B,WOLFSON O.A weight-based map-matching method in moving objects databases [C]//Proceedings of the 16th International Conference on Scientific and Statistical Database Management.Santorini Island:[s.n.],2004:437-439.

[6] 曹凱,唐進君,劉汝成.基于Fréchet距離準則的智能地圖匹配算法[J].計算機工程與應用,2007,43(28):223-226.

[7] KENEFIC R J.Track clustering using Fréchet distance and minimum description length[J].Journal of Aerospace Information Systems,2014,11(8):512-524.

[8] 朱潔,黃樟燦,彭曉琳.基于離散Fréchet距離的判別曲線相似性的算法[J].武漢大學學報(理學版),2009,55(2):227-232.

[9] 朱潔,黃樟燦,彭曉琳.一種新的在線手寫簽名認證算法[J].計算機工程與應用,2008,44(31):178-181.

[10] 陳昊,李兵.基于云模型的不確定性推理方法[J].小型微型計算機系統,2011,32(12):2449-2455.

[11] 李德毅,孟海軍,史雪梅.隸屬云和隸屬云發生器[J].計算機研究和發展,1995,32(6):16-21.

[12] WYLIE T,ZHU B H.Following a curve with the discrete Fréchet distance[J].Theoretical Computer Science,2014,556:34-44.

[13] PINTO A M,MOREIRA A P,COSTA P G.A localization method based on map-matching and particle swarm optimization[J].Journal of Intelligent & Robotic Systems,2015,77(2):313-326.

(責任編輯 閆杏麗)

A map matching algorithm based on discrete Fréchet distance

ZHENG Shaobo, ZHOU Guoxiang, ZHANG Benhong, SHI Lei

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

For discrete Fréchet distance can be used to approximate the Fréchet distance and has the feature of easy calculation, discrete Fréchet distance is introduced to determine the distance between the travel path curve and the curve of road network, and a novel map matching method based on discrete Fréchet distance is proposed. Finally, the global map matching for global positioning system(GPS) tracking data is implemented by using the uncertain reasoning approach based on cloud model. The effectiveness and practicality of the proposed algorithm is verified by simulation experiments.

vehicle location; global positioning system(GPS) tracking data; map matching; uncertainty reasoning; rule generator

2015-12-18；

2016-02-19

國家自然科學基金資助項目(61501161)

鄭少波(1991-),男,安徽六安人,合肥工業大學碩士生; 周國祥(1956-),男,安徽合肥人,合肥工業大學教授,碩士生導師.

10.3969/j.issn.1003-5060.2017.01.008

P228.4

A

1003-5060(2017)01-0042-05