JPH0870384A - スレショルド・アレイ及びその生成方法 - Google Patents

Abstract

(57)【要約】 【目的】 スレショルド・アレイを生成する方法を提供
する。 【構成】（１）１つのドット・プロファイルの各限定さ
れていない画素に対して黒又は白として変換可能な値を
割り当てるステップと、（２）ドット・プロファイルの
所定の領域内の画素の値の関数が、予め定められた所望
値と異なっているかどうかに基づいて、上記所定の領域
内の特定の画素に対して割り当てられた上記値を調整
し、何分の１かの場合に、上記調整された値が無調整の
値から反対の色に変換できるようにするステップと、
（３）ドット・プロファイルの全体がカバーされるまで
ステップ（２）をドット・プロファイルの別の所定領域
に対してくり返すステップと、スレショルド・アレイ内
のドット・プロファイルのそれぞれに対して（１）から
（３）のステップをくり返すステップとからなる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、様々なディジタル表示
装置又は印刷装置におけるハーフトーン・イメージの生
成に用いるスレショルド・アレイの作成に関する。ディ
ジタル・ハーフトーンは、通常スレショルド・アレイ又
はエラー拡散テクニックを用いて行われる。スレショル
ド・アレイ・テクニックは、高速で、実施し易く、広範
囲のハーフトーン・システムに適応する。エラー拡散テ
クニックは、ハーフトーン・イメージから大規模な人為
構造を除去することによって、良好な再生忠実度を達成
できるが、多くの処理時間を要し、多くの既存のイメー
ジ・ハーフトーン・システムに用いることができない。
今日行われているハーフトーンの多くは、ディジタル・
コンピュータ又はその他の特定用途のディジタル・ハー
ドウェアを用いて電子的に行われている。ディジタル・
ハーフトーンは、印刷機の原板の作成、電子写真式及び
インク・ジェット式卓上プリンタ、コンピュータのＣＲ
Ｔ表示装置その他のイメージ装置に用いられている。

【０００２】

【従来の技術】グレイの中間色調を有するイメージは、
良く知られたハーフトーンの方法によって、黒又は白の
画素を生成できる装置上で再生される。ハーフトーン
は、細い黒と白のパターンでグレイの色調を再生し、こ
のパターンにおける全体の領域に対する黒の領域の比が
グレイの色調を決定する。黒と白のパターンが細ければ
細いほど、見る人は望ましいグレイの色調を知覚し、黒
と白のパターンをあまり知覚しない。

【０００３】スレショルド・アレイによるディジタル・
ハーフトーンの方法は良く知られている。スレショルド
・アレイによるハーフトーンは、次のステップを用い
る。（１）出力装置の各画素で再生されるイメージをサ
ンプリングし、イメージのグレイ値を得る。（２）その
画素に対するスレショルド・アレイから基準グレイ値を
得る。（３）イメージのグレイ値を基準グレイ値と比較
する。（４）この比較の出力を用いて、装置上の画素の
色（黒又は白）を決定する。

【０００４】スレショルド・アレイは、一般に基準グレ
イ値の矩形のアレイで構成される。この矩形のアレイ
は、くり返して配置されて、ディジタル出力装置のラス
タ（出力領域）をカバーしており、出力装置の各画素
は、スレショルド・アレイの配置されたコピーの１つに
おける１つの基準グレイ値に正確に対応している。

【０００５】スレショルド・アレイによるハーフトーン
の利点は、１画素当たりに要する計算が少ないことであ
る。２つのグレイ値をフェッチし、それらを比較するだ
けである。これは、印刷機の原板作成等の高解像度出力
装置は、１頁につき５億画素を処理しなければならない
ので重要である。

【０００６】スレショルド・アレイによるハーフトーン
の別の利点は、ユーザがイメージをハーフトーンを処理
するのに用いるスレショルド・アレイを特定させること
が可能なディジタル表示装置の設置台数の増大である。
従って、このような装置の所有者は、ハードウェアを変
えることなくスレショルド・アレイによるハーフトーン
を選択することができる。

【０００７】

【発明が解決しようとする課題】スレショルド・アレイ
によるハーフトーンは、擬似的な従来のスクリーン（網
目ガラス）に基づいたハーフトーンに広く用いられてい
る。スクリーンに基づいた方法は、一般に妥当である
が、それに関する問題も常にある。１つの問題は、４つ
のハーフトーン・イメージを４色印刷のように透明に組
み合わせたとき、「モアレ」（斑紋）パターンを除去す
るため、スクリーンの角度を非常に注意深く制御しなけ
ればならないことである。モアレ・パターンは、望まし
くない可視的効果を引き起こす。別の問題は、スクリー
ンによる方法は、小さなドットの、細いけれども規則的
な格子をハーフトーンのイメージに生成することであ
る。このドットの配置は、精密な検査で認識でき、元の
イメージにはない再生上の産物となる。このような人為
的産物は、カラーの再生のように２つ又はそれ以上のス
クリーンによるイメージを組み合わせたとき、もっと多
く認識される。このようなパターンは、イメージを精密
に見るとき、不快感を与える。

【０００８】ディジタル・ハーフトーン・テクニックの
別の相関するグループが、長年の間に開発された。例
は、エラー拡散、ＦＭスクリーニング又は確率論的スク
リーニングである。これらは、全てやや類似の結果をも
たらし、ここでは、全て確率論的スクリーニングと呼ば
れる。これらのテクニックでは、半無作為的処理を用い
て、非常に小さな、見かけ上ランダムに配置されたドッ
トのパターンを作成し、このとき、これらドット間の平
均間隔及び黒対白の全体的密度を精密に制御する。エラ
ー拡散及びスレショルド・アレイによるハーフトーンの
概要は、ＭＩＴ出版から１９８７年に発行されたロバー
ト・ウリクニー（Robert Ulichney） による「ディジタ
ル・ハーフトーン（Degital Halftoning）」に見られ
る。

【０００９】確率論的ハーフトーンのテクニックは、ス
レショルド・アレイによるハーフトーンの問題を解決す
るために部分的に用いることができる。望ましくないド
ット・パターンは、多く見られず、モアレ・パターン
は、かなり低減している。一方、確率論的ハーフトーン
のテクニックは、スレショルド・アレイの方法よりも、
数倍の計算時間を要し、既存のスレショルド・アレイに
基づいた表示装置に確率論的ハーフトーンの方法を適用
することは、費用効果が悪い。

【００１０】このような確率論的ハーフトーンのテクニ
ックの１つは、「ＡＣＭ Transaction of Graphics 」v
ol.１２、NO.２（１９９３年４月）におけるロバート・
ガイスト、ロバート・レイノルズ及びデリル・サグによ
る「Ａ Markovian Frameworkfor Digital Halftoning
（ディジタル・ハーフトーンに関するマルコフ構成）」
に記載されている。この記事は、エラー拡散と類似の結
果を生ずる無作為処理に基づくハーフトーンについて説
明している。この方法の１つの欠点は、これはスレショ
ルド・アレイに基づくものではなく、計算時間が極端に
かかることである。更に、ガイスト等の方法は、大きな
領域をカバーするようにドット・プロファイルを配置す
るときに発生するパターンを完全に回避していない。

【００１１】別の確率論的ハーフトーンのテクニック
は、１９９１年サン・ノゼにおけるＳＰＩＥ会議の会報
において、ミスタ及びパーカーによる「Digital Halfto
ning Using a Blue Noise Mask（ブルー・ノイズ・マス
クを用いたディジタル・ハーフトーン）」及び１９９２
年の「 Raster Imaging and Digital Typography（ラス
タ・イメージ及びディジタル・タイポグラフィ）」に関
する会議の会報において、ミスタ、ウリクニー及びパー
カーによる関連記事「The Construction and Evaluatio
n of HlftonePatterns with Manipulated Power Spectr
a （操作されたパワー・スペクトルを有するハーフトー
ン・パターンの構成と評価）」に教示されている。これ
らの記事において、ミスタ等は、不快なパターンが低減
され、所望のグレイ・レベルを再生するドット・プロフ
ァイルの構成方法を教示している。ミスタ等は、成分ド
ット・プロファイルからスレショルド・アレイをアセン
ブルする具体的方法も説明している。しかし、ミスタ等
のプロファイルは、多くのアプリケーションで要求され
るようなスムーズさではない。

【００１２】

【課題を解決するための手段】簡単にいって、本発明
は、複数のドット・プロファイルで作られたスレショル
ド・アレイの生成方法に関する。その際、各ドット・プ
ロファイルは、複数の黒又は白の画素でできており、特
定のプロファイルの特定の画素は、黒又は白に限定され
る。生成されたドット・パターンでは、実質的に不快な
可視パターンは見られない。この方法は、１つのドット
・プロファイルの限定されていない各画素に１つの値を
与える第１のステップで始まる。この値は、黒又は白と
して変換され得るものである。第２のステップにおい
て、ドット・プロファイルの所定領域内の画素値の関数
が、所定の所望値と異なっているかどうかに基づいて、
所定領域内の特定の画素に割り当てられた値を調整し、
ごくわずかの場合に、調整後の値が無調整の値から反対
の色に変換できるようにするものである。

【００１３】この第２のステップは、ドット・プロファ
イル全体がカバーされるまで、同一ドット・プロファイ
ルの別の所定領域についてくり返される。この第２ステ
ップは、同一ドット・プロファイル内を循環して何回も
くり返される。この処理全体は、スレショルド・アレイ
のドット・プロファイルのそれぞれに対してくり返され
る。結果のスレショルド・アレイにおけるドット・プロ
ファイルには、不快な可視的パターンはない。本発明
は、比較的小さなスレショルド・アレイを構築する従来
技術を改良するもので、エラー拡散によるハーフ・トー
ンのテクニックと同様の結果を生ずる。これによって、
高速性とスレショルド・アレイに基づいたハーフ・トー
ンに関するハードウェアの利用性が得られ、併せて確率
論的ハーフ・トーンと同様のスクリーニング結果が得ら
れる。

【００１４】

【実施例】本発明の方法は、いくつかのタイプの計算装
置のどれかを用いて実施でき、これらの計算装置には、
スキャナ、コンピュータ及びラスタ表示装置が含まれ
る。本発明の方法の第１のステップは、スレショルド・
アレイを準備することである。このスレショルド・アレ
イは、一般にコンピュータ又は特定用途のディジタル・
ハードウェアを用いて計算される。スレショルド・アレ
イは、基準グレイ値の矩形アレイで構成され、以下に述
べるように準備される。スレショルド・アレイは、当業
者に良く知られているように、コンピュータに付随した
一時的又は永久的記憶装置に保持しても良いし、又は他
のコンピュータに分散しても良い。例えば、ネットワー
ク上に分散するかディスケットで分散しても良い。スレ
ショルド・アレイは、当業者に良く知られた方法で、元
のイメージをハーフトーンにするのに用いられる。

【００１５】本発明のスレショルド・アレイは、多くの
「ドット・プロファイル」をアセンブルすることによっ
て生成される。ドット・プロファイルは、０及び１等の
２進値のアレイである。これは、スレショルド・アレイ
と同じ幅と高さを有する。ドット・プロファイルは、一
定のグレイ値をハーフトーン化するのにスレショルド・
アレイを用いるときに生ずる黒と白の画素のパターンに
対応する。スレショルド・アレイは、所与のグレイ値に
対して、特定のドット・プロファイルを生成する。通
常、スレショルド・アレイを用いてハーフトーン化を行
うとき、アレイからドット・プロファイルが生成され
る。本発明の方法は、所望の１組のドット・プロファイ
ルを用いてこの処理を逆に行い、スレショルド・アレイ
を用いて一定のグレイ値をハーフトーン化するときに、
同一のドット・プロファイルを生成するようなスレショ
ルド・アレイを構成するようにしたものである。スレシ
ョルド・アレイをアセンブルするのに用いられる各ドッ
ト・プロファイルは、それに関するグレイ値を有する。
グレイ値は、スレショルド・アレイと比較したとき、関
連するドット・プロファイルを生ずる値である。

【００１６】もしドット・プロファイルにおける所与の
位置における２進値が、特定のグレイ・レベルに対して
黒であると、全てのより暗いグレイ・レベルに対応する
全てのドット・プロファイルに対して、それと同一の２
進値は黒でなければならないので、使用するドット・プ
ロファイルには、一定の制約がある。同様に、ドット・
プロファイルの所与の位置における２進値が、所与の中
間グレイ値に対して白であると、同一位置の全ての２進
値は、より明るいグレイ・レベルのドット・プロファイ
ルに対して白でなければならない。本発明の１つの目的
は、このような制約を満足する１組のドット・プロファ
イルを生成することである。

【００１７】別の目的は、意図した出力装置上で暗いカ
ラー値及び明るいカラー値に変換するとき、各ドット・
プロファイルが、それだけによっても又はそれ自身の他
のコピーと共に配置されているときにおいても、可視パ
ターンがない暗いドット及び明るいドットのパターンに
なり、しかもそのドット・プロファイルに関するカラー
値を正確に再生することである。

【００１８】本発明の方法によるドット・プロファイル
の構築は、特定の手順で行われる。関連グレイ値の順序
づけが行われ、ドット・プロファイルは、この順序で構
成される。この順序づけにおける最初のドット・プロフ
ァイルは、乱数又は擬似乱数発生器又はその他の既知の
方法を用いて、ドット・プロファイルの各位置に対して
−１から１の範囲の乱数又は擬似乱数（以下単に乱数と
いう）を計算することによって構築される。これらの乱
数は、スレショルド・アレイの次数と同じ次数の別のア
レイにストアされる。このアレイは、図１（Ａ）に示す
「状態アレイ」１００と呼ばれる。ドット・プロファイ
ルは、このアレイ内の値の符号を考慮して、この状態ア
レイから導くことができる。ゼロより小さい状態アレイ
の値は、対応する２進値０を与え、０以上の状態アレイ
の値は、２進値１を生成する。これらの値は、図１
（Ｂ）のドット・プロファイル２００に示されている。
黒いセルは、２進値０を示し、白いセルは２進値１を示
す。図１（Ａ）の状態アレイの値はランダムであるの
で、図１（Ｂ）のドット・プロファイル・アレイの初期
値もランダムである。

【００１９】本発明の方法における次のステップは、フ
ィルタをかけたドット・プロファイル・アレイと呼ばれ
る実数値の第３のアレイを生成することであり、これ
は、図１（Ｃ）において、暗い色調で小さな実数値を表
し、明るい色調で大きな実数値を表している。このアレ
イは、ディジタル・フィルタをドット・プロファイルに
適用することによって得られる。ディジタル・フィルタ
は、一般にロー・パス・ガウス・フィルタであり、よっ
て、図１（Ｃ）に示す、フィルタをかけたドット・プロ
ファイルの表現は、ぼかしに対して、ドット・プロファ
イルがどのように人間には見えるかを示している。

【００２０】本発明の方法の次のステップでは、ドット
・プロファイルに関するグレイ・レベルとフィルタをか
けたドット・プロファイル・アレイの値の差に比例する
量によって、状態アレイの各値が調整される。後で説明
するように、この調整に対して、追加項目を加えても良
い。この調整の正味の効果は、フィルタをかけたドット
・プロファイルが暗すぎる場合には、状態値は高く調整
され、明るすぎる場合には、低く調整されると云うこと
である。この調整のために、次に状態アレイからドット
・プロファイルを得たとき、任意の点での局所的平均グ
レイ値は、関連グレイ値に近くなる。

【００２１】上で概説した処理は、何回もくり返され、
状態アレイ及び結果的に生じるドット・プロファイルに
対してより良い修正が行われる。ある時点以後は、状態
アレイに対する修正は、結果のドット・プロファイルに
何ら有意差を生じなくなる。この時点で、異なったディ
ジタル・フィルタが用いられ、修正が必要でなくなるま
で処理が再度くり返される。多くの異なったディジタル
・フィルタが連続して用いられ、スレショルド・アレイ
が様々な方法で修正される。特に、遮断周波数変動型ロ
ー・パス・フィルタを用いることが有益であることが分
かっている。遮断周波数が高いロー・パス・フィルタ
は、３から５画素のスケールで平均グレイ値の変動を無
視するように働くため、初めに用いられる。遮断周波数
が低いロー・パス・フィルタは、全体的平均グレイ値が
正確であることを保証するように働くため、後で用いら
れる。少なくとも１つのフィルタが用いられる。フィル
タの数には制限はない。

【００２２】上のステップによって、多くのものの１つ
である最初のドット・プロファイルが作られる。引き続
き次のドット・プロファイルは、同じ方法で作られる
が、連続した作成テクニックでは、ドット・プロファイ
ルの様々なエレメントは、すでに作られたドット・プロ
ファイルに従って、黒又は白にとどまるように限定され
ることがある点が異なる。エレメントが白又は黒に限定
されているかどうかに基づいて、限定されたエレメント
の状態値を＋１又は−１に維持することによって、本発
明の方法は、この制約に対して順応する。これらの限定
された状態値に対しては、調整は行われず、これによっ
て、結果のドット・プロファイルは、これらのエレメン
トに対する限定値を維持する。

【００２３】新しいドット・プロファイルが、それぞれ
完成するにつれて、スレショルド・アレイのエレメント
は更新され、新しいドット・プロファイルを含むように
なる。全てのドット・プロファイルが完成された後、ス
レショルド・アレイもまた完成する。ドット・プロファ
イルは、注意深く作られ、全ての点において同じ平均グ
レイ値を生ずるので、結果的にスレショルド・アレイ
は、望ましくない可視的ドット・パターン又は規則的ド
ット・パターンを最小にするようにして、平坦なグレイ
・イメージやその他のイメージを再生する。

【００２４】本発明のテクニックは、スレショルド・ア
レイをコンピュータ・メモリ上に表現する必要がある。
これには多くの表現方法があるが、望ましい実施例の方
法は、特定の１つを用いる。スレショルド・アレイは、
基準グレイ値の矩形アレイで、例えば、幅がＷエレメン
トで高さがＨエレメントである。各基準グレイ値は、整
数で表され、例えば、その範囲は０から２５５である。
業界では知られているように、これより大きな又は小さ
な整数は、特定の利点があれば用いても良い。

【００２５】基準グレイ値を表す各整数は、最高値を表
すのに十分なビットを有するコンピュータ・メモリにス
トアされる。２５５がその最高値であれば、８ビットが
必要で、メモリの単位は８ビット（１バイト）である。
以下の説明において、どんなサイズの単位でも良いこと
は分かっているが、スレショルド・アレイの単位はバイ
トであると仮定している。メモリにおける基準グレイ値
の構成は、アレイのエレメントがコンピュータ・メモリ
の連続した位置に配置され、列Ｃと行Ｒのエレメントの
アドレスが、スレショルド・アレイの基準アドレス＋Ｃ
＋（Ｒ×Ｗ）であるような一般的２次元アレイであるこ
とが望ましい。

【００２６】スレショルド・アレイの他に、本発明の方
法は、更に３つのアレイを用いる。これらは、状態アレ
イ、カーネル・アレイ及びフィルタをかけたドット・プ
ロファイル・アレイである。状態アレイは、図１（Ａ）
に示すスレショルド・アレイ内の各位置に対する状態値
のアレイである。フィルタをかけたドット・プロファイ
ル・アレイは図１（Ｃ）に示されている。カーネル・ア
レイは、ドット・プロファイルからドット・プロファイ
ル・アレイを得るために用いるディジタル・フィルタに
対するコンボリューション・カーネル（convolution ke
rnel）を保持する。コンボリューション・カーネルにつ
いては、１９７９年 Prentice Hall発行のケネス・Ｒ・
キャスルマンによる有名な参考書「Digital Image Proc
essing（ディジタル・イメージ処理）」に論じられてい
る。

【００２７】コンピュータの変数名又はＣ言語コードが
本文中に参照されているところでは、それは、例えば
「code」のようなアルファベット文字列で書かれてい
る。これら３つの追加アレイは、浮動小数点値の２次元
アレイとして表されており、そのタイプは、本発明で用
いられ、以下に提供されているコンピュータ・コードの
Ｃ言語フラグメントにおいて floatである。これらのア
レイの次数は、スレショルド・アレイの次数と同じであ
る。これらのアレイにおけるエレメントの配置は、スレ
ショルド・アレイのエレメントの配置と同じであり、わ
ずかに異なる点は、これらのアレイに浮動小数点値をス
トアするのに必要なビット数が、スレショルド・アレイ
の値をストアするのに要する８ビットより多いことであ
る。

【００２８】従って、２つのアレイの対応するエレメン
トは、常にアレイの始めから同じエレメント数である。
ドット・プロファイルは、図１（Ａ）の状態アレイのエ
レメントをゼロと比べることによって、そのエレメント
が簡単に、いつでも計算できるので、第５のアレイとし
て明確な形でコンピュータ・メモリにはストアされてい
ないことに留意されたい。

【００２９】上で述べたアレイは、全てのコードがアク
セスできるように、コンピュータ・プログラムの包括的
変数であることが望ましい。更に、全てのアレイの次数
を与える変数 width及びhightもまた、プログラムに対
して包括的である。

【００３０】表記： 本発明は、擬似コードのフラグメ
ント及びＣプログラム言語のフラグメントで明記され
る。擬似コードは、コンピュータ・プログラムの多くの
ステップの全体的構成を明記する当業者に良く知られた
表記法である。擬似コードの構造は、いくつかの個々の
ステップが何を行うかについての英語の説明である点を
除いて、ハイ・レベル・プログラム言語の構造である。
擬似コードは、時には、わずらわしいフローチャートの
代わりとなる。熟練した実務者に対して役立つなら、擬
似コードにおけるこれらの英語の記述に更に説明を加
え、適当なＣプログラム言語のコード・フラグメントが
与えられる。

【００３１】Ｃプログラム言語は、恐らく今日用いられ
ている最も共通したプログラム言語であり、当業者に良
く知られている。典型的参考書は、１９８４年Prentice
-Hall発行のハービソン及びスティールによる「Ｃ： Re
ference 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をユーザが与えたパラメ
ータと共に呼び出し、スレショルド・アレイを計算する
ためのものである。値０及び１も渡される。これらの値
は、グレイ値の全体の範囲についてドット・プロファイ
ルを作ることを示す。ステップ５は、完成したスレショ
ルド・アレイをディスクに書き込むためのものである。
このステップは、もしそのコンピュータ・プログラムが
スレショルド・アレイをコンピュータ・メモリから直接
用いるハーフトーン・システムの一部であれば、省略で
きる。

【００３５】プログラムの残りの部分は、４つのユニッ
ト又は手順に分割される。コンピュータ・プログラムの
技術を有するものは、様々な時点で呼び出され同じタス
クを実行するコンピュータ命令の組み込みユニットとし
ての手順に詳しいであろう。近代的プログラム言語によ
って、別々のコンピュータ・メモリが、１つの手順を起
動する度に使用される一時的記憶域として割り当てられ
る。従って、この自己参照に対する終結条件がある限
り、１つの手順がそれ自身を再帰的に呼び出すことがで
きる。

【００３６】図２は、手順間の全体的流れを示すフロー
チャートである。メイン・プログラム１０は、MakeThre
sholdArray手順１２を呼び出し、その手順は、スレショ
ルド・アレイの全体的構築を管理する。そのパラメータ
は、上で述べたように、メイン・プログラムを通してユ
ーザから得られる。 MakeThresholdArray 手順は、関連
するグレイ値についてのドット・プロファイルの計算順
序を決定する。それは、MakeDotProfile手順１４を呼び
出し、各ドット・プロファイルの実際の構築を実行す
る。

【００３７】MakeDotProfile手順１４の目的は、１つの
ドット・プロファイルを作成し、そのドット・プロファ
イルからの情報をスレショルド・アレイに入力すること
である。ドット・プロファイルは、状態アレイ内の値の
符号として存在する。MakeDotProfile手順１４は、パラ
メータとして、作成されるドット・プロファイルに対す
るグレイ値、構築されつつあるスレショルド・アレイ及
びその他後で説明するいくつかのものを有する。この手
順は、MakeThresholdArray手順１２の全てのパラメータ
に対してアクセスできる。MakeDotProfile手順１４は、
MakeDigitalFilter手順１６を呼び出すことによって多
くのディジタル・フィルタを作成し、ApplyFilter手順
１８を呼び出すことによって、状態アレイを通してドッ
ト・プロファイルに対する連続した修正を行う。

【００３８】MakeDigitalFilter 手順１６は、ディジタ
ル・フィルタに対するコンボリューション・カーネルを
作成し、それをカーネル・アレイと呼ばれる実数値の２
次元アレイにストアする。これは、パラメータとして、
コンボリューション・カーネルの様々な特性を記述する
数個の浮動小数点値を用いる。この点は、以下のコード
・フラグメントに関する詳細な説明に見られる。

【００３９】ApplyFilter 手順１８は、ディジタル・フ
ィルタをドット・プロファイルに対してくり返し適用
し、フィルタをかけた値に基づいて状態アレイに対する
修正を行う。これは、パラメータとして、この処理をく
り返す回数、ディジタル・フィルタ、状態アレイ及び後
で論じるその他の値を用いる。図２に示す４つの手順の
それぞれの詳細な働きについて、以下に説明する。

【００４０】MakeThresholdArray手順：MakeThresholdA
rray手順は、以下のコード・フラグメント２で実行され
る（ライン番号は、言語部分ではないが、参照のために
含まれている）。

【００４１】

【００４２】ライン１−３は、このコード・フラグメン
ト及び後で説明するＣ言語のコード・フラグメントで用
いられるデータ・タイプを定義する。ライン４は、手順
のパラメータを示す。userParamsパラメータは、ユーザ
によって指定された全てのパラメータを有する構造に対
するポインタである。このポインタは、単に他の手順に
渡されるもので、別に用いられなければ、この構造の内
容は、現時点では考慮する必要はない。LowDotDens及び
HighDotDensのパラメータは、その手順がドット・プロ
ファイルを計算するためのドット密度の範囲を指定す
る。このプログラムにおける「ドット密度」という言葉
は、ドット・プロファイル内の全ドットに対する白のド
ットの比を云う。その手順は、この範囲内のドット密度
に対するドット・プロファイルを作成するが、この範囲
の終点は含まれない。

【００４３】特定のドット・プロファイルのドット密度
の記述は、スレショルド・アレイからそのドット・プロ
ファイルを抽出するグレイ値の記述から分離される。グ
レイ値は、２５５を乗ずることによってドット密度から
計算され、MakeDotProfileに対して別の値として渡す必
要がないと思われるかも知れない。しかし、ハーフトー
ンに用いられる実際の物理的装置におけるドット利得の
現象では、再生されたドット・プロファイルの観察され
た平均グレイ値は、ドット密度だけから期待されるより
も著しく暗く又は明るくなる。プログラムが、ドット密
度の２５５倍と異なる値を指定できるようにすることに
よって、実際の装置におけるドット利得に対する修正が
行える。

【００４４】このような修正を行う能力は、上のコード
・フラグメントのライン７で用いられているDotDensToG
ray 手順を通してこのコンピュータ・プログラムで実現
される。もし修正が必要なければ、この手順は、その引
数を単に戻すようにコーディングできる。一方、DotDen
sToGray は、ドット・プロファイルのドット密度がその
装置に表示されると仮定して、特定の装置で観察され、
０から１の範囲に正規化された実際のグレイ・レベルを
返す転送機能を実行する。この転送機能は、コンピュー
タ・メモリのテーブルにストアされた値の間に内挿する
ことによって、或いは当業者に良く知られた方法で実行
できる。

【００４５】コード・フラグメント２は、次のように動
作する。ライン６は、要求されたドット密度の範囲の中
間のドット・プロファイルに対するドット密度を計算す
る。ライン７、８及び９は、そのドット密度及び要求さ
れた範囲の両端のドット密度に対して対応するグレイ値
を計算する。ライン１０、１１及び１２は、要求された
ドット密度範囲の低、中間及び高位置でのドット・プロ
ファイルに対して、スレショルド・アレイにストアされ
る値を計算する。ライン１３は、中間のドット・プロフ
ァイルに対する閾値が、（整数にまるめたとき）範囲の
両端の閾値と異なっているかをチェックする。もし異な
っていれば、ライン１４、１５及び１６が実行される。
ライン１４は、MakeDotProfile手順を呼び出して、要求
された範囲の中間ドット密度に対するドット・プロファ
イルを作成する。ライン１５及び１６は、MakeThreshol
dArrayに対する再帰的呼び出しであり、要求された範囲
における残りのドット・プロファイルを作成する。

【００４６】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. }

【００４９】ライン１は、この手順のパラメータがuser
Params、dotDens、lowTVal、highTVal及びThrsVal であ
ることを示す。他の変数、スレショルド・アレイ等、は
包括的変数として利用可能である。

【００５０】これらのパラメータの意味は、次の通りで
ある。userParamsのパラメータは、上で述べたのと同じ
意味を有する。DotDens のパラメータは、生成されるド
ット・プロファイルのドット密度である。thrshValのパ
ラメータは、スレショルド・アレイにストアされ、作成
されるドット・プロファイルを表す値である。もしグレ
イ値thrshValが、結果として生ずるスレショルド・アレ
イと比較されると、作成されるドット・プロファイルが
生ずる。 lowTValのパラメータは、スレショルド・アレ
イにストアされた最大の値であり、大旨thrsValより小
さい。 highTValは、スレショルド・アレイにストアさ
れた最小の値であり、大旨thrshValより大きい。ドット
・プロファイルが計算される再帰的順序のために、 low
TVal及びhighTValは、単に計算されるドット密度の現在
の範囲の終点に対する閾値である。

【００５１】コード・フラグメント３の最初のステッ
プ、ライン２は、状態アレイの値を−１から＋１の範囲
のランダムな浮動小数点値で初期化するためのものであ
るが、これは、ドット・プロファイルの対応するエレメ
ントが限定されていないときだけである。もしドット・
プロファイルのエレメントが限定されており、そのエレ
メントが黒に限定されていれば、状態値は−１、白に限
定されていれば＋１である。所与のドット・プロファイ
ルのエレメントが限定されているかどうかを判定するた
めに、スレショルド・アレイの対応するエレメントは、
lowTVal及びhighTValパラメータと比較される。もしス
レショルド・アレイのエレメントが lowRangeより低け
れば、ドット・プロファイルのエレメントは黒に限定さ
れており、もし highRangeと等しいかそれより高いと、
ドット・プロファイルのエレメントは白に限定されてい
る。それ以外では、ドット・プロファイルのエレメント
は限定されていない。

【００５２】Ｃプログラム言語で書かれた以下のコード
・フラグメント４は、この初期化処理の１つの方法を示
している。このコード・フラグメントは、次の変数が、
実行前に次の値を有すると仮定している。すなわち、th
rPtrは、スレショルド・アレイの最初のエレメントのコ
ンピュータ・メモリ内のアドレスであり、thrEndは、ス
レショルド・アレイの最後のエレメントの直後の最初の
バイトのアドレスであり、statePtrは、状態アレイの最
初のエレメントのアドレスであり、lowTVal 及びhighTV
alは、上で述べたパラメータである。

【００５３】 コード・フラグメント４： 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３ｆｆｆｆｆｆｆで除し、１を減ずるこ
とによって、これは、−１から１の範囲の浮動小数点値
に変換される。

【００５５】上のコード・フラグメントの実行の結果と
して、状態アレイは、図１（Ａ）の状態アレイ１００と
して発生する。エレメント１０３及び１０４は、それぞ
れ白及び黒と限定されたエレメントに対応する。コード
・フラグメント３に戻って、ライン３は、ライン４ない
しライン８で構成されるメイン・ループに対する変数ke
rnelSizeを初期化する。変数kernelSizeは、ディジタル
・フィルタを実行するために用いられるコンボリューシ
ョン・カーネルのサイズである。kernelSizeの初期値
は、userParams構造のフィールドから得られる。

【００５６】ライン５は、MakeDigitalFilter 手順を呼
び出し、カーネル・アレイに書き込む（fill in）。Mak
eDigitalFilter 手順には、kernelSize及びDotDensの変
数が与えられる。別の実施例では、必要ならuserParams
構造にストアされた他のフィールドが渡される。ライン
６は、ApplyFilter 手順を呼び出し、ライン５で作成さ
れたフィルタを用いて状態アレイに対するくり返し修正
を行う。

【００５７】ライン７は、状態アレイの全ての項目のＲ
ＭＳ（二乗平均）を計算し、限定されない画素に対応す
る全ての項目をこの値の逆数によってスケーリングす
る。このステップの目的は、状態アレイのＲＭＳ値を１
に維持することである。このアレイ内の値は、通常Appl
yFilter の呼び出しによって行われる調整後は、小さく
なり、これを補償しない限り、メイン・ループの反復実
行後、ＲＭＳ値はゼロに非常に近くなり、これによって
計算上の数値的不安定が発生する。

【００５８】ライン８は、カーネル・サイズをユーザに
よって与えられ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及びhighT
Valパラメータの間であれば、状態アレイの対応する値
の符号によって、スレショルド・アレイのその位置は、
そのままにしておかれるか又はthrshValにセットされ
る。スレショルド・アレイのその他の値は、そのままで
ある。lowTValとhighTVal の間の値を有するスレショル
ド・アレイの位置は、限定されていないドット・プロフ
ァイルのエレメントに正確に対応する。スレショルド・
アレイのこれらの特定のエレメントが変わることによっ
てのみでは、ドット・プロファイルの限定されたエレメ
ントは変更されない。ドット・プロファイルの限定され
ないエレメントに対応するスレショルド・アレイのエレ
メントは、全て値lowTVal を有する。これは、現時点迄
に、lowTValとhighTVal の値がスレショルド・アレイに
ストアされていないためである。この時点以降は、thrs
ValがlowTValより大きく、highTVal より小さいので、
スレショルド・アレイをthrsValと比較した結果、限定
されないエレメントに対しては、状態アレイによって示
される黒と白の同一パターンになる。これでMakeDotPro
file手順の説明を完了する。

【００６２】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が含まれ
る。ライン２は、ライン３から７で構成されるこの手順
のメイン・ループの実行を制御する。このループは、us
erParams->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に対する第１の座標に関して、０からwidt
h-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 （数値処理法）」に与えら
れている。

【００８３】フィルタ動作は、２Ｄ ＦＦＤを用いて次
のステップで行われる。第１に、フィルタをかけたアレ
イに初期ストアされたフィルタをかけていない値の２Ｄ
ＦＦＴは、計算されて複素数の第１の補助アレイにス
トアされる。第２に、カーネル・アレイの２Ｄ ＦＦＴ
は、計算されて複素数の第２の補助アレイにストアされ
る。（このステップは、カーネル・アレイがループ内で
は変わらないため、メインループの外側で実行され
る。）第３に、第１の補助アレイの各エレメントに、第
２の補助アレイの対応する位置にあるエレメントを乗ず
る。最終ステップは、第１の補助アレイに逆２Ｄ ＦＦ
Ｔを実行し、その結果をフィルタをかけたアレイに戻し
て再びストアする。これによってフィルタ処理が完了す
る。コンボリューション・カーネルのサイズ（ gRadiu
s）が大きいとき、この方法は、コード・フラグメント
９及び次の節で説明されている方法よりも速い。更に、
ＦＦＴの方法は、自動的に所望のラップ・アラウンドの
効果をシミュレートする。

【００８４】フィルタリングの後、フィルタをかけたア
レイは、図１（Ｃ）のドット・プロファイル３００とし
て現れる。ここで、暗いグレイは０に近い値に、明るい
グレイは、コンボリューション・カーネルの全項目の和
であるgausSum に近い値に対応する。例えば、このフィ
ルタをかけたドット・プロファイル・アレイのエレメン
ト３０３は、部分２０４Ａ及び２０４Ｂからなる一つの
円に含まれる図１（Ｂ）のフィルタをかけていないドッ
ト・プロファイル・アレイ２００のエレメントの加重加
算である。円は２つの部分、左の２０４Ａ及び右の２０
４Ｂに分割されている。これは、どのようにディジタル
・フィルタ計算のラップ・アラウンド機構が動作するか
を示している。もし円が一体となった円であれば、円の
左端は、アレイの左端を超えてしまう。これは、左端に
負のｘ座標を有する円内の位置に対応する。上のモジュ
ール化された計算コードは、アレイの幅を加えることに
よって、これらの負のインデックスを訂正し、部分円２
０４Ｂで示すように、アレイの右側に来るようにしてい
る。

【００８５】擬似コード・フラグメント７は状態アレイ
の値の調整を行う。この調整の正確なメカニズムは、次
のＣ言語のコード・フラグメント１０で述べられてい
る。次の変数が、このコード・フラグメントの実行前に
設定されていると仮定する。すなわち、thrsPtr はスレ
ショルド・アレイの最初のエレメントに対するポインタ
であり、endThrshは、スレショルド・アレイの最後を越
えた最初のエレメントに対するポインタであり、stateP
trは状態アレイの最初のエレメントに対するポインタで
あり、filtPtr は、フィルタをかけたアレイの最初のエ
レメントに対するポインタである。変数lowTVal、highT
Val及びDotDensはこの手順のパラメータである。変数ga
ussSumは、上の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についてチェックし、ドット・プロファイル
の対応する位置が限定されていないかどうか調べ、もし
そうなら、ライン７から１０が実行される。ライン７
は、状態アレイの現在の位置から値をフェッチし、stat
e にストアする。ライン８は、現在の位置のフィルタを
かけていないドット・プロファイルの値を計算し、DotC
olorにストアする。

【００８９】ライン９は、現在の位置での状態アレイに
対する調整を計算する。この調整は２つの部分からな
る。第１の部分は、所望のフィルタをかけた値と実際の
フィルタをかけた値の差、grayAvg-*filtPtrである。こ
の調整部分は、暗すぎるドット・プロファイルの領域を
明るくし、その逆も行う修正作用を構成する。第２の調
整部分は、hyst*(2*dotColor -1)であり、白いドットを
白く、黒いドットを黒く維持しようとする保守的作用を
構成する。変数hystは、この作用の大きさを制御する履
歴定数である。この修正作用の必要性は明白である。こ
れは、暗すぎたり、明るすぎたりするドット・プロファ
イルの領域をならし、従って最終的に不快なパターンが
ないドット・プロファイルを生成する。

【００９０】保守的作用は、もっと微妙である。保守的
作用の１つの目的は、反復修正を一定の値に収束させる
ためのものである。従って、この手順のメイン・ループ
の１回のくり返しで、ドット・プロファイルを修正する
可能性は、ドット・プロファイルをそれが次のループ
で、前にあった場所に修正して戻されることによっての
み避けられる。

【００９１】保守的作用の第２の目的は、修正作用によ
ってオーバーライドされないとき、状態アレイの元の値
をできるだけ無傷のまま保持することである。状態アレ
イがランダム値で初期化され、このランダム作用を最終
的ドット・プロファイルのドット配置に保持することが
望ましい。ランダム・ドット配置によって、ドット・プ
ロファイルにおける不快なパターン及びドット・パター
ンを重ねることによって生ずる斑紋のパターンが減少す
る。保守的作用に対する更に別の利点は、いくつかの異
なったディジタル・フィルタが用いられたとき、最初の
フィルタによって行われた有益な作業が、後のフィルタ
を適用することによって取り消されないことである。

【００９２】修正作用と保守的作用は、対立した数の量
である。一般に修正作用は、特定の画素の周囲のドット
・プロファイルのエレメントの加重加算の誤差が変数hy
stより大きいとき、成功する。もし状態アレイが、ラン
ダム・パターン以外のパターンで初期化されると、保守
的作用は、そのパターンをできるだけ保持し、修正作用
は、ドット・プロファイルの平均グレイ値に対する修正
を行うことに留意されたい。これは、複数の同一でない
ハーフトーンのセルがスレショルド・アレイに含まれる
ときに発生するドット・プロファイルのスムージングの
ために役立つ。この場合、初期のパターンは、従来のス
クリーニングのように、ハーフトーン・ドットのアレイ
である。従って、本発明は、ランダム・スレショルド・
アレイと同様、スレショルド・アレイからの別のタイプ
のパターンを除去するのにも役立つ。

【００９３】ライン１０は、今行われた調整に従って、
状態アレイの値を修正する。これは、状態アレイの値を
調整された現在の値の加重平均に設定することによって
行われる。adjustmentは、１０／gaussSum倍され、大き
なコンボリューション・カーネルについて発生するadju
stmentの大きな値を打ち消すことに留意されたい。この
ようにして、状態アレイの値は、メイン・ループを何回
も反復することによって、調整の方向に徐々に調整され
る。これは、状態アレイの多くのエレメントが、メイン
・ループの１回のくり返しで符号を変えないようにする
ために必要である。これは、この手順のイメージ・ルー
プが実行されるにつれて、状態アレイの値が安定した値
に収束することを保証する。

【００９４】ドット・プロファイルにおける画素が黒
で、フィルタをかけたアレイで計算された平均が「明る
すぎ」であると、調整は、ドット・プロファイルにおけ
る画素は、黒にとどまることにも留意されたい。同じこ
とは、平均が「暗すぎ」の領域における白い画素につい
ても云える。暗すぎる領域における黒又は明るすぎる領
域における白の画素のみが変わり得る。また、限定され
ていない画素のみが変わりうる。これらの画素のうち、
上の調整によって、状態アレイの対応するエレメントが
符号を変えるわずかな部分のみが選択されて、その色を
逆にする。状態アレイにおける初期値はランダムである
ので、この選択は、決定論的成分に加えてランダム成分
を有する。

【００９５】ドット利得パターンを防止するための修
正：上で説明した方法は、ドット利得が良く制御された
ディジタル出力装置で良く動作することが分かってい
る。ドット利得は、中心のドットを囲むドットの色が、
その中心のドットの色に影響を与える物理現象である。
理想的ディジタル出力装置では、各ドットの色は、この
ような影響からは全く独立している。しかも、多くの実
際の装置は、この理想を達成できない。ドット利得によ
って、ドットのグループの実際の平均グレイ値におい
て、上のプログラムで計算された理論的値からの実質的
変化が生ずる。従って、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. }

【０１０４】ドット利得モデル化コードの実行は、第５
のパラメータによって制御されることに留意されたい。
従って、コード・フラグメント３のライン６からのAppl
yFilter に対する第１の呼び出しでは、ドット利得モデ
ル化コードは実行されず、第２の呼び出しで実行され
る。これによって、ドット利得が出力装置上に存在する
場合と存在しない場合の両方について、スムージングの
ためにドット・プロファイルを交替して調整できる。こ
の交替のテクニックによって、ドット利得が高い装置と
低い装置の両方で、所与のドット・プロファイルに関し
て生ずるパターンを低減する。

【０１０５】所与の装置のドット利得の実際の量が、温
度や湿度のような環境ファクタによって変動し、しばし
ばユーザのコントロール外であるため、これは重要であ
る。ドット利得があるときにも、ないときにもスムーズ
に見えるドット・プロファイルを作ることによって、こ
のドット・プロファイルは、ドット利得パラメータの範
囲で、装置上に良く再生されることが分かっている。

【０１０６】ドット利得のモデル化を、ApplyFilterに
対する１回目の呼び出しでオンにし、２回目の呼び出し
でオフにすることが時として有利である。ApplyFilter
手順のメイン・ループを連続して通る間にドット利得の
モデル化をオン、オフすることもときには有利である。
モデル化をオン、オフするその他の手順を用いることも
できる。殆ど又は全くドット利得がない装置に対するス
レショルド・アレイを生成するとき、全てのドット利得
修正を排除することによって優れた結果が得られること
も分かっている。

【０１０７】本発明のテクニックを用いて、不快なパタ
ーンがないドット・プロファイルが生成される。それら
は、継ぎ目なしに配列され、所望のドット密度で構築さ
れる。更に、ドット・プロファイルは、あるエレメント
が黒のままであり、他が白のままであるような制限付き
で生成される。相応する制限を有する複数のこのような
ドット・プロファイルは、元のグレイ値と比較して、要
素であるドット・プロファイルを生ずる１つのスレショ
ルド・アレイにアセンブルされる。このようなスレショ
ルド・アレイは、様々なディジタル表示装置に用いるこ
とができ、不快なパターンがなく、斑紋効果のない優れ
たハーフトーンを達成できる。更に、ドット・プロファ
イル自体は、ディジタル表示装置上に平坦なグレイ階調
を再生する必要があるとき、役立つ。

【０１０８】本発明の説明を、ディジタル・コンピュー
タで動作するプログラムについて行ったが、当業者は、
特定用途のディジタル・ハードウェア等の他の実施も可
能であることが分かるであろう。更に、コンピュータ・
プログラムの説明は、多くの場合、黒と白のドットを生
ずるディジタル表示装置を想定している。しかし、当業
者は、同じテクニックが固定色セット又は固定グレイ階
調のセットを再生するディジタル表示装置に適用できる
ことが分かるであろう。当業者には理解できるように、
上に説明した装置及び方法に対する変更は、本発明の精
神と範囲からはずれることなく、熟練した実務者によっ
て成されることが可能であり、本発明は以下の特許請求
の範囲に限定されるべきである。

【図面の簡単な説明】

【図１】 （Ａ）、（Ｂ），（Ｃ）は、本発明に用いら
れる様々な２次元アレイと、本発明の方法における特定
の時点でのこれらアレイの相互関係を図表形式に示す。

【図２】 本発明の方法で用いられる様々な手順の間の
制御の全体的流れを示すフローチャートである。

【図３】 ドット・プロファイルの仮定した区画におけ
るドット利得を示す図である。

【符号の説明】

１００ 状態アレイ ２００ 関連ドット・プロファイル ３００ フィルタをかけたドット・プロファイル

Claims (2)

【特許請求の範囲】
1. 【請求項１】 複数のドット・プロファイルからなるス
   レショルド・アレイを生成する方法であって、各ドット
   ・プロファイルは、黒又は白の画素からなり、特定のド
   ット・プロファイルにおける特定の画素は、黒又は白に
   限定されており、（１） １つのドット・プロファイル
   の各限定されていない画素に対して黒又は白として変換
   可能な値を割り当てるステップと、（２） 上記ドット
   ・プロファイルの所定の領域内の画素の上記値の関数
   が、予め定められた所望値と異なっているかどうかに基
   づいて、上記所定の領域内の特定の画素に対して割り当
   てられた上記値を調整し、ごくわずかの場合に、上記調
   整された値が無調整の値から反対の色に変換できるよう
   にするステップと、（３） 上記ドット・プロファイル
   の全体がカバーされるまでステップ（２）を上記ドット
   ・プロファイルの別の所定領域に対してくり返すステッ
   プと、 上記スレショルド・アレイ内の上記ドット・プロファイ
   ルのそれぞれに対して（１）から（３）のステップをく
   り返すステップとからなり、結果として生ずる上記スレ
   ショルド・アレイ内の上記ドット・プロファイルが、実
   質的に不快な可視パターンを生じないことを特徴とする
   スレショルド・アレイの生成方法。
2. 【請求項２】 請求項１の方法に従って作成されたスレ
   ショルド・アレイ。