曾 喆，李清泉，鄒海翔，萬劍華

1.中國石油大學（華東）地球科學與技術學院，山東 青島266580；2.深圳大學土木工程學院空間信息智能感知與服務深圳市重點實驗室，廣東 深圳518060；3.武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢430079；4.深圳市規(guī)劃國土發(fā)展研究中心，廣東 深圳518034

1 引 言

近年來，在智能交通領域中，GPS浮動車已經(jīng)成為一種交通、出行信息采集的重要手段。隨著互聯(lián)網(wǎng)大數(shù)據(jù)時代的到來，地理信息服務需求明顯增強，交通、出行等信息同時也成為地理信息數(shù)據(jù)的重要組成部分［1－2］。地圖匹配方法則是在海量GPS浮動車軌跡中實現(xiàn)地理信息數(shù)據(jù)挖掘的一項關鍵技術。然而，浮動車上配置的GPS設備往往是導航型GPS接收機，其定位精度并不高；而且，浮動車的數(shù)目一般較多，為避免數(shù)據(jù)量過大，浮動車的GPS采樣間隔往往較長（通常為20～100s）。在交通地理信息數(shù)據(jù)處理中，GPS浮動車數(shù)據(jù)是一系列相對于數(shù)字化道路中心線有一定偏離的離散軌跡點。因此，需要對這些軌跡數(shù)據(jù)實施地圖匹配以恢復其在道路網(wǎng)絡中的真實行駛路徑。

在傳統(tǒng)的車載導航中，GPS定位的采樣間隔（1s）相對較短，其所采用的地圖匹配算法通過GPS軌跡點的特征［3］以及與航位推算數(shù)據(jù)的融合，實際上可以達到比較高的匹配正確性與穩(wěn)定性［4－5］。與車載導航的地圖匹配類似，浮動車地圖匹配算法也主要采用GPS軌跡點的幾何、拓撲等特性來實施軌跡與道路的匹配。與車載導航中的軌跡數(shù)據(jù)不同的是，浮動車軌跡數(shù)據(jù)的采樣間隔較大，在兩相鄰軌跡點之間所缺失的信息較多。因而，需要根據(jù)兩相鄰軌跡點所具有的幾何、拓撲等特性在道路網(wǎng)絡中作關聯(lián)性分析來實施地圖匹配?，F(xiàn)有的浮動車地圖匹配方法主要通過下面這些方法來恢復在相鄰軌跡點之間損失的路徑信息：隱馬爾科夫匹配方法通過距離約束建立隱馬爾科夫模型來恢復浮動車軌跡在時間序列上最可能的路徑［6］；時空匹配方法（ST－matching method，ST）通過路網(wǎng)空間距離、拓撲關系及軌跡時間/速度限制來實施軌跡點之間的這種關聯(lián)性路徑恢復［7］。浮動車地圖匹配的其他變體方法也往往是基于浮動車軌跡點的方向、距離等初等幾何拓撲特征作為路徑恢復的一個主要約束條件［8－12］。從現(xiàn)有浮動車的地圖匹配方法來看，其單點匹配主要采用距離、方向等幾何特征來約束，其相鄰軌跡點之間的關聯(lián)匹配則主要采用道路拓撲關系來約束。然而，目前互聯(lián)網(wǎng)大數(shù)據(jù)時代，各種地理信息服務采用的路網(wǎng)模型往往是針對導航的較為精細的數(shù)據(jù)模型［13－14］（比如雙線路、輔路、匝道等的數(shù)字化表達），并且道路網(wǎng)絡在一些區(qū)域的形式較為復雜［13，15－16］?，F(xiàn)有浮動車地圖匹配方法在道路網(wǎng)絡復雜的位置實施地圖匹配時，由于具有近似特征的備選道路路段較多，在將軌跡點匹配到道路路段的過程中難以作出正確判決。這種復雜路網(wǎng)的精細數(shù)據(jù)模型導致在相對較大的時間間隔下，浮動車軌跡數(shù)據(jù)的地圖匹配結(jié)果存在正確率并不高，不同情形下匹配正確率并不穩(wěn)定等問題。

本文提出一種曲率積分約束的GPS浮動車地圖匹配方法，主要實現(xiàn)方式為：先分別計算GPS軌跡的相鄰軌跡點之間的曲率積分值和相鄰軌跡點對應的候選路段對之間的路徑的曲率積分值，然后通過這兩個曲率積分值之間的相似程度來約束浮動車的地圖匹配。

2 曲率的相關概念及其計算

2.1 曲線曲率的相關概念

定義1 在投影平面P中，假設向量a相對于正北方向按順時針方向旋轉(zhuǎn)所成的角度為向量a的方位角φ（a），其取值范圍為［0，2π）。

定義2 兩個向量的旋轉(zhuǎn)夾角deltφ（a，b）為b相對于a按順時針方向旋轉(zhuǎn)所成的角度，旋轉(zhuǎn)角范圍定義在（－π，π］，逆時針為負值，順時針為正值。

平面P上兩個向量a和b，則可以采用式（1）計算它們之間的旋轉(zhuǎn)夾角

式（1）給出了兩個向量旋轉(zhuǎn)夾角與其方位角之間的計算關系。

定義3 假設γ＝γ（s）：（α，β）→R2為一條以弧長為參數(shù)的二維平面光滑曲線，那么，可以定義X＝γ（s）點處的曲率［17］為式中，ψ（s）為曲線在X點的切向量T（s）的角度值；Δψ為ψ（s）的增量；Δs為弧長增量。

曲率描述了曲線上切向量T（s）對弧長s的轉(zhuǎn)動速率，也就是說，它描述了曲線在該點的彎曲程度。

定義4 假設γ＝γ（s）：（α，β）→R2為以弧長為參數(shù)的一條二維平面光滑曲線，相對曲率［18］為

平面曲線的相對曲率定向，在曲線上某點X，沿s增加的方向，曲線在X前方的軌跡在切向量左側(cè)則κs＜0，在右側(cè)κs＞0。在地圖投影平面上一般為左手系，定義1、定義2實際上給出的是一種左手坐標系的定義方法，因此，在這里也是采用左手系來定義κs的正負方向。

定義5 假設γ＝γ（s）：（α，β）→R2為以弧長為參數(shù)的一條二維平面光滑曲線γ，曲線γ上a、b兩點，且有a，b∈（α，β），a＜b則a、b之間的曲率積分值為

曲率積分Γ（a，b）描述的是切向量T（s）從γ（a）處出發(fā)沿曲線γ轉(zhuǎn)動到γ（b）處所轉(zhuǎn)動的角度。曲率是曲線的一個內(nèi)蘊幾何量，在GPS軌跡點的地圖匹配中，前后兩軌跡點之間的曲率積分值給出了曲線在兩點之間的這種內(nèi)蘊幾何量的累積值，其度量的是運動軌跡在某一時間段內(nèi)軌跡曲線的累積彎曲程度。本文將其作為地圖匹配的特征之一。

2.2 曲率積分的計算

假設γ：（α，β）→R2為二維平面曲線γ上有兩點a，b∈（α，β），a＜b，假設a、b兩點處的切向量為a和b，且在a、b之間的曲率積分值的取值在（－2π，2π）之間，則曲率積分值Γ可用切向量的方向角φ按式（5）計算

式中，deltφ（a，b）為曲線在a、b處的切向量的旋轉(zhuǎn)夾角。這里給出了二維平面上取值在（－2π，2π）之間的曲線曲率積分值的計算方法，由式（1）、式（5）可以將二維平面上曲線上兩點之間的曲率積分值用其兩點的切向量方位角計算出來。

2.2.1 曲率積分值的計算

假設曲線γ在計算機中被離散表示為n個點的序列〈p0p1…pn〉，序列中相鄰前后兩點之間向量為pi－1pi（1≤i≤n）。曲率以及曲率積分是在連續(xù)曲線上定義的，而在計算機中對連續(xù)的曲線（如道路的弧段）做了離散數(shù)字化處理，筆者用n個點中前后相鄰的兩個點形成的向量來近似估算該位置的切向量。因此，在這種局部范圍內(nèi)，曲線γ數(shù)字化的前后兩點之間的相對曲率κs方向不改變，并且其切向量的旋轉(zhuǎn)遠小于2π，這樣，根據(jù)式（5），被離散化后的曲率積分值可采用式（6）近似計算

式中，點pi處的切向量用向量pipi＋1來近似，每段的Γ值采用式（5）計算。

3 曲率積分約束的地圖匹配方法

3.1 地圖匹配方法框架

地圖匹配是在道路網(wǎng)絡所嵌入的地圖平面中完成，而地圖一般是在投影平面P上繪制，這里僅僅考慮GPS定位給出的投影平面坐標（x，y）。將道路網(wǎng)絡看作一個有向圖G（V，A），這里V為頂點集，代表道路網(wǎng)絡中路段端點及道路交叉口，A為弧段集，代表道路網(wǎng)絡中的路段。將每個弧段α∈A的非負長度值l作為其權重值。

浮動車的地圖匹配實際上是已知GPS采樣得到的浮動車軌跡T以及道路網(wǎng)絡G（V，A），在圖G中找到與真實軌跡ζ最近似的匹配路徑λ，如圖1所示。

圖1 浮動車軌跡點、真實軌跡及路徑Fig.1 Floating car track points，real trajectory and path

浮動車的地圖匹配問題實際上就是根據(jù)GPS采樣得到的不連續(xù)的點坐標序列T在道路網(wǎng)絡G中找到與T具有最大相似度的路徑λ。由于T是浮動車真實軌跡ζ采樣得到的，因此僅僅在采樣點處保留了部分特征。地圖匹配實際上就是要根據(jù)T中所保留的這部分特征在圖G中找到與之具有最大相似度的路徑λ。也即，浮動車地圖匹配問題也就是在平面道路網(wǎng)絡G中所有可能的路徑中尋找與GPS軌跡T具有的特征相似度最高的一條路徑。這實際上是一個最優(yōu)化問題。給定某種特征度量F，假設路徑λ的特征度量與GPS軌跡T的特征度量之間的相似度為S（FT，F(xiàn)λ），則浮動車的地圖匹配問題即為在G中所有可能的路徑中找到使得 ArgmaxλS（FT，F(xiàn)λ）成立的路徑λ。

在整個地圖匹配中采用的特征主要分為單個軌跡點的幾何特征和前后軌跡點之間的關聯(lián)特征。因此，求解地圖匹配問題的總體框架主要為以下步驟。

（1）根據(jù)單個軌跡點的位置和方向等單點特征，對每個軌跡點在路網(wǎng)中找到與之具有一定單點相似度的若干候選道路弧段。

（2）根據(jù)相鄰軌跡點之間的幾何、拓撲的關聯(lián)特征，在相鄰軌跡點的候選弧段對之間找到具有一定關聯(lián)相似度的子路徑（最終的匹配路徑是多條子路徑首尾相接所組成）。

（3）上一步形成的子路徑組合而成的所有可能路徑中，搜索出相似度S（FT，F(xiàn)λ）最大的路徑λ。

在目前的浮動車地圖匹配方法中，相似度S（FT，F(xiàn)λ）的定義方式中未考慮對于軌跡曲線彎曲程度的直接度量。真實軌跡曲線ζ在相鄰采樣點之間的曲率積分值實際上就是曲線在相鄰采樣點之間的一種彎曲度量。從整體上來看，浮動車真實軌跡曲線ζ的累積彎曲特征還是較好地保留在了采樣后的GPS軌跡T中，如圖1所示。本文的浮動車匹配方法就是基于前述匹配方法框架，利用保留在GPS軌跡T中的相鄰軌跡點之間的這種曲率積分值來約束完成地圖匹配。

3.2 地圖匹配的計算實現(xiàn)

3.1節(jié)中已經(jīng)給出了浮動車的地圖匹配方法的基本框架，本節(jié)說明在此框架下如何實現(xiàn)曲率積分約束的地圖匹配方法。目前的地圖匹配方法中關于方向特征的比較計算往往是單個軌跡點的速度方向與單個候選路段之間方向角的比較［9，11］。與此不同的是，本文方法主要是在計算相鄰軌跡點的關聯(lián)相似度時采用了曲率積分值來做約束。浮動車的GPS軌跡點實際上是車輛運動軌跡曲線的采樣點，相鄰兩個采樣點能夠包含的曲線特征信息不多，而在此兩點之間的曲線曲率積分值給出的是這一段曲線的累積彎曲特征。相鄰GPS軌跡點的匹配候選路段對之間的路徑的曲率積分值應該與GPS軌跡在相鄰GPS軌跡點之間的曲率積分之間具有最大相似度。因此，本文的匹配方法是先通過計算GPS軌跡T上相鄰兩點之間曲率積分估值，然后根據(jù)此估值來約束道路網(wǎng)絡中的路徑搜索匹配。本文地圖匹配方法主要是對3.1節(jié)給出的框架的詳細實現(xiàn)。本節(jié)中首先給出本文地圖匹配方法中的曲率積分計算方法，然后給出基于此的詳細地圖匹配實現(xiàn)步驟。

3.2.1 地圖匹配中的曲率積分近似計算

地圖匹配中主要需要計算GPS軌跡中相鄰點之間的曲率積分值和它們對應的候選匹配路段對之間的路徑的曲率積分值。本文先給出計算中用到的數(shù)學符號說明，然后分別說明如何計算路網(wǎng)中的路徑的曲率積分以及相鄰軌跡點之間的曲率積分。

浮動車行駛在道路網(wǎng)絡中，其行駛路徑λ應該具有與真實軌跡曲線一樣的幾何拓撲特征。假設路徑λ是由弧段序列ai＝（vi－1，vi）（1≤i≤k）組成，而在計算機中道路弧段ai由一序列離散的形狀點來表示，其中ai的第一個形狀點和最后一個形狀點坐標與節(jié)點vi－1和vi的坐標重合，即將路徑λ上的曲率積分值的計算分成道路弧段內(nèi)部和道路弧段之間的計算這兩部分，即

式中，Γai為路徑λ上一條道路弧段ai起點到終點的曲率積分值，其值可以由道路弧段的離散點（即形狀點）根據(jù)式（6）得到。deltφ（ai－1，ai）為路徑中相鄰弧段的旋轉(zhuǎn)夾角，其計算公式為

GPS軌跡中相鄰兩個軌跡點pi－1和pi之間的曲率積分，將pi－2pi－1作為pi－1處的近似切向量，將pipi＋1作為pi處的近似切向量，一般情況下采樣相鄰的GPS軌跡點不繞圈（即曲率積分值在（－2π，2π）之間變化），因此可以用式（9）估算其曲率積分值

式中，pi－2為pi－1前一個軌跡點，pi＋1為pi后一個軌跡點。再根據(jù)式（5）計算其曲率積分估值。

3.2.2 曲率積分約束的地圖匹配實現(xiàn)

3.2.2.1 單點相似度的實現(xiàn)

在3.1節(jié)匹配框架的步驟（1）中主要采用GPS軌跡點的位置作為單點匹配特征，以GPS點到候選路段之間的距離作為單點相似度量。設定距離閾值對于每個GPS軌跡點可以得到該距離閾值范圍內(nèi)的一個候選弧段集，在此集合中距離越近的弧段就具有越高的相似度。

3.2.2.2 關聯(lián)相似度的計算實現(xiàn)

在3.1節(jié)匹配計算框架的步驟（2）中，主要是計算相鄰的兩GPS軌跡點與其所對應的候選路段對之間的關聯(lián)相似度Stopo。本文的匹配方法中Stopo主要由長度相似度Srange與彎曲相似度Scurve求和來實現(xiàn)，其步驟如下。

（i）相鄰兩個軌跡點的關聯(lián)特征計算。關聯(lián)特征1，根據(jù)前后兩軌跡點的速度及兩點之間的間隔時間估算它們之間的行駛距離lrange；

關聯(lián)特征2，根據(jù)式（9）估算軌跡曲線在兩相鄰軌跡點之間的曲率積分值Γestm。

（ii）相鄰軌跡點所對應的候選路段對之間的路徑搜索。一般認為在浮動車采樣點時間間隔內(nèi)行駛最短路徑，因此兩相鄰軌跡點之間的關聯(lián)路徑搜索主要是計算出一對候選道路弧段和之間的最短路徑sp［19］并計算sp的長度lsp及曲率積分積。這里候選弧段為GPS軌跡中第i個軌跡點的候選路段集中的第j個弧段，候選弧段為相鄰的第i＋1個軌跡點的候選路段集中的第j′個弧段。

（iii）候選路段對的關聯(lián)特征計算。候選路段對的關聯(lián)特征主要是候選路段對之間的可能路徑的長度特征和彎曲特征。長度特征直接由步驟（2）確定的路徑長度lsp得到，彎曲特征根據(jù)公式（7）計算該路徑的曲率積分Γsp得到。

（iv）關聯(lián)相似度?？赡芷ヅ渎窂降拈L度相似度Srange：根據(jù)步驟（i）、步驟（ii）中得到的lsp、lrange，計算兩者的絕對值來確定其相似度Srange。

可能匹配路徑的彎曲程度相似度Scurve：根據(jù)步驟（i）、步驟（ii）中得到的Γestm、Γsp，計算｜Γsp－Γestm｜來確定彎曲程度相似度Scurve。

3.2.2.3 全局搜索策略

在3.1節(jié)地圖匹配框架中的步驟（3）中采用有向無環(huán)圖實現(xiàn)最大相似度路徑搜索，每個軌跡點的候選路段構成圖的節(jié)點，相鄰軌跡點之間的候選路段對之間最短路徑作為有向無環(huán)圖的邊，將相鄰軌跡點之間的候選路段對的關聯(lián)相似度以及其所含兩個候選路段的單點相似度之和作為有向無環(huán)圖的邊的權重。用有向無環(huán)圖的拓撲序算法來搜索最長路徑［7］，該路徑對應的匹配道路弧段集即為GPS軌跡的地圖匹配結(jié)果。

3.2.3 相似度的函數(shù)

3.2.2節(jié)中的相似度的計算實際上就是將比較值通過一定函數(shù)映射到一個權重值范圍，即可以將單點相似度中介紹的距離值以及關聯(lián)相似度中介紹的長度及曲率積分的兩個比較差值通過函數(shù)映射到一個權重范圍上［20］。本文相似度的映射對于距離和長度差值采用冪函數(shù)，對于曲率積分采用三角函數(shù)，這3種相似度的權重范圍均在1～10之間。

4 試驗

4.1 試驗數(shù)據(jù)

本文采用兩組浮動車GPS軌跡數(shù)據(jù)集作為地圖匹配方法的試驗數(shù)據(jù)，這些軌跡數(shù)據(jù)中主要包含浮動車輛的經(jīng)緯度、采樣時刻、速度等屬性信息。

數(shù)據(jù)集1為深圳市出租車浮動車數(shù)據(jù)。這里，出租車浮動車數(shù)據(jù)為隨機選擇的10輛出租車GPS軌跡數(shù)據(jù)（見圖2）。每輛出租車選擇不同數(shù)目的連續(xù)采樣GPS軌跡點來參與地圖匹配（見表1）。出租車的GPS采樣間隔為30s（2014年3月22日采集）。

圖2 試驗數(shù)據(jù)集1數(shù)據(jù)示例Fig.2 Samples of data set 1for experiments

表1 數(shù)據(jù)集1中不同出租車的軌跡點數(shù)目Tab.1 Numbers of different taxis in data set 1

數(shù)據(jù)集2為深圳市公交車浮動車數(shù)據(jù)。該數(shù)據(jù)集為兩輛公交車分別在兩條路線上按原始采樣間隔（20s）連續(xù)采集得到的GPS軌跡數(shù)據(jù)（2012年2月1日）。其中，公交車路線為兩種不同固定路線，一種為在甲、乙兩目的地之間往返，一種為環(huán)線行駛，本文的公交車路線分別選擇這兩種類型公交線路。所選擇的公交線路為A（深圳公交B829，運營時間為6：30—22：15）和B（深圳公交707線路，運營時間為6：00—23：00），如圖3所示。其所經(jīng)過的道路主要有廣深公路、西鄉(xiāng)立交、西鄉(xiāng)大道等?；谠疾蓸娱g隔GPS軌跡數(shù)據(jù)進一步抽稀得到40s、60s、80s及100s間隔的公交車GPS軌跡數(shù)據(jù)。

圖3 試驗數(shù)據(jù)集2數(shù)據(jù)示例Fig.3 Samples of data set 2for experiments

兩個數(shù)據(jù)集中的GPS軌跡數(shù)據(jù)基本都通過了城市中典型的較復雜道路，比如城市快速路、立交匝道、主輔路等。

4.2 試驗及其結(jié)果

本文試驗主要將曲率積分約束的匹配方法與ST算法比較。ST算法主要全面地考慮了多種匹配限制條件并得到相對比較好的匹配效果［7］。該方法在軌跡的單點匹配時采用距離，在相鄰點之間的關聯(lián)匹配時采用道路拓撲及速度來實施匹配限制。該方法是目前文獻引用率較高且比較經(jīng)典的一種低頻GPS浮動車地圖匹配方法。曲率積分約束的匹配方法即為本文前面所詳細論述的匹配方法，此方法除了在單點時采用距離特征，在關聯(lián)匹配時采用道路拓撲特征之外，還采用了相鄰軌跡點之間的軌跡彎曲程度來約束關聯(lián)匹配。試驗采用兩種不同的浮動車匹配算法分別針對4.1節(jié)介紹的兩組浮動車GPS軌跡數(shù)據(jù)來實施。對于數(shù)據(jù)集1，在固定采樣間隔下不同車輛、不同軌跡點數(shù)目分別實施兩種地圖匹配方法。對于數(shù)據(jù)集2，不同匹配方法針對不同采樣間隔總共實施了20次的軌跡匹配試驗。

本文試驗主要考察兩種不同的方法對于不同浮動車GPS軌跡數(shù)據(jù)集其匹配結(jié)果的正確性及穩(wěn)定性。為此，本文定義軌跡匹配的錯誤率與錯誤程度（長度）兩個指標來衡量。每次地圖匹配試驗的錯誤率為該次匹配的錯誤匹配軌跡點數(shù)目與軌跡點總數(shù)目之比，即

該指標給出了浮動車地圖匹配的錯誤率，錯誤率越大表明正確匹配的軌跡點越少，匹配方法效果越差。錯誤程度（長度）為錯誤匹配軌跡點處錯誤匹配的路徑與正確路徑的長度比，本文試驗中一次軌跡匹配中的錯誤程度（長度）采用所有錯誤匹配點處該值的平均值，即

式中，Nerr為錯誤匹配點數(shù)。該值反映了浮動車軌跡地圖匹配結(jié)果錯誤的地方在長度上平均偏離正確路徑的程度。該值衡量了匹配結(jié)果與正確路徑的一種符合程度。該值越大，則匹配結(jié)果符合正確路徑的程度越差。

圖4給出了本文方法與ST方法在數(shù)據(jù)集1上匹配錯誤率的柱狀比較分析圖。整體上來看本文方法的錯誤率基本都在5%以內(nèi)，有兩項數(shù)據(jù)甚至達到了1%以下。相比較而言，在不同的軌跡數(shù)據(jù)上ST方法的匹配錯誤率均大于本文方法的。從本組數(shù)據(jù)的地圖匹配結(jié)果來看，本文給出的曲率積分約束的地圖匹配方法其匹配結(jié)果在正確率上優(yōu)于經(jīng)典的ST方法。

圖4 數(shù)據(jù)集1的出租車軌跡地圖匹配結(jié)果比較Fig.4 Map matched results of taxi trajectories in data set 1

表2給出了數(shù)據(jù)集2中的20次（4組）浮動車軌跡地圖匹配試驗結(jié)果。軌跡匹配試驗根據(jù)試驗方法及試驗線路的不同主要分為4組，軌跡編號為”＃－＃”，這里第1個序號為組號，第2個編號為組內(nèi)編號。小組編號中，第0、1組為公交線路A的浮動車軌跡數(shù)據(jù)；2、3組為公交線路B的浮動車軌跡數(shù)據(jù)；其中0、2組采用曲率的匹配方法，1、3組采用ST算法實施匹配。組內(nèi)編號反映的是試驗中采樣間隔的不同，每組內(nèi)分別測試了20s、40s、60s、80s、100s采樣間隔下的效果。

表2 公交浮動車地圖匹配分組試驗結(jié)果Tab.2 Experimental results of map matching for floating buses

圖5給出了數(shù)據(jù)集2中兩種方法在兩個錯誤指標上的試驗結(jié)果比較。圖中橫軸為浮動車GPS軌跡采樣間隔，縱軸為錯誤率，曲線擬合出了錯誤率隨著采樣時間而變化的曲線。圖4為公交路線A上浮動車軌跡匹配的試驗結(jié)果，圖5為公交線路B上的浮動車軌跡匹配的試驗結(jié)果。圖中曲線上每個結(jié)果點的半徑大小正比于其錯誤程度Elen的大小。總體上看，兩種匹配方法隨著采樣間隔的變大，錯誤率均呈上升趨勢。在兩種不同行駛線路上ST方法在不同采樣間隔下的錯誤率均高于本文方法。圖5中，在采樣間隔變大的情況下，本文方法的錯誤率上升較緩慢，這說明將浮動車軌跡曲線的曲率特征用來約束地圖匹配可以抑制隨著采樣間隔變大而產(chǎn)生的部分錯誤。但是，由于采樣間隔變大軌跡點中的信息損失掉得越來越多，因此總體上看錯誤率仍是呈上升趨勢。

圖5 不同匹配方法錯誤指標比較Fig.5 Comparison of error indicators for different map－matching methods

圖6將上述公交路線A和B的結(jié)果指標在一張圖上繪出。陰影部分擬合出了不同方法在兩種固定路線上錯誤率變動幅度的緩沖范圍。從圖中可以看出在不同的行駛路線中以及不同采樣間隔下兩種匹配方法錯誤率的波動幅度。圖6結(jié)果表明，相比較于經(jīng)典的ST方法，采用曲率約束的地圖匹配方法在不同情況下其錯誤率變化的幅度較小，其匹配結(jié)果錯誤率在不同情況下的變化具有一定的穩(wěn)定性。

圖6 不同匹配方法錯誤趨勢比較Fig.6 Comparison of error trends for different map－matching methods

圖7給出了數(shù)據(jù)集2上兩種不同匹配方法的錯誤程度比較。從圖7中可以看出整體上具有曲率約束的匹配結(jié)果錯誤程度好于ST方法的。曲率約束采用了衡量軌跡曲線彎曲程度的特征，因此不會產(chǎn)生彎曲形狀上和真實路徑相差太大的匹配結(jié)果，從而抑制了一些長度上極大偏離正確軌跡路徑的匹配結(jié)果的發(fā)生。

圖7 不同匹配方法錯誤程度比較Fig.7 Comparison of error levels for different map－matching methods

4.3 分析與討論

本文試驗中的ST方法基本包含了傳統(tǒng)浮動車地圖匹配中采用的一些幾何、拓撲特征［7］。本文提出的浮動車地圖匹配方法主要是利用曲率積分值直接描述兩個相鄰軌跡點之間的軌跡曲線的彎曲程度，這種彎曲程度相比較于傳統(tǒng)匹配方法中使用的幾何拓撲特征更加直接的描述了軌跡在路網(wǎng)中的彎曲程度。前面的4.2節(jié)的試驗結(jié)果表明了這種對彎曲程度的直接度量在路網(wǎng)數(shù)據(jù)中實施地圖匹配是更加有效的。圖8給出了一個本文方法匹配結(jié)果與ST方法匹配結(jié)果差異比較。圖中在軌跡點2處兩種匹配方法的匹配結(jié)果產(chǎn)生了差異。在該位置處本文方法將軌跡點2匹配到直行道路上，而ST方法將軌跡點2匹配至右轉(zhuǎn)彎道上。ST方法主要采用距離、道路拓撲（網(wǎng)絡距離）及速度約束來實現(xiàn)地圖匹配，而軌跡2位置處，道路拓撲關系上從右轉(zhuǎn)彎道彎回直行道路的道路網(wǎng)絡距離與直行道路的網(wǎng)絡距離差別不大；直行道路和彎道的等級一致，且都在路口，其行駛速度近似；然而在歐氏空間距離近似程度上，軌跡點2由于GPS定位誤差，其位置非常接近于右轉(zhuǎn)彎道，ST方法在地圖匹配中綜合考慮這3方面的約束條件，由于網(wǎng)絡拓撲以及速度上直行和右轉(zhuǎn)彎道差別不大，而在歐氏距離上軌跡點2明顯更接近于右轉(zhuǎn)彎道，因此其結(jié)果最終匹配到右轉(zhuǎn)彎道上。而本文方法，引入曲率積分的約束作用后，其積分估值在軌跡點2處接近于直線的積分值，而從直行道路到右轉(zhuǎn)彎道的路徑曲率積分接近90°，這種差異弱化了軌跡點2在空間距離上接近于右轉(zhuǎn)彎道的作用，在整體優(yōu)化策略下，使得軌跡點2最終匹配到了直行道路上。圖8中軌跡點2的道路匹配情形比較具有代表性。我國各城市經(jīng)濟快速發(fā)展，道路更新速度很快，各種道路結(jié)構比較復雜；同時，當前地理信息服務中的路網(wǎng)模型趨向于更加精細化的表達。因此，在當前的交通道路數(shù)據(jù)中，車道、匝道等在復雜道路環(huán)境中往往表達為單獨的數(shù)字化曲線，這就導致地圖匹配在同等相似度的約束下相近似的候選道路路段增多，匹配的正確率會下降。圖8結(jié)果表明，在包含右轉(zhuǎn)匝道的復雜路口處，本文的方法通過曲率積分的約束，可以得到正確的地圖匹配結(jié)果。

另外，隨著浮動車采樣間隔的增加，相鄰軌跡點之間的軌跡位置信息會損失得越來越多。本文匹配方法采用距離、道路拓撲、累積彎曲程度等特征來實施地圖匹配可以幫助在信息不完整的GPS軌跡中恢復路徑信息并實施地圖匹配。圖5和圖6中，可以看到采樣間隔增加導致錯誤匹配率的上升，在100s的采樣間隔以內(nèi)，曲率積分的約束還是抑制了由于信息損失而導致的錯誤率上升。曲率積分給出的是兩相鄰軌跡點之間累積的彎曲程度并不是在一點處的瞬時彎曲值。在本文試驗的采樣間隔以內(nèi)總體上比較正確地估計了兩點之間的累積彎曲程度，對錯誤率上升起到抑制作用。但是隨著采樣間隔增加到大于100s，GPS軌跡損失的信息將會導致關聯(lián)匹配中的恢復路徑計算（比如，計算相鄰軌跡點在道路網(wǎng)絡中行駛最短路徑，計算相鄰兩軌跡點之間累積彎曲度）變得不可靠，從而錯誤率變大。因此在更大采樣間隔下更加有效地實現(xiàn)正確的浮動車地圖匹配是未來工作的一個方向。

圖8 不同方法匹配結(jié)果的比較示例Fig.8 Comparison example for map－matching results of different methods

5 結(jié) 論

本文給出了一種曲率積分值約束下的GPS浮動車地圖匹配方法。曲率度量了平面曲線在一點處瞬時彎曲程度，曲率積分則度量了平面曲線在一段曲線上的累積彎曲程度。本文以曲率積分對于軌跡曲線的這種度量作為浮動車軌跡中相鄰點之間的前后關聯(lián)特征來實施地圖匹配。通過兩組不同試驗數(shù)據(jù)的比較分析表明，這種基于曲率特征約束的浮動車地圖匹配方法在不同類型行駛路線以及不同采樣時間間隔下可以提高匹配正確性及匹配穩(wěn)定性。本文方法比較適用于采樣間隔在100s以內(nèi)的低頻GPS軌跡數(shù)據(jù)。本文方法的結(jié)果可應用于海量低頻GPS軌跡數(shù)據(jù)挖掘及交通出行分析等方面。

［1］LI Qingquan，LI Deren.Big Data GIS［J］.Geomatics and Information Science of Wuhan University，2014，39（6）：641－644，666.（李清泉，李德仁.大數(shù)據(jù)GIS［J］.武漢大學學報：信息科學版，2014，39（6）：641－644，666.）

［2］LU Feng，ZHANG Hengcai.Big Data and Generalized GIS［J］.Geomatics and Information Science of Wuhan University，2014，39（6）：645－654.（陸鋒，張恒才.大數(shù)據(jù)與廣義GIS［J］.武漢大學學報：信息科學版，2014，39（6）：645－654.）

［3］GREENFELD J S.Matching GPS Observations to Locations on a Digital Map［C］∥Transportation Research Board 81st Annual Meeting.Washington D.C.：［s.n.］，2002.

［4］LI Liang，QUDDUS M，ZHAO Lin.High Accuracy Tightlycoupled Integrity Monitoring Algorithm for Map－matching［J］.Transportation Research Part C：Emerging Technologies，2013，36：13－26.

［5］SU Jie，ZHOU Dongfang，YUE Chunsheng.Real－time Mapmatching Algorithm in GPS Navigation System for Vehicles［J］.Acta Geodaetica et Cartographica Sinica，2010，30（3）：252－256.（蘇潔，周東方，岳春生.GPS車輛導航中的實時地圖匹配算法［J］.測繪學報，2001，30（3）：252－256.）

［6］NEWSON P，KRUMM J.Hidden Markov Map Matching Through Noise and Sparseness［C］∥Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.Seattle，Washington：ACM，2009：336－343.

［7］LOU Yin，ZHANG Chengyang，ZHENG Yu，et al.Map－Matching for Low－Sampling－Rate GPS Trajectories［C］∥Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.Seattle，Washington，ACM，2009：352－361.

［8］BRAKATSOULAS S，PFOSER D，SALAS R，et al.On Map－Matching Vehicle Tracking Data［C］∥Proceedings of the 31st International Conference on Very Large Databases.VLDB Endowment，2005：853－864.

［9］WANG Meiling，CHENG Lin.Study on Map－matching Algorithm for Floating Car［J］.Acta Geodaetica et Cartographica Sinica，2012，41（1）：133－138.（王美玲，程林.浮動車地圖匹配算法研究［J］.測繪學報，2012，41（1）：133－138.）

［10］LI Qingquan，HUANG Lian.A Map Matching Algorithm for GPS Tracking Data［J］.Acta Geodaetica et Cartographica Sinica，2010，39（2）：207－212.（李清泉，黃練.基于GPS軌跡數(shù)據(jù)的地圖匹配算法［J］.測繪學報，2010，39（2）：207－212.）

［11］ZHANG Wei，XU Jianmin，LIN Mianfeng.Map Matching Algorithm of Large Scale Probe Vehicle Data［J］.Journal of Transportation Systems Engineering and Information Technology，2007，7（2）：39－45.（章威，徐建閩，林綿峰.基于大規(guī)模浮動車數(shù)據(jù)的地圖匹配算法［J］.交通運輸系統(tǒng)工程與信息，2007，7（2）：39－45.）

［12］LI Qingquan，HU Bo，YUE Yang.Flowing Car Data Mapmatching Based on Constrained Shortest Path Algorithm［J］.Geomatics and Information Science of Wuhan University，2013，38（7）：805－808.（李清泉，胡波，樂陽.一種基于約束的最短路徑低頻浮動車數(shù)據(jù)地圖匹配算法［J］.武漢大學學報：信息科學版，2013，38（7）：805－808.）

［13］ZHENG Nianbo，LU Feng，LI Qingquan.Dynamic Multi－scale Road Network Data Model for Navigation［J］.Acta Geodaetica et Cartographica Sinica，2010，39（4）：428－434.（鄭年波，陸鋒，李清泉.面向?qū)Ш降膭討B(tài)多尺度路網(wǎng)數(shù)據(jù)模型［J］.測繪學報，2010，39（4）：428－434.）

［14］LI Qingquan，XU Jinghai，ZHENG Nianbo，et al.Function Based Navigation Data Model［J］.Geomatics and Information Science of Wuhan University，2007，32（3）：266－270.（李清泉，徐敬海，鄭年波，等.基于功能的導航數(shù)據(jù)模型［J］.武 漢 大 學 學 報： 信 息 科 學 版，2007，32（3）：266－270.）

［15］ZHANG Yun，LI Qingquan，CAO Xiaohang，et al.An Algorithm for Detecting the Geometric Difference between the Road Networks［J］.Acta Geodaetica et Cartographica Sinica，2008，37（4）：521－525.（張韻，李清泉，曹曉航，等.一種道路網(wǎng)信息幾何差異檢測算法［J］.測繪學報，2008，37（4）：521－525.）

［16］ZHENG Nianbo，LU Feng.Improved Navigation Road Network Data Model and Its Organization Method［J］.China Journal of Highway and Transport，2011，24（2）：96－102.（鄭年波，陸鋒.導航路網(wǎng)數(shù)據(jù)改進模型及其組織方法［J］.中國公路學報，2011，24（2）：96－102.）

［17］MEI Xiangming，HUANG Jingzhi.Differential Geometry［M］.4th ed.Beijing：Higher Education Press，2008.（梅向明，黃敬之.微分幾何［M］.第四版.北京：高等教育出版社，2008.）

［18］MENG Daoji，LIANG Ke.Differential Geometry［M］.Beijing：Science Press，2002.（孟道驥，梁科.微分幾何［M］.北京：科學出版社，2002.）

［19］DIJKSTRA E W.A Note on Two Problems in Connexion with Graphs［J］.Numerische Mathematik，1959，1（1）：269－271.

［20］QUDDUS M A.High Integrity Map Matching Algorithms for Advanced Transport Telematics Applications［D］.London：Imperial College London Department of Civil and Environmental Engineering，2006.