(57)【要約】【課題】データ列のうち情報価値の高い部分の劣化を防ぎながら、データ列を効率的に圧縮する。【解決手段】データ列を取得して複数のセグメントに分割する。代表データ列を取得し、複数のセグメントに分割されたデータ列と、複数のセグメントに分割された代表データ列と、の乖離度を各セグメントについて判定する。乖離度が閾値以下であるセグメントを代表データ列を用いた第１の表現で表し、乖離度が閾値を超えるセグメントを第１の表現とは異なる第２の表現で表すように、データ列を変換データへと変換する。変換データを出力する。【選択図】図６
2017041794.tif 000002
【特許請求の範囲】
【請求項１】
データ列を取得して複数のセグメントに分割する分割手段と、
代表データ列を取得し、前記複数のセグメントに分割された前記データ列と、複数のセグメントに分割された代表データ列と、の乖離度を各セグメントについて判定する判定手段と、
前記乖離度が閾値以下であるセグメントを前記代表データ列を用いた第１の表現で表し、前記乖離度が閾値を超えるセグメントを前記第１の表現とは異なる第２の表現で表すように、前記データ列を変換データへと変換する変換手段と、
前記変換データを出力する出力手段と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記データ列は、複数の座標データで構成される動線データであることを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記判定手段は、複数の代表データ列から、前記データ列に対応する代表データ列を選択することを特徴とする、請求項１又は２に記載の情報処理装置。
【請求項４】
前記判定手段は、前記データ列に最も類似する代表データ列を選択することを特徴とする、請求項３に記載の情報処理装置。
【請求項５】
前記判定手段は、各セグメントについて前記データ列と前記代表データ列との乖離度を取得し、各セグメントについて取得された乖離度に応じて得られる前記データ列と前記代表データ列との乖離度に基づいて前記データ列に最も類似する代表データ列を選択することを特徴とする、請求項４に記載の情報処理装置。
【請求項６】
前記乖離度は、前記データ列を構成するデータと前記代表データ列を構成するデータとの間のデータ間距離に従って得られることを特徴とする、請求項５に記載の情報処理装置。
【請求項７】
各セグメントについて前記データ列に含まれるデータの数と前記代表データ列に含まれるデータの数とが同数となるように前記データ列を更新する更新手段をさらに備えることを特徴とする、請求項１乃至６の何れか１項に記載の情報処理装置。
【請求項８】
前記出力手段は、前記第１の表現として、前記代表データ列を示す識別子を出力することを特徴とする、請求項１乃至７の何れか１項に記載の情報処理装置。
【請求項９】
前記出力手段は、前記第２の表現として、前記データ列を出力することを特徴とする、請求項１乃至８の何れか１項に記載の情報処理装置。
【請求項１０】
前記出力手段は、前記第２の表現として、前記代表データ列を示す識別子と、前記データ列と前記代表データ列との差分データ列と、を出力することを特徴とする、請求項１乃至８の何れか１項に記載の情報処理装置。
【請求項１１】
前記代表データ列は、同じ属性を有する複数のデータ列から生成されることを特徴とする、請求項１乃至１０の何れか１項に記載の情報処理装置。
【請求項１２】
前記代表データ列は、類似性に基づいてグループ化されたデータ列から生成されることを特徴とする、請求項１乃至１０の何れか１項に記載の情報処理装置。
【請求項１３】
前記出力手段は、前記データ列に対する前記変換データの圧縮率が所定値未満であるか否かを判定し、前記圧縮率が前記所定値未満である場合、前記変換データの代わりに前記データ列に基づく別のデータを出力することを特徴とする、請求項１乃至１２の何れか１項に記載の情報処理装置。
【請求項１４】
前記判定手段は、前記代表データ列を参照して前記変換データからデータ列を復元し、前記複数のセグメントに分割された前記復元されたデータ列と、複数のセグメントに分割された新たな代表データ列と、の乖離度を各セグメントについて判定し、
前記変換手段は、前記乖離度が閾値以下であるセグメントを前記新たな代表データ列を用いた第１の表現で表し、前記乖離度が閾値を超えるセグメントを前記第２の表現で表すように、前記復元されたデータ列を新たな変換データへと変換し、
前記出力手段は、前記新たな変換データが前記変換データよりも小さいか否かを判定し、前記新たな変換データが前記変換データよりも小さい場合、前記変換データを前記新たな変換データで置換する
ことを特徴とする、請求項１乃至１３の何れか１項に記載の情報処理装置。
【請求項１５】
前記出力手段は、前記データ列に対する前記変換データの圧縮率が所定値以上であるか否かと、前記データ列の生成時刻が所定時刻以後であるか否かと、の少なくとも一方を判定し、前記判定に応じて前記変換データの出力先を変更することを特徴とする、請求項１乃至１４の何れか１項に記載の情報処理装置。
【請求項１６】
前記分割手段は、前記変換データが小さくなるように複数の分割方法から選択された分割方法に従って前記データ列を分割することを特徴とする、請求項１乃至１５の何れか１項に記載の情報処理装置。
【請求項１７】
複数のセグメントで構成され、それぞれのセグメントは第１の表現を含む複数の表現から選択された表現で表されている、変換データを取得する第１の取得手段と、
前記変換データに付された識別子に従って、前記第１の表現に対応する代表データ列を取得する第２の取得手段と、
前記代表データ列を用いて前記第１の表現で表されたセグメントをデータ列へと変換する手段を有する、前記セグメントのそれぞれをデータ列へと変換して前記セグメントのそれぞれについて得られたデータ列を統合する変換手段と、
を備えることを特徴とする情報処理装置。
【請求項１８】
情報処理装置が行う情報処理方法であって、
データ列を取得して複数のセグメントに分割する分割工程と、
代表データ列を取得し、前記複数のセグメントに分割された前記データ列と、複数のセグメントに分割された代表データ列と、の乖離度を各セグメントについて判定する判定工程と、
前記乖離度が閾値以下であるセグメントを前記代表データ列を用いた第１の表現で表し、前記乖離度が閾値を超えるセグメントを前記第１の表現とは異なる第２の表現で表すように、前記データ列を変換データへと変換する変換工程と、
前記変換データを出力する出力工程と、
を備えることを特徴とする情報処理方法。
【請求項１９】
コンピュータを、請求項１乃至１７の何れか１項に記載の情報処理装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
近年、監視カメラで人物を追尾することにより動線を表すデータ列を大量に生成し、異常検知等に応用する試みがなされている。このため、大量に生成された動線データをどのように蓄積するかが課題となっている。特許文献１には、誤差が許容値以内となるように、対象とする動線を区間ごとに直線で近似する方法が示されている。この方法によれば、複雑な動線データを圧縮してデータ量を小さくすることができる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１０−８２４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１に記載の方法には、それぞれの動線データについて近似を行って近似曲線を得るため、圧縮効率が低いという課題があった。一方で、圧縮効率を高めようとすると、動線データの情報量が低下してしまう。
【０００５】
本発明は、データ列のうち情報価値の高い部分の劣化を防ぎながら、データ列を効率的に圧縮することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の目的を達成するために、例えば、本発明の情報処理装置は以下の構成を備える。すなわち、
データ列を取得して複数のセグメントに分割する分割手段と、
代表データ列を取得し、前記複数のセグメントに分割された前記データ列と、複数のセグメントに分割された代表データ列と、の乖離度を各セグメントについて判定する判定手段と、
前記乖離度が閾値以下であるセグメントを前記代表データ列を用いた第１の表現で表し、前記乖離度が閾値を超えるセグメントを前記第１の表現とは異なる第２の表現で表すように、前記データ列を変換データへと変換する変換手段と、
前記変換データを出力する出力手段と、
を備えることを特徴とする。
【発明の効果】
【０００７】
データ列のうち情報価値の高い部分の劣化を防ぎながら、データ列を効率的に圧縮することができる。
【図面の簡単な説明】
【０００８】
【図１】実施形態１に係る監視システムの構成図。
【図２】実施形態１に係るサーバ１０３の主要部の構成図。
【図３】実施形態１に係るサーバ１０３のモジュール構成図。
【図４】実施形態１で用いられる各種データの構成を説明する図。
【図５】実施形態１における識別部分動線データの保存処理のフローチャート。
【図６】実施形態１における動線データ保存処理のフローチャート。
【図７】実施形態１における動線データ復元処理のフローチャート。
【図８】実施形態７におけるラベル付き動線データの構成を説明する図。
【図９】実施形態２で用いられる各種データの構成を説明する図。
【図１０】実施形態２における識別部分動線データの保存処理のフローチャート。
【図１１】実施形態２における動線データ保存処理のフローチャート。
【発明を実施するための形態】
【０００９】
動線データのような一つのデータ列（系列データ）中には、情報価値の高い部分と、低い部分が混在している。例えば、動線データであれば、他人と同じような動きをしている部分については情報価値が低く、他人と異なる動きをしている部分については情報価値が高いといえる。例えば、動線データを用いて異常検知等を行う場合、このような情報価値が高い部分は異常箇所に相当する可能性が高いため、この部分における動線データの情報量を損なわないことは、より高精度な異常検知につながる。このように、情報価値の高い部分の情報量が低下しないように圧縮を行うことは、データ列を一様に圧縮するよりも有利である。
【００１０】
本発明の一実施形態によれば、データ列のうち、代表データ列との乖離度が小さい部分は一括して識別子に置換される。このために、データ列を効率的に圧縮することができる。また、乖離度が大きい部分については、置換を行わず元のデータが保持される。このため、情報価値の高い部分の情報量が損なわれないようにデータ列を圧縮することができる。
【００１１】
以下、本発明の実施例を図面に基づいて説明する。ただし、本発明の範囲は以下の実施例に限定されるものではない。
【００１２】
［実施形態１］
本発明の実施形態１に係る圧縮装置について以下に説明する。本実施形態に係る圧縮装置は、図１に示す監視システムにおいて用いられる。この監視システムは、監視カメラ１０１、ネットワーク１０２、サーバ１０３及びモニタ装置１０４を備える。
【００１３】
監視カメラ１０１は、ネットワーク１０２を介してサーバ１０３と接続している。監視カメラ１０１は、撮影した映像をサーバ１０３に送信する機能を有する。サーバ１０３は、監視システムの機能を統括する。例えば、サーバ１０３は、監視カメラ１０１から受信した映像から人物を抽出することができる。また、サーバ１０３は、映像中での人物の動きの軌跡を示す動線データを抽出する機能、抽出した動線データを圧縮する機能、及び圧縮された動線データを復元する機能を有する。モニタ装置１０４は、監視カメラ１０１から受信した映像又はサーバ１０３に蓄積された映像を表示する機能に加えて、動線データを表示する機能を有する。監視システムはさらに、監視者が監視システムを操作するための入力部等のその他の構成を有していてもよいが、これらの説明は省略する。
【００１４】
以下では、説明を簡単にするために、監視カメラ１０１の設置位置、撮影方向及び焦点距離は固定されており、これらの情報はカメラ設置情報としてサーバ１０３において管理されているものとする。また、監視カメラ１０１の監視領域内での位置は、予め設定された平面座標上の位置として表されるものとする。監視カメラ１０１が固定されていない場合には、例えば動線データに監視カメラ１０１の位置等を示す情報を含めることができる。
【００１５】
図２はサーバ１０３のハードウェア構成例を示す。演算部２０１は、情報処理のための演算及び論理判断等を行う。演算部２０１は、システムバス２０５を介して、システムバス２０５に接続された各構成要素を制御する。演算部２０１は、例えばＣＰＵ等のプロセッサでありうる。
【００１６】
表示部２０２は、表示装置における画像情報の表示を制御するコントローラである。本実施形態においては、表示部２０２は表示装置として液晶パネルを有しているものとする。入力部２０３には、サーバ１０３へのユーザからの指示が入力される。入力部２０３は、例えばボタン、キーボード、マウス等でありうる。通信部２０４は、外部にある他の装置との通信を制御する。通信部２０４はネットワークコントローラ等であり、例えばＬＡＮ、３Ｇ、４Ｇ、又はＢｌｕｅｔｏｏｔｈ（登録商標）技術等に従うコントローラでありうる。なお、目的に従う他の装置との通信が可能であれば、通信方式は上記の例には限られない。
【００１７】
ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２０６は、各構成要素からの各種データの一時記憶に用いられるメモリである。記憶部２０７は各種データを長期記憶することが可能なメモリである。記憶部２０７としては、フラッシュメモリ、ＨＤＤ又は光学ディスク等の物理媒体を用いることができ、本実施形態で実行される処理プログラム等の制御プログラムコードの他、各種設定データ、画像データ又は動線データ等を記憶することができる。
【００１８】
これらの各構成要素を備えるサーバ１０３は、入力部２０３からの各種入力及び通信部２０４からのネットワーク経由の各種入力に応じて作動する。すなわち、入力部２０３又は通信部２０４からの入力が供給されると、まず、インタラプト信号が演算部２０１に送られる。そして、演算部２０１は記憶部２０７に記憶されている各種の制御信号を読み出し、それらの制御信号に従って演算部２０１が動作することにより、各種の制御が行われる。また、本実施形態に係るプログラムを格納した記憶媒体をシステム又は装置に供給し、そのシステム又は装置が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、本実施形態は達成される。
【００１９】
図３は監視システムのサーバ１０３のモジュール構成の一例を示す。サーバ１０３は、データ抽出部３０１、データ格納部３０２、代表データ保存部３０３、属性抽出部３０５、代表データ格納部３０７、データ置換部３０８、保存データ格納部３１３、及びデータ復元部３１４を備える。
【００２０】
データ抽出部３０１は、データ列を取得する。本実施形態においてデータ抽出部３０１は、通信部２０４を通じて監視カメラ１０１から得た映像データを解析し、人物追尾処理を行う。こうして、データ抽出部３０１は、複数の座標データで構成され、人物ごとの動きの軌跡を示す動線データを生成する。そして、データ抽出部３０１は、データ格納部３０２に動線データを観測点データとして記録する。観測点データに関しては図４（Ａ）を参照して後述する。
【００２１】
属性抽出部３０５は、データ列の属性を取得する。本実施形態において属性抽出部３０５は、人物の属性を抽出することができる。人物の属性としては、性別、身長、又は年齢等が挙げられる。例えば属性抽出部３０５は、認識技術を用いることにより、監視カメラ１０１から取得されてＲＡＭ２０６に記録されている画像データから人物の性別を抽出することができる。すなわち、属性抽出部３０５は、データ格納部３０２に記録される人物の動線データについて、人物の属性を取得することができる。
【００２２】
代表データ保存部３０３は、代表データ列を生成、分割及び保存する。本実施形態において代表データ保存部３０３は、代表データ列として、観測点データから代表動線データを取得する。そして、代表データ保存部３０３は、代表データ列を複数のセグメントに分割する。本実施形態において、代表データ保存部３０３は、代表動線データを複数の代表部分動線データに分割する。さらに、代表データ保存部３０３は、分割により得られた代表データ列のそれぞれのセグメントに識別子を付与し、識別子が付与されたセグメントを保存する。本実施形態において、代表データ保存部３０３は、代表部分動線データに識別子を付与し、識別子が付与された代表部分動線データを保存する。
【００２３】
代表データ保存部３０３は、代表データ抽出部３０４ａと、代表データ分割部３０４ｂと、識別子付与部３０６との３つのモジュールを備える。代表データ抽出部３０４ａは、同じ属性を有する複数のデータ列から、代表データ列を生成する。本実施形態において代表データ抽出部３０４ａは、データ格納部３０２に格納された動線データから、同じ属性を有する動線データを抽出し、抽出された動線データから代表動線データを生成する。本実施形態において、代表動線データが表す代表動線は、人物の代表的な動線又は平均的な動線を示すものであり、特定の属性を有する人物群ごとに生成される。本実施形態においては、性別ごとに代表動線データが生成される。例えば、性別ごとの動線データの座標値の平均を算出することにより、代表動線データを生成することができる。
【００２４】
そして、代表データ分割部３０４ｂは、代表動線データを分割して代表部分動線データを生成する。本実施形態において代表データ分割部３０４ｂは、座標区間ごとに代表動線を分割することにより得られる複数の代表部分動線のそれぞれを、それぞれの代表部分動線データが表すように、代表部分動線データを生成する。
【００２５】
識別子付与部３０６は、代表部分動線データに対して、代表部分動線データを一意に特定するための識別子を付与する。本実施形態において識別子付与部３０６は、代表部分動線データに対して識別子として部分動線ＩＤを付与する。識別子が付与された代表部分動線データのことを、本明細書においては識別部分動線データと呼ぶ。そして、識別子付与部３０６は、識別部分動線データを代表データ格納部３０７に保存する。
【００２６】
データ置換部３０８は、データ格納部３０２に格納されているデータ列に対して置換処理を行うことにより、データ列を圧縮する。本実施形態においてデータ置換部３０８は、データ格納部３０２に格納されている動線データを部分動線データへと分割する。そしてデータ置換部３０８は、部分動線データと代表部分動線データとの乖離度を取得する。さらにデータ置換部３０８は、取得された乖離度に基づいて部分動線データを代表部分動線データの識別子で置換する。
【００２７】
データ置換部３０８は、データ分割部３０９ａ、乖離度取得部３０９ｂ、識別子置換部３１０、データ生成部３１１、データ保存部３１２の四つのモジュールを備える。
【００２８】
データ分割部３０９ａは、データ列を取得して複数のセグメントに分割する。本実施形態においてデータ分割部３０９ａは、データ格納部３０２にあらかじめ蓄積されている動線データを取得し、取得した動線データを分割して部分動線データを生成する。本実施形態においてデータ分割部３０９ａは、動線データが表す動線を座標区間ごとに分割することにより得られる複数の部分動線のそれぞれを、それぞれの部分動線データが表すように、部分動線データを生成する。区切り方に関しては図４（Ｅ）を参照して後述する。
【００２９】
乖離度取得部３０９ｂは、代表データ列を取得し、データ分割部３０９ａにより複数のセグメントに分割されたデータ列と、複数のセグメントに分割された代表データ列と、の乖離度を各セグメントについて判定する。本実施形態において、乖離度取得部３０９ｂは、代表データ格納部３０７に保存されている代表動線データを取得する。そして、乖離度取得部３０９ｂは、データ分割部３０９ａにより得られた部分動線データのそれぞれについて、代表部分動線データとの乖離度を取得する。乖離度としては、データ列を構成するデータと代表データ列を構成するデータとの間のデータ間距離を用いることができる。本実施形態において乖離度取得部３０９ｂは、乖離度として、部分動線データと代表部分動線データとの間の座標値の二乗誤差を算出する。
【００３０】
本実施形態において、代表データ格納部３０７には、複数の代表動線データ（代表データ列）が、代表部分動線データとして格納されている。そこで、乖離度取得部３０９ｂは、複数の代表データ列から、データ列に対応する代表データ列を選択することができる。例えば、乖離度取得部３０９ｂは、各セグメントについてデータ列と代表データ列との乖離度を取得することができる。そして、各セグメントについてのデータ列と代表データ列との乖離度に基づいて、乖離度取得部３０９ｂは、データ列と代表データ列との乖離度との乖離度を取得することができる。本実施形態において、乖離度取得部３０９ｂは、データ分割部３０９ａにより得られた部分動線データのそれぞれについて、対応する代表部分動線データとの乖離度を取得する。そして、乖離度取得部３０９ｂは、それぞれの部分動線データについて得られた乖離度から、動線データと代表動線データとの乖離度を取得する。乖離度取得部３０９ｂは、こうして得られた乖離度に基づいて動線データに最も類似する代表動線データを選択することができる。
【００３１】
識別子置換部３１０は、乖離度が閾値以下であるセグメントを代表データ列を用いた第１の表現で表し、乖離度が閾値を超えるセグメントを第１の表現とは異なる第２の表現で表すように、データ列を変換データへと変換する。第１の表現及び第２の表現は特定の表現に限定されるわけではないが、例えば、第１の表現として第２の表現よりもデータ量が少なくなる表現を用いることができる。本実施形態において、識別子置換部３１０は、乖離度取得部３０９ｂにより得られた乖離度が予め定められた閾値以下である場合、部分動線データを、対応する代表部分動線データの識別子（部分動線ＩＤ）で置換する。このようにして、部分動線データは代表データ列を用いて表現される。一方で、識別子置換部３１０は、乖離度が予め定められた閾値より大きい場合、部分動線データを部分動線ＩＤで置換しない。すなわち、乖離度が予め定められた閾値より大きい場合、閾値以下である場合とは異なる表現で部分動線データは表される。本実施形態においては、乖離度が予め定められた閾値より大きい場合、部分動線データはそのまま出力され、保存データ内に格納される。
【００３２】
データ生成部３１１は、識別子置換部３１０により変換された変換データを出力する。本実施形態において、データ生成部３１１は、識別子置換部３１０による処理により得られたデータ同士を結合して保存データを生成する。例えば、データ生成部３１１は、動線データを分割して得られた部分動線データのそれぞれを結合して保存データを生成する。上記の通り、乖離度が閾値以下である部分動線データは、対応する代表動線データを示す識別子（部分動線ＩＤ）に置換されて出力される。また、乖離度が閾値を超える部分動線データはそのまま出力される。そして、データ保存部３１２は、保存データを保存データ格納部３１３へと出力して保存する。
【００３３】
データ復元部３１４は、データ置換部３０８によって圧縮されたデータ列を復元する。本実施形態において、データ復元部３１４は、入力部２０３によって指定された保存データを動線データへと復元する。データ復元部３１４は、保存データ取得部３１５、代表部分データ取得部３１６、及びデータ収集部３１７の３つのモジュールを備える。
【００３４】
保存データ取得部３１５は、複数のセグメントで構成され、それぞれのセグメントは第１の表現を含む複数の表現から選択された表現で表されている、変換データを取得する。本実施形態において保存データ取得部３１５は、保存データ格納部３１３に格納されている保存データを取得する。
【００３５】
代表部分データ取得部３１６は、保存データ取得部３１５が取得した変換データに付された識別子に従って、第１の表現に対応する代表データ列を取得する。本実施形態において代表部分データ取得部３１６は、識別子置換部３１０による置換処理のために保存データに含まれている部分動線ＩＤに対応する代表部分動線データを代表データ格納部３０７から取得する。
【００３６】
データ収集部３１７は、代表データ列を用いて第１の表現で表されたセグメントをデータ列へと変換することにより、セグメントのそれぞれをデータ列へと変換し、セグメントのそれぞれについて得られたデータ列を統合する。本実施形態においてデータ収集部３１７は、保存データのうち、部分動線ＩＤで置換されていない部分についての部分動線データの座標値と、部分動線ＩＤで置換されている部分についての対応する代表部分動線データの座標値と、を取得する。そして、データ収集部３１７は、取得した座標値を結合することにより、復元動線データを生成する。
【００３７】
図４（Ａ）は、データ格納部３０２に格納される動線データを構成する観測点データの構成の一例を示す。動線データを構成するそれぞれの観測点データは、観測点ＩＤ４０２、動線ＩＤ４０３、及び座標４０４を有している。観測点データ４０１は、データ抽出部３０１による追尾処理により検出された全ての人物についてその観測点の座標を示すデータであって、複数の座標を含む系列データである。観測点ＩＤ４０２は、動線データを構成する観測点を一意に識別するために観測点に対して割り当てられる識別子であり、本実施形態においては記録順に１より順に割り当てられる。
【００３８】
動線ＩＤ４０３は、動線データを一意に識別するために動線データに対して割り当てられる識別子である。本実施形態においては、１つの動線データは、監視領域内における１人の人物の移動軌跡を表し、１つの動線データを構成する観測点には同じ動線ＩＤ４０３が割り当てられる。動線データに対応する人物を識別可能な動線ＩＤ４０３を割り当てることもでき、こうして動線ＩＤ４０３を用いて座標４０４と監視対象の人物とを一対一に対応させることもできる。図４（Ａ）に示されるデータは３人の人物についての動線データを含んでおり、それぞれの人物についての観測点にはそれぞれ異なる動線ＩＤ４０３が付されている。座標４０４は、監視領域内の人物の位置、すなわち観測点の位置を平面座標で示したものである。
【００３９】
図４（Ｂ）（Ｃ）は、代表データ格納部３０７に格納される代表動線データ４１１，４１２を構成する観測点データの構成の一例を示す。代表動線データを構成するそれぞれの観測点データは、代表動線ＩＤ４１３及び座標４１４を有している。図４（Ｂ）（Ｃ）に示す代表動線データは、複数の動線データを性別ごとに代表するデータである。例えば、図４（Ｂ）に示す代表動線データは性別が男性である動線データを代表したものであり、図４（Ｃ）に示す代表動線データは性別が女性の動線データを代表したものである。代表動線ＩＤは、代表動線データを一意に識別するために代表動線データに対して割り当てられる識別子である。また、座標４１４は、代表動線データにより表される代表動線の位置を示す平面座標である。
【００４０】
図４（Ｄ）は属性データ４２１の構成の一例を示す。属性データのそれぞれのエントリは動線ＩＤ４０３と属性値４２２を有している。属性値４２２は、動線ＩＤ４０３を有する動線データがどのような属性を有しているかを示す。本実施形態において属性値４２２は、動線ＩＤ４０３を有する動線データが表す人物の性別を示す。この属性値は、監視カメラ１０１から取得されＲＡＭ２０６に保存されている画像データから、属性抽出部３０５が抽出することができる。
【００４１】
図４（Ｅ）は部分動線を説明する図である。本実施形態においては、監視領域４３１が一定間隔で複数の領域に分割され、動線はそれぞれの領域に含まれる部分動線へと分割される。すなわち、動線データは、それぞれの領域に含まれる観測点データで構成される部分動線データへと分割される。図４（Ｅ）において、実線は動線に相当し、それぞれの点４３２は１つの観測点に相当する。そして、動線を座標区間ごとに区切って領域分割することにより、部分動線４３３，４３４，４３５が得られる。
【００４２】
図４（Ｆ）（Ｇ）は識別部分動線データ４４１，４４２の構成の一例を示す。データのそれぞれのエントリは代表動線ＩＤ４１３、部分動線ＩＤ４４３、及び座標４１４を有している。図４（Ｆ）に示すデータは、図４（Ｂ）（Ｃ）に示す代表動線データを図４（Ｅ）に示すように分割し、それぞれの代表部分動線に対してユニークな部分動線ＩＤ４４３を割り当てることにより得られる。
【００４３】
図４（Ｈ）は動線データ４５１を構成する観測点データの構成の一例を示し、具体的な構成は図４（Ａ）と同様である。図４（Ｈ）に示す動線データは、データ抽出部３０１により抽出され、データ格納部３０２に格納されている。図４（Ｉ）は、識別子置換部３１０による置換処理を説明する図である。図４（Ｉ）に示すラベル付き動線データ４６１は、動線ＩＤ４０３、部分動線ＩＤ４４３、及び座標４０４を有している。図４（Ｉ）に示すデータは、観測点データに対応する部分動線ＩＤ４４３を割り当てることにより得られる。具体的な処理については後述する。
【００４４】
図４（Ｊ）は保存データ４７１の構成の一例を示す。保存データ４７１は、動線ＩＤ４０３、部分動線ＩＤ４４３、及び座標４０４を有している。保存データ４７１は、部分動線ＩＤ４４３が割り当てられたエントリから座標データを削除し、重複する部分動線ＩＤ４４３を削除することにより、図４（Ｈ）に示すラベル付き動線データ４６１から得られる。図４（Ｋ）は復元動線データ４８１の構成図の一例を示す。復元動線データ４８１は観測点ＩＤ４０２、動線ＩＤ４０３、及び座標４０４を有している。復元動線データ４８１は、データ復元部３１４が保存データ４７１に対して復元処理を行うことにより得られる。
【００４５】
本実施形態に係る圧縮方法を、図５〜７のフローチャートに従って説明する。図５は、本実施形態においてサーバ１０３が行う識別部分動線データ４４１，４４２の生成処理を示すフローチャートである。ステップＳ５０１において代表データ抽出部３０４ａは、データ格納部３０２に蓄積されている１以上の動線データを取得する。例えば、代表データ抽出部３０４ａは、観測点データ４０１のうち、動線ＩＤ４０３が同一である１以上の観測点データを動線データとして取得する。図４（Ａ）に示す観測点データ４０１を用いる場合、代表データ抽出部３０４ａはまず、動線ＩＤ４０３がＴ００１である観測点データを取得する。ステップＳ５０２で代表データ抽出部３０４ａは全ての動線データを受け取ったか否かを判定し、受け取っている場合は処理はステップＳ５０３へ進み、受け取っていない場合には処理はステップＳ５０１へ戻る。こうして、代表データ抽出部３０４ａはステップＳ５０１の処理を全ての動線データを取得するまで繰り返し、こうして動線ＩＤ４０３がＴ００２である観測点データ及び動線ＩＤ４０３がＴ００３である観測点データを取得する。
【００４６】
本実施形態においては、それぞれの動線データを構成する観測点の数は一定であるものとする。このような動線データは、サーバ１０３が備える更新部（不図示）が観測点データに対して補間処理又は間引き処理を行うことにより生成することができる。例えば、図４（Ａ）に示す観測点データ４０１の場合、それぞれの動線データ（Ｔ００１〜Ｔ００３）は６つの観測点データ（観測点ＩＤ＝１〜６）により構成される。一実施形態において、更新部（不図示）は、各セグメントについてデータ列に含まれるデータの数と代表データ列に含まれるデータの数とが同数となるように、データ列を更新する。この処理を行うことにより、各セグメントについての乖離度、すなわち部分動線データと識別部分動線データとの乖離度の算出が容易となる。データ列の更新方法としては、補間処理又は間引き処理等が挙げられる。
【００４７】
ステップＳ５０３〜Ｓ５０８において、代表データ抽出部３０４ａは代表動線データを生成する。本実施形態において代表データ抽出部３０４ａ、動線データを属性ごとに分類し、それぞれの分類について座標値の平均を求めることにより、代表動線データを生成する。また、本実施形態においては属性として性別を用いる。
【００４８】
ステップＳ５０３において代表データ抽出部３０４ａは、あらかじめ属性抽出部３０５により取得されている、図４（Ｂ）に示す属性データ４２１から、動線データに対応する人物の属性値４２２を取得する。ステップＳ５０４で代表データ抽出部３０４ａは全ての動線データについて属性値を取得したか否かを判定し、受け取っている場合は処理はステップＳ５０５へ進み、受け取っていない場合には処理はステップＳ５０３へ戻る。こうして、代表データ抽出部３０４ａはステップＳ５０３の処理を全ての動線データについて属性値を取得するまで繰り返す。図４（Ｂ）に示す属性データ４２１を用いる場合、動線ＩＤがＴ００１又はＴ００３である動線データについては対応する属性値として男性を示す値が取得され、動線ＩＤがＴ００２である動線データについては対応する属性値として女性を示す値が取得される。
【００４９】
ステップＳ５０５において代表データ抽出部３０４ａは、同じ属性を有する動線データに対して、観測点ＩＤごとの座標値の平均を求める。例えば、代表データ抽出部３０４は、属性が男性である動線データ（動線ＩＤ＝Ｔ００１，Ｔ００３）について、まず観測点ＩＤ＝１に対応する座標値の平均値を求める。得られた値（（１００＋１００）／２），（１００＋１００）／２））＝（１００，１００）が、図４（Ｂ）に示す代表動線データの１番目の座標４１４となる。ステップＳ５０６で代表データ抽出部３０４ａは全ての観測点ＩＤに対応する平均値を求めたか否かを判定し、求めている場合は処理はステップＳ５０７へ進み、求めていない場合には処理はステップＳ５０５へ戻る。こうして、代表データ抽出部３０４ａはステップＳ５０３の処理を観測点ＩＤ＝２以降の全ての観測点ＩＤに対応する平均値を求めるまで繰り返す。
【００５０】
ステップＳ５０７においては、ステップＳ５０５により得られた座標値のそれぞれに対して代表動線ＩＤ４１３としてＲ００１を割り振る。こうして、図４（Ｂ）に示す代表動線データ４１１が得られる。ステップＳ５０８で代表データ抽出部３０４ａは全ての属性について代表動線データを生成したか否かを判定し、生成している場合は処理はステップＳ５０９へ進み、生成していない場合には処理はステップＳ５０５へ戻る。こうして、代表データ抽出部３０４ａはステップＳ５０５〜Ｓ５０７の処理を全ての属性について代表動線データを生成するまで繰り返す。例えば、図４（Ａ）に示す観測点データを用いる場合、代表データ抽出部３０４ａは次に属性が女性である動線データ（動線ＩＤ＝Ｔ００２）を用いて図４（Ｃ）に示す代表動線データ４１２を生成する。
【００５１】
ステップＳ５０９において代表データ分割部３０４ｂは、図４（Ｂ）に示す代表動線データ４１１を分割する。例えば、代表データ分割部３０４ｂは、代表動線データ４１１を構成する座標４１４を複数のグループに分割することができる。そして、ステップＳ５１０において識別子付与部３０６は、分割された代表動線データに割り当てる部分動線ＩＤを取得する。例えば、識別子付与部３０６は代表データ格納部３０７に保存されている識別部分動線データに含まれる部分動線ＩＤ４４３を調べ、重複しないように新しい部分動線ＩＤを取得する。新しい部分動線ＩＤとしては、既に使われている部分動線ＩＤの最大値に１を足したものを用いることができる。ここでは、識別子付与部３０６は、新しい部分動線ＩＤとしてＰ００１を取得する。
【００５２】
さらに、ステップＳ５１１において識別子付与部３０６は、ステップＳ５１０において取得した部分動線ＩＤに基づいて、分割された代表動線データに部分動線ＩＤを割り当てる。本実施形態においては、図４（Ｅ）に示すように、分割された監視領域４３１ごとに代表動線データが分割される。より具体的には、監視領域４３１を分割する座標値に従って代表動線データを分割することができる。例えば、代表動線データ４１１に含まれる座標値を、各座標値が１００以上２００未満のもの、２００以上３００未満のもの、及び３００以上で４００未満のものにグループ化することができる。識別子付与部３０６は、それぞれのグループに対して一意な部分動線ＩＤが付されるように、座標値に対して部分動線ＩＤを付与することができる。
【００５３】
監視領域４３１の分割方法はこの方法には限定されない。例えば、監視領域４３１における通路配置等を考慮して、ユーザが手動で監視領域４３１を複数の領域に分割してもよい。また、代表動線データの分割方法もこの方法には限定されない。例えば、代表動線データを、最初にｘ座標値が２００以上となるまでの動線データ、その後ｘ座標値が最初に３００以上となるまでの動線データ、及びｘ座標値が最初に３００以上となった後の動線データ、へと分割することができる。
【００５４】
図４（Ｂ）に示す代表動線データ４１１の場合、１番目及び２番目の座標値、３番目及び４番目の座標値、並びに５番目及び６番目の座標値へと、座標値をグループ分けすることができる。そして、識別子付与部３０６は、それぞれのグループに対して、部分動線ＩＤとしてＰ００１、Ｐ００２、又はＰ００３を付与する。こうして、図４（Ｆ）に示す識別部分動線データ４４１が得られる。
【００５５】
ステップＳ５１２において、代表データ抽出部３０４ａは全ての代表動線データを識別部分動線データに変換したか否かを判定し、変換している場合は処理はステップＳ５１３へ進み、変換していない場合には処理はステップＳ５０９へ戻る。こうして、ステップＳ５０９〜Ｓ５１１の処理が繰り返され、図４（Ｃ）に示す代表動線データ４１２も図４（Ｇ）に示す識別部分動線データ４４２へと変換される。ステップＳ５１３において識別子付与部３０６は、こうして得られた識別部分動線データ４４１，４４２を代表データ保存部３０３に保存する。
【００５６】
図６は、本実施形態においてサーバ１０３が行う識別部分動線データ４４１，４４２の生成処理を示すフローチャートである。図６に示す処理の開始前には、通信部２０４は監視カメラ１０１から映像データを受信しており、データ抽出部３０１は図４（Ｈ）に示す動線データ４５１を抽出してデータ格納部３０２に保存している。
【００５７】
ステップＳ６０１においてデータ分割部３０９ａは、データ格納部３０２から動線データ４５１を取得する。ステップＳ６０２においてデータ分割部３０９ａは、動線データ４５１を分割して部分動線データを生成する。データ分割部３０９ａは、代表データ分割部３０４ｂと同様に、分割された監視領域４３１ごとに動線データ４５１を分割する。例えば、データ分割部３０９ａは、動線データ４５１に含まれる座標値を、各座標値が１００以上２００未満のもの、２００以上３００未満のもの、及び３００以上で４００未満のものにグループ化することができる。図４（Ｈ）に示す動線データ４５１は、こうして動線データ４５１の一部である３つの部分動線データに分割される。そして、観測点ＩＤが１，２の座標値で構成される部分動線データ、観測点ＩＤが３，４の座標値で構成される部分動線データ、及び観測点ＩＤが５，６の座標値で構成される部分動線データが得られる。
【００５８】
ステップＳ６０３において乖離度取得部３０９ｂは、代表データ格納部３０７から、それぞれの代表動線ＩＤ４１３ごとに識別部分動線データ４４１，４４２を取得する。例えば、まず乖離度取得部３０９ｂは、代表動線ＩＤ＝Ｒ００１についての識別部分動線データ４４１を取得する。ステップＳ６０４において乖離度取得部３０９ｂは全ての識別部分動線データを取得したか否かを判定し、取得している場合は処理はステップＳ６０５へ進み、求めていない場合には処理はステップＳ６０３へ戻る。こうして、乖離度取得部３０９ｂは、全ての代表動線ＩＤに対応する識別部分動線データを取得するまでＳ６０３の処理を繰り返す。このようにして、乖離度取得部３０９ｂは、代表動線ＩＤ＝Ｒ００２についての識別部分動線データ４４２も取得する。
【００５９】
ステップＳ６０５において、乖離度取得部３０９ｂは、ステップＳ６０２で得られた部分動線データと識別部分動線データとの乖離度を測定する。本実施形態においては、座標値の二乗誤差が乖離度として用いられる。例えば、乖離度取得部３０９ｂは、まずステップＳ６０１で得られた部分動線データと代表動線ＩＤ＝Ｒ００１についての識別部分動線データ４４１との乖離度を測定する。本実施形態においては、各座標値が１００以上２００未満の部分動線データ、２００以上３００未満の部分動線データ、及び３００以上で４００未満の部分動線データのそれぞれについて乖離度の測定が行われる。例えば、乖離度取得部３０９ｂは、代表動線ＩＤ＝Ｒ００１，部分動線ＩＤ＝Ｐ００１である代表部分動線データを、識別部分動線データ４４１から取得する。そして、乖離度取得部３０９ｂは、この代表部分動線データと、ステップＳ６０２で得られた観測点ＩＤが１，２の座標値で構成される部分動線データとの乖離度を測定する。乖離度は、（（１１０−１００）２＋（１４０−１００）２）＋（（１４０−１５０）２＋（１５０−１５０）２）＝１８００と計算できる。
【００６０】
ステップＳ６０６で乖離度取得部３０９ｂは全ての部分動線データに対して乖離度の測定を行ったか否かを判定し、行っている場合は処理はステップＳ６０７へ進み、行っていない場合には処理はステップＳ６０５へ戻る。こうして、乖離度取得部３０９ｂは全ての部分動線データに対して乖離度の測定を行うまでステップＳ６０５の処理を繰り返す。このようにして、乖離度取得部３０９ｂは、代表動線ＩＤ＝Ｒ００１，部分動線ＩＤ＝Ｐ００２である代表部分動線データと、ステップＳ６０２で得られた観測点ＩＤが３，４の座標値で構成される部分動線データとの乖離度を測定する。この例では、乖離度は２００と計算される。また、乖離度取得部３０９ｂは、代表動線ＩＤ＝Ｒ００１，部分動線ＩＤ＝Ｐ００３である代表部分動線データと、ステップＳ６０２で得られた観測点ＩＤが５，６の座標値で構成される部分動線データとの乖離度を測定する。この例では、乖離度は２６００と計算される。
【００６１】
ステップＳ６０７において乖離度取得部３０９ｂは、ステップＳ６０２で得られた部分動線データと、代表動線ＩＤ＝Ｒ００１の識別部分動線データ４４１との乖離度として、こうしてそれぞれの部分動線データについて計算された乖離度の和を計算する。この例の場合、乖離度は４６００と計算される。
【００６２】
ステップＳ６０８で乖離度取得部３０９ｂは全ての識別部分動線データに対して乖離度の測定を行ったか否かを判定し、行っている場合は処理はステップＳ６０９へ進み、行っていない場合には処理はステップＳ６０３へ戻る。こうして、乖離度取得部３０９ｂはステップＳ６０３〜Ｓ６０７の処理を全ての識別部分動線データに対して乖離度の測定を行うまで繰り返す。このようにして、ステップＳ６０２で得られた部分動線データと代表動線ＩＤ＝Ｒ００２の識別部分動線データ４４２との乖離度も測定される。この例の場合、乖離度は２６００と計算される。
【００６３】
ステップＳ６０９において乖離度取得部３０９ｂは、ステップＳ６０７で計算された乖離度の和が最小となる代表動線ＩＤを取得する。この例では、乖離度取得部３０９ｂは、最小の乖離度２６００を持つ代表動線ＩＤ＝Ｒ００２を取得する。ステップＳ６１０において乖離度取得部３０９ｂは、ステップＳ６０９で取得された代表動線ＩＤを有する識別部分動線データを取得する。この例では、乖離度取得部３０９ｂは、代表動線ＩＤ＝Ｒ００２を持つ識別部分動線データ４４２を取得する。
【００６４】
もっとも、別の実施形態において、識別部分動線データに対しては、識別部分動線データを生成するために用いられた動線データの属性が付与されていてもよい。この場合、乖離度取得部３０９ｂは、ステップＳ６０３〜Ｓ６０９の代わりに、ステップＳ６０１で得られた動線データと同じ属性を有する識別部分動線データを取得することができる。
【００６５】
ステップＳ６１１において乖離度取得部３０９ｂは、ステップＳ６１０で取得された識別部分動線データと、ステップＳ６０２で取得された部分動線データとの乖離度を測定する。この処理はステップＳ６０５と同様に行うことができる。本実施形態においては、ステップＳ６０５で計算された乖離度が記憶されていないことを前提として、乖離度が再び測定される。しかしながら、ステップＳ６１１において乖離度取得部３０９ｂは、ステップＳ６０５で算出した乖離度を取得してもよい。
【００６６】
ステップＳ６１２において識別子置換部３１０は、ステップＳ６１１で得られた乖離度が予め定められた閾値以下であるか否かを判定する。乖離度が閾値以下である場合、処理はステップＳ６１３に進み、乖離度が閾値を超える場合、処理はステップＳ６１４に進む。ステップＳ６１３において識別子置換部３１０は、ステップＳ６１１における乖離度の算出に用いた識別部分動線データの部分動線ＩＤ４４３を、ステップＳ６１１における乖離度の算出に用いた部分動線データに割り当てる。
【００６７】
ステップＳ６１４において識別子置換部３１０は、全ての部分動線データに対してステップＳ６１１〜Ｓ６１３の処理を行ったか否かを判定し、行っている場合は処理はステップＳ６１５へ進み、行っていない場合には処理はステップＳ６１１へ戻る。こうして、全ての部分動線データについてステップＳ６１１〜Ｓ６１３の処理が行われる。
【００６８】
ステップＳ６１１〜Ｓ６１４の処理についてさらに説明する。まず、部分動線ＩＤ＝Ｐ００４の識別部分動線データと、観測点ＩＤ＝１，２の部分動線データとの乖離度が計算され、乖離度の値は９２５となる。この例では閾値としては１０００が用いられ、乖離度は閾値を下回る。そこで、識別子置換部３１０は、識別部分動線データの部分動線ＩＤ＝Ｐ００４を観測点ＩＤ＝１，２の部分動線データに割り当てる。同様に、部分動線ＩＤ＝Ｐ００５の識別部分動線データと、観測点ＩＤ＝３，４の部分動線データとの乖離度は２５０となる。このため、識別子置換部３１０は、識別部分動線データの部分動線ＩＤ＝Ｐ００５を観測点ＩＤ＝３，４の部分動線データに割り当てる。一方で、部分動線ＩＤ＝Ｐ００６の識別部分動線データと、観測点ＩＤ＝５，６の部分動線データとの乖離度は１４２５となる。この乖離度は閾値を超えるため、識別子置換部３１０は観測点ＩＤ＝５，６の部分動線データには部分動線ＩＤを割り当てない。これらの処理の結果、図４（Ｉ）に示すラベル付き動線データ４６１が得られる。
【００６９】
ステップＳ６１５〜Ｓ６１９の処理は、ステップＳ６１１〜Ｓ６１４の処理により得られたラベル付き動線データ４６１のそれぞれのエントリについて行われる。まずステップＳ６１５において識別子置換部３１０は、エントリについて部分動線ＩＤが割り当てられているか否かを判定する。割り当てられていない場合、処理はステップＳ６１９に進む。割り当てられている場合、処理はステップＳ６１６に進む。
【００７０】
ステップＳ６１６において識別子置換部３１０は、処理対象のエントリの座標値を空にする。さらに、ステップＳ６１７において識別子置換部３１０は、動線ＩＤと部分動線ＩＤとの組が重複しているエントリが存在するか否かを判定する。例えば、処理対象のエントリの動線ＩＤと部分動線ＩＤとの組が、既に処理されたエントリについての動線ＩＤと部分動線ＩＤとの組と同じ場合、重複しているエントリが存在すると判定できる。重複しているエントリが存在する場合、処理はステップＳ６１８に進む。重複しているエントリが存在しない場合、識別子置換部３１０は、既に処理されたエントリと同じ動線ＩＤが処理対象のエントリに付されている場合には処理対象のエントリの動線ＩＤを空にする処理を行い、その後処理はステップＳ６１９に進む。ステップＳ６１８において、識別子置換部３１０は重複しているエントリを削除する。例えば、識別子置換部３１０は、処理対象のエントリを削除することができる。
【００７１】
ステップＳ６１９において識別子置換部３１０は、ラベル付き動線データ４６１の全てのエントリについてステップＳ６１５〜Ｓ６１８の処理を行ったか否かを判定する。処理を行っている場合、処理はステップＳ６２０に進み、処理を行っていない場合、処理はステップＳ６１５に戻って次のエントリについて処理が行われる。
【００７２】
ステップＳ６１５〜Ｓ６２０の処理により、ラベル付き動線データ４６１のうち、１番目のエントリについては座標値が空にされる。また、２番目のエントリは１番目のエントリと重複するため削除される。同様に、３番目のエントリについては座標値が空にされ、４番目のエントリは削除される。５，６番目のエントリには部分動線ＩＤが付されていないため、削除処理は行われない。
【００７３】
ステップＳ６２０においてデータ生成部３１１は、ステップＳ６１５〜６２０の処理により得られたエントリを結合して保存データを生成する。このように、図４（Ｉ）に示すラベル付き動線データ４６１から、図４（Ｊ）に示す保存データ４７１が得られる。そして、ステップＳ６２１において、データ保存部３１２は保存データ格納部３１３に保存データ４７１を保存する。
【００７４】
図７は、本実施形態においてサーバ１０３が行う保存データ４７１の復元処理を示すフローチャートである。図７に示す処理の開始前には、保存データ格納部３１３には保存データ４７１が格納されているものとする。ステップＳ７０１において、保存データ取得部３１５は、保存データ格納部３１３から保存データを取得する。本実施形態において保存データ取得部３１５は、入力部２０３を介して指定された動線ＩＤ＝Ｔ０１０を有する保存データ４７１を取得する。
【００７５】
ステップＳ７０２〜Ｓ７０７の処理は、保存データ４７１のそれぞれのエントリについて行われる。ステップＳ７０２において、代表部分データ取得部３１６は、処理対象のエントリに部分動線ＩＤが付されているか否かを判定する。部分動線ＩＤが付されている場合、処理はステップＳ７０３に進む。部分動線ＩＤが付されていない場合、処理はステップＳ７０６に進む。
【００７６】
ステップＳ７０３において代表部分データ取得部３１６は、代表データ格納部３０７から、処理対象のエントリに付されている部分動線ＩＤに対応する識別部分動線データを取得する。ここでは、保存データ４７１の１つ目のエントリは部分動線ＩＤ＝Ｐ００４を有するため、部分動線ＩＤ＝Ｐ００４に対応する識別部分動線データ４４２が取得される。
【００７７】
ステップＳ７０４においてデータ収集部３１７は、保存データの動線ＩＤと、ステップＳ７０３で取得された識別部分動線データ４４２のうち部分動線ＩＤ＝Ｐ００４に対応する座標値と、の組を取得する。ステップＳ７０５においてデータ収集部３１７は、識別部分動線データ４４２のうち部分動線ＩＤ＝Ｐ００４に対応する座標値を全て取得したか否かを判定する。取得している場合、処理はステップＳ７０６に進む。取得していない場合、処理はステップＳ７０４に戻り、データ収集部３１７は、保存データの動線ＩＤと、識別部分動線データ４４２のうち部分動線ＩＤ＝Ｐ００４に対応する次の座標値と、の組を取得する。この例においては、動線ＩＤ＝Ｔ０１０と座標値（１００，１００）との組がまず取得され、次に動線ＩＤ＝Ｔ０１０と座標値（１１５，１４０）との組が次に取得される。
【００７８】
ステップＳ７０６においてデータ収集部３１７は、保存データの動線ＩＤと、処理対象のエントリの座標値と、の組を取得する。
【００７９】
ステップＳ７０７においてデータ収集部３１７は、保存データ４７１の全てのエントリについてステップＳ７０２〜Ｓ７０６の処理を行ったか否かを判定する。処理を行っている場合、処理はステップＳ７０８に進む。処理を行っていない場合、処理はステップＳ７０２に戻り、次のエントリを処理対象として処理が行われる。この例では、２つ目のエントリには部分動線ＩＤ＝Ｐ００５が付されているので、同様に動線ＩＤ＝Ｔ０１０と座標値（２２０，２２０）との組が取得され、さらに動線ＩＤ＝Ｔ０１０と座標値（２５５，２４５）との組が取得される。その次のエントリには部分動線ＩＤが付されていないので、保存データの４７１動線ＩＤ＝Ｔ０１０と座標値（３３０，３５０）との組が取得される。最後のエントリについても同様に、動線ＩＤ＝Ｔ０１０と座標値（３５０，３５０）との組が取得される。
【００８０】
ステップＳ７０８においてデータ収集部３１７は、ステップＳ７０２〜Ｓ７０７の処理で取得した動線ＩＤと座標値との組を結合する。そして、それぞれのエントリに観測点ＩＤを１から順に振ることにより、図４（Ｋ）に示す復元動線データ４８１を得ることができる。復元動線データ４８１においては、保存データ４７１に付されている動線ＩＤが全ての行に割り当てられており、保存データ４７１の基となった動線データ４５１と同様の構成を有している。
【００８１】
以上のように、本実施形態に係る動線データの圧縮処理及び復元処理を行うことができる。本実施形態においては、動画から抽出した属性値を用いて代表動線データが生成された。具体的には、属性ごとに動線データを分類して、動線データの座標値の平均を求めることにより代表動線データが生成された。しかしながら、時刻又は通路ごとに平均を求める等の他の方法を用いて代表動線データを生成することもできる。また、座標値の二乗誤差を乖離度として用いたが、座標値の絶対値誤差又は離散化された誤差等を乖離度として用いることもできる。また、乖離度としては、動線データが示す動線と代表動線データが示す動線との乖離を示す任意の値を用いることができる。例えば、動線データが示す動線と代表動線データが示す動線とによって囲まれる領域の面積を、乖離度として用いることもできる。この場合、それぞれの動線データを構成する観測点の数を一定にすることは必須ではない。
【００８２】
本実施形態では、動線データを分割して得られた部分動線データを代表部分動線データの識別子で置換することにより、動線データを圧縮してデータサイズを小さくすることができる。また、乖離度の高い部分については元の部分動線データが保持されるため、通常の動きとは異なる情報価値の高い動線データを正確に復元することができる。
【００８３】
［実施形態２］
実施形態１では、属性値に従って動線データを分類して代表動線データを生成し、座標区間に基づいて代表動線データを分割して代表部分動線データを生成した。そして、部分動線データと代表部分動線データとの乖離度に従って部分動線データを識別子へと置換した。実施形態２では、機械学習を用いて代表部分動線データが生成され、代表部分動線データと部分動線データとの乖離度が求められる。
【００８４】
本実施形態では、機械学習を用いたクラスタリングにより、類似性に基づいて複数の動線データをいくつかのグループへとグループ化する。１つのクラスタには類似した動線データが含まれ、１つのクラスタに含まれる動線データには同じクラスタＩＤが付与される。そして、同じクラスタに含まれるデータ列から、代表データ列が生成される。
【００８５】
また、１つの動線データはいくつかの動きに分割され、それぞれの動きはいくつかのトピックに分類される。１つのトピックには類似した動きが含まれ、１つのトピックに含まれる動きには同じトピックＩＤが付与される。本実施形態において、１つの動きは１以上の観測点データで表され、観測点データにトピックＩＤが付与される。この結果、同じトピックＩＤが付された動きは同じ領域における動きを表すこととなり、トピックＩＤに従って動線データを領域分割することが可能となる。本実施形態では、このような機械学習のアルゴリズムとして、Ｄｕａｌ−ＨＤＰを用いた例について説明する。Ｄｕａｌ−ＨＤＰについては、Wang et al. Unsupervised activity perception in crowded and complicated scenes using hierarchical bayesian models. IEEE Transactions on Pattern Analysis and machine Intelligence, 2009, volume 31, issue 3, page 539.に詳しく記載されている。
【００８６】
本実施形態においては、まず、全ての動線データを用いたＤｕａｌ−ＨＤＰモデルの学習が行われる。次に、学習したモデルを用いて類似した動線データに同じラベルが付与される。そして、同じラベルが付与された動線データの座標値の平均を取ることにより代表動線データが生成される。次に、学習したモデルを用いて代表動線データが分割され、ラベルを付与することで代表部分動線データが得られる。同様に、学習したモデルを用いて動線データが分割され、ラベルを付与することで代表部分動線データが得られる。そして、実施形態１と同様に代表部分動線データと部分動線データとの乖離度が測定され、乖離度に基づいて圧縮が行われる。
【００８７】
本実施形態に係る監視システムのサーバ１０３は、図３に示すように実施形態１と同様の構成を有するが、属性抽出部３０５が機械学習部８０１及びモデル格納部８０２を備えている。機械学習部８０１は、複数の動線データを受け取ってモデルの学習を行い、学習したモデルをモデル格納部８０２に保存する。また、機械学習部８０１は、学習したモデルを用いて動線データを代表部分動線データに分割する。他のモジュールは実施形態１と同様である。
【００８８】
図９（Ａ）は、動線データの構成の一例を示す。動線データ９０１は、観測点ＩＤ４０２、動線ＩＤ４０３、座標４０４、トピックＩＤ９０２、及びクラスタＩＤ９０３を有する。動線データ９０１は、それぞれの観測点データに対してＤｕａｌ−ＨＤＰのモデルを用いてトピックＩＤ９０２とクラスタＩＤ９０３とを割り当てることにより得られる。類似している動線データに対しては同じクラスタＩＤ９０３が割り当てられるように、クラスタＩＤ９０３の割り当ては行われる。また、動線データを部分動線データへと分割した際に、部分動線データの各座標値が似た傾向にある場合には同じ値が割り振られるように、トピックＩＤ９０２の割り当ては行われる。
【００８９】
図９（Ｂ）（Ｃ）は、代表動線データの構成の一例を示す。代表動線データ９１１，９１２は、代表動線ＩＤ４１３、座標４１４、およびトピックＩＤ９０２を有する。代表動線データ９１１，９１２は、同じクラスタＩＤを有する動線データのグループごとに生成される。また、座標４１４は、同じクラスタＩＤを有する動線データについて、観測点ＩＤごとに座標値の平均を求めることにより得られる。
【００９０】
図９（Ｄ）（Ｅ）は、識別部分動線データの構成の一例を示す。識別部分動線データ９２１，９２２は、代表動線ＩＤ４１３、部分動線ＩＤ４４３、座標４１４を有する。識別部分動線データ９２１，９２２は、代表動線データ９１１，９１２をトピックＩＤに基づいて分割して得られたそれぞれの代表部分動線データに対してユニークな部分動線ＩＤ４４３を割り当てることにより得られる。
【００９１】
図９（Ｆ）は、動線データの構成の一例を示す。動線データ９３１は、動線ＩＤ４０３、座標４０４、及びトピックＩＤ９０２を有する。動線データ９３１は、動線データに対してＤｕａｌ−ＨＤＰのモデルを用いてトピックＩＤ９０２を割り当てることにより得られる。
【００９２】
本実施形態に係る圧縮方法を、図１０，１１のフローチャートに従って説明する。図１０は、本実施形態においてサーバ１０３が行う識別部分動線データ９２１，９２２の生成処理を示すフローチャートである。
【００９３】
ステップＳ１００１及びＳ１００２は、ステップＳ５０１及びＳ５０２と同様に行われる。ここでは、動線ＩＤ＝Ｔ００１の動線データ、動線ＩＤ＝Ｔ００２の動線データ、及び動線ＩＤ＝Ｔ００３の動線データが取得される。
【００９４】
ステップＳ１００３において機械学習部８０１は、ステップＳ１００１〜Ｓ１００２で取得された動線データの集合を用いてＤｕａｌ−ＨＤＰのモデルを学習する。ステップＳ１００４において機械学習部８０１は、学習したモデルをモデル格納部８０２に保存する。
【００９５】
ステップＳ１００５において代表データ分割部３０４ｂは、得られたモデルを用いて動線データにクラスタＩＤ９０３とトピックＩＤ９０２とを割り当てる。ステップＳ１００６において代表データ分割部３０４ｂは全ての動線データに対してクラスタＩＤ及びトピックＩＤの割り当てを行ったか否かを判定する。行っている場合は処理はステップＳ１００７へ進み、行っていない場合には処理はステップＳ１００５へ戻って次の動線データに対して処理が行われる。こうして、代表データ分割部３０４ｂは全ての動線データに対してクラスタＩＤ及びトピックＩＤを割り当てる。
【００９６】
ステップＳ１００７〜Ｓ１０１０において代表データ抽出部３０４ａは代表動線データを生成する。ステップＳ１００７において代表データ抽出部３０４ａは、１つのクラスタＩＤ及び１つの観測点ＩＤに着目し、同じクラスタＩＤを有する動線データのグループについての、同じ観測点ＩＤを有する座標値の平均を求める。ステップＳ１００８において代表データ抽出部３０４ａは、全ての観測点ＩＤについて処理を行ったか否かを判定する。行っている場合は処理はステップＳ１００９へ進み、行っていない場合には処理はステップＳ１００７へ戻って次の観測点ＩＤについて処理が行われる。こうして、着目クラスタＩＤを有する動線データについて、観測点ＩＤごとの平均座標値が得られる。
【００９７】
ステップＳ１００９において代表データ抽出部３０４ａは、観測点ＩＤごとに得られた平均座標値に同じ代表動線ＩＤを割り当てる。さらに代表データ抽出部３０４ａは、平均座標値の算出に用いられた座標値が有するトピックＩＤのうち、最も多くの座標値が有しているトピックＩＤを選択し、得られた平均座標値に選択されたトピックＩＤを割り当てる。こうして、図９（Ｂ）（Ｃ）に示す代表動線データが得られる。ステップＳ１０１０において代表データ抽出部３０４ａは、全てのクラスタＩＤについて処理を行ったか否かを判定する。行っている場合は処理はステップＳ１０１１に進み、行っていない場合には処理はステップＳ１００９へ戻って次のクラスタＩＤについて処理が行われる。こうして、クラスタＩＤごとに代表動線データが生成される。
【００９８】
ステップＳ１００３〜Ｓ１０１０の処理について詳しく説明する。図４（Ａ）に示すデータを用いる例では、図４（Ａ）に示す３つの動線データを用いてモデルの学習が行われ、それぞれの動線データにトピックＩＤ及びクラスタＩＤが割り振られる。こうして、動線データ９０１が得られる。次に、代表データ抽出部３０４ａは、クラスタＩＤ＝Ｃ００１である動線データについての代表動線データを生成する。具体的には、代表データ抽出部３０４ａは、クラスタＩＤ＝Ｃ００１であり、観測点ＩＤ＝１である座標値の平均を求めることにより、平均座標（１００，１００）を得る。同様に、代表データ抽出部３０４ａは、観測点ＩＤが２以降である座標値の平均を順次求める。また、代表データ抽出部３０４ａは、クラスタＩＤ＝Ｃ００１であり、観測点ＩＤ＝１である座標値に最も多く割り当てられているトピックＩＤを、求められた平均座標についてのトピックＩＤとして得る。同様に、代表データ抽出部３０４ａは、観測点ＩＤが２以降である座標値を用いて求めた平均座標についてもトピックＩＤを求める。そして、代表データ抽出部３０４ａは、平均座標の全てに代表動線ＩＤ９１３としてＲ００１を割り振り、平均座標のそれぞれに求められたトピックＩＤを割り振ることで、図９（Ｂ）に示す代表動線データ９１１を得る。代表データ抽出部３０４ａは、同様の処理をクラスタＩＤ＝Ｃ００２である動線データについても行うことにより、図９（Ｃ）に示す代表動線データ９１２を得る。
【００９９】
ステップＳ１０１１〜Ｓ１０１５の処理は、ステップＳ５０９〜Ｓ５１３と同様に行われる。ただし、本実施形態のステップＳ１０１１において代表データ分割部３０４ｂは、トピックＩＤが同じである代表動線ＩＤと座標との組を、１つの代表部分動線データとして取得する。そして、識別子付与部３０６はそれぞれの代表部分動線データにユニークな部分動線ＩＤを割り当てる。こうして図９（Ｄ）（Ｅ）に示す識別部分動線データ９２１，９２２が得られ、代表データ保存部３０３に格納される。
【０１００】
図１１は、本実施形態においてサーバ１０３が行う保存データの生成処理を示すフローチャートである。図１１に示す処理の開始前には、通信部２０４は監視カメラ１０１から映像データを受信しており、データ抽出部３０１は図４（Ｈ）に示す動線データ４５１を抽出してデータ格納部３０２に保存している。
【０１０１】
ステップＳ１１０１においてデータ分割部３０９ａは、データ格納部３０２から動線データ４５１を受け取る。ステップＳ１１０２において、データ分割部３０９ａは、モデル格納部８０２に格納されているモデルを用いて、ステップＳ１１０１で得られた動線データ４５１にトピックＩＤ９０２を割り当てる。こうして、図９（Ｆ）に示す動線データ９３１が得られる。
【０１０２】
ステップＳ１１０３においてデータ分割部３０９ａは、動線データ９３１を分割して部分動線データを生成する。本実施形態においてデータ分割部３０９ａは、トピックＩＤが同じエントリが１つの部分動線データに含まれるように部分動線データを生成する。その後は、実施形態１のステップＳ６０３〜Ｓ６２１と同様に処理が行われ、保存データが生成される。本実施形態においても、各セグメントについてデータ列（部分動線データ）に含まれるデータの数と代表データ列（識別部分動線データ）に含まれるデータの数とが同数となるようにデータ列を更新してから、乖離度の算出を行うことができる。
【０１０３】
本実施形態では、学習を用いることにより、複数の動線データの間で共通の代表部分動線データを生成する。このために、圧縮対象となる動線データとの乖離度が小さい部分動線データが得られる可能性を向上させることができる。このために、識別子による部分動線データの置換率が上がり、情報の損失を抑えながらより大きなデータ圧縮が可能となる。
【０１０４】
［実施形態３］
実施形態１では、乖離度が小さい場合には部分動線データを識別子に置換し、乖離度が大きい場合には部分動線データの座標値を保持するように、保存データを生成した。実施形態３では、乖離度が閾値より大きい部分動線データについては、代表データ列を示す識別子（部分動線ＩＤ）と、データ列（部分動線データ）と代表データ列（識別部分動線データ）との差分データ列と、が出力される。以下では、部分動線データと識別部分動線データとの座標値の差分を取り、その差分の値を可変量符号化して保存データを生成する方法について述べる。ここでは座標値が２バイトで表現されているものとする。
【０１０５】
ＳＳ６０１〜Ｓ６１９の処理は実施形態１と同様に行われるが、本実施形態においては乖離度が閾値を超える部分動線データに対しても、ステップＳ６１１における乖離度の算出に用いられた識別部分動線データの部分動線ＩＤ４４３が割り当てられる。ステップＳ６２０においてデータ生成部３１１は、識別子に置換されなかった部分動線データと、ステップＳ６１１における乖離度の算出に用いられた識別部分動線データ４４２との間で、各観測点について座標値の差分を求める。具体的には、１つ目の観測点についての差分は（３３０−３１５，３３０−３１０）＝（１５，２０）となり、２つ目の観測点についての差分は（−２０，−２０）となる。そして、データ生成部３１１は、得られた各々の差分の値に１バイトの符号を割り当てる。こうして、２バイトの座標値を１バイトの差分符号に置き換えることができる。この処理を乖離度が大きい部分動線データの各観測点について行った後に、データ生成部３１１は得られたエントリを結合して保存データを生成する。
【０１０６】
復元処理においては、保存データのエントリのうち座標がないものに対しては、部分動線ＩＤに対応する座標値が取得される。一方で、保存データのエントリのうち座標があるものに対しては、部分動線ＩＤに対応する座標値を用いて、元の座標値が復元される。
【０１０７】
本実施形態によれば、部分動線データと代表部分動線データとの比較により座標値の差分が求められる。こうして求められた差分は元の座標値より小さくなることが期待できるため、より小さな符号を割り当てることができ、保存データのデータ量を小さくすることが可能となる。
【０１０８】
［実施形態４］
実施形態１においては、生成された保存データ４７１は直ちに保存データ格納部３１３に保存された。実施形態４では、保存データの圧縮率を算出し、算出された圧縮率に基づいて保存データの生成方式が変更される。具体的には、データ列に対する変換データの圧縮率が所定値未満であるか否かが判定され、圧縮率が所定値未満である場合、変換データの代わりにデータ列に基づく別のデータが出力される。この場合に出力される別のデータは特に限定されるわけではなく、変換される前のデータ列をそのまま出力してもよいし、変換される前のデータ列を圧縮してから出力してもよい。本実施形態においては、算出された圧縮率の値が予め定められた値以上である場合には保存データ４７１がそのまま保存される。一方で、そうでない場合は、識別子置換部３１０による変換処理に従って得られる保存データ４７１の代わりに、変換処理を行う前の動線データ４５１が保存される。
【０１０９】
６つの観測点データで構成される動線データは、例えば、２４バイトの動線ＩＤ（４バイト×６行）及び２４バイトの座標値（２バイト×２値×６行）で構成され、データ量の合計が４８バイトでありうる。以下の説明では、予め定められた圧縮率を２５％とし、圧縮率（圧縮によるデータの削減率）が２５％以上（データ量が３６バイト以下）となる場合に保存データを保存する場合について説明する。
【０１１０】
ステップＳ６０１〜Ｓ６２０の処理は実施形態１と同様に行われ、保存データ４７１が得られる。保存データ４７１は、１６バイトの動線ＩＤ（４バイト×４行）、８バイトの部分動線ＩＤ（４バイト×２行）、及び８バイトの座標値（２バイト×２値×２行）で構成され、データ量の合計は３２バイトである。よって、データ保存部３１２は、得られた保存データ４７１の圧縮率が予め定められた値以上であると判定し、保存データ４７１を保存する。もし、得られた保存データ４７１の圧縮率が予め定められた値未満である場合、データ保存部３１２は識別子による置換を行う前の動線データ４５１を保存する。
【０１１１】
本実施形態によれば、目標のデータ圧縮率が達成されない場合には置換処理を行う前の動線データが保存される。このため、復元処理にかかる負荷を軽減することができる。また、予め定められた圧縮率により、復元された動線データのデータ精度を制御することができる。
【０１１２】
［実施形態５］
実施形態５では、実施形態１の処理に加えて、識別部分動線データが更新された場合に保存データ格納部３１３に格納されている保存データの更新が行われる。本実施形態においては特に、新たな識別部分動線データが得られ、ＲＡＭ２０６に新しく記憶された場合に、新たな識別部分動線データを用いて保存データが再圧縮される。この際には、新たな識別部分動線データを用いて動線データを圧縮した際の圧縮率が算出され、算出された圧縮率に基づいて保存データを再圧縮するか否かが判定される。
【０１１３】
ステップＳ６０１〜Ｓ６２０の処理は実施形態１と同様に行われ、保存データ４７１が得られる。実施形態４で説明したように、この保存データのサイズは３２バイトである。
【０１１４】
新たな識別部分動線データが得られると、データ復元部３１４は識別部分動線データ（代表データ列）を参照して保存データ４７１から復元動線データ４８１（復元データ列）を復元する。データ置換部３０８は、新たな識別部分動線データ及び復元動線データ４８１を用いて、ステップＳ６１０〜Ｓ６２０と同様に復元動線データ４８１を変換して新たな保存データを生成する。すなわち、新たな代表データ列（識別部分動線データ）が得られた場合に、複数のセグメントに分割された復元データ列と、複数のセグメントに分割された新たな代表データ列と、の乖離度が各セグメントについて判定される。そして、乖離度が閾値以下であるセグメントを新たな代表データ列を用いた第１の表現で表し、乖離度が閾値を超えるセグメントを第２の表現で表すように、復元データ列が新たな変換データへと変換される。
【０１１５】
そして、データ保存部３１２は、新たな変換データが元の変換データ（保存データ４７１）よりも小さいか否かを判定し、新たな変換データが元の変換データよりも小さい場合、元の変換データを新たな変換データで置換する。例えば、本実施形態において、データ保存部３１２は、新たに生成された保存データの圧縮率を、保存データ４７１の圧縮率と比較する。新たに生成された保存データの圧縮率が保存データ４７１の圧縮率よりも大きい場合、データ保存部３１２は新たに生成された保存データを保存データ格納部３１３に格納し、保存データ４７１を破棄する。そうではない場合、データ保存部３１２は新たに生成された保存データを保存データ格納部３１３に格納せず、保存データ４７１を維持する。例えば、新たに生成された保存データのデータサイズが６０バイトである場合、保存データ４７１のデータサイズよりも大きい（すなわち圧縮率が小さい）ため、保存データの置換処理は行われない。
【０１１６】
本実施形態では、新たな識別部分動線データが生成された時に、新たな識別部分動線データに基づく保存データのデータ量が小さくなる場合にのみ、この保存データが格納される。このため、格納される保存データのデータ量を小さくすることが可能となる。
【０１１７】
［実施形態６］
実施形態６では、データ列に対する変換データの圧縮率が所定値以上であるか否かと、データ列の生成時刻が所定時刻以後であるか否かと、の少なくとも一方が判定される。そして、この判定に応じて変換データの出力先が変更される。例えば、得られた保存データの格納場所を、動線データの観測時刻と保存データの圧縮率との少なくとも一方に従って変更することができる。
【０１１８】
本実施形態では、現在時刻と観測時刻の差が１０分以内であるか否か、及び保存データの圧縮率が２５％以上であるか否かに基づいて、保存データの格納場所が変更される。実施形態４で説明したように、動線データのデータ量が４８バイトである場合、データ量が３６バイト以下である場合に圧縮率は２５％以上となる。例えば、保存データの大きさが３６バイト以内であり、かつ保存データの大きさが３６バイト以下である場合、保存データはＲＡＭ２０６に保存される。一方で、現在時刻と観測時刻の差が１０分より大きい場合、又は保存データの大きさが３６バイトより大きい場合、保存データは記憶部２０７に保存する。
【０１１９】
現在時刻に近い観測時刻における動線データは、参照される可能性が高い。このため、このような動線データをＲＡＭ２０６のような高速なメモリに格納することにより、レイテンシを削減することができる。また、高速なメモリには圧縮率の高い保存データを格納することで、メモリに格納される保存データの数を増やすことができる。一方で、あまり使われにくい又はデータ量の大きい保存データは、必要なときにのみ取り出すことが可能となる。
【０１２０】
［実施形態７］
実施形態１では、代表動線データを識別部分動線データへと分割するのと同じ方法で、動線データを部分動線データへと分割した。実施形態７では、代表動線データとの乖離度に応じて、動線データの分割方法を変更する。
【０１２１】
本実施形態においては、代表動線データ４１１，４１２を参照して、動線データ４５１から保存データが生成される。まず、乖離度取得部３０９ｂは、１番目の観測点データから順に、動線データ４５１と代表動線データ４１１，４１２との座標間距離の二乗を求める。そして、乖離度取得部３０９ｂは、この値に従って、動線データ４５１と代表動線データ４１１，４１２との比較を行う。
【０１２２】
例えば、乖離度取得部３０９ｂは、実施形態１と同様に、動線データ４５１との乖離度が最小となる代表動線データを選択することができる。ここでは、代表動線データ４１１が選択されたものとする。動線データ４５１と代表動線データ４１１とを比較すると、１番目の観測点データについては距離の二乗は（１００−１１０）＾２＋（１００−１１０）＾２＝２００となる。２番目以降の観測点データについては、順に１００，１００，１００，８００，１８００となる。
【０１２３】
次に乖離度取得部３０９ｂは、部分動線データの最初の観測点データから順に距離の二乗を合計していき、合計値が予め定められた閾値に達する点で動線データを分割する。例えば、１番目からＮ番目までの合計値が閾値を超える場合には、１番目からＮ−１番目までの観測点データが含まれるラベル付き動線データを生成する。そして、識別子置換部３１０は、ラベル付き動線データの部分動線ＩＤとして、対応する代表動線データの代表動線ＩＤを割り当てる。また、識別子置換部３１０は、ラベル付き動線データに、代表動線データの対応する観測点データ群のうち最初の座標値と最後の座標値とを割り当てる。また、識別子置換部３１０は、１番目についての距離の二乗が閾値を超える場合にも、１番目の観測点データのみを含むラベル付き動線データを生成する。この場合、識別子置換部３１０は、ラベル付き動線データに、動線データに含まれる観測点データの座標値を割り当てる。こうして、動線データの部分動線データへの分割が行われる。
【０１２４】
ここでは、閾値が５００である場合について説明する。動線データ４５１については、１番目から４番目までの観測点データについての距離の二乗の和は５００となるため、１番目から４番目までの観測点データを有する部分動線データが生成される。この部分動線データに対しては、部分動線ＩＤとして対応する代表動線データの代表動線ＩＤ＝Ｒ００１が割り振られる。また、座標として代表動線データの対応する区間を示す座標値「（１００，１００）、（２５０，２５０）」が割り振られる。この過程では、１番目の観測点データを含む部分動線データ、１番目から２番目までの観測点データを含む部分動線データ、及び１番目から３番目までの観測点データを含む部分動線データと、対応する代表動線データとの比較が順次行われているといえる。
【０１２５】
同様に、５番目の観測点データについての距離の二乗は８００となるため、５番目の観測点データを有する部分動線データが生成される。乖離度は閾値である５００を超えているため、座標としては動線データ４５１の座標値である「（３３０，３３０）、（３３０，３３０）」が割り振られる。さらに、６番目の観測点データを有する部分動線データが生成される。乖離度は閾値である５００を超えているため、座標としては動線データ４５１の座標値である「（３５０，３５０）、（３５０，３５０）」が割り振られる。結果として、図８に示すラベル付き動線データ１２０１が得られる。
【０１２６】
図８は、ラベル付き動線データの構成の一例を示す。ラベル付き動線データ１２０１は、動線ＩＤ４０３、部分動線ＩＤ１２０２、及び座標１２０３を有する。ラベル付き動線データ１２０１は、動線データを距離の二乗和に基づいて区切ることによって得られたデータであり、部分動線ＩＤ１２０２として対応する代表動線ＩＤ４１３を有し、座標として始点と終点の座標を保持している。このように、乖離度が小さい区間（１番目のエントリ）については、動線データが代表動線データで置換され、動線データの観測点データの代わりに、代表動線データの識別子及び置換された区間が記録される。一方で、乖離度が大きい区間（２，３番目のエントリ）については、動線データは代表動線データで置換されず、動線データの観測点データが記録される。
【０１２７】
本実施形態では、圧縮対象の動線データごとにデータの分割方法を変えることができるため、圧縮効率が上がり、保存データのデータ量を小さくすることが可能となる。上記の例では、変換データが小さくなるように複数の分割方法から選択された分割方法に従ってデータ列が分割される。特に、上記の方法によれば距離の二乗の合計が閾値以内でできるだけ大きくなるように、すなわち代表動線データとの乖離度が閾値を超えない条件で部分動線データができるだけ長くなるように動線データの分割が行われる。このため、精度を保証しながらラベル付き動線データのデータ量をできるだけ小さくすることができる。
【０１２８】
動線データの分割方法は上記の方法には限られない。例えば、２つ以上の異なる方法で動線データを分割し、それぞれの場合について乖離度が閾値以下となる区間について動線データを代表動線データで置換することで、複数のラベル付き動線データを生成することができる。そして、データ量が最も小さいラベル付き動線データが得られる分割方法、及びこの方法により生成されたラベル付き動線データを採用することができる。
【０１２９】
（その他の実施例）
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【０１３０】
１０３：サーバ、３０９ａ：データ分割部、３０９ｂ：乖離度取得部、３１１：データ生成部、３１２：データ保存部
【図１】
2017041794.tif 000003
【図２】
2017041794.tif 000004
【図３】
2017041794.tif 000005
【図４】
2017041794.tif 000006
【図５】
2017041794.tif 000007
【図６】
2017041794.tif 000008
【図７】
2017041794.tif 000009
【図８】
2017041794.tif 000010
【図９】
2017041794.tif 000011
【図１０】
2017041794.tif 000012
【図１１】
2017041794.tif 000013