(57)【要約】      （修正有）【課題】ハーフトーンプリントのレンダリングを改良するためにイメージをスクリーニングする方法を提供する。【解決手段】方法は、イメージを適応的にタイリングのためのステップを有している。このタイリングは、イメージの自己類似構成による細区分に基づく。これらの細区分は、イメージの局部的な輝度に基づいて局部的に範囲を画定され、その局部的な範囲限定によってタイリングは最適にレンダリングされる。このタイリングの結果は、サンプリング構造のクラウドである。その各構造は、イメージピクセルとタイリングの間に生じるラベルとに関連している。ピクセルの輝度及びラベルによって、印刷の前に、緩和アルゴリズムによって予め計算されている訂正ベクトルテーブルから、ピクセルに適用される変位に対応する訂正ベクトルを読み出すことができる。【選択図】図２ｃ
2010283854.tif 000002
【特許請求の範囲】
【請求項１】
スクリーニング・デバイスによって実行される以下のステップを具備することを特徴とする、印刷前にイメージをスクリーニングする方法であって、
（１）自己類似構成の実施によって得られる非周期的な構成によってスクリーニングされるイメージに対してタイリング（１００）を行う、すなわち、そのタイリングは、ルールに従って再び分割される新しい構成を与えるためにこれら同じルールに従って分割される構成（１０２）からされ、それら構成の中からサンプリング構成及び細区分構成が区別され、サンプリング構成はドットに例えられ、細区分構成だけが再び分割される、
（２）タイリングが分割されるべき構成によっておおわれるイメージのゾーンの輝度に依存するので、タイリングは適応性があり、この輝度が予め定められた閾値未満になるときに、構成の分割は中止され（１０４）、
（３）イメージの表面積単位当たりの細区分構成の記録密度が閾値より高くなるときに、分割は中止され（１０４、
（４）各分割で、スクリーニング装置は、同様に各新しい構成と既存のサンプリング構成とにラベルを割り当て（１０３）、
（５）タイリングの最後に、各サンプリング構成は、二入力訂正テーブル中の該当する訂正ベクトルの関数として実行されるピクセルと関連付けられ（１０６）、二入力訂正テーブル中の第１の入力は、サンプリング構成のラベルであり、二入力訂正テーブル中の第２の入力は、サンプリング構成に対応するポイントであり、各サンプリング構成は、訂正テーブルの入力としてサンプリング構成を機能させたイメージのドットと関連した状態のままになっており、
（６）各サンプリング構成は、サンプリング構成のラベルの関数として、関連した閾値を有し（１０５）、
（７）前のステップにおいて決定される閾値は、ハーフトーン・レンダリング方法を実行するために使用される（１０７）
ことを特徴とするイメージをスクリーニングする方法。
【請求項２】
実行されるハーフトーン・レンダリング方法が閾値マトリックス法であることを特徴とする請求項１に記載の方法。
【請求項３】
実行されるハーフトーン・レンダリング方法がエラー−分散アルゴリズムであることを特徴とする請求項１に記載の方法。
【請求項４】
細区分構成が多角形であることを特徴とする請求項１から請求項３までの何れか１項に記載の方法。
【請求項５】
多角形が三角形（２０２）であることを特徴とする請求項４に記載の方法。
【請求項６】
新しい構成のラベルが、予め定めたルールに従って新しい構成がつくられた構成のラベルから導かれる（１０３）ことを特徴とする請求項１から請求項５までの何れか１項に記載の方法。
【請求項７】
ハーフトーン・レンダリング方法の実施のための以前のステップにおいて決定される閾値の使用の前に、スクリーニング・デバイスが、訂正テーブルの訂正ベクトルを決定するためにサンプリング構成に対して緩和アルゴリズムを実行することを特徴とする請求項１から請求項６までの何れか１項に記載の方法。
【請求項８】
細区分構成を２つの新しい細区分構成に細区分する間、新しい構成の面積の比が全ての細区分について一定であることを特徴とする請求項１から請求項７までの何れか１項に記載の方法。
【請求項９】
前記比が黄金比の自乗に等しいことを特徴とする請求項８に記載の方法。
【請求項１０】
構成と関連付けられるラベルが二進数であり、ラベルの最上位６ビットが、第１の入力を生成するために使われ、これらビットの各々の値はＦｉ倍される。ここで、ｉは２から７であり、Ｆｉはフィボナッチ数列に対応する数であり、従って、最上位ビットＦ７倍され、その次に下位のビットはＦ６倍され、以下同様にして、第６番目の最上位ビットまで処理させられることを特徴とする請求項１から請求項９までの何れか１項に記載の方法。
【請求項１１】
第２の入力が以下の関数に等しい：
【数１】
2010283854.tif 000007
ここで、ｐｈｉは黄金比であり、そして、ｘはサンプリング構成と関連付けられているイメージのピクセルの輝度であり、上記関数の結果の実数の区間［  ０、１  ］はＮ区間に分割されて、先行する関数結果を区間［０，（Ｎ−１）］内の整数と関連付けることができ、その整数が第２の入力であることを特徴とする請求項１から請求項１０までの何れか１項に記載の方法。
【請求項１２】
Ｎが８に等しいことを特徴とする請求項１１に記載の方法。
【請求項１３】
処理されるイメージが複数のブロックに分割され、各ブロックが、請求項１から請求項１２までの何れか１項に記載の方法に従って、スクリーニング装置によって実行されるステップによって処理されることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、イメージのスクリーニングの方法に関する。
【０００２】
本発明の分野は、特にイメージを印刷するときに、イメージのレンダリングする分野である。
特に、本発明の分野は、記憶されているイメージがモノクロ階調フォーマットとして公知のフォーマットにおいて印刷されるハーフトーン・プリントでのレンダリングの分野である。ここで、モノクロ階調フォーマットは、3つのモノクロのイメージのスーパーインポーズによって実際に形成されるカラーイメージに拡張される。より詳細に言うならば、本発明の分野は、例えばファックス受信装置において使われるプリンタのようなプリンタの分野である。
【背景技術】
【０００３】
従来技術において、最も共通して使うハーフトーン・レンダリング方法は、エラー-分散又は閾値マトリックス法である。
【０００４】
閾値マトリックスは、分散させられることができるか、又はグループ化させられることができる、又は、それらはブルー・ノイズ・マスクであってもよい。マトリックスに基づく方法は、演算速度に関しては優れているが、規則的な構成の外観に成り勝ちである。
【０００５】
エラー-分散方式は、人為的な構造の、特に波の外観に成り勝ちである。波は、繰返し構成、特にマトリックスによって得られる繰返し構成にリンクされる人為的な構造に特徴がある。構成の人為的な構造は、肉眼でもわかる明らかに不規則な形状の変化という形をとる。これは、イメージの各行でのイメージの処理の方向の変更に対応する、蛇行モードでイメージのトリップ乃至は移動を実行することによって解決できる。ここで、「ラウンドトリップ」も使われる。
【０００６】
更に、集積回路化された映像処理システムにおいて、イメージのブロック処理は、特に専用回路を作るための最も最適化されたモードである。現在、この種類のブロック処理は、蛇行モードを使用しているために、エラー分散アルゴリズムをほとんど適応化することができない。Chang及びAllebachはブロック-スクリーニング・アルゴリズムを提案した、しかし、このアルゴリズムは実施するには複雑であり、良好な結果を与えるためには冗長なセッティング・フェーズ及び多量のノウハウを必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、イメージの単方向トリップでのエラー-分散の実施に等価なアルゴリズムを提案することによってこれらの問題を解決する。本発明で、イメージの非周期的なタイリングがなされる。タイリングの結果として、タイリングのサンプリング構成に対応するドットのクラウドとなる。その記録密度がイメージの輝度に依存する意味において、タイリングは更に適応化される。本明細書において、イメージの輝度は、イメージのドットのエンコーディングにリンクされるとみなされる。これらのドット又はピクセルは、例えば、区間[ 0, 255 ]に含まれる数によってコード化される。ピクセルがコード化される値が大きいほど、その輝度は高い。タイリングは、自己類似方法での構成の細区分によってされる。各細区分で、新しい構成は、細区分された構成のラベルの関数として名をつけられる（それらは、ラベルを割り当てられる）。それ故に、タイリングの終わりに、各構成はラベルを有する。このラベルは、第一に構成に割り当てられる閾値を決定するために、そして、第２に二入力訂正テーブルの１つの入力として、使用される。
訂正テーブルの他方の入力は、考慮されるピクセルの輝度に依存する。訂正テーブルは、印刷前に、ドットの再調整のために使われるベクトルから成る。その結果、人間の目によって検出可能な人為的なものをもはや全く有しない印字イメージとなる。
【０００８】
タイリングを構成する要素の外観の周波数が整数の比によって表すことができない場合、タイリングは非周期的にセットされる。同様な意味で、タイリングを構成する基本タイルのセットを基礎として周期的なタイリングが全く不可能な場合、タイリングは非周期的であると言える。
タイリングは、それが有限のベクトルの変換対称性があるときに、非周期的であると言われている。
【課題を解決するための手段】
【０００９】
従って、本発明によるならば、スクリーニング・デバイスによって実行される以下のステップを具備することを特徴とする、印刷前にイメージをスクリーニングする方法が提供される：
（１）自己類似構成の実施によって得られる非周期的な構成によってスクリーニングされるイメージに対してタイリングを行う、すなわち、そのタイリングは、ルールに従って再び分割される新しい構成を与えるためにこれら同じルールに従って分割される構成からされ、それら構成の中からサンプリング構成及び細区分構成が区別され、サンプリング構成はドットに例えられ、細区分構成だけが再び分割される、
（２）タイリングが分割されるべき構成によっておおわれるイメージのゾーンの輝度に依存するので、タイリングは適応性があり、この輝度が予め定められた閾値未満になるときに、構成の分割は中止され、
（３）イメージの表面積単位当たりの構成の記録密度が閾値より高くなるときに、分割は中止され、
（４）各分割で、スクリーニング装置は、同様に各新しい構成と既存のサンプリング構成とにラベルを割り当て、
（５）タイリングの最後に、各サンプリング構成は、二入力訂正テーブル中の該当する訂正ベクトルの関数としてシフトされるピクセルと関連付けられ、二入力訂正テーブル中の第１の入力は、サンプリング構成のラベルであり、二入力訂正テーブル中の第２の入力は、サンプリング構成に対応するポイントであり、各サンプリング構成は、訂正テーブルの入力としてサンプリング構成を機能させたイメージのドットと関連したままになっており、
（６）各サンプリング構成は、サンプリング構成のラベルの関数として、関連した閾値を有し、
（７）前のステップにおいて決定される閾値は、ハーフトーン・レンダリング方法を実行するために使用される。
【００１０】
好ましくは、本発明は更に、実行されるハーフトーン・レンダリング方法が閾値マトリックス法であることを特徴とする。
好ましくは、本発明は更に、実行されるハーフトーン・レンダリング方法がエラー-分散アルゴリズムであることを特徴とする。
好ましくは、本発明は更に、細区分構成が多角形であることを特徴とする。
好ましくは、本発明は更に、多角形が三角形であることを特徴とする。
好ましくは、本発明は更に、新しい構成のラベルが、新しい構成がつくられた構成のラベルから導かれることを特徴とする。
【００１１】
好ましくは、本発明は更に、ハーフトーン・レンダリング方法の実施のための以前のステップにおいて決定される閾値の使用の前に、スクリーニング・デバイスが、訂正テーブルの訂正ベクトルを決定するためにサンプリング構成に対して緩和アルゴリズムを実行することを特徴とする。
【００１２】
好ましくは、本発明は更に、細区分構成を2つの新しい細区分構成に細区分する間、、新しい構成の面積の比が全ての細区分について一定であることを特徴とする。
好ましくは、本発明は更に、その比が黄金比の自乗に等しく、その一つの値は、小数点第２位で丸めて1.61であることを特徴とする。
【００１３】
好ましくは、本発明がまた、構成と関連付けられるラベルが二進数であり、ラベルの最上位６ビットが、第１の入力を生成するために使われ、これらビットの各々の値はＦi倍される。ここで、iは２から７であり、Ｆiはフィボナッチ数列に対応する数であり、従って、最上位ビットＦ7倍され、その次に下位のビットはＦ7倍され、以下同様にして、第6番目の最上位ビットまで処理させられることを特徴とする。
【００１４】
好ましくは、本発明は更に、第２の入力が以下に等しいことを特徴とする：
【数２】
2010283854.tif 000003
ここで、phi(すなわちφ)は黄金比であり、そして、ｘはサンプリング構成と関連付けられているイメージの輝度であり、実区間［  ０、１  ］はＮ区間に分割されて、先行する関数結果を区間［０，（Ｎ−１）］内の整数と関連付けることができ、その整数が第２の入力である。
好ましくは、本発明は更に、Ｎが８に等しいことを特徴とする。
【００１５】
好ましくは、本発明は更に、処理されるイメージがブロックに分割され、各ブロックが方法によって処理されることを特徴とする。
【図面の簡単な説明】
【００１６】
【図１】本発明の方法のステップを図解する。
【図２ａ】細区分のルールを図解する。
【図２ｂ】細区分のルールを図解する。
【図２ｃ】細区分のルールを図解する。
【発明を実施するための形態】
【００１７】
本発明は、以下の説明及び添付図面からより明らかに理解されるであろう。しかし、添付図面は、説明のためのであり、本発明の範囲を決して限定するものではない。
本発明の方法のステップは、イメージをスクリーニングする装置によって実行される。この種のデバイスは、メモリのイメージを読み取り、他のメモリにおいて記録されるか又は紙形式の物理的なキャリヤに直接に印刷されるスクリーニングされたイメージを生成する。本発明のおいて、イメージ又はイメージ・ブロックは、ピクセルと称すドットのマトリックスに関連付けることができ、各ピクセルはマトリックス内の座標を有し、且つ各ピクセルは輝度と関連付けることができる。本例において、輝度は、バイトで、すなわち区間[ 0, 255 ]の範囲に含まれる整
数値によってコード化されるとみなされる。
【００１８】
一般に、動作が装置に起因するときに、この動作は、装置のメモリに記録されている命令コードによって制御される装置のマイクロプロセッサによって実行される。
【００１９】
図1は、非周期的な構成によってイメージをタイリングするためのステップ100を示す。本明細書において、用語「タイリング」は、イメージ上に非周期的な構成を敷き詰める動作を指す。従来技術において、特非周期的な構成によってイメージにタイリングすることは、以下の特許文献１‐３から知られている。更に、これらの概念が、以下の非特許文献１で検討されている。っこれら文献は、Penroseタイリングを図解しているが、Ammann Beekerタイリングのようなタイリングの他の形式もある。この種類のタイリングを実行するための基本原理を、ここで思い出されたい。
【特許文献１】米国特許第４８９４７２６号
【特許文献２】米国特許第５１７９４４８号
【特許文献３】米国特許第５３７９１１８号
【非特許文献１】Grunbaum and Shephard "Tiling and Patterns"
【００２０】
図１は、タイリングプロセスを初期化するためのステップ１０１を示す。そこにおいて、タイリングの初期構成２０２は、イメージ上に敷き詰められている。図示の簡略した例において、初期構成２０２は、イメージ２０１を含むのに十分な大きさの三角形である。実際問題として、初期構成２０２は、より複合でも、更にはそれ自体がいくつかの構成に分割されてもよい。初期構成２０２が、図示の例のように、ラベル０と関連付けられる。初期構成２０２は、細区分構成として公知の構成である。
【００２１】
ステップ１０１から、方法は細区分ステップ１０２に移る。
このステップにおいて、前の細区分ステップから生じている全細区分構成が、予め定めたルールに従って細区分される。これにより、新しい細区分構成及び新しいサンプリング構成が得られる。
【００２２】
実際問題として、細区分構成は、細区分プロセスの間の細区分される構成であるのに、サンプリング構成は、ドットに例えることができ且つタイリングされるイメージのピクセルと関連付けられる。細区分プロセスの結果は、サンプリング構成のクラウド、それ故に、ピクセルのクラウドが得られる。ピクセルのクラウドは、平らな空間の分散を有する一組のピクセルである。その後、各ピクセルが関連するサンプリング構成の関数として、各ピクセルは処理される。このプロセスにおいて、与えられたイメージのために、サンプリング構成のクラウドは不変量であるのに対して、ピクセルのクラウドは、サンプリング構成のクラウドの関数として修飾される。
【００２３】
図面は、初期化ステップ１０１の結果に適用されたステップ１０２の結果を示している。
図２ｂは、三角形の構成２０２が２つの三角形の細区分構成２１０及び２１１と１つのサンプリング構成２１２に細区分されたことを示している。サンプリング構成２１２は、２つの三角形２１０及び２１１に共通する辺の交点である。三角形２１０及び２１１を得るための１つの考えられるルールは、それらの面積の比が黄金比の自乗となるようにするということである。その黄金比は、小数点第２位で丸めると1.61に等しい。
【００２４】
ステップ１０２から、方法は、新しい構成に番号を付けるためのステップ１０３に移る。ステップ１０３において、各新しい構成は、新しい構成が来た構成のラベルに従い、ラベルが割り当てられる。従って、構成２０２にラベル０が当てられている場合、構成２１０〜２１２のラベルは、予め定められたルールに従い０の補数から成る。１つの例のでは、これらのルールの適用の結果、構成２１０のラベルが０００であり、構成２１１のラベルは１００であり、そして、構成２１２のラベルは１００である。
【００２５】
これらの細区分ステップが繰り返され、各細区分構成もう一度細区分され、その結果としての細区分に番号が付けられる。細区分終了基準が確認されるときに、細区分プロセスは終了する。
【００２６】
実際、各細区分及びサンプリング構成は所与の形式である。各形式は、細区分構成のための細区分の対応するルール及び場合によればサンプリング構成のための形式変更ルールを有する。各形式の構成も、ラベルを決定するための対応するルールを有する。これらのルールは、すでに言及されるタイリング方法の場合既に知られている。図２ｃは、非周期的なタイリングを実行するために使われることができる他のルールを図解する。
【００２７】
１つの典型的な実施例において、６形式の構成、２形式のサンプリング構成及び４形式の細区分構成が定義される。サンプリング構成の形式は、ａ及びｂと名付ける。構成の各々は、方向付けれる。
【００２８】
図示の例において、細区分構成は、二等辺三角形である。この種の三角形の頂点は、等しい長さの辺の交点である。この種の三角形の基底は、頂点の反対辺の辺である。本明細書において、頂点でない三角形の辺の交点は、角と称する。三角形のこのような辺は、基底でない。
【００２９】
ａ形式及びｂ形式の構成は、形式変更ルールを受ける。ステップ１０２の各繰返しで、ａ形式の構成が、同じ方向を維持してｂ形式の構成になる。ｂ形式の構成は、１８０度回転したａ形式の構成になる。そのようにして得られたａ形式及びｂ形式の構成のラベルは、以下のルールから導かれる。
−  新しい構成のラベルは、００に元の構成ｂのラベルを続ける。
−  新しい構成のラベルは、００に元の構成ａのラベルを続ける。
【００３０】
図２ｃは、実際に二等辺三角形であるｃ形式の三角形の構成２２０を示す。ｃ形式三角形の両辺が１に等しい値、すなわち単一に対応する値を有する場合、基底は、予め定義された単位で表される黄金比の逆数に等しい長さを有する。本例において、構成２０２はｃ形式の−構造である。参照番号２２１は、ｃ形式の構造の細区分のルールを図解する。従って、ｃ形式の三角形が、１つのｆ形式の三角形２２２、１つのｃ形式の三角形２２３及び１つのａ形式のサンプリング構成２２４を含む２つの三角形に細区分される。参照番号２２１は、構成２２０の細区分が、三角形２２２の頂点に位置しているサンプリング構成２２４を生成することを示す。三角形２２２及び２２３に共通している辺が、三角形２２０の左角から延び、三角形２２０の頂点は上向きである。三角形２２２及び２２３は二等辺三角形であり、そして、三角形２２３の頂点は三角形２２０の左角である。
【００３１】
このようにして得られた新しいａ形式、ｃ形式及びｆ形式の構成のラベルは、以下のルールから導かれる。
−  新しい構成ａのラベルは、１０に元の構成ｃのラベルを続ける。
−  新しい構成ｃのラベルは、１０に元の構成ｃのラベルを続ける。
−  新しい構成ｆのラベルは、００に元の構成ｃのラベルを続ける。
【００３２】
図２ｃは、実際に二等辺三角形であるｆ形式の三角形の構成２２５を示す。ｆ形式の三角形の両辺が、１等しい値、すなわち単一に対応する値を有する場合、基底は、予め定義された単位で表される黄金比に等しい長さを有する。参照番号２２６は、ｆ形式の構成の細区分のルールを図解する。従って、ｆ形式の三角形が、１つのｆ形式三角形２２７、１つのｄ形式三角形２２８、１つのｅ形式三角形２２９及び１つのａ形式サンプリング構成２３０を含む３つの三角形に細区分される。三角形２２５は、その頂点が上向きであるとみなす。三角形２２７は、三角形２２５の頂点から延びて、三角形２２５の右角から１の距離離れて三角形２２５の基底に交差する直線に沿って、三角形２２５を２つに細区分して得られる。この最初の細区分から得られる右部分は、三角形２２７の頂点から延びて、三角形２２５の頂点から黄金比の逆数に等しい距離の三角形２２５の右辺に交差する直線に沿って、第２の細区分によって更に分割される。第２の細区分の右部分は、三角形２２９であり、他の部分は三角形２２８である。サンプリング構成２３０は、三角形２２７及び２２８の共通の頂点に対応する。
【００３３】
このようにして得られた新しいａ形式、ｄ形式、ｅ形式及びｆ形式の構成のラベルは、以下のルールから導かれる。
−  新しい構成ａのラベルは、０１に元の構成ｆのラベルを続ける。
−  新しい構成ｄのラベルは、１０に元の構成ｆのラベルを続ける。
−  新しい構成ｅのラベルは、００に元の構成ｆのラベルを続ける。
−  新しい構成ｆのラベルは、０１に元の構成ｆのラベルを続ける。
【００３４】
図２ｃは、実際に二等辺三角形であるｄ形式の三角形の構成２３１を示す。ｄ形式三角形の両辺が１に等しい値を有する、すなわち単一に対応する値を有する場合、基底は予め定義された単位で表される黄金比の逆数に等しい長さを有する。参照番号２３２は、ｄ形式構成の細区分のルールを図解する。従って、ｄ形式三角形は、１つのｆ形式三角形２３３及び１つのｅ形式三角形２３４を含む２つの三角形に細区分される。三角形２３３及び２３４に共通している辺は、三角形２３１の右角から延び、三角形２３１の頂点は上向きであり、三角形２３３及び２３４は二等辺三角形であり、三角形２３３の頂点は三角形２３１の右角である。
【００３５】
このようにして得られた新しいｄ形式及びｅ形式の構成のラベルは、以下のルールから導かれる。
−  新しい構成ｄのラベルは、１０に元の構成のラベルを続ける。
−  新しい構成ｅのラベルは、１０に元の構成のラベルを続ける。
【００３６】
図２ｃは、実際に二等辺三角形であるｅ形式三角形の構成２３５を示す。ｅ形式三角形の両辺が１に等しい値を有する、すなわち単一に対応する値を有する場合、基底は予め定義された単位で表される黄金比に等しい長さを有する。参照番号２３６は、ｅ形式構成の細区分のルールを図解する。従って、ｅ形式三角形は、１つのｆ形式三角形２３７、１つのｃ形式三角形２３８、１つのｅ形式三角形２３９、１つのａ形式サンプリング構成２４０を含む３つの三角形に細区分される。三角形２３５の頂点は上向きであるとみなす。三角形２３９は、三角形２３５の頂点から延びて、三角形２３５の左角から１の距離１離れた三角形２３５の基底を交差する直線に沿って三角形２３５を２つに細区分して得られる。三角形２３９は、このように細区分された三角形２３５の右部分である。
【００３７】
最初の細区分から得られた左部分は、三角形２３９の頂点から延びて、三角形２３５の頂点から黄金比自乗の逆数に等しい距離で三角形２３５の左辺に交差する直線に沿って、第２の細区分によって更に分割される。第２の細区分の右部分は、三角形２３８であり、他の部分は三角形２３７である。サンプリング構成２４０は、三角形２３７の頂点に対応する。
【００３８】
このようにして得られた新しいａ形式、ｃ形式、ｅ形式及びｆ形式の構成のラベルは、以下のルールから導かれる。
−  新しい構成ａのラベルは、１０に元の構成ｅのラベルを続ける。
−  新しい構成ｃのラベルは、１０に元の構成ｅのラベルを続ける。
−  新しい構成ｅのラベルは、０１に元の構成ｅのラベルを続ける。
−  新しい構成ｆのラベルは、００に元の構成ｅのラベルを続ける。
【００３９】
細区分構成が細区分されて、それらの元の構成に従って名を付けられる度に、本方法は、細区分終了基準を判断するためのステップに移る。実際問題として、処理終了基準が達成されない限り、各新しい細区分構成は再び細区分される。
【００４０】
本発明のいて、この基準は、二段階基準である。最初の条件は、表面積単位当たりサンプリング構成の記録密度が所定の閾値の下になければならないということである。この閾値を過ぎると、細区分プロセスは止まる。これは、細区分構成の表面のための最小表面領域を固定することと同義である。
【００４１】
細区分終了基準の他の部分は、イメージの輝度の基準である。細区分構成のイメージの輝度が所定の閾値より下になるとすぐにイメージの領域の細区分は終了する。この条件は、細区分プロセスを適応化する、すなわち細区分プロセスがイメージの性質に適応させる。換言すれば、イメージの低輝度領域に対応する細区分構成は、もはや細区分されない。
【００４２】
１つの変形例において、細区分構成内に位置するグレーレベルによって定義される細区分の数が達成されるときに細区分を終了するような細区分終了基準とする。グレーレベルｘに対してに、例えば、細区分の数は、次の式によって与えられる。
【数３】
2010283854.tif 000004
各細区分構成のために、この細区分を得るために実行されなければならなかった細区分の数Ｎが考慮される。それから、λ（ｘ）は細区分構成の頂点のために計算される。計算されたλ（ｘ）の値のどれもＮより大きくない場合、構成の細区分が終了させられる。
【００４３】
もう１つの変形例は、細区分構成の他のドット又は、終了基準が判定された細区分構成に関連するサンプリング構成のセンタを関係させる。これらの変形例において、各細区分構成については、本方法は、この細区分構成に到着するために実行されなければならなかったたくさんの細区分と関連する。
【００４４】
図示の例は、三角形の使用の基づく非周期的なタイリングの例として示した。Penroseタイリングは、四辺形を実行する。Amman Beekerタイリングは、はるかにより複合多角形を実行する。三角形を使用する有用性は、タイリングを実行するために計算を容易にするその単純構造にある。
【００４５】
黄金比に関連した寸法の使用によって、細区分構成が、面積の比が黄金比の自乗に等しい構成に細区分されることを可能にする。
【００４６】
タイリングが完了される度に、本方法は、ステップ１０４から、閾値を決定するためのステップ１０５に移行する。閾値は、閾値マトリックスによって又はエラー−分散によってアルゴリズムを実行するために使われる閾値である。エラー−分散の使用の場合、閾値は約１２７に、すなわち区間［0,255］の範囲内にある輝度でコード化されるピクセルのダイナミックレンジの中央にセットすることができる。実際問題として、上記したダイナミックレンジの場合、閾値自体が区間［124....128］の範囲内にある。本発明では、各サンプリング構成は、サンプリング構成と関連がある閾値を有する。本発明の１つの変形例において、閾値はサンプリング構成と関連があるラベルに関係する。例えば、本発明のラベルは、２進表記から１０表記に変換される。関数が変換に適用され、変換の間隔は、区間［0, 255］である。この変換は、例えば、記述ベクトルがフィボナッチ数列の要素であるベースにおいて実行される。そのフィボナッチ数列の要素は、訂正ベクトルのテーブルの第１の入力の生成のための以下に説明する。この場合、ラベルが、フィボナッチ数列の第２の要素で始まる複数の桁から成るように、フィボナッチ数列の多くの要素が使われる。
【００４７】
ステップ１０５から、本方法は、サンプリング構成の位置の訂正のためのステップ１０６に移る。上述したように、各サンプリング構成は、タイリングが作られるイメージのピクセルに対応する。ステップ１０６において、印刷前に、サンプリング構成の位置の、従ってサンプリング構成と関連したピクセルの位置の修正がなされる。この修正乃至は訂正はまた、緩和又は緩和プロセスと称す。
【００４８】
この訂正は、訂正ベクトルから成っている訂正テーブルの関数としてなされる。訂正テーブルによって、訂正ベクトルが各サンプリング構成と関連させることができる。訂正テーブルは、２つの入力を有する。第１の入力は、サンプリング構成のラベルに関係する。
【００４９】
上述したように、ラベルは、構成、特に、サンプリング構成と関連する二進数である。テーブルの最上位６ビットは、第１の入力を生成するために用いる。これらビットの各々の値は、ＦI倍される。ここでｉは区間［2, 7］であり、Ｆiはフィボナッチ数列の対応する数であり、最上位ビットはＦ7倍され、次ぎの上位ビットはＦ6倍され、以下同様にして６番目の上位ビットまで処理される。
【００５０】
従って、ラベルが１０１０１０１０１０１であるサンプリング構成に対しては、
第１の入力の値は、１×Ｆ７＋０×Ｆ６＋１×Ｆ５＋０×Ｆ４＋１×Ｆ３＋０×Ｆ２であり、
１×13＋０×８＋１×５＋０×３＋１×２＋０×１＝２０が得られる
【００５１】
次の変換は、フィボナッチ数列のためのここで適用される。
Ｆ０＝０、Ｆ１＝１、Ｆ２＝１、Ｆ３＝２、Ｆ４＝３、Ｆ５＝５、Ｆ６＝８、Ｆ７＝１３。
このシーケンスは続くが、本発明においては、最初の８つの項だけは第１の入力の定義のために有効である。
【００５２】
ラベルの割当ての選ばれたモードについては、ラベルが２つの連続する１を含むことができない点に注意されることができる。それ故、第１の入力のための値が、整数区間［0,20］の範囲にある。第１の入力は、構造のインデックスと称す。
【００５３】
訂正テーブルの第２の入力は、サンプリング構成と関連があるピクセルの輝度に関係する。或る実施例において、第２の入力は、以下に等しい。
【数４】
2010283854.tif 000005
ここで、
phi（すなわちφ）は黄金比であり、ｘはサンプリング構成と関連があるイメージの輝度である。関数の到着の実区間［０，  １］はＮ個の区間に分割され、先行する関数の結果を、区間［０，  （Ｎ−１）］内の整数に関連させることができる。この整数は、第２の入力である。この第２の入力は、重要性インデックスと称す。
【００５４】
１つの例において、Ｎは８に等しく、そして、実区間［0, 1］は、全く同じサイズのＮ個の離散した区間に分割され、その第２の入力は、整数区間［0,7］に含められる。
【００５５】
従って、選ばれた例において、訂正ベクトルのテーブルは、２１×８＝１６８の大きさである。
これらの１６８の訂正アクタは、予め定められる。このようなテーブルは、例えば以下である。
【００５６】
【表１】
2010283854.tif 000006
【００５７】
これらの訂正ベクトルは、タイリングプロセスから得られている各サンプリング構成と関連があるピクセルの位置に適用される。従って、これらのサンプリング構成は、訂正テーブルにリンクされる緩和プロセスによって影響を受けない。これらのサンプリング構成にリンクされるピクセルだけが、この緩和プロセスによって影響を受ける。
【００５８】
訂正がなされるサンプリング構成に関係する単位で訂正は表される。本発明の方法によれば、各サンプリング構成は、単位が定義される細区分構成に関連させられる。所与のサンプリング構成のために、この単位が、訂正ベクトルの解釈のために使われる。
【００５９】
ステップ１０６から、本方法は、スクリーニング・デバイスが、上述した方法によって得られたサンプリング構成に対応する閾値ピクセルをプリントするか、又は、それらをメモリに書き込むか又はスクリーン上に表示する印刷ステップ１０７へ移行する。この方法により、サンプリング構成従ってピクセルが印刷されなければならないかどうか決めるために使用される閾値並びにピクセルを元の位置に対してシフトするために使用される訂正ベクトルとピクセルとを関連付けることができる。実際問題として、ピクセルの値がそのピクセルと関連する閾値より上にある場合だけ、ピクセルは印刷される。これは、イメージの全てのピクセルに対して当てはまる
１つの変形例において、逆の基準が使われる。
【００６０】
ここで、エラー−分散アルゴリズムもまた閾値設定に基づき、しかし、スクリーニングされたピクセル及び選ばれた出力値との間にできたエラー（０又は255）は、スクリーニングされているピクセルの非処理された近傍において分散されることを思い出されたい。近傍は、処理されているピクセルの直ぐ近隣のピクセルによって構成される。エラーは、係数によって重み付けられて分散される。各近傍は、それ自身の係数を有する。かかる係数及びこのアルゴリズムは、１９７５年Floyd及びSteinbergによって定義された。実際問題として、Floydによって定義された係数が使用されている。しかし、本発明は、他のセットの係数の実施を反対するものではない。
【００６１】
従って、記載されているPenroseタイリングに従う分布は、エラー−分散アルゴリズム又は閾値マトリックス・アルゴリズムの実施において使われるマトリックスの確かな閾値に起因するだけである。
従って、本発明の方法は、次のように要約されることができる：
【００６２】
１．与えられた大きさのイメージのブロックが検索される。そして、イメージ・ブロックと同じサイズを有するマトリックス（閾値マトリックスと称す）が、ダイナミックレンジの半分を表示している値（本例では１２７）で初期化される。
ａ．イメージの適応細区分は、タイリングをつくるために実行される
ｉ．終了基準に達するまで、各細区分構成は細区分される。
ｂ．タイリングから、サンプリング・ドットのマトリックスはつくられる。
各サンプリング構成のために
ｉ．閾値は、ラベルの関数として計算される。
ii．Ｒ2において定義されるその座標が検索される。
iii．それに対して、構造インデックス及び重要性インデックスを使用して訂正がなされる。
iv．訂正された座標は、閾値マトリックスのドットの離散的な座標を得るために離散的にされる。
v．計算された閾値は、閾値マトリックスのステップ（i）に、ステップ（iv）において計算される位置で挿入される。
ｃ．エラー−分散アルゴリズムが適用される。アルゴリズムはイメージ・ブロックの内部に適用され、各ピクセル毎に、閾値のマトリックスから来ている閾値が適用される。
【００６３】
このように実行される方法により、より洗練されていないスクリーニング方法では許容せざるを得ない全ての人為的なものなしに、実行することが可能である。
【００６４】
本方法は、イメージ全体に対しても又はそのイメージのブロックに対しても実行できる利点を有する。従来の例において、ブロックは、１６ピクセル×１６ピクセルの大きさ又は３２ピクセル×３２ピクセルの大きさである。本発明の方法は、より大きいブロックにも適用でき、しかし、これは従来のプリントのコンテクストにはない事例である。当然、伝統的には、ブロック処理の場合、ブロックの端（右辺及び最下辺）でエラーは、近傍ブロックに伝わる。
【００６５】
実施の好適な例において、本発明で使われるタイリング方法を実行する方法に従って、訂正テーブルのベクトルは、ステップ１０６の前にステップ１０８において予め計算される。訂正テーブルのベクトルは、処理されるイメージから独立している。訂正ベクトルのテーブルの生成の方法を以下に説明する。
【００６６】
予備ステップにおいて、訂正ベクトルのテーブルが初期化され、全てのベクトルがゼロ（0,0）とされる。
【００６７】
各重要性インデックスのために、ドットのクラウドから成っているイメージが例えばランダムに生成され、これらのドットのグレーレベルが重要性インデックスに対応する。このイメージのために、タイリングは、本発明によって実行される方法に従って実行され、それによって、サンプリング構成は所与の位置で得られる。緩和アルゴリズム、例えば、Lloydのアルゴリズムがこれらのサンプリング構成に適用され、各サンプリング構成はドットであるとみなされ、且つ構造インデックスと関連付けられている。
【００６８】
簡単な方法において、Lloydのアルゴリズムは、次のように表すことができる。
１．ドットのセット（この場合サンプリング構成）がとられる。
２．Voronoiの多角形処理がドットのセットに対して実行される、
３．ドットを囲んでいる各多角形毎に重心が計算され、そして、ドットを生成している多角形は、重心にシフトされる。
４．ステップ２及び３が収束まで繰り返される
【００６９】
それから、各構造インデックス毎に、それらの元の位置に対するドットのシフトの平均値Ｖｍが計算される。この平均値は、訂正テーブルに既に存在するベクトルで、平均訂正ベクトルを計算するために用いる。それ故、テーブルは、次の式に従って更新される。
Ｖ＝（ｋ・Ｖ＋Ｖｍ）／（ｋ＋１）
ここで、ｋは、重要性インデックスのために既に生成されているドットのクラウドの数である。
【００７０】
このような処理が、訂正ベクトルの安定化まで、すなわちＶｍの影響が値Ｖに対して無視可能になるまで、繰り返される。
テーブルが得られる毎に、フィルタリングと等価な動作がローパスフィルタによって実行される。これは、或る数の訂正ベクトルを消去する効果を有する。
【００７１】
ステップ１０８に対応するこれらのステップは、本発明の方法で使用できる訂正ベクトルのテーブルを決定するために用いる。測定において、緩和テーブルと称すことができる訂正テーブルは予め計算される。本発明の方法は特に良く実行する。所与のタイリング方法を使用する際に本発明の方法を実行している全てのスクリーニング・デバイスのために上記ステップは一度だけ実行される。実際問題として、それ故、ステップ１０８はスクリーニング・デバイスによって実行されない。しかし、ステップ１０８の結果はスクリーニング・デバイスのメモリに格納される。
【図１】
2010283854.tif 000008
【図２ａ】
2010283854.tif 000009
【図２ｂ】
2010283854.tif 000010
【図２ｃ】
2010283854.tif 000011
【手続補正書】
【提出日】平成22年8月16日(2010.8.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
スクリーニング・デバイスによって実行される以下のステップを具備することを特徴とする、印刷前にイメージをスクリーニングする方法であって、
（１）自己類似構成の実施によって得られる非周期的な構成によってスクリーニングされるイメージに対してタイリング（１００）を行う、すなわち、そのタイリングは、前記構成をルールに従って分割して新しい構成を与え、その新しい構成を同一にするためにルールに従って更に分割して行い（１０２）、但し、そのようにして得られた構成の中からサンプリング構成及び細区分構成が区別され、サンプリング構成はドットに例えられ、細区分構成だけが再び分割される、
（２）タイリングが分割されるべき構成によっておおわれるイメージのゾーンの輝度に依存するので、タイリングは適応性があり、構成の輝度が予め定められた閾値未満になるときに、細区分構成の分割は中止し（１０４）、
（３）イメージの表面積単位当たりの細区分構成の記録密度が閾値より高くなるときに、細区分構成の分割は中止され（１０４、
（４）各分割で、スクリーニング装置は、同様に各新しい構成と既存のサンプリング構成とにラベルを割り当て（１０３）、
（５）タイリングの最後に、各サンプリング構成は、二入力訂正テーブル中の該当する訂正ベクトルの関数として実行されるピクセルと関連付けられ（１０６）、二入力訂正テーブル中の第１の入力は、サンプリング構成のラベルであり、二入力訂正テーブル中の第２の入力は、サンプリング構成に対応するポイントであり、各サンプリング構成は、訂正テーブルの入力としてサンプリング構成を機能させたイメージのドットと関連した状態のままになっており、
（６）各サンプリング構成は、サンプリング構成のラベルの関数として、関連した閾値を有し（１０５）、
（７）前のステップにおいて決定される閾値は、ハーフトーン・レンダリング方法を実行するために使用され（１０７）、
ハーフトーン・レンダリング方法の実施のための以前のステップにおいて決定される閾値の使用の前に、スクリーニング・デバイスが、訂正テーブルの訂正ベクトルを決定するためにサンプリング構成に対して緩和アルゴリズムを実行することを特徴とする
ことを特徴とするイメージをスクリーニングする方法。