(57)【特許請求の範囲】
【請求項１】
階調依存型誤差拡散ハーフトーン化のための方法であって、
少なくとも１つのしきい値および複数の誤差重み付けによる誤差拡散を実行するステップと、
入力画素値に依存する少なくとも１つのしきい値および入力画素値に依存する複数の誤差重み付けを得るステップと、を含み、
前記少なくとも１つのしきい値および前記複数の誤差重み付けが最適化されるよう、前記方法は、さらに、
階調レベルを有するパッチを提供するステップと、
直接２分探索ハーフトーン化によって、前記パッチの第１のハーフトーン・パターンを生成するステップと、
初期しきい値および初期誤差重み付けを使用して、誤差拡散ハーフトーン化によって前記パッチの第２のハーフトーン・パターンを生成するステップと、
前記第１のハーフトーン・パターンを前記第２のハーフトーン・パターンと比較するステップと、
前記第１のハーフトーン・パターンの品質および前記第２のハーフトーン・パターンの品質の差を表す第１の費用関数を最小にするように、前記初期しきい値および初期誤差重み付けを変更するステップと、
を含む、方法。
【請求項２】
さらに、
入力画素値を入力するステップと、
前記入力画素値、および、前に処理した画素から拡散された量子化誤差に基づいて、修正画素値を生成するステップと、
前記少なくとも１つのしきい値を前記修正画素値と比較して、２値の出力画素値を生成するステップと、
前記２値の出力画素値および前記修正画素値の間の差に基づいて、量子化誤差を生成するステップと、
前記複数の誤差重み付けを有する前記量子化誤差を、次に処理する画素に拡散させるステップと、
を含む、請求項１に記載の方法。
【請求項３】
前記少なくとも１つのしきい値を得ることは、上のしきい値および下のしきい値を得ることを含み、
前記少なくとも１つのしきい値を修正画素値と比較することは、前記上のしきい値を前記修正画素値と比較すると共に、前記下のしきい値を前記修正画素値と比較して、前記２値の出力画素を生成することを含む、
請求項２に記載の方法。
【請求項４】
前記修正画素値が、前記上のしきい値および前記下のしきい値の間にある場合には、さらに、
ほぼ中間調レベルを有する２値のビットマップ・パターンを提供するステップと、
前記入力画素と同じ座標にある前記２値のビットマップ・パターンの画素値を使用して、前記２値の出力画素を生成するステップと、
を含む、請求項３に記載の方法。
【請求項５】
前記少なくとも１つのしきい値および前記複数の誤差重みが最適化されるよう、前記方法は、さらに、
階調レベルを有するパッチを提供するステップと、
人間視覚系モデルを使用して前記パッチをフィルタリングし、第１のフィルタリングされた画像を生成するステップと、
初期しきい値および初期誤差重みを使用し、誤差拡散ハーフトーン化によって前記パッチの第１のハーフトーン・パターンを生成するステップと、
人間視覚系モデル（２３０）を使用して前記第１のハーフトーン・パターンをフィルタリングし、第２のフィルタリングされた画像を生成するステップと、
前記第１のフィルタリングされた画像を前記第２のフィルタリングされた画像と比較するステップと、
知覚される二乗誤差の合計である第２の費用関数を最小にするように、前記初期しきい値および初期誤差重みを変更するステップと、
を含む、請求項１に記載の方法。
【請求項６】
前記第２の費用関数は、知覚される二乗誤差の合計であり、前記第１の費用関数は、以下の式で表され、
【数１】
0004268313.tif 000024
該式において、ＧDBS（ｕ，ｖ）は前記第１のハーフトーン・パターンの高速フーリエ変換の期待値の大きさを示し、ＧTDED（ｕ，ｖ）は前記第２のハーフトーン・パターンの高速フーリエ変換の期待値の大きさを示しており、
前記第２の費用関数は、階調レベル範囲中の端部にある階調レベルに使用され、前記第１の費用関数は、階調レベル範囲の中間調における階調レベルに使用される、請求項５に記載の方法。
【請求項７】
さらに、
確率変数を修正項に加えることによって起動時のアーティファクトを防ぐステップを含み、該修正項が、前に処理された画素から拡散された量子化誤差の和である、
請求項１に記載の方法。
【請求項８】
さらに、
前記入力画素値がハイライトまたはシャドウの階調レベルであるとき、前記複数の誤差重み付けを有する前記量子化誤差を、第１の領域上の次に処理される画素に拡散するステップであって、該第１の領域の一部の画素が、該量子化誤差の一部を受け取るようにする、ステップと、
前記入力画素値が中間調レベルのとき、前記複数の誤差重み付けを有する前記量子化誤差を、第２の領域上の次に処理される画素に拡散するステップと、を含み、
前記第１の領域が、前記第２の領域よりも大きい、
請求項２に記載の方法。
【請求項９】
さらに、
前記入力画素値が、ハイライトレベルおよび中間調レベルの間の遷移レベルにあるとき、またはシャドウレベルおよび該中間調レベルの間の遷移レベルにあるとき、前記複数の誤差重み付けを有する前記量子化誤差を、第３の領域上の次に処理される画素に拡散するステップであって、該第３の領域の一部の画素が、該量子化誤差の一部を受け取るようにする、ステップと、を含み、
該第３の領域が、前記第２の領域よりも大きく、かつ前記第１の領域よりも小さい、
請求項８に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、階調依存型誤差拡散ハーフトーン化方法に関し、より具体的には、高品質なハーフトーン画像を生成するよう最適化されたしきい値および誤差重みによる効率的な階調依存型誤差拡散ハーフトーン化方法に関する。
【０００２】
【従来の技術】
チャート、図、写真のような連続階調画像は、画素（ピクセル）の２次元マトリクスとして表すことができる。それぞれの画素の空間解像度および輝度レベルは、使用する特定の出力装置に対応するよう選択される。
【０００３】
デジタル・ハーフトーン化は、連続階調画像を２値画像（すなわち、画素は、オンまたはオフのいずれかである）に変換する処理である。人間の視覚系の低域特性により、２値のテクスチャ・パターンを連続階調として知覚することができる。インクジェット・プリンタなどのハードコピー出力装置は、インクの液滴を放出して媒体上にドットを形成する２値装置である。このようなプリンタは連続階調画像を印刷することができず、したがって、デジタル・ハーフトーン化を使用して、媒体上に印刷された２値画像がオリジナル画像と同じように知覚されるようにする。
【０００４】
印刷のアプリケーションでは、画素値を表すのに吸収率が使用される。印刷処理は、一般に白紙上に吸収性のドットを配置する。理想的な装置モデルでは、着色剤の吸収率は１（ドットを印刷する）であり、用紙の吸収率は０（ドットを印刷しない）である。一般的な連続階調すなわちグレースケール（gray scale）の画像の画素値は、０〜１の吸収率の単位で表される。当然ながら、画素値を、従来のコンピュータ・モニタで使用されているような「連続階調に近い」範囲、たとえば０〜２５５で表すことができるということは理解されたい。そのような場合の２値階調レベルは、０（オフ）または２５５（オン）のいずれかで表される。
【０００５】
ハーフトーン化方法は、参照によりここで取り入れるRobert Ulichneyによる書籍「Digital Halftoning」（ＭＩＴ出版、1987年）に記載されている。一般に、ハーフトーン化方法を３つ、すなわち反復最適化法（iterative optimization method）、スクリーニング法（screening method）および誤差拡散法に分類することができる。
【０００６】
反復法は、人間の視覚系モデルを使用して、連続階調画像およびハーフトーン画像の間の知覚誤差（perceived error）を最小にする。反復法は、高品質のハーフトーン画像を作成するのに使用することができる直接２分探索法（direct binary search）である。残念ながら、反復法は非常に多くの演算を必要とし、実時間の画像処理は実現不可能である。
【０００７】
一方、スクリーニング法はあまり複雑ではないハーフトーン化方法であり、この方法では高品質のハーフトーン画像は提供されない。スクリーンは、しきい値のマトリクスによって定義される。連続階調画像を２値化するため、しきい値のマトリクスが画像上に周期的にタイル状に配置される。対応するマトリクスのしきい値よりも大きい画素は１に２値化され、そうでない画素は０に２値化される。
【０００８】
誤差拡散ハーフトーン化方法は、フィードバック・ループを使用して、入力画素値から過去の重み付けされた拡散誤差値を減算し、修正された画素値を得る。次に、この修正画素値をしきい値と比較して、ハーフトーン出力値を決定する。このように、特定の画素にドットを印刷するかどうかについての決定は、その画素の連続階調レベルだけでなく、前に処理された画素に対して行われたことにも基づく。拡散されるべき誤差すなわち量子化誤差は、出力値から修正画素値を減算することによって得られる。その後、その先の画素位置から、重み付けされた誤差を減算することによって、誤差をその先の一組の画素位置に拡散する。重み（weight）の合計が１の場合には、局所的な階調が保全される。
【０００９】
誤差拡散は、直接２分探索に比べて効率的なハーフトーン化方法ではあるが、スクリーニング法よりも複雑である。しかしながら、従来の誤差拡散法によって生成されるハーフトーン画像は、一般に、直接２分探索法によって生成される画像よりも品質が低い。
【００１０】
周知の誤差拡散技術は、参照によりここで取り入れる、R.FloydおよびL.Steinbergによる論文「Adaptive Algorithm for Spatial Grey Scale」（SID Int'l. Sym. Digest of Tech. Papersのページ36〜37(1975年)）に記載されている。
【００１１】
図１に、従来の誤差拡散システム１０のブロック図を示す。図１に示したように、連続階調値を有する入力画素値は、ｆ[ｍ，ｎ]として表される。ここで、ｍおよびｎは画素位置である。修正画素値は、ｕ［ｍ，ｎ］によって表される。出力ハーフトーン値はｇ［ｍ，ｎ］で表され、これは次の式（１）のようなしきい値演算によって求められる。ここで、ｔ［ｍ，ｎ］はしきい値マトリクス１２である。
【００１２】
【数１】
0004268313.tif 000002
量子化誤差ｄ［ｍ，ｎ］は、以下の式（２）のように、加算器１４において、出力ハーフトーン値ｇ［ｍ，ｎ］から修正画素値ｕ［ｍ，ｎ］を減算することによって求められる。
【００１３】
【数２】
ｄ[ｍ,ｎ]=ｇ[ｍ,ｎ]-ｕ[ｍ,ｎ]                         式（２）
その後、量子化誤差ｄ［ｍ，ｎ］は、誤差重み付けマトリクス１６を介して、近傍の次に処理される画素位置に拡散される。
【００１４】
修正画素値ｕ［ｍ，ｎ］は、次の式（３）のように更新される。
【００１５】
【数３】
0004268313.tif 000003
ここで、ｗ［ｋ，ｌ］は誤差重み付けマトリクス１６である。局所的階調を保全するためには、式（４）が成立することが必要である。
【００１６】
【数４】
0004268313.tif 000004
こうして、加算器１８への入力を、次の式（５）のように表すことができる。
【００１７】
【数５】
0004268313.tif 000005
ここで、ｃ［ｍ，ｎ］は、次の式（６）で定義される修正項である。
【００１８】
【数６】
0004268313.tif 000006
このように、修正項ｃ［ｍ，ｎ］は、前に処理した画素から拡散された量子化誤差である。
【００１９】
従来の誤差拡散システム１０は、画像を従来のラスタ走査の順番で２値化する。しきい値マトリクス１２のしきい値ｔ［ｍ，ｎ］は、すべてのｍ，ｎについて一定の値、たとえば０．５を有する。誤差重み付けマトリクス１６は、図２に示したように、誤差を拡散させるのに４つのゼロでない重みｗ［０，１］＝７／１６、ｗ［１，−１］＝３／１６、ｗ［１，０］＝５／１６およびｗ［１，１］＝１／１６を使用する。図２は誤差の配分を示す図であり、処理している現在の画素２２を「Ｐ」で示す。
【００２０】
従来の誤差拡散システム１０は、滑らかで鮮鋭なハーフトーン画像を生成することで長い間知られてきた。図３は、従来の誤差拡散システム１０を使用して生成された階調ハーフトーン画像３０である。図３の画像３０は、完全な黒すなわち階調１から、完全な白すなわち階調０に及ぶ（吸収率を使用する場合）。図３から明らかなように、システム１０は、ハイライト（明るい）領域およびシャドウ（暗い）領域において、「虫（worm）」３２、３３や、中間調領域の構造化パターン３４、３６、３８のような、目に見えるアーティファクトを生成する。
【００２１】
ハーフトーンの品質を向上させるために、多くの誤差拡散法の変形および改良が行われてきた。たとえば、誤差拡散システムの中には、固定のしきい値を、順序立てられたしきい値マトリクスに置き換えることにより、または対角線の１つに沿ってしきい値を散在させたマトリクスを使用することにより、しきい値を修正するものがある。後者の場合、その対角線の方向は、「虫」アーティファクトが広がる方向に垂直である。
【００２２】
参照によりここで取り入れる、J.Sullivan、R. MillerおよびG.Piosによる「Image Halftoning Using a Visual Model In Error Diffusion」（J.Opt.Soc.Am.A、Vol.10、No.8、ページ1714〜1724、1993年8月）は、誤差拡散システムのアーキテクチャに直接組み込む視覚系モデルを使用し、過去の出力によって量子化しきい値を決定する。Sullivanらが示すシステムのアーキテクチャは、視覚系モデルに使用される余分のフィルタのために複雑となり、これは追加の演算を必要とする。
【００２３】
誤差拡散法の中には、誤差基準を最小にする重みを調整するために、フィルタの重みをランダムにディザリングする処理、および適応信号処理にＬＭＳアルゴリズムを使用する処理を含む、可変の誤差重みを使用するものもある。さらに、ここで参照により取り入れるB.W.Kolpatzik およびC.A.Boumanによる「Optimized Error Diffusion for Image Display」（Journal of Electronic Imaging 1(3)、ページ277〜292、1992年7月）と、P.W.WongおよびJ.P.Allebachによる論文「Optimum Error Diffusion Kernel Design」（Proceedings of SPIE/IS&T Symposium on Electronic Imaging、San Jose、CA、1997年1月）とで考察されている他の誤差拡散方法は、視覚モデリングに基づく最適誤差重み付けの設計を使用する。しかしながら、これらの方法は、階調依存型手法で設定される重みを最適化することはしていない。
【００２４】
【発明が解決しようとする課題】
現在の誤差拡散法は大量の処理を必要とし、望ましくない目に見えるアーティファクトを発生させ、および／または直接２分探索のハーフトーン化よりも画像の品質が低い。
【００２５】
したがって、高品質画像を提供する効率的なハーフトーン化方法が必要とされる。
【００２６】
【課題を解決するための手段】
効率的なハーフトーン化システムは、モデルベースの費用関数を最小にすることによって最適化される階調依存型のしきい値および誤差重み付けによる階調依存型誤差拡散ハーフトーン化方法を使用する。それぞれの中間調レベルごとに、直接２分探索法および誤差拡散法によってハーフトーン画像が生成される。ハーフトーン画像の高速フーリエ変換の大きさ（magnitude）が視覚的費用関数を使用して比較され、しきい値および誤差重み付けが、費用関数を最小にするよう変更される。ハイライトおよびシャドウの階調レベルについては、人間視覚系（human visual system ： ＨＶＳ）モデルを介して画像をフィルタリングした後、誤差拡散システムからのハーフトーン画像が連続階調画像と比較される。この場合も費用関数を最小にすることによって、しきい値および誤差重み付けが最適化される。しきい値および誤差重み付けを最適化して、それらの値をルックアップテーブル（look-up table）に保持することができる。こうして、この発明による階調依存型誤差拡散システムは、高品質画像を生成しながら画像を効率的に処理する。誤差拡散アーキテクチャに対して追加のフィルタを全く使用しないので、さらなる計算を必要としない。
【００２７】
階調依存型誤差拡散ハーフトーン化方法は、上および下のしきい値を使用して、修正画素値と比較する。修正画素値が、上のしきい値よりも大きければドットが印刷され、下のしきい値よりも小さければドットは印刷されず、その間の値ならば、２値ビットマップを使用してドットを印刷すべきかどうか判断する。
【００２８】
さらに、従来のラスタ走査および２行蛇行走査（2-row serpentine scan）について、この発明の実施形態では、誤差が拡散される領域が入力画素値にしたがって変更される。こうして、入力画素値が階調範囲の端部にある場合、たとえばハイライトまたはシャドウの階調レベルにある場合、誤差は大きい領域に拡散される。一方、入力画素値が中間調領域にある場合、誤差は、より小さい領域に拡散される。また、遷移階調領域を使用することもでき、その場合誤差は、中間調の拡散領域よりも大きいがハイライト／シャドウの階調領域よりも小さい領域に拡散される。さらに、入力画素値がすべてオンまたはすべてオフ、すなわちすべて１またはすべて０のいずれかである２値領域の場合、従来のラスタ走査を使用すれば、誤差全体を垂直方向または水平方向に拡散させることができる。
【００２９】
起動アーティファクトの発生を回避するため、平均修正項のものと等しい分散を有する乱雑音（random noise）を加えることにより、画素値を修正することができる。
【００３０】
【発明の実施の形態】
図４は、この明細書で説明する誤差拡散法のすべてまたは一部を実行する処理回路を備えるインクジェット・プリンタ１００の１つのタイプを示す。このインクジェット・プリンタは、カバー１０１、未使用の用紙１０４を保持する用紙トレイ１０２、印刷したページを受け取る出力トレイ１０６、インク印刷カートリッジ１０８、および用紙にドットを印刷中にスライド・バー１１２に沿って摺動する走査カートリッジ１１０を備える。１つの実施形態において、インクジェット・プリンタは、シアン（Ｃ）、マジェンタ（Ｍ）、イエロー（Ｙ）およびブラック（Ｋ）のインク印刷カートリッジを含むカラー印刷カートリッジ１０８を使用するカラー・プリンタである。ＣＭＹのようなインクの他の組合せ、またはブラック（Ｋ）のような単色インクを使用することもできる。さらに、各色のインクごとに別々の印刷カートリッジを設ける必要はなく、たとえば、単一の取替え可能な印刷カートリッジは、各色のインク放出ノズルの関連するアレイと共に、複数色のインクを含むことができる。また、走査プリントヘッドのそれぞれのインク供給部は、固定されていてもよく、管によってプリントヘッドに接続されていてもよい。インクジェット・プリンタのインクジェット印刷カートリッジは、当業者には周知である。Brian J. Keefeらによる「Ink Channel Structure for Inkjet Printhead」と題する米国特許第５，５９４，４８１号は、適切なインクジェット印刷カートリッジの構造を記載しており、ここで参照により取り入れる。
【００３１】
図５は、ホスト・コンピュータ１２２、モニタ１２４（たとえば、ＣＲＴ）、およびプリンタ１２６を備える印刷システム１２０の概略図である。プリンタ１２６は、インクジェット・プリンタを含むブラックおよび／またはカラーのドットを印刷する任意のタイプのプリンタでよい。プリンタ１２６は、後で説明するように媒体を横切って走査し、インクの液滴を印刷する印刷カートリッジ１２７を備える。また、たとえば異なる色のインクを提供するために、追加の印刷カートリッジ１２８をプリンタ１２６に含ませることもできる。印刷カートリッジ１２７、１２８の一方または両方が、複数のインクを含むことができる。図４のプリンタ１００を、図５のプリンタ１２６の代わりに用いることができる。プリンタ１２６は、印刷カートリッジ１２７、１２８によるドットの印刷を制御するプリンタ・コントローラ１２９を備える。印刷カートリッジ１２７、１２８は、３００ドット／インチ（ＤＰＩ）、６００ＤＰＩ、または他の任意の解像度で印刷することができる。
【００３２】
図６は、コンピュータ１２２からプリンタ１２６までの画像情報の標準的な流れを示す。最初に画像は、作成され、またはコンピュータ１２２のメモリに取り込まれる。この画像をコンピュータ・モニタ１２４上に表示させるために、この画像は、一般に加法ＲＧＢ色空間で表現される。画面上のそれぞれの画素位置は、輝度または階調の２５６レベルのうちのいずれかの１レベル（０〜２５５）の赤、緑および青で照明されることができる。２５６レベル（２8＝２５６）を表現するには８ビットが必要である。３原色のそれぞれが８ビットを必要とするので、ＲＧＢカラー・モニタは２４ビット・カラー（３×８＝２４）を生成する、と一般に言われる。この画像は、特定のモニタの空間解像度で表現される。典型的なモニタは、垂直および水平方向に１インチ（２５．４ミリメートル）四方あたり７５個の画素を有する（７５ＤＰＩ）。
【００３３】
ステップ１３０において、２４ビットのＲＧＢカラー画像は、モニタ１２４上に表示することができるようコンピュータ１２２のメモリに保持される。
【００３４】
ステップ１３２において、メモリにおける画像は、プリンタの解像度における２４ビットＲＧＢ画像に変換される。典型的なインクジェット・プリンタは、インチあたり３００、６００、または１２００ドット数の解像度を有する。プリンタは典型的にはＣＭＹまたはＣＭＹＫの減色法で印刷するけれども、ステップ１３２の画像処理のため、プリンタをＲＧＢ装置と考えるのが都合良い。これは、カラー・モニタのＲＧＢ値をＣＭＹに直接変換する後の処理により、通常、測色的な組合せ（colorimetric match）が生成されるからである。しかしながら、マッチするすべての値が同じ画像品質を生成するわけではない。ある選択は他よりも視覚的ノイズを多く含み、他の選択は、画像のハーフトーンの遷移に不所望な不連続性をもたらすことがある。
【００３５】
ステップ１３４において、プリンタのＲＧＢカラー画像は、参照テーブルまたは他の従来の変換手段を使用してＣＭＹ色空間に変換される。当然ながら、ＲＧＢカラー画像を、同じ方法でＣＭＹＫ色空間に変換することができる。
【００３６】
ステップ１３６において、ＣＭＹ画像はハーフトーン化され、プリンタのＤＰＩ解像度で、８ビット／色の３プレーン(3-plane、ここではＣＭＹ)から２値カラー（オンまたはオフのドット）の３プレーンに変換される。言い換えると、それぞれの画素位置における色および階調（０〜２５５）は、印刷されるべきＣ、ＭまたはＹドットのオンまたはオフ（０または２５５の輝度）のパターンに変換される。このハーフトーン化された画像（画像全体の一部分でもよい）は、メモリに記憶される。ステップ１３６については、後でさらに詳細に説明する。
【００３７】
ステップ１３８において、ハーフトーン画像は、一般に、ヒューレット・パッカード・カンパニーのプリンタ制御言語（Printer Control Language：ＰＣＬ）で特定されるものと同様のエスケープ・シーケンスを使用するような効率のよい通信技術を使用して、プリンタに送られる。ステップ１３６において生成された画像は、ページ上のそれぞれの画素位置に印刷されるべき各色のドット数およびそれらのドット位置に関する情報のすべてを含む。プリンタ・コントローラ１２９（図５）は、そのドットをいつ印刷すべきかを決定する。
【００３８】
プリンタによっては、図６に関して説明する機能を、（処理機能を実行するようにプログラムされた）ホスト・コンピュータまたはプリンタによって実行することができるということを理解されたい。たとえば、「スマート（smart）」プリンタでは、ステップ１３２〜１３８のすべてをプリンタで実行することができる。一方、プリンタのコストを節約するために、機能１３２〜１３８のすべてまたは一部をホスト・コンピュータで実行することもできる。
【００３９】
階調依存型誤差拡散
次に、残りの図を参照して、ハーフトーン化ステップ１３６を詳細に説明する。したがって、図６のステップ１３４が完了し、現在ハーフトーン化のステップを実行しなければならないと想定する。
【００４０】
効率的なハーフトーン化方法が望ましいので、この発明に従う誤差拡散ハーフトーン化を使用する。しかしながら、誤差拡散ハーフトーン化方法は、ハーフトーン化に対する反復的な手法、すなわち直接２分探索法と同様の優れた品質を持つ画像を生成することが望ましい。したがって、直接２分探索によって生成されたテクスチャを模倣することに基づいて最適化された階調依存型のしきい値および誤差重み付けによる階調依存型誤差拡散ハーフトーン化を使用する。
【００４１】
図７は、この発明の実施形態に従う直接２分探索法と同様の品質を有するハーフトーン画像を生成する階調依存型誤差拡散ハーフトーン化システム１５０である。連続階調値を有する入力画素値はｆ[ｍ，ｎ]として表され、ここで、ｍおよびｎは画素位置である。階調依存型誤差拡散システムは、それぞれ入力画素値ｆ［ｍ，ｎ］の関数であるｗ［ｋ，ｌ；ｆ［ｍ，ｎ］］およびｔ［ｍ，ｎ；ｆ［ｍ，ｎ］］によって示される誤差重み付けマトリクス１５６およびしきい値マトリクス１５２を使用する。
【００４２】
図７に示したように、修正画素値はｕ［ｍ，ｎ］で表され、出力ハーフトーン値は、次の式（７）のようなしきい値演算によって求められるｇ［ｍ，ｎ］によって表される。
【００４３】
【数７】
0004268313.tif 000007
ここで、ｔ［ｍ，ｎ；ｆ［ｍ，ｎ］］は、階調依存の、すなわち入力画素値ｆ［ｍ，ｎ］に依存するしきい値マトリクス１５２である。
【００４４】
量子化誤差ｄ［ｍ，ｎ］は、次の式（８）のように、加算器１５４において、出力ハーフトーン値ｇ［ｍ，ｎ］から修正画素値ｕ［ｍ，ｎ］を減算することによって求められる。
【００４５】
【数８】
ｄ[ｍ,ｎ]＝ｇ[ｍ,ｎ]−ｕ[ｍ,ｎ]         式（８）
その後、量子化誤差ｄ［ｍ，ｎ］は、近傍の次に処理される画素位置に拡散される。
【００４６】
入力画素値ｆ［ｍ，ｎ］は、次の式（９）のように、加算器１５８を介して修正入力値ｕ［ｍ，ｎ］に更新される。
【００４７】
【数９】
0004268313.tif 000008
ここで、ｗ［ｋ，ｌ；ｆ[ｍ，ｎ]］は、階調依存の、すなわち入力画素値ｆ[ｍ，ｎ]に依存する誤差重み付けマトリクス１５６である。
【００４８】
この発明によるこの階調依存型誤差拡散システム１５０で使用されるしきい値マトリクスは、吸収率０．５すなわち中間調を有する２値の直接２分探索パターンに基づく。したがって、式（１０）のように表される。
【００４９】
【数１０】
0004268313.tif 000009
ここで、ｔ[ｍ，ｎ；ａ]はしきい値マトリクスであり、ｔu（ａ）およびｔl（ａ）は、ｔu（ａ）≧（ａ）ｔlを満たす階調依存型パラメータであり、“ａ”は、処理されている階調値であり、ｐ［ｍ，ｎ；０．５］は、吸収率０．５の一定のパッチ（patch）を表す、直接２分探索のハーフトーン化方法によって生成されたハーフトーン・パターンである。
【００５０】
図８は、吸収率０．５を有する、直接２分探索によって生成されたハーフトーン・ビットマップ・パターン１６０の例を示し、これを、ｐ［ｍ，ｎ；０．５］として使用することができる。図８のビットマップ・パターン１６０は、周期Ｍのｍおよびｎにおいて倍周期である。すなわち、以下の式（１１）が成立する。
【００５１】
【数１１】
ｐ[ｍ+ｋＭ,ｎ+ｌＭ;0.5]＝ｐ[ｍ,ｎ;0.5]              式（１１）
ここで、ｋおよびｌは整数であり、Ｍはハーフトーン・パターンのサイズである。したがって、理想的なしきい値マトリクスｔ［ｍ，ｎ；ａ］は、周期Ｍの周期関数でもある。このように、図８のビットマップ１６０を、画像上にタイル状に並べることができる。
【００５２】
式（１０）を式（７）に代入することによって、この階調依存型誤差拡散ハーフトーン化のマトリクス１５２は、次のように表される。
【００５３】
【数１２】
0004268313.tif 000010
【００５４】
こうして、式（１２）に示したように、パラメータｔuおよびｔlは、それぞれしきい値マトリクス１５２における上および下のしきい値として作用する。修正画素値ｕ［ｍ，ｎ］が上のしきい値ｔuよりも大きいか等しい場合、出力画素値ｇ［ｍ，ｎ］は１に設定される。修正画素値ｕ［ｍ，ｎ］が下のしきい値ｔ１よりも小さい場合、出力画素値ｇ［ｍ，ｎ］は０に設定される。それ以外の場合、図８に示した直接２分探索ビットマップ・パターン１６０における同じ場所、すなわちｍおよびｎにおける画素値を出力画素値ｇ［ｍ，ｎ］として使用することにより、しきい値を変調する。ビットマップ１６０を、処理する画像と同じかまたはそれよりも大きくなるようにタイル状に並べることができる。
【００５５】
上および下のしきい値ｔuおよびｔlが等しい場合は、ビットマップ・パターン１６０を使用したしきい値変調を取り除くことができる。他の実施形態では、式（１２）のしきい値変調が、たとえば直接２分探索スクリーンを使用するスクリーニング処理で置き換えられる。この場合、画素の階調値は、スクリーンすなわちしきい値マトリクスと比較される。画素が、対応するマトリクスしきい値よりも大きい階調値を持つ場合、その画素は１に２値化され、そうでない場合は０に２値化される。
【００５６】
階調依存型誤差拡散システム１５０は、蛇行走査(serpentine scan)を使用する。当然ながら、必要に応じて、後で説明するようなラスタまたは２行蛇行走査(2-row serpentine scan)などの他の種類の走査を使用することもできる。蛇行走査では、行を１つおきに左から右に処理し、図９に示した階調依存型誤差重み付けにしたがって誤差が拡散される。図９は、誤差の配分を示すブロック２０（図２）であり、処理している現在の画素１６２を「Ｐ」で示す。間の行は、図９の鏡像を使用して右から左に処理される。
【００５７】
上および下のしきい値ｔuおよびｔlのそれぞれ、および誤差重み付けは、それぞれの階調レベルについて最適化されなければならない。しきい値および誤差重みの最適化は、ハーフトーン画像の品質を測定する費用関数によって達成される。
【００５８】
誤差拡散のハーフトーン化方法は、直接２分探索のハーフトーン化方法と同様の品質を有する画像を生成することが望ましいので、直接２分探索ハーフトーン化と、直接２分探索により生成されたハーフトーン画像および連続階調画像の間の知覚誤差とについて簡単に調べることは有用なことである。
【００５９】
直接２分探索は、人間視覚系モデルを使用してハーフトーン画像および連続階調画像の間の知覚誤差を最小にする反復的ハーフトーン化方法である。
【００６０】
人間視覚系モデルは、線形シフト不変低域通過フィルタ(linear shift-invariant low pass filter)である。このフィルタの周波数応答は、次の式（１３）で与えられる。
【００６１】
【数１３】
0004268313.tif 000011
【００６２】
ここで、ｕおよびｖはサイクル／ラジアンで表した空間周波数変数、Ｌは１０ｃｄ／ｍ2の値を有する平均輝度であり、ｃ＝０．５２５およびｄ＝３．９１である。点広がり関数(point spread function)ｈ（ｘ,ｙ）は、Ｈ（ｕ,ｖ）の逆フーリエ変換を行うことによって得られる。距離Ｄから見たときの長さｘが、ｔａｎ-1（ｘ／Ｄ）≒ｘ／Ｄ（ｘ＜＜Ｄの場合）の角に対する（subtend）ので、印刷媒体上で測定される単位で、人間視覚系フィルタを以下の式のように計算することができる。ここで、Ｄは、１１インチ（約２８ｃｍ）に設定される。
【００６３】
【数１４】
0004268313.tif 000012
ｅ［ｍ，ｎ］は、誤差画像、すなわち連続階調画像およびハーフトーン画像の間の差を表し、ｅ［ｍ，ｎ］は次の式（１４）によって得られる。
【００６４】
【数１５】
ｅ[ｍ,ｎ]＝ｆ[ｍ,ｎ]−ｇ[ｍ,ｎ]                    式（１４）
ハーフトーン画像および連続階調画像の間の知覚誤差は、次の式（１５）で表される。
【００６５】
【数１６】
0004268313.tif 000013
ここで、Ｘは、出力装置のアドレス可能な点の格子、すなわちプリンタが実際にインクのドットを配置することができる位置に対応する。
【００６６】
直接２分探索により費用関数として使用される誤差計量(error metric)は、次の式（１６）で与えられる、知覚される合計の二乗誤差である。
【００６７】
【数１７】
0004268313.tif 000014
ここで、ｘ＝１／３００である。式（１６）を式（１５）に代入することにより、誤差計量Ｅすなわち費用関数を、次のように計算することができる。
【００６８】
【数１８】
0004268313.tif 000015
【００６９】
直接２分探索は、反復的トグル／スワップ方式(iterative toggling/swapping scheme)を使用して誤差計量Ｅを最小にする。この方法は、たとえば誤差拡散システム１０または従来のスクリーニングによって得ることができる初期ハーフトーン画像から開始する。ハーフトーン画像のそれぞれの画素について、画素を切り換える（トグル）またはその画素値をその８個の最近傍のうちの１つと交換する（スワップ）影響が測定される。何らかの変更によって誤差が減少する場合、誤差を最も大きく減少させる変更が受け入れられる。この処理は、いかなる変更も受け入れられなくなるまで、ハーフトーン画像について反復的に繰り返される。
【００７０】
この階調依存型誤差拡散システム１５０について最適な誤差重みおよびしきい値を探索するためには、ハーフトーン画像の品質を測定する視覚的な費用関数が必要である。直接２分探索によって使用される費用関数、すなわち式（１７）は、１つの可能な選択である。当然ながら、必要に応じて、式（１６）を費用関数として使用することができるということを理解されたい。
【００７１】
しかしながら、直接２分探索方法で使用される知覚誤差は、一般に、２値のテクスチャの滑らかさを示すことができるが、画像のテクスチャの多様性および均質性を測定することはできない。誤差拡散システムの全体の知覚誤差を最小にすると、特に中間調にかなり不均質なテクスチャの部分ができる。
【００７２】
図１０の（Ａ）および（Ｂ）は、それぞれ、従来の誤差拡散で生成した２値パターン１７２と、直接２分探索で生成した２値パターン１７４である。両方のパターン１７２および１７４は、吸収率８７／２５５の連続パッチを表す。式（１７）による知覚される合計の二乗誤差は、誤差拡散パターン１７２では０．００８４であり、直接２分探索パターン１７４では０．０１０３である。図１０の（Ａ）から明らかなように、誤差拡散パターン１７２は滑らかに見え直接２分探索パターン１７４よりも誤差は小さいが、誤差拡散パターン１７２は、望ましくない構造化パターンを含む。このように、式（１７）による二乗誤差を最小にしても、必ずしも均質なテクスチャは生成されない。
【００７３】
図１１の（Ａ）および（Ｂ）は、それぞれ、誤差拡散パターン１７２および直接２分探索パターン１７４の２次元高速フーリエ変換（ＦＦＴ）の大きさ（magnitude）を表す。図１１の（Ｂ）は、直接２分探索パターン１７４が、あらゆる方向に均一に分散されるテクスチャの多様性を有することを示す。一方、図１１の（Ａ）は、誤差拡散パターン１７２のエネルギー・スペクトルが、対角線方向のいくつかの固有周波数に集中されることを示す。このように、ＦＦＴ解析による「大きさ」をテクスチャの標示として使用することができる。
【００７４】
この階調依存型誤差拡散方法によって生成される画像の品質が直接２分探索方法によって生成される画像の品質に近づくことが望ましいので、この階調依存型誤差拡散は、中間調のハーフトーン・パターンの目標スペクトルとして、直接２分探索パターンのＦＦＴの大きさを使用する。
【００７５】
ＧDBS（ｕ，ｖ）およびＧTDED（ｕ，ｖ）は、それぞれ、直接２分探索パターンおよび階調依存型誤差拡散パターンのＦＦＴの大きさの期待値を表す。ＧDHS（ｕ，ｖ）およびＧTDED（ｕ，ｖ）の間の合計の二乗誤差は、次の式（１８）で与えられる。
【００７６】
【数１９】
0004268313.tif 000016
式（１８）の誤差計量は、中間調に関しては式（１７）の誤差計量よりも優れた視覚的費用関数であるが、ハイライトおよびシャドウの階調レベルが極端なとき、すなわちドットまたはホール(hole)がまばらなときには、式（１７）の誤差計量を視覚的費用関数として使用することができる、ということを発明者らは経験的に判断した。
【００７７】
上および下のしきい値ｔuおよびｔlのそれぞれの最適階調依存値と、前述の式（１６）および式（１８）の費用関数を最小にする誤差重み付けの探索において、関数は次のような制約を受ける。
【００７８】
【数２０】
0004268313.tif 000017
【００７９】
上記の制約１９により、しきい値マトリクス１５２は、０．５の固定平均値を有するよう使用される。制約１９は、上および下のしきい値の和が１であることを述べているが、上および下のしきい値は、最も高い階調レベルの値まで変倍されるべきであり、したがって、階調レベルが０〜２５５の範囲を有する場合には、上および下のしきい値の和が２５５になるということを理解されたい。この特定の構成について、制約１９および２１からｔｌ（ａ）およびｗ［１，−１；ａ］を得ることができるので、費用関数を、（ｔｕ（ａ），ｗ［０，１；ａ］，ｗ［１，１；ａ］，ｗ［１，０；ａ］）の関数として扱うことができる。したがって、４次元の最小化が必要とされる。当然ながら、必要に応じて、制約１９から下のしきい値ｔ1（ａ）を見つけることができ、上のしきい値ｔu（ａ）を得ることができる。制約２１を使用して他の誤差重み付けを求める場合にも同じことが当てはまる。
【００８０】
図１２は、この発明の実施形態に従う中間調の最適化されたしきい値および誤差重み付けを得る階調依存型誤差拡散訓練システム２００を示す。図１２に示されるように、所与の階調レベルの連続階調パッチ２０２が提供され、直接２分探索フィルタ２０４は、そのパッチのハーフトーン画像を生成し、誤差拡散フィルタ２０６は、そのパッチの他のハーフトーン画像を生成する。
【００８１】
１つの実施形態では、直接２分探索フィルタ２０４および誤差拡散フィルタ２０６において、複数のハーフトーン・パターンが生成される。たとえば、ＤＢＳパターンについて様々なランダムの初期パターンを使用して、連続階調パッチ２０２の階調レベルを表す５０個の１２８×１２８ハーフトーン・パターンが生成される。それぞれの直接２分探索パターンの「大きさ（magnitude）」が高速フーリエ変換ＦＦＴブロック２０８によって計算され、ＧDBS（ｕ，ｖ）の値が、その大きさの平均をとることによって推定される。
【００８２】
同様に、誤差拡散フィルタ２０６によって、いくつかの誤差拡散パターンが生成される。たとえば、ランダムな様々な起動条件で、５０個の１２８×１２８ハーフトーン・パターンが使用される。起動アーティファクトを防ぐために、それぞれの１２８×１２８ハーフトーン・パターンを、十分に大きい２値画像の中心部分から切り取るのがよい。それぞれの画像の「大きさ」は、ＦＦＴブロック２１０を介して得られる。その後、これらの５０個の画像の大きさの平均をとることによって、ＧTDED（ｕ，ｖ）の値が推定される。ＧDBS（ｕ，ｖ）およびＧTDED（ｕ，ｖ）の値が生成された後、ブロック２１２において、式（１８）を使用して費用関数εが得られる。ブロック２１２から誤差拡散フィルタ２０６までの破線２１３は、費用関数を小さくするために誤差拡散フィルタ２０６で使用されるしきい値および重みを調整するプロセスを示す。
【００８３】
図１３は、この発明の実施形態に従う、ハイライト領域およびシャドウ領域において最適化されたしきい値および誤差重み付けを得る階調依存型誤差拡散訓練システム２２０を示す。図１３は、図１２と同様に、所与の階調レベルについて連続階調パッチ２２２が提供されることを示す。システム２２０では、５１２×５１２の２値パターンが使用される。人間視覚系（ＨＶＳ）モデルのフィルタ２２４が、連続階調パッチに適用される。誤差拡散フィルタ２２６は、ハーフトーン画像２２８を生成するのに適用される。その後、人間視覚系モデルのフィルタ２３０をハーフトーン画像に適用する。次に、ブロック２３２によって、式（１７）を使用して費用関数が生成される。ブロック２３２から誤差拡散フィルタ２２６までの破線２３３は、費用関数を小さくするために誤差拡散フィルタ２２６に使用されるしきい値および重みを調整するプロセスを示す。
【００８４】
図１４および図１５は、中間調については図１２、ハイライト領域およびシャドウ領域については図１３の両方を使用して、最適化されたしきい値および誤差重み付けを得るのに使用されるダウンヒル探索法（downhill search method）を示すフローチャートである。階調依存型誤差拡散フィルタは、中間調レベルから１レベルずつ設計される。こうして、たとえば２５６レベルの階調依存型誤差拡散フィルタについては、それぞれの画素に対する階調値が０（白）および２５５（黒）の間の階調レベルの指標で表される場合、中間調レベルの始まりは１２７である。当然ながら、必要に応じて、たとえば階調レベルを２５５に分けることによって、階調レベルの指標を０（白）および１（黒）の間で変倍させるようにすることもできる。そのレベルに最適なしきい値および誤差重みを得た後、プロセスは次に進み、それぞれの独立したより明るい階調レベル（またはより暗い階調レベル）についてフィルタを設計する。
【００８５】
図１４および図１５のフローチャートで示されるように、ステップ２５０において探索が開始し、ステップ２５２において、初期値ａが、中間調の値たとえば吸収率＝１２７にセットされる。ステップ２５４において、上のしきい値ｔu(0)（ａ）および誤差重み付けｗ(0)［０，１；ａ］、ｗ(0)［１，１；ａ］、ｗ(0)［１，０；ａ］に、最後に設計された階調レベルで得られた最適値を設定する。最初に設計される階調レベルたとえば中間調１２７の初期フィルタは、従来の誤差拡散システム１０を使用して選択される。ステップ２５４において、誤差重み付けｗ［ｋ，ｌ；ａ］のステップサイズｈwは１／１６に等しいよう設定され、しきい値ｔu（ａ）のステップサイズｈtは１に設定され、ｉの値は０に設定される。
【００８６】
ステップ２５６において、上のしきい値ｔu（ａ）、および誤差重み付けｗ［０，１；ａ］、ｗ［１，１；ａ］、ｗ［１，０；ａ］のすべての可能な値（ステップ２５４で定義されたステップサイズにより）が、中間調たとえば階調レベル２１〜２３５には式（１８）の費用関数を使用する図１２に示したシステム２００を使用し、ハイライト領域およびシャドウ領域たとえば階調レベル０〜２０および２３６〜２５５には式（１７）を使用する図１３に示したシステム２２０を使用して、それぞれ評価される。費用関数は、条件１９〜２２に従って評価され、さらに｜ｔu（ａ）−ｔu(i)（ａ）｜＝０またはｈt、および｜ｗ［ｋ，ｌ；ａ］−ｗ(i)［ｋ，ｌ；ａ］｜＝０またはｈwに従って評価される。こうして、それぞれのパラメータは２つの値が可能であり、たとえば｜ｔu（ａ）−ｔu(i)（ａ）｜は０またはｈｔに設定され、｜ｗ［ｋ，ｌ；ａ］−ｗ(i)［ｋ，ｌ；ａ］｜は０またはｈwに設定される。それぞれ２つの可能な値を持つ４つのパラメータがあるので、１６の順列がある。最小の費用関数となる順列に使用される値が、ｔｕ(i+1)（ａ）、ｗ(i+1)［０，１；ａ］、ｗ(i+1)［１，１；ａ］、ｗ(i+l)［１，０；ａ］として定義される。
【００８７】
ステップ２５８では、最後の繰り返しにおいて上のしきい値ｔu(i＋１)（ａ）または誤差重み付けｗ(i+1)［ｋ，ｌ；ａ］に何らかの変化があったかどうかを確認する検査が実行される。これらの値に何らかの変化があった場合、すなわち（ｔu(i)（ａ），ｗ(i)［０，１；ａ］，ｗ(i)［１，１；ａ］，ｗ(i)［１，０；ａ］）が、（ｔu(i+1)（ａ），ｗ(i+1)［０，１；ａ］，ｗ(i+1)［１，１：ａ］，ｗ(i+1)［１，０；ａ］）と等しくない場合は、ステップ２６０においてｉの値がｉ＋１として再定義され、プロセスはステップ２５６に戻る。変化がなかった場合は、プロセスはステップ２６２に進み、ここでｉはｉ＋１で再定義され、ｈwはｈw／２として再定義される。
【００８８】
図１５のステップ２６４において、上のしきい値ｔu（ａ）、および誤差重み付けｗ［０，１；ａ］、ｗ［１，１；ａ］、ｗ［１，０；ａ］のすべての可能な値（ｈt＝１であり、ｈwはステップ２６２において定義される）が、再びステップ２５６と同じように評価される。
【００８９】
ステップ２６６において、ｈwの値が、所望の最小ステップ・サイズである１／２５６に等しいかどうか判定する検査が行われる。ｈwの値が１／２５６よりも大きければ、プロセスの流れはステップ２６２に戻る。ｈwの値が１／２５６に等しければ、プロセスの流れはステップ２６８に進み、（ｔu(i+1)（ａ），ｗ(i+1)［０，１；ａ］，ｗ(i+1)［１，１；ａ］，ｗ(i+1)［１，０；ａ］）の最後の値に等しい（ｔu（ａ），ｗ［０，１；ａ］，ｗ［１，１；ａ］，ｗ［１，０；ａ］）の最終値を出力する。
【００９０】
ステップ２７０において、階調値ａがａ−１として再定義される。ステップ２７２において、階調値が０に等しいかどうかを判定する検査が行われる。階調値が０でなければ、プロセスの流れはステップ２５４に戻る。階調値が０に等しければ、プロセスの流れはステップ２７４で終わる。
【００９１】
対称性に起因して、最も明るい階調レベルすなわち階調レベル０が終了した後、中間調レベルたとえば階調レベル１２７よりも暗い階調レベルの最適なしきい値および誤差重み付けを、ｔu（ａ）＝ｔu（２５５−ａ）およびｗ［ｋ，ｌ；ａ］＝ｗ［ｋ，ｌ；２５５−ａ］とすることによって得ることができる。
【００９２】
図１６、図１７の（Ａ）〜（Ｄ）は、それぞれ、最適化されたしきい値および誤差重み付けｗ［０，１；ａ］、ｗ［１，−１；ａ］、ｗ［１，０；ａ］、ｗ［１，１；ａ］の結果を示し、ここで、吸収率、しきい値および重みは０〜１の間で変化する。しきい値および誤差重み付けが最適化されると、これらをしきい値マトリクス１５２のルックアップテーブルに保持することができる。ルックアップテーブルを、ハードウェアまたはソフトウェアで実現することができる。こうして、階調依存型誤差拡散システム１５０は、高品質のハーフトーン画像を生成しながら画像を効率よく処理することができる。
【００９３】
図１８は、従来の誤差拡散システム１０を使用して生成されたハーフトーン画像を示す。図１９は、図１６および図１７の（Ａ）〜（Ｄ）に示したしきい値および誤差重み付けを使用する階調依存型誤差拡散システム１５０を使用して生成されたハーフトーン画像を示す。
【００９４】
エッジ強調および起動アーティファクト
図１８および図１９から明らかなように、「空」の領域のようなハイライト領域およびシャドウ領域と、中間調領域の品質が、階調依存型誤差拡散システム１５０によって大幅に改善された。しかしながら、図１９から明らかなように、画像の最上部における起動遅延のように、目に見えるアーティファクトが少し残っている。さらに、図１８および図１９の両方の画像は、誤差拡散に固有のエッジ強調特性に起因して鮮明になっている。エッジ強調は、たとえば図１８および図１９の建築構造物および画像の中心にある彫刻上に刻まれたパターンに見ることができる。こうして、エッジ強調および起動時欠陥のようなアーティファクトを減少させるよう階調型依存誤差拡散システム１５０を修正することが望ましい。
【００９５】
この発明の１つの実施形態によれば、階調依存型しきい値マトリクス１５２は、式（５）で定義したような修正項ｃ［ｍ，ｎ］の確率特性を使用して修正される。
【００９６】
例として従来の誤差拡散システム１０を使用すると、しきい値マトリクス１２への入力は、前述の式（５）によって与えられる修正画素ｕ［ｍ，ｎ］である。出力Ｅ（ｇ［ｍ，ｎ］）の期待値は、次の通りである。
【００９７】
【数２１】
0004268313.tif 000018
修正項ｃ［ｍ，ｎ］を、過去の誤差に基づいて計算された確率変数として扱うことができる。ｃ［ｍ，ｎ；ａ］は、吸収率ａを有する一定の入力画像についての確率変数を示す。したがって、この画像の期待値出力は、次の通りである。
【００９８】
【数２２】
Ｅ(ｇ[ｍ,ｎ])＝Ｐ(ｃ[ｍ,ｎ;ａ]≦ａ−ｔ[ｍ,ｎ;ａ])   式（２４）
ここで、ｔ［ｍ，ｎ；ａ］は、図７の階調依存型誤差拡散システム１５０で使用されるしきい値マトリクス１５２である。ある位置（ｍ，ｎ）においてこの一定の入力画像に変化があり、新しい画素値がｂであると仮定する。この位置において、修正項ｃ［ｍ，ｎ；ａ］は過去の誤差を使用して計算され、使用されるべきしきい値マトリクスは、現在の画素値ｂに基づく。式（２３）により、出力画素値ｇ［ｍ，ｎ］の期待値は、次の式（２５）によって与えられる。
【００９９】
【数２３】
Ｅ(ｇ[ｍ,ｎ])＝Ｐ(ｃ[ｍ,ｎ;ａ]≦ｂ−ｔ[ｍ,ｎ;ｂ])   式（２５）
いかなる鮮鋭化も「ぼけ」もないことを期待する場合（ここで、「鮮鋭化もぼけもない」という言葉は、「出力値の期待値が、近傍の入力値に依存しない」ということを意味する）、上記の式（２５）の期待値は、画像が一定の画素値ｂを有するときと同じであるべきである。
【０１００】
【数２４】
0004268313.tif 000019
式（２６）は、ｃ［ｍ，ｎ；ａ］およびｃ［ｍ，ｎ；ｂ］が、画素位置（ｍ，ｎ）において同じ確率分布を有する場合に真となる。一般に、近傍の入力値が変化したときに修正項の確率分布が変化しなければ、鮮鋭化もぼけも生じない。
【０１０１】
図２０の（Ａ）〜（Ｃ）は、ｃ［ｍ，ｎ；ａ］の確率密度関数（pdf）が、異なる入力画素値、すなわち入力値７／２５５、６３／２５５および１２７／２５５でそれぞれ異なることを示す。
【０１０２】
ｃ［ｍ，ｎ；ａ］の確率密度の入力画素値ａへの依存を小さくするために、しきい値マトリクスｔ［ｍ，ｎ；ａ］を修正して効果を調べる。任意の固定画素値ａでは、しきい値マトリクスを一定量ｔ0だけずらすと、ハーフトーンのテクスチャには影響がないがｃ［ｍ，ｎ；ａ］の確率密度が量ｔ0だけずれる、ということが分かっている。このように、すべてのａの値について、結果としてのハーフトーンのテクスチャに影響を及ぼさずにｃ［ｍ，ｎ；ａ］の確率分布をそろえることができる。これにより、ａへのこれらの分布の依存は小さくなるが、確率密度の形がなおａに依存するので、完全にはなくならない。
【０１０３】
したがって、エッジ強調の影響を小さくするしきい値マトリクスを次の式（２７）で与えて、修正項ｃ［ｍ，ｎ；ａ］が、どの入力値ａにも同じ平均値０を有するようにする。
【０１０４】
【数２５】
ｔ[ｍ,ｎ;ａ] ←ｔ[ｍ,ｎ;ａ]＋Ｅ(ｃ[ｍ,ｎ;ａ])             式（２７）
図２１は、修正項ｃ［ｍ，ｎ；ａ］の平均値を示し、ここで吸収率は０〜１の間にある。
【０１０５】
この発明による階調依存型誤差拡散法では、高いしきい値ｔu（ａ）および低いしきい値ｔl（ａ）は、次のように修正される。
【０１０６】
【数２６】
ｔu(ａ)←ｔu(ａ)＋Ｅ(ｃ[ｍ,ｎ;ａ])
ｔl(ａ)←ｔl(ａ)＋Ｅ(ｃ[ｍ,ｎ;ａ])                  式（２８）
図２２は、図２１の修正項Ｅ（ｃ［ｍ，ｎ；ａ］）によって修正された、図１６の上および下の階調依存型しきい値ｔu（ａ）およびｔl（ａ）を示す。
【０１０７】
図２２に示した修正された上および下の階調依存型しきい値ｔu（ａ）およびｔl（ａ）を使用して図２３に示されるハーフトーン画像がこの発明の実施形態に従って生成された点を除いて、図２３は、図１８および図１９に示したものと同様である。図２３から明らかなように、エッジ強調および起動アーティファクトは、修正された上および下の階調依存型しきい値ｔu（ａ）およびｔl（ａ）を使用することにより減少した。
【０１０８】
目障りな起動アーティファクト・パターンのうちの１つタイプは、図１９に示される画像の最上部にみられる構造化パターンであり、これは、前の線から拡散される誤差が無いために生じる。この種のアーティファクトを減少させるために、以下の式（２９）で表される修正項が、画像の最初の走査線のそれぞれの入力画素値ｆ［ｍ，ｎ］に加算される。
【０１０９】
【数２７】
0004268313.tif 000020
【０１１０】
この修正項を得るために、最初に、すべての階調レベルについてｃ［ｍ，ｎ；ａ］の確率密度関数の分散の平均（average）が生成される（これは、０．０２３１に等しい）。その後、式（２９）で表される修正項は、平均値(mean value)０および分散０．０２３１を有する区間［−０．２６３５，０．２６３５］で均一な分布を持つ確率変数であるよう定義される。この確率変数（式（２９）で表される）を、乱数発生器を使用することによって、またはルックアップテーブルに記憶された事前に計算された乱数(random number)を使用することによって生成することができる。この明細書で使用する「ランダム(random)」という言葉は、当該技術分野においてよく理解されているように、疑似ランダムを含むということを理解されたい。そのような確率変数を使用することによって、図２３に示したようなハーフトーン画像の最上部における品質が改善される。
【０１１１】
起動アーティファクトの他の種類は、図１９の「Ｐｕｒｄｕｅ  Ｕｎｉｖｅｒｓｉｔｙ」のテキスト・ボックスのすぐ下に見ることができる。この領域が２値、すなわちテキスト・ボックスの境界が完全な黒で内側の背景が完全な白であるので、この領域は、一般に新しい量子化誤差を生成せず、過去の誤差を補償しない。誤差重み付けマトリクスの低域特性は、誤差を伝搬するときにその過去の量子化誤差を平均化する傾向がある。したがって、誤差は、テキスト・ボックスの最下部に沿ってほぼ一定になる。その結果、量子化処理を続けるとき、テキスト・ボックスの後に起動アーティファクトができる。
【０１１２】
図１９に示したような、画像内のテキスト・ボックスの後に生じる起動アーティファクトを、黒階調および白階調すなわち０または１（２５５）の階調の特殊ケースのフィルタを使用することによって減少させることができる。この特殊ケースのフィルタの誤差重み付けマトリクスは、図２４に示したように、処理する画素の真下に拡散させる１つのゼロでない重みｗ［１，０；ａ］を使用する。図２４は、垂直方向の誤差の分布３００を示す図であり、ここで、現在処理している画素３０２は「Ｐ」で示される。このように、誤差がすべての黒（またはすべての白）の領域に平均化されないよう、量子化誤差は垂直方向に伝搬される。図２３は、この種のフィルタを使用した結果を示す。
【０１１３】
図１９から明らかなように、テキスト・ボックスによって生成されることのある他のアーティファクトは、テキスト・ボックスの最上部近くの白い領域に現れる黒いドットである。これらのドットは、それらの位置における修正画素値がしきい値を超えるために現れる。この種のアーティファクトを取り除くため、修正項ｃ［ｍ，ｎ］の範囲を見つける必要がある。
【０１１４】
図１に示した従来の誤差拡散システム１０の場合、修正項ｃ［ｍ，ｎ］は、次のように範囲が決められる。
【０１１５】
【数２８】
0004268313.tif 000021
【０１１６】
しかしながら、一般に、画像が一定の階調ａを持たないとき（画像が一定の階調ｆ［ｍ，ｎ］≡aを有するならば、制約２１に従って重みの合計は１になる）は、次の式（３１）の関係が成り立つので、式（３０）は、可変の誤差重みを有する階調依存型誤差拡散システムには当てはまらない。
【０１１７】
【数２９】
0004268313.tif 000022
【０１１８】
このように、図７に示した階調依存型誤差拡散システム１５０では、式（３０）をおよその推定としてしか利用することができない。式（３０）を使用すると、図２２から、階調依存型しきい値についてｃ［ｍ，ｎ］の推定範囲は、次の式（３２）で与えられることがわかる。
【０１１９】
【数３０】
−０．８７≦ｃ[ｍ,ｎ]≦０．８７                    式（３２）
式（３２）によると、しきい値は次の式（３３）および式（３４）のように設定される。
【０１２０】
【数３１】
ｔu(０)＝ｔ1(０)＝１                              式（３３）
ｔu(１)＝ｔ1(１)＝０                              式（３４）
これは、ｃ［ｍ，ｎ；ａ］の推定範囲に、ある程度の誤差を許容する。その結果、２値領域の出力画素値は入力に等しくなる。こうして、図２３に示したように、白領域における黒いドットが取り除かれる。しかしながら、２値領域の特性に起因して、式（３３）および式（３４）に示した上記のしきい値は、ｃ［ｍ，ｎ；ａ］の範囲には影響を及ぼさない。
【０１２１】
図２５は、この発明による階調依存型誤差拡散システム１５０を使用して生成された階調ハーフトーン画像３１０である。図３の画像３０に比べて、テクスチャ品質が、すべての濃度で大きく改善されている。さらに、画素値の変化と共にテクスチャ・パターンが一貫して変化し、そのため輪郭のアーティファクトが本質的に目立たない。
【０１２２】
図２６は、直接２分探索のハーフトーン化方法を使用して生成された階調ハーフトーン画像３２０である。図２５の画像３１０を図２６の画像３２０と比べると明らかなように、階調依存型誤差拡散システム１５０によって生成された画像３１０は、直接２分探索によって生成された画像３２０に匹敵するハイライト領域およびシャドウ領域のドット分布を有する。
【０１２３】
並列処理
蛇行（serpentine）走査はアーティファクトを減少させる有効な方法であるが、次の走査線の処理を始める前に走査線全体を終了させなければならないので、逐次処理でしか実現することができない。結果として、並列処理についての階調依存型誤差拡散の性能が、速度の点で制限される。したがって、従来のラスタ走査を使用する階調依存型誤差拡散方法を発展させる必要がある。
【０１２４】
従来のラスタ走査による誤差拡散は、ハイライトおよびシャドウの濃度について「虫」アーティファクトを生成する。図２７は、画素３３０のマトリクスを示す図であり、ここで画素Ａは、２値化される現在の画素である。この階調依存型誤差拡散のハーフトーン化方法には４項の誤差マトリクスが使用されるので、画素Ｂにおける量子化誤差は画素Ａには伝搬しない。実際に、画素Ａにおける出力画素値は、網掛けされて図示される画素で生成される誤差によってのみ影響を受ける。その結果、「虫」は、しばしば点線３３２で示されるような角度で形成される。
【０１２５】
従来のラスタ走査を使用する誤差拡散法において「虫」を減少させる以前の手法は、誤差重みのランダム化および低周波変調されたしきい値マトリクスの使用を含み、これらはそれぞれ、R.Ulichneyによる「Digital Halftoning」（ＭＩＴ出版、1987年）と、R.L. MillerおよにC.M. Smithによる「Image Processor with Error Diffusion Modulated Threshold Matrix」と題する米国特許５，１５０，４２９号とに記載されており、ここで参照により取り入れる。これらの方法は「虫」を減少させることはできるが、ノイズを加えてしまう。「虫」を減少させる他の方法は、ハイライト領域およびシャドウ領域に、より大きい誤差重み付けマトリクスを使用することによるものであり、これは、R. Eschbachによる「Reduction of Artifacts in Error Diffusion by Means of Input-Dependent Weights」（Journal of Electronic Imaging、Vol.2(4)、ページ352〜358、1993年10月）と、P. Stuckiによる「MECCA-A Multiple-Error Correcting Computation Algorithm for Bilevel Image Hardcopy Reproduction」（IBM Research Report RZ 1060、IBM、1981年）とに記載されており、これらをここで参照により取り入れる。誤差重み付けマトリクスが大きいほど、量子化誤差がより広い領域に広がり、それにより「虫」が分散する。しかしながらこの方法は、誤差拡散領域のそれぞれの画素に関連する多数の誤差重み付けを使用するので、このことは、計算が複雑で余分の走査線バッファを必要とする。このように、「虫」は分散させるがノイズを取り込まず、さらに計算を複雑にしない誤差拡散方法が必要とされる。
【０１２６】
広いマトリクスを使用し、位置が可変の限定された誤差重み付けマトリクスすなわちゼロでない４つの項のマトリクスを持つ誤差拡散方法を使用して、計算を複雑にすることなくハイライトおよびシャドウ濃度における「虫」を減少させることができる。換言すると、誤差は、大きい領域にまばらに拡散される。こうして、大きい誤差重み付けマトリクスが使用されるけれども、マトリクス内のすべての画素が誤差拡散を受けるわけではない。誤差重み付けマトリクスが希薄（まばら）な場合、２値化される現在の画素は、より大きいハーフトーン領域によって影響を受ける。誤差重み付けの項の可変位置は、経験的に決定される。
【０１２７】
図２８は、この発明の実施形態に従って使用される希薄な誤差重み付けマトリクス３４０である。図２８に示したように、処理する画素すなわち画素３４２からの誤差は、大きい領域にわたって拡散される。誤差重み付けマトリクス３４０は、入力画素値ａが極端なハイライトまたはシャドウのどちらかの濃度であるときに、「虫」を分散させるのに使用される。制限ではなく例として、入力画素値ａが、１／２５５≦ａ≦２０／２５５および２３５／２５５≦ａ≦２５４／２５５の範囲内の値を持つとき（これを、条件３４とする）、誤差重み付けマトリクス３４０を使用することができる。このように、図２８に示したように、誤差重み付けｗ［ｋ，ｌ；ａ］を、処理する画素の隣接した所すなわちｗ［０，１；ａ］から、画素がいくつか離れた所すなわちｗ［１，−５；ａ］まで任意の場所に分散させることができる。当然ながら、必要に応じて、後の方の行を含む均一なより大きい領域に誤差を拡散することもできる。しかしながら、たとえばほんの４つの誤差重み付けしか使用しないので、希薄な誤差重み付けマトリクスの使用は計算的に複雑なものではない。
【０１２８】
図２９は、この発明の実施形態によって使用される他の希薄な誤差重み付けマトリクス３５０である。この場合も、処理する画素３５２からの誤差は、大きい領域にわたって拡散される。しかしながら、入力画素値ａが、極端な階調レベルおよび中間調の間の遷移レベルにあるときは、誤差重み付けマトリクス３５０が使用される。こうして、誤差重み付けマトリクス３５０の誤差が分散される領域は、誤差重み付けマトリクス３４０よりも小さい。例として、入力画素値ａが、２１／２５５≦ａ≦３３／２５５および２２２／２５５≦ａ≦２３４／２５５の範囲内にあるとき（これを、条件３５とする）、誤差重み付けマトリクス３５０を使用することができる。
【０１２９】
中間調の階調レベルの場合は、図９に示した４項の誤差重み付けが使用される。入力画素値ａは、３４／２５５≦ａ≦２２１／２５５の中間調レベルにある。
【０１３０】
蛇行走査の階調依存型誤差拡散システムと同様に、入力画素値がどちらかの極端、すなわち０または２５５のどちらかの場合（これを、条件３６とする）は、１項の誤差重み付けマトリクスが使用される。従来のラスタ走査の場合には、画像の最上部および左側に起動アーティファクトが生じる。こうして、誤差重み付けマトリクス３６０は、処理している画素すなわち画素３６２から、図３０に示したような対角線上の画素に誤差を拡散させる。ここで、ｗ［１，１；ａ］＝１である。
【０１３１】
上記の条件３４、３５および３６の特定の範囲は、例であって制限ではないということを理解されたい。このように、必要に応じて他の範囲を使用することができる。さらに、必要ならば、希薄な誤差重み付けマトリクス３５０の条件３５で示した遷移範囲を使用しないようにしてもよい。こうして、極端なハイライトおよびとシャドウレベル、および中間調レベルについて、異なる誤差重み付けマトリクスを使用することができる。
【０１３２】
図２８、図２９、図３０および図９の誤差重み付けマトリクスは、「虫」の分散について、より大きいマトリクスを使用するのと同様の効果を有する。誤差重みおよびしきい値の最適値は、以上説明した方法を使用して決定される。図３１および図３２の（Ａ）〜（Ｄ）に、従来のラスタ走査を使用する階調依存型誤差拡散システムの最適な誤差重みおよびしきい値をそれぞれ示す。図３２の（Ｅ）は、誤差重み付けが拡散される画素の位置を示す。図３２の（Ａ）は、処理する画素のすぐ右側にある画素に拡散される誤差重み付けを示す。図３２の（Ｂ）、（Ｃ）および（Ｄ）は、処理する画素の下にある行の左から右の画素に拡散される誤差重み付けを示す。図３２の（Ａ）〜（Ｄ）に示されるように、ハイライトおよびシャドウ領域（領域１）、遷移領域（領域２）および中間調（領域３）に分けられる吸収率の３つの領域がある。
【０１３３】
図３３は、図３１および図３２の（Ａ）〜（Ｄ）に示したしきい値および誤差重み付けによるラスタ走査の階調依存型誤差拡散法を使用して生成された階調ハーフトーン画像３７０である。図３３から明らかなように、「虫」および他の見苦しいアーティファクトが、従来の誤差拡散システム１０によって生成された画像３０（図３）に比べて大幅に減少した。しかしながら、画像３７０には、蛇行走査を使用する階調依存型誤差拡散システム１５０（図７）で生成された画像３１０内のものよりも目立つアーティファクトがいくつかある。
【０１３４】
ハーフトーン画像の品質をさらに高めるために、ハイライトおよびシャドウ領域に、さらに多数の項を有するマトリクスを使用することができるが、これは、より多くの計算を必要とする。他の手法は、従来のラスタ走査および蛇行走査を混合することである。たとえば、一方向における連続した２本の走査線に続いてその反対方向における２本の走査線によってこの処理を行うことができ、これを以降「２行蛇行（2-row serpentine）」と呼ぶ。２行蛇行走査の使用は、通常の蛇行走査に比べてより並列化しやすい。さらに、２行蛇行走査は、従来のラスタ走査の使用よりもアーティファクトを減少させる効果が高い。
【０１３５】
２行蛇行走査を使用する誤差拡散システムは、長い対角線の「虫」を生成しない。しかしながら、小さい誤差重み付けマトリクスを使用する場合には、短い「虫」が生成されることがある。したがって、図３４に示したように、処理画素３８２からの誤差を分散させるために、端の濃度については希薄な誤差重み付けマトリクス３８０が使用される。図３４は、入力画素値ａが、１／２５５≦ａ≦８／２５５および２４７／２５５≦ａ≦２５４／２５５の範囲内にあるときに使用される。
【０１３６】
入力画素値ａが、９／２５５≦ａ≦２１／２５５および２３４／２５５≦ａ≦２４６／２５５の遷移範囲内にあるとき、図２９の希薄な誤差重み付けマトリクス３５０を使用することができる。
【０１３７】
たとえば２２／２５５≦ａ≦２３３／２５５の中間調の範囲の場合は、図３５に示した誤差重み付けマトリクス３９０を使用して、画素３９２から誤差を分散させることができる。
【０１３８】
この場合も、起動アーティファクトの発生を防ぐために、図２４に示したマトリクス３００のような１項の誤差マトリクスを使用し、入力画素値ａが１または０のときには、処理される画素から誤差を垂直方向に分散させる。
【０１３９】
誤差重みおよびしきい値の最適値は、前述の方法を使用して決定される。図３６および図３７の（Ａ）〜（Ｄ）に、２行蛇行走査を使用する階調依存型誤差拡散システムの最適な誤差重みおよびしきい値を示す。図３７の（Ｅ）は、誤差重み付けが拡散される画素の位置を示す。図３７の（Ａ）は、処理される画素のすぐ右側にある画素に拡散される誤差重み付けを示す。図３７の（Ｂ）〜（Ｄ）は、処理する画素の下にある行の画素に左から右に拡散される誤差重み付けを示す。図３７の（Ａ）〜（Ｄ）に示したように、ハイライトおよびシャドウ領域（領域１）、遷移領域（領域２）および中間調（領域３）に分けられた吸収率の３つの領域がある。
【０１４０】
図３８は、図３６および図３７の（Ａ）〜（Ｄ）に示したしきい値および誤差重み付けによる２行蛇行走査の階調依存型誤差拡散方法を使用して生成された階調ハーフトーン画像４００である。
【０１４１】
この階調依存型誤差拡散のハーフトーン化方法の変形は、異なる走査線ごとに異なるフィルタ・セットを使用するというような、たとえば偶数番の線についてはあるフィルタ・セットを使用し、奇数番の線については他のフィルタ・セットを使用するというような変形が可能であるということを理解されたい。これは、単一のフィルタ・セットの場合よりも悪くなることはなく、特に２行蛇行走査では、ほとんどの場合テクスチャ品質を高めることになる。このことによって、計算はあまり複雑にならないが、設計が大幅に複雑になることがある。
【０１４２】
１つの実施形態において、ルックアップテーブルおよび誤差拡散処理の制御方法が、プリンタ・ドライバとしてマイクロディスケットまたはフロッピ・ディスクなどのコンピュータ可読媒体で提供される。その後、このプリンタ・ドライバは、図５のコンピュータ１２２のようなコンピュータに導入され、その結果プログラムが、コンピュータのＲＡＭに導入される。そのようなプログラムを、プリンタに導入することもでき、またはある実施形態では、プリンタ内のファームウェアに導入することもできる。このプログラムは、印刷モードまたはプリントヘッド・パラメータ、および他の因子にも依存する。すべての論理機能を、ハードウェアまたはソフトウェアで実現することができる。ハードウェアを使用する場合、バス線を介してハーフトーン方法を実施する回路に、様々なテーブル値を利用することができる。またこの方法は、この開示を読んだ後で当業者が理解するような、様々な論理装置、ルックアップテーブルおよび画像マップとのデータの転送およびタイミングを制御するＡＳＩＣによって実現することもできる。
【０１４３】
この発明の特定の実施形態について図示し説明してきたが、そのより広い態様において、この発明から逸脱することなく変更および修正を行うことができ、したがって特許請求の範囲は、この発明の真の精神および範囲に含まれるすべての変更および修正をその範囲内に含むものである。
【０１４４】
この発明は、以下の実施態様を含む。
【０１４５】
（１）少なくとも１つのしきい値および複数の誤差重み付けによる誤差拡散を実行するステップ（１５０）と、
入力画素値に基づいて少なくとも１つのしきい値および複数の誤差重み付けを得るステップ（２００、２２０）と、
を含み、前記少なくとも１つのしきい値および複数の誤差重み付けが、費用関数を使用して決定されるようにした階調依存型誤差拡散ハーフトーン化方法。
【０１４６】
（２）入力画素値を入力するステップと、
前記入力画素値、および前に処理した画素から拡散された量子化誤差とに基づいて、修正画素値を生成するステップ（１５８）と、
前記少なくとも１つのしきい値を前記修正画素値と比較して、２値の出力画素値を生成するステップ（１５２）と、
前記２値の出力画素値および前記修正画素値の間の差に基づいて、前記量子化誤差を生成するステップ（１５４）と、
前記複数の誤差重み付けを有する前記量子化誤差を、次に処理する画素に拡散させるステップ（１５６）と、
を含む上記（１）に記載の階調依存型誤差拡散ハーフトーン化方法。
【０１４７】
（３）前記少なくとも１つのしきい値を得るステップが、上のしきい値および下のしきい値（図１６）を得るステップを含み、前記少なくとも１つのしきい値を修正画素値と比較するステップが、前記上のしきい値を前記修正画素値と比較し、前記下のしきい値を前記修正画素値と比較して、前記２値の出力画素を生成するステップを含む上記（２）に記載の階調依存型誤差拡散ハーフトーン化方法。
【０１４８】
（４）前記修正画素値が、前記上のしきい値および下のしきい値の間にある場合には、
ほぼ中間調レベルを有する２値のビットマップ・パターン（１６０）を提供するステップと、
前記入力画素と同じ座標にある前記２値のビットマップ・パターンの画素値を使用して、前記２値の出力画素を生成するステップと、
を含む上記（３）に記載の階調依存型誤差拡散ハーフトーン化方法。
【０１４９】
（５）前記少なくとも１つのしきい値および複数の誤差重み付けが最適化される階調依存型誤差拡散ハーフトーン化方法であって、
階調レベルを有するパッチを提供するステップ（２０２）と、
直接２分探索ハーフトーン化（２０４）によって、前記パッチの第１のハーフトーン・パターンを生成するステップと、
初期しきい値および初期誤差重み付けを使用して、誤差拡散ハーフトーン化（２０６）によって前記パッチの第２のハーフトーン・パターンを生成するステップと、
前記第１のハーフトーン・パターンを前記第２のハーフトーン・パターンと比較するステップ（２１２）と、
前記初期しきい値および初期誤差重み付けを変更して、第１の費用関数を最小にするステップ（２１３）と、
を含む上記（１）に記載の階調依存型誤差拡散ハーフトーン化方法。
【０１５０】
（６）前記少なくとも１つのしきい値および複数の誤差重みが最適化される階調依存型誤差拡散ハーフトーン化方法であって、
階調レベルを有するパッチを提供するステップ（２２２）と、
人間視覚系モデル（２２４）を使用して前記パッチをフィルタリングし、第１のフィルタリングされた画像を生成するステップと、
初期しきい値および初期誤差重みを使用し、誤差拡散ハーフトーン化（２２６）によって前記パッチの第１のハーフトーン・パターンを生成するステップと、
人間視覚系モデル（２３０）を使用して前記第１のハーフトーン・パターンをフィルタリングし、第２のフィルタリングされた画像を生成するステップと、
前記第１のフィルタリングされた画像を前記第２のフィルタリングされた画像と比較するステップ（２３２）と、
前記初期しきい値および初期誤差重みを変更して、第２の費用関数を最小にするステップ（２３３）と、
を含む上記（５）に記載の階調依存型誤差拡散ハーフトーン化方法。
【０１５１】
（７）前記第２の費用関数が、知覚される合計の二乗誤差であり、前記第１の費用関数が以下の式で表され、
【数３２】
0004268313.tif 000023
該式において、ＧDBS（ｕ，ｖ）は前記第１のハーフトーン・パターンの高速フーリエ変換の期待値の大きさを示し、ＧTDED（ｕ，ｖ）は前記第２のハーフトーン・パターンの高速フーリエ変換の期待値の大きさを示しており、
前記第２の費用関数は、階調レベル範囲の端にある階調レベルに使用され、前記第１の費用関数は、階調レベル範囲の中間調における階調レベルに使用される上記（６）に記載の階調依存型誤差拡散ハーフトーン化方法。
【０１５２】
（８）確率変数を修正項に加えることによって起動アーティファクトを防ぐステップを含み、該修正項が、前に処理された画素から拡散された量子化誤差の和である上記（１）に記載の階調依存型誤差拡散ハーフトーン化方法。
【０１５３】
（９）前記入力画素値がハイライトまたはシャドウの階調レベルであるとき、前記複数の誤差重み付けを有する前記量子化誤差を、第１の領域（３４０）上の次に処理される画素に拡散し、該第１の領域の一部の画素が、該量子化誤差の一部を受け取るようにするステップと、
前記入力画素値が中間調レベルのとき、前記複数の誤差重み付けを有する前記量子化誤差を、第２の領域（図９）上の次に処理される画素に拡散するステップとを含み、
前記第１の領域が、前記第２の領域よりも大きい上記（２）に記載の階調依存型誤差拡散ハーフトーン化方法。
【０１５４】
（１０）前記入力画素値が、ハイライトレベルおよび中間調レベルの間の遷移レベルにあるとき、またはシャドウレベルおよび中間調レベルの間の遷移レベルにあるとき、前記複数の誤差重み付けを有する量子化誤差を、第３の領域（３５０）上の次に処理される画素に拡散するステップを含み、該第３の領域の一部の画素が、該量子化誤差の一部を受け取るようにし、
該第３の領域が、前記第２の領域よりも大きく、前記第１の領域よりも小さい上記（９）に記載の階調依存型誤差拡散ハーフトーン化方法。
【０１５５】
【発明の効果】
この発明によると、しきい値および誤差重みが最適化される階調依存型の誤差拡散方法を使用するので、高品質のハーフトーン画像を提供することができる。
【図面の簡単な説明】
【図１】従来の誤差拡散システムの図。
【図２】従来の誤差拡散システムにおける誤差の分布を示す図。
【図３】従来の誤差拡散システムによって生成された階調ハーフトーン画像。
【図４】好ましい誤差拡散方法のすべてまたは一部を実行する処理回路を備えるカラー・インクジェット・プリンタを示す図。
【図５】コンピュータまたはプリンタまたはその両方がこの発明による誤差拡散方法を実行する場合の、インクジェット・プリンタに接続されたコンピュータを示す図。
【図６】図５のコンピュータおよびプリンタによって実行される一般的な方法を示す図。
【図７】この発明の実施形態による階調依存型誤差拡散ハーフトーン化システムの図。
【図８】直接２分探索ハーフトーン化法によって生成された吸収率０．５の２値ビットマップ・パターンを示す図。
【図９】図７の階調依存型誤差拡散システムにおける誤差の分布を示す図。
【図１０】従来の誤差拡散システムおよび直接２分探索システムによって生成された吸収率８７／２５５のパッチを表す２値パターンを示す図。
【図１１】図１０の（Ａ）および（Ｂ）に示したパターンの高速フーリエ変換の大きさをそれぞれ示す図。
【図１２】この発明の実施形態に従う、中間調における最適化されたしきい値および誤差重み付けを得るための階調依存型誤差拡散訓練システムを示す図。
【図１３】この発明の実施形態に従う、ハイライトおよびシャドウ領域において最適化されたしきい値および誤差重み付けを得る階調依存型誤差拡散訓練システムを示す図。
【図１４】最適化されたしきい値および誤差重み付けを得るのに使用されるダウンヒル探索法を示すフローチャート。
【図１５】図１４に示されるダウンヒル探索法のフローチャートの続きを示す図。
【図１６】この発明に従って最適化されたしきい値の結果を示す図。
【図１７】この発明の実施形態に従って最適化された誤差重み付けｗ［０，１；ａ］、ｗ［１，−１；ａ］、ｗ［１，０；ａ］およびｗ［１，１；ａ］の結果をそれぞれ示す図。
【図１８】従来の誤差拡散システムを使用して生成されたハーフトーン画像を示す図。
【図１９】図１６および図１７の（Ａ）〜（Ｄ）に示したしきい値および誤差重み付け使用する階調依存型誤差拡散システムを使用して生成されたハーフトーン画像を示す図。
【図２０】異なる入力画素値についての修正項ｃ［ｍ，ｎ；ａ］の確率密度関数を示す図。
【図２１】修正項ｃ［ｍ，ｎ；ａ］の平均値を示す図。
【図２２】図２１による修正項によって修正された図１６からの上および下の階調依存型しきい値を示す図。
【図２３】図２２に示した修正された上および下の階調依存型しきい値を使用してこの発明の実施形態に従って生成されたハーフトーン画像を示す図。
【図２４】吸収率０または１の領域における垂直方向の誤差の分布を示す図。
【図２５】この発明に従う階調依存型誤差拡散システムを使用して生成された階調ハーフトーン画像を示す。
【図２６】直接２分探索ハーフトーン化方法を使用して生成された階調ハーフトーン画像を示す図。
【図２７】画素Ａが２値化されるべき現在の画素である、画素のマトリクスを示す図。
【図２８】この発明の実施形態に従って使用される広い誤差重み付けマトリクスを示す図。
【図２９】この発明の実施形態に従って使用される他の広い誤差重み付けマトリクスを示す図。
【図３０】対角線方向における誤差の分布を示す図。
【図３１】従来のラスタ走査を使用する階調依存型誤差拡散システムの最適しきい値を示す図。
【図３２】従来のラスタ走査を使用する階調依存型誤差拡散システムの最適な誤差重み付けの値および位置を示す図。
【図３３】図３１および図３２の（Ａ）〜（Ｄ）に示したしきい値および誤差重み付けによるラスタ走査階調依存型誤差拡散方法を使用して生成された階調ハーフトーン画像を示す図。
【図３４】この発明の実施形態に従って使用される広い誤差重み付けマトリクスを示す図。
【図３５】この発明の実施形態に従って使用される他の広い誤差重み付けマトリクスを示す図。
【図３６】２行蛇行走査を使用する階調依存型誤差拡散システムの最適しきい値を示す図。
【図３７】２行蛇行走査を使用する階調依存型誤差拡散システムの最適な誤差重み付けの値およびそれらの位置を示す図。
【図３８】図３６および図３７の（Ａ）〜（Ｄ）に示したしきい値および誤差重み付けによる２行蛇行走査の階調依存型誤差拡散法を使用して生成された階調ハーフトーン画像を示す図。
【符号の説明】
１００ プリンタ
１２０ 印刷システム
１２２ コンピュータ
１２６ プリンタ
１５０ 階調依存誤差拡散ハーフトーン化システム
１５２ しきい値マトリクス
１５６ 誤差重み付けマトリクス
【図１】
0004268313.tif 000025
【図２】
0004268313.tif 000026
【図３】
0004268313.tif 000027
【図４】
0004268313.tif 000028
【図５】
0004268313.tif 000029
【図６】
0004268313.tif 000030
【図７】
0004268313.tif 000031
【図８】
0004268313.tif 000032
【図９】
0004268313.tif 000033
【図１０】
0004268313.tif 000034
【図１１】
0004268313.tif 000035
【図１２】
0004268313.tif 000036
【図１３】
0004268313.tif 000037
【図１４】
0004268313.tif 000038
【図１５】
0004268313.tif 000039
【図１６】
0004268313.tif 000040
【図１７】
0004268313.tif 000041
【図１８】
0004268313.tif 000042
【図１９】
0004268313.tif 000043
【図２０】
0004268313.tif 000044
【図２１】
0004268313.tif 000045
【図２２】
0004268313.tif 000046
【図２３】
0004268313.tif 000047
【図２４】
0004268313.tif 000048
【図２５】
0004268313.tif 000049
【図２６】
0004268313.tif 000050
【図２７】
0004268313.tif 000051
【図２８】
0004268313.tif 000052
【図２９】
0004268313.tif 000053
【図３０】
0004268313.tif 000054
【図３１】
0004268313.tif 000055
【図３２】
0004268313.tif 000056
【図３３】
0004268313.tif 000057
【図３４】
0004268313.tif 000058
【図３５】
0004268313.tif 000059
【図３６】
0004268313.tif 000060
【図３７】
0004268313.tif 000061
【図３８】
0004268313.tif 000062