(57)【要約】中間ドットを用いた誤差拡散を使用してイメージをハーフトーン化する方法及びシステムを提供する。まずピクチャレベル(例えばグレーレベル)を有する入力画素(入力ピクセル)を受け取る(700)。次に入力ピクセルのグレーレベルに基づいて再現可能グレーレベルが生成される(710)。次いで入力ピクセルのグレーレベル及び誤差量(例えば隣接する領域又はピクセルから伝搬すなわち拡散される誤差)に基づいて補正グレーレベルが生成される(720)。補正グレーレベルがしきい値と所定の関係にあるか否かが判定される(730)。補正グレーレベルがしきい値と所定の関係にある場合、再現可能グレーレベル(すなわち中間ドットサイズ)が出力として提供される(740)。補正グレーレベルがしきい値と所定の関係にない場合、ゼロ値が出力として提供される(750)。出力グレーレベル及び補正グレーレベルは、誤差を計算するため、また誤差を将来の隣接領域又はピクセルに伝搬すなわち拡散させるために、誤差拡散モジュールに提供されることに留意されたい。
2004531129.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力ピクセルを有するディジタルイメージをハーフトーン化する方法であって、
ピクチャレベルを有する入力ピクセルを受け取り(700)、
入力ピクセルのグレーレベルに基づいて再現可能なグレーレベルを生成し(710)、
入力ピクセルのグレーレベルと誤差量とに基づき補正されたグレーレベルを生成し(720)、
前記補正されたグレーレベルがしきい値と所定の関係にあるか否かを判定し(730)、
前記補正されたグレーレベルが前記しきい値と所定の関係にある場合に前記再現可能なグレーレベルを出力として提供し(740)、
前記補正されたグレーレベルが前記しきい値と所定の関係にない場合にゼロ値を出力として提供する(750)、
という各ステップを含む方法。
【請求項２】
誤差拡散モジュールに誤差測度を提供するステップを更に含み、該誤差測度が前記出力グレーレベルと前記補正されたグレーレベルとに基づくものであり、前記誤差拡散モジュールが該誤差測度を将来のピクセルに伝搬させる、請求項１に記載の方法。
【請求項３】
前記出力グレーレベルと前記補正されたグレーレベルとを誤差拡散モジュールに提供し、
前記出力グレーレベルと前記補正されたグレーレベルとに基づいて前記誤差測度を決定し、
該誤差測度を将来のピクセルに伝搬させる、
という各ステップを更に含む、請求項１に記載の方法。
【請求項４】
前記しきい値が、所定のしきい値及びランダムに生成されたしきい値のうちの一方である、請求項１に記載の方法。
【請求項５】
前記所定のしきい値が、ハーフトーンスクリーンを使用して生成される、請求項４に記載の方法。
【請求項６】
前記ハーフトーンスクリーンが、ブルーノイズ・ハーフトーンスクリーン、クラスタ化ドット・ハーフトーンスクリーン、及びグリーンノイズ・ハーフトーンスクリーンのうちの１つである、請求項５に記載の方法。
【請求項７】
前記補正されたグレーレベルがしきい値と所定の関係にあるか否かを判定する前記ステップが、前記補正されたグレーレベルが前記しきい値よりも大きいか否かを判定することを含む、請求項１に記載の方法。
【請求項８】
前記しきい値が、次式、すなわち、
ｔ(i,j)＝0.3×(128−ｔcsd(i,j))＋p／２
（ｔcsd(i,j)は色平滑ディザマトリクス要素、ｐは再現可能なグレーレベル値）
により生成される、請求項１に記載の方法。
【請求項９】
前記再現可能なグレーレベルが、ハイライト領域でサブピクセル変調を使用して生成され、及び中間階調領域及びシャドー領域で完全なドットへと移行する、中間ドットとして表される、請求項１に記載の方法。
【請求項１０】
前記出力ピクセル値ｚ(i,j)が、次式、すなわち、
ｚ(i,j)＝Ｐ(i,j)    （ｙ(i,j)＞ｔ(i,j)の場合）
０         （上記以外の場合）
により生成され、ここで、ｙ(i,j)は前記補正されたグレーレベル値、Ｐは前記再現可能なグレーレベル値、及びｔ(i,j)は前記しきい値である、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に画像処理に関し、特に中間ドットを用いた誤差拡散方法及びシステムに関する。
【背景技術】
【０００２】
ディジタルプリンティング分野では、用紙上のイメージ領域の強度（すなわちグレーレベル）の表現は、この10年間に発行された多種多様なアルゴリズムの対象となってきた。ディジタルプリンタは、通常は単位長さあたりのマーク数（一般にはドット／インチ（dpi））という形の指定された解像度で通常はドットという形で用紙上にマークを形成することが可能なプリンタと定義される。かかるディジタルプリンタを使用してグレーレベル強度を印刷する場合には、一般に、様々な幾何学的なパターンに従ってマークすなわちドットを用紙上に配置し、これにより、１グループをなすドット及びドットのない空白スポットを目で見た際に、初期の用紙ストック（普通は白色）とインクで全て覆った部分（すなわちべた濃度）との間の中間階調の描画がもたらされる。以下では、白色の用紙ストックに関して考察するが、これは本発明の例示のためのものであって本発明を制限するものではないことが理解されよう。
【０００３】
用紙上のドットマトリクスの解像度があまり高くない（例えば100dpi又はそれ未満の）場合には、顕著な問題が発生し、使用された幾何学的なパターンが特に目に見えるようになる。この場合には、観察者は、イメーが幾何学的なパターン自体のイメージアーチファクトによって表現されていることから気がそれ、イメージが低品質であるという印象を受ける。この問題に対する自明な解決策は、非常に高い解像度（例えば300dpi又はそれよりも高解像度で）プリントを行って、かかるアーチファクトがあまり目立たなくなり、負の印象がより目立たなくなるようにすることである。
【０００４】
1976年に、Robert W. Floyd及びLouis Steinbergは、Proceedings of the S.I.D. Vol. 17/2に「An Adaptive Algorithm for Spatial Greyscale」と題する論文を発表した。この論文には、該著者等が「誤差拡散(ＥＤ)」と称するアルゴリズムが記載されている。このアルゴリズムは、二階層（bilevel）装置を使用する、すなわちドットがあるかないかを用いる、グレースケールのための方法を提供する。この従来技術の方式によれば、連続階調イメージを表すグレーレベルデータがしきい値プロセスを受け、これにより、選択されたしきい値（例えば50％）を越えるグレーレベルにプリントすべきドットが割り当てられ、しきい値未満のグレーレベルにはドットが割り当てられない。この方法による処理の粗さは、該プロセスによる強度誤差を追跡し、該誤差を隣接する画素（すなわち「ピクセル」）に指定された量で伝搬させて、該しきい値プロセスでピクセルを重み付けすることによって補償される。この手法は、少数のドットを包含する小さな領域にわたってグレー階調の一層精確な表現を提供するものである。このため、イメージアーチファクトが知覚される程度が減り、より良好な品質のグレースケールイメージが生成される。更に、ＥＤアルゴリズムは、生成されるイメージの良好なエッジ品質を維持して、二階層方式で生成されたイメージに特有の「ぼやけ」を最小限にする。
【０００５】
後の研究者により、ＥＤ手法が、300dpiの解像度であってもなお、高品質のイメージを生成するにあたり深刻な制約を受けることが明らかになった。具体的には、ＥＤ手法の場合、グレースケールイメージを生成する際に、二値プリンタのドットは、アドレス指定可能なポイントの離隔距離よりも大きな直径を有するため、互いに重複する可能性がある。該重複は、グレー階調の離散化表現に対する非線形的な応答を生じさせるものとなる。加えて、該しきい値プロセスは、特定のグレーレベルがプリンティングされた際に目に見える望ましくないパターン又はテクスチャを導入するものとなる。
【０００６】
G. J. Dispoto、L. R. Mather、及びJ. D. Meyerによる「Method for rendering grayscale images with variable dot sizes」と題する米国特許第4,680,645号には、可変ドットサイズの誤差拡散を用いてプリント結果を改善するハーフトーン化方法が記載されている。この従来技術による手法では、プリンタが生成することができるドットサイズ及び対応するグレーレベルのリストを用いてルックアップテーブルが作成される。入力イメージピクセルのグレーレベルについて、それに最も近い再現可能なグレーレベルがルックアップテーブルから見つけられ、これが出力グレーレベルに指定される。入力グレーレベルと出力グレーレベルとの間の誤差は周囲のピクセルへと拡散される。これにより、最小限のコントラストを有するハーフトーンパターン（すなわち、任意の特定のグレーレベルについて該グレーレベルを再現することになる最も近い２つのドットサイズからなるハーフトーンパターン）が得られる。白から黒まで変化するグレーをプリントする場合には、白色ピクセルは可能な限り早期に排除される。
【０００７】
結果的に最大限のコントラストが得られる、可変ドットサイズを用いた誤差拡散の使用を拡張した例が、Q. Linによる「Print N-tone images with imperceptible dots」と題する米国特許第5,615,021号に記載されている。図８は、該米国特許第5,615,021号に記載のハーフトーン化プロセスを示している。入力イメージは一定の解像度Ｄドット／インチ（dpi）で表されているものと仮定する。最初のステップは、マルチレベル誤差拡散を用いてイメージをハーフトーン化することであり、これによりイメージＡ中の各ピクセルが１ビットよりも多くのビットを使用して表される。次に、イメージＡ中の各ピクセルが、二値スーパーピクセル（すなわち複数のピクセルからなるブロック）へとマッピングされて、複数のドットが共にクラスタ化される。出力は、入力イメージよりも高い解像度で描画された二値ハーフトーンイメージである。複数のドットが共にクラスタ化されるが、該ドットクラスタの中心は規則正しく離間される。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
この手法の１つの欠点は、該手法の結果として規則正しい矩形の格子上に複数のドットクラスタが配置されてなるハーフトーンが得られることにある。この配置は、細部を描写するプリンタの最大能力を完全に利用することを妨げるものとなる。プリンティングに関する専門用語で換言すれば、この手法は、プリントの「ライン／インチ（lpi）」を事実上低減させるものとなる。外観上の幾つかの態様では、これは、従来技術によるクラスタ化ドットハーフトーン処理(clustered-dot halftoning)による結果と類似したものとなり得る。このため、この先行技術による手法は、望ましくないモアレアーチファクトをもたらし得るものである、と予想するのが妥当である。
【０００９】
上記に基づき、既述の欠点を克服する、イメージをハーフトーン化するための方法及びシステムが必要とされている。
【課題を解決するための手段】
【００１０】
中間（partial）ドットを用いたコントラストを最大化する誤差拡散を使用したハーフトーン化方法及びシステム。本発明の一実施形態により提供されるハーフトーン化アルゴリズムは、ハイライト領域で中間ドットを使用し、また中間階調領域及びシャドー領域では完全なドットへと移行することにより、プリントされたイメージにおける目に見えるドットをなくすものである。好ましくは、該中間ドットは、サブピクセルパルス変調（sub-pixel pulse modulation）を利用することにより生成される。
【００１１】
本発明の一実施形態によれば、中間ドットを用いた誤差拡散を使用するハーフトーン化方法が提供される。最初に、ピクチャレベル（例えばグレーレベル）を有する入力画素（入力ピクセル）を受け取る。次に、該入力ピクセルのグレーレベルに基づいて、再現可能なグレーレベルが生成される。次いで、入力ピクセルのグレーレベルと誤差量（例えば、隣接する領域又はピクセルから伝搬され又は拡散された誤差）とに基づいて補正されたグレーレベルが生成される。該補正されたグレーレベルがしきい値と所定の関係にあるか否かが判定される。補正されたグレーレベルがしきい値と所定の関係にある場合には、再現可能なグレーレベル（中間ドット）が出力として提供される。また、補正されたグレーレベルがしきい値と所定の関係にない場合には、ゼロ値が出力として提供される。出力グレーレベル及び補正されたグレーレベルは、誤差を計算し、及び該誤差を後に隣接する領域又はピクセルに伝搬させ又は拡散させるために、誤差拡散モジュールに提供される、ということに留意されたい。
【発明を実施するための最良の形態】
【００１２】
本発明を、その制限ではなくその例示を目的として図面に示す。なお、同図において、同様の符号は同様の構成要素を意味している。
【００１３】
中間ドットを用いた誤差拡散方法及びシステムについて説明する。以下の説明では、説明を目的として、本発明の完全なる理解を提供するために多くの特定の詳細について解説する。しかし、本発明はかかる特定の詳細なしで実施可能であることが当業者には明らかであろう。別の実施形態では、本発明を不必要に曖昧にすることを避けるため、周知の構造及び装置をブロック形態で示す。
・システム100
図１は、本発明の中間ドットを用いた誤差拡散機構110を実施することができる例示的なコンピュータシステム100を示すブロック図である。該コンピュータシステム100は、有線媒体（例えばケーブル）や無線リンク（例えば無線周波数(ＲＦ)リンク又は赤外線(ＩＲ)リンク）といった通信リンク114を介してオフィス機器108に接続されたパーソナルコンピュータ(ＰＣ)104を含む。該ＰＣ104は、ポータブルコンピュータ、個人情報端末、携帯電話等といった任意のコンピューティングデバイスとすることが可能である。
【００１４】
オフィス機器108は、レーザプリンタ、インクジェットプリンタ、ファクシミリ機、ディジタルコピー機、オールインワンオフィス機器等の再現装置であることができる。オフィス機器108は、ハーフトーン化プロセスを使用してイメージ及びテキストを印字媒体118（例えば用紙）上に描写する。オフィス機器108は、プリンティングされるドットサイズを変更し又は変調する能力を有していることが重要である。例えば、現在入手可能な多くのレーザプリンタは、プリンティングされるドットサイズを変更又は変調する能力を有する。以下で詳述するように、本発明は、ドットサイズに依存する出力グレーレベルを提供するものである。
【００１５】
本実施形態では、ＰＣ104は、オフィス機器108用のドライバ124を含み、該ドライバの一部として、本発明の中間ドットを用いた誤差拡散機構110が組み込まれる。本発明の中間ドットを用いた誤差拡散機構110はまた、フロッピーディスク、コンパクトディスク、又はユーザがＰＣ104に本発明の誤差拡散方法をロードするために使用することができる他の媒体といった、コンピュータにより読み出すことが可能な任意の媒体に記憶させることも可能である。代替的に、本発明の中間ドットを用いた誤差拡散機構110は、インターネット等のネットワークに接続されたサーバ上に存在することができる。この場合には、本発明の中間ドットを用いた誤差拡散機構110は、ネットワークに接続するための通信機能を有する任意のコンピューティングデバイス（例えばＰＣ104）により必要に応じてアクセスすることができるものとなる。
・ソフトウェアによる実施形態
図２は、本発明の中間ドットを用いた誤差拡散機構の例示的なソフトウェアによる一実施形態を示している。この実施形態では、本発明の中間ドットを用いた誤差拡散機構110は、メモリ（例えばＲＯＭ又はＲＡＭ）等の記憶装置210内に存在するソフトウェアコードとして実施することができる。
・ハードウェアによる実施形態
図３は、本発明の中間ドットを用いた誤差拡散機構の例示的なハードウェアによる一実施形態を示している。この実施形態では、本発明の中間ドットを用いた誤差拡散機構110は、ハードウェアで実施することができる。例えば、オフィス機器108は、本発明の中間ドットを用いた誤差拡散機構110に従って処理を実行する論理回路を有する集積回路310を含むことができる。
【００１６】
したがって、本発明の中間ドットを用いた誤差拡散機構110は、ソフトウェア、ハードウェア、ファームウェア、又はそれらの組み合わせとして実施することが可能である。更に、本発明の中間ドットを用いた誤差拡散機構110は、任意の記憶装置（例えばメモリ）、コンピュータにより読み出すことが可能な媒体（例えばディスク、コンパクトディスク等）、ハードウェア要素（例えば集積回路）、又はそれらの組み合わせに組み込むことができる。更に、本発明の中間ドットを用いた誤差拡散機構110は、コンピューティングデバイス（例えばＰＣ104）、オフィス機器108、ウェブサーバ、又はコンピューティングデバイスとオフィス機器108との間に配置される他の中間的な装置内に存在することができる。
・誤差拡散
従来技術による典型的なＥＤ解析では、グレーレベルは、次の３ステップの手順で決定される。第１に、しきい値プロセスに基づいてプリンティング決定が行われる。第２に、該プリンティング決定の結果として誤差が計算される。第３に、該計算された誤差が隣接する領域又はピクセルに伝搬され、すなわち拡散される。
【００１７】
１つのイメージ表現において、該イメージの各画素（ピクセル）は、実際のピクチャレベルｌ(i,j)を１つずつ有する（iはi番目の列、jはj番目の行又は走査を表す）。一般に、プリンティング決定の入力におけるグレーレベルは、該プリンティング決定の結果として得られる二値レベル値と厳密に等しいわけではない。したがって、１ピクセルについてプリンティング決定は、おそらくは誤差要素を含むものとなる。
【００１８】
ＥＤを用いた典型的なプリンティング状況では、１ピクセルについてのプリンティング決定は、該ピクセルの補正レベルｌc(i,j)をしきい値Ｔと比較することにより行われる。すなわち、ｌc(i,j)がＴよりも大きい場合にはＰ(i,j)＝１でプリントし、ｌc(i,j)がＴと等しい場合またはＴ未満の場合にはＰ(i,j)＝０となる。次いで、下記の式に示すように、補正レベルと用紙上に実際に配置されるレベルとの間の差として誤差が計算される。
【００１９】
Ｅ(i,j)＝ｌc(i,j)−ｌmaxＰ(i,j)
ここで、ｌmaxは１ドット（典型的には１インクスポット）の最大濃度である。
【００２０】
この誤差E(i,j)は、次式に示すように、まだ二値化されていない隣接する将来のピクセルへと伝搬される。
【００２１】
ｌc(i+m,j+n)＝ｌc(i+m,j+n)＋Ｅ(i,j)Ｗ(m,n)
ここで、
m＝1,…,k; n＝0の場合、上記式は現在の行における将来のピクセルを表し、
m＝-k,…,k; n＝1,…,kの場合、上記式は将来の行における将来のピクセルを表す。
【００２２】
Ｗ(m,n)が誤差拡散に使用される一組の重みであることに留意されたい。実施形態によっては、該一組の重みは全ピクセルについて一定となることに留意されたい。他の実施形態では、該一組の重みはピクセル毎に異なることが可能である。例示的な一組の重みは、既述のFloyd及びSteinbergの出版物に記載されている。また、現在のピクセルはm＝0及びn＝0に位置していることに留意されたい。
・中間ドットを用いた誤差拡散
図４は、本発明の一実施形態による中間ドットを用いた誤差拡散を実行するシステム400を示すブロック図である。該システム400は、ドットサイズルックアップテーブル(ＬＵＴ)410と、該ドットサイズＬＵＴ410に接続された可変出力しきい値処理モジュール(ＶＴＭ)420と、該ＶＴＭ420に接続された誤差拡散モジュール430とを含む。該システム400は、入力ピクセル値ｘ(i,j)を受け取り、出力値ｚ(i,j)を生成する。
【００２３】
この実施形態では、誤差拡散モジュール430は誤差測度決定ユニット434を含み、該誤差測度決定ユニット434が、出力値ｚ(i,j)及び補正値ｙ(i,j)を受け取り、これらに基づき誤差測度を生成する。続いて、誤差拡散モジュール430は、該誤差測度に、以下で詳述する重みを適用し、将来のピクセルに選択的に誤差を伝搬させる。
【００２４】
図５は、本発明の代替的な実施形態による図１の中間ドットを用いた誤差拡散モジュールを更に詳細に示すブロック図である。この実施形態では、出力値ｚ(i,j)及び補正値ｙ(i,j)に基づいて誤差測度を決定する誤差測度決定ユニット510が設けられる。該誤差測度決定ユニット510は、誤差拡散ユニット530とは別個のものとすることができることに留意されたい。この実施形態では、誤差拡散ユニット530は誤差測度決定ユニット510から誤差測度を受け取って適当な重みを適用し、その誤差を将来のピクセルに拡散させる。「将来のピクセル」とは、まだ処理されていないピクセルのことである。典型的には、各ピクセルはラスタ順で処理される。誤差測度決定ユニット510は、補正値ｙ(i,j)を負の出力値(-ｚ(i,j)）に加算する加算器として実施することができる。
【００２５】
具体的には、本発明の好ましい実施形態による方法は、以下の手順で示すことができる。
・ドットサイズルックアップテーブル410の作成
本発明の一つの特徴は、入力ピクセルｘ(i,j)を入力として受け取り、プリンタにより再現されるべき中間ドットサイズに対応する再現可能なグレーレベル値を出力として提供する、ドットサイズルックアップテーブル410にある。好ましくは、可変の再現可能なグレーレベル値Ｐ(i,j)は、入力グレーレベルｘ(i,j)に従って選択される。例えば、可変の再現可能なグレーレベルＰ(i,j)は、ハイライト領域では小さく、シャドー領域では大きくすることが可能である。ｘ(i,j)の値が0〜255の間にある場合、Ｐ(i,j)の値は0〜255の間にある。
【００２６】
図６は、例示的な「可変の再現可能なグレーレベルＰ(i,j)」対「入力グレーレベルｘ(i,j)」のグラフを示したものである。最も明るいグレーレベルでは、中間ドットが、例えば通常のパルス幅の50％で生成される。該パーセント値は、ドットが作成されるが目には見えないものとなるよう選択することが可能である。入力グレーレベルが暗くなるにつれて、中間ドットサイズは大きくなる。なお、特定の用途に適するように、異なる形状を有する他の「再現可能なグレーレベルＰ(i,j)」対「入力グレーレベル」関数を利用することが可能であることに留意されたい。
【００２７】
次いで、このルックアップテーブルがプリンティング決定時に使用されて、表面に堆積させるべき実際のドットサイズが決定される。例示的なドットサイズＬＵＴを表１に示す。
【００２８】
【表１】
2004531129.tif 000003
【００２９】
・可変出力しきい値処理モジュール
可変出力しきい値処理モジュール（ＶＴＭ）420は、再現可能なグレーレベルＰ(i,j)（以下「中間ドットサイズ」とも称す）を受け取るための第１の入力と、補正されたグレーレベルｙ(i,j)を受け取るための第２の入力と、出力グレーレベルｚ(i,j)を生成するための出力とを有する。可変出力しきい値処理モジュール（ＶＴＭ）420は、ゼロ値又は可変再現可能なグレーレベルＰ(i,j)の何れか一方を選択的に生成する。該ゼロ値は、ドットがないことを示し、可変再現可能なグレーレベルは、中間ドットを示すものである。なお、Ｐ(i,j)の値は入力ピクセル毎に変化し得るものである（すなわち再現可能なグレーレベルはi及びjに依存する）。
【００３０】
本発明の中間ドットを用いた誤差拡散は、従来の誤差拡散アルゴリズムに通常付随するアーチファクトが視認されることのない、非常に滑らかなテクスチャをプリントするものとなる。
【００３１】
好ましくは、可変出力しきい値処理モジュール420は次の演算を実行する。
【００３２】
ｚ(i,j)＝Ｐ(i,j)    （ｙ(i,j)＞ｔ(i,j)の場合）
０         （上記以外の場合）
（ｔ(i,j)はしきい値）
しきい値は、所定のしきい値又はランダムに生成されたしきい値とすることができる。所定のしきい値の例としては、従来のクラスタドット・ハーフトーンスクリーン、分散ドット又はブルーノイズ・ハーフトーンスクリーン、及びグリーンノイズ・ハーフトーンスクリーンを使用することにより生成されるしきい値が挙げられる。ブルーノイズマスクを使用する一例が、T. Mitsa及びK. J. Parkerによる「Digital Halftoning Technique Using a Blue-Noise Mask」(J. Opt. Soc. of Am. A, 9 (11): 1920-1929, November 1992）に記載されている。グリーンノイズマスクを使用する一例が、D. Lau、G. Arce、及びN Allagherによる「Digital Halftoning by Means of green-Noise Masks」（J. Opt. Soc. Am. A, Vol. 16, No. 7 ,pp1575-1586，July 1999）に記載されている。
【００３３】
本発明の一つの特徴は、特定のプリンティングプロセスに合わせて設計者がしきい値を変更することが可能になる点である。しきい値は、選択されたプリンティングプロセス（例えばレーザ又はインクジェットプリンティングプロセス）に最適化させそれに適合させるよう設計者により選択的に変更することが可能である。当業者には自明であるように、低いしきい値はドットのプリントを促し、高いしきい値はドットのプリントを抑制するものとなる。したがって、本発明の利点は、設計者が、本発明により生成されるドットパターンが、意図するマーキング装置（例えばプリンタ）でのプリンティングに適合するものとなるように、しきい値を選択することができることにある。
【００３４】
例えば、レーザプリンティングの場合には、結果的に複数のドットクラスタを生成するハーフトーン化を使用することが好ましい可能性があることは周知である。これを考慮に入れるため、ドットクラスタの形成を促進させるしきい値を選択することができる。これを実施する１つの方法として、本発明で使用すべきしきい値アレイとしてクラスタ化ドット(clustered-dot)スクリーンを使用することが挙げられる。色平滑ディザ（ColorSmooth Dither：ＣＳＤ）スクリーンがドットクラスタを生成するよう設計されている場合には、該ＣＳＤスクリーンを使用することも適当である。グリーンノイズスクリーンの使用もまた適当となり得る。
【００３５】
同様に、分散ドットプリンティング技法がインクジェットプリンティングプロセスに一層適したものとなり得ることが周知である。これを考慮に入れるため、互いに分散したドットからなるパターンの生成を促進させるしきい値を選択することができる。これを実施する１つの方法として、本発明に使用すべきしきい値アレイとしてブルーノイズ又は分散ドットスクリーンを使用することが挙げられる。
【００３６】
好ましくは、以下で詳述するように、ｔ(i,j)は、分散ドット手法の場合にはランダムなしきい値であり、クラスタドット手法の場合には非ランダムなしきい値である。
【００３７】
例えば、CMYKイメージの場合には、色平滑ディザマトリクスを使用してしきい値ｔ(i,j)を生成することができる。色平滑ディザマトリクス及びかかるディザマトリクスを生成するためのプロセスについては、J. Allebach及びQ. Linによる「Joint Design of Dither Matrices for a Set of Colorants」と題する米国特許第5,812,744号に記載されている。CMYKイメージ中の各色平面は、それぞれ別個にハーフトーン化することができ、特定の一平面についてのしきい値ｔ(i,j)は、次の式における対応する色平滑ディザマトリクス要素ｔcsd(i,j)を使用することにより生成することができる。
ｔ(i,j)＝0.3×（128−ｔcsd(i,j)）＋Ｐ(i,j)／２
しきい値は、R. Ulichney著「The Void-and-Cluster Method for Dither Array Generation」（Proceedings, IS&T/ SPIE Symposium on Elec. Imaging Science&Technology，pp155-158，San Jose, CA, February 1993）に記載の技術といった他の技術を使用することにより生成することもできることを理解されたい。
・処理ステップ
図７は、本発明の一実施形態による中間ドットを用いた誤差拡散機構により実行される各ステップを示すフローチャートである。ステップ700で、所与のピクチャレベル（例えばグレーレベル）を有する入力画素（入力ピクセル）を受け取る。ステップ710で、該入力ピクセルのグレーレベルに基づいて再現可能なグレーレベルが生成される。ステップ720で、入力ピクセルのグレーレベルと所与の誤差量（例えば、先行する領域又はピクセル（すなわち既に処理済のピクセル）から伝搬され又は拡散された誤差）とに基づいて補正されたグレーレベルが生成される。ステップ730で、該補正されたグレーレベルがしきい値と所定の関係にあるか否かが判定される。補正されたグレーレベルがしきい値と所定の関係にある場合には、ステップ740で、再現可能なグレーレベル（中間ドット）が出力として提供される。また、補正されたグレーレベルがしきい値と所定の関係にない場合には、ステップ750で、ゼロ値（ドットなし）が出力として提供される。なお、出力グレーレベルが誤差拡散モジュール430に提供されることに留意されたい。また、しきい値は、所定のしきい値又はランダムに生成されたしきい値とすることが可能であることに留意されたい。以下で説明するように、しきい値は、しきい値アレイ（例えばハーフトーンスクリーン）とすることが可能である。
【００３８】
この本発明のハーフトーン化手順は、ゼロ値（ドットなし）又は特定のグレーレベルに対応する中間ドット値の何れか一方である出力ピクセル値が全てのピクセルに割り当てられるまで繰り返される。これが完了すると、そのデータがプリンタに転送され、次いで該プリンタが該出力データに従って様々なサイズのドットを堆積させる。その結果として得られるイメージは、本発明の好ましい実施形態による、望ましくないイメージアーチファクトが実質的に存在しないものとなる。
【００３９】
本発明の中間ドットサイズを用いた誤差拡散の一つの特徴は、グレーレベルが高くなるにつれて、ドットサイズ（又は濃度）が増大すると共に、ドットの数もまた増大することにある。この結果は、効率の良い態様で達成され、コスト効果の高い態様で実施することができる。
【００４０】
この中間ドットを用いた誤差拡散アルゴリズムが、走査された複合文書からグラフィックス及びテキストに至る範囲の入力イメージに適用される場合には、以下の結果が認められる。走査された複合文書の場合、最も顕著な利点は、モアレパターンの大幅な低減にある。またグラフィックス及びテキストイメージの場合には、最も顕著な利点は、滑らかなエッジ及び微細な細い線にある。
【００４１】
図８に示す従来技術によるハーフトーン化方法とは対照的に、本発明は、複数のプリンタドットからなるクラスタに通ずるものではない。そうではなく、本発明のハーフトーン方法は、プリンタに依存して個々のドットのサイズを変更するものである。このため、複数のプリンタドットが共にクラスタ化されることはない。結果的に、プリンタの最大限の細かい再現を実現することができる。更に、本発明のドット分散は、規則正しいものではなく、確率的なものである。このため、本発明のハーフトーン化プロセスは、モアレアーチファクトがより出現し難いものとなる。
・クラスタドットパターンへの拡張
本発明の中間ドットを用いた誤差拡散機構は、特定の用途の場合に一層安定する傾向を有するクラスタ化ドット・ハーフトーンパターンを生成するよう拡張させることができる。この実施形態では、クラスタ化ドット確率的(stochastic)ディザマトリクス（例えばグリーンノイズマスク）をしきい値アレイに使用することにより、最終的なハーフトーンパターンがクラスタ化ドットとなることが促進される。レーザプリンタ等のプリンタの場合には、クラスタ化ドット・ハーフトーンパターンが一層安定したものとなる。
【００４２】
なお、可変出力しきい値モジュール420の効果は、その内部で用いるしきい値アレイ（すなわちｔ(i,j)）を変更することにより変更することが可能である。色平滑ディザ（ＣＳＤ）マトリクスは、分散ドットしきい値アレイの一例である。ＣＳＤアレイでは、互いに数値的に近接したしきい値は空間的に分散しており、このため、可変出力しきい値処理にＣＳＤを使用することにより、プリントされるドットを空間的に分離し分散させることが促進される。マーキング装置（例えばオフィス機器108）が空間的に分離されたドットを安定して描画する能力を有する場合には、分散ドットしきい値アレイが好ましい。これは、該アレイによって更なる細部を描画することが可能となるからである。
【００４３】
しかし、電子写真式（レーザ）プリンタプロセスが空間的に分離したドットを安定して描画することが比較的不可能なものであることは周知である。かかるプロセスで、クラスタ化ドットしきい値アレイを利用することが可能である。クラスタ化ドット・ハーフトーンスクリーンをしきい値に使用することにより、ドットクラスタ（各クラスタは複数のプリンタドットを含む）の形成が促進される。この手法は、レーザプリンティングプロセスに一層適したものである。
【００４４】
上記では、特定の実施形態を参照して本発明を解説した。しかし、本発明のより広い範囲から逸脱することなく様々な変形及び変更を実施することが可能であることは明らかであろう。例えば、本書では、本発明の中間ドットを用いた誤差拡散機構を、主にグレースケールイメージに関して解説した。しかし、本発明の中間ドットを用いた誤差拡散機構をカラーイメージのハーフトーン化に利用できることが当業者には明らかとなろう。例えば、本発明の中間ドットを用いた誤差拡散機構を適用して、異なる色平面（例えば、シアン、マゼンタ、イエロー、及びブラック（CMYK）色平面、又は、赤、緑、青（RGB）色平面）をそれぞれ独立してハーフトーン化することが可能である。したがって、本明細書及び図面は、制限的な意味ではなく例示的な意味で解釈すべきものである。
【図面の簡単な説明】
【００４５】
【図１】本発明の中間ドットを用いた誤差拡散機構を実施することができる例示的なコンピュータシステムを示すブロック図である。
【図２】本発明の中間ドットを用いた誤差拡散機構の例示的なソフトウェアによる一実施形態を示している。
【図３】本発明の中間ドットを用いた誤差拡散機構の例示的なハードウェアによる一実施形態を示している。
【図４】本発明の一実施形態による図１の中間ドットを用いた誤差拡散モジュールを更に詳細に示すブロック図である。
【図５】本発明の代替的な実施形態による図１の中間ドットを用いた誤差拡散モジュールを更に詳細に示すブロック図である。
【図６】本発明の一実施形態による「中間ドットサイズ」対「入力グレーレベル」を示すグラフである。
【図７】本発明の一実施形態による中間ドットを用いた誤差拡散機構により実行される各ステップを示すフローチャートである。
【図８】従来技術によるハーフトーン化システムを示している。
【図１】
2004531129.tif 000004
【図２】
2004531129.tif 000005
【図３】
2004531129.tif 000006
【図４】
2004531129.tif 000007
【図５】
2004531129.tif 000008
【図６】
2004531129.tif 000009
【図７】
2004531129.tif 000010
【図８】
2004531129.tif 000011
【国際公開パンフレット】
2004531129.tif 000012
2004531129.tif 000013
2004531129.tif 000014
2004531129.tif 000015
2004531129.tif 000016
2004531129.tif 000017
2004531129.tif 000018
2004531129.tif 000019
2004531129.tif 000020
2004531129.tif 000021
2004531129.tif 000022
2004531129.tif 000023
2004531129.tif 000024
2004531129.tif 000025
2004531129.tif 000026
2004531129.tif 000027
2004531129.tif 000028
2004531129.tif 000029
2004531129.tif 000030
2004531129.tif 000031
2004531129.tif 000032
2004531129.tif 000033
2004531129.tif 000034
【国際公開パンフレット（コレクトバージョン）】
2004531129.tif 000035
2004531129.tif 000036
2004531129.tif 000037
2004531129.tif 000038
2004531129.tif 000039
2004531129.tif 000040
2004531129.tif 000041
2004531129.tif 000042
2004531129.tif 000043
2004531129.tif 000044
2004531129.tif 000045
2004531129.tif 000046
2004531129.tif 000047
2004531129.tif 000048
2004531129.tif 000049
2004531129.tif 000050
2004531129.tif 000051
2004531129.tif 000052
2004531129.tif 000053
2004531129.tif 000054
2004531129.tif 000055
2004531129.tif 000056
2004531129.tif 000057
2004531129.tif 000058