基于特征權重的地圖匹配算法研究

張 賀 孫婉瑩 宋國平

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

0 引言

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

1 技術簡介

1.1 ArcGIS 平臺

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

1.2 ArcPy

ArcPy 包是在arcgisscripting 模塊功能基礎上繼承和豐富Python 站點包的，ArcGIS 平臺依靠它來訪問包內部所提供的各種地理信息方面的處理方法和模塊類，進而進一步訪問和處理GIS 平臺上的數據，具體可實現的功能包括高效創建和使用各個應用程序、快速在各類業務方面形成邏輯以及完成幾何操作、地圖代數、地圖操作和編輯處理等功能。ArcPy為用戶提供了強大的功能，不僅可以通過調取相關的類及函數來實現將代碼補充完整的功能（這里主要講的是自動創建地圖和執行交互操作的相關接口函數實現了補充完整功能），而且提供了利用Python 語言調用全部地理處理工具的操作（這里主要指Toolbox），主要負責實現地理數據轉換、數據分析以及數據管理等內容。

1.3 GPS

目前，全球定位系統不僅可以應用到大氣觀測、地理勘測等領域，而且還可以應用到車輛導航系統中，為駕駛員提供路線導航，以便駕駛員可以安全、準確地按照選定路線行駛。

GPS 具備以下4 個特點：1）覆蓋范圍很廣。GPS 導航定位系統是由很多衛星構建而成的一個強大的分布網絡，這些衛星可以循環且按照合理的運行周期往地球GPS 接收站傳送觀測的信號，以便為地球上的駕駛員提供實時導航。2）實現路線實時導航。GPS 車輛導航系統通過語音及線路導航2 種方式為駕駛員提供多個可能行駛路線，并能夠根據駕駛員當前行駛路線實時更新后續行駛線路。3）定位準確。GPS車輛導航系統可以全方位且實時地發送精確的車輛位置、方向及車輛行駛速度等定位信息，定位準確度很高。4）成本相對較低。只要對相關軟件、硬件設備進行合理配置，就可以免費使用GPS 車輛導航系統。

1.4 WGS-84坐標系

車輛導航系統采用WGS-84 大地坐標系作為表示GPS車輛定位數據經常使用的坐標系，這種坐標系的具體原理簡述如下：坐標系的原點主要是地球質心，選取的X軸坐標方向主要是BIH1984.0 的零度子午面和CTP 赤道的交點，Z軸坐標的方向與CTP 的方向一致，X軸、Y軸及Z軸構成直角三維的右手坐標系。

WGS-84橢圓體選擇地心坐標系作為主要坐標系。WGS-84橢球上地表實體經緯度（L、B）、實體所在位置高度（H）分別對應空間的直角坐標（X、Y和Z）。

在進行地圖匹配前，需要將空間坐標系轉換為直角坐標系，具體轉換公式如公式（1）～公式（4）所示。

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

2 原始數據及其誤差

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

2.1 GPS 數據及其誤差

GPS 定位存在一定的誤差，GPS 定位誤差主要包括GPS系統及其他因素導致的誤差。出租車導航系統中的GPS 定位誤差主要是由GPS 定位系統造成的誤差[1]；其他誤差主要由衛星測量導致誤差、傳播途徑影響的誤差以及接收機本身造成的誤差組成[1]。

2.2 坐標轉換誤差

在與電子地圖中的GIS 路網數據完成匹配測試前，需要完成坐標轉換，即需要將車輛的多維定位數據進行高斯一克呂格正形投影處理變成二維數據，但是在坐標轉換過程中，無法達到精準無誤的坐標轉換。

2.3 GIS 數據及其誤差

在獲得道路網數據并構建拓撲關系時，必須保證電子地圖的路網地圖數據具有規范有序的網絡拓撲結構信息和高質量坐標數據，這樣才可以真實展現道路狀況，才能為后續的地圖匹配試驗提供準確的基礎數據。因此，對匹配精度來說，路網地圖數據的質量至關重要。

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

3.1 基本思想

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

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

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

3.2 投影算法的局限性

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

4 改進的基于特征權重的地圖匹配算法

4.1 設置“緩沖區域”

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

4.2 算法描述

基于特征權重的地圖匹配算法基本原理如下：1）設置“緩沖區域”，篩選車輛當前GPS 定位點在緩沖區域內所有的候選道路，并判斷歷史GPS 定位點已匹配成功位置點行駛至當前GPS 定位點匹配位置點是否符合駕駛行為，是否存在道路，經過這一系列判斷后，存儲具備合理性、可達性的路段。2）判斷已確定的歷史匹配成功路段與當前待匹配路段是否符合合理的拓撲關系，并存儲具備拓撲關系的候選路段，舍棄不具備拓撲關系的候選路段。

4.3 確定最佳匹配路段

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

4.3.1 相似程度權重

利用當前GPS 定位點和其緩沖區域劃定范圍內路段之間夾角與距離關系去計算相似程度權重值。GPS 定位點將向緩沖區域內的待匹配路段進行垂直投影操作，然后計算道路通行方向和車輛瞬時行駛方向的夾角、當前GPS 定位點到全部待匹配路段的垂直距離，并通過公式（6）計算每個待匹配道路對應的相似程度數值。

式中：λα為cosαi相應的權重系數；λd為di相應的權重系數；W1為相似程度權重相應的特征值。

4.3.2 定位點和候選道路的相對位置權重

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

式中：λ2為cos|βj|相應的權重系數；W2為定位點和候選道路的相對位置權重相應的特征值。

4.3.3 連通性權重

判斷當前GPS 定位點緩沖區域內的全部候選路段與以往匹配成功路段之間是否滿足合理的拓撲關系，保存滿足合理拓撲關系的候選道路，舍棄不滿足合理拓撲關系的候選道路，直至后續全部GPS 定位點執行匹配試驗成功后，利用Dij kstra 算法去計算歷史匹配成功路段和后續定位點對應的匹配道路的最短長度路徑，該算法基本原理是利用數組按照權重大小順序排列存儲路徑長度，最后選擇具有最短路徑長度的路段作為最優匹配路段[3]。

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

4.3.4 計算總權重

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

4.4 算法匹配步驟

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

5 試驗結果及分析

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

6 結語

車輛導航系統采用的基于特征權重的地圖匹配算法的精確地圖匹配結果可以為監測交通流量、判斷交通擁堵情況以及實時導航提供可靠的基礎數據。它在原有的基于投影的地圖匹配算法基礎上做出了改進，能夠在平行路段、交叉路段取得較理想的匹配效果。在未來工作中，將進一步研究地圖匹配算法，使它向更優化、更高效的方向發展，并繼續探索算法在其他領域應用的可行性。