耿小峰，王山東，季 軍

(1.河海大學(xué) 地球科學(xué)與工程學(xué)院，江蘇南京 210098；2.南通市海籍調(diào)查測量中心，江蘇 南通226006)

0 引 言

浮動車也稱GPS探測車，是近年來國際智能交通系統(tǒng)(ITS)中所采用的獲取城市道路交通狀態(tài)的重要途徑和有效方式[1]。浮動車可以實時的采集車輛的瞬時速度、坐標(biāo)以及瞬時方向角等信息，通過對車輛的運行信息進(jìn)行分析，可以實時的對其監(jiān)測并估計真實的道路交通狀態(tài)。而快速地對大規(guī)模的浮動車進(jìn)行道路匹配是依據(jù)浮動車對道路通行狀況進(jìn)行監(jiān)測的關(guān)鍵算法之一[2]。

現(xiàn)有地圖匹配算法包括基于模糊邏輯的地圖匹配算法、基于D-S證據(jù)理論的地圖匹配算法、基于權(quán)重的匹配算法、曲線擬合匹配法[3-6]等，它們往往只注重匹配精度、沒有考慮匹配的效率以及浮動車的方向，尤其在實時性方面無法滿足浮動車道路交通狀態(tài)監(jiān)測的要求。而基于投影的地圖匹配算法[7-8]、基于道路緩沖區(qū)分析的匹配算法[9]邏輯簡單、易于實現(xiàn)，滿足浮動車大數(shù)據(jù)量匹配實時性的要求，但前者在彎道或交叉路口等道路密集的路況識別準(zhǔn)確率降低、易造成識別混亂；后者的缺點是只能確定浮動車所在道路，無法確定浮動車在道路的具體位置。因此，本文在綜合考慮匹配準(zhǔn)確性和實時性的基礎(chǔ)上，提出了浮動車快速道路匹配算法。

1 傳統(tǒng)快速地圖匹配算法

1.1 基于投影的地圖匹配算法

算法思想:將浮動車GPS定位點垂直投影到與該定位點相關(guān)的路段上，計算垂直投影距離 di，及車輛行駛方向與道路間的夾角 θi，如圖1所示，P點為待匹配的GPS定位點，L1和L2表示GPS點附近的道路中心線。選出 di和θi值小于給定閾值的所有道路，并根據(jù)式(1)計算各候選道路的距離度量值Di。

式中:Wd，Wθ分別是投影距離和方向夾角的權(quán)值。在所有候選道路中選擇距離度量值最小的作為匹配道路，即認(rèn)為車輛正在該道路上行駛，選取最小垂線段距離的交點作為匹配點。算法最后將車輛在匹配道路上的投影點作為車輛的當(dāng)前位置。

圖1 投影匹配原理圖

1.2 基于道路緩沖區(qū)的匹配算法

首先依據(jù)路寬和GPS精度生成不同寬度的緩沖區(qū)，然后將浮動車數(shù)據(jù)與道路圖層緩沖區(qū)相匹配。匹配時，首先確定浮動車數(shù)據(jù)定位點所處的緩沖區(qū)個數(shù)，當(dāng)只有1個緩沖區(qū)區(qū)域時，可將浮動車數(shù)據(jù)定位點直接匹配到緩沖區(qū)區(qū)域?qū)?yīng)的道路上；當(dāng)緩沖區(qū)區(qū)域個數(shù)大于1時，則說明浮動車數(shù)據(jù)定位點在兩個或兩個以上緩沖區(qū)區(qū)域的疊加區(qū)域內(nèi)，即浮動車定位點位于交叉口處，通過比較浮動車數(shù)據(jù)定位點的方向角與連接交叉口的道路的直線段的方向角之間差的絕對值，將浮動車數(shù)據(jù)匹配到絕對值最小的直線段所對應(yīng)的道路上。

2 浮動車快速地圖匹配算法

據(jù)前面的兩種基本算法可知，基于投影的地圖匹配算法因其邏輯簡單使其匹配速度較快、實時性較好，但在十字路口等復(fù)雜路段的匹配準(zhǔn)確度較差；基于道路緩沖區(qū)分析的匹配算法在十字路口等復(fù)雜路段的匹配準(zhǔn)確度與投影的地圖匹配算法相比有一定的改善，但該算法無法確定浮動車所在道路的詳細(xì)位置，且在構(gòu)建緩沖區(qū)時靈活性較差，不利于數(shù)據(jù)維護(hù)，因此很難應(yīng)用于實際工程中?；谏鲜鏊惴ǖ娜秉c，本文在算法中融入了道路點元、點線相關(guān)度[10]的概念，使得算法在準(zhǔn)確性、實時性方面滿足工程的應(yīng)用需求。

2.1 道路點元

矢量電子地圖中任意線圖元都是由一系列點元組成，每一點元的坐標(biāo)(xi，yi)位置都是已知的。直線路段用線段表示，曲線路段之間用折線近似表示，如圖2所示:一條曲線道路由組成它的多個點元連接而成。

圖2 組成線的點元

2.2 點線相關(guān)度

設(shè)GPS定位點P的坐標(biāo)為(x，y)，路段AB兩端坐標(biāo)分別為 A(x1，y1)，B(x2，y2)，則點 P和路段AB的點線相關(guān)度r計算公式如下:

圖3 點線相關(guān)度r示意圖

點P與路段AB的相對位置如圖3所示，兩條虛線分別為過A點和B點的垂直于x軸的直線，以這兩條虛線為界，將線段AB所在的區(qū)域分為區(qū)域 Ⅰ、區(qū)域 Ⅱ和區(qū)域 Ⅲ，圖中點P1、點P2、點P3分別表示點P與路段AB的三種相對位置。當(dāng)點P位于區(qū)域Ⅰ時，由公式(2)計算出的r取值范圍為:r＜0；當(dāng)點 P位于區(qū)域 Ⅱ時，r范圍為:0≤r≤1；當(dāng)點P位于區(qū)域 Ⅲ時，r取值范圍為:r＞1。

當(dāng)r＜0時，取點P到路段AB的距離為線段PA的長度；當(dāng)r＞1時，取點P到路段AB的距離為線段PB的長度；當(dāng)r取其他值的時候，則直接根據(jù)點到直線的距離公式進(jìn)行計算。當(dāng)確定了GPS定位點到路段集合中各路段的距離后，選出距離值最小的路段，取其為當(dāng)前行駛路段進(jìn)行投影。投影時遵循車輛始終在路段上行駛的原則，根據(jù)r取值來確定投影點:當(dāng)r＜0時，投影點為 A；當(dāng) r＞1時，投影點為B；當(dāng)r取其他值時，投影點為P在路段AB上的垂足。

2.3 基于道路線圖元地圖匹配算法

首先獲取組成道路中心線圖元的點元坐標(biāo)、道路寬度，根據(jù)道路點元坐標(biāo)、道路寬度以及定位點GPS的誤差精度確定道路的矩形搜索范圍，以及道路折線段的方向角；然后將GPS定位點與搜索范圍進(jìn)行匹配。在地圖匹配時，首先判斷浮動車GPS定位點所在搜索范圍的個數(shù)，當(dāng)個數(shù)為1時，將浮動車數(shù)據(jù)直接匹配到該搜索范圍所在的道路上；當(dāng)搜索個數(shù)大于1時，說明浮動車定位點在兩條或者兩條以上道路的搜索范圍內(nèi)，說明可能是交叉路口，也可能是相距很近的路段。若在交叉路口時，通過比較定位點的方向角與道路折線段方向角之間差的絕對值，將浮動車匹配到絕對值最小的道路上；若在相距很近的路段時，通過GPS定位點與道路折線間的相關(guān)度確定點到線的距離，將浮動車匹配到距離最小的道路上。主要算法步驟如下:

(1)獲取組成每條道路中心線圖元的點元坐標(biāo)(xi，yi)，道路寬度 Ri，確定每條道路在坐標(biāo) x，y 方向上的最小 、最大值 xmin，xmax，ymin，ymax，以及道路折線段的方向角Ai；

(2)依據(jù)緩沖區(qū)思想確定道路的矩形搜索范圍，因此:

式中:Ri為道路寬度，RΔ為GPS定位精度，本文采用的GPS定位精度為15 m；

(3)將定位GPS點坐標(biāo)P(xp，yp)與搜索范圍相比較，如式(4)所示:

記錄符合上式條件的矩形搜索范圍的個數(shù)n1以及相對應(yīng)的路段編號；

(4)當(dāng)n1=0時，表示無符合條件的路段，把未匹配的定位點作為異常點刪除；

當(dāng)n1=1時，表示唯一匹配路段，進(jìn)入步驟6；

當(dāng)n1＞1時，表示有多條符合條件的路段，進(jìn)行步驟5；

(5)比較浮動車定位點方向角與符合條件路段的方向角之差的絕對值，與已給定的閾值相比較，當(dāng)滿足式(5)時，說明與路段方向相同，記為1；當(dāng)滿足式(6)時，說明與路段方向相反，記為0；記錄符合滿足式(5)或者式(6)條件的總個數(shù)n2；

式中:Ap為定位點方向角；AΔ為已知閾值，本文取30°；

(6)計算P點與符合條件路段的點線相關(guān)度ri，并根據(jù)相關(guān)度ri來確定定位點P到路段的距離di以及點在路段上的投影點P′；

(7)當(dāng)n2=1時，表示已找到匹配路段，進(jìn)入步驟8；

當(dāng)n2＞1時，表示有多條符合條件的路段，進(jìn)入步驟7；

(8)選取定位點到路段距離di最小的路段作為匹配道路；

(9)將投影點作為車輛的當(dāng)前位置加以顯示。

3 實驗結(jié)果及分析

本文采用馬鞍山市出租車GPS數(shù)據(jù)對算法進(jìn)行驗證。為了驗證算法的有效性，在數(shù)據(jù)獲取之前，已對數(shù)據(jù)進(jìn)行篩選，將數(shù)據(jù)中速度小于0或大于150的速度值作為GPS接收機(jī)定位異常點處理。因此，本文中用于驗證的浮動車單車GPS數(shù)據(jù)(如表1所示)可直接進(jìn)行數(shù)據(jù)匹配。

表1 部分單車GPS數(shù)據(jù)

表2 單車數(shù)據(jù)匹配結(jié)果

匹配的結(jié)果見表2所示，GPS數(shù)據(jù)已匹配到相應(yīng)的路段，表中的方向值1表示與路段方向相同，詳見圖4所示，行車方向與路段方向一致。

圖4 單車匹配效果圖

表3給出了不同數(shù)據(jù)定位點的匹配速度與匹配效率，時間為測試10次的時間所取的平均值。

表3 不同數(shù)據(jù)量的匹配率

可以看出，浮動車快速匹配算法隨著GPS數(shù)據(jù)量的成倍增多，匹配時間基本成倍增長，匹配時間始終小于0.1 s，滿足匹配實時性的需要；且匹配率基本都保持在92%左右，滿足浮動車數(shù)據(jù)匹配準(zhǔn)確性的要求。

表4為文中提到三種快速匹配算法用2 000條數(shù)據(jù)匹配10次的結(jié)果對照表。

表4 三種地圖匹配算法對2000個點匹配的性能數(shù)據(jù)

從表4可以看出，三種匹配算法在匹配率方面非常相近，但浮動車快速匹配算法與緩沖區(qū)匹配法較投影匹配法在匹配時間上有著絕對的優(yōu)勢?？紤]到緩沖區(qū)算法無法定位到詳細(xì)位置、數(shù)據(jù)維護(hù)復(fù)雜的弊端，因此，浮動車快速匹配算法更符合實際工程應(yīng)用中浮動車大數(shù)據(jù)量匹配實時性的要求。

實驗中所記錄的時間是程序去掉數(shù)據(jù)初始化后數(shù)據(jù)匹配的計算時間，時間因機(jī)器配置、路網(wǎng)情況而定。用于匹配的道路路段共有1 577段，點元數(shù)據(jù)為11 335個。

操作系統(tǒng):Windows XP，CPU處理器:Intel(R)Pentium(R)Dual 1.79 GHz，內(nèi)存:2GB。

4 結(jié) 語

文中提出的浮動車快速匹配算法在處理大規(guī)模GPS數(shù)據(jù)時，表現(xiàn)出良好的實用性，在保證高精度的同時，也滿足實時性的要求，此算法已在馬鞍山市公安交通地理信息系統(tǒng)中得到驗證。鑒于城市發(fā)展的特點，立交橋的匹配是不可忽視的問題，也是一個難點，將是下一步研究的重點。

[1]王東柱，董繼明，李亞檬，等.浮動車數(shù)據(jù)中零速度點數(shù)據(jù)地圖匹配方法[J].交通信息與安全，2009，27(6):38-42.

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

[3]孫棣華，王春麗.基于模糊模式識別的車輛定位地圖匹配算法[J].計算機(jī)工程與應(yīng)用，2007，43(25):227-230.

[4]胡 林，谷正氣，楊 易，等.基于權(quán)值D-S證據(jù)理論的車輛導(dǎo)航地圖匹配[J].中國公路學(xué)報，2008，21(2):116-120.

[5]陳佳瑜，肖桂榮.基于權(quán)重的地圖匹配算法[J].計算機(jī)工程與應(yīng)用 ，2005，41(11):168-170.

[6]周 穎，程蔭杭.基于曲線擬合的地圖匹配算法[J].交通運輸系統(tǒng)工程與信息，2004，4(2):68-70.

[7]陳 嘉，胡繼華，張飛舟.面向車輛監(jiān)控導(dǎo)航的地圖匹配算法研究[J].北京大學(xué)學(xué)報，2009，45(2):299-305.

[8]王冬暉，許占文.一種基于類投影的地圖匹配算法[J].沈陽工業(yè)大學(xué)學(xué)報，2003，25(5):433-436.

[9]賴云波，孫棣華，廖孝勇，等.基于道路緩沖區(qū)分析的地圖匹配算法[J].計算機(jī)應(yīng)用研究，2011，28(9):3312-3314.

[10]唐思靜.車輛定位導(dǎo)航系統(tǒng)中地圖匹配和路徑規(guī)劃算法研究[D].西安:西安電子科技大學(xué)，2009:30-32.