(57)【要約】【課題】  一連のバタフライ演算および行列乗算を使用して実現される８点のＷＭＶ９／ＶＣ−９の変換に関する高速実装を提供すること。【解決手段】  逆変換の高速実装は、行列乗算を逆のフローにしてバタフライ演算の逆演算を行うことにより実現される。これらの高速実装では、フィルタリングの両方の次元の終わりに、または各段で別々に、変換段にスケーリングを組み込むことができる。変換のこれらの高速実装は、画像圧縮および他の信号処理システムのこの変換に基づく符号化器および復号化器内で使用することができる。【選択図】  図６
2005327298.tif 000002
【特許請求の範囲】
【請求項１】
【数１】
2005327298.tif 000038
で表される変換行列に基づいて二次元ブロックの次元の少なくとも１つにおける８点のブロック変換に関する変換の高速実装を使用し前記ブロック内のメディアデータを変換符号化する方法であって、
空間領域の係数の８点集合と、前記少なくとも１つの８点の次元の８点の変換領域の係数との間の変換を行うバタフライ演算の複数の段を実行するステップと、
奇数の変換領域の係数について行列
【数２】
2005327298.tif 000039
による行列乗算を実行する前記複数の段を実行するステップと備えたことを特徴とする方法。
【請求項２】
メディアデータの変換符号化を行うメディアシステムであって、
前記メディアデータの二次元ブロックについて、前記ブロックの順変換を実行し前記ブロックを変換領域に変換する動作をする順変換の段と、
前記変換領域のブロックを量子化する動作をする量子化の段と、
前記変換領域のブロックを逆量子化する動作をする逆量子化の段と、
前記変換領域のブロックの逆変換を実行し、形式
【数３】
2005327298.tif 000040
の再構成されたブロックを出力する逆変換段とを備え、前記逆変換の少なくとも１つの次元ＴｎまたはＴｍは、８点行列
【数４】
2005327298.tif 000041
であり、前記逆変換は、一連のバタフライ演算および行列
【数５】
2005327298.tif 000042
による行列乗算として実装されることを特徴とするメディアシステム。
【請求項３】
【数６】
2005327298.tif 000043
で表される変換行列に基づいて二次元ブロックの次元の少なくとも１つにおける８点のブロック変換に関する変換の高速実装を使用し前記ブロック内のメディアデータを変換符号化する方法を実現するためのコンピュータ実行可能ソフトウェア命令を搬送するコンピュータ読み取り可能な媒体であって、前記方法は、
空間領域の係数の８点集合と前記少なくとも１つの８点の次元の８点の変換領域の係数との間の変換を行うバタフライ演算の複数の段を実行するステップと、奇数の変換領域の係数について行列
【数７】
2005327298.tif 000044
による行列乗算を実行することを含む前記複数の段を実行するステップと
を備えたことを特徴とするコンピュータ読み取り可能な媒体。
【請求項４】
空間領域の表現と変換領域の表現との間で画像データの二次元ブロックを変換する高速変換法であって、前記ブロックの少なくとも１つの次元は８点であり、順変換について、
変数０から７までの集合に対し、少なくとも、
値ｃおよびｓが１である、変数０および７のバタフライ演算と、
値ｃおよびｓが１である、変数１および６のバタフライ演算と、
値ｃおよびｓが１である、変数２および５のバタフライ演算と、
値ｃおよびｓが１である、変数３および４のバタフライ演算と、
値ｃおよびｓが１である、変数０および３のバタフライ演算と、
値ｃおよびｓが１である、変数１および２のバタフライ演算と、
値ｃおよびｓが１であり、１２によるスケーリングが行われる、変数０および１のバタフライ演算と、
値ｃおよびｓが１６および６である、変数３および２のバタフライ演算と、
値ｃおよびｓが４および１である、変数４および７のバタフライ演算と、
後に変数６の符号反転が続く、値ｃおよびｓが５および３である、変数５および６のバタフライ演算と、
値ｃおよびｓが１である、変数５および６の第２のバタフライ演算とを含む、
【数８】
2005327298.tif 000045
型の一連のバタフライ演算を実行するステップと、
前記変数５および６の第２のバタフライ演算の前に、行列
【数９】
2005327298.tif 000046
による変数４および５と変数７および６の行列乗算を実行するステップとを備え、
前記変換領域内で０から３までの前記変数は偶数の係数を出力し、４から７の前記変数は奇数の係数を出力することを特徴とする高速変換法。
【請求項５】
逆変換について、
前記順変換の逆フローで前記バタフライ演算の逆演算を実行するステップをさらに備えたことを特徴とする請求項４に記載の高速変換法。
【請求項６】
空間領域の表現と変換領域の表現との間で画像データの二次元ブロックを変換する高速変換法であって、前記ブロックの少なくとも１つの次元は８点であり、逆変換について、
変数０から７までの集合に対し、変数０から３までは偶数の変換係数であり、変数４から７までは奇数の変換係数であり、少なくとも、
値ｃおよびｓが１である、変数５および６のバタフライ演算と、
後に変数５の符号反転が続く、値ｃおよびｓが５および３である、変数６および５の第２のバタフライ演算と、
値ｃおよびｓが４および１である、変数４および７のバタフライ演算と、
値ｃおよびｓが１であり、１２によるスケーリングが行われる、変数０および１のバタフライ演算と、
値ｃおよびｓが１６および６である、変数３および２のバタフライ演算と、
値ｃおよびｓが１である、変数１および２のバタフライ演算と、
値ｃおよびｓが１である、変数０および３のバタフライ演算と、
値ｃおよびｓが１である、変数３および４のバタフライ演算と、
値ｃおよびｓが１である、変数２および５のバタフライ演算と、
値ｃおよびｓが１である、変数１および６のバタフライ演算と、
値ｃおよびｓが１である、変数０および７のバタフライ演算とを含む、
【数１０】
2005327298.tif 000047
型の一連のバタフライ演算を実行するステップと、
前記変数５および６の第２のバタフライ演算の前に、行列
【数１１】
2005327298.tif 000048
による変数４および５と変数７および６の行列乗算を実行するステップと
を備えたことを特徴とする高速変換法。
【請求項７】
空間領域の表現と変換領域の表現との間で画像データの二次元ブロックを変換する高速変換法であって、前記ブロックの少なくとも１つの次元は８点であり、逆変換について、
変数０から７までの集合に対し、変数０から３までは偶数の変換係数であり、変数４から７までは奇数の変換係数であり、少なくとも、
後に変数６の符号反転が続く、値ｃおよびｓが５および３である、変数５および６のバタフライ演算と、
値ｃおよびｓが４および１である、変数４および７のバタフライ演算と、
値ｃおよびｓが１である、変数５および６の第２のバタフライ演算と、
値ｃおよびｓが１であり、１２によるスケーリングが行われる、変数０および１のバタフライ演算と、
値ｃおよびｓが１６および６である、変数３および２のバタフライ演算と、
値ｃおよびｓが１である、変数１および２のバタフライ演算と、
値ｃおよびｓが１である、変数０および３のバタフライ演算と、
値ｃおよびｓが１である、変数３および４のバタフライ演算と、
値ｃおよびｓが１である、変数２および５のバタフライ演算と、
値ｃおよびｓが１である、変数１および６のバタフライ演算と、
値ｃおよびｓが１である、変数０および７のバタフライ演算とを含む、
【数１２】
2005327298.tif 000049
型の一連のバタフライ演算を実行するステップと、
前記変数４および７のバタフライ演算の後、前記変数５および６の第２のバタフライ演算の前に、行列
【数１３】
2005327298.tif 000050
による変数４および５と変数７および６の行列乗算を実行するステップと
を備えたことを特徴とする高速変換法。
【請求項８】
順変換について、
前記順変換の逆フローで前記バタフライ演算の逆演算を実行するステップをさらに備えたことを特徴とする請求項７に記載の高速変換法。
【請求項９】
空間領域の表現と変換領域の表現との間で画像データの二次元ブロックを変換する高速変換法であって、前記ブロックの少なくとも１つの次元は８点であり、順変換について、
変数０から７までの集合に対し、少なくとも、
値ｃおよびｓが１である、変数０および７のバタフライ演算と、
値ｃおよびｓが１である、変数１および６のバタフライ演算と、
値ｃおよびｓが１である、変数２および５のバタフライ演算と、
値ｃおよびｓが１である、変数３および４のバタフライ演算と、
値ｃおよびｓが１である、変数０および３のバタフライ演算と、
値ｃおよびｓが１である、変数１および２のバタフライ演算と、
値ｃおよびｓが１であり、１２によるスケーリングが行われる、変数０および１のバタフライ演算と、
値ｃおよびｓが１６および６である、変数３および２のバタフライ演算と、
値ｃおよびｓが１である、変数５および６の第１のバタフライ演算と、
値ｃおよびｓが４および１である、変数４および７のバタフライ演算と、
後に変数５の符号反転が続く、値ｃおよびｓが５および３である、変数６および５の第２のバタフライ演算とを含む、
【数１４】
2005327298.tif 000051
型の一連のバタフライ演算を実行するステップと、
前記変数５および６の第１のバタフライ演算の後、前記変数４および７のバタフライ演算の前に、行列
【数１５】
2005327298.tif 000052
による変数４および５と変数７および６の行列乗算を実行するステップとを備え、
前記変換領域内で０から３までの前記変数は偶数の係数を出力し、４から７の前記変数は奇数の係数を出力することを特徴とする高速変換法。
【請求項１０】
二次元メディアブロックの変換ベースの圧縮／圧縮解除を実行する二次元メディア圧縮プロセッサであって、前記ブロックの少なくとも１つの８点の次元における前記変換は、変換行列
【数１６】
2005327298.tif 000053
に基づき、
変数０から７までの集合に対し、変数０から３までは偶数の変換係数であり、変数４から７までは奇数の変換係数であり、少なくとも、
値ｃおよびｓが１である、変数０および７のバタフライ演算と、
値ｃおよびｓが１である、変数１および６のバタフライ演算と、
値ｃおよびｓが１である、変数２および５のバタフライ演算と、
値ｃおよびｓが１である、変数３および４のバタフライ演算と、
値ｃおよびｓが１である、変数０および３のバタフライ演算と、
値ｃおよびｓが１である、変数１および２のバタフライ演算と、
値ｃおよびｓが１であり、１２によるスケーリングが行われる、変数０および１のバタフライ演算と、
値ｃおよびｓが１６および６である、変数３および２のバタフライ演算と、
値ｃおよびｓが４および１である、変数４および７のバタフライ演算と、
後に変数６の符号反転が続く、値ｃおよびｓが５および３である、変数５および６のバタフライ演算と、
値ｃおよびｓが１である、変数５および６の第２のバタフライ演算とを含む、
【数１７】
2005327298.tif 000054
型の一連のバタフライ演算を実行する手段と、
前記変数５および６の第２のバタフライ演算の前に、行列
【数１８】
2005327298.tif 000055
による変数４および５と変数７および６の行列乗算を実行する手段と
を備えることを特徴とする二次元メディア圧縮プロセッサ。
【請求項１１】
二次元メディアブロックの変換ベースの圧縮／圧縮解除を実行する二次元メディア圧縮プロセッサであって、前記ブロックの少なくとも１つの８点の次元における前記変換は、変換行列
【数１９】
2005327298.tif 000056
に基づき、
変数０から７までの集合に対し、変数０から３までは偶数の変換係数であり、変数４から７までは奇数の変換係数であり、少なくとも、
値ｃおよびｓが１である、変数５および６のバタフライ演算と、
後に変数５の符号反転が続く、値ｃおよびｓが５および３である、変数６および５の第２のバタフライ演算と、
値ｃおよびｓが４および１である、変数４および７のバタフライ演算と、
値ｃおよびｓが１であり、１２によるスケーリングが行われる、変数０および１のバタフライ演算と、
値ｃおよびｓが１６および６である、変数３および２のバタフライ演算と、
値ｃおよびｓが１である、変数１および２のバタフライ演算と、
値ｃおよびｓが１である、変数０および３のバタフライ演算と、
値ｃおよびｓが１である、変数３および４のバタフライ演算と、
値ｃおよびｓが１である、変数２および５のバタフライ演算と、
値ｃおよびｓが１である、変数１および６のバタフライ演算と、
値ｃおよびｓが１である、変数０および７のバタフライ演算とを含む、
【数２０】
2005327298.tif 000057
型の一連のバタフライ演算を実行する手段と、
前記変数５および６の第２のバタフライ演算の前に、行列
【数２１】
2005327298.tif 000058
による変数４および５と変数７および６の行列乗算を実行する手段と
を備えることを特徴とする二次元メディア圧縮プロセッサ。
【請求項１２】
二次元メディアブロックの変換ベースの圧縮／圧縮解除を実行する二次元メディア圧縮プロセッサであって、前記ブロックの少なくとも１つの８点の次元における前記変換は、変換行列
【数２２】
2005327298.tif 000059
に基づき、
変数０から７までの集合に対し、変数０から３までは偶数の変換係数であり、変数４から７までは奇数の変換係数であり、少なくとも、
後に変数６の符号反転が続く、値ｃおよびｓが５および３である、変数５および６のバタフライ演算と、
値ｃおよびｓが４および１である、変数４および７のバタフライ演算と、
値ｃおよびｓが１である、変数５および６の第２のバタフライ演算と、
値ｃおよびｓが１であり、１２によるスケーリングが行われる、変数０および１のバタフライ演算と、
値ｃおよびｓが１６および６である、変数３および２のバタフライ演算と、
値ｃおよびｓが１である、変数１および２のバタフライ演算と、
値ｃおよびｓが１である、変数０および３のバタフライ演算と、
値ｃおよびｓが１である、変数３および４のバタフライ演算と、
値ｃおよびｓが１である、変数２および５のバタフライ演算と、
値ｃおよびｓが１である、変数１および６のバタフライ演算と、
値ｃおよびｓが１である、変数０および７のバタフライ演算とを含む、
【数２３】
2005327298.tif 000060
型の一連のバタフライ演算を実行する手段と、
変数４および７の前記バタフライ演算の後、変数５および６の前記第２のバタフライ演算の前に、行列
【数２４】
2005327298.tif 000061
による変数４および５と変数７および６の行列乗算を実行する手段と
を備えることを特徴とする二次元メディア圧縮プロセッサ。
【請求項１３】
二次元メディアブロックの変換ベースの圧縮／圧縮解除を実行する二次元メディア圧縮プロセッサであって、前記ブロックの少なくとも１つの８点の次元における前記変換は、変換行列
【数２５】
2005327298.tif 000062
に基づき、
変数０から７までの集合に対し、変数０から３までは偶数の変換係数であり、変数４から７までは奇数の変換係数であり、少なくとも、
値ｃおよびｓが１である、変数０および７のバタフライ演算と、
値ｃおよびｓが１である、変数１および６のバタフライ演算と、
値ｃおよびｓが１である、変数２および５のバタフライ演算と、
値ｃおよびｓが１である、変数３および４のバタフライ演算と、
値ｃおよびｓが１である、変数０および３のバタフライ演算と、
値ｃおよびｓが１である、変数１および２のバタフライ演算と、
値ｃおよびｓが１であり、１２によるスケーリングが行われる、変数０および１のバタフライ演算と、
値ｃおよびｓが１６および６である、変数３および２のバタフライ演算と、
値ｃおよびｓが１である、変数５および６の第１のバタフライ演算と、
値ｃおよびｓが４および１である、変数４および７のバタフライ演算と、
後に変数５の符号反転が続く、値ｃおよびｓが５および３である、変数６および５の第２のバタフライ演算とを含む、
【数２６】
2005327298.tif 000063
型の一連のバタフライ演算を実行する手段と、
前記変数５および６の第１のバタフライ演算の後、前記変数４および７のバタフライ演算の前に、行列
【数２７】
2005327298.tif 000064
による変数４および５と変数７および６の行列乗算を実行する手段と
を備えることを特徴とする二次元メディア圧縮プロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般には、信号のデジタル符号化およびデジタル処理を行う技術に関し、より詳細には、画像および動画像などの信号の符号化および復号化を行う際に、あるクラスの計算効率のよい変換の高速実装に関する。
【背景技術】
【０００２】
変換符号化は、多くのオーディオ、画像、および動画像圧縮システムで使用される圧縮手法である。未圧縮のデジタル画像およびデジタル動画像は、通常、二次元グリッドに配列された画像もしくは動画像フレーム内の複数の位置における複数の画素もしくは画色のサンプルとして表されるか、または取り込まれる。例えば、通常の画像の形式は、グリッドとして配列された２４ビットカラーの画素サンプルのストリームで構成される。各々のサンプルは、ＲＧＢ、もしくはとりわけＹＩＱなどの色空間内のグリッドにおけるピクセル位置の色成分を表す数である。さまざまな画像および動画像システムは、サンプリングのさまざまな異なる色、空間、および時間の解像度を使用することができる。
【０００３】
未圧縮のデジタル画像およびデジタル動画像の信号は、かなりの記憶領域および伝送容量を消費する可能性がある。変換符号化では、信号の空間領域の表現を周波数領域（もしくは他の類似の変換領域）の表現に変換し、続いて変換領域の表現に属する、多少の概して視認できないくらいの周波数成分に関する解像度を下げることにより、デジタル画像およびデジタル動画像のサイズを縮小する。この方法によって、一般的に、空間領域の画像もしくは動画像の、色もしくは空間の解像度を下げる方法と比較して、デジタル信号は知覚できないくらいにしか劣化しない。
【０００４】
より具体的には、標準的な変換符号化の手法では、未圧縮のデジタル画像のピクセルを、各々のブロックが場合によっては他のブロックと重なり合う、固定サイズの複数の二次元ブロックに分割する。空間周波数の分析を実行する線形変換が各々のブロックに適用される。その結果、ブロック内の空間のサンプルは、一般的にブロックの間隔にわたって対応する周波数帯域内のデジタル信号の強度を表す一組の周波数（または変換）係数に変換される。圧縮するため、変換係数を選択的に量子化する（すなわち、係数値のうち最も重要ではないビットを落とすか、もしくは他の何らかの手段により高い解像度の数集合の中の値を低い解像度にマッピングすることなどにより解像度を下げられる）ことができ、さらに圧縮されたデータストリームにエントロピー符号化もしくは可変長符号化することができる。復号化では、変換係数を逆変換することによって、色／空間サンプリングの画像／動画像信号がほぼ元通りに再構成される。
【０００５】
多くの画像および動画像圧縮システム、特にＭＰＥＧおよびウィンドウズ（登録商標）メディアなどは、離散的コサイン変換（ＤＣＴ）に基づく変換を利用する。ＤＣＴは、最適に近いデータ圧縮をもたらす好ましいエネルギーの圧縮特性を有することが知られている。これらの圧縮システムでは、個別のブロック画像を再構成するため圧縮システムの符号化器と復号化器の両方の再構成ループ内で逆ＤＣＴ（ＩＤＣＴ）が使用される。ＩＤＣＴの実装例が文献で説明されている（例えば、非特許文献１を参照）。
【０００６】
非特許文献１で定義されているようなＩＤＣＴ変換の欠点は、変換の計算が、高価なコンピュータによる、６４ビットの浮動小数点数の行列乗算を伴う点である。これは、ＩＤＣＴがリアルタイムもしくは他の同様の時間的制約の下で大量の圧縮データを処理する場合には、特にストリーミングメディアおよび同様にメディアを再生するアプリケーションにおいて、画像もしくは動画像圧縮システムの性能を制限する可能性がある。
【０００７】
映画テレビ技術者協会（ＳＭＰＴＥ）のＣ２４技術委員会を通じてビデオコーデック９（ＶＣ−９）として標準化を提案されている、ウィンドウズ（登録商標）・メディア・ビデオ９（ＷＭＶ９）の符号化の標準では、４種類の二次元データの変換である、８×８、８×４、４×８、および４×４の変換を定義する。これらのＶＣ−９標準の変換は、ＤＣＴに類似のエネルギーの圧縮特性を有するが、計算効率のために整数の行列乗算の演算に基づく実装となっている。ＷＭＶ９／ＶＣ−９の変換の行列による実装について詳細な説明が行われている（例えば、２００３年２月２８日に出願した米国特許出願第１０／３７６，１４７号明細書参照）。ＷＭＶ９規格では、逆変換のビット完全な実装を必要とする。
【０００８】
線形変換の高速実装には長い歴史がある。高速変換のよく知られている一例として、高速フーリエ変換（ＦＦＴ）がある（例えば、非特許文献２参照）。ＦＦＴでは、オーダーＯ（Ｎ  ｌｏｇ  Ｎ）回演算をすることによって、Ｎ点のフーリエ変換を実現する。この簡易化が可能になるのはフーリエ変換の定義から本来備わっている対称性のためである。類似の高速実装は、離散コサイン変換（ＤＣＴ）についても存在することが示されている（例えば、非特許文献３および非特許文献４参照）。
【０００９】
高速変換では、変換の行列乗算の定義を、「バタフライ」演算を伴う一連のステップに分解する。バタフライ演算は、空間領域、周波数領域もしくは媒介変数のいずれかである、２変数の間の重み付けをしたデータ交換である。例えば、以下の行列乗算に対応するバタフライ演算
【００１０】
【数１】
2005327298.tif 000003
【００１１】
は、図３に示されている。これは、適した倍率で原点を中心として、元の二次元ベクトルｘの回転に対応する。倍率は、ｃ２＋ｓ２＝１であれば１である。実数値を入力とするバタフライ演算は、３回の実数値の乗算のみで実装することができる。一般に、この行列は単なる回転に対応する必要はない−したがって、そのままスケーリングおよびせん断が可能である。
【００１２】
４点の（ｆｏｕｒ−ｐｏｉｎｔ）ＷＭＶ９／ＶＣ−９の変換では、ちょうど説明したように、バタフライ演算を直接適用することにより高速実装が可能である。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上記で議論したように、８点のＤＣＴは、変換の高速実装を持つことが知られている。しかし、これを８点のＷＭＶ９／ＶＣ−９の変換へ移し変えることは容易ではない。ＷＭＶ９／ＶＣ−９の変換は、ＤＣＴに類似しているが、ビット完全（ｂｉｔ−ｅｘａｃｔｎｅｓｓ）な整数の実装および要件により、知られている高速実装から直にマッピングすることは不可能である。
【００１４】
８点のＷＭＶ９／ＶＣ−９の変換は、偶行列（ｅｖｅｎ  ｍａｔｒｉｘ）と奇行列（ｏｄｄ  ｍａｔｒｉｘ）のペアを使用する演算により実装できる（例えば、特許文献１参照）。ＤＣＴの偶数の基底関数（すなわち、基底関数０、２、４、および８）は、４点のＤＣＴによって続けて入力される一連のバタフライ演算により実現できることは自明であることが知られている。ＤＣＴの知られている高速実装は、８点のＷＭＶ９／ＶＣ−９の変換の偶行列にうまく移し変える。
【００１５】
しかし、知られている高速実装は、８点のＷＭＶ９／ＶＣ−９の変換の奇行列の高速実装を得るための手段とはならない。ＷＭＶ９／ＶＣ−９の変換は、ＤＣＴに類似しているが、ＷＭＶ９／ＶＣ−９のビット完全な整数の実装および要件により、知られている変換の高速実装からの直にマッピングすることは不可能である。知られている変換の高速実装を参照しても、これらの変換の奇数の基底関数の解析および統合を解決できない。
【００１６】
本明細書では８点のＷＭＶ９／ＶＣ−９の変換に関する高速実装について説明する。
【００１７】
【特許文献１】U.S. Patent Application Serial No.10/376, 147, filed February 28, 2003
【非特許文献１】"IEEE Standard Specification for the Implementations of 8x8 Inverse Discrete Cosine Transform," IEEE Std. 1180-1990, December 6, 1990
【非特許文献２】J.W. Cooley and J.W. Tukey, "An Algorithm For The Machine Calculation Of Complex Fourier Series," Math. Computation, vol. 19, pp. 297-301, 1965
【非特許文献３】W. Chen, C.H. Smith and S.C. Fralick, "A Fast Computational Algorithm For The Discrete Cosines Transform," IEEE Trans. Commun., vol. 25, pp. 1004-1009, Sept. 1977
【非特許文献４】H. Malvar, "Fast Computation Of The Discrete Cosine Transform And The Discrete Hartley Transform," IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-35, pp. 1484-1485, October 1987
【課題を解決するための手段】
【００１８】
説明する実装は、８点のＷＭＶ９／ＶＣ−９の変換の順変換および逆変換の高速実装とともに、各々の代替えの実装を含む。これらの高速実装では、フィルタリングの両方の次元の終わりか各段で別々に、その変換段にスケーリングを組み込むことができる。また、ＷＭＶ９／ＶＣ−９の変換を用いるコーデックの符号化器および復号化器の面とともに、画像圧縮およびその他の信号処理システムでも、高速実装を使用することができる。
【００１９】
本発明の追加の特徴および利点は、添付の図面を参照して行われる実施形態についての以下の詳細な説明から明白になる。
【発明を実施するための最良の形態】
【００２０】
以下の説明は、ＷＭＶ９／ＶＣ−９に準拠したコーデックだけでなく他の二次元メディア（例えば、動画像および画像）のコーデックでの使用に適用することができて、ＷＭＶ９のおよびＶＣ−９のコーデックで定義された、一組の変換の高速実装についてのものである。メディア符号化の変換の高速実装に関する応用例は、画像のもしくは動画像の符号化器および復号化器に見られる。しかし、本明細書で説明するような変換の構成は、画像もしくは動画像のコーデックに限られず、他のメディア処理システムにも適用可能である。したがって、これらの変換の高速実装は、一般化された画像もしくは動画像の符号化器および復号化器の文脈において説明されるが、それとは別に、これらの変換を用いるさまざまな種類のメディア処理システムおよび信号処理システムに組み込むことができる。
【００２１】
１．一般化された動画像の符号化器および復号化器
図１は、一般化された動画像符号化器（１００）のブロック図であり、図２は、一般化された動画像復号化器（２００）のブロック図であり、これらにはＷＭＶ９／ＶＣ−９の変換を組み込むことができる。
【００２２】
符号化器および復号化器の内部のモジュール間の図に示されている関係は、符号化器および復号化器の情報の主な流れを示しており、他の関係は、簡単のために図に示さない。特に、図１および図２は、通常、動画像シーケンス、フレーム、マクロブロック、ブロックなどに使用される符号化器の設定、モード、テーブルなどを示す副次的情報を示さない。このような副次的情報は、通常、副次的情報のエントロピー符号化の後に、出力ビットストリームに送られる。出力ビットストリームの形式としては、ウィンドウズ（登録商標）・メディア・ビデオ形式もしくは別の形式が可能である。
【００２３】
符号化器（１００）および復号化器（２００）は、ブロックベースであり、各マクロブロックが４つの輝度で８×８の輝度ブロック（ときどき１つの１６×１６のマクロブロックとして扱われる）および２つの８×８の色差ブロックを含む、４：２：０のマクロブロックの形式を使用する。あるいはまた、符号化器（１００）および復号化器（２００）は、オブジェクトベースであり、異なるマクロブロックもしくはブロックの形式を使用するか、または８×８のブロックおよび１６×１６のマクロブロックと異なるサイズもしくは構成のピクセルの集合に対して演算を実行する。
【００２４】
所望の圧縮の実装および種類に応じて、符号化器もしくは復号化器のモジュールを追加し、省略し、複数のモジュールに分割し、他のモジュールと組み合わせ、および／もしくは類似のモジュールで置き換えることができる。代替の実施形態では、説明する手法の１つもしくは２つ以上が、異なるモジュールおよび／もしくはモジュールの他の構成の符号化器もしくは復号化器により、実行される。
【００２５】
Ａ．動画像符号化器
図１は、一般的な動画像符号化器のシステム（１００）のブロック図である。符号化器のシステム（１００）は、現在のフレーム（１０５）を含む動画像フレームのシーケンスを受け取り、出力として圧縮動画像情報（１９５）を生成する。動画像符号化器の特定の実施形態では、通常、一般化された符号化器（１００）を変更して、もしくは補足して使用する。
【００２６】
符号化器のシステム（１００）は、予測されたフレームおよびキーフレームを圧縮する。説明のため、図１は、符号化器のシステム（１００）を通るキーフレームの経路および前方予測のフレームの経路を示している。符号化器のシステム（１００）のコンポーネントの多くは、キーフレームおよび予測されたフレームの両方を圧縮するために使用される。これらのコンポーネントにより実行される演算は、厳密には圧縮される情報の種類に応じて異なる。
【００２７】
予測されたフレーム［ｐフレーム、双方向予測のｂフレーム、もしくはコーデック間のフレームとも呼ばれる］は、１つもしくは２つ以上の他のフレームからの予測（もしくは予測差分）に関して表される。予測残差は、予測されたフレームと元のフレームとの差分である。対照的に、キーフレーム［ｉフレーム、コーデック内部のフレームとも呼ばれる］は、他のフレームを参照せずに圧縮される。
【００２８】
現在のフレーム（１０５）が前方予測のフレームの場合、動き推定器（１１０）は、フレーム記憶（１２０）内にバッファリングされている再構成された前フレーム（１２５）である、基準フレームに関する、現在のフレーム（１０５）のマクロブロックもしくは他のピクセルの集合の動きを推定する。代替の実施形態では、基準フレームがより後のフレームであるかもしくは現在のフレームが双方向で予測される。動き推定器（１１０）は、動きベクトルなどの動き情報（１１５）を副次的情報として出力する。動き補整器（１３０）は、動き情報（１１５）を再構成された前フレーム（１２５）に適用することによって、動きが補整された現在のフレーム（１３５）を形成する。しかし、予測は通常、完全ということはなく、動きが補整された現在のフレーム（１３５）と元の現在のフレーム（１０５）との差分が予測残差（１４５）となる。あるいはまた、動き推定器および動き補整器は、別の種類の動き推定／補整を行う。
【００２９】
周波数変換器（１６０）は、空間領域の動画像情報を周波数領域の（すなわち、スペクトルである）データに変換する。ブロックベースの動画像フレームの場合、周波数変換器（１６０）は、ＤＣＴに類似の特性を持つ以下の節で説明されている変換を行う。いくつかの実施形態では、周波数変換器（１６０）は、周波数変換をキーフレームに対する空間の予測残差の複数のブロックに適用する。周波数変換器（１６０）は、８×８、８×４、４×８、もしくは他のサイズの周波数変換を行うことができる。
【００３０】
その後、量子化器（１７０）は、スペクトルデータの係数の複数のブロックを量子化する。量子化器は一様なスカラー量子化をスペクトルデータに適用するが、その際にステップサイズはフレーム毎の基準もしくは他の基準で変化する。あるはまた、量子化器は、別の種類の量子化、例えば、非一様量子化、ベクトル量子化、もしくは非適応型の量子化をベクトルデータの係数に適用するか、または周波数変換を使用しない符号化器のシステム内で空間領域のデータを直接量子化する。適応型量子化に加え、符号化器（１００）では、フレーム落ち、適応型フィルタリング、もしくは他の手法をレート制御に使用することができる。
【００３１】
再構成された現在のフレームが後続の動き推定／補整において必要な場合、逆量子化器（１７６）は、量子化されたスペクトルデータの係数に対し逆量子化を実行する。その後、逆周波数変換器（１６６）は、周波数変換器（１６０）の演算の逆演算を実行し、（予測フレームの）再構成された予測残差もしくは再構成されたキーフレームを生成する。現在のフレーム（１０５）がキーフレームであった場合、再構成されたキーフレームは（図に示されていない）再構成された現在のフレームとみなされる。現在のフレーム（１０５）が予測されたフレームであった場合、再構成された予測残差は、動き補整をされた現在のフレーム（１３５）に追加されることによって、再構成された現在のフレームを形成する。フレーム記憶（１２０）では、次のフレームを予測する際に使用するため、再構成された現在のフレームをバッファリングする。いくつかの実施形態では、符号化器は、非ブロック化のフィルタを再構成されたフレームに適用し、フレームの複数のブロック内の不連続を適応的に平滑化する。
【００３２】
エントロピー符号化器（１８０）は、量子化器（１７０）の出力だけでなく、特定の副次的情報（例えば、動き情報（１１５）、量子化ステップサイズ）を圧縮する。標準的なエントロピー符号化手法は、算術符号化、差分符号化、ハフマン符号化、ランレングス符号化、ＬＺ符号化、辞書型符号化、およびこれらの組合せを含む。エントロピー符号化器（１８０）は、通常、異なる種類の情報（例えば、ＤＣ係数、ＡＣ係数、異なる種類の副次的情報）に対し異なる符号化手法を使用し、特定の符号化手法の範囲内で複数の符号テーブルのうちから選択することができる。
【００３３】
エントロピー符号化器（１８０）は、圧縮動画像情報（１９５）をバッファ（１９０）内に置く。バッファレベルのインジケータは、ビットレート適応のモジュールにフィードバックされる。圧縮動画像情報（１９５）は、一定のもしくは比較的一定のビットレートでバッファ（１９０）から全て読み取られ、そのビットレートで行われる後続のストリーミング用に格納される。あるいはまた、符号化器システム（１００）は、圧縮の直後に圧縮動画像情報をストリーミングする。
【００３４】
バッファ（１９０）の前後で、圧縮動画像情報（１９５）を、ネットワーク上に伝送するためにチャネル符号化することができる。チャネル符号化によって、誤り検出および訂正データを圧縮動画像情報（１９５）に適用することができる。
【００３５】
Ｂ．動画像複合化器
図２は、一般的な動画像復号化器のシステム（２００）のブロック図である。復号化器のシステム（２００）は、動画像フレームの圧縮されたシーケンスに関する情報（２９５）を受け取り、再構成されたフレーム（２０５）を含む内容を出力する。動画像復号化器の特定の実施形態では、通常、一般化された復号化器（２００）を変更して、もしくは補足して使用する。
【００３６】
復号化器のシステム（２００）は、予測されたフレームおよびキーフレームを圧縮解除する。説明のため、図２は、復号化器のシステム（２００）を通るキーフレームの経路および前方予測のフレームの経路を示している。復号化器のシステム（２００）のコンポーネントの多くは、キーフレームおよび予測されたフレームの両方を圧縮するために使用される。これらのコンポーネントにより実行される演算は、厳密には圧縮される情報の種類によって異なる。
【００３７】
バッファ（２９０）は、圧縮動画像のシーケンスの情報（２９５）を受け取り、受け取った情報をエントロピー復号化器（２８０）で利用できるようにする。バッファ（２９０）は、通常、長時間にわたりかなり一定したレートで情報を受け取り、帯域幅もしくは伝送の短時間の変動を平滑化するジッタバッファを含む。バッファ（２９０）は、再生用バッファおよび他のバッファもまた含むことができる。あるいはまた、バッファ（２９０）は、可変レートで情報を受け取る。バッファ（２９０）の前後で、圧縮動画像情報を、チャネル復号化し、誤り検出および訂正のために処理することができる。
【００３８】
エントロピー復号化器（２８０）は、エントロピー符号化され量子化されたデータだけでなく、エントロピー符号化された副次的情報（例えば、動き情報、量子化ステップサイズ）をもエントロピー復号化し、通常は、符号化器内で実行されたエントロピー符号化の逆演算を行う。エントロピー復号化手法は、算術復号化、差分復号化、ハフマン復号化、ランレングス復号化、ＬＺ復号化、辞書型復号化、およびこれらの組合せを含む。エントロピー復号化器（２８０）は、多くの場合、異なる種類の情報（例えば、ＤＣ係数、ＡＣ係数、異なる種類の副次的情報）に対し異なる復号化手法を使用し、特定の復号化手法の範囲内で複数の符号テーブルのうちから選択することができる。
【００３９】
再構成されるフレーム（２０５）が前方予測のフレームである場合、動き補整器（２３０）は、動き情報（２１５）を基準フレーム（２２５）に適用することによって、再構成されるフレーム（２０５）の予測（２３５）を形成する。例えば、動き補整器（２３０）は、マクロブロックの動きベクトルを使用することによって、基準フレーム（２２５）内のマクロブロックを見つける。フレームバッファ（２２０）は、基準フレームとして使用するために前に再構成されたフレームを格納する。あるいはまた、動き補整器は、別の種類の動き補整を行う。動き補整器による予測はめったに完全ではないため、復号化器（２００）は、さらに、予測残差を再構成する。
【００４０】
復号化器が後続の動き補整のために再構成されたフレームを必要とする場合、フレーム記憶（２２０）は、次のフレームの予測で使用するために再構成されたフレームをバッファリングする。いくつかの実施形態では、符号化器は、非ブロック化のフィルタを再構成されたフレームに適用することによって、フレームの複数のブロック内の不連続を適応的に平滑化する。
【００４１】
逆量子化器（２７０）は、エントロピー復号化されたデータを逆量子化する。一般に、逆量子化器は一様なスカラーの逆量子化をエントロピー復号化されたデータに適用するが、その際にステップサイズはフレーム毎の基準もしくは他の基準で変化する。あるいはまた、逆量子化器は、別の種類の量子化、例えば、非一様な量子化、ベクトル量子化、もしくは非適応型の量子化をデータに適用するか、または逆周波数変換を使用しない復号化器のシステム内で空間領域のデータを直接逆量子化する。
【００４２】
逆周波数変換器（２６０）は、量子化された周波数領域のデータを空間領域の動画像情報に変換する。ブロックベースの動画像フレームについては、逆周波数変換器（２６０）は、以下の節で説明される逆変換を行う。いくつかの実施形態では、逆周波数変換器（２６０）は、キーフレームに対する空間の予測残差から成る複数のブロックに逆周波数変換を適用する。逆周波数変換器（２６０）は、８×８、８×４、４×８、もしくは他のサイズの逆周波数変換を行うことができる。
【００４３】
２．ＷＭＶ９／ＶＣ−９の変換
ＷＭＶ９／ＶＣ−９標準では、動画像符号化器１００（図１）および動画像復号化器２００（図２）内で周波数変換１６０および逆周波数変換２６０として使用することができる変換を定義している。ＷＭＶ９／ＶＣ−９標準では、４種類の二次元データの変換である、８×８、８×４、４×８、および４×４の変換を定義している。この規格では、以下に要約した定義に従って、逆変換のビット完全な（ｂｉｔ−ｅｘａｃｔ）実装を必要とする。
【００４４】
Ａ．ＷＭＶ９／ＶＣ−９の変換の定義
ＷＭＶ９／ＶＣ−９で使用される２Ｄ変換は、分離可能であり、適切に定義されスケーリングされた正規直交に近い乗数行列を使用して各々の方向で変換が実行される。４点のおよび８点の一次変換に各１つずつ、合わせて２つの行列が以下のように定義される。すべての変数は整数値をとるものと仮定されている。
【００４５】
【数２】
2005327298.tif 000004
【００４６】
【数３】
2005327298.tif 000005
【００４７】
逆変換は、すべての準拠した復号化器はビット完全な出力を供給する必要があるため、形式の仕様の中で詳しく説明する。この変換は、次のように定義される。まず、逆量子化の変換行列の行が逆変換される。この後に、列の逆変換が続く。
【００４８】
Ｄは逆量子化の変換行列を表し、Ｄ１は変換の第１段の出力を表し、Ｒは行および列方向に逆変換した後の再構成された出力を表す。Ｄ、Ｄ１およびＲは、所望の変換のサイズと同じサイズで、同型な８×８、８×４、４×８および４×４の行列である。表記の誤用として、行列およびスカラーを伴う演算を、本明細書では、行列に対する要素毎の演算として定義する。同様に、行列引数をとるスカラー演算を、行列に対する要素毎のスカラー演算として定義する。行列とベクトルとの和は、行列と、値が（それぞれ行ベクトル列ベクトルを問わずベクトルに基づく）ベクトルの同一場所に配置される行もしくは列から得られるスカラーとの、要素毎の和による略記の表記である。
【００４９】
ｍ×ｎの逆変換に対する正準形式は、以下のとおりである。
【００５０】
【数４】
2005327298.tif 000006
【００５１】
分母は、１Ｄ変換の基底関数の二乗ノルム（｛４×２８８，４×２８９，４×２９２｝のうちの１つ）に最も近い２のべき乗になるように選択される。実際のノルムと分母との比（約１．１２）は１に近いので、ＩＤＣＴに使用される量子化パラメータとＷＭＶ９／ＶＣ−９の変換に使用される量子化パラメータとの間には近い一致がある。残りのすべての正規化（本質的には、１０２４／基底関数の二乗ノルムによる）は、順変換のプロセスで実行されるため、ここにそれ以上の誤りが入り込むことはない−これについては、本明細書のさらに先の方で説明する。
【００５２】
実際には、１０２４による除算は、両方の１Ｄ変換のプロセスにまたがって分割される丸め演算として実行される。さらに、１６ビットの逆変換は、後述のように第２段の行列を偶数成分と奇数成分に分けることにより精度を最大限保持して実現される。
【００５３】
【数５】
2005327298.tif 000007
【００５４】
奇数成分
【００５５】
【数６】
2005327298.tif 000008
【００５６】
および
【００５７】
【数７】
2005327298.tif 000009
【００５８】
は、要素として０、１、および−１しかとれない。Ｔ８の要素の大半は偶数なので、
【００５９】
【数８】
2005327298.tif 000010
【００６０】
は疎行列である。同様に、
【００６１】
【数９】
2005327298.tif 000011
【００６２】
は、
【００６３】
【数１０】
2005327298.tif 000012
【００６４】
と高い相関関係の構造を持つ。そこで、逆変換のプロセスに関するＷＭＶ９／ＶＣ−９の正準表現は以下のように定義される。
【００６５】
【数１１】
2005327298.tif 000013
【００６６】
偶数成分はＴｎの範囲の半分を有し、奇数成分
【００６７】
【数１２】
2005327298.tif 000014
【００６８】
は、要素として０、１、および−１を持つように制限されているため、その結果得られる変換の第２段の分子は１６ビットに制限された範囲であることを示すことができる。この付加ビットにより余分に必要な計算は大したことはない。それにもかかわらず、この変換行列の分解の結果、無視できるくらい小さなコストで計算精度が高まる。
【００６９】
４点および８点変換の奇数および偶数成分を以下に示す。
【００７０】
【数１３】
2005327298.tif 000015
【００７１】
【数１４】
2005327298.tif 000016
【００７２】
を右から掛ける乗算は、以下のように簡略化することができ、
【００７３】
【数１５】
2005327298.tif 000017
【００７４】
ただし、
【００７５】
【数１６】
2005327298.tif 000018
【００７６】
であり、これは自明なバタフライ演算である。同様に、
【００７７】
【数１７】
2005327298.tif 000019
【００７８】
を右から掛ける乗算は、単に２回の加算（および符号反転）に等しいだけであり、以下のようになるが、
【００７９】
【数１８】
2005327298.tif 000020
【００８０】
ただし、
【００８１】
【数１９】
2005327298.tif 000021
【００８２】
である。
【００８３】
Ｂ．８×８の逆変換
行方向の逆変換は、まず、以下のように実行される。
【００８４】
Ｄ１＝（Ｄ・Ｔ８＋４）＞＞３
列方向の逆変換は、Ｔ８の奇数成分を考察することにより定義され、その結果として、８個の要素の２つの共通の行を計算する。これらは、１ビット右シフトされ、その後、偶数成分の積に加算（または減算）され、それからその結果の６ビット分が切り捨てられる。演算は、次のとおりである。
【００８５】
【数２０】
2005327298.tif 000022
【００８６】
Ｃ．４×８の逆変換
ＷＭＶ９／ＶＣ−９の規約により、「４×８」とは、４列、８行の配列のことである。行方向の逆行列は、以下のように定義される４点の演算である。
Ｄ１＝（Ｄ・Ｔ４＋４）＞＞３
【００８７】
列に沿った変換の第２の部分は、８×８の変換の第２の部分に等しく、上の式（１）で定義される。
【００８８】
Ｄ．８×４の逆変換
ＷＭＶ９／ＶＣ−９の規約により、「８×４」とは、８列、４行の配列のことである。８×４の変換演算の第１段は、以下の式にしたがって１行が８つの要素の４つの各行に作用する。
Ｄ１＝（Ｄ・Ｔ８＋４）＞＞３
【００８９】
第２段に対する列方向の４点の逆変換は、以下のように定義される。
【００９０】
【数２１】
2005327298.tif 000023
【００９１】
Ｅ．４×４の逆変換
４×４の逆変換の第１段は、行方向の演算であり、以下のように定義される４点の逆変換である。
【００９２】
Ｄ１＝（Ｄ・Ｔ４＋４）＞＞３
【００９３】
列に沿った変換の第２の部分は、８×４の変換の第２の部分に等しく、上の式（２）で定義される。
【００９４】
Ｆ．逆変換の代替の実装
変換行列の奇数および偶数成分を使用した逆変換の第２段の定義は、精度を最大限保持するとともに１６ビット実装を実現する必要がある。１６ビットワードサイズが問題でなければ（例えば、特定用途向け集積回路つまりＡＳＩＣで）、１７ビットの中間結果を使用することによって、基本算術演算の一部を簡略化することができる。前節の定義と比較してビット完全な結果を出力する変換の代替の定義を得ることができる。これらの実装の第１段は元の定義の第１段と同じなので、第２段のみが以下のように定義される。
【００９５】
８×８のおよび４×８の逆変換は、以下の第２段を有する。
【００９６】
【数２２】
2005327298.tif 000024
【００９７】
８×４のおよび４×４の逆変換は、以下の第２段を有する。
【００９８】
【数２３】
2005327298.tif 000025
【００９９】
Ｇ．順変換の定義
順変換は、（ｉ）変換行列が転置されることおよび（ｉｉ）倍率が異なることを除き、類似のプロセスにより得られる。符号化器側では順変換をビット完全な仕方で実行する必要はないため、整数変数の仮定はもはや必要ではない−実際、順変換は、浮動小数点演算もしくはスケーリングされた固定小数点演算を使用して実行することができる。以下に示されている順変換の行列乗算の表現は、行列乗算で特に１６ビットレジスタを持つ整数乗算を引用する逆変換とは異なり単に解析的表現である。段の間での丸めは、必要に応じて行われることができ、この選択は符号化器に任される。順変換のプロトタイプ定義を以下に示す。
【０１００】
データ行列Ｄの４×４、４×８、８×４および８×８の変換は、これら４つの場合に対する以下の一組の等式を使って計算することができる。
【０１０１】
【数２４】
2005327298.tif 000026
【０１０２】
ただし、演算子ｏは、成分方向の乗算である。正規化行列Ｎｉｊは、以下の式で与えられる。
【０１０３】
【数２５】
2005327298.tif 000027
【０１０４】
ただし、列ベクトルｃは、以下のとおりである。
【０１０５】
【数２６】
2005327298.tif 000028
【０１０６】
ここでもまた、正規化を、すべての乗算の終わりに１回、もしくは各段別々に実行することができる。これは、符号化器での選択である。２のべき乗で出力をスケールアップすることにより、順方向の量子化プロセスでの精度を容易に上げることができる。
【０１０７】
３．ＷＭＶ９／ＶＣ−９の変換に関する高速実装
この節では、上で説明したＷＭＶ９／ＶＣ−９の変換に関する高速実装について説明する。本質的に、順変換のプロセスの高速化は、行列乗算Ｔ４ＤおよびＴ８Ｄを高速化することにより達成できる。なぜならば各々の変換段がこの形式の行列乗算であるからである。同様に、逆変換は、行列乗算
【０１０８】
【数２７】
2005327298.tif 000029
【０１０９】
および
【０１１０】
【数２８】
2005327298.tif 000030
【０１１１】
を高速化することにより高速化することができる。
【０１１２】
４点のＷＭＶ９／ＶＣ−９の変換は、行列乗算Ｔ４Ｄであり、図４に示されているようなバタフライ演算を直接に適用することにより高速実装が可能である。図５は、４点の逆変換の高速実装を示している。すなわち行列乗算
【０１１３】
【数２９】
2005327298.tif 000031
【０１１４】
である。予想どおり、信号フローグラフは、順変換の信号フローグラフを逆にしたものである。これらの図ではスケーリングは無視されている−スケーリングは、浮動小数点演算が順変換で使用される場合、乗算器に後で加えることができる。さもなければ、整数実装が必要であれば、量子化段でない場合に、順変換の両方の段の終わりにスケーリングを実行することが好ましい。逆変換では、ＷＭＶ９／ＶＣ−９準拠するために本明細書の上記の節で定義されているようなスケーリングが実行されなければならない。
【０１１５】
８点のＤＣＴは変換の高速実装を持つことが知られているが、８点のＷＭＶ９／ＶＣ−９の変換に移し変えることは容易ではない。ＷＭＶ９／ＶＣ−９の変換は、ＤＣＴに類似しているが、ビット完全性の整数の実装および要件により、知られている高速実装から直接マッピングすることは不可能である。またＤＣＴの偶数の基底関数（すなわち、基底関数０、２、４および８）が、４点のＤＣＴで続けられる入力での一連のバタフライ演算により実現できることは自明であることも知られている−この事実は８点のＷＭＶ９／ＶＣ−９の変換についてもあてはまる。したがって、８点のＷＭＶ９／ＶＣ−９の変換に関する高速実装を得る際の真の問題は、奇数基底関数の解析および統合である。この問題について以下でとりあげる。
【０１１６】
図６は、８点のＷＭＶ９／ＶＣ−９の順変換に関する高速実装を示している。（空間領域の）入力は左であり、（変換領域の）出力は右である。右上の４つの出力は、偶数基底に対応し、これは、図４の４点変換との類似性を持つ。奇数基底に対応する行列乗算は、以下のとおりである。
【０１１７】
【数３０】
2005327298.tif 000032
行は中心に関して奇対称であり、このことは第１のバタフライ演算の段で利用されることが理解できる。その結果得られる、４つのバタフライ演算による「差」の項の行列乗算は以下の式による。
【０１１８】
【数３１】
2005327298.tif 000033
４×４の行列は、以下のように分解できる。
【０１１９】
【数３２】
2005327298.tif 000034
上の分解から、図６に示されているバタフライ演算の表現が得られる。行列成分も整数値をとるので、ビット完全性は保持される。
【０１２０】
逆変換は、２つの方法のうちの１つで分解される。第１の代替手段では、順変換のフローグラフを逆にする。バタフライ演算は反転される。特に、
【０１２１】
【数３３】
2005327298.tif 000035
【０１２２】
型のバタフライ演算は、それ自身の逆演算であるが、形式
【０１２３】
【数３４】
2005327298.tif 000036
【０１２４】
のバタフライ演算は、
【０１２５】
【数３５】
2005327298.tif 000037
【０１２６】
の逆演算であり、スケーリングは両方の場合において無視される。したがって、順変換のフローグラフを逆にすることにより、図７に示されている逆変換の高速実装を得る。
【０１２７】
第２の代替手段では、Ｔｏｄｄが対称行列であることに注目する。したがって、逆変換もまた、順変換と同じ行列乗算を伴う。すなわち、順変換の場合と同じバタフライ演算および順序付けを奇数の基底関数について保持することができる。この実装は、図８に示されている。
【０１２８】
上述の反転に基づく順変換も生成することができる。これにより、図９に示されている順変換の代替の高速実装が提供される。
【０１２９】
５．コンピューティング環境
ＷＭＶ９／ＶＣ−９の変換の上で説明した高速実装は、例としてとりわけ、コンピュータ、画像および動画像の記録、送信および受信の機器、携帯型のビデオプレイヤー、ビデオ会議装置、Ｗｅｂベースの動画像ストリーミングのアプリケーションなどを含む、画像および動画像の信号処理が実行されるさまざまな装置のいずれかで実行することができる。画像および動画像の符号化手法は、ハードウェア回路に（例えば、ＡＳＩＣ、ＦＰＧＡなどの回路に）だけでなく、図１０に示されているような、コンピュータもしくは他のコンピューティング環境内で実行される（中央演算処理ユニット（ＣＰＵ）、専用のグラフィックスプロセッサ、ビデオカードなどを問わず実行される）画像および動画像処理ソフトウェアに実装することができる。
【０１３０】
図１０は、説明されているＷＭＶ９／ＶＣ−９の変換を高速実装できる好適なコンピューティング環境（１０００）の一般化された実施例を例示している。本発明は多様な汎用もしくは専用のコンピューティング環境に実装できるため、コンピューティング環境（１０００）は、本発明の使用もしくはまたは機能性の範囲に関する制限を示唆する意図はない。
【０１３１】
図１０を参照すると、コンピューティング環境（１０００）は、少なくとも１つの処理ユニット（１０１０）およびメモリ（１０２０）を備える。図１０で、この最も基本的な構成（１０３０）は、破線で囲まれている。処理ユニット（１０１０）は、コンピュータ実行可能命令を実行し、実プロセッサでも、仮想プロセッサでもよい。マルチプロセッシングシステムでは、処理能力を高めるため、複数の処理ユニットがコンピュータ実行可能命令を実行する。メモリ（１０２０）は、揮発性メモリ（例えば、レジスタ、キャッシュ、ＲＡＭなど）、不揮発性メモリ（例えば、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリなど）、もしくはこれら２つのある組合せとすることができる。メモリ（１０２０）は、説明したＷＭＶ９／ＶＣ−９の変換を高速実装するソフトウェア（１０８０）を格納する。
【０１３２】
コンピューティング環境には、機能を追加することができる。例えば、コンピューティング環境（１０００）は、記憶装置（１０４０）、１つもしくは複数の入力デバイス（１０５０）、１つもしくは複数の出力デバイス（１０６０）、および１つもしくは複数の通信接続（１０７０）を備える。バス、コントローラ、もしくはネットワークなどの相互接続のメカニズム（図に示されていない）は、コンピューティング環境（１０００）のコンポーネントを相互接続する。通常、オペレーティングシステムのソフトウェア（図に示されていない）は、コンピューティング環境（１０００）内で他のソフトウェアを実行するためのオペレーティング環境を提供し、コンピューティング環境（１０００）のコンポーネントの機能を調整する。
【０１３３】
記憶装置（１０４０）は、取り外し可能であるか、または固定であり、磁気ディスク、磁気テープもしくはカセット、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、ＤＶＤ、または情報を格納するために使用することができ、コンピューティング環境（１０００）内でアクセスできる他の媒体を備える。記憶装置（１０４０）は、量子化行列を生成し圧縮する音声符号化器を実装するソフトウェア（１０８０）に対する命令を格納する。
【０１３４】
（複数の）入力デバイス（１０５０）は、キーボード、マウス、ペン、またはトラックボールなどのタッチ式の入力デバイス、音声入力デバイス、スキャニングデバイス、またはコンピューティング環境（１０００）に入力を行う別の装置とすることができる。オーディオについては、（複数の）入力デバイス（１０５０）は、サウンドカードもしくは、アナログもしくはデジタル形式のオーディオ入力を受け入れる類似のデバイス、またはコンピューティング環境にオーディオサンプルを供給するＣＤ−ＲＯＭリーダーとすることができる。（複数の）出力デバイス（１０６０）は、表示装置、プリンタ、スピーカ、ＣＤライター、もしくはコンピューティング環境（１０００）からの出力を供給する別のデバイスとすることができる。
【０１３５】
（複数の）通信接続（１０７０）では、通信媒体を介して、別のコンピュータ処理機器（ｅｎｔｉｔｙ）と通信することが可能である。通信媒体は、コンピュータ実行可能命令、圧縮された音声もしくは動画像情報、または他のデータなどの情報を変調データ信号で伝達する。変調データ信号は、信号内の情報を符号化する方法によりその特性のうち１つまたは複数が設定もしくは変更された信号である。例えば、限定はしないが、通信媒体は、電気的搬送波、光学的搬送波、ＲＦ搬送波、赤外線搬送波、音響搬送波、もしくは他の搬送波により実装された有線もしくは無線の手法を備える。
【０１３６】
本明細書の変換および符号化／復号化手法は、コンピュータ読み取り可能な媒体の一般的な文脈において説明することができる。コンピュータ読み取り可能な媒体は、コンピューティング環境内でアクセスできる利用可能な媒体である。例えば、限定はしないが、コンピューティング環境（１０００）では、コンピュータ読み取り可能な媒体は、メモリ（１０２０）、記憶装置（１０４０）、通信媒体、およびこれらのどれかの組合せを備える。
【０１３７】
本明細書のＷＭＶ９／ＶＣ−９の高速変換を、ターゲットの実プロセッサもしくは仮想プロセッサ上のコンピューティング環境で実行される、プログラムモジュールに含まれるような、コンピュータ実行可能命令の一般的な文脈において説明することができる。一般に、プログラムモジュールは、特定のタスクを実行する、もしくはは特定の抽象データ型を実装するルーチン、プログラム、ライブラリ、オブジェクト、クラス、コンポーネント、データ構造などを含む。プログラムモジュールの機能は、さまざまな実施形態で要求されているように、組み合わせたりもしくは複数のプログラムモジュールに分割させたりすることができる。プログラムモジュールのコンピュータ実行可能命令は、ローカルもしくは分散コンピューティング環境内で実行することができる。
【０１３８】
説明のため、詳細な説明では、「決定する」、「生成する」、「調整する」、および「適用する」などのような用語を使用することによって、コンピューティング環境におけるコンピュータのオペレーションを説明する。これらの用語は、コンピュータにより実行されるオペレーションを高水準に抽象化したものであり、人間が実行する行為と混同すべきではない。これらの用語に対応する実際のコンピュータオペレーションは、実装に応じて異なる。
【０１３９】
本発明の原理を適用できる多くの可能な実施形態を鑑みて、発明者は請求項および等価物の範囲および精神の範囲内に収まりうるすべての実施形態を本発明として請求する。
【図面の簡単な説明】
【０１４０】
【図１】本明細書で説明されているＷＭＶ９／ＶＣ−９の変換の高速実装を用いる動画像符号化器のブロック図である。
【図２】本明細書で説明されているＷＭＶ９／ＶＣ−９の変換の高速実装を用いる動画像復号化器のブロック図である。
【図３】正規直交変換に対応する従来技術のバタフライ演算の図である。
【図４】スケーリングなしの４点のＷＭＶ９／ＶＣ−９の順変換に関する高速実装のブロック図である。
【図５】スケーリングなしの４点のＷＭＶ９／ＶＣ−９の逆変換に関する高速実装のブロック図である。
【図６】スケーリングなしの８点のＷＭＶ９／ＶＣ−９の順変換に関する高速実装のブロック図である。
【図７】スケーリングなしの８点のＷＭＶ９／ＶＣ−９の逆変換に関する高速実装のブロック図である。
【図８】スケーリングなしの８点のＷＭＶ９／ＶＣ−９の逆変換の他の高速実装のブロック図である。
【図９】スケーリングなしの８点ＷＭＶ９／ＶＣ−９の順変換に関する代替の高速実装のブロック図である。
【図１０】図１および２の動画像符号化器／復号化器の好適なコンピューティング環境のブロック図である。
【図１】
2005327298.tif 000065
【図２】
2005327298.tif 000066
【図３】
2005327298.tif 000067
【図４】
2005327298.tif 000068
【図５】
2005327298.tif 000069
【図６】
2005327298.tif 000070
【図７】
2005327298.tif 000071
【図８】
2005327298.tif 000072
【図９】
2005327298.tif 000073
【図１０】
2005327298.tif 000074