ルート検索装置、方法、及びコンピュータプログラム
【課題】移動軌跡を基にして、道路状況等を反映させたルート検索を行うことができる。
【解決手段】移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部13と、軌跡データに基づいて、移動軌跡の出発点及び到着点を抽出する抽出手段としての条件抽出部14と、軌跡データに基づいて、移動軌跡上の一以上の通過地点を抽出する通過地点抽出手段としての条件抽出部と、出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、一以上の通過地点を経由地としたルート検索を行うルート検索部15と、を備える。
【解決手段】移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部13と、軌跡データに基づいて、移動軌跡の出発点及び到着点を抽出する抽出手段としての条件抽出部14と、軌跡データに基づいて、移動軌跡上の一以上の通過地点を抽出する通過地点抽出手段としての条件抽出部と、出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、一以上の通過地点を経由地としたルート検索を行うルート検索部15と、を備える。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、移動体のルート検索を行う装置に関する。
【背景技術】
【0002】
従来、移動体の移動軌跡を利用したルート表示装置として、例えば非特許文献1が知られている。
【0003】
非特許文献1のルート表示装置は、例えば、利用者が、よく使うルートを通るとき、他の人に道案内してもらったとき等にその移動軌跡を記録しておくことで、そのルートをもう一度通りたい場合に、記録しておいた移動軌跡をそのままルートとして表示させることが出来る。
【先行技術文献】
【非特許文献】
【0004】
【非特許文献1】パイオニア株式会社 DVDナビゲーションマップ Type2 P48−50
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、非特許文献1記載のルート表示のように、移動軌跡をそのままルートとして使用する場合には、GPS(Global Positioning System)の測位がずれてしまった位置データも含まれてしまうことがある。この場合、正確な移動軌跡をルートとして使用することが難しくなってしまう。
【0006】
また、移動軌跡をそのままルートとして使用した場合、交通状況は反映されない。例えば、車両での移動の際には、工事中の道路、渋滞中の道路がルートとして表示されてしまったりする。このため、移動軌跡を再現でき、かつ交通状況を反映させたルートを表示する装置が切望されていた。
【0007】
本発明の目的は、移動軌跡を基にして、道路状況等を反映させたルート検索を行うことが出来るルート検索装置を提供することにある。
【課題を解決するための手段】
【0008】
本発明の一つの実施態様に従うルート検索装置は、移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部と、前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出する抽出手段と、前記軌跡データに基づいて、前記移動軌跡上の一以上の通過地点を抽出する通過地点抽出手段と、前記出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、前記一以上の通過地点を経由地としたルート検索を行うルート検索手段と、を備える。
【0009】
好適な実施態様では、前記移動軌跡上の一以上の通過地点は、前記移動軌跡を所定条件に基づいて複数に分割したときの分割点としてもよい。
【0010】
好適な実施態様では、前記分割点は、前記移動軌跡を、同じ長さを有する複数の区間に分割した点であってもよい。
【0011】
好適な実施形態では、前記通過地点抽出手段は、前記移動軌跡を、折れ線近似によって得られた折れ線と、前記移動軌跡との交点を前記移動軌跡上の1以上の通過地点として抽出してもよい。
【0012】
好適な実施形態では、前記通過地点抽出手段は、前記抽出手段によって抽出された、前記移動軌跡の前記出発点及び前記到着点を、それぞれ出発地及び目的地として仮ルート検索を行い、前記仮ルートと、前記移動軌跡との間の距離に基づいて、前記移動軌跡上の1以上の通過地点を抽出してもよい。
【図面の簡単な説明】
【0013】
【図1】本発明の第1実施形態にかかるルート検索装置の機能ブロック図である。
【図2】図1の軌跡データ生成部が行うフィルタリング処理の概要説明するための図である。
【図3】図1の軌跡データ記憶部に記憶されたデータ構造の一例を示す図である。
【図4】図1の端末装置に表示されたルート検索の条件設定画面を示す図である。
【図5】第1実施形態における、通過地点の抽出及びルート検索を説明するための図である。
【図6】第2実施形態における、折れ線近似の方法を説明するための図である。
【図7】仮ルートから最も乖離した移動軌跡上の通過地点を抽出する方法を示すフローチャートである
【図8】第3実施形態における、通過地点の抽出を説明するための図である。
【図9】第3実施形態に係るルート検索装置の動作を表すフローチャートである
【図10】第3実施形態における、通過地点の抽出を説明するための図である。
【図11】第3実施形態における、通過地点の抽出を説明するための図である。
【発明を実施するための形態】
【0014】
<第1実施形態>
以下、本発明の第1実施形態に係るルート検索装置を一例に挙げ、図面を参照して詳細に説明する。
【0015】
図1は、端末装置3に接続されたルート検索装置1の機能ブロック図である。
【0016】
図示例では、端末装置3は、ネットワークを2介してルート検索装置1に接続されているが、端末装置3の内部にルート検索装置1を設けてもよい。
【0017】
端末装置3は、図示例のように、携帯電話等の移動通信機器を用いてもよいし、自動車などの車両4に固定的に搭載される車載用の端末、車両4に着脱自在に搭載される端末等、様々な種類の端末装置を用いてもよい。
【0018】
端末装置3は、図示しないGPS受信機を備える。GPS受信機は、複数のGPS衛星5から日時データを含む電波を受信し、端末装置3の現在位置を測位する。端末装置3は、自身の端末装置3を特定するための端末IDと、測位データとを、ネットワーク2を介してルート検索装置1に送信する。なおここでいう、測位データには、GPS受信機により、所定距離間隔(例えば10m毎)、又は、所定時間間隔(例えば1秒毎)に測位された端末装置3の位置を示す測位点(緯度及び経度)及び測位された日時が含まれる。
【0019】
端末装置3は、ルート検索装置1から受信した後述するルートデータ及び地図データに基づいて、検索したルートをディスプレイ上に表示する。
【0020】
ルート検索装置1は、出発地から目的地までのルートを現在の交通情報を加味して検索し、検索したルートを端末装置3に送信するルート検索機能を備えた装置である。ルート検索機能は、ルート検索装置1内部の図示しないプロセッサ及びメモリを用いて所定のプログラムを実行することにより実現される。なお、ルート検索装置1は、ナビゲーション機能を併せて備えてもよい。
【0021】
ルート検索装置1は、入出力部11と、軌跡データ生成部12と、軌跡データ記憶部13と、条件抽出部14と、ルート検索部15と、ルート記憶部16と、地図情報記憶部17とを主に備える。
【0022】
入出力部11は、端末装置3との間でデータの送受信を行う。入出力部11は、例えば、端末装置3から端末ID及び測位データを受信し、受信した端末ID及び測位データを軌跡データ生成部12へ送信する。また例えば、入出力部11は、後述するルートデータ及び地図データを端末装置3へ送信する。
【0023】
軌跡データ生成部12は、端末装置3が送信した端末ID及び測位データを、入出力部11を介して受信し、これら端末ID及び測位データから軌跡データ生成し、軌跡データ記憶部13に記憶する。軌跡データは、例えば、測位データの異常値を取り除くフィルタリング処理、一連の連続する測位点を移動軌跡Tとしてグループ化する処理等によって生成される。以下に、軌跡データ生成のための各処理を詳細に説明する。
【0024】
まず、フィルタリング処理について説明する。
【0025】
図2は、軌跡データ生成部12が行う、フィルタリング処理の概要を説明するための図である。
【0026】
軌跡データ生成部12は、入出力部11から測位データを受け取ると、順次フィルタリング処理を行う。フィルタリング処理は、複数の測位点の中から、異常値を示す測位点(以下、異常点という)を取り除く処理である。なお、本実施形態では、フィルタリング処理は、軌跡データを生成するための一過程として行っているが、フィルタリング処理を行うタイミングは、これだけには限られない。例えば、フィルタリング処理は、軌跡データを生成する際に行われた後、さらに、後述するルート検索の際にも行われるようにしてもよいし、ルート検索の際にのみ行われるようにしてもよい。
【0027】
図2(a)は、フィルタリング処理によって、異常点が検出される過程を説明するための図である。
【0028】
軌跡データ生成部12は、例えば、連続する測位点について、これら測位点間の距離に基づき異常点を検出し、取り除く。例えば、D1、D2、D3の順に測位された測位点について、まず軌跡データ生成部12は、測位点D1、D2間の距離を算出する。このとき、例えば、2つの測位点D1、D2間が所定距離内である場合には、D2は正常な測位点として扱われる。一方、図2(a)のように、測位点D1、D2間の距離が所定(図示例では300m)以上離れている場合には、軌跡データ生成部12は、続いて測位点D1、D3間の距離を算出する。ここでは、測位点D1、D3間の距離は300m以上離れていない。このため、軌跡データ生成部12は、測位点D1、D3が連続し、測位点D2は異常値を示すものと判断し、D2のみを異常点として検出し、取り除く。
【0029】
図2(b)は、フィルタリング処理による、他の例を説明するための図である。
【0030】
図2(b)では、測位点は、D4、D5、D6の順に測位されたものとする。図示例では、D4、D5間の距離が300m離れているが、D4、D6間も距離が300m以上離れている。この場合には、例えば、端末装置3を乗せた車両4がトンネル内を走行しているなど、何らかの事情で300m以上測位データが受信されなかったものと判断し、フィルタリング処理部はD4を異常点と扱わず正常な測位点とする。
【0031】
次に、移動軌跡Tを形成するための処理を説明する。本明細書中では、移動軌跡Tは、所定ルールに基づいてグループ化された、連続する複数の測位点のことをいう。この場合の所定ルールは、どのように設定してもよい。例えば、連続する2つの測位点間の距離又は時間が、それぞれ所定範囲以内である複数の測位点をグループ化するというルールにしてもよい。また、移動軌跡Tを構成する複数の測位点のうち、最も早い日時の点を出発点とし、最も遅い日時の点を到着点としてもよい。
【0032】
軌跡データ生成部12は、フィルタリング処理を行った後の測位データを用いて、所定ルールに基づいてグループ化し、移動軌跡Tとして同じ軌跡IDを付与する。例えば、軌跡データ生成部12は、連続する2つの測位点が、所定以上時間間隔が空いた場合には、後の測位点から次の移動軌跡Tとして扱ってもよい。また例えば、軌跡データ生成部12は、連続する測位点のうち、前後2つの測位点について、所定以上距離の差が開いた場合には、後の測位点から次の移動軌跡Tとして扱ってもよい。なお、上記のように、移動軌跡Tを形成することで、1つの移動軌跡Tに所定数以下しか測位点が存在しなくなった場合には、これらの測位点を移動軌跡Tと扱わなくてもよい。
【0033】
軌跡データ生成部12は、フィルタリング処理によって異常点を取り除いた後の測位データに、端末ID及び軌跡IDを対応づけて軌跡データ記憶部13に記憶する。
【0034】
軌跡データ記憶部は13、端末装置3の移動軌跡Tを示す軌跡データが格納される記憶部である。
【0035】
図3は、軌跡データ記憶部13内に記憶されたデータ構造の一例としての、端末装置3毎の軌跡データテーブル20である。
【0036】
端末装置3毎(各端末ID21)の軌跡データテーブル20には、例えば、軌跡ID22、位置23、日時24、及びフラグ25が記憶される。
【0037】
軌跡ID22は、移動軌跡Tを識別するためのIDである。位置23は、測位点の緯度(Xn)及び経度(Yn)である。日時24は、位置23が測位された日時を示す。フラグ25には、軌跡ID22の中で最も早い日時のものが出発点、最も遅い日時のものが到着点として記録される。
【0038】
条件抽出部14は、軌跡データ記憶部13から移動軌跡Tの出発点及び到着点を抽出する。例えば、条件抽出部14は、軌跡データ記憶部13から所望の軌跡ID22を有する軌跡データをすべて読み出す。そして、読みだした軌跡データの中から、フラグ25が出発点及び到着点であるデータを抽出する。
【0039】
また、条件抽出部14は、読みだした軌跡データの中から、移動軌跡T上の一以上の通過地点を抽出する。通過地点の抽出には様々な方法があるが、例えば、以下のようにしてもよい。
【0040】
すなわち、移動軌跡Tを所定条件に基づいて複数に分割したときの分割点を通過地点として抽出してもよい。この場合、例えば通過地点は、移動軌跡Tを、およそ同じ長さ(距離)を有する複数の区間に分割した分割点としてもよいし、日時データ24に基づいて時間的に略等間隔な複数の区間に分割した分割点としてもよい。例えば、分割点は、軌跡データから、略均等な距離又は時間間隔を有する複数の位置23としてもよい。なお、通過地点の数は、予め設定しておいてもよい。これは例えば、利用者が手動で設定してもよいし、デフォルトで設定されていてもよい。
【0041】
条件抽出部14は、抽出した出発点、到着点、及び通過地点をルート検索部15に通知する。
【0042】
ルート検索部は15、条件抽出部14からの通知を受けると、出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、一以上の通過地点を経由地としたルート検索を行う。
【0043】
ルート検索部15は、また、ルート検索の際には現在の交通情報を加味して最適なルートを検索するようにしてもよい。
【0044】
ルート検索部15は、検索したルートのルートデータをルート記憶部16に格納する。ルート検索部15は、検索したルートのルートデータを、地図情報記憶部17から抽出した周辺の地図データとともに入出力部11を介して、端末装置3に送信する。
【0045】
次に、第1実施形態におけるルート検索装置1の動作を説明する。
【0046】
図4は、端末装置3のディスプレイに表示されたルート検索の条件設定画面31を示す図である。図5(a)は、第1実施形態における、通過地点の抽出を説明するための図である。図5(b)は第1実施形態における、ルート検索を説明するための図である。
【0047】
利用者は、図4に示す条件設定画面31から、ルート検索のための設定条件を選択する。設定条件は、例えば、有料道路の利用の有無等の選択32と、どの移動軌跡Tを利用するかの選択33である。例えば、利用者は、このような設定条件の選択によって、有料道路等、自分の通りたい道を選択することができ、また、以前通ったことのある移動軌跡に基づいたルート検索を行うことができる。以下には、いずれかの移動軌跡Tを選択した場合のルート検索について説明する。
【0048】
端末装置3は、条件設定画面31で選択された設定条件をルート検索装置1に送信する。
【0049】
設定条件を受信したルート検索装置1の条件抽出部14は、設定条件に基づいて、軌跡データ記憶部13から所望の移動軌跡Tの軌跡データを読み出し、その中から出発点、到着点及び通過地点を抽出する。
【0050】
図5(a)では、出発点Sから到着点Gまでの移動軌跡Tを、同じ長さ(距離)を有する複数の区間に分割した4つの通過地点p10〜p13が抽出されている。条件抽出部14は、抽出された出発点S、到着点G及び通過地点p10〜p13をルート検索部15に通知する。
【0051】
ルート検索部15は、通知された出発点S、到着点G及び通過地点p10〜p13に基づいてルート検索を行う。図5(b)は、出発点Sを出発地、到着点Gを目的地とし、4つの通過地点p10〜p13を経由地としてルート検索を行った結果である。点線で示されたルートが検索されたルートである。この場合、前述したように、利用者が端末装置3を介して有料道路の使用の有無等の条件を設定していれば、ルート検索部15は、その条件を反映させたルート検索を行うこととなる。
【0052】
本発明に係る第1実施形態によれば、移動軌跡T上の通過地点を経由地に設定することで、以前通った道に基づいて、道路状況などを反映させたルート検索を行うことができる。
<第2実施形態>
【0053】
次に、第2実施形態について説明する。
【0054】
上述の第1実施形態では、条件抽出部14は、移動軌跡Tを所定条件に基づいて複数に分割したときの分割点を通過地点として抽出していたが、これに限定されない。
【0055】
例えば、第2実施形態では、条件抽出部14は、移動軌跡Tを、折れ線近似によって得られた折れ線と、移動軌跡Tとの交点を移動軌跡T上の一以上の通過地点として抽出する機能をさらに有するようにしてもよい。また例えば、この折れ線近似は、出発地と目的地とを結ぶ仮想直線からの距離が極大となる移動軌跡Tとの交点を、通過地点として抽出するようにしてもよい。
【0056】
上記した、出発地と目的地とを結ぶ仮想直線からの距離が極大となる移動軌跡Tとの交点を、通過地点として抽出する折れ線近似の方法について、図6を参照して以下に詳細に説明する。しかしながら、折れ線近似の方法は、以下に説明するものに限定されるものではない。
【0057】
図6(a)は、第1の通過地点を決定する方法を説明する図である。
【0058】
条件抽出部14は、まず、出発点Sと到着点Gの間を、直線I1で結ぶ。
【0059】
次に、条件抽出部14は、直線I1と移動軌跡Tとを、所定間隔ごとに、直線I1に直交する直線I2で結ぶ。なお、図示例のI2の間隔は、説明のために設定したものであり、これに限られない。
【0060】
条件抽出部14は、直線I1から移動軌跡Tまでにおいて、長さが最も長い直線I2と、移動軌跡Tとの交点を第1の通過地点P21に設定する。
【0061】
図6(b)は、第2及び第3の通過地点を決定する方法を説明する図である。
【0062】
条件抽出部14は、移動軌跡T上に位置する、出発点S、到着点G及び第1の通過地点p21を折れ線で結び、移動軌跡の近似を行う。換言すると、条件抽出部14は、出発点Sと第1の通過地点P21、第1の通過地点p21と到着点Gとの間を、それぞれ直線I11、I12で結ぶ。
【0063】
次に条件抽出部14は、直線I11及びI12と移動軌跡Tとを、所定間隔ごとに直線I11及びI12に直交する直線I2で結ぶ(図示なし)。
【0064】
そして、直線I11に直交する最も長い直線I2と、移動軌跡Tとの交点をp22とし、直線I12に直交する最も長い直線I2と、移動軌跡Tの交点をp23とする。
【0065】
図6(c)は、第2及び第3の通過地点を折れ線で結んで近似する方法を説明する図である。
【0066】
条件抽出部14は、移動軌跡T上に位置する、出発点S、到着点G、第1の通過地点p21、第2の通過地点p22、第3の通過地点p23を折れ線で結び、再度、移動軌跡の近似を行う。換言すると、条件抽出部14は、出発地と第2の通過地点P22、第2の通過地点p22と第1の通過地点p21、第1の通過地点p21と第3の通過地点p23、第3の通過地点p23と到着地との間を、それぞれ直線I13、I14、I15、I16で結ぶ。
【0067】
ルート検索の際には、条件抽出部14は、移動軌跡Tの出発点S、到着点Gとともに、上記のように抽出した通過地点p21〜23をルート検索部15に通知する。そして、ルート検索部15は、通知された出発点Sを出発地、到着点Gを目的地、通過地点p21〜23を経由地としてルート検索を行う。
【0068】
本発明に係る第2実施形態によれば、移動軌跡T上の通過地点を経由地に設定することで、以前通った軌跡に基づき、かつ道路状況などを反映させたルート検索を行うことができる。また、第1実施形態のように経由地を移動軌跡T上に略均等に設定した場合に比べて、移動軌跡Tにより近似したルート検索を行うことができる。
<第3実施形態>
【0069】
次に、第3実施形態について説明する。
【0070】
条件抽出部14及びルート検索部15の機能は、上述した第1実施形態及び第2実施形態に例示した機能には限定されない。以下の第3実施形態に示す機能をさらに有してもよい。
【0071】
第3実施形態では、条件抽出部14は、移動軌跡Tの出発点S及び到着点Gを、それぞれ出発地及び目的地とした仮ルート検索をルート検索部15に行わせ、移動軌跡T上の通過地点であって、仮ルート上にはない一以上の通過地点を抽出してもよい。
【0072】
この場合、例えば、条件抽出部14は、仮ルート検索をルート検索部15に依頼するとともに、抽出した出発点S及び到着点Gの軌跡データをルート検索部15に通知する。また、条件抽出部14は、ルート検索部15から仮ルート検索により生成されたルートデータを受信し、ルートデータに基づいて、通過地点の軌跡データを抽出する。詳細は後述する。
【0073】
またこの場合、ルート検索部15は、条件抽出部14から通知された出発点S及び到着点Gの軌跡データをそれぞれ出発地及び目的地として、仮ルート検索を行う。ルート検索部15は、また、仮ルート検索により生成されたルートデータを条件抽出部14に送信する。
【0074】
第3実施形態では、条件抽出部14が抽出する一以上の通過地点は、仮ルートと最も乖離している移動軌跡T上の通過地点を含んでもよい。例えば、条件抽出部14が抽出する一以上の通過地点は、仮ルート上に複数存在するノードのそれぞれについて、各ノードから移動軌跡Tまでの最短距離を算出し、算出した各ノードからの最短距離のうち最長距離となるノードに対応する移動軌跡T上の地点としてもよい。通過地点を抽出する方法の具体例を以下に説明する。
【0075】
図7は、仮ルートから最も乖離した移動軌跡上の通過地点を抽出する方法を示すフローチャートである。図8は、移動軌跡T及び仮ルートIRから通過地点を抽出する方法を説明するため図である。
【0076】
まず、条件抽出部14は軌跡データ記憶部13から軌跡データを読み出し、測位点(位置23)を抽出する(ステップS100)。
【0077】
次に条件抽出部14は、ルート検索部15から受け取った仮ルートのルートデータから、各リンクをつなぐノードを抽出する(ステップS101)。
【0078】
次に、条件抽出部14は、ステップS100で抽出した各測位点(位置23)及びステップS111で抽出した各ノードに基づいて、各ノードから最も近い測位点(位置23)をそれぞれ検索する(ステップS102)。
【0079】
図8(a)は移動軌跡Tと仮ルートIRの拡大図である。説明のため、移動軌跡T上の測位点(位置23)をD11〜D16で示し、仮ルートIR上のノードをN1〜N3とした。図8(a)を参照して、ある1つのノードN1について最も近い測位点(位置23)を検索する様子を説明する。例えば、条件抽出部14は、ノードN1と移動軌跡T上のすべての測位点(位置23)との距離を算出し、最も近い距離を選択する。図示例の場合、移動軌跡上T上のすべての測位点(位置23)のうちどれが一番近いかを、例えばD11、D12、D13、D14、D15、D16というように順次検索する。ノードN1といちばん近い測位点はD11であるので、これらを直線で結ぶ。
【0080】
上記処理を、条件抽出部14は、仮ルート上の複数のノードについて行う。図8(b)では、N1とD11、N2とD14、N3とD16とが、それぞれ直線で結ばれている。
【0081】
条件抽出部14は、ステップ102の結果から、各ノード及び各測位点(位置23)を結ぶ直線の距離が一番長いものを抽出する(ステップS103)。
【0082】
図示例ではN2とD14を結ぶ直線の距離が一番長い。このため、この直線と移動軌跡Tとの交点であるD14が通過地点(例えばP30)として抽出される。
【0083】
また、第3実施形態では、ルート検索部15が、条件抽出部14で抽出された通過地点を経由地として仮ルート検索を再度行う再仮ルート処理と、条件抽出部14が、再仮ルート検索により抽出された仮ルート上にはない、移動軌跡T上の通過地点を再度抽出する再抽出処理とを、所定回数繰り返し、ルート検索部15は、再仮ルート処理及び再抽出処理が、所定回数繰り返されて抽出された通過地点を経由地としてルート検索を行ってもよい。例えば、再仮ルート処理及び再抽出処理の繰り返し回数は、経由地をいくつ設けるかによって設定するようにしてもよい。利用者が手動で設定してもよいし、デフォルトで設定されていてもよい。
【0084】
次に、第3実施形態に係るルート検索装置1の動作を図9〜11を用いて以下に説明する。
【0085】
図9は、第3実施形態に係るルート検索装置1の動作を表すフローチャートである。図10は、第3実施形態における、通過地点の抽出方法を説明するための図である。図11は、第3実施形態における、通過地点の抽出方法を説明するための図である。
【0086】
端末装置3は、利用者がルート検索の条件設定画面31から入力した設定条件を(図4参照)送信し、ルート検索装置1の条件抽出部14は、この設定条件を受信する(ステップS110)。
【0087】
S110で設定条件を受信した条件抽出部14は、その設定条件に基づいて、軌跡データ記憶部13から軌跡データを読み出し、この中から出発点S及び到着点Gを抽出する(ステップS111)。
【0088】
そして、条件抽出部14は、抽出した出発点S及び到着点Gをルート検索部15に通知し、仮ルート検索を依頼する。
【0089】
ルート検索部15は、条件抽出部14から通知された出発点Sを出発地、到着点Gを目的地として仮ルート検索を行う(ステップS112)。
【0090】
図10(a)は、ルート検索部15による1回目の仮ルート検索の結果である。出発地から目的地までの移動軌跡Tを実線で示し、検索された仮ルートIRを二点鎖線で示す。ルート検索部15は、検索した仮ルートのルートデータを条件抽出部14に通知する。
【0091】
条件抽出部14は、ルート検索部15から通知された仮ルートのルートデータ及びステップS111で軌跡データ記憶部13から読み出した軌跡データに基づいて、通過地点を抽出する(ステップS113)。
【0092】
図10(b)は、ステップS113によって、第1の通過地点p40が抽出された様子を示す。ここでは、上述したように、仮ルートから最も乖離した移動軌跡T上の点を第1の通過地点p40とした。
【0093】
条件抽出部14は、抽出した通過地点が所定数に達したか否かを判定する(ステップS114)。なお、前述したとおり、通過地点の数は予め設定しておいてもよい。
【0094】
通過地点が所定数に達していない場合には(ステップS114:No)、ステップS112及びステップS113を再度行う。
【0095】
この場合、条件抽出部14は、移動軌跡Tの出発点S、到着点G、及び、ステップS113によって抽出されたすべての通過地点をルート検索部15に通知する。通知を受けたルート検索部15は、出発点Sを出発地、到着点Gを目的地、通過地点を経由地として、再度仮ルート検索が行う(ステップS112)。
【0096】
図11(a)は、ルート検索部15による2回目の仮ルート検索及び第2の通過地点抽出の結果である。検索された仮ルートIRは第1の通過地点p40を経由地としている。また、検索された仮ルートから最も乖離した移動軌跡上の点を第2の通過地点p50としている。
【0097】
図11(b)は、ルート検索部15による3回目の仮ルート検索及び第3の通過地点抽出の結果である。検索された仮ルートIRは第1の通過地点p40、第2の通過地点p50を経由地としている。また、検索された仮ルートから最も乖離した移動軌跡T上の点を第3の通過地点p60としている。
【0098】
通過地点が所定数に達した場合には(ステップS114:Yes)、条件抽出部14は、移動軌跡Tの出発点S、到着点G及び抽出したすべての通過地点をルート検索部15に通知する。そして、ルート検索部15は、通知された出発点Sを出発地、到着点Gを目的地、通過地点を経由地としてルート検索を行う(ステップS115)。
【0099】
本発明に係る第3実施形態によれば、移動軌跡T上の通過地点を経由地に設定することで、以前通った道に基づいて、道路状況などを反映させたルート検索を行うことができる。また、第1実施形態のように経由地を移動軌跡T上に略均等に設定した場合に比べて、移動軌跡Tにより近いルート検索を行うことができる。また、本実施形態では、経由地の設定に仮ルートを使用するため、経由地の選択においても、有料道路等の各種道路状況、道路状況などを考慮することができる。
【0100】
上述した実施形態1〜3に示す条件抽出部14の機能を組み合わせてもよい。例えば、第3実施形態に示すように、仮ルートを利用して通過地点を所定数抽出した後、抽出した通過地点を折れ線で結び、以降、第2実施形態に示した折れ線近似によって、移動軌跡上の通過地点をさらに抽出してもよい。
【0101】
上述した本発明の実施形態は、本発明の説明のための例示であり、本発明の範囲をそれらの実施形態にのみ限定する趣旨ではない。当業者は、本発明の要旨を逸脱することなしに、他の様々な態様で本発明を実施することができる。
【符号の説明】
【0102】
1 ルート検索装置
2 ネットワーク
3 端末装置
11 入出力部
12 軌跡データ生成部
13 軌跡データ記憶部
14 条件抽出部
15 ルート検索部
16 ルート記憶部
17 地図情報記憶部
IR 仮ルート
T 移動軌跡
【技術分野】
【0001】
本発明は、移動体のルート検索を行う装置に関する。
【背景技術】
【0002】
従来、移動体の移動軌跡を利用したルート表示装置として、例えば非特許文献1が知られている。
【0003】
非特許文献1のルート表示装置は、例えば、利用者が、よく使うルートを通るとき、他の人に道案内してもらったとき等にその移動軌跡を記録しておくことで、そのルートをもう一度通りたい場合に、記録しておいた移動軌跡をそのままルートとして表示させることが出来る。
【先行技術文献】
【非特許文献】
【0004】
【非特許文献1】パイオニア株式会社 DVDナビゲーションマップ Type2 P48−50
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、非特許文献1記載のルート表示のように、移動軌跡をそのままルートとして使用する場合には、GPS(Global Positioning System)の測位がずれてしまった位置データも含まれてしまうことがある。この場合、正確な移動軌跡をルートとして使用することが難しくなってしまう。
【0006】
また、移動軌跡をそのままルートとして使用した場合、交通状況は反映されない。例えば、車両での移動の際には、工事中の道路、渋滞中の道路がルートとして表示されてしまったりする。このため、移動軌跡を再現でき、かつ交通状況を反映させたルートを表示する装置が切望されていた。
【0007】
本発明の目的は、移動軌跡を基にして、道路状況等を反映させたルート検索を行うことが出来るルート検索装置を提供することにある。
【課題を解決するための手段】
【0008】
本発明の一つの実施態様に従うルート検索装置は、移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部と、前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出する抽出手段と、前記軌跡データに基づいて、前記移動軌跡上の一以上の通過地点を抽出する通過地点抽出手段と、前記出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、前記一以上の通過地点を経由地としたルート検索を行うルート検索手段と、を備える。
【0009】
好適な実施態様では、前記移動軌跡上の一以上の通過地点は、前記移動軌跡を所定条件に基づいて複数に分割したときの分割点としてもよい。
【0010】
好適な実施態様では、前記分割点は、前記移動軌跡を、同じ長さを有する複数の区間に分割した点であってもよい。
【0011】
好適な実施形態では、前記通過地点抽出手段は、前記移動軌跡を、折れ線近似によって得られた折れ線と、前記移動軌跡との交点を前記移動軌跡上の1以上の通過地点として抽出してもよい。
【0012】
好適な実施形態では、前記通過地点抽出手段は、前記抽出手段によって抽出された、前記移動軌跡の前記出発点及び前記到着点を、それぞれ出発地及び目的地として仮ルート検索を行い、前記仮ルートと、前記移動軌跡との間の距離に基づいて、前記移動軌跡上の1以上の通過地点を抽出してもよい。
【図面の簡単な説明】
【0013】
【図1】本発明の第1実施形態にかかるルート検索装置の機能ブロック図である。
【図2】図1の軌跡データ生成部が行うフィルタリング処理の概要説明するための図である。
【図3】図1の軌跡データ記憶部に記憶されたデータ構造の一例を示す図である。
【図4】図1の端末装置に表示されたルート検索の条件設定画面を示す図である。
【図5】第1実施形態における、通過地点の抽出及びルート検索を説明するための図である。
【図6】第2実施形態における、折れ線近似の方法を説明するための図である。
【図7】仮ルートから最も乖離した移動軌跡上の通過地点を抽出する方法を示すフローチャートである
【図8】第3実施形態における、通過地点の抽出を説明するための図である。
【図9】第3実施形態に係るルート検索装置の動作を表すフローチャートである
【図10】第3実施形態における、通過地点の抽出を説明するための図である。
【図11】第3実施形態における、通過地点の抽出を説明するための図である。
【発明を実施するための形態】
【0014】
<第1実施形態>
以下、本発明の第1実施形態に係るルート検索装置を一例に挙げ、図面を参照して詳細に説明する。
【0015】
図1は、端末装置3に接続されたルート検索装置1の機能ブロック図である。
【0016】
図示例では、端末装置3は、ネットワークを2介してルート検索装置1に接続されているが、端末装置3の内部にルート検索装置1を設けてもよい。
【0017】
端末装置3は、図示例のように、携帯電話等の移動通信機器を用いてもよいし、自動車などの車両4に固定的に搭載される車載用の端末、車両4に着脱自在に搭載される端末等、様々な種類の端末装置を用いてもよい。
【0018】
端末装置3は、図示しないGPS受信機を備える。GPS受信機は、複数のGPS衛星5から日時データを含む電波を受信し、端末装置3の現在位置を測位する。端末装置3は、自身の端末装置3を特定するための端末IDと、測位データとを、ネットワーク2を介してルート検索装置1に送信する。なおここでいう、測位データには、GPS受信機により、所定距離間隔(例えば10m毎)、又は、所定時間間隔(例えば1秒毎)に測位された端末装置3の位置を示す測位点(緯度及び経度)及び測位された日時が含まれる。
【0019】
端末装置3は、ルート検索装置1から受信した後述するルートデータ及び地図データに基づいて、検索したルートをディスプレイ上に表示する。
【0020】
ルート検索装置1は、出発地から目的地までのルートを現在の交通情報を加味して検索し、検索したルートを端末装置3に送信するルート検索機能を備えた装置である。ルート検索機能は、ルート検索装置1内部の図示しないプロセッサ及びメモリを用いて所定のプログラムを実行することにより実現される。なお、ルート検索装置1は、ナビゲーション機能を併せて備えてもよい。
【0021】
ルート検索装置1は、入出力部11と、軌跡データ生成部12と、軌跡データ記憶部13と、条件抽出部14と、ルート検索部15と、ルート記憶部16と、地図情報記憶部17とを主に備える。
【0022】
入出力部11は、端末装置3との間でデータの送受信を行う。入出力部11は、例えば、端末装置3から端末ID及び測位データを受信し、受信した端末ID及び測位データを軌跡データ生成部12へ送信する。また例えば、入出力部11は、後述するルートデータ及び地図データを端末装置3へ送信する。
【0023】
軌跡データ生成部12は、端末装置3が送信した端末ID及び測位データを、入出力部11を介して受信し、これら端末ID及び測位データから軌跡データ生成し、軌跡データ記憶部13に記憶する。軌跡データは、例えば、測位データの異常値を取り除くフィルタリング処理、一連の連続する測位点を移動軌跡Tとしてグループ化する処理等によって生成される。以下に、軌跡データ生成のための各処理を詳細に説明する。
【0024】
まず、フィルタリング処理について説明する。
【0025】
図2は、軌跡データ生成部12が行う、フィルタリング処理の概要を説明するための図である。
【0026】
軌跡データ生成部12は、入出力部11から測位データを受け取ると、順次フィルタリング処理を行う。フィルタリング処理は、複数の測位点の中から、異常値を示す測位点(以下、異常点という)を取り除く処理である。なお、本実施形態では、フィルタリング処理は、軌跡データを生成するための一過程として行っているが、フィルタリング処理を行うタイミングは、これだけには限られない。例えば、フィルタリング処理は、軌跡データを生成する際に行われた後、さらに、後述するルート検索の際にも行われるようにしてもよいし、ルート検索の際にのみ行われるようにしてもよい。
【0027】
図2(a)は、フィルタリング処理によって、異常点が検出される過程を説明するための図である。
【0028】
軌跡データ生成部12は、例えば、連続する測位点について、これら測位点間の距離に基づき異常点を検出し、取り除く。例えば、D1、D2、D3の順に測位された測位点について、まず軌跡データ生成部12は、測位点D1、D2間の距離を算出する。このとき、例えば、2つの測位点D1、D2間が所定距離内である場合には、D2は正常な測位点として扱われる。一方、図2(a)のように、測位点D1、D2間の距離が所定(図示例では300m)以上離れている場合には、軌跡データ生成部12は、続いて測位点D1、D3間の距離を算出する。ここでは、測位点D1、D3間の距離は300m以上離れていない。このため、軌跡データ生成部12は、測位点D1、D3が連続し、測位点D2は異常値を示すものと判断し、D2のみを異常点として検出し、取り除く。
【0029】
図2(b)は、フィルタリング処理による、他の例を説明するための図である。
【0030】
図2(b)では、測位点は、D4、D5、D6の順に測位されたものとする。図示例では、D4、D5間の距離が300m離れているが、D4、D6間も距離が300m以上離れている。この場合には、例えば、端末装置3を乗せた車両4がトンネル内を走行しているなど、何らかの事情で300m以上測位データが受信されなかったものと判断し、フィルタリング処理部はD4を異常点と扱わず正常な測位点とする。
【0031】
次に、移動軌跡Tを形成するための処理を説明する。本明細書中では、移動軌跡Tは、所定ルールに基づいてグループ化された、連続する複数の測位点のことをいう。この場合の所定ルールは、どのように設定してもよい。例えば、連続する2つの測位点間の距離又は時間が、それぞれ所定範囲以内である複数の測位点をグループ化するというルールにしてもよい。また、移動軌跡Tを構成する複数の測位点のうち、最も早い日時の点を出発点とし、最も遅い日時の点を到着点としてもよい。
【0032】
軌跡データ生成部12は、フィルタリング処理を行った後の測位データを用いて、所定ルールに基づいてグループ化し、移動軌跡Tとして同じ軌跡IDを付与する。例えば、軌跡データ生成部12は、連続する2つの測位点が、所定以上時間間隔が空いた場合には、後の測位点から次の移動軌跡Tとして扱ってもよい。また例えば、軌跡データ生成部12は、連続する測位点のうち、前後2つの測位点について、所定以上距離の差が開いた場合には、後の測位点から次の移動軌跡Tとして扱ってもよい。なお、上記のように、移動軌跡Tを形成することで、1つの移動軌跡Tに所定数以下しか測位点が存在しなくなった場合には、これらの測位点を移動軌跡Tと扱わなくてもよい。
【0033】
軌跡データ生成部12は、フィルタリング処理によって異常点を取り除いた後の測位データに、端末ID及び軌跡IDを対応づけて軌跡データ記憶部13に記憶する。
【0034】
軌跡データ記憶部は13、端末装置3の移動軌跡Tを示す軌跡データが格納される記憶部である。
【0035】
図3は、軌跡データ記憶部13内に記憶されたデータ構造の一例としての、端末装置3毎の軌跡データテーブル20である。
【0036】
端末装置3毎(各端末ID21)の軌跡データテーブル20には、例えば、軌跡ID22、位置23、日時24、及びフラグ25が記憶される。
【0037】
軌跡ID22は、移動軌跡Tを識別するためのIDである。位置23は、測位点の緯度(Xn)及び経度(Yn)である。日時24は、位置23が測位された日時を示す。フラグ25には、軌跡ID22の中で最も早い日時のものが出発点、最も遅い日時のものが到着点として記録される。
【0038】
条件抽出部14は、軌跡データ記憶部13から移動軌跡Tの出発点及び到着点を抽出する。例えば、条件抽出部14は、軌跡データ記憶部13から所望の軌跡ID22を有する軌跡データをすべて読み出す。そして、読みだした軌跡データの中から、フラグ25が出発点及び到着点であるデータを抽出する。
【0039】
また、条件抽出部14は、読みだした軌跡データの中から、移動軌跡T上の一以上の通過地点を抽出する。通過地点の抽出には様々な方法があるが、例えば、以下のようにしてもよい。
【0040】
すなわち、移動軌跡Tを所定条件に基づいて複数に分割したときの分割点を通過地点として抽出してもよい。この場合、例えば通過地点は、移動軌跡Tを、およそ同じ長さ(距離)を有する複数の区間に分割した分割点としてもよいし、日時データ24に基づいて時間的に略等間隔な複数の区間に分割した分割点としてもよい。例えば、分割点は、軌跡データから、略均等な距離又は時間間隔を有する複数の位置23としてもよい。なお、通過地点の数は、予め設定しておいてもよい。これは例えば、利用者が手動で設定してもよいし、デフォルトで設定されていてもよい。
【0041】
条件抽出部14は、抽出した出発点、到着点、及び通過地点をルート検索部15に通知する。
【0042】
ルート検索部は15、条件抽出部14からの通知を受けると、出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、一以上の通過地点を経由地としたルート検索を行う。
【0043】
ルート検索部15は、また、ルート検索の際には現在の交通情報を加味して最適なルートを検索するようにしてもよい。
【0044】
ルート検索部15は、検索したルートのルートデータをルート記憶部16に格納する。ルート検索部15は、検索したルートのルートデータを、地図情報記憶部17から抽出した周辺の地図データとともに入出力部11を介して、端末装置3に送信する。
【0045】
次に、第1実施形態におけるルート検索装置1の動作を説明する。
【0046】
図4は、端末装置3のディスプレイに表示されたルート検索の条件設定画面31を示す図である。図5(a)は、第1実施形態における、通過地点の抽出を説明するための図である。図5(b)は第1実施形態における、ルート検索を説明するための図である。
【0047】
利用者は、図4に示す条件設定画面31から、ルート検索のための設定条件を選択する。設定条件は、例えば、有料道路の利用の有無等の選択32と、どの移動軌跡Tを利用するかの選択33である。例えば、利用者は、このような設定条件の選択によって、有料道路等、自分の通りたい道を選択することができ、また、以前通ったことのある移動軌跡に基づいたルート検索を行うことができる。以下には、いずれかの移動軌跡Tを選択した場合のルート検索について説明する。
【0048】
端末装置3は、条件設定画面31で選択された設定条件をルート検索装置1に送信する。
【0049】
設定条件を受信したルート検索装置1の条件抽出部14は、設定条件に基づいて、軌跡データ記憶部13から所望の移動軌跡Tの軌跡データを読み出し、その中から出発点、到着点及び通過地点を抽出する。
【0050】
図5(a)では、出発点Sから到着点Gまでの移動軌跡Tを、同じ長さ(距離)を有する複数の区間に分割した4つの通過地点p10〜p13が抽出されている。条件抽出部14は、抽出された出発点S、到着点G及び通過地点p10〜p13をルート検索部15に通知する。
【0051】
ルート検索部15は、通知された出発点S、到着点G及び通過地点p10〜p13に基づいてルート検索を行う。図5(b)は、出発点Sを出発地、到着点Gを目的地とし、4つの通過地点p10〜p13を経由地としてルート検索を行った結果である。点線で示されたルートが検索されたルートである。この場合、前述したように、利用者が端末装置3を介して有料道路の使用の有無等の条件を設定していれば、ルート検索部15は、その条件を反映させたルート検索を行うこととなる。
【0052】
本発明に係る第1実施形態によれば、移動軌跡T上の通過地点を経由地に設定することで、以前通った道に基づいて、道路状況などを反映させたルート検索を行うことができる。
<第2実施形態>
【0053】
次に、第2実施形態について説明する。
【0054】
上述の第1実施形態では、条件抽出部14は、移動軌跡Tを所定条件に基づいて複数に分割したときの分割点を通過地点として抽出していたが、これに限定されない。
【0055】
例えば、第2実施形態では、条件抽出部14は、移動軌跡Tを、折れ線近似によって得られた折れ線と、移動軌跡Tとの交点を移動軌跡T上の一以上の通過地点として抽出する機能をさらに有するようにしてもよい。また例えば、この折れ線近似は、出発地と目的地とを結ぶ仮想直線からの距離が極大となる移動軌跡Tとの交点を、通過地点として抽出するようにしてもよい。
【0056】
上記した、出発地と目的地とを結ぶ仮想直線からの距離が極大となる移動軌跡Tとの交点を、通過地点として抽出する折れ線近似の方法について、図6を参照して以下に詳細に説明する。しかしながら、折れ線近似の方法は、以下に説明するものに限定されるものではない。
【0057】
図6(a)は、第1の通過地点を決定する方法を説明する図である。
【0058】
条件抽出部14は、まず、出発点Sと到着点Gの間を、直線I1で結ぶ。
【0059】
次に、条件抽出部14は、直線I1と移動軌跡Tとを、所定間隔ごとに、直線I1に直交する直線I2で結ぶ。なお、図示例のI2の間隔は、説明のために設定したものであり、これに限られない。
【0060】
条件抽出部14は、直線I1から移動軌跡Tまでにおいて、長さが最も長い直線I2と、移動軌跡Tとの交点を第1の通過地点P21に設定する。
【0061】
図6(b)は、第2及び第3の通過地点を決定する方法を説明する図である。
【0062】
条件抽出部14は、移動軌跡T上に位置する、出発点S、到着点G及び第1の通過地点p21を折れ線で結び、移動軌跡の近似を行う。換言すると、条件抽出部14は、出発点Sと第1の通過地点P21、第1の通過地点p21と到着点Gとの間を、それぞれ直線I11、I12で結ぶ。
【0063】
次に条件抽出部14は、直線I11及びI12と移動軌跡Tとを、所定間隔ごとに直線I11及びI12に直交する直線I2で結ぶ(図示なし)。
【0064】
そして、直線I11に直交する最も長い直線I2と、移動軌跡Tとの交点をp22とし、直線I12に直交する最も長い直線I2と、移動軌跡Tの交点をp23とする。
【0065】
図6(c)は、第2及び第3の通過地点を折れ線で結んで近似する方法を説明する図である。
【0066】
条件抽出部14は、移動軌跡T上に位置する、出発点S、到着点G、第1の通過地点p21、第2の通過地点p22、第3の通過地点p23を折れ線で結び、再度、移動軌跡の近似を行う。換言すると、条件抽出部14は、出発地と第2の通過地点P22、第2の通過地点p22と第1の通過地点p21、第1の通過地点p21と第3の通過地点p23、第3の通過地点p23と到着地との間を、それぞれ直線I13、I14、I15、I16で結ぶ。
【0067】
ルート検索の際には、条件抽出部14は、移動軌跡Tの出発点S、到着点Gとともに、上記のように抽出した通過地点p21〜23をルート検索部15に通知する。そして、ルート検索部15は、通知された出発点Sを出発地、到着点Gを目的地、通過地点p21〜23を経由地としてルート検索を行う。
【0068】
本発明に係る第2実施形態によれば、移動軌跡T上の通過地点を経由地に設定することで、以前通った軌跡に基づき、かつ道路状況などを反映させたルート検索を行うことができる。また、第1実施形態のように経由地を移動軌跡T上に略均等に設定した場合に比べて、移動軌跡Tにより近似したルート検索を行うことができる。
<第3実施形態>
【0069】
次に、第3実施形態について説明する。
【0070】
条件抽出部14及びルート検索部15の機能は、上述した第1実施形態及び第2実施形態に例示した機能には限定されない。以下の第3実施形態に示す機能をさらに有してもよい。
【0071】
第3実施形態では、条件抽出部14は、移動軌跡Tの出発点S及び到着点Gを、それぞれ出発地及び目的地とした仮ルート検索をルート検索部15に行わせ、移動軌跡T上の通過地点であって、仮ルート上にはない一以上の通過地点を抽出してもよい。
【0072】
この場合、例えば、条件抽出部14は、仮ルート検索をルート検索部15に依頼するとともに、抽出した出発点S及び到着点Gの軌跡データをルート検索部15に通知する。また、条件抽出部14は、ルート検索部15から仮ルート検索により生成されたルートデータを受信し、ルートデータに基づいて、通過地点の軌跡データを抽出する。詳細は後述する。
【0073】
またこの場合、ルート検索部15は、条件抽出部14から通知された出発点S及び到着点Gの軌跡データをそれぞれ出発地及び目的地として、仮ルート検索を行う。ルート検索部15は、また、仮ルート検索により生成されたルートデータを条件抽出部14に送信する。
【0074】
第3実施形態では、条件抽出部14が抽出する一以上の通過地点は、仮ルートと最も乖離している移動軌跡T上の通過地点を含んでもよい。例えば、条件抽出部14が抽出する一以上の通過地点は、仮ルート上に複数存在するノードのそれぞれについて、各ノードから移動軌跡Tまでの最短距離を算出し、算出した各ノードからの最短距離のうち最長距離となるノードに対応する移動軌跡T上の地点としてもよい。通過地点を抽出する方法の具体例を以下に説明する。
【0075】
図7は、仮ルートから最も乖離した移動軌跡上の通過地点を抽出する方法を示すフローチャートである。図8は、移動軌跡T及び仮ルートIRから通過地点を抽出する方法を説明するため図である。
【0076】
まず、条件抽出部14は軌跡データ記憶部13から軌跡データを読み出し、測位点(位置23)を抽出する(ステップS100)。
【0077】
次に条件抽出部14は、ルート検索部15から受け取った仮ルートのルートデータから、各リンクをつなぐノードを抽出する(ステップS101)。
【0078】
次に、条件抽出部14は、ステップS100で抽出した各測位点(位置23)及びステップS111で抽出した各ノードに基づいて、各ノードから最も近い測位点(位置23)をそれぞれ検索する(ステップS102)。
【0079】
図8(a)は移動軌跡Tと仮ルートIRの拡大図である。説明のため、移動軌跡T上の測位点(位置23)をD11〜D16で示し、仮ルートIR上のノードをN1〜N3とした。図8(a)を参照して、ある1つのノードN1について最も近い測位点(位置23)を検索する様子を説明する。例えば、条件抽出部14は、ノードN1と移動軌跡T上のすべての測位点(位置23)との距離を算出し、最も近い距離を選択する。図示例の場合、移動軌跡上T上のすべての測位点(位置23)のうちどれが一番近いかを、例えばD11、D12、D13、D14、D15、D16というように順次検索する。ノードN1といちばん近い測位点はD11であるので、これらを直線で結ぶ。
【0080】
上記処理を、条件抽出部14は、仮ルート上の複数のノードについて行う。図8(b)では、N1とD11、N2とD14、N3とD16とが、それぞれ直線で結ばれている。
【0081】
条件抽出部14は、ステップ102の結果から、各ノード及び各測位点(位置23)を結ぶ直線の距離が一番長いものを抽出する(ステップS103)。
【0082】
図示例ではN2とD14を結ぶ直線の距離が一番長い。このため、この直線と移動軌跡Tとの交点であるD14が通過地点(例えばP30)として抽出される。
【0083】
また、第3実施形態では、ルート検索部15が、条件抽出部14で抽出された通過地点を経由地として仮ルート検索を再度行う再仮ルート処理と、条件抽出部14が、再仮ルート検索により抽出された仮ルート上にはない、移動軌跡T上の通過地点を再度抽出する再抽出処理とを、所定回数繰り返し、ルート検索部15は、再仮ルート処理及び再抽出処理が、所定回数繰り返されて抽出された通過地点を経由地としてルート検索を行ってもよい。例えば、再仮ルート処理及び再抽出処理の繰り返し回数は、経由地をいくつ設けるかによって設定するようにしてもよい。利用者が手動で設定してもよいし、デフォルトで設定されていてもよい。
【0084】
次に、第3実施形態に係るルート検索装置1の動作を図9〜11を用いて以下に説明する。
【0085】
図9は、第3実施形態に係るルート検索装置1の動作を表すフローチャートである。図10は、第3実施形態における、通過地点の抽出方法を説明するための図である。図11は、第3実施形態における、通過地点の抽出方法を説明するための図である。
【0086】
端末装置3は、利用者がルート検索の条件設定画面31から入力した設定条件を(図4参照)送信し、ルート検索装置1の条件抽出部14は、この設定条件を受信する(ステップS110)。
【0087】
S110で設定条件を受信した条件抽出部14は、その設定条件に基づいて、軌跡データ記憶部13から軌跡データを読み出し、この中から出発点S及び到着点Gを抽出する(ステップS111)。
【0088】
そして、条件抽出部14は、抽出した出発点S及び到着点Gをルート検索部15に通知し、仮ルート検索を依頼する。
【0089】
ルート検索部15は、条件抽出部14から通知された出発点Sを出発地、到着点Gを目的地として仮ルート検索を行う(ステップS112)。
【0090】
図10(a)は、ルート検索部15による1回目の仮ルート検索の結果である。出発地から目的地までの移動軌跡Tを実線で示し、検索された仮ルートIRを二点鎖線で示す。ルート検索部15は、検索した仮ルートのルートデータを条件抽出部14に通知する。
【0091】
条件抽出部14は、ルート検索部15から通知された仮ルートのルートデータ及びステップS111で軌跡データ記憶部13から読み出した軌跡データに基づいて、通過地点を抽出する(ステップS113)。
【0092】
図10(b)は、ステップS113によって、第1の通過地点p40が抽出された様子を示す。ここでは、上述したように、仮ルートから最も乖離した移動軌跡T上の点を第1の通過地点p40とした。
【0093】
条件抽出部14は、抽出した通過地点が所定数に達したか否かを判定する(ステップS114)。なお、前述したとおり、通過地点の数は予め設定しておいてもよい。
【0094】
通過地点が所定数に達していない場合には(ステップS114:No)、ステップS112及びステップS113を再度行う。
【0095】
この場合、条件抽出部14は、移動軌跡Tの出発点S、到着点G、及び、ステップS113によって抽出されたすべての通過地点をルート検索部15に通知する。通知を受けたルート検索部15は、出発点Sを出発地、到着点Gを目的地、通過地点を経由地として、再度仮ルート検索が行う(ステップS112)。
【0096】
図11(a)は、ルート検索部15による2回目の仮ルート検索及び第2の通過地点抽出の結果である。検索された仮ルートIRは第1の通過地点p40を経由地としている。また、検索された仮ルートから最も乖離した移動軌跡上の点を第2の通過地点p50としている。
【0097】
図11(b)は、ルート検索部15による3回目の仮ルート検索及び第3の通過地点抽出の結果である。検索された仮ルートIRは第1の通過地点p40、第2の通過地点p50を経由地としている。また、検索された仮ルートから最も乖離した移動軌跡T上の点を第3の通過地点p60としている。
【0098】
通過地点が所定数に達した場合には(ステップS114:Yes)、条件抽出部14は、移動軌跡Tの出発点S、到着点G及び抽出したすべての通過地点をルート検索部15に通知する。そして、ルート検索部15は、通知された出発点Sを出発地、到着点Gを目的地、通過地点を経由地としてルート検索を行う(ステップS115)。
【0099】
本発明に係る第3実施形態によれば、移動軌跡T上の通過地点を経由地に設定することで、以前通った道に基づいて、道路状況などを反映させたルート検索を行うことができる。また、第1実施形態のように経由地を移動軌跡T上に略均等に設定した場合に比べて、移動軌跡Tにより近いルート検索を行うことができる。また、本実施形態では、経由地の設定に仮ルートを使用するため、経由地の選択においても、有料道路等の各種道路状況、道路状況などを考慮することができる。
【0100】
上述した実施形態1〜3に示す条件抽出部14の機能を組み合わせてもよい。例えば、第3実施形態に示すように、仮ルートを利用して通過地点を所定数抽出した後、抽出した通過地点を折れ線で結び、以降、第2実施形態に示した折れ線近似によって、移動軌跡上の通過地点をさらに抽出してもよい。
【0101】
上述した本発明の実施形態は、本発明の説明のための例示であり、本発明の範囲をそれらの実施形態にのみ限定する趣旨ではない。当業者は、本発明の要旨を逸脱することなしに、他の様々な態様で本発明を実施することができる。
【符号の説明】
【0102】
1 ルート検索装置
2 ネットワーク
3 端末装置
11 入出力部
12 軌跡データ生成部
13 軌跡データ記憶部
14 条件抽出部
15 ルート検索部
16 ルート記憶部
17 地図情報記憶部
IR 仮ルート
T 移動軌跡
【特許請求の範囲】
【請求項1】
移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部と、
前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出する抽出手段と、
前記軌跡データに基づいて、前記移動軌跡上の一以上の通過地点を抽出する通過地点抽出手段と、
前記出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、前記一以上の通過地点を経由地としたルート検索を行うルート検索手段と、を備えたルート検索装置。
【請求項2】
前記移動軌跡上の一以上の通過地点は、前記移動軌跡を所定条件に基づいて複数に分割したときの分割点である、請求項1記載のルート検索装置。
【請求項3】
前記分割点は、前記移動軌跡を、同じ長さを有する複数の区間に分割した点である、請求項2記載のルート検索装置。
【請求項4】
前記通過地点抽出手段は、
前記移動軌跡を、折れ線近似によって得られた折れ線と、前記移動軌跡との交点を前記移動軌跡上の1以上の通過地点として抽出する、
請求項1記載のルート検索装置。
【請求項5】
前記通過地点抽出手段は、
前記抽出手段によって抽出された、前記移動軌跡の前記出発点及び前記到着点を、それぞれ出発地及び目的地として仮ルート検索を行い、
前記仮ルートと、前記移動軌跡との間の距離に基づいて、前記移動軌跡上の1以上の通過地点を抽出する、
請求項1記載のルート検索装置。
【請求項6】
ルート検索装置が行う方法であって、
移動体の移動軌跡を示す軌跡データをサーバに記憶するステップと、
前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出するステップと、
前記軌跡データに基づいて、前記移動軌跡上の一以上の通過地点を抽出するステップと、
前記出発点及び到着点をそれぞれ出発地及び目的地とし、且つ、前記一以上の通過地点を経由地としたルート検索を行うステップと、を備えた方法。
【請求項7】
ルート検索を行うためのコンピュータプログラムであって、
移動体の移動軌跡を示す軌跡データをサーバに記憶するステップと、
前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出するステップと、
前記軌跡データに基づいて、前記移動軌跡上の一以上の通過地点を抽出するステップと、
前記出発点及び到着点をそれぞれ出発地及び目的地とし、且つ、前記一以上の通過地点を経由地としたルート検索を行うステップと、をコンピュータに実行させるための実現されるコンピュータプログラム。
【請求項1】
移動体の移動軌跡を示す軌跡データを記憶する軌跡データ記憶部と、
前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出する抽出手段と、
前記軌跡データに基づいて、前記移動軌跡上の一以上の通過地点を抽出する通過地点抽出手段と、
前記出発点及び到着点をそれぞれ出発地及び目的地とし、かつ、前記一以上の通過地点を経由地としたルート検索を行うルート検索手段と、を備えたルート検索装置。
【請求項2】
前記移動軌跡上の一以上の通過地点は、前記移動軌跡を所定条件に基づいて複数に分割したときの分割点である、請求項1記載のルート検索装置。
【請求項3】
前記分割点は、前記移動軌跡を、同じ長さを有する複数の区間に分割した点である、請求項2記載のルート検索装置。
【請求項4】
前記通過地点抽出手段は、
前記移動軌跡を、折れ線近似によって得られた折れ線と、前記移動軌跡との交点を前記移動軌跡上の1以上の通過地点として抽出する、
請求項1記載のルート検索装置。
【請求項5】
前記通過地点抽出手段は、
前記抽出手段によって抽出された、前記移動軌跡の前記出発点及び前記到着点を、それぞれ出発地及び目的地として仮ルート検索を行い、
前記仮ルートと、前記移動軌跡との間の距離に基づいて、前記移動軌跡上の1以上の通過地点を抽出する、
請求項1記載のルート検索装置。
【請求項6】
ルート検索装置が行う方法であって、
移動体の移動軌跡を示す軌跡データをサーバに記憶するステップと、
前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出するステップと、
前記軌跡データに基づいて、前記移動軌跡上の一以上の通過地点を抽出するステップと、
前記出発点及び到着点をそれぞれ出発地及び目的地とし、且つ、前記一以上の通過地点を経由地としたルート検索を行うステップと、を備えた方法。
【請求項7】
ルート検索を行うためのコンピュータプログラムであって、
移動体の移動軌跡を示す軌跡データをサーバに記憶するステップと、
前記軌跡データに基づいて、前記移動軌跡の出発点及び到着点を抽出するステップと、
前記軌跡データに基づいて、前記移動軌跡上の一以上の通過地点を抽出するステップと、
前記出発点及び到着点をそれぞれ出発地及び目的地とし、且つ、前記一以上の通過地点を経由地としたルート検索を行うステップと、をコンピュータに実行させるための実現されるコンピュータプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2011−203012(P2011−203012A)
【公開日】平成23年10月13日(2011.10.13)
【国際特許分類】
【出願番号】特願2010−68607(P2010−68607)
【出願日】平成22年3月24日(2010.3.24)
【出願人】(000155469)株式会社野村総合研究所 (1,067)
【Fターム(参考)】
【公開日】平成23年10月13日(2011.10.13)
【国際特許分類】
【出願日】平成22年3月24日(2010.3.24)
【出願人】(000155469)株式会社野村総合研究所 (1,067)
【Fターム(参考)】
[ Back to top ]