(57)【要約】方法は、圧縮ビデオにおける動きアクティビティの強度を測定する。動きアクティビティの強度を用いて、ビデオを累積動きアクティビティの等しいセグメントに分割する。次に、各セグメントからキーフレームを選択する。選択されたキーフレームを時間順に連結して、ビデオの要約を形成する。
2004520760.tif 000002
【特許請求の範囲】
【請求項１】
圧縮ビデオを要約化する方法であって、
前記圧縮ビデオにおける累積動きアクティビティ強度を測定すること、
前記累積動きアクティビティ強度に従って前記圧縮ビデオからキーフレームを選択すること、
前記キーフレームを時間順に連結して、前記圧縮ビデオの要約を形成することを含む方法。
【請求項２】
前記圧縮ビデオを、各々が略等しい量の累積動きアクティビティ強度を有する複数のセグメントに分割すること、
各セグメントから１つのキーフレームを選択すること
をさらに含む請求項１に記載の方法。
【請求項３】
前記セグメントの数は、前記要約における所望のキーフレーム数よりも少ない数である請求項１に記載の方法。
【請求項４】
各セグメントの１番目のフレームを前記要約の前記キーフレームの１つとして選択すること、
前記圧縮ビデオの最後のフレームを前記要約の最後のキーフレームとして選択すること
をさらに含む請求項３に記載の方法。
【請求項５】
各セグメントの累積動きアクティビティ強度に従って中央のフレームを前記キーフレームの１つとして選択することをさらに含む請求項２に記載の方法。
【請求項６】
前記動きアクティビティ強度は、動きベクトルの平均の大きさから測定される請求項１に記載の方法。
【請求項７】
前記動きアクティビティ強度は、動きベクトルの中央の大きさから測定される請求項１に記載の方法。
【請求項８】
前記動きアクティビティ強度は、動きベクトルの大きさの標準偏差から測定される請求項１に記載の方法。
【請求項９】
前記圧縮ビデオを、ショット境界に従って複数のセグメントに分割すること、
各セグメントにおける累積動きアクティビティ強度を測定すること、
前記累積動きアクティビティ強度に従って各セグメントから前記キーフレームを選択すること、
前記キーフレームを時間順に連結して、前記圧縮ビデオの要約を形成することをさらに含む請求項１に記載の方法。
【請求項１０】
２分割（ｂｉｎａｒｙ ｐａｒｔｉｔｉｏｎｉｎｇ）を用いて前記圧縮ビデオを、前記累積動きアクティビティ強度に基づき複数のセグメントに分割することであって、第１の分割は、ビデオ全体を含む１つのセグメントを生成し、第２の分割は、各々が略等しい量の累積動きアクティビティ強度を有する２つのセグメントを生成し、その後の各分割は、所定数のセグメントが生成されるまで、前の分割のセグメントを前記累積動きアクティビティ強度に基づき２等分すること、
前記累積動きアクティビティ強度に従って各セグメントから中央のフレームを前記キーフレームの１つとして選択すること、
前記キーフレームを時間順に連結して、前記圧縮ビデオの要約を形成することをさらに含む請求項１に記載の方法。
【請求項１１】
圧縮ビデオのプログレッシブな（ｐｒｏｇｒｅｓｓｉｖｅ）要約を生成する方法であって、
終了条件に達するまで前記圧縮ビデオからプログレッシブな順序付けでキーフレームを選択すること、
前記キーフレームを時間順で連結して、前記圧縮ビデオの前記プログレッシブな要約を形成すること
を含み、前記プログレッシブな順序付けは、
前記圧縮ビデオの１番目のフレームを第１のキーフレームとして選択すること、
前記圧縮ビデオの最後のフレームを第２のフレームとして選択すること、
前記圧縮ビデオにおける累積動きアクティビティ強度を測定し、該累積動きアクティビティ強度に従って前記圧縮ビデオから中央のフレームを第３のキーフレームとして選択すること、
前記動きアクティビティ強度に従って前記圧縮ビデオを２つの等しいセグメントに分割し、各セグメントの累積動きアクティビティ強度に従って中央のフレームを第４のキーフレームおよび第５のキーフレームとして選択すること、
前に分割した各セグメントを前記動きアクティビティ強度に従って２つの小さな大きさの等しいセグメントに繰り返し分割し、前記終了条件に達するまで、大きさの小さい各セグメントから前記累積動きアクティビティ強度に従ってさらなる中央のフレームを次の２つのキーフレームとして選択すること
を含む方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は包括的にはビデオに関し、特に、圧縮ビデオの要約化に関する。
【０００２】
【従来の技術】
ビデオの要約を自動的に生成すること、特に圧縮デジタルビデオの要約を生成することが望ましい。
【０００３】
圧縮ビデオフォーマット
ビデオをデジタル信号として圧縮する標準的な規格が、ＭＰＥＧ（Ｍｏｔｉｏｎ Ｐｉｃｔｕｒｅ Ｅｘｐｅｒｔ Ｇｒｏｕｐ）に採用されている。ＭＰＥＧ規格は、画像のフルフレームについての情報を時折にのみ作成することで、高いデータ圧縮率を達成する。フル画像フレーム、すなわちフレーム内符号化フレームは「Ｉフレーム」または「アンカーフレーム」と呼ばれることが多く、あらゆる他のフレームとは独立したフルフレーム情報を含む。画像差フレーム、すなわちフレーム間符号化フレームは、「Ｂフレーム」および「Ｐフレーム」、または「予測フレーム」と呼ばれることが多く、これは、Ｉフレーム間で符号化され、基準フレームからの画像差、すなわち残余のみを反映する。
【０００４】
通常、ビデオシーケンスの各フレームは、より小さな、画素、すなわちピクセルデータのブロックに分割される。各ブロックは離散コサイン変換（ＤＣＴ）関数を施され、統計上依存した空間領域ピクセルを独立周波数領域ＤＣＴ係数に変換する。「マクロブロック」と呼ばれる、それぞれの８×８、または１６×１６のピクセルのブロックは、ＤＣＴ関数を施されて、符号化信号を提供する。
【０００５】
ＤＣＴ係数は通常エネルギー集中的であるため、１つのマクロブロックにおいて少数の係数のみが、ピクチャ情報の主要部分を含む。たとえば、マクロブロックがオブジェクトのエッジ境界を含む場合、そのブロックのエネルギーは係数のマトリクスにわたって、比較的大きなＤＣ係数と、ランダムに分布するＡＣ係数とを含む。
【０００６】
一方、非エッジマクロブロックは通常、同様に大きなＤＣ係数と、そのブロックに関連する他の係数よりも実質的に大きな少数の隣接ＡＣ係数とを特徴とする。ＤＣＴ係数は通常、適応量子化を施されてから、ランレングス符号化および可変長符号化される。このため、送信データのマクロブロックは通常、８×８のマトリクスに満たない符号語を含む。
【０００７】
フレーム内符号化フレームデータ、すなわち符号化ＰまたはＢフレームデータのマクロブロックは、予測ピクセルとマクロブロックにおける実際のピクセルとの間の差分のみを表すＤＣＴ係数を含む。フレーム内符号化フレームデータおよびフレーム間符号化フレームデータのマクロブロックはまた、用いられた量子化のレベル、マクロブロックのアドレスインジケータまたはロケーションインジケータ、ならびにマクロブロックのタイプ等の情報も含む。後者の情報は、「ヘッダ」または「オーバーヘッド」情報と呼ばれることが多い。
【０００８】
各Ｐフレームは、最後のＩフレームまたはＰフレームから予測される。各Ｂフレームは、これを挟むＩフレームまたはＰフレームから予測される。予測符号化プロセスは、Ｉフレームのどのマクロブロックの変位量が現在符号化されているＢフレームまたはＰフレームのマクロブロックと最も密接にマッチしているかを示す、「動きベクトル」としばしば呼ばれる変位ベクトルの生成を含む。Ｉフレームにおけるマッチするブロックのピクセルデータが、符号化されているＰフレームまたはＢフレームのブロックからピクセル毎に減じられ、残余が現れる。変換された残余およびベクトルは、ＰフレームまたはＢフレームの符号化データの一部を形成する。
【０００９】
ビデオ分析
ビデオ分析は、ビデオコンテンツの理解を意図してのビデオ処理として定義することができる。ビデオの理解は、「低レベル」の統語論的理解（ビデオ中のセグメント境界の検出など）から「高レベル」の意味論的理解（ビデオのジャンルの検出など）までと様々であり得る。低レベルの理解は、カラー、動き、テクスチャ、形状等、低レベルの特徴を分析してコンテンツ記述を生成することでなされる。次にこのコンテンツ記述を用いて、ビデオを索引付けすることができる。
【００１０】
ビデオ要約化
ビデオ要約化は、ビデオの意味論的本質を伝えるビデオのコンパクトな表現を作成する。コンパクトな表現には、「キーフレーム」または「キーセグメント」、あるいはキーフレームとセグメントの組み合わせを含めることができる。一例として、テニスの試合のビデオ要約は、２つのフレーム、すなわち双方の選手を取り込んだ第１のフレームと、トロフィーを持った勝者を取り込んだ第２のフレームと、を含み得る。より詳細かつ長い要約には、マッチポイントを取り込んだすべてのフレームをさらに含めることができる。このような要約を手動で生成することは確かに可能であるが、これには時間と費用がかかる。したがって、自動要約化が望まれる。
【００１１】
自動ビデオ要約化方法は周知である。Ｓ． Ｐｆｅｉｆｅｒ他著「Ａｂｓｔｒａｃｔｉｎｇ Ｄｉｇｉｔａｌ Ｍｏｖｉｅｓ Ａｕｔｏｍａｔｉｃａｌｌｙ」（Ｊ． Ｖｉｓｕａｌ Ｃｏｍｍ． Ｉｍａｇｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ， ｖｏｌ． ７， ｎｏ． ４， ｐｐ． ３４５−３５３， Ｄｅｃｅｍｂｅｒ １９９６）およびＨａｎｊａｌｉｃ他著「Ａｎ Ｉｎｔｅｇｒａｔｅｄ Ｓｃｈｅｍｅ ｆｏｒ Ａｕｔｏｍａｔｅｄ Ｖｉｄｅｏ Ａｂｓｔｒａｃｔｉｏｎ Ｂａｓｅｄ ｏｎ Ｕｎｓｕｐｅｒｖｉｓｅｄ Ｃｌｕｓｔｅｒ − Ｖａｌｉｄｉｔｙ Ａｎａｌｙｓｉｓ」（ＩＥＥＥ Ｔｒａｎｓ． Ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｏｌｏｇｙ， Ｖｏｌ． ９， Ｎｏ． ８， Ｄｅｃｅｍｂｅｒ １９９９）を参照されたい。
【００１２】
ほとんどの従来のビデオ要約化方法は、専らカラーベースの要約化に集中している。Ｐｆｅｉｆｆｅｒ他だけが、ビデオ要約の作成に、動きを他の特徴と組み合わせて用いている。しかし、Ｐｆｅｉｆｆｅｒ他による方法は単に、組み合わせた特徴間の考え得る相関を見過ごした重み付き組み合わせを用いるだけにすぎない。要約化方法によっては、動き特徴を用いてキーフレームを抽出するものもある。
【００１３】
図１に示すように、従来技術によるビデオ要約化方法はほとんど、カラー特徴に基づくクラスタ化を強調している。これは、カラー特徴が圧縮領域において抽出し易くかつノイズに耐性があるためである。典型的な方法は、ビデオシーケンスＡ１０１を入力としてとり、カラーベースの要約化プロセス１００を適用してビデオ要約Ｓ（Ａ）１０２を作成する。ビデオ要約は、シーケンス全体の要約、あるいはシーケンスの関心を引くセグメント、すなわちキーフレームのセットのいずれかを含む。
【００１４】
方法１００は通常、以下のステップを含む。第１に、カラー特徴に従いビデオのフレームをクラスタ化する。第２に、クラスタをアクセスし易い階層データ構造にする。第３に、各クラスタからキーフレームまたはキーシーケンスを抽出して、要約を生成する。
【００１５】
動きアクティビティ記述子
ビデオはまた、様々なレベルのアクティビティ、すなわちアクション強度を有するものとして直観的に理解することができる。比較的高レベルのアクティビティの例は、スポーツビデオでの得点チャンスである。一方、ニュースビデオは比較的低レベルのアクティビティを有する。最近提案されたＭＰＥＧ−７映像規格は、ビデオ中の動きアクティビティに関連する記述子を提供する。
【００１６】
動きアクティビティの１つの尺度には、動きベクトルの大きさの平均および分散がある。Ｐｅｋｅｒ他著「Ａｕｔｏｍａｔｉｃ ｍｅａｓｕｒｅｍｅｎｔ ｏｆ ｉｎｔｅｎｓｉｔｙ ｏｆ ｍｏｔｉｏｎ ａｃｔｉｖｉｔｙ」（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＳＰＩＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｔｏｒａｇｅ ａｎｄ Ｒｅｔｒｉｅｖａｌ ｆｏｒ Ｍｅｄｉａ Ｄａｔａｂａｓｅｓ， Ｊａｎｕａｒｙ ２００１）を参照されたい。しかしながら、用途に応じて多くの変形が可能である。
【００１７】
キーフレームのセットの忠実度
単一のキーフレームを見つける最も簡単な方法は、シーケンスから任意のフレームを選択することであるが、単一のキーフレームをベースとする方法は、ビデオのコンテンツが単一のフレームで伝え得るよりも多くの情報を有する場合に機能しない。ビデオセグメントの１番目のフレームを第１のキーフレームとして割り当て、次に、特徴空間において１番目のフレームから最も遠く離れたフレームを第２のキーフレームとして割り当てることができる。Ｍ．Ｍ． Ｙｅｕｎｇ ａｎｄ Ｂ． Ｌｉｕ著「Ｅｆｆｉｃｉｅｎｔ Ｍａｔｃｈｉｎｇ ａｎｄ Ｃｌｕｓｔｅｒｉｎｇ ｏｆ Ｖｉｄｅｏ Ｓｈｏｔｓ」（Ｐｒｏｃ． ＩＥＥＥ ＩＣＩＰ， Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．， １９９５）を参照されたい。他の多数のキーフレーム生成手法、およびキーフレームのセットの忠実度の尺度に基づくキーフレーム生成手法が、Ｈ．Ｓ． Ｃｈａｎｇ， Ｓ． Ｓｕｌｌ ａｎｄ Ｓ．Ｕ． Ｌｅｅ著「Ｅｆｆｉｃｉｅｎｔ ｖｉｄｅｏ ｉｎｄｅｘｉｎｇ ｓｃｈｅｍｅ ｆｏｒ ｃｏｎｔｅｎｔ−ｂａｓｅｄ ｒｅｔｒｉｅｖａｌ」（ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｏｌｏｇｙ， Ｖｏｌ． ９， Ｎｏ． ８， １９９９）により記載される。忠実度の尺度は、ビデオシーケンスにおけるキーフレームのセットＳと、フレームのセットＲとの間の半ハウスドルフ（Ｓｅｍｉ−Ｈａｕｓｄｏｒｆｆ）距離（ｄｈｓ）として定義される。半ハウスドルフ距離の実際的な定義は以下の通りである。
【００１８】
セットＳｉがｉ＝１、．．．、ｍの場合にｍ個のフレームを含み、フレームのセットＲｉがｌ＝１、．．．、ｎの場合にｎ個のフレームを含むものとする。２つのフレームＳｉおよびＲｉ間の距離をｄ（Ｓｉ，Ｒｉ）とする。各フレームＲｉのｄｉを以下の通り定義する。
ｄｉ＝ｍｉｎ（ｄ（Ｓｋ，Ｒｉ））、ｋ＝０．．ｍ
すると、ＳとＲの間の半ハウスドルフ距離は以下の式で与えられる。
ｄｓｈ（Ｓ，Ｒ）＝ｍａｘ（ｄｉ）、ｉ＝１．．ｎ
【００１９】
換言すると、まずすべてのｉについて、フレームＲｉと、これをキーフレームのセットＳにおいて最もよく表現するものとの間の距離ｄｉを測定する。次に、上で計算した距離ｄｉの最大値を求める。この距離は、キーフレームのセットＳがどれほど良好にＲを表現するかを表す。表現が良好であるほど、ＳとＲの間の半ハウスドルフ距離は小さくなる。たとえば自明な場合において、セットＳおよびＲが同一である場合、半ハウスドルフ距離はゼロである。一方、距離が大きければ、Ｒのフレームの少なくとも１つが、キーフレームのセットＳのどのフレームにも良好に表現されなかったことを示す。
【００２０】
ほとんどの既存の相違度の尺度は、上記定義に用いられる距離空間上の距離に必要な特性を満たす。Ｍ．Ｊ． Ｓｗａｉｎ ａｎｄ Ｄ．Ｈ． Ｂａｌｌａｒｄ著「Ｃｏｌｏｒ ｉｎｄｅｘｉｎｇ」（Ｊ． Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， ｖｏｌ． ７， ｎｏ． １， ｐｐ． １１−３２， １９９１）により記載される、以下の通り定義されるカラーヒストグラム交差距離（ｉｎｔｅｒｓｅｃｔｉｏｎ ｍｅｔｒｉｃ）を用いることもできる。
【００２１】
Ｍ×Ｎサイズの２つの画像ｆｉおよびｆｉのＫビンカラーヒストグラムがＨｉおよびＨｊである場合、この２つの画像間の相違度は以下の式で与えられる。
【００２２】
【数１】
2004520760.tif 000003
【００２３】
相違度は、範囲［０，１］内であることに留意されたい。
【００２４】
【発明が解決しようとする課題】
本発明の目的は、動き特徴、特に動きアクティビティ特徴を単独で、また、カラーおよびテクスチャの特徴等、他の低レベルの特徴と組み合わせて用いて自動ビデオ要約化方法を提供することである。
【００２５】
【課題を解決するための手段】
本発明は以下の考えに基づく。ビデオの動きアクティビティは、ビデオの要約化の相対的な困難さを示すのによい目安である。動きの量が多くなるほど、そのビデオの要約化は困難である。ビデオ要約は、包含するフレームの数、たとえばキーフレームの数、またはキーセグメントのフレームの数等により、量的に記述することができる。
【００２６】
ビデオの動きアクティビティの相対強度は、カラー特徴の変化と強く関係付けられている。換言すれば、動きアクティビティの強度が高い場合、カラー特徴の変化も高い可能性が高い。カラー特徴の変化が高い場合、カラー特徴をベースとする要約には比較的多数のフレームが含まれることになり、カラー特徴の変化が低い場合には、要約にはより少数のフレームが含まれることになる。これは別の言い方をすれば、ビデオから選択されたキーフレームからなる視覚的な要約の忠実度を考慮することである。キーフレームの数を一定に保つことにより要約の長さを一定にしておけば、ショットの動きアクティビティの強度はより高く、その要約の忠実度はより低くなる。
【００２７】
たとえば、「トーキングヘッド（ｔａｌｋｉｎｇ ｈｅａｄ）」ビデオでは通常、動きアクティビティのレベルが低く、また同様にカラー変化もごくわずかである。要約化がキーフレームをベースとする場合、ビデオの要約化には１つのキーフレームで十分である。キーセグメントを用いる場合、視覚的なビデオの要約化には、１秒のフレームシーケンスで十分である。一方、スポーツイベントでの得点チャンスでは動きアクティビティ強度およびカラー変化が非常に高く、したがって要約化には数個のキーフレームすなわち数秒が必要である。
【００２８】
より詳細には、本発明は、まず圧縮ビデオ中の動きアクティビティの強度を測定することで、ビデオの要約化をする方法を提供する。次に、当該動きアクティビティの強度を用いて、長時間のカラーベースの計算を行うことなくビデオからキーフレームを選択する。
【００２９】
本発明はまた、要約化が容易なセグメントでは動きベースの方法を用い、要約化が困難なセグメントではカラーベースの方法を用いることによって、動きベースのキーフレーム抽出とカラーベースのキーフレーム抽出とを組み合わせる方法を提供する。要約化が容易なセグメントは、１つまたは複数のキーフレームからなる迅速に抽出した要約で表され、一方、要約化が困難な各セグメントからは、カラーベースの要約化プロセスがフレームシーケンスを抽出する。単一フレームおよび抽出したフレームシーケンスを時間順に連結して、ビデオの要約を形成する。
【００３０】
より詳細には、本発明による方法は、圧縮ビデオ中の動きアクティビティの強度を測定する。動きアクティビティの強度は、ビデオを累積動きアクティビティの等しいセグメントに分割するために用いられる。次に各セグメントからキーフレームを選択する。選択されたキーフレームは時間順に連結されて、ビデオの要約を形成する。一実施形態では、各セグメントの１番目のフレームと、シーケンスの最後のフレームとが選択されて、要約を形成する。別の実施形態では、動きアクティビティに関して中央のフレームが各セグメントから選択され、分割は、累積動きアクティビティー強度を基にした２分割である。
【００３１】
【発明の実施の形態】
本発明は、動き特徴を、またオプションでカラー特徴を用いて、圧縮ビデオを要約化する。したがって、本発明の要約化方法は最初に、これらの特徴を圧縮ビデオから測定する。
【００３２】
特徴抽出
カラー特徴
既知の手法を用いて、ＩフレームのＤＣ係数を正確に抽出することができる。ＰおよびＢのフレームの場合、ＤＣ係数は、完全に圧縮解除することなく動きベクトルを用いて近似することができる。たとえば、Ｙｅｏ他著「Ｏｎ ｔｈｅ Ｅｘｔｒａｃｔｉｏｎ ｏｆ ＤＣ Ｓｅｑｕｅｎｃｅ ｆｒｏｍ ＭＰＥＧ ｖｉｄｅｏ」（ＩＥＥＥ ＩＣＩＰ Ｖｏｌ． ２， １９９５）を参照されたい。ＤＣ画像のＹＵＶ値は、カラー特徴を抽出するために、別の色空間に変換することができる。
【００３３】
最も一般に使用される手法では、カラーヒストグラムを用いる。カラーヒストグラムは、画像および映像の索引付けおよび検索に広く用いられてきている。Ｓｍｉｔｈ他著「Ａｕｔｏｍａｔｅｄ Ｉｍａｇｅ Ｒｅｔｒｉｅｖａｌ Ｕｓｉｎｇ Ｃｏｌｏｒ ａｎｄ Ｔｅｘｔｕｒｅ」（ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９６）を参照されたい。通常、３チャネルＲＧＢ色空間では、各チャネルに４つのビンがあり、カラーヒストグラムには総計６４（４×４×４）個のビンが必要である。
【００３４】
動き特徴
動き情報は、ＰフレームおよびＢフレームの動きベクトルから抽出および測定することができる。動きベクトルは通常、実際のオプティカルフローに対する荒く、散在した近似であるため、ここでは動きベクトルを定性的にのみ用いる。動きベクトルを抽出する多くの異なる方法が記載されている。Ｔａｎ他著「Ａ ｎｅｗ ｍｅｔｈｏｄ ｆｏｒ ｃａｍｅｒａ ｍｏｔｉｏｎ ｐａｒａｍｅｔｅｒ ｅｓｔｉｍａｔｉｏｎ」（Ｐｒｏｃ． ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， Ｖｏｌ． ２， ｐｐ． ７２２−７２６， １９９５）、Ｔａｎ他著「Ｒａｐｉｄ ｅｓｔｉｍａｔｉｏｎ ｏｆ ｃａｍｅｒａ ｍｏｔｉｏｎ ｆｒｏｍ ｃｏｍｐｒｅｓｓｅｄ ｖｉｄｅｏ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｖｉｄｅｏ ａｎｎｏｔａｔｉｏｎ」（ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｏｌｏｇｙ， １９９９）、Ｋｏｂｌａ他著「Ｄｅｔｅｃｔｉｏｎ ｏｆ ｓｌｏｗ−ｍｏｔｉｏｎ ｒｅｐｌａｙ ｓｅｑｕｅｎｃｅｓ ｆｏｒ ｉｄｅｎｔｉｆｙｉｎｇ ｓｐｏｒｔｓ ｖｉｄｅｏｓ」（Ｐｒｏｃ． ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ｍｕｌｔｉｍｅｄｉａ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ， １９９９）、Ｋｏｂｌａ他著「Ｓｐｅｃｉａｌ ｅｆｆｅｃｔ ｅｄｉｔ ｄｅｔｅｃｔｉｏｎ ｕｓｉｎｇ ＶｉｄｅｏＴｒａｉｌｓ： ａ ｃｏｍｐａｒｉｓｏｎ ｗｉｔｈ ｅｘｉｓｔｉｎｇ ｔｅｃｈｎｉｑｕｅｓ」（Ｐｒｏｃ． ＳＰＩＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｔｏｒａｇｅ ａｎｄ Ｒｅｔｒｉｅｖａｌ ｆｏｒ Ｉｍａｇｅ ａｎｄ Ｖｉｄｅｏ Ｄａｔａｂａｓｅｓ ＶＩＩ， １９９９）、Ｋｏｂｌａ他著「Ｃｏｍｐｒｅｓｓｅｄ ｄｏｍａｉｎ ｖｉｄｅｏ ｉｎｄｅｘｉｎｇ ｔｅｃｈｎｉｑｕｅｓ ｕｓｉｎｇ ＤＣＴ ａｎｄ ｍｏｔｉｏｎ ｖｅｃｔｏｒ ｉｎｆｏｒｍａｔｉｏｎ ｉｎ ＭＰＥＧ ｖｉｄｅｏ」（Ｐｒｏｃ． ＳＰＩＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｔｏｒａｇｅ ａｎｄ Ｒｅｔｒｉｅｖａｌ ｆｏｒ Ｉｍａｇｅ ａｎｄ Ｖｉｄｅｏ Ｄａｔａｂａｓｅｓ Ｖ， ＳＰＩＥ Ｖｏｌ． ３０２２， ｐｐ． ２００−２１１， １９９７）、およびＭｅｎｇ他著「ＣＶＥＰＳ − ａ ｃｏｍｐｒｅｓｓｅｄ ｖｉｄｅｏ ｅｄｉｔｉｎｇ ａｎｄ ｐａｒｓｉｎｇ ｓｙｓｔｅｍ」（Ｐｒｏｃ． ＡＣＭ Ｍｕｌｔｉｍｅｄｉａ ９６， １９９６）を参照されたい。
【００３５】
上述したように、ほとんどの従来技術による要約化方法は、カラー特徴のクラスタ化をベースとして、カラー記述子を得る。カラー記述子は、定義上比較的ノイズに耐性があるが、ビデオの動き特徴を含まない。しかし、動き記述子はノイズに対する耐性がより低い傾向があるため、ビデオの要約化に広くは用いられていない。
【００３６】
Ｄｉｖａｋａｒａｎ他出願の米国特許出願第０９／４０６，４４４号「Ａｃｔｉｖｉｔｙ Ｄｅｓｃｒｉｐｔｏｒ ｆｏｒ Ｖｉｄｅｏ Ｓｅｑｕｅｎｃｅｓ」（２０００年８月９日提出、参照により本明細書中に援用）は、圧縮ビデオにおける動きベクトルから導出した動き特徴を用いて、ビデオにおける動きアクティビティおよびビデオにおける動きアクティビティの空間分布を決定する方法を記載している。このような記述子は、上記特許出願に記載されるように、ビデオ閲覧用途に関しては有用である。本明細書では、このような動き記述子を新規のビデオ要約化に適用する。
【００３７】
本明細書では動きを、ビデオシーンがどれほど変化しているかを示す強力な指示器であると考える。したがって、ビデオシーンの「要約化可能性（ｓｕｍｍａｒｉｚａｂｉｌｉｔｙ）」の尺度として動きを用いることにする。例として高速のカーチェイスは、たとえばニュースキャスターのショットと比較した場合に、より多くの「変化」を含むことだろう。したがって、高速のカーチェイスは、視覚的な要約化のためにニュースキャスターのショットよりも多くの資源を要することになる。
【００３８】
不都合なことに、動きが実際にシーンの変化に関連するのかどうかをテストする単純で客観的な尺度はない。しかし、シーンの変化はカラー特徴の変化も伴うことが多いため、上記で定義したカラーベースの忠実度と動きアクティビティの強度との間の関係を調べる。
【００３９】
ショットＡのキーフレームのセットをＳＡ、ショットＢのキーフレームのセットをセットＳＢとする。セットＳＡとセットＳＢの両方が同数のキーフレームを含み、ショットＡの動きアクティビティの強度がショットＢの動きアクティビティの強度よりも大きい場合、セットＳＡの忠実度はセットＳＢの忠実度よりも低い。換言すれば、ショットＡは、その動きアクティビティの強度がより高いため、ショットＢよりも「要約化可能性」が低くなっている。
【００４０】
動きアクティビティの強度が要約化可能性を獲得することの証明
ＭＰＥＧ−１フォーマットのＭＰＥＧ−７テストセットから、標準的なニュースビデオ番組のカラー特徴および動き特徴を抽出する。始めに、番組を複数のショットに区分化する。次に各ショットについて、各Ｐフレームの動きベクトルの大きさの標準偏差を計算することですべてのＰフレームから動きアクティビティ特徴を抽出するとともに、すべてのＩフレームから６４ビンＲＧＢヒストグラムを抽出する。これらはともに、圧縮領域にある。
【００４１】
次に、Ｐフレームのグループにおける以前のＰフレームの動きアクティビティ記述子を平均することにより、各Ｉフレームについて動きアクティビティ記述子を決定する。したがってＩフレームにはすべて、ヒストグラムと、動きアクティビティ値とが関連付けられる。ショット全体の動きアクティビティは、上で計算した個々の動きアクティビティ値を平均することによって得られる。以下、ショット中のＩフレームのセットを、上記で定義したようなフレームのセットＲとして扱う。動きアクティビティは、動きベクトルの平均の大きさを基にすることができる。
【００４２】
単純な要約化方法はショットの単一のキーフレームを、上述のように、当該ショットの１番目のフレームを用いて生成する。したがって、１番目のＩフレームをキーフレームとして使用し、その忠実度を上述のように判定する。「トーキングヘッド」シーケンスの例を分析することにより、高くても０．２の忠実度を有するキーフレームが十分な品質のものであることを経験的に判断する。したがって、ショットを２つのカテゴリー、すなわち、キーフレームが０．２以下のｄｓｈを有する（キーフレームが許容可能な忠実度を有する）第１のカテゴリーと、キーフレームが０．２より大きいｄｓｈを有する（キーフレームが許容不可能な忠実度を有する）第２のカテゴリーとに分類することができる。
【００４３】
ショットはまた、表Ａに示すように、アクティビティが非常に低いものから非常に高いものまで５つのカテゴリーに分類することができる。
【００４４】
【表１】
2004520760.tif 000004
【００４５】
次に、図２に示すように、標準的なニュース番組のビデオ（スペインのニュース）に関し、これらのカテゴリー２０２のそれぞれにおいて、０．２よりも大きいｄｓｈを有するショットの継続時間（ｄｕｒａｔｉｏｎ）を割合２０１として判定する。動きアクティビティが非常に低から非常に高へ増加するに従い、ｄｓｈの値も一貫して増加する。換言すれば、ショットの動きアクティビティが増加するに従い、その要約化可能性の容易さは減少する。
【００４６】
さらに、単一のキーフレームの忠実度は、動きアクティビティ強度が非常に低いカテゴリーのショットの９０％について許容可能である。他のニュース番組（ＭＰＥＧ−７テストセットからのポルトガルのニュース番組など）ならびにＮＢＣのニュース番組からとったニュース番組で同一のパターンを観察することができる。したがって実験的証拠は、ニュース番組ではショットの動きアクティビティ強度がその要約化可能性の直接的な目安であることを示す。
【００４７】
ニュース番組はコンテンツが様々であるので、この結果は広範囲のコンテンツに当てはまると思われる。動きアクティビティにＭＰＥＧ−７の閾値を用いるため、この結果はコンテンツに左右されない。
【００４８】
図３は、閾値Ｔ以下の動きアクティビティ強度を有するショットにおける許容不可能な忠実度を有するショットの継続時間の割合３０１と、これに対して、Ｔ以下の動きアクティビティを有する番組中のショットの継続時間の全割合３０２とを示す。このプロットは、スペインのニュース番組に関して、ショットの１番目のフレームを、ショットの３０％について許容可能な忠実度のキーフレームとして用いることができることを示す。他のニュース番組についても同様の結果が得られる。したがって、アクションが非常に低いショットでは、ＭＰＥＧ−７の動きアクティビティ閾値を用いて、ショットが１番目のフレームによって良好に要約化されるかを見い出すことができる。
【００４９】
要約化方法
上記の結果は、動きアクティビティが増加する（ｉｎｃｒｅｍｅｎｔ）毎に情報が増加することを示す。したがって、ビデオのキーフレームは、連続するキーフレーム間の累積動きアクティビティの差が均一であるようにサンプリングすることができる。すると、各キーフレームは、前のキーフレームと同一の情報増加を提供する。
【００５０】
したがって、図４に示すように、まず入力ビデオシーケンス４０１における累積動きアクティビティの強度を測定する（４１０）。累積強度とは、（正規化した）累積がビデオの始まりで０．０、終わりで１．０、どこか中間の位置で０．５であることを意味する。ビデオを動きアクティビティに従って「中央」で分割し、ビデオの第１の部分の動きレベルが非常に高い場合、この第１の部分は、第２の部分よりずっと少ないフレームを有することになる。この反対は、アクティビティのほとんどがビデオの後半にある場合になる。たとえば、アクティビティの半分が１時間のビデオの最後の６分（１０％）に起こる場合、累積動き（０．５）の動きの「中央」は、完全なビデオが毎秒３０フレームで１０８，０００個のフレームを有する場合にフレーム１０８，０００〜１０，８００にあることになる。換言すれば、動きアクティビティは本質的に、ビデオフレーム上のタイムワープである。アクティビティレベルが高い間、動きを累積するために必要なフレーム数は、アクティビティレベルが低い間よりも少ない。また実際、ビデオの動きがない部分（たとえば「静止」ショット）では、動きの累積は全くない。
【００５１】
次に、ビデオシーケンスをｎ−１個のセグメントに分割する（４２０）。本発明の分割における各セグメントは、略等しい量の累積動きアクティビティ強度を有する。なお、第１のセグメント４２１のフレーム数は多いが、累積動きの量はフレーム数の少ない第２のセグメント４２２と同じである。次に、各セグメントの１番目のフレームと、シーケンスの最後のフレームとを選択して、ｎ個のキーセグメントを得る。次に、セグメントを時間順に連結して要約を形成する。たとえば３つのキーフレーム４０９を得るために、シーケンスを、それぞれがシーケンス全体の累積動きアクティビティの半分に相当する累積動きアクティビティを有する２つのセグメント４２１〜４２２に分割する。次に、第１および第２のセグメントの１番目のフレームと、シーケンスの最後のフレームとを選択する。
【００５２】
単一のキーフレームのみを選択する場合、累積動きアクティビティスケールの中間位置にあるキーフレームが最良であろう。したがって、ｎ個のキーフレームを得るための最適な方策は、まずビデオを累積動きアクティビティの等しいｎ個のセグメントに分割し、次に各セグメントについて、累積動きアクティビティスケールの中間位置にあるフレームをキーフレームとして選択することである。すると最終的なキーフレームのセットは、上述のように得たセグメントの各々のキーフレームからなる。この方法が最も良く機能することが分かった。図５は、１番目のフレームを選択した場合（上の曲線）と、これに対して中央のフレームを選択した場合（下の曲線）とで得られた結果を、非常に低、低、中、および高レベルのアクティビティ５０１〜５０４について比較する。すべての場合において、中央のフレームを選択すると、わずかに良い結果が得られる。
【００５３】
換言すれば、動きアクティビティの強度に基づきビデオの非均一なサブサンプリングを行う。たとえば、ビデオ中の全アクションがビデオの前半に起こる場合、キーフレームはすべてビデオの前半から引き出されることを保証する。これは、アクティビティベースの時間軸ワーピング、およびこれに続く、ワープした時間軸上での均一なサンプリングとして解釈することもできる。これは、カラーの比較を全く必要としないため、非常に高速な手順であることに留意されたい。
【００５４】
この方法は最適であるものの、プログレッシブ（ｐｒｏｇｒｅｓｓｉｖｅ）でないという欠点がある。たとえば、最適な単一のキーフレームは、累積動きアクティビティがシーケンス全体の累積動きアクティビティの半分であるフレームである。しかしながら、選択されるキーフレームのペアは、累積動きアクティビティがセグメント全体の累積動きアクティビティの１／４であるフレームと３／４であるフレームとからなる。したがって、最適なキーフレームのペアには、最適な単一のキーフレームと共通のフレームがない。これは、数ｎのキーフレーム毎に、より低い数（たとえばｎ−１）のキーフレームについて得られた結果を活用できないことを意味する。したがって、上記の最適な手法のプログレッシブ近似を以下のように用いる。
【００５５】
１番目のフレームと最後のフレームから始めて、ビデオシーケンスの半分をそれぞれ、累積動きアクティビティが等しい部分に繰り返し分けて、１、３、５、９といった個数の最適なキーフレームを得る。任意の他の数（たとえば３）のべき乗を用いることもできる。しかしながら、デジタルコンピュータでは２のべき乗が計算し易い。
【００５６】
上記の方法を用いれば、閾値数のフレームが選択されるまで、いかなる数のキーフレームも選択可能であることに留意されたい。閾値は手動で、または対話型アプリケーションにより、あるいは表１に記載したＭＰＥＧ−７強度カテゴリ毎にキーフレームの数の固定テーブルを設けることによって決定することができる。たとえば、ほとんどのニュースビデオなら、５つのキーフレームで十分である。中、高および非常に高のカテゴリーのビデオでは、５つよりも多くのキーフレームが必要であり得る。
【００５７】
上述の方法は、サイズおよびアクティビティの大きい、動きのある領域（ｍｏｖｉｎｇ ｒｅｇｉｏｎｓ）を有するセグメントには動きベクトルの平均の大きさを動きアクティビティの尺度として用い、大きいグローバルな動きを有するセグメントには最短の動きベクトルの大きさを動きアクティビティの尺度として用いるが、他の統計学上の動きモーメント（偏差、中央値、分散、スキュー、および尖度など）を用いることもできることを理解されたい。ＭＰＥＧ−７の動きアクティビティ記述子は、表１のように、動きベクトルの大きさの標準偏差の量子化した標準偏差を動きアクティビティの強度の尺度として用いる。動きベクトルの大きさの量子化していない標準偏差を動きアクティビティの尺度として用いることも可能である。
【００５８】
産業上の利用可能性
最後に、本発明が計算を圧縮領域でのみ用いることに留意されたい。したがって、本発明の方法は、いかなる従来技術によるカラーベースのキーフレーム抽出が圧縮領域に適用されたとしても、それらの方法よりはるかに高速である。したがって本発明の方法は、ＭＰＥＧ−７に従ってこれを低いアクション閾値以下のビデオの大部分に用いること、および、カラーベースの手法をアクションのより高いセグメントのみに用いることによって、従来のカラーベースの抽出を助けるために用いることができる。また、カラーベースの計算に全く頼ることなく、ビデオ全体に本発明の方法のみを用いることもできる。これは計算上、最も速いオプションであるだろう。
【００５９】
本発明を好ましい実施形態の例により記載してきたが、本発明の精神および範囲内で様々な他の適用および変更がなされ得ることが理解される。したがって、併記の特許請求の範囲の目的は、本発明の真の精神および範囲内に入るような変形および変更すべてを網羅することである。
【図面の簡単な説明】
【図１】従来技術によるビデオ要約化方法のブロック図である。
【図２】ＭＰＥＧテストビデオの、動きアクティビティと、これに対して、許容不可能な忠実度を有するショットの割合とを表すグラフである。
【図３】所定の閾値以下のショット継続時間の割合と、これに対して、許容不可能な忠実度を有するショットの割合とを表すグラフである。
【図４】本発明によるビデオ要約化方法を示すブロック図である。
【図５】本発明に従って、１番目のフレームを選択した場合と中央のフレームを選択した場合とを比較するグラフである。
【図６】ビデオの２分割のブロック図である。
【図１】
2004520760.tif 000005
【図２】
2004520760.tif 000006
【図３】
2004520760.tif 000007
【図４】
2004520760.tif 000008
【図５】
2004520760.tif 000009
【図６】
2004520760.tif 000010
【国際公開パンフレット】
2004520760.tif 000011
2004520760.tif 000012
2004520760.tif 000013
2004520760.tif 000014
2004520760.tif 000015
2004520760.tif 000016
2004520760.tif 000017
2004520760.tif 000018
2004520760.tif 000019
2004520760.tif 000020
2004520760.tif 000021
2004520760.tif 000022
2004520760.tif 000023
2004520760.tif 000024
2004520760.tif 000025
2004520760.tif 000026
2004520760.tif 000027
2004520760.tif 000028
2004520760.tif 000029
2004520760.tif 000030
2004520760.tif 000031
2004520760.tif 000032
2004520760.tif 000033
2004520760.tif 000034
2004520760.tif 000035
2004520760.tif 000036
2004520760.tif 000037
2004520760.tif 000038
2004520760.tif 000039
2004520760.tif 000040
2004520760.tif 000041
2004520760.tif 000042
【国際調査報告】
2004520760.tif 000043
2004520760.tif 000044
2004520760.tif 000045