(57)【要約】【課題】本発明は、ビデオ中の通常事象を検出する方法を提供する。【解決手段】事象は先ず、ビデオから抽出した関連項目の特徴から類似性行列の総計を構成することによって検出される。類似性行列は、固有ベクトルに分解され、固有ベクトルは、類似性行列の総計の近似推定値を再構成するために用いられる。各行列は、クラスタリングおよびスコアリングされ、最も高いスコアをもたらすクラスタリングが通常事象の検出に用いられる。【選択図】図４
2006024210.tif 000002
【特許請求の範囲】
【請求項１】
複数の項目を含むビデオであり、ビデオ中の通常事象を検出する方法であって、
前記ビデオ中の項目毎に特徴セットを抽出すること、
前記項目に従って特徴毎に類似性行列を構成すること、
前記類似性行列を総計して類似性行列の総計にすること、
前記類似性行列の総計を分解して、最初から最後まで順番に並んだ固有ベクトルのセットにすること、
最初の類似性行列の総計の近似値は最初の固有ベクトルから再構成され、次の類似性行列の総計の近似値はそれぞれ、前記最初から最後まで順番に並んだ固有ベクトルを１つずつ多く含み、最後の類似性行列の総計の近似値が、全ての固有ベクトルから再構成される、複数の類似性行列の総計の近似値を再構成すること、
各類似性行列の総計の近似値に関連する項目を複数のクラスタにクラスタリングすること、
各類似性行列の総計の近似値を評価して各類似性行列の総計の近似値の有効性スコアを求めること、
および
有効性スコアが最も高い類似性行列の総計の近似値を通常事象に関連する項目のクラスタリングとして選択すること
を含む、ビデオ中の通常事象を検出する方法。
【請求項２】
前記特徴は、視覚特徴である
請求項１記載の方法。
【請求項３】
前記特徴は、聴覚特徴である
請求項１記載の方法。
【請求項４】
前記項目は、オブジェクトであり、前記特徴は、オブジェクトベースである
請求項１記載の方法。
【請求項５】
前記項目は、フレームであり、前記特徴は、フレームベースである
請求項１記載の方法。
【請求項６】
前記特徴は、低レベル特徴のヒストグラム、隠れマルコフモデル、およびスカラ値を含む
請求項１記載の方法。
【請求項７】
前記特徴は、前記構成中に重み付けおよび正規化される
請求項１記載の方法。
【請求項８】
前記再構成は、前記固有ベクトルの外積である
請求項１記載の方法。
【請求項９】
前記特徴は、前記オブジェクトの軌跡と関連付けられる
請求項４記載の方法。
【請求項１０】
前記軌跡は、持続時間が等しくない
請求項９記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはビデオ中の事象の検出に関し、特に通常事象の検出に関する。
【背景技術】
【０００２】
ビデオ中の事象を検出することは、「意味的に有意なオブジェクトの動作」を解釈するために必要である（A. EkinciおよびA. M. Tekalp著「映画的特徴を用いたスポーツビデオ中の一般事象の検出（Generic event detection in sports video using cinematic features）」（Proc. IEEE Workshop on Detection and Recognizing Events in Video, 2003））。「動作」または事象の検出を行うには、オブジェクトの数値特徴と有意な活動の記号による記述との間の隔たりを埋める必要がある。従来技術の事象検出方法は通常、ビデオから特徴の軌跡を抽出し、続いて教師付き学習を行う。
【０００３】
例えば、１つの方法は、視野に依存したテンプレートマッチングに基づく（J. DavisおよびA. Bobick著「テンポラルテンプレートを用いた人間の動きの表現および認識（Representation and recognition of human movement using temporal templates）」（Proc. IEEE Conf. Computer Vision and Pattern Recognition, 1997））。この方法では、動作はテンポラルテンプレートによって表現され、テンポラルテンプレートは、ビデオ中の各画素における累積的な動き特性から求められる。
【０００４】
別の方法は、人間の動きの周期的パターンの動的モデルを構成することによって単純な周期的事象、例えば歩行を検出する（L. Davis、R. Chelappa、A. Rosenfeld、D. Harwood、I. Haritaoglu、およびR. Cutler著「視覚的な監視およびモニタリング（Visual Surveillance and Monitoring）」（Proc. DARPA Image Understanding Workshop, pp. 73-76, 1998））。
【０００５】
オブジェクトの軌跡の分布をクラスタリングすることもできる（N. JohnsonおよびD. Hogg著「事象認識のためのオブジェクトの軌跡分布の学習（Learning the distribution of object trajectories for event recognition）」（Proc. British Machine Vision Conference, pp. 583-592, 1995））。共起特徴のクラスタリングを用いて同様の活動分布の階層を推定することもできる（C. StaufferおよびW. E. Grimson著「リアルタイム追跡を用いた活動パターンの学習（Learning patterns of activity using real-time tracking）」（IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(8), pp. 747-757, 2000））。
【０００６】
事象は、ビデオの分割を行うための時間的な確率過程として定義することができる（L. Zelnik-ManorおよびM. Irani著「事象に基づくビデオ解析（Event-Based Video Analysis）」（IEEE Conf. Computer Vision and Pattern Recognition, December 2001））。Zelnik-ManorおよびM. Iraniの非類似度は、オフライン訓練を必要とする経験分布のＸ２ダイバージェンス（発散、divergences）の和に基づき、クラスタ数は事前に設定されている。
【０００７】
隠れマルコフモデル（ＨＭＭ）は、このモデルが視覚的な観測シーケンスを生成する確率を求めることによって、単純な事象を表現し、事象を認識することができる（T. StarnerおよびA. Pentland「隠れマルコフモデルを用いたアメリカ手話の視覚認識（Visual recognition of American sign language using hidden Markov models）」（Proc. Int'l Workshop Automatic Face- and Gesture-Recognition, 1995））。
【０００８】
ＨＭＭは、侵入者の検出にも用いることができる（V. Kettnaker著「視覚的な侵入検出のための時間依存ＨＭＭ（Time-dependent HMMs for visual intrusion detection）」（Proc. IEEE Workshop on Detection and Recognizing Events in Video, 2003））。
【０００９】
従来技術のＨＭＭに基づく方法は通常、事象そのものを検出できるようになる前に、既知の事象を用いたオフライン訓練を必要とする。しかし、可能性のある事象を全て事前に把握できるという見込みはない。さらに、同一の事象であっても、異なる用途では変化する可能性がある。したがって、事象のモデル化および検出は難しい問題である。
【００１０】
いくつかの他の事象検出方法が既知である（A. Ng、M. Jordan、およびY. Weiss著「スペクトルのクラスタリングについて：解析とアルゴリズム（On spectral clustering: Analysis and an algorithm）」（Proc. of Neural Information Processing Systems, 2001）、M. MeilaおよびJ. Shi著「ランダムウォークによる分割の学習（Learning Segmentation by Random Walks）」（Proc. Advances in Neural Information Processing Systems, 2000）、Z. Marx、I. Dagan、およびJ. Buhmann著「結合クラスタリング：構造の対応関係を検出する方法（Coupled Clustering: a Method for Detecting Structural Correspondence）」（Proc. International Conference on Machine Learning, pp. 353-360, 2001）、S. Kamvar、D. Klein、およびC. Manning著「モデルベースの手法を用いた古典的な凝集型クラスタリングアルゴリズムの解釈および拡張（Interpreting and Extending Classical Agglomerative Clustering Algorithms using a Model-Based Approach）」（Proc. ICML, 2002）、ならびにM. Fiedler著「非負対称行列の固有ベクトルの特性とそのグラフ理論への応用（A property of eigenvectors of non-negative symmetric matrices and its application to graph theory）」（Czeckoslovak Mathematical Journal, 25: pp. 619-672, 1975））。
【００１１】
しかし、これらの方法は、異なる問題に対処する。例えばNg等は、Ｋ平均クラスタリングを用いる。Ng等は、最適なクラスタ数と最大固有ベクトルの数との間の関係を考慮しない。Meila等は、Ng等の方法を一般化固有値表現に拡張する。Meila等は、複数の固有ベクトルを用いるが、固有ベクトルの数は固定されている。Kamvarは、常に得られるとは限らない管理情報を必要とする。Marx等は、結合クラスタリングを固定数のクラスタとともに用いる。これらの方法の大きな欠点は、これらの方法すべてが、座標間の対応関係に依存するため、等しい長さの軌跡持続時間に限定されていることである。
【００１２】
ビデオからのオブジェクトの軌跡の抽出はよく知られている。しかし、トラッカの二次出力の調査に関しては、ほとんど研究がなされていない。１つの方法は、高さ、幅、速度、動き方向、および基準オブジェクトまでの距離を含む８つの不変な特徴を用いる（G. Medioni、I. Cohen、F. Bremond、S. Hongeng、およびR. Nevatia「ビデオストリームからの事象の検出および解析（Event detection and analysis from video streams）」（IEEE Trans. on PAMI, 23(8), 873-889, 2001））。視覚的な特徴も考慮することができる（Zelnik等およびStauffer等を参照）。Zelnik等は、異なる時間スケールにおける時空間強度勾配を用いる。Stauffer等は、座標、速度およびサイズの共起統計を用いる。しかし、従来技術の軌跡ベースの特徴は、多数の事象を検出するには表現力が不十分（insufficiently expressive）である。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
したがって、従来の特徴を用いた場合に通常は検出することができない事象を検出するために用いることができる、より表現力の高い特徴を提供することが望ましい。さらに、教師なしの学習方法を用いる方法を提供することが望ましい。
【課題を解決するための手段】
【００１４】
本発明は、ビデオ中の事象を検出する方法を提供する。本方法は、ビデオから抽出したフレームベースおよびオブジェクトベースの統計的特徴セットを用いる。統計的特徴は、軌跡、ヒストグラム、ならびに特徴の速度、方位、位置、サイズおよびアスペクト比の隠れマルコフモデルを含む。統計的特徴を構成するために用いられる低レベルの特徴は、ビデオ中の色および動きであり得る。
【００１５】
本発明はまた、最適なクラスタ数を自動的に推定するスペクトルクラスタリングプロセスを用いる。このクラスタリングプロセスは、性能に影響を与えることなく高次元データを用いる。
【００１６】
事前に定義されたモデルを事象に当てはめる従来技術の方法とは異なり、本発明は、有効性スコアおよび一致性スコアを解析することによって事象を判定する。本発明は、類似性行列（affinity matrices）を用い、固有値分解を適用して、事象の検出に用いられる最適なクラスタ数を求める。
【発明の効果】
【００１７】
本発明は、ビデオ中の通常事象および異常事象を検出する方法を提供する。事象は先ず、ビデオから抽出した関連項目（items）の特徴から類似性行列の総計（aggregate）を構成することによって検出される。類似性行列は、固有ベクトルに分解され、固有ベクトルは、類似性行列の総計の近似推定値を再構成するために用いられる。各行列は、クラスタリングおよびスコアリングされ、最も高いスコアをもたらすクラスタリングが事象の検出に用いられる。
【００１８】
本発明によって用いられる特徴は表現力が高いため、本発明は、従来技術の特徴を用いた場合には検出することができない事象を検出することができる。したがって、本発明は、計算の単純さと機能性の改善の両方の点で、従来技術の方法に全般的な実質的改良を施す。
【００１９】
本発明による表現力の高い特徴は、従来技術の記述子を用いた場合には検出することができない事象の検出を可能にする。本発明では、教師なしクラスタリングの枠組みをビデオに適用して事象を検出する。この枠組みは、特徴の次元数が増加しても悪影響を受けない。
【００２０】
本発明は、従来技術の不安定な補間に基づく手法とは対照的に、対の類似性による可変長の軌跡のクラスタリングを用いる。本発明は、特徴の選択基準を用いて、差別的特徴の寄与を増幅する。本発明はまた、部分空間を張る（span）絶対値での最大固有値の数はクラスタの数よりも１つ少ないことを示す。
【発明を実施するための最良の形態】
【００２１】
本発明は、ビデオから抽出した特徴に基づいてビデオ中の事象を検出する方法を提供する。特徴は項目に関連付けられる。項目は、ビデオ中のオブジェクト、あるいはビデオのフレームとすることができる。
【００２２】
オブジェクトの軌跡および特徴
第１の実施形態において、検討する項目はオブジェクトである。オブジェクトは、任意の既知の方法でビデオと分割することができる。オブジェクトの分割はよく知られており、数多くの技法が利用できる。時空間の軌跡は、ビデオ中の移動オブジェクトの連続的な経路を表す座標の時間シーケンスである。座標は、連続フレーム中のオブジェクトの位置に対応する。通常、「オブジェクト領域」の位置は、画素ベースのモデルの質量中心、楕円形モデルの主対角線の交点、およびバウンディングボックスモデルの垂直軸上の最小値および最大値の平均を示す。
【００２３】
本発明では、以下の表記を用いてオブジェクトの軌跡を定義する。
【００２４】
【数１】
2006024210.tif 000003
【００２５】
ここで、（ｘ，ｙ）は座標を示し、Ｎは、例えばフレーム数で測定される軌跡の持続時間である。
【００２６】
図１に示すように、本発明では、大きく２つのグループ１０１および１０２に分類することができる項目の特徴１００を用いる。オブジェクトベースの特徴１０１は、ビデオ中の個々のオブジェクトの特性を記述する。フレームベースの特徴１０２は、各ビデオフレームの特性を表す。さらに特徴は、統計的特徴、例えば低レベルの特徴から導出したヒストグラム、ＨＭＭ、およびスカラとしてより詳細に分類することができる。特徴は、視覚的なもの（例えば色および動き）であっても、聴覚的なもの（例えば音量および音の高さ）であっても、あるいは音の分類（例えば男性、女性、音楽、および歓声）であってもよい。
【００２７】
特徴によっては、追跡プロセス中にフレーム間で値が変化するものもある（例えばオブジェクトの速度）。このような動的な特徴は、正規化されたヒストグラムに関して統計学的に表現することができる。ヒストグラムは、特徴の密度分布に対応する。したがって、特徴は、平均、分散および高次モーメントを含む。しかし、ヒストグラムは、時間的な順序を廃棄するため、統計的属性の評価により有用である。
【００２８】
本発明では、特徴の動的特性を捕捉するＨＭＭベースの表現も用いる。ＨＭＭ表現は、ヒストグラムよりも表現力が高い。特徴の比較には、ベクトルの大きさが等しいことが必要であるため、大きさが変化する動的な特徴は、ＨＭＭを用いて共通パラメータ空間に移される。本発明はまた、いくつかの特徴をスカラ値として表現する。
【００２９】
オブジェクトベースの特徴
項目がオブジェクトである場合、フレームシーケンス中のオブジェクトの持続時間は顕著な特徴となる。例えば、監視カメラの場合、不審な事象は、持ち主不明のかばんである可能性があり、これは、人間は長時間静止していない傾向があるため、容易に検出することができる。この例において、移動オブジェクトは、瞬時に完全な静止オブジェクトとなる。
【００３０】
軌跡の全長は次のように定義することができる。
【００３１】
【数２】
2006024210.tif 000004
【００３２】
これは、｜Ｔ（１）−Ｔ（Ｎ）｜に等しいオブジェクトの全変位量とは異なる。
【００３３】
全方位記述子は、オブジェクトのグローバル方向を表す。カメラの配置に応じて、長さに関連する記述子を用いて異常な経路を区別することができる。長さ／持続時間の比率は、オブジェクトの平均速度を表す。
【００３４】
方位φ（ｔ）、アスペクト比δｙ＝δｘ、傾き（すなわち垂直軸とオブジェクトの主対角線との間の角度）、サイズ、瞬間速度｜Ｔ（ｎ）−Ｔ（ｎ−ｋ）｜＝ｋ、位置、および色といったオブジェクトの動的特性はヒストグラムによって表される。位置ヒストグラムは、フレーム中でオブジェクトが現れる座標を記録しておく。
【００３５】
色は、少数の支配的な色のヒストグラムを用いて表すことができる。カラーヒストグラムを用いた場合、オブジェクト、例えばスポーツビデオにおいて対抗する選手同士を識別することができる。
【００３６】
サイズヒストグラムを用いた場合、オブジェクトの動的特性を求めることができる。例えば、カメラに向かう方向に移動するオブジェクトを、そのオブジェクトのサイズが大きくなるものと仮定して、カメラから離れる方向に、あるいはカメラと平行に移動する別のオブジェクトと区別することができる。
【００３７】
オブジェクトは、追跡中に異なる速度で移動する可能性があるため、オブジェクトの瞬間速度をヒストグラムに累積することができる。事象によっては、速度が重要な側面となるものもある（例えば、歩行者の群衆の中で走っている人物）。速度ヒストグラムは、動きの不規則性、例えば不規則に移動するオブジェクトを解釈するために用いることができる。例えば、速度ヒストグラムを用いて交通事故を検出することができる。これは、累積速度が通常の交通の流れでは均等に分布するのに対して大きく変化するためである。
【００３８】
方位ヒストグラムは優れた記述子である。例として、特定の経路を移動するオブジェクト、例えば円状に移動するか、あるいは揺れ動くオブジェクトを区別することが可能になる。例えば、誤った車線を逆走してから再び正しく走り出す車両を検出することが可能であり、これは、グローバル方位を用いた場合には検出されない可能性がある。
【００３９】
アスペクト比は、人間と車両を区別するために優れた記述子である。アスペクト比ヒストグラムは、軌跡中で人物が横たわっているか、かがんでいるか、あるいは立っているかを検出することができる。
【００４０】
オブジェクトの座標は、軌跡間の空間的な相関を明らかにする。しかし、用途によっては、オブジェクトの座標に関係なく、軌跡の形状の類似性を区別することのほうが重要であるものもある。
【００４１】
図２に示すように、オブジェクトの瞬間速度２０１および方位２０２は、空間的な平行移動がある場合にも、形状の類似性を成すことができる。これらの２つのシーケンス２０１〜２０２は、図３に示すような軌跡の座標から時間関数への写像Ｒ２→Ｒである。
【００４２】
フレームベースの特徴
項目がフレームである場合、フレームベースの特徴は、各フレームの特性を特定する。フレームベースの特徴は、フレーム中の可視のオブジェクトの数が増えるほど顕著になる。
【００４３】
フレーム中で検出されるオブジェクトの数は、フレームベースの特徴の１つである。この特徴は、異常事象、例えば誰もいないはずの部屋の中の１人または複数の人物の指示を行うことができる。オブジェクトの全サイズもまた、部屋の占有（occupancy）レベルを示すことができる。位置ヒストグラムの総計は、オブジェクトがどこにあるかを示す。オブジェクトの瞬間方位のヒストグラムはオブジェクトの方向を示し、このオブジェクトの方向は、交通の流れの変化、例えば誤った車線への進入を検出するために用いることができる。スポーツビデオにおいて、方位は、攻撃している方のチームを示すことができる。速度は、フレーム中のオブジェクトの動きを規定する。この特徴は、オブジェクトの速度が他のフレームと異なるフレームを特定することができる。フレームベースのアスペクト比ヒストグラムおよびサイズヒストグラムも同様に定義される。
【００４４】
ＨＭＭ表現
本発明では、項目の座標特徴、方位特徴、および速度特徴を、ＨＭＭパラメータセットによって特徴付けられるパラメータ空間λに変換する。ＨＭＭは、有向グラフ中のいくつかの相互接続された状態を含む確率モデルであり、各状態は観測可能な出力を放出する（emit）。各状態は、２つの確率分布、すなわち、状態間の遷移分布、および出力シンボル間の放出分布によって特徴付けられる。
【００４５】
このようなモデルによって記述されるランダム系は、一連の出力シンボルを生成する。この系の活動は出力シンボルシーケンスを介して間接的に観測され、状態シーケンスは直接観測することができないため、これらの状態は隠れていると言われる。
【００４６】
本発明では、軌跡情報を有向グラフの放出される観測可能な出力として置き換える。すると、隠れ状態は、時空間軌跡の連続座標の推移的特性を表す。確率が最大となる状態シーケンスが軌跡に対応するモデルとなる。
【００４７】
ガウス観測によるＫ状態｛Ｓ１，Ｓ２，．．．，ＳＫ｝連続ＨＭＭの単純な仕様は、
１．事前確率のセットπ＝｛πｉ｝。ここで、πｉ＝Ｐ（ｑ１＝Ｓｉ）であり、１≦ｉ≦Ｋである。
２．状態遷移確率のセットＢ＝｛ｂｉｊ｝。ここで、ｂｉｊ＝Ｐ（ｑｔ＋１＝Ｓｊ｜ｑｔ＝Ｓｉ）であり、１≦ｉ，ｊ≦Ｋである。
３．混合モデルの平均、分散および重みＮ（Ｏｔ，μｊ，σｊ）。ここで、μｊおよびσｊは状態ｊの平均および共分散である。
によって与えられる。
【００４８】
上記において、ｑｔおよびＯｔは時刻ｔにおける状態および観測値である。各軌跡Ｔについて、本発明では、よく知られたＢａｕｍ−Ｗｅｌｃｈプロセスを用いてｌｅｆｔ−ｔｏ−ｒｉｇｈｔトポロジを有するＭ混合（M-mixture）ＨＭＭλ＝（π，Ｂ，μ，σ）を当てはめる。本発明では、連続プロセスを効率的に記述できることから、ｌｅｆｔ−ｔｏ−ｒｉｇｈｔトポロジを選択する。本発明では、軌跡そのものを訓練データとして用いてＨＭＭモデルを訓練する。言い換えれば、本発明における訓練は教師なしである。
【００４９】
結果として、各軌跡は別個のモデルに割り当てられる。最適な状態数および混合数は、軌跡の複雑度および持続時間に依存する。訓練中に全状態の全ガウス分布に十分な証拠を与えるために、軌跡の持続時間は、混合数に状態数を掛けたものよりも十分に長くなければならない（Ｎ＞＞Ｍ×Ｋ）。一方、状態は、基本的な軌跡パターンとして考えることができる。したがって、軌跡に応じて、状態数は、別個のパターンを適当に特徴付けるほど十分に大きく、なおかつ当てはめすぎを防ぐほど十分に小さい。
【００５０】
事象に対する特徴
上述のように、事象は、「所与の場所および時刻における動作」として定義することができる。本発明では、本発明により抽出した特徴を用いて２つのタイプの事象、すなわち、オブジェクトベースの事象およびフレームベースの事象を検出する。オブジェクトベースの事象はオブジェクトをクラスタリングすることによって検出される。同様に、フレームベースの事象は、フレームのクラスタリングから検出され、特定の瞬間または事象の持続時間に対応する。
【００５１】
さらに、本発明では、通常事象と異常事象を検出する。通常事象は、活動の共通性、例えば、ほとんどの人が歩く経路等を示す。異常事象は、活動の特殊性（distinctness）に関連する。例として、歩行者の群衆の中で走っている人物、ならびに走っている群衆の中で歩いている人物は異常なものとして解釈される。
【００５２】
通常事象の検出
図４は、本発明による通常事象を検出する方法４００を示す。上述のような項目（オブジェクトまたはフレーム）についてビデオから特徴４１０を抽出する。特徴は、ビデオ中に存在する低レベルの視覚的または聴覚的特徴、例えば色および動き、または音量および音の高さとすることができる。特徴は、上述のようにオブジェクトベースまたはフレームベースであり得る。さらに、特徴の高次統計モーメントを求めるか、あるいは、特徴をモデルによって表現することができる。
【００５３】
項目特徴毎に、対になったオブジェクトまたはフレームの類似性を用いて、抽出した特徴に基づいて類似性行列を構成する４２０。類似性は、距離関数に関するものとすることができる。例えば、オブジェクトが３つある場合、類似性行列Ａは３×３となり（図６を参照）、フレームが１０００個ある場合、類似性行列Ａは１０００×１０００となる。類似性行列は、関連出願により詳細に記載されている。
【００５４】
次に、全ての特徴の類似性行列を加重加算および［０：１］への正規化によって総計し４３０、行列の総計を得る。加重は、事前情報および用途に応じて、いくつかの特徴を他の特徴より優先させてもよい。
【００５５】
本発明では、Ｒｉｔｚ値を用いて類似性行列の総計に固有ベクトル分解４４０を適用する（C. C. Paige、B. N. Parlett、およびH. A. van der Vorst著「クリロフ部分空間からの近似解および固有値境界（Approximate solutions and eigenvalue bounds from Krylov subspaces）」（Numer. Linear Algebra Appl., 2, pp. 115-133, 1995）を参照）。分解は以下のステップを含む。所定数の固有値を生成する。固有値を最初から最後まで順番に並べる。固有値を用いて固有ベクトルを求める。固有ベクトルにそれ自身を外積として掛け、類似性行列の総計の近似値を再構成する。本発明の方法では、１番目の固有ベクトルについて、１番目および２番目の固有ベクトルについて、最初の３つの固有ベクトル等について、といった具合に再構成された類似性行列の近似値を生成し、各再構成は、所定数の固有値まで固有ベクトルを１つずつ多く含む。
【００５６】
各類似性行列の総計の近似値にクラスタリング４５０を適用する。クラスタリング４５０は、基礎となる特徴に応じて同様の項目（オブジェクトまたはフレーム）からなるグループを特定する。各クラスタリングは評価されて、クラスタ有効性スコア４６０が求められる。
【００５７】
類似性行列の総計の近似値をすべて評価したら、最も高いクラスタ有効性スコアを生じる行列を、通常事象４７０を最も良く検出する行列として選択する。
【００５８】
オブジェクト追跡用途ではごく一般的である、持続時間の異なる軌跡の対間距離を求めることは可能であるが、ベクトルの大きさが一定である均一なデータ空間に全ての軌跡を写像することは可能でないことに留意されたい。均一な特徴サイズを必要とする従来技術のクラスタリング方法は、本発明には役立たない。したがって、本発明ではスペクトルクラスタリングを提供する。
【００５９】
次に、本発明の方法のさらなる詳細を説明する。
【００６０】
類似性行列
項目特徴４１０毎に、ビデオ中の全てのオブジェクトまたは全てのフレームについて類似性行列Ａを構成する４２０。類似性行列の要素ａｉｊは、対応する項目（オブジェクトまたはフレーム）ｉおよびｊの類似度と等しい。類似性は次のように定義される。
【００６１】
【数３】
2006024210.tif 000005
【００６２】
ここで、ｄ（ｉ，ｊ）は距離であり、σ２は定数スカラ値である。行列Ａ∈Ｒｎ×ｎは半正値の実対称行列であり、よってＡＴ＝Ａであることに留意されたい。
【００６３】
ＨＭＭベースの特徴の場合、距離ｄ（ｉ，ｊ）は、特徴の相互適合性スコアを用いて測定される。本発明では、２つの軌跡間の距離をＨＭＭパラメータ化したもので次のように定義する。
【００６４】
【数４】
2006024210.tif 000006
【００６５】
これは、軌跡同士の互いのモデルに対する相互適合性（cross-fitness）に対応する。
【００６６】
Ｌ（Ｔａ；λａ）項およびＬ（Ｔｂ；λｂ）項は、軌跡の自己適合モデルに対する尤度を示す。すなわち、本発明ではモデルの最尤応答を得る。クロス項Ｌ（Ｔａ；λｂ）およびＬ（Ｔｂ；λａ）は、他方の軌跡モデルによって生成される軌跡の尤度を明らかにする。言い換えれば、２つの軌跡が同じである場合、クロス項は最大値を有し、式（１）はゼロに等しい。一方、２つの軌跡が異なる場合、それらが互いのモデルから生成されたものである尤度は小さく、距離は大きい。
【００６７】
固有ベクトル分解
対称行列の固有値および固有ベクトルへの分解は固有ベクトル分解として知られている。これまで、固有ベクトル分解はスペクトルクラスタリングを用いて行われてきた（G. L. ScottおよびH. C. Longuet-Higgins「近接行列の固有ベクトルの再定位による特徴の分類（Feature grouping by relocalisation of eigenvectors of the proximity matrix）」（Proc. British Machine Vision Conference, pp. 103-108, 1990）、M. MeilaおよびJ. Shi著「ランダムウォークによる分割の学習（Learning Segmentation by Random Walks）」（Proc. Advances in Neural Information Processing Systems, 2000）、Ng、M. JordanおよびY. Weiss著「スペクトルクラスタリングについて：解析とアルゴリズム（On spectral clustering: Analysis and an algorithm）」（Proc. of Neural Information Processing Systems, 2001）、およびY. Weiss著「固有ベクトルを用いた分割：統合的な視点（Segmentation using eigenvectors: a unifying view）」（Proc. IEEE International Conference on Computer Vision, 975-982, 1999））。
【００６８】
しかし、データ分布の最適なクラスタリングと、クラスタリングに用いるべき固有ベクトルの数との間の関係を確立する方法は知られていない。
【００６９】
本発明は、部分空間を張る絶対値での最大固有値の数がクラスタ数よりも１つ少ないことを示す。
【００７０】
Ｖ≡［ｖ１，ｖ２，．．．，ｖｎ］を、固有ベクトルの列によって形成される行列とする。Ｄを対角行列ｄｉａｇ［λ１，λ２，．．．，λｎ］とする。固有値がλ１≦λ２≦λｎである場合、一般化固有値問題は次のようになる。
【００７１】
【数５】
2006024210.tif 000007
【００７２】
かつＡ＝ＶＤＶ−１である。行列Ａは対称的であるため、別個の固有値に対応する固有ベクトルは実数の正規直交ＶＶＴ＝ＶＴＶ＝Ｉとなり、これはＡ＝ＶＤＶＴであることを意味する。
【００７３】
行列Ｐｋを、行列Ｖの列が張る部分空間Ｋの行列、例えばＰｋ＝［ｖ１  ｖ２  ．．．ｖｋ，０］とする。ここでＶはＡ＝ＶＤＶＴを満たす正規直交基底である。本発明ではここで、切断（truncated）行列Ｐｋの行であるベクトルｐｎを次のように定義する。
【００７４】
【数６】
2006024210.tif 000008
【００７５】
本発明では、行列Ｐｋの各行を
【００７６】
【数７】
2006024210.tif 000009
【００７７】
によって正規化する。次に、正規化された行を用いて、Ｃｋ＝ＰｋＰＴｋによって相関行列を求める。所与のＰｋについて、ｐｉｊの値は、例えばオブジェクトｉとオブジェクトｊの間の類似度を示す。１に近い値は一致に相当し、負の値および０に近い値は、オブジェクト（またはフレーム）が異なることを示唆する。εを、次式のような、行列Ｃｋの値を関連（association）行列Ｗｋの２値量子化した値に伝達する閾値とする。
【００７８】
【数８】
2006024210.tif 000010
【００７９】
ここで、ε≒０．５である。すると、クラスタリングは、１に等しい関連値、すなわちｗｉｊ＝１を有するオブジェクトの分類となる。
【００８０】
これが機能する理由を説明するために、固有ベクトルは、ｖＴｖ＝１によって制約される古典的な極値問題ｍａｘｖＴＡｖの解であることを思い出してほしい。すなわち、重みの二乗の和が１であるという制約で、最大の分散を有する変数の線形の組み合わせを見つける。通常のラグランジュの表現ｖＴＡｖ−λ（ｖＴｖ−１）の最小化は、（Ｉ−Ａ）ｖ＝λＩｖであることを示唆する。したがって、ｖは最大の固有値を有する固有ベクトルである。
【００８１】
結果として、類似性行列の列を、最大の固有値を有し、Ｋ１を張る固有ベクトルｖ１に射影すると、ａｉｊの分布は最大の分散、よって最大の分離を有する。閾値操作は、分離が高い場合に最良に行われることを頭に留めておく。この目的で、値の分布が２つの別個のクラスしか有さない場合、中心を通る釣合のとれた閾値が点を２つの別個のクラスタに分割する。同じ理由で、２番目に大きい固有値を有する固有ベクトルｖ２について、本発明では、ｖ１⊥ｖ２であることから、固有ベクトルｖ１を用いて射影空間を正規化した後に最良の分離を生じる基底ベクトルを得る。
【００８２】
したがって、本発明では、部分空間を張る絶対値での最大の固有値の数がクラスタの数よりも１つ少ないと言う。
【００８３】
類似性の定義に応じて、１番目の固有ベクトル、あるいは１番目と２番目の固有ベクトル、あるいは１番目の最大値と２番目の最大値の比である一般化された２番目の最小値のみを用いることに対して、対象とするクラスタの数に対して正確な固有ベクトルの数を選択しなければならない。従来技術において通常なされるように１つまたは２つの固有ベクトルのみを使用した場合、クラスタが３つ以上ある用途で失敗する。
【００８４】
閾値の値は、依然として求める必要がある。本発明では、最大の分離をもたらす射影を得ているが、分離の程度、すなわち基底ベクトルに射影された値の最大値および最小値は求めていない。便宜上、本発明では、射影、すなわち現在の射影行列（Ｖｋ）の行をｐＴｐ＝１として正規化し、次に相関ＶＴｋＶｋを計算する。相関は、同様の射影を有する行を１に近づけ、等しい値をちょうど１とし、非類似性の高い値を０とする。本発明では、正規直交基底上の異なるクラスタの点間の分離または距離を最大化することによって、点の直交性をそのクラスタに応じて最大化する、すなわち、それらの点が同一のクラスタにある場合はｐｉｐｊ≒１とし、異なるクラスタにある場合はｐｉｐｊ≒０とする。
【００８５】
クラスタの数はその場その場で推定することができる。類似性行列の近似値Ａの各固有値を再構成した後、本発明では、クラスタリングの結果を用いて有効性スコアαｋ４６０を次のように求める。
【００８６】
【数９】
2006024210.tif 000011
【００８７】
ここで、Ｚｃは、クラスタｃに含まれる項目（オブジェクトまたはフレーム）のセットであり、ＮｃはＺｃ中のオブジェクト（またはフレーム）の数である。有効性スコアは、適合度が高くなるほど増加する。したがって、本発明では、このスコアの極大値を評価することによって、クラスタ数の正確な数を自動的に求め、通常事象４７０を特徴付ける。
【００８８】
したがって、本発明では、「クラスタの総数はいくつであるべきか」という当然のクラスタリングの疑問に答える。まとめると、所与の最大クラスタ数ｋ＊のクラスタリングは以下を含む。
１．Ｒｉｔｚ値λｋ≒θｋを用いて類似性行列Ａの固有ベクトルを求め、ｋ＝１，．．．，ｋ＊について固有ベクトルｖｋを見つける。
２．ｋ＝１，．．．，ｋ＊についてＰｋ＝ＶｋＶＴｋおよびＱｋを見つける。
３．クラスタを求め、有効性スコアαｋを計算する。
４．α’＝ｄα／ｄｋを求め、極大値を見つける。
【００８９】
最大クラスタ数ｋ＊は、単なる上限であるため、最適一致をもたらすクラスタ数の決定に影響を与えない。
【００９０】
Ｋ平均との比較
本発明による固有ベクトルクラスタリングは、従来技術のＫ平均クラスタリングのいくつかの利点を有する。
【００９１】
最も重要なこととして、「平均」または「中心」ベクトルは、異なる持続時間を有する軌跡については定義することができない。本発明では、対になった距離しか得られない。固有ベクトル分解では、中心距離ではなく相互特徴間距離を使用する。
【００９２】
通常のＫ平均クラスタリングは、クラスタ中心間で変動する可能性があり、初期値が異なると、完全な非類似クラスタを生じる可能性がある。また、Ｋ平均クラスタリングは局所最適値に執着してしまう可能性がある。したがって、Ｋ平均に基づくクラスタ数の推定は常に正確であるとは限らない。さらに、Ｋ平均クラスタリングの計算の複雑度は、特徴ベクトルのサイズが大きくなるにつれて増す。
【００９３】
異常事象の検出
図５は、ビデオ中の異常事象を検出する方法５００を示す。上述のように、項目の特徴５１０を抽出する。各特徴について、項目毎に類似性行列を求める５２０。項目（オブジェクトまたはフレーム）毎に一致性スコアを求める５３０。一致性スコアを用途に応じて重み５４１によって重み付けし、重み付き一致性スコアをもたらすことができる５４０。各項目の重み付き一致性スコアを総和し５５０、スコアリングした項目を順番に並べる５６０。一致性スコアの合計が最も低い項目は、異常事象５７０を決定するものとみなされる。
【００９４】
単純な３項目の類似性行列について図６に示すように、所与の特徴ｆの項目（オブジェクトまたはフレーム）ｉの一致性スコアは、その特徴に属する類似性行列の対応する行または列の和である。
【００９５】
【数１０】
2006024210.tif 000012
【００９６】
異なる特徴の応答を総和するために、本発明では加重和５５０を用いる。本発明では、項目オブジェクトの一致性スコアの合計を加重和として得る。
【００９７】
【数１１】
2006024210.tif 000013
【００９８】
ここで、同等の特徴についてｗｆ＝１である。次に、本発明では、各項目（オブジェクトまたはフレーム）をその一致性スコアの和に関して順番に並べる５６０。スコアの最も低い項目（オブジェクトまたはフレーム）は、最も高いスコアを有する項目から最も異なるものであり、最も異常な事象５７０に関連付けることができる。
【００９９】
一致性スコア５３０の１つの明確な利点は、全ての事象が類似している場合には異常さを主張しないことである。さらに、或る事象が残りの事象と類似していないほど、スコアは低くなる。これは、本発明による一致性スコアが曖昧さの程度を有効に判定するとともに、異常事象を通常事象と区別することを示す。
【０１００】
特徴の選択および適応的な重み付け
クラスタリングを行う前に最も差別的な特徴を選択することも可能である。しかし、特徴の選択は、用途に関する事前知識、および事象の性質の理解を必要とする。したがって、本発明では、差別的な特徴を事前選択するのではなく、クラスタリングに差別的な特徴を判定させるほうが好ましい。さらに本発明者は、固有基底の切断が、類似性の高い特徴同士を引き寄せ、他の特徴を引き離すことによって、特徴の分布の不均一さを増幅することを見出している。
【０１０１】
特徴の分散は、上記の特徴の重みｗｉを選択するための有効な方法である。特徴の分散は、対応する類似性行列から求められる。特徴が独特の情報を供給する場合、分散の値は高くなる。その逆の場合も成立する。したがって、本発明では次のように重みを割り当てる。
【０１０２】
【数１２】
2006024210.tif 000014
【０１０３】
ここで、ａｉｊは特徴ｆの類似性行列Ａｆの要素である。これにより重要な特徴が強調される。
【０１０４】
本発明を好適な実施形態の例として説明してきたが、本発明の精神および範囲内で様々な他の適応および変更を行うことができることが理解される。したがって、添付の特許請求の範囲の目的は、本発明の真の精神および範囲に入るそうした変形および変更をすべて網羅することである。
【図面の簡単な説明】
【０１０５】
【図１】本発明による特徴の分類である。
【図２】特徴の速度と方位の時間シーケンスである。
【図３】サンプル座標シーケンスである。
【図４】通常事象を検出する方法のフロー図である。
【図５】異常事象を検出する方法のフロー図である。
【図６】スコアリングされた類似性行列のブロック図である。
【図１】
2006024210.tif 000015
【図２】
2006024210.tif 000016
【図３】
2006024210.tif 000017
【図４】
2006024210.tif 000018
【図５】
2006024210.tif 000019
【図６】
2006024210.tif 000020
【外国語明細書】
2006024210.tif 000021
2006024210.tif 000022
2006024210.tif 000023
2006024210.tif 000024
2006024210.tif 000025
2006024210.tif 000026
2006024210.tif 000027
2006024210.tif 000028
2006024210.tif 000029
2006024210.tif 000030
2006024210.tif 000031
2006024210.tif 000032
2006024210.tif 000033
2006024210.tif 000034
2006024210.tif 000035
2006024210.tif 000036
2006024210.tif 000037
2006024210.tif 000038
2006024210.tif 000039
2006024210.tif 000040
2006024210.tif 000041
2006024210.tif 000042
2006024210.tif 000043
2006024210.tif 000044
2006024210.tif 000045
2006024210.tif 000046
2006024210.tif 000047
2006024210.tif 000048
2006024210.tif 000049
2006024210.tif 000050
2006024210.tif 000051