(57)【特許請求の範囲】
【請求項１】
ディジタル動画シーケンスに対するディジタル動画信号を入力するステップと、
前記ディジタル動画信号に基づいて前記ディジタル動画シーケンス内の複数のショットを検出するステップと、
前記ショットの検出結果を用いて、各ショット内に含まれる複数のキーフレームの位置を決定するステップと、
前記決定された位置の複数のキーフレームを所定の基準に従ってレベル付けするステップと、
前記レベル付けされた複数のキーフレームから階層的な動画要約を生成するステップとを含むことを特徴とする階層的ディジタル動画要約及び閲覧方法。
【請求項２】
前記ショットを検出するステップは、
前記ディジタル動画シーケンスに対するヒストグラムを計算するステップと、
前記ディジタル動画シーケンス内のショット境界を検出するステップとを含んでなり、
前記位置を決定するステップは、
各ショット内に割り当てられたキーフレーム数を決定するステップと、
既に指定されている先行キーフレームに対して次のキーフレームの候補フレームが与えられ、該候補フレームのうち、先行キーフレームと該候補フレームとから計算される動き測度が最大となるフレームを、前記ディジタル動画シーケンスの次のキーフレームとして指定することで、前記キーフレーム数のキーフレームにあたる動きのある局面を位置決めするステップとを含んでなり、
前記レベル付けするステップは、
ショットから前記所定の基準によって選択されたキーフレームを削除していくことでレベル付けするステップとし、
前記所定の基準によって選択されるキーフレームは、該キーフレームの先行キーフレームに対して、先行キーフレームと該キーフレームとから計算される動き測度が別途定められる基準測度を超えないキーフレームであることを特徴とする請求項１に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項３】
前記生成した後に、前記階層的な動画要約に用いるキーフレームを閲覧することを含むことを特徴とする請求項１又は２に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項４】
前記入力した後に、ディゾルブイベントを検出し、除去することを含むことを特徴とする請求項１又は２に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項５】
前記ディゾルブイベントを検出し除去した後に、パンイベントとズームイベントよりなるイベント群より取ったイベントを含む前記ディジタル動画シーケンス内のフレームを検出することによって、グローバルな動きを検出することを含むことを特徴とする請求項４に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項６】
パンイベントを検出し、画像モザイクを形成することを含むことを特徴とする請求項５に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項７】
ズームイベントを検出し、前記イベント中のズームの度合を推定し、ズーム要約をコンパイルすることを含むことを特徴とする請求項５に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項８】
前記階層的な動画要約のプロセスからグローバルな動きイベントを除外することを含むことを特徴とする請求項５に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項９】
前記階層的な動画要約を生成することは、前記階層的な動画要約を、最もコンパクトなレベルの要約と粗いレベルの要約と最も細密なレベルの要約とを含む複数レベルの要約に分割することを含むことを特徴とする請求項１又は２に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１０】
特定レベルの要約を選択した後に、ユーザによって前記キーフレームを閲覧することを含むことを特徴とする請求項９に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１１】
前記階層的な動画要約中のキーフレームを、蓄積、検索或いは表示のために、サムネイルに空間的にサブサンプリングできることを特徴とする請求項９に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１２】
前記階層的な動画要約を生成することは、キーフレームをクラスタリングし、より粗いレベルの要約のキーフレームを生成することを含むことを特徴とする請求項９に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１３】
前記クラスタリングは、より粗いレベルにおけるキーフレーム数のコンパクション率を生成することを含むことを特徴とする請求項１２に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１４】
前記クラスタリングは、対ごとのクラスタリングを含むことを特徴とする請求項１２に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１５】
前記のより粗いレベルの要約のキーフレームを生成することは、最大連続差分判定基準を用いてキーフレームを生成することを含むことを特徴とする請求項１２に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１６】
ｔ0＝０、及び第２フレームを第１キーフレームとなるための候補として選択するとして、ｋ1＝１を設定し、ｉ＝１〜Ｋ−１に対して、ｔi＝２ｋi−ｔi-1であるｋi+1を２Ｃ（ｔi）−Ｃ（ｋi）≦Ｃ（ｋi+1）が維持される第１動画フレームとして定義し、ｉ＝Ｋに対して、ｔ’K＝２ｋK−ｔK-1を計算し、ｔK＞２ｋK−ｔK-1＝ｔ’Kでなければ、以前の反復結果を維持して全てのｋiにｔK＝ｔ’Kになるようにオフセット値を与えて終了し、それ以外であれば、ｋiを１だけ増加させて前記定義する処理に進むことにより、キーフレームを認定することを含むことを特徴とする請求項９に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１７】
前記計算することは、前記ショットの最後のキーフレームをｔK-1とｔKの間の中点付近に位置決めすることを含むことを特徴とする請求項１６に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１８】
前記認定することは、（ｎ／Ｋ）番目毎のフレームをキーフレームとして選択することを含むことを特徴とする請求項１６に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項１９】
前記認定することは、興味を引かないショットを検出し、前記階層的な動画要約から前記ショットのキーフレームを除去することを特徴とする請求項１６に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項２０】
前記ディジタル動画シーケンスは、圧縮されたディジタル動画シーケンスであり、前記入力するステップは、ビットストリームのインデックステーブルを生成することをさらに含み、前記計算するステップは、前記圧縮されたディジタル動画シーケンスを部分的にのみ復号することを特徴とする請求項２に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項２１】
前記各ショット内のキーフレームを割り当てることは、前記キーフレームを完全に復号することを含むことを特徴とする請求項２０に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項２２】
前記キーフレームを完全に復号することは、前記動画ビットストリームを構文解析せず、かつ、ビットストリームインデックステーブルを用いて前記動画ビットストリームの一部を復号することにより前記キーフレームを復号することを含むことを特徴とする請求項２１に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項２３】
ＤＣＴに基づいた圧縮動画を前記部分的に復号することは、ヒストグラムを計算するためのＤＣＴ係数のＤＣ値を使用することを含むことを特徴とする請求項２０に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項２４】
前記部分的に復号することは、キーフレームと該キーフレームの参照フレームのみを復号すること含むことを特徴とする請求項２０に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項２５】
前記復号することは、復号器マネージャによって復号することを含むことを特徴とする請求項２０に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項２６】
前記復号器マネージャによって復号することは、ビットストリームインデックステーブルを用いて、全動画ビットストリームの一部の復号及び部分的な構文解析でキーフレームを復号することを含むことを特徴とする請求項２５に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項２７】
前記復号器マネージャによって復号することは、削減されたビットストリームインデックステーブルを生成して、前記動画ビットストリームの一部を構文解析して復号することによりキーフレームを復号するために必要な情報のみを蓄積することを含むことを特徴とする請求項２６に記載の階層的ディジタル動画要約及び閲覧方法。
【請求項２８】
ディジタル動画シーケンスに対するディジタル動画信号を入力する手段と、
前記ディジタル動画信号に基づいて前記ディジタル動画シーケンス内の複数のショットを検出する手段と、
前記ショットの検出結果を用いて、各ショット内に含まれる複数のキーフレームの位置を決定する手段と、
前記決定された位置の複数のキーフレームを所定の基準に従ってレベル付けする手段と、
前記レベル付けされた複数のキーフレームから階層的な動画要約を生成する手段とを含むことを特徴とする階層的ディジタル動画要約及び閲覧装置。
【発明の詳細な説明】
【０００１】
関連出願
１９９８年１月７日提出のＲａｔａｋｏｎｄａの第０９／００４，０５８号の“動画シーケンスにおけるディゾルブ領域の検出（Ｄｅｔｅｃｔｉｎｇ  Ｄｉｓｓｏｌｖｅ  Ｒｅｇｉｏｒｓ  ｉｎ  Ｖｉｄｅｏ  Ｓｅｑｕｅｎｃｅｓ）”。
【０００２】
発明の属する技術分野
本発明は、（ｉ）動画コンテンツの視覚的な認定、（ii）動画のインデクシング、（iii）動画の閲覧ブラウジング及び（ｉｖ）動画の編集等の用途に用いる階層的要約において静止画の各セット毎にディジタル動画シーケンスの表現を決定することに関する。ディジタル動画シーケンスは、動画像圧縮標準（ＭＰＥＧ）により圧縮され、その表現は圧縮ビットストリームの最少復号化によって決定される。
【０００３】
発明の背景
動画のコンパクトな表現は、多数の情報問い合わせと検索の用途にとって肝要である。かような用途の例には、マルチメディアデータベースのアクセスから動画クリップを介したスキミング（高速前方走査）にまで及ぶ。大多数のこれまでの方法は、所与の動画セグメントを“ショット”に分割することに主として重点が置かれていた。各ショットは、そのショットを要約する１枚のキーフレームにより代表される。かように、全動画を通して閲覧する代わりにこれらの代表的なフレームを見ることができる。ショットの検出は高い精度（＞９０％）と僅かな脱漏率（＜５％）で達成される。ヒストグラムに基づく方法は最も成功率が高く、且つ計算量が最少ですむショット検出方法の１つである。種々のショット検出方法間の比較を文献に見ることができる。これらのスキームの多くは，動画ショット境界を定める際にパン，ズーム，ディゾルブ及びフェード等の幾つかの特殊な状況を考慮している。
【０００４】
公知の技法は、ショット境界またはシーン転換を検出し、動画シーケンスを代表するキーフレームのような各ショットからの単一フレームよりなるフレームの集積を使用することに一般的には重点を置いている。各ショットに１枚より多いキーフレームを割り当てることにより、その動画のコンテンツをより良く要約表現できる。かような公知の要約方法は，しかしながら、単層の要約であり柔軟性を欠く。
他の公知の技法は，色ヒストグラムを使用し、ＭＰＥＧビットストリーム（即ち、ＤＣＴ８ｘ８ブロックのＤＣ係数のヒストグラム）からヒストグラムを形成する方法を記述している。これは、Ｉ（フレーム内符号化）フレームに対する比較的直截な方法であるが、参照画像の最少復号化を伴うＰ（予測）フレーム又はＢ（双方向予測）フレームのＤＣ（ゼロ頻度）係数の回復方法が複数存在する。
離散余弦変換（ＤＣＴ）圧縮動画に関する公知の文献は、ワーキングシステムの具体的な実施例については何も記述していない。例えば、認定後にキーフレームは視覚表示のために復号されねばならないが、公知の文献のどれにも、全動画シーケンスを復号することなくビットストリームの任意位置にあり得るキーフレームの効率的な復号機構は記述されていない。
【０００５】
上記スキームの主要な制限は，全てのショットを同等に扱っていることである。大抵の場合、完全なショットを１枚のフレームでは十分に表現できないと考えられる。これは、ショット中の“興味深い動き”量に応じて、各ショット毎に若干のキーフレームを割り当てるアイデアに到達する。最新技術の動画閲覧システムは、動画シーケンスを成分ショットに分割し、各ショットを数枚の代表キーフレームで表現する。この表現を“要約”と称する。
【０００６】
本発明は、１９９６年のローザンヌ国際画像処理会議の会報（６７１−６７４頁）にＬ．Ｌａｎｇｅｎｄｉｊｋ，Ａ．Ｈａｎｊａｌｉｃ，Ｍ．Ｃｅｃｃａｒｅｌｌｉ，Ｍ．Ｓｏｌｅｔｉｃ及びＥ．Ｐｅｒｓｏｏｎによって開示された“ＳＭＡＳＨシステムにおける視覚的探索（Ｖｉｓｕａｌ  Ｓｅａｒｃｈ  ｉｎ  ＳＭＡＳＨ  Ｓｙｓｔｅｍ）”方法（これより後、“Ｌａｎｇｅｒｄｉｊｉｋ”の技法と記す）を改良し拡張するものである。
【０００７】
発明の要約
本発明は、階層的ディジタル動画要約及び閲覧方法であり、その基本構成には、ディジタル動画シーケンス毎にディジタル動画信号を入力することと、動画シーケンスのキーフレームに基づいて階層的要約を生成することを含んでいる。追加のステップとして、ディジタル動画シーケンスに対するヒストグラムを計算することと、ディジタル動画シーケンス内のショット境界を検出することと、各ショット内の割り当てられるキーフレーム数を算定することと、各ショット内の各キーフレームの動きのある位置を決定することと、最大連続差分判定基準によりキーフレームを認定することと、有意な動きの無いショット毎にキーフレームを削減することと、圧縮動画の場合にキーフレームを効率よく抽出することと階層的なキーフレームの要約を用いてショットを閲覧することを含んでいる。
【０００８】
“動画要約”はその動画の代表として使用できる所与の動画シーケンスの最も突出した（顕著な、主要な）フレームを決定することに関する。階層的要約方法は、レベル（即ち、フレーム数）が細部において異なる、複数のレベルを持つ階層的要約を構築するために開示される。最も粗いか最もコンパクトなレベルは、最も顕著なフレームを提供し、最少数のフレームを含んでいる。
【０００９】
本発明の目的は、各レベルが細部の異なるレベルに相当する階層的マルチレベルの要約を生成する方法を提供することにある。
【００１０】
本発明の他の目的は、キーフレームの選択を改善する方法を提供することにある。
【００１１】
本発明の他の目的は、階層的フレームの要約と共に、シーンの動きコンテンツ特にパンとズームを検出して利用しユーザに提示することにある。
【００１２】
本発明のさらなる目的は、各レベルが細部の異なるレベルに相当するＭＰＥＧ−２による圧縮動画の階層的マルチレベルの要約を生成する方法を提供することにある。
【００１３】
本発明のさらなる目的は、ヒストグラムの構築とビットストリームの復号が最少である階層的要約を生成するために、ＭＰＥＧ−２の圧縮動画に直接応用できる方法を提供することにある。
【００１４】
本発明の他の目的は、ＭＰＥＧ−２の圧縮動画の要約を生成する完全で効率のよいシステムを提供することにある。
【００１５】
本発明のさらに他の目的は、ＭＰＥＧビットストリ−ムに対するヒストグラム計算を処理する効率のよい方法を提供することにある。
【００１６】
好適な実施形態の詳細な説明
セマンテックな顕著さ（特徴）を自動捕捉する現在の技術はまだ未熟であるので、動画の要約方法は、色ヒストグラムのような低レベルな画像の特徴に依拠している。動画の要約は、その動画の代表として使用できる所与の動画シーケンスの最も顕著なフレームを決定する方法である。重要な情報を有する特定のフレームは、総数が予め規定されたフレームを含む単一の要約には含まれないようにすることも可能である。
【００１７】
図１を参照する。本発明の階層的要約方法により生成された階層的マルチレベルな要約２０は、重要なコンテンツの情報を失わないように十分に多数のフレームを用いた詳細にわたる細密レベルの要約を提供できるので重要なコンテンツ情報は失われない、と同時に、動画の迅速な閲覧と特定用により粗い又はコンパクトな要約の利用を妨げないようにより粗いレベルの詳細度の低い要約を提供できる。階層的マルチレベル要約２０は、より詳細な要約が必要と判断されて、粗い要約２４及び最も細密な要約２６のようなより細かいレベルの要約が呼び出されるまで提示される、最も粗いレベルの最もコンパクトな要約２２を含んでいる。図１には３つの要約レベルが示されているが、本発明の階層的要約は、１つより多い任意のレベル数を用いることができる。
【００１８】
要約２０は、又、動画シーケンスのデータベースの高速閲覧を容易にし、最もコンパクトな要約に基づく閲覧ができ、ユーザの要求に従って、より詳細なレベルに要約を高めていくことできる。
【００１９】
階層的マルチレベルな要約は、動画の要約を視覚的な対話式で効率よくユーザに提示する方法を容易にする。ユーザはグラフィカルユーザインターフェースを介して要約と対話し、より詳細な要約を要求し、異なるレベルの要約を視覚表示し、任意レベルにおける要約の任意の２枚のキーフレーム間で動画を再生することができる。ここに開示する方法のユーザは要約中のキーフレームの最大数と階層のレベル数を指定できるので、このシステムメモリと資源が制限された用途においても制御可能である。
【００２０】
ここに開示する方法は、非圧縮（又は伸長）動画又はＭＰＥＧ圧縮動画のようなＤＣＴ（離散余弦変換）による圧縮動画又は他の動き補償予測圧縮動画のいずれにも適用できる。ＭＰＥＧ圧縮動画の場合、要約は最少のビットストリームの復号と効率的なキーフレームの復号方法により実行され、計算及びメモリ能力に対する要求が軽減される。ここでは、ＭＰＥＧ−２による圧縮動画を例にとり説明するが、前記の通り、ＤＣＴに基づく任意の圧縮動画に対しても適用可能である。当技術に熟達した人には、ＭＰＥＧ動画への参照が他に規定されていない限り圧縮動画ストリームへの参照であることは理解されよう。
【００２１】
ここに開示の階層的要約方法において、後処理によるフェードのような特殊効果の検出が支援される。かような効果を含むセグメントは、精度に悪影響を与えないように要約プロセスには含まれない。本方法において、要約における最もコンパクトで意味深い表現に対して、パン及びズームセグメントを検出することも考慮される。
動画シーケンスは、静止画像に対して開発された技法を用いて要約フレームに基づいてインデクシングすることができる。複数レベルにより細部変化レベルにおけるインデクシング（索引）の方向に柔軟性を生じる。
【００２２】
本発明の階層的な方法は、最もコンパクトな要約のコンテンツが実際に興味を引くものであればより詳細な要約２４，２６にアクセスする選択肢を持ちつつ、ユーザが最もコンパクトな要約２２を考慮することにより、動画シーケンスの集まりを高速閲覧できる。本発明の方法のユーザは、動画シーケンスの選択セグメントにおいて要約を精錬する柔軟性を有している。
ＭＰＥＧ動画シーケンスを要約するために使用する、“ビットストリームインデックステーブル生成器”と“復号器マネージャ”と云う２つの構成要素が設けられている。これらの構成要素は、視覚的な要約を生成し、次に動画の全体を復号せずに閲覧するようにキーフレームを効率よく復号するために必要である。
【００２３】
図２に、本発明の方法全体３０を要約して示す。この方法は、カメラ一体型レコーダのような動画カメラとレコーダ又は少なくとも動画シーケンスを設置でき、理想的には動画入力３２として使用する大量の動画データを蓄積できる容量を有するコンピュータシステム上で作動することを目的としている。本発明の方法を含む機構をここでは“システム”と呼ぶ。入力動画３２は、フェードイン又はフェードアウトのような特殊効果を含むフレームは、擬似ショット境界と擬似キーフレームを生じる結果を招くので、まず、かようなフレームを検出し除去するための処理をする（３４）。かようなフレームは大域的（グローバル）な動きイベントとして分類して、次にさらなる処理から除外する。次のステップは、ヒストグラムの計算である（３６）。画像色ヒストグラム、即ち、色分布は、動画フレームを代表する特徴ベクトルを構成して、ショット境界の検出３８とキーフレームの選択に使用される。ショット境界の検出３８は、スレッシュルド（閾値）方法を用いて行い、連続するフレームのヒストグラム間の差を比較する。所与のキーフレーム総数（ユーザ指定）４０で、各ショットに、良く知られた技法により、ショット内の“動き（アクション）”に応じてキーフレーム数（４２）を割り当てる。細密レベルのキーフレームの選択４４は、Ｌａｇｅｎｄｉｋの技法を改良バージョンを用いて行う。ここに開示する実装は、この方法の改良バージョン、即ち、細密レベルのキーフレームの選択方法を拡張した、後でより詳細に説明する図４に示すような新しい追加のステップを含んだ技法を用いる。
【００２４】
図１を再び参照する。画像のモザイク５１を生成する結果をもたらす自動パン／ズーム４６とズーム要約５２は任意選択ステップであり後で説明する。次のステップは、キーフレームの階層化４８、即ち、細密レベルの要約より粗い細部での要約を生成する新しい方法である。このプロセスについても後で詳しく説明する。これは、ベクトル量子化の主題の変形に基づいている。細密レベルと粗いレベルの要約は、所与のショットに対し決定され、動画シーケンス中の他のショットに対してもこのプロセスが繰り返される（ブロック５０）。追加のステップは、階層的要約の閲覧（ブロック５３）とプロセスの終了（ブロック５４）を含んでいる。
【００２５】
自動パン／ズーム処理
自動パン／ズーム処理ステップ４６の詳細は図３に示す通りであり、ディジタル動画シーケンスにおけるパン及びズームのイベント（事象）の検出を含んでいる。グローバルな動きを含むフレームを検出する（５６）。これは、グローバルな動きの影響を受けるフレームを特定することを目的とした予備的選抜方法である。これらのフレームは、グローバルな動きがパン検出器で検出（５８）されるようなカメラのパンによる動きであれば画像モザイクを用いてコンパクトに表示でき、或いは、ズーム要約５２、即ち、ズーム検出器６０で検出されてズーム評価器（ズーム推定器）６６により編集されるような動きであれば、ズームイン又はズームアウトシーケンスの最初と最後のフレームを用いてコンパクトに表示できる。従って、モザイクの形成６２は、グローバルなパンの動きを示すこれらのフレームを対象にするだけであり、画像モザイク５１をもたらす。画像モザイク５１又はズームイン又はズームアウトに関係するフレームは、細密レベルの要約からは除外される（ブロック６４）。理由は、細密レベルの要約はさらに処理してより粗い、よりコンパクトなレベルの要約を形成するからである。
【００２６】
他の実施形態において、パン／ズーム処理４６は、自動ではなく対話形式で実施できる。ユーザは、選択された細密キーフレーム要約４４から、キーフレームを選択できる。それらキーフレームは、パンシーケンスの開始と終了を形成し、システムはこれに応え画像モザイク５１を形成し、ユーザに提示する。ユーザは、フレーム番号Ｋ及びＬ、即ち、カメラがパンした始点と終点の２つのキーフレームを認定又はタグ付けすることができる。モザイク形成器６２はモザイク形成時にフレーム番号Ｋ−ｎとＬ＋ｎ（ｎは予め定められたオフセット値）の間のフレームを考慮する。モザイク形成器６２は、通常の技術を有する者には良く知られている画像ステッチング技法により実装できる。ズームの場合、パンの場合と同様に、ユーザは開始と終了のフレームを手動で指定できる。自動ズーム検出アルゴリズムを採用してもよいし、このアルゴリズムもまた通常の技術を有する者には良く知られている。
【００２７】
図５に階層的要約の形式７０を示す。この階層的要約は、階層的キーフレームレベルに分割される。ユーザには先ず最もコンパクトな（最も粗い）レベルの要約７２、即ち、最もコンパクトな要約が可能な場合、画像モザイク５１及びズーム要約５２と共に提示される。次に、ユーザは、ここでは粗いレベル７４と称するより細かなレベルで親フレームにタグを付け、子フレームを見ることができる。最も細密なレベル７６のフレームのタグ付けにより、動画の再生、例えば、ｊ番目のキーフレームを最も細密なレベルでタグ付けすると、ｊ番目と（ｊ＋１）番目の間のフレームが再生される。実際のＧＵＩ実装において、親子関係は、表示時に明示できる。ここで用いるように、“タグ”又は“タグ付け”は、特定のフレーム上でクリックするように、コンピュータモニタ上で特定のオブジェクトを認定することにより達成される。階層的要約におけるキーフレームは、蓄積コストを有利にし、要約の高速検索・表示を実現するために、空間的にさらに“サムネール”にサブサンプリングする。動画シーケンスの通常の再生は、最も細密なレベルで行われるが、より粗いレベルでも実施できる。
【００２８】
非圧縮動画の入力
本発明の第１の実施形態は、階層的ディジタル動画の要約と閲覧に対する“画素ドメイン”法として記述し、非圧縮動画の入力（３２）を要する。
全動画シーケンス用に用いられるキーフレームの総数は所与である（通常蓄積空間要求条件により決まる）と仮定する。Ｌａｎｇｅｎｄｉｋの技法は３つの主要ステップ、即ち、
１）ショット境界の検出と、
２）各ショットに割り当てられるキーフレーム数の決定と、
３）各ショット内のキーフレームの位置の発見のステップを持つ。
【００２９】
図４に示す本発明に用いられるこの技法８０は、３ステップの反復方法（８２）を含んでいる。ショット境界の検出（図２の３８）は、動的閾値によるヒストグラムに基づく方法を用いてなされる。シーケンスの最初のｎフレーム（通常ｎ＝３）は、ショット境界に対応しないものと仮定する。平均動き測度Ａmと動き測度の標準偏差Ａsdは、最初のｎフレームに対する後述する動き測度の平均と標準偏差を各々計算して定める。閾値はＡm＋αＡsdに設定する。この閾値により境界が検出されれば、次のショット用の新しい閾値を、この新しいショットの最初のｎフレームを用いて、同じやり方で決定する。パラメータαは、通常１０に設定する。
２つのヒストグラム（ｈ1とｈ2）間の動き測度（Ａ（．，．））を（ｌ1ｎｏｒｍ）とする。
【００３０】
【式１】
0003719933.tif 000002
【００３１】
ｎフレームＳ1，…，Ｓnを持つ１ショットＳに対する累積動き測度（Ｃ（．））は次式で計算される。
【００３２】
【式２】
0003719933.tif 000003
【００３３】
各ショット毎の累積動き測度と各ショットの累積動き測度の合計がかようにして算定される。特定のショット“ｓ”に割り当てられたキーフレーム数（ブロック４２）は、そのショット内の累積動き測度の相対量に比例している。
ショット内のキーフレームの動きのある位置の位置決めはｌ1の最小化問題として記述できる。各キーフレームは連続した１セットの動画フレームを代表する（代替する）。動画フレームのこの連続のセットの統合が完全なショットである。連続動画フレームの各セットが１枚のキーフレームで代表されるので、動画フレームの１連続セット内の動き量を小さくしたいと考える。動画フレームの１連続セット内の“動き量”が多すぎると、１枚のキーフレームではその動き量を十分に代表できないことがこの背後にある理由である。かように、１ショットに割り当てられるキーフレームの総数（そのショットが分割された連続セット数と同じ数）が与えられれば、動画フレームの該当連続セット内の“動き”を最少にするキーフレームを発見する最小化手順を使用する。Ｋ枚のキーフレームを１ショットｓ内に位置決めするものと仮定し、キーフレームの位置をｋj（ｊ＝１，…，Ｋ）とする。さらに、ｋjのキーフレームで代表される動画フレームの連続セットをｔj-1，…，ｔj−１とする。換言すると、［ｔj-1，ｔj−１］は、キーフレームｋjにより代表されるショットセグメントである。以下のコスト判定条件式が全ての可能なｔjに対して最少となるべきである（ｋjは、ｔjを選択することにより即ち、ｋj＝（ｔj＋ｔj-1）／２で決定する）。
【００３４】
【式３】
0003719933.tif 000004
【００３５】
ｔ0とｔKはショットの最初と最後のフレームである（従って、定数である）。上記コスト判定条件式中にｋj＝（ｔj＋ｔj-1）／２を代入し、最適解は、２Ｃ（ｔi）−Ｃ（Ｋi）≦Ｃ（Ｋi+1）を満足する。
最小化を実行するために、Ｌａｇｅｎｄｉｊｋの技法と異なる、下記のステップを対話式で実行する。
１．ｋ1＝１に設定する。（ｔ0＝０、第２フレームを第１キーフレームとなるための候補として選択するものと仮定する。）
２．ｉ＝１〜Ｋ−１に対して、
ｔi＝２ｋi−ｔi-1
ｋi+1を、２Ｃ（ｔi）−Ｃ（ｋi）≦Ｃ（ｋi+1）を満たす第１動画フレーム（即ち、ｔiより大きい最少の下付き添字ｎを持つ動画フレーム）と定義する。３．ｉ＝Ｋに対して、ｔ'K＝２ｋK−ｔK-1を計算する。ｔK＞２ｋK−ｔK-1＝ｔ'Kであれば、ｋ1を１だけ増し、ステップ２に進む。そうでなければ、先の反復結果を保持し、全てのｋiにｔK＝ｔ'Kとなるようにオフセット値を与えて停止する。
【００３６】
この最小化は図６に示すように有限数のステップで実行する。累積誤差は１ショット内の非減少関数である。かように、上記の最小化手順は、累積誤差曲線９０に対し最良（ｌ1に関し最良）の段階近似を与えるキーフレームｋjを発見することを目的とする。これにより、ショット内の“動き”量に適応変化するキーフレームｋjの分布が得られる。式３で表現される最小化領域は９２である。
【００３７】
上記の３つのステップの意味は下記の通りである。ショットの最後のキーフレームはｔK-1とｔ＝ｔKの間の中点にできるだけ近づけなければならない。ｋｉを増加し、最初はこの中点を超えるまでステップ２と３を反復し、その後先の反復結果をとり、最後のキーフレームが中点と一致する、即ち、３ステップ反復法により決定されるｔK＝２ｋK−ｔK-1とｔ'KがｔKと一致するようにオフセット値を与える。
【００３８】
先のアルゴリズムに導入したもう１つの新規点は、特定のショットに十分多数のキーフレームを割り当てたことによりｋi＝１であってもショット境界を超えられる場合に関する。この場合、簡単なスキームを用いてキーフレームが等間隔になるように配分する。この簡単なスキームにおいて、１ショットがｎ枚のフレームを有し、Ｋ枚のフレームを割り当てる場合、（ｎ／Ｋ）枚毎のフレームをキーフレームとして選択する。
【００３９】
キーフレームの選択に関する改善
Ｌａｇｅｎｄｉｊｋ技法において、ｔj-1とｔj−１が与えられた１ショットセグメント［ｔj-1，ｔj−１］に対するキーフレームは常にｋj＝（ｔj＋ｔj-1）／２に位置する。言い換えれば、キーフレームは、常に、そのセグメントのフレームの代表としてセグメントの中央にあるように選択される。しかしながら、累積誤差の定義に戻れば、累積誤差は連続するフレーム間の絶対変化にのみ依存する。かように，１セグメントの中央の１枚のキーフレームは１フレームより多いフレームに分離された２枚のフレーム間の実際の変化を現わすことはできない。１名のレポータが話している動画シーケンスを考える。例えば１０フレーム離れた２枚のフレームがあり、両フレームは、口を開いているレポータを示していると仮定する。結果として、２枚のフレームは、非常に小さい変化又は“動き”を表しているのは明らかである。しかしながら、この２枚のフレーム間の累積変化は連続するフレーム間の絶対変化の合計を表すので前記２枚のフレーム間の累積変化は大きい。これら２枚のフレームは、“セグメントの中央”規則が適用される場合、キーフレームとして選択されたフレームの内にあることが可能である。かように、“セグメントの中央”フレームをキーフレームとして闇雲に選択するとキーフレームの選択を誤ることになる。
【００４０】
この実施形態の場合、３ステップ反復法によって得られた各ショット内の区切り点の結果集合｛ｔ0，ｔ1，…，ｔk｝を考慮する。先行キーフレーム（ｋj-1）から（動き測度Ａ（，）の点で）最も異なるセグメント（ｔj-1，ｔj−１）中のフレームをｋjに位置するキーフレームとして選択する。この方法は、先行キーフレームからの最大差を取るので、ここでは“最大連続差分”基準（ブロック８４）と記す。第１キーフレーム（ｋ1）は、３ステップ反復法により決定された１フレームとする。この方法は、連続キーフレームが互いに十分異なり、従って、冗長度をできる限り減少させることを保証する。
【００４１】
有意な動きのないショットセグメント中のキーフレーム数の低減
Ｌａｇｅｎｄｉｊｋの技法は、上述したように累積誤差に完全に依拠しているために、実際には極めて近似の２枚のフレーム間に大きな誤差があると報告することがあり得る。上述の技法は、与えられたショットセグメント中の最も興味を引くフレームを選択するには良いが、ショットセグメント内の動きの観点からショット全体が“興味を引かない”状況は解決しない。例えば、連続キーフーム間の十分有意な変化をもたらさない僅かなカメラの動きによる誤差の蓄積があり得る。
有意動きの無いショットを無視するために、それらのショットを認定し、それらショット用キーフレームを削減し（ブロック８６）、最も細密なレベルのキーフレームを残す（ブロック４４）。これは、２枚の所与のキーフレーム間にある連続動画シーケンスフレーム間で測定して分析された動き測度の平均と標準偏差を推定することによりなされる。２枚のキーフレーム間に十分“有意な動き”が存在すれば、原動画シーケンス中の連続フレーム間の動き測度は有意であり、即ち、そのキーフレームを最大連続差分基準（最大連続差分基準）に従い認定する（ブロック８４）。
Ａmがフレームｋi及びｋi-1間の平均動き測度であり、Ａsdを同動き測度の標準偏差とすると次式が得られる。
【００４２】
【式４】
0003719933.tif 000005
【００４３】
ただし、２枚のキーフレームｋi及びｋi-1間の動画シーケンスフレーム数をｓとし、２枚のキーフレーム間のコンテンツが興味深い場合である。ショットセグメントが前記の観点から興味を引かないものであれば、その特定のキーフレームを除去しそのショットセグメントを次のショットセグメントに結合する。
上式中のパラメータβは定数である。βが１より小さければ、大きな差異をもつキーフレームのみを残し、過度の削減を招く。ここで報告するシミュレーションの場合βの値は２.０に選定する。ショットに割り当てられたキーフレーム数が小さい場合は、キーフレーム間の距離、従って、キーフレーム間のフレーム数ｓが増大するために、ショット割り当てキーフレーム数が小さければ数量（ｓ／β）は増大する。（ｓ／β）が到達し得る最大値を、αに設定する。このαは、キーフレームの削減数を制限するためにショット境界検出のための閾値を規定する際に使用する係数である。
【００４４】
さらなる実験により、直線閾値スキームは、キーフレームの総数選択に不等なキーフレームの割り当てをもたらすことが明らかになった。この問題を軽減するために、上記削減法により消去できるキーフレームの総数の最大百分率に制限値ＭＡＸＥＲＡＳＥ＝０.３を設定する。この制限の場合、ＭＡＸＥＲＡＳＥ＝０.３に相当するフレームの最大冗長度３０％が除去される。“最大冗長度”の意味は、Ａ（ｋi，ｋi-1）が最も冗長なキーフレームに対して最少であると云うことを意味する。この場合、ｋiは除去される冗長キーフレームである。
この技法は、高動きシーケンスに応用すると、動きは殆ど構成的であり、即ち、全ての消去されるキーフレームに対して式（４）は満足されており、従って、冗長度は皆無である。
【００４５】
階層的要約と閲覧
前記の開示は、知的な“動画インデクシング”システムを記述しているが、かようなシステムは、動画フレームの当初の完全なシーケンスよりもよりコンパクトな動画コンテンツ表示である動画フレームの固定シーケンスのみを提供する。動画シーケンスを通して観察しコンテンツが変化するに従って、動画シーケンスにおける関心度レベルも変化するので、大抵の場合、上記の表示はまだ不適切である。また、特定の動画コンテンツの関心度レベルは予測できない。少女が猫を可愛がっており、カメラが少女から猫にパンする動画シーケンスを考える。１人の視聴者は少女ではなく猫をより接近して見たいと思い、もう１人の視聴者は猫ではなく少女をより近くで見たいと思い、さらにもう１人の視聴者は両方を見たいと思うかも知れない。目標は、これらの視聴者の誰かが見る“興味の無いフレーム”の数を最小にすることである。
【００４６】
同じ動画インデックスシステムに対する種々の視聴要求を調和させ満足させるために、マルチ解像度動画ブラウザ（図２のブロック５３）を提供してユーザが指定レベルの要約を選択して階層的要約を閲覧できるようにしている。これは、単なるインデックスシステムに代わるブラウザである。視聴者は、詳細の粗いレベルから始め、視聴者にとってより興味深いキーフレームシーケンス部分でマウスをクリックして詳細を拡張することができる。詳細１レベルより多い明細レベルが要求されて、視聴者が視聴者の選択したペースで閲覧できる。最も細密なレベルのキーフレームも検出できる。より粗いレベルにおいて、細密レベルにおける同様なキーフレームが集合し、各クラスタは１枚の代表キーフレームにより代表される。
【００４７】
このクラスタリング問題を解決するために、よく知られているＬｉｎｄｅ−Ｂｕｚｏ−Ｇｒａｙ（ＬＢＧ）のアルゴリズム（又はＬｌｏｙｄのアルゴリズム又はＫ平均アルゴリズム）の変更を提案する。同様な画像をクラスタさせることが望ましいことに留意する。ヒストグラムにより画像を表現し、類似の画像は類似のヒストグラムを有すると仮定する。各ヒストグラムを関連フレームの特徴ベクトルとして扱い、最も細密なレベルのＮヒストグラムに代わる粗いレベルにおける代表的ヒストグラム（Ｎ／ｒ）を発見する。尚、Ｎは最も細密なレベルにおけるキーフレーム数である。パラメータ‘ｒ’はコンパクション率（簡潔化率、若しくは、圧縮率）であり、ユーザによりプログラムに供給されるパラメータである。これからの議論において、各キーフレームをそのヒストグラムのベクトルとして表現する。
【００４８】
例えば、連続なｐ個のベクトル（時間において連続）に代わる１個の代表的ベクトルを選び出すことが望ましいので、これは、正規のクラスタリング問題と異なっている。正規のＬＧＢの場合は、１つの代表ベクトルに量子化したベクトルに関する“連続性”の制限は何もない。正規のＬＢＧ反復に近似の、下記の反復法は常に収斂する。この３ステップ反復法は、ここでは“対ごと”のＬＢＧ又はＰＬＢＧと記述する。ＰＬＢＧはＬＢＧと同じ極小問題を有することに注意すべきである。幸運なことに、反復後の“クリーンアップステップ”をこれを迅速処理するために用いることができる。まず、ヒストグラムベクトル列を等間隔で区画することから始める。例えば、簡潔化率３の場合、各区画は、（最後の１つ又は２つの区画を除き）３つのヒストグラムベクトルを含んでいる。次に、ＰＬＢＧ法の次のステップに進む。
【００４９】
１．各ベクトルセットに対して代表ベクトルとして重心（又は平均）ヒストグラムを指定する。
２．最初の区画から開始し、各区画を、区画の何れかの側の２つの隣接セット（用語“対ごとの”はここに由来する）に対する合計基準ｌ2が最小になるように調節する。数学的に、Ｈi-1がセット（ｔi-1，ｔi）中のベクトルに対する代表ベクトルで、Ｈiがセット（ｔi，ｔi+1）中のベクトルに対する代表ベクトルであれば、ｔiを各セット中のベクトルの対応代表ベクトルまでの自乗距離の総計が最小になるように調節する。
３．前記調節に続き、任意区画につき、ｔi＝ｔi+1であれば、ベクトルの代表セットからＨiを除去する。ｔi-1＝ｔiであれば、代表ベクトルセットからＨi-1を除去する。
４．ステップ１に戻る。
停止基準は、歪の減少量又は固定反復回数の何れかに基づく。前述の通り、１０回反復後停止する。各反復時に、歪（各セットの代表ベクトルとセット中の対応ベクトル間の基準ｌ2）は減少する。かように、各反復における総歪は、減少シーケンスを形成する。さらに、歪は、常にゼロより大きいかゼロに等しい。従って、シーケンスは、基本実解析による限界を有する。“反復に対する極小（従って固定点）が存在するか？”と云う問題は、純粋に学術的な問題であり、読者は、かような議論のための文献を参照することになる。除去ステップ（ステップ３）は、実際に、当初期待又は選択したより若干であるが少ないキーフレーム数となる結果を得た。
【００５０】
上記の方法において、停止後、代表ベクトルに最も近似したヒストグラムベクトルを有する第１クラスタ中のフレームを第１キーフレームとして選択する。後続クラスタに対するキーフレームも同様にして決定できる。“先行キーフレームとの最大差分判定基準”により後続クラスタ内でキーフレームを選択すると最良の結果が得られる。ここで、差分は動き測度で表現される。
【００５１】
上記反復の公式化において、最終区画が常にシーケンス中の最後のベクトルに固定されるので、最終セットが不適当に表現される可能性がある。同じことがショットの第１フレームに対しても言えるが、ここで報告する実験においては、そのような状況は観察されなかった。かように、この問題を解決するために、反復終了後にもう１つのステップを設ける。この最終ステージにおいて、代表ベクトルの最後にもう１つ代表ベクトルを付け加える必要があるかテストする。特に、最後のベクトルを新しい代表として加えることを検討する。最後のベクトルと先行代表ベクトルとの差がθＸ（連続代表ベクトルの全ての対（ペア）間の差の平均）より小さければ、最後のベクトルの追加を認める。シミュレーション時θを０.７５に選定する。θは０から１までの間で変化できる。
ベースライン法（Ｌａｇｅｎｄｉｊｋ）は、３枚キーフレームを指定し、ベースライン法を動画シーケンスに適用すると、関心を引く特徴をもつシーンを見失う。その結果は、上記の方法を用いて生成した３枚キーフレームによる複数レベル階層の最もコンパクトな（最も粗い）レベルよりも劣る。さらに、複数レベルの要約を生成するために異なる数のキーフレームを得るには、ベースラインアルゴリズムを複数回用いるよりも、提案の階層的方法を用いる方がさらに有効である。
【００５２】
ブロックヒストグラムの動き測度
ヒストグラムに基づく動き測度は全ての状況に適する訳ではない。例えば、黒い対象が白い背景に対して移動すると、ヒストグラムに基づく動き測度はその運動を記録できない。細かな動き、例えば、手のジェスチャ又は頭の動きを捕捉したい状況では、より良い動き測度を得る有利さを持っている。
【００５３】
ブロックヒストグラムはショットの検出のために提案された。しかしながら、ブロックヒストグラムはショットの検出には感度が高すぎて、多数の偽りの警告を発する。ブロックヒストグラムの背後にあるアイデアは、画像を若干数のブロック（通常４又は１６）に分割し、動き測度を各ブロックに対する絶対値のヒストグラム差の合計をとして規定する。ブロックヒストグラムが単純な全体ヒストグラムに基づく方法では、捕捉できない動きに対してより鋭敏であることは容易に観察できる。ブロックヒストグラムを図４の３ステップ反復法に示すように、最も細密なレベルのキーフレームに対してのみ適用した。ブロックヒストグラムを用いる利点は、１つのフレームの代わりに動画フレーム当たり４又は１６のヒストグラムを取り扱う必要があるので、計算及びメモリに関し、より集中的であることである。しかしながら、実験シーケンスにおいては、このブロックヒストグラム法は重要な性能改善をもたらさなかった。
【００５４】
要約のための動き特性の使用
パン又はズームのような特に重要なケースはこれまで検討されていない。カメラパンの場合、インテリジェントブラウザは、（ａ）一回のパンで複数のフレームを検出し、（ｂ）観察目的のために画像モザイクに変換するパンフレームに対するオプションを提供する。パンとズームのどちらの検出も動きベクトルの計算を含んでいるので、パンの検出と共にズームの検出は、大量の追加計算による過負荷を生じることなく実現できる。
【００５５】
シーケンス内の各フレームに対する動きベクトルを見つけ出すには、計算を要するので、支配的な又はグローバルな動きを持つフレームの全ての可能なシーケンスを先ず検出する予備スクリーニング（予備選抜）法を開発する。支配的な動きは（ａ）パン又は（ｂ）ズーム又は（ｃ）他の特別な編集効果により発生するので、検出したシーケンスをより詳細に調べ、パン又はズームの存在を決定する。
【００５６】
支配的な動きのための予備スクリーニング
支配的な動きは、動画フレーム内の各画素が輝度の変化を経験することを意味する。輝度の変化は通常ズーム又はカメラの動きによって生じる。この変化は、動画フレームのエッジ画素において最も顕著である。この方法は、各画素を観察し、その画素がエッジ画素かどうかを決定し、エッジ画素であれば、現画素と先行フレーム中の同一位置の画素との間の差を検出する。エッジ画素における差の絶対値が閾値（ＰＺ＿ＴＨＲＥＨ＝１５）より大きければ、その画素は動きを有すると指定される。画素がエッジ画素かどうかを決定するために、その画素においてＳｏｂｅｌエッジ検出演算子により得た数値を閾値（ＰＺ＿ＴＨＲＥＨ＝５０）と比較する。もし、ＰＺ＿ＴＨＲＥＨを減じると、偽の警報が発せられることがある。ＰＺ＿ＴＨＲＥＨ１を減じると、画素は強いエッジに属しておらず、動きが大きな輝度変化を生じないので、かような画素における有意の変化は無くなる。特別なフレームがパンフレームであるかを決定するために、エッジ画素の総数に対する、動きを有するものとして分類される画素数間の割合（パン率）に関する閾値を設ける（ＰＺ＿ＴＨＲＥＳＨ２＝０.９）。
【００５７】
この割合が、パンの間、一貫してＰＺ＿ＴＨＲＥＳＨ２を横断するのを確認するのに必要なもう１つのステップは、近傍にふくらませることである。言い換えれば、ＮＥＩＧＨｘＮＥＩＧＨ（ＮＥＩＧＨ＝５）内の任意画素の輝度変化がＰＺ＿ＴＨＲＥＳＨより大きければ、エッジ画素は動きを有する。特定数より短いフレームシーケンスは拒絶される（ＴＯＯ＿ＭＡＮＹ＿ＦＲＡＭＥＳ＿ＮＯＴ＿ＰＡＮＺＯＯＭ＝５）。サブサンプリングは、計算負荷をさらに軽減するために用いられる。
【００５８】
パン検出
このパン検出法は公知技法のバリエーションである。パンを検出するために、サブサンプリングした画像位置における動きベクトルを考察する（ＳＰＡＣＩＮＧ＝２４）。動きベクトルを決定するために使用する方法は、単純なブロックマッチング法である（ＢＬＫＳＩＺＥ＝７ｘ７、ＳＥＡＲＣＨＳＩＺＥ＝２４ｘ２４）。先行フレームのパンベクトルに基づく探索サイズを変化させる。先行のパンベクトルが（ＳＥＡＲＣＨＳＩＺＥ／２）−２より小さければこの探索サイズを半分し、先回のパンベクトルが（ＳＥＡＲＣＨＳＩＺＥ／２）−２より大きければ当初の（大きな）探索サイズを回復する。このバリエーションにより性能の低下が生じることはない。
【００５９】
パン検出の場合、許容範囲内のモード動きベクトルと（最も頻繁に生じる）平行な全ての動きベクトルを見つけ出すことが提案されている。かような動きベクトルの数が特定の閾値より大きければ、パンが検出される。しかしながら、１回のパンの場合、動きベクトルは並行しているだけでなく、同一に近い大きさを有している。従って、全並行動きベクトルを考察する代わりにモード動きベクトルの小さな近傍を調べる。モード動きベクトルの値に等しいベクトルが生じれば、恣意的な決定がなされる。モード動きベクトルの近傍サイズはＶＡＲＮ（＝４）によって制御される。ＶＡＲＮの値が大きければ、モード動きベクトル周りの近傍は小さくなる（我々の場合のＶＡＲＮ＝４は３ｘ３の近傍を意味する）。ＰＡＮＲＡＴＩＯ（パン率）（＝.５）は、動きベクトル総数に対する近傍内動きベクトル数間の割合に関する閾値を決定する。パンフレームシーケンス中の幾つかのフレームが閾値より低い場合でも、ホールが３より大きくない（ＴＯＯ＿ＢＩＧ＿Ａ＿ＨＯＬＥ＝３）であれば、パンの継続性が確保される。
【００６０】
ズーム検出
画像中の動きベクトル最も外側のリム、即ち、画像エッジの動きベクトルを調べて、ズーム条件を検出すべきである。リムの直径方向で対向する位置における動きベクトルは反対方向を指示しなければならない。反対方向に向いている動きベクトルの動きベクトル総数に対する割合の閾値は（ＺＯＯＭＲＡＴＩＯ＝.７）である。ズームの中心は画像の範囲内のどこに在ってもよいから、外側リム上の動きベクトルのみを使用する。かように外側リムの動きベクトルはズームの存在を示す最良のインジケータである。加えて、画像エッジには前景の動きがそれ程無い。
【００６１】
色処理
ここでは，先に開示した方法を色シーケンスに拡張する。２つの異なる実施形態を記述する。第１実施態様において、２５６ビンのＹヒストグラムと２つの１２８ビンのＵとＶのヒストグラムより成る連結ヒストグラムを使用する。第２実施形態においては、２５６−ビンのＹヒストグラムを使用する。幾つかの実験シーケンスの場合、結果として重要な変化は何も観察されなかった。両方の場合とも、活動測度は式１によって規定される。しかしながら、色ヒストグラムにおいて若干のシーケンスを用いることは、２枚の動画フレーム間の変化を検出するのに決定的な役割を演じる。例えば、輝度（ルミナンス）は略同一であるが彩度値（クロマ）は変化する。
【００６２】
非圧縮動画入力方法の要約
図２は階層的要約と閲覧方法のブロック図である。ディゾルブ、フェードイン／フェードアウト、除去モジュールについては、参照のために引用した関連用途において説明し、ここではディゾルブ検出方法を開示する。このモジュールは、動画シーケンスから遷移フレームを除去してディゾルブを突発移行シーンに変換するために用いられる。最も細密なレベルのキーフレームを検出するブロックを主要ステップと共に図４に示す。図３は自動パン／ズーム自動処理モジュールの詳細を示している。自動的に、（ａ）パンの動きがあれば検出してモザイク（パノラマ）画像を構築し、（ｂ）ズームシーケンスの最初と最後のフレームを検出し確認する。最も細密なレベルのキーフレームからパン／ズーム関連キーフレームを除外して非パン／非ズームフレームだけを階層的要約キーフレーム生成プロセスに参与させる。この除去及び自動パン／ズーム処理は、オプションであり、必要に応じ、ユーザが動画クリップのある特定点において対話方式で実行可能にすることができる。このＧＵＩにより、ユーザは、特定レベル要約の（階層的ブラウザにより生成された種々のレベルの内の）閲覧を開始することができる。例えば、モザイク画像とズーム要約と共に最も粗い要約を最初に表示することができる。次に、ユーザは、より細密な階層レベルにおけるフレームを対話方式で検索／再生することができる。ユーザは、ボタンをクリックして、現在見ているキーフレームの親−子の何れかにアクセスすることができる。親を選ぶと、現在のレベルのキーフレーム群が、親である１枚のキーフレームに代わる。子を選ぶと現在のキーフレームの子に該当する全てのキーフレームが見られる。図５は、親と子のキーフレームのコンセプトを示している。最も細密なレベルをさらに拡張し、即ち、最も細密なレベルにおける子では、指定のキーフレーム間の動画クリップを再生する。この時、動画が再生され、動画クリップのその部分に対応する音声が同時に再生される。動画クリップを再生するこの機能性はより粗いレベルの階層においても装備できる。
【００６３】
ここに記述した動画閲覧方法は、マルチメディア操作用の有効なユーザインターフェースを提供するだけではなく、種々の用途に用いられる。第２世代の画像符号化システムを連想させると第２世代の動画符号化システムにおいて採用される可能性のある動画シーケンスの時間的特性に関する知見を提供する。例えば、ＭＰＥＧ−２ビットストリームを処理する設計の復号器はＩＢＢＰ又はＩＢＢＢＰフォーマットに適応する。しかしながら、キーフレームの階層を用いれば、時間的な動画ストリームの本質に、知的に、より重要に、計算効率よく適応し、少ない資源を用いて高い品質を供給する符号器を設計できる。圧縮の改善に動画フレームの階層を用いる方法に関する情報は文献で得られ、セグメンテーションアルゴリズムのマルチスケール特性をロスの無い静止画像の圧縮を得るために活用されている。第２世代画像符号化システムと第２世代動画符号化システムの主たる違いは、前者は符号化機構の根本的な変更を必要とし、従って、大きな影響を持ちえず、一方後者は現存の動画符号化基準のいずれにも組み込むことができる。
【００６４】
計算性能
キーフレーム生成方法の計算性能は、本発明の方法を実施するために使用するコンピュータのハードディスクへのアクセス速度にかなり依存する。下記の議論において、“リアルタイム処理”は所定解像度において毎秒３０フレームを処理する能力を意味する。３００フレーム用１／４共通中間フォーマット（ＱＣＩＦ）のカラーシーケンス（１７６ｘ１４４の解像度）の場合、ＳＵＮ（登録商標）Ｕｌｔｒａ  ＳＰＡＲＣ−２（登録商標）を用い、ヒストグラムの構築には１１秒を要し、残りの処理には１秒未満を要することが判明した。かように、ヒストグラムの計算は、リアルタイムで達成できるとしても、リアルタイムで階層キーフレームの生成を容易に達成できなければならない。ヒストグラムの計算後の処理は実際のフレーム解像度とは関係なく、３００フレームＱＣＩＦシーケンスを処理するに要した時間量は、各フレームのヒストグラムが事前に計算されていれば、１０２４ｘ７８０の解像度でシーケンスを処理するに要する時間と同じであることも注記しておく。
現在のグローバルな動きの検出は、リアルタイムで実行できる。しかしながら、パン／ズーム検出に必要なブロックマッチングアルゴリズムを伴う厳しい計算負荷のために、パン／ズーム処理は実装したソフトウェアを用いてリアルタイムでは実行できない。
【００６５】
圧縮動画入力
前述の論議において、非圧縮又は伸長ビットストリームのみを検討し実験に用いてきた。しかしながら、入手できる動画ストリームの殆どは、コンパクトに蓄積するために圧縮フォーマットされている。図４の方法を圧縮ビットストリームに拡張し、最少の復号を行いキーフレームを抽出できるようにする。圧縮動画を処理するブルートフォース方法で全体動画ストリームを簡単に伸長し、その後ここに記述する非圧縮動画用の技法を用いるのが良いと判断される。
【００６６】
本項では、ＭＰＥＧ−２ビットストリームで使用できる、ディジタル動画の階層要約と閲覧のバリエーションを記述する。全体のスキームは図７のフローチャートに要約して示す。ヒストグラムを計算する新規の方法を開示する。８ｘ８ブロックのＤＣ係数のヒストグラムを用いる。このプロセスは、入力ビット１３２により開始する。Ｉピクチャに対するヒストグラムの計算１３４は従って通常の技術を有する者にはよく知られた方法により直接的に行われる。予測ピクチャ（Ｐ及びＢフレーム）に対するヒストグラムの計算は、参照フレームを完全に復号することなく、後述のようにして実行され、ヒストグラムの精度の向上と従ってキーフレームの選択１３６の精度向上がもたらされる。階層的キーフレームの選択１３６は、階層的要約のキーフレームの識別を、例えば、時間的な表示順序で決定し、この要約の情報を後述する復号器マネージャに供給する。ＤＣＴ係数のヒストグラムが生成されると、階層的キーフレームの選択が、図４を参照し教示された様にして実行される。
【００６７】
私の同時係属出願“動画シーケンス中のディゾルブ領域の検出（Ｄｅｔｅｃｔｉｎｇ  Ｄｉｓｓｏｌｖｅ  Ｒｅｇｉｏｒｓ  ｉｎ  Ｖｉｄｅｏ  Ｓｅｑｕｅｎｃｅｓ）”に開示した機構のような動画中のディゾルブ領域検出機構を、ヒストグラムの計算とビットストリームインデックステーブル（ＢＩＴ）の生成を行う図７の処理ブロック１３４に容易に組み込むことができる。即ち、ディゾルブ領域に含まれるフレームをＢＩＴ内にマークし、逐次キーフレーム選択プロセスにおいて無視する。或いは、ディゾルブ領域の内のフレームを偽のキーフレームにしてもよい。
【００６８】
本方法は、ヒストグラムの計算１３４と同時に、ビットストリーム内のバイトオフセット位置，参照フレーム，ＤＣＴブロック量子化に使用した量子化マトリックスのような各ピクチャに関する情報を含む、ビットストリームの記録を生成する。本発明において、“ビットストリームインデックステーブル”（ＢＩＴ）と称するテーブルを生成する。ＢＩＴ１３８のコンテンツとＢＩＴの生成方法については、後で詳述する。
ＢＩＴ１３８の１つの目的は、ビットストリームの本質的なパラメータを捕捉する全ビットストリームを復号又はパーシング（構文解析）する必要なく要約を生成するためのキーフレームの復号を可能にすることである。構文解析は、システムに動画ストリームを復号するか否かにして、動画ストリーム中の各ビットを考察することを要求する。さらに、ユーザが、例えば、要約の表示又は２枚のキーフレーム間の動画の再生を望む際に効率的に閲覧を可能にするために、図８に示すように、要約の識別と原動画ビットストリームに加えＢＩＴ又はＢＩＴの縮小バージョンを装備する。ユーザに要約を提示し、若干の対話を含めた本方法の特別な実施態様について後述する。図８において、ビットストリームはＢＩＴと要約フレームの識別子とは物理的に異なる位置に置かれたメモリに常駐させることができる。例えば、ビットストリームをデータベースサーバに保管し、要約とＢＩＴをローカルマシーンに常駐させてもよい。代案として、３種のデータを全て、同一媒体、例えばＤＶＤディスク又は他の任意大容量蓄積媒体に常駐させることができる。ＢＩＴをさらにコンパクトにする（又は削減する）方法については、“コンパクトな蓄積装置用の削減されたビットストリームインデックステーブルの生成”の章で説明する。ＢＩＴを生成しＢＩＴサイズの“削減”を決定し、ダウンサイズＢＩＴに任意数の技法を使用できることは評価すべきである。一つの例をここにあげる。ＢＩＴを形成保管せず、全ビットストリームを構文解析して復号を要するキーフレームを毎回復号することもまた可能である。
【００６９】
図７を再び参照する。階層的要約１４０の生成期間中、復号器マネージャ１４２がＢＩＴに含まれている情報を利用しキーフレームを選択的に復号してＭＰＥＧ−２復号器１４４に送り、復号次第、階層要約１４０を形成する。復号器マネージャ１４２は提示段階中に、ユーザがキーフレーム間の動画を再生して動画を閲覧することを望む際に、同様なタスクを実行する。復号器マネージャの作動原理（例えば、コンピュータプログラムにより実装される）について次に説明する。
【００７０】
本発明は、ＭＰＥＧ−２圧縮動画を蓄積して記録する動画カメラ内に実装できる。かような場合、要約情報とＢＩＴは動画ストリームを蓄積する蓄積システムに蓄積できる。或いは、要約情報とＢＩＴを、明確な方式で動画ストリームと連結された任意のメモリ位置に蓄積してもよい。階層的要約自体は、キーフレーム又はキーフレームをサブサンプリングしたバージョンを含んでおり、迅速にアドレスできる蓄積システムに保管できる。オンカメラ式ユーザインターフェイスは、カメラ、テープ又は任意の他の蓄積媒体に階層的要約に基づき保管された動画コンテンツの認定のために装備される。
【００７１】
別案として、ビットストリームをカメラから要約プロセスを実行するコンピュータにダウンロードしてもよい。この場合、要約はテープ又は動画データを保持する任意の他の蓄積媒体又はビットストリームとの明確なリンクで連結された他のメモリにコピーする。例えば、圧縮されたＭＰＥＧストリームを直接記録するカメラが現在入手可能であり（例えば、日立ＭＰ−ＥＧ１Ａ型カメラ）、ビットストリームをパーソナルコンピュータ（ＰＣ）にダウンロードできる。本発明のシステムは、ＰＣプラットホームでかようなビットストリームを処理するために使用できる。
【００７２】
ＭＰＥＧ−２ビットストリームを効率よく処理し階層的動画要約を作成するためには、以下の問題に取り組み解決しなければならない。
１．ＭＰＥＧ−２ビットストリームを最小限復号しながら、キーフレームの階層を生成する。
２．全てのフレームを復号することなくＭＰＥＧ−２ビットストリームから選択したキーフレームを復号する手順を確立する。
３．２枚の所与のキーフレーム間の一連のフレームを復号する戦略を開発する。
この方法は、ヒストグラムレベルで働く。ＭＰＥＧ−２ビットストリームを最小限復号しながらフレーム毎に色ヒストグラムを計算する方法を開示する。
【００７３】
ヒストグラムの計算と後続処理は、各次元における８分の１のサブサンプリングから大きな影響を受けない。１ステップ進めて、８ｘ８ブロックの平均である、８ｘ８ブロックＤＣＴのＤＣ成分のみ使用して計算したヒストグラムは実際の目的には十分であった。動き補償画像の場合、計算量を削減するために、性能の低下が無視できる程度である近似動き補償を用いることができるとして提案されている。ＭＰＥＧ規格に用いられているブロックマッチングのスキームに従い、１６ｘ１６マクロブロックの動きベクトルを、実行中の動き補償予測の参照フレームの１６ｘ１６マクロブロックの最大限４つのマクロブロックと重ね合わせる。同様に、１６ｘ１６マクロブロック中の各８ｘ８のサブブロックを最大限４つの他の８ｘ８サブブロックと重ね合わせる。かように、各８ｘ８サブブロックを、重なる各８ｘ８サブブロック中の値の重み付けた平均値で近似させ得ることが示唆された。個別ブロックに割り当てられた重み値は、重なり領域に比例させることができた。図９を参照し、８ｘ８サブブロックの平均値は、次式で計算される。
【００７４】
【式５】
0003719933.tif 000006
【００７５】
ここで、ΔDCTは、ブロックに対する残差ＤＣＴのＤＣ成分の８倍である（ＭＰＥＧ−２規格に用いられるブロックに対する残差ＤＣＴのＤＣ成分はブロックの残差誤りの平均値の１／８であるので、８の係数が入る）。ヒストグラムは、式５中に見られるように、画像内の各８ｘ８ブロックの平均でヒストグラムベクトルを更新することにより得られる。ヒストグラムを得る上記の方法は、性能の低下をもたらす問題を有している。本発明の方法の改良の１つは、ＭＰＥＧビットストリームに対するヒストグラムの計算を取り扱うより良い方法を提案することにある。
ＭＰＥＧビットストリームは、特定のフレームを復号しようとする前にビットストリームの他の部分からの復号情報を必要とする複雑な符号化戦略を内蔵している。上首尾の動画閲覧方法も最少の時間量で特定の動画フレームを復号する問題を検討する必要がある。
【００７６】
ＭＰＥＧビットストリームからのヒストグラムの計算
ＭＰＥＧビットストリームの復号は、次の２つの計算が集中するステップを含んでいる。
１．８ｘ８ブロックの逆ＤＣＴを得る。
２．ＭＰＥＧ−２の場合、１６ｘ１６マクロブロックによる動き補償。ブロックは小さいか又は偶数／奇数フィールドのみを有している。
先に、８ｘ８ブロックをその平均値で置き換えても画像のヒストグラムに大きな影響を及ぼさないことを指摘した。この実装例において、各８ｘ８ブロックを８Ｘ（ＤＣＴ係数のＤＣ値）で置換する。逆ＤＣＴ計算のための公式から、これはブロックの平均値を生じ、補償関連量子化誤差の範囲内で正確である。
【００７７】
次のステップを理解するために、ＭＰＥＧビットストリームに採用されている符号化戦略についてその概略を説明する。典型的なＭＰＥＧビットストリームは３種類のフレームを有している。
Ｉ（フレーム内符号化フレーム）、
Ｂ（双方向予測フレーム）及び
Ｐ（予測フレーム）。
ＩフレームはＤＣＴデータのみを含んでいる（動き補償は行わない）。かように、ヒストグラムの計算にＤＣＴ係数のＤＣ値を用いるとＩフレームの最少限復号の問題は完全に解決できる。ＢフレームとＰフレームは先に復号した参照フレームから現フレームを予測するためにブロック動きベクトルを用いる追加ステップを含む。先に復号した利用可能なフレーム自身は部分的にのみ復号されている。かように、ＢフレームとＰフレームの復号に用いられる戦略は、十分に検討しなければならない。以下の検討において、ケース（ａ）は既に存在し文献において共通に用いられている動き補償スキームに関し、ケース（ｂ）はここで開示する新しい動き補償スキームに関する。
【００７８】
動き補償を単純化するために、最も知られている方法で、前節で記述したスキームを用い、即ち、各８ｘ８サブブロックを、それが重なった８ｘ８サブブロックの重みを付けた平均値で置き換える。２つのシナリオを検討する。ケース（ａ）は８ｘ８サブブロックを部分的に復号した参照フレーム中の重なったブロックの重みを付けた平均値で置き換える。ケース（ｂ）は、８ｘ８サブブロックを、部分的に復号した参照フレームからの正確な画素で置き換える。ケース（ａ）において、動き補償予測フレーム中の全８ｘ８ブロックが単一値を持つことが判る。ケース（ｂ）においては、８ｘ８ブロックは潜在的に多くの異なる値を持ち得る（即ち、ブロック内の画素は多くの異なる値を取り得る）。これをさらに説明するために、ケース（ａ）とケース（ｂ）を通して８ｘ８ブロックの例を検討する。図１０はこの例を示している。図１０において、予測ブロックはＩフレームから得る、即ち、８ｘ８ブロックは予測フレーム中の関連する単一値を持つものと仮定する。ケース（ａ）は、ただ１つの値μを持つ現フレーム中の１つの８ｘ８ブロックを生じる。ケース（ｂ）は潜在的に４つの異なる値を有する現フレーム内の１つの８ｘ８ブロックを生じる。
【００７９】
これは、フレーム内符号化参照フレーム（又はＩフレーム）に続く第１の幾つかの動き補償フレーム（ＰまたはＢフレーム）に大きな差を生じない。事実、ヒストグラムの計算は平均化及びサブサンプリングから大きな影響を受けないので、２つの手順はヒストグラムの計算に対しては同等に有効であるとみなされる。しかしながら、ケース（ａ）は計算量が少なくメモリの消費も少ないのでより好ましい。これは、ケース（ａ）のように動き補償された任意所与のフレーム（Ｉ又はＰ又はＢ）においては、各８ｘ８ブロックにはただ１つの値が得られるからである。かように、各次元において８分の１の容量を要するだけで済む。即ち、全フレームを蓄積する場合と比較して潜在的可能性としては、６４（８ｘ８）分の１の容量のメモリ装置ですむことになる。しかしながら、以下に説明するように、ケース（ａ）は過度の性能低下をもたらすので、使用可能な代案ではない。
【００８０】
連続動き補償フレーム数、Ｉフレームを介在させない、すなわち連続動き補償フレーム数が増加すると、ケース（ａ）とケース（ｂ）間の差が増大する。図３に戻って、１枚の動き補償済みフレームから予測を、例えば、ＰフレームからＢフレーム又はＰフレームからもう１つのＰフレームに予測を行う際に、何が生じるかを考察する。ケース（ａ）の場合、重み付け平均化処理を予測ブロックが重なる４つのブロックに対して実施すると、各ブロックは単一の値を持っており、８ｘ８の予測ブロック全体に対し単一の値で終了する。ケース（ｂ）の場合は、予測フレームの各ブロックは潜在的に４つ（又はそれ以上）の異なる値を有するので、現予測ブロックは多数の異なる値を持ち得る。いま、動き補償済みフレームからのこの一連の予測としてケース（ａ）とケース（ｂ）間に出現する重要な変化キーとなる差分が大きくなることに注目する。動き補償フレームのシーケンスが十分に長いと、ケース（ａ）は、後述するようにフレーム間の動きが十分であれば、フレーム全体に対し単一の値を生じると期待される。これは、しかしながら、ケース（ｂ）には生じない。
【００８１】
この現象をさらに詳細に説明するために、Ｉフレーム内の各８ｘ８ブロックを平均で置換し、原画像のより小さいバージョンを生成することを考える。今、ケース（ａ）において実施したように動き補償は、この小画像を１個の２ｘ２平均化フィルタで反復再帰処理することを必要とする。基本的なフーリエ解析で、平均化フィルタの反復用途によりエッジ効果を無視すれば制限内の均質な画像を生じることを容易に示すことができる。
【００８２】
上記の観察が真実であることが実際に観察された。典型的なＭＰＥＧ−２圧縮シーケンスの場合、２枚のＩフレーム間の距離は１５である。これにより、動き補償をケース（ａ）に従い実行すると非常に顕著な性能低下が生じることが発見された。ケース（ａ）の動き補償スキームはヒストグラムに周期的に強い変動を生じさせ、偽のキーフレームを検出する結果をもたらす。かような理由で、ケース（ｂ）を実装に使用した。最少復号法を用いヒストグラムを計算することにより、１つのＱＣＩＦシーケンスに対するヒストグラム計算速度を半分に短縮されるが、利点は解像度が高まることの方が大きかった。現在、５１２次元のヒストグラムのベクトルを使用しており、２５６ビンのグレイスケール（Ｙ成分）ヒストグラムと１２８ビンのＵ成分ヒストグラムと１２８ビンのＶ成分ヒストグラムにより形成される。上記の説明は、彩度（クロマ）フォーマットとは無関係に、Ｙ，Ｕ及びＶのフレーム構成成分に対して個々に適用できる。
【００８３】
ＭＰＥＧ−２ビットストリームからの特別フレームの抽出
ここに開示する実施形態において、ＭＰＥＧ−２ビットストリームからの特定フレームの抽出は２ステップの手順で行われる。ヒストグラムの計算と同時に実行される第１ステップにおいて、ＭＰＥＧ−２ビットストリームからランダムに選んだフレームを迅速に復号するために必要な情報を含む“ビットストリームインデックステーブル”を生成する。キーフレームの階層が生成される、即ち、階層的要約に入るキーフレームの識別が規定されると、階層の最も細密なレベルのキーフレームだけが復号を要求され、階層の粗いレベルのフレームは最も細密なレベルのフレームのサブセットとなる。キーフレーム抽出手順における第２ステップは、後述する復号器マネージャにより、第１ステップで生成された“ビットストリームインデックステーブル”を使用して実行される。
【００８４】
上記２ステップ手順の利点は、ビットストリームの関連部分を直接復号する場合に比し、関心を引くフレームまでの全ビットストリームを見るのに要する時間を削減できることである。フレ−ム番号１３５０から１４００までのＭＰＥＧ−２ビットストリームをビットストリームインデックステーブルを用いずに復号するためには、フレーム番号１３５０までの全ビットストリームを、完全に復号しないにしても、構文解析することが必要である。これにはかなりの時間を要する。ビットストリームインデックステーブルが使用できれば、ビットストリームの関連部分に直接進むことができ、絶対最少量の構文解析と復号のみが要求される。
【００８５】
ＭＰＥＧ−２ビットストリームからランダムに選択したフレーム（ここでは現フレームと記す）を復号するためには下記の情報が必要である。
１．過去において（時間的に）最も近いシーケンスのヘッダ（そのバイトオフセット）。
２．現フレームのビットストリームへのバイトオフセット。
３．過去において（そのバイトオフセット）最も近い量子化マトリックスのリセット（もしあれば）。
４．現フレームがＢフレームであれば、現フレームに対応する参照フレーム（Ｉ−Ｐ／Ｉ−Ｉ／Ｐ−Ｐ）（それらのフレームのバイトオフセット）。
５．現フレームがＰフレームであれば、（Ｐフレームの参照フレームである）最も近いＩフレーム（そのフレームのバイトオフセット）。
【００８６】
Ｂ／Ｐフレームの場合は、参照フレームを正確に復号するために、参照フレーム以外の幾つかの他の参照フレームを復号する必要があることを指摘しておく。
前記２つのステップ、即ち、（１）ビットストリームインデックステーブルを生成するステップと（２）後述の復号器マネージャによるビットストリームインデックステーブルを用いたフレームの抽出するステップ間で情報交換が容易に行えるように、上記情報を保持するための共通のデータ構成を開発した。Ｃコードの下記のセグメントを使用しビットストリームインデックステーブルの形成に用いる異なるフラグを実態化した。但し、これは一例に過ぎず、ビットストリームインデックステーブルは任意数の異なるシンタックス形式をもち得ることは理解されよう。
【００８７】
【表１】
0003719933.tif 000007
【００８８】
Ｋ＿ＯＦＦＳＥＴフラグは、上記の他のフラグから区別するために任意バイトオフセットに加える。１５のバイトオフセットは、我々の表記では１５＋Ｋ＿ＯＦＦＳＥＴ（＝２１）と翻訳する。Ｋ＿ＥＮＤ＿ＯＦ＿ＤＡＴＡは、異なるイベント（例えば、シーケンスヘッダとＩフレーム又はＩフレームとＢフレーム等）間の区切りである。生成されたビットストリームインデックステーブルがどのように出現するかを理解するために、下記イベントのシーケンスの符号化が要求されていると仮定する。
【００８９】
１．シーケンスヘッダが０バイトで開始
２．Ｉピクチャが１５０バイト
３．Ｐピクチャが３０００バイト
４．Ｂピクチャが４２００バイト
５．Ｂピクチャが５３００バイト
６．量子化マトリックスのリセットが５４００バイト
７．Ｐピクチャが６２００バイト
このシーケンスを下記の表現に変換する。
【００９０】
【表２】
0003719933.tif 000008
【００９１】
これは前記のＣデータ構成を用いて下記のバイト表現を生成する。
【００９２】
【表３】
0003719933.tif 000009
【００９３】
上記バイトを用いた表現中のスペースは、復号器がビットストリームを構文解析するために必要である。Ｋ＿ＥＮＤ＿ＯＦ＿ＤＡＴＡフラグは、厳密にいえば冗長である。しかしながら、このフラグは、発生した偽のデータを除去するために使用でき（ビットストリーム中のエラーによって）、このアルゴリズムをエラーに対し強くする。このフラグは偽データを除去するための“同期信号”として作用し、例えば、（ビットストリーム中のエラーによる）バイトオフセット値を伴わないシーケンスヘッダを破棄する。
【００９４】
上記の生成された“ビットストリームインデックステーブル”を使用する復号器マネージャは下記のように機能する。
１．  最後に復号されたフレームの番号（ｌｄｆ）を−１に初期化する。
２．  復号される各フレーム（ｆｔｄ）に対し：
復号を開始するフレーム（ｓｄｆ）を見つけ出す。
ｆｔｄがＩフレームであれば、ｓｄｆ＝ｆｔｄとする。
ｆｔｄがＰフレームであれば、ｓｄｆをｆｔｄより前の最も近いＩフレームにセットする。
ｆｔｄがＢフレームであれば、ｓｄｆをｆｔｄに対応するアンカーフレームの両方より前の最も近いＩフレームにセットする。
上記ｓｄｆがｌｄｆ＋１より小さければ、ｓｄｆ＝ｌｄｆ＋１に設定する。ｓｄｆ＜ｌｄｆ＋１であれば、要求されたフレームの幾つかはすでに復号されている。
ｉ＝ｌｄｆ＋１〜ｓｄｆに対して、
最も近いシーケンスヘッダ（ｒｓｈ）を見つけ出す。
ｑｍｒがｒｓｈより大きい場合は、最も近い量子化マトリックスのリセット（ｑｍｒ）を見つけ出す（ｑｍｒが存在すれば）。
ｒｓｈとｑｍｒをビットストリーム中に出現する順序で復号する。
全てのＩ及びＰフレームを、ｓｄｆから開始し、ｆｔｄ−１に到るまで順次復号する。
ｆｔｄを復号する。
１連のフレームを復号するために、復号器マネージャの上記手順に従って、第１フレーム（ｆｔｄ）を復号する。残りのフレームは，１連のフレームの最後まで順次復号する。
【００９５】
特別な場合に必要に応じ、所要のフィールドピクチャを処理する。偶数／奇数フィールドヒストグラムを使用することができ、どちらも最初に復号できる。他のフィールドは、Ｂピクチャの場合復号できず、Ｐ及びＩピクチャの場合は、最少符号化戦略で復号できる。１フィールドのみ復号する場合は、ヒストグラムを２分の１に縮尺しなければならない。余分に復号したフィールドはＰ／Ｉフレーム用ヒストグラムの計算には使用せず、この場合、全てのフレームはヒストグラムに１フィールド供給しているので、ヒストグラムを縮尺しなくてよい。フィールドをフレームから区別し適切なステップをとるために、ＭＰＥＧ−２ビットストリームは、ピクチャヘッダとピクチャ符号の拡張から下記の２つの情報を提供する。
１．（ピクチャヘッダ中の）時間的な基準が現在復号中のフレーム番号を提供する。この時間基準は各グループのピクチャヘッダの先頭にリセットされる。
２．（ピクチャ符号の拡張中の）ピクチャ構成が、トップ／ボトムフィールド情報を提供する。
【００９６】
コンパクトな蓄積装置用の削減されたビットストリームインデックステーブルの生成
実装の観点から重要な問題は、ディスクスペースを節減するためにビットストリームインデックステーブルをコンパクトに表現することである。ＭＰＥＧ動画が占拠する大スペースと比べると、ビットストリームインデックステーブルは各フレーム当たり約８−１０バイトのスペースをとるだけなので、これは、一見、重要な問題ではないよう見えるかもしれない。オーバーヘッドは下記のステップを取ることにより低減できる。
１．絶対バイトオフセットよりも増分バイトオフセットを用いる。これにより大きなシーケンスの場合かなりの量の節減になる。
２．ＵｎｉｘプラットホームのｇｚｉｐまたはＰＣ上のｐｋｚｉｐのような圧縮アルゴリズムを用いる。
３．Ｋ＿ＥＮＤ＿ＯＦ＿ＤＡＴＡフラグを除去する。
４．ビットストリームを最少の復号及び構文解析してキーフレームを復号するために必要な最少量の情報を蓄積するように、ビットストリームインデックステーブルのデータ量を削減する。
【００９７】
最後の項は、キーフレームの位置にのみアクセスでき、キーフレームの位置をユーザが後で変更することを許さないことに注意すべきである。（１）と（４）は完全には両立しないことも注記しておく。増分バイトオフセットを用いる場合、（４）の削減アルゴリズムは、フレームの変更順序を反映するようにバイトオフセットを変更すべきである。現在の実装において、削減されたビットストリームインデックステーブルを後述のように生成する。復号器マネージャがこの削減バージジョンのテーブルを使用する。この削減ビットストリームテーブルの使用は、得られるべき速度と使用可能な蓄積スペースの量の関数として決定される。蓄積装置のスペースが使用可能であれば、ビットストリームテーブルを削減する必要はない。完全なテーブルを納める余地があれば、検索及び処理も迅速に行える。
【００９８】
削減されたビットストリ−ムインデックステーブル
ビットストリ−ムインデックステーブル（ＢＩＴ）と同じ構成を用いるが、同時に削減ビットストリ−ムインデックステーブル（ＰＢＩＴ）用の異なる組織シンタックスを採用している。各キーフレームは、ＢＩＴ内の１単位として表現されている各動画フレームに対向し、（Ｋ＿ＥＮＤ＿ＯＦ＿ＤＡＴＡのフラグで挟まれた）１単位として表現される。全ビットストリームを構文解析及び復号することなく特定の（現）キーフレームを復号するためには、下記の情報が必要である。
【００９９】
１．現キーフレームのタイプＩ／Ｂ／Ｐ
２．現キーフレームに対応する開始復号フレーム（ｓｄｆ）（バイトオフセット）。復号器マネージャのＢＩＴバージョンにおいて仮定したように、復号器は全てのキーフレームを復号するためには順次作動しないので、（ｓｄｆ＜ｌｄｆ＋１であればｌｄｆ＋１でない）バイトオフセット表示の実際のｓｄｆは保管する必要がある。復号器が順次作動し、ｓｄｆ＜ｌｄｆ＋１であれば、復号はｌｄｆ＋１から開始することが必要である。ｌｄｆ＋１が先行キーフレームに続く動画フレームであり、そのオフセットは入手できるので、この情報は既に入手可能である。
３．現キーフレームのバイトオフセット
４．最も近いシーケンスヘッダのオフセット。全ての有効なＭＰＥＧ−２ビットストリームはシーケンスヘッダを有しているので、Ｋ＿ＳＥＱＵＥＮＣＥ＿ＨＥＡＤＥＲフラグは必要ない。
５．量子化マトリックスのリセットがあった場合は、ＭＰＥＧ−２ビットストリームには量子化マトリックスリセットがないので、Ｋ＿ＱＵＡＮＴ＿ＭＡＴＲＩＸ＿ＥＸＴＥＮＳＩＯＮフラグを付けて蓄積する必要がある。シーケンスヘッダの出現で量子化マトリックスがリセットされるので、そのリセットがそのシーケンスヘッダ以前に発生していればその量子化マトリックスのリセットを蓄積する必要はない。
【０１００】
復号器マネージャは、ｓｄｆ情報と現キーフレームのタイプとそのバイトオフセットを次のように用いる。所望の現キーフレームがＩ又はＰタイプであれば、復号器マネージャはｓｄｆから復号を開始し、ビットストリームを構文解析し、Ｉ及びＰフレームのみを探す。かようなＩ及びＰフレームは、所望の現フレームに到達するまで復号され、所望の現フレームも復号される。この技法において、復号器マネージャは、フレームがＢフレームあるかをチェックせず、Ｉ及びＰフレームのヘッダのみを探索する。所望の現キーフレームがＢタイプであれば、復号器マネージャはｓｄｆから始まる各フレームを考慮し、全てのＩ及びＰフレームを復号し、各Ｂフレームで停止してそのフレームが所望のキーフレームであるかをチェックする。
【０１０１】
そのフレームがＢタイプであれば、Ｂフレームを構文解析する必要を無くすために、最も近い復号参照（Ｉ又はＰ）フレームに近似させたい。Ｂフレームが５３５００バイトのオフセット値より始まる復号すべきキーフレ−ムであり、４３０００バイトから読む量子化マトリックスを必要とし、３９０００バイト位置で読むシーケンスヘッダを必要としていると仮定する。復号を開始するフレームは４５０００バイトより始まる。このデータは次のように符号化されている。
【０１０２】
【表４】
0003719933.tif 000010
【０１０３】
復号器マネージャが実行する構文解析量が増大することにより計算時間が増えてコストが掛かるためにＰＢＩＴをさらにスリムにできることを明らかにしておかねばならない。従って、復号器マネージャの複雑化とＰＢＩＴのサイズとの間にトレードオフがある。用途の要求条件により適当なバランスをとることも可能である。例えば、ＰＢＩＴはｓｄｆと、ｓｄｆと現キーフレーム間の全てのＩ及びＰフレームのバイトオフセットと、現フレームのバイトオフセットを蓄積し、復号器マネージャがビットストリ−ムを構文解析する必要を無くす。但し、その結果、ＰＢＩＴのサイズは増大する。他の極端な場合は、ｓｄｆとキーフレームのバイトオフセットのみを蓄積する。最もコンパクトなＰＢＩＴが得られるが、その代わり、復号器マネージャは、開始フレームからキーフレーム位置までのビットストリームを構文解析し、ＩとＰのフレームを復号しなければならない。自動パン／ズーム検出／抽出機能を組み込むためには、全フレームビットストリームを復号する必要がある。
【０１０４】
ディジタル動画シーケンスのキーフレームを閲覧するシステムを開示してきた。入力動画ストリームは、通常のディジタル動画であるか、或いは、ＤＣＴに基づく圧縮ストリ−ムである。本発明の好適な実施態様と幾つかの変更例を開示してきたが、特許請求範囲に規定した本発明の範囲から逸脱することなく、さらなる変更及び修正を加えることができることを理解すべきである。
【図面の簡単な説明】
【図１】  図１は、３つのレベルに対する動画の要約の階層構造を示す図である。
【図２】  図２は、本発明による方法の第１実施形態のブロック図である。
【図３】  図３は、本発明の自動パン／ズーム処理モジュールのブロック図である。
【図４】  図４は、本発明の最も細密なレベルのキーフレームの選択アルゴリズムを示すブロック図である。
【図５】  図５は、本発明の階層的要約のブロック図である。
【図６】  図６は、キーフレーム（ｋj）および対応ショットセグメント（ｔj-1，ｔj）の累積動き測定値（Ｃ（ｘ））と分布を示す図である。
【図７】  図７は、ＭＰＥＧ−２による圧縮入力動画に使用される本発明の第２実施形態の一部を示すブロック図である。
【図８】  図８は、階層的要約中のキーフレームの復号に用いられるデータの示す図である。
【図９】  図９は、動き補償のグラフである。
【図１０】  図１０は、ケース（ａ）及びケース（ｂ）を定義するために用いる動き補償アルゴリズム間の差分を示す図である。
【図１】
0003719933.tif 000011
【図２】
0003719933.tif 000012
【図３】
0003719933.tif 000013
【図４】
0003719933.tif 000014
【図５】
0003719933.tif 000015
【図６】
0003719933.tif 000016
【図７】
0003719933.tif 000017
【図８】
0003719933.tif 000018
【図９】
0003719933.tif 000019
【図１０】
0003719933.tif 000020