復雜路段的角度差和后續點地圖匹配方法

摘 要： "針對僅依靠距離和軌跡與路徑的相似性來判斷正確道路的方法，在并行和交叉路段的復雜路網環境中，易匹配到相鄰路段或部分不可達的路段，導致匹配錯誤的問題，提出采用線性回歸模型的方法，其能更精確地描述道路形狀在轉彎處的變化，根據路段方向和移動對象移動的方向差判斷并行或交叉路段，并通過參照多個后續點的匹配情況，實現復雜路段處的地圖匹配，減少匹配錯誤。此外，還提出簡化聚類的路網補全方法，可以解決部分GPS點周圍缺失候選路段無法匹配的問題，并采用四叉樹索引地圖數據，提高效率。對比實驗結果表明在軌跡點數較少時，與現有的基于隱馬爾可夫模型的概率匹配方法相比，時間最多減少了62%，更適合時效性要求高的應用場景，與傳統的幾何匹配方法相比，匹配精度提高了3%，且更適合復雜路段匹配。

關鍵詞： "地圖匹配； 并行路段； 交叉路段； 角度差； 回歸； 后續點

中圖分類號： "TP391 """文獻標志碼： A

文章編號： "1001-3695（2022）02-009-0379-06

doi：10.19734/j.issn.1001-3695.2021.07.0263

Map matching method for complex road sections via "difference and subsequent points

Wang Xiaohana，b， He Zengyua，b， Hu Wangwua，b， Wang Peia，b， Yang Longa，b

（a.School of Computer amp; Information， b.Anhui Key Laboratory of Network amp; Information Security， Anhui Normal University， Wuhu Anhui 241002， China）

Abstract： "Map matching is important in navigation， traffic analysis and other applications. In the complex road network environment of parallel and cross sections， it is easy to match the adjacent sections or some inaccessible sections， which leads to the wrong matching. The proposed linear regression model was more accurate to describe the change of road shape at the tur-ning. According to the difference between the road section direction and the moving direction of the moving object， it judged the parallel or intersecting road sections. By referring to the matching of multiple subsequent points， the map matching at complex sections could be realized， which could reduce the matching error. In addition， the proposed road network completion method based on simplified clustering could solve the problem that the missing candidate road sections around some GPS points could not be matched. And it used quad-tree structure to index map data to improve the efficiency. The results of comparative experiment show that when the number of trajectory points is small， compared with the existing probabilistic matching method based on hidden Markov model， the time is reduced by 62%， which is more suitable for the application scenarios with high timeliness requirements. Compared with the traditional geometric matching method， the matching accuracy is improved by 3%， and it is more suitable for complex road matching.

Key words： "map matching; parallel road; cross road; angle difference; regression; subsequent points

0 引言

基于位置服務會生成大量定位數據，移動GPS設備存在定位誤差，還會因低質量、斷電，或高樓等障礙物的阻擋、信號衰減甚至消失等原因，產生更大的定位偏差，導致路網上的位置被定位到草坪、湖泊、建筑等不合理處。因此，這些定位數據均需要地圖匹配，例如智能交通、城市交通規劃、物流跟蹤等，若不處理這些軌跡，會降低數據的可用性，地圖匹配是定位數據的重要處理步驟。地圖匹配將移動對象的軌跡序列中的每個點映射到對應道路上，修正軌跡定位誤差。地圖匹配算法的作用是將具有誤差的GPS軌跡數據映射到真實的路網上［1］。從所應用到的技術來分，地圖匹配方法可分為幾何匹配、拓撲匹配、概率匹配、高級匹配四種。從不同的應用場景和實時性要求可分為在線地圖匹配［2，3］和離線地圖匹配［4］，離線地圖匹配可用于快速獲取最佳匹配路線，還可用于智能交通系統的構建、興趣點的推薦等應用場景。

傳統幾何匹配方法中點到線、線到線的匹配方法實現簡單，且匹配效率高，被廣泛運用，但是，僅依靠距離和軌跡與路徑的相似性來判斷正確道路，在并行和交叉路段的復雜路網環境中，易匹配到相鄰路段或部分不可達的路段，容易導致匹配錯誤。

目前，基于概率的地圖匹配方法被研究者廣泛應用［5］，例如基于隱馬爾可夫模型（HMM）的概率方法［4，6～10］，不需要大量訓練數據集，實現起來比較容易，并且匹配正確率高。但是，現有的概率方法在計算路段方向時，采用的是路段起始點和終止點的連線方向［7，8］，在復雜環境下，僅用起始點和終止點的方向無法描述路段的變化情況。因此，本文提出了構建一元線性回歸方程的方法，用回歸方程的直線斜率作為路段的方向，可以更好地適應路段的方向變化。另外，這些基于隱馬爾可夫模型的概率匹配方法，由于需要計算概率矩陣才能確定最終的匹配，會消耗較大的時間成本，所以對時效性要求較高的應用場景不太適合。利用四叉樹索引存儲地圖數據，減少花費的時間。針對形狀不規則的復雜路段，提出采用回歸模型生成的回歸方程代替和路段方向，能更好地描述路段方向的不斷變化。針對在并行、交叉的路段，復雜的路況環境容易導致匹配錯誤問題，提出了角度差方法，判斷復雜路段，并提出參考后續點的匹配，可以減少匹配錯誤。針對地圖數據缺失和更新不及時等現狀，提出簡化聚類的路網補全方法，可以解決部分GPS點周圍沒有候選路段，無法匹配的問題。將沒有候選路段的軌跡點進行聚類，并將聚類后生成的聚類中心作為缺失路段的路網點加入路網數據集合。

1 相關工作

地圖匹配面臨復雜的路況環境的挑戰，例如在并行、交叉及環形等路段處容易出現匹配錯誤，是地圖匹配的難點。早期的地圖匹配方法通過計算GPS點到路段所在直線的距離以及到路網點的最近距離以獲取到最佳的匹配結果［11，12］。但并行道路處，這兩項數值十分接近，僅憑借單個點到路段的距離或點的方向與路段之間方向的差值，無法決定最終的匹配。Kong等人［13］設定方向、路口、拓撲連接等過濾器，解決了并行路段，交叉路口和環形路口等處易出現匹配錯誤問題，但是該算法主要處理低頻軌跡，在高頻率采樣時計算開銷會非常大。Abdallah等人［14］提出一種區間分析和置信函數理論的地圖匹配算法，使用拓撲和相似性標準定義一組候選路段，并用多準則融合算法構造質量函數，計算候選路段的估算值，選擇估算值最高的作為最佳路段。該方法提高了交叉和并行路段的匹配精確度。Sharath等人［15］針對復雜路網環境中的并行路段，提出了基于道路寬度的地圖匹配算法，解決了車輛被匹配到相鄰并行路段上的問題，但是該方法需要道路寬度作為加權條件，而現有路網數據中寬度屬性不易獲取。Hashemi等人［16］針對交叉路口判定，根據航向、行駛方向與道路的差值，以及當前點的投影是否超出了候選路段的末節點等要素，判斷車輛是否已轉彎。該方法提高了交叉路段處的匹配精度，但是需要利用移動用戶的水平精度因子參數，衡量GPS的誤差范圍，該參數需要專門配備傳感器采集。Wang等人［17］提出卡爾曼濾波的匹配方法，重復校正并行路段處有誤差的GPS采樣點，提高匹配精度。Hu等人［18］基于HMM匹配，結合方向位置信息，計算觀測和轉移概率，并通過最大化序列狀態，解決維特比算法的標簽偏向問題，提高了在并行、交叉、高架以及環形路段處的匹配精度。Qi等人［19］對十字路口區域所有的GPS點分類，按照出入站規則匹配，將十字路段處的匹配作為一個單獨的模塊處理，但該方法需要對一條軌跡所經過的所有十字路段精確分割，不易實現。Liu等人［20］針對不同路網環境提出了軌跡分割、分段匹配的方法，當移動對象行駛至交叉路口等復雜路段，采用自定義的出入站規則匹配，提高了交叉路段匹配的精度。

現有的算法在復雜路段處，如果只依賴當前點的信息，沒有參照多個后續點的匹配，例如在并行處，容易被匹配至相鄰的路段;在交叉處，容易被匹配不可達路段，造成錯誤匹配。

近年來基于HMM的地圖概率匹配方法［5］被成功應用。文獻［4］首先將HMM應用到地圖匹配中，該方法為距離GPS點近的路段分配更高的概率，另外，如果前后兩個點的直線距離和候選點之間最短路徑距離比值越接近，那么該候選點所在路段將分配更高的概率。之后，一系列基于HMM的概率地圖匹配方法被提出。ST-matching方法利用主路與輔路之間最高限速不同的特點，在傳統HMM模型中加入了車輛行駛速度與路段限速的相似性比較［6］ ，但是該方法在路段復雜的情況下未考慮方向因素，因此匹配正確率不高。STD-matching方法在ST-matching算法的基礎上加入了方向因素，進一步提高了匹配正確率，還采用A*、GPS聚類、GPS平滑算法，解決了在交叉路段處錯誤匹配的情況并且縮短了匹配所需的時間［7］。SD-matching模型［8］將STD-matching模型簡化，其匹配正確率和時間均優于ST-matching，然而對于形狀變化較大的路段，例如環形路段，計算起止點連線方向作為路段方向的方法會產生較大誤差。另外，針對傳統的HMM匹配算法對于每個觀測點的可能路徑選擇僅僅依賴于前一個點而未參考歷史信息以及后續點的信息導致會產生許多無意義的路徑，例如繞路的情況。文獻［3］提出路徑選擇過程中通過添加駕駛員的個人偏好等因素，例如行駛的時間、經過路口的數量、平均道路等級以及道路等級變化數量作為駕駛員選擇路徑的決定因子為每條路段生成對應的概率，該方法減少了觀測點被匹配至無關路段的情況，但是該方法需要獲取很多個人信息以提高正確路段的概率。由于距離最近的道路不一定是正確的道路，但大多數HMM模型中觀測概率大的都是偏向于距離GPS點最近的路段。為了解決這一問題，文獻［9］提出計算GPS點與路段距離時，需要額外考慮道路等級為參考的權重，重要的道路賦予較小的權重以獲取更大的觀測概率值。文獻［10］對軌跡進行分割以緩解傳統HMM匹配方法密集道路網絡中效率低下的缺陷，縮短了匹配時間。現有基于HMM的概率匹配方法主要是通過考慮各種因素計算出其概率矩陣，確定最終的匹配，雖然相比較神經網絡方法，HMM方法不需要訓練大量數據集，但其仍然需要消耗較高的時間開銷用于各種計算，無法滿足時效性要求高的離線應用場景。

另外，針對地圖缺失或更新不及時的問題，Fang等人［21］從大量軌跡數據中提取出地圖數據，將缺失的路段加入當前的電子地圖中，但這需要大量歷史軌跡數據作為支撐。當給定的GPS點指定距離范圍內沒有候選路段或者相鄰兩個GPS點的候選路段沒有連通，文獻［22］認為該處路段缺失需要添加新的路段，并且采用GPS觀測點構建路段，但是，若某個GPS點誤差較大時，構建出的路段形狀與真實的路段形狀差異較大。文獻［23］針對沒有候選路段的GPS點，聚類形成簇并迭代，根據聚類點的距離和轉向角確定合適的路網點，但對多次迭代會增加運行時間。因此，為了更快地構建缺失的路段，本文采用更簡化的聚類算法，解決路段缺失問題，提高效率。

2 復雜路段判斷的地圖匹配方法

并行、交叉路段匹配（PC-matching）方法主要有預處理、復雜路段判斷和復雜路段匹配三個部分。首先，預處理中，提出四叉樹索引方法和更高效的路網補全方法，并在指定寬度的矩形區域內生成GPS點的待匹配路段；其次，提出角度差方法，判斷當前GPS點所處道路復雜情況（并行、交叉、簡單路段）；最后，提出參照多個后續點的并行和交叉路段匹配方法。方法框架如圖1所示。

2.1 預處理

2.1.1 路網點存儲

大量路網數據的存儲、檢索所會花費較長的時間，尤其是在地圖較大或者軌跡延伸范圍變寬時更為顯著。廖佳等人［24］提出網格劃分的方法用于解決路網數據存儲問題。但是，若存在某個網格中路網點數量過多時，仍需要花費大量時間去查找，或者若干網格內都沒有路網點造成存儲空間浪費的問題。Xia等人［25］最初提出四分樹存儲軌跡，可以根據路網點的密度合理分配存儲空間，具有較高的索引效率。當某個區域內的節點數量大于給定的閾值時會繼續把該區域進行四等分，如此不斷地迭代，直到子節點數量小于給定閾值時停止。

如圖2所示，整個區域內有七個路網點，若將劃分數量閾值設定為4，則該平面會被等分為A～D。對于A這個區域，路網點數量仍然大于等于設定閾值，則繼續等分，例如A區域被分為AA、AB、AC、AD，直到包含路網點的數量小于給定閾值。將劃分后的每個區域使用四分樹存儲結構存儲，如圖3所示，第二層四個子節點對應于圖2中A～D四個區域；第三層的每個子節點對應于A～D四個區域內進一步劃分的子區域，依此類推。葉子節點代表地圖被劃分后的最小區域，存儲該區域內的所有路網點。

2.1.2 路網缺失處理

現有的地圖數據中，均存在路網缺失的情況，會造成GPS點附近范圍內沒有可供選擇的路段，匹配中斷。圖4虛線中為現實中存在的路段，但由于地圖中數據缺失，匹配時沒有可供選擇的路段，如圖5虛線方框處所示。

針對此問題，提出使用簡化后的K-means聚類方法對路網缺失區域附近的GPS點進行處理，將生成的聚類中心點作為缺失的路網點添加到地圖數據中，再重新對這些GPS點進行匹配。具體如算法1所示。

算法1 缺失路網補全

輸入： 路 網G;軌跡數據T;距離閾值theta 1 。

輸出： 新生成的路網數據 G ′。

1 for each "P i∈T

2 nbsp;if （distance（ P i，e j）gt;theta "1）

3 """pointlist←P i; //將P i加入 到異常點集合中

4 "end if

5 end for

6 for each（ "P j，P j+1，P j+2）∈pointlist

7 ""e m.node k← k_means （P j，P j+1，P j+2） ;

8 ""G′← add （e m.node k）;

9 end for

10 return "G ′

算法1中： e j表示P i的候選路段集合中的任意一條候選路段;e m.node k表示經過聚類算法生成的路網點、第2、3行所示，首先，遍歷整個軌跡中的每 個GPS點，當GPS 點P i指定范圍內沒有候選路段時進入路段缺失處理步驟，將P i存放至異常點集合。遍歷結束對異常點集合中按照序號順序三個異常點為一 組進行K-means聚類，初聚類中心為這組異常點中第一個點，聚類次數為一次。將聚類后的路網點加入路網數據集合中，并生成新道路的ID。最后，返回新生成的路網數據 G ′。

圖6（a）中，圓圈所示是異常點經過聚類后生成的若干個聚類中心。根據每個聚類簇中GPS點的時間先后順序，生成新的路網點，如圖6（b）藍色點所示，構成一條道路（見電子版）。

2.1.3 候選路段生成

采用范圍搜尋的方法生成候選路段，如圖7所示，以當前GPS點 P i為中心，選擇2d為邊長的矩形區域內所有路段e 1、e 2、e 3作為候選路段，并分別向這三條路段投影，得到投影點c i，1、c i，2、c i，3 。

2.2 基于角度差的復雜路段判斷

復雜路網環境下，首先采用回歸模型依次計算每個候選路段的方向；其次，計算車輛行駛方向與路段方向間的角度差，判斷GPS點所處路段類型，再分別使用簡單、交叉和并行路段匹配。

2.2.1 路段方向計算

文獻［7，8，18］中，道路方向用路段起始點到終點經度之差與緯度之差比值的反正切值，如圖8中紅色實線所示（見電子版）。然而，角度變化較大的路段處，該方法計算行駛方向與路段方向間角度差時會產生較大誤差，無法正確描述路段的方向，例如圖8中的環形路段處。因此，提出使用回歸方程斜率作為當前候選路段的路段方向，如圖8中紅色虛線所示。該方法選取同一條候選路段中距離當前GPS點最近的三個路網點，構建線性回歸方程，并用回歸方程中斜率系數和方向作為當前路段的方向。該方法能描述一條路段不同位置的方向情況，減少角度不斷變化所帶來的誤差。

算法2 路段回歸模型構建

輸入： 路 網G；當前軌跡點P i 。

輸出： P i候選路段的回歸方程集合list。

1 "initiate候選路段集合Rs pi，回歸方程集合list;

2 Rs pi←G. get （p i） ；

3 for each "e j∈Rs pi

4 "for each "e j.node k ∈e j

5 """e j.node k－1，e j.node k+1← findNearPoint（ e j.node k）;

6 """if "（kgt;=2 amp;amp; klt;=|e j.nodelist|－1 amp;amp; rgt;=1 amp;amp; rlt;=|Rs pi|）

7 """"lj r i ←liner_regression（ e j.node k－1，e j.node k+1）;

8 """"list←lj r i

9 ""end if

10 "end for

11 end for

12 return "list ;

算法2的處理對象是一個軌跡點的候選集合 Rs pi 。首先計算出當前GPS 點p i的候選路段集合;其次，遍歷該候選路段集合，對候選路段中與p i直線距離最近的路網點，選擇與之最 近并且道路ID相同的兩個相鄰路網點，構造回歸方程并存儲。當集合中所有的路網點都被遍歷完后，生成一系列的回歸方程。

2.2.2 角度差計算

利用距離，在簡單路段可以選出正確的匹配道路，但是在交叉路段處，分布的道路數量多且密集，如果只憑借距離遠近決定最佳匹配路段，會造成部分GPS點匹配錯誤。角度差是描述汽車行駛方向與路段方向間差異的指標。當移動對象運動方向與路段方向越接近，匹配到該路段可能性越高。因此，本文在距離的基礎上添加角度差作為輔助判定要素，提高交叉并行路段處的匹配精確度。角度差是軌跡點方向與路段方向的差值。

假設給定當前GPS點 P i和 下一個相鄰的GPS點 P i+1，如圖9所示，移動物體的行駛方向記為P i.θ，點P i所對應回歸方程的斜率記為e j.k 。則路段的方向是路段回歸 方程的斜率e j.k。點P i 的行駛方向就是前后兩個GPS 點P i和P i+1連線的方向 ，其計算如式（1）所示。

P i.θ=（P i.lat－P i+1.lat）/（P i.lng－P i+1.lng） "1≤ilt;|T|

P i.θ=P i－1.θ i=|T| """"（1）

其中： |T|是軌跡點總數量。角度差Δ θ 的計算如式（2）所示。

Δ θ=|p i.θ－e j.k| ""（2）

角度差可以用來判斷軌跡與路段的相似程度，角度差值越小，則匹配到該條道路的可能性越大。根據STD-matching[7]匹配方法將角度差閾值設置為30°，本文方法將角度差閾值設置為15°。

2.2.3 復雜路段判斷

現有地圖匹配算法將并行以及交叉路段當成簡單路段來處理。在并行路段處的GPS點與兩條路段的角度差以及距離都比較接近，所以無法確定哪一條是正確的匹配路段。在交叉路段處的GPS點可能會因為到直行路段的距離比較接近而被錯誤地匹配到直行路上。針對這一問題提出復雜路段探測機制，其主要思路是根據角度差來判斷當前GPS點屬于并行、交叉或簡單路段。設定角度差閾 值θ 1、θ 2，若P i的方向與兩條及以上的候選路段夾角在0°～θ 1時，如式（3）所示，則可以判斷移動對象行駛至并行路段區域。若P i的方向與候選路段集合中其他路段夾角超過θ 2 ，如式（4）所示，則可以判斷移動對象可能行駛至交叉路段區域。

Δ θ=|p i.θ－e j.k| 0°lt;Δ θlt;θ 1 ""（3）

Δ θ=|p i.θ－e j.k| Δ θgt;θ 2 ""（4）

算法3 復雜路段判斷算法

輸入： GPS點 p i，角度差閾值θ 1、θ 2，路網G 。

輸出： 當前所處路段是否為并行、交叉的結果。

1 創建候選路段集合 Rs pi，最佳候選點集合Result ；

2 "Rs pi←G. get （p i）;//獲取候 選路段點集合

3 for each "e j，e m∈Rs pi

4 ""if （0° lt;|p i.θ－e j.k|lt;θ 1 amp;amp; 0°lt;|p i.θ－e m.k|lt;θ 1）‖（p i.θ- e m.kgt;θ "2）

5 "return true

6 "end if

7 end for

8 return 1

算法3利用移動對象方向與路段的夾角來判斷是否進入復雜路段，行駛方向與路段之間方向的夾角過大時，則最有可能進入交叉路段；當與多個路段的夾角大小在給定某閾 值θ 1與0° 之間時，可能進入并行路段。由于GPS點的方向與路段存在差值，當與兩條及以上路段的差值相同或接近時（本文設置為5°以內，即 θ "1的取值），這些路段方向基本一致，根據實際車輛行駛情況，可以認為這些路段是平行路段。同理，當前GPS點的方向如果和其他幾條路段間的角度差值大于某個值時（本文設置角度差值為90°，即 θ "2的取值），則認為其駛入了交叉路段。不符合上述兩種情況的路段均當成簡單路段處理。

2.3 基于多個后續點的復雜路段匹配

在簡單路段處，根據距離選擇最近路段匹配。并行、交叉路段則采取復雜路段匹配算法中的處理方法。在并行和交叉的復雜路段，除了角度差外，提出了“向后看 ”多個后續點的方法。匹配當前點P i時，參考它的后續多個后續點P i+1，P i+2…等所處的路段，這樣不僅可以有效解決匹配到并行路段上的問 題，也可以適用于交叉路段。具體實現如算法4所示。

算法4 復雜路段匹配算法

輸入：軌跡 數據T，路網G 。

輸出：返回所有軌跡點的最佳候選點 Result 。

1 "創建候 選路段集合Rs pi，最佳候選點集合Result；

2 "for each "p i ∈|T|

3 """Rs pi←G. get （p i）;//獲 取候選路段點集合

4 ""for each "e j，e m∈Rs pi

5 """if "e j，e m "is parallel or crossing segment

6 """""c i，j ←Parallel_Crossing（ p i，p i+1，p i+2 ，…）；

7 """else

8 """""c i，j ←Normal_Matching "（p i） ；

9 """end if

10 ""Result← c i，j;

11 "end for

12 end for

13 return Result

算法4中Parallel_Crossing匹配方法分為并行、交叉路段兩種匹配。并行路段處，計算當前GPS點的后續多個點到并行路段中每一條路段的距離之和，選擇值最小的匹配。如圖10（a）所示， p 1距離兩條路段很接近，如果根據后續一個點p 2到兩條路段的距離來判斷p 1的匹配結果會造成p 1被匹配到錯誤的路段e 1 上。如圖10（b）所示，若根據后續兩個GPS點分別到兩條路段距離來判斷會極大地降低錯誤匹配的概率，可以看 出p 2、p 3到e 1的距離之和大于到e 2的距離之和。因此，優先將p 1匹配至e 2 。交叉路段處，計算后續點到直行路段和垂直路段的距離，選擇值最小的路段匹配，若距離相等，則考慮后續點到每條候選路段的角度差，選擇角度差小的匹配。如圖 11所示，p 2點匹配時，參考p 3、p 4，由于p 3、p 4兩個點距離e 1的距離較遠，并且與e 1路段的角度差較大，將p 2匹配至e 2 路段。

3 實驗

在真實數據集上，將本文方法與傳統基于距離的幾何匹配方法［11］、傳統基于距離和方向的幾何匹配方法、SD-matching方法［26］、STD-matching方法［7］，以及采用了文獻［7，8，18］中起始點和終止點方向的方法（詳細描述見2.2.1節）進行比較，驗證所提算法在并行和交叉路段處的匹配精度。可視化展示選用ArcMAP 10.5，匹配算法用Java語言實現。

3.1 數據集

地圖數據集OSM文件包含3 738個路網點，共289條道路，包括高速公路、小路、人行道、自行車道、摩托車道等不同等級道路；同時也包括交叉并行等不同種類路段。軌跡數據集是Open Street Map網站上的開源GPX文件，包含116個GPS采樣點，平均每兩個GPS點采樣間隔為2 min。其中數據包括用戶id、軌跡生成時間、平均速度、總路程、軌跡所覆蓋區域邊界經緯度以及海拔高度等信息。

3.2 評價指標

評價主要從匹配正確程度和時間效率兩個方面來衡量。其中，時間效率主要用算法的執行時間來衡量。匹配正確程度分別采用了匹配精度可視化以及匹配正確率來評價。并行交、叉路段的匹配正確率計算方法如式（5）所示。

匹配正確率= count correct count total """（5）

其中： count total表示整條軌跡中所處并行或 交叉路段的GPS點的數量； count correct 表示這些GPS點被正確匹配至路段上的數量。

3.3 復雜路段處的匹配精度可視化分析

對比方法是傳統基于距離和方向的幾何匹配方法和SD-matching方法［26］。采用ArcGIS可視化展示本文方法的匹配精度。圖12、13是本文PC-matching匹配方法在并行、交叉路段的匹配可視化。

由圖12（a）可以看出， p i 所處位置為交叉路段。此時，該GPS點與 r 1、r 2兩條路段的距離較為接近，因此無法判斷正確匹配路段。使用本文所提方法對后續若干點到這兩條候選路段的距離之和以及角度差之和可知，后續點到r 2這條路段的總距離最小，原因在于后續若干點到r 2距離比到r 1近，且與路段的角度差值更小，因此 優先將當前GPS點匹配至 r 2。 但是基于距離方向的匹配方法將GPS點匹配至距離最短且方向接近的路網點，如圖12（b）箭頭所示，匹配錯誤。

由圖13可以看出綠色GPS點（見電子版）位于兩條并行路段之間。根據方向和點到兩條路段的距離無法判斷出屬于哪條道路，但是根據本文方法可知后續若干點到 r 1的距離之和小于到r 2的距 離之和。所以該GPS點應被匹配至 r 1 路段，圖13三角形標志即為最終匹配在路段上的位置。而SD-matching［26］是基于距離和方向的HMM匹配方法，由于沒考慮后續點以及最短路徑等因素導致GPS點被匹配到錯誤的路段，如圖13（b）黑色GPS點所示。

3.4 基于不同方法的匹配精度可視化分析

將本文PC-matching方法與傳統的基于距離的幾何匹配方法［11］、傳統的基于距離和方向的幾何匹配方法、使用起始點和終點路段方向的方法［7，8，18］進行比較，并可視化分析。圖14是整條軌跡匹配的比較。圖中紅色GPS點序列為原始軌跡，黑色點為不同方法的匹配結果（見電子版）。

圖14（a）中，采用傳統基于距離的幾何匹配方法時，因為僅考慮距離，部分區域路網稀疏、路網點數量較少，大量GPS點都會被匹配至同一個路網點上。例如，在交叉路段區域的GPS點沒有被匹配至對應的路段，而是被匹配至交叉路段的交叉點上，導致匹配結果十分稀疏。如圖中紅色虛線框內多個GPS點被匹配至藍色箭頭所指的路網點。圖14（b）中，采取傳統基于距離和方向相結合的幾何匹配算法，由于未考慮后續點的匹配，部分GPS點選取候選路段時，選擇與行駛方向接近、但沒有拓撲關聯的路段，如圖中紅色虛線框內多個GPS點被匹配至不相鄰但是方向相同的路段上。圖14（c）中，沒有回歸模型時，采用文獻［7，8，18］中路段起始點與終止點的直線描述整條路段，并將GPS點投影到這條直線。藍色箭頭為GPS點的行駛方向； e 1路段方向對應于k 1。 但是，正確路段路網點稀疏且距離當前GPS點較遠，因此優先將該GPS點匹配到錯誤路段 e 1上。通過回歸模型可計算e 1路 段在當前GPS點附近的方向為 k "2。因此，根據角度差可判斷進入交叉路段，根據本文的PC-matching匹配方法，在考慮后續點影響后將該GPS點匹配至正確路段 e "2。

由圖14（d）可知，雖然在路網密集的區域，本文方法仍有少部分點被匹配到錯誤的路段上，這是由于該區域路網點稀疏導致錯誤路段的路網點到當前GPS點距離更為接近，但是大部分點都匹配到正確道路上。

綜上所述，在并行、交叉路段，本文方法解決了多個GPS點被匹配至同一個路網點的問題，以及錯誤匹配到其他路段問題。匹配準確率高于其他方法，并且在整條軌跡上的匹配，也比其他匹配算法準確。

3.5 基于不同方法的匹配正確率對比分析

在整條軌跡上，將本文PC-matching方法與傳統基于距離的幾何匹配方法［11］、傳統基于距離和方向的幾何匹配方法、使用起始點和終點路段方向的方法［7，8，18］進行比較，不同匹配方法的匹配正確率如圖15所示。

圖15中，相對于傳統的基于距離、基于距離和方向的幾何匹配方法，匹配準確率分別提高了10%和3%，本文方法具有更高的匹配精確度。相對于采用起始點和終止點的路段方向方法，本文方法采用了回歸模型，精確度提高了10%。

3.6 時間效率對比分析

為了驗證時間效率情況，與STD-matching方法［7］比較，分別在三個規模和采樣頻率不同的數據集上進行測試。其中，數據集1是3 738個路網點和116個GPS采樣點，數據集2是100個路網點和9個GPS采樣點，數據集3是81個路網點和8個GPS采樣點。實驗結果如表1所示。

由表1可知，本文方法在軌跡數據集大的情況下，涉及較大量GPS軌跡數據時，由于本文所提算法需要為多條路段構建多個回歸模型，會花費較長的時間。但是在GPS數量少的情況下，在運行時間方面，與現有的基于HMM的匹配方法相比，在小規模數據集的情況下最多可減少62%的運行時間。相比較STD-matching算法［7］，可以取得更好的匹配效率，主要是由于STD-matching算法是基于概率的匹配方法，需要為GPS點的每條候選路段構建轉移概率矩陣，會花費較長的時間，因此，本文方法更適合于時效性要求高的離線應用場景。

3.7 搜尋半徑的影響分析

由圖16、17可知，運行時間隨著搜尋半徑增加而增加，但匹配精確度則會降低。這是因為搜尋半徑增加，更多的路段加入候選路段集合，增加了回歸模型對路段的構建次數，因此，運行時間會增加。另外，搜尋半徑增加，會添加更多的干擾路段，導致匹配正確率降低。

從圖16可知，運行時間隨著半徑的增加基本呈線性增長趨勢，算法在時間效率方面具有較好的穩定性和可擴展性。從圖17可知，匹配準確率隨著搜尋半徑的增大而降低，但也基本呈線性下降趨勢，而且，半徑增大到一定程度之后，對匹配精度幾乎無太大影響，因此，算法在準確率方面也表現出了較好的穩定性。

4 結束語

針對復雜路段環境中并行、交叉路段的錯誤匹配問題，提出一種PC-matching的匹配方法。該方法首先利用回歸模型刻畫道路形狀，并采用四分樹結構存儲、索引路網數據其減少時間。其次，通過GPS點與路段間的角度差判斷所處道路類型（并行、交叉、簡單路段）。最后，提出參照多個后續點的并行和交叉路段匹配方法。實驗結果表明，本文方法相對于已有的基于距離、基于距離方向的匹配方法具有較高的匹配正確率，能更好地適應復雜路段處的匹配，與STD-matching方法相比，在小規模數據集上的運行時間可以大大減少，更適合在時效性要求高的離線應用場景。本文主要針對并行和交叉路段處的匹配，未來將進一步探討環形路段處的匹配。

參考文獻：

[1] "高文超，李國良，塔娜.路網匹配算法綜述［J］.軟件學報，2018， 29 （2）：225-250.（Gao Wenchao， Li Guoliang， Ta Na. Survey of map matching algorithms［J］. Journal of Software ，2018， 29 （2）：225-250.）

［2] Taguchi S， Koide S， Yoshimura T. Online map matching with route prediction［J］. IEEE Trans on Intelligent Transportation Systems ，2019， 20 （1）：338-347.

［3] Jagadeesh G R， Srikanthan T. Online map-matching of noisy and sparse location data with hidden Markov and route choice models［J］. IEEE Trans on Intelligent Transportation Systems ，2017， 18 （9）：2423-2434.

［4] Newson P， Krumm J. Hidden Markov map matching through noise "and sparseness［C］//Proc of the 17th ACM SIGSPATIAL International "Conference on Advances in Geographic Information Systems.New York：ACM Press，2009：336-343.

［5] Che Mingliang， Wang Yingli， Zhang Chi， "et al . An enhanced hidden Markov map matching model for floating car data［J］. Sensors ，2018， 18 （6）：1758-1776.

［6] Lou Yin， Zhang Chengyang， Zheng Yu， "et al . Map-matching for low-sampling-rate GPS trajectories［C］//Proc of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York：ACM Press，2009：352-361.

［7] Hsueh Y L， Chen H C. Map matching for low-sampling-rate GPS tra-jectories by exploring real-time moving directions［J］. Information Sciences ，2018， 433-434 ：55-69.

［8] Chen Chao， Ding Yan， Xie Xuefeng， "et al . TrajCompressor： an online map-matching-based trajectory compression framework leveraging vehicle heading direction and change［J］. IEEE Trans on Intelligent Transportation Systems ，2019， 21 （5）：2012-2028.

［9] Mohamed R， Aly H， Youssef M. Accurate real-time map matching for challenging environments［J］. IEEE Trans on Intelligent Transportation Systems ，2017， 18 （4）：847-857.

［10] Cui Ge， Bian Wentao， Wang Xin. Hidden Markov map matching based on trajectory segmentation with heading homogeneity［J］. GeoInformatica ，2021， 25 （1）：179-206.

［11] Bernstein D， Kornhauser A. An introduction to map matching for personal navigation assistants［J］. Geometric Distributions ，1996， 122 （7）：1082-1083.

［12] White C E， Bernstein D， Kornhauser A L. Some map matching algorithms for personal navigation assistants［J］. Transportation Research， Part C： Emerging Technologies ，2000， 8 （9）：91-108.

［13] Kong Xiangfu， Yang Jiawen. A scenario-based map-matching algorithm for complex urban road network［J］. Journal of Intelligent Transportation Systems ，2019， 23 （6）：617-631.

［14] Abdallah F， Nassreddine G， Denoeux T. A multiple-hypothesis map-matching method suitable for weighted and box-shaped state estimation for localization［J］. IEEE Trans on Intelligent Transportation Systems ，2011， 12 （4）：1495-1510.

［15] "Sharath M N， Velaga N R， Quddus M A. A dynamic two-dimensional （D2D） weight-based map-matching algorithm［J］. Transportation Research， Part C： Emerging Technologies， 2019， 98 （1）：409-432.

［16] Hashemi M， Karimi H A. A weight-based map-matching algorithm for vehicle navigation in complex urban networks［J］. Journal of Intelligent Transportation Systems： Technology， Planning and Ope-rations ，2016， 20 （6）：573-590.

［17] Wang Hongyu， Li Jin， Hou Zhenshan， "et al . Research on paralleli-zed real-time map matching algorithm for massive GPS data［J］. Cluster Computing ，2017， 20 （2）：1123-1134.

［18] Hu Yigong， Lu Binbin. A hidden Markov model-based map matching algorithm for low sampling rate trajectory data［J］. IEEE Access ，2019， 7 （12）：178235-178245.

［19] Qi Hui， Di Xiaoqiang， Li Jinqing. Map-matching algorithm based on the junction decision domain and the hidden Markov model［J］. PLoS One ，2019， 14 （5）：e0216476.

［20] Liu Minshi， Zhang Ling， Ge Junlian， "et al . Map matching for urban high-sampling-frequency GPS trajectories［J］. ISPRS International Journal of Geo-Information ，2020， 9 （1）：article No.31.

［21] Fang Weidong， Hu Rong， Xu Xiang， "et al . A novel road network change detection algorithm based on floating car tracking data［J］. Telecommunication Systems ，2020， 75 （2）：161-167.

［22] Torre F， Pitchford D， Brown P， "et al . Matching GPS traces to （possibly） incomplete map data： bridging map building and map matching［C］//Proc of the 20th International Conference on Advances in Geographic Information Systems.2012：546-549.

［23] 吳濤，向隆剛，龔健雅.路網更新的軌跡—地圖匹配方法［J］.測繪學報，2017， 46 （4）：507-515.（Wu Tao， Xiang Longgang， Gong Jianya. Renewal of road networks using map-matching technique of trajectories［J］. Journal of Geodesy and Geoinformation Science ，2017， 46 （4）：507-515.）

［24] "廖佳，俞薦中，李俊峰.一種利用網格劃分及方向加權的地圖匹配算法［J］.測繪通報，2017（3）：124-127.（Liao Jia， Yu Jianzhong， Li Junfeng. A map matching algorithm based on meshing and direction "weighting［J］. Bulletin of Surveying and Mapping ，2017（3）：124-127.）

［25] Xia Yingjie， Liu Yuncai， Ye Zhoumin， "et al . Quadtree-based domain decomposition for parallel map-matching on GPS data［C］//Proc of the 15th IEEE International Conference on Intelligent Transportation Systems.Piscataway，NJ：IEEE Press，2012：808-813.

［26] Chen Chao， Ding Yan， Xie Xuefeng， "et al . A three-stage online map-matching algorithm by fully using vehicle heading direction［J］. Journal of Ambient Intelligence and Humanized Computing ，2018， 9 （5）：1623-1633.