国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

地圖匹配算法實踐

bluesky / 1539人閱讀

摘要:在實際應用中,采樣信號的質量會嚴重影響地圖匹配結果采樣頻率的降低定位誤差的加大信號的丟失,都會使匹配的不準確性增加。年首次設立的競賽,其內容就是地圖匹配。地圖匹配算法綜述以使用到的信息來劃分現有的算法可被分成四類幾何拓撲概率高級。

1 背景

如下圖所示,1、2、3 這三個點是汽車的GPS定位結果,盡管汽車是在道路上,但定位結果與道路存在偏差。地圖匹配(Map Matching)是指將行車軌跡的經緯度采樣序列與數字地圖路網匹配的過程,其本質上是平面線段序列的模式匹配問題( Alt等,2003)。

在實際應用中,GPS采樣信號的質量會嚴重影響地圖匹配結果:采樣頻率的降低、定位誤差的加大、信號的丟失,都會使匹配的不準確性增加。這些情況在實際應用中經常出現。如何在這些情況下仍能保持較高的路徑匹配準確率是個值得研究的問題。

2012年ACM SIGSPATIAL首次設立的競賽,其內容就是地圖匹配。三年前本人有幸和國防科大的楊岸然博士一同參加了該競賽,收獲良多。

2 地圖匹配算法綜述 2.1 以使用到的信息來劃分

現有的算法可被分成四類:幾何、拓撲、概率、高級。
a)基于幾何的算法考慮GPS點與道路的幾何信息,如距離、角度等;
b)基于拓撲的算法使用道路拓撲信息來控制;
c)概率方法通過考慮GPS點的概率;
d)高級的算法往往綜合考慮使用全面信息,有卡爾曼濾波、模糊邏輯模型、隱式馬爾可夫模型等等。

2.2 以考慮采樣點的范圍來劃分

根據考慮采樣點的范圍,可分成局部/增量算法、全局算法。
a)局部/增量算法是貪婪算法,每次確定一個匹配點,下個點從已經確定的匹配點開始。這些方法根據距離和方向相似性來找到局部最優點或邊。(在線匹配)
b)全局算法是要從路網中找到一條與采樣軌跡最接近的匹配軌跡。為了測量采樣軌跡和匹配軌跡的相似性,大多數算法使用“Frechet距離”或者是“弱Frechet距離”。還有時空匹配算法、投票算法等。(離線匹配)

2.3 以采樣點的頻率來劃分

根據軌跡數據的采樣頻率,現有的地圖匹配算法可分成:
a)高頻采樣算法(所有局部算法、部分全局算法如Frechet距離判別法等)
b)低頻采樣算法(ST-matching算法、IVVM算法

一般認為30s及其以上為低頻采樣,1s~10s為高頻采樣。

3 我們的訓練數據

a)路網數據: Washington State U.S.A.(有128萬條邊 )
b)GPS數據:采樣頻率為1~30s,

4 采用的算法

使用ST-Matching算法(Lou等,2009),該算法是一種全局算法,能綜合幾何信息( GPS點與道路的距離)、道路拓撲信息(最短路徑)、道路屬性信息(每條道路的限速),具有精度高,穩定性好等優點。

4.1 準備候選集

4.2 確定權重

a)空間因素權重(Fs)

b)時間因素權重(Ft)

5 實驗結果

6 技術實現要點 6.1 地圖投影問題

問題:原始道路網數據的坐標與軌跡點的坐標并不在一個坐標體系下,不能直接進行計算!

解決方法:使用PRJ4地圖投影庫將兩個數據投影到統一坐標下。

6.2 大路網信息數據量的讀取

問題:該路網有128萬條邊,我們采用C++,如果讀取每條邊都進行new和delete操作,將執行128萬次,效率極低!

解決方法:使用內存池技術。

6.3 最短路徑算法的選擇

問題:候選集不同層次的候選點之間都要計算最短路徑,使用最常用的Dijkstra最短路徑算法效率極低!

解決方法:使用啟發式最短路徑算法:A-star算法。

6.4 索引

問題:由于競賽真實測試會使用很多不同的路網數據,所以建立索引沒必要,但是計算某一GPS點的候選集時路網所有數據會參與計算,效率很低;

解決方法:計算某一GPS點的候選集時,先進行切片過濾,比如以該GPS點為中心,生成200m的正方形框,然后在該框里建立新的道路網,這時計算候選集時只需要與該框內的道路網數據計算。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/52203.html

相關文章

  • 地圖匹配算法實踐

    摘要:在實際應用中,采樣信號的質量會嚴重影響地圖匹配結果采樣頻率的降低定位誤差的加大信號的丟失,都會使匹配的不準確性增加。年首次設立的競賽,其內容就是地圖匹配。地圖匹配算法綜述以使用到的信息來劃分現有的算法可被分成四類幾何拓撲概率高級。 1 背景 如下圖所示,1、2、3 這三個點是汽車的GPS定位結果,盡管汽車是在道路上,但定位結果與道路存在偏差。地圖匹配(Map Matching)是指將行...

    nihao 評論0 收藏0
  • 機器學習在美團配送系統的實踐:用技術還原真實世界

    摘要:可以說,美團要建設的就是配送系統的超級大腦。美團超腦配送系統目前互聯網技術,很大部分還是針對線上產品和系統研發,整個流程可以在線上全部完成,而這也正是配送技術最大的不同和挑戰。 在2018 AI開發者大會(AI NEXTCon)上,美團配送AI方向負責人何仁清,分享了美團在即時配送領域中機器學習技術的最新進展,以及如何通過大數據和機器學習手段,建立對線下真實世界各種場景的感知能力,還原...

    hearaway 評論0 收藏0
  • GitChat · 人工智能 | 自動駕駛的技術架構和生態發展

    摘要:目前每年全球有萬人死于車禍,損失,相關于很多國家的,自動駕駛可以很大效率的減少車禍,拯救生命。美國汽車工程師協會和美國高速公路安全局將自動駕駛技術進行了分級。特定場所的高度自動駕駛。這叫基于規則的一種自動駕駛,簡單的。 來自 GitChat 作者:劉盼更多IT技術分享,盡在微信公眾號:GitChat技術雜談 進入 GitChat 閱讀原文我們先以汽車在現代科技領域的演進來開始這次的ch...

    X1nFLY 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<