(57)【要約】【課題】マルチメディアから１つまたは複数の概念を自動的に検出する。【解決手段】１つまたは複数の概念を表す低レベル特徴が抽出される（３１０）。これらの低レベル特徴を使用して分類識別器が訓練される（３４０）。集合注釈付けモデルは、該分類識別器に基づいて構築される（３８０）。フレームワークは完全に包括的であり、任意の数の低レベル特徴または分類識別器と適用できる。さらに、解析は領域に特殊な仮定を行わず、変型なしで活動分析または他のシナリオに適用できる。該フレームワークは幅広いクラスのポテンシャル関数の包含を認め、したがってマルチモーダル解析及び異種情報源の融合を可能にする。【選択図】図３
2008123486.tif 000002
【特許請求の範囲】
【請求項１】
マルチメディアで１つまたは複数の概念を検出するための方法であって、
（ａ）前記１つまたは複数の概念を表す低レベル特徴を抽出し、
（ｂ）前記低レベル特徴の集合を使用して、概念ごとに分類識別器を訓練し、
（ｃ）前記分類識別器のそれぞれを結合する集合注釈モデルを構築し、
（ｄ）関連する概念の間で相互依存をモデル化するために１つまたは複数の相互作用ポテンシャルを定義し、
（ｅ）前記集合注釈モデル及び前記定義された相互作用ポテンシャルに基づいて１つまたは複数の概念の存在又は不在を検出する方法。
【請求項２】
前記マルチメディアが１つまたは複数のデジタルビデオフレームを含む請求項１に記載の方法。
【請求項３】
前記マルチメディアが、位置合わせされたデジタルテキスト、タグ情報、テキスト複写、及びウェブページリンクを有する群より選択される１つまたは複数の形式のデータをさらに含む請求項２に記載の方法。
【請求項４】
低レベル特徴の前記集合が、色ヒストグラム、テクスチャ特徴、エッジ特徴、運動解析、顔検出、及び位置合わせされたテキストデータを有する群より選択される請求項１に記載の方法。
【請求項５】
前記分類識別器がサポートベクターマシンである請求項１に記載の方法。
【請求項６】
前記サポートベクターマシンの前記出力が論理マッピングを使用して確率に変換される請求項５に記載の方法。
【請求項７】
集合注釈モデルが、分類確率場（ＤＲＦ）モデル、条件付確率場（ＣＭＵ）モデル、分類出力独立概念検出（ＳＶＭ）モデル、概念間共起性（ＣＭＬ＋Ｉ）モデル、及び概念特徴共起性（ＣＭＬＴ＋Ｉ）モデルを有する群より選択される請求項１に記載の方法。
【請求項８】
前記定義された相互作用ポテンシャルが概念Ｙi，Ｙjの各組の関数である請求項１に記載の方法。
【請求項９】
前記定義された相互作用ポテンシャルが４つすべてが２つからなる組み合わせを識別する請求項８に記載の方法。
【請求項１０】
前記定義された相互作用ポテンシャルが、概念Ｙi，Ｙjの各組と低レベル特徴データの関数である請求項１に記載の方法。
【請求項１１】
分類識別器が単一概念に適用し、分類識別器の集合が概念の集合に適用する請求項１に記載の方法。
【請求項１２】
分類識別器の前記集合が集合マルチメディア注釈付けの枠内で積分される請求項１１に記載の方法。
【請求項１３】
さらに、前記特定された概念と関連付けられる信頼基準と順序付けの１つまたは両方を供給する請求項１に記載の方法。
【請求項１４】
前記信頼基準と前記順位付けの１つまたは両方が経時的に変化することがある請求項１３に記載の方法。
【請求項１５】
前記信頼基準と前記順序付けの１つまたは両方が、順序付けられたリストの形式でユーザに注釈を勧めるために使用できる請求項１３に記載の方法。
【請求項１６】
さらに、概念の検出を改善するために、事前に訓練された概念検出器を利用する請求項１に記載の方法。
【請求項１７】
さらに、概念の検出を改善するために近似的推論計画を利用する請求項１に記載の方法。
【請求項１８】
前記訓練中に前記低レベル特徴の量子化をさらに備える請求項１に記載の方法。
【請求項１９】
デジタルメディアで１つまたは複数の概念を特定するシステムであって、
１つまたは複数の概念を表す低レベル特徴を抽出するための第１の処理手段と、
前記低レベル特徴の集合を使用して概念ごとに分類識別器を訓練するための第２の処理手段と、
前記分類識別器のそれぞれに基づいて集合注釈付けモデルを構築できる第３の処理手段と、
関係する概念を特定するための１つまたは複数の相互作用ポテンシャルと、
前記集合注釈モデル及び前記定義された相互作用ポテンシャルに基づいて１つまたは複数の概念を特定できる第４の処理手段と、
を備えるシステム。
【請求項２０】
コンピュータに、
１つまたは複数の構成要素を表す低レベル特徴を抽出させ、
前記低レベルの特徴を使用して概念ごとに分類識別器を訓練させ、
前記分類識別器のそれぞれに基づいて集合注釈モデルを構築させ、
関係する概念を特定するために１つまたは複数の相互作用ポテンシャルを定義させ、
前記集合注釈付けモデル及び前記定義された相互作用ポテンシャルに基づいて１つまたは複数の概念を特定させる
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルメディアの自動注釈付けのための方法に関する。すなわち、本発明は、デジタルメディアで１つまたは複数の概念を検出する方法、システム及びプログラムに関する。
【背景技術】
【０００２】
多くの現代のマルチメディア分析研究がビデオコンテンツのための情報検索に重点的に取り組んでいる。Ｙａｈｏｏ！（登録商標）及びＧｏｏｇｌｅ（登録商標）等の企業は自社のテキストベースのサーチ機能をビデオデータに拡張している。コンテキスト索引付けのためのこれらのシステムの適用性は、多くの場合使用可能な時間で整列されているテキストを含むビデオに制限されているか、あるいはリンク構造及びビデオを含んだウェブページのテキストに依存している。ビデオ検索は、大きな成功を収めているＴＲＥＣＶＩＤワークショップ（非特許文献１参照。）の焦点でもあった。ＴＲＥＣＶＩＤ評価では、視覚情報の使用が強調されているが、テキスト記述子がない場合に視覚データから意味論を抽出することが大きな未決の問題のままである。
【０００３】
この意味上のギャップに対処するための最近の研究は意味素性抽出に対するオントロジーベースの手法に集中していた（非特許文献２及び３参照。）。オントロジーベースの手法では、バイナリ識別器の「基本」セットが、ビデオショットが特定の意味素性を示しているかどうかを判断するために構築される。これらの分類出力は、より高水準の分析を提供し、索引付け及び検索を強化するために統計的に結合される。これらの手法の多くは初期セグメンテーションに続いてショットレベルで作用する。これは、計算上の効率、フレームの局所的なセットの動的な分析、及び何らかの一時的な持続時間を示す意味素性の抽出のために望ましい。
【０００４】
現在、マニュアルタグが、Ｆｌｉｃｋｒ及びＹｏｕ  Ｔｕｂｅ等の多様な共用ビデオサイトと画像データサイトで激増している。この情報は精緻化及び訓練の自動システム用を含む、ビデオ索引付けにとってはきわめて貴重であるが、それはまた多くの欠点も示している。例えば、非常に長いビデオは該ビデオの（特定されていない場合もある）小さな部分だけに適用するタグを有することがある。また、テキストカテゴリ化の関連で説明される多義性と同義性の昔ながらの問題はマルチメディアカテゴリ化用の凝集タグデータで継承されている（非特許文献４）。
【非特許文献１】Ｐ．Ｏｖｅｒ、Ｔ．Ｉａｎｅｖａ、Ｗ．Ｋｒａａｉｊ、Ａ．Ｓｍｅａｔｏｎ、ＴＲＥＣＶＩＤ２００５、「概要（Ｏｖｅｒｖｉｅｗ）」、ＴＲＥＣＶＩＤ会議録２００５年（Ｐｒｏｃ．ＴＲＥＣＶＩＤ  ２００５）、ｈｔｔｐ：／／ｗｗｗ−ｎｌｐｉｒ．ｎｉｓｔ．ｇｏｖ／ｐｒｏｊｅｃｔｓ／ｔｖｐｕｂｓ／ｔｖ５．ｐａｐｅｒｓ／ｔｖ５ｏｖｅｒｖｉｅｗ．ｐｄｆ、前回アクセス２００７年５月２５日
【非特許文献２】Ａ．Ｈａｕｐｔｍａｎｎ、画像及びビデオ検索に関する第三回会議の議事録（Ｐｒｏｃ．Ｏｆ  ｔｈｅ  Ｔｈｉｒｄ  Ｃｏｎｆ．ｏｎ  Ｉｍａｇｅ  ａｎｄ  Ｖｉｄｅｏ  Ｒｅｔｒｉｅｖａｌ）の中の放送ビデオのための大規模概念オントロジーに向かって（Ｔｏｗａｒｄｓ  ａ  ｌａｒｇｅ  ｓｃａｌｅ  ｃｏｎｃｅｐｔ  ｏｎｔｏｌｏｇｙ  ｆｏｒ  ｂｒｏａｄｃａｓｔ  ｖｉｄｅｏ）、コンピュータ科学における講義ノートシリーズ、第３１１５巻、Ｓｐｒｉｎｇｅｒ、６７４〜６７５ページ、２００４年
【非特許文献３】Ｌ．Ｈｏｌｌｉｎｋ、Ｍ．Ｗｏｒｒｉｎｇ及びＧ．Ｓｃｈｒｅｉｂｅｒ、マルチメディア’０５でのビデオ検索のための視覚オントロジーの構築：マルチメディアに関する第１３回年次ＡＣＭ国際会議の会議録（Ｂｕｉｌｄｉｎｇ  ａ  ｖｉｓｕａｌ  ｏｎｔｏｌｏｇｙ  ｆｏｒ  ｖｉｄｅｏ  ｒｅｔｒｉｅｖａｌ  ｉｎ  ＭＵＬＴＩＭＥＤＩＡ  ’０５：Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １３ｔｈ  ａｎｎｕａｌ  ＡＣＭ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ）、ＡＣＭ出版社（ＡＣＭ  Ｐｒｅｓｓ）、２００５年
【非特許文献４】Ｍ．Ｗ．Ｂｅｒｒｙ、Ｓ．Ｔ．Ｄｕｍａｉｓ及びＧ．Ｗ．Ｏ’Ｂｒｉｅｎ、「インテリジェント情報検索のための線形台数の使用（Ｕｓｉｎｇ  ｌｉｎｅａｒ  ａｌｇｅｂｒａ  ｆｏｒ  ｉｎｔｅｌｌｉｇｅｎｔ  ｉｎｆｏｒｍａｔｉｏｎ  ｒｅｔｒｉｅｖａｌ）」、ＳＩＡＭレビュー（ＳＩＡＭ  Ｒｅｖｉｅｗ）３７（４）：５７３−５９５、１９９５年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
目標は、単一のキーフレーム、またはフレームの集合の分析を介してビデオのクリップにおける意味論的な属性つまり概念を検出することである。提案されている方法は、集合的な複数の概念検出のための確率場モデルでの高性能分類単一概念検出器を統合する。さらに、包括的なフレームワークが、意味概念間の任意の複雑な依存性を捕捉できる意味媒体分類のために提供される。
【０００６】
本明細書に説明されているシステムはビデオフレームで試験されているが、システムは他のタイプのマルチメディアコンテンツに幅広く適用できる。
【０００７】
本発明の実施形態では、概念を特定するための半自動的なインタフェースが可能にされる。例えば、写真またはビデオの集合体を考慮する場合、本発明はユーザがその中から選択する順位リストとしての概念の集合を勧めることができる。該リストは他のユーザのタグ、またはタグ付きデータの既存の集合から生じることがあるであろう。凝集タグ（ａｇｇｒｅｇａｔｉｎｇ  ｔａｇ）付きデータ（例えば、Ｆｌｉｃｋｅｒ）では、本発明は類似するタグをクラスタ化するのに役立つ、あるいはタグのあいまいさ（例えば、多義性）を解決するのに役立つことがある。
【課題を解決するための手段】
【０００８】
ここで対処される問題は、バイナリ属性の集合を使用してセグメント化されたビデオの自動注釈付けである。これらの属性は概念と呼ばれ、さらに一般的な問題は概念保護と呼ばれている。システムは概念相互依存性を利用することにより概念の集合の存在／不在を検出できる。
【０００９】
本発明の実施形態では、デジタルマルチメディアにおける概念を特定する方法は、概念ごとに分類識別器を訓練するために使用される該１つまたは複数の概念を表現する低レベルの特徴を抽出することを含み、該分類識別器は、集合注釈付けモデルを構築するために結合される。さらに、相互作用ポテンシャルの集合が、該マルチメディアでの関連する概念を特定するために定められる。集合注釈付けモデル及び相互作用ポテンシャルを使用して、該概念を特定できる。
【００１０】
すなわち、本発明の第１の態様は、マルチメディアで１つまたは複数の概念を検出するための方法であって、（ａ）前記１つまたは複数の概念を表す低レベル特徴を抽出し、（ｂ）前記低レベル特徴の集合を使用して、概念ごとに分類識別器を訓練し、（ｃ）前記分類識別器のそれぞれを結合する集合注釈モデルを構築し、（ｄ）関連する概念の間で相互依存をモデル化するために１つまたは複数の相互作用ポテンシャルを定義し、（ｅ）前記集合注釈モデル及び前記定義された相互作用ポテンシャルに基づいて１つまたは複数の概念の存在又は不在を検出する方法である。
【００１１】
本発明の第２の態様は、デジタルメディアで１つまたは複数の概念を特定するシステムであって、１つまたは複数の概念を表す低レベル特徴を抽出するための第１の処理手段と、前記低レベル特徴の集合を使用して概念ごとに分類識別器を訓練するための第２の処理手段と、前記分類識別器のそれぞれに基づいて集合注釈付けモデルを構築できる第３の処理手段と、関係する概念を特定するための１つまたは複数の相互作用ポテンシャルと、前記集合注釈モデル及び前記定義された相互作用ポテンシャルに基づいて１つまたは複数の概念を特定できる第４の処理手段と、を備えるシステムである。
【００１２】
本発明の第３の態様は、コンピュータに、１つまたは複数の構成要素を表す低レベル特徴を抽出させ、前記低レベルの特徴を使用して概念ごとに分類識別器を訓練させ、前記分類識別器のそれぞれに基づいて集合注釈モデルを構築させ、関係する概念を特定するために１つまたは複数の相互作用ポテンシャルを定義させ、前記集合注釈付けモデル及び前記定義された相互作用ポテンシャルに基づいて１つまたは複数の概念を特定させるプログラムである。
【００１３】
本発明の代替の、及び追加の特徴及び態様は、明細書、図及び請求項を検討することから得ることができる。
【発明の効果】
【００１４】
本発明は、マルチメディアから１つまたは複数の概念を自動的に検出することができる。
【発明を実施するための最良の形態】
【００１５】
本発明の好適な実施形態は、以下の図に基づいて詳細に説明される。
【００１６】
本発明は、入力手段、出力手段、プロセッサ、記憶手段を有するコンピュータに適用される。すなわち、このコンピュータを使用することによって、本発明の方法が実施される。
【００１７】
索引付けまたはメターデータの作成のために一貫した信頼できる注釈付けを提供するために、半自動の手法が必要とされる。手動の注釈付けは、量が絶えず増え続ける新規に生成されるコンテンツは言うまでもなく、レガシーアセットの規模では実行不可能である。計測可能な自動技法はデータの量には対処できるが、自動注釈付けの品質は十分ではない。以下に示す理想的な媒体注釈付けシステムの解析構成要素には複数の要件を特定できる。
【００１８】
−共通フレームワークにおいて異種モダリティを統合する能力
−注釈付けと関連付けられ、時間変化することがある信頼基準または順位付けを供給する能力
−アーカイブデータ、あるいはタグ情報、テキスト複写、またはウェブページリンク構造が不在であるデータのどちらかに注釈を付けるための完全自動モード
−信頼基準を活用して、必要に応じて自動的な結果を手動で改訂するための半自動モード
−ラベル順位付け及び共起性を活用して、異なるユーザによる類似した概念を示すために使用されるタグを調整またはクラスタ化する能力
定義
「タグ」つまり「注釈」は、本発明の実施形態とともに生成されないが、手動で、または別の方法でマルチメディアデータと関連付けられるテキストを説明するために使用される。しかしながら、タグつまり注釈は本発明の実施形態と統合、あるいは分類し直されてよい。
【００１９】
「概念」は、本発明の実施形態で半自動的にまたは自動的に生成されるマルチメディアデータと関連付けられたテキストを説明するために使用される。
【００２０】
「信頼基準」は、モデルによって指定されるような概念に遭遇する確率から導き出される。
【００２１】
「順位付け」は該信頼基準から導き出される。
【００２２】
２．１特徴抽出
第１の処理ステップでは、低レベルの特徴データを抽出できる。本発明者らのケースでは、ソースビデオはショットに従ってセグメント化され、キーフレームは各ショットの中で特定される。該キーフレームは低レベルの特徴データを抽出するために処理される。このデータは色ヒストグラム、テクスチャ特徴またはエッジ特徴、運動解析または顔検出出力等の視覚的な特徴を含んでよい。時間で整列されているテキストデータが存在する場合、ワードカウントまたはｔｆ／ｉｄｆ特徴等の標準的な低レベルテキスト特徴も含むことができる。使用される特徴の特定の集合は重要ではない。マルチモダリティのケースでは、単一の概念識別器を構築するために早期または後期の融合手法を使用できる（Ｃ．Ｓｎｏｅｋ、Ｍ．Ｗｏｒｒｉｎｇ、及びＡ．Ｗ．Ｓｍｅｕｌｄｅｒ、意味論的なビデオ解析における早期融合対後期融合、マルチメディアに関する第１３回年次ＡＣＭ国際会議の会議録（Ｅａｒｌｙ  ｖｅｒｓｕｓ  ｌａｔｅ  ｆｕｓｉｏｎ  ｉｎ  ｓｅｍａｎｔｉｃ  ｖｉｄｅｏ  ａｎａｌｙｓｉｓ．Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １３ｔｈ  Ａｎｎｕａｌ  ＡＣＭ  ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ）、ＡＣＭ出版社（ＡＣＭ  Ｐｒｅｓｓ）、ニューヨーク、ＮＹ、３９９−４０２、２００５年）。
【００２３】
２．２  独立概念検出
第２のステップでは、分類識別器（ｄｉｓｃｒｉｍｉｎａｔｉｖｅ  ｃｌａｓｓｉｆｉｅｒ）が低レベルの特徴のラベルが付けられた訓練セットを使用して概念ごとに訓練される。しばらくの間、サポートベクターマシン（ＳＶＭ）が好ましい識別器であった。各ＳＶＭの出力は論理マッピングを使用する確率に変換され、これが独立概念検出のためのベースラインシステムになる。
【００２４】
以下の実験では、公に入手可能な低レベル特徴（Ｊ．ｖａｎ  Ｇｅｍｅｒｔ、Ｊ．−Ｍ．Ｇｅｕｓｅｂｒｏｅｋ、Ｃ．Ｖｅｅｎｍａｍ、Ｃ．Ｓｎｏｅｋ、及びＡ．Ｓｍｅｕｌｄｅｒｓ、コンテキスト内の画像統計を学習することによるロバストな場面分類化（Ｒｏｂｕｓｔ  Ｓｃｅｎｅ  Ｃａｔｅｇｏｒｉｚａｔｉｏｎ  ｂｙ  Ｌｅａｒｎｉｎｇ  Ｉｍａｇｅ  Ｓｔａｔｉｓｔｉｃｓ  ｉｎ  Ｃｏｎｔｅｘｔを参照すること。ＩＥＥＥ  ＣＶＰＲ、２００６年の会議録に掲載される。）及びメディアミル（Ｍｅｄｉａ  Ｍｉｌｌ）チームによって提供されるＳＶＭ出力が活用される（Ｃ．Ｓｎｏｅｋ、Ｍ．Ｗｏｒｒｉｎｇ、Ｊ．Ｖａｎ  Ｇｅｒｍｅｒｔ、Ｊ．−Ｍ．Ｇｅｕｓｅｂｒｏｅｋ、及びＡ．Ｓｍｅｕｌｄｅｒｓ、「マルチメディアにおける１０１の意味概念の自動検出のための課題（Ｔｈｅ  Ｃｈａｌｌｅｎｇｅ  Ｐｒｏｂｌｅｍ  ｆｏｒ  Ａｕｔｏｍａｔｅｄ  Ｄｅｔｅｃｔｉｏｎ  ｏｆ  １０１  Ｓｅｍａｎｔｉｃ  Ｃｏｎｃｅｐｔｓ  ｉｎ  Ｍｕｌｔｉｍｅｄｉａ）、ＡＣＭマルチメディア、２００６年の会議録（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ，２００６）。これらのＳＶＭ出力は、概念単位での分類パラメータに対する計算上集約的なグリッドサーチを使用して高度に最適化されている。このようにして、これらの出力は以下の実験での２００５年の評価で提出された本発明者らのシステムのすべてより性能が優れていた、きわめて競争力のあるベースラインシステムを表す。
【００２５】
この手法に対応するグラフィックモデルは図１に表示されている。本明細書に提示されている集合注釈付け方法に対応するグラフィックモデルは図２に表現されている。確率論的には、概念集合Ｃの中のｉ番目の概念がバイナリ確率変数Ｙiによって示される場合には、式（１）となる。
【００２６】
【数１】
2008123486.tif 000003
【００２７】
２．３  モデリング概念の共起性
集合注釈付けモデルは、前項に説明された単一概念分類モデルに基づくことができる。本発明者らの第１の手法はＫｕｍａｒ及びＨｅｂｅｒｔの分類確率場（ＤＲＦ）モデルを拡張する（Ｓ．Ｋｕｍａｒ及びＭ．Ｈｅｂｅｒｔ。なお、ここで使用される用語「に基づく」は、他に特に規定がなければ、「に少なくとも一部基づいて」を意味する。空間依存性を自然画像でモデル化するための分類場（Ｄｉｓｃｒｉｍｉｎａｔｉｖｅ  Ｆｉｅｌｄｓ  ｆｏｒ  Ｍｏｄｅｌｉｎｇ  Ｓｐａｔｉａｌ  Ｄｅｐｅｎｄｅｎｃｉｅｓ  ｉｎ  Ｎａｔｕｒａｌ  Ｉｍａｇｅｓ）。神経情報処理システムの進展（Ａｄｖａｎｃｅｓ  ｉｎ  Ｎｅｕｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍｓ、ＮＩＰＳ  １６、２００４年）。このモデルは分類単一概念識別器を文脈情報を表す対付加概念共起性特徴と結合する。彼らの研究において、目標は、画像内のピクセルブロックのバイナリ分類を、「自然」または「人工」のどちらかとして実行することである。ブロックごとの分類の場合、彼らはロジスティック回帰を使用する。確率場は、空間依存性を有する。さらに具体的には、彼らは、低レベル画像データＸに対するバイナリラベルＹの（集合）ベクトルの確率を以下のようにモデル化する。
【００２８】
【数２】
2008123486.tif 000004
【００２９】
用語Ａiは、集合Ｓの中の空間的位置ｉのための局所的な分類識別器である連関ポテンシャル（ａｓｓｏｃｉａｔｉｏｎ ｐｏｔｅｎｔｉａｌ）（単項式ポテンシャル（ｕｎｉｔａｒｙ ａｓｓｏｃｉａｔｉｏｎ）またはノードポテンシャル（ｎｏｄｅ ｐｏｔｅｎｔｉａｌ））である。Ｉijは空間的位置ｉ、ｊの間の相互作用を表す用語である。Ｎiはグラフ内のノードｉの近傍の集合である。
【００３０】
この手法は、集合的な意味概念検出に適応できる。静止画像内の隣接する空間的位置を集合的に分類するよりむしろ、ビデオクリップの中の関連する意味概念を集合的に検出できる。具体的には、概念ごとに無関係に訓練されるＳＶＭ識別器は、式（２）の連関項のために使用できる。各ＳＶＭ出力は、対応する確率ＰD（Ｙｉ＝１｜Ｘ）にマップできる（大きなマージンの識別器における進展（Ａｄａｎｃｅｓ  ｉｎ  Ｌａｒｇｅ  Ｍａｒｇｉｎ  Ｃｌａｓｓｉｆｉｅｒｓ）、Ａ．Ｓｍｏｌａ、Ｐ．Ｂａｒｔｌｅｔｔ、Ｂ．Ｓｃｈｏｌｋｏｐｆ、Ｄ．Ｓｃｈｕｕｒｍａｎｓ、編集者、ＭＩＴ出版社（ＭＩＴ  Ｐｒｅｓｓｓ）、１９９９年の中のＪ．Ｐｌａｔｔ、「サポートベクターマシンのための確率論的な出力及び正規化尤度方法に対する比較（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｏｕｔｐｕｔｓ  ｆｏｒ  Ｓｕｐｐｏｒｔ  Ｖｅｃｔｏｒ  Ｍａｃｈｉｎｅｓ  ａｎｄ  Ｃｏｍｐａｒｉｓｉｏｎｓ  ｔｏ  Ｒｅｇｕｌａｒｉｚｅｄ  Ｌｉｋｅｌｉｈｏｏｄ  Ｍｅｔｈｏｄｓ）」を参照）。下付き文字Ｄは、以下に提示される集合モデルと対照的にこの確率を単一概念識別器と結び付けるために使用できる。概念Ｙiの連関の項は式（３）に従って設定できる。
【００３１】
【数３】
2008123486.tif 000005
【００３２】
相互作用項がない（つまりＩij＝０）場合、式（２）は概念単位のＳＶＭモデルに戻る。スカラー重みｖiは、後述されるように訓練の中で決定される。
【００３３】
次に、関係付けられる概念、つまり本発明者らのグラフの端縁によって連結される概念が特定できる。このために、本発明者らの訓練セットの地上測定（ｇｒｏｕｎｄ  ｔｒｕｔｈ）標識化を使用するカイ二乗試験を使用できる。各概念は、それが最も統計的に重要な関係を持つ５つの他の概念に連結できる。結果として生じるグラフは概念Ｙiごとに近隣Ｎiを画定する。これは、現在では閾値化することなく行われ、最適ではない可能性がある。しかしながら、一般的なケースで最適グラフを学習することはＮＰ困難である。それにも関わらず、グラフ誘導のために他のヒューリスティックス及び近似方式を評価することは、これらの方法の成功及び将来の研究に有望な分野の両方にとって重大である。多くの他の手法が、本発明を制限することなくこのステップで使用できる。
【００３４】
Ｋｕｍａｒ及びＨｅｒｂｅｒｔの相互作用ポテンシャルは、Ｍａｒｋｏｖ確率場を使用する画像解析における長年に渡る研究により示唆された（Ｓ．Ｋｕｍａｒ及びＭ．Ｈｅｂｅｒｔ、自然画像における空間依存性をモデル化するための分類場（Ｄｉｓｃｒｉｍｉｎａｔｉｖｅ  Ｆｉｅｌｄｓ  ｆｏｒ  Ｍｏｄｅｌｉｎｇ  Ｓｐａｔｉａｌ  Ｄｅｐｅｎｄｅｎｃｉｅｓ  ｉｎ  Ｎａｔｕｒａｌ  Ｉｍａｇｅｓ）、神経情報処理システムの進展（Ａｄｖａｎｃｅｓ  ｉｎ  Ｎｅｕｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍｓ）、ＮＩＰＳ  １６、２００４年）。対照的に、使用されている相互作用ポテンシャルが定義され、テキストカテゴリ化における最新の研究を構築する（Ｎ．Ｇｈａｍｒａｗｉ、及びＡ．ＭｃＣａｌｌｕｍ、「集合マルチラベル分類（Ｃｏｌｌｅｃｔｉｖｅ  ｍｕｌｔｉ−ｌａｂｅｌ  ｃｌａｓｓｉｆｉｃａｔｉｏｎ）、情報及び知識管理ＣＩＫＭ  ’０５に関する第１４回ＡＣＭ国際会議の会議録（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １４ｔｈ  ＡＣＭ  ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｋｎｏｌｗｅｄｇｅ Ｍａｎａｇｅｍｅｎｔ  ＣＩＫＭ  ’０５）」、ＡＣＭ出版社（ＡＣＭ  Ｐｒｅｓｓ）、ニューヨーク、ＮＹ、１９５−２００ページ、２００５年）。式（２）は、式（４）として本発明者らの標記を明確にするために書き直すことができる。
【００３５】
【数４】
2008123486.tif 000006
【００３６】
表記ＰDは、単一概念ＳＶＭ出力からマップされる確率を、ジョイントモデルの対応する周辺確率から区別するために使用できる。式（４）を式（２）と比較すると、相互作用の項が次のような線形形式であることが留意される。
【００３７】
【数５】
2008123486.tif 000007
【００３８】
なお、式（４）は、ベクトルを使用すると、式（６）のように簡潔に書き直される。
【００３９】
【数６】
2008123486.tif 000008
【００４０】
式（６）では、Ｖ及びＰD（Ｘ）のｉ番目の要素は、それぞれｖi及びｌｏｇ（Ｐ（Ｙi｜Ｘ））である。同様に、ΛijとＦij（Ｙi，Ｙj，Ｘ）のｋ番目の要素はそれぞれλij(k)とｆij(k)（Ｙi，Ｙj，Ｘ）である。この形式は、確率場モデルが単に対数線形識別器にすぎないことを示している。したがって、最大尤度モデル訓練の場合、対数尤度の勾配は標準形式を取る。
２．３．１  「ＣＭＬ＋Ｉ」モデル
２つのモデルの相互作用ポテンシャル関数の詳細は以下のとおりである。「ＣＭＬ＋Ｉ」と示される第１のモデルは概念間の共起性を捕捉する。これらの特徴は、本発明者らのグラフで連結される概念Ｙi、Ｙjの組ごとに（つまり、すべての組についてではなく）定義される。したがって、相互作用ポテンシャル関数の索引付きの群は式（７Ａ）〜（７Ｄ）によって示される。
【００４１】
【数７】
2008123486.tif 000009
【００４２】
４つの考えられる組み合わせを別々にモデル化することによって、モデルの中のすべての種類の概念間共起性を捕捉できる。このモデルの場合、相互作用ポテンシャルのための索引集合はΚ＝｛０，１，２，３｝にすぎない。この相互作用モデルは、分類できるように訓練された連関ポテンシャルを以前に提案されたテキストカテゴリ化のための方法（Ｎ．Ｇｈａｍｒａｗｉ、及びＡ．ＭｃＣａｌｌｕｍ、集合マルチラベル分類（Ｃｏｌｌｅｃｔｉｖｅ  ｍｕｌｔｉ−ｌａｂｅｌ  ｃｌａｓｓｉｆｉｃａｔｉｏｎ）、情報及び知識管理ＣＩＫＭ  ‘０５に関する第１４回ＡＣＭ国際会議の会議録（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １４ｔｈ  ＡＣＭ  ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｋｎｏｗｌｅｄｇｅ Ｍａｎａｇｅｍｅｎｔ  ＣＩＫＭ  ’０５））、ＡＣＭ出版社（ＡＣＭ  Ｐｒｅｓｓ）、ニューヨーク、ＮＹ、１９５−２００ページ、２００５年）を参照すること）に追加する。
【００４３】
図３に図示されるように、本発明の実施形態では、ＳＶＭは、媒体のラベルの付けられた集合を使用して概念が存在するかどうかに関して訓練され、媒体はステップ３００で入力される。次に、低レベル特徴はステップ３１０で抽出される。ステップ３２０では、初期条件が設定される。ステップ３３０では、初期条件が増分される。ステップ３４０では、分類識別器は低レベル特徴の集合を用いて訓練される。ステップ３５０では、ＳＶＭは低レベル特徴に基づいて最適化される。ステップ３６０では、ＳＶＭがすべての概念について訓練されるまで手順が反復される。ステップ３７０では、相互作用ポテンシャルが定義される。ステップ３７０では、集合注釈モデルが構築される。
【００４４】
図４に示されているように、図３に示されるような本発明の実施形態で生成できる訓練されたＳＶＭは、概念が媒体集合に存在するかどうかを判断するために別の媒体集合で使用される。ステップ４００で媒体が入力される。次に、ステップ４１０でＳＶＭが適用される。ステップ４２０では、集合注釈モデルが構築される。ステップ４３０では、概念が検出される確率が決定できる。
【００４５】
２．３．２「ＣＭＬＴ＋Ｉ」モデル
概念特徴共起性を捕捉するための第２のモデルを定義できる。第１に、低レベル視覚特徴Ｘは、ｋ手段または他のベクトル量子化技法を使用して訓練集合全体で量子化できる。この離散表現は、Ｑ（Ｘ）０｛０，．．．，Ｑ｝として低レベル特徴について示すことができる。「ＣＭＬＴ＋Ｉ」と示されているこのモデルの場合、相互作用ポテンシャルは式（８Ａ）〜（８Ｄ）によって定義できる。
【００４６】
【数８】
2008123486.tif 000010
【００４７】
相互作用ポテンシャルのための索引集合は、Κ＝｛（ｉ，ｑ）：０≦ｉ≦３，０≦ｑ≦Ｑ｝である。
【００４８】
例１
ＴＲＥＣＶＩＤ２００５開発データは、高レベル概念検出タスクのために使用される。訓練と試験の集合はそれぞれ、２００４年に収集された多様な放送情報源からの６０００を超えるビデオショットを含んでよい。また、５つの概念グラフ及び１１の概念グラフは、Ｒ．Ｙａｎ、Ｍ．−Ｙ．Ｃｈｅｎ、Ａ．Ｈａｕｐｔｍａｎｎ、「確率的グラフィックモデルを使用する概念間のマイニング関係（Ｍｉｎｉｎｇ Ｒｅｌａｔｉｏｎｓｈｉｐｓ  Ｂｅｔｗｅｅｎ  Ｃｏｎｃｅｐｔｓ  ｕｓｉｎｇ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｇｒａｐｈｉｃａｌ  Ｍｏｄｅｌｓ）」、ＩＥＥＥ  ＩＣＭＥ会議録、２００６年の結果に比較して使用される。
【００４９】
５つの概念グラフ：車、顔、人物、テキスト、歩行／ランニング
１１の概念グラフ：建物、車、顔、地図、屋外、人物、スポート、スタジオ、テキスト、都市、歩行／ランニング
比較のために、本発明者らはＹａｎらのシステム（Ｙａｎ、Ｍ．−Ｙ．Ｃｈｅｎ、Ａ．Ｈａｕｐｔｍａｎｎ、「確率的グラフィックモデルを使用する概念間のマイニング関係（Ｍｉｎｉｎｇ Ｒｅｌａｔｉｏｎｓｈｉｐｓ  Ｂｅｔｗｅｅｎ  Ｃｏｎｃｅｐｔｓ  ｕｓｉｎｇ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｇｒａｐｈｉｃａｌ  Ｍｏｄｅｌｓ）」、ＩＥＥＥ  ＩＣＭＥ会議録、２００６年の結果を参照すること）が以下の条件付き確率場を使用することを概略する。
【００５０】
【数９】
2008123486.tif 000011
【００５１】
システムは、適合されたパラメータまで訓練集合の尤度を最大化するように訓練される。対数尤度は以下のとおりである。
【００５２】
【数１０】
2008123486.tif 000012
【００５３】
これは、勾配方程式（１１）及び（１２）を与える。
【００５４】
【数１１】
2008123486.tif 000013
【００５５】
ここでは、Ｙ(d)は、訓練サンプルＸ(d)のための地上測定を示す。また、Ｙi、Ｙjが積分のバイナリ変数を示すとき、Ｙi(d)、Ｙj(d)は、サンプルＸ(d)のための概念ｉ，ｊ０の真の値を示す。（Ｒ．Ｍａｌｏｕｆ、「最大エントロピーパラメータ推定のためのアルゴリズムの比較（Ａ  ｃｏｍａｒｉｓｏｎ  ｏｆ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｍａｘｉｍｕｍ  ｅｎｔｒｏｐｙ  ｐａｒａｍｅｔｅｒ  ｅｓｔｉｍａｔｉｏｎ）」、自然言語学習に関する第６回会議の会議録−第２０巻、コンピュータ的言語学に関する国際会議（Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ｔｈｅ  ６ｔｈ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｎａｔｕｒａｌ  Ｌａｎｇｕａｇｅ  Ｌｅａｒｎｉｎｇ−Ｖｏｌｕｍｅ  ２０  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｒｎｃｅ  Ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｌｉｎｇｕｉｓｔｉｃｓ）、コンピュータ的言語学学会（Ａｓｓｏｃｉａｔｉｏｎ  ｆｏｒ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｌｉｎｇｕｉｓｔｉｃｓ）、モリスタウン、ニュージャージー（Ｍｏｒｒｉｓｔｏｗｎ，ＮＪ）、２００２年１−７）で証明されるように、制限メモリ共役勾配方法が訓練最大エントロピー及び対数線形識別器を大幅に加速する。最大尤度モデル訓練には、Ｂｒｏｙｄｅｎ−Ｆｌｅｔｃｈｅｒ−Ｇｏｌｄｆａｒｂ−Ｓｈａｎｎｏ（ＢＦＧＳ）最適化ルーチンが使用できる。
【００５６】
観察されたＹごとにＰ（Ｙ｜Ｘ）を評価すること、及び「すべての」ｉ０ＣについてＰ（Ｙi｜Ｘ）を計算するために故意に過小評価することを必要とする綿密な推論も使用できる。これは、一般的には概念の数との概念組み合わせの急激な増加のために極めて困難である。本文脈では、観察された組み合わせの数ははるかに少ない。例えば、実験で２００より少ない組み合わせが、（２０４８の考えられる組み合わせと対照的に）１１の概念グラフを使用して観察される。
【００５７】
「ＣＭＵ」と示される第１の実験ベースラインは、式（９）を使用する結果を示す（Ｒ．Ｙａｎ、Ｍ．−Ｙ．Ｃｈｅｎ、Ａ．Ｈａｐｕｔｍａｎｎ、（「確率的グラフィックモデルを使用する概念間のマイニング関係（Ｍｉｎｉｎｇ Ｒｅｌａｔｉｏｎｓｈｉｐｓ  Ｂｅｔｗｅｅｎ  Ｃｏｎｃｅｐｔｓ  ｕｓｉｎｇ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｇｒａｐｈｉｃａｌ  Ｍｏｄｅｌｓ）」ＩＥＥＥ  ＩＣＭＥ会議録、２００６年）。「ＳＶＭ」で示される第２の実験のベースラインは、独立した概念検出のために分類「ＳＶＭ」出力を使用した結果を示す（Ｃ．Ｓｎｏｅｋ、Ｍ．Ｗｏｒｒｉｎｇ、Ｊ．ｖａｎ  Ｇｅｍｅｒｔ、Ｊ．Ｍ−Ｇｅｕｓｅｂｒｏｅｋ及びＡ．Ｓｍｅｕｌｄｅｒｓ、「マルチメディアにおける１０１の意味概念の自動化された検出のための課題（Ｔｈｅ Ｃｈａｌｌｅｎｇｅ  Ｐｒｏｂｌｅｍ  ｆｏｒ  Ａｕｔｏｍａｔｅｄ  Ｄｅｔｅｃｔｉｏｎ  ｏｆ  １０１  Ｓｅｍａｎｔｉｃ  Ｃｏｎｃｅｐｔｓ  ｉｎ  Ｍｕｌｔｉｍｅｄｉａ）」、ＡＣＭマルチメディアの会議録、２００６年）。「５つの概念」グラフの実験結果は図５に要約されている。「１１の概念」グラフのための実験結果は、図６に要約されている。性能基準は、概念ごとにリコールの各レベルで精度を平均してから、概念の集合上で（平均精度の）平均を計算する平均精度（ｍｅａｎ  ａｖｅｒａｇｅ  ｐｒｅｃｉｓｉｏｎ）（ＭＡＰ）である。
【００５８】
分類できるようなラベル単位の識別器の貢献を隔離するために、式（１３）の相互作用ポテンシャルが、「ＣＭＬ」システムを式（４）を用いて構築するために「ＣＭＵ」システムで使用できる。
【００５９】
【数１２】
2008123486.tif 000014
【００６０】
このケースの場合、端縁（Ｙｉ，Ｙｊ）ごとに単一の特徴があり、ｋを超える合計が単一の項に退化する。「ＣＭＬ」システム（０．６００２）は、５つの概念のグラフの場合、「ＳＶＭ」システム（０．５９７７）及び「ＣＭＵ」システム（０．５８８２）よりわずかにうまく実行する。また、それは１１の概念グラフ（［ＣＭＵ］＝０．５２１１、「ＳＶＭ」＝０．４９７５、「ＣＭＬ」＝０．５２６２）上の両方のシステムより性能が優れている。
【００６１】
次に、さらに完全な索引が付けられた群の相互作用ポテンシャルが、「ＣＭＬ＋Ｉ」と記されるシステムを形成するために、式（７Ａ）〜（７Ｄ）によって式（４）に与えられている。このシステムは異なる種類の概念間関係性を説明し、それぞれ「５つの概念」及び「１１の概念」のグラフについて０．６２３３と０．５３０７というＭＡＰを用いて両方のケースのすべてのシステムの最高レベルで実行する。
【００６２】
最終システムは、概念−特徴共起性相互作用ポテンシャルの値を試験する。「ＣＭＬＴ」モデルが分類できる連関ポテンシャルを（ＣＭＬに類似する）単純な相互作用と結合する。
【００６３】
【数１３】
2008123486.tif 000015
【００６４】
システムは両方のグラフについてＳＶＭベースラインより性能が優れているが、ＣＭＵベースラインは１１概念グラフについてさらに向上する。「ＣＭＬＴ」システムはそれぞれ５つの概念グラフと１１の概念グラフについて０．６００９と０．５１５６というＭＡＰを有する。「ＣＭＬＴ＋Ｉ」システムは、（８）というさらに完全な相互作用ポテンシャル関数を使用する。このシステムは「ＣＭＬＴ」より性能が優れているが、両方のケースで「ＣＭＬ＋Ｉ」より悪い。「ＣＭＬＴ＋Ｉ」システムは、それぞれ５の概念グラフと１１の概念グラフについて０．６１２２及び０．５１８４というＭＡＰを有する。これは、粗い量子化、及び使用されている相対的に無益な低レベル特徴（ｋ手段から１２６のクラス）に起因することがあり、さらに精密な量子化が追加の改善策を生じさせることを予想できる。
【００６５】
本発明の方法、システム及び構成要素の例の実施形態が本明細書に説明された。ほかのどこかで注記されるように、これらの例の実施形態は例示目的のためだけに説明され、限定しない。他の実施形態が考えられ、本発明によってカバーされている。このような実施形態は、本明細書に含まれている教示に基づき関連技術の当業者に明らかになるであろう。
【００６６】
したがって、本発明の広さ及び範囲は、前述された例示的な実施形態のどれかによって制限されるべきではなく、請求項及びその同等物によってのみ定義されるべきである。
【図面の簡単な説明】
【００６７】
【図１】４つの概念を検出するために使用され独立した分類であるグラフィックモデルを示す図である。
【図２】４つの概念を検出するために使用され集合的分類であるグラフィックモデルを示す図である。
【図３】概念が本発明に従って媒体のラベルが付けられた集合の上に存在するかどうかを判断するために意味解析モデルを訓練するためのフローチャートである。
【図４】本発明に従って媒体を使用して訓練された概念を検出するために意味解析発明を試験するためのフローチャートである。
【図５】「５概念」グラフのための多様なシステム変形を比較する実験結果を示す図である。
【図６】「１１概念」グラフのための多様なシステム変形を比較する実験結果を示す図である。
【図１】
2008123486.tif 000016
【図２】
2008123486.tif 000017
【図３】
2008123486.tif 000018
【図４】
2008123486.tif 000019
【図５】
2008123486.tif 000020
【図６】
2008123486.tif 000021