JPS63167526A - データ圧縮装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 以下の順序で本発明を説明する。

Ａ、−産業上の利用分野 Ｂ、従来技術 Ｃ０発明が解決しようとする問題点 り８問題点を解決するための手段 Ｅ、実施例 Ｆ６発明の効果 Ａ、産業上の利用分野 本発明は、一般的には、差分パルス・コート変調（ＤＰ
ＣＭ）データ圧縮に関する。特に本発明は、エントロピ
ー・エンコーディングのために画素（ピクセル）をモデ
ル化するための装置及び方法に関するものである。

Ｂ、従来技術 多くの場合、記録されたイメージに関連するデータは蓄
積されまたは通信されることになる。例えば、テレビ会
議では、遠隔地の視聴者に通信リンクを介して高速かつ
明瞭に連続的なグレイレベル・イメージを送る必要があ
る。また、銀行業界では、銀行小切手上の情報を、後で
検索できるように蓄積する必要がある。さらに、゛ファ
クシミリ及びそれの関連の環境においては、ある場所か
ら別の場所へテキストまたはグラフィック・イメージが
通信されることになる。

これらのさまざまな環境においては、通常、イメージは
、限定された記憶容量に収め迅速に伝送することができ
るようにコード化された形式に変換される。

ディジタル・コーディング処理においては、ある瞬間の
イメージを、各々がイメージの特定の部分をあられすよ
うな複数の画素（“ピクセル”または”ペル”とも呼ば
れる）として定義することが良（知られている。従って
、イメージはｎ個の画素からなるｍ本のラインとして見
ることができる。そして集合的に、複数の画素からなる
ラインの複数本の集まりがイメージをあられす。

各画素は対応するグレイレベルまたは暗レベルをもつこ
とに注意しな（てはならない。イメージ中に含まれるこ
の情報をコード化する１つの方法は、画素をライン毎に
走査して各画素のグレイレベルを識別することである。

例えば、左上の画素がＸｌ、１であるとする。ここで第
１の添字はライン番号に対応し、第２の添字はそのライ
ン内の画素番号に対応する。従って、第１のライン中の
第２の画素はＸ４．２である。もしラインが４８０本あ
り、各ラインが５１２個の画素から成っているなら、所
与の瞬間のイメージは、４８０Ｘ５１２画素の走査によ
って集められた情報によってあられすことができる。

各画素は典型的には、黒値（例えば０）と白値（例えば
２５５）の間の範囲に亘る対応するグレイレベルを有す
る。すなわち、所与の８ビツトである、画素のグレイレ
ベルは、２５６個の値のうちのどれかをとりうる。イメ
ージをあられすためには、イメージを、規定された様式
で、画素の値を１つずつ記録しながら走査することがで
きる。

例えば、ライン毎に進行して、イメージを連続的に記録
された画素の値Ｘ４１４、Ｘｌ、２・・・Ｘ４８０，５
１２によってあられすことができる。

尚、場合によっては、イメージの上方から下方への走査
が”フィールドと呼ばれ、”フレーム”を形成するため
に複数のフィールドがインターレースされる。例えば、
あるフィールドが、最初に走査される奇数番号のライン
を有し、別の第２のフィールドが、その後走査される偶
数番号のライ／を有する。これら２つのフィールドは併
せて単一の６フレーム”を形成する。

上述の簡単な技法によれば、各イメージを記録するため
に莫大な量のビットが必要となる。しかし、そのように
ビット量が莫大であると、記憶空間が限定され、または
高速のデータ伝送が要求されるときに、データを記憶し
データを伝送することが非実際的になってしまう。

そのような必要ビットの量の低減の問題に対処するため
に、多（のデータ圧縮技術が教示されている。

データ圧縮のある技術に、″′エントロピー・コーディ
ングと呼ばれるものがある。エントロピー・コーディン
グにおいては、事象をあられすために使用されるビット
の数が、事象確率に逆相関するように意図される。すな
わち、尤度のより高い事象が比較的短い（ビット）長さ
によって特徴づけられるコード・ワードによってあられ
され、一方尤度の低い事象は比較的長いビットによって
あられされる。

エントロピー・コーディングを実行するために、典型的
にはエントロピー・コーグは２つの入力を有する。その
第１の入力は”判断″であり、第２の入力は、判断入力
のための前後関係ないしは文脈（ｃｏｎｔｅｘｔ）を与
える状態入力である。例えば、２進判断入力は、硬貨投
げの裏表の事象や、スイッチのＯＮまたはＯＦＦの状態
や、ストリング中のビットの１または０の値をあられす
ことができる。状態入力は、通常、活動記録、理論また
は推定に基づき、判断入力をいかに処理すべきかの示唆
を与えるある文脈的なインデックスを与える。例えば、
画素が黒か白かのどちらかであるようなイメージにおい
ては、画素の異なる近傍で、その近傍の画素が白である
尤度が異なることがあり得る。すなわち、各近傍は、め
いめいが個別に推定された黒白確率比を関連づけられて
いるのである。それゆえ、判断入力に意味を与えるため
に、状態入力は判断入力に対応する近傍関係を反映する
ように設けられている。そして、状態人力に基づき、エ
ントロピー・コーグは、判断入力を適当な長さのコード
・ワードに変形する。

エントロピー・コーグに対する状態入力は、モデル化、
すなわちコード・ワードを判断に割当るために依存する
文脈を決定したことの結果である。

これのよ（知られた例としては、マルコフ状態として文
献に教示されているものがある。エントロピー・コーグ
の効率はモデル化の品質、すなわちエントロピー・コー
グに対する状態入力が、判断入力の確率の変動をどれほ
どよくあうわずかに依存する。

コード・ワードの長さの正確な割当ては、情報理論の教
示するところであり、それは事象の発生の推定確率罠基
づく。すなわち確率の推定が良好である＃ｌと、コード
・ワードの割当てがより効率的になり、そのことはより
良い圧縮につながる。

エントロピー・コーグの例は次の文献に詳述されている
。

（１）出願中の米国特許出願第０６／９０７７００号 （２）　　出願中の米国特許出願筒０６／９０７６９５
号 （３）°出願中の米国特許出願筒０６７９０７７１４号 上述の米国特許出願は本願の発明者及びその協同研究者
によって発明されたものである。

他のコーグとしてはハフマン（Ｈｕｆｆｍａｎｎ）コー
ディング・コーグ及びエリアス（Ｅｌｉａｓ）コーディ
ング・コーグがある。そのような手法は多くの刊行物に
記載されている。

データ圧縮に使用される別の技術として、１差分パルス
・コード変調（ＤＰＣＭ）”と呼ばれるものがある。基
本的なりＰＣＭの教示に従うと、１つまたはそれ以上の
近傍画素値に基づく予測値が、ある１対象の”画素、す
なわちその情報内容が現在コード化されつつある画素に
つき決定される。その対象の画素の値と予測された値の
間の差が次に、以下のコーディングのための基準として
使用される。すると、近隣の画素間に高い相関が存在す
る場合に、実際の測定値ではなく差分値を用いることに
よって相当な圧縮をはかることができる。典型的には、
ＤＰＣＭ技術を用いることによって２桁の圧縮を達成す
ることができる。

Ｃ１発明が解決しようとする間順点 本発明の目的は゛、高い程度の圧縮を達成するために、
ＤＰＣＭコーディング技術とエントロピー・コーディン
グ技術を結合した新規なコーディング技術を提供するこ
とにある。

Ｄ０問題点を解決するための手段 本発明によれば、殊にイメージ・データ圧縮環境におい
てデータ圧縮率を高めるために、ＬＪＰＣＭコーディン
グがエントロピー・コーディングと組合わせて使用され
る。

さらに詳しく説明すると、画素が１つずつ１対象”画素
として選択される。その対象画素の近くに隣接画素が存
在する。量子化テーブルに基づくと、各隣接画素の大き
さは量子化レベルによってあられされる。例えば、１か
ら９までのしきい位差分信号値が第１の量子化レベルで
あり（例えば値ｎ　４ｎによってあられされる）、１０
から１７までが第２の量子化レベルであり（例えば値”
１２″によってあられされる）、それから複数の量子化
レベルを経て２４９から上が最終の量子化レベルである
（例えば”２５５”によってあられされる）。一方、量
子化レベルは、再マツピング（ｒｅｍａｐｐｉｎｇ）さ
れる。　この再マツピングにおいては、好適には最底量
子化レベルを含む第１のセットがビット０からなる２進
ストリングとして再マツプされる。その次に高い量子化
レベルを含む第２のセットが、ビット０の後の下位（最
下位）ビットに少くとも１つのビット１が続く２進スト
リングとして再マツプされ、最高量子化レベルを含む最
後のセットが、すべてビット１からなる２進ストリング
としてマツプされる。各隣接画素は、対応する再マツプ
値をもつ。

隣接画素の再マツプされた値は、対象画素の画素近傍を
あられす単一の値を与えるために合併（ａｇｇｒｅｇａ
ｔｅ）される。尚、この再マツピングと合併の段階は、
慣用的なマルコフ−モデルよりも、可能な状態の数を指
数関数的に低減させる働きをすることに注目されたい。

一般的には、再マツプ値の合併により、ｍ　Ｎ（ｍ傘車
Ｎ）個の可能な履歴表現（または状態）からｍ個の履歴
表現（または状態）への隣接画素の２進表現における低
減がはかられる。ここで、Ｎは隣接画素の数であり、ｍ
は各隣接画素毎の可能な再マツプされた値の数である。

尚、以下の説明において、単一アスタリスク中が数式中
にあられれたときはそれは乗算をあられすものとし、２
重アスタリスク本車が数式中にあられれたときはそれは
指数をあられすものとする。

さて、対象画素の左の画素がＡ、左上対角画素がＢ、上
方画素がＣ１右上対角画素がＤであるとすると、再マツ
プされた大きさの値Ｍ　Ｍ　ｎが割当てられる（ここで
ｎは画素Ａ、Ｂ、ＣまたはＤである）。大きさの状態を
決定する際に、好適には次の合併式が適用される。

状態　　　　　　　　定　義 □　　　　　　　Ｍｍａｘ＝００００ １　　　　　　　Ｍｍａｘ　＝０００１２　　　　　　
　Ｍｍａｘ＝００１１ ３　　　　　　　Ｍｍａｘ＝０１１１ ４　　　　　　　Ｍｍａｘ　＝１１１１ここでＭｍａｘ
＝ＭＭＡ　ＩＭＭＢ　ＩＭＭＣＩＭＭＤである（この説
明においては、縦線１は論理ＯＲをあられすものとする
）。

再マツピングと集合化の手法を採用することにより、本
発明は、実施が簡単であり計算の効率を高めるという目
的を達成する。

尚、各集合値は、対象画素に隣接する画素のＤＰＣＭの
大きさを反映する個別の１大きさの”状態（０から４ま
で）に対応することに注意されたい。すなわち、対象の
画素の隣接画素から決定される合併された大きさの状態
が、その対象画素に対応するＤＰＣＭ値の確率の履歴、
または文脈をあられす。合併された大きさの状態は、Ｄ
Ｐ　０Ｍ値を圧縮するために使用されるエントロピー・
コーグへの状態入力として作用する。

その合併値に対応する合併された大きさの状態はまた、
適応性量子化においても使用される。特に、複数の量子
化器が与えられる。それらの量子化器のうちの１つは対
象画素のために選択され、その選択は対象画素に対応す
る大きさの状態に基づく。

その合併値に対応する合併された大きさの状態はまた、
適応性予測にも使用される。本発明によれば、ＤＰＣＭ
コーディングのために複数の選択可能な予測器が設けら
れる。すなわち、差分（信号）値を与えるために対象画
素に対応するグレイレベル値から引き算するべく複数の
予測器のうちの１つが選択される。予測器の選択は、対
象画素に対応する大きさの状態によって決定される。

本発明によれば、隣接画素の差分信号値が量子化され再
マツプされ、再マツプされた値が合併される。この合併
値は、対象画素の周囲、履歴、または文脈をあられす大
きさの状態を表示する。この大きさの状態は、（１）エ
ントロピー・コーグに状態入力を与え、（２）対象画素
のために複数の量子化器のうちの１つを選択するための
入力を与え、（５）対象画素のＤＰＣＭコーディングに
おける差分値を決定する際に使用する複数の選択可能な
予測器のうちの１つを選択するための入力を与える、と
いう３重の機能を果たす。

選択された予測器と選択された量子化器は任意の所与の
大きさの状態について常に同一であるけれども、それら
が状態に応じて変化し得る。この特徴は、従来技術の他
のアルゴリズムに比較して、システムの計算必要量を相
当に減少させる。

切換予測は、グラフィック及びテキストなどのきわめて
非類似のグレイレベル・イメージを有効に処理すること
において、本発明の優秀さを担う主要な要因である。切
換量子化は、約７％高い圧縮率を担う主要な要因である
。

このコーディング手法は、好適にはエントロピーのコー
ディングのためにＤＰＣＭの符号とＤＰＣＭの大きさを
分離することに注目されたい。すなわち、上述したＤＰ
ＣＭの大きさの処理のみならず、本発明はまたＤＰＣＭ
符号モデルをも与える。大きさのモデルと同様に、符号
モデルは（例えば、強い負から強い正までの）複数の可
能な符号値を与え、これはある式に従って”符号”状態
を生成するために合併される。

好適な符号モデルはＤＰＣＭ符号を２進形式で（、）符
号なし０００、（ｂ）″弱いプラス”　ｏ　ｉ　ｏ、（
ｃ）１弱いマイナス”００１、（ｄ）″強いプラス”１
１０、（、）″強いマイナス”　ｉ　ｏ　ｉのように表
示する。これらの２進表示のうちの１つが各々の隣接画
素に加えられ、ＭＳｎ（ｎは画素Ａ、Ｂ、ＣまたはＤで
ある）として示される。ＤＰＣＭ符号状態を合併する際
に、好適には次の式が適用される。

ＭＳＡ；（ＭＳＡＩＭＳＢＩＭＳＣＩＭＳＤ）ここでセ
ミコロン；は連結をあられす。

これから、それに対応するＤＰＣＭの大きさの値及び状
態が決定され、それに対応するＤＰ　ＣＭ符号及び状態
が決定される。各対象画素につき、その大きさが、対応
する大きさの状態上の条件つキテエントロピー・エンコ
ードされ、その符号が対応する符号状態上の条件つきで
エントロピー・エンコードされる。大きさと符号の状態
は履歴データのみを用いて生成されるので、それらは伝
送する必要がな（、すなわち、デコーディング装置もま
た履歴からその状態を生成することができる。

上述の各特徴、すなわち（、）大きさの状態の数を減ら
すために再マツプされた大きさの値を併合スルコト、（
ｂ）エントロピーφコーディング、適応性量子化及び適
応性予測のために対象画素の活動または履歴に対応する
大きさの状態を採用すること、及び（ｃ）ＤＰＣＭ差分
値の大きさと符号のエントロピー−エンコーディングで
個別のモデルを与えることにより、実施の容易さと、計
算の効率と、すぐれた圧縮性能がもたらされる。

本発明は、（写真のように）イメージが固定されている
場合にも、（テレビやテレビ会議伝送の場合のように）
イメージが時々刻々と変化する場合にも適用可能である
。

さらに、本発明は、画素以外の事象が画素と同様にして
処理されるような、イメージ・データ処理以外の環境に
も拡張される。

Ｅ、実施例 第１図を参照すると、複数の画素Ａ、Ｂ、Ｃ１Ｄ及びＸ
を含むイメージの一部が図示されている。

ここでこのイメージが左から右へ１ラインずつ下方へ走
査されると仮定すると、対象画素Ｘが現在のライン中の
現在の画素であると考えられる。画素Ａは画素Ｘの直前
に走査された画素である。また、画素Ｂ、Ｃ及びＤは、
前に走査されたライン中の画素をあられす。

本発明によれば、画素ＡからＤまでが画素Ｘの隣接画素
をあられす。そして、この隣接画素に関連する情報が、
エントロピー・コーディング及びＤＰＣＭコーディング
を使用することによって画素Ｘに含まれている情報をコ
ーディングする際に使用される。

第２図を参照すると、データ圧縮エンコーダ１００が図
示されている。これにおいて、（画素Ｘの）グレイレベ
ル値Ｘが予測値Ｐとともに加算器１０２に入る。加算器
１０２はＸからＰを減算して出力として差分信号を与え
る。この差分信号は量子化器１０４ａないし１０４Ｃに
向げられる。

各量子化器１０４ａないし１０４Ｃは差分値をあるレン
ジで単一の量子化レベルに関連づける。すなわち、各量
子化器１０４ａないし１０４Ｃは差分値入力を、テーブ
ルに基づき量子化された出力に変換する。これに関する
２つのテーブル１及びテーブル２が以下に示されている
。

テーブル１ ＴＨＲＥＳＨＶ 判　　　断 ２＊　　１７　　　　　２傘　１２ ２＊　　ｉ８　　　　　２率　２２ ２本　７３　　　　２申　６４ ２＄　　９２　　　　　２中　８２ ２＊１５６　２１１２４ ２４１６１　　　　　２＊１４８ ２本１８８　　　　　２＄１７４ ？２１７　１２０２ ２＄２４８　２＄２３２ 上記より大きい　　　　２本２５５ テーブル１の第１列ＴＨＲＥＳＨＶは大ぎさの差分値の
範囲を示し、第２列は各範囲に関連づけられた量子化レ
ベル（Ｑｎ）を示す。テーブル１は１４個の範囲と、そ
れに関連づけられた１４個のＱｎ値を有する。尚、判断
しきい値レベルと量子化レベルにはそれぞれ２が掛けら
れていることに注意されたい。判断しきい値と量子化レ
ベルを２倍することによって、精度のための余分なビッ
トが実現される。この余分なビットを設けた理由は、予
測値とＤＰＣＭ差分値も余分な桁の精度で計算されるか
らである。実験によると、このようにして算術計算が実
行されたときに圧縮の改良がはかられたことが分かった
。以下に示すテーブル２は１２個の範囲と１２個のＱｎ
値を有する。テーブル２は、量子化範囲が少ないという
点でテーブル１よりもやや粗い。

テーブル２ 判　　断 ２本　１５　　　　　２＄　　　６ ２申　３２　　　　２申　２２ ２＄　５２　　２＊　４２ ２１　７３　　　　　２中　６２ ２率１３６　　　　　２＄１２４ ２傘１８８　２１１７４ ２中２１７　　　　　２本２０２ ２申２４８　　　　　　２１２３２ 上記よりも大きい　　　　２＄２５５ テーブル１の第１の範囲は０から２１９−１の範囲に亘
り、量子化レベル２申４によって識別される。この範囲
の値にはすべて値２中４が割り当てられている。第２の
範囲は２率９から２＊１７−１に亘り、この範囲のすべ
ての値には値２＊１２が割り当てられている。そして、
第３の範囲から第１３番目の範囲も同様に定義され、そ
れぞれＱｎ値が割り当てられる。第１４番目の範囲は２
本２４８以上から無限に亘り、それは量子化レベル２＊
２５５によってあられされる。テーブル２も同様に構成
されているが、範囲の区分けがやや粗い。

第２図に戻って、論理回路（量子化器セレクタ）１０６
は、量子化器１０４ａないし１０４Ｃのうちの１つを選
択する。再構成された画素データを生成するべ（（この
ことはＤＰＣＭコーダコーグて慣用的である）入力用加
算器１３０からもたらされたセレクタ出力は他の２つの
構成要素に入力を与える。第１に、対応する符号によっ
て拡張された量子化レベル出力の表現がエントロピー・
エンコーダ１０８に入力する。この表現は、量子化レベ
ルの２進数表現でよいが、より一般的には、エントロピ
ーｅコーディング処理を容易ならしめる表現（Ｑｎトリ
ー）であろう。エントロピー・コーグ１０８は判断入力
（例えば、量子化レベルをあられす判断入力）と、それ
に割当てられたコードを入力する。所与の判断に割当て
られたコードは、所与の判断が生起する確率に逆相関す
る長さをもつ。すなわち、ある量子化レベルの尤度が高
ければ高いほど、エントロピー・エンコーダ１０日によ
ってそれに割当てられるコードが小さいという訳である
。

エントロピー・エンコーダ１０８は好適には、前記米国
特許出願第０６７９０７６９５号に記載されているよう
な算術コーディング・エンコーダである。あるいは、エ
ントロピー・エンコーダ１０８は、ハフマン（Ｈｕｆｆ
ｍａｎｎ）コーディング・エンコーダであってもよい。

エントロピー・エンコーダ１０８は、（符号によって拡
張された）量子化レベルのみならず、状態入力も印加さ
れる。

後述するように、状態入力は、判断入力のための文脈を
与える。例えば、エントロピー・エンコーダ１０８は、
判断確率のテーブルと、現在の判断確率を示すためのポ
インタと、特定の次の判断の生起に応答して現在の判断
確率に続く次の判断確率を選択する方法を含んでいても
よい。すなわち、判断のタイプが異なるか、または判断
が同一であっても基づ（履歴が異なる場合、確率テーブ
ル中のポインタの位置が異なる。状態入力は、確率テー
ブル中で、次の判断を処理する前に確率テーブル中のど
の位置にポインタが位置づけられるべきかを示す。状態
入力については、前述の米国特許出願第０６７９０７６
９５号及びエントロピー・コーディングの文献中に述べ
られている。

第２図の実施例において、さらに２つの状態入力が示さ
れている。その一方は符号モデル１１０のための状態入
力をあられし、他方は大きさモデル１１２のための状態
入力をあられす。これに関連して、ＤＰＣＭが符号とい
う観点の導入をもたらすということが観察される（Ｘか
らＰを減算する際に、差分値は正または負のどちらかに
なり得る）。ＤＰＣＭ符号に関する情報は、ＤＰＣＭ（
量子化レベルの）大きさの情報とともにエントロピー・
エンコーダ１０８に供給される。ＤＰＣＭ符号情報は、
十または−をあられす単なる１ビツトであり、このビッ
トは、ＸとＰとを比較する比較器（図示しない）によっ
て容易に決定される。

エントロピー・エンコーダ１０８に対する判断は、量子
化レベル・タイプの情報かまたは符号タイプの情報のど
ちらかである。量子化レベル情報がエントロピー・エン
コーダ１０８に入力されるとき、大きさ状態入力がエン
トロピー・エンコーダ１０８に印加され、符号情報が入
力されるとき、符号状態入力が印加される。

選択された量子化器１０４ａないし１０４Ｃからの量子
化レベル出力Ｑｎとそれに関連する符号がモード・ルッ
ク−アップ・テーブル（ＬＵＴ　）１１４に入力される
。ルック・アップ・テーブル１１４において、量子化レ
ベルが、きわめて低減された数の代表値に再マツプされ
る。同様に、差分値の符号も、次の２進値定義に従って
再マツプされる。すなわち、その２進値定義とは、（、
）符号なしが０００（大きさゼロ）に対応する、（ｂ）
”弱いプラス”が０１０に対応する、（ｃ）″弱いマイ
ナスパが００１に対応する、（ｄ）”強いプラスパが１
１０に対応する、及び（、）”強いマイナス”が１０１
に対応する、である。

画素ｎの再マツプされた大きさはＭ　Ｍ　ｎと定義され
、画素ｎの再マツプされた符号はＭ　Ｓ　ｎと定義され
る。

以下のテーブル６及び４は、２つの量子化テーブル１及
び２のための、本発明に基づく再マツピング・スキーム
をあられす。

ロ　　　ロ　　　ロ　　　ロ　　　ロ　　　ロ　　　０
　　　ロロ　　　ロ　　　ロ　　　ロ　　　０　　　ロ
　　　ロ　　　Ｏｒ　　　　？”　　　　ｒ　　　　Ｐ
　　　Ｆ　　　ｒ　　　　Ｆ　　　ｒｖ＋？＋ｖ＋ｆ＋
−一一− ｆｆ　　　　？＋　　　ｆ＋　　　？　　　　ｒ　　　
　ｒ　　　　ｒ　　　　ｒ“　−Ｗ　　　　ｒ　　　ｒ
　　　　ｒ　　　　ｒ　　　　ｖ＋　　　ｒ（’Ｊ　　
　へ　　　寸　　の　　　寸　　　へ　　　へ　　　の
の　　　ロ　　　ヘ　　　寸　　　ｈ　　　ロ　　　唖
　　　のＰ　　　−−−ヘ　　　ヘ　　　ヘ ４）４Ｉ　　　　　　畳　　　　　畳　　　　　畳　　
　　　費　　　　　費　　　　　費へ　　ヘ　　ヘ　　
（Ｎ　　　へ　　へ　　ヘ　　ヘＣ’Ｊ　　　哨　　℃
　　−の　　へ　　の　　杓へ　　　−蛸　　　℃　　
　の　　　−マ　　ベ一　　　−−Ｆ　　　〜　　　〜
　　Ｄ斧　　　　　優　　　　　骨　　　　　畳　　　
　　畳　　　　　畳　　　　　４Ｉ−Ｌ−６へ　　ｃＮ
　　　へ　　へ　　へ　　ヘ　　へ　　圓円 ０　　　ロ　　　ロ　　　ロ　　　ロ　　　Ｏロ　　　
ロロ　　　ロ　　　ロ　　　ロ　　　ロ　　　ロ　　　
ロ　　　ロへ　　へ　　寸　　の　　寸　　ヘ　　ヘ　
　唖の　　　ロ　　　ヘ　　　寸　　　ト、　　　ロ　
　　（イ）　　　罰ｒ　　　　Ｆ　　　ｒ　　　　−へ
　　　ヘ　　　ヘ臀　　　　　畳　　　　　骨　　　　
　畳　　　　　骨　　　　　骨　　　　　骨　　　　　
骨ヘ　　へ　　へ　　ヘ　　ヘ　　ｃＮＪＣ’Ｊ　　　
へへ　　（イ）　　噂　　−の　　ＮＯ）　　　初へ　
　　−つ　　　℃　　の　　　−寸　　長ｒ　　　　−
ｒ　　　　ｆ＋　　　ヘ　　　ヘ　　０畳　　　　　畳
　　　　　骨　　　　　骨　　　　　畳　　　　　倚　
　　　　骨　　　　↓（（Ｎ　　　へ　　へ　　へ　　
へ　　ヘ　　ヘ　　「口利 １つずつの画素（対象画素）の再マツプされた大きさの
値、及び再マツプされた符号の値がテーブル１１４中で
ルック争アップされ、履歴モード遅延要素１１６中に記
憶される。（現在の対象画素である）画素Ｘの隣接面素
人ないしＤすべての再マツプされた大きさの値及び再マ
ツプされた符号の値が遅延要素１１６に記憶される。、
符号モデル１１０と大きさモデル１１２は入力としてこ
れらの再マツプされた符号値及び再マツプされた大きさ
値を受け取り、それに応答して個別の状態を発生する。

次に大きさモデル１１２について説明する。

太きさもデル 前述の再マツプ段階において、テーブル１０１４個の量
子化レベル及びテーブル２０１２個の量子化レベルは、
００００．０００１．００１１．０１１１または１１１
１の５個の４ビット表現のうちの１つによってあられさ
れる。再マツプ・スキームを観察すると、量子化レベル
が高（なるほど、より多くのＭ　Ｍ　ｎの下位ビットが
セットされることか見てとれる。そして、最下位量子化
レベルに対しては、再マツプ値が００００である。最高
位量子化レベルに対しては、再マツプ値が１１１１であ
る。

遅延要素１１６中に記憶されているＭＭ値を使用するこ
と罠よって、大きさモデル１１２が現在の対象画素の大
きさの状態を次のように定義する。

Ｑ　　　　　　　　　　　　Ｍｍａｘ＝００００１　　
　　　　　　　　　　Ｍｍａｘ＝０　０　０　１２　　
　　　　　　　　　　Ｍｍａｘ＝ＯＯ１１３Ｍｍａｘ＝
０　１　１　１ ４　　　　　　　　　　　　Ｍｍａｘ＝　１　１　１　
１ここで、Ｍｍａｘ＝＝ＭＭＡ　Ｉ　ＭＭＢ　Ｉ　ＭＭ
ＣＩＭＭＤこの式に基づくと、５個の状態０ないし４の
うちの１が現在の対象画素（画素Ｘ）に帰因する。

この状態は、その量子化レベル入力のための文脈を与え
るために大きさ状態入力としてエントロピー・エンコー
ダ１０８に入力される。

画素Ｘに対応する大きさ状態は、（前に走査され処理さ
れた）隣接画素中の”活動度”の固有の測度である。特
に、併合式の結果は、隣接画素の一ゲシュタルト（形態
）タイプの図式を与える。すなわち、４個の隣接画素に
おける２“（αはある正の整数）個のグレイレベル差分
が量子化レベルに割当てられる。この量子化レベルは、
４ビツト長のＭ　Ｍ　ｎ値に再マツプされ、状態口ない
し４を決定する際に隣接画素値の”最大”のもののみが
使用されるように上述の式が再マツプされた値に適用さ
れる。

大きさの状態はまた、複数の予測器１２６ａないし１２
６Ｃのうちの１つを選択するセレクタ１２４と、複数の
量子化器１０４ａないし１０４Ｃのうちの１つを選択す
るセレクタ１０６に入力を与える。この適応性予測及び
適応性量子化の処理について、以下でより詳細に説明す
る。

大きさの状態値（０ないし４）はまた、量子化器セレク
タ１０６にも指向される。好適な実施例においては、テ
ーブル１及び２によってあられされる２つの量子化器の
うちの１つが次のスキームに従って選択される。

状態０の場合： Ｉ　Ｆ　　Ｄ　Ｉ　ＦＦＭ＜　１０　　ｔｈｅｎ：Ｑ　
ｎ　＝　Ｏを割当て １ｓｅ Ｑｎを決定するためにテーブル１を 使用 ｎｄｉｆ 状態１の場合： Ｑｎを決定するためにテーブル１を 使用 状態２．５及び４の場合： Ｑｎを決定するためにテーブル２を 使用 ここでＤ　Ｉ　ＦＦＭは、画素ＸにおけるＤＰＣＭ差分
値の大きさの２倍である。尚、状態０の場合、Ｑｎ＝Ｏ
という追加的な値が含まれることに注意されたい。

より粗い量子化を導入することによって、イメージの歪
みの実効値が増加するが、この増加は、知覚される歪み
においては同様の増加としては反映されない。実験によ
れば、テーブル２の粗量子化器はイメージの活動性領域
でのみ使用されるので、増加した歪みは、人間の視覚の
マスキング効果によって隠されることが分かった。

量子化セレクタ１０６（第２図）の量子化レベル出力は
加算器１３０にも入る。

加算器１３０は、差分値（ｘ−ｐ）に大まかに対応する
量子化レベルＱと、現在の予測値Ｐとを結合して再構成
された値を生成する。以前に走査された画素に対応して
決定された再構成値の履歴が遅延要素１３２に記憶され
ている。予測器１２６ａないし１２６ｃは、遅延要素１
３２に記憶された予定の値を結合して、個別の、選択可
能な予測器の値を作成する。

好適な実施例においては、２個の予測器１２６ａ及び１
２６ｂが存在する。予測器１２６ａはＰを、画素Ａに対
応して遅延要素１３２に記憶された値に等しく設定する
。予測器１２６ｂは、Ｐ＝る。

（予測器の数に拘らず）予測器の選択は大きさの状態に
よって決定される。上述の２つの予測器１２６ａ（Ｐ＝
Ａ）及び１２６ｂ（勾配予測器Ｐ）の場合、（１）大き
さの状態０の場合、勾配予測器１２６ｂを使用し、（２
）大きさの状態１．２．６及び４の場合、予測器１２６
ａ（Ｐ＝Ａ）を使用する、という切換の方策になってい
る。このように予測器は、大きさの状態によって与えら
れる“活動性”の測度に基づき選択される。

ＤＰＣＭ符号モデル 量子化されたＤＰＣＭ差分の符号のエントロピー・エン
コーディングのモデルは、Ａ、Ｂ、Ｃ及びＤにおけるコ
ード化された差分の符号に基づ（。

このモデルにおいては、小さい量子化レベルに関連する
符号（弱符号）と、大きいレベルに関連する符号（強符
号）の間に区別がある。このシステムに使用される符号
の厳密な定義はテーブル３及び４に与えられている。す
なわち、量子化されたＤＰＣＭの大きさがゼロのとき（
例えば、大きさモデルの状態０の場合）、６符号なし”
が定義される。これらの符号の２進表現は次のとおりで
ある。

定　義　　　　　２進表現 符号なしくゼロ）　　　　０００ 弱プラス（−）−）　　　　　　０１０弱マイナス（−
）００１ 強プラス（＋＋）　　　　　１１０ 強マイナス（−−）１０１ この定義及び２進表現からは、”強”符号に対して最高
位ピント（ｍｓｂ）がセットされ、６プラス”に対して
中間のピットがセットされ、６マイナスパに対して最下
位ピッ）　（ｌｓｂ）がセットされることが見てとれる
。従って、Ａ、Ｂ、Ｃ及びＤ近傍を使用するマルコフ・
モデルは６２５個の可能な状態を生成することになる。

尚、ＤＰＣＭの大きさのモチリングの場合にも同様であ
るが、ある種の経験式に従いいくつかの状態を併合する
ことによって状態の数を低減することが望まし〜・。

この併合式は次のようである。

ＭＳＡ；（ＭＳＡＩＭＳＢ　ＩＭｓｃ　ＩＭｓＤ）ここ
で、ＭＳＡ、ＭＳＢ、ＭＳＣ及びＭＳＤは、２進表現に
おける画素Ａ、Ｂ、Ｃ及びＤの符号である。この式の結
果は、併合された状態の２進表現を与える。この状態の
２進表現（６ビツト）ゆえに、６４個の併合状態に対応
して記憶を割振るのが好都合である。しかし、上述の合
併式の場合、６５個の状態しか可能でないことが容易に
分かる。

上述の式の大きな恩恵は、それが、ＤＰＣＭ大ぎさモデ
ルの合併式に非常によく似ていることである。実際、モ
デル関数は、連続されたＭ　Ｍ　ｎ及びＭ　Ｓ　ｎ値と
して定義することができる。すなわち、 Ｍｎ　＝　ＭＭｎ　；　Ｍ　Ｓ　ｎ このモデル関数を使用することによって、符号式中の第
２の項の評価が、ＤＰＣＭ大きさ値の評価と同時に実行
される。

グレイレベル・デコーダ 第３図は、グレイレベル・デコーダ１５０をあられす。

これにおいて、２進形式で圧縮されたデータがエントロ
ピー・デコーダ１５２に入り、エントロピー・デコーダ
は出力として、インデックスを表示する２進シーケンス
（ＢＳＴＲＥＡＭＫ関する後述の説明を参照されたい）
を与える。このインデックスは、複数の逆量子化器１５
４ａないし１５４Ｃの各々におけるＱｎ値を識別する。

逆量子化器のうちの１つが、対応するＱｎ出力を与える
ためにセレクタ１５６によって選択される。

セレクタ１５６からのＱｎ及びそれに関連する符号出力
はモード・ルック・アップ・テーブル１５８に入る。モ
ード・ルック・アップ・テーブル１５８は遅延要素１６
０に入力を与え、それからの出力が、符号モデル１６２
及び大きさく活動度）モデル１６４に入る。構成要素１
５８ないし１６４は、グレイレベル・エンコーダ１ｏｏ
（第２図）中の対応する構成要素と同一である。大きさ
モデル１６４は、（、）エントロピー・デコーダ１５２
と、逆量子化器セレクタ１５６と、（ｃ）予測器セレク
タ１６６にその出力を与える。

予測器セレクタ１６６は、予測器１６８ａないし１６８
Ｃによって生成された（再構成された履歴データに基づ
く）複数の予測値のうちの１つを選択する。予測器の選
択においては、対象画素のための再構成されたグレイレ
ベル値Ｘ１を得るために、加算器１７Ｇ中で、選択され
た量子化値Ｑｎに、最も新しい選択された予測値Ｐが加
えられる。

ｘｌは遅延バッファ１７２に格納され、（以前って生成
されたｘｌ値とともに）後の予測値を計算するために使
用される。予測器１６８ａないし１６８Ｃはグレイレベ
ル・エンコーダ１００（第２図）の予測器１２６ａない
し１２６Ｃに対応し、（活動度に基づき）グレイレベル
・エンコーダ１００中の適応性予測と同様にして選択さ
れる。

２進判断トリー 第４図を参照すると、第２図に示すものと同一のグレイ
レベル・エンコーダ２００が、（統計ポインタｓｐの形
式の）状態入力と、２進算術エンコーダ２０４に対する
判断人力ＹＮを与えるグレイスケール・モデル２０４を
有している（算術エンコーダ２０４は第２図のエントロ
ピー・エンコーダ２０４に対応する）。算術エンコーダ
２０４の出力は圧縮されたデータであり、それは要素２
０６によって転送され、第６図に示すものと同一のグレ
イレベル・エンコーダ２１０によって後でデコードされ
ることになる。グレイレベル拳デコーダ２１０は、グレ
イスケール・モデル２１４と協働して動作する算術デコ
ーダ２１２を有する。

デコーダ２１゛０の各要素は、エンコーダ２００中の各
要素に対応し、コーディングを元に戻す働きを行う。適
応性算術エンコーダと対応するデコーダは、前述の米国
特許出願筒０６７９０７７００号、第０６／９０７６９
５号及び第０６／９０７７１４号などに記載されている
。

エンコーダ２０４とデコーダ２１２の好適な実施例は、
２進判断入力を、ＹＮ入カラベルによって示唆されたも
のとして処理する。グレイレベルに関連して前に説明し
た判断は、２進ではなく多重記号（ｍｕｌｔｉｓｙｍｂ
ｏｌ）である。

２進算術エンコーダ２０４と２進算術デコーダ２１２が
、グレイスケール・モデル２０２及び２１４と協働する
ことを可能ならしめるために、グレイレベル判断は、第
２図の”　Ｑ　Ｎ　）　ＩＪ　−”ラベルによって示唆
されるような相系化（ｔｒｅｅｉｎｇ）方法によって２
値形式でフォーマットされる。

第５図には、２値判断’ｔ”）　−３００が図示されて
いる。この２値判断トリーは、多重レベル・データを２
進データ・シーケンスに変換する。すなわち、テーブル
１の１４の量子化レベル、またはテーブル２の１２の量
子化レベルの各々が２値判断のシーケンスによってあら
れされる。所与の量子化レベルをあられす２進シーケン
スは、根から葉へとトリーに従って下降することによっ
て決定される。もし左の枝が選択され、６葉゛に到達す
ると、′１″がコード化され、そうでないなら”０”が
コード化される。

各状態（０ないし４）毎に、自身の割振記憶をもつ個別
のトリーが存在する。尚、さまざまなトリーにつき、”
共通統計”領域が存在することに注意されたい。それら
のトリーのうちの１つが第５図に示すようなものである
。

第５図において、各２値判断に関連する確率分布は、そ
の２値判断とは別の２値判断とは別個に評価されること
に注意されたい。前述の米国特許出願のＱ−コーダーの
場合、このことは、トリーの各ノード毎に個別の記憶が
割振られていることを意味する。

理論的には、第５図に示されているトリーと同一の葉を
もつ別の２進トリーが、圧縮率の損失を伴うことな（使
用することができる。しかし、そのような別のトリーは
、計算の労力の増大をもたらしかねない。第５図のトリ
ーは、トリーにより生成されるシーケンスの期待される
長さが最小に近づくように量子化レベルの統計に一致す
る。

以下に示す量子化テーブル５及び量子化テーブル６は、
判断トリーを効率的に縦断するために使用することがで
きる２値判断トリーのための１６進（ｈｅｘ）コードを
示す。このシステムの好適な実施構成においては、この
１６進コードがレジスタ中にロードされ、レジスタは次
に負の数が存在するかどうか（最高位ピットが１である
かどうか）についてテストされる。各テストの後、１だ
ゆ左にシフトすることにより、レジスタはストリーム中
の次のビットのテストの準備完了となる。そして検出さ
れた負ピットが、葉または共通統計領域のどちらかを表
示する。７番目のエントリ（テーブル５におけるＱ　ｎ
　＝　２中８２、テーブル６におけるＱ　ｎ　＝２　＊
　１２４　）からは、状態に拘らず統計領域が同一であ
る。

ｖ−ｒ　　　　ｖ−ｆｆ　　　　ｒ　　　　ｒ　　　　
ｒ　　　　ｒ　　　　ｒロ　　　ロ　　　Ｏ口　　　ｏ
　　　Ｏロ　　　ロ　　　Ｏｆｆ　　　　Ｐ＋　　　ｒ
　　　　ｖ’−Ｗ　　　　ｒ　　　　Ｆ　　　ｒ　　　
　ＦＯロ　　　ロ　　　ロ　　　ロ　　　０　　　ロ　
　　ＯロＷ　　　　ｒ　　　　ｖ＋　　　ｖ＋　　　ｖ
＋　　　？　　　　ｒ　　　　ｒ　　　　ｒｒ　　　　
ｒ　　　　ｒ　　　　ｒ　　　　ｆｆ　　　　ｆｆ　　
　　ｒ　　　　ｒ　　　　ｆｆｒ　？　ｆ＋ｖ＋ｆｆ　
ｖ＋ｆｆ　ｒ　ｒｒ　　　　ｖ＋　　　ｒ　　　　ｒ　
　　　ｖ＋　　　ｒ　　　　ｒ　　　　ｒ　　　　ｒｒ
　　　　ｒ　　　　ｆｆ　　　　ｒ　　　　ｒ　　　　
ｙ−ｆｆ　　　　ｙ−ｆｆｒ　　　　ｒ　　　ｒ　　　
　ｒ　　　ｒ　　　　ｆｆ　　　　ｒ　　　　ｒ　　　
ｒロ　　　ロ　　　ロ　　　Ｏロ　　　ロ　　　ロ　　
　０　　　ローーー　　　　−へ　　　へ　　　へ へ　　へ　　へ　　へ　　へ　　へ　　へ　　ヘ　　ヘ
ｒ　　　　　ｒ　　　　　ｒ　　　　　マー　　　　で
１　　　　〒１　　　　〒１０　　　ロ　　　ロ　　　
ロ　　　ロ　　　ｏ　　　。

ロ　　　ロ　　　０　　　ロ　　　ロ　　　ＱＯｒ　　
　　ｒ　　　　ｆｆ　　　　ｆｆ　　　　Ｐ　　　ｒ　
　　　ｒｒ　　　　ｆｆ　　　ｒ　　　　ｒ　　　　ｆ
ｆ　　　　ｒ　　　？Ｆ＋ｆｆ　　　ｒ　　　　ｒ　　
　　ｆｆ　　　　ｒ　　　　ｆｆｖ＋ｒ　ｒ　ｒ　Ｗ　
ｒ　ｆｆ ｒ　　　　？　　　　ｒ　　　ｒ　　　　ｆｆ　　　　
ｒ　　　　ｒロ　　　ロ　　　ロ　　　ロ　　　ロ　　
　ロ　　　のロ　　　ロ　　　の　　　寸　　　へ　　
　−０寸　　Ｎ′）　　　へ　　へ　　へ　　ヘ　　Ｎ
口　　　ロ　　　ロ　　　ロ　　　ロ　　　ロ　　　ロ
ＸＸＨＸＸ圓べ ΦΦΦΦΦΦΦ ＡＪ：Ｉ　Ｊ　、Ｊ：Ｉ　、ＣＩ　Ｊ：　、Ｊ：＋へ　
　寸　　の　　ｑｒ　　　へ　　へ　　リロ　　　ヘ　
　　寸　　　ｈ　　　ロ　　　（イ）　　　り一一一　
　　−へ　　　ヘ　　ヘ 畳　　　　　骨　　　　　畳　　　　　費　　　　　骨
　　　　　畳　　　　　脣へ　　　　ＣＩ　　　　ＣＩ
　　　　へ　　　　ＣＩ　　　　ＣＩ　　　　（Ｎｖ＋
　　　Ｆ　　　−Ｆ　　　ヘ　　　ヘ　　Ｄ骨　　　　
　畳　　　　　費　　　　　畳　　　　　費　　　　　
畳　　　　み（へ　　へ　　へ　　へ　　ヘ　　ヘ　　
圓門 例えば、テーブル５のビット・ストリームｆｉ検査する
と、２本４に対応する第１のテーブル・エントリＱ１が
１６進８０００または２進１００ｏｏｏｏｏｏｏｏｏｏ
ｏｏｏであられされることが見てとれる。第２のテーブ
ル・エントリＱ２は２＊１２に対応し、１６進４０００
または２進０ｉｏｏｏｏｏｏｏｏｏｏｏｏｏｏによって
あられされる。テーブル５の７番目のエントリＱ７は、
２進シーケンスｏｏｏｏｏｏｉ　１ｏｏｏｏｏｏ。

Ｏ（すなわち１６進０３００）によってあられされる。

再び第２図を参照すると、トリー処理は、エントロピー
・エンコーダ１０８に至る判断入力線に沿って配置する
ことができる変換器によって実行し得る。あるいは、各
量子化器１０４ａないし１０４ｅ中で量子化レベルを個
々の２進シーケンスに変換し、以てトリーの２進シーケ
ンスがエントロピー・エンコー・ダ１０８の入力に直接
与えられるようにすることもできる（これは第２図中に
示唆されている手法である）。より好適である後者の手
法は、加算器１３０とモード・ルック・アップ・テーブ
ル１１４中で必要とされる多重レベル値を移送する、選
択された量子化器からの第２の出力を要する。さらに、
もしモード再マツピングも量子化器からの第３の出力に
よって直接与えられ、以て量子化、２進化及びモード再
マツピングを記憶された単一のテーブル（テーブル５ま
たはテーブル６参照）から実行することを可能ならしめ
るなら、さらなる能率の増大がもたらされる。

どの場合にも、２＊４または２１２５５などの値が入力
としてエントロピー・エンコーダ１０８に与える代わり
に、１００００００００００００００ｏまたはｏｏｏｏ
ｏｏ　ｉ　ｏｏｏｏｏｏｏ　ｉ　。

などの２値判断入力のエントリーをトリー変換が与える
。

状態Ｏにおいては、上述の適応性量子化器がＱｎ＝０と
いう値を発生子ることかできる。この固有の場合は、上
述の方法が適用される前に単一の２値判断により個別に
コード化される。すなわち、状態０においては、Ｑｎが
ゼロでないときのみ上述のトリーが生成される。

の実施 （ＱＣＧＲＡＹと呼ばれる）Ｑ−ニーダ２進算術コーデ
ィングを行うグレイレベル・コーディングが、以下に示
すアルゴリズム及びテーブルに基づきＩＢＭパーソナル
−コンピュータＡＴ上で実施された。

以下に示すテーブル７及び８は、適応性量子化のために
使用され、それらはテーブル５及び６に対応する。それ
らのテーブルはＴＨＲＥＳＨＶ（９ビット精度のため２
倍されている）、Ｑｎ　（９ビット精度のために２倍さ
れている）、ＢＳＴＲＥＡＭ（Ｑｎをエンコードするた
めのトリー・ピット・パターン）、正符号のためのＭｎ
＋及び負符号のためのＭｎ−のそれぞれのためのエント
リをもつ。最後の４ピツトは留保されているが、不使用
である。テーブル・ポインタを１２バイトだけ増分する
ことにより、テーブル中の次の行がアクセスされる。テ
ーブル７は大きさ状態０と太きさ状態１のために使用さ
れる。テーブル８は大きさ状態２．３及び４のために使
用される。

Ｏロ　　　ロ　　　ＯＯロ　　　ロ　　　ロヘ　　へ　
　へ　　へ　　へ　　ヘ　　へ　　・１雇用 ロ　　　ロ　　　ロ　　　ロ　　　ロ　　　ロ大きさを
コーディングする際に使用される統計領域は、状態の各
々に割当てられた連続的な５つのセルからなる。各セル
は、状態０に割当てられた、３２バイトをもつセルを除
いては２８バイトの記憶領域をもつ。状態０セルに割当
てられたこの余分の４バイトはＱ　ｎ　＝　Ｏ判断の統
計のためのものである（状態０では、ＴＨＲＥＳＨＶ＝
ＴＨＲＯ＝２傘５としてＱ　ｎ　＝　０レベルがテーフ
゛ルアの開始地点に始まれている）。各セルの２４バイ
トは、第５図中のＱ１〜Ｑ６に対応する６個の２値判断
の統計のために使用される。各セル中の最後の４バイト
は、対応する状態によって使用されるテーブル（７また
は８）のアドレスを記憶するために使用される。各ボッ
クスが４バイト単位をあられすような次の表が、この構
造をあられす。

状態０ ＋−−−−−−−−−−−−−−−−−−−−＋ｌ　　
　　　ＱＮ＝０　　統計　　　　ＩＩ　　　　　　Ｑｌ
　　統計　　　　ＩＩ　　　　　　Ｑ２　　統計　　　
　　ＩＩ　　　　　　Ｑ５　　統計　　　　　１１　　
　　　　Ｑ４　　統計　　　　　１１　　　　　　Ｑ５
　　統計　　　　　ＩＩ　　　　　　Ｑ６　　統計　　
　　　１１　　テーブル７のアドレス　　１ 状態１ 十−−−−−−−−−−ｍ−−−−−−−−−＋ｌ　　
　　　　Ｑｌ　　統計　　　　ＩＩ　　　　　　Ｑ２　
　統計　　　　ＩＩ　　　　　　Ｑ３　　統計　　　　
　１１　　　　　Ｑ４　　統計　　　　Ｉ Ｉ　　　　　　Ｑ５　　統計　　　　　ＩＩ　　　　　
　Ｑ６　　統計　　　　　１１　　テーブル７のアドレ
ス　　１ 状態２．３、または４ ＋−−−−−一−−−−−−−−−−−−−−十ｌ　　
　　　　Ｑｌ　　統計　　　　　１１　　　　　　Ｑ２
　　統計　　　　　ＩＩ　　　　　　Ｑ３　　統計　　
　　　ＩＩ　　　　　　Ｑ４　　統計　　　　　ＩＩ　
　　　　　Ｑ５　　統計　　　　　ＩＩ　　　　　　Ｑ
６　　統計　　　　　１１　　テーブル８のアドレス　
　１ ＱＣＧＲＡＹのフローｅチャート 第４図を再び参照すると、本発明のグレイスケール圧縮
／伸張システムが示されている。以下の構成ではグレイ
スケール・エンコーダ２００がＧＳ　ＥＭＡ　Ｉ　Ｎと
して示される。グレイスケール・デコーダ２１０は、Ｇ
ＳＤＭＡＩＮとして示される。エンコーダ・グレイスケ
ール・モデル２０２はＤＡＴＡＩＮとして画素グレイレ
ベル値を受け取り、出力としてＹＮ（ｙｅｓ／ｎｏ）単
一ビット２進判断のシーケンスを発生する。これらの判
断は、ＤＡＴＡＩＮに対する近似でありさえすればよい
ＤＡＴＡＯＵＴを発生するに十分である。エンコーダと
デコーダはＤＡＴＡＯ・ＵＴ値を履歴としてしか使用し
ない。

また、コーディング処理のための統計がどこで見出され
更新されるべきかを表示するために、（状態入力をあら
れす）統計ポインタｓｐが各判断に伴う。圧縮されたデ
ータは一度に１バイトずつ完了し、記憶するかまたはデ
コーダ２１０への転送の間に伝送することができる。デ
コーダ２１０は、２値判断のシーケンス中で各ピッ）Ｙ
Ｎを回復するために適応性算術デコーディングを使用す
る。デコーダ２１０中の統計ポインタＳＰは、エンコー
ダ２００のために生成されたのと同一の、所与の判断の
ための情報を指定する。

適応性コーグ２０４とデコーダ２１２は、圧縮データ・
ストリームの発生の一部として確率更新の段階を有する
。

尚、実施されたシステムの説明を容易ならしめるために
、次の用語定義リストを与えておく。

ＹＮ−２値判断。ＹＮ＝Ｏは、０がエンコードまたはデ
コードされたことを意味する。ＹＮ＝１は、１がエンコ
ードまたはデコードされたことを意味する。

ＴＨＲＯ−状態０におけるゼロ量子化エラーのための判
断レベル。

５ＴＡＴＳ−統計記憶領域。この領域には、テーブル７
及び８のアドレスを含むポインタも記憶されている。

５ＩＧＮＳＴＡＴ−符号（めいめいが４バイトからなる
６４エントリ）の条件づけのための統計記憶領域。

５ＴＡＴＢＩＴ−６を超える大きさビットをコーディン
グするためにすべての状態によって共有される共有統計
領域。

ＢＵＦＦ　Ｉ−もとの画素（ＤＡＴＡＩＮ）のラインを
含む入力バッファ。

ＭＢＵＦＦＥＲ−各画素のモードを含みＢＵＦＦＩから
の固定オフセットであるモード・バッファ。

ＨＢＵＦＦＥＢ−再構成された画素を含み、ＭＢＵＦＦ
ＥＲからの固定オフセットである履歴バッファ。

Ｘ−次の入力画素値。

Ａ　−Ｘの左の画素のための再構成された値。

Ｂ−Ａの上の画素のための再構成された値。

Ａが記憶される前にＢが使用される限り、ＢはＡと同じ
位置にあり得る。こうして、ＨＢＵＦＦＥＲは、あるラ
インのエンコーディング／デコーディングの間に現在の
ラインの再構成された値と置き換えられた履歴画素をも
つことができる。

Ｃ−Ｘの上及びＢの右の画素のための再構成された値。

Ｄ−Ｃの右の画素のための再構成された値。

Ｍｎ−モード・ピット・パターンのためのテーブル７及
び８を参照。実際の画素に対してｌｓｂは常に０である
。次の３ビツトは符号に関連する。

上位４ビツトは大きさに関連する。Ｉ　Ｆ　Ｆ＋は、イ
メージの右端をフラグするために使用される。

ＭＡが記憶される前にＭＢが完全に使用されている限り
、その履歴ラインのモードを、エンコーディング／デコ
ーディング処理の間に現在のラインのためのモードに置
き換えることができる。

ＭＡ−Ａのモード（符号なしのバイト）。

ＭＢ−Ｈのモード（符号なしのバイト）。

ＭＣ−Ｃのモード（符号なしのバイト）。

ＭＤ−Ｄのモード（符号なしのバイト）。

Ｍ−ＭＡ、ＭＢ、ＭＣ及びＭＤをＯＲ演算した値（符号
なしのバイト）。

ＨＰ−履歴ポインタ。Ｘ、Ａ、ＢｌＣ，Ｄ、ＭＡ、ＭＢ
ｌＭＣ及びＭＤはすべてＨＰからの固定オフセットであ
る。ＨＰに１を加えるとこれらの値は右に１つの位置だ
けシフトする。

ＳＰ−統計ポインタ。ｓｐを４だけ増加すると、ｓｐは
次の統計セットを指定する。

５ｐｓｖ−ｓｐを復元できるようにＳＰをセーブ。

ＴＰ−ＴＨＲＥＳＨＶ％　Ｑｎ、ＢＳＴＲＥＡＭ。

Ｍ　ｎ　＋、及びＭｎ−データ・セットを含むテーブル
７またはテーブル８にアドレスするテーブル・ポインタ
。ＴＰを１２だけ増加すると次のデータ・セットに移行
する。

ＴＨＲＥＳＨＡＤＤＲ−ＴＰをテーブル７または８のア
ドレスに初期化するＳＰに基づくポインタ。

ＴＨＲＥＳＨＶ−テーブル７または８からの判断レベル
。

Ｍｎ−テーブル７または８からのモード。これは、コー
ド化された差の符号に応じてＭｎ＋またはＭｎ−のどち
らかである。

Ｑｎ−テーブル７または８かもの量子化大きさ値。

ＢＳＴＨＥＡＭ−テーブル７または８からのＱｎのため
の２値判断として使用すべきビット・パターン。

ＢＩＴＳ−ＢＳＴＲＥＡＭのエンコーディングの間に一
時変数として使用される。

ＰＥＬＩ−最初のライン上の一番左の画素のためのもと
の画素値。この値は、デコーダ中で使用することができ
るようにヘッダの一部として伝送される。履歴ラインは
この値に予め初期化される。

ＰＲＥＤ２−９ピット精度予測値。画素ループ毎のエン
コーティングまたはデコーディングの開始時点で、ＰＲ
ＥＤ２は９ビット精度の再構成値を含む。

ＤＩＦＦ２−もとの画素値の２倍と予測値（９ピット精
度）ＰＲＥＤ２の間の差。

ＤＩＦＦＭ−ＤＩＦＦ２の大きさ。

５ＬＯＰＥ−Ｃ及びＢの間の差。この値は、なめらかな
領域において９ビット精度予測子を形成するためにＰＲ
ＥＤ２に加えられる。

Ｌｌ−Ｊｌｌ（Ｄグレイスケール・エンコーティング・
スキームのライン毎の画素の数。それ以上のデータがな
いときＬｌはゼロである。

Ｌ２−第２（７）グレイスケール・エンコーディング・
スキームのライン毎の画素の数。それ以上のデータがな
・いときＬ２はゼロである。

フローチャートにおけるボールド（太線強調）文字は、
他の箇所で示されているより詳細なフローチャートをシ
ンボル化したものである。エンコーダ２００とデコーダ
２１０についての同一の処理は多くの場合ボールド文字
で与えられ、その共通性を強調するため（簡単な計算で
しかない場合すらも）別個の図で説明する。すべての掛
算（り及び割算いは２のべき乗により、すなわち適当な
左シフトまたは右シフトにより実施することができる。

第６図は、走査される出力が非インターレース・ディス
プレイである場合に使用することができルクレイスケー
ル・エンコータＧ　Ｓ　ＥＭＡ　Ｉ　Ｎ　−Ｎのフロー
チャートである。ＩＮＩＴＧＳＥ（第７図）で初期化処
理が行なわれた後、１ラインの画素が入力バッファに読
み込まれる。圧縮すべき別のラインが存在する限り、各
ラインの開始時点でエンコーダはＣ０ＤＥＬＩＮＥＯに
０をエンコードする。これは、０かより確からしいと仮
定する固定確率（非適応性）を用いて０を算術コーディ
ングすることによってなされる。グレイスケールで圧縮
されたデータの１ラインの圧縮はＧＳＥｌ（第８図）で
なされる。それ以上のデータがないとき、エンコーダは
、Ｃ０ＤＥＬＩＮＥＯと同じ固定確率を用いてＣ０ＤＥ
ＬＩＮＥ１に１をエンコードする。これによりデコーダ
が、停止の時期を一意的に知ることが可能となる。ＦＬ
ＵＳＨは最終の圧縮されたデータ・ビットを伝送する。

Ｑコーグについて記述する前記米国特許出願の第３３〜
３９図には、Ｑコーグ・システムのためのＦＬＵＳＨの
詳細な実施例が与えられている。もし適応性算術コーデ
ィングの代わりに、ビットが連結されるなら、ＦＬＵＳ
Ｈは最終のバイトを完了するために十分なＱを追加する
だけである。

第７図は、グレイスケール・エンコーダ初期化処理、Ｉ
ＮＩＴＧＳＥを示す。これは、適応性算術コーグと、Ｉ
ＮＩＴＥＮＣ中の統計記憶領域の初期化から始まる。Ｉ
ＮＩＴＥＮＣ中例は、前述のＱコーグに関する米国特許
出願の第１４図（及び第１５図）Ｋ与えられている。Ｈ
ＢＵＦＦＥＲ中の履歴ラインには左上画素の値、ＰＥＬ
Ｉが入れられる。この履歴ラインは定値をもつので、最
初のライン画素の予測の間にゼロ勾配が生成されること
になる。このモードを含むバッファはクリアされる。ま
た、右端を超えるバイトがクリアされ、右端をフラグす
るために第２のバイトが不法モードＩ　Ｆ　Ｆ　＋にセ
ットされる。さらにしぎい値アドレスがセットアツプさ
れな（てはならない。

第１のフィールド自エンコーティングースキームを用い
るラインのためのグレイスケール・エンコーダがＧＳＥ
ｌ　（第８図）に示されている。５ＥＴＵＰＧＳ１　（
第９図）における初期化の後、画素毎のループが、モー
ドＭＣ及びＭＤのＯＲを含むＭで開始される。というの
は、左端ではＭＡ及びＭＢがゼロに定義されているから
である。一般的には、ＭはＭ　Ａ　、　Ｍ　Ｂ　、　Ｍ
　Ｃ及びＭＤの論理ＯＲと定義される。そのループの開
始時点で、Ｍについてその非符号関連ビット（バイト中
の上位４ビツト）がすべて０かどうか調べるための判断
がなされる。Ｍは非符号バイトであって、第８図におけ
るそれに関するすべての判断は算術的比較ではなく論理
的比較である。

もしＭの上位４ビツトが０（状態０）なら、Ｑｎ＝０と
いう特殊なコーディングが試みられる。尚、画素毎のル
ープの各反復の開始時点でＰＲＥＤ２が９ビット精度の
以前の画素を含んでいることに注意されたい。ＣＡＬＣ
ＰＲＤＳ　（第１０図）は、ＰＲＥＤ２に勾配環を加え
ることによって予測子を計算する。ＤＩＦＦ２は、入力
画素Ｘの値を２倍し、それからＰＲＥＤ２を引くことに
よって得られる。もしＤＩＦＦ２の絶対値が定数ＴＨＲ
Ｏよりも大きくないなら、Ｃ０ＤＥＹＮ１　（前記Ｑコ
ーグに関連する米国特許出願の第１９図）で１というＹ
Ｎ値がコード化される。ＮＥＸＴＰＩＸＥＬＯ（第１１
図）がＱ　ｎ　＝　０というコーディングの処理を完了
する。エンコーディング処理は、画素エンコーディング
を継続するためにループを戻る。この経路によって統計
ポインタＳＰは乱されない。

もし画素差分がＴＨＲＯよりも大きいなら、Ｃ０ＤＥＹ
ＮＯ（前記Ｑコーグに関する米国特許出願の第２１図）
が、デコーダにＱ　ｎ　＝　Ｑであることを教えるため
に０をエンコードする。最初の画素の量子化された差分
符号及び大きさはＣ０ＤＥＳ　ＩＧＮＭＡＧ（第１２図
）中でエンコードされる。ＮＥＸＴＰＩＸＥＬ（第１３
図）は次の画素を処理する準備をする。このとき、統計
ポインタＳＰは５ＴＡＴＳの開始地点にリセットされな
くてはならない。

隣接モードのどれかが状態１．２．３または４のどれか
であるなら（そのことはセットされつつあるＭの上位４
ビツトのいくつかによって表示される）、ＣＡＬＣＰＲ
ＥＤＡ（第１４図）は、何の勾配環も追加することな（
予測子のためにＰＲＥＤ２　（精度の余分のビットをも
つ前の画素）のみを使用する。こうして適応性予測が達
成される。

次に、Ｘの２倍とＰＲＥＤ２の差分としてＤＩＦＦ２が
計算される。統計ポインタは、Ｍく’ＯＥ’経路で使用
される統計上をスキップするために増分される。

次に現在の状態を識別するためにＭがＩ　Ｉ　ＥＩ、１
　！、　Ｅｌ、＋７Ｅ１及びＩ　Ｆ　Ｅ　Ｉと順次比較
される。ＳＰは、より高い状態に達する場合毎に２８バ
イトだけ増分される。その線の最後の地点を超える最初
のバイトのためのモードはｌ　Ｆ　Ｆ　＋という不法値
であり、従ってそれにより状態もやはり不法値＋　Ｆ　
Ｆ　＋となされる。この状態はＧＳＥＩからの脱出をひ
き起こす。−たんＭが次のより高い状態のための判断に
失敗すると、状態０でＱｎ＝０を処理するために、処理
は、失敗のために既に説明したのと同一の経路をたどる
。

第９図（ＳＥＴＵＰＧＳ　１　）は、ライン毎の初期化
処理の詳細を示す。ここでは、統計ポインタＳＰが、統
計記憶領域である５ＴＡＴＳのアドレスに初期化される
。履歴ポインタＨＰは入力バッファＢＵＦＦ　Ｉの開始
地点を指定する。ＰＲＥＤ２は、前のラインの左端画素
Ｃの２倍に初期化される。Ｃは、第１の画素のためにゼ
ロ勾配が自動的に生成されるようＫＢに複写される。Ｃ
及びＤのためのモードは、開始Ｍ値を作成するためにＯ
Ｒ演算される。

第１０図は、勾配項を用いての予測子の計算を示す。こ
の勾配は、ＢとＣの間の差分として計算される。次に古
いＢを、ＰＲＦＤ２の半分である新しいＡと置換するこ
とができる。次に勾配がＰＲＥＤ２に加えられる。その
結果は、０から５１０に亘る値に限定される。

第１１図中のＮＥＸＴＰ　ＩＸＥＬＯは、状態０でＱ　
ｎ　＝　０がコード化された後の次の画素のための準備
を与える。履歴に対するポインタは上方へ１位置移動さ
れる。そして、ＭＡがゼロなので新しいＭがＭＤから直
接セットされる。また、ＭＢ及びＭＣがモード０である
ことも分かつているので、ＭＢまたはＭＣからのいかな
る寄与も無視し得る。この特徴はフローチャート中に具
現されている。

第１２図は、差分の符号及び量子化された大きさをエン
コードするＣ０ＤＥＳ　ＩＧＮＭＡＧのための詳細なフ
ローチャートである。これにおいて、ＳＰの値は、符号
コーディングのための条件づげ状態の計算（ＳＥＴＳＩ
ＧＮＳＰ（第１５図））の前に５ｐｓｖ中にセーブされ
る。ＤＩＦＦ２の値は、大きさコーディングに使用する
ためにＤＩＦＦＭ中にコピーされる。もしその差が負で
ないなら、Ｃ０ＤＥＹＮ１においてＹＮの１がエンコー
ドされる。また、統計ポインタは、セーブされた値であ
る５ｐｓｖにリセットされる。量子化された大きさはＦ
ＩＮＤＱＮ（第１６図）中で見出され、それはＣＯＤＥ
ＭＡＧ（第１７図）中でコード化される。この正の場合
の経路のための再構成された画素の計算はＲＥＣＯＮＳ
ＴＲＵＣＴＰＩＸＥＬＰ（第１８図）中でなされる。負
の差の場合の経路は、０がエンコードされ量子化された
値を見出す前に正の差を得るべ（ＤＩＦＦＭが反転され
なくてはならないことを除いてはそれと同様である。Ｃ
ＯＤＥＭＡＧ内でのエンコーディングの後、この負の差
の経路のためにＲＥＣＯＮＳＴＲＵＣＴＰ　ＩＸＥＬＮ
中で画素が再構成される。

ＮＥＸＴＰＩＸＥＬ（第１３図）中で履歴ポインタが１
位置上方に移動され、以て最も新しくエンコードされた
画素を画素人として再定義する。

履歴モードＭＢ、ＭＣ及びＭＤは互いにＯＲされてＭに
セーブされる。次に、テーブル７または８かもの新しい
モードＭＮをＭＡに記憶し、やはりＯＲＬ、てＭに入れ
ることができる。

ＣＡＬＣＰＲＥＤＡ（第１４図）の処理は、ＰＲＥＤ２
の値の半分をＡに記憶すること以外要しない。ＰＲＥＤ
２は既に０から５１０の間の値にクランプされているの
で、この経路上ではアンダーフローまたはオーバーフロ
ーについてのチェックは不要である。

５ＥＴＳＩＧＮＳＰ（第１５図）は、Ｍ及びＭＡから６
つの符号ピットのみをそれぞれ選択するマスク’ＯＥ’
Ｘを示す。これらの３ビツトは、符号のための統計領域
であるＳ　Ｉ　ＧＮＳＴＡＴのアト−レスで始まる６４
個の状態から１つを選択するために使用される。尚、こ
の統計は４バイト量であるので下位２ビツトがゼロであ
ることに注意されたい。

ＦＩＮＤＱＮ（第１６図）は、適正な量子化の大きさを
決定するためのエンコーダ・ループを示す。ＳＰによっ
て指示される２８バイト統計セルのうちの最後の４バイ
ト中に見出されるＴＨＲＥＳＨＡＤＤＲが、テーブル・
ポインタＴＰを初期化するために使用される。各状態の
ための適切なテーブル（テーブル７または８）のアドレ
スが■ＮＩＴＧＳＥにセットアツプされている。このよ
うにして、適応性量子化が実施される。もしＴＰに基づ
＜ＴＨＲＥＳＨＶがＤ　Ｉ　ＦＦＭよりも小さいかそれ
に等しいなら、テーブル・ポインタがテーブル・エント
リの次のセットに移動される。そうでないなら、最終の
ＴＰアドレスに基づきＢＳＴＲＥＡＭ中でＢＩＴＳにビ
ット・ストリームがロードされる。

ＣＯＤＥＭＡＧ（第１７図）は、２値判断トリーによっ
て大きさをエンコードする。ＢＩＴＳＵ、スキップすべ
き各量子化レベルのための先行する複数のゼロを含む。

もしＢＩＴＳに１つよりも多いビット１が存在している
なら、Ｃ０ＤＥＢ　ＩＴＳＬＥＦＴ（第２０図）におい
ていくつかの余分なビットがコード化されなくてはなら
ない。Ｃ０ＤＥＹＮＯは各先行ゼロ毎に０をエンコード
し、統計ポインタが次の位置に移動され、ＢＩＴが１だ
け左ヘシフトされる。そして、もしＢ　ＩＴＳの最高位
ビットが１なら、先行ゼロの末端が見出されたというこ
とになる。１ビツトをシフトアウトした後、コード化す
べきビットがさらに残っているかどうかを調べるため残
りのビットが判断される。もしＢ　ＩＴＳがゼロでない
なら、Ｃ０ＤＥＢＩＴＳＬＥＦＴ（第２０図）が、共通
の統計領域を用いて残りのビットをエンコードする。そ
して、１をコード化することによってＣ０ＤＥＹＮ１は
処理を終了させる。

ＲＥＣＯＮＳＴＲＵＣＴＰＩＸＥＬＰ（第１８図）では
、テーブル７（または８）からのＱｎ値がＰＲＥＤ２に
加えられる。このときＰＲＥＤ２に正の値が加えられる
ので、ＰＲＥＤ２が、許容される最大値である５１０を
超えるかどうかを調べるためのチェックがなされる。そ
してもしそうなら、ＰＲＥＤ２が５１０にリセットされ
る。

ＲＥＣＯＮＳＴＲＵＣＴＰＩＸＥＬＮ（第１９図）は、
画素を負のＱで再構成するためにＰＲＥＤ２から正のＱ
ｎを引く。もしその新しいＰＲＥＤ２が負なら、ＰＲＦ
Ｄ２は、ＰＲＥＤ２に許容される最小値であるゼロにリ
セットされる。テーブル・ポインタは、ＭＮの負のバー
ジョンが後でＭＡにセーブされるように１位置移動され
る。

次の１までの残りのゼロはＣ０ＤＥＢ　ＩＴＳＬＥＦＴ
（第２０図）中でエンコードされる。統計ポインタは５
ＴＡＴＢＩＴ領域にセットされる。

これは、６つ以上の判断が必要とされるときすべての状
態の統計を集めるための領域である。各先行ゼロ毎にゼ
ロを送るコーディング処理はＣＯＤＥＭＡＧ　（第１７
図）と同様である。そして−たん１が見出されるとすべ
てのゼロがエンコードされたことになる。

第２１図は、出力が非インターレース・ディスプレイで
ある場合に使用することができるグレイスケール・デコ
ーダＧＳＤＭＡＩＮ−Ｎのフローチャートである。ＩＮ
ＩＴＧＳＤ（第２２図）で初期化処理が行なわれた後、
ＤＥＣＯＤＥＬＩＮＥ（図示しない）中で最初の判断が
デコードされる。もしＹＮが０なら、別のラインをデコ
ードする必要がある。ライン毎デコーダＧＳＤ１（第２
６図）は、記憶またはディスプレイに書かれる準備が出
来ているラインをデコードする。もしＤＥＣＯＤＥＬ　
ＩＮＥがＹＮの１を検出するなら、イメージが完全にデ
コードされたことになる。

第２２図は、グレイスケール・デコーダ初期化処理、Ｉ
ＮＩＴＧＳＤを示す。これは、適応性算術コーグまたは
統計記憶領域のための初期化がＩＮＩＴＤＥＣ中でデコ
ーダのためになされることを除けばＩＮＩＴＧＳＥＫ類
似する。ＩＮＩＴＤＥＣの例は、前記Ｑコーグに関連す
る米国特許出願の第４０図に与えられている。

第１のフィールド圧縮スキームを使用する、ラインのた
めのグレイスケール・デコーダがＧＳＤｌ（第２３図）
Ｋ示されている。５ＥＴＵＰＧＳ１（第９図）での初期
化の後、もし非符号関連ビット（バイト中の上位４ビツ
ト）がすべて０であるかどうかを調べるためのＭの値の
判断で画素毎のループが始まる。Ｍは非符号バイトであ
って、従って第２３図におけるその判断は算術的比較で
なく論理的比較である。もしＭの上位４ビツトがゼロな
ら、Ｑ　ｎ　＝　０という特殊なコーディングが試行さ
れる。ＣＡＬＣＰＲＥＤＳ　（第１０図）が勾配項と前
の画素とを用いてその画素のための予測値（ＰＲＥＤ２
）を計算する。次にＤＥＣＯＤＥ（前記Ｑコーグに関連
する米国特許出願の第２２図）が、Ｑ　ｎ　：０がデコ
ードされた（ＹＮ＝Ｏ）かどうかを判断する。ＮＥＸＴ
ＰＩＸＥＬＯ（第１１図）が、Ｑ　ｎ　＝　Ｏでデコー
ドされた画素に続く処理を完了する。このデコーディン
グ処理は、画素エンコーディングを継続するためにルー
プを戻る。尚、統計ポインタＳＰはこの経路によって乱
されない。

もしＱｎ　＝Ｏ（ＹＮ：Ｏ）なら、ＤＥＣＯＤＥｓ　Ｉ
ＧＮＭＡＧ（第２４図）において最初の画素の量子化さ
れた差の符号及び大きさがデコードされる。そしてＮＥ
ＸＴＰＩＸＥＬ（第１６図）が次の画素を処理する準備
をする。このとき、統計ポインタＳＰが動かされている
ので、ＳＰは５ＴＡＴＳの開始地点にリセットされな（
てはならない。

他方もしＭがＩ　ＯＥ　ｌよりも大きいなら、現在の状
態を識別するためにＭはＩ　Ｉ　Ｅ　Ｉ、“５Ｅ’、１
７Ｅ１及びｌ　Ｆ　Ｅ　ｌと順次比較される。また、よ
り上の状態に到達するため毎に、ｓｐが２８バイトずつ
増分される。このとき、ラインの最後を超える最初のバ
イトのためのモードがｌ　Ｆ　Ｆ　＋という不法値であ
るので、不法状態を強いることによってＧＳＤｌからの
戻りをひき起こす。Ｍが−たん次の高位状態についての
判断で失敗すると、Ｑ　ｎ　＝　Ｏを処理するために、
処理は既に説明したのと同一の失敗用の経路をたどる。

第２４図は、差分の符号と量子化された大きさをデコー
ドするＤＥＣＯＤＥＳ　Ｉ　ＧＮＭＡＧのための詳細な
フローチャートである。ＳＰの値は、符号コーディング
のための条件づけ状態の計算、すなわち５ＥＴＳＩＧＮ
ＳＰ（第１５図）の前に５ｐｓｖ中にセーブされる。Ｄ
ＥＣＯＤＥは次のＹＮ値を決定する。もしＹＮがゼロで
ないなら、正のＱｎがエンコードされたということであ
る。

統計ポインタＳＰはセーブされた値である、５ＰＳＶに
リセットされる。量子化された大きさはＤＥＣＯＤＥＭ
ＡＧ（第２５図）でデコードされる。

この正の経路のだめの再構成された画素の計算はＲＥＣ
ＯＮＳＴＲＵＣＴＰＩＸＥＬＰ（第１８図）で実行され
る。もし符号が０としてデコードされたなら、それは負
であったということである。ＳＰは５ｐｓｖからリセッ
トされる。ＤＥＣＯＤＥＭＡＧでデコードされた後、こ
の負の差分の経路に応じて画素がＲＥＣＯＮＳＴＲＵＣ
ＴＲＩＸＥＬＮ中で再構成される。

ＤＥＣＯＤＥＭＡＧ（第２５図）は大きさをデコードす
る。テーブル・ポインタが（ＳＰに基づ（）ＴＨＲＥＳ
ＨＡＤＤＲからセット・アップされる。ゼロである各Ｙ
Ｎ判断に対して、ＳＰが次の統計領域に移動され、ＴＰ
がテーブル−エントリの次のセットへ増分される。。６
個のゼロがデコードされた後に、統計ポインタｓｐを共
通統計領域へ移動する必要があり、そうしてＤＥＣＯＤ
ＥＢＩＴＳＬＥＦＴ（第２６図）中でデコーディングが
継続される。その限界を識別するためにＳＬが前取って
計算され、各ゼロの後にＳＰに比較される。

次の１までの残りのビットがＤＥＣＯＤＥＢ　ＩＴＳＬ
ＥＦＴ（第２６図）中でデコードされる。

統計ポインタＳＰは５ＴＡＴＢＩＴ領域にセットされる
。そして、各々のゼロがデコードされる毎に、ｓｐとＴ
Ｐが増分される。

インターレースされた映像を使用するディスプレイのた
めに、第２８図及び第２９図に第２のグレイスケール・
エンコーダＧＳＥＭＡＩＮ−Ｉ及びデコーダＧＳＤＭＡ
ＩＮ−Ｉシステムが図示されている。このとき、２つの
コーディング・スキームがインターリーブされている。

それらは交替的なイメージ・ライン上、すなわち第１及
び第２のフィールド上で動作する。第１のフィールド・
ラインのために使用することのできるアルゴリズムは上
述のフローチャートに詳細されている。このときもし望
むなら適応性算術コーディングを採用することができる
。第２のフィールドは、それと同一または異なるアルゴ
リズムのどれを用いて圧縮してもよい。

第２７図及び第２８図に示すように、ライン毎に２つの
技術を交番させることができる。（第２のフィールドの
アルゴリズムのだめの初期化を含むように拡張されるこ
とになる）ＩＮＩＴＧＳＥ中の初期化の後、ラインが入
力バッファ中に読み込まれる。Ｌｌは、成功裡に読み込
まれたバイトの数をセーブする。Ｌｌ（またはＬ２）が
ゼロのとき、それ以上の入力データは存在しな（・。さ
て、第１のラインがエンコードされ、次に再構成された
出力が、ＧＳＥ２のだめの履歴バッファ中にコピーされ
る。一対のラインを第１及び第２のフィールド人力バッ
ファに読み込むことができる限りは、残りの第１フイー
ルド・ラインがエンコードされ、そのあと直ぐにＧＳＥ
２における先行する第２フイールド・ラインのエンコー
ディングが続く。そして最早第１フイールド・ラインが
存在しな（なると、第１フイールドのアルゴリズムを用
いて最後の第２フイールド・ラインがエンコードされる
。あるいは、最後の第２フイールド・ラインをスキップ
することもできる。

デコーダＧＳＤＭＡＩＮ−Ｉは第１のラインをデコード
し、次に第３のラインをデコードした後筒２のラインを
デコードする。ラインの対は、ＤＥＣＯＤＥＬＩＭＥが
、それ以上のラインの対をデコードすべきでないことを
検出するまでデコードされる。最後のラインは第１フイ
ールドのアルゴリズムを用いてデコードすることができ
る。

本発明のシステムは、ハードウェアまたはソフトウェア
で簡単且つ効率的に実施できるように設計されたもので
ある。例えば、ＩＢＭＰＣ−ＡＴパーソナル・コンピュ
ータ中で５１２Ｘ４８０×８のグレイレベル・イメージ
の第」のフィールドを圧縮するのに費した典型的なＣＰ
Ｕ時間は９秒であった。このシステムの効率と簡易性は
、その大部分が本発明の特徴に起因するものである。

実験によれば、この適応性予測及び適応性量子化方法に
関連して改善がはかられたことが分かった。

尚、本発明は好適な実施例に関連して説明されたが、本
発明の範囲から逸脱することなくさまざまな変更がなし
うろことがこの分野の当業者により理解されよう。例え
ば、適応性算術コーグ及びデコーダは、Ｙｅｓ／ＮＯ判
断のビット連結で置き換えることができる。そうして、
圧縮されたデータ・ストリームのビット毎の検査がＹＮ
シーケンスを回復する。さらに、本発明は、再マツピン
グのために特定のビット表現を開示しているけれども、
その表現は本発明に従い変更することができる。例を掲
げると、再マツプされたビットは反転することができ（
例えば、弱いマイナス符号のための００１°゛を１１０
”であられしてもよい）、それに従って必要となる実施
の変更は当業者の通常の技術の範囲内にある。また、再
マツプされる２進値も異なるように定義することができ
る。例えば、最下位量子化レベルに対応する００００と
、最高位量子化レベルに対応する１１１１０代わりに、
最下位が１１１１に対応し、下から２番目のレベルが０
１１１に対応し、・・・・最高位レベルが００００に対
応するように表現を反転することができる。さらに、も
し望むなら、ビットの数を、４ビツトを超えるようにし
てもよい。再マツプ値の他の２進表現も簡単な論理の変
更で容易に置き換えることができ、そのこともまた、当
業者の通常の技術の範囲内でなし得る。

１０発明の効果 以上のように、この発明によれば、ＤＰＣＭコーディン
グ技術とエントロピー・コーディング技術を結合して高
い比率のデータ圧縮を達成する新規な技術が提供される
。

【図面の簡単な説明】

第１図は、対象画素に関連する情報のＤＰＣＭコーディ
ングに使用される対象画素とその隣接画素の位置関係を
示す図、 第２図は、本発明に基づくイメージ・データ圧縮エンコ
ーダの概要ブロック図、 第３図は、本発明に基づくイメージ・データ・デコーダ
の概要ブロック図、 第４図は、本発明のグレイスケール・エンコーディング
及びデコーディング・システムに適応性算術エンコーデ
ィング及びデコーディングが採用されてなるブロック図
、 第５図は、２値判断トリーの図、 第６図ないし第２８図は、本発明の実施例の動作を示す
フローチャートである。 １０４　ａ〜１０４　ｃ−−−−量子化器、１２６ａ〜
１２６ｃ・・・・予測器、１０８・・・・エントロピｍ
−デコーダ、１１６・・・・履歴モード遅延要素、１０
６・・・・第１のセレクタ、１２４・・・・第２のセレ
クタ。 出願人インターナショナル・ビジネス・マシーンズΦコ
＋々ン２道判断トリー 第５図 第７図 第１０図

Claims (1)

1. 【特許請求の範囲】 量子化されるべき差分信号値を与えるために入力信号値
   Ｘから予測値Ｐが引算される差分パルス・コード変調デ
   ータ圧縮装置であつて、 （ａ）差分信号入力を量子化するための選択可能な複数
   の量子化器と、 （ｂ）複数の選択可能な予測子計算手段と、 （ｃ）判断入力と、受信した該判断入力の文脈を与える
   状態入力に応答してコード出力を生成するエントロピー
   ・エンコーダ手段と、 （ｄ）量子化された差分の履歴に基づき入力信号の活動
   度のレベルをあらわすための活動度表示手段と、 （ｅ）上記活動度表示手段の出力を入力として受け取り
   、該活動度表示出力に基づき上記量子化器のうちの１つ
   を選択するための第１のセレクタ手段 （ｆ）上記活動度表示手段の出力を入力として受け取り
   、該活動度表示出力に基づき上記予測子Ｐとして上記予
   測子計算手段の出力のうちの１つを選択するための第２
   のセレクタ手段とを具備し、上記エントロピー・エンコ
   ーダ手段が状態入力として上記活動度表示手段の出力を
   受け取るようにした、 データ圧縮装置。