基于粒子濾波的行車軌跡路網匹配方法

　　摘要：行車軌跡是一種時間序列的地理空間位置采樣數據，而傳統的軌跡—路網匹配方法主要以全局或局部尋優的方式建立軌跡—路網匹配關系，影響了時空場景中數據的匹配計算過程的相對獨立性。針對這個問題，本文基于粒子濾波(ParticleFilter,PF)原理建立行車軌跡與道路網絡之間的匹配關系。首先，沿軌跡中車輛運動方向在道路網絡中搜索鄰近道路節點，在與道路節點拓撲鄰接的道路弧段上初始化隨機生成粒子，根據軌跡中車輛運動模型將粒子沿所在道路弧段移動;然后，基于PF原理計算各時刻粒子運動狀態及與行車軌跡采樣點之間的距離誤差，根據高斯概率密度函數計算粒子權重并利用隨機重采樣方法進行粒子重采樣，迭代更新粒子運動狀態;最后，計算與搜索到的道路節點拓撲鄰接的每條道路弧段中累計粒子權重，通過各道路弧段累計權重計算軌跡—路網匹配關系。以行車軌跡進行實驗表明，利用本文方法可以通過粒子時空變化反映采樣點的移動，行車軌跡—路網匹配結果的正確率大于85%，能夠實現行車軌跡和路網的準確匹配。

　　本文源自地球信息科學學報,2020,22(11):2109-2117.《地球信息科學學報》主要刊登地球系統科學及其相關邊緣交叉學科的新研究成果，主要包括前瞻性、創新性強的科學研究論文以及與國民經濟、技術研究開發緊密相關，應用價值較高的學術論文。本刊還辟有研究通訊、前沿探索、科技開發、綜述、學術動態等相關欄目。熱忱歡迎國內外學者踴躍賜稿。

　　1、引言

　　裝備有GNSS設備的車輛在行駛過程中會得到時間序列上地理位置變化這一軌跡數據。這些行車軌跡尤其是沿城市道路行駛的軌跡數據蘊含了豐富的居民交通出行、道路通行情況等信息，對于移動地理對象建模、地理規律發掘等方面具有重要意義[1,2,3]。通過行車軌跡—路網匹配建立行車軌跡與道路網絡之間的語義關聯則是進行深入的分析或知識挖掘的基礎。因此，有必要尋求高效的行車軌跡—路網匹配方法，準確地建立行車軌跡與道路網絡之間的匹配關系，為車輛運動信息快速提取與建模提供基礎，進而為智慧城市建設提供有效的決策支持[4,5,6,7,8]。

　　現有行車軌跡—路網匹配方法可根據匹配過程中采樣點的時空分布分為全局匹配和局部/增量匹配2類[2,9]。

　　(1)軌跡—路網的全局匹配方法[10,11,12,13,14]以完成地理位置采樣的軌跡數據為研究對象，通過數據后處理方法，提取軌跡中幾何、語義、距離權重、個性偏好等特征，將軌跡數據匹配到道路網絡。Yin等[10]將軌跡中采樣點到道路弧段的距離作為道路弧段的權重，利用最短路徑方法計算加權道路圖中的最短路徑，將其作為軌跡-道路匹配結果，高需等[11]則以用戶歷史軌跡中的個性偏好作為權重因子進行路網匹配。Nikoli?等[12]對軌跡數據濾波并通過聚類和位置投影的方式建立軌跡采樣點與道路節點和道路弧段的關聯關系，構建軌跡—路網候選匹配集，然后根據基因遺傳算法(GenericAlgorithm,GA)選取最佳路網匹配結果。Lou等[13]與李清泉等[14]根據軌跡中幾何和拓撲等特征構建最短路徑候選匹配集，然后通過軌跡采樣點之間的時間、空間、速度等約束條件，構建軌跡—路網匹配關系。這類方法以事后推定的方式計算軌跡—路網匹配關系，需要顧及整個軌跡數據特征，能夠處理長時間間隔的路網匹配問題，但方法計算速度較慢，一般用于離線地圖匹配。

　　(2)軌跡—路網的局部/增量匹配方法[9,15,16,17,18,19]基于軌跡數據的時空采樣過程，建立軌跡—路網局部匹配關系。Brakatsoulas等[17]基于自由空間(FreeSpace)理論計算軌跡曲線與道路網絡之間的Fréchet距離，根據軌跡和路網的局部相似的幾何特征性進行增量式軌跡—路網匹配。針對軌跡采樣點之間的時空連續特征，Newson等[18]和Song等[19]根據隱馬爾可夫模型(HiddenMarkovModels,HMM)計算軌跡中的采樣點與道路網絡之間的概率匹配關系，以采樣點到相鄰道路弧段的距離和道路中不同采樣位置之間的最短路徑計算HMM的發射概率和轉移概率，得到軌跡與道路網絡的匹配結果。Liu等[9]針對基于HMM的路網匹配方法中存在的標記偏置問題，提出時空條件隨機場(SpatialandTemporalConditionalRandomField,ST-CRF)方法，訓練路網匹配特征函數權重參數，通過HMM中類似的解碼方法計算軌跡-路網匹配結果。這類方法利用軌跡的局部特征進行路網匹配，計算速度較快，通過已匹配路網局部/增量延伸，最終得到全局最優匹配結果，可用于在線地圖匹配，但匹配結果容易受到軌跡噪聲的影響，或依賴“貪心算法”策略尋找最優解。

　　車輛在地理空間運動產生的時空位置記錄，是一個動態的地理位置采樣過程的結果，而粒子濾波(ParticleFilter,PF)作為一種序貫蒙特卡羅(SequentialMonteCarlo)方法，具有一定的時空模型模擬能力[20,21]，能夠根據上一時刻觀測值、當前時刻模型模擬值與觀測值，通過粒子重采樣和權重更新優化當前模型模擬結果，可處理軌跡中的噪聲并減少軌跡—路網匹配過程中對已匹配結果準確性的依賴，因此可利用PF方法對行車軌跡中車輛的時空運動過程進行模擬，建立行車軌跡—路網的匹配關系。基于此，本文利用PF原理對行車軌跡中車輛的時空運動過程進行建模，在拓撲關聯的道路弧段中生成粒子，構建行車軌跡與道路網絡的匹配方法，并通過行車軌跡為研究對象，對方法的可靠性和準確性進行實驗和分析。

　　2、粒子濾波與軌跡—路網匹配

　　2.1粒子生成

　　本文以行車軌跡采樣點鄰近的道路節點拓撲關聯的道路弧段為粒子生成區間，所有粒子均位于相鄰道路弧段，是一個沿道路線性度量空間分布的二維空間采樣點，其中行車軌跡中采樣點和相鄰道路弧段的關系表示如下：

　　(1)假定沿著行車軌跡S中車輛運動方向，與軌跡采樣點Si(xi,yi)相鄰近j個道路節點N{N1,N2,,Nj};

　　(2)與道路節點Nk∈N相鄰的l個道路弧段L{L1,L2,…,Ll}中，存在一條道路弧段Lm∈L，其中每條道路弧段Lm由n個頂點p{p1,p2,…,pn}組成;

　　在PF過程中，需要在粒子采樣空間生成o個隨機粒子q{q1,q2,…,qo}。為使得生成粒子具有隨機性，粒子的生成需要滿足2個條件：(1)粒子q在l個道路弧段L中產生的概率具有隨機性;(2)粒子q在道路弧段Lm∈L的幾何坐標具有隨機性。

　　因此，可通過隨機數生成索引m∈[1,2,…,l]從L中選取道路弧段Lm。然后，根據隨機長度比例r∈[0,1]從Lm中生成粒子qkLm，如圖1所示。詳細步驟如下：

　　圖1粒子的生成

　　(1)依次計算道路弧段Lm中相鄰頂點{pmi,pmi+1}組成的子弧段Lmi的長度SLmi，如式(1)所示，式中Length(·)為長度計算函數。

　　(2)計算由弧段起點至弧段頂點pmi+1的子弧段ALmi累計長度比例ASLmi，如式(2)所示。

　　(3)根據隨機長度比例r，計算粒子坐標qkLm(r)，如式(3)所示。

　　(4)最終得到沿道路網絡弧段線性度量空間隨機分布的初始化隨機粒子q，如式(4)所示。其中k為粒子索引，生成的粒子滿足條件(1)和條件(2)隨機性的要求。

　　2.2行車軌跡—路網匹配

　　在傳統的PF方法中，粒子隨機分布在研究區域中，并隨著行車軌跡采樣點的狀態變化不斷更新，從而更新采樣點的位置坐標。而在本文行車軌跡—路網匹配方法的計算過程如下：

　　(1)從車輛運動產生的行車軌跡采樣點出發，搜索鄰近的道路節點，根據道路節點拓撲鄰接的道路弧段初始化產生隨機粒子;

　　(2)通過行車軌跡中車輛運動模型更新粒子在道路弧段中的位置，利用粒子與下一時刻軌跡采樣點的地理位置計算粒子權重，并統計每條拓撲鄰接道路弧段的粒子權重，進行粒子重采樣，根據行車軌跡采樣時刻迭代更新軌跡采樣位置與粒子狀態;

　　(3)當搜索到新的鄰近道路節點時，計算各條道路弧段的累計粒子權重，計算累計粒子權重最大的道路弧段作為匹配道路弧段;

　　(4)以道路節點為匹配關系分界線，更新行車軌跡與路網的匹配關系，返回步驟(1)并根據新的道路節點及拓撲鄰接道路弧段集合自動生成隨機粒子采樣，不斷迭代直至車輛完全停止運動。行車軌跡—路網匹配算法的流程如圖2所示。

　　圖2基于粒子濾波的車行軌跡—路網匹配算法流程

　　基于PF原理的行車軌跡—路網匹配方法，假定輸入行車軌跡S，軌跡中車輛勻速運動速度為v，運動模型過程的噪聲標準差為ς，同時，利用高斯概率密度函數作為粒子權重函數，其標準差σ表示高斯函數的帶寬，將粒子與軌跡采樣點之間的距離作為函數輸入，計算得到粒子權重w，此外，隨機粒子個數為o，道路網絡及道路節點和弧段Road(N,L)，行車軌跡采樣點與道路節點的搜索距離閾值為d。在這個過程中，在相鄰軌跡采樣點之間的軌跡中車輛運動模型可以假設為一個勻速運動的過程，因此，可通過計算當前軌跡采樣點及其之前時刻軌跡采樣點之間的軌跡片段平均速度，將其作為PF方法中車輛運動模型的速度輸入，對粒子運動情況進行模擬，此外，如果道路網絡中不同等級道路弧段的限速信息已知，可直接將其作為車輛運動模型的速度輸入。運動模型如式(5)所示。

　　式中：St為軌跡采樣點在tt時刻坐標;θ為車輛的運動方向(與正北方向順時針轉角);v為運動速度;;S?t+1為tt+1時刻軌跡采樣點的位置預測。粒子生成與更新算法過程如下：

　　(1)搜索與行車軌跡中采樣點Si距離小于d的道路網節點NSi，并根據NSi查找道路網絡中拓撲鄰接的道路弧段LSi，在LSi上初始化產生o個隨機粒子。

　　(1)如果是首次初始化粒子，則準備開始PF過程模擬;

　　(2)否則，統計每條鄰接道路弧段LSi的累計粒子權重，將權重最大的道路弧段作為對應行車軌跡片段的匹配道路弧段。

　　(2)根據軌跡中車輛運動方向，根據采樣時間先后順序從行車軌跡中順序選取采樣點Si;

　　(3)根據PF原理和軌跡中車輛運動模型，在鄰接道路弧段LSi中更新粒子狀態，其中，粒子在軌跡中的運動存在標準差ς的隨機噪聲;

　　(4)計算粒子與行車軌跡采樣點的距離D，根據式(6)計算粒子權重w

　　(5)歸一化權重，并對粒子重采樣;

　　(6)重復步驟(1)、(2)(3)，直至采樣點Si以距離d搜索到新的道路節點，則返回步驟(1)。

　　其中，粒子重采樣方法為隨機重采樣，通過不斷迭代選擇權重較大的粒子作為新的粒子，然后利用車輛運動模型計算下一時刻粒子狀態。PF粒子權重的影響因素主要為軌跡采樣點在不同時刻的位置以及粒子權重函數式(6)。在該過程中可能會存在粒子退化現象，但是由于本文方法中行車軌跡采樣點在每條道路弧段中移動時間較短，并且在道路節點處重新生成粒子，因此，粒子退化現象對本文方法的影響較為有限。

　　3、行車軌跡—路網匹配實驗結果與分析

　　3.1實驗數據

　　本文采用行車軌跡為實驗對象，由兩條長時間序列采集的行車軌跡組成。其中，行車軌跡的長度約為102km，軌跡采樣點共計1838個;水平采樣精度為10m，采樣時間間隔為10s。具體情況如表1所示。

　　表1車行軌跡采樣信息

　　研究區域中道路數據和輔助遙感影像來自于該區域的基礎地理數據庫，研究區域面積約為55km2，道路中路網分布比較復雜，在部分區域路網密度較高。數據空間分布如圖3所示。

　　3.2實驗結果與分析

　　3.2.1數據預處理與參數選擇

　　行車軌跡—路網匹配過程中，首先需要對數據進行拓撲檢查，根據道路數據構建具有弧段和節點結構的道路網絡，同時對行車軌跡進行離群值粗差剔除等預處理，然后根據PF原理實現行車軌跡與路網的匹配。其中，相關參數的選取方法如下：

　　(1)計算每個道路節點及其最鄰近道路節點之間的距離，以所有道路節點最鄰近道路節點距離平均值的2倍，作為軌跡采樣點搜索鄰近道路節點的范圍d的參考值，在本文實驗中d的值為70m;

　　(2)假定在相鄰軌跡采樣點之間車輛的運動速度v為勻速，由于本文道路數據中未提供道路限速信息，因此車輛運動速度可通過當前時刻和之前時刻軌跡采樣點的距離及其時間間隔計算得到，將行車軌跡中相鄰軌跡采樣點之間距離平均值的0.5倍作為運動模型的過程噪聲標準差ς的參考值，在本文實驗中ς為10m;

　　(3)以道路網絡中道路弧段長度的平均值作為高斯概率密度函數標準差σ的參考值，在本文實驗中σ的值為1000m;

　　(4)根據道路網絡中每個道路節點的復雜程度作為隨機粒子個數o的參考依據，在道路節點復雜程度較高的道路數據中設置較大的粒子數目，反之亦然。在本文實驗中與道路節點鄰接的道路弧段數目以4條為主，因此可設置隨機粒子個數o為100。

　　3.2.2粒子的隨機生成

　　在行車軌跡中采樣點濾波初始時刻，粒子在道路弧段中是隨機生成的，如圖4所示，假定一條道路弧段由9個頂點組成(綠色小圓點)，從弧段起點到弧段終點，根據式(1)和式(2)計算各個頂點組成的子弧段在道路弧段中的累計長度比例，分別為0%、21%、31%、43%、55%、67%、76%、87%、100%(綠色字體)，初始時刻在道路弧段中隨機生成5個粒子，在道路弧段中的長度比例分別為17%、38%、52%、80%、94%(紅色字體)，則根據長度比例以式(3)在相應的子弧段中計算粒子在道路弧段中的幾何位置(紅色大圓點)。由圖可見，粒子能夠利用隨機生成的長度比例，根據粒子坐標計算公式，分別分布在道路弧段的不同子弧段中。

　　圖3研究區域中車行軌跡與道路網絡空間分布

　　圖4基于道路弧段的粒子生成

　　注：綠色數字為各個頂點組成的道路子弧段累計長度比例，紅色數字為隨機粒子組成的道路子弧段累計長度比例。

　　3.2.3粒子移動與路網匹配

　　根據鄰近道路節點拓撲關聯的道路弧段生成粒子，然后利用PF原理對行車軌跡采樣點和粒子每個時刻的狀態進行更新，最后根據累計粒子權重匹配道路弧段，過程如圖5所示。

　　由圖5可見，在初始時刻1，軌跡采樣點(紅色大圓點)搜索到道路節點有4條鄰接道路弧段，分別在每條道路弧段中生成粒子集(其他顏色小圓點)，在時刻2，車輛位置更新后軌跡采樣點移動到下一時刻，道路弧段中粒子的數量和位置得到更新，在時刻3，隨著軌跡采樣點位置的更新，粒子的空間分布發生較大變化，開始集中在待匹配道路弧段，在時刻4，粒子則集中在了待匹配道路弧段，這條弧段中的粒子數量顯著增多，進而可以通過每條道路弧段的累計粒子權重判斷出行車軌跡—路網的匹配結果。由圖可見，本文方法能夠根據PF原理，更新不同行車軌跡位置采樣時刻的粒子在道路弧段中的位置，并通過這個過程，計算待匹配道路弧段的累計粒子權重，實現行車軌跡與道路網絡的匹配。

　　圖5軌跡采樣點不同時刻粒子位置的變化

　　3.2.4行車軌跡—路網匹配

　　為了對本文方法路網匹配能力進行實驗對比，首先，基于距離判別法將軌跡點與鄰近道路網絡弧段進行距離投影，根據軌跡點與鄰近道路弧段的距離計算其匹配關系，對行車軌跡1和行車軌跡2進行實驗，結果如圖6所示。

　　在圖6基于距離判別方法的實驗結果中，黑色實線為與行車軌跡正確匹配的道路弧段，灰色實線為與行車軌跡錯誤匹配的道路弧段。由圖可見，行車軌跡1和行車軌跡2均匹配到了鄰近道路弧段，但匹配結果在道路節點處存在較多錯誤匹配，導致行車軌跡-路網匹配結果在時間和空間上存在一定的不連續性，與軌跡中車輛運動情況存在不一致。

　　利用本文基于PF的行車軌跡-路網匹配方法對研究區域中行車軌跡和道路網絡進行匹配，實驗結果如圖7。圖中黑色實線為與行車軌跡正確匹配的道路弧段，灰色實線為與行車軌跡錯誤匹配的道路弧段，灰色虛線為與行車軌跡未匹配的道路弧段。由圖可見，行車軌跡-路網匹配結果覆蓋了大部分區域，而在局部路網密度較高的復雜通行區域存在一定的錯誤匹配結果，本文方法能夠從行車軌跡中計算出軌跡-路網匹配關系。

　　本文以用“正確匹配長度/軌跡總長度”計算行車軌跡-路網匹配結果的正確率。對實驗結果進行統計，分別從匹配長度、正確匹配、錯誤匹配、未匹配進行統計，結果如表2所示。

　　在基于距離判別法的實驗結果中，行車軌跡1的正確匹配路網長度為64944m，路網的匹配準確率為84.24%，而行車軌跡2的正確匹配路網長度為21252m，路網的匹配正確率為83.68%，行車軌跡1和行車軌跡2的路網匹配長度均比實際行車軌跡長度大，因此，路網匹配結果中均存在明顯的過匹配現象;在本文方法實驗結果中，行車軌跡1匹配路網長度為71220m，其中正確匹配路網65921m，未匹配路網長度8882m，路網匹配正確率為85.51%，行車軌跡2匹配路網長度為25057m，其中正確匹配路網23621m，未匹配路網長度2578m，路網匹配的正確率為93.01%。由表可見，本文方法能夠在較為復雜的道路網絡中建立行車軌跡-路網的正確匹配關系，對85%以上的行車軌跡建立匹配關系，同時能夠使匹配結果具有時空連續性。

　　圖6基于距離判別法的車行軌跡—路網匹配結果

　　圖7本文基于PF方法的車行軌跡-路網匹配結果

　　表2車行軌跡-路網匹配結果統計

　　通過實驗結果可見，本文方法基于PF原理構建行車軌跡-路網匹配方法，使得路網匹配方法在計算過程中不依賴于全局或局部/增量式匹配過程的尋優條件，使得計算過程具有相對獨立性，具有較高的匹配準確率并且行車軌跡-路網匹配結果具有路徑連續性，與車輛實際運動情況較為一致。

　　4、結論

　　行車軌跡—路網匹配方法往往需要顧及行車軌跡中采樣點的時空連續特征。現有行車軌跡—路網匹配方法利用采樣點的全局或局部時空連續特征，依賴“貪心算法”尋優策略或易受軌跡噪聲影響，獲得的路網匹配結果準確性和時空連續性存在一定的不足。本文基于PF原理通過3個方面構建行車軌跡—路網匹配關系：(1)利用行車軌跡的采樣點鄰近道路網絡弧段隨機生成粒子;(2)通過軌跡中車輛運動模型計算不同軌跡采樣時刻下粒子的運動狀態，根據粒子與軌跡采樣點之間的距離誤差計算粒子權重，進行粒子重采樣并更新粒子狀態;(3)根據每條道路弧段中的累計粒子權重對行車軌跡與道路網絡進行匹配。實驗表明，本文方法對長度約為102km的較長時間采樣序列的行車軌跡進行路網匹配，路網匹配結果的正確率大于85%，能夠基于PF原理將行車軌跡與道路網絡進行準確地匹配，使得匹配過程具有相對獨立性，同時保持匹配結果的時空連續性。本文方法具有一定的實時運算能力，可對較大研究區域中行車軌跡數據通過并行運算方式對本文方法的在線行車軌跡-路網匹配進一步研究。

　　參考文獻：

　　[1]吳華意,黃蕊,游蘭,等.出租車軌跡數據挖掘進展[J].測繪學報,2019,48(11):1341-1356.

　　[2]高文超,李國良,塔娜.路網匹配算法綜述[J].軟件學報,2018,29(2):225-250.

　　[5]高強,張鳳荔,王瑞錦,等.軌跡大數據:數據處理關鍵技術研究綜述[J].軟件學報,2017,28(4):959-992.

　　[6]張健欽,李明軒,段穎超,等.一種改進的快速浮動車地圖匹配方法[J].測繪通報,2017(1):87-92.

　　[7]劉張,王心迪,閆小勇.面向復雜城市道路網絡的GPS軌跡匹配算法[J].電子科技大學學報,2016,45(6):1008-1013.

　　[8]吳濤,向隆剛,龔健雅.路網更新的軌跡—地圖匹配方法[J].測繪學報,2017,46(4):507-515.

　　[11]高需,武延軍,郭黎敏,等.基于偏好的個性化路網匹配算法[J].軟件學報,2018,29(11):3500-3516.

　　[14]李清泉,胡波,樂陽.一種基于約束的最短路徑低頻浮動車數據地圖匹配算法[J].武漢大學學報·信息科學版,2013,38(7):805-808,885.

　　[15]朱遞,劉瑜.一種路網拓撲約束下的增量型地圖匹配算法[J].武漢大學學報·信息科學版,2017,42(1):77-83.