(57)【要約】【課題】差分データ量を少なくでき、かつ、容易に差分更新を行えるようにする。【解決手段】道路を構成するリンク等のオブジェクトに不変のリンクＩＤ（パーマネントリンクＩＤ）を付け、この不変のリンクＩＤを用いて描画データ、経路探索データ、経路誘導データにおける各レコードを記述して地図データを構成する。差分データの作成に際して、旧地図データＯＬＤＭと新地図データＮＥＷＭを比較して作成された差分データをナビゲーション装置２００に入力し、ナビゲーション装置において、地図記録媒体２０４に保存されている旧地図データと該入力された差分データを用いて旧地図データを新地図データに更新する。【選択図】    図１
2004287705.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーションに用いる地図データを保存する地図記録媒体において、
地図データに少なくとも、地図描画のために必要な多数のレコードで構成された描画データ、目的地までの経路探索に必要な多数のレコードで構成された経路探索データ、交差点における経路案内のために必要な多数のレコードで構成された経路誘導データを含ませ、道路を構成するリンク等のオブジェクトに不変のリンクＩＤを付与し、この不変のリンクＩＤを用いて前記描画データ、経路探索データ、経路誘導データにおける各レコードを記述すると共にリンクＩＤを用いて他のレコードを参照して構成された描画データ、経路探索データ、経路誘導データを記録してなるナビゲーション用地図記録媒体。
【請求項２】
旧地図データを新地図データに更新する地図データ更新方法において、
道路を構成するリンク等のオブジェクトに不変のリンクＩＤを付け、この不変のリンクＩＤを用いて描画データ、経路探索データ、経路誘導データにおける各レコードを記述すると共にリンクＩＤを用いて他のレコードを参照して地図データを構成し、
旧地図データと新地図データを比較して作成された差分データをナビゲーション装置に入力し、
ナビゲーション装置において、地図記録媒体に保存されている旧地図データと該入力された差分データを用いて旧地図データを新地図データに更新する、
ことを特徴とする地図更新方法。
【請求項３】
新地図データと旧地図データをバイト単位で比較し、
新地図データ領域と一致する旧地図データ領域の場所とサイズ、旧地図データと一致しない新地図データとの組を順番に配列して前記差分データを作成する、
ことを特徴とする請求項２記載の地図更新方法。
【請求項４】
新地図データを所定サイズのブロックに分割し、
対象ブロックと最も一致する旧地図データのブロックを求め、該旧ブロックの場所と該旧ブロック内における新地図データと異なる位置と該新地図データとで、前記対象ブロックを表現して前記差分データを作成する、
ことを特徴とする請求項２記載の地図更新方法。
【請求項５】
旧地図データを新地図データに更新するナビゲーション装置において、
道路を構成するリンク等のオブジェクトに不変のリンクＩＤを付け、この不変のリンクＩＤを用いて描画データ、経路探索データ、経路誘導データにおける各レコードを記述すると共にリンクＩＤを用いて他のレコードを参照して構成される地図データを保存する地図記録媒体、
旧地図データと新地図データを比較して作成された差分データを外部より取得する差分データ取得部、
地図記録媒体に保存されている旧地図データと外部より取得した差分データを用いて旧地図データを新地図データに更新する地図更新手段、
を備えたことを特徴とするナビゲーション装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ナビゲーションに用いる地図データを保存する地図記録媒体、地図データ更新方法及びナビゲーション装置に係わり、特に、旧地図データを新地図データに更新する差分データ量を少なくでき、しかも、容易に地図データの更新ができる地図記録媒体、地図データ更新方法及びナビゲーション装置に関する。
【０００２】
【従来の技術】
従来のナビゲーションシステム及びデジタル地図は、読込み専用メディアであるＣＤ  （コンパクトディスク）やＤＶＤ（デジタルバーサタイルディスク）などで供給されていた。このため、差分更新という考えがなかった。
近年、通信技術の発展により配信による地図データの供給や読み書き可能なハードディスク（ＨＤＤ）が利用されるようになってきてはいるが、はじめから差分更新を考慮した地図データのデータ構造や技術に関しては考えられていない。
【０００３】
図９は従来の地図データファイルの構造説明図であり、地図データファイルＭＰＦは地図描画機能のために必要な描画データＭＤＤ、目的地までの経路探索機能のために必要な経路探索データＰＳＤ、交差点における経路案内機能のために必要な経路誘導データＰＣＤ等を含んでいる。描画データＭＤＤは、地図を描画するために必要な文字、ポリゴン、道路等の描画データや交差点毎の誘導データ（案内データ）へのポインタを含んでおり、道路データにはリンクＩＤが付されている。経路探索データＰＳＤは、階層レベル毎に、リンクＩＤ付きの道路リンク情報や各リンクの交通規制情報を含んでいる。経路誘導データＰＣＤは、交差点拡大図表示用の交差点拡大図情報、案内情報（ランドマーク情報、進行方向、方面情報等）を含んでいる。
【０００４】
ところで、図９からわかるように、描画データＭＤＤはポインタにより直接経路誘導データＰＣＤの交差点拡大図情報／案内情報を指し示している。ポインタ（オフセットアドレス）を用いるため、一部の経路誘導データを更新（たとえば削除）して空き部分を詰めたり、あるいは所定の分類をしてデータを再配置すると、交差点拡大図情報／案内情報のアドレス（基準位置からのオフセット）が変化し、全てのポインタ情報を更新しなければならなくなる。
また、描画データと経路探索データは共にリンクＩＤを使用し、このリンクＩＤによって経路探索結果を経路描画データに反映して探索経路を描画するようにしている。しかし、従来のＩＤリンクは、地図データ更新毎に付け替えが行われて全て変わってしまうために、全てのリンクＩＤを更新しなければならない。
【０００５】
図１０は経路探索データＰＳＤにおける道路データの構造例であり、固定長レコードで構成された道路データオフセットテーブルＲＤＯＴ、可変長レコードの道路属性情報テーブルＲＤＴＴ、可変長レコードの道路接続情報テーブルＲＣＮＴが示されている。道路データオフセットテーブルＲＤＯＴには、道路データ作成毎にユニークに付与される道路番号が格納される。また、道路属性情報テーブルＲＤＴＴ内の対応したレコードまでのオフセットＰｉ、道路接続情報テーブルＲＣＮＴ内の対応したオフセット情報Ｑｉなどが格納される。道路属性情報テーブルＲＤＴＴは、▲１▼道路毎に道路の種別、▲２▼幅員、▲３▼車線数、▲４▼道路形状などの情報が格納される。道路接続情報テーブルＲＣＮＴは、道路毎に道路間の接続情報や規制情報が格納される。なお、以上のほかにも付加情報によって、１つの道路データが複数のデータテーブルに格納される。
【０００６】
上記地図データの差分更新例を説明する。なお、上記道路データの道路番号Ｎｏ．１の道路を削除するものとする。
・道路Ｎｏ．１の道路データオフセットＲＤＯＴのレコードＲ１０の削除。
・道路Ｎｏ．１の道路属性情報レコードＲ１１の削除。
・道路Ｎｏ．１の道路接続情報レコードＲ１２の削除。
・道路Ｎｏ．１に接続する道路接続情報レコードの接続、規制情報の変更。
・道路Ｎｏ．１の各データを削除した事による他のオフセット情報を全て変更。
・道路Ｎｏ．１に接続する道路接続情報レコードの接続、規制情報を変更した事によるレコードサイズの変化に伴い、道路データオフセットテーブル内で影響のでるレコードのオフセット情報の変更。
【０００７】
以上のように１道路の削除だけでも、複数のデータレコードに影響する差分更新が大量に発生してしまう。オフセット情報などは、複数の条件によって同じ場所に何回も変更要因が発生し、複雑になってしまい、更新ミスにつながる恐れもある。また、更新の方法は、地図データの構造（フォーマット）を意識した形式であり、機能毎にそれらの処理を作成しなければならない。
以上の様に、従来の地図データの構造は、データ容量や処理の効率化のために、１ファイルに複数の機能、データを格納し、それぞれのデータ間の紐付けを直接ポインタ（オフセットアドレス）等で指定していた。また、データの種類によってレコードを複数に分けて格納していた。しかし、かかる地図データ格納方法では、差分を作成する際に差分データが多岐に渡って発生し、その結果、差分データ量も増え、差分データの作成や更新も非常に困難なものになってしまっている。
【０００８】
従来、更新を差分によって行うと共に、機能（描画情報、経路探索情報、ランドマーク情報）毎に更新処理を行う技術がある（例えば、特許文献１参照）。たとえば、描画情報は、差分データを送るが該差分データで旧描画情報を変更せず該差分データを地図記録媒体にそのまま保存する。そして、地図描画に際して、旧描画情報で地図を描画すると共に、差分データを用いて変更部分の地図を描画する。また、ランドマーク情報は差分データを送らず最新のランドマーク情報をすべて送って上書き更新する。経路探索情報は、差分データを送り、旧経路探索情報と該差分データとで新経路探索情報を作成して更新し、更新後の新経路探索情報を地図記録媒体に上書き更新し、該新経路探索情報を用いて経路探索を行う。
【特許文献１】特開平１１−９５６５７号公報（段落００４５〜００５４、図５￣図８）
【０００９】
【発明が解決しようとする課題】
特許文献１の従来技術は、地図データの種類に応じてその更新処理の方法を変えるものであるが、経路探索情報については依然として差分データを作成し、この差分データを用いて新経路探索情報を作成して更新する。しかし、特許文献１は図１０で説明した従来の問題点を解決するための技術を何も提案していない。すなわち、従来の地図データ構成では、差分データが多岐に渡って発生し、その結果、差分データ量も増え、差分データの作成や更新も非常に困難なものになってしまっているが、特許文献１はかかる問題点を解決するための技術を何も提案していない。
また、特許文献１は、機能毎に更新処理を変更するものであるため、新たな機能が付加された場合に該機能に応じた更新処理を検討する必要がある。
以上から、本発明の目的は、合理的に差分更新を行えるようにすることである。すなわち、差分データ量を少なくでき、かつ、容易な方法、構成で、かつ、統一した方法で差分更新を行えるようにすることである。
【００１０】
【課題を解決するための手段】
本発明の第１は、ナビゲーションに用いる地図データを保存する地図記録媒体であり、▲１▼地図データに少なくとも、地図描画のために必要な多数のレコードで構成された描画データ、目的地までの経路探索に必要な多数のレコードで構成された経路探索データ、交差点における経路案内のために必要な多数のレコードで構成された経路誘導データを含ませ、▲２▼道路を構成するリンク等のオブジェクトに不変のリンクＩＤを付与し、この不変のリンクＩＤを用いて前記描画データ、経路探索データ、経路誘導データにおける各レコードを記述すると共にリンクＩＤを用いて他のレコードを参照して構成された描画データ、経路探索データ、経路誘導データを記録媒体に記録してナビゲーション用の地図記録媒体を形成する。
【００１１】
本発明の第２は、旧地図データを新地図データに更新する地図データ更新方法であり、▲１▼道路を構成するリンク等のオブジェクトに不変のリンクＩＤを付け、この不変のリンクＩＤを用いて描画データ、経路探索データ、経路誘導データにおける各レコードを記述すると共にリンクＩＤを用いて他のレコードを参照して地図データを構成し、▲２▼旧地図データと新地図データを比較して作成された差分データをナビゲーション装置に入力し、▲３▼ナビゲーション装置において、地図記録媒体に保存されている旧地図データと該入力された差分データを用いて旧地図データを新地図データに更新する。
【００１２】
本発明の第３は旧地図データを新地図データに更新するナビゲーション装置であり、▲１▼道路を構成するリンク等のオブジェクトに不変のリンクＩＤを付け、この不変のリンクＩＤを用いて描画データ、経路探索データ、経路誘導データにおける各レコードを記述すると共にリンクＩＤを用いて他のレコードを参照してすると共にリンクＩＤを用いて他のレコードを参照して構成される地図データを保存する地図記録媒体、▲２▼旧地図データと新地図データを比較して作成された差分データを外部より取得する差分データ取得部、▲３▼地図記録媒体に保存されている旧地図データと外部より取得した差分データを用いて旧地図データを新地図データに更新する地図更新手段、を備えている。
以上の本発明の地図記録媒体、地図データ更新方法、ナビゲーション装置によれば、差分データ量を少なくでき、しかも、容易な方法かつ構成で、差分更新を行なうことが可能となる。
【００１３】
【発明の実施の形態】
（Ａ）本発明の地図データ構成例
図１、図２は本発明の地図データ構成説明図である。
地図データファイルＭＰＦは、▲１▼地図描画のために必要な多数のレコードで構成された描画データＭＤＤ、▲２▼目的地までの経路探索に必要な多数のレコードで構成された経路探索データＰＳＤ、▲３▼交差点における経路案内のために必要な多数のレコードで構成された経路誘導データＰＣＤ等を含んでいる。
【００１４】
描画データＭＤＤは、地図を描画するために必要な文字、ポリゴン、道路等の描画データや交差点毎の誘導データ（案内データ）へのポインタを含んでいる。道路データには従来の構成とは異なり、不変のリンクＩＤ（パーマネントリンクＩＤ）が付与されている。経路探索データＰＳＤは、階層レベル毎に、道路リンク情報や各リンクの交通規制情報を含んでおり、道路リンク情報にはパーマネントリンクＩＤが付与されている。経路誘導データＰＣＤは、交差点拡大図表示用の交差点拡大図情報、案内情報（ランドマーク情報、進行方向、方面情報等）を含んでおり、これらにはパーマネントリンクＩＤが付与されている。
【００１５】
例えば、図２に示す道路ＲＤの描画データＭＤＤにはパーマネントリンクＩＤ（＝ＰＬＮｏ．１）が付与され、該道路ＲＤの経路探索データＰＳＤには同一のパーマネントリンクＩＤ（＝ＰＬＮｏ．１）が付与され、該道路ＲＤの交差点Ｎ２の経路誘導データＰＣＤにはパーマネントリンクＩＤ（＝ＰＬＮｏ．１′）が付与される。描画データＭＤＤはポインタとしてこのパーマネントリンクＩＤ（＝ＰＬＮｏ．１′）を用いて交差点Ｎ２の経路誘導データを指示する。
【００１６】
以上のように、本発明では、機能に応じたデータ（描画データ、経路探索データ、経路誘導データ）間をオフセットアドレスで直接指定したりせずに、グローバルな不変のパーマネントリンクＩＤを利用して機能間を紐つけることによって、機能毎の独立性を向上させた。これにより、更新されていない機能については影響を与える事無く余分な差分データが発生しないようになる。また、地図データの作成毎に全て変更になる従来のリンクＩＤとは異なり、更新されていない道路データのパーマネントリンクＩＤは不変であるため余分な差分データが発生しないようになる。
【００１７】
図３は本発明の経路探索データＰＳＤにおける道路データの構造例であり、図１０の従来例のように道路種別や接続情報などのカテゴリー毎にテーブル化されていない。すなわち、図３のデータ構成では、１つの道路に付随する情報を全て１つのレコードに集約し、接続情報などはパーマネントリンクＩＤによって表現することによって、更新された道路に関連するレコードを変更するだけで更新が行なえるようになっている（レコード単位の独立性が高い）。
例えば、図４の点線に示すように、新たな道路０４が追加される場合、差分データは、
▲１▼パーマネントリンクＩＤ  ０４の道路レコードを作成するために必要なデータと、▲２▼追加道路０４が接続する道路０１，０３に応じたレコードに、接続道路のパーマネントリンクＩＤ  ０４を追加するに必要なデータ、
となる。
【００１８】
又、図４の道路０３を削除する場合、差分データは、
▲１▼削除道路に応じたレコードを削除するに必要なデータ、
▲２▼削除道路が接続していた道路０１，０２に応じたレコードから、削除道路のパーマネントリンクＩＤ  ０３を削除するに必要なデータ、
となる。
【００１９】
（Ｂ）地図更新システムの構成図
図５は本発明の地図更新システムの構成図であり、センター装置１００とナビゲーション装置２００は通信回線（無線回線、インタネット等）を介して通信可能に接続されている。
センター装置１００において、差分抽出部１０１は後述する方法により、旧地図データＯＬＤＭと新地図データＮＥＷＭの差分データを作成し、該差分データを通信インターフェース１０２を介してナビゲーション装置２００に送信する。
ナビゲーション装置２００のＨＤＤ制御部２０１は通信インターフェース２０２を介して差分データを取り込み、地図更新部２０３は差分データを用いてハードディスクＨＤＤ  ２０４に保存されている旧地図データＯＬＤＭを新地図データＮＥＷＭに更新する。これにより、ナビゲーション装置２０５は以後更新された新地図データに基づいてナビゲーション制御を実行する。
【００２０】
（Ｃ）差分データの作成処理
・差分データ作成の第１の方法
図６は差分データ作成の第１の方法説明図であり、新地図データＮＥＷＭと旧地図データＯＬＤＭをバイト単位で比較し，▲１▼新地図データ領域と一致する旧地図データ領域を検索し、該旧地図データ領域の先頭アドレスとサイズ、▲２▼旧地図データと一致しない新地図データの組を順番に配列して前記差分データを作成する。
【００２１】
図６において、矢印で双方を指し示している個所が新旧で同一の領域である。旧地図データＯＬＤＭにおける不一致領域データＤＬＴＭは破棄され、新地図データＮＥＷＭにおける不一致領域データＡ〜Ｄは差分データとして追加される。同一の旧地図データ領域は、該領域の先頭アドレスＡＤｉとサイズＳｉで特定される。図６の例では、差分データは図７に示すようになる。すなわち、
差分データの構成は、
・新ファイル：Ａデータ
・旧ファイル：１データ指定（先頭アドレスＡＤ１，サイズＳ１）
・新ファイル：Ｂデータ
・旧ファイル：３データ指定（先頭アドレスＡＤ３，サイズＳ３）
・新ファイル：Ｃデータ
・旧ファイル：２データ指定（先頭アドレスＡＤ２，サイズＳ２）
・新ファイル：Ｄデータ
となる。
【００２２】
・差分データ作成の第２の方法
図８は差分データ作成の第２の方法説明図であり、新地図データを所定サイズ（１６〜６４バイト程度）のブロックＢＬＫ１〜ＢＬＫｎに分割し、最初の対象ブロックＢＬＫ１と最も一致する旧地図データのブロックを先頭より１バイトづつシフトしながら比較（スキャン比較）して求め、▲１▼最も一致する旧ブロックの場所（先頭アドレス）と、▲２▼該旧ブロック内における新地図データと異なる位置と、▲３▼該新地図データとで、前記対象ブロックＢＬＫ１を表現し、以後、対象ブロックを順次ＢＬＫ２〜ＢＬＫｎまで変えて前記差分データを作成する。以上の▲１▼〜▲３▼のデータは、
最大一致エリアの先頭アドレス＋Σ（ブロック内の不一致アドレス＋新データ）のように表現できる。
【００２３】
・差分データ作成処理について
図１〜図４で説明した地図データの構造改善によってデータをレコード単位にした事により、連続するある領域において旧ファイルと新ファイルで全く同じ個所が多く存在する事になる。本発明の差分データ作成法は、この条件を利用して、新地図データファイルを圧縮する方法である。
通常、圧縮するために辞書ファイルを作成するが、本発明の差分データ作成法では、辞書ファイルに旧ファイルを利用する。
当然、新ファイルと旧ファイルとで同じデータ領域が多いほど圧縮率が向上する。
差分が余りにも多いときは、旧ファイルが辞書として機能せず、単純に新ファイルを自己圧縮したほうがデータサイズが小さくなる。この場合は、通常の自己圧縮を採用する方法もある。
【００２４】
【発明の効果】
以上、本発明の地図記録媒体、地図データ更新方法、ナビゲーション装置によれば、地図更新時における差分データ量を少なくでき、しかも、容易な方法かつ構成で、差分データを作成できる。
また、本発明によれば、差分データの作成処理及び更新処理を統一化でき、機能データに応じて種々の差分データ作成処理手順及び新地図データの更新処理手順を用意する必要がなく処理を簡略化できる。
また、本発明によれば、地図データ構造を意識せず、機械的に更新が可能となり、更新処理の簡易化及び高速化が可能となる。
【図面の簡単な説明】
【図１】本発明の地図データ構成例である。
【図２】本発明の地図データ構成説明図である。
【図３】本発明の経路探索データＰＳＤにおける道路データの構造例である。
【図４】道路の追加、削除時の差分データの説明図である。
【図５】本発明の地図更新システムの構成図である。
【図６】差分データ作成の第１の方法説明図である。
【図７】差分データの構成例である。
【図８】差分データ作成の第２の方法説明図である。
【図９】従来の地図データファイルの構造説明図である。
【図１０】経路探索データＰＳＤにおける道路データの構造例である。
【符号の説明】
１００  センター装置
１０１  差分抽出部
２００  ナビゲーション装置
２０１  ＨＤＤ制御部
２０３  地図更新部
２０４  ハードディスクＨＤＤ
２０５  ナビゲーション装置
ＯＬＤＭ  旧地図データ
ＮＥＷＭ  新地図データ
【図１】
2004287705.tif 000003
【図２】
2004287705.tif 000004
【図３】
2004287705.tif 000005
【図４】
2004287705.tif 000006
【図５】
2004287705.tif 000007
【図６】
2004287705.tif 000008
【図７】
2004287705.tif 000009
【図８】
2004287705.tif 000010
【図９】
2004287705.tif 000011
【図１０】
2004287705.tif 000012