基于粒子濾波的行車軌跡路網(wǎng)匹配方法

　　摘要：行車軌跡是一種時(shí)間序列的地理空間位置采樣數(shù)據(jù)，而傳統(tǒng)的軌跡—路網(wǎng)匹配方法主要以全局或局部尋優(yōu)的方式建立軌跡—路網(wǎng)匹配關(guān)系，影響了時(shí)空?qǐng)鼍爸袛?shù)據(jù)的匹配計(jì)算過(guò)程的相對(duì)獨(dú)立性。針對(duì)這個(gè)問(wèn)題，本文基于粒子濾波(ParticleFilter,PF)原理建立行車軌跡與道路網(wǎng)絡(luò)之間的匹配關(guān)系。首先，沿軌跡中車輛運(yùn)動(dòng)方向在道路網(wǎng)絡(luò)中搜索鄰近道路節(jié)點(diǎn)，在與道路節(jié)點(diǎn)拓?fù)溧徑拥牡缆坊《紊铣跏蓟S機(jī)生成粒子，根據(jù)軌跡中車輛運(yùn)動(dòng)模型將粒子沿所在道路弧段移動(dòng);然后，基于PF原理計(jì)算各時(shí)刻粒子運(yùn)動(dòng)狀態(tài)及與行車軌跡采樣點(diǎn)之間的距離誤差，根據(jù)高斯概率密度函數(shù)計(jì)算粒子權(quán)重并利用隨機(jī)重采樣方法進(jìn)行粒子重采樣，迭代更新粒子運(yùn)動(dòng)狀態(tài);最后，計(jì)算與搜索到的道路節(jié)點(diǎn)拓?fù)溧徑拥拿織l道路弧段中累計(jì)粒子權(quán)重，通過(guò)各道路弧段累計(jì)權(quán)重計(jì)算軌跡—路網(wǎng)匹配關(guān)系。以行車軌跡進(jìn)行實(shí)驗(yàn)表明，利用本文方法可以通過(guò)粒子時(shí)空變化反映采樣點(diǎn)的移動(dòng)，行車軌跡—路網(wǎng)匹配結(jié)果的正確率大于85%，能夠?qū)崿F(xiàn)行車軌跡和路網(wǎng)的準(zhǔn)確匹配。

　　本文源自地球信息科學(xué)學(xué)報(bào),2020,22(11):2109-2117.《地球信息科學(xué)學(xué)報(bào)》主要刊登地球系統(tǒng)科學(xué)及其相關(guān)邊緣交叉學(xué)科的新研究成果，主要包括前瞻性、創(chuàng)新性強(qiáng)的科學(xué)研究論文以及與國(guó)民經(jīng)濟(jì)、技術(shù)研究開(kāi)發(fā)緊密相關(guān)，應(yīng)用價(jià)值較高的學(xué)術(shù)論文。本刊還辟有研究通訊、前沿探索、科技開(kāi)發(fā)、綜述、學(xué)術(shù)動(dòng)態(tài)等相關(guān)欄目。熱忱歡迎國(guó)內(nèi)外學(xué)者踴躍賜稿。

　　1、引言

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

　　現(xiàn)有行車軌跡—路網(wǎng)匹配方法可根據(jù)匹配過(guò)程中采樣點(diǎn)的時(shí)空分布分為全局匹配和局部/增量匹配2類[2,9]。

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

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

　　車輛在地理空間運(yùn)動(dòng)產(chǎn)生的時(shí)空位置記錄，是一個(gè)動(dòng)態(tài)的地理位置采樣過(guò)程的結(jié)果，而粒子濾波(ParticleFilter,PF)作為一種序貫蒙特卡羅(SequentialMonteCarlo)方法，具有一定的時(shí)空模型模擬能力[20,21]，能夠根據(jù)上一時(shí)刻觀測(cè)值、當(dāng)前時(shí)刻模型模擬值與觀測(cè)值，通過(guò)粒子重采樣和權(quán)重更新優(yōu)化當(dāng)前模型模擬結(jié)果，可處理軌跡中的噪聲并減少軌跡—路網(wǎng)匹配過(guò)程中對(duì)已匹配結(jié)果準(zhǔn)確性的依賴，因此可利用PF方法對(duì)行車軌跡中車輛的時(shí)空運(yùn)動(dòng)過(guò)程進(jìn)行模擬，建立行車軌跡—路網(wǎng)的匹配關(guān)系。基于此，本文利用PF原理對(duì)行車軌跡中車輛的時(shí)空運(yùn)動(dòng)過(guò)程進(jìn)行建模，在拓?fù)潢P(guān)聯(lián)的道路弧段中生成粒子，構(gòu)建行車軌跡與道路網(wǎng)絡(luò)的匹配方法，并通過(guò)行車軌跡為研究對(duì)象，對(duì)方法的可靠性和準(zhǔn)確性進(jìn)行實(shí)驗(yàn)和分析。

　　2、粒子濾波與軌跡—路網(wǎng)匹配

　　2.1粒子生成

　　本文以行車軌跡采樣點(diǎn)鄰近的道路節(jié)點(diǎn)拓?fù)潢P(guān)聯(lián)的道路弧段為粒子生成區(qū)間，所有粒子均位于相鄰道路弧段，是一個(gè)沿道路線性度量空間分布的二維空間采樣點(diǎn)，其中行車軌跡中采樣點(diǎn)和相鄰道路弧段的關(guān)系表示如下：

　　(1)假定沿著行車軌跡S中車輛運(yùn)動(dòng)方向，與軌跡采樣點(diǎn)Si(xi,yi)相鄰近j個(gè)道路節(jié)點(diǎn)N{N1,N2,,Nj};

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

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

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

　　圖1粒子的生成

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

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

　　(3)根據(jù)隨機(jī)長(zhǎng)度比例r，計(jì)算粒子坐標(biāo)qkLm(r)，如式(3)所示。

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

　　2.2行車軌跡—路網(wǎng)匹配

　　在傳統(tǒng)的PF方法中，粒子隨機(jī)分布在研究區(qū)域中，并隨著行車軌跡采樣點(diǎn)的狀態(tài)變化不斷更新，從而更新采樣點(diǎn)的位置坐標(biāo)。而在本文行車軌跡—路網(wǎng)匹配方法的計(jì)算過(guò)程如下：

　　(1)從車輛運(yùn)動(dòng)產(chǎn)生的行車軌跡采樣點(diǎn)出發(fā)，搜索鄰近的道路節(jié)點(diǎn)，根據(jù)道路節(jié)點(diǎn)拓?fù)溧徑拥牡缆坊《纬跏蓟a(chǎn)生隨機(jī)粒子;

　　(2)通過(guò)行車軌跡中車輛運(yùn)動(dòng)模型更新粒子在道路弧段中的位置，利用粒子與下一時(shí)刻軌跡采樣點(diǎn)的地理位置計(jì)算粒子權(quán)重，并統(tǒng)計(jì)每條拓?fù)溧徑拥缆坊《蔚牧Ｗ訖?quán)重，進(jìn)行粒子重采樣，根據(jù)行車軌跡采樣時(shí)刻迭代更新軌跡采樣位置與粒子狀態(tài);

　　(3)當(dāng)搜索到新的鄰近道路節(jié)點(diǎn)時(shí)，計(jì)算各條道路弧段的累計(jì)粒子權(quán)重，計(jì)算累計(jì)粒子權(quán)重最大的道路弧段作為匹配道路弧段;

　　(4)以道路節(jié)點(diǎn)為匹配關(guān)系分界線，更新行車軌跡與路網(wǎng)的匹配關(guān)系，返回步驟(1)并根據(jù)新的道路節(jié)點(diǎn)及拓?fù)溧徑拥缆坊《渭献詣?dòng)生成隨機(jī)粒子采樣，不斷迭代直至車輛完全停止運(yùn)動(dòng)。行車軌跡—路網(wǎng)匹配算法的流程如圖2所示。

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

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

　　式中：St為軌跡采樣點(diǎn)在tt時(shí)刻坐標(biāo);θ為車輛的運(yùn)動(dòng)方向(與正北方向順時(shí)針轉(zhuǎn)角);v為運(yùn)動(dòng)速度;;S?t+1為tt+1時(shí)刻軌跡采樣點(diǎn)的位置預(yù)測(cè)。粒子生成與更新算法過(guò)程如下：

　　(1)搜索與行車軌跡中采樣點(diǎn)Si距離小于d的道路網(wǎng)節(jié)點(diǎn)NSi，并根據(jù)NSi查找道路網(wǎng)絡(luò)中拓?fù)溧徑拥牡缆坊《蜭Si，在LSi上初始化產(chǎn)生o個(gè)隨機(jī)粒子。

　　(1)如果是首次初始化粒子，則準(zhǔn)備開(kāi)始PF過(guò)程模擬;

　　(2)否則，統(tǒng)計(jì)每條鄰接道路弧段LSi的累計(jì)粒子權(quán)重，將權(quán)重最大的道路弧段作為對(duì)應(yīng)行車軌跡片段的匹配道路弧段。

　　(2)根據(jù)軌跡中車輛運(yùn)動(dòng)方向，根據(jù)采樣時(shí)間先后順序從行車軌跡中順序選取采樣點(diǎn)Si;

　　(3)根據(jù)PF原理和軌跡中車輛運(yùn)動(dòng)模型，在鄰接道路弧段LSi中更新粒子狀態(tài)，其中，粒子在軌跡中的運(yùn)動(dòng)存在標(biāo)準(zhǔn)差ς的隨機(jī)噪聲;

　　(4)計(jì)算粒子與行車軌跡采樣點(diǎn)的距離D，根據(jù)式(6)計(jì)算粒子權(quán)重w

　　(5)歸一化權(quán)重，并對(duì)粒子重采樣;

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

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

　　3、行車軌跡—路網(wǎng)匹配實(shí)驗(yàn)結(jié)果與分析

　　3.1實(shí)驗(yàn)數(shù)據(jù)

　　本文采用行車軌跡為實(shí)驗(yàn)對(duì)象，由兩條長(zhǎng)時(shí)間序列采集的行車軌跡組成。其中，行車軌跡的長(zhǎng)度約為102km，軌跡采樣點(diǎn)共計(jì)1838個(gè);水平采樣精度為10m，采樣時(shí)間間隔為10s。具體情況如表1所示。

　　表1車行軌跡采樣信息

　　研究區(qū)域中道路數(shù)據(jù)和輔助遙感影像來(lái)自于該區(qū)域的基礎(chǔ)地理數(shù)據(jù)庫(kù)，研究區(qū)域面積約為55km2，道路中路網(wǎng)分布比較復(fù)雜，在部分區(qū)域路網(wǎng)密度較高。數(shù)據(jù)空間分布如圖3所示。

　　3.2實(shí)驗(yàn)結(jié)果與分析

　　3.2.1數(shù)據(jù)預(yù)處理與參數(shù)選擇

　　行車軌跡—路網(wǎng)匹配過(guò)程中，首先需要對(duì)數(shù)據(jù)進(jìn)行拓?fù)錂z查，根據(jù)道路數(shù)據(jù)構(gòu)建具有弧段和節(jié)點(diǎn)結(jié)構(gòu)的道路網(wǎng)絡(luò)，同時(shí)對(duì)行車軌跡進(jìn)行離群值粗差剔除等預(yù)處理，然后根據(jù)PF原理實(shí)現(xiàn)行車軌跡與路網(wǎng)的匹配。其中，相關(guān)參數(shù)的選取方法如下：

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

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

　　(3)以道路網(wǎng)絡(luò)中道路弧段長(zhǎng)度的平均值作為高斯概率密度函數(shù)標(biāo)準(zhǔn)差σ的參考值，在本文實(shí)驗(yàn)中σ的值為1000m;

　　(4)根據(jù)道路網(wǎng)絡(luò)中每個(gè)道路節(jié)點(diǎn)的復(fù)雜程度作為隨機(jī)粒子個(gè)數(shù)o的參考依據(jù)，在道路節(jié)點(diǎn)復(fù)雜程度較高的道路數(shù)據(jù)中設(shè)置較大的粒子數(shù)目，反之亦然。在本文實(shí)驗(yàn)中與道路節(jié)點(diǎn)鄰接的道路弧段數(shù)目以4條為主，因此可設(shè)置隨機(jī)粒子個(gè)數(shù)o為100。

　　3.2.2粒子的隨機(jī)生成

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

　　圖3研究區(qū)域中車行軌跡與道路網(wǎng)絡(luò)空間分布

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

　　注：綠色數(shù)字為各個(gè)頂點(diǎn)組成的道路子弧段累計(jì)長(zhǎng)度比例，紅色數(shù)字為隨機(jī)粒子組成的道路子弧段累計(jì)長(zhǎng)度比例。

　　3.2.3粒子移動(dòng)與路網(wǎng)匹配

　　根據(jù)鄰近道路節(jié)點(diǎn)拓?fù)潢P(guān)聯(lián)的道路弧段生成粒子，然后利用PF原理對(duì)行車軌跡采樣點(diǎn)和粒子每個(gè)時(shí)刻的狀態(tài)進(jìn)行更新，最后根據(jù)累計(jì)粒子權(quán)重匹配道路弧段，過(guò)程如圖5所示。

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

　　圖5軌跡采樣點(diǎn)不同時(shí)刻粒子位置的變化

　　3.2.4行車軌跡—路網(wǎng)匹配

　　為了對(duì)本文方法路網(wǎng)匹配能力進(jìn)行實(shí)驗(yàn)對(duì)比，首先，基于距離判別法將軌跡點(diǎn)與鄰近道路網(wǎng)絡(luò)弧段進(jìn)行距離投影，根據(jù)軌跡點(diǎn)與鄰近道路弧段的距離計(jì)算其匹配關(guān)系，對(duì)行車軌跡1和行車軌跡2進(jìn)行實(shí)驗(yàn)，結(jié)果如圖6所示。

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

　　利用本文基于PF的行車軌跡-路網(wǎng)匹配方法對(duì)研究區(qū)域中行車軌跡和道路網(wǎng)絡(luò)進(jìn)行匹配，實(shí)驗(yàn)結(jié)果如圖7。圖中黑色實(shí)線為與行車軌跡正確匹配的道路弧段，灰色實(shí)線為與行車軌跡錯(cuò)誤匹配的道路弧段，灰色虛線為與行車軌跡未匹配的道路弧段。由圖可見(jiàn)，行車軌跡-路網(wǎng)匹配結(jié)果覆蓋了大部分區(qū)域，而在局部路網(wǎng)密度較高的復(fù)雜通行區(qū)域存在一定的錯(cuò)誤匹配結(jié)果，本文方法能夠從行車軌跡中計(jì)算出軌跡-路網(wǎng)匹配關(guān)系。

　　本文以用“正確匹配長(zhǎng)度/軌跡總長(zhǎng)度”計(jì)算行車軌跡-路網(wǎng)匹配結(jié)果的正確率。對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)，分別從匹配長(zhǎng)度、正確匹配、錯(cuò)誤匹配、未匹配進(jìn)行統(tǒng)計(jì)，結(jié)果如表2所示。

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

　　圖6基于距離判別法的車行軌跡—路網(wǎng)匹配結(jié)果

　　圖7本文基于PF方法的車行軌跡-路網(wǎng)匹配結(jié)果

　　表2車行軌跡-路網(wǎng)匹配結(jié)果統(tǒng)計(jì)

　　通過(guò)實(shí)驗(yàn)結(jié)果可見(jiàn)，本文方法基于PF原理構(gòu)建行車軌跡-路網(wǎng)匹配方法，使得路網(wǎng)匹配方法在計(jì)算過(guò)程中不依賴于全局或局部/增量式匹配過(guò)程的尋優(yōu)條件，使得計(jì)算過(guò)程具有相對(duì)獨(dú)立性，具有較高的匹配準(zhǔn)確率并且行車軌跡-路網(wǎng)匹配結(jié)果具有路徑連續(xù)性，與車輛實(shí)際運(yùn)動(dòng)情況較為一致。

　　4、結(jié)論

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

　　參考文獻(xiàn)：

　　[1]吳華意,黃蕊,游蘭,等.出租車軌跡數(shù)據(jù)挖掘進(jìn)展[J].測(cè)繪學(xué)報(bào),2019,48(11):1341-1356.

　　[2]高文超,李國(guó)良,塔娜.路網(wǎng)匹配算法綜述[J].軟件學(xué)報(bào),2018,29(2):225-250.

　　[5]高強(qiáng),張鳳荔,王瑞錦,等.軌跡大數(shù)據(jù):數(shù)據(jù)處理關(guān)鍵技術(shù)研究綜述[J].軟件學(xué)報(bào),2017,28(4):959-992.

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

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

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

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

　　[14]李清泉,胡波,樂(lè)陽(yáng).一種基于約束的最短路徑低頻浮動(dòng)車數(shù)據(jù)地圖匹配算法[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版,2013,38(7):805-808,885.

　　[15]朱遞,劉瑜.一種路網(wǎng)拓?fù)浼s束下的增量型地圖匹配算法[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版,2017,42(1):77-83.