経路特定のための方法及び装置
【課題】移動デバイスが移動した経路を特定する。
【解決手段】本方法は、ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する方法である。各位置測定値には、その測定値が生成された測定時刻と、対応する測定精度とが関連付けられている。本方法は、ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するステップと、ｂ）前記位置測定値の中から、前記経路の第３の地点の候補として、その測定時刻が、選択された前記起点と選択された前記終点との間に存在するある位置測定値を選択するステップであって、前記候補の選択は、測定精度のより高い位置測定値が、測定精度のより低い位置測定値よりも優先されるように行われる、ステップと、ｃ）前記候補についての測定された座標を補正するステップであって、該座標を前記起点と前記終点とを繋ぐ線に向かって移動させて、前記候補についての補正された座標を得る、ステップと、ｄ）補正された座標を前記経路における実際の前記第３の地点として選択するステップとを含む。
【解決手段】本方法は、ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する方法である。各位置測定値には、その測定値が生成された測定時刻と、対応する測定精度とが関連付けられている。本方法は、ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するステップと、ｂ）前記位置測定値の中から、前記経路の第３の地点の候補として、その測定時刻が、選択された前記起点と選択された前記終点との間に存在するある位置測定値を選択するステップであって、前記候補の選択は、測定精度のより高い位置測定値が、測定精度のより低い位置測定値よりも優先されるように行われる、ステップと、ｃ）前記候補についての測定された座標を補正するステップであって、該座標を前記起点と前記終点とを繋ぐ線に向かって移動させて、前記候補についての補正された座標を得る、ステップと、ｄ）補正された座標を前記経路における実際の前記第３の地点として選択するステップとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路特定（path determination）のための方法及び装置に関する。
【背景技術】
【０００２】
移動デバイスにおいては、検知される位置データの品質及び密度が、（地形、天候等に起因する）周囲の環境とセンサの品質及び機能とに加えて、エネルギーの考慮により制限を受けることが度々ある。位置特定の精度はエネルギーの消費と相反するので、多くの場合、エネルギー消費を制限するために（ＧＰＳはＷＩＦＩによる位置特定よりも約２０倍大きなエネルギーを必要とする）、より低いか、あるいは動的なサンプリングレート、及びより精度の低いセンサ（ＧＰＳよりもＷＩＦＩ又はセルＩＤ追跡（CellID tracking）等）が用いられる。通常、質のよくない位置の全てをその（時間的な）順序に従って順に繋ぐだけでは、結果的に、検知された移動物体がとった実際の経路よりもはるかに長く、多くの場合、物体の実際の動きには対応し得ない部分的な経路を含む経路となる。これとは対照的に、通常、「最良の」測定値だけをとると、結果として、実際の経路よりもはるかに短く、かつかなり粗い経路が生まれる。結果的に、一連の生の位置データから直接的に生成された経路を用いて、ある時点における物体の速度といった派生データを信頼できる程度に推定することはできない。これでは、速度推定に基づいて、行程（エピソードとも呼ばれる）の開始及び終了、すなわち、静止状態とは対照的な、物体が移動した経路の部分、又は移動方法（車、徒歩等）を導き出す等の後の処理ステップの性能が制限されてしまう。
【０００３】
一連の位置データから経路を再現する標準的な方法は、異常値、すなわち、ＧＰＳシステムにおいて認識できる衛星の数が少ないことにより生じる系統的誤差（systematic error）などに起因する、観測時刻に関して隣接する他のサンプルからかけ離れた位置サンプルを最初に取り除くことである。これらの異常値は、数多くの平滑化の手法に計り知れない影響を及ぼす。予想される速度との適当な相関をもたらさない位置サンプルを取り除くために、多くの場合、速度に関するしきい値を利用する手法が用いられる。すなわち、あるサンプルが、先行するサンプルと後続のサンプルとを繋ぐセグメントにおいて現実的ではない高速値又は高加速値を示す場合には、当該サンプルは取り除かれる（例えば、非特許文献１又は２を参照されたい）。
【０００４】
データサンプルに関して高度（あるいは高さ）のデータが既知である場合（通常、ＧＰＳを用いて収集された場合にあてはまる）には、それらに関するしきい値を用いて異常値を特定することもできる（例えば、非特許文献３を参照されたい）。
【０００５】
異常値を取り除いた後に、例えば、ＧＰＳ信号のマルチパスによる反射によって引き起こされるランダム誤りの影響を最小限に抑えるために、窓（window）に基づく平滑化手法を用いるのが通例である。通常は、サンプルの所与のタイムスタンプが正確であり、導き出される速度値ではなく、サンプリングされた位置のみを平滑化するものとしている。最も一般的な平滑化手法は、移動平均（moving average, ＭＡ）を用いることである。これは、ｘ枠及びｙ枠に別々に適用される時間窓（time window）における直前のサンプル及び将来のサンプルに基づいた移動メディアンモデルとしても知られている。僅かに良い方法は、窓内の値に、ガウシアンカーネル（Gaussian kernel）に基づく局所回帰モデルを適用することである。これはＭＡ法の変形とみなすことができ、窓の中央にあるサンプルに対してより大きな重みを割り当てるものである。これに類似する方法は、残差平方和誤差（residual sum of squared errors）を最小にする最小二乗スプライン近似の方法であり、繰返し適用することによって改善することができる。最後に、速度及びプロセスのノイズを考慮して、ナビゲーションデータを平滑化するために、カルマンフィルタ（Kalman filter）が頻繁に用いられる。カルマンフィルタの最も重要な要素は、センサの想定される測定誤差であり、低減すべきランダム誤りの量を決定する。しかし、この測定誤差は通常、一定ではなく、環境の状態によって変化する。修正カルマンフィルタは実際の測定誤差を考慮するものであり、例えば、ＧＰＳの場合には、その質の基準は、衛星の数とＰＤＯＰ値とに基づいている（例えば、非特許文献４を参照されたい）。
【０００６】
上述した全ての手法は、経路再現問題に対して設計され適用される標準的な統計フィルタリング手法に基づくものである。したがって、これらの手法は、サンプリングされた値をデータの流れ（あるいはストリーム）とみなして、測定された順番でデータを処理するものであり、それらの多くは測定誤差が一定であることを前提としている。しかし、最近のモバイルロケーションシステムでは特に、測定値はＧＰＳ又はＷＩＦＩといった種々の検知方法から得られ、それゆえ、広い誤差分散を伴う。修正カルマンフィルタは、セルＩｄ追跡、ＷＩＦＩ又はＧＰＳといったモバイルポジショニングシステムから通常入手可能な一組のデータにおける精度推定を考慮する唯一の既知の手法である。しかし、他の全ての手法と同様、カルマンフィルタも測定順に処理を行い、サンプリングレートが一定であることを前提とするものである。
【０００７】
しかし、エネルギー効率の良いサンプリングシステムでは、多くの場合、適応的なレートが適用される（例えば、サンプリングレートは、都市部では高く、幹線道路では低い）。さらに、場合によっては、厳密な測定の瞬間に影響を及ぼすことすらできず、ｉＯＳ又はアンドロイドといった最新のモバイルＯＳの位置ＡＰＩに関して誤り率の異なる種々の位置検知サブシステム（ＧＰＳ、ＷＩＦＩ、セルＩＤ追跡）から得られる位置サンプルが不規則なレートで与えられる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】A. Thiagarajan, L. Ravindranath, K. LaCurts, S. Madden, H. Balakirshnan, S. Toledo, and J. Eriksson. VTrack: accurate, energy-aware road traffic delay estimation using mobile phones. In Proceedings of 7th ACM Conference on Embedded Networked Sensor Systems (SenSys’09), 2009
【非特許文献２】Z. Yan, C. Parent, S. Spaccapietra, and D. Chakraborty. A hyprid model and computing platform for spatio-semantic trajectories. In Proceedings of the Extended Semantic Web Conference (ESWC’2010), 2010
【非特許文献３】N. Schuessler and K. W. Axhausen. Processing GPS raw data without additional information. Technical report, Eidgenossische Technische Hochschule, Institut fur Verkehrsplanung und Transportsysteme, 2008
【非特許文献４】J. Jun, R. Guensler, and J. H. Ogle. Smoothing methods designed to minimize the impact of GPS random error on travel distance, speed and acceleration profile estimates. Geospatial Data Acquisition Technologies in Design and Construction, 2007
【発明の概要】
【課題を解決するための手段】
【０００９】
一実施形態によれば、ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する方法が提供される。各位置測定値には、該測定値が生成された測定時刻と、対応する測定精度とが関連付けられている。本方法は、ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するステップと、ｂ）前記位置測定値の中から、前記経路における第３の地点の候補として、測定時刻が、選択された前記起点と選択された前記終点との間に存在するある位置測定値を選択するステップであって、前記候補の選択は、測定精度のより高い位置測定値が、精度のより低い位置測定値よりも優先される、ステップと、ｃ）前記候補について測定された座標を補正するステップであって、該座標を前記起点と前記終点とを繋ぐ線に向かって移動させて、前記候補についての補正された座標が得られる、ステップと、ｄ）補正された座標を前記経路における実際の前記第３の地点として選択するステップとを含む。
【００１０】
精度に基づいて移動経路の地点を選択することにより、かつ選択された地点の座標の補正を更に行うことにより、サンプル測定値の品質が様々な場合であっても、特定する移動経路の全体的な精度を改善することができる。
【００１１】
一実施形態によれば、前記補正には、選択された前記候補の測定時刻と、前記移動デバイスの速度とに基づいて、前記起点と前記終点とを繋ぐ線上に前記候補の測定時刻において前記移動デバイスが位置することになる仮想的な位置を特定することと、前記仮想的な位置と前記経路における第３の地点の前記候補とを繋ぐ線上にある地点を、前記経路における実際の第３の地点として選択することとが含まれる。
【００１２】
この手法によれば、経路において実際に選択される地点は、一方では、起点及び終点の精度がより高いことを考慮し、他方では、候補地点の精度及び移動デバイスの速度を考慮したものとなる。このようにして、移動経路について選択される実際の地点を得るために良好かつ情報に基づいた選択を行うことができる。
【００１３】
一実施形態によれば、前記経路における前記選択された第３の地点を新たな起点又は新たな終点として用いてステップａ）〜ｄ）が再帰的に行われる。
【００１４】
このようにして、移動経路を再帰的に特定することができる。
【００１５】
一実施形態によれば、前記実際の第３の地点は、前記候補の測定精度を考慮することに基づいて選択される。
【００１６】
これは、実際の第３の地点を、その測定精度が起点及び終点の精度よりも実際には低いことを考慮することにより選択する、適切かつ有利な方法である。
【００１７】
一実施形態によれば、前記実際の第３の地点は、前記候補の測定精度内に依然として存在しつつも、前記仮想的な位置のできる限り近くに位置するものとなるように選択される。
【００１８】
これは、実際の測定値と、起点及び終点の測定精度が候補地点の測定精度よりも高いという事実との良好な妥協点（あるいは歩み寄り）である。
【００１９】
一実施形態によれば、起点と終点との間の速度を考慮することに基づいて、実際の第３の地点が選択される。より具体的には、一実施形態によれば、選択される地点が前記起点と前記終点との間を直結する線（direct line）からどの程度ずれうる（あるいは逸脱しうる）かを、移動デバイスの速度に応じて判断することにより、速度が考慮される。
【００２０】
このようにして、例えば、高速の場合、実際には、起点と終点との間を直結する線からの小さなずれ（あるいは逸脱）のみが現実的であるということを考慮することができる。
【００２１】
一実施形態によれば、前記実際の第３の地点は、前記起点と前記終点との間の速度と、前記候補の測定精度とを考慮することに基づいて選択される。
【００２２】
このようにして、実際の第３の地点を求める際に、より多くのパラメータを考慮することができる。
【００２３】
一実施形態によれば、前記移動デバイスの速度は、前記起点の測定時刻と前記終点の測定時刻と前記起点と前記終点との間の距離とに基づいて求められる。
【００２４】
これは、移動デバイスの速度を求めるための都合の良い方法である。
【００２５】
一実施形態によれば、起点及び終点としてそれぞれ選択される前記２つの位置測定値は、選択される前記２つの位置測定値間のある時点において生成された位置測定値がいずれも、選択される前記２つの位置測定値よりも高い精度を有しないものとなるように選択される。
【００２６】
これは、アルゴリズムににて起点を選択するのに適した方法である。
【００２７】
一実施形態によれば、前記複数の位置測定値は、それぞれ精度が異なる少なくとも２つの異なる測定方法により得られる。
【００２８】
これは、本アルゴリズムを、サンプル測定値が精度の異なる様々な測定方法により得られるようなシナリオに適用できることを考慮したものである。
【００２９】
一実施形態によれば、ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する装置が提供される。各位置測定値には、該測定値が生成された測定時刻と、対応する測定精度とが関連付けられている。本装置は、ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するモジュールと、ｂ）前記位置測定値の中から、前記経路における第３の地点の候補として、測定時刻が、選択された前記起点と選択された前記終点との間に存在する位置測定値を選択するモジュールであって、前記候補の選択は、測定精度のより高い位置測定値が、精度のより低い位置測定値よりも優先されて行われる、モジュールと、ｃ）前記候補について測定された座標を補正するモジュールであって、該座標を前記起点と前記終点との間を繋ぐ線に向かって移動させて、前記候補についての補正された座標が得られるようにする、モジュールと、ｄ）補正された座標を前記経路における実際の前記第３の地点として選択するモジュールとを有する。
【００３０】
これは、本発明の一実施形態による装置を実現するのに適した方法である。
【００３１】
一実施形態によれば、前記装置は、本発明の実施の形態のうちの１つによる方法を実行するモジュールを更に有する。
【００３２】
一実施形態によれば、本発明の実施形態のうちの１つによる方法をコンピュータに実行させるコンピュータプログラムコードを有するコンピュータプログラムが提供される。
【図面の簡単な説明】
【００３３】
【図１】移動経路及び一組のサンプル測定値を示す概略図である。
【図２】図１のサンプル測定値をその測定精度とともに示す説明図である。
【図３】本発明の一実施形態による経路特定方法を示す説明図である。
【図４】本発明の別の実施形態による経路特定方法を示す説明図である。
【発明を実施するための形態】
【００３４】
まず、以下の説明で用いる幾つかの用語について説明する。
【００３５】
ＧＰＳ： グローバルポジショニングシステム（Global Positioning System）
ＷＩＦＩ： ＩＥＥＥ８０２．１１標準規格に基づく無線ローカルエリアネットワーク
セルＩＤ追跡（CellID tracking）： 移動電話基地局装置の位置に基づく位置決め方法
【００３６】
一実施形態によれば、生の位置センサデータから得られる品質のよくない経路を、ロバストな方法で改善することができ、それにより、経路に基づいたサービスの品質及び対象範囲を向上させることのできる方法が提案される。
【００３７】
一実施形態によれば、通常の統計的な平滑化フィルタではなく、幾何学的なバックグラウンドを有する経路再現方法が提供される。一実施形態によれば、主な着想は、所与の窓内の最も正確な測定値が、再現しようとする経路上の地点を正確に表すものと仮定した上で、そのような地点から開始することにある。続いて、次に最も正確な測定値が再帰的に追加され、それまでに前後に追加された地点と追加されることになる実際の地点とのタイムスタンプ、精度及び位置の情報に基づいて、元の経路の地点に対応する可能性がより高い位置にそれらの測定値を動かすことにより、それらの測定値が「補正」あるいは「調整」される。先のセクションにて要約した従来の手法とは異なり、本手法は、測定精度に基づいた順序で測定値を処理する。
【００３８】
提案される方法は、様々な検知方法が関わることに起因して、従来のモバイルロケーションＡＰＩによってもたらされるような位置測定精度の大きな変動に関し、ロバストであるという利点を有している。これは、この方法が、処理の順序を決定する際に、測定値の所与の精度を考慮するためである。さらに、平滑化の判断においても、精度が考慮される。このようにして、提案される方法は、所与の一組のデータにおいて入手可能であり、かつこれまでに用いられていなかった情報を考慮することにより、より多くの情報に基づくものとなる。また、提案される方法は、可変のサンプリングレートを有する一組のデータにも適用できる。このような可変のサンプリングレートは通常、モバイルポジショニングシステムのエネルギー効率の良いサンプリング方式によるものである。最後に、この方法は、フットポッド（footpod）又はバイクのスピードまたは動き（cadence）のセンサといった別の検知装置から得られる付加的な速度推定値を直接的に統合することにも対応している。
【００３９】
以下、本発明の更なる実施形態を詳しく説明する。
【００４０】
以下の例では、それぞれのタイムスタンプによって順序付けられる位置決めサンプルの系列（あるいは集合）
【数１】
が得られていることを前提とする。各サンプルは以下の情報を有している。
・Ｘ座標
・Ｙ座標
・タイムスタンプ
・距離（その位置を中心とする半径）として与えられる精度
・速度（任意）
【００４１】
例えば、ある時間窓に基づいて、一組のサンプルを選択することができるか、又は単に、測定された、存在する全てのサンプルを用いることができる。あるいは、地理的な窓（エリア）を選択することができ、その際、一組のサンプルは、このエリアに入る測定値からなる。サンプル測定値を求めるためのこの２つの判定基準をともに用いることもでき、それにより、サンプル測定値はある時間窓内に、かつある地理的窓内に存在することになる。そして、本手法の役割は、サンプルデータの位置測定値が得られた移動デバイスが移動したルート又は経路を特定することである。
【００４２】
一組のデータは、様々な環境の状態においてデータを供給する種々の検知サブシステムの統合に起因した、精度が大きく異なる測定値を含む場合がある。例えば、トンネルでは、ＧＰＳサブシステムからは何の結果も提供されない場合があるが、それでも、精度の低いセルＩＤ追跡に基づくサブシステムによれば位置を推定することができる。一実施形態では、一組のデータから系統的誤差が既に取り除かれていることを更に前提とする。例えば、実際の位置に関する最初の要求には、通常、モバイルロケーションＡＰＩが、かなり不正確なサンプルを用いて非常に迅速に応じ、その後、ＧＰＳサブシステムが位置（fix）を捕えると、より正確なサンプルを用いて応ずる。この場合、系統的誤差をフィルタリングした後に、一組のデータ内には、より正確な（ＧＰＳからの）測定値のみが残るものと仮定することができる。
【００４３】
続いて、提案される手法は、一組のサンプルに基づいて以下に説明するように移動経路を特定する。
【００４４】
図１は、本発明の一実施形態が適用される状況を示している。街路（薄いグレー表示）を示す地図が示されており、さらに、移動経路、すなわち移動デバイスがそれに沿って実際に移動した経路である黒色の太線が示されている。さらに、測定され、それに基づいて移動経路が特定又は再現される４つの位置サンプル（ｘ，ｙ）も示されている。
【００４５】
図２にも４つの測定値を示しているが、ここではそれぞれの精度ｒもあわせて示している。時間順において最初の測定値１（ｘ１，ｙ１，ｒ１）は最も精度の高い測定値であり、一連の測定値の中で最後の測定値（ｘ４，ｙ４，ｒ４）は、２番目に精度の高いものである。（測定時刻に関して）その間に行われた測定は、精度が比較的低いこともわかる。
【００４６】
図２に示したサンプル測定値を用いて、次に、本発明による経路特定手法を、図３を参照して説明する。
【００４７】
全部でｄ個のサンプル測定値を含む、サンプル測定値の集合
【数２】
が存在するものとする。本実施形態では、図２に示した４つの測定値が存在するが、この数は例示にすぎない。
【００４８】
一般性を失うことなく、所与のタイムスタンプに基づいたサンプルの時間的順序に関して最初の位置決めサンプル（以下、Ｐ（インデックスｐ＝０）とする。
【数３】
である。）と、最後の位置決めサンプル（以下、Ｎ（インデックスｎ＝（ｄ−１））とする。
【数４】
である。）との間にある測定値はいずれも、Ｐ又はＮよりも精度が高くないものと仮定することができる。したがって、利用可能なサンプル測定値から、例えば、集合
【数５】
を選択することができる。Ｐ及びＮの座標は、再現しようとしている経路内の対応する位置を極力反映しているとみなされるので（その他のサンプル測定値はそれより精度が高くないため）、その位置を補正又は調整することなく、結果として生成される集合に直ちに追加される。
【００４９】
その後、本実施形態は、特定しようとしている経路に追加すべき次のサンプル測定値の選択に進む。追加すべき次のサンプル測定値は、選択判定基準ｃ１に基づいて選択される。これは測定精度に基づくものである。測定精度に基づく判定基準ｃ１を適用することは、より測定精度の高い位置測定値ほど、より測定精度の低い位置測定値よりも好ましいということを意味する。このため、判定基準ｃ１による一実施形態では、追加しようとする、
【数６】
においてインデックスがｔである次に最良の測定値Ｔ１が、測定時刻に関してＰとＮとの間に存在するサンプル測定値の部分集合、すなわち、部分集合
【数７】
から選択される。この部分集合が空である場合には、判定基準を満たす測定値を見つけることができないため、プロセスは中止される。
【００５０】
判定基準ｃ１は、非常に簡単な場合には、部分集合において次に最も精度の高いサンプル測定値が決定され、このサンプル測定値を、特定しようとするルートのための次の位置候補Ｔ１として単純に選択することを意味する。この例を図３に示している。Ｐ及びＮの次に最も精度の高い測定値は（ｘ３，ｙ３，ｒ３，ｔ３）であり、この測定値が、経路を特定するための次の候補測定値Ｔ１として選択される。
【００５１】
部分集合内に、Ｐ及びＮの精度に最も近い同じ精度を有する２つ以上のサンプル測定値が存在する場合には、本手法は、一実施形態によれば、同じ測定精度を有する
【数８】
のこの所与の部分集合から、
【数９】
における順序に関して（すなわち、測定時刻に関して）この集合の中央にある測定値を候補Ｔ１として選択する。このことは、Ｐ及びＮの次に最も高い精度を有し、かつ測定時刻に関してＰとＮとの間の中央に極力近くに存在する測定サンプルＴ１が選択されることを意味する。
【００５２】
一実施形態によれば、更に複雑な別の判定基準ｃ１により、ＰとＴ１との間、及びＴ１とＮとの間のサンプルの数のバランスをとろうと試みることもできる。
【００５３】
経路の候補地点としてＴ１が選択されると、その測定された座標の補正又は調整が行われる。これは、当該候補地点の測定精度が地点Ｐ及び地点Ｎのそれよりも低いことを考慮するために行われる。このような状況に照らして、測定された当該候補地点の座標は、移動デバイスの実際の移動経路を考慮すると実際に座標が存在するはずである場所よりも、ＰとＮとを直接繋ぐ線から離れて位置する可能性がある。この理由から、そしてこのことを考慮するために、サンプル測定値Ｔ１に関して測定された座標を、測定値Ｐ及びＮを接続する（直結する）線に向かって移動させる補正が行われる。このとき、当該座標が再現しようとしている経路に対応する可能性がより高くなるように、補正がなされる。
【００５４】
直結する線に向かって候補地点を移動させる非常に簡単な方法は、例えば、単に、直結する線までの距離に沿ってその地点を半分だけ移動させることか、直結する線までの距離に沿って３分の１だけ移動させることか、Ｐ及びＮを直結する線に向かって任意のその他の所定の長さにわたり移動させることかであろう。このようにして、候補地点が、Ｐ及びＮを直結する線に向かってシフトされ、それにより、候補地点の測定値が、（Ｐ及びＮの測定値よりも精度が低いことに起因して）その「実際の」位置が直結する線により近くなるように偏っている可能性があることを考慮する。候補地点をＰ及びＮを直結する線に向けてシフトすることによって、この偏りをある程度補償することができる。
【００５５】
以下、図３を参照して、一実施形態においてこの補正がどのように行われるかを説明する。
【００５６】
補正を行うために、最初に、Ｔの時間的な投影（projection）に基づいて、ＰとＮとの間の線上の位置Ｘ１を特定する。すなわち、Ｘ１は、Ｐ及びＮのタイムスタンプを考慮し、かつ速度が一定であると仮定して、Ｔ１のタイムスタンプにおけるＰとＮとの間の線上の位置を示すものである。ＰとＮとの経路にＸ１を追加しても、結果として、いかなる速度の増加も生じないことに留意されたい。
【００５７】
そして、次のステップでは、Ｔ１’が、Ｔ１に対応する、再現しようとする経路の位置にある可能性がより高くなるように、判定基準ｃ２を用いて、Ｔ１とＸ１との間の線上の位置Ｔ１’を特定する。一実施形態によれば、判定基準ｃ２は、単にＴ１の精度を考慮し、線Ｔ１Ｘ１と、Ｔ１の精度に相当する半径を有するＴ１の回りの円との交点にＴ１を移動させる。Ｔ１の補正後の座標を得るためのこの手法を図３に示している。Ｔ１の精度を示す半径上にある正方形は補正された候補Ｔ１’であり、これは、移動経路又は経路の「実際の第３の地点（actual third point）」として選択される。
【００５８】
しかし、別の実施形態によれば、補正を行うために、更に複雑な判定基準ｃ２を用いることもできる。このような判定基準ｃ２によれば、例えば、Ｐ、Ｔ１、Ｎの別の属性を考慮することができる。一例は、Ｔ１’の位置をＰとＮとの間の速度に依存させることである。例えば、選択される地点Ｔ１’が直結する線ＰＮからどの程度ずれて（あるいは逸脱して）いるかを定義又は規定する規則又は方法がある。例えば、速度が相対的に大きいか、又はあるしきい値（例えば、８０ｋｍ／ｈ）を超える場合には、Ｔ１の精度からも外れて、Ｐ及びＮを直結する線ＰＮのより近くに存在するものとなるように地点Ｔ１’を選択することができる。さらには、ＰとＮとの間の速度と、線ＰＮからの地点Ｔ１’のずれ（あるいは逸脱）の程度（deviation）と、Ｔ１’の測定精度とに応じて、それに対応する測定値を完全に捨てる（drop）と判断することもできる。その目的のために、Ｐ及びＮの速度の組合せと、線ＰＮからの地点Ｔ１’のずれの程度と、実際の候補地点が直結する線からどの程度ずれる可能性があるかを示すＴ１’の測定精度とを定める、対応するルックアップテーブルを設けることができる。例えば、高速の場合には、直結する線からのずれの程度を０に近いものとし、高速の場合には移動デバイスがジグザグの経路に沿って移動しないということを考慮することができる。
【００５９】
次の反復ステップを示しており、以下に説明する図４は、補正される候補Ｔ２’が候補Ｔ２の測定範囲を越えて位置決めされる状況を示している。
【００６０】
最終的に、Ｔの左側にある位置サンプル
【数１０】
と、Ｔの右側にある
【数１１】
とに対して本方法が再帰的に適用される。このような次の反復ステップを図４に示している。図３の起点Ｐがここでも起点である。しかし、図４に示している反復ステップにおいては、それまでに選択されている実際の第３の地点Ｔ１’が新たな終点Ｎ２となる。
【００６１】
そして、次の候補Ｔ２として選択される次のサンプル測定値は、次に精度が高い測定値であり、それは（ｘ２，ｙ２，ｒ２，ｔ２）である。そしてまた、これらの座標の補正が行われる。図４から明らかなように、結果として、補正された地点Ｔ２’は、Ｔ２の精度の半径を越えて位置している。
【００６２】
そして、本方法は、上記のようにステップを繰り返してかつ反復的に実行することにより、更に進むことになる。一実施形態によれば、本プロセスは部分集合が空になると終了する。
【００６３】
上記の実施形態は、ハードウェアによって実施することもでき、ソフトウェアによって実施することもでき、ソフトウェア及びハードウェアの組み合わせによって実施することもできることが当業者には理解されよう。本発明の実施形態に関して説明したモジュール及び機能は、本発明の実施形態に関して説明した方法に従って動作するように適切にプログラミングされたマイクロプロセッサ又はコンピュータによって全体的に実施することもできるし、部分的に実施することもできる。本発明の一実施形態を実施する装置には、例えば、コンピュータ、ＰＤＡ、移動電話、スマートフォン、又は同様の任意のものが含まれうる。
【技術分野】
【０００１】
本発明は経路特定（path determination）のための方法及び装置に関する。
【背景技術】
【０００２】
移動デバイスにおいては、検知される位置データの品質及び密度が、（地形、天候等に起因する）周囲の環境とセンサの品質及び機能とに加えて、エネルギーの考慮により制限を受けることが度々ある。位置特定の精度はエネルギーの消費と相反するので、多くの場合、エネルギー消費を制限するために（ＧＰＳはＷＩＦＩによる位置特定よりも約２０倍大きなエネルギーを必要とする）、より低いか、あるいは動的なサンプリングレート、及びより精度の低いセンサ（ＧＰＳよりもＷＩＦＩ又はセルＩＤ追跡（CellID tracking）等）が用いられる。通常、質のよくない位置の全てをその（時間的な）順序に従って順に繋ぐだけでは、結果的に、検知された移動物体がとった実際の経路よりもはるかに長く、多くの場合、物体の実際の動きには対応し得ない部分的な経路を含む経路となる。これとは対照的に、通常、「最良の」測定値だけをとると、結果として、実際の経路よりもはるかに短く、かつかなり粗い経路が生まれる。結果的に、一連の生の位置データから直接的に生成された経路を用いて、ある時点における物体の速度といった派生データを信頼できる程度に推定することはできない。これでは、速度推定に基づいて、行程（エピソードとも呼ばれる）の開始及び終了、すなわち、静止状態とは対照的な、物体が移動した経路の部分、又は移動方法（車、徒歩等）を導き出す等の後の処理ステップの性能が制限されてしまう。
【０００３】
一連の位置データから経路を再現する標準的な方法は、異常値、すなわち、ＧＰＳシステムにおいて認識できる衛星の数が少ないことにより生じる系統的誤差（systematic error）などに起因する、観測時刻に関して隣接する他のサンプルからかけ離れた位置サンプルを最初に取り除くことである。これらの異常値は、数多くの平滑化の手法に計り知れない影響を及ぼす。予想される速度との適当な相関をもたらさない位置サンプルを取り除くために、多くの場合、速度に関するしきい値を利用する手法が用いられる。すなわち、あるサンプルが、先行するサンプルと後続のサンプルとを繋ぐセグメントにおいて現実的ではない高速値又は高加速値を示す場合には、当該サンプルは取り除かれる（例えば、非特許文献１又は２を参照されたい）。
【０００４】
データサンプルに関して高度（あるいは高さ）のデータが既知である場合（通常、ＧＰＳを用いて収集された場合にあてはまる）には、それらに関するしきい値を用いて異常値を特定することもできる（例えば、非特許文献３を参照されたい）。
【０００５】
異常値を取り除いた後に、例えば、ＧＰＳ信号のマルチパスによる反射によって引き起こされるランダム誤りの影響を最小限に抑えるために、窓（window）に基づく平滑化手法を用いるのが通例である。通常は、サンプルの所与のタイムスタンプが正確であり、導き出される速度値ではなく、サンプリングされた位置のみを平滑化するものとしている。最も一般的な平滑化手法は、移動平均（moving average, ＭＡ）を用いることである。これは、ｘ枠及びｙ枠に別々に適用される時間窓（time window）における直前のサンプル及び将来のサンプルに基づいた移動メディアンモデルとしても知られている。僅かに良い方法は、窓内の値に、ガウシアンカーネル（Gaussian kernel）に基づく局所回帰モデルを適用することである。これはＭＡ法の変形とみなすことができ、窓の中央にあるサンプルに対してより大きな重みを割り当てるものである。これに類似する方法は、残差平方和誤差（residual sum of squared errors）を最小にする最小二乗スプライン近似の方法であり、繰返し適用することによって改善することができる。最後に、速度及びプロセスのノイズを考慮して、ナビゲーションデータを平滑化するために、カルマンフィルタ（Kalman filter）が頻繁に用いられる。カルマンフィルタの最も重要な要素は、センサの想定される測定誤差であり、低減すべきランダム誤りの量を決定する。しかし、この測定誤差は通常、一定ではなく、環境の状態によって変化する。修正カルマンフィルタは実際の測定誤差を考慮するものであり、例えば、ＧＰＳの場合には、その質の基準は、衛星の数とＰＤＯＰ値とに基づいている（例えば、非特許文献４を参照されたい）。
【０００６】
上述した全ての手法は、経路再現問題に対して設計され適用される標準的な統計フィルタリング手法に基づくものである。したがって、これらの手法は、サンプリングされた値をデータの流れ（あるいはストリーム）とみなして、測定された順番でデータを処理するものであり、それらの多くは測定誤差が一定であることを前提としている。しかし、最近のモバイルロケーションシステムでは特に、測定値はＧＰＳ又はＷＩＦＩといった種々の検知方法から得られ、それゆえ、広い誤差分散を伴う。修正カルマンフィルタは、セルＩｄ追跡、ＷＩＦＩ又はＧＰＳといったモバイルポジショニングシステムから通常入手可能な一組のデータにおける精度推定を考慮する唯一の既知の手法である。しかし、他の全ての手法と同様、カルマンフィルタも測定順に処理を行い、サンプリングレートが一定であることを前提とするものである。
【０００７】
しかし、エネルギー効率の良いサンプリングシステムでは、多くの場合、適応的なレートが適用される（例えば、サンプリングレートは、都市部では高く、幹線道路では低い）。さらに、場合によっては、厳密な測定の瞬間に影響を及ぼすことすらできず、ｉＯＳ又はアンドロイドといった最新のモバイルＯＳの位置ＡＰＩに関して誤り率の異なる種々の位置検知サブシステム（ＧＰＳ、ＷＩＦＩ、セルＩＤ追跡）から得られる位置サンプルが不規則なレートで与えられる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】A. Thiagarajan, L. Ravindranath, K. LaCurts, S. Madden, H. Balakirshnan, S. Toledo, and J. Eriksson. VTrack: accurate, energy-aware road traffic delay estimation using mobile phones. In Proceedings of 7th ACM Conference on Embedded Networked Sensor Systems (SenSys’09), 2009
【非特許文献２】Z. Yan, C. Parent, S. Spaccapietra, and D. Chakraborty. A hyprid model and computing platform for spatio-semantic trajectories. In Proceedings of the Extended Semantic Web Conference (ESWC’2010), 2010
【非特許文献３】N. Schuessler and K. W. Axhausen. Processing GPS raw data without additional information. Technical report, Eidgenossische Technische Hochschule, Institut fur Verkehrsplanung und Transportsysteme, 2008
【非特許文献４】J. Jun, R. Guensler, and J. H. Ogle. Smoothing methods designed to minimize the impact of GPS random error on travel distance, speed and acceleration profile estimates. Geospatial Data Acquisition Technologies in Design and Construction, 2007
【発明の概要】
【課題を解決するための手段】
【０００９】
一実施形態によれば、ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する方法が提供される。各位置測定値には、該測定値が生成された測定時刻と、対応する測定精度とが関連付けられている。本方法は、ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するステップと、ｂ）前記位置測定値の中から、前記経路における第３の地点の候補として、測定時刻が、選択された前記起点と選択された前記終点との間に存在するある位置測定値を選択するステップであって、前記候補の選択は、測定精度のより高い位置測定値が、精度のより低い位置測定値よりも優先される、ステップと、ｃ）前記候補について測定された座標を補正するステップであって、該座標を前記起点と前記終点とを繋ぐ線に向かって移動させて、前記候補についての補正された座標が得られる、ステップと、ｄ）補正された座標を前記経路における実際の前記第３の地点として選択するステップとを含む。
【００１０】
精度に基づいて移動経路の地点を選択することにより、かつ選択された地点の座標の補正を更に行うことにより、サンプル測定値の品質が様々な場合であっても、特定する移動経路の全体的な精度を改善することができる。
【００１１】
一実施形態によれば、前記補正には、選択された前記候補の測定時刻と、前記移動デバイスの速度とに基づいて、前記起点と前記終点とを繋ぐ線上に前記候補の測定時刻において前記移動デバイスが位置することになる仮想的な位置を特定することと、前記仮想的な位置と前記経路における第３の地点の前記候補とを繋ぐ線上にある地点を、前記経路における実際の第３の地点として選択することとが含まれる。
【００１２】
この手法によれば、経路において実際に選択される地点は、一方では、起点及び終点の精度がより高いことを考慮し、他方では、候補地点の精度及び移動デバイスの速度を考慮したものとなる。このようにして、移動経路について選択される実際の地点を得るために良好かつ情報に基づいた選択を行うことができる。
【００１３】
一実施形態によれば、前記経路における前記選択された第３の地点を新たな起点又は新たな終点として用いてステップａ）〜ｄ）が再帰的に行われる。
【００１４】
このようにして、移動経路を再帰的に特定することができる。
【００１５】
一実施形態によれば、前記実際の第３の地点は、前記候補の測定精度を考慮することに基づいて選択される。
【００１６】
これは、実際の第３の地点を、その測定精度が起点及び終点の精度よりも実際には低いことを考慮することにより選択する、適切かつ有利な方法である。
【００１７】
一実施形態によれば、前記実際の第３の地点は、前記候補の測定精度内に依然として存在しつつも、前記仮想的な位置のできる限り近くに位置するものとなるように選択される。
【００１８】
これは、実際の測定値と、起点及び終点の測定精度が候補地点の測定精度よりも高いという事実との良好な妥協点（あるいは歩み寄り）である。
【００１９】
一実施形態によれば、起点と終点との間の速度を考慮することに基づいて、実際の第３の地点が選択される。より具体的には、一実施形態によれば、選択される地点が前記起点と前記終点との間を直結する線（direct line）からどの程度ずれうる（あるいは逸脱しうる）かを、移動デバイスの速度に応じて判断することにより、速度が考慮される。
【００２０】
このようにして、例えば、高速の場合、実際には、起点と終点との間を直結する線からの小さなずれ（あるいは逸脱）のみが現実的であるということを考慮することができる。
【００２１】
一実施形態によれば、前記実際の第３の地点は、前記起点と前記終点との間の速度と、前記候補の測定精度とを考慮することに基づいて選択される。
【００２２】
このようにして、実際の第３の地点を求める際に、より多くのパラメータを考慮することができる。
【００２３】
一実施形態によれば、前記移動デバイスの速度は、前記起点の測定時刻と前記終点の測定時刻と前記起点と前記終点との間の距離とに基づいて求められる。
【００２４】
これは、移動デバイスの速度を求めるための都合の良い方法である。
【００２５】
一実施形態によれば、起点及び終点としてそれぞれ選択される前記２つの位置測定値は、選択される前記２つの位置測定値間のある時点において生成された位置測定値がいずれも、選択される前記２つの位置測定値よりも高い精度を有しないものとなるように選択される。
【００２６】
これは、アルゴリズムににて起点を選択するのに適した方法である。
【００２７】
一実施形態によれば、前記複数の位置測定値は、それぞれ精度が異なる少なくとも２つの異なる測定方法により得られる。
【００２８】
これは、本アルゴリズムを、サンプル測定値が精度の異なる様々な測定方法により得られるようなシナリオに適用できることを考慮したものである。
【００２９】
一実施形態によれば、ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する装置が提供される。各位置測定値には、該測定値が生成された測定時刻と、対応する測定精度とが関連付けられている。本装置は、ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するモジュールと、ｂ）前記位置測定値の中から、前記経路における第３の地点の候補として、測定時刻が、選択された前記起点と選択された前記終点との間に存在する位置測定値を選択するモジュールであって、前記候補の選択は、測定精度のより高い位置測定値が、精度のより低い位置測定値よりも優先されて行われる、モジュールと、ｃ）前記候補について測定された座標を補正するモジュールであって、該座標を前記起点と前記終点との間を繋ぐ線に向かって移動させて、前記候補についての補正された座標が得られるようにする、モジュールと、ｄ）補正された座標を前記経路における実際の前記第３の地点として選択するモジュールとを有する。
【００３０】
これは、本発明の一実施形態による装置を実現するのに適した方法である。
【００３１】
一実施形態によれば、前記装置は、本発明の実施の形態のうちの１つによる方法を実行するモジュールを更に有する。
【００３２】
一実施形態によれば、本発明の実施形態のうちの１つによる方法をコンピュータに実行させるコンピュータプログラムコードを有するコンピュータプログラムが提供される。
【図面の簡単な説明】
【００３３】
【図１】移動経路及び一組のサンプル測定値を示す概略図である。
【図２】図１のサンプル測定値をその測定精度とともに示す説明図である。
【図３】本発明の一実施形態による経路特定方法を示す説明図である。
【図４】本発明の別の実施形態による経路特定方法を示す説明図である。
【発明を実施するための形態】
【００３４】
まず、以下の説明で用いる幾つかの用語について説明する。
【００３５】
ＧＰＳ： グローバルポジショニングシステム（Global Positioning System）
ＷＩＦＩ： ＩＥＥＥ８０２．１１標準規格に基づく無線ローカルエリアネットワーク
セルＩＤ追跡（CellID tracking）： 移動電話基地局装置の位置に基づく位置決め方法
【００３６】
一実施形態によれば、生の位置センサデータから得られる品質のよくない経路を、ロバストな方法で改善することができ、それにより、経路に基づいたサービスの品質及び対象範囲を向上させることのできる方法が提案される。
【００３７】
一実施形態によれば、通常の統計的な平滑化フィルタではなく、幾何学的なバックグラウンドを有する経路再現方法が提供される。一実施形態によれば、主な着想は、所与の窓内の最も正確な測定値が、再現しようとする経路上の地点を正確に表すものと仮定した上で、そのような地点から開始することにある。続いて、次に最も正確な測定値が再帰的に追加され、それまでに前後に追加された地点と追加されることになる実際の地点とのタイムスタンプ、精度及び位置の情報に基づいて、元の経路の地点に対応する可能性がより高い位置にそれらの測定値を動かすことにより、それらの測定値が「補正」あるいは「調整」される。先のセクションにて要約した従来の手法とは異なり、本手法は、測定精度に基づいた順序で測定値を処理する。
【００３８】
提案される方法は、様々な検知方法が関わることに起因して、従来のモバイルロケーションＡＰＩによってもたらされるような位置測定精度の大きな変動に関し、ロバストであるという利点を有している。これは、この方法が、処理の順序を決定する際に、測定値の所与の精度を考慮するためである。さらに、平滑化の判断においても、精度が考慮される。このようにして、提案される方法は、所与の一組のデータにおいて入手可能であり、かつこれまでに用いられていなかった情報を考慮することにより、より多くの情報に基づくものとなる。また、提案される方法は、可変のサンプリングレートを有する一組のデータにも適用できる。このような可変のサンプリングレートは通常、モバイルポジショニングシステムのエネルギー効率の良いサンプリング方式によるものである。最後に、この方法は、フットポッド（footpod）又はバイクのスピードまたは動き（cadence）のセンサといった別の検知装置から得られる付加的な速度推定値を直接的に統合することにも対応している。
【００３９】
以下、本発明の更なる実施形態を詳しく説明する。
【００４０】
以下の例では、それぞれのタイムスタンプによって順序付けられる位置決めサンプルの系列（あるいは集合）
【数１】
が得られていることを前提とする。各サンプルは以下の情報を有している。
・Ｘ座標
・Ｙ座標
・タイムスタンプ
・距離（その位置を中心とする半径）として与えられる精度
・速度（任意）
【００４１】
例えば、ある時間窓に基づいて、一組のサンプルを選択することができるか、又は単に、測定された、存在する全てのサンプルを用いることができる。あるいは、地理的な窓（エリア）を選択することができ、その際、一組のサンプルは、このエリアに入る測定値からなる。サンプル測定値を求めるためのこの２つの判定基準をともに用いることもでき、それにより、サンプル測定値はある時間窓内に、かつある地理的窓内に存在することになる。そして、本手法の役割は、サンプルデータの位置測定値が得られた移動デバイスが移動したルート又は経路を特定することである。
【００４２】
一組のデータは、様々な環境の状態においてデータを供給する種々の検知サブシステムの統合に起因した、精度が大きく異なる測定値を含む場合がある。例えば、トンネルでは、ＧＰＳサブシステムからは何の結果も提供されない場合があるが、それでも、精度の低いセルＩＤ追跡に基づくサブシステムによれば位置を推定することができる。一実施形態では、一組のデータから系統的誤差が既に取り除かれていることを更に前提とする。例えば、実際の位置に関する最初の要求には、通常、モバイルロケーションＡＰＩが、かなり不正確なサンプルを用いて非常に迅速に応じ、その後、ＧＰＳサブシステムが位置（fix）を捕えると、より正確なサンプルを用いて応ずる。この場合、系統的誤差をフィルタリングした後に、一組のデータ内には、より正確な（ＧＰＳからの）測定値のみが残るものと仮定することができる。
【００４３】
続いて、提案される手法は、一組のサンプルに基づいて以下に説明するように移動経路を特定する。
【００４４】
図１は、本発明の一実施形態が適用される状況を示している。街路（薄いグレー表示）を示す地図が示されており、さらに、移動経路、すなわち移動デバイスがそれに沿って実際に移動した経路である黒色の太線が示されている。さらに、測定され、それに基づいて移動経路が特定又は再現される４つの位置サンプル（ｘ，ｙ）も示されている。
【００４５】
図２にも４つの測定値を示しているが、ここではそれぞれの精度ｒもあわせて示している。時間順において最初の測定値１（ｘ１，ｙ１，ｒ１）は最も精度の高い測定値であり、一連の測定値の中で最後の測定値（ｘ４，ｙ４，ｒ４）は、２番目に精度の高いものである。（測定時刻に関して）その間に行われた測定は、精度が比較的低いこともわかる。
【００４６】
図２に示したサンプル測定値を用いて、次に、本発明による経路特定手法を、図３を参照して説明する。
【００４７】
全部でｄ個のサンプル測定値を含む、サンプル測定値の集合
【数２】
が存在するものとする。本実施形態では、図２に示した４つの測定値が存在するが、この数は例示にすぎない。
【００４８】
一般性を失うことなく、所与のタイムスタンプに基づいたサンプルの時間的順序に関して最初の位置決めサンプル（以下、Ｐ（インデックスｐ＝０）とする。
【数３】
である。）と、最後の位置決めサンプル（以下、Ｎ（インデックスｎ＝（ｄ−１））とする。
【数４】
である。）との間にある測定値はいずれも、Ｐ又はＮよりも精度が高くないものと仮定することができる。したがって、利用可能なサンプル測定値から、例えば、集合
【数５】
を選択することができる。Ｐ及びＮの座標は、再現しようとしている経路内の対応する位置を極力反映しているとみなされるので（その他のサンプル測定値はそれより精度が高くないため）、その位置を補正又は調整することなく、結果として生成される集合に直ちに追加される。
【００４９】
その後、本実施形態は、特定しようとしている経路に追加すべき次のサンプル測定値の選択に進む。追加すべき次のサンプル測定値は、選択判定基準ｃ１に基づいて選択される。これは測定精度に基づくものである。測定精度に基づく判定基準ｃ１を適用することは、より測定精度の高い位置測定値ほど、より測定精度の低い位置測定値よりも好ましいということを意味する。このため、判定基準ｃ１による一実施形態では、追加しようとする、
【数６】
においてインデックスがｔである次に最良の測定値Ｔ１が、測定時刻に関してＰとＮとの間に存在するサンプル測定値の部分集合、すなわち、部分集合
【数７】
から選択される。この部分集合が空である場合には、判定基準を満たす測定値を見つけることができないため、プロセスは中止される。
【００５０】
判定基準ｃ１は、非常に簡単な場合には、部分集合において次に最も精度の高いサンプル測定値が決定され、このサンプル測定値を、特定しようとするルートのための次の位置候補Ｔ１として単純に選択することを意味する。この例を図３に示している。Ｐ及びＮの次に最も精度の高い測定値は（ｘ３，ｙ３，ｒ３，ｔ３）であり、この測定値が、経路を特定するための次の候補測定値Ｔ１として選択される。
【００５１】
部分集合内に、Ｐ及びＮの精度に最も近い同じ精度を有する２つ以上のサンプル測定値が存在する場合には、本手法は、一実施形態によれば、同じ測定精度を有する
【数８】
のこの所与の部分集合から、
【数９】
における順序に関して（すなわち、測定時刻に関して）この集合の中央にある測定値を候補Ｔ１として選択する。このことは、Ｐ及びＮの次に最も高い精度を有し、かつ測定時刻に関してＰとＮとの間の中央に極力近くに存在する測定サンプルＴ１が選択されることを意味する。
【００５２】
一実施形態によれば、更に複雑な別の判定基準ｃ１により、ＰとＴ１との間、及びＴ１とＮとの間のサンプルの数のバランスをとろうと試みることもできる。
【００５３】
経路の候補地点としてＴ１が選択されると、その測定された座標の補正又は調整が行われる。これは、当該候補地点の測定精度が地点Ｐ及び地点Ｎのそれよりも低いことを考慮するために行われる。このような状況に照らして、測定された当該候補地点の座標は、移動デバイスの実際の移動経路を考慮すると実際に座標が存在するはずである場所よりも、ＰとＮとを直接繋ぐ線から離れて位置する可能性がある。この理由から、そしてこのことを考慮するために、サンプル測定値Ｔ１に関して測定された座標を、測定値Ｐ及びＮを接続する（直結する）線に向かって移動させる補正が行われる。このとき、当該座標が再現しようとしている経路に対応する可能性がより高くなるように、補正がなされる。
【００５４】
直結する線に向かって候補地点を移動させる非常に簡単な方法は、例えば、単に、直結する線までの距離に沿ってその地点を半分だけ移動させることか、直結する線までの距離に沿って３分の１だけ移動させることか、Ｐ及びＮを直結する線に向かって任意のその他の所定の長さにわたり移動させることかであろう。このようにして、候補地点が、Ｐ及びＮを直結する線に向かってシフトされ、それにより、候補地点の測定値が、（Ｐ及びＮの測定値よりも精度が低いことに起因して）その「実際の」位置が直結する線により近くなるように偏っている可能性があることを考慮する。候補地点をＰ及びＮを直結する線に向けてシフトすることによって、この偏りをある程度補償することができる。
【００５５】
以下、図３を参照して、一実施形態においてこの補正がどのように行われるかを説明する。
【００５６】
補正を行うために、最初に、Ｔの時間的な投影（projection）に基づいて、ＰとＮとの間の線上の位置Ｘ１を特定する。すなわち、Ｘ１は、Ｐ及びＮのタイムスタンプを考慮し、かつ速度が一定であると仮定して、Ｔ１のタイムスタンプにおけるＰとＮとの間の線上の位置を示すものである。ＰとＮとの経路にＸ１を追加しても、結果として、いかなる速度の増加も生じないことに留意されたい。
【００５７】
そして、次のステップでは、Ｔ１’が、Ｔ１に対応する、再現しようとする経路の位置にある可能性がより高くなるように、判定基準ｃ２を用いて、Ｔ１とＸ１との間の線上の位置Ｔ１’を特定する。一実施形態によれば、判定基準ｃ２は、単にＴ１の精度を考慮し、線Ｔ１Ｘ１と、Ｔ１の精度に相当する半径を有するＴ１の回りの円との交点にＴ１を移動させる。Ｔ１の補正後の座標を得るためのこの手法を図３に示している。Ｔ１の精度を示す半径上にある正方形は補正された候補Ｔ１’であり、これは、移動経路又は経路の「実際の第３の地点（actual third point）」として選択される。
【００５８】
しかし、別の実施形態によれば、補正を行うために、更に複雑な判定基準ｃ２を用いることもできる。このような判定基準ｃ２によれば、例えば、Ｐ、Ｔ１、Ｎの別の属性を考慮することができる。一例は、Ｔ１’の位置をＰとＮとの間の速度に依存させることである。例えば、選択される地点Ｔ１’が直結する線ＰＮからどの程度ずれて（あるいは逸脱して）いるかを定義又は規定する規則又は方法がある。例えば、速度が相対的に大きいか、又はあるしきい値（例えば、８０ｋｍ／ｈ）を超える場合には、Ｔ１の精度からも外れて、Ｐ及びＮを直結する線ＰＮのより近くに存在するものとなるように地点Ｔ１’を選択することができる。さらには、ＰとＮとの間の速度と、線ＰＮからの地点Ｔ１’のずれ（あるいは逸脱）の程度（deviation）と、Ｔ１’の測定精度とに応じて、それに対応する測定値を完全に捨てる（drop）と判断することもできる。その目的のために、Ｐ及びＮの速度の組合せと、線ＰＮからの地点Ｔ１’のずれの程度と、実際の候補地点が直結する線からどの程度ずれる可能性があるかを示すＴ１’の測定精度とを定める、対応するルックアップテーブルを設けることができる。例えば、高速の場合には、直結する線からのずれの程度を０に近いものとし、高速の場合には移動デバイスがジグザグの経路に沿って移動しないということを考慮することができる。
【００５９】
次の反復ステップを示しており、以下に説明する図４は、補正される候補Ｔ２’が候補Ｔ２の測定範囲を越えて位置決めされる状況を示している。
【００６０】
最終的に、Ｔの左側にある位置サンプル
【数１０】
と、Ｔの右側にある
【数１１】
とに対して本方法が再帰的に適用される。このような次の反復ステップを図４に示している。図３の起点Ｐがここでも起点である。しかし、図４に示している反復ステップにおいては、それまでに選択されている実際の第３の地点Ｔ１’が新たな終点Ｎ２となる。
【００６１】
そして、次の候補Ｔ２として選択される次のサンプル測定値は、次に精度が高い測定値であり、それは（ｘ２，ｙ２，ｒ２，ｔ２）である。そしてまた、これらの座標の補正が行われる。図４から明らかなように、結果として、補正された地点Ｔ２’は、Ｔ２の精度の半径を越えて位置している。
【００６２】
そして、本方法は、上記のようにステップを繰り返してかつ反復的に実行することにより、更に進むことになる。一実施形態によれば、本プロセスは部分集合が空になると終了する。
【００６３】
上記の実施形態は、ハードウェアによって実施することもでき、ソフトウェアによって実施することもでき、ソフトウェア及びハードウェアの組み合わせによって実施することもできることが当業者には理解されよう。本発明の実施形態に関して説明したモジュール及び機能は、本発明の実施形態に関して説明した方法に従って動作するように適切にプログラミングされたマイクロプロセッサ又はコンピュータによって全体的に実施することもできるし、部分的に実施することもできる。本発明の一実施形態を実施する装置には、例えば、コンピュータ、ＰＤＡ、移動電話、スマートフォン、又は同様の任意のものが含まれうる。
【特許請求の範囲】
【請求項１】
ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する方法であって、各位置測定値には、その測定値が生成された測定時刻と、対応する測定精度とが関連付けられており、
ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するステップと、
ｂ）前記位置測定値の中から、前記経路の第３の地点の候補として、その測定時刻が、選択された前記起点と選択された前記終点との間に存在するある位置測定値を選択するステップであって、起点及び終点としてそれぞれ選択されている前記２つの位置測定値は、該選択されている２つの位置測定値の間のある時刻において生成された位置測定値がいずれも、選択されている前記２つの位置測定値よりも高い精度を有しないものとなるように選択されており、前記候補の選択は、測定精度のより高い位置測定値が、精度のより低い位置測定値よりも優先されるように行われる、ステップと、
ｃ）前記候補についての測定された座標を補正するステップであって、該座標を前記起点と前記終点とを繋ぐ線に向かって移動させて、前記候補についての補正された座標を得る、ステップと、
ｄ）前記補正された座標を前記経路における実際の前記第３の地点として選択するステップと
を含む方法。
【請求項２】
前記補正には、
選択された前記候補の測定時刻と、前記起点の測定時刻と前記終点の測定時刻と前記起点と前記終点との間の距離とに基づいて求められる前記移動デバイスの速度とに基づいて、前記起点と前記終点とを繋ぐ線上に前記候補の測定時刻において前記移動デバイスが位置することになる仮想的な位置を特定することと、
前記仮想的な位置と前記経路における第３の地点の前記候補とを繋ぐ線上のある地点を、前記経路における実際の第３の地点として選択することと
が含まれる、請求項１に記載の方法。
【請求項３】
前記経路における前記選択された第３の地点を新たな起点又は新たな終点として用いて前記ステップａ）〜ｄ）が再帰的に実行される、請求項１又は２に記載の方法。
【請求項４】
前記実際の第３の地点は、前記候補の測定精度の考慮に基づいて選択される、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記実際の第３の地点は、前記候補の測定精度内に依然として位置しつつも、前記仮想的な位置のできる限り近くに位置するものとなるように選択される、請求項４に記載の方法。
【請求項６】
前記実際の第３の地点は、前記起点と前記終点との間の速度を考慮することに基づいて選択される、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記実際の第３の地点は、前記起点と前記終点との間の速度と、前記候補の測定精度とを考慮することに基づいて選択される、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記複数の位置測定値は、精度がそれぞれ異なる少なくとも２つの異なる測定方法により得られるものである、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する装置であって、各位置測定値には、その測定値が生成された測定時刻と、対応する測定精度とが関連付けられており、
ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するモジュールであって、起点及び終点としてそれぞれ選択される前記２つの位置測定値は、該選択される２つの位置測定値の間のある時刻において生成された位置測定値がいずれも、選択される前記２つの位置測定値よりも高い精度を有しないものとなるように選択される、モジュールと、
ｂ）前記位置測定値の中から、前記経路の第３の地点の候補として、その測定時刻が、選択された前記起点と選択された前記終点との間に存在するある位置測定値を選択するモジュールであって、前記候補の選択は、測定精度のより高い位置測定値が、精度のより低い位置測定値よりも優先されるように行われる、モジュールと、
ｃ）前記候補についての測定された座標を補正するモジュールであって、該座標を前記起点と前記終点とを繋ぐ線に向かって移動させて、前記候補についての補正された座標を得る、モジュールと、
ｄ）前記補正された座標を前記経路における実際の前記第３の地点として選択するモジュールと
を有する装置。
【請求項１０】
前記補正には、
選択された前記候補の測定時刻と、前記起点の測定時刻と前記終点の測定時刻と前記起点と前記終点との間の距離とに基づいて求められる前記移動デバイスの速度とに基づいて、前記起点と前記終点とを繋ぐ線上に前記候補の測定時刻において前記移動デバイスが位置することになる仮想的な位置を特定することと、
前記仮想的な位置と前記経路における第３の地点の前記候補とを繋ぐ線上のある地点を、前記経路における実際の第３の地点として選択することと
が含まれる、請求項９に記載の装置。
【請求項１１】
請求項３〜８のいずれか一項に記載のステップを実行するモジュールを更に有する請求項９又は１０に記載の装置。
【請求項１２】
請求項１〜８のいずれか一項に記載の方法をコンピュータに実行させるコンピュータプログラムコードを有するコンピュータプログラム。
【請求項１】
ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する方法であって、各位置測定値には、その測定値が生成された測定時刻と、対応する測定精度とが関連付けられており、
ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するステップと、
ｂ）前記位置測定値の中から、前記経路の第３の地点の候補として、その測定時刻が、選択された前記起点と選択された前記終点との間に存在するある位置測定値を選択するステップであって、起点及び終点としてそれぞれ選択されている前記２つの位置測定値は、該選択されている２つの位置測定値の間のある時刻において生成された位置測定値がいずれも、選択されている前記２つの位置測定値よりも高い精度を有しないものとなるように選択されており、前記候補の選択は、測定精度のより高い位置測定値が、精度のより低い位置測定値よりも優先されるように行われる、ステップと、
ｃ）前記候補についての測定された座標を補正するステップであって、該座標を前記起点と前記終点とを繋ぐ線に向かって移動させて、前記候補についての補正された座標を得る、ステップと、
ｄ）前記補正された座標を前記経路における実際の前記第３の地点として選択するステップと
を含む方法。
【請求項２】
前記補正には、
選択された前記候補の測定時刻と、前記起点の測定時刻と前記終点の測定時刻と前記起点と前記終点との間の距離とに基づいて求められる前記移動デバイスの速度とに基づいて、前記起点と前記終点とを繋ぐ線上に前記候補の測定時刻において前記移動デバイスが位置することになる仮想的な位置を特定することと、
前記仮想的な位置と前記経路における第３の地点の前記候補とを繋ぐ線上のある地点を、前記経路における実際の第３の地点として選択することと
が含まれる、請求項１に記載の方法。
【請求項３】
前記経路における前記選択された第３の地点を新たな起点又は新たな終点として用いて前記ステップａ）〜ｄ）が再帰的に実行される、請求項１又は２に記載の方法。
【請求項４】
前記実際の第３の地点は、前記候補の測定精度の考慮に基づいて選択される、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記実際の第３の地点は、前記候補の測定精度内に依然として位置しつつも、前記仮想的な位置のできる限り近くに位置するものとなるように選択される、請求項４に記載の方法。
【請求項６】
前記実際の第３の地点は、前記起点と前記終点との間の速度を考慮することに基づいて選択される、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記実際の第３の地点は、前記起点と前記終点との間の速度と、前記候補の測定精度とを考慮することに基づいて選択される、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記複数の位置測定値は、精度がそれぞれ異なる少なくとも２つの異なる測定方法により得られるものである、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
ある移動デバイスの複数の位置測定値に基づいて、該移動デバイスが移動した経路を特定する装置であって、各位置測定値には、その測定値が生成された測定時刻と、対応する測定精度とが関連付けられており、
ａ）前記複数の位置測定値の中から、前記経路の起点として１つ、前記経路の終点として１つの計２つの位置測定値を選択するモジュールであって、起点及び終点としてそれぞれ選択される前記２つの位置測定値は、該選択される２つの位置測定値の間のある時刻において生成された位置測定値がいずれも、選択される前記２つの位置測定値よりも高い精度を有しないものとなるように選択される、モジュールと、
ｂ）前記位置測定値の中から、前記経路の第３の地点の候補として、その測定時刻が、選択された前記起点と選択された前記終点との間に存在するある位置測定値を選択するモジュールであって、前記候補の選択は、測定精度のより高い位置測定値が、精度のより低い位置測定値よりも優先されるように行われる、モジュールと、
ｃ）前記候補についての測定された座標を補正するモジュールであって、該座標を前記起点と前記終点とを繋ぐ線に向かって移動させて、前記候補についての補正された座標を得る、モジュールと、
ｄ）前記補正された座標を前記経路における実際の前記第３の地点として選択するモジュールと
を有する装置。
【請求項１０】
前記補正には、
選択された前記候補の測定時刻と、前記起点の測定時刻と前記終点の測定時刻と前記起点と前記終点との間の距離とに基づいて求められる前記移動デバイスの速度とに基づいて、前記起点と前記終点とを繋ぐ線上に前記候補の測定時刻において前記移動デバイスが位置することになる仮想的な位置を特定することと、
前記仮想的な位置と前記経路における第３の地点の前記候補とを繋ぐ線上のある地点を、前記経路における実際の第３の地点として選択することと
が含まれる、請求項９に記載の装置。
【請求項１１】
請求項３〜８のいずれか一項に記載のステップを実行するモジュールを更に有する請求項９又は１０に記載の装置。
【請求項１２】
請求項１〜８のいずれか一項に記載の方法をコンピュータに実行させるコンピュータプログラムコードを有するコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１３−６１３３１（Ｐ２０１３−６１３３１Ａ）
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−１９７１２６（Ｐ２０１２−１９７１２６）
【出願日】平成２４年９月７日（２０１２．９．７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．アンドロイド
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Ｆターム（参考）】
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【出願番号】特願２０１２−１９７１２６（Ｐ２０１２−１９７１２６）
【出願日】平成２４年９月７日（２０１２．９．７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．アンドロイド
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Ｆターム（参考）】
[ Back to top ]