(57)【特許請求の範囲】
【請求項１】
複数のノードをリンクで連結したパスを複数含む経路グラフの前記ノードのうち、複数の観測点の時系列で表される軌跡に含まれる各観測点間の線分に対応するノードの２つずつの各組み合わせと前記線分とのフレシェ距離の最大値を計算する計算部と、
前記軌跡に含まれる各線分について前記計算部で計算された前記最大値が最小となる、前記軌跡に対応するパスを抽出する抽出部と、
を含む経路情報処理装置。
【請求項２】
前記計算部は、前記線分及び該線分に対応するノードを探索して、前記軌跡に対応するパスを更新しながら抽出する場合には、新たに探索されたノードの２つずつの各組み合わせと前記線分とのフレシェ距離、及び既に計算されているフレシェ距離の最大値を計算する請求項１記載の経路情報処理装置。
【請求項３】
前記計算部は、前記ノードの２つずつの各組み合わせと前記線分とのフレシェ距離を、各ノードから最短距離となる線分上の点の各々の順番と、前記各ノードの順番とが同じ場合には、前記最短距離のうち大きい方とし、前記各ノードから最短距離となる線分上の点の順番と、前記各ノードの順番とが逆の場合には、２つのノードの垂直二等分線と前記線分との交点といずれかのノードとの距離、及びいずれか一方のノードから最短距離となる線分上の点と他方のノードとの距離と前記いずれか一方のノードからの最短距離との大きい方のうち最小の距離とする請求項１または請求項２記載の経路情報処理装置。
【請求項４】
前記線分に対応するノードを、前記線分から所定距離以内に存在するノードとする請求項１〜請求項３のいずれか１項記載の経路情報処理装置。
【請求項５】
コンピュータに、
複数のノードをリンクで連結したパスを複数含む経路グラフの前記ノードのうち、複数の観測点の時系列で表される軌跡に含まれる各観測点間の線分に対応するノードの２つずつの各組み合わせと前記線分とのフレシェ距離の最大値を計算し、
前記軌跡に含まれる各線分について計算された前記最大値が最小となる、前記軌跡に対応するパスを抽出する
ことを含む処理を実行させる経路情報処理方法。
【請求項６】
コンピュータに、
複数のノードをリンクで連結したパスを複数含む経路グラフの前記ノードのうち、複数の観測点の時系列で表される軌跡に含まれる各観測点間の線分に対応するノードの２つずつの各組み合わせと前記線分とのフレシェ距離の最大値を計算し、
前記軌跡に含まれる各線分について計算された前記最大値が最小となる、前記軌跡に対応するパスを抽出する
ことを含む処理を実行させるための経路情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路情報処理装置、経路情報処理方法、及び経路情報処理プログラムに関する。
【背景技術】
【０００２】
空間情報分析として、移動体の経路に関する分析を行う技術が存在する。例えば、実際の観測データである複数の軌跡データが示す軌跡の各々から、指定された地点を出発地点または到着地点とする経路を検索するＯＤ（Ｏ＝“Origin”：出発地点、Ｄ＝“Destination”：到着地点）検索を行う技術が存在する。また、複数の軌跡から、所定回数（例えば、１０回）以上出現する出発地点と到着地点との組み合わせ（例えば、（新宿駅−渋谷駅）、（品川駅−池袋駅）等）を示す頻出ＯＤを分析する技術が存在する。また、軌跡の中から、例えば、品川駅→（山手線外回り）→池袋駅を通過する経路のように、部分経路を検索する技術が存在する。さらに、軌跡の中に、所定回数（例えば、１０回）以上出現する部分経路を示す頻出部分経路を分析する技術が存在する。
【０００３】
上記のような経路分析に用いられる軌跡を示す軌跡データは、誤差を含んでいたり、観測タイミングが異なっていたりするために、そのまま経路分析に用いることは困難である。そこで、経路分析の前処理として、例えば、複数の軌跡を統合して簡潔に表した経路グラフに軌跡を対応させることが行われている。
【０００４】
例えば、グラフ探索アリゴリズムを用いて、軌跡の経路グラフへのマッチングを行う技術が提案されている。この技術では、軌跡に含まれる観測点と経路グラフ上のリンクとの距離の総和が最小になるようにマッチングする。
【０００５】
また、経路グラフと軌跡との類似度としてフレシェ距離を用い、類似度が閾値以上の経路グラフのパスを、軌跡に対応するパスとして抽出する技術が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−３２５０８３号公報
【非特許文献】
【０００７】
【非特許文献１】H. Alt, A. Efrat, G. Rote, and C. Wenk, ”Matching planar maps”, J. Algorithms 49, 262−283, 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、軌跡に含まれる観測点と経路グラフ上のリンクとの距離の総和が最小になるようにマッチングする場合、軌跡が、Ｕターンやループなどのように移動の方向が変わる部分を含むと、距離を正しく見積もれない場合がある。上記の従来技術では、Ｕターンやループする区間については、「マップ照合不可」としている。
【０００９】
一方、フレシェ距離を軌跡と経路グラフとの類似度として用いる場合、移動の方向などを考慮することができる。しかし、フレシェ距離を用いた上記の従来技術では、軌跡との類似度が閾値以上の経路グラフのパスを抽出する際、最も類似度の高いパスが抽出できるとは限らない。そのため、類似度が閾値以上のパスを抽出するアルゴリズムの反復により、最も類似度の高いパスを抽出することになる。従って、最も類似度の高いパスを抽出するために、経路グラフに含まれる全パスについて総当り的に類似度を計算することになり、計算コストが高くなるという問題がある。
【００１０】
本発明は、一つの側面として、軌跡が移動の方向が変わる部分を含む場合でも、軌跡と経路グラフ上のパスとの類似度を効率良く求めることを目的とする。
【課題を解決するための手段】
【００１１】
一つの態様として、複数のノードをリンクで連結したパスを複数含む経路グラフの前記ノードのうち、複数の観測点の時系列で表される軌跡に含まれる各観測点間の線分に対応するノードの２つずつの各組み合わせと前記線分とのフレシェ距離の最大値を計算する。そして、前記軌跡に含まれる各線分について前記計算部で計算された前記最大値が最小となる、前記軌跡に対応するパスを抽出する。
【発明の効果】
【００１２】
一つの側面として、軌跡が移動の方向が変わる部分を含む場合でも、軌跡と経路グラフ上のパスとの類似度を効率良く求めることができる、という効果を有する。
【図面の簡単な説明】
【００１３】
【図１】経路情報処理システムの概略構成及び本実施形態に係る経路情報処理装置の機能ブロックを示す図である。
【図２】軌跡データの一例を示す図である。
【図３】経路グラフの一例を示す図である。
【図４】軌跡及び経路グラフの一例を概略的に示す図である。
【図５】軌跡内の観測点間の線分と経路グラフのノードとの対応付けを説明するための図である。
【図６】軌跡内の観測点間の線分と経路グラフのノードとの対応付けを説明するための図である。
【図７】更新時の軌跡内の観測点間の線分と経路グラフのノードとの対応付けを説明するための図である。
【図８】線分と２つのノード間のフレシェ距離εＸ，Ｙの計算に用いるマトリクスの一例である。
【図９】ノードから線分までの最短距離を説明するための図である。
【図１０】ノードの順番が逆になる場合のフレシェ距離εＸ，Ｙの計算方法の一例を説明するための図である。
【図１１】更新時の線分と２つのノード間のフレシェ距離εＸ，Ｙの計算の一例を説明するための図である。
【図１２】経路情報処理装置として機能するコンピュータの概略構成の一例を示すブロック図である。
【図１３】経路情報処理の一例を示すフローチャートである。
【図１４】軌跡及び経路グラフの一例を概略的に示す図である。
【図１５】線分の番号を説明するための図である。
【図１６】距離計算処理の一例を示すフローチャートである。
【図１７】初期の距離計算処理を説明するための図である。
【図１８】初期の距離計算処理を説明するための図である。
【図１９】初期の距離計算処理を説明するための図である。
【図２０】初期の距離計算処理後のリストＱ及びリストＬの一例を示す図である。
【図２１】ループ１の処理対象のデータの抜き出しを説明するための図である。
【図２２】２段目の距離計算処理を説明するための図である。
【図２３】２段目の距離計算処理を説明するための図である。
【図２４】２段目の距離計算処理を説明するための図である。
【図２５】２段目の距離計算処理（ループ１）後のリストＱ及びリストＬの一例を示す図である。
【図２６】ループ２の処理対象のデータの抜き出しを説明するための図である。
【図２７】２段目の距離計算処理（ループ２）後のリストＱ及びリストＬの一例を示す図である。
【図２８】ループ３の処理対象のデータの抜き出しを説明するための図である。
【図２９】２段目の距離計算処理（ループ３）後のリストＱ及びリストＬの一例を示す図である。
【図３０】ループ４の処理対象のデータの抜き出しを説明するための図である。
【図３１】ループ５の処理対象のデータの抜き出しを説明するための図である。
【図３２】２段目の距離計算処理（ループ５）後のリストＱ及びリストＬの一例を示す図である。
【図３３】ループ６の処理対象のデータの抜き出しを説明するための図である。
【図３４】２段目の距離計算処理（ループ６）後のリストＱ及びリストＬの一例を示す図である。
【図３５】ループ７の処理対象のデータの抜き出しを説明するための図である。
【図３６】２段目の距離計算処理（ループ７）後のリストＱ及びリストＬの一例を示す図である。
【図３７】ループ８の処理対象のデータの抜き出しを説明するための図である。
【図３８】ループ９の処理対象のデータの抜き出しを説明するための図である。
【図３９】２段目の距離計算処理（ループ９）後のリストＱ及びリストＬの一例を示す図である。
【図４０】ループ１０の処理対象のデータの抜き出しを説明するための図である。
【図４１】正規化済軌跡データの一例を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施形態の一例を詳細に説明する。
【００１５】
図１に示すように、本実施形態に係る経路情報処理装置１０は、軌跡データ生成装置２２と、軌跡データ記憶部２４と、経路グラフ記憶部２５と共に、経路情報処理システム２０に含まれる。
【００１６】
軌跡データ生成装置２２は、移動体の位置を観測するセンサ２６の各々で定期的に観測された移動体の位置を示す観測データを、ネットワーク２８を介して取得する。センサ２６は、移動体の一例である人が保持する携帯電話、スマートフォン等の端末や、移動体の一例である車両に搭載されたカーナビゲーションシステム等で利用されるＧＰＳ等とすることができる。観測データには、観測点毎の緯度及び経度で示される位置データと観測時刻、並びにセンサ２６を識別するセンサＩＤが含まれる。軌跡データ生成装置２２は、取得した複数の観測データを、センサＩＤ毎に抽出し、各観測データに含まれる位置データを、観測時刻に基づいて時系列に並べて軌跡データを生成する。軌跡データにより、移動体がどのように移動したかを示す軌跡が特定される。軌跡データ生成装置２２は、生成した複数の軌跡データを、軌跡データ記憶部２４に記憶する。
【００１７】
軌跡データ記憶部２４には、例えば、図２に示すように、軌跡データの識別子（軌跡ＩＤ、例えばセンサＩＤ）と、その軌跡に含まれる各観測点の識別子（観測点ＩＤ）と、各観測点のｘ座標及びｙ座標とが対応付けて記憶される。なお、ｘ座標及びｙ座標は、例えば緯度及び経度である。
【００１８】
また、経路グラフ記憶部２５には、経路グラフが記憶されている。経路グラフは、例えば、複数の軌跡を統合して生成されたものであり、複数のノードと、ノード間を結ぶリンクで表される。経路グラフ記憶部２５には、例えば、図３に示すように、各ノードの識別子（ノードＩＤ）と、各ノードのｘ座標及びｙ座標とが対応付けて記憶され、さらに、リンク情報が記憶される。図３の例では、リンク情報は、リンクの両端のノードのノードＩＤを「＿（アンダーバー）」で接続した表記で表している。なお、以下では、観測点ＩＤがｉの観測点を「観測点ｉ」、ノードＩＤがＸのノードを「ノードＸ」と表記する。
【００１９】
軌跡データ記憶部２４は、軌跡データ生成装置２２に設けられた記憶装置であってもよいし、軌跡データ生成装置２２とは別の外部装置として設けられた記憶装置であってもよい。また、軌跡データ記憶部２４及び経路グラフ記憶部２５の各々は、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の可搬型記憶媒体であってもよい。
【００２０】
図１に示すように、経路情報処理装置１０は、取得部１１と、計算部１２と、抽出部１３とを備える。
【００２１】
取得部１１は、軌跡データ記憶部２４から、軌跡ＩＤをキーに、正規化対象（正規化については後述）の軌跡データを１つ取得する。また、取得部１１は、経路グラフ記憶部２５から経路グラフを取得する。取得する経路グラフは、経路グラフ全体でもよいし、正規化対象の軌跡データを含む所定範囲の部分グラフであってもよい。
【００２２】
図４に、取得部１１が取得する軌跡データが示す軌跡及び経路グラフの一例を概略的に示す。図４の例では、軌跡の観測点を四角内に観測点ＩＤを記した表記で表し、時系列順で連続する観測点間を実線の線分で結んで表している。また、経路グラフの各ノードを丸内にノードＩＤを記した表記で表し、ノード間を結ぶリンクを破線で表している。以下の図においても、軌跡及び経路グラフの表記方法は同様である。なお、本実施形態では、軌跡データについて、観測点の時系列順に、観測点ＩＤ＝１，２，・・・を付与している。また、経路グラフの各ノードの順番は、ノード間のリンク情報及びノードＩＤから判断可能であるものとする。図４の例では、経路グラフの各ノードは、ノードＡ→Ｂ→Ｃ→Ｄ→Ｅ→Ｆの順で並んでいる。
【００２３】
計算部１２は、軌跡の観測点間の線分と、その線分に対応するノードの系列で表されるパスとの類似度を計算する。
【００２４】
本実施形態では、軌跡が表す移動体の移動の方向を考慮する類似度として、フレシェ距離を用いる。フレシェ距離は、軌跡と経路グラフとを対応付け、対応付けられた点間の距離の最大値をとる距離である。そして、グラフ探索アルゴリズムを用いて、軌跡とのフレシェ距離が最も近い経路グラフ上のパスを、正規化した軌跡として抽出する。これにより、移動の方向も考慮した上で、効率的に軌跡を正規化する。
【００２５】
ここで、図５に示すように、軌跡の観測点間の線分と経路グラフのノードとが１対１に対応する場合には、線分と一番近いノードとの距離を計算すればよいため問題はない。しかし、図６に示すように、１つの線分に複数のノードが対応付けられる場合、計算コストが高くなる。なお、線分に対応するノードとは、例えば、線分から所定距離以内に存在するノードのことである。また、軌跡と経路グラフとの距離については、経路グラフのリンクと対応する軌跡の観測点との距離で求めてもよい。この場合も、１つのリンクに複数の観測点が対応付けられる場合には、同様に計算コストが高くなる。
【００２６】
さらに、線分に複数のノードが対応付けられる場合、ノードの順番が前後しないような対応付けを行わなければ、軌跡を正確に反映したパスを抽出することができない。例えば、線分と各ノードとが最短距離となるように、ノードから線分へ延びる垂線で対応付けした場合、図６の左図に示すように、ノードに対応する線分上の点の順番が、Ａ→Ｃ→Ｂ→Ｄとなってしまい、本来のＡ→Ｂ→Ｃ→Ｄとは異なってしまう。本来のノードの順番Ａ→Ｂ→Ｃ→Ｄを保持するためには、図６の右図に示すように、ノードの順番を考慮してノードと線分とを対応付ける必要がある。
【００２７】
また、特に、図７に示すように、隣接するノードを探索しながら軌跡に対応するパスを更新する場合には、対応付けが変化することがある。図７の例では、ノードＢと、観測点１と観測点２との間の線分（以下、観測点ｉと観測点ｉ＋１との間の線分を「線分ｉ＿ｉ＋１」と表記する）との対応点は、ノードＢ、・・・、Ｄ、・・・、Ｆと探索が進む都度、変化している。従って、対応点が変化する都度、ノードと線分との距離を再計算する必要があり、計算コストは増加する。
【００２８】
そこで、本実施形態では、計算部１２は、経路グラフのノードに対応する軌跡の線分上の対応点は決定せず、線分と対応するノード間の距離の計算のみを行う。また、計算部１２は、線分に複数のノードが対応する場合には、対応する複数のノードの２つずつの各組合せと線分とのフレシェ距離を計算し、さらにその最大値であるフレシェ距離を、線分とその線分に対応するノードを含むパスとの類似度とする。
【００２９】
例えば、図４に示す軌跡（観測点１及び２）と、経路グラフ（パス：ノードＡ→Ｂ→Ｃ→Ｄ→Ｅ→Ｄ）とのフレシェ距離ε０の計算について説明する。この例では、線分１＿２に、ノードＡ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦの複数のノードが対応している。
【００３０】
ノードの２つずつの組み合わせの一方のノードをノードＸ、他方のノードをノードＹとする。そして、線分１＿２と、ノードＸ及びノードＹの各々とのフレシェ距離の大きい方をεＸ，Ｙとする。計算部１２は、ノードＸとノードＹとの組み合わせ毎に、フレシェ距離εＸ，Ｙの各々を計算し、図８に示すように、ノードＸとノードＹとの全ての組み合わせに対応するマトリクスの各マスに記録する。そして、計算部１２は、マトリクスに記録されたフレシェ距離εＸ，Ｙの最大値（図８の例では「４２．４」）を、線分１＿２と経路グラフとの類似度を表すフレシェ距離ε０とする。
【００３１】
また、計算部１２は、ノードの順番を考慮するため、各フレシェ距離εＸ，Ｙを、以下のように計算する。まず、図９に示すように、各ノードから線分までの最短距離を求める。最短距離は、ノードから線分に降ろした垂線の足が線分上に含まれる場合には、その垂線の長さである。垂線の足が線分に含まれない場合には、ノードから近い方の観測点までの距離である。ノードＸ及びＹに対応する垂線の足または近い方の観測点をｌＸ及びｌＹとし、最短距離をｄ（Ｘ，ｌＸ）及びｄ（Ｙ，ｌＹ）とする。ｌＸ、ｌＹがノードの順に並んでいる場合には、ｄ（Ｘ，ｌＸ）とｄ（Ｙ，ｌＹ）との大きい方を、フレシェ距離εＸ，Ｙとする。例えば、ノードＸ→ノードＹの順の場合には、線分１＿２上でｌＸの方がｌＹより観測点１寄りにある場合には、ノードの順に並んでいると判断することができる。
【００３２】
計算部１２は、ｌＸ、ｌＹがノードの順に並んでいない場合には、図１０の左図に示すように、２つのノード間の垂直二等分線と線分との交点とノードＸまたはＹとの距離εＸ，Ｙ＿１を求める。また、計算部１２は、図１０の中央図に示すように、ｌＸとノードＸ及びＹの各々との距離の大きい方の距離εＸ，Ｙ＿２を求める。また、計算部１２は、図１０の右図に示すように、ｌＹとノードＸ及びＹの各々との距離の大きい方の距離εＸ，Ｙ＿３を求める。そして、計算部１２は、距離εＸ，Ｙ＿１、距離εＸ，Ｙ＿２、及び距離εＸ，Ｙ＿３のうち、最小のものをフレシェ距離εＸ，Ｙとする。
【００３３】
なお、距離εＸ，Ｙ＿１、距離εＸ，Ｙ＿２、及び距離εＸ，Ｙ＿３の全てを計算して比較する場合に限らず、以下のように、場合分けによりフレシェ距離εＸ，Ｙを計算してもよい。まず、ｄ（Ｘ，ｌＸ）及びｄ（Ｙ，ｌＹ）を計算する。そして、ｄ（Ｘ，ｌＸ）≧ｄ（Ｙ，ｌＹ）の場合には、ｄ（Ｘ，ｌＸ）をフレシェ距離εＸ，Ｙとする。ｄ（Ｘ，ｌＸ）＜ｄ（Ｙ，ｌＹ）の場合には、ｄ（Ｙ，ｌＹ）をフレシェ距離εＸ，Ｙとする。それ以外の場合には、距離εＸ，Ｙ＿１をフレシェ距離εＸ，Ｙとする。
【００３４】
また、計算部１２は、抽出済みのパスに含まれるノードに隣接するノードを順次探索しながらパスを更新する場合には、図１１に示すように、新たに探索されたノードの組についてのフレシェ距離εＸ，Ｙを計算する。そして、計算部１２は、更新以前に計算済みのフレシェ距離εＸ，Ｙの最大値（図１１の各マトリクスの太線枠内）と新たに計算した各フレシェ距離εＸ，Ｙとを比較して、フレシェ距離εＸ，Ｙの最大値を、軌跡と経路グラフとの類似度を表すフレシェ距離ε０とする。
【００３５】
抽出部１３は、軌跡に含まれる各線分について計算部１２で計算された類似度が最大となる、すなわち、フレシェ距離ε０が最小となるように、軌跡に対応するパスを抽出する。抽出部１３は、抽出したパスに含まれる各ノードの座標及びリンク情報を、正規化済軌跡データとして出力する。
【００３６】
経路情報処理装置１０は、例えば図１２に示すコンピュータ４０で実現することができる。コンピュータ４０はＣＰＵ４１、一時記憶領域としてのメモリ４２、及び不揮発性の記憶装置４３を備える。また、コンピュータ４０は、入出力装置４８が接続される入出力インターフェース（Ｉ／Ｆ）４４を備える。また、コンピュータ４０は、記録媒体４９に対するデータの読み込み及び書き込みを制御するｒｅａｄ／ｗｒｉｔｅ（Ｒ／Ｗ）部４５、及びインターネット等のネットワークに接続されるネットワークＩ／Ｆ４６を備える。ＣＰＵ４１、メモリ４２、記憶装置４３、入出力Ｉ／Ｆ４４、Ｒ／Ｗ部４５、及びネットワークＩ／Ｆ４６は、バス４７を介して互いに接続される。
【００３７】
記憶装置４３はＨＤＤ（Hard Disk Drive）、ＳＳＤ（solid state drive）、フラッシュメモリ等によって実現できる。記憶媒体としての記憶装置４３には、コンピュータ４０を経路情報処理装置１０として機能させるための経路情報処理プログラム５０が記憶される。
【００３８】
ＣＰＵ４１は、経路情報処理プログラム５０を記憶装置４３から読み出してメモリ４２に展開し、経路情報処理プログラム５０が有するプロセスを順次実行する。経路情報処理プログラム５０は、取得プロセス５１と、計算プロセス５２と、抽出プロセス５３とを有する。
【００３９】
ＣＰＵ４１は、取得プロセス５１を実行することで、図１に示す取得部１１として動作する。また、ＣＰＵ４１は、計算プロセス５２を実行することで、図１に示す計算部１２として動作する。また、ＣＰＵ４１は、抽出プロセス５３を実行することで、図１に示す抽出部１３として動作する。これにより、経路情報処理プログラム５０を実行したコンピュータ４０が、経路情報処理装置１０として機能することになる。
【００４０】
なお、経路情報処理装置１０は、例えば半導体集積回路、より詳しくはＡＳＩＣ（Application Specific Integrated Circuit）等で実現することも可能である。
【００４１】
次に、本実施形態に係る経路情報処理システム２０の作用について説明する。軌跡データ生成装置２２が、複数のセンサ２６の各々で観測された観測データを、ネットワーク２８を介して取得し、観測データから軌跡データを生成して、軌跡データ記憶部２４に記憶する。また、経路グラフ記憶部２５には、経路グラフが予め記憶されている。この状態で、経路情報処理装置１０は、図１３に示す経路情報処理ルーチンを実行する。なお、経路情報処理装置１０において実行される経路情報処理ルーチンは、本発明の経路情報処理方法の一例である。
【００４２】
図１３に示す経路情報処理のステップＳ１０で、取得部１１が、経路グラフ記憶部２５から経路グラフを取得し、軌跡データ記憶部２４から正規化対象の軌跡データを取得する。ここでは、図１４に示すような経路グラフ及び軌跡データを取得したものとする。
【００４３】
次に、ステップＳ１１で、抽出部１３が、軌跡の始点（図１４の例では、観測点１）から距離ε以内の全てのノードを抽出し、ノード集合｛Ｖ｝とする。距離εは、観測点間の線分と対応するノードを判定するための距離であり、ここでは、ε＝５０とする。従って、ここでは、｛Ｖ｝＝｛Ａ，Ｃ｝となる。
【００４４】
次に、ステップＳ１２で、抽出部１３が、ノード集合｛Ｖ｝から１つのノードＶを選択する。ここでは、まず、ノードＡを選択するものとする。
【００４５】
次に、ステップＳ１３で、抽出部１３が、処理対象データ（ｄ，−ｉ，Ｖ，Ｖ’，Ｓ，ｐａｔｈ）を設定する。ｄは、 探索済みの線分とパスとのフレシェ距離ε-０である。ｉは、観測点間の線分を識別するための番号であり、ノードＶに対応する線分をどこまで探索したかを示す番号である。なお、ｉは、図１５に示すように、軌跡の始点の前と終点の後に仮想の線分を設定し、始点の前の線分から順に、ｉ＝０，１，２，・・・とする。Ｖは、探索済みのノード、Ｖ’は、ノードＶに隣接するノードであり、探索中のノードを表す。Ｓは、ｉ番目の線分に対応するノードの配列（順番を考慮）である。ｐａｔｈは、探索済みのパスである。本ステップは、探索の開始時であるため、初期値として、ｄ＝０、ｉ＝０、Ｖ’＝Ｖ、Ｓ＝［  ］（空）、ｐａｔｈ＝［  ］とする。
【００４６】
次に、ステップＳ１４で、計算部１２が、図１６に詳細を示す距離計算処理を実行する。ステップＳ１４で実行される距離計算処理を、後述するステップＳ２２で実行される距離計算処理と区別するため、「初期の距離計算処理」という。また、ステップＳ２２で実行される距離計算処理は、「２段目の距離計算処理」という。
【００４７】
図１７に、現在の設定で実行される初期の距離計算処理の様子を示す。図１７の＜処理対象のデータ＞は、上記ステップＳ１３で設定した（ｄ，−ｉ，Ｖ，Ｖ’，Ｓ，ｐａｔｈ）である。
【００４８】
図１６のステップＳ３１で、計算部１２が、ノードＶ’に対応する線分として探索中の線分の番号を示す変数ｊに、ｉと１との大きい方を設定する。ここでは、ｉ＝０であるため、ｊ＝１である。また、計算部１２が、ｊ番目の線分に対応するノードの配列を示すＳ’にＳ＋［Ｖ’］を設定する。ここでは、Ｓ’＝［Ａ］である。また、計算部１２が、探索中のノードが新たにパスに追加された場合のパスを示すｐａｔｈ’にｐａｔｈ＋［Ｖ’］を設定する。ここでは、ｐａｔｈ’＝［Ａ］である。また、計算部１２が、観測点ｊとリンクＶ＿Ｖ’との距離ｄ１の初期値に０を設定する。本ステップで設定される値は、図１７の＜ｄ’＞の「ｊ」、「Ｓ’」、「ｐａｔｈ’」、及び「ｄ１」の各項目である。
【００４９】
次に、ステップＳ３２で、計算部１２が、ｉ＋１≦ｊ’≦ｊとなる各ｊ’について、観測点ｊ’及び観測点ｊの各々と、リンクＶ＿Ｖ’との距離の最大値ｄ１’を計算する。距離の計算は、図１７の＜ｄ１’＞のマトリクスを用い、上述したフレシェ距離εＸ，Ｙの計算の手順で計算する。ここでは、ｊ’＝１であるため、観測点１とリンクＡ＿Ａ（＝ノードＡ）との距離１０．０がｄ１’となる。そして、計算部１２が、ｄ１’とｄ１との最大値をｄ１とする。上記ステップＳ３１でｄ１＝０と設定しているため、ここでは、ｄ１＝１０．０となる（図１７上図参照）。なお、ｊ’をｉ＋１以上としていることで、新たに探索する線分の観測点の組に対してだけ距離の計算を行うことになる。本ステップで計算したｄ１は、図１７の＜ｄ’＞の「ｄ１」の項目に相当する。
【００５０】
次に、ステップＳ３３で、計算部１２が、上記ステップＳ３２で計算したｄ１がε以下か否かを判定する。ｄ１がε以下の場合には、探索中のノードはｊ番目の線分に対応するノードであると判定し、処理はステップＳ３４へ移行する。ｄ１がεより大きい場合には、探索中のノードはｊ番目の線分に対応するノードではないと判定し、処理は図１３の経路情報処理に戻る。ここでは、ｄ１＝１０．０≦ε＝５０であるため、肯定判定されて、ステップＳ３４へ移行する。
【００５１】
ステップＳ３４では、計算部１２が、Ｓ’に含まれる各ノードＶ”について、ノードＶ”及びノードＶ’の各々と、ｊ番目の線分（線分ｊ＿ｊ＋１）との距離ｄ２’の最大値ｄ２を計算する（図１７上図参照）。距離の計算は、図１７の＜ｄ２’＞のマトリクスを用い、上述したフレシェ距離εＸ，Ｙの計算の手順で計算する。ここでは、ノードＶ”＝ノードＶ’＝ノードＡであるため、線分１＿２とリンクＡ＿Ａ（＝ノードＡ）との距離１０．０がｄ２となる。そして、計算部１２が、ｄ、ｄ１、及びｄ２の最大値をｄ’とする。ここでは、ｄ’＝１０．０となる。本ステップで計算したｄ２及びｄ’は、図１７の＜ｄ’＞の「ｄ２」及び「ｄ’」の項目に相当する。
【００５２】
次に、ステップＳ３５で、計算部１２が、上記ステップＳ３４で計算したｄ’がε以下か否かを判定する。ｄ’がε以下の場合には、探索中のノードを新たにパスに追加する候補であると判定し、処理はステップＳ３６へ移行する。ここでは、ｄ’＝１０．０≦ε＝５０であるため、肯定判定されて、ステップＳ３６へ移行する。
【００５３】
ステップＳ３６では、（Ｖ’，ｊ）の組み合わせがリストＬに含まれるか否かを判定する。リストＬは、ノードＶについてｉ番目の線分まで探索した際のフレシェ距離ｄを記録したリストであり、図１７の＜リストＬ＞に示すように、「Ｖ」、「ｉ」、及び「ｄ」の項目を含む。（Ｖ’，ｊ）の組み合わせと一致する（Ｖ，ｉ）がリストＬに含まれる場合には、処理はステップＳ３７へ移行し、含まれない場合には、処理はステップＳ３８へ移行する。初期段階では、リストＬは空であるため、ここでは、否定判定されて、ステップＳ３８へ移行する。
【００５４】
ステップＳ３８では、計算部１２が、（Ｖ’，ｊ，ｄ’）を、リストＬの「Ｖ」、「ｉ」、及び「ｄ」の各項目に記録する。また、計算部１２が、探索済のノード情報を示すリストＱに、新たに探索されたノードの情報を記録する。具体的には、リストＱは、図１７の＜リストＱ＞に示すように、「ｄ」、「−ｉ」、「Ｖ」、「Ｓ」、及び「ｐａｔｈ」の項目を含む。計算部１２は、（ｄ’，−ｊ，Ｖ’，Ｓ’，ｐａｔｈ’）をリストＱの各項目に対応付けて記録する。
【００５５】
次に、ステップＳ３９で、抽出部１３が、ｊを１インクリメントし、Ｓ’に［Ｖ’］を設定する。Ｓ’に［Ｖ’］を設定することで、上記ステップＳ３４で、ノードＶ’に対してだけ距離の計算を行うことになる。
【００５６】
次に、ステップＳ４０で、ｊが軌跡の観測点数を示すｐ以下か否かを判定する。ｊがｐ以下の場合には、処理はステップＳ３２に戻り、ｊがｐより大きい場合には、処理は図１３の経路情報処理に戻る。ここでは、ｊ＝１≦ｐ＝４であるため、肯定判定されて、ステップＳ３２に戻る。
【００５７】
図１８に、現在の設定で実行されるステップＳ３２以降の処理の様子を示す。この段階では、＜処理対象のデータ＞は、図１７の場合と同じであり、＜ｄ’＞は、「ｄ」に０、「ｄ１」に１０．０、「ｊ」に２、「Ｓ’」に［Ａ］、「ｐａｔｈ’」に「Ａ」が設定されている。上記と同様の処理により、ステップＳ３２でｄ１＝４１．２が得られ（図１８上図参照）、ステップＳ３３で肯定判定されて、ステップＳ３４でｄ２＝４０．０が得られ（図１８上図参照）、さらにｄ’＝４１．２が得られる。そして、ステップＳ３５で肯定判定され、ステップＳ３６で否定判定され、ステップＳ３８で、図１８に示すように、リストＬ及びリストＱにデータが追加される。そして、ステップＳ３９及びＳ４０を経て、再びステップＳ３２に戻る。
【００５８】
図１９に、現在の設定で実行されるステップＳ３２以降の処理の様子を示す。この段階では、＜処理対象のデータ＞は、図１７の場合と同じであり、＜ｄ’＞は、「ｄ」に０、「ｄ１」に４１．２、「ｊ」に３、「Ｓ’」に［Ａ］、「ｐａｔｈ’」に「Ａ」が設定されている。上記と同様の処理により、ステップＳ３２でｄ１＝９８．５が得られる（図１９上図参照）。これにより、ステップＳ３３で否定判定されて、図１３の経路情報処理に戻る。
【００５９】
次に、図１３のステップＳ１５で、抽出部１３が、上記ステップＳ１１で抽出したノード集合｛Ｖ｝に含まれる全てのノードを選択したか否かを判定する。未選択のノードが存在する場合には、処理はステップＳ１２に戻り、全てのノードを選択済みの場合には、処理はステップＳ１６へ移行する。ここでは、ノードＣが未選択のため、処理はステップＳ１２に戻る。そして、抽出部１３が、ノードＣを選択し、ステップＳ１３で、処理対象データ（ｄ，−ｉ，Ｖ，Ｖ’，Ｓ，ｐａｔｈ）に（０，０，Ｃ，Ｃ，[  ]，[  ]）を設定し、上記と同様に、初期の距離計算処理を実行する。
【００６０】
ノードＣについての初期の距離計算処理が終了すると、上記ステップＳ１５で肯定判定されて、処理はステップＳ１６へ移行する。図２０に、初期の距離計算処理後のリストＱ及びリストＬを示す。
【００６１】
ステップＳ１６では、抽出部１３が、図２１に示すように、リストＱのデータをリストＰへ移し、リストＱを空にする。次に、ステップＳ１７で、抽出部１３が、リストＰが空か否かを判定し、空の場合には、処理はステップＳ３５へ移行し、空ではない場合には、処理はステップＳ１８へ移行する。ここでは、リストＰは空ではないため、処理はステップＳ１８へ移行する。
【００６２】
ステップＳ１８では、抽出部１３が、リストＰを、「ｄ」及び「−ｉ」の項目で昇順にソートする。そして、抽出部１３が、リストＰの先頭の（ｄ，−ｉ，Ｖ，Ｓ，ｐａｔｈ）を処理対象のデータとして取り出す。「ｄ」及び「−ｉ」で昇順にソートしているため、先頭のデータは、フレシェ距離が最小、すなわち探索済の線分とパスとの類似度が最大のデータとなる。ここでは、（ｄ，−ｉ，Ｖ，Ｓ，ｐａｔｈ）＝（１０．０，−１，Ａ，［Ａ］，［Ａ］）が取り出される。このデータは、１番目の線分（線分１＿２）まで探索済であり、探索済ノードはＡ、１番目の線分に対応するノードは［Ａ］、探索済のパスは［Ａ］であり、このパスと軌跡の１番目の線分とのフレシェ距離が１０．０であることを表す。
【００６３】
次に、ステップＳ１９で、抽出部１３が、上記ステップＳ１８で取り出した処理対象のデータの「ｉ」がｐと一致するか否かを判定する。ｉ＝ｐの場合には、処理はステップＳ２４へ移行し、ｉ≠ｐの場合には、処理はステップＳ２０へ移行する。ここでは、ｉ＝１≠ｐ＝４であるため、否定判定された処理はステップＳ２０へ移行する。
【００６４】
ステップＳ２０では、抽出部１３が、処理対象のデータの「Ｖ」の項目のノードＶに隣接する全てのノードを抽出し、ノード集合｛Ｖ’｝とする。ここでは、ノードＶはノードＡであるため、｛Ｖ’｝＝｛Ｂ，Ｃ｝となる。
【００６５】
次に、ステップＳ２１で、抽出部１３が、ノード集合｛Ｖ’｝から１つのノードＶ’を選択する。ここでは、まず、ノードＢを選択するものとする。
【００６６】
次に、ステップＳ２２で、抽出部１３が、上述の図１６に示す距離計算処理を、２段目の距離計算処理として実行する。
【００６７】
図２２に、現在の設定で実行される２段目の距離計算処理の様子を示す。この段階では、＜処理対象のデータ＞には、上記ステップＳ１８で抜き出した処理対象のデータ、及び上記ステップＳ２１で選択したノードＶ’が設定される。そして、上記と同様の処理により、ステップＳ３１で、＜ｄ’＞の「ｊ」に１、「Ｓ’」に［ＡＢ］、「ｐａｔｈ’」に［ＡＢ］、「ｄ１」に０が設定される。また、ステップＳ３２では、ｉ＋１≦ｊ’≦ｊとなるｊ’が存在しないため、ｄ１＝０が得られる（図２２の＜ｄ１’＞参照）。そして、ステップＳ３３で肯定判定されて、ステップＳ３４でｄ２＝１１０が得られ（図２２上図参照）、さらにｄ’＝１１０が得られ、ステップＳ３５で否定判定され、ステップＳ３９及びＳ４０を経て、再びステップＳ３２に戻る。
【００６８】
図２３に、現在の設定で実行されるステップＳ３２以降の処理の様子を示す。この段階では、＜処理対象のデータ＞は、図２２と同じであり、＜ｄ’＞は、「ｄ」に１０．０、「ｄ１」に０、「ｊ」に２、「Ｓ’」に［Ｂ］、「ｐａｔｈ’」に「ＡＢ」が設定されている。上記と同様の処理により、ステップＳ３２でｄ１＝４１．２が得られ（図２３上図参照）、ステップＳ３３で肯定判定されて、ステップＳ３４でｄ２＝４１．２が得られ（図２３上図参照）、さらにｄ’＝４１．２が得られる。そして、ステップＳ３５で肯定判定され、ステップＳ３６で否定判定され、ステップＳ３８で、図２３に示すように、リストＬ及びリストＱの各項目が追加される。そして、ステップＳ３９及びＳ４０を経て、再びステップＳ３２に戻る。
【００６９】
ｊ＝３についても上記と同様にステップＳ３２以降の処理を実行することで、ステップＳ３８で、リストＬに（Ｖ，ｉ，ｄ）＝（Ｂ，３，４１．２）が追加され、リストＱに（ｄ，−ｉ，Ｖ，Ｓ，ｐａｔｈ）＝（４１．２，−３，Ｂ，［Ｂ］，［ＡＢ］）が追加される。そして、ステップＳ３９及びＳ４０を経て、再びステップＳ３２に戻る。
【００７０】
ｊ＝４については、ステップＳ３２でｄ１＝８０が得られ、ステップＳ３３で否定判定されて、図１３の経路情報処理に戻り、ステップＳ２３で否定判定されて、ステップＳ２１に戻る。ステップＳ２１で、抽出部１３が、ノードＶ’として、ノードＣを選択し、ステップＳ２２で、２段目の距離計算処理を実行する。
【００７１】
図２４に、現在の設定で実行される２段目の距離計算処理の様子を示す。この段階では、＜処理対象のデータ＞には、上記ステップＳ１８で抜き出した処理対象のデータ（ｄ，−ｉ，Ｖ，Ｓ，ｐａｔｈ）＝（１０．０，−１，Ａ，［Ａ］，［Ａ］）、及び上記ステップＳ２１で選択したノードＣがノードＶ’に設定される。そして、上記と同様の処理により、ステップＳ３１で、＜ｄ’＞の「ｊ」に１、「Ｓ’」に［ＡＣ］、「ｐａｔｈ’」に［ＡＣ］、「ｄ１」に０が設定される。また、ステップＳ３２では、ｉ＋１≦ｊ’≦ｊとなるｊ’が存在しないため、ｄ１＝０が得られる（図２４の＜ｄ１’＞参照）。そして、ステップＳ３３で肯定判定されて、ステップＳ３４でｄ２＝１０．０が得られ（図２４上図参照）、さらにｄ’＝１０．０が得られ、ステップＳ３５で肯定判定され、ステップＳ３６へ移行する。
【００７２】
ステップＳ３６では、（Ｖ’，ｊ）＝（Ｃ，１）はリストＬに含まれるため、肯定判定されて、ステップＳ３７へ移行する。ステップＳ３７では、計算部１２が、上記ステップＳ３４で計算したｄ’が、リストＬに含まれる（Ｖ’，ｊ）の組み合わせと一致する（Ｖ，ｉ）に対応する「ｄ」より小さいか否かを判定する。ここでは、ｄ’＜リストＬのｄであるため、処理はステップＳ３８へ移行する。この場合、ステップＳ３８では、図２４に示すように、計算部１２が、リストＬにおいて、（Ｖ’，ｊ）と一致する（Ｖ，ｉ）に対応するｄをｄ’で更新する。また、計算部１２は、リストＰにおいて、（Ｖ’，ｊ）と一致する（Ｖ，ｉ）を有するデータを削除する。さらに、計算部１２は、リストＱに（ｄ’，−ｊ，Ｖ’，Ｓ’，ｐａｔｈ’）を追加する。そして、ステップＳ３９及びＳ４０を経て、再びステップＳ３２に戻る。
【００７３】
ｊ＝２についても上記と同様にステップＳ３２以降の処理を実行することで、ステップＳ３４でｄ’＝３１．６が得られ、ステップＳ３５で肯定判定され、ステップＳ３６で肯定判定され、ステップＳ３７へ移行する。ここでは、（Ｖ’，ｊ）＝（Ｃ，２）であり、リストＬの（Ｃ，２）に対応するｄは３１．６である。従って、ｄ’＜リストＬのｄではないため、処理はステップＳ３８をスキップしてステップＳ３９へ移行する。そして、ステップＳ３９及びＳ４０を経て、再びステップＳ３２に戻る。
【００７４】
ｊ＝３については、ステップＳ３２でｄ１＝９４．９が得られ、ステップＳ３３で否定判定されて、図１３の経路情報処理に戻り、ステップＳ２３で肯定判定されて、ステップＳ１６に戻る。
【００７５】
図２５に、２段目の距離計算処理の１回目のループ（以下、ｎ回目のループを「ループｎ」という）後のリストＱ及びリストＬを示す。なお、ここでは、ステップＳ１６〜Ｓ２３までを、２段目の距離計算処理の１回のループとしている。
【００７６】
２段目の距離計算処理のループ２では、ステップＳ１６〜Ｓ１８で、抽出部１３が、図２６に示すように、リストＱのデータをリストＰへ移し、リストＱを空にする。そして、抽出部１３が、リストＰを「ｄ」及び「−ｉ」でソートして、先頭の（ｄ，−ｉ，Ｖ，Ｓ，ｐａｔｈ）＝（１０．０，−１，Ｃ，［ＡＣ］，［ＡＣ］）を処理対象のデータとして取り出す。
【００７７】
２段目の距離計算処理（ループ２）で、上記と同様の処理により、図２７に示すようなリストＱ及びリストＬが得られる。同様に、２段目の距離計算処理（ループ３）の処理対象のデータの抜き出しの様子を図２８に、処理後のリストＱ及びリストＬを図２９に示す。以下、同様に、ループ４について、図３０に、ループ５について、図３１及び図３２に、ループ６について、図３３及び図３４に、ループ７について、図３５及び図３６に、ループ８について、図３７に、ループ９について、図３８及び図３９に示す。なお、ループ４及びループ８については、処理後のリストＱ及びリストＬは、前のループの処理後のリストＱ及びリストＬから変化がないため、図示を省略している。
【００７８】
図４０に示すように、２段目の距離計算処理（ループ１０）のために抜き出された処理対象のデータでは、ｉ＝ｐ（＝４）となっているため、ステップＳ１９で肯定判定されて、処理はステップＳ２４へ移行する。
【００７９】
ステップＳ２４では、抽出部１３が、抜き出した処理対象のデータの「ｐａｔｈ」（ここでは、［ＡＣＩＪ］）を、正規化した軌跡として抽出する。すなわち、図１４に示す軌跡（観測点１，２，３，４）は、経路グラフにおけるノードＡ→Ｃ→Ｉ→Ｊのパスにマッチングされたことを表す。抽出部１３は、抽出したパスを、例えば図４１に示すような正規化済軌跡データとして出力し、経路情報処理を終了する。
【００８０】
一方、ステップＳ１９で肯定判定される前にステップＳ１７でリストＰが空になったと判定された場合には、軌跡に対応するパスが経路グラフに存在しないことを表している。そこで、処理はステップＳ２５へ移行し、抽出部１３が、エラーを出力して、経路情報処理を終了する。
【００８１】
以上説明したように、本実施形態に係る経路情報処理装置によれば、観測点間の線分に対応付けられたノードの２つずつの各組み合わせと線分との距離の最大値であるフレシェ距離を、軌跡と経路グラフ上のパスとの類似度として計算する。このため、軌跡と経路グラフ上のパスとの類似度を効率良く求めることができる。また、ノードと線分との距離も、ノードの順番を考慮したフレシェ距離で計算することで、軌跡に含まれるＵターンやループなどのように移動の方向が変わる部分についても、精度良く反映された類似度を計算することができる。
【００８２】
また、隣接するノードを探索しながら、軌跡とマッチするパスを更新する際には、新たに探索するノードについてのみ、２つずつの組の各ノードと線分との距離を計算し、更新前に計算済みのフレシェ距離と比較すればよい。このため、軌跡と経路グラフ上のパスとのマッチングの計算コストも抑えることができる。
【００８３】
なお、上記実施形態では、経路情報処理プログラム５０が記憶装置４３に予め記憶（インストール）されている態様を説明したが、これに限定されない。本発明に係る経路情報処理プログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の記録媒体に記録された形態で提供することも可能である。
【００８４】
以上の各実施形態に関し、更に以下の付記を開示する。
【００８５】
（付記１）
複数のノードをリンクで連結したパスを複数含む経路グラフの前記ノードのうち、複数の観測点の時系列で表される軌跡に含まれる各観測点間の線分に対応するノードの２つずつの各組み合わせと前記線分とのフレシェ距離の最大値を計算する計算部と、
前記軌跡に含まれる各線分について前記計算部で計算された前記最大値が最小となる、前記軌跡に対応するパスを抽出する抽出部と、
を含む経路情報処理装置。
【００８６】
（付記２）
前記計算部は、前記線分及び該線分に対応するノードを探索して、前記軌跡に対応するパスを更新しながら抽出する場合には、新たに探索されたノードの２つずつの各組み合わせと前記線分とのフレシェ距離、及び既に計算されているフレシェ距離の最大値を計算する付記１記載の経路情報処理装置。
【００８７】
（付記３）
前記計算部は、前記ノードの２つずつの各組み合わせと前記線分とのフレシェ距離を、各ノードから最短距離となる線分上の点の各々の順番と、前記各ノードの順番とが同じ場合には、前記最短距離のうち大きい方とし、前記各ノードから最短距離となる線分上の点の順番と、前記各ノードの順番とが逆の場合には、２つのノードの垂直二等分線と前記線分との交点といずれかのノードとの距離、及びいずれか一方のノードから最短距離となる線分上の点と他方のノードとの距離と前記いずれか一方のノードからの最短距離との大きい方のうち最小の距離とする付記１または付記２記載の経路情報処理装置。
【００８８】
（付記４）
前記線分に対応するノードを、前記線分から所定距離以内に存在するノードとする付記１〜付記３のいずれか１項記載の経路情報処理装置。
【００８９】
（付記５）
コンピュータに、
複数のノードをリンクで連結したパスを複数含む経路グラフの前記ノードのうち、複数の観測点の時系列で表される軌跡に含まれる各観測点間の線分に対応するノードの２つずつの各組み合わせと前記線分とのフレシェ距離の最大値を計算し、
前記軌跡に含まれる各線分について計算された前記最大値が最小となる、前記軌跡に対応するパスを抽出する
ことを含む処理を実行させる経路情報処理方法。
【００９０】
（付記６）
前記線分及び該線分に対応するノードを探索して、前記軌跡に対応するパスを更新しながら抽出する場合には、新たに探索されたノードの２つずつの各組み合わせと前記線分とのフレシェ距離、及び既に計算されているフレシェ距離の最大値を計算する付記５記載の経路情報処理方法。
【００９１】
（付記７）
前記ノードの２つずつの各組み合わせと前記線分とのフレシェ距離を、各ノードから最短距離となる線分上の点の各々の順番と、前記各ノードの順番とが同じ場合には、前記最短距離のうち大きい方とし、前記各ノードから最短距離となる線分上の点の順番と、前記各ノードの順番とが逆の場合には、２つのノードの垂直二等分線と前記線分との交点といずれかのノードとの距離、及びいずれか一方のノードから最短距離となる線分上の点と他方のノードとの距離と前記いずれか一方のノードからの最短距離との大きい方のうち最小の距離とする付記５または付記６記載の経路情報処理方法。
【００９２】
（付記８）
前記線分に対応するノードを、前記線分から所定距離以内に存在するノードとする付記５〜付記７のいずれか１項記載の経路情報処理方法。
【００９３】
（付記９）
コンピュータに、
複数のノードをリンクで連結したパスを複数含む経路グラフの前記ノードのうち、複数の観測点の時系列で表される軌跡に含まれる各観測点間の線分に対応するノードの２つずつの各組み合わせと前記線分とのフレシェ距離の最大値を計算し、
前記軌跡に含まれる各線分について計算された前記最大値が最小となる、前記軌跡に対応するパスを抽出する
ことを含む処理を実行させるための経路情報処理プログラム。
【００９４】
（付記１０）
前記線分及び該線分に対応するノードを探索して、前記軌跡に対応するパスを更新しながら抽出する場合には、新たに探索されたノードの２つずつの各組み合わせと前記線分とのフレシェ距離、及び既に計算されているフレシェ距離の最大値を計算する付記９記載の経路情報処理プログラム。
【００９５】
（付記１１）
前記ノードの２つずつの各組み合わせと前記線分とのフレシェ距離を、各ノードから最短距離となる線分上の点の各々の順番と、前記各ノードの順番とが同じ場合には、前記最短距離のうち大きい方とし、前記各ノードから最短距離となる線分上の点の順番と、前記各ノードの順番とが逆の場合には、２つのノードの垂直二等分線と前記線分との交点といずれかのノードとの距離、及びいずれか一方のノードから最短距離となる線分上の点と他方のノードとの距離と前記いずれか一方のノードからの最短距離との大きい方のうち最小の距離とする付記９または付記１０記載の経路情報処理プログラム。
【００９６】
（付記１２）
前記線分に対応するノードを、前記線分から所定距離以内に存在するノードとする付記９〜付記１１のいずれか１項記載の経路情報処理プログラム。
【００９７】
（付記１３）
コンピュータに、
複数のノードをリンクで連結したパスを複数含む経路グラフの前記ノードのうち、複数の観測点の時系列で表される軌跡に含まれる各観測点間の線分に対応するノードの２つずつの各組み合わせと前記線分とのフレシェ距離の最大値を計算し、
前記軌跡に含まれる各線分について計算された前記最大値が最小となる、前記軌跡に対応するパスを抽出する
ことを含む処理を実行させるための経路情報処理プログラムを記憶した記憶媒体。
【符号の説明】
【００９８】
１０   経路情報処理装置
１１   取得部
１２   計算部
１３   抽出部
２０   経路情報処理システム
２２   軌跡データ生成装置
２４   軌跡データ記憶部
２５   経路グラフ記憶部
２６   センサ
２８   ネットワーク
４０   コンピュータ
４１   ＣＰＵ
４２   メモリ
４３   記憶装置
５０   経路情報処理プログラム
【図１】
0006350251.tif 000002
【図２】
0006350251.tif 000003
【図３】
0006350251.tif 000004
【図４】
0006350251.tif 000005
【図５】
0006350251.tif 000006
【図６】
0006350251.tif 000007
【図７】
0006350251.tif 000008
【図８】
0006350251.tif 000009
【図９】
0006350251.tif 000010
【図１０】
0006350251.tif 000011
【図１１】
0006350251.tif 000012
【図１２】
0006350251.tif 000013
【図１３】
0006350251.tif 000014
【図１４】
0006350251.tif 000015
【図１５】
0006350251.tif 000016
【図１６】
0006350251.tif 000017
【図１７】
0006350251.tif 000018
【図１８】
0006350251.tif 000019
【図１９】
0006350251.tif 000020
【図２０】
0006350251.tif 000021
【図２１】
0006350251.tif 000022
【図２２】
0006350251.tif 000023
【図２３】
0006350251.tif 000024
【図２４】
0006350251.tif 000025
【図２５】
0006350251.tif 000026
【図２６】
0006350251.tif 000027
【図２７】
0006350251.tif 000028
【図２８】
0006350251.tif 000029
【図２９】
0006350251.tif 000030
【図３０】
0006350251.tif 000031
【図３１】
0006350251.tif 000032
【図３２】
0006350251.tif 000033
【図３３】
0006350251.tif 000034
【図３４】
0006350251.tif 000035
【図３５】
0006350251.tif 000036
【図３６】
0006350251.tif 000037
【図３７】
0006350251.tif 000038
【図３８】
0006350251.tif 000039
【図３９】
0006350251.tif 000040
【図４０】
0006350251.tif 000041
【図４１】
0006350251.tif 000042