浮動(dòng)車快速道路匹配算法

耿小峰，王山東，季 軍

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

0 引 言

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

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

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

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

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

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

圖1 投影匹配原理圖

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

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

2 浮動(dòng)車快速地圖匹配算法

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

2.1 道路點(diǎn)元

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

圖2 組成線的點(diǎn)元

2.2 點(diǎn)線相關(guān)度

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

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

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

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

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

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

(1)獲取組成每條道路中心線圖元的點(diǎn)元坐標(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點(diǎn)坐標(biāo)P(xp，yp)與搜索范圍相比較，如式(4)所示:

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

本文采用馬鞍山市出租車GPS數(shù)據(jù)對(duì)算法進(jìn)行驗(yàn)證。為了驗(yàn)證算法的有效性，在數(shù)據(jù)獲取之前，已對(duì)數(shù)據(jù)進(jìn)行篩選，將數(shù)據(jù)中速度小于0或大于150的速度值作為GPS接收機(jī)定位異常點(diǎn)處理。因此，本文中用于驗(yàn)證的浮動(dòng)車單車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ù)定位點(diǎn)的匹配速度與匹配效率，時(shí)間為測(cè)試10次的時(shí)間所取的平均值。

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

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

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

表4 三種地圖匹配算法對(duì)2000個(gè)點(diǎn)匹配的性能數(shù)據(jù)

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

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

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

4 結(jié) 語

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

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

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

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

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

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

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

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

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

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

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