復(fù)雜路網(wǎng)改進(jìn)的投影地圖匹配算法研究

付小雪，羅贊文，劉振東

(1.上海健康醫(yī)學(xué)院 信息管理中心，上海 201318；2.上海交通運(yùn)輸研究中心大數(shù)據(jù)研究院，上海 200031)

有關(guān)智慧交通的應(yīng)用大多基于車輛軌跡，其核心是對(duì)道路上車輛的GPS軌跡數(shù)據(jù)進(jìn)行精確定位，即地圖匹配[1]。典型的GPS軌跡是一系列順序的軌跡點(diǎn)，每個(gè)GPS點(diǎn)由緯度、經(jīng)度和時(shí)間戳信息組成。由于GPS自身的局限性，GPS數(shù)據(jù)的采樣和計(jì)算過程以及定位數(shù)據(jù)的接收和返回的過程都有可能出現(xiàn)誤差，從而導(dǎo)致GPS數(shù)據(jù)不準(zhǔn)確[2]。因此，需要對(duì)原始數(shù)據(jù)進(jìn)行處理后在路網(wǎng)上使用，也就是地圖匹配。地圖匹配算法的輸入應(yīng)該是GPS點(diǎn)標(biāo)記的位置信息、道路網(wǎng)的鄰接信息和車輛的其他行駛信息。最關(guān)鍵問題是如何通過綜合各方面信息，快速準(zhǔn)確地推斷出車輛的行駛路線。地圖匹配算法主要包括：基于幾何的地圖匹配算法[3]、拓?fù)涞貓D匹配算法[4-5]、概率地圖匹配算法[6]和其他地圖匹配算法(比如機(jī)器學(xué)習(xí)匹配算法、卡爾曼濾波匹配算法、模糊邏輯模型匹配算法和隱馬爾科夫模型(HMM)的地圖匹配算法等)。這些先進(jìn)的匹配算法雖然準(zhǔn)確率較高，但是對(duì)低頻采樣數(shù)據(jù)準(zhǔn)確性明顯下降。其中基于隱馬爾科夫模型(HMM)的地圖匹配算法雖然對(duì)處理離線的高頻采樣的行駛數(shù)據(jù)具有較高的匹配準(zhǔn)確率，但是在線路網(wǎng)匹配準(zhǔn)確率不高。在線地圖匹配算法中最常用的是基于時(shí)間窗口的地圖匹配算法[7], 由于推斷的延遲，影響了立即更新輸出。

近期有學(xué)者針對(duì)在線地圖匹配算法進(jìn)行了相關(guān)研究:Mohamed等[8]提出了基于隱馬爾科夫模型的在線地圖匹配算法(Novel incremental hidden markov model (HMM)-based map matching algorithm, OHMM),該算法利用機(jī)器學(xué)習(xí)方法進(jìn)行概率轉(zhuǎn)移矩陣的計(jì)算，同時(shí)考慮了道路的限速和路寬信息，進(jìn)行觀測(cè)概率矩陣的計(jì)算，地圖匹配的過程利用了維特比算法；Hou等[9]提出了INC-RB算法，該算法是基于增量推理和回溯策略的地圖匹配算法；鄭詩(shī)晨等[10]提出的基于粒子濾波的在線行車軌跡路網(wǎng)匹配方法基于粒子濾波(Particle filter，PF)理論進(jìn)行了行車軌跡與道路網(wǎng)絡(luò)之間的匹配，準(zhǔn)確率只有85%，并且當(dāng)研究區(qū)域較大時(shí)，實(shí)時(shí)運(yùn)算能力較差，效率較低；陳良健等[11]提出了一種基于GRU模型的在線路網(wǎng)匹配算法,該算法雖然不需要通過對(duì)路網(wǎng)建立索引和搜索多條候選路徑，地圖匹配過程可以加快，但是沒有考慮速度和方向信息，算法的匹配準(zhǔn)確率較低，會(huì)出現(xiàn)匹配錯(cuò)誤的情況；黃振鋒等[12]提出了一種改進(jìn)的曲線擬合算法，該算法考慮了移動(dòng)對(duì)象的速度、道路的限速和方向等因素，具有較高的匹配準(zhǔn)確率和計(jì)算效率，然而在城市復(fù)雜路網(wǎng)的真實(shí)情景下，算法的容錯(cuò)性、穩(wěn)定性和效率均不高；滕志軍等[13]提出了基于D-S證據(jù)理論的自適應(yīng)地圖匹配算法，該算法雖然改進(jìn)了傳統(tǒng)D-S證據(jù)理論地圖匹配算法準(zhǔn)確率低的問題，但是當(dāng)候選區(qū)域存在多條候選路段時(shí)，算法的效率和準(zhǔn)確率均會(huì)受到影響，算法性能降低?，F(xiàn)有的地圖匹配算法雖然匹配準(zhǔn)確率較高，但是在城市復(fù)雜路網(wǎng)的實(shí)際應(yīng)用場(chǎng)景中，或者當(dāng)軌跡數(shù)據(jù)急劇增加時(shí)，算法效率往往較低，而對(duì)于算法效率較高的匹配算法，由于沒有考慮車輛角度、速度和方向角等因素，算法的匹配準(zhǔn)確率會(huì)受到一定影響。因此，筆者提出了一種改進(jìn)的自適應(yīng)投影地圖匹配算法，將城市復(fù)雜路網(wǎng)中的道路分為平行道路、交叉道路、立交橋道路和組合道路4種路段類型，對(duì)不同的道路類型進(jìn)行反復(fù)實(shí)驗(yàn)測(cè)試，確定權(quán)重系數(shù)，即使在復(fù)雜的實(shí)際應(yīng)用場(chǎng)景下以及軌跡數(shù)據(jù)量急劇增加時(shí)，依然能夠保持較高的地圖匹配準(zhǔn)確率和匹配效率，實(shí)現(xiàn)了城市復(fù)雜路網(wǎng)下精準(zhǔn)和快速的地圖匹配。

1 算法設(shè)計(jì)

1.1 建立網(wǎng)格索引

Open street map(OSM)地圖是一種開放街道地圖，所有地圖數(shù)據(jù)都是由全球志愿者提供的，均可直接從官網(wǎng)下載使用。OSM地圖數(shù)據(jù)主要有Node(節(jié)點(diǎn))、Way(道路)和Relation(關(guān)系) 3種類型。為了提高單點(diǎn)定位的匹配速度，筆者采用Hash Map網(wǎng)格索引算法。在對(duì)地圖進(jìn)行網(wǎng)格劃分之前，首先需要對(duì)城市OSM地圖的完整度進(jìn)行分析校驗(yàn)，將OSM地圖上缺失的道路增加到地圖數(shù)據(jù)庫(kù)中。傳統(tǒng)四叉樹索引算法的缺點(diǎn)是對(duì)象的空間分布越不均勻，構(gòu)建的四叉樹越不平衡，從而引起空間查詢的效率急劇低下，采用Hash網(wǎng)格索引算法可以有效地避免四叉樹嚴(yán)重不平衡的情況，通過對(duì)地圖進(jìn)行2次網(wǎng)格劃分(圖1)，更加準(zhǔn)確地找到待匹配點(diǎn)的所屬匹配范圍，減少大量無(wú)效的匹配計(jì)算，大大提升了匹配的效率和準(zhǔn)確率。由圖1(b)可以看出：待匹配點(diǎn)P的匹配范圍為1，3，4區(qū)，大大縮小了待匹配點(diǎn)P的所屬區(qū)域，提高了匹配準(zhǔn)確率。在對(duì)地圖進(jìn)行Hash網(wǎng)格劃分時(shí)，網(wǎng)格的邊長(zhǎng)設(shè)置為100 m，網(wǎng)格的大小可以根據(jù)實(shí)際情況進(jìn)行適當(dāng)調(diào)整。

圖1 基于Hash Map算法的網(wǎng)格劃分示意圖Fig.1 Meshing diagram of the Hash Map algorithm

1.2 候選道路集合

對(duì)地圖進(jìn)行2次網(wǎng)格劃分之后，進(jìn)一步確定待匹配點(diǎn)所在實(shí)際道路的大概區(qū)域，一般使用誤差橢圓的方式確定此區(qū)域，其中誤差橢圓的計(jì)算式分別為

(1)

(2)

(3)

式中：a為橢圓的長(zhǎng)半軸；b為橢圓的短半軸；σX，σY，σXY分別為車輛經(jīng)緯度的標(biāo)準(zhǔn)差及協(xié)方差；σ0=1；φ為橢圓長(zhǎng)半軸與正北方向的夾角。

由式(1～3)可以看出：誤差橢圓的計(jì)算方式比較復(fù)雜，故通過誤差圓[14-15]的方式進(jìn)行計(jì)算可降低計(jì)算工作量,誤差圓的計(jì)算式為

(4)

通過誤差圓的計(jì)算，可以確定候選路段集合D={R1,R2,…,Ri,…,Rn|i=1,2,…,n}。

1.3 構(gòu)造基本概率函數(shù)

1.3.1 投影距離概率計(jì)算

車輛定位點(diǎn)到道路的投影距離是地圖匹配中一個(gè)非常重要的指標(biāo)[16-19]，其投影示意圖如圖2所示。定位點(diǎn)到附近某條道路的投影距離越小，真實(shí)位置就越有可能在該條道路上[20-22]。

圖2 定位點(diǎn)到道路的投影示意圖Fig.2 Projection diagram from anchor point to road

投影距離的計(jì)算方式如下：

1) 定位點(diǎn)S1到路段PQ的最短距離為d1，其計(jì)算式為

(5)

2) 定位點(diǎn)S2到路段PQ的投影在路段PQ的延長(zhǎng)線上，S2到路段PQ的最短距離為d2，其計(jì)算式為

(6)

假設(shè)從誤差圓中獲取的候選道路集合為D={R1,R2,…,Ri,…,Rn|i=1,2,…,n}，那么距離的概率p1(Ri)計(jì)算式為

(7)

式中λ為誤差圓半徑R與定位點(diǎn)到路段的投影距離d之比。

1.3.2 車輛道路夾角概率計(jì)算

在車輛位于交叉路口或者車輛周圍有多條候選道路的情況下，車輛方向是對(duì)車輛進(jìn)行準(zhǔn)確定位的一個(gè)重要標(biāo)準(zhǔn)。假設(shè)車輛方向與道路方向的夾角為θi，其示意圖如圖3所示。

圖3 車輛與道路的夾角示意圖Fig.3 Diagram of the angle between road and vehicle

假設(shè)Q點(diǎn)的坐標(biāo)為(x，y)，O為坐標(biāo)原點(diǎn)(0，0)，那么道路上的路段OQ與北方方向夾角γi的計(jì)算式為

(8)

如果x=0，y<0，那么γi=π；如果x=0，y>0，那么γi=0，由此可以推導(dǎo)出θi的計(jì)算式為

(9)

假設(shè)從誤差圓中獲取的候選道路集合為D={R1，R2，…,Ri，…，Rn|i=1，2，…，n}，那么方向角概率p2(Ri)的計(jì)算式為

(10)

1.3.3 車輛高程概率計(jì)算

城市復(fù)雜道路還包括高架路段，城市高架路錯(cuò)綜復(fù)雜[23-26]，尤其是分叉口比較多的路段是地圖匹配中最為復(fù)雜的情況。除了投影距離、方向和車速等指標(biāo)外，還需要考慮高程信息[27-28]。

假設(shè)待匹配點(diǎn)的高程為h，路網(wǎng)的高程為Hi，那么高程概率p3(Ri)的計(jì)算式為

(11)

1.3.4 計(jì)算候選路段概率

分別計(jì)算了投影距離、方向和高程的概率后，對(duì)于非高架路段，采用距離與方向結(jié)合的方式計(jì)算候選路段的綜合概率。針對(duì)高架路段，采用距離、方向和高程結(jié)合的方式計(jì)算路段的綜合概率。對(duì)于非高架路，候選路段的綜合概率計(jì)算式為

p0=μ1p1p2+μ2p1p2+μ3p1p2+μ4p1p2

(12)

式中每一項(xiàng)依次為距離和方向都能匹配到道路Ri的概率。

對(duì)于高架路，加入了高程信息，候選路段綜合概率的計(jì)算式為

p0=μ1p1p2+μ2p1p2+μ3p1p2+
μ4p1p2+μ5p1p3

(13)

式中最后一項(xiàng)為根據(jù)高程匹配到候選路段Ri的概率。

1.4 算法流程

步驟1利用Hash Map網(wǎng)格索引算法對(duì)地圖進(jìn)行網(wǎng)格劃分。

步驟2采用誤差圓方法確定候選區(qū)域。

步驟3針對(duì)不同道路類型，根據(jù)投影距離、方向和高程等信息確定概率計(jì)算公式。

步驟4根據(jù)不同道路類型，自適應(yīng)確定權(quán)重參數(shù)。

步驟5根據(jù)融合結(jié)果選取概率最大的路段為匹配路段。

改進(jìn)的基于投影的地圖匹配算法流程如圖4所示。

圖4 改進(jìn)的基于投影的地圖匹配算法流程 Fig.4 Flowchart of improved matching algorithm basedon projection

2 算法實(shí)驗(yàn)驗(yàn)證及評(píng)價(jià)

2.1 實(shí)驗(yàn)驗(yàn)證

通過2 000多輛常州市出租車采集的實(shí)時(shí)定位信息對(duì)改進(jìn)的自適應(yīng)投影匹配算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，每輛車的位置、方向和速度信息均通過車輛車載終端的定位設(shè)備獲取，采樣時(shí)間間隔為10 s，圖5為筆者算法在一塊區(qū)域的匹配結(jié)果。由圖5可以看出：車輛的每一個(gè)定位點(diǎn)都能很好地匹配到道路上，在交叉路口也能有極高的匹配準(zhǔn)確率。

圖5 車輛軌跡數(shù)據(jù)匹配效果Fig.5 Road matching of vehicles trajectory

除了在一塊區(qū)域?qū)λ惴ǖ钠ヅ湫ЧM(jìn)行實(shí)驗(yàn)驗(yàn)證之外，還對(duì)同一輛車在一段道路上的匹配效果進(jìn)行了實(shí)驗(yàn)驗(yàn)證，匹配結(jié)果如圖6所示。由圖6可知：車輛的原始定位信息基本沒有定位在道路上，經(jīng)過匹配算法進(jìn)行匹配之后，車輛的行駛軌跡基本匹配在相應(yīng)的道路上。當(dāng)進(jìn)行大批量浮動(dòng)車數(shù)據(jù)的匹配計(jì)算時(shí)，依然有很好的匹配效果，其匹配效果如圖7所示。

圖6 同一浮動(dòng)車的道路匹配效果Fig.6 Road matching of the same floating vehicle

圖7 大規(guī)模軌跡數(shù)據(jù)匹配效果Fig.7 Diagram of matching thousands of data points

2.2 評(píng) 價(jià)

將改進(jìn)的自適應(yīng)投影地圖匹配算法分別與最新提出的基于GRU模型的路網(wǎng)匹配算法[8-11]、復(fù)雜環(huán)境下精確實(shí)時(shí)地圖匹配中提出的OHMM 算法和在《基于低頻采樣GPS數(shù)據(jù)還原行駛路線的快速在線地圖匹配算法研究》一文中提出的INC-RB算法進(jìn)行匹配準(zhǔn)確率和單點(diǎn)匹配時(shí)間兩個(gè)方面的比較。將城市復(fù)雜道路劃分為平行道路、交叉道路、立交橋道路和組合道路4種類型。上述4種算法的匹配準(zhǔn)確率對(duì)比如圖8所示，在平行路段，改進(jìn)的投影地圖匹配算法和INC-RB算法匹配準(zhǔn)確率最高，原因在于待匹配點(diǎn)到道路的投影距離在平行道路的情況下是最重要的參考指標(biāo)，待匹配點(diǎn)到平行道路中某條道路的投影距離越近，越有可能位于該道路。在交叉路段的情況下，筆者算法的匹配準(zhǔn)確率約為97%，匹配準(zhǔn)確率最高，在交叉路段的情形下，由于改進(jìn)的自適應(yīng)投影匹配算法同時(shí)考慮投影距離和方向角2個(gè)變量進(jìn)行候選道路概率的計(jì)算，車輛在交叉路口的定位不會(huì)只根據(jù)投影距離最近的原則進(jìn)行路網(wǎng)匹配。而OHMM算法是通過計(jì)算實(shí)際觀測(cè)概率和計(jì)算轉(zhuǎn)移概率相結(jié)合的方式計(jì)算候選道路的最終匹配概率，在復(fù)雜交叉路口的實(shí)際應(yīng)用場(chǎng)景下，準(zhǔn)確率受到一定程度的影響。在組合路段下，匹配算法準(zhǔn)確率最高，改進(jìn)的自適應(yīng)投影算法主要是針對(duì)不同路段得出的一種計(jì)算方法，根據(jù)不同的道路類型，選擇不同的權(quán)重系數(shù)和變量計(jì)算候選道路的概率，最適用于組合路段的情況，故改進(jìn)的自適應(yīng)投影匹配算法在組合路段情形下匹配準(zhǔn)確率最高。

圖8 4種算法的匹配準(zhǔn)確率對(duì)比Fig.8 Comparison of the matching accuracy ofthe four algorithms

對(duì)匹配算法的評(píng)價(jià)，除了計(jì)算4種不同算法的匹配準(zhǔn)確率之外，還分別計(jì)算了4種算法的單點(diǎn)匹配時(shí)間。單點(diǎn)匹配時(shí)間是指將待匹配點(diǎn)匹配到確定路段所用的平均時(shí)間，圖9為4種算法分別在2，3，4，5條候選道路下的匹配時(shí)間。由圖9可以得出：當(dāng)候選道路為2條時(shí)，筆者所提出的算法匹配時(shí)間為3.8 ms；當(dāng)候選道路為5條時(shí)，匹配時(shí)間約為5.5 ms；隨著候選道路的增加，4種算法的單點(diǎn)匹配時(shí)間雖然均有所增加，但是筆者算法的匹配時(shí)間均低于其他3種算法，其單點(diǎn)匹配時(shí)間大約可以降低1.5 ms，具有較好的實(shí)時(shí)性。

圖9 4種不同算法對(duì)應(yīng)的單點(diǎn)匹配時(shí)間Fig.9 Single point matching time of the four different algorithms

3 結(jié) 論

針對(duì)城市復(fù)雜道路的不同類型，提出一種改進(jìn)的自適應(yīng)投影地圖匹配算法，無(wú)論在平行路段還是在交叉路段、高架路段以及組合路段，該算法都有較高的地圖匹配準(zhǔn)確率。對(duì)于平行路段，投影距離最近原則可以實(shí)現(xiàn)大部分的地圖匹配，在十字路口或者交叉路段，引入了方向角參數(shù)，更加精確地定位車輛所在的實(shí)際道路，不會(huì)因?yàn)閮H僅根據(jù)投影距離將車輛定位在錯(cuò)誤的道路上；在高架路段，結(jié)合了方向角和高程，確定車輛實(shí)際所在位置，解決了普通地圖匹配算法無(wú)法實(shí)現(xiàn)的高架道路定位的問題。在車載終端設(shè)備定位信號(hào)不穩(wěn)定和不連續(xù)時(shí)，系統(tǒng)接收到的車輛定位信息存在一定的誤差，導(dǎo)致最后的地圖匹配結(jié)果產(chǎn)生誤差，后續(xù)可以通過GPS漂移點(diǎn)檢測(cè)算法將不準(zhǔn)確的定位點(diǎn)去除，進(jìn)一步提高地圖匹配的準(zhǔn)確率。采用Hash Map網(wǎng)格索引對(duì)地圖進(jìn)行了網(wǎng)格劃分，提高了初始匹配效率，利用誤差圓方法確定了誤差區(qū)域，縮小了候選區(qū)域，大幅減少了匹配時(shí)間。根據(jù)不同的道路類型，構(gòu)造了不同的綜合概率計(jì)算方法，并且自適應(yīng)調(diào)整權(quán)重參數(shù)，以常州市出租車運(yùn)行數(shù)據(jù)進(jìn)行實(shí)驗(yàn)驗(yàn)證。結(jié)果表明：改進(jìn)的算法提高了地圖匹配的準(zhǔn)確率，縮短了單點(diǎn)匹配時(shí)間，實(shí)現(xiàn)了城市復(fù)雜道路下的精準(zhǔn)地圖匹配。