JP2016048238A - ナビゲーションシステム、ナビゲーション方法及びプログラム - Google Patents

Abstract

【課題】利用者の安全性をより高めることができるナビゲーションシステム、ナビゲーション方法及びプログラムを提供する。
【解決手段】可視マップ生成部１１は、地理情報システム２から提供される３次元地図情報に基づいて、地図上の道路ネットワークにおける複数のノード各々で道標として存在位置を知覚できるランドマークを、ノード毎に抽出する。経路探索部１２は、可視マップ生成部１１で抽出されたノード毎のランドマークに基づいて、道標となるランドマークの数及び切り替え頻度が少なくなるように、出発地から目的地までノード間を移動可能な経路を探索する。
【選択図】図３

Description

この発明は、ナビゲーションシステム、ナビゲーション方法及びプログラムに関する。

ナビゲーションシステムは、スマートフォン等の携帯機器へ提供されるサービスとして一般化している。歩行者や二輪車の運転者を含む多くの者がこのサービスを利用している。しかしながら、利用者が移動中に携帯機器の画面を注視することで、利用者の周囲への警戒が疎かになるという問題が表面化している。

利用者が携帯端末のナビゲーション画面に表示された地図情報を再確認することなく、安全に、現在の進路の正しさを確認するための方法には、音声ガイドによる方法と、記憶しやすい道標（ランドマーク）を用いる方法とがある。

前者の方法は、音声が聞き取りやすい自動車内での利用に効果を発揮している。しかし、歩行者及び二輪車の運転者に対してこの方法を適用する場合には、周囲の音声情報を遮断することになり、安全性から言って望ましくない状況が発生する。

後者の方法は、進路上に見えるランドマークを事前に利用者に認識させることで、進路の確認を行う方法である。この方法は、古くから経路を案内する際に用いられている。例えば、郵便局やコンビニエンスストア、高層建造物等をランドマークとして利用したものは、店舗等の案内地図にも頻繁に見られる。この方法によれば、利用者が周囲をよく見ながら、進路確認を行うことができるので、利用者の安全性が損なわれる場面も少なくなる。

利用者にとっては、道標とするランドマークの数及び切り替え頻度は少ない方がよい。したがって、ランドマークを用いた案内方法では、経路の距離のみに着目した経路探索手法とは異なり、ランドマークの可視性も同時に考慮するのが望ましい。

ランドマークの視認性を考慮した経路探索を行うために様々な手法が提案されている（例えば、特許文献１、非特許文献１、２参照）。特許文献１は、視認性の高いものをランドマークとして利用し、さらに音により曲がり角を指示することで目的を目指すアプローチを取る技術を開示している。しかし、特許文献１には、具体的な視認性の計算手法や、経路探索手法、音以外による曲がり角の指示手法などについての具体的な記述はない。非特許文献１に記載の手法では、経路探索の際に、あるランドマークに対する連続的な視認性を考慮するとともに、複数のランドマークを切り替えながら目的地を目指すアプローチを取る。この方法では、ランドマークとして用いる店舗等の昼夜による外観の違いにも配慮し、案内を行う際の時刻に応じて、道標として利用するランドマークを切り替える工夫を行っている。

また、ランドマークとなる建物が継続して見えることが、歩行者の安心につながるという報告がある（例えば、非特許文献２参照）。さらに、最短経路の探索を行う際に、数百の交差点からなる小規模な道路ネットワークの情報に対して、Ｄｉｊｋｓｔｒａ法による経路探索が実施されている（例えば、非特許文献３参照）。Ｄｉｊｋｓｔｒａ法は、ノード間に距離のみが与えられている経路の探索アルゴリズムとして非常に有用であるものの、経路を逐次的に決定していく方法であるため、経路全体において案内に用いるランドマーク数を最小化することが難しい。

以上のことから、数万のノードから構成される実用的な規模の道路ネットワーク上で、ランドマークの視認性を考慮した経路探索を行うために、新たな工夫が必要となる。他に、視認性を考慮した経路探索手法として、景観の可視性を考慮した経路探索システムが提案されている（例えば、非特許文献４参照）。このシステムでは、経路からの景観の可視性を計測し、同じ景観（例えば富士山等）が連続的に見える経路のランク付けを行うことで、経路を決定している。

上記非特許文献４に開示された方法では、天候や時刻などの要因により変化するランドマークの視認性に基づいて経路探索を行っているが、同じランドマークに関してどの程度見え続けるかというような連続性を考慮した経路探索は行われていない。

特開２００７−１３９４２５号公報

中澤啓介，岡田謙一，"ランドマークの視認性に基づいた動的な案内地図生成"，情報処理学会論文誌，Vol. 48，No. 1，2008. 宇戸裕人，古川宏，"ランドマークの定量的評価に基づく歩行者の不安を軽減する経路探索アルゴリズム（自動車運転／位置情報／通信技術）"，シンポジウムモバイル研究論文集2010，27-32, 2010. E. W. Dijkstra, "A Note On Two Problems In Connexion Withgraphs.", NUMERISCHE MATHEMATIK, Vol. 1, No. 1, pp. 269-271, 1959. 河野亜希, 谷村孟紀, 崔楊, 河合由起子, 川崎洋."景観の可視性を考慮したルート探索システムの提案"，情報科学技術レターズ，Vol. 6，No. LK-005，pp. 351-354，2007.

上述のように、従来のナビゲーションシステムでは、案内の際の道標となるランドマークの数及び切り替え頻度を少なくして、ナビゲーション画面を見る回数を減らすことにより、利用者の安全性をより高めるための具体的な方法は、いまだ確立されていない。

この発明は、上記のような問題点を解決するためになされたものであり、利用者の安全性をより高めることができるナビゲーションシステム、ナビゲーション方法及びプログラムを提供することを目的とする。

上記目的を達成するため、この発明の第１の観点に係るナビゲーションシステムは、
地理情報システムから提供される３次元地図情報に基づいて、地図上の道路ネットワークにおける複数のノード各々で道標として存在位置を知覚できるランドマークを、前記ノード毎に抽出するランドマーク抽出部と、
前記ランドマーク抽出部で抽出されたノード毎のランドマークに基づいて、道標となるランドマークの数及び切り替え頻度が少なくなるように、出発地から目的地まで前記ノード間を移動可能な経路を探索する経路探索部と、
を備える。

前記ランドマーク抽出部は、
前記地図を複数の領域に分割し、
複数のランドマークを背の高い順に前記領域毎に選択し、
選択されたランドマークの中から、前記ノード毎に可視率が高い順にランドマークを抽出する、
こととしてもよい。

前記ランドマーク抽出部は、
前記地理情報システムから提供される３次元地図情報に基づいて、複数のノード各々からの３次元コンピュータグラフィック画像データを生成し、
生成された３次元コンピュータグラフィック画像データにおける前記ランドマークの画像をレンダリングし、
レンダリングされた前記ランドマークに基づいて、前記ランドマークの可視率を求め、
求められた可視率に基づいて、前記複数のノード各々から視認できるランドマークを、前記ノード毎に抽出する、
こととしてもよい。

前記ランドマーク抽出部は、
インターネット上に投稿されたランドマークに関する情報と、その情報が投稿された位置情報とに基づいて、前記ランドマークの存在位置を知覚できる範囲を求め、前記ランドマークの可視率に相当する値を決定する、
こととしてもよい。

前記経路探索部は、
前記出発地から前記目的地までに通過する複数のノード各々について、道標として選択されたランドマークの可視率と、
隣接するノード間での道標とするランドマークの切り替え頻度と、
をコストとするコスト関数の値が最小となるように、
前記出発地から前記目的地までの経路を探索する、
こととしてもよい。

前記経路探索部は、
前記出発地から前記目的地までの経路の距離を前記コスト関数のコストとしてさらに加えて、前記出発地から前記目的地までの経路を探索する、
こととしてもよい。

前記経路探索部は、
最適化アルゴリズムを用いて、前記出発地から前記目的地までの経路を探索する、
こととしてもよい。
なお、以下の実施形態では、遺伝的アルゴリズムを利用するが、解候補の生成と評価とを繰り返すアルゴリズムであれば、他のアルゴリズムを用いてもよい。このように試行錯誤的に解候補の生成及び評価を行うことにより最適化するアルゴリズムとしては、他に、ランダム法、シンプレックス法、山登り法、焼き鈍し法、タブー探索などの単点探索アルゴリズム、または、遺伝的アルゴリズム、粒子群最適化、蟻コロニー最適化などの多点探索アルゴリズムなどが挙げられる。

前記ランドマーク抽出部は、
地理情報システムから提供される３次元地図情報と、インターネット上に投稿された地物に関する情報及びその情報が投稿された位置情報との少なくとも一方に基づいて、前記複数のノードで認識可能な面状のランドマークと、複数のノードに跨がる線状のランドマークと、前記各ノードで認識可能な点状のランドマークを、ランドマークとして抽出する、
こととしてもよい。

前記経路探索部は、
前記線状又は面状のランドマークを道標として連続的に認識しながら出発地から目的地まで前記ノード間を移動可能な経路を探索する、
こととしてもよい。

前記経路探索部は、
前記線状のランドマーク上にある視認性の高い地物を点状のランドマークとして抽出し、
前記点状のランドマークと前記面状のランドマークとを結ぶ経路を新たな線状のネットワークとして抽出する、
こととしてもよい。

前記ランドマーク抽出部は、
前記地理情報システムから提供される３次元地図情報に含まれるランドマークの著名性に関する情報に基づいて、複数のノードに跨がって道標として認識可能なランドマークとして、前記線状のランドマークを抽出する、
こととしてもよい。

前記経路探索部は、
出発地からの所定の条件を満たす地点までの経路については、可視率が高い面状又は線状のランドマークを優先して、経路を探索し、
前記地点から目的地までの経路については、面状又は線状のランドマークのうちの残りのランドマーク及び点状のランドマークを優先して、経路を探索する、
こととしてもよい。

前記経路探索部は、
面状のランドマークとして案内情報を提示したランドマークが、所定の距離以内となった場合に、当該ランドマークを点状のランドマークとして案内情報を提示する、
こととしてもよい。

前記経路探索部は、
前記各ノードで案内情報を知覚可能な提示装置又は前記ランドマークに、案内情報を提示させる情報を生成してその情報を提示する装置に送信する、
こととしてもよい。

この発明の第２の観点に係るナビゲーション方法は、
地理情報システムから提供される３次元地図情報に基づいて、地図上の道路ネットワークにおける複数のノード各々で道標として存在位置を知覚できるランドマークを、前記ノード毎に抽出するランドマーク抽出ステップと、
前記ランドマーク抽出部で抽出されたノード毎のランドマークに基づいて、道標となるランドマークの数及び切り替え頻度が少なくなるように、出発地から目的地まで前記ノード間を移動可能な経路を探索する経路探索ステップと、
を含む。

この発明の第３の観点に係るプログラムは、
コンピュータを、
地理情報システムから提供される３次元地図情報に基づいて、地図上の道路ネットワークにおける複数のノード各々で道標として存在位置を知覚できるランドマークを、前記ノード毎に抽出するランドマーク抽出部、
前記ランドマーク抽出部で抽出されたノード毎のランドマークに基づいて、道標となるランドマークの数及び切り替え頻度が少なくなるように、出発地から目的地まで前記ノード間を移動可能な経路を探索する経路探索部、
して機能させる。

この発明によれば、可視率の高い同一のランドマークを道標として連続的に視認しながら出発地から目的地まで前記ノード間を移動可能な経路で利用者を案内することが可能となる。このため、案内の際に道標となるランドマークの数及び切り替え頻度を少なくすることができるので、画面を見る回数を減らして、利用者の安全性を高めることができる。

この発明の実施の形態１に係るナビゲーションシステムの概略的な構成を示すブロック図である。 コンピュータのハードウエア構成を示すブロック図である。 コンピュータの機能構成を示すブロック図である。 地域をブロックに分割する例を示す図である。 選択されたランドマークの一例を示す図である。 各ノードでのランドマークの選択方法を示す図である。 図７（Ａ）は、ノードから見た風景の一例を示す図であり、図７（Ｂ）はレンダリングされた３次元ＣＧ画像の一例を示す図である。 ランドマークによる経路探索の一例を示す図である。 経路の選択範囲の一例を示す図である。 可視マップ生成工程のフローチャートである。 経路探索工程のフローチャートである。 決定された経路の一例を示す図である。 この発明の実施の形態３に係るナビゲーションシステムで案内される経路の一例を示す図である。 この発明の実施の形態３に係るナビゲーションシステムで案内される経路を具体的に探索するアルゴリズム例を示す図である。 点状と線状と面状のランドマークを示す図である。 面状のランドマークと点状のランドマークから、新しい線状のランドマークを作成する図である。 新しい線状のランドマークを追加した、経路ネットワークを示す図である。 点状と線状と面状のランドマークによる、経路案内の一例を示す図である。 この発明の実施の形態３に係るナビゲーションシステムの経路探索工程のフローチャートである。 この発明の実施の形態４に係るナビゲーションシステムの概略的な構成を示すブロック図である。 図２０のナビゲーションシステムのサーバの機能構成を示すブロック図である。 この発明の実施の形態５に係るナビゲーションシステムのサーバ（経路探索工程）の動作を示すフローチャートである。 この発明の実施の形態６に係るナビゲーションシステムの概略的な構成を示すブロック図である。 図２３のナビゲーションシステムのサーバの機能構成を示すブロック図である。

以下、この発明の実施の形態について図面を参照して詳細に説明する。

実施の形態１．
まず、この発明の実施の形態１について説明する。

図１には、ナビゲーションシステム１００の概略的な構成が示されている。図１に示すように、ナビゲーションシステム１００は、サーバコンピュータ（サーバ）１と、地理情報システム２と、携帯端末３と、を備える。サーバ１と、地理情報システム２、携帯端末３とは、通信ネットワーク４を介して通信可能に接続されている。

サーバ１は、出発地から目的地までの経路を探索する。地理情報システム２は、サーバ１での経路を探索するためのＧＩＳ（Geographic Information System）データを、サーバ１へ提供する。携帯端末３は、利用者によって携帯されたスマートフォン等の通信端末である。サーバ１は、携帯端末３からの求めに応じ、出発地から目的地までの経路を探索する。

図２に示すように、サーバ１は、制御部３１、主記憶部３２、外部記憶部３３、操作部３４、表示部３５及び通信部３６を備える。主記憶部３２、外部記憶部３３、操作部３４、表示部３５及び通信部３６はいずれも内部バス３０を介して制御部３１に接続されている。

制御部３１は、ＣＰＵ（Central Processing Unit）等から構成されている。このＣＰＵが、外部記憶部３３に記憶されているプログラム３９を実行することにより、図１に示すサーバ１の各構成要素が実現される。

主記憶部３２は、ＲＡＭ（Random-Access Memory）等から構成されている。主記憶部３２には、外部記憶部３３に記憶されているプログラム３９がロードされる。この他、主記憶部３２は、制御部３１の作業領域（データの一時記憶領域）として用いられる。

外部記憶部３３は、フラッシュメモリ、ハードディスク、ＤＶＤ−ＲＡＭ（Digital Versatile Disc Random-Access Memory）、ＤＶＤ−ＲＷ（Digital Versatile Disc ReWritable）等の不揮発性メモリから構成される。外部記憶部３３には、制御部３１に実行させるためのプログラム３９があらかじめ記憶されている。また、外部記憶部３３は、制御部３１の指示に従って、このプログラム３９の実行の際に用いられるデータを制御部３１に供給し、制御部３１から供給されたデータを記憶する。

操作部３４は、キーボード及びマウスなどのポインティングデバイス等と、キーボード及びポインティングデバイス等を内部バス３０に接続するインターフェイス装置から構成されている。操作部３４を介して、操作者が操作した内容に関する情報が制御部３１に入力される。

表示部３５は、ＣＲＴ（Cathode Ray Tube）またはＬＣＤ（Liquid Crystal Display）などから構成され、操作者が操作情報を入力する場合は、操作用の画面が表示される。

通信部３６は、シリアルインターフェイスまたはパラレルインターフェイスから構成されている。通信部３６は、通信ネットワーク３を介して地理情報システム２及び携帯端末４と接続する。

図１に示すサーバ１の各種構成要素は、図２に示すプログラム３９が、制御部３１、主記憶部３２、外部記憶部３３、操作部３４、表示部３５及び通信部３６などをハードウエア資源として用いて実行されることによってその機能を発揮する。

なお、携帯端末３も、図２に示すハードウエア構成を含んでおり、プログラムの実行により、携帯端末３の機能が実現される。

図２に示すようなハードウエア構成を有するサーバ１は、その機能構成として、図３に示すように、記憶部１０と、可視マップ生成部１１と、経路探索部１２と、を備える。

ランドマーク抽出部としての可視マップ生成部１１は、地理情報システム２からＧＩＳデータ２０を取得して記憶部１０にＧＩＳデータ１５として記憶する。可視マップ生成部１１は、ＧＩＳデータ１５に基づいて、地図上の道路ネットワークにおける複数のノード、例えば交差点の各々について、その交差点から視認できるランドマークを、可視率を条件としてノード毎に抽出する。

ＧＩＳデータは、地理情報システム２から提供される３次元地図情報である。ＧＩＳデータには、対象となる地域（例えば、ある都市）における建物、道路、地形等の３次元データが含まれる。このＧＩＳデータを用いれば、対象となる地域の任意の地点から視認できる物体のオブジェクトの３次元コンピュータグラフィックス（３ＤＣＧ）画像を描画することができる。なお、描画するオブジェクトには、建物、地形、道路、線路などがある。

また、可視率は、３次元コンピュータグラフィックス（３ＤＣＧ）画像全体におけるランドマークの画素の占有率とすることができる。可視率は、そのノードからのランドマークの見やすさを表している。

可視マップ生成部１１は、ＧＩＳデータ１５に基づいて、対象となる矩形地域の地図を、図４に示すように、複数の領域、例えば、１ｋｍ四方のブロックに分割する。

続いて、可視マップ生成部１１は、各ブロック内に含まれる建物のうち、背の高い順に上位ｎ件の建物を、ランドマークとしてブロック毎に選択する。選択されたランドマークのデータが、記憶部１０に記憶されるランドマークデータ１６である。各ブロックからランドマークを選ぶ理由は、市街地の中心部等に偏ってランドマークが選択されてしまわないようにするためである。ｎは、生成する都市の状態に応じて、適切な数値が設定される。図５では、このようにして選択されたランドマークが強調表示されている。

可視マップ生成部１１は、ブロック毎にｎ個のランドマークを選択した後、選択されたランドマークの中から、可視率の高いランドマークを、ノードとしての交差点毎に抽出し、各ノードから視認できるランドマークを、可視率を条件としてノード毎に記憶する可視率データベース１７を生成する。

可視率データベース１７を生成する際には、可視マップ生成部１１は、ＧＩＳデータ１５に基づいて、全てのノード（交差点）各々から全周を見渡した３ＤＣＧ画像を描画により生成し、その画像に含まれているランドマークを抽出する。図６に示すように、あるノード（交差点）から見えるランドマークが抽出され、見えないランドマークは抽出されない。

より具体的には、可視マップ生成部１１は、決定した各ランドマークに固有の番号を割り振り、各番号に対応する個別の色を用いて３ＤＣＧ画像における全ランドマークの画像をレンダリングする。可視マップ生成部１１は、それ以外の建物、背景を図７（Ａ）及び図７（Ｂ）に示すように、単色でレンダリングする。このレンダリング画像中に含まれる画素値（色）を調べることで、あるノード（交差点）から見えるランドマークの番号を検出できる。可視マップ生成部１１は、レンダリングされたランドマークに基づいて、ランドマークの可視率を求める。さらに、可視マップ生成部１１は、求められた可視率に基づいて、複数のノード各々から視認できるランドマークを、ノード毎に抽出する。このとき、可視率が小さすぎるランドマークは、画面に描画されないようにするようにしてもよい。可視率の計算手法としては、画面の中に占める対象ランドマークの割合を用いることができる。さらに、視点を摂動させそれぞれの可視率を計算し、その最悪値を利用してもよい。

経路探索部１２は、可視率データベース１７に記憶された情報、すなわち抽出されたノード毎のランドマークに基づいて、可視率の高い同一のランドマークを道標として連続的に視認しながら出発地から目的地までノード間を移動可能な経路を探索する。経路探索では、道標として用いられるランドマークの可視率及びノード間でのランドマークの切り替え頻度をコストとして、これを合計するコスト関数が導入される。

コスト関数には、ランドマークの可視性を考慮したものが用いられる。ここで、地点ｉから地点ｊに移動するためのＮ地点の経由地点リストをＴ（ｐ）＝｛ｉ，・・・，Ｔp，・・・，ｊ｝と表現する。経路Ｔ（ｐ）のコスト関数Ｃ（Ｔ（ｐ））は式（１）で示される。

ここで、上記式（１）の右辺第１項は、ある経路を構成する各ノードで選択されたランドマークの可視率の合計である。すなわち、ここでは、出発地から目的地までに通過する複数のノード各々について、道標として選択されたランドマークの可視率をコストとしている。また、右辺第２項は、隣接ノードの正規化項である。ノード間で参照するランドマークの切り替えがあった場合には、Ｒ_e＝１となり、切り替えがなかった場合には、Ｒ_e＝０となる。すなわち、右辺第２項は、ノード間でランドマークの切り替え頻度をコストとし、切り替え頻度が多くなればなるほど値が大きくなる。λは重み係数である。

経路探索部１２は、上記式（１）をコスト関数として、そのコスト関数の値が最小となるように、遺伝的アルゴリズム（ＧＡ）を用いて、出発地から目的地までの最適な経路を探索する。図８には、このような各ノードνを結ぶ経路ｅと、各ノードνでのランドマーク（Ａ、Ｂ、Ｃ、Ｄ、Ｅ）との関係が示されている。図８に示すように、隣接するノードでのランドマークができるだけ連続するように、各ノードで選択されるランドマークは、Ｃ、Ｃ、Ｃ、Ｅ、Ｅとなっている。

実用的な規模の道路ネットワークの情報は膨大である。そこで、経路探索部１２では、出発地と目的地の位置に応じて、経路探索の範囲をあらかじめ絞り込む方法が一般的に用いられている。特に、ＧＡによる経路探索では、経路情報の突然変異による変更を、ある程度の範囲に限定することで、探索効率が上がるという特徴があり、探索範囲の絞込みが有効に働く。そこで、ここでは、図９に示すように、出発地と目的地を結ぶ線分から距離d以内にあるノード（交差点）のみを経路探索に用いる。ここでは，出発地と目的地を結ぶ線分の長さをLength としたとき，ｄ＝Length／４とする。

次に、このナビゲーションシステム１００の動作について説明する。

図１０には、ナビゲーションシステム１００において行われる可視マップ生成工程の処理の流れが示されている。図１０に示すように、まず、可視マップ生成部１１は、地理情報システム２からＧＩＳデータ２０を取得してＧＩＳデータ１５として記憶部１０に記憶する（ステップＳ１）。続いて、可視マップ生成部１１は、ＧＩＳデータ１５に規定される矩形領域を、複数のブロックに分割する（ステップＳ２）。続いて、可視マップ生成部１１は、ブロック毎に、背の高い順に上位ｎ件の建物をランドマークとして選択する（ステップＳ３）。選択されたランドマークの情報は、ランドマークデータ１６として記憶部１０に記憶される。

可視マップ生成部１１は、ＧＩＳデータ１５に含まれる道路ネットワークにおける各ノード（各交差点）での、３次元ＣＧ画像を生成する（ステップＳ４）。さらに、可視マップ生成部１１は、３次元ＣＧ画像において、各ランドマークのレンダリングを行う（ステップＳ５）。可視マップ生成部１１は、レンダリングされた各ランドマークの可視率を算出する（ステップＳ６）。可視マップ生成部１１は、ノード毎にランドマークを関連づけて記憶する可視率データベース１７を生成して記憶部１０に記憶する（ステップＳ７）。ステップＳ７完了後、可視マップ生成工程が終了する。

図１１には、ナビゲーションシステム１００において行われる経路探索工程の処理の流れが示されている。図１１に示すように、まず、経路探索部１２は、携帯端末５のナビゲーションアプリ５０から、出発地、目的地を取得する（ステップＳ１１）。続いて、経路探索部１２は、親世代の経路候補Ｔ（ｐ）を複数選択する（ステップＳ１２）。続いて、経路探索部１２は、現世代の複数の経路候補Ｔ（ｐ）各々のコスト関数を算出する（ステップＳ１３）。続いて、経路探索部１２は、遺伝的アルゴリズム（ＧＡ）により子世代の経路候補Ｔ（ｐ）を複数生成する（ステップＳ１４）。ＧＡでは、経路候補Ｔ（ｐ）を個体として、交叉（組み替え）、突然変異を行って子世代の経路候補Ｔ（ｐ）を生成する処理である。なお、子世代の個体には、親世代で最良であった個体をそのまま残すようにする。

続いて、経路探索部１２は、コスト関数の値が一定範囲内に収束したか否かを判定する（ステップＳ１５）。いわゆる探索の終了判定である。終了判定の判定条件には、世代数が所定数となることであってもよいし、コスト関数の値が閾値を下回ることであってもよい。

コスト関数の値が収束していないと判定された場合（ステップＳ１５；Ｎｏ）、経路探索部１２は、ステップＳ１３に戻り、子世代におけるコスト関数の算出（ステップＳ１３）。子世代の経路候補Ｔ（ｐ）の生成（ステップＳ１４）、コスト関数の収束判定（ステップＳ１５）を繰り返し行う。

コスト関数が収束したと判定された場合（ステップＳ１５；Ｙｅｓ）、経路探索部１２は、最もコスト関数が良好な経路候補Ｔ_pを最終的な経路として決定して記憶部１０に記憶する（ステップＳ１６）。続いて、経路探索部１３は、記憶された経路Ｔ_pを出力し（ステップＳ１７）、処理を終了する。図１２には、このようにして生成された経路の一例が示されている。図１２に示す経路では、出発地から目的地に至るまでに参照するランドマークの数は、３つのみとなる。

以上詳細に説明したように、この実施の形態によれば、可視率の高いランドマークを連続的に見ながら移動できるように最適な経路で出発地から目的地まで案内することが可能となる。このため、案内に用いるランドマークの数及び切り替え頻度を少なくすることができるので、利用者の安全性を高めることができる。

実施の形態２．
次に、この発明の実施の形態２について説明する。

この実施の形態は、コスト関数が、上記実施の形態１と異なる。この実施の形態では、以下のコスト関数が用いられる。

右辺第３項は、距離に応じて増加する項である。Dist（T_p、T_p+1）は、ノードT_pからノードT_p+1までの距離であり、W（ｐ）はその距離の重みである。このように、この実施の形態では、ランドマークだけでなく、経路の距離も考慮して、経路が探索される。すなわち、経路探索部１２は、出発地から目的地までの経路の距離をコスト関数のコストとしてさらに加えて、出発地から目的地までの経路を探索する。

このようにすれば、ランドマークの可視率を考慮しつつ、距離の短い経路を探索することが可能となる。

実施の形態３．
次に、この発明の実施の形態３について説明する。

上記各実施の形態に係るナビゲーションシステム１００は、いわゆる可視率の高いランドマークを目印とする経路を案内した。この実施の形態に係るナビゲーションシステム１００では、ビルのような地図上で広い地域から観測される面状のランドマークだけでなく、線路、通り、高速道路等の線状のランドマークや、コンビニエンスストアやガススタンド、銀行、交番、公園、テーマパーク等の線状のランドマーク上にある視認性の高い地物である点状のランドマークも道標として用いられる。

可視マップ生成部１１は、ＧＩＳデータ１５に基づいて、対象となる領域に含まれる可視率の高いランドマークの他、線状のランドマーク、点状のランドマークを抽出する。線状のランドマーク、点状のランドマークの抽出方法には様々な方法があるが、例えば、線路、通り、高速道路、公園、テーマパークが著名であったり、ツイッターの書き込みの発信場所となっていたりする場合に、そのランドマークを事前にサーバ１内に登録しておき、対象となる地域に、登録された線状、点状のランドマークが存在するか否かを判定することにより行うことができる。すなわち、可視マップ生成部１１は、ＧＩＳデータ１５に含まれるランドマークの著名性の高いものについて、複数のノードに跨がって道標として認識可能なランドマークとして線状又は点状のランドマークを抽出する。例えば、著名な国道、高速道路、有名な街道、商店街、公園、球技場などはこのようなランドマークとなり得る。

可視マップ生成部１１は、抽出した線状、点状のランドマークをランドマークデータ１６に記憶する。可視マップ生成部１１は、ＧＩＳデータ１５に基づいて、地図上の道路ネットワークにおける複数のノードに跨がって道標として認識可能なランドマークを、線状又は面状のランドマークとして、ノード毎に抽出する。経路探索部１２は、可視率の高い面状のランドマークだけでなく、線状又は点状のランドマークを道標として連続的に認識しながら出発地から目的地までノード間を移動可能な経路を探索する。経路探索部１２は、道標とするランドマークの数ができるだけ少なくなるような経路を探索する。

例えば、図１３に示すように、経路上、線状のランドマークとして市電の路線があるときには、市電の路線を案内に用いるランドマークとして選択し、そのランドマーク上にいる間は、そのランドマーク上を移動するようにすれば、複数の隣接するノードで市電の路線を共通のランドマークとすることができる。この結果、コスト関数の値を良好なものとすることができる。

図１４から図１９までを用いて、具体的な、面・線・点状のランドマークを用いた経路探索手法について説明する。まず、図１４に示すように、経路探索部１２は、出発地と目的地の情報に基づき、２地点を含むBounding Boxを生成する。次に、図１５に示すように、経路探索部１２は、Bounding Boxに含まれる点状のランドマーク（四角）・線状のランドマーク（太い実線）・面状のランドマーク（小さな円）を選択する。ここで図中に示される大円（以降、面状のランドマークの可視エリアと呼ぶ）は、面状のランドマークを可視できる範囲を示しており、各小円に対し１つずつある。

次に、図１６を用いて、点状と面状のランドマークから新しい線状のランドマークを決定する方法を説明する。まず、経路探索部１２は、それぞれの面状のランドマークと、その面状のランドマークの可視エリアの範囲内に存在する点状のランドマークとを線で繋ぐ。この時、出発地も点状のランドマークに含まれるとする。この線が新しい線状のランドマークとなる（太い破線）。このとき、新しい線状のランドマークと、既存のランドマークが交わる時は、その交点が、新たな点状のランドマークとなる（図１６では三角で示される）。すなわち、経路探索部１２は、線状のランドマーク（図１６では実線）上にある視認性の高い地物を点状のランドマーク（図１６では、四角）として抽出し、点状のランドマーク（四角）と面状のランドマーク（小さな円）とを結ぶ経路を新たな線状のネットワーク（破線）として抽出する。経路探索部１２は、線上のネットワーク（実線）と、新たな線状のネットワーク（破線）との交点を新たな点状のネットワーク（三角）として抽出する。これを全ての面状のランドマークに対して行う。そして最後に、目的地をこの道路ネットワークに追加する。追加方法としては、目的地の近傍にある道路ネットワークに、新たなノードとして挿入すれば良い。

図１７は、このようにして生成されたランドマークのみによる道路ネットワークを示したものである。このランドマークのみを使用したネットワークによる経路探索を行った結果の例を図１８に示す。このように線状や点状のランドマークを導入することで、多少遠回りでも、少ないランドマークで目的地まで辿り着けるような経路を効率よく求めることができる。さらに、このように線状のランドマークを導入すると、経路探索に用いる道路ネットワークの規模を小さくすることができるというメリットもある。

ここまでの流れをフローチャートにしたものが図１９である。図１９に示すように、サーバ１により、出発地・目的地の指定、すなわちスタート・ゴール指定（ステップＳ２１、図１４参照）、Bounding Box生成（ステップＳ２２、図１４参照）、点・線・面状のランドマークの決定（ステップＳ２３、図１５参照）、道路ネットワーク生成（ステップＳ２４、図１６、図１７参照）、経路探索（ステップＳ２５、図１８参照）がこの順で行われる。道路ネットワーク生成（ステップＳ２４）では、面状のランドマークと点状のランドマークを結ぶ経路（破線）の生成、生成した経路と線状のランドマークが交わる新しい点（ノード（三角）の生成）が行われる（図１８参照）。

実施の形態４．
次に、この発明の実施の形態４について説明する。一般的に、ランドマークは、視覚的に顕著なものを指す。このため、上記各実施の形態では、主として、ノード毎のランドマークの可視率を画像処理などで取得した。一方で、ランドマークとなり得るような顕著性の高い地物は、Ｗｅｂサイト、ソーシャルネットワークサービス（ＳＮＳ）のツイッター、フェイスブック、インスタグラムなどのようなインターネット上の投稿システムにおいて頻繁に登場し、その出現頻度は高い傾向にある。そこで、本実施の形態では、ツイッターやフェイスブック、インスタグラムなどに投稿された情報を解析し、その出現頻度が高い傾向にある地物を視認性のみでは推し量れない新たなランドマークとして利用する。

例えば、「雰囲気の良いカフェ」という投稿（書き込み）があれば、そのカフェを、点状のランドマークとして利用する。また、「爽やかな並木道」という投稿があれば、線状のランドマークとして利用する。「ビルの谷間にたまに見える変わった色のビル」という投稿があれば、面状のランドマークとして利用する。

図２０には、本実施の形態に係るナビゲーションシステム１００の概略的な構成が示されている。図２０に示すように、このナビゲーションシステム１００は、多くの携帯端末３から得られる情報に基づいて成り立っている。

また、通信ネットワーク４には、投稿システム５が接続されている。投稿システム５は、Ｗｅｂサイト、ツイッターやフェイスブック等の位置基盤ＳＮＳにおいて携帯端末３等から投稿される投稿情報（投稿データ）を管理するサーバコンピュータである。

投稿システム５は、携帯端末３等から、通信ネットワーク４を介して、投稿データと、その投稿データが投稿されたときの携帯端末３のＧＰＳ（Global Positioning System）データ（位置情報）とを受信する。投稿システム５は、受信した投稿データと、ＧＰＳデータとを対応づけて記憶する。

図２１には、本実施の形態に係るナビゲーションシステム１００を構成するサーバ１の機能構成が示されている。サーバ１は、その機能構成として、記憶部１０と、可視マップ生成部１１と、経路探索部１２とを備える点は、上記実施の形態１と同じである。

可視マップ生成部１１は、地理情報システム２からＧＩＳデータを取得して記憶部１０に記憶する他、投稿システム５から受信した投稿データ＋ＧＰＳデータ２１を取得して投稿データ（位置情報）１９として記憶する。投稿データには、ＧＰＳなどの位置情報が付加されているので、その投稿データがどこで投稿されたのかを容易に検出することができる。

可視マップ生成部１１は、地理情報システム２から提供される３次元地図情報に基づいて、複数のノード各々からの３次元ＣＧ画像データを生成する。さらに、可視マップ生成部１１は、生成された３次元ＣＧ画像データにおける面状のランドマークの画像をレンダリングし、レンダリングされたランドマークに基づいて、面状のランドマークの可視率を求め、求められた可視率に基づいて、複数のノード各々から視認できる面状のランドマークを、ノード毎に抽出する。

しかしながら、面状のランドマークについては、街路樹、道案内、病院や店の看板など、デジタル地図にはない地物に視界が遮られ、シミュレーション、ＣＡＤ（Computer Aided Design）モデル、画像処理による可視率の計算が必ずしも正しくないときもある。そこで、このような場合には、可視マップ生成部１１は、ツイッターやフェイスブック、インスタグラム等のインターネットに投稿された投稿データ（位置情報）１９を使用する。具体的には、可視マップ生成部１１は、投稿データと、そのデータが投稿された位置情報とに基づいて、ランドマークの存在位置を知覚できる範囲と、ランドマークが出現する投稿データの出現頻度を、ランドマークの可視率に相当する値として求める。ランドマークの存在位置を知覚できる範囲とは、ランドマークを直接視認することができる範囲のみならず、”ランドマークへはここを右に曲がって５００ｍ”などと表示された看板等が見える範囲で、ランドマークの存在位置がわかる範囲も含まれる。

まず、可視マップ生成部１１は、投稿システム５から投稿データ及び投稿された位置を収集して、投稿データ（位置情報）１９として記憶部１０に記憶する。さらに、可視マップ生成部１１は、記憶された投稿データ（位置情報）１９を解析し、各位置における投稿データに対するランドマークの出現頻度を算出する。可視マップ生成部１１は、ランドマークの出現頻度が所定値以上となる位置を、ランドマークの存在位置を知覚できる範囲とし、各ノードにおけるランドマークの選択に用いる。さらに、可視マップ生成部１１は、各位置におけるランドマークの出現頻度を、ランドマークに対する可視率に相当する値（重要度）として算出する。経路探索部１２は、このランドマークの出現頻度を経路探索に用いる。

なお、可視マップ生成部１１は、投稿データにランドマークの固有名詞が出現していなくても、関連するテキストが含まれている場合には、その投稿データにランドマークが出現しているものとして、ランドマークの重要度を算出するようにしてもよい。例えば、一定の範囲内で「スカイツリー」と共起している「行列」、「観光名所」、「高い」といった単語が投稿データに含まれる場合には、可視マップ生成部１１は、その投稿データを「スカイツリー」を含む投稿データとして扱って、「スカイツリー」の影響度を算出してもよい。

なお、可視率や可視範囲は、その他にも、ストリートビューの画像を解析することにより算出することができる。ストリートビューの画像は、実際にその場所から撮像された場所であるため、ランドマークの見え方は正確である。この際、ストリートビュー画像に含まれる建物がどの地図上のいずれの建物であるかを認識したり、その建物の可視率や可視範囲を算出したりするために、例えば、深層学習（ディープラーニング）のような画像認識技術を用いるようにしてもよい。

なお、ランドマークそのものが見えなくても、地物に関する情報（例えば、”〜は、ここを右に”などの看板や標識など）により、その地物の存在する位置や方向が分かるものであれば、その地物もランドマークとして利用可能である。また、これを援用すれば、ランドマークによっては、ある地域全体をカバーする面のランドマークとしても利用できる（これは、言い換えると、ある地域における方角を表すことと同値とも理解できる）。例えば、鹿児島においては、桜島の方向と言えば、東向きと同等の意味になるため、桜島をそのような方向を表す面のランドマークとして利用できる。また、京都であれば、比叡山の方とか、嵐山の方角、と言うだけでそれぞれ北東や南西を指し、神戸であれば、山手とか海岸方向と言うことで、それぞれ南北を指すことができ、方向音痴の人でも直感的に正しい方角に向かって進むこととが出来る。都心では、同様のアプローチにより、駅で降りて、どちらの方向に進むべきかについて、この「知覚できる方向」としてこの面のランドマークを使用できる（例えば、渋谷駅からならば、新宿方面か、六本木方面か、恵比寿方面か・・などのように）。

実施の形態５．
次に、この発明の実施の形態５について説明する。非常に高層で可視率の高い範囲が広い建物（面状のランドマーク）であっても、周辺がある程度高い建物で囲まれている場所からは見えない場合がある。一方で、広範囲からは見ることができないあまり背の高くない建物でも、その周辺数十ｍから数百ｍ以内に限れば、非常に視認性の高い地物もある。本実施の形態では、このようなランドマークの特性を有効活用して経路を案内するナビゲーションシステムについて説明する。

上記各実施の形態のように、可視率のしきい値処理でランドマークを選択した場合には、前者は面状のランドマークとして選ばれるが、後者は選ばれないことになる。そこで、本実施の形態５に係るナビゲーションシステム１００は、経路探索を階層化し、利用するランドマークを前者から後者に切り替える。

本実施の形態に係るナビゲーションシステム１００の構成は、図２０、図２１に示す上記実施の形態４に係るナビゲーションシステム１００の構成と同じである。

ただし、本実施の形態に係るナビゲーションシステム１００では、サーバ１の可視マップ生成部１１は、図１０に示す可視マップ生成工程を、広い領域（スタート地点とゴール地点とを含むBounding Box）と、狭い領域とに分けて複数回行う。このようにすれば、広い領域で選択されなかった背の低いランドマークを狭い領域において抽出することが可能となる。

続いて、経路探索部１２の動作について説明する。

図２２に示すように、この経路探索部１２は、スタート・ゴール指定（ステップＳ２１）〜道路ネットワークの形成（ステップＳ２４）までは、上記実施の形態３と同じように動作する。

続いて、経路探索部１２は、概略経路の探索を行う（ステップＳ２５）。この探索では、主に可視率が高く広範囲で視認可能な面状のランドマークや線状のランドマークが優先的に用いられる。この概略経路探索では、背の低い面状、線状のランドマーク（出発地近傍では可視率が高くないランドマーク）は実際には見えないことが良くあるため、このようなランドマークは、抑制的に使用される。

その後、経路探索部１２は、探索された概略経路の案内を行う（ステップＳ２６）。

経路探索部１２は、携帯端末３から送信された位置情報に基づいて、携帯端末３が目的地までの所定の距離の範囲内に達するまで待つ（ステップＳ２７；Ｎｏ）。目的地までの所定の距離の範囲内まで達すると（ステップＳ２７；Ｙｅｓ）、経路探索部１２は、その地点から目的地までの詳細経路の探索を行う（ステップＳ２８）。この探索では、主に可視率の低い面状のランドマークが優先的に用いられる。この概略経路探索では、背の高い面状のランドマークでは詳細な道案内の道標には向いていないため、抑制的に使用される。

その後、経路探索部１２は、探索された詳細経路で案内を行う（ステップＳ２９）。

本実施の形態では、現在地から目的地までの距離で、経路探索に用いるランドマークを切り替えたが、経路案内に用いている面状のランドマークとの間の距離が所定の距離以内となった場合に、そのランドマークを、視認できる範囲の狭い面状、点状又は線状のランドマークに切り替えて案内するようにしてもよい。このようにすれば、例えば、最初は、遠くから見える東京タワーを面状のランドマークとして経路案内に用い、東京タワーのすぐ近くまで来ると「東京タワーの足元で右折する」といったように、東京タワーを点状のランドマークとして経路案内に用いることも可能である。すなわち、経路探索部１２は、面状のランドマークとして案内情報を提示したランドマークが、所定の距離以内となった場合に、当該ランドマークを点状のランドマークとして案内情報を提示することができる。

実施の形態６．
次に、この発明の実施の形態６について図２３を用いて説明する。本実施の形態では、国道を線状のランドマークとしてその国道沿いに歩いており、途中で、遠方にある高層ビルを目指して歩くといったように、ランドマークをスイッチする場合に有用なナビゲーションシステムについて説明する。

このようなスイッチの際に、より良く分かりやすい目印となるような点状のランドマーク（例えば郵便局など）が、線状のランドマークに接して存在していれば、それを使用することができる。しかし、そのようなランドマークが無い場合、ユーザは非常に遠回りさせられたり、あるいはそのような経路が経路探索結果として現れたりしないおそれがある。そこで、本実施の形態では、ランドマークを切り替える地点にデジタルサイネージ４０（図２３参照）を配置し、デジタルサイネージ４０に特別な案内情報（案内パターン）を能動的に表示させる。

図２４に示すように、携帯端末３のナビゲーションアプリ５０は、その経路案内を利用することを図２３のサーバ１の経路探索部１２に知らせておく。経路探索部１２は、定点カメラ、ＲＦＩＤ（Radio Frequency IDentifier）、ＷｉＦｉ（Wireless Fidelity）による位置検出システムなどを用いて図２３の携帯端末３の位置情報を取得し、携帯端末３がそのデジタルサイネージ４０の位置に来た時に合わせて、デジタルサイネージ４０に特別な案内パターンを表示させる。案内パターンとしては様々なものがある。例えば、案内パターンは、目的地の画像であってもよいし、あるいは単に経路が正しいことを示す記号（○）、間違っていることを示す記号（×）であってもよい。進行方向を示す矢印を表示すれば、ユーザが進行方向を識別することができる。また、案内パターンとして、次のランドマークの情報を表示するようにしてもよい。また、スピーカを有する装置を各ノードに用意して、音声を用いて案内するようにしてもよい。

また、案内パターンの表示としては、特定の人にのみ意味のある記号を提示するようにしてもよい。例えば、ある一定間隔で次々とパターンを切り替えて表示することで、複数の人に複数の情報をほぼ同時に提示することも可能である。

このような案内パターンを見れば、ユーザは自分の位置を把握することができるうえ、目的地までの経路をその表示で確認することができる。この結果、ユーザが携帯端末３の画面を確認する必要がなくなるので、ユーザの安全性を高めることができる。

また、デジタルサイネージ４０が設置されていない場所では、プロジェクションマッピングによって、案内パターンを表示するようにしてもよい。また、音声等でユーザに知らせるようにしてもよい。

さらに、このような能動的な案内パターンの表示は、面状のランドマーク等も用いることが可能である。面状のランドマークを照明で明るく照らすだけでも、他の構造物よりも目立つようになるため、ランドマークとして好適となる。特に、夜間などはこのような表示はランドマークの視認性を上げることにも役立つので、本実施の形態に係るナビゲーションシステム１００の利用範囲を大きく拡げることができる。

加えて、近年注目されている、天空に向けてレーザ光を投影するシステムであれば、新たな面状のランドマークを構築することもできる。ここで、イベントごと、あるいは時間ごとに異なる案内パターンをレーザ光で天空に投影すれば、その案内パターンを見た人の流れをコントロールすることも可能となる。例えば、ある時間にサッカーの試合があり、最寄り駅からスタジアムに多くの人が向かう時は、混雑を解消するように人々の経路を分散するような最適な案内パターンを投影するようにしてもよい。また、別の時間にコンサートがあり、同じ駅が最寄り駅の場合、コンサートホールに向かう別な経路を案内する案内パターンを投影するようにしてもよい。

また、デジタルサイネージ４０が設置されていない場所では、人や車といった移動物体を案内パターンの表示対象とすることも考えられる。

このように、ランドマークは、能動的なものであってもよい。ただし、実際の運用では、経路案内時に、これら能動的なランドマークがアクティブであるか否か、どこに位置しているか、といった情報を表示する装置から受信するなどして、サーバ１が把握しておく必要がある。

以上のように、上記各実施の形態に係るナビゲーションシステムによれば、面状、線状、点状のランドマーク等、ランドマークとなり得るあらゆるものを用いて、案内を行う。線状、点状のランドマークを使用することによって、ユーザの状況に応じたより正確で安全性の高い経路案内が可能となる。また、面状、線状、点状のランドマークには、視認し易い幾何的なものに限らず、人々の記憶に残りやすい意味的なランドマーク（話題になっているカフェや混雑している店、渋滞している道路、寺社などのパワースポット）やその看板なども含まれている。このような意味的なランドマークは、ツイッター等の位置基盤ＳＮＳ等に投稿された投稿データから取得可能である。

また、上記実施の形態に係るナビゲーションシステムによれば、例えば、ユーザが目的地にどの程度近づいているかに応じて、経路案内を階層的に行う。これにより、ユーザのそのときの状況に応じて視認し易いランドマークを用いた案内が可能となるので、より正確で安全性の高い経路案内が可能となる。

また、上記実施の形態に係るナビゲーションシステムによれば、ユーザの経路上にあるデジタルサイネージ、ランドマーク等その他のものに、ユーザを案内する案内情報を提示させる。これにより、ユーザが経路等を再確認することができるので、ユーザの状況に応じたより正確で安全性の高い経路案内が可能となる。

なお、上記各実施の形態では、サーバ１でランドマーク抽出部（可視マップ生成部１１）及び経路探索部の機能を実現したが、これには限られず、携帯端末３でランドマーク抽出部及び経路探索部の機能を実現するようにしてもよい。また、携帯端末３は、ゲーム端末であってもよいし、モバイルコンピュータやパーソナルコンピュータであってもよい。また、カーナビゲーション装置等の専用のナビゲーション装置であってもよい。また、町中に設置された端末などであってもよい。

また、ノードとしては、交差点である必要はない。経路の途中の地点であればよい。

また、上記各実施の形態では、ＧＩＳサービスを利用するシステムとしたが、本発明はこれには限られない。例えば、Ｇｏｏｇｌｅ（登録商標） ＭａｐｓのＡＰＩを利用するようにしてもよい。

このように、本発明により、ユーザが経路や自分位置をなるべく確認しないですむようになり、人が記憶しやすく視認性の高いランドマークを用いたナビゲーションが可能となった。

その他、サーバ１のハードウエア構成やソフトウエア構成は一例であり、任意に変更及び修正が可能である。

制御部３１、主記憶部３２、外部記憶部３３、操作部３４、表示部３５及び通信部３６、内部バス３０などから構成されるサーバ１の処理を行う中心となる部分は、専用のシステムによらず、通常のコンピュータシステムを用いて実現可能である。例えば、前記の動作を実行するためのコンピュータプログラムを、コンピュータが読み取り可能な記録媒体（フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等）に格納して配布し、当該コンピュータプログラムをコンピュータにインストールすることにより、前記の処理を実行するサーバ１を構成してもよい。また、インターネット等の通信ネットワーク上のサーバ装置が有する記憶装置に当該コンピュータプログラムを格納しておき、通常のコンピュータシステムがダウンロード等することでサーバ１を構成してもよい。

サーバ１の機能を、ＯＳ（オペレーティングシステム）とアプリケーションプログラムの分担、またはＯＳとアプリケーションプログラムとの協働により実現する場合などには、アプリケーションプログラム部分のみを記録媒体や記憶装置に格納してもよい。

搬送波にコンピュータプログラムを重畳し、通信ネットワークを介して配信することも可能である。たとえば、通信ネットワーク上の掲示板（BBS, Bulletin Board System）にコンピュータプログラムを掲示し、ネットワークを介してコンピュータプログラムを配信してもよい。そして、このコンピュータプログラムを起動し、ＯＳの制御下で、他のアプリケーションプログラムと同様に実行することにより、前記の処理を実行できるように構成してもよい。

この発明は、この発明の広義の精神と範囲を逸脱することなく、様々な実施の形態及び変形が可能とされるものである。また、上述した実施の形態は、この発明を説明するためのものであり、この発明の範囲を限定するものではない。すなわち、この発明の範囲は、実施の形態ではなく、特許請求の範囲によって示される。そして、特許請求の範囲内及びそれと同等の発明の意義の範囲内で施される様々な変形が、この発明の範囲内とみなされる。

１ サーバコンピュータ（サーバ）、２ 地理情報システム、３ 携帯端末、４ 通信ネットワーク、５ 投稿システム、１０ 記憶部、１１ 可視マップ生成部、１２ 経路探索部、１５ ＧＩＳデータ、１６ ランドマークデータ、１７ 可視率データベース、１９ 投稿データ（位置情報）、２０ ＧＩＳデータ、２１ 投稿データ＋ＧＰＳデータ、３０ 内部バス、３１ 制御部、３２ 主記憶部、３３ 外部記憶部、３４ 操作部、３５ 表示部、３６ 通信部、３９ プログラム、４０ デジタルサイネージ、５０ ナビゲーションアプリ、１００ ナビゲーションシステム。

Claims (16)

1. 地理情報システムから提供される３次元地図情報に基づいて、地図上の道路ネットワークにおける複数のノード各々で道標として存在位置を知覚できるランドマークを、前記ノード毎に抽出するランドマーク抽出部と、
   前記ランドマーク抽出部で抽出されたノード毎のランドマークに基づいて、道標となるランドマークの数及び切り替え頻度が少なくなるように、出発地から目的地まで前記ノード間を移動可能な経路を探索する経路探索部と、
   を備えるナビゲーションシステム。
2. 前記ランドマーク抽出部は、
   前記地図を複数の領域に分割し、
   複数のランドマークを背の高い順に前記領域毎に選択し、
   選択されたランドマークの中から、前記ノード毎に可視率が高い順にランドマークを抽出する、
   請求項１に記載のナビゲーションシステム。
3. 前記ランドマーク抽出部は、
   前記地理情報システムから提供される３次元地図情報に基づいて、複数のノード各々からの３次元コンピュータグラフィック画像データを生成し、
   生成された３次元コンピュータグラフィック画像データにおける前記ランドマークの画像をレンダリングし、
   レンダリングされた前記ランドマークに基づいて、前記ランドマークの可視率を求め、
   求められた可視率に基づいて、前記複数のノード各々から視認できるランドマークを、前記ノード毎に抽出する、
   請求項２に記載のナビゲーションシステム。
4. 前記ランドマーク抽出部は、
   インターネット上に投稿されたランドマークに関する情報と、その情報が投稿された位置情報とに基づいて、前記ランドマークの存在位置を知覚できる範囲を求め、前記ランドマークの可視率に相当する値を決定する、
   請求項１に記載のナビゲーションシステム。
5. 前記経路探索部は、
   前記出発地から前記目的地までに通過する複数のノード各々について、道標として選択されたランドマークの可視率と、
   隣接するノード間での道標とするランドマークの切り替え頻度と、
   をコストとするコスト関数の値が最小となるように、
   前記出発地から前記目的地までの経路を探索する、
   請求項２から４のいずれか一項に記載のナビゲーションシステム。
6. 前記経路探索部は、
   前記出発地から前記目的地までの経路の距離を前記コスト関数のコストとしてさらに加えて、前記出発地から前記目的地までの経路を探索する、
   請求項５に記載のナビゲーションシステム。
7. 前記経路探索部は、
   最適化アルゴリズムを用いて、前記出発地から前記目的地までの経路を探索する、
   請求項５又は６に記載のナビゲーションシステム。
8. 前記ランドマーク抽出部は、
   地理情報システムから提供される３次元地図情報と、インターネット上に投稿された地物に関する情報及びその情報が投稿された位置情報との少なくとも一方に基づいて、前記複数のノードで認識可能な面状のランドマークと、複数のノードに跨がる線状のランドマークと、前記各ノードで認識可能な点状のランドマークを、ランドマークとして抽出する、
   請求項１から７のいずれか一項に記載のナビゲーションシステム。
9. 前記経路探索部は、
   前記線状又は面状のランドマークを道標として連続的に認識しながら出発地から目的地まで前記ノード間を移動可能な経路を探索する、
   請求項８に記載のナビゲーションシステム。
10. 前記経路探索部は、
    前記線状のランドマーク上にある視認性の高い地物を点状のランドマークとして抽出し、
    前記点状のランドマークと前記面状のランドマークとを結ぶ経路を新たな線状のネットワークとして抽出する、
    請求項９に記載のナビゲーションシステム。
11. 前記ランドマーク抽出部は、
    前記地理情報システムから提供される３次元地図情報に含まれるランドマークの著名性に関する情報に基づいて、複数のノードに跨がって道標として認識可能なランドマークとして、前記線状のランドマークを抽出する、
    請求項９又は１０に記載のナビゲーションシステム。
12. 前記経路探索部は、
    出発地からの所定の条件を満たす地点までの経路については、可視率が高い面状又は線状のランドマークを優先して、経路を探索し、
    前記地点から目的地までの経路については、面状又は線状のランドマークのうちの残りのランドマーク及び点状のランドマークを優先して、経路を探索する、
    請求項８に記載のナビゲーションシステム。
13. 前記経路探索部は、
    面状のランドマークとして案内情報を提示したランドマークが、所定の距離以内となった場合に、当該ランドマークを点状のランドマークとして案内情報を提示する、
    請求項８に記載のナビゲーションシステム。
14. 前記経路探索部は、
    前記各ノードで案内情報を知覚可能な提示装置又は前記ランドマークに、案内情報を提示させる情報を生成してその情報を提示する装置に送信する、
    請求項１から１３のいずれか一項に記載のナビゲーションシステム。
15. 地理情報システムから提供される３次元地図情報に基づいて、地図上の道路ネットワークにおける複数のノード各々で道標として存在位置を知覚できるランドマークを、前記ノード毎に抽出するランドマーク抽出ステップと、
    前記ランドマーク抽出部で抽出されたノード毎のランドマークに基づいて、道標となるランドマークの数及び切り替え頻度が少なくなるように、出発地から目的地まで前記ノード間を移動可能な経路を探索する経路探索ステップと、
    を含むナビゲーション方法。
16. コンピュータを、
    地理情報システムから提供される３次元地図情報に基づいて、地図上の道路ネットワークにおける複数のノード各々で道標として存在位置を知覚できるランドマークを、前記ノード毎に抽出するランドマーク抽出部、
    前記ランドマーク抽出部で抽出されたノード毎のランドマークに基づいて、道標となるランドマークの数及び切り替え頻度が少なくなるように、出発地から目的地まで前記ノード間を移動可能な経路を探索する経路探索部、
    して機能させるプログラム。

Images