JP3968942B2 - ビデオの内容を要約する方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、ビデオ或いは動画の要約(summary)に関する。特に、本発明は、ビデオから各々のショット或いはセグメントの重要度を決定することに関する。また本発明は、要約中の各々のセグメント或いはショットの重要度を強調するか、或いは、重要視しないような構成にパック（即ち、構成）された、ビデオ或いは動画の要約を生成或いは印刷することにも関する。更に本発明は、要約を表示するために最低コストのパッキングしか必要でないように、異なったサイズにされたフレームをビデオ要約にパック（最小の重み付けをされたリサイズ量（即ち、最少のフレームを最小の重み付けをされたリサイズ量で異なったサイズに摺ることによってパックする））するための方法に関する。また更に、ビデオブラウジングシステムへのインタフェースとして最低コストでパックされたビデオ要約を使用することに関する。
【０００２】
【従来の技術】
ビデオの使用及びビデオを介してのイベントの蓄積及び通信が増加すると（インターネット通信、テレビジョン帯域（即ち、テレビジョン放送の周波数帯域）及びチャンネルの増加、ニュース放送におけるビデオの使用の増加等）、ビデオユーザ及び管理者は、最も効率的な方法で、ビデオを格納し、アクセスし、重要なシーン或いはフレームを決定し、そして要約するという付加的な作業に直面する。
【０００３】
「ショット」は、時間及び視覚空間において一般的には連続的であるビデオ或いは動画のセグメントである。一般的には、カットに対応する大きなフレーム差或いはショット境界を見つけることによって、ビデオをその構成要素のショットに自動的にセグメント化する技術は存在する。多くの分野において、既存のビデオ、動画、或いは放送の要約或いは「スキム(skim)」を自動的に生成することが所望される。これは、ビデオの冗長な情報を選択的に廃棄するか或いは重要視しないこによって行うことができる。例えば、繰り返されるショットは、それらが既に示されたショットに類似している場合には、含める必要はない（すなわち、繰り返される或いは共通のシーンのような重要でない情報は廃棄する）。
【０００４】
【発明が解決しようとする課題】
ＡＴＴ研究所のシャラレイ（Ｓｈａｈｒａｒａｙ）らは、ビデオのＨＴＭＬ表現のためにキーフレームを使用することを研究している。彼らは、冗長さを減らすために、キーフレームの数を減らすことについて特別な考慮なしに各ショットから一つのキーフレームを抽出している。キーフレームは一様なサイズとされ、クローズドキャプションデータから抽出されたテキストと共にコラム内に単純にレイアウトされる。彼らの研究には、パックするための努力は組み込まれていない。
【０００５】
タニグチ（Ｔａｎｉｇｕｃｈｉ）らは、パンして得られたビデオを合成することによって形成された大きな画像である「パノラマ」の２Ｄパッキングを使用してビデオを要約した。彼らの方法においては、キーフレームは、全てのショットから抽出され、ビデオの内容の２Ｄ表現のために使用された。フレームは、冗長さを減らす目的では選択されなかった。彼らのパッキング手順は、幾分か準最適であり、結果として生じる合成物に白い空間を残している。
【０００６】
イェン（Ｙｅｕｎｇ）らは、ビデオの各ショット毎に「ドミナンススコア(dominance score)」を使用してビデオの絵で表した要約を作成したが、このようなスコアをどのように実施するか、及び、それをどのように使用するかについての詳細は、アドホック(ad hoc)である。また絵で表した要約には、フレームの時間的な順序がしばしば無視されるポスター状の表現に関してのみ使用することが可能である特定された所定の構造が用いられている。
【０００７】
ビデオの内容をブラウジングするための作られた幾つかの他のツールが公知であるが、不十分な要約を提供するだけであるか、或いは、単にビデオを「そのままの」シーケンスで表示するだけである。
【０００８】
【課題を解決するための手段】
本発明者らは、ビデオ要約が生成される効率を高めるためには、ショット或いはセグメントの重要度の量的な測定が必要であるということを理解した。そのような量的な測定は、ビデオのどのショット或いはセグメントが最も意味があるかを決定するために使用することができる。また、本発明者らは、計算或いは数式によって客観的に決定され、これにより、ショット或いはセグメントの選択プロセスを自動化することができる場合には量的な測定が最良であることも理解した。
【０００９】
これに加えて、本発明者らは、量的な測定は、最も重要なショット或いはセグメントのみを有するビデオ要約を生成するために使用することもでき、また、代表フレーム（キーフレームとしても参照される）のサイズを増やすか減らすかのいずれかによって、要約のどのショット或いはセグメントを強調する（より重要な情報（とする））か、或いは、重要視しない（より重要でない情報（とする））かを決定する際に使用することができるということも理解した。
【００１０】
更に、本発明者らは、要約のために選択された、強調された及び重要視されなかったショット或いはセグメントの各々の効率的な２Ｄ表現のためのパッキング方法を決定した。このように、ショットの重要度が決定されると、二次元の静止表現は、重要度に相関的にサイズが決められた各々のショット或いはセグメントについて代表キーフレームを効率的にパックすることによって構成することができる。
【００１１】
したがって、本発明の目的は、ビデオのショット或いはセグメントの重要度を決定する方法であって、ビデオを複数のショット或いは関連する複数のフレームにセグメント化するステップと、各々のショット或いはセグメントごとに重要度の量を計算するステップとを含む方法を提供することである。セグメント化するステップは、共通の属性及び合致基準或いはアルゴリズムの少なくとも一つに基づいて、ビデオのフレームをクラスタ化するステップも含む。
【００１２】
本発明の別の目的は、ビデオを要約する方法であって、ビデオの構成要素のショットの重要度を決定するステップと、それらの重要度に基づいて要約で使用されるべき構成要素のショット或いはセグメントを選択して、選択された構成要素のショットから代表フレームを抽出するステップと、代表フレームをビデオ要約中に提示するステップとを含む方法を提供することである。提示するステップは、フレームが抽出されるショットの重要度と要約の表示のための所定の限定領域の空間の量とに基づいて各々の代表フレームのサイズを決定し、代表フレームを所定の限定領域にパックするステップとを含む。
【００１３】
また本発明の目的は、フレームのシーケンスを限定領域にパックするための方法であって、フレームシーケンスを限定領域に適合させるステップと、限定領域ごとに最低コストを有するフレームシーケンスを選択するステップとを含む方法を提供することである。
【００１４】
また本発明の目的は、ビデオ要約を見るためのインターフェースを提供することである。インターフェースは、要約の各々のフレームについてビデオの開始点或いは（開始）部分にリンクされた参照符号と共に印刷されたビデオ要約を有する紙、或いは、ビデオの一つ以上の開始点或いは（開始）部分に対応するリンクを備えたウェブベースのインターフェースとすることができるが、これらに限定されるものではない。
本発明の第１の態様は、ビデオのセグメント重要度を決定する方法であって、
ビデオを少なくとも一つの関連するフレームにセグメント化するステップと、
各々のセグメントごとに重要度の量を計算するステップと、を含む。
本発明の第２の態様は、第１の態様において、前記セグメント化するステップは、少なくとも一つのクラスタを作り出すために、共通の属性及び合致基準の少なくとも一つに基づいてビデオのフレームをクラスタ化するステップと、ビデオを同じクラスタのフレームのセグメントに分割するステップと、を含む。
本発明の第３の態様は、第２の態様において、前記クラスタ化するステップは、ビデオの各フレームを階層的なツリーの葉に配置するステップであって、ツリーのルートノードはビデオの全てのフレームを含む最大クラスタである該ステップと、前記階層的なツリーの中間ノードであるクラスタを生成するために、共通の属性及び合致基準の少なくとも一つに基づいて関連するフレームをショットに結合するステップと、を含む。
本発明の第４の態様は、第２の態様において、前記合致基準は、各構成要素のショット間の時間の近接度、空間の近接度、色の近接度、最小距離、カラーヒストグラム距離、及び、変換係数距離の少なくとも一つを評価するステップと、評価するステップの所定の閾値に合致する構成要素のショットを結合するステップと、を含む。
本発明の第５の態様は、第１の態様において、前記計算するステップは、各クラスタの重みを計算するステップと、各々のショットの特徴及びその対応するクラスタの重みに基づいてビデオの各々の個別のショットの重要度を決定するステップと、を含む。
本発明の第６の態様は、第５の態様において、前記各クラスタの重みを計算するステップは、以下の式を含む少なくとも１つの式に基づいてクラスタの重みを決定するステップを有する。
【数２】

ここで、Ｗ_iはクラスタｉの計算された重みであり、Ｓ_iはクラスタｉの全てのショットの全体の長さであり、Ｃはビデオのクラスタの数である。
本発明の第７の態様は、第６の態様において、各クラスタ内の各ショットの重要度を決定する前記ステップは、以下の式を含む少なくとも１つの式に基づいて各ショットの重要度を計算するステップ、を含む。
【数３】

ここで、Ｉ_jはショットｊの重要度、Ｌ_jはショットｊの長さ、Ｗ_kはショットｊが属するクラスタｋの計算された重みである。
本発明の第８の態様は、ビデオの内容を要約する方法であって、ビデオの構成要素のショットの重要度を決定するステップと、構成要素のショットから代表フレームを選択するステップと、代表フレームが選択される構成要素のショットの重要度に基づいて要約中の選択された代表フレームを提示するステップと、を含むビデオのセグメント重要度を決定する方法である。
本発明の第９の態様は、第８の態様において、各々の個々のショットの特性と個々のショットを含むクラスタの重みに基づいてビデオの構成要素のショットに閾値処理を行うステップを更に含む。
本発明の第１０の態様は、第９の態様において、前記閾値処理を行うステップが、いずれかの選択されなかったショットより高い重要度レベルを有するショットと、少なくとも所定の重要度の値を有するショットの所定の数の少なくとも一つを選択するステップと、全ての選択されなかったショットを廃棄するステップとを含む。
本発明の第１１の態様は、第８の態様において、前記選択するステップは、 各々のショットの最初のフレーム、各々のショットを特徴付けるフレーム、各々のショットの全てのフレームの図心に最も近いフレーム、顔が存在するフレーム、動きの欠如及び徴候のいずれか一方を有するフレームの少なくとも一つを含む式に基づいて各々のショットから代表フレームを選択するステップ、を含む。
本発明の第１２の態様は、第８の態様において、前記提示するステップは、各フレームの重要度及び要約の表示のための所定の限定領域内の空間の量に基づいて、各代表フレームのサイズを決定するステップと、代表フレームを所定の限定領域の中にパックするステップとを含む。
本発明の第１３の態様は、第１２の態様において、前記サイズを決めるステップは、代表フレームが選択される構成要素のショットの重要度に基づいて各々の代表フレームのサイズを決定するステップと、各フレームのサイズを前記要約の所定の限界領域の空き空間に適合するように調整するステップと、を含む。
本発明の第１４の態様は、第８の態様において、前記要約は、前記要約のプリントアウトと、各々のコードがビデオの少なくとも一つの代表フレームに関連している少なくとも一つのコードのセットと、を含む紙インターフェースを含み、各々のコードがビデオのセグメント及び開始マーカの少なくとも一つへのインデックスを供給する。
本発明の第１５の態様は、第８の態様において、前記要約は、前記要約の表示と、各々のリンクが選択された代表フレームの少なくとも一つに関連している少なくとも一つのリンクのセットと、を含むウェブインターフェースを含み、各々のリンクがビデオのセグメント及び開始マーカの少なくとも一つにアクセスする。
本発明の第１６の態様は、フレームセットを限定領域にパックする方法であって、フレームシーケンスを限定領域に適合させるステップと、限定領域について最小のコストを有するフレームシーケンスを選択するステップと、を含む。
本発明の第１７の態様は、第１６の態様において、前記適合させるステップは、行高さのセットから行高さ（ｒ）を割り当てるステップと、限定領域を高さ（ｒ）を有する行に分割するステップと、行高さ（ｒ）を有する限定領域に適合するフレームシーケンスを生成するステップと、前記行高さのセットの各々について、前記割り当てるステップ、前記分割するステップ、及び、前記生成するステップを繰り返すステップと、を含む。
本発明の第１８の態様は、第１７の態様において、前記適合させるステップは、各々の行高さ（ｒ）について生成された最低コストのフレームシーケンスを低コストのシーケンスのセットに配置するステップを含み、前記選択するステップは、前記低コストのフレームシーケンスのセットから最低コストのフレームシーケンスを選択するステップを含む。
本発明の第１９の態様は、第１７の態様において、前記分割するステップは、限定領域を、前記フレームのセットの最小フレームの高さの倍数である行高さ（ｒ）を有するグリッドに分割するステップを含む。
本発明の第２０の態様は、第１６の態様において、前記適合させるステップは、限定領域を少なくとも一つのグリッドのセットに分割するステップと、最低コストのフレームシーケンスを各々のグリッドに適合させるステップとを含み、前記選択するステップは、 各々のグリッドから最低コストのフレームシーケンスに基づいて限定領域のフレームシーケンスを選択するステップを含む。
本発明の第２１の態様は、第２０の態様において、最低コストのフレームシーケンスを適合させる前記ステップは、前記グリッドのセットのグリッドを選択するステップと、行高さのセットから選択されたグリッドの行高さ（ｒ）を割り当てるステップと、行高さ（ｒ）を備えた選択されたグリッドに適合するフレームシーケンスを生成するステップと、行高さ（ｒ）を備えた選択されたグリッドについての最低コストを有する生成されたフレームシーケンスを低コストのフレームシーケンスのセットに配置するステップと、行高さのセットの各々の残りの行高さについて前記生成するステップ及び前記配置するステップを実行するステップと、低コストのフレームシーケンスのセットから最低コストのフレームシーケンスを選択するステップと、各々の残りのグリッドについて、前記割り当てるステップ、前記生成するステップ、前記配置するステップ、前記実行するステップ、及び、最低コストのフレームシーケンスを選択するステップを繰り返すステップと、を含む。
本発明の第２２の態様は、第２１の態様において、前記フレームシーケンスを生成するステップは、前記フレームのセットのフレームの数及び順序に一致する最低コストのフレームシーケンスにわたってフレームの数及び順序を維持するステップを含む。
本発明の第２３の態様は、第２１の態様において、前記生成するステップは、フレームが生成された順序と等価な前記フレームシーケンスのフレームの順序を維持するステップ、を含む。
本発明の第２４の態様は、第２１の態様において、前記生成するステップは、選択されたグリッドの行の白い空間の最初の白い空間に適合させるために各々のフレームのサイズを変えるステップ、を含む。
本発明の第２５の態様は、第２１の態様において、前記分割するステップは、限定領域をＷのグリッド間隔を有する少なくとも一つのグリッドのセットに分割するステップを含み、 前記生成するステップは、選択されたグリッドのグリッド空間の白い空間の最初の白い空間に適合させるために各々のフレームのサイズを変えるステップを含む。
本発明の第２６の態様は、第２１の態様において、前記配置するステップは、以下の式を使用して、前記生成するステップによって生成された各々のシーケンスのコストｄ（ｑ，ｂ，ｅ）を計算するステップを含む。
【数４】

ここで、
ｑはフレームシーケンス（ｑ_iはフレームシーケンスｑのｉ番目の要素）、
ｂは開始フレーム、
ｅは終了フレーム、
ｊは要約マーカ、
ｃはコスト関数、
ｆはフレームサイズ、
ｗは重要度関数
である。
本発明の第２７の態様は、第１６の態様において、選択されたフレームシーケンスをウェブページに表示するステップと、選択されたフレームシーケンスの少なくとも一つのフレームを、リンクされたフレームに関連するビデオの表示及び他の情報の少なくとも一つの表示のために、セグメント、開始ポイント、及びメニューオプションの一つにリンクさせるステップと、を更に含む。
本発明の第２８の態様は、第１６の態様において、選択されたフレームシーケンスを、紙及び他の媒体の少なくとも一つを有するタブレットに転送するステップと、選択されたフレームシーケンスの少なくとも一つのフレームを、リンクされたフレームに関連するコード参照情報にリンクさせるステップと、を更に含む。
【００１５】
本発明の一層完全な理解及び本発明に付随する利点が容易に得られるように、添付の図面と関連して本発明を考察する際に、以下の詳細な説明を参照することによって一層良く理解される。
【００１６】
【発明の実施の形態】
本発明は、ショット或いはセグメントの重要度の測定を提示する。直接の用途は、重要なショット或いはセグメントからのキーフレームは印刷されるが、重要でないものは印刷されないビデオ要約を印刷することである。本実施態様においては、重要でないキーフレームは、小さなサイズで印刷され、「コミックブック」或いは「マンガ」レイアウトになる。新規の方法は、異なったサイズにされたキーフレームを効率的にパックするために提示される。
【００１７】
一般的には、カットに対応する大きなフレーム差、或いは、ショット境界を見つけることによって、自動的にビデオをその構成要素のショットにセグメント化するための多くの技術が存在する。検出されると、類似のショット（例えば、類似のカメラアングル或いは対象物）が一つのショット或いはクラスタであると見做せるように、類似性によってショットをクラスタ化することができる。例えば、カメラが二人の俳優の間を繰り返し交互に行き来するフィルムダイアログは、一般的には、各俳優について一つである二つのクラスタから成る。
【００１８】
セグメント化されると、ショットは類似性によってクラスタ化することができる。ビデオをショットに予めセグメント化することなく、クラスタを決定することもできる。ここで使用された方法は、最初にビデオの各々のフレーム（或いは、サブサンプルされた表現）が独自のクラスタに割り当てられる階層的なクラスタ化である。クラスタの数は、二つのクラスタメンバフレームの全ての組み合わせの間の最小距離に基づいて、各々のステップにおいて二つの最も近いクラスタを相互に併合することによって減少する。フレーム間の距離を比較するために、カラーヒストグラム距離或いは変換係数距離のような多数の技術が利用可能である。階層的クラスタ化により、個々のフレームがツリーの葉の上にあるようなツリー構造とされた表現になる。
【００１９】
ツリーのルートノードは全てのフレームから成る最大クラスタである。各々のノードの子は、ノードを形成するために併合されるサブクラスタであり、葉に至るまで細かくなる。併合されたクラスタ間の距離が各々のノードと共に格納される場合には、閾値処理によってクラスタ化の所望の数を選択するためにその距離を使用することができる。それ以下ではフレームが同じクラスタの中にあると見做される閾距離を設定することにより、一つ（ツリーのルート）と多数のフレーム（ツリーの葉）との間で数を調整することができる。
【００２０】
クラスタの最適数は、ビデオのタイプ及び長さに依存する。クラスタが選択されると、各々のフレームにはその対応するクラスタのラベルが付けられる。セグメント或いはショットは、同じクラスタ内のフレームのシーケンスによって規定される。ビデオにＣ個のクラスタがあり、正規化されたクラスタ重みの測定値がクラスタｉについてＷ_iであるとすると、以下のように計算される。
【数５】

ここで、Ｓ_iは、クラスタ内の全てのショット或いはセグメントの長さを合計することによって求められた、クラスタｉ内の全てのショット或いはセグメントの長さの合計である。Ｗ_iは、クラスタｉ内にあるビデオ全体に対するショット或いはセグメントの割合である。
【００２１】
ショット或いはセグメントは、それが長く且つ稀である場合には、すなわち、それが大部分の他のショット或いはセグメントに似ていない場合には重要である。このようにショット或いはセグメントの長さをクラスタ重みの逆数で重み付けすることにより、ショット或いはセグメントの重要度の測定値が生じる。このように（クラスタｋにおける）ショットｊの重要度Ｉは、以下の通りである。
【数６】

ここで、Ｌ_jは、ショットｊの長さである。
【００２２】
重要度の測定値は、ショットが長い場合には大きくなり、クラスタ重みが大きい場合（ショットが一般的であることを意味する）には小さくなる。また重要度は、カラーヒストグラムの差、画素差、或いは、変換係数差として計算されたショットを開始する変化の大きさのような他の要因によっても重み付けされる。これにより、先行するショットから大きく異なっていない場合には、ショットの重要度は減少する。
【００２３】
対数関数の中の定数１は、ショット長とクラスタ重みとの間のトレードオフを制御するための重み付け係数αで置き換えることができる。
【数７】

【００２４】
αの値が大きいと、クラスタ重みが重要度にあまり寄与しないことを意味し、αを小さくすることは、重要度の測定値に対するクラスタ重みの寄与を増やすことである。或るショットカテゴリーを優先的に重み付けすることがしばしば必要である。例えば人物のクローズアップは、ワイドの群衆ショットよりも優先されるかもしれない。重要度の重みは、増幅係数を含ませることによって、これを反映させるために修正することができる。
【数８】

【００２５】
Ａ_tは、カテゴリーｔについての所定の増幅因子である（例えば、カテゴリーｔは、一層優位に重み付けされるクローズアップ、或いは、一層少なく重み付けされる群衆シーン或いはモーションとすることができる）。Ｐ_t（Ｓ_j）は、ショットＳ_jがカテゴリーｔに属する確率の推定値である。式（３）及び式（４）は、以下の式（５）に示されるように、ショット長と個々のクラスタの両方の重み付けができるように、結合することができる。
【数９】

【００２６】
幾つかの図面にわたって同様な参照番号が同一或いは対応する部分を示す図面、特にその図１をここで参照すると、ビデオクリップのセグメントについての計算された重要度の値を表すグラフが例示されている。ビデオクリップは、階層的クラスタ化によって、各々がグラフ上のポイントによって表される６９個のセグメント或いはショットに分割された。各々のポイントについての重要度の値は、殆ど無視できるもの（例えば、ポイント２４）から約０．３（ポイント１８参照）の高さであるものまである。
【００２７】
各々のショットについての重要度が計算されると、ビデオの要約を作り出すことができる。構成されると、代表的な静止フレーム或いはキーフレームは、各々のショットに関連する。これは、例えば、ショットの最初のフレームを抽出することによって、或いは、更に洗練された方法では、ショットの特徴を最も良く表しているフレームを見つけることによって行うことができる。例えば、最良の選択は、（上述したようなクラスタ化における距離計量を使用して）全てのショットフレームの図心に最も近いフレームとすることができる。代表的なフレームを選択するために多数の基準、例えば、顔検出器による顔の存在、動きの欠如、或いは、他の理由が利用可能である。
【００２８】
ショットに重要度のラベルが付されるときには、重要度の値は、ショットの所望の数、したがって、要約についてのキーフレームを選択するための閾値に従うことができる。フレームが選択されると、ビデオシーケンスの絵で表されたアブストラクトを形成するために、フレームを一次元以上の次元にレイアウトすることができる。「コミックブック」フォーマットのような印刷された概要のためには、二次元が最も適切であろう。連続的な表現或いはオーバーレイ特性を組み込んだ他のフォーマットも同様に使用することができる。
【００２９】
重要度のスコアに閾値処理を行うことにより、表示すべきフレームの所望の数を適切なレベルにすることができる。レイアウトを容易にするために、フレームは、おそらくそれらの重要度のスコアに依存して、より小さな或いはより大きなサイズで表示することができる。例えば、これにより、図２Ａに示されるような結果となる。「主要な」ショットＩ及びＪ（それらは高い重要度のスコアを有するので主要である）は、フルサイズのフレームによって表される。ショットＫ及びＬはセクションを共有しなければならないが、これはそれらが重要でない場合には不合理ではない。
【００３０】
閾値処理を行うプロセス自体は、異なった方法で実行することができる。例えば、重要度の値は、０．１５以上を選択することができ、少なくとも０．１５のスコアをもつセグメントが、要約のために選択される。別の方法として、ショットの最適数を、例えば４に決定することができ、四つのみのセグメントが残るまで閾値レベルを高くする（本質的に四つの最も高いスコアのセグメントを選択する）。
【００３１】
これらの技術を図１のチャートに適用すると、閾値を０．１５にするとビデオ要約のために単一セグメントが選択されることになる。この別の方法の技術を使用すると、要約のレイアウトのために四つのフレーム（キーフレーム）が残すために、閾値は約０．１２に下げられる。
【００３２】
またフレームサイズも重要度のスコアに閾値処理を行うことによって選択される。例えば、三つのフレームサイズが指定されたと仮定する。重要度のスコアが閾値よりも大きく最大スコアまでの距離の１／３より小さい場合には、最小サイズのキーフレームが使用される。最大スコアまでの距離の１／３より大きく最大スコアまでの距離の２／３より小さいセグメントについては、最小のサイズの２倍のサイズのキーフレームが選択される。最大スコアと最大スコアまでの距離の２／３との間のセグメントは最大サイズのキーフレームを使用する。
【００３３】
適切な制約条件が与えられると、異なったサイズとされたキーフレームシーケンスは、ユーザの介入なしに合理的なページ（或いは、他の）レイアウトに変えることができるので、レイアウトプロセスは自動化することができる。理想的には、ユーザは、ページの数、ページ当たりのセクションの数、及び、キーフレームサイズの許容範囲のような少数のパラメータを指定することだけが必要となる。上記の例においては（図２Ａ）、二つのキーフレームサイズのみの範囲であるが、他のパラメータの指定も勿論可能である。
【００３４】
したがって、図３に示されるように全体のプロセスを例示することができる。ビデオをフレーム３１５に分割するためにビデオ３００が分割器３１０に供給される。フレーム３１５は、セグメント１…ｎ ３２５を作り出すための上述されたプロセス（クラスタ化、階層ツリー等）のいずれかを使用することができるセグメンタ３２０に供給される（別の方法として、ビデオ３００は、構成要素のショットに分割され、次いで、セグメンター３２０に供給され、或いは、ビデオ３００は、セグメンター３２０に直接供給される）。次いで、セグメント或いはショットは、各々のセグメント或いはショットごとに重要度の量を計算する重要度計算機３３０に供給される。次いで、セレクタ３４０は、各々のセグメント或いはショットから代表フレームを選択する。代表フレームが選択されると、パッキング装置３５０は、ディスプレイ／インターフェース３５５のために重要度に従ってフレームサイズを変えて効率的な配置にパックする。
【００３５】
フレームをショットから選択することが可能であるとすると、空間を効率的に埋め、且つ、元のビデオシーケンスを良好に表すフレームサイズのシーケンスを見つけるというレイアウト問題が減る。一致の程度を規定するために適切なコスト関数を使用することができる。しかしながら、空間のサイズに従ってあり得るシーケンスの数は非常に大きく増加するので、最適なシーケンスを見つけることは困難である。
【００３６】
最適な或いは最適に近いレイアウトを見つけるために、ダイナミックプログラミング（ＤＰ）及びグリーディ(greedy)アルゴリズムのような既存の技術を使用することができる。ダイナミックプロセッシングは、この種の問題についての最適解を見つけることが保証されているが、多大な努力と面倒な調整が必要である。グリーディアルゴリズムは、比較的簡単であるが、合理的な結果を作り出すのに失敗することがある。新規のパッキング方法がここで紹介される。それはＤＰよりも適用するのが簡単であり、純粋なグリーディストラテギー(strategy)よりも良好な解を供給する。
【００３７】
この方法は、全体の空間の特定の「ブロック」或いはサブ領域をパックするためのフレームの最良のシーケンスを選択するので「ブロック網羅型(exhaustive)」して説明される。最良のシーケンスは、特定のブロックについてレイアウトの全ての組み合わせを探索することによって見つけられる。ブロックは、比較的少ないので、これは組み合わせは爆発せず（即ち、組み合わせの数が処理限界を超えることなく）、したがって、最適なレイアウトが単純なツリー探索を含む簡単な技術で見つけられる。
【００３８】
パックされるべき空間は、グリッドの一つのユニットが最小のフレームサイズを保持するように、グリッドに分割される。これは、フレームを以下のようにレイアウトするために使用される。すなわち、一つの「行ブロック」或いはグリッドを横切る列の行が一度にパックされる。ブロックごとの一致スコアは、その高さに応じて変化する。特定のブロックごとの高さは、パッキングスコアによって決定されたような最良のパッキングを作り出す。行ブロックがフレームにパックされると、全てのフレームがパックされるまで、更なる行ブロックが相互に考慮される。
【００３９】
以下のように仮定する。
・最小フレームサイズの倍数として表されたフレームサイズ（本実施態様においては、これは上記のようなショット重要度スコアから決定されるが、任意のサイズの割り当てを使用することができる）ｆ₁，ｆ₂，…，ｆ_Nのシーケンスｆ_iは、Ｋ値（ｓ₁，ｓ₂，…，ｓ_K）の一つを採る。
・Ｍ値（ｒ₁，ｒ₂，…，ｒ_M）として、ブロック行高さの許容可能な範囲を選択する。例えば、最小フレームサイズの２或いは3 倍の行高さが許容可能である場合には、Ｍ＝２，ｒ₁＝２，ｒ₂＝３である。ブロック幅を固定された値ｗに設定する。
・フレームｘを利用可能な残りの空間ｙに配置するコストである関数ｃ（ｘ，ｙ）。一般的なコスト関数は、ｘとｙのサイズ差とすることができる。例えば、フレームを２ｘ２のサイズから1 ｘ１のセルに適合させるために縮小する必要がある場合には、コストは１である。サイズ変更を行わない場合はコストはゼロである。コスト関数は、実際の領域差を反映するために二次にすることができ、或いは、あらゆる任意のコスト関数も使用可能である。
・空間埋め規則。一般的な規則は、列重視、すなわち、上から下、そして、左から右である。これは、フレームが優先的にパックされる順序である。図２Ｂに示される例は、最大ブロック高さが３であり、ブロック幅が８であるときの一般的な場合を示す。
【００４０】
上記のように仮定すると、パッキング方法は、一つの行ブロックについてパッキングを最適化する三つの入れ子になったループから成る。外側ループは、全ての可能性のある行高さ（ｒ₁，ｒ₂，…，ｒ_M）にわたっている。中間ループは、行ブロックを合致するできるだけ多くのフレームにパックして、シーケンスを作る。内側ループは、全ての行高さｒ，可能性のあるフレームシーケンスｉ及びｊについて、コストを累計する。これらのプロセスは、以下にステップ１〜７で説明される。
１．開始フレームｓを１に設定する。
２．行高さｒをＭ値（ｒ₁，ｒ₂，．．．，ｒ_M）の一つに設定する。
３．「行ブロック」に合致する全てのフレームシーケンス｛ｑ₁，ｑ₂，．．．，ｑ_Lr｝を。見つける。
４．上記のシーケンスから、ｓとｓ＋ｎ₁の間の元のシーケンスの一部分に合致する長さｎ₁のシーケンスｑ₁を見つける。ここで、
【数１０】

ｆ_iは、元のシーケンスのｉ番目のフレームサイズを示す。ｑ_ijは、シーケンスｑ_iのｊ番目の要素である。ｗ_iは、付加的な重み付け係数である。
５．最良の行高さｒ及び長さｎの対応するシーケンスｑを見つけるために２及び３を繰り返す。これはこの行ブロックについての最適パッキングである。
６．ｓをｎだけ増やす。
７．ｓが元のシーケンスの長さであるＮに達するまで２から６を繰り返す（全てのフレームがパックされる）。
【００４１】
上記のステップ２は、１）ｊ番目の要素がＫ値（ｓ₁，ｓ₂，…、ｓ_K）の一つである１からｒｘＷの長さの全てのシーケンスを網羅的に生成し、そして、２）「行ブロック」に合致しない全ての生成シーケンスを除去することによって行われる。例えば、
１）ブロック高さが２である場合には、３要素を含むシーケンスは合致せず、２）ブロック幅Ｗが８であり、最大行高さが３である場合には、３より長い全ての３ｓのシーケンスは合致しない。
考慮すべき可能性のある（ｒｘＷ）^Kシーケンスがあるけれども、ｒ、Ｗ、及びＫは非常に小さいので、効率は大きな問題ではない。
【００４２】
図４は、上述したプロセスのフロー例を示すフローチャートである。図4 は、外側ループ４０５／４４５の初期変数を設定して、ブロックに合致させるべきフレームの開始位置を維持するステップ４００を含む。内側ループ４１０／４３０は、各々の可能性のある行ブロック高さごとにフレームシーケンスを生成し、コストアルゴリズムｄ（ｑ_i，ｓ，ｓ＋ｎ_i-1）は、各々の行ブロックを合致させるためのコストを決定するために使用される。各々の行高さについて最小シーケンスを決定した後に、行ブロック全体についての最小が選択され、プロセスは繰り返す。
【００４３】
繰り返しプロセスは、以前の最小行ブロックに合致する最後のフレームの後のフレームから始まる。全てのフレームがパックされた後に、ステップ４５０でプロセスが完了する。表１は、図４のフローチャートで使用された用語を示す。
【表１】

【００４４】
この「行ブロック」パッキング手続きの結果の例が図５に図示される。図の上部における矩形１ａ〜５ａは、重要度によってサイズが変えられた元のフレームシーケンスを示す。図の下部は、高さが３で幅が８の行ブロックにパックされたフレームを示す（ここでは、矩形１ｂ〜５ｂとして図示される）。フレーム５ｂのサイズは、最小の白空間でより良好なパッキングを行うために（影が付された矩形で示された）元のものより拡大される。
【００４５】
【実施例】
本発明者らは、ビデオテープに記録されたスタッフミーティングに対して上述された方法をテストした。ビデオは、約５０分の長さで、実際のカメラ切り換えの間をカウントすると、４９個の実際のショットから成る。１５秒毎にビデオから静止フレームが抽出され、計量距離として、高分散ＤＣＴ係数のユークリッド距離を使用して、５１個のクラスタにクラスタ化された。時折、同じショットからのフレームが、カメラの移動や室内光の変化のような大きな変化のために、異なったクラスタに分割された。結果として、ビデオ全体は、９２個のセグメントに分割された。上述したように、各々のセグメントについて、重要度の測定値が、その長さ及びクラスタ重みに基づいて計算された。
【００４６】
静止概要を生成するために、高い重要度スコアを有するビデオセグメントが選択された。（式２の重み付けしない計算を使用して）最大スコアの８分の１より高いスコアを有するセグメントが選択された。減らされたＤＣＴ係数のユークリッド距離を再度使用して、選択された各々のセグメント毎に、セグメント平均に最も近いフレームが代表フレームとして抽出された。フレームは、それらの元のセグメントの重要度の測定値に従ってサイズが決定されるので、高い重要度のフレームは大きかった。
【００４７】
現在の実施態様においては、所与のフレームの重要度が最大の８分の１と４分の１の間であった場合には、最小フレームサイズが割り当てられる。最大の４分の１より大きく半分より小さいスコアのフレームは、最小サイズの２倍のサイズにされ、２分の１より大きいスコアのフレームは、最小サイズの３倍の大きさのサイズにされた。概略のフレームサイズのパーセンテージは、経験的に決定される閾値によって設定することができる。例えば、全ての表示されたフレームの半分が最大サイズであることが望まれる場合には、上側閾値は、（幾つかのフレームはパッキング方法によってサイズが変更されることになるが）累計重要度スコアから決定することができる。
【００４８】
フレームサイズを割り当てた後に、冗長なフレームを更に除去するために、以下の二つの手続きが適用される。二つの手続きは、除去がなくなるまで繰り返して適用される。
【００４９】
［トリミング分岐］
２つの連続するフレームが同じクラスタからのものである場合には、より小さなフレームが除去される。両方のフレームが同じサイズを有する場合には、後に現れるフレームが除去され、先に現れるフレームが拡大される。
【００５０】
［孤立部の除去］
各々１フレームだけ離れた同じクラスタからの三つのフレームが見つかった場合には、中間のフレームが最小のフレームであり、中間のフレームが除去される。
【００５１】
我々のサンプルビデオの場合には、サイズ１，２，３の抽出されたフレームの数は、それぞれ、９個，１３個，２個であった。我々は重要度スコアに対して簡単なフレームサイズの割り当てを選択したが、連続可変サイズを含む多くの他の割り当てが可能である。異なったサイズとされたフレームが、前述された方法を使用してパックされた。結果は図６に示されており、このパッキングについては、２４個のフレームの中の６個のみがサイズの調整が必要であった。上記の要約は、テキスト注釈、タイトル、或いは、フレームと一緒にトランスクリプション(transcription)を表示することのような、任意の数の方法で強化することができる。テキストは、見だし或いは台詞の吹き出しとして各々のフレームにスーパーインポーズして表示することができる。フレームは、例えば、色が付いた境界を使用して、特別な時間或いはインデックスマークを示すために、ハイライトすることができる。フレームは、例えば、弱いコントラスト（退色した）或いは色（グレイスケール）で表示することにより、重要度或いは他のスコアによって、重要視しない様にすることができる。
【００５２】
［ビデオの紙インターフェース］
上述された方法は、紙ユーザインターフェースを使用するビデオデータベースシステムに容易に適用することができる。ビデオデータベースの各々のビデオは、説明された方法を使用して要約され、元のビデオを示すコード化された情報と共に印刷される。図７は、各々の印刷されたフレーム（例えば、６１０）、及び対応するコード化された情報６１５についての紙インターフェースを例示する。
【００５３】
情報は、テキスト、グリフ(gryph)コード或いはバーコードを含む多くの方法のいずれかを使用してコード化することができる。また、要約のフレームは、フレームによって表されたショットの開始時間を示すタイムコードでラベルをつけることができる。各々のフレームについてのタイムコードは、各フレームの下方、或いは、実際のフレーム画像の中にコード化されて、対応するどこにでも配置することができ,或いは、呼び出し或いは図形的な指示を有することもできることは明らかである。
【００５４】
図８は、システムの一般的な実施態様を例示する。基本的な構成要素は、ハンドヘルドグリフスキャナ７００、グリフデコードユニット７１０及びビデオ記録装置７２０及び再生装置７３０である。ユーザは、紙要約に印刷されたグリフコードを走査することによって所望のビデオを選択する。次いで、そのビデオからの特定のショットは、代表フレームに添付されたグリフを走査することによって選択することができる。別方として、グリフは、ビデオとショットの両方をコード化することができる。デコーダは、走査されたグラフコードをデコードし、デコーダからの出力はビデオデータベースに送られ、ビデオが検索されて指定された位置から再生される。ビデオは、選択されたキーフレームが提示しているセグメントの最初から始めることができ、或いは、選択された代表フレームが抽出されたポイントにおいて始めることができる。他の印刷されたグリフは、例えば、音量或いは再生のような他の表現態様を制御することができる。
【００５５】
ビデオは、ショット重要度の測定値を強調するために再生のしながら修正することができる。例えば、音量を下げたり再生速度を上げたりすることによって、より重要でないショットを重要視しないようにすることができる。特定の閾値より重要度の低いショットは全体的にスキップすることができ、要約或いは「ビデオスキム」になる。複数のフレーム及びそれらの対応するショットは、個人的なビデオ要約を生成するためにユーザによって選択することができる。この動作のために、ユーザは、フレームを選択する前後に専用のコードを走査しなければならないかもしれない。この手順は、システムのボタンを押すことによって置き換えることができる。スキャナがハンドヘルドであることは必須ではなく、代わりにフラットベッドスキャナを使用することができる。その場合には、グリフコードの代わりにチェックボックスをフレームに添付することができ、ユーザは、一つ以上のチェックボックスをマーキングすることによってショットを特定することになる。（例図７）
【００５６】
［ウェブベースのインターフェース］
紙に加えて、上記の機能の多くはウェブベースのビデオユーザインターフェースのために使用することができる。ビデオ要約は前記の通り構成することができるが、紙よりはむしろハイパーテキストの形態で表現される。ユーザは、列記されたビデオの名称或いは機能的に等価な表現をクリックすることによってビデオ要約を生成することができる。要約におけるフレームのサイズ及び数のような種々のパラメータは、要求に応じて指定することができる。生成された要約は、ウェブブラウザでの表示のためにクライアントに送り返され、或いは、紙の形態で印刷される。これは少なくとも二つの方法で行うことができる。一つの方法は、サーバにおいて完全なビットマップとされた画像を生成して、それをクライアントに送ることである。別の方法は、サーバから画像ファイルとレイアウト情報を送って、クライアントに要約を組み立てさせることである。
【００５７】
またサーバは、開始時間及び期間、キーフレームインデックス、及び、レイアウト情報のような全ての適切なショット情報を含むテーブルを生成することもできる。このテーブルは、サーバ側或いはクライアント側のどちらでも保持することができる。要約上でマウスクリックが検出されたときには、クリック位置をテーブルを介してマッピングすることによって指定されたビデオ及びショットを決定することができる。次いで、開始時間を決定することができ、ビデオプレイヤを起動するために使用することができる。このように、ユーザは、要約を見ることによってビデオの内容を通してスキミングし、クリックされたフレームに対応するビデオの位置或いはセグメントから再生されるべきビデオについてのトリガである要約中の任意のフレームをクリックすることによって詳細に入り始める（即ち、詳細を見る）ことができる。
【００５８】
前述の紙インターフェースと同様な外見を有するウェブインターフェースの例が図９に示される。
【００５９】
本発明は、コンピュータ技術分野の当業者にとって明らかであるように、本開示の教示に従ってプログラムされた従来の汎用或いは専用デジタルコンピュータ或いはマイクロプロセッサを使用して簡便に実施することができる。
【００６０】
適切なソフトウェアコーディングは、ソフトウェア技術分野の当業者にとって明らかであるように、本開示の教示に基づいて、熟練したプログラマによって容易に用意することができる。また本発明は、当業者にとって容易に明らかであるように、用途特定集積回路の用意によって、或いは、従来の構成要素回路の適切なネットワークの相互接続によって、実施することもできる。
【００６１】
本発明は、本発明のプロセスのいずれかを実行するようにコンピュータをプログラムするために使用することができる、その内部に格納された命令を有する一つの（或いは複数の）記憶媒体であるコンピュータプログラム製品を含む。蓄積媒体は、フロッピディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、及び光磁気ディスクを含む任意のタイプのディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリ装置、磁気或いは光カード、（分子(molecular)ＩＣを含む）ナノシステム、或いは、命令及び／又はデータを格納するのに適した任意のタイプの媒体或いはデバイスを含むことができるが、これらに限定されるものではない。
【００６２】
本発明は、コンピュータが読み取り可能な一つの（或いは複数の）媒体のいずれか一つに格納されて、汎用／専用コンピュータ或いはマイクロプロセッサのハードウェアの両方を制御するための、また、コンピュータあるいはマイクロプロセッサが、本発明の結果を使用して、人間であるユーザ或いは他のメカニズムと相互作用できるようにようにするためのソフトウェアを含む。そのようなソフトウェアは、デバイスドライバ、オペレイティングシステム、及び、ユーザアプリケーションを含むことができるが、これらに限定されるものではない。最後に、そのようなコンピュータが読み取り可能な媒体は、更に、上述したように、本発明を実行するためのソフトウェアを含む。
【００６３】
汎用／専用コンピュータ或いはマイクロプロセッサのプログラミング（ソフトウェア）に含まれるのは、ビデオのセグメント化、ショットの重要度の計算、クラスタ化、パッキング、及び、本発明のプロセスに従った結果の表示、記憶、或いは、通信を含む本発明の教示を実施するためのソフトウェアモジュールであるが、これに限定されるものではない。
【００６４】
明らかに、本発明の修正及び変形が上記の教示を考慮して可能である。したがって、それは添付の特許請求の範囲内であることが理解されるべきであり、本発明は、ここに特に説明されたものとはべつのもので実施することができる。
【図面の簡単な説明】
【図１】 ビデオ提示における各々のセグメント或いはショットごとの重要度計算のグラフである。
【図２】 （Ａ）は重要度に基づいてサイズが決定されパックされたフレームを示し、（Ｂ）はパッキングのための行ブロックの例を示す。
【図３】 セグメント化、クラスタ化、及びパッキング装置のブロック図である。
【図４】 パッキングプロセスを説明するフローチャートである。
【図５】 白空間を最小化するための再サイズ決定によるパックされたフレームシーケンスの例示である。
【図６】 重要度に基づいたパッキングから得られるビデオ要約製品である。
【図７】 本発明に従ってレイアウトされたビデオフレームの紙要約である。
【図８】 ビデオ紙要約を使用するための装置レイアウトの例示である。
【図９】 本発明に従ったビデオ要約ウェブインターフェースの例示である。
【符号の説明】
３００ ビデオ
３１０ 分割器
３２０ セグメンター
３００ 重要度計算機
３４０ セレクタ
３５０ パッキング装置
３５５ 表示／インターフェース

Claims (1)

1. ビデオの内容を要約する方法であって、
   複数のフレームのシーケンスからなるビデオを少なくとも一つのフレームを含むセグメントにセグメント化するステップと、
   各々のセグメントごとに重要度を計算するステップと、
   セグメントの重要度に基づいて重要なセグメントを決定するステップと、
   重要なセグメントから代表フレームを選択するステップと、
   重要なセグメントの重要度に基づく代表フレームの重要度及び要約の表示のための所定の限定領域の空き領域のサイズに基づいて、各代表フレームのサイズを決定するステップと、
   代表フレームのシーケンスを当該シーケンスに対応した並びを維持した状態で前記所定の限定領域の中にパックするステップと、
   パックされた限定領域の内容を要約として表示するステップと、
   を含み、
   さらに、前記セグメントの関連するセグメントをクラスタにクラスタ化するステップを含み、
   前記計算するステップは、
   クラスタ内にある全てのセグメントのビデオ全体に対する割合を示すクラスタの重みをクラスタの各々について計算するステップと、
   各々のセグメントの長さに比例し、該セグメントに対応するクラスタの重みの対数に反比例するように、ビデオの各々の個別のセグメントの重要度を決定するステップと、
   を含む、
   ビデオの内容を要約する方法。

Images