(57)【特許請求の範囲】
【請求項１】
通信端末と、前記通信端末に地図データを配信する地図データ配信装置とを備える地図データ配信システムであって、
前記地図データ配信装置は、
前記地図データにおける更新前後の差分を示す差分更新データと、
前記差分更新データの集合を表現する更新エレメントと、
前記更新エレメントの識別情報である更新エレメントＩＤと、前記差分更新データの地図領域と重なる所在領域を有し、前記地図データの更新前の更新日時を有して当該地図データの更新に依存関係を保持する依存更新エレメントＩＤとを含む更新エレメント管理データと、
を記憶する記憶部と、
前記通信端末から、前記更新エレメント、前記更新エレメント管理データ及び前記差分更新データの配信要求を受け付ける地図配信要求受付部と、
前記配信要求の前記地図領域と重なる前記所在領域を有する前記更新エレメント管理データと、当該更新エレメント管理データのうち、前記依存更新エレメントＩＤを有する前記更新エレメント管理データとを前記管理データ記憶部から抽出する更新管理データ抽出部と、
抽出された前記更新エレメント管理データと、当該更新エレメント管理データにより管理される前記更新エレメントと、前記差分更新データとを前記通信端末に送信する更新データ配信部とを備え、
前記通信端末は、少なくとも、受信した前記差分更新データ、前記更新エレメント及び前記更新エレメント管理データに基づいて、前記地図データを更新する地図更新部を備える
ことを特徴とする地図データ配信システム。
【請求項２】
請求項１に記載の地図データ配信システムにおいて、
前記更新管理データ抽出部は、前記所在領域を有する前記更新エレメント管理データを前記管理データ記憶部から抽出する処理を、前記地図データの更新に影響を与える前記依存更新エレメントＩＤを含まなくなるまで行う
ことを特徴とする地図データ配信システム。
【請求項３】
請求項１に記載の地図データ配信システムにおいて、
前記差分更新データは、ノードデータ及びリンクデータである
ことを特徴とする地図データ配信システム。
【請求項４】
請求項１に記載の地図データ配信システムにおいて、
前記配信要求は、前記通信端末の地図バージョン又は更新時間情報を含み、
前記更新データ配信部は、前記更新管理データ抽出部が抽出した前記更新エレメント管理データの中から、前記配信要求に含まれる前記地図バージョン又は前記更新時間情報と同一又は後に取得した前記地図バージョン又は前記更新時間情報を有する前記更新エレメント管理データ及び前記更新エレメントと、対応する前記差分更新データとを配信する
ことを特徴とする地図データ配信システム。
【請求項５】
請求項１に記載の地図データ配信システムにおいて、
前記地図データ配信装置は、入力された緯度及び経度からなる情報の集合であるルートデータから、道路ネットワークを表現するリンクデータと、リンクと既存道路が交差する点を表現するノードデータとを作成し、
前記ノードデータ及び前記リンクデータに対し、既存の前記リンクデータ及び前記ノードデータと異なる情報を、補完の属性を有する前記差分更新データとして追加する補完更新エレメントと、さらに、当該補完更新エレメントを管理する補完更新エレメント管理データとを作成して前記記憶部に格納し、
前記補完更新エレメントの地図領域と重なる前記所在領域を有し、かつ、最新の補完更新エレメント管理データが示す前記更新エレメントＩＤを、前記補完更新エレメント管理データにおける前記依存更新エレメントＩＤとして表現する補完地図情報作成部を備える
ことを特徴とする地図データ配信システム。
【請求項６】
通信端末と、前記通信端末に地図データを配信する地図データ配信装置とを備える地図データ配信システムにおける地図データ配信方法であって、
前記地図データ配信装置は、
前記地図データにおける更新前後の差分を示す差分更新データと、
前記差分更新データの集合を表現する更新エレメントと、
前記更新エレメントの識別情報である更新エレメントＩＤと、前記差分更新データの地図領域と重なる所在領域を有し、前記地図データの更新前の更新日時を有して当該地図データの更新に依存関係を保持する依存更新エレメントＩＤとを含む更新エレメント管理データと、
を記憶し、
前記通信端末から、前記更新エレメント、前記更新エレメント管理データ及び前記差分更新データの配信要求を受け付け、
前記配信要求の前記地図領域と重なる前記所在領域を有する前記更新エレメント管理データと、当該更新エレメント管理データのうち、前記依存更新エレメントＩＤを有する前記更新エレメント管理データとを抽出し、
抽出された前記更新エレメント管理データと、当該更新エレメント管理データにより管理される前記更新エレメントと、前記差分更新データとを前記通信端末に送信し、
前記通信端末は、少なくとも、受信した前記差分更新データ、前記更新エレメント及び前記更新エレメント管理データに基づいて、前記地図データを更新する
ことを特徴とする地図データ配信方法。
【請求項７】
請求項６に記載の地図データ配信方法において、
前記更新管理データ抽出部は、前記所在領域を有する前記更新エレメント管理データを前記管理データ記憶部から抽出する処理を、前記地図データの更新に影響を与える前記依存更新エレメントＩＤを含まなくなるまで行う
ことを特徴とする地図データ配信方法。
【請求項８】
請求項６に記載の地図データ配信方法において、
前記差分更新データは、ノードデータ及びリンクデータである
ことを特徴とする地図データ配信方法。
【請求項９】
請求項６に記載の地図データ配信方法において、
前記配信要求は、前記通信端末の地図バージョン又は更新時間情報を含み、
前記更新データ配信部は、前記更新管理データ抽出部が抽出した前記更新エレメント管理データの中から、前記配信要求に含まれる前記地図バージョン又は前記更新時間情報と同一又は後に取得した前記地図バージョン又は前記更新時間情報を有する前記更新エレメント管理データ及び前記更新エレメントと、対応する前記差分更新データとを配信する
ことを特徴とする地図データ配信方法。
【請求項１０】
請求項６に記載の地図データ配信方法において、
前記地図データ配信装置は、入力された緯度及び経度からなる情報の集合であるルートデータから、道路ネットワークを表現するリンクデータと、リンクと既存道路が交差する点を表現するノードデータとを作成し、
前記ノードデータ及び前記リンクデータに対し、既存の前記リンクデータ及び前記ノードデータと異なる情報を、補完の属性を有する前記差分更新データとして追加する補完更新エレメントと、さらに、当該補完更新エレメントを管理する補完更新エレメント管理データとを作成し、
前記補完更新エレメントの地図領域と重なる前記所在領域を有し、かつ、最新の補完更新エレメント管理データが示す前記更新エレメントＩＤを、前記補完更新エレメント管理データにおける前記依存更新エレメントＩＤとして表現する
ことを特徴とする地図データ配信方法。
【請求項１１】
地図データ配信装置から地図データを受信する通信端末であって、
前記地図データにおける更新前後の差分を示す差分更新データと、
前記差分更新データの集合を表現する更新エレメントと、
前記更新エレメントの識別情報である更新エレメントＩＤと、前記差分更新データの地図領域と重なる所在領域を有し、前記地図データの更新前の更新日時を有して当該地図データの更新に依存関係を保持する依存更新エレメントＩＤとを含む更新エレメント管理データと、
を前記地図データ配信装置へ配信要求する配信要求部と、
前記更新エレメント、前記更新エレメント管理データ及び前記差分更新データを前記地図データ配信装置から受信する受信部と、
前記更新エレメント及び前記更新エレメント管理データを記憶する管理データ記憶部と、
前記差分更新データとしてノードデータ及びリンクデータを記憶する地図データ記憶部と、
受信した前記更新エレメント管理データの種別を参照し、種別が補完である前記更新エレメントの内容を参照し、前記更新エレメントの操作が追加である前記リンクと前記ノードを削除し、操作が削除である前記リンクと前記ノードを追加することにより、種別が補完である前記更新エレメントによる更新を無効化し、
次に受信した前記更新エレメント管理データの種別を参照し、種別が正規である前記更新エレメントの内容を適用して更新を実施し、
次に受信した前記更新エレメント管理データの種別を参照し、種別が補完である前記更新エレメントの内容を適用して更新を実施する地図更新部とを備える
ことを特徴とする通信端末。
【請求項１２】
請求項１１に記載の通信端末において、
前記配信要求部は、前記通信端末が有する前記地図バージョン又は前記更新時間情報と同一又は後に取得した前記地図バージョン又は前記更新時間情報を有する前記更新エレメント及び前記更新エレメント管理データと、対応する前記差分更新データの配信を要求する
ことを特徴とする通信端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データの配信及び地図の更新技術に係る地図データ配信システム、地図データ配信方法及び通信端末に関する。
【背景技術】
【０００２】
従来、カーナビゲーションシステム（以下、「カーナビ」ともいう）において、車に固定され持ち運びが不可の点や、操作や表示インターフェースの使い難さを補うため、自宅ＰＣ（Personal Computer）からインターネット上の専用サイトに接続して目的地検索やルート設定を行い、結果をカーナビにダウンロードするサービスが実現されている。特に、ハードディスク（ＨＤＤ）を内蔵したカーナビでは、保持可能なデータ量が多く、前記のようなサービスを実現しやすい。
【０００３】
前記のようなサイトでは、施設（目的地）情報等は、カーナビ内臓の情報と比較し、より多くかつ最新の情報が提供されている。また、サイト利用者間で情報提供および共有の仕組みがある場合は、通常のカーナビ地図が対象としない、詳細なローカル情報の取得と目的地設定が可能である。
【０００４】
このような情報をカーナビにダウンロードした場合、施設の位置情報は、全ての機器で共通である緯度経度情報に基づくため、カーナビにおいて走行ルート検索の目的地として利用しても不都合は生じない。
【０００５】
一方、前記のようなサイトで検索や共有されたルート情報（経路）に関しても、緯度経度情報の集合、という形式でカーナビに取り込む事は可能である。しかし、地図の新旧や詳細度の違い等の理由により、カーナビにおいて同一のルート表現ができないケースがある。このような例として、前記サイト上の地図ではバイパス道路が開通しているが、カーナビ地図は古いためバイパス道路が記載されていない場合等が挙げられる。
【０００６】
この問題への対応として、カーナビ地図中で、ルート情報に対応する道路ネットワーク情報が存在しない場合、不足する道路ネットワーク情報をルート情報から新規に作成する手法が考えられる。例えば、カーナビ中の地図が図１７（ａ）の状態であり、領域４、５、６を横に貫く道路ネットワーク情報が必要な場合、図１７（ｂ）の点線で示す道路ネットワーク情報を補完地図情報として、既存道路ネットワークと同様な形式で付加するのである。このようにすることにより、任意のルート表現を可能にし、ルート検索やルートガイドも従来と同様のアルゴリズムで実現できる。
【０００７】
また、カーナビの地図情報は、定期的に最新版が発売され、ユーザは任意の版の地図を入手し更新できる。例えば、特許文献１では、最新版の地図を複数の方法でダウンロードし地図更新する方式が開示されている。
【０００８】
【特許文献１】特開２００６-３１７６４３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１に記載の技術では、このような地図更新があった場合、上記の補完地図情報との共存に問題がある。
【００１０】
問題の一つに上書き消去のケースがある。これを図１７、図１８を用いて説明する。たとえば、領域４、５、６を横に貫く仮にＡバイパスと呼ぶ道路の一部開通が２００７年２月（図１７（ａ）の状態）、全線開通が２００７年８月であり（図１７（ｂ）の状態）、カーナビ地図更新版が２００７年５月の地図（図１８（ａ）の状態）とする。ここでＡバイパス全線開通後の２００７年９月のルート情報から、Ａバイパスの道路情報を補完地図情報として作成していた場合（図１７（ｂ））に、カーナビ地図を更新した場合を考える。一般にカーナビ地図の更新版は、電子化やメディア作成、流通等のタイムラグにより、道路の変更は直ちに反映されない。この場合も、２００７年５月の情報（図１８（ａ））を使用することになる。
【００１１】
この状態での地図更新は、２００７年５月すなわちＡバイパスが一部開通状態の地図（図１８（ａ））に更新されるため、せっかくルート情報から作成したＡバイパスの全線開通情報が消去されてしまう。
【００１２】
また、前記消去を避けるため、補完地図情報は消去せず継続的に保存するという手段も考えられる。しかしこの場合、一部開通区間の道路ネットワーク情報が、補完地図情報と更新された新規地図情報とで二重に保持される事になる（図１８（ｂ））。このような道路ネットワークの二重保持は、カーナビの道路表示アルゴリズムや経路探索アルゴリズムへ大きな影響を及ぼすため受け容れられ難い。
【００１３】
このような矛盾は、補完地図情報も正規の地図更新情報と同様に扱えば避ける事が出来るが、前述のように情報の鮮度が古くなる点や、地図の提供者が、ユーザがルート情報から任意に作成した補完地図情報を全て把握し網羅するのは多大な労力が必要になる。
【００１４】
即ち、正規の地図更新情報と、利用者が任意でルート情報等から作成した補完地図情報とを共存させた場合に発生する、道路ネットワーク情報の情報欠落や二重情報保持等によるの矛盾の発生である。
【００１５】
上記問題点に鑑み、本発明は、補完地図情報と地図更新情報から整合性のある道路ネットワーク情報を導く地図データ配信システムを提供することにある。
【００１６】
さらに、本発明の目的は、上記地図データ配信システムに用いる地図データ配信方法を提供することにある。
【００１７】
さらに、本発明の目的は、上記整合性のある道路ネットワーク情報を導くためのデータ処理量及び通信量の削減を実現するカーナビゲーションシステムを提供することにある。
【課題を解決するための手段】
【００１８】
上記課題を解決するために、本発明による地図データ配信システムは、通信端末と、前記通信端末に地図データを配信する地図データ配信装置とを備える地図データ配信システムであって、前記地図データ配信装置が、前記地図データにおける更新前後の差分を示す差分更新データと、前記差分更新データの集合を表現する更新エレメントと、前記更新エレメントの識別情報である更新エレメントＩＤと、前記差分更新データの地図領域と重なる所在領域を有し、前記地図データの更新前の更新日時を有して当該地図データの更新に依存関係を保持する依存更新エレメントＩＤとを含む更新エレメント管理データと、を記憶する記憶部と、前記通信端末から、前記更新エレメント、前記更新エレメント管理データ及び前記差分更新データの配信要求を受け付ける地図配信要求受付部と、前記配信要求の前記地図領域と重なる前記所在領域を有する前記更新エレメント管理データと、当該更新エレメント管理データのうち、前記依存更新エレメントＩＤを有する前記更新エレメント管理データとを前記管理データ記憶部から抽出する更新管理データ抽出部と、抽出された前記更新エレメント管理データと、当該更新エレメント管理データにより管理される前記更新エレメントと、前記差分更新データとを前記通信端末に送信する更新データ配信部とを備え、前記通信端末が、少なくとも、受信した前記差分更新データ、前記更新エレメント及び前記更新エレメント管理データに基づいて、前記地図データを更新する地図更新部を備える。
【００１９】
さらに、本発明による地図データ配信システムは、前記更新管理データ抽出部が、前記所在領域を有する前記更新エレメント管理データを前記管理データ記憶部から抽出する処理を、前記地図データの更新に影響を与える前記依存更新エレメントＩＤを含まなくなるまで行う。
【００２０】
さらに、本発明による地図データ配信システムは、前記差分更新データが、ノードデータ及びリンクデータである。
【００２１】
さらに、本発明による地図データ配信システムは、前記配信要求が、前記通信端末の地図バージョン又は更新時間情報を含み、前記更新データ配信部は、前記更新管理データ抽出部が抽出した前記更新エレメント管理データの中から、前記配信要求に含まれる前記地図バージョン又は前記更新時間情報と同一又は後に取得した前記地図バージョン又は前記更新時間情報を有する前記更新エレメント管理データ及び前記更新エレメントを配信する。
【００２２】
さらに、本発明による地図データ配信システムは、前記地図データ配信装置が、入力された緯度及び経度からなる情報の集合であるルートデータから、道路ネットワークを表現するリンクデータと、リンクと既存道路が交差する点を表現するノードデータとを作成し、前記ノードデータ及び前記リンクデータに対し、既存の前記リンクデータ及び前記ノードデータと異なる情報を、補完の属性を有する前記差分更新データとして追加する補完更新エレメントと、さらに、当該補完更新エレメントを管理する補完更新エレメント管理データとを作成して前記記憶部に格納し、前記補完更新エレメントの地図領域と重なる前記所在領域を有し、かつ、最新の補完更新エレメント管理データが示す前記更新エレメントＩＤを、前記補完更新エレメント管理データにおける前記依存更新エレメントＩＤとして表現する補完地図情報作成部を備える。
【００２３】
さらに、本発明では、上記地図データ配信システムに用いる地図データ配信方法及び通信端末を提供する。
【発明の効果】
【００２４】
本発明によれば、利用者が任意でルート情報等から作成した補完地図情報と地図更新を共存させることが可能になり、定期的な更新地図情報より新しい地図や詳細な地図を、ルート情報として入手し、適用の可否も含め任意に利用する可能な地図データ配信システムを提供でき、さらに、当該システムに用いる地図データ配信方法を提供することができる。
【００２５】
さらに、地図更新時において、情報欠落や二重保持等の矛盾の発生が生じないため、従来の道路表示や経路探索アルゴリズムを変えることなく利用可能な通信端末を提供できる。
【発明を実施するための最良の形態】
【００２６】
以下に、本発明の実施の形態について、添付の図面を参照しながら詳細に説明する。
【００２７】
図１は、本発明の地図データ配信システムの一実施例を示す図である。
【００２８】
本実施例の地図データ配信システムは、ネットワーク４０に接続された地図配信サーバ１０と、ナビゲーション端末２０とを備える。ナビゲーション端末２０には、無線通信装置３０が接続されている。ナビゲーション端末２０は、この無線通信装置３０により無線基地局３１を経由してネットワーク４０に接続される。なお、無線通信装置３０は、ナビゲーション端末２０に内蔵することもできる。
【００２９】
地図配信サーバ１０は、ナビゲーション端末２０から受信した地図配信要求に従い、地図データの更新部分をナビゲーション端末２０に配信する。
【００３０】
図１に示すように、地図配信サーバ１０は、地図配信サーバ１０をネットワーク４０に接続するためのネットワークＩ／Ｆ（インターフェース）部１５、更新データ記憶部１２、管理データ記憶部１１、更新管理データ抽出部１３及び補完地図情報作成部１４を備え、ＣＰＵ(Central Processing Unit：不図示)とメモリー（不図示）に内蔵されるプログラムにより制御されている。
【００３１】
更新データ記憶部１２には、地図の構成物（地物）を単位とする地図更新データ（地図情報、道路ネットワーク情報）が記憶されている。地図更新データは、具体的には、図２に示すリンクデータテーブル、及び、図３に示すノードデータテーブルにより構成されている。このデータの内容により地図が表現される。さらにこのデータを削除・追加することで地図データの更新が達成される。
【００３２】
図４は、更新を説明するための図である。図４（ａ）に示す直線道路をＴ字路に変更するためには、図４（ｂ）に示すように、直線道路を構成するリンクｌｉｎｋ１を削除し、図４（ｃ）に示すように、一方のノードがｎｏｄｅ１で他方のノードがｎｏｄｅ３とするｌｉｎｋ２を追加し、一方のノードがｎｏｄｅ２で他方のノードがｎｏｄｅ３とするｌｉｎｋ３を追加し、一方のノードがｎｏｄｅ３で他方のノードがｎｏｄｅ４とするｌｉｎｋ４を追加する。この一連の追加・削除の指示データが、後述する更新エレメントであり、対象となるデータが更新データとなる。
【００３３】
管理データ記憶部１１は、図５に示す更新エレメントテーブル、及び、図６に示す更新エレメント管理テーブルを格納している。
【００３４】
更新エレメントテーブルは、地図データを更新するための追加・削除の指示データである更新エレメントが登録されている。更新エレメントは、更新エレメントを識別する更新エレメントＩＤ、後述する更新エレメントの種別、更新時の操作、更新対象となるデータの種類とそのＩＤを持つ。更新エレメントテーブルのレコード一つで、一個のリンクかノードの追加又は削除を表現する。図４で示したように、一連の追加・削除が発生する場合は、同一の更新エレメントＩＤを持つ複数のレコードで表現する。
【００３５】
更新エレメント管理テーブルは、更新エレメントを管理するデータが記録されている。図６に示すように、更新エレメント管理テーブルのレコードは、更新を識別する更新エレメントＩＤ、後述する更新エレメントの種別、更新が対象とする地図のバージョンと更新日付、更新データが表す地物が所在する地図領域（所在領域）、後述する依存更新エレメントのＩＤと依存先の更新エレメントの種別を持つ。なお、本実施例では、地物の最大ｘ座標値、最小ｘ座標値、最大ｙ座標値および最小ｙ座標値により特定される矩形で所在領域を表し、所在領域を特定するための情報として、この矩形の対角の頂点座標を用いる。依存更新エレメントＩＤおよび依存先種別は複数ある場合もある。
【００３６】
依存更新エレメントＩＤとは、地物の接続関係に影響を与える他の差分更新データであり、その更新より前に更新の適用が必要な更新エレメントのＩＤである。図７に更新エレメントの依存関係の例を示す。当初図７（ａ） に示すリンクｌｉｎｋ１からなる直線道路があり、その後図７（ｂ）に示すようにリンクｌｉｎｋ５、ｎｏｄｅ４とｎｏｄｅ５からなる道路が開通した。ここでリンクｌｉｎｋ５、ｎｏｄｅ４とｎｏｄｅ５からなる道路の追加を表現する更新エレメントを更新エレメント１とする。
【００３７】
さらに、その後図７（ｃ）に示すようにリンクｌｉｎｋ２、リンクｌｉｎｋ３およびリンクｌｉｎｋ４からなるＴ字路が追加され、この更新エレメントを更新エレメント２とする。ここで更新エレメント２は、更新エレメント１で追加されたｎｏｄｅ４の存在を前提とするため、依存関係が存在する。この場合、更新エレメント１が更新エレメント２の依存更新エレメントＩＤとなる。
【００３８】
更新エレメントの種別は、その更新の種別を表す。ナビゲーション端末２０の地図情報は、通常数ヶ月おきに最新版が発売される。このような通常の定期的な地図の更新に対する更新エレメントの場合、種別は「正規」となる。また、本実施例では、定期的な地図の更新以外に、任意の地図情報に基づいた地図更新の実施の形態を説明する。このような任意の更新を表現する更新エレメントの場合、種別は「補完」となる。以降、種別が正規の更新エレメントを正規更新エレメント、種別が補完の更新エレメントを補完更新エレメントと呼ぶ。
【００３９】
図８は、更新エレメントの依存関係を表示した例を示す図である。ここで四角は更新エレメントを、矢印は依存関係を表す。図６（ａ）の更新エレメント管理テーブルの例は、図８の波線で囲った部分の更新エレメントを表現している。図８において、地図データをＶｅｒ．１からＶｅｒ．２に更新する場合を想定する。Ｖｅｒ．１より新しい更新エレメントＩＤは、ｅ２１、ｅ２２、ｅ２３、ｅｒ０２が該当し、これらに依存関係を有する更新エレメントＩＤは、各々ｅ０１、ｅ１１、ｅ１３、ｅ１１となる。ところが、図８では、更新エレメントＩＤとして、ｅ０２、ｅ０３、ｅ０４、ｅ１２が存在する。これらのうち、ｅ０２、ｅ０４は、Ｖｅｒ．１の更新においては、依存関係を有しているが、Ｖｅｒ．２では、依存関係を有しない。よって、更新エレメント管理テーブルにはＶｅｒ．１の依存更新エレメントＩＤとして当該テーブル上にはリストされるものの、Ｖｅｒ．２の更新には必要とされない。
【００４０】
図１の説明を続ける。ネットワークＩ／Ｆ部１５は、ネットワーク４０を介してナビゲーション端末２０から地図配信要求を受信する地図配信要求受付部である。また、ネットワークＩ／Ｆ部１５は、ナビゲーション端末２０に地図の更新データを配信する更新データ配信部でもある。ここで、地図配信要求は、宛先である地図配信サーバ１０のネットワーク上のアドレス、送信元であるナビゲーション端末２０のネットワーク上のアドレス、及び、ナビゲーション端末２０にて地図データに反映済み（更新済み）の地図のバージョン情報又は更新時間情報である。更新データは、更新管理データ抽出部１３が抽出した更新エレメント管理データの中から、配信要求に含まれている地図バージョン又は更新時間情報と同一又は後に取得した地図バージョン又は更新時間情報を有する更新エレメント管理データ及び更新エレメントが含まれる。配信要求に含まれている地図バージョン又は更新時間情報より前の更新エレメント管理データ及び更新エレメントは排除される。
【００４１】
更新管理データ抽出部１３は、後述するアルゴリズムに従い、リンクデータ、ノードデータ、更新エレメント、更新エレメント管理データを抽出し、ネットワークＩ／Ｆ１５を使用してナビゲーション端末２０に送信する。図８において、上述したように、更新エレメント管理データには、地図データの更新に影響を与える依存更新エレメントＩＤと、当該地図データの更新に影響を与えない依存更新エレメントＩＤとの両方が含まれる。よって、更新管理データ抽出部１３は、上記地図データの更新に影響を与える依存更新エレメントＩＤを含むものはすべて抽出することになる。即ち、上記地図データの更新に影響を与える依存更新エレメントＩＤを含まなくなるまで抽出処理を行う。
【００４２】
補完地図情報作成部１４は、インターネット等を経由してルート情報を入手し、補完地図情報として、補完更新エレメント、リンクデータ及びノードデータを作成し、補完更新エレメントを管理データ記憶部に格納し、リンクデータ及びノードデータを更新データ記憶部に格納する。これらのデータの形式は、更新エレメントの種別が補完となっている以外は、他の地図情報と同様な形式である。
【００４３】
ルート情報（緯度経度情報の集合）から補完地図情報である補完更新エレメント、リンクデータ及びノードデータの作成は、次の二つのステップにより行われる。第一ステップは、ルート情報（緯度経度情報の集合）から、リンクおよびノードで表現される道路ネットワーク情報の作成、第二ステップは、作成した道路ネットワーク情報から、補完更新エレメントおよび最終的なリンクデータ、ノードデータの作成である。
【００４４】
第一ステップであるルート情報（緯度経度情報の集合）から道路ネットワーク情報の作成は、このルートと他の既存道路が交差する点にノードを設定し、ノード間をリンクで接続することで達成される。ルート情報から道路ネットワークの作成方式に関しては、例えば、特許文献特開２００７−１７９３７３号公報等、多くの公知技術があり利用可能である。この処理を実行することにより、ルート情報から、リンクデータとノードデータにより表現される道路ネットワーク情報（例えば、図４（ｃ）のような情報）が作成される。
【００４５】
図９〜１１は、補完更新エレメント作成を示すフローチャートである。図９に示すように、第二ステップとして、最初に、第一ステップで作成したリンクデータ全てに対し、地図配信サーバが保持している既存道路を表現するリンクデータと、マップマッチを実施し、マップマッチしなかった道路を追加道路として抽出する（１４１）。マップマッチとは、既存道路とリンク情報が同一の道路を示しているかの判定である。
【００４６】
具体的には、図１０のフローチャートで示すように、作成したリンクデータと地図配信サーバが保持している既存道路を表現するリンクデータとの道路形状座標列データの違いが、予め定めた一定以内の範囲に収まっているかをチェック（１５２）し、収まっていた場合をマップマッチ成功と判定する（１５３）。マップマッチに失敗したリンクデータは追加道路として保存し（１５５）、マップマッチに成功したリンクデータは既存道路と重なる道路としてそのデータを破棄する（１５４）。さらに、第一ステップで作成したノードデータに対し、上記（１５５）で保存したリンクが使用していないノードを破棄する（１５７）。
【００４７】
図９のフローチャートの説明を続ける。上記（１５５）、（１５７）で選択されたリンクデータおよびノードデータを追加する補完更新エレメントを更新エレメントテーブルに追加する（１４２）。
【００４８】
上記（１４２）で作成した更新エレメントを管理し依存関係を表現する、更新エレメント管理テーブルのデータを作成する（１４３）。
【００４９】
具体的には、図１１のフローチャートで示すように、更新エレメント管理テーブルの最新バーションの値を持つエントリに対し、更新エレメントＩＤは上記（１４２）で作成した更新エレメントＩＤ、種別は「補完」、バージョンはＮＵＬＬ、更新日付はこの処理を実施した日付又はルートデータが作成された日付、所在領域はこの更新エレメントのノードデータが存在する範囲であるレコードを追加する（１６１、１６２）。さらに、この更新エレメントと所在領域が重なる更新エレメント管理テーブルのエントリを検索し（１６３、１６４）、重なる場合は、依存先更新エレメントと依存先種別のカラムに、該当するエントリの更新エレメントＩＤを追加し、依存先種別に「正規」を追加する。ここで最新バーションの値を持つエントリだけを対象にしている理由は、最新の地図情報に対しての差分を作成するためである。
【００５０】
以上に述べたステップにより、補完更新エレメントが作成できる。
【００５１】
さらに、図１の説明を続ける。ナビゲーション端末２０は、自身が保持する地図データを用いて、地図表示、ルート探索、ルート誘導等のナビゲーション処理を行う。また、地図データに反映済み（更新済み）の地図バージョン情報を含む地図配信要求を、地図配信サーバ１０に送信して、地図配信サーバ１０から更新データを入手し、これを自身が保持する地図データに反映させる。
【００５２】
図１に示すように、ナビゲーション端末２０は、ナビゲーション端末２０を無線通信装置３０及び無線基地局３１を介してネットワーク４０に接続するためのネットワークＩ／Ｆ部２１と、配信要求部２２と、地図更新部２３と、地図データ記憶部２７と、ナビゲーション処理部２４と、ユーザへの情報表示およびユーザからの指示受付を行う画面入出力Ｉ／Ｆ２５と、管理データ記憶部２６とを備え、ＣＰＵ(Central Processing Unit：不図示)とメモリー（不図示）に内蔵されるプログラムにより制御されている。
【００５３】
管理データ記憶部２６は、地図配信サーバから依存関係リストとして配信された更新エレメント管理データを格納する。テーブル構成は、図６に示す地図配信サーバのそれと同様である。
【００５４】
配信要求部２２は、定期的あるいは画面入出力Ｉ／Ｆ２５で入力されたユーザの指示に従い地図配信要求を生成し、地図配信要求をネットワークＩ／Ｆ部２１を介して地図配信サーバ１０に送信する。ここで、地図配信要求とは、上述した更新エレメント管理データ、更新エレメント及び差分更新データの配信を要求することである。
【００５５】
ネットワークＩ／Ｆ部２１は、地図配信サーバ１０へ配信要求を送信する送信部と、地図配信サーバから更新エレメント管理データ、更新エレメント及び差分更新データを受信する受信部としての機能を備えている。
【００５６】
地図更新部２３は、配信要求部２２から受け取った更新エレメント管理データ、更新エレメント及び差分更新データからなる配信データを蓄積し、後述するアルゴリズムに従い地図更新を実行する。
【００５７】
地図データ記憶部２７は、リンクデータとノードデータを格納する。これらの情報は、地図配信サーバ１０中の更新データ記憶部に格納されるリンクデータとノードデータと同じフォーマットである。具体的なフォーマットを、図２、図３に示す。
【００５８】
リンクデータには、地図上の道路を構成する各リンクのリンクデータが登録される。図２は、リンクデータの内容の一例である。図示するように、リンクデータのレコードは、リンクを識別するためのリンクＩＤ、リンクが位置する領域を識別するための領域ＩＤ、リンクが表現する道路の幅員、一般道路、有料道路といったリンクの道路種別を示す種別フラグ、リンクの形状を示す点列（開始ノード、終了ノード、および、リンクの屈折地点等に所在する中間ノードからなる点列）の座標データである点列データ、リンクの開始ノードに付与されたノードＩＤ、リンクの終了ノードを有する。
【００５９】
ノードデータには、リンクデータに登録されているリンクを構成する各ノードのノードデータが登録される。図３は、ノードデータの内容の一例である。図示するように、ノードデータのレコードは、ノードを識別するノードＩＤ、ノードが位置する領域を識別する領域ＩＤ、ノードの座標データ、ノードを開始ノード又は終了ノードとするリンクの接続リンクＩＤを有する。
【００６０】
ナビゲーション処理部２４は、このリンクデータに登録されているリンクデータ、及び、ノードデータに登録されているノードデータを用いて、地図表示、ルート探索、ルート誘導等のナビゲーション処理を行う。
【００６１】
図１２は、補完地図情報の配信動作を説明する図である。
【００６２】
地図配信サーバ１０は、所定のイベントが発生すると、補完地図情報の配信を開始する。所定のイベントとは、ナビゲーション端末２０からの要求やネットワーク経由でのユーザの指示等があるがこれらに限定はされない。また、対象となる補完地図情報の指定方法は、領域、識別ＩＤ、作成日時、作成者等が考えられる。図１２では、領域を指定した場合の動作を説明する。
【００６３】
地図配信サーバ１０において、更新管理データ抽出部１３は、管理データ記憶部１１中の更新エレメント管理テーブルを検索し、指定された領域に存在する補完更新エレメントのレコードを抽出し依存関係リストとする（１２１）。
【００６４】
次に、更新管理データ抽出部１３は、依存関係リストをネットワークＩ／Ｆ部１５を通してナビゲーション端末２０に送付する（１２２）。ナビゲーション端末２０は、（１２２）で送付された依存関係リストを保存する。
【００６５】
続いて、更新管理データ抽出部１３は、（１２１）で作成した依存関係リストに基づき、更新エレメントテーブルから対応する補完更新エレメントを検索し、エレメントをネットワークＩ／Ｆ部１５を通してナビゲーション端末２０に送付する（１２３）。ナビゲーション端末２０は、（１２３）で送付された補完更新エレメントを保存する。
【００６６】
さらに、更新管理データ抽出部１３は、（１２１）で検索した補完更新エレメントが対象とするリンクデータ(リンクデータテーブルのレコード)とノードデータ(ノードデータテーブルのレコード)を検索し、レコードをネットワークＩ／Ｆ部１５を通してナビゲーション端末２０に送付する（１２４）。
【００６７】
ナビゲーション端末２０は、受信した依存関係リスト、更新エレメントおよびノードとリンクのデータを使用して地図を更新する（１２９）。ここでの地図更新の動作は、取得した補完更新エレメントの「操作」カラムの情報に基づき、対象となるリンク又はノードを、追加又は削除する処理である。
【００６８】
以上の動作により、利用者が任意でルート情報等から作成した補完地図情報を取り込むことができる。さらに、地図更新時において、情報欠落や二重保持等の矛盾の発生が生じないため、従来のカーナビの道路表示や経路探索アルゴリズムを変えることなく利用することが可能になる。
【００６９】
図１３は、ナビゲーション地図の更新、即ち、地図更新情報の配信動作を説明する図である。この処理は、前述の補完地図情報による地図更新ではなく、地図の定期的な更新（正規更新エレメントによる更新）の反映を対象としている。
【００７０】
ナビゲーション端末２０は、所定のイベントが発生すると、配信要求部２２が地図センターに、現在の地図バージョンを含む地図配信要求を作成し、ネットワークＩ／Ｆ部２１を介して地図配信サーバ１０に送信する（１０５）。所定のイベントとは画面入出力Ｉ／Ｆ２５を介したユーザの地図配信要求や、事前に設定された時刻や時間の経過等があるがこれらに限定はされない。
【００７１】
地図配信サーバ１０において、更新管理データ抽出部１３は、ネットワークＩ／Ｆ部１５を介してナビゲーション端末２０から地図配信要求を受信すると、後述する依存関係リスト作成処理を実施して依存関係リストを作成する（１０１）。そして作成した依存関係リストを、ネットワークＩ／Ｆ部１５を通してナビゲーション端末２０に送付する（１０２）。ナビゲーション端末２０は、（１０２）で送付された依存関係リストを保存する。
【００７２】
続いて、更新管理データ抽出部１３は、（１０１）で作成した依存関係リストに基づき、更新エレメントテーブルから対応する正規更新エレメントを検索し、エレメントをネットワークＩ／Ｆ部１５を通してナビゲーション端末２０に送付する。ナビゲーション端末２０は、（１０３）で送付された正規更新エレメントを保存する
さらに、更新管理データ抽出部１３は、（１０３）で検索した正規更新エレメントが対象とするリンクデータ(リンクデータテーブルのレコード)とノードデータ(ノードデータテーブルのレコード)を検索し、レコードをネットワークＩ／Ｆ部１５を通してナビゲーション端末２０に送付する（１０４）。
【００７３】
ナビゲーション端末２０は、受信した更新エレメント管理テーブル、更新エレメントおよびノードとリンクのデータを使用して後述する地図更新処理を実施し、地図が更新される（１０９）。
【００７４】
図１４は、図１３（１０１）に示す依存関係リスト作成処理を説明するフローチャートである。この動作を、図１５に示す依存関係リストの場合を例に説明する。
【００７５】
まず、取得したナビゲーション端末２０の地図バージョンより新しいバージョンの更新エレメントＩＤ（種別＝正規）を更新エレメント管理テーブルから抽出する（１１２）。図１５の例では、ナビゲーション端末２０の地図バージョンを、Ｖｅｒ．１とすると、更新エレメントｅ２１、ｅ２２、ｅ２３が該当する。
【００７６】
続いて、上記ステップ（１１２）で抽出した更新エレメントの依存先と同じ依存先を持つ更新エレメントＩＤ（種別＝補完）を更新エレメント管理テーブルから抽出する（１１３）。図１５の例では、更新エレメントｅｒ０２が該当する。
【００７７】
さらに、上記ステップ（１１２）で抽出した更新エレメントが依存する更新エレメントＩＤ（種別＝補完）を更新エレメント管理テーブルから抽出する（１１４）。図１５の例では、更新エレメントｅｒ０１が該当する。
【００７８】
そして、更新エレメント管理テーブル中のレコードの中で上記ステップ（１１１〜１１４）で抽出した更新エレメントＩＤを持つレコードを依存関係リストとする（１１５）。図１５の例では、更新エレメントｅ２１、ｅ２２、ｅ２３、ｅｒ０１、ｅｒ０２が該当し、図６（ｂ）に示す更新エレメント管理テーブルの更新エレメントＩＤに該当する。
【００７９】
図１６は、図１３（１０９）に示す地図更新処理を説明するフローチャートである。
【００８０】
最初に、依存関係リスト中の更新エレメント（種別＝補完）の操作を元に戻す。すなわち、（操作＝追加）で追加されたリンク／ノードを削除し、操作＝削除で削除されたリンク／ノードを追加する（１３２）。
【００８１】
続いて、依存関係リスト中の依存関係の順番に基づき、更新エレメントデータ(種別=正式)の操作を実施する（１３３）。
【００８２】
そして、依存関係リスト中の依存関係の順番に基づき、更新エレメントデータ(種別=補完)の操作を実施する（１３４）。ただしこの操作において、Ｖｅｒ．２の地図が更新エレメントデータ(種別=補完)の地図情報を含んでいた場合、同じ道路が二重に作成される。このため、手順（１３４）での補完更新エレメントによる地図情報作成は、次に示す手順を用い、同じ道路の二重作成を抑止する。
【００８３】
具体的には、リンクやノードを追加する場合、既に同じ位置にリンクやノードが存在した場合は追加操作を行わない。この処理により、同じ道路の二重作成を抑止する。同じ位置かどうかの判定は、ノードに対しては座標の一致で判断する。リンクに対しては、そのリンクが持つ始点ノードと終点ノードと同じ始点および終点ノードを保持する別のリンクが存在する場合、同一リンクが存在すると判断する。
【００８４】
以上の動作により、利用者が任意でルート情報等から作成した補完地図情報と地図更新を共存させることが可能になる。さらに、地図更新時において、情報欠落や二重保持等の矛盾の発生が生じないため、従来のカーナビの道路表示や経路探索アルゴリズムを変えることなく利用することが可能になる。
【図面の簡単な説明】
【００８５】
【図１】地図データ配信システムの一実施例を示す図である。
【図２】上記システムにおけるリンクデータテーブルの一構成例を示す図である。
【図３】上記システムにおけるノードデータテーブルの一構成例を示す図である。
【図４】上記システムにおける道路データの更新の一例を示す図である。
【図５】上記システムにおける更新エレメントテーブルの一構成例を示す図である。
【図６】上記システムにおける更新エレメント管理テーブルの一構成例を示す図である。
【図７】上記システムにおける更新エレメントの依存関係の一例を示す図である。
【図８】上記システムにおける更新エレメントの依存関係の表示の一例を示す図である。
【図９】上記システムにおける補完更新エレメント作成を説明するフローチャートである。
【図１０】上記システムにおける補完更新エレメント作成を説明するフローチャートである。
【図１１】上記システムにおける補完更新エレメント作成を説明するフローチャートである。
【図１２】上記システムにおける補完地図情報の配信動作を説明する図である。
【図１３】上記システムにおける地図更新情報の配信動作を説明する図である。
【図１４】上記システムにおける依存関係リスト作成処理を説明するフローチャートである。
【図１５】上記システムにおける更新エレメントの依存関係の表示の一例を示す図である。
【図１６】上記システムにおける地図更新処理を説明するフローチャートである。
【図１７】従来の地図ネットワークとそれに補完地図情報を適用した例を示す図である。
【図１８】従来の地図ネットワークとそれに補完地図情報を適用した他の例を示す図である。
【符号の説明】
【００８６】
１０…地図配信サーバ、１１…管理データ記憶部、１２…更新データ記憶部、１３…更新管理データ抽出部、１４…補完地図情報作成部、１５…ネットワークＩ／Ｆ、２０…ナビゲーション端末、２１…ネットワークＩ／Ｆ、２２…配信要求部、２３…地図更新部、２４…ナビゲーション処理部、２５…画面入出力Ｉ／Ｆ、２６…管理データ記憶部、２７…地図データ記憶部、３０…無線通信装置、３１…無線基地局、４０…ネットワーク、４１…インターネット。
【図１】
0005189838.tif 000002
【図２】
0005189838.tif 000003
【図３】
0005189838.tif 000004
【図４】
0005189838.tif 000005
【図５】
0005189838.tif 000006
【図６】
0005189838.tif 000007
【図７】
0005189838.tif 000008
【図８】
0005189838.tif 000009
【図９】
0005189838.tif 000010
【図１０】
0005189838.tif 000011
【図１１】
0005189838.tif 000012
【図１２】
0005189838.tif 000013
【図１３】
0005189838.tif 000014
【図１４】
0005189838.tif 000015
【図１５】
0005189838.tif 000016
【図１６】
0005189838.tif 000017
【図１７】
0005189838.tif 000018
【図１８】
0005189838.tif 000019