基于車輛GPS軌跡數(shù)據(jù)的農(nóng)村公路地圖匹配算法

毛海臻 毛華

摘 要：為了提升農(nóng)村地區(qū)車輛軌跡與縣鄉(xiāng)路網(wǎng)的匹配精度，解決車輛行駛軌跡飄移、點(diǎn)位跳躍等問題，本研究基于隱形馬爾可夫理論，通過劃分農(nóng)村公路網(wǎng)格，計(jì)算觀測概率與轉(zhuǎn)移概率乘積的最大值，然后通過編程建模篩選出最佳候選路線，實(shí)現(xiàn)車輛軌跡與農(nóng)村路網(wǎng)的在線匹配。筆者選取平頂山市寶豐縣某農(nóng)村公路為研究對(duì)象，現(xiàn)場驗(yàn)證了該算法的可行性和有效性。試驗(yàn)結(jié)果表明：該算法能夠提升農(nóng)村公路車輛軌跡的匹配精度，在路線十字、T形交叉及平曲線中點(diǎn)等區(qū)域的軌跡匹配精度提升效果明顯。

關(guān)鍵詞：農(nóng)村公路;GPS軌跡數(shù)據(jù);地圖匹配

中圖分類號(hào)：U418.6 ? ? ?文獻(xiàn)標(biāo)志碼：A ? ? 文章編號(hào)：1003-5168（2022）11-0022-04

DOI：10.19968/j.cnki.hnkj.1003-5168.2022.11.004

Rural Road Map Matching Algorithm Based on Vehicle GPS Trajectory Data

MAO Haizhen1? ? MAO Hua2

（1.Henan Communications Planning & Design Institute Co.，Ltd，Zhengzhou 450000，China;

2.Hebi Qibin District Transportation Bureau，Hebi 458030，China ）

Abstract：In order to improve the matching accuracy between vehicle trajectory and county and township road network in rural areas，and solve the problems of vehicle trajectory drift，point jumping and so on.With the help of hidden Markov theory，this paper divides the rural road grid，calculates the maximum product of observation probability and transfer probability，selects the best candidate route through programming modeling，and realizes the online matching between vehicle trajectory and rural road network.A rural highway in Baofeng County，Pingdingshan City is selected as the experimental object to verify the feasibility and effectiveness of the algorithm.The results show that the algorithm can improve the track matching accuracy of rural road vehicles.In the areas of route cross，T-shaped cross and the midpoint of horizontal curve，the track matching accuracy is obviously improved.

Keywords：rural highway;GPS track data;map matching

0 引言

近年來，我國鄉(xiāng)村公路發(fā)展迅速，截至2021年10月，全國農(nóng)村公路通車?yán)锍踢_(dá)到438.2萬 km。但部分鄉(xiāng)村地區(qū)受通信基站數(shù)量少、地形地貌復(fù)雜等因素的影響，導(dǎo)致車輛GPS軌跡點(diǎn)位與實(shí)際路線存在偏差大、匹配度低等問題，如何有效提升鄉(xiāng)村公路車輛軌跡匹配精度已成為研究的重點(diǎn)問題。

地圖匹配（map-matching）技術(shù)是在車輛處于行駛狀態(tài)下，實(shí)時(shí)收集、分析車輛的地理空間信息，借助算法模型來實(shí)現(xiàn)車輛經(jīng)緯度與路線位置的動(dòng)態(tài)關(guān)聯(lián)[1]。針對(duì)路網(wǎng)軌跡算法模型，國內(nèi)外學(xué)者已相繼提出幾何模型、權(quán)重模型、網(wǎng)絡(luò)拓?fù)淠Ｐ偷?，但在路網(wǎng)匹配精度和軌跡匹配時(shí)間方面仍存在諸多問題[2]。鄉(xiāng)村公路具有線多面廣、路網(wǎng)復(fù)雜的特點(diǎn)，傳統(tǒng)的軌跡匹配模型已無法滿足農(nóng)村公路車輛軌跡匹配的精度要求。對(duì)此，本研究基于隱馬爾可夫模型，建立基于車輛GPS軌跡數(shù)據(jù)的農(nóng)村公路地圖匹配模型，通過劃分路線網(wǎng)格，計(jì)算觀測概率、轉(zhuǎn)移概率，尋找最大的似然路徑，從而實(shí)現(xiàn)車輛行駛軌跡與農(nóng)村路網(wǎng)的動(dòng)態(tài)匹配。本研究選取平頂山市寶豐縣某農(nóng)村公路為研究對(duì)象，現(xiàn)場驗(yàn)證算法模型的可行性、準(zhǔn)確性，從而有效提升農(nóng)村路網(wǎng)車輛軌跡的匹配程度。

1 農(nóng)村公路車輛軌跡匹配模型

1.1 劃分農(nóng)村公路網(wǎng)格

隨著采集頻率和行駛時(shí)間的增加，車輛GPS軌跡點(diǎn)位與路網(wǎng)經(jīng)緯度的數(shù)據(jù)集合會(huì)成倍數(shù)關(guān)系增長，從而造成算法模型遍歷計(jì)算任務(wù)重，導(dǎo)致匹配耗時(shí)長。依據(jù)農(nóng)村公路路線長度遠(yuǎn)大于寬度的特征，近似將農(nóng)村公路看作一條曲線，將路線的集合作為路網(wǎng)。在電子地圖基礎(chǔ)上，預(yù)先將路網(wǎng)進(jìn)行網(wǎng)格化劃分（網(wǎng)格間距約為100 m）[3]，并將網(wǎng)格單元進(jìn)行分類排序、編碼存儲(chǔ)，進(jìn)而提升數(shù)據(jù)庫的計(jì)算運(yùn)行效率。

1.2 車輛軌跡匹配模型

為了進(jìn)一步提升軌跡點(diǎn)位匹配的效率及精度，通過設(shè)定圓形誤差檢索區(qū)域，縮小候選路線范圍。檢索區(qū)域的路線數(shù)量Φ分為以下3種情況：①當(dāng)路線數(shù)量Φ為0時(shí)，說明受地形環(huán)境或數(shù)據(jù)精度的影響，該GPS點(diǎn)位發(fā)生跳躍，無法與路網(wǎng)進(jìn)行關(guān)聯(lián)匹配，在路網(wǎng)匹配過程中需要將此類無效數(shù)據(jù)進(jìn)行剔除;②當(dāng)路線數(shù)量Φ為1時(shí)，說明檢索區(qū)域范圍僅存在1條候選路線，車輛軌跡能夠真實(shí)有效地反映出路網(wǎng)空間線形，該候選路線可作為最終結(jié)果進(jìn)行直接匹配;③當(dāng)路線數(shù)量Φ為2時(shí)，表明檢索區(qū)域內(nèi)存在2條候選路線，此情況多出現(xiàn)在路線交叉的區(qū)域，無法明確與GPS點(diǎn)位相匹配的具體路線，需借助計(jì)算模型比較軌跡點(diǎn)位與各路線間的最小距離ε。B4580923-1B7C-4064-8555-C506F1A371D8

依據(jù)數(shù)據(jù)點(diǎn)位匹配特征，發(fā)現(xiàn)最小距離ε與匹配概率成反比，即最小距離ε越小，匹配概率越高。選取高斯分布公式建立正態(tài)分布，計(jì)算軌跡點(diǎn)位于某候選路線的觀測概率，見式（1）[4]。

[Pd（Trn︱Φi）=12πσze?12D（Φi，Trn）2σ2z]? （1）

式中：[Trn]為軌跡點(diǎn)位;[σz]為GPS點(diǎn)位的標(biāo)準(zhǔn)差，取20 m[5];[D（Φi，Trn）]表示點(diǎn)到候選路線的垂直距離。

候選路線的選取受相鄰軌跡點(diǎn)的路線連續(xù)性的影響。同時(shí)，考慮到農(nóng)村公路路線交叉多等特征，車輛行駛軌跡可能存在頻繁轉(zhuǎn)彎、點(diǎn)位跳躍等情況。對(duì)此，依據(jù)上個(gè)軌跡點(diǎn)所在的候選路線計(jì)算下個(gè)軌跡點(diǎn)所在候選路段的概率時(shí)，選用Manhattan公式來計(jì)算點(diǎn)間距[D1]，依次遍歷最小距離[ε]與[D1]的差值，可得出車輛軌跡中連續(xù)點(diǎn)位的轉(zhuǎn)移概率，見式（2）（3）[4]。

[dij]=[Dsp（Φi，Φj）]-[D1（Trn，Trn+1）]? ?（2）

[Pd（Φi，Trn，Φj，Trn+1）]=[? 1βedijβ0]? ? （3）

式中：[Dsp（Φi，Φj）]<[THDsp]時(shí)，[Pd]取[1βedijβ]，反之則取0;[THDsp]為最短路徑閾值，該值取決于車輛行駛速度;[β]為模型參數(shù)[2]。

1.3 車輛軌跡匹配

在已知觀測概率及轉(zhuǎn)移概率的基礎(chǔ)上，采用維特比算法（Viterbi algorithm）來尋找最大似然路線[2]，即通過n個(gè)GPS軌跡點(diǎn)的觀測概率、轉(zhuǎn)移概率來計(jì)算所有情況下兩者的乘積結(jié)果，乘積最大值的組合方式就是最接近真實(shí)路徑的車輛軌跡，如圖1所示。

1.4 編程建模開發(fā)應(yīng)用

依據(jù)車輛軌跡的數(shù)據(jù)特征，建立涵蓋車輛經(jīng)緯度（lng，lat）、方位角[θ]、速度v、間隔時(shí)間t等參數(shù)的專題數(shù)據(jù)庫，數(shù)據(jù)庫類型選取目前應(yīng)用廣泛的MySQL。通過編程語言建立軌跡點(diǎn)位與路網(wǎng)數(shù)據(jù)的動(dòng)態(tài)匹配模型，基于Java語言定制開發(fā)Android手機(jī)軟件（見圖2），通過高德地圖API將處理前后的車輛行駛軌跡展示出來。由于高德地圖采用的是GCJ-02火星坐標(biāo)系，若直接使用WGS84坐標(biāo)會(huì)造成點(diǎn)位偏差，因此在傳遞經(jīng)緯度數(shù)據(jù)時(shí)應(yīng)將坐標(biāo)系格式進(jìn)行統(tǒng)一[6]。

2 車輛軌跡匹配流程

依據(jù)數(shù)據(jù)采集、編程建模、開發(fā)驗(yàn)證等環(huán)節(jié)，總結(jié)車輛GPS軌跡數(shù)據(jù)與農(nóng)村公路地圖匹配算法流程，具體如下。

①采集車輛軌跡GPS點(diǎn)位數(shù)據(jù)（包括經(jīng)緯度、間隔時(shí)間、瞬時(shí)速度等），調(diào)用農(nóng)村公路電子地圖，對(duì)初始數(shù)據(jù)進(jìn)行篩選、清洗，創(chuàng)建數(shù)據(jù)庫、數(shù)據(jù)表。

②依據(jù)農(nóng)村公路路網(wǎng)密度，設(shè)定單元網(wǎng)格尺寸，批量生成單元模塊，并進(jìn)行分類排序、編碼存儲(chǔ)。

③劃定誤差檢索區(qū)域范圍，優(yōu)選圓形誤差閾值、采點(diǎn)頻率等相關(guān)參數(shù)及數(shù)據(jù)標(biāo)準(zhǔn)。

④確定誤差檢索范圍內(nèi)存在的路線數(shù)量Φ，判定是否需要借助模型篩選候選路徑。

⑤計(jì)算候選點(diǎn)的觀測概率、轉(zhuǎn)移概率、最小距離等，確定最大似然路線。

⑥通過編程建模、開發(fā)應(yīng)用模塊、現(xiàn)場采集驗(yàn)證，最終得到車輛的優(yōu)化軌跡。

3 試驗(yàn)結(jié)果分析

為驗(yàn)證車輛軌跡與農(nóng)村路網(wǎng)匹配模型的有效性，以平頂山市寶豐縣某農(nóng)村公路為試驗(yàn)對(duì)象，通過現(xiàn)場采集車輛GPS點(diǎn)位信息，對(duì)比算法優(yōu)化前后車輛軌跡匹配結(jié)果存在的差異。

車輛行駛點(diǎn)位的采集頻率將影響連續(xù)兩點(diǎn)的距離誤差及數(shù)據(jù)計(jì)算效率。隨著采集頻率的增加，采樣點(diǎn)將更為密集，軌跡數(shù)據(jù)誤差減小，但路網(wǎng)的匹配效率降低。為兼顧采集誤差及計(jì)算效率的合理性，現(xiàn)場試驗(yàn)測試得出車輛連續(xù)GPS點(diǎn)位的采集時(shí)間間隔為20 s。

在保證車輛行駛速度、采樣頻率、起始時(shí)間等因素相同的前提下，平行采集車輛GPS軌跡點(diǎn)位，分別驗(yàn)證農(nóng)村公路線形為直線、曲線及交叉口區(qū)域的軌跡優(yōu)化效果，車輛GPS點(diǎn)位的數(shù)據(jù)處理結(jié)果如表1、表2所示。

為了能夠更直觀地展示路網(wǎng)匹配修正效果，將縣鄉(xiāng)道路電子地圖、原始車輛軌跡、優(yōu)化后軌跡分別導(dǎo)出為CSV或shp文件，借助ArcGIS及奧維地圖軟件，生成可視化的放大圖片，如圖3、圖4所示

通過對(duì)圖3、圖4進(jìn)行分析可以得出：①當(dāng)農(nóng)村公路線型為直線時(shí)，車輛原始軌跡、模型優(yōu)化軌跡與路網(wǎng)的偏差較小，均能真實(shí)地反映出車輛的行駛軌跡;②當(dāng)?shù)缆肪€形的平曲線半徑較小時(shí)，車輛軌跡易在平曲線中點(diǎn)附近發(fā)生偏移，相較于原始數(shù)據(jù)，經(jīng)模型優(yōu)化后的軌跡可以更加準(zhǔn)確地反映出車輛行駛軌跡;③當(dāng)位于農(nóng)村公路交叉口時(shí)，存在檢索區(qū)域的路線數(shù)量Φ為2的時(shí)刻，疊加GPS精度誤差，原始軌跡的部分點(diǎn)位可能跳躍至其他路線，而優(yōu)化后的車輛軌跡能夠有效保持車輛軌跡的準(zhǔn)確性、連續(xù)性，避免發(fā)生點(diǎn)位偏離距離過大等現(xiàn)象。

4 結(jié)論

為提升車輛GPS軌跡與農(nóng)村路網(wǎng)的匹配程度，本研究基于隱馬爾科夫模型，通過計(jì)算觀測概率、轉(zhuǎn)移概率等參數(shù)，得出車輛最佳行駛軌跡，并以平頂山市寶豐縣某農(nóng)村公路為例，編程驗(yàn)證匹配模型的可行性、有效性。試驗(yàn)結(jié)果表明，經(jīng)模型優(yōu)化后的車輛GPS軌跡與路網(wǎng)的匹配程度較好，在曲線、路線交叉等復(fù)雜路網(wǎng)條件下，路網(wǎng)匹配精度良好。

參考文獻(xiàn)：

[1] 于娟，楊瓊，魯劍鋒，等.高級(jí)地圖匹配算法：研究現(xiàn)狀和趨勢[J].電子學(xué)報(bào)，2021（9）：1818-1829.

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

[3] 吉宏梅.基于隱馬爾可夫模型的路網(wǎng)匹配算法研究[D].沈陽：沈陽理工大學(xué)，2020.

[4] 陳浩，許長輝，張曉平，等.基于隱馬爾科夫模型和動(dòng)態(tài)規(guī)劃的手機(jī)數(shù)據(jù)移動(dòng)軌跡匹配[J].地理與地理信息科學(xué)，2019（3）：1-8.

[5] 文江輝，霍佳琪，楊玲.一種車輛GPS軌跡數(shù)據(jù)的改進(jìn)地圖匹配算法[J/OL].武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版），2022：1-11[2022-05-01].http：//kns.cnki.net/kcms/detail/42.1824.U.20220309.2125.093.html

[6] 康路，閆浩文，張黎明.電子地圖間的實(shí)時(shí)坐標(biāo)轉(zhuǎn)換系統(tǒng)[J].遙感信息，2018（2）：122-126.B4580923-1B7C-4064-8555-C506F1A371D8