(57)【要約】      （修正有）【課題】スレショルド・アレイを生成する方法を提供する。【解決手段】（１）値割り当て手段で、１ドットプロファイルの各画素に白黒の一方を割当てるステップ、（２）デジタルフィルタ適用手段で、所定画素にデジタルフィルタをかけた値が所望値と異なるか否かでその画素に割り当てられた値を調整するステップ、（３）実行制御手段で、ドットプロファイル全体がカバーされるまでステップ（２）を繰り返すステップ、（４）実行制御手段で、デジタルフィルタを変更し同じドットプロファイルについてステップ（２）と（３）を繰り返すステップ、（５）実行制御手段で、スレショルド・アレイ内の各ドットプロファイルにステップ（１）〜（４）を繰り返して望まない可視パターンを最小にするドットプロファイルを得るステップ、（６）アセンブル手段で、１組の基準グレイ値のスレショルド・アレイを作るよう複数のドットプロファイルをアセンブルするステップ。【選択図】図３
2005333657.tif 000002
【特許請求の範囲】
【請求項１】
デジタル表示装置のために使用されるスレショルド・アレイを作成する方法であって、該スレショルド・アレイは複数の白または黒の画素から成る複数のドット・プロファイルから成っている方法において、
（１）値割り当て手段により、１つのドット・プロファイルの白または黒とされていない各画素に、白黒２色の内の一方の色を示す値を割当てるステップと、
（２）デジタルフィルタ適用手段により、所定の画素におけるデジタルフィルタをかけた値が当該画素における所望の値と異なるか否かに基づいて、その画素に割り当てられた値を調整するステップと、
（３）実行制御手段により、ドット・プロファイル全体がカバーされるまでそのドット・プロファイルの残りの画素に関してステップ（２）を繰り返すステップと、
（４）実行制御手段により、デジタル・フィルタを変更して前記ドット・プロファイルと同じドット・プロファイルについてステップ（２）と（３）とを繰り返すステップと、
（５）実行制御手段により、前記スレショルド・アレイ内の各ドット・プロファイルについてステップ（１）〜（４）を繰り返して望ましくない可視パターンを最小にするドット・プロファイルを得るステップと、
（６）アセンブル手段により、１組の基準グレイ値からなるスレショルド・アレイを作るよう複数のドット・プロファイルをアセンブルするステップと、
から成るスレショルド・アレイの生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、様々なディジタル表示装置又は印刷装置におけるハーフトーン・イメージの生成に用いるスレショルド・アレイの作成に関する。ディジタル・ハーフトーンは、通常スレショルド・アレイ又はエラー拡散テクニックを用いて行われる。スレショルド・アレイ・テクニックは、高速で、実施し易く、広範囲のハーフトーン・システムに適応する。エラー拡散テクニックは、ハーフトーン・イメージから大規模な人為構造を除去することによって、良好な再生忠実度を達成できるが、多くの処理時間を要し、多くの既存のイメージ・ハーフトーン・システムに用いることができない。今日行われているハーフトーンの多くは、ディジタル・コンピュータ又はその他の特定用途のディジタル・ハードウェアを用いて電子的に行われている。ディジタル・ハーフトーンは、印刷機の原板の作成、電子写真式及びインク・ジェット式卓上プリンタ、コンピュータのＣＲＴ表示装置その他のイメージ装置に用いられている。
【背景技術】
【０００２】
グレイの中間色調を有するイメージは、良く知られたハーフトーンの方法によって、黒又は白の画素を生成できる装置上で再生される。ハーフトーンは、細い黒と白のパターンでグレイの色調を再生し、このパターンにおける全体の領域に対する黒の領域の比がグレイの色調を決定する。黒と白のパターンが細ければ細いほど、見る人は望ましいグレイの色調を知覚し、黒と白のパターンをあまり知覚しない。
【０００３】
スレショルド・アレイによるディジタル・ハーフトーンの方法は良く知られている。スレショルド・アレイによるハーフトーンは、次のステップを用いる。（１）出力装置の各画素で再生されるイメージをサンプリングし、イメージのグレイ値を得る。（２）その画素に対するスレショルド・アレイから基準グレイ値を得る。（３）イメージのグレイ値を基準グレイ値と比較する。（４）この比較の出力を用いて、装置上の画素の色（黒又は白）を決定する。
【０００４】
スレショルド・アレイは、一般に基準グレイ値の矩形のアレイで構成される。この矩形のアレイは、くり返して配置されて、ディジタル出力装置のラスタ（出力領域）をカバーしており、出力装置の各画素は、スレショルド・アレイの配置されたコピーの１つにおける１つの基準グレイ値に正確に対応している。
【０００５】
スレショルド・アレイによるハーフトーンの利点は、１画素当たりに要する計算が少ないことである。２つのグレイ値をフェッチし、それらを比較するだけである。これは、印刷機の原板作成等の高解像度出力装置は、１頁につき５億画素を処理しなければならないので重要である。
【０００６】
スレショルド・アレイによるハーフトーンの別の利点は、ユーザがイメージをハーフトーンを処理するのに用いるスレショルド・アレイを特定させることが可能なディジタル表示装置の設置台数の増大である。従って、このような装置の所有者は、ハードウェアを変えることなくスレショルド・アレイによるハーフトーンを選択することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
スレショルド・アレイによるハーフトーンは、擬似的な従来のスクリーン（網目ガラス）に基づいたハーフトーンに広く用いられている。スクリーンに基づいた方法は、一般に妥当であるが、それに関する問題も常にある。１つの問題は、４つのハーフトーン・イメージを４色印刷のように透明に組み合わせたとき、「モアレ」（斑紋）パターンを除去するため、スクリーンの角度を非常に注意深く制御しなければならないことである。モアレ・パターンは、望ましくない可視的効果を引き起こす。別の問題は、スクリーンによる方法は、小さなドットの、細いけれども規則的な格子をハーフトーンのイメージに生成することである。このドットの配置は、精密な検査で認識でき、元のイメージにはない再生上の産物となる。このような人為的産物は、カラーの再生のように２つ又はそれ以上のスクリーンによるイメージを組み合わせたとき、もっと多く認識される。このようなパターンは、イメージを精密に見るとき、不快感を与える。
【０００８】
ディジタル・ハーフトーン・テクニックの別の相関するグループが、長年の間に開発された。例は、エラー拡散、ＦＭスクリーニング又は確率論的スクリーニングである。これらは、全てやや類似の結果をもたらし、ここでは、全て確率論的スクリーニングと呼ばれる。これらのテクニックでは、半無作為的処理を用いて、非常に小さな、見かけ上ランダムに配置されたドットのパターンを作成し、このとき、これらドット間の平均間隔及び黒対白の全体的密度を精密に制御する。エラー拡散及びスレショルド・アレイによるハーフトーンの概要は、ＭＩＴ出版から１９８７年に発行されたロバート・ウリクニー（Robert Ulichney） による「ディジタル・ハーフトーン（Degital Halftoning）」に見られる。
【０００９】
確率論的ハーフトーンのテクニックは、スレショルド・アレイによるハーフトーンの問題を解決するために部分的に用いることができる。望ましくないドット・パターンは、多く見られず、モアレ・パターンは、かなり低減している。一方、確率論的ハーフトーンのテクニックは、スレショルド・アレイの方法よりも、数倍の計算時間を要し、既存のスレショルド・アレイに基づいた表示装置に確率論的ハーフトーンの方法を適用することは、費用効果が悪い。
【００１０】
このような確率論的ハーフトーンのテクニックの１つは、「ＡＣＭ Transaction of Graphics 」vol.１２、NO.２（１９９３年４月）におけるロバート・ガイスト、ロバート・レイノルズ及びデリル・サグによる「Ａ Markovian Framework for Digital Halftoning （ディジタル・ハーフトーンに関するマルコフ構成）」に記載されている。この記事は、エラー拡散と類似の結果を生ずる無作為処理に基づくハーフトーンについて説明している。この方法の１つの欠点は、これはスレショルド・アレイに基づくものではなく、計算時間が極端にかかることである。更に、ガイスト等の方法は、大きな領域をカバーするようにドット・プロファイルを配置するときに発生するパターンを完全に回避していない。
【００１１】
別の確率論的ハーフトーンのテクニックは、１９９１年サン・ノゼにおけるＳＰＩＥ会議の会報において、ミスタ及びパーカーによる「Digital Halftoning Using a Blue Noise Mask（ブルー・ノイズ・マスクを用いたディジタル・ハーフトーン）」及び１９９２年の「 Raster Imaging and Digital Typography（ラスタ・イメージ及びディジタル・タイポグラフィ）」に関する会議の会報において、ミスタ、ウリクニー及びパーカーによる関連記事「The Construction and Evaluation of HlftonePatterns with Manipulated Power Spectra （操作されたパワー・スペクトルを有するハーフトーン・パターンの構成と評価）」に教示されている。これらの記事において、ミスタ等は、不快なパターンが低減され、所望のグレイ・レベルを再生するドット・プロファイルの構成方法を教示している。ミスタ等は、成分ドット・プロファイルからスレショルド・アレイをアセンブルする具体的方法も説明している。しかし、ミスタ等のプロファイルは、多くのアプリケーションで要求されるようなスムーズさではない。
【課題を解決するための手段】
【００１２】
簡単にいって、本発明は、複数のドット・プロファイルで作られたスレショルド・アレイの生成方法に関する。その際、各ドット・プロファイルは、複数の黒又は白の画素でできており、特定のプロファイルの特定の画素は、黒又は白に限定される。生成されたドット・パターンでは、実質的に不快な可視パターンは見られない。この方法は、１つのドット・プロファイルの限定されていない各画素に１つの値を与える第１のステップで始まる。この値は、黒又は白として変換され得るものである。第２のステップにおいて、ドット・プロファイルの所定領域内の画素値の関数が、所定の所望値と異なっているかどうかに基づいて、所定領域内の特定の画素に割り当てられた値を調整し、ごくわずかの場合に、調整後の値が無調整の値から反対の色に変換できるようにするものである。
【００１３】
この第２のステップは、ドット・プロファイル全体がカバーされるまで、同一ドット・プロファイルの別の所定領域についてくり返される。この第２ステップは、同一ドット・プロファイル内を循環して何回もくり返される。この処理全体は、スレショルド・アレイのドット・プロファイルのそれぞれに対してくり返される。結果のスレショルド・アレイにおけるドット・プロファイルには、不快な可視的パターンはない。
本発明は、比較的小さなスレショルド・アレイを構築する従来技術を改良するもので、エラー拡散によるハーフ・トーンのテクニックと同様の結果を生ずる。
これによって、高速性とスレショルド・アレイに基づいたハーフ・トーンに関するハードウェアの利用性が得られ、併せて確率論的ハーフ・トーンと同様のスクリーニング結果が得られる。
【発明を実施するための最良の形態】
【００１４】
本発明の方法は、いくつかのタイプの計算装置のどれかを用いて実施でき、これらの計算装置には、スキャナ、コンピュータ及びラスタ表示装置が含まれる。本発明の方法の第１のステップは、スレショルド・アレイを準備することである。このスレショルド・アレイは、一般にコンピュータ又は特定用途のディジタル・ハードウェアを用いて計算される。スレショルド・アレイは、基準グレイ値の矩形アレイで構成され、以下に述べるように準備される。スレショルド・アレイは、当業者に良く知られているように、コンピュータに付随した一時的又は永久的記憶装置に保持しても良いし、又は他のコンピュータに分散しても良い。例えば、ネットワーク上に分散するかディスケットで分散しても良い。スレショルド・アレイは、当業者に良く知られた方法で、元のイメージをハーフトーンにするのに用いられる。
【００１５】
本発明のスレショルド・アレイは、多くの「ドット・プロファイル」をアセンブルすることによって生成される。ドット・プロファイルは、０及び１等の２進値のアレイである。これは、スレショルド・アレイと同じ幅と高さを有する。ドット・プロファイルは、一定のグレイ値をハーフトーン化するのにスレショルド・アレイを用いるときに生ずる黒と白の画素のパターンに対応する。スレショルド・アレイは、所与のグレイ値に対して、特定のドット・プロファイルを生成する。通常、スレショルド・アレイを用いてハーフトーン化を行うとき、アレイからドット・プロファイルが生成される。本発明の方法は、所望の１組のドット・プロファイルを用いてこの処理を逆に行い、スレショルド・アレイを用いて一定のグレイ値をハーフトーン化するときに、同一のドット・プロファイルを生成するようなスレショルド・アレイを構成するようにしたものである。スレショルド・アレイをアセンブルするのに用いられる各ドット・プロファイルは、それに関するグレイ値を有する。グレイ値は、スレショルド・アレイと比較したとき、関連するドット・プロファイルを生ずる値である。
【００１６】
もしドット・プロファイルにおける所与の位置における２進値が、特定のグレイ・レベルに対して黒であると、全てのより暗いグレイ・レベルに対応する全てのドット・プロファイルに対して、それと同一の２進値は黒でなければならないので、使用するドット・プロファイルには、一定の制約がある。同様に、ドット・プロファイルの所与の位置における２進値が、所与の中間グレイ値に対して白であると、同一位置の全ての２進値は、より明るいグレイ・レベルのドット・プロファイルに対して白でなければならない。本発明の１つの目的は、このような制約を満足する１組のドット・プロファイルを生成することである。
【００１７】
別の目的は、意図した出力装置上で暗いカラー値及び明るいカラー値に変換するとき、各ドット・プロファイルが、それだけによっても又はそれ自身の他のコピーと共に配置されているときにおいても、可視パターンがない暗いドット及び明るいドットのパターンになり、しかもそのドット・プロファイルに関するカラー値を正確に再生することである。
【００１８】
本発明の方法によるドット・プロファイルの構築は、特定の手順で行われる。関連グレイ値の順序づけが行われ、ドット・プロファイルは、この順序で構成される。この順序づけにおける最初のドット・プロファイルは、乱数又は擬似乱数発生器又はその他の既知の方法を用いて、ドット・プロファイルの各位置に対して−１から１の範囲の乱数又は擬似乱数（以下単に乱数という）を計算することによって構築される。これらの乱数は、スレショルド・アレイの次数と同じ次数の別のアレイにストアされる。このアレイは、図１（Ａ）に示す「状態アレイ」１００と呼ばれる。ドット・プロファイルは、このアレイ内の値の符号を考慮して、この状態アレイから導くことができる。ゼロより小さい状態アレイの値は、対応する２進値０を与え、０以上の状態アレイの値は、２進値１を生成する。これらの値は、図１（Ｂ）のドット・プロファイル２００に示されている。黒いセルは、２進値０を示し、白いセルは２進値１を示す。図１（Ａ）の状態アレイの値はランダムであるので、図１（Ｂ）のドット・プロファイル・アレイの初期値もランダムである。
【００１９】
本発明の方法における次のステップは、フィルタをかけたドット・プロファイル・アレイと呼ばれる実数値の第３のアレイを生成することであり、これは、図１（Ｃ）において、暗い色調で小さな実数値を表し、明るい色調で大きな実数値を表している。このアレイは、ディジタル・フィルタをドット・プロファイルに適用することによって得られる。ディジタル・フィルタは、一般にロー・パス・ガウス・フィルタであり、よって、図１（Ｃ）に示す、フィルタをかけたドット・プロファイルの表現は、ぼかしに対して、ドット・プロファイルがどのように人間には見えるかを示している。
【００２０】
本発明の方法の次のステップでは、ドット・プロファイルに関するグレイ・レベルとフィルタをかけたドット・プロファイル・アレイの値の差に比例する量によって、状態アレイの各値が調整される。後で説明するように、この調整に対して、追加項目を加えても良い。この調整の正味の効果は、フィルタをかけたドット・プロファイルが暗すぎる場合には、状態値は高く調整され、明るすぎる場合には、低く調整されると云うことである。この調整のために、次に状態アレイからドット・プロファイルを得たとき、任意の点での局所的平均グレイ値は、関連グレイ値に近くなる。
【００２１】
上で概説した処理は、何回もくり返され、状態アレイ及び結果的に生じるドット・プロファイルに対してより良い修正が行われる。ある時点以後は、状態アレイに対する修正は、結果のドット・プロファイルに何ら有意差を生じなくなる。この時点で、異なったディジタル・フィルタが用いられ、修正が必要でなくなるまで処理が再度くり返される。多くの異なったディジタル・フィルタが連続して用いられ、スレショルド・アレイが様々な方法で修正される。特に、遮断周波数変動型ロー・パス・フィルタを用いることが有益であることが分かっている。遮断周波数が高いロー・パス・フィルタは、３から５画素のスケールで平均グレイ値の変動を無視するように働くため、初めに用いられる。遮断周波数が低いロー・パス・フィルタは、全体的平均グレイ値が正確であることを保証するように働くため、後で用いられる。少なくとも１つのフィルタが用いられる。フィルタの数には制限はない。
【００２２】
上のステップによって、多くのものの１つである最初のドット・プロファイルが作られる。引き続き次のドット・プロファイルは、同じ方法で作られるが、連続した作成テクニックでは、ドット・プロファイルの様々なエレメントは、すでに作られたドット・プロファイルに従って、黒又は白にとどまるように限定されることがある点が異なる。エレメントが白又は黒に限定されているかどうかに基づいて、限定されたエレメントの状態値を＋１又は−１に維持することによって、本発明の方法は、この制約に対して順応する。これらの限定された状態値に対しては、調整は行われず、これによって、結果のドット・プロファイルは、これらのエレメントに対する限定値を維持する。
【００２３】
新しいドット・プロファイルが、それぞれ完成するにつれて、スレショルド・アレイのエレメントは更新され、新しいドット・プロファイルを含むようになる。
全てのドット・プロファイルが完成された後、スレショルド・アレイもまた完成する。ドット・プロファイルは、注意深く作られ、全ての点において同じ平均グレイ値を生ずるので、結果的にスレショルド・アレイは、望ましくない可視的ドット・パターン又は規則的ドット・パターンを最小にするようにして、平坦なグレイ・イメージやその他のイメージを再生する。
【００２４】
本発明のテクニックは、スレショルド・アレイをコンピュータ・メモリ上に表現する必要がある。これには多くの表現方法があるが、望ましい実施例の方法は、特定の１つを用いる。スレショルド・アレイは、基準グレイ値の矩形アレイで、例えば、幅がＷエレメントで高さがＨエレメントである。各基準グレイ値は、整数で表され、例えば、その範囲は０から２５５である。業界では知られているように、これより大きな又は小さな整数は、特定の利点があれば用いても良い。
【００２５】
基準グレイ値を表す各整数は、最高値を表すのに十分なビットを有するコンピュータ・メモリにストアされる。２５５がその最高値であれば、８ビットが必要で、メモリの単位は８ビット（１バイト）である。以下の説明において、どんなサイズの単位でも良いことは分かっているが、スレショルド・アレイの単位はバイトであると仮定している。メモリにおける基準グレイ値の構成は、アレイのエレメントがコンピュータ・メモリの連続した位置に配置され、列Ｃと行Ｒのエレメントのアドレスが、スレショルド・アレイの基準アドレス＋Ｃ＋（Ｒ×Ｗ）であるような一般的２次元アレイであることが望ましい。
【００２６】
スレショルド・アレイの他に、本発明の方法は、更に３つのアレイを用いる。これらは、状態アレイ、カーネル・アレイ及びフィルタをかけたドット・プロファイル・アレイである。状態アレイは、図１（Ａ）に示すスレショルド・アレイ内の各位置に対する状態値のアレイである。フィルタをかけたドット・プロファイル・アレイは図１（Ｃ）に示されている。カーネル・アレイは、ドット・プロファイルからドット・プロファイル・アレイを得るために用いるディジタル・フィルタに対するコンボリューション・カーネル（convolution kernel）を保持する。コンボリューション・カーネルについては、１９７９年 Prentice Hall発行のケネス・Ｒ・キャスルマンによる有名な参考書「Digital Image Processing（ディジタル・イメージ処理）」に論じられている。
【００２７】
コンピュータの変数名又はＣ言語コードが本文中に参照されているところでは、それは、例えば「code」のようなアルファベット文字列で書かれている。これら３つの追加アレイは、浮動小数点値の２次元アレイとして表されており、そのタイプは、本発明で用いられ、以下に提供されているコンピュータ・コードのＣ言語フラグメントにおいて floatである。これらのアレイの次数は、スレショルド・アレイの次数と同じである。これらのアレイにおけるエレメントの配置は、スレショルド・アレイのエレメントの配置と同じであり、わずかに異なる点は、これらのアレイに浮動小数点値をストアするのに必要なビット数が、スレショルド・アレイの値をストアするのに要する８ビットより多いことである。
【００２８】
従って、２つのアレイの対応するエレメントは、常にアレイの始めから同じエレメント数である。ドット・プロファイルは、図１（Ａ）の状態アレイのエレメントをゼロと比べることによって、そのエレメントが簡単に、いつでも計算できるので、第５のアレイとして明確な形でコンピュータ・メモリにはストアされていないことに留意されたい。
【００２９】
上で述べたアレイは、全てのコードがアクセスできるように、コンピュータ・プログラムの包括的変数であることが望ましい。更に、全てのアレイの次数を与える変数 width及びhightもまた、プログラムに対して包括的である。
【００３０】
表記：      
本発明は、擬似コードのフラグメント及びＣプログラム言語のフラグメントで明記される。擬似コードは、コンピュータ・プログラムの多くのステップの全体的構成を明記する当業者に良く知られた表記法である。擬似コードの構造は、いくつかの個々のステップが何を行うかについての英語の説明である点を除いて、ハイ・レベル・プログラム言語の構造である。擬似コードは、時には、わずらわしいフローチャートの代わりとなる。熟練した実務者に対して役立つなら、擬似コードにおけるこれらの英語の記述に更に説明を加え、適当なＣプログラム言語のコード・フラグメントが与えられる。
【００３１】
Ｃプログラム言語は、恐らく今日用いられている最も共通したプログラム言語であり、当業者に良く知られている。典型的参考書は、１９８４年Prentice-Hall発行のハービソン及びスティールによる「Ｃ： Reference Manual」である。
【００３２】
最上レベルの構成：
コード・フラグメント１は、コンピュータ・プログラムの最上レベルの制御を概説する擬似コードを示す。
コード・フラグメント１：
１．  userParams = user input;
２．  Allocate memory for arrays;
３．  Initialize threshold array to all 0's;
４．  MakeThresholdArray(userParams,0,1); 
５．  Write threshold array out to disk;
【００３３】
ステップ１は、ユーザが特定のパラメータを選択するためのものである。パラメータには次のものが含まれる。すなわち、スレショルド・アレイのサイズ、各ドット・プロファイルに対して各ディジタル・フィルタを適用する回数、適用する異なったディジタル・フィルタの数及びこれらのフィルタの特性である。
ステップ２は、プログラムで用いる様々なアレイに必要なメモリを割り当てるためのものである。これには、スレショルド・アレイ、状態アレイ、カーネル・アレイ及びその他がある。メモリの割り当ては、当業者に良く知られた方法で行われる。
【００３４】
ステップ３は、スレショルド・アレイの内容を全てゼロに初期化するためのものである。
ステップ４は、手順MakeThresholdArrayをユーザが与えたパラメータと共に呼び出し、スレショルド・アレイを計算するためのものである。値０及び１も渡される。これらの値は、グレイ値の全体の範囲についてドット・プロファイルを作ることを示す。
ステップ５は、完成したスレショルド・アレイをディスクに書き込むためのものである。このステップは、もしそのコンピュータ・プログラムがスレショルド・アレイをコンピュータ・メモリから直接用いるハーフトーン・システムの一部であれば、省略できる。  
【００３５】
プログラムの残りの部分は、４つのユニット又は手順に分割される。コンピュータ・プログラムの技術を有するものは、様々な時点で呼び出され同じタスクを実行するコンピュータ命令の組み込みユニットとしての手順に詳しいであろう。近代的プログラム言語によって、別々のコンピュータ・メモリが、１つの手順を起動する度に使用される一時的記憶域として割り当てられる。従って、この自己参照に対する終結条件がある限り、１つの手順がそれ自身を再帰的に呼び出すことができる。
【００３６】
図２は、手順間の全体的流れを示すフローチャートである。メイン・プログラム１０は、MakeThresholdArray手順１２を呼び出し、その手順は、スレショルド・アレイの全体的構築を管理する。そのパラメータは、上で述べたように、メイン・プログラムを通してユーザから得られる。 MakeThresholdArray 手順は、関連するグレイ値についてのドット・プロファイルの計算順序を決定する。それは、MakeDotProfile手順１４を呼び出し、各ドット・プロファイルの実際の構築を実行する。
【００３７】
MakeDotProfile手順１４の目的は、１つのドット・プロファイルを作成し、そのドット・プロファイルからの情報をスレショルド・アレイに入力することである。ドット・プロファイルは、状態アレイ内の値の符号として存在する。MakeDotProfile手順１４は、パラメータとして、作成されるドット・プロファイルに対するグレイ値、構築されつつあるスレショルド・アレイ及びその他後で説明するいくつかのものを有する。この手順は、MakeThresholdArray手順１２の全てのパラメータに対してアクセスできる。MakeDotProfile手順１４は、MakeDigitalFilter手順１６を呼び出すことによって多くのディジタル・フィルタを作成し、ApplyFilter手順１８を呼び出すことによって、状態アレイを通してドット・プロファイルに対する連続した修正を行う。
【００３８】
MakeDigitalFilter 手順１６は、ディジタル・フィルタに対するコンボリューション・カーネルを作成し、それをカーネル・アレイと呼ばれる実数値の２次元アレイにストアする。これは、パラメータとして、コンボリューション・カーネルの様々な特性を記述する数個の浮動小数点値を用いる。この点は、以下のコード・フラグメントに関する詳細な説明に見られる。
【００３９】
ApplyFilter 手順１８は、ディジタル・フィルタをドット・プロファイルに対してくり返し適用し、フィルタをかけた値に基づいて状態アレイに対する修正を行う。これは、パラメータとして、この処理をくり返す回数、ディジタル・フィルタ、状態アレイ及び後で論じるその他の値を用いる。図２に示す４つの手順のそれぞれの詳細な働きについて、以下に説明する。
【００４０】
MakeThresholdArray手順：
MakeThresholdArray手順は、以下のコード・フラグメント２で実行される（ライン番号は、言語部分ではないが、参照のために含まれている）。
【００４１】
コード・フラグメント２：
1．   struct UserParameters;
2．   typedef int Integer;
3．   typedef float Real; 
4．   void MakeThresholdArray(
struct UserParameters *userParams, 
Real lowDotDens, Real highDotDens) 
5．   { 
6.    Real midDens = (lowDotDens + highDotDens)/2;
7.    Real midGray = DotDensToGray(midDens);
8.    Real lowGray = DotDensToGray(lowDotDens); 
9.    Real highGray = DotDensToGray(highDotDens); 
10.   Integer thrshVal = floor(255*midGray) + 1;
11.   Integer lowTVal = floor(255*lowGray) + 1; 
12.   Integer highTVal = floor(255*highGray) + 1; 
13.   if(thrshVal - lowTVal >= 1 && 
highTVal - thrshVal >= 1){
14.       MakeDotProfile( 
userParams, midDens, 
lowTVal, highTVal, thrsVal); 
15.       MakeThresholdArray( 
userParams, lowDotDens, midDens);
16.       MakeThresholdArray( 
userParams, midDens, highDotDens); 
17.       } 
18.   } 
【００４２】
ライン１−３は、このコード・フラグメント及び後で説明するＣ言語のコード・フラグメントで用いられるデータ・タイプを定義する。ライン４は、手順のパラメータを示す。userParamsパラメータは、ユーザによって指定された全てのパラメータを有する構造に対するポインタである。このポインタは、単に他の手順に渡されるもので、別に用いられなければ、この構造の内容は、現時点では考慮する必要はない。LowDotDens及び HighDotDensのパラメータは、その手順がドット・プロファイルを計算するためのドット密度の範囲を指定する。このプログラムにおける「ドット密度」という言葉は、ドット・プロファイル内の全ドットに対する白のドットの比を云う。その手順は、この範囲内のドット密度に対するドット・プロファイルを作成するが、この範囲の終点は含まれない。
【００４３】
特定のドット・プロファイルのドット密度の記述は、スレショルド・アレイからそのドット・プロファイルを抽出するグレイ値の記述から分離される。グレイ値は、２５５を乗ずることによってドット密度から計算され、MakeDotProfileに対して別の値として渡す必要がないと思われるかも知れない。しかし、ハーフトーンに用いられる実際の物理的装置におけるドット利得の現象では、再生されたドット・プロファイルの観察された平均グレイ値は、ドット密度だけから期待されるよりも著しく暗く又は明るくなる。プログラムが、ドット密度の２５５倍と異なる値を指定できるようにすることによって、実際の装置におけるドット利得に対する修正が行える。
【００４４】
このような修正を行う能力は、上のコード・フラグメントのライン７で用いられているDotDensToGray 手順を通してこのコンピュータ・プログラムで実現される。もし修正が必要なければ、この手順は、その引数を単に戻すようにコーディングできる。一方、DotDensToGray は、ドット・プロファイルのドット密度がその装置に表示されると仮定して、特定の装置で観察され、０から１の範囲に正規化された実際のグレイ・レベルを返す転送機能を実行する。この転送機能は、コンピュータ・メモリのテーブルにストアされた値の間に内挿することによって、或いは当業者に良く知られた方法で実行できる。
【００４５】
コード・フラグメント２は、次のように動作する。ライン６は、要求されたドット密度の範囲の中間のドット・プロファイルに対するドット密度を計算する。ライン７、８及び９は、そのドット密度及び要求された範囲の両端のドット密度に対して対応するグレイ値を計算する。ライン１０、１１及び１２は、要求されたドット密度範囲の低、中間及び高位置でのドット・プロファイルに対して、スレショルド・アレイにストアされる値を計算する。ライン１３は、中間のドット・プロファイルに対する閾値が、（整数にまるめたとき）範囲の両端の閾値と異なっているかをチェックする。もし異なっていれば、ライン１４、１５及び１６が実行される。ライン１４は、MakeDotProfile手順を呼び出して、要求された範囲の中間ドット密度に対するドット・プロファイルを作成する。ライン１５及び１６は、MakeThresholdArrayに対する再帰的呼び出しであり、要求された範囲における残りのドット・プロファイルを作成する。
【００４６】
MakeThresholdArray手順を再帰的に実行することによって、ドット・プロファイルが作成される順序ができあがる。この順序づけは、言葉で次のように要約される。先ず、中間ドット密度値１／２に対するドット・プロファイルが作成される。これによって、残りのドット密度値が２つの範囲、すなわち、１／２の両側の範囲に分割される。これらは、範囲全体の時と同様の方法で処理される。すなわち、先ず中間グレイが処理され（これは、低い方の範囲では１／４、上側では３／４である）、これらの両側の小範囲が処理される、等々。この順序づけ（バイナリ・ツリーのプリ・オーダ・トランスバーサルと同等）は、望ましい実施例において良く動作することが分かったけれども、当業者に良く知られたドット密度値の順序づけも十分満足できる。例えば、反復的MakeThresholdArrayの起動が、再帰的起動の代わりに使える。
【００４７】
MakeDotProfileの手順：  
MakeDotProfile手順の動作について説明する。この手順の全体的論理フローは、次の擬似コード・フラグメント３に示される。
【００４８】
コード・フラグメント３：
1.    MakeDotProfile( 
struct UserParams* userParams,
Real dotDens, Integer lowTVal,
Integer highTVal, Integer thrshVal) { 
2.    Initialize state array with random values.
3.    KernelSize = userParams->initialSize; 
4.    while (kernelSize < userParams->finalSize) {
5.         MakeDigitalFilter(kernelSize, dotDens);
6.         ApplyFilter( 
userParams, dotDens, lowTVal, highTVal);
7.         Rescale entries in the state array;
8.         kernelSize = kernelSize * userParams->sizeInc; 
9.         }
10.   Store dot profile info into threshold array;
11.   } 
【００４９】
ライン１は、この手順のパラメータがuserParams、dotDens、lowTVal、highTVal及びThrsVal であることを示す。他の変数、スレショルド・アレイ等、は包括的変数として利用可能である。
【００５０】
これらのパラメータの意味は、次の通りである。userParamsのパラメータは、上で述べたのと同じ意味を有する。DotDens のパラメータは、生成されるドット・プロファイルのドット密度である。thrshValのパラメータは、スレショルド・アレイにストアされ、作成されるドット・プロファイルを表す値である。もしグレイ値thrshValが、結果として生ずるスレショルド・アレイと比較されると、作成されるドット・プロファイルが生ずる。 lowTValのパラメータは、スレショルド・アレイにストアされた最大の値であり、大旨thrsValより小さい。 highTValは、スレショルド・アレイにストアされた最小の値であり、大旨thrshValより大きい。ドット・プロファイルが計算される再帰的順序のために、 lowTVal及びhighTValは、単に計算されるドット密度の現在の範囲の終点に対する閾値である。
【００５１】
コード・フラグメント３の最初のステップ、ライン２は、状態アレイの値を−１から＋１の範囲のランダムな浮動小数点値で初期化するためのものであるが、これは、ドット・プロファイルの対応するエレメントが限定されていないときだけである。もしドット・プロファイルのエレメントが限定されており、そのエレメントが黒に限定されていれば、状態値は−１、白に限定されていれば＋１である。所与のドット・プロファイルのエレメントが限定されているかどうかを判定するために、スレショルド・アレイの対応するエレメントは、lowTVal及びhighTValパラメータと比較される。もしスレショルド・アレイのエレメントが lowRangeより低ければ、ドット・プロファイルのエレメントは黒に限定されており、もし highRangeと等しいかそれより高いと、ドット・プロファイルのエレメントは白に限定されている。それ以外では、ドット・プロファイルのエレメントは限定されていない。
【００５２】
Ｃプログラム言語で書かれた以下のコード・フラグメント４は、この初期化処理の１つの方法を示している。このコード・フラグメントは、次の変数が、実行前に次の値を有すると仮定している。すなわち、thrPtrは、スレショルド・アレイの最初のエレメントのコンピュータ・メモリ内のアドレスであり、thrEndは、スレショルド・アレイの最後のエレメントの直後の最初のバイトのアドレスであり、statePtrは、状態アレイの最初のエレメントのアドレスであり、lowTVal 及びhighTValは、上で述べたパラメータである。
【００５３】
コード・フラグメント４：  
1.    while (thrPtr < thrEnd) { 
2.        Int32 tv = *thrPtr++; 
3.        if (tv < lowTVal) *statePtr = -1; 
4.        else if (tv < tighTVal) { 
5.             *statePtr = (Real)random()/0x3fffffff - 1; 
6.        } else *statePtr = 1; 
7.        ++statePtr; 
8.    } 
【００５４】
このコード・フラグメント４のライン３、５及び６は、エレメントが限定されているか、そしてそれが限定された値にセットされているかについてまとめてテストする。ライン５は、ランダムな限定されない値をセットする。ライン５に用いられている関数randomは、無符号の３２ビットの整数で表される値の範囲のランダム整数を返すＣライブラリ関数である。ヘキサデシマルの定数 ０x３ｆｆｆｆｆｆｆで除し、１を減ずることによって、これは、−１から１の範囲の浮動小数点値に変換される。
【００５５】
上のコード・フラグメントの実行の結果として、状態アレイは、図１（Ａ）の状態アレイ１００として発生する。エレメント１０３及び１０４は、それぞれ白及び黒と限定されたエレメントに対応する。
コード・フラグメント３に戻って、ライン３は、ライン４ないしライン８で構成されるメイン・ループに対する変数kernelSizeを初期化する。変数kernelSizeは、ディジタル・フィルタを実行するために用いられるコンボリューション・カーネルのサイズである。kernelSizeの初期値は、userParams構造のフィールドから得られる。
【００５６】
ライン５は、MakeDigitalFilter 手順を呼び出し、カーネル・アレイに書き込む（fill in）。MakeDigitalFilter 手順には、kernelSize及びDotDensの変数が与えられる。別の実施例では、必要ならuserParams構造にストアされた他のフィールドが渡される。
ライン６は、ApplyFilter 手順を呼び出し、ライン５で作成されたフィルタを用いて状態アレイに対するくり返し修正を行う。
【００５７】
ライン７は、状態アレイの全ての項目のＲＭＳ（二乗平均）を計算し、限定されない画素に対応する全ての項目をこの値の逆数によってスケーリングする。このステップの目的は、状態アレイのＲＭＳ値を１に維持することである。このアレイ内の値は、通常ApplyFilter の呼び出しによって行われる調整後は、小さくなり、これを補償しない限り、メイン・ループの反復実行後、ＲＭＳ値はゼロに非常に近くなり、これによって計算上の数値的不安定が発生する。
【００５８】
ライン８は、カーネル・サイズをユーザによって与えられuserParams構造にストアされた係数で拡大（スケール・アップ）する。この係数は、一般に２から４の範囲である。この係数が小さいと、ドット・プロファイルが外見上ややスムーズになるが、プログラムの実行時間が長くなる。
【００５９】
これによって、この手順のメイン・ループの実行が完了する。この時点で、黒及び白のドットのパターンとして物理的に具現化したときに、不快なパターンがない望ましい特性を有するドット・プロファイルが、状態アレイ内の値の符号によって決定される。ライン１０は、状態アレイのこの情報をスレショルド・アレイに転送する。これは、次のコード・フラグメント５によって実行される。コード・フラグメント５は、次の変数が実行前に次の値を有すると仮定している。すなわち、thrEndは、スレショルド・アレイの最後のエレメントの直後の最初のバイトのアドレスであり、statePtrは、状態アレイの最初のエレメントのアドレスであり、thrshVal、lowTVal及びhighTValは、上で述べたパラメータである。
【００６０】
コード・フラグメント５：
1.    while (thrPtr < thrEnd) { 
2.         Int32 tv = *thrPtr;
3.         if (lowTVal <= tv && tv < highTVal) {
4.              if (*statePtr > 0)
5.                   *thrshPtr = thrshVal;
6.         }
7.         ++thrPtr;
8.         ++statePtr;
9.    } 
【００６１】
コード・フラグメント５は、現在のスレショルド・アレイの各エレメントを検査する。もしスレショルド・アレイの所与の位置の値が、lowTVal及びhighTVal パラメータの間であれば、状態アレイの対応する値の符号によって、スレショルド・アレイのその位置は、そのままにしておかれるか又はthrshValにセットされる。スレショルド・アレイのその他の値は、そのままである。lowTValとhighTVal の間の値を有するスレショルド・アレイの位置は、限定されていないドット・プロファイルのエレメントに正確に対応する。スレショルド・アレイのこれらの特定のエレメントが変わることによってのみでは、ドット・プロファイルの限定されたエレメントは変更されない。ドット・プロファイルの限定されないエレメントに対応するスレショルド・アレイのエレメントは、全て値lowTVal を有する。これは、現時点迄に、lowTValとhighTVal の値がスレショルド・アレイにストアされていないためである。この時点以降は、thrsValがlowTValより大きく、highTVal より小さいので、スレショルド・アレイをthrsValと比較した結果、限定されないエレメントに対しては、状態アレイによって示される黒と白の同一パターンになる。これでMakeDotProfile手順の説明を完了する。
【００６２】
MakeDigitalFilterの手順：
ディジタル・フィルタは、コンピュータ・メモリ内でスレショルド・アレイと同じ次数の浮動小数点値の２次元アレイとして表される。このアレイの項目は、実行されるフィルタのコンボリューション・カーネルを表す。コンボリューション・カーネルの中心を座標（０，０）に位置づけることは、一般的で望ましいやり方である。本発明の望ましいコンボリューション・カーネルは、その中心の周囲にゼロでない項目を有するので、ゼロでない項目がコンボリューション・カーネルを表す２次元アレイの負のインデックスにストアされる必要がある。負のインデックスは、通常Ｃプログラム言語に許されていないので、この制限は、負の列インデックスにアレイの幅を加え、負の行インデックスにアレイの高さを加えることによって克服される。従って、インデックスは、アレイの幅（又は高さ）の倍数まで正しく、負のインデックスは回避される。幅又は高さの倍数による項目のオフセットは、コンボリューション・カーネルを用いるときに考慮される。
【００６３】
コンボリューション・カーネルの幅及び高さが、それぞれスレショルド・アレイの幅及び高さの半分以下であれば、この調整はうまく働く。しかし、もしこの条件が満足されなければ、その左右（又は上下）の端からのコンボリューション・カーネルのエレメントは、アレイ内の同一位置にマップする。これは、異なる側からの寄与分を一緒に加え、その値をアレイにストアすることによって解決される。
【００６４】
本発明で用いられるコンボリューション・カーネルは、ガウス・カーネルである。すなわち、カーネル・アレイの行Ｒ及び列Ｃのエレメントは、次の式で与えられる。
exp(-(C*C + D*D)/(radius*radius))
ここで、この式は、Ｃプログラム言語のシンタックスで表されており、ｅｘｐは指数関数、radiusは、カーネルの値が１／ｅ＝．３６７９に落ちるときの半径である。この式が本発明において良く働くことは分かっているけれども、当業者は、他の式も使えることが分かるであろう。例えば、中心からの指数関数的減衰を有する放射波動関数を上の式に加え、ハーフ・トーンのドット・サイズ及び間隔を制御することもできる。
【００６５】
この成分に関する式は、
wfactor*cos(sqrt(C*C+D*D)/wl)*exp(-sqrt(C*C+D*D)*decay) である。
ここで、COSはコサイン関数、wlは所望のドット間隔の６．２８倍、 sqrtは平方根、decayは、どの程度厳格にドット間隔を制御するかのものであり、wfactorは、放射波動関数の全体的影響を制御するものである。その他の式も、有用なコンボリューション・カーネルを様々な状況で提供する。
MakeDigitalFilter 手順によって実行される実際のステップは、次のＣ言語のコード・フラグメント６で表される。次の変数はこの手順のパラメータである。すなわち、kernelSizeは、コンボリューション・カーネルの所望の半径であり、dotDens は、作成されるドット・プロファイルに対するドット密度である。包括的変数kernelは、カーネル・アレイの最初のエレメントのアドレスである。
【００６６】
コード・フラグメント６：
1.    Real density =
dotDens <= .5 ? dotDens : 1 - dotDens;   
2.    Real kernelArea = 3.14159*kernelSize*kernelSize;
3.    Real alpha = 2*3.14159*deosity/kernelArea;
4.    Real cutOffError = 1e-4;
5.    Integer gRadius = ceil(sgrt(-log(cutOffError)/alpha));
6.    Real gaussSum = 0;
7.    Integer ix, iy; 
8.    SetToZero(kernel, width, height); 
9.    for (iy = -gRadius; iy <= gRadius; iy++) {
10.       for (ix= -gRadius; ix <= gRadius; ix++) { 
11.            Integer distSqrd = ix*ix + iy*iy;
12.            Real g = exp(-alpha*distSqrd); 
13.            Integer ic = ix; 
14.            Integer ir = iy; 
15.            while (ic < 0) ic += width;
16.            while (ir < 0) ir += height; 
17.            while (ic > width) ic -= width;
18.            while (ir > height) ir -= height;
19.            kernel[ic + ir*width] += g;
20.            gaussSum += g; 
21.       } 
22.   } 
【００６７】
ライン１は、いわゆる「少数派密度」を計算し、これは、他の色のドットに対して少数派である色のドットの密度である。少数派密度は、少数の色の平均ドット間隔と逆比例関係にある。カーネル・サイズは、少数色ドットの間隔と等しい係数によって拡大されるべきであることが分かっている。これはライン３で考慮されている。ライン２は、少数派の間隔を考慮に入れる前に、コンボリューション・カーネルの所望の領域を計算する。ライン３は、指数関数で用いられる乗数alpha を計算し、所望のサイズのコンボリューション・カーネルを達成する。ガウス・カーネルは、中心から評価されていくにつれてゼロに近づく（実際にゼロに到達しない）ので、その先はガウス・カーネルがゼロであると想定されるカット・オフ・ポイントを設定しなければならない。ライン４は、このカット・オフの設定から許される最小誤差を１０−4と指定する。
【００６８】
ライン５は、ライン４の誤差制限を達成するために、カーネルが評価される半径を計算する。ライン６は、この手順の完了時点でコンボリューション・カーネルの項目の合計となる包括変数gaussSumを初期化する。この値は、プログラムで後に用いられる。ライン８は、コンボリューション・カーネルの全ての項目をゼロに初期化する。ライン９、１０及び１１は、値の計算が必要なコンボリューション・カーネルの全ての位置を列挙する二重ループを設定する。変数ix及びiyは、所与の位置の座標である。ライン１１及び１２は、値 gすなわち所与の位置に対するガウス関数を計算する。ライン１３から１８は、変数ix及びiyからカーネル・アレイの行及び列インデックスを計算する。この計算によって、負のix及びiyが突き止められ、又はカーネル・アレイのサイズを越えるix及びiyが突き止められる。ライン１９は、計算されたガウス関数を、カーネル・アレイの適当な項目に加える。ライン２０は、計算されたガウス関数を変数gaussSumに加える。
【００６９】
これでMakeDigitalFilter 手順の説明を完了する。この手順の完了時点で、カーネル・アレイには、所望のコンボリューション・カーネルがストアされており、
gaussSum変数には、カーネル・アレイの項目の合計がストアされている。
【００７０】
ApplyFilter手順：
この手順の全体的論理は、次の擬似コード・フラグメント７で与えられる。略語「フィルタをかけたアレイ」は、以下「フィルタをかけたドット・プロファイル」のアレイを指す。
【００７１】
コード・フラグメント７：
1.    ApplyFilter(
struct UserParms* userParams, 
Real dotDens, Integer lowTVal, Integer highTVal)
{ 
2.        for (count=0; count < userParams->nIters; count++) {
3.             Initialize the filtered array; 
4.             Apply digital filter to filtered array;
5.             Adjust values in state array,
based on filtered array 
6.             }
7.        } 
8.    } 
【００７２】
擬似コード・フラグメント７のライン１は、この手順のユーザ指定のパラメータuserParamsを示し、これには、所望のドット・プロファイルの白いドットの密度であるdotDens及びMakeDigitalFilter手順の場合と同じ意味を有するlowTVal 及びhighTValが含まれる。
ライン２は、ライン３から７で構成されるこの手順のメイン・ループの実行を制御する。
このループは、userParams->nIters回くり返される。これは、ユーザによって指定されたユーザ・パラメータ構造のフィールドである。
【００７３】
ライン３は、この手順のメイン・ループの最初のステップである。このステップにおいて、フィルタをかけたアレイは、初期化されて（フィルタをかけていない）ドット・プロファイルを表す。このアレイ内の位置は、現在のドット・プロファイルにおいて黒のドットは０に、現在のドット・プロファイルにおいて白のドットは１にセットされる。現在のドット・プロファイルは、状態アレイの値の符号から計算される。より具体的には、状態アレイがゼロかそれ以上の位置では、１がフィルタをかけたアレイに入れられ、他の位置では、０が入れられる。
【００７４】
図１（Ｂ）において、フィルタをかけたアレイ２００は、この時点でのフィルタをかけたアレイの状態を示している。白い四角は、フィルタをかけたアレイにストアされた値１に対応し、暗いグレイの四角は、値０に対応する。このアレイのエレメント２０１（値０を有する）は、図１（Ａ）に示す状態アレイ１００のエレメント１０１（負値を有する）に対応する。同様に、図１（Ｂ）のドット・プロファイル・アレイのエレメント２０２（値１を有する）は、図１（Ａ）の状態アレイのエレメント１０２（正値を有する）に対応する。
【００７５】
ライン４は、フィルタをかけたアレイにディジタル・フィルタを適用する。互いに隣り合わせて配置したときに生ずるドット・プロファイルの端における継ぎ目の出現を除去するために、コンボリューション・カーネルとフィルタをかけつつあるアレイの両方が、あたかも「ラップ・アラウンド」しているようにフィルタリングが行われる。別の言い方をすれば、各アレイの左端が右端と連続していると考えられ、同様に、各アレイの上端が下端と連続していると考えられる。コンボリューション・カーネルは、この目的に沿うように準備されている。これは、モジュール化された計算を用いてフィルタをかけたアレイで実行でき、所与のアレイの外側に来るアレイ・インデックスを現存する範囲の値に持ってくることができる。
【００７６】
このコンセプトを更に説明するために、変数filteredValue において、変数kx及びkyで与えられる座標でフィルタをかけた値を計算する、次のコード・フラグメント８を考える。
【００７７】
コード・フラグメント８：
1.    Real filteredValue = 0; 
2.    Integer ix, iy; 
3.    for (iy = -gRadius; iy <= gRadius; iy++) {
4.         for (ix= -gRadius; ix <= gRadius; ix++) {
5.              filteredValue +=
fltPtr[ix + width*iy]* 
kernel[(kx - ix) + width*(ky - iy)]; 
6.         }
7.    } 
【００７８】
ライン５は、位置（ix,iy）でのフィルタをかけたアレイの項目に、カーネル・アレイの位置（kx-ix,ky-iy） を乗ずる。後者の式の座標は、恐らくある値のkx及びkyに対する第１の座標に関して、０からwidth-1 の許された範囲の外側であり、０からhigh+-1 の許された範囲の外側である。これは、モジュール化された計算が入ってくるところである。上のコード・フラグメントは、修正され、これを次のように突き止める。
【００７９】
コード・フラグメント９：
1.    Real filteredValue = 0; 
2.    Integer ix, iy; 
3.    for (iy = -gRadius; iy <= gRadius; iy++) {
4.         for (ix= -gRadius; ix <= gRadius; ix++) {
5.              Integer rx = kx - ix; 
6.              Integer ry = ky - iy; 
7.              while (rx < 0) rx += width; 
8.              while (ry < 0) ry += height;
9.              while (rx > width) rx -= width; 
10.             while (ry > height) ry -= height; 
11.             filteredValue +=
fltPtr[ix + width*iy]* 
kernel[rx + width*ry]; 
12.        }
13.   } 
【００８０】
ライン５から１０は、kx-kyを０からwidthの範囲へ、ky-iyを０からhightの範囲へ持ってくるモジュール化された算術演算を行う。
コード・フラグメント９は、どのようにしてディジタル・フィルタリングが行われるかも示しているので、その他の説明が整えられている。２つの入れ子になった（ネスト）ループ（ライン３及び４）は、-gradiusから gradiusの範囲のインデックスを列挙する。これは、MakeDigitalFilter 手順に関して前に説明したコード・フラグメント６のライン５で計算された値と同じである。カーネル・アレイの項目は、この半径の外側ではゼロであるので、この半径の区画内についてのみこれらの計算を行うことによって、時間を節約できる。しかし、gradius がスレショルド・アレイの次数の１／２又はそれ以上であり得る。この場合には、列挙の限界は、水平方向に０からwidth-1、垂直方向に０からhight-1でなければならないであろう。上のコード・フラグメントは、フィルタをかけた値を、位置（kx,ky）についてのみ計算する。アレイ全体をフィルタにかけるため、kx 及びkyの全ての値に対してこのコードを実行しなければならない。フィルタをかけた値は、計算の都度フィルタをかけたアレイに戻されてストアされてはならない。その代わりに、それらは一時的アレイにストアされ、全ての計算が終わった後にコピーされ、戻されなければならない。
【００８１】
上のコード・フラグメントは、kx、kyで与えられる位置についての半径gradius の円内で、フィルタをかけていない値の加重加算を取る。この和は、カーネル・アレイの値の和で除するとき、位置（kx, ky）を中心とする円内の画素の加重平均グレイ値を与える。円の中心に近い値は、多く加重される。遠く離れた値ほど少なく加重される。正確な加重は、上の式によるコンボリューション・カーネルによって決定される。従って、コンボリューション・カーネル及び所定のエレメントの位置によって決まる領域において、このフィルタをかける動作によって、所与のフィルタをかけていないエレメントが、元のフィルタをかけない（すなわちドット・プロファイル）値の加重和で置き換えられる。ガウス・カーネルの場合、この領域は円であり、この円のサイズは、MakeDotProfile手順で計算されるkernelSizeパラメータによって変化する。
【００８２】
ディジタル・フィルタリング動作を実行する別の方法は、２次元高速フーリエ変換すなわち「２Ｄ  ＦＦＴ」によるものである。２Ｄ  ＦＦＴは、当業者に良く知られたステップを用いて実行される。例えば、２Ｄ  ＦＦＴに対するはっきりしたコンピュータ・コードは、１９８６年ケンブリッジ大学出版からのプレス等による「Numerical Recipes （数値処理法）」に与えられている。
【００８３】
フィルタ動作は、２Ｄ  ＦＦＤを用いて次のステップで行われる。第１に、フィルタをかけたアレイに初期ストアされたフィルタをかけていない値の２Ｄ  ＦＦＴは、計算されて複素数の第１の補助アレイにストアされる。第２に、カーネル・アレイの２Ｄ  ＦＦＴは、計算されて複素数の第２の補助アレイにストアされる。（このステップは、カーネル・アレイがループ内では変わらないため、メインループの外側で実行される。）第３に、第１の補助アレイの各エレメントに、第２の補助アレイの対応する位置にあるエレメントを乗ずる。最終ステップは、第１の補助アレイに逆２Ｄ  ＦＦＴを実行し、その結果をフィルタをかけたアレイに戻して再びストアする。これによってフィルタ処理が完了する。コンボリューション・カーネルのサイズ（ gRadius）が大きいとき、この方法は、コード・フラグメント９及び次の節で説明されている方法よりも速い。更に、ＦＦＴの方法は、自動的に所望のラップ・アラウンドの効果をシミュレートする。
【００８４】
フィルタリングの後、フィルタをかけたアレイは、図１（Ｃ）のドット・プロファイル３００として現れる。ここで、暗いグレイは０に近い値に、明るいグレイは、コンボリューション・カーネルの全項目の和であるgausSum に近い値に対応する。例えば、このフィルタをかけたドット・プロファイル・アレイのエレメント３０３は、部分２０４Ａ及び２０４Ｂからなる一つの円に含まれる図１（Ｂ）のフィルタをかけていないドット・プロファイル・アレイ２００のエレメントの加重加算である。円は２つの部分、左の２０４Ａ及び右の２０４Ｂに分割されている。これは、どのようにディジタル・フィルタ計算のラップ・アラウンド機構が動作するかを示している。もし円が一体となった円であれば、円の左端は、アレイの左端を超えてしまう。これは、左端に負のｘ座標を有する円内の位置に対応する。上のモジュール化された計算コードは、アレイの幅を加えることによって、これらの負のインデックスを訂正し、部分円２０４Ｂで示すように、アレイの右側に来るようにしている。
【００８５】
擬似コード・フラグメント７は状態アレイの値の調整を行う。この調整の正確なメカニズムは、次のＣ言語のコード・フラグメント１０で述べられている。次の変数が、このコード・フラグメントの実行前に設定されていると仮定する。すなわち、thrsPtr はスレショルド・アレイの最初のエレメントに対するポインタであり、endThrshは、スレショルド・アレイの最後を越えた最初のエレメントに対するポインタであり、statePtrは状態アレイの最初のエレメントに対するポインタであり、filtPtr は、フィルタをかけたアレイの最初のエレメントに対するポインタである。変数lowTVal、highTVal及びDotDensはこの手順のパラメータである。変数gaussSumは、上のMakeDigitalFilter 手順で計算されたものである。
【００８６】
コード・フラグメント１０：
1.    const Real kGamma = .968; 
2.    const Real hyst = 0.1;
3.    Real grayAvg = gaussSum*dotDens;
4.    while (thrsPtr < endThrsh) {
5.         Real tv = *thrsPtr++;
6.         if (fLowTVal <= tv && tv < fHighTVal) {
7.              Real state = *statePtr; 
8.              Real dotColor = state < 0 ? 0 : 1;
9.              Real adjustment = 
grayAvg - *filtPtr + 
hyst*(2*dotColor - 1); 
10.             *statePtr = 
kGamma*state + (1-kGamma)*adjustment*(10/gaussSum); 
11.        }
12.        ++statePtr;
13.        ++filtPtr; 
14.   } 
【００８７】
このコード・フラグメントのライン１及び２は、後でこのコードで用いる定数kGamma及びhyst を定義する。ライン３は、変数grayAvgを計算する。この変数は、所望のドット密度が全領域で達成されたとき、フィルタをかけたアレイの各エレメントにストアされる値である。このエレメントは、その所望のドット密度にコンボリューション・カーネルの項目の和を乗ずることによって計算される。ライン４は、ライン５から１３で構成されるループを制御する。このループは、スレショルド・アレイの各位置を列挙する。
【００８８】
ライン５は、スレショルド・アレイの現在の位置から値をフェッチし、変数tvにストアする。ライン６は、tvについてチェックし、ドット・プロファイルの対応する位置が限定されていないかどうか調べ、もしそうなら、ライン７から１０が実行される。ライン７は、状態アレイの現在の位置から値をフェッチし、state にストアする。ライン８は、現在の位置のフィルタをかけていないドット・プロファイルの値を計算し、DotColorにストアする。
【００８９】
ライン９は、現在の位置での状態アレイに対する調整を計算する。この調整は２つの部分からなる。第１の部分は、所望のフィルタをかけた値と実際のフィルタをかけた値の差、grayAvg-*filtPtrである。この調整部分は、暗すぎるドット・プロファイルの領域を明るくし、その逆も行う修正作用を構成する。第２の調整部分は、hyst*(2*dotColor -1)であり、白いドットを白く、黒いドットを黒く維持しようとする保守的作用を構成する。変数hystは、この作用の大きさを制御する履歴定数である。
この修正作用の必要性は明白である。これは、暗すぎたり、明るすぎたりするドット・プロファイルの領域をならし、従って最終的に不快なパターンがないドット・プロファイルを生成する。
【００９０】
保守的作用は、もっと微妙である。保守的作用の１つの目的は、反復修正を一定の値に収束させるためのものである。従って、この手順のメイン・ループの１回のくり返しで、ドット・プロファイルを修正する可能性は、ドット・プロファイルをそれが次のループで、前にあった場所に修正して戻されることによってのみ避けられる。
【００９１】
保守的作用の第２の目的は、修正作用によってオーバーライドされないとき、状態アレイの元の値をできるだけ無傷のまま保持することである。状態アレイがランダム値で初期化され、このランダム作用を最終的ドット・プロファイルのドット配置に保持することが望ましい。ランダム・ドット配置によって、ドット・プロファイルにおける不快なパターン及びドット・パターンを重ねることによって生ずる斑紋のパターンが減少する。保守的作用に対する更に別の利点は、いくつかの異なったディジタル・フィルタが用いられたとき、最初のフィルタによって行われた有益な作業が、後のフィルタを適用することによって取り消されないことである。
【００９２】
修正作用と保守的作用は、対立した数の量である。一般に修正作用は、特定の画素の周囲のドット・プロファイルのエレメントの加重加算の誤差が変数hystより大きいとき、成功する。
もし状態アレイが、ランダム・パターン以外のパターンで初期化されると、保守的作用は、そのパターンをできるだけ保持し、修正作用は、ドット・プロファイルの平均グレイ値に対する修正を行うことに留意されたい。これは、複数の同一でないハーフトーンのセルがスレショルド・アレイに含まれるときに発生するドット・プロファイルのスムージングのために役立つ。この場合、初期のパターンは、従来のスクリーニングのように、ハーフトーン・ドットのアレイである。従って、本発明は、ランダム・スレショルド・アレイと同様、スレショルド・アレイからの別のタイプのパターンを除去するのにも役立つ。
【００９３】
ライン１０は、今行われた調整に従って、状態アレイの値を修正する。これは、状態アレイの値を調整された現在の値の加重平均に設定することによって行われる。adjustmentは、１０／gaussSum倍され、大きなコンボリューション・カーネルについて発生するadjustmentの大きな値を打ち消すことに留意されたい。このようにして、状態アレイの値は、メイン・ループを何回も反復することによって、調整の方向に徐々に調整される。これは、状態アレイの多くのエレメントが、メイン・ループの１回のくり返しで符号を変えないようにするために必要である。これは、この手順のイメージ・ループが実行されるにつれて、状態アレイの値が安定した値に収束することを保証する。
【００９４】
ドット・プロファイルにおける画素が黒で、フィルタをかけたアレイで計算された平均が「明るすぎ」であると、調整は、ドット・プロファイルにおける画素は、黒にとどまることにも留意されたい。同じことは、平均が「暗すぎ」の領域における白い画素についても云える。暗すぎる領域における黒又は明るすぎる領域における白の画素のみが変わり得る。また、限定されていない画素のみが変わりうる。これらの画素のうち、上の調整によって、状態アレイの対応するエレメントが符号を変えるわずかな部分のみが選択されて、その色を逆にする。状態アレイにおける初期値はランダムであるので、この選択は、決定論的成分に加えてランダム成分を有する。
【００９５】
ドット利得パターンを防止するための修正：
上で説明した方法は、ドット利得が良く制御されたディジタル出力装置で良く動作することが分かっている。ドット利得は、中心のドットを囲むドットの色が、その中心のドットの色に影響を与える物理現象である。理想的ディジタル出力装置では、各ドットの色は、このような影響からは全く独立している。しかも、多くの実際の装置は、この理想を達成できない。ドット利得によって、ドットのグループの実際の平均グレイ値において、上のプログラムで計算された理論的値からの実質的変化が生ずる。従って、ApplyFilter におけるコードの修正作用は、ドット利得のために、グレイ値の差を修正できないかも知れない。ドット利得の局所的変動によって、ある種の出力装置上に不快なパターンが生じ得る。
【００９６】
上の手順に対するいくつかの小さな修正によって、この問題が矯正できる。第１の修正は、コード・フラグメント３のライン６におけるApplyFilter に対する第１の呼び出しの後、第２の呼び出しを挿入することである。このラインをライン６．５と呼ぶ。２つの呼び出しは、第５のパラメータを有し、これは、第１の呼び出しでは０、第２の呼び出しでは１である。コード・フラグメント７におけるApplyFilter は、この第５のパラメータをライン１に追加する必要がある（以下のコード・フラグメント１１参照）。最終的修正は、１つのステップが、コード・フラグメント７のライン３と４の間に挿入されることである。これによって、一般的出力装置のドット利得がモデル化される。
【００９７】
基本的に、３種類のドット利得がある。すなわち、黒のドット利得、白のドット利得、又は両方である。これらの全タイプは、黒いドット利得に対する１つのパラメータ、白いドット利得に対する１つのパラメータによってモデル化される。ドット利得モデル化コードは、以下のようにフィルタをかけたアレイのエレメントを修正する。黒（０）のエレメントは、白のドット利得係数に対して、水平又は垂直に隣接する白い画素の数を乗じたものを加えることによって増分する。白（１）のエレメントは、黒のドット利得係数に対して、水平又は垂直に隣接する黒い画素の数を乗じたものを減ずることによって減分する。本発明は、例えば、白のドット利得係数０（すなわち白のドット利得はない）及び黒のドット利得係数０．１２を用いる。
【００９８】
ドット利得モデル化計算は、図３（Ａ）に示されている。エレメント４０６は、図のように９つの画素に囲まれた仮定の白い画素である。画素４０６の黒のドット利得は、水平又は垂直に隣接する黒い画素を数えることによって計算される。３つの画素４０２、４０３及び４０４がそれである。画素４０１は黒であるが、これは対角線上に隣接しているのであって、水平又は垂直方向でないので数えない。画素４０５は水平に隣接しているが、これは白であり、これも数えない。
【００９９】
従って、合計のドット利得は、黒のドット利得パラメータ（０．１２）の３倍すなわち０．３６である。この値を白の画素（以前は１）から減ずることによって、図３（Ｂ）の中央の画素４０６Ａに示すように、最終値０．６４を生ずる。もし画素４０６が黒であると、黒のドット利得に対する調整はない。
【０１００】
図３Ｃは、仮定の画素４０９に対する白のドット利得計算を示す。この場合、水平又は垂直に１つの隣接する白の画素４０８があり、合計の白のドット利得は、１に白のドット利得パラメータ０．１２を乗じて、０．１２を生ずる。この値は、図３（Ａ）の黒い画素４０６の値０に加えられ、図３（Ｄ）の画素４０９Ａに示すように最終値０．１２を生ずる。もし画素４０９が白であれば、白のドット利得調整があるであろう。
【０１０１】
これらの修正されたエレメントは、補助アレイにストアされ、全ての値の計算ができたとき、フィルタをかけたアレイにコピー・バックされる。一度このモデル化のコードが実行されると、フィルタをかけたアレイのエレメントは、通常通りフィルタをかけられる。調整ステップ（コード・フラグメント７のライン５）が実行されるとき、グレイ値の完全な平均とは対照的に、モデル化されたドット利得に基づいてドット・プロファイルに対して修正が行われる。MakeDotProfileに対する修正された擬似コードは次の通りである。
【０１０２】
コード・フラグメント１１：
1.    MakeDotProfile( 
struct UserParams* userParams, 
Real dotDens, Integer lowTVal, 
Integer highTVal, Integer thrshVal) {
2.    Initialize state array with random values.
3.    kernelSize = userParams->initialSize; 
4.    while (kernelSize < userParams->finalSize) {
5.         MakeDigitalFilter(kernelSize, dotDens);
6.         ApplyFilter( 
userParams, dotDens, lowTVal, highTVal, 0); 
6.5        ApplyFilter( 
userParams, dotDens, lowTVal, highTVaal, 1);
7.         Rescale entries in the state array;
8.         kernelSize = kernelSize * userParams->sizeInc; 
9.              } 
10.   Sotre dot profile info into threshold array;
11.   } 
修正されたApplyFilterに対する擬似コードを次に示す。
【０１０３】
コード・フラグメント１２：
ApplyFilterに対する修正された擬似コードは、次の通りである。
1.    ApplyFilter(
struct UserParams* userParams, 
Real dotDens, Integer lowTVal, Integer highTVal, 
Integer modelDotGain)
{ 
2.         for (count=0; count < userParams->nIters; count++) { 
3.              Initialize the filterad array;
3.1             if (modelDotGain > 0) 
3.2                  ModelDotGain;
4.              Apply digital filter to filtered array; 
5.              Adjust valuse in state array, 
based on filtered array 
6.              } 
7.         }
8.    } 
【０１０４】
ドット利得モデル化コードの実行は、第５のパラメータによって制御されることに留意されたい。従って、コード・フラグメント３のライン６からのApplyFilter に対する第１の呼び出しでは、ドット利得モデル化コードは実行されず、第２の呼び出しで実行される。これによって、ドット利得が出力装置上に存在する場合と存在しない場合の両方について、スムージングのためにドット・プロファイルを交替して調整できる。この交替のテクニックによって、ドット利得が高い装置と低い装置の両方で、所与のドット・プロファイルに関して生ずるパターンを低減する。
【０１０５】
所与の装置のドット利得の実際の量が、温度や湿度のような環境ファクタによって変動し、しばしばユーザのコントロール外であるため、これは重要である。ドット利得があるときにも、ないときにもスムーズに見えるドット・プロファイルを作ることによって、このドット・プロファイルは、ドット利得パラメータの範囲で、装置上に良く再生されることが分かっている。
【０１０６】
ドット利得のモデル化を、ApplyFilterに対する１回目の呼び出しでオンにし、２回目の呼び出しでオフにすることが時として有利である。ApplyFilter 手順のメイン・ループを連続して通る間にドット利得のモデル化をオン、オフすることもときには有利である。モデル化をオン、オフするその他の手順を用いることもできる。
殆ど又は全くドット利得がない装置に対するスレショルド・アレイを生成するとき、全てのドット利得修正を排除することによって優れた結果が得られることも分かっている。
【０１０７】
本発明のテクニックを用いて、不快なパターンがないドット・プロファイルが生成される。それらは、継ぎ目なしに配列され、所望のドット密度で構築される。更に、ドット・プロファイルは、あるエレメントが黒のままであり、他が白のままであるような制限付きで生成される。相応する制限を有する複数のこのようなドット・プロファイルは、元のグレイ値と比較して、要素であるドット・プロファイルを生ずる１つのスレショルド・アレイにアセンブルされる。このようなスレショルド・アレイは、様々なディジタル表示装置に用いることができ、不快なパターンがなく、斑紋効果のない優れたハーフトーンを達成できる。更に、ドット・プロファイル自体は、ディジタル表示装置上に平坦なグレイ階調を再生する必要があるとき、役立つ。
【０１０８】
本発明の説明を、ディジタル・コンピュータで動作するプログラムについて行ったが、当業者は、特定用途のディジタル・ハードウェア等の他の実施も可能であることが分かるであろう。更に、コンピュータ・プログラムの説明は、多くの場合、黒と白のドットを生ずるディジタル表示装置を想定している。しかし、当業者は、同じテクニックが固定色セット又は固定グレイ階調のセットを再生するディジタル表示装置に適用できることが分かるであろう。
当業者には理解できるように、上に説明した装置及び方法に対する変更は、本発明の精神と範囲からはずれることなく、熟練した実務者によって成されることが可能であり、本発明は以下の特許請求の範囲に限定されるべきである。
【図面の簡単な説明】
【０１０９】
【図１】（Ａ）、（Ｂ），（Ｃ）は、本発明に用いられる様々な２次元アレイと、本発明の方法における特定の時点でのこれらアレイの相互関係を図表形式に示す。
【図２】本発明の方法で用いられる様々な手順の間の制御の全体的流れを示すフローチャートである。
【図３】ドット・プロファイルの仮定した区画におけるドット利得を示す図である。
【符号の説明】
【０１１０】
１００  状態アレイ
２００  関連ドット・プロファイル
３００  フィルタをかけたドット・プロファイル
【図１】
2005333657.tif 000003
【図２】
2005333657.tif 000004
【図３】
2005333657.tif 000005