JP3810835B2 - 誤差拡散とハーフトーン処理を利用する画像処理方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、カラー画像とモノクロ印刷の両方に使用できる従来のハーフトーン手法を組み合わせた誤差拡散法に関するものである。
【０００２】
【従来の技術】
ファン（Fan ）に付与された米国特許第５，２２６，０９６号や、エシュバッハ（Eschbach）に付与された米国特許第５，２４３，４４３号あるいはヘインズ（Hains ）に付与された米国特許第５，３２１，５２５号等が開示しているように、ここ数年間従来のハーフトーン手法と誤差拡散を組み合わせる数々の技術が提案されている。このような組み合わせの背景となる考え方は、解像度を損なわないで、粗い量子化の結果生じる画質の劣化を削減することに根拠をおいている。粗い量子化による画質の劣化は、風景がほとんど変わらない画像領域によくみられ、バンディング現象（ｂａｎｄｉｎｇ）とも呼ばれている。バンディングは、使用できる灰色出力レベルの数が限られていることに起因し、一般にバンディングを起こす画像領域は、セルのサイズが小さくなると増加する傾向にある。これは、ハーフトーンセルが表現できるレベル数が少なくなることに等しい。
【０００３】
ファンとヘインズによる上述の手法は、画像を通常長方形で互いに共通部分のないブロックに分割し、その後画像がブロック毎に処理される。普通このプロセスの第一ステップは、順序付きのハーフトーン化で、その後ブロックに基づく誤差拡散技術を使って量子化誤差を削減する。ブロックに基づく誤差拡散技術の主な制限要因は、ブロックがハーフトーンセルをカバーしなければならないことである。ディジタルハーフトーンのしきいマトリックスが、長方形ブロックを周期的に繰り返すホラデー（Holladay）の方法を使って表すことができることは公知である（トーマス・Ｍ・ホラデー（Thomas M. Holladay）著「An Optimum Algorithm for Halftone Generation for Displays and Hard Copies'」Proc. Society for Information Display, １９８０年２１巻第２号１８５〜１９２ページ参照）。従って、モノクロ画像の印刷に関するアプリケーションでは、上述の制限はあまり問題とならない。なぜなら、そのような印刷は、幅対高さの比が２のホラデーブロックを持つ角度４５度のスクリーンを使用しているからである。
【０００４】
【発明が解決しようとする課題】
しかし、カラー画像の印刷の場合は、通常任意のスクリーン配置方向、すなわち角度１５度または７５度などのスクリーンを使用するので状況が異なってくる。このようなスクリーンは、典型的に幅対長さ比が非常に大きいか、非常に小さくなっている。そのためブロックベースの誤差拡散を使用することが困難になる。
【０００５】
従って本発明の目的は、誤差拡散と任意のスクリーン配置方向を使用するハーフトーン手法とを組み合わせることにより、画質の劣化を最小限に抑える画像処理方法を開示することにある。
【０００６】
【課題を解決するための手段】
本発明によると、ブロックの大きさと幅対高さ比が、ほとんどドットサイズやハーフトーンの角度に無関係の方法が提供されている。この手法を利用し、通常任意の配置方向を持つスクリーンを使用するカラー画像の再生の質を向上することができる。
【０００７】
このために本発明の画像処理方法は、
（１）それぞれがしきい値（スレッシュホルド・レベル）を有する複数の画素から形成され、かつ、相互に共通部分を持たない（ディスジョイント：disjointed）ブロックに画像を分割するステップ
（２）複数の代表レベルに前記しきい値をレベル分け（スレッシュホルディング：thresholding）するステップ
（３）各ブロックについて、前記代表レベルの１つを生む最大しきい値を表す第１しきい値と、前記代表レベルとは別の代表レベルを生む最小しきい値を表す第２しきい値とを判定するステップ
（４）各ブロックについて、第１しきい値を持つ画素数である第１数と、第２しきい値を持つ画素数である第２数を判定するステップ
（５）第１しきい値と第２しきい値とを比較するステップ
（６）第２しきい値が第１しきい値より大きい場合、各ブロックの入力データのレベルを測るステップ
（７）入力データのレベルが均一の場合、各ブロックの重大局部誤差と平均値を計算するステップ
（８）重大局部誤差に基づいて重大ブロックを判定するステップ
（９）重大局部誤差に前記第１数を乗じるステップ
（１０）その乗算の結果を伝播された誤差に加算し、各ブロックの総誤差を求めるステップ
（１１）各重大ブロックの総誤差が−０．５／Ｌ未満または０．５／Ｌ以上であるか否かを判定するステップ
（１２）前記重大ブロックの総誤差が０より大きい場合、前記第２しきい値を持つ重大ブロックの１つの画素を変更する第１変更ステップ
（１３）前記総誤差が０．５／Ｌ未満になるまで、その重大ブロックの総誤差を１／Ｌづつ減少するステップ
（１４）前記重大ブロックの総誤差が０より小さい場合、前記第１しきい値を持つ重大ブロックの１つの画素を変更する第２変更ステップ
（１５）前記総誤差が−０．５／Ｌ以上になるまで、その重大ブロックの総誤差を１／Ｌづつ増加するステップ
（１６）重大ブロックの減少もしくは増加後の総誤差、または減少も増加もされなかった重大ブロックおよび非重大ブロックの総誤差を、少なくとも１つの周辺ブロックに拡散するステップ
を含み、誤差拡散とハーフトーン処理を利用する。
【０００８】
本発明のもう１つの特徴は、量子化に起因する誤差が、「重大ブロック」内でのみ補正されることである。
【０００９】
さらに本発明の別の特徴は、量子化に起因する誤差が、フルドットのみで補正されることである。フルドットとは、均一な領域として発生する可能性の大きいドットと定義されている。ドットは複数の画素から構成されている。さらに、誤差拡散は、最初の連続トーン画像がほとんど変化のない灰色レベルを持つ領域内でのみ実行される。この考え方は次の２つの点に基づいている。すなわち、（１）非常に細かい画像の領域では、肉眼で精密な灰色レベルおよび量子化誤差を見分けることができない。（２）この技術は、部分ドットに関する画素値を変えることによって生じうる画質の劣化を避けることである。
【００１０】
【発明の実施の形態】
図１〜４は、本発明を適用した一実施形態のステップを説明するフローチャートである。ここで、入力される灰色トーンが［０，１］の範囲内にあり、出力される値は０か１であるものとする。
【００１１】
まず、予備のステップＳ５０で、画像を互いに共通部分のないブロックに分割する。ステップＳ１００では、それぞれの画素が、使用されているハーフトーンセルから決まる適切なしきい値に従って、レベル分けされる。
【００１２】
図５（Ａ）には、７つの異なる画素参照レベルを持つ２つのドット（各ドットは１×７の画素群からなる）が示されている。ドット１の画素１はしきい値として１．５／Ｌという値、画素５は同様に５．５／Ｌという値を持つ。ここでＬはセルの大きさを表し、本例では７である。
【００１３】
７つの画素による各グループは、ドットの周期にも対応している。レベル分け（順序付けディサーリング：ｄｉｔｈｅｒｉｎｇ）の結果が図５（Ｂ）に示される。そこでは３つの画素からなる各グループが、ブロック１、２、３、４にそれぞれ対応している。同図に示すように、ブロック（ここではブロック３）が複数の周期（ドット）をまたぐ可能性もある。ここでは一例として、２．５／Ｌのデータが続けて入力されるものとする。このとき、平均出力値も２．５Ｌにならなければならず、すべての周期の平均が２．５／Ｌになるべきである。２．５／Ｌ以下のしきい値には２進数の１が与えられ、２．５／Ｌより大きいしきい値には２進数の０が与えられる。
【００１４】
図６（Ａ）は、図５（Ａ）に示された２つのドット周期のそれぞれの理想値を示している。最初の周期は、３／Ｌ（すなわち２進数の１で表される「オン」状態に合計３つの画素がある）で、２番目の周期は、２／Ｌ（すなわち２進数の１で表される「オン」状態に第１および第７番目の画素がある）となっている。それからわかるように、この２つの周期の平均値は、３／Ｌと２／Ｌの平均をとり、所期の値２．５／Ｌとなる。
【００１５】
図５（Ｂ）に示され、図６（Ｂ）に載せられた実際値を、図６（Ａ）に示された理想値と比較すると、レベル分けの結果生じる２つの周期の平均が２．５／Ｌではなく、３／Ｌとなっている。図６（Ｂ）に示された第１周期は３／Ｌ（第１、２、７番目の画素が「オン」状態）、第２周期も、３／Ｌの値を持つ。レベル分けの結果得られる平均値が３／Ｌなので、初期の灰色レベルに誤差が生じることになる。この誤差を補正するには、図６（Ｂ）に示された２つの周期のどちらか一方の値が３／Ｌから２／Ｌに変えられ、２つの周期の平均を２．５／Ｌとしなければならない。このために、２つの周期の一方の画素を２進数の１から０に変える必要がある。このように、図６（Ｂ）のレベル分けは、従来の技術の限界を示すものである。
【００１６】
図１に戻る。次のステップＳ２００では、
１）「オン」画素（すなわちあるブロックの第１の代表レベル）を生じる第１（かつ最大）のしきい値であるＢ_MAX
２）「オフ」画素（すなわちあるブロックの第２の代表レベル）を生じる第２（かつ最小）のしきい値であるＷ_MIN
３）しきい値Ｂ_MAX のブロックにおける第１の画素数であるＮＢ_MAX
４）しきい値Ｗ_MIN のブロックにおける第２の画素数であるＮＷ_MIN
がそれぞれ記録される。図５（Ａ）（Ｂ）に示される第１ブロックの、２進数の１の生じる最大のしきい値は２．５／Ｌであり、Ｂ_MAX ＝２．５／Ｌとなる。また、２進数の０を生じる最小のしきい値は３．５／Ｌで、従ってＷ_MIN ＝３．５／Ｌとなる。
【００１７】
次にＢ_MAX とＷ_MIN が比較され、レベル分けの結果得られる出力パターンがフルドットパターン（またはフルドットパターンの一部）か、部分ドットパターンかが判定される。部分ドットは、画像に端部（エッジ）が生じている領域でハーフトーン処理が行われた結果生じる。ここで端部とは、画像の灰色レベルの突然の変化と定義することができる。部分ドットは、そうした突然の変化を反映するものであり、ドットの一部が１つの灰色レベルで、同じドットの他の部分が別の灰色レベルとなる。
【００１８】
ここで注意すべき特徴は、特定のディサーマトリックス、すなわちハーフトーンセルにおいて、セル領域全体にわたるレベル分け操作が不均一であることである。すなわち、セル内の１画素では高レベルのしきい値を超え、同じセル内の他の画素では低レベルのしきい値に達していない状態があるということである。すなわち、部分ドットは、十分に均一な灰色レベルを持つ所定のパターンのいずれにも該当しないパターンとして検出される。従って、部分ドット上には均一な灰色レベルがないので、そのドットを２つの灰色レベルとして扱うことができる。
【００１９】
フルドットパターンは、Ｗ_MIN ＞Ｂ_MAX が満たされると生じ、部分ドットは、反対の条件、すなわち、Ｗ_MIN ≦Ｂ_MAX の時に生じる。もしステップＳ３００でドットが部分ドットと判定されると、特定のブロックの誤差が、補正されずにすべて周囲のブロックに伝播される。一方、ステップＳ３００で、ドットがフルドットであると判定されると、次のステップＳ４００が実行される。
【００２０】
図７に示されているように、図５（Ａ）のドットはすべてフルドットと判定されている。ここで、ブロック２および４は両方とも、「オン」の画素がないこと、即ち、２進数の１を表す画素がないことに注意する必要がある。このようにＢ_MAX が存在しない場合には、Ｂ_MAX を−０．５／Ｌに設定する。同様に、ブロック３には「オフ」の状態の画素がなく、最小Ｗ_MIN が存在しないため、Ｗ_MIN が１＋０．５／Ｌに設定される。
【００２１】
次に、図５（Ａ）に戻り、ＮＢ_MAX とＮＷ_MIN を決める。それぞれのブロックをみると、Ｂ_MAX （または２．５／Ｌの値）がブロック１で１回起こっている。従って、ＮＢ_MAX が１に設定される。同様に、ＮＷ_MIN （Ｗ_MIN ＝３．５／Ｌ）がブロック１で１回起っている。従って、ブロック１のＮＷ_MIN が１に設定される。同様にしてそれぞれのブロックに関連するＮＢ_MAX とＮＷ_MIN が定められる。
【００２２】
ステップＳ４００では、それぞれのブロックへのデータ入力のレベルが測られ、それらが同質または均一かどうか判定される。同質かどうかは、ブロックへのデータ入力のダイナミックレンジを適切なしきい値と比べて決定する。もしブロックが同質でない場合は、そのブロックの全体の誤差が補正されずに、周辺のブロックに伝播される。本実施形態では、２．５Ｌばかりがつづけて入力されると仮定しているため、その入力は均一であり、次のステップＳ５００の処理が行なわれる。ステップＳ５００では、それぞれのブロックの平均灰色値（エリア）ｉ^* が、次の公式により計算される。
【００２３】
ｉ^* ＝Σ _k ε_block ｙ（ｋ）／ｂｌｏｃｋ ｓｉｚｅ
ここでΣはブロック内の画素に対する総和であり、ｙ（ｋ）は各画素の色を示す数値である。ここでは、入力値として定数２．５／Ｌが選ばれているので、それぞれのブロックの平均灰色値も定数２．５／Ｌでなければならない。
【００２４】
次に、ステップＳ５１０でそれぞれのブロックの重大（クリティカル）局部誤差が下記の公式により計算される。
【００２５】
重大局部誤差 ＝｜［ｉ−（Ｂ_MAX ＋０．５／Ｌ］｜
ブロック１〜４の重大局部誤差が図８に示されている。図８を参照すると、特定のブロックの重大局部誤差の絶対値が０．５／Ｌ以下であれば、その重大局部誤差は実際の誤差に等しい（例えば、ブロック１の重大局部誤差は−０．５／Ｌであるため、絶対値は＋０．５／Ｌであり、重大局部誤差はもとの−０．５／Ｌでよい）。一方、もし重大局部誤差の絶対値が、０．５／Ｌよりも大きい場合、重大局部誤差は０に設定される（例えば、ブロック２の重大局部誤差は２．５／Ｌであるから、絶対値は＋２．５／Ｌであり、重大局部誤差は０となる）。
【００２６】
ステップＳ５２０では、それぞれのブロックが「重大（クリティカル）ブロック」かどうか判定するため分析する。次の条件の１つまたは両方が満たすブロックは、「重大ブロック」と呼ばれる。すなわち、
１／Ｌ≧ ｉ^* −Ｂ_MAX ≧０
または、
０．５／Ｌ≧Ｗ_MIN −ｉ^* ≧０
図９に示されているように、ブロック１および３は重大ブロックである。従って、量子化に起因する誤差は、これらのブロック内で補正される。しかし、ブロックが重大ブロックと判定されない場合は、このような誤差がブロック内で補正されることはない。
【００２７】
ステップＳ６１０では、まず重大局部誤差にＮＢ_MAX の値を掛け（ステップ６０５）、それに周囲のブロックより拡散または伝播された誤差を加算し、総誤差が得られる。もし、
（１）（ａ）総誤差≧０．５／Ｌ または （ｂ）総誤差＜−０．５／Ｌ
なら、重大ブロックの画素が変更される（ステップＳ７０１とＳ７０２）。ブロック内のどの画素が変えられるべきか決めるため、次の規則（２）（３）を用いる。
【００２８】
（２）もし、総誤差が０より大の場合、しきい値Ｗ_MIN を有するブロックの画素の２進数値を変える。
【００２９】
（３）もし、総誤差が０より小の場合、しきい値Ｂ_MAX を有するブロックの画素の２進数値を変える。
【００３０】
規則（２）（３）は、１ブロックにつき１画素のみがＢ_MAX またはＷ_MIN の値をとるものと仮定している。もし規則（２）において、１ブロックにつき２以上の画素がＷ_MIN の値をとる場合、Ｗ_MIN に最も近い入力を持つ画素を選び、それを変える。同様に、１ブロックにつき２以上の画素がＢ_MAX の値をとる場合は、Ｂ_MAX に最も近い入力を持つ画素を選ぶ。
【００３１】
変更すべき画素を持つブロックを選択した後、ステップＳ９１０で１／Ｌずつ総誤差を減少または増加する。最初の総誤差の符号が正か負かによって、減少か増加が決まる。もし最初の総誤差が正の場合、総誤差が０．５／Ｌ以下になるまで、または選択されたブロックの変更すべき画素数がＮＷ_MIN になるまで、１／Ｌずつ減少される。このようにして、量子化による誤差が重大ブロック内で補正される。一方、最初の総誤差が負の場合、総誤差は（ステップＳ９１０で）−０．５／Ｌ以上になるまで、または選択されたブロックの変更すべき画素数がＮＢ_MAX になるまで１／Ｌずつ増加される。
【００３２】
図１０は、図５〜９で参照されたと同じ４つの図解ブロックを使って得られたステップＳ６００〜Ｓ９１０の例の１つの結果をまとめたものである。
【００３３】
具体的にいうと、まずブロック１の重大局部誤差−０．５／Ｌに１、すなわちＮＢ_MAX ＝１を掛け、それを伝播の剰余０に加算し（ブロック１には先行するブロックや周辺のブロックがないものとする）総誤差−０．５／Ｌを得る。ブロック１は、重大ブロックなので（図８、９を参照）誤差補正が実行される可能性がある。
【００３４】
ここで、重大ブロックにはまず、数式（１）（ａ）および（ｂ）が適用されるが、この場合は総誤差が−０．５／Ｌなので、数式（１）（ａ）、（ｂ）の条件がともに満たされず、誤差補正は起こらない。つづいて、ブロック１の総誤差がブロック２に伝播される。
【００３５】
ここで留意すべきことは、本発明を説明する上で、拡散は一次元でのみ検討されれば十分ではあるが、拡散は数個の周辺ブロックを含む、一次元以上の次元でも起こりうるということである。
【００３６】
ブロック２の総誤差は−０．５／Ｌとなっている。ブロック２は、重大ブロックではないので、数式（１）（ａ）または（ｂ）は適用されない。従ってブロック２の総誤差がブロック３に拡散される。ブロック３は、重大ブロック（図８、９参照）で、総誤差−１．０／Ｌを有している。ここでは数式（１）（ｂ）が満たされるので、次に規則（２）および（３）が検討される。ブロック３の総誤差が−１．０／Ｌで０より小さいので、（３）があてはまる。
【００３７】
規則（３）により、Ｂ_MAX 、すなわち２．５／Ｌに対応する画素を変更することが要求される。すなわち、ブロック３の画素３を２進数の１から０に変えなければならない。それにより、周期２の平均値を２／Ｌに変え（周期２の画素１および７はともに、２進数の値１を有している）全体の周期平均値（周期１と周期２）を２．５／Ｌとしている。
【００３８】
ここで、総誤差に１．０／Ｌが加えられる。その後、総誤差が−０．５／Ｌ以上になったかどうか検討される。もしなっていなければ、同じ処理を総誤差が−０．５／Ｌ以上になるか、そのブロック内で変更された画素の数がＮＢ_MAX に達するまで繰り返す。この例の場合、１／Ｌが１回加算された時点で総誤差が０になるため、処理は終了する。この後、総誤差がブロック４に伝播される。
【００３９】
図１１は、従来のスクリーン手法を使った画像を示している。一方、図１２は、本発明を適用したスクリーンを示している。図１１は、ドットサイズが１×２６でシフトパラメータが５のスクリーンを使用している。図１１では、粗い量子化の影響が見られ、図１２では粗い量子化の影響が大幅に削減されている。図１２のブロックの大きさは、２×４となっている。
【００４０】
【発明の効果】
本発明によれば、誤差拡散と任意のスクリーン配置方向を使用するハーフトーン手法とを組み合わせることにより、画質の劣化を最小限に抑える画像処理方法が実現できる。
【図面の簡単な説明】
【図１】 本発明の実施形態の処理を示すフローチャートである。
【図２】 本発明の実施形態の処理を示すフローチャートである。
【図３】 本発明の実施形態の処理を示すフローチャートである。
【図４】 本発明の実施形態の処理を示すフローチャートである。
【図５】 （Ａ）および（Ｂ）は、従来のしきい値処理を施す前と後の２つのドットを示す図である。
【図６】 （Ａ）および（Ｂ）は、理想的しきい値処理の結果と従来のしきい値処理技術の結果をそれぞれ示す図である。
【図７】 フルドットを部分ドットから分離する際に使われる４つの図解ブロックの最高値と最低値を示す図である。
【図８】 ４つの図解画像ブロックの重大局部誤差を示す図である。
【図９】 図８の重大局部誤差を使って重大ブロックを鑑定する様子を示す図である。
【図１０】 ４つの図解ブロックの誤差拡散を示す図である。
【図１１】 従来のスクリーンの例を示す、ディスプレイに表示した中間調画像の写真である。
【図１２】 本発明の実施形態によるスクリーンの例を示す、ディスプレイに表示した中間調画像の写真である。

Claims (1)

1. それぞれがしきい値を有する複数の画素から形成され、かつ、相互に共通部分を持たないブロックに画像を分割するステップと、
   複数の代表レベルに前記しきい値をレベル分けするステップと、
   各ブロックについて、前記代表レベルの１つを生む最大しきい値を表す第１しきい値と、前記代表レベルとは別の代表レベルを生む最小しきい値を表す第２しきい値とを判定するステップと、
   各ブロックについて、第１しきい値を持つ画素数である第１数と、第２しきい値を持つ画素数である第２数を判定するステップと、
   第１しきい値と第２しきい値とを比較するステップと、
   第２しきい値が第１しきい値より大きい場合、各ブロックの入力データのレベルを測るステップと、
   入力データのレベルが均一の場合、各ブロックの重大局部誤差と平均値を計算するステップと、
   重大局部誤差に基づいて重大ブロックを判定するステップと、
   重大局部誤差に前記第１数を乗じるステップと、
   その乗算の結果を伝播された誤差に加算し、各ブロックの総誤差を求めるステップと、
   各重大ブロックの総誤差が−０．５／Ｌ未満または０．５／Ｌ以上であるか否かを判定するステップと、
   前記重大ブロックの総誤差が０より大きい場合、前記第２しきい値を持つ重大ブロックの１つの画素を変更する第１変更ステップと、
   前記総誤差が０．５／Ｌ未満になるまで、その重大ブロックの総誤差を１／Ｌづつ減少するステップと、
   前記重大ブロックの総誤差が０より小さい場合、前記第１しきい値を持つ重大ブロックの１つの画素を変更する第２変更ステップと、
   前記総誤差が−０．５／Ｌ以上になるまで、その重大ブロックの総誤差を１／Ｌづつ増加するステップと、
   重大ブロックの減少もしくは増加後の総誤差、または減少も増加もされなかった重大ブロックおよび非重大ブロックの総誤差を、少なくとも１つの周辺ブロックに拡散するステップと、
   を含むことを特徴とする、誤差拡散とハーフトーン処理を利用する画像処理方法。

Images