(57)【特許請求の範囲】
【請求項１】
入力イメージを、前記入力イメージの輝度Ｙ、クロミナンス−オレンジＣｏ、およびクロミナンス−グリーンＣｇで色空間表現を定義するＹＣｏＣｇ表現にマップする色空間マッパと、
前記ＹＣｏＣｇ表現を入力値として受け取り、少なくとも部分的に前記入力値の重複双直交変換に基づく第１の変換係数を含む出力を提供する第１の重複双直交変換と、
前記第１の重複双直交変換から前記第１の変換係数の少なくとも１つを受け取り、少なくとも部分的に前記少なくとも１つの第１の変換係数の重複双直交変換に基づく第２の変換係数を含む出力を提供する第２の重複双直交変換と
を含むことを特徴とするピクチャ圧縮システム。
【請求項２】
前記色空間マッパは、ＲＧＢ入力成分の前記入力イメージを、次式のスケーリングされたバージョンにより前記ＹＣｏＣｇ表現にマップすることを特徴とする請求項１に記載のピクチャ圧縮システム。
【数１】
0004444571.tif 000006
【請求項３】
前記第１の変換係数および前記第２の変換係数の少なくとも１つを量子化し、量子化された係数の出力を提供する量子化器をさらに含むことを特徴とする請求項１に記載のピクチャ圧縮システム。
【請求項４】
前記量子化された係数を走査するスキャナをさらに含むことを特徴とする請求項３に記載のピクチャ圧縮システム。
【請求項５】
前記スキャナは、少なくとも部分的にペアノ様の走査順序を使用することを特徴とする請求項４に記載のピクチャ圧縮システム。
【請求項６】
前記量子化された係数をデジタル式にエントロピー符号化するエントロピー符号器をさらに含むことを特徴とする請求項３に記載のピクチャ圧縮システム。
【請求項７】
前記第１の重複双直交変換は、前記入力値の前記重複双直交変換を行う際、整数演算を利用することを特徴とする請求項１に記載のピクチャ圧縮システム。
【請求項８】
前記第１の重複双直交変換は、前記入力値の前記重複双直交変換を行う際、浮動点演算を利用することを特徴とする請求項１に記載のピクチャ圧縮システム。
【請求項９】
請求項１に記載のピクチャ圧縮システムを使用することを特徴とする写真複写機。
【請求項１０】
請求項１に記載のピクチャ圧縮システムを使用することを特徴とする文書スキャナ。
【請求項１１】
請求項１に記載のピクチャ圧縮システムを使用することを特徴とする光学式文字認織システム。
【請求項１２】
請求項１に記載のピクチャ圧縮システムを使用することを特徴とするパーソナルデジタルアシスタント。
【請求項１３】
請求項１に記載のピクチャ圧縮システムを使用することを特徴とするファックス装置。
【請求項１４】
請求項１に記載のピクチャ圧縮システムを使用することを特徴とするデジタルカメラ。
【請求項１５】
請求項１に記載のピクチャ圧縮システムを使用することを特徴とするデジタルビデオカメラ。
【請求項１６】
請求項１に記載のピクチャ圧縮システムを使用することを特徴とするビデオゲーム装置。
【請求項１７】
入力ビットストリームをデジタル式にエントロピー復号するエントロピー復号器と、
前記エントロピー復号器から入力値を受け取り、逆の階層式の重複双直交変換を利用して出力値を提供する逆変換構成要素と、
輝度Ｙ、クロミナンス−オレンジＣｏ、およびクロミナンス−グリーンＣｇで色空間表現を定義するＹＣｏＣｇ表現の前記逆変換構成要素からの出力値をＲＧＢ出力イメージにマップするリバース色空間マッパと
を含むことを特徴とするピクチャ圧縮解除システム。
【請求項１８】
前記リバース色空間マッパは、次式のスケーリングされたバージョンにより前記ＹＣｏＣｇ表現の前記逆変換構成要素からの出力値をＲＧＢ出力イメージ出力イメージにマップすることを特徴とする請求項１７に記載のピクチャ圧縮解除システム。
【数２】
0004444571.tif 000007
【請求項１９】
前記エントロピー復号された入力ビットストリームをリバース走査し、量子化された第１の変換係数および量子化された第２の変換係数の少なくとも１つの出力を提供するリバーススキャナをさらに含むことを特徴とする請求項１７に記載のピクチャ圧縮解除システム。
【請求項２０】
量子化された第１の変換係数および量子化された第２の変換係数の前記少なくとも１つを逆量子化し、量子化解除された係数の出力を提供する逆量子化器をさらに含むことを特徴とする請求項１９に記載のピクチャ圧縮解除システム。
【請求項２１】
前記エントロピー復号された入力ビットストリームをリバース走査し、量子化された第１の変換係数および量子化された第２の変換係数の少なくとも１つの出力を提供するリバーススキャナをさらに含むことを特徴とする請求項１７に記載のピクチャ圧縮解除システム。
【請求項２２】
量子化された第１の変換係数および量子化された第２の変換係数の前記少なくとも１つを逆量子化し、量子化解除された係数の出力を提供する逆量子化器をさらに含むことを特徴とする請求項１９に記載のピクチャ圧縮解除システム。
【請求項２３】
少なくとも部分的に、入力イメージの輝度Ｙ、クロミナンス−オレンジＣｏ、およびクロミナンス−グリーンＣｇで色空間表現を定義するＹＣｏＣｇ表現の入力値に対する第１の重複双直交変換に基づいて第１レベルの係数を提供すること、および、
少なくとも部分的に前記第１レベルの係数に対する第２の重複双直交変換に基づいて第２レベルの係数を含む出力を提供すること
を含むことを特徴とするピクチャデータ圧縮／符号化のための方法。
【請求項２４】
ＲＧＢ入力成分の入力イメージを、次式のスケーリングされたバージョンにより前記ＹＣｏＣｇ表現の入力値にマップすることを特徴とする請求項２３に記載のピクチャ圧縮／符号化の為の方法。
【数３】
0004444571.tif 000008
【請求項２５】
前記第１レベルの係数を量子化すること、
前記第２レベルの係数を量子化すること、
前記第１レベルの係数および前記第２レベルの係数の少なくとも１つを走査すること、および、
前記第１レベルの係数および前記第２レベルの係数の少なくとも１つを符号化すること
のうち少なくとも１つの動作をさらに含むことを特徴とする請求項２３に記載の方法。
【請求項２６】
入力イメージの輝度Ｙ、クロミナンス−オレンジＣｏ、およびクロミナンス−グリーンＣｇで色空間表現を定義するＹＣｏＣｇ表現の入力値から圧縮／符号化されたピクチャデータを圧縮解除／復号するための方法であって、
係数を復号すること、
少なくとも部分的に復号された係数の逆の重複双直交変換に基づいて第２レベルの係数を提供すること、
少なくとも部分的に第２レベルの係数および復号された係数の逆の重複双直交変換に基づいて第１レベルの係数を提供すること
を含むことを特徴とするピクチャデータ圧縮解除／復号のための方法。
【請求項２７】
前記第１レベルの係数は、前記ＹＣｏＣｇ表現であり、次式のスケーリングされたバージョンにより前記ＹＣｏＣｇ表現をＲＧＢ出力イメージ出力イメージにマップすることをさらに含むことを特徴とする請求項２６に記載のピクチャ圧縮解除／復号のための方法。
【数４】
0004444571.tif 000009
【請求項２８】
ピクチャ圧縮のためのコンピュータプログラムを記憶するコンピュータ可読記憶媒体であって、前記コンピュータプログラムは、コンピュータを
輝度Ｙ、クロミナンス−オレンジＣｏ、およびクロミナンス−グリーンＣｇで色空間表現を定義するＹＣｏＣｇ表現の入力値を受け取り、少なくとも部分的に前記入力値の重複双直交変換に基づく第１の変換係数を含む出力を提供する第１の重複双直交変換手段と、
前記第１の重複双直交変換から前記第１の変換係数の少なくとも１つを受け取り、少なくとも部分的に前記少なくとも１つの第１の変換係数の重複双直交変換に基づく第２の変換係数を含む出力を提供する第２の重複双直交変換手段と
して機能させることを特徴とするコンピュータ可読記憶媒体。
【請求項２９】
前記コンピュータプログラムは、前記コンピュータを、入力イメージのＲＧＢ入力成分を、次式のスケーリングされたバージョンにより前記ＹＣｏＣｇ表現の入力値にマップするマッピング手段として機能させることを特徴とする請求項２８に記載のコンピュータ可読記憶媒体。
【数５】
0004444571.tif 000010
【請求項３０】
入力イメージの輝度Ｙ、クロミナンス−オレンジＣｏ、およびクロミナンス−グリーンＣｇで色空間表現を定義するＹＣｏＣｇ表現の入力値から圧縮／符号化されたピクチャデータを圧縮解除／復号するためのコンピュータプログラムを記憶するコンピュータ可読記憶媒体であって、前記コンピュータプログラムは、コンピュータを
入力ビットストリームをデジタル式にエントロピー復号するエントロピー復号器手段と、
前記エントロピー復号器構成要素から入力値を受け取り、逆の階層式の重複双直交変換を利用して出力値を提供する逆変換手段と、
前記逆変換構成要素からの出力値をＲＧＢ出力イメージにマップするリバース色空間マッパ手段と
として機能させることを特徴とするコンピュータ可読記憶媒体。
【請求項３１】
前記リバース色空間マッパ手段は、次式のスケーリングされたバージョンにより前記ＹＣｏＣｇ表現の出力値をＲＧＢ出力イメージ出力イメージにマップすることを特徴とする請求項３０に記載のコンピュータ可読記憶媒体。
【数６】
0004444571.tif 000011
【請求項３２】
入力イメージを、前記入力イメージの輝度Ｙ、クロミナンス−オレンジＣｏ、およびクロミナンス−グリーンＣｇで色空間表現を定義するＹＣｏＣｇ表現にマッピングするための手段と、
前記ＹＣｏＣｇ表現の入力値を受け取り、少なくとも部分的に前記入力値の重複双直交変換に基づく第１の変換係数を含む出力を提供する第１の重複双直交変換手段と、
前記第１の重複双直交変換から前記第１の変換係数の少なくとも１つを受け取り、少なくとも部分的に前記少なくとも１つの第１の変換係数の重複双直交変換に基づく第２の変換係数を含む出力を提供する第２の重複双直交変換手段と、
前記第１の変換係数および前記第２の変換係数を量子化するための手段と、
前記第１の変換係数および前記第２の変換係数を走査するための手段と、
前記走査された第１の変換係数および前記第２の変換係数をデジタル式にエントロピー符号化するための手段と
を含むことを特徴とするピクチャ圧縮システム。
【請求項３３】
前記ＹＣｏＣｇ表現にマッピングするための手段は、ＲＧＢ入力成分の前記入力イメージを、次式のスケーリングされたバージョンにより前記ＹＣｏＣｇ表現にマップすることを特徴とする請求項３２に記載のピクチャ圧縮システム。
【数７】
0004444571.tif 000012
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、デジタルピクチャ処理に関し、より詳細には、ピクチャ符号化および／または復号を容易にするためのシステムおよび方法に関するものである。
【０００２】
【従来の技術】
コンピュータを介して利用可能な情報の量は、コンピュータネットワーク、インターネット、およびデジタル記憶手段が広く普及するとともに劇的に増加している。そのように情報の量が増加するとともに、情報を迅速に伝送し、その情報を効率的に記憶する必要性が生じている。データ圧縮は、情報の効果的な伝送および記憶を容易にする技術である。
【０００３】
データ圧縮は、情報を表すのに必要なスペースの量を小さくし、多くの情報タイプに関して使用することができる。イメージ、テキスト、オーディオ、およびビデオを含め、デジタル情報を圧縮する要求は、ますます高まっている。通常、データ圧縮は、標準のコンピュータシステムとともに使用される一方、それだけに限らないが、デジタル／衛星テレビジョン並びにセルラー／デジタル電話機など他の技術も、データ圧縮を使用する。
【０００４】
大量の情報を扱い、伝送し、処理する要求が高まるにつれて、そのようなデータを圧縮する要求も高まっている。記憶デバイス容量は相当に増加しているが、情報の要求の方が、容量の進歩を上回っている。例えば、圧縮されていないデジタルピクチャは、５メガバイトのスペースを必要とする可能性があるが、一方、同じピクチャをロスなしに圧縮して、２．５メガバイトのスペースしか必要としないようにすることが可能である。したがって、データ圧縮により、大量の情報を転送することが容易になる。ブロードバンド、ＤＳＬ、ケーブルモデムインターネットなどのように伝送速度が増加しても、圧縮されていない情報では、伝送の限界に容易に達する。例えば、ＤＳＬ回線を介する圧縮されていないイメージの伝送に、１０分間かかる可能性がある。しかし、同じイメージを、圧縮しているとき、およそ１分間で伝送することができ、データスループットで１０倍の利得がもたらされる。
【０００５】
一般に、２つのタイプの圧縮、ロスレス圧縮およびロスのある圧縮が存在する。ロスレス圧縮は、圧縮の後、厳密に元のデータを回復することを可能にし、一方、ロスのある圧縮は、圧縮の後に回復されるデータが、元のデータとは異なることを見込む。ロスのある圧縮の方が、ある程度のデータ完全性の妥協が許容されるため、ロスレス圧縮よりも高い圧縮比を提供することで、この２つの圧縮モード間にはトレードオフが存在する。ロスレス圧縮は、例えば、データを正確に再構成するのに失敗することが、テキストの品質および可読性に劇的に影響を及ぼす可能性があるため、クリティカルなテキストを圧縮する際に使用することができる。ロスのある圧縮は、ある量のひずみまたは雑音が許容可能であるか、または人間の感覚で感知できないピクチャまたはクリティカルでないテキストで使用することができる。
【０００６】
ピクチャの圧縮は、デジタルピクチャが、前述した情報増大の相当な部分であるため、特に重要な技術的問題である。今日のほとんどのＷｅｂページが、多数のピクチャを含み、また多くのオフィス文書も、いくつかのピクチャを含む。デジタルカメラの使用が、急速なペースで増加しており、多くのユーザが、そのようなカメラで文字どおり数千のピクチャを撮影している。
【０００７】
ピクチャ圧縮の最もポピュラーで、広く使用されている技術の１つが、ジョイントフォトグラフィックエキスパーツグループ（Joint Photographic Experts Group）（ＪＰＥＧ）標準である。ＪＰＥＧ標準は、８×８ピクセルの正方形ブロックを、離散コサイン変換（ＤＣＴ）を使用することによって周波数領域にマップすることで機能する。ＤＣＴによって得られた係数が、スケールファクタで割られ、最も近い整数に丸められ（量子化として知られるプロセス）てから、固定のジグザクスキャンパターンを介して１次元ベクトルにマップされる。この１次元ベクトルは、ランレングス符号化とハフマン符号化の組合せを使用して符号化される。
【０００８】
ＪＰＥＧは、ポピュラーで広く使用される圧縮技術であるが、いくつかの欠点を有する。例えば、ＪＰＥＧの１つの欠点は、低いビット伝送速度では、ＤＣＴが、再構成されたイメージにおいて不規則な部分および不連続な部分（タイリング（tiling）アーチファクトまたはブロッキングアーチファクトとして知られる）を生じさせることである。ブロッキングアーチファクトは、８×８ピクセルのブロックのグループ間の境界が、再構成されたイメージにおいて見えるようになることを生じさせる。このブロッキングアーチファクトは、イメージ品質の望ましくない低下を生じさせる。ＪＰＥＧの別の欠点は、ＪＰＥＧが、忠実度が累進的なイメージ再構成を行うことができないことである。言い換えれば、イメージをある忠実度で符号化し、後により低い忠実度が所望される場合（例えば、利用可能な帯域幅またはストレージが限られているため）、そのイメージを復号して、再び符号化しなければならない。
【０００９】
ＪＰＥＧの欠点のいくつかは、ＤＣＴをウェーブレット変換で置き換える新しいＪＰＥＧ２０００によって軽減されている。ウェーブレットは、ブロッキングアーチファクトなしの平滑な信号の再構成を提供するが、ブラーリング（blurring）アーチファクトおよびリンギングアーチファクトの増加をもたらす可能性がある。さらに、ＪＰＥＧ２０００は、比較的複雑な係数符号化システムを使用し、ＪＰＥＧと比べて３×（またはそれを上回って）遅い可能性がある圧縮技術をもたらす。
【００１０】
【発明が解決しようとする課題】
本発明は上記の課題を解決するためになされたもので、デジタルデータを累進的に変形し、符号化するシステムおよび方法を提供するものである。
【００１１】
【課題を解決するための手段】
以下に、本発明のいくつかの態様の基本的理解を提供するための本発明の単純化した概要を提示する。この概要は、本発明を広範に概説するものではない。この概要は、本発明の主要な／クリティカルな要素を明らかにすること、または本発明の範囲を画定することを目的とする。この概要の目的は、後に提示するより詳細な説明の前置きとして、本発明のいくつかの概念を単純化した形で提示することだけである。
【００１２】
本発明は、入力値を（例えば、色空間マッパ（mapper）から）受け取る多重解像度重複変換（multi-resolution lapped transform）を使用するデジタルピクチャ圧縮のシステムおよび方法を提供し、また累進的なレンダリングを提供する。多重解像度重複変換は、ＪＰＥＧなどの離散コサイン変換（ＤＣＴ）を使用する多くの従来のピクチャ圧縮に関連する「ブロッキングアーチファクト」を軽減する階層式の重複双直交変換（hierarchical lapped bi-orthogonal transform）を利用する。さらに、重複双直交変換の使用により、従来のＤＣＴベースのピクチャ圧縮システムと比べて目立った「リンギングアーチファクト」が少なくなる。
【００１３】
本発明の１つの特定の態様は、色空間マッパ、多重解像度重複変換、量子化器、スキャナ、および／またはエントロピー符号器を有するピクチャ圧縮システムを提供する。多重解像度重複変換は、変換係数、例えば、第１の変換係数および第２の変換係数を出力する。多重解像度表現は、多重解像度重複変換の第２の変換係数を利用して得ることができる。色空間マッパは、入力イメージをその入力イメージの色空間表現（例えば、ＹＵＶおよび／またはＹＣＯＣＧ）にマップする。次に、この入力イメージの色空間表現が、多重解像度重複変換に提供される。量子化器は、第１の変換係数および／または第２の変換係数を受け取り、スキャナおよび／またはエントロピー符号器が使用するための量子化された係数の出力を提供する。スキャナはその量子化された係数を走査して、エントロピー符号器が使用するための１次元ベクトルを生成する。ペアノ様の（Peano-like）走査順序は、スキャナによって利用されることが可能である。エントロピー符号器は、量子化器および／またはスキャナから受け取った量子化された係数を符号化して、データ圧縮がもたらされる。エントロピー符号器は、適応ランレングス符号器を利用することができる。
【００１４】
本発明の別の態様は、色空間マッパ、ロスレス変換、およびエントロピー符号器を有するピクチャ圧縮システムを提供する。ロスレス変換は、色空間マッパから入力値を受け取り、ロスレス変換（例えば、階層式アダマール変換）を利用する。
【００１５】
本発明のさらに別の態様は、エントロピー復号器、逆変換、およびリバース色空間マッパを有するピクチャ圧縮解除システムを提供する。エントロピー復号器は、ビットストリーム（例えば、対応するエントロピー符号器によって生成された）を受け取り、そのビットストリームを復号する。エントロピー復号器は、適応ランレングス復号器を利用することができる。
【００１６】
逆変換は、エントロピー復号器から入力値を受け取り、逆変換（例えば、逆向きの階層式の重複双直交変換または逆向きの階層式アダマール変換）を利用する。逆変換は、リバース色空間マッパに出力値を提供する。リバース色空間マッパは、入力値（例えば、ＹＵＶおよび／またはＹＣＯＣＧ）をＲＧＢ出力イメージにマップする。
【００１７】
本発明の別の態様は、セグメント化された階層式イメージシステム、写真複写機、文書スキャナ、光学式文字認織システム、パーソナルデジタルアシスタント、ファックス装置、デジタルカメラ、デジタルビデオカメラ、および／またはビデオゲームを含むが、以上には限定されない多数の様々な文書イメージアプリケーションで使用されるピクチャ圧縮システムを提供する。
【００１８】
本発明の他の態様は、データ圧縮／符号化、データ圧縮解除／復号、一群の係数の走査、色マッピング、およびリバース色マッピングを行うための方法を提供する。ピクチャ圧縮用のシステムのためのコンピュータ使用可能命令を有するコンピュータ可読媒体、およびピクチャ圧縮解除用のシステムのためのコンピュータ使用可能命令を有するコンピュータ可読媒体がさらに提供される。また、データ圧縮を容易にする関連する情報を含む、２つ以上のコンピュータプロセス間で伝送されるように適合されたデータパケットも提供され、この情報は、入力値の重複双直交変換に少なくとも部分的に基づく第１の変換係数、および少なくとも１つの第１の変換係数の重複双直交変換に少なくとも部分的に基づく第２の変換係数を含む。入力値の階層式アダマール変換に少なくとも部分的に基づく第１の変換係数、および少なくとも１つの第１の変換係数の階層式アダマール変換に少なくとも部分的に基づく第２の変換係数を含むデータフィールドを含むデータ圧縮を容易にする、２つ以上のコンピュータ構成要素間で伝送されるように適合されたデータパケットがさらに提供される。
【００１９】
以上の目的および関連する目的を達するため、本発明のいくつかの例としての態様を本明細書で、以下の説明および添付の図面に関連して説明する。ただし、これらの態様は、本発明の原理を使用することができる様々なやり方のいくつかを示すものに過ぎず、本発明は、すべてのそのような態様および等価の態様を含むものとする。本発明の他の利点および新しい特徴は、本発明の以下の詳細な説明を図面と併せて考慮することで明白となる可能性がある。
【００２０】
【発明の実施の形態】
次に、本発明を図面を参照して説明する。すべての図面で、同様の要素を指すのに同様の符号を使用している。以下の説明では、説明に関して、本発明の十分な理解を提供するため、多数の特定の詳細を提示する。ただし、本発明は、それらの詳細なしに実施できることが明白となろう。その他、周知の構造および周知のデバイスは、本発明を説明するのを容易にするため、ブロック図形式で示している。
【００２１】
本出願で使用する「コンピュータ構成要素」という用語は、ハードウェア、ハードウェアとソフトウェアの組合せ、ソフトウェア、または実行中のソフトウェアであるコンピュータ関連エンティティを指すものとする。例えば、コンピュータ構成要素は、プロセッサ上で実行されているプロセス、プロセッサ、オブジェクト、実行ファイル、実行スレッド、プログラム、および／またはコンピュータであることが可能であるが、以上には限定されない。例として、サーバ上で実行されているアプリケーションも、そのサーバもともにコンピュータ構成要素であることが可能である。１つ以上のコンピュータ構成要素が、プロセスおよび／または実行スレッドの内部に存在することが可能であり、また構成要素は、１つのコンピュータ上に局所化され、および／または２つ以上のコンピュータ間で分散されていることが可能である。
【００２２】
図１を参照すると、本発明の態様によるピクチャ圧縮システム１００が示されている。前述した通り、本発明のシステム１００は、多重解像度重複変換１２０の使用を介して、累進的なレンダリング、並びに多くの従来の圧縮システムと比べてブロッキングアーチファクトおよびリンギングアーチファクトの軽減を提供する。ピクチャ圧縮システム１００は、色空間マッパ１１０、多重解像度重複変換１２０、量子化器１３０、スキャナ１４０、およびエントロピー符号器１５０を含む。
【００２３】
色空間マッパ１１０は、入力イメージをその入力イメージの色空間表現にマップする。次に、入力イメージの色空間表現が、多重解像度重複変換１２０に提供される。一例では、色空間マッパ１１０は、入力イメージをＲＧＢ入力イメージ（例えば、レッド、グリーン、ブルーで表現される）のＹＵＶ表現にマップする。ＹＵＶ表現は、Ｙで表される輝度成分、Ｕで表されるクロミナンス−レッド、およびＶで表されるクロミナンス−ブルーを使用する。
【００２４】
別の例では、色空間マッパ１１０は、入力イメージをＹＣｏＣｇ表現にマップする。ＹＣＯＣＧ表現は、Ｙで表される輝度、ＣＯで表されるクロミナンス−オレンジ、およびＣｇで表されるクロミナンス−グリーンを利用する。ＲＧＢ入力成分が、以下の変換を利用して、ＹＣＯＣＧにマップされる（例えば、前述した従来のＹＵＶの代わりに）。
【００２５】
【数１】
0004444571.tif 000002
【００２６】
重要なこととして、ＹＣｏＣｇ色空間マッピングの利点は、ＲＧＢからＹＣｏＣｇへのマッピング、およびＹＣｏＣｇからＲＧＢへの逆変換が、整数演算を利用して達することができ、計算上のオーバーヘッドが小さくなることである。さらに、逆変換は、乗算なしに行うことができる。ＹＣｏＣｇ色空間表現により、普及しているＹＵＶよりも相当に高いパフォーマンスがもたらされる可能性がある。というのは、ＹＣｏＣｇ色空間表現の方が、最新のデジタルピクチャデータに対する主成分解析から得られる統計上最適な空間のよりよい近似となっているからである。
【００２７】
本発明に関連して多重解像度重複変換を利用するデータ圧縮を容易にすることに寄与する多数の他の色空間が、企図されていることを理解されたい。本発明に関連して使用するためのあらゆる適切な色空間表現が、頭記の特許請求の範囲に含まれるものとする。さらに、あらゆる適切なコンピュータプロセス（例えば、整数および／または浮動点）が、本発明による色空間マッパ１１０によって行われることが可能である。
【００２８】
多重解像度重複変換１２０は、例えば、色空間マッパ１１０から入力値を受け取る。多重解像度重複変換１２０により、ピクチャ圧縮システム１００が、累進的なレンダリングを有するようにすることができる。多重解像度重複変換１２０は、階層式の重複双直交変換を利用する。重複変換を使用することにより、ＪＰＥＧなどの、離散コサイン変換（ＤＣＴ）を使用する従来のピクチャ圧縮システムの「ブロッキングアーチファクト」を減らすことができる。さらに、重複双直交変換の使用により、従来のＤＣＴベースのピクチャ圧縮システムと比べて目立った「リンギングアーチファクト」が少なくなる。
【００２９】
図２を参照すると、本発明の態様による重複双直交変換（ＬＢＴ）２００が示されている。ＬＢＴ２００は、第１のブロックのデータに関連する４つの入力ｘ（０）、ｘ（１）、ｘ（２）、およびｘ（３）を有する第１のＤＣＴ様の変換（ＤＣＴ-like transform）２１０（例えば、ＤＣＴに類似するが、同一ではない）を含む。また、ＬＢＴ２００は、第２のブロックのデータに関連する４つの入力ｘ（０）、ｘ（１）、ｘ（２）、およびｘ（３）を有する第２のＤＣＴ様の変換２２０も含む。ＬＢＴ２００は、４つの出力２３０、Ｘ（０）、Ｘ（１）、Ｘ（２）、およびＸ（３）も有する。図２で示す通り、直接変換（例えば、データ圧縮／符号化）では、データは、左から右に処理され、また逆変換（例えば、データ圧縮解除／復号）では、データは、右から左に処理される。スケールファクタは、直接（Ｄ）変換と逆（Ｉ）変換で異なっていることが可能である。
【００３０】
変換の重複部分を行うため、第２のＤＣＴ様の変換２２０に入力されたデータブロックに関する出力２３０が、第１のＤＣＴ様の変換２１０に入力された前のデータブロックの入力に依存する。前に入力されたデータブロックが存在しない場合（例えば、初期設定後および／またはピクチャのコーナにおいて（at corner(s)））、第１のＤＣＴ様の変換２１０への入力値は、完全に定義されていない。具体的には、第１のＤＣＴ様の変換２１０が、行または列の最初のものである場合、ｘ（０）およびｘ（１）が、ピクチャ境界の外側になる。その場合、例としての解決策は、ｘ（１）＝ｘ（２）、かつｘ（０）＝ｘ（３）に設定することにより、偶対称の拡大を使用することである。同様の対称反射をピクセルの行または列に関して最後のＤＣＴ様の変換２１０に適用する。両方の場合で、行または列に関する最初と最後のＤＣＴ様の変換２１０を単純な２×２演算子（例えば、２つの別個の入力、２つの別個の出力）で置き換えることができるのを容易に見て取ることができる。
【００３１】
一例では、ＬＢＴ２００における実質的にすべての計算を、整数演算だけを使用して、乗算を全く使用せずに実行することができる。例えば、所与の値ｚに関して、新しい値ｚ／２が、右シフト、すなわち、ｚ＞＞１として実施される。さらに、ｚを右に２回シフトして、その量をｚに加える（例えば、ｚ＋（ｚ＞＞２））ことにより、量１．２５２を実施することができる。この実施は、シフトによって生成される小さい打切り誤差をもたらす可能性があるが（データが、適切にスケーリングされている限り）、注目に値することとして、この実施は、一般にプロセッサ独立である。というのは、結果が、通常、変換を行うのに使用されるプロセッサに関わらず同じであるからである。したがって、本発明のシステムおよび方法の実質的にすべての実施形態により、ＪＰＥＧ、ＭＰＥＧ、およびその他の標準などの従来のデータ圧縮システムとは異なり、同じ元のピクチャビットマップに関して実質的に同様の圧縮されたファイルがもたらされることが可能である。
【００３２】
図３を簡単に見ると、本発明の態様による多重解像度重複変換３００が示されている。多重解像度重複変換３００は、第１の初期ＬＢＴ３１０１ないし第Ｓ番の初期ＬＢＴ３１０Ｓを含み、Ｓは、１以上の整数である。第１の初期ＬＢＴ３１０１ないし第Ｓ番の初期ＬＢＴ３１０Ｓは、全体として、初期ＬＢＴ３１０と呼ぶことができる。また、多重解像度重複変換３００は、第２のＬＢＴ３２０も含む。多重解像度重複変換３００は、例えば、多重解像度重複変換１２０によって利用されることが可能である。
【００３３】
初期ＬＢＴ３１０が、入力値を受け取る（例えば、色空間マッパ１１０から）。初期ＬＢＴ３１０は、入力値を処理し、入力値の重複双直交変換に少なくとも部分的に基づいて第１の変換係数を出力する。例えば、初期ＬＢＴ３１０は、前述した例としてのＬＢＴ２００を利用することができる。
【００３４】
第１の初期ＬＢＴ３１０１ないし第Ｓ番の初期ＬＢＴ３１０Ｓの第１の変換係数が、第２のＬＢＴ３２０への入力として提供される。一例では、低い周波数の係数（例えば、ＤＣ）が、初期ＬＢＴ３１０によって第２のＬＢＴ３２０に提供される。第２のＬＢＴ３２０は、第１の変換係数を処理し、入力の第１の変換係数の重複双直交変換に少なくとも部分的に基づいて第２の変換係数を出力する。例えば、第２のＬＢＴ３２０は、前述した例としてのＬＢＴ２００を利用することができる。
【００３５】
第２の重複双直交変換３２０の第２の変換係数を利用して多重解像度表現を得ることができる。例えば、逆の階層式ＬＢＴの第２レベルだけを適用することによって再構成されたビットマップにより、従来の双３次ダウンサンプリングフィルタによってもたらされるイメージと同等の元のイメージの４×ダウンサンプリングされたバージョンを表すピクチャビットマップが回復される。
【００３６】
図４を簡単に見ると、本発明の態様による多重解像度重複変換４００が示されている。変換４００は、第１の初期ＬＢＴ４１０１、第２の初期ＬＢＴ４１０２、第３の初期ＬＢＴ４１０３、第４の初期ＬＢＴ４１０４、および２次ＬＢＴ４２０を含む。第１の初期ＬＢＴ４１０１、第２の初期ＬＢＴ４１０２、第３の初期ＬＢＴ４１０３、および第４の初期ＬＢＴ４１０４の低い周波数の係数の出力が、２次ＬＢＴ４２０に入力として提供される。多重解像度重複変換４００は、例えば、多重解像度重複変換１２０によって利用されることが可能である。
【００３７】
次に、図５を見ると、本発明の態様による多重解像度重複変換５００が示されている。変換５００は、初期ＬＢＴ５１０および２次ＬＢＴ５２０を含む。初期ＬＢＴ５１０の低い周波数の係数の出力が、２次ＬＢＴ５２０に順次に提供される。２次ＬＢＴ５２０は、初期ＬＢＴ５１０から十分に低い周波数の係数が受け取られた後、第２レベルの係数の出力を提供する。多重解像度重複変換５００は、例えば、多重解像度重複変換１２０によって利用されることが可能である。
【００３８】
イメージを処理するため、２次元変換が利用される。２次元変換を実行するため、前述したＬＢＴを（例えば、色空間マッパ１１０から受け取られたＹ、Ｃｏ、およびＣｇのそれぞれの）入力値の行および列に適用することができる。一例では、計算上のオーバーヘッドを小さくするため、列全体は処理しない。というのは、各列アクセスが、ほとんどビットマップアレイ全体にわたり、オフキャッシュメモリアクセス（off-cache memory access）が必要とされることになるからである。代わりに、本発明によれば、４行の各セットが処理された後、列変換が行われる内部で「ローリングバッファ（rolling buffer）」の手法を利用することができる。このようにすると、元のビットマップの一回だけの走査で、２次元変換を計算することができる。
【００３９】
図１を再び参照すると、量子化器１３０が、第１の変換係数および／または第２の変換係数を受け取り、スキャナ１４０および／またはエントロピー符号器１５０が使用するための量子化された係数の出力を提供する。量子化器１３０は、通常、ピクチャ圧縮システム１００に情報損失を導入する。損失は、係数の量子化によってもたらされる。というのは、変換された値Ｙに関して、量子化されたバージョンは、通常、ｒ＝ｉｎｔ［（Ｙ＋ｆ）／ｓ］で与えられ、ただし、ｓは、量子化器１３０のステップサイズであり、通常、｜ｆ｜が、ｓ／２に等しく、かつ符号（ｆ）＝符号（Ｙ）となっているからである。したがって、ステップサイズｓが増加するにつれ、ｒの対応するダイナミックレンジが小さくなり、ｒの尤度も同様であり、ゼロに等しくなる。圧縮解除（例えば、復号）中、Ｙの近似が、通常、
【００４０】
【数２】
0004444571.tif 000003
【００４１】
で回復される。したがって、ステップサイズｓが小さくなるほど、近似
【００４２】
【数３】
0004444571.tif 000004
【００４３】
が近くなる。ステップサイズが大きくなるにつれ、通常、データ圧縮が、より効果的になる。ただし、より大きい損失が導入される。一例では、計算上のオーバーヘッドを小さくするため、量子化器１３０が、例えば、整数因子Ｚで値をスケーリングし、Ｚ／ｓを整数で近似することにより、整数演算を利用する。
【００４４】
スキャナ１４０が量子化された係数を走査して、エントロピー符号器１５０が使用するための１次元ベクトルを生成する。一例では、スキャナ１４０は、行方向走査（row-wise scanning）を利用するが、別の例では、スキャナは、列方向走査（column-wise scanning）を利用する。さらに別の例では、スキャナ１４０は、従来のＪＰＥＧデータ圧縮システムにおけるように、ジグザグパターンを利用する。
【００４５】
第４の例では、量子化された係数が、異なってはいるが、やはり固定の（データ独立の）パターンで走査される（例えば、ランダムなデータアクセスを回避するため）。図６を簡単に見ると、本発明の態様による４×４ブロックの係数が示されている。次に、図７を見ると、本発明の態様による１６×１６データマクロブロック（このケースでは、Ｌ＝４であるＬブロックのグループ）に関するペアノ様の走査パターンが示されている。図８は、本発明の態様による４×４ブロックの第２レベルの係数（３２０、４２０、および５２０の２次の重複変換で生成されるもののような）に関する走査パターンを示している。
【００４６】
各マクロブロック（例えば、４×４変換の階層式カスケードで生成される）に関して、変換値が、６グループの係数の１つのグループに読み込まれる。各グループの連続する値が、Ｍ個の連続するマクロブロック（「一まとまり（a "chunk"）」）から読み取られ、６グループは、エントロピー符号器に送られる１つの２５６Ｍ長のベクトルとして連結される。したがって、各まとまりは、独立に符号化することができる。独立した符号化により、各まとまりを独立に復号することができるようになり、所望される場合、ピクチャビットマップの一部分だけを復号することができるようになる。
【００４７】
図７および図８で提示した走査パターンは、ＤＣ係数（例えば、２つのレベルのＬＢＴを経た）に関する空間−周波数の順の走査と、ＡＣ係数（例えば、第１レベルのＬＢＴだけを経た）に関するペアノプラス空間周波数順の走査（Peano plus spatial-frequency-ordered scan）の組合せである。ペアノ成分（図７の陰影付き矢印パターン）を使用して、特定のグループの中で隣接するＡＣ係数の各グループが、隣接する４×４ブロックから来るようにする。
【００４８】
したがって、グループ０は、各マクロブロックの第２レベルのＬＢＴを通過した特定の第２レベルのＤＣ係数を含む。次に、グループ１ないしグループ５の走査を各マクロブロックに関して行うことができ、次にグループ１ないしグループ５の走査を次のマクロブロックに関して行い、以下同様である。グループ１は、あるマクロブロックに関して、そのマクロブロックに関する第２レベルのＬＢＴを経た、残っているＤＣ係数を含む。グループ２は、そのマクロブロックの各ＬＢＴブロックに関して、図示した係数値を含む。グループ３は、そのマクロブロックの各ＬＢＴに関して、図示した係数を含む。グループ４は、そのマクロブロックの各ＬＢＴブロックに関して、図示した係数値を含む。グループ５は、そのマクロブロックの各ＬＢＴブロックに関して、図示した係数値を含む。
【００４９】
図１を再び参照すると、エントロピー符号器１５０が、量子化器１３０および／またはスキャナ１４０から受け取った量子化された係数を符号化している。色空間マッパ１１０、多重解像度重複変換１２０、量子化器１３０、および／またはスキャナ１４０が、元のピクセルデータを、データは全く圧縮されていないが、より小さいダイナミックレンジおよび長いストリングのゼロを伴う整数のベクトルに変換している。エントロピー符号器１５０が、この量子化された係数を符号化し、データ圧縮がもたらされる。
【００５０】
一例では、適応ランレングス符号器が、エントロピー符号器１５０によって利用される。入力ベクトルの各ビット平面が、最上位のビット（ＭＳＢ）から開始して、最下位のビットで終了する順序で処理される。各係数に関して、ビットには、ゼロではないビットがまだ符号化されていない場合、「有意」とラベルが付けられ、あるいはその係数に関して有意なビットが既に符号化されている場合、「リファインメント（refinement）」とラベルが付けられる。リファインメントビットは、ゼロまたは１である尤度が等しく、したがって、変更されずにビットストリームにコピーされる。有意なビットは、ゼロである可能性の方が高く、したがって、適応式の効率的なランレングス符号器を介して符号化され、これにより、テーブル１で記した規則に従って記号が生成される。
【００５１】
【表１】
0004444571.tif 000005
【００５２】
パラメータｋは、ランレングス符号器の圧縮効率を制御する。ｋの値が大きいほど、単一のビット＝０から成るコードワードで表されることが可能なゼロビットのストリングが長くなり、したがって、圧縮比が高くなる。パラメータｋは、データの統計に合わせて「調整」して、２ｋが、ゼロのストリングの最も可能性の高い長さにほぼ等しくなるようにすることができる。
【００５３】
従来のランレングス符号化では、パラメータｋが固定であるか、または定期的に更新され、ビットストリームに加えられる（復号器が、ｋの変更があった場合、それを知っている必要があるため）。双方の手法ともに、相当なパフォーマンスのペナルティをもたらす可能性があるが、これは、２つの理由による。第１に、入力データは、通常、変動する統計を有し、したがって、ｋは、そのような変化を追うために様々である必要がある。第２に、ｋの値をビットストリームにコピーすることによって更新することにより、相当なオーバーヘッドが加わる。というのは、ｋの値を表すのに数ビットが必要とされるからである。したがって、この例の適応ランレングス符号器では、ｋに関する逆方向適応規則が使用される。逆方向で意味するのは、ｋが、入力データに基づいてではなく、符号化された記号に基づいて調整されることである。したがって、符号器および復号器が、同じ適応規則を使用する限り、ｋの値を伝送する必要がない。基本適応規則は、極めて単純である。コードワードが、ゼロである場合、これは、ゼロの連続が観察されたことを意味し、ゼロの連続の可能性がより高いことが予期され、したがって、ｋを増加させる。コードワードが、１で開始する場合、これは、不完全な連続が観察されたことを意味し、したがって、ゼロの連続の可能性がより低いことが予期され、したがって、ｋを減少させる。
【００５４】
ｋを整数で増大させることにより、圧縮パフォーマンスの結果のペナルティとの適合があまりにも急速になり過ぎる可能性がある。したがって、ｋは、分数の量で調整することができる（例えば、ｋのスケーリングされたバージョンを増加または減少させることにより）。
【００５５】
ランレングス符号化記号は、各ビット平面の終りで終端させて、各ビット平面に関する符号化されたデータレングスを有するフィールドを加えることができる。したがって、ビットストリームを構文解析して、所望される場合、最下位のビット平面を除去することができる。これは、データをステップサイズの半分で再符号化することと等価である。したがって、そのデータを再圧縮することが、単に圧縮されたファイルから何らかのビットを構文解析して除くことで達せられる。このため、忠実度のスケーラビリティを実現することができる。
【００５６】
本発明に関連して多重解像度重複変換を利用するデータ圧縮を容易にするのに寄与する多数の他のエントロピー符号化技術（例えば、適応演算符号化）が、企図されることを理解されたい。本発明に関連して使用するためのあらゆる適切なエントロピー符号化技術が、頭記の特許請求の範囲に含まれるものとする。
【００５７】
図１は、ピクチャ圧縮システム１００の構成要素を示したブロック図であるが、色空間マッパ１１０、多重解像度重複変換１２０、量子化器１３０、スキャナ１４０、および／またはエントロピー符号器１５０は、本明細書で用語を定義したところの、１つ以上のコンピュータ構成要素として実装できることを理解されたい。したがって、ピクチャ圧縮システム１００、色空間マッパ１１０、多重解像度重複変換１２０、量子化器１３０、スキャナ１４０、および／またはエントロピー符号器１５０を実装するように動作可能なコンピュータ実行可能構成要素を、本発明に従い、ＡＳＩＣ（特定用途向け集積回路）、ＣＤ（コンパクトディスク）、ＤＶＤ（デジタルビデオディスク）、ＲＯＭ（読取り専用メモリ）、フロッピー（登録商標）ディスク、ハードディスク、ＥＥＰＲＯＭ（電気的に消去可能なプログラマブル読取り専用メモリ）、およびメモリスティックを含むが、以上には限定されないコンピュータ可読媒体上に記憶することが可能なことを理解されたい。
【００５８】
次に、図９を見ると、本発明の態様によるロスレスピクチャ圧縮システム９００が示されている。ロスレスピクチャ圧縮システム９００は、色空間マッパ１１０、ロスレス変換９１０、およびエントロピー符号器１５０を含む。
【００５９】
ロスレス変換９１０が、例えば、色空間マッパ１１０から入力値を受け取る。ロスレス変換９１０は、ロスレス変換を利用する。ロスレス符号化の場合、重なり合う変換を使用する必要はない。というのは、ブロッキングアーチファクトが存在しないからである（量子化が全く関与しないため）。例えば、階層式のアダマール変換が、ロスレス変換９１０によって利用されることが可能である。図１０を簡単に見ると、階層式の変換構造１０１０を利用することができるが、４×４変換モジュールが、ロスレスアダマール構造１０２０によって実装されている。ロスレス変換１０１０は、本明細書で用語を定義したところの、１つ以上のコンピュータ構成要素として実装できることを理解されたい。
【００６０】
図１１を見ると、本発明の態様によるピクチャ圧縮解除システム１１００が示されている。ピクチャ圧縮解除システム１１００は、エントロピー復号器１１１０、リバーススキャナ１１２０、逆量子化器１１３０、逆変換構成要素１１４０、およびリバース色空間マッパ１１５０を含む。
【００６１】
エントロピー復号器１１１０が、ビットストリーム（例えば、対応するエントロピー符号器によって生成された）を受け取り、そのビットストリームを復号する。一例では、エントロピー復号器１１１０は、エントロピー符号器１５０に関して前述したものと同様に動作する適応ランレングス復号器を利用する。
【００６２】
リバーススキャナ１１２０は、エントロピー復号器１１１０から受け取られたエントロピー復号された入力のビットストリームをリバース走査（reverse scan）する。リバーススキャナ１１２０は、量子化された第１の変換係数および／または量子化された第２の変換係数の出力を逆量子化器１１３０に提供する。
【００６３】
一例では、リバーススキャナ１１２０は、行方向のリバース走査を利用するが、別の例では、リバーススキャナは、列方向のリバース走査を利用する。さらに別の例では、リバーススキャナ１１２０は、従来のＪＰＥＧデータ圧縮システムにおけるように、ジグザグパターンを利用する。第４の例では、エントロピー復号された入力のビットストリームが、ペアノ様のリバース走査パターンなどの、異なってはいるが、それでも固定の（データ独立の）パターンで走査される（ランダムなデータアクセスを回避するため）。
【００６４】
逆量子化器１１３０が、リバーススキャナ１１２０から受け取られた量子化された第１の変換係数および／または量子化された第２の変換係数を逆量子化する。逆量子化器１１３０は、量子化解除（unquantize）された係数（例えば、第１の変換係数および／または第２の変換係数）の出力を提供する。
【００６５】
逆変換構成要素１１４０が、逆量子化器１１３０から出力値を受け取る。一例では、逆変換構成要素１１４０は、逆の階層式の重複双直交変換を利用して、出力値をリバース色空間マッパ１１５０に提供する。例えば、逆変換構成要素１１４０は、図２の多重解像度重複変換２００の逆（例えば、右から左へ）を使用することができる。別の例では、逆変換構成要素１１４０は、例えば、逆のロスレス変換（例えば、逆の階層式のアダマール変換）を利用して、ロスレス符号化システム９００を使用して元々符号化されたピクチャビットマップを復号する。例えば、逆変換（例えば、ロスレス）は、基本的に、ロスレスモジュール１０２０における計算を元に戻すことができる（例えば、逆の順序で）。
【００６６】
リバース色空間マッパ１１５０が、入力値をＲＧＢ出力イメージにマップする。一例では、リバース色空間マッパ１１５０は、ＹＵＶ表現をＲＧＢ出力にマップする。別の例では、リバース色空間マッパ１１５０は、ＹＣｏＣｇ表現をＲＧＢ出力にマップする。本発明に関連して、例えば、逆の階層式の重複双直交変換を利用するデータ圧縮解除を容易にすることに寄与する多数の他の色空間表現が企図されることを理解されたい。本発明に関連して使用するためのあらゆる適切な色空間表現が、頭記の特許請求の範囲に含まれるものとする。さらに、あらゆる適切なコンピュータプロセス（整数および／または浮動点）が、本発明によるリバース色空間マッパ１１５０によって行われることが可能である。
【００６７】
エントロピー復号器１１１０、リバーススキャナ１１２０、逆量子化器１１３０、逆変換１１４０、および／またはリバース色空間マッパ１１５０は、コンピュータ構成要素であることが可能なことを理解されたい。
【００６８】
図示し、以上に説明した例としてのシステムに鑑みて、本発明に従って実施することができる方法が、図１２、図１３、図１４、図１６、および図１７の流れ図を参照することで、よりよく理解されよう。説明を簡明にするため、方法を一連のブロックとして図示し、説明しているが、本発明は、そのブロックの順序で限定されないことを理解し、認識されたい。というのは、一部のブロックは、本発明により、本明細書で図示し、説明するものと異なる順序で生じ、および／または他のブロックと同時に生じることが可能であるからである。さらに、すべての図示したブロックが、本発明による方法を実施するのに必要とされる可能性があるわけではない。
【００６９】
本発明は、１つ以上の構成要素によって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的コンテキストで説明することができる。一般に、プログラムモジュールには、特定のタスクを行う、または特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、データ構造等が含まれる。通常、プログラムモジュールの機能は、様々な実施形態で所望に応じて、組み合わせるか、または分散させることができる。
【００７０】
図１２を見ると、本発明の態様によるデータ圧縮／符号化のための方法１２００が示されている。１２１０で、各マクロブロックに関して、各ブロックに関する変換が行われる。一例では、重複双直交変換が使用される（例えば、ロスのあるモード）。別の例では、ロスレスアダマール変換（例えば、ロスレスアダマール構造１０２０）が利用される（例えば、ロスレスモード）。１２２０で、ブロックの低い周波数の係数に対して変換が行われる。一例では、重複双直交変換が使用される（例えば、ロスのあるモード）。第２の例では、ロスレスアダマール変換（例えば、ロスレスアダマール構造１０２０）が利用される（例えば、ロスレスモード）。次に、１２３０で、係数が量子化される。１２４０で、係数が走査される。１２５０で、量子化された係数が符号化される。
【００７１】
図１３を参照すると、本発明の態様によるピクチャ圧縮解除／復号のための方法１３００が示されている。１３１０で、係数が復号される。１３２０で、各マクロブロックに関して、各ブロックに関する低い周波数の係数に対して逆変換が行われる。一例では、逆の重複双直交変換が利用される（例えば、ロスのあるモード）。別の例では、逆のロスレスアダマール変換が使用される（例えば、ロスレスモード）。１３３０で、各ブロックに関する係数に対して逆変換が行われる。一例では、逆の重複双直交変換が利用される（例えば、ロスのあるモード）。第２の例では、逆のロスレスアダマール変換が使用される（例えば、ロスレスモード）。
【００７２】
次に、図１４を参照すると、本発明の態様による一まとまりの係数を走査するための方法１４００が示されている。１４１０で、まとまりの中の各マクロブロックに関する１つの第２レベルの係数（例えば、ＤＣ成分）が走査される。次に、１４２０で、まとまりの中の各マクロブロックに関して、そのマクロブロックに関する残りの第２レベルの係数が走査される。１４３０で、マクロブロックの中の各ブロックに関するグループ２の第１レベルの係数（例えば、ＡＣ成分）が走査される。１４４０で、マクロブロックの中の各ブロックに関するグループ３の第１レベルの係数が走査される。１４５０で、マクロブロックの中の各ブロックに関するグループ４の第１レベルの係数が走査される。１４６０で、マクロブロックの中の各ブロックに関するグループ５の第１レベルの係数が走査される。かたまりの中で、走査されていない何らかのマクロブロックがまだ存在する場合、１４２０で走査が継続される。前述した例としての走査方法では、６つのグループの変換係数（グループ０ないし５）が生成される。そのような走査およびグループ化の構成により、良好な圧縮結果がもたらされるものと考えられるが、例えば、より高速の処理のために圧縮パフォーマンスを犠牲にすることができる場合、任意の他の適切な走査およびグループ化パターンを使用することができる。本発明に関連して使用するためのあらゆるそのような走査／グループ化のパターンが、頭記の特許請求の範囲に含まれるものとする。
【００７３】
図１５を見ると、フォワードマッパ構成要素１５１０（例えば、色空間マッパ１１０が使用するための）が示されている。フォワードマッパ構成要素１５１０は、元のＲＧＢ入力成分が、空間ＹＣｏＣｇにマップされるようにする（例えば、数式（１）のスケーリングされたバージョンを介して）。スケーリングは、２で割ることが必要とされるようになっており（１／２でラベルを付けた矢印で示す通り）、２で割ることは、前述した通り、右シフトによって実行される。最初、そのようなシフトによって導入される誤差は、回復不可能なものであるように思われるかもしれない。しかし、リバースマッパ構成要素１５２０において、フォワードマッパ構成要素１５１０の出力が逆の順序で適用され、シフトによる打切り（例えば、フォワードマッピング構成要素１５１０におけるのと同じ）が生じるようになるが、この場合、その打切りの効果は引かれ（−１／２でラベルを付けた矢印で示す通り）、これにより、元のデータの回復が可能になる。したがって、リバースマッパ構成要素１５２０は、ＹＣｏＣｇ成分から元のＲＧＢ入力成分を（例えば、正確に）回復することができる。
【００７４】
次に、図１６を参照すると、色空間マッピングを行うための方法１６００が示されている。例えば、方法１６００は、フォワードマッパ構成要素１５１０によって使用されることが可能である。
【００７５】
１６１０で、ＲＧＢ入力（Ｒ成分、Ｇ成分、およびＢ成分を含む）が受け取られる。１６２０で、ＲＧＢ入力の平均光度（輝度）の表現を含むＹチャネル出力が提供される。Ｙチャネルは、前述した変換（１）に基づいて提供することができる（例えば、Ｙは、少なくとも部分的に、Ｒ＋２Ｇ＋Ｂに基づいている）。一例では、Ｙチャネルは、乗算なしに、ＲＧＢ入力に関連する情報の加算および／またはシフトを使用して提供することができる。
【００７６】
１６３０で、オレンジに近い方向全体にわたってＲＧＢ入力の色情報（クロミナンス）の表現を含むＣｏチャネル出力が提供される。Ｃｏチャネルは、前述した変換（１）に基づいて提供することができる（例えば、Ｃｏが、少なくとも部分的に、２Ｒ−２Ｂに基づく）。一例では、Ｃｏチャネルを、乗算なしに、ＲＧＢ入力に関連する情報の加算および／またはシフトを使用することによって提供することができる。
【００７７】
１６４０で、グリーンに近い方向全体にわたってＲＧＢ入力の色情報（クロミナンス）の表現を含むＣｇチャネル出力が提供される。Ｃｇチャネルは、前述した変換（１）に基づいて提供することができる（例えば、Ｃｇが、少なくとも部分的に、−Ｒ＋２Ｇ−Ｂに基づく）。一例では、Ｃｇチャネルを、乗算なしに、ＲＧＢ入力に関連する情報の加算および／またはシフトを使用することによって提供することができる。
【００７８】
別の例では、方法１６００に従って提供されるＹＣｏＣｇチャネルのリバースマッピングによってＲ成分、Ｇ成分、および／またはＢ成分を回復することができる。
【００７９】
次に、図１７を見ると、リバース色空間マッピングのための方法１７００が示されている。例えば、方法１７００は、リバースマッパ構成要素１５２０によって使用されることが可能である。
【００８０】
１７１０で、平均光度を表すＹチャネル、オレンジに近い方向全体にわたって色情報を表すＣｏチャネル、およびグリーンに近い方向全体にわたって色情報を表すＣｇチャネルを含むＹＣｏＣｇ入力が受け取られる。１７２０で、少なくとも部分的に、ＹＣｏＣｇ入力に基づくＲ成分が提供される。Ｒ成分は、前述した変換（１）に基づいて提供することができる（例えば、Ｒが、少なくとも部分的に、Ｙ＋Ｃｏ−Ｃｇに基づく）。一例では、Ｒ成分を、乗算なしに、ＹＣｏＣｇ入力に関連する情報の加算および／またはシフトを使用することによって提供することができる。
【００８１】
１７３０で、少なくとも部分的に、ＹＣｏＣｇ入力に基づくＧ成分が提供される。Ｇ成分は、前述した変換（１）に基づいて提供することができる（例えば、Ｇが、少なくとも部分的に、Ｙ＋Ｃｇに基づく）。一例では、Ｇ成分を、乗算なしに、ＹＣｏＣｇ入力に関連する情報の加算および／またはシフトを使用することによって提供することができる。
【００８２】
１７４０で、少なくとも部分的に、ＹＣｏＣｇ入力に基づくＢ成分が提供される。Ｂ成分は、前述した変換（１）に基づいて提供することができる（例えば、Ｂが、少なくとも部分的に、Ｙ＋Ｃｏ−Ｃｇに基づく）。一例では、Ｂ成分を、乗算なしに、ＹＣｏＣｇ入力に関連する情報の加算および／またはシフトを使用することによって提供することができる。
【００８３】
本発明のシステムおよび／または方法を圧縮システム全体において利用して、テキスト、手書き、図面、ピクチャ等の圧縮を容易にすることができるのが理解されよう。さらに、本発明のシステムおよび／または方法を、写真複写機、文書スキャナ、光学式文字認織システム、ＰＤＡ、ファックス装置、デジタルカメラ、デジタルビデオカメラ、および／またはビデオゲームを含むが、以上には限定されない多数の様々な文書イメージアプリケーションにおいて使用できることが、当分野の技術者には認められよう。
【００８４】
本発明の様々な態様のさらなるコンテキストを提供するため、図１８および以下の考察は、本発明の様々な態様を実施することができる適切な動作環境１８１０の簡単な一般的説明を提供することを目的とする。図１９が、本発明が動作することができる追加の動作環境および／または代替の動作環境を提供する。本発明を、１つ以上のコンピュータまたはその他のデバイスによって実行される、プログラムモジュールなどの、コンピュータ実行可能命令の一般的コンテキストで説明するが、本発明は、他のプログラムモジュールと組み合わせて、および／またはハードウェアとソフトウェアの組合せとして実施することも可能なことが、当分野の技術者には認められよう。ただし、一般に、プログラムモジュールには、特定のタスクを行うか、または特定のデータタイプを実装するルーチン、プログラム、オブジェクト、構成要素、データ構造等が含まれる。動作環境１８１０は、適切な動作環境の一例に過ぎず、本発明の使用または機能の範囲に関する何らかの限定を示唆するものではない。本発明とともに使用するのに適していることが可能な他の周知のコンピュータシステム、コンピュータ環境、および／またはコンピュータ構成には、パーソナルコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラマブル家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、以上のシステムまたはデバイスを含む分散コンピューティング環境等が含まれるが、以上には限定されない。
【００８５】
図１８を参照すると、本発明の様々な態様を実施するための例としての動作環境１８１０が、コンピュータ１８１２を含む。コンピュータ１８１２は、処理ユニット１８１４、システムメモリ１８１６、およびシステムバス１８１８を含む。システムバス１８１８は、システムメモリ１８１６ないし処理ユニット１８１４を含むが、以上には限定されないシステム構成要素を結合する。処理ユニット１８１４は、様々な利用可能なプロセッサの任意のものであることが可能である。また、デュアルマイクロプロセッサおよびその他のマルチプロセッサアーキテクチャも、処理ユニット１８１４として使用することができる。
【００８６】
システムバス１８１８は、１８ビットバス、インダストリアルスタンダードアーキテクチャ（Industrial Standard Architecture）（ＩＳＡ）、マイクロチャネルアーキテクチャ（Micro-Channel Architecture）（ＭＳＡ）、エクステンデッドＩＳＡ（Extended ISA）（ＥＩＳＡ）、インテリジェントドライブエレクトロニクス（Intelligent Drive Electronics）（ＩＤＥ）、ＶＥＳＡローカルバス（VESA Local Bus）（ＶＬＢ）、ペリフェラルコンポーネントインターコネクト（Peripheral Component Interconnect）（ＰＣＩ）、ユニバーサルシリアルバス（Universal Serial Bus）（ＵＳＢ）、アドバンストグラフィックスポート（Advanced Graphics Port）（ＡＧＰ）、パーソナルコンピュータメモリカードインターナショナルアソシエーション（Personal Computer Memory Card International Association）（ＰＣＭＣＩＡ）バス、およびスモールコンピュータシステムズインターフェース（Small Computer Systems Interface）（ＳＣＳＩ）を含むが、以上には限定されない任意の様々な利用可能なバスアーキテクチャを使用する、メモリバスまたはメモリコントローラ、周辺バスまたは外部バス、および／またはローカルバスを含むいくつかのタイプのバス構造の任意のものであることが可能である。
【００８７】
システムメモリ１８１６は、揮発性メモリ１８２０および不揮発性メモリ１８２２を含む。起動中などに、コンピュータ１８１２内部の要素間で情報を転送する基本ルーチンを含む基本入力／出力システム（ＢＩＯＳ）が、不揮発性メモリ１８２２の中に記憶される。例として、限定としてではなく、不揮発性メモリ１８２２には、読取り専用メモリ（ＲＯＭ）、プログラマブルＲＯＭ（ＰＲＯＭ）、電気的にプログラマブルなＲＯＭ（ＥＰＲＯＭ）、電気的に消去可能なＲＯＭ（ＥＥＰＲＯＭ）、またはフラッシュメモリが含まれることが可能である。揮発性メモリ１８２０には、外部キャッシュメモリとして作用するランダムアクセスメモリ（ＲＡＭ）が含まれる。例として、限定としてではなく、ＲＡＭは、シンクロナス（synchronous）ＲＡＭ（ＳＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、ダブルデータレート（double data rate）ＳＤＲＡＭ（ＤＤＲ  ＳＤＲＡＭ）、エンハンスト（enhanced）ＳＤＲＡＭ（ＥＳＤＲＡＭ）、シンクリンク（Synchlink）ＤＲＡＭ（ＳＬＤＲＡＭ）、およびダイレクトラムバス（direct Rambus）ＲＡＭ（ＤＲＲＡＭ）などの多くの形態で入手可能である。
【００８８】
また、コンピュータ１８１２は、取外し可能／取外し不可能な、揮発性／不揮発性のコンピュータ記憶媒体も含む。図１８は、例えば、ディスクストレージ１８２４を示している。ディスクストレージ１８２４には、磁気ディスクドライブ、フロッピー（登録商標）ディスクドライブ、テープドライブ、Ｊａｚｚ（登録商標）ドライブ、Ｚｉｐ（登録商標）ドライブ、ＬＳ−１００ドライブ、フラッシュメモリカード、またはメモリスティックが含まれるが、以上には限定されない。さらに、ディスクストレージ１８２４は、独立に、あるいはコンパクトディスクＲＯＭデバイス（ＣＤ−ＲＯＭ）、書込み可能ＣＤドライブ（ＣＤ−Ｒ  Ｄｒｉｖｅ）、書換え可能ＣＤドライブ（ＣＤ−ＲＷ  Ｄｒｉｖｅ）、またはデジタルバーサタイルディスクＲＯＭドライブ（ＤＶＤ−ＲＯＭ）などの光ディスクドライブが含まれるが、以上には限定されない他の記憶媒体との組合せで記憶媒体を含むことが可能である。ディスクストレージデバイス１８２４をシステムバス１８１８に接続するのを容易にするため、インターフェース１８２６のような取外し可能な、または取外し不可能なインターフェースが、通常、使用される。
【００８９】
図１８は、ユーザと、適切な動作環境１８１０において説明した基本的なコンピュータリソースの間の仲介として動作するソフトウェアを描いていることが認められよう。そのようなソフトウェアには、オペレーティングシステム１８２８が含まれる。ディスクストレージ１８２４上に記憶することができるオペレーティングシステム１８２８は、コンピュータシステム１８１２のリソースの制御および割振りを行うように動作する。システムアプリケーション１８３０は、システムメモリ１８１６の中に、またはディスクストレージ１８２４上に記憶されたプログラムモジュール１８３２およびプログラムデータ１８３４を介してオペレーティングシステム１８２８によるリソースの管理を利用する。本発明を、様々なオペレーティングシステムを使用して、またはオペレーティングシステムの組合せを使用して実施できることが理解されよう。
【００９０】
ユーザは、入力デバイス１８３６を介してコマンドまたは情報をコンピュータ１８１２に入力する。入力デバイス１８３６には、マウス、トラックボール、スタイラス、タッチパッドなどのポインティングデバイス、キーボード、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナ、ＴＶチューナカード、デジタルカメラ、デジタルビデオカメラ、ウェブカメラ等が含まれるが、以上には限定されない。以上の入力デバイスおよびその他の入力デバイスが、インターフェースポート１８３８を介してシステムバス１８１８を通して処理ユニット１８１６に接続される。インターフェースポート１８３８には、例えば、シリアルポート、パラレルポート、ゲームポート、およびユニバーサルシリアルバス（ＵＳＢ）が含まれる。出力デバイス１８４０は、同じタイプのポートのいくつかを入力デバイス１８３６として使用する。したがって、例えば、ＵＳＢポートを使用して入力をコンピュータ１８１２に提供し、またコンピュータ１８１２から出力デバイス１８４０に情報を出力することができる。特別のアダプタを必要とする出力デバイス１８４０として、とりわけモニタ、スピーカ、およびプリンタのようないくつかの出力デバイス１８４０が存在するのを示すため、出力アダプタ１８４２を提供している。出力アダプタ１８４２には、例として、限定としてではなく、出力デバイス１８４０とシステムバス１８１８の間の接続手段を提供するビデオカードおよびサウンドカードが含まれる。遠隔コンピュータ１８４４のような他のデバイスおよび／またはデバイスのシステムは、入力能力と出力能力をともに提供することに留意されたい。
【００９１】
コンピュータ１８１２は、遠隔コンピュータ１８４４のような１つ以上の遠隔コンピュータに対する論理接続を使用するネットワーク化された環境で動作することができる。遠隔コンピュータ１８４４は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ワークステーション、マイクロプロセッサベースの機器、ピアデバイス、または他の一般的なネットワークノード等であることが可能であり、通常、コンピュータ１８１２に関連して説明した要素の多く、またはすべてを含む。簡略のため、メモリ記憶デバイス１８４６だけを遠隔コンピュータ１８４４とともに示している。遠隔コンピュータ１８４４は、コンピュータ１８１２にネットワークインターフェース１８４８を介して論理接続されており、通信コネクション１８５０を介して物理的に接続される。ネットワークインターフェース１８４８は、ローカルエリアネットワーク（ＬＡＮ）およびワイドエリアネットワーク（ＷＡＮ）などの通信網を包含する。ＬＡＮ技術には、ファイバディストリビューテッドデータインターフェース（Fiber Distributed Data Interface）（ＦＤＤＩ）、コッパディストリビューテッドデータインターフェース（Copper Distributed Data Interface）（ＣＤＤＩ）、イーサネット（登録商標）／ＩＥＥＥ  １５０２．３、トークンリング／ＩＥＥＥ  １５０２．５等が含まれる。ＷＡＮ技術には、ポイントツーポイントリンク、統合デジタル通信網（ＩＳＤＮ）およびその変形形態のような回線交換網、パケット交換網、およびデジタル加入者回線（ＤＳＬ）が含まれるが、以上には限定されない。
【００９２】
通信コネクション１８５０とは、ネットワークインターフェース１８４８をバス１８１８に接続するのに使用されるハードウェア／ソフトウェアを指す。通信コネクション１８５０は、明確に示すため、コンピュータ１８１２の内部に示しているが、コンピュータ１８１２の外部にあることも可能である。ネットワークインターフェース１８４８に接続するために必要なハードウェア／ソフトウェアには、単に例として、通常の電話品質のモデム、ケーブルモデムおよびＤＳＬモデム、ＩＳＤＮアダプタ、並びにイーサネット（登録商標）カードを含むモデムなどの内部技術および外部技術が含まれる。
【００９３】
図１９は、本発明が対話することができるサンプルのコンピューティング環境１９００を示す概略ブロック図である。システム１９００は、１つ以上のクライアント１９１０を含む。クライアント１９１０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）であることが可能である。また、システム１９００は、１つ以上のサーバ１９３０も含む。サーバ１９３０も、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）であることが可能である。サーバ１９３０は、例えば、本発明を使用することによって変換を行うスレッドを収容することができる。クライアント１９１０とサーバ１９３０間の１つの可能な通信は、２つ以上のコンピュータプロセスの間で伝送されるように適合されたデータパケットの形態であることが可能である。システム１９００は、クライアント１９１０とサーバ１９３０の間で通信を容易にするのに使用することができる通信フレームワーク１９５０を含む。クライアント１９１０は、クライアント１９１０にローカルで情報を記憶するのに使用することができる１つ以上のクライアントデータストアに動作上、接続される。同様に、サーバ１９３０も、サーバ１９３０にローカルで情報を記憶するのに使用することができる１つ以上のサーバデータストア１９４０に動作上、接続される。
【００９４】
以上に説明したことが、本発明の例を含む。もちろん、本発明を説明するために構成要素または方法の考えられるすべての可能な組合せを説明することは、可能ではないが、本発明の多くのさらなる組合せまたは置換えが可能であるのを当分野の技術者は認識することができよう。したがって、本発明は、頭記の特許請求の範囲の趣旨および範囲に含まれるすべてのそのような変更形態、改変形態、および変形形態を包含するものとする。さらに、「含まれる」という用語が、詳細な説明または特許請求の範囲で使用される限り、そのような用語は、請求項において従来の用語として使用される際、「含む」という用語が解釈されるのと同じように包括的であるものとする。
【図面の簡単な説明】
【図１】本発明の態様によるピクチャ圧縮システムを示すブロック図である。
【図２】本発明の態様による重複双直交変換を示すブロック図である。
【図３】本発明の態様による多重解像度重複変換を示すブロック図である。
【図４】本発明の態様による多重解像度重複変換を示すブロック図である。
【図５】本発明の態様による多重解像度重複変換を示すブロック図である。
【図６】本発明の態様による４×４データブロックを示すブロック図である。
【図７】本発明の態様による１６×１６マクロブロックに関するペアノ様の走査パターンを示すブロック図である。
【図８】本発明の態様による第２レベルの係数の４×４ブロックに関する走査パターンを示すブロック図である。
【図９】本発明の態様によるピクチャ圧縮システムを示すブロック図である。
【図１０】本発明の態様によるレングス４アダマール変換を示すブロック図である。
【図１１】本発明の態様によるピクチャ圧縮解除システムを示すブロック図である。
【図１２】本発明の態様によるデータ圧縮／符号化のための方法を示す流れ図である。
【図１３】本発明の態様によるデータ圧縮解除／復号のための方法を示す流れ図である。
【図１４】本発明の態様による一まとまりの係数を走査するための方法を示す流れ図である。
【図１５】本発明の態様によるロスレス色空間フォワードマッパ構成要素およびリバースマッパ構成要素を示すブロック図である。
【図１６】本発明の態様による色空間マッピングを行うための方法を示す流れ図である。
【図１７】本発明の態様によるリバース色空間マッピングを行うための方法を示す流れ図である。
【図１８】本発明が機能することができる例としての動作環境を示す図である。
【図１９】本発明による例としての通信環境を示す概略ブロック図である。
【符号の説明】
１００  ピクチャ圧縮システム
１１０  色空間マッパ
１２０，２００，３００，４００，５００  多重解像度重複変換
１３０  量子化器
１４０  スキャナ
１５０  エントロピー符号器
２１０，２２０  ＤＣＴ様の変換
２３０  出力
３２０  重複双直交変換
９００  ロスレスピクチャ圧縮システム（ロスレス符号化システム）
９１０，１０１０  ロスレス変換
１０２０  ロスレスアダマール構造（ロスレスモジュール）
１１００  ピクチャ圧縮解除システム
１１１０  エントロピー復号器
１１２０  リバーススキャナ
１１３０  逆量子化器
１１４０  逆変換
１１５０  リバース色空間マッパ
１５１０  フォワードマッピング構成要素
１５２０  リバースマッパ構成要素
１８１０  動作環境
１８１２  コンピュータシステム
１８１４  処理ユニット
１８１６  システムメモリ
１８１８  システムバス
１８２０  揮発性メモリ
１８２２  不揮発性メモリ
１８２４  ディスクストレージ
１８２６  インターフェース
１８２８  オペレーティングシステム
１８３０  システムアプリケーション
１８３２  プログラムモジュール
１８３４  プログラムデータ
１８３６  入力デバイス
１８３８  インターフェースポート
１８４０  出力デバイス
１８４２  出力アダプタ
１８４４  遠隔コンピュータ
１８４６  メモリ記憶デバイス
１８４８  ネットワークインターフェース
１８５０  通信コネクション
１９００  コンピューティング環境
１９１０  クライアント
１９３０  サーバ
１９４０  サーバデータストア
１９５０  通信フレームワーク
【図１】
0004444571.tif 000013
【図２】
0004444571.tif 000014
【図３】
0004444571.tif 000015
【図４】
0004444571.tif 000016
【図５】
0004444571.tif 000017
【図６】
0004444571.tif 000018
【図７】
0004444571.tif 000019
【図８】
0004444571.tif 000020
【図９】
0004444571.tif 000021
【図１０】
0004444571.tif 000022
【図１１】
0004444571.tif 000023
【図１２】
0004444571.tif 000024
【図１３】
0004444571.tif 000025
【図１４】
0004444571.tif 000026
【図１５】
0004444571.tif 000027
【図１６】
0004444571.tif 000028
【図１７】
0004444571.tif 000029
【図１８】
0004444571.tif 000030
【図１９】
0004444571.tif 000031