3S系統(tǒng)中的地圖匹配方法研究.pdf

1、“3S系統(tǒng)”即GIS/GPS/LBS系統(tǒng)，就是采取GPS作為定位手段，為用戶提供LBS服務(wù)的嵌入式GIS系統(tǒng)。“地圖匹配”研究的問題就是如何在3S系統(tǒng)的導航地圖和GPS信號精度都比較低下的情況下，將接收到的GPS位置匹配到地圖上的實際位置上去。 本文首先簡要介紹了3S系統(tǒng)的含義以及典型的3S系統(tǒng)的架構(gòu)，然后回顧總結(jié)了現(xiàn)有的地圖匹配算法，包括基于地圖幾何信息的點到點、點到線和線到線匹配，基于地圖拓撲結(jié)構(gòu)信息的匹配算法，以及將這兩者

2、結(jié)合起來的綜合性的地圖匹配算法?；诘貓D幾何信息的匹配算法是將地圖視為點、線等幾何對象的集合，利用GPS點以及相鄰GPS點連接形成的矢量線段與地圖上幾何對象的相似度來進行匹配。這類算法最大的缺點是備選路段范圍大，算法效率低，并且不能保證連續(xù)GPS點的匹配結(jié)果具有連續(xù)性。這些缺點可以利用地圖的拓撲信息，即路段與路段之間的連通性等性質(zhì)有效地克服。因此，將地圖幾何信息與拓撲信息結(jié)合起來的匹配算法在準確度和性能上均有所提高，但仍存在著不少缺點，

3、如準確度低，不能自我糾正，一次匹配錯誤可能導致連續(xù)的后續(xù)匹配錯誤等。 接著，本文以這些算法為基礎(chǔ)，提出了一種新的地圖匹配算法，很好地克服了上述缺點。該算法的主要特點包括：保存多個匹配結(jié)果，并可回溯，在后續(xù)匹配中自我校正歷史匹配記錄；綜合考慮了多種匹配因素，并根據(jù)匹配因素的權(quán)重對匹配度進行擬合；充分利用了歷史匹配記錄，縮小了備選路段的范圍，同時將備選路段分成三個等級，即當前路段、當前路段的后續(xù)路段以及當前路段后續(xù)路段的后續(xù)路段，在

4、算法效率和準確度之間取得了良好的平衡；計算簡單，沒有復雜的積分計算，適用軟硬件資源緊張的嵌入式實時系統(tǒng)；可以快速高效地構(gòu)建出用戶所有可能的運動軌跡等。 為支持該算法，本文同時還設(shè)計了一種數(shù)據(jù)結(jié)構(gòu)—PS Graph。PS Graph其實是一種具有特殊用法的用來存儲匹配結(jié)果的有向圖，它可以很自然地表示GPS點匹配路段之間的前后關(guān)系，并且可以隨著匹配的GPS點的增多而靈活地擴展，并在回溯時高效地刪除歷史匹配記錄。同時文中還描述了一種簡潔