(57)【要約】【課題】安定した特徴量の抽出を可能とすることにより精度の高い行動識別を可能とする。【解決手段】本発明の一態様としての行動識別装置は、観測領域における移動体の２次元位置を所定時間間隔で記録した時系列データを記憶する時系列データ記憶部と、前記時系列データの一部を部分時系列データとして選択し、前記部分時系列データを、互いに直交する２つの軸により規定される２次元座標系にプロットし、プロットされた点群の輪郭を算出する輪郭算出部と、前記輪郭の幾何的な特徴を表す複数の特徴量を抽出する特徴抽出部と、前記特徴抽出部により抽出された複数の特徴量に基づいて前記移動体の行動を識別する行動識別部と、を備える。【選択図】図１
2009134600.tif 000002
【特許請求の範囲】
【請求項１】
観測領域における移動体の２次元位置を所定時間間隔で記録した時系列データを記憶する時系列データ記憶部と、
前記時系列データの一部を部分時系列データとして選択し、前記部分時系列データを、互いに直交する２つの軸により規定される２次元座標系にプロットし、プロットされた点群の輪郭を算出する輪郭算出部と、
前記輪郭の幾何的な特徴を表す複数の特徴量を抽出する特徴抽出部と、
前記特徴抽出部により抽出された複数の特徴量に基づいて前記移動体の行動を識別する行動識別部と、
を備えた行動識別装置。
【請求項２】
前記輪郭算出部は、前記輪郭として凸包を算出することを特徴とする請求項１に記載の行動識別装置。
【請求項３】
前記複数の特徴量は、
前記輪郭の面積と、
前記輪郭の長径と、
前記輪郭の短径と、
前記長径および前記短径間の比率であるアスペクト比率と、
前記輪郭の重心と、
前記輪郭を構成する点の個数と前記輪郭の内側に含まれる点の個数間の比率である点比率と、
のうち少なくとも２つ以上を含むことを特徴とする請求項１または２に記載の行動識別装置。
【請求項４】
前記輪郭算出部は、
前記部分時系列データと一部重複するように前記時系列データから第２の部分時系列データを選択し、
（１）前記第２の部分時系列データに含まれずかつ前記部分時系列データに含まれる第１の位置を特定し、前記第１の位置を表す第１の点が前記部分時系列データから得られた前記凸包の頂点に一致するときは、前記第１の点の両側に位置する２つの頂点を特定し、前記第２の部分時系列データを前記２次元座標系にプロットして得られる点群のうち前記凸包の演算方向において前記２つの頂点間に位置する点を用いて、前記２つの頂点間における前記凸包を更新し、
（２）前記第２の部分時系列データに含まれかつ前記部分時系列データに含まれない第２の位置を前記第２の部分時系列データから特定し、前記第２の位置を表す第２の点が、前記部分時系列データから得られた前記凸包の外側に存在するときは、前記第２の点から前記凸包に対して２つの接線を引きかつ前記２つの接線が接する２つの頂点の一方から他方へ向けて前記第２の点が存在する側の経路で前記凸包を辿ったときに通過する線分を前記凸包から削除する
ことにより前記第２の部分時系列データに対応する第２の凸包を得る、
ことを特徴とする請求項２に記載の行動識別装置。
【請求項５】
観測領域における移動体の２次元位置を所定時間間隔で記録した時系列データを読み込む時系列データ読み込みステップと、
前記時系列データの一部を部分時系列データとして選択し、前記部分時系列データを、互いに直交する２つの軸により規定される２次元座標系にプロットし、プロットされた点群の輪郭を算出する輪郭算出ステップと、
前記輪郭の幾何的な特徴を表す複数の特徴量を抽出する特徴抽出ステップと、
前記特徴抽出ステップにより抽出された複数の特徴量に基づいて前記移動体の行動を識別する行動識別ステップと、
を備えた行動識別方法。
【請求項６】
前記輪郭算出ステップは、前記輪郭として凸包を算出することを特徴とする請求項５に記載の行動識別方法。
【請求項７】
前記複数の特徴量は、
前記輪郭の面積と、
前記輪郭の長径と、
前記輪郭の短径と、
前記長径および前記短径間の比率であるアスペクト比率と、
前記輪郭の重心と、
前記輪郭を構成する点の個数と前記輪郭の内側に含まれる点の個数間の比率である点比率と、
のうち少なくとも２つ以上を含むことを特徴とする請求項５または６に記載の行動識別方法。
【請求項８】
前記輪郭算出ステップは、
前記部分時系列データと一部重複するように前記時系列データから第２の部分時系列データを選択し、
（１）前記第２の部分時系列データに含まれずかつ前記部分時系列データに含まれる第１の位置を特定し、前記第１の位置を表す第１の点が前記部分時系列データから得られた前記凸包の頂点に一致するときは、前記第１の点の両側に位置する２つの頂点を特定し、前記第２の部分時系列データを前記２次元座標系にプロットして得られる点群のうち前記凸包の演算方向において前記２つの頂点間に位置する点を用いて、前記２つの頂点間における前記凸包を更新し、
（２）前記第２の部分時系列データに含まれかつ前記部分時系列データに含まれない第２の位置を前記第２の部分時系列データから特定し、前記第２の位置を表す第２の点が、前記部分時系列データから得られた前記凸包の外側に存在するときは、前記第２の点から前記凸包に対して２つの接線を引きかつ前記２つの接線が接する２つの頂点の一方から他方へ向けて前記第２の点が存在する側の経路で前記凸包を辿ったときに通過する線分を前記凸包から削除する
ことにより前記第２の部分時系列データに対応する第２の凸包を得る、
ことを特徴とする請求項６に記載の行動識別方法。
【請求項９】
観測領域における移動体の２次元位置を所定時間間隔で記録した時系列データを読み込む時系列データ読み込みステップと、
前記時系列データの一部を部分時系列データとして選択し、前記部分時系列データを、互いに直交する２つの軸により規定される２次元座標系にプロットし、プロットされた点群の輪郭を算出する輪郭算出ステップと、
前記輪郭の幾何的な特徴を表す複数の特徴量を抽出する特徴抽出ステップと、
前記特徴抽出ステップにより抽出された複数の特徴量に基づいて前記移動体の行動を識別する行動識別ステップと、
をコンピュータに実行させるための行動識別プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体の行動を識別する行動識別装置、行動識別方法および行動識別プログラムに関する。
【背景技術】
【０００２】
監視対象の行動を自動識別する機能を持つサーベイランスシステムの開発が様々な研究機関で進行している。行動識別を行う識別器に入力として与えるデータとしては、画像処理等によって得られる歩行軌跡データが主流の一つになりつつある。歩行軌跡データは2次元平面上の移動履歴であり、実数の組のシーケンスからなる不定長時系列データである
【従来の課題】
【０００３】
歩行軌跡データからの特徴抽出方法としては移動速度及び角度変化量等に基づくアプローチがある。しかし、これら移動速度及び角度変化量等の値は、測定誤差による位置のずれ、および観測時間の不定等に起因する誤差のため、安定して抽出することが困難である問題がある。
【０００４】
一般的に誤差に対する対策としてはノイズの傾向をモデル化し除去を行う方法が考えられるが、センサーとして画像処理システムを想定した場合、ノイズは場所や時間帯に依存するため汎用なモデルを構築することは困難である。
【特許文献１】特開２００７−２４１４４５号公報
【非特許文献１】浅野哲夫著 計算幾何―理論の基礎から実装まで―（共立出版 2007 ISBN-10: 4320121767 ）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、安定した特徴量の抽出を可能とすることにより精度の高い行動識別を可能とした行動識別装置、方法およびプログラムを提供する。
【課題を解決するための手段】
【０００６】
本発明の一態様としての行動識別装置は、
観測領域における移動体の２次元位置を所定時間間隔で記録した時系列データを記憶する時系列データ記憶部と、
前記時系列データの一部を部分時系列データとして選択し、前記部分時系列データを、互いに直交する２つの軸により規定される２次元座標系にプロットし、プロットされた点群の輪郭を算出する輪郭算出部と、
前記輪郭の幾何的な特徴を表す複数の特徴量を抽出する特徴抽出部と、
前記特徴抽出部により抽出された複数の特徴量に基づいて前記移動体の行動を識別する行動識別部と、
を備える。
【０００７】
本発明の一態様としての行動識別方法は、
観測領域における移動体の２次元位置を所定時間間隔で記録した時系列データを読み込む時系列データ読み込みステップと、
前記時系列データの一部を部分時系列データとして選択し、前記部分時系列データを、互いに直交する２つの軸により規定される２次元座標系にプロットし、プロットされた点群の輪郭を算出する輪郭算出ステップと、
前記輪郭の幾何的な特徴を表す複数の特徴量を抽出する特徴抽出ステップと、
前記特徴抽出ステップにより抽出された複数の特徴量に基づいて前記移動体の行動を識別する行動識別ステップと、
を備える。
【０００８】
本発明の一態様としての行動識別プログラムは、
観測領域における移動体の２次元位置を所定時間間隔で記録した時系列データを読み込む時系列データ読み込みステップと、
前記時系列データの一部を部分時系列データとして選択し、前記部分時系列データを、互いに直交する２つの軸により規定される２次元座標系にプロットし、プロットされた点群の輪郭を算出する輪郭算出ステップと、
前記輪郭の幾何的な特徴を表す複数の特徴量を抽出する特徴抽出ステップと、
前記特徴抽出ステップにより抽出された複数の特徴量に基づいて前記移動体の行動を識別する行動識別ステップと、
をコンピュータに実行させる。
【発明の効果】
【０００９】
本発明により、安定した特徴量の抽出を可能とすることにより精度の高い行動識別を可能とする。
【発明を実施するための最良の形態】
【００１０】
図１は本発明の一実施形態としての行動識別装置の全体構成を示すブロック図である。
【００１１】
センサーデバイス１１は、観測領域を移動する移動体（たとえば歩行者）を観測することにより、移動体の位置を所定時間間隔で記録した歩行軌跡データ（時系列データ）を取得する。歩行軌跡データはたとえばｘ座標およびｙ座標からなる２次元データである。
【００１２】
センサーデバイス１１がビデオカメラ（監視カメラ）及び画像処理機能を含む場合、監視カメラにより移動体を一定時間撮影し、その後、画像処理機能により、各フレームにおける位置座標の連続系列を、歩行軌跡データとして取得する。画像処理機能では、色追跡等の移動体追跡技術を用いることができる。
【００１３】
凸包算出部１２は、センサーデバイス１１によって取得された歩行軌跡データを入力として受け取る。凸包算出部１２は、受け取った歩行軌跡データ（時系列データ）を記憶する時系列データ記憶部を含む。凸包算出部１２は、歩行軌跡データに含まれる位置座標を、時点数入力部１３から入力される時点数N（一定区間）だけ部分歩行軌跡データとして抽出する。ユーザはたとえば時点数入力部１３を用いて、アプリケーションを介して、対話的に、時点数Ｎを入力することが可能である。
【００１４】
凸包算出部１２は、抽出した部分歩行軌跡データを２次元座標系にプロットして凸包を求め、凸包のデータ、および凸包に含まれる各点（内点）のデータを出力する。凸包は、部分歩行軌跡データを２次元座標系にプロットして得られる点群の輪郭の一例に相当する。
【００１５】
歩行軌跡データから抽出する位置座標は、連続するN時点の位置座標でもよいし、所定間隔で抽出したN時点数の位置座標でもよい。凸包算出部１２は、上記時点数Nの一定区間を、所定の時点数（たとえば１時点）だけスライドさせながら部分歩行軌跡データを逐次取得する。すなわち前回取得した部分時系列データと一部重複するように第２の部分時系列データを取得する。たとえば抽出した部分歩行軌跡データにおいて時間的に最も古い位置座標を削除し、かつ部分歩行軌跡データに含まれない新しい時点の位置座標を取得するようにして、部分歩行軌跡データを逐次取得する。
【００１６】
特徴抽出部１４は、凸包算出部１２から凸包のデータ、および凸包に含まれる各点のデータを入力として受け取り、当該凸包の幾何的な特徴を表す複数の特徴量を計算し、計算した複数の特徴量を、上記一定区間の特徴量ベクトルとして出力する。凸包の幾何的な特徴を表す複数の特徴量は、上記部分歩行軌跡データの輪郭の幾何的な特徴を表す複数の特徴量に相当する。
【００１７】
特徴量データベース（特徴量ＤＢ）１６は、特徴量ベクトルと、行動の種別を表す行動ラベルとを対応づけた学習データを記憶している。
【００１８】
行動識別部１５は、特徴抽出部１４により抽出された特徴量ベクトルを入力として受け取り、受け取った特徴量ベクトルと特徴量データベース１６とを用いて、移動体の行動識別を行い、識別した行動を表す行動ラベルを出力する。たとえばk-NN法等を用いて、特徴量ベクトルと特徴量データベース１６との比較により行動識別を行うことができる。あるいは、行動識別部１５が、特徴量データベース１６に蓄えられた学習データからSupport Vector Machine・Neural Net等の自動識別器を生成し、生成した自動識別器に、特徴量ベクトルを入力することにより、行動識別を行ってもよい。識別する行動種別としては、たとえば停止・歩行・走行等の行動が考えられる。なお、識別結果を収集して蓄積することでより抽象度の高い行動の予測や分析も可能になる。
【００１９】
以下では、凸包算出部１２と特徴抽出部１４についてさらに詳細に説明する。
【００２０】
［凸包算出部１２］
凸包算出部１２は、上述したように、センサーデバイス１１から入力された歩行軌跡データから、N個の位置座標からなる部分歩行軌跡データを抽出する。抽出した部分歩行軌跡データを２次元平面にプロットし、プロット間を線分により時系列に接続した例を図２（Ａ）に示す。
【００２１】
図２（Ａ）から理解されるように、N時点の位置座標からなる部分歩行軌跡データは、1本の時系列としてイメージされる。この時系列としてイメージされる部分歩行軌跡データを、時点間の順序性を取り去って、図２（Ｂ）に示すように、N個の点からなる点集合としてとらえることが可能である。
【００２２】
凸包算出部１２は、図２（Ｂ）に示すような点集合から凸包を算出する。凸包は、点集合における各点の間に定義される線分を全て内部領域に含むものである。図２（Ｂ）の点集合から算出される凸包のイメージを図３に示す。2次元平面上の点集合から凸包を算出するアルゴリズムと数学的背景に関しては非特許文献１（浅野哲夫著 計算幾何―理論の基礎から実装まで― 、共立出版 2007、ISBN-10: 4320121767 ）に詳しい。
【００２３】
以下では上記非特許文献１の方法に従い、N時点の位置座標からなる部分歩行軌跡データから凸包を算出する過程を一例として示す。
【００２４】
まず説明を行う前に、凸包を算出するアルゴリズムで用いられる、三角形の符号付き面積について図4を用いて説明する。
【００２５】
三角形の符号付き面積Sは、３つの点を T1(x1、y1)、T2(x2、y2)、T3(x3、y3)としたとき、以下の式で計算される。
【数１】
2009134600.tif 000003
【００２６】
三角形上の各点T1,T2,T3が反時計回りに配置されている場合、Sの値は正となり、逆に時計回りの場合は負となる。また３つの点が直線状に並ぶ場合にはSの値は0となる。この性質を利用すると、２つの点T1,T2が与えられていた場合、３つ目の点T3が直線T1-T2のどちら側に存在するかを決定することが可能になる。凸包の算出ではこの性質が利用される。
【００２７】
図１８は、凸包算出アルゴリズムの全体の流れを概略的に示すフローチャートである。
【００２８】
Step1では、入力としてN個の点を含む点集合が与えられ、また外周点集合Oおよび内点集合Iを初期化する。入力された点集合は、最終的に、「外周点集合（頂点集合）」と「内点集合」に分離して出力される。外周点集合Oは、最終的に、凸包をなす点（外周点あるいは頂点）の集合であり、内点集合Iは、凸包の内側に存在する内点の集合（外周点集合O以外の全ての点からなる点集合）である。
【００２９】
Step2では、入力として与えられた点集合（N個の点からなる）から、ｘ座標およびｙ座標が同一である重複座標を取り除き、同一の点が１つしか含まれないようにする。したがって、Step2の結果として得られる点集合には、N’（≦N）個の点が含まれる。
【００３０】
Step3ではN’個の点をx座標について整列する。凸包算出アルゴリズムの性質上、x座標ではなくy座標をベースにして処理を実行することも可能であるが、ここでは直観的な理解の容易さを優先しx座標による整列を行うとする。
【００３１】
Step4では、x座標が最大および最小のものを凸包の両端点として外周点集合に加える。どちらの点も、凸包に属する（凸包の頂点に該当する）ことは明らかである。なお、外周点集合は順序付けされており、外周点集合内の各点は、ｘ座標の順（ここでは昇順）に並べられる。
【００３２】
Step5は凸包算出アルゴリズムの本体をなすもので、実際に凸包を算出する。具体的には、まず凸包の上半分（上部辺）をなす点集合を求め、その後、Step6にて残りの下半分（下部辺）をなす点集合を求める。
【００３３】
凸方の上半分（上部辺）の計算では、左端点から3つの点を選択して符号付き面積を計算し、負（右回り）であればそれらの点を外周点集合に含める。符号付き面積が正（左回り）であれば外周点集合に最後に追加された点を削除し、外周点集合に最後から３番目に追加された点と、最後から第２番目に追加された点と、新たに選択する点との３点で同様の処理を行う。N’個の点から両端点を除いたすべて点について、この処理を繰り返す。以下、凸包の上半分を求める計算について、具体例を用いて、詳細に説明する。
【００３４】
図5は凸包計算の開始状態（最初の段階）を示す。入力された点集合は点P1〜点P7からなり、先ほどのStep4では、両端点の点P1と点P7とが外周点集合に加えられたとする。
【００３５】
次の段階では、図6に示すように、外周点集合に、点P1の次にｘ座標が大きい点P2を含める。外周点集合のサイズが3を超えない場合、無条件に新しい点を含める。
【００３６】
次の段階では、次にｘ座標が大きい点P3を選択し、三角形(P1,P2,P3)の点配置を、上述した符号付き面積を用いて判定する。配置（P1→P2→P3）が右回りの場合、点P3は、凸包の頂点（外周点）と見なし、点P3を外周点集合に含める。ここでは図７に示すように、右回りであるため、点P3を外周点集合に含める。
【００３７】
次の段階では、図8に示すように、図7と同様にして、三角形（P2,P3,P4）の点配置を判定し、配置が右回りであるため、点P4を外周点集合に含める。
【００３８】
次の段階では、図９に示すように、図7および図８と同様にして、三角形（P3,P4,P5）の点配置を判定し、配置が右回りであるため、点P5を外周点集合に含める。
【００３９】
次の段階では、三角形（P4,P5,P6）の点配置を判定するが、判定の結果、これら３つの点は左周りに配置されているため、図１０に示すように、外周点集合において最も新しい要素である点P5を削除する。
【００４０】
次の段階では、三角形（P3,P4,P6）の点配置を判定するが、判定の結果、これら３つの点は左周りに配置されているため、図１１に示すように、外周点集合において最も新しい要素である点P4を削除する。
【００４１】
次の段階では、三角形（P2,P3,P6）の点配置を判定し、判定の結果、これらの３つの点は右回りであるため、図１２に示すように、点P6を外周点集合に含める。
【００４２】
以上により、全ての点について判定が終了し、結果として、図１３に示すように、点P1,P2,P3,P6,P7が、上部辺の点集合（上側点集合）として確定する。上側点集合に含まれない残りの点は、下部辺の点集合（下側点集合）の候補となる。なお、両端点は上側点集合および下側点集合に共通に含まれると考える。
【００４３】
Step6では、Step5と同様の手法により、下側点集合の候補を用いて、下側点集合を求める。ただし、上述した上側点集合の場合は、点配置が負の場合（右回りの場合）に外周点集合への追加を行ったが、下側点集合の場合は、三角形の符号付き面積が正の場合に、外周点集合への追加を行う。上側点集合および下側点集合のいずれにも含まれなかった点集合は、最終的には内点集合（凸包の内側に存在する点集合）として扱われる。
【００４４】
図５に示したアルゴリズムは全体としてN2のオーダー（O(N2)）の計算量で動作するが、その理由はStep2において重複を取り除く処理を行うためである。またはStep3において整列処理を行うためである。
【００４５】
ただし、図５に示したアルゴリズムは、移動体の追跡開始時（計算開始時）の凸包算出方法を示したものであり、これより後の追跡での凸包計算は、一旦算出した凸包の一部分を更新することにより得ることが可能であり、この場合O(N)の計算量で凸包を算出することが可能である。これは本実施形態の大きな特徴の１つである。
【００４６】
図１９は、凸包の更新アルゴリズムの全体の流れを概略的に示すフローチャートである。
【００４７】
Step11では、前回処理対象となったN個の点から削除される削除点（第２の部分時系列データに含まれず部分時系列データに含まれる第１の位置を表す第１の点）と、新規に追加される追加点（第２の部分時系列データに含まれ部分時系列データに含まれない第２の位置を表す第２の点）とが指定される。削除点は、前回のN個の点のうち、最も古い点であり、追加点は、前回のN個の点のうち最も新しい点の次に取得された点である。ここでは図１４のように削除点と追加点が指定されたとする。削除点と追加点とを指定されたら、削除点が外周点集合（前回得られた外周点集合）に含まれているかどうかを検査し、含まれているときは削除点を外周点集合から削除し、含まれないときは内点集合（前回得られた内点集合）から削除する。
【００４８】
Step12では、外周点集合から削除された削除点に対し隣り合う２つの外周点（頂点）を特定し、凸包の演算方向（ここではｘ軸方向）において、特定した外周点間に存在する内点集合を抽出する。
【００４９】
Step13では、Step12で抽出した内点集合を対象として、凸包算出アルゴリズムのStep5を適用することにより、上記２つの外周点間の範囲において外周点（頂点）を再計算する。なお、上記追加点がこの範囲に含まれるときは、この追加点も本ステップの演算対象に含めるものとする。図14の例では、点線Ｌ１、Ｌ２間に存在する内点集合が対象とされ。点線Ｌ１上の点Ｋ１と、点線Ｌ２上の点Ｋ２が両端点として計算が行われる。計算の結果、図１５に示すように、新たな外周点Ｈが見つかり、外周点集合に追加される。
【００５０】
Step14では、追加点が凸包（Step12で更新されたときは更新後の凸包）の内側にあるか、外側（凸包上を含む）にあるかを判定する。この判定は、たとえば以下のようにして行う。図１６に別の例として示す５角形の凸包において、凸包内側の一点を選択し、選択点（図中三角で示される）から各外周点（図中丸で示される）に線分を引き、これにより凸包を複数の三角形領域１〜５に分割する。そして、追加点が三角形領域１〜５のいずれかに含まれるかどうかを検査し、いずれの三角形領域にも属さなければ追加点は凸包の外側にあると判定し、いずれかの三角形領域に属すれば凸包の内側にあると判定する。
【００５１】
追加点が三角形領域に属するか否かの判定は、前述した三角形の符号付き面積を用いて行うことができる。たとえば三角形領域１に属するか否かの判定は以下のようにして行う。追加点と、辺Ｔ１の両端点との間で符号付き面積を計算することにより辺Ｔ１からみて追加点が領域１側およびその反対側のいずれに位置するかを調べる。辺Ｔ２、辺Ｔ３についても同様にして符号付き面積を計算して、追加点が領域１側およびその反対側のいずれに位置するかをそれぞれ調べる。辺Ｔ１〜辺Ｔ３の全てについて領域１側に位置するとの判定が得られたとき、追加点は領域１に含まれ、それ以外のときは領域１に含まれないと判定する。
【００５２】
Step15では、追加点が凸包の内側にある場合は、追加点を内点集合へ含める。追加点が凸包の外側にある場合は、追加点から凸包に対して２つの接線を引き、それらの接点（接点は外周点（頂点）である）を求める。そして、求めた接点の一方から他方へ向けて上記追加点が存在する側の経路で凸包を辿ったときに通過する外周点を外周点集合から削除し、削除した外周点を内点集合に含める。そして、追加点を外周点集合に含める。図１４の例では、追加点から接線Ｒ１、Ｒ２が引かれることにより外周点Ｋ１、Ｋ３が接点として計算され、外周点Ｋ１、Ｋ３の間の外周点Ｋ４を、外出点集合から削除する。そして、削除した外周点Ｋ４を、図１５に示すように、内点集合に登録し、また追加点を外周点集合に含める。
【００５３】
追加点から凸包に対する２つの接点は、以下のようにして求めることが可能である。図１６と同様に５角形の凸包を例にして説明する。図１７（Ａ）の接線領域図（左側用）に示すように、５角形の各辺を特定の方向に延長することにより、凸包の外側領域を領域１Ａ〜５Ａに分割する。また図１７（Ｂ）の接線領域図（右側用）に示すように、５角形の各辺を、図１７（Ａ）とは逆の方向に延長することにより、凸包の外側領域を領域１Ｂ〜５Ｂに分割する。そして、図１７（Ａ）および図１７（Ｂ）のそれぞれにおいて追加点がいずれの領域に属するかを判定し、属する領域に応じて決まる点（外周点あるいは頂点）を接点として選択する。たとえば追加点が領域３Ａおよび領域４Ｂに属するときは、前者に対応して点３、後者に対応して点４を接点として選択する。追加点がどの領域に属するか否かは、前述の符号付き面積を利用して求めることができる。たとえば図１７（Ａ）において、追加点が、５角形の各辺の両側のうちいずれの側に属するかを、符号付き面積を利用して求め、その結果を総合判定することで、追加点が属する領域を求めることができる。
【００５４】
Step16では、更新された凸包（更新された外周点集合）、および更新された内点集合を出力する。更新された凸包はたとえば第２の凸包に相当する。
【００５５】
以上に説明した凸包更新アルゴリズムの計算は、上述したように、O(N)の計算量で可能である。すなわち、重複点の除去（図５のStep2参照）は追加点に対するチェックのみで良く、したがって、重複点の除去処理は、O(N)の計算量で完了する。また、凸包更新アルゴリズムでは、図５の凸包算出アルゴリズムと異なり、整列操作は必要としない。また、Step13の処理は、いったん外周点集合の候補から除外された点が、新たに外周点集合に含まれるか否かの演算の対象となることはないため、O(N)以下の計算量で完了する（これは凸包算出アルゴリズムのStep15にも言えることである）。Step14の処理は、各三角形領域に追加点が含まれるかどうかを判定すればよいため、O(N)以下の計算量で終了する。Step15の処理は凸包の各辺について図１７（Ａ）および図１７（Ｂ）に示した処理をそれぞれ１回実行すればよいのでO(2*N)=O(N)以下の計算量で完了する。よって、全体として凸包更新アルゴリズムはO(N)以下の計算量で実行可能である。
【００５６】
［特徴抽出部１４］
図１の特徴抽出部１４は凸包算出部１２にて算出された凸包（外周点集合）と内点集合とを入力として受け取り、当該凸包の幾何的な特徴を表す複数の特徴量を計算する。特徴量の例を以下に示す。
（１）凸包の面積：凸包の面積は、図１６のように凸包内の一つの内点をランダムに指定し、指定点から各頂点に線分を引くことにより凸包を領域分割し、各三角形の面積を合計することで得られる。内点は、内点集合の任意の点を選んでもよいが、外周点集合の重心を計算し、重心を用いてもよい。三角形の面積は、前述の符号付き面積の絶対値を計算することにより計算可能である。
（２）凸法の長径：長径は外周点集合上の最も距離の離れた２点の組であり、単純には全ての２点の組み合わせをチェックすることで得られる。 
（３）凸包の短径：短径は外周点集合上の隣接していない２点のうちで最も距離の短い２点の組であり長径と同様に、２点の各組み合わせをチェックすることで得られる。
（４）アスペクト比率：アスペクト比率は、まずX軸方向の最大値と最小値及びY軸方向の最大値と最小値を持つ外周点を整列によって得、次に、X軸方向の最大値と最小値の差分と、Y軸方向の最大値と最小値の差分との比率を計算することによって得られる。
（５）重心：重心はｘ座標およびｙ座標からなる2次元ベクトルとなるが、ｘ座標およびｙ座標のいずれも独立して特徴ベクトルの要素となる。
（６）周上点比率：周上点比率は外周点集合の要素数と、内点集合の要素数の比を計算することで得られる。
【００５７】
以上のように、本実施の形態によれば、同一の現象に対して、安定した特徴量の抽出を可能とすることにより精度の高い行動識別が可能となる。また動的な再計算方法を用いて凸包を算出することで、計算量を低次に抑え、リアルタイム処理が可能になる。
【産業上の利用可能性】
【００５８】
本発明の応用先の一例としては不審者検出等を行うセキュリティ分野がある。特徴量データベースには不審者ではない者から取得したデータを格納し、それらのデータの特徴を学習することで、データの傾向から離れたものを不審者として識別することができる。
【００５９】
また別の応用例としてはスポーツデータの分析がある。TV中継等から得られたサッカー選手の移動履歴は歩行軌跡データとみなすことが可能であり、一試合分の歩行軌跡データから停止・歩行・走行等の行動ラベル集合を取得し蓄積する。そして、蓄積した行動ラベル集合を、得点数等のコンディションを示す数値と関連づけることでコンディションに関する判別を行うことや、当日の予想得点数に関する回帰分析を行うことが可能になる。
【図面の簡単な説明】
【００６０】
【図１】本発明の一実施形態としての行動識別装置の全体構成を示すブロック図
【図２】歩行軌跡データの例を示す図
【図３】凸包のイメージを示す図
【図４】三角形の符号付き面積の計算方法を説明する図
【図５】凸包の算出過程を説明する図
【図６】図５に続く、凸包の算出過程を説明する図
【図７】図６に続く、凸包の算出過程を説明する図
【図８】図７に続く、凸包の算出過程を説明する図
【図９】図８に続く、凸包の算出過程を説明する図
【図１０】図９に続く、凸包の算出過程を説明する図
【図１１】図１０に続く、凸包の算出過程を説明する図
【図１２】図１１に続く、凸包の算出過程を説明する図
【図１３】図１２に続く、凸包の算出過程を説明する図
【図１４】凸包更新処理において追加点と削除点とを示す図
【図１５】更新された凸包を示す図
【図１６】凸包を複数の三角形に分割した状態を示す図
【図１７】接点の特定方法を説明する図
【図１８】凸包算出アルゴリズムの全体の流れを示すフローチャート
【図１９】凸包更新アルゴリズムの全体の流れを示すフローチャート
【符号の説明】
【００６１】
１１：センサーデバイス
１２：凸包算出部（時系列データ取得部、輪郭算出部）
１３：時点数入力部
１４：特徴抽出部
１５：行動識別部
１６：特徴量データベース
【図１】
2009134600.tif 000004
【図２】
2009134600.tif 000005
【図３】
2009134600.tif 000006
【図４】
2009134600.tif 000007
【図５】
2009134600.tif 000008
【図６】
2009134600.tif 000009
【図７】
2009134600.tif 000010
【図８】
2009134600.tif 000011
【図９】
2009134600.tif 000012
【図１０】
2009134600.tif 000013
【図１１】
2009134600.tif 000014
【図１２】
2009134600.tif 000015
【図１３】
2009134600.tif 000016
【図１４】
2009134600.tif 000017
【図１５】
2009134600.tif 000018
【図１６】
2009134600.tif 000019
【図１７】
2009134600.tif 000020
【図１８】
2009134600.tif 000021
【図１９】
2009134600.tif 000022