JPH1042144A - グレースケール画像の符号化方法および装置 - Google Patents

Abstract

(57)【要約】 【課題】 グレースケール画像を記憶するための必要メ
モリを低減する。 【解決手段】 グレースケール画像をディザ・マトリク
スを用いてハーフトーン化し、これをメモリに記憶す
る。この２値化画像データの各ビットの位置をハーフト
ーン化に用いたディザ・マトリクスに従って並べ替え、
それを圧縮してメモリに記憶する。元の２値化画像に復
元する時は、メモリから検索した後、ハーフトーン化に
用いたディザ・マトリクスに従って、並べ替えられてい
たデータを再び並べ直し、元の２値化画像の正確な複製
を形成する。このように、圧縮前にビットを並び替える
ことによってグレー値の近いビットが近接した位置にな
るので、圧縮装置の算術コーディング手順を簡略化する
ことができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はハーフトーンを含む画像
の算術符号化を行なう方法および装置に関し、より詳細
には、最適な圧縮比を達成しつつ算術コーディングを用
いてハーフトーンのエントロピー符号化を行なうための
一次元コンテキストモデルに関する。

【０００２】

【従来の技術】デジタル・データ信号のストリームを圧
縮されたデジタルコード信号に符号化し、この圧縮され
たデジタルコード信号をもとのデータに復号するデータ
圧縮システムが当該技術分野において周知である。デー
タ圧縮とは、所与のフォーマットのデータをこのもとの
データより必要スペースの少ない他のフォーマットに変
換する処理を指す。データ圧縮システムの目的は所与の
デジタル情報の保持に要する記憶域の量あるいはその送
出に要する時間を節約することである。

【０００３】汎用デジタルデータ圧縮システムが実用的
であるためにはある種の基準を満足しなければならな
い。かかるシステムには相互性がなければならない。デ
ータ圧縮システムが相互であるためには、圧縮されたデ
ータをいかなる改変や情報の損失も伴なわずそのもとの
形態に再拡張すなわち復号することが可能でなければな
らない。復号されたデータともとのデータは同一であ
り、互いに区別できないものでなければならない。相互
性は情報理論で用いられる厳密な無雑音性と同義であ
る。用途によっては厳密な相互性が求められない場合も
ある。かかる用途を特に一つ挙げれば、図形データの処
理がある。人間の眼は雑音に対してさほど敏感ではない
ため、圧縮/復元処理における多少の変化や情報の損失
は許される。

【０００４】かかるシステムは、データ圧縮および復元
システムと通信する装置によって提供され、かつ許容さ
れるデータ転送速度に関して十分な性能を持つものでな
ければならない。データ圧縮速度は圧縮システムへの入
力データの処理速度（通常数百万バイト/秒（メガバイ
ト/秒））によって決まる。通常１メガバイト/秒を越え
る今日のディスク、テープおよび通信システムにおける
データ転送速度を維持する十分な性能が必要である。従
って、かかるデータ圧縮/復元システムはシステム全体
に悪影響を与えないだけの十分なデータ帯域幅を持って
いなければならない。データ圧縮/復元システムの性能
は通常、圧縮および復元に必要な計算および統計データ
の記憶や圧縮および復元処理の実行に用いられるランダ
ムアクセスメモリ（RAM）その他のシステム構成要素の
速度による制約を受ける。圧縮装置の性能は、その圧縮
装置における１入力文字あたりに必要なプロセッサ・サ
イクルの数で表わされる。このサイクル数が小さいほ
ど、性能が高いということになる。

【０００５】データ圧縮/復元システムの設計における
もう一つの重要な評価基準は、圧縮率で表わされる圧縮
の有効性である。圧縮率は未圧縮の形態でのデータサイ
ズを圧縮された形態のデータサイズで割った率である。
データが圧縮可能であるためには、そのデータに冗長性
がなければならない。圧縮の有効性はその圧縮手順が入
力データの冗長性をいかに有効に利用するかによって決
まる。通常のコンピュータ記憶データにおける冗長性
は、個々の記号、例示ディジット、バイトあるいは文字
の不規則な使用および共通のワードや空白記録フィール
ド等の記号シーケンスの頻繁な反復という形で発生す
る。

【０００６】また、従来技術において汎用データ圧縮手
順が知られており、かかる適切な手順としてHuffman
法、Tunstall法およびLempel-Ziv法の３つがある。Huff
man法は広く知られ使用されている。これについては、P
roceedings IRE、40の1098〜1100ページ（1952年９月）
の“A Method For Construction Of Minimum Redundanc
y Codes”と題するD. A. Huffmanの論文を参照された
い。TunstallアルゴリズムについてはGeorgia Institut
e of Technology（1967年９月）の“Synthesis of Nois
eless Compression Codes”と題するB. P. Tunstallの
博士論文を参照されたい。Lempel-Ziv手順についてはIE
EE Transactions on Information Theory、IT-23, 3, 3
37〜343ページ（1977年５月）の“A Universal Algorit
hm For Sequential Data Compression”と題するJ. Ziv
およびA. Lempelの論文を参照されたい。

【０００７】

【発明が解決しようとする課題】最初に開発された汎用
データ圧縮手順の１つがHuffman法である。簡単にいえ
ば、Huffman手順は記号のセグメント全長を可変長のワ
ードにマップするものである。Huffmanデータ圧縮手順
には２つの制約がある。第一に、Huffman手順は圧縮す
べき入力データを固定長の記号セグメントに分解しなけ
ればならないという制約下で動作する。Huffman手順は
かかる制約下において可能な最良の圧縮率を得られるも
のではあるが、かかる制約が緩和されれば、他の手順を
用いてはるかに高い圧縮率を得ることが可能である。第
二に、Huffmanコーディングはソース・データの統計的
特性に関する全知識を必要とする。Huffman手順は固定
長の入力セグメントそれぞれの発生する確率が既知であ
ることを前提とするものである。Huffman手順のかかる
条件は実際にはデータの処理中に必要な統計値を蓄積す
るこの手順の適応バージョンを使用して満足することが
できる。しかし、これには手間がかかり、かなりの作業
メモリスペースが必要であり、適応中には最適な性能が
得られない。

【０００８】可変長の記号セグメントを固定長の２進ワ
ードにマップするTunstallアルゴリズムは固定長の制約
が入力セグメントではなく出力セグメントに加わるとい
う意味でHuffman手順を補完するものである。Huffman手
順と同様に、Tunstall手順においてもソース・データの
確率があらかじめわかっていなければならない。この事
前知識の条件は、データ処理中に統計値を蓄積する適応
バージョンを利用してある程度満たすことができる。

【０００９】Lempel-Ziv手順は可変長の記号セグメント
を可変長の２進ワードにマップするものである。これは
入力あるいは出力セグメントに制約がない場合には漸近
的な最適性を有する。この手順では、入力データ・スト
リングは適応して大きいセグメントに分解され、各セグ
メントは、入力セグメントの始めの部分の正確なコピー
に、入力データからの１つの新たな記号を付したものか
らなる。ここで作成するコピーは可能な限り長いもので
あり、それ以前の分解されたいかなるセグメントにも一
致する必要はない。出力においてかかるセグメントに置
き換えられるコードワードは、それよりも前にコピーさ
れた部分の始点を指すポインタ、そのコピーの長さ、お
よび前記の新たな記号からなる情報を含む。

【００１０】HaffmanコーディングあるいはShannon-Fan
oコーディングは完全なデータ圧縮手段のようにも見え
る。しかし、これは事実ではない。上述したように、こ
れらのコーディング法は記号の確率が1/2の整数乗の数
である場合にのみ最適であり、通常はそうではない。

【００１１】算術コーディングの技術にはかかる制約が
ない。この技術は、メッセージを１単位として扱う（Hu
ffmanコーディングの場合には各メッセージの列挙を必
要とする）のと同様な効果が得られ、従って、任意のソ
ースに対して圧縮効率の理論的エントロピー境界に達す
ることができる。

【００１２】算術コーディングにおいては、判断が次々
と符号化され、数直線上により小さいincluded間隔が画
成される。算術コーディングの詳細についてはIBM Jour
nal of Reseacrh and Development、Vol. 28、n. 2（19
84年３月）135〜149ページのG. G. Langdon, Jr.の“An
Introduction To Arithmetic Encoding”、Vol. 23、
n. 11（1981年４月）5112〜5114ページのD. R. Helman,
G. G. Langdon, Jr.と、J. J. Rissanenの“ Arithmet
ic Compression Code Control Parameters Approximati
on”、およびLangdon, Jr.その他の米国特許第4,905,29
7号“Arithmetic Coding Encoder And Decoder Syste
m”を参照されたい。

【００１３】上記の各論文に述べるように、算術コーデ
ィングによれば、各判断から複数の可能な排他的な結果
“OR事象”が導かれる。それぞれの結果すなわち事象は
記号を用いたデータとして表わされる。たとえば、画像
化の分野においては、各判断はある特定の画素を黒であ
るか否かの判断に対応する。その判断の結果はその画素
が黒である場合にはY（すなわちYES）記号、黒でない場
合にはN（すなわちNO）記号で表わされる。従って、複
数の判断を一連の記号、たとえばYNNY…などで表わすこ
とができる。

【００１４】従来の算術コーディング技術によれば、確
率直線には現行間隔が画成される。最初の現行間隔は０
から１の間である。この現行間隔がセグメントに分割さ
れ、各セグメントは次の判断の１つの可能な結果に対応
する。各判断に対して可能な結果が２つしかない場合、
現行間隔は２つのセグメントに分割される。各セグメン
トの長さはそれに関係付けられた対応する確率に基づい
て決まる。この対応する確率は固定したままにすること
もでき、また判断データの入力時に適宜変更させること
もできる。

【００１５】大きなセグメントを高い頻度で発生する記
号に相関させることによって圧縮効果が得られる。上記
の論文（“An Introduction To Arithmetic Encodin
g”）には４記号算術コーディングの例が記載されてお
り、この例では各判断から（50％の確率を有する）
“a”事象、（25％の確率を有する）“b”事象、（12.5
％の確率を有する“c”事象、あるいは（12.5％の確率
を有する“d”事象が発生する。これら４つの事象を２
進数形式で表わすには、各判断に２ビットが必要であ
り、これらの事象はそれぞれ00、01、10、11で表わされ
る。“aab”等のように頻繁に発生する３つの判断につ
いては、符号化データは率直に考えると00 00 01であ
り、６ビットを必要とする。しかし、この論文の137ペ
ージに見られるように、この算術コーディング法ではこ
のシーケンス“aab”を値0.001で表わすことができる。
この情報を６ビットではなく３つのビットで表わすこと
ができる。このようなビットの節約は、比較的発生確率
の高い連続する事象が発生するときに得られる。

【００１６】確率が低くまたラインセグメントの比較的
短い多数の事象が発生する場合には、かかる節約の効果
は低下する。上記の確率によれば、一連の事象“dd’は
符号化データ“11 11”で表わされ、算術コーディング
によれば“dd”事象は111111によって表わされる。大き
いセグメントは実際には発生頻度の高い事象に対応する
ことを条件とすれば、確率の高い記号が発生するときに
達成される節約は、確率の低い記号に必要な追加ビット
を上回る。

【００１７】連続階調グレースケールを含む画像は２レ
ベルプリンタで印刷されるハーフトーンでなければなら
ない。ハーフトーン化は一般にディザ・マトリクスを用
いて達成される。ディザ・マトリクスはしきい値の２次
元マトリクスである。グレースケール画像は、生成され
る画像信号の連続する画素をディザ・マトリクスの対応
するしきい値と比較し、その画像信号がディザ・マトリ
クス中の対応するしきい値より大きいか小さいかに応じ
て２値信号（ディザ信号）が生成され、２値化される。
従って、１つのハーフトーン画像について、ディザ信号
中の各画素ごとに１つのビットが割り当てられる。隣接
する画素は様々なしきい値に応じて２値化されるため、
ディザ信号の局所的密度はもとのグレースケール画像の
密度に対応する。

【００１８】連続階調グレースケール画像のデジタルハ
ーフトーン化および印刷においては、一般にハーフトー
ン解像度と生成されるグレーレベルの数の間でのトレー
ドオフが存在する。エッジ精細度を高くするための解像
度を高くすると利用可能なグレーレベルの数が少なくな
り、グレー輪郭の深さおよびなめらかさがそれに対応し
て低下する。デジタルハーフトーン化の詳細について
は、ISBN 0-262-21009-6（第４版、1993年）のUlichne
y, Rの“Digital Halftoning”を参照されたい。

【００１９】ハーフトーン解像度と生成可能なグレーレ
ベルの数を増大させる最も直接的な方法は、プリンタの
解像度を高くすることである。たとえば、600 dpiのプ
リンタから1200 dpiのプリンタに変われば、利用可能な
グレーレベルの数は４倍になる。しかし、より解像度の
高い印刷機構の追加コストが発生し、必要なビットマッ
プメモリが４倍に増える。

【００２０】高い解像度を用いることによるビットマッ
プメモリのコストの増大を避けるために、画像をリアル
タイムにハーフトーン化し、ビットマップメモリに中間
的に記憶することなくプリンタに送ることができる。し
かし、ページにはテキストや図形などの他の非画像要素
が存在する可能性がある。これらがハーフトーン画像に
重なったり、これを覆い隠したり、悪影響を及ぼしたり
する可能性があり、あるいは逆にハーフトーン画像に論
理的に作用する可能性があるので、ハーフトーン画像と
ともにメモリに記憶しなければならない。

【００２１】一般に、データ圧縮をハーフトーン画像に
適用してそれに必要なビットマップ・メモリを低減し、
リアルタイムに復元された出力をプリンタに送ることが
できる。しかし、従来のほとんどの復元システムはハー
フトーン画像については比較的低い圧縮率しか得ること
ができなかった。

【００２２】

【課題を解決するための手段】グレースケール画像を記
憶するための必要メモリを低減する方法が提供される。
この方法を実行するために、まずグレースケール画像が
ディザ・マトリクスを用いて２レベル画像に変換され
る。この２レベル画像はメモリに記憶される。この２レ
ベル画像中のビットの位置がディザ・マトリクスに従っ
て並べ替えられる。メモリ内の２レベル画像がこの並べ
替えられた画像に置き換えられる。画像処理装置が圧縮
装置に、この並べ替え画像のメモリからの検索、圧縮、
および圧縮された並べ替え画像のメモリへの記憶を行わ
せる。

【００２３】もとの２レベル画像を復元するには、画像
処理装置は圧縮装置に圧縮された並べ替えられた画像の
メモリからの検索、およびその復元を行なわせる。並べ
替えられた画像の複製がメモリに記憶される。並べ替え
られた画像の複製のビットがディザ・マトリクスに従っ
て並べ替えられ、２レベル画像の正確な複製が形成され
る。

【００２４】圧縮に先立ってビットを並べ替えることに
よって、近いグレー値のビットは互いに近接して位置す
る。従って、圧縮装置は一次元モデル算術コーディング
手順を用い、これによって算術コーディング手順を簡略
化することができる。圧縮に先立つ２レベルデータの移
し変えは他の圧縮手順にも有効である。

【００２５】

【実施例】デジタル・ハーフトーン画像は、ディザリン
グされたデータに起因する高周波雑音があるため、予測
が困難なものである。コンテキストモデルを得る標準的
な方法は隣接画素を見ることである。たとえば、JBIGで
は２×５と３×３の２種類のウィンドウを用いる。図１
および図２はそれぞれこれら２つのモデルを示す。ここ
で、画素“X”を予測したいものとする。この画素の周
囲の画素を用いてXの予測が行なわれる。

【００２６】これらのモデルはいずれもテキストおよび
線用に開発されたものである。いずれもデジタルハーフ
トーンに適したものではない。デジタルハーフトーン画
像における主たる問題は、所与の画素の周囲の画素が予
測処理にとって部分的にしか意味を持たないことであ
る。より有益な情報は、形成されるドットのエッジ周辺
に存在する。

【００２７】ハーフトーン化処理において形成される画
素は比較動作の結果得られるものである。比較される値
は、もとの多レベル画像データとしきい値（ディザとも
呼ぶ）マトリクス中のレベルである。しきい値マトリク
ス中の同じ値からは同じ画素が生成される。従って、同
じしきい値マトリクスレベルの前の画素に基づいて画素
を予測すれば、予測能力を大きく向上させることができ
る。

【００２８】図３に106 lpi 600 dpiプリンタ・マトリ
クス・パターンを示す。この典型的なしきい値マトリク
スはしきい値の昇順の配置を示す。このしきい値マトリ
クスを用いて、まず小さな数がオンする。従って、非常
に明かるい領域においてのみ、たとえば数０から７が常
にオフされる。

【００２９】図１および図２に示す方法を用いて位置１
の画素の値を予測することは困難である。たとえば、図
１の２×５のモデルを採用して、ディザ・マトリクス番
号38、31、23、15、29、52および９でハーフトーン化さ
れた画素を用いて予測が行なわれる。このモデルにおけ
る最も意味のある画素は９であり、これは空間的に画素
１に近い。他の画素はさまざまなグレー値でオンあるい
はオフされる。

【００３０】予測しようとする画素とモデル内の他の画
素との空間的関係を確認する方法の１つは、適当なモデ
ルを構築することである。しかし、かかるモデルの構築
は動的に行なわねばならない。これは、画素の相対的位
置と空間的関係は図３のマトリクスにおいて一定ではな
いためである。本実施例では、図３に示すしきい値マト
リクスによって作成されるようなハーフトーン画像は、
空間的に関係付けられた画素を物理的に近接して配置す
ることができるように並べ替えることができる。以上の
説明は図３および図４に関係するが、当業者にはこの説
明からしきい値マトリクスの実際の構成に応じてこれ以
外の並べ替え手順の使用が可能であることが理解されよ
う。

【００３１】図４は、図３のしきい値マトリクスが並べ
替えられた状態を示す。ハーフトーン化前には、ディザ
・マトリクスではなくハーフトーン画像自体が並べ替え
られることに注意しなければならない。しかし、説明の
便宜上、ディザ・マトリクスのシャフリングは、ハーフ
トーン処理中にしきい値に対応する画素がどのように並
べ替えられるかを示す。その画素が図４に示すように並
べ替えられた画像においては、等しいレベルの画素は同
じライン上に配置される。たとえば、図４のライン3は
画素０、２、４、６、１、３、５および７を含む。最初
は、図4内のラインが順序づけられていない理由が明ら
かでないかもしれない。かかる順序付けも可能ではある
が、これは並べ替えアルゴリズムを不必要に複雑化させ
る。

【００３２】ハーフトーン画像が並べ替えられると、適
正化されたモデルを用いて所与の画素の状態をより正確
に予測することができる。図４に示すように並べ替えら
れた図３のしきい値マトリクスについて、一次元コンテ
キストモデルによってかかる近い関係の画素に関する情
報が提供される。たとえば、画素１を予測するとき、一
次元コンテキスト・モデルは画素１と同じライン上の前
の画素のみを用いる。従って、３、５、７、０、２、４
および６に対応する画素を用いて画素１の予想値が判定
される。これらの画素はMPS（最確記号）および確度を
得る上ではるかに大きな意味を持つ。

【００３３】図５は、ハーフトーン画像データを図３の
しきい値マトリクスに従って並べ替えるのに用いる並べ
替えアルゴリズムを示す。まず、図５に示すように、象
限CおよびDの画素情報が交換される。象限AおよびBの画
素情報は変更されない。図３を参照して説明すると、し
きい値39に関する画素情報がしきい値29に関する画素情
報と交換される。象限CおよびD内の他の画素情報も同様
にして交換される。図５の“マクロ”交換の後、図３の
最も上の行のしきい値データは30、22、14、28、31、2
3、15および29となる。次に、それぞれの象限において
図６に示すような“ミクロ”交換が行なわれる。図４に
４つの象限すべてが処理された結果を示す。特に、１対
の画素を例にとれば、図３の画素30および10は図４に示
すように交換される。図５および図６の並べ替えアルゴ
リズムは迅速に実行することができる。これは、このア
ルゴリズムが決まった場所への並べ替えである、すなわ
ちデータが単純に交換されるだけであるためである。

【００３４】当業者には、データを最初に並べ替えたの
と同じ並べ替えアルゴリズムを用いてデータの再並べ替
えが可能であることは明らかであろう。この決まった場
所への並べ替えアルゴリズムを用いることが図４のデー
タが順序付けられていない理由である。図４のデータの
順序付けを行なってもよいが、順序付けられた並べ替え
アルゴリズムを設けても算術的圧縮率が大幅に増大する
ことはない。用途によっては圧縮効率を犠牲にして“マ
イクロ”交換が省略される場合がある。下の表にはマク
ロ並べ替えのみを行なう算術コーディングとマクロおよ
びミクロ並べ替えの両方を行なう算術コーディングを用
いて処理されたファイルの５つの例を示す。

【００３５】

【表１】

【００３６】図７には本実施例のフローチャートを示
す。システムはグレー画像のデータを受け取る（200）
と、まずグレーデータを記憶できるだけのメモリがある
かどうかを判定しなければならない（202）。グレーデ
ータを記憶できるだけのメモリがある場合、情報は最初
に圧縮されることなく単純に記憶される（201）。しか
し、通常、グレー画像データの記憶にはシステムで現在
利用できる以上の記憶スペースを要する。

【００３７】まず、グレー画像データに対してハーフト
ーン化処理が実行される（203）。ハーフトーン化処理
（203）の詳細については本願では説明しない。ハーフ
トーン化処理の詳細については多くの文献があり、その
いくつかを従来技術の部分で挙げた。画像にハーフトー
ン化が行なわれた後、この２レベルデータはハーフトー
ン化の実行に用いたディザ・マトリクスに従って並べ替
えられる（204）。次に、圧縮装置が初期化され、起動
される（205）。本実施例の意図する環境では、圧縮装
置/復元装置はハードウエア要素で実施される。従っ
て、205における圧縮処理は、システムがサービスを必
要とするときシステムに割り込む（206）。圧縮装置が
圧縮された画像の記憶に追加のメモリを必要とする場
合、照会が行なわれる（207）。追加メモリが不要であ
る場合、圧縮装置はグレースケール画像の圧縮を完了し
ており、200において実行を継続することができる。あ
るいは、さらにメモリが必要な場合、本実施例ではまず
圧縮率が１より大きいかどうかが判定される。圧縮率が
１未満であれば、これは圧縮装置が実際にはそのデータ
を拡張していることを意味する。この場合、システムは
圧縮されたデータを破棄し、もとのグレー画像データを
維持する（210）。一方、画像が圧縮されている（すな
わち、圧縮率が１より大きい）場合、メモリプールから
追加メモリが入手され、圧縮処理が再開される（20
9）。最後に、圧縮装置はシステムを停止させ（206）、
圧縮が完了したことを知らせる（207）。

【００３８】図８には典型的な復元サイクルのフローチ
ャートを示す。画像処理装置が圧縮された画像をストリ
ップに入れる（301）さいには、復元装置がまずその画
像を復元する（302）。結局、復元装置は、追加情報を
要求するかあるいは圧縮画像の復元が完了したことを知
らせる信号を発することによって画像処理装置を停止さ
せる（303）。復元装置が追加メモリを要求する場合、
画像処理装置はまずメモリプールからメモリを入手し、
復元装置を再起動する（305）。復元装置が圧縮画像の
復元を完了すると、画像処理装置は停止し（303）、復
元装置がそのタスクを完了したとの通知を受ける。次
に、使用されたディザ・マトリクスに従って復元された
画像が並べ直される（306）。最後に、圧縮および並べ
替えの解かれた画像がラスタ化され、ストリップに入れ
られる。

【００３９】図９にはこの圧縮処理のデータフローを簡
略化したブロック図で示す。画像処理装置（IP）413が
２レベル画像を並べ替えた後、この画像はDRAM 400に記
憶される。次に、IP 413は圧縮サイクルを開始する。ハ
ードウエア圧縮装置402がDMAコントローラ412の制御の
もとに、DRAM 400中の並べ替えられた２レベル画像デー
タを要求する。FIFO 409が弾性的バッファリングを実行
してDRAM 400とハードウエア圧縮装置402のデータ転送
速度の差を補償する。

【００４０】１つの行がFIFO 409からシフトレジスタ41
0に転送される。図９では現在、ビット407が圧縮されて
いる。関係するビット408が、算術コーディング・ハー
ドウエア403の確率RAM 406のアドレスを形成する。確率
RAM 406の出力および算術コーディングハードウエア403
によって実行される追加的な算術演算に基づいて、ビッ
ト407のMPSが生成される。特定のビット407が圧縮され
ると、シフトレジスタ410のデータがシフトされ、新た
なビットが圧縮される。本実施例は一次元コンテキスト
モデルであるため、シフトレジスタ410によって圧縮装
置のハードウエアによる実施が大いに簡略化される。

【００４１】算術コーディングハードウエア403は作成
された圧縮データをFIFO 404に渡す。DMAコントローラ4
05の制御のもとに、データはFIFO 404からDRAM 401に転
送される。DRAM 400のデータがすべて圧縮されDRAM 401
に転送された後、ハードウエア圧縮装置402はIP 413に
これを知らせる。

【００４２】図10はこの復元処理のデータフローを簡略
化したブロック図で示す。ここでは、圧縮データはDMA
コントローラ405の制御のもとにDRAM 401からFIFO 404
に転送される。算術コーディング・ハードウエア403が
このデータを復元し、一度に１つのビット511を出力す
る。

【００４３】ビット507はビット508との関係に基づいて
予測される。ビット508は確率RAM406のアドレスを形成
する。確率RAM 406の出力および算術コーディングハー
ドウエア403によって実行される追加的な算術演算に基
づいて、ビット507の状態が生成される。次に、シフト
レジスタ410のデータがシフトされ、次のビットが復元
される。結局、シフトレジスタ410は圧縮されていない
データの全バイトを保持し、これがFIFO 409に転送され
る。DMAコントローラ412の制御のもとに、この圧縮され
ていないデータがFIFO 409からDRAM 400に転送される。
圧縮画像401の復元が完了すると、ハードウエア圧縮装
置402はIP 413にこれを知らせる。IP 403は並べ替えら
れた２レベル画像データ400を並べ直さなければならな
い。当業者には、この並べ替えはIP 413によってファー
ムウエアの指示のもとに、あるいは図示しない特殊目的
のハードウエア・ブロックを介して実行可能であること
が理解されよう。

【００４４】ここでは算術コーディングの圧縮率の増大
に焦点を当てたが、この並べ替え処理によってLZやRLE
といった他の圧縮法の圧縮率の増大も可能であること
が、当業者には以上の説明から理解されよう。並べ替え
の後に同じグレー値がグループ化されることにより、０
あるいは１の連続する連なりの数および長さが増大し、
その結果こういった圧縮率の増大を生む。

【００４５】以上、本発明の実施例を図示し、その態様
を説明したが、当業者には本発明の精神および特許請求
の範囲から逸脱することなくさまざまな変更が可能であ
ることは明らかであろう。

【００４６】〔実施態様〕なお、本発明の実施態様の例
を以下に示す。

【００４７】〔実施態様１〕 グレースケール画像を符
号化する方法であって、前記のグレースケール画像をデ
ィザ・マトリクス（図３）を用いてハーフトーン化して
２レベル画像を形成するステップ（203）と、前記の２
レベル画像中の個々のビットを前記のディザ・マトリク
ス（図３）に従って並べ替えて並べ替え画像を形成する
ステップ（204）と、前記の並べ替え画像を圧縮するス
テップ（205）と、圧縮された並べ替え画像をメモリ（4
01）に記憶するステップ（209）とを設けて成る方法。

【００４８】〔実施態様２〕 前記の圧縮された並べ
替え画像を前記のメモリ（401）から検索するステップ
（301）と、前記の圧縮された並べ替え画像を復元して
前記の並べ替え画像の複製を得るステップ（302）と、
前記並べ替え画像の複製の個々のビットを前記のディザ
・マトリクス（図３）に従って並べ直して前記の２レベ
ル画像の複製を形成するステップ（306）とをさらに備
えることを特徴とする、実施態様１に記載の方法。

【００４９】〔実施態様３〕 前記の圧縮ステップ（2
05）は一次元モデル算術コーディング手順を用いて実行
され（図９）、前記の復元ステップ（302）は前記の一
次元モデル算術コーディング手順を用いて実行される
（図10）ことを特徴とする、実施態様１または実施態様
２に記載の方法。

【００５０】〔実施態様４〕 グレースケール画像の
記憶に要するメモリを低減する方法であって、前記のグ
レースケール画像をディザ・マトリクス（図３）を用い
て２レベル画像に変換するステップ（203）と、前記の
２レベル画像をメモリ（400）に記憶するステップ（20
3）と、前記の２レベル画像の個々のビットを前記のデ
ィザ・マトリクス（図３）に従って並べ替え、前記のメ
モリ（400）に記憶された前記の２レベル画像が前記の
並べ替えられた画像に置き換えられるステップ（204）
と、前記のメモリから前記の並べ替え画像を検索するス
テップと、前記の並べ替え画像を圧縮して、圧縮された
並べ替え画像を得るステップ（205）と、前記の圧縮さ
れた並べ替え画像を前記のメモリ（401）に記憶するス
テップとを設けて成る方法。

【００５１】〔実施態様５〕 前記のメモリ（401）か
ら前記の圧縮された並べ替え画像を読み出すステップ
と、前記の圧縮された並べ替え画像を復元して前記の並
べ替え画像の複製を得るステップ（302）と、前記の並
べ替え画像の前記の複製の個々のビットを前記のディザ
・マトリクス（図３）に従って並べ直して前記の２レベ
ル画像の複製を形成するステップ（306）とをさらに含
むことを特徴とする、実施態様４に記載の方法。

【００５２】〔実施態様６〕 前記の圧縮ステップ（2
05）は一次元モデル算術コーディング手順を用いて実行
され（図９）、前記の復元ステップ（302）は前記の一
次元モデル算術コーディング手順を用いて実行される
（図10）ことを特徴とする、実施態様４または実施態様
５に記載の方法。

【００５３】〔実施態様７〕 グレースケール画像の
記憶に要するメモリを低減する装置であって、メモリ
（400、401）と、圧縮装置（402、403）と、前記のメモ
リ（400、401）および前記の圧縮装置（402、403）に取
り付けられた画像処理手段（413）とを備えており、前
記の画像処理手段（413）はディザ・マトリクス（図
３）を用いて前記のグレースケール画像を２レベル画像
に変換し、前記の２レベル画像は前記のメモリ（400）
に記憶され、前記の２レベル画像の個々のビットが前記
のディザ・マトリクス（図３）に従って並べ替えられ、
並べ替え画像が形成され（204）、前記のメモリ（400）
に記憶された前記の２レベル画像が前記の並べ替え画像
に置き換えられ、前記の画像処理手段（413）は、前記
の圧縮装置（402、403）が前記のメモリ（400）から前
記の並べ替え画像を検索（409、412）し、圧縮（205）
し、圧縮された並べ替え画像（401）を前記のメモリ（4
01）に記憶（405、404）することを可能とすることを特
徴とする装置。

【００５４】〔実施態様８〕 前記の画像処理手段（4
13）は、前記の圧縮装置（402、403）が前記のメモリ
（401）から前記の圧縮された並べ替え画像を検索（40
4、405）し、復元（302）し、および前記の並べ替え画
像の複製を前記のメモリ（400）に記憶（409、412）す
ることを可能とし、前記の画像処理手段（413）は、前
記の並べ替え画像の前記の複製の個々のビットを前記の
ディザ・マトリクス（図３）に従って並べ直して前記の
２レベル画像の複製を形成することを特徴とする、実施
態様７に記載の装置。

【００５５】〔実施態様９〕 前記の圧縮装置（402、
403）は一次元モデル算術コーディング手順（図９、図1
0）を用いることを特徴とする、実施態様７または実施
態様８に記載の装置。

【００５６】

【発明の効果】以上詳細に説明したように、本発明によ
れば、プリンタその他の画像処理が行われる装置におい
て、グレースケール画像を記憶するために必要なメモリ
の容量を低減することができる。特に、グレースケール
画像データをハーフトーン化し２値化したデータを圧縮
する前に、そのデータをハーフトーン化に用いたディザ
・マトリクスに従って並べ替えるので、グレー値の近い
ビットが互いに近接して位置することになり、圧縮装置
の算術コーディング手順を簡略化することができる。さ
らに、この２値化画像データのビットの移し替えの技術
は、一次元モデル算術コーディング手順のみならず、他
の圧縮手順にも有効であり、メモリ、圧縮装置の簡略化
に大きく寄与することができ、実用に供して有益であ
る。

【図面の簡単な説明】

【図１】２×５ウィンドウを示す図である。

【図２】３×３ウィンドウを示す図である。

【図３】106 LPI 600 DPIマルチドット・ディザ・マト
リクスの一例を示す図である。

【図４】並べ替え後の図３のディザ・マトリクスを示す
図である。

【図５】並べ替え処理の実施例のマクロ部分を示す図で
ある。

【図６】並べ替え処理の実施例のミクロ部分を示す図で
ある。

【図７】本発明の圧縮処理を示す論理フローチャートを
示す図である。

【図８】本発明の復元処理を示す論理フローチャートを
示す図である。

【図９】本発明の圧縮処理のハードウエアによる実施を
示すブロック図である。

【図１０】本発明の復元処理のハードウエアによる実施
を示すブロック図である。

【符号の説明】

０、２、４、６、１、３、５、７：画素 １：位置 ３：線 10、30：画素 14、15、22、23、28、29、30、31、39：しきい値 200〜210：圧縮サイクルのフロー 301〜307：復元サイクルのフロー 400、401：DRAM 402：ハードウエア圧縮装置 403：算術コーディングハードウエア 404、409：FIFO 405、412：DMAコントローラ 406：確率RAM 407、408：ビット 410：シフトレジスタ 413：画像処理装置（IP） 507、508：ビット A、B、C、D：象限

Claims (2)

【特許請求の範囲】
1. 【請求項１】 グレースケール画像を符号化する方法で
   あって、 前記のグレースケール画像をディザ・マトリクスを用い
   てハーフトーン化して２レベル画像を形成するステップ
   と、 前記の２レベル画像中の個々のビットを前記のディザ・
   マトリクスに従って並べ替えて並べ替え画像を形成する
   ステップと、 前記の並べ替え画像を圧縮するステップと、 圧縮された並べ替え画像をメモリに記憶するステップと
   を設けて成る方法。
2. 【請求項２】 グレースケール画像の記憶に要するメ
   モリを低減する装置であって、 メモリと、 圧縮装置と、 前記のメモリおよび前記の圧縮装置に取り付けられた画
   像処理手段とを備えており、 前記の画像処理手段はディザ・マトリクスを用いて前記
   のグレースケール画像を２レベル画像に変換し、 前記の２レベル画像は前記のメモリに記憶され、 前記の２レベル画像の個々のビットが前記のディザ・マ
   トリクスに従って並べ替えられ、並べ替え画像が形成さ
   れ、 前記のメモリに記憶された前記の２レベル画像が前記の
   並べ替え画像に置き換えられ、 前記の画像処理手段は、前記の圧縮装置が前記のメモリ
   から前記の並べ替え画像を検索し、圧縮し、圧縮された
   並べ替え画像を前記のメモリに記憶することを可能とす
   ることを特徴とする装置。