道のり推定装置及び方法及びプログラム
【課題】 大規模な記憶装置を必要とせず、高速に算出可能であって、しかも、都市内での現実的な移動実態を反映したより正確な道のりを算出する。
【解決手段】 本発明は、推定する道のりの２点を取得し、矩形単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段から該２点を対角線の２頂点とするような矩形に含まれるメッシュを取得し、２点を矩形とするメッシュを対象として、自由度の数値の和ｃと面積の和Ｓを求め、該面積の和Ｓが小さいほど、また、該自由度の数値の和ｃが大きいほど小さくなるパラメータｐを算出し、入力された２点の座標とパラメータｐを用いたＬｐノルムを用いて道のりを推定する。
【解決手段】 本発明は、推定する道のりの２点を取得し、矩形単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段から該２点を対角線の２頂点とするような矩形に含まれるメッシュを取得し、２点を矩形とするメッシュを対象として、自由度の数値の和ｃと面積の和Ｓを求め、該面積の和Ｓが小さいほど、また、該自由度の数値の和ｃが大きいほど小さくなるパラメータｐを算出し、入力された２点の座標とパラメータｐを用いたＬｐノルムを用いて道のりを推定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道のり推定装置及び方法及びプログラムに係り、特に、都市内・都市間の指定された２点間の道のりを推定するための道のり推定装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
２点間の道のりを自動的に推定するための技術として、従来より、
１）カーナビゲーションシステムに見られるように、道路地図相当の情報を保持し、２点間を結ぶ様々な経路のうち最短のものを返す方法（例えば、特許文献１参照）；
２）直線距離やマンハッタン距離を用いる方法；
という大きく２通りの方法が存在する。
【０００３】
上記の１）の方法は、正確な道のりの算出を行うことができるため、カーナビゲーションのように正確さが要求される状況で用いられている。
【０００４】
上記の２)の方法は、大きな記憶装置を必要とせず、より高速に算出を行えるため、道のりの算出を高頻度に行う必要がある状況、例えば、与えられた多数の地点の任意の２点間を結ぶ道のりを全て算出するような状況や、利用できる記憶資源が限られている状況などで用いられている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第３０７６０２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、従来技術のうち、１)の方式によれば、膨大な地図データを必要とする上に、２点間での移動可能な各種経路の算出や、各経路を辿った場合の移動距離の算出を行う必要があった。すなわち、大規模な記憶装置が必要であるという課題と、計算のために必要な処理が大きいという問題があった。
【０００７】
また、２）の方式によれば、都市内で現実的な移動実態を反映した正確な道のりの算出をすることができないという問題があった。
【０００８】
本発明は、上記の点に鑑みなされたもので、大規模な記憶装置を必要とせず、高速に算出可能であって、しかも、都市内での現実的な移動実態を反映したより正確な道のりを算出することができるような道のり推定装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明（請求項１）は、道のりを概算で推定するための道のり推定装置であって、
矩形単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段と、
推定する道のりの２点を取得し、該２点を対角線の２頂点とするような矩形に含まれるメッシュを前記記憶手段から取得するメッシュ取得手段と、
前記２点を矩形とするメッシュを対象として、自由度の数値の和ｃと面積の和Ｓを求め、該面積の和Ｓが小さいほど、また、該自由度の数値の和ｃが大きいほど小さくなるパラメータｐを算出するパラメータ算出手段と、
入力された前記２点の座標と前記パラメータｐを用いたＬｐノルムを用いて道のりを推定する推定手段と、を有する。
【００１０】
また、本発明（請求項２）は、前記パラメータ算出手段において、
前記パラメータｐを求める際に、
【００１１】
【数１】
（但し、αは調整のためのパラメータ定数）
を用い、ｐの値が負となった場合はｐ＝０とし、ｐの値が概ね１〜２の値となるように決定する手段を含む。
【００１２】
また、本発明（請求項３）は、前記推定において、
前記道のりを求める際に、
【００１３】
【数２】
(但し、βは事前に設定したパラメータ定数、ｘ１，ｘ２，ｙ１，ｙ２は前記入力された２点の座標)
を用い、２点が完全に一致であれば０、ｘ座標とｙ座標のうち、いずれか１つが異なればβ、ｘ座標、ｙ座標ともに異なればβ×２であるとする手段を含む。
【発明の効果】
【００１４】
本発明によれば、道のりの算出を直線距離ではなく、都市内での移動を反映した距離を用い、当該距離において、パラメータｐを用いたＬｐノルムを用い、単位矩形内のメッシュ毎の交差点数を用いるため、大規模な記憶装置を必要とせずに、高速に、より正確な２点間の道のりの推定が可能となる。
【００１５】
また、対象矩形内の総交差点数を取得した後には２つの数式のみであるので、高速に計算可能である。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施の形態における道のり推定装置の構成図である。
【図２】本発明の一実施の形態におけるメッシュ−交差点数データベースのデータ例である。
【図３】本発明の一実施の形態における概要動作のフローチャートである。
【発明を実施するための形態】
【００１７】
以下図面と共に、本発明の実施の形態を説明する。
【００１８】
図１は、本発明の一実施の形態における道のり推定装置の構成を示す。
【００１９】
同図に示す道のり推定装置は、矩形内メッシュ情報取得部１、距離調整パラメータ決定部２、道のり推定部３、メッシュ−交差点数データベース４から構成される。
【００２０】
メッシュ−交差点数データベース４は、図２に示すように、各メッシュの番号、そのメッシュの範囲、そのメッシュ内に含まれる交差点の数長を記録したものであり、ハードディスク等の記憶媒体に設けられる。本装置が取り扱う緯度経度から一意にメッシュ番号を特定するように構成することも可能である。その場合は、メッシュ範囲を持たず、メッシュ番号と、交差点数だけで構成することも可能である。
【００２１】
また、メッシュ−交差点数データベース４に格納する情報は、そのメッシュ範囲内で自由に移動のしやすさと相関にある情報であれば、必ずしも交差点数である必要はない。例えば、交差点数の代わりにメッシュ内での道路の総延長等を用いることも可能である。
【００２２】
図３は、本発明の一実施の形態における概要動作のフローチャートである。
【００２３】
ステップ１） 矩形内メッシュ情報取得部１は、装置に入力された２点の座標を入力として受け取り、この２点を対角線の２頂点とするような矩形に含まれる全てのメッシュの情報をメッシュ−交差点数データベース４に問い合わせる。
【００２４】
ステップ２） 矩形メッシュ情報取得部１は、取得した矩形に含まれる全てのメッシュ情報について、メッシュ−交差点数データベース４を参照し、矩形内の総交差点数を得る。
【００２５】
ステップ３） 距離調整パラメータ決定部２では、矩形内メッシュ情報取得部１で得られた総交差点数ｃと矩形の面積（すなわち、装置に入力された２点を対角線の２頂点とするような矩形の面積)Ｓを用いて、以下の式により非負の距離調整パラメータｐを決定する。
【００２６】
【数３】
もし、上記の式(1)により算出したｐの値が負となった場合はｐ＝０とする。ここで、αは調整のためのパラメータ定数であり、想定されるＳ，ｃにおいて、ｐの値が概ね１〜２の値となるように決定することが望ましい。このαの決定方法としては、例えば、標準的な都市において２点間を選択した場合に、本装置により算出した道のりと実際の道のりが一致するように調整することが可能である。
【００２７】
ステップ４） 道のり推定部３では、装置へ入力された２点の座標(ｘ１，ｙ１)，（ｘ２，ｙ２）と、距離調整パラメータ決定部２によって決定された距離調整パラメータｐを用いて、以下の式(2)によって道のりを推定し、これを出力する。
【００２８】
【数４】
ここで、βは事前に設定したパラメータ定数である。特に、ｐ＝０の場合は、２点間のｘ座標とｙ座標の値のうち、異なりの数とする。すなわち、２点が完全に一致であれば、０、ｘ座標とｙ座標のうち、いずれか１つが異なればβ、ｘ座標、ｙ座標ともに異なれば、β×２である。
【００２９】
上記のように本発明では、例えば、メッシュ−交差点数データベース４において、メッシュ範囲を持たない構成とした上で、総メッシュ数１万であるとき、交差点数を各１０ビットで表現した場合は、１０万ビットだけでよく、高速に２点間の道のりの推定が可能となる。
【００３０】
なお、上記の図１の道のり推定装置の各構成要素の動作をプログラムとして構築し、道のり推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００３１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００３２】
１ 矩形内メッシュ情報取得部
２ 距離調整パラメータ決定部
３ 道のり推定部
４ メッシュ−交差点数データベース
【技術分野】
【０００１】
本発明は、道のり推定装置及び方法及びプログラムに係り、特に、都市内・都市間の指定された２点間の道のりを推定するための道のり推定装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
２点間の道のりを自動的に推定するための技術として、従来より、
１）カーナビゲーションシステムに見られるように、道路地図相当の情報を保持し、２点間を結ぶ様々な経路のうち最短のものを返す方法（例えば、特許文献１参照）；
２）直線距離やマンハッタン距離を用いる方法；
という大きく２通りの方法が存在する。
【０００３】
上記の１）の方法は、正確な道のりの算出を行うことができるため、カーナビゲーションのように正確さが要求される状況で用いられている。
【０００４】
上記の２)の方法は、大きな記憶装置を必要とせず、より高速に算出を行えるため、道のりの算出を高頻度に行う必要がある状況、例えば、与えられた多数の地点の任意の２点間を結ぶ道のりを全て算出するような状況や、利用できる記憶資源が限られている状況などで用いられている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第３０７６０２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、従来技術のうち、１)の方式によれば、膨大な地図データを必要とする上に、２点間での移動可能な各種経路の算出や、各経路を辿った場合の移動距離の算出を行う必要があった。すなわち、大規模な記憶装置が必要であるという課題と、計算のために必要な処理が大きいという問題があった。
【０００７】
また、２）の方式によれば、都市内で現実的な移動実態を反映した正確な道のりの算出をすることができないという問題があった。
【０００８】
本発明は、上記の点に鑑みなされたもので、大規模な記憶装置を必要とせず、高速に算出可能であって、しかも、都市内での現実的な移動実態を反映したより正確な道のりを算出することができるような道のり推定装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明（請求項１）は、道のりを概算で推定するための道のり推定装置であって、
矩形単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段と、
推定する道のりの２点を取得し、該２点を対角線の２頂点とするような矩形に含まれるメッシュを前記記憶手段から取得するメッシュ取得手段と、
前記２点を矩形とするメッシュを対象として、自由度の数値の和ｃと面積の和Ｓを求め、該面積の和Ｓが小さいほど、また、該自由度の数値の和ｃが大きいほど小さくなるパラメータｐを算出するパラメータ算出手段と、
入力された前記２点の座標と前記パラメータｐを用いたＬｐノルムを用いて道のりを推定する推定手段と、を有する。
【００１０】
また、本発明（請求項２）は、前記パラメータ算出手段において、
前記パラメータｐを求める際に、
【００１１】
【数１】
（但し、αは調整のためのパラメータ定数）
を用い、ｐの値が負となった場合はｐ＝０とし、ｐの値が概ね１〜２の値となるように決定する手段を含む。
【００１２】
また、本発明（請求項３）は、前記推定において、
前記道のりを求める際に、
【００１３】
【数２】
(但し、βは事前に設定したパラメータ定数、ｘ１，ｘ２，ｙ１，ｙ２は前記入力された２点の座標)
を用い、２点が完全に一致であれば０、ｘ座標とｙ座標のうち、いずれか１つが異なればβ、ｘ座標、ｙ座標ともに異なればβ×２であるとする手段を含む。
【発明の効果】
【００１４】
本発明によれば、道のりの算出を直線距離ではなく、都市内での移動を反映した距離を用い、当該距離において、パラメータｐを用いたＬｐノルムを用い、単位矩形内のメッシュ毎の交差点数を用いるため、大規模な記憶装置を必要とせずに、高速に、より正確な２点間の道のりの推定が可能となる。
【００１５】
また、対象矩形内の総交差点数を取得した後には２つの数式のみであるので、高速に計算可能である。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施の形態における道のり推定装置の構成図である。
【図２】本発明の一実施の形態におけるメッシュ−交差点数データベースのデータ例である。
【図３】本発明の一実施の形態における概要動作のフローチャートである。
【発明を実施するための形態】
【００１７】
以下図面と共に、本発明の実施の形態を説明する。
【００１８】
図１は、本発明の一実施の形態における道のり推定装置の構成を示す。
【００１９】
同図に示す道のり推定装置は、矩形内メッシュ情報取得部１、距離調整パラメータ決定部２、道のり推定部３、メッシュ−交差点数データベース４から構成される。
【００２０】
メッシュ−交差点数データベース４は、図２に示すように、各メッシュの番号、そのメッシュの範囲、そのメッシュ内に含まれる交差点の数長を記録したものであり、ハードディスク等の記憶媒体に設けられる。本装置が取り扱う緯度経度から一意にメッシュ番号を特定するように構成することも可能である。その場合は、メッシュ範囲を持たず、メッシュ番号と、交差点数だけで構成することも可能である。
【００２１】
また、メッシュ−交差点数データベース４に格納する情報は、そのメッシュ範囲内で自由に移動のしやすさと相関にある情報であれば、必ずしも交差点数である必要はない。例えば、交差点数の代わりにメッシュ内での道路の総延長等を用いることも可能である。
【００２２】
図３は、本発明の一実施の形態における概要動作のフローチャートである。
【００２３】
ステップ１） 矩形内メッシュ情報取得部１は、装置に入力された２点の座標を入力として受け取り、この２点を対角線の２頂点とするような矩形に含まれる全てのメッシュの情報をメッシュ−交差点数データベース４に問い合わせる。
【００２４】
ステップ２） 矩形メッシュ情報取得部１は、取得した矩形に含まれる全てのメッシュ情報について、メッシュ−交差点数データベース４を参照し、矩形内の総交差点数を得る。
【００２５】
ステップ３） 距離調整パラメータ決定部２では、矩形内メッシュ情報取得部１で得られた総交差点数ｃと矩形の面積（すなわち、装置に入力された２点を対角線の２頂点とするような矩形の面積)Ｓを用いて、以下の式により非負の距離調整パラメータｐを決定する。
【００２６】
【数３】
もし、上記の式(1)により算出したｐの値が負となった場合はｐ＝０とする。ここで、αは調整のためのパラメータ定数であり、想定されるＳ，ｃにおいて、ｐの値が概ね１〜２の値となるように決定することが望ましい。このαの決定方法としては、例えば、標準的な都市において２点間を選択した場合に、本装置により算出した道のりと実際の道のりが一致するように調整することが可能である。
【００２７】
ステップ４） 道のり推定部３では、装置へ入力された２点の座標(ｘ１，ｙ１)，（ｘ２，ｙ２）と、距離調整パラメータ決定部２によって決定された距離調整パラメータｐを用いて、以下の式(2)によって道のりを推定し、これを出力する。
【００２８】
【数４】
ここで、βは事前に設定したパラメータ定数である。特に、ｐ＝０の場合は、２点間のｘ座標とｙ座標の値のうち、異なりの数とする。すなわち、２点が完全に一致であれば、０、ｘ座標とｙ座標のうち、いずれか１つが異なればβ、ｘ座標、ｙ座標ともに異なれば、β×２である。
【００２９】
上記のように本発明では、例えば、メッシュ−交差点数データベース４において、メッシュ範囲を持たない構成とした上で、総メッシュ数１万であるとき、交差点数を各１０ビットで表現した場合は、１０万ビットだけでよく、高速に２点間の道のりの推定が可能となる。
【００３０】
なお、上記の図１の道のり推定装置の各構成要素の動作をプログラムとして構築し、道のり推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００３１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００３２】
１ 矩形内メッシュ情報取得部
２ 距離調整パラメータ決定部
３ 道のり推定部
４ メッシュ−交差点数データベース
【特許請求の範囲】
【請求項１】
道のりを概算で推定するための道のり推定装置であって、
矩形単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段と、
推定する道のりの２点を取得し、該２点を対角線の２頂点とするような矩形に含まれるメッシュを前記記憶手段から取得するメッシュ取得手段と、
前記２点を矩形とするメッシュを対象として、自由度の数値の和ｃと面積の和Ｓを求め、該面積の和Ｓが小さいほど、また、該自由度の数値の和ｃが大きいほど小さくなるパラメータｐを算出するパラメータ算出手段と、
入力された前記２点の座標と前記パラメータｐを用いたＬｐノルムを用いて道のりを推定する推定手段と、
を有することを特徴とする道のり推定装置。
【請求項２】
前記パラメータ算出手段は、
前記パラメータｐを求める際に、
【数５】
（但し、αは調整のためのパラメータ定数）
を用い、ｐの値が負となった場合はｐ＝０とし、ｐの値が概ね１〜２の値となるように決定する手段を含む
請求項１記載の道のり推定装置。
【請求項３】
前記推定手段は、
前記道のりを求める際に、
【数６】
(但し、βは事前に設定したパラメータ定数、ｘ１，ｘ２，ｙ１，ｙ２は前記入力された２点の座標)
を用い、２点が完全に一致であれば０、ｘ座標とｙ座標のうち、いずれか１つが異なればβ、ｘ座標、ｙ座標ともに異なればβ×２であるとする手段を含む
請求項１記載の道のり推定装置。
【請求項４】
道のりを概算で推定するための道のり推定方法であって、
メッシュ取得手段が、推定する道のりの２点を取得し、矩形単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段から該２点を対角線の２頂点とするような矩形に含まれるメッシュを取得するメッシュ取得ステップと、
パラメータ算出手段が、前記２点を矩形とするメッシュを対象として、自由度の数値の和ｃと面積の和Ｓを求め、該面積の和Ｓが小さいほど、また、該自由度の数値の和ｃが大きいほど小さくなるパラメータｐを算出するパラメータ算出ステップと、
推定手段が、入力された前記２点の座標と前記パラメータｐを用いたＬｐノルムを用いて道のりを推定する推定ステップと、
を行うことを特徴とする道のり推定方法。
【請求項５】
前記パラメータ算出ステップにおいて、
前記パラメータｐを求める際に、
【数７】
（但し、αは調整のためのパラメータ定数）
を用い、ｐの値が負となった場合はｐ＝０とし、ｐの値が概ね１〜２の値となるように決定する
請求項４記載の道のり推定方法。
【請求項６】
前記推定ステップにおいて、
前記道のりを求める際に、
【数８】
(但し、βは事前に設定したパラメータ定数、ｘ１，ｘ２，ｙ１，ｙ２は前記入力された２点の座標)
を用い、２点が完全に一致であれば０、ｘ座標とｙ座標のうち、いずれか１つが異なればβ、ｘ座標、ｙ座標ともに異なればβ×２であるとする
請求項４記載の道のり推定方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載の道のり推定装置の各手段として機能させる道のり推定プログラム。
【請求項１】
道のりを概算で推定するための道のり推定装置であって、
矩形単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段と、
推定する道のりの２点を取得し、該２点を対角線の２頂点とするような矩形に含まれるメッシュを前記記憶手段から取得するメッシュ取得手段と、
前記２点を矩形とするメッシュを対象として、自由度の数値の和ｃと面積の和Ｓを求め、該面積の和Ｓが小さいほど、また、該自由度の数値の和ｃが大きいほど小さくなるパラメータｐを算出するパラメータ算出手段と、
入力された前記２点の座標と前記パラメータｐを用いたＬｐノルムを用いて道のりを推定する推定手段と、
を有することを特徴とする道のり推定装置。
【請求項２】
前記パラメータ算出手段は、
前記パラメータｐを求める際に、
【数５】
（但し、αは調整のためのパラメータ定数）
を用い、ｐの値が負となった場合はｐ＝０とし、ｐの値が概ね１〜２の値となるように決定する手段を含む
請求項１記載の道のり推定装置。
【請求項３】
前記推定手段は、
前記道のりを求める際に、
【数６】
(但し、βは事前に設定したパラメータ定数、ｘ１，ｘ２，ｙ１，ｙ２は前記入力された２点の座標)
を用い、２点が完全に一致であれば０、ｘ座標とｙ座標のうち、いずれか１つが異なればβ、ｘ座標、ｙ座標ともに異なればβ×２であるとする手段を含む
請求項１記載の道のり推定装置。
【請求項４】
道のりを概算で推定するための道のり推定方法であって、
メッシュ取得手段が、推定する道のりの２点を取得し、矩形単位に経路選択の自由度を表す交差点数または総道路距離を格納した記憶手段から該２点を対角線の２頂点とするような矩形に含まれるメッシュを取得するメッシュ取得ステップと、
パラメータ算出手段が、前記２点を矩形とするメッシュを対象として、自由度の数値の和ｃと面積の和Ｓを求め、該面積の和Ｓが小さいほど、また、該自由度の数値の和ｃが大きいほど小さくなるパラメータｐを算出するパラメータ算出ステップと、
推定手段が、入力された前記２点の座標と前記パラメータｐを用いたＬｐノルムを用いて道のりを推定する推定ステップと、
を行うことを特徴とする道のり推定方法。
【請求項５】
前記パラメータ算出ステップにおいて、
前記パラメータｐを求める際に、
【数７】
（但し、αは調整のためのパラメータ定数）
を用い、ｐの値が負となった場合はｐ＝０とし、ｐの値が概ね１〜２の値となるように決定する
請求項４記載の道のり推定方法。
【請求項６】
前記推定ステップにおいて、
前記道のりを求める際に、
【数８】
(但し、βは事前に設定したパラメータ定数、ｘ１，ｘ２，ｙ１，ｙ２は前記入力された２点の座標)
を用い、２点が完全に一致であれば０、ｘ座標とｙ座標のうち、いずれか１つが異なればβ、ｘ座標、ｙ座標ともに異なればβ×２であるとする
請求項４記載の道のり推定方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載の道のり推定装置の各手段として機能させる道のり推定プログラム。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１３−９２４３４（Ｐ２０１３−９２４３４Ａ）
【公開日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願番号】特願２０１１−２３４２６０（Ｐ２０１１−２３４２６０）
【出願日】平成２３年１０月２５日（２０１１．１０．２５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願日】平成２３年１０月２５日（２０１１．１０．２５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]