(57)【要約】  本発明は、電子画像データセットを圧縮するためのシステム及び方法を提供する。画像は複数のアレイに分割され、その各々は、ウェーブレット変換を用いて別個に変換される。結果として得られるウェーブレット係数は次いで、エントロピー・エンコード・スキームを用いてエンコードされて、圧縮されたデータセットを与える。【選択図】図２
2010537534.tif 000002
【特許請求の範囲】
【請求項１】
二次元電子データセットを圧縮するための方法であって、
前記データセットを複数のデータアレイに分割するステップと、
各アレイにウェーブレット変換を行なって、複数のウェーブレット係数を与えるステップと、
エントロピー・エンコード・スキームを用いて、前記ウェーブレット係数の少なくとも幾つかをエンコードし、圧縮された電子データセットを与えるステップと、
を含むことを特徴とする方法。
【請求項２】
前記データセットは画像データセットであり、各データアレイは、画像の別個の連続する区域に対応することを特徴とする、請求項１に記載の方法。
【請求項３】
前記ウェーブレット変換を行なう前に、前記データセットを所定のデータ・フォーマットに変換するステップをさらに含むことを特徴とする、請求項１又は請求項２に記載の方法。
【請求項４】
前記所定のデータ・フォーマットは、８ビット符号なし整数のデータ・フォーマットであることを特徴とする、請求項３に記載の方法。
【請求項５】
前記データセットを変換するステップは、より大きいデータ・ユニットを複数のより小さいデータ・ユニットに分割するステップを含むことを特徴とする、請求項３又は請求項４に記載の方法。
【請求項６】
前記より大きいデータ・ユニットを分割するステップは、該より大きいデータ・ユニットを複数の別個のデータチャネルに分割するステップを含むことを特徴とする、請求項５に記載の方法。
【請求項７】
前記ウェーブレット変換を行なうステップは、モジュロ演算を用いて実行されることを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項８】
前記モジュロ演算は、所定のデータ・フォーマットに対応することを特徴とする、請求項７に記載の方法。
【請求項９】
前記ウェーブレット変換を行なうステップ及び前記エンコードするステップは、異なるデータアレイに対して並列して実行されることを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項１０】
前記データセットは、複数のデータチャネル画像の単一のデータチャネルであり、前記方法ステップの各々は、前記複数のデータチャネルに適用されることを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項１１】
前記画像は色データを含み、色変換を用いて前記色データを異なる色空間に変換するステップをさらに含むことを特徴とする、請求項１０に記載の方法。
【請求項１２】
前記色データを異なる色空間に変換するステップは、ウェーブレット変換を行なう前に実行されることを特徴とする、請求項１１に記載の方法。
【請求項１３】
前記色データを変換するステップは、ウェーブレット変換を行なうステップの後に行われ、複数の代替的な色変換を行って複数の結果をもたらし、エンコードのための最良の結果を選択するステップを含むことを特徴とする、請求項１１に記載の方法。
【請求項１４】
前記色変換は、モジュロ演算を用いて行なわれることを特徴とする請求項１１、請求項１２、又は請求項１３に記載の方法。
【請求項１５】
前記ウェーブレット変換は、更新ステップを含まないことを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項１６】
前記ウェーブレット係数を評価し、該ウェーブレット係数の前記評価の結果に基づいて、エントロピー・エンコード・スキームを選択するステップをさらに含むことを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項１７】
前記係数は各アレイについて評価され、エンコード・スキームが各アレイについて選択されることを特徴とする、請求項１６に記載の方法。
【請求項１８】
前記評価するステップは、前記ウェーブレット係数の分布を評価するステップを含むことを特徴とする、請求項１６又は請求項１７に記載の方法。
【請求項１９】
前記ウェーブレット変換は線形ウェーブレット変換であることを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項２０】
前記ウェーブレット係数は、リフティング・スキームを用いて計算されることを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項２１】
前記ウェーブレット変換を行なうステップは、各データアレイに対して複数のウェーブレット変換演算を行なうステップを含むことを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項２２】
第１のウェーブレット変換演算は、ハール変換演算であることを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項２３】
二次元電子データセットを圧縮するための装置であって、
前記データセットを複数のデータアレイに分割するための分割手段と、
コンプレッサ・ユニットと、
を含み、前記コンプレッサ・ユニットは、各データアレイにウェーブレット変換を行なって、各データアレイについての複数のウェーブレット係数を出力するための手段と、エントロピー・エンコード・スキームを用いて、前記複数のウェーブレット係数の少なくとも幾つかをエンコードするためのエンコード手段とを含むことを特徴とする装置。
【請求項２４】
前記装置は、グラフィックス・レンダリング・システムであることを特徴とする、請求項２３に記載の装置。
【請求項２５】
前記電子データセットは画像データセットであり、各データアレイは、画像の別個の連続する区域に対応することを特徴とする、請求項２３又は請求項２４に記載の装置。
【請求項２６】
ウェーブレット変換を行なう前に、前記データセットを、所定のデータ・フォーマットを有するデータチャネルに変換するための再フォーマット・ユニットをさらに含むことを特徴とする、請求項２３から請求項２５までのいずれか１項に記載の装置。
【請求項２７】
色画像データに対して色変換を行なうための色変換手段をさらに含むことを特徴とする、請求項２３から請求項２６までのいずれか１項に記載の装置。
【請求項２８】
前記ウェーブレット変換を行なうための手段は、モジュロ演算を用いることを特徴とする、請求項２３から請求項２７までのいずれか１項に記載の装置。
【請求項２９】
前記ウェーブレット係数を評価し、該ウェーブレット係数の前記評価の結果に基づいてエントロピー・エンコード・スキームを選択するための評価手段をさらに含むことを特徴とする、請求項２３から請求項２８までのいずれか１項に記載の装置。
【請求項３０】
二次元電子データセットを復元するための方法であって、
少なくとも１つのエントロピー・デコード・スキームを用いて前記データセットをデコードし、複数の係数の組を生成するステップと、
前記係数に対して逆ウェーブレット変換を行なって、複数のデータアレイを生成するステップと、
前記複数のデータアレイを結合して二次元データセットを生成するステップと、
を含むことを特徴とする方法。
【請求項３１】
前記電子データセットは画像データセットであり、各データアレイは、画像の別個の連続する区域に対応することを特徴とする、請求項３０に記載の方法。
【請求項３２】
二次元電子データセットを復元するための装置であって、
少なくとも１つのエントロピー・デコード・スキームを用いて前記データセットをデコードして複数の組の係数を生成するための手段と、前記係数に対して逆ウェーブレット変換を行なって複数のデータアレイを生成するための手段とを含むデコンプレッサ・ユニットと、
前記複数のデータアレイを結合して二次元データセットを生成するための手段と、
を含むことを特徴とする装置。
【請求項３３】
前記装置はグラフィックス・レンダリング・システムであることを特徴とする、請求項３２に記載の装置。
【請求項３４】
前記電子データセットは画像データセットであり、各データアレイは、画像の別個の連続する区域に対応することを特徴とする、請求項３２又は請求項３３に記載の装置。
【請求項３５】
二次元電子データセットを圧縮するための方法であって、
前記データセットを複数のデータアレイに分割するステップと、
各データアレイにウェーブレット変換を行なって、各アレイについての複数のウェーブレット係数を与えるステップと、
前記複数のウェーブレット係数の各々を処理して、各アレイについての値を与えるステップと、
そのアレイについての前記値に基づいて各アレイについてのエンコード・スキームを選択し、圧縮された電子データセットを与えるステップと、
を含むことを特徴とする方法。
【請求項３６】
前記エンコード・スキームを選択するステップは、エンコードを行わない結果をもたらす場合があることを特徴とする、請求項３５に記載の方法。
【請求項３７】
二次元電子データセットを圧縮するための装置であって、
前記データセットを複数のデータアレイに分割するための分割手段と、
コンプレッサ・ユニットと、
を含み、前記コンプレッサ・ユニットは、各データアレイにウェーブレット変換を行なって、各データアレイについての複数のウェーブレット係数を出力するための手段と、前記係数を処理して、各アレイについての値を生成するためのプロセッサと、前記値に基づいて、前記ウェーブレット係数をエンコードするためのエンコード・スキームを選択するための選択手段とを含むことを特徴とする装置。
【請求項３８】
二次元電子データセットを圧縮するための方法であって、
前記データセットに対して、モジュロ演算を用いるウェーブレット変換を行なって、複数の係数を生成するステップと、
エントロピー・コードを用いて前記係数をエンコードし、圧縮された電子データセットを与えるステップと、
を含むことを特徴とする方法。
【請求項３９】
二次元電子データセットを圧縮するための方法であって、
前記データセットに対して、更新ステップを含まないウェーブレット変換を行なって、複数の係数を与えるステップと、
エントロピー・コードを用いて前記係数をエンコードし、圧縮された電子データセットを与えるステップと、
を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二次元データのデータ圧縮のための方法及びシステムに関する。具体的には、本発明は、メモリの帯域幅を減少させるグラフィックス・レンダリング・システムにおけるデータ圧縮に関する。
【背景技術】
【０００２】
可逆型及び非可逆型の両方のデータ圧縮は、大量のデータが格納され読み出される、グラフィックス・フレームバッファを含む多くの用途において、非常に望ましい。従って、携帯通信装置のような小型装置におけるグラフィックスの使用が増大するに伴って、圧縮データの使用は極めて望ましいものとなっている。
【０００３】
一般的な非可逆型（ｌｏｓｓｙ）画像圧縮は、画像全体に適用される場合、コンピュータグラフィックにおいてはＪＰＥＧ及びＧＩＦ等の規格で周知である。ＰＮＧ等の可逆型（ｌｏｓｓｌｅｓｓ）画像圧縮法は、一般的にあまり用いられていないが、Ｃｏｍｐｒｅｓｓ又はＺＩＰ等のいずれかの可逆圧縮ツールを、圧縮されていないソースに適用することもできる。しかしながら、これらの全ての方法に関連する問題は、ａ）これらの方法は、オンザフライ圧縮及び復元には費用がかかること、及び、ｂ）これらの方法により、データへのランダム・アクセスが可能ではないことである。
【０００４】
テクスチャ圧縮のために特別に設計されたものなどの幾つか非可逆圧縮スキーム（幾つかの既知のスキームの再検討が非特許文献１において与えられる）は、確かにデータへのランダム・アクセス及び簡単な復元ステップを提供する。しかしながら、これらの方法の主要な欠点は、圧縮アルゴリズムは、復元アルゴリズムよりはるかに費用がかかり（すなわち、これらの方法は、非対称エンコード及びデコードを用いる）、従って、リアルタイム演算には適していないことである。また、可逆圧縮を提供するようにこれらの方法を適合させるのは困難でもある。
【０００５】
Ｒａｓｍｕｓｓｏｎ他のシステム（手短に説明される）を例外として、データバッファ（フレーム及びＺバッファ等の）のための対称的な（すなわち、エンコード費用及びデコード費用がおよそ等しい）リアルタイム圧縮システムは、これまでかなり簡単なスキームに限定されていた。こうしたシステムの再検討を、非特許文献２に見出すことができる。
【０００６】
Ｒａｓｍｕｓｓｏｎ他はまた、ＲＧＢデータについての、より高度な圧縮及び復元システムも提示するが、このシステムは、数値の動的範囲の拡大を必要とし、これによりレジスタサイズに関する費用が発生する。このシステムはまた、一連の予測スキームを用いるだけであり、そのことは、並列計算を妨げる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｓ．Ｆｅｎｎｅｙ著、「Ｔｅｘｔｕｒｅ  Ｃｏｍｐｒｅｓｓｉｏｎ  ｕｓｉｎｇ  Ｌｏｗ−Ｆｒｅｑｕｅｎｃｙ  Ｓｉｇｎａｌ  Ｍｏｄｕｌａｔｉｏｎ」、Ｇｒａｐｈｉｃｓ  Ｈａｒｄｗａｒｅ  ２００３年
【非特許文献２】Ｒａｓｍｕｓｓｏｎ、Ｈａｓｓｅｌｇｒｅｎ及びＡｋｅｎｉｎｅ−Ｍｏｌｌｅｒ著、「Ｅｘａｃｔ  ａｎｄ  Ｅｒｒｏｒ−ｂｏｕｎｄｅｄ  Ａｐｐｒｏｘｉｍａｔｅ  Ｃｏｌｏｒ  Ｂｕｆｆｅｒ  Ｃｏｍｐｒｅｓｓｉｏｎ  ａｎｄ  Ｄｅｃｏｍｐｒｅｓｓｉｏｎ」Ｇｒａｐｈｉｃｓ  Ｈａｒｄｗａｒｅ  ２００７年
【非特許文献３】Ｗｉｍ  Ｓｗｅｌｄｅｎｓ及びＰｅｔｅｒ  Ｓｃｈｒｏｄｅｒ著、「Ｂｕｉｌｄｉｎｇ  Ｙｏｕｒ  Ｏｗｎ  Ｗａｖｅｌｅｔｓ  ａｔ  Ｈｏｍｅ」１９９６年、ｈｔｔｐ：／／ｃｉｔｅｓｅｅｒ．ｉｓｔ．ｐｓｕ．ｅｄｕ／ｓｗｅｌｄｅｎｓ９６ｂｕｉｌｄｉｎｇ．ｈｔｍｌ
【非特許文献４】Ｍａｌｖｅｒ及びＳｕｌｌｉｖａｎ著、「ＹＣｏＣｇ−Ｒ：Ａ  Ｃｏｌｏｒ  Ｓｐａｃｅ  ｗｉｔｈ  ＲＧＢ  Ｒｅｖｅｒｓｉｂｉｌｉｔｙ  ａｎｄ  Ｌｏｗ  Ｄｙｎａｍｉｃ  Ｒａｎｇｅ」
【非特許文献５】Ｈｅｎｒｉｑｕｅ  Ｍａｌｖｅｒ及びＧａｒｙ  Ｓｕｌｌｉｖａｎ、Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐ，ＪＶＴ  ＰＥｘｔ  Ａｄ  Ｈｏｃ  Ｇｒｏｕｐ  Ｍｅｅｔｉｎｇ：２００３年７月２２〜２４日、Ｔｒｏｎｄｈｅｉｍ（ｈｔｔｐ：／／ｒｅｓｅａｒｃｈ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ／ｕｓｅｒｓ／ｍａｌｖａｒ／ｐａｐｅｒｓ／ＪＶＴ−Ｉ０１４ｒ３．ｐｄｆ）
【非特許文献６】Ｌｉ他著、「Ａ  Ｒｅｖｅｒｓｉｂｌｅ  Ｃｏｌｏｒ  Ｔｒａｎｓｆｏｒｍ  ｆｏｔ  １６−ｂｉｔ−ｃｏｌｏｒ  Ｐｉｃｕｔｒｅ  Ｃｏｄｉｎｇ」、ｔｈｅ  １２th  ａｎｎｕａｌ  ＡＣＭ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａの予稿集、２００４年
【非特許文献７】Ｗｅｉｎｂｅｒｇｅｒ他著、「Ｔｈｅ  ＬＯＣＯ−Ｉ  Ｌｏｓｓｌｅｓｓ  Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ａｌｇｏｒｉｔｈｍ：Ｐｒｉｎｃｉｐｌｅｓ  ａｎｄ  Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ  ｉｎｔｏ  ＪＰＥＧ−ＬＳ」
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、上述の問題を解決するための方法及びシステムを提供することである。
【課題を解決するための手段】
【０００９】
本発明は、ここで参照すべき特許請求の範囲において定義される。有利な特徴は、従属項において定義される。
第１の態様において、本発明は、二次元電子データセットを圧縮するための方法であって、
データセットを複数のデータアレイに分割するステップと、
各アレイにウェーブレット変換を行なって、複数のウェーブレット係数を与えるステップと、
エントロピー・エンコード・スキームを用いて、ウェーブレット係数の少なくとも幾つかをエンコードするステップと、
を含む方法である。
【００１０】
電子データセットは、画像データセットであることが好ましい。各データアレイは、画像の別個の連続する区域に対応することが好ましい。事実上、データセットをデータアレイに分割するステップは、次に、画像をタイルに分割するステップである。タイルは任意のサイズ及び形状のものであってもよいが、矩形であることが好ましい。
【００１１】
本方法は、ウェーブレット変換を行なう前に、データセットを所定のデータ・フォーマットに変換するステップをさらに含むことが好ましい。所定のデータ・フォーマットは、８ビット符号なし整数のデータ・フォーマットであることが好ましい。データセットを変換するステップは、より大きいデータ・ユニットを複数のより小さいデータ・ユニットに分割するステップを含むことが好ましい。
【００１２】
より大きいデータ・ユニットを分割するステップは、より大きいデータ・ユニットを複数の別個のデータチャネルに分割するステップを含むことが好ましい。
【００１３】
ウェーブレット変換を行なうステップは、モジュロ演算を用いて実行されることが好ましい。モジュロ演算は、所定のデータ・フォーマットに対応することが好ましい。
【００１４】
ウェーブレット変換を行なうステップ及びエンコードするステップは、異なるデータアレイに対して並列して実行されることが好ましい。
【００１５】
データセットは、複数のデータチャネル画像の単一のデータチャネルであり、方法ステップの各々は、複数のデータチャネル上で実行されることが好ましい。画像は色データを含み、本方法は、色変換を用いて色データを異なる色空間に変換するステップをさらに含むことができる。色データを異なる色空間に変換するステップは、ウェーブレット変換を行なう前に実行することができる。代替的には、色データを変換するステップは、ウェーブレット変換を行なうステップの後に実行され、複数の代替的な色変換を行なって複数の結果をもたらし、エンコードのために最良の結果を選択するステップを含む。
【００１６】
色変換は、モジュロ演算を用いて行なわれることが好ましい。
【００１７】
ウェーブレット変換は、第２世代のウェーブレットであることが好ましい。ウェーブレット変換は更新ステップを含まないことが好ましい。更新ステップを除去することは、可逆型変換を用いるときには全く問題がない。
【００１８】
本方法は、ウェーブレット係数を評価し、ウェーブレット係数の評価結果に基づいて、エントロピー・エンコード・スキームを選択するステップをさらに含むことが好ましい。係数が、各アレイについて評価され、エンコード・スキームが各アレイについて選択されることが好ましい。評価するステップは、ウェーブレット係数の分布を評価するステップを含むことが好ましい。
【００１９】
ウェーブレット変換は線形ウェーブレット変換であることが好ましい。代替的には、ウェーブレット変換はハール変換とすることができる。ウェーブレット係数は、リフティング・スキームを用いて計算されることが好ましい。
【００２０】
ウェーブレット変換を行なうステップは、各データアレイに対して複数のウェーブレット変換演算を行なうステップを含むことが好ましい。第１のウェーブレット変換演算は、ハール変換演算であることが好ましい。
【００２１】
第２の態様によると、本発明は、二次元電子データセットを圧縮するためのシステムであって、
データセットを複数のデータアレイに分割するための分割手段と、
コンプレッサ・ユニットと、
を含み、コンプレッサ・ユニットは、各アレイにウェーブレット変換を行なって、各データアレイについての複数のウェーブレット係数を出力するための手段と、エントロピー・エンコード・スキームを用いて、複数のウェーブレット係数の少なくとも幾つかをエンコードするためのエンコード手段とを含むシステムである。
【００２２】
本システムは、グラフィックス・レンダリング・システムの一部であることが好ましい。電子データセットは、画像データセットであることが好ましい。各データアレイは、画像の別個の連続する区域に対応することが好ましい。
【００２３】
本システムは、ウェーブレット変換を行なう前に、データセットを、所定のデータ・フォーマットを有するデータチャネルに変換するための再フォーマット・ユニットをさらに含むことが好ましい。
【００２４】
本システムは、色画像データに色変換を行なうための色変換手段をさらに含むことが好ましい。
【００２５】
ウェーブレット変換を行なうための手段は、モジュロ演算を用いることが好ましい。
【００２６】
本システムは、ウェーブレット係数を評価し、ウェーブレット係数の評価の結果に基づいてエントロピー・エンコード・スキームを選択するための評価手段をさらに含むことが好ましい。
【００２７】
第３の態様によると、本発明は、二次元電子データセットを復元するための方法であって、
少なくとも１つのエントロピー・デコード・スキームを用いてデータセットをデコードして、複数の組の係数を生成するステップと、
係数に逆ウェーブレット変換を行なって、複数のデータアレイを生成するステップと、
複数のデータアレイを結合して二次元データセットを生成するステップと、
を含む方法である。
【００２８】
電子データセットは、画像データセットであることが好ましい。各データアレイは、画像の別個の連続する区域に対応することが好ましい。
【００２９】
第４の態様によると、本発明は、二次元電子データセットを復元するための装置であって、
少なくとも１つのエントロピー・デコード・スキームを用いてデータセットをデコードして、複数の組の係数を生成するための手段と、係数に逆ウェーブレット変換を行なって複数のデータアレイを生成するための手段とを含むデコンプレッサ・ユニットと、
複数のデータアレイを結合して二次元データセットを生成するための手段とを含む装置である。
【００３０】
本装置は、グラフィックス・レンダリング・システムの一部であることが好ましい。電子データセットは、画像データセットであることが好ましい。各データアレイは、画像の別個の連続する区域に対応することが好ましい。
【００３１】
第５の態様によると、本発明は、二次元電子データセットを圧縮するための方法であって、
データセットをデータアレイに分割するステップと、
各アレイにウェーブレット変換を行なって、各アレイについての複数のウェーブレット係数を与えるステップと、
複数の係数の各々を処理して、各アレイについての値を生成するステップと、
そのアレイについての値に基づいて各アレイについてのエンコード・スキームを選択するステップとを含む方法である。
【００３２】
エンコード・スキームを選択するステップは、エンコードを行わない結果をもたらすことが好ましい。
電子データセットは、画像データセットであることが好ましい。各データアレイは、画像の連続する区域に対応することが好ましい。
【００３３】
第６の態様によると、本発明は、二次元電子データセットを圧縮するための装置であって、
データセットを複数のデータアレイに分割するための分割手段と、
コンプレッサ・ユニットと、
を含み、コンプレッサ・ユニットは、各データアレイにウェーブレット変換を行なって、各データアレイについての複数のウェーブレット係数を出力するための手段と、係数を処理して、各アレイについての値を生成するためのプロセッサと、この値に基づいて、ウェーブレット係数をエンコードするためのエンコード・スキームを選択するための選択手段とを含む装置である。
本装置は、グラフィックス・レンダリング・システムの一部であることが好ましい。電子データセットは、画像データセットであることが好ましい。各データアレイは、画像の連続する区域に対応することが好ましい。
【００３４】
本発明の第７の態様によると、本発明は、二次元電子データセットを圧縮するための方法であって、
データセットに対して、モジュロ演算を用いるウェーブレット変換を行なうステップと、
エントロピー・コードを用いて係数をエンコードするステップと、
を含む方法である。
【００３５】
本発明の第８の態様によると、本発明は、二次元電子データセットを圧縮するための方法であって、
データセットに対して、更新ステップを含まないウェーブレット変換を行なって、複数の係数を与えるステップと、
エントロピー・コードを用いて係数をエンコードするステップと、
を含む方法である。
【図面の簡単な説明】
【００３６】
【図１】本発明による、グラフィックス・レンダリング・システムの概略図である。
【図２】図１のグラフィックス・レンダリング・システムをより詳細に示す。
【図３】異なるデータチャネルに対する本発明の１つの実施形態の方法ステップを示す概略図である。
【図４】図２に示すコンプレッサ／デコンプレッサ・ユニットの概略図である。
【図５ａ】ウェーブレット変換を行なうための疑似コードを示す。
【図５ｂ】ウェーブレット変換を行なうための疑似コードを示す。
【図６ａ】ウェーブレット変換前の画像タイルの赤色チャネルのヒストグラムである。
【図６ｂ】ウェーブレット変換後の図６ａの画像タイルの赤色チャネルのヒストグラムである。
【図７】本発明で用いるための第１の可変長のエンコード・スキームを示す。
【図８】本発明で用いるための第２の可変長のエンコード・スキームを示す。
【図９】本発明で用いるための第３の可変長のエンコード・スキームを示す。
【図１０】ウェーブレット変換後のＲＧＢチャネルデータと、ウェーブレット変換後の変換されたＹＣｍＣｎデータとの間の差異を示す。
【図１１】３２ビットのデータを８ビットのデータのチャネルに分割することを示す。
【図１２】１６ビットのデータを８ビットのデータのチャネルに分割することを示す。
【図１３】ハール・ウェーブレット変換と線形ウェーブレット変換との間の比較を示す。
【発明を実施するための形態】
【００３７】
ここで本発明の例を、添付図面を参照して詳細に説明する。
図１は、電子装置におけるグラフィックス・レンダリング・システムの概略図である。ＣＰＵ１は、グラフィックス・メモリ３内に格納されたフレームバッファ及び幾何学情報等のバッファデータにアクセスする、グラフィックス・レンダリング・サブシステム２と通信する。メモリ内に格納されたレンダリングされた画像は次いで、表示装置等の出力装置４に転送することができる。
【００３８】
本発明によるレンダリング・システムにおいて、二次元データセットとして考えることができる画像データのチャネルは、一連のアレイ又はタイルに区分される。各タイルは個々に圧縮される。タイルのサイズは任意に選択することができるが、２の累乗の次元であることが好ましく、統一される必要はない。選択されたタイルサイズは、改善された圧縮率（大きいタイル）と、より短い待ち時間及びより小さい内部データ格納サイズ（小さいタイル）との間のバランスを表わす。最も実用的な適用のための良好な妥協案は、約３２×３２ピクセルのタイルサイズであることが分かっている。画像データは、スカラー値及び／又はベクトルの組とすることができる。
【００３９】
図２は、本発明の好ましい実施形態のレンダリング・システムをより詳細に示す。グラフィックス・レンダリング・システム２は、レンダラ１０と、コンプレッサ／デコンプレッサ・ユニット２０と、メモリ・インターフェース１５と、表示出力ユニット３０とを含む。レンダラ１０は、Ｚ試験及びテクスチャ・マッピングのような既知の技術を用いて、三角形及び線等のグラフィックス・プリミティブの走査変換を実行する。レンダラは、タイルベースの順番で動作する。レンダラは、メモリ・トラフィックを減少させるためのキャッシュ・ユニットを含むことができる。一部のデータは、メモリ・インターフェース・ユニット１５を介して、レンダラよって読み取られるか、又はグラフィックス・メモリ３に直接書き込まれるが、フレームバッファ等の他のデータに関しては、コンプレッサ／デコンプレッサ・ユニット２０を介して進行することが好ましい。このユニットは、外部メモリバスを介して転送する必要があるデータ量を減少させる。コンプレッサ／デコンプレッサ・ユニットは、メモリ・インターフェース・ユニット１５にアクセスできる。表示出力ユニット３０は、完成した画像データを表示装置４に送る。これは、メモリ・インターフェース・ユニット１５から直接アクセスされる圧縮されていない画像であってもよく、又は、コンプレッサ／デコンプレッサ２０を介してアクセスされる圧縮されたデータであってもよい。単一のエンティティとして示されるが、コンプレッサ／デコンプレッサ・ユニットは、性能を高めるために、複数の並列圧縮／復元ユニットを含むことができる。
【００４０】
図３は、本発明に従ったコンプレッサ／デコンプレッサ・ユニットによって実行される可逆圧縮法の概略図を示す。図３は、異なるデータ・フォーマットに対する圧縮法を示し、異なるデータ・フォーマットは、別個の列（ａ）（ｂ）（ｃ）及び（ｄ）に示されている。データ圧縮のための本方法のステップは、図の上から下へ順番に示される。データ復元においては、ステップは単純に逆になり、従ってページの下から上に示される。
【００４１】
本例においては、この圧縮法は、８ビットの符号なしデータに対して機能する。これは、列（ａ）に示される。列（ｂ）に示す１６ビット浮動小数点データ（ＦＬＯＡＴ１６）及び１６ビット符号付き整数データ（（Ｕ）ＩＮＴ１６）、並びに、列（ｃ）に示されるような３２ビット浮動小数点データ（ＦＬＯＡＴ３２）等の他のデータ・フォーマットが、最初に、８ビット符号なし整数データ（ＵＮＩＴ８）チャネルに分割される。これは、ステップ１２０として示される。
【００４２】
列（ｄ）は、ＲＧＢ（Ａ）色データのための方法を示す。有利なことに、ＲＧＢ（Ａ）色データは、異なる色空間、この例ではＹＣｍＣｎ色空間に変換することができ、又は、さらに詳細に説明されるように、ＪＰＥＧ−ＬＳ変換を用いて変換することができる。この変換ステップ１２５は、ウェーブレット変換に先行するものとして示されるが、ウェーブレット変換の後に実行してもよい。色データの異なるチャネルは、８ビット符号なし整数のデータチャネルである。アルファ・チャネルＡがＲＧＢ（Ａ）データ内に含まれる場合、このアルファ・チャネルＡは、色変換と関係なくエンコードされる。
【００４３】
次いで、ウェーブレット変換を用いて、８ビット符号なし整数データが変換される。本例における変換は、非特許文献３に記載されるリフティング・スキームを用いた線形ウェーブレット変換である。
【００４４】
次いで、ステップ１４０として示されるエントロピー・エンコード・スキームを用いて、係数がエンコードされる。この結果は、ステップ１５０に示される圧縮データである。好ましい実施形態においては、各タイルをエンコードするための４つの選択肢がある。係数は、３つの可変長のエントロピー・エンコード・スキームのうちの１つを用いてエンコードしてもよいし、又は、エンコードしないままにしてもよい。実際にはどのエンコード・スキームもデータを圧縮しない場合には、係数はエンコードされないままになる。
【００４５】
これらのタスクを実行することができるコンプレッサ／デコンプレッサ・ユニット２０を、図４に概略的に示す。ユニットの処理ステップは、コンプレッサ／デコンプレッサ・ユニット内部の全ての演算を調整する状態機械２００によって制御される。圧縮プロセスに言及すると、レンダラ１０の出力は、データの簡易逆多重化を実行する再フォーマット・ユニット２０５に与えられる。これは、図３のステップ１２０の部分に対応する。次いで、再フォーマットされたデータは、クロック・サイクル毎に多数のデータ要素への並列アクセスを与えるレジスタ・ファイルからなることが好ましい、記憶領域２１０に保持される。図３のステップ１２５に対応する色変換、及び、図３のステップ１３０に対応するウェーブレット変換に必要な演算を実行する「並列」算術論理演算ユニット（ＡＬＵ）２２０が、データ記憶装置に取り付けられる。このユニットは、性能上の理由のために、多くのチャネル及び又はピクセル上で、並列して演算を実行する。
【００４６】
色変換及びウェーブレット変換の結果もたらされる係数に対してエントロピー・エンコードを実行するエントロピー・エンコード／デコード・ユニット２３０もまた、データ記憶装置２１０に接続される。これは、図３のステップ１４０に対応する。可変長のエンコードされたデータは、メモリ・インターフェース１５を介してメモリに転送される前に、データバッファ２４０に書き込まれる。
復元は、これらのステップの逆である。表示出力ユニット３０も、データ記憶装置２１０にアクセスすることができ、圧縮されたバッファの表示を可能にする。
【００４７】
ここでステップの各々の好ましい実施形態をより詳細に説明する。全てのデータ型に共通する圧縮アルゴリズムの第１段階は、主として線形ウェーブレットを用いるウェーブレット変換である。本例においては、非特許文献３に記載されるものと同様のリフティング・ベースのスキームを用いて、圧縮されていないデータアレイの代わりにウェーブレット係数が計算される。このスキームにおける更新ステップは、このステップが圧縮率に対してごくわずかな利点（１％未満）しか有さないこと（画像に関して）、又は、利点を低減させること（ｚバッファデータに関して）を本発明者らが見出したため、効率上の理由で省略される。
【００４８】
ウェーブレット変換の各レベルについて、二次元データアレイは、まず水平方向に、次いで垂直方向に変換される。標準的なウェーブレット手法とは異なり、好ましい実施形態はまた、通常、前のステップで既に計算された差異に対して変換を適用することを避けるが、これは、画像データについては、結果的にはごくわずかな改善しか測定されないためである。これに対する例外は後述する。
【００４９】
図５ａにおける疑似コードは、１つのデータチャネルに適用されるようなプロセスを示す。ステップ３００において、処理の反復／レベルの数を求める。ステップ３１０は、これらのレベルを「ループ」し、サブステップ３２０、３２５、３３０、３５０及び３６０を含む。ステップ３２０及び３２５は、このレベルで処理される行のサブセットを判断する。ステップ３３０は、現在の行のサブセットにおける各行をアドレス指定し、各行におけるデータのサブセットに対してウェーブレット・プロセス３３５を実行する。
【００５０】
その後、ステップ３５０は、データの列のどのサブセットがこのレベルで処理されるかを判断し、ステップ３６０は、これらの列を通って、その列におけるピクセルのサブセットに対して再びウェーブレット・プロセス３３５を実行する。
【００５１】
繰り返して説明するが、ステップ３３０における全ての行は、ウェーブレット・プロセス３３５により、独立して処理することができ、従って、並列して実行することができる。同様に、３６０の列の反復もまた、並列して行うことができる。さらに、種々のデータチャネルも独立しており、従って並列して動作することができる。
【００５２】
ウェーブレット変換全体を通して、計算された値は、８ビット演算のみを用いて格納される。これは、［０，２５５］範囲外の計算結果は、［０，２５５］に戻してマッピングされることを意味する。数学的に、これは、２５６を法として全ての演算を実行することに相当する。コンピュータ・システムにおいては、このマッピングは、単に、いずれの計算された結果の最下位８ビットを保持することだけにより、自動的に実現することができる。
【００５３】
ここで図５ｂを参照して、ウェーブレット・プロセス３３５をより詳細に説明する。ウェーブレット・プロセスに与えられる値の組は、「偶数」及び「奇数」の組３７０に分けられる。次に、各々の奇数値は、「リフティング」ステップ３９０を用いて処理される３８０。このことは、リフティング・ステップが各奇数ピクセルに対して独立しているため、反復的に又は並列して行うことができる。リフティング３９０は、以下のステップからなる。
ａ．予測。線形ウェーブレットにおいて、隣接する偶数値を用いて、２つの偶数値の平均をとることにより、奇数値についての予想値を推定する。これは、単純化された形態で図に示される。本実施形態においては、２５６を法とする計算で計算するように適合された、後で詳述される「ＣｌｏｓｅｓｔＡｖｅｒａｇｅ」関数を用いるように適合されている。他の実施形態においては、処理されるデータに応じて選択可能とすることができる。
ｂ．しかしながら、最後の奇数ピクセルにおいては、隣接する偶数は１つ（前のもの）しかないため、その値が予測として用いられる。
ｃ．奇数値とその予測値との差異は、奇数ピクセルの格納位置にライトバック（ｗｒｉｔｅ  ｂａｃｋ）される。
本実施形態に用いられるウェーブレット・プロセスは、偶数値が修正される標準的な「更新」段階を省略する。
【００５４】
計算されたウェーブレット係数からオリジナル・データを回復するための逆ウェーブレット変換は、単に、全ての関係するステップの逆である。これは、変換が、ウェーブレットの最高レベルから最低レベルへ向かって行われる、ここではレベルごとに列が処理され、その後に行が処理されることを意味する。格納された差異からの奇数要素及び隣接する偶数要素を用いる予測値を回復することにより、データが回復される。疑似コードにおいて、これは：
for level ＝ highestWLLevel down to 0
｛
for each column in level
｛
for each odd element
｛
if not border element then
predicted ＝ average(evenLeft, evenRight)
else
predicted ＝ evenLeft
endif
element ＝ element ＋ predicted;
｝
｝
for each row in level
｛
.
recover odd elements as above
.
｝
｝
のようになる。
列の「左」及び「右」は、「上」及び「下」として解釈されることに留意されたい。上記の疑似コードに記述される「平均（ａｖｅｒａｇｅ）」関数は、モジュロ演算で機能するように適合されており、後で詳述される。
【００５５】
随意的な色変換及びウェーブレット変換から結果として得られる係数は、可変長のエントロピー・エンコード・スキームを用いてエンコードされる。データアレイは、タイルベースの方法により圧縮され、すなわち、データアレイは、等しいサイズのタイルに分割され、各タイルは個々に圧縮される。好ましい実施形態においては、各タイルに対して４つのエンコード・スキームの選択肢があり、３つのエントロピー・エンコード・スキームのうちの１つを用いてそのウェーブレット係数がエンコードされる、又は、ウェーブレット係数がこれらのスキームによっては圧縮できない場合、すなわち、圧縮ではなく拡張される結果になる場合、そのウェーブレット係数は全くエンコードされず、その代わりに単に８ビット値として出力される。後者の場合には、タイルに対してどのような圧縮も実現されないが、このことは、データを拡張させるスキームにおいては有利である。
【００５６】
以下のエントロピー・エンコード・スキームの説明においては、ウェーブレット係数の値が、１２８だけオフセットされているため、「ゼロ」がヒストグラムの中央に事実上現れる。これは主として、人間が解釈しやすくなるように行われる。図に示されるエンコードもまた、この分布を前提とする。この＋１２８の「追加」（簡略的には、各々の８ビット値の上位ビットを逆にすることに等しい）は、本発明に必要なものではなく、また、エントロピー・エンコード・スキームがこれに応じて調整されるのであれば、等しく効果的な実施形態を、このオフセットなしに済ませ得ることに留意されたい。
【００５７】
エンコードの第１のステップは、圧縮スキームを選択すること又は圧縮を用いないという選択をすることである。全てのスキームを試行して最小の出力を生成したものを選択するよりはむしろ、はるかに安く簡単な発見的手法が用いられる。この発見的手法は、各タイルにおける０、−１、及び１の係数（１２８のオフセットのために、１２８、１２７及び１２９として格納される）の数をカウントし、合計を所定の閾値と比較する。これは、以下の疑似コードに示される。
count ＝ 0;
for each coefficient
｛
if (             (coefficient ＝＝ 128 ) OR 
(coefficient ＝＝ 127 ) OR 
(coefficient ＝＝ 129 ) ) then
count ＝ count ＋ 1;
endif
｝
Const int numCoefficients ＝ tileWidth * tileHeight;
Const int noPackThresh  ＝ 0.05 * numCoefficients;
Const int scheme1Thresh ＝ 0.3  * numCoefficients;
Const int scheme2Thresh ＝ 0.9  * numCoefficients;
if ( count < noPackThresh ) then
encodingScheme ＝ 0;
else if ( count < scheme1Thresh  )
encodingScheme ＝ scheme1;
else if ( count < scheme2Thresh  )
encodingScheme ＝ scheme2;
else encodingScheme ＝ scheme3;
endif
【００５８】
上記で与えられる閾値定数は、特定のデータ型に合わせてさらに調整することができるが、これらは、レンダリングされたもの及び写真の両方の、主としてＲＧＢ画像で構成される試験されたデータセットについての良好な選択肢となることが分かっている。エンコード・スキームは、ウェーブレット係数が典型的には「ゼロ」の周りにクラスタ化され（例においては、１２８にマッピングされ）、多かれ少なかれベル形状のヒストグラム曲線を形成するという事実を活用する。オリジナルのデータセットが区分的線形関数に近づくほど、その（線形）ウェーブレット係数はゼロに近くなる。反対に、よりランダムな又は雑音の多いデータセットは、より均一に分布したヒストグラムを形成する係数を有する。図６は、画像からの例示的なタイルに対応する。その赤色チャネルのヒストグラム５１０が図６ａに示され、対応するウェーブレット係数のヒストグラム５２０が図６ｂに示される。ここでもウェーブレット係数は１２８だけオフセットされている。
【００５９】
３つのエンコード・スキームの各々は、８ビット空間［０，２５５］を、グループを形成する区間に区分化することからなる。各スキームにおける第１のグループは、１２８（ゼロ）の周りにクラスタ化された最も一般的なウェーブレット係数を含む１つの区間だけを有する。後に続くグループは、より一般的でないウェーブレット係数を含む２つの区間からなる。各々の区間は、格納効率を最大化するために、係数値の２xの数をカバーする。係数を格納するために用いられるビットコードは、グループｉｄ接頭辞及び値からなる。グループｉｄ及び値の両方とも、グループの位置及びサイズに応じた、可変長のものである。グループｉｄは、グループ位置によってゼロ又は少なくとも１からなり、その後に０が続く。最後のグループｉｄは例外であり、ここでは終端の０を省くことができる。例えば、スキーム内に４つより多いグループがあるとき、第４のグループｉｄは１１１０であるが、スキーム内に４つのグループしかない場合には、１１１になる。
【００６０】
グループ値は、グループにおける係数の位置である。例えば、図７に示すスキーム１におけるグループ４は、５つのビット値フィールドを有し、従って、３２の係数値の範囲をカバーする。このグループは、各々が１６の係数値を含む２つの区間［８１、９６］及び［１６１、１７６］からなる。このように含まれる値フィールドが例えば８３である場合には、グループ４の第１の区間に属し、グループ値は「２」である。値フィールドが１７０である場合には、グループ４の第２の区間に属し、そのグループ値は「２５」である。
【００６１】
図７、図８及び図９は、画像データセットから実験的に生み出された３つの異なるエンコード・スキームを示す。各々のスキームは、異なるグループ構造を有する可変長のエントロピー・エンコード・スキームである。これらの図の各々に示されるヒストグラムは、対応するスキームを用いる圧縮に適した例示的なデータからとられる。
【００６２】
データがランダムでないほど、ウェーブレット係数は１２８の周りに集中する。従って、より短い長さのコードを１２８の周りの係数に用い、より長いコードを１２８から遠い係数に用いることによって、よりランダムでないデータについてより高い圧縮を実現することができる。図７に示す第１のスキームは、図８に示す第２のデータ・スキームよりも、ランダムなデータセットに用いられ、図８の第２のデータ・スキームは、図９に示す第３のスキームよりも、ランダムなデータセットに用いられる。
【００６３】
例示的なスキームは、より大きい試験データのセットに基づいてさらに改良することができ、他のエンコード・スキームを代替的な実施形態に対して選択することができる。こうしたスキームの１つは、幾つかの係数の文字列をエンコードすることができる。例えば、数値的に小さい値に対して大きくバイアスがかけられているデータセットについての、単一の値をもつ２つのゼロである。
【００６４】
エンコード・スキームの別の実施形態においては、左上のウェーブレット値、すなわち、「ｄｃ」項は、エントロピー・エンコードされないが、これらは一般にほとんど均一な値の分布を有するため、代わりに単に８ビット値として直接格納される。
【００６５】
デコンプレッサがデータの特定のタイルをデコードすることができる場合、デコンプレッサは、そのタイルに用いられるエンコード・スキームを知る必要がある。従って、エンコードされたタイル・データの最初の２ビットは、以下のようなエンコード・スキームを格納するために用いられる。
００＝圧縮なし
０１＝スキーム１
１０＝スキーム２
１１＝スキーム３
【００６６】
エンコードされたデータ・タイルの復元は簡単である。まず、最初の２ビットからスキームが読み取られる。タイルのウェーブレット係数がエントロピー・エンコードされていない特定の場合においては、デコード・ステップを省略することができ、前述のウェーブレット変換を逆にすることにより、オリジナルのデータを取り出すことができる。他の場合には、タイルのデータ要素の各々を最初にデコードしなければならず、以下のステップを必要とする。
１．０に到達するまで、又は、グループ１の最大数が読み取られるまで、エンコードされたデータ要素をビット毎に読み取ることにより、グループを識別する。
２．グループｉｄの後に続くグループ値を、［０，２５５］範囲内の対応する位置にマッピングする。
【００６７】
代替的な実施形態においては、エンコード・スキームのビットは、メモリ又はレジスタの別個のアレイ内に、１タイル当たり１つのエントリで格納することができる。このアレイはまた、タイル毎に圧縮されたデータのサイズの詳細を含むこともできるため、外部メモリバスは、タイルをデコードするために、正しいデータ転送を要求することができる。
【００６８】
別の代替的な実施形態においては、独立したエンコード・スキームを用いて、異なるチャネルをエントロピー・エンコードすることができる。
【００６９】
エンコードされた係数が可変長であるために、係数のデコード・プロセスは、一般に逐次的である。例えば、より短いビット文字列でエンコードされた係数の対をデコードすることは可能であり得るが、１クロック・サイクル内で行うことができる数を増加させるのは極めて困難である。代替的な実施形態においては、少なくとも１つの付加的な並列エントロピー・デコーダが含められる。記号の第１の部分が第１エントロピー・デコーダによりデコードされ、第２の部分が第２のデコーダによりデコードされる。従って、第２のデコーダは、エンコードされた記号がどこで始まるのか分かり、ビットのオフセットも圧縮されたデータの始めに格納される。こうしたオフセットは確かに圧縮効率を下げるため、従って、こうした実施形態は、デコード速度を圧縮率と引き換えにする。データが決して拡張されないため、オフセットのサイズは有界であることに留意されたい。さらに、代替的な実施形態においては、デコーダ及びオフセットを用いて、速度をさらに増大させることができる。
【００７０】
チャネルにつき８ビットのＲＧＢ（Ａ）の色データを圧縮する場合、データを、ＲＧＢの色チャネル間の相関性を活用する異なる色空間に変換することにより、圧縮率を改善することができる。しかしながら、色空間の変換が可逆的であることは重要であり、従って可逆型画像圧縮が可能である。
【００７１】
ＲＧＢの可逆性を有する１つのこうしたモデルは、非特許文献４及び非特許文献５に説明されるＹＣｏＣｇ−Ｒの色モデルであり、これらの内容は引用により本明細書に組み入れられる。ＲＧＢからＹＣｏＣＧへの変換の概要は、以下に与えられる。
Ｃ0＝Ｒ−Ｂ
ｔ＝Ｂ＋（Ｃ0＞＞１）
Ｃg＝Ｇ−ｔ
Ｙ＝ｔ＋（Ｃg＞＞１）
【００７２】
このモデルは、青色から赤色への、並びに平均化された赤色及び青色のチャネルから緑色への相関を失わせ、色情報のほとんどを１つの輝度（Ｙ）チャネルにパックする。ＹＣｏＣｇ−Ｒにおいては、Ｃｏ及びＣｇチャネルは９ビットに拡張される。変換は、単に８ビットモジュロ演算を用いることによって行うことができるが、これは、値のラップアラウンドによりもたらされる不連続性のため、幾つかの画像についての圧縮率を大幅に減少させる。ＹＣｏＣｇ−Ｒはまた、「ｔ」値についての付加的な一時格納部を必要とすることにも留意されたい。
【００７３】
別の既知の色モデルは、非特許文献６に説明されるＪＰＥＧ２０００の可逆色変換（Ｒｅｖｅｒｓｉｂｌｅ  Ｃｏｌｏｕｒ  Ｔｒａｎｓｆｏｒｍ、ＲＣＴ）であり、この内容は引用により本明細書に組み入れられる。ＲＣＴは：
2010537534.tif 000003
2010537534.tif 000004
2010537534.tif 000005
のように指定される。
【００７４】
８ビットの計算のみに関する問題を防ぐために、ＹＣｏＣｇ／ＲＣＴモデルを修正することができる。ＹＣｍＣｎと名付けられる新しいモデルは、ＹＣｏＣｇ／ＲＣＴモデルと同様に、１つの輝度と２つの色成分（Ｃｍ、Ｃｎ）とからなる。ＲＧＢ色空間からの変換は、以下の：
2010537534.tif 000006
2010537534.tif 000007
2010537534.tif 000008
のように定義される。
【００７５】
ＹＣｏＣｇ及びＲＣＴ色変換の両方において、除算演算がある。８ビット算術を用いて除算を計算するときは、十分に注意しなければならない。従って、上述の変換における４による除算は、後に説明されるＭｏｄｕｌｏｓａｆｅ＿ｄｉｖ４の演算子で置き換えられる。８ビット値で行われる計算は、容易に８ビット範囲外の値をもたらしかねない（すなわち、オーバーフロー・アンダーフロー）。モジュロ演算は、これらの値を８ビット範囲に戻して「マッピング」し、「曖昧さ」をもたらす。
【００７６】
例えば、２つの計算結果、−１２及び６を有し、これらの「平均」を計算したいと仮定する。理想的には、（−１２＋６）／２＝−３に対応する値を期待する。ここで、−１２は、２５６を法として２４４と合同であるため、再マッピングされた値を平均化しようとする場合、（２４４＋６）／２＝１２５が得られるが、実際には２５３（≡２５６を法として−３）の値を期待している。
【００７７】
この問題に対する解決法は、モジュロ演算を用いるときに８ビット範囲［０，２５５］が円を形成することを考慮することにより見出すことができる。これは、１組の値に対して、常に２つの平均があることを意味する。２つの計算結果が、近い値を表わすようになっていると仮定する場合（これは、より典型的な状況である）、すなわち、１２８からより間隔が離れた値が、２つの値のうちの一方の単一の「ラップアラウンド」結果である場合には、「正しい」平均は、円の周りのより短い経路上の平均値を選択することより、計算することができる。これは、次の：
2010537534.tif 000009
により実現される。
【００７８】
さらに、範囲［１２８，２５５］における値が負の値を表わすことを仮定する「ｄｉｖｉｄｅ  ｂｙ  ２」の演算子が定義される。
2010537534.tif 000010
【００７９】
ＲチャネルとＧチャネルとの間、及びＢチャネルとＧチャネルとの間の高い相関が期待されるために、Ｃｍ及びＣｎの両方がゼロに近いと仮定すると、以下の演算を定義することができる。
2010537534.tif 000011
【００８０】
このことは、ほとんどの場合、Ｃｍ及びＣｎの両方の制約のない値は、すなわち、十分な精度の計算を用いており、８ビット精度にマスクしない場合には、範囲［−１２８，１２７］内にあり、１２８より間隔が離れることはないため、実際上良好に機能する。すなわち、ほとんどの場合、ＣｌｏｓｅｓｔＡｖｅｒａｇｅ（Ｃｍ、Ｃｎ）の結果は正しく、範囲［−１２８、１２７］内にあり、負の値は範囲［１２８、２５５］内の値にマッピングされる。このことは次いで、ＤｉｖｉｄｅＢｙＴｗｏの演算子に対する仮定が正しいことを意味する。しかしながら、制約のない値が［−１２８、１２７］の外にあったとしても演算は依然として可逆的である。
【００８１】
従って、最後のＲＧＢのＹＣｍＣｎへの色変換は以下のように記述することができる。
2010537534.tif 000012
2010537534.tif 000013
2010537534.tif 000014
【００８２】
これは、赤色チャネルと緑色チャネル、及び緑色チャネルと青色チャネルとの間の相関を活用する完全に可逆的な色変換である。ＲＧＢの試験画像の大部分においては、これらは、最も顕著な組になったチャネル相関であるが、青色チャネルと赤色チャネルとの間の相関は特に少ないことが見出されている。
【００８３】
チャネルにつき８ビットのＲＧＢ（Ａ）画像を圧縮するためには、そのＲＧＢチャネルは、まずＹＣｍＣｎ空間に変換される。各チャネルは、次いで上述のようにウェーブレット変換され、個々に圧縮されるが、これは、随意的なアルファ・チャネルを含むことができる。オリジナル画像を取り出すのは簡単であり、デコード及び逆ウェーブレット変換後、ＲＧＢチャネルは、ＹＣｍＣｎ変換を逆にすることにより回復される。
2010537534.tif 000015
2010537534.tif 000016
2010537534.tif 000017
【００８４】
Ｙ、Ｃｍ及びＣｎチャネルを変換する際のウェーブレット変換における正しい差分計算を保証するためには、従来技術の線形ウェーブレットに用いられる予測、すなわち
2010537534.tif 000018
が、
2010537534.tif 000019
と置き換えられる。これは、ＹＣｍＣｎ変換は、ｖE_left又はｖE_rightのうちの少なくとも一方が「負」になる結果をもたらす可能性が高く、従って標準的な平均計算が、圧縮の点で不良な結果を生み出すためである。
【００８５】
図１０は、ＲＧＢに実行されたウェーブレットの結果９００と、同等のＹＣｍＣｎデータ９１０とを比較するヒストグラムを示す。標準偏差は、ＲＧＢウェーブレットの色チャネルにおけるもの（９５０乃至９５２）より、ＹＣｍＣｎウェーブレットのＣｍ及びＣｎチャネル９２０、９３０のものの方がはるかに低いことが明らかに分かる。これは、Ｙ、Ｃｍ及びＣｎウェーブレット出力をエントロピー・エンコードすることが、Ｒ、Ｇ及びＢのウェーブレット結果をエンコードすることよりも、より大幅に圧縮された出力をもたらすことを意味する。
【００８６】
代替的な実施形態においては、ＹＣｍＣｎの色変換は、非特許文献７に説明されるＪＰＥＧ−ＬＳ色変換と置き換えられるが、２５６を法として機能するように適合される。多くのＲＧＢ（Ａ）色画像に対して、２５６を法とするＪＰＥＧ−ＬＳ変換を用いることにより、ＹＣｍＣｎより良好な圧縮結果が生み出されることが分かっている。ＪＰＥＧ−ＬＳ変換は、以下の演算： 
2010537534.tif 000020
2010537534.tif 000021
2010537534.tif 000022
を用いて、赤色チャネル及び青色チャネルと緑色チャネルの相関をなくす。
【００８７】
この変換の逆は自明である。ウェーブレット変換の予測ステップにおいては、最近接平均関数（ｃｌｏｓｅｓｔ  ａｖｅｒａｇｅ  ｆｕｎｃｔｉｏｎ）をｒとして用いる必要があり、ｂの値はＪＰＥＧ−ＬＳ変換においてラップアラウンドされることになる。
【００８８】
このように説明される好ましい実施形態においては、色変換は、ウェーブレット変換の前に実行される。別の実施形態においては、最初にウェーブレット変換が行われ、次いで、１つ又はそれ以上の異なる色変換が並列して行われる。次いで、各タイルごとに最良の圧縮をもたらす色変換を選択して、そのタイルを表す。
【００８９】
同じハードウェアの再利用を可能にし、それによりシリコンの費用を減らすために、ＩＥＥＥ規格７５４の３２ビット浮動小数点データが、３２ビット値の各々を４つの別個の８ビット成分に分割し、次いで、各成分ごとにウェーブレット変換を個々に行うことにより、圧縮される。こうした分割の一例を図１１に示す。３２ビット値１０００は、４つの８ビット値１０１０に分割された状態で示される。
【００９０】
種々の自明でないマッピング・スキームにより実験が行われた。しかしながら、圧縮率の点では、単純な分割は非常に有効である。
【００９１】
通常、ウェーブレット変換は、浮動小数点データに対して直接実行されるが、このことは費用のかかる浮動小数点計算装置を暗に示し、浮動小数点の丸めによる精度の損失を招く。代替的には、３２ビット浮動小数点データは、３２ビットの整数データ（２32を法とする）として解釈できるが、３２ビットの計算は依然として費用がかかり、付加的なハードウェアを必要とする。
【００９２】
試験では、分割された３２ビットＨＤＲ又はｚ−バッファデータを圧縮するとき、ウェーブレット変換の予測ステップが前述の「最近接平均」関数を用いる場合には、平均して、２％高い圧縮率が達成されることが示された。
【００９３】
これは、ウェーブレット変換前には、値のラップアラウンドが行われないため奇妙に思われるが、仮数が別個の８ビットチャネルに分割されるので、隣接する値間の滑らかな移行が、幾つかのチャネルにおいてラップアラウンド効果をもたらし、「鋭利な縁部（ｓｈａｒｐ  ｅｄｇｅ）」が生成される。最近接平均関数は、ラップアラウンドの不連続性を滑らかな移行として扱うことにより、これらの状況を正しく処理する。単純な平均計算では、これらの不連続性に近い不良な予測を招き、はるかに大きいウェーブレット係数をもたらす。
【００９４】
３２ビットのｚ−バッファデータを圧縮する場合、従来技術のウェーブレット処理においてより標準的であるように、前のウェーブレット変換ステップにおいて既に計算された差異の差を計算することによって、より高い圧縮を達成することができる。このことは、行及び列の刻み幅を、単に、図５で記述されたアルゴリズムの１つに設定することにより実現される。
【００９５】
１６ビットの浮動小数点及び１６ビットの整数データは、図１２に示す好ましい実施形態により、上述されたような標準的な３２ビット浮動小数点データに用いられたのと同じ簡単な分割技術を用いて圧縮される。１６ビットの浮動小数点データ１０２０及び１６ビットの整数データ１０４０はそれぞれ、８ビットの成分１０３０及び１０５０に分割される。
【００９６】
３２ビットの場合と同様に、１６ビットの浮動小数点データに対する種々の自明でないマッピング・スキームによる実験は、単純な分割に優る改善を示さなかった。
【００９７】
２×２マルチサンプル・アンチエイリアス（Ｍｕｌｔｉ−Ｓａｍｐｌｅｄ  Ａｎｔｉａｌｉａｓｉｎｇ、ＭＳＡＡ）の生データを用いる好ましい実施形態についての圧縮率は、ウェーブレット変換の第１レベルの間、すなわち、単一ピクセル内部に完全に含まれるデータを依然として処理している間、線形ウェーブレットの代わりにハール・ウェーブレット（Ｈａａｒ  ｗａｖｅｌｅｔ）を用いることにより改善される。より高いレベルのＭＳＡＡサンプリングを用いる実施形態においては、より初期のハール・ステップが用いられる。
【００９８】
ハール・ウェーブレットは、圧縮されるデータが、隣接するサンプルにわたって一定であることを前提とする。そのリフティング・ステップ中、奇数要素は、その左の隣接する偶数により予測され、予測された奇数要素と実際の奇数要素との間の差異が、奇数要素に格納される。
2010537534.tif 000023
【００９９】
線形ウェーブレットを計算するときと同様に、ハール変換の更新ステップは、圧縮性能を改善しないため、省略されることが有利である。
【０１００】
各々のオーバーサンプリングされたピクセル内では、色が複製される可能性が非常に高いため、ハール・ウェーブレットはＭＳＡＡ生データに有利である。線形ウェーブレットは、予測のために、隣接する偶数サンプルの両方を用いるので、従って、ＭＳＡＡデータの２×２ブロックの境界にわたる線形のブレンドを予測する。これは、第１のウェーブレット・レベルにおける奇数サンプルは、通常、線形ウェーブレットの代わりにハール・ウェーブレットを用いるとき、予測されるエラーがより少ないことを意味する。このことは、一対の２×２のマルチサンプリングされたピクセルを並べて示す図１３に示される。両方のピクセルは、同じ２つの三角形１１００及び１１０１が横断している。前者は、シェーディング又はテクスチャリングのために、明るい緑色から暗い緑色に変化するが、ＭＳＡＡが実行されると、各三角形についての色は、ピクセル毎に一度だけ評価され、三角形によりカバーされるピクセルにおける全てのサンプルに複製される。例示のために、データの第１行にだけウェーブレットを適用することを考慮する。
【０１０１】
図１３の左側には、ハール・ウェーブレットの例が示される。予測される奇数ピクセル１１０４は、純粋に、左の隣接する偶数１１０５からその予測値を取得し、明るい緑色の１００％完璧な予測１１１０をもたらし、これはゼロ係数を格納できることを意味する。
【０１０２】
比較のために、図１３の右側は、線形ウェーブレットを用いる、同じ予測される要素１１２０は、今度は、２つの異なる偶数サンプル１１２５及び１１２６の平均からその予測を取得し、これは、１１２５からの明るい緑色と１１２６からの暗い緑色を平均して、中強度の緑色の予測結果１１３０を生み出すことを意味する。これは、非ゼロのウェーブレット係数が格納され、より多くのビットのエンコードを必要とすることを意味する。典型的には、ＭＳＡＡは各ピクセル内部のサンプル値を反復するため、隣接するピクセルの値を用いる予測は、より非生産的なものになりやすい。
【０１０３】
さらに圧縮率を増大させるために、本技術を発展させて、非可逆圧縮の選択肢を支持することができる。このことは、修正されたエンコード・スキームを用いてエンコードする前に、ウェーブレット係数におけるよりあまり重要でないビットをゼロにすることにより、達成することができる。従って、可能な値のより小さい数により、より大きい圧縮率が可能になる。より厳格には、より高い周波数項の幾つかをゼロに量子化することができ、このことも同様な効果を有する。しかしながら、可逆形態では用いられないウェーブレットの「更新」ステップは、品質を維持するために必要とされ得る。
【０１０４】
本発明の可逆圧縮法はまた、ビデオ処理、すなわち、例えばＭＰＥＧ２、ＭＰＥＧ４及びＨ．２６４などを使用する圧縮／復元システムにも適用可能であり、ここでは幾つかの基準フレームを維持し、圧縮及び復元処理ステップの両方に対して、定期的に参照しなければならない。これらのフレームにアクセスすることは（擬似ランダム順で）、高い帯域幅の費用をもたらしかねないが、この費用は、本明細書に記述される方法により大幅に低減させることができる。
【符号の説明】
【０１０５】
１：ホスト
２：グラフィックス・レンダリング・システム
３：グラフィックス・メモリ
４：表示装置
１０：レンダラ
１５：メモリ・インターフェース
２０：コンプレッサ／デコンプレッサ・ユニット
３０：表示出力ユニット
２００：状態機械
２１０：データ記憶装置
２２０：算術論理演算ユニット（ＡＬＵ）
２３０：エントロピー・エンコード／デコード・ユニット
２４０：データバッファ
【図１】
2010537534.tif 000024
【図２】
2010537534.tif 000025
【図３】
2010537534.tif 000026
【図４】
2010537534.tif 000027
【図５ａ】
2010537534.tif 000028
【図５ｂ】
2010537534.tif 000029
【図６ａ】
2010537534.tif 000030
【図６ｂ】
2010537534.tif 000031
【図７】
2010537534.tif 000032
【図８】
2010537534.tif 000033
【図９】
2010537534.tif 000034
【図１０】
2010537534.tif 000035
【図１１】
2010537534.tif 000036
【図１２】
2010537534.tif 000037
【図１３】
2010537534.tif 000038
【手続補正書】
【提出日】平成22年4月22日(2010.4.22)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二次元データのデータ圧縮のための方法及びシステムに関する。具体的には、本発明は、メモリの帯域幅を減少させるグラフィックス・レンダリング・システムにおけるデータ圧縮に関する。
【背景技術】
【０００２】
可逆型及び非可逆型の両方のデータ圧縮は、大量のデータが格納され読み出される、グラフィックス・フレームバッファを含む多くの用途において、非常に望ましい。従って、携帯通信装置のような小型装置におけるグラフィックスの使用が増大するに伴って、圧縮データの使用は極めて望ましいものとなっている。
【０００３】
一般的な非可逆型（ｌｏｓｓｙ）画像圧縮は、画像全体に適用される場合、コンピュータグラフィックにおいてはＪＰＥＧ及びＧＩＦ等の規格で周知である。ＰＮＧ等の可逆型（ｌｏｓｓｌｅｓｓ）画像圧縮法は、一般的にあまり用いられていないが、Ｃｏｍｐｒｅｓｓ又はＺＩＰ等のいずれかの可逆圧縮ツールを、圧縮されていないソースに適用することもできる。しかしながら、これらの全ての方法に関連する問題は、ａ）これらの方法は、オンザフライ圧縮及び復元には費用がかかること、及び、ｂ）これらの方法により、データへのランダム・アクセスが可能ではないことである。
【０００４】
テクスチャ圧縮のために特別に設計されたものなどの幾つか非可逆圧縮スキーム（幾つかの既知のスキームの再検討が非特許文献１において与えられる）は、確かにデータへのランダム・アクセス及び簡単な復元ステップを提供する。しかしながら、これらの方法の主要な欠点は、圧縮アルゴリズムは、復元アルゴリズムよりはるかに費用がかかり（すなわち、これらの方法は、非対称エンコード及びデコードを用いる）、従って、リアルタイム演算には適していないことである。また、可逆圧縮を提供するようにこれらの方法を適合させるのは困難でもある。
【０００５】
Ｒａｓｍｕｓｓｏｎ他のシステム（手短に説明される）を例外として、データバッファ（フレーム及びＺバッファ等の）のための対称的な（すなわち、エンコード費用及びデコード費用がおよそ等しい）リアルタイム圧縮システムは、これまでかなり簡単なスキームに限定されていた。こうしたシステムの再検討を、非特許文献２に見出すことができる。
【０００６】
Ｒａｓｍｕｓｓｏｎ他はまた、ＲＧＢデータについての、より高度な圧縮及び復元システムも提示するが、このシステムは、数値の動的範囲の拡大を必要とし、これによりレジスタサイズに関する費用が発生する。このシステムはまた、一連の予測スキームを用いるだけであり、そのことは、並列計算を妨げる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｓ．Ｆｅｎｎｅｙ著、「Ｔｅｘｔｕｒｅ  Ｃｏｍｐｒｅｓｓｉｏｎ  ｕｓｉｎｇ  Ｌｏｗ−Ｆｒｅｑｕｅｎｃｙ  Ｓｉｇｎａｌ  Ｍｏｄｕｌａｔｉｏｎ」、Ｇｒａｐｈｉｃｓ  Ｈａｒｄｗａｒｅ  ２００３年
【非特許文献２】Ｒａｓｍｕｓｓｏｎ、Ｈａｓｓｅｌｇｒｅｎ及びＡｋｅｎｉｎｅ−Ｍｏｌｌｅｒ著、「Ｅｘａｃｔ  ａｎｄ  Ｅｒｒｏｒ−ｂｏｕｎｄｅｄ  Ａｐｐｒｏｘｉｍａｔｅ  Ｃｏｌｏｒ  Ｂｕｆｆｅｒ  Ｃｏｍｐｒｅｓｓｉｏｎ  ａｎｄ  Ｄｅｃｏｍｐｒｅｓｓｉｏｎ」Ｇｒａｐｈｉｃｓ  Ｈａｒｄｗａｒｅ  ２００７年
【非特許文献３】Ｗｉｍ  Ｓｗｅｌｄｅｎｓ及びＰｅｔｅｒ  Ｓｃｈｒｏｄｅｒ著、「Ｂｕｉｌｄｉｎｇ  Ｙｏｕｒ  Ｏｗｎ  Ｗａｖｅｌｅｔｓ  ａｔ  Ｈｏｍｅ」１９９６年、ｈｔｔｐ：／／ｃｉｔｅｓｅｅｒ．ｉｓｔ．ｐｓｕ．ｅｄｕ／ｓｗｅｌｄｅｎｓ９６ｂｕｉｌｄｉｎｇ．ｈｔｍｌ
【非特許文献４】Ｍａｌｖｅｒ及びＳｕｌｌｉｖａｎ著、「ＹＣｏＣｇ−Ｒ：Ａ  Ｃｏｌｏｒ  Ｓｐａｃｅ  ｗｉｔｈ  ＲＧＢ  Ｒｅｖｅｒｓｉｂｉｌｉｔｙ  ａｎｄ  Ｌｏｗ  Ｄｙｎａｍｉｃ  Ｒａｎｇｅ」
【非特許文献５】Ｈｅｎｒｉｑｕｅ  Ｍａｌｖｅｒ及びＧａｒｙ  Ｓｕｌｌｉｖａｎ、Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐ，ＪＶＴ  ＰＥｘｔ  Ａｄ  Ｈｏｃ  Ｇｒｏｕｐ  Ｍｅｅｔｉｎｇ：２００３年７月２２〜２４日、Ｔｒｏｎｄｈｅｉｍ（ｈｔｔｐ：／／ｒｅｓｅａｒｃｈ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ／ｕｓｅｒｓ／ｍａｌｖａｒ／ｐａｐｅｒｓ／ＪＶＴ−Ｉ０１４ｒ３．ｐｄｆ）
【非特許文献６】Ｌｉ他著、「Ａ  Ｒｅｖｅｒｓｉｂｌｅ  Ｃｏｌｏｒ  Ｔｒａｎｓｆｏｒｍ  ｆｏｔ  １６−ｂｉｔ−ｃｏｌｏｒ  Ｐｉｃｕｔｒｅ  Ｃｏｄｉｎｇ」、ｔｈｅ  １２th  ａｎｎｕａｌ  ＡＣＭ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａの予稿集、２００４年
【非特許文献７】Ｗｅｉｎｂｅｒｇｅｒ他著、「Ｔｈｅ  ＬＯＣＯ−Ｉ  Ｌｏｓｓｌｅｓｓ  Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ａｌｇｏｒｉｔｈｍ：Ｐｒｉｎｃｉｐｌｅｓ  ａｎｄ  Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ  ｉｎｔｏ  ＪＰＥＧ−ＬＳ」
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、上述の問題を解決するための方法及びシステムを提供することである。
【課題を解決するための手段】
【０００９】
本発明は、ここで参照すべき特許請求の範囲において定義される。有利な特徴は、従属項において定義される。
第１の態様において、本発明は、グラフィックス・レンダリング・システムにおいて、二次元電子画像データセットを圧縮するための方法であって、
データセットをデータアレイに分割するステップと、
各アレイにウェーブレット変換を行なって、複数のウェーブレット係数を与えるステップであって、ｎは正の整数である場合にウェーブレット変換はｎを法とする演算を用いて行なわれ、２つの値ｖ1及びｖ2の平均は、
2010537534.tif 000039
及び、
2010537534.tif 000040
として計算される、ステップと、
エントロピー・エンコード・スキームを用いて、ウェーブレット係数の少なくとも幾つかをエンコードするステップと、
を含む方法である。
【００１０】
各データアレイは、画像の別個の連続する区域に対応することが好ましい。事実上、データセットをデータアレイに分割するステップは、次に、画像をタイルに分割するステップである。タイルは任意のサイズ及び形状のものであってもよいが、矩形であることが好ましい。
【００１１】
本方法は、ウェーブレット変換を行なう前に、データセットを所定のデータ・フォーマットに変換するステップをさらに含むことが好ましい。所定のデータ・フォーマットは、８ビット符号なし整数のデータ・フォーマットであることが好ましい。データセットを変換するステップは、より大きいデータ・ユニットを複数のより小さいデータ・ユニットに分割するステップを含むことが好ましい。
【００１２】
より大きいデータ・ユニットを分割するステップは、より大きいデータ・ユニットを複数の別個のデータチャネルに分割するステップを含むことが好ましい。
【００１３】
モジュロ演算は、所定のデータ・フォーマットに対応することが好ましい。
【００１４】
ウェーブレット変換を行なうステップ及びエンコードするステップは、異なるデータアレイに対して並列して実行されることが好ましい。
【００１５】
データセットは、複数のデータチャネル画像の単一のデータチャネルであり、方法ステップの各々は、複数のデータチャネル上で実行されることが好ましい。画像は色データを含み、本方法は、色変換を用いて色データを異なる色空間に変換するステップをさらに含むことができる。色データを異なる色空間に変換するステップは、ウェーブレット変換を行なう前に実行することができる。代替的には、色データを変換するステップは、ウェーブレット変換を行なうステップの後に実行され、複数の代替的な色変換を行って複数の結果をもたらし、エンコードのために最良の結果を選択するステップを含む。
【００１６】
色変換は、モジュロ演算を用いて行なわれることが好ましい。
【００１７】
ウェーブレット変換は、第２世代のウェーブレットであることが好ましい。ウェーブレット変換は更新ステップを含まないことが好ましい。更新ステップを除去することは、可逆型変換を用いるときには全く問題がない。
【００１８】
本方法は、ウェーブレット係数を評価し、ウェーブレット係数の評価結果に基づいて、エントロピー・エンコード・スキームを選択するステップをさらに含むことが好ましい。係数が、各アレイについて評価され、エンコード・スキームが各アレイについて選択されることが好ましい。評価するステップは、ウェーブレット係数の分布を評価するステップを含むことが好ましい。
【００１９】
ウェーブレット変換は線形ウェーブレット変換であることが好ましい。代替的には、ウェーブレット変換はハール変換とすることができる。ウェーブレット係数は、リフティング・スキームを用いて計算されることが好ましい。
【００２０】
ウェーブレット変換を行なうステップは、各データアレイに対して複数のウェーブレット変換演算を行なうステップを含むことが好ましい。第１のウェーブレット変換演算は、ハール変換演算であることが好ましい。
【００２１】
第２の態様によると、本発明は、グラフィックス・レンダリング・システムにおいて、二次元電子画像データセットを圧縮するためのシステムであって、
データセットを複数のデータアレイに分割するための分割手段と、
コンプレッサ・ユニットと、
を含み、コンプレッサ・ユニットは、各アレイにウェーブレット変換を行なって、各データアレイについての複数のウェーブレット係数を出力するための手段であって、ｎは正の整数である場合にウェーブレット変換はｎを法とする演算を用いて行なわれ、２つの値ｖ1及びｖ2の平均は、
2010537534.tif 000041
及び、
2010537534.tif 000042
として計算される、手段と、
エントロピー・エンコード・スキームを用いて、複数のウェーブレット係数の少なくとも幾つかをエンコードするためのエンコード手段と、
を含むシステムである。
【００２２】
各データアレイは、画像の別個の連続する区域に対応することが好ましい。
【００２３】
本システムは、ウェーブレット変換を行なう前に、データセットを、所定のデータ・フォーマットを有するデータチャネルに変換するための再フォーマット・ユニットをさらに含むことが好ましい。
【００２４】
本システムは、色画像データに色変換を行なうための色変換手段をさらに含むことが好ましい。
【００２５】
本システムは、ウェーブレット係数を評価し、ウェーブレット係数の評価の結果に基づいてエントロピー・エンコード・スキームを選択するための評価手段をさらに含むことが好ましい。
【００２６】
第３の態様によると、本発明は、グラフィックス・レンダリング・システムにおいて、二次元電子画像データセットを圧縮するための方法であって、
少なくとも１つのエントロピー・デコード・スキームを用いてデータセットをデコードして、複数の組の係数を生成するステップと、
係数に逆ウェーブレット変換を行なって、複数のデータアレイを生成するステップであって、ｎは正の整数である場合に逆ウェーブレット変換はｎを法とする演算を用いて行なわれ、２つの値ｖ1及びｖ2の平均は、
2010537534.tif 000043
及び、
2010537534.tif 000044
として計算される、ステップと、
複数のデータアレイを結合して二次元データセットを生成するステップと、
を含む方法である。
【００２７】
各データアレイは、画像の別個の連続する区域に対応することが好ましい。
【００２８】
第４の態様によると、本発明は、グラフィックス・レンダリング・システムにおいて、二次元電子画像データセットを復元するための装置であって、
少なくとも１つのエントロピー・デコード・スキームを用いてデータセットをデコードして、複数の組の係数を生成するための手段と、係数に逆ウェーブレット変換を行なって、複数のデータアレイを生成するための手段であって、ｎは整数である場合に逆ウェーブレット変換はｎを法とする演算を用いて行なわれ、２つの値ｖ1及びｖ2の平均は、
2010537534.tif 000045
及び、
2010537534.tif 000046
として計算される、手段とを含むデコンプレッサ・ユニットと、
複数のデータアレイを結合して二次元データセットを生成するための手段と、
を含む装置である。
【００２９】
各データアレイは、画像の別個の連続する区域に対応することが好ましい。
【図面の簡単な説明】
【００３０】
【図１】本発明による、グラフィックス・レンダリング・システムの概略図である。
【図２】図１のグラフィックス・レンダリング・システムをより詳細に示す。
【図３】異なるデータチャネルに対する本発明の１つの実施形態の方法ステップを示す概略図である。
【図４】図２に示すコンプレッサ／デコンプレッサ・ユニットの概略図である。
【図５ａ】ウェーブレット変換を行なうための疑似コードを示す。
【図５ｂ】ウェーブレット変換を行なうための疑似コードを示す。
【図６ａ】ウェーブレット変換前の画像タイルの赤色チャネルのヒストグラムである。
【図６ｂ】ウェーブレット変換後の図６ａの画像タイルの赤色チャネルのヒストグラムである。
【図７】本発明で用いるための第１の可変長のエンコード・スキームを示す。
【図８】本発明で用いるための第２の可変長のエンコード・スキームを示す。
【図９】本発明で用いるための第３の可変長のエンコード・スキームを示す。
【図１０】ウェーブレット変換後のＲＧＢチャネルデータと、ウェーブレット変換後の変換されたＹＣｍＣｎデータとの間の差異を示す。
【図１１】３２ビットのデータを８ビットのデータのチャネルに分割することを示す。
【図１２】１６ビットのデータを８ビットのデータのチャネルに分割することを示す。
【図１３】ハール・ウェーブレット変換と線形ウェーブレット変換との間の比較を示す。
【発明を実施するための形態】
【００３１】
ここで本発明の例を、添付図面を参照して詳細に説明する。
図１は、電子装置におけるグラフィックス・レンダリング・システムの概略図である。ＣＰＵ１は、グラフィックス・メモリ３内に格納されたフレームバッファ及び幾何学情報等のバッファデータにアクセスする、グラフィックス・レンダリング・サブシステム２と通信する。メモリ内に格納されたレンダリングされた画像は次いで、表示装置等の出力装置４に転送することができる。
【００３２】
本発明によるレンダリング・システムにおいて、二次元データセットとして考えることができる画像データのチャネルは、一連のアレイ又はタイルに区分される。各タイルは個々に圧縮される。タイルのサイズは任意に選択することができるが、２の累乗の次元であることが好ましく、統一される必要はない。選択されたタイルサイズは、改善された圧縮率（大きいタイル）と、より短い待ち時間及びより小さい内部データ格納サイズ（小さいタイル）との間のバランスを表わす。最も実用的な適用のための良好な妥協案は、約３２×３２ピクセルのタイルサイズであることが分かっている。画像データは、スカラー値及び／又はベクトルの組とすることができる。
【００３３】
図２は、本発明の好ましい実施形態のレンダリング・システムをより詳細に示す。グラフィックス・レンダリング・システム２は、レンダラ１０と、コンプレッサ／デコンプレッサ・ユニット２０と、メモリ・インターフェース１５と、表示出力ユニット３０とを含む。レンダラ１０は、Ｚ試験及びテクスチャ・マッピングのような既知の技術を用いて、三角形及び線等のグラフィックス・プリミティブの走査変換を実行する。レンダラは、タイルベースの順番で動作する。レンダラは、メモリ・トラフィックを減少させるためのキャッシュ・ユニットを含むことができる。一部のデータは、メモリ・インターフェース・ユニット１５を介して、レンダラよって読み取られるか、又はグラフィックス・メモリ３に直接書き込まれるが、フレームバッファ等の他のデータに関しては、コンプレッサ／デコンプレッサ・ユニット２０を介して進行することが好ましい。このユニットは、外部メモリバスを介して転送する必要があるデータ量を減少させる。コンプレッサ／デコンプレッサ・ユニットは、メモリ・インターフェース・ユニット１５にアクセスできる。表示出力ユニット３０は、完成した画像データを表示装置４に送る。これは、メモリ・インターフェース・ユニット１５から直接アクセスされる圧縮されていない画像であってもよく、又は、コンプレッサ／デコンプレッサ２０を介してアクセスされる圧縮されたデータであってもよい。単一のエンティティとして示されるが、コンプレッサ／デコンプレッサ・ユニットは、性能を高めるために、複数の並列圧縮／復元ユニットを含むことができる。
【００３４】
図３は、本発明に従ったコンプレッサ／デコンプレッサ・ユニットによって実行される可逆圧縮法の概略図を示す。図３は、異なるデータ・フォーマットに対する圧縮法を示し、異なるデータ・フォーマットは、別個の列（ａ）（ｂ）（ｃ）及び（ｄ）に示されている。データ圧縮のための本方法のステップは、図の上から下へ順番に示される。データ復元においては、ステップは単純に逆になり、従ってページの下から上に示される。
【００３５】
本例においては、この圧縮法は、８ビットの符号なしデータに対して機能する。これは、列（ａ）に示される。列（ｂ）に示す１６ビット浮動小数点データ（ＦＬＯＡＴ１６）及び１６ビット符号付き整数データ（（Ｕ）ＩＮＴ１６）、並びに、列（ｃ）に示されるような３２ビット浮動小数点データ（ＦＬＯＡＴ３２）等の他のデータ・フォーマットが、最初に、８ビット符号なし整数データ（ＵＮＩＴ８）チャネルに分割される。これは、ステップ１２０として示される。
【００３６】
列（ｄ）は、ＲＧＢ（Ａ）色データのための方法を示す。有利なことに、ＲＧＢ（Ａ）色データは、異なる色空間、この例ではＹＣｍＣｎ色空間に変換することができ、又は、さらに詳細に説明されるように、ＪＰＥＧ−ＬＳ変換を用いて変換することができる。この変換ステップ１２５は、ウェーブレット変換に先行するものとして示されるが、ウェーブレット変換の後に実行してもよい。色データの異なるチャネルは、８ビット符号なし整数のデータチャネルである。アルファ・チャネルＡがＲＧＢ（Ａ）データ内に含まれる場合、このアルファ・チャネルＡは、色変換と関係なくエンコードされる。
【００３７】
次いで、ウェーブレット変換を用いて、８ビット符号なし整数データが変換される。本例における変換は、非特許文献３に記載されるリフティング・スキームを用いた線形ウェーブレット変換である。
【００３８】
次いで、ステップ１４０として示されるエントロピー・エンコード・スキームを用いて、係数がエンコードされる。この結果は、ステップ１５０に示される圧縮データである。好ましい実施形態においては、各タイルをエンコードするための４つの選択肢がある。係数は、３つの可変長のエントロピー・エンコード・スキームのうちの１つを用いてエンコードしてもよいし、又は、エンコードしないままにしてもよい。実際にはどのエンコード・スキームもデータを圧縮しない場合には、係数はエンコードされないままになる。
【００３９】
これらのタスクを実行することができるコンプレッサ／デコンプレッサ・ユニット２０を、図４に概略的に示す。ユニットの処理ステップは、コンプレッサ／デコンプレッサ・ユニット内部の全ての演算を調整する状態機械２００によって制御される。圧縮プロセスに言及すると、レンダラ１０の出力は、データの簡易逆多重化を実行する再フォーマット・ユニット２０５に与えられる。これは、図３のステップ１２０の部分に対応する。次いで、再フォーマットされたデータは、クロック・サイクル毎に多数のデータ要素への並列アクセスを与えるレジスタ・ファイルからなることが好ましい、記憶領域２１０に保持される。図３のステップ１２５に対応する色変換、及び、図３のステップ１３０に対応するウェーブレット変換に必要な演算を実行する「並列」算術論理演算ユニット（ＡＬＵ）２２０が、データ記憶装置に取り付けられる。このユニットは、性能上の理由のために、多くのチャネル及び又はピクセル上で、並列して演算を実行する。
【００４０】
色変換及びウェーブレット変換の結果もたらされる係数に対してエントロピー・エンコードを実行するエントロピー・エンコード／デコード・ユニット２３０もまた、データ記憶装置２１０に接続される。これは、図３のステップ１４０に対応する。可変長のエンコードされたデータは、メモリ・インターフェース１５を介してメモリに転送される前に、データバッファ２４０に書き込まれる。
復元は、これらのステップの逆である。表示出力ユニット３０も、データ記憶装置２１０にアクセスすることができ、圧縮されたバッファの表示を可能にする。
【００４１】
ここでステップの各々の好ましい実施形態をより詳細に説明する。全てのデータ型に共通する圧縮アルゴリズムの第１段階は、主として線形ウェーブレットを用いるウェーブレット変換である。本例においては、非特許文献３に記載されるものと同様のリフティング・ベースのスキームを用いて、圧縮されていないデータアレイの代わりにウェーブレット係数が計算される。このスキームにおける更新ステップは、このステップが圧縮率に対してごくわずかな利点（１％未満）しか有さないこと（画像に関して）、又は、利点を低減させること（ｚバッファデータに関して）を本発明者らが見出したため、効率上の理由で省略される。
【００４２】
ウェーブレット変換の各レベルについて、二次元データアレイは、まず水平方向に、次いで垂直方向に変換される。標準的なウェーブレット手法とは異なり、好ましい実施形態はまた、通常、前のステップで既に計算された差異に対して変換を適用することを避けるが、これは、画像データについては、結果的にはごくわずかな改善しか測定されないためである。これに対する例外は後述する。
【００４３】
図５ａにおける疑似コードは、１つのデータチャネルに適用されるようなプロセスを示す。ステップ３００において、処理の反復／レベルの数を求める。ステップ３１０は、これらのレベルを「ループ」し、サブステップ３２０、３２５、３３０、３５０及び３６０を含む。ステップ３２０及び３２５は、このレベルで処理される行のサブセットを判断する。ステップ３３０は、現在の行のサブセットにおける各行をアドレス指定し、各行におけるデータのサブセットに対してウェーブレット・プロセス３３５を実行する。
【００４４】
その後、ステップ３５０は、データの列のどのサブセットがこのレベルで処理されるかを判断し、ステップ３６０は、これらの列を通って、その列におけるピクセルのサブセットに対して再びウェーブレット・プロセス３３５を実行する。
【００４５】
繰り返して説明するが、ステップ３３０における全ての行は、ウェーブレット・プロセス３３５により、独立して処理することができ、従って、並列して実行することができる。同様に、３６０の列の反復もまた、並列して行うことができる。さらに、種々のデータチャネルも独立しており、従って並列して動作することができる。
【００４６】
ウェーブレット変換全体を通して、計算された値は、８ビット演算のみを用いて格納される。これは、［０，２５５］範囲外の計算結果は、［０，２５５］に戻してマッピングされることを意味する。数学的に、これは、２５６を法として全ての演算を実行することに相当する。コンピュータ・システムにおいては、このマッピングは、単に、いずれの計算された結果の最下位８ビットを保持することだけにより、自動的に実現することができる。
【００４７】
ここで図５ｂを参照して、ウェーブレット・プロセス３３５をより詳細に説明する。ウェーブレット・プロセスに与えられる値の組は、「偶数」及び「奇数」の組３７０に分けられる。次に、各々の奇数値は、「リフティング」ステップ３９０を用いて処理される３８０。このことは、リフティング・ステップが各奇数ピクセルに対して独立しているため、反復的に又は並列して行うことができる。リフティング３９０は、以下のステップからなる。
ａ．予測。線形ウェーブレットにおいて、隣接する偶数値を用いて、２つの偶数値の平均をとることにより、奇数値についての予想値を推定する。これは、単純化された形態で図に示される。本実施形態においては、２５６を法とする計算で計算するように適合された、後で詳述される「ＣｌｏｓｅｓｔＡｖｅｒａｇｅ」関数を用いるように適合されている。他の実施形態においては、処理されるデータに応じて選択可能とすることができる。
ｂ．しかしながら、最後の奇数ピクセルにおいては、隣接する偶数は１つ（前のもの）しかないため、その値が予測として用いられる。
ｃ．奇数値とその予測値との差異は、奇数ピクセルの格納位置にライトバック（ｗｒｉｔｅ  ｂａｃｋ）される。
本実施形態に用いられるウェーブレット・プロセスは、偶数値が修正される標準的な「更新」段階を省略する。
【００４８】
計算されたウェーブレット係数からオリジナル・データを回復するための逆ウェーブレット変換は、単に、全ての関係するステップの逆である。これは、変換が、ウェーブレットの最高レベルから最低レベルへ向かって行われる、ここではレベルごとに列が処理され、その後に行が処理されることを意味する。格納された差異からの奇数要素及び隣接する偶数要素を用いる予測値を回復することにより、データが回復される。疑似コードにおいて、これは：
for level = highestWLLevel down to 0
{
for each column in level
{
for each odd element
{
if not border element then
predicted = average(evenLeft, evenRight)
else 
predicted = evenLeft
endif
element = element + predicted;
}
}
for each row in level
{
.
recover odd elements as above
.
}
}
のようになる。
列の「左」及び「右」は、「上」及び「下」として解釈されることに留意されたい。上記の疑似コードに記述される「平均（ａｖｅｒａｇｅ）」関数は、モジュロ演算で機能するように適合されており、後で詳述される。
【００４９】
随意的な色変換及びウェーブレット変換から結果として得られる係数は、可変長のエントロピー・エンコード・スキームを用いてエンコードされる。データアレイは、タイルベースの方法により圧縮され、すなわち、データアレイは、等しいサイズのタイルに分割され、各タイルは個々に圧縮される。好ましい実施形態においては、各タイルに対して４つのエンコード・スキームの選択肢があり、３つのエントロピー・エンコード・スキームのうちの１つを用いてそのウェーブレット係数がエンコードされる、又は、ウェーブレット係数がこれらのスキームによっては圧縮できない場合、すなわち、圧縮ではなく拡張される結果になる場合、そのウェーブレット係数は全くエンコードされず、その代わりに単に８ビット値として出力される。後者の場合には、タイルに対してどのような圧縮も実現されないが、このことは、データを拡張させるスキームにおいては有利である。
【００５０】
以下のエントロピー・エンコード・スキームの説明においては、ウェーブレット係数の値が、１２８だけオフセットされているため、「ゼロ」がヒストグラムの中央に事実上現れる。これは主として、人間が解釈しやすくなるように行われる。図に示されるエンコードもまた、この分布を前提とする。この＋１２８の「追加」（簡略的には、各々の８ビット値の上位ビットを逆にすることに等しい）は、本発明に必要なものではなく、また、エントロピー・エンコード・スキームがこれに応じて調整されるのであれば、等しく効果的な実施形態を、このオフセットなしに済ませ得ることに留意されたい。
【００５１】
エンコードの第１のステップは、圧縮スキームを選択すること又は圧縮を用いないという選択をすることである。全てのスキームを試行して最小の出力を生成したものを選択するよりはむしろ、はるかに安く簡単な発見的手法が用いられる。この発見的手法は、各タイルにおける０、−１、及び１の係数（１２８のオフセットのために、１２８、１２７及び１２９として格納される）の数をカウントし、合計を所定の閾値と比較する。これは、以下の疑似コードに示される。
count = 0;
for each coefficient
{
if (            (coefficient == 128 ) OR 
(coefficient == 127 ) OR 
(coefficient == 129 ) ) then
count = count + 1;
endif
}
Const int numCoefficients = tileWidth * tileHeight;
Const int noPackThresh  = 0.05 * numCoefficients;
Const int scheme1Thresh = 0.3  * numCoefficients;
Const int scheme2Thresh = 0.9  * numCoefficients;
if ( count < noPackThresh ) then
encodingScheme = 0;
else if ( count < scheme1Thresh  )
encodingScheme = scheme1;
else if ( count < scheme2Thresh  )
encodingScheme = scheme2;
else encodingScheme = scheme3;
endif
【００５２】
上記で与えられる閾値定数は、特定のデータ型に合わせてさらに調整することができるが、これらは、レンダリングされたもの及び写真の両方の、主としてＲＧＢ画像で構成される試験されたデータセットについての良好な選択肢となることが分かっている。エンコード・スキームは、ウェーブレット係数が典型的には「ゼロ」の周りにクラスタ化され（例においては、１２８にマッピングされ）、多かれ少なかれベル形状のヒストグラム曲線を形成するという事実を活用する。オリジナルのデータセットが区分的線形関数に近づくほど、その（線形）ウェーブレット係数はゼロに近くなる。反対に、よりランダムな又は雑音の多いデータセットは、より均一に分布したヒストグラムを形成する係数を有する。図６は、画像からの例示的なタイルに対応する。その赤色チャネルのヒストグラム５１０が図６ａに示され、対応するウェーブレット係数のヒストグラム５２０が図６ｂに示される。ここでもウェーブレット係数は１２８だけオフセットされている。
【００５３】
３つのエンコード・スキームの各々は、８ビット空間［０，２５５］を、グループを形成する区間に区分化することからなる。各スキームにおける第１のグループは、１２８（ゼロ）の周りにクラスタ化された最も一般的なウェーブレット係数を含む１つの区間だけを有する。後に続くグループは、より一般的でないウェーブレット係数を含む２つの区間からなる。各々の区間は、格納効率を最大化するために、係数値の２xの数をカバーする。係数を格納するために用いられるビットコードは、グループｉｄ接頭辞及び値からなる。グループｉｄ及び値の両方とも、グループの位置及びサイズに応じた、可変長のものである。グループｉｄは、グループ位置によってゼロ又は少なくとも１からなり、その後に０が続く。最後のグループｉｄは例外であり、ここでは終端の０を省くことができる。例えば、スキーム内に４つより多いグループがあるとき、第４のグループｉｄは１１１０であるが、スキーム内に４つのグループしかない場合には、１１１になる。
【００５４】
グループ値は、グループにおける係数の位置である。例えば、図７に示すスキーム１におけるグループ４は、５つのビット値フィールドを有し、従って、３２の係数値の範囲をカバーする。このグループは、各々が１６の係数値を含む２つの区間［８１、９６］及び［１６１、１７６］からなる。このように含まれる値フィールドが例えば８３である場合には、グループ４の第１の区間に属し、グループ値は「２」である。値フィールドが１７０である場合には、グループ４の第２の区間に属し、そのグループ値は「２５」である。
【００５５】
図７、図８及び図９は、画像データセットから実験的に生み出された３つの異なるエンコード・スキームを示す。各々のスキームは、異なるグループ構造を有する可変長のエントロピー・エンコード・スキームである。これらの図の各々に示されるヒストグラムは、対応するスキームを用いる圧縮に適した例示的なデータからとられる。
【００５６】
データがランダムでないほど、ウェーブレット係数は１２８の周りに集中する。従って、より短い長さのコードを１２８の周りの係数に用い、より長いコードを１２８から遠い係数に用いることによって、よりランダムでないデータについてより高い圧縮を実現することができる。図７に示す第１のスキームは、図８に示す第２のデータ・スキームよりも、ランダムなデータセットに用いられ、図８の第２のデータ・スキームは、図９に示す第３のスキームよりも、ランダムなデータセットに用いられる。
【００５７】
例示的なスキームは、より大きい試験データのセットに基づいてさらに改良することができ、他のエンコード・スキームを代替的な実施形態に対して選択することができる。こうしたスキームの１つは、幾つかの係数の文字列をエンコードすることができる。例えば、数値的に小さい値に対して大きくバイアスがかけられているデータセットについての、単一の値をもつ２つのゼロである。
【００５８】
エンコード・スキームの別の実施形態においては、左上のウェーブレット値、すなわち、「ｄｃ」項は、エントロピー・エンコードされないが、これらは一般にほとんど均一な値の分布を有するため、代わりに単に８ビット値として直接格納される。
【００５９】
デコンプレッサがデータの特定のタイルをデコードすることができる場合、デコンプレッサは、そのタイルに用いられるエンコード・スキームを知る必要がある。従って、エンコードされたタイル・データの最初の２ビットは、以下のようなエンコード・スキームを格納するために用いられる。
００＝圧縮なし
０１＝スキーム１
１０＝スキーム２
１１＝スキーム３
【００６０】
エンコードされたデータ・タイルの復元は簡単である。まず、最初の２ビットからスキームが読み取られる。タイルのウェーブレット係数がエントロピー・エンコードされていない特定の場合においては、デコード・ステップを省略することができ、前述のウェーブレット変換を逆にすることにより、オリジナルのデータを取り出すことができる。他の場合には、タイルのデータ要素の各々を最初にデコードしなければならず、以下のステップを必要とする。
１．０に到達するまで、又は、グループ１の最大数が読み取られるまで、エンコードされたデータ要素をビット毎に読み取ることにより、グループを識別する。
２．グループｉｄの後に続くグループ値を、［０，２５５］範囲内の対応する位置にマッピングする。
【００６１】
代替的な実施形態においては、エンコード・スキームのビットは、メモリ又はレジスタの別個のアレイ内に、１タイル当たり１つのエントリで格納することができる。このアレイはまた、タイル毎に圧縮されたデータのサイズの詳細を含むこともできるため、外部メモリバスは、タイルをデコードするために、正しいデータ転送を要求することができる。
【００６２】
別の代替的な実施形態においては、独立したエンコード・スキームを用いて、異なるチャネルをエントロピー・エンコードすることができる。
【００６３】
エンコードされた係数が可変長であるために、係数のデコード・プロセスは、一般に逐次的である。例えば、より短いビット文字列でエンコードされた係数の対をデコードすることは可能であり得るが、１クロック・サイクル内で行うことができる数を増加させるのは極めて困難である。代替的な実施形態においては、少なくとも１つの付加的な並列エントロピー・デコーダが含められる。記号の第１の部分が第１エントロピー・デコーダによりデコードされ、第２の部分が第２のデコーダによりデコードされる。従って、第２のデコーダは、エンコードされた記号がどこで始まるのか分かり、ビットのオフセットも圧縮されたデータの始めに格納される。こうしたオフセットは確かに圧縮効率を下げるため、従って、こうした実施形態は、デコード速度を圧縮率と引き換えにする。データが決して拡張されないため、オフセットのサイズは有界であることに留意されたい。さらに、代替的な実施形態においては、デコーダ及びオフセットを用いて、速度をさらに増大させることができる。
【００６４】
チャネルにつき８ビットのＲＧＢ（Ａ）の色データを圧縮する場合、データを、ＲＧＢの色チャネル間の相関性を活用する異なる色空間に変換することにより、圧縮率を改善することができる。しかしながら、色空間の変換が可逆的であることは重要であり、従って可逆型画像圧縮が可能である。
【００６５】
ＲＧＢの可逆性を有する１つのこうしたモデルは、非特許文献４及び非特許文献５に説明されるＹＣｏＣｇ−Ｒの色モデルであり、これらの内容は引用により本明細書に組み入れられる。ＲＧＢからＹＣｏＣＧへの変換の概要は、以下に与えられる。
Ｃ0＝Ｒ−Ｂ
ｔ＝Ｂ＋（Ｃ0＞＞１）
Ｃg＝Ｇ−ｔ
Ｙ＝ｔ＋（Ｃg＞＞１）
【００６６】
このモデルは、青色から赤色への、並びに平均化された赤色及び青色のチャネルから緑色への相関を失わせ、色情報のほとんどを１つの輝度（Ｙ）チャネルにパックする。ＹＣｏＣｇ−Ｒにおいては、Ｃｏ及びＣｇチャネルは９ビットに拡張される。変換は、単に８ビットモジュロ演算を用いることによって行うことができるが、これは、値のラップアラウンドによりもたらされる不連続性のため、幾つかの画像についての圧縮率を大幅に減少させる。ＹＣｏＣｇ−Ｒはまた、「ｔ」値についての付加的な一時格納部を必要とすることにも留意されたい。
【００６７】
別の既知の色モデルは、非特許文献６に説明されるＪＰＥＧ２０００の可逆色変換（Ｒｅｖｅｒｓｉｂｌｅ  Ｃｏｌｏｕｒ  Ｔｒａｎｓｆｏｒｍ、ＲＣＴ）であり、この内容は引用により本明細書に組み入れられる。ＲＣＴは：
2010537534.tif 000047
2010537534.tif 000048
2010537534.tif 000049
のように指定される。
【００６８】
８ビットの計算のみに関する問題を防ぐために、ＹＣｏＣｇ／ＲＣＴモデルを修正することができる。ＹＣｍＣｎと名付けられる新しいモデルは、ＹＣｏＣｇ／ＲＣＴモデルと同様に、１つの輝度と２つの色成分（Ｃｍ、Ｃｎ）とからなる。ＲＧＢ色空間からの変換は、以下の：
2010537534.tif 000050
2010537534.tif 000051
2010537534.tif 000052
のように定義される。
【００６９】
ＹＣｏＣｇ及びＲＣＴ色変換の両方において、除算演算がある。８ビット算術を用いて除算を計算するときは、十分に注意しなければならない。従って、上述の変換における４による除算は、後に説明されるＭｏｄｕｌｏｓａｆｅ＿ｄｉｖ４の演算子で置き換えられる。８ビット値で行われる計算は、容易に８ビット範囲外の値をもたらしかねない（すなわち、オーバーフロー・アンダーフロー）。モジュロ演算は、これらの値を８ビット範囲に戻して「マッピング」し、「曖昧さ」をもたらす。
【００７０】
例えば、２つの計算結果、−１２及び６を有し、これらの「平均」を計算したいと仮定する。理想的には、（−１２＋６）／２＝−３に対応する値を期待する。ここで、−１２は、２５６を法として２４４と合同であるため、再マッピングされた値を平均化しようとする場合、（２４４＋６）／２＝１２５が得られるが、実際には２５３（≡２５６を法として−３）の値を期待している。
【００７１】
この問題に対する解決法は、モジュロ演算を用いるときに８ビット範囲［０，２５５］が円を形成することを考慮することにより見出すことができる。これは、１組の値に対して、常に２つの平均があることを意味する。２つの計算結果が、近い値を表わすようになっていると仮定する場合（これは、より典型的な状況である）、すなわち、１２８からより間隔が離れた値が、２つの値のうちの一方の単一の「ラップアラウンド」結果である場合には、「正しい」平均は、円の周りのより短い経路上の平均値を選択することより、計算することができる。これは、次の：
2010537534.tif 000053
により実現される。
【００７２】
さらに、範囲［１２８，２５５］における値が負の値を表わすことを仮定する「ｄｉｖｉｄｅ  ｂｙ  ２」の演算子が定義される。
2010537534.tif 000054
【００７３】
ＲチャネルとＧチャネルとの間、及びＢチャネルとＧチャネルとの間の高い相関が期待されるために、Ｃｍ及びＣｎの両方がゼロに近いと仮定すると、以下の演算を定義することができる。
2010537534.tif 000055
【００７４】
このことは、ほとんどの場合、Ｃｍ及びＣｎの両方の制約のない値は、すなわち、十分な精度の計算を用いており、８ビット精度にマスクしない場合には、範囲［−１２８，１２７］内にあり、１２８より間隔が離れることはないため、実際上良好に機能する。すなわち、ほとんどの場合、ＣｌｏｓｅｓｔＡｖｅｒａｇｅ（Ｃｍ、Ｃｎ）の結果は正しく、範囲［−１２８、１２７］内にあり、負の値は範囲［１２８、２５５］内の値にマッピングされる。このことは次いで、ＤｉｖｉｄｅＢｙＴｗｏの演算子に対する仮定が正しいことを意味する。しかしながら、制約のない値が［−１２８、１２７］の外にあったとしても演算は依然として可逆的である。
【００７５】
従って、最後のＲＧＢのＹＣｍＣｎへの色変換は以下のように記述することができる。
2010537534.tif 000056
2010537534.tif 000057
2010537534.tif 000058
【００７６】
これは、赤色チャネルと緑色チャネル、及び緑色チャネルと青色チャネルとの間の相関を活用する完全に可逆的な色変換である。ＲＧＢの試験画像の大部分においては、これらは、最も顕著な組になったチャネル相関であるが、青色チャネルと赤色チャネルとの間の相関は特に少ないことが見出されている。
【００７７】
チャネルにつき８ビットのＲＧＢ（Ａ）画像を圧縮するためには、そのＲＧＢチャネルは、まずＹＣｍＣｎ空間に変換される。各チャネルは、次いで上述のようにウェーブレット変換され、個々に圧縮されるが、これは、随意的なアルファ・チャネルを含むことができる。オリジナル画像を取り出すのは簡単であり、デコード及び逆ウェーブレット変換後、ＲＧＢチャネルは、ＹＣｍＣｎ変換を逆にすることにより回復される。
2010537534.tif 000059
2010537534.tif 000060
2010537534.tif 000061
【００７８】
Ｙ、Ｃｍ及びＣｎチャネルを変換する際のウェーブレット変換における正しい差分計算を保証するためには、従来技術の線形ウェーブレットに用いられる予測、すなわち
2010537534.tif 000062
が、
2010537534.tif 000063
と置き換えられる。これは、ＹＣｍＣｎ変換は、ｖE_left又はｖE_rightのうちの少なくとも一方が「負」になる結果をもたらす可能性が高く、従って標準的な平均計算が、圧縮の点で不良な結果を生み出すためである。
【００７９】
図１０は、ＲＧＢに実行されたウェーブレットの結果９００と、同等のＹＣｍＣｎデータ９１０とを比較するヒストグラムを示す。標準偏差は、ＲＧＢウェーブレットの色チャネルにおけるもの（９５０乃至９５２）より、ＹＣｍＣｎウェーブレットのＣｍ及びＣｎチャネル９２０、９３０のものの方がはるかに低いことが明らかに分かる。これは、Ｙ、Ｃｍ及びＣｎウェーブレット出力をエントロピー・エンコードすることが、Ｒ、Ｇ及びＢのウェーブレット結果をエンコードすることよりも、より大幅に圧縮された出力をもたらすことを意味する。
【００８０】
代替的な実施形態においては、ＹＣｍＣｎの色変換は、非特許文献７に説明されるＪＰＥＧ−ＬＳ色変換と置き換えられるが、２５６を法として機能するように適合される。多くのＲＧＢ（Ａ）色画像に対して、２５６を法とするＪＰＥＧ−ＬＳ変換を用いることにより、ＹＣｍＣｎより良好な圧縮結果が生み出されることが分かっている。ＪＰＥＧ−ＬＳ変換は、以下の演算： 
2010537534.tif 000064
2010537534.tif 000065
2010537534.tif 000066
を用いて、赤色チャネル及び青色チャネルと緑色チャネルの相関をなくす。
【００８１】
この変換の逆は自明である。ウェーブレット変換の予測ステップにおいては、最近接平均関数（ｃｌｏｓｅｓｔ  ａｖｅｒａｇｅ  ｆｕｎｃｔｉｏｎ）をｒとして用いる必要があり、ｂの値はＪＰＥＧ−ＬＳ変換においてラップアラウンドされることになる。
【００８２】
このように説明される好ましい実施形態においては、色変換は、ウェーブレット変換の前に実行される。別の実施形態においては、最初にウェーブレット変換が行われ、次いで、１つ又はそれ以上の異なる色変換が並列して行われる。次いで、各タイルごとに最良の圧縮をもたらす色変換を選択して、そのタイルを表す。
【００８３】
同じハードウェアの再利用を可能にし、それによりシリコンの費用を減らすために、ＩＥＥＥ規格７５４の３２ビット浮動小数点データが、３２ビット値の各々を４つの別個の８ビット成分に分割し、次いで、各成分ごとにウェーブレット変換を個々に行うことにより、圧縮される。こうした分割の一例を図１１に示す。３２ビット値１０００は、４つの８ビット値１０１０に分割された状態で示される。
【００８４】
種々の自明でないマッピング・スキームにより実験が行われた。しかしながら、圧縮率の点では、単純な分割は非常に有効である。
【００８５】
通常、ウェーブレット変換は、浮動小数点データに対して直接実行されるが、このことは費用のかかる浮動小数点計算装置を暗に示し、浮動小数点の丸めによる精度の損失を招く。代替的には、３２ビット浮動小数点データは、３２ビットの整数データ（２32を法とする）として解釈できるが、３２ビットの計算は依然として費用がかかり、付加的なハードウェアを必要とする。
【００８６】
試験では、分割された３２ビットＨＤＲ又はｚ−バッファデータを圧縮するとき、ウェーブレット変換の予測ステップが前述の「最近接平均」関数を用いる場合には、平均して、２％高い圧縮率が達成されることが示された。
【００８７】
これは、ウェーブレット変換前には、値のラップアラウンドが行われないため奇妙に思われるが、仮数が別個の８ビットチャネルに分割されるので、隣接する値間の滑らかな移行が、幾つかのチャネルにおいてラップアラウンド効果をもたらし、「鋭利な縁部（ｓｈａｒｐ  ｅｄｇｅ）」が生成される。最近接平均関数は、ラップアラウンドの不連続性を滑らかな移行として扱うことにより、これらの状況を正しく処理する。単純な平均計算では、これらの不連続性に近い不良な予測を招き、はるかに大きいウェーブレット係数をもたらす。
【００８８】
３２ビットのｚ−バッファデータを圧縮する場合、従来技術のウェーブレット処理においてより標準的であるように、前のウェーブレット変換ステップにおいて既に計算された差異の差を計算することによって、より高い圧縮を達成することができる。このことは、行及び列の刻み幅を、単に、図５で記述されたアルゴリズムの１つに設定することにより実現される。
【００８９】
１６ビットの浮動小数点及び１６ビットの整数データは、図１２に示す好ましい実施形態により、上述されたような標準的な３２ビット浮動小数点データに用いられたのと同じ簡単な分割技術を用いて圧縮される。１６ビットの浮動小数点データ１０２０及び１６ビットの整数データ１０４０はそれぞれ、８ビットの成分１０３０及び１０５０に分割される。
【００９０】
３２ビットの場合と同様に、１６ビットの浮動小数点データに対する種々の自明でないマッピング・スキームによる実験は、単純な分割に優る改善を示さなかった。
【００９１】
２×２マルチサンプル・アンチエイリアス（Ｍｕｌｔｉ−Ｓａｍｐｌｅｄ  Ａｎｔｉａｌｉａｓｉｎｇ、ＭＳＡＡ）の生データを用いる好ましい実施形態についての圧縮率は、ウェーブレット変換の第１レベルの間、すなわち、単一ピクセル内部に完全に含まれるデータを依然として処理している間、線形ウェーブレットの代わりにハール・ウェーブレット（Ｈａａｒ  ｗａｖｅｌｅｔ）を用いることにより改善される。より高いレベルのＭＳＡＡサンプリングを用いる実施形態においては、より初期のハール・ステップが用いられる。
【００９２】
ハール・ウェーブレットは、圧縮されるデータが、隣接するサンプルにわたって一定であることを前提とする。そのリフティング・ステップ中、奇数要素は、その左の隣接する偶数により予測され、予測された奇数要素と実際の奇数要素との間の差異が、奇数要素に格納される。
2010537534.tif 000067
【００９３】
線形ウェーブレットを計算するときと同様に、ハール変換の更新ステップは、圧縮性能を改善しないため、省略されることが有利である。
【００９４】
各々のオーバーサンプリングされたピクセル内では、色が複製される可能性が非常に高いため、ハール・ウェーブレットはＭＳＡＡ生データに有利である。線形ウェーブレットは、予測のために、隣接する偶数サンプルの両方を用いるので、従って、ＭＳＡＡデータの２×２ブロックの境界にわたる線形のブレンドを予測する。これは、第１のウェーブレット・レベルにおける奇数サンプルは、通常、線形ウェーブレットの代わりにハール・ウェーブレットを用いるとき、予測されるエラーがより少ないことを意味する。このことは、一対の２×２のマルチサンプリングされたピクセルを並べて示す図１３に示される。両方のピクセルは、同じ２つの三角形１１００及び１１０１が横断している。前者は、シェーディング又はテクスチャリングのために、明るい緑色から暗い緑色に変化するが、ＭＳＡＡが実行されると、各三角形についての色は、ピクセル毎に一度だけ評価され、三角形によりカバーされるピクセルにおける全てのサンプルに複製される。例示のために、データの第１行にだけウェーブレットを適用することを考慮する。
【００９５】
図１３の左側には、ハール・ウェーブレットの例が示される。予測される奇数ピクセル１１０４は、純粋に、左の隣接する偶数１１０５からその予測値を取得し、明るい緑色の１００％完璧な予測１１１０をもたらし、これはゼロ係数を格納できることを意味する。
【００９６】
比較のために、図１３の右側は、線形ウェーブレットを用いる、同じ予測される要素１１２０は、今度は、２つの異なる偶数サンプル１１２５及び１１２６の平均からその予測を取得し、これは、１１２５からの明るい緑色と１１２６からの暗い緑色を平均して、中強度の緑色の予測結果１１３０を生み出すことを意味する。これは、非ゼロのウェーブレット係数が格納され、より多くのビットのエンコードを必要とすることを意味する。典型的には、ＭＳＡＡは各ピクセル内部のサンプル値を反復するため、隣接するピクセルの値を用いる予測は、より非生産的なものになりやすい。
【００９７】
さらに圧縮率を増大させるために、本技術を発展させて、非可逆圧縮の選択肢を支持することができる。このことは、修正されたエンコード・スキームを用いてエンコードする前に、ウェーブレット係数におけるよりあまり重要でないビットをゼロにすることにより、達成することができる。従って、可能な値のより小さい数により、より大きい圧縮率が可能になる。より厳格には、より高い周波数項の幾つかをゼロに量子化することができ、このことも同様な効果を有する。しかしながら、可逆形態では用いられないウェーブレットの「更新」ステップは、品質を維持するために必要とされ得る。
【００９８】
本発明の可逆圧縮法はまた、ビデオ処理、すなわち、例えばＭＰＥＧ２、ＭＰＥＧ４及びＨ．２６４などを使用する圧縮／復元システムにも適用可能であり、ここでは幾つかの基準フレームを維持し、圧縮及び復元処理ステップの両方に対して、定期的に参照しなければならない。これらのフレームにアクセスすることは（擬似ランダム順で）、高い帯域幅の費用をもたらしかねないが、この費用は、本明細書に記述される方法により大幅に低減させることができる。
【符号の説明】
【００９９】
１：ホスト
２：グラフィックス・レンダリング・システム
３：グラフィックス・メモリ
４：表示装置
１０：レンダラ
１５：メモリ・インターフェース
２０：コンプレッサ／デコンプレッサ・ユニット
３０：表示出力ユニット
２００：状態機械
２１０：データ記憶装置
２２０：算術論理演算ユニット（ＡＬＵ）
２３０：エントロピー・エンコード／デコード・ユニット
２４０：データバッファ
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
グラフィックス・レンダリング・システムにおいて、二次元電子画像データセットを圧縮するための方法であって、
前記データセットを複数のデータアレイに分割するステップと、
各アレイにウェーブレット変換を行なって、複数のウェーブレット係数を与えるステップであって、ｎは正の整数である場合にウェーブレット変換はｎを法とする演算を用いて行なわれ、２つの値ｖ1及びｖ2の平均は、
2010537534.tif 000068
及び、
2010537534.tif 000069
として計算される、ステップと、
エントロピー・エンコード・スキームを用いて、前記ウェーブレット係数の少なくとも幾つかをエンコードするステップと、
を含むことを特徴とする方法。
【請求項２】
各データアレイは、画像の別個の連続する区域に対応することを特徴とする、請求項１に記載の方法。
【請求項３】
前記ウェーブレット変換を行なう前に、前記データセットを所定のデータ・フォーマットに変換するステップをさらに含むことを特徴とする、請求項１又は請求項２に記載の方法。
【請求項４】
前記所定のデータ・フォーマットは、８ビット符号なし整数のデータ・フォーマットであることを特徴とする、請求項３に記載の方法。
【請求項５】
前記データセットを変換するステップは、より大きいデータ・ユニットを複数のより小さいデータ・ユニットに分割するステップを含むことを特徴とする、請求項３又は請求項４に記載の方法。
【請求項６】
前記より大きいデータ・ユニットを分割するステップは、該より大きいデータ・ユニットを複数の別個のデータチャネルに分割するステップを含むことを特徴とする、請求項５に記載の方法。
【請求項７】
前記ウェーブレット変換を行なうステップ及び前記エンコードするステップは、異なるデータアレイに対して並列して実行されることを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項８】
前記データセットは、複数のデータチャネル画像の単一のデータチャネルであり、前記方法ステップの各々は、前記複数のデータチャネルに適用されることを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項９】
前記ウェーブレット係数を評価し、該ウェーブレット係数の前記評価の結果に基づいて、エントロピー・エンコード・スキームを選択するステップをさらに含むことを特徴とする、前記請求項のいずれか１項に記載の方法。
【請求項１０】
前記係数は各アレイについて評価され、エンコード・スキームが各アレイについて選択されることを特徴とする、請求項９に記載の方法。
【請求項１１】
グラフィックス・レンダリング・システムにおいて、二次元電子画像データセットを圧縮するための装置であって、
前記データセットを複数のデータアレイに分割するための分割手段と、
コンプレッサ・ユニットと、
を含み、前記コンプレッサ・ユニットは、各データアレイにウェーブレット変換を行なって、各データアレイについての複数のウェーブレット係数を出力するための手段であって、ｎは正の整数である場合に前記ウェーブレット変換はｎを法とする演算を用いて行なわれ、２つの値ｖ1及びｖ2の平均は、
2010537534.tif 000070
及び、
2010537534.tif 000071
として計算される、手段と、
エントロピー・エンコード・スキームを用いて、前記複数のウェーブレット係数の少なくとも幾つかをエンコードするためのエンコード手段と、
を含むことを特徴とする装置。
【請求項１２】
各データアレイは、画像の別個の連続する区域に対応することを特徴とする、請求項１１に記載の装置。
【請求項１３】
ウェーブレット変換を行なう前に、前記データセットを、所定のデータ・フォーマットを有するデータチャネルに変換するための再フォーマット・ユニットをさらに含むことを特徴とする、請求項１１又は請求項１２のいずれか１項に記載の装置。
【請求項１４】
色画像データに対して色変換を行なうための色変換手段をさらに含むことを特徴とする、請求項１１から請求項１３までのいずれか１項に記載の装置。
【請求項１５】
前記ウェーブレット係数を評価し、該ウェーブレット係数の前記評価の結果に基づいてエントロピー・エンコード・スキームを選択するための評価手段をさらに含むことを特徴とする、請求項１１から請求項１４までのいずれか１項に記載の装置。
【国際調査報告】
2010537534.tif 000072
2010537534.tif 000073
2010537534.tif 000074
2010537534.tif 000075
2010537534.tif 000076