(57)【要約】  動き補償ビデオ圧縮システムにおいて動きベクトルを決定するための方法、システムおよびコンピュータプログラム。一側面では、複数の高速動き推定法を１組のビデオ画像に適用し、圧縮で用いるために選択した全ての一致から最良の結果を得る。ＡＣおよびＤＣ両方の動きベクトル一致基準が適用できる。これらの方法により共通に用いられるフルピクセル探索に加えて、サブピクセル探索も、ＡＣおよびＤＣ両方の一致基準を用いて、動きベクトル候補毎に実行できる。更に、フルピクセルおよびサブピクセル高速探索のハイブリッドな組み合わせを用いることもできる。本発明の他の側面には、動き補償システムにおいて動きベクトルを決定するためにＡＣ一致を用いること；ＡＣ一致とＤＣ一致の比較、および動き補償圧縮で用いるための最良一致の選択；最良一致（ＡＣまたはＤＣ）を用いて広いダイナミックレンジおよび広いコントラストレンジの画像の動きベクトル決定を改良すること；およびＡＣ一致プロセスにおけるＡＣ周波数成分をスケーリング（増加／減少）することが含まれる。
2005516433.tif 000002
【特許請求の範囲】
【請求項１】
動き補償ビデオ圧縮システムにおける動き推定のための方法であって、
（ａ）少なくとも２つの高速動き推定探索法を１組のビデオ画像に適用するとともに、各探索法に対する最良一致動きベクトル候補を選択するステップと、
（ｂ）前記最良一致動きベクトル候補から最良の動きベクトルを選択するステップと、
（ｃ）前記最良一致動きベクトルを適用して、前記１組のビデオ画像を圧縮するステップとを含む方法。
【請求項２】
各探索法に対する最良一致動きベクトル候補を選択するステップは、
（ａ）ＡＣ一致基準を適用して、ＡＣ最良一致動きベクトルを決定するステップと、
（ｂ）ＤＣ一致基準を適用して、ＤＣ最良一致動きベクトルを決定するステップと、
（ｃ）前記ＡＣ最良一致動きベクトルと前記ＤＣ最良一致動きベクトルのうち、より良好な一致を選択して、前記探索法に対する前記最良一致動きベクトル候補とするステップとを含む請求項１の方法。
【請求項３】
各高速動き推定探索法をサブピクセルに適用する請求項１の方法。
【請求項４】
各高速動き推定探索法をフルピクセルに適用する請求項１の方法。
【請求項５】
更に、
（ａ）前記最良の動きベクトルに基づいて、前記１組のビデオ画像にサブピクセル動き探索を実行して、１組のサブピクセル動きベクトルを生成するステップと、
（ｂ）前記最良一致動きベクトルとして、前記１組のサブピクセル動きベクトルから前記最良の動きベクトルを選択するステップとを含む請求項４の方法。
【請求項６】
前記最良一致動きベクトルを選択するステップは、
（ａ）ＡＣ一致基準を前記１組のサブピクセル動きベクトルに適用して、ＡＣ最良一致サブピクセル動きベクトルを決定するステップと、
（ｂ）ＤＣ一致基準を前記１組のサブピクセル動きベクトルに適用して、ＤＣ最良一致サブピクセル動きベクトルを決定するステップと、
（ｃ）前記ＡＣ最良一致サブピクセル動きベクトルと前記ＤＣ最良一致サブピクセル動きベクトルのうち、より良好な一致を選択して、前記最良一致動きベクトルとするステップとを含む請求項５の方法。
【請求項７】
更に、
（ａ）各高速動き推定探索法に対する前記最良の動きベクトルに基づいて、前記１組のビデオ画像に１組のサブピクセル動き探索を実行して、各高速動き推定探索法に対する１組のサブピクセル動きベクトルを生成するステップと、
（ｂ）各高速動き推定探索法に対する各１組のサブピクセル動きベクトルから、最良一致サブピクセル動きベクトルを選択するステップと、
（ｃ）前記最良一致動きベクトルとして、前記最良一致サブピクセル動きベクトルから前記最良の動きベクトルを選択するステップとを含む請求項１の方法。
【請求項８】
最良一致を選択するステップは、
（ａ）ＡＣ一致基準を適用して、ＡＣ最良一致を決定するステップと、
（ｂ）ＤＣ一致基準を適用して、ＤＣ最良一致を決定するステップとを含む請求項７の方法。
【請求項９】
動き補償ビデオ圧縮システムにおいて、１組のビデオ画像に対する動きベクトル決定の質を決定するための方法であって、前記１組のビデオ画像に対する最良一致動きベクトル候補を決定する際に、ＡＣ一致アルゴリズムを適用するステップを含む方法。
【請求項１０】
動き補償ビデオ圧縮システムにおいて、１組のビデオ画像に対する動きベクトル決定の質を決定するための方法であって、
（ａ）前記１組のビデオ画像に対する最良一致ＡＣ動きベクトル候補を決定する際に、ＡＣ一致アルゴリズムを適用するステップと、
（ｂ）前記１組のビデオ画像に対する最良一致ＤＣ動きベクトル候補を決定する際に、ＤＣ一致アルゴリズムを適用するステップと、
（ｃ）最良一致として、前記最良一致ＡＣ動きベクトル候補と前記最良一致ＤＣ動きベクトル候補のうち、より良好な一致を選択するステップとを含む方法。
【請求項１１】
更に、広いダイナミックレンジおよび広いコントラストレンジの画像に対する動きベクトルを決定する際に、前記ＡＣ一致アルゴリズムを優先的に選択するステップを含む請求項１０の方法。
【請求項１２】
更に、変化するコントラストを有する画像に対する動きベクトルを決定する際に、前記ＤＣ一致アルゴリズムを優先的に選択するステップを含む請求項１０の方法。
【請求項１３】
前記ＡＣ一致アルゴリズムが周波数成分を有し、更に、前記ＡＣ一致アルゴリズムを適用して最良一致を見つける間に、前記周波数成分をスケーリングするステップを含む請求項１０の方法。
【請求項１４】
前記ＤＣ一致アルゴリズムは、少なくともＲＧＢ差の一致を用いる請求項１０の方法。
【請求項１５】
前記ＤＣ一致アルゴリズムは、少なくとも輝度の一致を用いる請求項１０の方法。
【請求項１６】
更に、前記最良一致の種類を後続の符号化処理へ送るステップを含む請求項１０の方法。
【請求項１７】
動き補償ビデオ圧縮システムにおける動き推定のためのコンピュータ可読な媒体上に記憶されたコンピュータプログラムであって、
（ａ）少なくとも２つの高速動き推定探索コンピュータプログラムを１組のビデオ画像に適用するとともに、各探索コンピュータプログラムに対する最良一致動きベクトル候補を選択することと、
（ｂ）前記最良一致動きベクトル候補から最良の動きベクトルを選択することと、
（ｃ）前記最良一致動きベクトルを適用して、前記１組のビデオ画像を圧縮することとをコンピュータに実行させるための命令を備えるコンピュータプログラム。
【請求項１８】
各探索コンピュータプログラムに対する最良一致動きベクトル候補を選択することを前記コンピュータに実行させるための前記命令は、
（ａ）ＡＣ一致基準を適用して、ＡＣ最良一致動きベクトルを決定することと、
（ｂ）ＤＣ一致基準を適用して、ＤＣ最良一致動きベクトルを決定することと、
（ｃ）前記ＡＣ最良一致動きベクトルと前記ＤＣ最良一致動きベクトルのうち、より良好な一致を選択して、前記探索コンピュータプログラムに対する前記最良一致動きベクトル候補とすることとを前記コンピュータに実行させるための命令を含む請求項１７のコンピュータプログラム。
【請求項１９】
各高速動き推定探索法をサブピクセルに適用する請求項１７のコンピュータプログラム。
【請求項２０】
各高速動き推定探索法をフルピクセルに適用する請求項１７のコンピュータプログラム。
【請求項２１】
更に、
（ａ）前記最良の動きベクトルに基づいて、前記１組のビデオ画像にサブピクセル動き探索を実行して、１組のサブピクセル動きベクトルを生成することと、
（ｂ）前記最良一致動きベクトルとして、前記１組のサブピクセル動きベクトルから前記最良の動きベクトルを選択することとをコンピュータに実行させるための命令を含む請求項２０のコンピュータプログラム。
【請求項２２】
前記最良一致動きベクトルを選択することを前記コンピュータに実行させるための前記命令は、
（ａ）ＡＣ一致基準を前記１組のサブピクセル動きベクトルに適用して、ＡＣ最良一致サブピクセル動きベクトルを決定することと、
（ｂ）ＤＣ一致基準を前記１組のサブピクセル動きベクトルに適用して、ＤＣ最良一致サブピクセル動きベクトルを決定することと、
（ｃ）前記ＡＣ最良一致サブピクセル動きベクトルと前記ＤＣ最良一致サブピクセル動きベクトルのうち、より良好な一致を選択して、前記最良一致動きベクトルとすることとを前記コンピュータに実行させるための命令を含む請求項２１のコンピュータプログラム。
【請求項２３】
更に、
（ａ）各高速動き推定探索コンピュータプログラムに対する前記最良の動きベクトルに基づいて、前記１組のビデオ画像に１組のサブピクセル動き探索を実行して、各高速動き推定探索コンピュータプログラムに対する１組のサブピクセル動きベクトルを生成することと、
（ｂ）各高速動き推定探索コンピュータプログラムに対する各１組のサブピクセル動きベクトルから、最良一致サブピクセル動きベクトルを選択することと、
（ｃ）前記最良一致動きベクトルとして、前記最良一致サブピクセル動きベクトルから前記最良の動きベクトルを選択することとをコンピュータに実行させるための命令を含む請求項１７のコンピュータプログラム。
【請求項２４】
最良一致を選択することを前記コンピュータに実行させるための前記命令は、
（ａ）ＡＣ一致基準を適用して、ＡＣ最良一致を決定することと、
（ｂ）ＤＣ一致基準を適用して、ＤＣ最良一致を決定することとを前記コンピュータに実行させるための命令を含む請求項２３のコンピュータプログラム。
【請求項２５】
動き補償ビデオ圧縮システムにおいて、１組のビデオ画像に対する動きベクトル決定の質を決定するためのコンピュータ可読な媒体上に記憶されたコンピュータプログラムであって、前記１組のビデオ画像に対する最良一致動きベクトル候補を決定する際に、ＡＣ一致アルゴリズムを適用することをコンピュータに実行させるための命令を備えるコンピュータプログラム。
【請求項２６】
動き補償ビデオ圧縮システムにおいて、１組のビデオ画像に対する動きベクトル決定の質を決定するためのコンピュータ可読な媒体上に記憶されたコンピュータプログラムであって、
（ａ）前記１組のビデオ画像に対する最良一致ＡＣ動きベクトル候補を決定する際に、ＡＣ一致アルゴリズムを適用することと、
（ｂ）前記１組のビデオ画像に対する最良一致ＤＣ動きベクトル候補を決定する際に、ＤＣ一致アルゴリズムを適用することと、
（ｃ）最良一致として、前記最良一致ＡＣ動きベクトル候補と前記最良一致ＤＣ動きベクトル候補のうち、より良好な一致を選択することとをコンピュータに実行させるための命令を備えるコンピュータプログラム。
【請求項２７】
更に、広いダイナミックレンジおよび広いコントラストレンジの画像に対する動きベクトルを決定する際に、前記ＡＣ一致アルゴリズムを優先的に選択することをコンピュータに実行させるための命令を含む請求項２２のコンピュータプログラム。
【請求項２８】
更に、変化するコントラストを有する画像に対する動きベクトルを決定する際に、前記ＤＣ一致アルゴリズムを優先的に選択することをコンピュータに実行させるための命令を含む請求項２２のコンピュータプログラム。
【請求項２９】
前記ＡＣ一致アルゴリズムが周波数成分を有し、更に、前記ＡＣ一致アルゴリズムを適用して最良一致を見つける間に、前記周波数成分をスケーリングすることをコンピュータに実行させるための命令を含む請求項２２のコンピュータプログラム。
【請求項３０】
前記ＤＣ一致アルゴリズムは、少なくともＲＧＢ差の一致を用いる請求項２２のコンピュータプログラム。
【請求項３１】
前記ＤＣ一致アルゴリズムは、少なくとも輝度の一致を用いる請求項２のコンピュータプログラム。
【請求項３２】
更に、前記最良一致の種類を後続の符号化処理へ送ることをコンピュータに実行させるための命令を含む請求項２２のコンピュータプログラム。
【請求項３３】
動き補償ビデオ圧縮システムにおける動き推定のためのシステムであって、
（ａ）少なくとも２つの高速動き推定探索法を１組のビデオ画像に適用するとともに、前記各探索法に対する最良一致動きベクトル候補を選択する手段と、
（ｂ）前記最良一致動きベクトル候補から最良の動きベクトルを選択する手段と、
（ｃ）前記最良一致動きベクトルを適用して、前記１組のビデオ画像を圧縮する手段とを含むシステム。
【請求項３４】
各探索法に対する最良一致動きベクトル候補を選択する手段は、
（ａ）ＡＣ一致基準を適用して、ＡＣ最良一致動きベクトルを決定する手段と、
（ｂ）ＤＣ一致基準を適用して、ＤＣ最良一致動きベクトルを決定する手段と、
（ｃ）前記ＡＣ最良一致動きベクトルと前記ＤＣ最良一致動きベクトルのうち、より良好な一致を選択して、前記探索法に対する前記最良一致動きベクトル候補とする手段とを含む請求項３３のシステム。
【請求項３５】
各高速動き推定探索法をサブピクセルに適用する請求項３３のシステム。
【請求項３６】
各高速動き推定探索法をフルピクセルに適用する請求項３３のシステム。
【請求項３７】
更に、
（ａ）前記最良の動きベクトルに基づいて、前記１組のビデオ画像にサブピクセル動き探索を実行して、１組のサブピクセル動きベクトルを生成する手段と、
（ｂ）前記最良一致動きベクトルとして、前記１組のサブピクセル動きベクトルから前記最良の動きベクトルを選択する手段とを含む請求項３６のシステム。
【請求項３８】
前記最良一致動きベクトルを選択する手段は、
（ａ）ＡＣ一致基準を前記１組のサブピクセル動きベクトルに適用して、ＡＣ最良一致サブピクセル動きベクトルを決定する手段と、
（ｂ）ＤＣ一致基準を前記１組のサブピクセル動きベクトルに適用して、ＤＣ最良一致サブピクセル動きベクトルを決定する手段と、
（ｃ）前記ＡＣ最良一致サブピクセル動きベクトルと前記ＤＣ最良一致サブピクセル動きベクトルのうち、より良好な一致を選択して、前記最良一致動きベクトルとする手段とを含む請求項３７のシステム。
【請求項３９】
更に、
（ａ）各高速動き推定探索法に対する前記最良の動きベクトルに基づいて、前記１組のビデオ画像に１組のサブピクセル動き探索を実行して、各高速動き推定探索法に対する１組のサブピクセル動きベクトルを生成する手段と、
（ｂ）各高速動き推定探索法に対する各１組のサブピクセル動きベクトルから、最良一致サブピクセル動きベクトルを選択する手段と、
（ｃ）前記最良一致動きベクトルとして、前記最良一致サブピクセル動きベクトルから前記最良の動きベクトルを選択する手段とを含む請求項３３のシステム。
【請求項４０】
最良一致を選択する手段は、
（ａ）ＡＣ一致基準を適用して、ＡＣ最良一致を決定する手段と、
（ｂ）ＤＣ一致基準を適用して、ＤＣ最良一致を決定する手段とを含む請求項３９のシステム。
【請求項４１】
動き補償ビデオ圧縮システムにおいて、１組のビデオ画像に対する動きベクトル決定の質を決定するためのシステムであって、
（ａ）前記１組のビデオ画像を入力する手段と、
（ｂ）前記１組のビデオ画像に対する最良一致動きベクトル候補を決定する際に、ＡＣ一致アルゴリズムを適用する手段とを含むシステム。
【請求項４２】
動き補償ビデオ圧縮システムにおいて、１組のビデオ画像に対する動きベクトル決定の質を決定するためのシステムであって、
（ａ）前記１組のビデオ画像に対する最良一致ＡＣ動きベクトル候補を決定する際に、ＡＣ一致アルゴリズムを適用する手段と、
（ｂ）前記１組のビデオ画像に対する最良一致ＤＣ動きベクトル候補を決定する際に、ＤＣ一致アルゴリズムを適用する手段と、
（ｃ）最良一致として、前記最良一致ＡＣ動きベクトル候補と前記最良一致ＤＣ動きベクトル候補のうち、より良好な一致を選択する手段とを含むシステム。
【請求項４３】
更に、広いダイナミックレンジおよび広いコントラストレンジの画像に対する動きベクトルを決定する際に、前記ＡＣ一致アルゴリズムを優先的に選択する手段を含む請求項４２のシステム。
【請求項４４】
更に、変化するコントラストを有する画像に対する動きベクトルを決定する際に、前記ＤＣ一致アルゴリズムを優先的に選択する手段を含む請求項４２のシステム。
【請求項４５】
前記ＡＣ一致アルゴリズムが周波数成分を有し、更に、前記ＡＣ一致アルゴリズムを適用して最良一致を見つける間に、前記周波数成分をスケーリングする手段を含む請求項４２のシステム。
【請求項４６】
前記ＤＣ一致アルゴリズムは、少なくともＲＧＢ差の一致を用いる請求項４２のシステム。
【請求項４７】
前記ＤＣ一致アルゴリズムは、少なくとも輝度の一致を用いる請求項４６のシステム。
【請求項４８】
更に、前記最良一致の種類を後続の符号化処理へ送る手段を含む請求項４２のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はビデオ圧縮に関し、詳細には、ＭＰＥＧ等のビデオ圧縮システムの動き推定に関する。
【背景技術】
【０００２】
ＭＰＥＧの背景
ＭＰＥＧ−２およびＭＰＥＧ−４は、画像シーケンスをよりコンパクトな符号化データの形で表わす効率的な方法を提供するビデオシンタックスを定義する国際ビデオ圧縮標準規格である。符号化ビットの言語は、「シンタックス」である。例えば、僅かなトークンでサンプルの全ブロックを表すことができる（例えば、ＭＰＥＧ−２では６４サンプル）。両方のＭＰＥＧ標準規格には、復号化（再構成）処理も記述されており、符号化ビットを、コンパクトな表現から元のフォーマットの近似画像シーケンスへ写像する。例えば、符号化ビットストリーム内のフラグは、後続のビットを、離散コサイン変換（ＤＣＴ）アルゴリズムで復号化する前に、予測アルゴリズムで先に処理すべきかどうかを知らせる。復号化処理を含むアルゴリズムは、これらのＭＰＥＧ標準規格により定義されているセマンティックスにより規定されている。このシンタックスは、空間冗長性、時間冗長性、一様な動き、空間マスキング等の共通のビデオ特性を活用するように適用され得る。実際、これらＭＰＥＧ標準規格は、データフォーマットはもとよりプログラミング言語も定義している。ＭＰＥＧデコーダは、入力されるデータストリームを解析し、復号化できなければならないが、データストリームが対応するＭＰＥＧシンタックスに準拠している限り、広く多様な可能なデータ構造および圧縮技法を用いることができる（セマンティックスが整合性をもたないために、技術的には標準規格から逸脱することはあるが）。代替シンタックス内に必要なセマンティックスを持つことも可能である。
【０００３】
これらＭＰＥＧ標準規格は、イントラフレーム（フレーム内）およびインターフレーム（フレーム間）法を含む多様な圧縮法を用いる。ほとんどの映像シーンでは、動きが前景において生じている間、背景は比較的静止したままである。背景が動くこともあるが、多くのシーンは冗長である。これらＭＰＥＧ標準規格は、「イントラ」フレームまたは「Ｉフレーム」と呼ばれる基準フレームを作成することにより圧縮を開始する。Ｉフレームは、他のフレームを参照せずに圧縮されるので、フレーム全体の映像情報を含んでいる。Ｉフレームは、ランダムアクセスのためのエントリーポイントをデータビットストリームに提供するが、中程度にしか圧縮できない。Ｉフレームを表すデータは、１２から１５フレーム毎にビットストリームに配置されるのが普通である（状況によっては、Ｉフレーム間にもっと広い間隔を設けることも有用である）。従って、基準Ｉフレーム間にあるフレームの僅かな部分だけが、両側を挟むＩフレームと異なるので、その画像の差分だけが捕捉され、圧縮され、そして格納される。２種類のフレームが、かかる差分のために用いられる。すなわち、予測フレームつまりＰフレーム、および双方向補間フレームつまりＢフレームである。
【０００４】
Ｐフレームは、一般に過去のフレーム（Ｉフレームまたは以前のＰフレームのいずれか）を参照して符号化され、一般には後続のＰフレームに参照されて用いられる。Ｐフレームはかなり高い圧縮を受ける。Ｂフレームは、最も高い圧縮量を提供するが、符号化されるために過去と未来の両参照フレームを必要とする。標準圧縮技術で双方向フレームが参照フレームとして用いられることはない。符号化されると、ＭＰＥＧデータビットストリームは、一連のＩ、ＰおよびＢフレームを備える。
【０００５】
マクロブロックは、画像ピクセルからなる領域である。ＭＰＥＧ−２では、マクロブロックは、８×８のＤＣＴブロック４つを集めた１６×１６ピクセルであり、Ｐフレームについては１つの動きベクトル、Ｂフレームについては１つまたは２つの動きベクトルを伴う。Ｐフレーム内のマクロブロックは、イントラフレームまたはインターフレーム（予測フレーム）符号化のいずれかを用いて個別に符号化され得る。Ｂフレーム内のマクロブロックは、イントラフレーム符号化、順方向予測符号化、逆方向予測符号化、または、順方向および逆方向の両方向（すなわち、双方向補間）予測符号化を用いて個別に符号化され得る。僅かに異なってはいるが類似の構造が、ＭＰＥＧ−４ビデオ符号化で用いられている。
【０００６】
動きベクトル予測
ＭＰＥＧ−２およびＭＰＥＧ−４（およびＨ．２６３等の類似の標準規格）では、Ｂ型（双方向予測）フレームの使用が圧縮の効率に有利であることが分かっている。各マクロブロックに対する動きベクトルは、以下の３つの方法のいずれかにより予測できる：
１）以前のＩまたはＰフレームから順方向へ予測する。
２）後続のＩまたはＰフレームから逆方向へ予測する。
３）後続および以前のＩまたはＰフレームの両方から双方向に予測する。
【０００７】
モード１は、Ｐフレームに用いる順方向予測法と同一である。モード２は、後続フレームから逆方向に働くこと以外、同じ考え方である。モード３は、以前および後続のフレームからの情報を組み合わせる補間モードである。
【０００８】
これら３つのモードに加えて、ＭＰＥＧ−４は、第２の補間動きベクトル予測モード、すなわち、後続のＰフレームからの動きベクトルおよびデルタ値を用いる直接モード予測もサポートする。後続のＰフレームの動きベクトルは、以前のＰまたはＩフレームを指し示す。ある比率を用いて後続のＰフレームからの動きベクトルに重み付けをする。その比率は、後続のＰおよび以前のＰ（またはＩ）フレームに対する現在のＢフレームの相対的時間位置である。
【０００９】
動きベクトル探索
動き補償圧縮において動きベクトルを決定する共通の方法は、適切な近似に基づく連続画像のフルピクセル（「フルペル」とも呼ばれる）一致を決定することである。最も一般的な近似法は、低い解像度の画像を探索し、次いで、最良の低解像度一致点について小さく精緻な探索を行う、階層的動き探索を実行することである。
【００１０】
一般に用いられる一致の判断基準は、厳密にＤＣ一致である差の絶対値の合計（Sum of Absolute Difference）（ＳＡＤ）である。フルピクセルのＳＡＤ一致が見つかると、通常、１個から２個のピクセルの小さな探索範囲を有するサブピクセル探索が、上、下、左および右、ならびに対角線で実行される。次いで、細かなサブピクセル探索に対する最良のＳＡＤ一致の値が、ほとんどのシステムで動きベクトルとして用いられる。
【００１１】
ＭＰＥＧ−４では、幾つかの種類の階層的探索が基準エンコーダソフトウエアで実装されている。これらは、「ダイヤモンド探索（diamond search）」、「高速動き推定（fast motion estimation）」、および「改良型高速動き推定（progressive fast motion estimation）」の名称で呼ばれている。これらのアルゴリズムは、完全探索と質を等しくするよう試みる。完全探索（ＭＰＥＧ−２およびＭＰＥＧ−４基準ソフトウエアエンコーダで実装されているような探索）は、総ピクセル探索をするためにピクセル毎に検査を行う。これは探索範囲が広いと著しく低速度になる。
【００１２】
従って、符号化に際しては質をあまり低下させずに、十分な速度を達成することが望まれている。質は、信号対雑音比（ＳＮＲ）の値、および最終出力の目視比較を用いて確認するのが普通である。
【００１３】
解像度階層法に加えて、これらの高速動き推定アルゴリズムの中には、以前のフレームにおける現在位置での動きベクトルを、現在のフレームにおける現在位置での動きベクトルに対する有望な指針として検討するものもある。
【００１４】
しかしながら、すべてのかかる高速動き推定法は、用いる便法の基礎を成す仮定が崩れるという異常な問題に直面する。このような場合、既知の高速動き推定アルゴリズムは、結果的に粗悪な動きベクトルを選択するのが普通である。
【００１５】
本発明はこれらの限界に取り組む。
【発明の開示】
【００１６】
本発明は、動き補償ビデオ圧縮システムにおける動きベクトルを決定するための方法、システムおよびコンピュータプログラムに向けられている。本発明の一側面では、複数の高速動き推定法を１組のビデオ画像に適用し、圧縮で用いるために選択した全ての一致からの最良の結果を得る。本技法は、動きベクトルの質に著しい改善をもたらす。両ＡＣおよびＤＣの動きベクトル一致基準が適用できる。すなわち、動きベクトル探索を２回実行することが有用であり、１回は最良のＤＣ一致（最小ＳＡＤ）を探すこと、そしてもう１回は最良のＡＣ一致を探すことであり、次いで、その結果を比較し、最高性能を持つ一致を選択することである。
【００１７】
これらの方法により共通に用いられるフルピクセル探索に加えて、サブピクセル探索も、ＡＣおよびＤＣ（ＳＡＤ）両方の一致基準を用いて、候補の動きベクトル毎に実行できる。更に、フルピクセルおよびサブピクセルの高速探索のハイブリッドな組み合わせを用いることができる。
【００１８】
本発明の他の側面には、動き補償圧縮システムにおいて動きベクトルを決定するためにＡＣ一致を用いること；ＡＣ一致とＤＣ一致の比較をすること、および動き補償圧縮で用いるための最良一致を選択すること；最良一致（ＡＣまたはＤＣ）を用いて広いダイナミックレンジおよび広いコントラストレンジの画像の動きベクトルの決定法を改良すること；そしてＡＣ一致処理におけるＡＣ周波数成分をスケーリング（増加／減少）することが含まれる。
【００１９】
本発明の１つ以上の実施の形態の詳細を添付図面と以下の説明で述べる。本発明の他の特徴、目的、そして利点は、その説明と図面、および請求の範囲から明らかとなろう。なお、種々の図において同様な要素には同様な参照符号を付する。
【００２０】
詳細な説明
組み合わせ高速動き推定
種々の高速動き推定法はそれぞれ弱点を持っている。しかしながら、１つの高速法の弱点が、別の方法の弱点と同一ではないこともある。事実、複数の高速動き推定法を利用し、次いで、一致の全てから最良の結果を選択することが有利であることが見出されている。この技法は、結果的に動きベクトルの質を著しく改善する。
【００２１】
以下に述べるように、ＡＣ動きベクトル一致は、多くの場合ＤＣ動きベクトル一致よりも良好である。従って、好ましい実施の形態では、各高速動き推定は、ＡＣおよびＤＣ（ＳＡＤ）一致の両方に対して検査される。すなわち、動きベクトル探索を２回実行することが有用であり、１回は最良のＤＣ一致（最小ＳＡＤ）を探すこと、そして、もう１回は最良のＡＣ一致を探すこと、次いで、その結果を比較し、最高性能を有する一致を選択することである。
【００２２】
幾つかの高速探索の選択肢を評価するには、特に、著しく低速度の完全探索と比べて、わずかな追加時間しか必要とされない。例えば、一般的な階層探索、ダイヤモンド探索、高速動き推定探索、および改良型高速動き推定探索をそれぞれ試すことができる。
【００２３】
これらの方法により共通に用いられるフルピクセル探索に加えて、それぞれの動きベクトル候補について、ＡＣおよびＤＣ（ＳＡＤ）両方の一致基準を用いてサブピクセル探索を実行することもできる。
【００２４】
さらに、フルピクセルおよびサブピクセル高速探索のハイブリッドな組み合わせを利用することができる。例えば、より高解像度（２倍または４倍）の画像を探索して、高速探索アルゴリズムから直接サブピクセル結果を提供できる。あるいは、経験的に決定された、サブピクセル精細探索を伴うフルピクセル領域探索の組み合わせは、単独で、または追加の精細探索と共に、サブピクセルの最適一致を直接的に生成できる。
【００２５】
図１は、高速動き推定のための（コンピュータに実装されるであろう）例示的な方法を示すフロー図である。
【００２６】
ステップ１０１：ビデオ画像圧縮システムにおいて、１組のビデオ画像を入力し（例えば、ビデオ画像ストリームから）、その１組のビデオ画像についてフルピクセルレベルで、少なくとも２つの高速動き推定探索法を用い、１つ以上の一致優良性検査（例えば、ＤＣまたはＡＣ一致等）を用いて探索法毎の最良の一致（すなわち、動きベクトル候補）を見つける。
【００２７】
ステップ１０２：フルピクセル動き探索における最良一致上で、最良のサブピクセル一致を見つけるために、１つ以上の一致優良性検査（例えば、ＤＣまたはＡＣ一致等）を用いて、サブピクセル動き探索を実行する。
【００２８】
ステップ１０３：１つ以上の他の高速動き推定探索法の最良一致上で、サブピクセル動き探索を実行し、１つ以上の一致優良性検査（例えば、ＤＣまたはＡＣ一致等）を用いて、推定法毎にサブピクセルレベルでの最良一致を決定する。
【００２９】
ステップ１０４：最良の全体一致を選択する。
【００３０】
ステップ１０５：動き補償圧縮において最良一致の動きベクトルを用いる。
【００３１】
サブピクセル精度が不要な場合、ステップ１０２〜１０３は省略してもよい。また、フルピクセル探索に代えてサブピクセル動きベクトル探索だけを実行してもよい。
【００３２】
動きベクトルを決定するためのＡＣ一致の使用
上記のように、ＭＰＥＧ−２およびＭＰＥＧ−４の現行基準の実装は、差の絶対値の合計（Sum of Absolute Difference）（ＳＡＤ）アルゴリズムの形でＤＣ一致のみを利用する。しかしながら、多くの場合、ＡＣ一致を用いる方が良好であり、その場合、ＤＣの違いは無視される。例えば、フェードしている間、または照度が変化する下では、最良のＳＡＤ  ＤＣ一致は、その場面で関係のない点を見つけてしまうので、最良のＳＡＤ  ＤＣ一致を見つけ出すよりも、ＡＣ一致を用いて実際の対象を一致させ、ＤＣの変化を符号化する方がよい。
【００３３】
Ｂフレームは、以前および後続のフレームの比率を利用して予測され、フェードのようなＤＣ変化は自動的に予測される。Ｐフレームでは、ＤＣの差は、単一項として符号化され、多くのＡＣ項を含む差よりもずっと効率的に調整できる（本出願と同時に出願され、本発明の譲受人へ譲渡された「ビデオ圧縮フレームの改良補間法」（"Improved Interpolation of Video
Compression Frames”）と題する係属中の米国特許第０９／９０４，２０３号を参照のこと。フレーム補間に関する追加情報として引用して本明細書に組み込む。）。
【００３４】
「動き補償およびフレームレート変換のためのシステムおよび方法」（"System and Method for Motion
Compensation and Frame Rate Conversion”）と題する係属中の米国特許出願第０９／４３５，２７７号（本発明の譲受人へ譲渡され、引用して本明細書に組み込む。）は、動き補償およびフレームレート変換の両方において最良のＡＣ一致はもとより、最良のＤＣ一致を考慮することの利点について論じている。本発明はこれらの類似の考え方を圧縮に応用する。具体的には、本発明の一側面は、圧縮中の最良の動きベクトルを見つける際に、ＡＣ一致がＤＣ一致より適切であるかどうかを判断することも好ましいことであるという認識に、ある程度基づいている。次節では、両一致を計算するための技法を説明する。
【００３５】
種々の技法を用いて最良のＡＣ一致と最良のＤＣ一致のどちらかに決定できる。例えば、各予測ベクトル（ＤＣ最良一致ベクトルおよびＡＣ最良一致ベクトル）を用いて生成されるビット数を比較し、所与の量子化値に対して、最小ビット数を生成するベクトルが選択できる。ＡＣ相関値（最高の相関を探す）およびＤＣ  ＳＡＤ値（最小差を探す）について、２つの値の一方の逆数を用いて単純比較できる。
【００３６】
ダイナミックレンジが拡張される場合（例えば、「ビデオ画像の高精度符号化および復号化」（"High Precision Encoding and
Decoding of Video Images”）と題する係属中の米国特許出願第０９／７９８，３４６号を参照のこと。本発明の譲受人へ譲渡され、引用して本明細書に組み込む。）、太陽が雲から現れる場合のように照度に変化があり得、この場合、ＡＣ一致はＤＣ一致より適切である。また、低コントラスト圧縮符号化をもたらす、明るい雲または霞に入ったり出たりする飛行機は、全体的にＤＣ値が変化するだろうから、飛行機自体のＡＣ一致は、より良い動きベクトル予測子となる。その代わりに、コントラストが変化し、明るさは変化しないという場合に、ＤＣ一致はより良好に動作する。
【００３７】
拡張されたダイナミックレンジまたは低コントラスト符号化を用いる場合、ＡＣ値とは別の方法論でＤＣ値を符号化するのが適切である。これはＭＰＥＧ−４で既に実装されている。しかしながら、それに加えて、ＡＣ係数に対する量子化パラメータ（ＱＰ）の値と異なる値を、ＤＣ係数に対して用いることが望ましいであろう。変化している雲の中の低コントラストの対象は、雲の平均灰色値固有のＤＣ変化より、少ししかコントラストを変えない。かかる場合、対数表現では低コントラストのほぼ同じ範囲のままである低コントラストの画像の飛行機自体よりも、雲の間や雲を通る陽光によって、ＤＣ値はより広い範囲に及ぶであろう。
【００３８】
また、雲から出る飛行機は、一定のＤＣ平均明度を持ちながらコントラストが増加することがあり、このときはＤＣ一致がより良好な選択となる。別の手段としては、かかる場合、スケール化ＡＣ値を一致させることも適切である。平均明度（ＤＣ）および局所的コントラスト（ＡＣ）において変化している画像領域は、ＡＣ周波数を上下にスケーリングし、探索することで最良一致させられるだろう。このように、コントラストの増加／減少が起こるが、それでも一致させることができる。これらの一致検査を実行する場合、最良一致の種類（例えば、ＤＣ  ＳＡＤ対ＡＣ対スケール化ＡＣ）に関する情報は、後続の動き補償ステップ中で利用できる（例えば、上記の「ビデオ圧縮フレームの改良補間法」と題する係属中の米国特許を参照のこと。）。
【００３９】
どのような場合でも、動き補償およびＤＣＴまたはその他の変換符号化を改良するために、最良一致の種類（例えば、ＤＣ対ＡＣ対スケール化ＡＣ）を後続の符号化処理へ送る（例えば、チャネル内で、またはチャネル外で）ことができる。
【００４０】
従って、本発明のこの側面は、以下を含む多くの特徴を包含する：
動き補償圧縮における動きベクトルを決定するためのＡＣ一致の使用。
ＡＣ一致とＤＣ一致の比較、および動き補償圧縮での使用のための最良一致選択。
広いダイナミックレンジおよび広いコントラストレンジの画像における動きベクトル決定を改良する最良一致（ＡＣまたはＤＣ）の使用。
ＡＣ一致処理におけるＡＣ周波数成分のスケーリング（増加／減少）。
輝度一致に加えて、またはその代替として、ＲＧＢ差の一致の使用（下記の式１および式２を追加説明とともに参照のこと。）。
【００４１】
一致基準
現在フレーム内の位置を一致させ、以前または後続のフレーム内の対応する対象位置を見つけるためには、一致基準を定義する必要がある。例示的な実施の形態では、主たる一致基準は、ピクセル一致領域（例えば、１５×１５ピクセル）全体に一様に重み付けされる。ピクセル毎に、現在のフレーム（「self」）および一致させられるフレーム（「（other）」）に対して、赤、緑、および青（Ｒ、Ｇ、Ｂ）の差の合計の絶対値を計算し、個々の差の絶対値の合計を加算する。これを以下に示す：
【数１】
2005516433.tif 000003
【数２】
2005516433.tif 000004
【００４２】
式１は本質的には２つの項を有する。ピクセルの色の合計した差の絶対値である第１項は、元のカメラセンサ（またはフィルム）が無相関の色チャネルを持つ場合（これが通例である）、一致におけるノイズの影響を減少させるのに役立つ。ノイズはほとんどの場合、色間で無相関であり、従って、ある色と他の色で逆方向に向かうと考えられ、それ故、差を相殺し、より良好な一致を見つけるのに役立つ。第２項は、差の絶対値を合計する（つまり、ＳＡＤであるが、全ての原色に適用される）。式１にこの項を使用する理由は、色相の変化を検出するためである。なぜなら、第１項はノイズではなく、むしろ、青チャネルが減少するのと同じ量だけ赤チャネルが増加したために（緑が変わらないとき）、合計がゼロになる場合がある。このように、これら２つの項は協力して、ＲＧＢの差を用いる一致を検出するのに役立つ。また、輝度の式で用いられる代表的な知覚のバイアスである緑に比重を置くことも可能であり、あるいは、一致に対して輝度自体を用いることも可能である。しかしながら、輝度を用いる場合、上記の関数で赤、緑、および青チャネルを別々に維持することによって、一致に影響を与える無相関なノイズを減少させられなくなる。しかし、輝度一致も受容可能な程度には動作するはずである。（注：ＭＰＥＧタイプの動きベクトル探索では、輝度一致だけを用いるのが典型である）。さらに、ＲＧＢ差および輝度の一致はともに組み合わせることができる。
【００４３】
式２は、式１を用いた結果を、一致領域全体で合計する。従って、式２を用いて、全体一致の値、または特定の一致領域／探索領域毎の比較についての信頼性係数が与えられる。探索における最良一致は、式２のdiff_dcが最小値をとる位置であろう。これは主としてＤＣ一致である。
【００４４】
しかしながら、この「領域差分」関数は、対象が光に入っていくか、もしくは出て行く場合、または、全体の映像が溶明するか、黒に溶暗していく場合を検出しない。かかる場合、たとえ一致領域全体の明るさが変化しても、ノイズ減少およびフレームレート動き変換は、依然適切に動作するだろうから、画像中の対象を一致させることは依然として有用であろう。かかる状況のもとで一致を検出するために、明度の全体変化を除去する別の「ＡＣ」（変化するＤＣ条件に対する）一致が必要とされる。かかる一致は、ＤＣ（または一定成分）バイアスを領域差分から除去するＡＣ相関関数、または他のＡＣ一致技法を必要とする。これは、両方の画像のピクセルを減算する代わりに乗算し、一致関数について最良の相関を見つけることで、達成される。乗算については、ＤＣ項は、乗算に先立って一致領域毎の平均値を減算することにより除去できる。こうして、平均値に関して正負両方の乗算がなされ、ＡＣ一致だけが決定される。好適な一実施の形態で、ＡＣ相関一致関数は、以下のように生成される：
【数３】
2005516433.tif 000005
【数４】
2005516433.tif 000006
【数５】
2005516433.tif 000007
【００４５】
このＡＣ一致関数は、最大領域相関／畳み込み関数である。一致した領域の平均値は、ＤＣ項を与える（式３）。一致されるべき領域は、ＤＣ項を減算した後乗算されるピクセルを有し（式４）、そしてこれらの乗算された値は合計される（式５）。探索領域におけるこの合計の最大値が最良の相関であり、従って、最良の一致である。
【００４６】
第２の実施の形態では、以下のようなＡＣ  ＳＡＤ差関数を用いてもよい：
【数６】
2005516433.tif 000008
【数７】
2005516433.tif 000009
【００４７】
輝度情報も最良ＡＣ一致関数を決定するのに用いることができる（緑成分の差により重みをおく）。乗算関数は、チャネル間ノイズを相殺するのに本質的に役立たないため、ここで輝度または他の色の重み付けを用いることにより失われるものは何もない。しかしながら、同一輝度を有する色相変化が、誤って一致することはあり得る。これは３色全ての相関の合計を用いることにより回避される。しかしながら注意すべきは、ＡＣ一致関数は、フレーム間の色相および輝度一致を見つけることはできず、ただ細部の一致を見つけるだけということである。色相または輝度一致は基本的には、上記の最小領域差分関数（式２）を用いるＤＣ一致である（一致領域の２つのＤＣ平均値を減算することと等価である）。
【００４８】
（黒、焦点ボケ、または一定の色の領域等の）細部を持たない領域については、カメラセンサ（またはフィルム粒子）のノイズは信号を上回りがちであり、偽りの一致を導く。従って、フェードまたは明暗が変化している間（統計的には非常に希であり、映画の約１％が普通である）の一致を提供しようとする場合、ＡＣ最大領域相関一致、およびＤＣ最小領域差分一致による作用の組み合わせは、最適一致関数を形成すると考えられる。ＡＣ最大領域相関一致関数が積を用いる最大相関値を伴うのに対して、系はＤＣ最小領域差分一致関数に対しては全体の最小値を決定するから、これら２つの一致関数の組み合わせは、スケールファクタおよび関数の一方（典型的には、ＡＣ最大領域相関一致関数）の逆数を必要とする。また、これら２つの関数は、一致に対して異なる感度を有する。しかしながら、重み付け、スケールファクタ、および、ことによると累乗法の適切な調整により、一致探索領域全体の最小差分および最大相関の組み合わせとして最適一致を見出す場合に、これら２つの独立関数間のいかなる所望のバランスをも生み出すことができる。
【００４９】
上記の、２つの一致関数を組み合わせて単一の一致関数を形成する代わりに、それぞれの一致関数を独立した結果として保つ、異なる（幾分かより好適な）方法がある。これにより、幾分か独立した一致は、後での組み合わせおよび後続処理のための独立した動きベクトルおよび動き補償結果を生成することができる。
【００５０】
実装
本発明は、ハードウエアもしくはソフトウエアまたは両者の組み合わせ（例えば、プログラマブル・ロジック・アレー）で実装してもよい。特に規定のない限り、本発明の一部として含まれるアルゴリズムは、如何なる特定のコンピュータまたは他の装置と本質的に関連しない。特に、本明細書の教示に従って書かれたプログラムを有する各種の汎用マシンを用いることができ、あるいはより特化した装置（例えば、集積回路）を構成して特定の機能を実行すると更に便利になろう。このように、本発明は、１台以上のプログラマブルコンピュータシステム上の１つ以上のコンピュータプログラムに実装でき、各システムは、少なくとも１つのプロセッサ、少なくとも１つのデータ記憶システム（揮発性または不揮発性メモリおよび／または記憶素子を含む）、少なくとも１つの入力装置またはポート、および少なくとも１つの出力装置またはポートを備える。プログラムコードを入力データに適用して本明細書で説明した機能を実行するとともに、出力情報を生成する。出力情報は、既知の方法で１台以上の出力装置に適用される。
【００５１】
コンピュータシステムと通信するための、任意の所望するコンピュータ言語（機械語、アセンブリ言語、または高レベル手続き型言語、論理型言語、またはオブジェクト指向プログラム言語を含む）で、かかるプログラムをそれぞれ実装してよい。いずれにしても、言語は、コンパイラ型言語でもインタープリタ型言語でもよい。
【００５２】
本明細書で説明した手段を実行するためのコンピュータシステムにより、汎用または特定用途のプログラマブルコンピュータにより可読な記憶媒体または装置（例えば、固体メモリか媒体、または磁気式か光学式媒体）が読み込まれる際に、コンピュータを構成するとともに操作するため、かかるコンピュータプログラムはそれぞれ、その記憶媒体または装置に格納するかダウンロードされるのが好ましい。本発明のシステムは、コンピュータプログラムで構成されたコンピュータ可読の記憶媒体として実施されると考えられてもよく、その場合、そのように構成された記憶媒体は、コンピュータシステムを特定のかつ予め定義された方法で動作させて、本明細書で説明した機能を実行する。
【００５３】
本発明の多くの実施の形態を説明してきた。それにもかかわらず、本発明の趣旨と範囲から逸脱することなく、多様な改変がなされるだろうことは言うまでもない。例えば、上記のステップの幾つかは順不同であってもよく、従って、説明したものと異なる順序で実行してもよい。よって、他の実施の形態は、以下の請求の範囲内にある。
【図面の簡単な説明】
【００５４】
【図１】図１は、高速動き推定のための（コンピュータに実装されるであろう）例示的な方法を示すフロー図である。
【図１】
2005516433.tif 000010
【国際調査報告】
2005516433.tif 000011