(57)【要約】サブ解像度画像を使用する、画像圧縮および解凍のための方法、システム、および製造品が開示される。画像の圧縮は、複数のエントロピー符号組を決定することと、複数のエントロピー符号組を備えている第１のサブ解像度画像を含む１つ以上のサブ解像度画像を生成することと、１つ以上のサブ解像度画像を使用して、入力画像をエンコードすることと、圧縮されたエントロピー符号化画像ファイルとして、エンコードされた入力画像および生成された１つ以上のサブ解像度画像を出力することとを含む。画像の解凍は、画像ファイルを分解し、エンコードされた圧縮入力画像および複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像にアクセスすることと、それぞれのサブ解像度画像を使用して、エンコードされた圧縮入力画像をデコードすることとを含む。
2014525183.tif 000002
【特許請求の範囲】
【請求項１】
入力画像を圧縮する方法であって、前記方法は、
前記入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
前記複数のエントロピー符号組への参照を備えている第１のサブ解像度画像を含む１つ以上のサブ解像度画像を生成することであって、前記参照の各々は、前記入力画像内の対応する画素をエンコードするために使用される、前記エントロピー符号組のうちの１つを示す、ことと、
エントロピー符号を含む１つ以上の圧縮パラメータを制御するために前記生成された１つ以上のサブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、少なくとも前記エンコードされた入力画像および前記生成された１つ以上のサブ解像度画像を出力することと
を含む、方法。
【請求項２】
入力画像を圧縮する方法であって、前記方法は、
前記入力画像から、複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像を生成することと、
前記複数の圧縮パラメータの各々を制御するために前記それぞれのサブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、少なくとも前記エンコードされた入力画像および前記生成されたサブ解像度画像を出力することと
を含む、方法。
【請求項３】
前記それぞれのサブ解像度画像を生成することは、
前記入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
前記複数のエントロピー符号組への参照を備えている第１のサブ解像度画像を生成することであって、前記参照の各々は、前記入力画像内の対応する画素をエンコードするために使用される、前記エントロピー符号組のうちの１つを示す、ことと
を含む、請求項２に記載の方法。
【請求項４】
前記複数のエントロピー符号組を決定することは、
前記入力画像を複数のブロックに分割することと、
前記複数のブロックからのそれぞれのブロックに対するエントロピー統計を決定することと、
前記決定されたエントロピー統計の類似性に従って、前記複数のブロックをクラスタ化し、複数のブロッククラスタを形成することと、
前記ブロッククラスタの各々に対するエントロピー符号を決定することと
を含む、請求項３に記載の方法。
【請求項５】
形成されるブロッククラスタの数は、前記第１のサブ解像度画像のビットのサイズを最小限にすることに基づいて決定される、請求項４に記載の方法。
【請求項６】
前記それぞれのサブ解像度画像を生成することは、
前記入力画像のそれぞれのブロックに対して、予測のエントロピーを低減させるように構成されている空間的予測子を決定することと、
前記それぞれのブロックに対する前記空間的予測子を備えている第２のサブ解像度画像を生成することと
を含む、請求項２に記載の方法。
【請求項７】
前記入力画像をエンコードすることは、前記第２のサブ解像度画像から、前記入力画像のそれぞれのブロックに対する前記空間的予測子を決定することを含む、請求項６に記載の方法。
【請求項８】
前記空間的予測子を決定することは、前記ブロックに対するエンコーディングコスト、前記複数のブロックに対する予測誤差、および近傍画素に対して選択された空間的予測子に対するバイアスを最小限化することにさらに基づく、請求項６に記載の方法。
【請求項９】
前記それぞれのサブ解像度画像を生成することは、
前記入力画像のそれぞれのブロックに対して、前記ブロックの画素における２つ以上のカラー成分間の相関に対応するカラー相関係数を決定することと、
前記それぞれのブロックに対する前記カラー相関係数を備えている第３のサブ解像度画像を生成することと
を含む、請求項２に記載の方法。
【請求項１０】
前記ブロックに対する前記カラー相関係数を決定することは、
緑色成分、赤色成分、および青色成分のうちの任意の２つ間の相関と、
前記ブロックにおける赤色チャネルおよび青色チャネルにおけるエントロピーを低減させることと
にさらに基づく、請求項９に記載の方法。
【請求項１１】
前記入力画像をエンコードすることは、前記第３のサブ解像度画像からアクセスされる前記カラー相関係数を少なくとも部分的に使用して、予測誤差を決定することを含む、請求項９に記載の方法。
【請求項１２】
前記入力画像をエンコードすることは、別個のエントロピー符号を使用して、赤色チャネル、青色チャネル、緑色チャネル、およびαチャネルをエンコードすることを含む、請求項２に記載の方法。
【請求項１３】
前記入力画像をエンコードすることは、前記入力画像の１つ以上のブロックのそれぞれの群に対して、カラーパレットを局所的に決定することを含む、請求項２に記載の方法。
【請求項１４】
前記カラーパレットは、ハッシュ法を使用して、動的に決定される、請求項１３に記載の方法。
【請求項１５】
前記エンコードされた入力画像および前記生成されたサブ解像度画像のエンコードされたものを保存することが、第１のエンコーディング技法を使用して、前記入力画像、前記第１のサブ解像度画像、前記第２のサブ解像度画像、および前記第３のサブ解像度画像をエンコードすることを含む、請求項２に記載の方法。
【請求項１６】
前記エンコードすることは、
それぞれのコストに基づいて、前記入力画像内のそれぞれの画素に対して、先に生じた画素への逆方向参照を挿入すること、前記画素を挿入すること、またはカラーパレットエントリからのインデックスを挿入することのうちの１つから動作を選択し、中間画像を生成することと、
前記中間画像の最初の画素から最後の画素への動作の最小コスト経路を決定することと
を含む、請求項２に記載の方法。
【請求項１７】
前記逆方向参照は、画素において規定される、請求項１６に記載の方法。
【請求項１８】
前記逆方向参照は、２次元平面における距離に対する所定の距離符号を使用して規定される、請求項１６に記載の方法。
【請求項１９】
前記それぞれのコストの各々は、対応する動作に対する出力ビットの数を含む、請求項１６に記載の方法。
【請求項２０】
オフセットを用いて、前記入力画像において半透明の赤色、緑色、および青色値を有する画素のα値を調節することをさらに含む、請求項２に記載の方法。
【請求項２１】
前記α値を置換することは、結果として生じる予測誤差における新しいシンボルを低減させるために、前記入力画像におけるカラーの動的範囲をパックすることを含む、請求項２０に記載の方法。
【請求項２２】
エンコーダであって、前記エンコーダは、
プロセッサと、
前記プロセッサに連結されたメモリと、
エントロピー符号生成モジュールであって、前記エントロピー符号生成モジュールは、前記プロセッサによって実行されると、
入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
前記複数のエントロピー符号組への参照を備えている第１のサブ解像度画像を生成することであって、前記参照の各々は、前記入力画像内の対応する画素をエンコードするために使用される前記エントロピー符号組のうちの１つを示す、ことと
を前記プロセッサに行わせるように構成されている、エントロピー符号生成モジュールと、
画像保存モジュールであって、前記画像保存モジュールは、前記プロセッサによって実行されると、複数の圧縮パラメータの各々を制御するためにそれぞれのサブ解像度画像を使用して、前記入力画像をエンコードすることを前記プロセッサに行わせるように構成されている、画像保存モジュールと、
圧縮画像ファイル出力モジュールであって、前記圧縮画像ファイル出力モジュールは、前記プロセッサによって実行されると、圧縮されたエントロピー符号化画像ファイルとして、少なくとも前記エンコードされた入力画像および前記生成された第１のサブ解像度画像を出力することを前記プロセッサに行わせるように構成されている、圧縮画像ファイル出力モジュールと
を備えている、エンコーダ。
【請求項２３】
前記エントロピー符号生成モジュールは、前記プロセッサによって実行されると、
前記入力画像を複数のブロックに分割することと、
前記複数のブロックからのそれぞれのブロックに対するエントロピー統計を決定することと、
前記決定されたエントロピー統計の類似性に従って、前記複数のブロックをクラスタ化し、複数のブロッククラスタを形成することと、
前記ブロッククラスタのそれぞれに対するエントロピー符号を決定することと
を前記プロセッサに行わせるようにさらに構成されている、請求項２２に記載のエンコーダ。
【請求項２４】
前記圧縮画像ファイル出力モジュールは、前記プロセッサによって実行されると、第１のエンコーディング技法を使用して、前記エンコードされた入力画像、および、前記生成された第１のサブ解像度画像のエンコードされたバージョンを保存することを前記プロセッサに行わせるようにさらに構成されている、請求項２２に記載のエンコーダ
【請求項２５】
エンコードされた命令を有するコンピュータ読み取り可能な保存媒体を備えている製造品であって、前記命令は、コンピューティングデバイスによって実行されると、前記コンピューティングデバイスに、動作を行わせ、前記動作は、
前記入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
前記複数のエントロピー符号組への参照を備えている第１のサブ解像度画像を含む１つ以上のサブ解像度画像を生成することであって、前記参照の各々は、前記入力画像内の対応する画素をエンコードするために使用される前記エントロピー符号組のうちの１つを示す、ことと、
エントロピー符号を含む１つ以上の圧縮パラメータを制御するために前記生成された１つ以上のサブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、前記エンコードされた入力画像および前記生成された１つ以上のサブ解像度画像を出力することと
を含む、製造品。
【請求項２６】
エンコードされた入力画像を解凍する方法であって、前記方法は、
圧縮されたエントロピー符号化画像ファイルを分解し、前記エンコードされた入力画像と複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像とにアクセスすることと、
前記複数の圧縮パラメータの各々を制御するために前記それぞれのサブ解像度画像を使用して、前記エンコードされた入力画像をデコードすることと、
前記デコードされた入力画像を出力することと
を含む、方法。
【請求項２７】
デコーダであって、前記デコーダは、
プロセッサと、
前記プロセッサに連結されたメモリと、
画像ファイルデコンポーザであって、前記画像ファイルデコンポーザは、前記プロセッサによって実行されると、圧縮されたエントロピー符号化画像ファイルを分解し、エンコードされた圧縮入力画像と複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像とにアクセスすることを前記プロセッサに行わせるように構成されている、画像ファイルデコンポーザと、
入力画像デコーダであって、前記入力画像デコーダは、前記プロセッサによって実行されると、前記複数の圧縮パラメータの各々を制御するために前記それぞれのサブ解像度画像を使用して、前記エンコードされた入力画像をデコードすることを前記プロセッサに行わせるように構成されている、入力画像デコーダと
を備えている、デコーダ。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して、画像圧縮に関する。
【背景技術】
【０００２】
デジタルカメラ、カメラ装備携帯電話および携帯デバイス、ならびに他の便利な画像捕捉デバイスの普及は、多数の画像が、種々のウェブベースの画像アプリケーション上に定期的にアップロードされることにつながっている。このようなアプリケーションは、改善された効率、品質、および柔軟性を有する、画像圧縮技法の継続的必要性を強調している。
【０００３】
ポータブルネットワークグラフィック（ＰＮＧ）形式は、インターネット等のネットワーク上で画像を保存およびトランスポートするために頻繁に使用されている形式である。グラフィックスインターチェンジ形式（ＧＩＦ）、タグ画像ファイル形式（ＴＩＦＦ）、およびジョイントピクチャエキスパートグループ（ＪＰＥＧ）等の他の画像形式もまた、インターネット環境において頻繁に使用される。ＰＮＧおよびＧＩＦは、可逆圧縮方法と見なされる一方、ＪＰＥＧは、不可逆圧縮方法である。ＴＩＦＦは、時として、不可逆または可逆圧縮を使用し得る。これらの技法の各々は、画像圧縮において、多くの利点をもたらす。しかしながら、これらの技法の各々は、効率、品質、または柔軟性に脆弱性を有する。
【０００４】
したがって、広く採用および支持され得、現在利用可能な技法に勝る、改善された効率および品質をもたらす、画像圧縮技法が、所望される。
【発明の概要】
【課題を解決するための手段】
【０００５】
サブ解像度画像を使用する、画像圧縮および解凍のための方法、システム、および製造品が、開示される。画像圧縮のために、これらは、入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、複数のエントロピー符号組を備えている第１のサブ解像度画像を含む、１つ以上のサブ解像度画像を生成することと、エントロピー符号を含む１つ以上の圧縮パラメータを制御するために生成された１つ以上のサブ解像度画像を使用して、入力画像をエンコードすることと、圧縮されたエントロピー符号化画像ファイルとして、エンコードされた入力画像および生成された１つ以上のサブ解像度画像を出力することとを含む。
【０００６】
画像圧縮のための別の実施形態は、入力画像から、複数の圧縮パラメータのそれぞれに対して、それぞれのサブ解像度画像を生成することと、複数の圧縮パラメータの各々を制御するためにそれぞれのサブ解像度画像を使用して、入力画像をエンコードすることと、圧縮されたエントロピー符号化画像ファイルとして、エンコードされた入力画像および生成されたサブ解像度画像を出力することとを含む。
【０００７】
画像解凍のための実施形態は、画像ファイルを分解し、エンコードされた圧縮入力画像および複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像にアクセスすることと、複数の圧縮パラメータの各々を制御するためにそれぞれのサブ解像度画像を使用して、エンコードされた圧縮入力画像をデコードすることと、デコードされた入力画像を出力することとを含む。
【０００８】
さらなる特徴および利点ならびに種々の実施形態の構造および動作が、付随の図面を参照して、以下に詳細に説明される。本発明は、本明細書に説明される具体的実施形態に限定されないことに留意されたい。そのような実施形態は、例証的目的のためだけに本明細書に提示される。追加の実施形態は、本明細書に含まれる教示に基づいて、当業者に明白となるであろう。
【０００９】
その実施例が、付随の図に図示され得る、本発明の実施形態を参照する。これらの図は、限定ではなく、例証であることが意図される。本開示は、概して、これらの実施形態の文脈において説明されるが、これらの実施形態は、範囲に関して限定するものではないことを理解されたい。
【図面の簡単な説明】
【００１０】
【図１】図１は、ある実施形態による、画像圧縮およびエンコーディング技法を図示する、流れ図である。
【図２】図２は、ある実施形態による、図１の画像圧縮およびエンコーディング技法において使用される、事前処理技法を図示する、流れ図である。
【図３】図３は、ある実施形態による、図１の画像圧縮およびエンコーディング技法において使用される、空間的予測技法を図示する、流れ図である。
【図４】図４は、ある実施形態による、図１の画像圧縮およびエンコーディング技法において使用される、カラー変換技法を図示する、流れ図である。
【図５】図５は、ある実施形態による、図１の画像圧縮およびエンコーディング技法において使用される、初期画素ベースの圧縮技法を図示する、流れ図である。
【図６】図６は、ある実施形態による、図１の画像圧縮およびエンコーディング技法において使用される、エントロピー符号を決定するための技法を図示する、流れ図である。
【図７】図７は、ある実施形態による、図１の画像圧縮およびエンコーディング技法において使用される、一般的画像エンコーディング技法を図示する、流れ図である。
【図８】図８は、ある実施形態による、エンコーダのブロック図である。
【図９】図９は、ある実施形態による、図８のエンコーダに関連付けられ得るデータを図示する、ブロック図である。
【図１０】図１０は、ある実施形態による、圧縮された画像ファイル形式のブロック図である。
【図１１】図１１は、ある実施形態による、画像解凍およびデコーティング技法を図示する、流れ図である。
【図１２】図１２は、ある実施形態による、デコーダのブロック図である。
【図１３】図１３は、ある実施形態による、コンピュータシステムである。
【発明を実施するための形態】
【００１１】
特定の用途に対する例証的実施形態が、本開示において説明されるが、実施形態は、それらに限定されないことを理解されたい。他の実施形態も、可能であって、本明細書の教示の精神および範囲ならびに実施形態が有意な可用性があるであろうさらなる分野内において、修正を実施形態に行うことができる。さらに、特定の特徴、構造、または特性が、実施形態に関連して説明されるとき、明示的に説明されるかどうかにかかわらず、他の実施形態と関連して、そのような特徴、構造、または特性をもたらすことは、当業者の知識内であることが思量される。
【００１２】
本開示は、概して、画像の圧縮のための方法、システム、および製造品を対象とする。それらの具体的に本明細書に開示されるものを含む、実施形態は、可逆またはほぼ可逆画像圧縮を達成する一方、また、処理効率、画質、および保存において、実質的利点を達成する。現在一般的ＰＮＧ画像圧縮と実施形態との間のいくつかの差異は、例証である。
【００１３】
実施形態は、類似統計を有する入力画像の面積に対して、別個の組のエントロピー符号を生成する。それぞれの生成されたエントロピー符号は、サブ解像度画像（すなわち、より低い解像度を有する画像、したがって、入力画像より小さい画像）内に保存され、次いで、入力画像内の画素のエントロピーエンコーディングを制御するために使用される。そうすることによって、画像の２次元空間内で近接する、画素のエントロピー特性が、有利には、実施形態において利用される。ＰＮＧは、対照的に、線形メモリのブロックに対してエントロピーをエンコードする。すなわち、画像は、バイトストリームに変換され、次いで、エントロピー符号化される。入力画像内で２次元的に近接して存在するエントロピー特性は、線形バイトストリームが、エントロピー符号化されるため、ＰＮＧでは、効果的に利用されない。さらに、サブ解像度画像を使用して、異なる面積に対してエントロピー符号を規定することによって、実施形態は、デコーディングプロセスの間、エントロピー符号をより費用効果的に変更可能である。
【００１４】
空間的予測に関しても、画像内で２次元的に近接して生じる類似性は、各長方形ブロックに対して、空間的予測子を規定するために、実施形態において効果的に利用される。空間的予測子は、サブ解像度画像内に保存され、次いで、空間的予測を制御するために使用される。対照的に、ＰＮＧは、局所面積の統計的類似性の特定の配慮を伴わずに、入力画像の各行に対して、空間的予測子を規定する。
【００１５】
実施形態は、クロスカラー成分予測子を使用して、空間的予測誤差を予測することによって、異なるカラーチャネル間の相関を活用する。実施形態は、有利には、入力画像内の同一のカラーの成分間の相互関係を使用するために、別個のエントロピー符号を使用して、各カラーチャネルをエンコードする。ＰＮＧは、全カラーチャネルに対して、共通エントロピー符号を使用する。
【００１６】
ＰＮＧは、静的カラーパレットを定義するが、実施形態は、入力画像の面積に対して、局所的に定義されたカラーパレットを導入する。パレットは、ハッシュ法を使用して、動的に生成され、これは、カラー特性の改善につながり得る。
【００１７】
さらに、実施形態は、サブ解像度画像を使用して、画像圧縮およびエントロピーエンコーディングの種々の側面を制御する。サブ解像度画像は、入力画像を保存するために使用されるものと同一の技法を使用して保存され得る。
【００１８】
図１−７は、圧縮の方法の実施形態の種々の側面を図示する。図８−１０および１３は、実施形態による、システムを図示する。
【００１９】
図１は、ある実施形態による、画像圧縮およびエントロピーエンコーディングのための方法１００を図示する。本方法は、例えば、図８−１０および１３に関連して後述されるようなシステムを使用して、実装することができる。方法１００は、示される順序で生じなくてもよく、ステップの全部を要求しなくてもよい。
【００２０】
ステップ１０２では、事前処理が、入力画像に関して行われる。入力画像は、デジタル化された写真または他のデジタル画像であることができる。入力画像は、画素の論理的長方形アレイとして、メモリ内に表され得る。画素は、１バイト以上であり得る。ある実施形態によると、画素は、４バイトであり、赤色、緑色、青色、およびαチャネルを含む。事前処理ステップ１０２は、事前処理後、入力画像が、改善された圧縮をもたらすように、入力画像の画素を処理し得る。ある実施形態によると、α置換、カラー離散化、およびパレット選択が、ステップ１０２において行われ得る。事前処理ステップ１０２はさらに、図２に関連して以下に説明される。
【００２１】
ステップ１０４では、入力画像、またはより具体的には、事前処理された入力画像が、空間的予測を受ける。具体的には、当業者には公知のように、空間的予測は、１つ以上の以前に生じた画素に基づいて、画素を予測することを指す。予測された値と実際の値との間の差異は、空間的に予測された画像内の画素位置に記録される。さらに、選択された空間的予測子のサブ解像度画像が、保存される。
【００２２】
入力画像は、所定のサイズの長方形面積（「ブロック」）に分割することができる。ブロックは、例えば、１６×１６画素等の任意のサイズであり得る。同一のまたは異なるサイズのブロックが、空間的予測、カラー空間変換、およびエントロピー符号選択において使用され得る。
【００２３】
各ブロック内の各画素に対して、空間的予測子の組が、試みられる。試みられる空間的予測子の組は、事前に構成されることができる、または動的に決定されることができる。ある実施形態によると、空間的予測子の組は、個々の画素、あるいは現在の画素（用語「現在の画素」は、現在処理されている画素を指すために使用される）の左にある画素および／または現在の画素の上の１つ以上の行である画素の組み合わせを含む。現在の画素の左または上のいずれかにある画素は、画像内の画素の左右上下の処理順序に従って、現在の画素の前に処理されることに留意されたい。
【００２４】
ブロックに対して選択された空間的予測子は、ブロック内の画素の空間的に予測された値とそれぞれの実際の値との間の差異における最小合計エントロピーをもたらす、空間的予測子であり得る。したがって、実施形態では、空間的予測子は、各ブロックに対して、エントロピーを局所的に最適化する様式で決定される。
【００２５】
いくつかの実施形態では、現在のブロックに対する空間的予測子を選択する際に考慮される基準は、空間的に予測された値と実際の値との間の差異の絶対値を最小限にすることと、予測子として、および／または予測子の一部として、所定の近傍画素に有利に働くバイアスとを含む。差異の絶対値の最小限化は、画像全体を通して、エントロピーを全体的に低減させ得る。ある実施形態によると、絶対値の最小限化は、ブロック内の各画素に対する差異の絶対値を最小限化すること、またはブロックに対する差異の合計絶対値を最小限化することに基づき得る。別の実施形態によると、絶対値の最小限化は、少なくとも部分的に、差異値の集団数の加重和を最小限にすることによって達成され得る。重み付けは、例えば、大きい絶対値より小さい絶対値に有利に働くような指数関数的またはガウス的であり得る。
【００２６】
各ブロックに対して選択された空間的予測子は、次いで、空間的予測子サブ解像度画像内に記録される。空間的予測のさらなる詳細は、図３に関連して以下に説明される。
【００２７】
ステップ１０６では、入力画像のカラー空間変換が、行われる。入力画像のカラー空間変換は、空間的予測前または後に行うことができる。説明される実施形態では、カラー空間変換への入力は、画素値として、空間的予測差異を含む、中間入力画像である。
【００２８】
カラー空間変換は、カラー成分間の相関を識別および記録するステップを含む。例えば、緑色と赤色、緑色と青色、および赤色と青色との間の相関が、カラー相関係数として、識別および記録される。したがって、緑色、赤色、および青色に対する３つの別個のカラー値を元々含んでいた画素は、カラー変換後、緑色に対する元々のカラー値と、赤色および青色に対する相関係数を使用して決定された値とによって表され得る。赤色は、赤色を緑色に関連させる相関係数として表され得、青色は、青色を赤色に関連させる相関係数または青色を緑色に関連させる相関係数のうちの１つ以上として表され得る。
【００２９】
相関係数は、サブ解像度画像内に保存される。入力画像内のカラー値は、それぞれの相関係数に基づいて、赤色および青色に対する予測誤差を含むように変更される。カラー空間変換はさらに、図４に関連して以下に説明される。
【００３０】
ステップ１０８では、入力画像の初期画素ベースの圧縮が、行われる。本明細書に説明される実施形態では、初期画素ベースの圧縮への入力は、空間的予測およびカラー変換処理を既に受けた入力画像である。しかしながら、ステップ１０８は、方法１００の流れ内の他の位置で行われ得、したがって、他の実施形態では、ステップ１０４および１０６の事前または事後の入力画像を有し得る。
【００３１】
各画素に対して、初期画素ベースの圧縮は、逆方向参照、画素、またはパレット参照のうちの１つを挿入するように動作する。当業者は、逆方向参照を挿入することによる圧縮が、バイトに基づく従来のＬＺ７７において行われることを認識するであろう。ＬＺ７７とは対照的に、実施形態では、逆方向参照の挿入は、画素に基づく。画素ベースの圧縮は、画像内の２次元近接特性を有効に利用し、圧縮を改善する。ある実施形態によると、パレット（本明細書では、「新生カラーパレット」と称される）は、画素ベースの圧縮の間に動的に取り込まれ得る。入力画像の初期画素ベースの圧縮はさらに、図５に関連して以下に説明される。
【００３２】
ステップ１１０では、ステップ１０８から出力される、圧縮された入力画像は、２次元局所性変換を受ける。２次元局所性変換は、圧縮された画像内の位置情報を識別し、対応する２次元距離を表す符号によって、その位置情報をエンコードするように動作する。例えば、逆方向参照は、圧縮（例えば、ステップ１０８）の間、画素距離として元々挿入され得る。２次元局所性変換は、その画素距離を対応する２次元距離に対する短符号と置換し得る。事前に構成された２次元局所性符号表は、それぞれの短符号と選択された対応する相対的画素距離との間の関係を規定する。ある実施形態によると、事前に構成された表は、現在の画素の周囲近傍の１６×８画素に対して、短符号を規定する。これらの短符号は、現在の画素までのそのユークリッド距離によって配列される。すぐ近傍の面積に対する短符号の使用は、例えば、すぐ上の１つ以上前の行からの画素へのより安価な（ビットの観点から）参照を可能にする。
【００３３】
ステップ１１２では、エントロピー符号が、決定され、エントロピー符号に対するサブ解像度画像が、記録される。エントロピー符号は、類似統計を有する画像の局所面積（例えば、ブロックまたはブロックのクラスタ）に対して決定される。エントロピー符号または各画素をエンコードするために使用されるエントロピー符号への参照は、エントロピーサブ解像度画像と称されるサブ解像度画像内に保存される。エントロピー符号決定はさらに、図６に関連して以下に説明される。
【００３４】
ステップ１１４では、入力画像は、エントロピー符号化される。ある実施形態による、エントロピー符号化に対する入力は、空間的予測、カラー変換、画素圧縮、および２次元局所性変換を受けた入力画像であり得る。
【００３５】
エントロピー符号化は、左右上下様式で画素毎に、入力画像に動作する。画像の各場所において、エントロピーエンコーディングが、エントロピーサブ解像度画像内で参照されるエントロピー符号に基づいて決定される。図６に関連して以下に説明されるように、エントロピー符号組は、入力画像の各ブロックに対して決定される。エントロピー符号組は、カラー、距離等に対するそれぞれのエントロピー符号を含み得る。エントロピーサブ解像度画像は、入力画像内の対応する画素のために使用されるべきエントロピー符号組を規定し得る。エントロピー符号は、現在の画素のブロックに基づいてアクセスされる。エントロピー符号は、例えば、ハフマン符号および算術符号に基づき得る。
【００３６】
ステップ１１６では、エントロピー符号化圧縮された画像は、メモリ、永続性メモリに出力される、または別のエンティティに伝送される。エントロピー符号化画像を出力することは、圧縮されたエントロピー符号化入力画像、サブ解像度画像、および入力画像を復元するように解凍するために必要とされる他の情報を含む圧縮されたエントロピー符号化画像ファイル（図１０に関連して説明されるもの等）を形成することを含むことができる。
【００３７】
図２は、入力画像を事前処理する方法２００の流れ図を図示する。ある実施形態によると、方法２００は、前述の方法１００のステップ１０２を行う際に使用することができる。方法２００は、示される順序で生じなくてもよく、ステップの全部を要求しなくてもよい。
【００３８】
ステップ２０２では、α置換が、入力画像に関して行われる。α置換は、入力画像内のエントロピーを低減させるための技法である。α置換は、一意のものまたは画像内で稀に生じるものであるα値等、α値のいくつかをより一般に画像内に現れるα値と置換するように動作する。ある実施形態によると、例えば、また、ＰＮＧ、ＴＩＦＦ、およびＧＩＦ等の画像形式に表されるもの等、半透明値を有する特殊カラー値は、対応する具体的半透明性値を含むように補正することによって、元々含まれる半透明性値を除去するように処理される。このプロセスは、αチャネルにおけるエントロピーを低減するように動作する。
【００３９】
任意の数の画素が、半透明としてマークされ、それによって、α置換を受けることができる。ある実施形態によると、半透明性は、赤色、緑色、および青色に対する別個のカラー値として規定されず、代わりに、対応するα値に対するオフセットとして規定される。αに対するオフセットを使用して、半透明赤色、緑色、および青色を規定することは、実施形態が、特定のＲＧＢトリプレットに対して複数のαが存在するときでも、半透明性情報を保存することを可能にする。オフセットを使用して、α値を規定する副次的効果として、αチャネルのエントロピーが、低減され得る。
【００４０】
ステップ２０４では、カラー離散化が、行われ得る。ある実施形態によると、カラー離散化およびコンパクト化は、予測が、元々の画像内にあるそれらのようなカラー値および／または予測誤差値のみ、あるいはその大部分をもたらすであろうように、カラーの動的範囲をパックするように動作する。これは、予測画像が、元々の画像より多くの一意のシンボルを有する必要性を回避または低減する。
【００４１】
例えば、カラー離散化およびコンパクト化がない実施形態では、予測子は、２つのカラー値を検討し、画素に対して予測されたカラーとして、それらの２つの検討された値の平均を予測し得る。しかしながら、平均値は、元々の画像内のいずれかの場所にあったカラーではない場合があり、したがって、予測された信号は、新しいシンボルを導入しているであろう。予測および／または予測誤差が、元々の画像内に未だない新しい値をもたらす可能性が、新しいシンボルの追加の最小限化につながるように、カラーの動的範囲をパックする。その結果、予測された画像は、従来の技法と比較して、エントロピーを低減し得る。
【００４２】
ステップ２０６では、随意に、パレット選択が、行われる。ある実施形態によると、パレット選択は、数カラーのみが、画像においてエンコードされるために要求される場合に行われる。パレット選択は、複数の画素が、単一画素内にパックされることを可能にする。
【００４３】
図３は、空間的予測を行うための方法３００を図示する。ある実施形態によると、方法３００は、前述の方法１００のステップ１０４を行う際に使用されることができる。方法３００は、示される順序で生じなくてもよく、ステップの全部を要求しなくてもよい。
【００４４】
ステップ３０２では、空間的予測子が、決定される。ステップ１０４に関して前述のように、開示される実施形態は、ブロック内の予測差異が最小限化されるような空間的予測子を見つけるように動作する。別の実施形態では、限定されないが、ブロック内の空間的予測差異のエントロピーを最小限化すること、空間的予測差異の絶対値を最小限化すること、および近傍画素ブロックに有利に選択基準をバイアスすること等の他の基準が、ブロックの局所的特性に対して、および随意に、全体的特性に対して、空間的予測子の選択を最適化するために使用され得る。
【００４５】
前述のように、現在の画素を予測するために選択される画素は、以前に処理された画素位置のいずれかに由来し得る。ある実施形態によると、事前に構成された空間的予測子符号表が、複数の画素位置および画素組み合わせの各々に対する符号を規定する。例えば、空間的予測子符号表は、無予測のための符号、個々の画素を複製するための複数の符号、および２つ以上の画素を平均化するための複数の符号を含み得る。したがって、現在の画素の予測は、１つ以上の画素に基づき得る。
【００４６】
それによって入力画像をエンコードする空間的予測子は、前述の基準のうちの１つ以上によって決定されたコスト関数に基づいて、ブロック毎ベースで選択される。あるブロックでは、全画素が、同一の選択された空間的予測子に関連付けられる。
【００４７】
ステップ３０４では、各ブロックに対して選択された空間的予測子は、空間的予測子サブ解像度画像内に保存される。サブ解像度画像内の画素は、入力画像内のブロックを表す。
【００４８】
圧縮されたエントロピー符号化入力画像を保存するために使用される同一の保存技法は、それぞれのサブ解像度画像を保存するために使用することができる。サブ解像度画像のためを含む、圧縮されたエントロピー符号化画像を保存するための一般的技法は、図７に関連して以下に開示される。
【００４９】
ステップ３０６では、入力画像（事前処理の有無にかかわらず）は、空間的予測子サブ解像度画像に従って、空間的予測をエンコードするために処理される。ブロック内の各画素に対して、予測された値は、空間的予測子サブ解像度画像内に保存された対応する空間的予測子に基づいて決定される。予測された値と実際の値との間の差異が、次いで、画素中にエンコードされる。空間的予測が、入力画像にわたり画素を処理することを進める場合、空間的予測子サブ解像度画像が、各ブロックに対して適用される空間的予測子を制御する。
【００５０】
図４は、ある画像のカラー空間変換のための方法４００を図示する。ある実施形態によると、方法４００は、前述の方法１００のステップ１０６を行う際に使用することができる。方法４００は、示される順序で生じなくてもよく、ステップの全部を要求しなくてもよい。
【００５１】
ステップ４０２では、カラー相関が、決定される。カラー成分間のカラー相関子は、ブロックベースで決定される。各ブロックに対して、画素、すなわち、より具体的には、赤色、緑色、青色（ＲＧＢ）値が分析され、それらの間の相関を決定する。ある実施形態によると、緑色と赤色、赤色と青色、および緑色と青色との間の相関が、決定される。カラー相関子は、赤色チャネルおよび青色チャネルにおけるエントロピーを低減させるように動作する。例えば、その画素内の緑色値の係数として赤色を表すことによって、実施形態は、赤色チャネルにおけるエントロピーを低減させる。例えば、従来のシステムにおいてエンコードされる、それぞれ、ＲＧＢ８：６：２および４：３：０を有する、２つのブロックを検討する。ある実施形態によると、この情報は、８：Ｘ：Ｙおよび４：Ｘ：Ｙとしてエンコードすることができ、ＸおよびＹは、７５％および２５％に対する符号である。したがって、カラー変換は、隣接するブロック間のカラー関係を利用することによって、赤色チャネルおよび青色チャネルのエントロピーを低減させ得る。
【００５２】
カラー相関子の共通組が、各ブロックに対して決定される。ブロックに対する相関子は、例えば、平均に基づいて、または現在のブロック内で最も頻繁に生じるカラー値に基づいて、選択され得る。ある実施形態によると、ブロックに対する相関子は、赤色および青色成分のエントロピーおよび絶対値を組み合わせる、ヒューリスティックを最小限にする様式で決定され得る。例えば、ブロック内の緑色と赤色の全値を試験することができ、最低ヒューリスティックをもたらすものを選択することができる。また、ブロック内の緑色と青色および赤色と青色の全組み合わせを試験することができ、最低ヒューリスティックを伴う組み合わせを選択することができる。さらに、いくつかの実施形態では、現在のブロックの上または左にあるブロックから選択された相関子に類似する相関子値が、若干、選択に有利に働き得る。
【００５３】
ステップ４０４では、選択された相関係数は、カラー相関サブ解像度画像内に保存される。カラー相関サブ解像度画像では、各画素は、入力画像内のブロックを表す。サブ解像度画像内の各画素は、それぞれ、緑色と赤色、緑色と青色、および赤色と青色の相関係数を保存する。これらの係数は、正または負の相関が示され得るような様式で保存され得る。
【００５４】
ステップ４０６では、カラー変換が、入力画像においてエンコードされる。入力画像内の赤色チャネルおよび青色チャネルは、ここで、カラー相関予測の予測誤差を表すように修正される。具体的には、カラー予測は、以下に説明されるようにエンコードされる。緑色は、予測されず、したがって、保存される値は、実際の緑色値である。赤色は、カラー相関サブ解像度画像内で規定された現在のブロックに対応する緑色と、赤色の相関係数に基づいて、緑色から予測される。カラー相関係数に基づく赤色予測値と赤色成分に対して以前にエンコードされた空間的予測誤差との間の差異が、ここで、エンコードされる。青色は、緑色および赤色のうちの１つ以上から予測され得る。緑色および赤色が両方とも、青色値を予測する際に使用される場合、ある実施形態によると、緑色と青色および赤色と青色予測の平均が、青色成分に対して予測された値として見なされる。青色が予測されるモードは、事前に構成され得る。したがって、赤色チャネルおよび青色チャネルのエンコーディングは、カラー相関サブ解像度画像内で規定される相関係数に従って制御される。
【００５５】
図５は、入力画像の画素ベースの圧縮のための方法５００を図示する。ある実施形態によると、方法５００は、方法１００のステップ１０８を行う際に使用することができる。ステップ５０２−５１６は、左右上下移動パターンにおいて、画素をトラバースすることによる画像の処理を図示する。方法５００は、示される順序で生じなくてもよく、ステップの全部を要求しなくてもよい。
【００５６】
ステップ５０２では、処理されることになる次の画素が、選択される。処理は、典型的には、左上画素から開始するであろう。他の反復では、後続画素が、選択される。選択された次の画素は、現在の画素と称される。
【００５７】
ステップ５０４−５０８は、入力画像を圧縮するプロセスにおいて、現在の画素に行われ得る、各動作のコストを決定する。ある実施形態によると、３つの別個の選択肢が、検討され得る。すなわち、１）逆方向参照の挿入、２）画素の挿入、および３）パレットエントリの挿入である。
【００５８】
「逆方向参照」は、規定された１つ以上の画素が、画像を圧縮するために、現在の画素の場所で複製され得ることを示す。例えば、現在の画素が、全てカラーＣである、３画素のストリングの開始であり、現在の画素の２００画素前の以前に処理された場所に、３つのカラーＣ画素のストリングがあった場合、実施形態は、現在の画素に一致する２００画素前への参照と、参照される画素から開始する３画素のストリングの長さとを示す逆方向参照を挿入することができる。逆方向参照は、距離および長さ値によって規定される。距離は、現在の画素から参照される画素までの距離を指し、長さは、参照される画素が複製され得る現在の画素からの画素の数を指す。
【００５９】
画素の挿入は、圧縮される画像内に現在の画素を挿入することを指す。いくつかの状況では、これは、画素に対する最もコスト効率的動作であり得る。
【００６０】
パレットエントリを挿入することは、圧縮される画像内にインデックスを挿入することを指す。いくつかの実施形態では、パレットエントリを挿入することは、パレット内に対応するカラーエントリを挿入することも含むことができる。新生カラーパレットが、画素ベースの圧縮が、画像を通して進むにつれて、動的に構築される。各画素場所において、新生パレット内にカラー値を挿入し、圧縮される画像内に対応するパレットインデックスを挿入するコストが、検討される。新生パレットのサイズは、事前に構成され得る。ある実施形態によると、赤色／緑色／青色／α値を表す、３２ビット整数が、所定の乗数によって乗算される。サイズに基づいて、結果として生じる整数からの数ビットが、新生カラーパレットを表す、アレイへのインデックスとして使用される。例えば、１２８の新生パレットサイズに対して、７ビットをインデックス値として使用することができる。圧縮されていない画素ストリームからの各カラー値に対して、インデックスが、いくつかの方法のうちの１つにおいて決定され得る。ある実施形態によると、カラーのインデックスは、前述のカラーのバイト表現の所定の開始位置から７つの隣接する連続ビットに基づいて、決定される。別の実施形態によると、モジュロ演算が、カラー値に関して行われ、新生パレットへのハッシュインデックスを決定し得る。ある実施形態によると、ある新生カラーパレットは、入力画像のために使用することができる。他の実施形態では、別個の新生パレットは、それぞれの面積のために定義され得る。例えば、新しい新生パレットは、入力画像のｘ−軸に沿って、３２画素毎に作成され得る。
【００６１】
ステップ５０４では、現在の画素に逆方向参照を挿入するコストが、決定される。前述のように、逆方向参照の挿入は、画素までの距離および長さの挿入を含む。長さは、参照される画素から開始して、複製され得る画素の数を指す。コストは、現在の画素に対応する、圧縮された画像内の位置における距離および長さを挿入するコストを含む。ビットを挿入するコストは、現在の画素の場所から開始して複製され得る、逆方向参照からの画素の数に等しい画素の数を複製する必要はないという、コスト削減と組み合わせて検討される。例えば、逆方向参照が、エンコードに５バイトかかり、３画素の長さが示される場合、サイズ１バイトの画素の例では、逆方向参照挿入のコストは、５−３＝２バイトとなるであろう。別の実施形態によると、逆方向参照のコストは、挿入コストにのみ基づく、すなわち、逆方向参照が、エンコードに５バイトかかる場合、挿入コストは、５バイトである。
【００６２】
ある実施形態によると、最長逆方向参照が、選択される。別の実施形態によると、可能性として、異なる距離および長さ特性を有する２つ以上の逆方向参照が、比較され、最もコスト効率的なものが、選択される。
【００６３】
ステップ５０６では、入力画像内に画素を挿入するコストが、決定される。本コストは、１画素を挿入するビットコストとして考えることができる。
【００６４】
ステップ５０８では、新生パレットインデックスを挿入するコストが、決定される。新生パレットエントリを挿入するコストは、インデックスエントリのサイズとして考えることができる。
【００６５】
ステップ５１０では、ステップ５０４−５０８におけるコスト決定に基づいて、最小コスト動作が、決定され、最小コスト動作は、現在の画素場所に記録される。コストは、ビットコストに基づいて決定される。
【００６６】
ステップ５１２では、入力画像の最後の画素に到達したかどうか決定される。該当しない場合、ステップ５０２−５１２は、トラバースパターンにおいて、次の画素に対して繰り返される。
【００６７】
ステップ５１２において、現在の画素が最後の画素であると決定される場合、処理は、ステップ５１４に進む。ステップ５１４では、最後の画素からの経路は、画像を圧縮するための最小コスト経路の逆を決定するように逆トレースされる。
【００６８】
ステップ５１４では、決定された経路は、次いで、画像に対する圧縮のための最小コスト経路をトラバースするために行われるべき圧縮動作をもたらすように反転される。経路は、画素場所における逆方向参照のエンコーディング、画素値のエンコーディング、およびパレットインデックス値のエンコーディングのうちの１つ以上を含み得る。ステップ５１４の終了時、入力画像は、画素ベースの圧縮を完了する。
【００６９】
図６は、エントロピー符号を決定する方法６００を図示する。ある実施形態によると、方法６００は、前述の方法１００のステップ１１２を行う際に使用することができる。方法６００は、示される順序で生じなくてもよく、ステップの全部を要求しなくてもよい。
【００７０】
ステップ６０２では、画像が、エントロピー符号化されるために受信される。ある実施形態によると、受信された画像は、画素ベースの圧縮プロセスを受ける。画素ベースの圧縮に先立って、入力画像は、空間的予測およびカラー空間変換を受けている場合がある。しかしながら、方法６００は、他のタイプの入力画像にも適用可能である。
【００７１】
ステップ６０４では、ブロックが、入力画像から決定される。ある実施形態によると、サイズ１６×１６のブロックが、決定される。他のブロックサイズも、可能である。
【００７２】
ステップ６０６では、統計が、それぞれのブロックに対して決定される。統計は、赤色、緑色、青色、αカラー成分に対して、距離符号、逆方向参照長さ符号に対して、およびパレットハッシュ値に対して、別個に決定され得る。統計は、各統計に対する画素の数がカウントされ得る、ヒストグラム形態で決定され得る。
【００７３】
ステップ６０８では、ブロックは、それぞれのブロックの統計の類似性に従って、クラスタ化される。ある実施形態によると、確率論的クラスタ化が、行われる。確率論的クラスタ化は、最初に、クラスタとして、各ブロックを検討し、次いで、ランダムにクラスタを反復的に選択することによって、行われ得る。次いで、最類似クラスタが、選択された数のクラスタから見つけられ、選択されたクラスタおよび見つけられたクラスタが、組み合わせられる。本クラスタ化動作は、クラスタの数が、決定された閾値クラスタ数まで低減されるまで行うことができる。閾値クラスタ数も、コスト関数に基づいて、決定することができる。例えば、各クラスタに対して、エントロピー符号を保存するためのコストをモデル化することができ、それぞれのエントロピー符号のサイズは、クラスタに対するブロックの分布に依存する。ある実施形態では、例えば、確率論的アルゴリズムは、クラスタの数を約１０００から約５０クラスタに低減させるように動作する。
【００７４】
ステップ６１０では、クラスタ化が、精緻化される。このステップは、ブロックとそのクラスタとの間の一致の正確度を改善するために、ブロック（または、ブロック統計）をクラスタに移動することによって、確率的に決定されたクラスタを精緻化するように動作する。ｋ平均アルゴリズム等のクラスタ化アルゴリズムをこのステップで使用することができる。別の実施形態によると、各ブロックは、それに対する最適クラスタを決定するように分析され、出力（保存）するための予期されるビット数が最小限化されるように、そこに移動される。各移動後、統計は、移動を補償するために調節される。この動作は、所定の回数の間、または出力するための予期されるビット数が、全ブロックに対して減少し続け、精緻化されたクラスタ化をもたらすまで、繰り返され得る。
【００７５】
ステップ６１２では、エントロピー符号が、各クラスタに対して決定される。したがって、クラスタは、類似特性を伴うブロックを一緒に群化するので、結果として生じるエントロピー符号は、各それぞれのクラスタの特性に対して特定的に決定される。さらに、各クラスタ内では、別個のエントロピー符号が、緑色、赤色、青色、α、および距離成分に対して決定される。実施形態では、同一のエントロピー符号を緑色、パレットインデックス、および長さ成分に対して使用することができる。限定されないが、各クラスタならびに各クラスタ内のカラーおよび距離成分の各々に特定的であるハフマン符号等、任意の技法を使用して、エントロピー符号を決定することができる。
【００７６】
ステップ６１４では、各ブロックに対するエントロピー符号が、決定される。特に、エントロピー符号の組（「エントロピー符号組」）は、赤色、緑色、青色、αカラー成分に対して、距離符号、逆方向参照長符号に対して、およびパレットハッシュ値に対して、別個のエントロピー符号を備えている。これは、特定のブロックが属するクラスタを識別することによって決定することができる。
【００７７】
ステップ６１６では、エントロピー符号組が、保存され、各画素に適用されるエントロピー符号は、エントロピー符号サブ解像度画像内に規定される。エントロピー符号サブ解像度画像は、入力画像内の、例えば、各１６×１６ブロックに対して、１画素を保存する。エントロピー符号サブ解像度画像内の各画素は、入力画像内の対応するブロックに適用されるべきエントロピー符号の組を規定する。例えば、サブ解像度画像内の画素の緑色成分は、保存されるエントロピー符号組内のエントロピー符号の対応する組の位置への参照とともにアップデートされ得る。エントロピー符号の組は、５つの別個のエントロピー符号を含むことができる。すなわち、緑色／画素インデックス／逆方向参照長に対するエントロピー符号と、赤色、青色、α、および距離成分に対するエントロピー符号とである。これらのエントロピー符号の各々は、ハフマン符号化およびランレングス符号化を使用して、別個に体系化され得る。
【００７８】
エントロピー符号サブ解像度画像は、他のサブ解像度画像および圧縮されたエントロピー符号化入力画像を保存する際に使用される同一の技法を使用して、保存することができる。画像の保存は、図７に関連して以下に説明される。
【００７９】
図７は、圧縮およびエントロピー符号化形態において、画像を保存する方法７００を図示する。ある実施形態によると、方法７００は、圧縮されたエントロピー符号化入力画像ならびにサブ解像度画像（例えば、エントロピーサブ解像度画像、カラー相関サブ解像度画像、および空間的予測子サブ解像度画像）を保存するために使用することができる。方法７００は、示される順序で生じなくてもよく、ステップの全部を要求しなくてもよい。
【００８０】
ステップ７０２では、入力画像は、画素ベースの圧縮を受ける。例示的画素ベースの圧縮は、ＬＺ７７の側面に類似するが、バイトの代わりに、画素に適用される。図５は、例示的画素ベースの圧縮方法を図示する。画素ベースの圧縮の出力は、画素、逆方向参照、およびパレットインデックス値を有する、画素ストリームである。
【００８１】
ステップ７０４では、画素ベースの圧縮からの出力は、２次元局所性変換を受ける。２次元局所性変換は、２次元近接性に基づいて、画素距離である距離を符号に変換する。例示的２次元変換は、前述の方法１００のステップ１１０に関連して前述されている。
【００８２】
ステップ７０６では、入力画像は、ブロック（例えば、１６×１６画素）に分割され、統計が、各ブロックに対して決定される。統計は、赤色、緑色、青色、α、および距離成分に対して、別個に収集され得る。統計はまた、（逆方向参照の）長さおよび画素インデックス値に対して、収集され得る。ある実施形態によると、緑色／長さ／画素インデックス値に対する統計は、組み合わせられ得る。ブロックに対する統計の決定は、方法６００のステップ６０４−６０６に関連して前述されている。
【００８３】
ステップ７０８では、ブロックは、統計の類似性に従ってクラスタ化され、ステップ７１０では、クラスタは、精緻化され、ブロックとそれぞれのクラスタとの間の一致を改善する。ステップ７１２では、エントロピー符号が、クラスタに対して決定される。ブロックのクラスタ化、クラスタの精緻化、およびそれぞれのクラスタに対するエントロピー符号の決定は、それぞれ、方法６００のステップ６０８、６１０、および６１２に関連して説明されている。
【００８４】
ステップ７１４では、エントロピーサブ解像度画像が、保存される。エントロピーサブ解像度画像の保存は、方法７００に定義されるものと同一の保存技法を使用し得る。したがって、方法７００は、画像の再帰的保存を定義する。エントロピー符号サブ解像度画像の保存は、方法６００のステップ６１６に関連して前述されている。
【００８５】
ステップ７１６では、入力画像は、エントロピーエンコードされる。入力画像のエントロピーエンコーディングは、方法１００のステップ１１４に関連して前述されている。
【００８６】
図８は、ある実施形態による、エンコーダ８００を図示する。エンコーダ８００は、事前処理モジュール８０２、空間的予測子８０４、カラー空間コンバータ８０６、画素コンプレッサ８０８、２次元局所性変換モジュール８１０、エントロピー符号生成モジュール８１４、画像保存モジュール８１２、および圧縮画像ファイル出力モジュール８１６を備えている。
【００８７】
事前処理モジュール８０２は、より良好に圧縮され得るように、画像を事前処理するように構成される。事前処理モジュール８０２は、例えば、画像が圧縮される前に、画像内のエントロピーを低減させるように動作することができる。事前処理モジュール８０２は、α置換マッパ８２２、カラー離散化器８２４、およびパレットセレクタ８２６を含む。
【００８８】
α置換マッパ８２２は、選択されたα値を除去または置換するように構成される。ある実施形態によると、α置換モジュールは、方法２００のステップ２０２を実装することができる。
【００８９】
カラー離散化器８２４は、予測子の値の動的範囲を調節することによって、元々の画像内にない予測された値を排除または低減させることにより、結果として生じるエントロピーを低減させるように構成される。ある実施形態によると、カラー離散化器８２４は、方法２００のステップ２０４を実装することができる。
【００９０】
パレットセレクタ８２６は、データ構造内に複数のカラーをより近接してパックすることによって、画像が、所定の数のカラー未満のみ有するとき、隣接する画素間の結合分布のエントロピーを低減させるように構成される。ある実施形態によると、パレットセレクタ８２６は、方法２００のステップ２０６を実装することができる。
【００９１】
空間的予測子８０４は、空間的予測を実装するように構成される。空間的予測は、例えば、方法１００のステップ１０４および方法３００に関連して説明される。
【００９２】
カラー空間変換器８０６は、カラー空間変換を実装するように構成される。カラー空間変換は、例えば、方法１００のステップ１０６および方法４００に関連して前述されている。前述の実施形態は、ＲＧＢカラーモデルに関して説明されている。限定されないが、ＹＵＶカラーモデル等の他のカラーモデルも、使用することができる。
【００９３】
画素コンプレッサ８０８は、入力画像の画素ベースの圧縮を行うように構成される。ある実施形態によると、画素コンプレッサ８０８は、方法７００のステップ７０２に関連して説明されるように、画素ベースの圧縮を実装するように構成される。画素コンプレッサ８０８は、逆方向参照挿入モジュール８３２、最長マッチを行うコンプレッサモジュール８３４、最小コストコンプレッサモジュール８３６、およびパレット挿入モジュール８３８を含む。
【００９４】
逆方向参照モジュール８３２は、現在の画素が、以前に生じた画素を参照することによって圧縮され得るかどうかを決定し、該当する場合、参照される画素までの画素距離および長さを挿入するように動作する。逆方向参照の挿入は、図５のステップ５０４に関連して前述されている。
【００９５】
パレット挿入モジュール８３８は、各画素に対するインデックス値を決定するように動作し、その間にも、それぞれの画素を処理するにつれて、新生カラーパレットを動的に構築する。対応する画素に対するパレットエントリへのインデックス参照を決定後、パレット挿入モジュール８３８は、逆方向参照のコストおよび画素挿入のコストに対するコスト比較が、好ましい場合、そのインデックスを圧縮された画像内に挿入し得る。
【００９６】
新生パレットの生成は、パレット挿入モジュール８３８が、圧縮プロセスの間、各画素を処理するために読み出されるにつれて進む。各画素は、カラー値（例えば、ＲＧＢまたはＲＧＢＡ）を含み得る。カラー値は、対応する空間的予測および／またはカラー変換予測内の誤差を表し得る。ハッシュインデックスは、現在の画素の値から生成される。ある実施形態によると、所定の数のビットが、画素の所定のビット位置から選択される。選択されたビットは、ハッシュインデックスとして使用される。画素（例えば、カラー値）は、次いで、ハッシュインデックスに基づいて、表内に挿入される。各カラーに対するハッシュ位置を決定する他の方法も、可能であって、本開示の範囲内で想定される。
【００９７】
最小コストコンプレッサ８３６は、入力画像に対する最小コスト圧縮を決定するように構成される。最小コストコンプレッサ８３６は、入力画像の各画素において、ａ）逆方向参照の挿入、ｂ）現在の画素の挿入、およびｃ）パレットエントリへのインデックスの挿入のうちの１つ以上の選択肢間で選択を行う。選択は、コスト分析に基づく。図５は、入力画像を圧縮するために、最小コストコンプレッサ８３６によって実装されることができる、方法５００を説明する。
【００９８】
最長マッチを行うコンプレッサモジュール８３４は、最長逆方向参照、画素の複製、およびパレットインデックスの挿入間の選択によって、入力画像を圧縮するように動作する。逆方向参照の挿入、画素の複製、およびパレットエントリの挿入の動作は、それぞれ、方法５００のステップ５０４、５０６、および５０８に関連して前述されている。最長マッチを行うコンプレッサモジュール８３４は、速度が圧縮のレベルより重要であるときに使用される、より高速圧縮技法として動作し得る。したがって、逆方向参照を検討するとき、例えば、最長マッチを行うコンプレッサモジュール８３４は、画素挿入およびパレットインデックス挿入に対するコスト比較の最長整合シーケンスを伴う、逆方向ストリングのみ、検討し得る。
【００９９】
２次元変換モジュール８１０は、２次元距離に基づいて、より短い符号を伴う画素距離の発生を置換するように構成される。ある実施形態によると、２次元変換モジュール８１０は、方法１００のステップ１１０に関連して前述の処理を実装し得る。
【０１００】
エントロピー符号生成モジュール８１４は、類似統計を有する入力画像のそれぞれの面積に対して、エントロピー符号を生成するように構成される。ある実施形態によると、ブロッククラスタモジュール８４２は、入力画像に対して、所定のサイズのブロックを決定し、次いで、統計の類似性に従って、ブロックをクラスタ化する。エントロピー符号生成モジュール８１４は、各クラスタに対して、別個のエントロピー符号を生成し、そのクラスタの特性に対して、符号を最適化することができる。エントロピー符号の組が、各クラスタに対して生成され得る。エントロピー符号生成モジュール８１４はさらに、エントロピーサブ解像度画像を生成し、入力画像の各ブロックに対して、エントロピー符号を保存するように構成される。ブロッククラスタモジュール８４２は、方法６００のステップ６０４−６１０および／または方法７００のステップ７０６−７１０に関連して前述の処理を実装し得る。エントロピー符号生成モジュール８１４は、方法６００のステップ６１２−６１６および／または方法７００のステップ７１２−７１６に関連して前述の処理を実装し得る。
【０１０１】
画像保存モジュール８１２は、圧縮されたエントロピー符号化入力画像および入力画像に基づいて生成されたサブ解像度画像のそれぞれを保存するように構成される。ある実施形態によると、画像保存モジュール８１２は、方法７００に関連して前述の処理を実装し得る。前述のように、方法７００は、再帰的定義を使用して、画像を保存する。例えば、ステップ７１４は、同一の方法７００を使用して、エントロピー符号サブ解像度画像の保存を要求する。
【０１０２】
圧縮画像ファイル出力モジュール８１６は、完全圧縮エントロピー符号化入力画像を、例えば、方法１００に基づく処理後、ファイルに出力する、またはデコードするための別のエンティティに伝送されるように構成される。出力としての完全圧縮エントロピー符号化入力画像は、とりわけ、圧縮されたエントロピー符号化入力画像およびサブ解像度画像を含む。圧縮されたエントロピー符号化入力画像を保存する、例示的ファイルは、以下の図１０に図示される。
【０１０３】
図９は、ある実施形態による、画像の圧縮におけるデータエンティティを図示する。入力画像９００は、圧縮されるためにエンコーダ８００に入力される圧縮されていない画像である。圧縮されたエントロピー符号化画像９０４は、完全に圧縮され、かつエントロピー符号化された入力画像である。入力画像中間形式９０２（また、「中間画像」とも称される）は、入力画像が受ける、圧縮されていない入力画像と圧縮されたエントロピー符号化画像との間の画像形式のいくつかの中間段階を指す。例は、事前処理モジュール８０２およびそのサブモジュールのいずれかからの出力、空間的予測子８０４からの出力、カラー空間コンバータ８０６からの出力、画素コンプレッサ８０８およびそのサブモジュールのいずれかからの出力、ならびに２次元局所性変換モジュール８１０からの出力を含む。
【０１０４】
空間的予測子サブ解像度画像９０６、カラー相関サブ解像度画像９０８、およびエントロピーサブ解像度画像９１０の各々は、入力画像内の各ブロック（例えば、１６×１６画素面積）に対する画素を備えている。空間的予測子サブ解像度画像９０６は、入力画像のそれぞれのブロックに対して選択された空間的予測子を保存する。カラー相関サブ解像度画像９０８は、入力画像内の各ブロックに対するカラー相関係数を保存する。エントロピーサブ解像度画像９１０は、入力画像の各ブロックに対して、エントロピー符号の組への参照を保存する。
【０１０５】
新生パレット９２０は、ある実施形態によると、ハッシュインデックス９２２およびパレット値９２４を備えている各エントリを伴う、ハッシュ表である。パレット値９２４は、カラーを備えている。ハッシュインデックス９２２は、対応するカラー値のうちの１つからのビットを使用して算出されたインデックスに対応する。
【０１０６】
２次元符号表９３０は、選択された画素距離に対して、短符号を用いて構成される。短符号は、画像内の画素場所間の２次元距離を表す。２次元符号表９３０の各エントリは、２つの画素間の画素距離を表す、相対的画素距離エントリ９３２と、その距離を表す、短２次元符号９３６とを含み得る。
【０１０７】
空間的予測子符号表９４０は、複数の空間的予測子を表す符号を用いて構成される。前述のように、空間的予測子は、個々の画素または２つ以上の画素の組み合わせに基づき得る。
【０１０８】
図１０は、圧縮されたエントロピー符号化画像９０４を保存することができる、ファイル形式１０００のコンテンツのブロック図を図示する。画像形式１０００は、永続性メモリ内に圧縮されたエントロピー符号化入力画像９０４を保存するために使用することができる。さらに、画像形式１０００は、解凍されるために、圧縮されたエントロピー符号化入力画像９０４を別のエンティティに伝送するための形式として使用することができる。当業者は、他の要素が、ファイル形式１０００内に含まれ得ることを理解するであろう。
【０１０９】
画像サイズ１００２は、画像ファイルのサイズを表す。サイズは、バイトで規定され得る。ブロックサイズ１００６は、圧縮プロセスにおいて使用されたブロックのサイズ（例えば、１６×１６画素）を表す。パレットハッシュ情報１００４は、限定されないが、ハッシュインデックスサイズおよびパレットエントリを含む、カラーパレットに関する情報を表す。保存されるエントロピーサブ解像度画像１０１２、保存されるカラー相関サブ解像度画像１０１４、および保存される空間的予測子サブ解像度画像１０１６は、保存されるそれぞれのサブ解像度画像である。保存されるエントロピーサブ解像度画像は、エントロピー符号組１００８への参照を含み得る。例えば、参照は、エントロピー符号組１００８からエントロピー符号組を識別する整数であり得る。前述のように、各サブ解像度画像は、入力画像を圧縮および保存するために使用されたものと同一のプロセスを使用して、再帰的様式で保存され得る。保存される圧縮されたエントロピー符号化入力画像１０２２は、圧縮されたエントロピー符号化入力画像のビットストリームである。
【０１１０】
例えば、保存される圧縮されたエントロピー符号化入力画像１０２２等、方法１００を使用してエンコードされた画像の受信に応じて、対応するデコーダは、ステップ１１６−１０２のうちのいくつかの逆を行い、圧縮されておらず、かつデコードされた入力画像を得てもよい。図１１は、ある実施形態による、デコーディングプロセスを行う、方法１１００を図示する。
【０１１１】
ステップ１１０２では、圧縮されたエントロピー符号化画像ファイルが、処理され、圧縮されたエントロピー符号化入力画像、圧縮されたサブ解像度画像、および入力画像を解凍し、復元するために必要とされる他の情報を得る。圧縮されたサブ解像度画像は、エントロピー符号サブ解像度画像、空間的予測子サブ解像度画像、およびカラー相関サブ解像度画像の圧縮されたバージョンを含む。圧縮されたエントロピー符号化画像ファイルのコンテンツは、図１０に関連して前述されている。前述のように、各圧縮されたサブ解像度画像は、入力画像を圧縮するために使用される同一の方法１００を再帰的に使用することによって、保存されている。したがって、方法１１００は、各圧縮されたエントロピー符号化サブ解像度画像に関してそれぞれ行われ、対応する圧縮されていないサブ解像度画像を得てもよい。説明を容易にするために、方法１１００のステップは、入力画像のデコーディングに関して、以下に説明される。
【０１１２】
ステップ１１０４では、エントロピー符号化入力画像のデコーディングが、行われる。入力画像をエンコードする際に使用されたエントロピー符号が、エントロピー符号サブ解像度画像内の対応する画素に基づいて、決定される。前述のように、エントロピー符号サブ解像度画像の各画素は、入力画像内のブロックに対応し、ブロックのために使用されるエントロピー符号組を規定する。エントロピー符号サブ解像度画像は、対応するエントロピー符号組への各ブロックに対する参照を含み得る。エントロピー符号組は、分解された画像において、または別個の伝送を通してのいずれかによって、デコーダに別個に利用可能であり得る。エントロピー符号をデコードすることによって、圧縮された入力画像が、エントロピー符号化入力画像から得られる。
【０１１３】
ステップ１１０６では、２次元局所性変換が、反転される。例えば、２次元局所性変換符号が含まれる、圧縮された入力画像内の各位置において、値は、対応する実際の画素距離と置換される。２次元局所性変換距離符号は、分解された画像において、別個の伝送を通して、または構成を通してのいずれかによって、デコーダに別個に利用可能であり得る。
【０１１４】
ステップ１１０８では、圧縮された入力画像が、解凍される。前述のようにように、入力画像の圧縮の間、画素ベースの圧縮が、入力画像の左上画素から右下画素へ、それぞれの画素位置に、逆方向参照、画素、またはパレット参照のうちの１つを挿入することによって行われた。解凍の間、圧縮された入力画像は、左上画素から右下画素にトラバースされ、逆方向参照からのデータ、画素値、またはカラーパレットからの値を挿入する。入力画像の初期圧縮に関連して前述のように、新生パレットが、解凍プロセスが圧縮された入力画像の画素を通して進むにつれて構築される。圧縮された画素場所が、トラバースされるにつれて、新生パレットが、カラー値のハッシュ表を取り込むことによって、動的に構築される。パレットインデックスが挿入された圧縮された入力画像内の場所に遭遇すると、動的に構築された新生パレットからの対応するカラー値と置換される。画素解凍ステップ１１０８からの出力は、依然として、カラー空間変換のエンコーディング、空間的予測、およびエンコーダによって行われる他の事前処理ステップを含む、解凍された入力画像である。
【０１１５】
ステップ１１１０では、入力画像内のカラー空間変換が、デコードされる。エンコードされたカラー空間変換は、前述のように、それぞれの相関係数に基づいて、赤色および青色に対する予測誤差によって、カラー値を置換した。相関係数は、カラー相関サブ解像度画像内で利用可能である。カラー相関サブ解像度画像内に保存された相関係数を使用して、デコーディングプロセスは、カラー値をカラー相関を伴わないその値に戻す。
【０１１６】
ステップ１１１２では、エンコーディングの間に行われた空間的予測が、反転される。空間的予測は、空間的予測サブ解像度画像内で利用可能な空間的予測子を使用して、反転される。各画素に対して、予測された値、より精密には、予測誤差値が、実際の対応する画素値と置換される。
【０１１７】
ステップ１１１４では、エンコーダによって行われた１つ以上の事前処理ステップが、反転される。エンコーディングの間に行われた事前処理ステップは、例えば、α置換、カラー離散化、およびパレット選択のうちの１つ以上を含み得る。これらの事前処理ステップの各々は、エンコーディング方法１００に関連して前述されている。
【０１１８】
方法１１００の完了に応じて、元々の入力画像のデコードされたバージョンが、得られる。
【０１１９】
図１２は、ある実施形態による、デコーダ１２００を図示する。デコーダ１２００は、入力画像デコーダ１２０１および画像ファイルデコンポーザ１２０２を含む。入力画像デコーダ１２０１は、エントロピーデコーダ１２０４、２次元変換デコーダ１２０６、画素デコンプレッサ１２０８、パレットジェネレータ１２１０、カラー空間変換デコーダ１２１２、空間的予測デコーダ１２１４、および事前処理デコーダ１２１６を備えている。デコーダ１２００は、ある実施形態によると、方法１００等のプロセスを使用して以前にエンコードされた画像をデコードする方法１２００を行う。
【０１２０】
画像ファイルデコンポーザ１２０２は、方法１００等のエンコーディングプロセスによって作成された圧縮エンコード画像ファイルを入力としてとり、エンコードされた圧縮入力画像、サブ解像度画像、および入力画像のデコーティングを補助する他の保存された成分を抽出するように動作する。図１０は、画像ファイルデコンポーザ１２０２に入力される、圧縮エンコード画像ファイルの例示的形式を図示する。入力画像デコーダ１２０１は、以下に説明されるように、エンコードされた圧縮入力画像をデコードするように動作する。ある実施形態によると、サブ解像度画像の各々も、入力画像デコーダ１２０１を使用してデコードされる。
【０１２１】
エントロピーデコーダ１２０４は、エンコーディングプロセスによって圧縮された入力画像に関して行われたエントロピーエンコーディングを反転するように動作する。エントロピーデコーディングプロセスは、エントロピーサブ解像度画像（圧縮されたエンコードされた画像ファイルからデコードされた）を使用して、入力画像の各ブロックに対してエントロピー符号を選択する。
【０１２２】
２次元変換デコーダ１２０６は、エンコーダによって圧縮された入力画像内に挿入された２次元変換符号を実際の画素距離と置換するように動作する。
【０１２３】
画素デコンプレッサ１２０８は、エンコーダによって行われた初期圧縮を反転するように動作する。ある実施形態によると、画像デコンプレッサは、２次元距離符号が置換された後のエントロピーデコードされた圧縮画像を入力としてとる。解凍の間、圧縮された入力画像は、左上画素から右下画素へトラバースされ、逆方向参照からのデータ、画素値、またはカラーパレットからの値を挿入する。
【０１２４】
パレットジェネレータ１２１０は、入力画像の解凍の間、カラーパレット（前述で「新生パレット」と称される）を動的に作成するように動作する。方法１１００のステップ１１０８に関連して説明されるように、圧縮された画素場所がトラバースされるにつれて、新生パレットは、カラー値のハッシュ表を取り込むことによって、動的に構築される。
【０１２５】
カラー空間変換デコーダ１２１２は、入力として解凍された入力画像をとり、エンコーダによって挿入されたカラー空間変換符号化を反転するように動作する。カラー空間サブ解像度画像内にブロック毎ベースで保存されるカラー相関子は、カラー空間変換をデコーディングする際に採用される。カラー空間デコーディングは、方法１１００のステップ１１１０に関連して前述されている。
【０１２６】
空間的予測デコーダ１２１４は、エンコーディングプロセスの間、エンコードされた空間的予測をデコードするように動作する。各ブロックに対する空間的予測子は、空間的予測子サブ解像度画像内で利用可能である。
【０１２７】
事前処理デコーダ１２１６は、例えば、エンコーディングプロセスの間に行われ得る、α置換、カラー離散化、およびパレット選択等の事前処理ステップのいずれかを反転するように動作する。事前処理デコーダ１２１６の出力は、完全にデコードされた入力画像である。
【０１２８】
図１３は、図１−７に図示されるエンコーディング方法、図１１に図示されるデコーディング方法、エンコーダ８００、および／またはデコーダ１２００等の実施形態を実装することができる、コンピュータシステム１３００を図示する。システム１３００は、命令を実行し、画素情報を含む情報を処理するための任意のコンピュータまたは電子プロセッサを含み得る、プロセッサ１３０２を含む。プロセッサ１３０２は、命令の任意のシーケンスを処理可能な任意のデバイスを含み得るか、またはその一部であり得る。プロセッサ１３０２は、例えば、コンピュータプロセッサ、モバイルデバイスまたは他の電子内のプロセッサ、および／またはデジタルプロセッサを含み得る。プロセッサ１３０２は、例えば、コンピュータ、モバイルコンピューティングデバイス、スマートフォン、セットトップボックス、エンターテイメントプラットフォーム、サーバ、カメラまたは他の画像捕捉デバイス、サーバファーム、クラウドコンピュータ等内に含まれ得る。
【０１２９】
プロセッサ１３０２は、バス１３０８を介して、メモリ１３０４に接続され得る。メモリ１３０４は、揮発性、永続性、仮想、または別様に、システム１３００による使用または出力のための情報を保存するメモリを含み得る。メモリ１３０４は、例えば、ランダムアクセスメモリ（ＲＡＭ）および／または動的ＲＡＭ（ＤＲＡＭ）を含み得る。メモリ１３０４は、システム１３００の状態情報等の任意の情報を保存するために使用され得る。メモリ１３０４はまた、例えば、画像処理モジュール１１２の命令を含む、システム１３００の命令を保存するために使用され得る。システム１３００は、必要または適切な１つ以上のプロセッサ１３０２を含み得る。
【０１３０】
バス１３０８は、システム１３００の種々の構成要素間の相互作用を可能にする、通信インフラストラクチャを含み得る。バス１３０８は、例えば、プロセッサ１３０２とメモリ１３０４との間等のシステム１３００の構成要素間でデータを搬送し得る。バス１３０８は、システム１３００の構成要素間に無線および／または有線通信媒体を含み得、並列、直列、または他のトポロジ配列を含み得る。
【０１３１】
永続性記憶装置１３０６は、ある長期的期間にわたって（例えば、メモリ１３０４と比較して）、データを保存するために、システム１３００によって使用されるようなメモリまたは他の永続性記憶装置等の構成要素を含み得る。永続性記憶装置１３０６は、システム１３００内のプロセッサ１３０２によって使用されるような不揮発性メインメモリを含み得る。永続性記憶装置１３０６は、例えば、フラッシュメモリ、ハードディスク、光ディスク、または他のコンピュータ読み取り可能な媒体を含み得る。
【０１３２】
入力／出力インターフェース１３１０は、キーボード、マウス、音声コマンド入力、ディスプレイ、あるいは他の入力または出力デバイスに対するインターフェースを含み得る。圧縮されることになる構成コマンドおよび／または画像は、入力／出力デバイスインターフェース１３１０を通して受信され得る。
【０１３３】
ネットワークインターフェース１３１２は、ローカルエリアネットワークまたはインターネット等のネットワークへの１つ以上のインターフェースを含み得る。ネットワークインターフェース１３１２は、有線または無線接続のためのインターフェースを含み得る。圧縮されることになる構成コマンドおよび／または画像は、ネットワークインターフェース１３１２を通して受信され得る。
【０１３４】
本発明は、規定された機能およびその関係の実装を図示する、機能的構築ブロックを用いて前述された。これらの機能的構築ブロックの境界は、本明細書では、説明の便宜上、随意的に定義されている。規定された機能およびその関係が、適切に行われる限り、代替境界が、定義されることができる。
【０１３５】
特定の実施形態の上記説明は、当技術の範囲内の知識を適用することにより、必要以上の実験を行わずに、また本発明の一般的概念から逸脱せずに、他の者がそのような特定の実施形態を様々な用途に合わせ容易に修正および／または適合させることができるように、本発明の一般的性質を十分明らかとしている。したがって、そのような適合および修正は、本明細書に示された教示および指針に基づき、開示された実施形態の同等物の意味および範囲内であることが意図される。本明細書における語法または用語は、説明を目的としており、限定を目的とせず、本明細書の用語または語法は、教示および指針に照らして当業者により解釈されるべきであることを理解されたい。
【０１３６】
本発明の広さおよび範囲は、上述の例示的な実施形態のいずれによっても限定されるべきではなく、以下の請求項およびその同等物によってのみ定義されるべきである。
【図１】
2014525183.tif 000003
【図２】
2014525183.tif 000004
【図３】
2014525183.tif 000005
【図４】
2014525183.tif 000006
【図５】
2014525183.tif 000007
【図６】
2014525183.tif 000008
【図７】
2014525183.tif 000009
【図８】
2014525183.tif 000010
【図９】
2014525183.tif 000011
【図１０】
2014525183.tif 000012
【図１１】
2014525183.tif 000013
【図１２】
2014525183.tif 000014
【図１３】
2014525183.tif 000015
【手続補正書】
【提出日】平成26年1月14日(2014.1.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力画像を圧縮する方法であって、前記方法は、
前記入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
サブ解像度画像を生成することであって、前記サブ解像度画像における各画素は、前記複数のエントロピー符号組からのエントロピー符号組を保存し、前記エントロピー符号組は、前記入力画像内の対応する画素をエンコードする、ことと、
エントロピー符号を含む圧縮パラメータを制御するために前記生成されたサブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、前記エンコードされた入力画像および前記生成されたサブ解像度画像を出力することと
を含む、方法。
【請求項２】
入力画像を圧縮する方法であって、前記方法は、
前記入力画像から、複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像を生成することであって、前記それぞれのサブ解像度画像の各々における各画素は、前記複数の圧縮パラメータからの圧縮パラメータをエンコードし、前記圧縮パラメータは、前記入力画像における画素の組をエンコードする、ことと、
前記複数の圧縮パラメータの各々を制御するために前記それぞれのサブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、前記エンコードされた入力画像および前記生成されたサブ解像度画像を出力することと
を含む、方法。
【請求項３】
前記それぞれのサブ解像度画像を生成することは、
前記入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
第１のサブ解像度画像を生成することであって、前記第１のサブ解像度画像における各画素は、前記複数のエントロピー符号組からのエントロピー符号組を保存し、前記エントロピー符号組は、前記入力画像内の対応する画素をエンコードする、ことと
を含む、請求項２に記載の方法。
【請求項４】
前記複数のエントロピー符号組を決定することは、
前記入力画像を複数のブロックに分割することと、
前記複数のブロックからのそれぞれのブロックに対するエントロピー統計を決定することと、
前記決定されたエントロピー統計の類似性に従って、前記複数のブロックをクラスタ化し、複数のブロッククラスタを形成することと、
前記ブロッククラスタの各々に対するエントロピー符号を決定することと
を含む、請求項３に記載の方法。
【請求項５】
形成されるブロッククラスタの数は、前記第１のサブ解像度画像のビットのサイズを最小限にすることに基づいて決定される、請求項４に記載の方法。
【請求項６】
前記それぞれのサブ解像度画像を生成することは、
前記入力画像のそれぞれのブロックに対して、予測のエントロピーを低減させるように構成されている空間的予測子を決定することと、
前記それぞれのブロックに対する前記空間的予測子を備えている第２のサブ解像度画像を生成することと
を含む、請求項２に記載の方法。
【請求項７】
前記入力画像をエンコードすることは、前記第２のサブ解像度画像から、前記入力画像のそれぞれのブロックに対する前記空間的予測子を決定することを含む、請求項６に記載の方法。
【請求項８】
前記空間的予測子を決定することは、前記ブロックに対するエンコーディングコスト、前記複数のブロックに対する予測誤差、および近傍画素に対して選択された空間的予測子に対するバイアスを最小限化することにさらに基づく、請求項６に記載の方法。
【請求項９】
前記それぞれのサブ解像度画像を生成することは、
前記入力画像のそれぞれのブロックに対して、前記ブロックの画素における２つ以上のカラー成分間の相関に対応するカラー相関係数を決定することと、
前記それぞれのブロックに対する前記カラー相関係数を備えている第３のサブ解像度画像を生成することと
を含む、請求項２に記載の方法。
【請求項１０】
前記ブロックに対する前記カラー相関係数を決定することは、
緑色成分、赤色成分、および青色成分のうちの任意の２つ間の相関と、
前記ブロックにおける赤色チャネルおよび青色チャネルにおけるエントロピーを低減させることと
にさらに基づく、請求項９に記載の方法。
【請求項１１】
前記入力画像をエンコードすることは、前記第３のサブ解像度画像からアクセスされる前記カラー相関係数を少なくとも部分的に使用して、予測誤差を決定することを含む、請求項９に記載の方法。
【請求項１２】
前記入力画像をエンコードすることは、別個のエントロピー符号を使用して、赤色チャネル、青色チャネル、緑色チャネル、およびαチャネルをエンコードすることを含む、請求項２に記載の方法。
【請求項１３】
前記入力画像をエンコードすることは、前記入力画像の１つ以上のブロックのそれぞれの群に対して、カラーパレットを局所的に決定することを含む、請求項２に記載の方法。
【請求項１４】
前記カラーパレットは、ハッシュ法を使用して、動的に決定される、請求項１３に記載の方法。
【請求項１５】
圧縮されたエントロピー符号化画像ファイルとして、前記エンコードされた入力画像および前記生成されたサブ解像度画像を出力することは、第１のエンコーディング技法を使用して、前記エンコードされた入力画像、および前記生成されたサブ解像度画像を保存することを含む、請求項２に記載の方法。
【請求項１６】
前記エンコードすることは、
それぞれのコストに基づいて、前記入力画像内のそれぞれの画素に対して、先に生じた画素への逆方向参照を挿入すること、前記画素を挿入すること、またはカラーパレットエントリからのインデックスを挿入することのうちの１つから動作を選択し、中間画像を生成することと、
前記中間画像の最初の画素から最後の画素への動作の最小コスト経路を決定することと
を含む、請求項２に記載の方法。
【請求項１７】
前記逆方向参照は、画素において規定される、請求項１６に記載の方法。
【請求項１８】
前記逆方向参照は、２次元平面における距離に対する所定の距離符号を使用して規定される、請求項１６に記載の方法。
【請求項１９】
前記それぞれのコストの各々は、対応する動作に対する出力ビットの数を含む、請求項１６に記載の方法。
【請求項２０】
オフセットを用いて、前記入力画像において半透明の赤色、緑色、および青色値を有する画素のα値を調節することをさらに含む、請求項２に記載の方法。
【請求項２１】
前記α値を調節することは、結果として生じる予測誤差における新しいシンボルを低減させるために、前記入力画像におけるカラーの動的範囲をパックすることを含む、請求項２０に記載の方法。
【請求項２２】
エンコーダであって、前記エンコーダは、
プロセッサと、
前記プロセッサに連結されたメモリと、
エントロピー符号生成モジュールであって、前記エントロピー符号生成モジュールは、前記プロセッサによって実行されると、
入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
サブ解像度画像を生成することであって、前記サブ解像度画像における各画素は、前記複数のエントロピー符号組からのエントロピー符号組を保存し、前記エントロピー符号組は、前記入力画像内の対応する画素をエンコードする、ことと
を前記プロセッサに行わせるように構成されている、エントロピー符号生成モジュールと、
画像保存モジュールであって、前記画像保存モジュールは、前記プロセッサによって実行されると、圧縮パラメータを制御するために前記生成されたサブ解像度画像を使用して、前記入力画像をエンコードすることを前記プロセッサに行わせるように構成されている、画像保存モジュールと、
圧縮画像ファイル出力モジュールであって、前記圧縮画像ファイル出力モジュールは、前記プロセッサによって実行されると、圧縮されたエントロピー符号化画像ファイルとして、前記エンコードされた入力画像および前記生成された第１のサブ解像度画像を出力することを前記プロセッサに行わせるように構成されている、圧縮画像ファイル出力モジュールと
を備えている、エンコーダ。
【請求項２３】
前記エントロピー符号生成モジュールは、前記プロセッサによって実行されると、
前記入力画像を複数のブロックに分割することと、
前記複数のブロックからのそれぞれのブロックに対するエントロピー統計を決定することと、
前記決定されたエントロピー統計の類似性に従って、前記複数のブロックをクラスタ化し、複数のブロッククラスタを形成することと、
前記ブロッククラスタのそれぞれに対するエントロピー符号を決定することと
を前記プロセッサに行わせるようにさらに構成されている、請求項２２に記載のエンコーダ。
【請求項２４】
前記圧縮画像ファイル出力モジュールは、前記プロセッサによって実行されると、第１のエンコーディング技法を使用して、前記エンコードされた入力画像、および、前記生成されたサブ解像度画像のエンコードされたバージョンを保存することを前記プロセッサに行わせるようにさらに構成されている、請求項２２に記載のエンコーダ
【請求項２５】
エンコードされた命令を有するコンピュータ読み取り可能な保存媒体を備えている製造品であって、前記命令は、コンピューティングデバイスによって実行されると、前記コンピューティングデバイスに、動作を行わせ、前記動作は、
前記入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
サブ解像度画像を生成することであって、前記サブ解像度画像における各画素は、前記複数のエントロピー符号組からのエントロピー符号組を保存し、前記エントロピー符号組は、前記入力画像内の対応する画素をエンコードする、ことと、
エントロピー符号を含む圧縮パラメータを制御するために前記生成されたサブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、前記エンコードされた入力画像および前記生成されたサブ解像度画像を出力することと
を含む、製造品。
【請求項２６】
エンコードされた入力画像を解凍する方法であって、前記方法は、
圧縮されたエントロピー符号化画像ファイルを分解し、前記エンコードされた入力画像と複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像とにアクセスすることであって、前記それぞれのサブ解像度画像の各々における各画素は、前記複数の圧縮パラメータからの圧縮パラメータをエンコードし、前記圧縮パラメータは、元々の画像における画素の組をエンコードする、ことと、
前記複数の圧縮パラメータの各々を制御するために前記それぞれのサブ解像度画像を使用して、前記エンコードされた入力画像をデコードすることと、
前記デコードされた入力画像を出力することと
を含む、方法。
【請求項２７】
デコーダであって、前記デコーダは、
プロセッサと、
前記プロセッサに連結されたメモリと、
画像ファイルデコンポーザであって、前記画像ファイルデコンポーザは、前記プロセッサによって実行されると、圧縮されたエントロピー符号化画像ファイルを分解し、エンコードされた圧縮入力画像と複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像とにアクセスすることであって、前記それぞれのサブ解像度画像の各々における各画素は、前記複数の圧縮パラメータからの圧縮パラメータをエンコードし、前記圧縮パラメータは、元々の画像における画素の組をエンコードする、ことを前記プロセッサに行わせるように構成されている、画像ファイルデコンポーザと、
入力画像デコーダであって、前記入力画像デコーダは、前記プロセッサによって実行されると、前記複数の圧縮パラメータの各々を制御するために前記それぞれのサブ解像度画像を使用して、前記エンコードされた入力画像をデコードすることを前記プロセッサに行わせるように構成されている、入力画像デコーダと
を備えている、デコーダ。
【請求項２８】
入力画像を圧縮する方法であって、前記方法は、
前記入力画像の複数のブロックに対して、予測のエントロピーを低減させるように構成されているそれぞれの空間的予測子を決定することであって、前記決定することは、前記ブロックに対するエンコーディングコスト、前記ブロックに対する予測誤差、および近傍画素に対して選択された空間的予測子に対するバイアスを最小限化することを含む、ことと、
前記それぞれのブロックに対する前記空間的予測子を備えているサブ解像度画像を生成することと、
前記複数の圧縮パラメータの各々を制御するために前記サブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、前記エンコードされた入力画像および前記生成されたサブ解像度画像を出力することと
を含む、方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
さらなる特徴および利点ならびに種々の実施形態の構造および動作が、付随の図面を参照して、以下に詳細に説明される。本発明は、本明細書に説明される具体的実施形態に限定されないことに留意されたい。そのような実施形態は、例証的目的のためだけに本明細書に提示される。追加の実施形態は、本明細書に含まれる教示に基づいて、当業者に明白となるであろう。
本発明はさらに、例えば、以下を提供する。
（項目１）
入力画像を圧縮する方法であって、前記方法は、
前記入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
前記複数のエントロピー符号組への参照を備えている第１のサブ解像度画像を含む１つ以上のサブ解像度画像を生成することであって、前記参照の各々は、前記入力画像内の対応する画素をエンコードするために使用される、前記エントロピー符号組のうちの１つを示す、ことと、
エントロピー符号を含む１つ以上の圧縮パラメータを制御するために前記生成された１つ以上のサブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、少なくとも前記エンコードされた入力画像および前記生成された１つ以上のサブ解像度画像を出力することと
を含む、方法。
（項目２）
入力画像を圧縮する方法であって、前記方法は、
前記入力画像から、複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像を生成することと、
前記複数の圧縮パラメータの各々を制御するために前記それぞれのサブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、少なくとも前記エンコードされた入力画像および前記生成されたサブ解像度画像を出力することと
を含む、方法。
（項目３）
前記それぞれのサブ解像度画像を生成することは、
前記入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
前記複数のエントロピー符号組への参照を備えている第１のサブ解像度画像を生成することであって、前記参照の各々は、前記入力画像内の対応する画素をエンコードするために使用される、前記エントロピー符号組のうちの１つを示す、ことと
を含む、項目２に記載の方法。
（項目４）
前記複数のエントロピー符号組を決定することは、
前記入力画像を複数のブロックに分割することと、
前記複数のブロックからのそれぞれのブロックに対するエントロピー統計を決定することと、
前記決定されたエントロピー統計の類似性に従って、前記複数のブロックをクラスタ化し、複数のブロッククラスタを形成することと、
前記ブロッククラスタの各々に対するエントロピー符号を決定することと
を含む、項目３に記載の方法。
（項目５）
形成されるブロッククラスタの数は、前記第１のサブ解像度画像のビットのサイズを最小限にすることに基づいて決定される、項目４に記載の方法。
（項目６）
前記それぞれのサブ解像度画像を生成することは、
前記入力画像のそれぞれのブロックに対して、予測のエントロピーを低減させるように構成されている空間的予測子を決定することと、
前記それぞれのブロックに対する前記空間的予測子を備えている第２のサブ解像度画像を生成することと
を含む、項目２に記載の方法。
（項目７）
前記入力画像をエンコードすることは、前記第２のサブ解像度画像から、前記入力画像のそれぞれのブロックに対する前記空間的予測子を決定することを含む、項目６に記載の方法。
（項目８）
前記空間的予測子を決定することは、前記ブロックに対するエンコーディングコスト、前記複数のブロックに対する予測誤差、および近傍画素に対して選択された空間的予測子に対するバイアスを最小限化することにさらに基づく、項目６に記載の方法。
（項目９）
前記それぞれのサブ解像度画像を生成することは、
前記入力画像のそれぞれのブロックに対して、前記ブロックの画素における２つ以上のカラー成分間の相関に対応するカラー相関係数を決定することと、
前記それぞれのブロックに対する前記カラー相関係数を備えている第３のサブ解像度画像を生成することと
を含む、項目２に記載の方法。
（項目１０）
前記ブロックに対する前記カラー相関係数を決定することは、
緑色成分、赤色成分、および青色成分のうちの任意の２つ間の相関と、
前記ブロックにおける赤色チャネルおよび青色チャネルにおけるエントロピーを低減させることと
にさらに基づく、項目９に記載の方法。
（項目１１）
前記入力画像をエンコードすることは、前記第３のサブ解像度画像からアクセスされる前記カラー相関係数を少なくとも部分的に使用して、予測誤差を決定することを含む、項目９に記載の方法。
（項目１２）
前記入力画像をエンコードすることは、別個のエントロピー符号を使用して、赤色チャネル、青色チャネル、緑色チャネル、およびαチャネルをエンコードすることを含む、項目２に記載の方法。
（項目１３）
前記入力画像をエンコードすることは、前記入力画像の１つ以上のブロックのそれぞれの群に対して、カラーパレットを局所的に決定することを含む、項目２に記載の方法。
（項目１４）
前記カラーパレットは、ハッシュ法を使用して、動的に決定される、項目１３に記載の方法。
（項目１５）
前記エンコードされた入力画像および前記生成されたサブ解像度画像のエンコードされたものを保存することが、第１のエンコーディング技法を使用して、前記入力画像、前記第１のサブ解像度画像、前記第２のサブ解像度画像、および前記第３のサブ解像度画像をエンコードすることを含む、項目２に記載の方法。
（項目１６）
前記エンコードすることは、
それぞれのコストに基づいて、前記入力画像内のそれぞれの画素に対して、先に生じた画素への逆方向参照を挿入すること、前記画素を挿入すること、またはカラーパレットエントリからのインデックスを挿入することのうちの１つから動作を選択し、中間画像を生成することと、
前記中間画像の最初の画素から最後の画素への動作の最小コスト経路を決定することと
を含む、項目２に記載の方法。
（項目１７）
前記逆方向参照は、画素において規定される、項目１６に記載の方法。
（項目１８）
前記逆方向参照は、２次元平面における距離に対する所定の距離符号を使用して規定される、項目１６に記載の方法。
（項目１９）
前記それぞれのコストの各々は、対応する動作に対する出力ビットの数を含む、項目１６に記載の方法。
（項目２０）
オフセットを用いて、前記入力画像において半透明の赤色、緑色、および青色値を有する画素のα値を調節することをさらに含む、項目２に記載の方法。
（項目２１）
前記α値を置換することは、結果として生じる予測誤差における新しいシンボルを低減させるために、前記入力画像におけるカラーの動的範囲をパックすることを含む、項目２０に記載の方法。
（項目２２）
エンコーダであって、前記エンコーダは、
プロセッサと、
前記プロセッサに連結されたメモリと、
エントロピー符号生成モジュールであって、前記エントロピー符号生成モジュールは、前記プロセッサによって実行されると、
入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
前記複数のエントロピー符号組への参照を備えている第１のサブ解像度画像を生成することであって、前記参照の各々は、前記入力画像内の対応する画素をエンコードするために使用される前記エントロピー符号組のうちの１つを示す、ことと
を前記プロセッサに行わせるように構成されている、エントロピー符号生成モジュールと、
画像保存モジュールであって、前記画像保存モジュールは、前記プロセッサによって実行されると、複数の圧縮パラメータの各々を制御するためにそれぞれのサブ解像度画像を使用して、前記入力画像をエンコードすることを前記プロセッサに行わせるように構成されている、画像保存モジュールと、
圧縮画像ファイル出力モジュールであって、前記圧縮画像ファイル出力モジュールは、前記プロセッサによって実行されると、圧縮されたエントロピー符号化画像ファイルとして、少なくとも前記エンコードされた入力画像および前記生成された第１のサブ解像度画像を出力することを前記プロセッサに行わせるように構成されている、圧縮画像ファイル出力モジュールと
を備えている、エンコーダ。
（項目２３）
前記エントロピー符号生成モジュールは、前記プロセッサによって実行されると、
前記入力画像を複数のブロックに分割することと、
前記複数のブロックからのそれぞれのブロックに対するエントロピー統計を決定することと、
前記決定されたエントロピー統計の類似性に従って、前記複数のブロックをクラスタ化し、複数のブロッククラスタを形成することと、
前記ブロッククラスタのそれぞれに対するエントロピー符号を決定することと
を前記プロセッサに行わせるようにさらに構成されている、項目２２に記載のエンコーダ。
（項目２４）
前記圧縮画像ファイル出力モジュールは、前記プロセッサによって実行されると、第１のエンコーディング技法を使用して、前記エンコードされた入力画像、および、前記生成された第１のサブ解像度画像のエンコードされたバージョンを保存することを前記プロセッサに行わせるようにさらに構成されている、項目２２に記載のエンコーダ
（項目２５）
エンコードされた命令を有するコンピュータ読み取り可能な保存媒体を備えている製造品であって、前記命令は、コンピューティングデバイスによって実行されると、前記コンピューティングデバイスに、動作を行わせ、前記動作は、
前記入力画像内の統計的類似領域に基づいて、複数のエントロピー符号組を決定することと、
前記複数のエントロピー符号組への参照を備えている第１のサブ解像度画像を含む１つ以上のサブ解像度画像を生成することであって、前記参照の各々は、前記入力画像内の対応する画素をエンコードするために使用される前記エントロピー符号組のうちの１つを示す、ことと、
エントロピー符号を含む１つ以上の圧縮パラメータを制御するために前記生成された１つ以上のサブ解像度画像を使用して、前記入力画像をエンコードすることと、
圧縮されたエントロピー符号化画像ファイルとして、前記エンコードされた入力画像および前記生成された１つ以上のサブ解像度画像を出力することと
を含む、製造品。
（項目２６）
エンコードされた入力画像を解凍する方法であって、前記方法は、
圧縮されたエントロピー符号化画像ファイルを分解し、前記エンコードされた入力画像と複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像とにアクセスすることと、
前記複数の圧縮パラメータの各々を制御するために前記それぞれのサブ解像度画像を使用して、前記エンコードされた入力画像をデコードすることと、
前記デコードされた入力画像を出力することと
を含む、方法。
（項目２７）
デコーダであって、前記デコーダは、
プロセッサと、
前記プロセッサに連結されたメモリと、
画像ファイルデコンポーザであって、前記画像ファイルデコンポーザは、前記プロセッサによって実行されると、圧縮されたエントロピー符号化画像ファイルを分解し、エンコードされた圧縮入力画像と複数の圧縮パラメータの各々に対するそれぞれのサブ解像度画像とにアクセスすることを前記プロセッサに行わせるように構成されている、画像ファイルデコンポーザと、
入力画像デコーダであって、前記入力画像デコーダは、前記プロセッサによって実行されると、前記複数の圧縮パラメータの各々を制御するために前記それぞれのサブ解像度画像を使用して、前記エンコードされた入力画像をデコードすることを前記プロセッサに行わせるように構成されている、入力画像デコーダと
を備えている、デコーダ。
【国際調査報告】
2014525183.tif 000016
2014525183.tif 000017
2014525183.tif 000018
2014525183.tif 000019
2014525183.tif 000020
2014525183.tif 000021
2014525183.tif 000022