地圖匹配方法、地圖匹配設備、用於形狀匹配的資料庫、和形狀匹配設備的製作方法

2023-05-14 21:52:06

專利名稱：地圖匹配方法、地圖匹配設備、用於形狀匹配的資料庫、和形狀匹配設備的製作方法
技術領域：
本發明涉及一種地圖匹配方法、用於執行地圖匹配方法的一種設備、以及一種電腦程式。更具體地，本發明專注於能夠以高速執行地圖匹配操作的一種地圖匹配方法、地圖匹配設備、以及電腦程式。而且，本發明涉及用於傳送交通信息提供系統等中的有關交通堵塞、交通事故等的位置信息的一種信息傳送方法，並涉及用於通過使用此信息傳送方法來執行有關位置的信息交換操作的一種設備。特別地，本發明專注於能夠穩定且迅速地傳送數字地圖上的位置的一種形狀匹配目的的資料庫和形狀匹配設備。
背景技術：
傳統上，例如，如下面提到的專利出版物1中所描述的，當車輛導航設備裝有地圖數據時，車輛導航設備以例如1秒的時間間隔執行地圖匹配操作，以識別地圖數據上的移動交通工具的位置。在此地圖數據中，已存儲了所有寬度大於或等於3.3米的道路。當使用被限制到自己的交通工具位置的周圍區域的區域地圖數據作為對象區域時，車輛導航設備執行地圖匹配操作，並由此獲得對應於自己的交通工具位置的地圖上這種點。
作為地圖匹配方法，幾類地圖匹配方法是公知的。例如，宏地圖匹配操作的算法如下定義(1)如圖35(a)所示，當使用由GPS接收器獲得的交通工具位置作為對應於在形狀向量上形成的點的WP(way point-路點)時，搜索位於WP的周邊區域的連結，以便檢測具有由A米(大約250米)構成的正方形內的這種方位的連結，其中將第一路點WP1設置為正方形的中心。通過此方位和交通工具的移動方位之間的差異被限制為+B度到-B度(例如，B近似等於45度)，來定義此連結的方位。接下來，將檢測出的此連結設置為候選點(符號「X」)。因而假定候選點的總連結數(n)被選擇為5到8段。在圖35(b)中，將第一路點WP1的候選點設置為1-1、1-2、1-3。
(2)如圖35(b)中表示的，在由A米構成的正方形內檢測具有這種方位的連結，其中將下一個路點WP2設置為正方形的中心。通過此方位和交通工具的移動方位之間的差異被限制為+B度到-B度，將「n」段連結設置為候選點(2-1、2-2、2-3)。
(3)重複執行此過程操作，直到匹配操作到達了最後的WP。
(4)將各自的候選點沿著道路連結彼此連接，以便形成形狀模型。在候選點沒有沿著道路連接(例如，WP3的候選點3-3和3-2不能沿著道路被連接到接下來的WP4的候選點)的情況中，不形成形狀模型。
(5)當各自的形狀模型與WP1、WP2......的形狀相比較時，選擇和路點的形狀最相似的一個形狀模型。也就是說，此形狀模型位於接近路點的位置，並擁有與WP1、WP2......的形狀有關的小起伏，其通過標準偏差等來評價。
現在假定WP的總數等於「M」段，並獲得每個WP的「N」段候選點作為平均值，在項目(4)中獲得的形狀模型為NM段的組合，通常為幾千到幾萬個形狀模型。
另一方面，本發明的發明者已提出了使用地圖匹配操作的交通信息傳送系統(日本專利申請第2002-89069號)。在此系統中，當沿著道路而改變的交通信息的狀態量(移動時間、以及交通堵塞程度等)利用從表示道路的形狀向量的參考節點來測量的距離的函數來表示時，將此交通信息的數據和表示道路形狀的形狀向量的數據提供給用戶終端。用戶終端通過使用形狀向量來執行地圖匹配操作，以便識別交通信息的目標道路，並從交通信息的數據再現有關此道路的交通信息。
圖36(b)示出了在此系統中傳送的交通信息的數據，而圖36(a)表示與此交通信息數據組合傳送的道路的形狀向量數據。或者，這些數據可被編碼，以便壓縮數據量。圖37(a)和圖37(b)示出了已被編碼的形狀向量數據、以及交通信息數據。在已接收了這些數據的用戶終端對形狀向量數據和交通信息數據解碼之後，用戶終端類似地執行地圖匹配操作，同時將包含於形狀向量數據中的各個節點定義為WP，以便識別交通信息的目標道路，並從交通信息數據再現有關目標道路的交通信息。
在當前可用的交通信息中，當將統一的編號應用到節點和連結時，通過此號碼來識別目標道路。此情況中，需要與道路和路線改變的新近施工操作相結合、關於節點號和連結號的更新操作。由於道路和路線改變的新近施工操作今後不會停止，所以用於使用統一編號的方法必定需要維護的工作負擔。相反，由於通過此交通信息傳送系統中的地圖匹配操作來識別道路位置，所以不需要將這種統一編號應用到節點和連結，並由此可減少工作負擔。
日本公開專利申請第HEI-7-260499號然而，在此交通信息傳送系統中，接收方設備(解碼器；導航設備等)必須執行包含於交通信息中的有關廣闊範圍內(例如，東京行政區的全部區域、或10公裡構成的正方形)的長主題區域(long subject section)的地圖匹配操作。
並且，在地圖匹配操作的處理操作中，在使用上述利用來識別交通工具位置的WP情況中，當大量候選點被形成在WP周圍時，必定需要非常長的時間來為候選點執行檢索處理操作(即上面描述的宏地圖匹配操作的處理操作(1)和(2))。此處理時間與WP的總數成正比地增加。而且，響應候選點的總數和WP的總數，各自候選點之中的組合呈指數增加，並由此，形狀模型的形成處理操作(上面描述的處理操作(4))和比較處理操作(上面描述的處理操作(5))需要大量時間。
結果，有一個目的是減少地圖匹配操作的處理時間。
並且，在這種探測獲取系統中，其中，通過中心來獲得在各種地方駕駛的交通工具(probe，探頭)的駕駛數據，以便利用其以形成交通信息、從大量探頭將表示駕駛軌跡的位置數據收集到一個中心。接下來，此中心通過基於位置數據來執行地圖匹配操作，識別各個探頭沿其駕駛的道路。因而，為了從大量探頭收集的數據可被快速處理，需要高速地圖匹配操作。
並且，安裝有車輛導航機器的交通工具迅速增加。在通過此車輛導航機器使用的交通工具裝載(on-vehicle)的導航系統中，當裝有數字地圖資料庫時，可將自己的交通工具的位置周圍的地圖顯示在屏幕上，並且另外，基於由GPS接收器接收的緯度/經度數據，可將移動軌跡和直到目的地點的路線搜索結果顯示在地圖上。
應當注意，數字地圖資料庫可能包含由減小比例的地圖的致命方面而造成的錯誤。當取決於數字地圖資料庫、錯誤程度彼此不同時，例如，存在可以商業使用的數字地圖資料庫，其具有1/25000的縮小比例，依照地點，包含大約50米的錯誤。
並且，在此交通工具裝載的導航機器中，接收從交通信息提供系統提供的諸如交通堵塞信息和交通事故信息的交通信息，並隨後可將交通堵塞地點和交通事故位置顯示在地圖上，並且/或者通過將這些交通堵塞/事故信息添加到條件中來執行路線搜索操作。
在上面描述的交通信息提供系統中，如圖57中所表示的，從控制局部區域的控制中心71將交通信息供應到交通信息發布中心72，並隨後將已為了各種媒介(FM廣播、道路上的信號燈、便攜電話等)的目的而編輯的交通信息通過這些各種媒介來傳送。還應當理解，控制中心71與另一個局部區域的控制中心78傳遞交通信息，並由此獲得包含周邊地區的廣闊地帶內的交通信息。
對於由上面說明的交通信息提供系統供應的交通信息，例如，在這種情況中，即單獨地提供有關交通堵塞位置和交通事故位置的緯度/經度數據，以通知交通堵塞位置和交通事故位置，此時存在這種風險，即如果交通信息提供源和交通信息提供的目的地使用不同種類的數字地圖資料庫，那麼交通工具裝載的導航機器將道路上的不同位置識別為交通事故位置。這是由於，如前面說明的，取決於交通工具裝載的導航機器裝有的數字地圖資料庫的種類，這些數字地圖資料庫含有彼此不同的誤差。
為了改正這種信息傳送操作或信息顯示操作的錯誤，交通工具裝載的導航系統使用圖58中示出的這種地圖信息。如圖58(a)中的一個例子所表示的，假定現在道路網絡的交叉點「a」和「b」對應於節點，而節點之間的道路「c」對應於連結，將節點號(a＝1111，b＝3333)設置到各自節點，其專門來表示這些節點，而將連結號(c＝11113333)設置到各自連結，其專門來表示此連結。接下來，已與各自交叉點和各自道路相關地設置的節點號和連結號已被存儲在數字地圖資料庫中，其中該數字地圖資料庫由與節點號和連結號有聯繫的各種廠商上市銷售。
並且，對於表示交通堵塞位置、交通事故位置等的交通信息，為了表示道路上的位置，識別出連結號，並隨後通過這種表示來表示道路上的點，其中，將此點從通過此連結號表示的道路的開頭部分隔開特定的米數(距離)。例如，在這種情況中，其中交通信息包含[從連結號＝「11113333」的道路的開頭部分相隔200米的位置]，即使當交通工具裝載的導航機器使用任意類型的數字地圖資料庫時，也可通過跟蹤與具有由連結號「11113333」定義的道路的節點號「1111」的節點相隔200米的這個位置，來獲得相同道路上的位置，即由交通信息表示的位置。
然而，如圖58(b)所示，對於已在道路網絡中定義的節點號和連結號，如果道路「d」為新施工的，並且改變了道路，則必須用新號碼來替換這些號碼。當節點號和連結號改變時，各種廠商的數字地圖數據必須更新。
對於將來來說，由於不斷地執行道路的施工和道路的改變，所以為了執行數字地圖資料庫的維護操作，必定永久地需要許多工作量和大量費用，直到還利用通過節點號和連結號來實現的傳統的道路位置顯示方法。因此，存在這種問題，即此維護操作增加，並造成沉重的負擔。
存在基於由交通信息提供中心72提供的交通信息、利用形狀匹配系統(也將被稱為「地圖匹配系統」)來識別道路的另一種方法。此形狀匹配系統可能在很大程度上依賴於在接收方提供的交通工具裝載的導航機器的處理性能。對於在傳統的交通工具裝載的導航機器中執行的地圖匹配操作，由於僅需要關於自己的交通工具位置周圍的有限區域(通常，幾百米的正方形)內的一個地點的地圖匹配操作，所以匹配處理操作可以每秒鐘執行一次。另一方面，關於將在交通信息提供系統中處理的路線(道路)，通常，有很多諸如高速路、國道、以及主要地方道路的道路。此外，在城市區域中，屬於日本的行政區一般道路和城市道路的一部分被包括於這些路線中。而且，存在獲取現有連結之外的路線的信息增加的一些可能性。
因而，傳統的交通工具裝載導航機器的信息處理能力具有這種問題，即需要大量時間，直到基於接收的交通信息通過執行形狀匹配操作來識別出道路、並隨後顯示交通信息。
已為解決這些問題而做出了本發明，並且本發明的目的在於，提供一種能夠實現高速處理操作的地圖匹配方法，並且，提供實現此地圖匹配方法的一種設備和電腦程式。此外，本發明的另一個目的在於，提供一種形狀匹配目的的資料庫和一種形狀匹配設備，其能夠在地圖上提供位置信息，同時不為地圖資料庫執行過多的維護操作。並且，本發明的另一個目的在於，提供一種形狀匹配目的的資料庫和一種形狀匹配設備，其能夠快速地顯示、或表示與道路相關的信息，如交通信息。

發明內容
為此，根據本發明的地圖匹配方法，對於具有對應於地圖匹配操作的目標道路的頻率上非均勻的條件的道路網絡，響應該頻率而設置優先級順序；基於該優先級順序來限定與目標道路匹配的道路網絡；並且，當不能獲得與目標道路的形狀向量匹配的候選道路時，放鬆基於優先級順序作出的限定，以便擴大與目標道路匹配的道路網絡的範圍。
並且，當使用包括已被施加不同權重的一組道路網絡的一組地圖道路網絡數據時，在開始階段中，將權重相對較大的這種道路網絡與表示目標道路的形狀的形狀向量匹配；並且，當不能在權重相對較大的道路網絡中獲得與形狀向量匹配的這種候選道路時，由於權重相對較小的道路網絡已被加到該道路網絡的道路網絡與形狀向量匹配，因而識別出目標道路。
並且，當使用這種道路網絡數據時，其中在多個分層(hierarchical layer)中形成道路網絡，並且上級分層的道路網絡通過從具有比具有上級分層的道路網絡低的下級分層的道路網絡中提取的道路網絡來建立，在開始階段中，相對上級分層的道路網絡與表示目標道路的形狀的形狀向量匹配；並且，當不能在相對上級分層的道路網絡中獲得與形狀向量匹配的這種候選道路時，由於具有更低級的分層的道路網絡與形狀向量匹配，因而識別出目標道路。
通過這些配置的使用，在大多情況中，在使用具有較高優先級順序的道路、具有大權重的道路、或具有最上級分層的道路網絡的地圖匹配操作中，可識別出目標道路，並由此，可以高速執行地圖匹配操作。
並且，根據本發明，接收設備包括數字地圖；地圖匹配目的道路網絡數據，其由已從數字地圖形成的道路網絡建立，並形成在多個分層中，並且，其中，已從具有下級分層的道路網絡提取了具有上級分層的道路網絡；數據接收單元，用於接收包含表示目標道路的形狀的形狀向量的數據；以及地圖匹配單元，用於通過使用道路網絡數據來執行形狀向量的地圖匹配操作，以便識別目標道路；其中，在開始階段，地圖匹配單元將形狀向量與具有道路網絡數據的最上級分層的道路網絡進行匹配；並且，當不能在具有最上級分層的道路網絡中獲得與形狀向量匹配的候選道路時，由於地圖匹配單元將形狀向量與具有另一分層的道路網絡匹配，因而識別出目標道路。
通過使用此配置，可通過執行地圖匹配操作來迅速識別包含於接收信息中的目標道路。
並且，根據本發明，事件信息提供設備包括數字地圖；地圖匹配目的道路網絡數據，其由已從數字地圖形成的道路網絡建立，並形成在多個分層中，並且其中，已從具有下級分層的道路網絡提取了具有上級分層的道路網絡；地圖數據信息傳送單元，用於發布數字地圖和道路網絡數據；形狀向量數據產生單元，用於通過使用數字地圖的數據，來產生表示事件信息的目標道路的形狀的形狀向量；形狀向變形(deforming)單元，用於執行用於指定道路網絡數據的分層的信息添加到形狀向量數據產生單元所產生的形狀向量的處理操作；以及事件信息傳送單元，用於傳送包含由形狀向量變形單元處理的形狀向量的事件信息。
通過使用此配置，由於接收方設備通過使用具有地圖匹配目的道路網絡數據的指定分層的道路網絡，來執行地圖匹配操作，其中所述地圖匹配目的道路網絡數據從事件信息提供設備發布，所以，可快速且正確地識別出事件信息的目標道路。
並且，根據本發明，事件信息提供設備包括數字地圖；平行移動相似形狀計算單元，用於計算平行移動相似形狀連結，其與連結相平行地移動，並具有與來自數字地圖的數據的連結相似的形狀；形狀向量數據產生單元，用於通過使用數字地圖的數據，來產生表示事件信息的目標道路的形狀的形狀向量；形狀向量變形單元，用於以下面這種方式執行形狀向量的變形處理操作，其中，形狀向量變形單元通過使用平行移動相似形狀計算單元的計算結果，來識別關於目標道路的連結中是否存在平行移動相似形狀連結；並且當存在平行移動相似形狀連結時，形狀向量變形單元延伸目標道路，直到這種位置，即平行移動相似形狀連結的形狀能夠與目標道路的形狀相區分的位置；以及事件信息傳送單元，用於傳送包含由形狀向量變形單元處理的形狀向量的事件信息。
通過使用此配置，在已接收了事件信息的接收方設備中，當通過使用具有上級分層的道路網絡來執行地圖匹配操作，以識別出候選道路時，即使與候選道路相似的平行移動相似形狀道路出現在了具有較低分層的道路網絡中，也可通過將這些形狀相互比較，來清楚地作出使用候選道路的決定。
並且，根據本發明的電腦程式，該程序使計算機執行一個序列，其中，當使用由在多個分層中形成的道路網絡建立的道路網絡數據、並且其中已從具有下級分層的道路網絡提取了具有上級分層的道路網絡時，在具有最上級分層的道路網絡和表示目標道路的形狀的形狀向量之間執行匹配操作；並且，當不能在具有最上級分層的道路網絡中獲得與形狀向量匹配的候選道路時，由於形狀向量與具有另一分層的道路網絡匹配，因而獲得目標道路的候選道路；一個序列，其中，當可以獲得與形狀向量匹配的候選道路時，作出關於與目標道路相平行地移動、並且具有與其相似的形狀的平行移動相似形狀道路，是否存在於具有比其中可以獲得候選道路的道路網絡的分層低的分層的道路網絡中的判定；一個序列，其中，當存在平行移動相似形狀道路時，將形狀向量的形狀、候選道路的形狀、以及平行移動相似形狀道路的形狀彼此相比較，以判定關於候選道路的使用是否可被接受；以及一個序列，其中，當不能判定候選道路的使用可被接受時，通過使用具有比已經從其獲得候選道路的道路網絡的分層低的分層的道路網絡，來重新執行對於形狀向量的匹配操作。
通過使用這種配置，可通過執行地圖匹配操作來迅速且正確地識別出目標道路。
在根據本發明的形狀匹配資料庫中，在這種情況下，即通知數字地圖上的道路位置，這種形狀匹配目的資料庫具有多個分層，並且其中，道路網絡通過每個分層中的節點和連結來表示，所述資料庫包括具有節點和連結的最上級分層，其表示最重要的道路；以及各個層，基於表示道路的節點和連結的重要特點，其從最上級分層到下級分層被順序地細分；其中，通過使用各個層來限制應當從道路網絡進行形狀匹配的節點和連結。由此，可捕獲應當由形狀匹配操作處理的節點和連結，以使得總處理速度可以增加。
並且，在根據本發明的形狀匹配設備中，如權利要求26中所述的，用於通過使用形狀匹配目的資料庫和形狀向量、來執行形狀匹配操作的這種形狀匹配設備通過形狀匹配設備從最上級分層執行形狀匹配操作來配置；在可在最上級分層中成功完成形狀匹配操作、並可識別出節點和連結的情況中，完成處理操作；在不能識別對應於形狀向量的節點和連結的情況中，將形狀匹配操作轉移到下級分層，並執行形狀匹配操作；以及用於形狀匹配操作的對象被順序地轉移到下一分層，以便執行形狀匹配操作。由此，可執行也與表示非常狹窄的道路的節點和連結相關的形狀匹配操作。
並且，在根據本發明的形狀匹配設備中，當在多個分層之間提供公共節點時，將形狀匹配操作的對象從公共節點轉移到下一分層，並將各個分層中的形狀匹配操作的結果通過公共節點彼此耦接，以便執行形狀匹配操作。由此，可容易地執行分層之間的轉移操作，並且可將數據容易地彼此耦接。
並且，在根據本發明的形狀匹配設備中，如果以下面這種方式來實現這種道路識別方法，其中當將標識符應用到也在上級層中定義的連結時，通過使用標識符，將形狀匹配操作轉移到上級層，以便執行形狀匹配操作，則可在其中連結和節點在粗略條件下配置的層中迅速地執行形狀匹配操作。
並且，在根據本發明的形狀匹配設備中，在下面這種情況中，其中匹配操作在預定的分層中失敗，而利用表示地點的絕對位置，如果形狀匹配操作被順序地轉移到下級分層、以便執行形狀匹配操作，那麼在各個分層中執行的該匹配操作可以以簡單的方式彼此耦接。並且，當存儲這種地圖資料庫時，如果使用這種伺服器，其響應於預定的信號，而傳送位置或所有地圖數據，那麼大量的人可容易地使用地圖資料庫。
並且，在形狀匹配目的資料庫中，上級層變得越高，則使形狀向量的節點總數越粗糙。
並且，在形狀向量傳送伺服器中，形狀向量傳送伺服器將權利要求26或權利要求31中所述的形狀向量目的資料庫存儲在其中，並響應於預定的信號，而傳送部分或所有形狀向量。
並且，在根據本發明的形狀匹配設備中，當在上級層中執行形狀匹配操作時，通過使用有關連結長度的信息，從節點串中削減(thin)節點，以成為形狀向量；並且，通過使用削減的節點串，執行形狀匹配操作。由此，可實現較高速度的處理操作。
此外，在根據本發明的形狀匹配設備中，當將諸如道路種類和收費道路碼的這種附加信息加到形狀向量時，如果通過使用附加信息選擇了首先被形狀匹配的這種分層，那麼可以避免對於所有分層從最上級分層執行形狀匹配操作的這種無用處理操作。


圖1為用於表示根據本發明的第一實施例的數字地圖數據的數據結構的圖。
圖2為用於示意性地示出根據本發明的第一實施例的具有分層結構的地圖匹配目的的道路網絡的圖。
圖3為用於表示根據本發明的第一實施例的具有分層結構的地圖匹配目的的道路網絡數據的數據結構的圖。
圖4示出了表示道路形狀的列印的數字地圖。
圖5為用於描述根據本發明的第一實施例的地圖匹配操作的順序操作的流程圖。
圖6為用於表示根據本發明的第一實施例的傳送方設備的配置和接收方設備的配置的方框圖。
圖7為用於表示根據本發明的第一實施例的順序操作的流程圖，其中在所允許的高度的上級層中執行地圖匹配操作。
圖8為用於表示平行移動相似形狀道路的圖。
圖9為用於表示以其半程截斷的平行移動相似形狀道路的圖。
圖10為用於示出根據本發明的第一實施例的地圖匹配目的的道路網絡數據的數據結構的圖，其中平行移動相似形狀道路存在/不存在信息已被加到所述道路網絡數據。
圖11為用於表示在交點處彼此沒有連結-連接(link-connect)的平行移動相似形狀道路的圖。
圖12是根據本發明的第一實施例，用於表示其中添加了平行移動相似形狀道路存在/不存在信息的地圖匹配目的道路網絡數據的圖。
圖13為用於示出根據本發明的第一實施例、通過將形狀彼此比較的錯誤匹配操作的可能性判斷序列。
圖14為用於將已通過形狀向量和地圖匹配操作識別出的道路的形狀與平行移動相似形狀道路相比較的圖。
圖15為用於示出這種條件的圖，其中平行移動相似形狀道路僅存在於部分區域內。
圖16為用於表示根據本發明的第二實施例的跨越多個分層的目標道路的圖，其中所述多個分層應當由地圖匹配方法處理。
圖17為用於示出根據本發明的第二實施例的在地圖匹配操作中設置的層間連結節點的圖。
圖18為用於說明根據本發明的第二實施例的在地圖匹配操作中設置的層間連結節點的定義的圖。
圖19為用於說明根據本發明的第三實施例的在地圖匹配操作中定義的推薦跳躍距離的圖。
圖20為用於說明根據本發明的第三實施例的在地圖匹配操作中定義的用於指定特徵部分的推薦跳躍距離的圖。
圖21為用於表示根據本發明的第四實施例的地圖匹配目的的道路網絡數據的圖。
圖22為用於描述根據本發明的第四實施例的地圖匹配操作的處理序列的流程圖。
圖23為用於示意性地示出根據本發明第四實施例的地圖匹配操作的圖。
圖24為用於示出根據本發明第五實施例接收的形狀向量數據的圖。
圖25為描述用於根據本發明的第五實施例、在地圖匹配操作中確定候選點搜索範圍的順序操作的流程圖。
圖26為用於表示根據本發明第六實施例、具有分層結構的道路網絡數據的更新順序操作的流程圖。
圖27為用於示意性地示出根據本發明的第七實施例、用於產生在地圖匹配操作中利用的高速緩衝存儲器層的數據的順序操作的圖。
圖28為表示根據本發明的第七實施例、在地圖匹配操作中利用的高速緩衝存儲器層的數據的數據結構的圖。
圖29為用於表示在地圖匹配操作中命中(hit)的連結的圖。
圖30為表示根據本發明的第八實施例的用於發布具有分層結構的道路網絡數據的傳送方設備的圖。
圖31為用於表示根據本發明的第八實施例、通過傳送方設備傳送的形狀向量數據的數據結構的圖。
圖32為用於表示根據本發明的第八實施例、用於調節目標道路區段的傳送方設備的配置的方框圖。
圖33為描述根據本發明的第八實施例、用於提取平行移動相似形狀的順序操作的流程圖，其中該操作由傳送方設備執行。
圖34為用於說明根據本發明的第八實施例、傳送方設備的形狀向量產生順序操作的流程圖。
圖35為用於表示傳統的宏地圖匹配操作的處理順序操作的圖。
圖36為用於示出提供有用於目標道路的形狀向量的交通信息的數據結構的圖。
圖37為用於表示交通信息的數據結構的圖，其中已經與要提供的目標道路的形狀向量相結合地對所述交通信息編碼。
圖38為用於表示根據本發明的第十實施例的地圖匹配操作的處理順序操作的流程圖。
圖39為用於表示根據本發明的第十實施例、在地圖匹配操作中使用的地圖數據的圖。
圖40為用於說明根據本發明的第九實施例、具有分層結構的道路網絡數據的產生順序操作的流程圖。
圖41為用於表示根據本發明的第九實施例、具有分層結構的道路網絡數據的產生機制的圖。
圖42為用於表示將本發明的分層結構應用到信息交換系統的情形的圖。
圖43為表示用於基於形狀匹配操作來傳送/接收事件信息的系統的配置的圖。
圖44為用於表示事件信息的結構的例子。
圖45為用於表示連結的信息格式的圖。
圖46為用於示出節點的信息的圖。
圖47為用於表示形狀向量數據的圖。
圖48為用於示出被傳送的形狀向量的圖。
圖49為用於表示基於分層的形狀匹配操作的示意圖。
圖50為示出用於說明基於分層的形狀匹配操作的處理流程操作的圖。
圖51為用於表示在使用分層公共節點的情況中、基於分層的形狀匹配操作的示意圖。
圖52為用於表示在使用分層公共節點的情況中、被傳送的形狀向量的圖。
圖53為用於表示在使用具有分層標識符的連結的情況中、被傳送的形狀向量的圖。
圖54為用於表示在使用具有分層標識符的連結的情況中、基於分層的形狀匹配操作的示意圖。
圖55為用於表示在使用具有分層標識符的連結的情況中獲得的匹配操作結果的圖。
圖56為示出在節點具有分層信息的情況中、用於描述基於分層的形狀匹配操作的處理流程操作的圖。
圖57為用於表示現有技術中的交通信息提供中心的圖。
圖58為示出用於識別節點和連結的傳統思想的圖。
應當注意，附圖中示出的附圖標記如下所述10 接收方設備；11 數據接收單元；12 表示事件信息的形狀向量資料庫；14 地圖匹配單元；15 顯示單元/事件信息利用單元；16 數字地圖B資料庫；17 地圖數據信息接收單元；30 傳送方設備；31 數據傳送單元；32 表示事件信息的形狀向量資料庫；33 特徵節點提取/形狀向量變形單元；34 形狀向量數據表示信息產生單元；35 數字地圖A資料庫；36 事件信息資料庫；37 地圖數據信息傳送單元；38 分層結構道路網絡數據；39 平行移動相似形狀計算單元；40 平行移動相似形狀資料庫；113 分層結構道路網絡數據；116 數字地圖數據A；Ps 開始連結；Pe 結束連結；Pc 普通連結；Ps 開始連結；81 數據傳送單元；82 表示事件信息數據的形狀向量；83 特徵節點提取/形狀向量變形單元；84 形狀向量表示信息產生單元；85 事件信息數據；
86 地圖資料庫；87 傳送設備；88 接收設備；241 上級分層；242 中級分層；261 上級層；262 中級層；263 連結；264 連結；265 連結；具體實施方式
(第一實施例)在本發明的第一實施例中，作出有關本發明的地圖匹配方法的基本概念方案的描述。
執行地圖匹配操作的接收方設備擁有如圖1所示的這種數字數據。在此地圖數據中，描述了有關節點和連結的信息，其位於由首標定義的區域內。節點信息包含節點總數、各個節點的節點號、各個節點的節點屬性信息、各個節點的緯度和經度，並且，還有有關被連接到各個節點的連接節點和連接連結的信息。並且，連結信息包含連結總數、連結號、表示連結的道路種類的屬性信息、定義連結形狀的插值點總數、以及有關各個插值點的緯度和經度的信息。
應當理解，節點號、連結號、以及插值號已由此地圖數據的製造者獨立地設置，但不具有有關另一個地圖數據製造者形成的那些地圖數據的共有特點。
接收方設備形成具有用於基於此地圖數據的地圖匹配操作的分層結構的道路網絡數據。
圖2表示此分層結構的道路網絡數據的示意性方案。在此圖中，表示了三層分層結構的例子。並且，圖3表示每個分層的道路網絡數據的例子。圖2(c)對應於分層結構的最下層的道路網絡數據，有關所有道路網絡的數據包含於其中。此最下層的此道路網絡數據的例子表示在圖3(c)中。此道路網絡數據對應於類似於圖1的這種地圖數據。圖2(b)對應於中級層的道路網絡數據，其僅包含這種道路，其道路寬度大於或等於5.5米。圖3(b)中表示此道路網絡數據。圖2(a)對應於僅包含大於或等於主要地方道路的主路線道路的道路網絡數據。圖3(a)中示出了此道路網絡數據。
上級層、中級層、以及下級層的道路網絡數據的數據格式彼此相同。也應當注意，節點號、連結號、以及插值點號被對於上級層所允許地、最大地削減。對於節點號，直接使用在最下層中應用的這種號碼，作為上級層中對應的節點的號碼。對於連結號，優選應用對於各個層的連結唯一的這種號碼，以使得這些唯一連結號在所有層中不會重複。
還應當注意，儘管在此例子中已示範了三層分層結構，但可將分層的總數選擇為大於或等於3。
圖6示出了接收方設備10的配置和傳送方設備30的配置。接收方設備10裝有具有此分層結構的道路網絡數據。傳送方設備30將交通信息和道路形狀的形狀向量數據提供到接收方設備10。
傳送方設備30配有資料庫36、另一個資料庫35、形狀向量數據表示信息產生單元34、特徵節點提取/形狀向量變形單元33、形狀向量表示事件信息資料庫32、以及數據傳送單元31。資料庫36將諸如交通信息的事件信息存儲在其中。資料庫35將數字地圖A存儲在其中。形狀向量數據表示信息產生單元34產生事件信息，其中通過使用資料庫35和36的數據，通過形狀向量數據來表示目標道路。特徵節點提取/形狀向量變形單元33將交叉道路的部分形狀加到特徵節點位置處的形狀向量數據，以避免錯誤匹配操作，並校正相對距離。形狀向量表示事件信息資料庫32將已產生的形狀向量數據和事件信息數據存儲在其中。數據傳動單元31傳動這些數據。從數據傳送單元31傳送圖36中示出的數據或圖37中示出的數據。
另一方面，接收方設備10裝備有數據接收單元11、形狀向量表示事件信息資料庫12、地圖匹配單元14、資料庫16、以及顯示單元/事件信息利用單元15。數據接收單元11接收數據。形狀向量表示事件信息資料庫12將接收的數據存儲在其中。地圖匹配單元14通過使用具有分層結構的道路網絡13來執行地圖匹配操作，以識別目標道路。資料庫16將數字地圖B存儲在其中。顯示單元/事件信息利用單元15顯示並利用事件信息。
還應當注意，可通過使此接收方設備10的計算機執行由電腦程式定義的處理操作，來實現地圖匹配單元14。
先前通過使用資料庫16的數字地圖B來產生分層結構的道路網絡數據13(將在後面說明其中的產生順序操作)。並且，接收方設備10的資料庫16中裝有的數字地圖B的製造者不同於傳送方設備30的資料庫35中裝有的數字地圖A的製造者。
並且，顯示單元/事件信息利用單元15將交通堵塞地點顯示在地圖上，並通過考慮交通堵塞來搜索路線，同時使用目標道路的交通信息。
圖5的流程圖表示這種情況中的地圖匹配操作的處理順序操作，其中裝有此分層結構的道路網絡數據13的接收方設備10從傳送方設備30接收目標道路的形狀向量數據。
當接收方設備10接收目標道路的形狀向量數據時，接收方設備10執行地圖匹配操作，同時使用所能允許的高的上級層的道路網絡數據，並且將包含於形狀向量數據中的節點用作WP(步驟1)。其中具體的順序操作將在後面描述。作為地圖匹配操作的處理操作自身，使用諸如宏地圖匹配方法的方法，其已為傳統上公知的。
層變得越高，道路網絡便變得越粗略，以使得位於WP周圍的候選點的總數較小，並且，可以高速執行地圖匹配處理操作的處理操作。
另一方面，通常，交通信息的主題路線對應於高速路(快速路)、國道、以及主要地方道路(注意，屬於日本的行政區的重要通用道路和有關城市道路部分的交通信息也在城市區域中提供)。通過使用上級層的道路網絡數據、可在地圖匹配操作中識別出目標道路的概率非常高。
如果出現這種情況，其中，不能通過使用上級層的道路網絡數據識別出目標道路(例如，在不能設置候選點的情況中)，通過使用下級的道路網絡數據來重新執行地圖匹配操作。
並且，即使在可通過利用上級層的道路網絡數據來執行地圖匹配操作識別出該目標道路的情況中，當出現平行移動的目標道路時，仍有執行錯誤匹配操作的一些可能性。
例如，在圖4中，現在假定粗實線和粗鏈狀線對應於主要地方道路；點狀線對應於屬於日本行政區的道路；並且位於上述線之間的道路對應於使用中的道路，其寬度短於或等於5.5米；最上級層的道路網絡數據僅包含粗實線和粗鏈狀線，而點狀線包含於中級層的道路網絡數據和最下層的道路網絡數據中，並且使用中的道路僅包含於最下級層的道路網絡數據中。
在通過使用最上級層的道路網絡數據的地圖匹配操作可以識別出粗鏈狀線的情況中，即使當通過使用中級層的道路網絡數據和最下層的道路網絡數據來執行地圖匹配操作時，也不能識別出被粗鏈狀線取代的這種道路。
然而，在通過使用最上級層的道路網絡數據的地圖匹配操作中可識別出粗實線的這種情況中，有一些可能性。也就是說，如果通過使用中級層的道路網絡數據來執行地圖匹配操作，那麼會識別出點狀線。並且，如果通過使用最下級層的道路網絡數據來執行地圖匹配操作，則會識別出相對於粗實線和點狀線平行移動的使用中的道路。換句話說，在將粗實線確定為目標道路、其中該目標道路已在使用最上級層的道路網絡數據的地圖匹配操作中定義的這種情形中，有引起錯誤匹配操作的出現的某種可能性。
由此，作出有關可能在識別出的道路的周邊區域處被錯誤地地圖匹配的這種道路是否出現在下級層的道路網絡數據中的判斷(步驟2)。將在後面討論此判斷的具體的順序操作。
在出現了可能被錯誤地地圖匹配的這種道路的情況中，將已通過使用上級層的道路網絡數據而定義的道路確定為目標道路(步驟6)。
並且，在出現了可能在識別出的道路的周邊區域處被錯誤地地圖匹配的這種道路的這種情況中，執行對於形狀向量的形狀比較操作，以檢查有關識別出的道路是否正確地對應於目標道路(步驟4)。將在後面說明此形狀比較操作的具體方法。
基於此形狀比較操作的結果，作出有關已被基於上級層的道路網絡數據識別出的道路作為目標道路是否正確的判斷(步驟5)。如果此識別出的道路為正確的，則將識別出的道路確定為目標道路(步驟6)。另一方面，當不能判斷識別出的道路作為目標道路是正確的時，通過使用下級層的道路網絡數據來重新執行地圖匹配操作(步驟7)。
如前面所說明的，這種情形——在已通過使用上級層的道路網絡數據來執行地圖匹配操作之後，通過使用下級層的道路網絡數據來重新執行地圖匹配操作——可能使上級層中執行的處理操作變得無用，並可能使處理效率與從開始階段即在下級層中執行地圖匹配處理操作的這種情況中相比而較低。然而，在上級層中可成功完成地圖匹配操作、此外沒有出現可能被錯誤地地圖匹配的平行移動的道路的情況中，可能立即完成處理操作。由此，在幾十到幾百個地圖匹配處理操作中獲得的總性能中，這種順序操作擁有優點，其中，上級層的道路網絡數據的地圖匹配操作依照圖5的順序操作而開始。
圖7示出了圖5的步驟1中定義的處理順序操作的例子，即其中以高級層中所允許的高度執行地圖匹配操作的處理順序操作。
將在地圖匹配操作中使用的道路網絡數據的分層設置為最高級(層號＝1)(步驟10)。當目標道路的形狀向量數據的節點被設置為WP時，執行地圖匹配操作(步驟11)。
基於WP和所選形狀模型的候選點之間的距離誤差和方位誤差來計算評價值(步驟12)。例如，根據下面提到的公式來計算評價值評價值Φ＝{∑(α·Lj+β|θj-θj′|)}/S在此公式中，符號「Lj」表示WP(j)和候選點(j)之間的距離；符號「θj」表示WP(j)的絕對角度；符號「θj′」表示候選點(j)的絕對角度；符號「S」示出形狀模型的距離；並且符號「α」和「β」為係數。
可成功完成候選點的設置，並作出有關候選點的評價值是否被限定在定義值之內的判斷(步驟13)。當候選點的評價值被限定在定義值之內時，基於所選的形狀模型來定義目標道路(步驟14)。
並且，在步驟13中，當不能成功完成候選點的設置、或候選點的評價值超過了定義值時，作出有關使用的道路網絡數據的分層是否對應於最下層的區分(步驟16)。當所述分層對應於最下層時，假定地圖匹配操作失敗，並隨後完成處理操作(步驟17)。
並且，在步驟16中使用的道路網絡數據的分層不對應於最下層的這種情況中，通過使用其層號減小1的這種道路網絡數據，來重複執行從步驟11定義的順序操作。
由於執行了這種順序操作，所以可在所允許的高級的高級層中執行地圖匹配操作。
接下來，作出圖5的步驟2的判斷處理操作的描述。
為了可作出有關可能被錯誤地地圖匹配、並且位於上級層中識別出的目標道路的周邊區域處的這種道路是否出現在下級的道路網絡數據中的判斷，之前添加屬性信息(平行移動相似形狀屬性)，作為對上級分層的道路網絡數據的連結信息。屬性信息表示有關是否存在平行移動形狀道路。平行移動的道路暗示了相似形狀的道路，在此說明書中，其角度差異小於預定的角度。通常說來，可通過使用已在上級層的相關道路上設置的多個WP的一項或多項、多個WP和鄰接道路上對應的最近點之間的距離和方位差異、最近點之間的連接特性、以及路線距離來產生有關平行移動相似形狀屬性的信息。下面給出詳細的說明為了評價有關平行移動相似形狀道路是否出現在上級層的每個連結中，(1)如圖8所示，沿著上級層的連結(插值點之中的中心點，並以固定長度為單位)，適當地設置「WP(Pj)」。
(2)將垂直線從每個WP(Pj)繪出到包含於下級層中的「n」段周邊道路上，以便在各個周邊道路上設置候選點Pnj′，並隨後根據下面提到的公式來計算對每個周邊道路的評價值評價值Φ＝{∑(α·Lnj+β|θj-θnj′|)}/S在此公式中，符號「Lnj」表示WP(Pj)和候選點(Pnj′)之間的距離；符號「θj」表示WP(Pj)的絕對角度；符號「S」示出連結長度；並且符號「α」和「β」表示係數。
為了評價有關上級層的連結的平行移動相似形狀道路的出現，有關周邊道路的此評價值小於或等於恆定值的這種條件為必要條件。
(3)為了評價有關上級層的連結的平行移動相似形狀道路的出現，這種條件——周邊道路上的候選位置(Pnj-1′)和候選位置(Pnj′)對於所有的「j」來說是相連接的——為必要條件。如圖9中所表示的，在對應於上級層的連結的周邊道路的部分被截斷的這種情況中，由於未出現錯誤匹配操作，所以從用於平行移動相似形狀道路的對象導出此周邊道路。
(4)為了評價有關上級層的連結的平行移動相似形狀道路的出現，這種條件——對於周邊道路上的所有「j」，有關候選位置(Pnj-1′)和候選位置(Pnj)之間的最短路線的偏差絕對值的累計值小於或等於恆定值，並且此外，兩點之間的路線距離WP(Pj-1)到WP(Pj)基本彼此相等——為必要條件。另一方面，即距離(Lnj)的波動小於或等於恆定值的這種條件。
因而假定如果以與門(AND-gating)條件的方式處理上面描述的條件(2)、(3)、(4)，並且滿足所有這些條件，則對於上級層的連結，存在平行移動相似形狀道路。
如圖10(a)中所表示的，作為各個連結的屬性信息，將連結的平行移動相似形狀屬性添加到道路網絡數據，並且如圖10(b)中所表示的，在道路網絡數據中描述平行移動相似形狀道路的存在/不存在(即，存在/存在部分區域/不存在)。
並且，將這種信息「上遊/下遊(up-stream/down-stream)方交叉點處的連接(存在/不存在)」添加到平行移動相似形狀屬性。此信息表示有關此平行移動相似形狀道路是否連接到了彼此相鄰、並且在上遊和下遊的連結中的交叉點處的平行移動相似形狀道路。從此信息可以捕獲對於上級層的各個連結而存在的平行移動相似形狀道路是否彼此相連接。如果平行移動相似形狀道路沒有彼此相連接，則可作出這種判斷，即沒有出現錯誤匹配操作的風險。例如，如圖11所示，在這種情況中，即對應於自身連結(qj)的下遊側的相鄰連結(qj+1)的相似形狀連結(qj+1′)沒有在交叉點處連接到自身連結(qj)的相似形狀連結(qj′)，此時不存在上級層的道路被錯誤地與下級層的平行移動相似形狀道路匹配的風險。
由於連結的這種平行移動相似形狀屬性先前被添加到了道路網絡數據，所以，可如下執行圖5的步驟2中定義的處理操作也就是說，可從道路網絡數據做出對識別出的道路區段中的各個連結的平行移動相似形狀屬性的參考，其中已使用所述道路網絡數據，以便在步驟1中定義目標道路。
接下來，在這種情況中，即平行移動相似形狀存在於大於或等於此道路區段的部分的區段內，並且，此外也存在交叉部分的連接，此時可作出這種判斷，即「在下級層中，有相似形狀道路存在於其鄰近位置的某些可能性」。在其它情況中，因而被判斷為「否」。
應當注意，可替換地通過考慮錯誤匹配操作的出現比率、以及在上面描述的項(2)中計算的評價值「Φ」來執行此判斷。
還應當注意，用於評價平行移動相似形狀道路的存在的評價值「Φ」也可從另一個公式計算。
或者，當評價平行移動相似形狀道路的存在時，可應用模型匹配操作的算法。
接下來，作出有關圖5的步驟4中定義的形狀比較操作的例子的描述。
為了容易地執行此形狀比較操作，相關連結的形狀和表示平行移動相似形狀道路的形狀的代表值，即「形狀代表值」包含於連結的平行移動相似形狀屬性中，其被添加到道路網絡數據。
使用下面提到的值作為此形狀代表值·「偏角(declination)累計值」如圖8中所表示的，現在假定平行移動相似形狀道路上的位置等於Pj′(j＝1到N)，其對應於以上級層的連結上的相等距離排列的WP(pj)(j＝1到N)，通過在WP(Pj)(j＝1到N)處將偏角彼此相加，來獲得連結的偏角累計值，並且，通過在位置Pj′(j＝1到N)處將偏角彼此相加，來獲得平行移動相似形狀道路的偏角累計值。
·「偏角絕對值累計值」通過在WP(Pj)(j＝1到N)處將偏角絕對值彼此相加，來獲得連結的偏角絕對值累計值，並且，通過在位置Pj′(j＝1到N)處將偏角絕對值彼此相加，來獲得平行移動相似形狀道路的偏角絕對值累計值。
·「關於上級層的相關道路(平行移動道路)的波動」通過WP(Pj)和位置Pj′之間的距離Lj(j＝1到N)的標準偏差來表示此波動。
另外，可使用頻譜等。
圖12示出了道路網絡數據，其中已將這種信息添加到平行移動相似形狀屬性，並且此外，關於每個平行移動相似形狀道路，已將下面提到的項加到其中。也就是說，連結的偏角累計值、連結的偏角絕對值累計值、以及平行移動相似形狀的總數已被加到平行移動相似形狀屬性。此外，這些項對應於相似形狀評價值((2)的評價值「Φ」)；分層；道路屬性；全部/部分區分，用於表示有關此平行移動相似形狀是否出現在部分連結、或連結的整個部分中；偏角累計值；偏角絕對值累計值；有關連結的波動；上遊方交叉點處的連接/非連接；以及有關每個平行移動相似形狀道路的連接部分的偏角絕對值累計值(最小值)。
圖13表示通過使用此道路網絡數據來執行圖5的步驟4和步驟7中定義的處理操作的情況中、詳細的順序操作。
當提及來自道路網絡數據的各個連結的平行移動相似形狀屬性、其中已使用所述道路網絡數據以便在步驟1中識別目標道路時，在這種情況中，即平行移動相似形狀道路存在於識別的道路區段的一部分或其整個區段中，計算出形狀向量的形狀代表值(步驟41)。這些連結包括在識別的道路區段中。
接下來，從道路網絡數據中讀出在地圖匹配操作中識別的道路區段的形狀代表值、以及包含於連結道路屬性信息中的道路種類。並且，從道路網絡數據中讀出平行移動相似形狀道路的形狀代表值和道路種類，並隨後將讀取的這些形狀代表值和道路種類與形狀向量的形狀代表值和道路種類相比較(步驟42)。
在此比較操作中，當形狀向量的道路種類與在地圖匹配操作中識別的道路區段的道路種類相一致、且不同於平行移動相似形狀道路的道路種類時，評價沒有出現錯誤匹配操作的可能性(步驟5)。並且，如果僅基於道路種類不能作出評價，則比較形狀代表值。在這種情況中，即通過地圖匹配操作識別的道路區段擁有與平行移動相似形狀道路相比、對於形狀向量更小的形狀差異，則評價沒有出現錯誤匹配操作的可能性(步驟5)。
並且，當形狀向量的道路種類與在地圖匹配操作中識別的道路區段的道路種類不一致時，或在這種情況中，即儘管道路種類與形狀向量的道路種類一致，平行移動相似形狀道路擁有對於形狀向量較小的形狀差異，判斷有出現錯誤匹配操作的可能性。從此道路種類和形狀代表值判斷存在相關平行移動相似形狀道路的最上層，並隨後選擇此最上層。當存在此相關平行移動相似形狀道路的層不清楚時，選擇最下層(步驟71)。
當使用所選層的道路網絡數據時，重新執行形狀向量的地圖匹配操作(步驟72)，以便識別目標道路(步驟73)。
如前面所說明的，由於此方法可直接識別「如果出現錯誤的地圖匹配，則屬於該分層的道路是相關的」，可通過使用直接識別的分層的道路網絡數據、而不總是使用需要較長處理時間的最下層，再次執行匹配操作。因此，可較高效率地執行重新計算。
例如，在圖14的例子中，現在假定形狀向量為(1)；在地圖匹配操作中識別的上級層的路線區段為(2)；並且，出現在下級層中的平行移動相似形狀道路為(3)，當作出關於(1)、(2)、(3)的偏角累計值和偏角絕對值累計值的計算時，並且當計算形狀(1)和形狀(2)之間的波動、以及形狀(1)和形狀(3)之間的波動時，產生下面的結果·偏角累計值(1)幾乎等於(2)、幾乎等於(3)、幾乎等於0度。
·偏角絕對值累計值180度，幾乎等於(1)、幾乎等於(3)，不等於(2)，其幾乎等於0度。
·形狀(1)和形狀(2)之間的波動幾乎等於形狀(1)和形狀(3)之間的波動。
可以看出，通過簡單地將這些值彼此比較，可能被錯誤匹配的這種道路被定位於第三層。
還應當注意，對於步驟41中的形狀向量的形狀代表值的計算，在這種情況中，即當壓縮了形狀向量時，以相等距離來重新對形狀向量採樣，並且在傳送方設備中，對偏角以可變長度編碼，接收方設備可簡單地對接收的數據計算偏角累計值和偏角絕對值的累計值。
並且，在平行移動相似形狀道路存在於部分區域內的情況中，採用圖15中示出的這種模式。在此情況中，假設平行移動相似形狀道路必須在某個交叉點處被合併入相關道路。換句話說，假設平行移動相似形狀道路必須在某個地點彎曲。由此，在步驟42中，研究有關詳細的部分的形狀。接下來，當可以判斷形狀向量的形狀不具有和平行移動相似形狀道路一樣的這種彎曲、而具有近似於主道路的形狀的形狀時，在大多數情況中，地圖匹配操作的重新執行不再需要基於下層的道路網絡數據。
另一方面，在這種情況中，即平行移動相似形狀道路存在於整個區域中，此時，在大多數情況中，實踐上難以僅基於形狀來限定形狀向量對應於主道路，並且需要通過使用下層的道路網絡數據來重新執行地圖匹配操作。
為此，當傳送方設備識別交通信息的目標道路時，採用某種思想。在這種情況中，即存在平行移動相似形狀道路，此時，如果以這樣方式，即此平行移動相似形狀道路可能成為「平行移動相似形狀道路存在於部分區域中」，來選擇目標道路的區段，則接收方設備可否定基於步驟42的處理操作的錯誤匹配操作的可能性，並且在大多數情況中，不需要在下層中重新執行地圖匹配操作。
並且，在這樣的情況中，即作出有關直接到上遊的道路與直接到下遊的道路相合併的判斷，此時，僅對於一方道路執行地圖匹配操作，而省略對另一方道路的地圖匹配操作，可以以較高的效率來執行處理操作。
如前所述，根據此地圖匹配方法，可高速、正確地識別目標道路。尤其是，類似於交通信息的目標道路，在不均勻的情形出現在包括於道路網絡內的目標道路中的道路中的情況中，此地圖匹配方法可達到較大效果。
並且，對於從探測獲取系統的探頭(移動的交通工具)傳送的移動軌跡，由於這種關係「A主道路擁有大交通量。如果交通量較大，則上行連結頻率也較高」，所以在包括在道路網絡內的目標道路中的道路中存在不均勻的情形。由此，由於將此地圖匹配方法應用於探測獲取系統，所以可達到巨大的效果。
並且，如圖10(a)或圖12所示，當用戶選擇的頻率和統計信息(例如，由季、年、月、日、時間、以及天氣因素造成的交通堵塞或凍結)被添加到包含於首標信息中的分層號信息時，為了進一步縮短地圖匹配操作所需要的處理時間，可通過使用此信息來替換地預測道路可能成為特定主題(subject)的可能性的變化。
在此情況中，當未選擇預測的道路網絡時，基於包含在圖10(a)中示出的首標信息中的常規分層信息來執行地圖匹配操作。
或者可基於下面提到的道路屬性確定分層道路網絡的各個分層的道路·道路種類高速路/國道/主要地方道路/屬於日本的行政區的道路/城市道路/窄城鎮道路。
·道路號碼應用於各個道路種類的號碼，國道246→246，轄區道路407路線→407。
·收費/免費關於道路是否為收費道路的區分。
·道路模式主道/輔道/通信道路(IC部分等)/環島等，其表示道路的功能。
·用於提供交通信息的路線先前已被識別為交通信息提供主題路線的路線、VICS連結目標道路。
(第二實施例)在本發明的第二實施例中，作出圖5的步驟1中定義的處理操作中的改進的描述，即在這種處理操作中的改進，即在所允許的最高級的高級層中執行地圖匹配操作。
由於具有分層結構的道路網絡數據已被初始分類，以被形成在接收方設備裝有的地圖數據的帳戶上，所以傳送方設備通常不能獲得這種項目，即哪個道路區段包含於此分層結構的上級層中、以及哪個道路區段包含於其下級層中。由此，有一些這種可能性，即上級層的道路區段與從傳送方設備傳送的單個形狀向量內的下級層的道路區段相混合。
在這種情況中，例如，即使當接收方設備通過使用上級層的道路網絡數據來開始地圖匹配操作、並命中滿足條件下的半程道路中的候選點時，當出現下級層的道路區段的形狀向量時，接收方設備也不能每次都立即獲得候選點，使得接收方設備通過使用下級層的道路網絡數據，從開始部分重新開始地圖匹配操作。更具體地說，在下面這種情況中，此問題可能變得顯著，此情況即傳送方設備30(圖6)的特徵節點提取/形狀向量變形單元33將交叉道路的形狀的一部分(稱為「小鬍子(mustache)」)添加到形狀向量數據，以避免錯誤匹配操作並且校正相對距離。
圖16中表示了此狀態。在傳送方設備傳送形狀向量數據Pa→Pb的情況中，此傳送方設備將Ps→Pa和Pb→Pe添加到其中，作為小鬍子，並將Ps→Pa→Pb→Pe這種形狀向量數據傳送到接收方設備。
然而，儘管Ps→Pa→Pb的區段包含於接收方設備的上級層的道路網絡數據中，但另一部分Pb→Pe不包含於此道路網絡數據中。結果，當通過使用上級層的道路網絡數據開始地圖匹配操作時，命中候選點，直到Ps→Pb的區段，但不能在Pb→Pe的區段中獲得候選點，使得必須通過使用下級層的道路網絡數據來重新執行地圖匹配操作。
為了改進這種低效率的方面，在此實施例中，當在上級層中不再能夠命中候選點時，將地圖匹配操作轉移到下級層。
為實現此操作，將下面提到的數據設置到各個分層的道路網絡數據。
如圖17所示，將用於轉移到低一級分層的層間連結節點設置到除了最下級層之外的每個分層的道路網絡數據，並且，通過此層間連結節點來分割連結一次。由於層間連結節點不是交叉點，所以連接連結僅為一個連結。在圖17中，將層間連結節點設置到這種位置，即交叉點位於降低一層的分層。然而，不總是將層間連結節點設置在交叉點上，是不必要的，而可能將其設置到任意地點。
應當理解，由於連結被分割這種事實使得性能被破壞，所以以這種方式來設置層間連結節點，即層間連結節點之間的距離長於或等於預定的距離。
·出現的最上層號碼(例如，對於屬於日本行政區的通用道路，由於最上層號碼出現在2層以下，所以設置「2」)，作為每個連結的屬性信息，被設置到包含最下級層的各個層的道路網絡數據。
當接收方設備通過使用上級層的道路網絡數據來開始地圖匹配操作、並在滿足條件下命中候選點時，此接收方設備連續使用上級層的道路網絡數據。當接收方設備未能搜尋到候選點時，地圖匹配操作回到最近層間連結節點這種位置，其中地圖匹配操作已通過了該節點。接下來，將上級層的道路網絡數據傳送到下級層的道路網絡數據，並通過使用下級層的道路網絡數據，從此位置連續執行地圖匹配操作。
由於設置了上面說明的層間連結節點，所以通過使用上級層的道路網絡數據來執行的處理操作不會成為無用的，以便可以高效率執行地圖匹配操作。
還應當注意，如圖18(a)所示，在交叉點的情況中，正常條件下，「層間連結節點」不是必須需要的。現在假定，在僅包含粗實線的上級層的地圖匹配操作中，候選點的搜索操作可在WP(A)中成功完成，而候選點的搜索操作已在WP(B)中失敗，如果地圖匹配操作最終回到候選點的搜索操作可成功完成的WP(A)，並將上級層的地圖匹配操作轉換為下級層的地圖匹配操作，則可連續執行下級層中的地圖匹配操作。
然而，在如圖18(b)中表示的這種情況中，在僅包含粗實線的上級層的地圖匹配操作中，當候選點的搜索操作可在WP(A)中成功完成、而候選點的搜索操作已在WP(B)中失敗時，即使地圖匹配操作回到WP(A)，並且將上級層的地圖匹配操作轉換為下級層的地圖匹配操作，在上級層中通過地圖匹配操作匹配的道路也不能被連接到在下級層中通過地圖匹配操作而匹配的道路。在這種情況中，需要清楚「用於連接到下級層的道路網絡的點在哪裡」，並由此，這可扮演層間連結節點「C」的角色。
並且，在此情況中，如果地圖匹配操作沿著正確的方向返回直到與層間連結節點C分離的點，並且將上級層的地圖匹配操作轉換為下級層的地圖匹配操作，則可將通過下級層的地圖匹配操作匹配的道路連接到下級層的道路網絡。由此，取代設置這種層間連結節點C，沿著正確的方向返回直到與層間連結節點C分離的點的距離可被設置到每個連結(插值點之中的連結等)，作為「當將地圖匹配操作轉換為下級層時的返回距離」。
(第三實施例)在本發明的第三實施例中，作出用於在圖5的步驟1中定義的處理操作中、在上級層中高效地執行地圖匹配操作的方法的描述。
在這種情況中，即通過使用上級層的道路網絡數據來執行地圖匹配操作，由於平均連結長度較長，所以可將節點設置到WP，其中已經以一定間隔、從形狀向量的構造節點列將所述WP選出。
因此，在第一方法中，在使用上級層的道路網絡數據的情況中，通過使用這種節點作為WP來執行地圖匹配操作。已從例如形狀向量的構造節點列、每「N」段選擇了所述節點。如上所述，由於所述節點從形狀向量被削減(跳躍)，以便作為WP使用，所以WP的總數減少，並且可縮短地圖匹配操作的處理時間。通過考慮形狀向量的平均連結長度和偏角來設置削減節點的比率。或者，可在N個節點的單元中提取一個節點作為WP，或者在固定距離的單元中提取一個節點。
換句話說，與分層的特性相對應地削減節點。作為具體削減方法，每N個節點削減節點一次，或者，每個機械檢測(mechanical sense)中的固定距離削減節點一次。或者，可在高級削減方法中的分層類型數據中設置「跳躍距離」。
並且，在第二方法中，當從形狀向量削減節點時所選的WP之間的距離間隔先前被設置為與上級層的連結相對應的推薦跳躍距離，並且，被定義為上級層的道路網絡數據的連結信息。
如在圖19中所表示的，此推薦的跳躍距離如下設置也就是說，從每個插值點或連結的中心點查看地圖匹配方向(即在從下遊一方執行地圖匹配操作的情況中的上遊方向)，在下一個節點對應於交叉節點的情況中，基於從每個插值點或連結的中心點直到此交叉節點的近似距離，來設置此推薦的跳躍距離。並且，從每個插值點或連結的中心點查看地圖匹配方向，在下一個節點對應於層間連結節點的情況中，基於從每個插值點或連結的中心點直到下一個連結的中心點的近似距離，來設置此推薦的跳躍距離。
在通過使用上級層的道路網絡數據來執行地圖匹配操作的情況中，根據在連結信息中定義的推薦跳躍距離，從形狀向量的構造節點列削減節點，並且，選擇用作WP的這種節點。
由此，由於候選點搜索操作的總時間減少，並且模型號碼的總數減少，所以可縮短地圖匹配操作所需的處理時間。
還應當理解，當使用這種方法時，其中，在形狀向量的壓縮期間以相等距離來對節點重新採樣、並以可變長度對偏角編碼，此時，由於形狀向量的節點之間的距離變為相等距離，所以有可能簡單地執行通過沿著形狀向量的指定距離來跳躍節點。
並且，在第三方法中，以這種方式指定推薦跳躍距離，即可在「產生相關層的連結的形狀特徵的地點(＝較好的被檢查地點)」之前和之後設置WP。
如圖20中所表示的，在此第三方法中，在通過上級層的道路網絡數據表示的連結形狀擁有特徵的曲柄形狀的情況中，以將WP設置到此曲柄形狀的位置的方式、基於道路網絡數據的連結信息來指定推薦跳躍距離。
可基於每單位連接區段的偏角累計值的大小和每單位連接區段的偏角絕對值累計值的大小，來判定連接形狀中的特徵部分。
如先前說明的，由於將WP設置到產生連結形狀的特徵的地點，所以，即使WP被削減，也可以捕獲連結的特徵，並且可以通過地圖匹配操作、以正確的方式識別連結。
並且，甚至當相關連結的形狀沒有特徵時，也可基於推薦跳躍距離、替換地指定這種地點(＝較好的被檢查地點)，即平行移動相似形狀道路擁有特徵的地點。在此替換情況中，如果通過形狀向量的地圖匹配操作、選擇此連結作為候選點，則有可能判定下級層的平行移動相似形狀道路不對應於目標道路。
(第四實施例)在本發明的第四實施例中，通過將第一實施例和第二實施例與第三實施例結合、作出用於在圖5的步驟1中定義的處理操作中、在上級層中高效地執行地圖匹配操作的方法的描述。
圖21表示此實施例中的道路網絡數據(分層結構的部分)。在此道路網絡數據中，包含了在第二實施例中說明的作為連結信息的、有關「當前道路的最上層號碼」和「當將地圖匹配操作轉移到下級層時的返回距離」的數據，並且，還包含有關在第三實施例中說明的「推薦跳躍距離」的數據。
並且，圖22的流程圖表示此實施例中的地圖匹配方法。圖23示意性地示出了此地圖匹配方法。在此情況中，流程圖表示道路網絡數據的分層結構對應於2層，並且，對形狀向量以此順序Ps→Pa→Pb→Pa→Pd→Pe、從下遊向上遊進行地圖匹配。
在此方法中，首先，開始關於位於最下級層中的終點WP(Ps)的周邊部分處的候選點的搜索操作(步驟51)。在最下級層中的短區段內執行地圖匹配操作，以便獲得多個候選點(步驟52)，並隨後識別此層號碼(步驟53)。如前面說明的，地圖匹配操作從最下級層開始的原因為避免開始點處的致命的錯誤匹配操作。
確定下一個WP，並搜索候選點(步驟54)。在地圖匹配操作的開始階段，將鄰接點選擇為下一個WP。當重複執行候選點搜索操作、並隨後在相同層號處繼續候選點搜索操作時，通過參考推薦跳躍距離來確定下一個WP。
作出有關下一個WP中的候選點搜索操作是否可以成功的檢查(步驟55)。在這種情況中，即候選點搜索操作可以連續地成功完成，並且進一步，也將相關道路定義在上級層中，此時，將地圖匹配操作轉移到上級層(步驟56)。如果所有WP仍未完成(在步驟59中「否」的情況中)，則重複執行從步驟54定義的順序操作。並且，當結束了所有WP時(在步驟59中「是」的情況中)，完成處理操作。
並且，在候選點搜索操作失敗(在步驟55中「否」的情況中)的情況中，作出有關候選點搜索操作是否連續失敗的檢查(步驟57)。如果候選點搜索操作沒有連續失敗，則使要搜索的WP返回，直到層間連結節點的位置，或直到當將地圖匹配操作轉移到下級層時的返回距離，並隨後將上級層的地圖匹配操作轉移到下級層(步驟58)。接下來，當沒有結束所有WP時(在步驟59中「否」的情況中)，重複執行從步驟54定義的順序操作。
並且，當候選點搜索操作連續失敗時(在步驟57中「是」的情況中)，作出開始點的分層不正確的判斷，並由此，再次獲得識別的分層。
在圖23的例子中，由於Ps的地圖匹配操作從下級層開始，並且可連續地成功完成候選點搜索操作，所以將下級層的地圖匹配操作轉移到上級層，並隨後在上級層中執行Pc→Pd→Pe的地圖匹配操作。然而，由於Pe的候選點搜索操作失敗，地圖匹配操作返回，直到層間連結節點Pc的位置，並且將地圖匹配操作轉移到下級層。接下來，在下級層中執行Pd→Pe的地圖匹配操作。
如先前說明的，由於在具有分層結構的多層的道路網絡數據之中執行地圖匹配操作，所以，可以多次執行基於上級層的有效地圖匹配操作，以便可以縮短用於地圖匹配操作的處理時間。
(第五實施例)在本發明的第五實施例中，作出確定用於響應於形狀向量的錯誤情況的地圖匹配操作的候選點搜索操作的範圍的方法的描述。
在地圖匹配操作中，如果用於應用WP的形狀向量的誤差小，則候選點搜索操作的範圍可以被變窄，而如果形狀向量的誤差大，則候選點搜索操作的範圍可以被變寬。如先前說明的，響應於WP的錯誤、可變地設置候選點搜索操作的範圍，而不是以固定方式設置，使得可以適當地設置搜索範圍。並且，可較高效率地執行地圖匹配操作中的處理操作。
形狀向量數據的誤差元素包含用於由傳送方設備形成形狀向量數據的基礎地圖數據的精度；有意地使地圖數據變形、以避免錯誤的匹配操作的變形量(在日本公開專利申請第2001-132610號中描述)；當編碼的形狀向量數據以不可逆方式壓縮時的形狀變形可允許誤差(在日本公開專利申請第2001-132611號中描述)等。
如圖24中表示的，傳送方設備將上述信息傳送到接收方設備，同時上面說明的信息包含於作為「形狀向量的基礎地圖精度信息」、「當作出變形、以避免錯誤匹配操作時的最大變形量」、以及「在不可逆壓縮操作期間的最大可允許誤差」的形狀向量數據中。
基於上述信息，接收方設備可響應於形狀向量的誤差條件、而設置候選點搜索操作的範圍。
圖25的流程圖表示響應於此形狀向量的誤差條件、有關候選點搜索範圍的設置順序操作。
從形狀向量數據流獲得基礎地圖的精度信息(A)(步驟20)。接下來，從形狀向量數據流獲得當作出變形以避免錯誤匹配操作時的最大變形量(B)(步驟21)。接下來，從形狀向量數據流獲得在不可逆壓縮操作期間的最大可允許誤差(C)(步驟22)。從這些獲得的(A)、(B)、(C)確定候選點搜索操作的範圍(步驟23)。
例如，現在假定這種基礎地圖精度信息「傳送方的基礎地圖為1/25000」已被輸入到了形狀向量，並且另一方面，接收方設備的地圖數據的精度等於「1/2500」，最大有大約70米的位移。
並且，如果在用於避免錯誤匹配操作的變形中存在最大為10米的位移，則通過將此位移和由基礎地圖精度造成的誤差相結合，產生最大80米的這種位移。
並且，現在假定，當以不可逆方式壓縮形狀向量時，設置最大10米的可允許誤差，通過由基礎地圖精度造成的誤差和用於避免錯誤匹配操作的變形相結合，產生最大90米的位移。由此，可在半徑為90米的範圍內找出候選點。由此，儘管候選點搜索操作的範圍傳統上已被固定到大約250米，但仍能夠以更適當的方式設置本發明的搜索範圍。
(第六實施例)在本發明的第六實施例中，作出用於基於接收信息、順序優化道路網絡數據的分層結構的方法的描述。
實際上說，將用於接收交通信息的道路區段確定到某個範圍。由此，基於數據接收時間、匹配結果等來更新已在預設設置操作中設置的、具有分層結構的道路網絡數據，並由此，可順序地將此道路網絡數據優化為適合於接收環境的、具有分層結構的道路網絡數據。
例如，在這種情況中，即當已接收了交通信息10次時，包括在上級層中的道路區段僅適合於目標道路1次到2次，此時，從上級層中刪除該道路區段。由於執行了這種數據重新排列操作，所以，上級層的道路網絡數據變得精簡，使得可高速地執行地圖匹配處理操作。
並且，對於在開始階段中、僅包含於下級層的這種道路區段，如果此道路區段作為目標道路出現的這種頻率較高，則將此道路區段包含於上級層中。將傳感器等重新設置到道路、並隨後提供此道路的交通信息的這種情況可對應於上面說明的情況。由於執行了分層結構的優化處理操作，所以增加了在上級層中的命中率，並且可高速地執行地圖匹配操作。
並且，如先前在第二實施例和第四實施例中說明的，在單個形狀向量內的目標道路跨越多個分層的情況中，以上面描述的方式識別目標道路。當提供交通信息的頻率高時，通過順序優化分層結構，可將此目標道路的所有區段包括於上級層中。
現在將描述此優化的處理順序操作。
首先，將關於交通信息的接收次數的交通信息的出現概率定義為對分層結構的每層的目標命中率。
例如，將關於過去幾十個項目的接收次數的出現概率設置如下第一層關於接收次數的出現概率高於或等於80％，第二層關於接收次數的出現概率為80到50％，第三層關於接收次數的出現概率為50到10％，第四層關於接收次數的出現概率低於10％。
接下來，根據圖26(a)中示出的順序操作，當接收了交通信息時，通過執行地圖匹配處理操作來識別目標道路(直到識別出目標道路的順序操作與圖7的順序操作相同)。當將命中數目計數器設置到識別出的目標道路時(步驟18)，計算已被定義為目標道路的道路區段。
當使用此計數值時，根據圖26(b)中示出的順序操作，以離線處理模式順序執行分層結構的優化操作。
基於接收次數和命中數目計數器的計數值，計算出道路區段單元中的命中率(步驟80)。
在接收次數達到預定次數的情況中，將各個道路區段重新排列為這種分層，即其命中率與目標命中率相一致，並且各個分層的道路重新彼此組合，並由此，更新具有分層結構的道路網絡數據。接下來，設置接收次數和命中數目計數器(步驟81)。
或者，在此情況中，當準備了地圖匹配處理目的的文件和更新操作目的的文件時，可分別利用用於執行地圖匹配處理操作的數據和背景中要被更新的數據。當完成了更新處理操作時，可切換分別使用這些文件。
由於執行了這些處理操作，所以能夠與接收環境相一致地優化各個層的道路網絡。
還應當注意，當增加/刪除網絡時，可應用滯後(hysteresis)，以使得在目標命中率的邊界的臨近處不出現擺動(hinting)現象。例如，在出現概率變為小於或等於75％的情況中，從第一層中刪除網絡，而在出現概率超過85％的情況中，在第一層中增加網絡。
由於安裝在道路上的傳感器進入故障狀態，有交通信息的提供暫時停止的某種可能性。由此，即使在關於快速路、國道等的這種情況中，可將這種識別標誌「絕對不被刪除」應用到快速路、國道等，以使得這些快速路和國道的道路網絡不會從上級層中刪除。
並且，當交通工具在目的地點接收交通信息時，提供關於此目的地點周圍的道路狀況的詳細交通信息，並且提供關於與此目的地點遠離的道路狀況的粗略的交通信息。由此，當更新各個層的道路網絡時，可替換地以這種方式降低分層，即道路密度在接近自己的交通工具的位置的道路區段內增加，而替換地以這種方式增加分層，即道路密度在遠離自己的交通工具的位置的道路區段內減小。
另一方面，由於從信號燈類型傳送器傳送的交通信息的詳細內容不同於從廣播類型傳送器傳送的內容，所以，可替換地管理取決於交通信息傳送媒介而彼此不同的具有分層結構的道路網絡數據。
或者，可基於交通信息的傳送源ID(廣播站號碼TOKYO·KANAGAWA轄區等)、以及信息源ID(國家警察署(National Police Office)·大都會高速路協會(Metropolitan Highway Institute)等)來管理具有不同的分層結構的道路網絡數據。
並且，在探測信息獲取系統的情況中，更新中心所持有的具有分層結構的道路網絡數據，同時使用每單位時間的命中數目和所有接收的軌跡數據內的命中概率，作為參數。
並且，在此情況中，由於特徵根據日(day)的種類(工作日/假日/第5日、第10日/周六)和時間範圍而變化，所以，可取決於日的種類和時間範圍、交替地管理具有分層結構的道路網絡數據。
如先前說明的，地圖匹配設備基於從幾次過去的地圖匹配操作中獲得實際的匹配結果，知曉那個道路區段擁有較高的命中率，並隨後基於此知曉結果來順序更新具有分層結構的道路網絡數據。由此，地圖匹配設備可減少這種無用處理操作，即當分層改變時執行地圖匹配操作、以及/或者當執行地圖匹配操作時，在半程中切換分層。
(第七實施例)在本發明的第七實施例中，作出用於利用高速緩衝存儲器區域作為具有分層結構的道路網絡數據的最上級層的方法的描述。
在此方法中，如在圖27中示意性地示出的，將已在各個層中被命中的連結(層間連結節點之中的連結)複製在高速緩衝存儲器區域中，並隨後，使用此高速緩衝存儲器區域的道路網絡作為最上層。
圖28表示此時具有分層結構的道路網絡數據。圖28(a)示出了上級層的道路網絡數據，圖28(b)表示下級層的道路網絡數據，而圖28(c)表示高速緩衝存儲器層的道路網絡數據。
現在，如在圖29中示出的，當命中了連結SK2時，其中SK2通過這種方式定義，即地圖匹配操作從下級層的節點K2開始，併到達節點S，此時，將有關連結SK2的連結號碼和連結信息，節點K2和節點S的節點號碼、屬性信息、緯度/經度，以及下級層的道路網絡數據(圖28(b))的這些節點之中的連接信息複製到高速緩衝存儲器層的道路網絡數據中(圖28(c))。如果作為形狀代表值的這種信息和平行移動相似形狀道路形狀屬性包含於連結信息中，則將所有上述信息複製到高速緩衝存儲器層。還應當注意，必須再次計算推薦跳躍距離等。
每次將數據複製到高速緩衝存儲器層時，計算高速緩衝存儲器層的道路網絡數據(圖28(c))的節點號碼和連結號碼，以便被更新。
並且，當命中圖29中示出的從上級層的節點S到另一個節點J1定義的另一個連結SJ1時，將有關連結SJ1的連結號碼和連結信息，節點J1和節點S的節點號碼、屬性信息、緯度/經度，以及上級層的道路網絡數據(圖28(a))的這些節點之中的連接信息複製到高速緩衝存儲器層的道路網絡數據(圖28(c))中。
由於通過使用安裝在道路上的傳感器來獲得交通信息的信息，所以，在實際情況中，每次在目標道路區段內提供基本相同的交通信息。由此，由於使用已經以上述方式複製的高速緩衝存儲器層的道路網絡數據作為最上級層，儘管當在系統剛初始化之後、第一次接收交通信息時的地圖匹配處理操作較慢，但仍可以快速執行第二次地圖匹配處理操作和後續的地圖匹配處理操作。
(第八實施例)在本發明的第八實施例中，描述了傳送方設備為了高速地執行地圖匹配操作所做出的貢獻。
在已描述的各個實施例中，當在接收方上準備了分層結構的道路網絡數據時，通過使用此道路網絡數據來執行地圖匹配操作。或者，可實現另一個模式，其中傳送方設備將分層結構的道路網絡數據發布到接收方設備。
圖30表示此傳送方設備30的配置和此接收方設備10的配置。傳送方設備30配備有地圖數據信息傳送單元37。地圖數據信息傳送單元37將分層結構的道路網絡數據38、以及已存儲在資料庫35中的數字地圖A發布到接收方設備10。並且，接收方設備10配備有地圖數據信息接收單元17，其接收這些地圖數據信息。接收方設備10通過使用從傳送方設備30接收的、具有分層結構的道路網絡數據113和數字地圖數據A116，來執行地圖匹配操作和事件信息的利用。其它配置與第一實施例(圖6)中的那些配置相比沒有改變。
此傳送方設備30將這種信息包含在通過事件信息傳送單元31被傳送到接收方設備10的形狀向量數據中。此信息用於識別在地圖匹配操作中使用的道路網絡數據的分層。
圖31(a)表示形狀向量數據，其中，分層號碼和道路屬性信息(道路種類等)已被加到所述形狀向量數據中，作為形狀向量單元中的此分層識別信息。圖31(b)示出了形狀向量數據，其中，分層號碼和道路屬性信息(道路種類等)已被加到所述形狀向量數據，作為節點單元中的此分層識別信息。或者，只有分層號碼可被僅表示為分層識別信息。並且，當基於道路屬性來確定道路網絡數據的每個分層的道路時，只有道路屬性可以僅被表示。
當接收方設備10的地圖匹配單元14執行這些形狀向量數據的地圖匹配操作時，地圖匹配單元14通過使用在分層識別信息中表示的分層的道路網絡數據113，來執行地圖匹配操作。
在此情況中，由於地圖匹配單元14可通過直接使用其中已包含由形狀向量表示的目標道路的分層的網絡數據，來執行地圖匹配操作，所以，完全不用顧及關於另一個分層的平行移動道路，並由此可高速地處理地圖匹配操作。
或者，應當理解，可將「分層信息」和「道路屬性信息」輸入到索引首標信息的附加信息中。
並且，如在第一實施例中說明的，即使在目標道路中出現平行移動相似形狀道路的情況中，如果以這種方式選擇目標道路區段，即此平行移動相似形狀道路在部分區域內平行移動，則在大多數情況中，接收方設備在形狀檢查操作(即檢查彎曲點，並通過形狀代表值來進行比較操作)中也可能顯示「作為此目標道路是沒有疑問的」，並由此，不需要在下級層中再次執行匹配操作。作出能夠選擇這種目標道路區段的這種傳送方設備的描述。
如圖32所示，此傳送方設備配備有平行移動相似形狀計算單元39、以及平行移動相似形狀資料庫40。平行移動相似形狀計算單元39通過使用已存儲在資料庫35中的數字地圖數據A來預先提取平行移動形狀道路。平行移動相似形狀資料庫40將由平行移動相似形狀計算單元39提取的平行移動相似形狀道路的數據存儲在其中。當特徵節點提取/形狀向量變形單元33使用存儲在平行移動相似形狀資料庫40中的平行移動相似形狀道路的數據時，此特徵節點提取/形狀向量變形單元33以下面的方式將形狀向量數據表示信息產生單元34中產生的形狀向量數據的對象區段變形，該方式即平行移動相似形狀道路在部分區段內平行移動。其它配置與第一實施例(圖6)的配置沒有什麼不同。
圖33的流程圖表示平行移動相似形狀計算單元39的處理順序操作。
當使用連結號碼L＝1的連結作為對象時(步驟90)，從地圖資料庫35獲得有關連結L和周邊連結的信息(步驟91)，並計算連結L的平行移動相似形狀道路的當前狀況(步驟92)，並隨後將計算結果存儲在平行移動相似形狀資料庫40中(步驟93)。直到對於所有連結的處理操作完成(步驟94)，連結號碼增加(步驟95)，並且，重複執行從步驟91定義的順序操作。
並且，圖34的流程圖表示有關形狀向量數據表示信息產生單元34和特徵節點提取/形狀向量變形單元33的處理順序操作。形狀向量數據表示信息產生單元34獲得事件信息36(步驟100)，並產生形狀向量(步驟101)。
特徵節點提取/形狀向量變形單元33計算對應於形狀向量的連結號碼(步驟102)，並從平行移動相似形狀資料庫40獲得每個連結的平行移動相似形狀道路的當前狀況(步驟103)，並隨後通過全部形狀向量計算平行移動相似形狀道路的當前狀況(步驟104)。
特徵節點提取/形狀向量變形單元33判別有關形狀向量的開始端和末端的周邊區域是否存在平行移動相似形狀道路(步驟105)。當存在平行移動相似形狀道路時，特徵節點提取/形狀向量變形單元33以下面的方式對形狀向量變形，即在當前方的形狀向量的該端沿著道路延伸(步驟107)，並重複執行從步驟102定義的順序操作。
並且，在這種情況中，即不存在平行移動相似形狀道路(在步驟105中的「否」的情況中)，特徵節點提取/形狀向量變形單元33判別有關是否平行移動相似形狀道路不存在、存在於部分區段中、或對應於形狀向量的半程中的任意情況(步驟106)。當不存在平行移動相似形狀道路、或存在於形狀向量的半程的部分區段中時，特徵節點提取/形狀向量變形單元33在直接條件下確定形狀向量(步驟108)。當平行移動相似形狀道路不對應於任意這些情況時(在步驟106中的「否」的情況中)，特徵節點提取/形狀向量變形單元33以這種方式對形狀向量變形，該方式即此形狀向量沿著道路從兩端延伸(步驟107)，並隨後重複執行從步驟102定義的順序操作。
由於執行了這種順序操作，所以，即使在形狀向量數據的對象區段中存在平行移動相似形狀道路的這種情況中，仍可以以這種方式對目標道路變形，該方式即此平行移動相似形狀道路僅存在於目標道路區段的「部分區段」中。並且，在地圖匹配處理操作中，可以以這種方式設置目標道路區段，該方式即在特別重要的目標道路的開始端和結束端不存在平行移動相似形狀道路。
(第九實施例)在第九實施例中，作出具有分層結構的道路網絡數據的產生順序操作的描述。
如在圖41中示意性示出的，對於此道路網絡數據，數據產生處理單元121從數字地圖資料庫120的地圖數據產生各個分層的道路網絡數據123、124、125。圖40表示此處理順序操作。
首先，順序地從N＝1開始設置有關數字地圖數據的感興趣的區段(步驟130)，並且順序地從連結號＝1開始設置此區段內的感興趣的連結(步驟131)。從數字地圖資料庫獲得相關區段N的相關連結L的數據，並隨後從其中的道路屬性信息確定此連結L的分層號(步驟132)。並且，獲得此連結L的周邊道路信息(步驟133)。對於所有連結執行上面說明的處理操作(步驟134和步驟142)。當對於所有這些連結的處理操作完成時，將分層號設置為M＝1(步驟135)，並隨後構造分層M的道路網絡(步驟136)。對於所有分層執行此處理操作(步驟137和步驟143)。當具有所有分層的道路網絡的構造完成時，設置層間連結節點(步驟138)。並且，對於所有已在區段N的分層M中重新產生的連結，從周邊道路信息產生平行移動相似形狀屬性信息(步驟139)，並且將跳躍距離設置到各個插值點之間的連結(步驟140)。對於所有區段執行上面說明的處理操作(步驟141和步驟144)。
由於執行了上面說明的處理操作，所以從圖1的數字地圖數據產生圖3(a)、圖3(b)、圖3(c)中示出的這種數據。並且，在產生了平行移動相似形狀屬性信息的情況中，產生圖10的這種數據。在產生了形狀代表值的情況中，獲得圖12的這種數據結構。並且，在產生跳躍距離的情況中，獲得圖21的這種數據結構。
(第十實施例)在第十實施例中，作出這種描述，即取代使用分層結構、對一組(one sheet)地圖數據設置上級、中級和下級的權重的這種系統。
如圖39所示，在此系統中，將包含於一組地圖數據中的各個道路細分為上級道路、中級道路、以及下級道路。與在分層結構的上級層中的地圖匹配操作相對應，通過使用上級道路來執行地圖匹配操作。與在分層結構的中級層中的地圖匹配操作相對應，通過使用上級道路和中級道路來執行地圖匹配操作。並且，與在分層結構的下級層中的地圖匹配操作相對應，通過使用所有上級道路、中級道路和下級道路來執行地圖匹配操作。
圖38示出了用於說明該處理操作的流程圖。
作出哪個級別的道路在地圖匹配操作中被用作目標道路的判定(步驟120)，並隨後執行地圖匹配操作(步驟121)，並計算評價值(步驟122)。評價值的計算與圖7中示出的情況相同。
可成功完成有關候選點的設置操作，並且此外，作出對於候選點的評價值是否小於或等於預定值的判斷(步驟123)。當候選點的評價值小於或等於預定值時，基於所選的形狀模型來識別目標道路(步驟124)。
並且，在步驟13中，當候選點的設置操作不能成功完成、或候選點的評價值超過了預定值時，作出對於用過的道路是否對應於下級道路的檢查(步驟126)。當用過的道路對應於最下級道路時，假定地圖匹配操作失敗，並隨後結束處理操作(步驟127)。當用過的道路不對應於最下級道路時，將低於當前使用的道路的道路添加到目標道路中(步驟125)，並隨後重複執行從步驟121定義的處理操作。
如先前說明的，當使用一組地圖時，將權重賦給道路，並且選擇在地圖匹配操作中使用的道路，以便減小當執行候選點搜索操作時的候選點的總數，並由此，可以高速執行地圖匹配操作。
還應當理解，迄今，各個實施例已經描述了這種方法，即執行形狀向量的地圖匹配操作，以便識別道路。也可將分層構造方案應用到信息交換系統中，其中，通過路線計算的方式來計算節點之間的路線。在此信息交換系統中，在連結和/或交叉點的半程中間隔地選擇節點，並隨後通過路線計算來獲得節點之間的路線。圖42表示這種情況中的情形，即已經對此系統實行了分層構造方案。以間隔的方式選擇節點P1(＝連結中心點)、節點P2(＝交叉點)、節點P3(＝連結中心點)、以及節點P4(＝連結中心點)。當參考這些節點的緯度/經度數據時，檢測出上級層中的節點位置。在此情況中，儘管對於節點P1、P2、P3的候選點的檢測操作可以成功完成，但對於節點P4的候選點的檢測操作失敗。結果，P1到P2到P3可識別目標道路區段，但仍不能識別P3到P4之間的路線。
由此，將上級層轉移到下級層，檢測出節點P3和P4的候選點，通過路線搜索操作計算出節點P3到P4之間的路線，並由此與上級層中的識別點相結合，識別P1到P2到P3到P4之中的所有道路區段。
如先前說明的，對於基於緯度/經度信息來識別道路的所有位置傳送方法，可應用分層構造方案。
本發明的特徵如下。即，對於對應於地圖匹配操作的目標道路的具有頻率上不一致條件的道路網絡，響應於該頻率而基本地設置優先級順序；基於優先級順序，限定與上述目標道路地圖匹配的道路網絡；以及當不能獲得與目標道路的形狀向量匹配的目標道路時，釋放基於優先級順序的限定，以便擴大與目標道路匹配的道路網絡的範圍。結果，可高速地執行地圖匹配操作。
(第十一實施例)接下來，現在將通過參照附圖來詳細說明根據本發明的形狀匹配目的的資料庫和形狀匹配設備的實施例。
應當注意，在此實施例中，將節點、連結、或專注於輔助目的的節點的插值點用作表示地圖上的特定點或特定道路的信息。節點對應於道路上這種點，即已與交叉點、隧道的入口和出口、橋的入口和出口、行政區的邊界等相一致地對其設置。插值點對應於這種點，其被用作再現節點之間的道路形狀。連結對應於將節點連接到另一個節點的線段。通過使用節點和連結來作出下面提到的說明。
圖43表示根據此實施例的道路信息提供系統，其使用形狀匹配目的的資料庫和形狀匹配設備。在此附圖中，將諸如交通事故、道路建設、交通堵塞、降雨、降雪以及交通管制的事件信息與要識別的道路、地域信息等相結合、存儲在事件信息資料庫85中。並且，通過被稱為節點的「點」和被稱為連結的「線段」，已將表示道路、河流、橋、建築物等的信息存儲在地圖資料庫86中。
圖44中示出了事件信息的數據結構，連結信息的數據結構在圖45中表示，節點信息的數據結構在圖46中表示，而形狀向量的數據結構在圖47中示出。當通過已被存儲在圖43中示出的地圖資料庫86中的節點和連結，來構造地圖數據和形狀匹配(地圖匹配)目的的數據時，如圖47所示，通過必要點中的絕對位置或相對位置來表示節點。
圖43中示出的道路信息提供系統擁有的形狀向量數據表示信息產生單元84基於作為緯度和經度的絕對位置、以及與此絕對位置的相對位置，來表示由事件信息代表的事件出現位置，並從已被存儲在地圖資料庫86中的節點和連結產生表示目標道路的形狀向量。在此實施例中，現在將描述其中傳送圖48中示出的「Ps-Pa-Pb-Pe」的形狀向量的例子。因而假定，對於形狀向量的表示，以通過順序、從開始點表示對應於節點的點的名稱。
在此情況中，在這種情況中，即要傳送的形狀向量沒有特徵，並且在接收設備88中幾乎不能執行形狀向量的地圖匹配操作，此時，特徵節點提取/形狀向量變形設備83可替換地以「Ps-Pa-Pm2-Pms2-Pm2-Pm3-Pm4-Pb-Pe」的方式添加節點或插值點，並由此可替換地通過窄連結來表示此形狀向量。
圖48為用於表示指出道路的「Ps-Pa-Pb-Pe」的形狀向量的圖。圖49為用於示意性地表示這種情形的示例圖，即已接收了圖48的形狀向量的接收設備88執行形狀匹配(地圖匹配)操作。
或者，在此實施例中，除了有關節點和插值點的坐標流(coordinate stream)的信息之外，可將先前已存在於數字地圖資料庫中的諸如道路種類、道路號碼、收費道路碼、或交通交叉節點的詳細信息、或如快速路、國道、以及主要地方道路的這種道路種類添加到節點中。此外，作為其它(信息)之中的附加信息，在交叉節點的情況中，可替換地添加交叉點的名稱。在這種情況中，即節點表示隧道的入口和出口、橋的入口和出口、行政區的邊界，此時，可替換地添加上面說明的所有信息。此外，作為附加信息，為了通知傳送信息的精度，可替換地添加代表基礎地圖的精度級別的這種信息，例如，從以1/25000的縮小比例尺繪製的地圖數據獲得的數據、或從以1/10000的縮小比例尺繪製的地圖數據獲得的數據。
在此情況中，在圖48中示出的已接收了包含形狀向量的數據的接收設備88中，通過數據接收單元88e來恢復數據，並且，通過形狀向量表示事件信息單元88b來再現形狀向量，以便分離已被添加到此形狀向量的信息。接下來，形狀匹配單元88d通過使用用於識別事件的出現地點的形狀匹配目的資料庫88b，來識別由形狀向量表示的地圖上的位置。
此實施例的形狀匹配目的資料庫88b以下面這種方式將數據存儲到其中，即將數據細分為三層構造(即上級層、中級層、下級層)。已將節點和連結存儲在了上級層中，其表示國道、主要地方道路、已安裝了光信號燈設備的道路、以及其它主要道路。光信號燈設備對應於已在警察署的主要控制下安裝的道路信息接收設備。已將節點和連結存儲在了中級層中，其表示諸如轄區道路和城市/城鎮/鄉村道路的道路，其在以1/100000的縮小比例尺繪製的地圖中表示。並且，已將示出在以1/5000的縮小比例尺繪製的地圖中表示的道路的節點和連結存儲在了下級層中。
在此實施例中，接收設備88的形狀匹配單元88d從上級層順序地執行關於形狀向量的形狀向量匹配操作。當形狀彼此相一致時，形狀匹配單元88d完成匹配操作，並隨後判定這種道路包括在形狀向量的對象中。
圖50示出了用於說明根據此實施例的此形狀匹配方法的流程圖。如在此圖中所表示的，在上級層中不能成功完成形狀匹配操作的情況中(在圖49示出的例子中，如圖49(c)所表示的，在上級層(a)中不存在Pb到Pe之間的道路)，將上級層的形狀匹配操作轉換到中級層(b)，其中，從第一點Ps再次執行形狀地圖操作。圖49是在中級層中已完成了所有形狀匹配操作的例子。在即使在中級層中也未完成地圖匹配操作的情況中，將形狀匹配操作轉移到表示更多詳細道路的下級層，並隨後執行形狀匹配操作。
(第十二實施例)接下來，圖51表示在已設置了通常在各個層中使用的節點的情況中執行的形狀匹配操作。如在此圖中所示出的，上級層的符號「Pa」和「Pc」為分別對應於下級層的符號「P1」和「P2」的節點。由於這種形狀匹配目的資料庫擁有與安裝在圖43中示出的中央系統的導航機器上的傳送設備87和接收設備88相同的硬體結構，所以，現在將結合圖43來說明此形狀匹配目的資料庫。並且，在此情況中，在各個部分中，根據圖50中表示的流程圖來執行處理操作本身。
在將圖52中示出的形狀向量從傳送設備87傳送的情況中，在上級層中存在從Ps到Pd的路線，但在上級層中不存在對應於路線「Pd-Pe」的部分。由此，將接收設備88的形狀匹配單元88d轉移到形狀匹配目的數據88b的中級層，並執行形狀匹配操作。在此情況中，由於在圖53中表示通常對於兩層——即從節點Ps到節點Pd定義的路線中的上級層和中級層——定義的節點Pd(上級層)和節點P2(中級層)，所以，在Ps和Pc之間的路線中使用在上級層中獲得的匹配結果，而在對應於Pc的P2和Pe′之間的路線中使用在中級層中獲得的匹配結果，以便形狀匹配單元88d從節點Ps直到節點Pe完成形狀匹配操作。
在此形狀匹配方法中，由於在中級層和下級層之間類似地設置公共節點，所以，各個層的形狀匹配結果通過該公共節點彼此連接，以便可以更有效地利用形狀匹配結果。
圖54示出了在擁有標識符、同時此標識符表示道路通過公共節點被連結到了哪個分層的情況中的形狀匹配操作的情形。在圖54中，附圖標記263、264、265表示連結。尤其是，附圖標記264示出了這種連結，即在也位於上級層的道路中進行標識符的定義。另一方面，附圖標記263和265對應於僅位於下級層中的道路，而道路263和264在部分區段中平行移動。並且，圖55中表示圖54中示出的形狀匹配操作的結果。並且，在此情況中，硬體結構與圖43中示出的結構相同。
圖45表示存儲在形狀匹配資料庫88b中的連結信息的數據結構。並且，圖56表示用於描述在第十二實施例中的形狀匹配系統的流程圖。此形狀匹配系統的第一特徵如下給出也就是說，由於分層從屬信息存在於連結中，所以，如果根據此信息執行形狀匹配操作，則可以高速地執行形狀匹配操作。
當已詳細地、或參照特定實施例來描述了本發明時，顯然，對於本領域的技術人員來說，本發明可改變或修改，同時不背離本發明的技術範圍和精神。
本專利申請基於2002年3月29日提交的日本專利申請(第2002-096893號)和2002年9月30日提交的日本專利申請(第2002-288149號)作出，其內容合併於此作為引用。
工業應用性
從前面的描述中可顯然看出，根據本發明的地圖匹配方法，可快速且正確地識別應當處理的道路。
尤其是，在這樣情況中，即在包括在道路網絡內的目標道路中的道路中出現不均勻的情形，此時可達到巨大效果，例如，從交通信息的目標道路傳送的移動軌跡，以及探測獲取系統的探頭(移動交通工具)。
並且，本發明的設備和電腦程式可實現高速且正確的地圖匹配操作，並能夠支持高速且正確的地圖匹配操作。
此外，根據本發明，即使當用於提供交通信息的目標道路增加時，由於將接收的信息用於執行形狀匹配操作，所以仍能夠識別道路，並能夠顯示交通信息，而不需要用於車輛導航設備的過多的處理能力。由此，當沒有給出對道路數據的維護的過多工作負擔時，可傳送數字地圖上的位置信息。並且，可快速顯示、或可立即提供諸如交通信息的與道路相關的信息。
權利要求
1.一種地圖匹配方法，包括以下步驟響應於適合地圖匹配操作的目標道路的頻率，對道路網絡設置優先級順序，其中所述道路網絡具有所述頻率上的偏差；基於所述優先級順序來限定與所述目標道路匹配的所述道路網絡的範圍；以及如果不能獲得與所述目標道路的形狀向量匹配的候選道路，則釋放基於優先級順序作出的所述限定，以便擴大與所述目標道路匹配的道路網絡的所述範圍。
2.一種地圖匹配方法，包括以下步驟通過使用包括已被施加不同權重的一組道路網絡的地圖的道路網絡數據，將權重相對較大的道路網絡與表示目標道路的形狀的形狀向量進行匹配；以及如果不能在權重相對較大的道路網絡中獲得與所述形狀向量相適合的候選道路，則進一步將具有權重相對較大的所述道路網絡和權重相對較小的道路網絡的道路網絡與所述形狀向量進行匹配，並識別所述目標道路區段。
3.一種地圖匹配方法，包括以下步驟通過使用包括分層道路網絡的道路網絡數據，將相對上級分層的道路網絡與表示目標道路區段的形狀的形狀向量進行匹配，其中從具有更低的下級分層的道路網絡中提取上級分層的道路網絡；以及如果不能在相對上級分層的所述道路網絡中獲得與所述形狀向量相適合的候選道路，則進一步將具有更低級分層的道路網絡與所述形狀向量進行匹配，並識別所述目標道路。
4.如權利要求3所述的地圖匹配方法，還包括以下步驟通過參照所述形狀向量的屬性信息，在開始階段中確定被匹配的分層。
5.如權利要求3所述的地圖匹配方法，還包括以下步驟通過道路屬性來確定所述分層道路網絡的每個分層。
6.如權利要求5所述的地圖匹配方法，其中，使用道路種類、道路號碼、收費道路/免費道路、道路模式、或有關交通信息提供目標道路的識別信息，作為所述道路屬性。
7.如權利要求3所述的地圖匹配方法，還包括以下步驟如果可以獲得適合於所述形狀向量的候選道路，則判斷具有與所述候選道路平行移動的相似形狀的平行移動相似形狀道路是否存在於這種道路網絡中，該種道路網絡具有比其中可以獲得所述候選道路的道路網絡的分層低的分層。
8.如權利要求7所述的地圖匹配方法，還包括以下步驟如果存在所述平行移動相似形狀道路，則將所述形狀向量的形狀、所述候選道路的形狀、以及所述平行移動相似形狀道路的形狀彼此比較，並判定所述候選道路的使用是否可被接受。
9.如權利要求8所述的地圖匹配方法，還包括以下步驟如果不能判定所述候選道路的使用可被接受，則通過使用具有比已從其獲得所述候選道路的道路網絡的分層低的分層的道路網絡，來重新開始對於所述形狀向量的匹配操作。
10.如權利要求3所述的地圖匹配方法，還包括以下步驟提供層間連結節點，其用於通過具有上級分層的道路網絡、從具有上級分層的道路網絡轉移到具有低一級的上級分層的另一個道路網絡；如果在所述具有上級分層的道路網絡的半程中不能執行對於所述形狀向量的匹配操作，則通過返回到所述層間連結節點、轉移到具有低一級的上級分層的道路網絡；以及將具有下級分層的所述道路網絡與所述形狀向量進行匹配。
11.如權利要求3所述的地圖匹配方法，還包括以下步驟定義返回距離，其用於從具有上級分層的道路網絡轉移到具有低一級的上級分層的另一個道路網絡；如果在所述具有上級分層的道路網絡的半程中不能執行對於所述形狀向量的匹配操作，則通過返回所述返回距離、轉移到具有低一級的上級分層的道路網絡；以及將具有下級分層的所述道路網絡與所述形狀向量進行匹配。
12.如權利要求3所述的地圖匹配方法，將表示存在各個連結的最上級分層的數據設置到具有除了最上級分層之外的各個分層的道路網絡數據；如果當在所述形狀向量和具有最上級分層之外的分層的道路網絡之間執行匹配操作時、可在一個或更多點處成功完成該匹配操作，則通過連結轉移到具有存在所述連結的上級分層的道路網絡；以及將具有上級分層的所述道路網絡與所述形狀向量進行匹配。
13.如權利要求3所述的地圖匹配方法，還包括以下步驟基於包括在所述形狀向量中的誤差的大小，改變道路網絡內的候選點的搜索範圍，以與所述形狀向量匹配。
14.如權利要求3所述的地圖匹配方法，還包括以下步驟基於具有各個分層的道路網絡的平均連結長度，設置路點的削減距離，以與所述形狀向量匹配；以及根據所述削減距離，通過削減路點來設置路點。
15.如權利要求3所述的地圖匹配方法，還包括以下步驟響應於所述道路區段已被識別為所述目標道路的頻率，而更新要包括在具有所述道路網絡數據的各個分層的道路網絡中的所述道路區段。
16.如權利要求3所述的地圖匹配方法，還包括將在每個分層中被識別為所述目標道路的道路區段複製在高速緩衝存儲器區域中，其中，使用記錄在所述高速緩衝存儲器區域中的道路網絡，作為所述最上級分層的道路網絡。
17.如權利要求4所述的地圖匹配方法，還包括以下步驟預先將用於表示有關平行移動相似形狀道路是否存在的平行移動相似形狀道路存在/不存在信息，應用到除了所述道路網絡數據的最下級分層之外的各個分層的連結數據；以及基於所述平行移動相似形狀道路存在/不存在信息，判定有關平行移動相似形狀道路是否存在。
18.如權利要求16所述的地圖匹配方法，還包括通過使用下面的任意一項或更多項，來創建所述平行移動相似形狀道路存在/不存在信息在上級層的相關道路上設置的多個路點；相鄰道路上的各個路點的最近點之間的距離；相鄰道路上的各個路點的最近點之間的方位差異；最近點之間的連接特性；以及路線距離。
19.如權利要求5所述的地圖匹配方法，還包括以下步驟預先將表示連結的形狀的形狀代表值應用到具有所述道路網絡數據的各個分層的連結數據，其中，將所述形狀代表值用於對於所述形狀向量的形狀的比較。
20.如權利要求13所述的地圖匹配方法，其中以將路點設置為連結的形狀的特徵點的方式定義所述削減距離。
21.如權利要求9所述的地圖匹配方法，還包括以下步驟如果所述形狀向量的形狀變得接近於所述平行移動相似形狀道路的形狀、而不是所述候選道路的形狀，則通過使用包括所述平行移動相似形狀道路的分層的道路網絡，來重新開始對於所述形狀向量的匹配操作。
22.一種接收設備，包括數字地圖；用於地圖修補的道路網絡數據，所述道路網絡包括具有從所述數字地圖形成的多個分層的分層道路網絡，其中從具有下級分層的道路網絡提取具有上級分層的道路網絡；數據接收單元，用於接收包含表示目標道路的形狀的形狀向量的數據；以及地圖匹配單元，用於通過使用所述道路網絡數據來執行所述形狀向量的地圖匹配操作，以便識別所述目標道路，其中，在開始階段，所述地圖匹配單元將所述形狀向量與具有所述道路網絡數據的最上級分層的道路網絡進行匹配，並且其中，如果不能在具有最上級分層的道路網絡中獲得適合於所述形狀向量的候選道路，則所述地圖匹配單元將所述形狀向量與具有另一分層的道路網絡進行匹配，並識別所述目標道路。
23.一種事件信息提供設備，包括數字地圖；用於地圖修補的道路網絡數據，所述道路網絡包括具有從所述數字地圖形成的多個分層的分層道路網絡，其中從具有下級分層的道路網絡提取具有上級分層的道路網絡；地圖數據信息傳送單元，用於發布所述數字地圖和所述道路網絡數據；形狀向量數據產生單元，用於通過使用所述數字地圖的數據，來產生表示事件信息的目標道路的形狀的形狀向量；形狀向量變形單元，用於執行將指定所述道路網絡數據的分層的信息添加到所述形狀向量數據產生單元所產生的所述形狀向量的添加處理操作；和事件信息傳送單元，用於傳送包含由所述形狀向量變形單元處理的所述形狀向量的事件信息。
24.一種事件信息提供設備，包括數字地圖；平行移動相似形狀計算單元，用於計算平行移動相似形狀連結，其與連結相平行地移動，並具有與來自所述數字地圖的數據的所述連結相似的形狀；形狀向量數據產生單元，用於通過使用所述數字地圖的數據，來產生表示事件信息的目標道路的形狀的形狀向量；形狀向量變形單元，用於通過使用所述平行移動相似形狀計算單元的計算結果，來識別關於所述目標道路的連結中是否存在所述平行移動相似形狀連結，並且如果存在所述平行移動相似形狀連結，則通過延伸所述目標道路直到這種位置，即所述平行移動相似形狀連結的形狀能夠與所述目標道路的形狀相區分，來執行所述形狀向量的變形處理操作；以及事件信息傳送單元，用於傳送包括由所述形狀向量變形單元處理的所述形狀向量的事件信息。
25.一種程序，使計算機執行以下過程通過使用包括具有從所述數字地圖形成的多個層的分層道路網絡的道路網絡數據，來獲得目標道路的候選道路，通過將具有最上級分層的所述道路網絡與表示目標道路的形狀的形狀向量進行匹配，以及如果在具有最上級分層的道路網絡中不能獲得適合於所述形狀向量的候選道路，則通過重新開始將具有另一分層的道路網絡與所述形狀向量進行匹配，來從具有下級分層的道路網絡提取具有上級分層的所述道路網絡；如果能夠獲得與所述形狀向量相匹配的候選道路，則判定關於與所述目標道路相平行地移動、並且具有與其相似的形狀的平行移動相似形狀道路，是否存在於具有比其中能夠獲得所述候選道路的所述道路網絡的分層低的分層的道路網絡中；如果存在所述平行移動相似形狀道路，則通過將所述形狀向量的形狀、所述候選道路的形狀、以及所述平行移動相似形狀道路的形狀彼此比較，以判定關於所述候選道路的使用是否可被接受；以及如果不能判定候選道路的使用可被接受，則通過使用具有比已從其獲得所述候選道路的道路網絡的分層低的分層的道路網絡，來重新開始對於所述形狀向量的匹配。
26.一種用於形狀匹配的資料庫，具有多個分層，並且其中道路網絡通過每個分層中的節點和連結來表示，所述資料庫包括具有節點和連結的最上級分層，其表示最重要的道路；以及各個層，基於表示道路的所述節點和所述連結的重要特點，其從所述最上級分層到下級分層被順序地細分，其中，通過使用所述各個層來限定應當從所述道路網絡形狀匹配的節點和連結。
27.一種形狀匹配設備，用於通過使用形狀匹配目的資料庫和形狀向量來執行形狀匹配操作，如權利要求26中所述的，其中所述形狀匹配設備從所述最上級分層執行形狀匹配操作；在所述最上級分層中可以成功完成形狀匹配操作、並可識別出節點和連結的情況中，完成處理操作；在不能識別對應於所述形狀向量的節點和連結的情況中，將形狀匹配操作轉移到下級分層，並執行形狀匹配操作；以及用於形狀匹配操作的對象被順序地轉移到下一分層，以便執行形狀匹配操作。
28.如權利要求27所述的形狀匹配設備，其中，如果在所述多個分層之間提供公共節點，則將形狀匹配操作的對象從所述公共節點轉移到下一分層，並將各個分層中的形狀匹配操作的結果通過所述公共節點彼此耦接，以便執行形狀匹配操作。
29.如權利要求27或28所述的形狀匹配設備，其中，如果將標識符應用到也在上級層中定義的連結，則通過使用所述標識符，將形狀匹配操作轉移到所述上級層，以便執行形狀匹配操作。
30.如權利要求27、28或29所述的形狀匹配設備，其中，在形狀匹配操作在所述預定分層中失敗的情況下，並且如果利用表示所述地點的絕對位置，則形狀匹配操作被順序地轉移到下級分層，以便執行形狀匹配操作。
31.如權利要求26所述的形狀向量目的資料庫，其中，上級層變得越高，則使形狀向量的節點總數變得越粗糙。
32.一種形狀向量傳送伺服器，用於將權利要求26、或權利要求31中所述的形狀向量目的資料庫存儲到其中，並響應於預定信號而傳送部分或全部形狀向量。
33.如權利要求27、28、29或30所述的形狀匹配設備，其中，如果在上級層中執行形狀匹配操作，則通過使用有關連結長度的信息，從節點串中削減節點，並且通過使用削減的節點串，執行形狀匹配操作。
34.如權利要求27、28、29、30或33所述的形狀匹配設備，其中，如果將附加信息添加到形狀向量，則通過使用所述附加信息選擇被用於首次形狀匹配的分層。
全文摘要
一種高速地圖匹配方法。該地圖匹配方法使用被分為層(a、b、c)的道路網絡上的道路網絡數據。該網絡包括由從低級道路網絡提取的網絡組成的高級道路網絡。將最高級層(a)中的道路網絡與示出目標道路的形狀的形狀向量相匹配。如果在最高級層(a)的道路網絡中沒有與該形狀向量匹配的候選道路，則將另一層(b或c)中的道路網絡與形狀向量來匹配，以識別目標道路。作為交通信息的對象的大多數目標道路可以通過使用最高級層(a)的道路網絡進行地圖匹配來識別，並且允許高速的地圖匹配。
文檔編號G06Q10/00GK1653505SQ0381098
公開日2005年8月10日 申請日期2003年3月28日 優先權日2002年3月29日
發明者足立晉哉, 佐藤誠 申請人:松下電器產業株式會社