(57)【要約】【課題】経路分析の適切な分析結果を得ることができる経路グラフを作成する。【解決手段】共通化箇所特定部１１は、移動体の位置を示す点の系列で表される複数の軌跡データの各々について、処理対象の軌跡データが示す軌跡から所定距離内に存在する他の軌跡の部分である共通化箇所を特定する。代表経路抽出部１２は、共通化箇所に含まれる測位点を接続した経路から、処理対象の軌跡との距離及び測位点の密集度に基づいて、処理対象の軌跡と対応する代表経路を抽出する。統合部１３は、軌跡毎に抽出した複数の代表経路の各々を、代表経路に対応する軌跡周辺の他の軌跡の密集度が高い代表経路から順に、作成中の仮経路グラフとの距離に基づいて、仮経路グラフに統合して、経路グラフを作成する。【選択図】図３
2015210083.tif 000002
【特許請求の範囲】
【請求項１】
複数の経路のうちの特定の経路を統合させる対象の統合先経路を前記複数の経路のうちの他の経路の中から抽出する際に、経路の分布密度の高さに応じて抽出可能性を高める制御を行う、
処理をコンピュータに実行させることを特徴とする統合先経路抽出方法。
【請求項２】
前記特定の経路から所定距離内に第１の経路と第２の経路とが存在する場合に、前記第２の経路の周辺よりも、前記第１の経路の周辺の方がより高い経路の密集度を示す場合に、該第１の経路を前記が統合先経路として抽出する、
処理をコンピュータに実行させることを特徴とする請求項１記載の統合先経路抽出方法。
【請求項３】
前記経路の分布密度は、経路内のノードの分布密度に基づいて算出される、ことを特徴とする請求項１又は２記載の統合先経路抽出方法。
【請求項４】
複数の経路のうちの特定の経路を統合させる対象の統合先経路を前記複数の経路のうちの他の経路の中から抽出する際に、経路の分布密度の高さに応じて抽出可能性を高める制御を行う抽出部
を含む統合先経路抽出装置。
【請求項５】
複数の経路のうちの特定の経路を統合させる対象の統合先経路を前記複数の経路のうちの他の経路の中から抽出する際に、経路の分布密度の高さに応じて抽出可能性を高める制御を行う、
処理をコンピュータに実行させるための統合先経路抽出プログラム。
【請求項６】
コンピュータに、
移動体の位置を示す点の系列で表される複数の軌跡データの各々について、処理対象の軌跡データが示す軌跡から所定距離内に存在する他の軌跡の点を接続した経路から、前記処理対象の軌跡との距離及び点の密集度を基に代表経路を抽出し、
軌跡毎に抽出した複数の代表経路に基づき、経路グラフを作成する
ことを含む処理を実行させる経路グラフ作成方法。
【請求項７】
前記経路グラフを作成する際、軌跡毎に抽出した複数の代表経路の各々を、前記代表経路に対応する軌跡周辺の他の軌跡の密集度が高い代表経路から順に、作成中の仮経路グラフとの距離に基づいて該仮経路グラフに統合して、経路グラフを作成する請求項６記載の経路グラフ作成方法。
【請求項８】
前記代表経路を抽出する際に、前記所定距離内に存在する他の軌跡の点の各々をノードとする平面グラフを作成し、前記平面グラフ上のパスのうち、前記処理対象の軌跡との距離が近いほど、かつ選択するノード周辺のノードの密集度が高いほど高くなるマッチング度が最も高いパスを、前記代表経路として抽出する請求項６または請求項７記載の経路グラフ作成方法。
【請求項９】
前記代表経路に対応する軌跡周辺の他の軌跡の密集度を、各軌跡に設定した点数を軌跡に含まれる点の各々に持ち点として分配し、処理対象の軌跡から前記所定距離内に存在する他の軌跡の点に分配された持ち点を合計した得点で表す請求項６〜請求項８のいずれか１項記載の経路グラフ作成方法。
【請求項１０】
コンピュータに、
移動体の位置を示す点の系列で表される複数の軌跡データの各々が示す軌跡の各々を、複数のノードとノード間を接続する辺とを含むネットワークデータに対応させ、軌跡の各々から所定距離内に存在する前記ネットワークデータ上のパスを経路として抽出し、
抽出した複数の経路に含まれる辺のうち、経路グラフに含まれる辺の組み合わせを、前記複数の軌跡との近似度が高くなるように最適化して求めることにより、経路グラフを作成する
ことを含む処理を実行させる経路グラフ作成方法。
【請求項１１】
前記最適化の際に、抽出された経路は辺の集合であり、各軌跡は抽出された経路のいずれかに対応し、かつ前記経路グラフは軌跡に対応する全ての経路を含むとの制約の下、前記経路グラフに含まれる辺の数を最小化する請求項１０記載の経路グラフ作成方法。
【請求項１２】
前記ネットワークデータを、前記複数の軌跡に含まれる点をノードとする平面グラフとした請求項１０または請求項１１記載の経路グラフ作成方法。
【請求項１３】
移動体の位置を示す点の系列で表される複数の軌跡データの各々について、処理対象の軌跡データが示す軌跡から所定距離内に存在する他の軌跡の点を接続した経路から、前記処理対象の軌跡との距離及び点の密集度を基に代表経路を抽出する抽出部と、
軌跡毎に抽出した複数の代表経路に基づき、経路グラフを作成する作成部と、
を含む経路グラフ作成装置。
【請求項１４】
移動体の位置を示す点の系列で表される複数の軌跡データの各々が示す軌跡の各々を、複数のノードとノード間を接続する辺とを含むネットワークデータに対応させ、軌跡の各々から所定距離内に存在する前記ネットワークデータ上のパスを経路として抽出する抽出部と、
抽出した複数の経路に含まれる辺のうち、経路グラフに含まれる辺の組み合わせを、前記複数の軌跡との近似度が高くなるように最適化して求めることにより、経路グラフを作成する最適化部と、
を含む経路グラフ作成装置。
【請求項１５】
コンピュータに、
移動体の位置を示す点の系列で表される複数の軌跡データの各々について、処理対象の軌跡データが示す軌跡から所定距離内に存在する他の軌跡の点を接続した経路から、前記処理対象の軌跡との距離及び点の密集度を基に代表経路を抽出し、
軌跡毎に抽出した複数の代表経路に基づき、経路グラフを作成する
ことを含む処理を実行させるための経路グラフ作成プログラム。
【請求項１６】
コンピュータに、
移動体の位置を示す点の系列で表される複数の軌跡データの各々が示す軌跡の各々を、複数のノードとノード間を接続する辺とを含むネットワークデータに対応させ、軌跡の各々から所定距離内に存在する前記ネットワークデータ上のパスを経路として抽出し、
抽出した複数の経路に含まれる辺のうち、経路グラフに含まれる辺の組み合わせを、前記複数の軌跡との近似度が高くなるように最適化して求めることにより、経路グラフを作成する
ことを含む処理を実行させるための経路グラフ作成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、統合先経路抽出方法、統合先経路抽出装置、統合先経路抽出プログラム、経路グラフ作成方法、経路グラフ作成装置、及び経路グラフ作成プログラムに関する。
【背景技術】
【０００２】
従来、空間情報分析として、移動体の経路に関する分析を行う技術が存在する。例えば、実際の観測データである複数の軌跡データから、指定された地点を出発地点または到着地点とする経路を検索するＯＤ（Ｏ＝“Origin”：出発地点、Ｄ＝“Destination”：到着地点）検索を行う技術が存在する。また、複数の軌跡データから、所定回数（例えば、１０回）以上出現する出発地点と到着地点との組み合わせ（例えば、（新宿駅−渋谷駅）、（品川駅−池袋駅）等）を示す頻出ＯＤを分析する技術が存在する。また、軌跡データの中から、例えば、品川駅→（山手線外回り）→池袋駅を通過する経路のように、部分経路を検索する技術が存在する。さらに、軌跡データの中に、所定回数（例えば、１０回）以上出現する部分経路を示す頻出部分経路を分析する技術が存在する。このような経路分析において、分析対象となる経路が、道路ネットワークや地図データなどで予め特定されている場合には、経路に軌跡データを対応させることで、適切な分析結果を得ることができる。
【０００３】
ここで、移動体として人を対象とした場合の経路分析を考える。人の移動を表す軌跡データは、例えば、携帯電話やスマートフォン等に内蔵されたＧＰＳ（Global Positioning System）センサにより緯度及び経度（測位点）を定期的に測位した位置データの系列として取得することができる。また、ＷｉＦｉ等を利用して位置データを取得することもできる。人の移動は、道路や電車の路線に沿った移動に限られず、例えば展示会会場等のオープンスペースを自由に移動する場合もある。すなわち、経路が特定されていない空間における軌跡データが取得される場合もある。軌跡データを道路ネットワークや地図データなどの予め特定された経路に対応付けて経路分析を行う手法では、経路が特定されていない空間における軌跡データに対して経路分析を行うことができない。
【０００４】
そこで、分析対象の範囲を所定面積の複数の領域（メッシュ）に分割し、軌跡データに含まれる各位置データが示す測位点をメッシュに対応付ける技術が存在する。この技術では、経路分析におけるＯＤ（出発地点、到着地点）は、ＯＤを示す測位点に対応するメッシュの組み合わせで表現し、経路は、軌跡データが通過するメッシュの系列で表現する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−１２５８８２号公報
【特許文献２】特開２０１３−５４６４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、メッシュを用いた経路分析においては、設定するメッシュの面積の大きさによって、分析結果が変わる場合がある。例えば、メッシュの面積が小さい場合には、略同じ軌跡データであっても、異なる経路として表現される場合がある。一方、メッシュの面積が大きい場合には、異なる経路として取り扱いたい異なる軌跡データであっても、同じ経路として表現される場合がある。このようにメッシュの面積の調整の微妙なずれが分析結果に悪影響を及ぼす場合がある。さらに、メッシュの境界付近では、略同じ場所を表す測位点であっても、一方の測位点は、一方のメッシュと対応付けられ、他方の測位点は、境界を挟んだ他方のメッシュに対応付けられる場合もあり、適切な分析結果が得られない場合がある。
【０００７】
本発明は、一つの側面として、経路分析の適切な分析結果を得ることができる経路グラフを作成することを目的とする。
【課題を解決するための手段】
【０００８】
一つの態様として、経路グラフ作成方法は、移動体の位置を示す点の系列で表される複数の軌跡データの各々について、処理対象の軌跡データが示す軌跡と対応する代表経路を抽出する。代表経路は、処理対象の軌跡データから所定距離内に存在する他の軌跡の測位点を接続した経路から、前記処理対象の軌跡との距離及び測位点の密集度に基づいて抽出する。そして、軌跡毎に抽出した複数の代表経路に基づき、経路グラフを作成する。
【０００９】
また、一つの態様として、経路グラフ作成方法は、移動体の位置を示す点の系列で表される複数の軌跡データの各々が示す軌跡の各々を、複数のノードとノード間を接続する辺とを含むネットワークデータに対応させる。そして、軌跡の各々から所定距離内に存在する前記ネットワークデータ上のパスを経路として抽出する。さらに、抽出した複数の経路に含まれる辺のうち、経路グラフに含まれる辺の組み合わせを、前記複数の軌跡との近似度が高くなるように最適化して求めることにより、経路グラフを作成する。
【発明の効果】
【００１０】
一つの側面として、経路分析の適切な分析結果を得ることができる経路グラフを作成することができる、という効果を有する。
【図面の簡単な説明】
【００１１】
【図１】軌跡を統合して経路グラフを作成する例を説明するための図である。
【図２】第１及び第２実施形態に係る経路グラフ作成装置を含む経路グラフ作成システムの概略構成を示すブロック図である。
【図３】第１実施形態に係る経路グラフ作成装置の機能ブロック図である。
【図４】軌跡の一例を示す図である。
【図５】共通化箇所の特定を説明するための図である。
【図６】共通化箇所の特定を説明するための図である。
【図７】密集度に基づく得点の計算を説明するための図である。
【図８】密集度に基づく得点の計算を説明するための図である。
【図９】平面グラフの作成を説明するための図である。
【図１０】代表経路の抽出を説明するための図である。
【図１１】代表経路の抽出を説明するための図である。
【図１２】代表経路の統合を説明するための図である。
【図１３】代表経路の統合を説明するための図である。
【図１４】第１実施形態に係る経路グラフ作成装置として機能するコンピュータの概略構成を示すブロック図である。
【図１５】第１実施形態における経路グラフ作成処理の一例を示すフローチャートである。
【図１６】第２実施形態に係る経路グラフ作成装置の機能ブロック図である。
【図１７】経路束の抽出を説明するための図である。
【図１８】軌跡の一例を示す図である。
【図１９】最適化による経路グラフの作成を説明するための図である。
【図２０】第２実施形態に係る経路グラフ作成装置として機能するコンピュータの概略構成を示すブロック図である。
【図２１】第２実施形態における経路グラフ作成処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、図面を参照して開示の技術の実施形態の一例を詳細に説明する。
【００１３】
＜第１実施形態＞
第１実施形態では、領域をメッシュに分割したり、道路ネットワークや地図データ等を用いたりすることなく、経路分析に用いられる経路を表す経路グラフを、移動体の移動した軌跡を示す軌跡データから作成する。軌跡データは、測位された移動体の位置（測位点）を示す位置データの系列である。
【００１４】
まず、第１実施形態の詳細を説明する前に、軌跡データから経路グラフを作成する場合に想定される問題点について説明する。
【００１５】
軌跡データから経路グラフを作成する場合、複数の軌跡データが示す軌跡の各々に対する近似度が高い経路の集合を表し、かつ簡潔な経路グラフを作成することが望ましい。そこで、例えば、軌跡間の距離が所定距離以内の軌跡同士を順次統合することにより、経路グラフを作成することが考えられる。
【００１６】
例えば、図１に示す軌跡ｔ１〜ｔ６の各々を統合して経路グラフを作成する場合を例に説明する。図１における○印は各軌跡に含まれる測位点を表す。ここでは、軌跡間の距離がε以下の場合に、一方の軌跡の測位点を他方の軌跡の測位点に統合することで、軌跡を統合することとする。なお、説明を簡単にするため、軌跡ｔ１の前半部分と軌跡ｔ３の前半部分との距離、軌跡ｔ１の後半部分と軌跡ｔ４の後半部分との距離、軌跡ｔ４の前半部分と軌跡ｔ６の前半部分との距離、軌跡ｔ３の後半部分と軌跡ｔ６の後半部分との距離をεとする。また、軌跡ｔ１と軌跡ｔ２との距離、及び軌跡ｔ５と軌跡ｔ６との距離はεより小さい距離とする。
【００１７】
図１のＡの状態から、軌跡間の距離が小さい軌跡ｔ１と軌跡ｔ２、及び軌跡ｔ５と軌跡ｔ６とを統合する。ここでは、軌跡ｔ２を軌跡ｔ１へ、軌跡ｔ５を軌跡ｔ６へ統合するものとすると、図１のＢの状態となる。次に、軌跡ｔ３に着目すると、軌跡（ｔ１＋ｔ２）との距離は、前半部分ではε以下であるが、後半部分ではεより大きくなっている。一方、軌跡ｔ４との距離は、全範囲においてε以下であるため、軌跡ｔ３と軌跡ｔ４とを統合する。ここでは、軌跡ｔ３を軌跡ｔ４へ統合するものとすると、図１のＣの状態となる。なお、軌跡ｔ４に着目した場合でも、軌跡（ｔ５＋ｔ６）との距離は、前半部分ではε以下であるが、後半部分ではεより大きくなっているため、軌跡ｔ３と軌跡ｔ４とを統合するとの判断になる。さらに、軌跡（ｔ３＋ｔ４）の前半部分と軌跡（ｔ５＋ｔ６）の前半部分との距離、及び軌跡（ｔ３＋ｔ４）の後半部分と軌跡（ｔ１＋ｔ２）の後半部分との距離がε以下であるため、これらを統合し、図１のＤの状態となる。図１のＤの状態では、軌跡間の距離がε以下となる部分が存在しないため、ここで軌跡の統合を終了し、図１のＤの状態を経路グラフとすることができる。
【００１８】
しかし、図１のＤに示すように作成された経路グラフでは、元の軌跡ｔ-３における軌跡ｔ１側から軌跡ｔ２側へ向かう流れが表れておらず、元の軌跡ｔ１〜ｔ６の全てをよく近似した経路グラフとはいえない。これは、各軌跡について、他のどの軌跡と統合するかを、軌跡間の距離のみに基づいて判定しており、順次統合していく過程で、元の軌跡全体の特徴が失われているためであると考えられる。
【００１９】
そこで、第１実施形態では、元の軌跡全体の特徴が、経路グラフにより反映されるように、元の軌跡の密集度も加味して、経路グラフを作成する。
【００２０】
以下、第１実施形態に係る経路グラフ作成装置の詳細について説明する。
【００２１】
図２に示すように、第１実施形態に係る経路グラフ作成装置１０は、軌跡データ生成装置２２と、軌跡データ記憶部２４と共に、経路グラフ作成システム２０に含まれる。
【００２２】
軌跡データ生成装置２２は、移動体の位置を測位するセンサ２６の各々で定期的に測位された移動体の位置を示す測位データを、ネットワーク２８を介して取得する。センサ２６は、移動体の一例である人が保持する携帯電話、スマートフォン等の端末や、移動体の一例である車両に搭載されたカーナビゲーションシステム等で利用されるＧＰＳ等とすることができる。測位データには、緯度及び経度で示される位置データ、測位した時刻を示す時刻情報、及びセンサ２６を識別するセンサＩＤが含まれる。軌跡データ生成装置２２は、取得した複数の測位データを、センサＩＤ毎に抽出し、各測位データに含まれる位置データを、時刻情報に基づいて時系列に並べて軌跡データを生成する。例えば、センサＩＤ＝ｋの測位データに含まれる位置データが示す測位点をｐｋｉ（ｉ＝１，２，・・・，ｎ、ｎはセンサＩＤ＝ｋを含む測位データに含まれる位置データの総数）とすると、軌跡ｔｋを示す軌跡データは、ｔｋ＝＜ｐｋ１，ｐｋ２，・・・，ｐｋｎ＞と表すことができる。なお、測位点ｐｉを示す位置データは、ｐｉ＝（ｘｉ，ｙｉ）∈Ｒ２（Ｒ２は実数を要素とする二次元空間）である。
【００２３】
軌跡データ生成装置２２は、生成した複数の軌跡データを、軌跡データ記憶部２４に記憶する。軌跡データ記憶部２４は、軌跡データ生成装置２２に設けられた記憶装置であってもよいし、軌跡データ生成装置２２とは別の外部装置として設けられた記憶装置であってもよい。また、軌跡データ記憶部２４は、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の可搬型記憶媒体であってもよい。
【００２４】
図３に、第１実施形態に係る経路グラフ作成装置１０の機能ブロック図を示す。経路グラフ作成装置１０には、軌跡データ記憶部２４に記憶された軌跡データ集合が入力される。図４に、軌跡データ集合に含まれる軌跡データの各々が示す軌跡の概念図の一例を示す。図４の例では、軌跡データ集合には、軌跡ｔ１〜ｔ６の各々を示す軌跡データが含まれる。
【００２５】
図３に示すように、経路グラフ作成装置１０は、共通化箇所特定部１１と、代表経路抽出部１２と、統合部１３とを備える。以下、経路グラフ作成装置１０の各部について詳述する。なお、共通化箇所特定部１１及び代表経路抽出部１２は、開示の技術の抽出部の一例である。また、統合部１３は、開示の技術の作成部の一例である。
【００２６】
共通化箇所特定部１１は、入力された軌跡データ集合に含まれる軌跡データから１つずつ処理対象の軌跡を示す軌跡データを選択する。共通化箇所特定部１１は、処理対象の軌跡から所定距離ε内に存在する他の軌跡の部分を、処理対象の軌跡と他の軌跡との共通化箇所として特定する。軌跡間の距離は、例えばフレッシェ（Frechet）距離を用いることができる。図５に、軌跡ｔ３と他の軌跡との共通化箇所を特定した一例を示す。図５では、軌跡ｔ３の各測位点ｐ３ｉ（ｉ＝１，２，３，４，５）からの距離εの範囲を、網掛けした破線の円で示している。共通化箇所特定部１１は、この範囲に含まれる他の軌跡の部分を、共通化箇所として特定する。以下では、各軌跡ｔｋの測位点ｐｋｉ毎の共通化箇所をαｋｉと表記し、共通化箇所αｋｉの集合をαｋと表記する。図６に、各軌跡ｔｋについて特定した共通化箇所の集合αｋを示す。
【００２７】
また、共通化箇所特定部１１は、各軌跡ｔｋについて、各軌跡の周辺における他の軌跡の密集度を示す得点を計算する。具体的には、共通化箇所特定部１１は、各軌跡ｔｋに所定の点数を設定し、設定した点数をその軌跡ｔｋに含まれる測位点ｐｋｉの各々の持ち点として分配する。そして、測位点ｐｋｉの持ち点を、その測位点ｐｋｉについての共通化箇所αｋｉとして特定された他の軌跡に分配し、軌跡毎に分配された持ち点を合計し、その軌跡の密集度を示す得点とする。
【００２８】
例えば、各軌跡に設定する点数を１００点とすると、軌跡ｔ３には５つの測位点が含まれるため、共通化箇所特定部１１は、図７のＡに示すように、軌跡ｔ３の各測位点ｐ３ｉに各２０点の持ち点を分配する。また、図５に示すように、測位点ｐ３１についての共通化箇所α３１として、軌跡ｔ１、ｔ２、及びｔ４の各々の部分が特定されている。そこで、共通化箇所特定部１１は、図７のＢに示すように、測位点ｐ３１の持ち点２０点を軌跡ｔ１、ｔ２、及びｔ４の各々に分配する。共通化箇所特定部１１は、他の測位点ｐ３ｉについての共通化箇所α３ｉについても同様に持ち点を分配する。図７では、各軌跡ｔｋに分配された持ち点を網掛けのマスで示している。そして、共通化箇所特定部１１は、軌跡ｔｋ毎に分配された持ち点の合計（例えば、軌跡ｔ２の合計は図７のＣ）を、共通化箇所α３に基づく得点として計算する。
【００２９】
共通化箇所特定部１１は、他の共通化箇所αｋに基づく得点も同様に計算し、図８に示すように、共通化箇所αｋに基づく得点を軌跡ｔｋ毎に集計する。図７のＤに示す共通化箇所α３に基づく得点は、図８のＡに対応する。共通化箇所特定部１１は、軌跡ｔｋ毎の共通化箇所αｋに基づく得点の合計（例えば、軌跡ｔ３の合計は図８のＢ）を、各軌跡ｔｋの密集度を示す得点として計算する。
【００３０】
代表経路抽出部１２は、軌跡データを１つずつ処理対象の軌跡を示す軌跡データとして選択し、処理対象の軌跡についての共通化箇所に含まれる測位点を接続した経路から、処理対象の軌跡と対応した代表経路を抽出する。具体的には、代表経路抽出部１２は、図９の上段に示すように、軌跡ｔｋ（図９の例では軌跡ｔ３）について、共通化箇所特定部１１で共通化箇所αｋとして特定された他の軌跡の部分に含まれる測位点のみを取り出す。すなわち、共通化箇所について、測位点間を接続する辺を消去した状態となる。なお、図９では、処理対象の軌跡である軌跡ｔ３を破線で示している。
【００３１】
代表経路抽出部１２は、図９の下段に示すように、取り出した測位点をノードとする平面グラフを作成する。平面グラフは、例えば、測位点に対応するノードをボロノイ図における母点とし、ボロノイ図において隣接する領域に対応する母点同士を接続したドロネーグラフを構築することにより作成することができる。なお、平面グラフは、ドロネーグラフに限定されず、他の平面グラフを適用してもよい。
【００３２】
代表経路抽出部１２は、作成した平面グラフ上のパス（経路）のうち、ノードの密集度、及び処理対象の軌跡との距離に基づいて、処理対象の軌跡とのマッチング度の高い経路を代表経路として抽出する。マッチング度は、軌跡との距離が近い経路ほど高く、軌跡との距離が同程度であれば、ノードの密集度が高い箇所を通過する経路ほど高くなるように定める。これにより、処理対象の軌跡と所定距離以内に含まれる他の軌跡において共通化された経路が、処理対象の軌跡に対応する代表経路として抽出される。
【００３３】
図１０を参照して、平面グラフから処理対象の軌跡ｔ３に対応する代表経路を抽出する場合について説明する。以下では、平面グラフにおいて、測位点ｐｋｉに対応するノードを、ノードｐｋｉと表記する。図１０は、軌跡ｔ３についての共通化箇所α３から作成した平面グラフを示す。なお、図１０では、処理対象の軌跡である軌跡ｔ３を破線で示している。
【００３４】
代表経路抽出部１２は、軌跡ｔ３の始点であるノードｐ３１から距離ε以内（図１０中のノードｐ３１周辺の破線円の範囲）に含まれる平面グラフのノードを探索する。ここでは、ノードｐ１１、ｐ２１、及びｐ４１が探索される。代表経路抽出部１２は、始点であるノードｐ３１と、軌跡ｔ３における次のノードｐ３２を通る直線（図１０中の一点破線）で、ノードｐ３１からの距離がεの円を分割し、２つの半円のうち、含まれるノードが多い半円を選択する。これにより、周辺のノードの密集度が高いノードを選択することができる。図１０の例では、上側の半円には２つのノード、下側の半円には１つのノードが含まれるため、上側の半円を選択する。この選択した半円に含まれるノードのうち、ノードｐ３１からの距離が最も遠いノード（ここでは、ノードｐ１１）を、抽出する代表経路の始点とする。
【００３５】
代表経路抽出部１２は、軌跡ｔ３の終点であるノードｐ３５についても同様に、ノードｐ３５から距離ε以内（図１０中のノードｐ３５周辺の破線円の範囲）に含まれる平面グラフのノードを探索する。ここでは、ノードｐ４５、ｐ５４、及びｐ６５が探索される。代表経路抽出部１２は、終点であるノードｐ３５と、軌跡ｔ３における前のノードｐ３４を通る直線（図１０中の一点破線）で、ノードｐ３５からの距離がεの円を分割し、２つの半円のうち、含まれるノードが多い半円を選択する。この選択した半円に含まれるノードのうち、ノードｐ３５からの距離が最も遠いノード（ここでは、ノードｐ６５）を、抽出する代表経路の終点とする。
【００３６】
代表経路抽出部１２は、平面グラフ上のパスであって、始点及び終点が求めた始点（ノードｐ１１）及び終点（ノードｐ６５）となるパスのうち、軌跡ｔ３との距離（例えばFrechet距離）が最も近いパスを探索する。例えば、ノードｐ１１の次のノードの候補としては、ノードｐ２１、ｐ１３、及びｐ４１が存在するが、このうち軌跡ｔ３との距離が最も近いノードｐ２１を、ノードｐ１１の次のノードとして選択する。軌跡ｔ３との距離が最も近いノードが複数存在する場合には、それらのノードのうち、周辺のノードの密集度が最も高いノードを選択する。密集度が高いノードは、代表経路の始点及び終点を選択した方法と同様に選択することができる。なお、軌跡ｔ３との距離が近い順に所定個のノードを候補とし、その中から周辺の密集度に基づいて、代表経路に含まれるノードを選択してもよい。このようなノードの選択を始点から開始して終点に至るまで繰り返すことで、代表経路を選択する。以下では、軌跡ｔｋに対応する代表経路をΠｋと表記する。
【００３７】
代表経路抽出部１２は、他の軌跡ｔｋについても同様に代表経路Πｋを抽出する。図１１に、各軌跡ｔｋについて作成された平面グラフ、及び抽出された代表経路Πｋを示す。なお、図１１では、処理対象の軌跡ｔｋを破線で、代表経路Πｋを太線の矢印で接続したパスで表している。
【００３８】
統合部１３は、代表経路抽出部１２で抽出された各軌跡に対応する代表経路の各々を、共通化箇所特定部１１で計算した各軌跡の密集度を示す得点が高い代表経路から順に、その段階で作成されている経路グラフ（仮経路グラフ）と統合して、経路グラフを作成する。統合の方法は、図１を参照して説明した方法と同様で、代表経路に含まれるノード間の距離がε以下の場合に、処理対象の代表経路のノードを仮経路グラフのノードに統合する。得点が高い代表経路は、その代表経路に対応する軌跡周辺の他の軌跡の密集度が高いことを表しており、より多くの軌跡の特徴を代表する代表経路であるといえる。そのような代表経路から順に処理していくことで、元の軌跡の特徴をより良く表した経路グラフを作成することができる。
【００３９】
例えば、共通化箇所特定部１１において、図８に示すような各軌跡ｔｋの密集度を示す得点が得られたとする。この場合、統合部１３は、代表経路Π４→Π３→Π２→Π６→Π１→Π５の順で処理する。具体的には、まず、図１２のＡに示すように、統合部１３は、空の仮経路グラフＧ（０）に対して、最初の処理対象の代表経路Π４を統合する。この場合、図１２のＢに示すように、代表経路Π４がそのままこの段階での仮経路グラフＧ（Π４）となる。次に、図１２のＣに示すように、この仮経路グラフＧ（Π４）に、次の代表経路Π３を統合する。ここでは、ノードｐ３３とノードｐ４３との距離がε以下であるので、処理対象の代表経路Π３のノードｐ３３を、仮経路グラフＧ（Π４）のノードｐ４３に統合する。これにより、図１２のＤに示すように、仮経路グラフＧ（Π４）に代表経路Π３を統合した仮経路グラフＧ（Π４＋Π３）が作成される。
【００４０】
以下、同様に、図１２のＥに示すように、仮経路グラフＧ（Π４＋Π３）に代表経路Π２を統合し、図１２のＦに示すような仮経路グラフＧ（Π４＋Π３＋Π２）を作成する。また、図１３のＧに示すように、仮経路グラフＧ（Π４＋Π３＋Π２）に代表経路Π６を統合し、図１３のＨに示すような仮経路グラフＧ（Π４＋Π３＋Π２＋Π６）を作成する。また、図１３のＩに示すように、仮経路グラフＧ（Π４＋Π３＋Π２＋Π６）に代表経路Π１を統合し、図１３のＪに示すような仮経路グラフＧ（Π４＋Π３＋Π２＋Π６＋Π１）を作成する。また、図１３のＫに示すように、仮経路グラフＧ（Π４＋Π３＋Π２＋Π６＋Π１）に代表経路Π５を統合し、図１３のＬに示すような仮経路グラフＧ（Π４＋Π３＋Π２＋Π６＋Π１＋Π５）を作成する。この段階で未処理の代表経路が存在しなくなるため、仮経路グラフＧ（Π４＋Π３＋Π２＋Π６＋Π１＋Π５）が最終的な経路グラフＧとなる。
【００４１】
統合部１３は、作成した経路グラフＧ＝（Ｖ，Ｅ）を出力する。なお、Ｖは、経路グラフのノードを示すデータの集合、Ｅはノード間を接続する辺を示すデータの集合である。
【００４２】
経路グラフ作成装置１０は、例えば図１４に示すコンピュータ４０で実現することができる。コンピュータ４０はＣＰＵ４２と、メモリ４４と、不揮発性の記憶部４６と、入出力インターフェース（Ｉ／Ｆ）４７と、ネットワークＩ／Ｆ４８とを備えている。ＣＰＵ４２と、メモリ４４と、記憶部４６と、入出力Ｉ／Ｆ４７と、ネットワークＩ／Ｆ４８とは、バス４９を介して互いに接続されている。
【００４３】
記憶部４６は、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（solid state drive）、フラッシュメモリ等によって実現できる。記録媒体としての記憶部４６には、コンピュータ４０を経路グラフ作成装置１０として機能させるための経路グラフ作成プログラム５０が記憶されている。ＣＰＵ４２は、経路グラフ作成プログラム５０を記憶部４６から読み出してメモリ４４に展開し、経路グラフ作成プログラム５０が有するプロセスを順次実行する。
【００４４】
経路グラフ作成プログラム５０は、共通化箇所特定プロセス５１と、代表経路抽出プロセス５２と、統合プロセス５３とを有する。ＣＰＵ４２は、共通化箇所特定プロセス５１を実行することで、図３に示す共通化箇所特定部１１として動作する。また、ＣＰＵ４２は、代表経路抽出プロセス５２を実行することで、図３に示す代表経路抽出部１２として動作する。また、ＣＰＵ４２は、統合プロセス５３を実行することで、図３に示す統合部１３として動作する。
【００４５】
なお、経路グラフ作成装置１０は、例えば半導体集積回路、より詳しくはＡＳＩＣ(Application Specific Integrated Circuit)等で実現することも可能である。
【００４６】
次に、第１実施形態の作用を説明する。軌跡データ生成装置２２が、複数のセンサ２６の各々で測位された測位データを、ネットワーク２８を介して取得し、測位データから軌跡データを生成して、軌跡データ記憶部２４に記憶する。経路グラフ作成装置１０に、軌跡データ記憶部２４に記憶された軌跡データ集合が入力されと、経路グラフ作成装置１０において、図１５に示す経路グラフ作成処理が実行される。
【００４７】
図１５に示す経路グラフ作成処理のステップＳ１１で、共通化箇所特定部１１が、変数ｋに１を設定し、次のステップＳ１２で、軌跡ｔｋを処理対象に設定する。次に、ステップＳ１３で、共通化箇所特定部１１が、処理対象の軌跡ｔｋから所定距離ε内に存在する他の軌跡の部分を、共通化箇所αｋとして特定する。
【００４８】
次に、ステップＳ１４で、共通化箇所特定部１１が、各軌跡ｔｋに設定した所定の点数を、その軌跡ｔｋに含まれる測位点ｐｋｉの各々の持ち点として分配する。そして、共通化箇所特定部１１は、測位点ｐｋｉの持ち点を、その測位点ｐｋｉについての共通化箇所αｋｉとして特定された他の軌跡に分配し、軌跡毎に分配された持ち点を合計する。これにより、共通化箇所特定部１１は、例えば図７に示すような、共通化箇所αｋに基づく得点を計算する。
【００４９】
次に、ステップＳ１５で、共通化箇所特定部１１が、変数ｋが、軌跡データ集合に含まれる軌跡データの数ｎとなったか否かを判定する。ｋがｎ未満の場合には、処理はステップＳ１６へ移行し、共通化箇所特定部１１が、ｋを１インクリメントして、ステップＳ１２に戻る。ｋがｎとなった場合には、処理はステップＳ１７へ移行する。
【００５０】
ステップＳ１７では、共通化箇所特定部１１が、例えば図８に示すように、上記ステップＳ１４で計算した共通化箇所αｋに基づく得点を、軌跡ｔｋ毎に集計し、各軌跡ｔｋの密集度を示す得点を計算する。
【００５１】
次に、ステップＳ１８で、代表経路抽出部１２が、変数ｋに１を設定し、次のステップＳ１９で、軌跡ｔｋを処理対象に設定する。次に、ステップＳ２０で、代表経路抽出部１２が、軌跡ｔｋについて、上記ステップＳ１３で共通化箇所αｋとして特定された他の軌跡の部分に含まれる測位点間を接続する辺を消去して、測位点のみを取り出す。そして、代表経路抽出部１２は、取り出した測位点をノードとする平面グラフを作成する。
【００５２】
次に、ステップＳ２１で、代表経路抽出部１２が、上記ステップＳ２０で作成した平面グラフ上のパスのうち、ノードの密集度、及び軌跡ｔｋとの距離に基づいて、軌跡ｔｋとのマッチング度の高いパスを代表経路Πｋとして抽出する。
【００５３】
次に、ステップＳ２２で、代表経路抽出部１２が、変数ｋが、軌跡データ集合に含まれる軌跡データの数ｎとなったか否かを判定する。ｋがｎ未満の場合には、処理はステップＳ２３へ移行し、代表経路抽出部１２が、ｋを１インクリメントして、ステップＳ１９に戻る。ｋがｎとなった場合には、処理はステップＳ２４へ移行する。
【００５４】
ステップＳ２４では、統合部１３が、上記ステップＳ２１で抽出された各軌跡に対応する代表経路から、未処理の代表経路のうち、上記ステップＳ１７で計算された各軌跡の密集度を示す得点が最も高い代表経路を選択する。そして、統合部１３は、選択した代表経路を、その段階での仮経路グラフに統合する。統合部１３は、未処理の代表経路が存在しなくなるまで仮経路グラフへの統合を繰り返し、最終的な経路グラフを作成する。統合部１３は、作成した経路グラフＧ＝（Ｖ，Ｅ）を出力し、経路グラフ作成処理は終了する。
【００５５】
以上説明したように、第１実施形態に係る経路グラフ作成装置１０によれば、各軌跡データが示す軌跡について、周辺の他の軌跡との共通化により代表経路を抽出する。そして、各軌跡に対応する代表経路を、軌跡周辺の他の軌跡の密集度が高い順に統合していくことで、経路グラフを作成する。このため、単純に距離が近い軌跡同士を順次統合して経路グラフを作成する場合に比べ、元の軌跡の特徴を良く表した経路グラフを作成することができる。また、軌跡データのみから経路グラフを作成するため、第１実施形態により作成した経路グラフを経路分析に用いた際に、メッシュの面積の調整などによる不都合が生じることなく、適切な分析結果を得ることができる。また、道路ネットワークや地図データ等が対応していない箇所についても、軌跡データに基づいて経路グラフを作成することができるため、人の自由な移動についても、適切な分析結果を得ることができる。
【００５６】
また、代表経路を抽出する際、共通化箇所に含まれる測位点をノードとする平面グラフを作成することで、効率的に代表経路を抽出することができる。
【００５７】
また、軌跡周辺の他の軌跡の密集度を、上記したような得点として計算することで、簡易な処理で密集度を求めることができる。
【００５８】
＜第２実施形態＞
次に、第２実施形態について説明する。図１に示すように、第２実施形態に係る経路グラフ作成装置２１０も、経路グラフ作成システム２０に含まれる。なお、第２実施形態に係る経路グラフ作成装置２１０において、第１実施形態に係る経路グラフ作成装置１０と同一の部分については、同一符号を付して詳細な説明を省略する。
【００５９】
図１６に、第２実施形態に係る経路グラフ作成装置２１０の機能ブロック図を示す。経路グラフ作成装置２１０には、第１実施形態と同様に、軌跡データ集合が入力される。経路グラフ作成装置２１０は、経路束抽出部１６と、最適化部１７とを備える。なお、経路束抽出部１６は、開示の技術の抽出部の一例である。
【００６０】
経路束抽出部１６は、軌跡データが示す軌跡の各々を、複数のノードとノード間を接続する辺とを含むネットワークデータ上に対応させる。ネットワークデータは、例えば、入力された軌跡データ集合内の軌跡データに含まれる位置データが示す測位点をノードとする平面グラフとすることができる。また、道路ネットワークデータを利用可能な場合には、道路ネットワークデータを用いてもよい。経路束抽出部１６は、ネットワークデータ上に対応させた軌跡から所定距離ε以内に存在するネットワークデータの部分に含まれるパスを、経路グラフの作成に利用する経路として抽出する。軌跡ｔｋについて抽出された経路を、経路ｃｋｉ（ｉ＝１，２，・・・，ｎ、ｎは軌跡ｔｋについて抽出された経路の総数）とし、経路ｃｋｉをまとめて経路束Ｓｋと表記する。
【００６１】
以下では、説明を簡単にするため、例えば図１７に示すように、ネットワークデータを格子状で表す。図１７の例では、○印がノード、ノード内に記載した数字がノードの識別番号（ノードＩＤ）、及びノード間の破線が辺である。例えば、図１７に示すような軌跡ｔ１をこのネットワークデータに対応させたときの、軌跡ｔ１からの距離がεの範囲が、図１７中の斜線で示す範囲であったとする。経路束抽出部１６は、斜線の範囲から、図１７の中段に示すような６つの経路ｃ１１〜ｃ１６を、軌跡ｔ１についての経路束Ｓ１として抽出する。なお、ここでは、経路を辺の系列で表現し、辺は両端のノードのノードＩＤで表すものとする。例えば、経路ｃ１１は、以下のように表記する。
ｃ１１：２＿８，８＿９，９＿１０，１０＿１６，１６＿１７，
１７＿２３，２３＿２４
【００６２】
さらに、以下では、説明を簡単にするため、図１８に示すような軌跡ｔｋ（ｋ＝１，２，３）の各々について、以下の経路束Ｓｋが抽出されるものとして説明する。
【００６３】
＜Ｓ１＞
ｃ１１：２＿８，８＿１４，１４＿１５，１５＿１６，１６＿２２，
２２＿２３，２３＿２４
ｃ１２：２＿８，８＿９，９＿１５，１５＿１６，１６＿１７，１７＿２３，
２３＿２４
ｃ１３：２＿８，８＿９，９＿１０，１０＿１６，１６＿２２，２２＿２３，
２３＿２４
＜Ｓ２＞
ｃ２１：２＿８，８＿１４，１４＿２０，２０＿２１，２１＿２２，
２２＿２３，２３＿２４
ｃ２２：２＿８，８＿１４，１４＿１５，１５＿２１，２１＿２２，
２２＿２３，２３＿２４
ｃ２３：２＿８，８＿１４，１４＿１５，１５＿１６，１６＿２２，
２２＿２３，２３＿２４
＜Ｓ３＞
ｃ３１：７＿８，８＿９，９＿１０，１０＿１６，１６＿１７，
１７＿２３，２３＿２４
ｃ３２：１３＿１４，１４＿１５，１５＿１６，１６＿１７，１７＿２３，
２３＿２４
【００６４】
最適化部１７は、経路束抽出部１６により抽出された経路束に含まれる辺のうち、経路グラフに含まれる辺の組み合わせを、元の軌跡との近似度が高くなるように最適化することにより、経路グラフを作成する。
【００６５】
最適化部１７は、例えば以下のような最適化を行う。まず、最適化部１７は、（１）経路は辺の集合であること、（２）軌跡はいずれかの経路に一致すること、及び（３）経路グラフは、軌跡に一致する経路を全て含むこと、という制約条件を設定する。そして、最適化部１７は、この制約条件の下、経路グラフに含まれる辺の数を最小化するように最適化する。
【００６６】
例えば、最適化部１７は、経路束抽出部１６で抽出された経路束Ｓｋに含まれる辺の各々をｘ、経路ｃｋｉをｙ、軌跡ｔｋに一致する経路をｚとし、それぞれを下記のように定義する。なお、軌跡に一致する経路とは、軌跡に完全に一致する経路だけでなく、軌跡と所定割合以上の一致度で一致する経路を含んでもよい。
【００６７】
ｘ２＿８，・・・，ｘ２３＿２４∈｛０，１｝
ｙ１１，ｙ１２，・・・，ｙ３２∈｛０，１｝
ｚ１，ｚ２，ｚ３∈｛０，１｝
【００６８】
また、上記（１）〜（３）の制約条件を、下記のように定義する。
（１）経路は辺の集合である
ｙ１１：＝ｘ２＿８∧ｘ８＿１４∧ｘ１４＿１５∧ｘ１５＿１６∧ｘ１６＿２２
∧ｘ２２＿２３∧ｘ２３＿ｘ２４
ｙ１２：＝ｘ２＿８∧ｘ８＿９∧ｘ９＿１５∧ｘ１５＿１６∧ｘ１６＿１７
∧ｘ１７＿２３∧ｘ２３＿ｘ２４
ｙ１３：＝ｘ２＿８∧ｘ８＿９∧ｘ９＿１０∧ｘ１０＿１６∧ｘ１６＿２２
∧ｘ２２＿２３∧ｘ２３＿ｘ２４
・・・
ｙ３２：＝ｘ１３＿１４∧ｘ１４＿１５∧ｘ１５＿１６∧ｘ１６＿１７
∧ｘ１７＿２３∧ｘ２３＿ｘ２４
【００６９】
（２）軌跡はいずれかの経路に一致する
ｚ１：＝ｙ１１∨ｙ１２∨ｙ１３
ｚ２：＝ｙ２１∨ｙ２２∨ｙ２３
ｚ３：＝ｙ３１∨ｙ３２
【００７０】
（３）経路グラフは、軌跡に一致する経路を全て含む
Ｇ＝ｚ１∧ｚ２∧ｚ３
【００７１】
さらに、最適化部１７は、経路グラフに含まれる辺の数を最小化することを、下記の目的関数で定義する。
ｍｉｎｉｍｉｚｅ  ｘ２＿８＋・・・＋ｘ２３＿２４
【００７２】
最適化部１７は、上記（１）〜（３）の制約下における上記目的関数を、０−１整数計画の最適化問題に還元し、ｘの最適化解を求める。すなわち、経路グラフＧに含まれる辺を示すｘは１、含まれない辺を示すｘは０となる最適化解が得られる。例えば、図１９の上段に示すような軌跡ｔｋ（ｋ＝１，２，３）とネットワークデータとを対応させて抽出した経路束Ｓｋに含まれる各辺について、図１９の中段に示すような最適化解が得られる。最適化部１７は、得られた最適化解とネットワークデータとに基づいて、経路グラフを作成する。具体的には、最適化解で値が１として得られたｘに対応する辺を接続することにより、図１９の下段に示すような経路グラフを作成することができる。
【００７３】
経路グラフ作成装置２１０は、第１実施形態に係る経路グラフ作成装置１０と同様、例えば図２０に示すコンピュータ４０で実現することができる。コンピュータ４０の記憶部４６には、コンピュータ４０を経路グラフ作成装置２１０として機能させるための経路グラフ作成プログラム２５０が記憶されている。ＣＰＵ４２は、経路グラフ作成プログラム２５０を記憶部４６から読み出してメモリ４４に展開し、経路グラフ作成プログラム２５０が有するプロセスを順次実行する。
【００７４】
経路グラフ作成プログラム２５０は、経路束抽出プロセス５６と、最適化プロセス５７とを有する。ＣＰＵ４２は、経路束抽出プロセス５６を実行することで、図１６に示す経路束抽出部１６として動作する。また、ＣＰＵ４２は、最適化プロセス５７を実行することで、図１６に示す最適化部１７として動作する。
【００７５】
なお、経路グラフ作成装置２１０は、例えば半導体集積回路、より詳しくはＡＳＩＣ等で実現することも可能である。
【００７６】
次に、第２実施形態の作用を説明する。第２実施形態では、経路グラフ作成装置２１０において、図２１に示す経路グラフ作成処理が実行される。
【００７７】
図２１に示す経路グラフ作成処理のステップＳ３１で、経路束抽出部１６が、変数ｋに１を設定し、次のステップＳ３２で、軌跡ｔｋを処理対象に設定する。
【００７８】
次に、ステップＳ３３で、経路束抽出部１６が、軌跡ｔｋをネットワークデータ上に対応させる。そして、経路束抽出部１６は、ネットワークデータ上に対応させた軌跡から所定距離ε以内に存在するネットワークデータの部分に含まれる経路束Ｓｋを抽出する。
【００７９】
次に、ステップＳ３４で、経路束抽出部１６が、変数ｋが、軌跡データ集合に含まれる軌跡データの数ｎとなったか否かを判定する。ｋがｎ未満の場合には、処理はステップＳ３５へ移行し、経路束抽出部１６が、ｋを１インクリメントして、ステップＳ３２に戻る。ｋがｎとなった場合には、処理はステップＳ３６へ移行する。
【００８０】
次に、ステップＳ３６で、最適化部１７が、（１）経路は辺の集合であること、（２）軌跡はいずれかの経路に一致すること、及び（３）経路グラフは、軌跡に一致する経路を全て含むこと、という制約条件を設定する。そして、最適化部１７は、この制約条件の下、経路グラフに含まれる辺の数を最小化するように、例えば上記したような０−１整数計画の最適化問題を解くことにより、経路グラフに含まれる辺を示す最適化解を求める。
【００８１】
次に、ステップＳ３７で、最適化部１７が、上記ステップＳ３６で得られた最適化解と、上記ステップＳ３３で用いたネットワークデータとに基づいて、経路グラフＧを作成する。最適化部１７は、作成した経路グラフＧを出力し、経路グラフ作成処理は終了する。
【００８２】
以上説明したように、第２実施形態に係る経路グラフ作成装置２１０によれば、ネットワークデータ上に軌跡を対応させ、軌跡から所定距離内の範囲に含まれるネットワークデータの部分から経路束を抽出する。そして、経路束に含まれる辺のうち、経路グラフに含まれる辺の組み合わせを、経路グラフに含まれる辺の数が最小となるように最適化して、経路グラフを作成する。このため、元の軌跡の特徴を良く表した経路グラフを作成することができる。
【００８３】
また、第２実施形態では、軌跡データとネットワークデータのみから経路グラフを作成するが、このネットワークデータは、軌跡データから作成した平面グラフを用いることができる。従って、第１実施形態と同様に、第２実施形態により作成した経路グラフを経路分析に用いた際に、メッシュの面積の調整などによる不都合が生じることなく、適切な分析結果を得ることができる。また、道路ネットワークや地図データ等が対応していない箇所についても、軌跡データに基づいて経路グラフを作成することができるため、人の自由な移動についても、適切な分析結果を得ることができる。
【００８４】
なお、上記では開示の技術に係る経路グラフ作成プログラムの一例である経路グラフ作成プログラム５０及び２５０が記憶部４６に予め記憶（インストール）されている態様を説明したが、これに限定されない。開示の技術に係る経路グラフ作成プログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の記録媒体に記録された形態で提供することも可能である。
【００８５】
以上の各実施形態に関し、更に以下の付記を開示する。
【００８６】
（付記１）
複数の経路のうちの特定の経路を統合させる対象の統合先経路を前記複数の経路のうちの他の経路の中から抽出する際に、経路の分布密度の高さに応じて抽出可能性を高める制御を行う、
処理をコンピュータに実行させることを特徴とする統合先経路抽出方法。
【００８７】
（付記２）
前記特定の経路から所定距離内に第１の経路と第２の経路とが存在する場合に、前記第２の経路の周辺よりも、前記第１の経路の周辺の方がより高い経路の密集度を示す場合に、該第１の経路を前記が統合先経路として抽出する、
処理をコンピュータに実行させることを特徴とする付記１記載の統合先経路抽出方法。
【００８８】
（付記３）
前記経路の分布密度は、経路内のノードの分布密度に基づいて算出される、ことを特徴とする付記１又は２記載の統合先経路抽出方法。
【００８９】
（付記４）
複数の経路のうちの特定の経路を統合させる対象の統合先経路を前記複数の経路のうちの他の経路の中から抽出する際に、経路の分布密度の高さに応じて抽出可能性を高める制御を行う抽出部
を含む統合先経路抽出装置。
【００９０】
（付記５）
複数の経路のうちの特定の経路を統合させる対象の統合先経路を前記複数の経路のうちの他の経路の中から抽出する際に、経路の分布密度の高さに応じて抽出可能性を高める制御を行う、
処理をコンピュータに実行させるための統合先経路抽出プログラム。
【００９１】
（付記６）
コンピュータに、
移動体の位置を示す点の系列で表される複数の軌跡データの各々について、処理対象の軌跡データが示す軌跡から所定距離内に存在する他の軌跡の点を接続した経路から、前記処理対象の軌跡との距離及び点の密集度を基に代表経路を抽出し、
軌跡毎に抽出した複数の代表経路に基づき、経路グラフを作成する
ことを含む処理を実行させる経路グラフ作成方法。
【００９２】
（付記７）
前記経路グラフを作成する際、軌跡毎に抽出した複数の代表経路の各々を、前記代表経路に対応する軌跡周辺の他の軌跡の密集度が高い代表経路から順に、作成中の仮経路グラフとの距離に基づいて該仮経路グラフに統合して、経路グラフを作成する付記６記載の経路グラフ作成方法。
【００９３】
（付記８）
前記代表経路を抽出する際に、前記所定距離内に存在する他の軌跡の点の各々をノードとする平面グラフを作成し、前記平面グラフ上のパスのうち、前記処理対象の軌跡との距離が近いほど、かつ選択するノード周辺のノードの密集度が高いほど高くなるマッチング度が最も高いパスを、前記代表経路として抽出する付記６及び付記７記載の経路グラフ作成方法。
【００９４】
（付記９）
前記代表経路に対応する軌跡周辺の他の軌跡の密集度を、各軌跡に設定した点数を軌跡に含まれる点の各々に持ち点として分配し、処理対象の軌跡から前記所定距離内に存在する他の軌跡の点に分配された持ち点を合計した得点で表す付記６〜付記８のいずれか１項記載の経路グラフ作成方法。
【００９５】
（付記１０）
コンピュータに、
移動体の位置を示す点の系列で表される複数の軌跡データが示す軌跡の各々を、複数のノードとノード間を接続する辺とを含むネットワークデータに対応させ、軌跡の各々から所定距離内に存在する前記ネットワークデータ上のパスを経路として抽出し、
抽出した複数の経路に含まれる辺のうち、経路グラフに含まれる辺の組み合わせを、前記複数の軌跡との近似度が高くなるように最適化して求めることにより、経路グラフを作成する
ことを含む処理を実行させる経路グラフ作成方法。
【００９６】
（付記１１）
前記最適化の際に、抽出された経路は辺の集合であり、各軌跡は抽出された経路のいずれかに対応し、かつ前記経路グラフは軌跡に対応する全ての経路を含むとの制約の下、前記経路グラフに含まれる辺の数を最小化する付記１０記載の経路グラフ作成方法。
【００９７】
（付記１２）
前記ネットワークデータを、前記複数の軌跡データに含まれる点をノードとする平面グラフとした付記１０または付記１１記載の経路グラフ作成方法。
【００９８】
（付記１３）
移動体の位置を示す点の系列で表される複数の軌跡データの各々について、処理対象の軌跡データが示す軌跡から所定距離内に存在する他の軌跡の点を接続した経路から、前記処理対象の軌跡との距離及び点の密集度を基に代表経路を抽出する抽出部と、
軌跡毎に抽出した複数の代表経路に基づき、経路グラフを作成する作成部と、
を含む経路グラフ作成装置。
【００９９】
（付記１４）
前記作成部は、軌跡毎に抽出した複数の代表経路の各々を、前記代表経路に対応する軌跡周辺の他の軌跡の密集度が高い代表経路から順に、作成中の仮経路グラフとの距離に基づいて該仮経路グラフに統合して、経路グラフを作成する付記１３記載の経路グラフ作成装置。
【０１００】
（付記１５）
前記抽出部は、前記所定距離内に存在する他の軌跡の点の各々をノードとする平面グラフを作成し、前記平面グラフ上のパスのうち、前記処理対象の軌跡との距離が近いほど、かつ選択するノード周辺のノードの密集度が高いほど高くなるマッチング度が最も高いパスを、前記代表経路として抽出する付記１３または付記１４記載の経路グラフ作成装置。
【０１０１】
（付記１６）
前記代表経路に対応する軌跡周辺の他の軌跡の密集度を、各軌跡に設定した点数を軌跡に含まれる点の各々に持ち点として分配し、処理対象の軌跡から前記所定距離内に存在する他の軌跡の点に分配された持ち点を合計した得点で表す付記１３〜付記１５記載のいずれか１項記載の経路グラフ作成装置。
【０１０２】
（付記１７）
移動体の位置を示す点の系列で表される複数の軌跡データの各々が示す軌跡の各々を、複数のノードとノード間を接続する辺とを含むネットワークデータに対応させ、軌跡の各々から所定距離内に存在する前記ネットワークデータ上のパスを経路として抽出する抽出部と、
抽出した複数の経路に含まれる辺のうち、経路グラフに含まれる辺の組み合わせを、前記複数の軌跡との近似度が高くなるように最適化して求めることにより、経路グラフを作成する最適化部と、
を含む経路グラフ作成装置。
【０１０３】
（付記１８）
前記最適化部は、抽出された経路は辺の集合であり、各軌跡は抽出された経路のいずれかに対応し、かつ前記経路グラフは軌跡に対応する全ての経路を含むとの制約の下、前記経路グラフに含まれる辺の数を最小化する付記１７記載の経路グラフ作成装置。
【０１０４】
（付記１９）
前記ネットワークデータを、前記複数の軌跡データに含まれる点をノードとする平面グラフとした付記１７または付記１８記載の経路グラフ作成装置。
【０１０５】
（付記２０）
コンピュータに、
移動体の位置を示す点の系列で表される複数の軌跡データの各々について、処理対象の軌跡データが示す軌跡から所定距離内に存在する他の軌跡の点を接続した経路から、前記処理対象の軌跡との距離及び点の密集度を基に代表経路を抽出し、
軌跡毎に抽出した複数の代表経路に基づき、経路グラフを作成する
ことを含む処理を実行させるための経路グラフ作成プログラム。
【０１０６】
（付記２１）
前記経路グラフを作成する際、軌跡毎に抽出した複数の代表経路の各々を、前記代表経路に対応する軌跡周辺の他の軌跡の密集度が高い代表経路から順に、作成中の仮経路グラフとの距離に基づいて該仮経路グラフに統合して、経路グラフを作成する付記６記載の経路グラフ作成プログラム。
【０１０７】
（付記２２）
前記代表経路を抽出する際に、前記所定距離内に存在する他の軌跡の点の各々をノードとする平面グラフを作成し、前記平面グラフ上のパスのうち、前記処理対象の軌跡との距離が近いほど、かつ選択するノード周辺のノードの密集度が高いほど高くなるマッチング度が最も高いパスを、前記代表経路として抽出する付記２０または付記２１記載の経路グラフ作成プログラム。
【０１０８】
（付記２３）
前記代表経路に対応する軌跡周辺の他の軌跡の密集度を、各軌跡に設定した点数を軌跡に含まれる点の各々に持ち点として分配し、処理対象の軌跡から前記所定距離内に存在する他の軌跡の点に分配された持ち点を合計した得点で表す付記２０〜付記２２のいずれか１項記載の経路グラフ作成プログラム。
【０１０９】
（付記２４）
コンピュータに、
移動体の位置を示す点の系列で表される複数の軌跡データの各々が示す軌跡の各々を、複数のノードとノード間を接続する辺とを含むネットワークデータに対応させ、軌跡の各々から所定距離内に存在する前記ネットワークデータ上のパスを経路として抽出し、
抽出した複数の経路に含まれる辺のうち、経路グラフに含まれる辺の組み合わせを、前記複数の軌跡との近似度が高くなるように最適化して求めることにより、経路グラフを作成する
ことを含む処理を実行させるための経路グラフ作成プログラム。
【０１１０】
（付記２５）
前記最適化の際に、抽出された経路は辺の集合であり、各軌跡は抽出された経路のいずれかに対応し、かつ前記経路グラフは軌跡に対応する全ての経路を含むとの制約の下、前記経路グラフに含まれる辺の数を最小化する付記２４記載の経路グラフ作成プログラム。
【０１１１】
（付記２６）
前記ネットワークデータを、前記複数の軌跡データに含まれる点をノードとする平面グラフとした付記２４または付記２５記載の経路グラフ作成プログラム。
【符号の説明】
【０１１２】
１０、２１０  経路グラフ作成装置
１１   共通化箇所特定部
１２   代表経路抽出部
１３   統合部
１６   経路束抽出部
１７   最適化部
４０   コンピュータ
４２   ＣＰＵ
４４   メモリ
４６   記憶部
５０、２５０  経路グラフ作成プログラム
【図２】
2015210083.tif 000003
【図３】
2015210083.tif 000004
【図４】
2015210083.tif 000005
【図５】
2015210083.tif 000006
【図６】
2015210083.tif 000007
【図８】
2015210083.tif 000008
【図９】
2015210083.tif 000009
【図１０】
2015210083.tif 000010
【図１１】
2015210083.tif 000011
【図１２】
2015210083.tif 000012
【図１３】
2015210083.tif 000013
【図１４】
2015210083.tif 000014
【図１５】
2015210083.tif 000015
【図１６】
2015210083.tif 000016
【図１８】
2015210083.tif 000017
【図１９】
2015210083.tif 000018
【図２０】
2015210083.tif 000019
【図２１】
2015210083.tif 000020
【図１】
2015210083.tif 000021
【図７】
2015210083.tif 000022
【図１７】
2015210083.tif 000023