(57)【要約】【課題】  リソースが抑制されている環境に適するカラー画像の伸張、そのような伸張を可能にするカラー画像の圧縮、および、単純なカラー画像の効率的な画像圧縮および伸張のための方法および装置を提供すること。【解決手段】  カラー画像(1)が、可変長カラー・コードと、画像の各カラーとを連結させるステップと、次いで、各々が、カラー画像の各ピクセルに対する2進カラー・コードの1つのビット位置を表わすビット・プレーン(51-54)を形成するステップと、によって圧縮される。可変長コードは、カノニカル・ハフマン・アルゴリズムなどによって最適化される。圧縮は、単純なアイコン画像、および、特殊な文字画像（例えば、16x16ピクセル）においてさえ、高度である。伸張は、簡単で、高速で、かつ、リソースがかからない。多くの他の使用の中で、この画像伸張は、カラーLCDディスプレイを持つセルラ電話での使用に適している。
2005516554.tif 000002
【特許請求の範囲】
【請求項１】
複数のビット・プレーンを作成するステップであって、各ビット・プレーンが、2進値の二次元アレイを有するステップと、
前記複数のビット・プレーンをエンコードするステップと、を有するカラー画像を圧縮する方法であって、
前記カラー画像中のピクセルのカラー別に2進カラー・コードのセットを形成するステップであって、前記2進カラー・コードが、可変長であるステップと、
カラー画像に適用された前記可変長2進カラー・コードのそれぞれのビット位置を表わすために、前記複数のビット・プレーンを作成するステップと、を有することを特徴とする方法。
【請求項２】
各カラーの出現頻度を参照して、前記カラー画像に用いられているカラーに、前記可変長2進カラー・コードを割り付けるステップを有する請求項1に記載の方法。
【請求項３】
各カラーに割り付けられる前記可変長2進コードが、ハフマン・アルゴリズムによって決定される請求項1に記載の方法。
【請求項４】
各カラーに割り付けられる前記可変長2進カラー・コードが、カノニカル・ハフマン・アルゴリズムによって決定される請求項1に記載の方法。
【請求項５】
グレイ・コードのセットが、前記可変長2進カラー・コードの少なくとも1つの長さに対して決定される請求項1に記載の方法。
【請求項６】
2進カラー・コードの最初の割り付けを形成するステップと、次いで、最も小さく圧縮された画像に帰結する最適カラー・コーディングが見つかるまで、連続的に代わりのカラー・コーディング割り付けを試みるステップとを有する請求項1に記載の方法。
【請求項７】
(a)  前記可変長2進カラー・コードに対する最初の木形状、および、リーフへのカラーの初期割り付けを選択するステップと、最初の圧縮された画像バージョンを形成するステップと、
(b)  最適のリーフ割り付けが決定されるまで、リーフのペアを連続的に交換することによって代わったリーフ割り付けを評価するステップと、連続的に圧縮された画像バージョンを形成するステップと、
(c)  前記木形状を連続的に変更することによって代わった木形状のセットを評価するステップと、代わったリーフ割り付けを評価するステップ(b)を反復するステップと、それによって、最適木形状および最適リーフ割り付けを選択するステップと、を有する請求項1に記載の方法。
【請求項８】
ステップ(c)が、前記木形状を連続的にモーフィングすることによって代わる木形状のセットの各々を形成するステップを有する請求項7に記載の方法。
【請求項９】
前記2進カラー・コードの木構造を定め、そして、前記2進カラー・コードと前記カラー画像に用いられているカラーとの連結を定めるカラー・コーディング・レファレンスを形成するステップを有する請求項1に記載の方法。
【請求項１０】
複数の原カラー画像に用いられているカラー別に、前記可変長カラー・コードを形成するステップを有する請求項1に記載の方法。
【請求項１１】
元カラー画像を、原画像のセットに分割するステップを有する請求項1に記載の方法。
【請求項１２】
各ビット・プレーンが、前記可変長2進カラー・コードのセットにおける1つのビット位置を表わす請求項1に記載の方法。
【請求項１３】
最初の作成されたビット・プレーンが、前記2進カラー・コードのセットの各々における最初のビット位置に対応する2進値を表わし、2番目、および、それ以降のビット・プレーンの各々が、それぞれ、前記2進カラー・コードにおける2番目、および、それ以降のビット位置を表わす請求項12に記載の方法。
【請求項１４】
1つのビット位置が、前記可変長2進カラー・コードのセットの任意の特定の1つにおいて存在しない場合には、前記ビット・プレーンの1つ以上に空白を形成するステップを有する請求項12に記載の方法。
【請求項１５】
前記ビット・プレーンをエンコードするステップが、コンテキスト・モデリングおよびエントロピ・エンコーディングを行うステップを有する請求項1に記載の方法。
【請求項１６】
前記ビット・プレーンの少なくとも最初のグループをエンコードするステップであって、一方、0個以上のそれ以降のビット・プレーンが、エンコードされないステップを有する請求項15に記載の方法。
【請求項１７】
前記ビット・プレーンを、少なくとも2つのグループに分配して、各ビット・プレーンのグループを、そのグループのエンコーディング・スキームでエンコードするステップを有する請求項15に記載の方法。
【請求項１８】
デコーディングに必要な順番を参照して、前記エンコードされたビット・プレーンからのエンコードされた記号をインターリーブするステップを有する請求項16に記載の方法。
【請求項１９】
請求項1の方法によって形成される、圧縮されたカラー画像信号。
【請求項２０】
可変長2進カラー・コードと、圧縮される元カラー画像において使用されているカラーとを連結させるように構成されたカラー・コーディング・ユニットと、
前記2進カラー・コードから、ビット・プレーンのセットを作成するためのビット・プレーン・ジェネレータと、
前記作成されたビット・プレーンをエンコードして、圧縮された画像を形成するためのビット・プレーン・エンコーディング・ユニットと、を有するカラー画像を圧縮するための画像エンコーダ。
【請求項２１】
可変長2進カラー・コードと、圧縮された画像のカラーとの連結を表わすカラー・コーディング・レファレンスを読み出すステップと、
各々が、前記可変長2進カラー・コードの1つのビットを表わす、1つ以上のエンコードされたビット・プレーンをデコードするステップと、
前記圧縮されたカラー画像の各ピクセルに対して、前記可変長2進カラー・コードを決定するステップと、
各ピクセルに対する前記可変長2進カラー・コードを、連結するカラーに置き換えるステップと、を有する圧縮された画像の伸張のための方法。
【請求項２２】
前記エンコードされたビット・プレーンをデコードするステップが、各ピクセルに対して、
前記エンコードされたビット・プレーンの1つから1つのビット値をデコードするステップと、
前記ビット値が、2進カラー値を決めれば、それ以降のビット・プレーンを無視するステップ、そうでなければ、前記デコードされたビット値が、2進カラー・コードを決めるまで、または、最終的な、エンコードされたビット・プレーンに到達するまで、それ以降のビット・プレーンからビット値をデコードするステップ、を有する請求項21に記載の方法。
【請求項２３】
各ピクセルに対する前記可変長2進カラー・コードが、そのピクセル位置に対応する、1つ以上のエンコードされたビット・プレーンから取られたビット位置、および、0以上のエンコードされなかったビット・プレーンから取られたビット位置を組み合わせることによって決定される請求項21に記載の方法。
【請求項２４】
前記エンコードされたビット・プレーンをデコードするステップは、テンプレートが、現在デコードされているピクセルの近傍のピクセルのセットを定めるために用いられる、エントロピ・デコーディングおよびコンテキスト・モデリングを行うステップであって、前記テンプレートが、前記エンコードされたビット・プレーンの全てにおける全てのピクセルに対して一定形状であるステップを有する請求項21に記載の方法。
【請求項２５】
前記テンプレートが、最初のピクセル位置から2番目のピクセル位置に移動するとき、前記2番目のピクセル位置とオーバーラップする前記最初のピクセル位置のコンテキスト値を保持することによって、コンテキスト値にインクリメンタル・フェッチを行うステップを有する請求項24に記載の方法。
【請求項２６】
前記ビット・プレーンをデコードするステップ、および、各ピクセルに対して前記可変長2進カラー・コードを決定するステップは、各ピクセルに対して、そのピクセルに対するデコードされたビット・プレーンのセットが、あらかじめ定められたビット順に、単一のロケーションに記憶されるピクセル・アレイを形成するステップを有する請求項21に記載の方法。
【請求項２７】
圧縮されたカラー画像を伸張するように構成された画像デコーダであって、
可変長2進カラー・コードのセットにしたがって、伸張される画像の各ピクセルにカラーを割り当てるように構成されたカラー・デコーディング・ユニットと、
複数のビット・プレーンから前記2進カラー・コードを作成するためのビット・プレーン・アキュムレータと、
圧縮された画像からのエンコードされたビット・プレーンのセットをデコードして、再形成するためのビット・プレーン・デコーディング・ユニットと、を有する画像デコーダ。
【請求項２８】
圧縮されたカラー画像を記憶するための記憶装置と、
前記圧縮されたカラー画像を伸張して、伸張されたカラー画像を形成するための画像デコーダであって、請求項27に記載のように構成されている画像デコーダと、
前記伸張されたカラー画像を表示するためのカラーディスプレイと、を有する画像ディスプレイデバイス。
【請求項２９】
前記デバイスが、セルラ電話通信デバイスである請求項28に記載の画像ディスプレイデバイス。
【請求項３０】
請求項20に記載の画像エンコーダと、
請求項27に記載の画像デコーダと、を有する画像圧縮システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、カラー画像の、圧縮されたカラー画像への圧縮のための方法および装置、および、カラー画像の伸張のための方法および装置に関するものである。
【背景技術】
【０００２】
画像は、ピクセルの二次元アレイを用いて、デジタル化された形式で表わされる。ピクセル・アレイのサイズは、およそ16 x 16ピクセルを持つ、非常に単純な文字画像またはアイコン画像から、1024 x 1024（または、それ以上の）ピクセルを持つ大きく詳細な画像まで、さまざまである。白黒のような2つの明暗度(color shade)だけしか持たない2階調（バイレベル）の画像においては、各ピクセルを、単一の2進値で表わすことができる。他方、カラー画像は、望みのカラー範囲を表わすために、ピクセル当たり、8ビットまたは24ビットさえ必要とし、したがって、2階調の画像よりも、ずっと多くのデータを含んでいる。効率的なデータ伝送およびデータ記憶のために、カラー画像を圧縮することが、強く望まれている。
【０００３】
種々さまざまの画像圧縮技術が、提案されており、それらの大部分は、ストリーム指向である。それらのストリーム指向の技術は、画像が、相対的に大きくて複雑なところでは、一般に効率的であるが、単一の単純なアイコン画像または文字画像に単独に適用したときには、一般に効率的ではない。また、伸張が、相対的に高価なリソースを必要とし勝ちである。
【０００４】
カラー画像は、種々さまざまの環境で利用される。1つの新生分野は、カラーLCDディスプレイ画面のようなカラーディスプレイデバイスを持つ、セルラ電話のような携帯通信デバイスに関するものである。このタイプのデバイスでは、システム・リソース、特に、ROM、RAM、および、コンピューティング・パワーのようなリソースは、抑制される。第1に、デバイスの物理的サイズを最小化することが、望まれる。第2に、デバイスの部品のコストを最小化することが、望まれる。第3に、電力消費を最少化することが、望まれる。第4に、時間抑制に導くように、画像を相対的に高速に表示することが、一般に望ましい。したがって、システム・リソースが抑制されている環境に適用可能な画像圧縮および伸張のための方法および装置が必要とされる。特に、小型で、高速で、最小限のメモリリソースしか用いず、かつ、コンピューティング・パワー的に安価であるデコーダによって伸張することができる圧縮された画像を提供することが望まれる。
【０００５】
特許文献１は、任意選択にビット・プレーンのセットが後続する、カラープレーンのセットを生成する、カラー画像のためのデータ圧縮システムを開示している。各カラープレーンおよびビット・プレーンは、2諧調画像における単一のビット・プレーンと同様の、1ビット2進値の二次元アレイであり、それは、エンコードするのに効率的である。しかしながら、このカラープレーンおよびビット・プレーンのセットは、画像の最適圧縮を提供せず、また、伸張は、依然として、リソース集約的である。
【０００６】
【特許文献１】米国特許第5,659,631号明細書
【発明の開示】
【課題を解決するための手段】
【０００７】
本発明の1つの目的は、上に言及されたものであれ、それ以外のものであれ、従来技術の問題に取り組む、カラー画像の圧縮および伸張のための方法および装置を提供することである。本発明の少なくとも好適な実施例の1つの目的は、伸張が、システム・リソースが抑制されている環境に適するものになるように、カラー画像の圧縮に取り組み、そして、そのような環境において伸張に取り組むことである。もう1つの好適な目標は、単純なアイコン画像または文字画像の効率的な画像圧縮および伸張を提供することである。
【０００８】
本発明の第1の態様によれば、複数のビット・プレーンを作成するステップであって、各ビット・プレーンが、2進値の二次元アレイを有するステップと、前記複数のビット・プレーンをエンコードするステップと、を有するカラー画像を圧縮する方法であって、前記カラー画像中のピクセルのカラー別に2進カラー・コードのセットを形成するステップであって、前記2進カラー・コードが、可変長であるステップと、
カラー画像に適用された前記可変長2進カラー・コードのそれぞれのビット位置を表わすために、前記複数のビット・プレーンを作成するステップと、を有することを特徴とする方法が、提供される。
【０００９】
本方法において、可変長2進カラー・コードを、圧縮されるカラー画像に使用されている各カラーに対して形成するのが好ましい。各2進カラー・コードに割り当てられる長さが、最適化される。したがって、2進カラー・コードのいくつかは、より短くなり、それらは、カラー画像において非常に頻繁に出現するようなカラーを表わすために用いるのが好都合であり、一方、2進カラー・コードの他のものは、より長く、カラー画像において、よりまれにしか出現しないようなカラーを表わすのが好都合である。
【００１０】
一実施例において、各カラーに割り付けられる前記可変長2進コードが、ハフマン・アルゴリズムによって決定され、また、カノニカル・ハフマン・アルゴリズムによって決定されるのが、さらに好ましい。したがって、可変長カラー・コードが、最適化される。特に、元画像において高い相関を持つカラーを、ビット・プレーンのセットにおいて冗長度を増加させる可変長2進カラー・コードのセットを用いてエンコードするのが、望ましい。
【００１１】
好適な一実施例において、本方法は、2進カラー・コードの最初の割り付けを形成するステップと、次いで、最も小さく圧縮された画像に帰結する最適カラー・コーディングが見つかるまで、連続的に代わりのカラー・コーディング割り付けを試みるステップとを有する。最適カラー・コーディング割り付けは、(a)前記可変長2進カラー・コードに対する最初の木形状、および、リーフへのカラーの初期割り付けを選択するステップと、最初の圧縮された画像バージョンを形成するステップと、(b)最適のリーフ割り付けが決定されるまで、リーフのペアを連続的に交換することによって代わったリーフ割り付けを評価するステップと、連続的に圧縮された画像バージョンを形成するステップと、(c)前記木形状を連続的に変更することによって代わった木形状のセットを評価するステップと、代わったリーフ割り付けを評価するステップ(b)を反復するステップと、それによって、前記セットから最適木形状および最適リーフ割り付けを選択するステップと、によって見出すのが適切である。
【００１２】
本方法は、複数の原カラー画像に用いられているカラー別に、可変長カラー・コードのセットを形成するステップを有するのが好ましい。ここにおいては、制御オーバーヘッドが、アイコンまたは特殊な文字のセットのような、類似したカラー画像のセットの各々に対して同じカラー・コーディングを用いることによって縮小される。
【００１３】
本方法は、元カラー画像を、前記元画像の相異なるエリア、または、前記元画像の相異なるカラー成分に基づくように、原画像(starting image)のセットに分割するステップを有するのが好ましい。大きな、または、非常に詳細な画像においては、各エリアに対して相異なるカラー・コーディングを生成して、より小さな圧縮された画像に導くのが、より効率的であろう。
【００１４】
可変長2進カラー・コードを用いて、カラー画像が、複数のビット・プレーンに分けられる。各ビット・プレーンが、前記2進カラー・コードの1つのビット位置を表わす、即ち、可変長2進カラー・コードが、ビット単位に分けられて、ビット・プレーンのセットを形成する。最初の作成されたビット・プレーンが、前記2進カラー・コードのセットの各々における最初のビット位置に対応する2進値を表わすのが適切である。2番目、および、それ以降のビット・プレーンが、それぞれ、前記2進カラー・コードにおける2番目、および、それ以降のビット位置を表わす。1つのビット位置が、特定の2進カラー・コードにおいて存在しない場合には（例えば、そのコードが、調べている現位置よりも短いため）、対応するビット・プレーンに空白を形成するのが好都合である。これらの空白は、2番目、または、それ以降のビット・プレーンのサイズを、相当に縮小することを可能にする。
【００１５】
ビット・プレーンは、如何なる適切なエンコーディング・スキームによってもエンコードされる。前記ビット・プレーンをエンコードするステップが、コンテキスト・モデリングおよびエントロピ・エンコーディングを行うステップを有するのが好ましい。コンテキスト・モデリングは、エンコードされたビットのストリームを生成するために、あらかじめ定められたエンコーディング深度にしたがって、ビット・プレーンのセットのサブセットに適用するのが好ましい。それ以降のビット・プレーンは、エンコードされず、そして、それらのエンコードされなかったビット・プレーンは、エンコードされなかったビットのストリームを形成する。他の1つの好ましい実施例において、ビット・プレーンのセットが、2つ以上のグループに分配され、相異なるエンコーディング・スキームが、各グループに適用される。例えば、より小さなテンプレートを用いた、より簡単なコンテキスト・モデリングステップが、2番目のグループに適用され、そして、3番目のグループには、エンコーディングが、適用されない。それらのグループは、各々、エンコーディング深度によって定めることができ、それ以降の各グループ中のビット・プレーンの最大数を決定する。
【００１６】
本発明は、さらに、本明細書において定められる方法によって生成される、圧縮されたカラー画像信号に及ぶ。
【００１７】
本発明の第2の態様によれば、可変長2進カラー・コードと、圧縮される元カラー画像において使用されているカラーとを連結させるように構成されたカラー・コーディング・ユニットと、各々が、前記可変長2進カラー・コードの1つのビットを表わすビット・プレーンのセットを作成するためのビット・プレーン・ジェネレータと、前記作成されたビット・プレーンのセットをエンコードして、圧縮された画像を形成するためのビット・プレーン・エンコーディング・ユニットと、を有するカラー画像を圧縮するための画像エンコーダが、提供される。
【００１８】
本発明の第3の態様によれば、可変長2進カラー・コードと、圧縮された画像のカラーとの連結を表わすカラー・コーディング・レファレンスを読み出すステップと、各々が、前記可変長2進カラー・コードの1つのビットを表わす、1つ以上のエンコードされたビット・プレーンをデコードするステップと、前記圧縮されたカラー画像の各ピクセルに対して、前記可変長2進カラー・コードを決定するステップと、各ピクセルに対する前記可変長2進カラー・コードを、連結するカラーに置き換えるステップと、を有する圧縮された画像の伸張のための方法が、提供される。
【００１９】
前記エンコードされたビット・プレーンをデコードするステップが、各ピクセルに対して、前記エンコードされたビット・プレーンの1つからビット値をデコードするステップと、前記ビット値が、2進カラー値を決めれば、それ以降のビット・プレーンを無視するステップ、そうでなければ、前記デコードされたビット値が、2進カラー・コードを決めるまで、または、最終的な、エンコードされたビット・プレーンに到達するまで、それ以降のビット・プレーンからビット値をデコードするステップ、を有するのが好ましい。
【００２０】
各ピクセルに対する前記可変長2進カラー・コードが、そのピクセル位置に対応する、1つ以上のエンコードされたビット・プレーンから取られたビット位置、および、0以上のエンコードされなかったビット・プレーンから取られたビット位置を組み合わせることによって決定されるのが好ましい。
【００２１】
前記エンコードされたビット・プレーンをデコードするステップは、テンプレートが、現在デコードされているピクセルの近傍のピクセルのセットを定めるために用いられる、エントロピ・デコーディングおよびコンテキスト・モデリングを行うステップであって、前記テンプレートが、前記エンコードされたビット・プレーンの全てにおける全てのピクセルに対して一定形状であるステップを有するのが好ましい。
【００２２】
前記コンテキスト・モデリングは、前記テンプレートが、最初のピクセル位置(P1)から2番目のピクセル位置(P2)に移動するとき、前記2番目のピクセル位置とオーバーラップする前記最初のピクセル位置のコンテキスト値を保持することによって、コンテキスト値にインクリメンタル・フェッチを行うステップを有するのが好ましい。
【００２３】
前記ビット・プレーンをデコードするステップ、および、各ピクセルに対して前記可変長2進カラー・コードを決定するステップは、各ピクセルに対して、そのピクセルに対するビット・プレーンのセットが、下り（または、上り）ビット順に、単一のバイト（または、他の長さのメモリ・ロケーション）に記憶されるバイトアレイを形成するステップを有するのが好ましい。
【００２４】
本発明の第4の態様によれば、圧縮されたカラー画像を伸張するように構成された画像デコーダであって、可変長2進カラー・コードのセットにしたがって、伸張される画像の各ピクセルにカラーを割り当てるように構成されたカラー・デコーディング・ユニットと、複数のビット・プレーンから前記2進カラー・コードを作成するためのビット・プレーン・アキュムレータと、圧縮された画像からのエンコードされたビット・プレーンのセットをデコードして、再形成するためのビット・プレーン・デコーディング・ユニットと、を有する画像デコーダが、提供される。
【００２５】
本発明は、さらに、本画像デコーダ、および／または、本画像エンコーダを組み込んでいる装置に及ぶ。それらの装置には、テレビジョンのようなディスプレイ装置、ビデオカッセトレコーダまたはデジタル・ビデオ・ディスク・プレーヤのようなメディア再生デバイス、プリンタ、スキャナ、カメラ、または、ビデオカメラのような画像処理システム、パームトップ・コンピュータのような汎用のコンピューティング・デバイス、または、セルラ電話のような電気通信装置が、含まれるが、それらに限定されるものではない。このリストは、網羅的なものではなく、本発明は、種々さまざまの実際の装置に適用可能である。本発明は、装置のシステム・リソースが制約されているところに、特に適用可能である。
【発明を実施するための最良の形態】
【００２６】
本発明のよりよい理解のために、また、その実施例が、いかに実行されるかを示すために、ここで、付随するダイアグラマティックな図面が、例証として、参照される。
【００２７】
図1は、カラー画像の圧縮のための好適な一装置、および、カラー画像の伸張のための好適な一装置の線図的なブロックダイアグラムである。元画像1が、画像エンコーダ10によって圧縮されて、圧縮された画像2が、形成される。圧縮された画像2は、望みにしたがって、記憶されるか、または、伝送される。その後、圧縮された画像2が、画像デコーダ20によって伸張されて、伸張された画像3が、形成される。ここで、伸張された画像3が、元画像1を忠実に復元すること、即ち、圧縮および伸張が、無損失であることが望ましい。
【００２８】
画像エンコーダ10は、元画像1に利用されているカラーのセットに連結する2進カラー・コードを形成するように構成されたカラー・コーディング・ユニット12、その2進カラー・コードからビット・プレーンのセットを作成するためのビット・プレーン・ジェネレータ14、および、作成されたビット・プレーンをエンコードして、圧縮された画像2を形成するためのコンテキスト・モデラ16およびビット・プレーン・エンコーダ18を有するビット・プレーン・エンコーディング・ユニットを有する。
【００２９】
画像デコーダ20は、2進カラー・コードのセットから伸張された画像3の1ピクセルごとにカラー値を割り当てるように構成されたカラー・デコーディング・ユニット22、ビット・プレーンのセットから、2進カラー・コードを作成するためのビット・プレーン・アキュムレータ24、および、圧縮された画像2からのビット・プレーンのセットをデコードするためのコンテキスト・モデラ26およびビット・プレーン・デコーダ28を有するビット・プレーン・デコーディング・ユニットを有する。
【００３０】
単一のデバイスを、圧縮機能と伸張機能との両方を実行するように適合させることが可能であるが、好適な実施例においては、画像エンコーダ10と画像デコーダ20とは、物理的に別個のデバイスプラットフォームで提供される。好適な一例として、画像エンコーダ10は、汎用のコンピューティング・プラットフォームで提供するのが好都合であり、一方、画像デコーダ20は、セルラ電気通信デバイスに埋め込むのが好都合である。画像デコーダ20は、メモリ記憶装置（図示せず）などから、圧縮された画像2を受け取り、そして、伸張された画像3を、256色LCDディスプレイなどのディスプレイ25に渡すように構成されている。ここで、画像デコーダ20に利用可能な時間、メモリ、および、コンピューティング・パワーのようなシステム・リソースを、その画像デコーダが動作するデバイスの特質にしたがって抑えるのが、高く評価されることである。
【００３１】
図2は、カラー画像の圧縮のための好適な一方法の線図的な大要である。ここで、画像エンコーダ10の機能および動作が、図2の方法を参照して、より詳細に記述される。
【００３２】
2諧調画像の圧縮および伸張を排除するものではないが、元カラー画像1には、3色以上が含まれていると仮定する。2諧調画像とカラー画像との両方を、同じ装置および方法によって処理してもよいが、その場合には、2諧調画像は、カラー画像の単純な形式として扱われる。元画像中の各ピクセルのカラー（または、明暗度）は、そのピクセルのカラーの明示的な表現によって、または、カラーのフルパレット（例えば、8ビットカラーまたは24ビットカラー）を参照して定められる。各ピクセルのカラーを計算するか、または、別のやり方で決定することを可能にする如何なる適切なフォーマットでも、元画像1を受け取ることができる。
【００３３】
予備段階として、既知のカラーLCDディスプレイ25が生成できる256色のパレットのように、既知のディスプレイ装置によって表示することができる、あらかじめ定められたパレットに、元画像1のカラーを制限することが必要であろう。元カラー画像のカラーが、ディスプレイ・パレットで利用可能でないときには、最も一致に近いものを選ぶのが好都合である。そのように、原カラー画像を圧縮する準備が形成される。
【００３４】
図2において、ステップ201は、原カラー画像1で用いられるカラーのセットを決定するステップを有する。ステップ201は、さらに、各カラーの頻度（ピクセルエリア）を決定するステップを有する。実際には、如何なる1つの画像において用いられるカラーのセットでも、256色のディスプレイ・パレットからのわずか5または10または20色にすぎないような、利用可能なカラーパレットの小さなサブセットにすぎない。したがって、特定のカラー画像において用いられているカラーを基にして画像圧縮を実行し、そして、その用いられているカラーの各々について個別の符号を作るのが好都合である。
【００３５】
ステップ202は、原カラー画像において用いられているカラーのセットを表わす可変長2進カラー・コードのセットを形成するステップを有する。各カラーに割り当てられる2進カラー・コードの長さは、カラー画像のエントロピを最適化するように選択される。ステップ201および202は、カラー・コーディング・ユニット12によって実行するのが好都合である。
【００３６】
この画像のために形成された可変長2進カラー・コードのセットを知っておくことが、後で、伸張中に必要になる。カラー・コード構造、および、それに対応する実際のカラーの規定が、カラー・コーディング・レファレンス31として、圧縮されたカラー画像3の初めに記憶される。
【００３７】
ステップ203は、ビット・プレーン・ジェネレータ14において、各ピクセルの可変長2進カラー・コードから導出される複数のビット・プレーンを作成するステップを有する。フルビット・プレーンを、可変長2進カラー・コードの全てに対して共通である、少なくとも最初のビット位置に対して導出するのが好都合である。2番目、および、それ以降のビット・プレーンは、より短い可変長2進カラー・コードが、そのビット位置に値を持っていない空白を含んでいてもよい。より長い2進カラー・コードが、カラー画像の、よりまれにしか出現しないカラーに対して用いられ勝ちであるから、したがって、連続するビット・プレーンは、次第に、より小さくなり勝ちである。
【００３８】
ステップ204は、作成されたビット・プレーンをエンコードするステップを有する。要約すると、ステップ204は、ビット・プレーンに、コンテキスト・モデラ16でコンテキスト・モデリングを行うステップと、その後、エントロピ・エンコーダ18でエントロピ・エンコーディングを行うステップとを有する。ビット・プレーンのセットを効率的にエンコードするための技術は、既知であり、本明細書においては、詳細に記述しない。一例として、“Compression of Black and White Images with Arithmetic Coding（算術符号化による白黒画像の圧縮）”, G.L. Langdon and J. Rissanen, IEEE Transactions on Communications, Vol. 29, No 6, pp858-867を参照されたい。この参照文献は、静的コンテキスト・モデリングと適応的コンテキスト・モデリングとのどちらかと、算術符号化とを用いて、2諧調（白黒）画像のビット・プレーンをエンコードするための技術について検討している。その参照技術は、ビット・プレーンのセットの各々に対して適切に適用されて、圧縮された画像2のためにエンコードされたデータを生成する。ビット・プレーンのセットにコンテキスト・モデリングを行う、また、エントロピ・エンコーディングを行うための他の多くのオプションがある。
【００３９】
本発明の画像圧縮方法および装置を、より詳細に例示するために、図3〜7に示されるような簡単化した一例を参照する。
【００４０】
図3は、8 x 8ピクセルのアイコンの形状をした簡単なカラー画像を示している。より実際的な一実施例において、カラー画像は、およそ15 x 15または16 x 16または28 x 28ピクセルのピクセル・アレイによって表わされるアイコン、または、中国語文字のような特殊な文字である。ピクセル・アレイは、如何なるサイズであってもよく、また、正方形である必要もない。
【００４１】
本例において、各ピクセルは、8ビットカラー値によって表わされる256色の1つを持っている。図3の元カラー画像は、あらかじめ定められたディスプレイ・パレットからの6色を表わす、図4に示されるような6つの記号A, I, Q, U, X, Yによって表わすことができる6色（または、グレイ・スケール色調）を持っている。
【００４２】
図5は、このカラー画像例内の各カラーの出現頻度を示すテーブルである。この出現頻度を、各カラーに対する効率的な2進カラー・コードを決定するために用いるのが好都合である。ここで、カラーQおよびXが、最も頻繁に出現し、したがって、カラーA, Y, I, Uよりも短い長さのコードを与えられることが、理解される。この例においては、カラーQおよびXに対する2進カラー・コードは、2ビット長であり、一方、4つの他のカラーA, Y, I , Uに対するコードは、3ビット長である。
【００４３】
図6は、図5の2進カラー・コードの2進木表現である。各深度におけるリーフ（葉）が全て、可能な限り、左側に置かれているから、これは、カノニカル木である。この2進木表現を用いて、各深度におけるリーフの数、および、それらのリーフによって定められているカラーを記述することによって、カラー・コーディング・レファレンス31が、形成される。
【００４４】
図7は、図3および4のカラー画像例に適用された、図5に示されている可変長2進カラー・コードから導出された3つのビット・プレーン51, 52, 53を示している。これらの3つのビット・プレーン51, 52, 53に、コンテキスト・モデリングおよびエントロピ・エンコーディングを適用して、圧縮された画像2が、形成される。
【００４５】
最初のビット・プレーン51は、2進カラー・コードの最初の（左端の）ビット位置に対応する。この最初のビット位置は、可変長2進カラー・コードの全てによって共有され、したがって、最初のビット・プレーン51は、各1つのビットが、カラー画像の各ピクセルに対応したフルビット・プレーンである。
【００４６】
2番目のビット・プレーン52は、2進カラー・コードの2番目のビット位置から導出される。2進カラー・コードが全て、2番目のビット位置を含んでいるから、ここでも、フルビット・プレーンが、形成される。
【００４７】
3番目のビット・プレーン53は、2進カラー・コードの3番目のビット位置を表わす。ここでは、カラーQおよびXに対するコードが、このビット位置よりも短く、したがって、3番目のビット・プレーン53は、カラーQおよびXに対応するピクセル位置に、ドットで表示された空白を含んでいる。デコーディング中に、最初と2番目のビット・プレーン51, 52、および、一般的には、その前にデコードされたビット・プレーンからの情報を用いて、それらの空白を復元するから、それらの空白をエンコードする必要はない。したがって、3番目のビット・プレーン53は、カラー画像の完全なアレイよりも少ないデータ位置しか含んでいないパーシャル・ビット・プレーンである。この例において、2進カラー・コードの最大長は、3ビットであり、したがって、3つのビット・プレーン51, 52, 53が、作成される。一般に、各1つのビット・プレーンが、2進カラー・コードのセットのうちの最長のものの各ビット位置に対して作成され、そして、この最大長よりも短い2進カラー・コードに対しては、空白が、それらのビット・プレーンの少なくとも1つに現れる。
【００４８】
第1の好適な実施例において、各カラーに対する可変長2進コードは、カラー画像内の各カラーのエリアサイズ（即ち、画像内のピクセルの総数に対する割合として、そのカラーを持っているピクセルの数）にしたがって、ハフマン・アルゴリズムによって、そして、より好ましくは、カノニカル・ハフマン・アルゴリズムによって決定される。その結果として、画像中で頻繁に用いられるカラーは、相対的に短い長さのコードを与えられ、一方、相対的にまれにしか用いられないカラーは、より長い長さのコードを与えられる。
【００４９】
図7に示されているビット・プレーン例は、2進カラー・コードの最適セットを選ぶことの利点を例示している。最初の2つのビット・プレーン51, 52は、各々、好都合な形状をした「1」と「0」からなる長方形を含んでおり、これらのパターンは、一般に、各ビット・プレーンの効率的なコーディングを可能にする。この例は、また、ハフマン・アルゴリズムを用いて最適に長さを変えるエンコーディングを適用するということは、各カラーのエリアサイズが、エンコーディング効率に比例するということを仮定していることを例示している。カラーIおよびUの市松模様によって例示されているように、これは、正しくない場合もある。
【００５０】
したがって、第2の実施例において、極めて小さく、または、より効率的に圧縮された画像が達成されるように、各カラーを表わすために用いられる可変長2進カラー・コードを最適に選択することが、望ましい。この第2の実施例では、ステップ202は、最適カラー・コーディングが見つかるまで、連続的に代わりのカラー・コーディング割り付けを試みることによって、最初の単純な2進カラー・コードの割り付けを改善するステップを有する。
【００５１】
図8は、この第2の実施例において用いられるような、画像エンコーダ10において、可変長2進カラー・コードの割り付けを最適化するための好適な一方法の線図的な大要である。
【００５２】
ステップ801において、上で検討したようなカノニカル・ハフマン・アルゴリズム、または、他の方法を適用するなどによって、任意の木形状が、決定され、そして、リーフへの初期カラー割り付けが、なされる。圧縮された画像の最初のバージョンが、その最初の割り付けを用いて形成される。
【００５３】
ステップ802において、リーフのペアが、交換され、そして、エンコーディングが、反復される。交換されるリーフのペアは、木の同じレベルにあることもできるし、異なるレベルにあることもできる。結果として生じた圧縮された画像が、より小さくなれば、その新しい割り付けが、保持され、そうでなければ、以前の割り付けが、戻される。ステップ802は、それ以上の改善を、この木形状に対してはなすことができなくなるまで、各リーフのペアに対して反復される。
【００５４】
ステップ803は、木形状を変更するステップと、その後、その新しい木形状に対してステップ802を反復するステップとを有する。ステップ803は、あらかじめ定められた形状のセットを通して、木形状をモーフィングするステップを有するのが好ましい。図5の出現頻度テーブルを参照して、全ての出現カウントの和（即ち、ピクセルの総数）をtとし、pを、pminからpmaxまでのあらかじめ定められた範囲（例えば、0と10との間）で可変な整数とする。モデファイア
2005516554.tif 000003
が、各出現カウントに加えられて、変更された出現カウントを与える。
【００５５】
2005516554.tif 000004
の場合には、ノーマル・ハフマン木が、決定される。pがpmaxに向かって増加していくと、変更された出現カウントは、カラー間の頻度差を一様化し、木形状は、フル2進木に向かって変化していく。各木形状が、順番に考察され、そして、最も小さく圧縮された画像に帰着した木形状が、選択される。このように、最適の木形状および割り付けが、考察中の画像（単数または複数の）に特有に決定される。
【００５６】
グレイ・コードの複数のセットを用いて、2進カラー・コードを形成することが好ましい。グレイ・コードの各1セットが、可変長2進カラー・コードの各長さに対して決定される。例えば、グレイ・コードの最初のセットが、2ビット長の2進カラー・コードに対して決定され、また、グレイ・コードの2番目のセットが、3ビット長の2進カラー・コードに対して決定される、等である。グレイ・コードは、画像のカラーが、その画像がグレイ・スケール画像であるように、関連づけられているときに、特に、有用である。グレイ・コードは、隣り合う整数が、ただ1つのビット位置でしか異ならないグレイ・コード表現を持つような順番の長さNの2進記号列としての整数列
2005516554.tif 000005
における各数を表わす。したがって、整数列中を進むと、それは、一度にただ1つのビットしか裏返らないことを要求する。
【００５７】
元カラー画像1が、多くのカラーを含んでいる場合、例えば、例えば、500の異なるカラーを用いた24ビットカラー画像である場合には、その元画像を、原画像のセットに分離するのが好ましい。元画像のR, G, Bカラー成分を、個別のグレイ・スケール画像として分離するのが、好都合である。その後、R, G, Bグレイ・スケール画像は、本明細書で検討される方法を用いて、即ち、R画像に対して、次に、G画像に対して、次に、B画像に対してエンコードされたビット・プレーンを形成して、個別に圧縮され、そして、それらは、圧縮された画像2として、連続して順番に供給される。デコーディング中に、分離されたR, G, Bカラー成分が、各々、伸張され、次いで、再び結合される。
【００５８】
他のオプションとして、原画像のセットが、非常に大きい、または、非常に詳細な元画像1の相異なるエリア部分を、各々、表わすように生成される。その後、より小さくなった、または、より単純になった原画像のセットの各々が、個別に、本明細書で検討される通りに圧縮される。
【００５９】
特殊な文字またはアイコンのセットのように、非常に単純な原画像が、圧縮されることになっている場合には、カラー・コーディング・レファレンス31のようなオーバーヘッドを、複数の画像で共有するのが好ましい。ここでは、カラー・コーディング・レファレンス31は、原画像のセットに対して決定され、セット中の各画像に適用される。
【００６０】
図9は、圧縮された画像2を生成するためのエンコーダ10におけるデータ・フローの線図的な表現である。伸張中のデータ・フローは、図9のフローの逆である。
【００６１】
上述のように、可変長カラー・コード、および、それらが表わすカラーの割り付けは、カラー・コーディング・レファレンス31として記憶される。可変長2進カラー・コードを用いて、複数のビット・プレーンが、作成される。その4つのビット・プレーン51, 52, 53, 54が、図9に示されている。
【００６２】
ビット・プレーンの少なくともいくつかが、この場合には、ビット・プレーン51, 52, 53が、コンテキスト・モデリングおよびエントロピ・エンコーディングなどによってエンコードされて、エンコードされたビットストリーム32を形成する。エンコーディングの相異なる種々のレベルを、ビット・プレーンの相異なる種々のグループに適用してもよい。簡単な一実施例において、ビット・プレーンの最初のグループが、エンコードされ、一方、2番目のグループは、エンコードされないままか、または、より簡単なエンコーディングを受ける。最初のn個のビット・プレーンが、最初のグループを形成し、
2005516554.tif 000006
番目の、および、それ以降のビット・プレーンが、2番目のグループを形成する。ここで、nは、あらかじめ定められた整数である。それ以上のグループ、および、エンコーディングの変形を、同様に定めてもよい。
【００６３】
コンテキスト・モデラ16によって実行されるコンテキスト・モデリングは、現在コード化されているピクセルの近傍の、少なくとも1つのピクセルを参照するコンテキスト（このビット・プレーン中の、または、任意選択に他のビット・プレーン中の、ピクセルを含むコンテキスト）を利用する。コンテキストは、現在エンコードされているピクセルの近傍のピクセルのセットであって、あらかじめ定められた形状を持つセットを選択するテンプレートによって導出するのが好ましい。テンプレートを適用することによって戻される2進値は、現在エンコードされているピクセルが、「1」または「0」の2進値を持つ確率を予測するテーブルのインデックスを形成するのが好都合である。この予測が、現在エンコードされているピクセルの実際の値と比較され、そして、差が、計算される。差が、0である（即ち、予測が正しかった）場合には、このビット・プレーンにおいて現在エンコードされているピクセル位置が、「0」の値を与えられ、そうでなければ（即ち、予測が正しくない場合には）、そのピクセル位置が、「1」の値を与えられる。このコンテキスト・モデリングは、多くの0と、わずかの1を持つビット・プレーンを形成することによって、各ビット・プレーンのエントロピを相当に減少させる。したがって、エントロピ・エンコーディングの効率が、改善される。エントロピ・エンコーダ18は、エントロピ・エンコーディングを実行するために、複数のカノニカル・ハフマンコーダを適切に有する。コンテキスト値は、また、このピクセルのために用いられるべきコーダを決定する。本発明の実際的な実施例においては、コンテキスト・モデリングは、まれに「1」を持つ、「0」の長いランを生成する。したがって、このエントロピ・エンコーディングは、「0」のランの長さを表わすランレングス(RL)コーディングであるのが好都合である。
【００６４】
ビット・プレーン54のような、それ以降のビット・プレーンは、多くの空白を含み勝ちであり、コンテキスト・モデリングは、データ値のコヒーレンスをあまり改善しない。エンコードされるべきビット・プレーンの数は、あらかじめ定められた深度までに設定される。コンテキスト・モデリングは、指定された深度まで適用される。それ以降のビット・プレーンは、コンテキスト・モデリングが行われず、即ち、エンコードされず、0以上のエンコードされなかったビット・プレーンが、エンコードされなかった記号のストリーム33として、そのまま記憶される。
【００６５】
1つのオプションとして、ビット・プレーン51, 52, 53が、各々、個別に順番にエンコードされる。しかしながら、好適な実施例において、記号のストリームが、各ビット・プレーンの内部から、および／または、別々のビット・プレーンから、インターリーブされる。これは、デコーダをシミュレートすることによって行われる。デコーダが、エンコードされたビット・プレーンストリームのランレングス・デコーディングのために相異なる種々のハフマン・デコーダをコールするであろう順番が、別々のストリームをインターリーブするために用いられる。
【００６６】
図10は、圧縮された画像2の伸張のための好適な一方法の大要である。
【００６７】
ステップ101は、可変長2進カラー・コードと、それに連結するカラーとの割り付けを表わす、圧縮されたカラー画像のカラー・コーディング・レファレンス31を読み出すステップを有する。
【００６８】
ステップ102は、エントロピデコーダ28およびコンテキスト・モデラ26におけるエントロピ・デコーディングおよびコンテキスト・モデリングなどによって、複数のビット・プレーンをデコードするステップを有する。最初のピクセルに対して、最初のビット・プレーンの最初のビットが、復元される。このビットが、既に、1つのカラーをエンコードしているものであれば、即ち、そのカラーは、単一ビット可変長2進カラー・コードでエンコードされたものであるから、その最初のピクセルに対して、1つのカラーを決定することができ、そして、それ以降のビット・プレーンは、現在デコードされているピクセルの位置に空白を含むから、それ以上のビット・プレーンは、無視される。他方、最初のビット・プレーンから取られたビットが、1つのカラーをエンコードしているものでない場合には、さらに1つ以上のエンコードされたビット・プレーンのビットが、それらのビットが1つのカラーをエンコードしているものになるまで、または、最終的なエンコード深度に達するまで、復元される。その後、次のピクセルが、そのピクセルのカラーに対する2進カラー・コードにビットを与えている、適切な1つ以上のエンコードされたビット・プレーンを参照して、順番にデコードされる。
【００６９】
ピクセルの2進カラー・コードのビット値は、その後のピクセルのコンテキストとして用いられるから、デコードされたビット値を、アレイ中の全てのピクセルがデコードされてしまうまで保持するのが好ましい。
【００７０】
ステップ103において、各ピクセルのカラーが、復元される。ここで、2進カラー・コードが、そのピクセル位置に対応する、1つ以上のデコードされたビット・プレーンから取られたビット位置、および、任意のエンコードされなかったビット・プレーンから取られたビット位置を組み合わせることによって得られる。最初のピクセルに対して、デコードされたビット・プレーンが、そのピクセルの完全な2進カラー・コードを備えていたら、その2進カラー・コードが、決定される。より多くのビットが必要な場合には、それらのビットは、そのピクセルに対する2進カラー・コードが完全になるまで、エンコードされなかったビット・プレーンのストリームから呼び出される。
【００７１】
ステップ104において、各ピクセルの2進カラー・コードが、それに連結する元のカラー値に置き換えられる。そうすると、そのピクセル・アレイは、伸張された画像3として、デコーダの出力を形成する。
【００７２】
コンテキスト・モデリング中に、テンプレートが、現在デコードされているピクセルの近傍のピクセルのセットを定めるために用いられる。テンプレートは、エンコードされたビット・プレーンの全てにおける全てのピクセルに対して、一定形状であるのが理想である。この一定形状のテンプレートは、デコーダを単純化することを可能にする。図11は、この場合、現在ピクセルP1の近傍の13個のピクセル0〜12をおおっている、テンプレート60の一例を示している。如何なる適切なサイズおよび形状のテンプレートでも、利用することができる。テンプレートの一部が、ピクセル・アレイの外側になってしまったところでは、慣例として、「0」の値が、用いられる。
【００７３】
図12は、最初の位置および2番目の位置におけるテンプレート60の例を示している。テンプレートが、新しい2番目のピクセル位置P2を調べるために、最初のピクセル位置P1から移動するとき、新しい位置の新しいコンテキスト値だけのインクリメンタル・フェッチ（インクリメンタルな呼び出し）が、実行される。この場合、近くのピクセル0, 3, 8, 12に対するコンテキスト値しか、フェッチングを必要としない。最初のピクセル位置と2番目のピクセル位置との間でオーバーラップする、他のコンテキスト値は、保持されて、2番目の位置でも再び用いられる。この例においては、前に決定されたピクセルP1が、ピクセルP2に対するテンプレートにおいて位置0を形成する。このインクリメンタル・フェッチを行うステップは、各ピクセル位置においてコンテキスト・モデラによって必要とされる新しいデータの量を相当減らす。
【００７４】
図13は、デコーディング中に用いられる、1つの好ましいデータ記憶構成を示している。ビット・プレーンの復元のために、それ以降にデコーダからの出力ピクセル・アレイを形成する、デコードされたビット・プレーン・アレイが、形成される。各ピクセルにおいて、最初にデコードされたビット・プレーンのビット51が、そのピクセルに対するアレイ・ロケーション（アレイ記憶位置）の最初のビット位置に記憶される。それ以降にデコードされたビット・プレーンが、同じロケーションの、それ以降のビット位置に記憶される。即ち、各ピクセルに対して、そのピクセルに対するビット・プレーンのセットが、下り（または、上り）ビット順に、単一のロケーションに記憶される。したがって、単一のアレイ・ロケーションの読み出しが、ビット・プレーンの完全なセットからのデータを決定することを可能にし、これによって、デコーダの速度が改善し、そのメモリ・アクセスが減少する。一例として、図13は、各ロケーションが、8ビットバイトであるアレイを示しており、8個のビット・プレーンまで記憶することを可能にする。望み通りに、他の長さのロケーションを、ビット・プレーン・アレイに用いることができる。
【００７５】
相対的に小さく、単純な単発の画像においてさえ、効率的な画像圧縮を提供する、カラー画像の圧縮のための方法および装置が、記述された。その圧縮された画像の伸張は、単純で、かつ、安価である。システム・リソースが抑制されている環境における動作に適した、カラー画像の伸張のための方法および装置が、記述された。他の特徴および利点は、前の記述から、および本発明の実行を通じて明白になる。
【００７６】
本出願に記述されているデコーダ実装は、現発明の範囲外にも応用可能であり、それ自体で発明と見なすことができることに注意されたい。特に、2進カラー・コードが、米国特許第5,659,631号明細書に従ってエンコードされたような圧縮された画像の場合の如く固定長である圧縮された画像をデコードするためのデコーダ実装に応用することが可能である。
【００７７】
固定長2進カラー・コードを持つ圧縮された画像が有利となるデコーディングは、以下のステップ：2進カラー・コードと、圧縮された画像のカラーとの連結を表わすカラー・コーディング・レファレンスを読み出すステップ；各々が、2進カラー・コードの1つのビットを表わす、1つ以上のエンコードされたビット・プレーンをデコードするステップ；圧縮されたカラー画像の各ピクセルに対して2進カラー・コードを決定するステップ；各ピクセルに対する2進カラー・コードを、それに連結するカラーに置き換えるステップを有する。ここで、そのデコードするステップは、各ピクセルに対して、以下のステップ：各ピクセルに対する2進カラー・コードを、そのピクセル位置に対応する、1つ以上のエンコードされたビット・プレーンから取られたビット位置、および、0以上のエンコードされなかったビット・プレーンから取られたビット位置を組み合わせることによって決定するステップを有する。そのデコードするステップは、テンプレートが、現在デコードされているピクセルの近傍のピクセルのセットを定めるために用いられる、エントロピ・デコーディングおよびコンテキスト・モデリングを行うステップを有し、そのテンプレートが、エンコードされたビット・プレーンの全てにおける全てのピクセルに対して一定形状であるのが好ましい。そのデコードするステップは、テンプレートが、最初のピクセル位置から2番目のピクセル位置に移動するとき、2番目のピクセル位置とオーバーラップする最初のピクセル位置のコンテキスト値を保持することによって、コンテキスト値に対してインクリメンタル・フェッチを行うステップを有するのが好ましい。ビット・プレーンをデコードするステップ、および、各ピクセルに対して2進カラー・コードを決定するステップは、各ピクセルに対して、そのピクセルに対するデコードされたビット・プレーンのセットが、あらかじめ定められたビット順に、単一のロケーションに記憶されるピクセル・アレイを形成するステップを有するのが好ましい。
【００７８】
上述の実施例は、本発明を制限するものではなくて、例示するものであること、および、当業者であれば、付随する請求項の範囲を逸脱することなく、多くの代替実施例を立案することができることに注意されたい。請求項において、括弧内に置かれた如何なる参照符号も、その請求項を制限するものと解釈してはならない。用語「有する」は、請求項に記載されているもの以外の、他の要素またはステップの存在を排除するものではない。本発明は、いくつかの異なる要素を有するハードウェアによって実装することもできるし、また、適切にプログラムされたコンピュータによって実装することもできる。いくつかの手段を列挙しているデバイス請求項において、それらの手段のいくつかは、1つ、かつ、同一のハードウェア品目で具象化することができる。いくつかの方策が、互いに異なる従属請求項に挙げられているという単なる事実は、これらの方策の組合せを有利に用いることができないということを指示するものではない。
【図面の簡単な説明】
【００７９】
【図１】カラー画像の圧縮および伸張のための好適な一装置の線図的なブロック図である。
【図２】カラー画像の圧縮のための好適な一方法の線図的な大要である。
【図３】カラー画像の一例を示す。
【図４】図3のカラー画像の例に割り当てられたカラー・コードを示す。
【図５】カラー画像の例内の各カラーの出現頻度を示すテーブルである。
【図６】2進カラー・コードの2進木表現の一例である。
【図７】ビット・プレーンの例を示す。
【図８】可変長2進カラー・コードの割り付けを最適化するための好適な一方法の線図的な大要である。
【図９】圧縮および伸張中のデータ・フローを示す線図的な図である。
【図１０】カラー画像の伸張のための好適な一方法の線図的な大要である。
【図１１】ビット・プレーンのコンテキスト・モデリング中に利用されるテンプレートの一例を示す。
【図１２】最初と2番目のピクセル位置間を移動したテンプレートの例を示す。
【図１３】圧縮されたカラー画像の伸張中に用いるための1つの好適なデータ記憶レイアウトを示す。
【符号の説明】
【００８０】
1  元カラー画像
2  圧縮された画像
3  伸張された画像
10  画像エンコーダ
12  カラー・コーディング・ユニット
14  ビット・プレーン・ジェネレータ
16  コンテキスト・モデラ
18  エントロピ・エンコーダ（ビット・プレーン・エンコーダ）
20  画像デコーダ
22  カラー・デコーディング・ユニット
24  ビット・プレーン・アキュムレータ
26  コンテキスト・モデラ
28  エントロピデコーダ（ビット・プレーン・デコーダ）
31  カラー・コーディング・レファレンス
32  エンコードされたビットストリーム
33  エンコードされなかった記号のストリーム
51, 52, 53, 54  ビット・プレーン
60  テンプレート
【図１】
2005516554.tif 000007
【図２】
2005516554.tif 000008
【図３】
2005516554.tif 000009
【図４】
2005516554.tif 000010
【図５】
2005516554.tif 000011
【図６】
2005516554.tif 000012
【図７】
2005516554.tif 000013
【図８】
2005516554.tif 000014
【図９】
2005516554.tif 000015
【図１０】
2005516554.tif 000016
【図１１】
2005516554.tif 000017
【図１２】
2005516554.tif 000018
【図１３】
2005516554.tif 000019
【国際調査報告】
2005516554.tif 000020
2005516554.tif 000021
2005516554.tif 000022