GNSS高采樣率路徑增量地圖匹配方法

王浩巖，劉遠(yuǎn)剛，李少華，梁 博，何宗宜,2

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

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

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

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

1 基本概念與總體思路

1.1 道路匹配基本概念

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

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

1.2 匹配算法總體設(shè)計(jì)

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

圖1 算法流程

2 復(fù)雜道路網(wǎng)絡(luò)的組合過(guò)濾

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

圖2 過(guò)濾結(jié)果示例

2.1 距離約束過(guò)濾

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

2.2 道路連通性過(guò)濾

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

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

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

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

圖3 方向連通性

2.3 方向一致性過(guò)濾

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

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

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

(1)

式中，α為當(dāng)前向量的方位角；(x1,y1)、(x2,y2)分別為向量的首尾點(diǎn)坐標(biāo)。

圖4 方向一致性過(guò)濾

2.4 單點(diǎn)連通路段“剪枝”

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

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

3.1 相似度評(píng)價(jià)

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

3.1.1 距離因子

在路口點(diǎn)的匹配中，需要將連續(xù)的軌跡點(diǎn)匹配到路口點(diǎn)相關(guān)的前后兩個(gè)路段上，距離評(píng)價(jià)因子為上述兩組點(diǎn)之間的距離的映射。Hausdorff距離是描述兩組點(diǎn)之間相似程度的一種量度，本文采用Hausdorff距離計(jì)算軌跡點(diǎn)與軌跡在匹配路段上的投影點(diǎn)之間的距離。其定義[18]為：假設(shè)有兩組集合A={a1,a2,…,ap},B={b1,b2,…,bq}，這兩組點(diǎn)之間的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)；‖*‖為點(diǎn)集A與點(diǎn)集B之間的距離范數(shù)。

3.1.2 彎曲度因子

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

(3)

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

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

(4)

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

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

(5)

式中，在計(jì)算各點(diǎn)曲率時(shí)，以正北方向作為基準(zhǔn)，采用方位角代替原公式中的傾角，式(1)為方位角的計(jì)算方式。

3.1.3 相似度計(jì)算

路口點(diǎn)處的相似度為上述兩個(gè)因子的綜合，表達(dá)式為

(6)

式中，Hdif為軌跡與對(duì)應(yīng)路徑之間的Hausdorff距離的差值的絕對(duì)值；Kdif為軌跡與對(duì)應(yīng)道路的曲率積分差的絕對(duì)值，相似度的值域?yàn)?0,1]，值越大時(shí)則當(dāng)前路徑與軌跡越為相似。

3.2 增量匹配

3.2.1 增量匹配過(guò)程

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

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

算法1：增量匹配過(guò)程

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

輸出：匹配路徑P

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

P.append(startSection)

獲取起始路段終點(diǎn)estart.lastPoint

vjudge←estart.lastPoint #初始化當(dāng)前判斷點(diǎn)

ejudge←estart#初始化當(dāng)前判斷路段

while True:

獲取與當(dāng)前判斷點(diǎn)連接的路段列表E

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

break

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

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

P.append(ebackward)

ejudge←ebackward

vjudge←ebackward.lastPoint

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

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

P.append(ebackward)

ejudge←ebackward

vjudge←ebackward.lastPoint

3.2.2 首尾路段的確定

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

圖5 首尾路段的選擇

算法2：起始路段的確定

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

輸出：起始路段startSection

i←0

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

while True:

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

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

i←i+1

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

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

break

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

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

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

startSection←esimmax

break

3.2.3 路口點(diǎn)處的匹配

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

圖6 路口點(diǎn)處匹配過(guò)程

圖7 候選點(diǎn)位置判斷

算法3：路口點(diǎn)處匹配

輸入：軌跡Trcak，當(dāng)前判斷點(diǎn)vjudge，當(dāng)前判斷路段ejudge，與vjudge連接的路段列表E

輸出：匹配路段ematch

獲取vjudge的候選點(diǎn)集I#此時(shí)vjudge為路口點(diǎn)

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

foreinE:

ife.equals(ejudge):

pass

else:

Iproject←[] #初始化投影點(diǎn)集

計(jì)算Ifailed中軌跡點(diǎn)在ejudge上的投影點(diǎn)，并添加至Iproject

Iproject.append(vjudge)

計(jì)算Ipassed中軌跡點(diǎn)在e上的投影點(diǎn)，并添加至Iproject

計(jì)算I與Iproject之間的相似度

獲取相似度最高的路段esimmax

ematch←esimmax

4 試驗(yàn)與討論

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

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

圖8 測(cè)試軌跡

表1 測(cè)試軌跡信息表

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

試驗(yàn)主機(jī)環(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 試驗(yàn)結(jié)果及對(duì)比分析

為更好地驗(yàn)證算法的效果，將本文算法與曲率積分約束的地圖匹配算法(以下簡(jiǎn)稱為“曲率積分算法”)[21]及HMM算法[22]進(jìn)行對(duì)比。主要從匹配結(jié)果的精度及效率角度對(duì)算法進(jìn)行測(cè)試。為評(píng)價(jià)算法匹配精度，本文借鑒文獻(xiàn)[34]中評(píng)價(jià)方法，將評(píng)價(jià)指標(biāo)設(shè)為：路徑不匹配分?jǐn)?shù)(route mismatch fraction，RMF)，準(zhǔn)確率(Precision)，召回率(Recall)，具體定義如式(7)—式(9)所示

(7)

(8)

(9)

式中，L+為算法計(jì)算結(jié)果中與真實(shí)路徑相比錯(cuò)誤增加的長(zhǎng)度；L-為算法計(jì)算結(jié)果中與真實(shí)路徑相比錯(cuò)誤減少的長(zhǎng)度；Lmatched為算法計(jì)算結(jié)果中正確匹配路徑的總長(zhǎng)度；Linferred為算法計(jì)算結(jié)果的總長(zhǎng)度；Lreal為真實(shí)路徑的總長(zhǎng)度。

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

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

圖9 地圖匹配精度評(píng)價(jià)指標(biāo)

圖10 軌跡匹配結(jié)果

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

圖11 算法效率

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

5 結(jié) 論

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

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