(57)【要約】【課題】効率的な損失なしデータ圧縮のための可逆重ね合わせ演算子を提供すること。【解決手段】効率的な重ね合わせ変換が、単位行列式成分行列で構成されたプリフィルタおよびポストフィルタ（または可逆重ね合わせ演算子）を使って実現される。プリフィルタおよびポストフィルタは、一連の平面回転変換および単位行列式平面スケーリング変換として実現される。平面スケーリング変換は、平面せん断変形またはリフティングステップを使って実装され得る。さらに、平面回転および平面せん断変形は、可逆／損失なし演算としての実装形態を持ち、結果として、可逆重ね合わせ演算子をもたらす。【選択図】図１１
2006174487.tif 000002
【特許請求の範囲】
【請求項１】
タイル状のブロックに分割されたディジタルメディアデータを符号化し、かつ／または復号化する方法であって、
ブロック間の境界の少なくともいくつかにまたがって、単位行列式である可逆重ね合わせ演算子を適用すること、および
前記ブロックに可逆ブロック変換を適用すること
を含み、
前記可逆重ね合わせ演算子および前記可逆ブロック変換の前記適用は、前記ディジタルメディアデータの符号化と復号化の間で反転される
ことを特徴とする方法。
【請求項２】
前記可逆重ね合わせ演算子は、それぞれが単位行列式である複数の成分から構成されることを特徴とする請求項１に記載の方法。
【請求項３】
前記可逆重ね合わせ演算子の前記適用は、
可逆アダマールネットワークを適用すること、
可逆ブロック回転を適用すること、
可逆スケーリング演算子を適用すること、
別の可逆ブロック回転を適用すること、および
可逆逆アダマールネットワークを適用すること
を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記可逆スケーリング演算子の前記適用は、
第１の値を、第２の値にパラメータ値と１引く前記パラメータ値の二乗との比を掛けた積と合計する第１のリフティングステップを実行すること、
前記第２の値を、前記第１の和に前記パラメータ値を掛けた積と合計する第２のリフティングステップを実行すること、
前記第１の和を、前記第２の和に前記パラメータ値の負数を掛けた積と合計する第３のリフティングステップを実行すること、および
前記第２の和を、前記第３の和に前記パラメータ値と１引く前記パラメータ値の二乗との比の負数を掛けた積と合計する第４のリフティングステップを実行すること
を含む４リフティングステップ手順を実行することを含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記可逆スケーリング演算子の前記適用は、
第２の値を第１の値と合計する第１のリフティングステップを実行すること、
前記第１の値を、前記第１の和に、ｓ２＋ｃ２＝１である
【数１】
2006174487.tif 000013
を掛けた積と合計する第２のリフティングステップを実行すること、
前記第１の和を、前記第２の和に
【数２】
2006174487.tif 000014
を掛けた積と合計する第３のリフティングステップを実行すること、
前記第２の和を、前記第３の和に
【数３】
2006174487.tif 000015
を掛けた積と合計する第４のリフティングステップを実行すること、および
前記第３の和を、前記第４の和の負数の積と合計する第５のリフティングステップを実行すること
を含む５リフティングステップ手順を実行することを含むことを特徴とする請求項３に記載の方法。
【請求項６】
前記リフティングステップの１つまたは複数は、前記可逆重ね合わせ演算子の別のステップと組み合わされ、または前記可逆重ね合わせ演算子の別のステップによって相殺されることを特徴とする請求項５に記載の方法。
【請求項７】
前記可逆スケーリング演算子の前記適用は、２点スケーリングのカスケードを使ってＭ個のスケーリング係数ｓ１からｓＭによってＭ個のデータパスをスケーリングすることを含むことを特徴とする請求項５に記載の方法。
【請求項８】
符号化され、かつ／または復号化されるディジタルメディアデータを格納するデータ記憶バッファと、
前記ディジタルメディアデータをタイル状のブロックに分割し、
ブロック間の境界の少なくともいくつかにまたがって、単位行列式である可逆重ね合わせ演算子を適用し、
前記ブロックに可逆ブロック変換を適用する
ようにプログラムされたプロセッサと
を備え、
前記可逆重ね合わせ演算子および前記可逆ブロック変換の前記適用は、前記ディジタルメディアデータの符号化と復号化の間で反転される
ことを特徴とするディジタルメディア符号器および／または復号器。
【請求項９】
前記可逆重ね合わせ演算子は、それぞれが単位行列式である複数の成分変換から構成されることを特徴とする請求項８に記載のディジタルメディア符号器および／または復号器。
【請求項１０】
前記プロセッサは、前記可逆重ね合わせ演算子を、
可逆アダマールネットワークを適用すること、
可逆ブロック回転を適用すること、
可逆スケーリング演算子を適用すること、
別の可逆ブロック回転を適用すること、および
可逆逆アダマールネットワークを適用すること
によって実現することを特徴とする請求項９に記載のディジタルメディア符号器および／または復号器。
【請求項１１】
前記プロセッサは、前記可逆スケーリング演算子を適用するに際して、
第１の値を、第２の値にパラメータ値と１引く前記パラメータ値の二乗との比を掛けた積と合計する第１のリフティングステップを実行すること、
前記第２の値を、前記第１の和に前記パラメータ値を掛けた積と合計する第２のリフティングステップを実行すること、
前記第１の和を、前記第２の和に前記パラメータ値の負数を掛けた積と合計する第３のリフティングステップを実行すること、および
前記第２の和を、前記第３の和に前記パラメータ値と１引く前記パラメータ値の二乗との比の負数を掛けた積と合計する第４のリフティングステップを実行すること
を含む４リフティングステップ手順を実行することを特徴とする請求項１０に記載のディジタルメディア符号器および／または復号器。
【請求項１２】
前記プロセッサは、前記可逆スケーリング演算子を適用するに際して、
第２の値を第１の値と合計する第１のリフティングステップを実行すること、
前記第１の値を、前記第１の和に、ｓ２＋ｃ２＝１である
【数４】
2006174487.tif 000016
を掛けた積と合計する第２のリフティングステップを実行すること、
前記第１の和を、前記第２の和に
【数５】
2006174487.tif 000017
を掛けた積と合計する第３のリフティングステップを実行すること、
前記第２の和を、前記第３の和に
【数６】
2006174487.tif 000018
を掛けた積と合計する第４のリフティングステップを実行すること、および
前記第３の和を、前記第４の和の負数の積と合計する第５のリフティングステップを実行すること
を含む５リフティングステップ手順を実行することを特徴とする請求項１０に記載のディジタルメディア符号器および／または復号器。
【請求項１３】
前記リフティングステップの１つまたは複数は、前記可逆重ね合わせ演算子の別のステップと組み合わされ、または前記可逆重ね合わせ演算子の別のステップによって相殺されることを特徴とする請求項１２に記載のディジタルメディア符号器および／または復号器。
【請求項１４】
前記プロセッサは、前記可逆スケーリング演算子を、２点スケーリングのカスケードを使ってＭ個のスケーリング係数ｓ１からｓＭによってＭ個のデータパスをスケーリングすることによって実現することを特徴とする請求項１２に記載のディジタルメディア符号器および／または復号器。
【請求項１５】
タイル状のブロックに分割されたディジタルメディアを処理する方法を実行するコンピュータ実行可能ディジタルメディア処理プログラムを保持している少なくとも１つのコンピュータ可読記録媒体であって、前記方法は、
ブロック間の境界の少なくともいくつかにまたがって、単位行列式である可逆重ね合わせ演算子を適用すること、および
前記ブロックに可逆ブロック変換を適用すること
を含み、
前記可逆重ね合わせ演算子および前記可逆ブロック変換の前記適用は、前記ディジタルメディアデータの符号化と復号化の間で反転される
ことを特徴とする少なくとも１つのコンピュータ可読記録媒体。
【請求項１６】
前記可逆重ね合わせ演算子は、それぞれが単位行列式である複数の成分から構成されることを特徴とする請求項１５に記載の少なくとも１つのコンピュータ可読記録媒体。
【請求項１７】
前記可逆重ね合わせ演算子の前記適用は、
可逆アダマールネットワークを適用すること、
可逆ブロック回転を適用すること、
可逆スケーリング演算子を適用すること、
別の可逆ブロック回転を適用すること、および
可逆逆アダマールネットワークを適用すること
を含むことを特徴とする請求項１６に記載の少なくとも１つのコンピュータ可読記録媒体。
【請求項１８】
前記可逆スケーリング演算子の前記適用は、
第１の値を、第２の値にパラメータ値と１引く前記パラメータ値の二乗との比を掛けた積と合計する第１のリフティングステップを実行すること、
前記第２の値を、前記第１の和に前記パラメータ値を掛けた積と合計する第２のリフティングステップを実行すること、
前記第１の和を、前記第２の和に前記パラメータ値の負数を掛けた積と合計する第３のリフティングステップを実行すること、および
前記第２の和を、前記第３の和に前記パラメータ値と１引く前記パラメータ値の二乗との比の負数を掛けた積と合計する第４のリフティングステップを実行すること
を含む４リフティングステップ手順を実行することを含むことを特徴とする請求項１７に記載の少なくとも１つのコンピュータ可読記録媒体。
【請求項１９】
前記可逆スケーリング演算子の前記適用は、
第２の値を第１の値と合計する第１のリフティングステップを実行すること、
前記第１の値を、前記第１の和に、ｓ２＋ｃ２＝１である
【数７】
2006174487.tif 000019
を掛けた積と合計する第２のリフティングステップを実行すること、
前記第１の和を、前記第２の和に
【数８】
2006174487.tif 000020
を掛けた積と合計する第３のリフティングステップを実行すること、
前記第２の和を、前記第３の和に
【数９】
2006174487.tif 000021
を掛けた積と合計する第４のリフティングステップを実行すること、および
前記第３の和を、前記第４の和の負数の積と合計する第５のリフティングステップを実行すること
を含む５リフティングステップ手順を実行することを含むことを特徴とする請求項１７に記載の少なくとも１つのコンピュータ可読記録媒体。
【請求項２０】
前記可逆スケーリング演算子の前記適用は、２点スケーリングのカスケードを使ってＭ個のスケーリング係数ｓ１からｓＭによってＭ個のデータパスをスケーリングすることを含むことを特徴とする請求項１９に記載の少なくとも１つのコンピュータ可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、重ね合わせ変換を使ったディジタルメディア（ビデオや画像など）圧縮に関する。
【背景技術】
【０００２】
（重ね合わせ変換）
重ね合わせ変換は、データ圧縮で使用される強力な信号処理技法である（例えば、非特許文献１参照）。しかしながら、今日まで、線形位相を用いた効率的な重ね合わせ変換は、損失なし（可逆）データ圧縮については考案されておらず、適用もされていない。
【０００３】
以下でより詳細に論じるように、重ね合わせ変換は、プリフィルタの後にデータ変換が続くもの（およびその逆の、逆データ変換の後にポストフィルタが続くもの）として考案され得ることが知られている（非特許文献２および３参照）。この考案方式で損失なしデータ変換を使って、可逆性の正しい尺度が達成され得る。これまでは、特定の限られた種類のプリフィルタおよびポストフィルタだけが可逆性のために選択され得ると考えられてきた。この限られたセットは、その圧縮（レート対ひずみ、またはＲＤ）性能が非常に制限される。最近のある論文（非特許文献４参照）には、その大部分の要素が可逆であり、良好な圧縮特性を持つ構造が提示された。
【０００４】
音声圧縮においては、可逆重ね合わせ変換のためのいくつかの構造が紹介された（非特許文献５および６参照）。しかしながら、これらの構造は、その基底関数が直交し、対称でない（すなわち、基底関数が線形位相でない）、変形離散コサイン変換（ＭＤＣＴ）とも呼ばれる、変調重ね合わせ変換（ＭＬＴ）にのみ適用できる。これらの変換は、ディジタル写真圧縮の場合など、線形位相（対称）関数が必要とされるデータ圧縮用途には適用できない。
【０００５】
写真（画像）圧縮では、ＲＤ性能の点で最もうまく機能する変換の１つは、重ね合わせ双直交変換（ＬＢＴ）である（非特許文献７参照）。ＭＬＴと異なり、ＬＢＴの基底関数は対称であり、厳密に直交しない（ＬＢＴでは、分析基底関数(analysis basis function)が合成基底関数(synthesis basis function)に直交し、それゆえに、双直交という用語が使用される）。ＬＢＴは、画像圧縮用途ではうまく使用されているが、損失なし画像圧縮ではまだ使用されていない。というのは、整数可逆構造が知られていなかったからである。
【０００６】
（ブロック変換ベースの符号化の概要）
変換符号化は、多くのオーディオ、画像およびビデオ圧縮システムで使用される圧縮技法である。圧縮されていないディジタル画像およびビデオは、通常、２次元（２Ｄ）グリッドとして構成された画像またはビデオフレーム中の場所にある画素または色のサンプルとして表され、または取り込まれる。これは、画像またはビデオの空間領域表現と呼ばれる。例えば、画像での１つの典型的な形式は、グリッドとして構成された２４ビット色画素サンプルのストリームからなる。各サンプルは、特に、ＲＧＢやＹＩＱといった色空間内のグリッド中のある画素位置における色成分を表す数である。様々な画像およびビデオシステムが、多種多様なサンプリングの色、空間および時間分解能を使用し得る。同様に、ディジタルオーディオは、通常、時間サンプリングされたオーディオ信号ストリームとして表される。例えば、１つの典型的なオーディオ形式は、規則的な時間間隔で取られたオーディオ信号の１６ビット振幅サンプルのストリームからなる。
【０００７】
圧縮されていないディジタルオーディオ、画像およびビデオ信号は、相当な記憶および伝送容量を消費し得る。変換符号化は、信号の空間領域表現を周波数領域（または他の類似の変換領域）表現に変換し、次いで、その変換領域表現の、特定の、一般により知覚されにくい周波数成分の分解能を低減することによって、ディジタルオーディオ、画像およびビデオのサイズを縮小する。これは、一般に、空間領域における画像またはビデオの色または空間分解能、あるいは時間領域におけるオーディオの分解能を低減するのと比べて、はるかに知覚されにくいディジタル信号の劣化を生じる。
【０００８】
より具体的には、図１に示す典型的なブロック変換ベースのコーデック１００は、圧縮されていないディジタル画像の画素を、各ブロックが、おそらく、他のブロックと重なり合う固定サイズの２次元ブロック（Ｘ１，．．．Ｘｎ）に分割する。空間周波数分析を行う線形変換１２０〜１２１が各ブロックに適用され、ブロック内の間隔が置かれたサンプルが、一般に、そのブロック間隔にわたる対応する周波数帯域でのディジタル信号の強さを表す、１組の周波数（または変換）係数に変換される。圧縮では、これらの変換係数が選択的に量子化され１３０（すなわち、係数値の最下位ビットを除去し、あるいは別の方法でより高い分解能数セット中の値をより低い分解能にマップすることによって、分解能が低減され）、さらに、圧縮データストリームにエントロピまたは可変長符号化１３０され得る。復号化時に、変換係数は、元の色／空間サンプリング画像／ビデオ信号（復元されたブロック
【０００９】
【数１】
2006174487.tif 000003
【００１０】
）をほぼ復元するように逆変換される１７０〜１７１。
【００１１】
ブロック変換１２０〜１２１は、サイズＮのベクトルｘに対する数学演算として定義され得る。たいていの場合、この演算は線形乗算であり、Ｍを変換行列とする、変換領域出力ｙ＝Ｍｘを生じる。入力データが任意に長いとき、それは、サイズＮのベクトルに区分化され、ブロック変換が各区分に適用される。データ圧縮のためには、可逆ブロック変換が選択される。言い換えると、行列Ｍは反転可能である。（例えば画像やビデオなどの）多次元において、ブロック変換は、通常、分離可能な演算として実施される。行列乗算は、データの各次元（すなわち行と列の両方）に沿って分離可能に適用される。
【００１２】
圧縮では、変換係数（ベクトルｙの成分）が、選択的に量子化され（すなわち、係数値の最下位ビットを除去し、あるいは別の方法でより高い分解能数セット中の値をより低い分解能にマップすることによって、分解能が低減され）、さらに、圧縮データストリームにエントロピまたは可変長符号化され得る。
【００１３】
復号器１５０における復号時には、図１に示すように、これらの演算の逆（逆量子化／エントロピ復号化１６０および逆ブロック変換１７０〜１７１）が復号器１５０側で適用される。データを復元する間、逆行列Ｍ−１（逆変換１７０〜１７１）が、乗数として変換領域データに適用される。変換領域データに適用されると、この逆変換は、ほぼ、元の時間領域または空間領域ディジタルメディアを復元する。
【００１４】
多くのブロック変換ベースの符号化アプリケーションにおいて、変換は、望ましくは、量子化係数に応じて、損失ありと損失なし両方の圧縮をサポートするように、可逆である。例えば、量子化なしの場合（一般に、量子化係数１として表される）、可逆変換を利用するコーデックは、復号時に入力データを正確に再現することができる。しかしながら、これらのアプリケーションにおける可逆性の要件は、コーデックがそれに基づいて設計され得る変換の選択を制約する。
【００１５】
ＭＰＥＧやＷｉｎｄｏｗｓ（登録商標）  Ｍｅｄｉａなど、多くの画像およびビデオ圧縮システムは、特に、離散コサイン変換（ＤＣＴ）に基づく変換を利用する。ＤＣＴは、ほぼ最適なデータ圧縮を生じる好適なエネルギ圧縮特性(energy compaction properties)を持つことが知られている。これらの圧縮システムでは、個々の画像ブロックを復元するために、圧縮システムの符号器と復号器両方の復元ループで逆ＤＣＴ（ＩＤＣＴ）が用いられる。ＤＣＴについては記載されている（例えば、非特許文献８参照）。ＩＤＣＴの例示的実装形態については記載されている（例えば、非特許文献９参照）。
【００１６】
静止画像（またはビデオシーケンスにおける画面内符号化フレーム）を圧縮する間、ＭＰＥＧ−２、ＭＰＥＧ−４、Ｗｉｎｄｏｗｓ（登録商標）  Ｍｅｄｉａなどの最も一般的な規格は、その画像を正方形のタイルに分割し、各画像タイルにブロック変換を適用する。所与の区画（一般にブロックと呼ばれる）における変換係数は、そのブロック内の未処理データ成分によってのみ影響される。量子化など、符号器側における不可逆の、または損失ありの演算は、復号化画像にアーティファクトを生じさせる。これらのアーティファクトは、ブロック間で独立であり、ブロックひずみ(blocking effect)と呼ばれる視覚的に不快な影響を生じる。同様にオーディオデータでは、重なり合わないブロックが独立に変換符号化されると、量子化誤差が、復号器におけるオーディオ信号の復元時に、ブロック境界のところの信号における不連続性を生じる。オーディオでは、周期的なクリッキングが聞こえる。
【００１７】
ブロックひずみに対処するのにいくつかの技法が使用される。中でも最も一般的な技法が、ブロック間エッジ境界を平滑化する非ブロック化フィルタ、および未処理の入力データと近隣のブロック境界からの予測の間の差異を符号化する空間的外挿である。これらの技法には欠点がないわけではない。例えば、非ブロック化フィルタ手法は「オープンループ」である。すなわち、その順変換プロセスは、非ブロック化が、復号器側で復元の前に実行されることになることを考慮に入れない。その上、これらの技法は、両方とも、計算上高くつく。
【００１８】
ブロックひずみを最小限に抑えるために、ブロック相互間の相関関係が利用され得る。ブロック相互間の相関関係を実現する１つのやり方は、重ね合わせ変換を使用することによるものである（例えば、非特許文献１０参照）。重ね合わせ変換とは、その入力が、現在のブロック中のデータ要素に加えて、近隣のブロック中の少数の隣接する要素にも及ぶ変換である。同様に、復元側で、この逆変換は、現在のブロック中のすべてのデータ点と共に近隣のブロック中の少数のデータ点にも影響を及ぼす。
【００１９】
２次元（２Ｄ）データの場合には、重ね合わせ２Ｄ変換は、現在のブロックと、左、上、右、下、および、おそらくは、左上、右上、左下、右下のブロックの選択要素との関数である。現在の変換を計算するのに使用される近隣のブロック中のデータ点の数は、重ね合わせと呼ばれる。
【００２０】
（空間領域重ね合わせ変換の概要）
重ね合わせ変換は、従来方式のブロック変換の後に変換領域量をマージするステップとして変換領域で実装され得る。さもなければ、重ね合わせ変換は、重ね合わせの範囲内の画素に適用される前処理段によって、空間領域で実装され得る。これら２つの実装形態は、数学的に関連しており、したがって、等価である。
【００２１】
図２に、従来方式の空間領域重ね合わせ変換の一例を示す。図示の例では、重ね合わせは２画素であり、図示の２つの隣接するブロックから２画素ずつが前処理段２１０において前処理される。２つの前処理された出力は、図１と同様にコーデック２００によるブロック変換ベースの符号化のためにブロックのそれぞれに送られる。前処理段の逆が、復号化後に後処理段２２０において適用される。前処理およびブロック変換の適切な選択により、幅広い重ね合わせ変換が実現され得る。
【００２２】
重ね合わせ変換の空間領域実現の主要な利点は、既存のブロック変換ベースのコーデックに、前処理および後処理段を後付けし、既存のコーデック枠組みを使って、重ね合わせ変換の利益、すなわち、ブロックひずみの低減およびより適切な圧縮が導出され得ることである。前処理２１０および後処理は、図３に示す行列乗算として表され得る。従来方式では、前処理および後処理行列は、相互の逆である。すなわち、前処理行列（Ｐｆ）とその逆または後処理行列（Ｐｉ）を一緒に掛け合わせると、単位行列Ｉに等しい。
【００２３】
（定義）
一般に、変換の長さＮは、ある変換ブロック中の変換係数の数である。
【００２４】
変換のサポートＫは、その変換ブロックの係数に影響を与える入力データ点の数である。同様に、サポートＫは、逆変換のプロセスで、各変換係数によって影響される出力データ点の数でもある。
【００２５】
離散コサイン変換（ＤＣＴ）などの典型的なブロック変換では、その長さとサポートは同一である。しかしながら、重ね合わせ変換（ＬＴ）は、そのサポートＫが長さＮより大きい変換の１つの重要なクラスである。重ね合わせ変換のサポートおよび長さを表すには、Ｋ×Ｎという表記法が使用される（Ｋ＜Ｎである変換は拡張的であり、したがって、データ圧縮では使用されない）。
【００２６】
一例３００として、図３に示す６×４ＬＴ３１０は、６つの入力および４つの出力を持つ変換である。この変換は反転可能であるため、これらの入力の２つは隣接する変換ブロックと共用される。逆重ね合わせ変換（ＩＬＴ）３２０は、その４つの入力から６つの出力を生み出す。ブロック境界に近い出力データ点（この場合にはブロックの各端部ごとに１点）は、２つの隣接する逆変換ブロックの対応する応答を合計することによって復元される。
【００２７】
（圧縮システムで使用される重ね合わせ変換の制約条件）
数学的な意味で、重ね合わせ変換は、入力および出力信号ならびに中間計算結果を実数とみなすとき、反転可能な構造である。無限精度が達成され得る場合、入力データは、その重ね合わせ変換係数から完全に回復され得るはずである。しかしながら、無限精度は実際には不可能である。すなわち、データの損失なし圧縮のための要件は、整数または固定精度の演算に作用し、しかも、変換係数の整数表現が与えられたものとして、データを完全に復元する変換を設計することである。これは、数学的反転可能性より強い条件であり、そのような変換を、本明細書では、「損失なし」変換と呼ぶ。さらに、この損失なし変換は、（損失なしと損失あり両方の）データ圧縮でも効率的であることが必要とされる。その効率性は、変換されたデータのエントロピによって測定される。すなわち、エントロピが低いほど、変換されるデータは、コンテキストベースの算術符号化や適応ランレングス符号化などの標準エントロピ符号化技法によって、より一層圧縮され得る。
【００２８】
【非特許文献１】H. S. Malvar, Signal Processing with Lapped Transforms. Boston, MA: Artech House, 1992
【非特許文献２】H. S. Malvar, "A pre- and post-filtering technique for the reduction of blocking effects," in Proc. Picture Coding Symposium, Stockholm, Sweden, Jun. 1987
【非特許文献３】T.D. Tran, J. Liang, and C. Tu, "Lapped Transform via Time-Domain Pre- and Post-Filtering", IEEE Trans. on Signal Processing, vol.51, no.6, June 2003
【非特許文献４】W. Dai and T. Tran, "Regularity-constrained pre- and post-filtering for block DCT-based systems," IEEE Trans. on Signal Processing, vol. 51, pp. 2568-2581, Oct. 2003
【非特許文献５】R. Geiger, J. Herre, J. Koller, and K. Brandenburg, "IntMDCT - A link between perceptual and lossless audio coding," in Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, Orlando, FL, May 2002;
【非特許文献６】J. Li, "Reversible FFT and MDCT viva matrix lifting." in Proc. IEEE Conf. on Acoustics, Speech, and Signal Processing, Montreal, Canada, May 2004
【非特許文献７】H. S. Malvar, "Biorthogonal and nonuniform lapped transforms for transform coding with reduced blocking and ringing artifacts," IEEE Trans. on Signal Processing, vol. 46, pp. 1043-1053, Apr. 1998
【非特許文献８】N. Ahmed, T. Natarajan, and K.R. Rao, "Discrete Cosine Transform," IEEE Transactions on Computers, C-23 (January 1974), pp. 90-93
【非特許文献９】"IEEE Standard Specification for the Implementations of 8x8 Inverse Discrete Cosine Transform," IEEE Std. 1180-1990, December 6, 1990
【非特許文献１０】H. Malvar, "Signal Processing with Lapped Transforms," Artech House, Norwood MA, 1992
【非特許文献１１】A. A. M. L. Bruekens and A. W. M. van den Enden, "New networks for perfect inversion and perfect reconstruction", IEEE J. Selected Areas Communications, vol.10, no.1, 1992
【非特許文献１２】I. Daubechies and W. Sweldens, "Factoring wavelet transform into lifting steps", J. Fourier Anal. Appl., vol. 4, pp. 247-269, 1998
【非特許文献１３】J. Liang and T. D. Tran, "Fast multiplierless approximations of the DCT with the lifting scheme," IEEE Trans. Signal Processing, vol. 49, pp. 3032-3044, Dec. 2001
【発明の開示】
【発明が解決しようとする課題】
【００２９】
本発明は、整数演算において可逆であり、効率的な損失なしデータ圧縮／伸張システムの基礎として使用され得る、効率的な重ね合わせ変換を提供する。
【課題を解決するための手段】
【００３０】
本明細書では、整数演算において可逆であり、効率的な損失なしデータ圧縮／伸張システムの基礎として使用され得る、効率的な重ね合わせ変換の様々な実現形態について説明する。
【００３１】
最も効率的な損失なし変換設計（すなわち、変換されたデータの最小限のエントロピを伴うもの）は、変換行列が単位行列式(unit determinant)である（すなわち、変換行列の行列式が±１である）ことを必要とすることが示され得る。以下の説明では、変換が行列乗算として表され得ると想定されるが、データの丸めなど、少数の非線形現象があり得ることが認められている。ゆえに、行列式に言及するとき、切り捨てまたは丸めの側面は考察されない。
【００３２】
効率的な重ね合わせ変換は、本明細書で「重ね合わせ演算子」と呼ぶプリフィルタおよびポストフィルタを使って実現される。この実現形態は、可逆であり、しかも非常にＲＤ効率が高い。これらの新しい重ね合わせ演算子は、用途の中でも特に、損失なし画像圧縮に使用され得る、可逆ＬＢＴの実装を可能にする。プリフィルタおよびポストフィルタは、可逆演算を使用する。さらに、前述の重ね合わせ演算子は、計算上の効率のための単純化も含む。
【００３３】
プリおよびポストフィルタリング演算の１つの実現形態は、一連の平面回転変換(planar rotational transform)および単位行列式平面スケーリング変換としてのものである。さらに、平面回転および平面せん断変形(shear)は、可逆／損失なし演算としての実装形態を持ち、結果として、可逆重ね合わせ演算子(reversible overlap operator)をもたらす。
【００３４】
１つの適用例は、可逆重ね合わせ演算子の計算上効率のよい近似を使って実現される８×４の１次元重ね合わせ変換(lapped transform)におけるものである。
【００３５】
本発明のその他の特徴および利点は、添付の図面を参照して進められる以下の実施形態の詳細な説明を読めば明らかになるであろう。
【発明を実施するための最良の形態】
【００３６】
以下の説明は、重ね合わせ変換のために可逆重ね合わせ演算子を利用する、ディジタルメディア圧縮システムまたはコーデックに関するものである。例として、可逆重ね合わせ演算子を組み込んだ圧縮システムの一実施形態は、画像またはビデオ圧縮システムである。代替として、可逆重ね合わせ演算子は、他の２Ｄデータの圧縮システムまたはコーデックにも組み込まれ得る。可逆重ね合わせ演算子は、ディジタルメディア圧縮システムが、圧縮されるディジタルメディアデータを特定の符号化形式で符号化することを必要としない。
【００３７】
１．符号器／復号器
図４および５は、可逆重ね合わせ演算子を使用する重ね合わせ変換に基づく代表的な２次元（２Ｄ）データ符号器４００および復号器５００で用いられるプロセスの一般化された図である。これらの図には、２Ｄデータ符号器および復号器を組み込んだ圧縮システムにおけるこの可逆重ね合わせ演算子の使用および適用の一般化され、または単純化された実例が示されている。この可逆重ね合わせ演算子に基づく代替の符号器では、この代表的な符号器および復号器に示すものより多い、または少ないプロセスも２Ｄデータ圧縮に使用され得る。例えば、いくつかの符号器／復号器は、色変換、色形式、拡張可能符号化、損失なしの符号化、マクロブロックモードなども含み得る。圧縮システム（符号器および復号器）は、損失なしから損失ありまで変化する量子化パラメータに基づくものとすることのできる量子化に応じて、２Ｄデータの損失なしおよび／または損失あり圧縮を提供することができる。
【００３８】
２Ｄデータ符号器４００は、符号器に入力として提示される２Ｄデータ４１０の（典型的な入力のための）よりコンパクトな表現である圧縮ビットストリーム４２０を生成する。例えば、２Ｄデータ入力は、画像、ビデオシーケンスのフレーム、または２次元を持つ他のデータとすることができる。２Ｄデータ符号器は、入力データを、この代表的符号器では１６×１６画素のサイズであるタイル状のマクロブロックに分割する４３０。２Ｄデータ符号器は、さらに、各マクロブロックを、タイル状の４×４ブロックに分割する４３２。「順方向重ね合わせ」(forward overlap)演算子４４０が、ブロック間の各エッジに適用され、その後、各４×４ブロックがブロック変換４５０を使って変換される。このブロック変換４５０は、可逆のスケールなし(scale-free)２Ｄ変換とすることができる。代替として、離散コサイン変換または他のブロック変換も、本明細書で説明する可逆重ね合わせ演算子と共に使用され得る。この変換の後、各４×４変換ブロックのＤＣ係数４６０は、類似の処理連鎖（タイル状に分割、順方向重ね合わせ、次いで４×４ブロック変換）を施される。結果として生じるＤＣ変換係数およびＡＣ変換係数は量子化され４７０、エントロピ符号化され４８０、パケット化される４９０。
【００３９】
復号器は、逆のプロセスを実行する。復号器側では、変換係数ビットがそれぞれのパケットから抽出され５１０、そこから係数自体が復号化され５２０、逆量子化される５３０。ＤＣ係数５４０は、逆変換を適用することによって再生成され、ＤＣ係数の平面が、ＤＣブロックエッジにまたがって適用される適当な平滑化演算子を使って「逆に重ね合わせ」られる。その後、データ全体が４×４逆変換５５０をＤＣ係数に適用することによって再生成され、ＡＣ係数５４２がビットストリームから復号化される。最後に、結果として生じる画像平面中のブロックエッジが逆重ね合わせフィルタリングされる５６０。これは、復元された２Ｄデータ出力を生成する。
【００４０】
２．重ね合わせ演算子を使って実現される重ね合わせ変換
より一般的には、符号器４００（図４）の重ね合わせ演算子４４０およびブロック変換４５０は、図６に示すようにプリフィルタリング演算６１０と、それに続くブロックデータ変換６２０に分解され得る重ね合わせ変換６００の大きなクラスの一例である。図６に、そのような分解された重ね合わせ変換の一般化された例を示す。この図示の事例では、図３に示す６×４重ね合わせ変換３１０が、プリフィルタ演算６１０段とブロック変換６２０段に分解される。プリフィルタリング演算６１０およびブロック変換６２０は、データ点上に均一に交互配置される。この図示の６×４重ね合わせ変換６００の例では、各プリフィルタは、隣接するブロックにまたがるデータ点の長さ２の変換である。復号側では、ポストフィルタ６４０が、ブロック境界にまたがって、逆ブロック変換６３０の後に適用される。同様に、一般的なＫ×Ｎの場合では、プリフィルタは、ブロック境界に隣接する各ブロックの（Ｋ−Ｎ）／２データ点に適用される。
【００４１】
反転可能にするために、プリフィルタ６１０およびポストフィルタ６４０は、相互の逆である。しかしながら、損失なし重ね合わせ変換を実現するには、この条件は不十分である。これは、ブロック（コア）変換６２０が損失なしで実現されるのみならず、さらに、プリフィルタ６１０およびポストフィルタ６４０もまた損失なし変換であることを強いる。ＤＣＴは、特に、はしご型、格子またはリフティングベースの方法を使って、損失なしで実現され得る（例えば、非特許文献１１および１２参照）。また、可逆スケールなし２次元変換についても知られている。また、１次元におけるＤＣＴへのリフティングベースの可逆近似も知られている（例えば、非特許文献１３参照）。
【００４２】
効率的な可逆性は、さらに、両ステップ、すなわちプリ／ポストフィルタとブロック変換が単位行列式であることも必要とする。
【００４３】
３．可逆重ね合わせ演算子
符号器４００／復号器５００（図４および５）がそれに基づく損失なし重ね合わせ変換６００のプリフィルタ６１０（図６）として使用するための効率的可逆重ね合わせ演算子は、図７に示す構造７００に分解される線形位相プリフィルタとして実現され得る。また、このプリフィルタの逆（すなわち、ポストフィルタ６４０）も、異なる係数を伴うが、同じ構造を持つ。
【００４４】
この線形位相フィルタ構造７００は、その入力および出力における交差アダマールネットワーク(cross-over Hadamard network)７１０を含めて、複数の直交する構成要素を持つ。図示のアダマールネットワーク７１０中の内部矢印は、この図において否定を表す。構造７００は、さらに、直交行列Ｕ１、Ｕ２、Ｖ１およびＶ２を含む。これらの構成要素は、格子／リフティングベースの方法を使用することによって、損失なしで実施され得る。
【００４５】
さらに、構造７００は、非ゼロのスケール係数(scale factor)ｓ１からｓＭを持つ。この単位行列式制約条件は、
【００４６】
【数２】
2006174487.tif 000004
【００４７】
を示唆する。すべてのスケール係数が±１であるとき、プリ／ポストフィルタは、その成分行列Ｕ１、Ｕ２、Ｖ１およびＶ２が損失なし格子／リフティングステップとして実施される損失なし変換として実現され得る。しかしながら、スケール係数がすべてが±１とは限らないとき、損失なしの実現は、以下でより詳細に論じるように対処される課題のままにとどまる。
【００４８】
この線形位相プリフィルタ構造７００を用いれば、損失なしプリ／ポストフィルタ対を実現する問題は、以下の３つのステップに還元される。
【００４９】
１．直交行列Ｕ１、Ｕ２，Ｖ１およびＶ２について、フィルタＦを以下の形に分解する(factorize)ステップ。
【００５０】
【数３】
2006174487.tif 000005
【００５１】
式中、Ｉは単位行列であり、
２．Ｕ１、Ｕ２、Ｖ１およびＶ２の損失なしの実現を導出するステップ。
【００５２】
３．スケーリング行列の損失なしの実現を導出するステップ。
【００５３】
ステップ１に関して、２点アダマール変換を定義する右辺の最初と最後の行列は、これらの段を単位行列式にするために、いくつかの項に因数１／２を組み込んでいる。残りは、それぞれがＦの線形次元(linear dimension)の半分の、２つのブロックを持つブロック対角形に再構成される。各ブロックの特異値分解またはＳＶＤは、直交行列Ｕ１、Ｕ２、Ｖ１およびＶ２、ならびにそのスケールを提供する。
【００５４】
成分行列の損失なしの実現は、ステップ２で、（例えば、非特許文献１１に）記載されている標準リフティングベースの技法を使って導出され得る。
【００５５】
ステップ３でのスケーリング行列の損失なしの実現は、以下のように対処される。簡単にするために、（ａ）損失なしであり、（ｂ）第１の構成要素にはｓ（０＜ｓ＜１）による、第２の構成要素には１／ｓによるスケーリングを実現する、ある２入力２出力構成要素を備えるものと仮定する（他の場合は、出力信号の一方または両方の符号を反転することによって獲得され得る）。言い換えると、
【００５６】
【数４】
2006174487.tif 000006
【００５７】
によって与えられる入力／出力関係を持つ。
【００５８】
式（２）における変換行列の行列式はｓ／ｓ＝１である。この行列は、図８および９に示す４リフティングステップ手順８００または５リフティングステップ手順９００で実現され得る。普通は、除算なしの整数実装形態を得るために、リフティングステップすべてを、ｘを入力とし、ｙを出力とし、ａ、ｂおよびｒを整数とし、ｒを丸め誤差制御に使用されるものとする、ｙ＝（ａ．ｘ＋ｒ）＞＞ｂの形で近似する。式（２）によって定義される変換を、本明細書では、単位行列式スケーリング変換と呼び、スケーリング変換と略す。
【００５９】
興味深いことに、スケーリング変換は、以下で定義するように、せん断変形演算(shearoperation)と密接に関連している。
【００６０】
【数５】
2006174487.tif 000007
【００６１】
ａ２−ｂ２＝１（ａ＞０，ｂ＝０）という制約条件の下、せん断変形演算は単位行列を持ち、３つのリフティングステップを用いて実現され得る。
【００６２】
【数６】
2006174487.tif 000008
【００６３】
したがって、
【００６４】
【数７】
2006174487.tif 000009
【００６５】
である。
【００６６】
ここで、せん断変形行列を間に挟む行列中のスケーリング係数１／２および２は、せん断変形リフティングステップに分配され、最初の行列の最後のリフティングステップは最初のせん断変形リフティングステップと組み合わされ、最後の行列の最初のリフティングステップは最初のせん断変形リフティングステップと組み合わされる。図９に示すスケーリング変換の手順９００としての５ステップ実現は、式（５）に基づくものである。可能な場合には、式（１）の３グループ、すなわち、アダマールネットワーク、直交行列、およびスケーリング演算の間で逆演算を相殺することによってこの構造の単純化が可能となり得る（これらは、結果として、アダマール演算およびせん断変形演算に分解され得る）。
【００６７】
より具体的には、手順８００の損失なしスケーリングの４リフティングステップ実現の実際の変換行列は、
【００６８】
【数８】
2006174487.tif 000010
【００６９】
であり、式中、ｃ２＝１−ｓ２である。他方、手順９００の５リフティングステップ実現の実際の変換行列は、
【００７０】
【数９】
2006174487.tif 000011
【００７１】
であり、式中、ｃ２＝１−ｓ２である。
【００７２】
図８に示すスケーリング手順８００は図９に示すものより１つ少ないリフティングステップを持つが、後者の手順９００は、前者の４つとは対照的に、３つの非自明(non-trivial)なリフティングステップだけしか持たない。前段で述べた理由により、図９の最初または最後の自明のリフティングステップは、一定の条件（例えば、Ｕ１、Ｕ２およびＶ１が単位行列であるときなど）の下で、前の、または後の変換ステップと（例えば、図７のどちらかの端のアダマールネットワーク７１０などと）マージされ得る。
【００７３】
スケーリング手順は、より大きい行列に容易に拡張され得る。これを図１０に示す。図１０では、Ｍ個のおそらく異なるスケール係数ｓ１からｓＭが、スケーリング変換のカスケード１０００としてＭ個のデータパスに適用される。これを可逆に達成するためには、一般に、Ｍ−１回の可逆スケーリング変換が必要とされる。
【００７４】
１つの役に立つ特殊な例が、Ｍ個のスケール係数ｓ１からｓＭが、（ｓ，１／ｓ）の形のＭ／２グループにグループ化され得る場合である。この場合には、Ｍ／２回の可逆スケーリング変換だけでよい。一例が、ｓ１＝ｓ２＝．．．＝ｓＭ／２＝ｓおよびｓＭ／２＋１＝ｓＭ／２＋２＝．．．＝ｓＭ＝１／ｓの場合である。好ましいグループ化のやり方は、中心軸を挟んで対象性を維持するものであり、言い換えると、各グループが、係数ｓｉおよびｓＭ＋１−ｉをスケーリングする。Ｍが奇数である場合、グループ化されない１つのスケール係数は１であり、軸に沿ったデータパスに対応する。
【００７５】
プリ／ポストフィルタが信号の外側に延在する必要のある信号境界上における１つの解決法は、信号を対称的に延長し、次いで、プリ／ポストフィルタを適用するものである。これは、一般に、スケーリングのため、損失なし演算ではない。別の解決法は、境界上におけるプリ／ポストフィルタリングをスキップするものである。これら２つの解決法の間には、（例えば、損失ありの画像／ビデオ圧縮に使用される場合）ＲＤ性能および知覚的品質の点で目立った差異はない。
【００７６】
次に図１１を見ると、次いで、所望のＲＤ効率のよい（すなわち単位行列式の）特性を持つ可逆重ね合わせ演算子が、可逆単位行列式アダマールネットワーク７１０、（成分行列Ｕ１、Ｕ２、Ｖ１およびＶ２での）可逆直交回転１１１０、および（リフティングステップ手順８００、９００またはカスケード１１００などを使った）可逆単位行列式スケーリング１１２０を含む線形位相プリフィルタ構造７００（図７）として実現される。ポストフィルタはプリフィルタに類似し、逆の順序で逆のリフティングステップを用いてではあるが、同じ構成を使って構築される。これは図７に示されており、図中、ブロック中のデータ値Ｍの数は、一般に、任意の自然数である。図は偶数Ｍの場合についてであるが、中央データ値の「１点アダマール」変換がそれ自体であることに留意すれば、奇数値も可能である。この手順は、より高次元のデータに一般化され得る。
【００７７】
要約すると、可逆重ね合わせ演算子の動作は、図１２に示される。第１のステップ１２１０で、入力２次元ディジタルメディアデータが（図４の符号器４００でも示すように）タイル状のブロックに分割される。ステップ１２２０で、可逆重ね合わせ演算子は、アダマールネットワーク７１０を隣接するタイルにまたがって適用する。次いで、ステップ１２３０で、この演算子は、可逆回転を和と差に適用し、その後に、ステップ１２４０の可逆スケーリング演算子が続く。この後に、別の可逆ブロック回転（ステップ１２５０）、可逆逆アダマールネットワーク（ステップ１２６０）が続く。
【００７８】
次に、図１３を参照すると、可逆ブロック回転およびスケーリング演算子の行列表現は、例えば、式（１）に示す演算を使用する所望の重ね合わせ演算子に依存する。図１３には、その前に可逆ブロック変換（この場合は４点アダマール変換）が行われる、図７および図１１に示す構造７００を備えるポストフィルタの一例が示されている。このポストフィルタの伝達関数は、
【００７９】
【数１０】
2006174487.tif 000012
【００８０】
である。
【００８１】
アダマールの低域成分は、図１４のグラフに示すインパルス応答を生み出す。
【００８２】
４．コンピューティング環境
可逆重ね合わせ演算子を使用する重ね合わせ変換に基づく前述のコーデックは、特に、コンピュータ、画像／ビデオ記録、送信および受信装置、携帯用ビデオプレーヤ、テレビ会議などを含む、ディジタルメディア信号処理が行われる様々な装置のいずれかで実行され得る。このディジタルメディア符号化技法は、図１５に示すようなコンピュータまたは他のコンピューティング環境内で、ディジタルメディア処理ソフトウェアとしてのみならず、ハードウェア回路としても実装され得る。
【００８３】
図１５には、前述の実施形態が実施され得る適当なコンピューティング環境（１５００）の一般的な例が示されている。コンピューティング環境（１５００）は、本発明の用途または機能の範囲に関するどんな限定を示唆するためのものでもない。というのは、本発明は、多種多様な汎用または専用コンピューティング環境で実施され得るからである。
【００８４】
図１５を参照すると、コンピューティング環境（１５００）は、少なくとも１つの処理装置（１５１０）およびメモリ（１５２０）を含む。図１５では、この最も基本的な構成（１５３０）が破線内に含まれる。処理装置（１５１０）は、コンピュータ実行可能命令を実行し、実プロセッサとすることも、仮想プロセッサとすることもできる。多重処理システムにおいては、処理能力を増大させるために、複数の処理装置がコンピュータ実行可能命令を実行する。メモリ（１５２０）は、揮発性メモリ（レジスタ、キャッシュ、ＲＡＭなど）、不揮発性メモリ（ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリなど）、またはこれら２つの何らかの組み合わせとすることができる。メモリ（１５２０）は、前述の符号器／復号器および変換を実施するソフトウェア（１５８０）を格納する。
【００８５】
コンピューティング環境は、追加の機構を備え得る。例えば、コンピューティング環境（１５００）は、記憶（１５４０）、１つまたは複数の入力装置（１５５０）、１つまたは複数の出力装置（１５６０）、および１つまたは複数の通信接続（１５７０）を含む。バス、コントローラ、ネットワークなどの相互接続機構（図示せず）が、コンピューティング環境（１５００）の構成要素を相互接続する。通常は、オペレーティングシステムソフトウェア（図示せず）が、コンピューティング環境（１５００）で実行される他のソフトウェアのための動作環境を提供し、コンピューティング環境（１５００）の構成要素のアクティビティを調整する。
【００８６】
記憶（１５４０）は、着脱式でも固定式でもよく、これには、磁気ディスク、磁気テープまたはカセット、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、ＤＶＤ、または情報を格納するのに使用され、コンピューティング環境（１５００）内でアクセスされ得る他の任意の媒体が含まれる。記憶（１５４０）は、可逆重ね合わせ演算子を使用する重ね合わせ変換に基づくコーデックを実施するソフトウェア（１５８０）の命令を格納する。
【００８７】
入力装置（１５５０）は、キーボード、マウス、ペン、トラックボールなどのタッチ入力装置、音声入力装置、スキャン装置、またはコンピューティング環境（１５００）への入力を提供する別の装置とすることができる。オーディオでは、入力装置（１５５０）は、アナログまたはディジタル形式でオーディオ入力を受け入れるサウンドカードまたは類似の装置、あるいはコンピューティング環境にオーディオサンプルを提供するＣＤ−ＲＯＭリーダとすることができる。出力装置（１５６０）は、ディスプレイ、プリンタ、スピーカ、ＣＤライタ、またはコンピューティング環境（１５００）からの出力を提供する別の装置とすることができる。
【００８８】
通信接続（１５７０）は、通信媒体を介した別のコンピューティングエンティティへの通信を可能にする。通信媒体は、コンピュータ実行可能命令、圧縮オーディオまたはビデオ情報、その他のデータなどの情報を変調データ信号として伝達する。変調データ信号とは、その特性の１つまたは複数が、その信号に情報を符号化するような方式で設定または変更されている信号である。例をあげると、それだけに限らないが、通信媒体には、電気、光、ＲＦ、赤外線、音響またはその他の搬送波を用いて実施される有線または無線技法が含まれる。
【００８９】
本明細書のディジタルメディア処理技法は、コンピュータ可読媒体の一般的状況で説明され得る。コンピュータ可読媒体は、コンピューティング環境内でアクセスされ得る任意の利用可能な媒体である。例をあげると、それだけに限らないが、コンピューティング環境（１５００）で、コンピュータ可読媒体には、メモリ（１５２０）、記憶（１５４０）、通信媒体、およびそれらのいずれかの組み合わせが含まれる。
【００９０】
本明細書のディジタルメディア処理技法は、コンピューティング環境においてターゲット実／仮想プロセッサ上で実行される、プログラムモジュールに含まれるものなどのコンピュータ実行可能命令の一般的状況で説明され得る。一般に、プログラムモジュールには、個々のタスクを実行し、または個々の抽象データ型を実施する、ルーチン、プログラム、ライブラリ、オブジェクト、クラス、コンポーネント、データ構造などが含まれる。プログラムモジュールの機能は、様々な実施形態において所望に応じて組み合わされ、またはプログラムモジュール間で分割され得る。プログラムモジュールのコンピュータ実行可能命令は、ローカルまたは分散コンピューティング環境内で実行され得る。
【００９１】
表現のために、詳細な説明では、「決定する」、「生成する」、「調整する」、および「適用する」のような用語を使ってコンピューティング環境でのコンピュータ動作を説明している。これらの用語は、コンピュータによって実行される動作の高度な抽象化であり、人間によって行われる行為と混同すべきではない。これらの用語に対応する実際のコンピュータ動作は、実装に応じて異なる。
【００９２】
５．可逆重ね合わせ演算子の変形および拡張
前述の可逆重ね合わせ演算子の様々な変更および拡張が行われ得る。前述の説明は１次元データでのものであるが、同じ手順は、複数のデータ次元に分離可能に、または分離不能に適用され得る。
【００９３】
前述の可逆重ね合わせ演算子実装における直交回転は、その近似によって、または直交しないことのある他の変換によって置換され得る。
【００９４】
さらに、前述の説明では入力データの損失なし回復に主要な焦点が置かれているが、同じ変換は、損失ありデータ圧縮にも使用され得る。この場合、損失は、量子化プロセスにおいて、あるいはプリフィルタまたはポストフィルタの限られた精度／近似実装が原因で、あるいは他の誤り、もしくは複数の要因の組み合わせが原因で発生し得る。
【００９５】
本明細書で述べた可逆重ね合わせ演算子は、データ圧縮以外の領域にも適用され得る。可逆重ね合わせ演算子を使用する重ね合わせ変換は、それ自体、拡張的であり得る。
【００９６】
可逆重ね合わせ演算子は、適切に変更された形で、マルチレートフィルタバンク、ウェーブレット、２を上回るブロック幅にまたがる（Ｋ＞２Ｎ）サポートを有する重ね合わせ変換を実施するために適用され得る。
【００９７】
可逆重ね合わせ演算子は、重ね合わせフィルタの大きさおよび形状がデータの空間的大きさによって異なり得る、空間的に変化する方式で適用され得る。
【００９８】
本発明の原理が適用され得る多くの可能な実施形態を考慮して、発明者らは、以下の特許請求の範囲およびその均等物の範囲および精神の内に含まれ得るそのようなすべての実施形態を本発明として特許請求するものである。
【図面の簡単な説明】
【００９９】
【図１】従来技術における従来方式のブロック変換ベースのコーデックを示すブロック図である。
【図２】従来技術における、図１のブロック変換ベースのコーデックと組み合わせた前処理および後処理演算として実装される空間領域重ね合わせ変換を示すブロック図である。
【図３】１次元データの重ね合わせ変換と逆重ね合わせ変換の対を示すブロック図である。
【図４】可逆重ね合わせ演算子を利用する重ね合わせ変換に基づく符号器を示す流れ図である。
【図５】重ね合わせ変換に基づく復号器を示す流れ図である。
【図６】プリフィルタリングおよびポストフィルタリング演算（または可逆重ね合わせ演算子）をブロック変換と併用する１次元データの重ね合わせ変換と逆重ね合わせ変換の対を示すブロック図である。
【図７】図６の重ね合わせ変換で可逆重ね合わせ演算子として使用するための線形位相プリ（またはポスト）フィルタの構造を示すシグナルフローグラフである。
【図８】可逆重ね合わせ演算子で使用するための４つのリフティングステップとしての損失なしスケーリングを示すシグナルフローグラフである。
【図９】可逆重ね合わせ演算子で使用するための５つのリフティングステップとしての損失なしスケーリングを示すシグナルフローグラフである。
【図１０】損失なし単位行列式スケーリングを実現するためにより大きい次元の行列に適用される２点スケーリングのカスケードを示すシグナルフローグラフである。
【図１１】図７に示す構造を持ち、図１０の損失なし単位行列式スケーリングを使用する可逆重ね合わせ演算子（またはプリ／ポストフィルタ）を示すシグナルフローグラフである。
【図１２】図１１の可逆重ね合わせ演算子の動作を示す流れ図である。
【図１３】図１１の可逆重ね合わせ演算子を使用する可逆重ね合わせ変換実装形態の一例を示すシグナルフローグラフである。
【図１４】図１３の例示的重ね合わせ変換のＤＣ係数を示すインパルス応答グラフである。
【図１５】図４および５の改善された空間領域重ね合わせ変換を用いたブロック変換ベースのコーデックを実装するのに適したコンピューティング環境を示すブロック図である。
【符号の説明】
【０１００】
７１０  可逆単位行列式アダマール
１１１０  可逆直交回転
１１２０  可逆単位行列式スケーリング
【図１】
2006174487.tif 000022
【図２】
2006174487.tif 000023
【図３】
2006174487.tif 000024
【図４】
2006174487.tif 000025
【図５】
2006174487.tif 000026
【図６】
2006174487.tif 000027
【図７】
2006174487.tif 000028
【図８】
2006174487.tif 000029
【図９】
2006174487.tif 000030
【図１０】
2006174487.tif 000031
【図１１】
2006174487.tif 000032
【図１２】
2006174487.tif 000033
【図１３】
2006174487.tif 000034
【図１４】
2006174487.tif 000035
【図１５】
2006174487.tif 000036