基于MBR的地圖匹配算法研究.pdf

1、隨著地理信息系統(tǒng)技術(shù)、衛(wèi)星定位技術(shù)以及通信技術(shù)的日趨成熟，個(gè)人定位和軌跡記錄變得簡(jiǎn)單快捷，基于位置的服務(wù)正在迅速普及，也日益受到人們的重視，并顯示出巨大的經(jīng)濟(jì)和社會(huì)效益。位置服務(wù)是通過(guò)移動(dòng)運(yùn)行商的無(wú)線電通信網(wǎng)絡(luò)或外部定位方式（如GPS）獲取移動(dòng)終端用戶的位置信息。在 GIS平臺(tái)的支持下，為用戶提供相應(yīng)服務(wù)的一種增值服務(wù)。
　　位置服務(wù)的前提就是獲得移動(dòng)終端的地理位置。由于 GPS定位設(shè)備和數(shù)字地圖都不可避免地存在誤差，任何一種定位

2、系統(tǒng)都存在一定的定位誤差，所以GPS數(shù)據(jù)往往偏離實(shí)際地理位置。如何保證移動(dòng)終端定位的準(zhǔn)確，是提供位置服務(wù)的關(guān)鍵。作為一種定位技術(shù)，地圖匹配以電子地圖的高精度道路信息為匹配的數(shù)據(jù)基礎(chǔ)，將 GPS接收機(jī)接收到的設(shè)備位置或軌跡數(shù)據(jù)，與電子地圖道路數(shù)據(jù)相比較，從而找到設(shè)備所在的位置。地圖匹配算法，通過(guò)接受到的GPS數(shù)據(jù)進(jìn)行修正來(lái)保證移動(dòng)終端的精確定位從而精確導(dǎo)航，有效的彌補(bǔ)了設(shè)備精度較低的不足。將GPS數(shù)據(jù)映射到實(shí)際位置的過(guò)程稱為地圖匹配(Ma

3、p-Matching)。其過(guò)程是：根據(jù) GPS定位點(diǎn)或 GPS軌跡段與數(shù)字地圖信息，先確定候選路段，從中選擇最優(yōu)匹配路段，再依次擬合 GPS定位點(diǎn)或GPS軌跡段。
　　根據(jù)匹配方式的不同，現(xiàn)有的地圖匹配算法可以分為漸增式匹配算法和全局式匹配算法兩種類型。漸增式匹配算法要求在前一定位點(diǎn)正確匹配的前提下，根據(jù)當(dāng)前定位點(diǎn)搜索候選道路，分別計(jì)算定位點(diǎn)與各個(gè)候選道路的距離及相鄰定位點(diǎn)的連線與各個(gè)候選道路夾角，并選擇與軌跡點(diǎn)距離、角度的加權(quán)和

4、數(shù)值為最小的道路作為匹配結(jié)果。全局式匹配算法是先將多個(gè)軌跡點(diǎn)連接成軌跡曲線，再通過(guò)曲線匹配的方式與路網(wǎng)模型中的道路進(jìn)行相似度比較，并選擇最相似的路段作為匹配結(jié)果。漸增式匹配算法計(jì)算簡(jiǎn)單，準(zhǔn)確性較差，且僅適用于路網(wǎng)模型較簡(jiǎn)單的情況。全局式匹配算法準(zhǔn)確性較好，但是算法復(fù)雜，處理速度較慢。此外，當(dāng)前的地圖匹配算法大多數(shù)采用將軌跡匹配到道路中心線的策略，沒(méi)有考慮到道路寬度的因素。然而，移動(dòng)對(duì)象一般不會(huì)嚴(yán)格地沿著道路中心線行進(jìn)，而是在道路寬度范圍

5、內(nèi)彎曲行進(jìn)，所以，現(xiàn)有方法準(zhǔn)確率偏低。
　　本文提出基于最小外接矩形(Minimum Bounding Rectangle，MBR)的地圖匹配算法。該算法利用MBR對(duì)軌跡進(jìn)行區(qū)域建模，較嚴(yán)格地約束一段軌跡與道路的匹配條件；通過(guò)概率統(tǒng)計(jì)方法確定誤差區(qū)域，準(zhǔn)確地限制候選道路的范圍；根據(jù)歷史軌跡數(shù)據(jù)的相關(guān)性提高匹配率，既克服了漸增式匹配算法誤匹配率較高的缺陷，又避免了全局式匹配算法計(jì)算復(fù)雜的不足；同時(shí)，使用二維幾何變換，擬合軌跡數(shù)據(jù)到最

6、優(yōu)匹配道路上。論文的主要內(nèi)容包括：
　　1)首先，論述了地圖匹配的概念，地圖匹配算法涉及到的基本概念以及增量匹配、全局匹配等基本原理，地圖匹配算法的研究現(xiàn)狀并指出存在的問(wèn)題，為后面算法的設(shè)計(jì)工作做好鋪墊。
　　2)其次，針對(duì)GPS定位數(shù)據(jù)的特點(diǎn)，研究GPS數(shù)據(jù)預(yù)處理方法。數(shù)據(jù)預(yù)處理部分，包括了誤差分析，數(shù)據(jù)產(chǎn)生冗余、中斷或漂移的原因并給出解決辦法。結(jié)合實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，給出處理后的效果。實(shí)驗(yàn)結(jié)果表明，論文中數(shù)據(jù)處理的方法正確

7、，處理后的結(jié)果符合真實(shí)的道路情況，可以作為下一步地圖匹配的數(shù)據(jù)源。
　　3)第三，在上述工作基礎(chǔ)上，詳細(xì)介紹基于MBR的地圖匹配算法設(shè)計(jì)與實(shí)現(xiàn)。重點(diǎn)論述了算法的設(shè)計(jì)思路，算法的實(shí)現(xiàn)過(guò)程以及算法流程。按照算法流程完成了誤差區(qū)域的確定、最佳匹配道路識(shí)別的設(shè)計(jì)。闡述了如何獲得最佳匹配道路的算法實(shí)現(xiàn)過(guò)程，對(duì)流程中的每個(gè)算法過(guò)程進(jìn)行了詳細(xì)的描述，并給出了實(shí)現(xiàn)流程圖。
　　4)最后，經(jīng)過(guò)局部仿真實(shí)驗(yàn)，對(duì)基于MBR的地圖匹配算法進(jìn)行驗(yàn)證，

8、在實(shí)驗(yàn)中，采用GPS模塊接收數(shù)據(jù)，針對(duì)較復(fù)雜的路段進(jìn)行地圖匹配，并詳細(xì)給出了復(fù)雜路段和一般路段的匹配實(shí)驗(yàn)結(jié)果。經(jīng)驗(yàn)證該算法能夠更真實(shí)地反映GPS載體運(yùn)動(dòng)軌跡，其匹配效率和準(zhǔn)確性較高。
　　在該算法經(jīng)過(guò)初步驗(yàn)證基礎(chǔ)上，又將其集成于“校園GPS巡檢系統(tǒng)”中進(jìn)行實(shí)際應(yīng)用驗(yàn)證。目前，國(guó)內(nèi)外巡邏績(jī)效考核還處在起步階段，95％以上的用戶選擇了離線式電子巡更系統(tǒng)，但仍存在許多問(wèn)題和缺陷。例如：考核信息過(guò)于匱乏，巡邏過(guò)程中巡檢點(diǎn)之外的執(zhí)勤表現(xiàn)無(wú)從

9、考證；不能實(shí)時(shí)定位；巡邏歷史數(shù)據(jù)難以可視化；主觀性和描述性考核指標(biāo)較多，客觀公正性有待進(jìn)一步加強(qiáng)。因此，本文提出基于 GPS軌跡的巡邏績(jī)效考核模型。首先，本文利用 GPS軌跡記錄儀采集數(shù)據(jù)，追蹤定位巡邏人員的執(zhí)勤軌跡。GPS軌跡形式的考核信息，包含了巡邏時(shí)間、地點(diǎn)、速度等，且記錄頻率最高為1次/秒。其次，借以功能強(qiáng)大的GIS時(shí)空分析能力，以巡邏區(qū)域、巡邏路線、巡邏區(qū)段、巡檢點(diǎn)等為主要研究對(duì)象，分析保安人員的巡邏過(guò)程，客觀提取考核指標(biāo)信息