(57)【特許請求の範囲】
【請求項１】
階調処理されたラスタデータを圧縮符号化するに際して、圧縮符号化すべき符号化ラインよりも前に符号化されたラインを参照ラインとし、この参照ラインと前記符号化ラインとの間の画素値の配列関係に基づいて前記符号化ラインを圧縮符号化するラスタデータの圧縮方法において、
前記符号化ラインよりも前に符号化された複数のラインをそれぞれ参照ラインとして記憶しておき、
前記複数の参照ラインのうち、前記符号化ラインの圧縮率が最大となる参照ラインを選択し、当該参照ラインのラスタデータを参照しながら前記符号化ラインのラスタデータを圧縮符号化する
ことを特徴とするラスタデータの圧縮方法。
【請求項２】
前記符号化ラインよりも前に符号化された複数のラインのうち、前記符号化ラインの２n（ｎ＝０，１，２，…）ライン前のラインを前記複数の参照ラインとする
ことを特徴とする請求項１記載のラスタデータの圧縮方法。
【請求項３】
圧縮符号化すべき全てのラスタデータのうち、最初の一部のラスタデータについて前記複数の参照ラインを参照した圧縮符号化を行って前記圧縮率が最大となる参照ラインを決定し、以後は決定された参照ラインのみを参照して前記符号化ラインのラスタデータを圧縮符号化する
ことを特徴とする請求項１又は２記載のラスタデータの圧縮方法。
【請求項４】
前記決定された参照ラインを参照して前記符号化ラインのラスタデータを圧縮符号化している途中で圧縮率が所定の値を下回ったら、前記複数の参照ラインから再度参照すべき参照ラインを決定するようにした
ことを特徴とする請求項３記載のラスタデータの圧縮方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、符号化ラインとこの符号化ラインよりも前に符号化された参照ラインとの間の画素値の配列関数に基づいて符号化ラインを圧縮符号化するラスタデータの圧縮方法に関し、特に階調処理されたラスタデータの圧縮に適したラスタデータの圧縮方法に関する。
【０００２】
【従来の技術】
従来より、２値画像の圧縮方法として、ＭＲ（Modified READ）方式やＭＭＲ（Modified MR）方式等が知られている。これらの方式は、連続する２つのラインの相関が高いことを利用してラスタデータを高能率で圧縮する方式であるが、ディザ等によって階調処理された画像に対しては却って圧縮率が悪化するという問題がある。これは、ディザ化画像では、長いランの発生頻度が少なく、且つテクスチャノイズの防止のため、隣接するラインでドットの位置をずらすような処理をしているからである。
そこで、このようなディザ処理が施されたイメージデータの圧縮方法として、ディザパターンの周期性に着目し、例えば４×４のディザマトリクスを用いて２値化する場合、各ライン上で４画素ずつをまとめ、それぞれを新たに２4値信号を有する１つのブロックとみなし、ラインに沿う方向のそのブロック系列上で変化ブロックをＭＲと同様に符号化処理する方法が提案されている（特公平２−６１８３１号）。
【０００３】
【発明が解決しようとする課題】
しかし、上述した従来の圧縮方法は、使用されたディザパターンのサイズが予め分っていることが前提となっており、例えばプロッタに供給されるイメージデータのように、既にディザ処理が施され、ディザパターンのサイズもまちまちで、未知であるような場合には、必ずしも最適な方法とは言えない。しかも、この方式は、ブロック単位のランレングスを符号化する方式であるため、可変長コードのテーブルを階調数分だけそれぞれ値を異ならせてエンコーダ、デコーダの双方に備える必要があり、テーブルの規模が数十倍〜数百倍になってしまうという問題がある。
【０００４】
この発明は、このような問題点に鑑みなされたもので、ディザのサイズが未知の場合でも常に最も効率の良い圧縮符号化が可能で、かつ可変長コードのテーブルも従来と同等サイズとすることができるラスタデータの圧縮方法を提供することを目的とする。
【０００５】
【課題を解決するための手段】
この発明に係る第１のラスタデータの圧縮方法は、階調処理されたラスタデータを圧縮符号化するに際して、圧縮符号化すべき符号化ラインよりも前に符号化されたラインを参照ラインとし、この参照ラインと前記符号化ラインとの間の画素値の配列関係に基づいて前記符号化ラインを圧縮符号化するラスタデータの圧縮方法において、前記符号化ラインよりも前に符号化された複数のラインをそれぞれ参照ラインとして記憶しておき、前記複数の参照ラインのうち、前記符号化ラインの圧縮率が最大となる参照ラインを選択し、当該参照ラインのラスタデータを参照しながら前記符号化ラインのラスタデータを圧縮符号化することを特徴とする。
【０００６】
この発明に係る第２のラスタデータの圧縮方法は、前記符号化ラインよりも前に符号化された複数のラインのうち、前記符号化ラインの２nライン前のラインを前記複数の参照ラインとすることを特徴とする。
【０００７】
この発明に係る第３のラスタデータの圧縮方法は、圧縮符号化すべき全てのラスタデータのうち、最初の一部のラスタデータについて前記複数の参照ラインを参照した圧縮符号化を行って前記圧縮率が最大となる参照ラインを決定し、以後は決定された参照ラインのみを参照して前記符号化ラインのラスタデータを圧縮符号化することを特徴とする。
【０００８】
この発明に係る第４のラスタデータの圧縮方法は、前記決定された参照ラインを参照して前記符号化ラインのラスタデータを圧縮符号化している途中で圧縮率が所定の値を下回ったら、前記複数の参照ラインから再度参照すべき参照ラインを決定するようにしたことを特徴とする。
【０００９】
この発明に係るラスタデータの圧縮方法によれば、符号化すべき符号化ラインよりも前に符号化された複数の参照ラインのうち、符号化ラインの圧縮率が最も最大となる参照ラインを選択してから、この参照ラインのラスタデータを参照して前記符号化ラインのラスタデータを符号化して行くようにしているので、どのようなパターンのディザ画像が与えられても、常に最も効率の良い符号化処理が実行されることになる。しかも、この発明によれば、従来のＭＲ，ＭＭＲ方式等と比べると、参照ラインの位置を直前とせず、任意とするだけの違いであり、ドット単位での処理は変わらないので、従来と同様のテーブルをそのまま使用することができ、符号化処理及び復号処理自体の変更も殆んどないので、処理速度の低下もない。
【００１０】
なお、ディザマトリクスは通常、２×２，４×４，８×８，…のように２n×２nのサイズで与えられるので、符号化ラインと相関の強いラインは、２nライン前である可能性が高い。このため、これらのラインを参照ラインとすれば、余分なラインの参照が不要となり、処理の効率が向上する。
【００１１】
また、処理速度が問題とならない場合は、全ての符号化ラインについて最適な参照ラインを選択すれば良いが、処理速度を上げる場合には、全てのラスタデータのうちの最初の一部（例えばデータの１／４等）についてのみ参照ラインの選択を行い、以後の処理については選択された参照ラインのみを参照して符号化処理を行えば良い。
【００１２】
更に決定された参照ラインを状況に応じて変更することも考えられる。例えば符号化処理の過程で、圧縮率が所定値を下回ったら、再度、最適参照ラインの選択を行う。これにより、１つのイメージデータ中に異なるサイズによるディザ化画像や通常の２値画像が混在するような場合でも、各画像に最もマッチした適応的な処理が可能になる。
【００１３】
【発明の実施の形態】
以下、図面を参照して、この発明の実施の形態を説明する。
図１は、この発明の一実施例に係るラスタデータの圧縮方法を適用した符号化システムの構成を示すブロック図である。
【００１４】
このシステムは、ＣＡＤシステム、スキャナ、パソコン又はそれらのプリンタドライバ等でディザ処理された画像や通常の２値画像との混合画像等を圧縮してプロッタ、プリンタ、ファクシミリ装置等に送信するシステムであるが、送信部５を記録部に変更することで、記録媒体への記録装置にも適用できる。画像データとして入力されるラスタデータは、入力データバッファ１に格納される。入力データバッファ１には、少なくとも符号化の対象となる符号化ラインとそれよりも前に符号化された１６ラインの計１７ライン分のデータが格納される。入力データバッファ１に格納されたデータのうち、符号化ライン、その直前のライン、２ライン前のライン、４ライン前のライン、８ライン前のライン及び１６ライン前のラインは、それぞれラインバッファ２1，２2，２3，２4，２5，２6に格納される。エンコーダ３は、ラインバッファ２2，２3，２4，２5，２6に格納されたラインを参照ラインＤR1，ＤR2，ＤR4，ＤR8，ＤR16とし、これらの参照ラインＤR1，ＤR2，ＤR4，ＤR8，ＤR16とラインバッファ２1に格納された符号化ラインＤCとの画素値の配列関係に基づいて符号化ラインＤCをＭＨ（Modified Huffman）符号化又はＭＲ符号化する。選択制御部４は、複数の参照ラインＤR1，ＤR2，ＤR4，ＤR8，ＤR16のうち、符号化ラインＤCの圧縮率が最大となる参照ラインＤR1，ＤR2，ＤR4，ＤR8，ＤR16を選択する。エンコーダ３は、また、選択制御部４で選択された参照ラインＤR1，ＤR2，ＤR4，ＤR8，ＤR16のラスタデータを参照しながら符号化ラインＤCのラスタデータをＭＨ又はＭＲ符号化し、送信部５を介して送信する。なお、再利用バッファ６は、コピー等のために用いられる。
【００１５】
図２は、エンコーダ３の構成の一例を示すブロック図である。
ＭＨ符号化部１１1は、コードテーブル１２を参照し、符号化ラインＤCの画素値のランレングスに基づいて符号化ラインＤCをＭＨ符号化し、コードバッファ１３2に格納する。ＭＲ符号化部１１2，１１3，１１4，１１5，１１6は、コードテーブル１２を参照し、参照ラインＤR1，ＤR2，ＤR4，ＤR8，ＤR16と符号化ラインＤCとの画素値の配列関係に基づいて符号化ラインＤCをそれぞれＭＲ符号化し、コードバッファ１３3，１３4，１３5，１３6，１３7に格納する。これらＭＨ符号化部１１1及びＭＲ符号化部１１2〜１１6での符号化に際して、コードテーブル１２を共用することができる。なお、コードバッファ１３1には、符号化ラインＤCがそのまま格納される。そして、コードバッファ１３1〜１３7に格納されたコードの長さが選択制御部４で比較され、ビット数が最も小さいコードが選択される。選択・ヘッダ付加部１４は、コードバッファ１３1〜１３7に格納されたコードのうち、選択制御部４で指定されたコードを選択し、この選択されたコードに符号化方式の種類や参照ラインを特定するためのヘッダを付加する。
【００１６】
次に、このように構成されたシステムにおけるラスタデータの圧縮方法について説明する。
いま、図３に示すような多値画像データが与えられ、これを図４に示すような４×４のディザマトリクスＭで２値化すると、図５に示すような２値画像が得られる。
エンコーダ３は、１ライン目についてはＭＨ符号化又は符号化なしの処理を実行するが、２ライン目以降はＭＲ符号化処理も含めて、最も圧縮率の高い方式の符号化を選択する。また、ＭＲ符号化処理では、ドット誤りが以後の処理に影響を与え続けるので、適当な間隔でＭＨ符号化処理を挿入するようにしても良い。これらの処理の選択は、選択制御部４によって制御される。
図５において、符号化すべき符号化ラインがＤCであるとすると、通常のＭＲ符号化処理では、その直前のラインＤR1を参照ラインとする。その組合せを示したのが図６（ａ）である。同様に、図６（ｂ），（ｃ），（ｄ）はそれぞれ参照ラインを２ライン前（ＤR2）、４ライン前（ＤR4）、８ライン前（ＤR8）とした場合の組合せを示している。なお、１６ライン前は説明の便宜上省略している。
【００１７】
図７は、ＭＲ符号化処理を説明するための図である。
着目画素をａ0とすると、ａ1，ａ2，ｂ1，ｂ2はそれぞれ次のように定義される。
ａ1：符号化ラインＤC上のａ0よりも後に最初に発生するａ0と異なる色の画素の位置
ａ2：符号化ラインＤC上のａ1よりも後に最初に発生するａ1と異なる色の画素の位置
ｂ1：参照ラインＤR上でａ0の直上及びそれよりも後に最初に発生するａ0と異なる色の画素の位置
ｂ2：参照ラインＤR上でａ1よりも後に最初に発生するｂ1と異なる色の画素の位置
【００１８】
これらの画素の位置関係から次の３つのモードを選択する。
（１）パスモード；ｂ2＜ａ1の場合
（２）垂直モード；｜ａ1−ｂ1｜≦３の場合
（３）水平モード；上記（１）（２）以外の場合
各モードと画素間の相対間の相対位置とコードとの関係を表１に示す。
【００１９】
【表１】
0003776528.tif 000002
【００２０】
ここで、ＭＨ（ｌ2），ＭＨ（ｌ3）は、それぞれｌ2，ｌ3のときのＭＨ符号化によるコードを意味する。なお、ＭＨ，ＭＲ符号化の具体的なアルゴリズムについては周知であるため割愛する。
以上の規則に基づいて図６（ａ）〜（ｄ）のそれぞれについてＭＲ符号化を行うと、次のようになる。
（１）参照ラインをＤR1とした場合［図６（ａ）］
０１００１００１００１０００１０００１１１０１０１ＥＯＬ（２５ビット）
（２）参照ラインをＤR2とした場合［図６（ｂ）］
１１１１１１１１０００１１ＥＯＬ（１３ビット）
（３）参照ラインをＤR4とした場合［図６（ｃ）］
１１１１１１１１０００１０１１ＥＯＬ（１５ビット）
（４）参照ラインをＤR8とした場合［図６（ｄ）］
１１１１１００００１０００００１０１０００１０１１ＥＯＬ（２５ビット）
【００２１】
以上から明かなように、参照ラインをＤR2とした場合が一番ビット数が少なく、圧縮率が高くなる。但し、この例の場合、全く符号化しない場合でも１２ビットであるから、あまり圧縮効果は高くない。これは、例示のケースが白と黒とが１ビットずつしかシフトしていないからである。また、上記の例は説明上、濃度変化がかなり激しくなっているが、実際の画像の場合、このような急激な濃度変化はない。
【００２２】
そこで、濃度レベルが０〜１５の各場合について考えると、通常は図８のような４×４のドットパターンが広い範囲にわたって繰返されることになる。そして、全ての濃度レベルについてこれらの各パターンに着目すると、図９に示すように、ライン方向に黒ドットが続く（ａ）のパターンが１０通り、ライン方向に３ドットおきに白ドットが現れる（ｂ）のパターンが８通り、黒と白とが交互に現れる（ｃ）のパターンが２４通り、ライン方向に３ドットおきに黒ドットが現れる（ｄ）のパターンが８通り、ライン方向に白ドットが続く（ｅ）のパターンが１４通りであり、（ｃ）のパターンを除くパターンの出現確率は６０％以上であり、これらのパターンでは、ラン長が３以上となるので、ＭＲ符号による圧縮効率をかなり高めることができる。
【００２３】
例えば、図１０は濃度レベル１０の一様パターンであるが、図１１（ａ）に示すように、符号化ラインＤCを参照ラインＤR4を参照して符号化すると、“１１１１ＥＯＬ”となり、圧縮率は４倍となる。また、図１１（ｂ）に示すように、符号化ラインＤC′を参照ラインＤR4′を参照して符号化すると“１ＥＯＬ”となり、圧縮率は１２倍となる。このように、符号化圧縮率が先の例のように低い場合には、全く符号化しない場合も選択対象とし、符号化圧縮の効果が望める場合には、最も圧縮率が高くなるように参照ラインを選択することにより、画像の状態に合わせて最も効率の良い圧縮処理が可能になる。
符号化ラインがいずれの符号化処理で符号化されたかは、符号化データの先頭に付加されるヘッダによって識別すれば良い。
【００２４】
表２は、ヘッダの一例を示す表である。
符号化しないときには、“０００”、ＭＨ符号化するときには、“００１”、直前ラインを参照してＭＲ符号化するときには、“０１０”、２ライン前を参照してＭＲ符号化するときには、“０１１”、４ライン前を参照してＭＲ符号化するときには、“１００”、８ライン前を参照してＭＲ符号化するときには、“１０１”、１６ライン前を参照してＭＲ符号化するときには、“１１０”をそれぞれ各ラインのデータの先頭に付加する。
【００２５】
【表２】
0003776528.tif 000003
【００２６】
符号化されたラスタデータは、図１２に示すような復号システムを用いて復号することができる。
符号化されたラスタデータは、入力データバッファ２１に格納される。先頭に付加されているヘッダは、ヘッダ識別部２２で識別される。この識別結果に基づいて、参照ラインバッファ２３から参照ラインが選択され、この参照ラインがＭＲデコーダ２４に供給される。ＭＲデコーダ２４は、ヘッダ識別部２２の識別結果に基づいてＭＨ復号、ＭＲ復号又は復号処理無しの選択をし、ＭＲ復号の場合は、供給された参照ラインを参照する。ＭＲデコーダ２４で復号されたラスタデータは、出力データバッファ２５に格納されると共に、後のラインの復号のために参照ラインバッファ２３に格納される。このように、付加されたヘッダを識別することにより、符号化されたデータを容易に復号することができる。
【００２７】
この発明によれば、従来のＭＲ，ＭＭＲ方式等と比べると、参照ラインの位置を直前とせず、任意とするだけの違いであり、ドット単位での処理は変わらないので、従来と同様のテーブルをそのまま使用することができ、符号化処理及び復号処理自体の変更も殆んどないので、処理速度の低下もない。
【００２８】
なお、ディザマトリクスは通常、２×２，４×４，８×８，…のように２n×２nのサイズで与えられるので、符号化ラインと相関の強いラインは、２nライン前である可能性が高い。このため、これらのラインを参照ラインとすれば、余分なラインの参照が不要となり、処理の効率が向上する。
【００２９】
図１３は、エンコーダ３の更に他の実施例を示すブロック図である。この実施例では、誤差演算を行う誤差演算部３１を用いて、符号化ラインと各参照ラインとの相関を計算している。参照ラインＤRiの最小二乗誤差をＤｅｆｉ、ライン方向の各画素の位置をｘとすると、誤差演算部３１は、
【００３０】
【数１】
0003776528.tif 000004
【００３１】
を演算し、選択制御部４は、このうち最も最小二乗誤差の小さいラインを参照ラインと決定する。この場合、単純な誤差演算だけで参照ラインを決定することができるので、ＭＲエンコーダ３３は１つで足りるという利点がある。ＭＲエンコーダ３３の出力にヘッダ付加部３４でヘッダが付加されるのは先の実施例と同様である。
【００３２】
なお、以上の実施例では、全ての符号化ラインで最適な符号化を選択することを前提としたが、全てのラスタデータのうちの最初の一部（例えばデータの１／４等）で符号化方式や参照ライン等を決定し、以後は決定された方式に固定して符号化処理を実行するようにしても良い。
この場合には、処理速度を先の例よりも高めることができる。
【００３３】
また、この場合、例えば符号化処理の過程で、圧縮率が所定値を下回ったら、再度、最適参照ラインの選択を行うようにしても良い。これにより、１つのイメージデータ中に異なるマトリクスサイズによるディザ化画像や通常の２値画像が混在するような場合でも、各画像に最もマッチした適応的な処理が可能になる。
【００３４】
【発明の効果】
以上述べたように、この発明によれば、符号化すべき符号化ラインよりも前に符号化された複数の参照ラインのうち、符号化ラインの圧縮率が最も最大となる参照ラインを選択してから、この参照ラインのラスタデータを参照して前記符号化ラインのラスタデータを符号化して行くようにしているので、どのようなパターンのディザ画像が与えられても、常に最も効率の良い符号化処理を実行することができるという効果を奏する。
【図面の簡単な説明】
【図１】  この発明の一実施例に係るラスタデータの圧縮方法を適用した符号化システムの構成を示すブロック図である。
【図２】  エンコーダの構成の一例を示すブロック図である。
【図３】  画像データの一例を示す図である。
【図４】  ディザマトリクスの一例を示す図である。
【図５】  ディザ化画像の一例を示す図である。
【図６】  同実施例の圧縮処理を説明するための図である。
【図７】  同実施例のＭＲ符号化処理を説明するための図である。
【図８】  ディザ化画像のドットパターンを示す図である。
【図９】  各パターンの出現確率を説明するための図である。
【図１０】  ディザ化画像の他の一例を示す図である。
【図１１】  ＭＲ符号化処理の効果を説明するための図である。
【図１２】  復号システムの構成の一例を示すブロック図である。
【図１３】  エンコーダの構成の他の一例を示すブロック図である。
【符号の説明】
１…入力データバッファ、２…ラインバッファ、３…エンコーダ、４…選択制御部、５…送信部、６…再利用バッファ。
【図１】
0003776528.tif 000005
【図２】
0003776528.tif 000006
【図３】
0003776528.tif 000007
【図４】
0003776528.tif 000008
【図５】
0003776528.tif 000009
【図６】
0003776528.tif 000010
【図７】
0003776528.tif 000011
【図１０】
0003776528.tif 000012
【図１１】
0003776528.tif 000013
【図８】
0003776528.tif 000014
【図９】
0003776528.tif 000015
【図１２】
0003776528.tif 000016
【図１３】
0003776528.tif 000017