(57)【要約】【課題】方法は、映像の構造と整合性のある映像内の事象を検出するように、映像の構造を無管理設定で学習する。【解決手段】特徴集合が映像から選択される。選択された特徴に基づいて、階層的統計モデルが更新され、階層的統計モデルの情報利得が評価される。冗長な特徴は次に、フィルタリングされ、フィルタリングされた特徴に基づいて、階層的統計モデルが更新される。ベイズ情報基準が、それぞれのモデルおよび特徴集合対に適用され、特徴集合対は次に、映像内の事象を検出するために、基準に従ってランク順序付けされることができる。【選択図】図１
2005196750.tif 000002
【特許請求の範囲】
【請求項１】
映像の構造と整合性のある前記映像の事象を検出するように、前記映像の構造を学習する方法であって、
前記映像から特徴集合を選択すること、
それぞれの特徴集合について、階層的統計モデルを更新すること、
前記階層的統計モデルの情報利得を評価すること、
冗長な特徴をフィルタリングすること、
フィルタリングされた特徴に基づいて前記階層的統計モデルを更新すること、
それぞれのモデルおよび特徴集合対にベイズ情報基準を適用すること、
及び
前記モデルおよび特徴集合対をランク順序付けて、無管理で、前記映像の構造を学習し、前記映像の事象を検出すること
を含む映像の構造を学習する方法。
【請求項２】
前記階層的統計モデルは、ガウス混合を用いる
請求項１記載の方法。
【請求項３】
前記階層的統計モデルは、隠れマルコフモデルを用いる
請求項１記載の方法。
【請求項４】
前記映像の事象の状態は、階層的隠れマルコフモデルにおける低レベル隠れマルコフモデルとしてモデル化され、前記事象は、前記階層的隠れマルコフモデルにおける高レベルマルコフ鎖としてモデル化される
請求項３記載の方法。
【請求項５】
前記特徴は、支配的な色比、動き強度、カメラ平行移動の最小２乗推定、音声ボリューム、スペクトルロールオフ、低帯域エネルギー、高帯域エネルギー、ゼロ交差レートを含む
請求項１記載の方法。
【請求項６】
前記特徴は、マルコフブランケットでフィルタリングされる
請求項１記載の方法。
【請求項７】
前記評価することは、期待値最大およびマルコフ鎖モンテカルロ法を用いて行われる
請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は包括的に、映像解析、より詳細には、映像における事象を検出するための、映像構造の無管理（unsupervised）学習に関する。
【背景技術】
【０００２】
映像を要約し、ブラウジングし、索引付けするために、映像において、構造および事象を検出し特定する必要がある。構造は、映像の構文構成を表し、事象は、映像の構造と整合性のある映像の意味論的概念の発生を表す。
【０００３】
たとえば、最も低いレベルでは、構造は、反復される配色(color scheme)、テキストパターン、または動き(motion)によって示されることができる。中間レベルでは、構造は、反復されるカメラの移動(movement)、たとえば、パンとそれに続く接写に基づくことができる。高いレベルでは、構造は、映像における特定の状態遷移に関連する可能性がある。たとえば、ゴルフ映像において、ティーショットは普通、空気中を飛ぶボールがフェアウェイに着地しフェアウェイ上を転がるまで、ボールに追従するパンによって追従される。
【０００４】
構造を特定する問題は、２つの主要な部分を有し、２つの部分とは、構造の記述すなわちモデルを見つけること、および、記述に一致する映像内のセグメントを突き止めることである。ほとんどの従来技術は、これらの２つのタスクを別々のステップで行う。前者は通常、訓練と呼ばれ、一方、後者は分類またはセグメント化と呼ばれる。
【０００５】
構造を表す１つの考えられる方法は、隠れマルコフモデル（ＨＭＭ）を用いることである。Rabiner著「A tutorial on hidden Markov models and selected applications in speech recognition」Proceedings of the IEEE, Vol. 77, pp.257-285, February 1989を参照されたい。ＨＭＭは、離散的な状態空間を有する確率モデルである。ＨＭＭは、映像などの時間的に相関する信号に対してうまく働く。ＨＭＭは、音声認識、筆跡認識、および映像の動き解析などの多くの異なる用途で首尾よく適用されてきた。
【０００６】
映像の場合、ＴＶプログラムの異なるジャンルは、それぞれのジャンルについて訓練されたＨＭＭを用いて区別されてきた。Wang等著「Multimedia content analysis using both audio and visual clues」IEEE Signal Processing Magazine, Vol. 17, pp.12-36, November 2000を参照されたい。サッカーゲームの高いレベルの構造、たとえば、プレー対ブレークは、それぞれのクラスについて訓練されたＨＭＭのプールを用いて描写された(delineate)。Xie等著「Structure analysis of soccer video with hidden Markov models」Proc. International Conference on Acoustic, Speech and Signal Processing(ICASSP), 2002、１９９８年１０月２７日にChang他に発行された米国特許第５，８２８，８０９号「Method and apparatus for extracting indexing information from digital video data」（フットボールゲームが解析される）を参照されたい。
【０００７】
上述した方法の全てが、管理学習として知られるものを用いる。そこでは、構造および事象それ自体ではない場合、構造および事象の重要な側面および制約が明示的に特定され、訓練用映像が、訓練および分類についてのこれらの先入主観(preconceived notion)に従ってラベル付けされる。その方法論は、小規模での特定の映像ジャンルに適している。しかし、こうした方法は、大規模でのより一般的な場合に拡張されることができない。
【０００８】
したがって、映像のジャンルについての事前知識なしで、ラベルが付いていない映像において目立った構造および事象を自動的に確定することができる無管理学習技法を用いることが望ましい。
【０００９】
無管理学習は、遺伝子共通構造(motif)の発見およびデータマイニングに適用されてきた。Xie等著「Learning hierarchical hidden Markov models for video structure discovery」Tech. Rep. 2002-006, ADVENT Group, Columbia University, 2002, December 2002および２００３年６月５日に出願された米国特許出願第２００３０１０３５６５号、Xie他著「Structural analysis of videos with hidden Markov models and dynamic programming」を参照されたい。
【００１０】
クラスタリング技法は、ＴＶドラマの物語ユニットを発見するために、ショットのキーフレームに適用されてきた。しかし、映像の時間依存性は正式にはモデル化されなかった。Yeung等著「Time-constrained clustering for segmentation of video into story units」Proceedings International Conference on Pattern Recognition (ICPR), 1996を参照されたい。
【００１１】
Ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ型ＨＭＭは、映像において時間的に展開する事象をモデル化するために、大きなＨＭＭ内に積み重ねられた。Clarkson等著「Unsupervised clustering of ambulatory audio and video」International Conference on Acoustic, Speech and Signal Processing(ICASSP), 1999およびNaphade等著「Discovering recurrent events in video using unsupervised methods」Proc. Intl. Conf. Image Processing, 2002を参照されたい。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって、映像の構造モデルを自動的に確定し、モデルと整合性のある、映像における意味論的事象を検出する方法に対する必要性が存在する。
【課題を解決するための手段】
【００１３】
映像において、構造は、整合性のある確定的なまたは確率的な特性を用いて、反復セグメントを規定する。ほとんどの従来技術の方法は、別々のステップで管理学習を用いるが、本発明は、単一の無管理統計的方法を用いる。すなわち、方法は、映像の内容がどんなものであるかという先入主観なしで、映像の信号それ自体によって完全にドライブされる。このため、利点として、本発明は、任意の映像に適用されることができる。
【００１４】
映像に適用されると、単一化された方法は、同時に、構造の統計的記述を確定し、構造に一致する事象を含むセグメントを突き止める。本発明は、映像のマルチレベルの統計的構造を階層的統計モデルとして表し、モデルとモデルのパラメータの両方を学習するための効率的な手順を提供する。階層的モデルは、階層的隠れマルコフモデル（ＨＨＭＭ）または階層的ガウス混合モデル（ＨＧＭＭ）である可能性がある。
【００１５】
映像に適用されると、本発明による無管理学習法は、内容の知識を有する、同程度の管理方法より正確である可能性がある。
【発明を実施するための最良の形態】
【００１６】
図１に示すように、本発明者等の発明は、映像１０１、すなわち、音声−視覚ストリームの構造を確定するのに無管理学習を用いる。構造を知って、本発明者等は、構造と整合性のある映像の事象を検出することができる。構造は、階層的統計モデル２００の形態である。図２を参照されたい。階層的モデルは、階層的隠れマルコフモデル（ＨＨＭＭ）または階層的ガウス混合モデル（ＨＧＭＭ）である可能性がある。
【００１７】
本発明者等の発明は、映像１０１が以下の性質を有するという観測に基づく。本発明者等は、映像を概念によって理解するため、映像の構造は、離散的状態空間にある。本発明者等は、所与の映像ジャンルまたは領域には、少数の概念の集合があると考える。映像の特徴１０２は確率的である。それは、映像の種々のセグメントは、セグメントが概念的に同じ時でも、全く同じ特徴を有することがめったにないためである。映像の特徴は、高い時間相関性を有する。それは、ほとんどの映像が、シーンの変化よりずっと速いレートで、たとえば、３０または６０フレーム／秒でサンプリングされるからである。
【００１８】
本発明者等は、特徴における統計的特性を強調するために、「構造」という用語を用いる。特定の映像領域が与えられると、こうした統計的構造は、オブジェクトの発生、オブジェクトまたは映像に描写されるシーンの変化を表す事象に対応する場合が多い。
【００１９】
特に、本発明者等は、密な(dense)映像構造に焦点を当てる。密によって、本発明者等は要素たる構造が、共通のパラメトリッククラスとしてモデル化される場合を言う。構造の代替を表すことは、十分に全映像を記述することになる。こうして、映像における大部分の背景から疎な事象を区別するために、同じパラメトリック形態である場合もない場合もある、明示的な背景クラスに対する必要性は存在しない。
【００２０】
上述の性質に基づいて、本発明者等は、時間的に相関する離散的状態空間において確率的観測をモデル化し、効率的な処理を容易にする２、３の弱い仮定を採用する。それぞれの事象内において、状態は、離散的であり、低レベルの隠れマルコフモデルである可能性がある。観測は、固定したパラメトリック形態（通常ガウス）の下で状態と結合する。本発明者等は、事象遷移を高いレベルでのマルコフ鎖としてモデル化する。この簡単化によって、モデルのパワーに対して低コストでの効率的な処理が可能になる。
【００２１】
本発明者等は、単一化された統計的フレームワークにおいて、映像の事象の時間依存性および汎用構造をモデル化する。本発明者等は、映像において循環事象を隠れマルコフモデル（ＨＭＭ）として、これらの事象間のより高いレベルの遷移をより高いレベルのマルコフ鎖としてモデル化する。
【００２２】
ＨＭＭのこの階層は、本発明による階層的隠れマルコフモデル（ＨＨＭＭ）２００を形成する。隠れ状態干渉およびパラメータ推定は、期待値最大化（ＥＭ）プロセス１３０を用いて学習され、評価される。本発明者等の方法は、異なる複雑さの事象にスケーラブルであるために一般的である。方法はまた、従来の領域知識が、状態連結性、マルコフ鎖のレベル数、および状態の時間スケールについて組み込まれる可能性がある点で柔軟性がある。しかし、方法は先験的領域知識なしで正確に働くことに留意する。
【００２３】
統計的階層モデルはまた、ガウス混合モデルなどの他のベイズ分類器の形態である可能性があることに留意されるべきである。ガウス混合において、それぞれの観測は、平均μｋおよび分散行列Σｋを有するｄ次元ガウス密度の混合から独立して生ずると考えられる。こうしたベイズベースの方法論は、ここではそうであるように、未知のデータに当てはめた複雑過ぎるモデルに自動的にペナルティを課す。ガウス混合モデルについて、モデルにおける成分の「最適な」数は、データ集合を分割するために選択される。Langrognet等著「A Gentle Tutorial on the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models」Technical Report, University of Berkeley, ICSI-TR-97-021, 1997およびHusmeier等著「Bayesian Approaches to Gaussian Mixture Modelling」IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, No. 11, 1133-1142, 1998を参照されたい。
【００２４】
本発明者等はまた、抽出されるべき適切な特徴集合を選択するプロセスを提供する。領域知識が用いられない無管理設定において、これが必要である。ベイズ学習技法を用いて、モデルの複雑さが学習される。反転ジャンプマルコフ鎖モンテカルロ（ＭＣＭＣ）法を用いて、モデル空間にわたって検索が行われる。ベイズ情報基準（ＢＩＣ）１７０は、本発明者等のモデルの事後確率として適用される。
【００２５】
特徴選択の場合、本発明者等は、ラッパステップが、全ての考えられる特徴集合１０３を、相互情報利得基準に従って互いに一致する整合性のある部分集合に分割する反復フィルタ−ラッパ法を用いる。フィルタステップ１５０は、近似マルコフ「ブランケット」、すなわち、特定のノードの親、兄弟、および子供のノードを見つけることによって、それぞれの特徴の部分集合における冗長な次元を消去する。マルコフブランケットはよく知られており、以下で詳細に述べられる。ＥＭ／ＭＣＭＣ１６０は、以前と同様に、残りの特徴に適用され、得られる部分集合は、部分集合の事後適合性に関して修正ＢＩＣ１７０に従ってランク付けされる（１８０）。
【００２６】
本発明者等の発明による方法は、最大尤度（ＭＬ）パラメータ推定、モデルおよび特徴選択、構造復号化、および内容セグメント化が、単一の統合プロセスにおいて行われる点でエレガントである。
【００２７】
特徴プール
予備ステップとして、特徴１０２は、映像１０１、たとえば、支配的な色比、動き強度、カメラ平行移動、音声ボリュームなどから生成される（１１０）。生成された特徴はまた、映像の内容から学習されることができる。
【００２８】
生成された特徴１０２は、全ての考えられる特徴集合Ｆ＝｛ｆ１、…、ｆＤ｝として特徴プール１０３に格納される。データシーケンスがＸＦ＝Ｘ１ＴＦである場合、時刻ｔにおける特徴ベクトルは、ＸｉＦであり、反復がｉによって示される。
【００２９】
特徴選択
全ての考えられる特徴集合および音声視覚ストリームについて考えられる特徴抽出方式は非常に大きい。問題は、この特定の映像１０１から学習される構造および事象に結合する特徴の部分集合のみを確定することである。
【００３０】
確かに、十分な領域知識がある時、少数の特徴が手動で選択されることができる。しかし、こうした知識は、新しい領域では利用できないか、または、特徴とモデル構造の関係が、特定の映像について明白でない場合が非常に多い。
【００３１】
全ての考えられる特徴集合が非常に大きいため、特徴選択は、２つのタスク、すなわち無関係な特徴を消去すること、および、冗長な特徴を消去することを有する。無関係な特徴は、分類精度を低下させ、一方、冗長な特徴は、新しい情報を生成することなく、計算コストを増す。さらに、無管理構造発見の場合、異なる特徴の部分集合は、異なる事象に関連する場合がある。このため、事象は、一緒にモデル化されるのではなく、別々のモデルを用いて記述されるべきである。したがって、本発明者等の問題の範囲は、時間的に相関するデータストリーム１０１に対して、ＨＨＭＭモデル２００に合う、関連するコンパクトな特徴の部分集合を選択することである。
【００３２】
したがって、それぞれのｉ番目のラウンド中に、特徴プール１０３から無作為に基準特徴集合Ｆｉ１２１をまず選択する（１２０）。また、期待値最大化（ＥＭ）およびマルコフ鎖モンテカルロ(ＭＣＭＣ)法を用いて、（−）Ｆｉ上でＨＨＭＭΘｉ２００を学習する（１３０）。Ｘ（−）Ｆｉのビタビ復号化を行い、基準状態シーケンス（〜）Ｑｉを得る。なお、（−）Ｆｉは、Ｆｉの上に−があることを表す。（〜）Ｑｉも同様で、Ｑｉの上に〜があることを表す。
【００３３】
特徴プール１０３におけるそれぞれの残りの特徴ｆｄ１０４について、再びＥＭおよびＭＣＭＣ１３５を用いて、ＨＨＭＭΘｄを学習し、ビタビ状態シーケンスＱｄを得、基準集合の分割、すなわち、基準分割を確定する。
【００３４】
次に、本発明者等は、基準状態シーケンス（〜）Ｑｉについて、状態シーケンスＱｄに対してそれぞれの残りの特徴の情報利得を評価する（１４０）。提案されたモデルが情報利得を増加させる（increases an information gain test）場合、提案されたモデルが新しい現在のモデルとして受容される。受容の一部として、決定ステップは、モデル事後および提案方策を用いて、提案されたモデルの適合性に基づいて受容確率αを確定する。提案されたモデルは次に、確率αで受容されるか、または、拒絶される。拒絶された特徴は、特徴プール１０３内に残る。
【００３５】
次に、本発明者等は、整合性のある特徴グループを基準集合および関連集合の和集合（−）Ｆｉとして形成するために、かなり大きな情報利得を有する、部分集合（^）Ｆｉ、特徴グループ１４１を見つける。本発明者等はまた、特徴集合についてＨＨＭＭモデル２００を更新する。なお、（^）Ｆｉは、Ｆｉの上に^があることを表す。
【００３６】
本発明者等は、特徴プールをリセットすることによって、以前の候補集合を消去し、処理すべきより多くの特徴が存在する、すなわち、特徴プールが空でない場合、ｉ＝ｉ＋１について再び反復する（１４５）。
【００３７】
マルコフブランケットフィルタリング１５０を用いて、そのマルコフブランケットが存在する最終関連集合（−）Ｆｉ内の冗長で無関係な特徴を消去する。
【００３８】
本発明者等は、関連するコンパクトな特徴部分集合Ｆｉ１５１を持ったままになる。本発明者等は、ＸＦｉに対するモデル適応を用いて、以前と同様に、ＨＨＭＭΘｉ２００を学習し（１６０）、モデルおよび特徴集合を対{Θ、ＸＦｉ}１６１として格納する。
【００３９】
それぞれのモデル−特徴対{Ｆｉ、Θｉ}１６１について、本発明者等は、正規化ＢＩＣを適用することによって、対の適合性を評価する（１７０）。次に、本発明者等は、特徴部分集合をランク付けし（１８０）、得られるランク付けされた対１８１の意味を解釈する。
【００４０】
情報利得を評価すること
上述したプロセスは、基準特徴集合に対して学習された分類器によって誘導されるデータシーケンスの基準ラベル付けを作成する。本発明者等はこの基準に関連する特徴を見つけたい。それぞれの特徴が基準ラベル付けに一致する程度を定量化する１つの適当な尺度は、基準分割を通じて候補特徴について誘導された新しい分割によって達成された相互情報、すなわち、情報利得である。
【００４１】
（〜）Ｑｉに関する特徴ｆの情報利得は、（〜）ＱｉおよびＱｆの間の相互情報として定義される。
【００４２】
【数１】
2005196750.tif 000003
【００４３】
ここで、Ｈ（・）はエントロピー関数である。直観的に、候補特徴ｆについてのより大きな情報利得は、ｆ誘導分割Ｑｆが、基準分割（〜）Ｑｉとより整合性があることを示唆する。それぞれの残りの特徴ｆｄについて情報利得Ｉ（Ｑｆ；（〜）Ｑｉ）を計算した（１４０）後、本発明者等は、系統図(dendrogram)を用いて情報利得ベクトルに対して階層的集積化(agglomerative)クラスタリングを行う。
【００４４】
本発明者等は、全特徴を２つのクラスタに分割する最高のリンクを調べ、上位のクラスタにある特徴を、基準特徴集合と十分な整合性を有する集合として選ぶ。
【００４５】
マルコフブランケット
全ての特徴候補の上に構築した分類器のまわりで情報利得基準をラッピングした後、本発明者等は、整合性を有し、なお同様に冗長性を有する可能性のある特徴の部分集合を有するままにされる。冗長な特徴を特定する手法は、特徴間での条件付き依存性に関連する。このために、本発明者等は、マルコフブランケットを用いてフィルタリングする（１５０）。ｆが特徴部分集合であり、Ｍｆが、ｆを含まないランンダム変数の集合である場合、Ｍｆが与えられたとして、{Ｆ∪Ｃ}＼{Ｍｆ∪ｆ}において、全ての変数と条件付きで独立であれば、Ｍｆはｆのマルコフブランケットである。
【００４６】
計算によって、特徴ｆは、そのマルコフブランケットＭｆが与えられたとして、データ集合の分割Ｃがｆに独立である時、冗長である。従来技術において、特徴集合{Ｍｆ∪ｆ}が与えられたとして、クラスの事後確率分布が、マルコフブランケットＭｆにのみ条件付けられる確率分布と同じでなければならないという等価な条件、すなわち、
【００４７】
【数２】
2005196750.tif 000004
【００４８】
を用いて、マルコフブランケットは一般に特定される。
【００４９】
ここで、Ｄ（Ｐ‖Ｑ）は、２つの確率質量関数Ｐ（ｘ）およびＱ（ｘ）の間のカルバック−ライブラー(Kullback-Leibler)距離である。
【００５０】
しかし、この基準は、時間的ストリーム上での無管理学習にすぐに使用されることができない。それは、クラスの事後分布は、現在のデータサンプルに依存するだけでなく、時間において「隣接する」サンプルにも依存するからである。
【００５１】
本発明者等は、全ての独立した特徴サンプルにわたって事後クラスラベルを条件付けなければならず、こうした条件付けは、条件付けされたサンプルの数が増えるにつれて、事後確率の推定を処理しにくくする。本発明者等は、次元数が高過ぎるため、特徴−クラスタプル(tuple)にわたってカウントすることによって、これらの高次元分布を推定するのに十分なデータを有していない。
【００５２】
したがって、本発明者等は、代替の必要条件を用いる。本発明者等の条件は、最適状態シーケンスＣ１：Ｔは、Ｍｆ∪ｆまたはＭｆを観測することのみに対して条件付けられ、変化しないことを要求する。特定されたそのマルコフブランケットを用いて、特徴を１度に１つ順次取り除くことによって、得られる集合の発散が生じない。それは、本発明者等が、特徴ｆを消去し、そのマルコフブランケットＭｆを維持する場合、特徴ｆは、より多くの特徴が消去される後段で不必要なままであるからである。
【００５３】
実際に、たとえあるとしても少数の特徴が、制限されたサイズのマルコフブランケットを有する。したがって、本発明者等は、変化が十分に小さい、たとえば、５％未満であると仮定すると、状態シーケンスの最も小さい変化を誘導する特徴を順次取り除く。このステップは、本発明者等のＨＨＭＭ学習設定におけるフィルタリングステップであることに留意されたい。それは、本発明者等が、ＨＨＭＭを、それぞれの候補特徴ｆおよびそのマルコフブランケットＭｆについて再訓練する必要がないためである。
【００５４】
ＨＨＭＭが集合ｆ∪Ｍｆに対して訓練されると仮定すると、Ｍｆにおける観測シーケンスを用いてのみ復号化される状態シーケンスＱＭｆは、ｆ∪Ｍｆにおける全観測シーケンスを用いて復号化される状態シーケンスＱｆ∪Ｍｆと比較される。ＱＭｆとＱｆ∪Ｍｆの差が、所定のしきい値未満である場合、特徴ｆは、Ｍｆが特徴ｆのマルコフブランケットであることがわかるため、取り除かれる。
【００５５】
正規化ＢＩＣ
特徴選択プロセスのステップ全体を反復することによって、コンパクトで互いに整合性のある小さな特徴の部分集合｛Ｆｉ｝が互いに共通元を持たなくなる。これらの部分集合に対して学習されたＨＨＭＭモデル｛Θｉ｝は、特徴に対するベストエフォートの適合であるが、モデル｛Θｉ｝は、上述した所望の映像構造の特性についてのマルチレベルマルコフ仮定に適合しない場合がある。
【００５６】
モデル−特徴対１６１の部分集合を評価するための、従来技術の考えられる距離尺度、すなわち、散布(scatter)分離性および最大尤度（ＭＬ）が存在する。前者は、多次元ユークリッド距離が時間依存性を考慮しないため、時間データには適さない。さらに、時間データについての適正な距離尺度を規定することは自明でない。後者は、より高い次元の特徴集合に対して偏りがあることが知られている。
【００５７】
したがって、本発明者等は、正規化ＢＩＣ１７０
【００５８】
【数３】
2005196750.tif 000005
【００５９】
を、ＭＬに対する代替として適用し、正規化ＢＩＣ１７０は、モデルの複雑さを用いて正規化されたデータ尤度（〜）Ｌの兼ね合いをつける。前者は、重み付け係数λを有し、後者は、サンプルの総数ｌｏｇ（Ｔ）によって調整される。隠れ状態が与えられると特徴が独立であるというナイーブベイズの仮定の下で、出力確率Ｐ（Ｘ｜Ｑ）が全て、Ｐ’Ｘ，Ｑ＝Ｐ（Ｘ｜Ｑ）１／Ｄで置き換えられる、すなわち、データ次元Ｄについて正規化されることを除いて、データ尤度は同じ前進後退反復において確定される。
【００６０】
特徴プール１０３の反復分割には、初期化および収束の問題が存在する。ステップ１２０においてランダム基準集合（〜）Ｆｉ１２１を生成する方策は、特徴分割の結果に影響を与える。それは、同じ基準集合を異なるシーケンスで作成しても、異なる最終分割がもたらされる場合があるからである。さらに、得られる構造の表現力または次元数もまた、基準集合によって影響を受ける。
【００６１】
基準集合（〜）Ｆｉの次元が低過ぎる場合、プロセスは、同じグループが互いにほとんど一致する、多くの小さな特徴グループを作成する傾向がある。この場合、学習されたモデルは、異なるモダリティ（音声および映像）からの特徴などの相補的な情報を保持する特徴を用いて特定されることができる、考えられる複雑な構造を特定することができない可能性がある。
【００６２】
一方、（〜）Ｆｉが非常に高い次元である場合、情報利得基準は、（〜）Ｆｉのあたりに大きな特徴グループを与え、したがって、道路調査映像における歩行者および車両の活動などの、個別によりよくモデル化されると思われる異なる事象ストリームを混合する。
【００６３】
階層的隠れマルコフモデル
好ましい実施形態は、映像１０１の構造について、２つのレベルの階層的隠れマルコフモデル（ＨＨＭＭ）２００を用いる。最上位レベルはマルコフ鎖を含み、最下位レベルは隠れマルコフモデルを含む。ＨＨＭＭモデルは、動的ベイズネットワーク（ＤＢＮ）の特別な場合である。モデルは、３以上のレベルに拡張されることができる。
【００６４】
このモデルにおいて、最上位レベルの構造要素は、映像の意味論的事象に対応し、一方、最下位レベルの状態は、同じ事象内で起こる可能性がある変動を表す。最下位レベルの状態は、観測、すなわち、ガウス混合(mixture-of-Gaussian)分布を用いて、生映像から行われた特徴の測定から作成される。しかし、特徴分布は必ずしも、ガウス混合分布に制約されなければならないわけではない。
【００６５】
図２は、階層的隠れマルコフモデル２００の木構造化表現を示し、図３は、最下位での観測Ｘｔを有する同じモデルについてのＤＢＮ表現を示す。ＨＨＭＭ２００は、階層的制御構造を有するＨＭＭの自然な一般化である。全てのより高いレベルの状態シンボルは、より低いレベルのサブＨＭＭによって作成されるシンボルのストリームに対応する。
【００６６】
高いレベルのモデルにおける遷移は、より低いレベルのモデルがエグジット（ｅまたはＥ）状態に入る時のみに呼び出される。エグジット状態は、高いレベルにおける遷移をオンする。観測は、最も低いレベルの状態において作成されるだけである。大文字の字体は、状態を、時刻ｔにおけるランダム変数として示し、小文字の字体は、ＨＭＭの状態−空間、すなわち、ランダム変数が任意の時間間隔においてとることができる値を示す。レベルｄにおける状態は、下位のレベルの既存の状態がオンである、すなわち、Ｅｄ＋１＝１でなければ、変わることが許されない。
【００６７】
このボトムアップの構造は、構造が、いくつかの他の階層的方式を特別な場合として含む点で一般的である。例が含むものは、全レベル的な(across-level)遷移が、より低いレベルのモデルの最初かまたは最後の状態において起こることができるだけである、ｌｅｆｔ−ｒｉｇｈｔＨＭＭの積重ね、および、より高いレベルにおいて同じ親状態に属するそれぞれの状態について、レベル遷移確率が同じであるボトムアップではなくトップダウンの制御構造を有するジャンプ・マルコフモデルの離散的同等物である。
【００６８】
ＨＨＭＭの従来の用途は、３つのクラス、すなわち管理学習、無管理学習、および両方の混合の中に入る。管理学習において、訓練データは、手動でセグメント化され、ラベル付けされる。したがって、それぞれのサブＨＭＭはセグメントについて個別に学習され、クロスレベル遷移は、セグメントにわたって遷移統計を用いて学習される。例は、ＤＮＡ配列における外含子(extron)／内含子(intron)の認識および作用認識を含む。無管理学習において、任意のレベルにおいてセグメント化されたデータは、訓練には利用できず、異なるレベルのパラメータが共同して学習される。上述の学習の混合において、サブモデル境界がある状態か、または、ない状態で、高いレベルにおける状態ラベルが与えられるが、パラメータはやはり、いくつかのレベルにわたって推定される必要がある。ここで、最も一般的な用途は、会話および筆跡認識である。
【００６９】
それぞれのレベルにおいてそれぞれのマルコフモデルによって生成される全ての考えられる長さのサブシーケンスをルーピングすることによって、マルチレベル隠れ状態インタフェースが行われることができる。しかし、このプロセスはとても最適とは言えない。簡単化のために、本発明者等は、隠れ状態インタフェースのための一般化前進後退プロセス、および前進後退反復に基づくパラメータ推定のための一般化ＥＭプロセスを好む。
【００７０】
ＥＭプロセスの目的は、正確なモデルパラメータを確立することである。本発明者等は、モデルの初期サイズが与えられ、モデルが、予め定義された特徴セットに対して学習されると仮定する。これらの２つの仮定は、本明細書で述べられる、適応モデル選択プロセスおよび適応特徴選択プロセスを用いて緩和される。
【００７１】
本発明者等は、任意のサブＨＭＭの最大状態−空間サイズをＮとして表す。本発明者等は、バー記号を用いて、Ｎアレイ、Ｄディジット整数（integer）を有し、最も低いレベル状態が最下位ディジットにある、最上位（レベル１）から最下位（レベルＤ）までの階層的状態の全構成を書く。
【００７２】
【数４】
2005196750.tif 000006
【００７３】
ここで、１≦ｑｉ≦Ｎ、ｉ＝１、…、Ｄである。本発明者等は、混乱がないところではｋの上付き添え字を省く。実質的にモデル２００を定義するＨＨＭＭのパラメータは、状態構成ｋ（ｄ−１）によって索引付けされるレベルｄにおけるマルコフ鎖パラメータλｄ、すなわち、遷移確率Ａｄｋ、従来確率πｄｋ、現在レベルからの既存の確率ｅｄｋを含み、出力パラメータＢは、状態構成について条件付けされた観測分布、すなわち、観測がガウス分布する時の平均μｋおよび共分散σｋを指定する。
【００７４】
【数５】
2005196750.tif 000007
【００７５】
期待値最大
現在のパラメータ集合はΘであり、提案されるか、または、更新されるパラメータ集合は（^）Θである。データ尤度Ｌを最大にすることは、完全データｌｏｇ尤度関数の期待値Ω（．，Θ）を反復して最大にすることと等価である。本発明者等は、記号（．）１：Ｔを用いて、長さＴの時間シーケンスの要素を書く。
【００７６】
【数６】
2005196750.tif 000008
【００７７】
一般的に言って、期待ステップは、現在のパラメータ集合に基づいて期待値を評価する。最大化ステップは、この期待値を最大にするパラメータ（^）Θを見つける。最大化ステップが閉じた形の解を有するように適正な隠れ状態空間を選択する時には、特別な配慮がなされなければならない。それは、未知数全てがｌｏｇ（・）内部にあるためである。完全データ確率が、未知パラメータ積の形をとるため、それぞれの未知数は、最大化において個別に解かれることができ、閉じた形の解が可能である。
【００７８】
ベイズ適応
ＥＭを用いると、ＥＭが山登りプロセスであるため、ＨＨＭＭのためのパラメータ学習は、データ尤度の局所的最大に収束する。尤度空間において大域的最大を探索することは難しい。さらに、データ尤度についてのこの最適化は、予め定義されたモデル構造に対して実行されるだけである。モデル構造の集合に対する比較および探索を可能にするために、本発明者等は、新しい最適性基準および代替の探索方策を必要とする。それは、全てのモデルトポロジーを尽くすことは、複雑さが超指数関数的であるからである。
【００７９】
本発明者等は、ランダム化した探索方策を用いて、全体のパラメータおよびモデル構造空間に関する、処理しにくさを有する探索問題に対処する。最適性基準は、最大尤度から最大事後確率に一般化される。そのため、本発明者等は、モデル構造にベイズ事前主観確率(prior belief)を組み込む。
【００８０】
具体的には、本発明者等は、マルコフ鎖モンテカルロ（ＭＣＭＣ）法を用いて、ベイズ情報基準（ＢＩＣ）１７０を最大にする。
【００８１】
本発明者等は、エントロピー事前確率を有する確定的パラメータトリミング・アルゴリズム（トリミングプロセスを通してモデル事前確率の単調増加を確保する）などの、構造を学習するための代替法が知られていることがわかっている。しかし、本発明者等は、そのトリミングプロセスを適用するために、十分に大きなモデルで始めなければならない。それは、計算の複雑さの目的にとって望ましくなく、本発明者等がモデルの複雑さの限界を前もって知らなければ、不可能であり、無管理設定においてはそうなるであろう。
【００８２】
ＭＣＭＣ
ＭＣＭＣは、高次元最適化問題を解くのに用いられることができる、或るクラスの方法である。一般に、ベイズ学習のためのＭＣＭＣは、２つのステップ間で反復される。提案ステップは、特徴の現在モデルおよび統計量によって決まる、或る提案分布からサンプリングされる、更新されたモデルを生成する。決定ステップは、モデル事後および提案方策を用いて、提案されたモデルの適合性に基づいて受容確率αを計算する。提案されたモデルは、確率αで受容されるか、または、拒絶される。
【００８３】
ＭＣＭＣは、一定の制約が提案分布について満足されると、確率の大域的最適に収束する。収束速度は、提案の「良さ」に大きく左右される。パラメータ学習に加えて、モデル選択もまた、異なる次元のパラメータ空間の間の可逆移動を構築することによる反転ジャンプＭＣＭＣ（ＲＪ−ＭＣＭＣ）を用いて同じフレームワーク内で対処されることができる。
【００８４】
本発明者等は、ＭＣＭＣ方式を用いて、ＨＨＭＭモデル２００の最適状態空間を学習する。本発明者等は、ＥＭおよびＭＣＭＣ手順の混合を用い、モデルパラメータはＥＭを用いて更新され、モデル構造の学習はＭＣＭＣを用いる。本発明者等は、パラメータ集合およびモデルの全部のモンテカルロ更新の代わりに、このハイブリッドプロセスを好む。それは、パラメータのＭＣＭＣ更新がＥＭよりずっと長い時間がかかるからである。ハイブリッド手法を用いると、収束は悪くならない。
【００８５】
ＨＨＭＭのためのＭＣＭＣ
本発明者等は、状態空間における、４つの一般的なタイプ「移動」を用いてＨＨＭＭを更新する。
【００８６】
ＥＭ移動は、状態空間のサイズを変えずにパラメータを更新する。
【００８７】
Ｓｐｌｉｔ（ｄ）移動は、状態をレベルｄにおいてスプリットする。これは、レベルｄにおける状態が２以上ある時に、ノードの直接の子供を２つの集合に無作為に分割することによって行われ、１つの集合は、その元の親ノードに割り当てられ、他の集合はレベルｄにおいて新しく生成された親の状態に割り当てられる。スプリットが、最も低いレベル、すなわち、ｄ＝Ｄで起こる時、本発明者等は、平均を摂動させることによって、元の観測確率のガウスカーネルをスプリットする。
【００８８】
Ｍｅｒｇｅ（ｄ）移動は、その子供を１つの集合に押し込め、レベルｄにおけるノードの数を１だけ減らすことによって、レベルｄにおける２つの状態を１にマージする。
【００８９】
Ｓｗａｐ（ｄ）移動は、レベルｄ−１における親ノードがもともと異なるレベルｄにおける２つの状態の親ノードをスワップする。この移動は、そのマルチレベル構造が、同じサイズの全体の状態−空間内で不均質であるため、ＨＨＭＭにとって必要である。
【００９０】
本発明者等は、これらの移動が、複数のスプリットおよびマージ移動で満たされるため、ａｄｄおよびｄｅｌｅｔｅ移動を持たない。
【００９１】
図４はモデル適応プロセスを示す。ステップ４１０にて、本発明者等は、現在のモデル２００を初期化する。付録で述べるように、反復ｉにおいて、現在モデルに基づいて、提案された確率プロファイルを確定する（４２０）。次に、タイプ｛ＥＭ、Ｓｐｌｉｔ（ｄ）、Ｍｅｒｇｅ（ｄ）、Ｓｗａｐ（ｄ）｜ｄ＝１、…、Ｄ｝の中から移動を提案する。
【００９２】
付録で述べるように、選択された状態およびその子供の状態に対する適切な作用によって、モデルおよびそのパラメータが更新される（４３０）。受容比ｒｉは、異なるタイプの移動について評価される（４４０）。付録を参照されたい。この比は、ＢＩＣについて確定されたモデルの事後確率、および、本発明者等がその間の比を評価する空間は、等しくないサイズであることを補償するアライメント項を考慮する。本発明者等は、受容確率をαｉ＝ｍｉｎ｛１、ｒｉ｝と表す。次に、本発明者等は、μ〜Ｕ（０，１）をサンプリングし、μ≦αｉであれば、移動を受容し、そうでければ排除する。モデルおよびパラメータが収束する場合、終了し（４５０）、そうでなければステップ４２０にて反復する。
【００９３】
ＢＩＣは事後モデル適合性の尺度である。ＢＩＣは、提案された移動が受容されるかどうかを確定する主要な因子である。
【００９４】
【数７】
2005196750.tif 000009
【００９５】
直観的に、ＢＩＣは、重み付け係数λを用いた、データ尤度Ｐ（Ｘ｜Θ）とモデルの複雑さ｜Θ｜・ｌｏｇ（Ｔ）の間の兼ね合いである。モデルの自由なパラメータの数は、より大きなモデルにペナルティを課す。モデルペナルティの影響は、ｌｏｇ（Ｔ）が比較的ゆっくり増えるため、訓練データＴの量が増えるにつれて減る。本発明者等は、重み係数λを１／１６として実験的に選択する。こうして、データ尤度およびモデル事前確率の変化は、１つの反復にわたって数値的に同程度になる。
【００９６】
用途
本発明者等による方法は、サッカーおよび野球映像において、目立った事象を見つけ、モデル構造を学習し、情報の特徴集合を特定することが自動的にできる。スポーツビデオは、本発明について、興味深い領域を表す。２つの主要な因子が、ビデオ領域および統計的技法におけるこの一致に寄与する。１つのスポーツ領域における全く異なる意味の集合は、音声−視覚特徴と強い相関を示す。ゲームおよびスポーツ映像における作成構文の、十分に確立されたルールは、強い時間的遷移制約を提供する。たとえば、サッカー映像において、プレーおよびブレークは、映像データの全時間軸をカバーする再帰事象である。野球映像において、ピッチング、バッティング、ランニングなどの知覚的に独特の異なる中間レベル事象の間での遷移は、ゲームの意味を示す。
【００９７】
サッカー映像の場合、サッカーゲームのルールに従って規定される、２つの意味論的事象、すなわちプレーおよびブレークをモデル化する構造を発見することが望ましい。これらの２つの事象は、２つの事象が映像の全体の時間スケールをカバーするため密であり、ブレークをプレーから区別することは、ブレークが映像の約４０％を占めるため、効率的なブラウジングおよび要約に役立ち、観察者は、中間のブレーク全てをスキップしながら、プレーごとにゲームを通してブラウジングするか、または、プレーヤの反応またはゲームのアナウンスを見つけるために、ブレークセグメントを無作為にアクセスする場合がある。
【００９８】
野球映像の場合、学習は、グランドトゥルース(ground truth)をラベル付けされずに、または、事前に特徴を手動で特定されずに行われる。これが、未知の領域に対する構造発見の用途であり、結果の評価および解釈は、自動発見法が適用された後に行われる。
【００９９】
試験結果が示すところでは、本発明者等の無管理学習法は、管理学習と同程度になり、よりよい精度、たとえば、無管理について７５．２％〜７５．７％、対、管理について７５．０％を達成することが時々ある。ＨＨＭＭの無管理学習が特定のグランドトゥルースに対して調整されていないため、このことは全く驚くべきことである。試験結果は、１．１％〜１．２％の低い四分領域(semi-interquartile range)によって示されるように整合性を維持する。
【０１００】
全モデル適応を有するＨＨＭＭの場合、方法は、２〜４の高レベル状態に収束し、評価は、それぞれの得られるクラスタを、対応する大部分のグランドトゥルースラベルに割り当てることによって行われる。
【０１０１】
モデルパラメータおよび構造学習法の良好な性能に基づいて、それぞれの残りの特徴について反復してラップアラウンドし、フィルタリングする、自動特徴選択法の性能が試験された。０．１秒ごとにサンプリングされた９次元特徴ベクトルは、初期特徴プール４０１を満たす。特徴ベクトルは、
支配的な色比（ＤＣＲ）、
動き強度（ＭＩ）、
カメラ平行移動の最小２乗推定（ＭＸ、ＭＹ）、
音声ボリューム、
スペクトルロールオフ（ＳＲ）、
低帯域エネルギー（ＬＥ）、
高帯域エネルギー（ＨＥ）、および
ゼロ交差レート（ＺＣＲ）を含む。
【０１０２】
１つのサッカー映像および選択された特徴集合｛ＤＣＲ、Ｖｏｌｕｍｅ｝の場合、モデルは、ＨＨＭＭにおける２つの高レベル状態に収束し、それぞれが、５つのより低いレベルの子供状態を有する。プレー／ブレークラベルに対する評価は、７４．８％の精度を示す。別のサッカー映像および選択された特徴集合｛ＤＣＲ、ＭＸ｝の場合、３つの高レベル状態および｛７，３，４｝子供状態が作成される。ＭＸは、サッカー映像における全体の動き強度に寄与する最も支配的な因子である水平カメラパニングの動きを近似する特徴である。それは、カメラが広角ショットでボールの移動を追跡する必要があり、広角ショットは、ゲームの全体の状態を見せる１つの主要なタイプのショットであるためである。
【０１０３】
発明の効果
本発明は、無管理で映像の構造を学習する方法を提供する。本発明者等は、階層的隠れマルコフモデルを用いて、密で、確率的な或るクラスの映像の構造をモデル化する。モデルパラメータおよびモデル構造は、ＥＭおよびモンテカルロサンプリング技法を用いて学習される。情報の特徴部分集合は、反復フィルタ−ラッパプロセスを用いて、大きな特徴プールから自動的に選択される。サッカー映像に関して評価されると、本発明は、管理学習法と同じ程度の結果を達成する。野球映像に関して評価されると、方法は、野球ゲームの状態が、視覚情報のみから推論されることができるという本発明者等の直感と一致する、２つの視覚特徴を自動的に選択する。
【０１０４】
本発明の精神および範囲内で、種々の他の適応および変更を行ってもよいことが理解されるべきである。したがって、添付の特許請求の範囲の目的は、本発明の真の精神および範囲に入る、全てのこうした変形形態および変更形態を包含することである。
【０１０５】
付録
モデル適応のための提案確率
【０１０６】
【数８】
2005196750.tif 000010
【０１０７】
ここで、ｃ＊はシミュレーションパラメータであり、ｋは現在の状態数である。パラメータρは、状態数の打ち切りポアソン事前確率のためのハイパーパラメータである。すなわち、ρは、最大状態サイズが＋∞であることを許される場合、状態数の期待平均値であり、ｃ＊に乗ずるスケーリング係数は、得られる状態−空間サイズｋ±１およびρを用いて確率を調整する。
【０１０８】
ＲＪ−ＭＣＭＣにおいて異なる移動を確定すること
期待値最大（ＥＭ）は、正規の１つの山登り反復である。ＥＭ以外の移動タイプが選択された後、一定のレベルにおける１つまたは２つの状態は、スワップ／スプリット／マージのために無作為に選択され、パラメータは、それに従って修正される。
【０１０９】
２つの状態の結合をスワップする：同じレベルから２つの状態（２つの状態のそれぞれは、異なる高レベル状態に属する）を選択する。２つの状態の高レベル結合をスワップする。
【０１１０】
状態をスプリットする：状態を無作為に選択する。スプリット方策は、この状態が階層の異なる位置にある時異なる。これが、最も低いレベル（ｄ＝Ｄ）にある状態である場合、以下のように、その結合したガウス観測分布の平均を摂動させる。
【０１１１】
【数９】
2005196750.tif 000011
【０１１２】
ここで、μｓ〜Ｕ［０，１］であり、ηは、スプリット移動とマージ移動の間の可逆性を確保するシミュレーションパラメータである。これが、２以上の子供の状態を有する、ｄ＝１、…、Ｄ−１における状態である時、その子供を２つの互いに共通元を持たない集合に無作為にスプリットし、選択された状態と同じ親に結合する、レベルｄにおける新しい兄弟状態を生成する。それに従って、対応するマルチレベルマルコフ鎖パラメータを更新する。
【０１１３】
２つの状態をマージする：レベルｄにおける２つの兄弟状態を選択し、元のＨＨＭＭにおいて、どのレベルに位置するかに応じて、これらの２つの状態の観測確率すなわち対応する子供−ＨＨＭＭをマージする。ｄ＝Ｄである時、２つの平均として新しい平均を作成することによってガウス観測確率をマージする。
【０１１４】
【数１０】
2005196750.tif 000012
【０１１５】
ｄ＝１、…、Ｄ−１である時、これらの２つの状態の子供の全てをマージされた状態の子供にすることによって２つの状態をマージし、それに従って、マルチレベル遷移確率を修正する。
【０１１６】
ＲＪ−ＭＣＭＣにおける異なる移動についての受容比
Ｓｗａｐについての受容比は、空間次元が変わらないため事後比に単純化される。Θを古いモデルとして、（∧）Θを新しいモデルとして表す。
【０１１７】
【数１１】
2005196750.tif 000013
【０１１８】
移動が、スプリットまたはマージなどの、異なる次元を有するパラメータ空間に対して提案される時、本発明者等は、受容比を評価する時に２つの追加の項を必要とするであろう。提案比の項は、詳細な平衡を確保するために、現在の提案が実際に達する確率を補償し、ヤコビの項は２つの空間を整列するのに用いられる。
【０１１９】
ここで、ｐｓｐ（ｋ）およびｐｍｓ（ｋ）は提案確率と言い（上記を参照されたい）、スプリットまたはマージ移動が、レベルにわたる任意の変化を伴わないため、余分の変数ｄは省略される。
【図面の簡単な説明】
【０１２０】
【図１】本発明による無管理学習法の流れ図である。
【図２】本発明に従って、映像構造をモデル化するのに用いられる階層的隠れマルコフモデルの図である。
【図３】図２のモデルを表す動的ベイズネットワークの図である。
【図４】本発明によるモデル適応手順の流れ図である。
【図１】
2005196750.tif 000014
【図２】
2005196750.tif 000015
【図３】
2005196750.tif 000016
【図４】
2005196750.tif 000017
【外国語明細書】
2005196750.tif 000018
2005196750.tif 000019
2005196750.tif 000020
2005196750.tif 000021
2005196750.tif 000022
2005196750.tif 000023
2005196750.tif 000024
2005196750.tif 000025
2005196750.tif 000026
2005196750.tif 000027
2005196750.tif 000028
2005196750.tif 000029
2005196750.tif 000030
2005196750.tif 000031
2005196750.tif 000032
2005196750.tif 000033
2005196750.tif 000034
2005196750.tif 000035
2005196750.tif 000036
2005196750.tif 000037
2005196750.tif 000038
2005196750.tif 000039
2005196750.tif 000040
2005196750.tif 000041
2005196750.tif 000042
2005196750.tif 000043
2005196750.tif 000044
2005196750.tif 000045
2005196750.tif 000046
2005196750.tif 000047
2005196750.tif 000048
2005196750.tif 000049
2005196750.tif 000050
2005196750.tif 000051
2005196750.tif 000052