JPH05244402A - 必要な記憶装置の量を低減する方法 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】 ハーフトーンプロセス中、しきい値にアクセ
スする速さおよび容易さを維持しながら、しきい値を記
憶するのに必要な記憶装置の量を大幅に減少させる。 【構成】 本発明の画像形成方法および装置では、しき
い値のディジタルハーフトーンセルを作成し、ハーフト
ーンセルの四隅の位置から決まる複数のタイルに分解す
る画像作成装置が設けられている。例えば５個のタイル
３５０，３５５，４００，４０５及び４１０は共に設置
したとき、ハーフトーンセルの周りに境界ボックスを形
成する。これらタイルはしきい値のしきい値列として設
置され、その列の幅は隣接タイルの行を横断するしきい
値の連鎖の中のしきい値の数に等しく、列の高さはハー
フトーンセルの頂点の間のｘ軸増分とｙ軸増分との最大
公分母に等しい。しきい値列はハーフトーンプロセス中
後の参照のため記憶装置に記憶される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明の方法および装置は、ディ
ジタルハーフトーン方式の分野に関する。更に詳細に
は、本発明は、最適な仕方でハーフトーンセルを格納
し、性能を維持しながらメモリ空間を節約することに関
する。

【０００２】

【従来の技術】ハーフトーンの手法は、写真のような、
画像の連続色調を、有限数の色を使用して個々の部分か
ら成る形で印刷する印刷業界で広く使用されている。た
とえば、新聞に載っている写真のような単色画像は二つ
の色、黒および白、を使用して表されており、典型的に
は白紙上に黒いドットを生成することにより作られる。
雑誌または新聞で見られるもののようなカラー画像は、
わずかな有限数の色で表されている。ハーフトーン方式
は画像を生成するために空間積分を活用している。空間
積分は、大きな視距離から小さな区域を見るとき目によ
って行われており、この場合目は小さい区域の中の細か
い詳細を平均化し、その区域の全体の強さおよび色を記
録している。

【０００３】複数の表示要素をハーフトーン格子と呼ば
れる小さい格子またはマトリックスに組分けすることに
より、表示出力の空間解像度が減少し、区域内の表現し
得る全体の強度レベルまたはグレーレベルが増大する。
たとえば、４表示要素を2×2マトリックスに組分けする
ことにより、表示出力の空間解像度は半分だけ減少する
が、表現し得るグレーレベルの量は５に増大する。ハー
フトーン格子は、ハーフトーンセルと言われる小マトリ
ックスの一様な格子を、表示装置の出力画素列（今後表
示空間と言う）上にマッピングすることにより規定され
る。ハーフトーン格子には、頻度（表示空間の単位尺度
あたりのハーフトーンセルの数）および角度（表示空間
の座標系に対する格子の向き）がある。表示空間の各表
示要素（「画素」と言う）はハーフトーンセル内の一要
素に対応する。表示画面の一区域を、区域内部の画素の
一定量を所定のパターンおよび順序でオン（たとえば、
「白」）またはオフ（たとえば、「黒」）することによ
り、灰色の色合いで近似させることができる。プリンタ
のような表示装置では、背景は画像がその後白紙上に印
刷されるべく出力されるという事実を反映して白に初期
設定され、作動される画素は白紙上に印刷されるインク
を反映して黒の「ドット」として出力される。説明の目
的で、以下の説明では作動される画素を白ということに
する。しかし、当業者には、システムおよび出力装置に
より、作動される画素を他の所定の色とすることができ
ることが明かである。特に、対応する印刷画像では、作
動された画素は黒になる。

【０００４】数値的には、セル内部で表現されるグレー
レベルは白である画素の数のそのセル内の画素の総数に
対する比である。セルのグレー値が黒から白に変わるに
つれて、各セル内の画素がますます多く黒から白に所定
の順序で変化する。画素が黒から白に変わってグレーレ
ベルを上げる順序はユーザによりドットまたはスポット
関数と呼ばれる数学関数を用いて指定される。スポット
関数は、一つの値がハーフトーンセルの各表示要素に関
連している複数のしきい値を計算するのに使用される。
しきい値の種々な大きさは画素が黒から白に変化してグ
レーレベルを増大するシーケンスを指示する。すなわ
ち、しきい値は所定強度レベルを表す値と比較される。
特定の表示画素に関連するしきい値が区域の所要強度レ
ベルより大きければ、画素は作動される。ハーフトーン
プロセスについてのこれ以上の事項については、Foley
等のComputer Graphics, Principles and Practice, Se
condEdition, pp.569〜573(Addison - Wesley Publishi
ng 1990); UlichneyのDigital Halftoning(MIT Press 1
987); Adobe Systems, Inc., POSTSCRIPT Language Ref
erence Manual, pp.84〜87(Addison - Wesley Publishi
ng 1986)を参照されたい。

【０００５】典型的には、異なる各強度レベルに対する
ハーフトーンセルの一つの２進表現は、ユーザ指定のス
ポット関数、ハーフトーン頻度、およびハーフトーン角
度に従って計算される。この２進表現をグレーパターン
と呼ぶ。可能なすべての強度レベルに対するグレーパタ
ーンの集まりをあらかじめ計算し、記憶装置に格納す
る。ハーフトーン画像を作成するときは、特定の強度に
対するグレーパターンを必要に応じて記憶装置から検索
して作動すべき画素を決定する。ハーフトーンセルを構
成する画素が多ければ多いほど、表現し得る異なる強度
の数が大きくなり、グレーパターンを格納するのに必要
な記憶装置の量が多くなる。スポット関数により作られ
るしきい値はハーフトーンセルの中心に対するハーフト
ーンセル内の画素の位置によって決まる。各ハーフトー
ンセルが表示空間内の画素と一貫して整列していれば、
わずかなハーフトーンセルを使用して表示空間全体にわ
たって複製することができ、一つだけのしきい値を使用
して作動して画像全体を作る画素の順序を決定すること
ができる。しかし、典型的にはハーフトーン格子は表示
空間格子と正確には合っていない。各ハーフトーンセル
を表示空間格子と一致させることは、ハーフトーンセル
の格子のサイズが通常、表示空間と同じ格子サイズでは
なく、ハーフトーンセルのマトリックスが一般的には表
示空間格子とは異なる角度の向きになっているため、複
雑なプロセスが必要である。表示空間の各画素について
しきい値を作成すれば、セル内の画素位置の可能な各形
状を処理するのに無限量の異なるハーフトーンセルを計
算しなければならなくなる。

【０００６】ハーフトーンセルを表示空間と整列させる
問題を図１により図解する。ハーフトーンセルは、一定
角度で表示空間の画素のマトリックスにマッピングされ
ている。セル50の一つの頂点は画素位置（図１では画素
位置は格子線の交差点に生じている）に直接マッピング
されるが、残りの頂点30、40、60はそうではない。同様
に、頂点10、20、30、40を有する隣接ハーフトーンセル
は画素マトリックスと精密には並ばない。各ハーフトー
ンセル内の相対画素位置は、ハーフトーンセルごとに変
わるので、各画素位置について作成されたしきい値はハ
ーフトーンセルごとに異なることになる。この問題を克
服するにはハーフトーンセルを最小限の誤差で画素マト
リックスに整列させる手法が考え出されており、それで
はハーフトーンセルの頂点を最も近い画素に合わせてい
る。これは図２を参照することにより見ることができ
る。ユーザ指定のハーフトーン頻度に直接対応するセル
の一辺の長さRdおよび座標空間に関する所要ハーフトー
ンセル角度θdを使用すれば、 修正セル頻度値は下記方
程式により決まる。

【０００７】 ａ＝INT[Rd cos(θd)] ｂ＝INT[Rd sin(θd)]

【０００８】ただしRdはハーフトーンセルの一辺の所要
長さであり、 θdは表示空間に対するハーフトーンセル
の所要角度であり、 INTは頂点を最も近い画素に仕上げ
る整数近似関数を表す。「ａ」値は第１の軸（たとえ
ば、ｘ軸）に沿う一頂点から隣接頂点までの増分整数量
（画素のような単位で表す）を表し、「ｂ」は第２の軸
（たとえば、ｙ軸）に沿う増分整数量を表す。したがっ
て、ハーフトーンセルの実際の長さ(Ra)はSQRT(a2+b2)
に等しく、実際の角度はθaである。ここでθaはARCTAN
(b/a)に等しく、SQRTは平方根関数を表し、 ARCTANは逆
正切関数を表す。 今後θdを「所要ハーフトーン角度」
と言い、θaを「実際のハーフトーン角度」と言う。Rd
を「所要セル頻度」と言い、Raを「実際のセル頻度」と
言う。実際のハーフトーン角度θa、実際のセル頻度R
a、および値ａおよびｂを使用すれば、 調節ずみハーフ
トーンセルを構成することができる。調節ずみハーフト
ーンセルは、図３に示すように、表示空間を横断してハ
ーフトーンセルの表示空間のマトリックスへのマッピン
グを完成するように構成することができる。構成される
実際のハーフトーンセルは等サイズのものであり、表示
空間の画素と整合しており、これにより一つの単独しき
いマトリックスをハーフトーンセルに適用することがで
きる。

【０００９】この手法に対する欠点はハーフトーンセル
を調節することにより導入される誤差である。実際のハ
ーフトーンセルの表示座標空間に対する角度 (θa)およ
び実際のハーフトーンセルの一辺の長さ(Ra)は所要角度
および所要頻度(θdおよびRd)とはわずかに異なり、わ
ずかな誤差が導入される。実際の頻度Ra、実際の角度θ
aと所要頻度Rdおよび所要角度θdとの間の誤差は、図４
に示すように、複数のハーフトーンセルから構成される
「スーパーセル」を構成することにより減らすことがで
きる。スーパーセルの表示空間に対する角度およびハー
フトーンセルの実際の頻度は各スーパーセルに含まれる
ハーフトーンセルの数を増やすことによりユーザの所要
角度および頻度に極めて近くなるように調節することが
できる。スーパーセルが大きくなるほど調節誤差は小さ
くなるが、しきい値を含むスーパーセルを格納するに必
要な記憶装置のサイズは大きくなる。典型的には、所定
の許容差を設定し、許容差内に入るスーパーセルを作成
するという妥協がユーザにより行われる。たとえば、ユ
ーザ指定角度が15゜であり、許容差が 0.1゜に設定され
れば、14.99゜から15.01゜までの範囲内の角度を有する
スーパーセルが作製される。一旦ハーフトーンセルのサ
イズが決まれば、セルは表示空間にわたって共に「縫い
合わされる」。

【００１０】

【発明が解決しようとする課題】しきい値列を分配する
に必要な記憶装置の量はシステムのコストおよび性能に
関して非常に重要である。ユーザが指定する角度および
頻度の許容差により、情報の格納に多量の記憶装置を取
上げる可能性がある。加えて、典型的な格納手法は表示
空間に対するハーフトーンセルの角度に従って変動す
る。それ故本発明の目的は、ハーフトーンセルを最少量
のメモリ空間に格納する方法および装置を提供すること
である。本発明の目的は、ハーフトーンセルを迅速且つ
容易に検索できるよう最少量のメモリ空間を利用して格
納する方法および装置を提供することである。

【００１１】

【課題を解決するための手段】本発明の方法および装置
では、しきい値のディジタルハーフトーンセルを作成し
て、そのハーフトーンセルの四隅の位置から決まる複数
のタイルに分解する画像発生装置が設けられている。タ
イルはハーフトーンセルの周りに境界ボックスを形成す
る。これらのタイルは、連続したタイルの行にわたるひ
と続きのしきい値の中のしきい値の数に列の幅が等し
く、ハーフトーンセルの頂点の間のｘ軸増分とｙ軸増分
との最大共通分母に列の高さが等しい、しきい値のしき
い値列内に配列される。しきい値列をハーフトーンプロ
セス中に以後の参照のために記憶装置に記憶する。本発
明の方法および装置によりハーフトーンプロセス中しき
い値にアクセスする速さおよび容易さを維持しながら、
しきい値を記憶するために必要な記憶装置の量は大幅に
減少する。

【００１２】

【実施例】記数法および用語 以下の詳細な説明は主として、コンピュータメモリ内部
のデータビットに関する演算のアルゴリズムおよび記号
表現で示してある。これらアルゴリズムの記述および表
現は、当業者がデータ処理技術において自身の仕事の要
旨を他の当業者に最も有効に伝えるのに使用する手段で
ある。アルゴリズムはここでは、および一般に、所要結
果に導く階程の首尾一貫したシーケンスであると考えら
れている。これらの階程は物理量の物理的操作を必要と
するものである。普通、必ずしも必要ではないが、これ
らの物理量は、格納し、転送し、組合わせ、比較し、お
よびその他の場合操作することができる電気信号または
磁気信号の形を取っている。主として共通利用の理由
で、これら信号をビット、値、要素、記号、文字、項、
数などと言うのが時々便利であることがわかっている。
しかし、これらすべておよび同様の用語は適切な物理量
と関連さすべきであり、これら数量に加えられた単に便
利なラベルであるということに留意すべきである。更
に、行われる操作は屡々、加法または比較のような言葉
で言われるが、これらは一般に人間のオペレータが行う
知能操作に関係している。人間のオペレータのこのよう
な能力は、本発明の部分を形成するここに述べるどんな
操作においても、必要ではなく、ほとんどの場合望まし
くない。操作は機械演算である。本発明の演算を行う有
用な機械には汎用ディジタルコンピュータまたは同様の
装置がある。すべての場合、コンピュータを操作する際
の方法動作と計算それ自身との間の区別に留意すべきで
ある。本発明は、電気信号または他の（たとえば、機械
的、化学的）物理信号を処理して他の所要物理信号を発
生する際にコンピュータを操作する方法階程に関する。
本発明はこれらの操作を行う装置にも関係している。こ
の装置は、必要な目的に対して特に構成することがで
き、またはコンピュータに格納されているコンピュータ
プログラムにより選択的に活性化されまたは再構成され
るような汎用コンピュータから構成することができる。
ここに提示するアルゴリズムは特定のコンピュータまた
は他の装置と本来的に関連しているものではない。特
に、種々の汎用機械をここに教示するところに従って書
かれたプログラムを用いて使用することができ、または
一層専用の装置を作って必要な方法階程を行うのが一層
便利であることが証明されることもある。多様なこれら
機械に必要な構造は下に示す説明から明らかになる。

【００１３】全般的システム構成 図５は、本発明によりディジタルハーフトーン画像を作
成する典型的なコンピュータ基準のシステムを示す。
三つの主要構成要素から成るコンピュータ101が示され
ている。主要構成要素の第１は、 情報を適切な構造形
態でコンピュータ101の他の部分と連絡し合うのに使用
される入力／出力(I/O)回路102である。コンピュータ10
1の一部として中央処理装置(CPU)103および記憶装置104
も図示されている。これら後の二つの要素はほとんどの
汎用コンピュータおよびほとんどすべての汎用コンピュ
ータに典型的に見られるものである。 事実、コンピュ
ータ101に入っている幾つかの要素をこの広い部類のデ
ータ処理装置の代表とするつもりである。コンピュータ
101の役割を満たす適切なデータ処理装置の特定の例に
は、カリフォルニヤ州マウンテンビューのSun Microsys
tems Inc. により製造されている機械がある。類似の能
力を有する他のコンピュータは勿論率直に以下に記す機
能を行うのに適合させることができる。

【００１４】また、図５に示されているのは入力装置10
5であり、 典型的な実施例ではキーボードとして図示さ
れている。しかし、入力装置は実際にはカードリーダ、
磁気または紙テープリーダ、または他の周知の入力装置
（勿論、他のコンピュータを含む）とすることができる
ことを理解すべきである。大量記憶装置106がI/O回路10
2に結合されてコンピュータ101に対する付加的記憶能力
を提供している。大量記憶装置には他のプログラムまた
は類似のものを入れることができ、磁気または紙テープ
リーダまたは他の周知の装置の形態を取ることができ
る。大量記憶装置106の内部に保持されているデータ
は、該当する場合、記憶装置104の一部としてコンピュ
ータ101に標準的仕方で組入れることができることが認
められる。 カーソルコントロール108aは命令モードを
選択したり入力データを編集したりするのに使用され、
一般に情報をシステムに入力する一層便利な手段とな
る。その他、メッセージまたは他の通信文をユーザに対
して表示するのに使用される表示モニタ107が示されて
いる。 このような表示モニタは幾つかの周知の種々なC
RT表示装置のすべての形態を取ることができる。好適に
も、表示モニタ107は、図形画像、すなわち、本発明の
プロセスにより作られるディジタルハーフトーン画像を
も表示することができる。ラスタ表示モニタは、所定の
仕方で「オンにされ」て画像を形成する。画素と呼ばれ
る、表示要素のマトリックスから構成されている。表示
すべき画像を表す画像データは最初フレームバッファ 1
08に書かれる。画像データは作動すべき各表示要素の
色、強度、および位置を識別する。表示制御装置109は
フレームバッファから画像データを読取り、 画素を作
動させて画像を作成する。

【００１５】プロセスの説明 本発明のディジタルハーフトーンプロセスの一好適実施
例を図８および図９の流れ図を参照して説明することに
する。 ブロック200でユーザは、作成すべきハーフトー
ンセルの頻度、表示空間格子に対して方位を定めるべき
ハーフトーンセルの角度、および角度が限界内で変わる
ことができ且つなお限界内にあることができる許容差を
指定する。たとえば、ユーザは、インチあたり60ハーフ
トーンセルのハーフトーン頻度を角度15゜、許容差0.01
°で指定することができる。たとえば、図２を参照する
と、所要ハーフトーンセルは頂点すなわち端点30、40、
50、および60を備えている。図８のブロック210で、 表
示空間格子に合わせて調節されたハーフトーンセルが作
成されている。調節ずみハーフトーンセルは端点80、9
0、50、および70を備えている。調節ずみハーフトーン
セルの端点は次の方程式を用いて決定される。

【００１６】 ａ＝INT[Rd cos(θd)] ｂ＝INT[Rd sin(θd)]

【００１７】ただしRdはハーフトーンセルの辺の所要長
さであり、 θdはハーフトーンセルの表示空間に対する
所要角度を表し、INT は値を最も近い整数に近似させる
整数近似関数を表す。「ａ」値はハーフトーンセルの一
つの頂点、たとえば、頂点50から隣接頂点、例えば頂点
70までの第１の軸（たとえば、ｘ軸）に沿う増分整数量
を表示空間の単位（たとえば、画素）で示し、「ｂ」は
第２の軸（たとえば、ｙ軸）に沿う増分整数量を表す。
決定された頂点に対してセルの対角線方向の次の頂点、
頂点80、を決定するには、ａの値を第２の軸に沿う増分
整数量として使用し、ｂの値を第１の軸に沿う増分整数
量として使用する。同様に、次の頂点、頂点90、はａの
値を第１の軸に沿う増分量、ｂの値を第２の軸に沿う増
分量として使用する。

【００１８】図６に示したように、このプロセスを続け
てすべての隣接頂点50、70、80、90、および境界ボック
スを決定することができる。境界ボックスは、調節ずみ
ハーフトーンセルを縁330、335、340、および345で包囲
するｘ軸およびｙ軸の方向を向く正方形である。境界ボ
ックスの各辺はハーフトーンセルの頂点と交差し、境界
ボックスの各辺が向いている軸はハーフトーンセルの対
応する辺の主軸である。各辺の長さはａ＋ｂの大きさで
ある。後に説明するように、境界ボックスは表示空間に
マッピングされる。計算時間および経費を節約するに
は、単一境界ボックスの頂点を決定するのが望ましい。
次に同じ境界ボックスを表示空間全体に適用して記憶装
置を節約し、作成プロセスを簡単にすることができる。
したがって、一つのセルを構成し、ａおよびｂを使用し
て頂点を決定するのが望ましい。これは、水平および垂
直の方向が０°および90°になっている表示空間格子に
対して所定の角度を成すハーフトーンセル 300を示す図
６を参照して図的に見ることができる。ハーフトーンセ
ルを表すのに使用されるタイルは、最初に調節ずみハー
フトーンセルの頂点 50、70、80および90の周りに境界
ボックス325を描くことにより図式に決定することがで
きる、ブロック220。 この境界ボックスには第１の辺33
0、第２の辺335、第３の辺340、および第４の辺345があ
る。 ブロック220でハーフトーンセルを表すのに使用す
ることになるタイルが構築される。図７を参照すると、
５個のタイル350、355、400、405、および410が構築さ
れている。これら５個のタイル 350、355、400、405、
および410は調節ずみハーフトーンセルの周りに境界ボ
ックスを形成している。タイルは調節ずみハーフトーン
セルの頂点50、70、80、および90に接続する線により描
かれている。これらタイルは記憶装置に記憶されていて
表示空間のハーフトーンセルを表すしきい値を表すもの
である。タイル350はタイル400の複製であり、タイル35
5はタイル405と同じであって記憶装置内では別々に表す
必要がないことを見るべきである。したがって、表示空
間全体は３個のタイル400、405、および410で規定され
る。 タイルは表示空間内のタイルの位置に関係なく互
いに対して同様にマッピングされ、これによりタイルを
利用する簡単な手段が提供される。

【００１９】作成された３個のタイル 400、405、410は
単純な長方形である。図１０を参照して、タイルの境界
ボックスに対する大きさおよび向きについて次に説明す
ることにする。第１の頂点50はｘ、ｙ座標位置(0,0)に
確定されている。 それで隣接頂点70は、上に説明した
とおりｘ軸に沿う増分値はａに等しく、ｙ軸に沿う増分
値はｂに等しいから、位置(a,b)にあることになる。次
の頂点80は、 ｘの増分値がｂに等しく、ｙの増分値が
ａに等しいから、位置(a-b,b+a)にある。 続いて最後の
頂点90は位置(-b,a)にある。同様に、タイルの数、大き
さ、および形状はセルの大きさおよび向き（すなわち、
θの値）によって決まる。たとえば、θaが０°90°、
または180°に等しければ、一つだけタイルが作成され
る。θaが45°、135°、225°、または315°に等しけれ
ば、二つのタイルが作成される。 しかし、一般的には
３個のタイルが作成される。

【００２０】第１のタイル405は隣接頂点によって発生
され、 これにより頂点は長方形タイルの対向頂点を形
成する。これら頂点は長方形を通る対角線の終点と見る
ことができる。図１０に示したように、ハーフトーンセ
ルの二つの頂点80および90(a-b,b+a)および(-b,a)を使
用すれば、残る二つのタイル頂点を位置(a-b,a)および
(-b,b+a)にある長方形の残りの頂点になるように容易に
決定される。第２のタイル400は同様に、頂点70(a,b)お
よび頂点80(a-b、b+a)を長方形を通る対角線の終点とし
て使用することにより決まる。このようにして第２の長
方形の頂点は(a-b,b)、(a,b)、(a,b+a)、および(a-b,b)
である。第３のタイル410は第２のタイル400と共通の頂
点(a-b,b)および第１のタイル405と共通の頂点(a-b,a)
を備えている。一方、第３の頂点は、セルの第１の頂点
(0,0)と共線の位置に確定されており、 セルの第２の頂
点(a,b)と共線である。したがって頂点の位置は(0,b)で
あり、(a-b,a)で形成される正方形を横断する対角線を
形成している。 簡単な幾何学から第４の頂点の位置は
(0,a)にあることがわかる。

【００２１】セル［(0,0)、(0,a)、(-b,a)、(-b,0)］お
よび［(a,0)、(a,b)、(0,b)、(0,0)］を包含する残りの
二つのタイル350、 355は第１のタイル405および第２の
タイル 400の単純な繰返しであり、それ故記憶装置に記
憶する必要はない。その代わり、ハーフトーンプロセス
中これら三つのタイルはしきい値の検索用に参照される
ことになる。図１１は単純なアドレス空間を横断するタ
イルのマッピングの図である。三つのタイルの間の空間
的関係は一定であり、タイルを表示空間にマッピングす
るプロセスが簡単になる。

【００２２】図８のブロック230で、 タイルが決まって
しまえば、ハーフトーンプロセスを行うのに使用される
しきい値が作成される。しきい値は各画素に対する値を
発生するスポット関数に従って計算され、このしきい値
は、ハーフトーンプロセスの期間中、所要強度値と比較
され、画素をオンにすべきかまたはオフにすべきかを判
定するのに使用される。スポット関数はユーザ指定の数
学的関数であり、当業者に既知の多数のスポット関数の
一つであることができる。スポット関数および作成され
たしきい値はそれ故スポット関数を例示するためだけの
ものであり、作成されたしきい値および本発明は多様な
スポット関数およびしきい値を用いて実現することがで
きることに注目すべきである。

【００２３】模範的スポット関数は、しきい値が方程式
f(x,y)＝１-x2-y2 から決まる円スポット関数である。
ここでｘおよびｙはハーフトーンセル内の画素のハーフ
トーンセルの中心に対する座標値である。しきい値を作
成するには、座標値を変換し、-1と+1との間に空間限界
を有するハーフトーンセルの周りに中心がある座標空間
に合わせて拡大縮小する。ハーフトーンセル内部の各画
素について、ｘ、ｙ座標対（変換ずみ座標）を用い、ス
ポット関数を用いて中間値を発生する。ハーフトーンセ
ル内部の各座標値対について中間値が発生してしまう
と、中間値をその大きさに従って分類し、しきい値を分
類の種類に基づいて作成する。たとえば、総計50画素が
一つのハーフトーンセルの内部にあり且つ模擬すべき強
度またはグレースケールが０と255との間にあれば、増
分しきい値が255÷50と決まり、これは 5.1に等しい。
このようにして最高中間値を有する分類後の第１の画素
に255の値、第２の画素に249.9の値、第３の画素に244.
8の値が与えられる。このプロセスは分類リストの最後
の画素に 5.1の値が与えられるまで続く。これらの値は
記憶装置内で分類された値であり、作成プロセス中ハー
フトーン画像作成のためアクセスされる。

【００２４】タイルはたとえば図１０に示すような形で
記憶装置に記憶することができるが、タイルを表示空間
にマッピングするプロセスまたは作成プロセス中特定の
画素のしきい値を取出すプロセスは極めて経費が高く且
つ時間がかかる。ハーフトーンセルを記憶するのに必要
な記憶装置の量を極力少なくし、なお且つ作成プロセス
中しきい値に迅速且つ簡単にアクセスする方法を得るに
は、タイルを開き、しきい値列という列に組織する。こ
れにより表示空間への一層簡単なマッピングが行われ
る。この列は極小の大きさではあるがなお且つアクセス
し易く、表示空間にマッピングし易い。

【００２５】図１２および図１３によって示したプロセ
スは、しきい値列を三つのタイル400、405、および410
から再構成する方法を例示したものである。今後、タイ
ル405をタイルT1、タイル400をタイルT2、およびタイル
410をタイルT3と言うことにする。表示空間にわたって
タイルを貼るため画素のマッピングを識別するのにポイ
ンタ表を作成する。ポインタ表の各エントリは三つのタ
イルの内の一つに対応するが、これを作成プロセスと調
和させて画素の出力値を走査線上に走査線を基準として
（すなわち、一行づつ）発生することができる。ポイン
タ表のポインタ値は、行およびその行の最も右の要素に
隣接するタイルおよび作成のために現在アクセスされて
いるタイルを示す。５個のタイル350、355、400、405
および410の間の空間的関係は表示空間全体にわたって
一定であるから、一つのポインタ表を表示空間全体にわ
たるタイル貼りに適用することができる。たとえば、図
１２および図１３を参照すると、タイルT1の第１の行の
第１の画素を表示空間の第１の走査線の第１の画素にマ
ッピングすることにより、その行のタイルの最も左の画
素から最も右の画素までのしきい値を利用して画素を第
１の走査線内に置くことができる。タイルT1の行の端に
達すると、システムはT1の現在の行の最も右の画素に隣
接する、次の行および利用すべきタイルの行を識別する
ポインタ表を参照する。現在の図解では、図１２および
図１３に示すように、ポインタ表はタイルT1の行１の最
も右の画素に続くタイルT2の行１を識別する。タイルT2
の行１のしきい値はこの行の最後の画素に達するまで利
用される。この到達時に、ポインタ表を再び参照して次
のタイルおよびタイルT2の行１の最も右の画素に隣接す
るタイルの行を決定する。次にポインタ表はタイルT2の
行１に隣接する行となるT3の行１を識別する。

【００２６】このプロセスは走査線の端に達するまで続
き、またこのプロセスは画像が作成されるまでディジタ
ル画像の各走査線に適用される。たとえば、図9bを参照
しれば、画素375に対するポインタ表のエントリはタイ
ル410の第１の行を指し、タイル410の行１の最も右の画
素390に対するポインタ表のエントリはタイル 400の行
５を指す。次にハーフトーンプロセスはタイル 400の第
５行の各画素に左から右に最後の画素385に達するまで
アクセスし、プロセスはタイル405の第３行の第１の画
素 395がアクセスすべき行であることを示すポインタ表
のエントリを参照する。このようにして、一つのポイン
タ表が各一つのタイルについて作成され、三つのポイン
タ表が表示空間にわたりすべてのタイルをマッピングす
るのに必要なすべてである。

【００２７】メモリ空間を極小にすることができ、また
ハーフトーン画像を作成するのに必要な時間の量を、タ
イルを「開き」、記憶装置の構造に一層適合し得るしき
い値列を発生することにより維持し、または増やすこと
さえ可能であることが解決された。しきい値の長方形列
を三つのタイルから得て表示空間にわたり画像を描くに
必要なしきい値を発生することができる。これはタイル
を長方形列に「開く」ことにより達成される。この列は
幅（ｗ）および高さ（ｈ）を備えている。高さｈはａと
ｂとの最大公分母（gcd）に等しい。現在の例では、a=
6、 b=4である。したがってh=gcd(6,2)=2。したがって
列の高さは２単位、たとえば、画素になる。列の幅はし
きい値の連鎖が自身反復する前の走査線を横断するしき
い値の数によって決まる。図１６を参照すると、一連の
ハーフトーンセルについて作成されたタイルおよびそれ
らの対応するしきい値が示されている。説明の目的で、
しきい値を文字（Ａ〜Ｚ）および（ａ〜ｚ）で示してあ
る。

【００２８】図１６および図１７において番号０で識別
されている行からわかるように、作成されたしきい値は
Ａで始まりＪで終わっている。この行にはしきい値Ａ〜
Ｆを有するタイル405の第１の行、およびしきい値Ｇ〜
Ｊを有するタイル400の第１の行が入っている。その次
の二つのしきい値はＵ、Ｖであり、これはハーフトーン
セルの中心タイル410の行に対応する。これに続くのは
タイル400からのしきい値Ｗ、Ｘ、Ｙ、Ｚの行である。
Ｚに隣接してタイル 405の第３の行からの要素があり、
続いてしきい値ａ乃至ｊを有する、タイル 400の第３の
行がある。しきい値ｊに続いて、しきい値のこの連鎖が
反復する。したがって記憶装置に記憶すべきしきい値の
連鎖はABCDEFGHIJUVWXYZabcdefghijであり、反復パター
ンの要素の数は26である（これをしきい値列の幅と言
う）。同様に、同じ連鎖を使用して、図１７の行１で識
別される第２の行が行０と同じ幅であって要素KLMNOPQR
ST、uvwxyz、klmnopqrstから成ることが確定する。

【００２９】図１６を参照すると、その元の向きにある
３個の基本タイルが行番号、行０はＡ〜Ｊであり、行１
はＫ〜Ｔである、等々、により区別されている。列のし
きい値の第１の連鎖は行０のしきい値、すなわち、Ａ〜
Ｊから始まる。図１７および図１９を参照すれば、使用
すべきしきい値の次の行を指すポインタは次の方程式に
よって決まる。行番号+b mod a。ここで行番号は現在の
行番号であり、ａおよびｂはそれぞれ調節ずみハーフト
ーンセルを決定するのに使用されるａおよびｂの要素で
ある。この方程式を０行に適用して０行に隣接する行を
決定すれば、(0+4)mod 6=4。したがって、行４のしきい
値は行０のしきい値に隣接している。しきい値の次の行
は(4+4)mod 6=2に等しい。隣接するしきい値の次の行は
(2+4)mod6=0によって決まり、これは連鎖の第１の行が
行０であるから連鎖がそれ自身を反復していることを示
す。このようにして記憶装置に記憶すべきしきい値のパ
ターンの幅は行０の幅（これは10である）に行４の幅
（これは６である）を加え、これに行２の幅（これは10
である）を加えたものに等しく、合計は26である。

【００３０】同様に、第２の行を決定するには、しきい
値の第１の行は行１であり、隣接行は方程式1+4 mod 6=
5で識別され、その次の行は方程式5+4 mod 6=3から決定
される。方程式を次の行に適用すれば番号１が発生し、
連鎖が自身を反復し始めることを示す。したがって、図
２０を参照すると、記憶装置に記憶されるしきい値列は
識別されたしきい値を含む２×26列である。図１６ない
し図２０に示すように三つのタイル400、405、および41
0を開くことによっては、 しきい値はポインタ値を考慮
に入れないのでポインタ表が物理的には記憶装置に記憶
されないことに注目すべきである。更に、このしきい値
列を用いれば、しきい値の表示空間へのマッピングが簡
単になる。

【００３１】図９の流れ図により示したように、記憶装
置に記憶されるしきい値には容易にアクセスしてディジ
タルハーフトーン画像を描くことができる。表示空間の
或る画素に対するしきい値を決定するには、簡単な変換
を行って表示空間の画素の座標をしきい値のメモリアド
レスに変換する。プロセスを図解するため、図２１の
ｘ、ｙ座標位置(16,5)にある画素500を利用する。図８
のブロック245で、表示空間の(0,0)位置から下の行の数
を次の式：Int(dy/h)を用いて決定している。ただしdy
は位置(0,0)からの画素の数であり、ｈはしきい値列の
高さであり、Intは整数関数である。したがって現在の
例では、(0,0) から下のしきい値列の行の数を表す変数
ｎは５÷２＝2.5、すなわち整数値２である。 表示空間
の第１の画素をしきい値列の第１の画素にマッピングす
るのは普通の慣例である。表示空間にマッピングされた
しきい値列の各行は、各後続行がオフセットと言う所定
量だけずれていることを除けば同じである。図２１に示
した例ではオフセットは10の値に等しく、特定の行に対
するオフセットの量はｎに各行に対するオフセットの量
を掛けたものに等しい。したがって、たとえば、 表示
空間510にマッピングされたしきい値列の第２の行は１
オフセットだけずれている。 同様に、515にマッピング
されたしきい値列の第３の行はオフセットの量の２倍に
等しい量だけずれている。

【００３２】ブロック250で、オフセットは行の幅から
決まる。 現在の例ではオフセットはしきい値列の高さ
（ｈ）と同じ数により識別される行から決まる。この例
では、ｈは２に等しい。したがってオフセットは行２
（要素ａ〜ｊ）の幅である10の値に等しい。続いて、し
きい値列の行510は10の値だけ右にずれており、 これに
よりしきい値の第１の行はしきい値ａ〜ｊで始まり、次
の行はしきい値ｋ〜ｔで始まる。同様に、マッピングさ
れた第３のしきい値列は右に２*10＝20 ずれ、それ故し
きい値Ｇ〜Ｊで始まり、次の行はしきい値Ｑ〜Ｔで始ま
る。

【００３３】特定の画素に対するdyおよびdxの座標は、
変換によりしきい値列メモリ座標にマッピングされ、こ
れにより dx'、すなわちしきい値列の原点からのｘ距
離、は（dx-n*オフセット）mod（しきい幅）に等しい。
ここで modはモジュラ関数を表す。同様にdy'、原点か
らのｙ距離、はdy-n*hに等しい。現在の例、図11の画素
500、を使用すれば、dx'=(16-2*10) mod 26=22およびd
y'=5-2*2=1。したがって特定の画素 500に対するハーフ
トーン値を決定するのに使用されるしきい値列の要素は
しきい値列内の位置ｘ＝22およびｙ＝１に存在する。図
6bのブロック260で、しきい値列の位置 (22,1)にあるし
きい値がアクセスされ、ブロック265でその画素に対す
るハーフトーン値が作成されている。行内の最初の画素
に対するしきい値が決まると、同じ行の中の後続の画素
を容易に識別することができ、しきい値列内の後続画素
として決定することができるが、この場合先に記したよ
うな包み込み関数を適用し、これによりしきい値列の最
後の画素に到達する。このプロセスを利用して、しきい
値列を記憶するのに使用する記憶装置の量を極力少なく
しながらハーフトーン画像を迅速且つ簡単に作成するこ
とができる。

【００３４】本発明を好適実施例に関連して説明してき
た。これまでの説明に照らして多数の代案、修正、変
形、および用途が当業者には明きからになることは明白
である。たとえば、好適実施例を、画素が表示空間の左
側から右側に水平に実現される行依存走査線プロセスと
して説明した。しかし、当業者には明きらかであるよう
に、描写プロセスは恐らくは表示空間の左側から右へ描
かれる行依存プロセスであることがあり、または走査線
アルゴリズムが表示空間の上から下へまたはその逆に垂
直に動作する列依存プロセスである場合がある。

【図面の簡単な説明】

【図１】隣接する四つのハーフトーンセルを示す。

【図２】ハーフトーンセルを表示空間格子に適合するよ
うにする調節を示す。

【図３】ハーフトーンセルを表示空間格子に適合するよ
うにする調節を示す。

【図４】複数の隣接ハーフトーンセルから成るハーフト
ーン「スーパーセル」を示す。

【図５】本発明のシステムに使用される例示コンピュー
タシステムである。

【図６】ハーフローンセルの周りに作成された境界ボッ
クスを示す。

【図７】本発明の好適実施例で作成されたタイルを示
す。

【図８】本発明の方法の好適実施例を示す流れ図であ
る。

【図９】本発明の方法の好適実施例を示す流れ図であ
る。

【図１０】本発明の好適実施例におけるタイルの作成を
示す。

【図１１】本発明の好適実施例におけるタイルの作成を
示す。

【図１２】本発明の好適実施例におけるポインタの利用
を示す。

【図１３】本発明の好適実施例におけるポインタの利用
を示す。

【図１４】本発明の好適実施例において利用されるタイ
ルの概念を示す。

【図１５】本発明の好適実施例において利用されるタイ
ルの概念を示す。

【図１６】本発明の好適実施例において採用されている
タイルを「開く」手順を示す。

【図１７】本発明の好適実施例において採用されている
タイルを「開く」手順を示す。

【図１８】本発明の好適実施例において採用されている
タイルを「開く」手順を示す。

【図１９】本発明の好適実施例において採用されている
タイルを「開く」手順を示す。

【図２０】本発明の好適実施例において採用されている
タイルを「開く」手順を示す。

【図２１】本発明の好適実施例におけるしきい値列の表
示空間へのマッピングを示す。

【符号の説明】

３０、４０、５０、６０：頂点、７０、８０、９０：調
節された頂点、３５０、３５５、４００、４０５、４１
０：タイル。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジェイムズ・ゴスリン アメリカ合衆国 94043 カリフォルニア 州・マウンテン ビュー・ビラ ストリー ト・1600・アパートメント 213

Claims (3)

【特許請求の範囲】
1. 【請求項１】ディジタルハーフトーンシステムを備え、
   一定範囲の画像強度を模擬してディジタル画像を作成す
   る画像作成装置であって、前記作成画像はX-Y 格子上に
   位置する画素のマトリックスから成るディジタル表示空
   間を備えた画像出力装置に出力され、前記画素は所定の
   パターン状に作動されてディジタル表示空間の所定の領
   域に所定の強度を視覚的に模擬してディジタル画像を作
   成し、前記画素は作成すべき画像を画素を作動せしめる
   か否かを示すしきい値のしきい値列と比較することによ
   り所定パターン状に作動せしめられる画像作成装置のデ
   ィジタルハーフトーン画像を作成するしきい値列を格納
   するのに必要な記憶装置の量を低減する方法において、 記憶装置に格納すべき、ディジタルハーフトーン画像を
   作成する基準となるしきい値のマトリックスを有するハ
   ーフトーンセルの辺の長さ、角度、および角度許容差を
   指定し、 表示空間格子に適合するように調節したハーフトーンセ
   ルの実際の角度および辺の長さを決定し；調節ずみハー
   フトーンセルを包み込む表示空間格子のｘ軸およびｙ軸
   に沿う向きに境界ボックスを決定し；前記境界ボックス
   を、ハーフトーンセルおよび境界ボックスの頂点に従っ
   て作成された一つ以上のしきい値のタイルに分割し、 表示空間わたってタイルのマッピングを作成し；調節ず
   みハーフトーンセルに対するスポット関数に従ってタイ
   ルのしきい値を作成し；しきい値列の高さをハーフトー
   ンセルの頂点の間のｘ軸増分とｙ軸増分との最大公分母
   に等しく、 しきい値列の幅を連続したタイルの行にわたるしきい値
   の連鎖の、その連鎖が自身反復する前に受けるしきい値
   の数に等しい、 しきい値のしきい値列を形成するためにしきい値のタイ
   ルを開き；しきい値のタイルよりかなり少ない量の記憶
   装置を要求するしきい値列を記憶装置に記憶し；しきい
   値列を参照してディジタルハーフトーンセルを作成する
   のに使用されるしきい値を抽出することを特徴とする必
   要な記憶装置の量を低減する方法。
2. 【請求項２】ディジタルハーフトーンシステムを備え、
   一定範囲の画像強度を模擬してディジタル画像を作成す
   る画像作成装置であって、前記作成画像はX-Y 格子上に
   位置する画素のマトリックスから成るディジタル表示空
   間を備えた画像出力装置に出力され、前記画素は所定の
   パターン状に作動されてディジタル表示空間の所定の領
   域に所定の強度を視覚的に模擬してディジタル画像を作
   成し、前記画素は作成すべき画像を画素を作動せしめる
   か否かを示すしきい値のしきい値列と比較することによ
   り所定パターン状に作動せしめられる画像作成装置のデ
   ィジタルハーフトーン画像を作成するしきい値列を格納
   するのに必要な記憶装置の量を低減する方法において、 記憶装置に格納すべき、ディジタルハーフトーン画像を
   作成する基準となるしきい値のマトリックスを有するハ
   ーフトーンセルの辺の長さ、角度、および角度許容差を
   指定し；第１の調節ずみ頂点を決定するためにハーフト
   ーンセルの第１の頂点を最も近い画素に近似させ；前記
   第２の頂点がセル頻度値に対応する増分距離に位置して
   おり、前記セル頻度値は最初の第１の増分ａおよび最初
   の第２の増分ｂから成り、ａの値は第１の調節ずみ頂点
   から第２の調節ずみ頂点までの第１のａ軸に沿う増分を
   示し、ｂの値は第１の調節ずみ頂点から第２の調節ずみ
   頂点までの第２の軸に沿う増分を示し、ａおよびｂの値
   は、Rdがハーフトーンセルの辺の所要長さを表し、 θd
   がハーフトーンセルの所要角度を表し、セル頻度がSQRT
   (a²+b²)に等しいとして、 方程式 ａ＝INT[Rd cosθd] ｂ＝INT[Rd sinθd] に従って第２の調節ずみ頂点を決定するためにハーフト
   ーンセルの隣接する第２の頂点を最も近い画素に近似さ
   せ；第３の調節ずみ頂点を決定するために、その第３の
   調節ずみ頂点がセル頻度値に対応する第２の調節ずみ頂
   点からの増分距離に位置し、前記第１の軸の増分がｂに
   等しく、前記第２の軸の増分がａに等しく第２の調節ず
   み頂点に隣接する第３の頂点を最も近い画素に近似さ
   せ；第４の調節ずみ頂点を決定するために、その第４の
   調節ずみ頂点はセル頻度値に対応する第３の調節ずみ頂
   点からの増分距離に位置し、前記第１の軸の増分がａに
   等しく、前記第２の軸の増分がｂに等しく第３の調節ず
   み頂点および第１の調節ずみ頂点に隣接する第４の頂点
   を最も近い画素に近似させ；ハーフトーンセルの頂点を
   通り、ハーフトーンセルの対応する辺の主軸である軸に
   沿って線を画いて、境界ボックスの辺を表す長さａ＋ｂ
   の表示格子の軸に沿う線を作成することにより、調節ず
   みハーフトーンセルを包む表示空間格子のｘ軸およびｙ
   軸に沿う向きの境界ボックスを決定し；境界ボックスか
   ら、長方形状で調節ずみハーフトーンセルの第１の辺に
   等しい対角線を有するタイルを作成し、これにより隣接
   ハーフトーンセルの第１の辺を作成する隣接頂点が第１
   のタイルの対向頂点を作成し；第１のタイルが境界ボッ
   クス全体を包含しなければ、形状が長方形で対角線が調
   節ずみハーフトーンセルの第２の調節ずみ辺に等しい第
   ２のタイルを作成し、これにより第２の辺を形成する調
   節ずみハーフトーンセルの隣接する頂点が第２のタイル
   の対向頂点を形成し；第１および第２のタイルが共に境
   界ボックス全体を包含しなければ、形状が長方形で、第
   １のタイルと共通の頂点、第２のタイルと共通の頂点、
   調節ずみハーフトーンセルの第１および第２の頂点と共
   線の第３の頂点、およびハーフトーンセルの第１の頂点
   およびハーフトーンセルの第３の頂点と共線の第４の頂
   点を作成し；表示空間にわたってタイルのマップを作成
   し；ハーフトーンセルの座標値をハーフトーンセルの周
   囲に中心がある-1から+1までの範囲の中間座標空間に変
   換し、 スポット関数および変換後の座標値に従ってタイルの各
   しきい位置に対応する中間しきい値を発生し、 中間しきい値を模擬すべき強度の範囲にマッピングして
   しきい値を発生して調節ずみハーフトーンセルのスポッ
   ト関数にしたがってタイルのしきい値を作成し；最初の
   タイルの最初の行から始め、タイルの行を最初のタイル
   の反復になるまで走査することによりしきい値列の第１
   の行の、最初のタイルおよび最初のタイルを反復する前
   に隣接しているタイルのしきい値である内容を決定し
   て、かつ最初のタイルの最初の行に続く隣接行となるし
   きい値列の、第１行と同じ幅を有し、行の数はしきい値
   列の高さで決まる後に続くの内容を決定してしきい値の
   ａおよびｂの最大公分母に等しい高さおよび隣接タイル
   の列にわたるしきい値の連鎖の、その連鎖が自身反復す
   る前に受けるしきい値の数に等しい幅を有するしきい値
   列を形成するためにしきい値のタイルを開き；しきい値
   のタイルよりかなり少ない量の記憶装置を要求するしき
   い値列を記憶装置に記憶し；しきい値列を参照してディ
   ジタルハーフトーン画像を作成するのに使用するしきい
   値を抽出することを特徴とする必要な記憶装置の量を低
   減する方法。
3. 【請求項３】ディジタルハーフトーンシステムを備え、
   出力装置上の画素を所定の順序で作動させることにより
   一定範囲の強度を模擬して画像を作成する画像作成装置
   であって、前記出力装置はX-Y 格子上に位置する画素の
   マトリックスから成るディジタル表示空間を備えてお
   り、前記画素は所定のパターン状に作動されて所定の強
   度をディジタル表示空間の所定の領域に視覚的に模擬し
   て画像を作成し、前記画素は作成すべき画像を画素を作
   動せしめるか否かを示すしきい値のしきい値列と比較す
   ることにより所定のパターン状に作動せしめられる画像
   作成装置において、 表示空間の格子に対して最初の大きさおよび角度を有
   し、ディジタルハーフトーン画像を作成するのに参照さ
   れるしきい値のマトリックスから構成されるハーフトー
   ンセル；ハーフトーンセルを調節して表示空間の格子に
   適合させる調節手段；調節ずみハーフトーンセルを包む
   表示空間格子のｘ軸およびｙ軸に沿う向きの境界ボック
   スを作成する手段；ハーフトーンセルおよび境界ボック
   スの頂点に従って作成されるしきい値の一つ以上から成
   るタイルセット；調節ずみハーフトーンセルに対するス
   ポット関数に従ってタイルのしきい値を作成する手段；
   表示空間を横断してタイルのマッピングを決定する手
   段；しきい値のタイルを開いてしきい値のしきい値列を
   形成するもので、 前記しきい値列はハーフトーンセルの頂点の間のｘ軸増
   分とｙ軸増分との最大公分母に等しい高さを有し、 前記しきい値列は隣接タイルの行を横断するしきい値の
   連鎖の、その連鎖が自身反復する前に受けるしきい値の
   数に等しい幅を有している、 しきい値列形成手段；しきい値列を格納するのに必要な
   記憶装置の大きさは、しきい値およびハーフトーンセル
   のタイルを格納するのに必要な記憶装置の量よりかなり
   少ないしきい値のしきい値列を記憶する手段；から構成
   され、 しきい値を記憶して画像を作成するのに必要な記憶装置
   の量を減少し、しきい値列を参照してディジタルハーフ
   トーン画像を発生するのに使用するしきい値を抽出する
   ことを特徴とする画像形成装置。