マップマッチング装置、マップマッチング方法及びそのプログラム
【課題】携帯端末によって収集したプローブデータから、精度良くＤＲＭデータ上の移動経路を特定するマップマッチング装置を提供する。
【解決手段】制御部３は、移動系列単位に分割されたプローブデータを局所的に集約し、集約データを作成する。次に、制御部３は、集約データの移動方向を算出するとともに、集約データを関連付ける候補リンクを検索する。次に、制御部３は、候補リンクの中から集約データの移動方向に最も近い方向を持つ最寄りリンクを決定し、集約データの位置座標から最寄りリンクへ引いた垂線の足を最寄り点とする。そして、制御部３は、最寄り点の集合を用いて、移動経路に含めるリンクを１つずつ確定していき、移動経路を特定する。
【解決手段】制御部３は、移動系列単位に分割されたプローブデータを局所的に集約し、集約データを作成する。次に、制御部３は、集約データの移動方向を算出するとともに、集約データを関連付ける候補リンクを検索する。次に、制御部３は、候補リンクの中から集約データの移動方向に最も近い方向を持つ最寄りリンクを決定し、集約データの位置座標から最寄りリンクへ引いた垂線の足を最寄り点とする。そして、制御部３は、最寄り点の集合を用いて、移動経路に含めるリンクを１つずつ確定していき、移動経路を特定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング装置、マップマッチング方法及びそのプログラムに関するものである。
【背景技術】
【０００２】
現在、車両に搭載した装置を用いて、車両の走行履歴を調査・分析することが行われている。車両搭載装置が収集するデータは、一般に、プローブデータと呼ばれており、位置情報、時刻情報の他に、車両の速度、車両の向き、ハンドルの旋回状況、ブレーキングの状況等様々な情報が含まれていることが多い。そして、車両の走行履歴を調査・分析するため、こうしたプローブデータから、ノードとリンクとで構成されたデジタル道路地図（ＤＲＭ：Ｄｉｇｉｔａｌ Ｒｏａｄ Ｍａｐ）データ上の移動経路を特定するマップマッチングが行われている。
【０００３】
ところで、本発明者らは、特許文献１に示すように、携帯端末を用いて携帯端末保持者の位置情報、時刻情報を効率的に収集できるシステムを発明している。特許文献１に示す携帯端末を用いる方法であれば、自動車を運転しているユーザ以外のプローブデータも収集することができる。
【特許文献１】特開２００７−１８３１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、携帯端末を用いる方法では、ユーザの向きに関する情報といった位置情報、時刻情報以外の情報が収集できない。また、自動車を運転していないユーザは、目的地に着くまでに様々な場所に立ち寄ることが考えられる。そのため、既存のマップマッチングでは、精度良くＤＲＭデータ上の移動経路を特定することができないといった問題があった。
【０００５】
本発明は、前述した問題点に鑑みてなされたもので、その目的は携帯端末によって収集したプローブデータから、精度良くＤＲＭデータ上の移動経路を特定するマップマッチング装置を提供することである。
【課題を解決するための手段】
【０００６】
前述した目的を達成するために第１の発明は、位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング装置であって、同一ユーザに係る前記プローブデータ群をデータ取得間隔に基づいて移動系列単位に分割する移動系列分割手段と、同一移動系列に係る前記プローブデータ群を局所的に集約した集約データ群を生成する集約データ生成手段と、前記集約データの移動方向を算出する移動方向算出手段と、前記集約データを関連付ける候補リンクを検索する候補リンク検索手段と、前記候補リンクの中から前記移動方向に最も近い方向を持つ最寄りリンクを決定する最寄りリンク決定手段と、前記集約データの位置座標から前記最寄りリンクへ引いた垂線の足である最寄り点の集合を用いて前記移動経路を特定する移動経路特定手段と、を具備することを特徴とするマップマッチング装置である。
【０００７】
ノードとは、交差点その他表現上の結節点である。リンクとは、ノード間の道路区間である。ユーザとは、プローブデータの提供者である。
【０００８】
更に、第１の発明は、前記移動経路に含まれる前記リンクごとに、リンク進入時刻、リンク退出時刻、リンク移動時間を含む旅行時間データを算出する旅行時間データ算出手段、を具備することが望ましい。
前記移動経路特定手段は、前記最寄り点の総数と前記最寄りリンクに対するヒット数とを用いても良い。また、前記移動経路特定手段は、前記最寄りリンクごとの前記最寄り点の総数を前記最寄りリンクの長さで除した値を用いても良い。そして、前記移動経路特定手段は、前記移動経路に含める前記リンクを１つずつ確定していくものであることが望ましい。
【０００９】
第２の発明は、位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング方法であって、同一ユーザに係る前記プローブデータ群をデータ取得間隔に基づいて移動系列単位に分割するステップと、同一移動系列に係る前記プローブデータ群を局所的に集約した集約データ群を生成するステップと、前記集約データの移動方向を算出するステップと、前記集約データを関連付ける候補リンクを検索するステップと、前記候補リンクの中から前記移動方向に最も近い方向を持つ最寄りリンクを決定するステップと、前記集約データの位置座標から前記最寄りリンクへ引いた垂線の足である最寄り点の集合を用いて前記移動経路を特定するステップと、を含むことを特徴とするマップマッチング方法である。
【００１０】
第３の発明は、コンピュータを第１の発明のマップマッチング装置として機能させるプログラムである。
【発明の効果】
【００１１】
本発明により、携帯端末によって収集したプローブデータから、精度良くＤＲＭデータ上の移動経路を特定するマップマッチング装置を提供することができる。
【発明を実施するための最良の形態】
【００１２】
以下、図面に基づいて、本発明の実施形態を詳細に説明する。
【００１３】
図１は、本実施の形態に係るマップマッチング装置１を実現するコンピュータのハードウェア構成図である。尚、図１のハードウェア構成は一例であり、用途、目的に応じて様々な構成を採ることが可能である。
マップマッチング装置１は、制御部３、記憶部５、メディア入出力部７、通信制御部９、入力部１１、表示部１３、周辺機器Ｉ／Ｆ部１５等が、バス１７を介して接続される。
【００１４】
制御部３は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）等で構成される。
【００１５】
ＣＰＵは、記憶部５、ＲＯＭ、記録媒体等に格納されるプログラムをＲＡＭ上のワークメモリ領域に呼び出して実行し、バス１７を介して接続された各装置を駆動制御し、マップマッチング装置１が行う後述する処理を実現する。
ＲＯＭは、不揮発性メモリであり、コンピュータのブートプログラムやＢＩＯＳ等のプログラム、データ等を恒久的に保持している。
ＲＡＭは、揮発性メモリであり、記憶部５、ＲＯＭ、記録媒体等からロードしたプログラム、データ等を一時的に保持するとともに、制御部３が各種処理を行う為に使用するワークエリアを備える。
【００１６】
記憶部５は、ＨＤＤ（ハードディスクドライブ）であり、制御部３が実行するプログラム、プログラム実行に必要なデータ、ＯＳ（オペレーティングシステム）等が格納される。プログラムに関しては、ＯＳ（オペレーティングシステム）に相当する制御プログラムや、後述の処理に相当するアプリケーションプログラムが格納されている。
これらの各プログラムコードは、制御部３により必要に応じて読み出されてＲＡＭに移され、ＣＰＵに読み出されて各種の手段として実行される。
【００１７】
メディア入出力部７（ドライブ装置）は、データの入出力を行い、例えば、フロッピー（登録商標）ディスクドライブ、ＣＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＤＶＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＭＯドライブ等のメディア入出力装置を有する。
【００１８】
通信制御部９は、通信制御装置、通信ポート等を有し、コンピュータとネットワーク１９間の通信を媒介する通信インタフェースであり、ネットワーク１９を介して、他のコンピュータ間との通信制御を行う。
【００１９】
入力部１１は、データの入力を行い、例えば、キーボード、マウス等のポインティングデバイス、テンキー等の入力装置を有する。
入力部１１を介して、コンピュータに対して、操作指示、動作指示、データ入力等を行うことができる。
【００２０】
表示部１３は、ＣＲＴモニタ、液晶パネル等のディスプレイ装置、ディスプレイ装置と連携してコンピュータのビデオ機能を実現するための論理回路等（ビデオアダプタ等）を有する。
【００２１】
周辺機器Ｉ／Ｆ（インタフェース）部１５は、コンピュータに周辺機器を接続させるためのポートであり、周辺機器Ｉ／Ｆ部１５を介してコンピュータは周辺機器とのデータの送受信を行う。周辺機器Ｉ／Ｆ部１５は、ＵＳＢやＩＥＥＥ１３９４やＲＳ−２３２Ｃ等で構成されており、通常複数の周辺機器Ｉ／Ｆを有する。周辺機器との接続形態は有線、無線を問わない。
【００２２】
バス１７は、各装置間の制御信号、データ信号等の授受を媒介する経路である。
【００２３】
次に、図２を参照しながら、マップマッチング装置１の機能を実現する構成について説明する。
図２は、マップマッチング装置１の機能の概要を示すブロック図である。
【００２４】
マップマッチング装置１は、プローブデータ入力手段２１、移動系列分割手段２２、集約データ生成手段２３、移動方向算出手段２４、候補リンク検索手段２５、最寄りリンク決定手段２６、移動経路特定手段２７、旅行時間データ算出手段２８、旅行時間データ出力手段２９、ＤＲＭデータＤＢ３０等を備える。
【００２５】
プローブデータ入力手段２１は、位置情報、時刻情報を含むプローブデータ３１を入力する。１回の処理で扱うデータ量は、例えば、１ユーザの１日分のプローブデータ３１である。ユーザとは、プローブデータ３１の提供者である。データの入力は、入力部１１を介しても良いし、メディア入出力部７を介しても良い。また、ネットワーク１９を介して、他のコンピュータからデータを受信しても良い。
【００２６】
移動系列分割手段２２は、同一ユーザに係るプローブデータ群をデータ取得間隔に基づいて移動系列単位に分割する。例えば、車両に乗車しているユーザであれば、途中で停車して休憩等を取った場合、別の移動系列として扱う。具体的には、データの取得間隔が所定の時間以上離れている場合、または、所定の時間を経過しても所定の半径内から出ていない場合等について、別の移動系列として扱う。
【００２７】
集約データ生成手段２３は、同一移動系列に係るプローブデータ群を局所的に集約した集約データ群を生成する。ＧＰＳ機能によって取得した位置情報は測位誤差が含まれており、同一の位置に所在している場合でも、プローブデータとしては微小な動きが生ずる。そこで、こうしたプローブデータを局所的に集約し、後続する処理の効率化と高速化を図る。
【００２８】
図３は、プローブデータを集約データに集約する１例を示す図である。
図３の左図に示すように、集約データ生成手段２３は、プローブデータの座標４１を集約範囲４３ごとに集約する。集約方法は、プローブデータの座標４１を時系列で順番にチェックしていき、所定の距離以内に含まれるものを集約する。
また、集約データ生成手段２３は、集約データの位置情報、時刻情報を決定する。集約データの位置情報、時刻情報は、例えば、同一の集約範囲４３に含まれるプローブデータの位置情報、時刻情報の平均値としても良いし、同一の集約範囲４３の中で時系列的に先頭となるプローブデータの位置情報、時刻情報としても良い。そして、図３の右図に示すように、集約範囲４３ごとに１つの集約データの座標４５が定まる。
【００２９】
移動方向算出手段２４は、集約データの移動方向を算出する。移動方向は、後述する最寄りリンク決定の処理において重要な判定要素となる。
【００３０】
図４は、集約データの移動方向を算出する１例を示す図である。
図４に示すように、移動方向算出手段２４は、ある集約データの座標４５から、時系列的に次の集約データの座標４５への向きを持つ移動方向ベクトル４７を算出する。
【００３１】
候補リンク検索手段２５は、ＤＲＭデータＤＢ３０を参照し、集約データを関連付ける候補リンクを検索する。ＤＲＭデータＤＢ３０は、ノードとリンクとで構成されたＤＲＭデータを保持する。ノードデータとしては、ノード番号、位置座標、ノード種別、接続リンク本数、接続ノード番号、交差点名称等が含まれる。また、リンクデータとしては、リンク番号（起終点ノードの番号）、道路種別、路線番号、リンク長、各種交通規制情報等が含まれる。尚、ＤＲＭデータは、一般に市販されているものである。
【００３２】
図５は、候補リンクを検索する１例を示す図である。
図５に示すように、ノード５１は、交差点その他表現上の結節点である。リンク５３は、ノード５１間の道路区間である。
候補リンク検索手段２５は、集約データの座標４５から所定の範囲内に存在するリンク５３を抽出する。図５の左図に示す例では、５３ａのリンクＡ、５３ｂのリンクＢ、５３ｃのリンクＣ、５３ｄのリンクＤが抽出される。次に、図５の右図に示すように、候補リンク検索手段２５は、集約データの座標４５から抽出したリンク５３に垂線５５を下ろす。垂線５５が下ろせないリンク５３は、候補リンクの対象から外す。図５の右図に示す例では、５３ａのリンクＡ、５３ｂのリンクＢに垂線５５を下ろすことができることから、５３ａのリンクＡ、５３ｂのリンクＢは候補リンクの対象となる。一方、５３ｃのリンクＣ、５３ｄのリンクＤに垂線５５を下ろすことができないことから、５３ｃのリンクＣ、５３ｄのリンクＤは候補リンクの対象外となる。尚、垂線の足５７のいずれかは、後述する最寄り点となる。
【００３３】
最寄りリンク決定手段２６は、候補リンクの中から集約データの移動方向に最も近い方向を持つ最寄りリンクを決定する。すなわち、移動方向算出手段２４で算出した集約データの移動方向を示す角度とＤＲＭデータより算出した候補リンクの方向を示す角度とを比較することで、最寄りリンクを決定する。最寄りリンクは、後述する移動経路の決定に重要な判定要素となる。
【００３４】
図６は、最寄りリンクを決定する１例を示す図である。
図６に示す例では、５３ａのリンクＡ、５３ｂのリンクＢが候補リンクである。そして、これらの候補リンクに対し、５９ａのリンク方向Ａ１、５９ｂのリンク方向Ａ２、５９ｃのリンク方向Ｂ１、５９ｄのリンク方向Ｂ２の４つのリンク方向が存在する。最寄りリンク決定手段２６は、これらのリンク方向を示す角度を算出し、移動方向ベクトル４７の方向を示す角度と最も近いリンク方向を持つものを最寄りリンクと決定する。図６に示す例では、５９ａのリンク方向Ａ１が最も近いリンク方向と判定されて、５３ａのリンクＡが最寄りリンクに決定される。
【００３５】
移動経路特定手段２７は、集約データの位置座標から最寄りリンクへ引いた垂線の足５７である最寄り点の集合を用いて移動経路を特定する。最寄り点は、候補リンク検索手段２５によって算出された垂線の足５７のうち、最寄りリンクに対する垂線の足５７である。
【００３６】
図７は、最寄り点６１の集合の１例を示す図である。
以下、例えば、ノードＡとノードＢとの間のリンクをリンクＡＢと呼ぶこととする。図７の例では、出発地点６３から５１ａのノードＡまでは、最寄り点６１が二つ存在する。また、５１ａのノードＡは分岐点となっており、リンクＡＢ上には最寄り点６１が三つ存在し、リンクＡＨ上には最寄り点６１が一つ存在する。従って、いずれのリンクを移動経路に含めるか決定する必要があるため、最寄りリンクを決定しただけでは移動経路を特定することができない。本発明の実施の形態では、移動経路を特定するロジックを二通り採用し、いずれのロジックで処理を行うかを処理開始前に選択することができる。
【００３７】
まず、移動経路を特定するロジックとして、最寄り点の総数と最寄りリンクに対するヒット数とを用いるロジックについて説明する。例として、図７の例において、出発地点６３から５１ａのノードＡまでの移動経路は確定した状態で、次のノードまでの移動経路を決定する手順を説明する。
【００３８】
図８は、図７の例における最寄り点の総数と最寄りリンクの総数を示す図である。
移動経路特定手段２７は、５１ａのノードＡを基準ノードとし、ノードＡから時系列順に所定の数の最寄り点６１を読み込み、読み込み経路ごとに最寄り点６１の総数を計算する。また、ノードＡから所定の数のリンクを読み込み、読み込み経路ごとに最寄りリンクに対するヒット数を算出する。ここで、最寄りリンクに対するヒット数とは、各最寄りリンク上に最寄り点６１が１つでも存在するときに最寄りリンクに対するヒットと定義し、読み込み経路におけるヒットの数をカウントしたものである。図８に示す例では、ノードＡから読み込むリンク数を６リンク先までとしている。
次に、移動経路特定手段２７は、ノードＡから、例えば、６リンク先までの最寄り点６１の総数が最も多い読み込み経路を移動経路の候補として決定する。更に、ノードＡから６リンク先までの最寄り点６１の総数が同一の読み込み経路が存在する場合、ノードＡから６リンク先までの読み込み経路の中のリンクに対するヒット数が多い方を、候補として決定する。
【００３９】
図８に示すように、ノードＡからの最寄り点６１の総数が最も多い読み込み経路は、Ａ−＞Ｂ−＞Ｃ−＞Ｄ−＞Ｅ−＞Ｆ−＞Ｇであり、この読み込み経路が移動経路の候補と決定される。そして、移動経路特定手段２７は、リンクＡＢを移動経路に含めることを確定する。ここで、移動経路を読み込んだ全てのリンクまで確定してしまうと、行き止まり等が存在する場合は、移動経路の到着地点（＝時系列的に最後の最寄り点６１）に到達できなくなる可能性があり、不正確な移動経路を特定してしまう場合がある。
リンクＡＢを移動経路に含めることを確定すると、次はノードＢを基準ノードとして同様の手順を行い、最終的に全ての移動経路を確定していく。このように、移動経路に含めるリンクを１つずつ確定していくことで、正確な移動経路を特定することができる。
【００４０】
次に、移動経路を特定するロジックとして、最寄りリンクごとの最寄り点の総数を最寄りリンクの長さで除した値を用いるロジックについて説明する。例として、図７の例において、出発地点６３から５１ａのノードＡまでの移動経路は確定した状態で、次のノードまでの移動経路を決定する手順を説明する。
【００４１】
図９は、図７の例における最寄りリンクの長さを示す図である。
図９に示す最寄りリンクの長さは、ＤＲＭデータに含まれるデータである。
【００４２】
図１０は、図７の例における最寄り点の総数をリンクの長さで除した値の合計値を示す図である。
図１０に示す値は、図７に示す最寄りリングごとの最寄り点の総数と図９に示す最寄りリンクの長さとを用いて算出した値である。
移動経路特定手段２７は、５１ａのノードＡを基準ノードとし、ノードＡから時系列順に所定の数の最寄り点６１を読み込み、最寄りリンクごとに最寄り点６１の総数を計算する。また、ノードＡから所定の数のリンクを読み込み、読み込み経路ごとに最寄り点６１の総数を最寄りリンクの長さで除した値の合計値を算出する。図１０に示す例では、ノードＡから読み込むリンク数を６リンク先までとしている。
次に、移動経路特定手段２７は、最寄りリンクごとの最寄り点６１の総数を最寄りリンクの長さで除した値の合計値が最も大きい読み込み経路を移動経路の候補として決定する。
【００４３】
図１０に示すように、最寄りリンクごとの最寄り点６１の総数を最寄りリンクの長さで除した値の合計値が最も大きい読み込み経路は、Ａ−＞Ｂ−＞Ｃ−＞Ｄ−＞Ｅ−＞Ｆ−＞Ｇであり、この読み込み経路が移動経路の候補と決定される。そして、移動経路特定手段２７は、リンクＡＢを移動経路に含めることを確定する。
リンクＡＢを移動経路に含めることを確定すると、次はノードＢを基準ノードとして同様の手順を行い、最終的に全ての移動経路を確定していく。このように、移動経路に含めるリンクを１つずつ確定していくことで、正確な移動経路を特定することができる。
【００４４】
最後に、移動経路特定手段２７は、確定した移動経路の検証を行う。これは、確定した移動経路に含まれる最寄りリンクの中に最寄り点６１が存在しないものもあるため、前後の最寄り点６１が存在する最寄りリンクを用いて検証を行い、必要があれば移動経路の補正をする。
【００４５】
旅行時間データ算出手段２８は、移動経路に含まれるリンクごとに、リンク進入時刻、リンク退出時刻、リンク移動時間を含む旅行時間データを算出する。リンク進入時刻、リンク退出時刻は、最寄り点６１の時刻情報を用いて、必要があれば補間計算を行うことにより算出する。リンク移動時間は、リンク進入時刻とリンク退出時刻とから算出する。更に、ＤＲＭデータに含まれるリンク長を用いて、リンク内平均移動速度も算出することができる。
【００４６】
旅行時間データ出力手段２９は、旅行時間データ３２を出力する。データの出力は、利用し易いフォーマットで記憶部５が保持するデータベースに書き込むようにしても良い。また、ネットワーク１９を介して、他のコンピュータに送信しても良い。
【００４７】
次に、図１１を参照しながら、マップマッチング装置１の動作の詳細について説明する。
図１１は、本実施の形態におけるマップマッチング装置１において実行されるマップマッチング処理の流れを説明するフローチャートである。
【００４８】
図１１に示すように、制御部３は、プローブデータ入力手段２１によってプローブデータが入力されると（Ｓ１０１）、移動系列分割手段２２によって移動系列を分割する（Ｓ１０２）。
【００４９】
次に、制御部３は、処理を行う移動系列を選択する（Ｓ１０３）。移動系列は、例えば、移動系列に含まれるプローブデータの時系列順に選択する。
次に、制御部３は、集約データ生成手段２３によって集約データを生成する（Ｓ１０４）。
【００５０】
次に、制御部３は、処理を行う集約データを選択する（Ｓ１０５）。集約データは、例えば、集約データが保持する時刻情報の時系列順に選択する。
次に、制御部３は、移動方向算出手段２４によって集約データの移動方向を算出する（Ｓ１０６）。そして、候補リンク検索手段２５によって候補リンクの検索を行い（Ｓ１０７）、最寄りリンク決定手段２６によって候補リンクの中から最寄りリンクを決定する（Ｓ１０８）。
次に、制御部３は、全ての集約データについて処理が終了したか確認する（Ｓ１０９）。
処理が終了していない場合、Ｓ１０５から繰り返す。
処理が終了している場合、Ｓ１１０に進む。
【００５１】
次に、制御部３は、移動経路特定手段２７によってＳ１１０からＳ１１３の処理を行う。
制御部３は、処理を行う基準ノードを選択する（Ｓ１１０）。基準ノードは、１回目の処理であれば出発地点であり、２回目以降の処理であれば前回のＳ１１２で確定されたリンクに係るノード（例えば、リンクＡＢが前回のＳ１１２で確定されたリンクであれば、ノードＢ）となる。
次に、制御部３は、移動経路の候補を決定し（Ｓ１１１）、移動経路に含めるリンクを確定する（Ｓ１１２）。
次に、制御部３は、移動経路が全て確定したか確認する（Ｓ１１３）。
全て確定していない場合、Ｓ１１０から繰り返す。
全て確定している場合、Ｓ１１４に進む。
【００５２】
次に、制御部３は、処理を行うリンクを選択する（Ｓ１１４）。リンクは、例えば、移動経路の出発地点を含むリンクから時系列順に選択する。
次に、制御部３は、旅行時間データ算出手段２８によって旅行時間データを算出する（Ｓ１１５）。
次に、制御部３は、移動経路に含まれる全てのリンクについて処理が終了したか確認する（Ｓ１１６）。
処理が終了していない場合、Ｓ１１４から繰り返す。
処理が終了している場合、Ｓ１１７に進む。
【００５３】
次に、制御部３は、全ての移動系列について処理が終了したか確認する（Ｓ１１７）。
処理が終了していない場合、Ｓ１０３から繰り返す。
処理が終了している場合、Ｓ１１８に進む。
【００５４】
最後に、制御部３は、旅行時間データ出力手段２９によって旅行時間データを出力し（Ｓ１１８）、処理を終了する。
【００５５】
以上説明したように、本発明の実施の形態によれば、制御部３は、移動系列単位に分割されたプローブデータを局所的に集約し、集約データを作成する。次に、制御部３は、集約データの移動方向を算出するとともに、集約データを関連付ける候補リンクを検索する。次に、制御部３は、候補リンクの中から集約データの移動方向に最も近い方向を持つ最寄りリンクを決定し、集約データの位置座標から最寄りリンクへ引いた垂線の足を最寄り点とする。そして、制御部３は、最寄り点の集合を用いて、移動経路に含めるリンクを１つずつ確定していき、移動経路を特定する。ここで、移動経路を特定するロジックは、最寄り点の総数と最寄りリンクに対するヒット数とを用いるものでも良いし、最寄りリンクごとの最寄り点の総数を最寄りリンクの長さで除した値を用いるものでも良い。
【００５６】
本発明の実施の形態によって、携帯端末によって収集したプローブデータから、精度良くデジタル道路地図データ上の移動経路を特定するマップマッチング装置を提供することができる。特に、プローブデータを局所的に集約することで、処理の効率化と高速化を図ることができる。また、移動経路に含めるリンクを１つずつ確定していくことで、正確な移動経路を特定することができる。
【００５７】
以上、添付図面を参照しながら、本発明に係るマップマッチング装置等の好適な実施形態について説明したが、本発明はかかる例に限定されない。当業者であれば、本願で開示した技術的思想の範疇内において、各種の変更例又は修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【図面の簡単な説明】
【００５８】
【図１】マップマッチング装置１を実現するコンピュータのハードウェア構成図
【図２】マップマッチング装置１の機能の概要を示すブロック図
【図３】プローブデータを集約データに集約する１例を示す図
【図４】集約データの移動方向を算出する１例を示す図
【図５】候補リンクを検索する１例を示す図
【図６】最寄りリンクを決定する１例を示す図
【図７】最寄り点６１の集合の１例を示す図
【図８】図７の例における最寄り点の総数と最寄りリンクの総数を示す図
【図９】図７の例における最寄りリンクの長さを示す図
【図１０】図７の例における最寄り点の総数をリンクの長さで除した値の合計値を示す図
【図１１】マップマッチング処理の流れを説明するフローチャート
【符号の説明】
【００５９】
１………マップマッチング装置
３………制御部
５………記憶部
７………メディア入出力部
９………通信制御部
１１………入力部
１３………表示部
１５………周辺機器Ｉ／Ｆ部
１７………バス
１９………ネットワーク
【技術分野】
【０００１】
本発明は、位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング装置、マップマッチング方法及びそのプログラムに関するものである。
【背景技術】
【０００２】
現在、車両に搭載した装置を用いて、車両の走行履歴を調査・分析することが行われている。車両搭載装置が収集するデータは、一般に、プローブデータと呼ばれており、位置情報、時刻情報の他に、車両の速度、車両の向き、ハンドルの旋回状況、ブレーキングの状況等様々な情報が含まれていることが多い。そして、車両の走行履歴を調査・分析するため、こうしたプローブデータから、ノードとリンクとで構成されたデジタル道路地図（ＤＲＭ：Ｄｉｇｉｔａｌ Ｒｏａｄ Ｍａｐ）データ上の移動経路を特定するマップマッチングが行われている。
【０００３】
ところで、本発明者らは、特許文献１に示すように、携帯端末を用いて携帯端末保持者の位置情報、時刻情報を効率的に収集できるシステムを発明している。特許文献１に示す携帯端末を用いる方法であれば、自動車を運転しているユーザ以外のプローブデータも収集することができる。
【特許文献１】特開２００７−１８３１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、携帯端末を用いる方法では、ユーザの向きに関する情報といった位置情報、時刻情報以外の情報が収集できない。また、自動車を運転していないユーザは、目的地に着くまでに様々な場所に立ち寄ることが考えられる。そのため、既存のマップマッチングでは、精度良くＤＲＭデータ上の移動経路を特定することができないといった問題があった。
【０００５】
本発明は、前述した問題点に鑑みてなされたもので、その目的は携帯端末によって収集したプローブデータから、精度良くＤＲＭデータ上の移動経路を特定するマップマッチング装置を提供することである。
【課題を解決するための手段】
【０００６】
前述した目的を達成するために第１の発明は、位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング装置であって、同一ユーザに係る前記プローブデータ群をデータ取得間隔に基づいて移動系列単位に分割する移動系列分割手段と、同一移動系列に係る前記プローブデータ群を局所的に集約した集約データ群を生成する集約データ生成手段と、前記集約データの移動方向を算出する移動方向算出手段と、前記集約データを関連付ける候補リンクを検索する候補リンク検索手段と、前記候補リンクの中から前記移動方向に最も近い方向を持つ最寄りリンクを決定する最寄りリンク決定手段と、前記集約データの位置座標から前記最寄りリンクへ引いた垂線の足である最寄り点の集合を用いて前記移動経路を特定する移動経路特定手段と、を具備することを特徴とするマップマッチング装置である。
【０００７】
ノードとは、交差点その他表現上の結節点である。リンクとは、ノード間の道路区間である。ユーザとは、プローブデータの提供者である。
【０００８】
更に、第１の発明は、前記移動経路に含まれる前記リンクごとに、リンク進入時刻、リンク退出時刻、リンク移動時間を含む旅行時間データを算出する旅行時間データ算出手段、を具備することが望ましい。
前記移動経路特定手段は、前記最寄り点の総数と前記最寄りリンクに対するヒット数とを用いても良い。また、前記移動経路特定手段は、前記最寄りリンクごとの前記最寄り点の総数を前記最寄りリンクの長さで除した値を用いても良い。そして、前記移動経路特定手段は、前記移動経路に含める前記リンクを１つずつ確定していくものであることが望ましい。
【０００９】
第２の発明は、位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング方法であって、同一ユーザに係る前記プローブデータ群をデータ取得間隔に基づいて移動系列単位に分割するステップと、同一移動系列に係る前記プローブデータ群を局所的に集約した集約データ群を生成するステップと、前記集約データの移動方向を算出するステップと、前記集約データを関連付ける候補リンクを検索するステップと、前記候補リンクの中から前記移動方向に最も近い方向を持つ最寄りリンクを決定するステップと、前記集約データの位置座標から前記最寄りリンクへ引いた垂線の足である最寄り点の集合を用いて前記移動経路を特定するステップと、を含むことを特徴とするマップマッチング方法である。
【００１０】
第３の発明は、コンピュータを第１の発明のマップマッチング装置として機能させるプログラムである。
【発明の効果】
【００１１】
本発明により、携帯端末によって収集したプローブデータから、精度良くＤＲＭデータ上の移動経路を特定するマップマッチング装置を提供することができる。
【発明を実施するための最良の形態】
【００１２】
以下、図面に基づいて、本発明の実施形態を詳細に説明する。
【００１３】
図１は、本実施の形態に係るマップマッチング装置１を実現するコンピュータのハードウェア構成図である。尚、図１のハードウェア構成は一例であり、用途、目的に応じて様々な構成を採ることが可能である。
マップマッチング装置１は、制御部３、記憶部５、メディア入出力部７、通信制御部９、入力部１１、表示部１３、周辺機器Ｉ／Ｆ部１５等が、バス１７を介して接続される。
【００１４】
制御部３は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）等で構成される。
【００１５】
ＣＰＵは、記憶部５、ＲＯＭ、記録媒体等に格納されるプログラムをＲＡＭ上のワークメモリ領域に呼び出して実行し、バス１７を介して接続された各装置を駆動制御し、マップマッチング装置１が行う後述する処理を実現する。
ＲＯＭは、不揮発性メモリであり、コンピュータのブートプログラムやＢＩＯＳ等のプログラム、データ等を恒久的に保持している。
ＲＡＭは、揮発性メモリであり、記憶部５、ＲＯＭ、記録媒体等からロードしたプログラム、データ等を一時的に保持するとともに、制御部３が各種処理を行う為に使用するワークエリアを備える。
【００１６】
記憶部５は、ＨＤＤ（ハードディスクドライブ）であり、制御部３が実行するプログラム、プログラム実行に必要なデータ、ＯＳ（オペレーティングシステム）等が格納される。プログラムに関しては、ＯＳ（オペレーティングシステム）に相当する制御プログラムや、後述の処理に相当するアプリケーションプログラムが格納されている。
これらの各プログラムコードは、制御部３により必要に応じて読み出されてＲＡＭに移され、ＣＰＵに読み出されて各種の手段として実行される。
【００１７】
メディア入出力部７（ドライブ装置）は、データの入出力を行い、例えば、フロッピー（登録商標）ディスクドライブ、ＣＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＤＶＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＭＯドライブ等のメディア入出力装置を有する。
【００１８】
通信制御部９は、通信制御装置、通信ポート等を有し、コンピュータとネットワーク１９間の通信を媒介する通信インタフェースであり、ネットワーク１９を介して、他のコンピュータ間との通信制御を行う。
【００１９】
入力部１１は、データの入力を行い、例えば、キーボード、マウス等のポインティングデバイス、テンキー等の入力装置を有する。
入力部１１を介して、コンピュータに対して、操作指示、動作指示、データ入力等を行うことができる。
【００２０】
表示部１３は、ＣＲＴモニタ、液晶パネル等のディスプレイ装置、ディスプレイ装置と連携してコンピュータのビデオ機能を実現するための論理回路等（ビデオアダプタ等）を有する。
【００２１】
周辺機器Ｉ／Ｆ（インタフェース）部１５は、コンピュータに周辺機器を接続させるためのポートであり、周辺機器Ｉ／Ｆ部１５を介してコンピュータは周辺機器とのデータの送受信を行う。周辺機器Ｉ／Ｆ部１５は、ＵＳＢやＩＥＥＥ１３９４やＲＳ−２３２Ｃ等で構成されており、通常複数の周辺機器Ｉ／Ｆを有する。周辺機器との接続形態は有線、無線を問わない。
【００２２】
バス１７は、各装置間の制御信号、データ信号等の授受を媒介する経路である。
【００２３】
次に、図２を参照しながら、マップマッチング装置１の機能を実現する構成について説明する。
図２は、マップマッチング装置１の機能の概要を示すブロック図である。
【００２４】
マップマッチング装置１は、プローブデータ入力手段２１、移動系列分割手段２２、集約データ生成手段２３、移動方向算出手段２４、候補リンク検索手段２５、最寄りリンク決定手段２６、移動経路特定手段２７、旅行時間データ算出手段２８、旅行時間データ出力手段２９、ＤＲＭデータＤＢ３０等を備える。
【００２５】
プローブデータ入力手段２１は、位置情報、時刻情報を含むプローブデータ３１を入力する。１回の処理で扱うデータ量は、例えば、１ユーザの１日分のプローブデータ３１である。ユーザとは、プローブデータ３１の提供者である。データの入力は、入力部１１を介しても良いし、メディア入出力部７を介しても良い。また、ネットワーク１９を介して、他のコンピュータからデータを受信しても良い。
【００２６】
移動系列分割手段２２は、同一ユーザに係るプローブデータ群をデータ取得間隔に基づいて移動系列単位に分割する。例えば、車両に乗車しているユーザであれば、途中で停車して休憩等を取った場合、別の移動系列として扱う。具体的には、データの取得間隔が所定の時間以上離れている場合、または、所定の時間を経過しても所定の半径内から出ていない場合等について、別の移動系列として扱う。
【００２７】
集約データ生成手段２３は、同一移動系列に係るプローブデータ群を局所的に集約した集約データ群を生成する。ＧＰＳ機能によって取得した位置情報は測位誤差が含まれており、同一の位置に所在している場合でも、プローブデータとしては微小な動きが生ずる。そこで、こうしたプローブデータを局所的に集約し、後続する処理の効率化と高速化を図る。
【００２８】
図３は、プローブデータを集約データに集約する１例を示す図である。
図３の左図に示すように、集約データ生成手段２３は、プローブデータの座標４１を集約範囲４３ごとに集約する。集約方法は、プローブデータの座標４１を時系列で順番にチェックしていき、所定の距離以内に含まれるものを集約する。
また、集約データ生成手段２３は、集約データの位置情報、時刻情報を決定する。集約データの位置情報、時刻情報は、例えば、同一の集約範囲４３に含まれるプローブデータの位置情報、時刻情報の平均値としても良いし、同一の集約範囲４３の中で時系列的に先頭となるプローブデータの位置情報、時刻情報としても良い。そして、図３の右図に示すように、集約範囲４３ごとに１つの集約データの座標４５が定まる。
【００２９】
移動方向算出手段２４は、集約データの移動方向を算出する。移動方向は、後述する最寄りリンク決定の処理において重要な判定要素となる。
【００３０】
図４は、集約データの移動方向を算出する１例を示す図である。
図４に示すように、移動方向算出手段２４は、ある集約データの座標４５から、時系列的に次の集約データの座標４５への向きを持つ移動方向ベクトル４７を算出する。
【００３１】
候補リンク検索手段２５は、ＤＲＭデータＤＢ３０を参照し、集約データを関連付ける候補リンクを検索する。ＤＲＭデータＤＢ３０は、ノードとリンクとで構成されたＤＲＭデータを保持する。ノードデータとしては、ノード番号、位置座標、ノード種別、接続リンク本数、接続ノード番号、交差点名称等が含まれる。また、リンクデータとしては、リンク番号（起終点ノードの番号）、道路種別、路線番号、リンク長、各種交通規制情報等が含まれる。尚、ＤＲＭデータは、一般に市販されているものである。
【００３２】
図５は、候補リンクを検索する１例を示す図である。
図５に示すように、ノード５１は、交差点その他表現上の結節点である。リンク５３は、ノード５１間の道路区間である。
候補リンク検索手段２５は、集約データの座標４５から所定の範囲内に存在するリンク５３を抽出する。図５の左図に示す例では、５３ａのリンクＡ、５３ｂのリンクＢ、５３ｃのリンクＣ、５３ｄのリンクＤが抽出される。次に、図５の右図に示すように、候補リンク検索手段２５は、集約データの座標４５から抽出したリンク５３に垂線５５を下ろす。垂線５５が下ろせないリンク５３は、候補リンクの対象から外す。図５の右図に示す例では、５３ａのリンクＡ、５３ｂのリンクＢに垂線５５を下ろすことができることから、５３ａのリンクＡ、５３ｂのリンクＢは候補リンクの対象となる。一方、５３ｃのリンクＣ、５３ｄのリンクＤに垂線５５を下ろすことができないことから、５３ｃのリンクＣ、５３ｄのリンクＤは候補リンクの対象外となる。尚、垂線の足５７のいずれかは、後述する最寄り点となる。
【００３３】
最寄りリンク決定手段２６は、候補リンクの中から集約データの移動方向に最も近い方向を持つ最寄りリンクを決定する。すなわち、移動方向算出手段２４で算出した集約データの移動方向を示す角度とＤＲＭデータより算出した候補リンクの方向を示す角度とを比較することで、最寄りリンクを決定する。最寄りリンクは、後述する移動経路の決定に重要な判定要素となる。
【００３４】
図６は、最寄りリンクを決定する１例を示す図である。
図６に示す例では、５３ａのリンクＡ、５３ｂのリンクＢが候補リンクである。そして、これらの候補リンクに対し、５９ａのリンク方向Ａ１、５９ｂのリンク方向Ａ２、５９ｃのリンク方向Ｂ１、５９ｄのリンク方向Ｂ２の４つのリンク方向が存在する。最寄りリンク決定手段２６は、これらのリンク方向を示す角度を算出し、移動方向ベクトル４７の方向を示す角度と最も近いリンク方向を持つものを最寄りリンクと決定する。図６に示す例では、５９ａのリンク方向Ａ１が最も近いリンク方向と判定されて、５３ａのリンクＡが最寄りリンクに決定される。
【００３５】
移動経路特定手段２７は、集約データの位置座標から最寄りリンクへ引いた垂線の足５７である最寄り点の集合を用いて移動経路を特定する。最寄り点は、候補リンク検索手段２５によって算出された垂線の足５７のうち、最寄りリンクに対する垂線の足５７である。
【００３６】
図７は、最寄り点６１の集合の１例を示す図である。
以下、例えば、ノードＡとノードＢとの間のリンクをリンクＡＢと呼ぶこととする。図７の例では、出発地点６３から５１ａのノードＡまでは、最寄り点６１が二つ存在する。また、５１ａのノードＡは分岐点となっており、リンクＡＢ上には最寄り点６１が三つ存在し、リンクＡＨ上には最寄り点６１が一つ存在する。従って、いずれのリンクを移動経路に含めるか決定する必要があるため、最寄りリンクを決定しただけでは移動経路を特定することができない。本発明の実施の形態では、移動経路を特定するロジックを二通り採用し、いずれのロジックで処理を行うかを処理開始前に選択することができる。
【００３７】
まず、移動経路を特定するロジックとして、最寄り点の総数と最寄りリンクに対するヒット数とを用いるロジックについて説明する。例として、図７の例において、出発地点６３から５１ａのノードＡまでの移動経路は確定した状態で、次のノードまでの移動経路を決定する手順を説明する。
【００３８】
図８は、図７の例における最寄り点の総数と最寄りリンクの総数を示す図である。
移動経路特定手段２７は、５１ａのノードＡを基準ノードとし、ノードＡから時系列順に所定の数の最寄り点６１を読み込み、読み込み経路ごとに最寄り点６１の総数を計算する。また、ノードＡから所定の数のリンクを読み込み、読み込み経路ごとに最寄りリンクに対するヒット数を算出する。ここで、最寄りリンクに対するヒット数とは、各最寄りリンク上に最寄り点６１が１つでも存在するときに最寄りリンクに対するヒットと定義し、読み込み経路におけるヒットの数をカウントしたものである。図８に示す例では、ノードＡから読み込むリンク数を６リンク先までとしている。
次に、移動経路特定手段２７は、ノードＡから、例えば、６リンク先までの最寄り点６１の総数が最も多い読み込み経路を移動経路の候補として決定する。更に、ノードＡから６リンク先までの最寄り点６１の総数が同一の読み込み経路が存在する場合、ノードＡから６リンク先までの読み込み経路の中のリンクに対するヒット数が多い方を、候補として決定する。
【００３９】
図８に示すように、ノードＡからの最寄り点６１の総数が最も多い読み込み経路は、Ａ−＞Ｂ−＞Ｃ−＞Ｄ−＞Ｅ−＞Ｆ−＞Ｇであり、この読み込み経路が移動経路の候補と決定される。そして、移動経路特定手段２７は、リンクＡＢを移動経路に含めることを確定する。ここで、移動経路を読み込んだ全てのリンクまで確定してしまうと、行き止まり等が存在する場合は、移動経路の到着地点（＝時系列的に最後の最寄り点６１）に到達できなくなる可能性があり、不正確な移動経路を特定してしまう場合がある。
リンクＡＢを移動経路に含めることを確定すると、次はノードＢを基準ノードとして同様の手順を行い、最終的に全ての移動経路を確定していく。このように、移動経路に含めるリンクを１つずつ確定していくことで、正確な移動経路を特定することができる。
【００４０】
次に、移動経路を特定するロジックとして、最寄りリンクごとの最寄り点の総数を最寄りリンクの長さで除した値を用いるロジックについて説明する。例として、図７の例において、出発地点６３から５１ａのノードＡまでの移動経路は確定した状態で、次のノードまでの移動経路を決定する手順を説明する。
【００４１】
図９は、図７の例における最寄りリンクの長さを示す図である。
図９に示す最寄りリンクの長さは、ＤＲＭデータに含まれるデータである。
【００４２】
図１０は、図７の例における最寄り点の総数をリンクの長さで除した値の合計値を示す図である。
図１０に示す値は、図７に示す最寄りリングごとの最寄り点の総数と図９に示す最寄りリンクの長さとを用いて算出した値である。
移動経路特定手段２７は、５１ａのノードＡを基準ノードとし、ノードＡから時系列順に所定の数の最寄り点６１を読み込み、最寄りリンクごとに最寄り点６１の総数を計算する。また、ノードＡから所定の数のリンクを読み込み、読み込み経路ごとに最寄り点６１の総数を最寄りリンクの長さで除した値の合計値を算出する。図１０に示す例では、ノードＡから読み込むリンク数を６リンク先までとしている。
次に、移動経路特定手段２７は、最寄りリンクごとの最寄り点６１の総数を最寄りリンクの長さで除した値の合計値が最も大きい読み込み経路を移動経路の候補として決定する。
【００４３】
図１０に示すように、最寄りリンクごとの最寄り点６１の総数を最寄りリンクの長さで除した値の合計値が最も大きい読み込み経路は、Ａ−＞Ｂ−＞Ｃ−＞Ｄ−＞Ｅ−＞Ｆ−＞Ｇであり、この読み込み経路が移動経路の候補と決定される。そして、移動経路特定手段２７は、リンクＡＢを移動経路に含めることを確定する。
リンクＡＢを移動経路に含めることを確定すると、次はノードＢを基準ノードとして同様の手順を行い、最終的に全ての移動経路を確定していく。このように、移動経路に含めるリンクを１つずつ確定していくことで、正確な移動経路を特定することができる。
【００４４】
最後に、移動経路特定手段２７は、確定した移動経路の検証を行う。これは、確定した移動経路に含まれる最寄りリンクの中に最寄り点６１が存在しないものもあるため、前後の最寄り点６１が存在する最寄りリンクを用いて検証を行い、必要があれば移動経路の補正をする。
【００４５】
旅行時間データ算出手段２８は、移動経路に含まれるリンクごとに、リンク進入時刻、リンク退出時刻、リンク移動時間を含む旅行時間データを算出する。リンク進入時刻、リンク退出時刻は、最寄り点６１の時刻情報を用いて、必要があれば補間計算を行うことにより算出する。リンク移動時間は、リンク進入時刻とリンク退出時刻とから算出する。更に、ＤＲＭデータに含まれるリンク長を用いて、リンク内平均移動速度も算出することができる。
【００４６】
旅行時間データ出力手段２９は、旅行時間データ３２を出力する。データの出力は、利用し易いフォーマットで記憶部５が保持するデータベースに書き込むようにしても良い。また、ネットワーク１９を介して、他のコンピュータに送信しても良い。
【００４７】
次に、図１１を参照しながら、マップマッチング装置１の動作の詳細について説明する。
図１１は、本実施の形態におけるマップマッチング装置１において実行されるマップマッチング処理の流れを説明するフローチャートである。
【００４８】
図１１に示すように、制御部３は、プローブデータ入力手段２１によってプローブデータが入力されると（Ｓ１０１）、移動系列分割手段２２によって移動系列を分割する（Ｓ１０２）。
【００４９】
次に、制御部３は、処理を行う移動系列を選択する（Ｓ１０３）。移動系列は、例えば、移動系列に含まれるプローブデータの時系列順に選択する。
次に、制御部３は、集約データ生成手段２３によって集約データを生成する（Ｓ１０４）。
【００５０】
次に、制御部３は、処理を行う集約データを選択する（Ｓ１０５）。集約データは、例えば、集約データが保持する時刻情報の時系列順に選択する。
次に、制御部３は、移動方向算出手段２４によって集約データの移動方向を算出する（Ｓ１０６）。そして、候補リンク検索手段２５によって候補リンクの検索を行い（Ｓ１０７）、最寄りリンク決定手段２６によって候補リンクの中から最寄りリンクを決定する（Ｓ１０８）。
次に、制御部３は、全ての集約データについて処理が終了したか確認する（Ｓ１０９）。
処理が終了していない場合、Ｓ１０５から繰り返す。
処理が終了している場合、Ｓ１１０に進む。
【００５１】
次に、制御部３は、移動経路特定手段２７によってＳ１１０からＳ１１３の処理を行う。
制御部３は、処理を行う基準ノードを選択する（Ｓ１１０）。基準ノードは、１回目の処理であれば出発地点であり、２回目以降の処理であれば前回のＳ１１２で確定されたリンクに係るノード（例えば、リンクＡＢが前回のＳ１１２で確定されたリンクであれば、ノードＢ）となる。
次に、制御部３は、移動経路の候補を決定し（Ｓ１１１）、移動経路に含めるリンクを確定する（Ｓ１１２）。
次に、制御部３は、移動経路が全て確定したか確認する（Ｓ１１３）。
全て確定していない場合、Ｓ１１０から繰り返す。
全て確定している場合、Ｓ１１４に進む。
【００５２】
次に、制御部３は、処理を行うリンクを選択する（Ｓ１１４）。リンクは、例えば、移動経路の出発地点を含むリンクから時系列順に選択する。
次に、制御部３は、旅行時間データ算出手段２８によって旅行時間データを算出する（Ｓ１１５）。
次に、制御部３は、移動経路に含まれる全てのリンクについて処理が終了したか確認する（Ｓ１１６）。
処理が終了していない場合、Ｓ１１４から繰り返す。
処理が終了している場合、Ｓ１１７に進む。
【００５３】
次に、制御部３は、全ての移動系列について処理が終了したか確認する（Ｓ１１７）。
処理が終了していない場合、Ｓ１０３から繰り返す。
処理が終了している場合、Ｓ１１８に進む。
【００５４】
最後に、制御部３は、旅行時間データ出力手段２９によって旅行時間データを出力し（Ｓ１１８）、処理を終了する。
【００５５】
以上説明したように、本発明の実施の形態によれば、制御部３は、移動系列単位に分割されたプローブデータを局所的に集約し、集約データを作成する。次に、制御部３は、集約データの移動方向を算出するとともに、集約データを関連付ける候補リンクを検索する。次に、制御部３は、候補リンクの中から集約データの移動方向に最も近い方向を持つ最寄りリンクを決定し、集約データの位置座標から最寄りリンクへ引いた垂線の足を最寄り点とする。そして、制御部３は、最寄り点の集合を用いて、移動経路に含めるリンクを１つずつ確定していき、移動経路を特定する。ここで、移動経路を特定するロジックは、最寄り点の総数と最寄りリンクに対するヒット数とを用いるものでも良いし、最寄りリンクごとの最寄り点の総数を最寄りリンクの長さで除した値を用いるものでも良い。
【００５６】
本発明の実施の形態によって、携帯端末によって収集したプローブデータから、精度良くデジタル道路地図データ上の移動経路を特定するマップマッチング装置を提供することができる。特に、プローブデータを局所的に集約することで、処理の効率化と高速化を図ることができる。また、移動経路に含めるリンクを１つずつ確定していくことで、正確な移動経路を特定することができる。
【００５７】
以上、添付図面を参照しながら、本発明に係るマップマッチング装置等の好適な実施形態について説明したが、本発明はかかる例に限定されない。当業者であれば、本願で開示した技術的思想の範疇内において、各種の変更例又は修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【図面の簡単な説明】
【００５８】
【図１】マップマッチング装置１を実現するコンピュータのハードウェア構成図
【図２】マップマッチング装置１の機能の概要を示すブロック図
【図３】プローブデータを集約データに集約する１例を示す図
【図４】集約データの移動方向を算出する１例を示す図
【図５】候補リンクを検索する１例を示す図
【図６】最寄りリンクを決定する１例を示す図
【図７】最寄り点６１の集合の１例を示す図
【図８】図７の例における最寄り点の総数と最寄りリンクの総数を示す図
【図９】図７の例における最寄りリンクの長さを示す図
【図１０】図７の例における最寄り点の総数をリンクの長さで除した値の合計値を示す図
【図１１】マップマッチング処理の流れを説明するフローチャート
【符号の説明】
【００５９】
１………マップマッチング装置
３………制御部
５………記憶部
７………メディア入出力部
９………通信制御部
１１………入力部
１３………表示部
１５………周辺機器Ｉ／Ｆ部
１７………バス
１９………ネットワーク
【特許請求の範囲】
【請求項１】
位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング装置であって、
同一ユーザに係る前記プローブデータ群をデータ取得間隔に基づいて移動系列単位に分割する移動系列分割手段と、
同一移動系列に係る前記プローブデータ群を局所的に集約した集約データ群を生成する集約データ生成手段と、
前記集約データの移動方向を算出する移動方向算出手段と、
前記集約データを関連付ける候補リンクを検索する候補リンク検索手段と、
前記候補リンクの中から前記移動方向に最も近い方向を持つ最寄りリンクを決定する最寄りリンク決定手段と、
前記集約データの位置座標から前記最寄りリンクへ引いた垂線の足である最寄り点の集合を用いて前記移動経路を特定する移動経路特定手段と、
を具備することを特徴とするマップマッチング装置。
【請求項２】
前記移動経路に含まれる前記リンクごとに、リンク進入時刻、リンク退出時刻、リンク移動時間を含む旅行時間データを算出する旅行時間データ算出手段、
を更に具備することを特徴とする請求項１に記載のマップマッチング装置。
【請求項３】
前記移動経路特定手段は、前記最寄り点の総数と前記最寄りリンクに対するヒット数とを用いるものであることを特徴とする請求項１または請求項２に記載のマップマッチング装置。
【請求項４】
前記移動経路特定手段は、前記最寄りリンクごとの前記最寄り点の総数を前記最寄りリンクの長さで除した値を用いるものであることを特徴とする請求項１または請求項２に記載のマップマッチング装置。
【請求項５】
前記移動経路特定手段は、前記移動経路に含める前記リンクを１つずつ確定していくものであることを特徴とする請求項３または請求項４に記載のマップマッチング装置。
【請求項６】
位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング方法であって、
同一ユーザに係る前記プローブデータ群をデータ取得間隔に基づいて移動系列単位に分割するステップと、
同一移動系列に係る前記プローブデータ群を局所的に集約した集約データ群を生成するステップと、
前記集約データの移動方向を算出するステップと、
前記集約データを関連付ける候補リンクを検索するステップと、
前記候補リンクの中から前記移動方向に最も近い方向を持つ最寄りリンクを決定するステップと、
前記集約データの位置座標から前記最寄りリンクへ引いた垂線の足である最寄り点の集合を用いて前記移動経路を特定するステップと、
を含むことを特徴とするマップマッチング方法。
【請求項７】
前記移動経路に含まれる前記リンクごとに、リンク進入時刻、リンク退出時刻、リンク移動時間を含む旅行時間データを算出するステップ、
を更に含むことを特徴とする請求項６に記載のマップマッチング方法。
【請求項８】
前記移動経路を特定するステップは、前記最寄り点の総数と前記最寄りリンクの総数とを用いるものであることを特徴とする請求項６または請求項７に記載のマップマッチング方法。
【請求項９】
前記移動経路を特定するステップは、前記最寄りリンクごとの前記最寄り点の総数を前記最寄りリンクの長さで除した値を用いるものであることを特徴とする請求項６または請求項７に記載のマップマッチング方法。
【請求項１０】
前記移動経路を特定するステップは、前記移動経路に含める前記リンクを１つずつ確定していくものであることを特徴とする請求項８または請求項９に記載のマップマッチング方法。
【請求項１１】
コンピュータを請求項１から請求項５までのいずれかに記載のマップマッチング装置として機能させるプログラム。
【請求項１】
位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング装置であって、
同一ユーザに係る前記プローブデータ群をデータ取得間隔に基づいて移動系列単位に分割する移動系列分割手段と、
同一移動系列に係る前記プローブデータ群を局所的に集約した集約データ群を生成する集約データ生成手段と、
前記集約データの移動方向を算出する移動方向算出手段と、
前記集約データを関連付ける候補リンクを検索する候補リンク検索手段と、
前記候補リンクの中から前記移動方向に最も近い方向を持つ最寄りリンクを決定する最寄りリンク決定手段と、
前記集約データの位置座標から前記最寄りリンクへ引いた垂線の足である最寄り点の集合を用いて前記移動経路を特定する移動経路特定手段と、
を具備することを特徴とするマップマッチング装置。
【請求項２】
前記移動経路に含まれる前記リンクごとに、リンク進入時刻、リンク退出時刻、リンク移動時間を含む旅行時間データを算出する旅行時間データ算出手段、
を更に具備することを特徴とする請求項１に記載のマップマッチング装置。
【請求項３】
前記移動経路特定手段は、前記最寄り点の総数と前記最寄りリンクに対するヒット数とを用いるものであることを特徴とする請求項１または請求項２に記載のマップマッチング装置。
【請求項４】
前記移動経路特定手段は、前記最寄りリンクごとの前記最寄り点の総数を前記最寄りリンクの長さで除した値を用いるものであることを特徴とする請求項１または請求項２に記載のマップマッチング装置。
【請求項５】
前記移動経路特定手段は、前記移動経路に含める前記リンクを１つずつ確定していくものであることを特徴とする請求項３または請求項４に記載のマップマッチング装置。
【請求項６】
位置情報と時刻情報とを含むプローブデータから、ノードとリンクとで構成されたデジタル道路地図データ上の移動経路を特定するマップマッチング方法であって、
同一ユーザに係る前記プローブデータ群をデータ取得間隔に基づいて移動系列単位に分割するステップと、
同一移動系列に係る前記プローブデータ群を局所的に集約した集約データ群を生成するステップと、
前記集約データの移動方向を算出するステップと、
前記集約データを関連付ける候補リンクを検索するステップと、
前記候補リンクの中から前記移動方向に最も近い方向を持つ最寄りリンクを決定するステップと、
前記集約データの位置座標から前記最寄りリンクへ引いた垂線の足である最寄り点の集合を用いて前記移動経路を特定するステップと、
を含むことを特徴とするマップマッチング方法。
【請求項７】
前記移動経路に含まれる前記リンクごとに、リンク進入時刻、リンク退出時刻、リンク移動時間を含む旅行時間データを算出するステップ、
を更に含むことを特徴とする請求項６に記載のマップマッチング方法。
【請求項８】
前記移動経路を特定するステップは、前記最寄り点の総数と前記最寄りリンクの総数とを用いるものであることを特徴とする請求項６または請求項７に記載のマップマッチング方法。
【請求項９】
前記移動経路を特定するステップは、前記最寄りリンクごとの前記最寄り点の総数を前記最寄りリンクの長さで除した値を用いるものであることを特徴とする請求項６または請求項７に記載のマップマッチング方法。
【請求項１０】
前記移動経路を特定するステップは、前記移動経路に含める前記リンクを１つずつ確定していくものであることを特徴とする請求項８または請求項９に記載のマップマッチング方法。
【請求項１１】
コンピュータを請求項１から請求項５までのいずれかに記載のマップマッチング装置として機能させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００９−９４４３（Ｐ２００９−９４４３Ａ）
【公開日】平成２１年１月１５日（２００９．１．１５）
【国際特許分類】
【出願番号】特願２００７−１７１５３１（Ｐ２００７−１７１５３１）
【出願日】平成１９年６月２９日（２００７．６．２９）
【出願人】（５９１１１５４７５）株式会社三菱総合研究所 (12)
【Ｆターム（参考）】
【公開日】平成２１年１月１５日（２００９．１．１５）
【国際特許分類】
【出願日】平成１９年６月２９日（２００７．６．２９）
【出願人】（５９１１１５４７５）株式会社三菱総合研究所 (12)
【Ｆターム（参考）】
[ Back to top ]