(57)【要約】【課題】現在に至るまでの全ての隣接区画組での全てのバージョン組を保持することなく更新する区画を決定する地図更新装置を得る。【解決手段】更新区画抽出部は、地図を更新する更新範囲が指定されたときに、更新範囲に対し、更新範囲と共通部分をもつ更新グループと、前記更新範囲と共通部分をもつ更新グループから参照できる旧バージョン更新グループとに属する区画を、更新する区画として抽出するとともに、更新する区画に対し、更新する区画が属する更新グループまたは旧更新グループのうち最新のバージョンを更新する区画の更新バージョンとして決定する。【選択図】図１
2014240920.tif 000002
【特許請求の範囲】
【請求項１】
更新時のバージョン毎の地図データと、前記地図データの更新のあった区画を管理する更新管理データとを記憶する記憶部と、
同時に更新する必要のある区画を更新グループにグループ分けする領域区分部と、
前記更新グループと共通の区画を有し、前記更新グループのバージョンより古いバージョンの前記地図データの更新時の更新グループである旧バージョン更新グループを参照できるようにして構造化された前記更新管理データを生成する領域構造化部と、
地図を更新する更新範囲が指定された場合、前記更新管理データに基づき、更新する区画と、前記更新する区画毎の更新バージョンとを決定する更新区画抽出部と、
前記地図データを参照し、前記更新する区画を前記区画毎に決定した更新バージョンに更新するための更新データを生成する更新データ生成部と、
通信ネットワークを介して、端末装置から前記更新範囲と、前記端末装置の地図データの更新状況を更新グループで示す更新状況データとを受信し、前記端末装置に前記更新データを送信する通信部とを備え、
前記更新区画抽出部は、
前記地図を更新する更新範囲が指定されたときに、前記更新範囲に対し、前記更新範囲と共通部分をもつ前記更新グループと、前記更新範囲と共通部分をもつ前記更新グループから参照できる前記旧バージョン更新グループとに属する区画を、前記更新する区画として抽出するとともに、前記更新する区画に対し、前記更新する区画が属する前記更新グループまたは前記旧更新グループのうち最新のバージョンを前記更新する区画の更新バージョンとして決定する
ことを特徴とする地図更新装置。
【請求項２】
前記更新区画抽出部は、
前記更新状況データと前記更新管理データとに基づき、前記更新状況データから前記端末装置の地図データの区画の現有バージョンを再現し、前記更新する区画毎の更新バージョンについて、前記現有バージョンと比較して、前記現有バージョンより新しいバージョンの区画のみを前記更新する区画とする
ことを特徴とする請求項１記載の地図更新装置。
【請求項３】
前記更新区画抽出部は、
前記更新状況データと前記更新管理データとに基づき、前記更新範囲と共通部分をもつ前記更新グループおよび前記更新範囲と共通部分をもつ前記更新グループから参照できる旧更新グループのうち、前記更新状況データから特定される更新グループおよび当該更新グループから参照できる更新グループを除いた更新グループに含まれる区画を前記更新する区画として抽出するとともに、前記更新する区画に対し、前記更新グループの集合に含まれ、前記更新する区画が属する更新グループのうち最新のバージョンを前記更新する区画のバージョンとして決定する
ことを特徴とする請求項１記載の地図更新装置。
【請求項４】
前記領域区分部は、
隣接する区画をまたがって地物の追加、削除、移動、属性変更があった場合に、前記隣接する区画を同一の更新グループとして領域を区分する
ことを特徴とする請求項１記載の地図更新装置。
【請求項５】
前記領域区分部は、
隣接する区画にともに地物の変更があった場合に、前記隣接する区画を同一の更新グループとして領域を区分する
ことを特徴とする請求項１記載の地図更新装置。
【請求項６】
更新時のバージョン毎の地図データと、前記地図データの更新のあった区画を管理する更新管理データとを記憶する記憶部と、
同時に更新する必要のある区画を更新グループにグループ分けする領域区分部と、
端末装置から地図を更新する更新範囲が指定された場合、前記更新管理データに基づき、更新する区画を抽出する更新区画抽出部と、
前記端末装置から要求のあった区画の前記地図データを前記記憶部から読み出し、配信を制御する配信制御部と、
通信ネットワークを介して前記端末装置との通信を行なう通信部とを備え、
前記更新抽出部は、
前記更新範囲と共通部分をもつ前記更新グループに属する区画を前記更新する区画として抽出し、
前記配信制御手段は、
前記更新する区画を示す前記地図データを、前記通信部を介して前記端末装置に送信する
ことを特徴とする地図更新装置。
【請求項７】
請求項１から請求項５のうちのいずれか１項記載の地図更新装置と、
地図データと、前記地図データの更新状況を更新グループで示す更新状況データとを記憶する記憶部と、
地図を更新する更新範囲を指定する更新範囲指定部と、
前記地図更新装置との通信を行う通信部と、
前記地図更新装置から送信された前記更新データにより前記地図データの更新を行う地図更新部とを備えた端末装置とで構成され、
前記地図更新装置は、前記端末装置から受信した前記更新範囲と前記更新状況データとに対する更新データを生成すると共に、前記受信した更新状況データを更新して前記端末装置に送信し、
前記端末装置は、前記地図更新装置から受信した更新データにて前記地図データの更新をする区画のバージョンを前記更新バージョンに更新するとともに、前記地図更新装置から受信した更新状況データにて前記更新状況データを更新する
ことを特徴とする地図更新システム。
【請求項８】
請求項６に記載の地図更新装置と、
地図データの一部の区画を区画バッファとして記憶する記憶部と、
前記区画バッファの更新を制御する更新制御部と、
前記地図更新装置との通信を行う通信部と、
前記地図更新装置から受信する区画単位の地図データを区画バッファに格納する地図更新部とを備えた端末装置とで構成され、
前記地図更新装置は、前記端末装置にて指定された更新範囲に対し、前記更新する区画を示すデータを前記端末装置に送信し、
前記端末装置は、前記地図更新装置から受信した前記更新する区画のうち前記区画バッファに対応している区画を抽出して、前記抽出した区画についての前記更新データを前記地図更新装置に要求し、
前記地図更新装置は、前記端末装置に対して前記要求に対応した前記更新データを送信し、
前記端末装置は、前記地図更新装置から受信した前記更新データにより前記区画バッファに対応している区画を更新する
ことを特徴とする地図更新システム。
【請求項９】
地図更新装置にて随時更新される地図の更新された区画を管理する地図の更新管理方法であって、
領域区分部が、同時に更新する必要のある区画を更新グループとして領域にグループ分けするステップと、
領域構造化部が、前記更新グループと共通の区画を有し、前記更新グループのバージョンより古いバージョンの前記地図データの更新時の更新グループである旧バージョン更新グループを参照できるようにして構造化された前記更新管理データを生成するステップとを有する
ことを特徴とする地図の更新管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、地図データを用いるカーナビゲーション装置やモバイルコンピュータ、パーソナルコンピュータ、あるいは携帯電話等の端末装置に対して、地図データの更新データを送信する地図更新装置、地図更新装置を用いて随時更新した地図を端末装置上に表示する地図更新システム、および地図の更新管理方法に関するものである。
【背景技術】
【０００２】
カーナビゲーション装置によるナビゲーションや地図表示検索ソフトウエアにおいては、地図データに示される状況が現在の実際の状況に合致するように、用いる地図データはできるだけ最新のデータに更新しておく必要がある。地図データは、例えば一ヶ月に一度というように更新されるため、その更新分を反映した更新データによりカーナビゲーションや地図システムを行う端末装置の地図データを更新していくことになる。このような地図データの更新において、端末が保有する全国あるいは全世界といった範囲の地図データをすべて更新するのではなく、主として用いる部分のみのデータを部分的に更新することで、配信する更新データの量およびカーナビゲーション装置での更新処理時間を節約する技術が開示されている（特許文献１）。
【０００３】
特許文献１では、地図を区分した区画ごとにデータ化した地図において、指定した更新領域内にて更新のあった区画については保有する地図データも更新するとともに、その更新区画に隣接する隣接区画についても、区画間で道路ネットワーク接続の整合が保障されるように、最新あるいは過去の更新データによる更新を追加して行うようにしている。例えば、更新領域外でも必要に応じて更新のあった区画を更新し、また、更新領域内外の今回更新のない区画においても、過去の更新データを用いて更新を実行することがある。この更新する区画はサーバにて決定し、必要な更新データを端末装置に送信する。道路ネットワークに不整合を生じることなく、更新領域近傍に限定した必要な部分のみの更新を実現している。
【０００４】
また、サーバの地図データを、コンピュータネットワークを用いて随時ダウンロードして利用する地図情報システムにおいて、サーバの更新された地図データを、端末装置のキャッシュに保持されたダウンロード済みの更新前の地図データに代えて用いる技術が示されている（特許文献２）。特許文献２では、地図の新規表示やスクロールにて新しい描画部分が必要になった場合、ウェブブラウザのキャッシュ管理機能を用いることにより、例えば、キャッシュに保持された地図データの更新時刻とサーバの地図データの更新時刻とを対比して最新の地図データを用いるように構成している。あるいは、地図データのダウンロード時に、新規の更新された地図データが存在する場合に、そのバージョン番号をサーバからブラウザに通知し、以降、ブラウザはそのバージョンを指定したＵＲＬにより識別される地図データをダウンロードするように構成する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１１−１５８３３９号公報
【特許文献２】特表２００７−５３１００４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１に示すような地図更新装置にあっては、隣接区画との道路ネットワークの接続の整合をとるため、隣接区画にまたがるような道路ネットワーク要素に変更が生じ、両者をともに更新しなければ整合がとれなくなる時点の両者のバージョンの組を、すべての隣接区画組について、過去から現在まですべて保持する。隣接区画との整合の判定では、両区画のバージョンが、その区画組のバージョン組を参照して整合しているものかどうかを判定する。そうでない場合には、隣接区画を整合するバージョンまで更新するように、順次更新区画として追加していく。このように動作するため、隣接区画間のバージョンの組を、すべての隣接区画組について、過去から現在に至るまですべて保持しておかなければならないという課題があった。
【０００７】
さらに、端末装置に対する更新区画を決定する際には、端末装置が保持する地図について、必要な区画の現有のバージョン情報を参照するため、すべての区画の現有のバージョン情報をサーバである地図更新装置に保持するか、あるいは、端末装置から地図更新装置に通知しなければならないという課題があった。さらに、更新区画を決定するには、更新区画と隣接する区画のバージョンとその隣接区画組のバージョン組のデータを参照しつつ、更新の要求ごとに毎回隣接する区画を順次探索して更新が必要か否かの判定を行わなければならないという課題があった。
【０００８】
また、特許文献２に示すような地図情報システムにあっては、新規に必要になる区画について最新のバージョンの地図を得るように構成されている。何らかの操作、例えば、パン操作（地図のスクロール操作）においては、順次表示エリアの移動先の必要な区画をダウンロードしていく。このため、ダウンロード済みの地図に隣接する区画の地図を新たにダウンロードする場合、その時点で地図が更新されたとすると、隣接する区画の地図は新しいバージョンになる。このため、古いバージョンの地図と新しいバージョンの地図が隣接することになり、その境界部に図形の過不足やずれが生じる恐れが出てくるという課題があった。このように、パン操作などの操作において、地図に不整合が生じるという問題点があった。
【０００９】
この発明は、上記のような課題を解決するためになされたものであり、現在に至るまでの全ての隣接区画組での全てのバージョン組を保持することなく更新する区画を決定する地図更新装置を得ることを目的としている。さらに、端末装置が現有する地図の全ての区画のバージョン情報をサーバである地図更新装置に保持あるいは端末装置から地図更新装置に送信することなく、更新する区画を決定する地図更新装置を得ることを目的としている。さらに、隣接する区画を探索することなく更新区画の決定を行う地図更新装置を得ることを目的としている。
またこの発明は、地図システム上において、区画の境界部に不整合が生じないようにパン操作を実行する地図情報システムを得ることを目的としている。
【課題を解決するための手段】
【００１０】
この発明に係る地図更新装置は、更新時のバージョン毎の地図データと、前記地図データの更新のあった区画を管理する更新管理データとを記憶する記憶部と、同時に更新する必要のある区画を更新グループにグループ分けする領域区分部と、前記更新グループと共通の区画を有し、前記更新グループのバージョンより古いバージョンの前記地図データの更新時の更新グループである旧バージョン更新グループを参照できるようにして構造化された前記更新管理データを生成する領域構造化部と、地図を更新する更新範囲が指定された場合、前記更新管理データに基づき、更新する区画と、前記更新する区画毎の更新バージョンとを決定する更新区画抽出部と、前記地図データを参照し、前記更新する区画を前記区画毎に決定した更新バージョンに更新するための更新データを生成する更新データ生成部と、通信ネットワークを介して、端末装置から前記更新範囲と、前記端末装置の地図データの更新状況を更新グループで示す更新状況データとを受信し、前記端末装置に前記更新データを送信する通信部とを備え、前記更新区画抽出部は、前記地図を更新する更新範囲が指定されたときに、前記更新範囲に対し、前記更新範囲と共通部分をもつ前記更新グループと、前記更新範囲と共通部分をもつ前記更新グループから参照できる前記旧バージョン更新グループとに属する区画を、前記更新する区画として抽出するとともに、前記更新する区画に対し、前記更新する区画が属する前記更新グループまたは前記旧更新グループのうち最新のバージョンを前記更新する区画の更新バージョンとして決定するものである。
【発明の効果】
【００１１】
この発明によれば、同時に更新する必要のある区画を更新グループとして領域にグループ分けし、共通の区画を有するそれ以前のバージョンの更新での更新グループを参照できるようにして更新管理データとして構造化したことにより、地図を更新する範囲が指定されたときに更新管理データにより更新する区画とその更新バージョンを容易に特定できるという顕著な効果を奏するものである。
また、同時に更新する必要のある区画を更新グループとして領域にグループ分けして更新管理データとすることにより、地図を更新する範囲が指定されたときに更新管理データにより更新する区画を容易に特定できるという顕著な効果を奏するものである。
【００１２】
また、地図更新装置は同時に更新する必要のある区画を更新グループとして領域にグループ分けし、共通の区画を有するそれ以前のバージョンの更新での更新グループを参照できるようにして更新管理データとして構造化し、通信ネットワークにて結ばれた端末装置が指定する更新範囲に対し、更新管理データにより更新する区画とその更新バージョンを容易に特定し、更新データとして端末装置に送信できる、といった従来にない顕著な効果を奏するものである。
【００１３】
また、地図更新装置は同時に更新する必要のある区画を更新グループとして領域にグループ分けし、通信ネットワークにて結ばれた端末装置が指定する更新範囲に対し、更新管理データにより更新する区画を容易に特定し、その情報を端末装置に送信できる、といった従来にない顕著な効果を奏するものである。
また、同時に更新する必要のある区画を更新グループとして領域にグループ分けし、共通の区画を有するそれ以前のバージョンの更新での更新グループを参照できるようにして更新管理データとして構造化したことにより、地図を更新する範囲が指定されたときに更新管理データにより更新する区画とその更新バージョンを容易に特定できる、といった従来にない顕著な効果を奏するものである。
【図面の簡単な説明】
【００１４】
【図１】この発明の実施の形態１に係る地図更新装置の構成を示すブロック図である。
【図２】この発明の実施の形態１に係る端末装置の構成を示すブロック図である。
【図３】地図更新装置において、地図データの区画の更新の一例を示す図である。
【図４】端末装置から更新が要求された場合に、地図更新装置において、更新グループのうち、端末装置に対して更新データを送信すべき更新グループを特定する例を説明する図である。
【図５】最新のバージョンの更新グループと共通部分をもつそれ以前のバージョンの更新グループが存在する場合の例を示す図である。
【図６】図５に示す状態の地図データについて、更新する区画を説明する図である。
【図７】領域構造化部によってはられる、新しい更新グループからそれ以前のバージョンの更新グループへのリンクの一例を示す図である。
【図８】更新範囲内に更新グループがあった場合の、更新が必要な更新グループ集合を説明する図である。
【図９】更新区画抽出部が、図８に基づき確定した更新を要する区画とそのバージョンを説明する図である。
【図１０】端末装置の地図データのバージョンの例を示す図である。
【図１１】更新データ生成部が生成する、端末装置用の新たな根更新グループのデータの一例を示す図である。
【図１２】地図データの更新により新しいバージョンの地図が与えられた時点の地図更新装置の動作のフローチャートである。
【図１３】領域区分部がまとめた更新グループのデータの例を示す図である。
【図１４】端末装置からの要求に対して、必要な更新データを作成し端末装置に送信する場合の地図更新装置の動作を示すフローチャートである。
【図１５】更新範囲をあらわすデータの一例である。
【図１６】端末装置端末装置が記憶している更新状況データの一例である。
【図１７】端末装置の動作を示すフローチャートである。
【図１８】この発明の実施の形態２に係る地図更新装置の動作を示すフローチャートである。
【図１９】実施の形態２に係る地図更新装置において、更新を要する更新グループの抽出方法の一例を説明する図である。
【図２０】この発明の実施の形態３に係る端末装置の構成を示すブロック図である。
【図２１】この発明の実施の形態３に係る地図更新装置１の構成を示すブロック図である。
【図２２】この発明の実施の形態３に係る端末装置の構成を示すブロック図である。
【図２３】区画バッファとクリッピング範囲の一例を示す図である。
【図２４】区画バッファの更新の一例を説明する図である。
【図２５】この発明の実施の形態３の端末装置の動作を示すフローチャートである。
【図２６】地図更新装置が送信する候補区画データの一例を示す図である。
【図２７】この発明の実施の形態３に係る地図更新装置の動作を示すフローチャートである。
【図２８】実施の形態３の地図更新装置の更新管理データの一例を示す図である。
【図２９】実施の形態３の地図更新装置において、端末装置からの要求に対して、候補区画データを求める動作を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、この発明の実施の形態について、図面を参照しながら詳細に説明する。
実施の形態１．
図１は、この発明の実施の形態１に係る地図更新装置１の構成を示すブロック図である。
図１に示すように、地図更新装置１は、記憶部４と、領域区分部５と、領域構造化部６と、更新区画抽出部７と、更新データ生成部８と、通信部９とを備える。また、記憶部４は、地図データ２と更新管理データ３とを記憶している。
記憶部４は、記憶手段であるハードディスクやメモリであり、記憶部４が記憶している地図データ２は、地図情報である。また、記憶部４が記憶している更新管理データ３は、地図の更新区画をグループ化し階層化グラフで表現したデータである。
領域区分部５は、同時に更新する必要のある区画を更新グループとしてグループ分けする領域区分手段である。
【００１６】
領域構造化部６は、領域区分部５がグループ分けした更新グループを、更新グループと共通の区画を有し、それ以前の（更新グループのバージョンより古いバージョンの）更新時の更新グループ（旧バージョングループ）を参照できるように構造化した更新管理データ３とする領域構造化手段である。
更新区画抽出部７は、地図を更新する範囲が指定されたときに更新管理データから更新を要する区画と、更新を要する区画毎の更新バージョンとを決定する更新区画抽出手段である。
更新データ生成部８は、更新を要する区画を、その区画毎に決定した更新バージョンに更新するための更新データを生成する更新データ生成手段である。
通信部９は、カーナビゲーション装置などの端末装置１１との通信を行う通信手段である。
【００１７】
図２は、この発明の実施の形態１に係る端末装置１１の構成を示すブロック図である。
端末装置１１は、例えば、カーナビゲーション装置やパーソナルコンピュータなどであり、地図更新装置１と、コンピュータネットワークや有線、無線の通信回路などの通信ネットワーク１０で結ばれることにより、地図更新システムを構成している。
図２に示すように、端末装置１１は、記憶部１４と、更新範囲指定部１５と、通信部１６と、地図更新部１７と、地図表示部１８とを備える。また、記憶部１４は、地図データ１２と、更新状況データ１３とを記憶している。
【００１８】
記憶部１４は、記憶手段であるハードディスクやメモリであり、記憶部１４が記憶している地図データ１２は、地図情報である。また、記憶部１４が記憶している更新状況データ１３は、地図データ１２の更新状態を示す更新状況データである。
更新範囲指定部１５は、地図を更新する範囲を指定する更新範囲指定手段である。
通信部１６は、地図更新装置１との通信を行う通信手段である。
地図更新部１７は、地図更新装置１から送信された地図更新データにより、記憶部１４に保有する地図データ１２の更新を行う。
地図表示部１８は、地図更新部１７が更新した地図データ１２に基づく地図をディスプレイなどの表示部に表示する。なお、表示部は、端末装置１１が備えるものとしてもよいし、端末装置１１の外部に表示装置を備えるものとしてもよい。
【００１９】
カーナビゲーションの利用においては、地図表示や経路探索などでは、例えば使用者が居住する地域など使用する地図の範囲が限られる場合が多い。その範囲に絞って部分的に更新を行うことにより、更新データの通信量および更新にかかる処理を節約することができる。この実施の形態１においては、端末装置１１にて地図の更新範囲を指定してそれを地図更新装置１に送信し、地図更新装置１では、端末装置１１から受信した更新範囲にかかる区画を確実に最新の地図に更新し、さらに、その周囲との道路ネットワークや描画される地物の整合をとるような、更新範囲の周囲で更新が必要になる区画とその更新バージョンを決定して更新する各区画の更新データを端末装置１１に送信し、端末装置１１では、地図更新装置１から受信した更新データにより保有する地図データ１２の更新を行う実施の形態について説明する。
【００２０】
なお、地図データは領域で区分された区画ごとに分割して保持されているものとし、更新データもその区画ごとに生成される。更新データは新しいバージョンの地図データあるいは、古いバージョンの地図データを新しいバージョンに変更するための差分を示すデータである。
また、区画はタイルとも呼ばれるものであり、例えば緯度経度による座標値を等間隔で分割した領域、あるいは、平面直角座標にて地図を画像として表したときに一定の画素サイズで分割した領域などである。一般に、複数の分割の幅あるいは縮尺を採用することで、複数の詳細度レベルが設定されるが、以下では単一のレベルでの動作を説明する。複数レベルにおいては、それぞれのレベルについてその動作を繰り返すことで地図の更新を実行する。
【００２１】
ここで、まず更新グループについて詳しく説明する。
地図更新装置１では、領域区分部５により地図データ２の更新のあった更新区画をグループに分け、領域構造化部６が、領域区分部５がグループ分けした更新グループを、それ以前の更新、つまり古いバージョンでの更新グループ（旧バージョン更新グループ）を参照できるように構造化した更新管理データ３を生成する。
図３は、地図更新装置１において、地図データ２の区画の更新の一例を示す図である。
図３に示すように、地図データ２は区画１９に分割され、バージョンＶ０からバージョンＶ１への更新で、区画Ａと区画Ｂにまたがる道路２０が新設されたとする。この場合、区画Ａのみを更新すると、道路２０はバージョンＶ１の区画ＡとバージョンＶ０の区画Ｂでつながらない。このように、区画１９をまたがって地物の追加、削除、位置変更がある場合、両区画を同時に更新しないと、その境界部２１で地物の過不足や座標のずれ（以下、不整合と記す）が生じる。
【００２２】
そこで、領域区分部５は、隣接し同時に更新する必要がある区画を領域としてまとめ、これを更新グループ２２とする。同一の更新グループ２２になるのは、隣接する区画にまたがって道路や地物の設置（データの追加）、撤去（データの削除）、移動（データの座標値変更）、属性変更などの変更などがあった場合である。また、より単純には、同じバージョンへの更新において、共に地物の変更のあった隣接する区画である。なお、前者のような地物の変更があった場合には、隣接する区画は共に同時に変更が発生するため、後者においても同一の更新グループ２２に属することになる。ここで、周囲との整合が問題にならない単独の変更区画も一つの更新グループ２２とし、変更のあった区画は、必ず一つの更新グループ２２に属するようにする。
更新グループ２２単位で区画を更新すれば、その周囲の区画とは整合がとれるので、更新の際に不整合は発生しない。
【００２３】
図４は、端末装置１１から更新が要求された場合に、地図更新装置１において、更新グループ２２のうち、端末装置１１に対して更新データを送信すべき更新グループ２４を特定する例を説明する図である。
端末装置１１から更新範囲２３が指定されて更新が要求された場合、地図更新装置１は、更新グループ２２のうちその更新範囲２３に全部あるいは一部が含まれる更新グループ２４を抽出し、その更新グループ２４を構成する区画２５を更新区画とする。隣接区画を探索しなくても、更新グループ２２と更新範囲２３との交差判定によって更新区画２５を決定することができる。このようにして、更新グループ２２のうち更新範囲２３と共通領域をもつ更新グループ２４を抽出し、この区画を更新することになる。
【００２４】
地図データの更新が例えば定期的に実行される場合、領域構造化部６では、各更新バージョンの更新グループ２２を階層的に管理する更新管理データ３を生成する。例えば、最新のバージョンでの地図データ２の更新グループ２２は、その直前のバージョンの地図データ２に対して、整合して更新することができる。最新のバージョンの更新グループ２２の区画が、それ以前のバージョンの更新グループ２２と共通部分をもつ、つまり重畳する場合、そのそれ以前のバージョンの更新グループによる更新を行わないと、最新の更新グループ２２の更新で周囲の区画との不整合が起きることがある。これを図５によって説明する。
図５は、最新のバージョンの更新グループ２２と共通部分をもつそれ以前のバージョンの更新グループ２２が存在する場合の例を示す図である。なお、図５において、バージョンＶ０は初期状態、最新のバージョンＶｍ、以前のバージョンＶｎとする。
【００２５】
以前のバージョンＶｎの更新グループ２６では道路などである地物２７が変更されている。また、更新グループ２６と共通の区画２８をもつ新しいバージョンＶｍの更新グループ２９では地物３０が変更されている。図に示すように、地物２７の更新が共通の区画２８とそれ以外の区画に及んでいる場合、新しいバージョンＶｍの更新グループ２９の更新において以前のバージョンＶｎの更新グループ２６の更新が行われていないと、地物２７は区画２８に含まれる部分のみが更新された状態となり、それ以外の区画では更新されない。このため、その隣接区画間で不整合を生じることになる。したがって、重畳する以前のバージョンの更新グループは、たとえ更新範囲２３に入っていなくても、新しい更新グループ２９の更新に合わせて、更新を実行しなければならない。もちろん、共通する区画は、新しいバージョンに更新する。
図６は、図５に示す状態の地図データについて、更新する区画を説明する図である。なお、図６の更新範囲２３は、端末装置１１によって指定された更新範囲とする。
地図更新装置１は、更新範囲２３に入る新しいバージョンＶｍの更新グループ２９の更新にあたり、以前のバージョンの更新グループ２６に属する区画ついても更新を行うことになる。
【００２６】
そこで、領域区分部５が、地図データ２の更新時に、つまり、最新のバージョンＶｍへの更新時に、更新のあった区画を更新グループ２２に区分するとともに、領域構造化部６は、以前のバージョンＶｎの更新グループ２６を簡易に得るため、各更新グループについてそれ以前のバージョンＶｎの更新グループ２６と共通区画をもつかどうかを判定し、共通の区画をもつ場合は、新しいバージョンＶｍの更新グループ２９から、それ以前のバージョンＶｎの更新グループ２６を参照するためのリンクデータをはる。これはつまり、新しいバージョンＶｍの更新グループ２９と、重畳するそれ以前のバージョンＶｎの更新グループ２６とを特定するデータ、例えば、更新グループを特定する識別番号を組にしてデータ化し、容易にその情報を得られるようにする。このようにすることで、図６に示すような更新グループ２９，２６を簡単に特定することができる。
【００２７】
図７は、領域構造化部６によってはられる、新しい更新グループからそれ以前のバージョンの更新グループへのリンクの一例を示す図である。なお、図７では、バージョンＶ０が初期状態で、以降、バージョンＶ１，Ｖ２，Ｖ３と更新され、変更のあった区画のみをハッチング等によって表している。バージョンＶｉ，ｉ＝１，２，３のｊ番目の更新グループをそれぞれＧｉｊと表記し、共通区画をもつそれ以前のバージョンの更新グループを矢印で表現している。
【００２８】
図７に示すように、新しい更新グループ２２からそれ以前のバージョンの更新グループ２２へのリンク３１は、更新グループ２２をノード３２とするグラフを構成するので、これを更新グラフ３３とする。なお、このグラフ構造を表すデータを更新グループ２２のデータから独立させて保持してもよい。地図データ２の更新は順次実行されるため、更新グループ間のリンクは何層にもわたることになる。したがって、ある更新グループについて更新を行う場合、区画間の不整合を防ぐためには、更新を行なう更新グループ２２からリンク３１が張られている更新グループ２２を全て更新することになるが、更新グラフ３３をたどることにより、更新が必要となる区画とそのバージョンを容易に特定することができる。
【００２９】
なお、ある更新グループ２２からのリンクでたどれるそれ以前のバージョンの更新グループ（旧バージョン更新グループ）を、その更新グループ２２の下位の更新グループということにする。この更新グラフ３３にて管理された更新グループ２２のデータが、更新管理データ３である。更新管理データ３は、記憶部４に記憶される。
【００３０】
次に、更新区画抽出部７が、図７で説明したような、更新グラフ３３で管理された更新グループ２２から、指定された更新範囲２３に対して更新する区画を抽出する動作について説明する。
端末装置１１から通信部１６を介して端末装置１１が指定した更新範囲２３を地図更新装置１の通信部９が受信する場合、つまり、地図を更新する更新範囲２３が指定された場合、更新区間抽出部７は、更新グラフ３３を検索し、更新範囲２３と共通部分をもつ更新グループ２２を抽出する。具体的には、更新範囲２３と共通部分をもつ更新グループ２２と、更新範囲２３と共通部分をもつ更新グループ２２から参照できる下位の更新グループとに属する区画を、前記更新する区画として抽出する。更新範囲２３が固定で地図データ２の更新ごとに端末装置１１の地図データ１２の更新も行っている場合には、最新のバージョンの更新グループのみから抽出する。ここで、各更新グループ２２は、例えばｋｄ木などの多次元データ管理構造によって管理し、更新範囲２３に入る更新グループ２２の検索を効率よく実行できるように構成してもよい。
【００３１】
次に、更新範囲２３内に更新グループ２２があった場合の、更新区画抽出部７による更新が必要な区画とそのバージョンの決定について説明する。
図８は、更新範囲２３内に更新グループ２２があった場合の、更新が必要な更新グループ集合を説明する図である。
図８において、更新が必要な更新グループ２２の集合を更新グループ集合Ｓ３４で表す。Ｓは、更新範囲２３内の更新グループ２２と、更新範囲２３内の更新グループ２２からのリンク３１でたどれる更新グループ２２の集合である。なお、更新グループを一つ選択すると、更新グラフ３３により、選択した更新グループ２２、および、選択した更新グループ２２からたどれる更新グループ２２が決定できる。以下では、この、選択した更新グループ２２からたどれる更新グループ２２を、その選択した更新グループ２２の更新部分グラフとする。また、更新部分グラフは木構造をなすことから、以下ではその木構造の根部分にあたる更新グループ２２を根更新グループとする。したがって、Ｓは、更新範囲２３内の更新グループ２２を根更新グループとする、更新部分グラフの少なくともひとつに属する更新グループ２２の集合である。なお、図８の左の図では、根更新グループからのリンクをわかりやすく表現するため、Ｓに入らない更新グループＧ３１からの矢印は描いていない。
【００３２】
更新区画抽出部７は、更新グループ集合Ｓに属する各更新グループ２２について、各更新グループ２２に含まれる区画をその各更新グループ２２のバージョンに更新するように設定していく。ただし、その区画について、既にその更新グループ２２より新しいバージョンでの更新が指定されている場合には、新しいバージョンでの更新を優先する。これにより、更新を要する区画とそのバージョンが確定する。
図９は、更新区画抽出部７が、図８に基づき確定した更新を要する区画とそのバージョンを説明する図である。
図９に示すように、更新が必要になる更新要求区画３５は、更新グループ集合Ｓの各更新グループの区画３６の和集合の区画であり、各区画３６の更新バージョンはその区画が含まれる更新グループ集合Ｓの更新グループ２２のうちの最も新しい更新グループのバージョンになる。図９でも新しいバージョンを優先して、ハッチングを変えて示している。
このようにして確定された更新を要する区画とその区画毎のバージョンに基づき、地図更新装置１は、端末装置１１へ更新データを送信することになる。
【００３３】
ただし、端末装置１１の地図データ１２も以前のある段階で更新を行っていることが考えられる。この場合は、端末装置１１の地図データ１２の各区画のバージョンよりも、図９で説明したような、更新要求区画３５のバージョンが新しい区画のみ更新を行うことになる。つまり、地図更新装置１は、端末装置１１の地図データ１２の各区画のバージョンよりも新しいバージョンの区画の更新データのみを端末装置１１へ送信する。そこで、地図更新装置１では、端末装置１１の地図データ１２の更新状況を把握する必要がある。端末装置１１の地図データ１２の更新状況の把握方法としては、端末装置１１の全区画の現有のバージョン情報を地図更新装置１に送信することも考えられるが、ここでは、過去の更新の際に更新を行った、ひとつあるいは複数の根更新グループのデータ（更新状況データ）を送信する。
【００３４】
端末装置１１が送信する根更新グループのデータは、過去の地図更新装置１での更新区画の選定の際に、更新区画抽出部７の抽出動作時に得られたもので、過去の更新時に更新データとともに端末装置１１に送信しておく。上述のとおり、根更新グループが指定されれば、その更新部分グラフ３３によって、更新された区画とバージョンが決定するので、同様に端末装置１１から送信された根更新グループのデータにより、端末装置１１の各区画の現有バージョンを復元し、復元した端末装置１１の各区画の現有バージョンと抽出した更新要求区画３５のバージョンとを比較することで、更新区画抽出部７は、更新する区画を絞り込むことができる。過去の根更新グループのデータは、例えば、更新グループを指定する識別番号であり、更新範囲２３にかかる根更新グループであるので、その数は全区画数に比べて格段に小さく、送信データ量が削減される。
【００３５】
図１０は、端末装置１１の地図データ１２のバージョンの例を示す図である。
例えば、図７に示すバージョンＶ２段階で更新グループＧ２２が更新範囲２３に入り、Ｇ２２を根更新グループとする更新を行なっていたとする。
この場合、端末装置１１の地図データ１２は、図１０のように、Ｇ２２とそれからリンクが張られているＧ１３の区画を、Ｇ２２のバージョンを優先して更新されていることになる。したがって、更新区画抽出部７は、図１０の更新状況と比較し、図９からすでに更新を満たしている区画を除くことで更新区画を絞り込む。絞り込みの結果、更新区画抽出部７は、例えば図９の更新要求区画３５の区画３６のうち、図１０でハッチングされ、かつ、バージョンを示すハッチングが同一である区画をすでに更新を満たしている区画として除き、これを更新区画と決定する。
【００３６】
次に、更新データ生成部８について説明する。
更新データ生成部８は、更新を要する区画についてそのバージョンへの更新データを記憶部４の地図データ２から読み出す。あるいは、記憶部４の地図データ２から作成して更新データとする。更新データは、各区画を置き換える指定されたバージョンの地図データ２であり、あるいは、各区画を端末装置１１の現有バージョンから指定されるバージョンに更新する差分データである。
【００３７】
また、更新データ生成部８は、更新範囲２３内で検索された更新グループ２２と端末装置１１から受信した根更新グループを統合して、端末装置１１用の新たな根更新グループを生成し、受信した根更新グループのデータを更新する。これは、更新範囲２３内の更新グループ２２と端末装置１１から受信した根更新グループとを合わせたデータのうち、重複するもの、および、他の更新部分グラフに含まれるものを除いたものになる。
図１１は、更新データ生成部が生成する、端末装置１１用の新たな根更新グループのデータの一例を示す図である。図１１において、更新範囲２３による更新後は、２個の区画グループＧ３２、Ｇ３３が根更新グループ３７を構成することになる。
【００３８】
通信部９は、更新データ生成部８が生成した更新データと新たな根更新グループのデータとを、通信ネットワーク１０を経由して端末装置１１に送信する。
端末装置１１では、地図更新装置１から送信された更新データにより地図データ１２を更新し、新たな根更新グループのデータにて更新状況データ１３を置き換える。
【００３９】
なお、地図更新装置１の記憶部４には、各バージョンの地図データ２、あるいは各バージョンの地図データ２間の差分データが格納され、この他、上述した更新グラフを含む更新管理データ３が格納される。地図データ２はデータベースによって管理されていてもよい。また、更新範囲２３は、例えば端末装置１１の使用者の居住する市町村や都道府県、あるいは行動範囲、また、端末装置１１の現在の存在地点、あるいは過去に移動した経路を包含する範囲などで、端末装置１１が自動的に設定してもよいし、使用者が自由に変更できるようにしてもよい。
【００４０】
次に、この発明の実施の形態１に係る地図更新装置１の動作の詳細について説明する。
図１２は、地図データ２の更新により新しいバージョンの地図が与えられた時点の地図更新装置１の動作のフローチャートである。なお、新しいバージョンの地図データ２は、既に記憶部４に格納されているものとする。
領域区分部５は、新しいバージョンの地図データ２と、１バージョン前の地図データ２を区画ごとに比較し、データの変更、つまり、更新があるかどうかを判定して、更新のある区画を抽出する（ステップＳＴ１）。ただし、新しいバージョンの地図データ２が、１バージョン前の地図データからの変更部分のみを抽出した差分データとして与えられている場合、その差分データが実質的な変更内容を含む場合に、その区画が更新のある区画として抽出する。
【００４１】
次に、領域区分部５は、ステップＳＴ１で抽出した更新のある区画を更新グループ２２に区分する（ステップＳＴ２）。これは、隣接する更新のある区画を一つのグループにまとめたものであり、あるいは、隣接区画上の地物データに変更があった場合に、隣接区画間をまとめたものである。
図１３は、領域区分部５がまとめた更新グループ２２のデータ３８の例を示す図である。図１３に示すように、更新グループ２２のデータ３８は、更新グループ２２の識別番号Ｇ0とバージョン番号Ｖ、および、属する区画の数Ｎと、それぞれの識別番号Ｔ1〜ＴNとの集合から構成される。なお、図１３は、後述するステップＳＴ３において付加されたリンクに関する情報も付加した例を示している。具体的には、リンクが張られている下位の、つまり、それ以前のバージョンの更新グループ２２へのリンク数Ｍとその更新グループ２２の識別場号Ｇ1〜ＧMである。
【００４２】
領域構造化部６は、ステップＳＴ２において領域区分部５が区分した更新グループ２２のデータ３８を受け取り、更新グループ２２を更新グラフ３３によって管理するデータを生成する（ステップＳＴ３）。具体的には、更新グループ２２と共通区画を有するそれ以前のバージョンの更新グループ２２を抽出し、抽出した以前のバージョンの更新グループ２２へのリンクを張ることにより実行する。各更新グループ２２については、例えば図１３に示したようなデータ形式で表し、これを更新管理データ３として記憶部４に記憶する。
地図の更新を更新管理データ３、つまり、更新グループ２２と更新グラフ３３で管理することで、更新された地図が与えられた場合の動作を完了する。
【００４３】
図１４は、端末装置１１からの要求に対して、必要な更新データを作成し端末装置１１に送信する場合の地図更新装置１の動作を示すフローチャートである。
地図更新装置１の通信部９は、端末装置１１より地図更新の要求と更新範囲２３、更新状況データ１３を受信する（ステップＳＴ１０１）。ここで、更新範囲２３は、例えば、緯度経度の範囲で指定される矩形である。
図１５は、更新範囲２３をあらわすデータの一例である。図１５のように、更新範囲２３は、緯度経度の下限（Ｂｓ，Ｌｓ）と上限（Ｂｅ，Ｌｅ）から構成されたデータ３９であらわされる。なお、更新範囲２３は、緯度経度の範囲で指定される矩形に限らず、区画の集合を指定するものでもよい。
【００４４】
端末装置１１から受信する更新状況データ１３は、それまでの更新での更新グループの根更新グループを示すもので、例えば、図１６に示すように個数Ｋと識別番号Ｒ1〜ＲKで構成されたデータ４０である。更新が行われていない場合、Ｋは０である。
【００４５】
更新区間抽出部７は、まず、ステップＳＴ１０１で受信した更新範囲２３と共通区画を有する更新グループ２２およびその更新部分グラフの更新グループ２２からなる更新グループ集合Ｓの更新グループ２２を更新管理データ３より抽出する（ステップＳＴ１０２）。更新範囲２３と共通区画を有する更新グループ２２は、更新範囲２３の示す緯度経度の範囲に含まれる区画を特定し、その区画が含まれる更新グループ２２を抽出するようにすればよい。
次に、更新区画抽出部７は、ステップＳＴ１０２で抽出した、更新範囲２３と共通区画を有する更新グループ２２から、不整合のない更新を実行するための更新区画を求める（ステップＳＴ１０３）。具体的には、ステップＳＴ１０２で抽出した更新グループ２２およびその更新部分グラフの更新グループからなる更新グループ集合Ｓの更新グループに対して、それに属する区画の和集合である更新要求区画３５を求め、その各区画３６に更新グループで指定されるバージョンのうち、最も新しいバージョンを指定する。更新区画抽出部７は、更新要求区画３５とその区画に指定されたバージョンを合わせ、更新要求区画データ４１とする（図９参照）。図９では更新要求区画３５に各区画に指定されたバージョン情報をハッチングを変えて示すことで更新要求区画データ４１を表している。更新範囲の更新を行うには、この更新要求区画データに示される区画をそのバージョンに更新することになる。
【００４６】
更新区画抽出部７は、ステップＳＴ１０１で受信した端末装置１１の更新状況データ１３から、端末装置１１の各区画がどのバージョンに更新されているかを示す現有区画データ４２（図１０参照）を求める（ステップＳＴ１０４）。具体的な現有区画データ４２の求め方は、ステップＳＴ１０３と同様、端末装置１１の根更新グループおよびその更新部分グラフの更新グループすべてに対して、それに属する区画の和集合である区画を求め、その各区画にこれら更新グループで指定されるバージョンのうち、最新のバージョンを指定すればよい。
【００４７】
更新区画抽出部７は、ステップＳＴ１０３で求めた更新要求区画データ４１と、ステップＳＴ１０４で求めた現有区画データ４２とを比較し、更新要求区画データ４１を補正する（ステップＳＴ１０５）。具体的には、更新要求区画データ４１にある区画が現有区画データ４２に含まれ、更新要求区画データ４１に指定されるバージョンが、現有区画データ４２に示される端末装置１１の現在のバージョンと同一であるか、それより以前のものである場合、その区画はさらに更新する必要がないので、更新要求区画データ４１から除く。つまり、更新要求区画データ４１に指定される区画について、端末装置１１がそのバージョンに達していない場合に、更新を実行するものとする。
【００４８】
更新データ生成部８は、ステップＳＴ１０５で更新区画抽出部７が補正した更新要求区画データ４１に記された各区画を、同じく更新要求区画データ４１に記されたバージョンに更新するための更新データを生成する（ステップＳＴ１０６）。
更新データ生成部８は、ステップＳＴ１０１で端末装置１１から受信した更新状況データ１３を更新する（ステップＳＴ１０７）。具体的には、更新状況データ１３に示された根更新グループに、更新範囲２３内で検索された更新グループ２２を付加し、その中で重複するもの、また、他の更新グループの更新部分グラフに含まれるものを除いたものになり、根更新グループとその更新部分グラフの更新グループとで、端末装置１１がこれまでに行った更新、つまり、各区画のバージョンを再現できる。
【００４９】
通信部９は、ステップＳＴ１０６で更新データ生成部８が生成した更新データと、ステップＳＴ１０７で更新データ生成部８が更新した更新状況データ、つまり、更新された根更新グループのデータを端末装置１１に送信する（ステップＳＴ１０８）。
【００５０】
図１７は、端末装置１１の動作を示すフローチャートである。端末装置１１は、例えばカーナビゲーション装置である。
端末装置１１の更新範囲指定部１５は、記憶部１４に保有する地図データ１２の更新範囲２３を設定する（ステップＳＴ２０１）。
通信部１６は、ステップＳＴ２０１で設定した更新範囲２３、および、記憶部１４に記憶している更新状況データ１３を地図更新装置１に送信する（ステップＳＴ２０２）。なお、これを受けて、地図更新装置１では、図１４のフローチャートに示す動作により、端末装置１１に向けた更新データを作成する。
【００５１】
通信部１６は、地図更新装置１から更新データと更新された更新状況データ１３を受信する（ステップＳＴ２０３）。
地図更新部１７は、ステップＳＴ２０３で通信部１６が受信した更新データにより記憶部１４の地図データ１２の更新を行う（ステップＳＴ２０４）。具体的には、更新データがそれに示す区画の地図データを置き換えるものであれば、その区画を置き換え、あるいは、区画の現有の地図データの差分を表すものであれば、現有の地図データの差分として与えられたデータを付加あるいは削除する。
また、ステップＳＴ２０４において、地図更新部１７は、ステップＳＴ２０３で通信部が受信した更新状況データで、更新状況データ１３を置き換える。
以降、地図表示部１８が、ステップＳＴ２０４で地図更新部１７が更新した地図データ１２を用いて地図の表示を行う。
【００５２】
このように、端末装置１１からの更新範囲２３を受け、地図更新装置１が、更新する区画とその更新バージョンを決定して更新データを作成し、端末装置１１に送信する。これは、更新範囲２３内を最新のバージョンに更新し、かつ、区画間での地物の整合をとるための、更新が必要となる最低限の区画である。端末装置１１では、地図更新装置１から更新データを受信して該当する区画の地図データ１２を更新する。
【００５３】
以上のように、実施の形態１によれば、少ない通信量と更新演算にて、日常必要となる範囲の地図を最新のものに更新することができる。また、更新が必要となる区画の選定に階層化した更新グループを用いているので、隣接区画間をその更新バージョンを比較しながら探索することなしに、更新区画と更新バージョンである更新データを得ることができる。
【００５４】
なお、この実施の形態１では、端末装置１１は地図データ１２の更新状況を更新状況データ１３により管理し、地図更新においても、その更新状況データ１３を地図更新装置１に送信するように構成したが、もちろん、各区画がどのバージョンであるかをすべて記憶部１４に記憶し、地図更新においても各区画の現在のバージョンの情報をすべて地図更新装置１に送信するように構成してもよい。この場合、図１４のステップＳＴ１０４は、すでに端末装置１１の地図データ１２の各区画のバージョンがわかっているので省略する。
また、図１４のステップＳＴ１０８では更新した根更新グループに代えて、更新データの区画の更新バージョンの情報を端末装置１１に送信する。端末装置１１では、ステップＳＴ２０３では更新データの区画の更新バージョンの情報を受信し、ステップＳＴ２０４での更新状況データ１３の更新に代えて、その更新バージョンにて更新する区画のバージョン情報を更新する。
【００５５】
また、この実施の形態１では、端末装置１１は地図データ１２の更新状況を更新状況データ１３により管理し、地図更新において、その更新状況データ１３を地図更新装置１に送信するように構成したが、更新状況データ１３は端末装置１１ではなく、地図更新装置１の記憶部４に保持するように構成してもよい。この場合、図１７のステップＳＴ２０２は、更新状況データ１３に代えて、端末装置１１がそれを識別する識別番号を地図更新装置１に送信する。図１４のステップＳＴ１０１では、地図更新装置１が、更新状況データ１３に代えて、端末装置１１を識別する識別番号を受信し、その識別番号に対応する更新状況データ１３を記憶部４から読み出す。また、図１４のステップＳＴ１０７では更新した更新状況データ１３を記憶部４に記憶する。端末装置１１では、ステップＳＴ２０３では更新した根更新グループのデータは受信せず、ステップＳＴ２０４での更新状況データ１３の更新も行わない。
【００５６】
実施の形態２．
実施の形態１では、地図更新装置１は、更新区画を抽出し（図１４のステップＳＴ１０３）、端末装置１１の更新状況を再現して（図１４のステップＳＴ１０４）、両者の比較を行って更新区画を決定する（図１４のステップＳＴ１０５）ように構成したが、この実施の形態２では、端末装置１１の更新状況を再現せずに動作させる実施の形態について説明する。
この発明の実施の形態２に係る地図更新装置１の構成は、実施の形態１で図１に示したものと同様であるため詳細な説明を省略する。また、この発明の実施の形態２に係る端末装置１１の構成についても、実施の形態１で図２に示したものと同様であるため詳細な説明を省略する。
【００５７】
図１８は、この発明の実施の形態２に係る地図更新装置１の動作を示すフローチャートである。なお、図１４に示す実施の形態１の地図更新装置１の動作と同一の動作については説明を省略する。また、地図更新装置１の地図データ２の新たなバージョンへの更新時の動作についても、実施の形態１において図１２を用いて説明したものと同様であるため詳細な説明を省略する。また、端末装置１１の構成と動作についても、実施の形態１で説明したものと同様であるため詳細な説明を省略する。
【００５８】
図１８のステップＳＴ１０１〜ステップＳＴ１０２、ステップＳＴ１０６〜ステップＳＴ１０８は、それぞれ、実施の形態１で図１３のステップＳＴ１０１〜ステップＳＴ１０２、ステップＳＴ１０６〜ステップＳＴ１０８で説明した動作と同一である。つまり、この実施の形態２に係る地図更新装置１の動作は、実施の形態１に係る地図更新装置１の動作から、端末装置１１の根更新グループから現有区画データを求める動作（図１４のステップＳＴ１０４）と、求められた現有区画データに基づき更新要求区画データを補正する動作（図１４のステップＳＴ１０５）を省略し、新たにステップＳＴ２１０３の動作を追加したものとなる。
【００５９】
実施の形態１で説明した、図１４のステップＳＴ１０３で得られた更新グループ集合Ｓの更新グループについて、その更新グループが端末装置１１の根更新グループのひとつあるいは複数の更新部分グラフに含まれる場合、その更新グループによって示される更新は、既に端末装置１１の地図データ１２に行われていることになる。その更新グループの下位の更新グループについても同様である。
【００６０】
したがって、更新グループが端末装置１１の更新状況データ１３の更新部分グラフに含まれる場合、その更新グループおよびその下位の更新グループは更新区画の決定において考慮しなくてもよい。
図１９は、実施の形態２に係る地図更新装置１において、更新を要する更新グループの抽出方法の一例を説明する図である。なお、ここでは、例えば、端末装置１１が、図１９に示すバージョンＶ２においてＧ２２の更新グループによる更新部分グラフの更新を行っていたとした場合を例に説明する。
【００６１】
図１９に示すように、更新範囲２３から決まる更新グループ集合Ｓに対して、端末装置１１の更新状況を示す更新部分グラフを除いたものが、真に更新を要する更新グループであり、これを更新グループ集合Ｓ’４３とする。
図１８のステップＳＴ２１０３において、更新区画抽出部７は、更新要求区画データ４１を得る際に、更新グループ集合Ｓの更新グループのうち、ステップＳＴ１０１で端末装置１１から受信した根更新グループから導き出される更新部分グラフに含まれるものを除いた更新グループ集合Ｓ’に属する区画のみを対象に抽出を行う。
【００６２】
他は、実施の形態１で説明した図１４のステップＳＴ１０３と同様の動作になる。つまり、上記更新グループ集合Ｓ’の更新グループすべてに対して、それに属する区画の和集合である区画を求め、その各区画にこれら更新グループで指定されるバージョンのうち、最新のバージョンを指定する。この動作にて、端末装置１１の現有の更新状況からの、さらなる更新区画のみが抽出されるので、図１４のステップＳＴ１０４とステップＳＴ１０５の動作は省略できる。
図２０は、図１９に示す更新グループ集合Ｓ’から得た更新要求区画データ４１の例である。
【００６３】
以上のように、実施の形態２によれば、更新グループ集合と端末装置１１の更新状況を示す更新部分グラフとを比較し、更新グループ集合のうち既に更新されている更新グループを除外することで、更新要求区画データ４１の作成時に勘案する更新グループ数を減らすことができ、処理の手間を軽減することができる。
【００６４】
実施の形態３．
従来技術においては、新規に必要になる区画について最新のバージョンの地図を得るように構成されていた。パン操作（地図のスクロール操作）においては、順次表示エリアの移動先の必要な区画をダウンロードしていく。このため、ダウンロード済みの地図に隣接する区画の地図を新たにダウンロードする場合、その時点で地図が更新されたとすると、隣接する区画の地図は新しいバージョンになる。このように、パン操作において、地図に不整合が生じるという課題があった。この実施の形態３では、地図システム利用中に新たに地図更新装置から取得した地図データが更新されている場合でも、区画の境界部に不整合が生じないようにパン操作を実行する地図情報システムを得ることができる実施の形態について説明する。
【００６５】
図２１は、この発明の実施の形態３に係る地図更新装置１の構成を示すブロック図である。
実施の形態１，２で図１に示したものと同様の構成については同じ符号を付し、重複した説明を省略する。実施の形態１，２で図１に示したものとは、領域構造化部６と更新データ生成部８とを備えず、配信制御部５２を追加した点が異なる。
配信制御部５２は、端末装置１１から要求のあった区画の地図データについて、記憶部４から読み出し、配信を制御する配信制御手段である。
【００６６】
図２２は、この発明の実施の形態３に係る端末装置１１の構成を示すブロック図である。なお、この実施の形態３において、端末装置１１とは、例えば、パーソナルコンピュータなどである。
実施の形態１，２で図２に示したものと同様の構成については同じ符号を付し、重複した説明を省略する。実施の形態１，２で図２に示したものとは、記憶部１４が地図データ１２および更新状況データ１３にかえて区画バッファ４４を記憶している点と、更新範囲指定部１５を備えず更新制御部４５を備えている点とが異なる。
区画バッファ４４は、地図データの一部の区画である。地図表示部１８は、区画バッファ４４の地図データをクリッピングしてディスプレイなどの表示部に表示する。なお、表示部は、端末装置１１が備えるものとしてもよいし、端末装置１１の外部に表示装置を備えるものとしてもよい。
更新制御部４５は、区画バッファ４４の更新を制御する。
なお、実施の形態１，２同様、地図更新装置１と端末装置１１とを有線あるいは無線のコンピュータネットワークや電話回線などである通信ネットワーク１０を介して結ぶことで地図更新システムを構成している。
【００６７】
パーソナルコンピュータなどで地図を表示し、現在位置の確認や目標地点の検索、ナビゲーションを行う地図システム利用においては、端末装置１１の記憶部１４に、現在表示中の領域を含み、これより広い領域を構成する一定数の区画の地図データを区画バッファ４４として記憶している。そして、地図表示部１８が、区画バッファ４４の範囲内で表示する領域を取り出すクリッピングを行い、地図データをディスプレイなどの表示部に表示する。
【００６８】
図２３は、区画バッファ４４とクリッピング範囲４６の一例を示す図である。
図２３に示すように、区画バッファ４４は、例えば緯度方向（図２３のａの方向）５区画、経度方向（図２３のｂの方向）５区画の矩形を構成する連続した区画になる。地図表示部１８が表示部に表示させた地図をパン（スクロール）する場合、表示するクリッピング範囲４６を順次区画バッファ４４の中で移動させていけば、区画バッファ４４の内部に限り、地図更新装置１との通信を行わずに、短時間で移動した領域の地図の表示を行うことができる。
なお、ここでは区画バッファ４４を、緯度方向，経度方向にそれぞれ５区画としたが、これに限らず、適宜設定可能とする。
【００６９】
図２４は、区画バッファ４４の更新の一例を説明する図である。
図２３に示す状態から、ユーザのスクロール動作などにより、クリッピング範囲４６が矢印の方向に移動したとする。このように、表示する範囲が区画バッファ４４を越えると、図２４に示すように、端末装置１１は、表示に必要な新たな区画の地図データを地図更新装置１に要求し、地図更新装置１から受信した新たな区画の地図データを区画バッファ４４に取り入れる。その際、新たな区画は、緯度方向の１列、または経度方向の１行にして、それから遠い部分の区画データと置き換えることとする。
【００７０】
この、区画バッファ４４の更新の際に、地図更新装置１の地図データ２が更新され、受信する区画の地図データ２が、その時点で区画バッファ４４に存在する地図データに対して新しいバージョンになっていた場合、端末装置１１は、新たに地図データ２が必要となる区画に加え、既存の区画についても整合をとるために必要な区画の更新を行う。
なお、この実施の形態３においても、実施の形態１，２と同様、地図更新装置１は、領域区分部５により、地図データ２の更新において更新のあった更新区画をグループに分ける。グループ分けの方法は実施の形態１で説明したものと同様であるため詳細な説明は省略するが、領域区分部５によりグループ分けされた更新グループ２２とは、隣接し同時に更新する必要がある区画を同一の更新グループ２２として一つにまとめたものである。
【００７１】
地図更新装置１で地図データ２の更新後に、端末装置１１が地図更新装置１に新たな区画の地図データを要求した場合、端末装置１１が地図データを要求した区画と区画バッファ４４に存在する区画とに更新グループ２２がまたがっていると、端末装置１１によって要求された区画の新しいバージョンと、区画バッファ４４内の、地図更新装置１から新たに取得した区画に隣接する区画の古いバージョンとが整合しなくなる。このため、区画バッファ４４内の区画についても必要な区画を新しいバージョンに更新する。すなわち、地図更新装置１の地図データ２に更新があった場合でも、区画バッファ４４内の区画間の整合がとれるようにする。
【００７２】
例えば、地図のパン操作時には、区画バッファ４４内のクリッピング範囲４６がパン操作に合わせて区画バッファ４４内を移動すると（図２３参照）、クリッピング範囲４６が区画バッファの範囲を越える場合には、区画バッファ４４が有する地図の範囲をクリッピング範囲４６を移動する方向にずらし、クリッピング範囲４６が区画バッファ４４内に収まるようにする（図２４参照）。図２３では、縦横５個の区画４８の区画バッファ４４においてクリッピング範囲４６が左に移動し、区画バッファ４４の範囲を越えようとしており、この時点で、破線で示した区画バッファの左側の区画１列を要求区画４７として、地図更新装置１に対して地図データを要求することになる。端末装置１１は、その後、地図更新装置１から要求区画４７を受信し、図２４に示すように、右側の１列の区画５０に代えて区画バッファ４４を再構成する。その時点で、地図更新装置１の地図データ２が更新されていた場合、新しく格納する要求区画４７のバージョンのみ上がることになるので、境界に不整合が生じる可能性が出る。これを解消するため、図２４に示すように、地図更新装置１では新しく格納する要求区画４７を含む更新グループ４９を抽出し、それに含まれる区画バッファ４４内の区画５１も更新する。
【００７３】
図２５は、この発明の実施の形態３の端末装置１１の動作を示すフローチャートである。
更新制御部４５は、パン操作によって新たな区画の表示が必要となった時点で、区画バッファ４４に読み込む要求区画４７を決定する（ステップＳＴ３２０１）。具体的には、図２４で説明したように、区画バッファ４４に対してクリッピング範囲４６が超える、あるいは接するような辺をはさんだ位置の区画になる。区画は、例えば、区画に割り当てられた識別番号、あるいは、その代表点の緯度経度の組によって特定する。
【００７４】
地図更新部１７は、ステップＳＴ３２０１で更新制御部４５が特定した要求区画４７の一つのデータの要求を、通信部１６を介して地図更新装置１に行う（ステップＳＴ３２０２）。これを受けて、地図更新装置１は、要求された区画の地図データを端末装置１１に送信する。
通信部１６は、地図更新装置１から区画の地図データを受信する（ステップＳＴ３２０３）。
地図更新部１７は、ステップＳＴ３２０３で通信部１６が受信した地図データで区画バッファ４４の区画を置き換える（ステップＳＴ３２０４）。
更新制御部４５は、未処理の要求区画４７があるかどうかを判定する（ステップＳＴ３２０５）。ステップＳＴ３２０５において、未処理の要求区画４７がある場合（ステップＳＴ３２０５の“ＹＥＳ”の場合）、つまり、要求区画４７の全ての区画について、地図更新部１７へ地図データを要求し、要求した区画の地図データを受信する処理を行なっていない場合、ステップＳＴ３２０２に戻る。
【００７５】
ステップＳＴ３２０５において、未処理の要求区画４７がない場合（ステップＳＴ３２０５の“ＮＯ”の場合）、つまり、要求区画４７の全ての区画について、地図更新部１７へ地図データを要求し、要求した区画の地図データを受信する処理を完了した場合、更新制御部４５は、地図更新装置１から受信した要求区画４７の地図データのバージョンを調べ、区画バッファ４４に現在格納されている、要求区画４７に隣接する区画の地図データのバージョンと比較し、要求区画４７が新しいバージョンに更新されているかどうかを判定する（ステップＳＴ３２０６）。具体的には、例えば、地図データがバージョン情報を有している場合はそれを用いてバージョン情報を比較することでバージョンが更新されているかどうかを判定すればよいし、あるいは、地図データの直前に改変された時刻の情報を比較することで判定するようにすればよい。
【００７６】
ステップＳＴ３２０６において、要求区画４７が新しいバージョンに更新されていなかった場合（ステップＳＴ３２０６の“ＮＯ”の場合）、要求区画４７の地図データは、区画バッファ４４の既存の区画の地図データと同一バージョンで整合していると判断し、処理を終了する。
ステップＳＴ３２０６において、要求区画４７が新しいバージョンに更新されていた場合（ステップＳＴ３２０６の“ＹＥＳ”の場合）、更新制御部４５は、通信部１６を介して要求区画４７についてその区画を識別するデータを地図更新装置１に送信する（ステップＳＴ３２０７）。これは、ステップＳＴ３２０３で地図更新装置１から受信した区画の地図データが、パン操作によって新たな区画の表示が必要になる前の区画バッファ４４にあった、要求区画４７に隣接する区画と整合しない可能性が出てくるためである。したがって、端末装置１１では、要求区画４７に隣接する必要な区画の更新を追加で実行する。
【００７７】
ステップＳＴ３２０７において、端末装置１１から要求区画４７の区画を識別するデータを受信すると、これを受けて、地図更新装置１は、要求区画４７と共通部分をもつ更新グループ２２に属する区画を候補区画データ５３として端末装置１１に送信する。
図２６は、地図更新装置１が送信する候補区画データ５３の一例を示す図である。
図２６に示すように、候補区画データ５３は、区画数Ｈと区画を示す識別番号Ｔ１〜ＴＨで構成され、要求区画４７の更新に合わせて整合をとるために更新を要する区画である。なお、要求区画４７と共通の区画をもつ更新グループが複数あれば、各更新グループに属する区画の和集合となる。また、なければ、区画数Ｈに０が入るのみである。
【００７８】
通信部１６は、地図更新装置１から候補区画データ５３を受信する（ステップＳＴ３２０８）。
更新制御部４５は、ステップＳＴ３２０８で受信した候補区画データ５３に未処理の候補区画があるかどうか、つまり、パン操作によって新たな区画の表示が必要になる前の区画バッファ４４にあった区画のバージョンより新しいバージョンのものがあるかどうかを判定する（ステップＳＴ３２０９）。具体的には、例えば、地図データがバージョン情報を有している場合はそれを用いてバージョン情報を比較することでバージョンが更新されているかどうかを判定すればよいし、あるいは、地図データの直前に改変された時刻の情報を比較することで判定するようにすればよい。
【００７９】
ステップＳＴ３２０９において、未処理の区画がない場合（ステップＳＴ３２０９の“ＮＯ”の場合）、処理を終了する。
ステップＳＴ３２０９において、未処理の区画がある場合（ステップＳＴ３２０９の“ＹＥＳ”の場合）、更新制御部４５は、未処理の区画を対象とする候補区画としてステップＳＴ３２１０に進み、対象とする候補区画が区画バッファ４４の既存の区画内かどうかを判定する（ステップＳＴ３２１０）。
ステップＳＴ３２１０において、対象とする候補区画が区画バッファ４４の既存の区画内ではない場合（ステップＳＴ３２１０の“ＮＯ”の場合）、更新制御部４５は、ステップＳＴ３２０９に戻り、未処理の候補区画がなくなるまでステップＳＴ３２０９以降の処理を繰り返す。
【００８０】
ステップＳＴ３２１０において、対象とする候補区画が区画バッファ４４の既存の区画内である場合（ステップＳＴ３２１０の“ＹＥＳ”の場合）、地図更新部１７は、地図更新装置１に対して、ステップＳＴ３２１０において区画バッファ４４の既存の区画内であると判断した、対象とする候補区画の地図データを、通信部１６を介して要求する（ステップＳＴ３２１１）。これを受けて、地図更新装置１では要求された区画の地図データ２を端末装置１１に送信する。
【００８１】
通信部１６は、地図更新装置１から、ステップＳＴ３２１１で要求した対象とする候補区画の地図データを受信する（ステップＳＴ３２１２）。
地図更新部１７は、対象とする候補区画の区画について、区画バッファ４４の地図データをステップＳＴ３２１２で地図更新装置１から受信した地図データに置き換える（ステップＳＴ３２１３）。その後、ステップＳＴ３２０９に戻り、未処理の候補区画がなくなるまでステップＳＴ３２０９以降の処理を繰り返す。
【００８２】
次に、地図更新装置１の動作について説明する。
図２７は、この発明の実施の形態３に係る地図更新装置１の動作を示すフローチャートである。なお、図２７は、地図データ２の更新により新しいバージョンの地図が与えられた時点の動作を示す。
図２７は、実施の形態１で図１２に示した新しいバージョンの地図が与えられた時点の動作を示すフローチャートから、ステップＳＴ３を除いたものであり、図２７のステップＳＴ１，ステップＳＴ２については、それぞれ図１２のステップＳＴ１，ステップＳＴ２と同様であるため、詳細な説明を省略する。実施の形態３においては、パン操作の他、ズーム操作などにもより区画バッファ４４に格納される区画は地図管理装置１から受信したものに随時更新される。また、端末装置１１が動作させる地図システムの継続利用時間に比べ、地図の更新間隔が十分に長いとすれば、区画バッファ４４に３つ以上のバージョンが並存することはない。このため、新旧の２バージョンを考えれば十分であり、複数の更新バージョンの階層化管理（図１２のステップＳＴ３の処理）までは不要である。
【００８３】
図２８は、実施の形態３の地図更新装置１の更新管理データ５４の一例を示す図である。
図２８のように、更新管理データ５４は、旧バージョンに対する新バージョンの更新区画の情報のみで、リンクに関する情報は有していない。
図２９は、実施の形態３の地図更新装置１において、端末装置１１からの要求に対して、候補区画データ５３を求める動作を示すフローチャートである。つまり、図２５のステップＳＴ３２０７で説明した端末装置１１の動作に対応した地図更新装置１側の動作を示すものである。
通信部９は、端末装置１１から要求区画４７の区画データを更新範囲として受信する（ステップＳＴ３１０１）。
更新区画抽出部７は、ステップＳＴ３１０１で受信した更新範囲と共通な区画を有する更新グループ２２を更新管理データ３から検索し、抽出する（ステップＳＴ３１０２）。
更新区画抽出部７は、ステップＳＴ３１０２にて得られた更新グループ２２に属する区画を識別するデータを、候補区画データ５３とし（ステップＳＴ３１０３）、通信部９を介して端末装置１１に送信する（ステップＳＴ３１０４）。
【００８４】
また、端末装置１１から要求区画４７の一つのデータの要求を受信した場合の地図更新装置１の処理（図２５のステップＳＴ３２０２で説明した端末装置１１の動作に対応した処理）、および、端末装置１１から区画バッファ４４の既存の区画内であると判断した、対象とする候補区画の地図データの要求を受信した場合の地図更新装置１の処理（図２５のステップＳＴ３２１１で説明した端末装置１１の動作に対応した処理）は、地図更新装置１の通信部９において端末装置１１からの要求を受信すると、配信制御部５２は、指定された区画の地図データ２を記憶部４から読み出し、通信部９を介して端末装置１１に送信する。
【００８５】
以上のように、実施の形態３によれば、地図システムでの地図表示において、地図表示のために新たに必要となる区画に加えて、既に保有している区画についても、整合のために更新が必要となる区画を特定して更新するように構成したので、地図システム利用中に地図更新装置の地図データが更新された場合でも、整合を保った地図を表示することができる。
【００８６】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【符号の説明】
【００８７】
１  地図更新装置、２  地図データ、３  更新管理データ、４  記憶部、５  領域区分部、６  領域構造化部、７  更新区画抽出部、８更新データ生成部、９  通信部、１０  通信ネットワーク、１１  端末装置、１２  地図データ、１３  更新状況データ、１４  記憶部、１５  更新範囲指定部、１６  通信部、１７  地図更新部、１８  地図表示部、４４  区画バッファ、４５  更新制御部、５２  配信制御部。
【図１】
2014240920.tif 000003
【図２】
2014240920.tif 000004
【図３】
2014240920.tif 000005
【図４】
2014240920.tif 000006
【図５】
2014240920.tif 000007
【図６】
2014240920.tif 000008
【図７】
2014240920.tif 000009
【図８】
2014240920.tif 000010
【図９】
2014240920.tif 000011
【図１０】
2014240920.tif 000012
【図１１】
2014240920.tif 000013
【図１２】
2014240920.tif 000014
【図１３】
2014240920.tif 000015
【図１４】
2014240920.tif 000016
【図１５】
2014240920.tif 000017
【図１６】
2014240920.tif 000018
【図１７】
2014240920.tif 000019
【図１８】
2014240920.tif 000020
【図１９】
2014240920.tif 000021
【図２０】
2014240920.tif 000022
【図２１】
2014240920.tif 000023
【図２２】
2014240920.tif 000024
【図２３】
2014240920.tif 000025
【図２４】
2014240920.tif 000026
【図２５】
2014240920.tif 000027
【図２６】
2014240920.tif 000028
【図２７】
2014240920.tif 000029
【図２８】
2014240920.tif 000030
【図２９】
2014240920.tif 000031