(57)【要約】【課題】異なる測定環境間で軌跡データの比較や分類を可能にすること。【解決手段】軌跡データ解析装置は、測定環境で取得された２次元の軌跡データを交点で立体交差させることで３次元の曲線に変換し、この曲線に基づく結び目を出力する結び目作成器４０３と、上記結び目の不変量を計算する結び目不変量計算器４０４と、上記測定環境で取得された複数の軌跡データについて、結び目不変量計算器４０４で計算された不変量を、データベース４０６に予め定義される複数種類の素な結び目の集合に分解し、素な結び目の出現頻度分布を求め、この出現頻度分布をもとに上記測定環境における軌跡データの特徴ベクトルを作成する特徴解析器４０５とを備える。【選択図】図４
2014170276.tif 000002
【特許請求の範囲】
【請求項１】
測定環境で取得された２次元の軌跡データを交点で立体交差させることで３次元の曲線に変換し、前記曲線に基づく結び目を出力する結び目作成手段と、
前記結び目の不変量を計算する結び目不変量計算手段と、
前記測定環境で取得された複数の軌跡データについて、前記結び目不変量計算手段で計算された不変量を、予め定義した複数種類の素な結び目の集合に分解し、素な結び目の出現頻度分布を求め、前記出現頻度分布をもとに前記測定環境における軌跡データの特徴ベクトルを作成する特徴解析手段と
を具備することを特徴とする軌跡データ解析装置。
【請求項２】
前記結び目作成手段は、前記曲線の始点と終点とが一致しない場合に、前記始点と終点とを結ぶことを特徴とする請求項１に記載の軌跡データ解析装置。
【請求項３】
前記結び目作成手段は、前記曲線に重複ルートが存在する場合に、前記曲線から重複ルートを解消することを特徴とする請求項１又は２に記載の軌跡データ解析装置。
【請求項４】
前記特徴解析手段は、前記出現頻度分布から素な結び目の交点数毎の出現頻度分布を求め、前記交点数毎の出現頻度分布をもとに前記特徴ベクトルを作成することを特徴とする請求項１乃至３のいずれか１項に記載の軌跡データ解析装置。
【請求項５】
情報処理装置が実行する軌跡データ解析方法であって、
測定環境で取得された２次元の軌跡データを交点で立体交差させることで３次元の曲線に変換し、前記曲線に基づく結び目を出力する結び目作成ステップと、
前記結び目の不変量を計算する結び目不変量計算ステップと、
前記測定環境で取得された複数の軌跡データについて、前記結び目不変量計算ステップで計算された不変量を、予め定義した複数種類の素な結び目の集合に分解し、素な結び目の出現頻度分布を求め、前記出現頻度分布をもとに前記測定環境における軌跡データの特徴ベクトルを作成する特徴解析ステップと
を有することを特徴とする軌跡データ解析方法。
【請求項６】
前記結び目作成ステップは、前記曲線の始点と終点とが一致しない場合に、前記始点と終点とを結ぶことを特徴とする請求項５に記載の軌跡データ解析方法。
【請求項７】
前記結び目作成ステップは、前記曲線に重複ルートが存在する場合に、前記曲線から重複ルートを解消することを特徴とする請求項５又は６に記載の軌跡データ解析方法。
【請求項８】
前記特徴解析ステップは、前記出現頻度分布から素な結び目の交点数毎の出現頻度分布を求め、前記交点数毎の出現頻度分布をもとに前記特徴ベクトルを作成することを特徴とする請求項５乃至７のいずれか１項に記載の軌跡データ解析方法。
【請求項９】
請求項５乃至８のいずれか１項に記載の軌跡データ解析方法に含まれる各ステップをコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ＧＰＳ等のセンサによって計測された人や物体等の軌跡データを解析する軌跡データ解析装置、軌跡データ解析方法及びプログラムに関する。
【背景技術】
【０００２】
ＧＰＳをはじめとするセンシング技術の進歩により、人や自動車等の様々な行動の軌跡を計測することが可能となっている。これらの軌跡データを活用し、都市や店舗の設計、ＷＥＢページ等のユーザビリティ評価が進められている。特に、魅力ある街作りや売上向上に向け、人が快適に行き来し、散策できるような空間設計や、ユーザビリティの観点から、所望の情報を容易に探すことができるようなＷｅｂページ設計が行われている。
【０００３】
これらの設計作業を支援する従来技術として、例えば、非特許文献１では、移動物体が通過する頻度の高い経路の特定、並びに、ある地点から別の地点への移動傾向をルールとして抽出し、移動物体の経路予測を行っている。特許文献１では、店舗内のカメラによって顧客の動線を取得し、そのデータを元に顧客の行動分析を行い、販売促進に向けた商品レイアウト設計等の支援を行っている。非特許文献２では、ＷＥＢページ閲覧者の視線を記録し、視線の注視点や移動方向を分析することにより、ＷＥＢページのユーザビリティ評価を支援する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−３０９９５１号公報
【非特許文献】
【０００５】
【非特許文献１】Mikolaj Morzy, “Mining Frequent Trajectories of Moving Objects for Location Prediction”, Proceedings of the 5th International Conference on Machine Learning and Data Mining in Pattern Recognition, pp. 667-680, 2007.
【非特許文献２】阪井誠, 中道 上, 島 和之, 中村 匡秀, 松本 健一, “WebTracer : 視線を利用したWebユーザビリティ評価環境”, 情報処理学会論文誌, Vol.44, No.11, pp. 2575-2586, 2003.
【非特許文献３】Colin C. Adams, “The Knot Book: An Elementary Introduction to the Mathematical Theory of Knots”, American Mathematical Society, 2004, pp. 1-7,164-169.
【非特許文献４】森川浩, 「数理科学美術館」, 工学社, 2005, pp. 105-112.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
都市計画やユーザビリティ評価等、それぞれの分野において成功事例が存在する場合、これらを参照することにより、ユーザは効果の高い計画を効率的に立案することができる。計画の効果を調べるためには、計画を実施する前後で成功事例にどれくらい近づいたかを把握する必要がある。成功事例が対象とする街、店舗、ＷＥＢページ等（以後、測定環境と呼ぶ）は、ユーザが対象としているものとは一般に異なるため、異なる測定環境間で軌跡データの解析結果を比較できなければならない。しかし、上記従来技術では、ランドマークや商品、注視点の種類や位置、及び、それらの間の移動時間や距離が解析に用いられているため、移動体が通過する頻度の高い経路や移動予測のためのルール等は、測定環境に固有のものとなり、それらを異なる環境間で比較することは不可能である。
【０００７】
この発明は上記事情に着目してなされたもので、その目的とするところは、異なる測定環境間で軌跡データの比較や分類を可能とする軌跡データ解析装置、軌跡データ解析方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するためにこの発明の第１の態様は、測定環境で取得された２次元の軌跡データを交点で立体交差させることで３次元の曲線に変換し、前記曲線に基づく結び目を出力する結び目作成手段と、前記結び目の不変量を計算する結び目不変量計算手段と、前記測定環境で取得された複数の軌跡データについて、前記結び目不変量計算手段で計算された不変量を、予め定義した複数種類の素な結び目の集合に分解し、素な結び目の出現頻度分布を求め、前記出現頻度分布をもとに前記測定環境における軌跡データの特徴ベクトルを作成する特徴解析手段とを具備することを特徴とする軌跡データ解析装置と、これに対応する軌跡データ解析方法及びプログラムを提供する。
【０００９】
上記第１の態様によれば、特徴ベクトルの各要素は測定環境間で同じ素な結び目を意味することになるため、特徴ベクトル間の距離計算を行うことにより、異なる測定環境間で軌跡データの類似性を調べ、それらを分類することが可能となる。これにより、互いに異なる測定対象においてＧＰＳ等のセンサによって収集された人や物体等の複数の軌跡データの特徴を比較、分類することが可能となる。
【００１０】
また、この発明の第２の態様は、上記第１の態様において、前記結び目作成手段は、前記曲線の始点と終点とが一致しない場合に、前記始点と終点とを結ぶことを特徴とする。  
人や物体等の軌跡データは必ずしも始点と終点とが一致するものとは限らないが、上記第２の態様によれば、始点と終点とが一致しない軌跡データも取り扱うことが可能になる。
【００１１】
また、この発明の第３の態様は、上記第１又は第２の態様において、前記結び目作成手段は、前記曲線に重複ルートが存在する場合に、前記曲線から重複ルートを解消することを特徴とする。  
上記第３の態様によれば、人が同じ道を行き来するように、軌跡データにルートの重複が見られる場合でも、ルートの重複を解消することでその曲線を結び目として出力することが可能となる。特に、同じ場所を行き来するような回遊的行動の軌跡データを取り扱う場合に有効である。
【００１２】
また、この発明の第４の態様は、上記第１乃至第３のいずれかの態様において、前記出現頻度分布から交点数毎の素な結び目の出現頻度分布を求め、前記交点数毎の素な結び目の出現頻度分布をもとに前記軌跡データの特徴ベクトルを作成することを特徴とする。
【００１３】
素な結び目の種類が非常に多い場合、特徴ベクトルは多くの要素が０となるスパースなベクトルとなり、この場合、特徴ベクトル間の距離はほとんどの場合０となってしまうため、軌跡データの分類には適さない。上記第４の態様によれば、素な結び目の出現頻度が交点数毎に求められるため、作成される特徴ベクトルの多くの要素が０になることが避けられ、軌跡データの分類に適した特徴ベクトルを解析結果としてユーザに提示することができる。
【発明の効果】
【００１４】
すなわちこの発明によれば、異なる測定環境間で軌跡データの比較や分類を可能とする軌跡データ解析装置、軌跡データ解析方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００１５】
【図１】ライデマイスター移動を示す図。
【図２】素な結び目の一例を示す図。
【図３】合成結び目の一例を示す図。
【図４】本発明の一実施形態に係る軌跡パターン分析装置の構成を示すブロック図。
【図５】軌跡パターン分析装置の動作概要を示すフローチャート。
【図６】結び目作成器の動作概要を示すフローチャート。
【図７】結び目作成器におけるクロージング処理を説明する図。
【図８】結び目作成器における重複ルートの解消処理を説明する図。
【図９】重複ルート解消処理の手順を示すフローチャート。
【図１０】重複ルート解消処理の一例を示す図。
【図１１】結び目不変量計算処理を説明する図。
【図１２】特徴解析器の動作概要を示すフローチャート。
【発明を実施するための形態】
【００１６】
以下、図面を参照しながら本発明に係る実施形態について説明する。  
本発明は、人や視線等が同じ場所を行き来するような回遊的行動の軌跡データの特徴を表現するものであり、軌跡データの交差の仕方に着目し、結び目理論を用いて、１つの環境における軌跡データ全体の特徴を１つの特徴ベクトルで表現する。特徴ベクトルの各要素の意味は測定する環境によらず、同じものに設定できるため、異なる測定環境間で特徴ベクトルの距離計算を行うことにより軌跡データの類似性を調べ、それらの比較、分類が可能になる。その原理と方法は、次の様である。
【００１７】
［原理と方法］  
人や視線等が同じ場所を行き来する回遊的行動においては、その軌跡データにはいくつかの交差点が存在する。この交差点間のつながり方を分析し、その特徴を測定環境に依存しない方法で表現することにより、時間的、或いは空間的に異なる測定環境間において、回遊的行動の軌跡データの比較を可能にする。本発明では、交差点のつながり方を結び目理論によって分析する。結び目理論は、自身と交わることのない３次元空間の閉折線や閉曲線を結び目と呼び、それらの形状を調べ分類する理論であり、例えば、非特許文献３に詳しく説明されている。本発明では、２次元空間における軌跡データから結び目を構成し、その結び目を分析することにより、軌跡データの特徴を表現する。
【００１８】
結び目は、ある２次元（ｘ−ｙ）平面に射影して表現され、射影図上で交差する点は交点と呼ばれる。また、交点においてｚ軸の値の小さい方の辺に切れ目を入れ、交点における各辺のｚ軸の値の大小が分かるように図示する。結び目理論では交点のつながり方のみを考慮するため、ライデマイスター移動と呼ばれる辺や頂点の局所的な移動を繰り返し行うことにより、一致する結び目は同じものと見なされる。
【００１９】
図１に示すように、ライデマイスター移動には３つのパターンが存在する。パターンＩは、交点の上下を入れ替えたループの作成と解消に関するもの、パターンＩＩは、交点の上下の入れ替え及び交点の解消に関するもの、パターンＩＩＩは、交点の上下の変化を伴わないような交点の移動に関するものである。これまでに、ライデマイスター移動によって一致させることができない結び目が、互いに異なる結び目として交点数に応じて整理されている。これらの結び目は「素な結び目」と呼ばれる。図２に、一例として、交点数が７以下の素な結び目を示す（出典：Ｋｎｏｔ  ｔａｂｌｅ．ｓｖｇ，  Ｗｉｋｉｍｅｄｉａ  Ｃｏｍｍｏｎｓ，  ｈｔｔｐ：／／ｃｏｍｍｏｎｓ．ｗｉｋｉｍｅｄｉａ．ｏｒｇ/ｗｉｋｉ/Ｆｉｌｅ：Ｋｎｏｔ＿ｔａｂｌｅ．ｓｖｇ？ｕｓｅｌａｎｇ＝ｅｎ）。図２では、結び目を閉曲線として表示している。交点数０の結び目は自明な結び目（Ｕｎｋｎｏｔ）と呼ばれる。ある結び目に対し、その交点のｚ軸の値の大小を逆にした結び目は、元の結び目の鏡像と呼ばれる。元の結び目とその鏡像は必ずしも同じものではなく、この場合、鏡像も素な結び目である。なお、図２では各結び目の鏡像は描かれていない。
【００２０】
また、図３に示すように、複数の結び目を交点が増えないようにつないだ結び目は、「合成結び目」と呼ばれる。任意の結び目は、素な結び目を合成することにより作成することができ、逆に、素な結び目の集合に一意に分解することができる。１つの結び目に対して、図１の局所変形によって変化しない結び目不変量が提案されている。結び目不変量が異なる結び目は互いに異なる。本発明では結び目不変量として、例えば、ＨＯＭＦＬＹ多項式を用いる。結び目Ｋ１とＫ２の合成結び目をＫ１＃Ｋ２、結び目ＫのＨＯＭＦＬＹ多項式をＰ（Ｋ）とすると、（１）式が成立する。
【００２１】
【数１】
2014170276.tif 000003
従って、ある結び目のＨＯＭＦＬＹ多項式を、素な結び目のＨＯＭＦＬＹ多項式で因数分解することにより、その結び目を構成する素な結び目の種類とそれぞれの数を求めることができる。但し、同じＨＯＭＦＬＹ多項式を持つ異なる結び目が幾つか存在するため、同じＨＯＭＦＬＹ多項式を持つ異なる素な結び目については、素な結び目のリストで最も若い番号を持つ素な結び目を因数分解に用いる。
【００２２】
次に、１つの測定環境における軌跡データの特徴表現について説明する。１つの軌跡データに対し、その交差点を立体交差にすることにより結び目を作成し、その結び目を構成する素な結び目の種類とそれぞれの数を（１）式により求める。この処理を同じ測定環境内で取得された全軌跡データについて行い、素な結び目の出現頻度からヒストグラムを作成する。このヒストグラムを素な結び目を各次元の要素とする特徴ベクトルとし、１つの測定環境における全軌跡データの特徴を１つの特徴ベクトルで表現する。特徴ベクトルの次元数は素な結び目の数となる。
【００２３】
例えば、図２の１４個の素な結び目（但し、自明な結び目を除く）を因数分解に用いた場合、ヒストグラムの個々のビンは１４個の素な結び目にそれぞれ対応し、その値は対応する素な結び目の出現数となり、さらに特徴ベクトルは１４次元のベクトルとなる。比較する全ての測定環境に対して、（１）式で調べる素な結び目の集合を同じものに設定することができる。つまり、特徴ベクトルの各要素は測定環境間で同じ素な結び目を意味することになり、特徴ベクトルのユークリッド距離やコサイン類似度等を計算することにより、異なる測定環境間で軌跡データの類似性を調べ、それらを分類することが可能となる。軌跡データ数は測定環境によって異なる場合がある。軌跡データ数の違いによる分析への影響を取り除く場合には、ヒストグラムの累積を１にする、或いは特徴ベクトルの大きさを１にする等の正規化を行う。
【００２４】
一方、素な結び目の種類が非常に多い場合、特徴ベクトルは多くの要素が０となるスパースなベクトルとなる。この場合、特徴ベクトル間の距離はほとんどの場合０となってしまうため、軌跡データの分類には適さない。そこで、素な結び目の出現頻度から、交点数毎に素な結び目の出現頻度を求め、そのヒストグラムをもとに特徴ベクトルを作成する。この特徴ベクトルの次元数は交点数の種類数となる。例えば、図２の１４個の素な結び目（但し、自明な結び目を除く）を因数分解に利用した場合、ヒストグラムの個々のビンは３〜７個の素な結び目の交点数にそれぞれ対応し、その値は対応する交点数を持つ素な結び目の出現数となり、さらに特徴ベクトルは５次元のベクトルとなる。素な結び目の出現頻度が交点数毎に求められるため、作成される特徴ベクトルの多くの要素が０になることが避けられる。
【００２５】
［構成］  
図４は、本発明の一実施形態に係る軌跡パターン分析装置の構成を示すブロック図である。図４において、軌跡パターン分析装置は、入出力器４０１、制御器４０２、結び目作成器４０３、結び目不変量計算器４０４、特徴解析器４０５、及びデータベース４０６を有する。入出力器４０１は、様々な測定環境で取得された２次元の軌跡データが入力される。軌跡データは、例えば、ＧＰＳ等のセンサによって計測された人や物体等の移動軌跡や、ＷＥＢページ閲覧者の視線の移動軌跡を利用することができる。データベース４０６には、複数種類の素な結び目とそのＨＯＭＦＬＹ多項式を予め格納しておく。例えば、図２の１４個の素な結び目に対しては、各素な結び目のインデックスとそれぞれのＨＯＭＦＬＹ多項式のペアを１レコードとして１４個のレコードが格納される。
【００２６】
結び目作成器４０３は、入出力器４０１に入力される２次元の軌跡データを交点で立体交差させることで３次元の曲線に変換し、この曲線の始点と終点とが結ばれた重複のない閉曲線を結び目として出力する。結び目不変量計算器４０４は、結び目作成器４０３から出力される結び目の不変量としてのＨＯＭＦＬＹ多項式を計算する。特徴解析器４０５は、結び目作成器４０３で計算された不変量を、データベース４０６に予め格納される複数種類の素な結び目の集合に分解してその出現頻度をヒストグラムに表し、このヒストグラムをもとに軌跡データの特徴ベクトルを作成する。制御器４０２は、結び目作成器４０３、結び目不変量計算器４０４、及び特徴解析器４０５を制御し、特徴解析器４０５で作成される軌跡データの特徴ベクトルを入出力器４０１から出力する。  
なお、この軌跡パターン分析装置は、例えば、コンピュータとメモリ上で実行されるプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを介して提供することも可能である。
【００２７】
［動作］  
図５は、軌跡パターン分析装置の動作概要を示すフローチャートである。
【００２８】
入出力器４０１は、測定環境内の全軌跡データを制御器４０２に出力する。制御器４０２は、軌跡データを結び目作成器４０３に入力する（ステップ５０１）。結び目作成器４０３は、個々の軌跡データからそれぞれの結び目を作成し、制御器４０２に出力する（ステップ５０２）。なお、結び目作成器４０３の処理については後述する。制御器４０２は軌跡データから作成された結び目を結び目不変量計算器４０４に出力すると、結び目不変量計算器４０４はそれらの結び目のＨＯＭＦＬＹ多項式を結び目不変量として計算し、制御器４０２に出力する（ステップ５０３）。なお、ＨＯＭＦＬＹ多項式の計算方法については後述する。
【００２９】
制御器４０２は、全ての軌跡データから作成された結び目のＨＯＭＦＬＹ多項式、及びデータベース４０６に格納された素な結び目のＨＯＭＦＬＹ多項式を特徴解析器４０５に出力する。特徴解析器４０５は、これらのＨＯＭＦＬＹ多項式から、測定環境内の個々の軌跡データから作成された結び目を構成する素な結び目の出現頻度を累計し、素な結び目の出現頻度を示すヒストグラムを作成する。特徴解析器４０５は、このヒストグラムをもとに測定環境内の全軌跡データに対する特徴ベクトルを求め、制御器４０２に出力する（ステップ５０４）。なお、特徴解析器４０５の処理については後述する。制御器４０２は特徴ベクトルを解析結果として入出力器４０１によりユーザに提示する（ステップ５０５）。
【００３０】
以下、ステップＳ５０２〜ステップＳ５０４の各処理内容について説明する。  
［結び目作成：ステップＳ５０２］  
図６から図１０を参照して、結び目作成器４０３における１つの軌跡データに対する結び目の作成方法について説明する。図６は、結び目作成器の動作概要を示すフローチャートである。まず、結び目作成器４０３は、２次元の軌跡データ(軌跡上の点を（ｘ，ｙ）で表す)から３次元の曲線（曲線上の点を(ｘ，ｙ，ｚ)で表す）を作成する。３次元曲線のｘ座標とｙ座標の値は、軌跡のｘ座標とｙ座標と同じ値に設定する。軌跡の始点から終点に向けて軌跡を辿り、ｚ座標を設定しながら曲線を伸ばしていく。初めて訪れる点については、そのｚ座標を０に設定する。移動軌跡が第ｉ回目に交差する点のｚ座標を（２）式により設定し、交差点を立体交差させる（ステップ６０１）。
【００３１】
【数２】
2014170276.tif 000004
これにより、自身とは交差しない３次元の曲線が得られる。次に、この３次元の曲線について始点と終点が一致しているか否かを判断し（ステップ６０２）、一致している場合はステップ６０４に進み、一致していない場合はステップ６０１で作成した３次元の曲線を含む直方体の外側で、始点と終点を結び（ステップ６０３）、ステップ６０４に進む。
【００３２】
ステップ６０３のクロージング処理は、図７に示すように、始点側については、始点からｚ軸の正の方向に辺を延ばし、終点側についてはステップ６０１の処理の最後のσの符号と同じｚ軸方向に終点から辺を延ばし、直方体の外側でそれらの辺を連結する。図７において、（ａ）はσ＞０の場合、（ｂ）はσ＜０の場合を示す。直方体の外側であれば、始点と終点からの辺をどのように結んでも図１に示す局所変形によって同じ結び目にすることができる。人が同じ道を行き来するように、軌跡データにはルートの重複が見られる場合がある。このとき、これまでの処理で得られる曲線には重複が存在するため、結び目にはならない。そこで、ルートの重複を解消した後（ステップ６０４）、その曲線を結び目として出力する（ステップ６０５）。
【００３３】
ここで、ステップ６０４の重複ルート解消処理について、図８、及び図９を参照しつつ説明する。重複ルートの解消は、例えば、非特許文献４に示された方法を適用することができる。曲線をバネでつながれた粒子の鎖とみなし、その弾性エネルギーを減少させるように粒子の位置を更新していく（以後、この処理を緩和と呼ぶ）。緩和により、粒子同士は互いに近づいていくが、重複ルート上の粒子が他の重複していない粒子に近づくため、曲線の重複が解消されていく。また、曲線の長さが減少していくことから、緩和過程は図１の（Ｉ）と（ＩＩ）の局所変形が行われることになり、より少ない数の交点を持つ結び目を作成することができる。これは、後に説明するＨＯＭＦＬＹ多項式の計算を容易にする効果がある。曲線上の始点から第ｉ番目の粒子の位置ベクトルをｑｉとすると、曲線全体の持つ弾性エネルギーＥは（３）式で表される。
【００３４】
【数３】
2014170276.tif 000005
第ｉ番目の粒子の移動量は、式（４）によって求められる。
【００３５】
【数４】
2014170276.tif 000006
但し、αは微小な定数であり、ｑｉの初期値は、ｘｙ座標については、軌跡データのｘｙ座標値に、（２）式で得られたｚiに粒子の直径Ｄを掛けた値に設定する。なお、直径Ｄは、軌跡データのスケールや測定誤差等から、測定環境毎にユーザが設定する。
【００３６】
また、緩和過程において、結び目の同等性を維持するために、曲線が自身を飛び越えないようにする必要がある。そこで、次の条件を満たす粒子を剛体球と見なし、それらが互いに衝突しないようにする。第ｉ番目の粒子に対して、次の（５）式の粒子集合Ｋｉが存在するとき、Ｋｉに含まれる粒子と第ｉ番目の粒子は互いに剛体球として作用する。
【００３７】
【数５】
2014170276.tif 000007
但し、ｌｉｋは曲線に沿って第ｉ番目の粒子から第ｋ番目の粒子に至る２方向の曲線のうち、短い方の曲線の長さであり、ｄｉｋは第ｉ番目と第ｋ番目の粒子の直線距離である。図８に示すように、第ｉ番目の粒子の近傍において、緩和によって曲線が縮小する時、曲線に沿ってπＤ／２以上離れた位置にある実線で示す粒子と、第ｉ番目の粒子の直線距離がＤ以内になることを防ぐことにより、粒子の衝突を回避し、曲線が自身を飛び越えないようにする。一方、曲線に沿ってπＤ／２以内に位置する破線で示す粒子は、剛体球とは見なされず、緩和によって第ｉ番目の粒子にいくらでも近づいて良い。集合Ｋｉが空集合でない場合、第ｉ番目の粒子の位置を以下の（６）式により更新する。
【００３８】
【数６】
2014170276.tif 000008
非特許文献４では、（４）式と（６）式の更新を同時期に行っているが、本発明では、曲線の飛び越え防止をより的確に行うために、（４）式に比べ（６）式の変化は素早く起こるものとし、（４）式の更新に際しては、（６）式で更新した粒子の位置は定数とみなし、更新は行わない。
【００３９】
図９を参照して、重複ルートの解消処理の流れについて説明する。ステップ６０３までに得られた曲線上に直径Ｄの粒子をＤ／２の間隔で補完する（ステップ９０１）。（５）式より、曲線に沿ってπＤ／２以内にある粒子同士は、剛体球として互いに作用せず、いくらでも近づけることができる。そこで、Ｄ／２の間隔で粒子を密に配置しておくことにより、緩和の過程で隣接する粒子が大きく離れてしまい、その間を衝突が検知されることなく曲線自身が飛び越えてしまうことを防ぐ。（６）式により、粒子の衝突を回避し、曲線が自身を飛び越えないようにする（ステップ９０２）。次に、ステップ９０２で更新しなかった粒子について、（４）式により、位置を更新した後（ステップ９０３）、緩和終了条件を満たすか否かを判断し（ステップ９０４）、緩和終了条件を満たす場合にはステップ９０５に進み、満たさない場合はステップ９０３に戻る。
【００４０】
緩和終了条件は、ステップ９０３の反復回数、或いは反復回数と併せて、ステップ９０２以降の処理後の曲線の長さや（３）式の弾性エネルギー等の変化の有無を組み合わせることにより、ユーザが設定する。但し、ステップ９０３からステップ９０４の反復が増えると、緩和をより促進することができるが、反復があまり多くなると、緩和を繰り返すうちに（５）式を満たす衝突する粒子が新たに現れたり、隣接する粒子が大きく離れ、その間を衝突が検知されることなく、曲線自身が飛び越えたりする可能性があることから、緩和終了条件を適切な値に設定し、ステップ９０３からステップ９０４の反復回数を制限する必要がある。
【００４１】
次に、終了条件を満たすか否かを判断し（ステップ９０５）、終了条件を満たす場合には処理を終了し、満たさない場合はステップ９０１に戻る。終了条件は、ステップ９０１の反復回数、ステップ９０１以降の処理後の曲線の長さや（３）式の弾性エネルギー等の変化の有無であり、これらのうちの一つ、或いは組み合わせによってユーザが設定する。  
図１０に、重複ルートの解消処理の一例を示す。時間とともに粒子同士が近づいていき、曲線は縮小していくが、（６）式により縮小が止まり、その結果、交点がより少ない結び目が作成されている。
【００４２】
［結び目不変量計算：ステップＳ５０３］  
図１１を参照して、結び目不変量計算器４０４における１つの結び目に対するＨＯＭＦＬＹ多項式の計算方法を説明する。結び目に任意の方向に向きを付ける。これにより、各交点の状態は図１１（ａ）のＬ＋とＬ−のどちらかになる。また、交点が無い状態をＬ０で表す。次に、図１１（ｂ）に示すように、結び目の中のある１つの交点に着目し、その状態をＬ＋とＬ−の間で逆転させた状態と、交点が無い状態（Ｌ０）にした結び目を分岐するように下に並べる。この操作を交点が無い状態になるまで繰り返し、結び目の分岐図を作成する。分岐図の下の結び目から上の結び目に向けて、以下のルールを適用し、ＨＯＭＦＬＹ多項式を計算していく。
【００４３】
【数７】
2014170276.tif 000009
但し、ｖとｚは変数であり、ルール１における○は交点の無い結び目を表す。ルール２は、ある結び目とそれから分岐された２つの結び目の３つ組に対して適用する。
【００４４】
［特徴解析：ステップＳ５０４］  
図１２を参照して、特徴解析器４０５における特徴ベクトルの計算方法に説明する。特徴解析器４０５は、予め選択した素な結び目についてそのＨＯＭＦＬＹ多項式を入力し、素な結び目の出現頻度を０に初期化するとともに、１番目の軌跡データの結び目を分解対象結び目に設定する（ステップ１２０１）。分解対象結び目のＨＯＭＦＬＹ多項式を分解対象多項式とし、素な結び目のｉｄを１に初期化する（ステップ１２０２）。そして、ｉｄ番目の素な結び目のＨＯＭＦＬＹ多項式によって分解対象多項式が因数分解できるか否かを調べ（ステップ１２０３）、因数分解が不可能であればｉｄ→ｉｄ＋１に更新し（ステップ１２０４）、ステップ１２０３に戻る。因数分解可能であれば、ｉｄ番目の素な結び目の出現頻度を１増加させる（ステップ１２０５）。ステップ１２０３において分解対象多項式をｉｄ番目の素な結び目のＨＯＭＦＬＹ多項式で割った商が１であるか否かを調べ（ステップ１２０６）、商が１でなければ、その商を分解対象多項式に設定し（ステップ１２０７）、ステップ１２０３に戻る。商が１であれば、次に解析する軌跡データの有無を確認し、次の軌跡データがある場合には、次の軌跡データの結び目を分解対象に設定し（ステップ１２０９）、ステップ１２０２に戻る。
【００４５】
次の軌跡データが無ければ、素な結び目の出現頻度からヒストグラムを作成し、そのヒストグラムをもとに特徴ベクトルを作成する。また、素な結び目の種類の数が多い場合など、必要に応じて、そのヒストグラムから交点数毎に素な結び目が出現した頻度を求めることにより、素な結び目の交点数に関するヒストグラムを作成し、そのヒストグラムをもとに特徴ベクトルを作成する（ステップ１２１０）。
【００４６】
なお、本発明では同じルートに対して辿る方向を区別しない。しかし、図６のステップ６０１において、図７（ｂ）のように、始点と終点から辺を延ばす方向が異なる場合、同じルートを終点から始点に向けて逆方向に辿ると、立体交差点のｚ座標の正負が逆転した結び目が作成される。この結び目は元の方向で得られた結び目の鏡像となり、元の結び目とは必ずしも一致しない場合がある。この場合、逆方向の結び目を分解して得られる素な結び目も、元の方向の結び目を分解して得られる素な結び目の鏡像となり、軌跡を辿る方向によって素な結び目の出現頻度が変わってしまう。そこで、軌跡を辿る方向によって素な結び目の頻度分布が変わらないようにするために、ステップ１２０２からステップ１２０７の処理によって得られた、出現する素な結び目に対し、それぞれの素な結び目の鏡像も同じ数だけ出現するものとして、元のルートの方向で得られた素な結び目の出現頻度に加え、その出現頻度を２で割ったものを素な結び目の出現頻度として以降の処理を進める。一方、始点と終点から辺を延ばす方向が同じ場合は、ルートを辿る方向によらず同じ結び目となるため、前記の鏡像に関する処理は行わない。
【００４７】
以上述べたように、上記実施形態では、２次元の軌跡データを交点で立体交差させることで３次元の曲線に変換し、この曲線の始点と終点とを結ぶ閉曲線から重複ルートを解消して得られた曲線を結び目と見なし、この結び目のＨＯＭＦＬＹ多項式を素な結び目のＨＯＭＦＬＹ多項式で因数分解し、結び目を構成する素な結び目の種類とその数を特定することにより、当該軌跡データの特徴ベクトルを作成する。特徴ベクトルの各要素は測定環境間で同じ素な結び目を意味することになり、特徴ベクトル間の距離計算を行うことにより、異なる測定環境間で軌跡データの類似性を調べ、それらを分類することが可能となる。
【００４８】
上記実施形態によれば、ＧＰＳ等のセンサによって計測された人や物体等の軌跡データについて、異なる街や異なる店舗、異なるWEBページ等、測定環境の異なる軌跡データを比較し、分類することを可能にする。また、軌跡データを活用した都市や店舗の設計、ＷＥＢページ等のユーザビリティ評価等において、成功事例等、他の事例との軌跡データの比較が可能となり、設計やユーザビリティ評価等の支援が可能となる。
【００４９】
なお、この発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【００５０】
４０１…入出力器、４０２…制御器、４０３…結び目作成器、４０４…結び目不変量計算器、４０５…特徴解析器、４０６…データベース。
【図１】
2014170276.tif 000010
【図２】
2014170276.tif 000011
【図３】
2014170276.tif 000012
【図４】
2014170276.tif 000013
【図５】
2014170276.tif 000014
【図６】
2014170276.tif 000015
【図７】
2014170276.tif 000016
【図８】
2014170276.tif 000017
【図９】
2014170276.tif 000018
【図１０】
2014170276.tif 000019
【図１１】
2014170276.tif 000020
【図１２】
2014170276.tif 000021