(57)【特許請求の範囲】
【請求項１】
地物の位置および高さ情報を記録した地図データベースと、
４つ以上の前記地物について、ユーザによって視認された相互の相対的な位置関係を入力する位置関係入力部と、
前記地図データベースを参照し、前記４つ以上の地物のうち２つの地物を処理対象の地物として選択する選択部と、
前記２つの地物を通る境界線を画定するとともに、前記ユーザによって入力された前記２つの地物における左右関係または前後関係を表わす情報から前記境界線によって隔てられている何れか一方の領域を前記ユーザが存在する領域であると推定しつつ前記ユーザの位置が存在し得る領域を決定していき、３つ以上の前記境界線によって囲まれた領域を前記ユーザの位置が存在する領域として推定する境界画定部と
を備える現在位置推定装置であって、
前記選択部は、前記境界画定部において最初の前記境界線が画定される場合には前記４つ以上の地物の中から高さの低い２つの地物を前記処理対象の地物として選択し、２つ目以降の前記境界線が画定される場合には前記境界線の何れかに交差する境界線が画定されるように前記４つ以上の地物から２つの地物を選択する
ことを特徴とする現在位置推定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザの現在位置を推定するための技術に関する。
【背景技術】
【０００２】
車両や歩行者を対象とするナビゲーションシステムが普及してきている。これらのナビゲーションシステムは、ユーザの現在位置を基準として目的地に至る経路を探索したり、探索された経路の案内を行ったりする。ユーザの現在位置は、ＧＰＳ（Global Positioning System）を用いて検出されるのが通常である。
【０００３】
ＧＰＳによる現在位置の検出は、人工衛星からの電波を受信可能な状況下でしか利用できないため、完全なものとは言えない。ナビゲーションシステムの実用性を向上するためには、電波が受信できない環境にある場合や、ユーザが所持する端末にＧＰＳが搭載されていない場合などでも現在位置を特定可能とすることが望まれる。かかる要望に対し、特許文献１は、ユーザに対して正面に何が見えるか、左に何が見えるかなどの質問を発し、その回答に基づいて現在位置を推定する技術を開示している。特許文献２も同様に、「左側にレストランが見えますか」などの質問をユーザに発することにより、現在位置を推定する技術を開示している。
【０００４】
【特許文献１】特開平９−３１９９９１号公報
【特許文献２】特開２００４−３４０６８９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来技術では、歩行者を基準として正面、左に見える建物を回答させる方法を採っている。しかし、現在位置が不明な場合には、歩行者は四方八方を見回し、頻繁に姿勢を変えるのが通常である。従来技術では、歩行者が複数の質問に回答する間に姿勢を変えてしまうと、「正面」、「左」等の方向の基準が変動してしまい、十分な精度で現在位置を推定することができなくなるという課題があった。
【０００６】
また、従来技術のように視認可否を質問する方法では、ユーザが特定しやすい建物、例えば、大型ビルなどのランドマークを対象とすることにより、ユーザの誤解を低減することができる点で好ましい。しかし、このようなランドマークは、遠方からも視認可能であるのが通常であるから、ランドマークに対する視認可否の回答を得たとしても、ユーザの現在位置を精度良く推定することはできない。従来技術では、現在位置の精度を十分に確保しうる質問対象を選択するのが困難であるという課題があった。
【０００７】
上述のランドマークについての課題から明らかな通り、従来技術では、現在位置を精度良く特定するためには、最終的にはユーザの付近にある建物を質問の対象とする必要がある。従って、ユーザが誤解なく特定できる特徴的な建物があったとしても、ユーザから一定範囲より遠方にある場合には、このような建物を現在位置の特定に活用することはできない。この結果、あまり特徴のない建物を現在位置の推定に使用せざるを得ないこととなり、ユーザの誤解等によって現在位置の特定精度が低下するおそれがあった。
【０００８】
このように従来技術における現在位置の推定には、更に実用性向上の余地が残されていた。現在位置の推定は、ナビゲーションシステムに特有の技術ではなく、例えば、ユーザの現在位置に応じてグルメ情報、観光情報、ショッピング情報などを提供するサービスを実現する際にも要求される技術である。本発明は、このように多様な場面で要求される現在位置の推定技術について、より実用性を向上することを目的とする。
【課題を解決するための手段】
【０００９】
ユーザの現在位置を推定する現在位置推定装置としての本発明の構成について説明する。本発明の現在位置推定装置は、複数の地物相互の相対的な位置関係についてユーザが視認した結果を入力する。入力するのは、ユーザから見て正面、左というようなユーザを基準とした位置関係ではなく、複数の地物相互の相対的な位置関係である。例えば、「３つの地物が右から、地物１，地物２，地物３の順に見える」とか、「地物Ａと地物Ｂは前後に重なって見える」とかいう相対的な位置関係が該当する。
【００１０】
現在位置推定装置は、各地物の位置を記録した地図データベースを参照して、上述の複数の地物を入力された相対的な位置関係で視認可能な範囲を特定して、ユーザの現在位置を推定する。例えば、「地物Ａと地物Ｂは前後に重なって見える」という位置関係が入力された場合、このような見え方をする場所は比較的限定されるため、ユーザの現在位置を絞り込むことが可能なのである。本発明では、現在位置の推定に、地物相互の位置関係を用いるため、ユーザが姿勢を変えたとしても支障なく現在位置の推定を行うことができる利点がある。
【００１１】
相対的な位置関係を入力する対象となる地物は、ユーザが決定してもよいし、現在位置推定装置が決定してもよい。前者の方法では、ユーザは、「地物Ａと地物Ｂは前後に重なって見える」というようにそれぞれの地物を名称等で指定した上で相対的な位置関係を入力することになる。この方法は、大都会の中心部など、多くの地物が存在し、ユーザは、看板等によって各地物の名称を容易に知ることができる場合に適している。ただし、この方法では、現在位置推定装置がユーザによって指定された地物を、地図データベースから一義的に特定できることが必要となる。
【００１２】
後者の方法では、現在位置推定装置は、ユーザが現地でそれぞれの地物を特定し得る情報を情報提示する。提示される情報としては、例えば、地物の画像、色、形状、高さなど外観に関する特徴や、地物の名称や、ホテル、デパートなど地物の種別等が含まれる。ユーザが提示された情報に基づいて現地で地物を確認し、相対的な位置関係を入力すると、現在位置推定装置は、これに基づいて現在位置を推定する。この方法では、相対的な位置関係の入力対象となる地物は現在位置推定装置にとって既知であるため、位置関係が入力された後の処理を容易かつ正確に行うことができる利点がある。
【００１３】
相対的な位置関係は種々の表現形式で特定可能であるが、一例として、ユーザを基準として見た場合の複数の地物相互の前後関係または左右関係で特定することが好ましい。地物相互の位置関係が斜めであっても、いずれか一方の地物が他方よりも手前に見えるとか、左または右に見えるとかいう方法での特定は比較的容易かつ正確に行うことができる。従って、このような方法で相対的な位置関係を特定することにより、ユーザにとって、現在位置推定装置を利用しやすくできる。また、位置関係の特定が正確になるため、現在位置の推定精度を向上させることができる。
【００１４】
本発明では、２つの地物を用いるだけでも、現在位置の範囲をある程度絞り込むことは可能であるが、更に推定精度を向上させるためには、一直線上にない３つ以上の地物を用いることが好ましい。
【００１５】
先に説明した通り、現在位置推定装置は３以上の地物を利用することができる。この時、これらの全地物を一度に処理する方法を採ることも可能ではあるが、処理の定型化、簡素化という観点から、複数の地物のうち処理対象となる２つの地物を選択し、選択された地物同士の相対的な位置関係に基づいて、ユーザの現在位置が存在し得る領域（以下、「存在領域」という。）の境界線を画定するという処理を、処理対象となる地物を変えながら繰り返し実行することで、存在領域を絞り込む処理を行うことが好ましい。
【００１６】
処理に利用可能な地物の数が増えるにつれて、処理対象となる２つの地物の組み合わせが多大となる。従って、存在領域の境界の画定に有用な組み合わせを選択的に実行することにより、処理時間を短縮し、効率的に存在領域を求めることが可能となる。この場合、対象とすべき地物の選択は、必ずしも理論的に最適な方法が存在する訳ではないが、いくつかの好適な選択方法が存在する。
【００１７】
第１の選択方法として、４つ以上の地物を用いる場合において、既に画定された境界が存在するときには、画定された境界と交差する境界を画定可能な位置関係にある地物を優先的に選択することが好ましい。例えば、既画定の境界を挟む位置関係にある２つの地物を選択する態様や、既画定の境界上にある地物と境界上にない地物とを選択する態様がこれに該当する。この方法で地物を選択した場合、選択された地物によって特定される新たな境界は、既に画定された境界に交差することになる。つまり、新たな境界は、既に画定された存在領域を分断する形となるため、存在領域を効率的に絞り込むことが可能となる。
【００１８】
第２の選択方法として、４つ以上の地物を用いる場合において、既に画定された境界が存在するときには、現在位置が存在し得る領域内に存在する２つの地物を優先的に用いることが好ましい。この方法で選択された地物によって画定される境界は、既に画定された境界に交差することになる。つまり、新たな境界は、既に画定された存在領域を分断する形となるため、存在領域を効率的に絞り込むことが可能となる。
【００１９】
第３の選択方法として、３つ以上の地物を用いる場合においては、高さの低い地物を優先的に用いることが好ましい。一般に高さの低い地物は、遠方から視認しづらいことを考えると、低い地物ほどユーザの現在位置に近いと考えられる。従って、高さの低い地物を優先的に使用することにより、現在位置の付近に存在領域の境界を画定することができ、存在領域の精度を向上させることができる。
【００２０】
上述の３つの選択方法は、いずれか一つのみを採用してもよいし、適宜、組み合わせて採用してもよい。複数の選択方法を採用する場合の優先順位は任意に設定可能である。また、上述の３つの選択方法と異なる選択方法を加味することも可能である。
【００２１】
本発明では、存在領域を画定するための上述の処理に先立って、ユーザの現在位置を概略把握するための前処理を行うことが好ましい。このための前処理としては、例えば、次の方法を採ることができる。まず、現在位置推定装置は、地物の特定に用い得る属性を、ユーザの操作に応じて入力する。属性の入力対象となる地物は、ユーザが視認できる範囲で任意に選択した地物である。属性としては、例えば、地物の名称、種別、色や高さや模様などの外観に関する情報等が挙げられる。地図データベースには、各地物についてこれらの属性が対応づけて記憶されている。現在位置推定装置は、この地図データベースを参照して属性に対応する地物を特定する。この場合、入力された属性に完全に一致するもののみを特定するようにしてもよいし、一定範囲で入力された属性との不一致を許容して地物を特定するようにしてもよい。後者の態様では、入力された項目のうち、所定数までは不一致であっても許容するという扱いをしてもよいし、各項目に対し許容誤差を認める扱いをしてもよい。
【００２２】
この地物が特定されると、地物を視認可能な範囲は概ね特定可能であるから、地物に基づいて現在位置が存在すると判断される概略領域を求めることができる。現在位置推定装置は、こうして求められた概略領域内の複数の地物を情報提示の対象として設定する。情報提示の対象となるべき地物は、ユーザが任意に選択した地物と同一であってもよいし、異なるものであってもよい。こうすることにより、現在位置が概ね絞り込まれた状態で、存在領域を画定するための処理を実行することができるため、効率的に精度良く存在領域を求めることが可能となる。
【００２３】
上述の前処理では、ユーザが入力した属性だけでは、それに対応する一つに地物を特定することができず、属性に対応する候補が複数存在する場合がある。このように特定の属性に対応する地物の候補が複数存在する場合には、各候補と別途入力された他の属性に対応する地物との距離に基づき、候補のいずれか一つを特定の属性に対応する地物として選択することが好ましい。
【００２４】
一例として、特定の属性に対応する候補が地物Ａ，Ｂの２つ存在する場合を考える。他の属性に対応する地物として地物Ｃが特定されているものとする。このような場合には、地物ＡＣの距離、地物ＢＣの距離をそれぞれ求めるのである。地物ＡＣ間の距離がユーザにとって双方の建物を視認可能な距離であり、地物ＢＣの距離が双方の建物を視認し得ないほどに離れている場合には、特定の属性に対応する地物として地物Ａを選択することができる。ユーザは地物Ａ，Ｃの双方を視認できる範囲に存在しているはずだからである。このように、入力された属性との対応関係のみならず、他の属性に対応する地物との位置関係を考慮することによって、属性に対応する地物を精度良く特定することが可能となる。
【００２５】
上述の前処理では、ユーザが入力した属性に対応する地物を十分に特定できない場合もある。かかる場合には、所定の地物に関する情報をユーザに提示するとともに、地物をユーザが視認できるか否かの回答を入力し、この回答を反映して概略領域を求めるようにしてもよい。かかる地物としては、比較的遠方からでも視認可能な大型のランドマークを用いることが好ましい。
【００２６】
このようにユーザに地物を提示して視認可否の回答を得る場合には、概略領域を絞り込むために、地物に関する情報の提示および回答の入力を所定の条件下で繰り返し実行することが好ましい。視認可否を尋ねる地物は任意に選択することも可能であるが、一の地物に対して視認できる旨の回答が得られた場合には、地物の位置に基づいて概略領域を狭めた上で、概略領域から次の情報提示の対象となる地物を選択することが好ましい。こうすることにより、視認可否についての無用な応答を省略し、効率的に概略領域を絞り込むことが可能となる。
【００２７】
逆に、一の地物に対して視認できない旨の回答が得られた場合には、地物の位置に基づいて概略領域を広げた上で、概略領域から次の情報提示の対象となる地物を選択するようにしてもよい。既存の概略領域内では別の地物についても視認できない旨の回答となる可能性が少なからずあるからである。視認可否の対象となる地物の選択範囲を広げることにより、このような無用な応答を回避でき、効率的に概略領域を見いだすことが可能となる。
【００２８】
先に説明した通り、概略領域の設定は、現在位置を推定する処理に先立つ前処理として行われるものである。現在位置推定装置は、上述の方法で概略領域を求めると、その中に存在する複数の地物を抽出して、存在領域を画定する処理に用いる。つまり、こうして抽出された複数の地物についての相対的な位置関係をユーザに問い合わせ、その結果に基づいて、存在領域を画定するのである。
【００２９】
本発明において、存在領域の画定は種々の方法を採ることができる。以下に画定方法の一例を示す。この方法では、まず、複数の地物のうち処理対象となる２つの地物を選択する。そして、選択された地物を包絡する凸多角形を求め、凸多角形を構成する辺のうち、２つの地物を結ぶ辺を選択する。辺の両端がそれぞれ異なる地物の頂点と重なる辺を選択すればよい。こうして選択された辺を延長すると、平面内は複数の領域に分割される。これらの各領域から、２つの地物を見た場合の相対的な位置関係は、領域ごとに定性的に相違する。従って、各領域について、ユーザから指定された相対的な位置関係に反しない領域を選択することで、存在領域の境界線を画定することができる。この方法によれば、比較的簡易な幾何学的処理で、境界線を画定することができる利点がある。
【００３０】
本発明では、ユーザが通行可能な道路をノード、リンクで表したネットワークデータを現在位置の推定に活用してもよい。ネットワークデータはユーザが移動可能な通路を表していると考えることができる。従って、現在位置推定装置は、ネットワークデータのうち、先に説明した地物を相対的な位置関係で視認可能な範囲、即ち存在領域内に存在するノードおよびリンク上のいずれかの地点を現在位置と推定することができるのである。例えば、歩行者を対象とした処理を行う場合、存在領域内に湖沼や自動車専用道路、線路などが存在すると、歩行者用のネットワークデータを参照することにより、歩行者が通行できないこれらの地点を現在位置の候補から速やかに外すことができ、簡易な処理で精度良く現在位置を推定することが可能となる。
【００３１】
ネットワークデータは種々の段階で活用することができる。例えば、存在領域を画定した後に、ネットワークデータを活用して、存在領域内のノード、リンクを抽出するようにしてもよい。また、存在領域を画定する段階でネットワークデータを活用し、複数の地物をユーザが入力した相対的な位置関係で視認可能となるノード、リンクの集合体として存在領域を求めるようにしてもよい。
【００３２】
上述の方法で、存在領域を求めた後、現在位置を更に絞り込む方法としては、例えば、その存在領域内の特定の地物の画像や属性をユーザに提示し、その地物が目の前に見えるか否かをユーザに入力させる方法を採ることができる。
【００３３】
本発明において、以上で説明した種々の特徴は、必ずしも全てを備えている必要はなく、その一部を省略したり、適宜、組み合わせたりして採用することができる。また、本発明は、上述した現在位置推定装置としての態様のみならず、コンピュータを用いてユーザの現在位置を推定するための現在位置推定方法として構成してもよい。更に、上述した現在位置推定を実現するためのコンピュータプログラムや、かかるコンピュータプログラムを記録した記録媒体として構成してもよい。ここで、記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【００３４】
本発明の実施例について、経路案内システムにおける現在位置推定機能として実現した場合を例にとって以下の順序で説明する。
Ａ．システム構成：
Ｂ．経路探索・案内処理：
Ｃ．現在位置推定処理：
Ｄ．基準建物設定処理：
Ｅ．存在領域画定処理：
Ｆ．基準建物の選択：
Ｇ．変形例：
【００３５】
Ａ．システム構成：
図１は実施例としての経路案内システムの構成を示す説明図である。本実施例では、歩行者用の経路案内システムとしての構成例を示すが、車両用の経路案内システムとして構成することもできる。経路案内システムは、携帯電話を利用した端末１００とサーバ２００とをネットワークＩＮＴで接続して構成されている。ネットワークＩＮＴは無線通信を利用したネットワークであり、ＬＡＮやイントラネットのように限定的なものであってもよいし、インターネットのように広域的なものであってもよい。端末１００は、携帯電話の他、いわゆる車両用のナビゲーション装置やＰＤＡ、ネットワーク通信機能を有するパーソナルコンピュータなどを利用することができる。歩行者用の経路案内システムとして構成する場合、車両用のナビゲーション装置は、車両から取り外して携帯可能としておくことが望ましい。
【００３６】
端末１００は、ユーザの操作に応じて、経路探索および経路案内に必要な指示をサーバ２００に送信するための機能を奏する。図中には、端末１００の機能ブロックを併せて示した。端末１００は、ＣＰＵ、ＲＡＭ、ＲＯＭを備えたマイクロコンピュータを制御装置として内蔵しており、このＣＰＵはＲＯＭに記憶されたソフトウェアを実行することで、図示する各機能ブロックを構成する。これらの機能ブロックは、このようにソフトウェア的に構成する他、ハードウェア的に構成することも可能である。
【００３７】
通信部１２０は、ネットワークＩＮＴを介してサーバ２００と通信する機能を奏する。ＧＰＳ１４０は、全地球測位システム（Global Positioning System）を利用して、端末１００の現在位置の緯度、経度を検出する。コマンド入力部１３０は、スイッチ等に対するユーザ操作に基づいて、経路探索や経路案内における目的地の指定、探索条件の指定、現在位置推定のための情報、その他のコマンドを入力する。表示制御部１５０は、端末１００のディスプレイに、これらのコマンド入力用のメニューを表示したり、サーバ２００から受信した経路案内データに基づいて地図を表示させたりする。主制御部１１０は、上述した各機能ブロックを統括制御することで、端末１００の全体機能を制御する。
【００３８】
サーバ２００は、端末１００からのコマンドに基づいて、種々のデータベースを参照しながら、経路探索を行ったり、経路案内を行ったりする。また、サーバ２００は、これらの処理過程で、端末１００のＧＰＳ１４０が電波を受信できない状態にある時など、ユーザの現在位置が不明となっている場合には、ユーザと所定の情報授受を行って現在位置を推定する機能、つまり本発明の現在位置推定装置としての機能も有している。図中には、これらの機能を実現するための機能ブロックおよびデータベースの例を示した。各機能ブロックは、サーバ２００のＣＰＵが実行するコンピュータプログラムによって、ソフトウェア的に構成されるが、ハードウェア的に構成することも可能である。
【００３９】
サーバ２００は、地図ＤＢ２５０を参照しながら、経路探索、経路案内、現在位置推定の各処理を実行する。地図ＤＢ２５０には、通路をノード、リンクで表したネットワークデータ２５２、地図描画用のポリゴンや文字データからなる描画データ２５４を有している。描画データ２５４には、建物などの各地物についての属性も記録されている。属性としては、例えば、建物の種別、名称、形状、高さ、色、外観（例えば、煉瓦造り、ガラス張りなど）が記録される。建物の写真を属性として記録してもよい。
【００４０】
経路案内ＤＢ２６０は、経路探索、案内の過程で端末１００から入力されたり、サーバ２００によって生成された種々のデータを格納する。かかるデータとしては、例えば、経路探索時にユーザが端末１００を操作して指定した探索条件や、ユーザの現在位置、経路探索の結果を示す経路案内データなどが含まれる。
【００４１】
通信部２１０は、端末１００とのネットワークＩＮＴ経由での通信を制御する。経路探索部２２０は、経路案内ＤＢ２６０に格納されている探索条件に従って、地図ＤＢ２５０のうち主としてネットワークデータ２５２を参照して、ユーザから指定された出発地、目的地間の経路を探索する。探索された結果は、上述の通り、経路案内ＤＢ２６０に経路案内データとして格納される。経路案内部２４０は、経路案内ＤＢ２６０内の経路案内データおよび現在位置を参照しながら、ユーザが進むべき経路を地図上に案内表示する表示データを生成し、端末１００に送信する。
【００４２】
推定エンジン２３０は、経路探索および経路案内の過程で、端末１００からユーザの現在位置が取得できない状況が生じた場合に、現在位置を推定するための処理を実行し、またユーザとの間で処理に必要な情報の授受を行う。基準建物設定部２３２は、現在位置を推定するための前処理として、ユーザとのやりとりによって、処理に用いられるべき基準建物を設定する機能を奏する。境界画定部２３４は、上述の基準建物を用いて、ユーザとのやりとりによって、存在領域、即ち「現在位置」が存在し得る領域の境界を画定する機能を奏する。この境界の画定において、選択部２３１は、基準建物が多数ある場合に、境界画定部２３４が用いるべき基準建物を所定の規則に従って決定する機能を奏する。情報提供部２３２は、ユーザが現地で基準建物を特定するために画像や属性などの情報を提示する。境界画定部２３４は、こうして選択された基準建物の位置関係に関してユーザが入力した情報を用いて上述の境界の画定を行うのである。基準建物設定部２３２、推定エンジン２３０境界画定部の処理内容については、後述する。
【００４３】
Ｂ．経路探索・案内処理：
図２は経路探索処理および経路案内処理のフローチャートである。サーバ２００の経路探索部２２０および経路案内部２４０が実行する処理であり、ハードウェア的にはサーバ２００のＣＰＵが実行する処理である。
【００４４】
経路探索処理では、サーバ２００はユーザからの指定に従った方法で、経路探索の出発地を設定する。現在位置を出発地として用いる指定がなされている時には（ステップＳ１０）、現在位置推定処理を実行して（ステップＳ１２）、現在位置を取得する。現在位置を出発地としない旨の指定がなされている時には、端末１００から出発地の指定を入力する（ステップＳ１１）。出発地の指定には、例えば、ユーザが地図上の一点をクリックする方法や、住所を入力する方法などを採ることができる。
【００４５】
サーバ２００は、次に経路探索の目的地、探索条件を入力する（ステップＳ１４）。目的地は、出発地の指定と同様の方法、または目的地の名称やレストラン、ショップなどの種別から検索する方法などを採ることができる。探索条件としては、最短距離の経路を探索する旨の指定、所要時間最短の経路を探索する旨の指定、上り坂や階段を回避する経路を探索する旨の指定などが可能である。
【００４６】
サーバ２００は、上述の各条件に基づき、経路探索処理を実行する（ステップＳ１６）。経路探索は、ダイクストラ法によって行うことができる。ダイクストラ法は、周知の方法であるため、詳細な説明は省略するが、道路を表すノード、リンクにそれぞれ付されたコストが最小となる経路を探索する方法である。上り坂や階段を回避する探索条件が付されている場合には、上り坂等に対応するリンクのコストを大きい値に設定することにより、探索条件を満たす経路を探索することができる。他の探索条件が指定されている場合にも、同様に、探索条件に応じて各リンクのコストを設定することにより、それぞれの探索条件を満たす経路を探索することが可能である。経路探索が完了すると、サーバ２００は、経路案内データを経路案内ＤＢ２６０に出力して、経路探索処理を終了する（ステップＳ１８）。
【００４７】
サーバ２００は、引き続き、経路案内データを参照して、経路案内処理を実行する。経路探索処理と経路案内処理とは一連の処理としてシーケンシャルに実行することも可能ではあるが、本実施例では、両者を別個の処理として構成した。こうすることにより、経路探索と経路案内とをそれぞれ別のタイミングで実行することができ、経路案内システムの利便性を向上させることができる。例えば、電車の乗車中に、電車を降りた後の駅から目的地までの経路探索を実行しておき、駅に到着した後、経路案内を開始するということが可能となるのである。
【００４８】
経路案内処理では、サーバ２００は、経路案内ＤＢ２６０に格納された経路案内データを読み込む（ステップＳ５０）。そして、現在位置推定処理によって（ステップＳ５２）、ユーザの現在位置を取得し、案内表示処理（ステップＳ５４）によって、ユーザが進むべき経路を地図上に表示する。サーバ２００は、以上の処理をユーザが目的地に到着するまで繰り返し実行し（ステップＳ５６）、経路案内処理を完了する。
【００４９】
Ｃ．現在位置推定処理：
図３は現在位置推定処理例を示す説明図である。本実施例では、サーバ２００が、処理に用いる複数の建物を決定し、ユーザから見た状態でのこれらの複数の建物相互の相対的な位置関係を問い合わせ、その結果に基づいて現在位置の存在領域を画定する方法を採る。以下の説明では、図３（ａ）の地図上に示す建物Ａ，Ｂ，Ｃ，Ｄに対する相対的な位置関係を入力した場合の処理を例にとって説明する。存在領域の画定に用いられる建物Ａ〜Ｄを、以下、基準建物と呼ぶ。
【００５０】
ユーザからは、これらの建物相互の左右の位置関係が入力される。図３（ｂ）はユーザにとって「建物Ｂが建物Ａの左側に見える」場合の存在領域を示している。図中に太線で示した境界線よりも矢印で示した側であれば、ユーザは建物Ａ，Ｂを、上述の位置関係で見ることができる。２つの建物の相対的位置関係が与えられた場合に、図３（ｂ）に示す形で存在領域を画定する方法については後述する。
【００５１】
図３（ｂ）で存在領域の境界線が建物Ａ，Ｂ間で折れ曲がっているのは、上述の条件に適合する存在領域として、建物Ａ、Ｂの間の領域も含めるものとしたからである。建物Ａ，Ｂ間の領域では、ユーザの位置および姿勢に応じて、建物Ａ、Ｂの相対的な位置関係は変化する。建物Ａが建物Ｂの左に見えることもあれば、その逆に見えることもある。また、建物Ａがユーザの前面に見え、建物Ｂがユーザの背後に見える場合、およびその逆に見える場合もある。本実施例では、「建物Ｂが建物Ａの左側に見える」という可能性があることを考慮し、建物Ａ、Ｂ間の領域も条件に合致する存在領域に含めている。本実施例では、左右いずれかに見えるという二者択一の形で建物の位置関係を問い合わせるものとしたが、この他に「建物の間に自分がいる」という選択肢を加えても良い。また、建物ＡおよびＢが重なって見える、またはいずれか一方の建物しか見えないという選択肢を加えても良い。これらの選択肢は、建物およびユーザがほぼ一直線上に並んでいるという３者の相対的な位置関係を表すものである。このような位置関係が成立する範囲は比較的限られるため、上述の選択肢を加えることにより、速やかにユーザの現在位置を絞り込むことが可能となる。
【００５２】
同様にして、ユーザから、「建物Ｃが建物Ｂの左側に見える」という位置関係が入力された場合には、図３（ｃ）に示す存在領域を画定することができる。「建物Ｄが建物Ｃの左側に見える」という位置関係が入力された場合には、図３（ｄ）に示す存在領域を画定することができる。「建物Ａが建物Ｄの左側に見える」という位置関係が入力された場合には、図３（ｅ）に示す存在領域を画定することができる。図３（ｂ）〜図３（ｅ）で画定された存在領域を重ねることにより、図３（ｆ）に示す通り、上述した全ての相対的な位置関係を満たす存在領域を求めることができる。
【００５３】
図４は存在領域の境界を画定する処理例を示す説明図である。図３において建物Ａ、Ｂの相対的な位置関係が指定された場合の処理例、即ち図３（ａ）の境界を画定するための処理例を示した。建物Ａ、Ｂは、図４（ａ）に示す位置に存在するとする。図の煩雑さを避けるため、図４（ｂ）〜図４（ｄ）では、背景の地図を省略して、建物Ａ、Ｂの位置および形状を示すものとする。
【００５４】
境界を画定する処理では、この建物Ａ、Ｂについて、図４（ｂ）に示すように両者を包絡する凸多角形を求める。次に、この凸多角形の各辺のうち、異なる建物にまたがるものを抽出する。つまり、辺の一端が建物Ａを表すポリゴンのいずれかの頂点と重なり、他端が建物Ｂを表すポリゴンのいずれかの頂点と重なる辺を抽出するのである。図４（ｂ）の例では、辺ｓ１、ｓ２がこの辺に該当する。
【００５５】
図４（ｃ）に示すように、抽出された辺ｓ１、ｓ２を延長する。これによって、平面は領域α０〜α５に分割される。建物Ａ、Ｂの見え方は、各領域で異なっている。領域α０はユーザの姿勢によって建物Ａ、Ｂの相対的な位置関係が変動する領域である。領域α１は建物Ａのみが視認でき、建物Ｂは視認できない領域である。領域α２は逆に建物Ｂのみが視認でき、建物Ａは視認できない領域である。もっとも、領域α１、α２においては、建物Ａ、Ｂの高さ関係によっては、建物Ａ、Ｂを前後に並んで見えることもある。領域α３は、建物Ａの背後に建物Ｂが見える領域であり、ユーザの姿勢によっては建物Ｂが建物Ａの左側に見える領域でもある。
【００５６】
領域α４は建物Ａが建物Ｂの左側に見える領域である。領域α５は建物Ｂが建物Ａの左側に見える領域である。以上より、ユーザから、「建物Ｂが建物Ａの左側に見える」という位置関係が指定された場合には、領域α０、α３、α５がこの条件に該当することになる。従って、この条件に対しては、図４（ｄ）に示すように、領域α０、α３、α５を合わせた範囲が存在領域として画定され、その境界線が特定されることになる。先に図３（ｂ）で示した境界線は、こうして求められたものである。図３（ｃ）〜図３（ｅ）に示したそれぞれの境界も、同様の方法によって求めることができる。
【００５７】
図４の方法で画定される存在領域は、理論上は無限に広がることになるが、実際には建物を視認可能な範囲は限られている。従って、建物の高さに応じて設定される視認可能範囲も併せて考慮し、存在領域は、この視認可能範囲内の有限な領域として扱うことが好ましい。
【００５８】
図５は現在位置推定処理のフローチャートである。推定エンジン２３０（図１参照）が図３、４で説明した処理を実現するためのフローチャートであり、ハードウェア的にはサーバ２００のＣＰＵが実行する処理である。
【００５９】
現在位置推定処理では、サーバ２００は、まず端末１００のＧＰＳ１４０が有効に機能しているか否かを判断する（ステップＳ１０２）。ＧＰＳ１４０が有効に機能している場合には、端末１００から現在位置を入力し（ステップＳ１０４）、現在位置推定処理を終了する。
【００６０】
ＧＰＳ１４０が機能していないと判断される場合には、図３、４に示した方法で現在位置を推定するための処理を実行する。サーバ２００は、まず基準建物設定処理を行う（Ｓ１１０）。基準建物設定処理は、図３の建物Ａ〜Ｄのように、存在領域の画定に用いられる基準建物を設定するための処理である。基準建物設定処理の内容は後述する。
【００６１】
サーバ２００は、設定された基準建物を用いて存在領域画定処理を実行する（ステップＳ１５０）。図３および図４で説明した処理であり、ユーザから、基準建物間の相対的な位置関係の入力を受け、これに対応する存在領域を画定するのである。存在領域画定処理の内容についても後述する。基準建物設定処理および存在領域画定処理は、それぞれ存在領域が画定されるまで継続する。例えば、基準建物設定処理において設定された基準建物の位置関係によっては、存在領域を十分に絞り込むことができない場合もある。このような場合には、サーバ２００は、存在領域は画定されていないと判断し、基準建物設定処理および存在領域画定処理を再試行するのである。
【００６２】
存在領域が画定されたか否かの判断は、種々の方法で行うことが可能である。例えば、存在領域が閉図形となった場合に画定されたと判断するようにしてもよいし、存在領域の面積または外接円の半径が所定値以下となった時に画定されたと判断するようにしてもよい。
【００６３】
サーバ２００は、存在領域が画定されると、現在位置を更に精度良く特定するための処理を行う。このための処理として、サーバ２００は、存在領域内の歩道リンクを抽出し（ステップＳ１８２）、その歩道リンク周辺の建物群を抽出する（ステップＳ１８４）。そして、端末１００に、この抽出された建物の建物情報を提示し、ユーザからの回答を入力する（ステップＳ１８６）。
【００６４】
図中にこの入力のためのインタフェース画面ＤＩＳＰを例示した。図の例では、抽出された建物の画像を提示し、その建物の視認可否をユーザに確認する方法を採っている。この例では、「目の前に」見えるか否かを聞く形としているため、ユーザが「ＹＥＳ］と回答した場合には、ほぼピンポイントで現在位置を特定することが可能となる。ユーザが「ＮＯ」と回答した場合には、現在位置が特定されないため、サーバ２００は他の建物について同様に視認可否を確認する（ステップＳ１８８）。
【００６５】
ステップＳ１８６では、「目の前」に限らず、単に建物の視認可否を訪ねるようにしてもよい。建物を視認可能な範囲は、建物の位置を中心とし、建物の高さに応じた半径で描いた円形領域と設定することができる。従って、ユーザが視認可と回答した場合には、ユーザの現在位置は上述の視認可能領域内にあると判断される。複数の建物についてユーザに視認可否を確認することにより、視認可能領域が重なり合う箇所が限定され、ユーザの現在位置を特定することが可能となる。本実施例では、ユーザステップＳ１８４までの処理で、存在領域が十分に絞り込まれているため、ユーザ付近の建物についてステップＳ１８６の質問および回答入力を行うことができ、現在位置を十分な精度で特定することが可能となる。
【００６６】
上述の実施例において、ステップＳ１８２〜Ｓ１８８の処理は省略してもよい。この処理を省略する場合には、例えば、存在領域中の任意の点、存在領域の重心などを現在位置と特定することができる。ステップＳ１８０までの処理で、存在領域が十分に絞り込まれている時には、上述の方法で現在位置を特定しても、経路探索処理および経路案内処理に支障が生じない程度の精度で現在位置を特定することが可能である。
【００６７】
Ｄ．基準建物設定処理：
図６は基準建物設定処理（前半）のフローチャートである。現在位置推定処理（図５）のステップＳ１１０に相当する処理である。基準建物設定部（図１参照）の機能に相当する処理であり、存在領域画定処理に用いる基準建物の設定を行う点で存在領域画定処理の前処理と言うこともできる。
【００６８】
基準建物設定処理が開始されると、サーバ２００はユーザが視認可能な範囲で任意に選択した建物について建物属性を入力する（ステップＳ１１１）。図中に建物属性を入力するために端末１００に表示されるインタフェース画面例ＤＩＳＰ１を示した。この例では、名称、種別、高さ、色を入力可能となっている。建物の名称が分かっている場合には、「名称」欄にそれを入力する。「種別」では、病院、デパート、マンション、ホテルなどから該当するものを選択する。「高さ」欄には、建物の階数を入力する。色には、建物の外観の色を入力する。煉瓦造り、ガラス張りなど、外観を入力可能としてもよい。属性は、ここに例示した項目に限らず、その他種々の項目を入力可能としてよい。
【００６９】
サーバ２００は、入力された属性に該当する候補建物を地図ＤＢ２５０から抽出する（ステップＳ１１２）。この場合、入力された属性に完全に一致するもののみを特定するようにしてもよいし、一定範囲で入力された属性との不一致を許容して地物を特定するようにしてもよい。後者の態様では、入力された項目のうち、所定数までは不一致であっても許容するという扱いをすることができる。例えば、図中に示した４つの項目のうち、１つまでは不一致を許容するものとすれば、「病院以外」の５階建ての白い建物や、「４階建て」の白い病院なども候補として抽出されることになる。不一致を許容する別の態様としては、各項目に対し許容誤差を認める扱いをしてもよい。図中の例では、例えば、５階建てという高さに対して「±１階」という誤差を許容すれば、４階建てや６階建ての白い病院も候補として抽出されることになる。基準建物設定処理では、ユーザはやや遠方にある建物についての属性を入力する可能性もあるから、このように一定の誤差を許容することにより、ユーザの見間違えなどによる属性の入力ミスを補充することができ、ユーザの意図に沿って候補の建物を抽出する可能性を高めることができる。
【００７０】
ステップＳ１１２の処理では、抽出された候補が一つに特定されないことがある。このような場合には、サーバ２００は既に設定された基準建物や他の候補建物との距離によって、候補を一つに絞り込む（ステップＳ１１３、Ｓ１１４）。
【００７１】
図中にこの絞り込みの方法を示した。左側の図は、建物ａ，ｂ，ｃの３つが候補となっている時に、基準建物ＢＢとの距離に基づいて、これらのいずれか一つに絞り込む例を示している。円形の領域Ｃａ〜Ｃｃは、建物ａ〜ｃのそれぞれを視認可能な領域である。円形領域Ｃｂｂは基準建物ＢＢを視認可能な範囲である。領域Ｃａ〜Ｃｃ、Ｃｂｂの半径は、建物ａ〜ｃ、ＢＢの高さに応じて設定することができ、高さが高いほど半径も大きくなる。既に設定済みの基準建物ＢＢが存在する場合、ユーザは、基準建物ＢＢを視認可能な位置、即ち領域Ｃｂｂ内に存在していることになる。一方、建物ａ〜ｃが候補として抽出されている時、ユーザは、建物ａ〜ｃのいずれかを視認可能な範囲、即ち領域Ｃａ〜Ｃｃのいずれかに存在していることになる。図示した位置関係では、領域Ｃｂｂと少なくとも一部が重なっているのは領域Ｃａのみである。従って、ユーザは領域Ｃｂｂ、Ｃａが重なっている範囲内に存在していると考えられ、ユーザが入力した属性に対応するのは建物ａであると特定することができる。
【００７２】
図の右側には、他の候補との距離に基づく絞り込みの例を示した。ユーザが入力した第１の属性に対応する候補が建物ｄ１、ｄ２であり、第２の属性に対応する候補が建物ｅ１、ｅ２であるとする。図中には、各建物の視認可能領域を併せて示した。ユーザは、建物ｄ１またはｄ２を視認可能な位置にいるとともに、建物ｅ１またはｅ２を視認可能な位置にいると考えられる。図示した位置関係では、候補ｄ２と候補ｅ１の視認可能領域が重なっている。このことから、第１の属性に対応する候補は建物ｄ２であり、第２の属性に対応する候補は建物ｅ１であると特定することができる。
【００７３】
サーバ２００は、上述の処理の結果、属性に対応した候補が一つに絞られた場合には、その候補を基準建物として登録する（ステップＳ１１５）。ステップＳ１１４の処理を実行しても候補が一つに絞り込めない場合には、抽出された複数の建物を候補として記憶しておくことになる。上述の候補ｄ１、ｄ２および候補ｅ１、ｅ２の処理例のように、他の候補建物の絞り込みを行う過程で、併せて一つの候補への絞り込みが可能となることもあるからである。サーバ２００は、また、地図ＤＢから抽出した時点で候補が一つに特定されている場合には（ステップＳ１１３）、ステップＳ１１４による絞り込みをスキップして、抽出された候補を基準建物として登録する（ステップＳ１１５）。
【００７４】
ユーザが他の属性を入力する旨を指示した場合には（ステップＳ１１６）、サーバ２００は、ステップＳ１１１〜Ｓ１１５までの処理を再度実行する。他の属性を入力しない旨の指示があった場合には（ステップＳ１１６）、サーバ２００は後半の処理に移行する。
【００７５】
図７は基準建物設定処理（後半）のフローチャートである。先に説明した処理によって基準建物数が３以上となっている時には、サーバ２００は、更に多くの基準建物を設定する必要はないと判断し（ステップＳ１２０）、基準建物設定処理を終了する。３個に満たない場合には、更に基準建物数を増やすための処理を実行する。存在領域を精度良く絞り込むためには、３個以上の基準建物を使うことが好ましいからである。もっとも、存在領域の画定にそれほど高い精度を要求されていない場合には、２個の基準建物が設定された時点で基準建物設定処理を終了してもよい。
【００７６】
基準建物数が３個に満たない場合、サーバ２００は、既に登録されている基準建物に基づき概略存在領域を設定する（ステップＳ１２１）。概略存在領域とは、基準建物の視認可能範囲から定まる現在位置の存在領域である。図中に概略存在領域の設定方法を例示した。ここでは、建物Ｂ１，Ｂ２が基準建物として設定されているものとする。各建物については、先に説明した通り、視認可能領域を求めることができる。図示する通り、建物Ｂ１、Ｂ２に対する視認可能領域は、半径ｒ１、ｒ２の円形領域とした。半径ｒ１、ｒ２は、建物Ｂ１、Ｂ２の高さに応じて定めることができる。概略存在領域は、各基準建物の視認可能領域が重なり合う部分として特定することができ、図の例では、ハッチングを付した領域となる。
【００７７】
サーバ２００は、こうして特定された概略存在領域から、基準建物となるべき候補建物を抽出する（ステップＳ１２２）。候補建物は種々の方法で抽出可能である。例えば、概略存在領域の中心付近に位置する建物を抽出するようにしてもよいし、多くの属性が対応づけられている建物を抽出するようにしてもよい。ユーザの視認しやすさを考え、所定以上の高さの建物を抽出するようにしてもよい。
【００７８】
サーバ２００は、抽出された候補建物について、建物情報を提示し、ユーザからの視認可否についての回答を入力する（ステップＳ１２３）。図中にこのためのインタフェース画面例を示した。この例では、端末１００に候補建物の画像を示すとともに、視認可否を入力するようになっている。ユーザの誤解を回避するという点では、このように候補建物の画像を提示することが好ましいが、必ずしも画像は必須ではなく、建物の名称、種別、階数、色などの属性で情報を提示するようにしてもよい。
【００７９】
提示した建物情報に対し、ユーザが視認可と回答した場合には（ステップＳ１２４）、サーバ２００はこの建物を基準建物として登録するとともに、基準建物数を１つ加算する（ステップＳ１２５）。この結果、基準建物数が３以上となれば（ステップＳ１２０）、基準建物設定処理を終了し、３に満たない場合には、ステップＳ１２１以降の処理を再度実行することになる。再度実行する際には、ステップＳ１２５で新たに登録された基準建物も考慮して、概略存在領域を設定する（ステップＳ１２１）。従って、徐々に概略存在領域は狭まっていくことになる。
【００８０】
一方、提示した建物情報に対し、ユーザが視認不可と回答した場合には（ステップＳ１２４）、サーバ２００は試行回数が予め設定された上限値に至るまで（ステップＳ１２６）、概略存在領域を拡張して（ステップＳ１２７）、ステップＳ１２２以降の処理を再度実行する。既存の概略存在領域を一定の相似比で拡張するようにしてもよいし、概略存在領域の周囲に一定幅の帯状領域を付加していくことで拡張するようにしてもよい。概略存在領域を拡張するのは、ステップＳ１２２で抽出された候補建物が視認不可と回答された場合には、ステップＳ１２１で設定された概略存在領域が誤っている可能性があるからである。
試行回数が上限値に至った場合には、この処理を行うことなく基準建物設定処理を終了する。
【００８１】
本実施例では、前半の処理（図６）において、ユーザが属性を入力した建物を基準建物として登録する処理例を示しているが、基準建物の設定は、かかる方法には限られない。例えば、前半の処理（図６）でユーザが属性を入力した建物は、図７における概略存在領域の設定にのみ用いるものとし、存在領域画定処理（図５のステップＳ１５０）で使用する基準建物は、後半（図７）の処理によって設定されたもののみを用いるようにしてもよい。
【００８２】
Ｅ．存在領域画定処理：
図８は存在領域画定処理のフローチャートである。図５のステップＳ１５０に相当する処理であり、境界画定部２３４（図１参照）の機能に相当する処理である。この処理では、図３および図４で説明した方法によって、存在領域が画定される。
【００８３】
サーバ２００は、まず、基準建物の位置、形状および高さデータを入力する（ステップＳ１５１）。本実施例では、３つ以上の基準建物が入力されることになる。存在領域の画定は、図４に示した通り、２つの基準建物に対する境界画定処理（図４）を繰り返し実行することで行う。
【００８４】
サーバ２００は、入力された基準建物のうち、境界画定処理の対象となる基準建物２つを選択する（ステップＳ１５２）。この選択は、任意の方法で行うことができるが、本実施例では、以下に示す３つの基準に基づいて選択するものとした。
優先度１：画定した境界に交差する位置関係にあるもの；
優先度２：存在領域内に存在する２つの建物；
優先度３：高さの低い建物；
【００８５】
基準建物として、図中に示した建物Ａ（１０階）、建物Ｂ（１２階）、建物Ｃ（１４階）が存在する場合を考える。既に建物Ａ、Ｂ間の処理によって境界Ｌが画定され、図示するようにＣを含む側の領域が存在領域として画定されているものとする。この状態では、サーバ２００は次に建物Ａ、Ｃまたは建物Ｂ、Ｃのいずれかを選択して境界画定処理を実行することになる。この組み合わせでは、いずれも画定済みの境界Ｌに交差する境界を画定することができるため、上述の「優先度１」「優先度２」の条件ではいずれか一方の組み合わせを選択することはできない。従って、優先度３の条件に従い、高さの低い建物、即ち建物Ａを優先的に使用することになる。この結果、建物Ａ、Ｃを基準建物として境界画定処理を実行することになる。建物Ａ、Ｃを基準建物として境界画定処理を実行した時点で、まだ存在領域が画定されていない場合には、建物Ｂ、Ｃを基準建物として境界画定処理を実行することになる。
【００８６】
サーバ２００は、ステップＳ１５２の処理で選択された基準建物の属性をユーザに提示するとともに、両者の相対的な位置関係の入力を行う（ステップＳ１５３）。図中に位置関係を入力するために端末１００に表示されるインタフェース画面例を示した。この例では、２つの基準建物の画像を表示し、左右の位置関係を入力するようになっている。図の例では、ユーザからは、上の建物の方が下の建物よりも左側に見えていることになる。このインタフェース画面では、上または下の建物について、左または右を選択すると、他方の建物については連動して入力状態が変わる。例えば、図の状態において、ユーザが上の建物について「右」を選択すると、下の建物の入力状態は自動的に「左」に切り替わる。こうすることで入力の誤りを低減することができる。
【００８７】
本実施例では、左右関係を入力するようにしたが、これに代えて建物相互の前後関係を入力するようにしてもよい。ただし、ユーザから見て建物相互の位置関係を特定する場合には、前後関係よりも左右関係の方が容易かつ正確に特定できるという利点がある。
【００８８】
サーバ２００は、基準建物の左右関係を入力すると、この結果に基づき境界画定処理を実行する（ステップＳ１５４）。境界画定処理は、図４で示した手法によって、ユーザが指定した左右関係に合致する存在領域を特定する処理である。
【００８９】
サーバ２００は以上の処理を所定の完了条件が満たされるまで繰り返し実行する（ステップＳ１５４）。本実施例では、「存在領域が閉領域となること」を完了条件とした。先に示した図３の例では、図３（ｂ）〜図３（ｅ）の４本の境界が画定された時に存在領域が閉領域となり、完了条件が満たされることになる。完了条件が満たされていない場合には、基準建物の組み合わせを変更して（ステップＳ１５２）、相対的位置関係の入力（ステップＳ１５３）、境界画定（ステップＳ１５４）の各処理を再度実行することになる。サーバ２００は以上の処理で画定した存在領域を出力して（ステップＳ１５６）、存在領域画定処理を終了する。
【００９０】
完了条件（ステップＳ１５５）は、上述の条件に限らず任意に設定可能である。例えば、閉図形になることに加えて存在領域の面積または外接円の半径が所定値以下となる条件を用いてもよい。また、存在領域の面積や外接円の半径を完了条件に用いる場合には、境界画定処理（ステップＳ１５４）で画定された境界のみで閉図形となるという条件を緩和し、図７で説明した概略存在領域の境界と併せて閉図形を構成するという条件を用いるようにしてもよい。完了条件は、このように存在領域自体の形状に基づく条件の他、全ての基準建物が一度は境界画定処理に利用されるという条件を用いてもよい。最も厳密な処理を行う場合には、基準建物の全組み合わせについて境界画定処理が完了するという条件とすることもできる。
【００９１】
Ｆ．基準建物の選択：
先に図８のステップＳ１５２で説明した通り、本実施例では、以下に示す３つの優先度に従って、基準建物の選択を行った。
優先度１：画定した境界に交差する位置関係にあるもの；
優先度２：存在領域内に存在する２つの建物；
優先度３：高さの低い建物；
以下では、これらの条件の意義について具体例を用いて説明する。
【００９２】
図９は基準建物の選択例を示す説明図である。それぞれ、基準建物として図示する位置に建物Ａ〜Ｄが存在する場合における境界画定処理の手順および存在領域を例示した。
【００９３】
図９（ａ）について説明する。最初に境界画定処理を行う際には、画定した境界が存在しないから、優先度１、優先度２の条件に適合する建物は存在しないことになる。従って、優先度３の条件に従い、高さの低い建物が選択される。図９（ａ）の例では、１０階の建物Ａ、および１２階の建物Ｂ、Ｃの一方が選択される。建物Ｂおよび建物Ｃはいずれを選択しても構わない。図の例では、建物Ｂが選択されたとする。この結果、建物Ａ、Ｂを通る境界線Ｌ［１］が画定される。境界線Ｌ［１］のハッチングを付した側が存在領域を表している。以下の例でも同様である。先に図４に示した通り、境界線は建物Ａ、Ｂ間で複雑な形状となるが、ここでは簡略化し、ただの直線で示した。
【００９４】
次に、優先度１の条件に従って、境界Ｌ［１］に交差する境界を画定可能な建物が選択される。図９（ａ）の例では、この条件に該当する組み合わせとして、建物ＡＣ、建物ＡＤ、建物ＢＣ、建物ＢＤの４通りの組み合わせが可能である。これらの組み合わせは、いずれも境界線Ｌ［１］で画定される存在領域内に存在する２つの建物、つまり、この存在領域内に境界線を画定する建物であるため、優先度２の条件に対しては優劣がない。しかし、優先度３の条件によれば、高さの低い建物Ａを通る組み合わせが選択されるため、建物ＡＣ、ＡＤの組み合わせが候補として残ることになる。更に優先度３の条件により、建物Ｃ、Ｄのうち高さが低い建物Ｃが選択される。この結果、建物ＡＣを用いて境界Ｌ［２］が画定される。
【００９５】
次に、再び、優先度１の条件に従って、まず境界Ｌ［２］に交差する境界を画定可能な建物を選択する。この例では、建物ＢＤ，建物ＡＤ、建物ＣＤ、建物ＢＣの４通りがこの条件を満足することになる。ただし、完全に交差する境界を画定可能なのは建物ＢＤのみである。建物ＡＤ、ＣＤの組み合わせは、それぞれ境界Ｌ［２］上の建物を利用しているからである。このように本実施例では、優先度１の条件を考慮する場合には、画定した境界に「完全に」交差する位置関係にある建物をより優先して利用する。この結果、図９（ａ）の例では、建物ＢＤが選択され、境界Ｌ［３］が画定される。
【００９６】
上述の通り、図９（ａ）の場合、本実施例の優先度１〜３に従って、基準建物を選択することにより、３回の境界線画定処理によって、効率的に存在領域ＡＰａを画定することが可能となる。
【００９７】
図９（ｂ）について説明する。最初に処理する際には、優先度１、２に該当する建物が存在しないため、優先度３に従って、建物ＡＣが選択され、境界Ｌ［１］が画定される。次の処理では、この境界Ｌ［１］に完全に交差する位置関係にある建物ＢＤが選択され、境界Ｌ［２］が画定される。そして、３度目の処理では、境界Ｌ［１］、Ｌ［２］に完全に交差する位置関係の建物は存在しないため、優先度２の条件が効き、建物ＡＢが選択され、境界Ｌ［３］が画定される。この結果、図９（ｂ）でも３回の処理で存在領域ＡＰｂを画定することができる。
【００９８】
図９（ｃ）について説明する。最初に処理する際には、優先度１、２に該当する建物が存在しないため、優先度３に従って、建物ＡＣが選択され、境界Ｌ［１］が画定される。次の処理では、この境界Ｌ［１］に完全に交差する位置関係にある建物ＢＤが選択され、境界Ｌ［２］が画定される。そして、３度目の処理では、境界Ｌ［１］、Ｌ［２］に完全に交差する位置関係の建物は存在しないため、優先度２の条件が効き、建物ＡＤが選択され、境界Ｌ［３］が画定される。図９（ｂ）の場合と選択される建物が相違するのは、２回目の処理が完了した時点で絞り込まれている存在領域が異なるからである。図９（ｃ）の場合も３回の処理で存在領域ＡＰｃを画定することができる。
【００９９】
４つの基準建物が存在する場合、全ての組み合わせで境界線画定処理を実行すると、６回の処理が要求されることになる。これに対し、本実施例の優先度を利用すれば、図９に示したように、３回の処理で存在領域を画定することができる。図９では、４つの基準建物が存在する例を示したが、５つ以上の基準建物が存在する場合でも同様に存在領域を画定するための処理回数を低減することができ、効率的に存在領域を画定することができる。
【０１００】
以上で説明した本実施例の経路案内システムによれば、現在位置推定機能を備えることにより、ユーザの現在位置が不明な時でも、十分な精度で現在位置を推定することができる。この結果、現在位置が不明という原因によって経路探索、経路案内が利用できなくなるという弊害を緩和することができ、経路探索、経路案内の利便性を向上させることができる。上述の本実施例ではＧＰＳ１４０を有する端末１００を利用する例を示したが、本実施例は、ＧＰＳ１４０を備えない端末１００で利用することも可能である。
【０１０１】
Ｇ．変形例：
実施例では、図８，９で示したように、存在領域を面として求める例を示した。存在領域は、必ずしも面として求める必要はない。例えば、歩行者用のネットワークデータに含まれるノード、リンクの集合体としての網状領域を存在領域としてもよい。変形例では、このような網状の存在領域を求める処理について説明する。
【０１０２】
図１０は変形例としての存在領域画定処理のフローチャートである。実施例の図８で示した処理に代わるものである。サーバ２００は、実施例と同様、基準建物位置、形状、高さデータの入力（ステップＳ１５１）、基準建物の選択（ステップＳ１５２）、建物の相対位置関係入力（ステップＳ１５３）、境界画定処理（ステップＳ１５４）を実行する。各処理は、実施例（図８）と同様である。
【０１０３】
次に、サーバ２００は、基準建物を視認可能な範囲を画定し（ステップＳ１５４ａ）、ステップＳ１５４で設定された境界および視認可能な範囲で囲まれる領域内に存在するノード、リンクを抽出する（ステップＳ１５４ｂ）。図の右側に、これらの処理例を示した。ネットワークデータは、図示する地図上の各通路に対応したノード、リンクを格納している。ステップＳ１５４までの処理において、基準建物Ｂａ，Ｂｂを用いて、境界Ｌａｂが求められたとする。存在領域は、図中のハッチングを付した側、即ち境界Ｌａｂの下側であるとする。
【０１０４】
図中の円Ｃａ，Ｃｂは、それぞれ基準建物Ｂａ、Ｂｂを中心とする円であり、視認可能な範囲を表している。円の半径は、基準建物Ｂａ、Ｂｂの高さに応じて設定することができる。ステップＳ１５４ｂの処理では、境界Ｌａｂ、円Ｃａ，Ｃｂで囲まれた領域内のノードおよびリンクＬｎｋを抽出する。図中では、抽出されたノード、リンクを太線で示した。変形例では、図中のハッチングで付された領域ではなく、抽出されたノードおよびリンクの集合体が存在領域となるのである。変形例では、視認可能な範囲（図中の円Ｃａ，Ｃｂを考慮してノード、リンクを抽出しているが、境界Ｌａｂのみを考慮してノード、リンクを抽出するようにしてもよい。
【０１０５】
以上の処理をサーバ２００は所定の完了条件が満たされるまで（ステップＳ１５５Ａ）、繰り返し実行する。完了条件としては、例えば、抽出されたノード、リンクの総数が所定値以下という条件を用いることができる。図の例においても、繰り返し処理を実行することで、境界Ｌａｂに加え、更に多くの境界が求められれば、境界および基準建物を視認可能な範囲で囲まれる領域は狭くなり、抽出されるノード、リンクの総数も小さくなる。そして、この総数が所定値以下となったところで完了条件が満たされたと判断するのである。完了後、サーバ２００は求められた存在領域を出力し（ステップＳ１５６）、この処理を終了する。
【０１０６】
上述の存在領域画定処理が完了した後は、実施例と同様、図５のステップＳ１８２以降の処理を行うことになる。ただし、変形例では、存在領域自体が歩道リンクで構成されているため、ステップＳ１８２の処理は省略することができる。実施例では、ステップＳ１８２の処理を実行することで非常に多くの歩道リンクが抽出される可能性があるのに対し、変形例では、存在領域画定処理の時点で十分に歩道リンクを絞り込むことが可能である。従って、変形例では、現在位置の特定（ステップＳ１８４〜Ｓ１８８）の処理を効率的に行うことができ、精度良く現在位置を求めることができる利点がある。
【０１０７】
以上、本発明の種々の実施例について説明したが、本発明はこれらの実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。実施例では、経路案内処理、経路探索処理の一機能として現在位置推定機能を有する場合を例示したが、本実施例の現在位置推定機能は、この他の用途に用いることも可能である。例えば、周辺のレストラン、ショップ等の情報を検索するサービスにおける現在位置推定機能として実現してもよい。これらのサービスに関わらず、現在位置を推定する固有の装置として構成することもできる。
【図面の簡単な説明】
【０１０８】
【図１】実施例としての経路案内システムの構成を示す説明図である。
【図２】経路探索処理および経路案内処理のフローチャートである。
【図３】現在位置推定処理例を示す説明図である。
【図４】存在領域の境界を画定する処理例を示す説明図である。
【図５】現在位置推定処理のフローチャートである。
【図６】基準建物設定処理（前半）のフローチャートである。
【図７】基準建物設定処理（後半）のフローチャートである。
【図８】存在領域画定処理のフローチャートである。
【図９】基準建物の選択例を示す説明図である。
【図１０】変形例としての存在領域画定処理のフローチャートである。
【符号の説明】
【０１０９】
１００…端末
１１０…主制御部
１２０…通信部
１３０…コマンド入力部
１４０…ＧＰＳ
１５０…表示制御部
２００…サーバ
２１０…通信部
２２０…経路探索部
２３０…推定エンジン
２３２…基準建物設定部
２３４…境界画定部
２４０…経路案内部
２５０…地図ＤＢ
２５２…ネットワークデータ
２５４…描画データ
２６０…経路案内ＤＢ
【図１】
0004717650.tif 000002
【図２】
0004717650.tif 000003
【図３】
0004717650.tif 000004
【図４】
0004717650.tif 000005
【図５】
0004717650.tif 000006
【図６】
0004717650.tif 000007
【図７】
0004717650.tif 000008
【図８】
0004717650.tif 000009
【図９】
0004717650.tif 000010
【図１０】
0004717650.tif 000011