(57)【要約】オブジェクト毎に測定されたパラメータセットを経時的に記録するデータセットを得るように、オブジェクトデータを処理し、測定されたオブジェクトのパラメータセットを行動といつ関連付けられるかを識別する学習用入力を提供し、それぞれの値の範囲にあるパラメータセットのうちのどのパラメータが行動を特徴付けるかを判断するために、学習用入力と組み合わせてデータセットを処理し、特徴的なパラメータおよびその特徴的な範囲を使用して、第２のオブジェクトデータを処理し、かつ行動が発生する時を自動的に識別する処理において使用するために、それぞれの値の範囲にあるパラメータセットのうちのどのパラメータが行動を特徴付けるかを識別する情報を送信することによって、１つまたは複数のオブジェクトの行動を自動的に特徴付ける。また、１つ以上のオブジェクトを追跡する方法も開示される。【選択図】図２
2009531049.tif 000002
【特許請求の範囲】
【請求項１】
１つまたは複数のオブジェクトの行動を自動的に特徴付けるための方法であって、
オブジェクト毎に測定されたパラメータセットを経時的に記録するデータセットを得るように、オブジェクトデータを処理することと、
オブジェクトの前記測定されたパラメータセットを行動といつ関連付けられるかを識別する学習用入力を提供することと、
前記パラメータセットのうちのどのパラメータが、どの値の範囲において、前記行動を特徴付けるかを判断するために、前記学習用入力と組み合わせて前記データセットを処理することと、
前記特徴的なパラメータおよびその特徴的な範囲を使用して第２のオブジェクトデータに対して行う処理であって、前記行動が発生する時を自動的に識別する処理において使用するために、前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかを識別する情報を送信することと、
を含む、方法。
【請求項２】
前記独立移動オブジェクトは、相対的に独立運動が可能な動物である、請求項1に記載の方法。
【請求項３】
前記動物は齧歯類である、請求項2に記載の方法。
【請求項４】
前記動物はハエである、請求項2に記載の方法。
【請求項５】
前記動物はゼブラフィッシュである、請求項2に記載の方法。
【請求項６】
前記動物はヒトである、請求項2に記載の方法。
【請求項７】
前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかを判断すべく前記学習用入力と組み合わせて前記データセットを処理することは、学習機構の使用を伴う、請求項１から６のいずれかに記載の方法。
【請求項８】
前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかを判断すべく前記学習用入力と組み合わせて前記データセットを処理することは、遺伝的アルゴリズムの使用を伴う、請求項１から７のいずれかに記載の方法。
【請求項９】
前記遺伝的アルゴリズムにおいて使用される染色体は、前記測定されたパラメータセットにおける前記パラメータ毎に、スイッチオンまたはオフであり得る遺伝子を含む、請求項8に記載の方法。
【請求項１０】
前記遺伝的アルゴリズムに使用される染色体は、前記行動を特徴付けるために必要なパラメータのクラスタの数を特定する遺伝子を含む、請求項8または9に記載の方法。
【請求項１１】
前記遺伝的アルゴリズムに使用される染色体は、染色体の適合が評価される時間を特定する遺伝子を含む、請求項8、9、または10に記載の方法。
【請求項１２】
前記遺伝的アルゴリズムにより使用される染色体の集団からの染色体は、パラメータ空間と、前記パラメータ空間が分割されるクラスタの数とを規定し、また、前記クラスタ内にある前記データセットの下位セットが、行動に関連付けられる前記データセットの下位セットと相関する度合いは、前記染色体の適合を決定する、請求項8から11のいずれかに記載の方法。
【請求項１３】
前記オブジェクトデータは映像である、請求項１から１２のいずれかに記載の方法。
【請求項１４】
前記特徴付けられる行動は、移動オブジェクトの相互作用である、請求項１から１３のいずれかに記載の方法。
【請求項１５】
請求項1から14のいずれかに記載の前記方法における各ステップを実行するためのコンピュータプログラム。
【請求項１６】
１つまたは複数のオブジェクトの行動を自動的に特徴付けるためのシステムであって、
測定された、オブジェクトのパラメータセットが、行動といつ関連付けられるかを識別する学習用入力を提供するための手段と、
前記パラメータセットのうちのどのパラメータが、どの値の範囲において、前記行動を特徴付けるかを判断するために、前記オブジェクト毎に前記測定されたパラメータセットを前記学習用入力と組み合せて経時的に記録するデータセットを得るための手段と、
前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかの情報を出力する手段と、
を含む、システム。
【請求項１７】
１つ以上のオブジェクトを追跡するための方法であって、
１つまたは複数の第１の基準を満たす連続データ値の第１の離散群を識別するために、第１のデータを処理することと、
１つまたは複数の第２の基準を満たす連続データ値の第２の離散群を識別するために、後続の第２のデータを処理することと、
前記第１の群と前記第２の群との間のマッピングを行うことと、
第２の群が単一のオブジェクトを表すか、または複数のオブジェクトを表すかについて判断するために、前記マッピングを使用することと、
前記第２の群が単一のオブジェクトを表すと判断される場合、前記第２の群の１つ以上のパラメータを測定することと、
前記第２の群がN（N>1）個のオブジェクトを表すと判断される場合、１つまたは複数の前記第２の基準を満たす連続データ値のN個の下位群に前記第２の群を分解すべく前記第２の群を処理することと、
前記下位群の前記１つ以上のパラメータを測定することと、
前記複数の下位群を前記複数のオブジェクトにマッピングすることと、
を含む、方法。
【請求項１８】
前記複数の下位群をそれぞれのオブジェクトにマッピングすることは、測定されるパラメータの一致に基づく、請求項17に記載の方法。
【請求項１９】
前記測定されるパラメータは距離である、請求項18に記載の方法。
【請求項２０】
前記複数の下位群をそれぞれのオブジェクトにマッピングすることは、測定されるパラメータの変更率の一致に基づく、請求項17から19のいずれかに記載の方法。
【請求項２１】
前記複数の下位群をそれぞれのオブジェクトにマッピングすることは、測定されるパラメータの履歴に基づく、請求項17から20のいずれかに記載の方法。
【請求項２２】
前記複数の下位群をそれぞれのオブジェクトにマッピングすることは、１つまたは複数の第３の基準が満たされる場合に第１の方法に従い、また、前記複数の下位群をそれぞれのオブジェクトにマッピングすることは、１つまたは複数の第４の基準が満たされる場合に第２の方法に従う、請求項17から21のいずれかに記載の方法。
【請求項２３】
前記第１の方法は、第１の測定されるパラメータを使用する、請求項22に記載の方法。
【請求項２４】
前記第２の方法は、前記第１の測定されるパラメータの経時的な変動に依存する値を使用する、請求項23に記載の方法。
【請求項２５】
前記第１のデータは第１の映像フレームであり、前記第２のデータは後続の第２の映像フレームであり、前記データ値は画素値である、請求項17から22のいずれかに記載の方法。
【請求項２６】
前記複数の下位群をそれぞれのオブジェクトにマッピングすることは、前記第１のフレームにおけるオブジェクトからの、前記第２のフレームにおける下位群の距離の測定に基づくが、但し、前記距離の最短距離が閾値を上回らない場合は、前記第１のフレームを含む前のフレームから導かれる移動オブジェクトの動きの測定と、前記移動オブジェクトの予測位置からの前記第２のフレームにおける下位群の距離とに基づく、請求項25に記載の方法。
【請求項２７】
１つまたは複数の基準を満たす連続画素値の離散群を識別するために映像フレームを処理することを更に含み、この処理は、サイズが（h×w）の前記第１の映像フレームを複数のウィンドウに分割すること、及び平均閾値化を各ウィンドウに個別に実行することを含む、請求項25または26のいずれかに記載の方法。
【請求項２８】
前記第１の群と前記第２の群との間のマッピングを行うことは、前記第１の群のうちの１つが進入（または退去）したように見え、また、同時に前記第２の群のうちの１つが退去（または進入）したように見える「不一致」イベントの識別と、進入（または退去）したように見える前記第１の群の前記１つを、同時に退去（または進入）したように見える前記第２の群の前記１つにマッピングすることを強制することと、を伴う、請求項17から27のいずれかに記載の方法。
【請求項２９】
前記第２の群のうちの１つ以上が、前記第１のフレームと比較して進入または退去したように見えるか否かに関わらず、前記第１の群と前記第２の群との間にマッピングすることにおけるコンフリクトを解決することをさらに含む、請求項17から28のいずれかに記載の方法。
【請求項３０】
前記測定されるパラメータには、面積（area）、方向（orientation）、位置（position）、速度（velocity）のうちの１つ以上が含まれる、請求項17から29のいずれかに記載の方法。
【請求項３１】
１つまたは複数の前記第１の基準ならびに１つまたは複数の第２の基準は同一である、請求項17から30のいずれかに記載の方法。
【請求項３２】
連続画素値の離散群を識別するための１つまたは複数の前記基準は動的である、請求項1から30のいずれかに記載の方法。
【請求項３３】
請求項17から32のいずれかに記載の方法を実行するためのコンピュータプログラム。
【請求項３４】
１つ以上のオブジェクトを追跡するためのシステムであって、
１つまたは複数の第１の基準を満たす連続データ値の第１の離散群を識別するために、第１のデータを処理し、
１つまたは複数の第２の基準を満たす連続データ値の第２の離散群を識別するために、後続の第２のデータを処理し、
前記第１の群と前記第２の群との間のマッピングを実行し、
第２の群が単一のオブジェクトを表すか、または複数のオブジェクトを表すかについて判断するために、前記マッピングを使用し、
前記第２の群が単一のオブジェクトを表すと判断される場合、前記第２の群の１つ以上のパラメータを測定し、
前記第２の群がN（N>1）個のオブジェクトを表すと判断される場合、１つまたは複数の前記第２の基準を満たす連続データ値のN個の下位群に前記第２の群を分解すべく前記第２の群を処理し、
前記下位群の前記１つ以上のパラメータを測定し、
前記複数の下位群を前記複数のオブジェクトにマッピングする、
ように動作可能なプロセッサを備える、
システム。  
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、オブジェクトの行動を自動的に特徴付けるための、コンピュータにより実装される方法に関する。
【発明の背景】
【０００２】
キイロショウジョウバエ（fruit-fly Drosophila melanogaster）の求愛行動に関する詳細な分析は、科学研究で日常的に使用される行動に関する主要例である。我々の研究では、神経機能の調査のためにこれを用いてきた。研究室においても野外においても、測定される様々な行動に共通して、研究には、熟練の専門スタッフであっても時間を要し且つ若干主観的となる手作業の採点手順を伴う。これは、明らかに費用を要しかつ信頼性のないステップであるため、現代の研究においてはそのようなステップを最小限に抑える必要がある。
【０００３】
例えば、WO02/43352（Clever Sys社）において、映像を使用してオブジェクトの行動を分類する方法について記載している。専門家は、まず、標準的なオブジェクトの種々の行動を、質的にも量的にもまず識別および分類しなければならない。例えば、マウスの行動には、立ち上がる、座る、横たわる、正常、異常などの行動が含まれ得る。これは、時間を要する処理である。新しい映像クリップを分析する際、システムは、まず、映像画像背景を入手し、それを使用して前景オブジェクトを識別する。前景オブジェクトの分析は、フレーム毎の特徴空間で行われてもよい。この場合、この特徴には、重心、オブジェクトの主要な方向や角度、面積などが含まれる。入手した特徴を使用して、事前に規定された分類のうちの１つにマウスの状態を分類する。
【０００４】
このような行動の自動分析は、多くの制限を有しており、本発明において概説されるように、生物またはその他の移動オブジェクトの行動の分析に関するこのような問題を対処することが望ましい。
【０００５】
対処すべき第１の問題は、オブジェクトの映像列を減らしたとしてもオブジェクトの相互作用を特徴付けることが可能な、適切且つ小さな時空間データセットを如何に効果的に識別するかということにある。
【０００６】
第２の問題は、任意の時に、一方のオブジェクトが別のオブジェクトを少なくとも部分的に遮蔽する場合に、コンピュータを使用して、個々のオブジェクトを如何に自動的に識別するかということにある。
【特許文献１】WO02/43352
【発明の簡単な説明】
【０００７】
本発明の一実施形態によると、オブジェクトの行動を自動的に特徴付けるための方法が提供される。この方法は、
オブジェクト毎に測定されたパラメータセットを経時的に記録するデータセットを得るようにオブジェクトデータを処理することと、
オブジェクトの前記測定されたパラメータセットを行動といつ関連付けられるかを識別する学習用入力を提供することと、
前記パラメータセットのうちのどのパラメータが、どの値の範囲において、前記行動を特徴付けるかを判断するために、前記学習用入力と組み合わせて前記データセットを処理することと、
前記特徴的なパラメータおよびその特徴的な範囲を使用して第２のオブジェクトデータに対して行う処理であって、前記行動が発生する時を自動的に識別する処理において使用するために、前記パラメータセットのうちのどのパラメータが、どの値の範囲において、前記行動を特徴付けるかを識別する情報を送信することと、
を含む。
【０００８】
これにより、機械による学習技術を使用して動的な特徴化が可能になり、また、ある特定行動についてモデルを予め設ける必要性が排除される。
【０００９】
学習用入力と組み合わせてデータセットを処理することは、パラメータセットのうちのどのパラメータが、どの値の範囲において、行動を特徴付けるかを動的に判断する。従って、特徴パラメータは、処理中に動的に変化してもよく、また、事前決定されない。
【００１０】
学習用入力は、行動が発生する時を識別する必要があるだけである。ゆえに、専門家に課される負担は、行動が発生している時を指示するだけである。専門家は、行動が発生していると考えられる理由を判断する必要はない。従って、行動を分類する負担は、専門家から処理ステップへ移行される。オブジェクトデータは、１つまたは複数の映像クリップであってもよい。あるいは、オブジェクトデータは、１つ以上のオブジェクトの動きを経時的に記録するその他のデータであってもよい。オブジェクトデータは、例えば、オブジェクト毎の、一連の全地球測位システム（Global Positioning System; GPS）座標を含んでもよい。行動は、生物有機体などの移動オブジェクトの相互作用であってもよい。
【００１１】
パラメータセットのうちのどのパラメータが、どの値の範囲において、行動を特徴付けるかを判断するために、学習用入力と組み合わせてデータセットを処理することは、遺伝的アルゴリズムなどの学習機構の使用を伴ってもよい。ただしそれだけに限定されない。
【００１２】
遺伝的アルゴリズムにおいて使用される染色体は、測定されたパラメータセットにおけるパラメータ毎に、スイッチオンまたはオフであり得る遺伝子を含んでもよい。遺伝的アルゴリズムに使用される染色体は、相互作用を特徴付けるために必要なパラメータのクラスタの数を特定する遺伝子を含んでもよい。遺伝的アルゴリズムに使用される染色体は、染色体の適合が評価される時間を特定する遺伝子を含んでもよい。
【００１３】
遺伝的アルゴリズムにより使用される染色体の集団からの染色体は、パラメータ空間と、パラメータ空間が分割されるクラスタの数とを規定する。クラスタ内にあるデータセットの下位セットが、相互作用に関連付けられるデータセットの下位セットと相関する度合いを使用して、染色体の適合を決定してもよい。
【００１４】
本発明の一実施形態によると、１つ以上のオブジェクトを追跡する方法が提供される。この方法は、１つまたは複数の第１の基準を満たす連続データ値の第１の離散群を識別するために、第１のデータを処理することと、１つまたは複数の第２の基準を満たす連続データ値の第２の離散群を識別するために、後続の第２のデータを処理することと、第１の群と第２の群との間のマッピングを行うことと、第２の群が単一のオブジェクトを表すか、または複数のオブジェクトを表すかについて判断するために、マッピングを使用することと、第２の群が単一のオブジェクトを表すと判断される場合、第２の群の１つ以上のパラメータを測定することと、第２の群がN（N>1）個のオブジェクトを表すと判断される場合、１つまたは複数の第２の基準を満たす連続データ値のN個の下位群に第２の群を分解すべく第２の群を処理することと、下位群の１つ以上のパラメータを測定することと、複数の下位群を複数のオブジェクトにマッピングすることと、を含む。
【００１５】
前記方法は、オブジェクトの相互作用としての社会的および個人的な全行動を分類する。全種類の行動に関して１つの手法が使用される。
【００１６】
個体は、多数の要素オブジェクトから構成されることが可能であるため、場面におけるオブジェクトのグラフを形成することが可能である。例えば、場面は、各々が頭部および胴体のオブジェクトから構成される２つのオブジェクトを含んでもよい。これにより、オブジェクトの階級を作成することが可能になり、また、オブジェクト全体の相互作用だけでなく、別のオブジェクトの要素またはオブジェクト全体自体の要素を有する要素オブジェクトの相互作用も調査可能になる。要素オブジェクトから構成されるオブジェクト全体は、オブジェクト全体の全特性を引き継ぎ、また、オブジェクト全体のオブジェクトの所定の種類（例えば、マウス、ハエ）を考慮して規定され得る追加の特徴を有してもよい。
【発明の実施形態の詳細な説明】
【００１７】
本発明をより理解するために、ほんの一例として添付の図面を参照する。
【００１８】
図1Aは、画像キャプチャおよび分析の実行に適切な追跡システム10を示す。システムは、ビデオカメラ2と、プロセッサ6に伝達される前にカメラにより供給される映像画像をバッファリングするためのメモリバッファ4とを備える。プロセッサ6は、メモリ8に対して読み込みおよび書き込みするように接続される。メモリ8は、コンピュータプログラム命令12を格納する。コンピュータプログラム命令12は、プロセッサ6にロードされる場合にシステム10の動作を制御する。コンピュータプログラム命令12は、論理およびルーチンを提供して、図2に示される方法を電子機器が実行できるようにする。
【００１９】
コンピュータプログラム命令は、電磁搬送波信号を介してシステム10に到達してもよく、あるいは、コンピュータプログラム製品などの物理的実体、メモリ装置、またはCD-ROMまたはDVDなどの記録媒体から複写されてもよく、あるいは、リモートサーバから転送されてもよい。
【００２０】
後述の追跡システム10は、遠隔地用に設計されている。従って、システムが、低帯域幅伝送を介してデータ構造40を伝送する無線送受信機などの出力ポート14を有することが望ましい。また、システムが、リアルタイムで動作することも望ましく、従って、プロセッサ6がデータ構造40を生成するのに必要な計算量を減らすことも望ましい。
【００２１】
入力ファイルフォーマット3は、映像ファイルまたはストリームである。選択されるカラースキームは、RGB、YUV、YCCであり得る。
【００２２】
フレーム落ちが実行されている。フレームの予測数がフレームの実数未満である場合、次のフレームを無視する命令を受ける。これにより、プログラムがストリームに追いつき、クラッシュを回避することが可能になる。しかしながら、フレームが落ちる場合、映像が飛ばされることにより追跡時に問題が生じる。この問題を解決するために、フレーム落ちの命令を受けると、フレームは、処理されずに格納される。映像の最後に、落とされた全フレームを処理し、その結果を結果データに挿入することができる。
【００２３】
図1Bは、図5に示されるデータセットアップおよび行動評価の実行に適切な処理システム110を示す。システムは、メモリ108に対して読み込みおよび書き込みするように接続されるプロセッサ106を備える。メモリ8は、コンピュータプログラム命令112およびデータ構造40を格納する。
【００２４】
コンピュータプログラム命令112は、プロセッサ106にロードされる場合にシステム110の動作を制御する。コンピュータプログラム命令112は、論理およびルーチンを提供して、図5に示される方法を電子機器が実行できるようにする。
【００２５】
コンピュータプログラム命令は、電磁搬送波信号を介してシステム110に到達してもよく、あるいは、コンピュータプログラム製品などの物理的実体、メモリ装置、またはCD-ROMまたはDVDなどの記録媒体から複写されてもよく、あるいは、リモートサーバから転送されてもよい。
【００２６】
また、システム110は、プロセッサ106によりメモリ108に格納されるデータ構造40を受信するように、システム10と通信する無線受信機も備える。
【００２７】
また、プロセッサ106は、入力手段101にも接続され、入力手段110を介してその他のデータがシステム110に入力されてもよい。
【００２８】
システム10および110は、図1Aおよび1Bにおいて別々の実体として図示されているが、その他の実装では、これらのシステムは一体型であってもよい。
【００２９】
追跡処理20を図2に示す。フィルタ段階22に提供される入力21は、映像ファイルまたは映像ストリームであってもよい。後者の場合、ビデオカメラのメモリバッファからの出力がフィルタ22に提供される。
【００３０】
段階22において、畳み込みを使用してノイズを除去するように画像をフィルタリングする。カーネルを画像全体に反復的に通し、各位置においてカーネルが適用される画素の重み付き和を計算する。
【００３１】
次の段階24は、閾値化（量子化としても知られる）を伴う。これは、画像内の関心画素（１つまたは複数の前景オブジェクト）を背景から分離する。これは、入力画像を２値画像にする処理（２値化）である。閾値Tに照らして各画素（i,j）を調査し、その値がTを超える場合に真値が与えられ、その値がT未満である場合に偽値が与えられる。
2009531049.tif 000003
【００３２】
T値を得るための方法は多く存在し、そのうちのいくつかについて以下に説明する。
【００３３】
平均閾値化（Mean Thresholding）は、最も容易な形式の閾値化であり、全画素値の平均を計算することと、そこから定数を減算することとを伴う。
2009531049.tif 000004
【００３４】
ここで、Nは画像における画素の総数である。この方法の利点は、非常に高速であることにあるが、画像における光強度の変更に対してロバストでない。
【００３５】
適応閾値化（Adaptive Thresholding）は、画像にウィンドウが繰り返し通される。各位置において、ウィンドウ内に含まれる画素の平均値を計算し、定数Cを減算して閾値を求める。
2009531049.tif 000005
【００３６】
これは、画像における光強度（intensity）の変更が可能であり、オブジェクトが画像全体において常に識別されるという利点を有する。不利点として、調査する画素数が非常に多い場合に、非常に遅くなることが挙げられる。
【００３７】
一定の背景で実験を実行する場合は、背景除去を使用することができる。前景オブジェクトを含まない背景の画像（B）を取り出し、この画像を、前景オブジェクトを含み得る現在の画像と共に使用する。この場合、背景画像は、テスト領域であり、残りの画像は、映像の各フレームであり得る。背景画像は、画素における現在の画像から画素ベースで差し引かれる。これは、前景オブジェクトのみを含む新しい画像を生成するという効果を有する。
【００３８】
あるいは、ホームケージ実験（home case experiment）における床敷（bedding）のように背景が変化している場合、背景推定を使用することができる。これは、N個毎のフレームを取り出し、サンプルフレームを使用してフレームセットを形成する処理である。フレームセットのサイズは固定であり、新しいフレームが加えられると、先入れ先出しの順番で古いフレームが除去される。フレームのセットにおける画素値を平均化する場合、移動オブジェクトが除去されるため、平均背景が残る。
【００３９】
擬似適応閾値化（Pseudo Adaptive Thresholding）は新しい閾値化技術である。この方法は、サイズが（h×w）の画像を、サイズが（h/q（N））×（w/q（N））である多数のウィンドウNに分割する。次に、これらのウィンドウの各々を、個々の画像として処理し、下位画像内に平均閾値化を適用する。下位画像が元々の画像に比べて小さい場合、前述の平均閾値化を使用する代わりに、k個のランダム画素を各下位画像において選択し、これらの値を平均化して閾値（定数を差し引く）を生成する。
2009531049.tif 000006
【００４０】
このアルゴリズムは画像における光変動にも十分対応する。ウィンドウの最適数は9から16の範囲である。
【００４１】
適応閾値化も良い結果を提供し、前景画素として分類される背景ノイズの量を極めて少なくすることが可能であるが、その代わりに時間を要する。適応閾値化は、速度精度を提供することを望まない場合に好ましい。そうでない場合、可変の光状態において適応閾値化が好ましく、また、一定の光状態において平均閾値化が好ましい。
【００４２】
次の段階は、画像消去段階26である。画像消去は、前の画像処理後に残り得る何らかのノイズを除去する処理である。画像消去処理後、画像に残るのは、大きな固体領域のみであるべきである。
【００４３】
エロージョン（Erosion）は、画像全体における画素の近傍（画素を囲む画素）を反復的に取り出す処理であり、近傍における真の画素数が閾値未満の場合、画素は偽（false）に設定される。これは、オブジェクトから突起部および突出部を除去するという効果を有し、また、少量のノイズも除去する。２つの領域がかろうじて接触している場合、それらを分離する効果も有する。これに関する不利点として、前景オブジェクトのエッジの詳細が失われることが挙げられる。
【００４４】
ダイレーション（Dilation）はエロージョンの反対である。近傍における真の画素数がある閾値を超える場合、その画素は真（true）に設定される。これは、前景オブジェクトにおける空洞を充填し、またエッジを平潤化する効果を有する。しかしながら、これは、実際はノイズであるサイズの小さい領域を増加させる。
【００４５】
エロージョンおよびダイレーションを合わせて使用し、前景オブジェクトのエッジを平潤化し、不要な小領域を画像から除去することができる。
【００４６】
フィルタ22が平均畳み込み（averating vonvolution）を実行する場合、これがダイレーションとほぼ同一の効果をもたらすため、ダイレーション操作は冗長であることが知られている。
【００４７】
次の段階は、段階28の画素群検出である。この場合、画素群は、オブジェクトに関連する画素における前景画素の連続領域またはオブジェクトの重複群として定義付けられる。
【００４８】
画素群が識別され、一意的なラベルが割り当てられる。以下のアルゴリズムは、各画素の近傍（4〜8個の連結された近傍）を再帰的に調査し、いずれかの近傍にラベルが割り当てられているか否かを判断する。割り当てられていない場合、その画素に現在のラベルを割り当て、割り当てられている場合、アルゴリズムは、もっとも小さな近傍ラベルにラベルを設定する。
2009531049.tif 000007
【００４９】
従って、図3aに示される画素は、図3Bに示されるようにラベル化される。図3Bは３つの異なる画素群を示す。
【００５０】
場合により、２値画像において前景オブジェクトでない画素群が残る。上限および下限が、許容オブジェクトの特徴（例えば、領域（area）および／または偏心（eccentricity））に設けられる。１つまたは複数の前景オブジェクトを表す画素群は、常に上限と下限の間にある。特徴の領域外のいかなる画素群も、画素群検出およびラベル化処理において無視される。
【００５１】
画素群検出段階は、現在のフレームで検出された画素群のリストを返信するが、これは、画像が遮蔽されているが原因で、フレームにおけるオブジェクトの全てでない場合がある。
【００５２】
次の段階は、段階30の遮蔽イベント（occlusion event）検証である。
【００５３】
画素群の境界は、画素群を包囲または取り囲む領域として定義付けられる。
【００５４】
境界は、画素群の最上点、最左点、最右点、および最底点によって画定される単純な長方形などの真の境界ボックスであってもよい。この手法の利点は、非常に高速に計算できることにある。しかしながら、画素群の形状または領域を良好に表現せず、相当な背景領域を含む可能性がある。
【００５５】
境界は、その主軸および方向を考慮した、上述のような適合境界ボックスであってもよい。この方法の利点は、所要の計算が依然として単純であり、結果として生じる長方形が、典型的には、ごく一部の背景しか含まないことにある。
【００５６】
また、境界は、画素群に最も適合する楕円または多面体などの適合境界であってもよい。例えば、画素群を包囲する最小面積を有する楕円を、標準的な最適化法を使用して求めてもよい。しかしながら、所要の計算が複雑であり、かつ相当な量の計算時間を必要とする。
【００５７】
あるいは、能動輪郭モデル（Active Contour Model）を使用して、境界を画素群に適合させることができる。画素群の境界を適合させるさらなる方法として、ソーベルフィルタなどの標準的なエッジ検出ルーチンを使用してエッジを抽出してから、検出されたエッジ上の直線分割によって直線の多面体表現を提供することが挙げられる。直線分割技術の１つとして、相互に対向する点を２つ（A,B）選び、この２つの点の間にベクトルを生成する。この直線に沿ったベクトルCからの最遠点が、ある閾値Tを超える場合、ベクトルは、２つ（AC、CB）に分割される。この処理は、抽出された表現からTより遠い点が無くなるまで反復的に実行される。
【００５８】
遮蔽イベント検出は、オブジェクトの境界を利用して遮蔽の開始および終了を識別する。これに対して追加のオブジェクト特性は、遮蔽中のオブジェクトの追跡を管理する枠組みを提供する。そのうちのいくつかを以下に列挙する。
・  ラベル：これは、経時的にオブジェクトを識別する、グローバルに一意なラベルである。すなわち、ラベルは時間が経過しても変化しない。
・  x、y：これは、オブジェクトのxおよびy座標である。
・  面積：オブジェクトの面積。
・  角度：オブジェクトの角度。
・  矩形（rect）：オブジェクトの境界。
・  包含（contains）：検出されたオブジェクトと現時点で関連付けられる一意的なラベル、あるいは他にリストに含まれるものが無い場合の独自のラベルを含むリスト。
・  被包含（contained）：当該オブジェクトが別の包含リストに含まれるか否かを記載するブールフラグ
・  可能性（possible）：当該オブジェクトに含まれる可能性のある一意的なラベルのリスト。これを使用して、２つを超えるオブジェクトを含む境界の分割によりもたらされる曖昧性に対処する。
【００５９】
その他の使用され得る特性として、偏心（eccentricity）、速度、加速、異なる次元におけるサイズなどが挙げられるが、それだけに限定されない。また、包含リストおよび可能性リストは、関連付けられる確率を有してもよい。例えば、要素オブジェクトは、一定の確率で親オブジェクトに含まれる。
【００６０】
遮蔽中のオブジェクトの追跡は、場面におけるN個の要素オブジェクトに対応するN個のカルマンフィルタを使用して拡張可能である。カルマンフィルタは、オブジェクトの情報履歴を考慮し、現在のフレームにおけるその情報に関する確率値を提供する。これを決定処理において使用し、多数の融合（merging）および分裂（splitting）操作が発生する場合あるいはフレーム間で大量の移動がある場合に、システムの信頼性を改善することができる。
【００６１】
FuentesおよびVelastinにより提案されたアルゴリズム［「監視用途における人物追跡」、追跡および監視に関する性能評価に関する第２回IEEE国際会議PETS2001］（["People Tracking in surveillance applications", 2nd IEEE International Workshop on Performance Evaluation on Tracking and Surveillance, PETS 2001]は、フレーム間の境界の境界ボックスを一致させることを試みる。これが機能するように立てられた仮定は、空間移動が時間移動に比べて小さいこと、すなわち、連続フレームにおける境界ボックス間に常に重複が存在するということである。
【００６２】
２つの連続フレームをf（t）およびf（t-1）と定義する場合、その両方が、遮蔽を示す異なる数の境界を含むことが可能であり、すなわち、境界は、１つ以上のオブジェクトを含み得る。２つのフレーム間の一致は、一対の一致マトリクス
2009531049.tif 000008
および
2009531049.tif 000009
によって定義される。
【００６３】
マトリクス
2009531049.tif 000010
は、現在のフレームの境界と前のフレームの境界とを一致させる。マトリクスは、N個の順序行およびM個の順序列を有する。ここで、Nは、現在のフレームにおける境界の数を表し、Mは、前のフレームにおける境界の数を表す。行における１つまたは複数の真値は、その行に関連付けられる現在のフレームの境界が、１つまたは複数の真値の１つまたは複数の位置に関連付けられる前のフレームの境界にマッピングすることを示す。
【００６４】
マッチング文字列
2009531049.tif 000011
は、単一行のベクトルであり、各ベクトルは、時間tのフレームにおける境界を表し、また各ベクトルは、そのオブジェクトに関し、時間t-1のフレームにおける関連付けられる１つまたは複数のオブジェクトを示す。従って、時間tにおける特定の境界に対応する位置における多値ベクトルの存在により、多数のオブジェクトが融合（結合、merge）してそのオブジェクトを形成していることが示され、そのベクトルにより要素オブジェクトが識別される。多数の位置における同一のベクトルの存在により、そのベクトルに識別される境界が分散していることが示される。さらに、行における多数の真値の存在により、境界が多数のオブジェクトに経時的に分裂（分離、split）していることが示される。
【００６５】
マッチング文字列を使用して、以下のイベントを定義することが可能である。
2009531049.tif 000012
【００６６】
FuentesおよびVelastinの文献（2001）より抜粋されるこれらの操作により、遮蔽が開始または完了する時、オブジェクトが退去または進入する時、ならびに境界が別の境界と一対一で一致する時を検出することが可能になる。
【００６７】
従って、さらなるイベントについて以下のように定義することが可能である。
2009531049.tif 000013
これは、オブジェクトが同一フレームから退去および進入する場合に、実際は映像の質の悪さによる誤差であり、オブジェクトが映像を退去または進入していない可能性が高いため、オブジェクトが相互に一致していることを言及している。
【００６８】
段階30の遮蔽イベント検出において、現在のフレームにおけるオブジェクトの新しい境界をまず計算し、次に、このフレームにおけるオブジェクトの境界と、前のフレームにおけるオブジェクトのフレームとの間の重複を計算することによって、一致しているマトリクスおよび文字列を生成する。その後、イベントに関するリストを作成し、このようなイベントについて、対応する操作を段階32において実行して、オブジェクト毎に追加の情報を生成する。情報が単一のオブジェクト画素群から抽出される処理34は、情報が多数のオブジェクト画素群から抽出される処理36とは異なる。
【００６９】
段階32において、オブジェクトを更新する。しかしながら、実行される更新操作は、段階30で検出されるイベントに依存する。
【００７０】
段階32の種々の許可イベントについて以下に説明する。多数のイベントがオブジェクトまたはオブジェクトの組について可能である場合に、イベントの履歴およびその関係を調査することによって、各イベントに確率を割り当てることが可能である。これは、ハードコード化が可能であり、あるいは現在または前のデータセットの時間に学習可能である。
【００７１】
・  一対一（A、B）：これは、前のフレームからのオブジェクトAが、現在のフレームの境界Bに一致することを言及する。
【００７２】
オブジェクトAに関する包含リスト変数が１つしかエントリを含まない場合、Aのラベルは、Bのラベルに複写される。画素群分析方法34をオブジェクトBに実行して、角度、面積、および配置を得ることが可能であるが、それだけに限定されない。
【００７３】
あるいは、包含リスト（contains-list）変数が多数のエントリを有する場合（遮蔽が連続している場合）、Aの包含リスト変数および可能性リスト（possible-list）変数はBに複写され、遮蔽情報生成方法36を実行して、画素群におけるオブジェクト毎の角度および配置情報を得る。被包含リストのオブジェクト領域の各々は、前のフレームにおける対応するオブジェクトから進められる。すなわち、遮蔽されたオブジェクトの新しい領域を計算する試みが為されない。
【００７４】
・  融合（[A,B],C）：これは、前のフレームからのオブジェクトAおよびBが融合（結合，Merge）して、現在のフレームにおいて境界Cを形成することを表す。
【００７５】
融合が検出されると、AおよびBの包含リスト変数が結合される（融合は、２つを超えるオブジェクトの融合を伴うことが可能である）。これにより、融合オブジェクトを表す境界Cの包含リスト変数が生成される（境界AまたはBは、複数のオブジェクトを含んでいたので）。次に、遮蔽情報生成方法36を使用して、Cの包含リストのために角度および位置情報を生成し、対応する前のデータに一致させる。
【００７６】
オブジェクト領域の各々は、前のフレームから進められる。すなわち、遮蔽されたオブジェクトの新しい領域を計算する試みが為されない。融合オブジェクトの各々の被包含フラグは、真に設定される。
【００７７】
・  分裂（A,[B,C]）：これは、前のフレームからのオブジェクトAが、単一の境界から、現在のフレームにおいてオブジェクトBおよびCに分裂（分離，Split）したことを表す。
【００７８】
分裂が検出されると、Aに含まれるオブジェクトの総数をS（a）と定義し、Aが分裂したオブジェクトの数をN（s）と定義する。次に、Bが（Sa-Na）のオブジェクトを有し、Cが１つのオブジェクトを含むと仮定するように分裂したと仮定する。Cは、Bの包含リストに設定される「可能性」オブジェクトの変数を有する。
【００７９】
分裂したオブジェクト毎に遮蔽情報を生成し、オブジェクトにBおよびCを割り当て、前のデータに一致させる。
【００８０】
オブジェクトAがBおよびCに分裂するが、オブジェクトAの包含リスト変数が分裂を対象とする十分なエントリを含まない場合、すなわち、（Sa<Ns）である場合の、オブジェクトAの可能性変数について説明する。可能性変数のサイズはP（a）であり、分裂し易くするのに必要な追加のオブジェクトの数は（Ns-Sa）である。（Sa<Ns）のエントリが、オブジェクトAの可能性変数から選択され、「数を補う」ために使用される。次に、これらのエントリは、前のフレームからのその他の全オブジェクトの可能性リストおよび包含リスト変数から消去される。次に、分裂は、前述のとおり完了する。最後に、各分裂オブジェクトは、その被包含フラグを偽に設定する。
【００８１】
分裂操作の擬似コードは以下のとおりである。
2009531049.tif 000014
【００８２】
・  退去（A）：前のフレームからのオブジェクトAが退去（leave）している。
【００８３】
オブジェクトAが退去していると検出される場合、その可能性リストに含まれるが他のオブジェクトの可能性リストには含まれない全てのエントリが、全ての他のオブジェクト可能性リストに加えられる。これにより、オブジェクトAが実際に複数のオブジェクトを含んでいる場合も対象となる。
【００８４】
・  進入（A）：現在のフレームにおける境界Aは新しい。
【００８５】
境界Aが進入している（Enter）と検出された場合、新しいラベルが割り当てられ、画素群分析方法34を実行して、多数のパラメータの中から、その面積、位置、および角度を得る。
【００８６】
境界Aが実際に複数のオブジェクトを含んでいた場合、その分裂時に、包含リストおよび可能性リスト変数におけるエントリが十分に存在しないことが分かる。この場合、分裂したオブジェクトは、新しいものとして処理され得る。
【００８７】
・  一致なし（A、B）：前のフレームからのオブジェクトAは、何に対しても一致せず（退去している）、また、現在のフレームにおける境界Bは、何に対しても一致しない（新しい）ため、空間移動が大きいために、それらが相互に一致することが仮定される。
【００８８】
不一致（No Match）が検出された場合、不一致B（p）を含む前のフレームからの全オブジェクトならびに不一致B（c）を含む現在のフレームからの全オブジェクトが求められ、またその中心点およびベストフィットアルゴリズムを使用して相互に割り当てられる。情報は、各一致された前のものから現在のオブジェクトに一対一の一致として複写される。
〔画素群分析方法（Pixel-Group Analysis method）34〕
【００８９】
この方法は、単一のオブジェクトを含む画素群の位置、面積、および角度情報を得るために使用可能である多数の方法のうちの１つの例である。画像における画素群が識別およびラベル化されると、所要の特性を抽出しなければならない。位置は、オブジェクトに属する画素のxおよびy位置を単に合計し、面積で割ることによって求めることが可能である。これにより、オブジェクトの平均xおよびy位置が提供される。角度は、線形パラメータモデルまたはベクトルベースの手法を使用して求めてもよい。
【００９０】
線形パラメータモデルは、線形モデルをサンプルデータの組に適合させるための回帰問題を解決する方法である。この方法の利点は、オブジェクトの方向に関して非常に正確に推定することにある。不利な点は、ベクトル手法に比べて計算に時間がかかる。ベクトルベースの手法は、オブジェクトにおいて、幅よりも頭部から尾部までのほうが長いことを単に仮定する。まず、中心点を求め、次に、中心点からの最遠点を計算する。これらの２つの点の間のベクトルを使用して、オブジェクトの方向を判断する。
〔遮蔽情報生成方法36〕
【００９１】
これは、多数のオブジェクトを含む画素群におけるオブジェクト毎の位置および角度情報を得るために使用される。
【００９２】
擬似コードは、以下のとおりである。
2009531049.tif 000015
【００９３】
最初に、オブジェクトAC（a）の包含リストの長さとしてオブジェクトの数を定義する。２値画像におけるオブジェクトAの境界内において、K＝長さ（C（a））でK平均法を実行する。これにより、含まれるオブジェクトに関する中心点（平均）P（n）が生成される。次に、オブジェクトAにおける点P（n）毎に、P（n）からのユークリッド距離の２乗が最大であるオブジェクト内の点を求めるD（n）。最後に、ベストフィット（best fit）を割り当てる手法によって全P値をD値に割り当てる。P値と割り当てられたD値との間のベクトル方向により、角度データが提供される。
【００９４】
ここで、境界A（つまり境界B）に含まれる既知のN個のオブジェクトに関するデータを有することになり、計算されたデータを、前のフレームからのオブジェクトBに含まれるデータに一致させなければならない。これは、計算された中心間の平均距離に依存する２つの方法のうちの１つにおいて実行される。最初に、計算された中心間の平均距離が、ある閾値Tを超える場合、ベストフィットマッチングアルゴリズムを使用して、前のフレームからの対応する中心点を現在のフレームにマッチングさせることが可能である。平均距離がT未満である場合、カルマンフィルタなどの予測方法が必要とされる。
【００９５】
段階32からの出力は、図4に示されるようなデータ構造40である。このデータ構造40は、映像のフレーム毎に、オブジェクト毎のエントリを含む。オブジェクト毎のエントリは、情報フィールドを含む。
〔コンフリクト〕
【００９６】
データセットにおけるフレーム毎のオブジェクトの数が定数であることが確実である場合、進入および退去動作は誤差によるものでなければならない。ゆえに、イベント検出段階30の一部として、コンフリクト解決ルーチンを導入することが有用である。それによって、進入および退去イベントは、不一致イベント（no match event）に置換可能になる。誤差訂正の初期段階後、フィルタイベントを分析して、全ての不一致が解決可能であるか否か（すなわち、全動作を満たすために十分な、前のフレームおよび現在のフレームにおけるオブジェクトが存在するか）を確認する。解決可能でない場合、満たすことのできない動作が消去される。
【００９７】
前述のように、この処理は確率的であってもよい。この場合、例えばカルマンフィルタから、コンフリクト動作に関与するオブジェクトの予測情報に関して利用可能な過去の経験および情報を考慮してコンフリクトを解決する操作に、コンフリクトを考慮して確率を割り当てることが可能である。
【００９８】
追跡処理20からの出力であるデータ構造40は、追跡処理を実行した位置またはその位置から遠隔の位置において処理されてもよい。
〔訓練データの分類〕
【００９９】
追跡処理20により生成されるデータ構造40を使用して、オブジェクトの相互作用を再構築する。専門家は、自身が探知する行動が満足であると考える映像の時間を識別するこことによって、アノテータ（annotator）と相互作用する。専門家の分類は、データ構造40の対応するパラメータ値と共にログファイルに記録される。ログファイルは、パラメータおよび値（満足または不満足な行動）のラベル化されたデータセットである。それは、専門家の分類手順に対応するルールを生成するために、行動学習アルゴリズムによって使用される。
〔行動（Behavior）学習アルゴリズム〕
【０１００】
ここでは、１つまたは複数のオブジェクトの一定の行動に相関するオブジェクトの相互作用から測定可能な一定のパラメータが存在することが仮定される。行動は、映像の単一フレームからは識別可能でない場合がある。というのも、分類が可能になる前に、ある時間帯に亘って現れねばならないかもしれないからである。ｎ次元空間を定義するｎ個のパラメータが存在する場合、特定の行動の異なる側面を特徴付けるデータ点が、異なるクラスタを形成することが仮定される。各クラスタは、ｎ次元空間における塊（ボリューム）であってもよく、またはいくつかのｎ次元下位空間における塊であってもよい。各クラスタは、学習された行動の特定の側面に関する行動のルールを表す。
【０１０１】
図4に示される処理50の目的は、ストリーミングデータ構造40を受信し、かつ事前に決定される行動が発生するか否か、また、発生する場合に、１つまたは複数のどのオブジェクトがその行動に関与するかをリアルタイムで判断することである。
【０１０２】
セットアップ処理52は、まず、異なる「行動」の塊（ボリューム）として行動の側面を特徴付ける。行動ボリュームは、n次元空間におけるそのm次元下位空間に及んでもよい。
【０１０３】
次に、評価処理54は、受信したパラメータを処理して、そのパラメータが行動ボリュームの範囲内に入るか否かを判断する。範囲内にある場合、受信したパラメータにより表される状況は、行動に対応していると考えられる。
〔セットアップ処理〕
【０１０４】
セットアップ処理52は、異なる「行動」ボリュームとして、行動の側面を特徴付ける。行動ボリュームは、ｎ次元空間におけるそのｍ次元下位空間に及んでもよい。この手法に関する次元的に減少させる種々の処理には、遺伝的アルゴリズム、主成分分析、確率的PCA、および因子分析を含むがそれだけに限定されない。
【０１０５】
遺伝的アルゴリズムの場合、処理によって、可能な解の集団が生成される。各解は、遺伝子の染色体によって定義される。染色体は、遺伝的アルゴリズムにおいて適合採点処理を制御する1組の測定されるパラメータ遺伝子および1組の遺伝子として設計される。典型的には、遺伝的アルゴリズムは、より適合する遺伝子の寿命をさらに促進し、増殖する可能性を増加させる。遺伝子のいくつかの突然変異も許可されてもよい。
【０１０６】
採点処理を制御する遺伝子は、例えば、クラスタの数Cを整数の遺伝子として特定してもよく、また、行動がテストされる時間Fを整数の遺伝子として特定してもよい。測定されるパラメータ遺伝子は、スイッチオン／オフ可能なブール遺伝子であってもよい。
【０１０７】
遺伝的アルゴリズムの利点は、測定されるどのパラメータがクラスタ化されたかについて、または、学習される行動を特徴付けるためにどのようにクラスタ化されるかついて、または、行動をどの時間に評価すべきかについて、事前に判断する必要がないことがないことにある。遺伝的アルゴリズム自体は、これらの問題を解決するだろう。
【０１０８】
遺伝的アルゴリズムの各反復において、染色体をランダムに（またはトーナメント選択を使用して）集団から取り出し、３つの操作のうちの１つをランダムに実行する。
・  選択（Selection）：不変の中間集団に染色体を移動する
・  突然変異（Mutation）：染色体における１つの値をランダムに変更し、それを中間集団に移動する
・  交叉（Crossover）：２つの染色体を取り出し、染色体の長さに沿って点をランダムに取り出し、分裂点の後に２つの染色体の全ての値を交換する。これにより、２つの子および２つの親が生成される。これらによって、中間集団に通すように数が取り出される。結果として生じる最も適合度の高い２つの染色体は、例えば、中間集団に入り、また、その他の２つは破棄されてもよい。
【０１０９】
各反復の終了時に、中間集団における各染色体の適合が評価される。
【０１１０】
適合点は、専門家の分類段階からのログファイル51を使用して各染色体解法に割り当てられる。可能な解法染色体において、スイッチオンされる、すなわち真値を有するｂ測定されるパラメータ遺伝子は、測定されるパラメータによって規定される次元パラメータ空間におけるｂ次元下位空間を規定する。
【０１１１】
ｎ次元空間におけるデータ点と、各データ点が行動中のものであると専門家が考えるか否かについて記録する専門家のログファイルは、ｎ次元パラメータ空間のｂ次元下位空間に及ぶＣクラスタの形成に使用される。例えば、ガウス分布あるいは拡張型Ｋ平均法またはＣ平均法アルゴリズムを使用して、クラスタ化を実行してもよいが、これらのクラスタ化方法に限定されない。
【０１１２】
ガウスクラスタ化は、データ空間における確率の「ブロブ」を適合させ、存在するガウス分布の各々に属する確率が、点に提供可能になる。これは、分類状態において有用であることが可能であるが、本明細書において、データ点がいずれのガウス分布の範囲内にある場合、行動として分類される。また、ガウス分布について、信頼区間を決定して、複雑化を引き起こし得るデータにベストフィットを提供しなければならない。
【０１１３】
Ｋ平均法アルゴリズムは、ｎデータ点に対する適合ｋ平均法の方法である。最初に、データセットにおける点は、ｋ組のうちの１つにランダムに割り当てられ、各組の重心が計算される。
2009531049.tif 000016
【０１１４】
次に、各点について反復し、それに最近接する重心を、ユークリッド距離の２乗に基づいて計算する。各点に、最近接重心に関連付けられる組が割り当てられる。
【０１１５】
各反復の終わりに、その組の重心を再び計算する。これは、所定数の反復が経過するまで、あるいは反復中に再割り当てが無くなるまで継続する。擬似コードは以下のとおりである。
2009531049.tif 000017
【０１１６】
Ｋ平均法は、平均値をデータ点に適合させるだけであるが、これを拡大して、各平均値を境界ボックスに提供することによって、クラスタにすることが可能である。これは、特定のクラスタに属する全ての点を調査し（すなわち、それはその点への近接平均値）、各次元におけるそのクラスタの平均値から最遠点を調査することによって、境界ボックス（２次元、３次元の立方体、３を超える次元の超立方体）を形成することによって、実行される。これにより、各次元において１組の閾値が生成される。平均値から遠過ぎるクラスタに属するいかなる点（閾値Ｔによりユーザ定義）も無視され、データセット（ノイズの多いデータ）の異常値を補う。従って、クラスタは、ｎ次元空間における中心点および各次元における公差として定義される。この公差は、最大のユークリッド距離の２乗を表す閾値であり、１組のパラメータの事例は、クラスタの範囲内にあるように、その定義される中心点からにあることが可能であり、また、行動の側面として分類可能である。
【０１１７】
閾値Ｔは、遺伝的アルゴリズムで使用される染色体の遺伝子として加えられてもよい。さらに、分類の時間的関係もこのように学習可能であり、また、分類または後処理において使用可能である。
【０１１８】
次に、定義されたＣクラスタを使用してログファイルを評価する。定義されたクラスタＣの範囲内にあるログファイルからの各データ点は、行動を提示するものとしてラベル化され、定義されたクラスタＣのいずれの範囲にもない各データ点は、行動を提示しないものとしてラベル化される。
【０１１９】
染色体の適合関数は、求愛行動のアルゴリズムの割り当てと、データの過去Ｆフレームにおける求愛行動の専門家の割り当てとのフレーム毎ベースの相関に基づく。相関が改善されると染色体はさらに適合する。
【０１２０】
次に、中間集団の全適合を求め、ルーレット方法を使用して次の集団を構築する。これにより、集団のサイズの一部（染色体適合／全適合）は、中間集団における各染色体に割り当てられる。これにより、より適合する解法が次世代に確実に存在することになる。
【０１２１】
停止の基準（Stppping criteria）は、（ユーザ定義による）テストデータにおける最適解と専門家による分類の相関割合の（ユーザ定義による）繰り返しの数としての組である。
【０１２２】
遺伝的アルゴリズムの結果は、単一のベストフィット染色体またはベストフィット染色体の群である。さらに、このような染色体に関連付けられるクラスタは、計算可能である。
【０１２３】
遺伝的アルゴリズムの利点は、それが任意時間アルゴリズム（any time algorithm）であることである。すなわち、いかなる時間であってもそれは停止可能であり、また、解が改善されるように実行する時間の量として有効な解が返されることが可能である。
【０１２４】
ハエでは、求愛の相互作用は、一定の距離限界内に一定の組の方法で、相互に方向づけられるオブジェクトとして明示することが想定される。従って、所要の可能なパラメータは、相対距離、２つのオブジェクト間の角度、ならびにオブジェクト間のxおよびy距離である。xおよびy距離は、求愛行動において、ハエは別のハエを追うことがあるために必要とされる。
【０１２５】
従って、ハエの例において、領域、相対位置、相対方向などの一定のパラメータのうちの１つ以上は、求愛行動が発生する際の一定の範囲の値を採用することが仮定されるが既知ではない。
【０１２６】
具体的な本例において、測定されるパラメータ遺伝子は、ｘ距離、ｙ距離、相対距離、および相対角度の４つのデータ値を表す４つのブール遺伝子である。採点処理遺伝子は、探知すべきクラスタの数Ｃと、考慮すべき過去データのフレームの数Ｆとを表す２つの整数の遺伝子である。
【０１２７】
セットアップ処理52における遺伝的アルゴリズムは、固定データ点および行動分類を有し、染色体およびクラスタを生成する。
【０１２８】
次に、ベストフィット染色体およびそれに関連付けられるクラスタを固定してもよい。次に、評価処理54において、データ構造40からの入力データ点を、ベストフィット染色体の「オン」測定されるパラメータによって離間される空間に及ぶものに減少させ、関連付けられるクラスタ内にあるか否かを確認するためにテストする。クラスタ内にある場合、出力56において行動を提示するものとして自動的に分類される。
【０１２９】
データセットの分類後、行動の要素間の関係について調査可能である。専門家が、高度な行動を認識し、アルゴリズムが、オブジェクト間の関係を認識している際、単一の行動は、複数の要素（学習クラスタ）から形成され得る。これは、識別される要素間の時間的関係を考察することによって達成可能である。時間点における要素値（または、要素が一つも一致しない場合は０）の可能性を隠れマルコフモデルなどの技術を使用して計算し、割り当てられた値が有望であるかを決定することができる。
【０１３０】
アルゴリズムからの出力がブール値（または確率）のリストであるため、全体的な行動を後処理してもよい。これらの値を平準化して、識別される行動に基づき、見込みの無い時間的関係を除去してもよい。例として、行動が表現される時間の長さあるいは表現される行動における休止の長さが含まれる。このような技術の例としてガウス分布を含むウィンドウを、平準化するためにデータ値に通すことが含まれる。
【０１３１】
本発明の実施形態について、種々の例を参照して前段落において説明したが、請求される本発明の範囲を逸脱することなく、提供された例に修正を加えることが可能であることを理解されたい。例えば、追跡および行動分析についてハエに関連して説明したが、独立生物有機体、相対的に独立運動が可能な動物、齧歯類、ハエ、ゼブラフィッシュ、およびヒトなどのその他の移動オブジェクトの追跡および行動分析のために使用されてもよい。
【０１３２】
前述の説明において、特に重要であると考えられる本発明の特徴に注目するように努めているが、説明され及び／又は図示される特許可能ないかなる特徴または特徴の組み合わせに関しても、それらの特徴を特に強調したか否かに関わらず、出願者は保護を主張することを理解されたい。
【図面の簡単な説明】
【０１３３】
【図１Ａ】追跡システムを概略的に描いたものである。
【図１Ｂ】処理システム110を概略的に描いたものである。
【図２】追跡処理を概略的に描いたものである。
【図３】図３Aおよび3Bは、画素値のラベル化を示す。
【図４】追跡処理から出力されたデータ構造を示す。
【図５】セットアップおよび行動評価処理を概略的に描いたものである。
【図１Ａ】
2009531049.tif 000018
【図１Ｂ】
2009531049.tif 000019
【図２】
2009531049.tif 000020
【図３】
2009531049.tif 000021
【図４】
2009531049.tif 000022
【図５】
2009531049.tif 000023
【手続補正書】
【提出日】平成20年11月25日(2008.11.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１つまたは複数のオブジェクトの行動を自動的に特徴付けるための方法であって、
オブジェクト毎に測定されたパラメータセットを経時的に記録するデータセットを得るように、オブジェクトデータを処理することと、
オブジェクトの前記測定されたパラメータセットを行動といつ関連付けられるかを識別する学習用入力を提供することと、
前記パラメータセットのうちのどのパラメータが、どの値の範囲において、前記行動を特徴付けるかを判断するために、前記学習用入力と組み合わせて前記データセットを処理することと、
前記特徴的なパラメータおよびその特徴的な範囲を使用して第２のオブジェクトデータに対して行う処理であって、前記行動が発生する時を自動的に識別する処理において使用するために、前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかを識別する情報を送信することと、
を含む、方法。
【請求項２】
前記独立移動オブジェクトは、相対的に独立運動が可能な動物である、請求項1に記載の方法。
【請求項３】
前記動物は齧歯類である、請求項2に記載の方法。
【請求項４】
前記動物はハエである、請求項2に記載の方法。
【請求項５】
前記動物はゼブラフィッシュである、請求項2に記載の方法。
【請求項６】
前記動物はヒトである、請求項2に記載の方法。
【請求項７】
前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかを判断すべく前記学習用入力と組み合わせて前記データセットを処理することは、学習機構の使用を伴う、請求項１から６のいずれかに記載の方法。
【請求項８】
前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかを判断すべく前記学習用入力と組み合わせて前記データセットを処理することは、遺伝的アルゴリズムの使用を伴う、請求項１から７のいずれかに記載の方法。
【請求項９】
前記遺伝的アルゴリズムにおいて使用される染色体は、前記測定されたパラメータセットにおける前記パラメータ毎に、スイッチオンまたはオフであり得る遺伝子を含む、請求項8に記載の方法。
【請求項１０】
前記遺伝的アルゴリズムに使用される染色体は、前記行動を特徴付けるために必要なパラメータのクラスタの数を特定する遺伝子を含む、請求項8または9に記載の方法。
【請求項１１】
前記遺伝的アルゴリズムに使用される染色体は、染色体の適合が評価される時間を特定する遺伝子を含む、請求項8、9、または10に記載の方法。
【請求項１２】
前記遺伝的アルゴリズムにより使用される染色体の集団からの染色体は、パラメータ空間と、前記パラメータ空間が分割されるクラスタの数とを規定し、また、前記クラスタ内にある前記データセットの下位セットが、行動に関連付けられる前記データセットの下位セットと相関する度合いは、前記染色体の適合を決定する、請求項8から11のいずれかに記載の方法。
【請求項１３】
前記オブジェクトデータは映像である、請求項１から１２のいずれかに記載の方法。
【請求項１４】
前記特徴付けられる行動は、移動オブジェクトの相互作用である、請求項１から１３のいずれかに記載の方法。
【請求項１５】
請求項1から14のいずれかに記載の前記方法における各ステップを実行するためのコンピュータプログラム。
【請求項１６】
１つまたは複数のオブジェクトの行動を自動的に特徴付けるためのシステムであって、
測定された、オブジェクトのパラメータセットが、行動といつ関連付けられるかを識別する学習用入力を提供するための手段と、
前記パラメータセットのうちのどのパラメータが、どの値の範囲において、前記行動を特徴付けるかを判断するために、前記オブジェクト毎に前記測定されたパラメータセットを前記学習用入力と組み合せて経時的に記録するデータセットを得るための手段と、
前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかの情報を出力する手段と、
を含む、システム。
【請求項１７】
前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかを判断すべく前記学習用入力と組み合わせて前記データセットを処理することは、学習機構の使用を伴う、請求項１６に記載のシステム。
【請求項１８】
前記パラメータセットのうちのどのパラメータがどの値の範囲において前記行動を特徴付けるかを判断するべく前記学習用入力と組み合わせて前記データセットを処理することは、遺伝的アルゴリズムの使用を伴う、請求項１６に記載のシステム。
【請求項１９】
前記遺伝的アルゴリズムに使用される染色体は、前記行動を特徴付けるために必要なパラメータのクラスタの数を特定する遺伝子を含む、請求項１８に記載のシステム。
【請求項２０】
前記遺伝的アルゴリズムに使用される染色体は、染色体の適合が評価される時間を特定する遺伝子を含む、請求項１９に記載のシステム。
【国際調査報告】
2009531049.tif 000024
2009531049.tif 000025
2009531049.tif 000026
2009531049.tif 000027
2009531049.tif 000028