(57)【要約】  ブロック変換ベースのデジタルメディアコーデックは、デジタルメディアデータの成分を、変換の多くの演算が並列または単一命令複数データ（ＳＩＭＤ）ベースで実行されうるベクトルまたは並列ユニットに再マップすることにより、さらに高速のパフォーマンスを達成する。１次元重複双直交変換の場合、デジタルメディアデータ成分は、重複変換のオーバーラッププレ／ポストフィルタおよびブロック変換部分のバタフライ段階がＳＩＭＤベースで実行されうるベクトルに再マップされる。２次元重複双直交変換の場合、デジタルメディアデータ成分は、オーバーラッププレ／ポストフィルタおよびブロック変換のアダマール演算子がＳＩＭＤベースで実行されうるベクトルに再マップされる。
2009505497.tif 000002
【特許請求の範囲】
【請求項１】
デジタルメディアデータを符号化する方法であって、
入力デジタルメディアデータ（１０１０）のブロックの成分を、変換の演算（７２０、７３０、７４０、７５０、７６０、１４１０、１４２０、１４３０、１４４０）が単一命令複数データベースでブロックの前記成分にわたって適用されうるベクトル（１０２０、８００）のセットに再マップするステップ（７１０、１０００、１００１）と、
前記デジタルディアデータのブロックに変換を適用して（３５０）各々のブロックの変換係数のセット（３６０、３６２）を生成するステップであって、前記変換を適用するステップはブロックの成分の前記ベクトルに単一命令複数データベースで少なくとも１つの演算を実行するステップを含むステップと、
圧縮されたビットストリームの前記変換係数を符号化（３８０）するステップとを含むことを特徴とする方法。
【請求項２】
前記変換はオーバーラップフィルタおよびブロック変換を備える重複双直交変換であり、前記ブロック変換は前記入力デジタルメディアデータのブロックに適用され、前記オーバーラップフィルタは隣接するブロックと重複するオーバーラップ領域に適用され、
前記再マップはコンポーネントを、前記オーバーラップフィルタの少なくとも１つの演算および前記ブロック変換の少なくとも１つの演算が単一命令複数データベースで前記成分にわたって適用されうるベクトルにグループ化し、
前記変換を適用する前記ステップは、前記オーバーラップフィルタの前記少なくとも１つの演算および前記ブロック変換の前記少なくとも１つの演算を単一命令複数データベースで前記ベクトルに適用するステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記オーバーラップフィルタの前記少なくとも１つの演算および前記ブロック変換の前記少なくとも１つの演算は各々２×２アダマール変換を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記オーバーラップフィルタおよび前記ブロック変換は各々順次命令ベースで前記コンポーネントに適用される回転演算を含むことを特徴とする請求項２に記載の方法。
【請求項５】
前記ベクトルは４成分ベクトルであることを特徴とする請求項２に記載の方法。
【請求項６】
前記変換はオーバーラップフィルタおよびブロック変換を備える１次元重複変換であり、前記ブロック変換は前記入力デジタルメディアデータのブロックに適用され、前記オーバーラップフィルタは隣接するブロックと重複するオーバーラップ領域に適用され、
前記再マップはコンポーネントを、前記オーバーラップフィルタの少なくとも１つの演算および前記ブロック変換の少なくとも１つの演算が単一命令複数データベースで前記成分にわたって適用されうるベクトルにグループ化し、
前記変換を適用する前記ステップは、前記オーバーラップフィルタの前記少なくとも１つの演算および前記ブロック変換の前記少なくとも１つの演算を単一命令複数データベースで前記ベクトルに適用するステップを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記オーバーラップフィルタの前記少なくとも１つの演算および前記ブロック変換の前記少なくとも１つの演算は各々バタフライ段階を含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記オーバーラップフィルタおよび前記ブロック変換は各々順次命令ベースで前記コンポーネントに適用される回転演算を含むことを特徴とする請求項６に記載の方法。
【請求項９】
前記ベクトルは２成分ベクトルであることを特徴とする請求項６に記載の方法。
【請求項１０】
前記デジタルメディアデータは２次元データであり、前記変換は１次元変換であり、前記方法は、
前記再マップするステップおよび前記変換を前記２次元メディアデータの行に適用するステップを実行するステップと、
前記再マップするステップおよび前記変換を前記２次元メディアデータの列に適用するステップを実行するステップとをさらに含むことを特徴とする請求項６に記載の方法。
【請求項１１】
請求項１に記載の方法により符号化されたデジタルメディアデータを復号化する方法であって、
前記圧縮されたビットストリームから前記変換係数を復号化するステップと、
前記復号化された変換係数を、前記変換の逆の演算が単一命令複数データベースで前記変換係数にわたって適用されうるベクトルの配置に配列するステップと、
前記復号化された変換係数のブロックに前記変換の前記逆を適用してブロックの前記デジタルメディアデータの表現を復元するステップであって、前記変換を適用するステップは単一命令複数データベースで変換係数の前記ベクトルに少なくとも１つの演算を実行するステップを含むステップと、
前記ベクトルの成分を前記デジタルメディアデータの初期配列に再マップするステップとをさらに含むことを特徴とする方法。
【請求項１２】
請求項１に記載の方法により符号化された前記圧縮ビットストリームを搬送することを特徴とする少なくとも１つのコンピュータ可読記録媒体。
【請求項１３】
符号化および／または復号化されるデジタルメディアデータ（３１０、３２０）を格納するデータ記憶バッファと、
デジタルメディアデータのブロック（１０１０）の要素を、変換の少なくとも一部の演算（７２０、７３０、７４０、７５０、７６０、１４１０、１４２０、１４３０、１４４０）が単一命令複数データベースでブロックの前記成分にわたって適用されうるベクトルのセット（８００、１０２０）に／から配列することと、
前記単一命令複数データベースで前記ブロックの前記ベクトルに前記少なくとも１つの演算を実行することを備える、前記デジタルメディアデータの前記ブロックに前記変換を適用する（３５０）ことと、
圧縮されたビットストリームに／から前記デジタルメディアデータを符号化（３８０）／復号化（４２０）することを行うようにプログラムされたプロセッサ（１７１０）とを備えることを特徴とするデジタルメディア符号器および／または復号器。
【請求項１４】
前記変換は前記デジタルメディアデータの隣接するブロックに適用されるブロック変換と前記隣接するブロックにまたがるオーバーラップ領域に適用されるオーバーラップフィルタとを有する重複双直交変換であり、前記プロセッサは前記ブロックの前記要素を、前記オーバーラップフィルタおよび前記変換の両方の少なくとも一部の演算が前記単一命令複数データベースで適用されうるベクトルに配列することを特徴とする請求項１３に記載のデジタルメディア符号器および／または復号器。
【請求項１５】
前記重複双直交変換は１次元であり、前記オーバーラップフィルタおよび前記ブロック変換は各々演算が前記単一命令複数データベースで前記ベクトルに適用されるバタフライ段階を備えることを特徴とする請求項１４に記載のデジタルメディア符号器および／または復号器。
【請求項１６】
前記重複双直交変換は２次元であり、前記オーバーラップフィルタおよび前記ブロック変換は各々演算が前記単一命令複数データベースで前記ベクトルに適用される２×２アダマール変換を備えることを特徴とする請求項１４に記載のデジタルメディア符号器および／または復号器。
【請求項１７】
前記プロセッサは、カラーフォーマット間の前記デジタルメディアデータの色変換の段階中に要素の前記配列を実行するようにさらにプログラムされることを特徴とする請求項１４に記載のデジタルメディア符号器および／または復号器。
【請求項１８】
デジタルメディアデータを処理する方法を実行するためにコンピュータ実行可能デジタルメディア処理プログラムを搭載する少なくとも１つのコンピュータ可読記録媒体であって、前記方法は、
デジタルメディアデータ（１０１０）のブロックの成分を、変換の演算（７２０、７３０、７４０、７５０、７６０、１４１０、１４２０、１４３０、１４４０）が単一命令複数データベースでブロックの前記成分にわたって適用されうるベクトル（１０２０、８００）のセットに再マップするステップ（７１０、１０００、１００１）と、
前記デジタルディアデータのブロックに変換を適用して（３５０）各々のブロックの変換係数のセット（３６０、３６２）を生成するステップであって、前記変換を適用するステップはブロックの成分の前記ベクトルに単一命令複数データベースで少なくとも一部の演算を実行するステップを含むステップと、
圧縮されたビットストリームに／から前記デジタルメディアデータを符号化（３８０）／復号化（４２０）するステップとを含むことを特徴とするコンピュータ可読記録媒体。
【請求項１９】
前記変換はオーバーラップフィルタおよびブロック変換を備える重複双直交変換であり、前記変換を適用するステップは前記オーバーラップフィルタおよびブロック変換の両方の少なくとも一部の演算を単一命令複数データベースで前記ベクトルに実行するステップを含むことを特徴とする請求項１８に記載の少なくとも１つのコンピュータ可読記録媒体。
【請求項２０】
前記変換を適用する前記ステップは、前記オーバーラップフィルタおよびブロック変換の両方の少なくとも一部の回転演算を順次ベースで実行するステップを含むことを特徴とする請求項１９に記載の少なくとも１つのコンピュータ可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
ＳＩＭＤ型重複変換ベースのデジタルメディア符号化／復号化に関する。
【背景技術】
【０００２】
著作権許可
本特許文献の開示の一部は、著作権の保護を受ける資料を含む。著作権の保有者は、本特許文献または特許開示が特許商標庁の特許ファイルまたは記録に表示されているため、本特許文献または特許開示の転載に異議はないが、すべての著作権を留保する。
【０００３】
ブロック変換ベースの符号化
変換符号化は、多くの音声、画像、およびビデオ圧縮システムに使用される圧縮技法である。圧縮されていないデジタル画像およびビデオは通常、２次元（２Ｄ）グリッドに配列された画像またはビデオフレーム内の位置で画素または色のサンプルとして表されるか、または取り込まれる。このサンプルは、画像またはビデオの空間領域表現と呼ばれる。たとえば、画像の標準的なフォーマットは、グリッドとして配列された２４ビットカラー画素サンプルのストリームで構成される。各サンプルは、特にＲＧＢ、またはＹＩＱなどの、色空間内のグリッドの画素位置で色成分を表す数値である。さまざまな画像およびビデオシステムは、サンプリングのさまざまな色、空間および時間分解能を使用することができる。同様に、デジタル音声は通常、時間サンプリングされた音声信号ストリームとして表される。たとえば、標準的な音声フォーマットは、一定時間ごとに採取される音声信号の１６ビット振幅サンプルのストリームで構成される。
【０００４】
圧縮されていないデジタル音声、画像、およびビデオ信号は、多大な記憶容量と伝送能力を消費する可能性がある。変換符号化は、信号の空間領域表現を周波数領域（またはその他の同様の変換領域）表現に変換して、変換領域表現の特定の概して知覚されにくい周波数成分の解像度を低減することにより、デジタル音声、画像、およびビデオのサイズを縮小する。このようにすることで一般に、空間領域の画像またはビデオ、または時間領域の音声の色または空間解像度を低減することに比べて、デジタル信号の劣化がはるかに知覚されにくくなる。
【０００５】
具体的には、図１に示される通常のブロック変換ベースのコーデック１００は、圧縮されていないデジタル画像の画素を固定サイズの２次元ブロック（Ｘ１、．．．Ｘｎ）に分割し、各ブロックが場合によっては他のブロックと重なり合うようにする。空間周波数分析を行う１次変換（linear transformation）１２０〜１２１が各ブロックに適用され、それによりブロック内の間隔をあけたサンプルを、ブロック間隔にわたり対応する周波数帯域のデジタル信号の強度を一般に表す周波数（または変換）係数のセットに変換する。圧縮の場合、変換係数は、選択的に量子化１３０され（つまり、係数値の最下位ビットをドロップするか、またはより高い解像度数値セットの値をより低い解像度にマップすることなどにより、解像度が低減される）、さらに、圧縮されたデータストリームにエントロピーまたは可変長符号化１３０されうる。復号化において、変換係数は、逆変換して１７０〜１７１、元の色／空間サンプリングされた画像／ビデオ信号をほぼ復元する（復元されたブロック
【０００６】
【数１】
2009505497.tif 000003
【０００７】
）。
【０００８】
ブロック変換１２０〜１２１は、サイズＮのベクトルｘへの数値演算として定義することができる。ほとんどの場合、演算は１次乗算であり、Ｍを変換行列として、変換領域出力ｙ＝Ｍｘを生成する。入力データが任意に長い場合、入力データはＮの大きさのベクトルに分割され、ブロック変換は各セグメントに適用される。データ圧縮の目的で、可逆ブロック変換が選択される。つまり、行列Ｍは、反転することができる。（たとえば、画像およびビデオなどの）多次元において、ブロック変換は通常、分離可能な演算として実施される。行列乗算は、データの各次元（つまり、行および列の両方）に沿って別個に適用される。
【０００９】
圧縮の場合、変換係数（ベクトルｙの成分）は、選択的に量子化され（つまり、係数値の最下位ビットをドロップするか、またはより高い解像度数値セットの値をより低い解像度にマップすることなどにより、解像度が低減される）、さらに圧縮されたデータストリームにエントロピーまたは可変長符号化されうる。
【００１０】
復号器１５０における復号化において、これらの演算の逆（逆量子化／エントロピー復号化１６０および逆ブロック変換１７０〜１７１）が、図１に示されるように復号器１５０側に適用される。データを復元する間、逆行列Ｍ−１（逆変換１７０〜１７１）は、変換領域データへの乗算として適用される。変換領域データに適用される場合、逆変換は、元の時間領域または空間領域のデジタルメディアをほぼ復元する。
【００１１】
多くのブロック変換ベースの符号化適用において、変換は、量子化因子に応じて不可逆圧縮（lossy compression）および可逆圧縮（lossless compression）を共にサポートするように反転できることが望ましい。たとえば量子化が行われない（一般に１の量子化因子として表される）場合、可逆的な変換を使用するコーデックは、復号化において入力データを正確に復元することができる。しかし、これらの適用における可逆性の要件は、コーデックが設計されうる変換の選択を制約する。
【００１２】
特に、ＭＰＥＧおよびＷｉｎｄｏｗｓ（登録商標）Ｍｅｄｉａのような、多くの画像およびビデオ圧縮システムは、離散コサイン変換（ＤＣＴ）に基づく変換を使用する。ＤＣＴは、ほぼ最適なデータ圧縮をもたらす好ましいエネルギー圧縮特性を備えることが知られている。これらの圧縮システムにおいて、逆ＤＣＴ（ＩＤＣＴ）は、個々の画像ブロックを復元するための圧縮システムの符号器および復号器の両方で復元ループに採用される。
【００１３】
【特許文献１】米国特許出願第１１／０１５，７０７号明細書（2004年12月17に出願したSrinivasanによる「Reversible Transform For Lossy And Lossless 2-D Data Compression」）
【特許文献２】米国特許出願第１１／０１５，１４８号明細書（2004年12月17に出願したTuらによる「Reversible Overlap Operator for Efficient Lossless Data Compression」）
【特許文献３】米国特許出願第１１／０３５，９９１号明細書（2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」）
【発明の開示】
【発明が解決しようとする課題】
【００１４】
重複変換（Lapped Transforms）
前述のブロック変換ベースの符号化システムにおいて、ブロック変換は、入力信号または画像の重複しない隣接ブロックに引き続いて適用される有限長（通常、４または８の短い長さ）の変換である。したがって、ブロック境界をまたぐ信号成分は、境界にわたりブロックの変換に影響を及ぼすことはない。データの圧縮に対する高周波数成分の量子化により、ブロック変換を使用すると、ブロック境界において知覚されるアーティファクト、つまりブロックノイズを生じる可能性もある。ブロックノイズは、圧縮比の高いＪＰＥＧ画像で顕著となり、画像にモザイク形状または階段形状として出現する。音声において、ブロックノイズは、周期的にはじけるようなノイズを生じる。これらはいずれも、許容できるアーティファクトではない。
【００１５】
重複変換（図２に示されるＬＴ２１０）は、著しいブロックノイズの影響を受けない信号または画像を表現する代替の手段である。重複変換において、各々の変換係数セットに影響を及ぼす入力信号成分は、変換出力ブロックのサイズよりも大きい。たとえば１Ｄの場合、８つの連続する信号成分は、４ポイント変換に影響を及ぼしうる。画像の場合も同様に、８×８領域は、４×４変換ブロックに影響を及ぼしうる。
【００１６】
重複変換は、２つの方法のうちの１つで定式化することができる。重複変換の１つの従来的な定式化は、後に一連の周波数混合が続く一連のブロック変換である。ブロック変換はＮポイントの規則的なグリッドに整列されるが（Ｎは変換サイズ）、周波数混合器はブロック境界にわたって対称的に間隔をあけて配置される。代替の定式化は、後にブロック変換が続く、ブロック端部にわたって行われるプレフィルタ処理演算を備える。
【００１７】
重複変換の逆（たとえば、図２のＩＬＴ２２０）は一般に、計算および実施が容易である。信号フローのグラフは、各基本演算が逆転されている状態で反転される。逆重複変換の１つの従来的な定式化は、後に一連のブロック変換が続く一連の周波数混合である。代替の定式化は、ブロック境界にわたって適用されるポストフィルタ処理演算が後に続く、一連のブロック変換を備える。
【００１８】
重複変換のいずれの定式化においても、主要な要素は、（ｉ）ブロック変換、および（ｉｉ）周波数混合器、プレまたはポストフィルタ処理であってもよい、ブロックをまたぐ演算子である。これらの演算子（ｉｉ）は、まとめてオーバーラップフィルタと呼ばれる。
【００１９】
重複直交変換（ＬＯＴ）は、重複変換のサブクラスである。重複直交変換は、順方向および逆方向変換が転置される特性を有する。圧縮の観点からは、サブクラスの重複双直交変換がさらに興味深いが、これはＬＯＴよりも優れたＰＳＮＲを達成することができるからである。双直交とは、分析および合成の基底関数が双直交（つまり相互に直交）であるということを示す。
【課題を解決するための手段】
【００２０】
本明細書に説明されるデジタルメディアコーデックにおけるデジタルメディア符号化および復号化技法とその技法の具現化は、符号化および復号化に使用される変換の高速化を達成する。この技法は、重複（またはその他の）変換を、概ね単一命令複数データ（ＳＩＭＤ）が扱いやすい演算のセットとして再定式化（reformulate）する。この再定式化は、重複変換の入力および出力サンプリンググリッドを再マップすることにより達成される。この再マップにより、入力データは、「ベクトル」または並列ユニットにグループ化することができる。この再配列により、重複変換ステップの多くが、ベクトル演算として実行されうる。ベクトル化可能ではない残りのわずかな演算は、連続的にベクトル成分に対して実行される。
【００２１】
この要約は、詳細な説明において以下でさらに説明される一連の概念を、簡略化した形式で示すために提供されている。この要約は、請求項に係る主題の重要な特徴または基本的な特徴を特定することを意図するものではなく、また請求項に係る主題の範囲を規定する際の補助として使用されることを意図するものでもない。
【発明を実施するための最良の形態】
【００２２】
以下の説明は、並列化またはＳＩＭＤ演算として重複変換のより高速な実施をもたらす符号化および復号化技法［これ以降「変換並列化技法」と称する］に関する。以下の説明では、デジタルメディア圧縮システムまたはコーデックのコンテキストにおいてこの技法の実施例を説明する。デジタルメディアシステムは、伝送または格納のために圧縮形式でデジタルメディアデータを符号化し、再生またはその他の処理のためにデータを復号化する。説明のために、この変換並列化技法を組み入れるこの模範的な圧縮システムは、画像またはビデオ圧縮システムである。代替として、この技法はさらに、その他の２Ｄデータの圧縮システムまたはコーデックに組み入れることもできる。変換並列化技法は、デジタルメディア圧縮システムが特定の符号化フォーマットで圧縮済みデジタルメディアデータを符号化することは要求しない。
【００２３】
１．  符号器／復号器
図３および図４は、代表的な２次元（２Ｄ）データ符号器３００および復号器４００に採用されるプロセスを一般化した図である。図は、変換並列化技法を実施する２Ｄデータ符号器および復号器を組み入れる圧縮システムの一般化または簡略化された説明を提示する。変換並列化技法を使用する代替の圧縮システムにおいて、この代表的な符号器および復号器に示されているプロセスよりも多いかまたは少ないプロセスが２Ｄデータ圧縮に使用されてもよい。たとえば、一部の符号器／復号器はさらに、色変換、カラーフォーマット、拡張可能符号化、可逆符号化、マクロブロックモードなどを含むこともできる。圧縮システム（符号器および復号器）は、可逆から不可逆へと変化する量子化パラメータに基づくことができる量子化に応じて、２Ｄデータの可逆圧縮および／または不可逆圧縮を行うことができる。
【００２４】
２Ｄデータ符号器３００は、符号器への入力として示される２Ｄデータ３１０のよりコンパクトな表現（標準的な入力の場合）である圧縮済みビットストリーム３２０を生成する。たとえば、２Ｄデータ入力は、画像、ビデオシーケンスのフレーム、または２次元を有するその他のデータであってもよい。２Ｄデータ符号器は、入力データをマクロブロックにタイル化３３０するが、マクロブロックはこの代表的な符号器において１６×１６画素のサイズである。２Ｄデータ符号器はさらに、各マクロブロックを４×４ブロックにタイル化する。「順方向オーバーラップ」演算子３４０は、ブロック間の各端部に適用され、その後各４×４ブロックがブロック変換３５０を使用して変換される。このブロック変換３５０は、可逆的なスケールフリーの２Ｄ変換であってもよい（たとえば、本願に引用して援用する、2004年12月17に出願したSrinivasanによる「Reversible Transform For Lossy And Lossless 2-D Data Compressionという名称の特許文献１を参照）。オーバーラップ演算子３４０は、可逆的なオーバーラップ演算子であってもよい（たとえば、本願に引用して援用する、2004年12月17に出願したTuらによる「Reversible Overlap Operator for Efficient Lossless Data Compression」という名称の特許文献２参照、および本願に引用して援用する、2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」という名称の特許文献３を参照）。オーバーラップ演算子および変換は共に、重複双直交変換をもたらす。代替として、離散コサイン変換またはその他のブロック変換およびオーバーラップ演算子が使用されうる。変換に続いて、各４×４変換ブロックのＤＣ係数３６０は、類似の処理チェーン（後に４×４ブロック変換が続く、タイル化、順方向オーバーラップ）に従う。結果として生じるＤＣ変換係数およびＡＣ変換係数は、量子化され３７０、エントロピー符号化され３８０、パケット化される３９０。
【００２５】
復号器は逆のプロセスを実行する。復号器側では、変換係数ビットはそれらのそれぞれのパケットから抽出され４１０、そこから係数自身が復号化され４２０、逆量子化される４３０。ＤＣ係数４４０は、逆変換を適用することにより再生成され、ＤＣ係数の面は、ＤＣブロック端部にわたって適用される適切な平滑化演算子を使用して「逆オーバーラップ」される。続いて、ＤＣ係数、およびビットストリームから復号化されたＡＣ係数４４２に４×４逆変換４５０を適用することにより全データが再生成される。最後に、得られた画像面のブロック端部は、逆オーバーラップフィルタ処理される４６０。こうして、復元された２Ｄデータ出力を生成する。
【００２６】
模範的な実施態様において、符号器３００（図３）は、入力画像を圧縮されたビットストリーム３２０（たとえばファイル）に圧縮し、復号器４００（図４）は、可逆または不可逆符号化が採用されるかどうかに基づいて、元の入力またはその近似を復元する。符号化のプロセスは、以下で説明される順方向重複変換（ＬＴ）の適用を伴うが、ＬＴは以下でさらに詳細に説明される可逆２次元プレ／ポストフィルタ処理で実施される。復号化のプロセスは、可逆２次元プレ／ポストフィルタ処理を使用する逆方向重複変換（ＩＬＴ）の適用を伴う。
【００２７】
説明されるＬＴおよびＩＬＴは、正確な意味で相互の逆であるので、まとめて可逆重複変換と呼ぶことができる。可逆変換として、ＬＴ／ＩＬＴのペアは、可逆画像圧縮に使用することができる。
【００２８】
示される符号器３００／復号器４００によって圧縮された入力データ３１０は、さまざまなカラーフォーマットの画像であってもよい（たとえば、ＲＧＢ／ＹＵＶ４：４：４、ＹＵＶ４：２：２、またはＹＵＶ４：２：０のカラー画像フォーマット）。通常、入力画像は常に輝度（Ｙ）成分を有する。入力画像が、ＲＧＢ／ＹＵＶ４：４：４、ＹＵＶ４：２：２、またはＹＵＶ４：２：０の画像である場合、画像はさらに、Ｕ成分およびＶ成分などのクロミナンス成分も有する。画像の別個の色平面または成分は、さまざまな空間解像度を備えることができる。たとえば、ＹＵＶ４：２：０のカラーフォーマットの入力画像の場合、ＵおよびＶ成分は、Ｙ成分の半分の幅および高さを有する。
【００２９】
前述のように、符号器３００は、入力画像またはピクチャをマクロブロックにタイル化する。模範的な実施態様において、符号器３００は入力画像をＹチャネルの１６×１６マクロブロックにタイル化する（カラーフォーマットに応じて、ＵおよびＶチャネルで１６×１６、１６×８、または８×８の領域となる）。各マクロブロック色平面は、４×４の領域またはブロックにタイル化される。したがって、マクロブロックは、この模範的な符号化実施態様について以下の方法でさまざまなカラーフォーマットに構成される。  
１．  グレースケール画像の場合、各マクロブロックは１６の４×４輝度（Ｙ）ブロックを含む。  
２．  ＹＵＶ４：２：０フォーマットのカラー画像の場合、各マクロブロックは１６の４×４  Ｙブロック、および４つの各４×４のクロミナンス（ＵおよびＶ）ブロックを含む。  
３．  ＹＵＶ４：２：２フォーマットのカラー画像の場合、各マクロブロックは１６の４×４  Ｙブロック、および８つの各４×４のクロミナンス（ＵおよびＶ）ブロックを含む。  
４．  ＲＧＢまたはＹＵＶ４：４：４のカラー画像の場合、各マクロブロックは各々Ｙ、Ｕ、およびＶチャネルの１６のブロックを含む。
【００３０】
２．  高速ＳＩＭＤ重複双直交変換の概要
前述の代表的な符号器３００（図３）および復号器４００（図４）におけるさらに計算処理上複雑な演算の１つは、重複双直交変換である。この演算の複雑さは、符号器および復号器のパフォーマンスに影響を与える。
【００３１】
特許出願（たとえば、2004年12月17に出願したSrinivasanによる「Reversible Transform For Lossy And Lossless 2-D Data Compression」という名称の特許文献１、2004年12月17に出願したTuらによる「Reversible Overlap Operator for Efficient Lossless Data Compression」という名称の特許文献２、および2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」という名称の特許文献３を参照）に説明されている重複双直交変換の実施態様は、複雑さを最小化するように設計されている。しかし、本明細書において説明される変換並列化技法は、ＳＩＭＤ（単一命令複数データ）または並列命令に扱いやすい方法で重複変換演算を定式化することにより、さらなる高速化を達成する。ＳＩＭＤ演算は、並行して複数の命令を計算するために使用されうる。そのようなＳＩＭＤ命令は、Ｉｎｔｅｌ製のＰｅｎｔｉｕｍ（登録商標）ファミリーのプロセッサ、ＡＭＤ製のさまざまなｘ８６互換プロセッサ、ＰｏｗｅｒＰＣ（登録商標）および各種のその他のＤＳＰ（デジタルシグナルプロセッサ）を含む、さまざまなプロセッサでサポートされる。
【００３２】
本明細書において説明される変換並列化技法は、重複（またはその他の）変換を、概ねＳＩＭＤが扱いやすい演算のセットとして再定式化する。この再定式化は、重複変換の入力および出力サンプリンググリッドを再マップすることにより達成される。この再マッピングにより、入力データは、「ベクトル」または並列ユニットにグループ化することができる。この再配列により、重複変換ステップの多くが、ベクトル演算として実行されうる。ベクトル化可能ではない残りのわずかな演算は、順次ベクトル成分に対して実行される。
【００３３】
技法は概して、重複変換に適用することができるが、代表的な符号器および復号器の重複双直交変換への技法の特定の適用（つまり、上記で列挙した特許出願に詳述される重複双直交変換）について、例示のために以下で説明される。変換並列化技法は、データサンプルの各グループが、重複変換を実施する演算の多くに対するベクトルとして処理されるように、代表的な重複双直交変換の入力サンプリンググリッドまたは格子を再マップおよびグループ化する。この特定の重複双直交変換の例において、技法は、ＳＩＭＤが扱いやすいバージョンの４ポイントオーバーラップ演算および４ポイントブロック変換を定式化するように適用されるが、技法はその他の変換長にも一般化することができる。さらに、技法は代替として、その他の重複変換具現化のＳＩＭＤまたは並列命令バージョンを作成するために適用されてもよい。
【００３４】
以下のセクションでは、代表的な重複双直交変換の１次元および２次元のＳＩＭＤが扱いやすい実施態様を詳しく説明する。１次元の場合、２つの要素は共に１つのベクトルにグループ化され、１Ｄ重複変換演算の多くはベクトル演算を使用して行われうる。２次元の場合、２つまたは４つの要素は共に１つのベクトルにグループ化され、重複変換演算の多くはベクトル演算を使用して行われうる。
【００３５】
これらのベクトル化技法は、（それぞれ符号器および復号器によって使用される）順方向および逆方向変換に同等に適用可能である。
【００３６】
２．１  １次元重複双直交変換のＳＩＭＤ具現化
図５を参照して、プレフィルタ（オーバーラップ演算子）５１０およびブロック変換５２０として定式化される重複変換５００の一般的な事例を考察する。説明される事例において、ブロック変換５２０は４のブロックサイズを有し、プレフィルタ５１０も４のオーバーラップサイズを有する。オーバーラップサイズは、プレ／ポストフィルタ長として定義される。したがって、データシーケンスが、ｘ０、ｘ１、ｘ２、ｘ３、というように番号付けされる場合、重複変換５００は以下のように進む。
【００３７】
１．  プレフィルタ５１０は、入力データ［ｘ４ｉ＋２、ｘ４ｉ＋３、ｘ４ｉ＋４、ｘ４ｉ＋５］の各セットに適用される。
【００３８】
２．  ブロック変換５２０は、各セット［ｘ４ｉ、ｘ４ｉ＋１、ｘ４ｉ＋２、ｘ４ｉ＋３］に適用される。代替実施態様において、重複変換は、その他の異なるブロック変換サイズおよびオーバーラップサイズで定義されてもよい。
【００３９】
図６は、図５に示されるプレフィルタおよびブロック変換定式化を有する重複双直交変換６００のさらに具体的な例を示す。重複双直交変換６００は、代表的な符号器３００（図３）および復号器４００（図４）に使用されることが上記で説明されている変換であり、その実施態様については特許出願（たとえば、2004年12月17に出願したSrinivasanによる「Reversible Transform For Lossy And Lossless 2-D Data Compression」という名称の特許文献１、2004年12月17に出願したTuらによる「Reversible Overlap Operator for Efficient Lossless Data Compression」という名称の特許文献２、および2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」という名称の特許文献３を参照）においてさらに具体的に詳述される。簡単にするため、符号器３００のプレフィルタおよびブロック変換は図６に示されている。復号器の逆重複変換のポストフィルタおよび逆ブロック変換は、順方向重複変換６００の逆である。図６に示されるように、プレフィルタは、第１のバタフライ段階６１０、回転／スケーリング６２０、および第２のバタフライ段階６３０として編成される一連のバタフライまたはリフティングステップ演算としての実施態様を備える。ブロック変換は、第３のバタフライ段階６４０および回転６５０としての実施態様を備える。
【００４０】
ＳＩＭＤ命令を使用する具現化のための演算を並列化する１つの方法は、類似する索引付けされた信号成分をブロックにわたって単にグループ化することによる。つまり、一部のｊに対するフォームｘ４ｉ＋ｊの成分は、グループにまとめられる。ここで考察される特定の重複双直交変換６００の例の場合、２つのコンポーネントのベクトルは、［ｘ１４  ｘ１８］、［ｘ１５  ｘ１９］、［ｘ１６  ｘ２０］、および［ｘ１７  ｘ２１］のようになる。
【００４１】
このグループ化は、プレフィルタでは良好に機能する。しかし、ブロック変換の場合、ベクトル［ｘ１４  ｘ１８］および［ｘ１６  ｘ２０］は、２つのブロックではなく、３つのブロックにまたがる。これはつまり、このグループ化は、重複変換の全体的な高速化を達成するために使用できないことを意味する。変換段階において、望ましいグルーピングは異なっており、［ｘ１６  ｘ２０］、［ｘ１７  ｘ２１］、［ｘ１８  ｘ２２］、および［ｘ１９  ｘ２３］である。
【００４２】
プレフィルタおよびブロック変換の望ましいグループ化を比較すると、ベクトルのうちの２つが両方のグループ化に共通であることが認められる（つまり、［ｘ１６  ｘ２０］および［ｘ１７  ｘ２１］。しかし、残りの２つのベクトルはグループ化間で異なっており、プレフィルタとブロック変換の間のベクトルの再グループ化が必要となる。これは、望ましい解決策ではない。
【００４３】
一方、変換並列化技法は、１Ｄ重複変換を並列化する代替の方法を提示する。代替の技法によれば、ＳＩＭＤ命令ベクトルへのコンポーネントのグループ化がプレフィルタとブロック変換の両段階に共通であるように、重複変換の前後に特定のコンポーネントの間に置換が加えられる。
【００４４】
図７は、本明細書に説明される変換並列化技法により並列化された、図６の重複双直交変換の修正された具現化７００を示す。この修正された重複変換具現化７００は、図６の重複双直交変換の実施態様６００と機能的には同一であるが、後にバタフライ７２０、７４０、および７５０のわずかに異なるネットワークが続く、第１段階の成分のねじれまたは置換７１０を含む。これらのバタフライ段階では、奇数の成分は奇数の成分とのみ相互作用し、偶数の成分は偶数の成分とのみ相互作用するので、これらの段階は２つの成分ベクトルと並行して実施することができる。さらに、奇数コンポーネントと偶数コンポーネントの演算は、これらの段階では同一である。したがって、隣接する奇数および偶数のコンポーネントのグループ化は、並列の実施態様を具現化する。
【００４５】
しかし、重複双直交変換のＳＩＭＤ具現化７００の段階の一部は、依然として並列化可能ではない。プレフィルタの回転／スケーリングステップ７３０、およびブロック変換の回転ステップ７６０は、連続して実施される。
【００４６】
図９は、図８に示されるデータの２成分ベクトルへの配列を使用する、重複双直交変換７００（図７）の具現化９００を示す。図９において、データパスは２成分ベクトル値であり、太字の矢印はベクトル内演算（つまり同じベクトルの成分間の演算）である。図８に示されるベクトルグループ化は入力に使用されるが、このグループ化は以下の成分−ベクトルマッピング規則に基づく。
【００４７】
Ｖ２ｉ＝［ｘ４ｉ  ｘ４ｉ＋１］
Ｖ２ｉ＋１＝［ｘ４ｉ＋３  ｘ４ｉ＋２］
【００４８】
このマッピングは元の信号を２成分ベクトルにグループ化し、多くの重複変換ステップの場合はＳＩＭＤ計算が適用され、残りのステップの場合は連続処理が適用される。
【００４９】
２．２  ２次元重複双直交変換のＳＩＭＤ具現化
２次元重複双直交変換（２Ｄ  ＬＢＴ）は、前述の１次元重複双直交変換（１Ｄ  ＬＢＴ）を使用して実施することができる。そのような実施態様において、１Ｄ  ＬＢＴは画像の各行に適用され、その後に各列に適用される１Ｄ  ＬＢＴが続く（または、その逆もある）。この場合、以下の２つのタイプのベクトル化技法を使用することができる。
【００５０】
１．  第１のタイプのベクトル化において、（上記の第２．１項で説明されている）１Ｄ  ＬＢＴに使用されたグループ化と同じグループ化が、水平および垂直変換の両方に使用されうる。
【００５１】
２．  第２のタイプのベクトル化において、ベクトルは、１Ｄ  ＬＢＴを行に沿って実施しながら、複数の行の類似した索引付け成分をグループ化することによって、また１Ｄ  ＬＢＴを列に沿って実施しながら、複数の列の類似した索引付け成分をグループ化することによって形成することができる。
【００５２】
これらのいずれの技法においても、ベクトル化は、行と列の変換の間で変化する。この変化は、変換の計算中にあるベクトル化フォーマットから別のベクトル化フォーマットに再マップする追加コストをまねき、それが高価になることもある。変換段階の間の入れ替えを伴うことのない代替のベクトル化技法について、以下で説明される。
【００５３】
さらに、上記に列挙されている特許出願（たとえば、2004年12月17に出願したSrinivasanによる「Reversible Transform For Lossy And Lossless 2-D Data Compression」という名称の特許文献１および2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」という名称の特許文献３を参照）で説明される２Ｄ  ＬＢＴは、２次元で直接ＬＢＴを実施する。この変換は、２つの１Ｄ演算に分割することはできない。
【００５４】
この直接２Ｄ  ＬＢＴ実施態様の並列化ＳＩＭＤバージョンの場合（および分離可能な２Ｄ実施態様の場合も）、双方向にねじれた再マップ１０００〜１００１は、図１０に示されるように最初に適用される。領域１０１０内の画素の各４×４ブロックは、各ベクトルが４×４ブロックの２×２サブブロックからの画素を含むように、領域１０２０内の４つの４成分ベクトルにマップされる１０００〜１００１。ベクトル内の成分の配列は、前述の１Ｄ再マップ（図７に示される置換７１０）の２次元拡張に従う。図１１は、結果として得られた領域１０２０の４成分ベクトルのセットのベクトル表記１１００を示す。
【００５５】
このように形成された４成分ベクトルは、直接２Ｄ  ＬＢＴのオーバーラップ演算子段階またはブロック変換段階のいずれかにおいてアダマール変換が適用される４画素のグループがベクトル内の同じ位置に整列される特性を有する。この特性は、オーバーラップ演算子の場合図１２、およびフォトコア変換（Ｐｈｏｔｏ  Ｃｏｒｅ  Ｔｒａｎｓｆｏｒｍ）の場合図１３に示され、以下で詳細に説明される。
【００５６】
２．２．１  ２次元重複双直交変換のＳＩＭＤ具現化におけるオーバーラップ演算子の並列実施態様
再び図５を参照すると、重複変換のオーバーラップ演算子（プレフィルタ５１０）は、ブロック境界にわたって適用される。この適用は、ブロック変換５２０の前または後のいずれに行われてもよい。
【００５７】
上記に列挙されている特許出願（たとえば、2004年12月17に出願したSrinivasanによる「Reversible Transform For Lossy And Lossless 2-D Data Compression」という名称の特許文献１および2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」という名称の特許文献３を参照）で説明される２Ｄ  ＬＢＴ実施態様の場合、オーバーラップ演算子は符号器側でブロック変換の前に適用される。同様に、オーバーラップ演算子は、復号化側で逆ブロック変換の後に適用される。画像の境界における特殊事例を無視すると、オーバーラップ演算子は、４つの４×４ブロックをまたぐ４×４領域に適用される。
【００５８】
図１４を参照すると、この２Ｄ  ＬＢＴ実施態様のオーバーラップ演算子１４００は、グリッド内に対称的に位置する４つの画素に適用される２つの２×２アダマール変換１４１０、後に続く回転およびスケーリング段階１４２０および１４３０、その後に続く同じ４つの画素に適用されるもう１つの２×２アダマール変換１４４０から構成される。演算子の詳細については提示されている（たとえば、2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」という名称の特許文献３を参照）。この特許出願に説明されているように、さらに簡略化を２Ｄ  ＬＢＴ定式化に使用することができ、ここでスケーリング段階と、２×２アダマール段階の１つは、一部の演算子を取り消す。
【００５９】
このオーバーラップ演算子の並列化ＳＩＭＤバージョンの場合、上記の第２．２項に説明され、図１０および図１１に示されている同じベクトル化手順が最初に適用される。図１５を参照すると、このベクトル化データに基づくオーバーラップ演算子の並列化ＳＩＭＤバージョンは、以下のプロセス１５００に従って実施される。
【００６０】
１．  アクション１５１０において示されるように、画像またはその他の２次元データ作業領域は、図１０および図１１に示されるように、４成分ベクトルにベクトル化される。
【００６１】
２．  アクション１５２０〜１５７０のオーバーラップ演算は、図１２に示されるように、画像上の４つの４×４ブロック１２００をまたぐ各４×４オーバーラップ領域に実行される。この演算の場合、ベクトルは図１１に示されるベクトル表示を使用して［ｖ３  ｖ６  ｖ９  ｖ１２］と識別される。これらのステップは、そのような領域すべてに対して繰り返される。
【００６２】
３．  最初に、アクション１５３０においてこれらの４つのベクトル間に２×２アダマール演算が実行される。
【００６３】
４．  次のアクション１５４０では、スケーリング演算（たとえば、2004年12月17に出願したTuらによる「Reversible Overlap Operator for Efficient Lossless Data Compression」という名称の特許文献２および2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」という名称の特許文献３を参照）がベクトルｖ３とｖ１２の間で実行される。
【００６４】
５．  回転１５５０は、ベクトルｖ６、ｖ９、およびｖ１２の成分内で実行される。これらは大部分が、概してデータの並列化を活用しない連続演算である。
【００６５】
６．  最後に、アクション１５６０において、オーバーラップ領域の４つのベクトル［ｖ３  ｖ６  ｖ９  ｖ１２］間に再び２×２アダマール演算が実行される。
【００６６】
プロセス１５００において、前述の演算は、指示されたベクトルの同所に実行される。さらに、実際には、特許出願（たとえば、2004年12月17に出願したTuらによる「Reversible Overlap Operator for Efficient Lossless Data Compression」という名称の特許文献２および2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」という名称の特許文献３を参照）に詳述されているように、さらなる簡略化を導く一部の取り消しがステップ３とステップ４の間にある。
【００６７】
２．２．２  ２次元重複双直交変換のＳＩＭＤ具現化におけるブロック変換の並列実施態様
オーバーラップ演算子がブロック内のすべての２×２サブブロックに適用された後、４×４ブロック１３００（図１３）はブロック変換される準備が整っている。ブロック変換演算は同じベクトル化を保持するので、オーバーラップとブロック変換演算の間でデータを入れ替える必要はない。
【００６８】
図１６を参照すると、以下のプロセス１６００に従ってブロック変換の並列実施態様が実行される。プロセスは、図１０および図１１に示されるようにオーバーラップ演算子のアクション１５１０（図１５）によって引き続きベクトル化される画像または作業領域から開始する。一方、オーバーラップ演算子プロセス１５００が最初に適用されることなくブロック変換が単独で２Ｄデータに適用される場合、代わりにプロセス１６００がアクション１５１０を実行することから開始して同じベクトル化をもたらす。
【００６９】
１．  アクション１６１０〜１６４０のループにおいて、変換は、画像の各４×４ブロック１３００に適用される。たとえば、図１３に示されるベクトル［ｖ０  ｖ１  ｖ２  ｖ３］は、左上ブロックに使用される。これらのステップは、すべてのブロックに対して繰り返される。
【００７０】
２．  最初アクション１６２０において、これらの４つのベクトル間に２×２アダマール演算が実行される。
【００７１】
３．  次のアクション１６３０において、回転は、ベクトルｖ０、ｖ１、ｖ２、およびｖ３の成分内で実行される。これらは大部分が、概してデータの並列化を活用しない連続演算である。実行される回転については、特許出願（たとえば、2004年12月17に出願したSrinivasanによる「Reversible Transform For Lossy And Lossless 2-D Data Compression」という名称の特許文献１および2005年1月14日に出願したTuらによる「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」という名称の特許文献３を参照）において詳述されるとおりである。
【００７２】
ＳＩＭＤ重複変換の代替実施態様において、ブロックのベクトルに適用される変換演算は、（上記で列挙されている特許出願に説明される可逆変換ではなく）その他のＤＣＴと類似した変換の演算であってもよい。
【００７３】
２．３  拡張
オーバーラップ演算子１５００および変換１６００のプロセスのいずれの場合も、４方向の２×２アダマール変換が基本の反復される演算である。データ成分が図１０および図１１に示されるベクトル化によって順序付けられているので、２×２アダマールはこれらのベクトルで機能するＳＩＭＤ命令として容易に実行される。さらに、オーバーラップ演算の場合、スケーリング演算も同様に、これらのベクトルで機能するＳＩＭＤ命令として実行されうる。回転（アクション１５５０、１６３０）は、部分的に並列化可能である。それは、関与する回転の一部が、４成分ベクトル内のデータポイントの２つのペアに実行される１Ｄ演算と同一であるからである。これらの回転はまた、乗算およびシフト演算により並列化されうる。
【００７４】
ベクトル内のデータ成分の再配列により、変換の最終出力もまた再配列される。この再配列は、変換が圧縮ビットストリームの符号器による出力のリストとして係数を順序付けるためにスキャンされるので、通常は問題にならない。並列の実施態様において、スキャンアレイは、再配列を考慮に入れるので、アルゴリズムの複雑さに悪影響を与えることはない。
【００７５】
同様の並列化技法は、ブロック変換とオーバーラップ演算の順序が反転されること、および各々のプロセスのアクション１５３０〜１５６０および１６２０〜１６３０の順序が反転されることを除いて、逆重複双直交変換にも有効である。再配列されたスキャンパターンは、入力データアレイを取り込むために使用され、出力は後に、図１０に示されるマッピングとは逆の方法で再マップされる。
【００７６】
並列化技法はまた、重複直交／双直交変換のその他のバージョンを使用する代替の実施態様にも有効である。ブロック変換プロセス１６００の説明において述べたように、並列化は、自身による（つまりオーバーラップ演算子なしの）ブロック変換にも使用することができる。４以外の変換およびオーバーラップサイズ、２を超える大きさはまた、並列化論理の簡単な拡張で対応することができる。
【００７７】
色変換の段階で、符号器でねじれた格子に再マップを実行し、復号器でねじれた格子から再マップを実行することにより、ベクトル化のコストは最小化される。復号器の色変換は、（ｉ）多数のカラーフォーマット、（ｉｉ）多くのカラーフォーマットの２４ビット画素境界によりワード位置合わせの不足、（ｉｉｉ）復号器側でクリッピングを実行する必要性などを含むいくつかの理由により、一般に連続して実施される。色変換に加えて再マップの追加コストは最小であるため、全般的なパフォーマンス向上のためにこの並列化技法を使用することが容易になる。さらに、入力画像が回転および／または横反転された方向で提示される場合、または出力画像に回転および／または横反転された方向が望ましい場合は、全体の計算上の複雑さをほとんど増すことなく達成することができる。
【００７８】
３．  コンピューティング環境
変換並列化技法を使用して実施される重複双直交変換を組み入れる前述の代表的な符号器３００（図３）および復号器４００（図４）は、特に、コンピュータ、画像およびビデオ記録、送信および受信装置、ポータブルビデオプレイヤー、テレビ会議などを含む、デジタルメディア信号処理が実行される任意のさまざまなデバイスで実行することができる。デジタルメディア符号化技法は、ハードウェア回路、および図１７に示されるようなコンピュータまたはその他のコンピューティング環境内で実行するデジタルメディア処理ソフトウェアにおいて実施されうる。
【００７９】
図１７は、前述の実施形態を実施することができる適切なコンピューティング環境（１７００）の一般例を示す。本発明はさまざまな汎用または特殊用途コンピューティング環境において実施されうるので、コンピューティング環境（１７００）は、本発明の使用または機能の範囲に関していかなる限定を示唆することも意図するものではない。
【００８０】
図１７を参照すると、コンピューティング環境（１７００）は、少なくとも１つの処理装置（１７１０）およびメモリ（１７２０）を含む。図１７において、この最も基本的な構成（１７３０）は、破線内に含まれている。処理装置（１７１０）は、コンピュータ実行可能命令を実行し、現実または仮想のプロセッサであってもよい。マルチプロセッシングシステムにおいて、複数の処理装置は、コンピュータ実行可能命令を実行して処理能力を増強する。メモリ（１７２０）は揮発性メモリ（たとえば、レジスタ、キャッシュ、ＲＡＭ）、不揮発性メモリ（たとえば、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリなど）、またはこの２つの組合せであってもよい。メモリ（１７２０）は、前述のデジタルメディア符号化／復号化および変換並列化技法を実施するソフトウェア（１７８０）を格納する。
【００８１】
コンピューティング環境は、追加の特徴を有することもできる。たとえば、コンピューティング環境（１７００）は、記憶装置（１７４０）、１つまたは複数の入力装置（１７５０）、１つまたは複数の出力装置（１７６０）、および１つまたは複数の通信接続（１７７０）を含む。バス、コントローラ、またはネットワークのような相互接続機構（図示せず）は、コンピューティング環境（１７００）のコンポーネントを相互接続する。通常、オペレーティングソフトウェア（図示せず）は、コンピューティング環境（１７００）で実行する他のソフトウェアのオペレーティング環境を提供し、コンピューティング環境（１７００）のコンポーネントのアクティビティを調整する。
【００８２】
記憶装置（１７４０）は、取り外し可能または固定式であってもよく、磁気ディスク、磁気テープまたはカセット、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、ＤＶＤ、情報を格納するために使用され、コンピューティング環境（１７００）内でアクセスされうる任意の他の媒体を含む。記憶装置（１７４０）は、変換並列化技法を使用して前述の符号器／復号器を実施するソフトウェア（１７８０）の命令を格納する。
【００８３】
入力装置（１７５０）は、キーボード、マウス、ペン、またはトラックボールなどのタッチ入力装置、音声入力装置、スキャニング装置、またはコンピューティング環境（１７００）に入力を供給する他の装置であってもよい。音声の場合、入力装置（１７５０）は、サウンドカード、または音声入力をアナログまたはデジタル形式で受け入れる同様の装置、あるいは音声サンプルをコンピューティング環境に供給するＣＤ−ＲＯＭリーダーであってもよい。出力装置（１７６０）は、ディスプレイ、プリンタ、スピーカ、ＣＤ−ライター、またコンピューティング環境（１７００）から出力を供給する他の装置であってもよい。
【００８４】
通信接続（１７７０）は、通信媒体を介して他のコンピューティングエンティティと通信できるようにする。通信媒体は、コンピュータ実行可能命令などの情報、圧縮音声またはビデオ情報、またはその他のデータを変調データ信号で搬送する。変調データ信号とは、１つまたは複数の特性セットを備える信号、または信号の情報を符号化するような方法で変更された信号を意味する。限定的ではなく例示的に、通信媒体は、電気、光学、ＲＦ、赤外線、音響、またはその他の搬送波で実施される有線または無線技法を含む。
【００８５】
本明細書においてデジタルメディア処理技法は、コンピュータ可読媒体の一般的なコンテキストにおいて説明されうる。コンピュータ可読媒体は、コンピューティング環境内でアクセスすることができる任意の使用可能な媒体である。限定的ではなく例示的に、コンピューティング環境（１７００）と共に、コンピュータ可読媒体は、メモリ（１７２０）、記憶装置（１７４０）、通信媒体、およびそれらの任意の組合せを含む。
【００８６】
本明細書におけるデジタルメディア処理技法は、プログラムモジュールに含まれ、ターゲットの現実または仮想のプロセッサのコンピューティング環境で実行される命令のような、コンピュータ実行可能命令の一般的なコンテキストに即して説明されうる。一般に、プログラムモジュールは、特定のタスクを実行するかまたは特定の抽象データタイプを実装するルーチン、プログラム、ライブラリ、オブジェクト、クラス、コンポーネント、データ構造などを含む。プログラムモジュールの機能は、さまざまな実施形態において要求されるとおりにプログラムモジュール間で組み合わされるかまたは分散されてもよい。プログラムモジュールのコンピュータ実行可能命令は、ローカルまたは分散コンピューティング環境内で実行することができる。
【００８７】
提示のために、詳細な説明では「ｄｅｔｅｒｍｉｎｅ（決定する）」、「ｇｅｎｅｒａｔｅ（生成する）」、「ａｄｊｕｓｔ（調整する）」、および「ａｐｐｌｙ（適用する）」などの用語を使用して、コンピューティング環境におけるコンピュータオペレーションを説明する。これらの用語は、コンピュータによって実行されるオペレーションの高水準な抽象概念であり、人間によって行われる行為と混同されてはならない。これらの用語に対応する実際のコンピュータオペレーションは、実施態様に応じて異なる。
【００８８】
本明細書において説明される主題の多くの可能な変種を考慮して、添付の特許請求の範囲およびその等価物の範囲に含まれるすべての実施形態を本発明として特許請求する。
【図面の簡単な説明】
【００８９】
【図１】従来技術における標準的なブロック変換ベースのコーデックを示すブロック図である。
【図２】重複変換の例を示す流れ図である。
【図３】ワイドレンジ係数の適応符号化を組み入れる代表的な符号器を示す流れ図である。
【図４】適応符号化されたワイドレンジ係数の復号化を組み入れる復号器を示す流れ図である。
【図５】プレフィルタ（またはオーバーラップ演算子）およびブロック変換として重複変換定式化の例を示す流れ図であり、ここでプレフィルタは、入力境界またはブロック変換のブロック端部にわたって適用される。
【図６】図５のプレフィルタおよびブロック変換定式化を有する代表的な重複変換を示す信号フローグラフである。
【図７】図６のプレフィルタおよびブロック変換定式化を有する代表的な重複双直交変換の並列化ＳＩＭＤバージョンを示す信号フローグラフである。
【図８】図７の１次元重複双直交変換の並列化ＳＩＭＤバージョンに使用される、２成分ベクトルへの１次元データのグループ化を示す図である。
【図９】図７の１次元重複双直交変換を示すベクトル信号フローグラフである。
【図１０】２次元重複双直交変換の並列化ＳＩＭＤバージョンに使用される、４成分ベクトルへの２次元データのグループ化を示す図である。
【図１１】図１０に示されるベクトルへのグループ化による２次元データのベクトル表記を示す図である。
【図１２】２次元重複双直交変換のオーバーラップ演算子（プレフィルタ）部分が適用され、オーバーラップ演算子の２×２アダマール演算子部分が適用される、２次元データおよび対応する並列化成分ベクトルにおける画素成分を示す図である。
【図１３】２次元重複双直交変換のブロック変換部分が適用され、そのブロック変換の２×２アダマール演算子部分が適用される、２次元データおよび対応する並列化成分ベクトルにおける画素成分を示す図である。
【図１４】２次元重複双直交変換のオーバーラップ演算子を示す図である。
【図１５】並列化２次元重複双直交変換のオーバーラップ演算子を実施するプロセスを示す流れ図である。
【図１６】並列化２次元重複双直交変換のブロック変換を実施するプロセスを示す流れ図である。
【図１７】図３および図４の代表的な符号器／復号器の並列化ＳＩＭＤバージョンを実施する最適なコンピューティング環境を示すブロック図である。
【図１】
2009505497.tif 000004
【図２】
2009505497.tif 000005
【図３】
2009505497.tif 000006
【図４】
2009505497.tif 000007
【図５】
2009505497.tif 000008
【図６】
2009505497.tif 000009
【図７】
2009505497.tif 000010
【図８】
2009505497.tif 000011
【図９】
2009505497.tif 000012
【図１０】
2009505497.tif 000013
【図１１】
2009505497.tif 000014
【図１２】
2009505497.tif 000015
【図１３】
2009505497.tif 000016
【図１４】
2009505497.tif 000017
【図１５】
2009505497.tif 000018
【図１６】
2009505497.tif 000019
【図１７】
2009505497.tif 000020
【国際調査報告】
2009505497.tif 000021