JPH0937271A

JPH0937271A - 画像圧縮方法

Info

Publication number: JPH0937271A
Application number: JP8185822A
Authority: JP
Inventors: Gadiel Seroussi; ガディエル・シィロウシー; Guillermo Sapiro; グイラーモ・サピロ; Weinberger Marcelo; マルセロ・ウェインバーガー
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 1995-07-18
Filing date: 1996-07-16
Publication date: 1997-02-07
Also published as: EP0755155A3; US5680129A; EP0755155A2; US5835034A

Abstract

(57)【要約】【課題】文脈決定回路および符号テーブル生成回路を備
えた無損失画像圧縮符号化器／復号化器システムを提供
する。【解決手段】符号化器が、符号化されるべきピクセルの
文脈を使用して、ピクセルの値を予測して予測誤差を決
定する。符号化器に含まれる文脈量子化器が、ピクセル
の文脈を量子化し、符号化器は、量子化文脈の各々につ
いて誤差値を通算し、この通算値を使用して、各量子化
文脈毎に文脈特有符号化テーブルを生成する。ピクセル
を符号化する時、符号化器は、該ピクセルの文脈に対応
する文脈特有符号化テーブルの中の予測誤差を検索して
その値を符号化する。画像を伸張する場合、復号化器
は、符号化の際と同じピクセルを使用して文脈を決定
し、文脈特有符号化テーブルから、符号化されたピクセ
ルに対応する誤差値を取り出し、文脈に基づいた予測値
に誤差値を加算してピクセルの実際値を決定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、一般的に画像圧縮
に関するもので、特に、文脈特有のハフマン符号を使用
し、複雑性が少ない上に情報損失のない画像圧縮を実行
する技術に関するものである。

【０００２】

【従来の技術】効率的なデータ記憶および通信のための
圧縮アルゴリズムの使用は、ほとんどのデジタル画像処
理システムにおける重要なコンポーネントとなってい
る。多くのアプリケーションにおいて、データを記憶ま
たは伝送するために必要な資源の量の減少は非常に重要
であり、従って、圧縮はイネーブリング技術（すなわち
それらアプリケーションを使用可能にさせる基本的技
術）とみなすことができる。画像圧縮アルゴリズムは、
損失のある（すなわち不可逆）方式と損失のない（すな
わち可逆的）方式に広義に類別される。損失のある方式
では、元のピクセル強度は、符号化されたビットストリ
ームから完全に復元できないが、損失のない（可逆的）
方式では、伸張される画像は元のデジタル画像と全く同
一である。

【０００３】画像が例えば特定の情報の抽出のような将
来の処理に従属するようなアプリケーションにおいて
は、一般的に後者の（無損失）方式が必要とされる。損
失のある圧縮技術のほとんどは、人が見るシステムのた
めに設計され、処理の間に必要な情報の一部を破壊する
ことがある。従って、医療分野のデジタル放射線機器か
らの画像や宇宙空間衛星からの画像は、通常、可逆的方
法で圧縮される。一般的には、高い費用で取得したため
に将来必要となるかもしれない情報を破棄するのは賢明
ではないような画像や、デジタル写真のように取得の時
点では描出される画像の所望の品質が未定であるような
アプリケーションにおいて、無損失圧縮が選択される。
加えて、細密編集または圧縮／伸張の反復が必要とされ
るアプリケーションでは、損失の反復による誤差の累積
が許容しがたいものとなるので、損失のある方式より損
失のない方式が望まれる。

【０００４】グレースケール画像は、あるビット数にデ
ジタル化された強度値の２次元アレイであるとみなされ
る。放射線機器では１２ビットが伝統的に使用されてい
るが、ほとんどのアプリケーションでは８ビットが使用
されている。次に、カラー画像は、通常、各コンポーネ
ントがグレースケール画像である（例えばＲＧＢ，ＹＵ
Ｖ、ＬＡＢのような）なんらかのカラー空間で表され
る。従って、カラー画像の圧縮に使用されるツールは、
グレースケール画像のために開発されたツールから引き
出される。本発明は、一般的に、グレースケール画像用
のツールに焦点をあてる。しかし、そのようなツールを
組み合わせてカラーの場合に適用する際には、（ＲＧＢ
表現におけるような）カラー平面の間の可能な相関を考
慮しなければならない点は留意する必要がある。

【０００５】無損失画像圧縮技術は、普通、モデル化お
よび符号化という個々に独立した２つのコンポーネント
から構成される。モデル化部分は、帰納的推論問題とし
て公式化することができ、そこでは、画像は（例えばラ
スタ走査のような）予め定められる特定の順序でピクセ
ル毎に観察される。各時間軸ｉ毎に、過去のデータｘⁱ
＝ｘ₁ｘ₂...ｘ_iを走査した後、条件付き確率分布を割り
当てることによって次のピクセルｘ_i+1に関する推論が
行なわれる。(注：ピクセル値は、２次元アレイに対応
してはいるがただ１つの添字でインデックス付けがされ
ていて、この添字は予め定められる順序における「時
間」インデックスを示す)。逐次公式化の過程で、この
ような分布ｐ( ^.｜ｘⁱ )は過去から学習され、次式(1)
のシーケンス全体に割り当てられる確率を最大にするこ
とが長期的目標である。

【０００６】

【数１】式(1)においてｘ⁰は空ストリングを示す。この方式の符
号化部分で、この確率割当ては、全符号長［−ｌｏｇＰ
（ｘⁿ）］を算出する算術符号化器によって逐次使用さ
れる。（注：上記対数の基底は２であり、以後の対数表
示においてもすべて同様である）。算術符号化は、J.Ri
ssanenおよびG.G.Langdon,Jr.両氏著の'Universal mode
ling and coding,' IEEE Trans.Inform.Theory, vol.IT
-27, pp. 1223, Jan. 1981に記載されている。ｘ_i+1を
符号化するために使用される条件付き確率はｘⁱだけに
依存しているので、過去のストリングを逐次復号する復
号機構にとって条件付き確率は役立つ。代替的方法とし
て、２回パス方式においては、条件つき分布が第１パス
で画像全体から学習され、その記述の一部がヘッダ情報
として復号機構へ送られる。この場合、全符号長はヘッ
ダの長さを含む。第２の符号化パスおよび（単一パス
の）復号も共に同じ逐次公式に従う。

【０００７】最新技術の無損失画像圧縮方式において、
確率割当ては、一般的に以下のコンポーネントに分割さ
れる。 (a)予測ステップ。使用可能な過去のシーケンスｘⁱのサ
ブストリング（すなわち部分列）ｘ_i1ｘ_i2...ｘ_ivに基
づいて、次のピクセルｘ_i+1に関して決定性値ｘ _i+ ₁が推
測される。ここでｖは予測値の順序を示す。 (b)ｘ_i+1発生の文脈の決定。再び、この文脈は、過去の
サブシーケンス（部分シーケンス）ｘ_i1ｘ_i2...ｘ_imの
関数である（ｍは整数）。 (c)x_i+1の文脈を条件として、予測残差(あるいは誤差信
号)ｅ_i+1＝ｘ_i+1−x _i+1に関する確率的モデル。

【０００８】図１は、典型的な無損失画像圧縮方式のブ
ロック図である。斜線部１０１および１０１'は、予測
および文脈モデル化が準拠する走査された過去のシーケ
ンスｘⁱを表し、一方、黒点１０３および１０３'は、現
在符号化されつつあるピクセル位置を表す。画像１０５
がモデル化機構１０７へ入力される。モデル化機構１０
７の内部で、画像は予測機構１０９へ入力される。ピク
セル１０３に先行するシーケンス１０１に基づいて、ピ
クセル１０３に関する予測値ｘ _i+1が推量される。この
予測値を実際値から減算した誤差値(ｅ_i+1＝ｘ_i+1−ｘ
_i+1)が計算され、誤差モデル化機構１０９において、誤
差がモデル化される。誤差値の確率分布および個々のピ
クセルに関する誤差値が符号化機構１１１に送られ、圧
縮されたビットストリーム出力が生成される。

【０００９】IEEEの Trans.Image Processingの出版用
に書かれたM.J.Weinberger, J.Rissanen, R.Arps３氏共
著の"Applications of universal context modeling to
lossless compression of gray-scale images"に記載
の方式が現在公表されている最もすぐれた圧縮比率を示
す。この方式において、ｘ_i+1に対する文脈が、動的に
変動する量子化された差分ｘ_ij−ｘ_iiから構築される。
ｘ_ijおよびとｘ_iiは、ｘⁱ内の文脈に対する最大探索空
間として使用される（走査方向に関する）固定的因果律
テンプレート(causal template)内の２つの隣接するピ
クセルの値である。量子化の度合いは、記号発生回数を
含む複雑なデータベースに基づいて行われる複雑な計算
によって動的に決定される。条件付け文脈の可変サイズ
は、モデルを「過剰適合」することを防止するため、確
率論的複雑性の概念に基づいて最適化される。原理的に
は、文脈が大きくなればなる程、それら文脈は、予測残
差に関する一層片寄った分布を示唆し、それによってよ
りすぐれた適合を生み出すので、データの固有の「構
造」をより効果的に捕捉する。

【００１０】しかしながら、（例えば、より小さい文脈
で、従ってより少ないパラメータで、同様の適合が達成
できるにもかかわらず）必要以上に複雑なモデルを選択
することは処理能力にマイナスの影響を及ぼす。このよ
うな冗長なパラメータは、「モデル費用」を示唆する。
このモデル費用は、逐次方式において、通算数統計を非
常に多数の文脈に広げて行わなければならない場合に発
生する「文脈希釈(context dilution)」という負荷ペナ
ルティを受けるものと（従って対応する推定の正確性に
影響を及ぼすものと）解釈される。非逐次（２回パス）
方式では、モデル費用は、符号化機構に伝送するために
第１回のパスにおいて推定されるモデル・パラメータを
符号化するために必要な符号長を表す。上述のWeinberg
er氏等の予測ステップは、最適化された文脈依存の線形
予測機構を用いて達成され、モデル化される予測残差
は、数値的に符号化される。その結果の符号長は、デー
タをモデル化するために使用される一定幅のクラスのプ
ロセスで、漸次近接するように最適化される。

【００１１】上記Weinberger氏等の方式のモデル化およ
び符号化部分は、予測と文脈モデル化に使用される複雑
な基礎的データ構造および必要な算術符号化機構のため
に、非常に複雑である。予測残差に対する固定的予測機
構および非最適化文脈を使用する代替方式がいくつか存
在する。それら代替方式では、一部のタイプの画像につ
いて得られる圧縮比率が若干悪化する（特に、自然の景
観の場合に悪化し、医療や衛星画像について劣化は顕著
である）。そのような技術の１つは、ＪＰＥＧ圧縮規格
の基礎となったSunsetルゴリズムである。この技術は、
特許名称'Compression of multilevel Signals"の米国
特許第4,749,983号に記載されている。

【００１２】しかし、このアルゴリズムに使用されるモ
デルは、なお予測残差の算術的符号化を必要とし、多く
のアプリケーションでは、特に、ソフトウエア・アプリ
ケーションおよび符号化速度が重要となる多くのアプリ
ケーションの場合に、この符号化動作は複雑であると考
えられる。単純化を目指して、伝統的ＤＰＣＭ技術を若
干修正した代替方式が提案されたが、これもまた固定予
測機構を使用して予測残差のハフマン符号化を含むもの
である。（ＤＰＣＭ技術は、A.Netravali andJ. 0.Lim
b, "Picture coding:A review," Proc.IEEE, vol. 68,
pp. 366406, 1980に記載されている）。このように、上
述の既存の技術は、予測残差の第１順序のエントロピー
による圧縮処理性能の点で基本的に制約される。予測ス
テップでのこれら技術のデータの「相関解除(decorrela
te)」能力は減じられ、そのため、一般的には、相関解
除全体を達成することができない。

【００１３】理想的には、処理された周囲のピクセルに
基づく現在時ピクセルｘ_i+1の値の予測は、上記Weinber
ger氏等の文献に記載のようにその近傍の稜線方向を条
件とするモデルを学習して適応することによって行われ
るべきであろう。しかしながら、そのような適応的学習
は非常に複雑である。それにもかかわらず、可能な限り
すぐれた予測機構を求めるため、複雑さの少ない稜線検
出器が望まれている。

【００１４】ISO/IEC 10918-1 ITU T.81. Digital comp
ression and coding of continuoustone still images
- Requirements and guidelines, Sept. 1993に記載さ
れているように）無損失ＪＰＥＧ方式に対して提案され
た７つの固定線形予測機構は、因果律テンプレートで使
用可能な稜線情報を破棄するとともに、選択された予測
機構に基づいた種々の圧縮結果を作成する。更に、最良
の予測機構は画像に大きく依存する。

【００１５】従って、ある程度複雑さの少ない予測機構
を使用する画像圧縮機構を持つことが望まれる。「少な
い複雑性」という用語は、本明細書においては、浮動小
数点演算および乗算を避け加算およびシフト演算を使用
する画像圧縮システムを意味する。それは、また、単純
な比較および固定テーブル検索を行い、複雑な基礎デー
タ構造の更新を行わない文脈決定プロセスを意味する。
文脈モデルに基づく上述の画像圧縮技術のいずれもこの
ような「少ない複雑性」を実現していない。

【００１６】プレフィックス符号として最適ではある
が、ハフマン符号は、その生成の基となった確率分布と
（その分布が非常に片寄っている場合）ほとんど一致し
ない。１つの事象が５０％以上の確率で集中する場合は
必ず平均記号当たり符号長がエントロピーに接近するこ
とのないように、少なくとも１つの１ビット符号ワード
が各事象に割り当てられる必要がある。これは、予測誤
差が０であるような円滑な区域を表す文脈のケースであ
る。画像によっては、対応するハフマン符号の冗長度
が、圧縮比率の顕著な劣化を生み出す。伝統的（非条件
つき）ハフマン符号方式では、データのブロックが「ス
ーパー符号」として符号化される形態をとるアルファベ
ット拡張法によってこの問題は対処される。この種のア
ルファベット拡張法は、ハフマン符号の超過の符号長を
多数の記号に拡散し、記号当たりの冗長度を減少させる
手段とみなすことができる。

【００１７】

【発明が解決しようとする課題】上記従来技術の諸問題
の観点から、文脈モデル条件付けのモデル化能力を持ち
ながら、なおかつ、片寄った確率分布とその分布のエン
トロピーに接近する記号当たりの符号を維持するハフマ
ン符号化の簡略化を達成することができる画像圧縮伸張
技術が必要とされている。従って、本発明の課題の１つ
は、複雑な画像圧縮システムと同等の圧縮比率を実現す
る複雑性の少ない画像圧縮機構を提供することである。
また、本発明の課題の１つは、ハフマン符号化と文脈モ
デル化の長所を結合する画像圧縮機構を提供することで
ある。本発明の別の１つの課題は、稜線に敏感な複雑性
の少ない予測機構を使用する画像圧縮機構を提供するこ
とである。また、本発明の課題の１つは、近傍の勾配を
使用して圧縮されるべきピクセルの文脈を決定すること
である。更に本発明の課題の１つは、圧縮されるべきピ
クセルの文脈を量子化し、圧縮された文脈を使用して予
測残差に関する検索テーブルを作成し選択することであ
る。本発明の更に別の課題の１つは、ハフマン符号化の
１ビット／ピクセルの最小制限を克服することである。

【００１８】

【課題を解決するための手段】本発明の上記およびその
他の課題は、文脈量子化機構、予測機構、および量子化
された文脈に関する誤差の確率分布に基づいてハフマン
・テーブルを構築するテーブル生成機構を備える画像圧
縮機構を提供することによって達成される。文脈は、以
前に符号化されたピクセルを含むテンプレート中のピク
セルによって決定される。文脈量子化機構は、符号化さ
れるべきピクセルの文脈を量子化する。画像圧縮機構
は、圧縮されるべきピクセルの文脈を使用して、ピクセ
ルの値を予測し、各ピクセルの予測値を対応する実際値
と比較する。ピクセルが属する特定の量子化された文脈
に関して、誤差が通算される。第１回目のパスの終了時
に、画像圧縮機構は、量子化された文脈毎に出会った誤
差に関する確率分布を持つ。画像圧縮機構は、これら確
率分布を使用して文脈特有のハフマン・テーブルを作成
する。

【００１９】第２回目のパスで、画像圧縮機構は、圧縮
されるべきピクセルの量子化された文脈を使用して、量
子化された文脈に対応するハフマン・テーブルにおい
て、該ピクセルに関する予測誤差に対応する符号を検索
する。本発明の１つの実施形態において、画像圧縮機構
は、その文脈モデルに組み込まれたアルファベット拡張
を使用して、符号化の冗長度を減少させる。

【００２０】伸張側では、伸張機構も予測機構および文
脈量子化機構を持つ。伸張機構が、画像圧縮機構によっ
て使用されたものと同一の文脈テンプレートを参照する
ことによって、復号されるべきピクセルの文脈を決定す
る。文脈量子化機構が、次に、符号化されるピクセルに
対応する誤差値を検索すべきハフマン・テーブルを決定
する。伸張機構が、文脈テンプレートの中の以前に復号
されたピクセルを使用してピクセルに関する予測値を入
手し、予測値に誤差値を加算して実際のピクセル値を入
手する。

【００２１】上記課題を解決する本発明の手段には、入
力装置から圧縮すべき画像を取り出すステップ、上記画
像におけるピクセルの文脈を使用して上記ピクセルに関
する予測値を決定するように上記コンピュータを動作さ
せるステップ、上記予測値を実際値と比較してそれによ
って残差を生成するステップ、文脈特有ハフマン・テー
ブルから上記残差の少くとも１つに対応する符号を取り
出すステップ、および上記符号を復号器へ伝送するステ
ップを含むコンピュータを用いてデジタル画像を損失な
く圧縮する方法が含まれる。

【００２２】

【発明の実施の形態】本発明は、ハフマン符号化の単純
性を文脈モデルの潜在的圧縮能力に結合させることによ
って連続階調画像の無損失圧縮を行うシステムおよび方
法である。本発明の圧縮機構は、固定的文脈モデルに基
づくものであるが、文脈に条件付けされたハフマン符号
を使用することによって処理能力の効率が向上するよう
に調整される。文脈に条件づけされたハフマン符号の使
用は、固有の問題を発生させるが、それは本発明によっ
て解決される。一方、各文脈毎に異なるハフマン・テー
ブルが設計されなければならないので、発生可能なエラ
ー事象（すなわち各文脈での効果的なアルファベット）
の数が大きすぎてはならない。同じ理由から、文脈の数
は比較的小さくなくてはならない。一方、アルファベッ
トは小さくすることはできない。なぜならば、それが小
さければ、ハフマン符号の冗長度（すなわちエントロピ
ーに対する過剰符号長）が増加するからである。この冗
長度は、各確率が−２の累乗である分布についてのみ消
滅する。更にハフマン符号の別の基本的制約として、ハ
フマン符号は、符号化毎に最小限１ビットの符号長を必
要とするので、非常に片寄った分布の文脈に対する圧縮
比率は顕著に劣化する。

【００２３】上記の問題に対処し解決策を見出すことに
よって、本発明は、例えばSunset符号化器シリーズのよ
うな算術演算に基づく複雑な符号化で得られるものと同
等またはそれよりすぐれた圧縮比率を、しかもより少な
い複雑性で、達成する。特に、本発明は、後述で明らか
になるように、ＪＰＥＧ独立無損失圧縮システムよりも
優れた圧縮性能を持つものである。

【００２４】図２は、本発明の好ましい実施形態に従う
画像圧縮システム２０１のブロック図である。非圧縮画
像が、画像バッファ２０３に記憶される。画像バッファ
は、ピクセル・シーケンス生成機構２０５に接続してい
る。ピクセル・シーケンス生成機構２０５は、予測機構
２０７および文脈量子化／ピクセル符号化機構２０９に
接続している。予測機構２０７は、現在処理されている
ピクセルに関して、その文脈を使用して予測値を決定す
るように動作する。可能な文脈の全体数は非常に多くな
る可能性がある。文脈量子化機構２０９は、特定の文脈
を、一組の量子化された文脈の中の１つに類別する。

【００２５】本発明の１つの実施形態では、画像圧縮機
構２０１は、２回パスのシステムとして動作する。第１
回のパスで、画像圧縮機構２０１は、各量子化された文
脈毎に各誤差値の発生数を通算する。第１回パスの終了
時に、画像圧縮機構２０１は、量子化された文脈各々に
ついて予測残差に関する確率分布を生成する。予測残差
のこれら文脈依存通算値が、符号化テーブル生成機構２
１１へ入力され、予測残差の確率分布に基づく複数のハ
フマン・テーブルが作成される。

【００２６】第２回目のパスの間、文脈量子化／ピクセ
ル符号化機構２０９を通して、画像圧縮システム２０１
は、それぞれの文脈に特有のハフマン・テーブルを使用
して、圧縮される画像の個々のピクセルについて予測残
差を符号化する。符号化された画像は、図１３に示され
るような画像復号機構によって復号されることができ
る。

【００２７】ピクセル・シーケンス生成機構２０５は、
予測機構２０７へ多数の文脈ピクセルを出力する。図３
は、本発明によって使用される因果律テンプレート３０
１を示している。エレメント３０３は、値ｘを持つピク
セルであって、現在処理されているピクセルである。テ
ンプレート３０１において、「北」のピクセル３０５
（すなわち現在時ピクセル３０１の上のピクセル）の値
はａとして、「西」のピクセル３０７（すなわち現在時
ピクセル３０１の左のピクセル）の値はｂとして示さ
れ、一方、「北西」のピクセル３０９および「北東」の
ピクセル３１１（すなわちそれぞれ現在時ピクセル３０
１の斜め方向のピクセル）の値はそれぞれｃおよびｄと
して示されている。復号機構が符号ストリングを逐次復
号する際、「東」のピクセルは復号機構にとって使用で
きないものなので、このピクセルは使用されない。当然
ａ、ｂ、ｃおよびｄは時間インデックスｉに依存する
が、簡略化のためこの依存性は表記から削除した。

【００２８】予測画像圧縮システム２０１の予測機構２０７は、単純なテ
ストを使って垂直または水平稜線を検出する。稜線が検
出されない場合、ａ＋ｂ−ｃが推測値である。なぜなら
ば、それぞれ高さａ、ｂおよびｃを持つ北、西および北
西のピクセル位置を１つの平面が通り、現在ピクセルは
同じ平面に属するように制約されるならば、上記の推測
値がｘ_i+1の値であるとみなされるからである。この制
約は、画像が稜線がないため円滑であると期待されると
いう事実を表す。具体的には、予測機構２０７は次式
(2)のように推測を行う。

【００２９】

【数２】普遍性の損失なしにａ≦ｂであると仮定すると、式(2)
の予測は、垂直稜線が現在位置の左に存在する多くのケ
ースでａを取り上げ、水平稜線が現在位置の上に存在す
る多くのケースでｂを取り上げ、あるいは、稜線が検出
されない場合（例えば平滑が仮定される場合）平面予測
となるものと解釈される。代替的実施形態では、ｄが予
測機構２０９によって使用される。ｄを利用することに
よって、予測機構２０９は稜線をより明確に識別する。
この実施形態では、予測機構２０９が、式(2)を使用す
る場合より小さい予測誤差の第１次エントロピーを把握
する。この予測は、次式(3)のように表される。

【００３０】

【数３】ただし式(3)でａ'は次式(4)で表されるものとする。

【００３１】

【数４】図４および図５は、式(3)および(4)を使用する予測機構
２０７の概略図である。回路４０１が補助信号ａ'を生
成する。回路４０１は入力値ａおよびｄを受け取る。こ
れらの値は、加算機構４０３によって加算され、シフト
・レジスタ４０５によって２で除算される。この結果が
マルチプレクサ４０７によって値ａとマルチプレクスさ
れる。マルチプレクサのための制御信号Ｙ１が制御機構
４０９によって生成される。制御信号Ｙ１が１であれ
ば、シフト・レジスタ４０５からの出力が補助信号ａ'
として出力され、さもなければ値ａが補助信号ａ'とし
て出力される。

【００３２】制御信号Ｙ１は、図６に示されるように制
御回路４０９によって生成される。回路４０９は値ａ、
ｃおよびｄを入力として受け取る。値ｄが減算機構５０
３によって値ａから減算される。同様に、値ａが減算機
構５０５によって値ｃから減算される。減算結果が絶対
値回路５０７および５０９へ送られ、絶対値が計算され
る。絶対値回路５０９の出力はシフト・レジスタ５１１
へ送られ、４が乗算される。シフト・レジスタ５１１か
らの出力および絶対値回路５０７からの出力が比較器５
１３へ送られる。比較器５１３の出力は、｜ａ−ｄ｜＜
４｜ａ−ｃ｜であれば１で、さもなければ０である。減
算器５０３および５０５の減算結果の符号が回路５１５
および５１７にそれぞれ出力され、それら符号ビットが
比較器５１９によって比較される。２つの符号ビットが
同一であれば比較器５１９の出力は１で、さもなければ
０である。比較器５１３および５１９からの出力がＡＮ
Ｄゲート５２１によってＡＮＤされ制御信号Ｙ１が生成
される。

【００３３】図５において、回路４１１が、信号ａ'を
介して図４の回路４０１に接続している。回路４１１
は、文脈ピクセル値ａ、ｂおよびｃ、および値ａ'に基
づき予測ピクセル値を決定する。回路４１１は、方程式
(3)の３つの代替値を計算する。第１の代替値は、加算
器４１３によって値ａおよびｂを加算して結果の和およ
び値ｃを減算器４１５へ送る。減算器の出力(ａ＋ｂ−
ｃ)が、第１の入力としてマルチプレクサ４１７に供給
される。３番目の代替値は、値ａ'およびｂの最小値(mi
n)と最大値(max)である。これらの値は回路４１９およ
び４２１によってそれぞれ生成される。

【００３４】マルチプレクサ４１７のための制御信号Ｙ
２が、第２制御回路４２３によって生成される。制御回
路４２３への入力は、回路４１９および４２１それぞれ
から出力されるａ'およびｂの最小値および最大値、お
よび減算器４１５からの出力(ａ＋ｂ−ｃ)である。制御
回路４２３の詳細が図７に示されている。制御回路４２
３は、２つの比較器４２５および４２７から構成され
る。比較器の各々は、減算器４１５からの出力である信
号(ａ＋ｂ−ｃ)を入力として受け取る。比較器４２５
は、信号ｍａｘ(ａ',ｂ)を受け取り、(ａ＋ｂ−ｃ)がｍ
ａｘ(ａ',ｂ)より小であれば０を出力し、さもなければ
１を出力する。比較器４２７は、信号ｍｉｎ(ａ',ｂ)を
受け取り、(ａ＋ｂ−ｃ)がｍｉｎ(ａ',ｂ)より大であれ
ば０を出力し、さもなければ１を出力する。制御信号Ｙ
２は、比較器４２５および４２７からの出力の組合せで
ある。

【００３５】制御信号Ｙ２が００であれば、ｍｉｎ
(ａ',ｂ) ＜ａ＋ｂ−ｃ＜ｍａｘ(ａ',ｂ)を意味し、
予測ピクセル値は、(ａ＋ｂ−ｃ)である。Ｙ２が０１で
あれば、ａ＋ｂ−ｃ≦ｍｉｎ(ａ',ｂ)を意味し、予測ピ
クセル値は、ｍｉｎ(ａ',ｂ)である。Ｙ２が１０であれ
ば、ａ＋ｂ−ｃ≧ｍａｘ(ａ',ｂ)を意味し、予測ピクセ
ル値は、ｍａｘ(ａ',ｂ)である。Ｙ２が１１であれば、
(ａ＋ｂ−ｃ)＝ｍｉｎ(ａ',ｂ)＝ｍａｘ(ａ',ｂ)である
ので、いずれの値でも選択することができる。

【００３６】図８は、文脈量子化／ピクセル符号化機構
２０９のブロック図である。文脈量子化／ピクセル符号
化機構は、誤差回路７０１、文脈決定回路７０３、文脈
インデックス付きカウンタ７０５、符号化回路７０７お
よび符号化テーブル選択回路７０９という５つの主要コ
ンポーネントから構成される。現在時ピクセルおよび
（予測機構２０７からの）予測された値が誤差回路７０
１の減算器７１１へ入力され、予測残差すなわち予測誤
差を決定する。図１０を参照して後述されるように、現
在時ピクセルが属する量子化された文脈に依存して、誤
差(ｅ)または誤差の反対値(−ｅ)が符号化または累算さ
れる。従って、ｅの負が回路７１３によって生成され、
２つの値がマルチプレクサ７１５へ送られ、文脈決定回
路からの（逆にされた）制御信号によって選択される。
結果として、マルチプレクサ７１５の出力は誤差量ｅで
あって、それは（第１回パスでは）累算され（第２回パ
スでは）符号化される。誤差量ｅは、文脈インデックス
付きカウンタ７０５および符号化器７０７に供給され
る。その供給先は、パス信号によって画像圧縮機構２０
１がどのパスで動作しているかに従って、イネーブルま
たはディスイネーブルされる。

【００３７】パラメータ減少パラメータ数を減らすことは、文脈モデル化方式におけ
る重要なステップである。逐次公式において、目標は、
「文脈希釈(context dilution)」を避けることであり、
一方、２回パス方式では、不必要なテーブル・オーバー
ヘッドを減らすことが望まれる。モデルにおけるパラメ
ータの総数は、各文脈で考慮される異なる誤差事象の数
および文脈の数に依存する。

【００３８】画像圧縮機構２０１の１つの方法は、アル
ファベットの減少である。Ａを異なるピクセル強度の総
数を意味するものとする。（例えば８ビットピクセルに
関してＡ＝２５６のように）Ａは２の累乗である。原理
的には、誤差残差は、範囲［−Ａ＋１，Ａ−1］にある
値を取る可能性がある。しかしながら、予測値を所与と
すれば、この範囲内のＡ個の残差だけが発生することが
でき、復号器がｘ_i+1を復元するため(ｅ_i+1ｍｏｄＡ)だ
けを必要とする点は容易にわかる。２の補数で表される
このモジュール減少量は、logＡ＋第１ビットに対する
いかなる桁上げも無視する。このように、画像圧縮機構
２０１は、予測残差がｌｏｇＡビットで表される−Ａ／
２とＡ／２−１の間の整数であるという事実を利用す
る。

【００３９】予測機構が合理的推量を行うものと仮定す
ると、予測残差の分布は通常片寄っていて、０で頂点と
なり、大きい予測残差に対して急速に下がる。従って、
Ａの可能な誤差事象の全セットに関してハフマン符号
（各文脈に対して１つの符号）を構築するのは賢明では
ない。なぜなら、これら事象の大部分は非常に低い確率
で発生することが予想されるからである。その代わり、
本発明の画像圧縮機構２０１は、誤差値ｅ_i+1に関して
次式(5)の可能な事象を考慮に入れる。 "−Ｔ未満",−Ｔ,−Ｔ＋１,...,−１,０,＋１...Ｔ−１,Ｔ,"Ｔより大" (5) 但し、Ｔは画像圧縮機構２０１を調整するために使用さ
れるしきい値パラメータである。Ａ＝２５６に関して
は、Ｔ＝８がすぐれた選択であることが経験的にわかっ
ているので、この場合、１文脈につき１９の可能な誤差
事象が存在する。当然のことながら、｜ｅ_i+1｜がたま
たまＴを越える場合、伸張システムは、予測残差の正確
な絶対値について通知を受ける必要がある（正負符号
は、「−Ｔ未満」および「Ｔより大」によって既に与え
られている）。これはありそうもない事象であるので、
本発明に従う画像圧縮機構２０１は、事象"ｅ_i+1＜−
Ｔ"または"ｅ_i+1＞Ｔ"が符号化される文脈を無視して、
単一の分布を使用して大きい予測残差のすべての発生を
符号化することによって「パラメータ資源」を節約す
る。

【００４０】予測残差が大きく識別された後、（誤差の
絶対値を表す）Ａ／２−Ｔの可能な値に符号ワードを割
り当てる必要がある（この時、符号化機構７０７は「大
きい誤差」状態となる）。再び、大きい残差は極めてあ
りそうもなく、本発明の画像圧縮機構２０１は、次の式
(6)の値からなる更に減少した対応ハフマン・テーブル
を使用する。Ｔ＋１,Ｔ＋２,...,Ｂ,≧Ｂ＋１, (6) 但しＢはパラメータであり、Ａ＝２５６に関してＢ＝６
４が良好な経験的選択である。

【００４１】誤差残差が少なくともＢ＋１であるような
場合、正確な誤差値を示すため、対応するハフマン符号
ワードの後に、［ｌｏｇ(ａ／２−Ｂ)］ビット（すなわ
ちＡ＝２５６の場合６ビット）に対する値(｜ｅ｜−Ｂ
−１)が続く。

【００４２】式(5)および(6)によって、画像圧縮機構２
０１は、文脈当たり(２Ｔ＋３)個のエントリ（典型的に
は１９のエントリ）を持つハフマン・テーブルと(Ｂ−
Ｔ＋１)個のエントリ（典型的にはＡ＝２５６の場合５
７のエントリ）を持つハフマン・テーブルを必要とす
る。後述のように、（減少されたアルファベットを拡張
することによって派生する）２つの別の種類のハフマン
・テーブルが使用される場合もある。これらのハフマン
・テーブルは、テーブル・アレイ・メモリ７１１に記憶
される。

【００４３】本発明に従う画像圧縮機構２０１において
現在時予測残差の符号化を条件づける文脈は、差分ｇ₁
＝ｄ−ａ、ｇ₂＝ａ−ｃ、ｇ₃＝ｃ−ｂから構築される。
これら差分は、近傍の勾配を表し、予測誤差の統計的特
性を左右する。対称性によって、３つの差分値は、同じ
形態でモデルに影響を与える。画像圧縮機構２０１にお
いて、各々の差をおよそ同程度に確からしい区域に量子
化することによってパラメータの減少が実現される。う
まく定義された数学的意味において、これは、現在時ピ
クセルとその文脈の間の相互情報量、すなわち、モデル
化されるべきピクセル値に対する条件付け文脈によって
与えられる情報量の情報理論的測定値を最大化する。本
発明に従って、画像圧縮器の複雑性の少なさは、固定的
数の同程度に確からしい区域に基づいて文脈を量子化す
ることによって達成される。対称性によって、差分値０
に中心が置かれる１つの区域が存在し、間隔［ｒ₁，
ｒ₂］が１つの区域を表すとすれば、［−ｒ₁，−ｒ₂］
も１つの区域を表す。このように、区域の総数は、奇数
の整数２Ｒ＋１であり、原理的には、総数(２Ｒ＋１)個
の文脈がある。Ｒは、量子化区域の総数を制御するパラ
メータである。しかし、再び対称性によって、次式(7)
を仮定することは妥当である。Ｐｒｏｂ｛ｅ_i+1＝Ｄ｜Ｃ_i＝［q₁,q₂,q₃］｝＝Ｐｒｏｂ｛ｅ_i+1＝−Ｄ｜Ｃ_i＝［−q₁,−q₂,−q₃］｝（7) 但し式(7)においてＣ_iは、時間ｉにおける文脈３ビット
バイト(triplet)を表し、q_j(j=1,2,3)は、ｇ_j(ｊ=1,2,
3)に対応する量子化された差分である（括弧は勾配のｇ
₁、ｇ₂、ｇ₃の３ビットバイトを示し、中括弧はその量
子化された対応値［ｑ₁,ｑ₂,ｑ₃］を示す）。この式を
使用して、画像圧縮機構２０１は、文脈の数を((２Ｒ＋
１)³−１)／２＋１に減らす。好ましい実施形態におい
て、画像圧縮機構２０１は、Ｒ＝1を使用し、その結
果、１４の異なる文脈となる。

【００４４】量子化された文脈各々は、３次元ベクトル
[ｑ,ｑ₂,ｑ₃]によって表される。ゼロでないベクトルに
ついては、大きさが同じで方向が正反対のベクトルが存
在する。これらの反対ベクトルによって表される文脈
は、量子化された文脈ペアと考えられ、画像圧縮機構２
０１の１つの実施形態では、そのようなペアの各々毎に
１つだけのハフマン・テーブルが生成される。対称文脈
をマージすることによって、符号化された値が実際には
予測残差の反対のものであることもできる点は注意する
必要がある。例えば、Ｒ＝１に関して、(−１)、０およ
び(＋１)が（「負」、「ほぼゼロ」、「正」をそれぞれ
示す）３つの文脈区域を示すとする。例えば４という残
差が文脈[−１,＋１,０]で符号化される場合、例えば文
脈[＋１,−１,０]における３という残差は、前者と同じ
テーブルを用いて(−3）と符号化される。

【００４５】Ｒ＝１とする画像圧縮機構２０１の１つの
実施形態において文脈の定義を完成させるため、パラメ
ータＳが、量子化区域の間の境界を決定する値を指定す
る。中心区域は、−Ｓ＜△＜Ｓである差値Δによって形
成される。Ｓの最適値は非常に画像に依存することが知
られている。多くの画像に関して、合理的な選択はＳ＝
７である。比較的スムーズな画像に関しては、この選択
は、ピクセルの大部分（[０,０,０]または [０,０,＋
１]のような文脈)を中心区域に集中させ、[−１,＋１,
＋１]のような文脈は過疎にさせる傾向を持つ。本発明
において、比較的大きい境界値（例えばデフォルトとし
てのＳ＝7）を選択し、境界パラメーターＳ／２を持つ
同じ方式を再帰的に適用して「中心文脈」[０,０,０]
を再分割することによって、上記の問題に対する解決策
が得られる。このように、文脈の総数は(２Ｒ＋１)
³（すなわち１つのの好ましい実施形態では２７）とさ
れる。後述のように、過疎の文脈は、固定符号を用いて
符号化することができるので、不要なテーブルのオーバ
ーヘッドを節約できる。

【００４６】図９は、図８の量子化回路７０３の概略図
である。上述の通り、実行される量子化には２つのレベ
ルがある。１つはＳを使用し、１つは中心文脈[０、
０、１]に関してＳ／２を使用するものである。前者の
文脈量子化は、勾配文脈量子化器８０１によって実行さ
れ、後者（中心文脈の細分量子化）は、第２の勾配文脈
量子化器８０３によって実行される。内部的には、２つ
の量子化器８０１および８０３は、図１０に示されるよ
うに、同一である。

【００４７】３つの勾配、ｄ−ａ（ｇ₁）、ａ−ｃ
（ｇ₂）およびｃ−ｂ（ｇ₃）が、減算器９０１、９０３
および９０５によってそれぞれ決定される。これらは、
各々、「±Ｓ」量子化器９０７ａ、９０７ｂおよび９０
７ｃへそれぞれ入力される。「±Ｓ」量子化器９０７の
各々は内部的に同一であり、その動作は図１１に示され
ている。「±Ｓ」量子化器９０７ａ−ｃは、勾配ｇ_iお
よびパラメータＳならびにその負（−Ｓ）を入力され
る。「±Ｓ」量子化器９０７は、２つの比較器１００１
および１００３からなり、上述の通りｇi≦−Ｓの場合"
１０"、−Ｓ＜ｇi＜Ｓの場合"００", Ｓ≦ｇ_iの場合"０
１"という値を持つ２ビットの出力信号ｑ_iを生成する。
Ｓは正と仮定されているので、組合せ値"１１"はあり得
ない。

【００４８】図１０を再び参照すれば、量子化文脈の間
には対称が存在するので、本発明の画像圧縮機構は、そ
の対称性を利用して、対称する量子化文脈のペアの各々
に対してただ１つのテーブルを備え持つ。かくして、量
子化文脈信号が、量子化文脈を適切なハフマン・テーブ
ルにマップするマッピング・テーブル９０９に送られ
る。上述の通り、Ｒ＝１については、そのようなテーブ
ルが１４ある。かくして、マッピング・テーブルから出
力される文脈インデックスは、０と１３の間の数を表す
４ビットからなる。加えて、インデックス(index)が
「反対の」テーブルのためのものであるか否かを示す１
ビットの逆信号が出力される。次の表１は、マッピング
・テーブル９０９の１つの例である。

【００４９】

【表１】入力出力ql q2 q3 マップ先 index 逆 00 00 00 00 00 00 0000 0 00 00 01 00 00 01 0001 0 00 00 10 00 00 01 0001 1 00 01 00 00 01 00 0010 0 00 01 01 00 01 01 0011 0 00 01 10 00 01 10 0100 0 00 10 00 00 01 00 0010 1 00 10 01 00 01 10 0100 1 00 10 10 00 01 01 0011 1 01 00 00 01 00 00 0101 0 01 00 01 01 00 01 0110 0 01 00 10 01 00 10 0111 0 01 01 00 01 01 00 1000 0 01 01 01 01 01 01 1001 0 01 01 10 01 01 10 1010 0 01 10 00 01 10 00 1011 0 01 10 01 01 10 01 1100 0 01 10 10 01 10 10 1101 0 10 00 00 01 00 00 0101 1 10 00 01 01 00 10 0111 1 10 00 10 01 00 01 0110 1 10 01 00 01 10 00 1011 1 10 01 01 01 10 10 1101 1 10 01 10 01 10 01 1100 1 10 10 00 01 01 00 1000 1 10 10 01 01 01 10 1010 1 10 10 10 01 01 01 1001 1

【００５０】再び図９を参照すると、文脈量子化器８０
１および８０３の各々からの文脈インデックスがマルチ
プレクサ８０５に供給され、文脈決定回路７０３からの
出力となる文脈インデックスが選択される。勾配文脈量
子化器８０１からの文脈インデックス出力が「中心」文
脈であるか否かを決定する比較器８０７によってマルチ
プレクサ８０５は制御される。もしそうであれば、細分
量子化器８０３からのインデックスが選択される。ま
た、比較器は、どの逆信号が文脈決定回路７０３からの
出力となるべきかを制御する。２つの逆信号が、比較器
８０７の出力によって制御されるマルチプレクサ８０９
へ入力される。このようにして、文脈決定回路７０３に
よって出力される逆信号は、選択された文脈インデック
スに対応する。回路７０３からのインデックス信号は５
ビットからなり、その４ビットは選択されたインデック
スであり、１ビットはどれが選択されたかを示す。５ビ
ットのインデックスは、２７の可能な値の１つをとる。

【００５１】アルファベットの拡張本発明の画像圧縮機構２０１は、文脈条件づけ機能にア
ルファベット拡張を組み入れることによって、非常に片
寄った分布によるハフマン符号の冗長度に対処する。３
つの差（ｇ₁、ｇ₂、ｇ₃）の絶対値が小さい場合の文脈
において、それが円滑な区域を示すので、非常に片寄っ
た分布が典型的に発生する。更に、この文脈はしばしば
実行時に発生する。すなわち、あらゆるピクセルが同じ
（低アクティビティ）文脈で発生する画像において連結
した区域が存在する。この観察は、以下に記述の方法で
ゼロ誤差値の実行を考慮することによって、アルファベ
ット拡張の実施を可能にする。第１に、「低アクティビ
ティ」文脈を、（すべての勾配が正確にゼロである）ａ
＝ｂ＝ｃである場合とそれ以外の場合の２つの別々の文
脈に分割する。一般的に、非常に片寄った分布が存在す
れば、この分割の後、その文脈は大部分ゼロ勾配文脈に
関連づけられる。従って、残りの文脈での発生は、非拡
張（減少された）アルファベットで符号化され、Ｒ＝１
に関して、このアルファベットを使用する文脈の数は２
７のままである（あるいは「中心文脈」を分割するオプ
ションが使われていない場合は１４のままである）。ゼ
ロ勾配文脈に関する拡張アルファベットが図１２のツリ
ー１１０１で表現されている。ツリー１１０１の葉１１
０３−１１２１は符号化されるべき事象を表す。この文
脈においてｘ_i+1が発生すれば、明らかにＸ _i+1=ａであ
る点に留意すべきである。予測残差ｅ_i+1がゼロでなけ
れば、１つの葉がアクセスされ１つのピクセルが符号化
される。しかし、予想されるように、ゼロ誤差（すなわ
ちｘ_i+1=ａ）が発生すれば、ｄの東側ピクセルが考慮さ
れる。その値がｄに等しければ、明らかにｘ_i+2もゼロ
勾配文脈で発生する。この場合、ツリー１１０１を辿っ
て長めの探索を行う。そうでない場合、１というラン長
(run-length)が符号化される。ツリーが検索されＸ_i+2
≠ｄであれば、ランは分割し、１というラン長が符号化
される（１つの葉がアクセスされた）。次に、予測残差
Ｘ_i+2−ｄが新しい「ラン終了」状態で符号化される。
この場合、分布は事象０を含まない。この新しい状態
は、Ｘ_i+2がｄでないという情報を取り入れる。さもな
ければこの情報は失われ、符号は冗長となるであろう。
再び、予想されるように、Ｘ_i+2＝ｄであれば、ツリー
はラン長が少くとも２であることを示し、以下の偶然事
象の１つが起こるまでプロセスは続く。 (a)所定の最大限ラン長ｒに達する（本実施形態ではそ
のデフォルト値はｒ＝6である）。ｒ回の連続的ゼロ誤
差値が単一事象として符号化され、次のピクセルが２７
（または１４）個の普通の文脈で符号化されるか、ある
いは、新しいランを開始するかいずれかである。これは
葉１１２１によって示されている。 (b)ランは非ゼロ誤差値によって分割され、例えば、葉
ノード１１１５、１１１７または１１１９となる。累算
されたランが単一の事象として符号化され、ランを分割
するピクセルが、「ランの終了」状態１１２３で符号化
される。 (c)次の北東ピクセルがゼロ勾配文脈のランを分割す
る。累算されたランが単一事象として符号化され、次の
ピクセルが通常の文脈で符号化される。

【００５２】アルファベット拡張プロシージャは一定量
の冗長度を含む。これは、ランが上記事象ｃによって分
割されるか否かを決定するために必要とされる情報がラ
ンの開始時点に既に復号機構で使用可能であるという事
実による。このように、復号機構はより長いランが起き
得ないことをあらかじめ決めることができ、符号化のた
めの空間をこれらの事象のために予約する必要がない。
以下に記述するように、この冗長度は簡単に取り除くこ
とができる。

【００５３】好ましい実施形態において、ほとんどの画
像に関して、ｒ＝６がゼロ勾配文脈でハフマン符号の冗
長度の許容可能な減少を生み出すことを示す実験結果を
反映する最大ラン長が取り入れられる。これはまたデジ
タル放射線の画像に関する長いランのケースでもある。

【００５４】要約すれば、文脈モデルに組み込まれるべ
きものと提案されるアルファベット拡張は、次の２つの
分布の追加を必要とする。１つはゼロ勾配ラン文脈に関
するもので、他方はラン終了状態に関するものである。
前者に関するアルファベット・サイズは、２Ｔ＋ｒ＋２
で、後者に関しては２Ｔ＋２である。デフォルトのパラ
メータＴ＝８およびｒ＝６について、これらは２４およ
び１８エントリのハフマン・テーブルをそれぞれ必要と
する。

【００５５】ハフマン符号化ピクセルまたはピクセルの中でストリングを圧縮する際
に画像圧縮機構２０１が以下の符号化アクションの１つ
または複数を生み出すプロシージャを上述した。（事象
の数は、Ａ＝２５６に対するデフォルト・パラメータを
使用して計算されている）。 (a)１９の中から１つの事象が、２７（または１４）の
可能な文脈の１つにおいて符号化される（普通の文脈に
おける小さい予測誤差）。 (b)５７の中から１つの事象が符号化される（大きい予
測誤差）。 (c)２４の中から１つの事象が符号化される（ゼロ勾配
文脈でおそらく破棄されるラン）。 (d)１８の中から１つの事象が符号化される（ラン終了
状態）。

【００５６】このように、本実施形態の画像圧縮機構２
０１は、１９個のエントリを持つハフマン・テーブルを
２７（または１４）テーブル、および、５７個のエント
リ、２２個のエントリならびに１８個のエントリのハフ
マン・テーブルをそれぞれ１つ管理する。これらのテー
ブルは、テーブル・アレイ・メモリ７１１に記憶され
る。好ましい実施形態において、画像圧縮機構２０１
は、２つのパスで動作する。第１のパスは、最適のハフ
マン符号を構築するための統計値を収集するためのもの
で、第２のパスで、テーブル検索を通してデータを符号
化する。その後、符号は１回のパスで逐次処理を行う復
号機構に送られなければならない。１回のパスで符号化
を行う代替的方法を以下に記述する。２７文脈の場合で
ハフマン符号が関与する事象の総数は６１２に及ぶの
で、ハフマン符号が完全に記述されなければならないか
否か、またどのように記述されるべきかに特別の注意を
払わねばならない。この問題は特に小さい画像において
重要である。なぜなら、その場合、過剰なテーブルのオ
ーバーヘッドが文脈条件付けによって得られる節約を帳
消しする可能性があるからである。そのため、１つの実
施形態において、画像圧縮機構２０１は、種々の組み合
わせのテーブルを使用して、達成される圧縮を比較し
て、テーブル・オーバーヘッドを最小限に抑える。いく
つかのケースでは、圧縮機構２０５は、テーブルを送出
することなく、圧縮機構および伸張機構両者にとって既
知のデフォルト・テーブルに逆戻りするか、あるいは、
より短い記述を持ち不一致がわずかなテーブルを送出す
ることを決定する。いずれの場合も、符号化長のわずか
な損失は、テーブル・オーバーヘッドに関する利得によ
って埋められる。すべてのテーブル情報は、符号化を行
う前の、第１回パスの終了時点に符号化機構に対して使
用可能となる。

【００５７】効率的符号記述ハフマン符号は、その関連バイナリ・ツリー、および、
記号（または事象）とツリーの葉の間の対応関係を記述
することによって完全に指定される。（Ｌ≧２である）
Ｌ個の葉を持つ完全なバイナリ・ツリーは、（２Ｌ−
４）ビットで記述できる。そのようなツリーを構成する
単純な方法は、ルートから開始して辞書の順にツリーの
各レベルを通過しながら、(Ｌ−１)の内部ノードを逐次
アクセスすることによってバイナリー・シーケンスを作
成するものである。各ノードには、子各々に１ビット宛
２ビットが割り当てられる。「０」は、その子が葉であ
ることを表し、「１」は内部ノードである子に対応す
る。最後にアクセスされた内部ノードに対応する２つの
ビットは、それら両方が常に「０」であるので、無視さ
れる。次に、ツリーの葉が、アルファベットの記号にマ
ップされる。このプロセスは、符号記述の高価な部分を
構成する。統計値を収集し、最適のハフマン符号を計算
した後、圧縮機構２０１は、通常文脈における２Ｔ＋３
の可能な事象に関して次の３つの代替的符号化を検討す
る。

【００５８】(a)負でない整数ｔに関して次の式(8)およ
び(9)を仮定する。Ｐｒｏｂ｛ｅ_i+1＝ｔ｜Ｃ_i｝≧Ｐｒｏｂ｛ｅ_i+1＝ｔ＋１｜Ｃ_i｝ (8) Ｐｒｏｂ｛ｅ_i+1＝−ｔ｜Ｃ_i｝≧Ｐｒｏｂ｛ｅ_i+1＝−ｔ−１｜Ｃ_i｝ (9) 式(8)および(9)の制約の下、「ｅ_i+1＞Ｔ」および「ｅ
_i+1＜−Ｔ」事象のランキング位置が指定され、従って
更に[ｌｏｇ（２Ｔ＋３)]ビットを必要とすることを前
提とすれば、値を減少させることによる誤差確率のラン
キングは、記述されるべき２Ｔビットだけを必要とす
る。従って、ハフマン・ツリー記述（２Ｔ＋２ビット）
を加えることによって、符号は、合計６Ｔ＋２ｌｏｇ
(２Ｔ＋３)＋２ビット（すなわちＴ＝８の場合６０ビッ
ト）で指定することができる。当然のことながら、式
（8)または(9)が第１回パスで収集された統計値に適用
されないならば、結果として生ずる符号は一致せず、符
号長は最適でないであろう。しかし、ほとんどの場合
に、これらの制約は適用されるか、または、Ｔに近いｔ
の値について若干制約が破られる程度である。過疎の文
脈においては、結果として生ずる超過の符号長は、不完
全な符号記述から生じる節約より通常小さい。

【００５９】(b)いかなる仮定も設定されず、減少する
頻度によってランクされる２Ｔ＋３事象のリスティング
をツリー表示に付加することによって、符号は完全に記
述される。単純化のために、１バイト全部を各事象のた
め使用する。符号記述が部分的か（すなわち上記(a)の
仮定が使用されているか）、あるいは、完全かを指定す
る１ビットが追加される。

【００６０】(c)符号化機構および復号機構両者に既知
の固定的テーブルが使用される。この代替方法は、発生
回数の少ない文脈についてテーブル・オーバーヘッドを
節約する。例えばＴ＝８の場合、１つの符号が、長さ３
の符号ワードを事象０、１および−1に、長さ４の符号
ワードを事象２、−２および３に、長さ５の符号ワード
をその他の事象に割り当てることができる。テーブルの
先頭には、固定的テーブルか指定テーブルが使用される
かを示す１ビットが各文脈毎に付けられる。

【００６１】画像圧縮機構２０１は、ラン終了状態にお
ける分布について同様のプロシージャを使用する。ラン
状態（ゼロ勾配文脈）に関して、また、Ｔより大なるｅ
_i+1の値に対応する１つの分布に関して、最後の代替方
法のみが（種々の固定符号が使用されるが）考慮され
る。第１回パスの終了時に、符号化機構は、最も短い符
号長になる代替方法を判断し、復号機構は、第２回パス
で使用された符号について通知される。

【００６２】本発明の画像圧縮機構の動作の方法画像圧縮機構２０１が２回パス形態でとる逐次ステップ
を以下に記述する。簡略化のため、画像境界処理のよう
な特別な場合は省略する。従って、処理されるピクセル
ｘ_i+1に関して周囲のピクセル値a、ｂ、ｃおよびｄがう
まく定義されていると仮定する。例えば、画像境界の外
側のすべてのピクセルはゼロであると仮定することがで
きる。例証の目的から、文脈量子化はＲ＝１を仮定す
る。

【００６３】この方法は、例えばＣＰＵ，ランダム・ア
クセス・メモリ、リード・オンリ・メモリ、多数の入出
力装置、ビデオ・メモリなどを備える汎用コンピュータ
上で実行することができる。このコンピューターは、Ｌ
ＡＮや広域ネットワークのようなネットワークを介し
て、または電話やＣＡＴＶのような通信回線を介して他
のコンピューターに接続することもある。あるいは、こ
の方法は医療画像処理システムのような専用装置上で実
行することも可能である。いずれのアプリケーションに
おいても、この方法は、システム・メモリにロードされ
ＣＰＵによって実行されるソフトウェア命令の形態をと
るか、上述のようなハードウェア実施形態を使用して実
施されるか、または、リード・オンリ・メモリ（ＲＯ
Ｍ）にファームウェアとして記憶される形態をとること
もできる。

【００６４】方法ステップ０：第１のアルファベット減少しきい値Ｔ、第
２のアルファベット減少しきい値Ｂ、最大ラン長ｒおよ
び文脈量子化しきい値Ｓを定義する。好ましい実施形態
におけるこれらパラメータのデフォルト値は、８、６
４、６および７である。「中心文脈」の帰納的細区分が
必要か否かを指定する（１４の基本文脈に対してオプシ
ョンの２７文脈がある）。各文脈における２Ｔ＋３事象
に関する通算発生数、大きい誤差値の単一分布における
Ｂ−Ｔ＋１の事象に関する通算発生数、ラン状態におけ
る２Ｔ＋２＋ｒ事象に関する通算発生数、およびラン終
了状態における２Ｔ＋２事象に関する通算発生数を割り
当てる。デフォルト・パラメータが使用されるか否かを
示す１ビットを復号機構に伝送する。非デフォルト・パ
ラメータが選択された場合、該パラメータの値を送信す
る。２７文脈か１４文脈かを示す別の１ビットを使用す
る。ステップ１：ピクセル・シーケンスｘⁱを処理した後、
次のピクセルｘ_i+1に関する処理を開始する。画像が終
わりの場合、ステップ１４へ進む。周辺ピクセルの値
ａ、ｂ、ｃおよびｄを所与として、対応する差ｄ−ａお
よびｃ−ｂを計算する（ａ−ｃはすでにｘ_iを処理した
後使用可能となっている）。ステップ２ :式(2)、または、式(3)ならび(4)に従って、
ｘ _i+1としてｘ_i+1を予測する。ステップ３：入力からｘ_i+1を読み取り、ｌｏｇＡビッ
トに対するｅ_i+1=（ｘ_i+1−ｘ _i+1）を計算する。ステップ４：それらの値をしきい値Ｓと比較することに
よって、量子化範囲−１、０および＋１に対して文脈差
分をマップし、文脈３ビットバイトＣｉ＝[ｑ₁,ｑ₂,
ｑ₃]を得る。３ビットバイトの第１の非ゼロ因子が−１
である場合、３ビットバイトのすべての符号を負に変更
する。さもなければ、符号は正とする。ステップ５：１４でなく２７文脈オプションが使用さ
れ、Ｃ_iが「中心文脈」[０,０,０]であれば、しきい値
パラメータ［Ｓ／２］を用いてステップ４を反復する。ステップ６：Ｃ_iの符号が負であれば、ｅ_i+1←−
ｅ_i+1。ステップ７：ａ＝ｂ＝ｃ＝ｄならば、「ラン」状態の符
号化処理を行うステップ１０へ進む。さもなければ通常
のモードにとどまるステップ８へ進む。ステップ８：通常の文脈モードにおいて、｜ｅ_i+1｜≦
Ｔならば、文脈Ｃ_iにおけるｅ_i+1に対応する通算値を増
分し、ｉを増分し、ステップ１へ戻る。さもなければ、
「大きい正」か「大きい負」のいずれかの誤差に対応す
る通算値を増分させる。ステップ９：｜ｅ_i+1｜≦Ｂならば、大きい誤差に関す
る分布における対応する通算値を増分させる。さもなけ
れば、｜ｅ_i+1｜＞Ｂに対応する通算値を増分させる。
ｉを増分してステップ１へ戻る。ステップ１０：ラン状態において、ｅ_i+1≠０の場合、
ステップ８およびステップ９と同様に処理する。ラン状
態に対応する通算値を使用し、必要なら大きい誤差の分
布を使用する。ステップ１１：さもなければ、ｅ_i+1＝０ならばラン通
算値を増分させる。次の北東位置のピクセルの値がｄに
等しければ、ｘ_i+2を読み取りｉを増分する。さもなけ
ればステップ１２へ進む。ステップ１２：処理されるピクセルがｄでなくなるま
で、または、ラン通算値が許容される最大値ｒに達する
までステップ１１を繰り返す。ステップ１３：ラン状態カウンタで検出される全ラン長
に対応する通算発生値を増分させる。最後に読取られた
ピクセルがｄでなければ、ラン終了状態における対応す
る通算値を増分する。また、必要ならば、大きい誤差の
分布における通算値を増分する。ｉを増分してステップ
１へ戻る。ステップ１４：第１回パスが完了後、記憶されたすべて
の分布についてハフマン符号を計算する。各符号につい
て、上記の「ハフマン符号化」および「効率的符号記
述」の節で述べた項目に対応する符号長を計算し、最も
短い符号長になるものを選択する。各コード毎に、固定
テーブルを使用したか否かを示すヘッダを復号機構に伝
送する。カスタマイズされた符号については、ハフマン
・ツリーの記述を伝送する。通常の文脈の場合、完全テ
ーブルを使用したか部分テーブルを使用したかを示すビ
ットを伝送する。次に、頻度ランキングを記述する。ステップ１５：第１回と同様に第２回パスを実行する
が、ただし発生通算数を増分する代わりに、対応する符
号ワードを伝送する。ステップ９が実行され、｜ｅ_i+1
｜＞Ｂであれば、｜ｅ_i+1｜−Ｂ−１の[ｌｏｇＡ／２−
Ｂ]ビット値を伝送する。

【００６５】図１３は、画像圧縮機構２０１に対応する
画像伸張機構１２０１のブロック図である。復号機構１
２０１は、画像圧縮機構２０１からの圧縮画像を受け取
り、この圧縮画像を圧縮画像バッファ１２０３に記憶す
る。画像を圧縮するために使用されたハフマン符号化テ
ーブルが、画像バッファ１２０３から文脈量子化／ピク
セル復号機構１２０５に送られる。テーブルは、画像圧
縮機構２０１によって生成されたハフマン・テーブルで
ある。文脈量子化機構は、復号されるべきピクセルの文
脈を画像圧縮機構２０１の場合と同じ方法で決定する。
しかし、ピクセルに関する文脈を入手するため、画像伸
張機構１２０１は、以前に伸張されたシーケンスのピク
セルを利用する。従って、ピクセルが復号された時、そ
れは、文脈量子化／ピクセル復号機構１２０５から伸張
画像バッファ１２０７へ送られる。伸張画像バッファに
接続するピクセル・シーケンス生成機構１２０９が、
（画像圧縮機構２０１に関する上記記述において定義さ
れる）文脈ピクセルａ、ｂ、ｃおよびｄを予測機構１２
１１へ送る。予測機構１２１１は、画像圧縮機構２０１
の予測機構２０７と同じ方法を使用して、予測値ｘ _iを
決定し、文脈ａ，ｂ，ｃおよびｄと共に、文脈量子化／
ピクセル復号機構１２０５に送る。

【００６６】図１４は、文脈量子化／ピクセル復号機構
１２０５のブロック図である。復号機構１２０５は、ピ
クセル・シーケンス生成機構１２０９から文脈値ａ、
ｂ、ｃおよびｄを受け取る。これらの文脈値は、（図
８、図９および図１０を参照して上述した）文脈決定回
路７０３と同様に動作する文脈決定回路７０３'へ供給
される。文脈決定回路７０３'は、文脈インデックスお
よび逆信号を出力する。文脈インデックスは、復号化テ
ーブル選択回路機構７０９'に入力され、そこで適切な
ハフマン・テーブルをテーブル・アレイ・メモリ７１
１'から取り出すために使われる。テーブル・アレイ・
メモリ７１１'はテーブル・アレイ・メモリ７１１と同
様であるが、符号化および復号化が異なる機構上で行わ
れる可能性があるため、これらのメモリが同一のメモリ
でない場合が多い。また、符号化および復号化テーブル
は、同じ情報を搬送するが、動作の最適化のため異なる
形式をとることもある。

【００６７】復号テーブル選択回路７０９'は、復号器
１３０１へ適切な復号化テーブルを供給する。復号器１
３０１は、また、符号化されたピクセル値ｙを受け取っ
て、復号化テーブルで対応する符号を検索する。値ｅの
符号が、符号変更回路７１３によって逆にされ、その値
および負の値の両方が、逆信号によって制御されるマル
チプレクサ７１５'に送られそこで選択される。マルチ
プレクサ７１５'の出力ｅが、加算回路１３０３によっ
て予測値ｘ _iに加算され、復号値ｘ_iが生成される。復号
値は伸張画像バッファ１２０７へ送られる。

【００６８】機構１２０５の文脈量子化部分は、画像圧
縮システム２０１の文脈量子化機構と同じ形態で動作す
る。従って、文脈量子化機構は、圧縮ピクセル値ｙに対
応する誤差を検索するため使用すべきハフマン・テーブ
ルを決定する。誤差値ｅを検索した後、ピクセル復号機
構１２０５はその数量を予測値ｘ _iに加算する。

【００６９】下記の復号化方法は、種々のハフマン符号
がラベルを付けられた葉を持つバイナリ・ツリーによっ
て表現されると仮定する。より高速の復号に適する１つ
の代替実施形態において、復号器が取る最初のアクショ
ンは、符号化器によって生成されたコンパクトな記述を
一層容易にアクセスできるテーブルに変換することであ
る。

【００７０】復号方法ステップ０：パラメータＴ、ｒおよびＳを取り出し、ヘ
ッダ情報を使用してハフマン・ツリーを構築する。ステップ１：ピクセル・シーケンスｘⁱを復号化した
後、次の符号ワードの復号を開始する。隣接ピクセルの
値ａ、ｂ、ｃおよびｄを所与として、対応する差ｄ−ａ
およびｃ−ｂ（ａ−ｃは既に使用可能）を計算する。ステップ２：前述の圧縮方法のステップ４、５および６
と同様の方法で、文脈Ｃ_i、その符号およびモードを決
定する。ステップ３：通常文脈モードでは、符号化ビット・スト
リームに続くＣ_iに対応するハフマン・ツリーを、１つ
の葉に達するまで逐次アクセスする。その葉が｜ｅ_i+1
｜＞Ｔを示せば、符号化ビット・ストリームを更に調
べ、大きい誤差の分布に対応するハフマン・ツリーを探
索する。復号された符号化ワードが再び｜ｅ_i+1｜＞Ｂ
を示せば、次のｌｏｇ(Ａ／２−Ｂ)ビットを読み取っ
て、ｅ_i+1の正確な値を計算する。もしもＣ_iに関係する
符号が負であれば、ｅ_i+1の符号を変更する。最後に、
（採用した予測方式に応じて）式(2)、または、式(3)な
らびに(4)に従って、ｘ _i+1を計算し、ｘ_i+1＝ｅ_i+1＋ｘ
_i+1を出力する。ｉを増分してステップ１へ戻る。ステップ４：ラン状態では、符号化ビット・ストリーム
に続くこの状態に対応するハフマン・ツリーを、１つの
葉に達するまで逐次アクセスする。その葉がゼロの長さ
のランを示せば、ステップ３へ進む。さもなければ、葉
によって示されるままの多数のピクセル値ｄを出力し、
それに応じてｉを増分する。全ラン長がｒである場合、
あるいは、次の北東ピクセルがｄでない場合、ステップ
１に戻る。さもなければ、符号化ビット・ストリームに
続くラン終了状態に対応するハフマン・ツリーを逐次ア
クセスし、ステップ３の場合と同様の処理を行ってｅ
_i+1を入手して、ｘ_i+1＝ｅ_i+1＋ｄを出力する。ｉを増
分してステップ１へ戻る。

【００７１】実験結果本発明は、以下に述べるようなＬＯＣＯ²Ｉ(Low Comple
xity, Context-Based, Lossless Image Compressionの
略称で複雑性の少ない文脈依存型無損失画像圧縮の意
味）と呼ばれるシステム上で実施した。次の表２は、Ｌ
ＯＣＯ²Ｉといくつかのその他の画像圧縮装置によって
達成された圧縮結果の比較である。この比較結果は、ピ
クセル当たり８ビットでデジタル化されたグレースケー
ル画像セットの圧縮のため、図１ないし図１２を参照し
て記述した本発明の基本構成を使用して得られたもので
ある。この画像セットは、標準的画像の他、医療、衛星
および（モザイク）デジタル・カメラ画像を含む。後述
の代替的構成を使用して、ＲＧＢカラー画像に関し、カ
ラー画像の処理性能を向上させる実施形態の暫定的実験
結果を紹介する。ここで述べるグレースケール画像実験
セットは以下のような画像を含む。 (a)ＪＰＥＧ規格委員会のＹＵＶ体系で表される７２０
桁×５７６行カラー実験画像。ＵおよびＶは、各々が別
個のグレースケール画像とみなされる５７６×３６０に
更にサンプリングされた濃淡コンポーネントである。 (b)ＵＳＣデータ・セットの５１２×５１２グレースケ
ール標準画像。 (c)医療(ＭＲＩ、Ｘ線および超音波）画像。ＭＲＩ画像
（脳および一連の頭部スライス）の次元は２５６×２５
６である。テストされたＸ線画像(人間の骨と肺)の次元
は１０２４×１０２４である。超音波画像は、４８０×
５１２の人間の心臓画像である。 (d)ボイヤジャ宇宙船によって得られた海王星の７枚の
４８０×６４０画像。主な画像オブジェクトに加えて、
画像ファイルは稜線の近くのテクスチャおよびグラフィ
ック情報を含む。

【００７２】

【表２】 DCXT 無損失７回パス画像 BT/CARP LOCO²I Sunset JPEG JPEG エントロヒ゜ barbara Y 4.56 4.84 4.81 5.26 5.26 5.44 balloon V 2.28 2.42 2.42 2.57 2.57 2.82 girl U 2.78 2.85 2.87 3.03 3.03 3.04 hotel Y 4.26 4.47 4.48 4.89 4.89 4.95 hotel V 3.25 3.35 3.37 3.59 3.59 3.59 hotel U 3.05 3.14 3.16 3.37 3.37 3.43 lena 4.15 4.33 4.21 4.65 4.65 4.61 pyramid 2.97 3.11 3.30 3.51 3.28(4) 4.14 couple 2.25 2.48 2.56 2.74 2.42(4) 3.58 MRI brain 4.35 4.62 4.51 4.9 4.9 4.96 MRI head 2.55 2.81 2.87 2.97 2.97 3.66 lung X-ray 2.09 2.37 2.25 2.41 2.37(4) 3.11 heart ultsnd 3.04 3.27 3.31 3.52 3.30(1) 4.17 海王星 3.04 3.26 3.54 3.69 3.56(4) 4.33

【００７３】表２において、上述の画像の代表的サブセ
ットが考察されている。表２では、各画像について、い
くつかの画像圧縮システムの場合の圧縮比率（すなわち
ピクセル当たりのビット数で数が小さいほど優れてい
る）が提示されている。この画像セットは、上述のWein
berger氏その他による文献で報告されている画像と一致
し、G.G.Langdon, Jr. および M. Mareboyanaによる "C
entering of context-dependent components of predic
tion error distributions, 11 in Proc.SPIE (Applica
tions of Digital Image Processing xvi), vol2028, p
p. 26-31記載のSunsetアルゴリズム最新技術との比較の
基礎を提供している。加えて、上記の実験結果は、(ISO
/IEC10918-1 ITU T.81. "Digital compression and cod
ing of continuous tone still images- Requirements
and guidelines, Sept.1993"に記載の)ＪＰＥＧ独立無
損失圧縮システムと比較されている。表２においてSuns
etアルゴリズムに関して報告されている結果は、計算さ
れた理想的な符号長、すなわちアルゴリズムによってデ
ータに割り当てられた確率の負の対数に対応している。
算術Ｑ符号器またはＱＭ符号器によるモデル化ステップ
を行う場合オーバーヘッドの追加が予想される。G.G.La
ngdon, Jr., A.GulatiおよびE.Seiler３氏著の"On the
JPEG model for lossless image compression," in Pxo
c.of the 1992Data Compression Conference, (Snowbir
d, Utah, USA), pp. 172-180, Mar. 1992において、(Su
nsetアルゴリズムの旧バージョンの場合)Ｑ符号器につ
いては平均３.５％、ＱＭ符号器については２.５％のオ
ーバーヘッドが報告されている。無損失ＪＰＥＧに関し
ては、表２で報告されている結果は、次の予測値数７す
なわち（ａ＋ｂ）／２、１に等しい上限動翼パラメー
タ、および０に等しい下限動翼パラメータというデフォ
ルト・パラメータ値を用い算術符号化を使用した結果で
ある。参照のため、表２は、また、特定の画像の各々に
対して、ＪＰＥＧで提案されている７つの標準的予測か
ら最善の予測が選択される（非常に非現実的な）状況を
カバーする付加的欄を含む。この方式は、表２で「７回
パスＪＰＥＧ」と表記されている。括弧内の数値は、７
でない場合の最適化された予測値を表す。Weinberger氏
等の上記文献で提案された最善の普遍的文脈モデル化オ
プションであるＤＣＸＴ−ＢＴ／ＣＡＲＰに関して得ら
れた結果もまた報告されている。別の極端な事例とし
て、デフォルトのＪＰＥＧ予測値（ａ＋ｂ／２）を適用
した後の予測残差の第１次（無条件の）エントロピーも
含まれている。この欄は、「ＤＰＣＭエントロピー」と
表記されている。表２で報告されていない画像を含む）
完全なセットに関する種々のアルゴリズムの比較も、後
述の表３に要約されているように、同様の結果を生む。
ＤＣＸＴ−ＢＴ／ＣＡＲＰを除いて、表３は、算術符号
化アルゴリズムに対して複雑でないににもかかわらず、
最高の圧縮比率をＬＯＣＯ²Ｉが達成することを示して
いる。

【００７４】

【表３】 DCXT 無損失７回パス画像 BT/CARP LOCO²I Sunset JPEG JPEG エントロヒ゜ JPEG 3.41 3.55 3.55 3.82 3.81 3.90 (27画像) usc 4.22 4.34 4.39 4.7 4.6 4.86 (26画像) 医療 2.36 2.61 2.65 2.72 2.7 3.38 (49画像) 宇宙 2.91 3.14 3.41 3.47 3.43 4.23 (3画像)

【００７５】ＬＯＣＯ²Ｉは、また、コダック・ディジ
タル・カメラで捕捉された２つのモザイク画像に適用さ
れた。各画像は、(２つのシフトされたグリーン平面、
１つのレッド平面および１つのブルー平面という)４つ
の独立したグレースケール画像として圧縮された。第１
の画像（肖像）は、無損失ＪＰＥＧの５.０２に対して
ＬＯＣＯ2Ｉでは４.５７ビット／ピクセルまで圧縮され
た。第２の画像（オフィス）は、無損失ＪＰＥＧの４.
８１に対してＬＯＣＯ²Ｉでは４.５２ビット／ピクセル
となった。（１つの画像が４つの独立した画像に圧縮さ
れる）再標本抽出プロセスによる相関減少にもかかわら
ず、ＬＯＣＯ²Ｉで得られた結果は、顕著なひずみを持
つ補間ステップを必要とする５：１無損失ＪＰＥＧ圧縮
よりもすぐれている。その理由は、圧縮される画像が全
体事後補間において２４ビットのピクセルによって形成
されるように、無損失ＪＰＥＧアルゴリズムが完全なカ
ラー平面に適用されるからである。従って、５：１圧縮
は、全体サイズを４.８ビット／ピクセルに減少させる
にすぎない。

【００７６】代替実施形態本発明の可能なバリエーションは多数存在するが、本節
でそのいくつかを記述する。本発明のバリエーションの
中には、特定の目標アプリケーションおよびそのアプリ
ケーション独自の複雑さ／圧縮上の制約に依存するもの
がある。ある場合には、稜線検出能力が、特定の複雑さ
の制約に対応しなければならない。例えば、北東ピクセ
ル値の知識を使用する予測方法は、式(3)の予測法の場
合におけるように、よりすぐれた稜線検出を提供する。
しかし、負荷の大きいモデル化ステップが文脈モデル化
ルーチンによって実行され、よりすぐれた予測法の特長
が制限されるため、複雑さの追加に値しないかもしれな
い。また、文脈の量子化は特定のアプリケーションによ
って影響を受けるかもしれない。例えば、医療画像の中
には、しきい値Ｓの最適値は、上述の画像圧縮機構２０
１で使用したデフォルト値Ｓ＝７より小さい。

【００７７】組み込みアルファベット拡張に関しては、
役に立たないと事前にわかっている符号化空間を割り当
てることが原因である冗長度(上述の「組み込みアルフ
ァベット拡張」の項で述べた)を取り除くことは可能で
ある。画像圧縮機構２０１の１つの代替実施形態は、最
大許容ラン長ｒより短くすることができる最大可能ラン
長を先ず検証することによって、この冗長度を取り除
く。より短い長さは、北東ピクセルの分割ランかまたは
境界によって実現できるであろう。両者は復号器によっ
て検出できる。符号化器７０７は、この最大長の(２と
ｒの間にある)可能な値のそれぞれについて異なる符号
を使用する。符号各々に対するアルファベット拡張ツリ
ーは、達成可能なランのみをカバーし、これによって冗
長度を取り除く。明らかに、伸張機構１２０１は、符号
化器７０７によって使用された符号を、追加情報なし
に、追跡することができる。単一のラン終了分布は、ｒ
−1の異なる符号によって共有される。別の代替的実施
形態は、必ずしもゼロ勾配ではないその他の非常に頻繁
な文脈（例えば｜ａ−ｃ｜、｜ｂ−ｃ｜、｜ａ−ｄ｜が
最高１である文脈）を処理する。

【００７８】更に別の代替的実施形態は、２回パスが不
可能なアプリケーションの場合に１回パスの符号化を提
供する。そのような実施形態では、最初の近似化が、復
号器にも使用可能な固定的ハフマン・テーブルを設計す
ることから構成される。これは、例えばＭＲＩ医療画像
のように、固有の特性をもつ同質のデータが予想される
アプリケーションで可能である。文脈モデル化は、異な
るテーブルで符号化されるクラスへピクセルを類別する
ので、本発明の固定テーブル・バージョンは適応性を維
持する。パラメータは学習されずパラメータは何も復号
器に伝えられないという意味において、これはゼロ・パ
ラメータ符号であるが、固定的テーブルを準備するため
に必要とされるデータを訓練する量を決定するので、文
脈の数はなお「モデル費用」の役割を演ずる。更にまた
別の代替的実施形態は、ハフマン符号化の代わりに、
(R.F. Rice著"Some practical universal noiseless co
dingtechniques",Technical Report JPL-79-22, Jet Pr
opulsion Laboratory, Pasadena, CA, Mar. 1979に記載
の)Rice-Golomb符号を使用する。最後に、複雑さが許容
される限り、本発明は、１回パスの算術符号を用いて符
号化を行うことも可能で、それによって、２回パスの場
合と少なくとも同等の圧縮結果を生む出すであろう。

【００７９】更に、本発明のシステムおよび方法は、図
２ないし図１３を参照して上述したように、カラー画像
の圧縮に適応できる。本発明がカラー画像に関連して使
用される方法は、画像が表現されるカラー空間に依存す
る。ＹＵＶ表示タイプは、かなり非相関的画像を生成す
るためのものと一般に仮定される。従って、これは、グ
レースケール画像として独立して圧縮することができ
る。一方、いくつかのケースにおけるＲＧＢ表示は、そ
のコンポーネント間で強い相関を提示する。従って、本
発明の画像圧縮方法を個別の平面に適用することもでき
るが、他のＲＧＢ代替方式では、予測およびモデル化テ
ンプレートが、平面間相関を記述する。１つの実施形態
において、（輝度情報の大部分を含む）グリーン平面を
グレースケール画像として圧縮し、そのピクセル値を使
用して、他の２つの平面をモデル化する。レッドおよび
ブルーの予測ルーチンは、本発明に従うカラー画像のた
めの圧縮機構を使用し、両平面間相関およびグリーン平
面との相関に基づいて、次式(10)によってブルーおよび
レッド平面を予測する。

【００８０】

【数５】上式(10)において肩文字Gはグリーン平面における対応
する値を示す。式(10)に従う予測動作は、ＪＰＥＧの予
測値７によって捕らえられる値を、上記予測法によって
グリーン平面で計算される誤差で補正するものと解読す
ることができる。無損失ＪＰＥＧに関する３カラー平面
（２４ビットのピクセル）における累算される節約
は、"girl"の場合２.６１ビット／ピクセルで、”barba
ra"の場合３.７５ビット／ピクセルである。

【００８１】下記の表４は、ＪＰＥＧセットからの２つ
の画像のＲＧＢ表現について、式（10）に従って動作す
る予測回路２０７を使用する画像圧縮機構２０５でグリ
ーン平面を圧縮することによって得られた結果(平面間
予測によるＬＯＣＯ²Ｉ)を、上述の式(2)によるＬＯＣ
Ｏ²Ｉおよび無損失ＪＰＥＧと比較して示すものであ
る。

【００８２】

【表４】

【００８３】本発明のシステムおよび方法は、ISO/IEC/
SC29/WG1委員会によって定義されている低損失圧縮法に
準拠するようにさらに適応させることができる。低損失
規格は、オリジナルのピクセルの各々とその復号された
バージョンの間の差に関して（１、２、３、７のよう
な）均一な境界ｅが存在することを必要とする。

【００８４】図１５は、画像圧縮機構２０５'の前にプ
レプロセッサ１４０１を持つ画像圧縮／伸張システムの
構成を示すブロック図である。画像圧縮機構２０５'
は、画像圧縮機構２０５と同じ設計で同様に動作する。
プリプロセッサは、許容される誤差をシステムへ受け入
れる。従って、無損失方式を実行する画像圧縮機構２０
５'にとって誤差は透過的である。

【００８５】プレプロセッサ１４０１は、各ピクセル値
を約Ａ/(２ｅ＋１)値の１つに対応させるスカラー量子
化を行い、従って、入力されるアルファベットＡのサイ
ズは減少する。更に具体的に云えば、本発明の１つの実
施形態に従って、オリジナルの画像の中の各ピクセル値
は、次式(11)にマップされる。ｙ_i＝［ｘ_i／(２ｅ＋１)］ (11) 画像におけるすべてのピクセルｘ_iを対応する値ｙ_iへ対
応付けした後、画像圧縮機構２０５'は、画像圧縮器２
０５に関して記述されたプロシージャに従って、画像ｙ
を圧縮画像ｙ'に圧縮する。対応する画像伸張機構１２
０１'は、図１３の画像伸張機構１２０１と同じ設計で
同様に動作する。伸張機構１２０１'は、画像伸張機構
１２０１に関して記述されたプロシージャに従ってｙ'
を損失なく画像ｙに伸張する。

【００８６】画像伸張機構１２０１'の後にポストプロ
セッサ１４０３が続く。ポストプロセッサ１４０３は、
スカラー逆量子化であって、次式(12)に従って再構築マ
ッピングを実行する。ｘ'＝ｙ(２ｅ＋１)＋ｅ (12) 再構築誤差の絶対値｜ｘ−ｘ'｜は、ｘ'がｘに最も近く
かつｅ mod (２ｅ＋１)に適合する正の整数であるの
で、ｅによって上限を設定される。式(12)について、ｙ
の大きい値は、Ａ−１より大きい値ｘ'にマップされ、
この場合ｘ'がＡ−１に切り下げられるかもしれない。

【００８７】本発明の別のほぼ無損失実施形態におい
て、プレプロセッサ１４０１は各ピクセル値ｘ_iを次式
(13)にマップする。ｙ_i＝［(ｘ_i＋ｅ)／(２ｅ＋１)］ (13) この代替形態において、ポストプロセッサ１４０３によ
って実行される対応する再構築マッピングは、次式(14)
に従う。ｘ'_i＝ｙ_i(２ｅ＋１) (14) この形態において、ｘ'_iは、ｘに最も近くかつ０ mod
(２ｅ＋１)に適合する正の整数である。「オーバーフロ
ー」の場合、ポストプロセッサ１４０３は、過剰値をＡ
−１に切り下げる。

【００８８】図１６は、画像圧縮機構２０５と画像伸張
機構１２０１を取り入れたコンピュータ・システム１５
０１のブロック図である。コンピュータ・システム１５
０１は、１つ以上の画像発生装置１５０５を接続するＣ
ＰＵ１５０３を備える。画像発生装置１５０５は、デジ
タル・カメラや走査器のような装置を含むこともでき
る。また、コンピュータ・システム１５０１は、（例え
ばネットワークへ直接接続あるいはモデムを経由した接
続による）ネットワーク接続１５０７を通して、ローカ
ルエリアネットワーク、インターネットまたはオンライ
ン・サービスのようなコンピュータ・ネットワークに接
続することもある。ＣＰＵ１５０３は、画像発生装置１
５０５から送られる画像を、上述の方法に従って画像を
圧縮する画像圧縮機構２０５へ送る。

【００８９】ＣＰＵ１５０３は、更に、（画像およびそ
の他のデータの記憶のため）メモリ、ディスク・ドライ
ブおよびテープ装置のような記憶機構１５０９を接続す
る。画像圧縮に続いて、ＣＰＵ１５０３は、これらの記
憶機構１５０９に画像を伝送することもある。代わり
に、ＣＰＵ１５０３は画像をネットワーク接続１５０７
に送り出す場合もある。

【００９０】コンピュータ・システム１５０１は、ま
た、圧縮画像を表示のため伸張するかもしれない。ＣＰ
Ｕは、例えばネットワーク接続１５０７を通して圧縮画
像を入手する場合もある。ＣＰＵ１５０３は、そのよう
な圧縮画像を画像伸張機構１２０１に送り、そこで、そ
の画像は、画像伸張に関して上述した方法に従って伸張
される。ＣＰＵ１５０３は、更に、ＣＲＴあるいはフラ
ットパネル・ディスプレイのようなディスプレイ１５１
１を接続する。ＣＰＵ１５０３は、表示のため伸張され
た画像をディスプレイ１５１１に送る。

【００９１】１つの実施形態において、画像圧縮機構２
０５および画像伸張機構１２０１は、ＣＰＵ１５０３の
動作を指揮するように使用できるコンピュータ命令とし
て実行される。そのような場合、画像圧縮機構２０５お
よび画像伸張機構１２０１は、記憶機構１５０９の１つ
に記憶され、本発明の方法に従って画像を圧縮し伸張す
るためＣＰＵ１５０３によって実行される。１つの代替
実施形態において、画像処理プロセッサ２０５および画
像伸張機構１２０１は、補助装置としてＣＰＵ１５０３
に装着される画像処理アクセラレータのような専用ハー
ドウェア装置である。ある種のアプリケーションでは、
コンピュータ・システム１５０１は、画像圧縮をせず画
像伸張だけを必要とするかもしれないし、またはその逆
の場合もある。そのような場合のいずれかでは、圧縮機
構２０５または伸張機構１２０１のいずれかがコンピュ
ータ・システム１５０１からはずされることもある。

【００９２】本発明を実現する最適モデルを単に例示す
るために特定の実施形態を示した本明細書の記述から、
本発明の上記以外の目的および特長が当業者に明らかに
なるであろう。本発明は、本明細書記載以外のその他の
異なる実施形態で実現することができるし、本発明から
離脱することなく、本発明のいくつかの細部は、種々の
明白な観点から修正を行うことができることは認められ
るであろう。従って、本明細書の記述および図面は、本
質的に例証を目的とするものとみなされるべきで、本発
明がそれら記述および図面に制限されるべきものではな
い。

【００９３】本発明には、例として次のような実施様態
が含まれる。（１）コンピュータを用いてデジタル画像を損失なく圧
縮する方法であって、入力装置から圧縮すべき画像を取
り出すステップと、上記画像におけるピクセルの文脈を
使用して上記ピクセルに関する予測値を決定するように
上記コンピュータを動作させるステップと、上記予測値
を実際値と比較してそれによって残差を生成するステッ
プと、文脈特有ハフマン・テーブルから上記残差の少く
とも１つに対応する符号を取り出すステップと、上記符
号を復号器へ伝送するステップと、を含むデジタル画像
圧縮方法。（２）上記コンピュータが、各文脈毎に誤差値の分布を
決定し、上記各文脈毎の上記分布を使用して上記文脈特
有ハフマン・テーブルを構築することによって、上記文
脈特有ハフマン・テーブルを決定する上記（１）に記載
のデジタル画像圧縮方法。（３）上記ピクセルに隣接する複数ピクセル間の勾配値
を決定することによって文脈を計算するステップを更に
含む上記（１）に記載のデジタル画像圧縮方法。（４）上記勾配を同程度に確からしい区域に量子化する
ことによって上記文脈を計算するステップを更に含む上
記（３）に記載のデジタル画像圧縮方法。（５）量子化することによって文脈を計算する上記ステ
ップが、上記勾配が所定の区域番号のどこに存在するか
を決定するステップを含む、上記（４）に記載のデジタ
ル画像圧縮方法。

【００９４】（６）画像の各ピクセル毎に当該各ピクセ
ルに先行して符号化された複数ピクセルに基づく文脈が
存在するように構成された画像圧縮符号化器／復号器シ
ステムであって、少くとも１つのデジタル画像を含む画
像バッファと、上記画像バッファに接続して、上記画像
バッファにおける１つのピクセルの値および該ピクセル
の文脈を決定するように動作するピクセル／文脈生成機
構と、複数の文脈特有ハフマン・テーブルを記憶するテ
ーブル・メモリと、上記ピクセル／文脈生成機構および
上記文脈特有ハフマン・テーブルに接続して、上記文脈
に基づく符号、上記ピクセル値および上記文脈に対応す
る文脈特有ハフマン・テーブルを取り出すように動作す
る符号生成機構と、を含む符号化器を備えた画像圧縮符
号化器／復号器システム。（７）上記符号化器が、上記文脈と連係して上記文脈に
基づいた上記ピクセル値を予測するように動作する予測
器と、上記予測器に接続し、対応する予測値から上記ピ
クセル値を減算することによって該ピクセルに関する誤
差値を計算する減算機構とを更に含み、上記文脈特有ハ
フマン・テーブルから上記符号を取り出すため、上記誤
差値が上記符号生成機構によって使用される、上記
（６）に記載の画像圧縮符号化器／復号器システム。（８）上記符号化器が上記文脈に連係し、１つのピクセ
ルの文脈を量子化するように動作する文脈量子化器を更
に含み、上記符号生成機構が上記量子化された文脈を使
用して１つの文脈特有ハフマン・テーブルを選択する、
上記（７）に記載の画像圧縮符号化器／復号器システ
ム。（９）上記文脈量子化器が、上記文脈の中の勾配を決定
し、上記勾配がいくつかの区域のどの区域に存在するか
を決定する、上記（８）に記載の画像圧縮符号化器／復
号器システム。

【００９５】（１０）上記文脈が、上記ピクセルの西、
北西、北および北東のピクセルから成り、上記画像バッ
ファが上記文脈ピクセルに対応する値を選択的に出力す
るように動作するように構成された上記（９）に記載の
画像圧縮符号化器／復号器システムであって、上記文脈
量子化器が、上記西および北西のピクセルを入力するよ
うに配置され、第１の差分および第１の勾配をを出力す
るように動作する第１の減算器、上記北西および北のピ
クセルを入力するように配置され、第２の差分および第
２の勾配をを出力するように動作する第２の減算器、上
記北および北東のピクセルを入力するように配置され、
第３の差分および第３の勾配をを出力するように動作す
る第３の減算器、および、上記第１、第２及び第３の減
算器から出力される上記勾配をそれぞれ入力として受け
取るように配置された第１、第２および第３の量子化器
を含み、上記第１、第２、第３の量子化器の各々が、上
記勾配およびしきい値を受け取る第１の比較器、および
上記勾配および上記しきい値の負を受け取る第２の比較
器を含み、量子化された勾配を出力し、上記３つの量子
化された勾配が１つの量子化された文脈を形成する、上
記（９）に記載の画像圧縮符号化器／復号器システム。（１１）正の範囲によって表される勾配区域の各々が対
応する負の範囲を有し、上記文脈量子化器が、負の範囲
を示す量子化された勾配を持つ文脈の各々を、正の範囲
を持つ同じ勾配を持つ対応する文脈に対応させる対応づ
けテーブルを含む、上記（１０）に記載の画像圧縮符号
化器／復号器システム。

【００９６】

【発明の効果】本発明は、ハフマン符号化と文脈モデル
化の長所を結合することによって、複雑な画像圧縮シス
テムが達成できるものと同等の圧縮比率を、複雑性の少
ない画像圧縮機構を使用して実現することができ、画像
圧縮／伸張システムの処理能力の向上およびコスト削減
という顕著な効果を奏するものである。

【図面の簡単な説明】

【図１】典型的従来技術の無損失画像圧縮方式のブロッ
ク図である。

【図２】本発明の好ましい実施形態に従う画像圧縮シス
テムのブロック図である。

【図３】本発明によって使用される因果律テンプレート
のブロック図である。

【図４】本発明に従う予測機構の１部のブロック図であ
る。

【図５】図４の続きで、本発明に従う予測機構の残りの
部分のブロック図である。

【図６】図４および図５の予測機構によって使用される
制御信号を生成する制御回路のブロック図である。

【図７】図４および図５の予測機構によって使用される
第２の制御信号を生成する第２の制御回路のブロック図
である。

【図８】図２の画像圧縮システムの文脈量子化機構とピ
クセル符号化機構のブロック図である。

【図９】図８の文脈量子化回路のブロック図である。

【図１０】図９の文脈量子化回路の勾配量子化機構のブ
ロック図である。

【図１１】図１０の勾配量子化機構の１つの勾配に関す
る量子化機構の論理図である。

【図１２】本発明に従う画像圧縮機構が符号化を行う場
合のバイナリ・ツリーの一例を示す図である。

【図１３】本発明に従う画像復号機構のブロック図であ
る。

【図１４】図１３の画像復号機構の文脈量子化機構およ
びピクセル復号機構のブロック図である。

【図１５】本発明のほぼ損失のない画像圧縮／伸張シス
テムを示すブロック図である。

【図１６】本発明に従う画像圧縮機構および画像伸張機
構を備えたコンピュータ・システムのブロック図であ
る。

【符号の説明】

２０１画像圧縮システム２０３画像バッファ２０５ピクセル・シーケンス生成機構２０７、４０１、４１１予測機構２０９文脈量子化／ピクセル符号化機構２１１符号化テーブル生成機構３０１因果律テンプレート３０３現在時ピクセル３０５北の近傍ピクセル３０７西の近傍ピクセル３０９北西の近傍ピクセル３１１北東の近傍ピクセル４０３、４１３加算器４０５、５１１シフト・レジスタ４０７、４１７、７１５、８０５、８０９マルチプレ
クサ４０９、４２３制御回路４１５、５０３、５０５、７１１、９０１、９０３、９
０５減算器４２５、４２７、５１３、５１９、８０７、９０７、１
００３比較器５２１ＡＮＤゲート７０１誤差回路７０３文脈決定回路７０５、７０７符号化器７０９符号化テーブル選択回路７１１テーブル・アレイ・メモリ８０１、８０３勾配文脈量子化器９０７量子化器９０９マッピング・テーブル１１０１アルファベット拡張ツリー１１０３、１１０４、１１０５葉（事象）１１２３ラン終了状態葉ノード１２０５、１２０５' 文脈量子化／ピクセル復号化機
構

───────────────────────────────────────────────────── フロントページの続き (72)発明者マルセロ・ウェインバーガーアメリカ合衆国95129カリフォルニア州サン・ノゼ、タッカー・ドライブ 6378

Claims

【特許請求の範囲】

【請求項１】コンピュータを用いてデジタル画像を損失
なく圧縮する方法であって、入力装置から圧縮すべき画像を取り出すステップと、上記画像におけるピクセルの文脈を使用して上記ピクセ
ルに関する予測値を決定するように上記コンピュータを
動作させるステップと、上記予測値を実際値と比較してそれによって残差を生成
するステップと、文脈特有ハフマン・テーブルから上記残差の少くとも１
つに対応する符号を取り出すステップと、上記符号を復号器へ伝送するステップと、を含むデジタル画像圧縮方法。