王浩巖，劉遠剛，李少華，梁 博，何宗宜,2

1.長江大學地球科學學院，湖北 武漢 430100；2.武漢大學資源與環(huán)境科學學院, 湖北 武漢 430079

空間軌跡數(shù)據(jù)代表了各種運動物體的移動性[1]，且在實時路徑規(guī)劃、路網(wǎng)更新、出行規(guī)律發(fā)現(xiàn)等諸多領域起著至關重要的作用。由于不同移動設備均存在定位誤差，且道路經(jīng)過地圖綜合過程已經(jīng)由真實世界中的面狀要素轉(zhuǎn)化為抽象平面下的線狀要素，軌跡與其實際所處道路之間存在偏差。因此，在處理和分析軌跡數(shù)據(jù)之前，應進行地圖匹配，使得軌跡被正確的定位在道路之上。在城市應用場景中，全球定位系統(tǒng)技術的進步和大數(shù)據(jù)處理技術的發(fā)展使得城市地區(qū)的定位數(shù)據(jù)以很短的時間間隔獲取，如1 s或5 s[2]。如何在兼顧效率及正確率的情況下，滿足高采樣率軌跡與復雜城市道路網(wǎng)絡的匹配成為一項挑戰(zhàn)。

地圖匹配可在處理實時GNSS數(shù)據(jù)的在線模式下進行，也可在擁有綜合GNSS軌跡信息的離線模式下進行[3]。根據(jù)執(zhí)行匹配操作時所考慮軌跡范圍的不同，現(xiàn)有的地圖匹配算法又可以分為3類：局部算法、增量算法及全局算法[3]。局部地圖匹配算法一次只考慮軌跡上的單個GNSS點，不考慮當前軌跡點與前后點之間的關系。這類方法往往直接基于軌跡點與路段之間的幾何關系(如歐氏距離)來判斷點所在的路段[4-5]，具有高效和易于實現(xiàn)的優(yōu)點，但由于忽略了軌跡點之間的時間和空間關系，使得此類算法對空間道路網(wǎng)絡數(shù)據(jù)的創(chuàng)建方式非常敏感[6]，實際應用中極易出現(xiàn)匹配錯誤的情況。增量地圖匹配算法通過考慮相鄰點，將拓撲[7-8]、運動狀態(tài)[9]及轉(zhuǎn)移概率[10-11]等信息引入地圖匹配過程，從而提高算法的性能。文獻[12]綜合考慮影響地圖匹配的幾何約束與拓撲約束，提出了一種路網(wǎng)拓撲約束下的增量型地圖匹配算法，以應對GNSS低頻性質(zhì)帶來的匹配不穩(wěn)定性和復雜城市路網(wǎng)帶來的計算復雜性。文獻[13]以道路拓撲結構為基礎，提出了一種基于道路追蹤的矢量道路匹配算法，根據(jù)不同道路拓撲結構的變化，進入不同的匹配狀態(tài)，進行實時匹配修正。文獻[14]針對拓撲匹配方法對于起始匹配位置的依賴性，綜合利用速度、距離和航向約束改進起始匹配路段和起始位置的判定，以起始位置為基礎、速度與時間信息為約束，確定匹配點。文獻[15]基于“分治”思想，通過將軌跡點分為相交軌跡點和非相交軌跡點將道路交點與道路區(qū)別處理，取得了較好的匹配效果。另外，一些基于動態(tài)權重的方法也成為最近的研究熱點，這類方法綜合考慮多種信息來評估候選集中每條道路的匹配可能[12]。文獻[16]提出了一種基于動態(tài)權重的地圖匹配算法，它的動態(tài)權重根據(jù)位置精度、速度以及與先前軌跡點的行駛距離計算。文獻[17]利用速度、方位差、垂直距離和空間相關性作為軌跡點匹配的影響因素，根據(jù)D-S理論(Dempster-Shafer evidence theory)動態(tài)估計每個因素的權重。但在增量匹配算法中，先前點的不正確匹配結果可能會累積并影響后續(xù)點的匹配[14]。全局地圖匹配算法基于相似性度量將整個軌跡映射到道路網(wǎng)絡中的路徑，由于軌跡上的GNSS點是分批考慮的，所以不會產(chǎn)生增量方法的誤差傳播問題。因此這類算法對采樣率不太敏感，保證在不同采樣率下均有較高匹配精度，但同時也導致了高采樣率情形下的低效率問題。早期的全局匹配算法基于幾何的思路進行相似性度量，其中Hausdorff距離與Fréchet距離為兩個較為經(jīng)典的相似性度量指標，但由于它們的計算公式中都包含最大化算子，使得基于這兩種方法的相似性度量均存在對異常值敏感的問題[18]。為了解決這一問題，更多的因子被引入到匹配過程，文獻[19]提出了一種時空匹配方法(ST matching method)，該方法將道路網(wǎng)絡的空間幾何和拓撲結構以及軌跡的時間、速度約束作為匹配特征來搜索匹配的子路徑，然后利用候選圖來確定全局最優(yōu)匹配路徑。文獻[20]使用由幾何似然、拓撲似然和時間似然組成的3部分似然函數(shù)，從候選集中獲得最佳匹配。文獻[21]提出保留在軌跡中的彎曲度可用于搜索最相似的匹配路徑，并在復雜路段的匹配中取得較好效果。另外，一些先進的算法也被應用于全局匹配，如隱馬爾科夫模型(HMM)[22-27]、粒子濾波器[28]、模糊邏輯模型[29-30]和條件隨機場[31]等，其中隱馬爾科夫模型由于其對噪聲不敏感，匹配精度較穩(wěn)定等特性被廣泛應用于各類地圖匹配場景中，在滿足齊次馬爾科夫假設和獨立觀測假設的條件下，該算法將每個采樣點的候選路段作為整條軌跡中的一個隱狀態(tài),通過計算發(fā)射概率與相鄰狀態(tài)之間的轉(zhuǎn)移概率,獲取全局可能性最高的路徑。

根據(jù)上述各類算法的特點，在面向高采樣率與復雜城市路網(wǎng)應用場景時，基于增量的匹配思路被更為廣泛的應用，但已有的相關算法在處理高采樣率軌跡時，仍存在以下兩個問題：①算法匹配時間不僅與軌跡點數(shù)量有關，也與車輛行駛路段的復雜程度密切相關，更高的采樣率及道路復雜度帶來了更為耗時的計算過程；②在路口點等復雜路段處，由于移動物體通常以低速進行移動，使得軌跡點間距離相對于其他區(qū)域更小，從而也容易導致錯誤匹配。針對以上兩個問題，本文主要關注在離線場景中算法性能的優(yōu)化，提出一種基于路徑增量的地圖匹配方法，能夠在提高計算效率的同時較好地處理復雜路段處的軌跡匹配問題，為解決相關問題提供有益思路。

1 基本概念與總體思路

1.1 道路匹配基本概念

軌跡T為移動設備所采集的位置點的集合，可以表示為T={pi|i=1,2,…,N}。路網(wǎng)為真實道路系統(tǒng)的數(shù)字表達，可以通過有向圖G(V,E)來描述，其中V為頂點的集合{vj|j=1,2,…,M}，E為邊的集合{ek|k=1,2,…,O}，頂點vj相關聯(lián)邊的數(shù)目稱為頂點vj的度，記作d(vj)。對于任意頂點vj，若d(vj)=1，稱vj為單連通點；若d(vj)=2，稱vj為過渡點；若d(vj)≥3，稱vj為路口點。將G(V,E)中的邊稱為路段，路徑P為一系列相連的路段的集合，表示為P={e0,e1,…,ej}。候選軌跡點為落在頂點vj鄰近區(qū)域內(nèi)的軌跡點集，記作I(vj)，下文將候選軌跡點簡稱為候選點。候選路段集為與軌跡點pi的誤差分布范圍相交路段的集合，表示為C(pi)。道路子網(wǎng)G′(V′,E′)為經(jīng)過過濾處理后，用于進行地圖匹配的路網(wǎng)，即G′?G，滿足V′?V,E′?E。

本文定義增量為兩個相鄰路口點之間的路徑，則可將地圖匹配抽象為根據(jù)軌跡T及路網(wǎng)G(V,E)，構建道路子網(wǎng)G′(V′,E′)，進行增量計算并最終確定物體實際運動路徑的過程。

1.2 匹配算法總體設計

本文算法旨在解決高采樣率軌跡在復雜路網(wǎng)中的地圖匹配問題，提高匹配效率以及優(yōu)化復雜路段處的匹配是本文算法的重點。算法可大致分為兩個部分：復雜道路網(wǎng)絡的組合過濾和針對道路子網(wǎng)的增量匹配過程，具體流程如圖1所示。在組合過濾部分，通過對路網(wǎng)G(V,E)的逐步過濾獲得道路子網(wǎng)G′(V′,E′)，首先采用距離約束過濾獲取候選路段集，然后基于道路連通性與方向一致性約束過濾無連通路段以及方向偏差較大路段，最后基于首尾路段識別結果，剪除單點連通路段，從而對復雜路網(wǎng)進行簡化，以減少后續(xù)增量過程中錯誤匹配的可能性以及不必要的耗時。在增量匹配部分，首先確定物體運動的起始路段，然后進行逐步增量計算以確定軌跡的匹配路徑；每一個增量計算過程均以路口點為起點(初次計算起點為起始路段的單連通點)，確定后續(xù)匹配路段，當匹配路段連接頂點為過渡點時則記錄當前路段，繼續(xù)確定下一路段，當匹配路段連接的頂點為路口點時，則進入下一個增量計算過程，直到出現(xiàn)單連通點(此時為終止路段)，匹配過程結束；在路口點處進行增量前進方向判斷的過程中，采用綜合Hausdorff距離及彎曲度特征的相似度評價方案進行路口點處候選點及連接路段的匹配，以減弱平行同向路段對匹配結果的影響，提高軌跡匹配精度。

圖1 算法流程

2 復雜道路網(wǎng)絡的組合過濾

在復雜的城市道路網(wǎng)絡中進行地圖匹配，難點在于對交叉路口以及平行道路的匹配。該區(qū)域的軌跡往往存在多個距離相近且形態(tài)相似的候選路段，容易導致錯誤匹配。因此，僅根據(jù)單個軌跡點是難以準確匹配的，需要將相近的軌跡點結合起來，形成運動對象的空間上下文信息。在采樣率較高的情況下，通過相近的軌跡點可計算出對象在當前時段內(nèi)的方向、速度等運動狀態(tài)，再結合附近路網(wǎng)的相關特征，一些無關路段可被剔除。理論上考慮的軌跡點越多匹配準確性越高，但計算成本也越高。因此，本文將相鄰兩個軌跡點的上下文信息與其附近道路的連通性、方向等特征結合，對候選路段進行過濾，剔除大量無關路段。圖2為道路網(wǎng)過濾結果的示意，其中原路網(wǎng)經(jīng)過距離、連通性、方向等一系列條件過濾和“剪枝”后得到與軌跡點比較匹配的候選“道路子網(wǎng)”。

圖2 過濾結果示例

2.1 距離約束過濾

地圖匹配的關鍵假設是GNSS定位存在誤差，且誤差是在一定的范圍內(nèi)[12]。將誤差范圍作為距離約束可以對路網(wǎng)進行初步過濾，構建初始候選路段集，合適的誤差范圍對于提高算法的精度及效率有著重要的意義。本文采用誤差圓構建緩沖區(qū)，刻畫軌跡點誤差范圍。已有研究表明，軌跡點的誤差與速度存在相關性，當運動物體速度變大時，定位誤差會在一定程度上減小[6]?？梢?，各軌跡點的誤差半徑并非固定，需要設置一個合理范圍。若半徑設置過小，會導致正確的路段被排除在外，反之，當半徑設置過大時，會增加匹配的計算量。因此，本文候選路段集通過一種動態(tài)調(diào)整的緩沖區(qū)選取，即以軌跡點為圓心初始半徑rp0構建緩沖區(qū)，若候選路段集為空，則將半徑擴大一個固定的步長rpstep，如此循環(huán)，直到候選路段集中至少包含一條路段為止。

2.2 道路連通性過濾

在以往的研究中，對于高采樣率軌跡一般指采樣間隔在30 s以內(nèi)的軌跡[32]，但運動對象的速度并不一致，當運動對象的速度較大時，軌跡間的距離也會變大，在低采樣率軌跡匹配中出現(xiàn)的“跳弧”現(xiàn)象也同樣會在高采樣率軌跡中出現(xiàn)。為避免因這一問題所帶來的歧義，本文將高采樣率軌跡定義為候選路段能夠滿足拓撲連通性的軌跡，基于這一定義即可對候選路段進行道路連通性的過濾。

根據(jù)城市道路通行規(guī)則將路段分為兩類：單向(通行)路段與雙向(通行)路段。在城市路網(wǎng)中，單向路段往往在復雜的交叉路口以及平行道路中大量出現(xiàn)，這類路段在地圖匹配過程中更容易出現(xiàn)匹配錯誤。道路連通性反映的是前后路段之間的連通關系，根據(jù)前后連接路段類型的不同，可以進一步將其連接關系分為單向路段與單向路段的連接，單向路段與雙向路段的連接以及雙向路段與雙向路段的連接。針對上述連接關系的特征，本文主要考慮了兩方面的連通性約束。

(1)拓撲連通性約束：基于緩沖區(qū)選擇的候選路段中，存在大量在幾何上相交但實際不具備連通性的路段，拓撲連通性約束是剔除這類路段的主要工具。其定義為對于軌跡中的任一點pi，其候選路段集C(pi)中存在路段ei與候選路段集C(pi+1)中某一路段ej端點相連或重疊。不滿足這一約束的路段將被剔除。

(2)方向連通性約束：如圖3(a)所示，對于單向通行路徑，其中的路段可抽象為一組有向線段，如果這組線段方向一致，則滿足方向連通性約束。其定義為對于軌跡中任一點pi，候選路段集C(pi)中存在路段ei與候選路段集C(pi+1)中某一路段ej相連或重疊，且當ei與ej相連時，應同時滿足兩路段方向在連接處首尾相接。圖3(b)中反映了兩類滿足拓撲連通性而不具備方向連通性的情況，這樣的路段應該被過濾。由于雙向路段沒有方向限制，故僅需要考慮單向路段相互連接時的方向連通性約束。

圖3 方向連通性

2.3 方向一致性過濾

在運動過程中軌跡方向與其實際行駛道路的方向應該是一致的，基于這一特性可以將候選路段中方向與軌跡方向有較大差別的路段剔除。方向一致性過濾應用于單向路段與雙向路段的連接以及單向路段與單向路段的連接，在單向路段與雙向路段的連接情況下，以單向路段方向作為連接路段方向。方向一致性過濾需要經(jīng)過長度比過濾與方位角過濾兩個步驟。

(1)長度比過濾：如圖4(a)所示，p1、p2為兩個連續(xù)的軌跡點，P1、P2與P3為3條包含候選路段的路徑，且這3條路徑均可作為p1，p2的匹配路徑，p1、p2在其對應候選路段上的投影即為該軌跡點的實際位置，對于高采樣率的軌跡，它們的分布與實際所在的路段通常呈近似平行的關系。基于這一認識，在進行軌跡方向與路段方向?qū)Ρ惹?，通過連續(xù)軌跡點之間的距離與其在候選路段上投影點之間距離的長度比剔除橫向路段，同時避免軌跡順序與對應候選路段順序不一致的情況。根據(jù)試驗這一比值設為0.8時，能達到較好的剔除效果。在圖4(a)中，軌跡點向P3投影后的長度Len3遠小于軌跡點之間的距離，從而可以將路徑P3剔除。

(2)方位角過濾：如圖4(b)所示，在完成長度比過濾后，剩下的即為兩條方向相反的路徑，通過計算軌跡與軌跡在路徑上投影點之間的向量方位角之差可以剔除方向相反的路徑，其中向量的方位角為正北方向沿順時針旋轉(zhuǎn)至當前向量所經(jīng)過的水平角度，計算公式為

(1)

式中，α為當前向量的方位角；(x1,y1)、(x2,y2)分別為向量的首尾點坐標。

圖4 方向一致性過濾

2.4 單點連通路段“剪枝”

在完成上述過濾步驟后，滿足連通性和方向一致性的路段被保留了下來。在這些剩余的路段構成的子網(wǎng)中，除了首尾路段之外，若還存在其他路段的頂點度數(shù)為1，則可將它們“剪枝”，因為這類單點連通路段不可能作為最終匹配路徑上的中間路段。圖2中經(jīng)過連通性、方向一致性約束過濾后的路網(wǎng)中仍存在單點連通路段，即被“剪枝”路段(紅色)，它們會增加后續(xù)地圖匹配的運算量，需要剔除。算法中，基于這一規(guī)則依次遍歷各個路段，分別計算各路段起點與終點的度數(shù)，刪除除首尾路段之外的其他單點連通路段即可。其中確定首尾路段的方法作為本文增量匹配算法的關鍵問題在3.2.2節(jié)中詳細介紹。

3 基于路徑的增量匹配算法

3.1 相似度評價

在基于幾何特征的匹配方法中，一般采用距離、角度等幾何特征進行軌跡點的匹配。采用Hausdorff距離作為距離因子，可以有效降低相似平行路段帶來的誤差。當匹配的路網(wǎng)較為復雜時，僅僅依賴距離和角度因子容易出現(xiàn)錯誤匹配，而彎曲度作為一種內(nèi)在的幾何特征，在采集的GNSS軌跡中被很好地保留，且軌跡與其行駛路段的彎曲度特征高度一致，從而可以用于進一步提升匹配精度。本文采用基于Hausdorff距離和彎曲度的相似度評價方法。

3.1.1 距離因子

在路口點的匹配中，需要將連續(xù)的軌跡點匹配到路口點相關的前后兩個路段上，距離評價因子為上述兩組點之間的距離的映射。Hausdorff距離是描述兩組點之間相似程度的一種量度，本文采用Hausdorff距離計算軌跡點與軌跡在匹配路段上的投影點之間的距離。其定義[18]為：假設有兩組集合A={a1,a2,…,ap},B={b1,b2,…,bq}，這兩組點之間的Hausdorff距離為

H(A,B)=max(h(A,B),h(B,A))

(2)

式中，h(A,B)=max min‖a-b‖，(a∈A,b∈B)；h(B,A)=max min‖b-a‖，(a∈A,b∈B)；‖*‖為點集A與點集B之間的距離范數(shù)。

3.1.2 彎曲度因子

彎曲度因子用于描述路口點處候選點與待匹配路段的幾何形態(tài)特征。在光滑曲線中采用曲率描述某點處的彎曲程度，其定義為γ(s)是二維平面上一條以弧長為參數(shù)的光滑曲線，在曲線上存在點M與點N，其中點M對應弧長為s，在點M處切向量的傾角為α，點N對應弧長為s+Δs，在點N處的切向量的傾角為α+Δα，則曲線γ(s)在點M處的曲率為

(3)

式中，Δα為M、N兩點間切線的轉(zhuǎn)角，其值域為(-π,π]；Δs為M、N兩點間弧長的變化。

在一段弧長上總的曲率變化可以通過曲率的積分表示，在上述以弧長為參數(shù)的光滑曲線γ(s)上，M、N之間的曲率積分可以表示為

(4)

式中，K(M,N)為點M、N之間的曲率積分；k為弧段上某點處的曲率，即M、N兩點之間的曲率積分描述了從點M出發(fā)沿γ(s)移動到點N所轉(zhuǎn)過的角度。

但在地圖匹配問題中，軌跡及道路均被離散化為點的序列，本文參考文獻[21]中對于離散點序列曲率積分的計算方法，采用離散化后點序列中前后相鄰的兩個點形成的向量來近似表示該位置的切向量。假設平滑曲線γ被離散化為點序列[a1,a2,…,an]，則離散化后曲線的曲率積分為

(5)

式中，在計算各點曲率時，以正北方向作為基準，采用方位角代替原公式中的傾角，式(1)為方位角的計算方式。

3.1.3 相似度計算

路口點處的相似度為上述兩個因子的綜合，表達式為

(6)

式中，Hdif為軌跡與對應路徑之間的Hausdorff距離的差值的絕對值；Kdif為軌跡與對應道路的曲率積分差的絕對值，相似度的值域為(0,1]，值越大時則當前路徑與軌跡越為相似。

3.2 增量匹配

3.2.1 增量匹配過程

在現(xiàn)實世界中，物體沿道路的運動通常為沿路線移動并在路口處判斷前進方向的過程，當確定了某一段路徑的首尾點后，它們之間的路徑往往是唯一的，所以物體移動的過程可以被抽象為沿運動方向的增量計算。在傳統(tǒng)的增量匹配方法中，通常是將軌跡點或者軌跡片段作為增量，但未能充分重視因道路的復雜性導致的錯誤匹配，同時在處理高采樣率軌跡時也帶來了更高的時間成本。基于路口點的增量匹配方法在前文過濾器的基礎上將兩個相鄰路口點之間的路徑作為增量，將軌跡與路段的匹配問題轉(zhuǎn)化為路口點處的方向選擇問題。

算法通過道路子網(wǎng)的頂點類型來控制匹配的過程，在確定初始路段后，進入增量計算過程，當路段終點為單連通點時，此時為終止路段，匹配過程結束；當路段終點為過渡點時，此時路段的選擇是唯一的；當路段終點為路口點時，此時為下一增量的起點，進行路口點匹配。算法1為增量匹配過程的偽代碼。

算法1：增量匹配過程

輸入：軌跡Trcak，道路子網(wǎng)G′

輸出：匹配路徑P

調(diào)用算法2，確定起始路段startSection

P.append(startSection)

獲取起始路段終點estart.lastPoint

vjudge←estart.lastPoint #初始化當前判斷點

ejudge←estart#初始化當前判斷路段

while True:

獲取與當前判斷點連接的路段列表E

if len(E)=1: #當E中路段數(shù)量為1時

break

else if len(E)=2: #當E中路段數(shù)量為2時

從vjudge的連接路段列表中剔除ejudge，剩下的即為后向路段ebackward

P.append(ebackward)

ejudge←ebackward

vjudge←ebackward.lastPoint

else if len(E)>=3: #當E中路段數(shù)量大于或等于3時

調(diào)用算法3，完成路口點的匹配操作，獲取ebackward

P.append(ebackward)

ejudge←ebackward

vjudge←ebackward.lastPoint

3.2.2 首尾路段的確定

增量算法中起始位置匹配誤差會隨著道路的延續(xù)而傳遞累計[14]。所以，首尾點路段的識別對本文匹配算法的成敗至關重要，同時也決定了哪些單連通路段可以被提前“剪枝”。本文參考“前瞻”[33]思想進行首尾路段的確定，算法2為起始路段的確定方法，對于終止路段的確定，以終止軌跡點作為起點進行逆向判斷即可。需要注意的是當候選路段所對應的路口點相同時，根據(jù)該路口點處路段匹配結果即可確定起止路段；當候選路段所對應的路口點不同時，則分別針對不同路口點處進行路段匹配，然后選取與軌跡相似度更高的路段作為起止路段。如圖5所示，e1、e2為起始軌跡點p1的候選路段，圖5(a)中e1、e2對應于同一路口點v1，在v1處執(zhí)行匹配，可以確定e1為起始路段；圖5(b)中e1、e2分別對應于路口點v1、v2，此時分別進行匹配并比較相似度即可確定起始路段。

圖5 首尾路段的選擇

算法2：起始路段的確定

輸入：軌跡Trcak，“剪枝”前路網(wǎng)filterRoads

輸出：起始路段startSection

i←0

startSection←filterRoads[0] #初始化起始路段

while True:

獲取候選路段集C(Trcak[i])

if len(C(Trcak[i]))=0: #當候選路段集中路段數(shù)量為0時

i←i+1

else if len(C(Trcak[i]))=1: #當候選路段集中路段數(shù)量為1時

startSection←C(Trcak[i])[0]

break

else if len(C(Trcak[i]))≥2: #當候選路段集中路段數(shù)量大于或等于2時

根據(jù)式(7)計算與候選路段連接的路口點處的相似度

確定最優(yōu)起始路段esimmax

startSection←esimmax

break

3.2.3 路口點處的匹配

路口點處的匹配用于確定增量匹配的方向，算法3描述了匹配過程。首先基于路口點與搜索半徑構建候選點集I，然后獲取候選點與其在對應路段上的投影點，計算軌跡與路段的相似度，最終通過對比相似度確定增量匹配方向。圖6描述了路口點v1的匹配過程，如圖6(a)所示，e1為上一增量已經(jīng)匹配的路段，v1為下一個增量匹配的起點，此時需要確定后續(xù)增量的匹配方向，即從路徑e1→e2和e1→e3中確定與軌跡匹配的路徑，圖6(b)、(c)分別刻畫了兩種不同路徑的匹配過程，通過計算軌跡與其投影點兩組點集之間的相似度可以較容易地確定e3為后續(xù)的匹配路段。其中，候選點集I應同時包含已通過及未通過路口點的軌跡點，否則以步長rcstep逐步增加搜索半徑rc的長度，直到條件滿足。

圖6 路口點處匹配過程

圖7 候選點位置判斷

算法3：路口點處匹配

輸入：軌跡Trcak，當前判斷點vjudge，當前判斷路段ejudge，與vjudge連接的路段列表E

輸出：匹配路段ematch

獲取vjudge的候選點集I#此時vjudge為路口點

根據(jù)是否通過vjudge將I中的軌跡點分為Ipassed及Ifailed兩部分

foreinE:

ife.equals(ejudge):

pass

else:

Iproject←[] #初始化投影點集

計算Ifailed中軌跡點在ejudge上的投影點，并添加至Iproject

Iproject.append(vjudge)

計算Ipassed中軌跡點在e上的投影點，并添加至Iproject

計算I與Iproject之間的相似度

獲取相似度最高的路段esimmax

ematch←esimmax

4 試驗與討論

4.1 試驗數(shù)據(jù)預處理

為驗證算法的有效性，本文從微軟亞洲研究院提供的GeoLife 1.3公開數(shù)據(jù)集中選取了部分出租車軌跡進行試驗，軌跡采樣間隔為1 s。路網(wǎng)數(shù)據(jù)為北京市的道路交通網(wǎng)絡，選取軌跡所經(jīng)過路段中包含大量平行路段、復雜交叉路口等特殊路段，測試軌跡如圖8所示，相關信息見表1。

圖8 測試軌跡

表1 測試軌跡信息表

在進行匹配工作前，需要對軌跡數(shù)據(jù)進行預處理，基于移動速度剔除軌跡中可能存在的異常軌跡點，異常軌跡點可分為兩類：①軌跡移動速度遠低于正常行駛速度或停滯的點；②由于定位誤差造成的偏離正常軌跡范圍的點。這兩類異常點均表現(xiàn)為速度上的異常，可通過速度閾值剔除，試驗中剔除了速度小于1 m/s或速度大于35 m/s的異常點。

試驗主機環(huán)境為AMD Ryzen 5 3600 6-Core Processor CPU @3.60 GHz、16.0 GB RAM、WIN10 x64；采用的編程環(huán)境為Python 3.6。

4.2 試驗結果及對比分析

為更好地驗證算法的效果，將本文算法與曲率積分約束的地圖匹配算法(以下簡稱為“曲率積分算法”)[21]及HMM算法[22]進行對比。主要從匹配結果的精度及效率角度對算法進行測試。為評價算法匹配精度，本文借鑒文獻[34]中評價方法，將評價指標設為：路徑不匹配分數(shù)(route mismatch fraction，RMF)，準確率(Precision)，召回率(Recall)，具體定義如式(7)—式(9)所示

(7)

(8)

(9)

式中，L+為算法計算結果中與真實路徑相比錯誤增加的長度；L-為算法計算結果中與真實路徑相比錯誤減少的長度；Lmatched為算法計算結果中正確匹配路徑的總長度；Linferred為算法計算結果的總長度；Lreal為真實路徑的總長度。

考慮試驗數(shù)據(jù)集中的GNSS定位誤差和道路寬度，將候選路段緩沖區(qū)半徑rp和候選點緩沖區(qū)半徑rc的初始長度均設為30 m，對應的步長設為5 m。同時,為比較相關算法在不同采樣頻率下的匹配性能,本文逐步提高采樣間隔至10 s，按照文獻內(nèi)的描述實現(xiàn)了相應算法，并利用上述指標進行對比試驗。

匹配結果指標統(tǒng)計如圖9中所示，在測試數(shù)據(jù)集中當采樣間隔為1 s時，本文算法的準確率達97.70%，召回率達97.10%，RMF為5.23%，相對于其他兩類算法均有較大提升，表明在高采樣率下本文算法能夠保證較高的匹配正確率。其原因主要包括兩個方面：①算法過濾器濾去了絕大部分錯誤路段，大大降低了錯誤匹配的可能性；圖10為采樣間隔為1 s時各數(shù)據(jù)集的匹配結果，其中紅色線條為本文算法匹配結果，綠色線條為曲率積分算法匹配結果，藍色算法為HMM算法匹配結果，灰色線條為北京市路網(wǎng)；可以看出HMM算法在匹配中出現(xiàn)了大量將軌跡匹配至方向相反路段的情況，而本文算法匹配前已過濾掉了反方向路段。②基于本文增量算法的匹配過程保證了路口點間路徑的唯一性，減弱了平行路段對匹配結果可能帶來的不利影響；如圖10(b)所示，曲率積分算法出現(xiàn)了兩條平行路段均被選擇的情況，其原因在于該方法是基于點對選擇匹配路段的，當軌跡采樣率較高時，同向平行的兩個路段可能在不同點對中被選擇，從而導致錯誤匹配，而本文算法則避免了對于平行路段的錯誤選擇。同時，算法在利用多層互通進行行駛方向變化的復雜場景的匹配中也表現(xiàn)出了較好的效果，其結果如圖10(d)所示。但隨著采樣間隔的提高，路口點匹配中候選點的數(shù)量將逐漸減少，使得算法準確率及召回率逐漸降低，且在采樣間隔為10 s左右時已無明顯的優(yōu)勢，說明本文算法對采樣率變化較為敏感。但由于算法獲取路徑的唯一性，RMF仍然明顯優(yōu)于其他算法。

圖9 地圖匹配精度評價指標

圖10 軌跡匹配結果

另外，對各類算法效率進行統(tǒng)計，結果如圖11所示。采樣間隔越短，本文算法的效率優(yōu)勢越明顯。其原因在于兩種對比算法中匹配單元的調(diào)用次數(shù)與軌跡點的數(shù)量密切相關，而匹配單元的頻繁調(diào)用無疑會導致更高的時間成本。而本文算法通過以路徑為增量，使得計算單元的調(diào)用次數(shù)僅與路網(wǎng)中路口點個數(shù)相關，而路網(wǎng)經(jīng)過組合過濾后，復雜度大大降低，從而實現(xiàn)了效率的進一步提高。圖12為采樣間隔為1 s時各算法中匹配單元的調(diào)用次數(shù)，當軌跡采樣間隔較短時，軌跡點數(shù)量遠大于需要匹配的路口點的數(shù)量，所以本文算法匹配單元的調(diào)用次數(shù)遠遠低于其他兩類算法，從而使得算法效率得到明顯提升。隨著采樣間隔的增加，軌跡點數(shù)量逐漸減少，但路口點的個數(shù)不變，故本算法效率優(yōu)勢將會逐漸消失，最終與全局匹配算法的效率接近。

圖11 算法效率

圖12 匹配單元調(diào)用次數(shù)

5 結 論

本文提出了一種高采樣率軌跡數(shù)據(jù)在復雜城市路網(wǎng)中的增量匹配方法，提高匹配效率的同時兼顧了對于復雜路段的處理。算法通過對路網(wǎng)的組合過濾消除了無連通路段及反向路段對匹配過程的影響，并采用路徑增量替代傳統(tǒng)增量匹配方法中的軌跡增量，使得匹配結果更加符合真實的車輛行駛路線。在路口點處采用曲率積分與Hausdorff距離的組合代替?zhèn)鹘y(tǒng)匹配算法中的幾何度量以提高起始路段以及路口點處的匹配精度。通過試驗驗證了本文算法的有效性，較好地解決了高采樣率數(shù)據(jù)在復雜路網(wǎng)匹配中準確率與效率之間的矛盾。

本文匹配算法的核心在于以路口點匹配為基礎的路徑增量過程，算法對于采樣率的變化較為敏感，當采樣率較低時，路口點處將有可能出現(xiàn)沒有軌跡點的情況，從而導致基于路口點的匹配失效。后續(xù)研究將進一步探討以路徑為增量的匹配思路處理低采樣率軌跡數(shù)據(jù)的可行性，增強算法對于不同采樣率數(shù)據(jù)的普適性。