(57)【要約】【課題】道路ネットワークにおける道路の孤立を効率よく解消して地図データを作成する。【解決手段】道路を複数のレベルに分け、対応する道路の各レベル毎にネットワーク化したレベル別ネットワークデータを生成して、道路ネットワークを、階層化された複数のレベル別ネットワークデータにより表現する。複数のレベル別ネットワークデータの一つとその上位のレベルのレベル別ネットワークデータに含まれるリンクの接続関係を検証し、検証したレベル別ネットワークデータに、孤立した一または複数のリンクが含まれているかを判定する。そして、孤立した一または複数のリンクが含まれている場合には、孤立した一または複数のリンクに対応する道路のレベルを下位のレベルに変更する。【選択図】図４
2016153814.tif 000002
【特許請求の範囲】
【請求項１】
道路に対応したリンクを含む地図データ作成装置であって、
前記リンクを前記道路に設定されたレベル毎にネットワーク化した複数のレベル別ネットワークデータが階層化された道路ネットワークを記憶するデータ記憶部と、
前記複数のレベル別ネットワークデータの一つとその上位のレベルのレベル別ネットワークデータとを併せて、前記レベル別ネットワークデータに含まれる前記リンクの接続関係を検証し、検証した前記レベル別ネットワークデータに、孤立した一または複数のリンクが含まれているかを判定する判定部と、
前記接続関係を検証した前記レベル別ネットワークデータに、前記孤立した一または複数のリンクが含まれている場合には、前記孤立した一または複数のリンクに対応する道路の前記レベルを下位のレベルに変更するレベル変更部と
を備える地図データ作成装置。
【請求項２】
前記判定部は、前記接続関係を検証した前記レベル別ネットワークデータに、接続関係を有するリンクの集合あって当該集合同士は接続関係が存在しないグループが複数存在する場合、含まれるリンクの数が少ないグループに属するリンクを、前記孤立した一または複数のリンクであると判定する
請求項１記載の地図データ作成装置。
【請求項３】
前記判定部は、前記接続関係を検証した前記レベル別ネットワークデータに、接続関係を有するリンクの集合あって当該集合同士は接続関係が存在しないグループが複数存在する場合、予め設定された幹線道路に対応するリンクを含まないグループに属するリンクを、前記孤立した一または複数のリンクであると判定する
請求項１記載の地図データ作成装置。
【請求項４】
請求項１記載の地図データ作成装置であって、
前記データ記憶部は、前記道路ネットワークを複数の区域に分け、一つの区域に存在する複数の前記リンクを、接続関係を有するリンクの集合毎に異なる処理グループとして扱えるように記憶し、
前記判定部は、前記処理グループを単位として、前記接続関係を検証した前記レベル別ネットワークデータに、接続関係を有するリンクの集合であって当該集合同士は接続関係が存在しない孤立グループが複数存在する場合、含まれるリンクの数が最も多いグループ以外のグループ、あるいは予め設定された幹線道路に対応するリンクを含むグループ以外のグループに属するリンクを、前記孤立した一または複数のリンクであると判定する
地図データ作成装置。
【請求項５】
前記レベル変更部は、下位のレベルに変更する際の最も低いレベルを、前記階層化されたレベル別ネットワークデータの最下層より上位の所定の階層に対応したレベルとする請求項１から請求項４のいずれか一項に記載の地図データ作成装置。
【請求項６】
道路に対応したリンクを含む地図データ作成方法であって、
前記道路を複数のレベルに分け、前記リンクを前記対応する道路の各レベル毎にネットワーク化したレベル別ネットワークデータを生成して、道路ネットワークを、階層化された複数のレベル別ネットワークデータにより表現し、
前記複数のレベル別ネットワークデータの一つとその上位のレベルのレベル別ネットワークデータに含まれる前記リンクの接続関係を検証し、検証した前記レベル別ネットワークデータに、孤立した一または複数のリンクが含まれているかを判定し、
前記検証したレベル別ネットワークデータに、前記孤立した一または複数のリンクが含まれている場合には、前記孤立した一または複数のリンクに対応する道路の前記レベルを下位のレベルに変更する
地図データ作成方法。
【請求項７】
道路に対応したリンクを含む道路ネットワークデータの修正方法であって、
前記リンクを前記道路に設定されたレベル毎にネットワーク化した複数のレベル別ネットワークデータが階層化された道路ネットワークを、コンピュータが記憶部から読み出し、
前記複数のレベル別ネットワークデータの一つとその上位のレベルのレベル別ネットワークデータをコンピュータが読み取り、当該レベル別ネットワークデータに含まれる前記リンクの接続関係をコンピュータが検証し、検証した前記レベル別ネットワークデータに、孤立した一または複数のリンクが含まれているかを判定し、
前記検証したレベル別ネットワークデータに、前記孤立した一または複数のリンクが含まれている場合には、前記コンピュータが、前記孤立した一または複数のリンクに対応する道路の前記レベルを下位のレベルに修正する
道路ネットワークデータの修正方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データの作成に関する。
【背景技術】
【０００２】
カーナビゲーションなどの普及に伴い、地図データの作成や整備が求められている。一般にこれら地図データは、交差点に対応したノードと交差点同士をつなぐ道路に対応したリンクとから構成されるネットワークデータとして表される。このネットワークデータは、道路ネットワークと呼ばれる。こうした道路ネットワークは、実際に存在する道路をある一定の基準によって複数のレベルに区分けし、同じレベルの道路同士のネットワークとして階層構造にすることも多い。道路ネットワークをレベルに区分けする一例としては、道路種別が挙げられる。これは、「国道」を上位レベルに、「一般道」を下位レベルに区分けするものである。更に、上位の階層として「高速道路」の層などを設けてもよい。ナビゲーションにおける経路探索は、階層構造を持つ道路ネットワークを利用して行なわれる。これは、全ての道路を単純に接続した道路ネットワークを用いて経路探索をさせたのでは、出発地から目的地までを接続可能な経路の数が膨大な数になり、最適な経路を決定するための演算量が膨大なものになってしまうからである。
【０００３】
道路ネットワークを階層化しておけば、出発地から目的地までの経路を、出発地／目的地から上位レベルの階層の道路ネットワークに通じるまでの経路の探索と、これら経路を結ぶ上位レベルの階層の道路ネットワーク内の経路探索とに分けて行なうことができる。この場合、階層化された各道路ネットワーク内におけるリンク同士で接続がなされていないリンク（孤立したリンク）が存在すると、その道路ネットワークにおける経路探索が失敗することがある。現実の道路が、物理的には接続されていても、その道路に対応したリンクのデータを作成して道路ネットワークとしたときに、データの入力ミスや接続関係のデータ誤りなどにより、道路ネットワーク上では孤立した道路になってしまうことがある。このため、従来から、道路ネットワークを作成する際に、作成した道路に関するデータ（道路データ）をチェックして、孤立したリンクが存在しないかをチェックすることが行なわれていた（例えば、下記特許文献１、２参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−２３７４８７号公報
【特許文献２】特開２０１１−２１５２１９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記特許文献１、２は、いずれも、孤立した道路データの検出を自動的に行なう優れたものであり、これらを踏まえて、更に作業性の良い地図データの作成手法が求められるに至った。道路データが孤立したものとなった原因は、道路ネットワークにおける接続関係の不備、階層を決定するレベルデータの不備、あるいは離島など本土の道路ネットワークと現実に接続されていない場合など、様々である。また、これらの原因が組み合わさって孤立していることもありえる。従って、本願は、孤立した道路データを検出した際に、孤立した道路データが生じた原因によらず、その修正作業を、効率よく行なう手法を提供することを課題とする。
【課題を解決するための手段】
【０００６】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の形態として実現することが可能である。
【０００７】
（１）本発明の第１の形態として、地図データ作成装置が提供される。この地図データ作成装置は、道路に対応したリンクを含む地図データ作成装置であって、データ記憶部と、判定部と、レベル変更部とを備えて良い。データ記憶部は、前記リンクを前記道路に設定されたレベル毎にネットワーク化した複数のレベル別ネットワークデータが階層化された道路ネットワークを記憶してよい。また、判定部は、前記複数のレベル別ネットワークデータの一つとその上位のレベルのレベル別ネットワークデータとを併せて、前記レベル別ネットワークデータに含まれる前記リンクの接続関係を検証してよい。更に判定部は、前記接続関係を検証した前記レベル別ネットワークデータに、孤立した一または複数のリンクが含まれているかを判定してよい。他方、レベル変更部は、前記接続関係を検証した前記レベル別ネットワークデータに、前記孤立した一または複数のリンクが含まれている場合には、前記孤立した一または複数のリンクに対応する道路の前記レベルを下位のレベルに変更してよい。
【０００８】
かかる地図データ作成装置によれば、階層化された複数のレベル別ネットワークデータのうちの一つのレベル別ネットワークデータとその上位のレベルのレベル別ネットワークデータとを併せて、リンクの接続関係を検証し、孤立した一または複数のリンクが存在する場合、そのリンクに対応する道路のレベルを下位のレベルに変更できる。このため、上位のレベルで孤立したリンクに対応する道路を、自動的に下位のレベルの道路に付け替えることができ、作成された道路ネットワーク内の孤立した道路を人手に拠って修正しなくても、経路探索に利用できる地図データを作成できる。なお、判定部、レベル変更部の処理は、前記複数のレベル別ネットワークデータの上位のレベルから順に行なうものとしてもよい。
【０００９】
（２）こうした地図データ作成装置において、前記判定部は、前記接続関係を検証した前記レベル別ネットワークデータに、接続関係を有するリンクの集合あって当該集合同士は接続関係が存在しないグループが複数存在する場合、含まれるリンクの数が少ないグループに属するリンクを、前記孤立した一または複数のリンクであると判定しても良い。
【００１０】
こうした地図データ作成装置によれば、レベル別ネットワークデータに、接続関係を有するリンクの集合あって当該集合同士は接続関係が存在しないグループが複数存在する場合に、何れのリンクの集合が、孤立した一または複数のリンクであるかの判定を容易に行なうことができる。
【００１１】
（３）上記の地図データ作成装置において、前記判定部は、前記接続関係を検証した前記レベル別ネットワークデータに、接続関係を有するリンクの集合あって当該集合同士は接続関係が存在しないグループが複数存在する場合、予め設定された幹線道路に対応するリンクを含まないグループに属するリンクを、前記孤立した一または複数のリンクであると判定しても良い。
【００１２】
こうした地図データ作成装置によっても、レベル別ネットワークデータに、接続関係を有するリンクの集合あって当該集合同士は接続関係が存在しないグループが複数存在する場合に、何れのリンクの集合が、孤立した一または複数のリンクであるかの判定を容易に行なうことができる。
【００１３】
（４）上記の地図データ作成装置において、前記データ記憶部は、前記道路ネットワークを複数の区域に分け、一つの区域に存在する複数の前記リンクを、接続関係を有するリンクの集合毎に異なる処理グループとして扱えるように記憶し、前記判定部は、前記処理グループを単位として、前記接続関係を検証した前記レベル別ネットワークデータに、接続関係を有するリンクの集合であって当該集合同士は接続関係が存在しない孤立グループが複数存在する場合、含まれるリンクの数が最も多いグループ以外のグループ、あるいは予め設定された幹線道路に対応するリンクを含むグループ以外のグループに属するリンクを、前記孤立した一または複数のリンクであると判定しても良い。
【００１４】
こうした地図データ作成装置によれば、検証を行なっている地図ネットワークに、離島のような、もともと孤立した一または複数のリンクが存在する場合、こうした孤立したリンクのレベルを徒に下位に変更することがない。この場合でも、本来接続関係が存在すべきリンクについては、そのレベルを下位に変更して、経路探索に利用できる地図データを作成できる。
【００１５】
（５）上記の地図データ作成装置において、前記レベル変更部は、下位のレベルに変更する際の最も低いレベルを、前記階層化されたレベル別ネットワークデータの最下層より上位の所定の階層に対応したレベルとしても良い。
【００１６】
こうした地図データ作成装置によれば、孤立した一または複数のリンクであると判定されたリンクに対応する道路のレベルを最下層よりは上位のリンクに留めることができる。階層化されたレベル別ネットワークデータでは最下層は車両通行不可など経路探索で利用しない道路とされることがあるため、最下層よりは上位のリンクに留めることで、経路探索に利用できない地図データを作成することがない。
【００１７】
（６）本発明の第２の形態として、道路に対応したリンクを含む地図データの作成方法が提供される。この地図データの作成方法は、前記道路を複数のレベルに分け、前記リンクを前記対応する道路のレベル毎にネットワーク化したレベル別ネットワークデータを生成して、道路ネットワークを、階層化された複数のレベル別ネットワークデータにより表現して良く；前記複数のレベル別ネットワークデータの一つとその上位のレベルのレベル別ネットワークデータに含まれる前記リンクの接続関係を検証し、前記接続関係を検証した前記レベル別ネットワークデータに、孤立した一または複数のリンクが含まれているか判定して良く；前記検証したレベル別ネットワークデータに、前記孤立した一または複数のリンクが含まれている場合には、前記孤立した一または複数のリンクに対応する道路の前記レベルを下位のレベルに変更して良く；これら、前記接続関係の検証、前記孤立した一または複数のリンクが含まれているかの判定、前記孤立した一または複数のリンクに対応する道路の前記レベルの下位のレベルへの変更は、前記複数のレベル別ネットワークデータの上位のレベルから順に処理して良い。かかる地図データの作成方法によっても、本発明の目的は達成される。
【００１８】
さらに本発明の第３の形態として、道路に対応したリンクを含む道路ネットワークデータの修正方法が提供される。この道路ネットワークデータの修正方法において、前記リンクを前記道路に設定されたレベル毎にネットワーク化した複数のレベル別ネットワークデータが階層化された道路ネットワークを、コンピュータが記憶部から読み出して良く；前記複数のレベル別ネットワークデータの一つとその上位のレベルのレベル別ネットワークデータをコンピュータが読み取り、当該レベル別ネットワークデータに含まれる前記リンクの接続関係をコンピュータが検証し、前記接続関係を検証した前記レベル別ネットワークデータに、孤立した一または複数のリンクが含まれているか判定して良く；前記検証したレベル別ネットワークデータに、前記孤立した一または複数のリンクが含まれている場合には、前記コンピュータが、前記孤立した一または複数のリンクに対応する道路の前記レベルを下位のレベルに修正して良く；前記接続関係の検証、前記孤立した一つまたは複数のリンクが含まれているかの判定、前記孤立した一つまたは複数のリンクに対応する道路の前記レベルを下位レベルに修正することを、レベル別ネットワークデータの上位のレベルから順に行なっても良い。
【００１９】
この道路ネットワークデータの修正方法によれば、階層化された複数のレベル別ネットワークデータのうちの一つのレベル別ネットワークデータとその上位のレベルのレベル別ネットワークデータとを併せて、リンクの接続関係を検証し、孤立した一または複数のリンクが存在する場合、そのリンクに対応する道路のレベルを下位のレベルに修正できる。このため、上位のレベルで孤立したリンクに対応する道路を、自動的に下位のレベルの道路に付け替えることができ、作成された道路ネットワーク内の孤立した道路のレベルを、経路探索に利用できるように修正できる。
【００２０】
上述した本発明の各形態の有する複数の構成要素はすべてが必須のものではなく、上述の課題の一部又は全部を解決するため、あるいは、本明細書に記載された効果の一部又は全部を達成するために、適宜、前記複数の構成要素の一部の構成要素について、その変更、削除、新たな他の構成要素との差し替え、限定内容の一部削除を行うことが可能である。また、上述の課題の一部又は全部を解決するため、あるいは、本明細書に記載された効果の一部又は全部を達成するために、上述した本発明の一形態に含まれる技術的特徴の一部又は全部を上述した本発明の他の形態に含まれる技術的特徴の一部又は全部と組み合わせて、本発明の独立した一形態とすることも可能である。
【００２１】
本発明は、装置以外の種々の形態で実現することも可能である。例えば、地図データ作成装置の製造方法や地図データ作成装置の制御方法、その制御方法を実現するコンピュータプログラム、そのコンピュータプログラムを記録した一時的でない記録媒体等の形態で実現できる。
【図面の簡単な説明】
【００２２】
【図１】第１実施形態の地図データ作成装置の概略構成を示す説明図。
【図２】地図データの作成処理の概要を示すフローチャート。
【図３】メッシュ毎の道路ネットワークデータの構造を示す説明図。
【図４】第１実施形態における孤立除去処理ルーチンを示すフローチャート。
【図５】孤立除去処理の実施の様子を示す説明図。
【図６】第２実施形態の地図データ作成処理を示すフローチャート。
【図７】データ作成の対象となる地図をメッシュに分けた構成を例示する説明図。
【図８】第２実施形態における孤立除去の様子を示す説明図。
【図９】第２実施形態における孤立除去の様子を示す説明図。
【図１０】第２実施形態における孤立除去の様子を示す説明図。
【図１１】第２実施形態における孤立除去の様子を示す説明図。
【図１２】第２実施形態における孤立除去の様子を示す説明図。
【発明を実施するための形態】
【００２３】
Ａ．第１実施形態：
本発明の第１実施形態としての地図データ作成装置および地図データの作成処理について説明する。図１は、地図データ作成装置１００の概略構成を示す説明図である。図示するように、地図データ作成装置１００は、処理を行なうコンピュータ１０，入力装置としてのキーボードおよびマウス３０，表示装置としてのディスプレイ４０から構成されている。
【００２４】
コンピュータ１０は、周知のＣＰＵ１１，ＲＯＭ１２，ＲＡＭ１３の他、ハードディスクなどのストレージ１５を制御するディスクコントローラ１４や、キーボード，マウス３０等とのインタフェースを司るＩ／Ｏインタフェース１６，ディスプレイ４０における表示を制御するディスプレイコントローラ１７等を備える。ストレージ１５には、後述する道路データベースＧＤＢと共に、地図データ作成処理を実現するプログラムが記憶されている。これらのプログラムは、ＲＡＭ１３にロードされ、ＣＰＵ１１によって実行されることにより、後述する地図データ作成処理を実現する。また、これらのプログラムと図１に示した各ハードウェアとの協働により、地図データ作成装置としての各部が実現される。また、実施形態のストレージ１５が「データ記憶部」の下位概念に相当する。
【００２５】
次に地図データ作成処理について説明する。図２には、地図データ作成処理の概要を示すフローチャートである。地図データは、道路ネットワーク（ＮW）データを作成する処理（ステップＳ１００）、孤立除去処理（ステップＳ２００）、地図データ出力処理（ステップＳ３００）という処理を経て作成される。このうち、道路ＮＷデータ作成処理は、孤立除去処理等に先立って行なわれるもので、地図データ作成装置１００とは別の装置で行ない、その結果だけが、ストレージに道路ＮＷデータとして保存されている。もとより、地図データ作成装置において、一から道路ＮＷデータを作成するものとしても良い。
【００２６】
道路ＮＷデータは、実際の道路を、ノードとリンクにより表わしたものである。図３に、道路ＮＷデータの一例を示す。道路ＮＷデータは、取り扱いの便を図って、まず地図を複数のメッシュに分割し、メッシュ毎に、そのメッシュに含まれる道路のデータの集合として作成されている。メッシュとは、道路ＮＷデータの作成対象となっている地域（例えば日本）を、緯度経度に基づいて地域を凡そ同じ大きさの複数の区域に分けた、その一つの区域を意味している。メッシュの大きさは、任意であり、対象地域を覆うことができれば、四角形、多角形など、どのような形状でも差し支えない。また、全てのメッシュが同じ形状である必要はなく、複数種類の形状を組み合わせたものであっても良く、メッシュ内で更に複数の区域に分けても良い。あるいは、区分けするメッシュの大きさを、メッシュ内に含まれるリンク本数が均一となるように調整しても良い。
【００２７】
道路ＮＷデータは、各道路に対応したリンクと、各交差点に対応したノードとによって構成される。ここでリンクは、リンクＩＤ、道路ＩＤ、出発ノードＩＤ、到着ノードＩＤ、ネットワークレベル（ＮＷＬ）情報、リンク付加情報１、幹線道路情報、までをひとまとまりとして定義されている。また、ノードは、ノードＩＤ、交差点ＩＤ、ノード付加情報１までを一つのノードとするものとして定義されている。各道路は、道路ＩＤにより区別され、リンクＩＤをもつ複数のリンクとして展開される。各リンクへ付与される付加情報としては種々のものがあり、例えば、交通規制に関する情報（例えば、制限速度などの情報）、車線に関する情報（例えば、車線数、道路幅）などが含まれる。幹線道路情報とは、そのリンクが、全国の主要な地点を結ぶ道路（例えば、高速道路、国道などの情報）か否かの情報であり、そのデータは、図示しない幹線道路設定処理によって設定される。同様に各交差点は、交差点ＩＤにより区別されノードＩＤをもつ複数のノードとして展開される。各ノードへ付加される付加情報としては、接続しているリンクの情報、交通規制に関する情報（例えば、右折禁止、通行止めなどの情報）などが含まれる。境界ノード情報とは、そのノードが、メッシュを跨ぐ道路をメッシュによって区域に分けるにあたって便宜上追加された仮想的なノードであるか否かの情報である。後述するように、メッシュ内で孤立している道路は、メッシュ内の他の道路との接続関係を調べれば分かるが、メッシュ外に延びている道路は、メッシュ内の他の道路とは接続していなくても、メッシュ外では他の道路と接続されており、孤立していない場合がある。このため、こうしたノードには、境界ノード情報として、隣接メッシュの対応するノードを記録している。
【００２８】
更に、各リンクには、ＮＷＬ情報が付与されている。このＮＷＬ情報は、道路のレベルを示す情報であり、一般に、高速道路や国道など、整備された道路ほど高いレベルが付与されている。もとより全ての国道が、高いＮＷＬ情報（例えば５）が付与されている訳ではなく、国道でも狭くて渋滞などが発生しやすい道路のＮＷＬ情報は、本実施形態では低い値とされている。ＮＷＬ情報は、経路探索を行なう場合、出発地／目的地からそれぞれ上位のＮＷＬ情報を持つ道路までの探索と、これら経路を結ぶ上位のＮＷＬ情報をもつリンクでの経路探索とに分けておこなうために用いられる。こうすることで、道路の接続を調べる探索処理を高速化できる。
【００２９】
道路データベースＧＤＢは、図３に示した内容に限られるものではなく、経路の探索が行なえる形態であれば、どのような構造であっても差し支えない。例えば、ノードを中心に、これに接続されているリンクを集めた形態でもよい。またメッシュに分けることなく、国道○号に含まれる道路を集めるなど、道路毎にまとめた形態でも良い。いずれの場合でも、道路を識別できるＩＤなどの識別子、道路の接続情報、それにＮＷＬ情報が含まれていればよい。
【００３０】
この道路ＮＷデータが作成され、ストレージ１５に記憶された状態で、次に孤立除去処理（ステップＳ２００）が行なわれる。図３に示したデータは、各道路のデータを集めたものであり、現実の道路を反映している。また、各道路に付与されたレベル情報は、その道路の種別や渋滞の発生状況などを考慮して、リンク毎に付与されており、道路の接続については考慮されていない。従って、道路は孤立している場合があり得るが、ここで言う「孤立」には、次の２種類の意味が含まれる。
［１］離島などの道路のように、実際に、他の道路と接続されておらず、孤立している場合。
［２］あるレベル、例えばＮＷＬ情報＝５の道路を辿っていくと、何処かで、同じレベルの道路と接続されておらず、孤立している場合。
このうち、［１］の孤立した道路は、実際に孤立しており、道路データベースＧＤＢ上の情報を加工しても孤立を解消することはできない。これに対して、［２］の孤立した道路は、特定のＮＷＬ情報が与えられた道路では、孤立しているものの、実際には、他の道路と接続している場合と、接続されておらず本当に孤立している場合とがありえる。
【００３１】
そこで、本実施形態では、［２］の孤立した道路の解消を行なうべく、孤立除去処理を行なうのである。この処理の詳細を図４に示した。孤立除去処理が開始されると、まず処理対象のメッシュ内における最上位のＮＷＬ情報を取得する（ステップＳ２１０）。本実施形態では、ＮＷＬ情報は、最高で値５、最低で値１に設定されている。そのメッシュに含まれる最高のＮＷＬ情報が、例えば値５であれば、ステップＳ２１０により、この値５が取得され、変数Ｃｎｗｌに格納される。
【００３２】
次に、ＮＷＬ情報が変数Ｃｎｗｌ以上の道路を抽出する処理を行ない（ステップＳ２１５）、続いて、抽出したリンクの中から、孤立グループを抽出する処理を行なう（ステップＳ２２０）。孤立グループの抽出処理とは、ステップＳ２１５で抽出した道路をつなぎ、つないだリンクのまとまり（以下、リンクグループと呼ぶ）の中から、孤立グループを抽出するのである。図５は、この孤立グループ抽出処理の様子を示す説明図である。図５の（Ａ）欄には、このメッシュに含まれる全てのリンクが示されている。最も太い線で記載されているリンクは、ＮＷＬ情報＝５のリンクである。このリンクは、国道など、通常、接続道路として、探索の対象となるリンクである。次に太い線で描かれているのが、ＮＷＬ情報＝４のリンクである。細線で描かれているのは、ＮＷＬ情報＝３のリンクであり、細い破線で描かれているのは、ＮＷＬ情報＝１のリンクである。このメッシュには、図４に示した処理を開始する以前には、ＮＷＬ情報＝２のリンクは存在しない。また、ＮＷＬ情報＝１のリンクは、通行が禁止されているリンクである。図５など地図を例示する図面において、白地の領域は陸地や島など道路が存在しうる領域を示しており、網点を付した領域は海や河川・湖沼など道路が敷設されることが原則としてない領域（陸地でない領域）を示している。
【００３３】
図５の（Ａ）に示したリンクに対して、まずＮＷＬ情報＝５において、リンクグループの形成を行なう。このように、特定のＮＷＬ情報のリンクを集めて構成したグループが、「レベル別ネットワークデータ」の下位概念に相当する。ＮＷＬ情報においてリンクグループを形成すると、図５の（Ｂ）欄に破線で囲って示したように、２つのリンクグループＩＧ１，ＩＧ２が見いだされる。いずれのリンクグループＩＧ１，ＩＧ２も、着目しているメッシュ内に存在するＮＷＬ情報＝５以上のリンクの集まりであり、リンクグループ同士は接続されていない。そこで、このうち、どのリンクグループを孤立グループとするかの判断を行ない、条件に該当するリンクグループを孤立グループとして抽出するのである。
【００３４】
複数のリンクグループが見いだされた時、どのグループを孤立グループとして抽出するかは、種々の手法により決定できる。例えば
（１）グループに含まれるリンクの数が最も多いリンクグループ以外を孤立グループとする。
（２）幹線道路であるリンクを含まない道路グループを孤立グループとする。
（３）隣接メッシュに対して接続があるリンクグループと接続のないリンクグループとがあれば、後者を孤立グループとする。
（４）各リンクグループに接続されている、ＮＷＬ情報が小さいリンクの数が一番多いリンクグループ以外を孤立グループとする。
例えば、上記の判断条件のうち（１）を当て嵌めると、図５の欄（Ｂ）の例では、リンクグループＩＧ２が孤立グループとなる。これらの判断条件は、単独で適用しても良いし、二つ以上の条件を組み合わせても良い。一つの判断条件では、異なるリンクグループの判断結果が等しくなる場合に、他の条件を適用しても良い、あるいは、その場合には、いずれか一方を、任意に、ランダムにあるいは先にグループを形成した方に、など、予め定めたルールに従って、いずれか一つのリンクグループを孤立グループでないとし、他を孤立グループとして抽出すればよい。あるいは、等しい判断結果を持つ異なるリンクグループをディスプレイ４０に表示し、ユーザーからどのリンクグループを孤立グループでないとするかついて、判断を受け付けても良い。孤立グループは複数抽出されることがあり得る。
【００３５】
こうして孤立グループの抽出が完了すると、次に、孤立グループに含まれるリンクのＮＷＬ情報を一つ格下げする処理を行なう（ステップＳ２３０）。図５に示した例では、リンクグループＩＧ２に含まれるリンクのＮＷＬ情報を値５から値４に変更するのである。この修正は、図３に示した道路データベースＧＤＢ内のＮＷＬ情報を書き直すことにより行なわれる。上述したステップＳ２１５およびＳ２２０を実行する際のＣＰＵ１１が、「判定部」の下位概念に相当する。また、上述したステップＳ２３０を実行する際のＣＰＵ１１が、「レベル変更部」の下位概念に相当する。
【００３６】
次に、変数Ｃｎｗｌを値１だけ小さくし（ステップＳ２４０）、変数Ｃｎｗｌが最小値Ｃｍｉｎ以下となったか否かを判断する（ステップＳ２５０）。ここでは、Ｃｍｉｎは、ＮＷＬ情報＝１は、通行不能なリンクとして規定していることから、値２に設定されている。変数Ｃｎｗｌが最小値Ｃｍｉｎより大きければ、処理は、ステップＳ２１５に戻って、孤立グループの抽出処理から再度実行される。
【００３７】
図５の例を用いて説明すると、ＮＷＬ情報が値５である場合に見い出された孤立グループ（リンクグループＩＧ２）に含まれるリンクのＮＷＬ情報を値４に下げて、再度図４のＮＷＬ情報が変数Ｃｎｗｌ以上のリンクの抽出（ステップＳ２１５）と孤立グループの抽出処理（ステップＳ２２０）が実行されると、図５（Ｃ）に示したように、今度は二つのリンクグループＩＧ２、ＩＧ３が孤立グループとして見いだされることになる。孤立グループとして抽出されたリンクグループＩＧ２は、そのリンクのＮＷＬ情報を値４に下げても、なお他のリンクと接続していないからである。また、リンクグループＩＧ３は、もともとＮＷＬ情報が値４であったリンクから構成されているため、この時点で、別の孤立グループとして見いだされたものである。このリンクグループＩＧ３に含まれるリンクも、ＮＷＬ情報が値４以上では、上記（１）を当て嵌めると、孤立グループと判断される。
【００３８】
そこで、ステップＳ２３０の処理により、これらの孤立グループの属するリンクのＮＷＬ情報を、更に格下げする。この結果、これらの孤立グループに属するリンクのＮＷＬ情報は、値３となる。この状態で、図４に示したリンクの抽出処理（ステップＳ２１５）と孤立グループの抽出処理（ステップＳ２２０）が再度実行されると、図５（Ｄ）に示したように、孤立グループであったリンクグループＩＧ２は、リンクグループＩＧ１に接続され、孤立は解消される。他方、リンクグループＩＧ３は、孤立グループであるため、これに属するリンクのＮＷＬ情報は、値２となる。その後、変数Ｃｎｗｌを更に値１だけデクリメントし（ステップＳ２４０）、変数Ｃｎｗｌは、設定した最小値Ｃｍｉｎ（ここでは値２）以下となるまで、上述した処理を繰り返す。
【００３９】
上述した例では、ＮＷＬ情報を値３まで下げたところで、それまでに見い出されたリンクグループの１つの孤立は解消したが、例えばＮＷＬ情報が高い際には孤立グループが見いだされなくても、ＮＷＬ情報を小さくしていった時点で孤立グループが見いだされることもあり得る。従って、本実施形態では、ＮＷＬ情報の格下げにより一旦孤立が解消しても、変数Ｃｎｗｌのデクリメントとリンクの抽出処理、孤立グループの抽出処理、孤立グループの格下げなどの処理を繰り返している。もとより、変数Ｃｎｗｌ以上のリンクを抽出して孤立グループが見いだされなければ、ＮＷＬ情報の格下げを行なう必要はない。
【００４０】
上述したステップＳ２１５ないしＳ２５０の処理を繰り返し、変数Ｃｎｗｌが次第に小さな値にデクリメントされて、ステップＳ２５０での判断が「ＹＥＳ」となると、図４に示した孤立除去処理ルーチンは、終了する。本実施形態では、ステップＳ２５０での判断の前に変数Ｃｎｗｌのデクリメントを行なっているので、ＮＷＬ情報が値２以下に格下げされることはない。
【００４１】
以上説明した第１実施形態としての地図データ作成装置１００によれば、通行可能なリンクであれば、特定のＮＷＬ情報が付与されたリンクが孤立することを解消できる。図５（Ｂ）に示したように、当初、リンクグループＩＧ２に存在したＮＷＬ情報＝５のリンクの孤立は、図５（Ｄ）に示すように、孤立グループの抽出に基づいてＮＷＬ情報を格下げするという単純な処理により、解消される。しかも、各リンクにＮＷＬ情報を付与する際には、リンクの孤立について特に考慮する必要がない。各リンクにＮＷＬ情報を付与する際には、国道、県道などの道路の種類や、通行量、通行のし易さなどの道路状態などによってＮＷＬ情報を階層的に付与しておくだけで良い。このため、道路についての情報の整備と、孤立除去の処理とを分離できる。また、孤立した道路を見い出した場合に、手動で道路の孤立の解消を行なう必要がない。
【００４２】
また、本実施形態では、ＮＷＬ情報の格下げを行なう際、ＮＷＬ情報＝２までしか格下げを行なわない。このため、ＮＷＬ情報の格下げによって孤立が解消しない場合でも、各道路のＮＷＬ情報は、値２までに留められる。本実施形態では、通行不能な道路には、ＮＷＬ情報＝１が割り当てられているが、孤立が解消しない場合でも、ＮＷＬ情報は車両の通行が可能なレベルに保たれる。なお、ＮＷＬ情報を値２まで格下げしても、孤立が解消していない場合には、何らかの方法で警告を出力するようにしても良い。図４に示した例では、ステップＳ２５０の判断が「ＹＥＳ」となったあとで、処理対象となった地域のリンクグループの孤立が解消しているかを判断し、解消していなければ、どのリンクグループが孤立したままであるかのレポートを出力するようにすれば良い。その場合、該当するリンクグループに含まれるリンクのＮＷＬ情報は、そのままに維持しても良いし、図４の処理を開始する前の値に戻すものとしても良い。
【００４３】
Ｂ．第２実施形態：
次に、本発明の第２実施形態について説明する。第２実施形態の地図データ作成装置１００は、ハードウェア構成は、第１実施形態の地図データ作成装置１００と同一である。第２実施形態では、地図データの作成処理（図６）が、第１実施形態の処理（図２、図４）とは異なっている。
【００４４】
第２実施形態では、地図データ作成装置１００は、図６示した地図データ作成処理を実行する。なお、図６において、第１実施形態と同じ処理は、同じ符号を付した。この処理が開始されると、まず道路ＮＷデータを作成する処理を行なう（ステップＳ１００）。この処理は、第１実施形態と同様である。従って、この処理が実行されると、図３に示した道路データベースＧＤＢが整備され、ストレージ１５内に保存される。
【００４５】
次に、処理対象地域を選択する処理が行なわれる（ステップＳ１１０）。この処理は、道路ＮＷデータの作成対象となっている対象の中から、一つの地域を選択する処理である。この様子を図７に示した。図示するように、道路ＮＷデータを作成する対象を所定の大きさのメッシュに分けているので、そのうちの一つを選択するのである。図７には、地図の左下を原点として、経度方向であるｘ方向に３つ、緯度方向であるｙ方向に３つ、全部で９つ（３×３）の地域が示されている。図７に示した例では、２つの陸地ＨＫＤ，ＨＮＳと、１つの島ＯＫＴ、がこの９つの地域に含まれている。以下の説明では、地域Ｍ（ｘ，ｙ）を取り上げる。この地域Ｍ（ｘ，ｙ）には、陸地ＨＫＤおよび島ＯＫＴとが含まれている。なお、「陸地」と「島」の呼び方は便宜的なものであり、道路が存在する土地という意味では、何ら差異はない。
【００４６】
次の処理グループを抽出する処理を行なう（ステップＳ１５０）。この処理は、孤立除去処理を行なう対象を特定する処理である。図７に示した地域Ｍ（ｘ，ｙ）を処理するものとして、二つの陸地が含まれている地域での処理を、図８ないし図１２に示した。図８に示すように、二つの陸地には、それぞれ道路網が存在するものとする。このとき、海で隔てられているため、それぞれの陸地の道路は接続されていない。こうした場合を想定して、処理グループを抽出する処理を行なうのである。
【００４７】
具体的には、図９に示したように、まず選択した地域Ｍ（ｘ，ｙ）に含まれる全ての道路を、ＮＷＬ情報に無関係に接続し、接続された道路毎に、処理グループとして、抽出する。図９の例では、陸地ＨＫＤに存在する道路からなる処理グループＰＧ１と、島ＯＫＴに存在する道路からなる処理グループＰＧ２とが、抽出される。こうした処理グループは、ＮＷＬ情報を使用しない経路探索を利用して自動的にリンクやノードの接続関係を解析する方法や、本土を１つの処理グループとし、隣接したメッシュに道路が存在する地域がない島を別の処理グループとする方法や、いわゆるラベリングによって行なう方法などで特定することができる。
【００４８】
こうして処理グループを抽出すると、まずその一つを処理対象のグループとして特定し（ステップＳ１６０）、続いて孤立除去処理（ステップＳ２００）を実施する。この孤立除去処理（ステップＳ２００）は、第１実施形態で説明した孤立除去処理と同一のものである。処理の対象が、第１実施形態では、処理対象のメッシュ全体であったのに対して、第２実施形態では、ステップＳ１６０により特定された一つの処理グループである点で相違しているに過ぎない。
【００４９】
処理グループＰＧ１について、孤立除去処理が実行されると、まずＮＷＬ情報＝５以上のリンクを選択して（図４、ステップＳ２１５）、孤立グループを抽出する処理を行ない（図４、ステップＳ２２０）、孤立グループが見いだされると、そのＮＷＬ情報を格下げする（図４、ステップＳ２３０）。図９に示した処理グループＰＧ１の例では、図１０に示すように、ＮＷＬ情報＝５において、２つのリンクグループＩＧ１、ＩＧ２が見い出され、上述した条件を当て嵌めることにより、リンクグループＩＧ２が孤立グループであるとして、そのリンクグループIＧ２に含まれるリンクのＮＷＬ情報が値１だけ格下げされる。
【００５０】
続いて、最小レベルまで処理が繰り返されたかを判断し（図４、ステップＳ２４０，Ｓ２５０）、最小レベル（ここでは、ＮＷＬ情報＝２）での判断が完了していなければ、再度リンクの抽出と孤立グループの抽出処理（ステップＳ２１５，Ｓ２２０）から処理を繰り返す。従って、次にはＮＷＬ情報＝４での判断が行なわれる。この状態を図１１に示した。図１１では、陸地ＨＫＤ側の処理グループＰＧ１と、島ＯＫＴ側の処理グループＰＧ２とが、共に示されているが、ここでは処理グループＰＧ１側の処理がなされており、ＮＷＬ情報＝４で見い出された３つのリンクグループＩＧ１〜ＩＧ３について、更に判断が行なわれ、孤立していると判断されたリンクグループＩＧ２，ＩＧ３について、ＮＷＬ情報の格下げが行なわれる。格下げ後のリンクの接続状態を図１２に示した。この例では、陸地ＨＫＤについては、孤立グループに属するリンクのＮＷＬ情報を値３まで下げたところで、リンクグループＩＧ２の孤立は解消したが、リンクグループＩＧ３については解消しなかった。リンクグループＩＧ３については、変数Ｃｎｗｌが値２までデクリメントされることにより、孤立は解消しなかったが、処理は打ち切られた。
【００５１】
こうして一つの処理グループについての処理が完了すると、次に、全処理グループについての処理が完了したかを判断し（図６、ステップＳ１７０）、未処理の処理グループが残っていれば、ステップＳ１６０の処理対象のグループの特定から処理を繰り返す。図８の例では、処理グループＰＧ１についての処理が完了したら、もうひとつの処理グループＰＧ２を特定し、上述した処理を繰り返す。
【００５２】
孤立除去処理（図４）を行なうことにより、図１１に示した例では、変数Ｃｎｗｌを値４までデクリメントした段階で、処理グループＰＧ２の中に、リンクグループＩＧ４，ＩＧ５が見い出され、接続されているリンクの数が少ないリンクグループＩＧ５が孤立グループと判断され、リンクグループＩＧ５に含まれるリンクのＮＷＬ情報を値３まで格下げした段階で、図１２に例示したように、この島ＯＫＴ内に見い出された処理グループＰＧ２に含まれるリンクについての孤立は解消する。
【００５３】
こうして特定したメッシュ（地域）における全ての処理グループについての処理が完了すると（ステップＳ１７０：「ＹＥＳ」）、次に、全ての地域についての処理が完了したかを判断し（ステップＳ１８０）、処理対象となった地域（図７の９つのメッシュ）についての処理が完了するまで、上述したステップＳ１１０ないしＳ１８０の処理を繰り返す。図７では、３×３の９つのメッシュを示したが、もとより、もっと広い地域を対象として処理を行なうことも差し支えない。例えば日本の道路を対象とする場合には、北海道、本州、四国、九州といった地域を個々に処理対象として処理を行なっても良いし、日本全体を対象としても良い。行政区画に従った地域分けにより処理対象地域を決めても良い。地域の特定は、図７に例示した矩形のメッシュによっても良いし、他の形状によっても良い。全てのメッシュが同じ形状をしている必要はなく、都道府県や州などの形（行政界の形）で区分けされた地域を対象として処理を行なっても良い。
【００５４】
全ての地域についての処理が完了すると（ステップＳ１８０：「ＹＥＳ」）、処理したデータを地図データとして出力し（ステップＳ３００）、地図データ作成処理を終了する。
【００５５】
以上説明した第２実施形態では、メッシュ内のリンクの接続状態に基づいて予め処理グループを抽出し、この処理グループ毎に孤立除去処理を行なっている。このため、第１実施形態の効果に加えて、島ＯＫＴに存在する道路のように、もともと他の道路から分離されている道路についての処理を、より適切に行なうことができるという効果を奏する。ＮＷＬ情報を下げても他のリンクと接続しないリンクが存在する場合、処理グループ内での孤立が解消すれば、その段階でＮＷＬ情報の格下げは完了するからである。従って、元々他のリンクに接続されていないこうしたリンク群について、ＮＷＬ情報を過度に低くしてしまうと言うことがない。図１２に示したように、処理グループＰＧ２では、ＮＷＬ情報を値３まで下げた時点で、リンクの孤立は解消したと判断できる。従って、それ以上にＮＷＬ情報が格下げされることはない。
【００５６】
Ｃ．変形例：
・変形例１：
上述した各実施形態では、ＮＷＬ情報は、最大で値５、最小で値１としているが、ＮＷＬ情報は、道路を区分けする目的に応じて、更に細かく分けても良いし、大まかに分けても良い。また、リンクのレベルを上位から下位に付け替えられるのであれば、ＮＷＬ情報は、数字である必要はなく、アルファベットでもバイナリーコードでも良い。また、格下げ（図４、ステップＳ２３０）により、直接、道路データベースＧＤＢ内の値を書き換えても良いし、一旦バッファに読み込んで処理し、その後、道路データベースＧＤＢ内の値を更新するものとしても良い。また、上記の実施形態では、通行できない道路にもＮＷＬ情報を付与したが、こうした道路にはＮＷＬ情報を付与しない、としてもよい。
【００５７】
・変形例２：
上述した各実施形態では、いずれも予め道路データベースＧＤＢを作成しておき、これに対して孤立除去処理を行なったが、メッシュ毎の道路データベースＧＤＢを作成する度に、図４に示した孤立除去処理を行なうものとしても良い。あるいは、孤立除去処理だけを単独で行なう装置として実装することも差し支えない。この場合は、地図データの修正方法や修正装置として、本発明を実施することが可能である。
【００５８】
・変形例３：
図４のステップＳ２２０の判断、つまり抽出されたリンクグループのいずれが孤立しているかの判断は、処理対象となっているメッシュ内での条件により判断しても良いし、着目しているメッシュの周囲に広がる他のメッシュにおけるリンクの接続状況を加味して判断しても良い。例えば、一つのメッシュにＮＷＬ情報＝５のリンクからなるリンクグループが複数見い出されたとして、そのいずれもが隣接メッシュのリンクに接続されている場合、メッシュ内の状況だけで、どのリンクグループが孤立グループでないと判断することも考えられるし、隣接メッシュでのリンクの状況も加味して判断することも考えられる。前者の場合、例えば、メッシュ内における接続道路の多寡により、孤立していないリンクグループを決定できる。この場合、隣接するメッシュまで含めて、接続されているリンクの数をカウントし、異なる判断結果を導くことも考えられる。隣接するメッシュ（領域）の道路の状況をどの程度加味して判断するかは、地図データの作成目的などに応じて決定すれば良い。
【００５９】
本発明は、上述の実施形態や実施例、変形例に限られるものではなく、その趣旨を逸脱しない範囲において種々の構成で実現できる。例えば、発明の概要の欄に記載した各形態中の技術的特徴に対応する実施形態、実施例、変形例中の技術的特徴は、上述の課題の一部又は全部を解決するために、あるいは、上述の効果の一部又は全部を達成するために、適宜、差し替えや、組み合わせを行うことが可能である。また、その技術的特徴が本明細書中に必須なものとして説明されていなければ、適宜、削除することが可能である。
【符号の説明】
【００６０】
１０…コンピュータ
１１…ＣＰＵ
１２…ＲＯＭ
１３…ＲＡＭ
１４…ディスクコントローラ（ＨＤＣ）
１５…ストレージ
１６…Ｉ／Ｏインタフェース
１７…ディスプレイコントローラ
３０…キーボード・マウス
４０…ディスプレイ
１００…地図データ作成装置
ＧＤＢ…道路データベース
ＨＫＤ，ＨＮＳ…陸地
ＯＫＴ…島
ＰＧ１〜ＰＧ２…処理グループ
ＩＧ１〜ＩＧ５…リンクグループ
【図１】
2016153814.tif 000003
【図２】
2016153814.tif 000004
【図３】
2016153814.tif 000005
【図４】
2016153814.tif 000006
【図５】
2016153814.tif 000007
【図６】
2016153814.tif 000008
【図７】
2016153814.tif 000009
【図８】
2016153814.tif 000010
【図９】
2016153814.tif 000011
【図１０】
2016153814.tif 000012
【図１１】
2016153814.tif 000013
【図１２】
2016153814.tif 000014