(57)【特許請求の範囲】
【請求項１】
コンピュータシステムにおいて、ビデオシーケンスのオブジェクトベースのビデオ符号化のためにスプライトを生成し、そこでは前記スプライトは前記ビデオシーケンス中のビデオオブジェクトを表す方法であって、
現在のビデオフレーム中の前記ビデオオブジェクトを前記スプライトに関連付ける動作パラメータを少なくともオブジェクトマスクおよびスプライトマスクの一部分に基づいて推定するステップであって、そこでは前記オブジェクトマスクは前記現在のビデオフレーム中のビデオオブジェクトの形を表し、前記スプライトマスクは前記スプライトの形を表し、前記推定するステップは、前記スプライト内部に位置するピクセルにマップするビデオオブジェクトのピクセルのみに基づき動作が推定されるように、前記オブジェクトマスクと前記スプライトマスクを使用することを含むステップ（１２００）と、
前記動作パラメータを使用してワープするステップであって、前記現在のビデオフレーム中のビデオオブジェクトおよびスプライトの間の動きに対して補償を行ない、前記現在のフレームに関するビデオオブジェクトをスプライト座標に変換するステップ（１２０２）と、
前記現在のビデオフレーム中のビデオオブジェクトを前記スプライトと混合するステップ（１２０４）と
を含む方法。
【請求項２】
前記推定するステップ（１２００）は少なくとも前記オブジェクトマスクおよびスプライトマスクの一部分に基づいて、前記スプライト内に対応するピクセルを有する、前記ビデオオブジェクトの複数のピクセルに対して与える重みを増大させ、前記ビデオオブジェクトの他の複数のピクセルに対して与える重みを減少させ、ワーピングされたビデオオブジェクトのそれぞれのピクセルと前記スプライト内の対応するピクセルとの間の強度誤差を最小にする動作パラメータの組を見つけることにより推定するステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記スプライト内に対応するピクセルを有する、前記ビデオオブジェクトの複数のピクセルは重み１を有することを特徴とする請求項２に記載の方法。
【請求項４】
前記混合するステップは、前記現在のビデオフレーム中のビデオオブジェクトは前記スプライトの少なくとも一部分に対して、前記ビデオオブジェクトが前記スプライトに寄与した現在の回数に比例して寄与することを含み、前記寄与は、スプライトが構築されるときに、ビデオオブジェクトによりスプライトが変更され、作成させることを示すことを特徴とする請求項１乃至３のいずれかに記載の方法。
【請求項５】
前記混合するステップは、前記ビデオフレーム中のビデオオブジェクトが以前に寄与したことがないスプライトの一部分に対しても前記現在のビデオフレーム中のビデオオブジェクトは寄与することを含み、前記寄与は、スプライトが構築されるときに、ビデオオブジェクトによりスプライトが変更され、作成させることを示すことを特徴とする請求項１乃至３のいずれかに記載の方法。
【請求項６】
前記ワープするステップ（１２０２）は前記動作パラメータを使用して前記スプライトに向けて前記現在のビデオフレーム中のビデオオブジェクトをワープするステップを含むことを特徴とする請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記スプライトは静的スプライトであることを特徴とする請求項１乃至６のいずれかに記載の方法。
【請求項８】
前記スプライトは動的スプライトであることを特徴とする請求項１乃至６のいずれかに記載の方法。
【請求項９】
前記推定するステップ（１２００）は先行するビデオフレーム中のビデオオブジェクトについての動作パラメータの値を初期的に使用するステップを含むことを特徴とする請求項１乃至８のいずれかに記載の方法。
【請求項１０】
１つまたは複数の他のビデオフレーム中のビデオオブジェクトに従って更新するスプライトを記憶するステップ（１２０６）をさらに含むことを特徴とする請求項１乃至９のいずれかに記載の方法。
【請求項１１】
前記動作パラメータは透視変換、シンプルな置き換えの変換またはアフィン変換であることを特徴とする請求項１乃至１０のいずれかに記載の方法。
【請求項１２】
前記オブジェクトマスクは前記現在のビデオフレームのピクセルにつき単一ビットの値を有することを特徴とする請求項１乃至１１のいずれかに記載の方法。
【請求項１３】
前記オブジェクトマスクは前記現在のビデオフレームのピクセルにつきマルチビットの値を有することを特徴とする請求項１乃至１１のいずれかに記載の方法。
【請求項１４】
前記スプライトマスクは前記スプライトのピクセルにつき単一ビットの値を有することを特徴とする請求項１乃至１３のいずれかに記載の方法。
【請求項１５】
前記スプライトマスクは前記スプライトのピクセルにつきマルチビットの値を有することを特徴とする請求項１乃至１３のいずれかに記載の方法。
【請求項１６】
前記スプライトを符号化するステップと、
透明性要素を符号化するステップと
をさらに含むことを特徴とする請求項１乃至１５のいずれかに記載の方法。
【請求項１７】
前記スプライトおよび該スプライトについての透明性要素はウェーブレット変換で符号化されることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記スプライトおよび該スプライトについての透明性要素は離散コサイン変換で符号化されることを特徴とする請求項１６に記載の方法。
【請求項１９】
前記スプライトを符号化するステップと、
前記スプライトについての照明要素を符号化するステップと
をさらに含むことを特徴とする請求項１乃至１５のいずれかに記載の方法。
【請求項２０】
前記スプライトマスクで表される形の輪郭を符号化するステップと、
前記スプライトと同じ方法で該スプライトについての付加的な照明または透明性要素を符号化するステップと
をさらに含むことを特徴とする請求項１乃至１５のいずれかに記載の方法。
【請求項２１】
前記推定するステップは、前記ビデオオブジェクトのオブジェクトの境界の内部輪郭を形成することにより、前記ビデオシーケンスの初期画像フレームからビデオオブジェクトをセグメント化し、前記内部輪郭を拡張して外部輪郭を形成し、前記内部輪郭および外部輪郭の間の、前記初期画像フレームのピクセルをオブジェクト内部の中にあるかどうかによって、予め定義された属性に従って、分類し、前記内部輪郭はオブジェクト周囲から公称寸法内で形成され、前記外部輪郭は、前記内部輪郭からユーザが定義したピクセル数であるステップと、
前記初期ビデオフレームのビデオオブジェクトの少なくとも２つの特徴点を選択し、選択された各特徴点の周りに集まる複数のピクセルのブロックを定義し、該ブロックを引き続く画像フレーム中の対応のブロックと比較するステップと
をさらに含むことを特徴とする請求項１乃至２０のいずれかに記載の方法。
【請求項２２】
請求項１乃至２０のいずれかに記載の方法を前記コンピュータシステムに実行させるためのコンピュータ実行可能命令を記録したことを特徴とするコンピュータ可読媒体。
【発明の詳細な説明】
発明の分野
本発明は、オブジェクトベースのビデオ符号化、特にビデオシーケンスの各フレーム内でビデオオブジェクトを再構成する際に使用されるピクセルデータを含む、スプライトと呼ばれる画像の生成に関する。
発明の背景
アナログビデオ信号に基づくフルモーションのビデオディスプレイは、長い間テレビジョン形式で使用されてきた。近年、コンピュータの処理能力が向上し、購入しやすい価格になってきたことで、デジタルビデオ信号に基づくフルモーションのビデオディスプレイの方が、より幅広く利用できるようになりつつある。デジタルビデオシステムは、従来のアナログビデオシステムに対して、フルモーションビデオシーケンスの作成、修正、伝送、記憶、および再生において、かなりの改良点を提供することができる。
デジタルビデオディスプレイは、３０Ｈｚから７５Ｈｚまでの周波数で連続的に再生または描画（ｒｅｎｄｅｒ）される大量の画像フレーム（ｉｍａｇｅ  ｆｒａｍｅ）を含む。それぞれの画像フレームは、特定システムの画面解像度に基づくピクセルの一配列で形成される静止画像である。その例として、ＶＨＳベースシステムの画面解像度は３２０×４８０ピクセル、ＮＴＳＣベースシステムの画面解像度は７２０×４８６ピクセル、開発中の高解像度テレビジョン（ＨＤＴＶ）システムの画面解像度は１３６０×１０２４ピクセルである。
ビデオシーケンスに含まれる未処理のデジタル情報は、膨大な量である。このような量のビデオ情報を記憶して伝送することは、従来のパーソナルコンピュータ装置では不可能である。３２０×４８０ピクセルという比較的解像度の低いＶＨＳ画像形式のデジタル化方式の場合、連続２時間の長編映画は、１００ギガバイトのデジタルビデオ情報に相当する。これに対して、従来のコンパクト光ディスクの記憶容量は約０．６ギガバイト、磁気ハードディスクの容量は１〜２ギガバイト、開発中のコンパクト光ディスクの容量は最高８ギガバイトである。
このように大量のデジタルビデオ情報を記憶または伝送する際の制限を解決するため、ＭＰＥＧ−１、ＭＰＥＧ−２、およびＨ．２６Ｘを含み、これまで様々なビデオ圧縮標準またはプロセスが確立されてきた。これら従来のビデオ圧縮技法では、時間相関（ｔｅｍｐｏｒａｌ  ｃｏｒｒｅｌａｔｉｏｎ）またはフレーム間相関（ｉｎｔｅｒｆｒａｍｅ  ｃｏｒｒｅｌａｔｉｏｎ）と呼ばれる、連続する画像フレーム間での相似性（ｓｉｍｉｌａｒｉｔｙ）を利用して、ピクセルベースの画像フレーム表示が動画表示に変換される、フレーム間圧縮（ｉｎｔｅｒｆｒａｍｅ  ｃｏｍｐｒｅｓｓｉｏｎ）を提供する。さらに従来のビデオ圧縮技法では、空間相関（ｓｐａｔｉａｌ  ｃｏｒｒｅｌａｔｉｏｎ）またはフレーム内相関（ｉｎｔｒａｆｒａｍｅ  ｃｏｒｒｅｌａｔｉｏｎ）と呼ばれる、画像フレーム内での相似性を利用して、１つの画像フレーム内で動画表示がさらに圧縮されるフレーム内圧縮を提供する。フレーム内圧縮は、離散コサイン変換（ＤＣＴ）符号化（ｄｉｓｃｒｅｔｅ  ｃｏｓｉｎｅ  ｔｒａｎｓｆｏｒｍ  ｅｎｃｏｄｉｎｇ）などの静止画像を圧縮するための従来のプロセスに基づいている。
特定の実施形態では異なるが、ビデオ圧縮標準であるＭＰＥＧ−１、ＭＰＥＧ−２、およびＨ．２６Ｘは、いくつかの点で類似している。以下に記載するＭＰＥＧ−２ビデオ圧縮標準についての説明は、一般にその他の標準にも適用可能である。
ＭＰＥＧ−２は、ビデオ画像におけるピクセルの正方形ブロックまたは配列に基づいてフレーム間圧縮およびフレーム内圧縮を提供する。ビデオ画像は、１６×１６ピクセル寸法の変換ブロックに分割される。画像フレームＮにおけるそれぞれの変換ブロックＴNに対して、直後のビデオフレームＮ＋１画像または直前の画像フレームＮ−１にまたがった（すなわち二方向性の）検索が実行され、最も類似したそれぞれの変換ブロックＴN+1またはＴN-1を識別する。
理論的に言えば、また直後の画像フレーム検索に関して、変換ブロックＴNとＴN+1がそれぞれの画像フレーム内で異なる位置にある場合でも、両者のピクセルは同一である。このような環境下では、変換ブロックＴN+1内のピクセル情報は、変換ブロックＴN内のそれに対して冗長である。圧縮は、変換ブロックＴN+1内のピクセル情報の代わりに、変換ブロックＴNとＴN+1との間で位置の平行移動（ｔｒａｎｓｌａｔｉｏｎ）を用いることによって達成される。この単純な例では、単一の平行移動ベクトル（ＤＸ，ＤＹ）が、変換ブロックＴN+1内の２５６ピクセルに関連付けられたビデオ情報に指定されている。
対応する変換ブロックＴNおよびＴN+1内のビデオ情報（すなわちピクセル）は、同一でないことが多い。この両者間の相違が変換ブロックエラーＥと呼ばれ、重要である場合が多い。これは離散コサイン変換（ＤＣＴ）符号化などの従来の圧縮プロセスによって圧縮されるが、変換ブロックエラーＥは扱いにくく、ビデオ信号が圧縮可能な範囲（率）および正確さを制限する。
大部分の変換ブロックエラーＥは、いくつかの理由から、ブロックベースのビデオ圧縮方式で発生する。ブロックベースの動作推定（ｍｏｔｉｏｎ  ｅｓｔｉｍａｔｉｏｎ）は、連続する画像フレーム間での並進運動（ｔｒａｎｓｌａｔｉｏｎａｌ  ｍｏｔｉｏｎ）のみを表す。表示可能な対応する変換ブロックＴNとＴN+1との間での変化だけが、変換ブロックの相対位置における変化である。このような表示方法の欠点は、フルモーションビデオシーケンスが、回転、拡大、ねじり（ｓｈｅａｒ）など、平行移動以外の複雑な動作を含むことが多いことである。こうした複雑な動作を簡単な平行移動近似を使用して表すと、重大なエラーが発生する。
ビデオディスプレイのもう１つの態様は、一般に互いに相対的に変化または移動する複数の画像特徴（ｆｅａｔｕｒｅ）すなわち「ビデオオブジェクト」を含むことである。ビデオオブジェクトは、ビデオディスプレイ内の明瞭な人物、物品、または背景であってもよい。たとえば映画の１場面の場合、その場面の人物（すなわち俳優）および物品（すなわち小道具）は、それぞれ異なるオブジェクトである。それぞれのオブジェクトが、ビデオシーケンスの各フレームにおいて非方形の１組のピクセルで表される。
ビデオシーケンスにおけるオブジェクト間の相対的動作は、従来のビデオ圧縮プロセスにおいて、重大な変換ブロックエラーＥのもう１つの原因である。変換ブロックの規則正しい構成およびサイズによって、その多くが異なるオブジェクトの部分を含む。連続する画像フレーム中のオブジェクト間の相対的な動作は、対応する変換ブロック間で極端に低い相関（すなわち、高変換エラー（ｈｉｇｈ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ  ｅｒｒｏｒ）Ｅ）を生じさせる可能性がある。同様に、連続する画像フレーム内におけるオブジェクトの部分の外観も、（たとえば人物が回転したときに）高変換エラーＥを導く。
従来のビデオ圧縮方式は、変換エラーＥのサイズによって本質的に制限されているように見える。デジタルビデオディスプレイ機能に対する要求が高まるに従って、改良されたデジタルビデオ圧縮プロセスが必要となる。
発明の概要
本発明は、オブジェクトベースのビデオ符号化システムで使用されるスプライトの生成方法に関するものである。従来のビデオ符号化システムとは異なり、オブジェクトベースのビデオ符号化システムは、ビデオシーケンス内のビデオオブジェクトを別々に符号化する。オブジェクトベースのビデオ符号化における「スプライト」とは、１つのビデオシーケンスから集められたビデオオブジェクトの代表画像である。スプライトの生成プロセスは、スプライトの構築およびビデオシーケンス内のビデオオブジェクトからの動作パラメータの算出を参照するので、各フレームのビデオオブジェクトは、スプライトおよび動作パラメータから再構成することができる。
スプライト生成方法には、３つの主なステップが含まれる。この方法は、現在のフレーム内にあるビデオオブジェクトの相対的動作を、前のフレーム用に構成されたスプライトまたは参照ビデオオブジェクトを基準にして推定する。全体動作推定（ｇｌｏｂａｌ  ｍｏｔｉｏｎ  ｅｓｔｉｍａｔｉｏｎ）と呼ばれるこのステップの結果は、スプライトまたは参照オブジェクトを基準にして現在のフレーム内にあるビデオオブジェクトの動作を定義する１組の動作パラメータである。次にこの方法は、動作パラメータを使用して、現在のフレームのビデオオブジェクトを、スプライトまたは参照オブジェクトに変換すなわち「ゆがめる（ｗａｒｐ）」。具体的に言うとこの方法は、ビデオオブジェクトの各ピクセルについて、各ピクセルをスプライトの座標空間に変換することによって、スプライトまたは参照オブジェクト内の対応する位置を算出する。最後にこの方法は、現在のビデオオブジェクトとスプライトまたは参照オブジェクトとを混合する。この方法はスプライトおよびビデオオブジェクトを混合することにより、ビデオオブジェクト内のピクセルと、動作パラメータによって決められた対応する位置にあるスプライトのピクセルとを結合する。このプロセスは、各フレームのビデオオブジェクトに対して反復される。以上のことを要約すると、この方法は各フレームからのビデオオブジェクトのピクセルを、スプライト（または参照オブジェクト）内の対応するピクセルと混合することによって、スプライトを増分的に構成していく。
本発明の一態様は、丸め平均値を使用してビデオオブジェクトとスプライトまたは参照オブジェクトとを混合するための方法である。この方法は丸め平均値を使用するので、各ビデオオブジェクトはスプライトに対して実質的に同等に寄与している。各ビデオオブジェクトを以前に構成されたスプライトに混合する場合、この方法は、それから構成されているビデオオブジェクトの数に比例して、スプライトピクセルに重み付けする。これによって、各フレームからのビデオオブジェクトは、スプライトに対して実質的に同等に寄与することになる。
本発明の別の態様は、前のフレームからのオブジェクトの動作を起点として使用し、各ビデオオブジェクトについて全体動作推定を実行するための方法である。動作推定構成要素の一実施形態において、この方法は、ビデオオブジェクトおよび以前に構成されたスプライトの両方における、ピクセルのすべての対応する対に関して強度（ｉｎｔｅｎｓｉｔｙ）エラーを最小限に抑えることによって、現在のビデオオブジェクトを以前に構成されたスプライトにマップする動作係数を算出する。この構成要素は、ビデオオブジェクトのピクセルとスプライトの対応するピクセルとの間のエラー合計を最小限に抑えるために、ビデオオブジェクト内のピクセルをスプライト内の対応するピクセルに変換する、１組の動作係数の検索を含む。前のフレームの動作係数から開始することによって、現在のフレーム内の動作係数の検索は、ビデオオブジェクト内のピクセルとスプライトまたは参照オブジェクト内の対応するピクセルとの間のエラーを最小限にする１組の動作係数が探しやすくなる。
各フレームについて動作パラメータを算出する場合、この方法は、スプライトまたは参照オブジェクト内部のピクセル位置にマップするビデオオブジェクト内のピクセルだけに基づいて動作を推定することを保証するために、オブジェクトおよびスプライト（または参照オブジェクト）のマスクを使用する。この方法は、全体動作推定プロセスにおけるエラーを削減し、ビデオオブジェクトの動作がスプライトを基準にしたオブジェクトの動作だけに基づくものであることを保証する。
以上概説したスプライト生成方法は、オフラインの静的スプライトを生成するスタンドアロンモジュール（ｓｔａｎｄ−ａｌｏｎｅ  ｍｏｄｕｌｅ）、ならびにオンラインの動的スプライトを生成するように符号器および復号器で統合されたモジュールで実施可能である。本発明は、コンピュータまたは特殊な目的のビデオ符号化ハードウェアで実行されるソフトウェアモジュールで実施可能である。
本発明の特徴および利点は、以下の詳細な説明および付属の図面の参照により明らかになるであろう。
【図面の簡単な説明】
図１は、本発明を具体化する方法および装置の実装に使用することができるコンピュータシステムのブロック図である。
図２Ａおよび図２Ｂは、ビデオ信号に対応する２つの連続する画像フレームを表示した、ビデオディスプレイ装置のディスプレイ画面を簡略化して表示した図である。
図３Ａは、複数の画像フレームのビデオシーケンスでの表示動作を表すデジタル化されたビデオ信号を圧縮するための、ビデオ圧縮符号器プロセスを示す、一般化された機能ブロック図である。図３Ｂは、本発明によるマスタオブジェクト符号器プロセスの機能ブロック図である。
図４は、ビデオシーケンスの画像フレームから選択されたオブジェクトをセグメント化するための、オブジェクトセグメント化プロセスの機能ブロック図である。
図５Ａは図２Ａのビデオディスプレイ装置のディスプレイ画面を簡略化して表示した図であり、図５Ｂは図５Ａのディスプレイ画面の一部を拡大表示した図である。
図６は、連続する画像フレーム内の対応するオブジェクトの中で、対応するピクセルの対の動作ベクトルを決定するための、多角形突合せプロセス（ｐｏｌｙｇｏｎ  ｍａｔｃｈ  ｐｒｏｃｅｓｓ）を示す機能ブロック図である。
図７Ａおよび図７Ｂは、２つの対応するオブジェクトを備えた２つの連続する画像フレームを示す、ディスプレイ画面を簡略化して表示した図である。
図８は、代替ピクセルブロックの相対プロセスを示す機能ブロック図である。
図９Ａは、異なる画像フレーム内で対応するピクセルを識別するのに使用される、第１のピクセルブロックを示す概略図である。図９Ｂは、対応するピクセルが検索される前の画像フレーム内の検索領域に対応するピクセル配列を示す、概略図である。図９Ｃ〜図９Ｇは、対応するピクセルを識別するために図９Ｂのピクセル配列全体でスキャンされる第１のピクセルブロックを示す、概略図である。
図１０Ａは、異なる画像フレーム内で対応するピクセルを識別するのに使用される、第２のピクセルブロックを示す概略図である。図１０Ｂ〜図１０Ｆは、対応するピクセルを識別するために図９Ｂのピクセル配列全体でスキャンされる第２のピクセルブロックを示す概略図である。
図１１Ａは、異なる画像フレーム内で対応するピクセルを識別するのに使用される、第３のピクセルブロックを示す概略図である。図１１Ｂ〜図１１Ｆは、図９Ｂのピクセル配列全体でスキャンされる第３のピクセルブロックを示す概略図である。
図１２は、第１および第２の連続する画像フレーム内にあるオブジェクト間のマッピング生成と、伝送または記憶用のマッピングの量子化を含む、多次元変換方法を示す機能ブロック図である。
図１３は、図１２の多次元変換方法を図示するために、図７Ｂの画像フレームを示すディスプレイ画面を簡略化して表示した図である。
図１４は、図１２の方法によって決定されたアフィン変換係数の量子化に使用される、変換ブロックの３つの選択されたピクセルを示す、拡大した略図である。
図１５は、図１２の多次元変換方式の代替実施形態で使用される、変換ブロック最適化方法を示す機能ブロック図である。
図１６は、図１５の変換ブロック最適化方法を図示する目的で、図７Ｂの画像フレームを示すディスプレイ画面を簡略化し、断片表示した図である。
図１７Ａおよび図１７Ｂは、圧縮を容易にするために任意構成の画像特徴を事前定義された構成に外挿するための、事前圧縮外挿方法を示す機能ブロック図である。
図１８Ａ〜図１８Ｄは、図１４の外挿方法の様々な態様を示すために、単純なオブジェクトが描画されたディスプレイ画面を示す図である。
図１９Ａおよび図１９Ｂは、本発明によりラプラス演算子ピラミッド符号器方法をそれぞれ採用した、符号器方法および復号器方法を示す機能ブロック図である。
図２０Ａ〜図２０Ｄは、図１９Ａの符号器プロセスによって処理される、ピクセルの任意の組または配列のカラー構成要素値を示す、略図である。
図２１は、本発明による動作ベクトル符号化プロセスを示す機能ブロック図である。
図２２は、代替量子化オブジェクトの符号器／復号器プロセスを示す、機能ブロック図である。
図２３Ａは、図３の符号器プロセスと突き合わせたビデオ圧縮復号器を示す、一般化された機能ブロック図である。図２３Ｂは、本発明によるマスタオブジェクト復号器プロセスを示す機能図である。
図２４Ａは、従来の連鎖コード形式（ｃｈａｉｎ  ｃｏｄｅ  ｆｏｒｍａｔ）を示す図である。図２４Ｂは、図２４Ａの連鎖コード形式を使用して処理するための、例示的輪郭を簡略化して表示した図である。
図２５Ａは、本発明の連鎖符号化プロセスを示す機能ブロック図である。
図２５Ｂは、連鎖コード形式を示す図である。
図２５Ｃは、図２５Ａのプロセスで使用される特殊な連鎖コード修正を示す図である。
図２６は、スプライトの生成プロセスまたは符号化プロセスを示す機能ブロック図である。
図２７Ａおよび図２７Ｂは、それぞれビットマップによって定義された第１オブジェクトおよび第２オブジェクトであって、図２６のプロセスによってオブジェクト上に重ね合わされた三角形のグリッドを示す図である。
図２８は、図２６の符号化プロセスに対応する、スプライトの復号化プロセスを示す機能ブロック図である。
図２９は、完全に定義されたオブジェクトのための単純化された復号化プロセスを示す、機能ブロック図である。
図３０は、ビデオシーケンスからスプライトを生成する方法を例示した図である。
図３１は、スプライト生成装置を図示したブロック図である。
図３２は、オブジェクトベースの符号化システムに関して、スプライトを生成するための方法を図示したフローチャートである。
図３３は、全体動作推定のための方法を図示したフローチャートである。
詳細な説明
図１を参照すると、本発明の好ましい実施形態の動作環境は、少なくとも１つの高速処理装置（ＣＰＵ）２２を備え、メモリシステム２４、入力装置２６、および出力装置２８に結合された、汎用タイプまたは専用タイプいずれかのコンピュータシステム２０である。これらの要素は、バス構造３０によって相互接続されている。
図示されたＣＰＵ  ２２は一般的な設計であり、計算を実行するためのＡＬＵ  ３２、データおよび命令を一時的に記憶するためのレジスタのコレクション３４、ならびにシステム２０の動作を制御するための制御ユニット３６を含む。ＣＰＵ  ２２は、Ｄｉｇｉｔａｌ社のＡｌｐｈａ、ＭＩＰＳ  Ｔｅｃｈｎｏｌｏｇｙ、ＮＥＣ、ＩＤＴ、Ｓｉｅｍｅｎｓ、その他各社のＭＩＰＳ、Ｉｎｔｅｌ社およびＣｙｒｉｘ、ＡＭＤ、Ｎｅｘｇｅｎを含む各社のｘ８６、ならびにＩＢＭ社およびＭｏｔｏｒｏｌａ社のＰｏｗｅｒＰＣを含む、様々なアーキテクチャのいずれかを備えたプロセッサであればよい。
メモリシステム２４は、主メモリ３８および補助記憶装置４０を含む。図示された主メモリ３８は、１６メガバイトの半導体ＲＡＭメモリの形式をとる。補助記憶装置４０は、ＲＯＭ、光ディスクまたは磁気ディスク、フラッシュメモリ、あるいはテープなどのような長期記憶形式をとる。当業者であれば、メモリシステム２４が他の多くの代替構成要素を備えられることを理解されよう。
入力装置２６および出力装置２８も一般的な装置である。入力装置２６は、キーボード、マウス、物理変換器（たとえばマイクロフォン）などを備えることができる。出力装置２８は、ディスプレイ、プリンタ、変換器（たとえばスピーカ）などを備えることができる。ネットワークインターフェースまたはモデムなどの装置の中には、入力および／または出力装置として使用できるものもある。
当業者であれば周知のように、コンピュータシステム２０は、オペレーティングシステムおよび少なくとも１つのアプリケーションプログラムをさらに含む。オペレーティングシステムは、コンピュータシステムの動作および資源の割振りを制御する１組のソフトウェアである。アプリケーションプログラムは、ユーザが所望するタスクを実行し、オペレーティングシステムを介したコンピュータ資源の使用を可能にする１組のソフトウェアである。どちらも図示されたメモリシステム２４内に常駐している。
コンピュータプログラミング分野の技術者の実施により、本発明は、特に指定のない限りコンピュータシステム２０によって実行される動作の記号表示を参照しながら、下記に記載される。このような動作は、コンピュータ実行と呼ばれることがある。記号で表示された動作が、データビットを表すＣＰＵ  ２２の電気信号による操作およびメモリシステム２４のメモリ位置でのデータビットの保守、ならびに他の信号処理を含むことを理解されよう。データビットが保守されるメモリ位置は、データビットに対応する特定の電気的、磁気的、または光学的特性を備えた物理的位置である。
図２Ａおよび図２Ｂは、対応するビデオ信号によって電子的に表示されるビデオ画像シーケンスの２つの連続する画像フレーム５４ａおよび５４ｂを示す、ビデオディスプレイ装置５２（たとえば、テレビジョンまたはコンピュータモニタ）のディスプレイ画面５０を簡略化して表示した図である。ビデオ信号は、ＮＴＳＣ、ＰＡＬ、およびＳＥＣＡＭなどのアナログのテレビジョンビデオ形式、ならびにＶＧＡ、ＣＧＡ、およびＥＧＡなどのコンピュータディスプレイで一般に使用されるピクセル化（ｐｉｘｅｌａｔｅｄ）またはデジタル化されたビデオ信号形式を含む、多様なビデオ信号形式が可能である。画像フレームに対応するビデオ信号は、当技術分野で知られている当初生成されたままの、あるいはアナログビデオ信号形式から変換された、デジタル化されたビデオ信号形式であることが好ましい。
画像フレーム５４ａおよび５４ｂは、背景６０上に配置された直方体画像特徴５６およびピラミッド型の画像特徴５８をそれぞれ含む。画像フレーム５４ａおよび５４ｂ内の画像特徴５６および５８は、隠れている部分と表示されている部分が異なるため、外観が異なる。以下の説明では、画像フレーム内にある画像特徴の特定の形式を、オブジェクトあるいはマスクと呼ぶ。したがって、直方体画像特徴５６は、それぞれの画像フレーム５４ａおよび５４ｂ内で直方体オブジェクト５６ａおよび５６ｂとして表示され、ピラミッド形の画像特徴５８は、それぞれの画像フレーム５４ａおよび５４ｂ内でピラミッド形オブジェクト５８ａおよび５８ｂとして表示される。
ピラミッド形画像特徴５８は、画像フレーム５４ａおよび５４ｂ内に同じ位置および配向で表示され、ビデオシーケンスで表示される場合は動きなしで「表示（ａｐｐｅａｒ）」される。直方体５６は、フレーム５４ａおよび５４ｂ内にピラミッド形５８に対して異なる配向および位置で表示され、ビデオシーケンスで表示される場合はピラミッド形５８に対して移動および回転しながら「表示」される。画像特徴５８および６０のこれらの外観は、象徴的であり誇張されている。ビデオシーケンスの画像フレームは、一般に３０〜８０Ｈｚの範囲内の速度で表示される。人間がビデオの動きを知覚するには、一般に２つより多くの画像フレームが必要である。したがって画像フレーム５４ａおよび５４ｂは、本発明を図示する目的で、従来のビデオシーケンスを簡略表示したものである。さらに、本発明がこのような簡略化されたビデオ画像、画像特徴、またはシーケンスに限定されるものではなく、それとは反対に任意の複雑なビデオ画像およびシーケンスに適用可能であることを理解されよう。
ビデオ圧縮符号器プロセスの概要
図３Ａは、複数画像フレームのビデオシーケンスにおける表示動作を表すデジタル化されたビデオ信号を圧縮するための、ビデオ圧縮符号器プロセス６４の一般化された機能ブロック図である。ビデオ情報の圧縮（すなわちビデオシーケンスまたは信号）は、たとえば対話形式またはデジタルテレビジョンおよびマルチメディアコンピュータアプリケーションを含むアプリケーションで、デジタルビデオ情報の節約型の記憶および伝送を提供することができる。簡潔に表すために、符号器プロセス６４の機能ブロックに割り当てられた参照番号は、機能ブロックによって生成された結果についても相互に同じ番号が使用されている。
従来のビデオ圧縮技法は、ピクセルベースの画像フレーム表示が動作表示に変換されるフレーム間圧縮を提供するために、時間相関またはフレーム間相関と呼ばれる連続する画像フレーム間での相似性を利用している。さらに従来のビデオ圧縮技法は、画像フレーム内の動作表示がさらに圧縮されるフレーム内圧縮を提供するために、空間相関またはフレーム内相関と呼ばれる画像フレーム内での相似性も利用している。
ＭＰＥＧ−１、ＭＰＥＧ−２、およびＨ．２６Ｘを含むこうした従来のビデオ圧縮技法では、時間相関および空間相関は、ピクセルの固定された規則正しい（たとえば正方形）配列の単純な平行移動を基準にして決定される。ただしビデオ情報は一般に、ピクセルの矩形配列を平行移動することでは正確に表示できない任意のビデオ動作を含む。したがって、従来のビデオ圧縮技法には一般に、圧縮率および正確さを制限する重大なエラー構成要素が含まれる。
これに対して符号器プロセス６４は、オブジェクトベースのビデオ圧縮を使用して、フレーム間動作およびフレーム内画像特徴を符号化する際の正確さおよび多様性を向上させている。符号器プロセス６４は、固定された規則正しいピクセルの配列ではなく、任意の構成のオブジェクトを基準にして、ビデオ情報を圧縮する。これにより、エラー構成要素が減少し、圧縮の効率および正確さが向上する。別の利点として、オブジェクトベースのビデオ圧縮は、圧縮されたビデオ情報を処理するための対話形式のビデオ編集機能を提供する。
図３Ａを参照すると、機能ブロック６６は、ビデオシーケンスの画像フレーム内にあるユーザ定義オブジェクトが、画像フレーム内の他のオブジェクトからセグメント化されていることを示す。オブジェクトは任意の構成でよく、表示画像内で明瞭な画像特徴を表すことが好ましい。セグメント化には、オブジェクトに対応する画像フレーム内でのピクセルの識別が含まれる。ユーザ定義オブジェクトは、ビデオシーケンスの各画像フレーム内で定義される。たとえば、図２Ａおよび図２Ｂでは、直方体オブジェクト５６ａおよび５６ｂならびにピラミッド形オブジェクト５８ａおよび５８ｂは別々にセグメント化されている。
セグメント化されたオブジェクトは、オブジェクトのバイナリまたはマルチビット（たとえば８ビット）の「アルファチャネル（ａｌｐｈａｃｈａｎｎｅｌ）」マスクで表される。オブジェクトマスクは、オブジェクトのサイズ、構成、および位置をピクセルごとに示す。簡潔にするために、以下の説明は、オブジェクトの各ピクセルが一般的な２４ビット（すなわち３色の構成要素値がそれぞれ８ビット）ではなく、単一のバイナリビットによって表されているバイナリマスクを対象とする。マルチビット（たとえば８ビット）マスクも使用されている。
機能ブロック６８は、各オブジェクトの「フィーチャポイント（ｆｅａｔｕｒｅ  ｐｏｉｎｔ）」がユーザによって定義されることを示す。フィーチャポイントは、オブジェクトの明瞭な特徴または態様であることが好ましい。たとえば、コーナー７０ａ〜７０ｃおよびコーナー７２ａ〜７２ｃは、ユーザによってそれぞれ直方体５６およびピラミッド形５８のフィーチャポイントとして定義することができる。各画像フレーム内で各オブジェクトマスクおよびそのフィーチャポイントに対応するピクセルは、メモリシステム２４に格納されたオブジェクトデータベースに記憶される。
機能ブロック７４は、連続する画像フレーム内にあるフィーチャポイントの位置の変化が識別され、連続する画像フレーム間のフィーチャポイントについて軌線が決定されることを示す。軌線は、フィーチャポイントの移動の方向および範囲を表す。機能ブロック７６は、前のフレームＮ−１と現在のフレームＮとの間で、オブジェクト内にあるフィーチャポイントの軌線も、オブジェクトデータベースから取り出されることを示す。
機能ブロック７８は、前のフレームＮ−１と現在のフレームＮとの間のオブジェクトについて、疎動作変換（ｓｐａｒｓｅ  ｍｏｔｉｏｎ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ）が決定されることを示す。疎動作変換は、フレームＮ−１とフレームＮとの間のフィーチャポイントの軌線に基づく。疎動作変換は、前のフレームＮ−１と現在のフレームＮの間のオブジェクトの変化を概算する。
機能ブロック８０は、現在のフレームＮのオブジェクトのマスクが、メモリシステム２４にあるオブジェクトデータベースから取り出されることを示す。
機能ブロック９０は、量子化されたマスタオブジェクトまたは「スプライト」が、画像フレームシーケンスの画像特徴に対応するオブジェクトまたはマスク６６と、フィーチャポイントの軌線７４から形成されることを示す。マスタオブジェクトは、複数のフレームに表示されているオブジェクトの態様または特徴をすべて含むことが好ましい。たとえば図２Ａおよび図２Ｂを参照すると、フレーム５４ｂの直方体５６は、フレーム５４ａでは表示されていない側面７８ｂを含む。同様に、フレーム５４ａの直方体５６は、フレーム５４ｂでは表示されていない側面７８ａを含む。直方体５６のマスタオブジェクトは、側面７８ａおよび７８ｂの両方を含む。
疎動作変換７８は、フレームＮ−１とフレームＮとの間でのオブジェクトの変化を完全に表さないことが多い。たとえば、矩形オブジェクト５４ａのような前のフレームＮ−１にあるオブジェクトは、矩形オブジェクト５４ｂの側面７８ｂのような現在のフレームＮにあるオブジェクトのすべての特徴を含まないことがある。
したがって、変換の正確さを向上させるために、当技術分野で知られている論理ＡＮＤ関数などによって、前のフレームＮ−１および現在のフレームＮにあるオブジェクトのマスクの共通部分（ｉｎｔｅｒｓｅｃｔｉｏｎ）が決定される。現在のフレームＮにあるオブジェクトのマスクは、前のフレームＮ−１にあるオブジェクトには含まれていない現在のフレームＮにあるオブジェクトの部分または特徴（たとえば、前述の矩形オブジェクト５４ｂの側面７８ｂ）を識別するために、結果として得られる共通部分から減算される。オブジェクトの新しく識別された部分がマスタオブジェクト９０に組み込まれるので、フレームＮ−１およびフレームＮにあるオブジェクトの完全な表示を含むことになる。
機能ブロック９６は、前のフレームＮ−１にあるオブジェクト９８の量子化された形（たとえば画像フレーム５４ａの直方体オブジェクト５６ａ）が、現在のフレームＮにあるオブジェクト１０２の予測される形（たとえば画像フレーム５４ｂにある直方体オブジェクト５６ｂ）を提供するために、稠密動作変換（ｄｅｎｓｅ  ｍｏｔｉｏｎ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ）によって変換されることを示す。この変換が、オブジェクトベースのフレーム間圧縮を提供する。
稠密動作変換は、フレームＮ−１にある量子化された前のオブジェクト９８と現在のフレームＮにあるオブジェクトとの間のアフィン変換を決定するステップと、そのアフィン変換を量子化された前のオブジェクト９８に適用するステップとを含むことが好ましい。好ましいアフィン変換はアフィン変換係数１０４によって表され、平行移動、回転、拡大、およびねじりを描写することができる。アフィン変換は、稠密動作推定から決定され、前の量子化されたオブジェクト９８と現在のフレームＮにあるオブジェクトとの間のピクセルごとのマッピングを含むことが好ましい。
予測された現在のオブジェクト１０２は、量子化された前のオブジェクト９８によって、稠密動作変換９６によって修正されたように表され、マスタオブジェクト９０から取得した新しい画像態様と合わせて、相対的に複雑な動作を表すことができる。オブジェクトに関連付けられた知覚的および空間的な連続によって、一般に異なる画像フレームにおける異なるオブジェクト間の関係を変更することから生じるエラーがなくなるため、このようなオブジェクトベースの表示は相対的に正確である。さらに、オブジェクトベースの表示を使用することで、ユーザは様々な複雑さのオブジェクトを表示するための相対的な効率性および正確さを最適化するために、解像度レベルの違う異なるオブジェクトを表示することができる。
機能ブロック１０６は、画像フレームＮの場合、予測されたオブジェクト１０２の推定エラー１１０を判定するために、現在のフレームＮについて、オリジナルオブジェクト１０８から予測された現在のオブジェクト１０２が減算されることを示す。推定エラー１１０は、量子化された前のオブジェクト９８を基準にした、画像フレームＮにある現在のオブジェクト１０８の圧縮表示である。さらに具体的に言えば、現在のオブジェクト１０８は、推定エラー１１０および量子化された前のオブジェクト９８から復号化または再構成することができる。
機能ブロック１１２は、推定エラー１１０が、ラチスサブバンド（ｌａｔｔｉｃｅ  ｓｕｂｂａｎｄ）（ウェーブレット）圧縮などの従来の「損失のある」静止画像圧縮方法によって、あるいはＶａｉｄｙａｎａｔｈａｎ著「Ｍｕｌｔｉｒａｔｅ  Ｓｙｓｔｅｍｓ  ａｎｄ  Ｆｉｌｔｅｒ  Ｂａｎｋｓ」、ＰＴＲ  Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，Ｉｎｃ．，Ｅｎｇｌｅｗｏｏｄ  Ｃｌｉｆｆｓ，Ｎｅｗ  Ｊｅｒｓｅｙ，（１９９３年）に記載されている符号化、またはＰｅｎｎｅｂａｋｅｒ他著「ＪＰＥＧ：Ｓｔｉｌｌ  Ｉｍａｇｅ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｓｔａｎｄａｒｄ」Ｖａｎ  Ｎｏｓｔｒａｎｄ  Ｒｅｉｎｈｏｌｄ，Ｎｅｗ  Ｙｏｒｋ（１９９３年）に記載されている離散コサイン変換（ＤＣＴ）符号化によって、圧縮または「符号化」されることを示す。
当技術分野で知られている「損失のある」圧縮方法は、データ圧縮率を上げるために一部データのゆがみを生じる。データのゆがみとは、圧縮前のオリジナルデータと圧縮および圧縮解除後に結果として生じるデータとの間の変化を指している。以下の例示では、機能ブロック１０２の圧縮または符号化はウェーブレット符号化であると仮定される。
機能ブロック１１４は、機能ブロック１１２からのウェーブレット符号化済み推定エラーが、圧縮データ１１６を形成するために、従来の「損失のない」静止画像圧縮方法によってさらに圧縮または「符号化」されることを示す。好ましい従来の「損失のない」静止画像圧縮方法は、Ｐｅｎｎｅｂａｋｅｒ他著「ＪＰＥＧ：Ｓｔｉｌｌ  Ｉｍａｇｅ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｓｔａｎｄａｒｄ」に記載されているエントロピー符号化である。当技術分野で知られている「損失のない」圧縮方法はデータのゆがみを生じない。
エラーフィードバックループ１１８は、後続のフレームＮ＋１のために前の量子化されたオブジェクトを取得するため、フレームＮのオブジェクトに対して、関数ブロック１１２からのウェーブレット符号化済み推定エラーを使用する。フィードバックループ１１８での初期ステップとして、機能ブロック１２０は、機能ブロック１１２からのウェーブレット符号化済み推定エラーが、画像フレームＮのオブジェクトに量子化エラー１２２を形成するために、逆ウェーブレット符号化、すなわちウェーブレット復号化されることを示す。
損失のある静止画像圧縮方式による連続する符号化および復号化推定エラー１１０の効果は、一般に見る人が知覚できないビデオ情報を量子化エラー１２２から削除することである。この情報は一般に高周波数である。その結果、このような高周波数の構成要素を削除すると、画像品質の低下を最小限にとどめながら、一般に画像圧縮率を約２００％まで向上させることができる。
機能ブロック１２４は、どちらも画像フレームＮに関する量子化エラー１２２および予測オブジェクト１０２が、画像フレームＮに量子化されたオブジェクト１２６を形成するために共に加えられることを示す。タイミング調整遅延１２８後、量子化されたオブジェクト１２６は量子化された前のオブジェクト９８になり、画像フレームＮ＋１で対応するオブジェクトを処理するための基準として使用される。
符号器プロセス６４は、改善されたフレーム間圧縮を取得するために、連続する画像フレームにおける対応するオブジェクトの時間相関を使用し、正確かつ効率的なフレーム内圧縮を取得するために、オブジェクト内での空間相関も使用する。フレーム間圧縮の場合、動作推定および補償が実行されるので、１つのフレーム内で定義されたオブジェクトを連続するフレーム内で推定することができる。連続するフレーム内で動作ベースのオブジェクトを推定するには、従来のブロックベースのオブジェクト表示よりもかなり少ない情報量でなければならない。フレーム内圧縮の場合、フレーム内でのオブジェクトの空間相関を使用し、異なるオブジェクトを異なる解像度で表示できるようにするために、各オブジェクトの推定エラー信号が圧縮される。フィードバックループ１１８では、後続フレーム内のオブジェクトを完全に圧縮解除されたオブジェクトから予測することが可能であり、それによって推定エラーの蓄積を防ぐことができる。
符号器プロセス６４は、複数の画像フレームのビデオシーケンスでの表示動作を表す、デジタル化されたビデオ信号の圧縮または符号化された表示を、出力として提供する。この圧縮または符号化された表示は、オブジェクトマスク６６、フィーチャポイント６８、アフィン変換係数１０４、および圧縮エラーデータ１１６を含む。符号化された表示は、ビデオ情報が使用される特定のアプリケーションに基づいて、記憶または伝送することができる。
図３Ｂは、マスタオブジェクト９０を符号化または圧縮するための、マスタオブジェクト符号化プロセス１３０を示す機能ブロック図である。機能ブロック１３２は、マスタオブジェクト９０が、ラチスサブバンド（ウェーブレット）圧縮または離散コサイン変換（ＤＣＴ）符号化など、従来の「損失のある」静止画像圧縮方法によって圧縮または符号化されることを示す。機能ブロック１３２はウェーブレット符号化を採用することが好ましい。
機能ブロック１３４は、機能ブロック１３２からのウェーブレット符号化マスタオブジェクトが、圧縮されたマスタオブジェクトデータ１３６を形成するために、従来の「損失のない」静止画像圧縮方式によって、さらに圧縮または符号化されることを示す。好ましい従来の損失のない静止画像圧縮方法は、エントロピー符号化である。
符号器プロセス１３０は、出力として圧縮されたマスタオブジェクト１３６を提供する。符号器プロセス６４が提供する圧縮または符号化された表示と共に、圧縮されたマスタオブジェクト１３６は、複数の画像フレームのビデオシーケンスを取得するために、記憶または伝送後に圧縮解除または復号化されてもよい。
符号化プロセス６４については、画像フレーム内の単一オブジェクトに対応するビデオ情報の符号化を参照しながら記述する。図２Ａおよび図２Ｂならびに前述のように、符号器プロセス６４は、１つの画像フレーム内にあるそれぞれのオブジェクト（たとえば図２Ａおよび図２Ｂのオブジェクト５６および５８）について別々に実行される。さらに、多くのビデオ画像は、その上に任意数の画像特徴またはオブジェクトが描画される背景を含む。この背景は、本発明によれば、すべてのユーザ定義オブジェクトが処理された後で、オブジェクトとして処理される。
画像フレーム内でオブジェクトを処理するには、そのオブジェクトが別々に識別される必要がある。符号器プロセス６４は、一番前のオブジェクトから始まり、連続して一番後のオブジェクト（たとえば背景）まで順番に、画像フレームのオブジェクトに適用されることが好ましい。符号化されたオブジェクトをビデオ画像に合成するステップは、一番後のオブジェクト（たとえば背景）から連続して一番前のオブジェクト（たとえば図２Ａおよび図２Ｂの直方体５６）まで順番に実行されることが好ましい。符号化オブジェクトの積層は、画像フレームのオブジェクトに関連付けられた明瞭な層状データとして、あるいは積層または合成シーケンスに対応する順序で符号化オブジェクトを伝送または取得することによって送られる。
オブジェクトのセグメント化および追跡
好ましい実施形態では、機能ブロック６６で参照される画像フレーム内でのオブジェクトのセグメント化を使用すると、ユーザが対話式にセグメント化を実行することができる。本発明のオブジェクトのセグメント化は、オブジェクトのセグメント化において正確さを向上させ、相対的に高速であって、セグメント化されるオブジェクトを定義する際にユーザに最適な柔軟性を与える。
図４は、ビデオシーケンスの画像フレームから選択されたオブジェクトをセグメント化するための、オブジェクトセグメント化プロセス１４０を示す機能ブロック図である。プロセス１４０によるオブジェクトセグメント化は、正確かつ高速で、ユーザが定義しやすいオブジェクトの知覚グループ化を提供する。
図５Ａは、画像フレーム５４ａおよび直方体オブジェクト５６ａのセグメント化を示す、ビデオディスプレイ装置５２のディスプレイ画面５０を簡略化した図である。このディスプレイ画面５０上の描画では、直方体オブジェクト５６ａには、オブジェクト内部１４４の境界となるオブジェクト周囲（ｏｂｊｅｃｔ  ｐｅｒｉｍｅｔｅｒ）１４２（明確にするためにオブジェクト５６ａから離して表示）が含まれる。オブジェクト内部１４４とは、ディスプレイ画面５０上にあるオブジェクト５６ａの輪郭のことであって、一般に内部表面または図のように画像特徴の外部表面に対応している場合がある。図５Ｂはディスプレイ画面５０の一部を拡大表示した図であって、直方体オブジェクト５６ａの半自動セグメント化を示す。以下の記述は、特別に直方体オブジェクト５６ａを基準にしているが、画像フレームからセグメント化される各オブジェクトに同様に適用可能である。
機能ブロック１４６は、ユーザがオブジェクト内部１４４でオブジェクト周囲１４２の内部輪郭１４８を形成することを示す。ユーザは、マウスやトラックボールなどの従来のポインタまたはカーソル制御装置を使用して、内部輪郭１４８を形成することが好ましい。内部輪郭１４８は、オブジェクト周囲１４２から公称寸法１５０内で形成される。公称寸法１５０は、ユーザが周囲１４２の公称寸法１５０内で相対的に素早く内部輪郭１４８を形成できる十分な大きさになるように、ユーザによって選択される。公称寸法１５０は、たとえばおよそ４から１０ピクセルの間で一致する。
機能ブロック１４６は、ビデオシーケンスの主フレームに関連して実行される。従来の映画の１場面を参照すると、たとえば主（ｋｅｙ）フレームは１場面の複数フレームの中で最初のフレームである場合がある。この機能にユーザが参加すると、オブジェクトセグメント化プロセス１４０が半自動的になるが、オブジェクトをセグメント化する際の正確さおよび柔軟性がかなり増加する。主フレーム以外についても、以下に詳細に記載するように、後続の画像フレーム内のオブジェクトは自動的にセグメント化される。
機能ブロック１５２は、外部輪郭１５６を形成するために内部輪郭１４８が自動的に拡張されることを示す。外部輪郭１５６の形成は、輪郭１４８の比較的単純な画像拡大として実行されるので、外部輪郭１５６は内部輪郭１４８からユーザが定義したピクセル数である。内部輪郭１４８と外部輪郭１５６との間の距離は、公称寸法１５０の約２倍であることが好ましい。
機能ブロック１５８は、内部輪郭１４８と外部輪郭１５６との間のピクセル数が、オブジェクト内部１４４の中にあるかどうかによって、あらかじめ定義された属性に従って分類され、それによってオブジェクト周囲１４２および図３Ａを参照して記述されたタイプの対応するマスク８０を自動的に識別することを示す。画像属性はピクセルのカラーおよび位置を含むが、属性は単独で使用されるかまたは他の属性と共に使用されるかのいずれかであることが好ましい。
好ましい実施形態では、内部輪郭１４８および外部輪郭１５６の各ピクセルが、（ｒ，ｇ，ｂ，ｘ，ｙ）の形で５次元ベクトルとして表される「クラスタセンタ（ｃｌｕｓｔｅｒ  ｃｅｎｔｅｒ）」を定義する。語ｒ、ｇ、およびｂは、それぞれ各ピクセルに関連付けられたレッド、グリーン、およびブルーのカラー構成要素に対応し、語ｘおよびｙはピクセル位置に対応する。内部輪郭１４８のピクセルに対応するｍ個のクラスタセンタベクトルは｛Ｉ0，Ｉ1，．．．，Ｉm-1｝と明示され、外部輪郭１５６のピクセルに対応するｎ個のクラスタセンタベクトルは｛Ｏ0，Ｏ1，．．．，Ｏn-1｝と明示される。
クラスタセンタベクトルＩiとＯjとの間のピクセルは、各ピクセルが５次元ベクトル空間内で最も近いベクトルを識別することによって分類される。各ピクセルについて、それぞれクラスタセンタベクトルＩiおよびＯjまでの絶対距離ｄiおよびｄjが、次式によって計算される。
0004572010.tif 000002
上式でｗcolorおよびｗcoordは、それぞれカラーおよびピクセル位置情報を表す重みづけ因子（ｗｅｉｇｈｔｉｎｇ  ｆａｃｔｏｒ）である。重みづけ因子ｗcolorおよびｗcoordは合計１になればそれ以外はユーザが選択できる値である。重みづけ因子ｗcolorおよびｗcoordは０．５に等しい値であることが好ましい。各ピクセルはクラスタセンタベクトルＩiおよびＯjのいずれか１つまでの最短５次元距離により、オブジェクト内部１４４または外部に関連付けられる。
機能ブロック１６２は、ユーザが、初期フレームまたは主フレームの各オブジェクトで、少なくとも２つ、好ましくはそれ以上（たとえば４から６）のフィーチャポイントを選択することを示す。フィーチャポイントは、オブジェクトの相対的に明瞭な態様であることが好ましい。たとえば直方体画像特徴５６を参照すると、コーナー７０ａ〜７０ｃがフィーチャポイントとして選択できる。
機能ブロック１６４は、選択されたそれぞれのフィーチャポイント（たとえば、コーナ７０ａ〜７０ｃ）を中心とする複数ピクセルからなるブロック１６６が定義され、後続画面フレーム内にある対応するブロック（たとえば次の連続する画像フレーム）と突き合わせられることを示す。ピクセルブロック１６６はユーザによって定義されるが、画像内部１４４の範囲内にあるピクセルしか含まない、３２×３２ピクセル配列を含むことが好ましい。機能ブロック１５８で決定されたように（例えば、コーナー７０ｂおよび７０ｃ）オブジェクト内部１４４から外へ出ているピクセルブロック１６６の任意のピクセル１６８（クロスハッチング（ｃｒｏｓｓ−ｈａｔｃｈｉｎｇ）で表示）は省かれる。ピクセルブロック１６６は、従来のブロック突合せプロセス、または以下に詳しく記載されている多角形突合せプロセスによって識別される最小絶対誤差により、次の画像フレーム内にある対応するピクセルブロックと突き合わせられる。
機能ブロック１７０は、オブジェクトの疎動作変換が、２つの連続する画像フレーム内にある対応するフィーチャポイントから決定されることを示す。機能ブロック１７２は、次の画像フレームにマスク８０の推定を提供するために、現在の画像フレームのマスク８０が疎動作変換によって変換されることを示す。連続する画像フレーム内で識別されない、現在のフレーム内にあるフィーチャポイントは無視される。
機能ブロック１７４は、次の画像フレームに対して結果として得られるマスク８０の推定が１フレームずつ遅延し、次の連続するサイクルに対して輪郭１７６として機能することを示す。同様に、機能ブロック１７８は、対応するフィーチャポイントも１フレームずつ遅延し、次の連続するフレームに対して初期のフィーチャポイント１８０として使用されることを示す。
多角形突合せ方法
図６は、連続する画像フレーム内にある対応する各ピクセル対について動作ベクトルを決定するための、多角形突合せプロセス２００を示す、機能ブロック図である。このように稠密動作ベクトルを決定することによって、図３Ａの稠密動作変換９６を決定するための基礎とする。
多角形突合せプロセス２００は、従来のブロック突合せプロセスと同様、連続する画像フレーム間の広範囲な動作を決定することができる。ただし従来のブロック突合せプロセスとは異なり、多角形突合せプロセス２００は、オブジェクト周囲の近くまたはオブジェクト周囲上にあるピクセルについてもその正確さが変わることなく、エラーの生成も著しく少ない。多角形突合せ方法２００の好ましい実施例では、計算効率も改善されている。
多角形ブロック方法２００は、図７Ａおよび図７Ｂを参照しながら説明されており、これらの図は２つの連続する画像フレーム２０２ａおよび２０２ｂを表示したディスプレイ画面５０を簡略化して示した図であって、この画面では画像特徴２０４がそれぞれオブジェクト２０４ａおよび２０４ｂとして描画されている。
機能ブロック２０６は、画像フレーム２０２ａおよび２０２ｂのオブジェクト２０４ａおよび２０４ｂが識別され、たとえばオブジェクトセグメント化方法１４０によってセグメント化されることを示す。
機能ブロック２０８は、オブジェクト２０４ｂに適用されるピクセルブロック２１０ｂの寸法（たとえば１５×１５ピクセル）およびオブジェクト２０４ａに関する検索範囲２１２の寸法が決定されることを示す。ピクセルブロック２１０ｂは、オブジェクト２０４ｂ内の各ピクセルに関する領域を定義し、この領域に対して対応するピクセルブロック２１０ａがオブジェクト２０４ａ内で識別される。検索範囲２１２は、対応するピクセルブロック２１０ａが検索される領域を確立する。ピクセルブロック２１０ｂおよび検索範囲２１２では、ピクセルが整然と規則正しく並んだ配列になっており、ユーザによって定義されたサイズであることが好ましい。
機能ブロック２１４は、オブジェクト２０４ｂ内の初期ピクセル２１６が識別され、現在のピクセルとなることを示す。初期ピクセル２１６は、たとえば縦方向の最大範囲および横方向の最小範囲にあるピクセルというように、多様な基準で定義することができる。図のように、ディスプレイ画面５０上のピクセルを座標軸２２０に従って配列すると、初期ピクセル２１６は、最大のｙ座標値および最小のｘ座標値を有するオブジェクト２１４ｂのピクセルとして表すことができる。
機能ブロック２２２は、ピクセルブロック２１０ｂが現在のピクセルを中心として広がっていることを示す。
機能ブロック２２４は、ピクセルブロック２１０ｂがオブジェクト２０４ｂに含まれていないピクセル（たとえば、図７Ｂのクロスハッチングで表示されているピクセル２２６）を含んでいるかどうかに関する問合せを示す。この問合せは、機能ブロック２０６により識別されたオブジェクトを参照しながら行われる。現在のピクセル上に位置するピクセルブロック２１０ｂの中でオブジェクト２０４ｂの外に出ているピクセルがある場合、機能ブロック２２４から必ず機能ブロック２２８へ進み、そうでない場合は機能ブロック２３２へ進む。
機能ブロック２２８は、ピクセルブロック２１０ｂの中でオブジェクト２０４ｂの外に出ているピクセル（たとえばピクセル２２６）は、ピクセルブロック２１０ｂによって定義される領域から省かれるので、この領域にはオブジェクト２０４ｂの中にあるピクセルだけが含まれることを示す。その結果、ピクセルブロック２１０ｂの定義する領域は、一般に最初に定義された正方形または四角形の領域よりも複雑な多角形となることが多い。
機能ブロック２３２は、オブジェクト２０４ａ内のピクセルが、オブジェクト２０４ｂの現在のピクセルに対応して識別されることを示す。オブジェクト２０４ａ内のピクセルは、前の対応ピクセルと呼ばれる。この前の対応ピクセルは、検索範囲２１２内の各ピクセルに関してピクセルブロック２１０ａを形成することと、オブジェクト２０４ｂ内の現在のピクセルに関して、ピクセルブロック２１０ａとピクセルブロック２１０ｂとの間の相関を決定することによって識別されることが好ましい。ピクセルブロック２１０ａと２１０ｂとの間の各相関は、たとえば平均絶対誤差によって決定することができる。前の対応ピクセルは、ピクセルブロック２１０ｂに対して平均絶対誤差が最小になっている検索範囲２１２内のピクセルブロック２１０ａを識別することによって識別される。ピクセルブロック２１０ｂに対して、ピクセルブロック２１０ａの平均絶対誤差Ｅは次式のように決定される。
0004572010.tif 000003
上式でｒij、ｇij、およびｂijはそれぞれ、ピクセルブロック２１０ｂ内の各ピクセルに関連付けられたレッド、グリーン、およびブルーのカラー構成要素に対応しており、ｒij′、ｇij′、およびｂij′はそれぞれ、ピクセルブロック２１０ａ内の各ピクセルに関連付けられたレッド、グリーン、およびブルーのカラー構成要素に対応している。
上記で述べたように、平均絶対誤差Ｅの合計は、ｍｘｎピクセル寸法を有するピクセル配列を備えたピクセルブロックを意味する。多角形構成のピクセルブロック２１０ｂは、たとえば多角形ピクセルブロック２１０ｂの外にあるすべてのピクセルのカラー構成要素に対してゼロ値を定義することにより、相対的に単純に対処される。
機能ブロック２３４は、オブジェクト２０４ｂ内にある各ピクセル間の動作ベクトルＭＶ、およびオブジェクト２０４ａ内にある対応する前のピクセルが決定されることを示す。動作ベクトルは、オブジェクト２０４ｂ内のピクセル位置と、オブジェクト２０４ａ内の対応する前のピクセル位置との間の差異として、次式のように定義される。
0004572010.tif 000004
上式でｘiおよびｙjはそれぞれピクセルブロック２１０ｂ内にあるピクセルのｘ座標位置およびｙ座標位置に相当し、ｘk′およびｙl′はそれぞれピクセルブロック２１０ａ内にある対応する前のピクセルのｘ座標位置およびｙ座標位置に相当する。
機能ブロック２３６は、オブジェクト２０４ｂが残りのピクセルを含んでいるかどうかに関する問合せを示す。オブジェクト２０４ｂが残りのピクセルを含んでいる場合は、必ず機能ブロック２３６から機能ブロック２３８へ進み、そうでない場合は最終ブロック２４０へ進む。
機能ブロック２３８は、オブジェクト２０４ｂ内にある次のピクセルが、あらかじめ定義された形式または順番に従って識別されることを示す。初期ピクセルが前述のように機能ブロック２１４を基準にして選択されると、後続のピクセルは、第１に行内で次の隣接するピクセル（すなわち共通ｙ座標値）を識別することによって、さらにオブジェクト２０４が行内に他のピクセルを含んでいない場合は、次の下行にある第１のピクセルまたは一番左のピクセル（すなわち最小のｘ座標値）に進むことによって定義することができる。こうして識別されたピクセルが現在のピクセルとなり、機能ブロック２３８は機能ブロック２２２に戻る。
多角形ブロック方法２００は、たとえオブジェクト周囲上にある場合またはその近くにある場合であっても、対応するピクセルを正確に識別する。ピクセルブロック２１０ｂの中でオブジェクト２０４ｂの外に出ているピクセルを省くかまたは無視することによって、従来のブロック突合せプロセスの重大なエラーの原因はなくなる。従来のブロック突合せプロセスは、均一なピクセルブロック構成を厳密に適用し、セグメント化されたオブジェクトを基準として適用されることはない。オブジェクトが移動するかまたはその背景が変化すると、オブジェクトの外にあるピクセルは著しく変化する可能性があるので、均一なブロック構成は、オブジェクトの周囲に隣接するピクセルに重大なエラーを生じさせる。このように、従来のブロック突合せプロセスには無関係なピクセルの変化が含まれるので、オブジェクト周囲付近にあるピクセルを、前の画像フレーム内にある対応するピクセルで正確に相関することはできない。
オブジェクト２０４ｂの各ピクセルの場合、オブジェクト２０４ａ内にある対応する前のピクセルは、ピクセルブロック２１０ｂを、前のオブジェクト２０４ａ内にある各ピクセルについてピクセルブロック２１０ａと比較することによって識別される。対応する前のピクセルは、ピクセルブロック２１０ｂと最もよく相関するピクセルブロック２１０ａを有するオブジェクト２０４ａ内のピクセルである。従来の方法で処理される場合、このような決定方法には、それぞれの対応する前のピクセルを識別するために非常に多くの計算が必要になる場合がある。実例を挙げると、ｍ×ｍ寸法のピクセルを有する検索範囲２１２よりもかなり小さいｎ×ｎ寸法のピクセルを有するピクセルブロックの場合、前のオブジェクト２０４ａ内にあるそれぞれの対応する前のピクセルを識別するには、約ｎ2×ｍ2の計算が必要である。
ピクセルブロックの相関プロセス
図８は、機能ブロック２３２を参照して記載されたプロセスの代わりに使用することが望ましい、修正されたピクセルブロック相関プロセス２６０を示す、機能ブロック図である。修正された相関プロセス２６０では、必要な計算の数を大幅に削減するために、ピクセルブロック２１０ｂおよび２１０ａの相関に固有の冗長性を利用する。
相関プロセス２６０は、連続する画像フレーム２０２ａおよび２０２ｂに対応するピクセルの任意のグループを表す概略図である、図９Ａ〜図９Ｇおよび図１０Ａ〜図１０Ｇを基準に記載される。特に、図９Ａは、各文字が異なるピクセルに対応した５×５寸法のピクセルを有する、ピクセルブロック２６２の概略図である。ピクセルブロック２６２のピクセルは、明確な列２６４を含む整然と規則正しく並んだピクセルの配列になっている。図９Ｂは、ｑ×ｑ寸法のピクセルを有し、前の画像フレーム２０２ａ内の検索範囲２１２に対応している、ピクセル配列２６６を表す。図９Ｂの各数字は、別々のピクセルを表す。相関プロセス２６０は、従来の整然と規則正しく並んだピクセルブロック２６２を基準に記載されているが、多角形突合せプロセス２００を基準に記載されたタイプの多角形ピクセルブロックにも同様に適用可能である。
機能ブロック２６８は、初期ピクセルブロック（たとえばピクセルブロック２６２）が、中央のピクセルＭに関して定義され、従来のブロック突合せプロセスの場合と同様に一般にラスタパターン（図７Ａに一部表示）で、検索範囲２１２全体（たとえばピクセル配列２６６）にわたってスキャンされていることを示す。図９Ｃ〜図９Ｇは、ピクセルブロック２６２とピクセル配列２６６との間のブロック突合せプロセスにおける、約ｑ2のステップを５つ示した概略図である。
ピクセル配列２６６全体にわたるピクセルブロック２６２のスキャンは従来の方法で実行されるが、それらの間の相関に関する計算は本発明により別々に実行される。特に、相関（たとえば平均絶対誤差）は、各スキャン位置におけるピクセルブロック２６２の各列２６４について決定および記憶される。各スキャン位置におけるピクセルブロック２６２の各列２６４について決定および記憶される相関は列相関２７０と呼ばれ、それらのいくつかは、相関されたピクセルを示すことによって図９Ｃ〜図９Ｇに記号で示されている。実例を挙げると、図９Ｃは、ピクセル配列２６６と位置合わせされたピクセルブロック２６２の単一の列２６４について決定された列相関２７０（１）を示す。同様に、図９Ｄは、ピクセル配列２６６と位置合わせされたピクセルブロック２６２の２つの列２６４について決定された、列相関２７０（２）および２７０（３）を示す。図９Ｅ〜図９Ｇは、ピクセル配列２６６に関する例示的な３つの後続スキャン位置における、ピクセルブロック２６２との同様の列相関を示す。
ピクセル配列２６６上での初期ピクセルブロック２６２のスキャンによって、列相関の記憶された配列またはデータベースが提供される。ｒ個の列２６４を有するピクセルブロック２６２とｑ×ｑ個のピクセルを有するピクセル配列２６６を備えている列相関データベースは、約ｒｑ2個の列相関を含む。ピクセルＭがピクセル配列２６６の最初の行のピクセルと位置合わせされるように、ピクセルブロック２６２はピクセル配列２６６全体で最初にスキャンされることが好ましいので、この列相関数は単なる概数である。
図９Ｃに示されているステップで始まる残りのステップは、ピクセル配列２６６全体にわたってピクセルブロック２６２が完全に２回スキャンされた後（すなわち、ピクセルＭがピクセル配列２６６の第１行および第２行と位置合わせされた後）に実行される。
機能ブロック２７４は、次のピクセルブロック２７６（図１０Ａ）が、たとえば、ピクセルＭと同じ行にある中央ピクセルＮを基準にして画像フレーム２０２ｂから定義されることを示す。ピクセルブロック２７６は、ピクセルブロック２６２に含まれていないピクセルの列２７８、およびピクセルブロック２６２に含まれているピクセルの列２８０とを含む。ピクセルブロック２７６は、ピクセルブロック２６２に含まれていた列２８２（図９Ａ）を含まない。このような次のピクセルブロック２７６の増分定義は、従来のブロック突合せプロセスで使用されていたものと実質的に同じである。
機能ブロック２８４は、ピクセルブロック２７６がピクセル配列２６６全体にわたって、機能ブロック２６８を基準にした前述の方法でスキャンされることを示す。図１０Ｂ〜図１０Ｇは、図９Ｃ〜図９Ｇと同様に、ピクセル配列２６６全体にわたるピクセルブロック２７６のスキャンを示す。
機能ブロック２８６は、列２７８の場合、列相関が各スキャン位置で決定および記憶されることを示す。したがって、列相関２８８（１）〜２８８（５）は、それぞれ図１０Ｂ〜図１０Ｆに示された列２７８のスキャン位置に関して実行される。
機能ブロック２９０は、ピクセルブロック２７６のそれぞれの列２８０では、記憶された列の決定は、機能ブロック２６８で前に計算されて記憶された各スキャン位置について取り出される。たとえば、図９Ｃの列相関２７０（１）は、図１０Ｃの列相関２７０′（１）と同じである。同様に、図１０Ｄ〜図１０Ｆの列相関２７０′（２）、２７０′（３）、２７０′（５）〜２７０′（８）、および２７０′（１５）〜２７０′（１８）は、図９Ｄ、図９Ｅ、および図９Ｇの対応する列相関と同じである。したがって、ピクセルブロック２７６の場合、各スキャン位置について１つの列相関２８８だけが計算される。その結果、ピクセルブロック２７６に必要な計算数は、ほぼ８０％削減される。
機能ブロック２９２は、後続のピクセルブロック２９４（図１１Ａ）が、ピクセルＭに関して次の連続する行にある、中央ピクセルＲを基準にして定義されることを示す。ピクセルブロック２９４は、図９Ａのピクセルブロック２６２にあるピクセルの列２６４に似ているが別個のものであるピクセルの列２９６を含む。特に列２９６は、列２６４に含まれないピクセルＡ′〜Ｅ′を含む。このような後続のピクセルブロック２９４の増分定義は、従来のブロック突合せプロセスで使用される定義と実質的に同じである。
機能ブロック２９８は、ピクセルブロック２９４が、機能ブロック２６８および２７６を基準にした前述の方法で、ピクセル配列２６６（図９Ｂ）全体にわたってスキャンされることを示す。図１１Ｂ〜図１１Ｆは、ピクセル配列２６６全体にわたるピクセルブロック２９４のスキャンを示す。
機能ブロック３００は、列相関がそれぞれの列２９６について決定され、記憶されることを示す。したがって、列相関３０２（１）〜３０２（１８）は、図１１Ｂ〜図１１Ｆに示された列２９６のスキャン位置を基準に実行される。
列相関３０２（１）〜３０２（１８）はそれぞれ、ピクセルブロック２６２（図９Ａ）を基準にして実行された列相関に基づく、省略された方法で計算することができる。
たとえば、図１１Ｄの列相関３０２（４）〜３０２（８）は、図９Ｅの２次列相関３０４（４）〜３０４（８）と同じ２次列相関３０４′（４）〜３０４′（８）を含む。したがって、列相関３０２（４）〜３０２（８）は、それぞれ列相関２７０（４）〜２７０（８）から、ピクセル０１Ａ、０２Ｂ、０３Ｃ、０４Ｄ、および０５Ｅについて後者の相関値から減算することにより、２次列相関３０４（４）〜３０４（８）をそれぞれ形成して、決定することができる。列相関３０２（４）〜３０２（８）は、ピクセルの対５６Ａ′、５７Ｂ′、５８Ｃ′、５９Ｄ′、および５０Ｅ′の相関値を、それぞれの２次列相関値３０４（４）〜３０４（８）にそれぞれ加算することによって得られる。
列相関３０２（４）〜３０２（８）をそれぞれ列相関２７０（４）〜２７０（８）から決定するには、ピクセルブロック２９４に含まれていないピクセルブロック２６２のピクセル列Ａ〜Ｅに対応するそれぞれのピクセル相関値を減算し、ピクセルブロック２９４に含まれているがピクセルブロック２６２には含まれていないピクセル列Ａ′〜Ｅ′のピクセル相関値を加算することが必要である。この方法では、列相関３０２（４）〜３０２（８）のそれぞれについて、従来の方法では各列相関を決定するのに必要であった５回の加算の代わりに、１回の減算と１回の加算を使用する。寸法の大きなピクセルブロックが好ましい場合、従来の計算方法を改善したこの方法は非常に有効である。従来のブロック突合せプロセスは、ピクセル配列２６６に関して初期ピクセルブロック２６２の各スキャン位置に対する合計のブロック相関だけを識別する。したがって、すべてのピクセルのすべての相関値を、各スキャン位置でそれぞれ計算しなければならない。これに対して、相関プロセス２６０は、記憶された列相関２７０を使用して必要な計算回数を著しく削減する。相関プロセス２６０によって実現される速度の改善およびプロセッサの資源要件は、システムの列相関記憶に関する要件を相殺してあまりある効果がある。
以上、本発明の特定の機能を例示するために、図９〜図１１を参照しながら相関プロセス２６０について説明してきたことを理解されたい。各図に示されているように本発明は、コンピュータシステムによる実行に特に好適な、循環または周期的機能を含む。これらの循環または周期的機能はピクセルブロックおよびピクセル配列の寸法に依存しており、当業者であればこれらについて周知であり実施可能である。
多次元変換
図１２は、第１と第２の連続する画像フレーム間で多次元変換を生成するステップと、伝送または記憶のためのマッピングを量子化するステップとを含む変換方法３５０を示す、機能ブロック図である。多次元変換は、図３の機能ブロック９６と関連して使用されることが好ましい。変換方法３５０は、図７Ａおよび図１３を参照して説明されており、図７Ｂに似ている後者は、画像特徴２０４がオブジェクト２０４ｂとして描画されている画像フレーム２０２ｂを表示した、ディスプレイ画面５０の略図である。
変換方法３５０は、平行移動、回転、拡大、ねじりのいずれかまたはすべてを含む、複雑な動作を表す多次元アフィン変換機能を提供することが好ましい。変換方法３５０は、１次元のみであって平行移動のみを示す、ＭＰＥＧ−１、ＭＰＥＧ−２、およびＨ．２６Ｘなどの従来のビデオ圧縮方法に著しい改善を加えるものである。この点に関しては下記に詳述するように、変換の次元数が変換の一般化された形式の座標数を表す。本発明により複雑な動作が表示される際の正確さが向上すると、従来の表示よりもエラーが少なくなり、これによって圧縮効率が向上する。
機能ブロック３５２は、オブジェクト２０４ａおよび２０４ｂにおけるピクセルの稠密動作推定が決定されることを示す。稠密動作推定は、多角形突合せプロセス２００によって得られることが好ましい。前述のように稠密動作推定は、画像フレーム２０２ｂのオブジェクト２０４ｂにおける座標（ｘi，ｙi）のピクセルと、対応する画像フレーム２０２ａのオブジェクト２０４ａにおける座標（ｘi′，ｙi′）のピクセルとの間の動作ベクトルを含む。
機能ブロック３５４は、変換ブロック３５６の配列がオブジェクト２０４ｂを取り囲むように定義されることを示す。変換ブロック３５６は、たとえば３２×３２寸法のピクセルを有する整然と規則正しく並んだピクセルの配列であることが好ましい。
機能ブロック３５８は、多次元アフィン変換が各変換ブロック３５６に対して生成されることを示す。アフィン変換は１次であり、次式のように表され、
ｘi′＝ａｘi＋ｂｙi＋ｃ
ｙi′＝ｄｘi＋ｅｙi＋ｆ
動作ベクトルが相対的に高い信頼を置いているすべてのピクセルを基準に決められることが好ましい。これらのアフィン変換は２次元で、ｘiおよびｙjは２つの座標ｘiおよびｙiを基準に定義されている。
動作ベクトルの相対的信頼度とは、それを使って対応するピクセル間の動作ベクトルが他のピクセルに対して一意に決定できる正確さのことである。たとえば、相対的に大規模なピクセル配列で均一なカラー（たとえばブラック）である特定のピクセル間の動作ベクトルは、一般に正確に決定できない。特に、第１の画像フレーム内にあるブラックピクセルの場合、後続画像フレームのピクセル配列内にある多くのピクセルが同じ相関（すなわち、ピクセルブロック間の平均絶対値誤差）を有する。
これに対して、ピクセルが顕著な特徴に対応しているピクセル配列は、一般に連続する画像フレーム内の特定の対応するピクセルに対して相対的に高い相関を有する。
相対的に高い相関は、特定のピクセルに関する最小絶対値誤差の決定として表されることが好ましい。したがって相対的に信頼度の高い動作ベクトルは、こうした一意的に低い誤差値を基準に決定される。たとえば、信頼度の高い動作ベクトルは、動作ベクトルに対する最小絶対値誤差が、しきい値の差異量よりも大きな差異量によってピクセルに関連付けられた、次に大きい誤差値よりも小さいものとして定義することができる。あるいは、信頼度の高い動作ベクトルは、それによって相関が決定される絶対誤差値の２次導関数に関して定義することができる。特定値よりも大きい２次導関数は、特定の対応するピクセル間で相対的に高い相関を示す。
こうした信頼度の高い動作ベクトルを備えたｎ個のピクセルを使って、好ましいアフィン変換式は、画像フレーム２０２ａおよび２０２ｂ内にあるｎ個の対応するピクセルを基準にして解かれる。画像フレームは、画像フレーム２０２ａおよび２０２ｂに、好ましいアフィン変換式の６個の未知の係数ａ、ｂ、ｃ、ｄ、ｅ、およびｆについて解くための、信頼度の高い動作ベクトルを備えた少なくとも３つの対応するピクセルが含まれていなければならない。好ましい寸法では、それぞれの変換ブロック３５６が、かなりの数が相対的に信頼度の高い動作ベクトルを一般に有する２10のピクセルを含む。したがって、より多数のピクセルが係数ａ、ｂ、ｃ、ｄ、ｅ、およびｆについて解くのに使用できるアフィン変換式が過決定される。
その結果、ｎ個の式を次式のような線形代数式で表すことができる。
0004572010.tif 000005
これらの式は、稠密動作ベクトルの概算を行う際に最小２乗エラーを最小に抑える、従来の特異値分解（ＳＶＤ）方法によって解かれることが好ましい。従来のＳＶＤ方法については、たとえばＰｒｅｓｓ他著「Ｎｕｍｅｒｉｃａｌ  Ｒｅｃｉｐｅｓ  ｉｎ  Ｃ」Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ（１９９２年）に記載されている。
前述のように、好ましい２次元アフィン変換式は、連続する画像フレーム２０２ａと２０２ｂとの間にある、変換ブロック３５６の平行移動、回転、拡大、およびねじりを表すことができる。これに対して、前の圧縮標準で使用される従来の動作変換方法は、次式のような形式の単純化された変換式を採用している。
xi′=xi+g
yi′=yi+h
前の単純化された変換式は、２つの係数ｇおよびｈのみで動作を表すが、これは好ましい多次元変換式によって得られる情報量（すなわち係数）の３分の１でしかない。従来の圧縮方法に基づく変換方式３５０によって得られる情報をさらに圧縮するには、変換ブロック３５６の寸法が、圧縮方法ＭＰＥＧ−１およびＭＰＥＧ−２で採用されている対応する１６×１６のピクセルブロックの３倍以上であることが好ましい。変換ブロック３５６の好ましい３２×３２ピクセル寸法は、従来の変換方法の変換ブロックで採用されているピクセル数の４倍を含む。変換ブロック３５６の寸法が大きくなり、アフィン変換係数が変換ブロック３５６の動作を表す正確さが向上すると、変換方法３５０は従来の圧縮方法よりも率の高い圧縮を提供することができるようになる。
本発明により生成されるアフィン係数は、一般に非整数の浮動小数点値であり、その正確さに不利な影響を与えることなく適切に圧縮することは困難であることを理解されよう。したがって、アフィン変換係数を量子化し、それを記憶または伝送するのに必要な帯域幅を減らすことが好ましい。
機能ブロック３６２は、機能ブロック３５８を基準に生成されるアフィン変換係数が、それを記憶または伝送するのに必要な帯域幅を減らすために量子化されることを示す。図１４は、６つの好ましいアフィン変換係数ａ〜ｆがそこから決定できる、３つの選択されたピクセル３６４ａ、３６４ｂ、および３６４ｃを示す変換ブロック３５６を拡大し断片的に表示した図である。
ピクセル３６４ａ〜３６４ｃは、それぞれピクセル座標（ｘ1，ｙ1）、（ｘ2，ｙ2）、および（ｘ3，ｙ3）で表される。機能ブロック３５２の稠密動作推定に基づき、ピクセル３６４ａ〜３６４ｃは先行する画像フレーム２０２ａ内に、それぞれ対応するピクセル（ｘ1′，ｙ1′）、（ｘ2′，ｙ2′）、および（ｘ3′，ｙ3′）を有する。従来と同様に、ピクセル位置（ｘi，ｙi）は整数値で表され、好ましいアフィン変換係数がそれに基づいているアフィン変換式の解である。したがって、選択されたピクセル３６４ａから３６４ｃは、一般的に浮動小数点値である、対応するピクセルを先行する画像フレーム２０２ａから算出するのに使用される。
これらの浮動小数点値の量子化は、対応するピクセル間の差異（ｘi−ｘ′i，ｙi−ｙ′i）を整数形式に変換することによって実行される。アフィン変換係数は、第１にベクトルとピクセル値（ｘi，ｙi）との差異からピクセル値（ｘ′i，ｙ′i）を算出し、次いでピクセル値（ｘ′i，ｙ′i）に基づいて機能ブロック３５８の多次元変換式を解くことで決定される。
図１４に示すように、ピクセル３６４ａ〜３６４ｃは、量子化の感度を変換ブロック３５６内の局所変化にまで最小化するために、変換ブロック３５６を中心に分散されることが好ましい。ピクセル３６４ａは変換ブロック３５６の中心または中心に隣接して配置され、ピクセル３６４ｂおよび３６４ｃは中心上方に配置されることが好ましい。さらに好ましい実施形態では、オブジェクト２０４ｂ内の各変換ブロック３５６について選択されたピクセルが同じ位置にあり、それによって量子化プロセスを効率よく実行することが可能になる。
機能ブロック３６２の量子化方法の別の態様は、異なるレベルの量子化を使用して様々な程度の動作を表すことができることである。その結果、相対的に単純な動作（たとえば平行移動）は、複雑な動作を表すのに必要なピクセル数よりも少ない、選択されたピクセル３６４で表すことができる。前述のアフィン変換式によれば、オブジェクト２０４ｂからのピクセル３６４ａ（ｘ1，ｙ1）およびオブジェクト２０４ａからの対応するピクセル（ｘ1′，ｙ1′）は、連続する画像フレーム間での平行移動を表す、以下に示す次式の形の単純化されたアフィン変換式を解くには十分である。
ｘ1′＝ｙ1＋ｃ
ｙ1′＝ｙ1＋ｆ
具体的に言うと、その中央位置が一般に他の種類の動作に依存しない平行移動を示すので、ピクセル３６４ａが使用される。したがってユーザは、複雑な動作を表すのに必要なデータの３分の１しか必要としない単純化されたアフィン変数式を使用して、平行移動のような単純化された動作を選択的に表すことができる。
同様に、オブジェクト２０４ｂから選択された１対のピクセル（ｘ1，ｙ1）（たとえばピクセル３６４ａ）および（ｘ2，ｙ2）（すなわちピクセル３６４ｂおよび３６４ｃのいずれか）、ならびにオブジェクト２０４ａからの対応するピクセル（ｘ1′，ｙ1′）および（ｘ2′，ｙ2′）は、これは連続する画像フレーム間での平行移動および拡大を含む動作を表すことができる。
ｘi′＝ａｘi＋ｃ
ｙi′＝ｅｙi＋ｆ
次式の形の単純化されたアフィン変換式を解くには十分である。
次式の単純化された形では、
x′=acosθx+sinθy+c
y′=-sinθx+acosθy+f
対応する１対の選択されたピクセルが、平行移動、回転、および等方性拡大を含む動作を表すことができる。この単純化された形式の場合、変数ｘおよびｙの共通係数を使って、対応する２対のピクセルで式を解くことができる。
したがってユーザは、平行移動、回転、および拡大を含む中程度の複雑な動作を、部分的に単純化されたアフィン変換式で選択的に表すことができる。このような式は、複雑な動作を表すのに必要なデータの３分の２を必要とする。オブジェクト２０４ｂから選択された第３のピクセル（ｘ3，ｙ3）、オブジェクト２０４ａからの対応するピクセル（ｘ3′，ｙ3′）、および完全に好ましいアフィン変換式を加えることで、ユーザは、連続する画像フレーム間のねじりも表すことができる。
変換方法３５０（図１２）の好ましい実施形態は、たとえば３２×３２寸法のピクセルを有する均一な変換ブロック３５６を使用するとして記載される。機能ブロック３５８に基づいて記載された好ましい多次元アフィン変換は、変換ブロック３５６に基づいて決定される。変換ブロック３５６の寸法が、この方法によって提供される圧縮比率に直接影響することを理解されよう。
画像フレーム間でのオブジェクトの変換を表すには、寸法の小さい変換ブロック３５６の数よりも、相対的に寸法は大きく数の少ない変換ブロック３５６が必要である。均一に大きい変換ブロック３５６を使用すると、それに対応して各変換ブロックに大きなエラーが生じることになる。したがって均一な大きさの変換ブロック３５６は、競合するパフォーマンスの制約との釣り合いをとるために、一般に中程度の寸法である。
変換ブロックの最適化
図１５は、最小エラーしきい値を提供する変換ブロックを自動的に選択する変換ブロック最適化方法３７０を示す、機能ブロック図である。最適化方法３７０は図１６を参照して記載されており、この図はオブジェクト２０４ｂを有する画像フレーム２０２ｂの一部分を示すディスプレイ画面５０の略図である。
機能ブロック３７２は、初期変換ブロック３７４がオブジェクト２０４ｂを基準に定義されることを示す。初期変換ブロック３７４は、ユーザが選択可能な最大寸法であり、たとえば６４×６４ピクセルであることが好ましい。初期変換ブロック３７４は、現在の変換ブロックと指定される。
機能ブロック３７６は、現在の信号対雑音比（ＣＳＮＲ）が現在の変換ブロックを基準に計算されることを示す。信号対雑音比は、現在の変換ブロック内のピクセルのカラー構成要素値の分散（ｖａｒｉａｎｃｅ）（すなわち信号）と、推定もられたエラー９８（図３）に関連付けられたピクセルのカラー構成要素値の分散との比として計算されることが好ましい。
機能ブロック３７８は、現在の変換ブロック（たとえば変換ブロック３７４）が、たとえば４つの等しいサブブロック３８０ａ〜３８０ｄに２次分割され、この各サブブロック３８０ａ〜３８０ｄについてアフィン変換が決定され、このアフィン変換を基準にして将来の信号対雑音比が決定されることを示す。この将来の信号対雑音比は、実質的に機能ブロック３７６を参照して説明された現在の信号対雑音比と同じ方法で計算される。
問合せブロック３８２は、将来の信号対雑音比が現在の信号対雑音比よりもユーザが選択したしきい値量以上に大きいかどうかについての問合せを示す。この問合せは、現在の変換ブロック（たとえば変換ブロック３７４）をさらに２次分割すると、少なくともしきい値だけアフィン変換の正確さが向上するという決定を表す。将来の信号対雑音比が現在の信号対雑音比よりもしきい値量以上に大きい場合は、必ず問合せブロック３８２から機能ブロック３８４に進み、そうでない場合は機能ブロック３８８に進む。
機能ブロック３８４は、サブブロック３８０ａ〜３８０ｄが連続して現在の変換ブロックと指定され、それぞれがさらに２次分割されるかどうかを分析されることを示す。図によれば、サブブロック３８０ａは現在の変換と指定され、機能ブロック３７６によって処理されて、さらにサブブロック３８６ａ〜３８６ｄに２次分割される。機能ブロック３８８は、次の連続する変換ブロック３７４′が識別され、初期または現在の変換ブロックと指定されることを示す。
事前圧縮（ｐｒｅｃｏｍｐｒｅｓｓｉｏｎ）外挿法
図１７Ａおよび図１７Ｂは、任意構成の画像特徴を、あらかじめ定義された構成に外挿して、符号化プロセス６４の機能ブロック１１２（どちらも図３）による圧縮を容易にするための、事前圧縮外挿法４００を示す機能ブロック図である。外挿方法４００を使用すると、機能ブロック１１２の圧縮を、前述のＤＣＴまたはラチスウェーブレット圧縮などの従来の方法で実行することができる。
ラチスウェーブレット圧縮または離散コサイン変換（ＤＣＴ）のような従来の静止画像圧縮方法は、ピクセルの矩形配列上で実行される。ただし前述のように、本発明の方法は任意構成の画像特徴またはオブジェクトに適用可能である。こうしたオブジェクトまたは画像特徴を矩形のピクセル配列構成に外挿すると、ラチスウェーブレット圧縮またはＤＣＴのような従来の静止画像圧縮方法を使用することができる。外挿方法４００について、単純なオブジェクト４０２が外挿方法４００の様々な態様を示すために描画される、ディスプレイ画面５０を表した図１８Ａ〜図１８Ｄを参照しながら下記に説明する。
機能ブロック４０４は、外挿ブロック境界４０６がオブジェクト４０２の周囲に定義されることを示す。外挿ブロック境界４０６は矩形であることが好ましい。図１８Ａによれば、オブジェクト４０２の周囲に形成される外挿ブロック境界４０６は、たとえば、オブジェクトセグメント化方法１４０（図４）によるオブジェクト４０２の周囲４０８の識別に基づいている。外挿ブロック境界４０６は、例示のためにオブジェクト４０２全体を取り囲むように表示されている。外挿ブロック境界４０６は、オブジェクト４０２の一部分だけを取り囲んでいてもよいことを理解されよう。オブジェクトセグメント化方法１４０を参照しながら説明したように、オブジェクト４０２に含まれるピクセルは、オブジェクト４０２に含まれないピクセルとは異なるカラー構成要素値を有する。
機能ブロック４１０は、外挿ブロック境界４０６によって囲まれ、オブジェクト４０２に含まれていないすべてのピクセル４１２には、たとえば各カラー構成要素に対してゼロ値を割り当てるように、あらかじめ定義された値が割り当てられることを示す。
機能ブロック４１４は、外挿ブロック境界４０６内にあるピクセルの水平線がスキャンされて、ゼロおよび非ゼロの両方のカラー構成要素値を有する水平ピクセルセグメントで水平線を識別することを示す。
機能ブロック４１６は、ゼロのカラー構成要素値を有する水平ピクセルセグメントの両端が、オブジェクト４０２の周囲４０８によって境界を画されているかどうかについての問合せを表す。図１８Ｂを参照すると、領域４１８は、両端が周囲４０８によって境界を画されているゼロのカラー構成要素値を有する水平ピクセルセグメントを表す。領域４２０は、ゼロのカラー構成要素値を有し、一方の端だけが周囲４０８によって境界を画されている水平ピクセルセグメントを表す。機能ブロック４１６は、その中のピクセルセグメントがオブジェクト４０２の周囲４０８によって両端が境界を画されているゼロのカラー構成要素値を有する領域４１８の場合は、機能ブロック４２６に進み、それ以外の場合は機能ブロック４２２に進む。
機能ブロック４２２は、領域４２０の各水平ピクセルセグメント内のピクセルに、対応する水平線およびオブジェクト４０２の周囲４０８内にあるピクセル４２４（例示的にのみ表示）のカラー構成要素値が割り当てられることを示す。あるいは、領域４２０内にあるピクセルに割り当てられたカラー構成要素値は、機能上はピクセル４２４のカラー構成要素値に関係する。
機能ブロック４２６は、領域４１８内の各水平ピクセルセグメント内のピクセルに、対応する水平線内で周囲４０８上にあるピクセル４２８ａおよび４２８ｂのカラー構成要素値の平均に対応し、好ましくはこれに等しいカラー構成要素値が割り当てられることを示す。
機能ブロック４３０は、外挿ブロック境界４０６内のピクセルの垂直線がスキャンされて、ゼロおよび非ゼロの両方のカラー構成要素値を有する垂直ピクセルセグメントで垂直線を識別することを示す。
機能ブロック４３２は、ゼロのカラー構成要素値を有する垂直線内の垂直ピクセルセグメントの両端が、オブジェクト４０２の周囲４０８によって境界を画されているかどうかについての問合せを表す。図１８Ｃを参照すると、領域４３４は、両端が周囲４０８によって境界を画されているゼロのカラー構成要素値を有する垂直ピクセルセグメントを表す。領域４３６は、ゼロのカラー構成要素値を有し、一方の端だけが周囲４０８によって境界を画されている垂直ピクセルセグメントを表す。機能ブロック４３２は、その中の垂直ピクセルセグメントがオブジェクト４０２の周囲４０８によって両端が境界を画されているゼロのカラー構成要素値を有する領域４３４の場合は、機能ブロック４４４に進み、それ以外の場合は機能ブロック４３８に進む。
機能ブロック４３８は、領域４３６の各垂直ピクセルセグメント内のピクセルに、垂直線およびオブジェクト４０２の周囲４０８内にあるピクセル４４２（例示的にのみ表示）のカラー構成要素値が割り当てられることを示す。あるいは、領域４３６内にあるピクセルに割り当てられたカラー構成要素値は、機能上はピクセル４４２のカラー構成要素値に関係する。
機能ブロック４４４は、領域４３４内の各垂直ピクセルセグメント内のピクセルに、水平線内で周囲４０８上にあるピクセル４４６ａおよび４４６ｂのカラー構成要素値の平均に対応し、好ましくはこれに等しいカラー構成要素値が割り当てられることを示す。
機能ブロック４４８は、この方法によりカラー構成要素値が割り当てられた水平および垂直両方のピクセルセグメント内にあるピクセルに、その水平および垂直なピクセルセグメントにより別な方法でピクセルに割り当てられたカラー構成要素値に関係し、好ましくはその平均である複合カラー構成要素値が割り当てられることを示す。
こうした複合カラー構成要素値が割り当てられるピクセルの例は、領域４１８および４３４内のピクセルである。
機能ブロック４５０は、外挿ブロック境界４０６によって境界を画され、水平線または垂直線に沿ってオブジェクト４０２の周囲４０８と交差しないピクセルの領域４５２に、隣接するピクセルに割り当てられたカラー構成要素値に関係し、好ましくはその平均に等しい複合カラー構成要素値が割り当てられることを示す。図１８Ｄを参照すると、領域４５２内の各ピクセル４５４には、それぞれ水平線および垂直線に沿ってピクセル４５４と位置合わせされ、この方法で以前割り当てられた非ゼロのカラー構成要素値を有する、ピクセル４５６ａおよび４５６ｂのカラー構成要素値の平均であることが好ましいカラー構成要素値が割り当てられる。
オブジェクト外挿プロセス４００の利点は、オブジェクト４０２に含まれていないピクセルに滑らかに変化するカラー構成要素値を割り当てるので、従来の静止画像圧縮方法の圧縮能力および正確さを最適化するという点である。これに対して、Ｃｈａｎｇ他著の「Ｔｒａｎｓｆｏｒｍ  Ｃｏｄｉｎｇ  ｏｆ  Ａｒｂｉｔｒａｒｉｌｙ−Ｓｈａｐｅｄ  Ｉｍａｇｅ  Ｓｅｇｍｅｎｔｓ」ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａのｐｐ．８３〜８８、１９９３年６月に記載されている、従来技術のゼロ埋込みまたは鏡像方法は、機能ブロック４１０で適用されるようなゼロカラー構成要素値を有するピクセルで満たされた、外挿されたオブジェクトに圧縮を適用する。次いでオブジェクトとゼロ埋込領域との間に発生する激しい画像変化は、圧縮が困難な、または圧縮時に画像アーティファクト（ａｒｔｉｆａｃｔ）を招くような高周波数変化を生じさせる。オブジェクト外挿方法４００は、こうした欠点を克服するものである。
代替符号化方法
図１９Ａは、エッジなどの画像特徴の非線形態様を維持しながら高圧縮も提供する固有フィルタを備えた、ラプラスピラミッド符号器を使用する符号器方法５００の機能ブロック図である。従来のラプラスピラミッド符号器については、たとえばＢｕｒｔおよびＡｄｄｌｅｓｏｎ共著「Ｌａｐｌａｃｉａｎ  Ｐｙｒａｍｉｄ  ａｓ  ａ  Ｃｏｍｐａｃｔ  Ｉｍａｇｅ  Ｃｏｄｅ」ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｍ．，Ｖｏｌ．３１，Ｎｏ．４、ｐｐ．５３２〜５４０、１９８３年４月に記載されている。符号器方法５００は、図３に示されている、あるいはウェーブレット符号化でＤＣＴが提案または使用される以外の場合は必ず、ビデオ圧縮符号器プロセス６４の機能ブロック１１２を参照して記載されている符号化を提供することができる。例を挙げると、符号器方法５００は、推定エラー１１０（図３）の符号化を参照しながら説明される。
第１のデシメーションフィルタ（ｄｅｃｉｍａｔｉｏｎ  ｆｉｌｔｅｒ）５０２は、推定エラー１１０（図３）に対応するピクセル情報を受け取り、フィルタ基準に従ってピクセルをフィルタにかける。従来のラプラスピラミッド方法では、デシメーションフィルタはガウス重みづけ関数のような低域フィルタである。ただし、符号器方法５００によれば、デシメーションフィルタ５０２は中位（ｍｅｄｉａｎ）フィルタ、具体的には３×３の分離不能中位フィルタを使用することが好ましい。
例を挙げると、図２０Ａはピクセル５０４の任意の１組または配列に対する１つのカラー構成要素（たとえばレッド）に関するカラー構成要素値を示す略図である。レッドのカラー構成要素値を特別に例示しているが、この図はピクセル５０４のグリーンおよびブルーのカラー構成要素値にも同様に適用される。
デシメーションフィルタ５０２の好ましい実施形態を参照すると、ピクセル５０４の中に３×３寸法のピクセルを有するフィルタブロック５０６が定義される。各ピクセルブロック５０６について、中位ピクセル強度値が識別または選択される。たとえば、ピクセルブロック５０６ａ〜５０６ｃを参照すると、デシメーションフィルタ５０２は、図２０Ｂの最初の３つのピクセルとしてリストされているそれぞれの値８、９、および１０を提供する。
ただし、本発明によれば、デシメーションフィルタ５０２は他の中位フィルタを使用できることを理解されよう。したがって、関連付けられたカラー構成要素値｛ａ0，ａ1，．．．，ａn-1｝を有するピクセルの各グループに対して、中位フィルタは中位値ａMを選択する。
第１の２×２のダウンサンプリングフィルタ５１４は、追加の圧縮を提供するために、垂直方向および水平方向で代替ピクセル５１２をサンプリングする。図２０Ｃは、その結果圧縮された１組のピクセル５１５を表す。
２×２のアップサンプリングフィルタ５１６は、ダウンサンプリングフィルタ５１４が省いたゼロ値のピクセルをピクセル５１２の各位置に挿入し、補間フィルタ５１８はそのゼロ値ピクセルに、反対に隣接するピクセルの平均のピクセル値、またはゼロ値ピクセルが反対の１対の非ゼロ値ピクセル間にない場合は前に割り当てられた値を割り当てる。例を挙げれば、図２０Ｄはその結果得られる１組または配列のピクセル５２０を表す。
ゼロ順位画像構成要素Ｉ0を形成するために、１組のピクセル５０４のカラー構成要素値と、１組のピクセル５２０の対応するカラー構成要素値との間の差異５２２がとられる。
第２のデシメーションフィルタ５２６は、第１の２×２のダウンサンプリングフィルタ５１４によって生成される、ピクセル５１５の圧縮された組に対応するカラー構成要素値を受け取る。デシメーションフィルタ５２６は、デシメーションフィルタ５０２（たとえば３×３の分離不能中位フィルタ）と同じであることが好ましい。したがって、デシメーションフィルタ５２６は、デシメーションフィルタ５０２と同様に機能し、その結果圧縮されたピクセルのセットまたは配列（図示せず）を第２の２×２のダウンサンプリングフィルタ５２８に送達する。
ダウンサンプリングフィルタ５２８はダウンサンプリングフィルタ５１４と同様に機能し、それぞれアップサンプリングフィルタ５１６および補間フィルタ５１８と同様に機能する、２×２のアップサンプリングフィルタ５３０および補間フィルタ５３１にも送達される第２順位の画像構成要素Ｌ2を形成する。１次の画像構成要素Ｉ1を形成するために、ピクセル５１５の組のカラー構成要素値と、補間フィルタ５３１によって提供されるその結果得られるカラー構成要素値との間の差異５３２がとられる。
画像構成要素Ｉ0、Ｉ1、およびＬ2は、ｎ×ｎ配列のピクセル５０４のカラー構成要素値を表すそれぞれの組のカラー構成要素値である。
0004572010.tif 000006
画像構成要素Ｉ0は、ピクセル５０４のオリジナルの組によって表される画像の高周波数構成要素（たとえばエッジ）を維持する。画像構成要素Ｉ1およびＬ2は、オリジナル画像の低周波数態様を表す。画像構成要素Ｉ0、Ｉ1、およびＬ2は、オリジナル画像の相対的圧縮を提供する。画像構成要素Ｉ0およびＩ1は、隣接するピクセル値間の相対的に高い相関により高圧縮が可能な形式で、高周波数特徴（たとえばエッジ）を維持する。画像構成要素Ｌ2は主として低周波数画像特徴を含むが、相対的にサイズの小さな組であるために、容易には圧縮できない。
図１９Ｂは、符号器方法５００によって生成された画像構成要素Ｉ0、Ｉ1、およびＬ2を復号化するかまたは逆に符号化する、復号器方法５３６を示す機能ブロック図である。復号器方法５３６は、画像構成要素Ｌ2を受け取り、ピクセルの隣接する対の間にゼロ値のピクセルを挿入する、第１の２×２のアップサンプリングフィルタ５３８を含む。補間フィルタ５３９は、そのゼロ値のピクセルに、好ましくは隣接するピクセルの値の平均であるピクセル値、またはゼロ値のピクセルが非ゼロ値のピクセルの反対の対の間にない場合は前に割り当てられた値を割り当てる。第１の２×２のアップサンプリングフィルタ５３８は、実質的に図１９Ａのアップサンプリングフィルタ５１６および５３０と同じ方法で動作し、補間フィルタ５３９は、実質的に補間フィルタ５１８および５３１と同じ方法で動作する。
合計５４０は、画像構成要素Ｉ1と、第１の２×２のアップサンプリングフィルタ５３８と補間フィルタ５３９によって生成されたピクセルの圧縮解除された組に対応するカラー構成要素値との間で決定される。第２の２×２のアップサンプリングフィルタ５４２は、ゼロ値のピクセルを、合計５４０によって生成されたピクセルの各隣接する対の間に挿入する。補間フィルタ５４３は、そのゼロ値のピクセルに、隣接するピクセルの値の平均を含むピクセル値を、またはゼロ値のピクセルが非ゼロ値ピクセルの反対の対の間にない場合は前に割り当てられた値を割り当てる。アップサンプリングフィルタ５４２および補間フィルタ５４３は、それぞれアップサンプリングフィルタ５３８および補間フィルタ５３９と実質的に同じである。
合計５４４は、画像構成要素Ｉ0と、第２の２×２のアップサンプリングフィルタ５４２および補間フィルタ５４３によって生成されたピクセルの圧縮解除された組に対応するカラー構成要素値とを合計する。合計５４４は、符号器プロセス５００に送達される推定エラー１１０に対応する、圧縮解除された推定エラー１１０を提供する。
動作ベクトルの変換符号化
ＭＰＥＧ−１またはＭＰＥＧ−２のような従来のビデオ圧縮符号器プロセスは、疎動作ベクトルフィールドのみを使用して、通常のサイズおよび構成でかなり大きなピクセル配列の動作を表す。動作ベクトルを１つだけ使用して、たとえば１６×１６寸法のピクセルを有するピクセル配列の動作を表す場合、動作ベクトルフィールドは疎である。この疎の動作ベクトルフィールドならびに、たとえば離散コサイン変換（ＤＣＴ）符号化による基礎をなす画像またはピクセルの変換符号化とを合わせて、従来のビデオ圧縮符号化を提供する。
これに対してビデオ圧縮符号化プロセス６４（図３）は、オブジェクトのすべての、または事実上すべてのピクセルに対して動作ベクトルが決定される、稠密動作ベクトルフィールドを使用する。このような稠密動作ベクトルフィールドは、対応するピクセル間の動作が表される正確さを著しく向上させる。正確さが向上すると、従来の疎動作ベクトルフィールド表示に関連付けられたエラーが著しく減少するが、稠密動作ベクトルフィールドに含まれた追加情報は、ビデオシーケンスを表示する情報量の増加を表す。本発明によれば、稠密動作ベクトルフィールドは、本発明によって提供される圧縮率を上げるために、それ自体が圧縮または符号化される。
図２１は、動作ベクトルフィールドおよび、好ましくは図３の稠密動作変換９６により生成されるような稠密動作ベクトルフィールドを符号化または圧縮するための、動作ベクトル符号化プロセス５６０を示す機能ブロック図である。選択されたオブジェクトからのこうした稠密動作ベクトルフィールドは、オブジェクトに対応する基礎をなすピクセルよりも一般にすぐれた連続性または「滑らかさ」を有することを理解されよう。その結果、稠密動作ベクトルフィールドを圧縮または符号化することで、基礎をなすピクセルを圧縮または符号化するよりも優れた圧縮率が達成される。
機能ブロック５６２は、たとえば図３を参照して説明された機能ブロック９６のプロセスにより、稠密動作ベクトルフィールドがオブジェクトまたはオブジェクトの一部について取得されることを示す。したがって、稠密動作ベクトルフィールドは、任意の構成またはサイズのオブジェクトまたは他の画像部分に対応する。
機能ブロック５６４は、稠密動作ベクトルフィールドの構成が、符号化または圧縮を容易にするために、規則正しい、好ましくは矩形の構成に外挿されることを示す。稠密動作ベクトルフィールド構成は、図１７Ａおよび図１７Ｂを参照して説明した事前圧縮外挿方法４００によって、規則正しい構成に外挿されることが好ましい。鏡像方法などの従来の外挿方法が代わりに使用できることを理解されよう。
機能ブロック５６６は、外挿された規則正しい構成を備える稠密動作ベクトルフィールドが、たとえば離散コサイン変換（ＤＣＴ）またはラチスウェーブレット圧縮など（前者の方が好ましい）の従来の符号化変換によって符号化または圧縮されることを示す。
機能ブロック５６８は、符号化された稠密動作ベクトルフィールドが、符号化された稠密動作ベクトルフィールド５７０を形成するために、エントロピー符号化などの従来の損失のない静止画像圧縮方法によって、さらに圧縮または符号化されることを示す。こうした静止画像圧縮方法は、図３の機能ブロック１１４を参照して説明される。
前のビデオフレームからの量子化オブジェクトの圧縮
図３によれば、ビデオ圧縮符号器プロセス６４は、次の連続するフレームＮ内の対応するオブジェクトを符号化するために、前のフレームＮ−１を基準にして決定される量子化された前のオブジェクト９８を使用する。したがって、符号器プロセス６４は、量子化された前のオブジェクト９８がアクセス可能メモリバッファ内に記憶されている必要がある。従来のビデオディスプレイ解像度の場合、単一のビデオフレームについて量子化された前のオブジェクト９８を記憶するためには、こうしたメモリバッファに少なくとも１メガバイトの容量が必要である。表示形式の解像度が高くなるほど、それに対応して大きなメモリバッファが必要になる。
図２２は、量子化オブジェクトメモリバッファの必要容量を減らすために、量子化された前のオブジェクト９８を圧縮し選択的に圧縮解除する、量子化オブジェクトの符号器・復号器（コーデック）プロセス６００を示す機能ブロック図である。
機能ブロック６０２は、画像フレーム内の各量子化オブジェクト９８が、離散コサイン変換（ＤＣＴ）符号化またはラチスサブバンド（ウェーブレット）圧縮などの損失のある符号化または圧縮方法で、ブロックごとに符号化されることを示す。
機能ブロック６０４は、符号化または圧縮された量子化オブジェクトが、メモリバッファ（表示せず）内に記憶されることを示す。
機能ブロック６０６は、次の連続するビデオフレーム内の対応するオブジェクトを処理することを見越して、符号化された量子化オブジェクトがメモリバッファから取り出されることを示す。
機能ブロック６０８は、符号化された量子化オブジェクトが、機能ブロック６０２に対して使用される符号化プロセスに従って、たとえばＤＣＴまたはウェーブレット復号によって逆に符号化されることを示す。
コーデックプロセス６００を使用すると、対応するメモリバッファの容量が約８０％まで削減できる。さらに、コーデックプロセス６００は、ビデオ圧縮符号器プロセス６４に対応する復号器プロセスにも同様に適用可能であることを理解されよう。
ビデオ圧縮復号器プロセスの概要
図３のビデオ圧縮符号器プロセス６４によって、複数画像フレームのビデオシーケンスに対応するビデオ信号が符号化または圧縮されて表示される。この圧縮された表示には、オブジェクトマスク６６、フィーチャポイント６８、アフィン変換係数１０４、ならびに符号器プロセス６４からの圧縮されたエラーデータ１１６および符号器プロセス１３０からの圧縮されたマスタオブジェクト１３６が含まれる。これらの圧縮表示によってビデオ情報の記憶または伝送が容易になり、ＭＰＥＧ−２などの従来のビデオ圧縮方法が達成できる圧縮率よりも最高３００％まで高い圧縮率が達成可能である。
ただし、このような圧縮されたビデオ情報をデータ記憶域から取り出す、またはビデオ情報の伝送を受け取るには、オリジナルのビデオ信号をビデオディスプレイ装置５２（図２Ａおよび図２Ｂ）などのディスプレイ装置によって描画できるように再構成するために、情報を復号または圧縮解除する必要があることが理解されよう。ＭＰＥＧ−１、ＭＰＥＧ−２、およびＨ．２６Ｘのような従来の符号化プロセスの場合と同様に、ビデオ情報の圧縮解除または復号は、それによってオリジナルビデオ信号が符号化または圧縮されるプロセスのほぼ逆である。
図２３Ａは、図３のビデオ圧縮符号器プロセス６４によって生成されるビデオ情報を圧縮解除するための、ビデオ圧縮復号器プロセス７００を示す機能ブロック図である。符号器プロセス６４の説明と一貫させるために、復号器プロセス７００は図２Ａおよび図２Ｂを参照して説明される。復号器プロセス７００は、オブジェクトマスク６６、フィーチャポイント６８、圧縮されたマスタオブジェクト１３６、アフィン変換係数１０４、および圧縮されたエラーデータ１１６を含む符号化されたビデオ情報を、メモリから取り出すか、または伝送として受け取る。
復号器プロセス７００は、符号器プロセス６４（図３）と逆の操作を実行する。したがって、復号化操作を有する符号器プロセス６４の前述の好ましい操作は、それぞれ同様に反対になる。
機能ブロック７０２は、マスク６６、フィーチャポイント６８、変換係数１０４、および圧縮されたエラーデータ１１６が、復号器プロセス７００によって処理するために、メモリから取り出されるかまたは伝送として受け取られることを示す。
図２３Ｂは、圧縮されたマスタオブジェクト１３６を復号または圧縮解除するための、マスタオブジェクト復号器プロセス７０４を示す機能ブロック図である。機能ブロック７０６は、圧縮されたマスタオブジェクトデータ１３６が、図３Ｂの機能ブロック１３４にある従来の損失のないエントロピー符号化方法の逆の方法でエントロピー復号化されることを示す。機能ブロック７０８は、機能ブロック７０６からエントロピー復号化されたマスタオブジェクトが、図３Ｂの機能ブロック１３２で使用される従来の損失のあるウェーブレット符号化プロセスの逆の方法によって復号化されることを示す。
機能ブロック７１２は、稠密動作変換、好ましくは多次元アフィン変換が、アフィン係数１０４から生成されることを示す。アフィン係数１０４が変換方法３５０（図１２）に従って量子化され、機能ブロック３６２（図１２）を参照して説明された操作の逆を実行することによって、量子化されたアフィン係数からアフィン変換が生成されることが好ましい。
機能ブロック７１４は、タイミング遅延７１８を介して提供される、前のフレームＮ−１（たとえば画像フレーム５４ａにある直方体オブジェクト５６ａ）内のオブジェクト７１６の量子化された形式が、現在のフレームＮ（たとえば画像フレーム５４ｂにある直方体オブジェクト５６ｂ）内のオブジェクト７２０の予測された形式を提供するために、稠密動作変換によって変換されることを示す。
機能ブロック７２２は、画像フレームＮの場合、予測された現在のオブジェクト７２０が、圧縮されたエラーデータ１１６から生成された量子化エラー７２４に加えられることを示す。具体的に言えば、機能ブロック７２６は、圧縮されたエラーデータ１１６が圧縮プロセス１１４（図３Ａ）の逆のプロセスによって復号されることを示す。好ましい実施の形態では、機能ブロック１１４および７２６は、エントロピー復号化のような従来の損失のない静止画像圧縮方法に基づいている。
機能ブロック７２８は、機能ブロック７２６からエントロピー復号化されたエラーデータが、機能ブロック１１２（図３Ａ）で使用される方法に対応する、従来の損失のある静止画像圧縮方法によって、さらに圧縮解除または復号化されることを示す。好ましい実施形態では、機能ブロック７２８の圧縮解除または復号化は、ラチスサブバンド（ウェーブレット）プロセスまたは離散コサイン変換（ＤＣＴ）プロセスによって実行される。
機能ブロック７２２は、後続フレームでオブジェクトを再構成するために、機能ブロック７１８に送達される再構成または圧縮解除されたオブジェクト７３２を表す、量子化されたオブジェクト７３０を、予測されるオブジェクト７２０と量子化エラー７２４との和としてフレームＮに提供する。
機能ブロック７３４は、量子化オブジェクト７３２が、圧縮解除されたビデオ信号を形成するために現在の画像フレームＮの他のオブジェクトと組み合わされることを示す。
単純化された連鎖符号化
マスク、オブジェクト、スプライト、および他のグラフィック特徴は、一般にその輪郭で表される。図５Ａに示され、これを参照して説明されるように、たとえば直方体オブジェクト５６ａは、オブジェクト周囲または輪郭１４２で境界を画されている。従来のプロセスあるいは輪郭の符号化または圧縮は、連鎖符号化と呼ばれる。
図２４Ａは、従来のレクティリニア（ｒｅｃｔａ−ｌｉｎｅａｒ）ピクセル配列が定義されている輪郭からの、従来の８点連鎖コード８００を示す。現在のピクセル位置Ｘを基準にして、輪郭内の次の連続するピクセル位置は、８０２ａ〜８０２ｈのいずれか１つの方向に広がる。次の連続するピクセルの連鎖コード値は、特定方向８０２に対応する数値である。例が示すように、右の水平方向８０２ａは連鎖コード値０に相当し、下の垂直方向８０２ｇは連鎖コード値６に相当する。どのような連続する輪郭も、８点連鎖コード８００から記述できる。
図２４Ｂによれば、ＸおよびＡ〜Ｇが指定されているピクセル８０６で表される輪郭８０４は、従来の方法で連鎖コードシーケンス｛００７６４４３２｝によって符号化できる。具体的に言えば、ピクセルＸを起点として、ピクセルＡおよびＢはそれぞれピクセルＸおよびＡを基準にして方向０に配置される。ピクセルＣはピクセルＢを基準にして方向７に配置される。残りのピクセルＤ〜Ｇも同様に、前述の連鎖コード値に対応する方向に配置される。２進法で表すと、従来の連鎖コード値はそれぞれ３桁のビットで表される。
図２５Ａは、従来の連鎖コードプロセスの少なくとも約２倍の輪郭圧縮率を提供できる、連鎖コードプロセス８１０を示す機能ブロック図である。連鎖コードプロセス８１０は、連鎖コードの数を制限し、ピクセルの隣接する対の位置合わせを基準にしてこれらを定義することによって、このように向上した圧縮率を達成する。実験に基づいて、連鎖コードプロセス８１０の制限された連鎖コードは、オブジェクトまたはマスクの輪郭のピクセル位置合わせの９９．８％より多くを直接表すことがわかっている。以下に詳細に記載するように、連鎖コード修正の特別な例は、残りのピクセル位置合わせの０．２％未満に対処している。
機能ブロック８１６は、マスク、オブジェクト、またはスプライトについて輪郭が得られることを示す。たとえば輪郭は、図４および図５を参照して記載されたオブジェクトセグメント化プロセス１４０によって取得することができる。
機能ブロック８１８は、輪郭内の初期ピクセルが識別されることを示す。初期ピクセルは、たとえば最小Ｘ軸およびＹ軸座標位置を有するピクセルとして、一般的な方法で識別することができる。
機能ブロック８２０は、初期ピクセルと輪郭内で次に隣接するピクセルとの関係を表すように、あらかじめ決められた連鎖コードが割り当てられることを示す。あらかじめ決定された連鎖コードが前方向に対応することが好ましい。
図２５Ｂは、３点連鎖コード８２２の略図である。連鎖コード８２２は前方向８２６ａ、左方向８２６ｂ、および右方向８２６ｃにそれぞれ対応する３つの連鎖コード８２４ａ、８２４ｂ、および８２４ｃを含む。方向８２６ａ〜８２６ｃは、現在のピクセル８３０と、連鎖コード内の先行ピクセルを示す隣接するピクセル８３２との間の先行する位置合わせ方向８２８を基準にして定義される。
前述の位置合わせ方向８２８は、図２４Ａに示されたどの方向８０２でもよいが、例示のために特定の配向（すなわち右、水平方向）で表示している。したがって、方向８２８と同様に方向８２６ａが定義される。方向８２６ｂおよび８２６ｃは、方向８２８から１ピクセル分だけ左方向および右方向に変位している。
５０％よりわずかに多くの連鎖コード８２４が前方向８２６ａに対応し、２５％よりわずかに少ない連鎖コード８２４が方向８２６ｂおよび８２６ｃのそれぞれに対応することが、実験的に判定されている。
機能ブロック８３６は、輪郭内の次の隣接するピクセルが方向８２６のいずれか１つと同じであるかどうかについての問合せを表す。輪郭内の次の隣接するピクセルが方向８２６の１つと同じである場合は必ず、機能ブロック８３６から機能ブロック８３８に進み、そうでなければ機能ブロック８４０へ進む。
機能ブロック８３８は、次の隣接するピクセルに、それに沿ってピクセルの隣接する前の対が位置合わせされる方向８２８を基準にして、その方向８２６に対応する連鎖コード８２４が割り当てられることを示す。
機能ブロック８４０は、実際の非共形ピクセルシーケンスに代わって、方向８２６のいずれか１つと同じピクセルシーケンスに置き換えられることを示す。実験に基づき、一般にこうした置換が発生する率は輪郭内のピクセルシーケンスの０．２％よりも少なく、６つの特例修正の１つで対処できることが判定されている。
図２５Ｃは、非共形ピクセルシーケンスを方向８２６と同じピクセルシーケンスに変換するための、６つの特例修正８４２を示す略図である。ピクセルシーケンス８４４は、各修正８４２の範囲内でピクセルシーケンス８４６に変換される。隣接するそれぞれのピクセルＸ1、Ｘ2、Ａ、Ｂの各ピクセルシーケンス８４４で、ピクセルＡの位置合わせはピクセルＸ1およびＸ2の位置合わせを基準にしているので、ピクセルＡとＢの間の方向は、方向８２６のうちの１つと一致しない。
ピクセルシーケンス８４４ａの場合、初期ピクセル位置合わせ８５０ａおよび８５２ａは非共形で直角の方向変化を表す。したがってピクセルシーケンス８４６ａの場合、ピクセルシーケンス８４４ａのピクセルＡは省略され、その結果ピクセル方向８２６ａと同じピクセル方向８５４ａとなる。ピクセルシーケンス修正８４２ｂ〜８４２ｆも同様に、非共形ピクセルシーケンス８４４ｂ〜８４４ｆを共形シーケンス８４６ｂ〜８４６ｆにそれぞれ変換する。
ピクセルシーケンス修正８４２は、隣接する前のピクセルＸ１およびＸ２の位置合わせを基準にして９０°以上変化するピクセル方向位置合わせを生じさせるピクセルを省略する。その効果の１つは、３つのピクセルに対して直角を表す輪郭の曲率の最小半径が増えることである。したがってピクセル修正８４２では、非常に細かい輪郭の細部がわずかに失われる。ただし本発明によれば、こうした細部の損失はほとんどの表示条件下で許容可能であることが判定されている。
機能ブロック８６０は、連鎖コードが割り当てられる別のピクセルが輪郭内にあるかどうかについての問合せを表す。連鎖コードが割り当てられる別のピクセルが輪郭内にある場合は機能ブロックは必ず機能ブロック８３６に戻り、そうでなければ機能ブロック８６２に進む。
機能ブロック８６２は、機能ブロック８４０のプロセスによって導入または発生した非共形ピクセル位置合わせ方向が削除されることを示す。好ましい実施形態では、非共形方向変化は、機能ブロック８１６に戻り、非共形ピクセルシーケンスがなくなるまでプロセス８１０を反復するだけで省略できるが、この反復は一般に８回未満で達成される。別の実施形態では、このように発生した非共形方向変化は、非共形方向変化が修正されるごとに発生した非共形方向変化を調べて補正することにより、「リアルタイム」で補正することができる。
機能ブロック８６４は、その結果生じた簡略化連鎖コードからハフマンコードが生成されることを示す。輪郭内の約５０％、２５％、および２５％のピクセルに発生する、方向８２６Ａ〜８２６Ｃに対応する連鎖コード８２４ａ〜８２４ｃの場合、それぞれハフマンコード０、１１、および１０が割り当てられる。このような１次のハフマンコードを使用すると、連鎖プロセス８１０では、輪郭内のピクセル当たり１．５ビットより少ないビットレートで輪郭を表すことができる。こうしたビットレートは、従来の連鎖コードプロセスよりも圧縮率が約５０％向上したことを表す。
ハフマン符号化が上位になるほど圧縮率も向上することが理解されよう。上位のハフマン符号化には、たとえば１次のハフマンコードのあらかじめ選択されたシーケンスに所定値を割り当てるステップが含まれる。
スプライト生成の概要
スプライト生成は、ビデオシーケンスの各フレーム内にある非矩形ビデオオブジェクトを表す、表示画像の構築を含む符号化限定動画ビデオ（映画）と合わせて使用される。スプライトを生成する場合、ビットマップは、１つの画像ソースから得られる順次画像の多数の順次ビットマップを備えた、ビットマップシリーズに融合（ａｃｃｒｅｔｅ）される。融合は、オブジェクトまたは図形（ｆｉｇｕｒｅ）が相互に関連しながら移動しているか、または前景の図形が背景を妨げるのと同様に、１つの図形が別の図形に妨げられている場合に発生する、ピクセルの妨害に関する問題を解決するのに使用される。たとえば、前景の図形が移動して新しい背景が現れる場合、後続のビットマップで取り出されることになっていたピクセルを含めることによって前のビットマップが第１に強調されない限り、前のビットマップからその新しい背景を構築する方法はない。この方法は、図形の不完全な画像を採用し、最終的には画像に属しているがすぐには見えないピクセルを見つけるのを待つ。これらのピクセルは、図形に合成ビットマップを作成するのに使用される。合成ビットマップを使用する場合、合成ビットマップをゆがめることで図形の将来の表示が作成できる。
フィーチャポイントを使用したスプライト生成の実施
符号化プロセスは、オペレータが現在のビットマップシリーズから現在のビットマップの図形および図形の一部を識別することから始まる。図形の一部がその周囲で移動する部分のフィーチャに関して、オペレータがフィーチャポイントまたはゆがみポイントを選択する。三角形の現在のグリッドが現在のビットマップの一部に重ね合わされる。三角形の現在のグリッドを構築する三角形は、隣接するゆがみポイントを結合することで形成される。このゆがみポイントは三角形の頂点である。現在のビットマップ上にある各三角形の現在位置が決定され、記憶装置に記憶される。各三角形の現在位置の範囲内にある第１の画像を定義する現在のビットマップのデータの一部は、将来使用するために保持される。
現在のビットマップシリーズの第２の画像を定義する次のビットマップが画像ソースから受け取られ、図形および図形の一部がオペレータによって識別される。次に、現在のビットマップからの三角形の現在のグリッドが、次のビットマップ上に重ね合わされる。三角形の現在のグリッドのゆがみポイントが、次のビットマップ上にある対応する図形のフィーチャと一致するように再度位置合わせされる。再度位置合わせされたゆがみポイントは、第２の画像の次のビットマップ上にある三角形の次のグリッドを形成する。次のビットマップ上にある各三角形の次の位置が決定され、記憶装置に記憶される。各三角形の次の位置内にある第２の画像を定義する次のビットマップのデータの一部は、将来使用するために保持される。
各三角形の現在の位置および次の位置を決定して記憶するプロセスは、現在のビットマップシリーズの多数の順次ビットマップに対して反復される。このプロセスが完了すると、現在のビットマップシリーズにある各三角形の平均画像が、別々に保持されたデータから決定される。各三角形の平均画像は、記憶装置に記憶される。
再生時には、現在のビットマップシリーズの各三角形の平均画像および現在のビットマップの各三角形の現在の位置が、記憶装置から取り出される。予測ビットマップは、現在のビットマップシリーズにある各三角形の平均画像を現在のビットマップの各三角形の現在位置に変換するための変換ソリューションを計算し、その変換ソリューションを各三角形の平均画像に適用することで生成される。この予測ビットマップは表示用モニタに渡される。
再生時にプログラムを制御することで画像が決定される、再生限定動画ビデオ（ビデオゲーム）と組み合わせて、スプライトビットマップ全体が記憶装置に記憶される。スプライトビットマップは、スプライト画像を定義する多数のデータビットを備える。スプライトビットマップはモニタ上に表示され、スプライトの一部がオペレータによって識別され、さらにそのスプライトの一部についてゆがみポイントが選択される。
三角形のグリッドはスプライトビットマップの一部に重ね合わされる。三角形のグリッドを構築する三角形は、隣接するゆがみポイントを結合することによって形成される。ゆがみポイントは三角形の頂点である。スプライトビットマップの各三角形の位置が決定され、記憶装置に記憶される。
再生時には、各三角形の次の位置が制御プログラムから受け取られる。スプライトビットマップおよびスプライトビットマップ上にある各三角形の次の位置が記憶装置からリコール（ｒｅｃａｌｌ）され、表示プロセッサに渡される。各三角形の次の位置も表示プロセッサに渡される。
変換ソリューションは、スプライトビットマップ上の各三角形について計算される。次いで、各三角形の位置内にあるスプライト画像を定義するスプライトビットマップから導かれた各三角形の変換ソリューションを適用することで、表示プロセッサに次のビットマップが生成される。表示プロセッサはこの次のスプライトビットマップを表示用モニタに渡す。このプロセスは、制御プログラムによって要求される各三角形のそれぞれの次の位置について反復される。
図２６に示すように、映画の動画ビデオ用符号化手順は、ＣＰＵ２２が画像ソースから現在のビットマップシリーズを受け取ることによって、ステップ９００から開始される。現在のビットマップシリーズは、順次画像の多数の順次ビットマップを備える。現在のビットマップシリーズは、画像ソースから第１の画像を定義する多数のデータビットを備えた現在のビットマップを有する。第１の画像は、少なくとも１つの部分を有する少なくとも１つの図形を備える。
ステップ９０２に進むと、オペレータ側のモニタ２８に第１の画像が表示される。モニタ２８から、現在のビットマップ上にある第１画像の図形がオペレータによって識別される。次いで、ステップ９０４では、現在のビットマップ上にある図形の一部がオペレータによって識別される。
次にステップ９０６で、オペレータが現在のビットマップ上にあるフィーチャポイントまたはゆがみポイントを選択する。ある部分の相対的動きが発生しやすい場所でゆがみポイントがビットマップ上のフィーチャと一致するように、ゆがみポイントが選択される。ビットマップ上の図形、図形の一部、およびゆがみポイントは、コンピュータシステム２０またはそれからの補助によって識別される場合があることを、当業者であれば理解されよう。ただし、ビットマップ上の図形、図形の一部、およびゆがみポイントは、オペレータが識別することが好ましい。
ステップ９０８へ進むと、コンピュータシステム２０によって、三角形の現在のグリッドが現在のビットマップの一部に重ね合わされる。図２７Ａを参照すると、現在のグリッドは隣接するゆがみポイントを接続することで形成される三角形を備える。ゆがみポイントは三角形の頂点を形成する。具体的に言えば、現在のビットマップの第１の画像は図形、すなわち人物９７０である。人物９７０には、頭部９７２、胴体９７４、右腕９７６、左腕９７８、右脚９８０、および左脚９８２に対応する６つの部分がある。ある部分の相対的動きが発生しやすい場所の特徴にゆがみポイントが一致するように、人物９７０の各部分でゆがみポイントが選択される。現在のグリッドは、隣接するゆがみポイントを接続することによって形成される現在の各グリッドの三角形を使って各部分に重ね合わされる。したがって、ゆがみポイントは三角形の頂点を形成する。
ステップ９１０では、コンピュータシステム２０が現在のビットマップ上にある各三角形の現在位置を決定する。現在のビットマップ上にある各三角形の現在位置は、三角形の頂点を形成するゆがみポイントの位置によって定義される。ステップ９１２では、各三角形の現在位置が記憶装置に記憶される。各三角形の現在位置内で第１の画像を定義する現在のビットマップから導かれたデータの一部が、ステップ９１４で保持される。
次にステップ９１６で、現在のビットマップシリーズの次のビットマップが、ＣＰＵ２２によって導かれる。この次のビットマップは、現在のビットマップシリーズの第２の画像を定義する多数のデータビットを備える。この第２の画像は、第１の画像内にある図形に対応する図形を含んでいる場合と含んでいない場合がある。以下のステップでは、この第２の画像は第１の画像にある図形に対応する図形を含んでいると想定されている。ステップ９１８では、三角形の現在のグリッドが次のビットマップ上に重ね合わされる。三角形のグリッドが重ね合わされた第２の画像は、オペレータ側のモニタ２８に表示される。
ステップ９２０では、オペレータがコンピュータシステム２０の補助を受けて、次のビットマップ上の対応するフィーチャと一致するように、ゆがみポイントを再度位置合わせする。コンピュータシステム２０は、ブロック突合せを使用してゆがみを再度位置合わせする。オペレータはどんな誤りも修正する。図２７Ｂを参照すると、再度位置合わせされたゆがみポイントは、三角形の次のグリッドを形成する。再度位置合わせされたゆがみポイントが、三角形の頂点である。具体的に言えば、人物２００の次のビットマップの第２画像は、頭部９７２、胴体９７４、右腕９７６、左腕９７８、右脚９８０、左脚９８２を含む。ただし第２画像では、右腕９８０が上がっている。第１画像の現在のグリッドは各部分に重ね合わされ、そのゆがみポイントは第２画像上の対応するフィーチャと一致するように再度位置合わせされている。再度位置合わせされたゆがみポイントは、三角形の次のグリッドを定義する。次のグリッドは、再度位置合わせされたゆがみポイントを接続することによって形成される。したがって、再度位置合わせされたゆがみポイントは、次のグリッドの三角形の頂点を形成する。
ステップ９２２に進むと、次のビットマップの各三角形の次の位置が、コンピュータシステム２０によって決定される。ステップ９２４では、次のビットマップ上にある各三角形の次の位置が記憶装置に記憶される。各三角形の次の位置内で第２画像を定義する次のビットマップから導かれたデータの一部が、ステップ９２６で保持される。ステップ９２６の次は判定ステップ９２８であって、ここで次に続くビットマップが存在するかどうかが判定される。
次に続くビットマップが存在する場合は、判定ステップ９２８のＹＥＳ方向にあるステップ９３０に進むが、ここでは次のビットマップが現在のビットマップになる。ステップ９３０はステップ９１６に戻り、ここで現在のビットマップシリーズの次のビットマップがＣＰＵ２２によって受け取られる。次に続くビットマップが存在しない場合は、判定ステップ９２８のＮＯ方向にあるステップ９３２に進み、ここで現在のビットマップシリーズの各三角形の平均画像が決定される。平均画像は、三角形のピクセルの中位値である。平均画像を使用すると、プロセスが退化（ｄｅｇｅｎｅｒａｔｉｏｎ）しにくくなる。ステップ９３４に進むと、現在のビットマップシリーズの各三角形の平均画像が記憶装置に記憶される。
次にステップ９３６では、現在のビットマップ上にある各三角形の現在位置が記憶装置から取り出される。次いでステップ９３８で、各三角形の平均画像を現在のビットマップ上にある三角形の現在位置に変換するためのアフィン変換ソリューションが、コンピュータシステム２０によって計算される。ステップ９４０では、各三角形の平均画像を現在のビットマップ上にある各三角形の現在位置に変換する変換ソリューションを適用することによって、予測ビットマップが生成される。この予測ビットマップがステップ９４２で現在のビットマップと比較される。
ステップ９４４で、補正ビットマップが生成される。補正されたビットマップは、予測ビットマップによって正確に予測されなかった現在のビットマップのデータビットを備える。補正されたビットマップは、ステップ９４８で記憶装置に記憶される。ステップ９４８の次は判定ステップ９５０で、ここで次のビットマップが存在するか否かを判定する。
次のビットマップが存在する場合は、判定ステップ９５０のＹＥＳ方向にあるステップ９５２に進み、ここで次のビットマップが現在のビットマップになる。ステップ９５２はステップ９３６に戻り、ここで現在のビットマップ上にある各三角形の現在位置が記憶装置から取り出される。次に続くビットマップが存在しない場合、判定ステップ９５０のＮＯ方向にある判定ステップ９５４に進み、ここで次のビットマップシリーズが存在するか否かを判定する。次のビットマップシリーズが存在しない場合、符号化は完了し、判定ステップ９５４のＮＯ方向にあるステップ９５６に進む。次のビットマップシリーズが存在する場合は、判定ステップ９５４のＹＥＳ方向にあるステップ９５８に進み、ここでＣＰＵ２２が現在のビットマップシリーズとして次のビットマップシリーズを受け取る。ステップ９５６はステップ９０２に戻り、ここで現在のビットマップシリーズの第１画像の図形がオペレータによって識別される。
図２６のプロセスは、図３の符号器プロセス６４が使用するためのスプライトまたはマスタオブジェクト９０の生成について記載している。マスタオブジェクト９０を使用して予測オブジェクト１０２を形成するプロセスは、図２８を参照して記載されている。
図２８に示すように、この手順は現在のビットマップシリーズが取り出されるステップ１０００から開始される。現在のビットマップシリーズは、順次画像の多数の順次ビットマップを備える。現在のビットマップシリーズは、画像ソースから第１の画像を定義する多数のデータビットを含む現在のビットマップを有する。第１の画像は、少なくとも１つの部分を有する少なくとも１つの図形を備える。
ステップ１００２では、現在のビットマップシリーズの各三角形の平均画像が記憶装置から取り出される。次いでステップ７０４で、各三角形の平均画像が表示プロセッサ（図示せず）に渡される。コンピュータシステム２０（図１）は任意選択で、本発明の各プロセスを実行するための表示プロセッサまたはその他の専用構成要素を含むことができることを理解されよう。ステップ１００６に進むと、現在のビットマップ上にある各三角形の現在の位置が記憶装置から取り出される。ステップ１００８で各三角形の現在位置が表示プロセッサに渡される。
次に、各三角形の平均画像を現在のビットマップ上にある各三角形の現在位置に変換するためのアフィン変換ソリューションが、ステップ１０１０で表示プロセッサによって計算される。ステップ１０１２に進むと、各三角形の平均画像を現在のビットマップ上にある各三角形の現在位置に変換するための変換ソリューションを適用することにより、表示プロセッサによって予測ビットマップが生成される。
ステップ１０１４では、現在のビットマップの補正ビットマップが記憶装置から取り出される。この補正ビットマップはステップ７１６で表示プロセッサに渡される。次いでこの補正ビットマップで予測ビットマップをオーバーレイすることで、表示プロセッサ内に表示ビットマップが生成される。表示プロセッサは、各三角形の平均画像のコピーを保持し、表示ビットマップをモニタ上に表示するためにフレームバッファに渡す。
次に判定ステップ１０２０で、現在のビットマップシリーズの次のビットマップが存在するか否かを判定する。現在のビットマップシリーズの次のビットマップが存在する場合は、判定ステップ１０２０のＹＥＳ方向にあるステップ１０２２に進む。ステップ１０２２では、次のビットマップが現在のビットマップになる。ステップ１０２２はステップ１００６に戻り、ここで現在のビットマップ上にある各三角形の位置が記憶装置から取り出される。
再び判定ステップ１０２０で、現在のビットマップシリーズの次のビットマップが存在しない場合は、判定ステップ１０２０のＮＯ方向にある判定ステップ１０２４に進む。判定ステップ１０２４では、次のビットマップシリーズが存在するかどうかを判定する。次のビットマップシリーズが存在しない場合、プロセスは完了し、判定ステップ１０２４のＮＯ方向にあるステップ１０２６に進む。次のビットマップシリーズが存在する場合は、判定ステップ１０２４のＹＥＳ方向にあるステップ１０２８に進む。ステップ１０２８では、次のビットマップシリーズが現在のビットマップシリーズになる。ステップ１０２８はステップ１０００に戻る。
スプライトを使用する簡略オブジェクト符号化
図２９は、それぞれ図３Ａおよび図２３Ａを参照しながら説明したビデオ圧縮符号器プロセス６４およびビデオ圧縮復号器プロセス７００と合わせて使用することが好ましい、簡略圧縮方法１１００を示す機能ブロック図である。簡略オブジェクト圧縮方法１１００は、以下に詳細に記載するように、オブジェクトが最初に表示されるときからのすべてのビデオシーケンスが完全に定義された、スプライト定義オブジェクトの圧縮ビデオ表示を符号化および復号化することを対象にしている。
簡略圧縮方法１１００、符号器プロセス６４、および復号器プロセス７００は、少なくとも１つのスプライト定義オブジェクトならびに、ビデオシーケンスで最初の表示から完全には定義されていない少なくとも１つの一般的なビデオオブジェクトを含む、一般的なビデオシーケンスまたは情報に適用されることが好ましい。一般的なビデオシーケンスの一般的なビデオオブジェクトは、前述の符号器プロセス６４および復号器プロセス７００によって処理されることが好ましい。一般的なビデオシーケンスのスプライト定義オブジェクトは、簡略圧縮方法１１００によって処理されることが好ましい。
スプライト定義オブジェクトは、一般的なビデオシーケンスの一般的なオブジェクトのサブセットであって、ビデオシーケンスに最初に表示されるときに、他のオブジェクトよりも多くの情報が利用可能である。簡略圧縮方法１１００を使用すると、符号器プロセス６４および復号器プロセス７００によって、スプライト定義オブジェクトに使用可能な追加情報が、本来の追加情報よりも効率よく使用できるようになる。その結果、簡略プロセス１１００に従って、一般的なビデオシーケンスのスプライト定義オブジェクトを処理すると、一般的なビデオ情報を記憶または伝送する場合のビットレート要件および効率をさらに向上させることができる。
スプライト定義オブジェクトは、「スプライト」および１つまたは複数の軌線によって最初に表示される時点で、ビデオシーケンス全体で完全に定義される。スプライトには、ビデオシーケンス全体のオブジェクトの画像特性がすべて含まれており、ビデオシーケンスの各フレーム内でオブジェクトを表示するために、１つまたは複数の軌線がスプライトをゆがめるかまたは変換する。アプリケーションによっては、ビデオシーケンスでオブジェクトが最初に表示された時点でわかっている、照明または透明性要素（ｔｒａｎｓｐａｒｅｎｃｙ  ｆａｃｔｏｒ）によってオブジェクトがさらに定義または修正される。スプライト定義オブジェクトは、たとえばビデオ会議およびコンピュータ生成グラフィックアプリケーションで頻繁に発生する。簡略圧縮方法１１００は、たとえば一般的なビデオ圧縮、マルチメディアアプリケーション、デジタルビデオアーカイブ、ネットワークまたはインターネット検索、およびビデオ伝送などにも適用可能である。
図２９を参照すると、プロセスブロック１１０２は、一般的なビデオシーケンスの複数オブジェクトそれぞれに関連するオブジェクト情報が、たとえばビデオ圧縮符号器プロセス６４（図３Ａ）の機能ブロック６６〜９６により得られることを示す。ビデオシーケンス内の少なくとも１つのオブジェクトは、スプライト生成オブジェクトであり、これに関してビデオシーケンスに必要なすべてのオブジェクト情報が使用可能であるか、またはビデオシーケンスの最初から「周知」である。スプライト定義オブジェクトに関するオブジェクト情報には、ビデオシーケンス全体のオブジェクトの画像特性をすべて含むスプライト、ならびにビデオシーケンスの各フレーム内にあるオブジェクトを表すためにスプライトをゆがめるかまたは変形させる軌線が含まれる。ビデオシーケンスは一般に、スプライト生成オブジェクトでない一般的なビデオオブジェクトを少なくとも１つ含むかまたは含むことができる。
たとえばコンピュータ生成グラフィックの場合、ビデオシーケンスの最初またはオブジェクトがビデオシーケンスに最初に表示されたときに使用可能なオブジェクトは、通常スプライト（または数学的に定義されたオブジェクトモデル）および軌線によって表される。軌線は、変換情報と呼ばれることもあり、ビデオシーケンス全体でオブジェクトを生成するのに使用されるので、使用可能である。変換情報は、多次元アフィン変換または透視（ｐｅｒｓｐｅｃｔｉｖｅ）変換の形式をとることができる。図１２に示した変換方法３５０を参照して前述したように、アフィン変換は次式のように表されることが好ましい。
ｘ′＝ａｘ＋ｂｙ＋ｃ
ｘ′＝ｄｘ＋ｅｙ＋ｆ
また変換情報は、たとえばＧｅｏｒｇｅ  Ｗｏｌｂｅｒｇ著「Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｗａｒｐｉｎｇ」ＩＥＥＥ、１９９０年に記載されているように、次式のように表されることが好ましい透視変換の形式をとることができる。
ｘ′＝（ａｘ＋ｂｙ＋ｃ）＼（ｇｘ＋ｈｙ＋１）
ｙ′＝（ｄｘ＋ｅｙ＋ｆ）＼（ｇｘ＋ｈｙ＋１）
図２６のスプライト生成または符号化プロセス（たとえばステップ９３６）を参照して説明したように、スプライトまたはオブジェクトは通常複数のアフィン変換で表され、したがって複数の軌線で表されることが多い。簡略圧縮方法１１００のこの記述で、１つの変換（アフィンまたは透視）または単数の軌線を参照しているのは、単に例示のためであり、この方法に制限があることを意図するものではないことを理解されよう。
たとえばビデオ会議用アプリケーションの場合、ビデオ会議場面の背景に対応するオブジェクトを、背景スプライト画像化中に背景だけを画像化することによって得られるスプライト定義オブジェクトとして形成することができる。この例の変換情報は、ビデオ場面全体を通じてオブジェクトを静的状態に維持するアイデンティティ変換である。こうしたアプリケーションでは、背景オブジェクト表示を簡略化することによって、ビデオシーケンスすなわち会議の伝送に必要な帯域幅が大幅に減少する可能性がある。
これら２つの例は単なる例示的なものであって、スプライトのタイプや適用範囲を制限するものではないことを理解されよう。一例として、単純な平行移動で変換されるコンピュータ生成グラフィック背景は、他のコンピュータ生成グラフィックオブジェクトまたはビデオグラフィックオブジェクトのいずれかで使用できる。
プロセスブロック１１０４は、一般的なビデオシーケンスの複数オブジェクトそれぞれに関係するオブジェクト情報において、スプライト定義オブジェクトが一般のオブジェクトと区別されることを示す。スプライト定義オブジェクトは、簡略化圧縮プロセス１１００の以下の処理ステップに従って処理される。一般的なオブジェクトは、それぞれ図３Ａおよび図２３Ａの符号器プロセス６４および復号器プロセス７００に従って処理されることが好ましい。スプライト定義オブジェクトは、たとえば作成時にラベル表示することによって区別してもよい。
ビデオ会議用アプリケーションの場合、たとえばビデオ会議場面の背景に対応するオブジェクトを、背景画像化時に背景だけを画像化することによって得られるスプライト定義オブジェクトにすることができる。別の例として、コンピュータ生成グラフィックオブジェクトは一般に、データまたはアルゴリズムによって全体的に生成され、一般にスプライト定義オブジェクトになる。一般にライブのビデオシーケンスの場合、符号化オペレータは何らかのオブジェクトにスプライト定義として手動でラベルを付けることができる。
プロセスブロック１１０６は、スプライト情報および変換情報が、簡略符号化プロセスによって符号化されることを示す。スプライト情報は、前述のように、ウェーブレットまたはＤＣＴ符号化のような従来の損失のある符号化プロセスによって記録されることが好ましい。スプライト定義オブジェクトが、（ビデオシーケンスでオブジェクトが最初に表示された時点でわかっている）照明または透明性要素などの追加要素によってさらに定義または修正される場合は、必ずこの追加要素もスプライトと同じ方法で符号化される。スプライトおよび追加要素の符号化には、たとえば拡張された圧縮または符号化を提供するための事前圧縮外挿方法４００（図１７Ａおよび図１７Ｂ）の適用がさらに含まれることがある。
軌線情報または変換情報は軌線として表され、Ｗｉｌｌｉａｍ  Ｂ．ＰｅｎｎｅｂａｋｅｒおよびＪｏａｎ  Ｌ．Ｍｉｔｃｈｅｌｌ共著「ＪＰＥＧ：Ｓｔｉｌｌ  Ｉｍａｇｅ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｓｔａｎｄａｒｄ」Ｖａｎ  Ｎｏｓｔｒａｎｄ  Ｒｅｉｎｈｏｌｄ，Ｎｅｗ  Ｙｏｒｋ、１９９３年に記載されているように、ＱＭ符号化などの損失のない符号化技法によって符号化または圧縮されることが好ましい。ハフマン符号化のような他の損失のない符号化技法が好適であることを理解されよう。例示のために、以下の記述はＱＭ符号化を対象としている。
スプライトのフィーチャポイント位置は、各軌線の基準として設定される。各軌線のｘおよびｙ構成要素は、スプライトのフィーチャポイントまたはピクセルの座標、ならびにスプライトのフィーチャポイントまたはピクセルと、対応する画像フレーム内の対応するオブジェクトの対応するフィーチャポイントまたはピクセルとの座標差を有する、表示またはビットストリームを形成するために、ＱＭ符号化される前に区別をつけて符号化および連結される。（ｘi（j），ｙi（j））、ｉ＝１、．．．，Ｔ，ｊ＝１，．．．，Ｎと表されるフィーチャポイント位置について、Ｔ個の画像フレームを有するビデオシーケンスおよびＮ個の軌線を有するスプライトの場合、ＱＭ符号化されることが好ましい値は、次式のようになる。
x1（1）,Δx2（1）,...,ΔxT（1）,y1（1）,Δy2（1）,...,ΔyT（1）,
x1（2）,Δx2（2）,...,ΔxT（2）,y1（2）,Δy2（2）,...,ΔyT（2）,
x1（N）,Δx2（N）,...,ΔxT（N）,y1（N）,Δy2（N）,...,ΔyT（N）
プロセスブロック１１０８は、符号化されたスプライト生成オブジェクトが、マルチメディアアプリケーション、デジタルビデオアーカイブ、ネットワークまたはインターネット検索、およびビデオ伝送を含む、符号化または圧縮されたデジタル情報の一般的な使用方法により記憶されるかまたは伝送され、取り出されるかまたは受け取られることを示す。
プロセスブロック１１１０は、記憶装置から取り出されたかまたは伝送を介して受け取られた符号化されたスプライト生成オブジェクトが復号化されることを示す。符号化された軌線はＱＭ復号化され、スプライトは符号化された形式（たとえばＤＣＴ）に従って復号化される。
オブジェクトベースビデオ符号化におけるスプライトの概要
スプライトとは、ビデオシーケンス全体にわたってビデオオブジェクトを表すピクセルで構成される画像のことである。たとえば、ビデオシーケンス全体にわたって場面の背景を表すスプライトは、シーケンス全体にわたって背景オブジェクトのすべての可視ピクセルを含む。一部のシーケンスの間は妨げられ、残りのシーケンスの間は、見えている背景オブジェクトの一部は、それでもなおシーケンス全体にわたってスプライトを生成するのに使用される。スプライトは、少なくともビデオシーケンス中に１回は見えた背景オブジェクトのすべての部分を含むので、スプライトを使用して背景オブジェクトを直接再構築するか、またはこれを背景オブジェクトの予測符号化に使用することができる。
スプライトには、（１）オフライン静的スプライト、および（２）オンライン動的スプライトという２つの主要なタイプがある。静的スプライトは、ビデオシーケンス内にあるフレームのスプライトからビデオオブジェクトを再構築するために、直接コピーされる（適切なワーピング（ｗａｒｐｉｎｇ）およびクロッピング（ｃｒｏｐｐｉｎｇ）を含む）スプライトである。静的スプライトはオフラインで構築され、静的スプライトのテクスチャおよび形状は符号化されてビデオ自体の符号化とは別に伝送される。オフラインの場合、静的スプライトはビデオオブジェクトを使用してビデオシーケンス内の各フレームから生成される。
動的スプライトは静的スプライトとは異なり、予測符号化において基準として使用される。予測符号化では、ビデオオブジェクトの動作がスプライトの動作パラメータを使用して補償される。動的スプライトは、符号器および復号器の両方で、符号化時にオンラインで動的に構築される。
オフライン静的スプライトは、特に合成オブジェクトに好適である。また、ほとんどが剛体運動を受ける未加工の（ｎａｔｕｒａｌ）ビデオオブジェクトにも好適である。オンライン動的スプライトは拡張された予測符号化環境で使用される。未加工のビデオオブジェクトの場合、オンライン動的スプライトは待ち時間を減らすかまたはローカル動作により生じる細部を保存することが好ましい。
スプライトベースの符号化の重要な一態様は、スプライト生成の方法である。オンラインおよびオフラインのスプライト生成方法は、同様の方法を使用する。オフラインの場合、スプライト生成方法は各フレームからのビデオオブジェクトを使用して、ビデオシーケンスが符号化される前にスプライトを構築する。オンラインの場合、符号器および復号器は、現在のビデオオブジェクトおよび前のフレーム用に再構築されたビデオオブジェクト（前に構築されたビデオオブジェクトまたは「参照オブジェクト」）から、スプライトを生成する。
スプライト生成プロセスには、以下のステップが含まれる。
１）ビデオオブジェクト内の各ピクセルが、スプライト内の対応するピクセルにどのようにマッピングするかを決定するために、グローバル動作推定を実行する。
２）グローバル動作推定パラメータを使用して、ビデオオブジェクトをスプライトの座標システムにワーピングする。
３）ワーピングされたオブジェクトのピクセルと対応するスプライトのピクセルとを混合する。
図３０は、スプライトの生成プロセスを示すために、ビデオシーケンス内のビデオオブジェクトを例示した図である。この例では４つのフレーム（０〜３）を示し、それぞれがジュースの缶を表すビデオオブジェクトＩ0〜Ｉ3を描画している。フレーム０の矢印は、ビデオシーケンス全体にわたるジュース缶の動作方向を示す。具体的に言えば、ジュース缶は上下が宙返りしながら、破線で示した軸を中心にわずかに回転している。ジュース缶は宙返りしながら同時に、「ＪＵＩＣＥ」のラベルの左側が見えなくなり、ラベルの右側が見えてくることからわかるように、わずかに回転もしている。図３０の下側の画像は、各フレームのビデオオブジェクトから増分的に構築されたスプライトである。各画像Ｓ0〜Ｓ3は、各フレームのワーピングされたビデオオブジェクトから構築されるスプライトを表す。
図３１は、スプライト生成器を示すブロック図である。動作推定ブロック１２００は、現在のフレームのビデオオブジェクト、前のフレームにあるビデオオブジェクトから構築されたスプライト、ならびに現在のビデオオブジェクトおよびスプライトのマスクに基づいて、「グローバル動作推定」を実行する。オフライン静的スプライトの場合、グローバル動作推定ブロックは、現在のフレームのビデオオブジェクトと前のフレームのビデオオブジェクトから構築されたスプライトとの間での相対的動作を推定する。グローバル動作推定ブロックは、現在のフレームのビデオオブジェクトと前に構築されたオブジェクトとの間の動作を推定することを除けば、動的スプライトに対しても同じ機能を果たす。
ビデオオブジェクトのグローバル動作は、透視変換などの幾何学的動作モデルを基準にしてモデリングされる。本出願人等が現在実施しているスプライト生成器は、透視変換に基づくものであるが、無動作（静止）、平行移動動作、等方性拡大、回転および平行移動、ならびにアフィン変換を含む特別な透過変換例である、別のタイプの変換も実行する。これらの変換は、スプライトに対してビデオオブジェクトの動作を定義する。各変換を表すデータ（変換情報）は、１組の動作パラメータとして表すことができる。たとえば、グローバル動作モデルが透視変換に基づいている場合、動作パラメータは１組の動作係数として表すことができる。動作係数は、ビデオオブジェクト（すなわちビデオオブジェクト内のポイント）をスプライトの座標空間にワーピングするのに使用される透視変換マトリックスの要素に対応している。前述のように、動作パラメータは、ビデオオブジェクト内の基準ポイントがスプライトの座標空間に対してどのように移動するかを定義する、一連の軌線または動作ベクトルとして表すこともできる。
本出願人等の実施態様では、動作推定ブロック１２００は、各ビデオオブジェクトを前に構築されたスプライトにワーピングするのに使用される動作パラメータを計算する。スプライトは最初に、図３０に示すように第１のフレーム（フレーム０）のビデオオブジェクトに設定される。次いで動作推定ブロック１２００は、ワーピングされたビデオオブジェクトとスプライト内にある対応するピクセルとの間の強度エラーを最小限にする、動作パラメータの組を見つけようとする。
図３１に示されたワーピングブロック１２０２は、ビデオオブジェクト内のピクセルの座標をスプライトまたは基準オブジェクト内の座標に変換するプロセスを表す。この場合、動作パラメータを使用して、現在のフレームに関するビデオオブジェクト（現在のビデオオブジェクト）をスプライト座標に変換する。たとえば図３０の場合、Ｉ1をスプライトＳ0にワーピングするのに、ビデオオブジェクトＩ1の動作パラメータが使用される。透視変換が動作モデルとして使用される場合、ワーピングブロック１２０２は動作係数から形成された透視変換マトリックスを使用して、スプライトの座標空間にビデオオブジェクトをワーピングする。
混合ブロック１２０４は、ワーピングされたオブジェクトとスプライトまたは基準オブジェクトとを結合するプロセスを表す。オンライン動的スプライトの場合、混合ブロック１２０４は現在のオブジェクトと前に構築されたオブジェクトとを混合する。本出願人等の実施態様の一利点は、各ビデオオブジェクトがスプライトにほぼ同様に寄与するように、混合ブロック１２０４が、ワーピングされた各ビデオオブジェクトをスプライトと増分的に混合することである。これを達成するために、混合ブロックは、そこからスプライトが構築された前のフレームからのビデオオブジェクトの数に比例して、スプライトからのピクセルに重みづけする。これによりスプライトは、ビデオシーケンス全体にわたって、各ビデオオブジェクトからほぼ同様の寄与を受ける。ワーピングされたビデオオブジェクトとスプライトとを混合する特定の方法について、以下に詳しく説明する。
図３０は、ワーピングされたオブジェクトと各フレームに対して前に構築されたスプライトとを混合することによって、スプライトがどのように構築されるかを例示的に示した図である。たとえば、混合ブロックは、スプライトＳ0をワーピングされたビデオオブジェクトＷ1と混合して、スプライトＳ1を構築する。このスプライトは、前に構築されたスプライトと現在のフレーム用にワーピングされたビデオオブジェクトとを混合することで、各フレームについて更新されることに留意されたい。
図３１に示すように、スプライトはフレームメモリ１２０６に記憶される。動作推定ブロック１２００は、フレームメモリからスプライトにアクセスして、ビデオシーケンス内の各ビデオオブジェクトについて動作パラメータを計算する。具体的に言えば、動作推定は、現在のビデオオブジェクトおよびスプライトに関するマスクおよびテクスチャデータを使用して、現在のビデオオブジェクトとスプライトとの間の相対的動作を推定する２Ｄ変換の動作係数を計算する。
以上、スプライトの生成プロセスの概要を述べてきたが、これは、オブジェクトベースのビデオ符号化においてスプライトがどのように使用されるかを理解するために、スプライトおよび動作パラメータがどのように符号化されるかを考慮するのに役立つ。
スプライトの符号化
スプライトは、そのテクスチャ、形状、および動作パラメータを符号化することによって符号化される。スプライトのテクスチャおよび形状は、前述の技法を使用して符号化することができる。
各ビデオオブジェクトの動作パラメータを符号化する方法の１つは、ビデオオブジェクトの基準ポイントの軌線を記録する方法である。たとえば、透視変換の動作係数は、ビデオオブジェクトの４つ以上の基準ポイントの座標ならびにスプライト内の対応する「ワーピングされた」基準ポイントを使用して符号化することができる。これら４対の基準ポイントを使用して、ビデオ復号器は動作推定で使用される変換の動作係数を導くことができる。
変換の動作係数を符号化するのに必要な基準ポイントの数は、変換のタイプによって異なる。以下に、透視変換および透視変換の特例（アフィン、等方性拡大、回転、および平行移動、平行移動動作、静止（動作なし））を符号化するのに必要な基準ポイントについて概説する。
グローバル動作推定に使用される透視変換は、次式のように表すことができる。
ｘ′＝（ａｘ＋ｂｙ＋ｃ）／（ｇｘ＋ｈｙ＋１）
ｙ′＝（ｄｘ＋ｅｙ＋ｆ）／（ｇｘ＋ｈｙ＋１）
ここで｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ｝は変換の動作係数、（ｘ，ｙ）は現在のビデオオブジェクト内にあるピクセルの座標、（ｘ′，ｙ′）はワーピングされた座標である。オンライン動的スプライトの場合、座標（ｘ′，ｙ′）はビデオオブジェクトの座標系で表された前のビデオオブジェクトにあるピクセルの座標である。オフライン静的スプライトの場合、座標（ｘ′，ｙ′）はスプライト座標系で表されたスプライトの座標である。本出願人等は、ワーピングされた座標が、ビデオオブジェクト内のピクセルに対応するスプライト内のピクセル位置を識別することから、この座標をスプライト内の「対応ピクセル」の座標と呼ぶ。
透視変換の動作係数を符号化するには、少なくとも４つの基準ポイントが必要である。それほど複雑でない動作をモデリングする変換は、透視変換の特例として処理することができる。これらの変換には、等方性拡大、回転および平行移動、アフィン変換、平行移動、ならびに静止が含まれる。
１．アフィン変換
アフィン変換を（符号器で）表し、係数｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ｝について（復号器で）解くには、３つのポイントが必要である（符号化される）。
ｘ′＝ａｘ＋ｂｙ＋ｃ
ｙ′＝ｄｘ＋ｅｙ＋ｆ
２．等方性拡大、回転、および平行移動
このタイプの動作は、２つの基準ポイントを使用して符号化することができる。この場合、ｇ＝ｈ＝０である。変換式は、次式のように表すことができる。
ｘ′＝ａｃｏｓｑｘ＋ａｓｉｎｑｙ＋ｃ
ｙ′＝−ａｓｉｎｇｑｘ＋ａｃｏｓｑｙ＋ｆ
これは次式のように簡略化することができる。
ｘ′＝ａｘ＋ｂｙ＋ｃ
ｙ′＝−ｂｘ＋ａｙ＋ｆ
ここで、ａ＝ａ  ｃｏｓｑおよびｂ＝ａ  ｓｉｎｇｑである。未知のポイントが４つ、所与のポイントが２対（２つはスプライト側、２つはビデオオブジェクト側）にあるため、復号器はこれらの２つの式で変換係数を解いて、ワーピングを実行することができる。
３．平行移動
１つのポイントしか必要でなく、ビデオオブジェクトの動作が平行移動であれば符号化される。この場合、ａ＝１＝ｅ＝１、ｂ＝ｇ＝ｈ＝ｄ＝０となり、変換式は次式のように表すことができる。
ｘ′＝ｘ＋ｃ
ｙ′＝ｙ＋ｆ
復号器側では、１対のポイント（１つはスプライト側、１つは現在のビデオオブジェクト側）があればｃおよびｆを解くのに十分である。
４．静止
静止オブジェクトには基準ポイントは不要である。この場合、ａ＝ｅ＝１およびｂ＝ｃ＝ｄ＝ｆ＝ｇ＝ｈ＝０、すなわちｘ′＝ｘおよびｙ′＝ｙである。
基準ポイントの位置は、座標系でビデオオブジェクトおよびスプライトとして表される。ビデオオブジェクトおよびスプライトは、それぞれの座標空間においてピクセルの配列で構成される。ピクセルの強度値には、輝度値とクロミナンス値が含まれる。
ビデオオブジェクトおよびスプライトにおけるピクセル位置を表すには、起点を基準にしてピクセル位置を定義する２次元の指数値を使用する方法が便利である。たとえば、起点は左上の輝度ピクセルとして定義できる。次いで、ピクセルの位置は２次元指数値の関数として表すことができる。ビデオオブジェクト内のピクセル位置を２次元指数値、ｉおよびｊで表す例は、以下のとおりである。
ビデオオブジェクト内の輝度ピクセルは、次式で表される。
ｘ＝ｉ
ｙ＝ｊ
ビデオオブジェクト内のクロミナンスピクセルは、次式で表される。
ｘ＝２ｉc＋０．５
ｙ＝２ｊc＋０．５
ここで指数値ｉ、ｊ、ｉc、ｊcは整数である。
ビデオオブジェクト内の各ピクセルに関する動作ベクトルの正確さは、ワーピング精度パラメータ、ｓを使用して定義することができる。ピクセル正確さ１÷ｓ（使用可能値は２、４、８、または１６）が動作ベクトルに採用されると仮定すると、指数値とスプライトまたは参照ビデオオブジェクト内の座標との間の関係は、以下のように定義することができる。
スプライトまたは基準ビデオオブジェクト内の輝度ピクセルは、次式のように表すことができる。
ｘ′＝ｉ′÷ｓ
ｙ′＝ｊ′÷ｓ
スプライトまたは基準ビデオオブジェクト内のクロミナンスピクセルは、次式のように表すことができる。
ｘ′＝２ｉc′÷ｓ＋０．５
ｙ′＝２ｊc′÷ｓ＋０．５
ここで指数値ｉ′、ｊ′、ｉc′およびｊc′は整数である。ワーピングされた座標（ｘ′，ｙ′）はサブピクセルの正確さを表すことが可能であるが、スプライトは一般に整数ピクセルグリッド上にしかピクセルを持たない。したがって、双一次補間法を使用して、ビデオオブジェクト内のピクセル（ｘ，ｙ）について対応するピクセル値（ｘ′，ｙ′）が計算される。
ビデオオブジェクトの基準ポイントは、ビデオオブジェクトの境界ボックスのコーナーとして選択することができる。ビデオオブジェクトの境界ボックスは、ビデオオブジェクト内のピクセルを囲む矩形の領域である。この形式を使用すると、ビデオオブジェクトの境界ボックスの４つのコーナーを、境界ボックスの幅および高さに沿って、境界ボックスの左上のコーナーで表すことができる。次いでグローバル動作モデルで使用される動作係数は、スプライト内の４つの基準座標ならびにビデオオブジェクトの境界ボックスの位置およびサイズから導くことができる。
以上を要約すると、動作パラメータは、グローバル動作推定を使用して計算される。動作モデルは、ビデオオブジェクト内のピクセルの座標を、対応するスプライト内の座標にワーピングする、２Ｄ変換に基づいている。動作パラメータは、ビデオオブジェクトおよびスプライト内の基準ポイントを使用して１組の軌線として符号化するか、または１組の動作係数として符号化することができる。前者の場合、動作係数は基準ポイントから導くことができる。この動作係数に基づいて、ビデオオブジェクト内のピクセルをスプライト空間にワーピングするには、変換関数が使用される。ビデオオブジェクトおよびスプライト内のピクセル位置が前述の２次元指数値で表される場合、変換関数は、ビデオオブジェクトおよびスプライト内の２次元指数値で表すことができる。
マスクおよび丸め平均値を使用したスプライト生成方法の実施態様
スプライト生成方法に関するこの実施態様は、
１）現在のオブジェクトの起点として前のビデオオブジェクトについて計算された動作パラメータを使用し、現在のフレーム内にあるビデオオブジェクトと前に構築されたスプライトとの間の動作パラメータを探すステップと、
２）ステップ１の動作パラメータを使用して、現在のフレームのビデオオブジェクトを前に構築されたスプライトにワープするステップと、
３）丸め平均値を使用して、ワープされたオブジェクトと前に構築されたスプライトとを混合するステップという３つの構成要素を含む。
１つのビデオシーケンスがｎ個のフレームで構成され、ここで各フレームｉが、ビデオオブジェクトを表す画像、Ｉi，ｉ＝０，１，．．．，ｎ−１を含む場合を考えてみる。スプライト生成方法の実施態様は、以下のように要約できる。
Ｓ0＝Ｉ0，Ｍ0＝Ｉ（同一変換）
（ｉ＝１；ｉ＜ｎ；ｉ＋＋）の場合｛
Ｍi＝Ｍi-1
透視動作パラメータＭiをＩiとＳi-1の間で探す
ワープ済み画像Ｗiを取得するために、Ｍiを使用してＩiからＳi-1へワープする
Ｓi＝（ｉ*Ｓi-1＋Ｗi）／（ｉ＋１）；を使用してＳiを取得するためにＷiとＳi-1を混合する
｝
図３２は、このスプライト生成方法における各ステップを示した流れ図である。この方法は、ステップ１３００に示すように、スプライトの値および動作係数を初期設定することで開始される。スプライトは、初期にはフレーム０のビデオオブジェクトと同じに設定されている。動作係数は、初期には同一変換に設定されている。
スプライトおよび動作係数を初期設定した後、この方法は、ビデオシーケンスの各フレーム内にあるビデオオブジェクトからスプライトを増分的に構築する。スプライトを増分的に構築するために、この方法は各フレーム内のビデオオブジェクトＩiに対して、一連のステップを反復する。図３２は、ＦＯＲループ１３０２を使用して、この方法の反復性を表している。各フレームに対する第１の主要なステップは、グローバル動作推定を実行することである。本実施態様では、動作推定のプロセスは、ステップ１３０４に示すように前のフレームの動作係数を使用して動作係数を初期設定することで開始され、次いでステップ１３０６に示すように、現在のビデオオブジェクトの動作係数を計算する。現在のビデオオブジェクトＩiの動作係数Ｍiを計算する前に、動作係数は初期に、前のビデオオブジェクトＩi-1について計算された動作係数Ｍi-1に設定される。次いでこの方法は、ＩiとＳi-1との間の動作を推定する動作係数Ｍiを計算する。
オブジェクトの前の動作を起点として使用すると、現在のフレームの動作は前のフレームの動作に似ていることが多いので、動作推定が改善される。スプライトに対するビデオオブジェクトの動作を推定する場合、この方法は、現在のビデオオブジェクト内にあるピクセルに最もよく一致するピクセルの組をスプライト内で探そうとする。前の動作を起点として使用すると、最もよく一致するか、少なくとも許容可能なエラーはあるが一致しているものを探すための反復回数が少なくなるので、計算時間という点ではこの検索がより効率的になる。
この方法は現在のフレームの動作係数を計算した後、ステップ１３０８に示すように、動作係数Ｍiを使用して現在のビデオオブジェクトＩiを座標空間Ｓi-1にワープする。このステップ１３０８の結果が、スプライト座標空間内のワープ済みビデオオブジェクトＷiである。次いでこの方法は、Ｓi＝（ｉ*Ｓi-1＋Ｗi）／（ｉ＋１）の式に基づいてワープ済み画像ＷiとＳiを混合する。これは、図３２にステップ１３１０として例示されている。スプライトＳiは、そこから構築されたフレームｉの数に比例して重み付けされることに留意されたい。したがって各ワープ済み画像は、最終スプライトに対して等しく寄与する。
この方法は、混合ステップ時にビデオオブジェクト内の各ピクセルをスキャンし、現在の動作係数に基づいた２Ｄ変換を使用してこれをスプライト座標にワープする。ワープ済みピクセルがスプライトのマスクより外に出ている場合は、スプライトに加えられる。そうではなくマスクの内側にある場合は、丸め平均方法Ｓi＝（ｉ*Ｓi-1＋Ｗi）／（ｉ＋１）を使用してスプライトと混合される。
この方法は、ビデオシーケンス内の各フレームについて、ステップ１３０４〜１３１０を反復する。したがってこの方法は、混合操作を実行した後にフレームを増分し、ステップ１３０４にループバックして次のフレームについて動作パラメータを計算する。
動作推定
スプライト生成方法における主要ステップの１つに、動作モデルを使用して現在のビデオオブジェクトのグローバル動作パラメータを計算するステップがある。本出願人等の実施態様では、グローバル動作モデルは２Ｄ平面透視変換に基づいている。この透視変換は、１つの画像、すなわち現在のビデオオブジェクトを、別の画像、すなわち前に構築されたスプライトまたはビデオオブジェクトにマップする。
考慮中の２つの画像を、Ｉ（ｘ，ｙ，ｗ）およびＩ′（ｘ′，ｙ′，ｗ′）と仮定する。同次座標を使用すると、２Ｄ平面透視変換は次式のように表すことができる。
0004572010.tif 000007
ここで（ｘ，ｙ，ｗ）は第１画像Ｉにあるピクセルの同次座標で、（ｘ′，ｙ′，ｗ′）は第２画像Ｉ′にある対応するピクセルの同次座標であり、
0004572010.tif 000008
は透視変換を表す動作パラメータのマトリックスである。動作パラメータはワーピング係数または動作係数と呼ばれることがある。
２Ｄ透視変換の式は、次式のように表すことができる。
0004572010.tif 000009
ここでワープ済み座標は第１画像Ｉにある座標の関数として表される。
動作パラメータを計算する目的は、第１画像Ｉのピクセル値と第２画像Ｉ′の対応するピクセル値との間の誤差を最小限にする、１組の動作パラメータを探すことである。座標（ｘ，ｙ）に配置されている第１画像Ｉ内にある各ピクセルの場合、第２画像Ｉ′内にある対応するピクセルは（ｘ′，ｙ′）に配置されている。
本実施態様における動作推定構成要素の目的は、第１画像および第２画像内にあるピクセルｉの対応するすべての対に関して、強度誤差の２乗和を最小限にすることである。オフライン静的スプライトの場合、第１画像Ｉは現在のフレーム用のビデオオブジェクトであり、第２画像Ｉ′は前のフレームのビデオオブジェクトから構築されたスプライト（前に構築されたスプライト）である。オンライン動的スプライトの場合、第１画像Ｉは現在のフレーム用のビデオオブジェクトであり、第２画像Ｉ′は前のフレーム用に構築されたビデオオブジェクト（前に構築されたビデオオブジェクト）である。
スプライトおよびビデオオブジェクトは、どちらもその形状を定義するマスクを有する。形状は、ビデオオブジェクトまたはスプライトなどの非矩形オブジェクトの境界（輪郭とも呼ばれる）を定義する。誤差を最小限にする問題は、第１画像内のピクセルが第１画像のマスク内にあり、第２画像内の対応するピクセルが第２画像のマスク内にある場合に限られている。これを達成するために、最小化ルーチンは、（ｘ，ｙ）がのマスクＩ内にあり、（ｘ′，ｙ′）がのマスクＩ′内にある場合、重み付けパラメータｗiを１に設定する。
したがって、この重み付けパラメータを使用して、ビデオオブジェクト内のピクセルと対応するスプライト内のピクセルとの間の２乗和誤差は、次式のように表すことができる。
0004572010.tif 000010
ここでｗiは重み付けパラメータ、Ｉ（ｘi，ｙi）は現在のビデオオブジェクト内でｉ番目のピクセル、Ｉ′（ｘ′i，ｙ′i）は前に構築されたスプライト（動的スプライトの場合はビデオオブジェクト）内の対応するピクセルである。
いくつかの標準最小化アルゴリズムを使用して、この最小化問題を解決することができる。一実施態様では、レベンバーグ（Ｌｅｖｅｎｂｅｒｇ）−マルカルト反復非線形最小化アルゴリズムを使用して最小化を実行する。このアルゴリズムでは、未知の動作パラメータ｛ｍ0，．．．，ｍ7｝に関してｅiの偏導関数を計算する。たとえば次式のようになる。
0004572010.tif 000011
ここでＤｉは分母である。アルゴリズムはこれらの偏導関数から、次式の構成要素を使って、ヘッシアンマトリックスＡおよび重み付け勾配ベクトルｂを概算する。
0004572010.tif 000012
次いで数量Δｍ＝Ａ-1ｂにより、動作パラメータ推定ｍを更新する。
図３３は、グローバル動作推定方法の実施態様を示す流れ図である。グローバル推定方法には、１）ビデオオブジェクト内の各ピクセルｉについて、ビデオオブジェクト内の各ピクセルの、ヘッシアンマトリックスＡおよび勾配ベクトルｂに対する寄与を計算するステップ（ステップ１３３０〜１３４０）と、２）ヘッシアンマトリックスおよび勾配ベクトルの現在値に基づいてΔｍを解き、動作係数を更新するステップ（ステップ１３４２〜１３４８）という、２つの主要な構成要素がある。これらの２つの部分を何回か反復することで動作係数を純化し、ビデオオブジェクトのピクセルと対応するスプライトのピクセルとの間の強度誤差を最小化することができる。
位置（ｘi，ｙi）にあるマスク内部の各ピクセルｉ（ステップ１３３０）の場合、この方法は、動作係数の現在値を使用して位置（ｘi，ｙi）をワープすることで、スプライト内の対応する位置（ｘ′i，ｙ′i）を計算する。前述のように、この方法は前のフレームから起点として動作係数を使用する。グローバル動作推定方法は、各反復を利用して動作係数を純化する。
現在の動作係数を使用してピクセルの位置をワープした後、この方法は、対応する位置（ｘ′i，ｙ′i）がスプライトのマスク内にあるかどうかを判定する（１３３４）。マスク内にない場合は、次のピクセル（１３３４）に進む。
対応する位置（ｘ′i，ｙ′i）がスプライトのマスク内にある場合、この方法は（ｘi，ｙi）位置のピクセル値と（ｘ′i，ｙ′i）位置のピクセル値との間の誤差ｅiを計算する（１３３６）。次に、それぞれの動作係数ｍk（ｋ＝０，１，２，．．．８）に関して、ｅiの偏導関数を計算する（１３３８）。この方法は最後に、ステップ１３３６および１３３８で計算した偏導関数および誤差値に基づいて、ピクセルのＡおよびｂに対する寄与を追加する。
いったんこの方法で各ピクセルのＡおよびｂに対する寄与を計算すると、次いで、式ＡΔｍ＝ｂの体系を解き、ステップ１３４２および１３４４に示すように、動作パラメータｍt+1＝ｍt＋Δｍを更新する。次いでこの方法は、次の反復に対してプロセス全体を繰り返す（１３４６）。動作係数を純化するために、この方法は固定数のステップｔ、たとえばｔ＝８に対して、上記プロセスを繰り返す。
動作パラメータを使用したビデオオブジェクトのワープ
動作パラメータがいったん取得されると、スプライト生成方法は現在のビデオオブジェクトを前に構築されたスプライトにワープする。図３０は、各フレームからのビデオオブジェクトＩiが、前に構築されたスプライトＳi-1にどのようにワープされるかを例示した図である。
ビデオオブジェクトと前に構築されたスプライトとの混合
ビデオシーケンス内の新しい各フレームを使用して、現在のワープ済みビデオオブジェクトと前のフレームから構築されたスプライトとを混合することにより、スプライトが更新される。これら２つの画像を混合する従来の方法の１つは、現在のワープ済みビデオオブジェクトとスプライトとの平均値を出す方法である。ただし、平均値を出す方法は、現在のビデオオブジェクトに重みをかけすぎる傾向がある。したがって、それぞれの画像の雑音が、スプライトの最終品質に影響を与える可能性がある。この問題を解決するために、本出願人等の実施態様では、丸め平均値方法を使用して、現在のワープ済みビデオオブジェクトとスプライトとを混合する。
ビデオシーケンスにｎ個のフレームが含まれ、各フレームが現在の、フレームＷi、ｉ＝０，１，．．．，ｎ−１のワープ済み画像を表すワープ済み画像を有すると仮定する。スプライトＳkは、Ｗi、ｉ＝０，１，．．．，ｋ−１を使用して生成される。最終スプライトはＳnである。この最終スプライトは、次式のように、各フレームのワープ済みビデオオブジェクトから同等の寄与を受けるものであることが好ましい。
Ｓn＝（Ｗ0＋．．．＋Ｗn-1）／ｎ
本出願人等の実施態様は、登録済み画像を前のスプライトに向かって増分的に混合し、それぞれの画像に等しく重み付けをしながら、現在のスプライトを取得する。
この実施態様が各ワープ済みビデオオブジェクトとスプライトをどのように増分的に混合するかを示した式は、次式のように表される。
Ｓi＝（ｉ*Ｓi-1＋Ｗi）／（ｉ＋１）
本出願人等のスプライトを生成する方法には、いくつかの利点がある。第１に、現在のビデオオブジェクトおよびスプライトのマスクを使用して、スプライト内部のピクセルにワープするビデオオブジェクト内にあるピクセルだけを基にして、動作係数が計算されることを保証する。もう１つの利点は、現在のフレーム内にあるビデオオブジェクトの動作を推定するために、起点として前のフレームから動作係数を使用することである。これにより、動作推定プロセスの効率がよくなり、より正確な動作パラメータが提供される傾向がある。さらに別の利点は、この方法が丸め平均値を使用してビデオオブジェクトとスプライトまたは基準オブジェクトとを混合することである。具体的に言えば、この方法は、各ビデオオブジェクトが最終スプライトに対してほぼ等しく寄与することを保証するために、スプライトに混合するビデオオブジェクトの数に比例してスプライトを重み付けすることによって、スプライト（または基準オブジェクト）を増分的に更新する。この混合形式により、スプライト内の各フレームのビデオオブジェクトに与える雑音の影響を少なくする。
以上、特定のビデオ符号化技法に関連して本出願人等のスプライト生成方法を記載してきたが、本発明を前述の符号化方法に限定することを意図するものではない。本明細書全体を通じて述べたように、スプライト生成方法は、オフライン静的スプライトを生成するためのスタンドアロンモジュールとして、ならびにオンライン動的スプライトを生成するための符号器および復号器の一部として使用することができる。スプライト生成方法は、１組のソフトウェア命令として実装して汎用コンピュータで実行する、デジタルビデオ符号器／復号器のような特殊な用途の論理ハードウェア内で実装する、あるいはソフトウェア構成要素およびハードウェア構成要素の組み合わせとして実装することができる。
本発明の原理が適用できる多くの可能な実施形態に鑑みて、前述の実施態様は本発明を例示的に示しただけであり、本発明の範囲を限定すべきものではないことを理解されたい。正確に言えば、本発明の範囲は以下の請求項によって定義される。したがって、本発明を、以下の請求の範囲および精神を逸脱することのないものとしてここに請求する。
【図１】
0004572010.tif 000013
【図２Ａ】
0004572010.tif 000014
【図２Ｂ】
0004572010.tif 000015
【図３Ａ】
0004572010.tif 000016
【図４】
0004572010.tif 000017
【図５Ａ】
0004572010.tif 000018
【図５Ｂ】
0004572010.tif 000019
【図６】
0004572010.tif 000020
【図７Ａ】
0004572010.tif 000021
【図７Ｂ】
0004572010.tif 000022
【図８】
0004572010.tif 000023
【図９Ａ】
0004572010.tif 000024
【図９Ｂ】
0004572010.tif 000025
【図９Ｃ】
0004572010.tif 000026
【図９Ｄ】
0004572010.tif 000027
【図９Ｅ】
0004572010.tif 000028
【図９Ｆ】
0004572010.tif 000029
【図９Ｇ】
0004572010.tif 000030
【図１０Ａ】
0004572010.tif 000031
【図１０Ｂ】
0004572010.tif 000032
【図１０Ｃ】
0004572010.tif 000033
【図１０Ｄ】
0004572010.tif 000034
【図１０Ｅ】
0004572010.tif 000035
【図１０Ｆ】
0004572010.tif 000036
【図１１Ａ】
0004572010.tif 000037
【図１１Ｂ】
0004572010.tif 000038
【図１１Ｃ】
0004572010.tif 000039
【図１１Ｄ】
0004572010.tif 000040
【図１１Ｅ】
0004572010.tif 000041
【図１１Ｆ】
0004572010.tif 000042
【図１２】
0004572010.tif 000043
【図１４】
0004572010.tif 000044
【図１５】
0004572010.tif 000045
【図１３】
0004572010.tif 000046
【図１６】
0004572010.tif 000047
【図１７Ａ】
0004572010.tif 000048
【図１７Ｂ】
0004572010.tif 000049
【図１８Ａ】
0004572010.tif 000050
【図１８Ｂ】
0004572010.tif 000051
【図１８Ｃ】
0004572010.tif 000052
【図１８Ｄ】
0004572010.tif 000053
【図１９Ａ】
0004572010.tif 000054
【図１９Ｂ】
0004572010.tif 000055
【図２１】
0004572010.tif 000056
【図２２】
0004572010.tif 000057
【図２３Ａ】
0004572010.tif 000058
【図３Ｂ】
0004572010.tif 000059
【図２０Ａ】
0004572010.tif 000060
【図２０Ｂ】
0004572010.tif 000061
【図２０Ｃ】
0004572010.tif 000062
【図２０Ｄ】
0004572010.tif 000063
【図２３Ｂ】
0004572010.tif 000064
【図２５Ａ】
0004572010.tif 000065
【図２４Ａ】
0004572010.tif 000066
【図２４Ｂ】
0004572010.tif 000067
【図２５Ｂ】
0004572010.tif 000068
【図２５Ｃ】
0004572010.tif 000069
【図２６】
0004572010.tif 000070
【図２７Ａ】
0004572010.tif 000071
【図２７Ｂ】
0004572010.tif 000072
【図２８】
0004572010.tif 000073
【図２９】
0004572010.tif 000074
【図３０】
0004572010.tif 000075
【図３１】
0004572010.tif 000076
【図３２】
0004572010.tif 000077
【図３３】
0004572010.tif 000078