(57)【要約】【課題】駅構内や地下街など屋内で歩行者向けナビゲーションシステムを提供する場合、広がりのある複雑な空間内での歩行者経路を一意に表現できるようにする。【解決手段】移動体端末（１０１）は測位を行いサーバに送信し、地図情報サーバ（１０３）はアプリケーションサーバ（１０２）を通して前記測位情報に対応した地図情報を移動体端末（１０１）に送信する。屋内地図ＤＢ（１１１）内にて、多角形分割された屋内空間データを管理し、当該空間データとノードデータを関連づける。空間データ同士が隣接し、かつ、人が遷移可能である（ドアがあるなど）場合、その点を空間接合点としリンクデータを関連づける。経路探索処理部（１０８）がノード・リンクを利用することで屋内においても屋外と同様に経路探索処理を実現する。【選択図】図１
2010164434.tif 000002
【特許請求の範囲】
【請求項１】
移動体端末の位置と目的地の情報から経路を探索し、前記現在位置と前記目的地までの地図情報と前記探索された経路情報を提供する地図情報サーバ装置と、前記地図情報サーバ装置から提供された前記地図情報と前記経路情報とを取得して前記移動体端末に提供するアプリケーションサーバ装置と、を備え、
前記地図情報サーバ装置は、
屋内地図について、屋内空間を分割して形成された多次元の図形で構成される複数の屋内ノードと、屋内ノード間の接合点である屋内リンクとを関連付けて格納する屋内地図データベースを参照し、屋内における前記移動体端末の位置と目的地の情報に関連する前記屋内ノードと前記屋内リンクの情報を取得し、前記移動体端末の位置と目的地までの空間遷移を認識して経路探索を実行し、屋内経路情報を生成する経路探索部と、
前記経路探索部によって生成された前記屋内経路情報に対応する地図情報を取得する地図情報取得部と、
を備えることを特徴とする空間情報管理システム。
【請求項２】
前記経路探索部は、さらに、屋外地図について、経路の変化点を表す複数の屋外ノードと、屋外ノード間の結線である屋外リンクとを関連付けて格納する屋外地図データベースを参照し、屋外における前記移動体端末の位置と屋内及び屋外の境界点に関連する前記屋外ノードと前記屋外リンクの情報を取得し、前記移動体端末の位置と前記境界点までの空間遷移を認識して経路探索を実行して屋外経路情報を生成し、前記屋内経路情報と前記屋外経路情報を繋ぎ合わせて統合経路情報を生成し、
前記地図情報取得部は、前記統合経路情報に対応する地図情報を取得することを特徴とする請求項１に記載の空間情報管理システム。
【請求項３】
前記屋内及び屋外の境界点は、前記屋内データベースでは前記屋内リンクとして管理され、前記屋外データベースでは前記屋外ノードとして管理され、
前記経路探索部は、前記境界点において、前記屋外ノードと前記屋内リンクを結びつけることにより前記屋内経路情報と前記屋外経路情報を統合することを特徴とする請求項２に記載の空間情報管理システム。
【請求項４】
前記経路探索部は、１つの空間として把握される屋内ノードを複数のブロックに分割して生成される複数のサブノードと当該複数のサブノード間の接合点であるサブリンクの情報を用いて、前記１つの空間として把握される屋内ノードの任意の位置までの空間遷移を認識して経路探索を実行して屋内ノード内経路情報を生成し、
前記地図情報取得部は、前記屋内経路情報及び前記屋内ノード内経路情報に対応する地図情報を取得することを特徴とする請求項１に記載の空間情報管理システム。
【請求項５】
移動体端末の位置と目的地の情報から経路を探索し、前記現在位置と前記目的地までの地図情報と前記探索された経路情報を提供する地図情報サーバ装置であって、
屋内地図について、屋内空間を分割して形成された多次元の図形で構成される複数の屋内ノードと、屋内ノード間の接合点である屋内リンクとを関連付けて格納する屋内地図データベースを参照し、屋内における前記移動体端末の位置と目的地の情報に関連する前記屋内ノードと前記屋内リンクの情報を取得し、前記移動体端末の位置と目的地までの空間遷移を認識して経路探索を実行し、屋内経路情報を生成する経路探索部と、
前記経路探索部によって生成された前記屋内経路情報に対応する地図情報を取得する地図情報取得部と、
を備えることを特徴とする地図情報サーバ装置。
【請求項６】
前記経路探索部は、さらに、屋外地図について、経路の変化点を表す複数の屋外ノードと、屋外ノード間の結線である屋外リンクとを関連付けて格納する屋外地図データベースを参照し、屋外における前記移動体端末の位置と屋内及び屋外の境界点に関連する前記屋外ノードと前記屋外リンクの情報を取得し、前記移動体端末の位置と前記境界点までの空間遷移を認識して経路探索を実行して屋外経路情報を生成し、前記屋内経路情報と前記屋外経路情報を繋ぎ合わせて統合経路情報を生成し、
前記地図情報取得部は、前記統合経路情報に対応する地図情報を取得することを特徴とする請求項５に記載の地図情報サーバ装置。
【請求項７】
前記屋内及び屋外の境界点は、前記屋内データベースでは前記屋内リンクとして管理され、前記屋外データベースでは前記屋外ノードとして管理され、
前記経路探索部は、前記境界点において、前記屋外ノードと前記屋内リンクを結びつけることにより前記屋内経路情報と前記屋外経路情報を統合することを特徴とする請求項６に記載の地図情報サーバ装置。
【請求項８】
前記経路探索部は、１つの空間として把握される屋内ノードを複数のブロックに分割して生成される複数のサブノードと当該複数のサブノード間の接合点であるサブリンクの情報を用いて、前記１つの空間として把握される屋内ノードの任意の位置までの空間遷移を認識して経路探索を実行して屋内ノード内経路情報を生成し、
前記地図情報取得部は、前記屋内経路情報及び前記屋内ノード内経路情報に対応する地図情報を取得することを特徴とする請求項５に記載の地図情報サーバ装置。
【請求項９】
コンピュータを請求項５に記載の地図情報サーバ装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、空間情報管理システム、及び地図情報サーバ装置、並びに、プログラムに関し、例えば、屋内及び屋外で利用可能な経路探索の技術に関するものである。
【背景技術】
【０００２】
近年、カーナビゲーションや携帯電話を用いた歩行者向けナビゲーションなど、利用者の位置を利用し経路探索などを行うサービスが普及している。これらは屋外での利用が主であり、利用者位置はＧＰＳ（Global Positioning System）衛星の電波の受信により測位している。利用者は車載端末や携帯端末上で目的地を設定することにより、現在位置から所望の目的地までの経路を探索することが可能となる。
【０００３】
ＧＰＳ受信機を搭載して携帯端末の現在位置を測位する技術はカーナビゲーションや携帯電話を用いたナビゲーションシステムで実用化されており、測位精度の向上も図られている。
【０００４】
しかし、ＧＰＳ衛星からの信号を受信できるエリアにいなければならず、駅構内や地下街、ビル内部など屋内における測位には適していない。
【０００５】
これに対して、建物内部にＧＰＳ衛星信号と等価な信号を発生させる設備を設置する手法や、無線ＬＡＮや携帯電話基地局もしくはＴＶ信号を利用した測位技術が近年開発されており、これらにより屋内においても利用者位置を測位することが可能となってきている。
【０００６】
そのため、歩行者向けナビゲーションにおいて屋外だけではなく駅構内や地下街、複雑なビル内部など屋内においても地図表示や目的地までの経路を分かりやすく案内可能なナビゲーションシステムが期待されている。
【０００７】
屋内での経路探索に関しては、例えば特許文献１及び２において、屋外での道路ネットワークデータのノード及びリンクを拡張し屋内に適用することで、屋内外をシームレスに経路探索する方式が開示されている。
【０００８】
また、一般的な屋外のナビゲーションシステムでは、道路ネットワーク上の交差点をノード、ノード間の線をリンクと捉え、ノードデータ、リンクデータ、そしてリンク上を移動するためのコストデータなどから構成された地図データがデータベース化されているため、出発地と目的地のノードが指定されれば、ダイクストラ法などを利用して経路探索を行うことが可能である。ダイクストラ法を用いた経路探索の方法の概略及び道路ネットワークのノード・リンクに関しては、例えば特許文献３にて開示されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−３３０４３号公報
【特許文献２】特開２００７−２４８４７２号公報
【特許文献３】特開２００１−１６５６８１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、屋内における歩行者ナビゲーションを行う場合、歩行者が通行可能な領域は部屋や広場、改札前など広がりのある空間であることが多く歩行経路が一意に定まらない。そのため屋外で利用者が道路上を移動するのとは異なり歩行経路を線で表現することが難しい。また、展示会場や複合施設内での店舗配置のように、レイアウトが頻繁に変更する場所も多く存在する。このように、屋内空間も対象とし、屋内外シームレスに利用可能な歩行者ナビゲーションを提供する場合、広がりのある複雑な空間内での歩行者経路の表現と、頻繁に変更するレイアウトに対応して経路探索可能な屋内空間情報の管理方式が定まっていない。
【００１１】
そして、屋内において歩行者は、広がりのある空間内を一意の線上を移動しないことが多く、道路を細線化しリンクとするネットワーク構造に合致しない。
【００１２】
また、道路ネットワーク上では交差点やランドマークをノードと設定するが、屋内の場合、１つの部屋に複数の出入り口が存在することが多く、部屋同士や部屋と廊下、ロビー間が複雑に接合するため、ノードをどの座標に設定するべきかが明確でないため、空間ごとに人により手動でネットワーク構造を作成しなければならない。
【００１３】
本発明はこのような状況に鑑みてなされたものであり、屋内における目的地まで利用者をスムーズに誘導することができるナビゲーションを実現するものである。また、本発明は、屋外の出発点から屋内にある目的場所までのナビゲーションを実現する際に、屋外と屋内をシームレスに経路探索することができるナビゲーションを提供するものである。
【課題を解決するための手段】
【００１４】
上記課題を解決するために、本発明による空間情報管理システム（ナビゲーションシステム）は、移動体端末の位置と目的地の情報から経路を探索し、現在位置と目的地までの地図情報と探索された経路情報を提供する地図情報サーバ装置と、地図情報サーバ装置から提供された地図情報と経路情報とを取得して移動体端末に提供するアプリケーションサーバ装置と、を備えている。ここで、地図情報サーバ装置は、屋内地図について、屋内空間を分割して形成された多次元の図形で構成される複数の屋内ノードと、屋内ノード間の接合点である屋内リンクとを関連付けて格納する屋内地図データベースを参照し、屋内における前記移動体端末の位置と目的地の情報に関連する屋内ノードと屋内リンクの情報を取得し、移動体端末の位置と目的地までの空間遷移を認識して経路探索を実行し、屋内経路情報を生成する経路探索部と、経路探索部によって生成された屋内経路情報に対応する地図情報を取得する地図情報取得部と、を備えている。なお、地図情報サーバ装置とアプリケーションサーバ装置は一体であっても良いし、別々に設けられていても良い。
【００１５】
経路探索部は、さらに、屋外地図について、経路の変化点を表す複数の屋外ノードと、屋外ノード間の結線である屋外リンクとを関連付けて格納する屋外地図データベースを参照し、屋外における移動体端末の位置と屋内及び屋外の境界点に関連する屋外ノードと屋外リンクの情報を取得し、移動体端末の位置と境界点までの空間遷移を認識して経路探索を実行して屋外経路情報を生成し、屋内経路情報と前記屋外経路情報を繋ぎ合わせて統合経路情報を生成する。そして、地図情報取得部は、統合経路情報に対応する地図情報を取得する。また、屋内及び屋外の境界点は、屋内データベースでは屋内リンクとして管理され、屋外データベースでは屋外ノードとして管理されている。従って、経路探索部は、境界点において、屋外ノードと屋内リンクを結びつけることにより屋内経路情報と屋外経路情報を統合する。なお、屋外地図データベース及び屋内地図データベースは、物理的に別の場所に存在するサーバ内に設置されていても良いし、地図情報サーバ装置内にあっても良い。
【００１６】
また、経路探索部は、１つの空間として把握される屋内ノードを複数のブロックに分割して生成される複数のサブノードと当該複数のサブノード間の接合点であるサブリンクの情報を用いて、１つの空間として把握される屋内ノードの任意の位置までの空間遷移を認識して経路探索を実行して屋内ノード内経路情報を生成する。そして、地図情報取得部は、屋内経路情報及び屋内ノード内経路情報に対応する地図情報を取得する。
【００１７】
さらなる本発明の特徴は、以下本発明を実施するための最良の形態および添付図面によって明らかになるものである。
【発明の効果】
【００１８】
本発明によれば、屋内における目的地まで利用者をスムーズに誘導することができるナビゲーションを実現することができる。また、屋外の出発点から屋内にある目的場所までのナビゲーションを実現する際に、屋外と屋内をシームレスに経路探索することができるナビゲーションを提供することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の各実施形態で共通して用いられる空間情報管理システム（ナビゲーションシステム）の概略基本構成を示す図である。
【図２】図１における屋内ＤＢ（１１１）で管理される地図データの一例を示す図である。
【図３】空間情報管理システムにおける全体シーケンスを示す図である。
【図４】第１の実施形態における屋内ナビゲーションの例を示す図である。
【図５】第１の実施形態におけるネットワークデータ構築方法を説明するための図である。
【図６】第１の実施形態における誘導画面例を示す図である。
【図７】第１の実施形態における、地図情報サーバによる屋内経路探索処理を説明するためのフローチャートである。
【図８】第２の実施形態における屋内外シームレスナビゲーションの例を示す図である。
【図９】第２の実施形態におけるネットワークデータ構築方法を説明するための図である。
【図１０】第２の実施形態における誘導画面例を示す図である。
【図１１】第２の実施形態における、地図情報サーバによる屋内外経路探索処理を説明するためのフローチャートである。
【図１２】第３の実施形態における広がりのある空間のナビゲーション例を示す図である。
【図１３】第３の実施形態における、地図情報サーバによる屋内空間経路探索処理を説明するためのフローチャートである。
【図１４】屋内シームレスナビゲーションサービスのイメージ図である。
【発明を実施するための形態】
【００２０】
本発明は、屋内には屋外のようなポイントとしてのノードの考え方を導入するのは困難であるので、その問題点を解決すべく、図形（ポリゴン）をノードとして適切に設定することにより屋内におけるスムーズなナビゲーションを実現する。また、本発明は、ノードの考え方が屋内と屋外が異なるため、屋外と屋内をシームレスにつなぐための工夫を提供する。
【００２１】
以下、添付図面を参照して本発明の実施形態について説明する。ただし、本実施形態は本発明を実現するための一例に過ぎず、本発明の技術的範囲を限定するものではないことに注意すべきであり、構成や処理手順などの異なった各種の変形がありうる。なお、各図において共通の構成については同一の参照番号が付されている。
【００２２】
まず、各実施形態における共通事項としてシステム構成、屋内ＤＢ内のデータ構造、及び全体のシーケンスについて説明する。そして、第１の実施形態により、屋内におけるナビゲーションの基本的な考え方を示す。また、第２実施形態により、屋外にある出発点から屋内にある目的場所へのシームレスなナビゲーションの実現について示す。さらに、第３の実施形態により、比較的大きな空間（部屋）内において適切なナビゲーションを実現する方法について示す。
【００２３】
１）各実施形態における共通事項
＜システム構成＞
図１は、本発明の各実施形態で共通して用いられる空間情報管理システム（ナビゲーションシステム）１０の概略基本構成を示す図である。
【００２４】
図１に示されるように、空間情報管理システム１０は、移動体端末（１０１）と、アプリケーションサーバ（１０２）と、地図情報サーバ（１０３）と、によって構成される。そして、移動体端末（１０１）とアプリケーションサーバ（１０２）、及びアプリケーションサーバ（１０２）と地図情報サーバ（１０３）はそれぞれネットワーク（１２１）で接続されており、ネットワーク（１２１）を介して情報のやり取りが実現される。
【００２５】
移動体端末（１０１）は、利用者が常に所持携帯する携帯電話やＰＤＡなどの携帯情報端末を想定している。
【００２６】
また、アプリケーションサーバ（１０２）は、移動体端末（１０１）の位置データを受信するか、或いは、移動体端末（１０１）のＩＤ情報を受信してそれに基づいて位置を測位する測位データ取得部（１０４）と、地図情報サーバ（１０３）から地図を取得し必要であれば編集を行った上で移動体端末（１０１）に地図を送信する地図情報送信部（１０５）と、を備えている。
【００２７】
地図情報サーバ（１０３）は、経路探索結果と地図情報を用いて地図データを描画する地図表示処理部（１０６）と、ネットワークデータを用いて経路探索する経路探索処理部（１０８）と、既存建物構造データを外部より取得・変換する地図データ変換部（１１２）と、ＤＢ（データベース）にアクセスする地図データ参照部（１０９）を有する。当該ＤＢは屋外地図に関連するデータを有する屋外地図ＤＢ（１１０）と屋内地図に関連するデータを有する屋内ＤＢ（１１１）から構成される。なお、各ＤＢに関しては、ＤＢを管理する事業主体が異なる場合もあるので、別サーバに配置されていても良い。また、これらの処理部は、コンピュータ・プログラム、あるいはスクリプトなどとして実現され、動作する。
【００２８】
なお、サーバ・端末ぞれぞれはデータを送受信するための処理部を有するが、図１においては省略している。
【００２９】
＜屋内ＤＢ内の地図データの例＞
次に、各実施形態で使用される屋内ＤＢ内の地図データの例について説明する。図２は、図１における屋内ＤＢ（１１１）で管理される地図データの一例を示す図である。
【００３０】
本発明の各実施形態において、屋内空間は、基本的に多角形に分割され図形形状と座標、属性情報を図形データにて管理されている。ドアなどの多角形に分割された空間の間の接合点も点としての図形形状と座標、属性情報を同様に管理されている。
【００３１】
また、屋外道路と同様に経路探索に必要なネットワーク構造は、ノードデータとリンクデータにより管理される。屋内空間のノードは、屋外空間（屋外のノードは点で管理される）とは異なり、それぞれ屋内空間の多角形に関連付けられている。また、屋内空間のリンクは、屋外空間（点であるノードとノードを結ぶ線分）とは異なり、前述のドアなど隣接する空間の間で利用者が移動することができる場合のその接合点に関連付けられている。もし空間同士が隣接していても壁による接合で直接移動することができない場合、空間接合点は存在せず、よってリンクも存在しない。
【００３２】
図２において、２０１は屋内空間の形状を表す図形データの一例である。図形データは、例えば、形状を一意に識別する図形ＩＤ（２０２）と、図形の種別を示す種別（２０３）と、当該図形の座標値のリストである座標列（２０４）とにより構成される。図形が多角形であれば座標列（２０４）は頂点の数だけの座標値がリストされており、空間接合点であれば１点の座標値のみ管理される。つまり、２次元（３次元地図によるナビゲーションであれば３次元）図形であればそれはノードの情報であり、点であればそれはリンクの情報である。
【００３３】
２１１はノードデータの一例である。ノードデータはノードに関する情報を記録した表形式の構造であり、ノードＩＤ（２１２）にて識別される１つの行に一つのノードに関する情報が格納される。ノードデータは、例えば、ノードを一意に識別するノードＩＤ（２１２）と、ノードが関連付けられている屋内空間の形状を一意に区別する図形ＩＤ（２１３）と、関連付けられている屋内空間の種別を表すノード種別（２１４）と、当該ノードが存在するエリアを表すエリア種別（２１５）とによって構成される。
【００３４】
２２１はリンクデータの一例である。リンクデータは、リンクに関する情報を記録した表形式の構造であり、リンクＩＤ（２２２）にて識別される１つの行に一つのリンクに関する情報が格納される。リンクデータは、例えば、リンクに関連付けられているドアなどの空間接合点を一意に示す識別番号である図形ＩＤ（２２３）と、当該リンクの端点ノードを意味する始点ノード（２２４）と、終点ノード（２２５と）、リンクが同エリア内か別階層間をつなぐリンクなのか、もしくは屋外と屋内をつなぐリンクなのかを識別するリンク種別（２２６）と、当該リンクをたどって端点間を移動するためのコストを示すコスト（２２７）と、によって構成される。なお、コストは、ネットワークモデルを辿るためにどの位の時間が掛かるかを示す重み付け係数である。距離が長ければコストの値も高くなり、例えば、同一エリア内であれば移動するのに困難性はないのでコスト値は低くなるように値が設定されている。
【００３５】
これらノードとリンクは関連づけられている空間上の形状が屋外の場合と異なるものの、任意のノードを始点とし、当該始点のノードＩＤを用いてノードデータを検索すると、ノードに接続されたリンクＩＤの一覧を取得することができる。
【００３６】
また、この取得したリンクＩＤを用いてリンクデータを検索するとその接続先のノードＩＤが取得できる。この手順を繰り返すことで、任意のノードからノードまでの経路を探索することが可能である。ノード・リンクをたどる手順は前述のダイクストラ法やその他にも既存の方式がいくつも存在するが、ノード・リンクを利用する探索方式であれば、使用することができる。
【００３７】
図２に示したこれらの構成は一例であり、地図を矩形に分割し管理するためのメッシュＩＤなど、本実施例にて例示されない公知の機能を実現するための情報を付加してもよい。
【００３８】
＜処理シーケンス＞
図３は、本発明の各実施形態による、経路探索要求から地図情報取得までの基本処理のシーケンス（例）を示す図である。
【００３９】
図３において、まず移動体端末（１０１）が測位した位置データをアプリケーションサーバ（１０２）に送信する（ステップ３０１）。ここで測位の手法としては、前述のように屋外においてはＧＰＳであることが多いと考えられるが、無線ＬＡＮや携帯電話基地局を利用した測位の場合もある。また、建物内部に設置されたＧＰＳ衛星信号と等価な信号を発生させる設備からの信号を受信し測位する手法も考えられる。無線ＬＡＮの場合には、移動体端末（１０１）での測位は行われず、例えば、ビーコン等の識別情報がアプリケーションサーバ（１０２）に移動体端末（１０１）から送信され、アプリケーションサーバ（１０２）でその識別情報から移動体端末（１０１）の位置が計測される。また、ステップ３０１においては、移動体端末（１０１）がＧＰＳ衛星信号を受信し位置を計算しアプリケーションサーバ（１０２）に送る処理の場合もあるが、環境に設置された設備が移動体端末（１０１）の位置を計算し、その位置データを、移動体端末（１０１）を介して、もしくは移動体端末（１０１）を介さずに直接に、アプリケーションサーバ（１０２）に送信することも考えられる。
【００４０】
次に、アプリケーションサーバ（１０２）の測位データ取得部（１０４）は、測位データと、利用者の指示に応じて経路探索結果の送信を地図情報サーバ（１０３）に要求する（ステップ３０２）。
【００４１】
地図情報サーバ（１０３）が経路探索結果送信要求をアプリケーションサーバ（１０２）から受信すると、経路探索処理部（１０８）が、測位データや指定された目的地、条件などに従い経路探索処理を行う（ステップ３０３）。この処理は、前述のダイクストラ法など、ノードとリンクを利用して最短経路を探索する方式により実現される。
【００４２】
続いて、地図情報サーバ（１０３）の地図データ参照部（１０９）は、ステップ３０３の経路探索結果や利用者が指定した条件に基づき必要となる地図情報をＤＢ１１０及び／又は１１１から検索する（ステップ３０４）。
【００４３】
さらに、地図表示処理部（１０６）は、ステップ３０３とステップ３０４の結果得られた経路探索結果と地図情報を用いて、地図情報を描画する（ステップ３０５）。
【００４４】
そして、地図情報サーバ（１０３）は、描画された地図情報を、直接或いはアプリケーションサーバ（１０２）を介して、移動体端末（１０１）に送信する（ステップ３０６）。
【００４５】
なお、アプリケーションサーバ（１０２）が描画機能を備える場合には、地図情報サーバ（１０３）がステップ３０３とステップ３０４の結果得られた経路探索結果と地図情報をアプリケーションサーバ（１０２）に送信し、アプリケーションサーバ（１０２）が受信した情報を用いて、地図画像を描画するようにしてもよい。
【００４６】
２）第１の実施形態
＜屋内ナビゲーションの概念＞
第１の実施形態は、屋内ナビゲーションに関するものである。図４は、屋内ナビゲーションの概念を説明するための図である。図４では、建物はエレベータと廊下、部屋から構成されている。図４を用いて、右上のエレベータを降りた地点から、右下の部屋内部までの経路を誘導する例を説明する。
【００４７】
まず、建物を多角形に分割しそれぞれノードとリンクに関連付けていく。本発明では、屋内において、２次元又は３次元（地図表示による）の図形をノードとし、ノード（図形）とノード（図形）の接合点をリンク（点）とすることが特徴となっている。つまり、本発明における屋内のノードとは、２次元又は３次元の広がり又は空間を有する図形をいい、屋内のリンクとはノードとノードの接合点をいう。
【００４８】
図５を用いて説明すると、５０１はエレベータを表し、ノードＩＤがＮ００１に関連付けられている。５０２はエレベータ（５０１）前の廊下を表し、ノードＩＤがＮ００２と関連付けられている。５０３も同様に廊下を表し２つの廊下が合流する空間を表している。ノードＩＤがＮ００３と関連付けられている。５０４は目的地の部屋に隣接する廊下を示し、ノードＩＤがＮ００４に関連づけられている。５０５は目的地の部屋を示し、ノードＩＤがＮ００５に関連付けられている。このように、各図形（空間）がノードとして定義されている。
【００４９】
次に、５１１はエレベータ（５０１）と廊下（５０２）の間をつなぐ接合点であり、リンクＩＤがＬ００１に関連づけられている。５１２は廊下（５０２）と廊下（５０３）の間をつなぐ接合点であり、リンクＩＤがＬ００２と関連づけられている。５１３は廊下（５０３）と廊下（５０４）の間をつなぐ接合点であり、リンクＩＤがＬ００３と関連づけられている。５１４は廊下（５０４）と目的地の部屋（５０５）の間をつなぐ接合点であり、リンクＩＤがＬ００４と関連づけられている。
【００５０】
ここで、屋内データの一例である図２を用いてノード・リンクをたどって経路探索を行う方法を説明する。エレベータ５０１はノードＩＤ＿Ｎ００１に関連付けられているため、探索用リンクデータ２２１内でＮ００１に接続するリンクを検索するとＬ００１がヒットする。検索結果がＬ００１のみのため、移動できる方向はＬ００１を辿るしかないと判明する。次に、探索用リンクデータ２２１内のＬ００１の行によるとリンクがつなぐ空間はＮ００２であると判明する。探索用ノードデータ２１１内でＮ００２を検索すると、当該ノードに関連付けられているのは廊下（５０２）と判明する。さらに、Ｎ００２に接続するリンクを探索用リンクデータ２２１にて検索する。以上を繰り返すことにより、目的地の部屋５０５までの経路探索を行うことが可能となる。
【００５１】
図６は、上記ノード・リンクによる経路探索結果を用いて、利用者に経路を誘導する方法の一例を示す図である。経路探索により隣接する空間から空間へ、どの接合点を通って移動するべきかを特定できているため、移動すべき空間接合点を矢印により示している。これは誘導方法の一例であり、分かりやすい色で経路を描画し誘導する方法や、曲がり角などポイントとなる場所で音声ガイダンスをするなどの方法もありうる。
【００５２】
＜屋内経路探索処理の内容＞
続いて、以上説明した本発明における屋内経路探索処理の詳細について説明する。図７は、地図情報サーバによる屋内経路探索処理を説明するためのフローチャートである。
【００５３】
地図情報サーバ（１０３）は、アプリケーションサーバ（１０２）から利用者の現在位置測位データと、利用者の指示による目的地情報や検索条件などを受信する（ステップ７０１）。
【００５４】
経路探索処理部（１０８）は、受信した測位データ座標などから利用者が存在する部屋の図形ＩＤを計算し、対応するノードＩＤを検索する（ステップ７０２）。同様に、経路探索処理部（１０８）は、目的地に関しても図形ＩＤを取得し、対応するノードＩＤを検索し（ステップ７０３）、２地点のノードＩＤの間の最短経路を探索する（ステップ７０４）。これはネットワークデータ間の任意の２つのノード間の最短経路探索であり、既述のように屋外ネットワークデータで使われてきているダイクストラ法など既存の手法を適宜利用する。
【００５５】
次に、地図データ参照部（１０９）は、屋内地図ＤＢ（１１１）を参照して、経路探索結果に対応する地図情報（誘導情報含む）を検索する（ステップ７０５）。第１の実施形態に示した例でいうと、探索結果であるネットワークデータに対応するエレベータから廊下を通って部屋まで続く地図情報と、各図形間の接続点情報が検索される。
【００５６】
最後に、地図表示処理部（１０６）は、上記探索結果のネットワークデータと、地図情報データを用いて地図情報を描画し、アプリケーションサーバ（１０２）を介して、或いは介さずに直接、移動体端末（１０１）に送信し、処理が終了となる（ステップ７０６）。なお、この処理は、地図情報描画処理が地図情報サーバ（１０３）で実行される場合の処理を示しているが、アプリケーションサーバ（１０２）が描画機能を有している場合には、アプリケーションサーバ（１０２）で地図情報描画処理が実行されるようにしても良い。
【００５７】
３）第２の実施形態
＜シームレスナビゲーションにおけるノードとリンクの関係＞
第２の実施形態は、屋外から屋内へのシームレスナビゲーションに関するものである。図８は、屋外（例：道路）から屋内（例：建物）へのシームレスナビゲーションの例を示す図である。図８に示されるように、建物が存在する敷地は屋外道路と接続しており、門を通して外部と行き来が可能となっている。ここで、右下から道路をたどり門を通ってエレベータに入り、エレベータを降り廊下を通って右下の部屋内部までの経路を誘導することを考える。
【００５８】
図９を参照して、道路と建物データをそれぞれノードとリンクに関連付けていく方法について説明する。図９では、道路下側（８２４）を始点としている。８２４はノードＩＤがＮ０１４と関連づけられている。次に、建物前の道路地点（８２３）はノードＩＤがＮ１０３に関連付けられており、Ｎ１０４とＮ１０３間をつなぐ道路（８３２）はリンクＩＤがＬ１０２に関連づけられている。同様に門（８２２）はノードＩＤがＮ１０２に関連づけられており、Ｎ１０３とＮ１０２間をつなぐ道路（８３３）はリンクＩＤがＬ１０３に関連づけられている。さらに、建物が外部につながるドア部分（８２１）はノードＩＤがＮ１０１に関連づけられており、Ｎ１０２とＮ１０１間をつなぐ道路８３４はリンクＩＤがＬ１０４に関連づけられている。ドア部分（８２１）により屋内ネットワークにつながっている。エレベータ（５０１）以降の屋内空間管理は図５を用いて説明した通りである。このように、屋外では各ノードは点で、リンクは線で表されているのに対し、屋内（図５参照）では各ノードは図形で、リンクはノードとノードの接合点で表されている。ただし、屋外と屋内の境界（図９の例ではエレベータのドア部分８２１）は、屋外から見た場合にはノードであり、屋内から見た場合にはリンクとなっている。
【００５９】
＜シームレスナビゲーションにおける経路探索方法＞
続いて、第２の実施形態における経路探索方法について説明する。屋外道路のノードとリンクの設定の方法は既存方式である。本発明の特徴は屋外と屋内の接続部分にあり、本実施形態ではドア部分８２１を屋内データ管理上はエレベータ空間（５０１）と外部空間をつなぐ空間接合点であり、リンクＩＤがＬ００５に関連づけられている点である。同一の図形を屋外データ管理上はノードＮ１０１、屋内データ管理上はリンクＬ００５とし、ネットワークデータにおいてはノードＮ１０１がリンクＬ００５と接続していると構造化する。これにより、ダイクストラ法など既存の経路探索手法を用いて屋内外をシームレスに経路探索することができる。
【００６０】
図１０は、上記ノード・リンクによる経路探索結果を用いて、利用者に経路を誘導する方法の一例を示す図である。屋外では利用者が道路や歩行通路などリンク上をたどることが想定できるため、経路探索結果のルート上を矢印線にて表現している。屋外から屋内に入る接合点を通過した後は、図６で説明したのと同様に経路探索により隣接する空間から空間へ、どの接合点を通って移動するべきかを特定できているため、移動すべき空間接合点を矢印により示している。これは誘導方法の一例であり、分かりやすい色で経路を描画し誘導する方法や、曲がり角などポイントとなる場所で音声ガイダンスをするなどの方法もありうる。
【００６１】
＜屋内外シームレス経路探索処理の内容＞
図１１は、第２の実施形態による屋内外シームレス経路探索処理の詳細について説明するための、地図情報サーバにおける動作フローチャートである。本実施形態では屋外から屋内への経路探索を例としているが、屋内から屋外の場合でも同様に適用可能である。
【００６２】
地図情報サーバ（１０３）は、アプリケーションサーバ（１０２）から利用者の現在位置測位データと、利用者の指示による目的地情報や検索条件などを受信する（ステップ１１０１）。そして、経路探索処理部（１０８）は、受信した測位データ座標などから利用者が存在する位置に対応する屋外ネットワーク内のノードＩＤを検索する（ステップ１１０２）。
【００６３】
次に、経路探索処理部（１０８）は、図示しない屋外ノード／リンクデータベースを参照して、目的地の部屋を含む建物に対応する屋外ネットワーク内のノードＩＤを検索する（ステップ１１０３）。そして、経路探索処理部（１０８）は、上記２つの屋外ノードＩＤ間の経路探索を行う（ステップ１１０４）。これは既存の屋外ネットワーク経路探索手法を利用する。
【００６４】
続いて、経路探索処理部（１０８）は、目的地建物が屋外と接続する点が屋内ネットワーク内で対応するリンクＩＤを検索する（ステップ１１０５）。つまり、この処理は、ステップ１１０３で検索した屋外ノードＩＤに対応する屋内ネットワーク上でのリンクＩＤを検索するものである。図９の例では、屋外ネットワーク上でのノードＩＤはＮ１０１、屋内ネットワーク上でのリンクＩＤはＬ００５となる。このリンクＩＤを始点として、経路探索処理部（１０８）は、目的地部屋までの屋内経路探索処理を実行する（ステップ１１０６）。この処理は、第１の実施形態の処理（図７参照）で示したものと同じである。
【００６５】
最後に、経路探索処理部（１０８）がステップ１１０４で取得した屋外ネットワークデータとステップ１１０６で取得したネットワークデータをつなげ、地図データ参照部（１０９）が対応する地図情報を検索し、アプリケーションサーバ（１０２）へ送信し処理が終了となる（ステップ１１０７）。
【００６６】
４）第３の実施形態
第３の実施形態は、多角形分割し管理されている屋内空間が大部屋など大きな広がりをもつ空間である場合、また、展示場など比較的頻繁にレイアウトが変わる性質の空間である場合のナビゲーションに関するものである。
【００６７】
＜広がりのある空間におけるナビゲーションの例＞
図１２は、広がりのある空間におけるナビゲーションの概念を説明するための図である。第３の実施形態では、目的地の部屋の中の任意の地点まで限定した経路探索を目的とする。
【００６８】
まず、部屋の入り口である空間接合点までは第１の実施形態で説明した屋内経路探索を適用することができる。部屋内の空間はまず人が通る空間を適度な粒度のセル（１００１）に分割される。それぞれのセルを第１の実施形態における多角形分割して空間と同様に管理しノードを関連づける。また、セル間は全て空間接合点とし全てリンクを関連付ける。そして、第１の実施形態で説明したノード・リンクをたどる経路探索方式を用いて行き止まりになるまで全パターン検索を行うことで、最終的に目的地までの経路探索を行うことが可能となる。
【００６９】
本実施形態の場合、セルとセル間の接合点管理は、第１の実施形態で説明したデータテーブルとは独立に管理するか、メモリ上で管理するなどして、頻繁なレイアウト変更に際しても半恒久的な建物内部空間データの管理とは独立させておいても良い。
【００７０】
＜屋内空間の経路探索処理の内容＞
図１３は、第３の実施形態による広がりのある屋内空間の経路探索処理の詳細について説明するための、地図情報サーバ（１０３）の動作フローチャートである。
【００７１】
地図情報サーバ（１０３）は、アプリケーションサーバ（１０２）から利用者の現在位置測位データと、利用者の指示による目的地情報や検索条件などを受信する（ステップ１３０１）。そして、経路探索処理部（１０８）は、目的地の広がりのある屋内空間を適度な粒度のセルに分割する（ステップ１３０２）。
【００７２】
また、経路探索処理部（１０８）は、これらのセルそれぞれに屋内ネットワーク上でのノードＩＤを付番し、また隣接するセル間の接続点は全て通過可能と認識しリンクＩＤを付番する（ステップ１３０３）。
【００７３】
続いて、経路探索処理部（１０８）は、利用者が指定した目的地点を含むセルに対応するノードＩＤを検索し（ステップ１３０４）、第１の実施形態で説明した方法（図７参照）により屋内経路探索を実行し、処理が終了となる（ステップ１３０５）。
【００７４】
５）ナビゲーションサービスのイメージ
図１４は、本発明の各実施形態により実現される屋内外シームレスナビゲーションサービスのイメージを示す図である。屋外地図と屋内地図が利用者の携帯端末上で同時に表示され、屋内外をシームレスに経路探索し誘導される。ここで屋外地図（１２０１）、屋内地図（１２０２）それぞれのデータソースは異なる地図ベンダより提供されると想定されるが、図１で示した地図データ変換部（１１２）により本発明で提案されるシステム内にて管理される。この場合、屋内地図（１２０２）は所謂地図データではなく、建物構造を示すＣＡＤデータを用いて、屋内空間の多角形分割を行い、ノード・リンクなどのネットワーク構造を構築する場合もある。
【００７５】
６）まとめ
第１の実施形態では、屋内地図について、屋内空間を分割して形成された多次元の図形で構成される複数の屋内ノード（地図が２次元であれば２次元図形、地図が３次元であれば３次元図形）と、屋内ノード間の接合点である屋内リンクとを関連付けて格納する屋内地図データベースを参照し、屋内における前記移動体端末の位置と目的地の情報に関連する屋内ノードと屋内リンクの情報を取得し、移動体端末の位置と目的地までの空間遷移を認識して経路探索を実行する。このようにすることにより、屋外のようにはリンクとノードを管理できない屋内であっても、適切に経路探索することができ、スムーズにナビゲーション情報を利用者に提供することができるようになる。なお、地図情報サーバ装置とアプリケーションサーバ装置は一体であっても良いし、別々に設けられていても良く、様々な態様が考えられる。
【００７６】
第２の実施形態では、屋内外のシームレスなナビゲーションを実現している。より具体的には、屋外地図について、経路の変化点を表す複数の屋外ノードと、屋外ノード間の結線である屋外リンクとを関連付けて格納する屋外地図データベースを参照し、屋外における移動体端末の位置と屋内及び屋外の境界点に関連する屋外ノードと屋外リンクの情報を取得し、移動体端末の位置と境界点までの空間遷移を認識して経路探索を実行して屋外経路情報を生成する。屋内経路情報と屋外経路情報は繋ぎ合わされて提供される。また、屋内及び屋外の境界点は、屋内データベースでは屋内リンクとして管理され、屋外データベースでは屋外ノードとして管理されている。従って、経路探索部は、境界点において、屋外ノードと屋内リンクを結びつけることにより屋内経路情報と屋外経路情報を統合する。このようにすることにより、屋内外においてノード及びリンクの定義は異なるが、屋内外においてシームレスなナビゲーションを実現することができる。なお、屋外地図データベース及び屋内地図データベースは、物理的に別の場所に存在するサーバ内に設置されていても良いし、地図情報サーバ装置内にあっても良く、様々な態様が考えられる。
【００７７】
第３の実施形態では、１つの空間として把握される屋内ノード（部屋等のある程度広がりのある空間や頻繁にレイアウトが変更される空間）を複数のブロック（所定サイズのブロック）に分割して生成される複数のサブノードと当該複数のサブノード間の接合点であるサブリンクの情報を用いて、１つの空間として把握される屋内ノードの任意の位置までの空間遷移を認識して経路探索を実行して屋内ノード内経路情報を生成する。このようにすることにより、比較的大空間（展示会場等）であっても、適切なナビゲーションを実現することができる。
【００７８】
なお、本発明は、実施形態の機能を実現するソフトウェアのプログラムコードによっても実現できる。この場合、プログラムコードを記録した記憶媒体をシステム或は装置に提供し、そのシステム或は装置のコンピュータ（又はＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出す。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコード自体、及びそれを記憶した記憶媒体は本発明を構成することになる。このようなプログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどが用いられる。
【００７９】
また、プログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）などが実際の処理の一部又は全部を行い、その処理によって前述した実施の形態の機能が実現されるようにしてもよい。さらに、記憶媒体から読み出されたプログラムコードが、コンピュータ上のメモリに書きこまれた後、そのプログラムコードの指示に基づき、コンピュータのＣＰＵなどが実際の処理の一部又は全部を行い、その処理によって前述した実施の形態の機能が実現されるようにしてもよい。
【００８０】
また、実施の形態の機能を実現するソフトウェアのプログラムコードを、ネットワークを介して配信することにより、それをシステム又は装置のハードディスクやメモリ等の記憶手段又はＣＤ-ＲＷ、ＣＤ-Ｒ等の記憶媒体に格納し、使用時にそのシステム又は装置のコンピュータ(又はＣＰＵやＭＰＵ)が当該記憶手段や当該記憶媒体に格納されたプログラムコードを読み出して実行するようにしても良い。
【符号の説明】
【００８１】
１０１：  移動体端末
１０２：  アプリケーションサーバ
１０３：  地図情報サーバ
１０４：  測位データ受信部
１０５：  地図情報送信部
１０６：  地図表示処理部
１０８：  経路探索処理部
１０９：  地図データ参照部
１１０：  屋外地図データベース
１１１：  屋内地図データベース
１１２：  地図データ変換部
１２１：  ネットワーク
２０１：  図形データ構造の例
２１１：  探索用ノードデータ構造の例
２２１：  探索用リンクデータ構造の例
１００１：  屋内空間をセル分割した際のセル
１２０１：  屋外地図データソース
１２０２：  屋内地図データソース
【図１】
2010164434.tif 000003
【図２】
2010164434.tif 000004
【図３】
2010164434.tif 000005
【図４】
2010164434.tif 000006
【図５】
2010164434.tif 000007
【図６】
2010164434.tif 000008
【図７】
2010164434.tif 000009
【図８】
2010164434.tif 000010
【図９】
2010164434.tif 000011
【図１０】
2010164434.tif 000012
【図１１】
2010164434.tif 000013
【図１２】
2010164434.tif 000014
【図１３】
2010164434.tif 000015
【図１４】
2010164434.tif 000016