(57)【特許請求の範囲】
【請求項１】
複数の動画フレームでなる動画セグメントに対し要約を生成する、コンピュータが実行する動画要約生成方法において、
（ａ）前記動画セグメントの第１の動画フレームを受信するステップと、
（ｂ）後続の動画フレームを受信するステップと、
（ｃ）前記ステップ（ａ），（ｂ）で受信した複数の動画フレームのそれぞれに対し、動画フレームを表現する特徴ベクトルを規定するステップと、
（ｄ）ベクトルランクフィルタを用いて、前記ステップ（ｃ）で規定した複数の特徴ベクトルの全てについて歪みを求め、該歪みを最小にする特徴ベクトルをキー特徴ベクトルとして認定するステップと、
（ｆ）前記ステップ（ｄ）で認定された前記キー特徴ベクトルに対応する前記動画フレームを、キー動画フレームとして認定するステップと、
（ｇ）前記ステップ（ｆ）で認定された前記キー動画フレームを、前記動画の要約として出力するステップと、
を含み、
前記ベクトルランクフィルタは、前記ステップ（ｃ）で規定した複数の特徴ベクトルのうち、１つの特徴ベクトルについて他の特徴ベクトルとの差の絶対値を、他の全ての特徴ベクトルについて求め、それぞれの絶対値をｑ乗（ｑは自然数とする。）して該１つの特徴ベクトルに関する重み付け係数ｗを乗じた総和を、該１つの特徴ベクトルの前記歪みとして算出することを特徴とする動画要約生成方法。
【請求項２】
前記要約の対象となる前記動画セグメントは、複数の動画フレームでなる動画シーケンスの所定の第１の境界を始点とし、第２の境界を終端とするものであり、
当該動画要約生成方法は、前記第２の境界を決定する動画セグメント第２境界決定ステップを、さらに含み、
前記動画セグメント第２境界決定ステップは、
（ｈ）しきい値を規定するステップと、
（ｏ）前記最小の歪みが前記しきい値を超えるまで、前記ステップ（ｂ）〜（ｄ）を繰り返し、前記最小の歪みが前記しきい値を超えたときの境界を前記第２の境界として決定するステップと、
を有することを特徴とする請求項１に記載の動画要約生成方法。
【請求項３】
複数の動画フレームでなる動画セグメントに対し要約を生成する、コンピュータが実行する動画要約生成方法において、
（ａ）前記動画セグメントの第１の動画フレームを受信するステップと、
（ｂ）後続の動画フレームを受信するステップと、
（ｃ）前記ステップ（ａ），（ｂ）で受信した複数の動画フレームのそれぞれに対し、動画フレームを表現する特徴ベクトルを規定するステップと、
（ｄ）ベクトルランクフィルタを用いて、前記ステップ（ｃ）で規定した複数の特徴ベクトルのそれぞれについて、他の全ての特徴ベクトルとの距離の総和を累積距離として算出し、該累積距離を最小にする特徴ベクトルをキー特徴ベクトルとして認定するステップと、
（ｆ）前記ステップ（ｄ）で認定された前記キー特徴ベクトルに対応する前記動画フレームを、キー動画フレームとして認定するステップと、
（ｇ）前記ステップ（ｆ）で認定された前記キー動画フレームを、前記動画の要約として出力するステップと、
を含み、
前記ベクトルランクフィルタは、前記ステップ（ｃ）で規定した複数の特徴ベクトルのうち、１つの特徴ベクトルについて他の特徴ベクトルとの差の絶対値を、他の全ての特徴ベクトルについて求め、それぞれの絶対値をｑ乗（ｑ＝１とする。）して該１つの特徴ベクトルに関する重み付け係数ｗ（ｗ＝１とする。）を乗じた総和を、該１つの特徴ベクトルの前記累積距離として算出することを特徴とする動画要約生成方法。
【請求項４】
前記要約の対象となる前記動画セグメントは、複数の動画フレームでなる動画シーケンスの所定の第１の境界を始点とし、第２の境界を終端とするものであり、
当該動画要約生成方法は、前記第２の境界を決定する動画セグメント第２境界決定ステップを、さらに含み、
前記動画セグメント第２境界決定ステップは、
（ｈ）しきい値を規定するステップと、
（ｐ）前記最小の累積距離が前記しきい値を超えるまで、前記ステップ（ｂ）〜（ｄ）を繰り返し、前記最小の累積距離が前記しきい値を超えたときの境界を前記第２の境界として決定するステップと、
を有することを特徴とする請求項３に記載の動画要約生成方法。
【請求項５】
相対的に一様な内容の複数の動画フレームをスキミングする動画スキミング装置において、
（ａ）前記複数の動画フレームを受信する受信機と、
（ｂ）前記複数の動画フレームを複数のベクトル信号として特徴付けるベクトルコンバータと、
（ｃ）前記ベクトルコンバータで特徴付けられた全ての前記ベクトル信号のセット内において、１つのベクトル信号について他のベクトル信号との差の絶対値を、他の全てのベクトル信号について求め、それぞれの絶対値をｑ乗（ｑは自然数とする。）して該１つのベクトル信号に関する重み付け係数ｗを乗じた総和を、該１つのベクトル信号の歪みとして算出し、前記セット内のベクトル信号の各々について算出された歪みに従って、前記セット内の各ベクトル信号をランク付けするベクトルランクフィルタと、
（ｄ）特定ランクの前記歪みを生じる前記ベクトル信号の各々に対応する前記動画フレームの各々を認定するスキマとを有することを特徴とする動画スキミング装置。
【請求項６】
相対的に一様な内容の複数の動画フレームをスキミングする動画スキミング装置において、
（ａ）前記複数の動画フレームを受信する受信機と、
（ｂ）前記複数の動画フレームを複数のベクトル信号として特徴付けるベクトルコンバータと、
（ｃ）前記ベクトルコンバータで特徴付けられた前記ベクトル信号全てのセット内において、１つのベクトル信号について他のベクトル信号との差の絶対値を、他の全てのベクトル信号について求め、それぞれの絶対値をｑ乗（ｑ＝１とする。）して該１つのベクトル信号に関する重み付け係数ｗ（ｗ＝１とする。）を乗じた総和を、該１つのベクトル信号の累積距離として算出し、前記セット内のベクトル信号の各々ついて算出された累積距離に従って、前記セット内の各ベクトル信号をランク付けするベクトルランクフィルタと、
（ｄ）特定ランクの累積距離を生じる前記ベクトル信号の各々に対応する前記動画フレームの各々を認定するスキマとを有することを特徴とする動画スキミング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、動画要約生成方法及び動画要約生成装置（動画スキミング装置）に関し、より詳細には、ディジタル動画の内容の解析に際し、ディジタル動画シーケンスを一連の代表的なキーフレームとして要約する動画要約生成方法及び動画要約生成装置に関する。
【０００２】
【従来の技術】
動画の有用性と効果が増大するに従って、動画を要約し抽象化し、ユーザが本来数千時間に及ぶ動画を有効且つ効率的にブラウジングするのを支援する必要が生じている。要約を作成するために動画の内容を解析しキーとなる代表的な内容を抽出する作業の自動化は、動画がアナログからディジタルフォーマットに進展するに従ってその重要性が高まっている。ディジタルテレビ，ディジタル動画ライブラリ及びインターネットは、動画を“閲覧（観察）”してその内容を自動的に要約する装置を有効に使用できるアプリケーションである。
【０００３】
一般に、動画シーケンスは、一連のシーンを含んでいる。各シーンは、また、一連の隣接動画“ショット”を含んでいる。１ショットは、同一シーンに属する１つ又は複数のオブジェクトに焦点を合わせた単一カメラによって撮影された相対的に同質な一連の個別フレームである。一般に、動画内容の自動解析及び抽出は、動画シーケンスを“閲覧”し、動画シーケンスを一連のショットに分割し、各ショットからそのショットの内容を示す“キーフレーム”を選択することを含んでいる。動画シーケンスは、一連のキーフレームが表示されることで要約される。各ショットの内容を最も代表（表現）するフレームを、キーフレームとして選択して要約に含めれば、動画の要約は、その動画シーケンスを最良に表現可能である。各ショットからのキーフレームの枚数に差をつけるような要約の階層化を導入することも、動画ユーザの種々の需要を満たすために望ましいことである。
【０００４】
要約プロセスにおける第１ステップは、動画を相対的に同質な（一様な）内容の一連のショットに分割することである。動画ショットの移行は、“フェード”，“ディゾルブ”，“ワイプ”等のような、２枚の連続フレーム（カット）間で生じる突然の遷移から、より緩やかな遷移への移行を特徴とする。１ショットの境界を検出する１つの技法は、順次フレーム中の予定されたしきい値を超えて数値が変化する画像の予定領域数又は画素数のいずれかをカウントすることを含んでいる。この第１の判定基準を満足する領域又は画素の数のいずれかが、第２の予定されたしきい値を超える時に、ショットの境界が宣言される。１フレームの予め特定された領域内の画素値の統計的な測定値もショット境界の検出に利用されている。画素差技法はカメラとオブジェクトの動きに反応できる。統計的技法は、統計式の計算が複雑なために比較的に低速度になる傾向がある。
【０００５】
ヒストグラムとヒストグラム関連統計値は、ショット境界の検出に用いる最も普通な画像表現である。グレイレベルのヒストグラム、色ヒストグラム又はヒストグラム関連統計値は、連続するフレームについて比較できる。その差が予定しきい値を超えれば、ショットの境界が検出される。第２のしきい値によるチェックは、さらに緩やかな形のショット遷移を検出するために用いる。
【０００６】
【発明が解決しようとする課題】
しかしながら、１ショットの相対的に均質なフレームを最適に表現する１枚又はそれ以上のキーフレームを選択することは、ショット境界を定義する以上に多くの問題を含んでいる。Lagendijk他は、論文“ＳＭＡＳＨシステムにおける映像探索（Visual Search In A Smash System）”（画像処理に関する国際会議の会報，１９９６年，６７１−６７４頁）において、時間による累積画像ヒストグラムの差を監視することによりショットの境界を決定するプロセスを記述している。各ショットのフレームを、各ショットからの抽出される予め特定された数のキーフレームを反映するグループに時間的に分割する。各フレームグループの中央のフレームを次にそのグループのキーフレームとして選択する。キーフレームの選択は、任意であり、そのグループの最も“重要なフレーム”或いは“有意義なフレーム”であることを意味しない。また、このプロセスは、“オフライン”で実施するので、動画全体を“再検討”及びショット境界の確定のために蓄積してから、ショットのセグメント化及びキーフレームの抽出をしなければならない。キーフレームの抽出のために、蓄積した動画を処理バッファにロードしてフレームグループと関連キーフレームを計算できるようにしなければならない。１ショットのサイズは、処理バッファのサイズで制限される。
【０００７】
Ratakondaの米国特許出願第０８／９９４，５５８号（１９９７年１２月１９日出願）においては、ショット境界は時系列による画像ヒストグラムの差の変動を監視することにより決定する。個々のショットは、高度に同質なグループを示すフレームのセグメントにさらに分割する。このショットのセグメント分割は、反復最適化プロセスにより達成する。動画セグメント毎に、先行セグメントのキーフレームと最も異なるフレームを要約の次のキーフレームとして選択する。１枚のキーフレームを、そのセグメントに属する他のフレームの表示に基づかず、先行キーフレームとのフレームの差異に基づいて選択する。Langendijkの提案技法と同様に、この技法はオフラインで実行しなければならず、再検討，セグメント分割及びキーフレームの選択のために、１動画ショットを全部蓄積しなければならない。また、比較のために先行キーフレームを蓄積する追加のメモリを必要とする。
【０００８】
Zhang他の米国特許第５，６３５，９８２号公報には、フレーム間の差を監視し累積する方法が記載されている。累積差が予定したしきい値を超えると、１枚のキーフレームとなり得るキーフレームが検出される。さらに、このキーフレーム候補と先行キーフレームとの差が設定しきい値を超える場合に、このキーフレーム候補をキーフレームとして指定する。追加の処理をすることなく、キーフレームの位置は、新しいショットの始点と常に一致する。
【０００９】
Smith他の論文“言語理解技法と画像の組み合せによる動画のスキミングと特徴付け（Video Skimming And Characterization Through The Combination Of The Image And Language Understanding Techniques）”並びにＭａｕｌｄｉｎ他の米国特許第５，６６４，２２７号公報には、反復度，動きの程度及び音声・動画の内容に関連するコンテキスト規則に基づく詳細なキーフレーム特定技法が開示されている。キーフレームシーケンスは、動画シーケンスの簡潔な要約を提供するために使用できるが、この方法は複雑であり、階層的な動画要約の作成を支援していない。
【００１０】
本発明は、上述のごとき実状に鑑みてなされたものであり、動画シーケンスのフレームに対応する特徴ベクトルの解析に基づいてディジタル動画の内容を解析し抽出する動画要約生成方法及び動画要約生成装置を提供することをその目的とする。
【００１１】
本発明は、動画の内容の自動解析と、動画シーケンスの各ショット又はセグメントを最も代表（表現）するフレームであるキーフレームを選択するキーフレーム抽出の技法を提供することをその目的とする。簡単な装備、計算機資源の維持及び各種入力の受信能力は、かような技法に望まれる特性である。さらに、本発明は、内容の解析とキーフレームの抽出を両方とも“オンライン（リアルタイム）”で処理でき、動画シーケンス全体を蓄積する必要なく実施でき、又“オフライン”でも実施できる動画要約生成方法及び動画要約生成装置を提供することをその目的とする。さらに、本発明は、より少ない数の最も代表的なフレームを含む各要約の階層化を簡便に実現できる動画要約生成方法及び動画要約生成装置を提供することをその目的とする。
【００１４】
【課題を解決するための手段】
本発明の第１の技術手段は、複数の動画フレームでなる動画セグメントに対し要約を生成する、コンピュータが実行する動画要約生成方法において、
（ａ）前記動画セグメントの第１の動画フレームを受信するステップと、
（ｂ）後続の動画フレームを受信するステップと、
（ｃ）前記ステップ（ａ），（ｂ）で受信した複数の動画フレームのそれぞれに対し、動画フレームを表現する特徴ベクトルを規定するステップと、
（ｄ）ベクトルランクフィルタを用いて、前記ステップ（ｃ）で規定した複数の特徴ベクトルの全てについて歪みを求め、該歪みを最小にする特徴ベクトルをキー特徴ベクトルとして認定するステップと、
（ｆ）前記ステップ（ｄ）で認定された前記キー特徴ベクトルに対応する前記動画フレームを、キー動画フレームとして認定するステップと、
（ｇ）前記ステップ（ｆ）で認定された前記キー動画フレームを、前記動画の要約として出力するステップと、
を含み、
前記ベクトルランクフィルタは、前記ステップ（ｃ）で規定した複数の特徴ベクトルのうち、１つの特徴ベクトルについて他の特徴ベクトルとの差の絶対値を、他の全ての特徴ベクトルについて求め、それぞれの絶対値をｑ乗（ｑは自然数とする。）して該１つの特徴ベクトルに関する重み付け係数ｗを乗じた総和を、該１つの特徴ベクトルの前記歪みとして算出することを特徴としたものである。
【００１６】
本発明の第２の技術手段は、第１の技術手段において、前記要約の対象となる前記動画セグメントは、複数の動画フレームでなる動画シーケンスの所定の第１の境界を始点とし、第２の境界を終端とするものであり、
当該動画要約生成方法は、前記第２の境界を決定する動画セグメント第２境界決定ステップを、さらに含み、
前記動画セグメント第２境界決定ステップは、
（ｈ）しきい値を規定するステップと、
（ｏ）前記最小の歪みが前記しきい値を超えるまで、前記ステップ（ｂ）〜（ｄ）を繰り返し、前記最小の歪みが前記しきい値を超えたときの境界を前記第２の境界として決定するステップと、
を有することを特徴としたものである。
【００２２】
本発明の第３の技術手段は、複数の動画フレームでなる動画セグメントに対し要約を生成する、コンピュータが実行する動画要約生成方法において、
（ａ）前記動画セグメントの第１の動画フレームを受信するステップと、
（ｂ）後続の動画フレームを受信するステップと、
（ｃ）前記ステップ（ａ），（ｂ）で受信した複数の動画フレームのそれぞれに対し、動画フレームを表現する特徴ベクトルを規定するステップと、
（ｄ）ベクトルランクフィルタを用いて、前記ステップ（ｃ）で規定した複数の特徴ベクトルのそれぞれについて、他の全ての特徴ベクトルとの距離の総和を累積距離として算出し、該累積距離を最小にする特徴ベクトルをキー特徴ベクトルとして認定するステップと、
（ｆ）前記ステップ（ｄ）で認定された前記キー特徴ベクトルに対応する前記動画フレームを、キー動画フレームとして認定するステップと、
（ｇ）前記ステップ（ｆ）で認定された前記キー動画フレームを、前記動画の要約として出力するステップと、
を含み、
前記ベクトルランクフィルタは、前記ステップ（ｃ）で規定した複数の特徴ベクトルのうち、１つの特徴ベクトルについて他の特徴ベクトルとの差の絶対値を、他の全ての特徴ベクトルについて求め、それぞれの絶対値をｑ乗（ｑ＝１とする。）して該１つの特徴ベクトルに関する重み付け係数ｗ（ｗ＝１とする。）を乗じた総和を、該１つの特徴ベクトルの前記累積距離として算出することを特徴としたものである。
【００２５】
本発明の第４の技術手段は、第３の技術手段において、
前記要約の対象となる前記動画セグメントは、複数の動画フレームでなる動画シーケンスの所定の第１の境界を始点とし、第２の境界を終端とするものであり、
当該動画要約生成方法は、前記第２の境界を決定する動画セグメント第２境界決定ステップを、さらに含み、
前記動画セグメント第２境界決定ステップは、
（ｈ）しきい値を規定するステップと、
（ｐ）前記最小の累積距離が前記しきい値を超えるまで、前記ステップ（ｂ）〜（ｄ）を繰り返し、前記最小の累積距離が前記しきい値を超えたときの境界を前記第２の境界として決定するステップと、
を有することを特徴としたものである。
【００５５】
本発明の第５の技術手段は、相対的に一様な内容の複数の動画フレームをスキミングする動画スキミング装置において、
（ａ）前記複数の動画フレームを受信する受信機と、
（ｂ）前記複数の動画フレームを複数のベクトル信号として特徴付けるベクトルコンバータと、
（ｃ）前記ベクトルコンバータで特徴付けられた全ての前記ベクトル信号のセット内において、１つのベクトル信号について他のベクトル信号との差の絶対値を、他の全てのベクトル信号について求め、それぞれの絶対値をｑ乗（ｑは自然数とする。）して該１つのベクトル信号に関する重み付け係数ｗを乗じた総和を、該１つのベクトル信号の歪みとして算出し、前記セット内のベクトル信号の各々について算出された歪みに従って、前記セット内の各ベクトル信号をランク付けするベクトルランクフィルタと、
（ｄ）特定ランクの前記歪みを生じる前記ベクトル信号の各々に対応する前記動画フレームの各々を認定するスキマとを有することを特徴としたものである。
【００５６】
本発明の第６の技術手段は、相対的に一様な内容の複数の動画フレームをスキミングする動画スキミング装置において、
（ａ）前記複数の動画フレームを受信する受信機と、
（ｂ）前記複数の動画フレームを複数のベクトル信号として特徴付けるベクトルコンバータと、
（ｃ）前記ベクトルコンバータで特徴付けられた前記ベクトル信号全てのセット内において、１つのベクトル信号について他のベクトル信号との差の絶対値を、他の全てのベクトル信号について求め、それぞれの絶対値をｑ乗（ｑ＝１とする。）して該１つのベクトル信号に関する重み付け係数ｗ（ｗ＝１とする。）を乗じた総和を、該１つのベクトル信号の累積距離として算出し、前記セット内のベクトル信号の各々ついて算出された累積距離に従って、前記セット内の各ベクトル信号をランク付けするベクトルランクフィルタと、
（ｄ）特定ランクの累積距離を生じる前記ベクトル信号の各々に対応する前記動画フレームの各々を認定するスキマとを有することを特徴としたものである。
【００７３】
【発明の実施の形態】
本発明の前述及び他の目的、特徴及び利点は、添付図面を参照して本発明の下記の詳細な説明を考慮すれば、容易に理解できよう。
本発明においては、ディジタル動画シーケンスの自動要約がベクトルランクフィルタを用いて達成される。ディジタル動画シーケンスの連続フレームをベクトルのセットに逐次蓄積する特徴ベクトルとして表現できる。各逐次ベクトルの追加によるセットの歪み、又は、セット内の各逐次ベクトルから他のすべてのベクトルまでの累積距離が、ベクトルランクフィルタで決定される。歪みがしきい値を超えると動画セグメントの終了が検出される。動画セグメント内の各フレームは、動画フレームを表現する特徴ベクトルにベクトルランクフィルタを適用することにより、セットの他のフレームとの相対的類似性に従ってランク付けすることが可能となる。動画シーケンスの内容を最も表現する動画シーケンスの要約を生成するために、セグメントを表現するベクトルセットに関し最小距離又は最小歪みを生じさせるベクトルに対応するフレームを選択する。相対的な歪みをランク付けして各セグメントから１フレームより多いフレームを選択する根拠として使用し、最も代表的な内容（以下、コンテンツと呼ぶ）を持つフレームを多数含む階層的要約を生成する。
【００７４】
一般に、動画シーケンスは一連のシーンを含んでいる。各シーンは、また、一連の隣接動画“ショット”を含んでいる。１ショットは、興味を引く１つ又は複数のオブジェクトに焦点を合わせた単一カメラによって撮影された比較的同質な一連の個別フレームである。一般に、動画コンテンツの自動解析及び抽出は、動画シーケンスを見ることと、動画シーケンスを一連のショットに分割することと、各ショットからそのショットのコンテンツを示す１つ以上の“キーフレーム”を選択することを含んでいる。動画シーケンスは、キーフレームのリストを表示又は提供することにより要約される。
【００７５】
ディジタル動画の１フレームのコンテンツは、幾つかの方法で表現できる。通常は、画素又はピクチャ領域の頻度分布を、画素又は領域の特性の関数として計算することにより得られる画像ヒストグラムで表現する。例えば、１画像の色ヒストグラムは、画素又は画素領域の色を関数とした画素又は領域の頻度分布である。画像のヒストグラムは、ヒストグラムの異なる特性に関する情報をもつ個々の構成要素の組合せを含む、“特徴ベクトル”として知られているベクトル信号として表現することができる。他の画像表現も、特徴ベクトルで把握することができる。特徴ベクトルは、例えば、１画像の平均輝度、画像サンプルの順序付けられたセット、画像からのサンプルの線形又は非線形の組合せの順序付けられ固定されたセット又は部分セット、輝度，色度又は輝度と色度を組合せたサンプル値のヒストグラム、或いは、１画像又は１画像ヒストグラムからの統計的又は確定的パラメータ値の順序セット又は統計的及び確定的パラメータ値の組合わせ順序セットを表現するために用いることができる。
【００７６】
本発明においては、動画シーケンスのフレームは、多次元特徴ベクトルとして表現する方が望ましい。ベクトルランクフィルタ又はベクトルランクフィルタの特別なバージョンであるベクトルメディアンフィルタは、１セット内の各特徴ベクトルから同セット内の他の特徴ベクトルまでの相対累積距離を決定するために使用される。同じセット内の１つの特徴ベクトルから他のすべての特徴ベクトルまでの累積距離は、ベクトルセットの“歪み”を調査中のベクトルから評価して測定する。この歪みは、対応特徴ベクトルで特徴付けられる、動画の１フレームのコンテンツと同じセット内における他のすべてのフレームコンテンツとの均質性（一様性）を示す。
【００７７】
ベクトルランクフィルタの出力は、動画コンテンツの同質性（一様性）を決定するために用いられる。このベクトルランクフィルタは、１セットのフレームのコンテンツを最も代表する動画フレームを認定することができる。また、このフィルタは、一連のフレーム中の次のフレームのコンテンツが実質的に先行フレームと異なっている場合に同質性の決定を容易にし、フレームコンテンツの同質性或いは各フレームによるセットの歪みに従ったセット内フレームのランク付けを容易にする。
【００７８】
最終的には、ベクトルランクフィルタは、動画要約装置のオンラインでの実装を可能にする。これは、代表的な動画フレームをより多くの動画フレームとして生成するか、又は、動画フィールドをシステムに入力することを意味する。オンラインでの実装は、例えば、処理前にすべての動画フレームを獲得して蓄積しなければならないオフラインでの実装よりも有利である。最大の利点は、自己資源（計算機資源、記憶装置資源、通信周波数帯域装置資源等）を監視・評価できる“スマート”受信装置が、資源（リソース）の瞬時の変動に対応してオンライン要約アルゴリズムのパラメータを選択し調整できることにある。実際に、オンライン実装により、受信機はスマートなトレードオフを適時に行うことができ、動画コンテンツとその処理時に使用可能な資源に関して最良の結果であると判断できる動画要約結果が得られる。
【００７９】
ベクトルランクフィルタは、１ベクトルセット内の各々のベクトルを、セット内の１ベクトルから他のベクトルまでの累積距離又は各ベクトルにより生じるセットの相対的歪みによりランク付けるために使用できる。ここで、１≦ｈ≦Ｐとして、Ｐ個のベクトルхhの１セットを与えられると、ベクトルランクフィルタの出力は、ベクトルх(h)であってＰ個のベクトル歪み値中でｈ番目の最小歪み値を有するものと仮定する。もし、１≦ｍ≦Ｐ、ｑを距離測定値を認定するものであるとして、ランクｍ（増加する数値ｍでランク付ける）の歪みがＤ(m)qであるとするならば、Ｄ(1)qは最小歪み、即ち、ランク１の歪みに対応する。同様に、Ｄ(2)qは２番目に小さい歪みに対応する。歪みＤ(p)qは最大歪みに相当し、歪みＤ(h)qは、ｈ番目にランクされた小さい歪みに対応する。最小累積距離で特徴付けられたベクトルはх1であり、２番目に小さい累積距離で特徴づけられたベクトルはｘ2である。最大累積距離で特徴付けられたベクトルはｘpである。
ベクトルｘhに対して、歪みは次式に等しい。
【００８０】
【数１】
0004201454.tif 000002
【００８１】
上式中、ｗはベクトルｘjとベクトルｘ(h)の連結使用に関連する重み付けファクタであり、ｑは距離又は歪みの測定を特定する。ｑの選択は、用途を考慮して決定される。例えば、ベクトル間の絶対値差（ｑ＝１）を合計する方が、差の平方（ｑ＝２）を合計するよりも計算量が少なくて済む。他の用途の場合、ｑは、或る特定の入力ベクトル統計値に関する歪みを最適化するために選択される。同様に、重みｗj,(h)は、入力特徴ベクトルの相対的な重要度を表現するために、或いは、特定のランクで順序付けられた統計値を使用するために選択することができる。
【００８２】
ランクが同じ場合、同じ歪み値を示す全ベクトルに同じランクを与えることができる。この場合、次のランクを調整して、複数のベクトルが“同”ランクを占めている事実を反映させる。例えば、歪みＤiq，Ｄjq，Ｄmqが互いに等しく、第２ランクの歪みを示している場合、各々のベクトルｘi，ｘj及びｘmに全て３のランク（２，３，４のランク値の平均）を与えることができる。その次の最小歪みを生じるベクトルには、３つのベクトルが、ランク２，３，４を占めている事実を反映させて、ランク５を与える。同位を処理する別の方法として、同じ歪みを負担するベクトルに分数のランクを割り当ててもよい。例えば、２つのベクトルが等しいランク２の歪みを生み出した場合、これらのベクトルに、５／２［（２＋３）／２＝５／２］のランクを与え同位であることを示すことができる。
【００８３】
特別なベクトルランクフィルタである“ベクトルメディアンフィルタ”は、１動画セグメント又はショットの最も代表的なフレームを認定するのに特に有効である。このベクトルランクフィルタは、１ショット又はセグメントの境界を決定するのにも用いることができる。ベクトルメディアンフィルタの出力は、１ベクトルセット内の全ベクトルの中で最小の歪みを生じるベクトルを認定する。言い換えれば、ベクトルメディアンフィルタは、ベクトルランクフィルタで特定したランク１のベクトルを特定する。Ｐ個のベクトルхjの１セットが与えられ、１≦ｊ≦Ｐであるとすると、ベクトルメディアンフィルタの出力хkは、その添字ｋが次式を満足するものとする。
【００８４】
【数２】
0004201454.tif 000003
【００８５】
上式において、歪み又は累積距離Ｄiq（ｑ＝１，２，…，∞）は、次式で定義される。
【００８６】
【数３】
0004201454.tif 000004
【００８７】
上式において、ｗj,iは、ベクトルｘj及びベクトルｘiを連結して使用する時の重み付けファクタであり、ｑは歪み又は距離の測定値を指定する。
例えば、ベクトルｘiがＲ次元ベクトルで成分ｘi,r（１≦ｉ≦Ｒ）を有し、重み付けファクタｗj,i及び歪み又は距離測定値ｑが１に等しければ、最小歪み値は次式で求められる。
【００８８】
【数４】
0004201454.tif 000005
【００８９】
ｑ＝２の場合、歪み値は次式で求められる。
【００９０】
【数５】
0004201454.tif 000006
【００９１】
ｑ＝∞であれば、歪み値は次式で求められる。
【００９２】
【数６】
0004201454.tif 000007
【００９３】
ベクトルメディアンフィルタの出力は、セットＰベクトル内の他の全ベクトルに、歪み測定値ｑに関し大局的に“最も近い”ベクトルである。出力ベクトルｘkは、ベクトルセット内の最小歪みと関連するので、すべてのＰ個の入力ベクトル中の最も代表的なベクトルであると考えられる。この特徴ベクトルに対応する動画フレームは、入力特徴ベクトルと関係する動画フレームセット中の最も代表的なフレームと考えることができる。
【００９４】
図１は、本発明の第１の実施形態によるキーフレーム認定方法を説明するための図である。本発明の第１の実施形態において、動画セグメント１０がベクトルメディアンフィルタ１２に入力される。このベクトルメディアンフィルタ１２は、動画セグメント１０の最も代表的なフレームであるキーフレーム１４を認定する。尚、セグメント１０の境界は本発明の方法又は他の方法で確定されているものとする。複数セグメントの各々からのキーフレーム１４は、複数のセグメントより成る動画シーケンスの要約として用いることができる。例えば、２つの認定された時系列境界である時間ｔ（ｊ）及び時間ｔ（ｊ＋１)（但しｊ＝１，２，…Ｎ）を持つ動画のｊ番目のセグメントを想定する。このｊ番目のセグメントは、ここでＦ（ｔ（ｊ）），Ｆ（ｔ（ｊ）＋１），…，Ｆ（ｔ（ｊ）＋Ｍ−１）として表わすＭ個の動画フレームを含んでいる。動画フレームは、ｈ（ｔ（ｊ）)，ｈ（t（ｊ）＋１），…，ｈ（t（ｊ）＋Ｍ−１）として表わすＲ次元特徴ベクトルのセットとして定義することができる。尚、ベクトルｈ（ｔ（ｊ）＋ｉ）は、フレームＦ（ｔ（ｊ）＋ｉ）に関連し、ここで、０≦ｉ≦Ｍ−１である。次の動画セグメント（（ｊ＋１）番目のセグメント）は、ｔ（ｊ＋１）の時点から始まる。ここでｔ（ｊ＋１）＝ｔ（ｊ）＋Ｍで、ｊ＜Ｎである。
【００９５】
ベクトルメディアンフィルタ１２をベクトルｈ（ｔ（ｊ））,ｈ（ｔ（ｊ）＋１），…，ｈ（ｔ（ｊ）＋Ｍ−１）に適用すると、動画セグメント１０に対応するベクトルセット内の最小歪みを生み出すベクトルを認定できる。このベクトルは、Ｆ（ｔ（ｊ）），…，Ｆ（ｔ（ｊ）＋１），…，Ｆ（ｔ（ｊ）＋Ｍ−１）のフレームセットに属し、セグメント１０中のフレームコンテンツを最も代表するフレームに対応する。キーフレーム１４は、動画シーケンス中のセグメント毎に同様にして決定することができる。結果として得られた一連のキーフレーム１４は、各キーフレームが各セグメントの最も代表的なフレームである動画シーケンスの要約を構成する。フレームの個数Ｍは、セグメント毎に変化してよく、入力フレームレートが既知であれば、本実施形態で特定するキーフレームの全数を制御できる。
【００９６】
本発明の第１の実施形態においては、各動画フレームを特徴ベクトルとして特徴付けるステップと、特徴ベクトルグループの歪みを最少にする主要特徴ベクトル（キー特徴ベクトル）を認定するステップと、そのキー特徴ベクトルに対応する動画フレームを主要動画フレーム（キー動画フレーム）として認定するステップとを含んでなる、相対的に一様なコンテンツのフレームを有する動画の１セグメント範囲内で１枚のキー動画フレームを認定する方法を提供する。本発明の第１実施形態の方法により選択されたキーフレームは、１シーケンスの各ショット内のフレームセットのコンテンツを最も代表するフレームである。
【００９７】
図２乃至図５は、本発明の第１の実施形態によるキーフレーム認定方法の一実施例を説明するためのフロー図であり、ここで用いた特徴ベクトルは画像ヒストグラムに基づいたものである。このフロー図で用いる変数には次のものが含まれる。即ち、セグメントの第１フレームの番号ｊ，セグメントの番号ｂ，検討中の現フレームと先行フレーム間の累積距離又は歪みａｃｃ＿ｄｉｆ，現在の最小累積歪みｍｉｎ＿ｄｉｆ，現フレームｎ，（セグメントの開始フレームから現フレームｎまでの）検討中のフレーム数ｍ，ｂ番目のセグメントのベクトル中央値（ベクトルメディアン）ｖｍ（ｂ），ｂ番目のセグメント内のフレーム数Ｐ（ｂ），動画シーケンス内のセグメント数Ｌ，如何なる累積距離でも得ることができない大きな数ＨＵＧＥが変数として含まれている。
【００９８】
本実施形態によるキーフレーム認定方法においては、まず、セグメントの第１フレームの番号ｊ及びセグメントの番号ｂを１にセットする（ステップＳ１）。次に、画像ｊのヒストグラムｈ（ｊ）を計算し、累積歪みａｃｃ＿ｄｉｆ（ｊ）を０にセットする（ステップＳ２）。続いて、ｂ番目の動画セグメント、ｊ番目の動画フレームから始め、累積歪みｍｉｎ＿ｄｉｆを大きな数ＨＵＧＥにセットする（ステップＳ３）。ｎ＝ｊ＋１とし（ステップＳ４）、画像ｎを獲得してヒストグラムｈ（ｎ）を計算、累積歪みａｃｃ＿ｄｉｆ（ｎ）を０にセットする（ステップＳ５）。ｍ＝ｊとし（ステップＳ６）、ヒストグラムｈ（ｍ）とヒストグラムｈ（ｎ）の間の差の絶対ｂｉｎ（ヒストグラム・エントリ）値の合計ｄｉｆを計算する（ステップＳ７）。
【００９９】
続いて、ヒストグラムｎ及びｍに対する累積歪み値ａｃｃ＿ｄｉｆ（ｎ）＋及びａｃｃ＿ｄｉｆ（ｍ）＋をｄｉｆに更新し（ステップＳ８）、ステップＳ９においてａｃｃ＿ｄｉｆ（ｍ）＜ｍｉｎ＿ｄｉｆであれば、現在の最小累積歪みｍｉｎ＿ｄｉｆをａｃｃ＿ｄｉｆ（ｍ）、ｂ番目のセグメントのベクトル中央値ｖｍ（ｂ）をｍとする（ステップＳ１０）。次に、ステップＳ１１において、ｍ＝ｎ−１でなければｍ＝ｍ＋１として（ステップＳ１２）、ステップＳ７へ戻り、ｍ＝ｎ−１であればステップＳ１３へ進む。ステップＳ１３において、ａｃｃ＿ｄｉｆ（ｎ）＜ｍｉｎ＿ｄｉｆであれば、現在の最小累積歪みｍｉｎ＿ｄｉｆをａｃｃ＿ｄｉｆ（ｎ）、ｂ番目のセグメントのベクトル中央値ｖｍ（ｂ）をｎとする（ステップＳ１４）。次に、ステップＳ１５において、セグメント長Ｐ（ｂ）を既知としてｎ＝Ｐ（ｂ）でなければｎ＝ｎ＋１とし（ステップＳ１６）、ステップＳ５へ戻り、ｎ＝Ｐ（ｂ）であればステップＳ１７へ続く。
【０１００】
ステップＳ１７において、ｑ＝Ｌ（セグメント数）でなければｂ＝ｂ＋１，ｊ＝ｎ＋１とし（ステップＳ１８）、ステップＳ２へ戻り、ｑ＝Ｌであれば代表フレームのシーケンスを表示し始める（ステップＳ１９）。続いて、ステップＳ２０においてｂ＝１、ステップＳ２１においてｐ＝１とし、ステップＳ２２において、ｐ＝ｖｍ（ｂ）であれば動画フレームを表示する（ステップＳ２３）。続いて、ステップＳ２４において、Ｐ＝Ｐ（ｂ）（セグメントｂの長さ）でなければ、ｐ＝ｐ＋１として（ステップＳ２５）ステップＳ２２に戻り、Ｐ＝Ｐ（ｂ）であればステップＳ２６へ進む。ステップＳ２６において、ｂ＝Ｌでなければｂ＝ｂ＋１として（ステップＳ２７）ステップＳ２１へ戻り、ｂ＝Ｌであれば処理を終了する。
【０１０１】
本発明の第２の実施形態においては、歪みしきい値を規定するステップと、動画セグメント内の第１フレームの位置決めをするステップと、前記第１フレームを表現する第１特徴ベクトルを規定するステップと、前記第１特徴ベクトルをセグメント特徴ベクトルのセットに含めるステップと、後続動画フレームを表現する次の特徴ベクトルを規定するステップと、前記次の特徴ベクトルを前記セグメント特徴ベクトルのセットに含めるステップと、前記次の特徴ベクトルを前記セットに含めることにより生じる前記セグメント特徴ベクトルセットの歪みを計算するステップと、前記セグメント特徴ベクトルのセットの歪みを前記歪みしきい値と比較するステップとを含んでなる、動画シーケンス内の動画セグメントの境界を決定する方法を提供する。後続フレームを特徴ベクトルとして特徴付けるステップと特徴ベクトルをセットに加えるステップと歪みを計算するステップと歪みをしきい値と比較するステップは、セグメント特徴ベクトルセットの歪みが、歪みしきい値に対し予定した関係に達してセグメントの第２の境界が規定できるまで繰り返される。セグメント化プロセスのために、全動画シーケンスを前もって受信し蓄積する必要はない。キーフレームは、第１又は後述の第３実施形態の方法を適用することにより、動画のセグメント分割と同時に認定できる。
【０１０２】
図６は、本発明の第２の実施形態によるセグメント境界及びキーフレームの認定方法を説明するための図である。本発明の第２実施形態において、動画プロセッサ４０は、動画シーケンス４２を受信する。動画プロセッサ４０は、セグメント内のキーフレームと他のフレーム間の累積距離が所与の歪みレベルを超えないようなキーフレーム４４を自動選択する。これは、セグメント内の全体の歪みが最も代表的な動画フレームに関して制限範囲にあることを保証する。この判断基準は、又、動画セグメントの境界４６をキーフレーム４４と同時にオンラインで決定する技法を提供する。
【０１０３】
本発明の第２実施形態において、動画セグメントの境界４６は予め特定しておく必要はない。動画セグメントの境界４６を決定するために、動画の連続フレームを各々に受信し、閲覧する際に“オンライン”で計算する変数として、この境界４６を指定する。動画が連続するフレームより成る場合、サンプリング技法を用いて順次であるが必ずしも連続でなくてよいフレームを選択できる。最後のフレームをセットに加えることにより生じる歪み及び累積距離が予定されたしきい値を超える時に、初めて、セグメントが終端する境界が検出される。例えば、時間t（ｊ），ｔ（ｊ）＋１，…，ｔ（ｊ＋１）−１，ｔ（ｊ＋１）に対応する１セットの連続した動画フレームＦ（ｔ（ｊ）），Ｆ（ｔ（ｊ）＋１），…，Ｆ（ｔ（ｊ＋１)−１），Ｆ（ｔ（ｊ＋１））をセグメントに分割する。第１セグメント境界は、時間ｔ（ｊ）においてこの方法で確立されると仮定する。時間ｔ（ｊ）に始まるセグメントは、セグメントｊである。動画は１セットの連続した画像より構成されているので、第１セグメントの第１画像はシーケンスの第１フレームと対応すると仮定する。
【０１０４】
後続セグメントの第１セグメントとの境界は、第１セグメントに続く各セグメント毎に第２境界を逐次位置決めすることにより決定することができる。各順次フレームを受信すると、特徴ベクトルの計算をフレームＦ（ｔ（ｊ））に対応するｈ（ｔ（ｊ））より始め、特徴ベクトルのセットに加える。ベクトルのセットの最小歪みをベクトルメディアンフィルタを用いて評価する。ベクトルメディアンフィルタをフレームＦ（ｔ（ｊ）），…，Ｆ（ｔ（ｊ）＋１）に適用して計算した累積最小距離Ｄq(1)が、フレームＦ（ｔ（ｊ＋１））をベクトルのセットに加えたときに初めて、予定したしきい値Ｔを超えるならば、セグメントｊの場合の包含的でないセグメントの終了境界を時間ｔ（ｊ＋１）であると宣言する。言い換えれば、時間ｔ（ｊ＋１）は、最小累積距離がこのフレーム（フレームＦ（ｔ（ｊ）−１））の直前のフレームに対するしきい値Ｔ（Ｄa(1)（ｔ（ｊ＋１）−１）＜Ｔ）より小さく、最小累積歪みがフレームＦ（ｔ（ｊ＋１））をセットに加えた時にしきい値Ｔ（Ｄg(1)（ｔ（ｊ＋１）−１）≧Ｔ）を超えるならば、次の動画セグメント（セグメントｊ＋１）の開始を表わす。
【０１０５】
別の判断基準として、一番最近のフレームに関連する累積距離が、１よりも大きいファクタ（ｋ）と最小距離の積のような、ベクトルのセット内の最小距離の或る関数を越える場合に１ショットの境界を宣言してもよい。言い換えれば、新しいセグメントはｋ＞１として条件式  Ｄqt(j+1)-1＜ｋＤq(1)（ｔ＋（ｊ＋１）−１）、及び、Ｄqt(j+1)＜ｋＤq(1)（ｔ＋（ｊ＋１））で検出される。
【０１０６】
しきい値Ｔ又は係数（ファクタ）ｋは、画像中の雑音電力の関数、又は動画要約によって達成される目標圧縮率の関数、又は雑音電力と目標圧縮率の組合せの関数として選択することができる。
【０１０７】
セグメントの境界が検出されると、第１実施形態で説明したように、そのセグメントのフレームに適用されたベクトルメディアンフィルタの出力が、そのセグメントの場合のキーフレームとなる。その結果、要約が“オンライン”で生成され、動画フレームを“閲覧”中にショット境界が検出されて、各ショット内のフレームが同時に選択されるので、全動画シーケンスを蓄積して検討処理する必要がない。さらに、１フレームを含む１ショットをこの方法で認定できる。
【０１０８】
図７乃至図１０は、本発明の第２の実施形態によるセグメント境界及びキーフレームの認定方法の一実施例を説明するためのフロー図である。特徴ベクトルは、画像のヒストグラムであり、１ショットの境界は、動画セグメント候補内の最大累積距離が、ベクトルメディアンフィルタにより距離乗数ｋを乗じて計算された最小歪み値を超えた時に宣言される。変数は、第１の実施形態（図２乃至図５）で説明した変数と同じである。追加された変数“ｐｒｅｖｉｏｕｓ＿ｖｍ（ｂ）”は、セグメントｂに対し事前に選択されたベクトルの中央値（メディアン）の指標を意味する。この変数は、セグメントの境界が検出されるとキーフレームの位置を記録する。このＪａｖａコードにおいて、１セグメントの境界は常にある特定の予定フレーム数によって生成されるので、このパラメータは、時変で時間と共に減少していく。このＪａｖａコードは、入力動画シーケンスの同質部分を検出するショット境界検出を含んでいる。ここで１ショットは、若干数のセグメントより成り、各セグメントは１個のキーフレームで表現されている。このＪａｖａコードは、又、同じベクトル中央値を何回連続使用したかを監視する追加のメカニズムを含んでいる。このメカニズムは、或る時間中に同一のベクトル中央値を選択することによりキーフレームが得られることを確実にする。後述のＴＡＢＬＥ  Ａは、第２実施形態による方法を実装するためにＪａｖａプログラム言語で書いたサンプルソースコードを提供する。
【０１０９】
本実施形態による方法においては、まず、セグメントの第１フレームの番号ｊ及びセグメントの番号ｂを１にセットする（ステップＳ３１）次に、画像ｊのヒストグラムｈ（ｊ）を計算し（ステップＳ３２）、累積歪みａｃｃ−ｄｉｆ（ｊ），ｐｒｅｖｉｏｕｓ＿ｖｍ（ｂ）を０にセットする（ステップＳ３３）。続いて、ｊ番目の動画フレーム、ｂ番目の動画セグメントから始め、累積歪みｍｉｎ＿ｄｉｆを大きな数ＨＵＧＥにセットする（ステップＳ３４）。ｎ＝ｊ＋１とし（ステップＳ３５）、ステップＳ３６において、動画シーケンスの終了でなければ、ステップＳ３８において、画像ｎを獲得してヒストグラムｈ（ｈ）を計算、累積歪みａｃｃ＿ｄｉｆ（ｎ）を０にセットする。
【０１１０】
続いて、ｍ＝ｊとし（ステップＳ３９）、ヒストグラムｈ（ｍ）とヒストグラムｈ（ｎ）間の差の絶対ｂｉｎ（ヒストグラム・エントリ）値の合計ｄｉｆを計算する（ステップＳ４０）。続いて、ヒストグラムｎ及びｍに対する累積歪み値ａｃｃ＿ｄｉｆ＋及びａｃｃ＿ｄｉｆ（ｍ）＋をｄｉｆに更新し（ステップＳ４１）、ステップＳ４２においてａｃｃ＿ｄｉｆ（ｍ）＜ｍｉｎ＿ｄｉｆであれば、現在の最小歪みｍｉｎ＿ｄｉｆをａｃｃ＿ｄｉｆ（ｍ）、ｂ番目のセグメントのベクトル中央値ｖｍ（ｂ）をｍとする（ステップＳ４３）。次に、ステップＳ４４において、ｍ＝ｎ−１でなければ、ｍ＝ｎ＋１として（ステップＳ４５）、ステップＳ４０に戻り、ｍ＝ｎ−１であれば、ステップＳ４６へ進む。ステップＳ４６において、ａｃｃ＿ｄｉｆ（ｎ）＜ｍｉｎ＿ｄｉｆであれば、現在の最小歪みｍｉｎ＿ｄｉｆをａｃｃ＿ｄｉｆ（ｎ）、ｂ番目のセグメントのベクトル中央値をｖｍ（ｂ）をｎとする（ステップＳ４７）。
【０１１１】
次に、ステップＳ４８において、ａｃｃ＿ｄｉｆ（ｎ）＞（ｋ*ｍｉｎ＿ｄｉｆ）でなければ、ｎ＝ｎ＋１、ｐｒｅｖｉｏｕｓ＿ｖｍ（ｂ）＝ｖｍ（ｂ）とし（ステップＳ４９）、ステップＳ３６に戻る。ａｃｃ＿ｄｉｆ（ｎ）＞（Ｋ*ｍｉｎ＿ｄｉｆ）であれば、セグメントの終端をｎ−１にセットし、ｂ番目のセグメントの長さＰ（ｂ）を蓄積してＰ（ｂ）＝ｎ−ｊ、ｖｍ（ｂ）＝ｐｒｅｖｉｏｕｓ＿ｖｍ（ｂ）とし（ステップＳ５０）、ステップＳ５１においてｂ＝ｂ＋１、ｊ＝ｎとして、ステップＳ３３に戻る。ステップＳ３６において、動画シーケンスの終了であれば、ｂ番目のセグメントの長さＰ（ｂ）を蓄積してＬ＝ｂとし（ステップＳ３７）、代表フレームのシーケンスを表示し始める（ステップＳ５２）。続いて、ステップＳ５３においてｂ＝１、ステップＳ５４においてｐ＝１とし、ステップＳ５５において、ｐ＝ｖｍ（ｂ）であれば動画フレームを表示する（ステップＳ５６）。次に、ステップＳ５７において、Ｐ＝Ｐ（ｂ）でなければ、ｐ＝ｐ＋１として（ステップＳ５８）ステップＳ５５に戻り、Ｐ＝Ｐ（ｂ）であればステップＳ５９へ進む。ステップＳ５９において、ｂ＝Ｌでなければｂ＝ｂ＋１として（ステップＳ６０）ステップＳ５４へ戻り、ｂ＝Ｌであれば処理を終了する。
【０１１２】
本発明の第３の実施形態においては、動画シーケンスの動画フレームを少なくとも１枚の動画フレームを含む相対的に一様な少なくとも１つの動画セグメントに分割するステップと、各動画フレームを表現する特徴ベクトルを規定するステップと、各動画セグメントに含まれたフレームを表現する特徴ベクトルを、前記セグメントを表現する特徴ベクトルのセットに含まれる各特徴ベクトルにより、セットに生じた相対歪みに従ってランク付けするステップと、特定ランクの相対歪みを生み出す特徴ベクトルで表現される動画フレームをシーケンスの要約に含めるステップとを含んでなる、各フレームからの１枚以上のキーフレームを含む動画シーケンスの要約を生成する方法を提供する。この第３の実施形態による方法を用い、キーフレームの階層性を特定でき、各セグメントから選択された多数の最も代表的なフレームを含む各要約により、動画シーケンスの階層的要約が生成できる。
【０１１３】
図１１は、本発明の第３の実施形態によるキーフレームの階層認定方法を説明するための図である。本発明の第３の実施形態において、階層的プロセスにより、ベクトルランクフィルタ７０により形成されたフレームのランクに基づく動画スキミング(要約)法を提供する。このプロセスは、ベクトルランクフィルタ７０に入力される動画セグメント７２の範囲内のフレームの階層７４を認定する。キーフレーム階層７４でのキーフレームのランクベースで動画セグメントから異なる数のキーフレームを取り込む（スキミングする）ことにより一連の階層的要約を構成することができる。この方法は、一連の階層的な要約を容易に生成でき、各逐次要約は、各ショットからのより多くの最も代表的なフレームを含んでいる。ベクトルランクフィルタにより生成されたランク値に基いて、一時的なサブサンプリングメカニズムを駆動した動画コンテンツが結果として得られる。
【０１１４】
図１２は、１セグメント内で各フレームを各フレームにより生じるセグメントの相対的な歪みに従ってランク付けされた動画シーケンスの一例を示す図で、本発明の方法又は他の方法により４つのセグメント６２に分割された１１枚のフレーム６０の動画シーケンスの例を示す図である。ベクトルランクフィルタは、セグメント６２のフレームセットにおいて各フレーム６０により生じる累積距離又は歪みに従って、各セグメント６２内のフレーム６０のランク６４を生成する。この動画を階層要約（スキミング）するために、フレーム６０を構成要素とする動画セグメント６２において、各フレームにより形成される相対累積距離ベースの要約にフレーム６０を選択し、含めることができる。レベル１で動画を選択（スキミング）する場合は、最も粗い要約にランク１のフレーム６６を含める。レベル２の要約には、ランク１のフレーム６６とランク２のフレーム６８を含めることができる。階層の各レベルにおいて、シーケンスの全フレーム６０が最大ランクの要約に含まれるまで追加フレーム６０を、要約に割当てて行く。ランクが大きくなれば、フレーム６０をセグメント６２のコンテンツのより少ない代表である要約に加え、シーケンスを最も代表するフレーム６０で各要約を構成する。
【０１１５】
図１３乃至図１７は、本発明の第３の実施形態による階層的要約のコンパイル及びキーフレームのランク付けの一実施例を説明するためのフロー図である。図１３乃至図１７に用いる変数は、第２の実施形態（図７乃至図１０）につき記述した変数と同一である。
【０１１６】
本実施形態による方法においては、まず、セグメントの第一フレームの番号ｊ及びセグメントの番号ｂを１にセットし、ρ  ｍａｘを０にセットする（ステップＳ７１）。次に、画像ｊのヒストグラムｈ（ｊ）を計算し（ステップＳ７２）、累積歪みａｃｃ＿ｄｉｆを０にｐｒｅｖｉｏｕｓ＿ｖｍ（ｂ）をｊにセットする（ステップＳ７３）。続いてｂ番目の動画セグメント、ｊ番目の動画フレームから始め、累積歪みｍｉｎ＿ｄｉｆを大きな数ＨＵＧＥにセットする（ステップＳ７４）。ｎ＝ｊ＋１とし（ステップＳ７５）、ステップＳ７６において、動画シーケンスの終了でなければ、画像ｎを獲得してヒストグラムｈ（ｎ）を計算し、累積歪みａｃｃ＿ｄｉｆ（ｎ）を０にセットする。次にｍ＝ｊとし（ステップＳ７９）、ヒストグラムｈ（ｍ）とヒストグラム（ｎ）の間の差の絶対ｂｉｎ（ヒストグラム・エントリ）値の合計ｄｉｆを計算する（ステップＳ８０）。
【０１１７】
続いて、ヒストグラムｎ及びｍに対する累積歪み値ａｃｃ＿ｄｉｆ（ｎ）＋及びａｃｃ＿ｄｉｆ（ｍ）をｄｉｆに更新し（ステップＳ８１）、ステップＳ８２において、ａｃｃ＿ｄｉｆ（ｍ）＜ｍｉｎ＿ｄｉｆであれば現在の最小歪みｍｉｎ＿ｄｉｆをａｃｃ＿ｄｉｆ（ｍ）、ｂ番目のセグメントのベクトル中央値ｖｍ（ｂ）をｍとする（ステップＳ８３）。次に、ステップＳ８４において、ｍ＝ｎ−１なければ、、ｍ＝ｍ＋１として（ステップＳ８５）ステップＳ８０に戻り、ｍ＝ｎ−１であれば、ステップＳ８６へ進む。ステップＳ８６において、ａｃｃ＿ｄｉｆ（ｎ）＜ｍｉｎ＿ｄｉｆであれば、現在の最小歪みｍｉｎ＿ｄｉｆをａｃｃ＿ｄｉｆ（ｎ）、ｂ番目のセグメントのベクトル中央値ｖｍ（ｂ）をｎとする（ステップＳ８７）。次に、ステップＳ８８において、ａｃｃ＿ｄｉｆ（ｎ）＞（Ｋ*ｍｉｎ＿ｄｉｆ）でなければ、ｎ＝ｎ＋１、ｐｒｅｖｉｏｕｓ＿ｖｍ（ｂ）＝ｖｍ（ｂ）とし（ステップＳ８９）ステップＳ７６へ戻る。
【０１１８】
ステップＳ８８において、ａｃｃ＿ｄｉｆ（ｎ）＞（Ｋ*ｍｉｎ＿ｄｉｆ）であれば、セグメントの終端をｎ−１にセットし、ｂ番目のセグメントの長さＰ（ｂ）を蓄積してＰ（ｂ）＝ｎ−ｊ，ｖｍ（ｂ）＝ｐｒｅｖｉｏｕｓ＿ｖｍ（ｂ）とし（ステップＳ９０）、値ａｃｃ＿ｄｉｆ，…ａｃｃ＿ｄｉｆ（ｎ−１）を昇順ランク付け、全ての動画フレームに関するランク値を蓄積する（ステップＳ９１）。次に、ステップＳ９２において、最大ランク値＞ρｍａｘであれば、ρｍａｘ＝最大ランク値とする（ステップＳ９３）。次に、ｂ＝ｂ＋１、ｊ＝ｎとして（ステップＳ９４）、ステップＳ７３に戻る。
【０１１９】
ステップＳ７６において、動画シーケンスの終了であれば、ｂ番目のセグメントの長さＰ（ｂ）を蓄積してＬ＝ｂとし（ステップＳ７７）、ｒ＝１とし（ステップＳ９５）、ｒより大きいか又は等しいランク値を有するフレームのシーケンスを表示し始める（ステップＳ９６）。続いて、ステップＳ９７においてｂ＝１、ステップＳ９８においてｐ＝１とし、ステップＳ９９において、セグメントの番号ｂ内の画像ｐのランクはｒより大きい又は等しくないならば、動画フレームを表示する（ステップＳ１００）。ステップＳ１０１において、Ｐ＝Ｐ（ｂ）でないならば、ｐ＝ｐ＋１とし（ステップＳ１０２）ステップＳ９９へ戻り、Ｐ＝Ｐ（ｂ）ならば、ステップＳ１０３に進む。ステップＳ１０３において、ｂ＝Ｌでないならば、ｂ＝ｂ＋１とし（ステップＳ１０４）、ステップＳ９８へ戻り、ｂ＝Ｌならば、ステップＳ１０５に進む。ステップＳ１０５において、ｒ＝ρｍａｘでないならば、ｒ＝ｒ＋１とし（ステップＳ１０６）、ステップＳ９６へ戻り、ｒ＝ρｍａｘならば処理を終了する。
【０１２０】
動画スキミング(要約)システムは、任意特定ランク範囲のフレームをスキミング(要約)した動画要約を表示するために構成される。これは、有効な原動画シーケンスの時間的な圧縮を提供する。この目的のために、動画フレームの各々の歪みランクを蓄積し、表示システムが、指定要約に含まれるべき動画フレームを認定できるようにしなければならない。指数及びランク情報は、動画シーケンスの時間的な階層記述を提供するために、動画シーケンスのデータベースに蓄積できる。
【０１２１】
階層的要約の表示システムは、これとは別に、直線的な“低時間頻度”から“高時間頻度”への分割に従い動画フレームを表示する。各セグメントにおいて、ベクトルランクフィルタのランク１の出力は、セグメントの全フレーム中の最も代表的なフレームであるので、“平均”キーフレームとして閲覧される。反対に、最高ランクの動画フレームは、セグメント内の最も少ない代表フレームであるから、最もコンテンツの詳細を表示するフレームとして閲覧される。このシステムは、非線形であり、時間的フィルタリングを必要としない利点を有する。テーブルＢは、階層的動画要約を生成するＪａｖａソース言語で書かれたコンピュータプログラムを示している。自動セグメント境界検出の実行に加え、このプログラムは、同一ショットに属するキーフレームに、実施形態１のベクトルメディアンプロセスを適用する。実際には、ＴＡＢＬＥ  Ｂに提供されたＪａｖａソースコードにより、動画ショット毎に１個のキーフレームだけを生成して、動画シーケンスの第２の粗い要約を作成する方法を提供する。ＴＡＢＬＥ  Ａのソースコードと同様に、詳細及び租野な動画要約をオンラインで計算する。
【０１２２】
本発明の技法を用いるキーフレームの認定に関しては、キーフレームの階層的要約を、下記の方法を含む他の方法を用いて生成することができる。論文“ベクトル量子化器を設計するためのアルゴリズム（AN ALGORITHM FOR VECTOR QUANTIZER DESIGN）”（１９８０年１月のＩＥＥＥ通信会報）に記載されているLinde-Buzo-Grayのクラスタアルゴリズム（Ｋ平均アルゴリズムとしても知られている）又は、Ratakondaの米国特許出願第０８／９９４，５５８号（１９９７年１２月１９日提出）に記載されているような、クラスタプロセスを強制する連続フレーム内の画像の変化のレートに依拠する方法が含まれる。
【０１２３】
図１８は、本発明による動画シーケンス要約装置の概略を示す図で、図中、８０は要約装置を示す。複数の動画フィールド又はフレーム８２より成る動画シーケンスが要約装置８０の受信機８４に入力される。フレーム８２又は若干の画像を受信機８４からベクトルコンバータ８６に移送し、特徴ベクトルとして各フレームを特徴付ける。動画シーケンスの順次フレーム８２を表現する順次特徴ベクトルを規定し、アキュムレータ８８が、それらの特徴ベクトルをベクトルの拡張セットに累積する。新しい特徴ベクトルがベクトルのセットに加わるごとに、ベクトルフィルタ９０が、ベクトルセットの歪み又は累積距離の測定値を計算する。このベクトルフィルタ９０は、アキュムレータ８８内で、各特徴ベクトルは、特徴ベクトルのセットにもたらす歪みに従って、特徴ベクトルをランク付ける。動画セグメントが入力フレーム８２で認定できなかった場合、セットに追加された一番最近のベクトルに関連する累積距離をベクトルフィルタ９０で計算して、比較器９２でしきい値と比較する。セットに一番最近に追加された特徴ベクトルに関する累積距離がしきい値と事前定義の関係を獲得した時に、セグメントの境界が宣言される。比較器９２でセグメントの境界が宣言されるか、又は、入力８２フレーム内でセグメントの境界が確定されると、ベクトルフィルタ９０の出力を用いて、スキマ９４が、動画シーケンスのコンテンツの最も代表的なフレームを認定し記録する。ベクトルフィルタ９０がより特殊なベクトルメディアンフィルタである場合、スキマ９４は、最も代表的なフレームを各動画セグメントのキーフレーム９６として特定することができる。より一般的なベクトルランクフィルタに基づくベクトルフィルタ９０は、動画セグメントのコンテンツの代表性又はコンテンツの相対的な同質性に従ってフレームをランク付けするのに用いられる。動画スキマ９４は、相対累積距離又はクラスター技法による特徴ベクトルのランクに基づく代表性の階層に従ってフレームを認定することができる。この方法によれば、複数のキーフレーム９６を各セグメントから選択し、複数フレーム８２の階層的要約を生成できる。
【０１２４】
【表１】
0004201454.tif 000008
【０１２５】
【表２】
0004201454.tif 000009
【０１２６】
【表３】
0004201454.tif 000010
【０１２７】
【表４】
0004201454.tif 000011
【０１２８】
【表５】
0004201454.tif 000012
【０１２９】
【表６】
0004201454.tif 000013
【０１３０】
【表７】
0004201454.tif 000014
【０１３１】
【表８】
0004201454.tif 000015
【０１３２】
【表９】
0004201454.tif 000016
【０１３３】
【表１０】
0004201454.tif 000017
【０１３４】
【表１１】
0004201454.tif 000018
【０１３５】
【表１２】
0004201454.tif 000019
【０１３６】
【表１３】
0004201454.tif 000020
【０１３７】
【表１４】
0004201454.tif 000021
【０１３８】
【表１５】
0004201454.tif 000022
【０１３９】
【表１６】
0004201454.tif 000023
【０１４０】
【表１７】
0004201454.tif 000024
【０１４１】
【表１８】
0004201454.tif 000025
【０１４２】
【表１９】
0004201454.tif 000026
【０１４３】
【表２０】
0004201454.tif 000027
【０１４４】
【表２１】
0004201454.tif 000028
【０１４５】
【表２２】
0004201454.tif 000029
【０１４６】
【表２３】
0004201454.tif 000030
【０１４７】
【表２４】
0004201454.tif 000031
【０１４８】
【表２５】
0004201454.tif 000032
【０１４９】
【表２６】
0004201454.tif 000033
【０１５０】
【表２７】
0004201454.tif 000034
【０１５１】
【表２８】
0004201454.tif 000035
【０１５２】
【表２９】
0004201454.tif 000036
【０１５３】
【表３０】
0004201454.tif 000037
【０１５４】
【表３１】
0004201454.tif 000038
【０１５５】
【表３２】
0004201454.tif 000039
【０１５６】
【表３３】
0004201454.tif 000040
【０１５７】
【表３４】
0004201454.tif 000041
【０１５８】
【表３５】
0004201454.tif 000042
【０１５９】
【表３６】
0004201454.tif 000043
【０１６０】
【表３７】
0004201454.tif 000044
【０１６１】
【表３８】
0004201454.tif 000045
【０１６２】
【表３９】
0004201454.tif 000046
【０１６３】
【表４０】
0004201454.tif 000047
【０１６４】
これまでの説明において使用した用語及び表現は説明のためであり制限するものではなく、かような用語又は表現を使用において図示及び説明した特徴の同等な用語及び表現又はその一部を排除する意図は無い。
【０１６５】
【発明の効果】
本発明によれば、セグメント化プロセスのために、全動画シーケンスを前もって受信し蓄積する必要はなく、動画のセグメント分割と同時に認定できる。
すなわち、コンテンツの解析とキーフレームの抽出を両方とも“オンライン（リアルタイム）”で処理でき、動画シーケンス全体を蓄積する必要なく実施でき、又“オフライン”でも実施できる。さらに、本発明によれば、より少ない数の最も代表的なフレームを含む各要約の階層化を簡便に実現できる。
【０１６６】
本発明によれば、ベクトルランクフィルタは、動画要約装置のオンラインで実装できる。これは、代表的な動画フレームをより多くの動画フレームとして生成するか、又は、動画フィールドをシステムに入力することを意味する。オンラインでの実装は、例えば、処理前にすべての動画フレームを獲得して蓄積しなければならないオフラインでの実装よりも有利である。最大の利点は、自己資源（計算機資源、記憶装置資源、通信周波数帯域装置資源等）を監視・評価できる“スマート”受信装置が、資源（リソース）の瞬時の変動に対応してオンライン要約アルゴリズムのパラメータを選択し調整できることにある。実際に、オンライン実装により、受信機はスマートなトレードオフを適時に行うことができ、動画コンテンツとその処理時に使用可能な資源に関して最良の結果であると判断できる動画要約結果が得られる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態によるキーフレーム認定方法を説明するための図である。
【図２】本発明の第１の実施形態によるキーフレーム認定方法をの一実施例を説明するためのフロー図である。
【図３】図２の続きを説明するためのフロー図である。
【図４】図３の続きを説明するためのフロー図である。
【図５】図４の続きを説明するためのフロー図である。
【図６】本発明の第２の実施形態によるセグメント境界及びキーフレームの認定方法を説明するための図である。
【図７】本発明の第２の実施形態によるセグメント境界及びキーフレームの認定方法の一実施例を説明するためのフロー図である。
【図８】図７の続きを説明するためのフロー図である。
【図９】図８の続きを説明するためのフロー図である。
【図１０】図９の続きを説明するためのフロー図である。
【図１１】本発明の第３の実施形態によるキーフレームの階層認定方法を説明するための図である。
【図１２】１セグメント内で各フレームを各フレームにより生じるセグメントの相対的な歪みに従ってランク付けされた動画シーケンスの一例を示す図である。
【図１３】本発明の第３の実施形態による階層的要約のコンパイル及びキーフレームのランク付けの一実施例を説明するためのフロー図である。
【図１４】図１３の続きを説明するためのフロー図である。
【図１５】図１４の続きを説明するためのフロー図である。
【図１６】図１５の続きを説明するためのフロー図である。
【図１７】図１６の続きを説明するためのフロー図である。
【図１８】本発明による動画シーケンス要約装置の概略を示す図である。
【符号の説明】
１０，６２，７２…動画セグメント、１２…ベクトルメディアンフィルタ、１４，４４，９６…キーフレーム、４０…動画プロセッサ、４２…動画シーケンス、４６…セグメントの境界、６０，８２…フレーム、６４…ランク値、６６…ランク１のフレーム、６８…ランク２のフレーム、７０…ベクトルランクフィルタ、７４…キーフレームの階層、８０…要約装置、８４…受信機、８６…ベクトルコンバータ、８８…アキュムレータ、９０…ベクトルフィルタ、９２…比較器、９４…スキマ。
【図１】
0004201454.tif 000048
【図２】
0004201454.tif 000049
【図３】
0004201454.tif 000050
【図４】
0004201454.tif 000051
【図５】
0004201454.tif 000052
【図６】
0004201454.tif 000053
【図７】
0004201454.tif 000054
【図８】
0004201454.tif 000055
【図９】
0004201454.tif 000056
【図１０】
0004201454.tif 000057
【図１１】
0004201454.tif 000058
【図１２】
0004201454.tif 000059
【図１３】
0004201454.tif 000060
【図１４】
0004201454.tif 000061
【図１５】
0004201454.tif 000062
【図１６】
0004201454.tif 000063
【図１７】
0004201454.tif 000064
【図１８】
0004201454.tif 000065