階層的可逆圧縮
【解決手段】
データ圧縮のための方法が提供される。データ圧縮方法は、データのスクエアをデータのタイルへと変形する。データのタイルは次いでデータの複数のクワッドに分割され、データの複数のクワッドは、表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換される。データの新たなタイルが次いで複数の表現要素を伴って形成され、そしてプロセスは単一の表現要素が残るまで繰り返される。単一の表現要素は次いで制御ワード及び対応するデルタ要素と共に出力ストリーム内に埋め込まれる。ビットストリームが構文解析されたならば、データの復元は符号化に対して対称である。
データ圧縮のための方法が提供される。データ圧縮方法は、データのスクエアをデータのタイルへと変形する。データのタイルは次いでデータの複数のクワッドに分割され、データの複数のクワッドは、表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換される。データの新たなタイルが次いで複数の表現要素を伴って形成され、そしてプロセスは単一の表現要素が残るまで繰り返される。単一の表現要素は次いで制御ワード及び対応するデルタ要素と共に出力ストリーム内に埋め込まれる。ビットストリームが構文解析されたならば、データの復元は符号化に対して対称である。
【発明の詳細な説明】
【技術分野】
【0001】
本発明はデータ圧縮に関する。より特定的には、本発明はハードウエア実装に適する可逆データ圧縮に関する。
【背景技術】
【0002】
データ圧縮は、より少ないビットを用いてデータが記憶されるようにデータを変換するプロセスである。データ圧縮には、非可逆(lossy)及び可逆(lossless)の2種類がある。非可逆データ圧縮は、より大きな程度でデータを圧縮するが、プロセスの最中にデータを喪失する。従って、復元(decompression)に際しては、データは、その正確な複製であるよりはむしろその元の形態の近似である。可逆データ圧縮は、より小さな程度でデータを圧縮するが、プロセスの最中にいかなるデータも喪失しない。従って、復元に際しては、データは圧縮前にあった通りに正確に再構築される。データ圧縮の目的は、伝送に必要な帯域幅及び/又は記憶に必要なメモリの量を低減することである。
【0003】
一般的な可逆圧縮技術の例としてハフマン符号化(Huffman coding)がある。ハフマン符号化はデータ項目の出現頻度に基いている。この技術は、より低い数(lower number)のビットを用いて、より頻繁に出現するデータを符号化する。残念なことに、ハフマン符号化の限界は、ハフマン符号化が固定されたシーケンス長手続きを有しておりまたシーケンス長を超えるデータにおける冗長性を圧縮することができないところにある。結果として、ハフマン符号化は複雑であり、また大量のメモリが有効にされることを必要とする。ハフマン符号化は、ファイルの任意の部分が抽出され得る前に全ファイルの解析を実行することを伴う。また、ハフマン技術は本質的に非対称であり、このことは復号プロセスが符号化プロセスよりも低速であることを意味している。そのような特性は、コンピュータが一般に単一のクロックサイクル上で概ね同じ量のデータを読み出し且つ書き込むように設計されていることを理由として、特定のハードウエア実装のためには受け入れられない。
【0004】
別の一般的な可逆技術は、レンペル・ジブ・ウェルチ法(Lempel-Ziv-Welch method)(LZW)である。LZWは、圧縮されているデータファイル内に以前に見えたストリングス(previously seen strings)の辞書を自動的に作成する。辞書は256エントリで動作開始し、1つのエントリは各可能な文字(character)のためにある。辞書内に未だないストリングが見つかるたびに、当該ストリングで構成されるもっと長いストリングが付け加えられる。出力は辞書内への整数指標(integer indices)で構成される。残念なことに、LZWにはそれが作成するストリングテーブルに起因する弱点がある。辞書は短時間の間に極めて大量に獲得することができる。加えて、必要とされるメモリの量は全ストリングの全長に依存するから、必要とされる記憶量が不確定である。また、ハフマン符号化と同様に、ファイルの任意の部分が圧縮され且つ/又は復元される前に全ファイルが符号化され且つ/又は復号される必要がある。更に、全体的プロセスは本質的に非対称であり、復元より圧縮の方がかなり長い時間を要する。
【0005】
上述の圧縮技術によって課せられる制限以外に、別の主要な問題は、データの異なるフォーマットに対する統一された圧縮方法がないことである。例えば、複数の画素からなるコンピュータグラフィックは、Zバッファリングを用いて表現され得る。Zバッファリングは、画素深さを試験することと、現在の位置のZ座標をZバッファに記憶されているデータと比較することとによって機能する。Zバッファは、各画素の最後の位置に関する情報を記憶している。観察者により近い位置における画素が、表示されることになる画素である。複数の画素からなるグラフィックスを表現するために用いられる他の一般的なデータフォーマットは、色バッファリング及び正規図(normal maps)である。現在のところ、正規図データのための可逆圧縮技術はなく、また色バッファリングデータは、ソフトウエア指向の独特な圧縮方法を必要としている。
【発明の概要】
【発明が解決しようとする課題】
【0006】
本質的に対称であり、それによりハードウエア実装に適しているデータ圧縮/復元方法が必要とされている。また、正規図データを含む幾つかの異なるデータフォーマットを圧縮し且つ復元することが可能なデータ圧縮/復元方法が必要とされている。更に、グラフィックに係る種々のハードウエアデバイスに適応可能なデータ圧縮/復元方法が必要とされている。
【課題を解決するための手段】
【0007】
本発明の1つの側面においては、データを主アレイへと配置するステップと、主アレイを複数の主サブアレイに分割するステップと、複数の圧縮されたサブアレイが形成されるように、各主サブアレイを圧縮されたサブアレイへと圧縮するステップと、圧縮されたサブアレイを補助アレイへと配置するステップと、分割するステップ、圧縮するステップ、及び配置するステップを単一のサブアレイが残るまで繰り返すステップと、をコンピュータが実行することを備えた階層的データ圧縮方法が提供され、ここでは、補助アレイはこれらのステップの繰り返しのための主アレイになる。圧縮されたサブアレイからのデータは出力ストリーム内に埋め込まれ得る。
【0008】
本発明の別の側面においては、データのスクエアを提供するステップと、データのスクエアをデータのタイルへと変形するステップと、左上画素、右上画素、左下画素、及び右下画素を各クワッドが有するデータの複数のクワッドにデータのタイルを分割するステップと、各クワッドを表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換するステップと、表現要素を伴うデータの新たなタイルを形成するステップと、データの新たなタイルが分割するステップ、変換するステップ、及び形成するステップの繰り返しのためのデータのタイルになるように、分割すること、変換すること、及び形成することを単一の表現要素が残るまで繰り返すステップと、単一の表現要素、制御ワード、及びデルタ要素を出力ストリーム内に埋め込むステップと、をコンピュータが実行することを備えたデータ圧縮方法が提供される。
【0009】
本発明の更に別の側面においては、機械によって可読なプログラム記憶デバイスが提供される。デバイスは、データ圧縮方法を実行することを機械によって実行可能な命令のプログラムを有形的に実施し、方法は、データのスクエアを提供することと、データのスクエアをデータのタイルへと変形することと、左上画素、右上画素、左下画素、及び右下画素を各クワッドが有するデータの複数のクワッドにデータのタイルを分割することと、各クワッドを表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換することと、表現要素を伴うデータの新たなタイルを形成することと、データの新たなタイルが分割するステップ、変換するステップ、及び形成するステップの繰り返しに対するデータのタイルになるように、分割すること、変換すること、及び形成することを単一の表現要素が残るまで繰り返すことと、単一の表現要素、制御ワード、及びデルタ要素を出力ストリーム内に埋め込むことと、を備えている。
【0010】
本発明は、上述の及び下記のように構成される他の実施形態の他、他の特徴及び代替案を伴う他の実施形態をも包含する。
【図面の簡単な説明】
【0011】
本発明は、添付の図面と併せて以下の詳細な説明によって容易に理解されるであろう。この説明を容易にするために、同様の参照番号は同様の要素を指定する。
【0012】
【図1A】図1Aは本発明の実施形態に従い画素ビットを含むデータの2次元表面を示す図(その1)である。
【図1B】図1Bは本発明の実施形態に従い画素ビットを含むデータの2次元表面を示す図(その2)である。
【図1C】図1Cは本発明の実施形態に従い画素ビットを含むデータの2次元表面を示す図(その3)である。
【図2A】図2Aは本発明の実施形態に従うスクエアからタイルへの変形を示す図(その1)である。
【図2B】図2Bは本発明の実施形態に従うスクエアからタイルへの変形を示す図(その2)である。
【図3A】図3Aは本発明の実施形態に従うタイルの分割、クワッドの変換、及び新たなタイルの形成を示す図(その1)である。
【図3B】図3Bは本発明の実施形態に従うタイルの分割、クワッドの変換、及び新たなタイルの形成を示す図(その2)である。
【図3C】図3Cは本発明の実施形態に従うタイルの分割、クワッドの変換、及び新たなタイルの形成を示す図(その3)である。
【図3D】図3Dは本発明の実施形態に従うタイルの分割、クワッドの変換、及び新たなタイルの形成を示す図(その4)である。
【図4】図4は本発明の実施形態に従うデータのタイルの階層を示す図である。
【図5】図5は本発明の実施形態に従うグラフィックに係る形態におけるデータ圧縮方法を示す図である。
【図6】図6は本発明の実施形態に従い階層的データを符号化すると共に出力ストリーム内に埋め込むために好ましく用いられるサブタイルパターンを示す図である。
【図7】図7は本発明の実施形態に従う階層的データのビット割り付けされた出力ストリームを示す図である。
【図8】図8は本発明の実施形態に従いグラフィックに係る形態におけるビット割り付けを示す図である。
【発明を実施するための形態】
【0013】
階層的可逆データ圧縮方法のための発明が開示される。本発明の実施形態の完全な理解をもたらすために、多くの特定の詳細が記載されている。しかし、本発明の実施形態は他の特定の詳細でも実施され得ることが当業者によって理解されるはずである。
【0014】
1つの実施形態においては、データの2次元表面が概念的にはデータの複数のスクエア(squares of data)に分割される。物理的なスクエアはないことが理解されるであろう。しかし、次元(長さ及び幅)及び表面を伴う物理的実体としてスクエアをみなすことは、本発明のための概念を理解するのに役立ち得る。データの2次元表面は、グラフィックに係る画像を表現する複数の画素ビットを含む。データの2次元表面は、16×16スクエアのサイズであるデータのスクエアに分割される。代替的な実施形態においては、データの2次元表面は、望ましい圧縮又は基本的なデータフォーマットに応じて、より大きな又はより小さな任意の数のスクエアに分割され得る。例えば、データの2次元表面は画素データの8×8スクエアに分割され得る。
【0015】
データの各スクエアは次いでデータのタイル(a tile of data)に変形される(transformed)。変形は、ハードウエア実装に適する整数加算演算又は整数減算演算を用いて行われる。データのスクエアをデータのタイルに変形するために用いられる技術は、グラフィックに係る画像を表現するのに用いられるデータフォーマットに依存し得る。例えばデータフォーマットがZバッファリングである場合には、データのタイルの第2列はデータのスクエアの第2列から第1列を減じたものに等しくセットされ、データのタイルの第3列はデータのスクエアの第3列からデータのスクエアの第2列を減じたものに等しくセットされ、データのタイルの第4列はデータのスクエアの第4列からデータのスクエアの第3列を減じたものに等しくセットされ、そして当該パターンは、各データ値が隣接データ値及びデータのタイル内に記憶される差を減ぜられるまで繰り返す。
【0016】
代替的な実施形態においては、異なる技術を用いて異なるデータフォーマットがタイルに変形され得る。例えば、各画素に対して色バッファデータのスクエアを変形するために、データのスクエアにおける第1チャネルは、データのスクエアにおける第2チャネルを減ぜられる。結果としてもたらされる値は、データのタイルにおける第1チャネル内に記憶される。データのスクエアにおける第2チャネルは、データのタイルにおける第2チャネル内に記憶される。データのスクエアにおける第3チャネルは、データのスクエアにおける第1チャネルを減ぜられ、そして当該値はデータのタイルにおける第3チャネル内に記憶される。当該パターンは、非相関変形が各画素に実行されるまで繰り返す。
【0017】
別の実施形態においては、各画素に対して正規図データを変形するために、データのスクエアにおける第1チャネルが落とされ、そしてその符号を表しているビットがデータのタイルにおける第1チャネル内に記憶される。データのスクエアにおける第2及び第3チャネルは、データのタイルにおけるそれぞれ第2及び第3チャネル内に記憶される。
【0018】
データのスクエアがデータのタイルに変形された後、タイルはクワッド(quads)に分割される。クワッドは、好ましくは左上画素、右上画素、左下画素、及び右下画素を有する2×2である。タイルがクワッドに分割されると、クワッドは表現要素(representative element)、3つのデルタ要素、及び制御ワードに変換される(converted)。変換は、好ましくはハードウエア実装に適した整数加算演算又は整数減算演算を含む。データフォーマットに応じて異なる技術がデータのクワッドを表現要素、3つのデルタ要素、及び制御ワードに変換するために用いられ得る。異なる変換技術の例が後で更に詳細に論じられることになる。
【0019】
クワッドが変換され終わった後に、結果としてもたらされる表現要素を伴う新たなタイルが形成される。新たなタイルは次いでクワッドに分割され、そしてそれらのクワッドは表現要素、3つのデルタ、及び制御ワードに変換される。同様に、結果としてもたらされる表現要素は別の新たなタイルを形成し、そして当該タイルはクワッドに分割され、分割されたクワッドは表現要素、3つのデルタ要素、及び制御ワードに変換される。当該パターンは単一の表現要素が残るまで繰り返す。結果はデータの階層であり、その最上層は単一の表現要素であり、またその最下層は、データの変形されたスクエアを表しているデータの変換されたクワッドである。最下層から最上層へ行き来すると、階層の各レベルはより小さいクワッドの4倍を有している。尚、この設計は、データの多重スクエアがグラフィックに係る画像を表現している場合に、全体プロセスが容易に並列化されることを可能にする。
【0020】
単一の表現要素が残ったら、圧縮されたデータのしっかりとアラインされた画素ストリーム内へ画素を埋め込むプロセスが開始する。好ましくは制御情報が最初にストリーム内へ埋め込まれ、これはデータフォーマットに応じて僅かに変化し得る。例えば、Zバッファ又は正規図データが用いられる場合には、制御情報は各画素のための符号の256画素マップを含み得る。次いで単一の表現要素が、適切な数の画素と共に出力ストリーム内へ埋め込まれる。
【0021】
階層内のデータのタイルの各々を4つの等しいスクエアに分割することは、データの4つのサブタイルを生成する。例えば、データのタイルは、最上位左サブタイルがサブタイル0、最上位右サブタイルがサブタイル1、最下位左サブタイルがサブタイル2、そして最下位右サブタイルがサブタイル3であるように分割されるであろう。例えばタイルが16×16である場合には、各サブタイルは8×8であろう。単一の表現要素の埋め込みに続いて、好ましくは、オフセットから構成されるサブタイルのディレクトリが埋め込まれる。例えばデータのタイルが16×16である場合、サブタイル1のためのオフセットはサブタイルゼロ([0,7][0,7])からの([8,15][0,7])であろう一方で、サブタイル2のためのオフセットはサブタイル1の開始からの([0,7][8,15])であろうし、そしてサブタイル3はサブタイル2からの([8,15][8,15])であろう。
【0022】
単一の表現要素及びサブタイルの好ましいディレクトリが出力ストリーム内へ埋め込まれた後、クワッドの各々からのデルタ要素が符号化される。符号化は階層の最上層で開始し、そして最下層へと進む。クワッドはそれらの対応する制御ワードに従って符号化される。符号化は好ましくはサブタイルパターンに追随する。例えば、最上層から最下層までのサブタイル0に対する全てのデルタが最初に符号化されるであろうし、最上層から最下層までのサブタイル1のデルタがそれに続くであろう。次いで、サブタイル2のデルタが最上層から最下層まで符号化されるであろうし、サブタイル3のデルタの符号化がそれに続くであろう。尚、階層の低い方のレベルが高い方のレベルから完全に復号され得る場合には、低い方のレベルの符号化が回避されるので、圧縮が増大される。
【0023】
符号化された画素は、次いで好ましくはサブタイルパターンに追随する出力ストリーム内に埋め込まれる。符号化された画素の埋め込みは、好ましくはサブタイル0に対して最上層クワッドを表している画素で開始することになる。次に、サブタイル0に対して階層の低い方のレベルで符号化された画素が、最上層から最下層まで出力ストリーム内に埋め込まれる。次いで、サブタイル1に対して最上層クワッドを表している画素が埋め込まれることになる。次に、好ましくはサブタイル1のためのディレクトリが出力ストリーム内に埋め込まれる。例えばデータのスクエアが16×16である場合には、サブタイル1のためのディレクトリはオフセット([4,7][0,3])であろう。ディレクトリに続いて、サブタイル1に対して階層の低い方のレベルで符号化された画素が、次いで最上層から最下層まで出力ストリーム内に埋め込まれることになる。次に、サブタイル2に対して最上層クワッドを表している画素が埋め込まれることになる。次いで、好ましくはサブタイル2のためのディレクトリが出力ストリーム内に埋め込まれる。例えばデータのスクエアが16×16である場合には、サブタイル2のためのディレクトリはオフセット([0,3][4,7])であろう。ディレクトリに続いて、サブタイル2に対して階層の低い方のレベルで符号化された画素が、次いで最上層から最下層まで出力ストリーム内に埋め込まれることになる。次に、サブタイル3に対して最上層クワッドを表している画素が埋め込まれることになる。次いで、サブタイル3のためのディレクトリが出力ストリーム内に埋め込まれる。例えばデータのスクエアが16×16である場合には、サブタイル3のためのディレクトリはオフセット([4,7][4,7])であろう。ディレクトリに続いて、サブタイル3に対して階層の低い方のレベルで符号化された画素が、次いで最上層から最下層まで出力ストリーム内に埋め込まれることになる。
【0024】
前述したように、データフォーマットに応じて、データのクワッドを表現要素、3つのデルタ要素、及び制御ワードに変換するために種々の技術が用いられ得る。例えば色バッファ又は正規図データを変換するために、表現要素はクワッドの左上画素に等しくセットされる。第1のデルタ要素は左上画素を減ぜられた右上画素に等しい。第2のデルタ要素は左上画素を減ぜられた左下画素に等しい。第3のデルタ要素は左下画素を減ぜられた右下画素に等しい。制御ワードはデルタ要素の間での相関に従ってセットされる。全てのデルタ要素がゼロに等しい場合には、制御ワードはゼロにセットされる。これは、画素割り付けの間、画素割り付け器(pixel allocator)がそのクワッドに対する画素の任意の更なる割り付けを中断するための信号である。デルタ要素がゼロに等しくない場合には、制御ワードは3つのデルタのうちの最大絶対値に応じてセットされる。デルタのうちの最大絶対値が1以下である場合には、制御ワードは1にセットされる。デルタのうちの最大絶対値が3以下である場合には、制御ワードは2にセットされる。デルタのうちの最大絶対値が7以下である場合には、制御ワードは3にセットされる。デルタのうちの最大絶対値が7より大きい場合には、異なる戦略が採用される。デルタのうちの最大絶対値が7より大きいと仮定すると、左上画素、右上画素、左下画素、及び右下画素の平均が計算される。表現要素はクワッド画素の平均に等しくなるようにリセットされる。第1のデルタ要素は、平均を減ぜられた左上画素に等しくなるようにリセットされる。第2のデルタ要素は、平均を減ぜられた右上画素に等しくなるようにリセットされる。第3のデルタ要素は、平均を減ぜられた左下画素に等しくなるようにリセットされる。制御ワードは、リセットされたデルタ要素のうちの最大絶対値が7以下である場合には、4にセットされる。リセットされたデルタ要素のうちの最大絶対値が15以下である場合には、制御ワードは5にセットされる。
【0025】
リセットされたデルタ要素のうちの最大絶対値が15より大きい場合には、制御ワードは6にセットされ、そして表現要素及びデルタ要素は元のクワッド画素としてセットされる。従って、リセットされたデルタ要素のうちの最大絶対値が15より大きいと仮定すると、表現要素は左上画素に等しく、第1のデルタ要素は右上画素に等しく、第2のデルタ要素は左下画素に等しく、そして第3のデルタ要素は右下画素に等しい。
【0026】
デルタの符号化及び埋め込みは、データフォーマットに応じて異なり得る。好ましい実施形態によると、データがどのように符号化されるのかを定義する6ビットプレフィックス(prefix)がある。各バッファのために2ビットある。各2ビット制御ワードは00、01、10、又は11であり得る。
【0027】
【表1】
【0028】
1つの例においては、Zバッファデータが用いられ、そして制御ワードは2ビットである。制御ワードが「00」である場合、制御ワードのみが出力ストリーム内に埋め込まれ、そして他のデータは埋め込まれない。このことは大幅な圧縮を可能にし、この場合、データの変化はない。制御ワードが「01」である場合、制御ワードが埋め込まれ、そしてデルタがそれらの対応する画素値と共に埋め込まれる。最後に制御ワードが「11」である場合、制御ワードを表しているビットが埋め込まれ、そしてデルタは関連する事例(以下の表を参照)に従って符号化される。
【0029】
【表2】
【0030】
符号化は、幾つかのビットを定義している5ビットプレフィックスと符号ビットとを含む。事例が0、1、又は2である場合、単一の値がプレフィックスと共に出力ストリーム内に埋め込まれて、ビットの最大数が1であることを指定する。事例が3、4、又は5である場合、2つの値がプレフィックスと共に出力ストリーム内に埋め込まれて、それらのうちのビットの最大数が2であることを指定する。事例が6である場合、3つの値がプレフィックスと共に出力ストリーム内に埋め込まれて、それらのうちのビットの最大数が3であることを指定する。代替的な実施形態においては、デルタ要素は異なる技術を用いて符号化され得るし、また埋め込まれ得る。
【0031】
例えば色バッファ又は正規図データが用いられ且つ制御ワードが0である場合、制御ワードを表す3ビットが出力ストリーム内に埋め込まれ、そして他のデータは埋め込まれない。色に対しては3ビット制御ワードが用いられる。
【0032】
制御ワードが1である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、第1のデルタ要素を表す1ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次に、第2のデルタ要素を表す1ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次いで、第3のデルタ要素を表す1ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0033】
制御ワードが2である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、第1のデルタ要素を表す2ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次に、第2のデルタ要素を表す2ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次いで、第3のデルタ要素を表す2ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0034】
制御ワードが3である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、第1のデルタ要素を表す3ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次に、第2のデルタ要素を表す3ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次いで、第3のデルタ要素を表す3ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0035】
制御ワードが4である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、クワッドの平均を表す2ビットが埋め込まれた後に、平均の符号を表すビットが続く。次に、第1のデルタ要素を表す3ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次いで、第2のデルタ要素を表す3ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次に、第3のデルタ要素を表す3ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0036】
制御ワードが5である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、クワッドの平均を表す2ビットが埋め込まれた後に、平均の符号を表すビットが続く。次に、第1のデルタ要素を表す4ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次いで、第2のデルタ要素を表す4ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次に、第3のデルタ要素を表す4ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0037】
制御ワードが6である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、第1のデルタ要素を表す8ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次に、第2のデルタ要素を表す8ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次いで、第3のデルタ要素を表す8ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0038】
制御ワードが7である場合には、データは全部ゼロで埋められる。
【0039】
出力ストリームを再構築するために、ビットアラインされたストリーム(bit-aligned stream)を構文解析することによって復号プロセスが開始する。ビットアラインされたストリームが構文解析され終わると、逆変換及び変形(inverse conversions and transforms)が実行されてデータを再構築する。復号プロセスは符号化プロセスと完全に対称である。一旦データ階層の最上層レベルが復号されると、下層の方のレベルは、それらの各々に対するビットストリーム内に開始位置が設けられている場合には、並列的に復号され得る。サブタイルのための適切なオフセットのディレクトリが好ましくは出力ストリーム内に埋め込まれており、並列ビットストリーム復号を可能にしている。
【0040】
上述のステップは、同一の結果を達成するためのアレイの組み合わせにおける種々のデータフォーマットで実行され得る。特に、データフォーマットは、データの2次元表面として表現され得る任意の便利な且つ/又は既知のデータフォーマットであってよい。例えば、データフォーマットは、静止画、動画、テクスチャ(textures)を代表していてよく、そして浮動32及び/又は固定24フォーマットであってよい。また、データのスクエア及び/又はクワッドに実行される変形及び/又は変換は、同一の結果を達成するための任意の便利な且つ/又は既知の方法で行われ得る。例えば、データのスクエア及びクワッドは、加算され、減算され、乗算され、除算され、且つ/又は同一の結果を達成するための任意の他の方法で操作され得る。加えて、ビット割り付けは、任意の便利な且つ/又は既知の方法で実行され得る。典型的な追加の制御情報が追加されてよく、又は出力ストリームには制御情報が埋め込まれなくてよい。また、デルタは、処理の間に任意の便利な且つ/又は既知のタイミングで符号化され得る。デルタは、対応するクワッドが変換された後、又は階層の同様のレベルのクワッドが変換されてすぐに且つ/若しくはビット割り付けに先立つ任意の他のタイミングで、符号化され得る。更に、追加のディレクトリがビットストリーム内に含まれ得るし、又はディレクトリを除去して圧縮を増大してもよい。
【0041】
図1A〜1Cは、本発明の実施形態に従い画素を含むデータの2次元表面によって表されるグラフィックに係る画像を示している。図1Aにおいては、グラフィックに係る画像101が画面102上に表示されている。
【0042】
図1Bにおいては、グラフィックに係る画像101は、データの2次元表面103上の一連の画素104によって表されている。グラフィックに係る画像101の存在は一連の1によって表される一方で、グラフィックに係る画像101の不在は0によって表される。
【0043】
図1Cにおいては、階層的圧縮を用いて圧縮され得るデータの2次元表面103から、データの16×16スクエア105が分割されたものとなっている。データのスクエア105は、グラフィックに係る画像101の左上部分を表している。
【0044】
代替的な実施形態においては、データの2次元表面は、任意の数の画素幅と任意の数の画素高さであってよい。例えば、データの2次元表面は、4×4若しくは1280×1024又は任意の他の便利な若しくは既知の幅×高さ画素表示であってよい。また、データのスクエア105は、より大きく又はより小さくてよい。例えば、データのスクエア105は、データの2次元表面の8×8分割であってよい。更に、代替的な実施形態においては、データの追加的なスクエアがデータの2次元表面から分割されてよく、そして並列的に圧縮されてよい。
【0045】
図2A及び2Bは本発明の実施形態に従うスクエアからタイルへの変形を示している。図2Aにおいては、データの8×8スクエア201はA1〜H8の値を含む。データ203はZバッファフォーマットにある。
【0046】
図2Bにおいては、データのスクエア201は、全ての画素を隣接画素間の値の差で置換することによって、データのタイル202へと変形される。Zバッファに対する変形は、T[i][j]が(j,i)座標のタイル内の画素の座標を表し、S[i][j]が(j,i)座標のスクエア内の画素の座標を表し、Hがタイル高さを表し、そしてWがタイル幅を表す場合、各行に沿って左から右に水平に移動しながら次の式に追随し得る。
(i=0,…,H−1)に対して
(j=0,…,W−1)に対して
T[i][j]=S[i][j]−S[i][j−1]
また、第0列に沿って上から下に垂直に移動しながら次の式に追随する。
(i=1,…,H−1)に対して
T[i][0]=S[i][0]−S[i−1][0]
S[0][0]は一定であり、T[0][0]はT[0][1](即ち最も近い右の近隣)で置換される。従って、画素A2はA2−A1で置換される。画素A3はA3−A2で置換される。プロセスは、データ1の全スクエアが隣接画素間の値の差を含むデータ202のタイルへと変形されるまで継続する。
【0047】
代替的な実施形態においては、データのスクエアは、データフォーマットに応じて異なる技術を用いて変形され得る。例えば、データのスクエアが色バッファフォーマットである場合において、T[i][j][c]が(j,i)座標のタイル内の画素の座標及びその画素のチャネルcを表し、S[i][j][c]が(j,i)座標のスクエア内の画素の座標及びその画素のチャネルcを表し、Hがタイル高さを表し、そしてWがタイル幅を表すときには、変形は次の式に追随し得る。
(i=0,…,H−1)に対して
(j=0,…,W−1)に対して
T[i][j][0]=S[i][j][0]−S[i][j][1]
T[i][j][1]=S[i][j][1]
T[i][j][2]=S[i][j][2]−S[i][j][1]
従って、タイル画素毎の第0チャネルは、対応するスクエア画素の第0チャネルから対応するスクエア画素の第1チャネルを減じたものに等しい。タイル画素毎の第1チャネルは、対応するスクエア画素の第1チャネルに等しい。タイル画素毎の第2チャネルは、対応するスクエア画素の第2チャネルから対応するスクエア画素の第1チャネルを減じたものに等しい。各画素について非相関変形を実行することによって、色バッファデータのスクエアがデータのタイルへと変形される。
【0048】
代替的な実施形態の別の例では、データのスクエアが正規図フォーマットである場合において、T[i][j][c]が(j,i)座標のタイル内の画素の座標及びその画素のチャネルcを表し、S[i][j][c]が(j,i)座標のスクエア内の画素の座標及びその画素のチャネルcを表し、Hがタイル高さを表し、そしてWがタイル幅を表すときには、変形は次の式に追随し得る。
(i=0,…,H−1)に対して
(j=0,…,W−1)に対して
S[i][j][0]>0の場合にはT[i][j][0]=1;
それ以外の場合にはT[i][j][0]=0
T[i][j][1]=S[i][j][1]
T[i][j][2]=S[i][j][2]
従って、タイル画素毎の第0チャネルは、対応するスクエア画素の第0チャネル内に記憶されている値が正である場合には、1に等しい。それ以外の場合には、タイル画素の第0チャネルは0に等しい。タイル画素毎の第1及び第2チャネルは、対応するスクエア画素の第1及び第2チャネルにそれぞれ等しい。一方の成分の値を落とし且つその符号を保存することによって、正規図データのスクエアはデータのタイルへと変形される。
【0049】
図3A〜3Dは本発明の実施形態に従いデータの階層を生成する一連のタイル分割及びクワッド変換を示している。図3Aにおいては、16×16データのタイル301がデータの複数のクワッド302に分割される。データの各クワッドは、表現要素303、第1のデルタ要素304、第2のデルタ要素305、第3のデルタ要素306、及び制御ワード307へと変換される。16×16タイル301の分割は、64個のクワッド302を生じさせる。データのクワッド302の変換の後、64個の表現要素303、64個の第1のデルタ要素304、64個の第2のデルタ要素305、64個の第3のデルタ要素306、及び64個の制御ワード307が生成される。
【0050】
図3Bにおいては、64個の表現要素303は新たなタイル308を形成する。表現要素303の8×8タイル308は、データのクワッド309に分割される。データの各クワッドは、表現要素310、第1のデルタ要素311、第2のデルタ要素312、第3のデルタ要素313、及び制御ワード314へと変換される。8×8タイル308の分割は、16個のクワッド309を生じさせる。データのクワッド309の変換の後、16個の表現要素310、16個の第1のデルタ要素311、16個の第2のデルタ要素312、16個の第3のデルタ要素313、及び16個の制御ワード314が生成される。
【0051】
図3Cにおいては、16個の表現要素310は新たなタイル315を形成する。表現要素310の4×4タイル315は、データのクワッド316に分割される。データの各クワッドは、表現要素317、第1のデルタ要素318、第2のデルタ要素319、第3のデルタ要素320、及び制御ワード321へと変換される。4×4タイル315の分割は、4個のクワッド316を生じさせる。データのクワッド316の変換の後、4個の表現要素317、4個の第1のデルタ要素318、4個の第2のデルタ要素319、4個の第3のデルタ要素320、及び4個の制御ワード321が生成される。
【0052】
図3Dにおいては、4個の表現要素317は新たなタイル322を形成する。表現要素317の2×2タイル322は、データの更なるクワッドに分割することができない。従って、データのタイル322は、データの最上層クワッド322である。データのクワッド322は、単一の表現要素323、第1のデルタ要素324、第2のデルタ要素325、第3のデルタ要素326、及び制御ワード327へと変換される。単一の表現要素323は、データの階層の最上層である。階層の次のレベルは、データの2×2タイル322から変換されたデルタ要素324,325,326及び制御ワード327である。階層の次のレベルは、データの4×4タイル315から変換されたデルタ要素318,319,320及び制御ワード321である。階層の次のレベルは、データの8×8タイル308から変換されたデルタ要素311,312,313及び制御ワード314である。階層の次のレベルは、データの16×16タイル301から変換されたデルタ要素304,305,306及び制御ワード307である。
【0053】
代替的な実施形態においては、データのタイルは、同様の結果を生じさせる任意の便利な且つ/又は既知の方法で分割され得る。また、代替的な実施形態においては、クワッドは、同様の結果を生じさせる種々の技術を用いる任意の便利な且つ/又は既知の方法で変換され得る。更に、代替的な実施形態においては、クワッドの変換は、異なっていてよく且つ/又はデータフォーマットに依存していてよい。
【0054】
図4は本発明の実施形態に従うデータのタイルの階層を示している。階層の最上層は、階層の第2のレベルからの単一の表現要素323である。階層の第2のレベルは、階層の第3のレベルからの表現要素317のタイルである。階層の第3のレベルは、階層の第4のレベルからの表現要素310のタイルである。階層の第4のレベルは、階層の第5のレベルからの表現要素303のタイルである。階層の第5のレベルは、データの変形されたスクエアのタイル301である。
【0055】
図5は本発明の実施形態に従うグラフィックに係る形態におけるデータ圧縮方法を示している。ステップ501では、データの2次元表面がデータの複数のスクエアに分割される。好ましくはデータの各スクエアは、独立して圧縮され、そして並列で実行される。データのスクエアは好ましくはデータの16×16スクエアであるが、任意の便利な且つ/又は既知のサイズのデータのスクエアであり得る。ステップ502では、データの各スクエアがデータのタイルへと変形される。好ましくは、変形は用いられるデータ種類に依存する。ステップ503では、データのタイルがデータの複数のクワッドに分割される。好ましくは、データのクワッドは2×2である。ステップ504では、データの各クワッドは、表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換される。ステップ505では、データの新たなタイルが、変換から結果として得られる表現要素と共に形成される。
【0056】
判断動作506では、新たなタイルが複数のクワッドに分割され得るかどうかが決定される。データの新たなタイルが複数のクワッドに分割され得る場合には、プロセスはステップ503へ戻り、タイルがデータの複数のクワッドに分割される。方法はそこから継続する。
【0057】
一方、データの新たなタイルが複数のクワッドに分割され得ない場合には、ステップ507において、データの階層のビットが符号化されると共に出力ストリーム内へ割り付けられる。方法はこうして完結する。
【0058】
図6は本発明の実施形態に従い階層的データを符号化し且つ出力ストリーム内へ埋め込むために好ましく用いられるサブタイルパターンを示している。データの階層内の各タイルは、4つのサブタイルに分割される。階層の最上層から開始して、最上層タイル601、即ちデータの最上層クワッドは、サブタイル0_602、サブタイル1_603、サブタイル2_604、及びサブタイル3_605に分割される。階層の次のレベル606、即ちデータの4×4タイルは、同様にしてサブタイル0_607、サブタイル1_608、サブタイル2_609、及びサブタイル3_610に分割される。階層の次のレベル611、即ちデータの8×8タイルは、同様にしてサブタイル0_612、サブタイル1_613、サブタイル2_614、及びサブタイル3_615に分割される。階層の次で且つ最下層のレベル616、即ちデータの変換された16×16スクエアは、同様にしてサブタイル0_617、サブタイル1_618、サブタイル2_619、及びサブタイル3_620に分割される。好ましくは、符号化及び/又は埋め込みプロセスは、サブタイル0_602のためのデルタ要素を伴い最上層で開始し、そしてサブタイル0階層607,612,617を下りながら進む。次に、符号化及び/又は埋め込みプロセスは、サブタイル1_603のためのデルタ要素を伴い最上層で開始し、そしてサブタイル1階層608,613,618を下りながら進む。次いで、符号化及び/又は埋め込みプロセスは、サブタイル2_604のためのデルタ要素を伴い最上層で開始し、そしてサブタイル2階層609,614,619を下りながら進む。最後に、符号化及び/又は埋め込みプロセスは、サブタイル3_605のためのデルタ要素を伴い最上層で開始し、そしてサブタイル3階層610,615,620を下りながら進む。サブタイルパターンは、並列ビットストリーム復号を可能にすると共に、サブタイルにおける全ての基本的なデルタがゼロである場合にビット割り付けを中断する能力を可能にする。
【0059】
図7は本発明の実施形態に従いビット割り付けされた階層的データの出力ストリームを示している。制御情報701を表すビットが出力ストリーム715内に埋め込まれる。制御情報は好ましくはデータ種類に依存している。例えば、データの符号の256ビットマップを表している制御ビットは、用いられているフォーマットが正規図及び/又はZバッファである場合に埋め込まれ得る。制御情報701に続いて、データの階層の最上層からの単一の表現要素702を表すビットが、出力ストリーム715内に埋め込まれる。単一の表現要素702に続いて、サブタイル703のディレクトリを表すビットが出力ストリーム715内に埋め込まれる。ディレクトリは好ましくは3つのオフセットを備えている。サブタイル703のディレクトリに続いて、対応する制御ワードに従ってデルタ要素が埋め込まれる。例えばデータフォーマットがZバッファデータである場合、PUT(由来、量)(PUT (From, Amount))が特定のデルタ要素に由来するビットの量を送る関数であり、D0が制御ワードを表し、D1がデルタ1を表し、D2がデルタ2を表し、そしてD3がデルタ3を表しているとして、符号化は以下の式に追随し得る。
PUT(D0,6)
D0=2の場合、
他のデータは階層に対するストリーム内には埋め込まれない。
D0=3の場合において、
D1=Y,D2=N,D3=N又は
D1=N,D2=Y,D3=N又は
D1=N,D2=N,D3=Yであるときには、
5ビットプレフィックス、符号ビット及び1つの値が符号化され、
D1=N,D2=Y,D3=Y又は
D1=Y,D2=N,D3=Y又は
D1=Y,D2=Y,D3=Nであるときには、
5ビットプレフィックス、符号ビット及び2つの値が符号化され、
D1=Y,D2=Y,D3=Yであるときには、
5ビットプレフィックス、符号ビット及び3つの値が符号化される。
例えばデータフォーマットが色又は正規図データである場合、PUT(由来、量)が特定のデルタ要素に由来するビットの量を送る関数であり、PUT_SIGN(値)が、値がゼロでないときのその値の符号を送る関数であり、D0が制御ワードを表し、D1がデルタ1を表し、D2がデルタ2を表し、D3がデルタ3を表し、そしてLSBがデルタ要素の平均を表しているとして、符号化は以下の式に追随し得る。
PUT(D0,3)
D0=0の場合、
他のデータは階層に対するストリーム内には埋め込まれない。
D0=7の場合、
他のデータはストリーム内には埋め込まれない。
D0=1の場合、
PUT(D1,1);
PUT_SIGN(D1);
PUT(D2,1);
PUT_SIGN(D2);
PUT(D3,1);
PUT_SIGN(D3);
D0=2の場合、
PUT(D1,2);
PUT_SIGN(D1);
PUT(D2,2);
PUT_SIGN(D2);
PUT(D3,2);
PUT_SIGN(D3);
D0=3の場合、
PUT(D1,3);
PUT_SIGN(D1);
PUT(D2,3);
PUT_SIGN(D2);
PUT(D3,3);
PUT_SIGN(D3);
D0=4の場合、
PUT(LSB,2);
LSBが陽符号を有しているときはPUT(LBS_SIGN,1);
PUT(D1,3);
PUT_SIGN(D1);
PUT(D2,3);
PUT_SIGN(D2);
PUT(D3,3);
PUT_SIGN(D3);
D0=5の場合、
PUT(LSB,2);
LSBが陽符号を有しているときはPUT(LBS_SIGN,1);
PUT(D1,4);
PUT_SIGN(D1);
PUT(D2,4);
PUT_SIGN(D2);
PUT(D3,4);
PUT_SIGN(D3);
D0=6の場合、
PUT(D1,8);
PUT_SIGN(D1);
PUT(D2,8);
PUT_SIGN(D2);
PUT(D3,8);
PUT_SIGN(D3)。
一旦デルタ要素が対応する制御ワードに従って符号化されると、サブタイル0に対する最上層クワッドを表すビット704が出力ストリーム715内に埋め込まれる。次いで、サブタイル0に対する階層の低い方のレベル上のクワッドを表すビット705が埋め込まれる。次に、サブタイル1に対する最上層クワッドを表すビット706が埋め込まれる。次いで、サブタイル1に対するサブタイルディレクトリを表すビット707が埋め込まれる。次に、サブタイル1に対する階層の低い方のレベル上のクワッドを表すビット708が埋め込まれる。次いで、サブタイル2に対する最上層クワッドを表すビット709が埋め込まれる。次に、サブタイル2に対するサブタイルディレクトリを表すビット710が埋め込まれる。次いで、サブタイル2に対する階層の低い方のレベル上のクワッドを表すビット711が埋め込まれる。次に、サブタイル3に対する最上層クワッドを表すビット712が埋め込まれる。次いで、サブタイル3に対するサブタイルディレクトリを表すビット713が埋め込まれる。次に、サブタイル3に対する階層の低い方のレベル上のクワッドを表すビット714が埋め込まれる。
【0060】
代替的な実施形態においては、デルタ要素は任意の便利な且つ/又は既知の方法で符号化され得る。例えばデータフォーマットに応じて、同様の符号化結果を達成するために種々の式が用いられる。また、デルタ要素は任意の便利な且つ/又は既知の方法で埋め込まれ得る。例えば、デルタ要素はサブタイルパターンよりはむしろタイルパターン上に埋め込まれ得る。更に、追加のデータが出力ストリーム内に埋め込まれ得る。例えば、追加の制御情報がデータフォーマットに応じて出力ストリーム全体に追加され得る。また、更なる圧縮のために出力ストリームからデータが除去され得る。例えばディレクトリを表しているビットが除去されて、より大きな圧縮をもたらし得る。
【0061】
図8は本発明の実施形態に従うグラフィックに係る形態におけるビット割り付けを示している。制御情報801が出力ストリーム内に埋め込まれる。代替的な実施形態においては、制御情報は更なる圧縮のために取り除かれ得る。次に、単一の表現要素802がストリーム内に埋め込まれる。単一の表現要素802に続いて、サブタイルのディレクトリ803が出力ストリーム内に埋め込まれる。代替的な実施形態においては、サブタイルのディレクトリ803は更なる圧縮のために取り除かれ得る。次に、対応する1つ以上の制御ワード804に従ってデルタ要素が符号化される。符号化は好ましくはサブタイルパターンに追随する。代替的な実施形態においては、デルタはプロセスの間の任意の都合の良いタイミングで符号化され得る。次いで、サブタイル0に対する最上層クワッドを表すビット805が出力ストリーム内に埋め込まれた後、サブタイル0に対する残りのクワッドを表すビット806が続く。サブタイル1に対する最上層クワッドを表すビット807が次いで埋め込まれた後、サブタイル1に対するディレクトリ808が続く。代替的な実施形態においては、ディレクトリは更なる圧縮のために取り除かれ得る。サブタイル1に対するクワッドを表す残りのビットが次いで出力ストリーム内に埋め込まれる。次に、サブタイル2に対する最上層クワッドを表すビット810が出力ストリーム内に埋め込まれる。サブタイル2に対する最上層クワッドを表すビット810に続いて、サブタイル2に対するディレクトリを表すビット811が埋め込まれる。代替的な実施形態においては、ディレクトリは更なる圧縮をもたらすために取り除かれ得る。次いで、サブタイル2に対するクワッドを表す残りのビット812が埋め込まれる。サブタイル3に対する最上層クワッドを表すビット813が次いで埋め込まれた後、サブタイル3に対するディレクトリ814が続く。代替的な実施形態においては、ディレクトリは更なる圧縮をもたらすために取り除かれ得る。サブタイル3に対するクワッドを表す残りのビット815が次いで出力ストリーム内に埋め込まれる。
【0062】
本発明の実施形態のデータ圧縮方法は、データのスクエアをデータのタイルへと変形する。データのタイルは次いでデータの複数のクワッドに分割され、データの複数のクワッドは、表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換される。データの新たなタイルが次いで複数の表現要素を伴って形成され、そしてプロセスは単一の表現要素が残るまで繰り返す。単一の表現要素は次いで複数の制御ワード及び対応する複数のデルタ要素と共に出力ストリーム内に埋め込まれる。
【0063】
データ圧縮のシステム及び方法実装
【0064】
コンピュータ分野における当業者には明らかであろうように、本発明の実施形態の部分は、本開示の教示に従ってプログラムされる標準的な汎用の又は専用のデジタルコンピュータ又はマイクロプロセッサを用いて便利に実装され得る。
【0065】
ソフトウエア分野における当業者には明らかであろうように、本開示の教示に基づいて当業者的プログラマによって適切なソフトウエア符号化が容易に準備され得る。当業者には明らかであろうように、本発明はまた、特定用途向け集積回路の準備によって、又は標準的な要素回路の適切なネットワークを相互接続することによっても実装され得る。集積回路の実装は、ソフトウエアコード(例えばハードウエア記述言語におけるコード)の作成を通して達成されるであろうし、ソフトウエアコードは、合成されそして処理されるときに、本発明の側面を実施することができる半導体集積回路を製造する製造プロセス(例えば半導体製造工場におけるような製造プロセス)を構成するように整えられる。
【0066】
本発明の実施形態は、その上に/内部に命令(例えば、ソフトウエア、ファームウエア、及び/又はハードウエア記述言語コードを含むハードウエア命令)を有する記憶媒体(複数の記憶媒体)であるコンピュータプログラム製品を含み、命令は、本発明の実施形態の任意のプロセスを実行するようにコンピュータを制御することができ又はコンピュータに当該プロセスをさせることができる。記憶媒体は、限定はされないが、フロッピー(登録商標)ディスク、ミニディスク(MD)、光ディスク、DVD、CD−ROM、マイクロドライブ、及び光磁気ディスクを含む任意の種類のディスク、ROM、RAM、EPROM、EEPROM、DRAM、VRAM、フラッシュメモリデバイス(フラッシュカードを含む)、磁気若しくは光カード、ナノシステム(分子メモリICを含む)、RAIDデバイス、遠隔データ記憶/アーカイブ/ウェアハウジング、又は命令及び/若しくはデータを記憶するのに適した任意の種類の媒体若しくはデバイスを含む。
【0067】
コンピュータ可読媒体(複数の媒体)の任意の1つに記憶されて、本発明の実施形態は、汎用/専用両方のコンピュータ又はマイクロプロセッサのハードウエアを制御するためのソフトウエア、及び人間のユーザ又は本発明の実施形態の結果を利用する他のメカニズムとコンピュータ又はマイクロプロセッサが相互作用することを可能にするためのソフトウエアを含む。そのようなソフトウエアは、限定はされないが、デバイスドライバ、オペレーティングシステム、及びユーザアプリケーションを含む。最終的には、そのようなコンピュータ可読媒体は、前述したような本発明の実施形態を実行するためのソフトウエアを更に含む。
【0068】
汎用/専用のコンピュータ又はマイクロプロセッサのプログラミング(ソフトウエア)には、本発明の実施形態の教示を実装するためのソフトウエアモジュールが含まれ、それらは、限定はされないが、本発明の実施形態のプロセスに従って、データのスクエアを提供することと、データのスクエアをデータのタイルへと変形することと、データのタイルをデータの複数のクワッドに分割することと、各クワッドを表現要素へと変換することと、複数の表現要素を伴うデータの新たなタイルを形成することと、単一の表現要素が残るまで繰り返すことと、単一の表現要素、複数の制御ワード、及び複数のデルタ要素を出力ストリーム内に埋め込むことと、を含んでいる。
【0069】
本発明の実施形態は、本発明の構成及び動作の原理の理解を容易にする詳細を組み込んでいる特定の実施形態に関して説明されてきた。特定の実施形態及びその詳細に対するここでのそのような参照は、ここに添付される特許請求の範囲を限定することを意図してはいない。本発明の精神及び範囲から逸脱することなしに、例示を目的として選択された実施形態において多くの修正がなされ得ることが、当業者にとって明白であろう。例えば、例示される実施形態の機能を実行するために、符号化及び/若しくは埋め込みのための異なる式、並びに/又は種々のデータ及び/若しくはデータフォーマットが追加され且つ/又は除去され得る。
【技術分野】
【0001】
本発明はデータ圧縮に関する。より特定的には、本発明はハードウエア実装に適する可逆データ圧縮に関する。
【背景技術】
【0002】
データ圧縮は、より少ないビットを用いてデータが記憶されるようにデータを変換するプロセスである。データ圧縮には、非可逆(lossy)及び可逆(lossless)の2種類がある。非可逆データ圧縮は、より大きな程度でデータを圧縮するが、プロセスの最中にデータを喪失する。従って、復元(decompression)に際しては、データは、その正確な複製であるよりはむしろその元の形態の近似である。可逆データ圧縮は、より小さな程度でデータを圧縮するが、プロセスの最中にいかなるデータも喪失しない。従って、復元に際しては、データは圧縮前にあった通りに正確に再構築される。データ圧縮の目的は、伝送に必要な帯域幅及び/又は記憶に必要なメモリの量を低減することである。
【0003】
一般的な可逆圧縮技術の例としてハフマン符号化(Huffman coding)がある。ハフマン符号化はデータ項目の出現頻度に基いている。この技術は、より低い数(lower number)のビットを用いて、より頻繁に出現するデータを符号化する。残念なことに、ハフマン符号化の限界は、ハフマン符号化が固定されたシーケンス長手続きを有しておりまたシーケンス長を超えるデータにおける冗長性を圧縮することができないところにある。結果として、ハフマン符号化は複雑であり、また大量のメモリが有効にされることを必要とする。ハフマン符号化は、ファイルの任意の部分が抽出され得る前に全ファイルの解析を実行することを伴う。また、ハフマン技術は本質的に非対称であり、このことは復号プロセスが符号化プロセスよりも低速であることを意味している。そのような特性は、コンピュータが一般に単一のクロックサイクル上で概ね同じ量のデータを読み出し且つ書き込むように設計されていることを理由として、特定のハードウエア実装のためには受け入れられない。
【0004】
別の一般的な可逆技術は、レンペル・ジブ・ウェルチ法(Lempel-Ziv-Welch method)(LZW)である。LZWは、圧縮されているデータファイル内に以前に見えたストリングス(previously seen strings)の辞書を自動的に作成する。辞書は256エントリで動作開始し、1つのエントリは各可能な文字(character)のためにある。辞書内に未だないストリングが見つかるたびに、当該ストリングで構成されるもっと長いストリングが付け加えられる。出力は辞書内への整数指標(integer indices)で構成される。残念なことに、LZWにはそれが作成するストリングテーブルに起因する弱点がある。辞書は短時間の間に極めて大量に獲得することができる。加えて、必要とされるメモリの量は全ストリングの全長に依存するから、必要とされる記憶量が不確定である。また、ハフマン符号化と同様に、ファイルの任意の部分が圧縮され且つ/又は復元される前に全ファイルが符号化され且つ/又は復号される必要がある。更に、全体的プロセスは本質的に非対称であり、復元より圧縮の方がかなり長い時間を要する。
【0005】
上述の圧縮技術によって課せられる制限以外に、別の主要な問題は、データの異なるフォーマットに対する統一された圧縮方法がないことである。例えば、複数の画素からなるコンピュータグラフィックは、Zバッファリングを用いて表現され得る。Zバッファリングは、画素深さを試験することと、現在の位置のZ座標をZバッファに記憶されているデータと比較することとによって機能する。Zバッファは、各画素の最後の位置に関する情報を記憶している。観察者により近い位置における画素が、表示されることになる画素である。複数の画素からなるグラフィックスを表現するために用いられる他の一般的なデータフォーマットは、色バッファリング及び正規図(normal maps)である。現在のところ、正規図データのための可逆圧縮技術はなく、また色バッファリングデータは、ソフトウエア指向の独特な圧縮方法を必要としている。
【発明の概要】
【発明が解決しようとする課題】
【0006】
本質的に対称であり、それによりハードウエア実装に適しているデータ圧縮/復元方法が必要とされている。また、正規図データを含む幾つかの異なるデータフォーマットを圧縮し且つ復元することが可能なデータ圧縮/復元方法が必要とされている。更に、グラフィックに係る種々のハードウエアデバイスに適応可能なデータ圧縮/復元方法が必要とされている。
【課題を解決するための手段】
【0007】
本発明の1つの側面においては、データを主アレイへと配置するステップと、主アレイを複数の主サブアレイに分割するステップと、複数の圧縮されたサブアレイが形成されるように、各主サブアレイを圧縮されたサブアレイへと圧縮するステップと、圧縮されたサブアレイを補助アレイへと配置するステップと、分割するステップ、圧縮するステップ、及び配置するステップを単一のサブアレイが残るまで繰り返すステップと、をコンピュータが実行することを備えた階層的データ圧縮方法が提供され、ここでは、補助アレイはこれらのステップの繰り返しのための主アレイになる。圧縮されたサブアレイからのデータは出力ストリーム内に埋め込まれ得る。
【0008】
本発明の別の側面においては、データのスクエアを提供するステップと、データのスクエアをデータのタイルへと変形するステップと、左上画素、右上画素、左下画素、及び右下画素を各クワッドが有するデータの複数のクワッドにデータのタイルを分割するステップと、各クワッドを表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換するステップと、表現要素を伴うデータの新たなタイルを形成するステップと、データの新たなタイルが分割するステップ、変換するステップ、及び形成するステップの繰り返しのためのデータのタイルになるように、分割すること、変換すること、及び形成することを単一の表現要素が残るまで繰り返すステップと、単一の表現要素、制御ワード、及びデルタ要素を出力ストリーム内に埋め込むステップと、をコンピュータが実行することを備えたデータ圧縮方法が提供される。
【0009】
本発明の更に別の側面においては、機械によって可読なプログラム記憶デバイスが提供される。デバイスは、データ圧縮方法を実行することを機械によって実行可能な命令のプログラムを有形的に実施し、方法は、データのスクエアを提供することと、データのスクエアをデータのタイルへと変形することと、左上画素、右上画素、左下画素、及び右下画素を各クワッドが有するデータの複数のクワッドにデータのタイルを分割することと、各クワッドを表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換することと、表現要素を伴うデータの新たなタイルを形成することと、データの新たなタイルが分割するステップ、変換するステップ、及び形成するステップの繰り返しに対するデータのタイルになるように、分割すること、変換すること、及び形成することを単一の表現要素が残るまで繰り返すことと、単一の表現要素、制御ワード、及びデルタ要素を出力ストリーム内に埋め込むことと、を備えている。
【0010】
本発明は、上述の及び下記のように構成される他の実施形態の他、他の特徴及び代替案を伴う他の実施形態をも包含する。
【図面の簡単な説明】
【0011】
本発明は、添付の図面と併せて以下の詳細な説明によって容易に理解されるであろう。この説明を容易にするために、同様の参照番号は同様の要素を指定する。
【0012】
【図1A】図1Aは本発明の実施形態に従い画素ビットを含むデータの2次元表面を示す図(その1)である。
【図1B】図1Bは本発明の実施形態に従い画素ビットを含むデータの2次元表面を示す図(その2)である。
【図1C】図1Cは本発明の実施形態に従い画素ビットを含むデータの2次元表面を示す図(その3)である。
【図2A】図2Aは本発明の実施形態に従うスクエアからタイルへの変形を示す図(その1)である。
【図2B】図2Bは本発明の実施形態に従うスクエアからタイルへの変形を示す図(その2)である。
【図3A】図3Aは本発明の実施形態に従うタイルの分割、クワッドの変換、及び新たなタイルの形成を示す図(その1)である。
【図3B】図3Bは本発明の実施形態に従うタイルの分割、クワッドの変換、及び新たなタイルの形成を示す図(その2)である。
【図3C】図3Cは本発明の実施形態に従うタイルの分割、クワッドの変換、及び新たなタイルの形成を示す図(その3)である。
【図3D】図3Dは本発明の実施形態に従うタイルの分割、クワッドの変換、及び新たなタイルの形成を示す図(その4)である。
【図4】図4は本発明の実施形態に従うデータのタイルの階層を示す図である。
【図5】図5は本発明の実施形態に従うグラフィックに係る形態におけるデータ圧縮方法を示す図である。
【図6】図6は本発明の実施形態に従い階層的データを符号化すると共に出力ストリーム内に埋め込むために好ましく用いられるサブタイルパターンを示す図である。
【図7】図7は本発明の実施形態に従う階層的データのビット割り付けされた出力ストリームを示す図である。
【図8】図8は本発明の実施形態に従いグラフィックに係る形態におけるビット割り付けを示す図である。
【発明を実施するための形態】
【0013】
階層的可逆データ圧縮方法のための発明が開示される。本発明の実施形態の完全な理解をもたらすために、多くの特定の詳細が記載されている。しかし、本発明の実施形態は他の特定の詳細でも実施され得ることが当業者によって理解されるはずである。
【0014】
1つの実施形態においては、データの2次元表面が概念的にはデータの複数のスクエア(squares of data)に分割される。物理的なスクエアはないことが理解されるであろう。しかし、次元(長さ及び幅)及び表面を伴う物理的実体としてスクエアをみなすことは、本発明のための概念を理解するのに役立ち得る。データの2次元表面は、グラフィックに係る画像を表現する複数の画素ビットを含む。データの2次元表面は、16×16スクエアのサイズであるデータのスクエアに分割される。代替的な実施形態においては、データの2次元表面は、望ましい圧縮又は基本的なデータフォーマットに応じて、より大きな又はより小さな任意の数のスクエアに分割され得る。例えば、データの2次元表面は画素データの8×8スクエアに分割され得る。
【0015】
データの各スクエアは次いでデータのタイル(a tile of data)に変形される(transformed)。変形は、ハードウエア実装に適する整数加算演算又は整数減算演算を用いて行われる。データのスクエアをデータのタイルに変形するために用いられる技術は、グラフィックに係る画像を表現するのに用いられるデータフォーマットに依存し得る。例えばデータフォーマットがZバッファリングである場合には、データのタイルの第2列はデータのスクエアの第2列から第1列を減じたものに等しくセットされ、データのタイルの第3列はデータのスクエアの第3列からデータのスクエアの第2列を減じたものに等しくセットされ、データのタイルの第4列はデータのスクエアの第4列からデータのスクエアの第3列を減じたものに等しくセットされ、そして当該パターンは、各データ値が隣接データ値及びデータのタイル内に記憶される差を減ぜられるまで繰り返す。
【0016】
代替的な実施形態においては、異なる技術を用いて異なるデータフォーマットがタイルに変形され得る。例えば、各画素に対して色バッファデータのスクエアを変形するために、データのスクエアにおける第1チャネルは、データのスクエアにおける第2チャネルを減ぜられる。結果としてもたらされる値は、データのタイルにおける第1チャネル内に記憶される。データのスクエアにおける第2チャネルは、データのタイルにおける第2チャネル内に記憶される。データのスクエアにおける第3チャネルは、データのスクエアにおける第1チャネルを減ぜられ、そして当該値はデータのタイルにおける第3チャネル内に記憶される。当該パターンは、非相関変形が各画素に実行されるまで繰り返す。
【0017】
別の実施形態においては、各画素に対して正規図データを変形するために、データのスクエアにおける第1チャネルが落とされ、そしてその符号を表しているビットがデータのタイルにおける第1チャネル内に記憶される。データのスクエアにおける第2及び第3チャネルは、データのタイルにおけるそれぞれ第2及び第3チャネル内に記憶される。
【0018】
データのスクエアがデータのタイルに変形された後、タイルはクワッド(quads)に分割される。クワッドは、好ましくは左上画素、右上画素、左下画素、及び右下画素を有する2×2である。タイルがクワッドに分割されると、クワッドは表現要素(representative element)、3つのデルタ要素、及び制御ワードに変換される(converted)。変換は、好ましくはハードウエア実装に適した整数加算演算又は整数減算演算を含む。データフォーマットに応じて異なる技術がデータのクワッドを表現要素、3つのデルタ要素、及び制御ワードに変換するために用いられ得る。異なる変換技術の例が後で更に詳細に論じられることになる。
【0019】
クワッドが変換され終わった後に、結果としてもたらされる表現要素を伴う新たなタイルが形成される。新たなタイルは次いでクワッドに分割され、そしてそれらのクワッドは表現要素、3つのデルタ、及び制御ワードに変換される。同様に、結果としてもたらされる表現要素は別の新たなタイルを形成し、そして当該タイルはクワッドに分割され、分割されたクワッドは表現要素、3つのデルタ要素、及び制御ワードに変換される。当該パターンは単一の表現要素が残るまで繰り返す。結果はデータの階層であり、その最上層は単一の表現要素であり、またその最下層は、データの変形されたスクエアを表しているデータの変換されたクワッドである。最下層から最上層へ行き来すると、階層の各レベルはより小さいクワッドの4倍を有している。尚、この設計は、データの多重スクエアがグラフィックに係る画像を表現している場合に、全体プロセスが容易に並列化されることを可能にする。
【0020】
単一の表現要素が残ったら、圧縮されたデータのしっかりとアラインされた画素ストリーム内へ画素を埋め込むプロセスが開始する。好ましくは制御情報が最初にストリーム内へ埋め込まれ、これはデータフォーマットに応じて僅かに変化し得る。例えば、Zバッファ又は正規図データが用いられる場合には、制御情報は各画素のための符号の256画素マップを含み得る。次いで単一の表現要素が、適切な数の画素と共に出力ストリーム内へ埋め込まれる。
【0021】
階層内のデータのタイルの各々を4つの等しいスクエアに分割することは、データの4つのサブタイルを生成する。例えば、データのタイルは、最上位左サブタイルがサブタイル0、最上位右サブタイルがサブタイル1、最下位左サブタイルがサブタイル2、そして最下位右サブタイルがサブタイル3であるように分割されるであろう。例えばタイルが16×16である場合には、各サブタイルは8×8であろう。単一の表現要素の埋め込みに続いて、好ましくは、オフセットから構成されるサブタイルのディレクトリが埋め込まれる。例えばデータのタイルが16×16である場合、サブタイル1のためのオフセットはサブタイルゼロ([0,7][0,7])からの([8,15][0,7])であろう一方で、サブタイル2のためのオフセットはサブタイル1の開始からの([0,7][8,15])であろうし、そしてサブタイル3はサブタイル2からの([8,15][8,15])であろう。
【0022】
単一の表現要素及びサブタイルの好ましいディレクトリが出力ストリーム内へ埋め込まれた後、クワッドの各々からのデルタ要素が符号化される。符号化は階層の最上層で開始し、そして最下層へと進む。クワッドはそれらの対応する制御ワードに従って符号化される。符号化は好ましくはサブタイルパターンに追随する。例えば、最上層から最下層までのサブタイル0に対する全てのデルタが最初に符号化されるであろうし、最上層から最下層までのサブタイル1のデルタがそれに続くであろう。次いで、サブタイル2のデルタが最上層から最下層まで符号化されるであろうし、サブタイル3のデルタの符号化がそれに続くであろう。尚、階層の低い方のレベルが高い方のレベルから完全に復号され得る場合には、低い方のレベルの符号化が回避されるので、圧縮が増大される。
【0023】
符号化された画素は、次いで好ましくはサブタイルパターンに追随する出力ストリーム内に埋め込まれる。符号化された画素の埋め込みは、好ましくはサブタイル0に対して最上層クワッドを表している画素で開始することになる。次に、サブタイル0に対して階層の低い方のレベルで符号化された画素が、最上層から最下層まで出力ストリーム内に埋め込まれる。次いで、サブタイル1に対して最上層クワッドを表している画素が埋め込まれることになる。次に、好ましくはサブタイル1のためのディレクトリが出力ストリーム内に埋め込まれる。例えばデータのスクエアが16×16である場合には、サブタイル1のためのディレクトリはオフセット([4,7][0,3])であろう。ディレクトリに続いて、サブタイル1に対して階層の低い方のレベルで符号化された画素が、次いで最上層から最下層まで出力ストリーム内に埋め込まれることになる。次に、サブタイル2に対して最上層クワッドを表している画素が埋め込まれることになる。次いで、好ましくはサブタイル2のためのディレクトリが出力ストリーム内に埋め込まれる。例えばデータのスクエアが16×16である場合には、サブタイル2のためのディレクトリはオフセット([0,3][4,7])であろう。ディレクトリに続いて、サブタイル2に対して階層の低い方のレベルで符号化された画素が、次いで最上層から最下層まで出力ストリーム内に埋め込まれることになる。次に、サブタイル3に対して最上層クワッドを表している画素が埋め込まれることになる。次いで、サブタイル3のためのディレクトリが出力ストリーム内に埋め込まれる。例えばデータのスクエアが16×16である場合には、サブタイル3のためのディレクトリはオフセット([4,7][4,7])であろう。ディレクトリに続いて、サブタイル3に対して階層の低い方のレベルで符号化された画素が、次いで最上層から最下層まで出力ストリーム内に埋め込まれることになる。
【0024】
前述したように、データフォーマットに応じて、データのクワッドを表現要素、3つのデルタ要素、及び制御ワードに変換するために種々の技術が用いられ得る。例えば色バッファ又は正規図データを変換するために、表現要素はクワッドの左上画素に等しくセットされる。第1のデルタ要素は左上画素を減ぜられた右上画素に等しい。第2のデルタ要素は左上画素を減ぜられた左下画素に等しい。第3のデルタ要素は左下画素を減ぜられた右下画素に等しい。制御ワードはデルタ要素の間での相関に従ってセットされる。全てのデルタ要素がゼロに等しい場合には、制御ワードはゼロにセットされる。これは、画素割り付けの間、画素割り付け器(pixel allocator)がそのクワッドに対する画素の任意の更なる割り付けを中断するための信号である。デルタ要素がゼロに等しくない場合には、制御ワードは3つのデルタのうちの最大絶対値に応じてセットされる。デルタのうちの最大絶対値が1以下である場合には、制御ワードは1にセットされる。デルタのうちの最大絶対値が3以下である場合には、制御ワードは2にセットされる。デルタのうちの最大絶対値が7以下である場合には、制御ワードは3にセットされる。デルタのうちの最大絶対値が7より大きい場合には、異なる戦略が採用される。デルタのうちの最大絶対値が7より大きいと仮定すると、左上画素、右上画素、左下画素、及び右下画素の平均が計算される。表現要素はクワッド画素の平均に等しくなるようにリセットされる。第1のデルタ要素は、平均を減ぜられた左上画素に等しくなるようにリセットされる。第2のデルタ要素は、平均を減ぜられた右上画素に等しくなるようにリセットされる。第3のデルタ要素は、平均を減ぜられた左下画素に等しくなるようにリセットされる。制御ワードは、リセットされたデルタ要素のうちの最大絶対値が7以下である場合には、4にセットされる。リセットされたデルタ要素のうちの最大絶対値が15以下である場合には、制御ワードは5にセットされる。
【0025】
リセットされたデルタ要素のうちの最大絶対値が15より大きい場合には、制御ワードは6にセットされ、そして表現要素及びデルタ要素は元のクワッド画素としてセットされる。従って、リセットされたデルタ要素のうちの最大絶対値が15より大きいと仮定すると、表現要素は左上画素に等しく、第1のデルタ要素は右上画素に等しく、第2のデルタ要素は左下画素に等しく、そして第3のデルタ要素は右下画素に等しい。
【0026】
デルタの符号化及び埋め込みは、データフォーマットに応じて異なり得る。好ましい実施形態によると、データがどのように符号化されるのかを定義する6ビットプレフィックス(prefix)がある。各バッファのために2ビットある。各2ビット制御ワードは00、01、10、又は11であり得る。
【0027】
【表1】
【0028】
1つの例においては、Zバッファデータが用いられ、そして制御ワードは2ビットである。制御ワードが「00」である場合、制御ワードのみが出力ストリーム内に埋め込まれ、そして他のデータは埋め込まれない。このことは大幅な圧縮を可能にし、この場合、データの変化はない。制御ワードが「01」である場合、制御ワードが埋め込まれ、そしてデルタがそれらの対応する画素値と共に埋め込まれる。最後に制御ワードが「11」である場合、制御ワードを表しているビットが埋め込まれ、そしてデルタは関連する事例(以下の表を参照)に従って符号化される。
【0029】
【表2】
【0030】
符号化は、幾つかのビットを定義している5ビットプレフィックスと符号ビットとを含む。事例が0、1、又は2である場合、単一の値がプレフィックスと共に出力ストリーム内に埋め込まれて、ビットの最大数が1であることを指定する。事例が3、4、又は5である場合、2つの値がプレフィックスと共に出力ストリーム内に埋め込まれて、それらのうちのビットの最大数が2であることを指定する。事例が6である場合、3つの値がプレフィックスと共に出力ストリーム内に埋め込まれて、それらのうちのビットの最大数が3であることを指定する。代替的な実施形態においては、デルタ要素は異なる技術を用いて符号化され得るし、また埋め込まれ得る。
【0031】
例えば色バッファ又は正規図データが用いられ且つ制御ワードが0である場合、制御ワードを表す3ビットが出力ストリーム内に埋め込まれ、そして他のデータは埋め込まれない。色に対しては3ビット制御ワードが用いられる。
【0032】
制御ワードが1である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、第1のデルタ要素を表す1ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次に、第2のデルタ要素を表す1ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次いで、第3のデルタ要素を表す1ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0033】
制御ワードが2である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、第1のデルタ要素を表す2ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次に、第2のデルタ要素を表す2ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次いで、第3のデルタ要素を表す2ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0034】
制御ワードが3である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、第1のデルタ要素を表す3ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次に、第2のデルタ要素を表す3ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次いで、第3のデルタ要素を表す3ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0035】
制御ワードが4である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、クワッドの平均を表す2ビットが埋め込まれた後に、平均の符号を表すビットが続く。次に、第1のデルタ要素を表す3ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次いで、第2のデルタ要素を表す3ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次に、第3のデルタ要素を表す3ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0036】
制御ワードが5である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、クワッドの平均を表す2ビットが埋め込まれた後に、平均の符号を表すビットが続く。次に、第1のデルタ要素を表す4ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次いで、第2のデルタ要素を表す4ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次に、第3のデルタ要素を表す4ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0037】
制御ワードが6である場合には、制御ワードを表す3ビットが出力ストリーム内に埋め込まれる。次いで、第1のデルタ要素を表す8ビットが埋め込まれた後に、第1のデルタ要素の符号を表すビットが続く。次に、第2のデルタ要素を表す8ビットが埋め込まれた後に、第2のデルタ要素の符号を表すビットが続く。次いで、第3のデルタ要素を表す8ビットが埋め込まれた後に、第3のデルタ要素の符号を表すビットが続く。
【0038】
制御ワードが7である場合には、データは全部ゼロで埋められる。
【0039】
出力ストリームを再構築するために、ビットアラインされたストリーム(bit-aligned stream)を構文解析することによって復号プロセスが開始する。ビットアラインされたストリームが構文解析され終わると、逆変換及び変形(inverse conversions and transforms)が実行されてデータを再構築する。復号プロセスは符号化プロセスと完全に対称である。一旦データ階層の最上層レベルが復号されると、下層の方のレベルは、それらの各々に対するビットストリーム内に開始位置が設けられている場合には、並列的に復号され得る。サブタイルのための適切なオフセットのディレクトリが好ましくは出力ストリーム内に埋め込まれており、並列ビットストリーム復号を可能にしている。
【0040】
上述のステップは、同一の結果を達成するためのアレイの組み合わせにおける種々のデータフォーマットで実行され得る。特に、データフォーマットは、データの2次元表面として表現され得る任意の便利な且つ/又は既知のデータフォーマットであってよい。例えば、データフォーマットは、静止画、動画、テクスチャ(textures)を代表していてよく、そして浮動32及び/又は固定24フォーマットであってよい。また、データのスクエア及び/又はクワッドに実行される変形及び/又は変換は、同一の結果を達成するための任意の便利な且つ/又は既知の方法で行われ得る。例えば、データのスクエア及びクワッドは、加算され、減算され、乗算され、除算され、且つ/又は同一の結果を達成するための任意の他の方法で操作され得る。加えて、ビット割り付けは、任意の便利な且つ/又は既知の方法で実行され得る。典型的な追加の制御情報が追加されてよく、又は出力ストリームには制御情報が埋め込まれなくてよい。また、デルタは、処理の間に任意の便利な且つ/又は既知のタイミングで符号化され得る。デルタは、対応するクワッドが変換された後、又は階層の同様のレベルのクワッドが変換されてすぐに且つ/若しくはビット割り付けに先立つ任意の他のタイミングで、符号化され得る。更に、追加のディレクトリがビットストリーム内に含まれ得るし、又はディレクトリを除去して圧縮を増大してもよい。
【0041】
図1A〜1Cは、本発明の実施形態に従い画素を含むデータの2次元表面によって表されるグラフィックに係る画像を示している。図1Aにおいては、グラフィックに係る画像101が画面102上に表示されている。
【0042】
図1Bにおいては、グラフィックに係る画像101は、データの2次元表面103上の一連の画素104によって表されている。グラフィックに係る画像101の存在は一連の1によって表される一方で、グラフィックに係る画像101の不在は0によって表される。
【0043】
図1Cにおいては、階層的圧縮を用いて圧縮され得るデータの2次元表面103から、データの16×16スクエア105が分割されたものとなっている。データのスクエア105は、グラフィックに係る画像101の左上部分を表している。
【0044】
代替的な実施形態においては、データの2次元表面は、任意の数の画素幅と任意の数の画素高さであってよい。例えば、データの2次元表面は、4×4若しくは1280×1024又は任意の他の便利な若しくは既知の幅×高さ画素表示であってよい。また、データのスクエア105は、より大きく又はより小さくてよい。例えば、データのスクエア105は、データの2次元表面の8×8分割であってよい。更に、代替的な実施形態においては、データの追加的なスクエアがデータの2次元表面から分割されてよく、そして並列的に圧縮されてよい。
【0045】
図2A及び2Bは本発明の実施形態に従うスクエアからタイルへの変形を示している。図2Aにおいては、データの8×8スクエア201はA1〜H8の値を含む。データ203はZバッファフォーマットにある。
【0046】
図2Bにおいては、データのスクエア201は、全ての画素を隣接画素間の値の差で置換することによって、データのタイル202へと変形される。Zバッファに対する変形は、T[i][j]が(j,i)座標のタイル内の画素の座標を表し、S[i][j]が(j,i)座標のスクエア内の画素の座標を表し、Hがタイル高さを表し、そしてWがタイル幅を表す場合、各行に沿って左から右に水平に移動しながら次の式に追随し得る。
(i=0,…,H−1)に対して
(j=0,…,W−1)に対して
T[i][j]=S[i][j]−S[i][j−1]
また、第0列に沿って上から下に垂直に移動しながら次の式に追随する。
(i=1,…,H−1)に対して
T[i][0]=S[i][0]−S[i−1][0]
S[0][0]は一定であり、T[0][0]はT[0][1](即ち最も近い右の近隣)で置換される。従って、画素A2はA2−A1で置換される。画素A3はA3−A2で置換される。プロセスは、データ1の全スクエアが隣接画素間の値の差を含むデータ202のタイルへと変形されるまで継続する。
【0047】
代替的な実施形態においては、データのスクエアは、データフォーマットに応じて異なる技術を用いて変形され得る。例えば、データのスクエアが色バッファフォーマットである場合において、T[i][j][c]が(j,i)座標のタイル内の画素の座標及びその画素のチャネルcを表し、S[i][j][c]が(j,i)座標のスクエア内の画素の座標及びその画素のチャネルcを表し、Hがタイル高さを表し、そしてWがタイル幅を表すときには、変形は次の式に追随し得る。
(i=0,…,H−1)に対して
(j=0,…,W−1)に対して
T[i][j][0]=S[i][j][0]−S[i][j][1]
T[i][j][1]=S[i][j][1]
T[i][j][2]=S[i][j][2]−S[i][j][1]
従って、タイル画素毎の第0チャネルは、対応するスクエア画素の第0チャネルから対応するスクエア画素の第1チャネルを減じたものに等しい。タイル画素毎の第1チャネルは、対応するスクエア画素の第1チャネルに等しい。タイル画素毎の第2チャネルは、対応するスクエア画素の第2チャネルから対応するスクエア画素の第1チャネルを減じたものに等しい。各画素について非相関変形を実行することによって、色バッファデータのスクエアがデータのタイルへと変形される。
【0048】
代替的な実施形態の別の例では、データのスクエアが正規図フォーマットである場合において、T[i][j][c]が(j,i)座標のタイル内の画素の座標及びその画素のチャネルcを表し、S[i][j][c]が(j,i)座標のスクエア内の画素の座標及びその画素のチャネルcを表し、Hがタイル高さを表し、そしてWがタイル幅を表すときには、変形は次の式に追随し得る。
(i=0,…,H−1)に対して
(j=0,…,W−1)に対して
S[i][j][0]>0の場合にはT[i][j][0]=1;
それ以外の場合にはT[i][j][0]=0
T[i][j][1]=S[i][j][1]
T[i][j][2]=S[i][j][2]
従って、タイル画素毎の第0チャネルは、対応するスクエア画素の第0チャネル内に記憶されている値が正である場合には、1に等しい。それ以外の場合には、タイル画素の第0チャネルは0に等しい。タイル画素毎の第1及び第2チャネルは、対応するスクエア画素の第1及び第2チャネルにそれぞれ等しい。一方の成分の値を落とし且つその符号を保存することによって、正規図データのスクエアはデータのタイルへと変形される。
【0049】
図3A〜3Dは本発明の実施形態に従いデータの階層を生成する一連のタイル分割及びクワッド変換を示している。図3Aにおいては、16×16データのタイル301がデータの複数のクワッド302に分割される。データの各クワッドは、表現要素303、第1のデルタ要素304、第2のデルタ要素305、第3のデルタ要素306、及び制御ワード307へと変換される。16×16タイル301の分割は、64個のクワッド302を生じさせる。データのクワッド302の変換の後、64個の表現要素303、64個の第1のデルタ要素304、64個の第2のデルタ要素305、64個の第3のデルタ要素306、及び64個の制御ワード307が生成される。
【0050】
図3Bにおいては、64個の表現要素303は新たなタイル308を形成する。表現要素303の8×8タイル308は、データのクワッド309に分割される。データの各クワッドは、表現要素310、第1のデルタ要素311、第2のデルタ要素312、第3のデルタ要素313、及び制御ワード314へと変換される。8×8タイル308の分割は、16個のクワッド309を生じさせる。データのクワッド309の変換の後、16個の表現要素310、16個の第1のデルタ要素311、16個の第2のデルタ要素312、16個の第3のデルタ要素313、及び16個の制御ワード314が生成される。
【0051】
図3Cにおいては、16個の表現要素310は新たなタイル315を形成する。表現要素310の4×4タイル315は、データのクワッド316に分割される。データの各クワッドは、表現要素317、第1のデルタ要素318、第2のデルタ要素319、第3のデルタ要素320、及び制御ワード321へと変換される。4×4タイル315の分割は、4個のクワッド316を生じさせる。データのクワッド316の変換の後、4個の表現要素317、4個の第1のデルタ要素318、4個の第2のデルタ要素319、4個の第3のデルタ要素320、及び4個の制御ワード321が生成される。
【0052】
図3Dにおいては、4個の表現要素317は新たなタイル322を形成する。表現要素317の2×2タイル322は、データの更なるクワッドに分割することができない。従って、データのタイル322は、データの最上層クワッド322である。データのクワッド322は、単一の表現要素323、第1のデルタ要素324、第2のデルタ要素325、第3のデルタ要素326、及び制御ワード327へと変換される。単一の表現要素323は、データの階層の最上層である。階層の次のレベルは、データの2×2タイル322から変換されたデルタ要素324,325,326及び制御ワード327である。階層の次のレベルは、データの4×4タイル315から変換されたデルタ要素318,319,320及び制御ワード321である。階層の次のレベルは、データの8×8タイル308から変換されたデルタ要素311,312,313及び制御ワード314である。階層の次のレベルは、データの16×16タイル301から変換されたデルタ要素304,305,306及び制御ワード307である。
【0053】
代替的な実施形態においては、データのタイルは、同様の結果を生じさせる任意の便利な且つ/又は既知の方法で分割され得る。また、代替的な実施形態においては、クワッドは、同様の結果を生じさせる種々の技術を用いる任意の便利な且つ/又は既知の方法で変換され得る。更に、代替的な実施形態においては、クワッドの変換は、異なっていてよく且つ/又はデータフォーマットに依存していてよい。
【0054】
図4は本発明の実施形態に従うデータのタイルの階層を示している。階層の最上層は、階層の第2のレベルからの単一の表現要素323である。階層の第2のレベルは、階層の第3のレベルからの表現要素317のタイルである。階層の第3のレベルは、階層の第4のレベルからの表現要素310のタイルである。階層の第4のレベルは、階層の第5のレベルからの表現要素303のタイルである。階層の第5のレベルは、データの変形されたスクエアのタイル301である。
【0055】
図5は本発明の実施形態に従うグラフィックに係る形態におけるデータ圧縮方法を示している。ステップ501では、データの2次元表面がデータの複数のスクエアに分割される。好ましくはデータの各スクエアは、独立して圧縮され、そして並列で実行される。データのスクエアは好ましくはデータの16×16スクエアであるが、任意の便利な且つ/又は既知のサイズのデータのスクエアであり得る。ステップ502では、データの各スクエアがデータのタイルへと変形される。好ましくは、変形は用いられるデータ種類に依存する。ステップ503では、データのタイルがデータの複数のクワッドに分割される。好ましくは、データのクワッドは2×2である。ステップ504では、データの各クワッドは、表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換される。ステップ505では、データの新たなタイルが、変換から結果として得られる表現要素と共に形成される。
【0056】
判断動作506では、新たなタイルが複数のクワッドに分割され得るかどうかが決定される。データの新たなタイルが複数のクワッドに分割され得る場合には、プロセスはステップ503へ戻り、タイルがデータの複数のクワッドに分割される。方法はそこから継続する。
【0057】
一方、データの新たなタイルが複数のクワッドに分割され得ない場合には、ステップ507において、データの階層のビットが符号化されると共に出力ストリーム内へ割り付けられる。方法はこうして完結する。
【0058】
図6は本発明の実施形態に従い階層的データを符号化し且つ出力ストリーム内へ埋め込むために好ましく用いられるサブタイルパターンを示している。データの階層内の各タイルは、4つのサブタイルに分割される。階層の最上層から開始して、最上層タイル601、即ちデータの最上層クワッドは、サブタイル0_602、サブタイル1_603、サブタイル2_604、及びサブタイル3_605に分割される。階層の次のレベル606、即ちデータの4×4タイルは、同様にしてサブタイル0_607、サブタイル1_608、サブタイル2_609、及びサブタイル3_610に分割される。階層の次のレベル611、即ちデータの8×8タイルは、同様にしてサブタイル0_612、サブタイル1_613、サブタイル2_614、及びサブタイル3_615に分割される。階層の次で且つ最下層のレベル616、即ちデータの変換された16×16スクエアは、同様にしてサブタイル0_617、サブタイル1_618、サブタイル2_619、及びサブタイル3_620に分割される。好ましくは、符号化及び/又は埋め込みプロセスは、サブタイル0_602のためのデルタ要素を伴い最上層で開始し、そしてサブタイル0階層607,612,617を下りながら進む。次に、符号化及び/又は埋め込みプロセスは、サブタイル1_603のためのデルタ要素を伴い最上層で開始し、そしてサブタイル1階層608,613,618を下りながら進む。次いで、符号化及び/又は埋め込みプロセスは、サブタイル2_604のためのデルタ要素を伴い最上層で開始し、そしてサブタイル2階層609,614,619を下りながら進む。最後に、符号化及び/又は埋め込みプロセスは、サブタイル3_605のためのデルタ要素を伴い最上層で開始し、そしてサブタイル3階層610,615,620を下りながら進む。サブタイルパターンは、並列ビットストリーム復号を可能にすると共に、サブタイルにおける全ての基本的なデルタがゼロである場合にビット割り付けを中断する能力を可能にする。
【0059】
図7は本発明の実施形態に従いビット割り付けされた階層的データの出力ストリームを示している。制御情報701を表すビットが出力ストリーム715内に埋め込まれる。制御情報は好ましくはデータ種類に依存している。例えば、データの符号の256ビットマップを表している制御ビットは、用いられているフォーマットが正規図及び/又はZバッファである場合に埋め込まれ得る。制御情報701に続いて、データの階層の最上層からの単一の表現要素702を表すビットが、出力ストリーム715内に埋め込まれる。単一の表現要素702に続いて、サブタイル703のディレクトリを表すビットが出力ストリーム715内に埋め込まれる。ディレクトリは好ましくは3つのオフセットを備えている。サブタイル703のディレクトリに続いて、対応する制御ワードに従ってデルタ要素が埋め込まれる。例えばデータフォーマットがZバッファデータである場合、PUT(由来、量)(PUT (From, Amount))が特定のデルタ要素に由来するビットの量を送る関数であり、D0が制御ワードを表し、D1がデルタ1を表し、D2がデルタ2を表し、そしてD3がデルタ3を表しているとして、符号化は以下の式に追随し得る。
PUT(D0,6)
D0=2の場合、
他のデータは階層に対するストリーム内には埋め込まれない。
D0=3の場合において、
D1=Y,D2=N,D3=N又は
D1=N,D2=Y,D3=N又は
D1=N,D2=N,D3=Yであるときには、
5ビットプレフィックス、符号ビット及び1つの値が符号化され、
D1=N,D2=Y,D3=Y又は
D1=Y,D2=N,D3=Y又は
D1=Y,D2=Y,D3=Nであるときには、
5ビットプレフィックス、符号ビット及び2つの値が符号化され、
D1=Y,D2=Y,D3=Yであるときには、
5ビットプレフィックス、符号ビット及び3つの値が符号化される。
例えばデータフォーマットが色又は正規図データである場合、PUT(由来、量)が特定のデルタ要素に由来するビットの量を送る関数であり、PUT_SIGN(値)が、値がゼロでないときのその値の符号を送る関数であり、D0が制御ワードを表し、D1がデルタ1を表し、D2がデルタ2を表し、D3がデルタ3を表し、そしてLSBがデルタ要素の平均を表しているとして、符号化は以下の式に追随し得る。
PUT(D0,3)
D0=0の場合、
他のデータは階層に対するストリーム内には埋め込まれない。
D0=7の場合、
他のデータはストリーム内には埋め込まれない。
D0=1の場合、
PUT(D1,1);
PUT_SIGN(D1);
PUT(D2,1);
PUT_SIGN(D2);
PUT(D3,1);
PUT_SIGN(D3);
D0=2の場合、
PUT(D1,2);
PUT_SIGN(D1);
PUT(D2,2);
PUT_SIGN(D2);
PUT(D3,2);
PUT_SIGN(D3);
D0=3の場合、
PUT(D1,3);
PUT_SIGN(D1);
PUT(D2,3);
PUT_SIGN(D2);
PUT(D3,3);
PUT_SIGN(D3);
D0=4の場合、
PUT(LSB,2);
LSBが陽符号を有しているときはPUT(LBS_SIGN,1);
PUT(D1,3);
PUT_SIGN(D1);
PUT(D2,3);
PUT_SIGN(D2);
PUT(D3,3);
PUT_SIGN(D3);
D0=5の場合、
PUT(LSB,2);
LSBが陽符号を有しているときはPUT(LBS_SIGN,1);
PUT(D1,4);
PUT_SIGN(D1);
PUT(D2,4);
PUT_SIGN(D2);
PUT(D3,4);
PUT_SIGN(D3);
D0=6の場合、
PUT(D1,8);
PUT_SIGN(D1);
PUT(D2,8);
PUT_SIGN(D2);
PUT(D3,8);
PUT_SIGN(D3)。
一旦デルタ要素が対応する制御ワードに従って符号化されると、サブタイル0に対する最上層クワッドを表すビット704が出力ストリーム715内に埋め込まれる。次いで、サブタイル0に対する階層の低い方のレベル上のクワッドを表すビット705が埋め込まれる。次に、サブタイル1に対する最上層クワッドを表すビット706が埋め込まれる。次いで、サブタイル1に対するサブタイルディレクトリを表すビット707が埋め込まれる。次に、サブタイル1に対する階層の低い方のレベル上のクワッドを表すビット708が埋め込まれる。次いで、サブタイル2に対する最上層クワッドを表すビット709が埋め込まれる。次に、サブタイル2に対するサブタイルディレクトリを表すビット710が埋め込まれる。次いで、サブタイル2に対する階層の低い方のレベル上のクワッドを表すビット711が埋め込まれる。次に、サブタイル3に対する最上層クワッドを表すビット712が埋め込まれる。次いで、サブタイル3に対するサブタイルディレクトリを表すビット713が埋め込まれる。次に、サブタイル3に対する階層の低い方のレベル上のクワッドを表すビット714が埋め込まれる。
【0060】
代替的な実施形態においては、デルタ要素は任意の便利な且つ/又は既知の方法で符号化され得る。例えばデータフォーマットに応じて、同様の符号化結果を達成するために種々の式が用いられる。また、デルタ要素は任意の便利な且つ/又は既知の方法で埋め込まれ得る。例えば、デルタ要素はサブタイルパターンよりはむしろタイルパターン上に埋め込まれ得る。更に、追加のデータが出力ストリーム内に埋め込まれ得る。例えば、追加の制御情報がデータフォーマットに応じて出力ストリーム全体に追加され得る。また、更なる圧縮のために出力ストリームからデータが除去され得る。例えばディレクトリを表しているビットが除去されて、より大きな圧縮をもたらし得る。
【0061】
図8は本発明の実施形態に従うグラフィックに係る形態におけるビット割り付けを示している。制御情報801が出力ストリーム内に埋め込まれる。代替的な実施形態においては、制御情報は更なる圧縮のために取り除かれ得る。次に、単一の表現要素802がストリーム内に埋め込まれる。単一の表現要素802に続いて、サブタイルのディレクトリ803が出力ストリーム内に埋め込まれる。代替的な実施形態においては、サブタイルのディレクトリ803は更なる圧縮のために取り除かれ得る。次に、対応する1つ以上の制御ワード804に従ってデルタ要素が符号化される。符号化は好ましくはサブタイルパターンに追随する。代替的な実施形態においては、デルタはプロセスの間の任意の都合の良いタイミングで符号化され得る。次いで、サブタイル0に対する最上層クワッドを表すビット805が出力ストリーム内に埋め込まれた後、サブタイル0に対する残りのクワッドを表すビット806が続く。サブタイル1に対する最上層クワッドを表すビット807が次いで埋め込まれた後、サブタイル1に対するディレクトリ808が続く。代替的な実施形態においては、ディレクトリは更なる圧縮のために取り除かれ得る。サブタイル1に対するクワッドを表す残りのビットが次いで出力ストリーム内に埋め込まれる。次に、サブタイル2に対する最上層クワッドを表すビット810が出力ストリーム内に埋め込まれる。サブタイル2に対する最上層クワッドを表すビット810に続いて、サブタイル2に対するディレクトリを表すビット811が埋め込まれる。代替的な実施形態においては、ディレクトリは更なる圧縮をもたらすために取り除かれ得る。次いで、サブタイル2に対するクワッドを表す残りのビット812が埋め込まれる。サブタイル3に対する最上層クワッドを表すビット813が次いで埋め込まれた後、サブタイル3に対するディレクトリ814が続く。代替的な実施形態においては、ディレクトリは更なる圧縮をもたらすために取り除かれ得る。サブタイル3に対するクワッドを表す残りのビット815が次いで出力ストリーム内に埋め込まれる。
【0062】
本発明の実施形態のデータ圧縮方法は、データのスクエアをデータのタイルへと変形する。データのタイルは次いでデータの複数のクワッドに分割され、データの複数のクワッドは、表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換される。データの新たなタイルが次いで複数の表現要素を伴って形成され、そしてプロセスは単一の表現要素が残るまで繰り返す。単一の表現要素は次いで複数の制御ワード及び対応する複数のデルタ要素と共に出力ストリーム内に埋め込まれる。
【0063】
データ圧縮のシステム及び方法実装
【0064】
コンピュータ分野における当業者には明らかであろうように、本発明の実施形態の部分は、本開示の教示に従ってプログラムされる標準的な汎用の又は専用のデジタルコンピュータ又はマイクロプロセッサを用いて便利に実装され得る。
【0065】
ソフトウエア分野における当業者には明らかであろうように、本開示の教示に基づいて当業者的プログラマによって適切なソフトウエア符号化が容易に準備され得る。当業者には明らかであろうように、本発明はまた、特定用途向け集積回路の準備によって、又は標準的な要素回路の適切なネットワークを相互接続することによっても実装され得る。集積回路の実装は、ソフトウエアコード(例えばハードウエア記述言語におけるコード)の作成を通して達成されるであろうし、ソフトウエアコードは、合成されそして処理されるときに、本発明の側面を実施することができる半導体集積回路を製造する製造プロセス(例えば半導体製造工場におけるような製造プロセス)を構成するように整えられる。
【0066】
本発明の実施形態は、その上に/内部に命令(例えば、ソフトウエア、ファームウエア、及び/又はハードウエア記述言語コードを含むハードウエア命令)を有する記憶媒体(複数の記憶媒体)であるコンピュータプログラム製品を含み、命令は、本発明の実施形態の任意のプロセスを実行するようにコンピュータを制御することができ又はコンピュータに当該プロセスをさせることができる。記憶媒体は、限定はされないが、フロッピー(登録商標)ディスク、ミニディスク(MD)、光ディスク、DVD、CD−ROM、マイクロドライブ、及び光磁気ディスクを含む任意の種類のディスク、ROM、RAM、EPROM、EEPROM、DRAM、VRAM、フラッシュメモリデバイス(フラッシュカードを含む)、磁気若しくは光カード、ナノシステム(分子メモリICを含む)、RAIDデバイス、遠隔データ記憶/アーカイブ/ウェアハウジング、又は命令及び/若しくはデータを記憶するのに適した任意の種類の媒体若しくはデバイスを含む。
【0067】
コンピュータ可読媒体(複数の媒体)の任意の1つに記憶されて、本発明の実施形態は、汎用/専用両方のコンピュータ又はマイクロプロセッサのハードウエアを制御するためのソフトウエア、及び人間のユーザ又は本発明の実施形態の結果を利用する他のメカニズムとコンピュータ又はマイクロプロセッサが相互作用することを可能にするためのソフトウエアを含む。そのようなソフトウエアは、限定はされないが、デバイスドライバ、オペレーティングシステム、及びユーザアプリケーションを含む。最終的には、そのようなコンピュータ可読媒体は、前述したような本発明の実施形態を実行するためのソフトウエアを更に含む。
【0068】
汎用/専用のコンピュータ又はマイクロプロセッサのプログラミング(ソフトウエア)には、本発明の実施形態の教示を実装するためのソフトウエアモジュールが含まれ、それらは、限定はされないが、本発明の実施形態のプロセスに従って、データのスクエアを提供することと、データのスクエアをデータのタイルへと変形することと、データのタイルをデータの複数のクワッドに分割することと、各クワッドを表現要素へと変換することと、複数の表現要素を伴うデータの新たなタイルを形成することと、単一の表現要素が残るまで繰り返すことと、単一の表現要素、複数の制御ワード、及び複数のデルタ要素を出力ストリーム内に埋め込むことと、を含んでいる。
【0069】
本発明の実施形態は、本発明の構成及び動作の原理の理解を容易にする詳細を組み込んでいる特定の実施形態に関して説明されてきた。特定の実施形態及びその詳細に対するここでのそのような参照は、ここに添付される特許請求の範囲を限定することを意図してはいない。本発明の精神及び範囲から逸脱することなしに、例示を目的として選択された実施形態において多くの修正がなされ得ることが、当業者にとって明白であろう。例えば、例示される実施形態の機能を実行するために、符号化及び/若しくは埋め込みのための異なる式、並びに/又は種々のデータ及び/若しくはデータフォーマットが追加され且つ/又は除去され得る。
【特許請求の範囲】
【請求項1】
複数の圧縮されたサブアレイが形成されるように、主アレイを形成する複数の主サブアレイを圧縮されたサブアレイへと圧縮するステップと、
前記圧縮されたサブアレイを補助アレイへと配置するステップと、
前記補助アレイが前記圧縮すること及び配置することの繰り返しのための前記主アレイになるように前記圧縮すること及び配置することを単一のサブアレイが残るまで繰り返すステップと、をコンピュータが実行することを備えた階層的データ圧縮方法。
【請求項2】
前記圧縮されたサブアレイからのデータを出力ストリーム内に埋め込むステップを更に備えた請求項1の方法。
【請求項3】
データのスクエアを提供するステップと、
前記データのスクエアをデータのタイルへと変形するステップと、
左上画素、右上画素、左下画素、及び右下画素を各クワッドが有するデータの複数のクワッドに前記データのタイルを分割するステップと、
各クワッドを表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換するステップと、
前記表現要素を伴うデータの新たなタイルを形成するステップと、
前記データの新たなタイルが前記分割するステップ、変換するステップ、及び形成するステップの繰り返しのための前記データのタイルになるように、前記分割すること、前記変換すること、及び前記形成することを単一の表現要素が残るまで繰り返すステップと、
前記単一の表現要素、前記制御ワード、及び前記デルタ要素を出力ストリーム内に埋め込むステップと、をコンピュータが実行することを備えたデータ圧縮方法。
【請求項4】
前記データのスクエアはデータの2次元表面の分割である請求項3の方法。
【請求項5】
前記データはZバッファデータ、色バッファデータ、及び正規図データの少なくとも1つである請求項3の方法。
【請求項6】
前記データのスクエアをデータのタイルへと変形するステップは各データ値を新たなデータ値で置換することを備えており、前記新たなデータ値は当該データ値から隣接するデータ値を減じたものに等しい請求項5の方法。
【請求項7】
前記データのスクエアをデータのタイルへと変形するステップは各データ値を非相関データ値で置換することを備えている請求項3の方法。
【請求項8】
前記データのスクエアをデータのタイルへと変形するステップは1つ小さい成分を有する新たなデータ値で各データ値を置換することを備えている請求項3の方法。
【請求項9】
前記各クワッドを変換するステップは、
前記左上画素を前記表現要素としてセットすることと、
前記右上画素から前記左上画素を減じることによって前記第1のデルタ要素を形成することと、
前記左下画素から前記左上画素を減じることによって前記第2のデルタ要素を形成することと、
前記右下画素から前記左下画素を減じることによって前記第3のデルタ要素を形成することと、
前記デルタ要素の間での相関に従って前記制御ワードをセットすることとを備えている請求項3の方法。
【請求項10】
制御情報が前記出力ストリーム内に埋め込まれる請求項3の方法。
【請求項11】
サブタイルのディレクトリが前記出力ストリーム内に埋め込まれ、前記サブタイルのディレクトリは前記分割するステップ、変換するステップ、及び形成するステップの結果から形成される請求項3の方法。
【請求項12】
前記埋め込むことはサブタイルパターンに追随する請求項3の方法。
【請求項13】
前記デルタ要素をそれらに関連する制御ワードに従って符号化するステップを更に備えた請求項3の方法。
【請求項14】
データ圧縮方法を実行することを実行可能な命令のプログラムを有形的に実施する機械によって可読なプログラム記憶デバイスであって、
前記データ圧縮方法は、
データのスクエアを提供するステップと、
前記データのスクエアをデータのタイルへと変形するステップと、
左上画素、右上画素、左下画素、及び右下画素を各クワッドが有するデータの複数のクワッドに前記データのタイルを分割するステップと、
各クワッドを表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換するステップと、
前記表現要素を伴うデータの新たなタイルを形成するステップと、
前記データの新たなタイルが前記分割するステップ、変換するステップ、及び形成するステップの繰り返しのための前記データのタイルになるように、前記分割すること、前記変換すること、及び前記形成することを単一の表現要素が残るまで繰り返すステップと、
前記単一の表現要素、前記制御ワード、及び前記デルタ要素を出力ストリーム内に埋め込むステップと、を備えているプログラム記憶デバイス。
【請求項15】
前記データのスクエアはデータの2次元表面の分割である請求項14のプログラム記憶デバイス。
【請求項16】
前記データはZバッファデータ、色バッファデータ、及び正規図データの少なくとも1つである請求項14のプログラム記憶デバイス。
【請求項17】
前記データのスクエアをデータのタイルへと変形するステップは各データ値を新たなデータ値で置換することを備えており、前記新たなデータ値は当該データ値から隣接するデータ値を減じたものに等しい請求項16のプログラム記憶デバイス。
【請求項18】
前記データのスクエアをデータのタイルへと変形するステップは各データ値を非相関データ値で置換することを備えている請求項14のプログラム記憶デバイス。
【請求項19】
前記データのスクエアをデータのタイルへと変形するステップは1つ小さい成分を有する新たなデータ値で各データ値を置換することを備えている請求項14のプログラム記憶デバイス。
【請求項20】
前記各クワッドを変換するステップは、
前記左上画素を前記表現要素としてセットすることと、
前記右上画素から前記左上画素を減じることによって前記第1のデルタ要素を形成することと、
前記左下画素から前記左上画素を減じることによって前記第2のデルタ要素を形成することと、
前記右下画素から前記左下画素を減じることによって前記第3のデルタ要素を形成することと、
前記デルタ要素の間での相関に従って前記制御ワードをセットすることとを備えている請求項14のプログラム記憶デバイス。
【請求項21】
制御情報が前記出力ストリーム内に埋め込まれる請求項14のプログラム記憶デバイス。
【請求項22】
サブタイルのディレクトリが前記出力ストリーム内に埋め込まれ、前記サブタイルのディレクトリは前記分割するステップ、変換するステップ、及び形成するステップの結果から形成される請求項14のプログラム記憶デバイス。
【請求項23】
前記埋め込むことはサブタイルパターンに追随する請求項14のプログラム記憶デバイス。
【請求項24】
前記デルタ要素をそれらに関連する制御ワードに従って符号化するステップを更に備えた請求項14のプログラム記憶デバイス。
【請求項1】
複数の圧縮されたサブアレイが形成されるように、主アレイを形成する複数の主サブアレイを圧縮されたサブアレイへと圧縮するステップと、
前記圧縮されたサブアレイを補助アレイへと配置するステップと、
前記補助アレイが前記圧縮すること及び配置することの繰り返しのための前記主アレイになるように前記圧縮すること及び配置することを単一のサブアレイが残るまで繰り返すステップと、をコンピュータが実行することを備えた階層的データ圧縮方法。
【請求項2】
前記圧縮されたサブアレイからのデータを出力ストリーム内に埋め込むステップを更に備えた請求項1の方法。
【請求項3】
データのスクエアを提供するステップと、
前記データのスクエアをデータのタイルへと変形するステップと、
左上画素、右上画素、左下画素、及び右下画素を各クワッドが有するデータの複数のクワッドに前記データのタイルを分割するステップと、
各クワッドを表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換するステップと、
前記表現要素を伴うデータの新たなタイルを形成するステップと、
前記データの新たなタイルが前記分割するステップ、変換するステップ、及び形成するステップの繰り返しのための前記データのタイルになるように、前記分割すること、前記変換すること、及び前記形成することを単一の表現要素が残るまで繰り返すステップと、
前記単一の表現要素、前記制御ワード、及び前記デルタ要素を出力ストリーム内に埋め込むステップと、をコンピュータが実行することを備えたデータ圧縮方法。
【請求項4】
前記データのスクエアはデータの2次元表面の分割である請求項3の方法。
【請求項5】
前記データはZバッファデータ、色バッファデータ、及び正規図データの少なくとも1つである請求項3の方法。
【請求項6】
前記データのスクエアをデータのタイルへと変形するステップは各データ値を新たなデータ値で置換することを備えており、前記新たなデータ値は当該データ値から隣接するデータ値を減じたものに等しい請求項5の方法。
【請求項7】
前記データのスクエアをデータのタイルへと変形するステップは各データ値を非相関データ値で置換することを備えている請求項3の方法。
【請求項8】
前記データのスクエアをデータのタイルへと変形するステップは1つ小さい成分を有する新たなデータ値で各データ値を置換することを備えている請求項3の方法。
【請求項9】
前記各クワッドを変換するステップは、
前記左上画素を前記表現要素としてセットすることと、
前記右上画素から前記左上画素を減じることによって前記第1のデルタ要素を形成することと、
前記左下画素から前記左上画素を減じることによって前記第2のデルタ要素を形成することと、
前記右下画素から前記左下画素を減じることによって前記第3のデルタ要素を形成することと、
前記デルタ要素の間での相関に従って前記制御ワードをセットすることとを備えている請求項3の方法。
【請求項10】
制御情報が前記出力ストリーム内に埋め込まれる請求項3の方法。
【請求項11】
サブタイルのディレクトリが前記出力ストリーム内に埋め込まれ、前記サブタイルのディレクトリは前記分割するステップ、変換するステップ、及び形成するステップの結果から形成される請求項3の方法。
【請求項12】
前記埋め込むことはサブタイルパターンに追随する請求項3の方法。
【請求項13】
前記デルタ要素をそれらに関連する制御ワードに従って符号化するステップを更に備えた請求項3の方法。
【請求項14】
データ圧縮方法を実行することを実行可能な命令のプログラムを有形的に実施する機械によって可読なプログラム記憶デバイスであって、
前記データ圧縮方法は、
データのスクエアを提供するステップと、
前記データのスクエアをデータのタイルへと変形するステップと、
左上画素、右上画素、左下画素、及び右下画素を各クワッドが有するデータの複数のクワッドに前記データのタイルを分割するステップと、
各クワッドを表現要素、第1のデルタ要素、第2のデルタ要素、第3のデルタ要素、及び制御ワードへと変換するステップと、
前記表現要素を伴うデータの新たなタイルを形成するステップと、
前記データの新たなタイルが前記分割するステップ、変換するステップ、及び形成するステップの繰り返しのための前記データのタイルになるように、前記分割すること、前記変換すること、及び前記形成することを単一の表現要素が残るまで繰り返すステップと、
前記単一の表現要素、前記制御ワード、及び前記デルタ要素を出力ストリーム内に埋め込むステップと、を備えているプログラム記憶デバイス。
【請求項15】
前記データのスクエアはデータの2次元表面の分割である請求項14のプログラム記憶デバイス。
【請求項16】
前記データはZバッファデータ、色バッファデータ、及び正規図データの少なくとも1つである請求項14のプログラム記憶デバイス。
【請求項17】
前記データのスクエアをデータのタイルへと変形するステップは各データ値を新たなデータ値で置換することを備えており、前記新たなデータ値は当該データ値から隣接するデータ値を減じたものに等しい請求項16のプログラム記憶デバイス。
【請求項18】
前記データのスクエアをデータのタイルへと変形するステップは各データ値を非相関データ値で置換することを備えている請求項14のプログラム記憶デバイス。
【請求項19】
前記データのスクエアをデータのタイルへと変形するステップは1つ小さい成分を有する新たなデータ値で各データ値を置換することを備えている請求項14のプログラム記憶デバイス。
【請求項20】
前記各クワッドを変換するステップは、
前記左上画素を前記表現要素としてセットすることと、
前記右上画素から前記左上画素を減じることによって前記第1のデルタ要素を形成することと、
前記左下画素から前記左上画素を減じることによって前記第2のデルタ要素を形成することと、
前記右下画素から前記左下画素を減じることによって前記第3のデルタ要素を形成することと、
前記デルタ要素の間での相関に従って前記制御ワードをセットすることとを備えている請求項14のプログラム記憶デバイス。
【請求項21】
制御情報が前記出力ストリーム内に埋め込まれる請求項14のプログラム記憶デバイス。
【請求項22】
サブタイルのディレクトリが前記出力ストリーム内に埋め込まれ、前記サブタイルのディレクトリは前記分割するステップ、変換するステップ、及び形成するステップの結果から形成される請求項14のプログラム記憶デバイス。
【請求項23】
前記埋め込むことはサブタイルパターンに追随する請求項14のプログラム記憶デバイス。
【請求項24】
前記デルタ要素をそれらに関連する制御ワードに従って符号化するステップを更に備えた請求項14のプログラム記憶デバイス。
【図1A】
【図1B】
【図1C】
【図2A】
【図2B】
【図3A】
【図3B】
【図3C】
【図3D】
【図4】
【図5】
【図6】
【図7】
【図8】
【図1B】
【図1C】
【図2A】
【図2B】
【図3A】
【図3B】
【図3C】
【図3D】
【図4】
【図5】
【図6】
【図7】
【図8】
【公表番号】特表2012−527836(P2012−527836A)
【公表日】平成24年11月8日(2012.11.8)
【国際特許分類】
【出願番号】特願2012−511956(P2012−511956)
【出願日】平成22年5月18日(2010.5.18)
【国際出願番号】PCT/US2010/035228
【国際公開番号】WO2010/135307
【国際公開日】平成22年11月25日(2010.11.25)
【出願人】(591016172)アドバンスト・マイクロ・ディバイシズ・インコーポレイテッド (439)
【氏名又は名称原語表記】ADVANCED MICRO DEVICES INCORPORATED
【Fターム(参考)】
【公表日】平成24年11月8日(2012.11.8)
【国際特許分類】
【出願日】平成22年5月18日(2010.5.18)
【国際出願番号】PCT/US2010/035228
【国際公開番号】WO2010/135307
【国際公開日】平成22年11月25日(2010.11.25)
【出願人】(591016172)アドバンスト・マイクロ・ディバイシズ・インコーポレイテッド (439)
【氏名又は名称原語表記】ADVANCED MICRO DEVICES INCORPORATED
【Fターム(参考)】
[ Back to top ]