JP4425561B2 - イメージおよびビデオ符号化のための２−ｄ変換 - Google Patents
イメージおよびビデオ符号化のための２−ｄ変換 Download PDFInfo
- Publication number
- JP4425561B2 JP4425561B2 JP2003122704A JP2003122704A JP4425561B2 JP 4425561 B2 JP4425561 B2 JP 4425561B2 JP 2003122704 A JP2003122704 A JP 2003122704A JP 2003122704 A JP2003122704 A JP 2003122704A JP 4425561 B2 JP4425561 B2 JP 4425561B2
- Authority
- JP
- Japan
- Prior art keywords
- matrix
- transformation
- data block
- transform
- scaling
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/007—Transform coding, e.g. discrete cosine transform
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
- G06F17/147—Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
- H04N19/132—Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Pure & Applied Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Multimedia (AREA)
- Discrete Mathematics (AREA)
- Computational Mathematics (AREA)
- Algebra (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- General Engineering & Computer Science (AREA)
- Signal Processing (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Television Systems (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、信号をデジタル方式でエンコードしたり、処理したりするための技術に関する。より詳細には、本発明は、イメージおよびビデオなどの信号のエンコードおよびデコードにおける、計算効率のよい変換のクラスの構築および使用に関する。
【０００２】
【従来の技術】
変換符号化は、多数のオーディオ、イメージおよびビデオ圧縮システムにおいて使用される圧縮技術である。圧縮されていないデジタル・イメージおよびビデオは通常、２次元グリッド内に配列されたイメージまたはビデオ・フレームにおける位置の画素または色のサンプルとして表現され、あるいは取り込まれる。例えば、イメージ用の通常のフォーマットは、グリッドとして配列された２４ビットのカラー画素サンプルのストリームからなる。各サンプルは、中でもＲＧＢまたはＹＩＱなど、色空間内のグリッド内でピクセル位置での色成分を表現する集まりである。様々なイメージおよびビデオ・システムは、サンプリングについて様々な異なる色、空間および時間分解能を備えることができる。
【０００３】
圧縮されていないデジタル・イメージおよびビデオ信号は、かなりの格納容量および伝送容量を消費する可能性がある。変換符号化は、これは、信号の空間領域表現を周波数領域（または、変換領域などの他の）表現に変換すること、および次いで、変換領域表現の、一般に知覚困難なある周波数成分の分解能を低減することによって、デジタル・イメージおよびビデオの量的なサイズを低減する。このことは、一般に、空間領域におけるイメージまたはビデオの色または空間の分解能の低減に比較して、ずっと少ないデジタル信号についての劣化を生じさせる。
【０００４】
具体的には、通常の変換符号化技術は、圧縮されていないデジタル・イメージのピクセルを、固定サイズの２次元ブロックで、場合によっては他のブロックと重なりあう各ブロックに分割する。空間周波数解析を行う線形変換が各ブロックに適用され、これはブロック内で間隔のあいたサンプルを、周波数（または変換）係数のセットに変換し、これは一般に、ブロック空間の全面にわたって対応する周波数帯域におけるデジタル信号の強度を表現している。圧縮のため、変換係数を選択的に量子化することができ（すなわち、分解能を低減し、これは、係数値の最下位ビットをドロップすること、またはそうでない場合は、より高い分解能数セットにおける値をより低い分解能にマップすることなどによって行う）、その後、圧縮データ・ストリームにエントロピー符号化または可変長符号化することができる。デコードでは、変換係数は逆方向変換されて、元々の、色／空間サンプリングされた、イメージ／ビデオ信号をほぼ再構築する。
【０００５】
中でもＭＰＥＧおよびＷｉｎｄｏｗｓ（登録商標）Ｍｅｄｉａなど、多数のイメージおよびビデオ圧縮システムは、離散コサイン変換（ＤＣＴ）に基づいた変換を利用する。ＤＣＴは、ほぼ最適なデータ圧縮を結果として生じる、好ましいエネルギー圧縮特性を有することが知られている。これらの圧縮システムでは、逆ＤＣＴ（ＩＤＣＴ）が、個々のイメージ・ブロックを再構築するために、圧縮システムのエンコーダおよびデコーダにおける再構築ループにおいて使用される（例えば、非特許文献１参照）。
【０００６】
非特許文献１において定義されたＩＤＣＴ変換の欠点は、変換の計算が６４ビット浮動小数点数の行列乗算を要件とする変換の計算であり、これは計算処理的に費用のかかるものである。このことは、ＩＤＣＴが、リアル・タイムベースで、あるいは他の同様の時間制約下で、多量の圧縮データに基づいて実行されている場合、特にストリーミング・メディアおよび同様のメディア再生アプリケーションにおいて、イメージまたはビデオ圧縮システムのパフォーマンスが制限される可能性がある。
【０００７】
【非特許文献１】
"IEEE Standard Specification for the Implementations of 8x8 Inverse Discrete Cosine Transform", IEEE Std. 1180-1990, December 6, 1990
【０００８】
【発明が解決しようとする課題】
本発明の目的は、イメージおよびビデオなどの信号のエンコードおよびデコードにおいて、１および２次元変換のクラス、このような変換の構築において、効率良く計算する方法、この方法を適用した装置、および記憶媒体を提供することにある。
【０００９】
本明細書では、１および２次元変換のクラス、このような変換を構築するための技術、および、このような変換を利用したメディア符号化／復号システムが、記載される。
【００１０】
【課題を解決するための手段】
記載した変換は、計算効率（computational efficiency）を得るために、整数を使用した行列乗算演算に基づいた実装（implementations）を備えている。通常の一般的な目的およびグラフィックス・プロセッサでは、整数を使用した行列乗算演算を、浮動小数点数を使用した場合よりも、はるかに高速に実行することができる。さらに、いくつかの３２ビット・プロセッサは、同時に２つの１６ビット整数を使用した乗算演算を提供する。典型的な実装では、記載した変換は、１６ビット整数行列乗算を使用して実行される。整数の行列乗算を使用した記載した変換の実装は、メディア符号化／復号システムにおける符号化および復号化のパフォーマンスの速度を早める。
【００１１】
記載した変換を、本明細書に記載した構築手順を介して生成することができる。この構築手順は、ある制約を受ける変換係数のセットの選択に基づく変換クラスの変換を生成する。この制約は、この変換が、スケーリングされた整数の実装を有すること、完全またはほぼ完全な再構築を提供すること、ＤＣＴ近似の基底（DCT like Basis）を有すること、ｎビット（例えば、ｎは１６ビット）における表現の範囲内の係数に制限されること、ノルム（norm）において近い基底関数（basis functions）を有すること、および、その範囲からのオーバーフローに備えて十分なヘッドルームを提供すること、を含むことができる。
【００１２】
記載した構築手順を使用すると、１次元における４および８点の成分を備えた変換のセットは、２次元における８×８、８×４、４×８および４×４ブロック変換を生じさせる。１６ビット行列乗算を使用した実装を可能にする変換に基づく圧縮システムは、より計算効率のよいエンコーディングおよびデコーディングを提供することができる。
【００１３】
本発明の追加の特徴および利点は、添付の図面を参照して進行する以下の実施形態の詳細な説明から、明らかになるであろう。
【００１４】
【発明の実施の形態】
以下の記載は、計算効率のための１および２次元変換のクラス、ある基準に従うこのような変換を構築するための技術、および信号処理におけるこのような変換の使用、および詳細には、このような変換に基づいたメディア圧縮システムを対象とする。変換の例示的応用例は、Ｍｉｃｒｏｓｏｆｔ Ｗｉｎｄｏｗｓ（登録商標）Ｍｅｄｉａ Ｖｉｄｅｏ（ＷＭＶ）ファイル・フォーマットの変形形態を使用するエンコーダおよびデコーダなど、イメージまたはビデオのエンコーダおよびデコータにおけるものである。しかし、本明細書に記載したように構築された変換はこのフォーマットに限定されず、他のメディア符号化フォーマットに適用することができる。したがって、これらの変換を、汎用のイメージまたはビデオのエンコーダおよびデコーダに関連して記載するが、別法として、様々なタイプのメディア信号エンコーダおよびデコーダに組み込むことができる。
【００１５】
Ｉ．汎用ビデオ・エンコーダおよびデコーダ
図１は汎用ビデオ・エンコーダ（１００）のブロック図であり、図２は汎用ビデオ・デコーダ（２００）のブロック図である。
【００１６】
エンコーダおよびデコーダ内の複数のモジュールの間で示される関係は、エンコーダおよびデコーダにおける情報の主要な流れを示し、他の関係は、簡単にするために図示しない。特に、図１および２は、通常、ビデオ・シーケンス、フレーム、マクロブロック、ブロックなどのために使用されるエンコーダ設定、モード、テーブルなどを示す副情報を図示しない。このような副情報が、通常は、副情報のエントロピー符号化の後、出力ビットストリームにおいて送信される。出力ビットストリームのフォーマットを、Ｗｉｎｄｏｗｓ（登録商標）ＭｅｄｉａＶｉｄｅｏフォーマットまたは別のフォーマットにすることができる。
【００１７】
エンコーダ（１００）およびデコーダ（２００）はブロック・ベースであり、４：２：０マクロブロック・フォーマットを使用し、各マクロブロックは、４つのルミナンス８×８ルミナンス・ブロック（時として、１つの１６×１６マクロブロックとして処理される）および２つの８×８クロミナンス・ブロックを含む。別法として、エンコーダ（１００）およびデコーダ（２００）はオブジェクト・ベースであり、異なるマクロブロックまたはブロック・フォーマットを使用し、あるいは、８×８ブロックおよび１６×１６マクロブロックとは異なるサイズまたは構成のピクセルのセットにおいてオペレーションを実行する。
【００１８】
実装および所望の圧縮のタイプに応じて、エンコーダまたはデコーダのモジュールを追加したり、省略したり、多数のモジュールに分割にしたり、他のモジュールと結合したり、かつ／または同様のモジュールで置き換えたりすることができる。代替実施形態では、異なるモジュールおよび／または他のモジュールの構成を有するエンコーダまたはデコーダは、記載した技術のうち１つまたは複数を実行する。
【００１９】
Ａ．ビデオ・エンコーダ
図１は、汎用ビデオ・エンコーダ・システム（１００）のブロック図である。エンコーダ・システム（１００）は、カレント・フレーム（１０５）を含むビデオ・フレームのシーケンスを受信し、圧縮されたビデオ情報（１９５）を出力として生じさせる。ビデオ・エンコーダの特定の実施形態は、通常、汎用エンコーダ（１００）の変形形態（variation）または補足バージョン（supplemented version）を使用する。
【００２０】
エンコーダ・システム（１００）は、予測フレームおよびキー・フレームを圧縮する。説明のため、図１は、エンコーダ・システム（１００）を通過するキー・フレームのパス、および、前方向予測フレームのパスを示す。エンコーダ・システム（１００）のコンポーネントの多くは、キー・フレームおよび予測フレームの両方を圧縮するために使用される。これらのコンポーネントによって実行される厳密なオペレーションは、圧縮中の情報のタイプに応じて変わる可能性がある。
【００２１】
予測フレーム（ｐフレーム、双方向予測ではｂフレーム、またはインター・コード化フレーム（inter-coded frame）とも呼ばれる）は、１つまたは複数の他のフレームからの予測（または差異）の期間に対して表現される。予測残差は、予測されたものと元のフレームの間の差異である。対照的に、キー・フレーム（ｉフレーム、イントラ・コード化フレーム（intra-coded frame）とも呼ばれる）は、他のフレームに関係なく圧縮される。
【００２２】
カレント・フレーム（１０５）が前方向予測フレームであった場合、動き予測器（１１０）は、フレーム・ストア（１２０）においてバッファリングされている、再構築された先のフレーム（１２５）である、参照フレームを考慮して、カレント・フレーム（１０５）のマクロブロックまたは他のピクセルのセットの動きを予測する。代替実施形態では、参照フレームは後のフレームであり、あるいはカレント・フレームは双方向予測される。動き予測器（１１０）は、副情報として動きベクトルなどの動き情報（１１５）を出力する。動き補償器（１３０）は、動き情報（１１５）を、再構築された先のフレーム（１２５）に加えて、動き補償されたカレント・フレーム（１３５）を形成する。しかし、予測はめったに完全ではなく、動き補償されたカレント・フレーム（１３５）と元のカレント・フレーム（１０５）の間の差異は、予測残差（１４５）である。別法として、動き予測器および動き補償器は、別のタイプの動き予測／補償を適用する。
【００２３】
周波数変換器（１６０）は、空間領域ビデオ情報を周波数領域（すなわち、スペクトル）データに変換する。ブロック−ベースのビデオ・フレームでは、周波数変換器（１６０）は、以下のセクションで記載する、離散コサイン変換［「ＤＣＴ」］に類似した特性を有する変換を適用する。いくつかの実施形態では、周波数変換器（１６０）は周波数変換を、キー・フレームについての空間予測残差のブロックに適用する。周波数変換器（１６０）は、８×８、８×４、４×８または他のサイズの周波数変換を適用することができる。
【００２４】
次いで、量子化器（１７０）がスペクトル・データ係数のブロックを量子化する。量子化器は、一様なスカラー量子化を、フレーム毎のベースで、あるいは他のベースで変わるステップ・サイズを使用してスペクトル・データに適用する。別法として、量子化器は別のタイプの量子化をスペクトル・データ係数に適用し、これは例えば、非一様、ベクトル、または非適応量子化であり、あるいは空間領域データを、周波数変換を使用しないエンコーダ・システムにおいて直接量子化する。適応量子化に加えて、エンコーダ（１００）はフレーム・ドロップ、適応フィルタリング、またはレート・コントロールのための他の技術を使用することができる。
【００２５】
再構築されたカレント・フレームが、後続の動き予測／補償のために必要とされるとき、逆量子化器（１７６）は逆量子化を、量子化されたスペクトル・データ係数上で実行する。次いで、逆周波数変換器（１６６）は、周波数変換器（１６０）のオペレーションの逆を実行し、再構築された予測残差（予測フレームのもの）、または再構築されたキー・フレームを生じさせる。カレント・フレーム（１０５）がキー・フレームであった場合、再構築されたキー・フレームが、再構築されたカレント・フレーム（図示せず）として採用される。カレント・フレーム（１０５）が予測フレームであった場合、再構築された予測残差が、動き補償されたカレント・フレーム（１３５）に追加されて、再構築されたカレント・フレームが形成される。フレーム・ストア（１２０）は、再構築されたカレント・フレームを、次のフレームの予測において使用するためにバッファリングする。いくつかの実施形態では、エンコーダは、デブロッキング・フィルタを再構築されたフレームに適用して、フレームのブロックにおける不連続性を適応的に平滑化する。
【００２６】
エントロピー符号器（１８０）は、量子化器（１７０）の出力ならびにある副情報（例えば、動き情報（１１５）、量子化ステップ・サイズ）を圧縮する。通常のエントロピー符号化技術には、算術符号化、差分符号化、ハフマン符号化、ラン・レングス符号化、ＬＺ符号化、辞書型符号化、および上記の組合せが含まれる。エントロピー符号器（１８０）は通常、異なる種類の情報（例えば、ＤＣ係数、ＡＣ係数、異なる種類の副情報）について異なる符号化技術を使用し、特定の符号化技術内の複数のコード・テーブルの中から選択することができる。
【００２７】
エントロピー符号器（１８０）は、圧縮されたビデオ情報（１９５）をバッファ（１９０）に入れる。バッファ・レベル・インディケータ（標識）が、ビットレート適応化モジュールにフィードバックされる。圧縮されたビデオ情報（１９５）は、バッファ（１９０）から、一定の、あるいは相対的に一定のビットレードで消耗され、そのビットレートでの後続のストリーミングに備えてに格納される。別法として、エンコーダ・システム（１００）は、圧縮されたビデオ情報を、圧縮のすぐ後に続いてストリームする。
【００２８】
バッファ（１９０）の前または後に、圧縮されたビデオ情報（１９５）を、ネットワークを介して伝送するためにチャネル符号化することができる。チャネル符号化は、誤り検出および訂正データを、圧縮されたビデオ情報（１９５）に適用することができる。
【００２９】
Ｂ．ビデオ・デコーダ
図２は、汎用ビデオ・デコーダ・システム（２００）のブロック図である。デコーダ・システム（２００）は、圧縮されたビデオ・フレームのシーケンスについての情報（２９５）を受信し、再構築されたフレーム（２０５）を含む出力を生じさせる。ビデオ・デコーダの特定の実施形態は、通常、汎用デコーダ（２００）の変形形態または補足バージョンを使用する。
【００３０】
デコーダ・システム（２００）は、予測フレームおよびキー・フレームを圧縮解除する。説明のため、図２は、デコーダ・システム（２００）を通過するキー・フレームのパス、および、前方向予測フレームのパスを示す。デコーダ・システム（２００）のコンポーネントの多くは、キー・フレームおよび予測フレームの両方を圧縮解除するために使用される。これらのコンポーネントによって実行される厳密なオペレーションは、圧縮解除中の情報のタイプに応じて変わる可能性がある。
【００３１】
バッファ（２９０）は、圧縮されたビデオ・シーケンスについての情報（２９５）を受信し、受信された情報をエントロピー復号器（２８０）で使用可能にする。バッファ（２９０）は通常、情報を、経時的にかなり一定であるレートで受信し、帯域幅または伝送における短期の変化を平滑化するためのジッタ・バッファを含む。バッファ（２９０）は、再生バッファおよび他のバッファも含むことができる。別法として、バッファ（２９０）は情報を、変化するレートで受信する。バッファ（２９０）の前または後に、圧縮されたビデオ情報をチャネル・デコードし、誤り検出および訂正のために処理することができる。
【００３２】
エントロピー復号器（２８０）は、通常は、エンコーダにおいて実行されたエントロピー符号化の逆を適用して、エントロピー符号化された量子化データ、ならびに、エントロピー符号化された副情報（例えば、動き情報、量子化ステップ・サイズ）をエントロピー復号する。エントロピー復号技術には、算術復号、差分復号、ハフマン復号、ラン・レングス復号、ＬＺ復号、辞書型復号、および上記の組合せが含まれる。エントロピー復号器（２８０）はしばしば、異なる種類の情報（例えば、ＤＣ係数、ＡＣ係数、異なる種類の副情報）について異なる符号化技術を使用し、特定の復号技術内の複数のコード・テーブルの中から選択することができる。
【００３３】
再構築されるフレーム（２０５）が前方向予測フレームであった場合、動き補償器（２３０）は動き情報（２１５）を参照フレーム（２２５）に適用して、再構築されるフレーム（２０５）の予測（２３５）を形成する。例えば、動き補償器（２３０）はマクロブロック動きベクトルを使用して、参照フレーム（２２５）におけるマクロブロックを発見する。フレーム・バッファ（２２０）は、先の再構築されたフレームを、参照フレームとして使用するために格納する。別法として、動き補償器は別のタイプの動き補償を適用する。動き補償器による予測はめったに完全ではなく、そのためデコーダ（２００）はまた予測残差をも再構築する。
【００３４】
デコーダが、再構築されたフレームを後続の動き補償のために必要とするとき、フレーム・ストア（２２０）は、再構築されたフレームを、次のフレームの予測において使用するためにバッファリングする。いくつかの実施形態では、エンコーダは、デブロッキング・フィルタを再構築されたフレームに適用して、フレームのブロック内の不連続性を適応的に平滑化する。
【００３５】
逆量子化器（２７０）は、エントロピー復号されたデータを逆量子化する。一般には、逆量子化器は一様なスカラー逆量子化を、フレーム毎のベースで、あるいは他のベースで変わるステップ・サイズを使用して、エントロピー復号されたデータに適用する。別法として、逆量子化器は別のタイプの逆量子化をデータに適用し、これは例えば、非一様、ベクトル、または非適応逆量子化であり、あるいは空間領域データを、逆周波数変換を使用しないデコーダ・システムにおいて直接逆量子化する。
【００３６】
逆周波数変換器（２６０）は、量子化された周波数領域を空間領域ビデオ情報に変換する。ブロック−ベースのビデオ・フレームに対して、逆周波数変換器（２６０）は、以下のセクションで記載する逆方向変換を適用する。いくつかの実施形態では、逆周波数変換器（２６０）は逆周波数変換を、キー・フレームの空間予測残差のブロックに適用する。逆周波数変換器（２６０）は、８×８、８×４、４×８または他のサイズの逆周波数変換を適用することができる。
【００３７】
ＩＩ．変換の概観
図３は、図１および２のビデオ・エンコーダ１００およびデコーダ２００において使用された２次元変換３００および逆方向変換３１０を例示する。変換３００および逆方向変換３１０は、以下に記載するようなある制約を受けて構築された変換のクラスに基づいている。
【００３８】
２次元変換３００は、メディア・コンテンツの空間的に関係付けられたサンプルとして表現されたメディア・コンテンツの２次元（ｎ×ｍ）ブロック３２０を、変換領域ブロックに変換する。例えば、ブロックは、一様に間隔のあいたグリッド位置に配列されたカラー・サンプル（ピクセル）のアレイとして表現することができるような、デジタル・イメージまたはデジタル・ビデオ・フレームの一部であるとすることができる。これは、メディア・コンテンツの空間領域表現と呼ばれる。この変換ブロックもまたｎ×ｍサンプルからなり、本明細書では、メディア・コンテンツの変換領域表現と称する。
【００３９】
逆方向変換３２０は、サンプルのブロックを変換領域から、元の、あるいは空間領域に戻すように変換する。
【００４０】
ＩＩＩ．変換ベースの符号化
一般に、例えば、上述したビデオ・エンコーダおよびデコーダにおけるような、メディア・コンテンツの変換ベースの符号化４００は、変換３００（図３）および逆方向変換３１０（図３）を量子化と共に利用して、メディア・コンテンツを圧縮された形式でエンコードする。変換ベースの符号化は最初に変換ステージ４１０内の変換３００を、変換領域に変換するためにメディア・コンテンツの入力ブロックに適用する。次いで、変換ベースの符号化は、量子化ステージ４２０で、ある変換領域サンプル（例えば、メディア・コンテンツについてより少ない知覚可能な劣化を生じさせる変換領域サンプル）の量子化を実行する（すなわち、分解能を低減する）。量子化された変換領域サンプルを使用して、圧縮された形式のメディア・コンテンツを生成することができる。
【００４１】
変換ベースの符号化４００はまた、逆量子化ステージ４３０および逆方向変換ステージ４４０も有する。逆量子化ステージ４３０で、変換ベースの符号化は、量子化された変換領域サンプルを、それらの元の分解能に戻すようにマップし、逆方向変換３１０の準備をする。変換ベースの符号化は、逆方向変換ステージにおいて、逆方向変換を逆量子化された領域サンプルにおいて実行して、次いでメディア・コンテンツ・ブロックを再構築する。
【００４２】
変換ベースの符号化４００を、ビデオ・エンコーダおよびデコーダにおける様々な点で実行することができる。例えば、ビデオ・エンコーダは、また、差分符号化およびインター・フレーム符号化技術において使用するために、逆量子化および逆方向変換ステージを有する再構築ループを含むこともできる。
【００４３】
ＩＶ．計算効率のよい逆方向変換の実装
このとき、図５を参照すると、変換３００および逆方向変換３１０（図３）は、好ましくは、前−乗算変換行列（Ｔ）による（変換３００のための空間領域サンプルの、かつ、逆方向変換のための変換領域サンプルの）２次元データ・ブロックの前−乗算５１０、および、後−乗算変換行列（Ｔ’）による後−乗算５３０として実装される。前−乗算変換行列（Ｔ）の行は変換の基底関数を表し、これが前−乗算５１０におけるデータ・ブロックの列に適用される。同様に、後−乗算変換行列（Ｔ’）の列は、後−乗算５３０におけるデータ・ブロックの行に適用される変換基底関数（transform basis functions）である。
【００４４】
計算効率のため、変換行列（ＴおよびＴ’）およびデータ・ブロックは、コンピュータまたはグラフィックス・プロセッサの整数乗算演算を使用してその行列乗算が実行されることを可能にする範囲内の整数値から構成される。例えば、１６ビット整数乗算演算を提供する多数の現在のプロセッサでは、好ましくは、１６ビット整数乗算演算を使用してその行列が実行されることを可能にする範囲内の整数から構成される。別法として、行列は、他のサイズの整数の整数乗算演算を提供するプロセッサのための、より小さい、あるいはより大きい範囲における整数から構成されることも可能である。
【００４５】
整数から構成される変換基底関数によるデータ・ブロックの前−乗算および後−乗算は、結果として生じるデータ・ブロック値をより大きい範囲において生じさせる。実装５００は、基底関数乗算によるこの拡大を、それぞれ前乗算および後乗算の後にスケーリング演算５２０、５４０を使用して補償する。計算効率のため、スケーリング演算５２０、５４０は、シフト演算（実際には、２のべき乗による除算）であることが好ましく、これは値をいくつかのビット位置Ｓ１およびＳ２だけそれぞれシフトさせる。
【００４６】
例示した実装５００では、データ・ブロック内の値は、前−乗算５１０の入力、スケーリング５２０、後−乗算５３０、スケーリング５４０および出力での、それぞれＡ〜Ｅとして表されたビット・サイズを有する整数である。例えば、前−乗算ステージ５１０の入力でのデータ・ブロックの値は、サイズがＡビットである整数である。
【００４７】
この変換の設計において基礎をなす原理は、順方向変換および逆方向変換において、後者が、制約された精度の整数の演算という態様で実装され、（有効な量子化および逆量子化に従う）対応する順方向変換プロセスによって生成されている入力データについての有意味の結果を生成するように保証されている、そのような逆方向変換と順方向変換のペアとしてのその実装５００である。
【００４８】
Ｖ．変換の構築
計算効率のよい変換は、以下に記載するある制約に従う、変換基底関数のための係数値（すなわち、前−乗算行列Ｔおよび後−乗算行列Ｔ’における値）を選択することによって構築される。この構築技術は、範囲が制限された、直交（orthogonal）または双直交変換（bi-orthogonal transforms）を生じさせることができる。
【００４９】
制約。
スケーリングされる整数の実装。この変換係数は、２のべき乗によるスケーリングを可能とする、整数である。これにより、標準のコンピュータにおける実装が容易になる。
【００５０】
完全な再構築。量子化（例えば、図４における量子化および逆量子化ステージ４２０、４３０）がない場合、逆方向変換は元の空間領域データを、変換によって生成された変換領域データから、完全に再構築する。データを圧縮するために使用される変換のための主要な要件は、量子化および丸めがない場合に、順方向および逆方向変換が完全な再構築ペアを形成することである。これは、正規直交性（orthonormality）または双正規直交性（biorthonormality）を通じて保証されることができる。前者の場合、順方向および逆方向変換は等しいが、後者ではこれらは異なる。
【００５１】
ＤＣＴ近似の基底（DCT like Basis）。変換および逆方向変換は、ＤＣＴに類似した特性を有する。よい符号化パフォーマンスのために、変換がＤＣＴを厳密に近似することが好ましい。ＤＣＴは、ほぼ最適なデータ圧縮を結果として生じる好ましいエネルギー圧縮特性を有することが知られている。ＤＣＴのＤＣ基底関数は定数値である。これは、「ゼロ番目」の基底の変換係数が定数値を有するように制約する。
【００５２】
範囲。データ値および変換係数の範囲は、（例えば、１６ビット整数演算において）ターゲット・コンピュータまたはグラフィックス・プロセッサにおける計算効率のよい整数乗算演算を使用した実装を可能にする。好ましい実装では、これらの値は、逆方向変換の１６ビット実装を可能にする範囲に制約される。この実装では、１６ビット整数演算は、１６ビット累算器、および、符号付きモジュロまたは基数２１６へのロールオーバ演算（rollover arithmetic）、すなわち、［−３２７６８．．．３２７６７］のデータ範囲を有する累算器、により実行することができる整数の算術演算である。２個の１６ビット数の乗算の結果は、積の保存されている下位１６ビットのみとなる。別法として、この範囲は、別のビット・サイズの整数演算をサポートする他のターゲット・プラットフォームについて変えることができる。
【００５３】
変換基底関数による、データ・ブロック内のサンプルについての乗算は、範囲に拡張をもたらし、その範囲は、変換基底関数内のサンプル（点）の数によって変わる。ビデオ圧縮システムでは、８×８、４×８、８×４および４×４点の２次元（Ｎ×Ｍ点）変換が一般に使用される。４および８点変換の間で、８点変換は、より厳しい制約を整数変換係数の範囲に課す。これは、Ｎ＞Ｍであるとき、Ｎ点変換に関連付けられた拡張は、Ｍ点変換に関連付けられたものより大きいからである。ＤＣ値は、Ｎ点変換では
【００５４】
【数２５】
【００５５】
として拡張する。したがって、８点変換がより厳しい制約を提示するので、最初に８点変換を考察する。
【００５６】
例えば、ビデオ圧縮システムにおける空間領域データ・ブロック・サンプルの共通範囲は［−２５５．．．２５５］であり、これは９ビットの分解能である。［−２５５ ２５５］の範囲に対応するこのような９ビット入力では、８×８変換は、範囲［−２０４７ ２０４７］内の値を取ることができ、１２ビットの精度を必要とする。実際には、各８点変換は１．５ビットの拡張の結果となる。２次元の８×８変換では、８点変換が、前−乗算ステージ５１０（図５）での行変換および後−乗算ステージ５３０（図５）での列変換により、２度適用され、結果として生じる変換領域サンプルが３ビットだけ（１２ビットの分解能に）拡張される。
【００５７】
より詳細に図５を参照すると、例示的実施において入力Ａで逆方向変換のために入力された変換領域データ・ブロックは、１２ビットの範囲を有するのに対して、出力Ｅで再構築された空間領域データ・ブロックは９ビットの範囲を有する。２つの逆方向変換演算（前−乗算５１０および後−乗算５３０）は、｜Ｔ｜２のスケーリングまたは範囲の拡張を引き起こし、これはｓ１およびｓ２ビットの２つのシフトによってそれぞれ補償される。これには、変換によって引き起こされた範囲の拡張が、補償のスケーリングにほぼ等しいか、または｜Ｔ｜２≒２（ｓ１＋ｓ２）であることが必要とされる。変換行列（Ｔ）が正規化された行列である（ただし、Ｔ１＝Ｔ／｜Ｔ｜）と仮定すると、前−乗算の後に結果として生じるデータ・ブロック（Ｂ＝Ｔ・Ａ）の動的範囲（dynamic range）は約１０．５ビットである。したがって、結果として生じるデータ・ブロック（Ｂ）は、１０．５＋ｌｏｇ２（｜Ｔ｜）ビットの範囲を有する。同様に、後−乗算データ・ブロック（Ｄ＝Ｃ・Ｔ’）は９＋２・ｌｏｇ２（｜Ｔ｜）−ｓ１ビットの範囲を有する。１６ビット整数演算を使用した、計算効率のよい逆方向変換の実装のために、以下の比較式が必要とされる（ｌｏｇ２（｜Ｔ｜）をＬによって示す）。
１０．５＋Ｌ＜＝１６ （１）
９＋２Ｌ−ｓ１＜＝１６ （２）
２Ｌ≒ｓ１＋ｓ２ （３）
【００５８】
したがって、続いて（９＋ｍ＜＝１６）となり、すなわち、ｍ＝６、かつＬ＜＝５．５または｜Ｔ｜＜＝２０４８である。
【００５９】
さらに、逆方向変換のＤＣ基底関数が［ｄｄｄｄｄｄｄｄ］によって与えられるようにすることにより、範囲制約は、８ｄ２＜＝２０４８またはｄ＜＝１６であることを必要とする。
【００６０】
基底関数のノルム。変換のための基底関数のそれぞれはノルムにおいて非常に近い。
【００６１】
一般的な直交（orthogonal）および双直交（biorthogonal）整数変換では、個々の基底関数に対応する変換行列Ｔの個々の行は、個々のノルムを有することができるようにされる。この柔軟性の背後にある考えは、複数のノルムの間の不適合の影響を、量子化および逆量子化中に順方向および逆方向変換について取り消すことができるということである。実際には、正規化は２つの難点を提示する。すなわち、（１）正規化により、特にデコーダ側に複雑さが追加されること、および、（２）正規化乗数が小さい整数でない限り、短い整数（short integer）（１６ビット）実装については正規化が不可能となることである。
【００６２】
すべての基底関数のノルムが一致していることが必要とされる場合、追加の再正規化は不要である。いかなる正規化項も、逆量子化の中に要因としており込むことができる。量子化値による効果は、このプロセスにおいて、少し変えることができる（すなわち、ある量子化点（ＱＰ）のレート−歪み点は、例えば正規化された完全精度変換を使用して計算されたその元の値から、離れているが、レート−歪み（Ｒ−Ｄ）曲線に沿って、動かすことができる）。
【００６３】
４および８点変換について言えば、同じ論理が当てはまる。４点か８点かにかかわらず、すべての基底関数のノルムが一致しており、正規化を取り出すことができるように、同様であることが必要とされる可能性がある。実際には、適切に小さい整数の基数について、すべての基底関数のすべてのノルムが一致しているという制約を受ける変換係数のセットを発見することは不可能である。ここでの制約は、基底関数がノルムにおいて非常に近いことを許容することによって、ささやかな柔軟性を可能とする。
【００６４】
ヘッドルーム。１つの実装では、順方向変換への有効な入力（空間領域データ・ブロック）の範囲は９ビットであるが、量子化（図４のステージ４２０）の後に再構築されたデータ・ブロックが、＋２５５ないし−２５５の範囲を上回るかあるいは下回るようにオーバーフローする可能性がある。短い整数（short integer）の実装は、このことを考慮に入れて、このような状況のために十分なヘッドルームを残すことが必要とされる。
【００６５】
要約すると、本明細書に記載した構築技術は、以下の制約を受ける変換を生じさせる。すなわち、（１）スケーリングされた整数の実装、（２）正規直交性または完全な再構築、（３）エネルギー圧縮についてのＤＣＴ近似の基底、および（４）整数ベースの実装のための制限された制約（例えば、１６ビット整数演算における）である。所与の範囲制限では、上の制約のすべてを満たすことは困難である。特定の例として、これらの制約の最初の３つを満たし、ならびに１６ビットに制限された範囲にある、変換を構築することは可能ではない。以下に記載する構築プロセスは、効率的な、範囲制限された、変換を、これらの制約のうち１つまたは複数をわずかに緩和すること（例えば、例示した変換の実装において、正規直交性の制約を緩和すること）によって、生み出す。例示した変換の実装では、変換のペアが直交（orthogonal）であることのみが必要とされるが、そのノルムをわずかに異なるようにすることができる。この追加の柔軟性により、変換のための探索空間が拡大され、これにより、他の制約を満たす効率的な範囲制限された変換の構築が実現可能となる。以下でさらに論じるように、ノルムにおけるわずかな不一致の影響を、量子化ステージ中に再正規化することによって取り消すことができる。この再正規化は、量子化ステージにおいて実装されているので、結果として複雑さの増大は、エンコーダのみがこうむることになる。これにより、圧縮能率を維持しつつ、システム全体の複雑さが、かなり低減する。
【００６６】
構築。
図６を参照すると、これらの制約に従う計算効率のよい変換を構築するプロセス６００は、図５の変換の実装５００についての前−乗算および後−乗算の変換行列（ＴおよびＴ’）のための直交変換係数のセットを生じさせる。この例示的な計算効率のよい変換の実装を生成するための、この構築手順において使用された許容差のしきい値のいくつかは任意であり、これらをさらに緩和して、さらなる解に達するようにすることができる。しかし、緩和されたしきい値により、このような代替変換の実装は、さらに悪い符号化パフォーマンスを有する可能性がある。
【００６７】
この手順６００を使用して構築された計算効率のよい変換の例示的セットは、４および８点の基底関数を使用した２次元変換を含む。４および８点の基底関数に基づいて、８×８、４×８、８×４および４×４変換のための変換行列が生成される。しかし、この制約プロセスを別法として、他の数の点またはブロック・ディメンションを有する基底関数による変換を生じさせるように変更することができる。
【００６８】
構築プロセス６００の第１のステップ６１０は、ＤＣ基底関数に属する一定の乗数を発見することである。４および８点の基底関数では、一定の乗数がそれぞれｄ４およびｄ８と示される。上で論じたノルム制約により、これらの一定の乗数は、ｄ８≦１６の場合に、
【００６９】
【数２６】
【００７０】
として関係付けられる。このノルム制約を約１％以内で満たす整数のペア｛ｄ４，ｄ８｝は、｛７，５｝、｛１０，７｝、｛１７，１２｝および｛２０，１４｝のみである。８点変換では、ＤＣ基底の２乗ノルムは
【００７１】
【数２７】
【００７２】
である。したがって、これらの整数ペアを有するＤＣ基底について許容可能な８点２乗ノルムは、２００、３９２、１１５２および１５６８である。
【００７３】
構築プロセス６００の第２のステップ６２０は、変換の奇数基底関数（odd basis functions）（奇数の「周波数」とも呼ばれる）を決定することである。上で論じた「ＤＣＴ近似の基底」の制約にしたがって、変換は、ＤＣＴ変換に類似した特性を有するべきであり、これは８点ＤＣＴ変換では、以下の奇数基底関数を有する。
【００７４】
【数２８】
【００７５】
４つの定数値が、８点ＤＣＴのこれらの奇数基底関数を決定する。基数の構造により、定数Ｃ１、Ｃ２、Ｃ３およびＣ４を使用して一意の絶対係数を置き換えて、以下の基底を与えることができる。
【００７６】
【数２９】
【００７７】
構築は、以下の条件を使用して、空間｛Ｃ１，Ｃ２，Ｃ３，Ｃ４｝上を探索することによって進行する。
【００７８】
１．基底の直交性。偶数周波数項を有する奇数項の直交性は、所与の偶数周波数の相補的構造に事実上含まれている。したがって、この条件は、減少して、奇数基底関数の直交性になる。
【００７９】
２．ＤＣＴ近似の基底。ベクトル［Ｃ１ Ｃ２ Ｃ３ Ｃ４］は、対応するＤＣＴ係数ベクトル［０．４９０４ ０．４１５７ ０．２７７８ ０．０９７５］と「十分」に相関する。相関は、複数のベクトルの間の角度のコサインによって測定され、可能な限り１に近くなることが望ましい。相関についての他の測定も使用することができる。
【００８０】
３．奇数の基数のノルムがＤＣノルムに密接に適合する。これを以下のように表すことができる。
【００８１】
【数３０】
【００８２】
ノルムの５％の許容差（条件３）および０．９９の許容可能な相関「コサイン」（条件２）内で、８点奇数基底関数のための制約を満たす整数係数のセットはただ１つしかない。このセットは［１６ １５ ９ ４］であり、５７８のノルムを有し、これは明確に所望の５７６に非常に近い。この相関は、好ましい０．９９８４である。
【００８３】
構築プロセス６００の第３のステップ６３０は、変換のための偶数基底関数（even basis functions）または偶数周波数を決定することである。再度、ＤＣＴ近似の基底の制約によれば、偶数基底関数は、ＤＣＴ変換のものに十分相関するべきである。８点ＤＣＴ変換では、偶数基底関数は以下のようになる。
【００８４】
【数３１】
【００８５】
周波数２および６におけるノルム制約は、
【００８６】
【数３２】
【００８７】
によって与えられる。整数ペア｛１６，６｝はこのノルム制約を約１％以内まで満たす。
【００８８】
結果として生じる（ステップ２および３で決定された整数係数を使用する）８点変換行列は、以下のようになる。
【００８９】
【数３３】
【００９０】
構築プロセス６００の第４のステップ６４０は、４点変換を生成する。上（ステップ６１０〜６３０）で論じたように生成された８点変換では、ＤＣ基底関数の一定の乗数はｄ８＝１２である。したがって、４点変換のための一定の乗数はｄ４＝１７である。ＤＣＴ近似の基底では、これはＤ１およびＤ２という係数を、生成される以下の基底関数において残す。
【００９１】
【数３４】
【００９２】
上の基底関数による行列は、いかなる選択のＤ１およびＤ２についても本質的に直交している。しかし、ＤＣＴ近似の変換の制約によれば、これらの係数が、
【００９３】
【数３５】
【００９４】
に等しいＤＣＴ回転因子（すなわち、Ｄ１／Ｄ２の比率）によって関係付けられる。さらに、これらの係数はノルム制約Ｄ１２＋Ｄ２２≒５７８に従う。直交性、ＤＣＴ近似の基底およびノルム制約を約１％以内まで満たす整数のペアは、整数ペア｛２２，１０｝である。これは、４点変換について以下の基底関数を生じる。
【００９５】
【数３６】
【００９６】
ＶＩ．変換の実装（続き）
図５に戻ると、上の構築プロセス６００を使用して生成された変換行列は本質的に変換を定義する。２次元変換では、基底関数が各ディメンションにおいてサンプル・データ・ブロックに適用される。例示した変換の実装５００では、基底関数が前−乗算５１０においてサンプル・データ・ブロックの行に適用され、次いで後−乗算５３０でサンプル・データ・ブロックの列に適用される。この変換が直交するように構築されるので、一致した変換行列が、順方向３００および逆方向３１０の変換について使用される。非ユニタリ・ノルムを有する変換基底関数なので、例示した実装は、また、スケーリング・ステージ５２０および５４０を逆変換で含んで、変換によって導入された範囲の拡張を補償する。このような範囲制限された実装を、順方向変換のために使用することもできるが、ビデオ符号化においては、順方向変換における範囲制限はしばしば冗長である。エンコード・プロセスはデコードより低速であり、かつエンコーダで使用可能な計算リソースはしばしばデコーダのものより桁違いに高いので、エンコーダをより高い精度（例えば、３２ビット）の整数または倍精度浮動小数点で、実装することができる。したがって、以下の考察ではまず、上で記載した変換行列を使用した逆方向変換の例示的実装を考察する。
【００９７】
逆方向変換の実装。
先に記載したような変換の実装５００では、前−乗算ステージ５１０において、適切なサイズの変換行列（例えば、８×８データ・ブロックでは上の行列Ｔ８）による行列乗算を実行することによって、変換領域データ・ブロックの行（以下の考察ではＤと示す）が逆方向変換される。後−乗算ステージ５３０において、同じくこの変換行列による行列乗算を実行することによって、変換領域データ・ブロックの列が逆方向変換される。この順序付けを逆にすることができるが、これは不適合の結果となる可能性が高い。前−乗算および後−乗算ステージのための変換行列は、上に記載したように構築された変換行列である。
【００９８】
スケーリング・ステージ５２０および５４０では、例示的変換の実装におけるスケーリングが、上で論じた、スケーリングされた整数の実装の制約（すなわち、スケーリングは、標準システムおよびグラフィックス・プロセッサの計算を容易にするために、２のべき乗による）に従って、決定される。したがって、スケーリングは、変換行列の基底関数の２乗ノルムに最も近い２のべき乗となるように選択される。
【００９９】
より詳細には、逆方向変換のための標準的な公式を以下のように表すことができる。
【０１００】
【数３７】
【０１０１】
ただし、Ｄは、逆方向変換への入力（Ａ）での変換領域データ・ブロックを示す。以下の考察では、Ｄ１は、変換の実装５００の第１の乗算ステージ５１０から出力されたデータ・ブロックを表し、Ｒは、行および列関連の逆方向変換の後の、再構築された出力を表す。分母ｓはスケーリング係数である。Ｄ、Ｄ１およびＲは、同形の８×８、８×４または４×８行列である。表記法において、行列およびスカラーを含む演算は、行列におけるエントリ関連の演算である。同様に、行列引数を有するスカラー演算は、行列におけるエントリ関連のスカラー演算である。
【０１０２】
分母ｓは、基底関数の２乗ノルムに最も近い２のべき乗となるように選択される。８×８の逆方向変換では、１次元の８点基底関数の２乗ノルムの値は｛１１５２，１１５６，１１６８｝である。したがって、分母が１０２４となるように選択され（すなわち、ｓ＝１０２４）、これはこれらの２乗ノルム値に最も近い２のべき乗である。実際のノルムとこの分母の間の比率（すなわち、ノルム／ｓ≒１．１２）は１に近いので、標準ＩＤＣＴについて使用された量子化パラメータと、例示した変換の実装について使用されたものの間に密接な対応がある。すべての残りの正規化（本質的には、１０２４／基底関数の２乗ノルムによる）が、以下に記載する順方向変換プロセスで実行されるので、誤りが付加されることはない。
【０１０３】
上の範囲制約の考察によれば、逆方向変換の入力での変換領域データ・ブロックＤは、例示した実装において１２ビットの範囲を有する。（正規化のため、順方向変換から生じた変換領域データ・ブロックが実際には±２０４８／１．１２に減らされる。）標準的な中間行列（１次元における逆方向変換の後のもの）は、以下のようになる。
【０１０４】
【数３８】
【０１０５】
これは１０．５ビットよりわずかに低い範囲を有する。
【０１０６】
１つの逆方向変換の実装５００では、スケーリング・ステージ５２０および５４０はそれぞれ、データ・ブロック値を５ビット位置だけ切り捨てるか、あるいはシフトすること（実際には、３２による除算）ができ、これは同時に（１０２４による除算について）１０ビット位置だけシフトする。これは、乗算ステージ５１０および５３０での範囲制約を１６ビット範囲内に維持する。
【０１０７】
代替実装は、第２の後−乗算ステージのための演算精度を保持し、これは、第１のスケーリング・ステージ５２０でのスケーリングまたは丸めの量を減らすことによって行う。第１の乗算ステージの後の結果のデータ・ブロックＤ１は、１０．５ビットの範囲を使用し、８点変換は範囲を４ビットにより拡張するので、スケーリングの多くとも１ビット少ないものを第１のスケーリング・ステージで許容して、両方の乗算ステージで１６ビット範囲制約内に残るようにすることができる。したがって、代替実装は、第１のスケーリング・ステージ５２０で４ビットだけ、第２のスケーリング・ステージ５４０で６ビットだけシフトすることができる。この変換の標準的な表現は、このとき、以下の通りである。
【０１０８】
【数３９】
【０１０９】
この代替実装は、追加の精度のビットがＤ１で保持されることを可能にする。この同じスケーリングを４点変換のために使用することができ、これは、４点変換行列における最大乗数が、どうにか、なお、使用可能なヘッドルーム（４．５ビット）内であるからである。
【０１１０】
第２の追加の精度のビットを中間データ・ブロックＤ１で保持するために、さらなる代替実装は変換行列を次のように分解する。
【０１１１】
【数４０】
【０１１２】
ここで、奇数成分行列
【０１１３】
【数４１】
【０１１４】
および
【０１１５】
【数４２】
【０１１６】
は０、１および−１のみをエントリとして有することが許容される。Ｔ８のエントリの大部分は偶数であるので、
【０１１７】
【数４３】
【０１１８】
はスパース（sparse）行列である。同様に、
【０１１９】
【数４４】
【０１２０】
は、
【０１２１】
【数４５】
【０１２２】
に非常に相関された構造を有する。このさらなる代替逆方向変換の実装の標準的な表現が、このとき以下のように定義される。
【０１２３】
【数４６】
【０１２４】
第１のスケーリング・ステージ５２０はこのとき３ビットのみ下にシフトし、第２の乗算ステージ５３０のための余分の精度を保持する。偶数成分はＴ８の範囲の半分を有するので、また、奇数成分
【０１２５】
【数４７】
【０１２６】
は、０、１および−１のエントリを有するように制限されるので、変換の第２のステージにおいて結果として生じる分子は、１６ビットに制限された範囲である。この方法には、精度Ｄ１での余分の精度のビットのために受ける、計算上の小さい不利がある。それにもかかわらず、この変換行列の分解は、結果として改善された演算精度をごくわずかなコストでもたらす。
【０１２７】
他の代替実装では、変換Ｔをより一般に成分変換行列ＴａおよびＴｂに分解することができ、これらが変換基底Ｔに、Ｔ＝２ｘ・Ｔａ＋Ｔｂとして関係付けられる。この変換の計算は以下の通りである。
【０１２８】
【数４８】
【０１２９】
次いでこれを以下のように定義することができる。
【０１３０】
【数４９】
【０１３１】
この計算を、行列乗算およびシフト演算を使用して、以下のように実装することができる。
（Ｄ・Ｔａ＋（（Ｄ・Ｔｂ）＞＞ｘ））＞＞（ｙ−ｘ）
【０１３２】
変換Ｔ８の特定の代替実装に戻ると、８点変換の奇数および偶数成分が以下のように示される。
【０１３３】
【数５０】
【０１３４】
【数５１】
【０１３５】
が２つの独立したゼロでない列のみを有することに留意されたい。
【０１３６】
【数５２】
【０１３７】
による後乗算は、以下のように２つの加算（および否定）のみと同等である。
【０１３８】
【数５３】
【０１３９】
ただし、以下の通りである。
【０１４０】
【数５４】
【０１４１】
４点逆方向変換の偶数および奇数成分は、以下の通りである。
【０１４２】
【数５５】
【０１４３】
このさらなる代替実装では、８×８逆方向変換のための行関連または前−乗算ステージ５１０および第１のスケーリング・ステージ５２０は、以下の演算を実行する。
Ｄ１＝（Ｄ・Ｔ８＋４）＞＞３
【０１４４】
この逆方向変換の実装における列関連または後−乗算ステージ５３０およびスケーリング・ステージ５４０は、最初に、Ｔ８の奇数成分を見て８つの要素の２つの共通の行を計算することによって定義される。これらは右に１ビットだけシフトされ、次いで、この結果が６ビットだけ下に丸められる前に、偶数成分の積に加算される（あるいはそれから減算される）。したがって、これらのステージにおいて実行される演算は以下のように表現される。
【０１４５】
【数５６】
【０１４６】
さらなる代替実装における４×８逆方向変換（本明細書で使用される規定によれば、これは４列および８行を有するアレイを指す）では、行関連または前−乗算ステージ５１０およびスケーリング・ステージ５２０は、以下のように定義される４点演算を実行する。
Ｄ１＝（Ｄ・Ｔ４＋４）＞＞３
【０１４７】
この変換の第２の部分では、列関連または後−乗算ステージ５３０およびスケーリング・ステージ５４０は、上に記載した８×８逆方向変換のためのものに等しい。
【０１４８】
８×４逆方向変換では、さらなる代替実装は、行関連ステージ５１０およびスケーリング・ステージ５２０において、４行／８列の変換領域データ上で、以下に従って演算する。
Ｄ１＝（Ｄ・Ｔ８＋４）＞＞３
【０１４９】
列関連ステージ５３０およびスケーリング・ステージ５４０のための４点逆方向変換は、以下のように定義される。
【０１５０】
【数５７】
【０１５１】
４×４逆方向変換では、４×４逆方向変換のステージ５１０、５３０が、４×８逆方向変換の行関連ステージ５１０および８×４逆方向変換の列関連ステージ５３０それぞれについて上に記載したように、実装される。
【０１５２】
順方向変換の実装。
スケーリング・ステージを含む図５に例示したような、範囲制限された実装を順方向変換にも適用することができるが、ビデオ符号化においては、このような手順はしばしば冗長である。エンコード・プロセスはデコードより低速であり、かつエンコーダで使用可能な計算リソースはしばしばデコーダのものより桁違いに高いので、エンコーダをより高い精度（例えば、３２ビット）の整数または倍精度浮動小数点で実装することができる。すなわち、順方向変換の実装において、スケーリング・ステージ５２０、５４０を省略することができる。
【０１５３】
図７に示す、好ましい順方向変換の実装では、再正規化ステージ７４０が順方向変換側で（行関連および列関連乗算７１０および７３０の後に）実行されて、再構築において、変換自体が最低量の誤りをもたらすように保証される。これにより、基底関数のノルムにおけるわずかな差異を補償し、使用可能な計算リソースがより少ない可能性のあるデコーダでの計算の負担を減らす。別法として、十分な計算リソースをデコードで設けているシステムでは、補償（変換データのスケーリング）をデコーダで実行することができる。
【０１５４】
以下の考察では、記号
【０１５５】
【数５８】
【０１５６】
は、等しいサイズの行列の要素関連の積を示す。元の２−Ｄ信号（サンプル・データ・ブロック）をＸと示し、その変換をＹと示す（Ｘ１は、行関連の変換のすぐ後のブロックを示す）。行列ＸおよびＹは同じサイズであり、８×８、８×４および４×８の場合を包含する。以下のスケーリング係数が使用される。
【０１５７】
【数５９】
【０１５８】
８×８順方向変換では、ステージ７１０、７３０および７４０における処理が以下のように記載される。
【０１５９】
【数６０】
【０１６０】
４×８順方向変換では、ステージが以下を実行する。
【０１６１】
【数６１】
【０１６２】
他方では、８×４順方向変換は、上の４×８順方向変換についての転置された変換である。
【０１６３】
４×４順方向変換は、以下のようにスケーリングを実装する。
【０１６４】
【数６２】
【０１６５】
ＶＩＩ．適切なコンピューティング環境
上に記載した変換を、イメージおよびビデオ信号処理が実行される様々なデバイスのいずれかにおいて実行することができ、これには、他の実施例の中でも、コンピュータ、イメージおよびビデオ記録、送信および受信装置、ポータブル・ビデオ・プレイヤー、テレビ会議およびその他が含まれる。イメージおよびビデオ符号化技術をハードウェアの回路において、ならびに、図８に示すような、コンピュータまたは他のコンピューティング環境内で実行するイメージおよびビデオ処理ソフトウェアにも実装することができる。
【０１６６】
図８は、記載した実施形態を実装することができる、適切なコンピューティング環境（８００）の汎用の実施例を例示している。本発明は、多様な汎用または専用コンピューティング環境において実装できるので、コンピューティング環境（８００）は、本発明の使用または機能性の範囲についていかなる限定も示唆するように意図されたものではない。
【０１６７】
図８を参照すると、コンピューティング環境（８００）は、少なくとも１つの処理装置（８１０）およびメモリ（８２０）を含む。図８では、この最も基本的な構成（８３０）が破線内に含まれる。処理装置（８１０）はコンピュータ実行可能命令を実行し、従って、現実の、あるいは仮想プロセッサにすることができる。多重処理システムでは、多重処理装置がコンピュータ実行可能命令を実行して処理能力を高める。メモリ（８２０）は、揮発性メモリ（例えば、レジスタ、キャッシュ、ＲＡＭ）、不揮発性メモリ（例えば、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリなど）、またはこの２つのある組合せにすることができる。メモリ（８２０）は、記載したイメージおよび／またはビデオ・エンコーダ／デコーダおよび変換を実装するソフトウェア（８８０）を格納する。
【０１６８】
コンピューティング環境は追加の機能を有することができる。例えば、コンピューティング環境（８００）は、記憶装置（８４０）、１つまたは複数の入力デバイス（８５０）、１つまたは複数の出力デバイス（８６０）、および１つまたは複数の通信接続（８７０）を含む。バス、コントローラまたはネットワークなどの相互接続メカニズム（図示せず）は、コンピューティング環境（８００）のコンポーネントを相互接続する。通常、オペレーティング・システム・ソフトウェア（図示せず）が、コンピューティング環境（８００）において実行する他のソフトウェアのためのオペレーティング環境を提供し、コンピューティング環境（８００）のコンポーネントのアクティビティを調整する。
【０１６９】
記憶装置（８４０）はリムーバブルまたは非リムーバブルにすることができ、これには、磁気ディスク、磁気テープまたはカセット、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、ＤＶＤ、または、情報を格納するために使用することができ、かつコンピューティング環境（８００）内でアクセスすることができる他のいずれかの媒体が含まれる。記憶装置（８４０）は、量子化行列を生成かつ圧縮するオーディオ・エンコーダを実装するソフトウェア（８８０）のための命令を格納する。
【０１７０】
入力デバイス（８５０）は、キーボード、マウス、ペンまたはトラック・ボールなどのタッチ入力デバイス、音声入力デバイス、走査デバイス、または、入力をコンピューティング環境（８００）に提供する別のデバイスにすることができる。オーディオについては、入力デバイス（８５０）をサウンド・カード、または、アナログまたはデジタル形式におけるオーディオ入力を受け入れる類似のデバイス、またはオーディオ・サンプルをコンピューティング環境に提供するＣＤ−ＲＯＭリーダにすることができる。出力デバイス（８６０）は、ディスプレイ、プリンタ、スピーカ、ＣＤライタ、または、コンピューティング環境（８００）からの出力を提供する別のデバイスにすることができる。
【０１７１】
通信接続（８７０）は、通信媒体を介して別のコンピューティング・エンティティへの通信を可能にする。通信媒体は、コンピュータ実行可能命令、圧縮されたオーディオまたはビデオ情報、または変調されたデータ信号における他のデータなどの情報を搬送する。変調されたデータ信号は、信号中に情報をエンコードするような方法で設定された、あるいは変更された１つまたは複数の特性を有する信号である。例として、限定しないが、通信媒体には、電気、光学、ＲＦ、赤外線、音響または他の搬送波により実装されるワイヤードまたはワイヤレス技術が含まれる。
【０１７２】
本明細書の変換および符号化／復号技術を、一般にコンピュータ可読媒体内に記述することができる。コンピュータ可読媒体は、コンピューティング環境内でアクセスすることができるいずれかの使用可能な媒体である。例として、限定しないが、コンピューティング環境（８００）では、コンピュータ可読媒体は、メモリ（８２０）、記憶装置（８４０）、通信媒体、および上記のいずれかの組合せを含む。
【０１７３】
本明細書の変換および符号化／復号技術を、ターゲットの、実際の、あるいは仮想のプロセッサ上のコンピューティング環境において実行される、プログラム・モジュールに含まれるような、一般にコンピュータ実行可能命令に関連して記述することができる。一般に、プログラム・モジュールには、ルーチン、プログラム、ライブラリ、オブジェクト、クラス、コンポーネント、データ構造など、特定のタスクを実行するか、あるいは特定の抽象データ型を実装するものが含まれる。プログラム・モジュールの機能性を、様々な実施形態において望まれるように、複数のプログラム・モジュールの間で結合あるいは分割することができる。プログラム・モジュールのためのコンピュータ実行可能命令を、ローカルまたは分散コンピューティング環境内で実行することができる。
【０１７４】
説明のため、詳細な説明では、「決定する」、「生成する」、「調整する」および「適用する」のような用語を使用して、コンピューティング環境におけるコンピュータ・オペレーションを記載した。これらの用語は、コンピュータによって実行されるオペレーションについての高レベルの抽象であり、人間によって実行される動作と混同されるべきではない。これらの用語に対応する実際のコンピュータ・オペレーションは、実装に応じて変わる。
【０１７５】
ＶＩＩＩ．拡張
上に記載した変換およびそれらの実装を、以下のものを含む、様々な方法で拡張することができる。
【０１７６】
変換の実装の変形形態には、オルタネート・ラウンディング（alternate rounding）、「バタフライ（butterfly）」実装および双直交公式化（biorthgonal formulations）が含めることができる。
【０１７７】
さらに、上に記載した構築プロセスの後に続いて、異なるビット範囲制約を受けて、異なる係数範囲を有する変換の変形形態を生成することができる。
【０１７８】
構築手順において使用された制約のしきい値のパラメータを変更して、より大きいセットの制約変換を生じさせることができる。
【０１７９】
変換セットを拡張して、さらなるブロック・サイズ（例えば、４×４および他のブロック・サイズの変換）を含むようにすることができる。同様に、生成された変換セットは必ずしも、上に例示した実装におけるサイズ（すなわち、８×８、８×４および４×８変換）を含まない可能性がある。変換を他のサイズのブロック、およびより高い（２より高い）次元まで拡張することができる。
【０１８０】
ビット深度の選択は可変パラメータであり、（生のピクセル値の８ビット分解能、および中間結果についての１６ビットを使用した）例示した実施例について任意に変更することができる。
【０１８１】
順方向変換の実装を、逆方向変換の実装を範囲制限するために記載した手順を使用することなどによって、範囲制限することもできる。
【０１８２】
上に記載した構築プロセスの後に続いて、他の非ＤＣＴ基底関数に近似する変換を生成することができる。例えば、構築プロセスは、スケールされた整数、完全な再構築および範囲制限における制約を満たしながら、ＦＦＴ、ウェーブレット、または他のオーバーラップ変換を近似する変換を生成することができる。
【０１８３】
本発明の原理を、記載した実施形態を参照して記載かつ例示したが、記載した実施形態の構成および詳細を、このような原理から逸脱することなく修正できることは理解されよう。本明細書に記載したプログラム、プロセスまたは方法は、そうでないと指示されない限り、いずれかの特定のタイプのコンピューティング環境に関係付けられず、あるいは限定されないことを理解されたい。様々なタイプの汎用または専用コンピューティング環境は、本明細書に記載した技術によるオペレーションと共に使用することができ、あるいはこれを実行することができる。ソフトウェアにおいて示した記載の実施形態の要素をハードウェアにおいて実施することができ、その逆も可能である。
【０１８４】
変換符号化技術を本明細書のところどころで、単一の統合されたシステムの一部として記載するが、これらの技術を他の技術と組み合わせて別々に、潜在的に適用することができる。代替実施形態では、エンコーダまたはデコーダ以外の信号処理ツールがこれらの技術の１つまたは複数を実装する。
【０１８５】
記載した変換および変換符号化の実施形態は、様々な技術を実行する。これらの技術のためのオペレーションを通常、提示のために特定の一連の順序で記載するが、この記載の方法は、特定の順序が必要とされない限り、オペレーションの順序における重要でない再配列を包含することを理解されたい。例えば、順次に記載したオペレーションを、いくつかの場合では、再配列あるいは同時に実行することができる。さらに、簡単にするため、流れ図では通常、特定の技術を他の技術と共に使用することができる様々な方法を図示していない。
【０１８６】
本発明の原理を適用することができる多数の可能な実施形態に鑑みて、本発明として、特許請求の範囲およびその同等物の範囲および趣旨内に入る可能性のあるこのようなすべての実施形態を請求する。
【図面の簡単な説明】
【図１】本明細書に記載した変換のクラスに基づくビデオ・エンコーダのブロック図である。
【図２】本明細書に記載した変換のクラスに基づくビデオ・デコーダのブロック図である。
【図３】２次元変換を例示するブロック図である。
【図４】図１および２のビデオ・エンコーダおよびデコーダによる、本明細書に記載した変換のクラスを使用した変換符号化を例示するデータ流れ図である。
【図５】本明細書に記載した変換のクラスについての逆方向変換の実装のブロック図である。
【図６】本明細書に記載した変換のクラスのうち１つを構築するためのプロセスの流れ図である。
【図７】本明細書に記載した変換のクラスについての順方向変換の実装のブロック図である。
【図８】図１および２の、記載した変換のクラスに基づくビデオ・エンコーダ／デコーダのための適切なコンピューティング環境のブロック図である。
【符号の説明】
１００ 汎用ビデオ・エンコーダ
１０５ カレント・フレーム
１１０ 動き予測器
１１５、２１５ 動き情報
１２０、２２０ フレーム・ストア
１２５、２２５ 参照フレーム
１３０、２３０ 動き補償器
１３５ 動き補償されたカレント・フレーム
１４５ 予測残差
１６０ 周波数変換器
１６６、２６０ 逆周波数変換器
１７０ 量子化器
１７６、２７０ 逆量子化器
１８０ エントロピー符号器
１９０、２９０ バッファ
１９５、２９５ 圧縮されたビデオ情報
２００ 汎用ビデオ・デコーダ
２０５ 再構築されたフレーム
２３５ 予測フレーム
２４５ 再構築された残差
２８０ エントロピー復号器
Ｔ 前−乗算変換行列
Ｔ’ 後−乗算変換行列
Ｓ１ シフトさせるビット位置
Ｓ２ シフトさせるビット位置
【発明の属する技術分野】
本発明は、信号をデジタル方式でエンコードしたり、処理したりするための技術に関する。より詳細には、本発明は、イメージおよびビデオなどの信号のエンコードおよびデコードにおける、計算効率のよい変換のクラスの構築および使用に関する。
【０００２】
【従来の技術】
変換符号化は、多数のオーディオ、イメージおよびビデオ圧縮システムにおいて使用される圧縮技術である。圧縮されていないデジタル・イメージおよびビデオは通常、２次元グリッド内に配列されたイメージまたはビデオ・フレームにおける位置の画素または色のサンプルとして表現され、あるいは取り込まれる。例えば、イメージ用の通常のフォーマットは、グリッドとして配列された２４ビットのカラー画素サンプルのストリームからなる。各サンプルは、中でもＲＧＢまたはＹＩＱなど、色空間内のグリッド内でピクセル位置での色成分を表現する集まりである。様々なイメージおよびビデオ・システムは、サンプリングについて様々な異なる色、空間および時間分解能を備えることができる。
【０００３】
圧縮されていないデジタル・イメージおよびビデオ信号は、かなりの格納容量および伝送容量を消費する可能性がある。変換符号化は、これは、信号の空間領域表現を周波数領域（または、変換領域などの他の）表現に変換すること、および次いで、変換領域表現の、一般に知覚困難なある周波数成分の分解能を低減することによって、デジタル・イメージおよびビデオの量的なサイズを低減する。このことは、一般に、空間領域におけるイメージまたはビデオの色または空間の分解能の低減に比較して、ずっと少ないデジタル信号についての劣化を生じさせる。
【０００４】
具体的には、通常の変換符号化技術は、圧縮されていないデジタル・イメージのピクセルを、固定サイズの２次元ブロックで、場合によっては他のブロックと重なりあう各ブロックに分割する。空間周波数解析を行う線形変換が各ブロックに適用され、これはブロック内で間隔のあいたサンプルを、周波数（または変換）係数のセットに変換し、これは一般に、ブロック空間の全面にわたって対応する周波数帯域におけるデジタル信号の強度を表現している。圧縮のため、変換係数を選択的に量子化することができ（すなわち、分解能を低減し、これは、係数値の最下位ビットをドロップすること、またはそうでない場合は、より高い分解能数セットにおける値をより低い分解能にマップすることなどによって行う）、その後、圧縮データ・ストリームにエントロピー符号化または可変長符号化することができる。デコードでは、変換係数は逆方向変換されて、元々の、色／空間サンプリングされた、イメージ／ビデオ信号をほぼ再構築する。
【０００５】
中でもＭＰＥＧおよびＷｉｎｄｏｗｓ（登録商標）Ｍｅｄｉａなど、多数のイメージおよびビデオ圧縮システムは、離散コサイン変換（ＤＣＴ）に基づいた変換を利用する。ＤＣＴは、ほぼ最適なデータ圧縮を結果として生じる、好ましいエネルギー圧縮特性を有することが知られている。これらの圧縮システムでは、逆ＤＣＴ（ＩＤＣＴ）が、個々のイメージ・ブロックを再構築するために、圧縮システムのエンコーダおよびデコーダにおける再構築ループにおいて使用される（例えば、非特許文献１参照）。
【０００６】
非特許文献１において定義されたＩＤＣＴ変換の欠点は、変換の計算が６４ビット浮動小数点数の行列乗算を要件とする変換の計算であり、これは計算処理的に費用のかかるものである。このことは、ＩＤＣＴが、リアル・タイムベースで、あるいは他の同様の時間制約下で、多量の圧縮データに基づいて実行されている場合、特にストリーミング・メディアおよび同様のメディア再生アプリケーションにおいて、イメージまたはビデオ圧縮システムのパフォーマンスが制限される可能性がある。
【０００７】
【非特許文献１】
"IEEE Standard Specification for the Implementations of 8x8 Inverse Discrete Cosine Transform", IEEE Std. 1180-1990, December 6, 1990
【０００８】
【発明が解決しようとする課題】
本発明の目的は、イメージおよびビデオなどの信号のエンコードおよびデコードにおいて、１および２次元変換のクラス、このような変換の構築において、効率良く計算する方法、この方法を適用した装置、および記憶媒体を提供することにある。
【０００９】
本明細書では、１および２次元変換のクラス、このような変換を構築するための技術、および、このような変換を利用したメディア符号化／復号システムが、記載される。
【００１０】
【課題を解決するための手段】
記載した変換は、計算効率（computational efficiency）を得るために、整数を使用した行列乗算演算に基づいた実装（implementations）を備えている。通常の一般的な目的およびグラフィックス・プロセッサでは、整数を使用した行列乗算演算を、浮動小数点数を使用した場合よりも、はるかに高速に実行することができる。さらに、いくつかの３２ビット・プロセッサは、同時に２つの１６ビット整数を使用した乗算演算を提供する。典型的な実装では、記載した変換は、１６ビット整数行列乗算を使用して実行される。整数の行列乗算を使用した記載した変換の実装は、メディア符号化／復号システムにおける符号化および復号化のパフォーマンスの速度を早める。
【００１１】
記載した変換を、本明細書に記載した構築手順を介して生成することができる。この構築手順は、ある制約を受ける変換係数のセットの選択に基づく変換クラスの変換を生成する。この制約は、この変換が、スケーリングされた整数の実装を有すること、完全またはほぼ完全な再構築を提供すること、ＤＣＴ近似の基底（DCT like Basis）を有すること、ｎビット（例えば、ｎは１６ビット）における表現の範囲内の係数に制限されること、ノルム（norm）において近い基底関数（basis functions）を有すること、および、その範囲からのオーバーフローに備えて十分なヘッドルームを提供すること、を含むことができる。
【００１２】
記載した構築手順を使用すると、１次元における４および８点の成分を備えた変換のセットは、２次元における８×８、８×４、４×８および４×４ブロック変換を生じさせる。１６ビット行列乗算を使用した実装を可能にする変換に基づく圧縮システムは、より計算効率のよいエンコーディングおよびデコーディングを提供することができる。
【００１３】
本発明の追加の特徴および利点は、添付の図面を参照して進行する以下の実施形態の詳細な説明から、明らかになるであろう。
【００１４】
【発明の実施の形態】
以下の記載は、計算効率のための１および２次元変換のクラス、ある基準に従うこのような変換を構築するための技術、および信号処理におけるこのような変換の使用、および詳細には、このような変換に基づいたメディア圧縮システムを対象とする。変換の例示的応用例は、Ｍｉｃｒｏｓｏｆｔ Ｗｉｎｄｏｗｓ（登録商標）Ｍｅｄｉａ Ｖｉｄｅｏ（ＷＭＶ）ファイル・フォーマットの変形形態を使用するエンコーダおよびデコーダなど、イメージまたはビデオのエンコーダおよびデコータにおけるものである。しかし、本明細書に記載したように構築された変換はこのフォーマットに限定されず、他のメディア符号化フォーマットに適用することができる。したがって、これらの変換を、汎用のイメージまたはビデオのエンコーダおよびデコーダに関連して記載するが、別法として、様々なタイプのメディア信号エンコーダおよびデコーダに組み込むことができる。
【００１５】
Ｉ．汎用ビデオ・エンコーダおよびデコーダ
図１は汎用ビデオ・エンコーダ（１００）のブロック図であり、図２は汎用ビデオ・デコーダ（２００）のブロック図である。
【００１６】
エンコーダおよびデコーダ内の複数のモジュールの間で示される関係は、エンコーダおよびデコーダにおける情報の主要な流れを示し、他の関係は、簡単にするために図示しない。特に、図１および２は、通常、ビデオ・シーケンス、フレーム、マクロブロック、ブロックなどのために使用されるエンコーダ設定、モード、テーブルなどを示す副情報を図示しない。このような副情報が、通常は、副情報のエントロピー符号化の後、出力ビットストリームにおいて送信される。出力ビットストリームのフォーマットを、Ｗｉｎｄｏｗｓ（登録商標）ＭｅｄｉａＶｉｄｅｏフォーマットまたは別のフォーマットにすることができる。
【００１７】
エンコーダ（１００）およびデコーダ（２００）はブロック・ベースであり、４：２：０マクロブロック・フォーマットを使用し、各マクロブロックは、４つのルミナンス８×８ルミナンス・ブロック（時として、１つの１６×１６マクロブロックとして処理される）および２つの８×８クロミナンス・ブロックを含む。別法として、エンコーダ（１００）およびデコーダ（２００）はオブジェクト・ベースであり、異なるマクロブロックまたはブロック・フォーマットを使用し、あるいは、８×８ブロックおよび１６×１６マクロブロックとは異なるサイズまたは構成のピクセルのセットにおいてオペレーションを実行する。
【００１８】
実装および所望の圧縮のタイプに応じて、エンコーダまたはデコーダのモジュールを追加したり、省略したり、多数のモジュールに分割にしたり、他のモジュールと結合したり、かつ／または同様のモジュールで置き換えたりすることができる。代替実施形態では、異なるモジュールおよび／または他のモジュールの構成を有するエンコーダまたはデコーダは、記載した技術のうち１つまたは複数を実行する。
【００１９】
Ａ．ビデオ・エンコーダ
図１は、汎用ビデオ・エンコーダ・システム（１００）のブロック図である。エンコーダ・システム（１００）は、カレント・フレーム（１０５）を含むビデオ・フレームのシーケンスを受信し、圧縮されたビデオ情報（１９５）を出力として生じさせる。ビデオ・エンコーダの特定の実施形態は、通常、汎用エンコーダ（１００）の変形形態（variation）または補足バージョン（supplemented version）を使用する。
【００２０】
エンコーダ・システム（１００）は、予測フレームおよびキー・フレームを圧縮する。説明のため、図１は、エンコーダ・システム（１００）を通過するキー・フレームのパス、および、前方向予測フレームのパスを示す。エンコーダ・システム（１００）のコンポーネントの多くは、キー・フレームおよび予測フレームの両方を圧縮するために使用される。これらのコンポーネントによって実行される厳密なオペレーションは、圧縮中の情報のタイプに応じて変わる可能性がある。
【００２１】
予測フレーム（ｐフレーム、双方向予測ではｂフレーム、またはインター・コード化フレーム（inter-coded frame）とも呼ばれる）は、１つまたは複数の他のフレームからの予測（または差異）の期間に対して表現される。予測残差は、予測されたものと元のフレームの間の差異である。対照的に、キー・フレーム（ｉフレーム、イントラ・コード化フレーム（intra-coded frame）とも呼ばれる）は、他のフレームに関係なく圧縮される。
【００２２】
カレント・フレーム（１０５）が前方向予測フレームであった場合、動き予測器（１１０）は、フレーム・ストア（１２０）においてバッファリングされている、再構築された先のフレーム（１２５）である、参照フレームを考慮して、カレント・フレーム（１０５）のマクロブロックまたは他のピクセルのセットの動きを予測する。代替実施形態では、参照フレームは後のフレームであり、あるいはカレント・フレームは双方向予測される。動き予測器（１１０）は、副情報として動きベクトルなどの動き情報（１１５）を出力する。動き補償器（１３０）は、動き情報（１１５）を、再構築された先のフレーム（１２５）に加えて、動き補償されたカレント・フレーム（１３５）を形成する。しかし、予測はめったに完全ではなく、動き補償されたカレント・フレーム（１３５）と元のカレント・フレーム（１０５）の間の差異は、予測残差（１４５）である。別法として、動き予測器および動き補償器は、別のタイプの動き予測／補償を適用する。
【００２３】
周波数変換器（１６０）は、空間領域ビデオ情報を周波数領域（すなわち、スペクトル）データに変換する。ブロック−ベースのビデオ・フレームでは、周波数変換器（１６０）は、以下のセクションで記載する、離散コサイン変換［「ＤＣＴ」］に類似した特性を有する変換を適用する。いくつかの実施形態では、周波数変換器（１６０）は周波数変換を、キー・フレームについての空間予測残差のブロックに適用する。周波数変換器（１６０）は、８×８、８×４、４×８または他のサイズの周波数変換を適用することができる。
【００２４】
次いで、量子化器（１７０）がスペクトル・データ係数のブロックを量子化する。量子化器は、一様なスカラー量子化を、フレーム毎のベースで、あるいは他のベースで変わるステップ・サイズを使用してスペクトル・データに適用する。別法として、量子化器は別のタイプの量子化をスペクトル・データ係数に適用し、これは例えば、非一様、ベクトル、または非適応量子化であり、あるいは空間領域データを、周波数変換を使用しないエンコーダ・システムにおいて直接量子化する。適応量子化に加えて、エンコーダ（１００）はフレーム・ドロップ、適応フィルタリング、またはレート・コントロールのための他の技術を使用することができる。
【００２５】
再構築されたカレント・フレームが、後続の動き予測／補償のために必要とされるとき、逆量子化器（１７６）は逆量子化を、量子化されたスペクトル・データ係数上で実行する。次いで、逆周波数変換器（１６６）は、周波数変換器（１６０）のオペレーションの逆を実行し、再構築された予測残差（予測フレームのもの）、または再構築されたキー・フレームを生じさせる。カレント・フレーム（１０５）がキー・フレームであった場合、再構築されたキー・フレームが、再構築されたカレント・フレーム（図示せず）として採用される。カレント・フレーム（１０５）が予測フレームであった場合、再構築された予測残差が、動き補償されたカレント・フレーム（１３５）に追加されて、再構築されたカレント・フレームが形成される。フレーム・ストア（１２０）は、再構築されたカレント・フレームを、次のフレームの予測において使用するためにバッファリングする。いくつかの実施形態では、エンコーダは、デブロッキング・フィルタを再構築されたフレームに適用して、フレームのブロックにおける不連続性を適応的に平滑化する。
【００２６】
エントロピー符号器（１８０）は、量子化器（１７０）の出力ならびにある副情報（例えば、動き情報（１１５）、量子化ステップ・サイズ）を圧縮する。通常のエントロピー符号化技術には、算術符号化、差分符号化、ハフマン符号化、ラン・レングス符号化、ＬＺ符号化、辞書型符号化、および上記の組合せが含まれる。エントロピー符号器（１８０）は通常、異なる種類の情報（例えば、ＤＣ係数、ＡＣ係数、異なる種類の副情報）について異なる符号化技術を使用し、特定の符号化技術内の複数のコード・テーブルの中から選択することができる。
【００２７】
エントロピー符号器（１８０）は、圧縮されたビデオ情報（１９５）をバッファ（１９０）に入れる。バッファ・レベル・インディケータ（標識）が、ビットレート適応化モジュールにフィードバックされる。圧縮されたビデオ情報（１９５）は、バッファ（１９０）から、一定の、あるいは相対的に一定のビットレードで消耗され、そのビットレートでの後続のストリーミングに備えてに格納される。別法として、エンコーダ・システム（１００）は、圧縮されたビデオ情報を、圧縮のすぐ後に続いてストリームする。
【００２８】
バッファ（１９０）の前または後に、圧縮されたビデオ情報（１９５）を、ネットワークを介して伝送するためにチャネル符号化することができる。チャネル符号化は、誤り検出および訂正データを、圧縮されたビデオ情報（１９５）に適用することができる。
【００２９】
Ｂ．ビデオ・デコーダ
図２は、汎用ビデオ・デコーダ・システム（２００）のブロック図である。デコーダ・システム（２００）は、圧縮されたビデオ・フレームのシーケンスについての情報（２９５）を受信し、再構築されたフレーム（２０５）を含む出力を生じさせる。ビデオ・デコーダの特定の実施形態は、通常、汎用デコーダ（２００）の変形形態または補足バージョンを使用する。
【００３０】
デコーダ・システム（２００）は、予測フレームおよびキー・フレームを圧縮解除する。説明のため、図２は、デコーダ・システム（２００）を通過するキー・フレームのパス、および、前方向予測フレームのパスを示す。デコーダ・システム（２００）のコンポーネントの多くは、キー・フレームおよび予測フレームの両方を圧縮解除するために使用される。これらのコンポーネントによって実行される厳密なオペレーションは、圧縮解除中の情報のタイプに応じて変わる可能性がある。
【００３１】
バッファ（２９０）は、圧縮されたビデオ・シーケンスについての情報（２９５）を受信し、受信された情報をエントロピー復号器（２８０）で使用可能にする。バッファ（２９０）は通常、情報を、経時的にかなり一定であるレートで受信し、帯域幅または伝送における短期の変化を平滑化するためのジッタ・バッファを含む。バッファ（２９０）は、再生バッファおよび他のバッファも含むことができる。別法として、バッファ（２９０）は情報を、変化するレートで受信する。バッファ（２９０）の前または後に、圧縮されたビデオ情報をチャネル・デコードし、誤り検出および訂正のために処理することができる。
【００３２】
エントロピー復号器（２８０）は、通常は、エンコーダにおいて実行されたエントロピー符号化の逆を適用して、エントロピー符号化された量子化データ、ならびに、エントロピー符号化された副情報（例えば、動き情報、量子化ステップ・サイズ）をエントロピー復号する。エントロピー復号技術には、算術復号、差分復号、ハフマン復号、ラン・レングス復号、ＬＺ復号、辞書型復号、および上記の組合せが含まれる。エントロピー復号器（２８０）はしばしば、異なる種類の情報（例えば、ＤＣ係数、ＡＣ係数、異なる種類の副情報）について異なる符号化技術を使用し、特定の復号技術内の複数のコード・テーブルの中から選択することができる。
【００３３】
再構築されるフレーム（２０５）が前方向予測フレームであった場合、動き補償器（２３０）は動き情報（２１５）を参照フレーム（２２５）に適用して、再構築されるフレーム（２０５）の予測（２３５）を形成する。例えば、動き補償器（２３０）はマクロブロック動きベクトルを使用して、参照フレーム（２２５）におけるマクロブロックを発見する。フレーム・バッファ（２２０）は、先の再構築されたフレームを、参照フレームとして使用するために格納する。別法として、動き補償器は別のタイプの動き補償を適用する。動き補償器による予測はめったに完全ではなく、そのためデコーダ（２００）はまた予測残差をも再構築する。
【００３４】
デコーダが、再構築されたフレームを後続の動き補償のために必要とするとき、フレーム・ストア（２２０）は、再構築されたフレームを、次のフレームの予測において使用するためにバッファリングする。いくつかの実施形態では、エンコーダは、デブロッキング・フィルタを再構築されたフレームに適用して、フレームのブロック内の不連続性を適応的に平滑化する。
【００３５】
逆量子化器（２７０）は、エントロピー復号されたデータを逆量子化する。一般には、逆量子化器は一様なスカラー逆量子化を、フレーム毎のベースで、あるいは他のベースで変わるステップ・サイズを使用して、エントロピー復号されたデータに適用する。別法として、逆量子化器は別のタイプの逆量子化をデータに適用し、これは例えば、非一様、ベクトル、または非適応逆量子化であり、あるいは空間領域データを、逆周波数変換を使用しないデコーダ・システムにおいて直接逆量子化する。
【００３６】
逆周波数変換器（２６０）は、量子化された周波数領域を空間領域ビデオ情報に変換する。ブロック−ベースのビデオ・フレームに対して、逆周波数変換器（２６０）は、以下のセクションで記載する逆方向変換を適用する。いくつかの実施形態では、逆周波数変換器（２６０）は逆周波数変換を、キー・フレームの空間予測残差のブロックに適用する。逆周波数変換器（２６０）は、８×８、８×４、４×８または他のサイズの逆周波数変換を適用することができる。
【００３７】
ＩＩ．変換の概観
図３は、図１および２のビデオ・エンコーダ１００およびデコーダ２００において使用された２次元変換３００および逆方向変換３１０を例示する。変換３００および逆方向変換３１０は、以下に記載するようなある制約を受けて構築された変換のクラスに基づいている。
【００３８】
２次元変換３００は、メディア・コンテンツの空間的に関係付けられたサンプルとして表現されたメディア・コンテンツの２次元（ｎ×ｍ）ブロック３２０を、変換領域ブロックに変換する。例えば、ブロックは、一様に間隔のあいたグリッド位置に配列されたカラー・サンプル（ピクセル）のアレイとして表現することができるような、デジタル・イメージまたはデジタル・ビデオ・フレームの一部であるとすることができる。これは、メディア・コンテンツの空間領域表現と呼ばれる。この変換ブロックもまたｎ×ｍサンプルからなり、本明細書では、メディア・コンテンツの変換領域表現と称する。
【００３９】
逆方向変換３２０は、サンプルのブロックを変換領域から、元の、あるいは空間領域に戻すように変換する。
【００４０】
ＩＩＩ．変換ベースの符号化
一般に、例えば、上述したビデオ・エンコーダおよびデコーダにおけるような、メディア・コンテンツの変換ベースの符号化４００は、変換３００（図３）および逆方向変換３１０（図３）を量子化と共に利用して、メディア・コンテンツを圧縮された形式でエンコードする。変換ベースの符号化は最初に変換ステージ４１０内の変換３００を、変換領域に変換するためにメディア・コンテンツの入力ブロックに適用する。次いで、変換ベースの符号化は、量子化ステージ４２０で、ある変換領域サンプル（例えば、メディア・コンテンツについてより少ない知覚可能な劣化を生じさせる変換領域サンプル）の量子化を実行する（すなわち、分解能を低減する）。量子化された変換領域サンプルを使用して、圧縮された形式のメディア・コンテンツを生成することができる。
【００４１】
変換ベースの符号化４００はまた、逆量子化ステージ４３０および逆方向変換ステージ４４０も有する。逆量子化ステージ４３０で、変換ベースの符号化は、量子化された変換領域サンプルを、それらの元の分解能に戻すようにマップし、逆方向変換３１０の準備をする。変換ベースの符号化は、逆方向変換ステージにおいて、逆方向変換を逆量子化された領域サンプルにおいて実行して、次いでメディア・コンテンツ・ブロックを再構築する。
【００４２】
変換ベースの符号化４００を、ビデオ・エンコーダおよびデコーダにおける様々な点で実行することができる。例えば、ビデオ・エンコーダは、また、差分符号化およびインター・フレーム符号化技術において使用するために、逆量子化および逆方向変換ステージを有する再構築ループを含むこともできる。
【００４３】
ＩＶ．計算効率のよい逆方向変換の実装
このとき、図５を参照すると、変換３００および逆方向変換３１０（図３）は、好ましくは、前−乗算変換行列（Ｔ）による（変換３００のための空間領域サンプルの、かつ、逆方向変換のための変換領域サンプルの）２次元データ・ブロックの前−乗算５１０、および、後−乗算変換行列（Ｔ’）による後−乗算５３０として実装される。前−乗算変換行列（Ｔ）の行は変換の基底関数を表し、これが前−乗算５１０におけるデータ・ブロックの列に適用される。同様に、後−乗算変換行列（Ｔ’）の列は、後−乗算５３０におけるデータ・ブロックの行に適用される変換基底関数（transform basis functions）である。
【００４４】
計算効率のため、変換行列（ＴおよびＴ’）およびデータ・ブロックは、コンピュータまたはグラフィックス・プロセッサの整数乗算演算を使用してその行列乗算が実行されることを可能にする範囲内の整数値から構成される。例えば、１６ビット整数乗算演算を提供する多数の現在のプロセッサでは、好ましくは、１６ビット整数乗算演算を使用してその行列が実行されることを可能にする範囲内の整数から構成される。別法として、行列は、他のサイズの整数の整数乗算演算を提供するプロセッサのための、より小さい、あるいはより大きい範囲における整数から構成されることも可能である。
【００４５】
整数から構成される変換基底関数によるデータ・ブロックの前−乗算および後−乗算は、結果として生じるデータ・ブロック値をより大きい範囲において生じさせる。実装５００は、基底関数乗算によるこの拡大を、それぞれ前乗算および後乗算の後にスケーリング演算５２０、５４０を使用して補償する。計算効率のため、スケーリング演算５２０、５４０は、シフト演算（実際には、２のべき乗による除算）であることが好ましく、これは値をいくつかのビット位置Ｓ１およびＳ２だけそれぞれシフトさせる。
【００４６】
例示した実装５００では、データ・ブロック内の値は、前−乗算５１０の入力、スケーリング５２０、後−乗算５３０、スケーリング５４０および出力での、それぞれＡ〜Ｅとして表されたビット・サイズを有する整数である。例えば、前−乗算ステージ５１０の入力でのデータ・ブロックの値は、サイズがＡビットである整数である。
【００４７】
この変換の設計において基礎をなす原理は、順方向変換および逆方向変換において、後者が、制約された精度の整数の演算という態様で実装され、（有効な量子化および逆量子化に従う）対応する順方向変換プロセスによって生成されている入力データについての有意味の結果を生成するように保証されている、そのような逆方向変換と順方向変換のペアとしてのその実装５００である。
【００４８】
Ｖ．変換の構築
計算効率のよい変換は、以下に記載するある制約に従う、変換基底関数のための係数値（すなわち、前−乗算行列Ｔおよび後−乗算行列Ｔ’における値）を選択することによって構築される。この構築技術は、範囲が制限された、直交（orthogonal）または双直交変換（bi-orthogonal transforms）を生じさせることができる。
【００４９】
制約。
スケーリングされる整数の実装。この変換係数は、２のべき乗によるスケーリングを可能とする、整数である。これにより、標準のコンピュータにおける実装が容易になる。
【００５０】
完全な再構築。量子化（例えば、図４における量子化および逆量子化ステージ４２０、４３０）がない場合、逆方向変換は元の空間領域データを、変換によって生成された変換領域データから、完全に再構築する。データを圧縮するために使用される変換のための主要な要件は、量子化および丸めがない場合に、順方向および逆方向変換が完全な再構築ペアを形成することである。これは、正規直交性（orthonormality）または双正規直交性（biorthonormality）を通じて保証されることができる。前者の場合、順方向および逆方向変換は等しいが、後者ではこれらは異なる。
【００５１】
ＤＣＴ近似の基底（DCT like Basis）。変換および逆方向変換は、ＤＣＴに類似した特性を有する。よい符号化パフォーマンスのために、変換がＤＣＴを厳密に近似することが好ましい。ＤＣＴは、ほぼ最適なデータ圧縮を結果として生じる好ましいエネルギー圧縮特性を有することが知られている。ＤＣＴのＤＣ基底関数は定数値である。これは、「ゼロ番目」の基底の変換係数が定数値を有するように制約する。
【００５２】
範囲。データ値および変換係数の範囲は、（例えば、１６ビット整数演算において）ターゲット・コンピュータまたはグラフィックス・プロセッサにおける計算効率のよい整数乗算演算を使用した実装を可能にする。好ましい実装では、これらの値は、逆方向変換の１６ビット実装を可能にする範囲に制約される。この実装では、１６ビット整数演算は、１６ビット累算器、および、符号付きモジュロまたは基数２１６へのロールオーバ演算（rollover arithmetic）、すなわち、［−３２７６８．．．３２７６７］のデータ範囲を有する累算器、により実行することができる整数の算術演算である。２個の１６ビット数の乗算の結果は、積の保存されている下位１６ビットのみとなる。別法として、この範囲は、別のビット・サイズの整数演算をサポートする他のターゲット・プラットフォームについて変えることができる。
【００５３】
変換基底関数による、データ・ブロック内のサンプルについての乗算は、範囲に拡張をもたらし、その範囲は、変換基底関数内のサンプル（点）の数によって変わる。ビデオ圧縮システムでは、８×８、４×８、８×４および４×４点の２次元（Ｎ×Ｍ点）変換が一般に使用される。４および８点変換の間で、８点変換は、より厳しい制約を整数変換係数の範囲に課す。これは、Ｎ＞Ｍであるとき、Ｎ点変換に関連付けられた拡張は、Ｍ点変換に関連付けられたものより大きいからである。ＤＣ値は、Ｎ点変換では
【００５４】
【数２５】
として拡張する。したがって、８点変換がより厳しい制約を提示するので、最初に８点変換を考察する。
【００５６】
例えば、ビデオ圧縮システムにおける空間領域データ・ブロック・サンプルの共通範囲は［−２５５．．．２５５］であり、これは９ビットの分解能である。［−２５５ ２５５］の範囲に対応するこのような９ビット入力では、８×８変換は、範囲［−２０４７ ２０４７］内の値を取ることができ、１２ビットの精度を必要とする。実際には、各８点変換は１．５ビットの拡張の結果となる。２次元の８×８変換では、８点変換が、前−乗算ステージ５１０（図５）での行変換および後−乗算ステージ５３０（図５）での列変換により、２度適用され、結果として生じる変換領域サンプルが３ビットだけ（１２ビットの分解能に）拡張される。
【００５７】
より詳細に図５を参照すると、例示的実施において入力Ａで逆方向変換のために入力された変換領域データ・ブロックは、１２ビットの範囲を有するのに対して、出力Ｅで再構築された空間領域データ・ブロックは９ビットの範囲を有する。２つの逆方向変換演算（前−乗算５１０および後−乗算５３０）は、｜Ｔ｜２のスケーリングまたは範囲の拡張を引き起こし、これはｓ１およびｓ２ビットの２つのシフトによってそれぞれ補償される。これには、変換によって引き起こされた範囲の拡張が、補償のスケーリングにほぼ等しいか、または｜Ｔ｜２≒２（ｓ１＋ｓ２）であることが必要とされる。変換行列（Ｔ）が正規化された行列である（ただし、Ｔ１＝Ｔ／｜Ｔ｜）と仮定すると、前−乗算の後に結果として生じるデータ・ブロック（Ｂ＝Ｔ・Ａ）の動的範囲（dynamic range）は約１０．５ビットである。したがって、結果として生じるデータ・ブロック（Ｂ）は、１０．５＋ｌｏｇ２（｜Ｔ｜）ビットの範囲を有する。同様に、後−乗算データ・ブロック（Ｄ＝Ｃ・Ｔ’）は９＋２・ｌｏｇ２（｜Ｔ｜）−ｓ１ビットの範囲を有する。１６ビット整数演算を使用した、計算効率のよい逆方向変換の実装のために、以下の比較式が必要とされる（ｌｏｇ２（｜Ｔ｜）をＬによって示す）。
１０．５＋Ｌ＜＝１６ （１）
９＋２Ｌ−ｓ１＜＝１６ （２）
２Ｌ≒ｓ１＋ｓ２ （３）
【００５８】
したがって、続いて（９＋ｍ＜＝１６）となり、すなわち、ｍ＝６、かつＬ＜＝５．５または｜Ｔ｜＜＝２０４８である。
【００５９】
さらに、逆方向変換のＤＣ基底関数が［ｄｄｄｄｄｄｄｄ］によって与えられるようにすることにより、範囲制約は、８ｄ２＜＝２０４８またはｄ＜＝１６であることを必要とする。
【００６０】
基底関数のノルム。変換のための基底関数のそれぞれはノルムにおいて非常に近い。
【００６１】
一般的な直交（orthogonal）および双直交（biorthogonal）整数変換では、個々の基底関数に対応する変換行列Ｔの個々の行は、個々のノルムを有することができるようにされる。この柔軟性の背後にある考えは、複数のノルムの間の不適合の影響を、量子化および逆量子化中に順方向および逆方向変換について取り消すことができるということである。実際には、正規化は２つの難点を提示する。すなわち、（１）正規化により、特にデコーダ側に複雑さが追加されること、および、（２）正規化乗数が小さい整数でない限り、短い整数（short integer）（１６ビット）実装については正規化が不可能となることである。
【００６２】
すべての基底関数のノルムが一致していることが必要とされる場合、追加の再正規化は不要である。いかなる正規化項も、逆量子化の中に要因としており込むことができる。量子化値による効果は、このプロセスにおいて、少し変えることができる（すなわち、ある量子化点（ＱＰ）のレート−歪み点は、例えば正規化された完全精度変換を使用して計算されたその元の値から、離れているが、レート−歪み（Ｒ−Ｄ）曲線に沿って、動かすことができる）。
【００６３】
４および８点変換について言えば、同じ論理が当てはまる。４点か８点かにかかわらず、すべての基底関数のノルムが一致しており、正規化を取り出すことができるように、同様であることが必要とされる可能性がある。実際には、適切に小さい整数の基数について、すべての基底関数のすべてのノルムが一致しているという制約を受ける変換係数のセットを発見することは不可能である。ここでの制約は、基底関数がノルムにおいて非常に近いことを許容することによって、ささやかな柔軟性を可能とする。
【００６４】
ヘッドルーム。１つの実装では、順方向変換への有効な入力（空間領域データ・ブロック）の範囲は９ビットであるが、量子化（図４のステージ４２０）の後に再構築されたデータ・ブロックが、＋２５５ないし−２５５の範囲を上回るかあるいは下回るようにオーバーフローする可能性がある。短い整数（short integer）の実装は、このことを考慮に入れて、このような状況のために十分なヘッドルームを残すことが必要とされる。
【００６５】
要約すると、本明細書に記載した構築技術は、以下の制約を受ける変換を生じさせる。すなわち、（１）スケーリングされた整数の実装、（２）正規直交性または完全な再構築、（３）エネルギー圧縮についてのＤＣＴ近似の基底、および（４）整数ベースの実装のための制限された制約（例えば、１６ビット整数演算における）である。所与の範囲制限では、上の制約のすべてを満たすことは困難である。特定の例として、これらの制約の最初の３つを満たし、ならびに１６ビットに制限された範囲にある、変換を構築することは可能ではない。以下に記載する構築プロセスは、効率的な、範囲制限された、変換を、これらの制約のうち１つまたは複数をわずかに緩和すること（例えば、例示した変換の実装において、正規直交性の制約を緩和すること）によって、生み出す。例示した変換の実装では、変換のペアが直交（orthogonal）であることのみが必要とされるが、そのノルムをわずかに異なるようにすることができる。この追加の柔軟性により、変換のための探索空間が拡大され、これにより、他の制約を満たす効率的な範囲制限された変換の構築が実現可能となる。以下でさらに論じるように、ノルムにおけるわずかな不一致の影響を、量子化ステージ中に再正規化することによって取り消すことができる。この再正規化は、量子化ステージにおいて実装されているので、結果として複雑さの増大は、エンコーダのみがこうむることになる。これにより、圧縮能率を維持しつつ、システム全体の複雑さが、かなり低減する。
【００６６】
構築。
図６を参照すると、これらの制約に従う計算効率のよい変換を構築するプロセス６００は、図５の変換の実装５００についての前−乗算および後−乗算の変換行列（ＴおよびＴ’）のための直交変換係数のセットを生じさせる。この例示的な計算効率のよい変換の実装を生成するための、この構築手順において使用された許容差のしきい値のいくつかは任意であり、これらをさらに緩和して、さらなる解に達するようにすることができる。しかし、緩和されたしきい値により、このような代替変換の実装は、さらに悪い符号化パフォーマンスを有する可能性がある。
【００６７】
この手順６００を使用して構築された計算効率のよい変換の例示的セットは、４および８点の基底関数を使用した２次元変換を含む。４および８点の基底関数に基づいて、８×８、４×８、８×４および４×４変換のための変換行列が生成される。しかし、この制約プロセスを別法として、他の数の点またはブロック・ディメンションを有する基底関数による変換を生じさせるように変更することができる。
【００６８】
構築プロセス６００の第１のステップ６１０は、ＤＣ基底関数に属する一定の乗数を発見することである。４および８点の基底関数では、一定の乗数がそれぞれｄ４およびｄ８と示される。上で論じたノルム制約により、これらの一定の乗数は、ｄ８≦１６の場合に、
【００６９】
【数２６】
として関係付けられる。このノルム制約を約１％以内で満たす整数のペア｛ｄ４，ｄ８｝は、｛７，５｝、｛１０，７｝、｛１７，１２｝および｛２０，１４｝のみである。８点変換では、ＤＣ基底の２乗ノルムは
【００７１】
【数２７】
である。したがって、これらの整数ペアを有するＤＣ基底について許容可能な８点２乗ノルムは、２００、３９２、１１５２および１５６８である。
【００７３】
構築プロセス６００の第２のステップ６２０は、変換の奇数基底関数（odd basis functions）（奇数の「周波数」とも呼ばれる）を決定することである。上で論じた「ＤＣＴ近似の基底」の制約にしたがって、変換は、ＤＣＴ変換に類似した特性を有するべきであり、これは８点ＤＣＴ変換では、以下の奇数基底関数を有する。
【００７４】
【数２８】
４つの定数値が、８点ＤＣＴのこれらの奇数基底関数を決定する。基数の構造により、定数Ｃ１、Ｃ２、Ｃ３およびＣ４を使用して一意の絶対係数を置き換えて、以下の基底を与えることができる。
【００７６】
【数２９】
構築は、以下の条件を使用して、空間｛Ｃ１，Ｃ２，Ｃ３，Ｃ４｝上を探索することによって進行する。
【００７８】
１．基底の直交性。偶数周波数項を有する奇数項の直交性は、所与の偶数周波数の相補的構造に事実上含まれている。したがって、この条件は、減少して、奇数基底関数の直交性になる。
【００７９】
２．ＤＣＴ近似の基底。ベクトル［Ｃ１ Ｃ２ Ｃ３ Ｃ４］は、対応するＤＣＴ係数ベクトル［０．４９０４ ０．４１５７ ０．２７７８ ０．０９７５］と「十分」に相関する。相関は、複数のベクトルの間の角度のコサインによって測定され、可能な限り１に近くなることが望ましい。相関についての他の測定も使用することができる。
【００８０】
３．奇数の基数のノルムがＤＣノルムに密接に適合する。これを以下のように表すことができる。
【００８１】
【数３０】
ノルムの５％の許容差（条件３）および０．９９の許容可能な相関「コサイン」（条件２）内で、８点奇数基底関数のための制約を満たす整数係数のセットはただ１つしかない。このセットは［１６ １５ ９ ４］であり、５７８のノルムを有し、これは明確に所望の５７６に非常に近い。この相関は、好ましい０．９９８４である。
【００８３】
構築プロセス６００の第３のステップ６３０は、変換のための偶数基底関数（even basis functions）または偶数周波数を決定することである。再度、ＤＣＴ近似の基底の制約によれば、偶数基底関数は、ＤＣＴ変換のものに十分相関するべきである。８点ＤＣＴ変換では、偶数基底関数は以下のようになる。
【００８４】
【数３１】
周波数２および６におけるノルム制約は、
【００８６】
【数３２】
によって与えられる。整数ペア｛１６，６｝はこのノルム制約を約１％以内まで満たす。
【００８８】
結果として生じる（ステップ２および３で決定された整数係数を使用する）８点変換行列は、以下のようになる。
【００８９】
【数３３】
構築プロセス６００の第４のステップ６４０は、４点変換を生成する。上（ステップ６１０〜６３０）で論じたように生成された８点変換では、ＤＣ基底関数の一定の乗数はｄ８＝１２である。したがって、４点変換のための一定の乗数はｄ４＝１７である。ＤＣＴ近似の基底では、これはＤ１およびＤ２という係数を、生成される以下の基底関数において残す。
【００９１】
【数３４】
上の基底関数による行列は、いかなる選択のＤ１およびＤ２についても本質的に直交している。しかし、ＤＣＴ近似の変換の制約によれば、これらの係数が、
【００９３】
【数３５】
に等しいＤＣＴ回転因子（すなわち、Ｄ１／Ｄ２の比率）によって関係付けられる。さらに、これらの係数はノルム制約Ｄ１２＋Ｄ２２≒５７８に従う。直交性、ＤＣＴ近似の基底およびノルム制約を約１％以内まで満たす整数のペアは、整数ペア｛２２，１０｝である。これは、４点変換について以下の基底関数を生じる。
【００９５】
【数３６】
ＶＩ．変換の実装（続き）
図５に戻ると、上の構築プロセス６００を使用して生成された変換行列は本質的に変換を定義する。２次元変換では、基底関数が各ディメンションにおいてサンプル・データ・ブロックに適用される。例示した変換の実装５００では、基底関数が前−乗算５１０においてサンプル・データ・ブロックの行に適用され、次いで後−乗算５３０でサンプル・データ・ブロックの列に適用される。この変換が直交するように構築されるので、一致した変換行列が、順方向３００および逆方向３１０の変換について使用される。非ユニタリ・ノルムを有する変換基底関数なので、例示した実装は、また、スケーリング・ステージ５２０および５４０を逆変換で含んで、変換によって導入された範囲の拡張を補償する。このような範囲制限された実装を、順方向変換のために使用することもできるが、ビデオ符号化においては、順方向変換における範囲制限はしばしば冗長である。エンコード・プロセスはデコードより低速であり、かつエンコーダで使用可能な計算リソースはしばしばデコーダのものより桁違いに高いので、エンコーダをより高い精度（例えば、３２ビット）の整数または倍精度浮動小数点で、実装することができる。したがって、以下の考察ではまず、上で記載した変換行列を使用した逆方向変換の例示的実装を考察する。
【００９７】
逆方向変換の実装。
先に記載したような変換の実装５００では、前−乗算ステージ５１０において、適切なサイズの変換行列（例えば、８×８データ・ブロックでは上の行列Ｔ８）による行列乗算を実行することによって、変換領域データ・ブロックの行（以下の考察ではＤと示す）が逆方向変換される。後−乗算ステージ５３０において、同じくこの変換行列による行列乗算を実行することによって、変換領域データ・ブロックの列が逆方向変換される。この順序付けを逆にすることができるが、これは不適合の結果となる可能性が高い。前−乗算および後−乗算ステージのための変換行列は、上に記載したように構築された変換行列である。
【００９８】
スケーリング・ステージ５２０および５４０では、例示的変換の実装におけるスケーリングが、上で論じた、スケーリングされた整数の実装の制約（すなわち、スケーリングは、標準システムおよびグラフィックス・プロセッサの計算を容易にするために、２のべき乗による）に従って、決定される。したがって、スケーリングは、変換行列の基底関数の２乗ノルムに最も近い２のべき乗となるように選択される。
【００９９】
より詳細には、逆方向変換のための標準的な公式を以下のように表すことができる。
【０１００】
【数３７】
ただし、Ｄは、逆方向変換への入力（Ａ）での変換領域データ・ブロックを示す。以下の考察では、Ｄ１は、変換の実装５００の第１の乗算ステージ５１０から出力されたデータ・ブロックを表し、Ｒは、行および列関連の逆方向変換の後の、再構築された出力を表す。分母ｓはスケーリング係数である。Ｄ、Ｄ１およびＲは、同形の８×８、８×４または４×８行列である。表記法において、行列およびスカラーを含む演算は、行列におけるエントリ関連の演算である。同様に、行列引数を有するスカラー演算は、行列におけるエントリ関連のスカラー演算である。
【０１０２】
分母ｓは、基底関数の２乗ノルムに最も近い２のべき乗となるように選択される。８×８の逆方向変換では、１次元の８点基底関数の２乗ノルムの値は｛１１５２，１１５６，１１６８｝である。したがって、分母が１０２４となるように選択され（すなわち、ｓ＝１０２４）、これはこれらの２乗ノルム値に最も近い２のべき乗である。実際のノルムとこの分母の間の比率（すなわち、ノルム／ｓ≒１．１２）は１に近いので、標準ＩＤＣＴについて使用された量子化パラメータと、例示した変換の実装について使用されたものの間に密接な対応がある。すべての残りの正規化（本質的には、１０２４／基底関数の２乗ノルムによる）が、以下に記載する順方向変換プロセスで実行されるので、誤りが付加されることはない。
【０１０３】
上の範囲制約の考察によれば、逆方向変換の入力での変換領域データ・ブロックＤは、例示した実装において１２ビットの範囲を有する。（正規化のため、順方向変換から生じた変換領域データ・ブロックが実際には±２０４８／１．１２に減らされる。）標準的な中間行列（１次元における逆方向変換の後のもの）は、以下のようになる。
【０１０４】
【数３８】
これは１０．５ビットよりわずかに低い範囲を有する。
【０１０６】
１つの逆方向変換の実装５００では、スケーリング・ステージ５２０および５４０はそれぞれ、データ・ブロック値を５ビット位置だけ切り捨てるか、あるいはシフトすること（実際には、３２による除算）ができ、これは同時に（１０２４による除算について）１０ビット位置だけシフトする。これは、乗算ステージ５１０および５３０での範囲制約を１６ビット範囲内に維持する。
【０１０７】
代替実装は、第２の後−乗算ステージのための演算精度を保持し、これは、第１のスケーリング・ステージ５２０でのスケーリングまたは丸めの量を減らすことによって行う。第１の乗算ステージの後の結果のデータ・ブロックＤ１は、１０．５ビットの範囲を使用し、８点変換は範囲を４ビットにより拡張するので、スケーリングの多くとも１ビット少ないものを第１のスケーリング・ステージで許容して、両方の乗算ステージで１６ビット範囲制約内に残るようにすることができる。したがって、代替実装は、第１のスケーリング・ステージ５２０で４ビットだけ、第２のスケーリング・ステージ５４０で６ビットだけシフトすることができる。この変換の標準的な表現は、このとき、以下の通りである。
【０１０８】
【数３９】
この代替実装は、追加の精度のビットがＤ１で保持されることを可能にする。この同じスケーリングを４点変換のために使用することができ、これは、４点変換行列における最大乗数が、どうにか、なお、使用可能なヘッドルーム（４．５ビット）内であるからである。
【０１１０】
第２の追加の精度のビットを中間データ・ブロックＤ１で保持するために、さらなる代替実装は変換行列を次のように分解する。
【０１１１】
【数４０】
ここで、奇数成分行列
【０１１３】
【数４１】
および
【０１１５】
【数４２】
は０、１および−１のみをエントリとして有することが許容される。Ｔ８のエントリの大部分は偶数であるので、
【０１１７】
【数４３】
はスパース（sparse）行列である。同様に、
【０１１９】
【数４４】
は、
【０１２１】
【数４５】
に非常に相関された構造を有する。このさらなる代替逆方向変換の実装の標準的な表現が、このとき以下のように定義される。
【０１２３】
【数４６】
第１のスケーリング・ステージ５２０はこのとき３ビットのみ下にシフトし、第２の乗算ステージ５３０のための余分の精度を保持する。偶数成分はＴ８の範囲の半分を有するので、また、奇数成分
【０１２５】
【数４７】
は、０、１および−１のエントリを有するように制限されるので、変換の第２のステージにおいて結果として生じる分子は、１６ビットに制限された範囲である。この方法には、精度Ｄ１での余分の精度のビットのために受ける、計算上の小さい不利がある。それにもかかわらず、この変換行列の分解は、結果として改善された演算精度をごくわずかなコストでもたらす。
【０１２７】
他の代替実装では、変換Ｔをより一般に成分変換行列ＴａおよびＴｂに分解することができ、これらが変換基底Ｔに、Ｔ＝２ｘ・Ｔａ＋Ｔｂとして関係付けられる。この変換の計算は以下の通りである。
【０１２８】
【数４８】
次いでこれを以下のように定義することができる。
【０１３０】
【数４９】
この計算を、行列乗算およびシフト演算を使用して、以下のように実装することができる。
（Ｄ・Ｔａ＋（（Ｄ・Ｔｂ）＞＞ｘ））＞＞（ｙ−ｘ）
【０１３２】
変換Ｔ８の特定の代替実装に戻ると、８点変換の奇数および偶数成分が以下のように示される。
【０１３３】
【数５０】
【数５１】
が２つの独立したゼロでない列のみを有することに留意されたい。
【０１３６】
【数５２】
による後乗算は、以下のように２つの加算（および否定）のみと同等である。
【０１３８】
【数５３】
ただし、以下の通りである。
【０１４０】
【数５４】
４点逆方向変換の偶数および奇数成分は、以下の通りである。
【０１４２】
【数５５】
このさらなる代替実装では、８×８逆方向変換のための行関連または前−乗算ステージ５１０および第１のスケーリング・ステージ５２０は、以下の演算を実行する。
Ｄ１＝（Ｄ・Ｔ８＋４）＞＞３
【０１４４】
この逆方向変換の実装における列関連または後−乗算ステージ５３０およびスケーリング・ステージ５４０は、最初に、Ｔ８の奇数成分を見て８つの要素の２つの共通の行を計算することによって定義される。これらは右に１ビットだけシフトされ、次いで、この結果が６ビットだけ下に丸められる前に、偶数成分の積に加算される（あるいはそれから減算される）。したがって、これらのステージにおいて実行される演算は以下のように表現される。
【０１４５】
【数５６】
さらなる代替実装における４×８逆方向変換（本明細書で使用される規定によれば、これは４列および８行を有するアレイを指す）では、行関連または前−乗算ステージ５１０およびスケーリング・ステージ５２０は、以下のように定義される４点演算を実行する。
Ｄ１＝（Ｄ・Ｔ４＋４）＞＞３
【０１４７】
この変換の第２の部分では、列関連または後−乗算ステージ５３０およびスケーリング・ステージ５４０は、上に記載した８×８逆方向変換のためのものに等しい。
【０１４８】
８×４逆方向変換では、さらなる代替実装は、行関連ステージ５１０およびスケーリング・ステージ５２０において、４行／８列の変換領域データ上で、以下に従って演算する。
Ｄ１＝（Ｄ・Ｔ８＋４）＞＞３
【０１４９】
列関連ステージ５３０およびスケーリング・ステージ５４０のための４点逆方向変換は、以下のように定義される。
【０１５０】
【数５７】
４×４逆方向変換では、４×４逆方向変換のステージ５１０、５３０が、４×８逆方向変換の行関連ステージ５１０および８×４逆方向変換の列関連ステージ５３０それぞれについて上に記載したように、実装される。
【０１５２】
順方向変換の実装。
スケーリング・ステージを含む図５に例示したような、範囲制限された実装を順方向変換にも適用することができるが、ビデオ符号化においては、このような手順はしばしば冗長である。エンコード・プロセスはデコードより低速であり、かつエンコーダで使用可能な計算リソースはしばしばデコーダのものより桁違いに高いので、エンコーダをより高い精度（例えば、３２ビット）の整数または倍精度浮動小数点で実装することができる。すなわち、順方向変換の実装において、スケーリング・ステージ５２０、５４０を省略することができる。
【０１５３】
図７に示す、好ましい順方向変換の実装では、再正規化ステージ７４０が順方向変換側で（行関連および列関連乗算７１０および７３０の後に）実行されて、再構築において、変換自体が最低量の誤りをもたらすように保証される。これにより、基底関数のノルムにおけるわずかな差異を補償し、使用可能な計算リソースがより少ない可能性のあるデコーダでの計算の負担を減らす。別法として、十分な計算リソースをデコードで設けているシステムでは、補償（変換データのスケーリング）をデコーダで実行することができる。
【０１５４】
以下の考察では、記号
【０１５５】
【数５８】
は、等しいサイズの行列の要素関連の積を示す。元の２−Ｄ信号（サンプル・データ・ブロック）をＸと示し、その変換をＹと示す（Ｘ１は、行関連の変換のすぐ後のブロックを示す）。行列ＸおよびＹは同じサイズであり、８×８、８×４および４×８の場合を包含する。以下のスケーリング係数が使用される。
【０１５７】
【数５９】
８×８順方向変換では、ステージ７１０、７３０および７４０における処理が以下のように記載される。
【０１５９】
【数６０】
４×８順方向変換では、ステージが以下を実行する。
【０１６１】
【数６１】
他方では、８×４順方向変換は、上の４×８順方向変換についての転置された変換である。
【０１６３】
４×４順方向変換は、以下のようにスケーリングを実装する。
【０１６４】
【数６２】
ＶＩＩ．適切なコンピューティング環境
上に記載した変換を、イメージおよびビデオ信号処理が実行される様々なデバイスのいずれかにおいて実行することができ、これには、他の実施例の中でも、コンピュータ、イメージおよびビデオ記録、送信および受信装置、ポータブル・ビデオ・プレイヤー、テレビ会議およびその他が含まれる。イメージおよびビデオ符号化技術をハードウェアの回路において、ならびに、図８に示すような、コンピュータまたは他のコンピューティング環境内で実行するイメージおよびビデオ処理ソフトウェアにも実装することができる。
【０１６６】
図８は、記載した実施形態を実装することができる、適切なコンピューティング環境（８００）の汎用の実施例を例示している。本発明は、多様な汎用または専用コンピューティング環境において実装できるので、コンピューティング環境（８００）は、本発明の使用または機能性の範囲についていかなる限定も示唆するように意図されたものではない。
【０１６７】
図８を参照すると、コンピューティング環境（８００）は、少なくとも１つの処理装置（８１０）およびメモリ（８２０）を含む。図８では、この最も基本的な構成（８３０）が破線内に含まれる。処理装置（８１０）はコンピュータ実行可能命令を実行し、従って、現実の、あるいは仮想プロセッサにすることができる。多重処理システムでは、多重処理装置がコンピュータ実行可能命令を実行して処理能力を高める。メモリ（８２０）は、揮発性メモリ（例えば、レジスタ、キャッシュ、ＲＡＭ）、不揮発性メモリ（例えば、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリなど）、またはこの２つのある組合せにすることができる。メモリ（８２０）は、記載したイメージおよび／またはビデオ・エンコーダ／デコーダおよび変換を実装するソフトウェア（８８０）を格納する。
【０１６８】
コンピューティング環境は追加の機能を有することができる。例えば、コンピューティング環境（８００）は、記憶装置（８４０）、１つまたは複数の入力デバイス（８５０）、１つまたは複数の出力デバイス（８６０）、および１つまたは複数の通信接続（８７０）を含む。バス、コントローラまたはネットワークなどの相互接続メカニズム（図示せず）は、コンピューティング環境（８００）のコンポーネントを相互接続する。通常、オペレーティング・システム・ソフトウェア（図示せず）が、コンピューティング環境（８００）において実行する他のソフトウェアのためのオペレーティング環境を提供し、コンピューティング環境（８００）のコンポーネントのアクティビティを調整する。
【０１６９】
記憶装置（８４０）はリムーバブルまたは非リムーバブルにすることができ、これには、磁気ディスク、磁気テープまたはカセット、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、ＤＶＤ、または、情報を格納するために使用することができ、かつコンピューティング環境（８００）内でアクセスすることができる他のいずれかの媒体が含まれる。記憶装置（８４０）は、量子化行列を生成かつ圧縮するオーディオ・エンコーダを実装するソフトウェア（８８０）のための命令を格納する。
【０１７０】
入力デバイス（８５０）は、キーボード、マウス、ペンまたはトラック・ボールなどのタッチ入力デバイス、音声入力デバイス、走査デバイス、または、入力をコンピューティング環境（８００）に提供する別のデバイスにすることができる。オーディオについては、入力デバイス（８５０）をサウンド・カード、または、アナログまたはデジタル形式におけるオーディオ入力を受け入れる類似のデバイス、またはオーディオ・サンプルをコンピューティング環境に提供するＣＤ−ＲＯＭリーダにすることができる。出力デバイス（８６０）は、ディスプレイ、プリンタ、スピーカ、ＣＤライタ、または、コンピューティング環境（８００）からの出力を提供する別のデバイスにすることができる。
【０１７１】
通信接続（８７０）は、通信媒体を介して別のコンピューティング・エンティティへの通信を可能にする。通信媒体は、コンピュータ実行可能命令、圧縮されたオーディオまたはビデオ情報、または変調されたデータ信号における他のデータなどの情報を搬送する。変調されたデータ信号は、信号中に情報をエンコードするような方法で設定された、あるいは変更された１つまたは複数の特性を有する信号である。例として、限定しないが、通信媒体には、電気、光学、ＲＦ、赤外線、音響または他の搬送波により実装されるワイヤードまたはワイヤレス技術が含まれる。
【０１７２】
本明細書の変換および符号化／復号技術を、一般にコンピュータ可読媒体内に記述することができる。コンピュータ可読媒体は、コンピューティング環境内でアクセスすることができるいずれかの使用可能な媒体である。例として、限定しないが、コンピューティング環境（８００）では、コンピュータ可読媒体は、メモリ（８２０）、記憶装置（８４０）、通信媒体、および上記のいずれかの組合せを含む。
【０１７３】
本明細書の変換および符号化／復号技術を、ターゲットの、実際の、あるいは仮想のプロセッサ上のコンピューティング環境において実行される、プログラム・モジュールに含まれるような、一般にコンピュータ実行可能命令に関連して記述することができる。一般に、プログラム・モジュールには、ルーチン、プログラム、ライブラリ、オブジェクト、クラス、コンポーネント、データ構造など、特定のタスクを実行するか、あるいは特定の抽象データ型を実装するものが含まれる。プログラム・モジュールの機能性を、様々な実施形態において望まれるように、複数のプログラム・モジュールの間で結合あるいは分割することができる。プログラム・モジュールのためのコンピュータ実行可能命令を、ローカルまたは分散コンピューティング環境内で実行することができる。
【０１７４】
説明のため、詳細な説明では、「決定する」、「生成する」、「調整する」および「適用する」のような用語を使用して、コンピューティング環境におけるコンピュータ・オペレーションを記載した。これらの用語は、コンピュータによって実行されるオペレーションについての高レベルの抽象であり、人間によって実行される動作と混同されるべきではない。これらの用語に対応する実際のコンピュータ・オペレーションは、実装に応じて変わる。
【０１７５】
ＶＩＩＩ．拡張
上に記載した変換およびそれらの実装を、以下のものを含む、様々な方法で拡張することができる。
【０１７６】
変換の実装の変形形態には、オルタネート・ラウンディング（alternate rounding）、「バタフライ（butterfly）」実装および双直交公式化（biorthgonal formulations）が含めることができる。
【０１７７】
さらに、上に記載した構築プロセスの後に続いて、異なるビット範囲制約を受けて、異なる係数範囲を有する変換の変形形態を生成することができる。
【０１７８】
構築手順において使用された制約のしきい値のパラメータを変更して、より大きいセットの制約変換を生じさせることができる。
【０１７９】
変換セットを拡張して、さらなるブロック・サイズ（例えば、４×４および他のブロック・サイズの変換）を含むようにすることができる。同様に、生成された変換セットは必ずしも、上に例示した実装におけるサイズ（すなわち、８×８、８×４および４×８変換）を含まない可能性がある。変換を他のサイズのブロック、およびより高い（２より高い）次元まで拡張することができる。
【０１８０】
ビット深度の選択は可変パラメータであり、（生のピクセル値の８ビット分解能、および中間結果についての１６ビットを使用した）例示した実施例について任意に変更することができる。
【０１８１】
順方向変換の実装を、逆方向変換の実装を範囲制限するために記載した手順を使用することなどによって、範囲制限することもできる。
【０１８２】
上に記載した構築プロセスの後に続いて、他の非ＤＣＴ基底関数に近似する変換を生成することができる。例えば、構築プロセスは、スケールされた整数、完全な再構築および範囲制限における制約を満たしながら、ＦＦＴ、ウェーブレット、または他のオーバーラップ変換を近似する変換を生成することができる。
【０１８３】
本発明の原理を、記載した実施形態を参照して記載かつ例示したが、記載した実施形態の構成および詳細を、このような原理から逸脱することなく修正できることは理解されよう。本明細書に記載したプログラム、プロセスまたは方法は、そうでないと指示されない限り、いずれかの特定のタイプのコンピューティング環境に関係付けられず、あるいは限定されないことを理解されたい。様々なタイプの汎用または専用コンピューティング環境は、本明細書に記載した技術によるオペレーションと共に使用することができ、あるいはこれを実行することができる。ソフトウェアにおいて示した記載の実施形態の要素をハードウェアにおいて実施することができ、その逆も可能である。
【０１８４】
変換符号化技術を本明細書のところどころで、単一の統合されたシステムの一部として記載するが、これらの技術を他の技術と組み合わせて別々に、潜在的に適用することができる。代替実施形態では、エンコーダまたはデコーダ以外の信号処理ツールがこれらの技術の１つまたは複数を実装する。
【０１８５】
記載した変換および変換符号化の実施形態は、様々な技術を実行する。これらの技術のためのオペレーションを通常、提示のために特定の一連の順序で記載するが、この記載の方法は、特定の順序が必要とされない限り、オペレーションの順序における重要でない再配列を包含することを理解されたい。例えば、順次に記載したオペレーションを、いくつかの場合では、再配列あるいは同時に実行することができる。さらに、簡単にするため、流れ図では通常、特定の技術を他の技術と共に使用することができる様々な方法を図示していない。
【０１８６】
本発明の原理を適用することができる多数の可能な実施形態に鑑みて、本発明として、特許請求の範囲およびその同等物の範囲および趣旨内に入る可能性のあるこのようなすべての実施形態を請求する。
【図面の簡単な説明】
【図１】本明細書に記載した変換のクラスに基づくビデオ・エンコーダのブロック図である。
【図２】本明細書に記載した変換のクラスに基づくビデオ・デコーダのブロック図である。
【図３】２次元変換を例示するブロック図である。
【図４】図１および２のビデオ・エンコーダおよびデコーダによる、本明細書に記載した変換のクラスを使用した変換符号化を例示するデータ流れ図である。
【図５】本明細書に記載した変換のクラスについての逆方向変換の実装のブロック図である。
【図６】本明細書に記載した変換のクラスのうち１つを構築するためのプロセスの流れ図である。
【図７】本明細書に記載した変換のクラスについての順方向変換の実装のブロック図である。
【図８】図１および２の、記載した変換のクラスに基づくビデオ・エンコーダ／デコーダのための適切なコンピューティング環境のブロック図である。
【符号の説明】
１００ 汎用ビデオ・エンコーダ
１０５ カレント・フレーム
１１０ 動き予測器
１１５、２１５ 動き情報
１２０、２２０ フレーム・ストア
１２５、２２５ 参照フレーム
１３０、２３０ 動き補償器
１３５ 動き補償されたカレント・フレーム
１４５ 予測残差
１６０ 周波数変換器
１６６、２６０ 逆周波数変換器
１７０ 量子化器
１７６、２７０ 逆量子化器
１８０ エントロピー符号器
１９０、２９０ バッファ
１９５、２９５ 圧縮されたビデオ情報
２００ 汎用ビデオ・デコーダ
２０５ 再構築されたフレーム
２３５ 予測フレーム
２４５ 再構築された残差
２８０ エントロピー復号器
Ｔ 前−乗算変換行列
Ｔ’ 後−乗算変換行列
Ｓ１ シフトさせるビット位置
Ｓ２ シフトさせるビット位置
Claims (21)
- イメージ・データの２次元ブロックで、当該ブロックの少なくとも１つのディメンションは８点である、２次元ブロックを空間領域表現と変換領域表現との間で変換する方法であって、
結果として生じる行列の積を、ビット範囲制限内に残るようにスケーリングすること
を備え、
前記イメージ・データ・ブロックは８×８ブロックであり、前記少なくとも１つの行列乗算を実行することは、前記変換行列を使用して、前記イメージ・データ・ブロックの行関連および列関連の行列乗算を実行することを備え、
前記スケーリングすることは、各前記行関連および列関連の行列乗算の後に、２のべき乗による除算を実施する行列の構成要素関連のシフト演算を備える
ことを特徴とする記載の方法。 - 第１の前記行列乗算の後の前記行列の構成要素関連のシフト演算は、第２の前記行列乗算の後よりも少ないビット位置によるシフトであることを特徴とする請求項１に記載の方法。
- 前記行列の構成要素関連のシフト演算は、各前記行列乗算の後のビット位置に等しい数によるシフトであることを特徴とする請求項１に記載の方法。
- イメージ・データの２次元ブロックで、当該ブロックの少なくとも１つのディメンションは８点である２次元ブロックを空間領域表現と変換領域表現との間で変換する方法をコンピュータ上で実行するための、格納されているコンピュータ実行可能プログラム命令を有するコンピュータ可読記憶媒体であって、前記方法は、
結果として生じる行列の積を、ビット範囲制限内に残るようにスケーリングすること
を備え、
前記イメージ・データ・ブロックは８×８ブロックであり、前記少なくとも１つの行列乗算を実行することは、前記変換行列を使用して、前記イメージ・データ・ブロックの行関連および列関連の行列乗算を実行することを備え
前記スケーリングすることは、各前記行関連および列関連の行列乗算の後に、２のべき乗による除算を実施する行列の構成要素関連のシフト演算を備える
ことを特徴とするコンピュータ可読記憶媒体。 - イメージ・データの２次元ブロックで、ブロックの少なくとも１つのディメンションは４点である２次元ブロックを空間領域表現と変換領域表現との間で変換する方法であって、
結果として生じる行列の積を、ビット範囲制限内に残るようにスケーリングすること
を備え、前記イメージ・データ・ブロックは４×４ブロックであり、前記少なくとも１つの行列乗算を実行することは、前記変換行列を使用して前記イメージ・データ・ブロックの行関連および列関連の行列乗算を実行することを備え、
前記スケーリングすることは、各前記行関連および列関連の行列乗算の後に、２のべき乗による除算を実施する行列の構成要素関連のシフト演算を備える
ことを特徴とする方法。 - 前記行列乗算の第１番目のものの後の前記行列の構成要素のシフト演算は、前記行列乗算の第２番目のものの後よりも少ないビット位置によるシフトであることを特徴とする請求項５に記載の方法。
- 前記行列の構成要素関連のシフト演算は、各前記行列乗算の後のビット位置に等しい数によるシフトであることを特徴とする請求項５に記載の方法。
- イメージ・データの２次元ブロックで、当該ブロックの少なくとも１つのディメンションは４点である２次元ブロックを空間領域表現と変換領域表現との間で変換する方法をコンピュータ・システム上で実行するための、格納されているコンピュータ実行可能プログラム命令を有するコンピュータ可読記憶媒体であって、前記方法は、
結果として生じる行列の積を、ビット範囲制限内に残るようにスケーリングすること
を備え、
前記イメージ・データ・ブロックは４×４ブロックであり、前記少なくとも１つの行列乗算を実行することは、前記変換行列を使用して前記イメージ・データ・ブロックの行関連および列関連の行列乗算を実行することを備え
前記スケーリングすることは、各前記行関連および列関連の行列乗算の後に、２のべき乗による除算を実施する行列の構成要素関連のシフト演算を備える
ことを特徴とするコンピュータ可読記憶媒体。 - イメージ・データの２次元ブロックで、当該ブロックのディメンションは４および８点である２次元ブロックを空間領域表現と変換領域表現との間で変換する方法であって、
結果として生じる行列の積を、ビット範囲制限内に残るようにスケーリングすること
を備え、
前記データ・ブロックは４×８点のディメンションを有し、前記行列乗算を実行する動作は、前記データ・ブロックをＸで表し、前記結果として生じる行列の積をＹとして、関係式Ｙ＝（Ｔ８・Ｘ・Ｔ’４）に従って実行されることを特徴とする方法。 - イメージ・データの２次元ブロックで、当該ブロックのディメンションは４および８点である２次元ブロックを空間領域表現と変換領域表現との間で変換する方法であって、
結果として生じる行列の積を、ビット範囲制限内に残るようにスケーリングすること
を備え、
前記データ・ブロックは８×４点のディメンションを有し、前記行列乗算を実行する動作は、前記データ・ブロックをＸで表し、前記結果として生じる行列の積をＹとして、関係式Ｙ＝（Ｔ４・Ｘ・Ｔ’８）に従って実行されることを特徴とする方法。 - イメージ・データの２次元ブロックで、当該ブロックのディメンションは４および８点である２次元ブロックを空間領域表現と変換領域表現との間で変換する方法をコンピュータ・システム上で実行するための、格納されているコンピュータ実行可能プログラム命令を有するコンピュータ可読記憶媒体であって、前記方法は、
結果として生じる行列の積を、ビット範囲制限内に残るようにスケーリングすること
を備え、
前記データ・ブロックは８×４点のディメンションを有し、前記行列乗算を実行する動作は、前記データ・ブロックをＸで表し、前記結果として生じる行列の積をＹとして、関係式Ｙ＝（Ｔ４・Ｘ・Ｔ’８）に従って実行される
ことを特徴とするコンピュータ可読記憶媒体。 - メディア・コンテンツを表現するデータ・ブロックを変換符号化する方法であって、
整数を使用することによって引き起こされた不一致であるが、演算結果のスケーリングをすることによって実質的に無くすことが可能な不一致を有する複数のノルム（norms）を有する変換基底関数のセットを備える変換を前記データ・ブロックに適用して、前記メディア・コンテンツを表現する変換領域データ・ブロックを生じさせること、および、
前記不一致を有する複数のノルム（norms）に対して補償するために、整数を使用することによって演算結果に引き起こされた不一致を補償するためにあらかじめ定められたスケーリング係数に従って前記変換領域データ・ブロックにおける値をスケーリングすること、
前記変換を適用することは、
スケーリングすることは、
ことを特徴とする方法。 - 前記不一致を有する複数のノルム（norms）を補償するためにスケーリングすることは、デコードでの計算負荷を削減するように、エンコードにおいて実行されることを特徴とする請求項１２に記載の方法。
- 前記不一致を有する複数のノルム（norms）を補償するためにスケーリングすることは、エンコードでの計算負荷を削減するように、デコードにおいて実行されることを特徴とする請求項１２に記載の方法。
- メディア・コンテンツを表現するデータ・ブロックを変換符号化する方法であって、
整数を使用することによって引き起こされた不一致であるが、演算結果のスケーリングをすることによって実質的に無くすことが可能な不一致を有する複数のノルム（norms）を有する変換基底関数のセットを備える変換を前記データ・ブロックに適用して、前記メディア・コンテンツを表現する変換領域データ・ブロックを生じさせること、および、
前記不一致を有する複数のノルム（norms）に対して補償するために、整数を使用することによって演算結果に引き起こされた不一致を補償するためにあらかじめ定められたスケーリング係数に従って前記変換領域データ・ブロックにおける値をスケーリングすること、
前記変換を適用することは、
スケーリングすることは、
ことを特徴とする方法。 - メディア・コンテンツを表現するデータ・ブロックを変換符号化する方法であって、
整数を使用することによって引き起こされた不一致であるが、演算結果のスケーリングをすることによって実質的に無くすことが可能な不一致を有する複数のノルム（norms）を有する変換基底関数のセットを備える変換を前記データ・ブロックに適用して、前記メディア・コンテンツを表現する変換領域データ・ブロックを生じさせること、および、
前記不一致を有する複数のノルム（norms）に対して補償するために、整数を使用することによって演算結果に引き起こされた不一致を補償するためにあらかじめ定められたスケーリング係数に従って前記変換領域データ・ブロックにおける値をスケーリングすること、
前記変換を適用することは、
スケーリングすることは、
ことを特徴とする方法。 - メディア・コンテンツを表現するデータ・ブロックを変換符号化する方法を達成するコンピュータ・システム上で実行する、格納されているコンピュータ実行可能プログラム命令を有するコンピュータ可読記憶媒体であって、前記方法は、
整数を使用することによって引き起こされた不一致であるが、演算結果のスケーリングをすることによって実質的に無くすことが可能な不一致を有する複数のノルム（norms）を有する変換基底関数のセットを備える変換を前記データ・ブロックに適用して、前記メディア・コンテンツを表現する変換領域データ・ブロックを生じさせること、および、
整数を使用することによって演算結果に引き起こされた不一致を補償するためにあらかじめ定められたスケーリング係数に従って前記変換領域データ・ブロックにおける値をスケーリングして、前記不一致を有する複数のノルム（norms）に対して補償すること
を備え、
前記変換を適用して、前記メディア・コンテンツを表現する変換領域データ・ブロックを生じさせることは、
スケーリングすることは、
ことを特徴とするコンピュータ可読記憶媒体。 - メディア・コンテンツを表現するデータ・ブロックＤを変換符号化する方法であって、
前記メディア・ブロックの空間領域表現と変換領域表現との間で変換であって、Ｔを変換基底関数の行列とし、前記変換の結果をＲとすると
前記計算することは、
前記データ・ブロックの行列乗算を、前記変換基底関数行列にＴ＝２ｘ・Ｔａ＋Ｔｂとして関係付けられた第１および第２の変換副成分行列（ＴａおよびＴｂ）を使用して実行すること、
前記データ・ブロックおよび第２の副成分行列の積を、ｘビット位置だけシフトすること、ここで、ｘは１に等しいか、１よりも大きい整数であり、
前記データ・ブロックおよび第１の副成分行列の積と、前記データ・ブロックおよび第２の副成分行列の積がｘビットだけシフトされた結果を合計すること、
１に等しいか、１よりも大きい整数のｙであって、前記合計された結果をｙビット位置だけシフトして前記結果Ｒを生じさせること
を備え、それにより前記変換のヘッドルームが拡張されることを特徴とする方法。 - 前記変換基底関数行列は、
- 前記変換基底関数行列は、
- メディア・コンテンツを表現するデータ・ブロックＤを変換符号化する方法をコンピュータ・システム上で実行する、格納されているコンピュータ実行可能プログラム命令を有するコンピュータ可読記憶媒体であって、前記方法は、
前記メディア・ブロックの空間および変換領域表現の間で変換するための変換であって、Ｔを変換基底関数の行列とし、前記変換の結果をＲとすると、
を備え、前記計算することは、
前記データ・ブロックの行列乗算を、前記変換基底関数行列にＴ＝２ｘ・Ｔａ＋Ｔｂとして関係付けられた第１および第２の変換副成分行列（ＴａおよびＴｂ）を使用して実行すること、
前記データ・ブロックおよび第２の副成分行列の積を、ｘビット位置だけシフトすること、ここで、ｘは１に等しいか、１よりも大きい整数であり、
前記データ・ブロックおよび第１の副成分行列の積と、前記データ・ブロックおよび第２の副成分行列の積がｘビットだけシフトされた結果を合計すること、および、
１に等しいか、１よりも大きい整数のｙであって、前記合計された結果をｙビット位置だけシフトして前記結果Ｒを生じさせること
を備え、それにより前記変換のヘッドルームが拡張されることを特徴とするコンピュータ可読記憶媒体。
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US37729802P | 2002-05-02 | 2002-05-02 | |
| US60/377,298 | 2002-05-02 | ||
| US10/376147 | 2003-02-28 | ||
| US10/376,147 US7242713B2 (en) | 2002-05-02 | 2003-02-28 | 2-D transforms for image and video coding |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2003333598A JP2003333598A (ja) | 2003-11-21 |
| JP4425561B2 true JP4425561B2 (ja) | 2010-03-03 |
Family
ID=29273051
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2003122704A Expired - Lifetime JP4425561B2 (ja) | 2002-05-02 | 2003-04-25 | イメージおよびビデオ符号化のための２−ｄ変換 |
Country Status (8)
| Country | Link |
|---|---|
| US (1) | US7242713B2 (ja) |
| EP (1) | EP1359546B1 (ja) |
| JP (1) | JP4425561B2 (ja) |
| KR (1) | KR100965704B1 (ja) |
| CN (1) | CN100379292C (ja) |
| AT (1) | ATE339744T1 (ja) |
| DE (1) | DE60308255T2 (ja) |
| HK (1) | HK1060205A1 (ja) |
Families Citing this family (86)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6882685B2 (en) | 2001-09-18 | 2005-04-19 | Microsoft Corporation | Block transform and quantization for image and video coding |
| IL147370A (en) * | 2001-12-27 | 2007-07-24 | Itzhak Florentin | Method and system for guiding a remote vehicle via a retarded communication channel |
| US7129962B1 (en) * | 2002-03-25 | 2006-10-31 | Matrox Graphics Inc. | Efficient video processing method and system |
| US7242713B2 (en) | 2002-05-02 | 2007-07-10 | Microsoft Corporation | 2-D transforms for image and video coding |
| US7760950B2 (en) * | 2002-09-26 | 2010-07-20 | Ntt Docomo, Inc. | Low complexity and unified transforms for video coding |
| US6831868B2 (en) * | 2002-12-05 | 2004-12-14 | Intel Corporation | Byte aligned redundancy for memory array |
| US7471726B2 (en) * | 2003-07-15 | 2008-12-30 | Microsoft Corporation | Spatial-domain lapped transform in digital media compression |
| JP4699685B2 (ja) * | 2003-08-21 | 2011-06-15 | パナソニック株式会社 | 信号処理装置及びそれを用いた電子機器 |
| US7369709B2 (en) * | 2003-09-07 | 2008-05-06 | Microsoft Corporation | Conditional lapped transform |
| US7724827B2 (en) | 2003-09-07 | 2010-05-25 | Microsoft Corporation | Multi-layer run level encoding and decoding |
| US7627187B2 (en) * | 2003-09-24 | 2009-12-01 | Ntt Docomo, Inc. | Low complexity and unified transforms for video coding |
| KR20050075578A (ko) * | 2004-01-16 | 2005-07-21 | 삼성전자주식회사 | 폐루프 최적화를 지원하는 스케일러블 비디오 엔코딩 방법및 장치 |
| US7487193B2 (en) | 2004-05-14 | 2009-02-03 | Microsoft Corporation | Fast video codec transform implementations |
| US8045614B2 (en) | 2005-05-11 | 2011-10-25 | Dolby Laboratories Licensing Corporation | Quantization control for variable bit depth |
| CN100440978C (zh) * | 2004-09-28 | 2008-12-03 | 华为技术有限公司 | 一种视频图像编码方法 |
| US7471850B2 (en) * | 2004-12-17 | 2008-12-30 | Microsoft Corporation | Reversible transform for lossy and lossless 2-D data compression |
| US7428342B2 (en) * | 2004-12-17 | 2008-09-23 | Microsoft Corporation | Reversible overlap operator for efficient lossless data compression |
| US7305139B2 (en) * | 2004-12-17 | 2007-12-04 | Microsoft Corporation | Reversible 2-dimensional pre-/post-filtering for lapped biorthogonal transform |
| AU2005239628B2 (en) * | 2005-01-14 | 2010-08-05 | Microsoft Technology Licensing, Llc | Reversible 2-dimensional pre-/post-filtering for lapped biorthogonal transform |
| US8311088B2 (en) * | 2005-02-07 | 2012-11-13 | Broadcom Corporation | Method and system for image processing in a microprocessor for portable video communication devices |
| US7953161B2 (en) * | 2005-04-27 | 2011-05-31 | Broadcom Corporation | System and method for overlap transforming and deblocking |
| US8422546B2 (en) * | 2005-05-25 | 2013-04-16 | Microsoft Corporation | Adaptive video encoding using a perceptual model |
| US8036274B2 (en) * | 2005-08-12 | 2011-10-11 | Microsoft Corporation | SIMD lapped transform-based digital media encoding/decoding |
| US20070047655A1 (en) * | 2005-08-26 | 2007-03-01 | Vannerson Eric F | Transpose buffering for video processing |
| WO2007027418A2 (en) * | 2005-08-31 | 2007-03-08 | Micronas Usa, Inc. | Systems and methods for video transformation and in loop filtering |
| EP2566160A3 (en) * | 2005-10-14 | 2013-08-21 | NEC Corporation | Apparatus and method for entropy coding with rate control |
| JP2007195117A (ja) * | 2006-01-23 | 2007-08-02 | Toshiba Corp | 動画像復号装置 |
| JP2007243427A (ja) * | 2006-03-07 | 2007-09-20 | Nippon Hoso Kyokai <Nhk> | 符号化装置及び復号化装置 |
| US7995649B2 (en) | 2006-04-07 | 2011-08-09 | Microsoft Corporation | Quantization adjustment based on texture level |
| US8503536B2 (en) | 2006-04-07 | 2013-08-06 | Microsoft Corporation | Quantization adjustments for DC shift artifacts |
| US8059721B2 (en) * | 2006-04-07 | 2011-11-15 | Microsoft Corporation | Estimating sample-domain distortion in the transform domain with rounding compensation |
| US8711925B2 (en) | 2006-05-05 | 2014-04-29 | Microsoft Corporation | Flexible quantization |
| JP4829019B2 (ja) * | 2006-07-06 | 2011-11-30 | 株式会社東芝 | 通信端末装置 |
| US8238424B2 (en) | 2007-02-09 | 2012-08-07 | Microsoft Corporation | Complexity-based adaptive preprocessing for multiple-pass video compression |
| US8942289B2 (en) | 2007-02-21 | 2015-01-27 | Microsoft Corporation | Computational complexity and precision control in transform-based digital media codec |
| US8498335B2 (en) | 2007-03-26 | 2013-07-30 | Microsoft Corporation | Adaptive deadzone size adjustment in quantization |
| US20080240257A1 (en) * | 2007-03-26 | 2008-10-02 | Microsoft Corporation | Using quantization bias that accounts for relations between transform bins and quantization bins |
| US8243797B2 (en) | 2007-03-30 | 2012-08-14 | Microsoft Corporation | Regions of interest for quality adjustments |
| US8442337B2 (en) | 2007-04-18 | 2013-05-14 | Microsoft Corporation | Encoding adjustments for animation content |
| US8331438B2 (en) | 2007-06-05 | 2012-12-11 | Microsoft Corporation | Adaptive selection of picture-level quantization parameters for predicted video pictures |
| US8255445B2 (en) * | 2007-10-30 | 2012-08-28 | The Chinese University Of Hong Kong | Processes and apparatus for deriving order-16 integer transforms |
| US8331454B2 (en) * | 2007-11-12 | 2012-12-11 | Cisco Technology, Inc. | Integer transform function for video compression systems |
| CN100461095C (zh) * | 2007-11-20 | 2009-02-11 | 浙江大学 | 一种支持多模式的媒体增强流水线乘法单元设计方法 |
| US8189933B2 (en) | 2008-03-31 | 2012-05-29 | Microsoft Corporation | Classifying and controlling encoding quality for textured, dark smooth and smooth video content |
| US8175165B2 (en) | 2008-04-15 | 2012-05-08 | The Chinese University Of Hong Kong | Methods and apparatus for deriving an order-16 integer transform |
| US8102918B2 (en) | 2008-04-15 | 2012-01-24 | The Chinese University Of Hong Kong | Generation of an order-2N transform from an order-N transform |
| US8369638B2 (en) * | 2008-05-27 | 2013-02-05 | Microsoft Corporation | Reducing DC leakage in HD photo transform |
| US8447591B2 (en) * | 2008-05-30 | 2013-05-21 | Microsoft Corporation | Factorization of overlapping tranforms into two block transforms |
| US8897359B2 (en) | 2008-06-03 | 2014-11-25 | Microsoft Corporation | Adaptive quantization for enhancement layer video coding |
| KR20100020441A (ko) * | 2008-08-12 | 2010-02-22 | 엘지전자 주식회사 | 비디오 신호 처리 방법 |
| US8275209B2 (en) * | 2008-10-10 | 2012-09-25 | Microsoft Corporation | Reduced DC gain mismatch and DC leakage in overlap transform processing |
| US9183181B2 (en) * | 2011-01-10 | 2015-11-10 | Cisco Technology, Inc. | Integer matrix transform video compression system, method and computer program product |
| US9110849B2 (en) | 2009-04-15 | 2015-08-18 | Qualcomm Incorporated | Computing even-sized discrete cosine transforms |
| US9069713B2 (en) * | 2009-06-05 | 2015-06-30 | Qualcomm Incorporated | 4X4 transform for media coding |
| US8762441B2 (en) * | 2009-06-05 | 2014-06-24 | Qualcomm Incorporated | 4X4 transform for media coding |
| KR101805531B1 (ko) | 2009-06-07 | 2018-01-10 | 엘지전자 주식회사 | 비디오 신호의 디코딩 방법 및 장치 |
| US9635368B2 (en) | 2009-06-07 | 2017-04-25 | Lg Electronics Inc. | Method and apparatus for decoding a video signal |
| US9118898B2 (en) | 2009-06-24 | 2015-08-25 | Qualcomm Incorporated | 8-point transform for media data coding |
| US9075757B2 (en) | 2009-06-24 | 2015-07-07 | Qualcomm Incorporated | 16-point transform for media data coding |
| US9081733B2 (en) | 2009-06-24 | 2015-07-14 | Qualcomm Incorporated | 16-point transform for media data coding |
| US8817875B2 (en) * | 2009-08-13 | 2014-08-26 | The Johns Hopkins University | Methods and systems to encode and decode sequences of images |
| RU2605677C2 (ru) | 2009-10-20 | 2016-12-27 | Франхофер-Гезелльшафт цур Фёрдерунг дер ангевандтен | Аудио кодер, аудио декодер, способ кодирования аудио информации, способ декодирования аудио информации и компьютерная программа, использующая итеративное уменьшение размера интервала |
| WO2011086066A1 (en) | 2010-01-12 | 2011-07-21 | Fraunhofer Gesellschaft zur Förderung der angewandten Forschung e.V. | Audio encoder, audio decoder, method for encoding and audio information, method for decoding an audio information and computer program using a modification of a number representation of a numeric previous context value |
| TWI415474B (zh) * | 2010-07-19 | 2013-11-11 | Mstar Semiconductor Inc | 視訊編／解碼器與其方法 |
| WO2012044076A2 (ko) | 2010-09-28 | 2012-04-05 | 삼성전자 주식회사 | 비디오의 부호화 방법 및 장치, 복호화 방법 및 장치 |
| CN101977321B (zh) * | 2010-11-04 | 2014-03-12 | 深圳市融创天下科技股份有限公司 | 一种视频编码的整数变换方法 |
| US9824066B2 (en) | 2011-01-10 | 2017-11-21 | Qualcomm Incorporated | 32-point transform for media data coding |
| GB2492333B (en) * | 2011-06-27 | 2018-12-12 | British Broadcasting Corp | Video encoding and decoding using transforms |
| AU2012276363B2 (en) | 2011-06-30 | 2016-02-18 | Samsung Electronics Co., Ltd. | Video encoding method with bit depth adjustment for fixed-point conversion and apparatus therefor, and video decoding method and aparatus therefor |
| JP5662887B2 (ja) * | 2011-07-01 | 2015-02-04 | 日本放送協会 | 符号化装置、復号装置及びプログラム |
| KR20140098114A (ko) * | 2011-11-07 | 2014-08-07 | 브이아이디 스케일, 인크. | 홀수-짝수 정수 변환 백그라운드를 사용하는 비디오 및 데이터 처리 |
| US8719321B2 (en) * | 2011-12-11 | 2014-05-06 | Hong Kong Applied Science and Technology Research Institute Company Limited | Adaptive block-size transform using LLMICT |
| WO2013109471A1 (en) * | 2012-01-19 | 2013-07-25 | Vid Scale, Inc. | System and method of video coding quantization and dynamic range control |
| CN103905825B (zh) * | 2012-12-27 | 2018-02-13 | 中国电信股份有限公司 | 视频图像的运动补偿方法和装置 |
| JP6102707B2 (ja) * | 2013-12-05 | 2017-03-29 | Ｎｔｔエレクトロニクス株式会社 | デジタル符号化装置 |
| CN104901703B (zh) * | 2015-04-08 | 2018-04-03 | 河海大学 | 一种整数序列快速压缩存储算法 |
| WO2017020167A1 (en) * | 2015-07-31 | 2017-02-09 | Hewlett Packard Enterprise Development Lp | Translate data structure to video frame structure |
| US10567800B2 (en) | 2016-11-29 | 2020-02-18 | Qualcomm Incorporated | Transform hardware architecture for video coding |
| CN106954070B (zh) * | 2017-04-28 | 2023-04-11 | 河南工程学院 | 一种滑动像素块整数dct核心矩阵变换运动补偿器及方法 |
| US11049219B2 (en) | 2017-06-06 | 2021-06-29 | Gopro, Inc. | Methods and apparatus for multi-encoder processing of high resolution content |
| CN111713104B (zh) * | 2018-02-14 | 2022-04-26 | 索尼公司 | 图像处理装置和方法 |
| US11647214B2 (en) * | 2018-03-30 | 2023-05-09 | Qualcomm Incorporated | Multiple transforms adjustment stages for video coding |
| US11228781B2 (en) | 2019-06-26 | 2022-01-18 | Gopro, Inc. | Methods and apparatus for maximizing codec bandwidth in video applications |
| US11109067B2 (en) | 2019-06-26 | 2021-08-31 | Gopro, Inc. | Methods and apparatus for maximizing codec bandwidth in video applications |
| US11481863B2 (en) | 2019-10-23 | 2022-10-25 | Gopro, Inc. | Methods and apparatus for hardware accelerated image processing for spherical projections |
| KR102723140B1 (ko) | 2021-04-27 | 2024-10-28 | 성균관대학교산학협력단 | 이미지의 암호화 방법 |
Family Cites Families (45)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS63219066A (ja) | 1987-03-06 | 1988-09-12 | Matsushita Electric Ind Co Ltd | 直交変換装置 |
| US5357594A (en) * | 1989-01-27 | 1994-10-18 | Dolby Laboratories Licensing Corporation | Encoding and decoding using specially designed pairs of analysis and synthesis windows |
| US5379351A (en) * | 1992-02-19 | 1995-01-03 | Integrated Information Technology, Inc. | Video compression/decompression processing and processors |
| US5319724A (en) | 1990-04-19 | 1994-06-07 | Ricoh Corporation | Apparatus and method for compressing still images |
| JP2945487B2 (ja) * | 1990-12-26 | 1999-09-06 | 株式会社日立製作所 | 行列乗算器 |
| JPH04282988A (ja) | 1991-03-12 | 1992-10-08 | Sony Corp | データ変換装置及び方法 |
| US5168375A (en) * | 1991-09-18 | 1992-12-01 | Polaroid Corporation | Image reconstruction by use of discrete cosine and related transforms |
| JPH0645948A (ja) | 1992-07-27 | 1994-02-18 | Victor Co Of Japan Ltd | 直交変換装置及び逆直交変換装置 |
| JPH0645949A (ja) | 1992-07-27 | 1994-02-18 | Victor Co Of Japan Ltd | 直交変換装置及び逆直交変換装置 |
| JPH0654307A (ja) | 1992-07-29 | 1994-02-25 | Casio Comput Co Ltd | データ圧縮装置 |
| JP3069455B2 (ja) * | 1992-12-22 | 2000-07-24 | 富士写真フイルム株式会社 | 画像データ圧縮伸張装置における量子化・逆量子化回路 |
| US5995539A (en) * | 1993-03-17 | 1999-11-30 | Miller; William J. | Method and apparatus for signal transmission and reception |
| JP3697717B2 (ja) * | 1993-09-24 | 2005-09-21 | ソニー株式会社 | ２次元離散コサイン変換装置および２次元逆離散コサイン変換装置 |
| US6002801A (en) * | 1995-04-18 | 1999-12-14 | Advanced Micro Devices, Inc. | Method and apparatus for improved video decompression by selection of IDCT method based on image characteristics |
| US5864637A (en) * | 1995-04-18 | 1999-01-26 | Advanced Micro Devices, Inc. | Method and apparatus for improved video decompression by selective reduction of spatial resolution |
| JP2914226B2 (ja) | 1995-06-16 | 1999-06-28 | 日本電気株式会社 | 可逆変換を可能にするディジタル信号の変換符号化方式 |
| US5701263A (en) * | 1995-08-28 | 1997-12-23 | Hyundai Electronics America | Inverse discrete cosine transform processor for VLSI implementation |
| US5933535A (en) * | 1995-10-05 | 1999-08-03 | Microsoft Corporation | Object-based video compression process employing arbitrarily-shaped features |
| US6957350B1 (en) * | 1996-01-30 | 2005-10-18 | Dolby Laboratories Licensing Corporation | Encrypted and watermarked temporal and resolution layering in advanced television |
| JPH1091614A (ja) | 1996-09-13 | 1998-04-10 | Hitachi Ltd | Ｉｄｃｔの整数化法 |
| US5883823A (en) | 1997-01-15 | 1999-03-16 | Sun Microsystems, Inc. | System and method of a fast inverse discrete cosine transform and video compression/decompression systems employing the same |
| US6058215A (en) * | 1997-04-30 | 2000-05-02 | Ricoh Company, Ltd. | Reversible DCT for lossless-lossy compression |
| US6134270A (en) * | 1997-06-13 | 2000-10-17 | Sun Microsystems, Inc. | Scaled forward and inverse discrete cosine transform and video compression/decompression systems employing the same |
| US6057855A (en) * | 1997-07-02 | 2000-05-02 | Hewlett-Packard Company | Method and apparatus for providing polygon pixel sub-sample information using incremental means |
| WO1999029112A1 (en) * | 1997-12-01 | 1999-06-10 | Matsushita Electric Industrial Co., Ltd. | Image processor, image data processor and variable length encoder/decoder |
| EP1038403B1 (de) * | 1997-12-19 | 2005-10-12 | Infineon Technologies AG | Vorrichtung zur multiplikation mit konstanten faktoren und deren verwendung zur videokompression (mpeg) |
| US6115689A (en) * | 1998-05-27 | 2000-09-05 | Microsoft Corporation | Scalable audio coder and decoder |
| US6029126A (en) * | 1998-06-30 | 2000-02-22 | Microsoft Corporation | Scalable audio coder and decoder |
| US6154762A (en) * | 1998-06-03 | 2000-11-28 | Microsoft Corporation | Fast system and method for computing modulated lapped transforms |
| US6073153A (en) * | 1998-06-03 | 2000-06-06 | Microsoft Corporation | Fast system and method for computing modulated lapped transforms |
| US6301304B1 (en) * | 1998-06-17 | 2001-10-09 | Lsi Logic Corporation | Architecture and method for inverse quantization of discrete cosine transform coefficients in MPEG decoders |
| GB9819648D0 (en) * | 1998-09-10 | 1998-11-04 | Nds Ltd | Determining visually noticeable differences between two images |
| US6363117B1 (en) * | 1998-12-31 | 2002-03-26 | Sony Corporation | Video compression using fast block motion estimation |
| US6473534B1 (en) * | 1999-01-06 | 2002-10-29 | Hewlett-Packard Company | Multiplier-free implementation of DCT used in image and video processing and compression |
| US6496795B1 (en) * | 1999-05-05 | 2002-12-17 | Microsoft Corporation | Modulated complex lapped transform for integrated signal enhancement and coding |
| US6487574B1 (en) * | 1999-02-26 | 2002-11-26 | Microsoft Corp. | System and method for producing modulated complex lapped transforms |
| US6370502B1 (en) * | 1999-05-27 | 2002-04-09 | America Online, Inc. | Method and system for reduction of quantization-induced block-discontinuities and general purpose audio codec |
| US6507614B1 (en) * | 1999-10-19 | 2003-01-14 | Sony Corporation | Efficient de-quantization in a digital video decoding process using a dynamic quantization matrix for parallel computations |
| JP3593944B2 (ja) * | 2000-03-08 | 2004-11-24 | 日本電気株式会社 | 画像データ処理装置及びそれに用いる動き補償処理方法 |
| US8374237B2 (en) | 2001-03-02 | 2013-02-12 | Dolby Laboratories Licensing Corporation | High precision encoding and decoding of video images |
| US20030112873A1 (en) | 2001-07-11 | 2003-06-19 | Demos Gary A. | Motion estimation for video compression systems |
| US7123655B2 (en) * | 2001-08-09 | 2006-10-17 | Sharp Laboratories Of America, Inc. | Method for reduced bit-depth quantization |
| US6882685B2 (en) * | 2001-09-18 | 2005-04-19 | Microsoft Corporation | Block transform and quantization for image and video coding |
| JP2003348598A (ja) | 2002-04-12 | 2003-12-05 | Seiko Epson Corp | メモリ効率のいい圧縮領域ビデオ処理のための且つ因数分解及び整数近似法を用いる高速逆動き補償のための方法並びに装置 |
| US7242713B2 (en) | 2002-05-02 | 2007-07-10 | Microsoft Corporation | 2-D transforms for image and video coding |
-
2003
- 2003-02-28 US US10/376,147 patent/US7242713B2/en active Active
- 2003-03-21 AT AT03006487T patent/ATE339744T1/de not_active IP Right Cessation
- 2003-03-21 EP EP03006487A patent/EP1359546B1/en not_active Expired - Lifetime
- 2003-03-21 DE DE60308255T patent/DE60308255T2/de not_active Expired - Lifetime
- 2003-04-25 JP JP2003122704A patent/JP4425561B2/ja not_active Expired - Lifetime
- 2003-04-30 CN CNB031241662A patent/CN100379292C/zh not_active Expired - Lifetime
- 2003-05-01 KR KR1020030028005A patent/KR100965704B1/ko active IP Right Grant
-
2004
- 2004-05-03 HK HK04103090A patent/HK1060205A1/xx not_active IP Right Cessation
Also Published As
| Publication number | Publication date |
|---|---|
| DE60308255T2 (de) | 2006-12-28 |
| US7242713B2 (en) | 2007-07-10 |
| KR100965704B1 (ko) | 2010-06-24 |
| US20030206582A1 (en) | 2003-11-06 |
| JP2003333598A (ja) | 2003-11-21 |
| DE60308255D1 (de) | 2006-10-26 |
| CN100379292C (zh) | 2008-04-02 |
| HK1060205A1 (en) | 2004-07-30 |
| EP1359546B1 (en) | 2006-09-13 |
| EP1359546A1 (en) | 2003-11-05 |
| CN1455599A (zh) | 2003-11-12 |
| ATE339744T1 (de) | 2006-10-15 |
| KR20030086423A (ko) | 2003-11-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4425561B2 (ja) | イメージおよびビデオ符号化のための２−ｄ変換 | |
| JP4874642B2 (ja) | ロッシーおよびロスレス２ｄデータ圧縮のための可逆な変換 | |
| JP3792789B2 (ja) | 符号化装置 | |
| KR101013344B1 (ko) | 이산 코사인 변환의 계산 중의 에러 감소 | |
| JP3693988B2 (ja) | 通信管理システム及び通信管理方法 | |
| US8724916B2 (en) | Reducing DC leakage in HD photo transform | |
| KR101507183B1 (ko) | 변환-기반 디지털 미디어 코덱에서의 계산 복잡도 및 정밀도 제어 | |
| JP4425824B2 (ja) | 動画像コーデック変換の高速実装 | |
| JP2002531973A (ja) | 画像の圧縮及び伸張 | |
| US7379500B2 (en) | Low-complexity 2-power transform for image/video compression | |
| KR20040005962A (ko) | 버터플라이 프로세서를 이용하여 이산 코사인 변환을인코딩하고 계산하는 장치 및 방법 | |
| JP2004516760A (ja) | スケーラブルな計算複雑性のビデオ画像及び静止画像復号化のための近似逆離散コサイン変換 | |
| CN1258169A (zh) | 流水线离散余弦变换设备 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20060323 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20090203 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20090507 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20090529 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20090929 |
|
| RD13 | Notification of appointment of power of sub attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7433 Effective date: 20090930 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A821 Effective date: 20090930 |
|
| A911 | Transfer to examiner for re-examination before appeal (zenchi) |
Free format text: JAPANESE INTERMEDIATE CODE: A911 Effective date: 20091030 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20091113 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20091209 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 4425561 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121218 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131218 Year of fee payment: 4 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |