基于特征權(quán)重的地圖匹配算法研究

張 賀 孫婉瑩 宋國平

（1.吉林開放大學(xué)，吉林 長春 130000；2.長春市公安局，吉林 長春 130000）

0 引言

隨著信息技術(shù)的不斷發(fā)展，GPS 衛(wèi)星定位技術(shù)和地理信息系統(tǒng)（GIS）日漸成熟，基于GIS/GPS 的車輛導(dǎo)航系統(tǒng)已經(jīng)廣泛應(yīng)用于車載監(jiān)控及定位領(lǐng)域。在車輛導(dǎo)航系統(tǒng)中，GPS 定位數(shù)據(jù)誤差和電子地圖精度誤差成為影響地圖匹配精度的關(guān)鍵因素，GPS 定位點(diǎn)在電子地圖上的匹配位置與車輛實(shí)際運(yùn)行道路時(shí)常出現(xiàn)偏差。針對(duì)這個(gè)實(shí)際問題，現(xiàn)提出以下解決方案：1）提高GPS 定位數(shù)據(jù)及電子地圖數(shù)據(jù)精度。2）采用地圖匹配方法。比較以上2 個(gè)方案可以得出，前者實(shí)現(xiàn)成本較高，無法通過有效手段消除車輛行駛軌跡的顯示誤差。后者是基于軟件技術(shù)的一種定位修正方法，它將GIS中道路層數(shù)據(jù)和GPS 定位數(shù)據(jù)進(jìn)行有效匹配，以緩解各種誤差導(dǎo)致的消極影響，使車輛實(shí)際定位點(diǎn)精準(zhǔn)匹配到GIS 中道路層，精確的地圖匹配結(jié)果可為監(jiān)測(cè)交通流量、實(shí)時(shí)導(dǎo)航等提供可靠的基礎(chǔ)數(shù)據(jù)。

1 技術(shù)簡(jiǎn)介

1.1 ArcGIS 平臺(tái)

地理信息系統(tǒng)（GIS）是具備多種功能的一種綜合性質(zhì)的信息管理系統(tǒng)，它廣泛應(yīng)用于各大領(lǐng)域。Arc GIS 10.4.1 作為Arc GIS 10 系列里的一個(gè)完整GIS 軟件集合，包括類似Arc GIS for Desktop、服務(wù)端GIS 等功能框架。其中，Arc GIS for Desktop 主要作為GIS 桌面端的一款軟件，包括創(chuàng)建、編輯地理信息以及對(duì)地理信息進(jìn)行分析處理等內(nèi)容，它不僅能夠提供1 套Windows 桌面應(yīng)用（這里主要指Arc Map 10.4.1），而且能夠提供采集和管理數(shù)據(jù)、構(gòu)建空間模型等功能。

1.2 ArcPy

ArcPy 包是在arcgisscripting 模塊功能基礎(chǔ)上繼承和豐富Python 站點(diǎn)包的，ArcGIS 平臺(tái)依靠它來訪問包內(nèi)部所提供的各種地理信息方面的處理方法和模塊類，進(jìn)而進(jìn)一步訪問和處理GIS 平臺(tái)上的數(shù)據(jù)，具體可實(shí)現(xiàn)的功能包括高效創(chuàng)建和使用各個(gè)應(yīng)用程序、快速在各類業(yè)務(wù)方面形成邏輯以及完成幾何操作、地圖代數(shù)、地圖操作和編輯處理等功能。ArcPy為用戶提供了強(qiáng)大的功能，不僅可以通過調(diào)取相關(guān)的類及函數(shù)來實(shí)現(xiàn)將代碼補(bǔ)充完整的功能（這里主要講的是自動(dòng)創(chuàng)建地圖和執(zhí)行交互操作的相關(guān)接口函數(shù)實(shí)現(xiàn)了補(bǔ)充完整功能），而且提供了利用Python 語言調(diào)用全部地理處理工具的操作（這里主要指Toolbox），主要負(fù)責(zé)實(shí)現(xiàn)地理數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)分析以及數(shù)據(jù)管理等內(nèi)容。

1.3 GPS

目前，全球定位系統(tǒng)不僅可以應(yīng)用到大氣觀測(cè)、地理勘測(cè)等領(lǐng)域，而且還可以應(yīng)用到車輛導(dǎo)航系統(tǒng)中，為駕駛員提供路線導(dǎo)航，以便駕駛員可以安全、準(zhǔn)確地按照選定路線行駛。

GPS 具備以下4 個(gè)特點(diǎn)：1）覆蓋范圍很廣。GPS 導(dǎo)航定位系統(tǒng)是由很多衛(wèi)星構(gòu)建而成的一個(gè)強(qiáng)大的分布網(wǎng)絡(luò)，這些衛(wèi)星可以循環(huán)且按照合理的運(yùn)行周期往地球GPS 接收站傳送觀測(cè)的信號(hào)，以便為地球上的駕駛員提供實(shí)時(shí)導(dǎo)航。2）實(shí)現(xiàn)路線實(shí)時(shí)導(dǎo)航。GPS 車輛導(dǎo)航系統(tǒng)通過語音及線路導(dǎo)航2 種方式為駕駛員提供多個(gè)可能行駛路線，并能夠根據(jù)駕駛員當(dāng)前行駛路線實(shí)時(shí)更新后續(xù)行駛線路。3）定位準(zhǔn)確。GPS車輛導(dǎo)航系統(tǒng)可以全方位且實(shí)時(shí)地發(fā)送精確的車輛位置、方向及車輛行駛速度等定位信息，定位準(zhǔn)確度很高。4）成本相對(duì)較低。只要對(duì)相關(guān)軟件、硬件設(shè)備進(jìn)行合理配置，就可以免費(fèi)使用GPS 車輛導(dǎo)航系統(tǒng)。

1.4 WGS-84坐標(biāo)系

車輛導(dǎo)航系統(tǒng)采用WGS-84 大地坐標(biāo)系作為表示GPS車輛定位數(shù)據(jù)經(jīng)常使用的坐標(biāo)系，這種坐標(biāo)系的具體原理簡(jiǎn)述如下：坐標(biāo)系的原點(diǎn)主要是地球質(zhì)心，選取的X軸坐標(biāo)方向主要是BIH1984.0 的零度子午面和CTP 赤道的交點(diǎn)，Z軸坐標(biāo)的方向與CTP 的方向一致，X軸、Y軸及Z軸構(gòu)成直角三維的右手坐標(biāo)系。

WGS-84橢圓體選擇地心坐標(biāo)系作為主要坐標(biāo)系。WGS-84橢球上地表實(shí)體經(jīng)緯度（L、B）、實(shí)體所在位置高度（H）分別對(duì)應(yīng)空間的直角坐標(biāo)（X、Y和Z）。

在進(jìn)行地圖匹配前，需要將空間坐標(biāo)系轉(zhuǎn)換為直角坐標(biāo)系，具體轉(zhuǎn)換公式如公式（1）～公式（4）所示。

式中：N為卯酉圈曲率半徑；e為地球偏心率；a為地球橢球的長半徑。

2 原始數(shù)據(jù)及其誤差

該算法采用的原始數(shù)據(jù)主要來自某市出租車實(shí)際行駛數(shù)據(jù)（GPS 定位數(shù)據(jù)）和GIS 路網(wǎng)數(shù)據(jù)，定位數(shù)據(jù)采集時(shí)間間隔較長且松散稀疏，每隔20 s 傳輸1 次，從道路特征上來看，大部分路況以交叉口或平行路段居多。影響出租車行駛軌跡匹配準(zhǔn)確性的因素主要包括GPS 數(shù)據(jù)及其誤差、坐標(biāo)轉(zhuǎn)換誤差和GIS 數(shù)據(jù)及其誤差。

2.1 GPS 數(shù)據(jù)及其誤差

GPS 定位存在一定的誤差，GPS 定位誤差主要包括GPS系統(tǒng)及其他因素導(dǎo)致的誤差。出租車導(dǎo)航系統(tǒng)中的GPS 定位誤差主要是由GPS 定位系統(tǒng)造成的誤差[1]；其他誤差主要由衛(wèi)星測(cè)量導(dǎo)致誤差、傳播途徑影響的誤差以及接收機(jī)本身造成的誤差組成[1]。

2.2 坐標(biāo)轉(zhuǎn)換誤差

在與電子地圖中的GIS 路網(wǎng)數(shù)據(jù)完成匹配測(cè)試前，需要完成坐標(biāo)轉(zhuǎn)換，即需要將車輛的多維定位數(shù)據(jù)進(jìn)行高斯一克呂格正形投影處理變成二維數(shù)據(jù)，但是在坐標(biāo)轉(zhuǎn)換過程中，無法達(dá)到精準(zhǔn)無誤的坐標(biāo)轉(zhuǎn)換。

2.3 GIS 數(shù)據(jù)及其誤差

在獲得道路網(wǎng)數(shù)據(jù)并構(gòu)建拓?fù)潢P(guān)系時(shí)，必須保證電子地圖的路網(wǎng)地圖數(shù)據(jù)具有規(guī)范有序的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息和高質(zhì)量坐標(biāo)數(shù)據(jù)，這樣才可以真實(shí)展現(xiàn)道路狀況，才能為后續(xù)的地圖匹配試驗(yàn)提供準(zhǔn)確的基礎(chǔ)數(shù)據(jù)。因此，對(duì)匹配精度來說，路網(wǎng)地圖數(shù)據(jù)的質(zhì)量至關(guān)重要。

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

3.1 基本思想

基于投影的地圖匹配算法的基本思想如下：選擇待匹配GPS 定位點(diǎn)附近所有道路作為候選投影路段，并分別向全部候選路段進(jìn)行投影操作，計(jì)算待匹配點(diǎn)與全部候選路段間的投影距離di以及車輛行駛方向與各路段間的夾角α，如公式（5）所示。

式中：i為各個(gè)投影路段；λd、λα分別為距離、方向的權(quán)值；Wi為各候選路段的度量值，從全部候選路段的度量值Wi中選擇最小度量值作為最終匹配路段，即判定車輛行駛在該路段上。

現(xiàn)將λd、λα分別賦值為0.5，通過公式（1）計(jì)算得出最小度量值為W1，確定其對(duì)應(yīng)的候選路段L1作為車輛的最佳匹配路段，選擇p1點(diǎn)在匹配路段L1上的投影點(diǎn)p1作為車輛的最終匹配位置。

3.2 投影算法的局限性

基于投影的地圖匹配算法目前被認(rèn)定為邏輯相對(duì)簡(jiǎn)單且在簡(jiǎn)單路段具有較好的匹配效果，但是在復(fù)雜道路網(wǎng)（交叉路口或平行路段）匹配效果不理想，極易出現(xiàn)錯(cuò)誤匹配情況。當(dāng)在交叉口路段或2 條距離相近的平行路段行駛時(shí)，按照車輛實(shí)際行駛軌跡判斷得出，車輛行駛點(diǎn)p1的正確匹配路段為L1且匹配位置點(diǎn)為p'1，但是通過算法匹配到了路段L2且匹配位置點(diǎn)為p'2。經(jīng)過反復(fù)試驗(yàn)驗(yàn)證得出，該算法需要在原有匹配因素的基礎(chǔ)上，新增定位點(diǎn)與待匹配路段的相對(duì)位置、待匹配道路和歷史匹配路段的連通性這2 個(gè)匹配因素才能提高匹配精度。

4 改進(jìn)的基于特征權(quán)重的地圖匹配算法

4.1 設(shè)置“緩沖區(qū)域”

該算法采用的電子地圖內(nèi)包括大量路網(wǎng)數(shù)據(jù)，假如針對(duì)整個(gè)路網(wǎng)道路執(zhí)行匹配試驗(yàn)時(shí)，特別影響匹配效率。為了改善這種情況，就需要根據(jù)當(dāng)前車輛位置信息篩選滿足算法匹配規(guī)則的待匹配道路范圍。因此，該文提出的算法設(shè)計(jì)了“緩沖區(qū)域”概念，基本原理是以車輛當(dāng)前GPS 定位點(diǎn)為圓心來劃定緩沖區(qū)域，并確定圓形區(qū)域內(nèi)所有的候選路段作為地圖匹配測(cè)試的路段。設(shè)置“緩沖區(qū)域”主要通過調(diào)用ArcGIS 中內(nèi)嵌的ArcPy 包中函數(shù)來計(jì)算實(shí)現(xiàn)。

4.2 算法描述

基于特征權(quán)重的地圖匹配算法基本原理如下：1）設(shè)置“緩沖區(qū)域”，篩選車輛當(dāng)前GPS 定位點(diǎn)在緩沖區(qū)域內(nèi)所有的候選道路，并判斷歷史GPS 定位點(diǎn)已匹配成功位置點(diǎn)行駛至當(dāng)前GPS 定位點(diǎn)匹配位置點(diǎn)是否符合駕駛行為，是否存在道路，經(jīng)過這一系列判斷后，存儲(chǔ)具備合理性、可達(dá)性的路段。2）判斷已確定的歷史匹配成功路段與當(dāng)前待匹配路段是否符合合理的拓?fù)潢P(guān)系，并存儲(chǔ)具備拓?fù)潢P(guān)系的候選路段，舍棄不具備拓?fù)潢P(guān)系的候選路段。

4.3 確定最佳匹配路段

通過以上步驟的精確篩選后，如果GPS 定位點(diǎn)還存在多個(gè)候選路段，通過該文提出的算法對(duì)當(dāng)前GPS 定位點(diǎn)和其緩沖區(qū)域劃定范圍內(nèi)候選路段之間夾角與距離相似程度、定位點(diǎn)和候選道路相對(duì)位置、候選道路和歷史匹配路段的連通性等3 個(gè)因素執(zhí)行加權(quán)計(jì)算操作，選擇權(quán)重值最小的候選路段作為最佳匹配路段。

4.3.1 相似程度權(quán)重

利用當(dāng)前GPS 定位點(diǎn)和其緩沖區(qū)域劃定范圍內(nèi)路段之間夾角與距離關(guān)系去計(jì)算相似程度權(quán)重值。GPS 定位點(diǎn)將向緩沖區(qū)域內(nèi)的待匹配路段進(jìn)行垂直投影操作，然后計(jì)算道路通行方向和車輛瞬時(shí)行駛方向的夾角、當(dāng)前GPS 定位點(diǎn)到全部待匹配路段的垂直距離，并通過公式（6）計(jì)算每個(gè)待匹配道路對(duì)應(yīng)的相似程度數(shù)值。

式中：λα為cosαi相應(yīng)的權(quán)重系數(shù)；λd為di相應(yīng)的權(quán)重系數(shù)；W1為相似程度權(quán)重相應(yīng)的特征值。

4.3.2 定位點(diǎn)和候選道路的相對(duì)位置權(quán)重

如果當(dāng)車輛駕駛到復(fù)雜道路（例如交叉路段）時(shí)，車輛瞬間駕駛方向和各候選道路所形成的夾角有較大偏差，當(dāng)前GPS 定位點(diǎn)pi和候選道路L1、L2和L3形成夾角分別為β1、β2和β3，其大小的差別較大。當(dāng)車輛瞬時(shí)駕駛方向與各個(gè)候選道路通行方向形成的夾角越小，代表定位點(diǎn)和候選道路相對(duì)位置這個(gè)因素的權(quán)重值越小，對(duì)應(yīng)路段是最佳匹配道路的概率就越大[2]。定位點(diǎn)和候選道路的相對(duì)位置權(quán)重相應(yīng)的特征值如公式（7）所示。

式中：λ2為cos|βj|相應(yīng)的權(quán)重系數(shù)；W2為定位點(diǎn)和候選道路的相對(duì)位置權(quán)重相應(yīng)的特征值。

4.3.3 連通性權(quán)重

判斷當(dāng)前GPS 定位點(diǎn)緩沖區(qū)域內(nèi)的全部候選路段與以往匹配成功路段之間是否滿足合理的拓?fù)潢P(guān)系，保存滿足合理拓?fù)潢P(guān)系的候選道路，舍棄不滿足合理拓?fù)潢P(guān)系的候選道路，直至后續(xù)全部GPS 定位點(diǎn)執(zhí)行匹配試驗(yàn)成功后，利用Dij kstra 算法去計(jì)算歷史匹配成功路段和后續(xù)定位點(diǎn)對(duì)應(yīng)的匹配道路的最短長度路徑，該算法基本原理是利用數(shù)組按照權(quán)重大小順序排列存儲(chǔ)路徑長度，最后選擇具有最短路徑長度的路段作為最優(yōu)匹配路段[3]。

當(dāng)前車輛GPS 定位點(diǎn)pi向路段L1和路段L2分別做垂直投影，投影位置點(diǎn)分別為點(diǎn)A和點(diǎn)B，以往GPS 定位點(diǎn)pi-1在匹配成功路段L3上的位置投影點(diǎn)是點(diǎn)C，Ldistance表示車輛處于持續(xù)時(shí)間段里的真實(shí)行駛距離，其本質(zhì)就是計(jì)算點(diǎn)pi-1到點(diǎn)pi的歐拉距離代表上一個(gè)GPS 定位點(diǎn)pi-1在匹配成功路段L3上投影位置點(diǎn)C到點(diǎn)pi在候選路段L1、路段L2上投影點(diǎn)A、點(diǎn)B在道路網(wǎng)上的成功匹配距離（匹配距離如果真實(shí)行駛距離與匹配距離相減后的絕對(duì)值越小，就代表路段Li為點(diǎn)pi的最佳匹配路段，如公式（8）所示。

4.3.4 計(jì)算總權(quán)重

利用網(wǎng)格搜索法確定每個(gè)權(quán)重對(duì)應(yīng)的系數(shù)[4]，規(guī)則如下：1）連通性的權(quán)重系數(shù)>相對(duì)位置的權(quán)重系數(shù)>相似程度的權(quán)重系數(shù)，即λ3>λ2>λd+λα。2）相對(duì)位置的權(quán)重系數(shù)+連通性的權(quán)重系數(shù)+相似程度的權(quán)重系數(shù)=1，即λ3+λ2+λd+λα=1，其中λd=λα。3）設(shè)定一個(gè)閾值（由經(jīng)驗(yàn)確定），以確定經(jīng)過加權(quán)計(jì)算操作后滿足要求的匹配路段。利用該文提出的算法對(duì)“緩沖區(qū)域”內(nèi)全部候選路段的3 個(gè)權(quán)重進(jìn)行加權(quán)計(jì)算操作，比較在合理閾值范圍內(nèi)的全部候選路段的權(quán)重值，選擇權(quán)重值（W總）最小的路段為最優(yōu)匹配路段，如公式（9）所示。

4.4 算法匹配步驟

篩選最優(yōu)匹配路徑的過程如下[5]：1）收集車輛經(jīng)度坐標(biāo)、緯度坐標(biāo)以及瞬時(shí)運(yùn)行方向等全部信息。2）對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。舍棄無效或異常數(shù)據(jù)。3）對(duì)預(yù)處理后的GPS 數(shù)據(jù)和路網(wǎng)數(shù)據(jù)進(jìn)行坐標(biāo)轉(zhuǎn)換操作。4）設(shè)置緩沖區(qū)域。以當(dāng)前GPS 定位點(diǎn)為圓心畫圓，選擇圓形區(qū)域范圍內(nèi)的全部路段作為候選路段。5）按照合理可達(dá)性原則保存具備合理可達(dá)性的路段，舍棄不具備合理可達(dá)性的道路。6）如果當(dāng)前車輛的GPS 定位點(diǎn)在緩沖區(qū)域內(nèi)只存在1 條候選路段，則選擇基于投影的地圖匹配算法來匹配車輛位置點(diǎn)；如果當(dāng)前GPS 定位點(diǎn)不止存在1 條候選路段，則通過網(wǎng)格搜索法確定權(quán)重系數(shù)，利用該文提出的算法計(jì)算全部侯選路段的3 個(gè)特征對(duì)應(yīng)的總權(quán)重值，并將具有最小權(quán)重值的候選路段確定為最佳匹配路段。7）如果同一輛車所行駛過的道路存在不連續(xù)的情況，就需要綜合考慮合理可達(dá)性、最短路徑算法、當(dāng)下GPS 定位點(diǎn)的候選路段和歷史匹配成功路段的連通性等因素來篩選車輛最佳匹配路段。8）匹配結(jié)束。

5 試驗(yàn)結(jié)果及分析

該文采用某市出租車的GPS 定位數(shù)據(jù)及道路網(wǎng)數(shù)據(jù)來完成地圖匹配試驗(yàn)，算法匹配試驗(yàn)平臺(tái)采用ArcGIS 的ArcMap 模塊功能完成匹配試驗(yàn)，選用Python 語言實(shí)現(xiàn)具體功能，在進(jìn)行匹配試驗(yàn)前需要將GPS 定位數(shù)據(jù)的多維坐標(biāo)轉(zhuǎn)換為二維平面坐標(biāo)。該算法從上千條出租車GPS 實(shí)際運(yùn)行數(shù)據(jù)中任意抽取1 條運(yùn)行軌跡數(shù)據(jù)，并將其在電子地圖里展現(xiàn)圖層。在交叉口、平行路段完成2 種地圖匹配算法的匹配對(duì)比試驗(yàn)后，使用基于投影算法在交叉口路段達(dá)到的匹配率為61.5%，平行路段匹配率為80.3%，總匹配率為70.9%；使用該文算法在交叉口路段的匹配率為82.6%，平行路段匹配率為93.7%，總匹配率為88.1%，顯然該文算法匹配效果更好。

6 結(jié)語

車輛導(dǎo)航系統(tǒng)采用的基于特征權(quán)重的地圖匹配算法的精確地圖匹配結(jié)果可以為監(jiān)測(cè)交通流量、判斷交通擁堵情況以及實(shí)時(shí)導(dǎo)航提供可靠的基礎(chǔ)數(shù)據(jù)。它在原有的基于投影的地圖匹配算法基礎(chǔ)上做出了改進(jìn)，能夠在平行路段、交叉路段取得較理想的匹配效果。在未來工作中，將進(jìn)一步研究地圖匹配算法，使它向更優(yōu)化、更高效的方向發(fā)展，并繼續(xù)探索算法在其他領(lǐng)域應(yīng)用的可行性。