到達可能範囲表示装置および到達可能範囲表示方法ならびにそのプログラム
【課題】地図画像上に、信頼性および視認性の高い所定の時間以内に到達可能な範囲を重畳表示する到達可能範囲表示装置を提供する。
【解決手段】地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置である。到達可能範囲表示装置は、探索部、画像生成部、画像処理部および画像重畳部とを備える。探索部は、基準点から任意の地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する。画像生成部は、探索部によって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。画像処理部は、画像生成部によって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。画像重畳部は、画像処理部によって生成された第２画像を地図画像に重畳して表示画面に表示する。
【解決手段】地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置である。到達可能範囲表示装置は、探索部、画像生成部、画像処理部および画像重畳部とを備える。探索部は、基準点から任意の地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する。画像生成部は、探索部によって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。画像処理部は、画像生成部によって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。画像重畳部は、画像処理部によって生成された第２画像を地図画像に重畳して表示画面に表示する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、到達可能範囲表示装置および到達可能範囲表示方法ならびにそのプログラムに関し、より特定的には、地図画像上に、移動体が所定の位置（例えば、現在位置）から所定の時間以内に到達可能な範囲を示す画像を重畳表示する到達可能範囲表示装置および到達可能範囲表示方法ならびにそのプログラムに関するものである。
【背景技術】
【０００２】
従来、移動体が基準点（例えば、車両の現在位置）から一定時間内に到達可能な範囲を閉曲線で表示する到達可能範囲表示装置に関する技術が開示されている（例えば、特許文献１参照）。この到達可能範囲表示装置は、タクシー、警備会社などでの配車・指令システムに用いられ、車両を適正に表示、管理し、最適に配車・指令させることができる。
【０００３】
また、この到達可能範囲表示装置を適用したナビゲーション装置によれば、車両の現在位置から一定時間内に到達可能な交差点を探索し、その中から、車両の現在位置を中心に、方位を分割した領域ごとに車両の現在位置から最も遠い交差点を表示ノードとして抽出する。さらに、分割領域ごとに抽出された表示ノードを結ぶ線（閉曲線）を地図画像上に重畳表示することができる。
【特許文献１】特開平１１−１６０９４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記特許文献１に記載される従来の到達可能範囲表示装置においては、上記車両の現在位置を中心に方位を分割した領域ごとに、車両の現在位置から最も遠い交差点を検索する前に、ユーザが何分割にするかを車両の現在位置を中心に方位を複数に分割する。この場合、ユーザが事前に何分割にするかを設定する必要があり、システム稼動まで手間がかかるという問題を有していた。
【０００５】
また、車両の現在位置を中心に方位を分割する分割数が、小さい値（例えば４または８など）の場合には、高速に到達可能な範囲を示す閉曲線を地図画像上に重畳して表示するができる。この場合、到達可能範囲の信頼性が低下するという問題を有していた。ここで、信頼性の低下とは、到達可能範囲内部に時間外ノード（実際には到達できない交差点）が含まれてしまうことである。つまり、分割毎に抽出されたノードを結ぶ際、各ノードが結ばれて囲まれた範囲に時間外ノード（実際には到達できない交差点）が含まれてしまうことになり、重畳表示される到達可能範囲の信頼性が低下して、ユーザにとって不便であった。
【０００６】
また、分割数が、大きい値の場合には、所定の時間以内に到達できるノードが抽出されるので、到達可能な範囲を示す形状が滑らかな閉曲線ではなくがたがたとした閉曲線となり、視認性が悪いという問題を有していた。
【０００７】
それ故に本発明は、ユーザが事前に何分割にするかの設定することなく、信頼性および視認性の高い到達可能な範囲を示すことが可能な到達可能範囲表示装置および到達可能範囲表示方法ならびにそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、本発明は以下の構成を採用した。
第１の発明は、地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置である。到達可能範囲表示装置は、探索部、画像生成部、画像処理部および画像重畳部とを備える。探索部は、基準点から任意の地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する。画像生成部は、探索部によって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。画像処理部は、画像生成部によって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。画像重畳部は、画像処理部によって生成された第２画像を地図画像に重畳して表示画面に表示する。
【０００９】
第２の発明は、上記第１の発明において、画像生成部は、基準点から探索部によって探索された所定の時間以内に到達可能な地点群を所定色で示される第１画像を生成する。画像処理部は、所定色で示された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。
【００１０】
第３の発明は、上記第２の発明において、画像生成部は、基準点から探索部によって探索された所定の時間以内に到達可能な地点群を示す画素をそれぞれの周囲へ所定色の画素で太らせた第１画像を生成する。
【００１１】
第４の発明は、上記第２の発明において、画像生成部は、基準点から探索部によって探索された所定の時間以内に到達可能な地点群を示す画素のうち、基準点から探索部によって探索された所定の時間以内に到達不可能な地点群との境界にある画素をそれぞれの基準点側にのみ所定色で太らせ、当該境界以外の画素をそれぞれの周囲へ所定色の画素で太らせた第１画像を生成する。
【００１２】
第５の発明は、上記第２の発明において、画像生成部は、基準点から探索部によって探索された所定の時間以内に到達可能な地点群のそれぞれまでの経路を使い、所定色で示される第１画像を生成する。
【００１３】
第６の発明は、上記第５の発明において、画像生成部は、経路の道路種別に基づいて、当該経路を所定色で塗りつぶす太さを決定する。
【００１４】
第７の発明は、上記第１の発明において、画像生成部は、到達可能な地点群をその内部に全て含む地図上の領域内を第１の色で塗りつぶし、到達不可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、当該第１の色および当該第２の色の境界となる輪郭曲線を抽出する輪郭抽出部を含む。画像重畳部は、輪郭曲線を地図画像に重畳して表示画面に表示する。
【００１５】
第８の発明は、上記第７の発明において、輪郭抽出部は、第１の色を黒色および第２の色を白色として第１の色および第２の色の境界を抽出する。
【００１６】
第９の発明は、上記第７の発明において、輪郭抽出部は、所定の動的輪郭モデルを用いて、輪郭曲線を抽出する。
【００１７】
第１０の発明は、上記第９の発明において、探索部は、基準点を中心として所定の距離を半径とする円形状からなる領域を探索範囲として、基準点から当該探索範囲に存在する任意の複数の地点までの最適経路を探索して所要時間を算出する。輪郭抽出部は、探索部が用いた円形状の領域を、動的輪郭モデルを用いる際の初期状態の曲線とする。
【００１８】
第１１の発明は、上記第３の発明において、探索部は、基準点を中心とする所定範囲に存在する基準点から任意の地図画像上の任意の複数の地点までの経路の数に基づいて、道路密度を算出する道路密度算出部を、さらに含む。画像生成部は、道路密度算出部によって算出された道路密度の算出結果に基づいて、到達可能な地点群を示す画素をそれぞれの周囲へ所定色の画素で太らせる画素数を道路密度に基づいて決定する。
【００１９】
第１２の発明は、上記第１１の発明において、道路密度算出部は、基準点を中心とした所定範囲を、同心円状またはメッシュ状の領域に分割し、当該分割された領域ごとに存在する経路の数に基づいて、道路密度を算出する。
【００２０】
第１３の発明は、上記第１の発明において、画像生成部は、到達可能な地点群を示す画像と到達不可能な地点群を示す画像とを生成し、当該画像が重複する領域について所定の演算を行い、到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する論理演算部を含む。
【００２１】
第１４の発明は、上記第１３の発明において、論理演算部は、到達不可能な地点群を第１の色で塗りつぶし到達可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、到達不可能な地点群を第２の色で塗りつぶし到達可能な地点群を第１の色で塗りつぶした画像を生成し、当該２つの画像の論理積を用いて、到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。
【００２２】
上記目的を達成するために、本発明は以下のステップを採用した。
第１５の発明は、地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示方法である。到達可能範囲表示方法は、探索ステップ、画像生成ステップ、画像処理ステップおよび画像重畳ステップとを含んでいる。探索ステップは、基準点から任意の地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する。画像生成ステップは、探索ステップによって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。画像処理ステップは、画像生成ステップによって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。画像重畳ステップは、画像処理ステップによって生成された第２画像を前記地図画像に重畳して表示画面に表示する。
【００２３】
上記目的を達成するために、本発明は以下のステップを実行させるプログラムを採用した。
第１６の発明は、地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置のコンピュータで実行される到達可能範囲表示プログラムである。到達可能範囲表示プログラムは、コンピュータに、探索ステップ、画像生成ステップ、画像処理ステップおよび画像重畳ステップとを実行させる。探索ステップは、基準点から任意の地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する。画像生成ステップは、探索ステップによって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。画像処理ステップは、画像生成ステップによって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。画像重畳ステップは、画像処理ステップによって生成された第２画像を地図画像に重畳して表示画面に表示する。
【発明の効果】
【００２４】
上記第１の発明によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すことができる。その結果、ユーザはどこまでを何分で到達できるかを一目瞭然に把握することができる。
【００２５】
上記第２の発明によれば、所定の時間以内に到達可能な地点群を所定色で示される画像を地図画像上に重畳表示するので、視認性が高く、到達可能な範囲を一目瞭然に把握することができる。
【００２６】
上記第３の発明によれば、所定の時間以内に到達可能な地点群を示す画素をそれぞれの周囲へ所定色の画素で太らせた画像を生成するので、所定の時間以内に到達可能な地点群を１つの領域として得ることができる。
【００２７】
上記第４の発明によれば、所定の時間以内に到達可能な地点群を示す画素のうち、所定の時間以内に到達不可能な地点群との境界にある画素をそれぞれの基準点側にのみ所定色で太らせ、当該境界以外の画素をそれぞれの周囲へ所定色の画素で太らせた画像を生成するので、所定の時間以内に到達不可能な地点群を含まない信頼性の高い到達可能な範囲を得ることができる。
【００２８】
上記第５の発明によれば、所定の時間以内に到達可能な地点群だけでなく、到達可能な地点群のそれぞれまでの経路を使い、所定色で示された画像を生成するので、より詳細な到達可能な範囲を示す画像を得ることができる。
【００２９】
上記第６の発明によれば、経路毎の道路種別に基づいて、当該経路を所定色で塗りつぶす太さを決定するので、例えば、細街路は、太く表示されることで、到達可能な経路として一目瞭然に把握することができる。
【００３０】
上記第７の発明によれば、到達可能な地点群をその内部に全て含む地図上の領域内を第１の色で塗りつぶし、到達不可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、当該第１の色および当該第２の色の境界となる輪郭曲線を抽出し、抽出された輪郭曲線を地図画像に重畳して表示画面に表示する。
【００３１】
上記第８の発明によれば、第１の色を黒色および第２の色を白色として第１の色および第２の色の境界を抽出するので、データが２値化になることでデータ量を軽減することができる。
【００３２】
上記第９の発明によれば、所定の動的輪郭モデルを用いることで、容易に輪郭曲線を抽出することができる。
【００３３】
上記第１０の発明によれば、探索部が用いた円形状の領域を、動的輪郭モデルを用いる際の初期状態の曲線とするので、煩わしい操作を省略することができる。
【００３４】
上記第１１の発明によれば、到達可能な地点群を示す画素をそれぞれの周囲へ所定色の画素で太らせる画素数を道路密度に基づいて決定するので、例えば、道路密度が疎の場合でも、処理時間が短い時間で、所定の時間以内に到達可能な地点群を１つの領域として得ることができる。
【００３５】
上記第１２の発明によれば、同心円状またはメッシュ状に分割された領域ごとに存在する経路の数に基づいて、道路密度を算出するので、例えば、経路の数が少ない領域でも、太らせる画素数を塗りつぶすことができる。
【００３６】
上記第１３の発明によれば、到達可能な地点群を示す画像と到達不可能な地点群を示す画像とを生成し、当該画像が重複する領域について所定の演算を行い、生成された到達可能な地点群と到達不可能な地点群との区別が可能な画像は、到達不可能な地点群をさらに除外されているので、信頼性の高い到達可能な範囲を示す画像を得ることができる。
【００３７】
上記第１４の発明によれば、所定の演算に理論積を用いるので、処理時間が短い時間で、信頼性の高い到達可能な範囲を示す画像を得ることができる。
【００３８】
上記第１５の発明によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すことができる。
【００３９】
上記第１６の発明によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すプログラムを提供することができる。
【発明を実施するための最良の形態】
【００４０】
（第１の実施形態）
図１〜図１８を参照して、本発明における第１の実施形態に係る到達可能範囲表示装置について説明する。なお、第１の実施形態および後述する第２の実施形態においては、車両に搭載されるナビゲーション装置に本発明の到達可能範囲表示装置を適用した例について説明する。また、各図面において、本発明に関係のない構成要素は省略している。
【００４１】
まず、上記到達可能範囲表示装置の概要構成を説明する。図１において、ナビゲーション装置１は、制御部１１、地図情報格納部１２、測位部１３、入力部１４、出力部１５、交通情報受信部１６、およびワーキングエリア部１７を備えている。これらの各部は、内部バスによって接続されている。
【００４２】
制御部１１は、例えばＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＭＰＵ（Ｍｉｃｒｏ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）で構成される。また、制御部１１は、到達可能範囲表示装置を適用したナビゲーション装置１全体の動作等を制御する。制御部１１は、探索部１１１、画像生成部１１２、画像処理部１１３、および画像重畳部１１４を含む。制御部１１に含まれる各部の詳細については後述する。
【００４３】
ワーキングエリア部１７は、例えばＲＡＭなどで構成され、制御部１１によってデータの読み出しおよび書き込みが行われる。
【００４４】
地図情報格納部１２は、例えばＨＤＤ（Ｈａｒｄ Ｄｉｓｃ Ｄｒｉｖｅ）またはＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）などで構成される。地図情報格納部１２には、道路（リンク）の形状データおよび交差点（ノード）の位置データなどの地図情報が予め格納されている。ただし本発明はこれに限らず、地図情報は、図示しない通信手段（例えば、携帯電話またはＰＨＳ（Ｐｅｒｓｏｎａｌ Ｈａｎｄｙｐｈｏｎｅ Ｓｙｓｔｅｍ）など）を通じて、図示しないセンター設備から適宜ダウンロードして地図情報格納部１２に格納される構成であってもよい。
【００４５】
ここで、図２Ａ〜図２Ｃを参照して、地図情報格納部１２に格納される地図情報について説明する。地図情報格納部１２は、例えばノードデータ、リンクデータ、および道路種別データなどを格納している。なお、図２Ａ〜図２Ｃは、地図情報格納部１２に格納されている地図情報のうち、本実施形態に関連する地図情報の一部を抜粋した地図情報の一例を示す図である。
【００４６】
図２Ａは、交差点や合流地点など複数の方向に道路が分岐する地点（ノード）に関するノードデータである。ノードデータは、ノード毎に、緯度および経度などの位置情報、当該ノードに接続するリンクの数、およびリンクのＩＤから構成されている。図２Ｂは、ノードとノードを結ぶ道路を示すリンクデータである。リンクデータは、リンク毎に、リンクの端点である始点ノードおよび終点ノード、リンクの長さ（単位は、例えばメートルやキロメートルなど）、リンクの幅（単位は、例えばメートルなどで、道路幅を表す）、一般道路や高速道路などを示す道路種別から構成されている。なお、リンクデータには、車線数または通行規制の情報が含まれていてもよい。図２Ｃは、リンクデータの属性の１つである道路種別を数値付けしたものである。つまり、高速道路または一般道路といった道路種別ごとにそれぞれの値が設定されている。
【００４７】
また、地図情報格納部１２は、上述の地図情報だけでなく、海洋などを示す背景データ（以下、水系と称す）および陸地などを示す背景データ（以下、陸系と称す）などの情報を格納していてもよい。さらに、ファミリーレストランやガソリンスタンドの位置を管理する情報である施設情報などの情報も格納していてもよい。
【００４８】
測位部１３は、車両の現在位置、速度、および方位を検出する。例えば、測位部１３は、ＧＮＳＳ（Ｇｌｏｂａｌ Ｎａｖｉｇａｔｉｏｎ Ｓａｔｅｌｌｉｔｅ Ｓｙｓｔｅｍ）受信機、車速センサ、ジャイロ（角速度）センサ、および加速度センサなどの測位センサである。ＧＮＳＳ受信機は、例えばＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）受信機であり、複数の衛星からの電波を受信し、それを復調することで受信機の絶対位置（現在位置）を検出する。なお、現在位置、速度、および方位の測位は、ＧＮＳＳ受信機および各種センサを単独または複合利用して計測される。
【００４９】
入力部１４は、例えば所定数の押圧式のスイッチ、リモートコントローラー、タッチパネル、音声入力用のマイクと音声認識エンジンなどで構成され、ユーザの指示を受け付ける。ユーザによって入力される指示は、例えば目的地の設定、探索経路の選択、経路案内の開始、画面表示の切替などである。
【００５０】
出力部１５は、例えば液晶ディスプレイ、プラズマディスプレイ、有機ＥＬディスプレイなどで構成される表示装置１５１を含んでおり、ユーザに対して情報を表示する。具体的には、目的地への案内を示す地図画像を表示する。また、出力部１５は、後述する画像処理部１１３によって抽出された到達可能範囲を示す閉曲線を含む画像を地図画像に重畳して表示される。
【００５１】
交通情報受信部１６は、提供される交通渋滞情報を受信する。交通情報受信部１６は、提供される交通渋滞情報の種類（例えば、ＶＩＣＳ情報やプローブ情報など）に応じた受信装置であり、ＦＭ放送波、光／電波ビーコン、ＤＳＲＣ（Ｄｅｄｉｃａｔｅｄ Ｓｈｏｒｔ Ｒａｎｇｅ Ｃｏｍｍｕｎｉｃａｔｉｏｎ；狭帯域無線通信）受信機、および携帯電話などである。例えば、交通情報受信部１６が、携帯電話の場合、交通情報受信部１６は、他の車両から収集される位置、時刻等のデータを加工したうえで配信される高精度な交通渋滞情報（例えばプローブ情報）を受信することができる。ただし本発明はこれに限らず、交通渋滞情報は、過去の渋滞統計データ（例えば、過去の時間帯や曜日、日付などに応じた道路の混雑状況を表すデータ）を記憶した予測渋滞データベースを地図情報格納部１２に格納しておき、交通情報受信部１６は、地図情報格納部１２から交通渋滞情報を受け取ってもよい。ここで、交通情報は、上述のリンクデータにおけるリンク長の区間をどれだけの所要時間で通過できるかを表す情報であり、リンク長の区間における平均速度データなどが用いられて算出される。この交通情報を用いることによって、混雑度合いを加味した精度の高い所要時間を決定することができる。なお、本実施および後述の第２の実施の形態では、地図情報格納部１２は、予め予測渋滞データベースを格納している。
【００５２】
探索部１１１は、所要時間を算出する地点（交差点）を探索するための範囲および基準点から所用時間を算出する地点までの経路の道路種別などの探索条件を決定する。探索部１１１は、決定された探索範囲および道路種別などに基づいて、探索開始の基準点（以下、本実施および第２の実施の形態では、自車の現在位置を基準点とする）から、走行する可能性のあるすべての地点（交差点）までの所要時間を算出する。
【００５３】
ここで、探索部１１１によって決定される探索条件について説明する。通常のナビゲーション装置においては、ユーザにより指定された目的地までの所要時間を算出すればよく、探索の開始位置と終了位置（目的地）との間が探索範囲となる。一方、本実施および第２の実施の形態では、ユーザにより目的地が指定されていない場合であっても、到達可能な範囲を表示するために、探索部１１１は、適切な探索範囲を決定する。なお、探索範囲は、表示装置１５１に表示される地図領域を少なくとも含む範囲である。また、本実施および第２の実施の形態における、探索範囲は、出発地点を中心とし、出発地点から一定の距離を半径とする円を範囲とする。例えば、円の半径は、車両の平均車速に到達可能範囲を求める時間を乗じた値としてもよい。この場合、平均車速が５００ｍ／分、到達可能範囲を求める時間を１０分とすると、探索範囲の円の半径は、５０００ｍである。また、この円内に含まれる全てのノードを探索対象とする。また、通常のナビゲーション装置においては、ユーザにより指定された道路種別に基づいて、経路探索を行う。具体的には、ユーザは、一般道路優先または高速道路優先を指定する入力を行う。一方、本実施および第２の実施の形態では、ユーザにより目的地が指定されていない場合であっても、到達可能な範囲を表示するために、探索部１１１は、道路種別を決定する。例えば、現在選択されている道路種別を探索する道路種別とすることができる。その他にも、特願２００６−１１３１６８号公報に開示されているような従来の方法を用いてもよい。
【００５４】
また、探索部１１１は、各地点の所要時間を、上述したノードとリンクからなる道路ネットワークを探索開始の基準点から放射状に広げて算出する。このとき、探索範囲を放射状に広げていく際、探索対象のノード（以下、親ノードと称す。）に接続されるリンクを順番に辿っていくことで徐々に探索範囲を広げていく。また、探索方法としては、公知のダイクストラ法に代表される経路探索方法を用いることができるが、後述するリンクコスト加算処理に関して時間精度を増すための改良を必要とする。また、リンクコストの総和（累積時間）が、一定の時間を越えても探索を止めない。
【００５５】
画像生成部１１２は、探索部１１１による探索結果に基づいて、一定時間内に到達可能なノードおよび／またはリンクと対応する位置を表示する画像（本発明の第１画像に相当）を生成する。具体的には、画像生成部１１２は、所定サイズを第１の色で表示し、第１の色で表示された画像上に、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を第２の色で表示した画像を生成する。なお、生成された画像は、ワーキングエリア部１７に格納される。また、本実施および第２の実施形態を説明するために用いる各図において、第１の色は、黒色、第２の色は、白色で表示する。また、本実施および第２の実施形態では、第１の色を黒色、第２の色を白色として説明する。なお、第１および第２の色は、任意の色で、透過処理した色または半透明であってもよい。
【００５６】
画像処理部１１３は、画像生成部１１２によって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す画像（本発明の第２画像に相当）を生成する。また、画像処理部１１３は、画像生成部１１２によって生成された画像のうち、第１の色と第２の色の境界となる輪郭曲線を求める。また、求められた到達可能な範囲を示す輪郭曲線は、画像処理座標系において、任意の箇所を開始点として時計周りに１周する方向で、輪郭曲線の座標列が抽出される。ここで、画像処理座標系とは、左上隅を原点とし、右方向をＸ軸、下方向をＹ軸とする座標系である。なお、抽出された到達可能な範囲を示す輪郭曲線（閉曲線）の座標列データは、ワーキングエリア部１７に格納される。
【００５７】
画像重畳部１１４は、画像生成部１１２によって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す画像（本発明の第２画像に相当）、例えば画像処理部１１３によって抽出された到達可能な範囲を示す輪郭曲線（閉曲線）を地図画像に重畳する。
【００５８】
なお、探索部１１１、画像生成部１１２、画像処理部１１３は、センター設備（非図示）に配置する構成であってもよい。この場合には、ナビゲーション装置１は、図示しない通信手段（例えば、携帯電話）を通じて、到達可能範囲の輪郭データをセンター設備から適宜ダウンロードして表示装置１５１に表示する。
【００５９】
次に、以上のように構成されるナビゲーション装置１における動作について説明する。図３は、制御部１１全体の処理の流れを示すフローチャートである。
【００６０】
まず、図３において、探索部１１１は、探索の条件の決定を行う（ステップＳ１）。続いて、探索部１１１は、経路探索処理を行う（ステップＳ２）。続いて、画像生成部１１２は、到達可能な範囲を示す画像を生成する画像生成処理を行う（ステップＳ３）。続いて、画像処理部１１３は、画像生成部１１２によって生成された画像を処理し、到達可能範囲の輪郭を抽出する画像抽出処理を行う（ステップＳ４）。さらに、画像重畳部１１４は、到達可能な範囲を地図画像上に重畳する（ステップＳ５）。
【００６１】
次に、図４を参照して、ステップＳ２における経路探索処理の動作について説明する。なお、図４は、経路探索処理の動作を表すフローチャートである。
【００６２】
まず、図４において、探索部１１１は、探索条件が成立するすべてのノードを探索したかを判定する（ステップＳ２１）。判定の結果、探索部１１１がすべてのノードを探索していない（ステップＳ２１においてＮｏ）場合には、処理は、ステップＳ２２に進む。一方、探索部１１１が、すべてのノードを探索した（ステップＳ２１においてＹｅｓ）場合には、経路探索処理を終了する。
【００６３】
次に、ステップＳ２２において、探索部１１１は、親ノードに到達するまでの総時間コスト値（Ｔ１）を取得する。続いて、探索部１１１は、当該親ノードに接続する接続先ノードに至るリンクコスト（累積時間）を取得する（ステップＳ２３）。続くステップＳ２４において、探索部１１１は、現在時刻を取得する。現在時刻は、例えば、測位部１３のＧＰＳ受信機から取得されてもよい。続いて、探索部１１１は、現在時刻に上述の取得された親ノードに到達するまでの総時間コスト値（Ｔ１）を加算し、時刻Ｔ２を得る（ステップＳ２５）。続くステップ２６において、時刻Ｔ２における当該親ノードから接続先ノードに至るリンクの予測渋滞情報を要求する。続いて、探索部１１１は、地図情報格納部１２に予め格納されている予測渋滞データベースから予測渋滞情報を取得する（ステップＳ２７）。さらに、探索部１１１は、ステップＳ２３で求めたリンクコストにステップＳ２７で取得した予測渋滞情報を加味したリンク通過時間（Ｔ３）を算出する（ステップＳ２８）。続いて、Ｔ１にＴ３を加算した値を接続先ノードに至るまでの総時間コスト値（Ｔ４）が、ワーキングエリア部１７に格納される（ステップＳ２９）。なお、あるノードに到達する経路は複数存在するうち、最小の総時間コスト値（Ｔ４）となる経路が採用される。
【００６４】
上述の経路探索処理において、探索部１１１は、車両が親ノードから接続先ノードに至るリンクを通過するであろう時間帯における渋滞情報を考慮した経路探索を行うので、より正確な到達可能交差点を探索することができる。また、到達可能範囲を求める時間が長くなったとしても、算出される時間の精度をある程度の範囲内の誤差に抑えることができる。
【００６５】
次に、図５を参照して、ステップＳ３における画像生成処理の動作について説明する。なお、図５は、画像生成処理の動作を表すフローチャートである。
【００６６】
まず、図５において、画像生成部１１２は、黒色（本発明の第１の色に相当）からなる所定サイズの画像を生成する（ステップＳ３１）。ここで、所定サイズとは、表示装置１５１の画面サイズかそれより少し大きいサイズである。続くステップ３２において、画像生成部１１２は、上述の生成された黒色からなる所定サイズの画像に探索部１１１によって探索された一定の時間以内で到達可能なノードおよび／またはリンクを示す位置を白色（本発明の第２の色に相当）で塗りつぶす（図６または図７参照）。なお、図６は、黒色で所定サイズを塗りつぶし、所定の時間以内に到達可能なノードを示す位置を白色で塗りつぶした様子を示す図である。また、図７は、黒色で所定サイズを塗りつぶし、所定の時間以内に到達可能なノード及びリンクを示す位置を白色で塗りつぶした様子を示す図である。なお、図６から図７への差分が追加されたリンクの情報である。
【００６７】
ここで、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置の塗りつぶしは、ノードの座標（緯度経度）を上述の画像処理座標系に変換することで行う。また、変換後の画像処理座標を（Ｘ、Ｙ）とすると、その近傍（例えば、８近傍、２４近傍）を白色で塗りつぶすようにしても良い。なお、近傍の形状は四角や円、楕円、半円等を用いることができる。さらに、探索部１１１によって探索された所定の時間以内に到達可能なノードおよび／またはリンクが、出発地点からの距離が遠くなる程、白色で塗りつぶす近傍の数を増やすようにしても良い。また、表示装置１５１の画面のサイズ（解像度）に応じて、白色で塗りつぶす近傍の画素の数を可変するようにしてもよい。この場合、画面サイズ（解像度）が大きくなるほど、近傍の画素の数を多く塗るようにする。
【００６８】
また、図８の例のように、所定の時間以内に到達可能なノードを示す位置を塗りつぶし（図８の斜線部分の画素）、さらに、その近傍（例えば、８近傍、２４近傍）すべてを塗りつぶすのではなく、出発地点側（図８の点線矢印方向）にのみ塗りつぶす（図８の灰色部分の画素；本発明の第１の色に相当）ようにしてもよい。例えば、図８の例のような、所定の時間以内に到達可能なノードが、最も遠い地点の場合、当該地点（図８の斜線部分の画素）に対して、出発地点と反対側を含まない（図８の白色部分の画素；本発明の第２の色に相当）ので、より信頼性の高い到達可能な範囲を示す領域を得ることができる。
【００６９】
次に、図９および図１０を参照して、画像生成部１１２が所定の時間以内に到達可能な範囲を示す画像を生成する他の画像生成処理の動作について説明する。
【００７０】
まず、図９のステップＳ４１において、上述のステップＳ３１と同様に、画像生成部１１２は、黒色からなる所定サイズの画像を生成する。続いて、探索部１１１は、図１０に示す例のように、出発地点を中心に同心円状に地図画像を分割して、探索範囲内の道路密度を算出する（ステップＳ４２）。なお、図１０は、同心円状に地図画像を分割する方法の一例を示す模式図である。ここで、道路密度とは、同心円状に分割された一つの領域におけるノードおよび／またはリンクの数とする。すなわち、ノードおよび／またはリンクの数が、所定の閾値未満の場合には、道路密度は「疎」であり、ノードおよび／またはリンクの数が、所定の閾値以上の場合には、道路密度は「密」となる。なお、閾値は、同心円が大きくなるにつれて増減してもよい。また、上述の図２Ｃの道路種別に基づいて、白色で塗りつぶす近傍の画素の数を可変するようにしてもよい。例えば、道路種別が、細街路から高速道路になるにつれて、道路密度は、疎になっていく。この場合、道路種別の値が小さくなるにつれて、近傍の画素の数を多く塗るようにする。
【００７１】
続く、ステップＳ４３において、探索部１１１によって算出された道路密度の疎密に基づいて、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で塗りつぶす。ここで、道路密度が疎の場合には、所定の時間以内に到達可能なノード及び／又はリンクを示す位置の多くの近傍を白色で塗りつぶす。なお、出発地点を中心に同心円状に地図を分割するとしたが、これに限らずメッシュ状（小さい矩形）に分割するようにしてもよい。また、地図画像をメッシュ状に分割する場合には、算出された道路密度の閾値は、一定値でかまわない。また、地図画像を同心円状またはメッシュ状に分割しない場合、隣接する各ノード間の距離から道路密度を判定するようにしてもよい。この場合、隣接する各ノード間の距離が、所定の閾値より長いほど疎と判定する。
【００７２】
次に、図１１を参照して、図３のステップＳ４における画像抽出処理の動作について説明する。なお、図１１は、画像抽出処理の動作を表すフローチャートである。
【００７３】
まず、図１１において、図３のステップＳ３の画像生成処理で生成された画像のうち、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で表示される部分の内部の黒色で表示される部分である隙間を埋める処理を行う（ステップＳ５１）。ただし、所定の時間以内に到達不可能なノードおよび／またはリンク、つまり黒色で表示される領域は、隙間としない。ここで、隙間を埋める処理とは、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で表示され、当該白色で表示された隣接するノードおよび／またはリンクの間で、黒色で表示される部分である隙間を白色に表示する処理である。また、この処理は白色で表示された位置の領域の膨張または収縮を繰り返して行う。具体的には、図１２の例のように、図６の例のような画像から隙間を埋める処理を行う。なお、隙間を埋める処理は、公知の方法を用いてかまわない。
【００７４】
ここで、白色で示される隣接するノードおよび／またはリンクの間隔が、図６の例のように、狭い場合、生成される画像は、図１２の例のように、所定の時間以内に到達可能な範囲が一つの領域として抽出される。一方、白色で示される隣接するノードおよび／またはリンクの間隔が、広い場合、生成される画像は、図１２の例のようにならず、例えば所定の時間以内に到達可能な範囲が二つ以上の領域として抽出される。この場合、上述した道路密度に基づいて、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で塗りつぶす大きさ（太さ）を可変する処理を用いるようにしてもよい。また、道路密度に応じて、白色で表示された位置の領域の膨張または収縮を繰り返してもよい。例えば、道路密度が、疎の場合、隣接する白色で示される画素どうしの距離を大きくとるようにする。これにより、所定の時間以内に到達可能な範囲が一つの領域として抽出される。また、出発地点から所定の時間以内に到達可能なノードおよび／またはリンクまでの距離に基づいて、白色で表示された位置の領域の膨張または収縮を繰り返してもよい。また、画面サイズ（解像度）に基づいて、白色で表示された位置の領域の膨張または収縮を繰り返してもよい。また、地図画像の水系および陸系を考慮して、白色で表示された位置の領域の膨張または収縮を繰り返してもよい。例えば、水系にかかる方向へは、膨張不可にし、陸系にかかる方向へは、膨張可能にする。これにより、所定の時間以内に到達可能な範囲が一つの領域として抽出される。
【００７５】
次に、ステップＳ５２において、ステップＳ５１で生成された画像のうち、白色と黒色の境界線を滑らかにする処理を行う。具体的には、図１３の例のように、図１２の例のような画像から白色と黒色の境界線を滑らかにする処理を行う。これにより、図１３の例のように、白色と黒色の境界線を滑らかに処理することで、最終的に到達可能な範囲を地図画像に重畳した画像の視認性を向上させることができる。なお、滑らかにする処理は、公知の方法を用いてかまわない。
【００７６】
続くステップＳ５３において、ステップＳ５２で生成された画像のうち、白色と黒色の境界となる輪郭曲線を抽出する。具体的には、図１４の例のように、図１３の例のような画像から白色と黒色の境界となる輪郭曲線３０２を抽出する処理を行う。なお、輪郭曲線を抽出する処理は、公知の方法を用いてかまわない。なお、図１５は、到達可能な範囲を示す輪郭曲線の表示例である。また、任意の箇所を開始点として時計周りに１周する方向で、輪郭曲線の座標列が抽出される。また、抽出された輪郭曲線座標列は、図１５の例のように、「開始Ｘ座標、開始Ｙ座標」から「終了Ｘ座標、終了Ｙ座標」で格納される。なお、抽出された輪郭曲線座標列はワーキングエリア部１７に格納される。
【００７７】
次に、図３のステップ５において、画像重畳部１１４は、ステップＳ５３で求められた輪郭曲線３０２を地図画像３００に重畳する。なお、図１６は、到達可能な範囲を示す輪郭曲線を地図画像に重畳して表示装置１５１に表示される表示例である。
【００７８】
次に、図１７および図１８を参照して、画像処理部１１３が、動的輪郭モデルを用いて、所定の時間以内に到達可能な範囲を示す輪郭曲線を求める他の画像生成処理の動作について説明する。なお、図１７は、他の画像抽出処理の動作を表すフローチャートである。
【００７９】
まず、図１７において、ステップＳ６１およびＳ６２は、図１１のステップＳ５１およびＳ５２と同様にして画像を処理しているので、その説明を省略する。
【００８０】
続くステップＳ６３において、画像処理部１１３は、動的輪郭モデル（Ｍ．Ｋａｓｓ：“Ｓｎａｋｅｓ：Ａｃｔｉｖｅ Ｃｏｎｔｏｕｒ Ｍｏｄｅｌｓ”，Ｉｎｔｅｍａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ，１，４，ｐｐ．３２１−３３１（１９８８））を用いて、所定の時間以内に到達可能な範囲を示す輪郭曲線を抽出する。ここで、動的輪郭モデルでは、まず、初期状態の曲線を設定し、エネルギーを最小化するように曲線を逐次変形する。これにより、最終状態の曲線を到達可能な範囲を示す輪郭として取り出す。なお、エネルギーは、エッジに滑らかに引き寄せるための関数として定義することができる。また、逐次修正法としては、例えば、変分法、Ｇｒｅｅｄｙ Ａｌｇｏｒｉｔｈｍ、または動的計画法をもちいてもよい。
【００８１】
次に、図１８を参照して、ステップ６３における動的輪郭モデルを用いた場合の輪郭を抽出する際の、曲線の逐次変形について説明する。なお、図１８は、図１７のステップ６３において動的輪郭モデルを適用した場合の曲線が初期状態から最終状態へ逐次変形の様子の一例を示す模式図である。
【００８２】
図１８において、曲線４００は初期状態を示し、曲線４０１は途中状態を示し、曲線４０２は最終状態を示している。初期状態の曲線４００は、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で示されている領域より大きな閉曲線であればどのような形状でもよい。例えば、自動的に設定する場合には、探索部１１１が探索範囲として設定する円形状を初期状態の曲線としてもよい。具体的には、探索範囲が出発地点を中心として半径５０００ｍの円とすると、その円形状を画像処理座標系へ変換し配置する。また、最終状態の曲線４０２についても、上述の図１５の例のように、輪郭曲線座標列が抽出されて、ワーキングエリア部１７に格納される。その結果、画像重畳部１１４は、動的輪郭モデルを用いて求められた輪郭曲線を地図画像に重畳して、表示装置１５１に表示される。
【００８３】
以上のように、本実施形態に係る到達可能範囲表示装置によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すことができる。その結果、ユーザはどこまでを何分で到達できるかを一目瞭然に把握することができる。
【００８４】
（第２の実施形態）
次に、第２の実施形態に係る到達可能範囲表示装置について説明する。なお、第２の実施形態においても第１の実施形態と同様、到達可能範囲表示装置の一例として、車両を目的地まで案内するナビゲーション装置に本発明を適用した例について説明する。また、第２の実施形態における到達可能範囲表示装置の構成は、第１の実施形態におけるナビゲーション装置１と同じ構成であるので、詳細な説明を省略する。第２の実施形態においては、到達可能範囲表示装置において所定の時間以内に到達可能な範囲の探索処理を行う際の探索方法および表示画面に関して主に説明する。
【００８５】
まず、探索部１１１によって所定の時間以内に到達可能なノードおよび／またはリンクが探索されると、第１の実施形態と同様の、つまり図５および図１１のステップＳ５１およびＳ５２の処理が実行される。これにより、図１３の例のような、画像（以下、時間内画像と称す）が生成される。
【００８６】
一方、探索部１１１によって所定の時間を越えて到達可能なノードおよび／またはリンクが探索されると、図１９のステップＳ３１およびＳ３２の処理が実行される。これにより、図２０の例のような、画像が生成される。なお、図２０は、黒色で所定サイズを塗りつぶし、所定の時間を越えて探索範囲における到達可能なノード示す位置を白色で塗りつぶした画像の表示例である。ここで、探索部１１１が、所定の時間を越えて探索範囲における到達可能なノードの探索に関して、予め探索範囲の条件が設定されるので、図２０の例のように、出発地点（画像中央）からすべての方向に対して探索が制限される。
【００８７】
次に、図２１を参照して、図２０における画像抽出処理の動作について説明する。なお、図２１は、画像抽出処理の動作を表すフローチャートである。
【００８８】
まず、図２１において、図２０の例のように生成された画像のうち、所定の時間を越えて到達可能なノードおよび／またはリンクを示す位置を白色で表示される部分の内部の黒色で表示される部分である隙間を埋める処理を行う（ステップＳ８１）。ただし、図２０において、所定の時間以内に到達可能なノードおよび／またはリンク、つまり黒色で表示される領域は、隙間としない。具体的には、図２２の例のように、図２０の例のような画像から隙間を埋める処理を行う。なお、隙間を埋める処理とは、上述した方法と同様である。
【００８９】
次に、ステップＳ８２において、ステップＳ８１で生成された画像のうち、白色と黒色の境界線を滑らかにする処理を行う。具体的には、図２３の例のように、図２２の例のような画像から白色と黒色の境界線を滑らかにする処理を行う。なお、滑らかにする処理は、上述した方法と同様である。
【００９０】
次に、ステップＳ８３において、画像生成部１１２は、ステップＳ８２で生成された画像のうち、白黒反転させた画像（以下、時間外画像と称す）を生成する。具体的には、図２４の例のように、図２３の例のような画像から白色と黒色とを反転させる。
【００９１】
続いて、図１１および図２１の処理を実行して得られた２つの画像の論理積を取り、時間内画像の白色の領域と時間外画像の白色の領域の重なり領域を抽出する。具体的には、図１３において白色で示した領域と、図２４において白色で示した領域とが重なる領域を抽出する。その結果、画像生成部１１２は、図２５の例のような画像を生成する。
【００９２】
次に、時間内画像の白色の領域と時間外画像の白色の領域の重なり領域の論理積を取り、生成された図２５の例のような画像のうち、白色と黒色の境界となる輪郭曲線を抽出する。具体的には、図２６の例のように、図２５の例のような画像から白色と黒色の境界となる輪郭曲線５０２を抽出する処理を行う。なお、輪郭曲線を抽出する処理は、上述した方法と同様である。なお、任意の箇所を開始点として時計周りに１周する方向で、輪郭曲線５０２の座標列が抽出される。また、抽出された輪郭曲線座標列はワーキングエリア部１７に格納される。
【００９３】
次に、画像重畳部１１４は、上述で求められた輪郭曲線５０２を地図画像５００に重畳する。なお、図２７は、到達可能な範囲を示す輪郭曲線５０２を地図画像５００に重畳して表示装置１５１に表示される表示例である。また、図１６で示した到達可能な範囲を示す輪郭曲線３０２と図２７で示す到達可能な範囲を示す輪郭曲線５０２と対比すると、輪郭曲線５０２は、輪郭曲線３０２よりも若干縮んでいる。つまり、到達可能な範囲を示す輪郭曲線５０２では、到達可能な範囲を示す輪郭曲線３０２内部に存在する所定の時間を越えて到達可能なノードを排除している。その結果、より信頼性の高い到達可能範囲表示を行うことができる。
【００９４】
以上のように、本実施形態に係る到達可能範囲表示装置によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すことができる。その結果、ユーザはどこまでを何分で到達できるかを一目瞭然に把握することができる。
【００９５】
また、上記第１の実施形態および第２の実施形態において、所定の時間以内に到達可能な範囲を示す輪郭曲線を地図画像に重畳するようにしたが、本発明はこれに限らず、図６または図７の所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で表示された領域を地図画像に重畳するようにしてもよい。また、白色で表示される領域または部分の色は、任意の色を用いてもよい。さらに、透過処理を施すようにしても構わない。
【００９６】
また、上記第１の実施形態および第２の実施形態において、画像生成部１１２は、地図画像を陸系と水系に分け、陸系を白色、水系を黒色とする画像を生成し、上述した図１３および図２５の画像から論理積を取り、到達可能な範囲を示す輪郭曲線を求めるようにしてもよい。なお、図２８Ａは、上記第１の実施形態および第２の実施形態における図１３又は図２７で示した画像と同様である。図２８Ｂは、陸系を白色、水系を黒色とした様子を示す図である。例えば、上記第１の実施形態および第２の実施形態と同様にして、図２８Ａと図２８Ｂのから論理積を取る。その結果、画像生成部１１２は、図２８Ｃの例のような画像を生成する。さらに、図２８Ｃの画像から上記第１の実施形態および第２の実施形態と同様にして、輪郭曲線を求める。これにより、到達可能な範囲を示す輪郭曲線は、常に陸系の範囲に描かれ、さらに、信頼性の高い到達可能範囲表示を行うことができる。
【００９７】
以上、本発明を詳細に説明したが、上記説明はあらゆる意味において例示的なものであり限定的なものではない。本発明の範囲から逸脱することなしに多くの他の改変例及び変形例が可能であることは言うまでもない。
【産業上の利用可能性】
【００９８】
本発明に係る到達可能範囲表示装置および到達可能範囲表示方法ならびにそのプログラムは、ナビゲーション装置やパーソナルコンピュータ上で動作する地図表示アプリケーション、携帯電話、タクシー、警備会社等での配車・指令システム等、地図を表示可能なあらゆる機器、システムに対して適用可能である。
【図面の簡単な説明】
【００９９】
【図１】第１の実施形態に係るナビゲーション装置の構成を示す機能
【図２Ａ】第１の実施形態に係る地図情報格納部１２に格納される地図情報のうち、ノードデータの一例を示す図
【図２Ｂ】第１の実施形態に係る地図情報格納部１２に格納される地図情報のうち、リンクデータの一例を示す図
【図２Ｃ】第１の実施形態に係る地図情報格納部１２に格納される地図情報のうち、道路種別の一例を示す図
【図３】制御部１１全体の処理の流れを示すフローチャート
【図４】経路探索処理の動作を表すフローチャート
【図５】本発明の第１の実施形態における画像生成処理の動作を表すフローチャート
【図６】黒色で所定サイズを塗りつぶし、所定の時間以内に到達可能なノードを示す位置を白色で塗りつぶした様子を示す図
【図７】黒色で所定サイズを塗りつぶし、所定の時間以内に到達可能なノード及びリンクを示す位置を白色で塗りつぶした様子を示す図
【図８】所定の時間以内に到達可能なノードの近傍を塗りつぶす位置を説明するための図
【図９】他の画像生成処理の動作を表すフローチャート
【図１０】同心円状に地図画像を分割する方法の一例を示す模式図
【図１１】本発明の第１の実施形態における画像抽出処理の動作を表すフローチャート
【図１２】図６を隙間を埋める処理した様子を示す図
【図１３】図１２の白色と黒色の境界を滑らかにする処理をした様子を示す図
【図１４】図１３の白色と黒色の境界となる輪郭曲線を抽出した様子を示す図
【図１５】輪郭曲線座標列の格納形式の一例を示す模式図
【図１６】本発明の第１の実施形態における到達可能な範囲を示す輪郭曲線を地図画像に重畳して表示装置１５１に表示される表示例
【図１７】他の画像抽出処理の動作を表すフローチャート
【図１８】動的輪郭モデルを適用した場合の曲線が初期状態から最終状態へ逐次変形の様子の一例を示す模式図
【図１９】本発明の第２の実施形態における画像生成処理の動作を表すフローチャート
【図２０】黒色で所定サイズを塗りつぶし、所定の時間を越えて到達可能なノードを示す位置を白色で塗りつぶした様子を示す図
【図２１】本発明の第２の実施形態における画像抽出処理の動作を表すフローチャート
【図２２】図２１を隙間を埋める処理した様子を示す図
【図２３】図２２の白色と黒色の境界を滑らかにする処理をした様子を示す図
【図２４】図２２の白色と黒色とを反転させる処理をした様子を示す図
【図２５】図１３と図２４との画像から理論積をした様子を示す図
【図２６】図２５の白色と黒色の境界となる輪郭曲線を抽出した様子を示す図
【図２７】本発明の第２の実施形態における到達可能な範囲を示す輪郭曲線を地図画像に重畳して表示装置１５１に表示される表示例
【図２８Ａ】図１２の白色と黒色の境界を滑らかにする処理をした様子を示す図
【図２８Ｂ】陸系を白色、水系を黒色とした様子を示す図
【図２８Ｃ】図２８Ａと図２８Ｂとの画像から理論積をした様子を示す図
【符号の説明】
【０１００】
１ ナビゲーション装置
１１ 制御部
１２ 地図情報格納部
１３ 測位部
１４ 入力部
１５ 出力部
１６ 交通情報受信部
１７ ワーキングエリア部
１１１ 探索部
１１２ 画像生成部
１１３ 画像処理部
１１４ 画像重畳部
１５１ 表示装置
３００、５００ 地図画像
３０２、５０２ 輪郭曲線
４００ 初期状態を示す曲線
４０１ 途中状態を示す曲線
４０２ 最終状態を示す曲線
【技術分野】
【０００１】
本発明は、到達可能範囲表示装置および到達可能範囲表示方法ならびにそのプログラムに関し、より特定的には、地図画像上に、移動体が所定の位置（例えば、現在位置）から所定の時間以内に到達可能な範囲を示す画像を重畳表示する到達可能範囲表示装置および到達可能範囲表示方法ならびにそのプログラムに関するものである。
【背景技術】
【０００２】
従来、移動体が基準点（例えば、車両の現在位置）から一定時間内に到達可能な範囲を閉曲線で表示する到達可能範囲表示装置に関する技術が開示されている（例えば、特許文献１参照）。この到達可能範囲表示装置は、タクシー、警備会社などでの配車・指令システムに用いられ、車両を適正に表示、管理し、最適に配車・指令させることができる。
【０００３】
また、この到達可能範囲表示装置を適用したナビゲーション装置によれば、車両の現在位置から一定時間内に到達可能な交差点を探索し、その中から、車両の現在位置を中心に、方位を分割した領域ごとに車両の現在位置から最も遠い交差点を表示ノードとして抽出する。さらに、分割領域ごとに抽出された表示ノードを結ぶ線（閉曲線）を地図画像上に重畳表示することができる。
【特許文献１】特開平１１−１６０９４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記特許文献１に記載される従来の到達可能範囲表示装置においては、上記車両の現在位置を中心に方位を分割した領域ごとに、車両の現在位置から最も遠い交差点を検索する前に、ユーザが何分割にするかを車両の現在位置を中心に方位を複数に分割する。この場合、ユーザが事前に何分割にするかを設定する必要があり、システム稼動まで手間がかかるという問題を有していた。
【０００５】
また、車両の現在位置を中心に方位を分割する分割数が、小さい値（例えば４または８など）の場合には、高速に到達可能な範囲を示す閉曲線を地図画像上に重畳して表示するができる。この場合、到達可能範囲の信頼性が低下するという問題を有していた。ここで、信頼性の低下とは、到達可能範囲内部に時間外ノード（実際には到達できない交差点）が含まれてしまうことである。つまり、分割毎に抽出されたノードを結ぶ際、各ノードが結ばれて囲まれた範囲に時間外ノード（実際には到達できない交差点）が含まれてしまうことになり、重畳表示される到達可能範囲の信頼性が低下して、ユーザにとって不便であった。
【０００６】
また、分割数が、大きい値の場合には、所定の時間以内に到達できるノードが抽出されるので、到達可能な範囲を示す形状が滑らかな閉曲線ではなくがたがたとした閉曲線となり、視認性が悪いという問題を有していた。
【０００７】
それ故に本発明は、ユーザが事前に何分割にするかの設定することなく、信頼性および視認性の高い到達可能な範囲を示すことが可能な到達可能範囲表示装置および到達可能範囲表示方法ならびにそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、本発明は以下の構成を採用した。
第１の発明は、地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置である。到達可能範囲表示装置は、探索部、画像生成部、画像処理部および画像重畳部とを備える。探索部は、基準点から任意の地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する。画像生成部は、探索部によって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。画像処理部は、画像生成部によって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。画像重畳部は、画像処理部によって生成された第２画像を地図画像に重畳して表示画面に表示する。
【０００９】
第２の発明は、上記第１の発明において、画像生成部は、基準点から探索部によって探索された所定の時間以内に到達可能な地点群を所定色で示される第１画像を生成する。画像処理部は、所定色で示された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。
【００１０】
第３の発明は、上記第２の発明において、画像生成部は、基準点から探索部によって探索された所定の時間以内に到達可能な地点群を示す画素をそれぞれの周囲へ所定色の画素で太らせた第１画像を生成する。
【００１１】
第４の発明は、上記第２の発明において、画像生成部は、基準点から探索部によって探索された所定の時間以内に到達可能な地点群を示す画素のうち、基準点から探索部によって探索された所定の時間以内に到達不可能な地点群との境界にある画素をそれぞれの基準点側にのみ所定色で太らせ、当該境界以外の画素をそれぞれの周囲へ所定色の画素で太らせた第１画像を生成する。
【００１２】
第５の発明は、上記第２の発明において、画像生成部は、基準点から探索部によって探索された所定の時間以内に到達可能な地点群のそれぞれまでの経路を使い、所定色で示される第１画像を生成する。
【００１３】
第６の発明は、上記第５の発明において、画像生成部は、経路の道路種別に基づいて、当該経路を所定色で塗りつぶす太さを決定する。
【００１４】
第７の発明は、上記第１の発明において、画像生成部は、到達可能な地点群をその内部に全て含む地図上の領域内を第１の色で塗りつぶし、到達不可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、当該第１の色および当該第２の色の境界となる輪郭曲線を抽出する輪郭抽出部を含む。画像重畳部は、輪郭曲線を地図画像に重畳して表示画面に表示する。
【００１５】
第８の発明は、上記第７の発明において、輪郭抽出部は、第１の色を黒色および第２の色を白色として第１の色および第２の色の境界を抽出する。
【００１６】
第９の発明は、上記第７の発明において、輪郭抽出部は、所定の動的輪郭モデルを用いて、輪郭曲線を抽出する。
【００１７】
第１０の発明は、上記第９の発明において、探索部は、基準点を中心として所定の距離を半径とする円形状からなる領域を探索範囲として、基準点から当該探索範囲に存在する任意の複数の地点までの最適経路を探索して所要時間を算出する。輪郭抽出部は、探索部が用いた円形状の領域を、動的輪郭モデルを用いる際の初期状態の曲線とする。
【００１８】
第１１の発明は、上記第３の発明において、探索部は、基準点を中心とする所定範囲に存在する基準点から任意の地図画像上の任意の複数の地点までの経路の数に基づいて、道路密度を算出する道路密度算出部を、さらに含む。画像生成部は、道路密度算出部によって算出された道路密度の算出結果に基づいて、到達可能な地点群を示す画素をそれぞれの周囲へ所定色の画素で太らせる画素数を道路密度に基づいて決定する。
【００１９】
第１２の発明は、上記第１１の発明において、道路密度算出部は、基準点を中心とした所定範囲を、同心円状またはメッシュ状の領域に分割し、当該分割された領域ごとに存在する経路の数に基づいて、道路密度を算出する。
【００２０】
第１３の発明は、上記第１の発明において、画像生成部は、到達可能な地点群を示す画像と到達不可能な地点群を示す画像とを生成し、当該画像が重複する領域について所定の演算を行い、到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する論理演算部を含む。
【００２１】
第１４の発明は、上記第１３の発明において、論理演算部は、到達不可能な地点群を第１の色で塗りつぶし到達可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、到達不可能な地点群を第２の色で塗りつぶし到達可能な地点群を第１の色で塗りつぶした画像を生成し、当該２つの画像の論理積を用いて、到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。
【００２２】
上記目的を達成するために、本発明は以下のステップを採用した。
第１５の発明は、地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示方法である。到達可能範囲表示方法は、探索ステップ、画像生成ステップ、画像処理ステップおよび画像重畳ステップとを含んでいる。探索ステップは、基準点から任意の地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する。画像生成ステップは、探索ステップによって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。画像処理ステップは、画像生成ステップによって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。画像重畳ステップは、画像処理ステップによって生成された第２画像を前記地図画像に重畳して表示画面に表示する。
【００２３】
上記目的を達成するために、本発明は以下のステップを実行させるプログラムを採用した。
第１６の発明は、地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置のコンピュータで実行される到達可能範囲表示プログラムである。到達可能範囲表示プログラムは、コンピュータに、探索ステップ、画像生成ステップ、画像処理ステップおよび画像重畳ステップとを実行させる。探索ステップは、基準点から任意の地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する。画像生成ステップは、探索ステップによって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する。画像処理ステップは、画像生成ステップによって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する。画像重畳ステップは、画像処理ステップによって生成された第２画像を地図画像に重畳して表示画面に表示する。
【発明の効果】
【００２４】
上記第１の発明によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すことができる。その結果、ユーザはどこまでを何分で到達できるかを一目瞭然に把握することができる。
【００２５】
上記第２の発明によれば、所定の時間以内に到達可能な地点群を所定色で示される画像を地図画像上に重畳表示するので、視認性が高く、到達可能な範囲を一目瞭然に把握することができる。
【００２６】
上記第３の発明によれば、所定の時間以内に到達可能な地点群を示す画素をそれぞれの周囲へ所定色の画素で太らせた画像を生成するので、所定の時間以内に到達可能な地点群を１つの領域として得ることができる。
【００２７】
上記第４の発明によれば、所定の時間以内に到達可能な地点群を示す画素のうち、所定の時間以内に到達不可能な地点群との境界にある画素をそれぞれの基準点側にのみ所定色で太らせ、当該境界以外の画素をそれぞれの周囲へ所定色の画素で太らせた画像を生成するので、所定の時間以内に到達不可能な地点群を含まない信頼性の高い到達可能な範囲を得ることができる。
【００２８】
上記第５の発明によれば、所定の時間以内に到達可能な地点群だけでなく、到達可能な地点群のそれぞれまでの経路を使い、所定色で示された画像を生成するので、より詳細な到達可能な範囲を示す画像を得ることができる。
【００２９】
上記第６の発明によれば、経路毎の道路種別に基づいて、当該経路を所定色で塗りつぶす太さを決定するので、例えば、細街路は、太く表示されることで、到達可能な経路として一目瞭然に把握することができる。
【００３０】
上記第７の発明によれば、到達可能な地点群をその内部に全て含む地図上の領域内を第１の色で塗りつぶし、到達不可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、当該第１の色および当該第２の色の境界となる輪郭曲線を抽出し、抽出された輪郭曲線を地図画像に重畳して表示画面に表示する。
【００３１】
上記第８の発明によれば、第１の色を黒色および第２の色を白色として第１の色および第２の色の境界を抽出するので、データが２値化になることでデータ量を軽減することができる。
【００３２】
上記第９の発明によれば、所定の動的輪郭モデルを用いることで、容易に輪郭曲線を抽出することができる。
【００３３】
上記第１０の発明によれば、探索部が用いた円形状の領域を、動的輪郭モデルを用いる際の初期状態の曲線とするので、煩わしい操作を省略することができる。
【００３４】
上記第１１の発明によれば、到達可能な地点群を示す画素をそれぞれの周囲へ所定色の画素で太らせる画素数を道路密度に基づいて決定するので、例えば、道路密度が疎の場合でも、処理時間が短い時間で、所定の時間以内に到達可能な地点群を１つの領域として得ることができる。
【００３５】
上記第１２の発明によれば、同心円状またはメッシュ状に分割された領域ごとに存在する経路の数に基づいて、道路密度を算出するので、例えば、経路の数が少ない領域でも、太らせる画素数を塗りつぶすことができる。
【００３６】
上記第１３の発明によれば、到達可能な地点群を示す画像と到達不可能な地点群を示す画像とを生成し、当該画像が重複する領域について所定の演算を行い、生成された到達可能な地点群と到達不可能な地点群との区別が可能な画像は、到達不可能な地点群をさらに除外されているので、信頼性の高い到達可能な範囲を示す画像を得ることができる。
【００３７】
上記第１４の発明によれば、所定の演算に理論積を用いるので、処理時間が短い時間で、信頼性の高い到達可能な範囲を示す画像を得ることができる。
【００３８】
上記第１５の発明によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すことができる。
【００３９】
上記第１６の発明によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すプログラムを提供することができる。
【発明を実施するための最良の形態】
【００４０】
（第１の実施形態）
図１〜図１８を参照して、本発明における第１の実施形態に係る到達可能範囲表示装置について説明する。なお、第１の実施形態および後述する第２の実施形態においては、車両に搭載されるナビゲーション装置に本発明の到達可能範囲表示装置を適用した例について説明する。また、各図面において、本発明に関係のない構成要素は省略している。
【００４１】
まず、上記到達可能範囲表示装置の概要構成を説明する。図１において、ナビゲーション装置１は、制御部１１、地図情報格納部１２、測位部１３、入力部１４、出力部１５、交通情報受信部１６、およびワーキングエリア部１７を備えている。これらの各部は、内部バスによって接続されている。
【００４２】
制御部１１は、例えばＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＭＰＵ（Ｍｉｃｒｏ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）で構成される。また、制御部１１は、到達可能範囲表示装置を適用したナビゲーション装置１全体の動作等を制御する。制御部１１は、探索部１１１、画像生成部１１２、画像処理部１１３、および画像重畳部１１４を含む。制御部１１に含まれる各部の詳細については後述する。
【００４３】
ワーキングエリア部１７は、例えばＲＡＭなどで構成され、制御部１１によってデータの読み出しおよび書き込みが行われる。
【００４４】
地図情報格納部１２は、例えばＨＤＤ（Ｈａｒｄ Ｄｉｓｃ Ｄｒｉｖｅ）またはＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）などで構成される。地図情報格納部１２には、道路（リンク）の形状データおよび交差点（ノード）の位置データなどの地図情報が予め格納されている。ただし本発明はこれに限らず、地図情報は、図示しない通信手段（例えば、携帯電話またはＰＨＳ（Ｐｅｒｓｏｎａｌ Ｈａｎｄｙｐｈｏｎｅ Ｓｙｓｔｅｍ）など）を通じて、図示しないセンター設備から適宜ダウンロードして地図情報格納部１２に格納される構成であってもよい。
【００４５】
ここで、図２Ａ〜図２Ｃを参照して、地図情報格納部１２に格納される地図情報について説明する。地図情報格納部１２は、例えばノードデータ、リンクデータ、および道路種別データなどを格納している。なお、図２Ａ〜図２Ｃは、地図情報格納部１２に格納されている地図情報のうち、本実施形態に関連する地図情報の一部を抜粋した地図情報の一例を示す図である。
【００４６】
図２Ａは、交差点や合流地点など複数の方向に道路が分岐する地点（ノード）に関するノードデータである。ノードデータは、ノード毎に、緯度および経度などの位置情報、当該ノードに接続するリンクの数、およびリンクのＩＤから構成されている。図２Ｂは、ノードとノードを結ぶ道路を示すリンクデータである。リンクデータは、リンク毎に、リンクの端点である始点ノードおよび終点ノード、リンクの長さ（単位は、例えばメートルやキロメートルなど）、リンクの幅（単位は、例えばメートルなどで、道路幅を表す）、一般道路や高速道路などを示す道路種別から構成されている。なお、リンクデータには、車線数または通行規制の情報が含まれていてもよい。図２Ｃは、リンクデータの属性の１つである道路種別を数値付けしたものである。つまり、高速道路または一般道路といった道路種別ごとにそれぞれの値が設定されている。
【００４７】
また、地図情報格納部１２は、上述の地図情報だけでなく、海洋などを示す背景データ（以下、水系と称す）および陸地などを示す背景データ（以下、陸系と称す）などの情報を格納していてもよい。さらに、ファミリーレストランやガソリンスタンドの位置を管理する情報である施設情報などの情報も格納していてもよい。
【００４８】
測位部１３は、車両の現在位置、速度、および方位を検出する。例えば、測位部１３は、ＧＮＳＳ（Ｇｌｏｂａｌ Ｎａｖｉｇａｔｉｏｎ Ｓａｔｅｌｌｉｔｅ Ｓｙｓｔｅｍ）受信機、車速センサ、ジャイロ（角速度）センサ、および加速度センサなどの測位センサである。ＧＮＳＳ受信機は、例えばＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）受信機であり、複数の衛星からの電波を受信し、それを復調することで受信機の絶対位置（現在位置）を検出する。なお、現在位置、速度、および方位の測位は、ＧＮＳＳ受信機および各種センサを単独または複合利用して計測される。
【００４９】
入力部１４は、例えば所定数の押圧式のスイッチ、リモートコントローラー、タッチパネル、音声入力用のマイクと音声認識エンジンなどで構成され、ユーザの指示を受け付ける。ユーザによって入力される指示は、例えば目的地の設定、探索経路の選択、経路案内の開始、画面表示の切替などである。
【００５０】
出力部１５は、例えば液晶ディスプレイ、プラズマディスプレイ、有機ＥＬディスプレイなどで構成される表示装置１５１を含んでおり、ユーザに対して情報を表示する。具体的には、目的地への案内を示す地図画像を表示する。また、出力部１５は、後述する画像処理部１１３によって抽出された到達可能範囲を示す閉曲線を含む画像を地図画像に重畳して表示される。
【００５１】
交通情報受信部１６は、提供される交通渋滞情報を受信する。交通情報受信部１６は、提供される交通渋滞情報の種類（例えば、ＶＩＣＳ情報やプローブ情報など）に応じた受信装置であり、ＦＭ放送波、光／電波ビーコン、ＤＳＲＣ（Ｄｅｄｉｃａｔｅｄ Ｓｈｏｒｔ Ｒａｎｇｅ Ｃｏｍｍｕｎｉｃａｔｉｏｎ；狭帯域無線通信）受信機、および携帯電話などである。例えば、交通情報受信部１６が、携帯電話の場合、交通情報受信部１６は、他の車両から収集される位置、時刻等のデータを加工したうえで配信される高精度な交通渋滞情報（例えばプローブ情報）を受信することができる。ただし本発明はこれに限らず、交通渋滞情報は、過去の渋滞統計データ（例えば、過去の時間帯や曜日、日付などに応じた道路の混雑状況を表すデータ）を記憶した予測渋滞データベースを地図情報格納部１２に格納しておき、交通情報受信部１６は、地図情報格納部１２から交通渋滞情報を受け取ってもよい。ここで、交通情報は、上述のリンクデータにおけるリンク長の区間をどれだけの所要時間で通過できるかを表す情報であり、リンク長の区間における平均速度データなどが用いられて算出される。この交通情報を用いることによって、混雑度合いを加味した精度の高い所要時間を決定することができる。なお、本実施および後述の第２の実施の形態では、地図情報格納部１２は、予め予測渋滞データベースを格納している。
【００５２】
探索部１１１は、所要時間を算出する地点（交差点）を探索するための範囲および基準点から所用時間を算出する地点までの経路の道路種別などの探索条件を決定する。探索部１１１は、決定された探索範囲および道路種別などに基づいて、探索開始の基準点（以下、本実施および第２の実施の形態では、自車の現在位置を基準点とする）から、走行する可能性のあるすべての地点（交差点）までの所要時間を算出する。
【００５３】
ここで、探索部１１１によって決定される探索条件について説明する。通常のナビゲーション装置においては、ユーザにより指定された目的地までの所要時間を算出すればよく、探索の開始位置と終了位置（目的地）との間が探索範囲となる。一方、本実施および第２の実施の形態では、ユーザにより目的地が指定されていない場合であっても、到達可能な範囲を表示するために、探索部１１１は、適切な探索範囲を決定する。なお、探索範囲は、表示装置１５１に表示される地図領域を少なくとも含む範囲である。また、本実施および第２の実施の形態における、探索範囲は、出発地点を中心とし、出発地点から一定の距離を半径とする円を範囲とする。例えば、円の半径は、車両の平均車速に到達可能範囲を求める時間を乗じた値としてもよい。この場合、平均車速が５００ｍ／分、到達可能範囲を求める時間を１０分とすると、探索範囲の円の半径は、５０００ｍである。また、この円内に含まれる全てのノードを探索対象とする。また、通常のナビゲーション装置においては、ユーザにより指定された道路種別に基づいて、経路探索を行う。具体的には、ユーザは、一般道路優先または高速道路優先を指定する入力を行う。一方、本実施および第２の実施の形態では、ユーザにより目的地が指定されていない場合であっても、到達可能な範囲を表示するために、探索部１１１は、道路種別を決定する。例えば、現在選択されている道路種別を探索する道路種別とすることができる。その他にも、特願２００６−１１３１６８号公報に開示されているような従来の方法を用いてもよい。
【００５４】
また、探索部１１１は、各地点の所要時間を、上述したノードとリンクからなる道路ネットワークを探索開始の基準点から放射状に広げて算出する。このとき、探索範囲を放射状に広げていく際、探索対象のノード（以下、親ノードと称す。）に接続されるリンクを順番に辿っていくことで徐々に探索範囲を広げていく。また、探索方法としては、公知のダイクストラ法に代表される経路探索方法を用いることができるが、後述するリンクコスト加算処理に関して時間精度を増すための改良を必要とする。また、リンクコストの総和（累積時間）が、一定の時間を越えても探索を止めない。
【００５５】
画像生成部１１２は、探索部１１１による探索結果に基づいて、一定時間内に到達可能なノードおよび／またはリンクと対応する位置を表示する画像（本発明の第１画像に相当）を生成する。具体的には、画像生成部１１２は、所定サイズを第１の色で表示し、第１の色で表示された画像上に、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を第２の色で表示した画像を生成する。なお、生成された画像は、ワーキングエリア部１７に格納される。また、本実施および第２の実施形態を説明するために用いる各図において、第１の色は、黒色、第２の色は、白色で表示する。また、本実施および第２の実施形態では、第１の色を黒色、第２の色を白色として説明する。なお、第１および第２の色は、任意の色で、透過処理した色または半透明であってもよい。
【００５６】
画像処理部１１３は、画像生成部１１２によって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す画像（本発明の第２画像に相当）を生成する。また、画像処理部１１３は、画像生成部１１２によって生成された画像のうち、第１の色と第２の色の境界となる輪郭曲線を求める。また、求められた到達可能な範囲を示す輪郭曲線は、画像処理座標系において、任意の箇所を開始点として時計周りに１周する方向で、輪郭曲線の座標列が抽出される。ここで、画像処理座標系とは、左上隅を原点とし、右方向をＸ軸、下方向をＹ軸とする座標系である。なお、抽出された到達可能な範囲を示す輪郭曲線（閉曲線）の座標列データは、ワーキングエリア部１７に格納される。
【００５７】
画像重畳部１１４は、画像生成部１１２によって生成された第１画像から、基準点から所定の時間以内に到達可能な範囲を示す画像（本発明の第２画像に相当）、例えば画像処理部１１３によって抽出された到達可能な範囲を示す輪郭曲線（閉曲線）を地図画像に重畳する。
【００５８】
なお、探索部１１１、画像生成部１１２、画像処理部１１３は、センター設備（非図示）に配置する構成であってもよい。この場合には、ナビゲーション装置１は、図示しない通信手段（例えば、携帯電話）を通じて、到達可能範囲の輪郭データをセンター設備から適宜ダウンロードして表示装置１５１に表示する。
【００５９】
次に、以上のように構成されるナビゲーション装置１における動作について説明する。図３は、制御部１１全体の処理の流れを示すフローチャートである。
【００６０】
まず、図３において、探索部１１１は、探索の条件の決定を行う（ステップＳ１）。続いて、探索部１１１は、経路探索処理を行う（ステップＳ２）。続いて、画像生成部１１２は、到達可能な範囲を示す画像を生成する画像生成処理を行う（ステップＳ３）。続いて、画像処理部１１３は、画像生成部１１２によって生成された画像を処理し、到達可能範囲の輪郭を抽出する画像抽出処理を行う（ステップＳ４）。さらに、画像重畳部１１４は、到達可能な範囲を地図画像上に重畳する（ステップＳ５）。
【００６１】
次に、図４を参照して、ステップＳ２における経路探索処理の動作について説明する。なお、図４は、経路探索処理の動作を表すフローチャートである。
【００６２】
まず、図４において、探索部１１１は、探索条件が成立するすべてのノードを探索したかを判定する（ステップＳ２１）。判定の結果、探索部１１１がすべてのノードを探索していない（ステップＳ２１においてＮｏ）場合には、処理は、ステップＳ２２に進む。一方、探索部１１１が、すべてのノードを探索した（ステップＳ２１においてＹｅｓ）場合には、経路探索処理を終了する。
【００６３】
次に、ステップＳ２２において、探索部１１１は、親ノードに到達するまでの総時間コスト値（Ｔ１）を取得する。続いて、探索部１１１は、当該親ノードに接続する接続先ノードに至るリンクコスト（累積時間）を取得する（ステップＳ２３）。続くステップＳ２４において、探索部１１１は、現在時刻を取得する。現在時刻は、例えば、測位部１３のＧＰＳ受信機から取得されてもよい。続いて、探索部１１１は、現在時刻に上述の取得された親ノードに到達するまでの総時間コスト値（Ｔ１）を加算し、時刻Ｔ２を得る（ステップＳ２５）。続くステップ２６において、時刻Ｔ２における当該親ノードから接続先ノードに至るリンクの予測渋滞情報を要求する。続いて、探索部１１１は、地図情報格納部１２に予め格納されている予測渋滞データベースから予測渋滞情報を取得する（ステップＳ２７）。さらに、探索部１１１は、ステップＳ２３で求めたリンクコストにステップＳ２７で取得した予測渋滞情報を加味したリンク通過時間（Ｔ３）を算出する（ステップＳ２８）。続いて、Ｔ１にＴ３を加算した値を接続先ノードに至るまでの総時間コスト値（Ｔ４）が、ワーキングエリア部１７に格納される（ステップＳ２９）。なお、あるノードに到達する経路は複数存在するうち、最小の総時間コスト値（Ｔ４）となる経路が採用される。
【００６４】
上述の経路探索処理において、探索部１１１は、車両が親ノードから接続先ノードに至るリンクを通過するであろう時間帯における渋滞情報を考慮した経路探索を行うので、より正確な到達可能交差点を探索することができる。また、到達可能範囲を求める時間が長くなったとしても、算出される時間の精度をある程度の範囲内の誤差に抑えることができる。
【００６５】
次に、図５を参照して、ステップＳ３における画像生成処理の動作について説明する。なお、図５は、画像生成処理の動作を表すフローチャートである。
【００６６】
まず、図５において、画像生成部１１２は、黒色（本発明の第１の色に相当）からなる所定サイズの画像を生成する（ステップＳ３１）。ここで、所定サイズとは、表示装置１５１の画面サイズかそれより少し大きいサイズである。続くステップ３２において、画像生成部１１２は、上述の生成された黒色からなる所定サイズの画像に探索部１１１によって探索された一定の時間以内で到達可能なノードおよび／またはリンクを示す位置を白色（本発明の第２の色に相当）で塗りつぶす（図６または図７参照）。なお、図６は、黒色で所定サイズを塗りつぶし、所定の時間以内に到達可能なノードを示す位置を白色で塗りつぶした様子を示す図である。また、図７は、黒色で所定サイズを塗りつぶし、所定の時間以内に到達可能なノード及びリンクを示す位置を白色で塗りつぶした様子を示す図である。なお、図６から図７への差分が追加されたリンクの情報である。
【００６７】
ここで、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置の塗りつぶしは、ノードの座標（緯度経度）を上述の画像処理座標系に変換することで行う。また、変換後の画像処理座標を（Ｘ、Ｙ）とすると、その近傍（例えば、８近傍、２４近傍）を白色で塗りつぶすようにしても良い。なお、近傍の形状は四角や円、楕円、半円等を用いることができる。さらに、探索部１１１によって探索された所定の時間以内に到達可能なノードおよび／またはリンクが、出発地点からの距離が遠くなる程、白色で塗りつぶす近傍の数を増やすようにしても良い。また、表示装置１５１の画面のサイズ（解像度）に応じて、白色で塗りつぶす近傍の画素の数を可変するようにしてもよい。この場合、画面サイズ（解像度）が大きくなるほど、近傍の画素の数を多く塗るようにする。
【００６８】
また、図８の例のように、所定の時間以内に到達可能なノードを示す位置を塗りつぶし（図８の斜線部分の画素）、さらに、その近傍（例えば、８近傍、２４近傍）すべてを塗りつぶすのではなく、出発地点側（図８の点線矢印方向）にのみ塗りつぶす（図８の灰色部分の画素；本発明の第１の色に相当）ようにしてもよい。例えば、図８の例のような、所定の時間以内に到達可能なノードが、最も遠い地点の場合、当該地点（図８の斜線部分の画素）に対して、出発地点と反対側を含まない（図８の白色部分の画素；本発明の第２の色に相当）ので、より信頼性の高い到達可能な範囲を示す領域を得ることができる。
【００６９】
次に、図９および図１０を参照して、画像生成部１１２が所定の時間以内に到達可能な範囲を示す画像を生成する他の画像生成処理の動作について説明する。
【００７０】
まず、図９のステップＳ４１において、上述のステップＳ３１と同様に、画像生成部１１２は、黒色からなる所定サイズの画像を生成する。続いて、探索部１１１は、図１０に示す例のように、出発地点を中心に同心円状に地図画像を分割して、探索範囲内の道路密度を算出する（ステップＳ４２）。なお、図１０は、同心円状に地図画像を分割する方法の一例を示す模式図である。ここで、道路密度とは、同心円状に分割された一つの領域におけるノードおよび／またはリンクの数とする。すなわち、ノードおよび／またはリンクの数が、所定の閾値未満の場合には、道路密度は「疎」であり、ノードおよび／またはリンクの数が、所定の閾値以上の場合には、道路密度は「密」となる。なお、閾値は、同心円が大きくなるにつれて増減してもよい。また、上述の図２Ｃの道路種別に基づいて、白色で塗りつぶす近傍の画素の数を可変するようにしてもよい。例えば、道路種別が、細街路から高速道路になるにつれて、道路密度は、疎になっていく。この場合、道路種別の値が小さくなるにつれて、近傍の画素の数を多く塗るようにする。
【００７１】
続く、ステップＳ４３において、探索部１１１によって算出された道路密度の疎密に基づいて、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で塗りつぶす。ここで、道路密度が疎の場合には、所定の時間以内に到達可能なノード及び／又はリンクを示す位置の多くの近傍を白色で塗りつぶす。なお、出発地点を中心に同心円状に地図を分割するとしたが、これに限らずメッシュ状（小さい矩形）に分割するようにしてもよい。また、地図画像をメッシュ状に分割する場合には、算出された道路密度の閾値は、一定値でかまわない。また、地図画像を同心円状またはメッシュ状に分割しない場合、隣接する各ノード間の距離から道路密度を判定するようにしてもよい。この場合、隣接する各ノード間の距離が、所定の閾値より長いほど疎と判定する。
【００７２】
次に、図１１を参照して、図３のステップＳ４における画像抽出処理の動作について説明する。なお、図１１は、画像抽出処理の動作を表すフローチャートである。
【００７３】
まず、図１１において、図３のステップＳ３の画像生成処理で生成された画像のうち、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で表示される部分の内部の黒色で表示される部分である隙間を埋める処理を行う（ステップＳ５１）。ただし、所定の時間以内に到達不可能なノードおよび／またはリンク、つまり黒色で表示される領域は、隙間としない。ここで、隙間を埋める処理とは、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で表示され、当該白色で表示された隣接するノードおよび／またはリンクの間で、黒色で表示される部分である隙間を白色に表示する処理である。また、この処理は白色で表示された位置の領域の膨張または収縮を繰り返して行う。具体的には、図１２の例のように、図６の例のような画像から隙間を埋める処理を行う。なお、隙間を埋める処理は、公知の方法を用いてかまわない。
【００７４】
ここで、白色で示される隣接するノードおよび／またはリンクの間隔が、図６の例のように、狭い場合、生成される画像は、図１２の例のように、所定の時間以内に到達可能な範囲が一つの領域として抽出される。一方、白色で示される隣接するノードおよび／またはリンクの間隔が、広い場合、生成される画像は、図１２の例のようにならず、例えば所定の時間以内に到達可能な範囲が二つ以上の領域として抽出される。この場合、上述した道路密度に基づいて、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で塗りつぶす大きさ（太さ）を可変する処理を用いるようにしてもよい。また、道路密度に応じて、白色で表示された位置の領域の膨張または収縮を繰り返してもよい。例えば、道路密度が、疎の場合、隣接する白色で示される画素どうしの距離を大きくとるようにする。これにより、所定の時間以内に到達可能な範囲が一つの領域として抽出される。また、出発地点から所定の時間以内に到達可能なノードおよび／またはリンクまでの距離に基づいて、白色で表示された位置の領域の膨張または収縮を繰り返してもよい。また、画面サイズ（解像度）に基づいて、白色で表示された位置の領域の膨張または収縮を繰り返してもよい。また、地図画像の水系および陸系を考慮して、白色で表示された位置の領域の膨張または収縮を繰り返してもよい。例えば、水系にかかる方向へは、膨張不可にし、陸系にかかる方向へは、膨張可能にする。これにより、所定の時間以内に到達可能な範囲が一つの領域として抽出される。
【００７５】
次に、ステップＳ５２において、ステップＳ５１で生成された画像のうち、白色と黒色の境界線を滑らかにする処理を行う。具体的には、図１３の例のように、図１２の例のような画像から白色と黒色の境界線を滑らかにする処理を行う。これにより、図１３の例のように、白色と黒色の境界線を滑らかに処理することで、最終的に到達可能な範囲を地図画像に重畳した画像の視認性を向上させることができる。なお、滑らかにする処理は、公知の方法を用いてかまわない。
【００７６】
続くステップＳ５３において、ステップＳ５２で生成された画像のうち、白色と黒色の境界となる輪郭曲線を抽出する。具体的には、図１４の例のように、図１３の例のような画像から白色と黒色の境界となる輪郭曲線３０２を抽出する処理を行う。なお、輪郭曲線を抽出する処理は、公知の方法を用いてかまわない。なお、図１５は、到達可能な範囲を示す輪郭曲線の表示例である。また、任意の箇所を開始点として時計周りに１周する方向で、輪郭曲線の座標列が抽出される。また、抽出された輪郭曲線座標列は、図１５の例のように、「開始Ｘ座標、開始Ｙ座標」から「終了Ｘ座標、終了Ｙ座標」で格納される。なお、抽出された輪郭曲線座標列はワーキングエリア部１７に格納される。
【００７７】
次に、図３のステップ５において、画像重畳部１１４は、ステップＳ５３で求められた輪郭曲線３０２を地図画像３００に重畳する。なお、図１６は、到達可能な範囲を示す輪郭曲線を地図画像に重畳して表示装置１５１に表示される表示例である。
【００７８】
次に、図１７および図１８を参照して、画像処理部１１３が、動的輪郭モデルを用いて、所定の時間以内に到達可能な範囲を示す輪郭曲線を求める他の画像生成処理の動作について説明する。なお、図１７は、他の画像抽出処理の動作を表すフローチャートである。
【００７９】
まず、図１７において、ステップＳ６１およびＳ６２は、図１１のステップＳ５１およびＳ５２と同様にして画像を処理しているので、その説明を省略する。
【００８０】
続くステップＳ６３において、画像処理部１１３は、動的輪郭モデル（Ｍ．Ｋａｓｓ：“Ｓｎａｋｅｓ：Ａｃｔｉｖｅ Ｃｏｎｔｏｕｒ Ｍｏｄｅｌｓ”，Ｉｎｔｅｍａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ，１，４，ｐｐ．３２１−３３１（１９８８））を用いて、所定の時間以内に到達可能な範囲を示す輪郭曲線を抽出する。ここで、動的輪郭モデルでは、まず、初期状態の曲線を設定し、エネルギーを最小化するように曲線を逐次変形する。これにより、最終状態の曲線を到達可能な範囲を示す輪郭として取り出す。なお、エネルギーは、エッジに滑らかに引き寄せるための関数として定義することができる。また、逐次修正法としては、例えば、変分法、Ｇｒｅｅｄｙ Ａｌｇｏｒｉｔｈｍ、または動的計画法をもちいてもよい。
【００８１】
次に、図１８を参照して、ステップ６３における動的輪郭モデルを用いた場合の輪郭を抽出する際の、曲線の逐次変形について説明する。なお、図１８は、図１７のステップ６３において動的輪郭モデルを適用した場合の曲線が初期状態から最終状態へ逐次変形の様子の一例を示す模式図である。
【００８２】
図１８において、曲線４００は初期状態を示し、曲線４０１は途中状態を示し、曲線４０２は最終状態を示している。初期状態の曲線４００は、所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で示されている領域より大きな閉曲線であればどのような形状でもよい。例えば、自動的に設定する場合には、探索部１１１が探索範囲として設定する円形状を初期状態の曲線としてもよい。具体的には、探索範囲が出発地点を中心として半径５０００ｍの円とすると、その円形状を画像処理座標系へ変換し配置する。また、最終状態の曲線４０２についても、上述の図１５の例のように、輪郭曲線座標列が抽出されて、ワーキングエリア部１７に格納される。その結果、画像重畳部１１４は、動的輪郭モデルを用いて求められた輪郭曲線を地図画像に重畳して、表示装置１５１に表示される。
【００８３】
以上のように、本実施形態に係る到達可能範囲表示装置によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すことができる。その結果、ユーザはどこまでを何分で到達できるかを一目瞭然に把握することができる。
【００８４】
（第２の実施形態）
次に、第２の実施形態に係る到達可能範囲表示装置について説明する。なお、第２の実施形態においても第１の実施形態と同様、到達可能範囲表示装置の一例として、車両を目的地まで案内するナビゲーション装置に本発明を適用した例について説明する。また、第２の実施形態における到達可能範囲表示装置の構成は、第１の実施形態におけるナビゲーション装置１と同じ構成であるので、詳細な説明を省略する。第２の実施形態においては、到達可能範囲表示装置において所定の時間以内に到達可能な範囲の探索処理を行う際の探索方法および表示画面に関して主に説明する。
【００８５】
まず、探索部１１１によって所定の時間以内に到達可能なノードおよび／またはリンクが探索されると、第１の実施形態と同様の、つまり図５および図１１のステップＳ５１およびＳ５２の処理が実行される。これにより、図１３の例のような、画像（以下、時間内画像と称す）が生成される。
【００８６】
一方、探索部１１１によって所定の時間を越えて到達可能なノードおよび／またはリンクが探索されると、図１９のステップＳ３１およびＳ３２の処理が実行される。これにより、図２０の例のような、画像が生成される。なお、図２０は、黒色で所定サイズを塗りつぶし、所定の時間を越えて探索範囲における到達可能なノード示す位置を白色で塗りつぶした画像の表示例である。ここで、探索部１１１が、所定の時間を越えて探索範囲における到達可能なノードの探索に関して、予め探索範囲の条件が設定されるので、図２０の例のように、出発地点（画像中央）からすべての方向に対して探索が制限される。
【００８７】
次に、図２１を参照して、図２０における画像抽出処理の動作について説明する。なお、図２１は、画像抽出処理の動作を表すフローチャートである。
【００８８】
まず、図２１において、図２０の例のように生成された画像のうち、所定の時間を越えて到達可能なノードおよび／またはリンクを示す位置を白色で表示される部分の内部の黒色で表示される部分である隙間を埋める処理を行う（ステップＳ８１）。ただし、図２０において、所定の時間以内に到達可能なノードおよび／またはリンク、つまり黒色で表示される領域は、隙間としない。具体的には、図２２の例のように、図２０の例のような画像から隙間を埋める処理を行う。なお、隙間を埋める処理とは、上述した方法と同様である。
【００８９】
次に、ステップＳ８２において、ステップＳ８１で生成された画像のうち、白色と黒色の境界線を滑らかにする処理を行う。具体的には、図２３の例のように、図２２の例のような画像から白色と黒色の境界線を滑らかにする処理を行う。なお、滑らかにする処理は、上述した方法と同様である。
【００９０】
次に、ステップＳ８３において、画像生成部１１２は、ステップＳ８２で生成された画像のうち、白黒反転させた画像（以下、時間外画像と称す）を生成する。具体的には、図２４の例のように、図２３の例のような画像から白色と黒色とを反転させる。
【００９１】
続いて、図１１および図２１の処理を実行して得られた２つの画像の論理積を取り、時間内画像の白色の領域と時間外画像の白色の領域の重なり領域を抽出する。具体的には、図１３において白色で示した領域と、図２４において白色で示した領域とが重なる領域を抽出する。その結果、画像生成部１１２は、図２５の例のような画像を生成する。
【００９２】
次に、時間内画像の白色の領域と時間外画像の白色の領域の重なり領域の論理積を取り、生成された図２５の例のような画像のうち、白色と黒色の境界となる輪郭曲線を抽出する。具体的には、図２６の例のように、図２５の例のような画像から白色と黒色の境界となる輪郭曲線５０２を抽出する処理を行う。なお、輪郭曲線を抽出する処理は、上述した方法と同様である。なお、任意の箇所を開始点として時計周りに１周する方向で、輪郭曲線５０２の座標列が抽出される。また、抽出された輪郭曲線座標列はワーキングエリア部１７に格納される。
【００９３】
次に、画像重畳部１１４は、上述で求められた輪郭曲線５０２を地図画像５００に重畳する。なお、図２７は、到達可能な範囲を示す輪郭曲線５０２を地図画像５００に重畳して表示装置１５１に表示される表示例である。また、図１６で示した到達可能な範囲を示す輪郭曲線３０２と図２７で示す到達可能な範囲を示す輪郭曲線５０２と対比すると、輪郭曲線５０２は、輪郭曲線３０２よりも若干縮んでいる。つまり、到達可能な範囲を示す輪郭曲線５０２では、到達可能な範囲を示す輪郭曲線３０２内部に存在する所定の時間を越えて到達可能なノードを排除している。その結果、より信頼性の高い到達可能範囲表示を行うことができる。
【００９４】
以上のように、本実施形態に係る到達可能範囲表示装置によれば、ユーザが事前に何分割にするかの設定することなく、車両の現在位置から所定の時間以内に到達可能な全ての交差点を示すノードおよび／または交差点を示すノードを結ぶリンクを示す画像を地図画像上に重畳表示することで、信頼性および視認性の高い到達可能な範囲を示すことができる。その結果、ユーザはどこまでを何分で到達できるかを一目瞭然に把握することができる。
【００９５】
また、上記第１の実施形態および第２の実施形態において、所定の時間以内に到達可能な範囲を示す輪郭曲線を地図画像に重畳するようにしたが、本発明はこれに限らず、図６または図７の所定の時間以内に到達可能なノードおよび／またはリンクを示す位置を白色で表示された領域を地図画像に重畳するようにしてもよい。また、白色で表示される領域または部分の色は、任意の色を用いてもよい。さらに、透過処理を施すようにしても構わない。
【００９６】
また、上記第１の実施形態および第２の実施形態において、画像生成部１１２は、地図画像を陸系と水系に分け、陸系を白色、水系を黒色とする画像を生成し、上述した図１３および図２５の画像から論理積を取り、到達可能な範囲を示す輪郭曲線を求めるようにしてもよい。なお、図２８Ａは、上記第１の実施形態および第２の実施形態における図１３又は図２７で示した画像と同様である。図２８Ｂは、陸系を白色、水系を黒色とした様子を示す図である。例えば、上記第１の実施形態および第２の実施形態と同様にして、図２８Ａと図２８Ｂのから論理積を取る。その結果、画像生成部１１２は、図２８Ｃの例のような画像を生成する。さらに、図２８Ｃの画像から上記第１の実施形態および第２の実施形態と同様にして、輪郭曲線を求める。これにより、到達可能な範囲を示す輪郭曲線は、常に陸系の範囲に描かれ、さらに、信頼性の高い到達可能範囲表示を行うことができる。
【００９７】
以上、本発明を詳細に説明したが、上記説明はあらゆる意味において例示的なものであり限定的なものではない。本発明の範囲から逸脱することなしに多くの他の改変例及び変形例が可能であることは言うまでもない。
【産業上の利用可能性】
【００９８】
本発明に係る到達可能範囲表示装置および到達可能範囲表示方法ならびにそのプログラムは、ナビゲーション装置やパーソナルコンピュータ上で動作する地図表示アプリケーション、携帯電話、タクシー、警備会社等での配車・指令システム等、地図を表示可能なあらゆる機器、システムに対して適用可能である。
【図面の簡単な説明】
【００９９】
【図１】第１の実施形態に係るナビゲーション装置の構成を示す機能
【図２Ａ】第１の実施形態に係る地図情報格納部１２に格納される地図情報のうち、ノードデータの一例を示す図
【図２Ｂ】第１の実施形態に係る地図情報格納部１２に格納される地図情報のうち、リンクデータの一例を示す図
【図２Ｃ】第１の実施形態に係る地図情報格納部１２に格納される地図情報のうち、道路種別の一例を示す図
【図３】制御部１１全体の処理の流れを示すフローチャート
【図４】経路探索処理の動作を表すフローチャート
【図５】本発明の第１の実施形態における画像生成処理の動作を表すフローチャート
【図６】黒色で所定サイズを塗りつぶし、所定の時間以内に到達可能なノードを示す位置を白色で塗りつぶした様子を示す図
【図７】黒色で所定サイズを塗りつぶし、所定の時間以内に到達可能なノード及びリンクを示す位置を白色で塗りつぶした様子を示す図
【図８】所定の時間以内に到達可能なノードの近傍を塗りつぶす位置を説明するための図
【図９】他の画像生成処理の動作を表すフローチャート
【図１０】同心円状に地図画像を分割する方法の一例を示す模式図
【図１１】本発明の第１の実施形態における画像抽出処理の動作を表すフローチャート
【図１２】図６を隙間を埋める処理した様子を示す図
【図１３】図１２の白色と黒色の境界を滑らかにする処理をした様子を示す図
【図１４】図１３の白色と黒色の境界となる輪郭曲線を抽出した様子を示す図
【図１５】輪郭曲線座標列の格納形式の一例を示す模式図
【図１６】本発明の第１の実施形態における到達可能な範囲を示す輪郭曲線を地図画像に重畳して表示装置１５１に表示される表示例
【図１７】他の画像抽出処理の動作を表すフローチャート
【図１８】動的輪郭モデルを適用した場合の曲線が初期状態から最終状態へ逐次変形の様子の一例を示す模式図
【図１９】本発明の第２の実施形態における画像生成処理の動作を表すフローチャート
【図２０】黒色で所定サイズを塗りつぶし、所定の時間を越えて到達可能なノードを示す位置を白色で塗りつぶした様子を示す図
【図２１】本発明の第２の実施形態における画像抽出処理の動作を表すフローチャート
【図２２】図２１を隙間を埋める処理した様子を示す図
【図２３】図２２の白色と黒色の境界を滑らかにする処理をした様子を示す図
【図２４】図２２の白色と黒色とを反転させる処理をした様子を示す図
【図２５】図１３と図２４との画像から理論積をした様子を示す図
【図２６】図２５の白色と黒色の境界となる輪郭曲線を抽出した様子を示す図
【図２７】本発明の第２の実施形態における到達可能な範囲を示す輪郭曲線を地図画像に重畳して表示装置１５１に表示される表示例
【図２８Ａ】図１２の白色と黒色の境界を滑らかにする処理をした様子を示す図
【図２８Ｂ】陸系を白色、水系を黒色とした様子を示す図
【図２８Ｃ】図２８Ａと図２８Ｂとの画像から理論積をした様子を示す図
【符号の説明】
【０１００】
１ ナビゲーション装置
１１ 制御部
１２ 地図情報格納部
１３ 測位部
１４ 入力部
１５ 出力部
１６ 交通情報受信部
１７ ワーキングエリア部
１１１ 探索部
１１２ 画像生成部
１１３ 画像処理部
１１４ 画像重畳部
１５１ 表示装置
３００、５００ 地図画像
３０２、５０２ 輪郭曲線
４００ 初期状態を示す曲線
４０１ 途中状態を示す曲線
４０２ 最終状態を示す曲線
【特許請求の範囲】
【請求項１】
地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置であって、
前記基準点から任意の前記地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する探索部と、
前記探索部によって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する画像生成部と、
前記画像生成部によって生成された第１画像から、前記基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する画像処理部と、
前記画像処理部によって生成された第２画像を前記地図画像に重畳して表示画面に表示する画像重畳部とを備える、到達可能範囲表示装置。
【請求項２】
前記画像生成部は、前記基準点から前記探索部によって探索された所定の時間以内に到達可能な地点群を所定色で示される第１画像を生成し、
前記画像処理部は、前記所定色で示された第１画像から、前記基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する、請求項１に記載の到達可能範囲表示装置。
【請求項３】
前記画像生成部は、前記基準点から前記探索部によって探索された所定の時間以内に到達可能な地点群を示す画素をそれぞれの周囲へ前記所定色の画素で太らせた第１画像を生成する、請求項２に記載の到達可能範囲表示装置。
【請求項４】
前記画像生成部は、前記基準点から前記探索部によって探索された所定の時間以内に到達可能な地点群を示す画素のうち、前記基準点から前記探索部によって探索された所定の時間以内に到達不可能な地点群との境界にある画素をそれぞれの前記基準点側にのみ前記所定色で太らせ、当該境界以外の画素をそれぞれの周囲へ前記所定色の画素で太らせた第１画像を生成する、請求項２に記載の到達可能範囲表示装置。
【請求項５】
前記画像生成部は、前記基準点から前記探索部によって探索された所定の時間以内に到達可能な地点群のそれぞれまでの経路を使い、所定色で示される第１画像を生成する、請求項２に記載の到達可能範囲表示装置。
【請求項６】
前記画像生成部は、前記経路の道路種別に基づいて、当該経路を所定色で塗りつぶす太さを決定する、請求項５に記載の到達可能範囲表示装置。
【請求項７】
前記画像生成部は、前記到達可能な地点群をその内部に全て含む前記地図上の領域内を第１の色で塗りつぶし、前記到達不可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、当該第１の色および当該第２の色の境界となる輪郭曲線を抽出する輪郭抽出部を含み、
前記画像重畳部は、前記輪郭曲線を前記地図画像に重畳して表示画面に表示する、請求項１に記載の到達可能範囲表示装置。
【請求項８】
前記輪郭抽出部は、前記第１の色を黒色および前記第２の色を白色として前記第１の色および前記第２の色の境界を抽出する、請求項７に記載の到達可能範囲表示装置。
【請求項９】
前記輪郭抽出部は、所定の動的輪郭モデルを用いて、前記輪郭曲線を抽出する、請求項７に記載の到達可能範囲表示装置。
【請求項１０】
前記探索部は、前記基準点を中心として所定の距離を半径とする円形状からなる領域を探索範囲として、前記基準点から当該探索範囲に存在する任意の複数の地点までの最適経路を探索して所要時間を算出し、
前記輪郭抽出部は、前記探索部が用いた前記円形状の領域を、前記動的輪郭モデルを用いる際の初期状態の曲線とする、請求項９に記載の到達可能範囲表示装置。
【請求項１１】
前記探索部は、前記基準点を中心とする所定範囲に存在する前記基準点から任意の前記地図画像上の任意の複数の地点までの経路の数に基づいて、道路密度を算出する道路密度算出部を、さらに含み、
前記画像生成部は、前記道路密度算出部によって算出された道路密度の算出結果に基づいて、前記到達可能な地点群を示す画素をそれぞれの周囲へ前記所定色の画素で太らせる画素数を前記道路密度に基づいて決定する、請求項３に記載の到達可能範囲表示装置。
【請求項１２】
前記道路密度算出部は、前記基準点を中心とした所定範囲を、同心円状またはメッシュ状の領域に分割し、当該分割された領域ごとに存在する前記経路の数に基づいて、前記道路密度を算出する、請求項１１に記載の到達可能範囲表示装置。
【請求項１３】
前記画像生成部は、前記到達可能な地点群を示す画像と前記到達不可能な地点群を示す画像とを生成し、当該画像が重複する領域について所定の演算を行い、到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する論理演算部を含む、請求項１に記載の到達可能範囲表示装置。
【請求項１４】
前記論理演算部は、前記到達不可能な地点群を第１の色で塗りつぶし前記到達可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、前記到達不可能な地点群を前記第２の色で塗りつぶし前記到達可能な地点群を前記第１の色で塗りつぶした画像を生成し、当該２つの画像の論理積を用いて、前記到達可能な地点群と前記到達不可能な地点群との区別が可能な第１画像を生成する、請求項１３に記載の到達可能範囲表示装置。
【請求項１５】
地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示方法であって、
前記基準点から任意の前記地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する探索ステップと、
前記探索ステップによって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する画像生成ステップと、
前記画像生成ステップによって生成された前記第１画像から、前記基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する画像処理ステップと、
前記画像処理ステップによって生成された第２画像を前記地図画像に重畳して表示画面に表示する画像重畳ステップとを含む、到達可能範囲表示方法。
【請求項１６】
地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置のコンピュータで実行される到達可能範囲表示プログラムであって、
前記コンピュータに、
前記基準点から任意の前記地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する探索ステップと、
前記探索ステップによって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する画像生成ステップと、
前記画像生成ステップによって生成された前記第１画像から、前記基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する画像処理ステップと、
前記画像処理ステップによって生成された第２画像を前記地図画像に重畳して表示画面に表示する画像重畳ステップとを実行させる、到達可能範囲表示プログラム。
【請求項１】
地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置であって、
前記基準点から任意の前記地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する探索部と、
前記探索部によって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する画像生成部と、
前記画像生成部によって生成された第１画像から、前記基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する画像処理部と、
前記画像処理部によって生成された第２画像を前記地図画像に重畳して表示画面に表示する画像重畳部とを備える、到達可能範囲表示装置。
【請求項２】
前記画像生成部は、前記基準点から前記探索部によって探索された所定の時間以内に到達可能な地点群を所定色で示される第１画像を生成し、
前記画像処理部は、前記所定色で示された第１画像から、前記基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する、請求項１に記載の到達可能範囲表示装置。
【請求項３】
前記画像生成部は、前記基準点から前記探索部によって探索された所定の時間以内に到達可能な地点群を示す画素をそれぞれの周囲へ前記所定色の画素で太らせた第１画像を生成する、請求項２に記載の到達可能範囲表示装置。
【請求項４】
前記画像生成部は、前記基準点から前記探索部によって探索された所定の時間以内に到達可能な地点群を示す画素のうち、前記基準点から前記探索部によって探索された所定の時間以内に到達不可能な地点群との境界にある画素をそれぞれの前記基準点側にのみ前記所定色で太らせ、当該境界以外の画素をそれぞれの周囲へ前記所定色の画素で太らせた第１画像を生成する、請求項２に記載の到達可能範囲表示装置。
【請求項５】
前記画像生成部は、前記基準点から前記探索部によって探索された所定の時間以内に到達可能な地点群のそれぞれまでの経路を使い、所定色で示される第１画像を生成する、請求項２に記載の到達可能範囲表示装置。
【請求項６】
前記画像生成部は、前記経路の道路種別に基づいて、当該経路を所定色で塗りつぶす太さを決定する、請求項５に記載の到達可能範囲表示装置。
【請求項７】
前記画像生成部は、前記到達可能な地点群をその内部に全て含む前記地図上の領域内を第１の色で塗りつぶし、前記到達不可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、当該第１の色および当該第２の色の境界となる輪郭曲線を抽出する輪郭抽出部を含み、
前記画像重畳部は、前記輪郭曲線を前記地図画像に重畳して表示画面に表示する、請求項１に記載の到達可能範囲表示装置。
【請求項８】
前記輪郭抽出部は、前記第１の色を黒色および前記第２の色を白色として前記第１の色および前記第２の色の境界を抽出する、請求項７に記載の到達可能範囲表示装置。
【請求項９】
前記輪郭抽出部は、所定の動的輪郭モデルを用いて、前記輪郭曲線を抽出する、請求項７に記載の到達可能範囲表示装置。
【請求項１０】
前記探索部は、前記基準点を中心として所定の距離を半径とする円形状からなる領域を探索範囲として、前記基準点から当該探索範囲に存在する任意の複数の地点までの最適経路を探索して所要時間を算出し、
前記輪郭抽出部は、前記探索部が用いた前記円形状の領域を、前記動的輪郭モデルを用いる際の初期状態の曲線とする、請求項９に記載の到達可能範囲表示装置。
【請求項１１】
前記探索部は、前記基準点を中心とする所定範囲に存在する前記基準点から任意の前記地図画像上の任意の複数の地点までの経路の数に基づいて、道路密度を算出する道路密度算出部を、さらに含み、
前記画像生成部は、前記道路密度算出部によって算出された道路密度の算出結果に基づいて、前記到達可能な地点群を示す画素をそれぞれの周囲へ前記所定色の画素で太らせる画素数を前記道路密度に基づいて決定する、請求項３に記載の到達可能範囲表示装置。
【請求項１２】
前記道路密度算出部は、前記基準点を中心とした所定範囲を、同心円状またはメッシュ状の領域に分割し、当該分割された領域ごとに存在する前記経路の数に基づいて、前記道路密度を算出する、請求項１１に記載の到達可能範囲表示装置。
【請求項１３】
前記画像生成部は、前記到達可能な地点群を示す画像と前記到達不可能な地点群を示す画像とを生成し、当該画像が重複する領域について所定の演算を行い、到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する論理演算部を含む、請求項１に記載の到達可能範囲表示装置。
【請求項１４】
前記論理演算部は、前記到達不可能な地点群を第１の色で塗りつぶし前記到達可能な地点群を当該第１の色とは異なった第２の色で塗りつぶした画像を生成し、前記到達不可能な地点群を前記第２の色で塗りつぶし前記到達可能な地点群を前記第１の色で塗りつぶした画像を生成し、当該２つの画像の論理積を用いて、前記到達可能な地点群と前記到達不可能な地点群との区別が可能な第１画像を生成する、請求項１３に記載の到達可能範囲表示装置。
【請求項１５】
地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示方法であって、
前記基準点から任意の前記地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する探索ステップと、
前記探索ステップによって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する画像生成ステップと、
前記画像生成ステップによって生成された前記第１画像から、前記基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する画像処理ステップと、
前記画像処理ステップによって生成された第２画像を前記地図画像に重畳して表示画面に表示する画像重畳ステップとを含む、到達可能範囲表示方法。
【請求項１６】
地図上の基準点から所定の時間以内に到達可能な範囲を地図画像上に表示する到達可能範囲表示装置のコンピュータで実行される到達可能範囲表示プログラムであって、
前記コンピュータに、
前記基準点から任意の前記地図画像上の任意の複数の地点までの最適経路を探索して所要時間を算出する探索ステップと、
前記探索ステップによって探索された所定の時間以内に到達可能な地点群と到達不可能な地点群との区別が可能な第１画像を生成する画像生成ステップと、
前記画像生成ステップによって生成された前記第１画像から、前記基準点から所定の時間以内に到達可能な範囲を示す第２画像を生成する画像処理ステップと、
前記画像処理ステップによって生成された第２画像を前記地図画像に重畳して表示画面に表示する画像重畳ステップとを実行させる、到達可能範囲表示プログラム。
【図１】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８Ａ】
【図２８Ｂ】
【図２８Ｃ】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８Ａ】
【図２８Ｂ】
【図２８Ｃ】
【公開番号】特開２００８−９６２０９（Ｐ２００８−９６２０９Ａ）
【公開日】平成２０年４月２４日（２００８．４．２４）
【国際特許分類】
【出願番号】特願２００６−２７６６５４（Ｐ２００６−２７６６５４）
【出願日】平成１８年１０月１０日（２００６．１０．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００５８２１）松下電器産業株式会社 (73,050)
【Ｆターム（参考）】
【公開日】平成２０年４月２４日（２００８．４．２４）
【国際特許分類】
【出願日】平成１８年１０月１０日（２００６．１０．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００５８２１）松下電器産業株式会社 (73,050)
【Ｆターム（参考）】
[ Back to top ]