(57)【特許請求の範囲】
【請求項１】
コンピュータが、
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する経路グラフ生成方法において、
近接距離基準を満たす複数の位置のそれぞれが、設定された同じエリア内に属するか否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御し、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する、
処理を実行することを特徴とする経路グラフ生成方法。
【請求項２】
前記コンピュータが、
前記近接距離基準を満たす前記複数の位置のそれぞれが、異なるエリアに属する場合に、前記複数の位置を１つの代表位置に統合せずに経路グラフを生成するように制御する、
処理を実行することを特徴とする請求項１記載の経路グラフ生成方法。
【請求項３】
前記経路グラフの生成において、前記移動体の異なる時刻における位置のうち、連続する２時刻の各々における一方の位置が、第１のエリアに属する代表位置と近接距離基準を満たし、他方の位置が、前記第１のエリアとは異なる第２のエリアに属する代表位置と近接距離基準を満たす場合、前記第１のエリアに属する代表位置と、前記第２のエリアに属する代表位置とを、異なるエリアに属する代表位置間の連結であることを示す情報を付加して連結する請求項１又は請求項２記載の経路グラフ生成方法。
【請求項４】
前記経路グラフは、前記代表位置を示すノードと、該ノード間を連結するエッジとで表され、前記第１のエリアに属する代表位置と、前記第２のエリアに属する代表位置との間は、同じエリアに属する代表位置間を連結する第１のエッジとは異なる第２のエッジで連結される請求項３記載の経路グラフ生成方法。
【請求項５】
前記複数の移動体の異なる時刻における位置の各々は、該位置が属するエリアに応じたラベルを持ち、前記代表位置は、該代表位置に統合された位置と同じラベルを持つ請求項３又は請求項４記載の経路グラフ生成方法。
【請求項６】
前記コンピュータが、
前記移動体の異なる時刻における位置について、近接距離基準を満たす代表位置が存在しない場合、又は近接距離基準を満たす代表位置のうち、同じエリアに属する代表位置が存在しない場合、該位置を新たな代表位置とする
処理を実行することを特徴とする請求項１〜請求項５のいずれか１項記載の経路グラフ生成方法。
【請求項７】
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する経路グラフ生成装置であって、
近接距離基準を満たす複数の位置のそれぞれが、設定された同じエリア内に属するか否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御する統合部と、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する生成部と、
を含む経路グラフ生成装置。
【請求項８】
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する処理をコンピュータに実行させる経路グラフ生成プログラムにおいて、
近接距離基準を満たす複数の位置のそれぞれが、設定された同じエリア内に属するか否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御し、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する、
ことを前記コンピュータに実行させることを特徴とする経路グラフ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路グラフ生成方法、経路グラフ生成装置、及び経路グラフ生成プログラムに関する。
【背景技術】
【０００２】
ＧＰＳ（Global Positioning System）等のセンサで収集した移動体の軌跡データの分析にあたり、軌跡データから経路グラフを作成する技術が開示されている。例えば、距離の近い軌跡データ同士を統合することにより、経路グラフを作成する技術が提案されている。作成された経路グラフを用いることにより、例えば、経路毎の移動体の流量等を分析することができる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１５−７６０６９公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、例えば、ある２つの移動体について、移動体の各々の軌跡データが示す距離が近い場合であっても、移動体の各々は、物理的又は概念的に異なるエリアに存在する場合がある。この場合、２つの移動体の軌跡データを、同一の経路として統合することにより作成された経路グラフでは、物理的又は概念的に異なるエリアの違いを考慮した分析を行うことができない場合がある、という問題がある。
【０００５】
本発明は、一つの側面として、エリアの違いを考慮した経路グラフを生成することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、一つの態様として、複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する。経路グラフの生成において、近接距離基準を満たす複数の位置のそれぞれが、設定された同じエリア内に属するか否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御する。そして、前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する。
【発明の効果】
【０００７】
一つの側面として、エリアの違いを考慮した経路グラフを生成することができる、という効果を有する。
【図面の簡単な説明】
【０００８】
【図１】本実施形態に係る経路グラフ生成装置の概略構成を示す機能ブロック図である。
【図２】エリアの違いを考慮しない場合における、経路グラフの生成を説明するための図である。
【図３】エリアの違いを考慮しない場合における、軌跡データの経路グラフへの統合を説明するための図である。
【図４】軌跡データが示す軌跡の一例を示す概略図である。
【図５】軌跡データ集合の一例を示す図である。
【図６】経路グラフの一例を示す図である。
【図７】経路グラフのデータ構造の一例を示す図である。
【図８】本実施形態に係る経路グラフ生成装置として機能するコンピュータの概略構成を示すブロック図である。
【図９】本実施形態における経路グラフ生成処理の一例を示すフローチャートである。
【図１０】経路グラフ更新処理の一例を示すフローチャートである。
【図１１】軌跡データｔ１の経路グラフへの統合を説明するための図である。
【図１２】軌跡データｔ２の経路グラフへの統合を説明するための図である。
【図１３】軌跡データｔ３の経路グラフへの統合を説明するための図である。
【図１４】軌跡データｔ４の経路グラフへの統合を説明するための図である。
【図１５】軌跡データｔ５の経路グラフへの統合を説明するための図である。
【図１６】軌跡データｔ６の経路グラフへの統合を説明するための図である。
【発明を実施するための形態】
【０００９】
まず、実施形態の詳細を説明する前に、経路グラフを生成する際に、エリアの違いを考慮せずに経路グラフを生成する場合の問題点について説明する。
【００１０】
図２に、複数の軌跡データ１２２について、距離の近い軌跡データ同士を統合して、経路グラフ１２４を作成する例を概略的に示す。図２左図に示すように、軌跡データ１２２の各々は、所定時間間隔でＧＰＳ（Global Positioning System）等のセンサにより観測された移動体の位置（観測点１２３、図２中の×印）の系列であり、移動体が移動した軌跡を表すデータである。また、図２右図に示すように、経路グラフは、複数のノード１２５とノード間を連結するエッジ１２６とで表されるグラフである。図２の例では、複数の軌跡データ１２２の破線で示す部分が、経路グラフ１２４において一点破線で示す部分のように統合されている。
【００１１】
ここで、図３左図に示すように、複数の軌跡データ１２２の各々が、駅の改札内のエリア及び改札外のエリアに混在している場合を考える。例えば、改札外のエリアであって、改札内のエリアに隣接する位置を移動する移動体の軌跡データ１２２Ａを、その他の軌跡データを統合することにより生成した経路グラフ１２４に統合するとする。軌跡データ１２２を経路グラフ１２４に統合する場合には、軌跡データ１２２との距離が近い経路グラフ１２４上の経路に統合するものとする。この場合において、距離の近さだけで、軌跡データ１２２を経路グラフ１２４に統合してしまうと、図３右図に示すように、改札外の軌跡データ１２２Ａが、経路グラフ１２４のうち、改札内の経路を表す部分に統合されてしまう。このように生成された経路グラフ１２４では、改札内又は改札外での人の流れや、改札を通過する人数等を正確に分析することができない。
【００１２】
そこで、以下の実施形態では、エリアの違いを考慮した経路グラフを生成する。
【００１３】
以下、図面を参照して、本発明に関する実施形態の一例を詳細に説明する。なお、本実施形態では、エリアの違いの一例として、図３の例と同様に、駅の改札内のエリアと改札外のエリアとの違いを考慮した経路グラフを生成する場合を例に説明する。
【００１４】
図１に示すように、本実施形態に係る経路グラフ生成装置１０は、軌跡データ集合２１を入力として受け付け、軌跡データ集合２１に含まれる軌跡データの各々を統合することにより経路グラフ２４を生成して、出力する。
【００１５】
軌跡データ集合２１は、例えば、図４に概略的に示す軌跡を表す軌跡データ２２の集合である。軌跡データ２２の各々は、移動体の位置を観測するセンサにより、所定時間間隔で観測された移動体の位置を示す観測データの系列である。本実施形態では、駅の改札内及び改札外の人の移動を表す軌跡データを扱うため、センサは、例えば、人が保持する携帯電話、スマートフォン等の端末に搭載されたＧＰＳ等とすることができる。
【００１６】
観測データには、センサを識別するセンサＩＤと、観測された位置（観測点２３、図４中の×印）毎の緯度及び経度で示される位置データ（ｘ座標及びｙ座標）と、観測時刻とが含まれる。軌跡データ２２は、複数の観測データをセンサＩＤ毎に抽出し、各観測データに含まれる観測点２３を、観測時刻に基づいて時系列に並べたものである。なお、センサＩＤが同一であっても、観測点２３間の観測時刻が所定時間以上離れている場合には、その箇所で軌跡データを分割する。この場合、センサＩＤに通し番号を付加するなどして、軌跡データを一意に識別可能な軌跡ＩＤを、軌跡データ毎に付与する。図４の例では、ｔ１、ｔ２、ｔ３、ｔ４、ｔ５、及びｔ６の各々が各軌跡データ２２の軌跡ＩＤであるものとする。なお、以下では、軌跡ＩＤがｔｉの軌跡データ２２を、「軌跡データｔｉ」とも表記する。
【００１７】
さらに、本実施形態における軌跡データ２２は、観測点２３毎に、その観測点２３が示す位置が改札内か改札外かを示すラベルが付与されている。図４の例では、改札内の観測点２３を網掛けの×印で表し、改札外の観測点２３を白抜きの×印で表している。観測点２３へのラベルの付与方法は特に限定されない。例えば、観測点２３を示す観測データに含まれる位置データを用いて、その観測点２３が、予め定めた改札内のエリア及び改札外のエリアのいずれに属するかを判定し、判定結果をラベルとして観測点２３に付与することができる。
【００１８】
例えば、軌跡データｔｉに含まれる観測点２３が、Ｐｉ１、Ｐｉ２、・・・、Ｐｉｊ、・・・、ＰｉＪ（Ｊは軌跡データｔｉに含まれる観測点２３の数）であるとする。この場合、軌跡データｔｉは、ｔｉ＝｛Ｐｉ１，Ｐｉ２，・・・，Ｐｉｊ，・・・，Ｐｉｋ｝と表すことができる。また、各観測点２３を示す観測データには、その観測点２３が含まれる軌跡データ２２の軌跡ＩＤと、観測点２３の識別情報である観測点ＩＤと、位置データ（ｘ座標及びｙ座標）と、観測時刻と、ラベルの情報とが含まれる。例えば、軌跡データｔｉに含まれる観測点Ｐｉｊの観測データは、Ｐｉｊ＝｛ｔｉ，Ｐｉｊ，（ｘｉｊ，ｙｉｊ），ｓｉｊ，０｝と表すことができる。なお、（ｘｉｊ，ｙｉｊ）は、観測点Ｐｉｊの位置データ、ｓｉｊは、観測点Ｐｉｊの観測時刻である。また、この例では、観測点２３が示す位置が改札内か改札外かを示すラベルを、「０＝改札内」及び「１＝改札外」としている。また、以下では、観測点ＩＤがＰｉｊの観測点を「観測点Ｐｉｊ」とも表記する。軌跡データ集合２１は、上記のデータ構造を用いて、例えば、図５に示すように表すことができる。
【００１９】
経路グラフ２４は、後述するように、複数の軌跡データ２２を統合して生成されるものであり、図６に示すように、複数のノード２５と、ノード２５間を連結するエッジ２６とで表される。なお、ノード２５は、本発明の代表位置の一例である。本実施形態では、各ノード２５には、軌跡データ２２の各観測点２３と同様に、そのノード２５が表す位置が改札内か改札外かを示すラベルが付与される（詳細は後述）。図６の例では、改札内のノード２５を網掛けの丸印で表し、改札外のノード２５を白抜きの丸印で表している。また、エッジ２６には、同一のラベルが付与されたノード２５間を連結する通常エッジ２６Ａと、異なるラベルが付与されたノード２５間を連結する異種間エッジ２６Ｂとの２種類がある。図６では、通常エッジ２６Ａを一重線、異種間エッジ２６Ｂを二重線で表している。なお、２種類のエッジを区別なく説明する場合には、単に「エッジ２６」と表記する。
【００２０】
経路グラフ２４のデータ構造は、図７に示すように、経路グラフ２４に含まれるノード２５を示すノード情報の集合と、エッジ２６を示すエッジ情報の集合とで表すことができる。ノード情報は、例えば、各ノード２５の識別情報（ノードＩＤ）と、各ノード２５の位置データ（ｘ座標及びｙ座標）と、ラベルの情報とを含む。また、エッジ情報は、各エッジ２６の識別情報（エッジＩＤ）と、そのエッジ２６で連結されているノード２５のノードＩＤを「＿（アンダーバー）」で接続した表記で表される連結ノードの情報と、エッジ２６の種類の情報とを含む。なお、図７の例では、エッジ２６の種類を、「０＝通常エッジ」及び「１＝異種間エッジ」としている。また、以下では、ノードＩＤがＮｉのノードを「ノードＮｉ」とも表記する。
【００２１】
また、経路グラフ生成装置１０は、機能的には、受信部１１と、統合部１２と、生成部１３と、出力部１４とを含む。
【００２２】
受信部１１は、経路グラフ生成装置１０に入力された軌跡データ集合２１に含まれる軌跡データ２２の各々を、統合部１２へ受け渡す。
【００２３】
統合部１２は、軌跡データ２２の各々に含まれる観測点２３の各々が、他の軌跡データ２２に含まれる観測点２３と近接距離基準を満たすか否かを判定する。近接距離基準を満たす場合とは、観測点２３間の距離が、予め定められた距離ε以下の場合であることをいう。また、統合部１２は、近接距離基準を満たす観測点２３の各々に付与されているラベルが同じ場合、すなわち、観測点２３が示す位置が同じエリア（改札内又は改札外）に属する場合に、それら複数の観測点２３を同一のノード２５に統合する。
【００２４】
本実施形態では、現段階で生成されている経路グラフ２４に、１つずつ軌跡データを統合させ、軌跡データ集合２１に含まれる軌跡データ２２を全て統合し終えた段階での経路グラフ２４を、最終的な経路グラフ２４として出力する。したがって、上記の「複数の観測点２３を同一のノード２５に統合する」ことは、本実施形態では、観測点２３を、近接距離基準を満たし、かつラベルが同じノード２５に統合することに相当する。
【００２５】
統合部１２は、軌跡データ２２の各々に含まれる観測点２３の各々と、近接距離基準を満たすノード２５が存在しない場合、又は近接距離基準を満たすが、同じラベルのノード２５が存在しない場合には、その観測点２３に対応する新しいノード２５を生成する。また、統合部１２は、生成したノード２５に、対応する観測点２３と同じラベルを付与する。統合部１２は、生成したノード２５を示すノード情報を、例えば、図７に示すような、経路グラフ２４のデータ構造に追加する。
【００２６】
生成部１３は、統合部１２によりノード２５が生成された場合に、ノード２５間をエッジ２６で連結して、経路グラフ２４を生成する。具体的には、生成部１３は、統合部１２により新たに生成されたノード２５と、そのノード２５に対応する観測点２３の直前の観測点２３に対応するノード２５とを、エッジ２６で連結する。この際、生成部１３は、新たに生成されたノード２５と、直前の観測点２３に対応するノード２５とで、ノード２５に付与されているラベルが同じ場合には、通常エッジ２６Ａで連結する。一方、生成部１３は、新たに生成されたノード２５と、直前の観測点２３に対応するノード２５とで、ノード２５に付与されているラベルが異なる場合には、異種間エッジ２６Ｂで連結する。
【００２７】
統合部１２は、ノード２５間を連結したエッジ２６を示すエッジ情報を、例えば、図７に示すような、経路グラフ２４のデータ構造に追加する。
【００２８】
これにより、改札内に属する観測点２３で構成される軌跡データ２２の断片は、経路グラフ２４のうち、改札内の経路を表す部分に対応付けられる。また、改札外に属する観測点２３で構成される軌跡データ２２の断片は、経路グラフ２４のうち、改札外の経路を表す部分に対応付けられる。すなわち、経路グラフ２４において、改札内の経路と改札外の経路とを区別することができる。また、軌跡データ２２が改札内外をまたぐ場合でも、経路グラフ２４への対応付けを途中で切らすことなく、改札内の経路と改札外の経路とに対して、連続して対応付けることができる。したがって、改札内の経路と改札外の経路とが連結された経路グラフ２４を生成することができる。
【００２９】
出力部１４は、最終的に生成された経路グラフ２４を出力する。
【００３０】
経路グラフ生成装置１０は、例えば、図８に示すコンピュータ４０で実現することができる。コンピュータ４０はＣＰＵ４１、一時記憶領域としてのメモリ４２、及び不揮発性の記憶部４３を備える。また、コンピュータ４０は、表示装置及び入力装置等の入出力装置４８が接続される入出力インターフェース（Ｉ／Ｆ）４４を備える。また、コンピュータ４０は、記録媒体４９に対するデータの読み込みと書き込みとを制御するｒｅａｄ／ｗｒｉｔｅ（Ｒ／Ｗ）部４５、及びインターネット等のネットワークに接続されるネットワークＩ／Ｆ４６を備える。ＣＰＵ４１、メモリ４２、記憶部４３、入出力Ｉ／Ｆ４４、Ｒ／Ｗ部４５、及びネットワークＩ／Ｆ４６は、バス４７を介して互いに接続される。
【００３１】
記憶部４３は、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（solid state drive）、フラッシュメモリ等によって実現できる。記憶媒体としての記憶部４３には、コンピュータ４０を経路グラフ生成装置１０として機能させるための経路グラフ生成プログラム５０が記憶される。また、記憶部４３は、例えば、図７に示すようなノード情報及びエッジ情報を含む経路グラフ２４の情報が記憶される経路グラフ情報記憶領域６０を有する。
【００３２】
ＣＰＵ４１は、経路グラフ生成プログラム５０を記憶部４３から読み出してメモリ４２に展開し、経路グラフ生成プログラム５０が有するプロセスを順次実行する。また、ＣＰＵ４１は、経路グラフ情報記憶領域６０からノード情報及びエッジ情報を読み出し、経路グラフ２４をメモリ４２に展開する。
【００３３】
経路グラフ生成プログラム５０は、受信プロセス５１と、統合プロセス５２と、生成プロセス５３と、出力プロセス５４とを有する。ＣＰＵ４１は、受信プロセス５１を実行することで、図１に示す受信部１１として動作する。また、ＣＰＵ４１は、統合プロセス５２を実行することで、図１に示す統合部１２として動作する。また、ＣＰＵ４１は、生成プロセス５３を実行することで、図１に示す生成部１３として動作する。また、ＣＰＵ４１は、出力プロセス５４を実行することで、図１に示す出力部１４として動作する。これにより、経路グラフ生成プログラム５０を実行したコンピュータ４０が、経路グラフ生成装置１０として機能することになる。
【００３４】
なお、経路グラフ生成プログラム５０により実現される機能は、例えば半導体集積回路、より詳しくはＡＳＩＣ（Application Specific Integrated Circuit）等で実現することも可能である。
【００３５】
次に、本実施形態に係る経路グラフ生成装置１０の作用について説明する。経路グラフ生成装置１０に軌跡データ集合２１が入力されると、経路グラフ生成装置１０において、図９に示す経路グラフ生成処理が実行される。
【００３６】
図９に示す経路グラフ生成処理のステップＳ１０で、受信部１１が、現段階で生成されている経路グラフ２４を示す経路グラフＧとして、空のグラフを設定する。
【００３７】
次に、ステップＳ２０で、受信部１１が、入力された軌跡データ集合２１に含まれる軌跡データｔｉの全てについて、経路グラフＧへ統合する処理が終了したか否かを判定する。未処理の軌跡データｔｉが存在する場合には、処理はステップＳ３０へ移行する。ステップＳ３０では、受信部１１が、軌跡データ集合２１から、未処理の軌跡データｔｉを１つ選択して、統合部１２へ受け渡す。そして、次のステップＳ４０で、選択された軌跡データｔｉについて、図１０に詳細を示す経路グラフ更新処理が実行される。
【００３８】
図１０に示す経路グラフ更新処理のステップＳ４１で、統合部１２が、直前に処理した観測点２３のラベルを示す変数Ｌｐに「ＮＵＬＬ」を設定する。また、統合部１２が、処理対象の観測点２３を示す変数ｎに、軌跡データｔｉの最初の観測点Ｐｉ１（観測時刻が最も古い観測点２３）を設定する。さらに、統合部１２が、処理対象の観測点２３のラベルを示す変数Ｌｃに、ｎに設定した観測点（以下、「観測点ｎ」と表記する）のラベルを設定する。
【００３９】
次に、ステップＳ４２で、統合部１２が、ＬｃとＬｐとが等しいか否か、すなわち、処理対象の観測点ｎと、直前に処理した観測点２３（以下、「観測点ｎ’」と表記する）とで、ラベルが同一か否かを判定する。Ｌｃ＝Ｌｐの場合、処理はステップＳ４３へ移行し、Ｌｃ≠Ｌｐの場合、処理はステップＳ４８へ移行する。
【００４０】
ステップＳ４３では、統合部１２が、観測点ｎから距離ε以内にラベルがＬｃのノード２５が存在するか否かを判定し、存在する場合には、処理はステップＳ４４へ移行し、存在しない場合には、処理はステップＳ４７へ移行する。
【００４１】
ステップＳ４４では、生成部１３が、上記ステップＳ４３で存在すると判定されたラベルＬｃのノード２５のうち、観測点ｎに１番近いノード２５を、ノードＮに設定する。また、生成部１３が、直前に処理した観測点ｎ’に対応するノード２５を、ノードＮ’に設定する。
【００４２】
次に、ステップＳ４５で、生成部１３が、ノードＮとノードＮ’とが同一でなく、かつノードＮとノードＮ’とを連結するエッジ２６が存在しないか否かを判定する。肯定判定の場合、処理はステップＳ４６へ移行し、生成部１３が、ノードＮとノードＮ’とを、通常エッジ２６Ａで連結する。一方、ノードＮとノードＮ’とが同一の場合、又は、ノードＮとノードＮ’とが既にエッジ２６で連結されている場合には、さらにエッジで連結する必要はないため、ステップＳ４６の処理はスキップされる。
【００４３】
ステップＳ４７では、生成部１３が、観測点ｎを示す観測データに含まれる位置データが示す位置に、ラベルＬｃのノードＮを新規に作成する。また、生成部１３が、直前に処理した観測点ｎ’に対応するノード２５を、ノードＮ’に設定する。そして、処理はステップＳ４６へ移行し、生成部１３が、ノードＮとノードＮ’とを、通常エッジ２６Ａで連結する。
【００４４】
一方、Ｌｃ≠Ｌｐと判定されて、処理がステップＳ４８へ移行した場合には、統合部１２が、上記ステップＳ４３と同様に、観測点ｎから距離ε以内にラベルがＬｃのノード２５が存在するか否かを判定する。ラベルがＬｃのノード２５が存在する場合には、処理はステップＳ４９へ移行し、存在しない場合には、処理はステップＳ５２へ移行する。
【００４５】
ステップＳ４９では、生成部１３が、上記ステップＳ４４と同様に、観測点ｎに１番近いノード２５をノードＮに設定し、直前に処理した観測点ｎ’に対応するノード２５をノードＮ’に設定する。
【００４６】
次に、ステップＳ５０で、生成部１３が、ノードＮとノードＮ’とを連結するエッジ２６が存在しないか否かを判定する。エッジが存在しない場合、処理はステップＳ５１へ移行し、生成部１３が、ノードＮとノードＮ’とを、異種間エッジ２６Ｂで連結する。一方、ノードＮとノードＮ’とが既にエッジ２６で連結されている場合には、ステップＳ５１の処理はスキップされる。
【００４７】
ステップＳ５２では、生成部１３は、上記ステップＳ４７と同様に、観測点ｎの位置に、ラベルＬｃのノードＮを新規に作成し、直前に処理した観測点ｎ’に対応するノード２５をノードＮ’に設定する。そして、処理はステップＳ５１へ移行し、生成部１３が、ノードＮとノードＮ’とを、異種間エッジ２６Ｂで連結する。
【００４８】
次に、ステップＳ５３で、統合部１２が、軌跡データｔｉに含まれる全ての観測点について上記の処理が終了したか否かを判定する。未処理の観測点が存在する場合には、処理はステップＳ５４へ移行する。ステップＳ５４では、統合部１２が、現在Ｌｃに設定されているラベルをＬｐに設定し、ｎに、軌跡データｔｉにおける次の観測時刻の観測点Ｐｉｊを設定し、Ｌｃに観測点ｎのラベルを設定する。そして、処理はステップＳ４２に戻る。
【００４９】
軌跡データｔｉに含まれる全ての観測点について上記の処理が終了した場合には、経路グラフ更新処理を終了し、経路グラフ生成処理（図９）に戻る。
【００５０】
図９に示す経路グラフ生成処理のステップＳ２０に戻って、受信部１１が、軌跡データ集合２１に含まれる軌跡データｔｉの全てについて、経路グラフＧへ統合する処理が終了と判定すると、処理はステップＳ６０へ移行する。ステップＳ６０では、出力部１４が、現在の経路グラフＧを、最終的な経路グラフＧ’として出力し、経路グラフ生成処理は終了する。
【００５１】
ここで、上記の経路グラフ生成処理について、図４に示すような、軌跡データｔｉ（ｉ＝１，２，・・・，６）を含む軌跡データ集合２１が入力された場合について、具体的に説明する。なお、以下では、ステップＳ３０において、軌跡データが、ｔ１、ｔ２、ｔ３、ｔ４、ｔ５、ｔ６の順で選択されて、ステップＳ４０の処理が実行される場合について説明する。また、各軌跡データｔｉは、以下に示すような観測点Ｐｉｊの系列で表されるものとする。
【００５２】
ｔ１＝｛Ｐ１１，Ｐ１２，Ｐ１３，Ｐ１４｝
ｔ２＝｛Ｐ２１，Ｐ２２，Ｐ２３，Ｐ２４，Ｐ２５，Ｐ２６｝
ｔ３＝｛Ｐ３１，Ｐ３２，Ｐ３３，Ｐ３４｝
ｔ４＝｛Ｐ４１，Ｐ４２，Ｐ４３，Ｐ４４｝
ｔ５＝｛Ｐ５１，Ｐ５２，Ｐ５３，Ｐ５４，Ｐ５５，Ｐ５６｝
ｔ６＝｛Ｐ６１，Ｐ６２，Ｐ６３，Ｐ６４｝
【００５３】
軌跡データｔ１を経路グラフＧへ統合する段階では、経路グラフＧは空のグラフであるため、図１１に示すように、軌跡データｔ１の各観測点Ｐ１１、Ｐ１２、Ｐ１３、及びＰ１４の位置にノードＮ１、Ｎ２、Ｎ３、及びＮ４が生成される。観測点Ｐ１１、Ｐ１２、及びＰ１３に対応するノードＮ１、Ｎ２、及びＮ３に付与されるラベルは、観測点Ｐ１１、Ｐ１２、及びＰ１３に付与されているラベルと同じく、「改札内」を示すものである。また、観測点Ｐ１４に対応するノードＮ４に付与されるラベルは、観測点Ｐ１４に付与されているラベルと同じく、「改札外」を示すものである。ノードＮ１とノードＮ２との間、及びノードＮ２とノードＮ３との間は、連結するノードのラベルが同じであるため、通常エッジ２６Ａで連結される。一方、ノードＮ３とノードＮ４との間は、連結するノードのラベルが異なるため、異種間エッジ２６Ｂで連結される。軌跡データｔ１を統合した段階での経路グラフＧを、経路グラフＧ１と表記する。
【００５４】
次に、図１２に示すように、経路グラフＧ１に、軌跡データｔ２を統合する。なお、図１２左図では、処理対象の軌跡データを実線で、処理済みの軌跡データを点線で示している。以下の図１３〜図１６も同様である。軌跡データｔ２の各観測点Ｐ２１、Ｐ２２、及びＰ２３は、近接距離基準を満たすノード２５が存在しないため、各観測点Ｐ２１、Ｐ２２、及びＰ２３の位置に、観測点Ｐ２１、Ｐ２２、及びＰ２３と同じラベルのノードＮ５、Ｎ６、及びＮ７が生成される。そして、各ノード間が通常エッジ２６Ａで連結される。次の観測点Ｐ２４は、ノードＮ３と近接距離基準を満たすものとする。しかし、観測点Ｐ２４のラベルは「改札外」、ノードＮ３のラベルは「改札内」で、双方のラベルが異なるため、観測点Ｐ２４はノードＮ３に統合されない。したがって、観測点Ｐ２４の位置に、観測点Ｐ２４と同じラベルのノードＮ８が生成され、直前に処理されたノードＮ７との間が通常エッジ２６Ａで連結される。観測点Ｐ２５及びＰ２６については、対応するノードＮ９及びＮ１０が生成され、通常エッジ２６Ａで連結される。経路グラフＧ１に軌跡データｔ２を統合した段階での経路グラフＧを、経路グラフＧ１２と表記する。
【００５５】
次に、図１３に示すように、経路グラフＧ１２に、軌跡データｔ３を統合する。軌跡データｔ３の観測点Ｐ３１については、対応するノードＮ１１が生成される。次の観測点Ｐ３２は、ノードＮ４と近接距離基準を満たすものとする。また、観測点Ｐ３２のラベルは「改札外」、ノードＮ４のラベルも「改札外」で、双方のラベルが同じであるため、観測点Ｐ３２はノードＮ４に統合される。すなわち、観測点Ｐ３２に対応する新規のノードは生成されない。観測点Ｐ３３及びＰ３４については、対応するノードＮ１２及びＮ１３が生成され、通常エッジ２６Ａで連結される。経路グラフＧ１２に軌跡データｔ３を統合した段階での経路グラフＧを、経路グラフＧ１２３と表記する。
【００５６】
次に、図１４に示すように、経路グラフＧ１２３に、軌跡データｔ４を統合する。軌跡データｔ４の観測点Ｐ４１、Ｐ４２、及びＰ４３については、対応するノードＮ１４、Ｎ１５、及びＮ１６が生成され、通常エッジ２６Ａで連結される。次の観測点Ｐ４４は、ノードＮ１２と近接距離基準を満たし、また、ラベルも同じであるため、ノードＮ１２に統合される。そして、ノードＮ１２と、直前に処理したノードＮ１６との間はまだエッジで連結されておらず、双方のラベルは異なるため、ノードＮ１６とノードＮ１２との間が、異種間エッジ２６Ｂで連結される。経路グラフＧ１２３に軌跡データｔ４を統合した段階での経路グラフＧを、経路グラフＧ１２３４と表記する。
【００５７】
次に、図１５に示すように、経路グラフＧ１２３４に、軌跡データｔ５を統合する。軌跡データｔ５の観測点Ｐ５１、Ｐ５２、及びＰ５３については、ノードＮ５、Ｎ６、Ｎ７とそれぞれ近接距離基準を満たすが、ラベルが異なるため、統合されない。したがって、観測点Ｐ５１、Ｐ５２、及びＰ５３の各々に対応するノードＮ１７、Ｎ１８、及びＮ１９が生成され、通常エッジ２６Ａで連結される。次の観測点Ｐ５４は、近接距離基準を満たし、かつラベルが同じノードＮ３に統合される。そして、ノードＮ１９−Ｎ３間が通常エッジ２６Ａで連結される。次の観測点Ｐ５５についても、近接距離基準を満たし、かつラベルが同じノードＮ１６に統合され、ノードＮ３−Ｎ１６間が通常エッジ２６Ａで連結される。次の観測点Ｐ５６は、近接距離基準を満たし、かつラベルが同じノードＮ１０に統合され、ノードＮ１０と、直前に処理されたノードＮ１６とはラベルが異なるため、ノードＮ１６−Ｎ１０間が異種間エッジ２６Ｂで連結される。経路グラフＧ１２３４に軌跡データｔ５を統合した段階での経路グラフＧを、経路グラフＧ１２３４５と表記する。
【００５８】
次に、図１６に示すように、経路グラフＧ１２３４５に、軌跡データｔ６を統合する。軌跡データｔ６の観測点Ｐ６１、Ｐ６２、Ｐ６３、及びＰ６４について、近接距離基準を満たし、かつラベルが同じノードＮ１４、Ｎ１５、Ｎ３、及びＮ４に統合される。そして、ノード間がエッジで連結されていないノードＮ１５−Ｎ３間が新たに通常エッジ２６Ａで連結される。経路グラフＧ１２３４５に軌跡データｔ６を統合した段階での経路グラフＧを、経路グラフＧ１２３４５６と表記する。この経路グラフＧ１２３４５６が、最終的に出力される経路グラフＧ’となる。
【００５９】
以上説明したように、本実施形態に係る経路グラフ生成装置によれば、軌跡データに含まれる各観測点に、その観測点が示す位置が属するエリアに応じたラベルを付与しておく。そして、軌跡データを経路グラフに統合する際に、各観測点を、近接距離基準を満たし、かつラベルが同じノードに統合する。ノードには、そのノードに統合された観測点に付与されていたラベルと同じラベルを付与しておく。これにより、エリアの違いを考慮した経路グラフを生成することができる。
【００６０】
また、異なるラベルが付与されたノード間を、同じラベルが付与されたノード間を連結するエッジとは異なるエッジで連結することで、異なるエリアにまたがる軌跡データであっても、途切れることなく経路グラフに対応付けることができる。
【００６１】
上記のように生成された経路グラフに軌跡データをマッチングして分析することにより、改札内及び改札外の各々のエリア内や、改札を通過する人の流れや流量などを分析することができる。また、１番左の改札を通過した場合は、改札通過後、直進する人よりも左へ曲がる人の方が多い、など、改札通過前後の細かな人の流れなども分析することができる。なお、マッチングに用いる軌跡データは、経路グラフの生成に利用した軌跡データであってもよいし、別の軌跡データであってもよい。経路グラフへの軌跡データのマッチングとは、軌跡データに含まれる各観測点を、距離の近さに基づいて、経路グラフのいずれかのノードに対応させ、軌跡データが示す軌跡を、経路グラフに含まれるいずれの経路に対応させることである。
【００６２】
なお、経路グラフを用いて移動体の流量を求める場合には、経路グラフに軌跡データをマッチングさせる際に、経路グラフの各ノードに対応付けられた観測点の数に基づいて求めればよい。
【００６３】
また、経路グラフを生成する際に、各ノードに、そのノードに統合された観測点の数を、流量の情報として保持させてもよい。さらに、経路グラフを画面表示等する際には、エッジの両端のノードが保持する流量の情報に応じて、そのノード間のエッジの太さ、色、線の種類等を変更するようにしてもよい。
【００６４】
また、上記実施形態では、エリアの違いとして、改札内のエリアと改札外のエリアとを区別する場合について説明したが、これに限定されない。例えば、展示会場における各ブースや、デパートにおける各店舗等を、それぞれのエリアとしてもよい。
【００６５】
さらに、物理的な（二次元平面上での）エリアの違いに限定されず、概念的なエリアの違い、例えば、車や電車等の中のエリアと、外のエリアとの違いを区別するようにしてもよい。この場合、例えば、軌跡データの各観測点に、徒歩で移動中であることを示すラベルや、車等で移動中であることを示すラベルを付与すればよい。ラベルの付与の方法としては、例えば、軌跡データの各観測点間の距離及び観測時刻から、観測点毎に移動体の速度を求め、所定数の観測点の速度の移動平均などから、徒歩か車移動かを判定して、ラベルを付与することができる。また、人がタクシーに乗車した場合などは、人が保持する携帯端末に搭載されたＧＰＳで観測された軌跡データと、その人が乗車したタクシーのカーナビゲーションシステムに搭載されたＧＰＳで観測された軌跡データとが、ほぼ重なることになる。このような情報を利用して、人の軌跡データに対して、徒歩か車移動かのラベルを付与することもできる。また、観測データに移動手段の情報を付与できるように、ＧＰＳ等のセンサを設定してもよい。
【００６６】
このような概念的なエリアの違いを区別した経路グラフを生成した場合には、移動手段の切り替わりを考慮した細かな経路分析を行うことができる。例えば、人がタクシーに乗車するまでの移動経路や、タクシー乗車後の移動経路などを分析することができる。
【００６７】
また、ラベルにより区別する情報としては、エリアや移動手段の他にも、各観測点の観測時刻が属する時間帯、移動体の属性（人の場合は性別、車の場合は車種等）などを適用してもよい。
【００６８】
また、上記では、経路グラフ生成プログラム５０が記憶部４３に予め記憶（インストール）されている態様を説明したが、これに限定されない。開示の技術に係るプログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の記録媒体に記録された形態で提供することも可能である。
【００６９】
以上の実施形態に関し、更に以下の付記を開示する。
【００７０】
（付記１）
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する経路グラフ生成方法において、
近接距離基準を満たす複数の位置のそれぞれが、設定された同じエリア内に属するか否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御し、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する、
ことを特徴とする経路グラフ生成方法。
【００７１】
（付記２）
前記近接距離基準を満たす前記複数の位置のそれぞれが、異なるエリアに属する場合に、前記複数の位置を１つの代表位置に統合せずに経路グラフを生成するように制御する、付記１記載の経路グラフ生成方法。
【００７２】
（付記３）
前記移動体の異なる時刻における位置のうち、連続する２時刻の各々における一方の位置が、第１のエリアに属する代表位置と近接距離基準を満たし、他方の位置が、前記第１のエリアとは異なる第２のエリアに属する代表位置と近接距離基準を満たす場合、前記第１のエリアに属する代表位置と、前記第２のエリアに属する代表位置とを、異なるエリアに属する代表位置間の連結であることを示す情報を付加して連結する付記１又は付記２記載の経路グラフ生成方法。
【００７３】
（付記４）
前記経路グラフは、前記代表位置を示すノードと、該ノード間を連結するエッジとで表され、前記第１のエリアに属する代表位置と、前記第２のエリアに属する代表位置との間は、同じエリアに属する代表位置間を連結する第１のエッジとは異なる第２のエッジで連結される付記３記載の経路グラフ生成方法。
【００７４】
（付記５）
前記複数の移動体の異なる時刻における位置の各々は、該位置が属するエリアに応じたラベルを持ち、前記代表位置は、該代表位置に統合された位置と同じラベルを持つ付記３又は付記４記載の経路グラフ生成方法。
【００７５】
（付記６）
前記移動体の異なる時刻における位置について、近接距離基準を満たす代表位置が存在しない場合、又は近接距離基準を満たす代表位置のうち、同じエリアに属する代表位置が存在しない場合、該位置を新たな代表位置とする付記１〜付記５のいずれか１項記載の経路グラフ生成方法。
【００７６】
（付記７）
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する経路グラフ生成方法において、
前記複数の移動体の異なる時刻における位置の各々は、前記移動体の属性、前記時刻を含む時間帯、及び前記位置の少なくとも１つに応じたラベルを持ち、
近接距離基準を満たす複数の位置のそれぞれが持つ前記ラベルが同一か否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御し、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する、
ことを特徴とする経路グラフ生成方法。
【００７７】
（付記８）
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する経路グラフ生成装置であって、
近接距離基準を満たす複数の位置のそれぞれが、設定された同じエリア内に属するか否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御する統合部と、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する生成部と、
を含む経路グラフ生成装置。
【００７８】
（付記９）
前記統合部は、前記近接距離基準を満たす前記複数の位置のそれぞれが、異なるエリアに属する場合に、前記複数の位置を１つの代表位置に統合せずに前記生成部に経路グラフを生成させる付記８記載の経路グラフ生成装置。
【００７９】
（付記１０）
前記生成部は、前記移動体の異なる時刻における位置のうち、連続する２時刻の各々における一方の位置が、第１のエリアに属する代表位置と近接距離基準を満たし、他方の位置が、前記第１のエリアとは異なる第２のエリアに属する代表位置と近接距離基準を満たす場合、前記第１のエリアに属する代表位置と、前記第２のエリアに属する代表位置とを、異なるエリアに属する代表位置間の連結であることを示す情報を付加して連結する付記８又は付記９記載の経路グラフ生成装置。
【００８０】
（付記１１）
前記経路グラフは、前記代表位置を示すノードと、該ノード間を連結するエッジとで表され、前記第１のエリアに属する代表位置と、前記第２のエリアに属する代表位置との間は、同じエリアに属する代表位置間を連結する第１のエッジとは異なる第２のエッジで連結される付記１０記載の経路グラフ生成装置。
【００８１】
（付記１２）
前記複数の移動体の異なる時刻における位置の各々は、該位置が属するエリアに応じたラベルを持ち、前記代表位置は、該代表位置に統合された位置と同じラベルを持つ付記１０又は付記１１記載の経路グラフ生成装置。
【００８２】
（付記１３）
前記生成部は、前記移動体の異なる時刻における位置について、近接距離基準を満たす代表位置が存在しない場合、又は近接距離基準を満たす代表位置のうち、同じエリアに属する代表位置が存在しない場合、該位置を新たな代表位置とする付記８〜付記１２のいずれか１項記載の経路グラフ生成装置。
【００８３】
（付記１４）
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する経路グラフ生成装置であって、
前記複数の移動体の異なる時刻における位置の各々は、前記移動体の属性、前記時刻を含む時間帯、及び前記位置の少なくとも１つに応じたラベルを持ち、
近接距離基準を満たす複数の位置のそれぞれが持つ前記ラベルが同一か否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御する統合部と、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する生成部と、
を含む経路グラフ生成装置。
【００８４】
（付記１５）
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する処理をコンピュータに実行させる経路グラフ生成プログラムにおいて、
近接距離基準を満たす複数の位置のそれぞれが、設定された同じエリア内に属するか否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御し、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する、
ことを前記コンピュータに実行させることを特徴とする経路グラフ生成プログラム。
【００８５】
（付記１６）
前記近接距離基準を満たす前記複数の位置のそれぞれが、異なるエリアに属する場合に、前記複数の位置を１つの代表位置に統合せずに経路グラフを生成するように制御する、付記１５記載の経路グラフ生成プログラム。
【００８６】
（付記１７）
前記移動体の異なる時刻における位置のうち、連続する２時刻の各々における一方の位置が、第１のエリアに属する代表位置と近接距離基準を満たし、他方の位置が、前記第１のエリアとは異なる第２のエリアに属する代表位置と近接距離基準を満たす場合、前記第１のエリアに属する代表位置と、前記第２のエリアに属する代表位置とを、異なるエリアに属する代表位置間の連結であることを示す情報を付加して連結する付記１５又は付記１６記載の経路グラフ生成プログラム。
【００８７】
（付記１８）
前記経路グラフは、前記代表位置を示すノードと、該ノード間を連結するエッジとで表され、前記第１のエリアに属する代表位置と、前記第２のエリアに属する代表位置との間は、同じエリアに属する代表位置間を連結する第１のエッジとは異なる第２のエッジで連結される付記１７記載の経路グラフ生成プログラム。
【００８８】
（付記１９）
前記複数の移動体の異なる時刻における位置の各々は、該位置が属するエリアに応じたラベルを持ち、前記代表位置は、該代表位置に統合された位置と同じラベルを持つ付記１７又は付記１８記載の経路グラフ生成プログラム。
【００８９】
（付記２０）
前記移動体の異なる時刻における位置について、近接距離基準を満たす代表位置が存在しない場合、又は近接距離基準を満たす代表位置のうち、同じエリアに属する代表位置が存在しない場合、該位置を新たな代表位置とする付記１５〜付記１９のいずれか１項記載の経路グラフ生成プログラム。
【００９０】
（付記２１）
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する処理をコンピュータに実行させる経路グラフ生成プログラムにおいて、
前記複数の移動体の異なる時刻における位置の各々は、前記移動体の属性、前記時刻を含む時間帯、及び前記位置の少なくとも１つに応じたラベルを持ち、
近接距離基準を満たす複数の位置のそれぞれが持つ前記ラベルが同一か否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御し、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する、
ことを前記コンピュータに実行させることを特徴とする経路グラフ生成プログラム。
【００９１】
（付記２２）
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する処理をコンピュータに実行させる経路グラフ生成プログラムにおいて、
近接距離基準を満たす複数の位置のそれぞれが、設定された同じエリア内に属するか否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御し、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する、
ことを前記コンピュータに実行させることを特徴とする経路グラフ生成プログラムを記憶した記憶媒体。
【００９２】
（付記２３）
複数の移動体の異なる時刻における位置に基づいて、経路グラフを生成する処理をコンピュータに実行させる経路グラフ生成プログラムにおいて、
前記複数の移動体の異なる時刻における位置の各々は、前記移動体の属性、前記時刻を含む時間帯、及び前記位置の少なくとも１つに応じたラベルを持ち、
近接距離基準を満たす複数の位置のそれぞれが持つ前記ラベルが同一か否かに応じて、前記複数の位置を１つの代表位置に統合するか否か制御し、
前記複数の位置が前記代表位置に統合された場合は、該代表位置を用いて経路グラフを生成する、
ことを前記コンピュータに実行させることを特徴とする経路グラフ生成プログラムを記憶した記憶媒体。
【符号の説明】
【００９３】
１０   経路グラフ生成装置
１１   受信部
１２   統合部
１３   生成部
１４   出力部
２２   軌跡データ
２４   経路グラフ
２６Ａ 通常エッジ
２６Ｂ 異種間エッジ
４０   コンピュータ
４１   ＣＰＵ
４２   メモリ
４３   記憶部
５０   経路グラフ生成プログラム
【図１】
0006572672.tif 000002
【図２】
0006572672.tif 000003
【図３】
0006572672.tif 000004
【図４】
0006572672.tif 000005
【図５】
0006572672.tif 000006
【図６】
0006572672.tif 000007
【図７】
0006572672.tif 000008
【図８】
0006572672.tif 000009
【図９】
0006572672.tif 000010
【図１０】
0006572672.tif 000011
【図１１】
0006572672.tif 000012
【図１２】
0006572672.tif 000013
【図１３】
0006572672.tif 000014
【図１４】
0006572672.tif 000015
【図１５】
0006572672.tif 000016
【図１６】
0006572672.tif 000017