JP5255372B2 - ビデオ・ストリームに対するリアル・タイム新規イベント検出のシステムおよび方法 - Google Patents

Description

本発明は、全般的にはビデオ・ストリーム処理に関し、より具体的には、ビデオ・ストリーム内の新規イベントを検出する技法に関する。

ストリーミング・ビデオについて、新規イベント検出（ＮＥＤ）は、以前に見たことのないイベントを提示する最初のビデオ・クリップを取り込むタスクである。このタスクは、情報収集（例えば、反テロ目的）、金融市場分析、およびニュース分析など、有用な情報が通常は時間に伴ってすばやく増加する大量のデータに埋もれている複数の領域での実用的応用例を有する。これらの応用例は、しばしば、時間にクリティカルであり、高速のターンアラウンドを必要とするので、オンライン新規イベント検出（ＯＮＥＤ）システムを実際に開発することが非常に望ましい。

約１０年前に、文書ストリームに対するＯＮＥＤが、テキスト処理コミュニティでますます関心を集め始めた。そのテキスト対応物の拡張として、ビデオ・ストリームに対するＯＮＥＤも、テキスト情報とビジュアル情報との両方を活用することによって、ビデオ処理コミュニティで高まる注意を引いた。ビデオＯＮＥＤシステムの基本的なアイデアは、新規クリップを過去に到着したすべてのクリップと比較することである。テキスト特徴およびビジュアル特徴に基づく類似度値のすべてが、あるしきい値未満である場合に、新規クリップは、新規イベントを提示すると予測される。

いままでの作業は、追加のイメージ情報が、関連するビデオ・クリップの識別およびよりよいトピック追跡結果の達成において重要な役割を演じることを示した。しかし、ビデオＯＮＥＤに関するこれらの努力のすべてが、主に、検出効率ではなく検出精度の最適化に焦点を合わせている。実際には、これらの方法は、クリップの個数に関して２次式のオーダーの時間複雑さを生じる。したがって、これらの方法は、特に大規模なビデオ・コレクションに関して、リアル・タイム環境で新規ビデオ・イベントを検出するのに十分に効率的ではない。
W. Hsu, and S. Chang, "Topic Trackingacross Broadcast News Videos with Visual Duplicates and SemanticConcepts," IEEE International Conference on Image Processing (ICIP), 2006:141-144 M. Campbell, S. Ebadollahi, and D.Joshi et al., "IBM Research TRECVID-2006 Video Retrieval System,"NIST TRECVID workshop, 2006 R. Peterson, "IBM Strives forSuper Human Speech," http://www.accessible-devices.com/superspeech.html,2006

例えば、数万個のテレビジョン・チャネルを同時に監視することを要求される情報収集システムでは、既存のＯＮＥＤシステムが、そのような集約された極端に高帯域幅のビデオ・ストリームをリアル・タイムで処理することは、非常にむずかしい。したがって、一部の既存ＮＥＤシステムは、オンラインで使用可能と言われているが、これらは、実際にはリアル・タイム応用例に十分に効率的ではない。

本発明の原理は、リアル・タイムでの改善された検出効率をもたらす、ビデオ・ストリーム内で新規イベントを検出する技法を提供する。

例えば、本発明の一態様で、方法は、所与のイベントがビデオ・ストリーム内の新規イベントであるかどうかを判定する。ビデオ・ストリームは、複数のイベントを含む。第１ステップは、所与のイベントから特徴の第１集合（例えば、テキスト特徴）を抽出する。特徴の第１集合は、所与のイベントに関連する特徴の第２集合（例えば、イメージ特徴）と比較して、処理するのが計算的により安価である。第２ステップは、１つまたは複数の第１相違度判断基準が存在するときに、特徴の第１集合だけを使用して、所与のイベントとビデオ・ストリーム内の１つまたは複数の以前のイベントとの間の１つまたは複数の第１相違度値を計算する。第３ステップは、１つまたは複数の計算された第１相違度値に基づいて、所与のイベントが新規イベントであるかどうかを判定する。

本発明のもう１つの態様で、ビデオ・ストリーミング環境内で以前に見られていないイベントを提示する新規イベント・ビデオ・クリップを取り込むためのリアル・タイム新規イベント検出方法は、マルチステージ・シーケンシャル・フィルタリング・プロセスを含む。このプロセスは、関連する特徴を識別することと、特徴を導出するか抽出するための計算的労力に基づいて特徴をランキングすることと、ランキングされた特徴に基づいて１つまたは複数のマルチステージ・シーケンシャル・フィルタを形成することであって、より簡単に計算される特徴は、よりむずかしく計算される特徴の前に使用される、形成することとを含む。一特定の実施形態で、マルチステージ・シーケンシャル・フィルタリング・プロセスの１ステージは、新規イベントを検出するためにフィルタとしてテキスト特徴のみを使用することであり、後続ステージは、検出プロセスを補足するためにフィルタとしてイメージ特徴を使用することである。

本発明の上記および他の目的、特徴、および利点は、添付図面とともに、本発明の例示的実施形態の以下の詳細な説明を参照することによって、明白になるであろう。

本発明を、下では、例示的なタイプのビデオ・ストリームベースのデータの文脈で説明する。しかし、本発明が、どの特定のタイプのビデオ・データ・ストリームにも限定されないことを理解されたい。そうではなく、本発明は、ビデオ・データ・ストリーム内の新規イベントの検出効率を改善することが望ましいすべてのビデオ・データ・ストリームに、より一般的に適用可能である。

図１に、時間軸に沿ってビデオ・ストリーム内のイベント（１０２、１０４、１０６、１０８、１１０、および１１２）を示す。異なる形状は、異なるイベントに対応する。塗り潰された形状は、取り込まれる必要があるクリップ（すなわち、新規クリップ）を表す。句「ビデオ・クリップ」（またはより単純に「クリップ」）が、ビデオ・ストリームの少なくとも１つの部分を指すことを意図され、用語「イベント」が、ビデオ・データ・ストリーム内の対象クリップの出現または存在に対応することを理解されたい。また、「クリップ」（または、より一般的にビデオ・ストリームの対象部分）が、１つまたは複数のイメージを含むことができることを理解されたい。下でさらに説明するように、「クリップ」を「ショット」とすることもできる。また、用語「オンライン」は、用語「リアル・タイム」と交換可能に使用される場合があり、一般に、ビデオ・ストリーム内の新規イベントまたは新規クリップの受け取りと実質的に同時に実行されるステップ／動作を記述することを理解されたい。これを、ステップ／動作がある後の時刻に実行される「オフライン」または「非リアル・タイム」と比較されたい。

本発明の原理によれば、前述の効率問題に対処し、実質的な検出精度を犠牲にせずにＯＮＥＤシステムのビデオ処理速度を数桁改善する技法が提供される。イメージ特徴に対する計算は、どちらかといえば時間がかかるので、我々は、できる限りイメージ特徴の処理を遅延させることによって、我々のＯＮＥＤシステムの効率を最大にする。より具体的には、我々は、次の複数の最適化ステップを提案する。まず、我々は、テキスト特徴だけを使用して、非新規イベント・クリップのほとんどをフィルタ・アウトし、その結果、これらのクリップの高価なイメージ特徴抽出ステップを避ける。次に、新規クリップを古いクリップと比較するときに、我々は、まず、そのテキスト類似度を計算し、テキストが十分に異なる場合に、コストの高いイメージ類似度計算をスキップする。最後に、我々は、インデクシング法および圧縮法の組合せを使用して、テキスト処理を高速化する。イメージ類似度計算中に、我々は、アンカ・イメージの除去も行って、ＯＮＥＤシステムの検出精度を改善する。

最適化された技法を詳細に述べる前に、我々は、まず、ＯＮＥＤシステムの１つの例示的実施形態（本明細書では「ベースライン・システム」と称する）を説明する。このベースライン・システムが、ＴＦ−ＩＤＦ（単語頻度−逆文書頻度（Inverse Document Frequency））テキスト特徴および２進イメージ複製特徴を含む、HsuおよびChang（W.Hsu, and S. Chang, "Topic Tracking across Broadcast News Videos with VisualDuplicates and Semantic Concepts," IEEE International Conference on ImageProcessing (ICIP), 2006: 141-144）で報告された技術的現状のＯＮＥＤシステムで提案された２つの最も影響力のある情報ソースを組み合わせると仮定する。本発明の原理を示すために、検出技法を、このベースライン・システムの上で構築されるものとして本明細書で例示的に説明する。

図２に、ビデオ・ストリームが、例えば１つまたは複数の多言語ビデオ・チャネル２０１（Ｃ_１、Ｃ_２、．．．、Ｃ_ｎ）から来る可能性がある、ベースラインＯＮＥＤシステム２００のアーキテクチャを示す。これらのストリームは、「ショット」に区分される。区分するブロックは、明示的には示されていない。各ショットは、おおむね数秒（例えば、３秒）の長さであり、編集者のカット、フェード、またはディゾルブ(dissolve)のない、単一の連続したカメラ操作と定義される。ショットごとに、特徴抽出モジュール２０２は、そのキーフレームからのイメージ特徴抽出（２０４）と自動音声認識（２０６）およびその後の機械翻訳（２０８）を使用することによる英語テキスト特徴の入手との両方を実行し、その結果、異なる言語のオリジナル・ビデオ・クリップが比較可能になる。「キーフレーム」は、ビデオ内の後続イメージの基準として使用される完全な（おそらくは圧縮された）イメージである。次に、ＯＮＥＤコンポーネント２１０が、テキスト特徴およびイメージ特徴を使用して、以前に見られていないイベントを提示する新規イベント・ショットを識別し、これらのショットをコンシューマ２１２に送り、コンシューマ２１２は、人または例えばより深い分析を行うコンピュータ・プログラムのいずれかとすることができる。我々は、この例示的実施形態で、基本的なＮＥＤ単位としてビデオ・ショットを使用するが、本発明の原理は、この適用例に限定されるものではなく,したがって、本発明の原理が、ニュース記事などの他の単位にあまねく適用可能であることに留意されたい。

ベースライン・システムは、伝統的なｔｆ・ｉｄｆ単語重さをテキスト特徴として使用する。各ショットＳは、意味のあるテキスト類似度を計算するのに十分なテキストを含むには短すぎる（下を参照されたい）ので、我々は、前のｍ＝５個のショットのテキストと次のｍ個のショットのテキストとの両方を用いてＳのテキストを拡張する（これらのショットのすべてが同一チャネルから来ることに留意されたい）。情報検索の慣例に従い、我々は、単語を一意の語と定義し、語彙をすべての一意の語の集合と定義する。語彙内の各単語ｔおよびショット集合Ｅ内のショットＳについて、ベースライン・システムは、次の式を使用して、単語重さを計算する。
（ｆ１）単語頻度（ｔｆ）重さｗ_ｔｆ＝ｌｎ（ｔｆ＋１）
（ｆ２）逆数文書頻度（ｉｄｆ：inverse document frequency）重さ
ｗ_ｉｄｆ＝ｌｎ［（Ｎ＋１）／（ｄｆ＋０．５）］
（ｆ３）単語（ｔｆ・ｉｄｆ）重さｗ_ｔ＝ｗ_ｔｆ×ｗ_ｉｄｆ
ここで、ｔｆは、Ｓのテキストにおける単語ｔの頻度（すなわち、出現の回数）であり、Ｎは、Ｅのショットの総数であり、ｄｆは、そのテキストがｔを含む、Ｅのショットの個数である。

実際には、複製に近いイメージを検出するのに（ほぼ同等に）適するイメージ特徴を抽出する多数の異なる形がある。ベースライン・システムは、Campbell他（M. Campbell, S. Ebadollahi, and D. Joshi et al., "IBMResearch TRECVID-2006 Video Retrieval System," NIST TRECVID workshop, 2006）に記載のカラー・モーメント（colormoment）特徴を使用し、ここで、局所化された色統計が、キーフレーム・イメージの３×３グリッドから抽出され、Ｌａｂ色空間内の各グリッドの最初の３つのモーメントが、Ｓのｎ＝８１個のイメージ特徴ｆ_ｉ（１≦ｉ≦ｎ）を構成するのに使用される。しかし、本発明は、この特定の技法に限定されない。

もう１つの例として、ＩＢＭ Ｃｏｒｐｏｒａｔｉｏｎ社のTranslingualAutomatic Language Exploitation（ＴＡＬＥＳ）システム（R. Peterson, "IBM Strives forSuper Human Speech," http://www.accessible-devices.com/superspeech.html,2006）は、コンピュータ・クラスタを使用して、約４分の遅延を伴って（ほぼリアル・タイムで）同時に数千個のチャネルからビデオ・フレームに対してイメージ特徴抽出とテキスト特徴抽出との両方を実行することができる。

やはり、上で説明したイメージ特徴抽出技法およびテキスト特徴抽出技法は、単に、使用できる従来の技法の例であり、したがって、他の適切な技法を使用できることを理解されたい。本発明の原理の焦点が、既存システムがリアル・タイムで満足には完了できないＯＮＥＤコンポーネント（２１０）であることを理解されたい。

ビデオＯＮＥＤシステムで新規イベント・ショットを検出するために、我々は、２つのショットＳ_１とＳ_２との間の相違度を、そのテキスト特徴およびイメージ特徴を使用して計算する。相違度が小さいほど、Ｓ_１およびＳ_２が同一イベントを提示する可能性が高い。相違度計算法を次に示す。まず、テキスト相違度値を、（ｆ４）および（ｆ５）を使用して入手する。
（ｆ４）正規化テキスト点乗積値

（ｆ５）テキスト相違度値

ただし、ｗ_ｉ，ｊ（ｊ＝１，２）は、Ｓ_ｊの単語重さである。表記ｔ∈Ｓ_ｊは、単語ｔがＳ_ｊのテキストに現れることを意味する。次に、（ｆ６）および（ｆ７）を使用してイメージ相違度値を入手する。
（ｆ６）正規化イメージ相違度値

（ｆ７）２進化イメージ相違度値

ただし、ｆ_ｉ，ｊ（ｊ＝１，２）は、Ｓ_ｊのイメージ特徴であり、Ｔ_{ｉｍａｇｅ}は、イメージ相違度を２進化するためのしきい値であり、Ｉは、インジケータ関数である。すなわち、２進化イメージ相違度は、正規化イメージ相違度がＴ_{ｉｍａｇｅ}より大きい場合に１であり、そうでない場合には０である。最後に、Ｓ_１およびＳ_２の総合相違度値を、（ｆ８）に従ってテキスト相違度値と２進化イメージ相違度値との線形組合せとして入手する。

ただし、ｗ_{ｉｍａｇｅ}は、ビジュアル・モダリティの線形重さである。そのような線形融合モデルは、ビデオＯＮＥＤシステムでビジュアル・モダリティおよびテキスト・モダリティを融合する最も効果的な手法の１つである。

ここで、ベースライン・システムの詳細を提示する。我々は、各ショットのテキストに関する情報検索で通常の前処理動作に従う、すなわち、（１）ステミング（語幹の抽出）を標準Ｐｏｒｔｅｒ ｓｔｅｍｍｅｒを使用して実行し、（２）ストップワードを、標準ＳＭＡＲＴストップワード・リストを使用することによって除去する。「ステミング」とは、語形変化（または時々派生）した語をその語幹、基本型、または原型、一般には書き言葉の形に変換するプロセスである。「ストップワード」とは、テキストの処理の前または後にフィルタ・アウトされる単語に与えられる名前である。

ショット集合Ｅは、新規ショットがビデオ・ストリーミング環境内で到着し続けるときに変化し続けることに留意されたい。ＯＮＥＤのためには、ｔｆ重さおよびｉｄｆ重さの計算を、Ｅに類似する特性を有する静的ショット集合Ｅ‘に基づくものとすることができる。Ｅ’のテキストに存在しない単語について、そのｄｆは、１と仮定される。統計Ｎおよびｄｆを増分式に更新する方法と比較して、この静的方法は、はるかに少ないオーバーヘッドを有するが、検出精度はほぼ同一のままである。

ショットＳが到着するときに、Ｓは、まず、前処理され、その特徴がメモリに保存される。次に、Ｓは、Ｓの前に同一チャネルから到着したばかりのＬ＝５０個のショットを除く、過去に到着したすべての古いショットと比較される。というのは、これらのＬ個のショットが、Ｓと同一のニュース記事セグメントに含まれる可能性が高いからである。Ｓと古いショットとの間のすべての総合相違度値が、しきい値Ｔを超える場合に、Ｓは、新規イベント・ショットであると予測される。そうではなく、Ｓと古いショットＳ_ｏｌｄとの間の総合相違度値が、Ｔ未満である場合には、Ｓは、Ｓ_ｏｌｄと同一のイベントを提示すると予測される。

テキスト特徴が、新規イベントの検出において最も有効なコンポーネントであるが、視覚的に近い複製が、それでも、テキスト・ベースラインの検出精度を一貫して高めることができることを示すことができる。より具体的には、テキスト特徴とイメージ特徴との両方を使用することによって、テキスト・ベースラインの検出精度を２５％まで改善することができる。これは、２つのショット内の類似するイメージが、それらに関連する音声トランスクリプトが言い換えまたは音声認識／翻訳エラーに起因して十分に似てはいない可能性がある場合であっても、しばしば、それらが同一イベントを表すことの証拠を提供するという事実によって説明することができる。すなわち、テキスト特徴自体は、これらの２つのショットが同一イベントを提示していることを正しく検出することができない。しかし、イメージ特徴からの追加の証拠を考慮することによって、このシステムは、正しい予測を作ることができる。

総合相違度値に対するさらなる洞察を提供するために、我々は、オリジナルの相違度式（ｆ８）を、テキスト特徴とイメージ特徴とを非対称に扱う同等の形に書き直す。我々は、さらに、この代替の形を分析して、ＮＥＤプロセスをどのようにしてより効率的にすることができるかを示す。まず、式（ｆ５）および（ｆ７）を（ｆ８）に代入し、Ｓ_１およびＳ_２の総合相違度を

に書き直す。我々は、２つの可能なケースを考慮することによって（ｆ９）を分析するが、この両方のケースが、２つのサブケースを有する。
（１）Ｓ_１およびＳ_２のキーフレームが、近い複製イメージであるとき、すなわち

であるときに、

を得る。したがって、次を予測することができる。
（ｉ）サブケース１：Ｓ_１およびＳ_２は、

である場合に同一イベントを表し、
（ｉｉ）サブケース２：Ｓ_１およびＳ_２は、

である場合に異なるイベントを表す。
（２）Ｓ_１およびＳ_２のキーフレームが、近い複製イメージではないとき、すなわち

であるときに、

を得る。

したがって、次を予測することができる。
（ｉ）サブケース３：Ｓ_１およびＳ_２は、

である場合に同一イベントを表し、
（ｉｉ）サブケース４：Ｓ_１およびＳ_２は、

である場合に異なるイベントを表す。

図３に、上の４つのサブケースを示す。
任意の２つのショットＳ_１およびＳ_２について、それらが同一イベントを表すかどうかを判定するために、そのテキスト／イメージ特徴の両方を使用し、上の４つのサブケースのすべてをチェックしなければならないと思われる。しかし、これは、多くの場合に不必要であることがわかる。テキストとイメージとを非対称に扱うことによって、我々は、上の４つのサブケースを次の同等な３つのケースに書き直すことによってＮＥＤ動作を大幅に単純化することができ、次の３つのケースの中では、ケース２だけが、２つのサブケースを有する。
（１）ケース１：

。この場合に、我々は、Ｓ_１およびＳ_２が、正規化イメージ相違度

にかかわりなく、異なるイベントを提示すると予測する。
（２）ケース２：

この場合には、次の２つのサブケースがある。
（ｉ）サブケース１：

の場合に、我々は、Ｓ_１およびＳ_２が、同一イベントを提示すると予測する。
（ｉｉ）サブケース２：

の場合に、我々は、Ｓ_１およびＳ_２が、異なるイベントを提示すると予測する。
（３）ケース３：

。この場合に、我々は、Ｓ_１およびＳ_２が、正規化イメージ相違度

にかかわりなく、同一イベントを提示すると予測する。

上のケースでは、ケース１とケース３との両方が、ショットＳ_１およびＳ_２のテキスト特徴だけを必要とする。したがって、ＯＮＥＤのためには、テキスト特徴およびイメージ特徴を非対称に扱うことができる、すなわち、我々は、プレフィルタとしてテキスト特徴を使用して、イメージ特徴に対する不必要な動作のほとんどをフィルタ・アウトすることができる。これは、検出効率に対する膨大な利益をもたらすことができる。というのは、ほとんどのショット対のテキスト類似度が低く、したがって、ケース１が最も頻繁に発生するケースであるからである。その一方で、テキスト特徴の前にイメージ特徴を処理することは、望ましくない。というのは、イメージ特徴の使用だけでは、Ｓ_１およびＳ_２が同一イベントを提示するかどうかを判定できないからである。

ここで、上の分析に基づくＯＮＥＤシステムの効率を改善する例示的技法を説明する。まず、我々の最適化されたＯＮＥＤシステムの高水準の概要を与え、次に、個々の技法を詳しく述べる。

図４に、例示的実施形態による最適化されたＯＮＥＤシステム４００のアーキテクチャを示す。１つまたは複数のチャネル４０１（Ｃ_１、Ｃ_２、．．．、Ｃ_ｎ）からのビデオ・ストリームが、ショット（明示的には図示せず）に分割される。ショットＳごとに、音声認識（４０３）技法ならびに機械翻訳（４０４）技法を使用することによって、テキスト特徴を抽出する（４０２）。テキスト特徴は、非ニュース・ショットを識別し、除去する（４０６）のに使用される。残りのニュース・ショットが、ＯＮＥＤコンポーネント４１２に供給され、ここで、新規イベント・ショットが識別され、コンシューマ（４１４）に送られる。ＯＮＥＤプロセス中に、我々は、Ｓのキーフレームがアンカ・イメージであるかどうかを判定すること（４１０）およびＳと古いショットとの間のイメージ類似度を計算することが必要であるときに限って、Ｓのイメージ特徴を抽出する（４０８）。

図５に、ＯＮＥＤシステム４００に従って使用されるアルゴリズムの説明を示す。このアルゴリズムの詳細は、下で説明する。当業者は、アルゴリズム５００内の擬似コードの諸部分が、ＯＮＥＤコンポーネントによって実行されるステップに関係することを簡単に認めるであろう。

放送ビデオでは、非ニュース・ビデオ・セグメント（例えば、コマーシャル、ＴＶ番組）が、通常、ニュース記事と混合されている。ＯＮＥＤのためには、類似するショットが前に現れていない場合であっても、非ニュース・ショットを新規イベント・ショットとして扱ってはならない。これらのショットの除去は、ＯＮＥＤコンポーネントによって処理する必要があるショットの数を減らすだけではなく、ＯＮＥＤシステムの効率および検出精度をも改善することができる。

このために、単純な方法は、ニュース・ビデオが放送される定期的な時間期間を手動で指定することである。しかし、そのような方法は、ＯＮＥＤシステムが処理する必要がある通常のケースの数万チャネルにスケーラブルではない。さらに、我々の目的には、コマーシャルだけではなくすべての非ニュース・ショットを除去することが好ましい。代替案として、我々は、単純なテキストベースの方法を適用して、非ニュース・ショットを除去する。その基本的なアイデアは、非ニュース・ショット（例えば、コマーシャル）が、しばしば、ニュース・ショットより大きい背景雑音を有し、これが、音声リコグナイザが非ニュース・ビデオでテキストを認識することをむずかしくすることである。また、ニュース・ショットでは、アンカ・パーソンが、非ニュース・ショット（例えば、ＴＶ番組）より速いペースで話す傾向がある。この２つのプロパティに基づいて、我々は、ショットＳの認識されたテキストがＪ個未満の別個の単語を含む場合に、Ｓがニュースではないと予測し、ここで、Ｊは所定の定数である。この方法は、どちらかといえば単純であるが、非常に正確であり、低いオーバーヘッドを有し、これは、ＯＮＥＤシステムの効率を改善するのを助ける。また、高価なイメージ特徴抽出ステップは、捨てられる非ニュース・ショットについてもはや不要である。

上で述べたように、できる限りイメージ特徴の処理を遅延させることが望ましい。図４および５に示されているように、新規ショットＳを処理するときには、まず、そのイメージ特徴ではなくテキスト特徴を抽出する。Ｓを古いショットＳ_ｏｌｄと比較するときには、まず、それらのイメージ相違度ではなく、それらの正規化テキスト点乗積を計算する。

（上のケース１）の場合には、ＳおよびＳ_ｏｌｄが異なるイベントを提示すると予測する。

（上のケース３）の場合には、ＳおよびＳ_ｏｌｄが同一のイベントを提示すると予測する。ケース１とケース３との両方で、高コストであるが不必要なイメージ相違度計算ステップをスキップする。ケース２（

のとき）に限って、イメージ相違度を計算する必要がある。ショットのほとんどの対のテキスト点乗積は、小さいので、ケース２は、通常、ケース１およびケース３よりはるかに低い頻度で発生する。その結果、ほとんどのイメージ相違度計算を、節約することができる。

さらに、新規ショットが新規イベントではないと予測されるときに、比較されたすべての古いショットがケース１またはケース３のいずれかに属する場合には、高価なイメージ特徴抽出ステップをスキップすることができる。言い換えると、Ｓが新規イベント・ショットであると予測されるときまたはいくつかのＳ_ｏｌｄについて

を有するときのいずれかに限って、新規ショットＳについてイメージ特徴を抽出すればよい。実際には、多数のチャネルの存在下で、ほとんどのショットは、異なるチャネルにまたがる同一イベントと同一チャネル内の同一イベントとの両方の繰り返される言及に起因して、既存イベントを提示している。また、ケース１およびケース３は、ケース２よりはるかに頻繁に発生する。したがって、ショットの大きい分数について、高価なイメージ特徴抽出ステップをスキップすることができる。

ニュース・ビデオでは、ニュース記事が、通常はアンカ・パーソンによって放送される。同一チャネルからの２つのニュース・ショットは、しばしば、同一のアンカ・パーソンを有するキーフレームを有するが、異なるイベントを提示する。しかし、この場合には、類似するキーフレームが、この２つのショットが同一イベントを提示することのヒントとして扱われてはならない。この要因を考慮に入れるために、我々は、次の方法を使用する。Campbell他（M. Campbell, S. Ebadollahi, and D. Joshi et al., "IBMResearch TRECVID-2006 Video Retrieval System," NIST TRECVID workshop, 2006）に記載のアンカ・イメージ検出方法を使用して、どのキーフレームがアンカ・イメージであるかを検出する。そのような既知のアンカ・イメージ検出方法では、サポート・ベクトル・マシン（ＳＶＭ）および低水準色コレログラム特徴（low-levelcolor correlogram feature）に基づいて、どのキーフレームがアンカ・イメージであるかに関する判定を行う。他の既知のアンカ・イメージ検出方法を使用することができる。次に、２つのショットを比較するときに、いずれかのショットのキーフレームがアンカ・フレームである場合には、２進化イメージ相違度に１をセットする。すなわち、我々は、キーフレームのいずれかがアンカ・ショットである場合に、それらを異なるものとして扱う。これは、ＯＮＥＤシステムの検出精度に対するアンカ・ショットの誤った証拠の影響を減らすことができる。

通常、あるイベントの議論は、ニュース・ビデオ内で有限の時間の間だけ続き、新規ショットは、かなり古いショットと同一のイベントを提示する可能性が低い。したがって、我々は、最後のＷ日などのスライディング・ウィンドウ内の古いショットの情報だけをメモリに保つ。ここで、Ｗは、所定の定数である。ショットＳについて保たれる情報は、そのテキスト特徴とイメージ特徴との両方を含む（上を参照されたい）が、これらの特徴だけが将来のショットとのＳの比較に必要なので、ビデオ・イメージは含まない。古いショットがスライディング・ウィンドウから満了したならば、その情報は即座に捨てられる。図示のように、図８は、本発明の実施形態よるスライディング時間ウィンドウを示す。

通常、イベントは、多数のショットによって提示される。これらのショットのうちの１つだけが、新規イベント・ショットである。同一イベントを提示するすべてのショットが、互いに類似する傾向がある。したがって、新規ショットを、同一イベントを提示するすべての古いショットと比較することは、やりすぎである。その代わりに、我々は、新規イベント・ショットの情報だけを保つ。新規ショットＳが到着するときに、Ｓを、古い新規イベント・ショットと比較する。Ｓが、新規イベントを提示する新規イベント・ショットであると予測される場合には、Ｓの情報をメモリに保存する。そうでない場合には、Ｓを破棄する。

あるショットのテキストのすべての単語を、その単語重さの降順でソートすることができる。一般に、より大きい重さを有する単語は、ＮＥＤにとってより重要である。したがって、保存されたショットごとに、我々は、すべての単語ではなく、最大の重さを有する上位Ｋ個の単語だけを保つ。ここで、Ｋは、所定の定数である。上位Ｋ個の単語だけが、テキスト点乗積の計算に使用される。

相違度値計算のオーバーヘッドを減らすために、新規ショットと異なるイベントを提示するショットのほとんどをすばやくフィルタ・アウトするのに低オーバーヘッド法を使用することによって、プレフィルタリング技法を開発する。この形で、我々は、計算する必要がある相違度値の個数を実質的に減らすことができる。２つのショットＳ_１およびＳ_２を検討されたい。Ｓ_１およびＳ_２が同一イベントを提示する場合に、そのテキストの上位単語は、あるオーバーラップを有する傾向がある。すなわち、いくつかの単語が、Ｓ_１のテキストとＳ_２のテキストとの両方の上位単語に現れる可能性が高い。したがって、これらの上位単語を使用して、不必要な計算をすばやくフィルタ・アウトすることができる。より具体的には、我々は、所定の定数Ｍ（Ｍ≦Ｋ）を有する。Ｓ_１およびＳ_２のテキスト点乗積を計算する前に、まず、Ｓ_１およびＳ_２の上位Ｍ個の単語が交差するかどうかをチェックする。そうである場合には、Ｓ_１およびＳ_２のテキスト点乗積の計算を継続する。そうでない場合には、我々は、Ｓ_１およびＳ_２が異なるイベントを提示すると予測し、そのテキスト点乗積を計算しない。

我々は、プレフィルタ・アウトされたショットの不必要な処理を避けるためにインデックスを構築する。語彙内の各単語は、単語ｉｄを有する。各ショットは、その到着時刻に対応するショットｉｄを有する。２つのインデックスすなわち順方向インデックスおよび逆インデックスが、保存されたすべてのショットについて保たれる。順方向インデックスは、保存されたショットごとに１エントリを有する。これらのエントリは、ショットの到着時刻の降順でソートされる。これは、最後のＷ日のスライディング・ウィンドウから満了したショットの情報をすばやく識別し、捨てることを可能にする（上を参照されたい）。保存されたショットごとに、対応するエントリは、イメージ特徴と単語重さに関連する上位Ｋ個の単語との両方を保つ。これらの単語は、その単語ｉｄの昇順でソートされる。その結果、２つのショットのテキスト点乗積を、その単語リストの効率的な「マージ」を介して計算することができる。

保存されたショットごとに、その上位Ｍ個の単語だけが、逆インデックスによって追跡される。逆インデックスは、語彙内の単語ごとに１エントリを有する。単語ｔのエントリは、その上位Ｍ個の単語がｔを含むすべてのショットのショットｉｄのポスティング・リスト（posting list）（リンク・リスト）である。これらのショットｉｄは、降順でソートされ、その結果、ポスティング・リストのマージを効率的に行えるようになっている。新規ショットＳが到着するときには、Ｓの上位Ｍ個の単語に対応するＭ個のポスティング・リストだけをスキャンする。これらのＭ個のポスティング・リストを一緒にマージして、Ｓと同一のイベントを提示する可能性がある候補ショットのショットｉｄを見つける。これが、上で説明したプレフィルタリング技法である。次に、そのような候補ショットＳ_ｃごとに、順方向インデックスを使用して、ＳおよびＳ_ｃのテキスト点乗積およびイメージ相違度（必要な場合に）を計算する。この計算は、候補ショットｉｄが生成されるのと同時に実行される。この形で、Ｓおよび古いショットの総合相違度値が、しきい値Ｔより小さい場合に、Ｓは、非新規イベント・ショットであると予測され、Ｓの処理は、即座に停止する。そうではなく、Ｓが新規イベント・ショットであると予測される場合には、Ｓのショットｉｄが、保存されたショットのショットｉｄより大きいので、Ｓの情報を、逆インデックスに簡単に追加することができる。

図６に、本発明のもう１つの実施形態によるオンライン新規イベント検出方法論を示す。この方法は、ＯＮＥＤシステム４００内で実施することができる。図示のように、方法６００は、所与のイベントがビデオ・ストリーム内の新規イベントであるかどうかを判定する。ビデオ・ストリームは、複数のイベントを含む。ステップ６０２は、所与のイベントから特徴の第１集合（例えば、テキスト特徴）を抽出する。特徴の第１集合は、所与のイベントに関連する特徴の第２集合（例えば、イメージ特徴）と比較して、処理するのが計算的により安価である。ステップ６０４は、１つまたは複数の第１相違度判断基準が存在するときに、特徴の第１集合だけを使用して、所与のイベントとビデオ・ストリーム内の１つまたは複数の以前のイベントとの間の１つまたは複数の第１相違度値を計算する。ステップ６０６は、１つまたは複数の計算された第１相違度値に基づいて、所与のイベントが新規イベントであるかどうかを判定する。

図７に、本発明のもう１つの実施形態によるオンライン新規イベント検出方法論を示す。この方法は、ＯＮＥＤシステム４００内で実施することができる。図示されているように、方法６１０は、は、ビデオ・ストリーミング環境内で以前に見られていないイベントを提示する新規イベント・ビデオ・クリップを取り込むリアル・タイム新規イベント検出プロセスである。この方法は、マルチステージ・シーケンシャル・フィルタリング・プロセスを含む。このプロセスは、関連する特徴を識別すること（ステップ６１２）と、特徴を導出するか抽出するための計算労力に基づいて特徴をランキングすること（ステップ６１４）と、ランキングされた特徴に基づいて１つまたは複数のマルチステージ・シーケンシャル・フィルタを形成することであって、より簡単に計算される特徴が、よりむずかしく計算される特徴の前に使用される、形成すること（ステップ６１６）とを含む。一特定の実施形態で、マルチステージ・シーケンシャル・フィルタリング・プロセスの１ステージは、新規イベントを検出するためにフィルタとしてテキスト特徴だけを使用することであり、後続ステージは、検出プロセスを補足するためにフィルタとしてイメージ特徴を使用することである。

最後に図９を参照すると、オンライン新規イベント検出の技法を本発明の実施形態に従って実施できるコンピュータ・システムが示されている。すなわち、図９は、本発明の実施形態による、それに従ってＯＮＥＤ技法の１つまたは複数のコンポーネント／ステップ（例えば、上で図１から７の文脈で説明したコンポーネントおよび方法論）を実施できるコンピュータ・システムを示す。個々のコンポーネント／ステップを、１つのそのようなコンピュータ・システム上で、または複数のそのようなコンピュータ・システム上で実施できることを理解されたい。分散コンピューティング・システム上での実施の場合に、個々のコンピュータ・システムまたはデバイスあるいはその両方を、適切なネットワーク、例えばインターネットまたはワールド・ワイド・ウェブを介して接続することができる。しかし、このシステムを、私設ネットワークまたはローカル・ネットワークを介して実現することができる。どの場合でも、本発明は、どの特定のネットワークにも限定されない。

したがって、図９に示されたコンピュータ・システムは、本明細書で説明する機能のすべてまたは一部を提供できる１つまたは複数のサーバあるいは１つまたは複数の他の処理デバイスを表すことができる。例えば、図９は、図２または図４のＯＮＥＤシステムのコンポーネントを実施するコンピュータ・アーキテクチャを表す。

図示されているように、コンピュータ・システム７００は、コンピュータ・バス７１０または代替接続配置を介して結合された、プロセッサ７０２、メモリ７０４、入出力（Ｉ／Ｏ）デバイス７０６、およびネットワーク・インターフェース７０８を含む。

本明細書で使用される用語「プロセッサ」が、例えばＣＰＵまたは他の処理回路あるいはその両方を含むものなど、任意の処理デバイスを含むことを意図されていることを了解されたい。また、単語「プロセッサ」が、複数の処理デバイスを指す場合があることと、処理デバイスに関連する様々な要素が他の処理デバイスによって共用される場合があることを理解されたい。

本明細書で使用される用語「メモリ」は、例えばＲＡＭ、ＲＯＭ、固定メモリ・デバイス（例えば、ハード・ドライブ）、取り外し可能メモリ・デバイス（例えば、ディスケット）、フラッシュ・メモリなど、プロセッサまたはＣＰＵに関連するメモリを含むことが意図されている。メモリは、コンピュータ可読記憶媒体と考えることができる。

さらに、本明細書で使用される句「入出力デバイス」または「Ｉ／Ｏデバイス」は、例えば、処理ユニットにデータを入力する１つもしくは複数の入力デバイス（例えば、キーボード、マウスなど）または処理ユニットに関連する結果を提示する１つもしくは複数の出力デバイス（例えば、ディスプレイなど）あるいはその両方を含むことが意図されている。

さらに、本明細書で使用される句「ネットワーク・インターフェース」は、例えば、コンピュータ・システムが適当な通信プロトコルを介して別のコンピュータ・システムと通信することを可能にする１つまたは複数のトランシーバを含むことが意図されている。

したがって、本明細書で説明する方法論を実行する命令またはコードを含むソフトウェア・コンポーネントを、関連するメモリ・デバイス（例えば、ＲＯＭ、固定メモリ、または取り外し可能メモリ）のうちの１つまたは複数に格納し、利用の準備ができたときに、部分的にまたは全体をロードし（例えば、ＲＡＭに）、ＣＰＵによって実行することができる。

どの場合でも、本明細書で説明し、添付図面に示した本発明の技法は、例えば、関連するメモリを伴う１つまたは複数の動作可能にプログラムされた汎用デジタル・コンピュータ、実施態様固有集積回路（１つまたは複数）、機能回路網など、様々な形のハードウェア、ソフトウェア、またはその組合せで実施することができる。本明細書で提供した本発明の技法を与えられれば、当業者は、本発明の技法の他の実施形態を企図することができるであろう。

本発明の例示的実施形態を、添付図面を参照して本明細書で説明したが、本発明が、これらの正確な実施形態に限定されず、様々な他の変更および修正を、当業者が本発明の範囲または趣旨から逸脱せずに行うことができることを理解されたい。

本発明の実施形態によるビデオ・データ・ストリーム内のイベントを示す図である。 本発明の実施形態によるオンライン新規イベント検出システムを示す図である。 本発明の実施形態による様々なビデオ・ストリーム類似度シナリオを示す図である。 本発明のもう１つの実施形態によるオンライン新規イベント検出システムを示す図である。 本発明の実施形態によるオンライン新規イベント検出方法論を示す図である。 本発明のもう１つの実施形態によるオンライン新規イベント検出方法論を示す図である。 本発明のもう１つの実施形態によるオンライン新規イベント検出方法論を示す図である。 本発明の実施形態によるスライディング時間ウィンドウを示す図である。 本発明の実施形態による、オンライン新規イベント検出の技法を実施できるコンピュータ・システムを示す図である。

符号の説明

１０２ イベント
１０４ イベント
１０６ イベント
１０８ イベント
１１０ イベント
１１２ イベント
２００ ベースラインＯＮＥＤシステム
２０１ 多言語ビデオ・チャネル
２０２ 特徴抽出モジュール
２０４ イメージ特徴抽出
２０６ 自動音声認識
２０８ 機械翻訳
２１０ ＯＮＥＤコンポーネント
２１２ コンシューマ
４００ ＯＮＥＤシステム
４０１ チャネル
４０２ テキスト特徴抽出モジュール
４０３ 音声認識
４０４ 機械翻訳
４０６ 非ニュース・ショット除去
４０８ イメージ特徴抽出
４１０ アンカ検出
４１２ ＯＮＥＤコンポーネント
４１４ コンシューマ
５００ アルゴリズム
６００ 方法
６１０ 方法
７００ コンピュータ・システム
７０２ プロセッサ
７０４ メモリ
７０６ 入出力（Ｉ／Ｏ）デバイス
７０８ ネットワーク・インターフェース
７１０ コンピュータ・バス

Claims (6)

1. 所与のイベントが複数のイベントを含むビデオ・ストリーム内の新規イベントであるかどうかを判定する方法であって、
   前記所与のイベントからテキスト特徴を含む第１集合を抽出するステップであって、特徴の前記第１集合は、前記所与のイベントに関連するイメージ特徴を含む第２集合と比較して、処理するのが計算的により安価であるステップと、
   １つまたは複数の第１相違度判断基準が存在するときに、特徴の前記第１集合だけを使用して、前記所与のイベントと前記ビデオ・ストリーム内の１つまたは複数の以前のイベントとの間の１つまたは複数の第１相違度値を計算するステップと、
   前記１つまたは複数の計算された第１相違度値に基づいて、前記所与のイベントが新規イベントであるかどうかを判定するステップと、
   前記所与のイベントから特徴の前記第２集合を抽出するステップと、
   １つまたは複数の第２相違度判断基準が存在するときに、特徴の前記第２集合を使用して、前記所与のイベントと前記ビデオ・ストリーム内の前記１つまたは複数の以前のイベントとの間の１つまたは複数の第２相違度値を計算するステップと、
   前記１つまたは複数の計算された第１相違度値および前記１つまたは複数の第２相違度値に基づいて、前記所与のイベントが新規イベントであるかどうかを判定するステップを含み、
   前記１つまたは複数の第１相違度値を計算する前に、前記所与のイベントと前記１つまたは複数の以前のイベントとの間の前記１つまたは複数の第１相違度値を計算するのに使用される前記以前のイベントをプレフィルタリングするステップをさらに含み、前記プレフィルタリングするステップは、前記所与のイベント内の単語と前記１つまたは複数の以前のイベント内の単語との間のオーバーラップの判定に基づく、
   方法。
2. 所与の時間ウィンドウ内の以前のイベントだけを含むために、前記所与のイベントと比較される１つまたは以前のイベントの個数を制限するステップをさらに含む、請求項１に記載の方法。
3. 前記複数のイベントのうちのどれが、前記所与のイベントが新規イベントであるかどうかの判定に使用されるのかを追跡するために１つまたは複数のインデックスを構築するステップをさらに含む、請求項１に記載の方法。
4. 前記１つまたは複数の第１相違度判断基準は、テキスト相違度しきい値が所与の値未満である、前記所与の値を超える、または前記所与の値と等しいことを含む、請求項１に記載の方法。
5. 前記１つまたは複数の第２相違度判断基準は、イメージ相違度しきい値が所与の値未満である、前記所与の値を超える、または前記所与の値と等しいことを含む、請求項１に記載の方法。
6. 所与のイベントが、複数のイベントを含むビデオ・ストリーム内の新規イベントであるかどうかを判定するプログラムであって、コンピュータによって実行されるときに請求項１に記載のステップを実行する１つまたは複数のプログラム・モジュールを含む、プログラム。

Images