鬼佬大哥大
  • / 23
  • 下載費用:30 金幣  

用于在導航應用中使用的方法和裝置.pdf

摘要
申請專利號:

CN201380071743.1

申請日:

2013.01.30

公開號:

CN105026892A

公開日:

2015.11.04

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||著錄事項變更IPC(主分類):G01C 21/32變更事項:申請人變更前:赫力環球有限公司變更后:赫力環球有限公司變更事項:地址變更前:荷蘭維德霍溫變更后:荷蘭艾恩德霍芬|||實質審查的生效IPC(主分類):G01C 21/32申請日:20130130|||公開
IPC分類號: G01C21/32; G06F17/30 主分類號: G01C21/32
申請人: 赫力環球有限公司
發明人: M·普法伊勒
地址: 荷蘭維德霍溫
優先權:
專利代理機構: 北京市金杜律師事務所11256 代理人: 酆迅; 程延霞
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201380071743.1

授權公告號:

|||||||||

法律狀態公告日:

2018.02.27|||2016.08.24|||2015.12.02|||2015.11.04

法律狀態類型:

授權|||著錄事項變更|||實質審查的生效|||公開

摘要

一種方法包括提供或接收經更新的信息,先前信息和所述經更新的信息與地理地區相關聯,所述先前信息包括與能夠用于連接至不同地理地區中的一個或多個鏈路的一個或多個鏈路有關的信息,并且所述經更新的信息至少包括所述先前信息以及與用于連接至所述不同地理地區中的一個或多個鏈路的一個或多個鏈路相關的新信息。

權利要求書

權利要求書
1.  一種方法,包括:
提供或接收經更新的信息,先前信息和所述經更新的信息與地理地區相關聯,所述先前信息包括與能夠用于連接至不同地理地區中的一個或多個鏈路的一個或多個鏈路有關的信息,并且所述經更新的信息至少包括所述先前信息以及與用于連接至所述不同地理地區中的一個或多個鏈路的一個或多個鏈路有關的新信息。

2.  根據權利要求1所述的方法,其中所述提供包括:
針對所述地理地區中能夠用于連接至所述不同地理地區的一個或多個鏈路的每條鏈路計算排名;
針對所述每條鏈路確定所述計算的排名是否具有比針對所述鏈路先前計算的排名低的重要性;以及
如果是,則保持所述先前計算的排名作為所述鏈路的排名。

3.  根據權利要求1或2所述的方法,包括將針對所述地理地區的所述經更新的信息與針對所述地理地區的地圖信息相關聯地進行存儲。

4.  根據任一前述權利要求所述的方法,其中地理區域至少被劃分為所述地理地區和所述不同地理地區,其中所述地理地區和所述不同地理地區彼此相鄰,并且所述地理地區和所述不同地理地區中的每一個包括至少一個能夠用于形成所述地理地區中的第一位置與所述不同地理地區中的第二位置之間的路線的相應鏈路。

5.  根據任一前述權利要求所述的方法,包括在確定所述地理地區和所述不同地區之間或者所述地理地區中的第一位置和所述不同地區中的第二位置之間的路線時使用所述經更新的信息。

6.  根據任一前述權利要求所述的方法,其中所述新信息涉及與所述先前信息所涉及的鏈路不同的一個或多個鏈路和/或在所述先前信息所涉及的所述一個或多個鏈路已經發生變化的情況下所述先前信息所涉及的一個或多個鏈路。

7.  根據任一前述權利要求所述的方法,其中所述先前信息和所述經更新的信息包括邊緣標志信息。

8.  根據任一前述權利要求所述的方法,其中所述先前信息和所述經更新的信息包括指示所述鏈路是否是去往地區的相應分區的相應節點的期望路徑的向量。

9.  根據權利要求8所述的方法,其中所述先前信息包括先前向量并且所述經更新的信息包括更新向量,所述更新向量中的每個值與所述先前向量相同或者相對于所述先前向量變化為表示更高排名的值。

10.  根據任一前述權利要求所述的方法,其中所述先前信息和所述經更新的信息包括鏈路分級信息。

11.  根據權利要求10所述的方法,其中所述經更新的信息處于第一鏈路級別并且所述先前信息被保持在所述第一鏈路級別。

12.  根據任一前述權利要求所述的方法,其中所述鏈路中的每個鏈路都具有與之相關聯的鏈路等級。

13.  根據任一前述權利要求所述的方法,包括向所述鏈路中的一個或多個鏈路應用成本函數。

14.  根據權利要求13所述的方法,其中所述成本函數取決于以下各項中的一項或多項:與所述鏈路相關聯的長度、與所述鏈路相關聯的速度、以及所述鏈路的一個或多個屬性。

15.  根據任一前述權利要求所述的方法,包括存儲所述先前信息,在所述地區的更新地區信息已經被更新時對所述更新地區信息進行編譯并且存儲與所述編譯相關聯的第一信息,以及根據所述先前信息和所述第一信息提供所述經更新的信息。

16.  根據權利要求15所述的方法,包括關于所述先前信息和所述第一信息執行OR運算以提供所述經更新的信息。

17.  根據權利要求15所述的方法,其中所述經更新的信息包括所述先前信息和所述第一信息。

18.  一種計算機程序,包括計算機代碼,所述計算機代碼在被執行時使得根據任一前述權利要求所述的方法被執行。

19.  一種裝置,包括至少一個處理器和包括計算機程序代碼的至少一個存儲器,所述至少一個存儲器和所述計算機程序代碼被配置為與所述至少一個處理器一起使得所述裝置至少提供或接收經更新的信息,先前信息和所述經更新的信息與地理地區相關聯,所述先前信息包括與能夠用于連接至不同地理地區中的一個或多個鏈路的一個或多個鏈路有關的信息,并且所述經更新的信息至少包括所述先前信息以及與用于連接至所述不同地理地區中的一個或多個鏈路的一個或多個鏈路有關的新信息。

20.  根據權利要求19所述的裝置,其中所述至少一個存儲器和所述計算機程序代碼被配置為與所述至少一個處理器一起使得所述裝置針對所述地理地區中能夠用于連接至所述不同地理地區的一個或多個鏈路的每條鏈路計算排名、針對所述每條鏈路確定所述計算的排名是否具有比針對所述鏈路先前計算的排名低的重要性、并且如果是,則保持所述先前計算的排名作為所述鏈路的排名。

21.  根據權利要求19或20所述的裝置,其中所述至少一個存儲器和所述計算機程序代碼被配置為與所述至少一個處理器一起使得所述裝置將針對所述地理區域的所述經更新的信息與針對所述地理區域的地圖信息相關聯地進行存儲。

22.  根據權利要求19、20或21所述的裝置,其中地理區域可以至少被劃分為所述地理地區和所述不同地理地區,其中所述地理地區和所述不同地理地區彼此相鄰,并且所述地理地區和所述不同地理地區中的每一個包括至少一個能夠用于形成所述地理地區中的第一位置與所述不同地理地區中的第二位置之間的路線的相應鏈路。

23.  根據權利要求19至22中任一項所述的裝置,其中所述至少一個存儲器和所述計算機程序代碼被配置為與所述至少一個處理器一起使得所述裝置在確定所述地理地區和所述不同地區之間或者所述地理地區中的第一位置和所述不同地區中的第二位置之間的路線時使用所述經更新的信息。

24.  根據權利要求19至23中任一項所述的裝置,其中所述先前 信息和所述經更新的信息可以包括指示所述鏈路是否是去往地區的相應分區的相應節點的期望路徑的向量。

25.  根據權利要求19至24中任一項所述的裝置,其中所述先前信息可以包括先前向量并且所述經更新的信息可以包括更新向量,所述更新向量中的每個值與所述先前向量相同或者相對于所述先前向量變化為表示更高排名的值。

26.  根據權利要求19至24中任一項所述的裝置,其中所述先前信息和所述經更新的信息可以包括鏈路分級信息。

27.  根據權利要求19至26中任一項所述的裝置,其中所述至少一個存儲器和所述計算機程序代碼被配置為與所述至少一個處理器一起使得所述裝置存儲所述先前信息、在所述地區的更新地區信息已經被更新時對所述更新地區信息進行編譯并且存儲與所述編譯相關聯的第一信息、并且根據所述先前信息和所述第一信息提供所述經更新的信息。

說明書

說明書用于在導航應用中使用的方法和裝置
技術領域
一些實施例涉及一種特別地但并非排他地在導航應用中使用的方法和裝置。一些實施例還可以涉及導航數據庫。
背景技術
許多設備都能夠提供導航功能。作為示例,這些設備可以是用于該用途的專用設備。這些專用設備可以是便攜式的或者可以例如整合在車輛之中。導航設備還可以被提供在諸如移動電話之類的用戶設備之中。
這些設備需要訪問導航數據庫。該導航數據庫可以被包括在該設備自身之中。可替換地,該數據庫可以在該導航設備與之進行通信的服務器中被提供。在后者的情況下,與該數據庫的通信例如可以經由無線電接口和/或核心網絡來進行。
這樣的導航數據庫可能需要進行更新,以便例如考慮提供新的道路或者針對已有道路的變更。這樣的數據庫被用來計算起點和終點之間的適當路線。
NDS(導航數據標準)是開發用于導航系統中的地圖的標準化物理存儲格式(PSF)的經注冊的機構。目前,有多種不同的更新媒體和數種更新機制可被用于車載系統或移動客戶端。NDS可以為不同系統提供與之協調的格式并且提供有關地圖合成和地圖更新的靈活性。
發明內容
根據一個方面,提供了一種方法,包括:提供或接收經更新的信息,先前信息和所述經更新的信息與地理地區相關聯,所述先前信息包括與能夠用于連接至不同地理地區中的一個或多個鏈路(link)的一個或多個鏈路有關的信息,并且所述經更新的信息至少包括所述先 前信息以及與用于連接至所述不同地理地區中的一個或多個鏈路的一個或多個鏈路相關的新信息。
所述提供可以包括針對所述地理地區中能夠用于連接至所述不同地理地區的一個或多個鏈路的每條鏈路計算排名(rank)、針對所述每條鏈路確定所述計算的排名是否具有比針對所述鏈路先前計算的排名更低的重要性、并且如果是,則保持所述先前計算的排名作為所述鏈路的排名。
所述方法可以包括將針對所述地理地區的所述經更新的信息與針對所述地理地區的地圖信息相關聯地進行存儲。
地理區域可以至少被劃分為所述地理地區和所述不同地理地區,其中所述地理地區和所述不同地理地區彼此相鄰,并且所述地理地區和所述不同地理地區中的每一個包括至少一個能夠用于形成所述地理地區中的第一位置與所述不同地理地區中的第二位置之間的路線的相應鏈路。
所述方法可以包括在確定所述地理地區和所述不同地理地區之間或者所述地理地區中的第一位置和所述不同地區中的第二位置之間的路線時使用所述經更新的信息。
所述新信息可以涉及與所述先前信息所涉及的鏈路不同的一個或多個鏈路和/或在所述先前信息所涉及的所述一個或多個鏈路已經發生變化的情況下所述先前信息所涉及的一個或多個鏈路。
所述先前信息和經更新的信息可以包括邊緣標志信息。
所述先前信息和所述經更新的信息可以包括指示所述鏈路是否是去往地區的相應分區的相應節點的期望路徑的向量。
所述先前信息可以包括先前向量并且所述經更新的信息可以包括更新向量,所述更新向量中的每個值與所述先前向量相同或者相對于所述先前向量變化為表示更高排名的值。
所述先前信息和所述經更新的信息可以包括鏈路分級信息。
所述經更新的信息可以處于第一鏈路級別并且所述先前信息可以被保持在所述第一鏈路級別。
所述鏈路中的每個鏈路都具有與之相關聯的鏈路等級。
所述方法可以包括向所述鏈路中的一個或多個應用成本函數。
所述成本函數可以取決于以下各項中的一項或多項:與所述鏈路相關聯的長度、與所述鏈路相關聯的速度、以及所述鏈路的一個或多個屬性。
所述一個或多個屬性可以包括隧道和橋梁中的一個或多個。
所述方法可以包括存儲所述先前信息,在更新地區信息已經被更新時對所述地區的更新地區信息進行編譯并且存儲與所述編譯相關聯的第一信息,并且根據所述先前信息和所述第一信息提供所述經更新的信息。
所述方法可以包括關于所述先前信息和第一信息執行OR運算以提供所述經更新的信息。
所述經更新的信息可以包括所述先前信息和所述第一信息。
根據一個方面,提供了一種裝置,包括用于提供或接收經更新的信息的裝置,先前信息和所述經更新的信息與地理地區相關聯,所述先前信息包括與能夠用于連接至不同地理地區中的一個或多個鏈路的一個或多個鏈路有關的信息,并且所述經更新的信息至少包括所述先前信息以及與用于連接至所述不同地理地區中的一個或多個鏈路的一個或多個鏈路相關的新信息。
所述用于提供的裝置可以用于針對所述地理地區中能夠用于連接至所述不同地理地區的一個或多個鏈路的每條鏈路計算排名、針對所述每條鏈路確定所述計算的排名是否具有比針對所述鏈路先前計算的排名更低的重要性、并且如果是,則保持所述先前計算的排名作為所述鏈路的排名。
所述裝置可以包括用于將針對所述地理地區的所述經更新的信息與針對所述地理地區的地圖信息相關聯地進行存儲的裝置。
地理區域可以至少被劃分為所述地理地區和所述不同地理地區,其中所述地理地區和所述不同地理地區彼此相鄰,并且所述地理地區和所述不同地理地區中的每一個包括至少一個能夠用于形成所述地 理地區中的第一位置與所述不同地理地區中的第二位置之間的路線的相應鏈路。
所述裝置可以包括用于在確定所述地理地區和所述不同地理地區之間或者所述地理地區中的第一位置和所述不同地區中的第二位置之間的路線時使用所述經更新的信息的裝置。
所述新信息可以涉及與所述先前信息所涉及的鏈路不同的一個或多個鏈路和/或在所述先前信息所涉及的所述一個或多個鏈路已經發生變化的情況下所述先前信息所涉及的一個或多個鏈路。
所述先前信息和經更新的信息可以包括邊緣標志信息。
所述先前信息和所述經更新的信息可以包括指示所述鏈路是否是去往地區的相應分區的相應節點的期望路徑的向量。
所述先前信息可以包括先前向量并且所述經更新的信息可以包括更新向量,所述更新向量中的每個值與所述先前向量相同或者相對于所述先前向量變化為表示更高排名的值。
所述先前信息和所述經更新的信息可以包括鏈路分級信息。
所述經更新的信息可以處于第一鏈路級別并且所述先前信息可以被保持在所述第一鏈路級別。
所述鏈路中的每一個都可以具有與之相關聯的鏈路等級。
所述裝置可以包括用于向所述鏈路中的一個或多個應用成本函數的裝置。
所述成本函數可以取決于以下各項中的一項或多項:與所述鏈路相關聯的長度、與所述鏈路相關聯的速度、以及所述鏈路的一個或多個屬性。
所述一個或多個屬性可以包括隧道和橋梁中的一個或多個。
所述裝置可以包括用于存儲所述先前信息的裝置,用于在更新地區信息已經被更新時對所述地區的更新地區信息進行編譯的裝置,用于存儲與所述編譯相關聯的第一信息,以及用于根據所述先前信息和所述第一信息提供所述經更新的信息的裝置。
所述裝置可以包括用于關于所述先前信息和第一信息執行OR運 算以提供所述經更新的信息的裝置。
所述經更新的信息可以包括所述先前信息和所述第一信息。
根據一個方面,提供了一種裝置,包括:至少一個處理器和至少一個包括計算機程序代碼的存儲器,所述至少一個存儲器和計算機程序代碼被配置為與所述至少一個處理器一起使得所述裝置至少提供或接收經更新的信息,先前信息和所述經更新的信息與地理地區相關聯,所述先前信息包括與能夠用于連接至不同地理地區中的一個或多個鏈路的一個或多個鏈路有關的信息,并且所述經更新的信息至少包括所述先前信息以及與用于連接至所述不同地理地區中的一個或多個鏈路的一個或多個鏈路相關的新信息。
所述至少一個存儲器和計算機程序代碼可以被配置為與所述至少一個處理器一起使得所述裝置針對所述地理地區中能夠用于連接至所述不同地理地區的一個或多個鏈路的每條鏈路計算排名、針對所述每條鏈路確定所述計算的排名是否具有比針對所述鏈路先前計算的排名更低的重要性、并且如果是,則保持所述先前計算的排名作為所述鏈路的排名。
所述至少一個存儲器和計算機程序代碼可以被配置為與所述至少一個處理器一起使得所述裝置將針對所述地理地區的所述經更新的信息與針對所述地理地區的地圖信息相關聯地進行存儲。
地理區域可以至少被劃分為所述地理地區和所述不同地理地區,其中所述地理地區和所述不同地理地區彼此相鄰,并且所述地理地區和所述不同地理地區中的每一個包括至少一個能夠用于形成所述地理地區中的第一位置與所述不同地理地區中的第二位置之間的路線的相應鏈路。
所述至少一個存儲器和所述計算機程序代碼可以被配置為與所述至少一個處理器一起使得所述裝置在確定所述地理地區和所述不同地理地區之間或者所述地理地區中的第一位置和所述不同地區中的第二位置之間的路線時使用所述經更新的信息。
所述新信息可以涉及與所述先前信息所涉及的鏈路不同的一個 或多個鏈路和/或在所述先前信息所涉及的所述一個或多個鏈路已經發生變化的情況下所述先前信息所涉及的一個或多個鏈路。
所述先前信息和經更新的信息可以包括邊緣標志信息。
所述先前信息和所述經更新的信息可以包括指示所述鏈路是否是去往地區的相應分區的相應節點的期望路徑的向量。
所述先前信息可以包括先前向量并且所述經更新的信息可以包括更新向量,所述更新向量中的每個值與所述先前向量相同或者相對于所述先前向量變化為表示更高排名的值。
所述先前信息和所述經更新的信息可以包括鏈路分級信息。
所述經更新的信息可以處于第一鏈路級別并且所述先前信息可以被保持在所述第一鏈路級別。
所述鏈路中的每個鏈路都可以具有與之相關聯的鏈路等級。
所述至少一個存儲器和計算機程序代碼可以被配置為與所述至少一個處理器一起使得所述裝置向所述鏈路中的一個或多個應用成本函數。
所述成本函數可以取決于以下各項中的一項或多項:與所述鏈路相關聯的長度、與所述鏈路相關聯的速度、以及所述鏈路的一個或多個屬性。
所述一個或多個屬性可以包括隧道和橋梁中的一個或多個。
所述至少一個存儲器和計算機程序代碼可以被配置為與所述至少一個處理器一起使得所述裝置存儲所述先前信息、在更新地區信息已經被更新時對所述地區的更新地區信息進行編譯并且存儲與所述編譯相關聯的第一信息、并且根據所述先前信息和所述第一信息提供所述經更新的信息。
所述至少一個存儲器和計算機程序代碼可以被配置為與所述至少一個處理器一起使得所述裝置關于所述先前信息和第一信息執行OR運算以提供所述經更新的信息。
所述經更新的信息可以包括所述先前信息和所述第一信息。
以上方法中的任一個都可以由一種裝置來執行。
還可以提供一種計算機程序,其包括適于執行所述方法的程序代碼裝置。所述計算機程序可以被存儲和/或以其它方式利用載體介質來體現。
應當意識到的是,任何方面的任何特征都可以與其它方面的任何其它特征進行組合。
附圖說明
現在將僅作為示例對附圖加以參考,其中:
圖1A至C示出了例如由NDS提供的更新地區概念;
圖2A至C示出了使用預先計算的邊緣標志的方法;
圖3示出了使用分級鏈路的路線制定的方法;
圖4A至H圖示了對具有預先計算的全局路線信息的更新地區進行更新所存在的問題;
圖5A至H圖示了實施例;
圖6示出了可以在其中提供實施例的系統;
圖7示意性示出了一些實施例的裝置;
圖8示出了使用預先計算的路線制定信息的方法的流程;以及
圖9示出了用于確定預先計算的路線制定信息的方法的流程。
具體實施方式
為了支持特定地區的增量更新,數據庫系統經常被劃分為一般獨立的地區。這些地區例如可以是一個國家或者該國家的一部分,或者具有一些地理意義。例如在NDS的環境中,這些地區可以被稱作更新地區。這些地區可以彼此獨立地進行更新。例如NDS中的地區的更新將在隨后進行更為詳細的描述。
可能需要導航數據庫支持長距離的路線制定。例如,根據數據庫的應用,可能期望例如計算兩個不同國家的兩個城市之間的距離。這些國家可能是相鄰的或者彼此被一個或多個其它國家所隔開。通常期望這樣的長距離路線在相對短的時間段內、例如幾秒鐘量級的時間段 內進行計算。一些導航數據庫提供商為了應對該需求而可以將預先計算的信息包括在數據庫之中。該預先計算的信息是基于完整數據庫的而并沒有考慮到獨立的地區。這將在隨后進行更為詳細的描述。
現在將參考圖1A至1C對更新地區概念進行更為詳細的描述。更新地區使得能夠對導航數據庫內所定義的地理地區進行增量和部分更新。更新地區可以表示數據庫中能夠被進行更新的地理區域。符合NDS標準的數據庫可以在邏輯上被劃分為并不相連但是可以在被定義的點處進行重疊的更新地區。這些被定義的點可以是連接更新地區的通道(gateway)。兩個或更多更新地區可以僅在邊界處進行重疊。NDS將地理區域劃分為規則的分片區域(tiling area)。因此,更新地區邊界通常并不與分片邊界一致。就此而言,參考圖1A,其示意性示出了邏輯分片2。該邏輯分片覆蓋了邊界區域。特別地,該分片的一部分與第一地區4相關聯并且該分片的另一部分與第二地區6相關聯。這兩個地區將被單獨更新。因此,與邊界重疊的諸如分片2的邏輯分片在物理上被存儲在每個相交的更新地區之中。換句話說,分片2關于更新地區1被存儲一次并且關于更新地區2被存儲一次。圖1B示出了關于更新地區1進行存儲的分片,并且圖1C示出了關于更新地區2進行存儲的分片。如能夠看到的,相應分片僅被填充有屬于對應的更新地區的內容。換句話說,關于更新地區1進行存儲的分片2將僅包含更新地區1的內容,而關于更新地區2進行存儲的分片2將僅包含更新地區2的內容。
兩個不同更新地區之間的道路網絡經由通道進行連接。這些通道可以被稱作交叉通道。在兩個更新地區中,邊界的交叉點利用穩定的標識進行存儲。這有時被稱作“通道ID”。穩定的通道ID允許從一個更新地區向另一個更新地區制定路線。在圖1A至C的上下文中,通道交叉點以附圖標記8表示。
現在參考圖2A至C,它們示出了用于在導航數據庫編譯過程期間向導航數據庫中提供預先計算的路線制定信息的第一技術。該信息可以被用來加速目標系統中的路線制定。圖2A至C中所圖示的方法 是使用預先計算的邊緣標志信息的技術。如圖2A中所示,假設數據庫被劃分為帶有編號或序號的分區。圖2A示出了被劃分為多個分區的地理區域。
參考圖2B,其示意性地示出了六個分區,其中每一個被編號為1至6。每條邊緣被分配一個位向量,以便針對每個分區i指示該邊緣是否處于從該邊緣的起始節點到分區i內的任意節點的最優路徑上。分區的網格數或編號將反映出該網格的空間位置。假設存在n個這樣的分區。針對每條鏈路(或道路),分配兩個向量,其中的每個向量由n位組成。在第一位向量中,位置i處的“1”位指示該鏈路處于從該鏈路的基準節點開始去往分區i中的任意目的地的最優路線上。在第二位向量中,位置i處的“1”指示該鏈路處于從該鏈路的非基準點開始去往分區i中的任意目的地的最優路線上。已知目的地位于分區i中的路線制定算法僅需要探究針對其設置對應項目的那些鏈路。
參考圖2B,對于從第一節點14到第二節點10的鏈路,向量將為110110,這意味著該鏈路處于針對分區1、2、4和5中的目的地的最優路線上(在圖2B的示例中有6個分區)。對于從第一節點14到第三節點12的鏈路,向量將為011001,這意味著該鏈路處于針對分區2、3和6中的目的地的最優路線上。
考慮圖2C,提供了起點16并且在分區3中提供了目的地18。對于該行程而言,經由節點10的路線能夠進行修剪,因為該向量在與分區3相關聯的位置并沒有“1”。換句話說,不存在經由節點10去往分區3的最優路線。諸如迪杰斯特拉(Dijkstra)或A*的圖形算法可以被配置為使用該邊緣信息。
另一種用于加速路線制定的方法關于圖3進行了圖示并且其使用分級鏈路的集合。在NDS中,提供了多個不同的層。高級別的層可以僅包括更為重要的鏈路而較低級別的層則將包括更多鏈路。該結構是分級的,這意味著較低級別將包括前一層的所有鏈路以及一個或多個附加鏈路。最低級別通常將包含所有鏈路。
為了對一個實施例進行說明,考慮其中使用五個不同層的示例。 這五個不同層可以被稱作級別13、10、8、6和4。應當意識到的是,所使用的層的數目在一些實施例中可以大于或小于5。可用層的數目可以大于或小于13。
在該示例中,最為詳細的層可以被認為處于級別13,其包含所有道路。例如處于級別10、8、6和4上的層因此可能僅包含重要的道路。級別4上的層可以僅包含最為重要的道路。
一種得到這樣的分層的方法是使用函數道路等級值。該值可以以人工方式、算法方式或者以任意其它適當方式進行指定。FRC值可以反映出道路的重要性。FRC值可以依據由當地機關定義的行政道路等級。在德國,FRC值1可以被分配給高速公路,2被分配給國道,等等。然而,這樣的方法可能沒有對于給定的成本函數提供最優路線。為了實現路線制定的優化,可能需要一種針對具體成本函數來計算分層的算法。針對鏈路l的成本函數c可以是c(L)=length(L)或者c(L)=length(L)*averageSpeed(L)等。該成本函數可以取決于鏈路的長度和/或該鏈路的速度類別,并且可選地可以考慮諸如隧道、橋梁等屬性。
在圖3中,被分配至級別6的鏈路可以如下計算。圖3所示的外部邊界20表示擴展級別6的分片邊界20。內部邊界22表示級別6的分片T。因此,針對每個級別6的分片T,確定其擴展分片ET的邊界鏈路。如圖3所示,擴展ET邊界可以通過向分片T的每條邊添加級別7的分片進行計算。擴展分片ET的邊界鏈路是級別8的鏈路中與擴展分片ET的邊界相交的那些鏈路。這些級別8的鏈路均以附圖標記24來表示。這些鏈路24例如可以被劃分為兩個集合。例如,鏈路可以被劃分為起始鏈路集合和目的地鏈路集合。起始鏈路集合可以包含去往ET之中的所有邊界鏈路,并且目的地邊界集合可以包含從ET 20離開的所有鏈路。雙向邊界鏈路可以被分配給兩個集合。基于這兩個集合,能夠計算出從起始邊界集合中的所有鏈路到目的地邊界集合中的所有鏈路的最優路線。這些可以是最優路線。最優路線可以基于包含于擴展分片之中的級別8鏈路。分片T中作為最優路線的一部分的所有級別8鏈路可以蔓延至級別6。因此,僅作為其中起始 和目的地鏈路至少處于遠離該鏈路的級別7分片的最優路線的一部分的那些鏈路被包含在級別6中。分片T的級別6鏈路的最終集合由處于從任意級別8起始邊界鏈路到擴展分片的任意級別8目的地邊界鏈路的最優路線上的所有級別8鏈路組成。
在圖3所示的布置中,級別8邊界鏈路24以附圖標記R1至R6來表示。由于除R4和R2以外的所有鏈路都是雙向的,所以起始鏈路集合包括R1、R3、R4、R5和R6。目的地鏈路集合包括R1、R2、R3、R5和R6。在邊界鏈路之間的、級別8上的用于最優路線的鏈路以附圖標記26來表示。如所能夠看到的,級別8上存在鏈路30,而鏈路30并非級別8邊界鏈路的一部分而且也并非在邊界鏈路之間的、級別8上的用于最優路線的級別8鏈路的一部分。如所能夠看到的,具有一些以附圖標記28表示的蔓延至級別6的鏈路。這些鏈路有效地成為級別8上的邊界鏈路之間的最優路線的一部分,但是其處于分片T之內并且因此蔓延至級別6。
現在參考圖4A至H,它們圖示了可以通過一些實施例來解決的問題。特別地,圖4A或4H圖示了可能在第一更新地區UR1被更新但是相鄰的更新地區UR2未被更新的情況下計算路線制定信息所可能出現的問題。考慮圖4A中的初始情形。第一更新地區UR1和第二更新地區UR2經由Q1/2014中的一些次要道路進行連接。
圖4B示出了更新后的情形,其中更新地區UR1和更新地區UR2變為由Q2/2014中新的主要道路進行連接。
圖4C示出了對應于圖4A中所示的情形(即Q1/2014中的情形)的邊緣標志。在該示例中,所有鏈路都可能具有指示該鏈路被用于進入到一些地區之中的一些最優路線的相同的邊緣標志位向量。作為示例,該位向量可以是001100111。
在圖4D中,示出了Q2/2014中的情形,其中假設兩個更新地區都已經被更新。所示出的是,次要道路的邊緣標志向量現在僅包含零值,這指示鏈路并不是去往任何邊緣向量分區的最優路線的一部分。兩個地區之間的所有最優路線現在都使用新的高速公路,并且該新的 主要道路鏈路的邊緣向量現在與關聯于該主要道路的先前的邊緣鏈路相同。
考慮圖4E中所示的情形。特別地,更新地區UR1已經被更新以反映新的道路。然而,更新地區UR2還沒有被更新并且包括Q1/2014的信息。如圖4E中所示,規劃了從第一更新地區UR1中的起點S開始到包含于新的邊緣標志向量中被標記為1的分區之中的目的地的路線。換言之,向量中相應的位是“1”。將期望在更新地區UR1中使用該新的主要路線,但是這將無法延伸至更新地區UR2的路線之中(因為該更新地區還沒有被更新)。UR1中之前的次要道路路線將不再被考慮,因為它們現在與目的地區域的邊緣標志向量中的零值相關聯。因此,在這種情況下將不可能使用邊緣標志找到最優路線。
現在將參考圖4F至4H,它們示出了隨著分層方法而出現的問題。同樣,圖4F示出了Q1/2014中的情形,其中更新地區UR1和更新地區UR2之間的路線僅經由次要道路。圖4G示出了Q2/2014中的情形,其中主要道路現在將更新地區UR1和更新地區UR2相連。在圖4F所示的布置中,該次要道路蔓延至更高的路線制定層,因為它們對于長距離路線制定而言是相關的。在Q2/2014中,僅新的主要鏈路蔓延至高路線制定層中,因為次要道路對于長距離路線制定而言不再重要。最優路線制定現在使用該主要鏈路。然而,考慮圖4H中所示的情形,其中更新地區UR1已經被更新但是更新地區UR2還沒有更新。如能夠看到的,高層上的鏈路現在將不再被連接。更新地區UR1將具有主要道路,而更新地區UR2將具有次要路線。因此,將不可能在兩個不同地區中使用這些高層找到最優路線。
一些實施例可以提供對個體更新地區的增量更新。一些實施例可以使用預先計算的路線制定信息。
現在參考圖5A至5H,它們示出了一些實施例。一些實施例可以解決并避免之前所描述的問題。一些實施例可以允許對不同更新地區進行單獨更新同時仍然允許找到最優路線。
實施例可以與預先計算的路線制定信息一起使用。該預先計算的 路線制定信息可以是任意適當的信息,并且例如可以使用之前所描述的邊緣標志方法和/或鏈路分級方法。
應當意識到的是,圖5A和5B圖示了與圖4A至4B相同的場景。特別地,圖5A示出了Q1/2014中的情形,其中兩個更新地區UR1和UR2被邊界隔開并且這兩個更新地區通過次要道路進行鏈接。
圖5B示出了Q2/2014中的情形,其中已經提供了跨邊界地區將兩個更新地區UR1和UR2進行鏈接的新的主要道路。
現在將參考圖5C、5D和5E,它們圖示了在使用邊緣標志方法的部署的上下文中的實施例。同樣,圖5C與圖4C中相同。考慮圖5D。在Q2/2014中,隨著主要道路的出現,包含該新的主要道路的道路網絡上的邊緣標志將會如下:新的主要道路的邊緣標志將為001100111并且次要道路的邊緣標志將為000000000。
在一些實施例中,可以使用單調增大的邊緣標志。由此,邊緣標志向量中的位并不會從“1”切換到“0”,其允許位以增大方式從0切換到1。在所給出的示例中,這意味著Q2/2014中的次要道路將保持邊緣向量001100111。換句話說,次要道路和主要道路都保持相同的邊緣向量。在一些實施例中,位的值僅可能增大,即值在新的數據庫中從0變為1。可以防止值從1減小到0。例如,一個鏈路在位置i具有值1。在下一次更新中,再次運行編譯并且該計算的結果將為該值在位置i應當為0。在一些實施例中,值“1”得以被保持而并不變為0。因此,位的值在某些位置會增大但是在一些實施例中并不減小。
考慮圖5E所示的場景,其中更新地區UR1被更新但是更新地區UR2并未被更新。現在將從更新地區UR1中的起點S找出最優路線制定。舊的次要道路和新的主要道路都將進行擴展并且由于次要道路連接至UR2,所以仍然能夠找到最優路線。在UR1中,次要道路和主要道路在路線制定期間都將進行擴展。主要道路在圖5E所示的場景中并非有必要被擴展,但是這考慮到了有關更新地區UR2是否已經被更新的不確定性。
現在參考圖5F至5H,它們示出了使用鏈路分級方法的實施例。 圖5F對應于圖4F所示出的內容。利用先前的方法,如果對Q2/2014的鏈路分級進行編譯,則如圖4G中所示,主要道路將不會被包括在內。然而,如圖5G所示,在實施例中,在某個鏈路級別的處于較舊的數據庫中的鏈路將被保持在該級別并且在后續并不被存儲在低鏈路級別之中。在一些實施例中,這將意味著Q2/2014中的次要道路被存儲在它們在Q1/2014中被存儲的相同鏈路級別。因此,如能夠從圖5G所看到的,次要和主要道路現在都被存儲在該鏈路級別。如果僅更新地區UR1進行了更新,則得到圖5H所示的情形。因此,更新地區UR1中的起點S到更新地區UR2中的任何目的地的任何路線計算都將會找出最優路線,這是因為即使在更新地區UR2中還不包括主要路線的情況下次要路線也互相連接。
一些實施例可以具有可能對更新地區進行單獨更新的優點。一些實施例允許使用預先計算的路線制定信息。
在一些實施例中,數據庫編譯的結果可以存儲在數據庫或存儲器地圖之中。例如,來自先前編譯、例如針對Q1/2012的數據,例如可以存儲在關系數據庫中的表格中。
對于邊緣標志(edge flag),這樣的關系可以是舊邊緣標志(永久鏈路ID,方向,邊緣向量)。在這樣的表格中,針對Q1/2014編譯的所有鏈路都會被存儲。
隨后可以執行針對新地區Q2/2014的數據的路線制定網絡的預先編譯。結果可以存儲在新的表格臨時新邊緣標志(永久鏈路ID,方向,邊緣向量)中。為了創建最終的表格新邊緣標志(永久鏈路ID,方向,邊緣向量),可以使用以(偽)SQL描述的以下過程來如下執行:
INSERT INTO NewEdgeFlags
SELECT*FROM NewTempEdgeFlags UNION
SELECT*FROM OldEdgeFlags WHERE PermanentLinkID NOT IN(SELECT PermanentLinkID FROM NewTempEdgeFlags);
UPDATE NewEdgeFlags N,OldEdgeFlags O SET N.EdgeVector=(N.EdgeVector BITOR O.EdgeVector)WHERE  N.PermanentLinkID=O.PermanentLinkID AND N.Direction=O.Direction;
DELETE OldEdgeFlags;
INSERT INTO OldEdgeFlags SELECT*FROM NewEdgeFlags;
表格新邊緣標志將包含針對Q2/2014編譯的最終結果。
邊緣向量可以通過利用新的Q2/2014計算其值來計算,并且隨后在位的級別與Q1/2014中使用的邊緣向量進行OR運算。位的級別上的該OR運算保證了該位絕對不會在新的邊緣中從值1減小為值0,相反該位僅能夠從值0增大為值1。新的結果存儲在舊的表格之中,使得其可用于Q3/2014數據的編譯。
對于鏈路分級(link hierarchy)而言,情形會是相似的。
之前表格的結果被存儲在關系舊鏈路分級(永久鏈路ID,層級)中(與邊緣標志的情形相反,不要求存儲方向,因為只要要求一個方向,鏈路就蔓延至更高級別)。隨后,利用新的數據執行鏈路分級計算,并且其結果被存儲在中間表格臨時新鏈路分級(永久鏈路ID,層級)中。為了創建最終的表格新鏈路分級(永久鏈路ID,層級),可以使用以(偽)SQL所描述的以下過程來如下執行:
INSERT INTO NewLinkHierarchy
SELECT*FROM NewTempLinkHierarchy UNION
SELECT*FROM OldLinkHierarchy WHERE PermanentLinkID NOT IN(SELECT PermanentLinkID FROM NewTempLinkHierarchy);
UPDATE NewLinkHierarchy N,OldLinkHierarchy O SET N.Level=max(N.Level,O.Level)WHERE N.PermanentLinkID=O.PermanentLinkID;
DELETE OldLinkHierarchy;
INSERT INTO OldLinkHierarchy SELECT*FROM NewLinkHierarchy;
MAX算子確保了鏈路絕對不會被存儲在較低級別,即使這是新編譯的結果。因此,可以保證即使在兩個更新地區之一并未更新的情 況下也能夠在某個級別上找到最優路線。
一些實施例可以允許對更新地區進行單獨更新。
在一些實施例中可以使用預先計算的路線制定信息。
一些實施例可以使用更新地區的概念以及預先計算的路線制定信息。
一些實施例除了“新的”編譯的預先計算的信息之外還可以使用來自“舊的”編譯的信息來創建包含預先計算的路線制定信息的新的數據庫。
一些實施例可以針對基于邊緣標志的路線制定方法而在位的級別上應用OR運算。
一些實施例可以針對分級路線制定方法的鏈路級別應用MAX算子。
現在參考圖6,其示意性示出了可以在其中提供一些實施例的系統。該系統包括能夠使用地圖服務的用戶設備101。該用戶設備所需要的地圖信息可以經由通信網絡105從地圖服務平臺103接收。提供保存地圖數據的地圖數據庫109。該地圖數據可以包括如以上所描述的用于一個或多個更新地區的數據以及預先計算的路線制定信息。在該實施例中,地圖服務由地圖服務平臺103提供給用戶設備101。
導航設備可以是獨立設備或裝置,并且因此使得所需的地圖信息被存儲在該設備或裝置自身上。
參考圖7。其示出了實施例可以與其一起來使用的裝置。該裝置包括位置傳感器110。該位置傳感器可以包括能夠獲取與該裝置的位置相關的信息的傳感器。僅作為示例,該位置傳感器可以是衛星定位傳感器,諸如全球定位系統(GPS)傳感器、輔助全球定位系統(輔助GPS)傳感器或者任意其它適當的衛星定位傳感器。應當意識到的是,可替換地或除此之外,該裝置可以以任意其它適當方式獲得位置信息,例如從基站等獲得。
該裝置包括控制器120。在一些實施例中,控制器120包括至少一個處理器。控制器120可以包括路線制定器功能122,其能夠運算 或計算期望的路線。
提供了用戶界面UI 114。用戶界面114例如允許用戶選擇目的地和/或起點。
該裝置包括顯示器112。顯示器112可以被配置為顯示地圖信息,諸如路線和/或區域地圖。在一些實施例中,該顯示器可以是觸摸屏并且因此提供了全部或部分的UI功能。
提供了地圖存儲器114,其被配置為存儲地圖信息。該地圖信息可以包括更新地區和/或預先計算的路線制定信息的至少一部分中的一種或多種。該地圖存儲器可以由一個或多個存儲器提供。
提供了接口118。在用戶設備被配置為隨地圖服務平臺一起工作的示例情形中,接口118將允許該設備例如與通信網絡105進行通信。應當意識到的是,在其它實施例中,該接口可以被提供以允許使用適當方法或裝置對獨立設備進行更新。在一些實施例中,經更新的地圖信息可以被提供至接口118并且被存儲在地圖存儲器114中。
路線制定器122例如可以使用來自位置傳感器110的有關當前位置的信息、有關所需路線的信息以及存儲在地圖存儲器中的信息來計算期望的路線。該期望的路線例如可以被顯示在顯示器112上。
在一些實施例中,路線制定器122所提供的至少一部分路線計算可以在地圖服務平臺103中被提供。
參考圖8,其示出了一種方法。
在步驟S1,輸入針對路線的請求。該路線可以具有起點和目的地。例如,該起點可以被輸入或者可以被假設為裝置的當前位置。
在步驟S2,確定信息可用于該起點和目的地之間的路線。
在步驟S3,在需要的情況下下載地圖信息。這可以例如經由地圖服務平臺103而來自于地圖數據庫109。應當意識到的是,在一些實施例中,步驟S2和S3可以至少部分被省略。在該裝置是獨立設備的一部分的情況下,步驟S2和S3可以被完全省略。
在步驟S4,使用如之前所討論的預先計算的信息來計算該起點和目的地之間的路線。
在步驟S5,從導航設備輸出所計算的路線。該輸出可以包括在顯示器上顯示該路線的至少一部分和/或諸如音頻輸出之類的任意其它適當輸出。
參考圖9,其示出了一些實施例的方法流程。
在步驟T1,確定更新地區已經被修改,特別是在邊界地區中進行了修改,并且例如在表格中存儲舊數據。
在步驟T2,對新的更新地區進行編譯并且例如將其存儲在第二表格中。
在步驟T3,對邊緣信息進行更新以有效保持先前的信息和新的信息,或者如之前所描述的先前的信息的至少一部分。在使用邊緣標志的情況下這可以通過針對舊的表格和新的表格執行OR運算來進行。在使用鏈路級別的情況下這可以是應用MAX算子。
應當意識到的是,在可替換的實施例中,可以與預先計算的路線制定信息的其他方法一起使用。
應當意識到的是,該實施例在圖5中示出并且所概括的情形是作為示例的,并且實施例顯然可以在其它適當場景中使用。
已經關于更新地區對實施例進行了描述。應當意識到的是,其它實施例可以在其中兩個相鄰區域或地區可能在不同時間進行更新的任意其它場景中使用。
在一些實施例中,鏈路的重要性隨著發布的不同而并不出現退化,即使預先計算的路線制定算法希望如此。鏈路重要性由邊緣標志向量中的值1或者該鏈路被存儲于其中的最高級別來反映。換句話說,針對任何鏈路,位絕對不會從值1減小到值0。在分級方法中,鏈路被存儲于其中的最大級別永遠不會降低。
所需的數據處理裝置可以利用一個或多個數據處理器來提供。所描述功能在每個方面都可以由單獨處理器或者集成處理器來提供。該數據處理器可以為適用于本地技術環境的任意類型,并且作為非限制性示例可以包括一個或多個通用計算機、專用計算機、微處理器、數字信號處理器(DSP)、應用特定集成電路(ASIC)、門級電路,以 及基于處理器的多核處理器架構。數據處理可以跨若干數據處理模塊進行分布。數據處理器例如可以利用至少一個芯片來提供。還可以在相關設備中提供適當的存儲器容量。一個或多個存儲器可以為適用于本地技術環境的任意類型,并且可以使用任意適當的數據存儲技術來實施,諸如基于半導體的存儲器設備、磁性存儲器設備和系統、光學存儲器設備和系統、固定存儲器和可移動存儲器。
總體上,各個實施例可以以硬件或專用電路、軟件、邏輯或者它們的任意組合來實施。一些方面可以以硬件實施,而其它方面則可以以固件或軟件來實施,后者可以由控制器、微處理器或其它計算設備來執行,雖然實施例并不局限于此。雖然各個方面可以被圖示并描述為框圖、流程圖或者使用其它一些圖形表示進行圖示,但是將要理解的是,作為非限制性示例,這里所描述的這些模塊、裝置、系統、技術或方法可以以硬件、軟件、固件、專用電路或邏輯、通用硬件或控制器或者其它計算設備,或者它們的一些組合來實施。軟件可以存儲在物理媒體上,諸如存儲器芯片或者在處理器內實施的存儲器模塊,諸如硬盤或軟盤的磁性介質,以及諸如DVD及其數據變化形式、CD的光學介質。
以上描述已經通過示例性而非限制性的示例提供了本發明的示例性實施例的完整且信息性的描述。然而,當結合附圖和所附權利要求閱讀時,各種修改和適配將通過以上描述而對于本領域技術人員是顯而易見的。然而,對于本發明教導的所有這樣和類似的修改都將落入如所附權利要求所限定的本發明的范圍之內。實際上,存在著包括之前所討論的一個或多個任意其它實施例的組合形式的另外的實施例。

關 鍵 詞:
用于 導航 應用 使用 方法 裝置
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:用于在導航應用中使用的方法和裝置.pdf
鏈接地址:http://www.wwszu.club/p-6401740.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大