(57)【特許請求の範囲】
【請求項１】
ラスター表示装置上に画像を、スーパータイル中のハーフトーンドットから作られる所定のグレイレベルでもって表示する方法であって、前記スーパータイルには、重心をそれぞれ持つＫ個のデジタルセルが含まれ、幾何学的中心をそれぞれ持つＫ個の対応する理想セルがあり、そして、画素座標を持つ複数の画素が含まれており、デジタルセルのために選択された複数の画素の画素座標に対してスポット関数を適用することによって画像が再現されるようにされており、
ａ）  デジタルセルのために選択した複数の画素の画素リストを生成する過程と、
ｂ）  前記画素リスト中の画素についてｘ座標及びｙ座標からなる画素座標を決定する過程と、
ｃ）  前記画素リスト中の画素の画素座標に加えるべき、ｘ座標及びｙ座標からなるオフセットベクトルを決定する過程と、
ｄ）  前記オフセットベクトルを前記画素リスト中の画素の画素座標に加算する過程と、
ｅ）  前記ステップｄ）で得られた座標をセルスペース座標に変換する過程と、
ｆ）  前記画素リスト中の画素のランク付けを、前記ステップｅ）で得られた画素座標に対して前記スポット関数を適用して得られた結果の値に従って、行う過程と、
ｇ）  ハーフトーンドットとなる表示すべき画素の選択を、前記ランク付けの結果に従って行って、再現中の画像の前記所定のグレイレベルが適正に再生されるようにする、選択を行う過程と、
ｈ）  前記スポット関数の適用により得られたランク付けを用いて表示すべきと選択され、ハーフトーンドットとなる画素から成る画像を表示する過程とを備え、
前記オフセットベクトルの決定は、スーパータイル内のハーフトーンドットの大きさのバラツキが減少するように行われる、
ことを特徴とする画像の表示方法。
【請求項２】
請求項１に記載の表示方法において、デジタルセルの重心は、当該デジタルセルのために選択された複数の画素についてのｘ座標の平均およびｙ座標の平均から計算でき、前記オフセットベクトルは、理想セルの幾何学的中心と、それに付随のデジタルセルの重心との差である、ことを特徴とする画像の表示方法。
【請求項３】
請求項１に記載の表示方法において、前記オフセットベクトルは、前記スーパータイルの全てのデジタルセルについて同じ値を持っていて、前記画素座標に当該オフセットベクトルを加えた後で、もしその和の値が所定の範囲の外側にあれば、その和を前記所定の範囲内に調整するようにした、ことを特徴とする画像の表示方法。
【請求項４】
請求項１に記載の表示方法にあって、画素リストを生成する前記過程ａ）において、
(i) 前記スーパータイルは、相互に４５度だけ異なる向きの第１および第２の２つのハーフトーン格子内にあり、その第１のハーフトーン格子は、前記Ｋ個の理想セルに、従って、前記Ｋ個のデジタルセルに対応し、その第２のハーフトーン格子は、前記スーパータイル内に２Ｋ個の理想疑似セルを画定し、それらの２Ｋ個の理想疑似セルに対応する２Ｋ個のデジタル疑似セルには、それぞれ等しい数の画素が割り当てられ、
(ii)前記画素リストの複数の画素は、等しい数の画素をそれぞれ有するデジタル疑似セルに基づいて決定される
ことを特徴とする画像の表示方法。
【請求項５】
請求項４に記載の表示方法において、前記スポット関数は、５０％のグレイレベルの要求に対しては、チェッカーボードパターンを生成する、ことを特徴とする表示方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、ハーフトーン画像を作成するために二つ以上のハーフトーンセルを含む閾値アレイの作成に関する。二つ以上のハーフトーンセルを含む閾値アレイは、画像中の類似するグレイ領域を表わすハーフトーンドットの大きさを均等にするための措置をとらない限り、再現される画像の中にはっきりしたはん点又は帯を生じさせる。
【０００２】
【従来の技術】
多くの印刷装置では連続階調画像を十分に印刷することができないので、通常は画像を格子に基づいてドットのパターンとして印刷する。格子は、それぞれが原画像の連続する階調の一つの部分を表しているハーフトーンセルのアレイから構成される。デジタル記録装置を使用してこの方法でハーフトーン画像を再現する場合、一つのハーフトーンセルは複数個の装置画素から構成される。各ハーフトーンセルの表示画素の一部が黒色に変わると、元の連続階調画像のより暗い部分又はより明るい部分を表わすべき相対的に大きいドット又は相対的に小さいドットができる。暗いハーフトーンセルの場合、その画素の大半は黒色に変わっており、明るいハーフトーンセルの場合には、その画素の大半は白色に変わっている。原画像の完全な格子は多数のそのようなハーフトーンセルから構成されており、それぞれのハーフトーンセルの中には個々に独立した密度で画素が表示されているので、距離をおいて観察すると、各ハーフトーンは異なる見かけの暗さを有している。
【０００３】
各ハーフトーンセルにおいてどのドットを黒色に変えるべきかを選択する際に、従来より一般に採用されてきた方法は次のように進行する。所定のハーフトーンセルについて、そのハーフトーンセルにおける表示画素位置ごとに原画像をサンプリングして、グレイ値を求める。このグレイ値は、通常は０から２５５までの一定の範囲内にあるデジタル数として表わされる。次に、グレイ値を同じ範囲内にある閾値と比較し、画像のグレイ値が閾値より大きい場合は表示画素を白色に変化させ、そうでない場合には黒色のままとする。この閾値は、ハーフトーンセルの画素ごとに別個の閾値を含む閾値アレイによって与えられ、画像の処理に先立って計算される。画像にハーフトーンセルごとにこのプロセスを実行する。
【０００４】
この方法は、画像中のあらゆるハーフトーンセルについて同一の閾値アレイを使用できる場合に最も良く機能する。その一つの利点は、画像全体に対して一つの閾値アレイを計算して記憶するだけで良いということである。第２の利点は、所定の強さのグレイ領域は、それが画像のどの場所に現れようと、同じ大きさ、同じ形状のドットを発生することである。ところが、この利点を発揮させるためには、画像中の各ハーフトーンセルに対応する表示画素の組は他のどのハーフトーンセルに対応する表示画像の組とも厳密に同じ大きさ，同じ形状でなければならないということである。多くの場合、四角が表示画素スペースにおける整数座標と全て厳密に一致するような平行四辺形としてハーフトーンセルを形成することを要求すれば、この条件は満たされる。本明細書にも参考として取り入れてある米国特許第４，１８５，３０４号は、この方法の１例を示している。
【０００５】
上記の方法の問題点の一つは、再現可能な異なるハーフトーンスクリーンの数がハーフトーンセルの四角を表示画素スペース中の整数座標と一致させなければならないために限定されることである。たとえば、カラー印刷で一般に使用されている、１５°又は７５°の回転を伴うスクリーンを正確に再現することは不可能である。１９８９年１１月８日に本発明と同一の発明者により出願され且つ本発明と同一の譲受人に譲渡されており、本明細書にも参考として取り入れてある第１の同時係属米国特許出願第４３４，９２４号（以下、第１の同時係属出願という）では、この欠点に対処している。この出願には、複数個のハーフトーンセルから構成される閾値アレイを使用して、利用可能なハーフトーンスクリーンの数をどのような任意のスクリーンでも適切な許容差の範囲内で近似できるところまでいかにして増加させることができるかが示されている。
【０００６】
閾値アレイが２個以上の理想セルを含む場合、このことがユーザーの目には見えないことが望ましい。すなわち、所定のグレイレベルについて、閾値アレイの一つのコピーにより発生される全てのハーフトーンドットは同じ大きさでなければならないと共に、等間隔で配列していなければならない。
残念なことに、そのような閾値アレイにおける複数のハーフトーンセルを表示画素により表わす場合には、それらのハーフトーンセルは、通常、異なる形状と大きさでなければならない。すなわち、異なるハーフトーンセルにより発生されるドットは、それらが同じグレイ値を表わしていても、異なる形状と大きさになってしまうのである。ハーフトーンセルの大きさと形状の差の程度に応じて、そのような差は目に見えることもあり、見えないこともある。目に見えるときには、原画像が一定のグレイ値しか含んでいなかったところに、反復するはん点又は帯の形をとるグレイ強さのまだらな変化を見ることになる。そのようなパターンは原画像を忠実に再現しておらず、従って、望ましくない。
【０００７】
明瞭を期するために、下記の用語を定義する。理想のハーフトーンセル，略して理想セルは上記のセルのようなハーフトーンセル、すなわち、回転される正方形又は平行四辺形により境界を限定される領域から構成されるハーフトーン格子の１要素である。これに対し、デジタルハーフトーンセル、略してデジタルセルは、理想のハーフトーンセルを近似するために使用される一組の画素である。従って、各デジタルハーフトーンセルはそれが近似する特定の一つの理想のハーフトーンセルと関連している。また、本明細書にも参考として取り入れてある上記の同時係属米国特許出願第４３４，９２４号に従って、複数個のハーフトーンセルから構成される閾値アレイを「スーパータイル」という。
【０００８】
同時係属出願に開示されているようなスーパータイルを生成する従来の方法においては、デジタルハーフトーンセルは、スーパータイル中の、関連する理想セルの中に幾何学的中心が入っている全ての画素から構成される。この方法はいくつかのハーフトーンスクリーンについては申し分のない一貫性をもつデジタルハーフトーンセルを作成するが、別のスクリーンに対しては、デジタルセルの大きさに不十分なばらつきが生じる。このようなばらつきが起こるのは、それぞれの理想セルが同一の形状を有しているにもかかわらず、画素格子に関する各セルの配置は画素の部分量によって異なるためである。そこで、場合によっては、一つの理想セルの内側に中心が入っている画素の数が多くなるが、別の場合には、理想セルの内側に中心が入っている画素の数は少なくなる。その結果、デジタルハーフトーンセルの大きさに変動が生じると、いくつかのグレイ値を再現するときに、ハーフトーンドットの大きさにも対応する変動が起こる。これはセルサイズ不均等の問題と呼ばれ、本発明と同一の発明者が１９９１年２月８日に出願し且つ本発明と同一の譲受人に譲渡されており、本明細書にも参考として取り入れてある同時係属米国特許出願第６５２，９２７号は、この問題を取り扱っている。
【０００９】
いくつかのグレイレベルで、所定の黒色又は白色のハーフトーンドットがそのデジタルハーフトーンセルの境界を越え、隣接するデジタルセルの画素と重なり合っている場合に別の型の誤差が発生する。一つの黒色又は白色のハーフトーンドットが二つ以上のピースに分割され、図１に示すように、それぞれのピースが別個のデジタルハーフトーンセルに位置することも考えられるであろう。デジタルハーフトーンセル１３０Ａ−Ｆは対応する理想のハーフトーンセル１２０Ａ−Ｆに対して非対称になることもあるので、理想セル１２０Ａ−Ｆにおけるハーフトーンドット７０Ａ−Ｆの様々なピースにも同様に非対称に画素が割り当てられるであろう。デジタルハーフトーンセル１３０Ａ−Ｆを一緒にして、ハーフトーンドット７０Ａ−Ｆの全体を形成したとき、正しいハーフトーンドット画素の全ては各デジタルセルの中にあるにもかかわらず、一つのハーフトーンドットを形成するために使用されるピースが所定の所期サイズに対して小さすぎる又は大きすぎることも起こりうる。
【００１０】
たとえば、図１のデジタルセル１３０Ａ−Ｆのそれぞれには１０個の黒色画素（斜線により示す）が割り当てられており、残る画素は白色である。黒色画素はドット７０Ａ−Ｆを作成する。ドット７０Ａは正しい所定サイズであり、主にデジタルセル１３０Ａの中にある９個の黒色画素と、主にデジタルセル１３０Ｂの中にある１個の黒色画素の合わせて１０個の黒色画素を含む。ところが、ドット７０Ｂは黒色画素を８つしか含んでおらず、そのうち一つは主にデジタルセル１３０Ｃの中に入っている。ドット７０Ｅは１２個の黒色画素を含み、そのうち八つは主にデジタルセル１３０Ｅの中にあり、２個は主にデジタルセル１３０Ｂの中にあり、１個は主にデジタルセル１３０Ｆの中にある。この問題をマルチセルドット（ＭＣＤ）の問題という。
【００１１】
【発明が解決しようとする課題】
本発明の主な目的は、上記のマルチセルドットの問題を修正することである。
【００１２】
【課題を解決するための手段】
本発明の方法は、スキャナ，コンピュータ及び何らかの種類のラスター表示装置を含むいくつかのハードウェア装置のどれを使用しても実施できる。原画像を機械的又は電子的に走査し、計算し、操作するか又は別の方法によりその再現の準備を行う。非常に正確なハーフトーンスクリーン表示のために、わずかに異なる形状をもつ複数のデジタルハーフトーンセルを含む閾値アレイを使用しなければならない場合、本発明は、各ハーフトーンセルが画素の数を均衡させるような方式で印刷又は表示されるように保証する。これは、より小さな画素を使用することと、二つ以上のデジタルセルの中に位置しているそれらの画素の一部から形成されるハーフトーンドットが隣接するデジタルハーフトーンから画素を奪ったり、隣接するデジタルハーフトーンセルに画素を奪われたりしないという条件とを組み合わせることにより可能になる。これにより、所定のグレイレベルを表わす全てのハーフトーンドットはできる限りほぼ等しい大きさとなることが保証される。
【００１３】
本発明の第１の方式は、たとえば、デジタルセルの一方の側に総称画素が追加され、他方の側から画素が取られたときに起こる偏りを修正する。ハーフトーンドットがデジタルセル間で分割されている場合、この偏りは総称画素を不均等に配分させてしまう。スポット関数を実行させるために、総称画素座標を理想セルスペース座標へ移行するときの原点として、各デジタルセルの重心を使用すると、この偏りは少なくなる。
【００１４】
本発明の第２の方式によれば、閾値アレイを作成するときに、各理想のハーフトーンセルを白色部分と、黒色部分という二つの全く等しい部分に分割すると、ＭＣＤの問題は緩和される。この第２の方式はいくつかのスポット関数、通常は、５０％グレイレベルが要求されるときに元のにハーフトーン格子に関して４５°回転された完全なチェッカーボードパターンを出現させるものにのみ限定される。
【００１５】
本発明の第３の方式は、スポット関数を全てのハーフトーンセルに対してセルスペース内のベクトル（１／２，１／２）だけオフセットさせることにより、ＭＣＤの問題をさらに少なくする。このようにすると、黒色のドットの中心も、白色ドットの中心もあらゆる理想セルの四角領域には厳密に位置しなくなる。ところが、いくつかのグレイレベルでは、黒色ドット及び白色ドットがある理想のハーフトーンセルの縁を最初に越えるとき、異なるデジタルセルに属しているそのドットの各ピースの大きさが異なるために、ドットの大きさはばらついてしまうことがある。しかしながら、ドットは既にその中に多数の総称画素を含んでいるので、そのようなばらつきは以前ほど顕著ではない。
【００１６】
本発明の第４の方式は、様々なグレイレベルでハーフトーンドットがデジタルセルによりいかにして分割されるかを表わす画素のリストの形態をとる情報を含むデータ構造を作成する。その後、選択されたセルの中の画素を、所定のモデルセルに対する画素の損失又は獲得をモデリングするようにランク付けしてゆく。
【００１７】
現在市場に出ているハーフトーン化システムのスポット関数の数は限られており、システムは、組み込みの定まった一連のスポット関数を使用して動作するように特別に最適化されている。本発明の方式は、これまで可能であったより広い範囲のスポット関数を使用して高品質のハーフトーン化を発生する。
添付の図面と関連させて以下の好ましい方式の説明を考慮することにより、本発明を完全に理解できると共に、本発明の他の利点や特徴を明らかにすることができるであろう。
【００１８】
【実施例】
デジタルコンピュータにおいて実行されるコンピュータプログラムの形で実現するものとして方法を説明する。方法の一部の実現が当業者に明確にわからないと思われるところでは、必ず、Ｃプログラミング言語による明示コンピュータ原始コードを示す。Ｃ言語に関しては、本明細書にも参考として取り入れてあるＢｒｉａｎ  Ｗ．Ｋｅｒｎｉｎｇｈａｎ，Ｄｅｎｎｉｓ  Ｍ．Ｒｉｔｃｈｉｅ共著「Ｔｈｅ  Ｃ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅ」（Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ  Ｉｎｃ．刊）を参照のこと。Ｃ言語による数学的表現は通常の数学表記法と類似している。記号「*」 は乗算を表すために使用され、原始コードの注釈の始めと終わりは「／*」と「*／」により規定される。
【００１９】
本発明をコンピュータプログラムとして実現するためには、プログラムのサブルーチンとしていくつかの数学的関数を利用できることが必要である。次の章ではそれらの関数を定義する。
本発明において使用する数学的関数
Ｅｌｏｏｒ（ｘ）は、浮動小数点値ｘ以下の最大の整数である。
Ｃｅｉｌ（ｘ）は、浮動小数点数ｘ以上の最小の整数である。
Ｓｑｒｔ（ｘ）は、ｘの正の平方根である。
用  語
以下の明細書及び図面の中で引用される用語を次の通りに定義する。
【００２０】
装置スペース：記録装置が白色の背景の上に黒色のマークを形成するか、又は黒色の背景の上に白色のマークを形成することができる二次元平面の一領域。
装置画素：記録装置は装置スペース内のいくつかの不連続の領域をマーキングすることしかできない。そのような各領域が装置画素又は総称画素である。
装置座標：装置画素の場所を記述するために使用される座標系。どの装置の装置画素も一つの矩形アレイの中にあると想定できる。画素座標（ｘ，ｙ）はｙ番目の行，ｘ番目の列にある画素を表わす。図３では、装置座標系の原点を００とラベル付けしてある。あいまいになるのを避けるため、場所（ｘ，ｙ）にある装置画素は、ｘ及びｙを整数とするとき、（ｘ，ｙ），（ｘ＋１，ｙ），（ｘ＋１，ｙ＋１），（ｘ，ｙ＋１）により四角が与えられる正方形の面積を覆っている画素であると仮定する。大半のマーキング装置はこれほど精密ではないが、以下で示すプロセスを説明する上で上記の規約は有用であろう。
ハーフトーン格子：装置画素より大きな複数の正方形から成り、通常、装置座標系に関して回転される格子。この格子はハーフトーンドットの配置を制御する。アナログシステムでは、ハーフトーンドットはハーフトーン格子の正方形の中心と厳密に中心が一致している円である。以下に説明する本発明の方式は、ハーフトーン格子が正方形ではなく、平行四辺形から構成されている場合にも機能する。
理想のハーフトーンセル：ハーフトーン格子の一つの正方形。
理想のセルスペース又はセルスペース：選択された一つの理想セルに基づく座標系。そのような座標系の原点は理想セルの中心にあり、また、この座標系は理想セルの四角が座標（１，１），（１，−１），（−１，−１），（−１，１）を有するようにスケーリングされる。そのような座標系と装置座標系との変換の方法は当業者には自明であろう。（本明細書にも参考として取り入れてあるＦｏｌｅｙとＶａｎ  Ｄａｍの「Ｆｕｎｄａｍｅｎｔａｌｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ」第７章を参照。）尚、異なる理想セルごとに異なるセルスペース座標系が存在している。
デジタルハーフトーンセル又はデジタルセル：形状及び大きさの点で関連する一つの理想セルに近似する１群の総称画素。一つの理想セルの辺は画素の境界とは、通常、一致しないので、デジタルセルは一つの理想セルを一つの総称画素の中に正確に近似できるにすぎない。理想セルが一つの特定のデジタルセルにより近似されるものであれば、そのデジタルセルは理想セルと関連しており、その逆もいえる。
ハーフトーンドット：所定のグレイレベルに対して、連続する一組の総称画素が黒色（白色ドットの場合には白色）に変わると、それは人間の目にはハーフトーン化画素を構成するドットのパターンの中の一つの黒色（又は白色）のドットとして知覚される。尚、この定義は人間の知覚に関して行われるものである。従って、この用語はある種のハーフトーン化方式の所望の又は実際の特性を説明するときにのみ使用され、そのような方式がいかに実行されるかを規定するために使用されるのではない。
黒色（又は白色）セルドット：所定のグレイレベルで黒色（又は白色）に変わる、一つのデジタルセルの中の一組の黒色（又は白色）の総称画素。セルドットという用語自体は、黒色又は白色のセルドットを意味するときに使用されて良い。セルドットという用語は、ハーフトーンドットとは異なって、厳密な定義を有することに注意すべきである。ただし、一つのセルドットを構成する画素は、目が一つのハーフトーンドットとして知覚する画素でなくとも良い。たとえば、図２の場合、デジタルセル１３０の黒色セルドットは複数の別個のピース８０Ａ，８０Ｂ，８０Ｃ及び８０Ｄから形成されている。別の例として、図１のデジタルセル１３０Ａは、ハーフトーンドット７０Ａの中の９個の黒色総称画素と、近接するハーフトーンドット７０Ｄの中の一つの黒色総称画素とを含む一つの黒色セルドットを有する。この二つの画素から成るグループを目で単一のドットと知覚することはないであろう。
黒色（又は白色）ドットピース：一つの黒色（又は白色）セルドットが分割されて入っている様々な連続するピース。たとえば、図２において、デジタルセル１３０の黒色セルドットはドットピース８０Ａの中の３個の黒色総称画素と、ドットピース８０Ｂの中の一つの黒色総称画素と、ドットピース８０Ｃの中の３個の黒色総称画素と、ドットピース８０Ｄの中の一つの黒色総称画素とを含む。
【００２１】
スーパータイル１４０（図３）：所定のハーフトーン格子２２０について、第１の同時係属出願はスーパータイル１４０をいかに構成するかを示す。スーパータイル１４０は次に記すような特性を有する一組の装置画素１４０である。（１）スーパータイル１４０は、装置スペースの中の各総称画素１１０を厳密に一度覆うように、並進により複製可能である。（２）スクリーン格子（この出願ではハーフトーン格子２２０）をスーパータイル１４０に重ね合わせた場合、スクリーン格子はスーパータイルを整数個の理想のハーフトーンセル１２０に分割する。それらの理想セル１２０の一部をスーパータイル１４０の境界によって複数のピースに分割しても良い。（３）タイリングによりスーパータイル１４０を組み立てたとき、スーパータイルの縁部にあるハーフトーンセルの分割ピースはいずれも図３に示すように再び組み立てられる。
【００２２】
この明細書では、便宜上、図３に示すように、寸法「ｓｘ」及び「ｓｙ」を有する特定のスーパータイルを構成する。これらの寸法は、左下角が装置座標系の原点００と一致するｓｘ×ｓｘの正方形の中にある画素と、左上角が装置座標系の原点００と一致するｓｙ×ｓｙの正方形の中にある画素とからスーパータイルが構成されることを示している。従って、ｓｘ×ｓｘ正方形の中の装置座標（ｘ，ｙ）を有する総称画素の場合、そのｘとｙは共に０以上、ｓｘ−１以下である。ｓｙ×ｓｙ正方形の中の同様の画素のｘは０以上、ｓｙ−１以下であり、ｙは０未満、−ｓｙ以上ということになるであろう。
【００２３】
スーパータイル並進ベクトル１４１Ａ及び１４１Ｂ：先に述べた通り、スーパータイルを装置スペースを覆うように並進させることができる。そのようなスーパータイルの並進は、二つのスーパータイル並進ベクトルを使用する連続並進を経て実行可能である。図３に示すように、二つのベクトルは装置座標系においてベクトル１４１Ａの場合は値（ｓｘ，ｓｙ），ベクトル１４１Ｂの場合には値（−ｓｙ，ｓｘ）を有する。
【００２４】
等価セル：ｃ１及びｃ２と呼ばれる二つの理想セルについて、二つのスーパータイル並進ベクトルによる連続並進を経て一方のセルを他方のセルに厳密に重ね合わせることができるのであれば、それらのセルは等価であるという。これを理解する別の方法は、一つのスーパータイルを取り上げ、そのスーパータイルの中の全ての理想セルに一意のラベルを付すというものである。そのスーパータイルにより全スペースをタイリングしたとき、このタイリングにより形成される理想セルが同じラベルを有している場合には、それらのセルは厳密に等価である。
【００２５】
閾値アレイ（図３）：ハーフトーン化方式において、各総称画素１１０に「閾値」が与えられているような平面（すなわち、スーパータイル１４０の定義の下の第１番の条件）をタイリングする一組の総称画素又は装置画素１１０を表わすために一般に使用される用語。そのような閾値アレイは次のようにしてハーフトーン化画像を生成するために使用される。まず、平面を閾値アレイによってタイリングする。従って、各総称画素１１０は閾値アレイのコピーにより覆われることになるので、この閾値アレイのコピーの中でその総称画素を覆っている総称画素１１０の閾値と総称画素を関連づけることができる。次に、ハーフトーン化されている画像から総称画素１１０の所望のグレイ値を計算し、それを閾値と比較する。グレイレベルが閾値より大きい場合には、総称画素１１０は白色のままであり、そうでない場合には、総称画素は黒色にマーキングされる。
本発明では、閾値アレイを構成する一組の画素を規定するために、上記のスーパータイル１４０を計算する。スーパータイルは複数の理想セルを取り囲んでいるので、閾値アレイも同様である。
【００２６】
スポット関数：デジタルハーフトーン化を実際に実現する場合には、一つのデジタルセルを選択し、次に、そのデジタルセルの中に位置する全ての画素をリストに導入する。その後、リスト中の画素ごとにスポット関数を呼び出す。画素のセルスペース座標をこのスポット関数に入力すると、その画素をその他の画素に対してランク付けするときに使用する値が戻される。
このランク付けは、所望のグレイレベルがより暗い値からより明るい値に変化するにつれて理想セルの中で画素が黒色から白色に変化する順序を確定する。従って、閾値アレイ（スーパータイル）における閾値を確定するためにランク付けを使用するのである。このように、スポット関数は様々なグレイレベルでハーフトーンドットの形状を制御するために使用される。
画素の座標がスポット関数に与えられると、その座標は処理すべき理想セルに関するセルスペースに変換される。
【００２７】
さらに図３を参照すると、以下に説明する方式は、第２の同時係属出願の様々な方式に示されているように、理想セル１２０ごとに割り当てられる総称画素１１０の数が等しいとわかった後に適用されることになる。初めの三つの方式は、デジタルハーフトーンを作成するプロセスの中でスポット関数がいかに呼び出されるかを変更する。その結果、先に説明した方式により閾値アレイが作成されるときの閾値アレイの値が変わる。第４の方式は、スポット関数により戻される値について詳細にわたる処理を実行する。その後、それらの値は閾値アレイを作成するために使用される。本発明で得られる出力はスーパータイルに基づく変更閾値アレイであり、後に、そのアレイを使用して、擬似グレイ帯又ははん点のないハーフトーン画像を作成できるであろう。
【００２８】
スポットオフセット修正方式
マルチセルドット（ＭＣＤ）の問題が原因となって起こるパターンを修正する第１の方式は、理想セル１２０ごとにスポット関数をどのようにして呼び出すかを変更するものである。
さらに図３を参照しながら説明すると、総称画素１１０を理想セル１２０に割り当てる場合、理想セル１２０の形状にだけ近似するデジタルセル１３０が作成される。たとえば、デジタルセルを関連する理想セル１２０の形状に対して偏ったままにおく、デジタルセルの一方の側に余分の総称画素１１０の追加がされても良い。ハーフトーンドットが図１に示すデジタルセル１３０Ａ−Ｆの間で分割されている場合、この偏りは総称画素１１０を不均一に配分させることになる。図１及び図２を参照しながら以下に説明する方式はそのような影響を減少させる。この方式はスーパータイル内の各デジタルセルについて同じように使用される。そこで、スーパータイルの中の任意の１つのデジタルセルを選択し、そのセルについてのみ説明する。デジタルセルの中の総称画素のリストと、装置スペース座標における対応する理想のハーフトーンセルの中心の、（ｃｘ，ｃｙ）により表される座標という２つの情報を利用することができる。
【００２９】
選択したデジタルセル１３０の重心を、実際にそのセルに割り当てられた総称画素１１０から以下に説明するようにして計算する。次に、重心（ｇｘ，ｇｙ）を理想セルの幾何学的中心（ｃｘ，ｃｙ）から減じて、オフセットベクトル（ｆｘ，ｆｙ）を発生する。スポット関数に備えて装置スペースにおける総称画素１１０の座標をセルスペース座標に変換する前に、このオフセットベクトル（ｆｘ，ｆｙ）を座標に加算する。これを次のように要約することができる。
ｆｘ＝ｃｘ−ｇｘ；
ｆｙ＝ｃｙ−ｇｙ
そこで、総称画素ごとの座標（ｘ，ｙ）は次のようになる。
ｘ＝ｘ＋ｆｘ；
ｙ＝ｙ＋ｆｙ
重心は、デジタルセル１３０の中の各総称画素１１０の装置座標（ｘ，ｙ）を取り出し、それらの座標をセルスペース座標（ｕ，ｖ）に変換し、得られたｕ座標値とｖ座標値を別個に平均して、平均ｕ座標と、平均ｖ座標とを得ることにより計算される。ところが、一つのデジタルセル１３０Ａ−Ｆが図３に示す任意のスーパータイルにより複数のピースに分割されていることもありうる。たとえば、デジタルセル１３０Ｂはスーパータイル１４０の任意の境界１４０Ｂにより二つのピースＤＲ及びＤＬに分割されている。このようなことが起こると、座標の平均は正しく実行されない。
【００３０】
この事態を防止するために、次の手段を構じる。装置座標（ｘ，ｙ）を有するデジタルセル中のいずれかの総称画素が理想のハーフトーンセルの中心（ｃｘ，ｃｙ）から、一つの理想セルの１辺の長さに等しい所定の距離より長い距離ｄにある場合、総称画素の座標（ｘ，ｙ）が座標（ｃｘ，ｃｙ）から所定の距離の内側に入るまで、総称画素の座標（ｘ，ｙ）をスーパータイル並進ベクトルにより並進させる。次に、並進させた座標を元の総称画素座標の代わりに平均プロセスで使用する。
【００３１】
上記のプロセスにおいて使用するスーパータイルベクトル並進シーケンスは直接計算できる。ただし、並進の順序は問題ではなく、二つのスーパータイル並進ベクトルのそれぞれを使用する回数のみが重要である。値（ｓｘ，ｓｙ）を有するスーパータイル並進ベクトル１４１Ａを使用する回数をｎ１で表わし、値（−ｓｙ，ｓｘ）のスーパータイル並進ベクトル１４１Ｂを使用する回数をｎ２で表わすものとすると、ｎ１又はｎ２に対応するスーパータイル並進ベクトルを並進に使用するときにそのベクトルが否定されることを指示するために、ｎ１又はｎ２のいずれかは負であっても良い。下記のＣ言語コードセグメント１ａはｎ１及びｎ２を計算する。ここで、ｘ及びｙは並進を計算すべき総称画素の装置座標である。
/*Code segment 1a */
int x1,x2; /*Declare temporary variables */
ｘ１  ＝  ｘ  −  ｃｘ  ＋  ｓｘ／２  −  ｓｙ／２；
ｙ１  ＝  ｙ  −  ｃｙ  ＋  ｓｙ／２  ＋  ｓｘ／２；
ｎ１  ＝  −Ｆｌｏｏｒ（（ｘ１＊ｓｘ  −  ｙ１＊ｓｙ）／（ｓｘ＊ｓｘ  ＋  ｓｙ＊ｓｙ））；
ｎ２  ＝  −Ｆｌｏｏｒ（（ｘ１＊ｓｙ  ＋  ｙ１＊ｓｘ）／（ｓｘ＊ｓｘ  ＋  ｓｙ＊ｓｙ））；
次に、コードセグメント１ｂにより（ｘ，ｙ）の実際の並進を次のように計算する。
/*Code segment 1b */
ｘ  ＝  ｘ  ＋  ｎ１＊ｓｘ  −  ｎ２＊ｓｙ；
y = y + n1*sy + n2*sx;
これを実行した後、ｘ座標及びｙ座標をセルスペース座標（ｕ，ｖ）に変換し、スポット関数に供給する。
【００３２】
上記の方式では、スポット関数に供給される座標は、選択したデジタルセルにある様々な総称画素の場所から計算された量だけオフセットされている。そのようなオフセットは他の方法でも計算できる。たとえば、そのようなオフセットを得るために乱数発生器を使用できるであろう。これは、総称画素をランダムパターンをもつデジタルセルに割り当てるときに偏りの規則的なパターンをおおい隠すことを意図しているときには有用であるといえる。
【００３３】
分割セル修正方式
次に、マルチセルドットＭＣＤの問題によって起こるパターンを修正する第２の方式を説明する。この方式は、スポットオフセット方式が常に十分であるとはいえないためにでてきた。スポットオフセット方式はハーフトーンドットの大きさのばらつきを減らすだけであるので、ハーフトーンドットの大きさのばらつきが所定のレベルを越えないように保証するものではない。第２の方式はある種のスポット関数についてほぼ等しいハーフトーンドットの大きさを確保することができる。
【００３４】
図３を参照して説明すると、この方式によれば、スーパータイル１４０である本発明の閾値アレイを構成するときに、各理想セル１２０を二つの等しい部分に分割する。
第２の方式は、図４に示すように、５０％のグレイレベルが要求されるときにハーフトーン格子２２０に関して４５°回転された完全なチェッカーボードパターンを生じさせるスポット関数のようないくつかのスポット関数について最も良く機能する。これは最も一般的なスポット関数である。光学的スクリーニングをシミュレートするために使用される関数を含む（本明細書にも参考として取り入れてあるＡｄｏｂｅ  Ｓｙｓｔｅｍｓ  ＩｎｃｏｒｐｏｒａｔｅｄのＴｈｅ  Ｐｏｓｔｓｃｒｉｐｔ  Ｌａｎｇｕａｇｅ  Ｒｅｆｅｒｅｎｃｅ  Ｍａｎｕａｌの３１５ページを参照）。
この第２の方式の第１のステップでは、第１の理想のハーフトーン格子２２０から５０％グレイレベルのチェッカーボードパターンに基づいて第２の理想のハーフトーン格子４２０を作成する。その後、好ましくは第２の同時係属出願に開示されている均等面積方法を使用して、第２の格子４２０の理想セル３２０Ａ又は３２０Ｂに総称画素を割り当てる。
【００３５】
この第２のチェッカーボードパターンは、第１の理想のハーフトーン格子２２０を４５°回転し、第１の理想のハーフトーン格子２２０の一つの理想セル１２０の辺を１／Ｓｑｒｔ（２）だけ縮小し、第２の理想のハーフトーン格子４２０の四角が第１の理想のハーフトーン格子２２０の理想セル１２０の辺の中間点と一致するように第２の理想のハーフトーン格子４２０をアライメントすることにより計算される理想のハーフトーン格子４２０を発生する。同じ大きさのスーパータイル１４０の中に、第１の理想のハーフトーン格子２２０にある理想セルの数の厳密に２倍の数の第２の理想のハーフトーン格子４２０の理想セル３２０Ａ、又は３２０Ｂが存在する。スーパータイル１４０の元の寸法を保持すると共に、第２のハーフトーン格子４２０をさらに微細にすることにより、ハーフトーン擬似セル３２０Ａ及び３２０Ｂが形成される結果となる。たとえば、各擬似セル３２０に同数の画素が確実に割り当てられるように、均等面積を使用しても良い。
【００３６】
最後に、スポット関数を呼び出し、閾値を計算する。スーパータイル１４０は、第１の理想のハーフトーン格子２２０を伴って作成されたかのように見えるようになる。これは、理想セル３２０の左下角の座標を第２の理想のハーフトーン格子４２０に基づく座標系で表わした場合に、それが偶数になるか、奇数になるかに応じて、第２のハーフトーン格子４２０の各理想セル３２０Ａ及び３２０Ｂが「偶数」番号になるか又は「奇数」番号になるかに注目することにより行われる。
【００３７】
偶数番号の理想セル３２０について、一つの偶数番号の理想セル３２０Ａを選択して、その並進の方式を示す。スポット関数に供給される座標は、以下に示すＣ言語コードセグメント２ａに表わすように、第１の理想のハーフトーン格子２２０の理想セル１２０Ａの、第２の理想のハーフトーン格子４２０のチェッカーボードパターンの黒色部分に寄与すると考えられる部分に入るように変換される。
/* Code segment 2a */
Ｘ  ＝  （ｘ  ＋  ｙ）／２；
Y = (x - y)/2;
大文字のＸとＹは理想セル１２０Ａのセルスペースにおける座標であり、小文字のｘとｙは理想セル３２０Ａのセルスペースにおける座標である。
これらの値をスポット関数に供給し、分類した後、通常の０から２５５の範囲ではなく、０から１２７までの範囲の閾値を割り当てる。これは、理想セル３２０Ａから取った値が理想セル１２０Ａにある全ての閾値のうちの半分にのみ適用されているためである。
【００３８】
奇数番号の理想セル３２０Ｂの場合には、理想セル１２０Ａの中に位置するように四つのピースに分割されるものとして図示してあり、元の第１の理想のハーフトーン格子２２０の座標に戻すための変換が下記のＣ言語コードセグメント２ｂに示すようになる点を除いて、プロセスは同様である。
/* Code segment 2a */
Ｘ  ＝  （ｘ  ＋  ｙ）／２  ＋  １；
if (X > 1)X = X - 2;
Y = (x - y)/2 + 1;
if (Y > 1)Y = Y - 2;
閾値は１２８から２５５の範囲で割り当てられる。
【００３９】
この時点で、白色のドットと黒色のドットは共に元の第１のハーフトーン格子２２０の一つの理想セル１２０の中に完全に取り込まれたことになる。すなわち、黒色と白色のチェッカーボードドットは第１のハーフトーン格子２２０の理想セル１２０の大きさにごく近づく。それらのドットの大きさにはほとんどばらつきはない。
スポット関数が５０％グレイレベルでチェッカーボードパターンを発生させるものではない場合には、スポットの大きさのばらつきを減らすために以下に説明する二つの方式を採用する。
【００４０】
ＭＣＤの問題を修正する第３の方式
次に、ＭＣＤの問題によって生じるパターンを修正する第３の方式を説明する。理想セルの四つの角が合うところで、スポット関数によっては最小値又は最大値を有するので、黒色又は白色のハーフトーンドットの中心は四つの理想のハーフトーンセルが合うところに位置することになる。このようにして一つのハーフトーンドットを二つ又は三つのピースではなく、四つのピースに分割すると、ＭＣＤの問題は一層悪化する。
そのようなスポット関数に伴うもう一つの問題は、ハーフトーンドットが非常に小さいときにハーフトーンドットの分割が起こることである。従って、若干の画素の大きさの誤差はハーフトーンドットの総体的な大きさに対して大きい。経験によれば、そのような状況では、誤差はより目に見えやすいことがわかっている。
そこで、この第３の方式の目的は、スポット関数の実行を変更することにより、そのようなスポット関数によって起こる問題を減少させることである。
【００４１】
先の場合と同様に、デジタルセルの中の総称画素の座標を対応する理想セルのセルスペース座標（ｘ，ｙ）に変換する。次に、下記のＣ言語コードセグメント３を使用して、ｘ及びｙをスポット関数に供給する前にｘとｙを修正する。
/* Code segment 3 */
ｘ  ＝  ｘ  ＋  １／２  ；
y = y + 1/2;
ｉｆ  （ｘ  ＞  １）ｘ  ＝  ｘ  −  ２；
if (y > 1)y = y - 2;
このｘ座標及びｙ座標の変換は、スポット関数の最小値又は最大値を理想のセル格子の四角領域から離して、理想セルの内側に向かって移動させる。その結果得られるハーフトーンドットはグレイレベルによっては依然として理想セルの境界を越えているが、越えるときにより大きくなるので、相対誤差はさほど顕著ではなくなる。図１のハーフトーンドットはそのようにしてオフセットされている。
【００４２】
上記のコードセグメント３では、ベクトル（１／２，１／２）を加算することにより画素座標をオフセットさせる。そのようなベクトルを画素の座標に加算した後、画素の座標を理想セルを含む座標の範囲内に戻せば、そのようなベクトルの使用は有利であろう。理想セルにおける座標がＡからＢの範囲にある場合、値Ｂ−Ａを各画素座標に繰り返し加算又は減算してゆき、その座標をＡからＢの範囲に戻す。コードセグメント３の例では、Ａは−１に等しく、Ｂは１に等しいので、画素座標ｘ及びｙを−１から１の範囲にするために、必要に応じて値２＝１−（−１）を減算することになる。
【００４３】
ＭＣＤの問題を修正する第４の方式
次に、ＭＣＤの問題によって生じるパターンを修正する第４の方式を図３を参照しながら説明する。図２についていえば、この方式は、各理想セル１２０に等しい数又はほぼ等しい数の総称画素１１０を割り当てた後に採用されると、ドットの大きさをほぼ一定にすることを保証する。分割セル方式とは異なり、この第４の方式はほぼ全てのスポット関数と共に使用できる。
【００４４】
スーパータイル１４０の境界１４０Ｂ（図３）がデジタルセル１３０Ｂを分割するならば、スポットオフセット方式と同様に、この方式も修正しなければならない。ここでも、スーパータイルにより分割されているデジタルセルを処理するときには、コードセグメント１ａ及び１ｂの並進コードを使用して、所定のデジタルセルの中の全ての総称画素を一組の連続する画素位置へ移すことになる。そのような全ての画素座標がコンピュータメモリで表示される場合、次に説明する方式の動作に先立って全ての画素座標について上記の動作を実行するものと仮定する。方式は、スーパータイルの中の複数のデジタルセルから一つの「モデル」デジタルセルを選択することにより始まる。モデルセルは、所定のデジタルセルを選択すること、無作為に一つのデジタルセルを選択すること、又はデジタルセルに含まれている画素と、対応する理想セルの場所、他のあらゆる有用な情報とに基づいてモデルデジタルセルを選択することを含む様々な方法のいずれかにより選択されれば良い。ただし、選択の方法は上記の場合にのみ限定されるのではない。
【００４５】
説明の便宜上、対応する理想セルの一つの角が装置座標（０，０）を有しているような所定のデジタルセルをモデルデジタルセルとして選択する。この方式の残る部分は、Ｃ言語で書かれた下記のコンピュータ原始コードセグメント４を参照することにより最も良く理解されるであろう。このコードセグメント４は数回のコード参照を含む。
【００４６】
0003643383.tif 000002
0003643383.tif 000003
0003643383.tif 000004
0003643383.tif 000005
0003643383.tif 000006
0003643383.tif 000007
0003643383.tif 000008
0003643383.tif 000009
0003643383.tif 000010
【００４７】
Ｍと呼ばれるモデルデジタルセル、すなわち、「モデルセルＭ」を選択したならば、そのデジタルセルＭの中の総称画素をコンピュータプログラムにおいて記録のアレイとして表わす。この場合、それぞれの記録は一つの総称画素を表わしている。上記のコードセグメント４では、そのような記録をコード参照４．２における「ｐｉｘｅｌＥｌｅｍｅｎｔ」宣言により規定している。このＰｉｘｅｌＥｌｅｍｅｎｔ構造の「ｘ」フィールド及び「ｙ」フィールドは、表わすべき画素のｘ装置スペース座標及びｙ装置スペース座標を記憶するために使用される。次に、記録ごとにその記録と共に記憶されているｘ装置座標及びｙ装置座標を理想セルスペース座標に変換し、それらをスポット関数への入力とする。その後、スポット関数により計算した結果を記録中の、「ｓｐｏｔＶａｌｕｅ」と名付けられたフィールドに記憶する。次に、アレイ中の記録をアレイのｓｐｏｔＶａｌｕｅフィールドに従って、ｓｐｏｔＶａｌｕｅフィールドが最小である記録がアレイの最初の要素となり、その後に、ｓｐｏｔＶａｌｕｅフィールドが次に小さい記録が続き、さらにその後もｓｐｏｔＶａｌｕｅフィールドが小さい順に並んでゆくように分類する。このような分類方式は当業者には良く知られている。次に、各ｐｉｘｅｌＥｌｅｍｅｎｔ記録のフィールド「ｏｌｄＲａｎｋ」をＰｉｘｅｌＥｌｅｍｅｎｔ記録のアレイにおけるその記録の索引によって充填する。アレイの先頭の記録の場合、索引は０であり、アレイ中の次の記録の索引は１である。その後も同様にして順次索引が付されている。この索引をアレイ中の総称画素の「ランク」という。総称画素のランクは、後に、その総称画素に関する閾値アレイ中の閾値を確定するために使用される。この閾値が、今後は、どのグレイレベルで画素が黒色から白色に変わるかを決定することになるのである。全体として見れば、全ての画素についてのランク付け値は、ハーフトーン化画像に表わされる様々に異なるグレイ値についてハーフトーンドットを形成するために使用される黒色総称画素の分布を決定する。
【００４８】
次に、記憶したアレイの要素に基づいて二重連係リストを作成する。この二重連係リストは、先に述べたｐｉｘｅｌＥｌｅｍｅｎｔ記録により規定されるのに加えて、コード参照４．１の「ＧｅｎｅｒｉｃＬｉｓｔ」宣言により規定される第２の型の記録から形成される。ＧｅｎｅｒｉｃＬｉｓｔ記録は、そのようなリストにおける次の要素と先行要素を記録する「ｎｅｘｔ」及び「ｐｒｅｖｉｏｕｓ」と名付けられたフィールドと、「ｅｌｅｍｅｎｔ」フィールドにリストアップされるべきデータを記録するフィールドとを有する。要素フィールドとしては様々な種類のものが考えられる。この特定の例では、要素フィールドは、ｐｉｘｅｌＥｌｅｍｅｎｔ記録に対するポインタ又はそのアドレスである。従って、ＧｅｎｅｒｉｃＬｉｓｔ記録の二重連係リストを形成することになり、それぞれの記録は独自の第２のｐｉｘｅｌＥｌｅｍｅｎｔ記録を参照する。さらに、このリストにより表わされるそれらの第２のｐｉｘｅｌＥｌｅｍｅｎｔ記録の順序は、第１の分類済アレイにおけるｐｉｘｅｌＥｌｅｍｅｎｔ記録の順序と同じである。そのような二重連係リストを作成する方法は当業者には自明であろう。（本明細書にも参考として取り入れてあるＶａｎ  ＷｙｋのＤａｔａ  Ｓｔｒｕｃｔｕｒｅ  ａｎｄ  Ｃ  Ｐｒｏｇｒａｍｓの第３章から第５章を参照。）
【００４９】
上記の二重連係リストにおける先頭のＧｅｎｅｒｉｃＬｉｓｔ記録のアドレスを含むコードセグメント４の変数はＬＭと名付けられている。従って、このリストをリストＬＭという。ここで、閾値アレイのうち、デジタルセルＭに対応する部分を充填することができる。リストＬＭに表わされている総称画素ごとに、対応するｐｉｘｅｌＥｌｅｍｅｎｔ記録のｏｌｄＲａｎｋフィールドから閾値を計算する。デジタルセルＭの中の総称画素の総数をＮとすれば、そのような画素に関する閾値アレイ値はＣｅｉｌ（ｏｌｄＲａｎｋ *２５５／Ｎ）となる。
【００５０】
その後、この第４の方式の残る部分は、デジタルセルＭとは異なる各デジタルセルを、画素の閾値を計算するステップまで、同じようにして処理するように進行してゆく。そこで、モデルデジタルセルＭとは異なるＣと呼ばれるデジタルセルを選択して、そのセル（選択したセルＣともいう）に関連して方式の残る部分を説明する。尚、モデルセルＭとは異なる全てのデジタルセルについて下記の手順を繰り返さなければならないということに留意すべきである。
【００５１】
次に、選択したセルＣからｐｉｘｅｌＥｌｅｍｅｎｔ記録のアレイを、上記のモデルセルＭについてそのようなアレイを作成したのと全く同じ方式で作成し、分類し、ランク付けする。その後、選択したセルに基づいて（アレイ中の要素とリスト中の要素とが同じ順序になるように）アレイ中の要素を参照する二重連係リストを、モデルセルＭについて実行したのと全く同じ方法で作成する。原始コードセグメント４では、このリストの先頭の記録をＬＣと呼んでいる。以後、選択したセルＣについての二重連係リストをリストＬＣという。
【００５２】
選択したセルＣの総称画素に対応する閾値アレイの場所は、モデルセルＭについて実行されたようには、この時点で充填されない。それらを充填する前に、さらに処理を実行する。項（ｔｘ，ｔｙ）を使用して、装置座標の中で、選択した理想セルＣの下方の角に加算したときにその項をモデル理想セルＭの下方の角へ並進させるベクトルを指定する。セルが装置座標と平行であれば、双方の理想セルの左下角を選択する。ｔｘ及びｔｙは概して整数ではないことに注意すべきである。
【００５３】
この方式の次のステップでは、リストＬＣの各ｐｉｘｅｌＥｌｅｍｅｎｔ記録の各ｘフィールドにｔｘを加算すると共に、リストＬＣの各ｐｉｘｅｌＥｌｅｍｅｎｔの各ｙフィールドにｔｙを加算する。これは、選択したセルＣがモデルセルＭの上に重ね合わされるようにセルＣを並進させる効果を有する。これにより、選択したセルＣにおける総称画素をモデルセルＭの総称画素のランク付けを模倣する方法でランク付けすることができ、選択したセルＣとモデルセルＭの双方で同じグレイ強さが示される場合には、セルＣのドットピースはモデルセルＭのドットピースと確実に同一の形状と大きさになる。
【００５４】
以上説明したようにリストＬＭ及びＬＣを準備したならば、選択したセルＣを処理する際の残る作業を実行するために、コード参照４．５の「ＰｒｏｃｅｓｓＯｎｅＣｅｌｌ」と名付けられた手順を呼び出す。この手順ＰｒｏｃｅｓｓＯｎｅＣｅｌｌは、実際には、二つの引数として作成したばかりの二つのリストＬＭ及びＬＣを取り出す。
ＰｒｏｃｅｓｓＯｎｅＣｅｌｌがどのように進行するかを説明する前に、コード参照４．３及び４．４を簡単に説明する。尚、ＬＭ及びＬＣを作成するための原始コードは当該技術において良く知られている方法で実行されるので、コードセグメント４の中には明示して挙げられていない。
【００５５】
先に述べたコード参照４．２とコード参照４．５との間のリスト作成における原始コードの部分については、まだ説明していなかった。コード参照４．３の下の原始コードは、方式が進む過程で生成される様々なリストを操作する手順から構成される。それらは、従来の用途で使用されていた手順に類似する標準的な手順である。それらの手順は本発明の一部として特許請求されてはいないが、完璧を期するために、原始コードのリストの中に提示されている。
【００５６】
コード参照４．４の下のコードをＰｒｏｃｅｓｓＯｎｅＣｅｌｌ手順の中で使用するものとして後に説明するが、ここでは、その動作方式についてコード参照４．５に関連させながら説明する。
コード参照４．５の第１の部分は、手順の本体で使用される様々な変数を宣言する。詳細にいえば、変数ＬＬ，ｆｉｎａｌＬｉｓｔ，ｈｅａｄＬＭ，ｔａｉｌＬＭ及びｑがＧｅｎｅｒｉｃＬｉｓｔ型となるように宣言する。すなわち、それらは様々な型のリストとなる。変数ｏｄｄＣａｓｅ，ｎｅｗＲａｎｋ及びｎＴｏｔａｌは整数として宣言される。それらの変数の意味については使用されるときにその都度説明する。
【００５７】
上記の変数の宣言に当たって、そのいくつかをある値に初期設定する。たとえば、リスト変数ＬＬ及びｆｉｎａｌＬｉｓｔは、プログラムの中でそれらのリストの中にはまだ何も存在していないことを意味するために使用されるコードであるＥＭＰＴＹに初期設定される。次に、手順ＰｒｏｃｅｓｓＯｎｅＣｅｌｌにより実現される本発明の部分の方式を一般的な用語で説明する。その後、原始コードリスティングの特定の部分を詳細に説明する。
【００５８】
以下の説明中、「グレイレベル」というときがあるが、グレイレベルは数多くの目盛又は数の範囲によって数値で表現できる。モデルセルＭの中の総称画素の数（ｎＴｏｔａｌという）に基づく目盛を使用すると好都合である。グレイレベル０は全くの白色であり、グレイレベルｎＴｏｔａｌは全くの黒色である。中間グレイレベルｇは、それぞれのｎＴｏｔａｌのうちｎ個の総称画素が黒色であるときに発生されるグレイに対応する。従って、モデルデジタルセルＭがグレイ強さｇを表わすようにさせるためには、ランクがｇ以下である全ての総称画素を黒色に変え、残る画素を白色のままにしておく。これにより、グレイレベルと、先にｐｉｘｅｌＥｌｅｍｅｎｔ構造におけるフィールドｏｌｄＲａｎｋとして表わしたデジタルセルの画素のランクとの間に密接な関係が成立する。この画素のランク付けについては以下にさらに説明する。
【００５９】
本発明の方式によれば、所定のグレイレベルに対して選択したセルＣにより発生されるドットピースがモデルセルＭにより発生されるドットピースと同じ大きさ、同じ場所になるように、選択したセルＣにおける総称画素のランク付けを変更する。所定のグレイレベルｇに対して、モデルセルＭで発生されるドットピースが唯一つであり且つ選択したセルＣで発生されるドットピースが唯一つである場合、それら二つのドットピースは自動的に同じ大きさになるので、それ以上の作業を実行する必要はない。ところが、所定のグレイレベルｇにおいてモデルセルＭで二つ以上のドットピースが発生される場合には、この方式は、同じクレイレベルｇに対して、セルＣで発生されるドットピースがセルＣにあったときと等しい大きさになり且つほぼ同じ場所にそれぞれ位置するように保証する。「ドットピース」という用語は、先の用語の章に詳細に定義されている。
【００６０】
上記の目的を達成するために選択したセルＣにおける総称画素のランク付けを変更するためには、グレイレベルごとに、モデルセルＭの各ドットピースを構成する総称画素の数と場所がわかっていなければならない。このために、所定のグレイレベルに関して一つのドットピースの中の全ての総称画素に対応するｐｉｘｅｌＥｌｅｍｅｎｔ構造のリストの形で各サブリストを含んでいるサブリストのリストとして、変数ＬＬを維持し、新たなグレイレベルごとに更新する。従って、たとえば、図１に示すように、デジタルセル１３０Ａの黒色総称画素は二つのドットピースを形成しており、主にハーフトーンドット７０Ａに入っている総称画素は９個あり、主にハーフトーンドット７０Ｄに入っている画素は一つである。この場合、リストＬＬは、ハーフトーンドット７０Ａの９個の画素を含む第１のリストと、ハーフトーンドット７０Ｄの一つの画素を含む第２のリストという二つのリストから構成されると考えられる。
【００６１】
この方式をあらゆるグレイレベルで機能させるために、リストＬＬの内容についてさらに変更を実施すべきである。グレイレベルが５０％黒色を越える場合、ハーフトーン化画像は、通常、白色の背景の上に黒色のハーフトーンドットがあるのではなく、黒色の背景の上にある白色のドットから構成される。５０％黒色を越えるグレイレベルについて本発明の方法を有効にするためには、白色ドット及び白色ドットピースを黒色ドットピースを制御するのと同じように制御しなければならない。このために、リストＬＬがある所定のグレイレベルｇにおける黒色ドットピースと、そのグレイレベル（ｎＴｏｔａｌ−ｇ）の白色ドットピースの双方を記述するサブリストを含むようにする。このように、リストＬＬは一度に二つの機能を果たすのである。
【００６２】
尚、この方式には、ＬＬの代わりに二つの別個のリスト、すなわち、白色ドットピースに対応するリストと、黒色ドットピースに対応するリストとを維持するような別の方式もある。当業者であれば、本発明をそのような方式に容易に変換できるであろう。スポット関数によっては、そのような方式のほうがすぐれていると思われる。
【００６３】
次に、本発明の方式のこのステップにおける実際の動作シーケンスを説明する。主な部分は、モデルセルＭの中に形成することができる各予想セルドットを考慮するメインループである。予想黒色セルドットは、リストＬＭの初めのｎ個の要素により形成されるドットである。尚、ｎは１からｎＴｏｔａｌ／２の範囲にある。予想白色セルドットは、リストＬＭの終わりのｎ個の要素により形成されるドットである。ｎは１からｎＴｏｔａｌ／２の範囲にある。これらのセルドットを考慮する順序は次の通りである。まず、リストＬＭの先頭の要素から構成される最小の黒色セルドットを考慮する。次に、リストＬＭの末尾の要素から構成される最小の白色セルドットを考慮する。その後、リストＬＭの初めの二つの要素から構成される次に小さい黒色セルドットを考慮する。続いて、リストＬＭの終わりの二つの要素から構成される次に小さい白色セルドットを考慮する。このシーケンスを、順次大きくなってゆく黒色セルドットと白色セルドットを考慮しながら続ける。
【００６４】
メインループを通過するたびに、リストＬＬは更新されて、現在考慮されている黒色セルドットと白色セルドットの総称画素の配列を表わすようになる。また、メインループを通過するたびに、選択したセルＣにおける総称画素のリストＬＣから新たな一つの総称画素が除かれて、新たなランク付けを与えられ、原始コードではｆｉｎａｌＬｉｓｔと呼ばれている別のリストに追加される。コードの実行が完了したとき、ｆｉｎａｌＬｉｓｔは選択したセルＣの全ての総称画素を含んでおり、各総称画素には所望の特性を有する新たなランク付けが与えられている。
【００６５】
リストＬＣから総称画素を選択し、それらに新たなランク付けを与える方式は、メインループの始めにリストＬＬがどのように更新されるかによって決まる。白色セルドットに対して黒色セルドットを考慮しているときには、この方法を変えても良い。まず、黒色セルドットの場合を考える。
黒色セルドットを考慮しているときには、リストＬＬにより表わされる黒色又は白色のセルドットの中にはないリストＬＭの先頭の総称画素ｐを選択する。次に、ｐに隣接する画素を含むリストＬＬのサブリストを見出す。ここで、隣接とは、二つの画素が重なり合っているか又は一つの辺を共有することを意味する。隣接性の条件はコード参照４．４の手順「Ａｄｊａｃｅｎｔ」により実現される。ｐに隣接する画素を含むＬＬの全てのサブリストをリストＬＬから除外する。次に、それらの除外したリストと画素ｐ自体とを原始コードではｎｅｗＬｉｓｔと呼ばれる一つのリストに併合し、リストＬＬに戻す。
【００６６】
次に、リストｎｅｗＬｉｓｔの中のいずれかの要素に隣接しており、原始コードではｑと呼ばれているリストＬＣの先頭の総称画素をリストＬＣから除外して、ｆｉｎａｌＬｉｓｔに導入する。この場合、総称画素ｑには、一つの黒色セルドットを考慮するためにメインループを実行した回数に等しい新たなランク付けを与える。このランク付けは、原始コードの変数ｎｅｗＲａｎｋを初期設定し、次に、この変数をループが二度実行されるについて一度ずつ単純に増分することにより計算される。
白色ドットを考慮するときの方式は、次に述べる点を除いて、上記の流れと同様である。総称画素ｐはリストＬＭの末尾の総称画素であるように選択されるが、ＬＬで表わされる総称画素のセットではない（先頭の画素ではない）。また、総称画素ｑも、ｎｅｗＬｉｓｔのいずれかの要素に隣接するリストＬＣの中の末尾の（先頭ではない）総称画素である。
【００６７】
上記のステップは先の原始コードリストの各部分と次のように関連している。コード参照４．７の後のコードリストがメインループである。これに先立って、二つの変数「ｈｅａｄＭ」及び「ｔａｉｌＭ」をそれらがリストＬＭの先頭と末尾をそれぞれ指示するように初期設定する。また、変数「ｂｌａｃｋＣａｓｅ」を１に設定する。ｂｌａｃｋＣａｓｅが１の値を有するとき、ループは次の黒色セルドットを考慮し、ｂｌａｃｋＣａｓｅが値０を有するときには、白色セルドットを考慮する。ｂｌａｃｋＣａｓｅの値はメインループの終了時に０と１の間で切り換えられるので、黒色セルドットと白色セルドットは確実に交互に考慮されるのである。
【００６８】
コード参照４．７におけるメインループの本体の開始時に、ｂｌａｃｋＣａｓｅが１の場合は変数ｐがｈｅａｄＭと同じ画素を表わすようにし、ｂｌａｃｋＣａｓｅが０の場合には変数ｐがｔａｉｌＭと同じ画素を表わすようにする。変数ｈｅａｄＭは、リストＬＬにより表わされる総称画素の組にまだ追加されていないリストＬＭの中の最初の画素を表わす。ｈｅａｄＭをｐに割り当てた後、次の時点では新たな総称画素が使用されるように、ｈｅａｄＭをｐの次の総称画素に設定する。ｔａｉｌＭについても同様の事象のシーケンスが起こる。
【００６９】
次に、コード参照４．８は、ＬＬの中の、総称画素ｐに隣接する要素を有するリストから成るリストを生成する。これは変数ＣＮとなる。次に、コード参照４．９では、ＬＮに含まれているリストをＬＬからそれぞれ除外し、リストｎｅｗＬｉｓｔに追加する。その後、総称画素ｐをｎｅｗＬｉｓｔに追加し、そのｎｅｗＬｉｓｔをリストＬＬの新たな要素として戻す。
次に、コード参照４．１０では、総称画素ｑをリストＬＣから除外し、ｆｉｎａｌＬｉｓｔに追加する。そこに示されている「ｉｆ」ステートメントは、この動作を、ｂｌａｃｋＣａｓｅが０であるか又は１であるかに従って二つの異なる方法で実行する。その相違は、第１の修飾要素を求めてリストＬＣを探索する順序（前から後へ又は後から前へ）にある。除外した画素ｑに割り当てられるランクはｎｅｗＲａｎｋ又はｎＴｏｔａｌ−ｎｅｗＲａｎｋである。
【００７０】
次に、コード参照４．１１では、メインループの終了時に、次にメインループを通過するのに備えて変数ｂｌａｃｋＣａｓｅ及びｎｅｗＲａｎｋを更新する。
続いて、コード参照４．１２では、メインループで処理されなかったリストＬＣ中の全ての総称画素を処理する。リストＬＭ又はリストＬＣのいずれかの総称画素がなくなったならば、メインループは終了する。場合によっては、リストＬＣはリストＬＭより多くの総称画素を含んでいることもある。そのときには、リストＬＣの残る未処理総称画素に、変数ｎｅｗＲａｎｋの現在値から始めて、順次ランク付けを与えてゆく。
【００７１】
これで、手順ＰｒｏｃｅｓｓＯｎｅＣｅｌｌの処理は完了する。この処理の後、閾値アレイのうち、選択したセルＣに対応する部分を、ＰｒｏｃｅｓｓＯｎｅＣｅｌｌにより戻されたｆｉｎａｌＬｉｓｔの総称画素の新たなランク付けから計算する。先に述べた通り、総称画素の閾値はＣｅｉｌ（ｎｅｗＲａｎｋ *２５５／ｎＴｏｔａｌ）である。尚、ｎｅｗＲａｎｋはその画素を表わすｐｉｘｅｌＥｌｅｍｅｎｔ構造の中のｎｅｗＲａｎｋフィールドから取った値である。
画素の場所はｐｉｘｅｌＥｌｅｍｅｎｔ構造のｘフィールド及びｙフィールドから求められるのであるが、ただし、選択したセルＣをモデルセルＭへ並進させるベクトルとして先に説明した（ｔｘ，ｔｙ）を考慮して、値ｔｘをｘフィールドから減じなければならないと共に、値ｔｙをｙフィールドから減じなければならない。
【００７２】
以上説明した本発明の様々な方式を組み合わせて利用されても良く、また、別個に利用されても良い。いくつかの角度範囲及び周波数範囲においては、他の場合に比べて、方式を組み合わせて利用するとより有用である。イメージセッタの分解能と、要求されるハーフトーン格子の周波数と、要求されるハーフトーン格子の角度とに基づいて、ある特定のタスクにどの方式を適用すべきか、又はどのような組み合わせで方式を適用すべきかをソフトウェアプログラムにより決定しても良い。
本発明の好ましい方式を説明したが、本発明の教示から様々な置き換えや代替えは当業者には明白であろう。従って、本発明は上述の実施例により限定されるものではなく、特許請求の範囲によってのみ限定される。
【図面の簡単な説明】
【図１】ドットが正しくない数の画素によって表示されている従来の技術による表示システムを示す図。
【図２】理想セルと関連するデジタルセルとの関係並びにセルドットとそれを含むデジタルセルとの関係を示す図。
【図３】一つのスーパータイルと、その中に含まれている理想のハーフトーンセル及び他のスーパータイルとの関係を示す図。
【図４】二つのハーフトーン格子により発生されるデジタルセルのチェッカーボードパターン。
【符号の説明】
１１０  総称画素
１２０  理想セル
１３０Ａ〜１３０Ｆ  デジタルセル
１４０  スーパータイル
１４０Ｂ  境界
１４０Ａ，１４０Ｂ  スーパータイル並進ベクトル
２２０  第１のハーフトーン格子
３２０Ａ，３２０Ｂ  理想セル
４２０  第２のハーフトーン格子
ＤＲ，ＤＬ  ピース
【図１】
0003643383.tif 000011
【図２】
0003643383.tif 000012
【図３】
0003643383.tif 000013
【図４】
0003643383.tif 000014