(57)【要約】【課題】ディザ・マスクを生成する技法を提供すること。【解決手段】第１色および第２色のうちの少なくとも１つの画素を有する少なくとも３つのオリジナル・パターンのシーケンスを選択することによってディザ・マスクを生成する。少なくとも２つのパターンを補間して、少なくとも３つのオリジナル・パターンの間のシーケンス内で補間されたパターンを生成する。少なくとも１つの指定された特性を有するパターンがシーケンスに存在する場合に、少なくとも２つのパターンの間で補間するステップと、少なくとも１つの指定された特性を有するパターンがシーケンスに存在するかどうかを判定するステップとを繰り返す。補間は、シーケンス内の少なくとも１つの指定された特性を有するパターンの各側からの少なくとも１つのパターンの間で行われる。【選択図】図２
2008516468.tif 000002
【特許請求の範囲】
【請求項１】
第１色および第２色のうちの少なくとも１つの画素を有する少なくとも３つのオリジナル・パターンのシーケンスを選択するステップと、
前記少なくとも３つのオリジナル・パターンの間の前記シーケンス内で補間されたパターンを生成するために、少なくとも２つのパターンの間で補間するステップと、
少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するかどうかを判定するステップと、
少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するときに、（ｉ）少なくとも２つのパターンの間で補間するステップであって、前記補間が、前記シーケンス内の少なくとも１つの指定された特性を有する前記パターンの各側からの少なくとも１つのパターンの間で行われる、ステップと、（ｉｉ）少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するかどうかを判定するステップとを繰り返すステップと
を含む、ディザ・マスクを生成する方法。
【請求項２】
少なくとも１つの指定された特性を有するパターンを含まない新しいディザ・マスクを生成するステップをさらに含む、請求項１に記載の方法。
【請求項３】
新しいディザ・マスクを生成する前記ステップにおいて、前記新しいディザ・マスクの補間されたパターンが、少なくとも１つの指定された特性を有する前記パターンの少なくとも１つの特性を含む、請求項２に記載の方法。
【請求項４】
少なくとも２つのパターンの間で補間する前記ステップが、
前記少なくとも２つのパターンの対から、第１パターン内で第１色であり、第２パターン内で第１色でない画素の集合を定義することと、
前記ディザ・マスク内で画素の前記集合に対応する位置のグレイ・レベルに関する整数を入力することと、
少なくとも１つの追加パターンが少なくとも２つのパターンの前記シーケンス内に存在するときに、パターンの第２対に関して画素の集合を定義する前記ステップと整数を入力する前記ステップとを繰り返すステップであって、前記第２パターンが新しい第１パターンになり、追加パターンが新しい第２パターンになる、ステップと
を含む、請求項１に記載の方法。
【請求項５】
前記第２パターン内の第１色の画素に対応するすべての位置について入力（エントリー）が前記ディザ・マスク内に置かれるまで繰り返すステップをさらに含む、請求項４に記載の方法。
【請求項６】
少なくとも２つのパターンの間で補間する前記ステップにおいて、少なくとも２つのパターンの前記シーケンス内の前記第１パターンが、第２色のすべての画素を含み、少なくとも２つのパターンの前記シーケンス内の最後のパターンが、第１色のすべての画素を含む、請求項４に記載の方法。
【請求項７】
パターンごとに対応するグレイ・レベルを定義するステップをさらに含む、請求項４に記載の方法。
【請求項８】
パターンごとに対応するグレイ・レベルを定義する前記ステップにおいて、少なくとも２つのパターンの前記シーケンスの前記第１パターンのグレイ・レベルが０であり、少なくとも２つのパターンの前記シーケンスの最後のパターンのグレイ・レベルが１である、請求項７に記載の方法。
【請求項９】
パターンの少なくとも１つの対について１つまたは複数の制約を選択するステップをさらに含む、請求項４に記載の方法。
【請求項１０】
再配置された画素を有する前記第１パターンとして前記第１パターンを再定義するステップと、前記第１パターンのグレイ・レベルを調整するステップとをさらに含む、請求項９に記載の方法。
【請求項１１】
前記選択された制約を満足するために画素の前記集合を再配置するステップをさらに含む、請求項９に記載の方法。
【請求項１２】
画素の前記集合を再配置する前記ステップにおいて、前記再配置された画素が、前記集合内に留まり、実質的に非周期的なパターンを形成する、請求項１１に記載の方法。
【請求項１３】
前記画素を再配置するステップが、前記画素および前記集合の総ポテンシャルを計算し、評価することを含む、請求項１１に記載の方法。
【請求項１４】
実質的に最小の総ポテンシャルを有する画素が前の反復で実質的に最大の総ポテンシャルを有する画素になるまで、前記実質的に最大の総ポテンシャルを有する画素を、前記制約を満足する実質的に最小の総ポテンシャルを有する前記集合内の画素に反復して移動するステップをさらに含む、請求項１３に記載の方法。
【請求項１５】
画素の再配置された構成が以前の構成よりよいかどうかを判定するステップをさらに含む、請求項１３に記載の方法。
【請求項１６】
１つまたは複数の制約を選択する前記ステップにおいて、制約が、クラスタ化判断基準を含む、請求項９に記載の方法。
【請求項１７】
整数を入力する前記ステップにおいて、前記整数が、前記第１パターンのグレイ・レベルの個数およびグレイ・レベルに関する、請求項４に記載の方法。
【請求項１８】
整数を入力する前記ステップにおいて、前記マスクに整数を充てんすることが、パターンの対ごとにグレイ・レベルの中間調（ハーフトーン）を生成する、請求項４に記載の方法。
【請求項１９】
少なくとも２つのパターンの間で補間する前記ステップにおいて、パターンの各対が、少なくとも２つのパターンの前記シーケンス内で連続する、請求項４に記載の方法。
【請求項２０】
イメージを中間調にする方法であって、前記方法が
第１色および第２色のうちの少なくとも１つの画素を有する少なくとも３つのオリジナル・パターンのシーケンスを選択するステップと、
前記少なくとも３つのオリジナル・パターンの間の前記シーケンス内で補間されたパターンを生成するために、少なくとも２つのパターンの間で補間するステップと、
少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するかどうかを判定するステップと、
少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するときに、（ｉ）少なくとも２つのパターンの間で補間するステップであって、前記補間が、前記シーケンス内の少なくとも１つの指定された特性を有する前記パターンの各側からの少なくとも１つのパターンの間で行われる、ステップと、（ｉｉ）少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するかどうかを判定するステップとを繰り返すステップと
を含む、ディザ・マスクを生成するステップと、
イメージの１つまたは複数の画素を前記ディザ・マスクと比較するステップと、
前記ディザ・マスクとの比較に基づいて前記画素のうちの１つまたは複数についてドットを印刷するステップと
を含む、方法。
【請求項２１】
イメージを走査してイメージ・ストレージに保存するステップをさらに含む、請求項２０に記載の方法。
【請求項２２】
より大きいディザ・マスクを形成するために、前記ディザ・マスクを第２ディザ・マスクと組み合わせるステップをさらに含む、請求項２０に記載の方法。
【請求項２３】
メモリと、
前記メモリに結合され、（ｉ）第１色および第２色のうちの少なくとも１つの画素を有する少なくとも３つのオリジナル・パターンのシーケンスを選択し、（ｉｉ）前記少なくとも３つのオリジナル・パターンの間の前記シーケンス内で補間されたパターンを生成するために、少なくとも２つのパターンの間を補間し、（ｉｉｉ）少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するかどうかを判定し、（ｉｖ）少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するときに、（ａ）少なくとも２つのパターンの間で補間する動作であってし、前記補間が、前記シーケンス内の少なくとも１つの指定された特性を有する前記パターンの各側からの少なくとも１つのパターンの間で行われる、動作と、（ｂ）少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するかどうかを判定する動作とを繰り返すように動作する、少なくとも１つのプロセッサと
を含む、ディザ・マスクを生成する装置。
【請求項２４】
少なくとも２つのパターンの間で補間する前記動作が、
前記少なくとも２つのパターンの対から、第１パターン内で第１色であり、第２パターン内で第１色でない画素の集合を定義するステップと、
前記ディザ・マスク内で画素の前記集合に対応する位置のグレイ・レベルに関する整数を入力するステップと、
少なくとも１つの追加パターンが少なくとも２つのパターンの前記シーケンス内に存在するときに、パターンの第２対に関して画素の集合を定義する前記ステップと整数を入力する前記ステップとを繰り返すステップであって、前記第２パターンが新しい第１パターンになり、追加パターンが新しい第２パターンになる、ステップと
を含む、請求項２３に記載の装置。
【請求項２５】
前記プロセッサが、パターンの少なくとも１つの対について１つまたは複数の制約を選択するようにさらに動作する、請求項２４に記載の装置。
【請求項２６】
前記プロセッサが、前記選択された制約を満足するために画素の前記集合を再配置するようにさらに動作する、請求項２５に記載の装置。
【請求項２７】
前記画素を再配置する前記動作が、前記画素および前記集合の総ポテンシャルを計算し、評価することを含む、請求項２６に記載の装置。
【請求項２８】
前記プロセッサが、実質的に最小の総ポテンシャルを有する画素が前の反復で実質的に最大の総ポテンシャルを有する画素になるまで、（前記）実質的に最大の総ポテンシャルを有する画素を、前記制約を満足する前記実質的に最小の総ポテンシャルを有する前記集合内の画素に反復して移動するようにさらに動作する、請求項２７に記載の装置。
【請求項２９】
前記プロセッサが、画素の再配置された構成が以前の構成よりよいかどうかを判定するようにさらに動作する、請求項２７に記載の装置。
【請求項３０】
第１色および第２色のうちの少なくとも１つの画素を含む少なくとも３つのオリジナル・パターンのシーケンスを選択するステップと、
前記少なくとも３つのオリジナル・パターンの間のシーケンス内で補間されたパターンを生成するために、少なくとも２つのパターンの間で補間するステップと、
少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するかどうかを判定するステップと、
少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するときに、（ｉ）少なくとも２つのパターンの間で補間するステップであって、前記補間が、前記シーケンス内の少なくとも１つの指定された特性を有する前記パターンの各側からの少なくとも１つのパターンの間で行われる、ステップと、（ｉｉ）少なくとも１つの指定された特性を有するパターンが前記シーケンスに存在するかどうかを判定するステップとを繰り返すステップと
をコンピュータに実行させて、ディザ・マスクを生成するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディザ・マスク生成技法に関し、より具体的には、反復補間によってディザ・マスクの生成することを含む中間調生成（ｈａｌｆｔｏｎｉｎｇ）のための方法および装置に関する。
【背景技術】
【０００２】
ディジタル・ハーフトーニング（中間調生成）は、小さいドットおよび限られた個数の色が使用される、２次元媒体で画像を表示する技法である。この画像は、適切な距離から見られたときに多数の色からなるように見える。たとえば、黒ドットおよび白ドットからなる画像は、さまざまなグレイ・レベルを表示しているように見せることが可能である。
【０００３】
当初は非常に粗い解像度を有する純粋に白黒のマシンであったディジタル・プリンタが、カラー、より微細な分解能に対処し、最近では１画素あたり複数ビットの情報に対処するように進歩してきた。本明細書で使用する画素は、ピクセルまたはペルを指す場合がある。
【０００４】
ディジタル・ハーフトーニングの最も高速で最も一般的に使用されている方法が、ディザリング・アルゴリズムであり、これは、閾値配列を使用し、ディザ・マトリックスまたはディザ・マスクとも呼ばれる。ディザ・マスクは、ハードウェアまたはソフトウェアのいずれかで定義されるが、数の行列と考えることができる。このマスクの最初の形は、「順序付ディザ（ordered dither）」と呼ばれ、閾値の周期的パターンを使用する。「ランダム・ディザ（random dither）」では、閾値が、ある確率過程に従って選ばれる。従来のディザ・マスクは、多数のグレイ・レベルを提供しなかった。これは、クラスタ化マスク（clusteredmask）の場合に特にそうであり、この場合に、より暗いグレイは、分散化マスク（dispersedmask）に従って使用される拡散技法ではなく、黒ドットのより大きいクラスタを印刷することによって生成された。両方のタイプのマスクが、ディジタル印刷で重要であり、クラスタ化マスクは、通常、レーザ・プリンタと共に使用され、分散化マスクは、通常、インク・ジェット・プリンタと共に使用される。
【０００５】
マスクは、マスクのサイズが、レンダリングされる所与の個数の別個のグレイ・レベルに必要な最小サイズとほぼ同じ場合、またはマスク内の閾値の配置が意図的に周期的構造を形成する場合に、周期的と定義される。非周期的とは、通常、「長周期」を指し、これは、閾値のそれぞれが、結果のマスクがより小さい同一のマスクの単なる並置ではない形でマスク内で比較的多数回繰り返されることを意味する。
【０００６】
ディザ・マスクの設計の多すぎるランダムさが、イメージをぼけさせ（blur）、美的でない結果を生む。１９８０年代末に、青ノイズまたはグレイ・レベルの大多数に関して半径方向に平均したパワー・スペクトルで減衰された低周波数を有するノイズが、改善された視覚的影響をもたらすことが発見された。たとえば、R.Ulichney,"Dithering with Blue Noise,"Proc.IEEE76,No.1,1988,pp.56-79を参照されたい。青ノイズを有するディザ・マスクを構成する方法が、その後に提案された。たとえば、Parkerらの米国特許第５，１１１，３１０号、M.Yaoet al.,"Modified Approach to the Construction of a Blue NoiseMask,"J.of Electronic Imaging 3,No.1,1994,pp.92-97、およびR.Ulichney,"TheVoid-and-Cluster Method for Dither Array Generation,"Proc.SPIE1913,1993,pp.332-343を参照されたい。
【０００７】
青ノイズ・マスクは、分散されたドットを生成し、これは、グレイ・レベルが、すべての黒ドットを分離させることが起こりそうもないか不可能にするのに十分に暗い場合に限って、黒ドットをクラスタ化のみできることを意味する。その結果、青ノイズ・マスクは、レーザ・プリンタまたは静電プリンタに実用的ではない。
【０００８】
クラスタ化を達成するために、伝統的な閾値配列を構成し、その結果、高まるグレイ・レベルが固定周期でのより大きいクラスタの印刷に対応するようにすることができる。この方法は、不満足なボケ（artifact）を生成しないが、そのような方法を使用して表すことのできるグレイ・レベルの個数が少なすぎるか、生成されるクラスタが大きすぎるかのいずれかである。これらの影響を訂正するために、マルチセル・アレイを使用することができ、これは、複数の単一クラスタ閾値アレイによってタイリングされる。マルチセル・アレイでは、複数のクラスタが、単一クラスタ・アレイと同一の空間周期で大きくなるが、同時には大きくならない。これによって、追加の中間グレイ・レベルが可能になる。伝統的なマルチセル・アレイは、周期的と考えられ、セルが大きくなる順序および方法は、一般に、複数のグレイ・レベルでの不満足な周期的パターンを生成する。
【０００９】
ディザ・マスク生成における２つの重要な問題が、クラスタ化された非周期的マスクおよびボケのないマルチセル・マスクを作ることである。通常、マルチセル・クラスタ化ディザ・アレイは、均一なグレイのすべての可能なレベルでテストされるときに、レンダリングされる均一なグレイ・レベルおよびプリンタの物理的特性に依存して、よいパターンとより許容できないパターンとの両方を生成する。
【００１０】
これらの問題は、
１）Thompsonらの米国特許第５，９１７，９５１号（以下では「ＴＴＷ１」と称する）、
２）Thompsonらの米国特許第６，０２５，９３０号（以下では「ＴＴＷ２」と称する）、
３）Stanichらの米国特許第６，５９７，８１３号（以下では「ＳＴＴＷ」と称する）、および
４）C.W.Wu et al.,"Supercell dithermasks with constrained blue noise interpolation,"NIP 17:IS&T'sInternational Conference on Digital printing Technologies,2001,pp.487-490
で連続して対処された。
【００１１】
これらの問題の解決において、たとえばレーザ・プリンタまたは静電プリンタで、必要に応じてハーフトーニングの許容できるパターンを生成するために、青ノイズおよびクラスタ化の利点を組み合わせる技法を提供することが一般的であった。
【００１２】
より具体的には、ＴＴＷ１、ＴＴＷ２、およびＳＴＴＷによれば、グレイ・スケール・イメージのハーフトーニングの方法は、部分的にランダムで部分的に決定的な単一値の関数からなるクラスタ化非周期的マスクに対するイメージの画素ごとの比較を利用し、この関数は、グレイの任意のレベルで閾値制限されたときに、視覚的に満足なドット構成を生成するように設計されている。ＴＴＷ１に対するＴＴＷ２の基本的な改善は、より青みを帯びた影響（more blueish effect）をもたらすことであった。ＴＴＷ１およびＴＴＷ２に対するＳＴＴＷの基本的な改善は、最も明るいグレイ・レベルから最も暗いグレイ・レベルへマスクを構成するときのクラスタ化の変調（modulation）であった。したがって、非ランダム・ディザ・マスクが構成され、このマスクは、青ノイズを目に満足なものにする、同様の周期性の欠如を提示する。しかし、ＴＴＷ１、ＴＴＷ２、およびＳＴＴＷは、クラスタ化の場合に審美的判断基準に対する柔軟性および適合性をもたらすが、分散化の場合に類似する利点を提供することができない。より具体的には、これらは、ディザ・マスク内の望ましくないパターンの所望の特性を維持する際の柔軟性を提供することができない。
【特許文献１】米国特許第５，１１１，３１０号
【特許文献２】米国特許第５，９１７，９５１号
【特許文献３】米国特許第６，０２５，９３０号
【特許文献４】米国特許第６，５９７，８１３号
【非特許文献１】R.Ulichney,"Dithering withBlue Noise,"Proc.IEEE 76,No.1,1988,pp.56-79
【非特許文献２】M.Yao et al.,"ModifiedApproach to the Construction of a Blue Noise Mask,"J.of Electronic Imaging3,No.1,1994,pp.92-97
【非特許文献３】R.Ulichney,"The Void-and-ClusterMethod for Dither Array Generation,"Proc.SPIE 1913,1993,pp.332-343.
【非特許文献４】C.W.Wu et al.,"Supercelldither masks with constrained blue noise interpolation,"NIP 17:IS&T'sInternational Conference on Digital printing Technologies,2001,pp.487-490.
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明は、ディザ・マスクを生成し、利用する技法、より具体的には、複数の異なる色（たとえば黒および白）の画素の好ましいパターンの集合の反復補間（iterativeinterpolation）を介してディザ・マスクを生成し、その結果、望ましくないパターンがシーケンスから除去されると同時にその特性がマスク内で維持されるようにする技法を提供する。
【課題を解決するための手段】
【００１４】
たとえば、本発明の一態様で、ディザ・マスクは、第１色および第２色のうちの少なくとも１つの画素を含む少なくとも３つのオリジナル・パターンのシーケンスを選択することによって生成される。少なくとも２つのパターンを補間して、少なくとも３つのオリジナル・パターンの間のシーケンス内で補間されたパターンを生成する。少なくとも１つの指定された特性を有するパターンがシーケンスに存在する場合に、少なくとも２つのパターンの間で補間するステップと、少なくとも１つの指定された特性を有するパターンがシーケンスに存在するかどうかを判定するステップとを繰り返す。補間は、シーケンス内の少なくとも１つの指定された特性を有するパターンの各側からの少なくとも１つのパターンの間で行われる。
【００１５】
本発明の追加実施形態では、ディザ・マスクを生成することと、イメージの各画素をディザ・マスク内の閾値と比較することとによって、イメージを中間調に（ハーフトーニング）する。第１色のドットを、ディザ・マスクの比較に基づいて、１つまたは複数の画素について印刷する。
【００１６】
有利なことに、パターンの初期シーケンスのあるプロパティを、これらの事例のマスク生成装置を明示的に設計する必要なしに最終的なディザ・マスクに与えることができる。そうでなければ特殊化されたアルゴリズムおよび方法を必要とするはずの完全に異なるマスク特性を、本発明を使用して達成することができる。
【００１７】
本発明の上記および他の目的、特徴、および利益は、添付図面と共に読まれるべき本発明の例示的実施形態の次の詳細な説明から明白になる。
【発明を実施するための最良の形態】
【００１８】
次の説明で、例示的なデータ処理システム・アーキテクチャを使用して本発明を示す。しかし、本発明が、特定のシステム・アーキテクチャと共に使用することに限定されないことを理解されたい。本発明は、その代わりに、ハーフトーニング技法に関してディザ・マスクを生成することが望ましいすべてのシステムにより一般的に適用可能である。
【００１９】
以下で詳細に示すように、本発明は、ディザ・マスクを生成する技法、より具体的には、複数の色（たとえば黒および白）の画素の好ましいパターンの集合の反復補間を介してディザ・マスクを生成し、その結果、望ましくないパターンがシーケンスから除去されると同時にその特性がディザ・マスク内で維持されるようにする技法を導入する。
【００２０】
当業者は、１画素あたり１ビットの情報を有するプリンタ・モデルに対する改善を、より高度な機械に簡単に適用できることを知っている。同様に、単一のディザ・マスクを生成し、使用する方法を、複数のディザ・マスクを同時に生成し、使用するように適合させることができる。以下で説明するディザ・マスク生成技法は、１画素あたり１ビットの情報を用いる白黒印刷のセッティングを利用するが、本技法は、カラー・プリンタおよびマルチビット・プリンタまたは他のイメージング・デバイスに拡張可能である。
【００２１】
本明細書で論じるように、マスクは、閾値の配列Ｍ＝［ｍ（ｉ，ｊ）］と定義され、ここで、ｉ＝１，２，…，ｈであり、ｊ＝１，２，…，ｖであり、ｈおよびｖは、それぞれマスクの水平サイズおよび垂直サイズである。ｍ（ｉ，ｊ）が、通常は１，２，…，Ｎとして調整されるＮ個の可能な値をとり、Ｎ’＝Ｎ＋１個の別個のグレイ・レベルをもたらすと仮定する。
【００２２】
プリンタの解像度（通常はプリンタのインチ毎のドット数（ｄｐｉ）として表される）になるようにスケーリングされる入力イメージは、入力値の配列Ａ＝［ａ（ｉ，ｊ）］であり、ここで、ｉ＝１，２，…，Ｈであり、ｊ＝１，２，…，Ｖであり、ＨおよびＶは、それぞれイメージの水平サイズおよび垂直サイズである。いくつかの実施形態で、Ｈ＞＞ｈかつＶ＞＞ｖであるが、この関係は、本発明のすべての実施形態について必要というわけではない。
【００２３】
プリンタ解像度での出力イメージ（ここでは白黒イメージ）は、出力値の配列Ｏ＝［ｏ（ｉ，ｊ）］であり、ここで、ｉ＝１，２，…，Ｈであり、ｊ＝１，２，…，Ｖであり、ＨおよびＶは、それぞれイメージの水平サイズおよび垂直サイズである。行あたりの画素数Ｈおよび列あたりの画素数Ｖは、配列ＡおよびＯについて同一である。
【００２４】
ＭおよびＡを与えられれば、出力イメージＯは、次のマスク式によって定義される。
ｏ（ｉ，ｊ）＝Ｓ（ａ（ｉ，ｊ）−ｍ（ｉ  ｍｏｄ  ｈ，ｊ  ｍｏｄ  ｖ））
ここで、Ｓ（ｘ）は、ｘ＜０の場合にＳ（ｘ）＝０、ｘ≧０の場合にＳ（ｘ）＝１によって定義されるステップ関数である。ステップ関数について、「１」は、画素を暗くすることに対応し、「０」は、画素を暗くしないことに対応する。
【００２５】
ａ（ｉ，ｊ）のあるグレイ・レベルｇについてｏ（ｉ，ｊ）＝１の場合に、ａ（ｉ’，ｊ’）のより暗いグレイ・レベルｇ’のすべてについてもｏ（ｉ’，ｊ’）＝１であり、ここで、ｉ  ｍｏｄ  ｈ＝ｉ’ｍｏｄ  ｈであり、ｊ  ｍｏｄ  ｖ＝ｊ’ｍｏｄ  ｖである。この制約は、拡張プロパティとして定義され、マスク式の直接の結果であり、視覚的に満足なマスクを生成する際の主要な障害の１つである。この問題を示すために、２つの均一なグレイ・レベルｇ１＜ｇ２を与えられれば、ｇ１について黒であるすべての画素が、ｇ２について黒にならなければならないことに留意されたい。
【００２６】
幾何学的観点から、ｈ×ｖディザ・マスクＭは、この配列を２次元トーラス（torus）であると考えることができるように、周期的境界条件を仮定することによって実施される。配列内の２つの点の間の距離に言及するか、関連する概念が使用されるときには、必ず、長方形上ではなくトーラス上の距離を定義することを意味する。記号Ｍは、行列、対応するｈ×ｖ長方形、またはトーラスの形で与えられる配列を指定するのに使用され、行列、長方形、またはトーラスのどれに言及しているかは、明瞭である。
【００２７】
Ｒが実数の集合を表し、Ｒ２が実数である２つの座標によってパラメータ化された平面を表すものとして、ある関数ｒ：Ｒ２→Ｒが、原点（origin）での最大数および原点から離れて移動するときに減少する数を有するか、原点での最小数および原点から離れて移動するときに増加する数を有するように選択される。関数ｒは、ポテンシャル関数として解釈されなければならない。ディザ・マスク生成方法と共に働き、ディザ・マスク生成方法がその中にあるステージでもある、グレイ・レベルｇｉに依存するポテンシャルｒを選択することによって、よりよい結果が得られる。
【００２８】
マスクを生成する方法を初期化するか再初期化するために、視覚的に満足である、パターンの初期シーケンスＰｋが選択される。パターンは、「０」および「１」のｈ×ｖ行列である。「０」は白画素に対応し、「１」は黒画素に対応する。各パターンＰｉは、グレイ・レベルｇｉ（０≦ｇｉ≦１）に対応し、このグレイ・レベルｇｉは、Ｐｉの全画素に対する黒画素の比率である。この初期シーケンス内のパターンの個数は、グレイ・レベルの最終的な個数より少なく、少なくとも２つのパターンすなわちすべて「０」およびすべて「１」を含む。この初期シーケンスは、すべての２つのパターンＰｉおよびＰｉ＋１について、Ｐｉ内で黒であるすべての画素がＰｉ＋１でも黒になるように、拡張プロパティを満足しなければならない。この初期条件は、グレイ・レベルｇ（Ｐ０１）＜ｇ（Ｐ０２）＜…＜ｇ（Ｐ０ｋ）を有するｋ個の開始パターンを用いて表すことができる。
【００２９】
したがって、閾値の集合全体が、前述の特許および論文に従って、すべてのグレイ・レベル１，２，…，Ｎ’について生成される。制約によって拡張プロパティを満足するＮ１個の視覚的に満足なグレイ・レベルｇ（Ｐ１１）＜ｇ（Ｐ１２）＜…＜ｇ（Ｐ１Ｎｌ）が、選択される。これらのグレイ・レベルは、初期条件ｇ（Ｐ０１）＜ｇ（Ｐ０２）＜…＜ｇ（Ｐ０ｋ）を含むことができるが、そうである必要はない。たとえば、初期条件を放棄することは、視覚的に満足であり、周期性を避けているように見えるが、開始パターンｇ（Ｐ０１）＜ｇ（Ｐ０２）＜…＜ｇ（Ｐ０ｋ）が周期的である場合に実際には周期的であるパターンをもたらす。
【００３０】
次に、新しいパターンｇ（Ｐ１１）＜ｇ（Ｐ１２）＜…＜ｇ（Ｐ１Ｎｌ）を、次のステージの初期条件として使用することができる。説明される方法は、これを自然に反復でき、連続するステージおよび新しい初期条件、たとえばｇ（Ｐｍ１）＜ｇ（Ｐｍ２）＜…＜ｇ（ＰｍＮｍ）が生成されるように考案されている。
【００３１】
この方法は、約Ｎ’個の満足なグレイ・レベルを有するとき、すなわち、ＮｍがほぼＮ’と等しいときに終了する。この近似は、いくつかのグレイ・レベルが大きい視覚的影響を有しないので許容できる。たとえば、欠けているレベルは、分離された、非常に明るいレベルまたは非常に暗いレベルである可能性がある。
【００３２】
完全なマスクを生成するこの方法は、まず、１つまたは複数のグレイ・レベルの初期条件として使用される特殊なグレイ・レベルだけの生成に集中することができる。このために、すべてのＮ’個のグレイ・レベルを作るのではなく、あるグレイ・レベルの近傍の連続するグレイ・レベルだけが生成され、ここで、選択されたグレイ・レベルが、初期条件として使用される。
【００３３】
たとえば、この方法の威力および融通性を、より明るいパターンおよびより暗いパターンと一緒にチェッカーボードを形成する１／２のグレイ・レベル（Ｎ／２未満の閾値レベル）に対応するハーフトーン・パターンを用いて例示する。周期的でない隣接するグレイ・レベルが、次に生成され、一方は１／２より明るく、他方は１／２より暗い２つのグレイ・レベルが選択される。選択されたグレイ・レベルを、美しさのために変更することができ、その後、拡張プロパティを満足するためにさらに変更することができる。次に、この２つのレベルを使用して、グレイ・レベル１／２を生成し、この方法を、わずかに非周期的であり視覚的に満足とすることのできる１／２グレイ・レベルが生成されるまで繰り返す。
【００３４】
ここで図面、より具体的には図１を参照すると、ブロック図に、本発明の実施形態による、ハーフトーニング・システムが示されている。より具体的には、入力イメージ１００が、スキャナ１１０によってスキャン（走査）され、イメージ・アレイＡ＝ａ（ｉ，ｊ）としてイメージ・ストレージ１２０に保存され、ここで、（ｉ，ｊ）は、イメージ・アレイＡ内の画素位置である。入力イメージ１００を、他の方法および装置によってこのシステムに入力することもできる。ディザ行列アレイＭ＝ｍ（ｉ，ｊ）  １３０が、イメージ・ストレージ１２０内のイメージをハーフトーニング（中間調化）するのに使用される。
【００３５】
Ｎ’＝Ｎ＋１が、表されるべきグレイ・レベルの個数である場合に、この説明で検討されるすべてのｈ×ｖ行列Ｍ＝ｍ（ｉ，ｊ）は、閾値レベルを表す、０とＮとの間の数の配列である。ディザ・マスク生成は、次のマスク式に従って働き、
ｏ（ｉ，ｊ）＝Ｓ（ａ（ｉ，ｊ）−ｍ（ｉ  ｍｏｄ  ｈ，ｊ  ｍｏｄ  ｖ））
ハーフトーン・コンパレータ（比較器）１４０で出力イメージＯ＝ｏ（ｉ，ｊ）を生成する。次に、この配列を、プリンタ１５０での実際に印刷されるイメージ１６０に変換することができる。イメージの実際の印刷は、Ｍが完全に構成される前に開始することができる。プリンタは、ＡおよびＭからのＯの構成が行われるプロセッサの外部とすることができ、スキャナ、プロセッサ、およびプリンタなどの部分の間のすべての情報転送を、有線または無線とすることができる。
【００３６】
図２を参照すると、流れ図に、本発明の実施形態による、図１に示されたハーフトーニング・システムで使用されるディザ・マスクＭを生成する例示的方法が示されている。
【００３７】
この方法は、ブロック２１０で開始され、ここで、白画素および黒画素のｋ個のパターンの順序付きシーケンスＰ１，…，Ｐｋを選択する。各パターンは、ｈ×ｖのサイズを有し、ここで、ｈおよびｖは、正の整数である。各パターンＰｉについて、対応するグレイ・レベルｇｉ（０≦ｇｉ≦１）は、ブロック２１２で決定されるように、ｇｉ＝（Ｐｉの黒画素の個数）／（ｈ×ｖ）と定義される。Ｐ１は、すべてが白画素を有し、すべて「０」の行列を有する０行列として選択される。この選択は、完全さのために好ましいが、必要ではない。というのは、非常に明るいグレイも、本発明の実施形態に組み込むのが簡単であるからである。対応するグレイ・レベルｇ１は、０と等しい。Ｐｋは、すべて「１」の行列を有する、すべて黒画素のパターンとして選択される。やはり、この選択は、完全さのために好ましいが、非常に暗いグレイを本発明の実施形態に組み込むのが簡単なので、必要ではない。対応するグレイ・レベルは、ｇｋ＝１である。
【００３８】
ブロック２１４で、制約の組を選択する。制約の例に、クラスタ化判断基準（参照特許および論文を参照されたい）を含めることができる。制約を選択しないことも、制約の１タイプと考えることができる。パターンＰｉおよびＰｉ＋ｌの集合ごとに１つの制約を設けることができ、ここで、ｉは、１からｋ−１までの範囲である。
【００３９】
ディザ・マスクＭを、ブロック２１６で次のように初期化する。
１）Ｐ１内の黒画素ごとに、Ｍの対応する項目に、ｇ１×Ｎを整数に丸めたものをセットするが、ここで、Ｎは、ｍ（ｉ，ｊ）によって仮定される値の個数であり、
２）Ｐ２内の、Ｐ１に存在しない黒画素ごとに、Ｍの対応する項目に、ｇ２×Ｎを整数に丸めたものをセットし、
３）Ｐｉ内の、Ｐ１，…，Ｐｉ−１に存在しない黒画素ごとに、Ｍの対応する項目に、ｇｉ×Ｎを整数に丸めたものをセットする。
【００４０】
隣接するパターンＰｉおよびＰｉ＋１の対ごとに、マスクに閾値を充てんして、ｇｉとｇｉ＋１との間のグレイ・レベルに関するハーフトーンを生成する。
【００４１】
ブロック２１８で、ｉ＝１から開始して、Ｐｉ＋１では黒であるがＰｉでは黒でない画素の集合としてＱｉを定義する。Ｑｉの黒画素の個数をｔｉと表す。次に、ｔｉ／（Ｎｘ（ｇｉ＋１−ｇｉ））とほぼ等しい整数ｎｉを計算し、ブロック２２０で、隣接するパターンの対について制約を選択する。
【００４２】
次に、図３でさらに説明するように、ブロック２２２で反復方式を使用して、Ｑｉ内のｎｉ個の画素を
１．これらのｎｉ個の画素が、Ｑｉ内に残され、
２．これらのｎｉ個の画素が、Ｐｉと共に、十分な非周期的パターンを形成し、
３．これらのｎｉ個の画素が、Ｐｉと共に、選択された制約を満足する
ように再配置する。
【００４３】
ブロック２２４で、（ｇｉ×Ｎ）＋１に最も近い整数を、ディザ・マスクのこれらのｎｉ個の位置に入力する。これによって、Ｐｉおよびこれらの画素が、ｇｉ＋（１／Ｎ）とほぼ等しいグレイ・レベルに対応するパターンになることが保証される。
【００４４】
次に、ブロック２２６で、ＰｉをＰｉおよびｎｉ個の画素に置換し、ｇｉをｇｉ＋（１／Ｎ）に置換する。次に、ブロック２２８で、Ｐｉ＋１のすべての画素を考慮に入れたかどうか、または、エントリ（項目）がＭのＰｉ＋１内のすべての黒画素の位置に置かれたかどうかを判定する。まだすべての画素が考慮に入れられてはいない場合には、ブロック２１８、２２０、２２２、２２４、２２６、および２２８を繰り返す。
【００４５】
Ｐｉ＋１のすべての黒画素が考慮に入れられている場合には、ブロック２３０でｉを１つ増分して、グレイ・レベルの次の対（ｇｉ，ｇｉ＋１）の間のグレイ・レベルの充てんの次の反復を開始する。ブロック２３２で、ｉがｋ未満であるかどうかを判定するが、ここで、ｋは、パターンの総数である。そうである場合には、この方法は、パターンの次の対を用いてブロック２１８で継続する。ｉがｋ以上である場合には。ディザ・マスクＭのすべてのグレイ・レベルが考慮に入れられている。
【００４６】
ブロック２３４で、パターン・シーケンスに望ましくないパターンが存在するかどうかを判定する。望ましくないパターンは、あるユーザ指定の特性を有するものとすることができ、ユーザが個別に決定することができる。たとえば、ユーザは、純粋に周期的なパターンまたは純粋に確率的なパターンを望ましくないものと認める場合がある。シーケンスに望ましくないパターンがあると判定される場合に、この方法は、ブロック２３８で継続する。ブロック２３８では、望ましくないパターンの各側から少なくとも１つの、複数のパターンを選択する。次に、この方法は、ブロック２１０に戻って、初期パターンとしての複数の選択されたパターンの間で補間する（interpolate）。したがって、パターンの間でグレイ・レベルが形成され、望ましくないパターンが除去される。しかし、複数の選択されたパターンに渡された、望ましくないパターンからの特性も、新たに補間されるパターンに渡される場合がある。ブロック２３４で望ましくないパターンがない場合には、この方法はブロック２３６に継続する。
【００４７】
有利なことに、本発明の実施形態は、初期シーケンスのパターンのあるプロパティを、これらの事例のマスク生成装置を明示的に設計する必要なしに最終的なディザ・マスクに与える簡単で一般的な形を提供する。たとえば、クラスタ化が望まれる場合に、初期シーケンスのパターンが、クラスタ化され、本明細書で説明した補間が、クラスタ化ディザ・マスクを作るはずである。確率的に見えるが支配的な基本周波数を含むマスクを生成することが望まれる場合には、この周波数の１つまたは複数の分散化パターンを、スタータ集合として使用することができる。これらのパターンは、非常に規則的な分散化セットとすることができる。パターンのフル・セットへの補間の後に、補間されたパターンのうちの多数が、純粋に確率的に見えるが、なおかつこの支配的な基本周波数特性を保持する。その後、これらのパターンが、第２補間のために部分集合として選択され、結果のマスクは、青ノイズ・マスクであるように見える可能性があるが、それでも、スタータ・パターンからの支配的な周波数を含む。したがって、そうでなければ事例ごとに特殊化されたアルゴリズムおよび方法を必要とするはずの完全に異なるマスク特性を、本発明を使用して達成することができる。
【００４８】
ブロック２３６は、生成されたｈ×ｖマスクＭを別の事前定義のｈ２×ｖ２マスクＭ２と組み合わせて、より大きい（ｈ×ｈ２）×（ｖ×ｖ２）マスクＭ３にするのに使用することができる任意選択のステップを提供する。より大きいディザ配列Ｍ３は、比較的より小さいマスクＭを生成するのに主集中型計算（mainintensive computation）が実行されている間に作成することができる。この任意選択のステップは、ＴＴＷ１で十分に説明されている。この任意選択のステップが使用される場合に、ディザ・マスクＭ３が（Ｍではなく）、図１のイメージをハーフトーニングするのに使用される。
【００４９】
図３を参照すると、流れ図に、本発明の実施形態による、例示的な反復画素配置方法が示されている。これは、図２のブロック２２２の詳細な説明と考えることができる。
【００５０】
ブロック３１０で、選択された制約（ある場合に）を満足する、Ｑｉ内のｎｉ個の位置をランダムに選択する。制約が「制約なし」の場合には、Ｑｉ内のｎｉ個の位置をランダムに、または一様分布などのある好ましい分布を用いて、選択する。ブロック３１２で、ポテンシャルｒを、ｎｉ個の点のそれぞれおよびＰｉ内の黒画素のそれぞれに課す。次に、ＰＴ（総ポテンシャル）によって表されるポテンシャルの合計を、Ｑｉ内の制約を満足する点ごとに計算する。ポテンシャルｒは、ｇｉに依存する可能性がある。
【００５１】
ブロック３１４で、最小の総ポテンシャルＰＴを有する画素が、前の反復で最大の総ポテンシャルＰＴを有した画素であるかどうかを判定する。これが最初の反復である場合、または最小総ポテンシャルを有する画素が前の反復で最大総ポテンシャルを有しなかった場合には、この方法はブロック３１６に直接にジャンプする。最小総ポテンシャルを有する画素が前のアクションで最大総ポテンシャルを有する画素である場合には、この方法はブロック３２２にジャンプする。ブロック３１６では、ｎｉ個の点のうちで最大の総ポテンシャルＰＴを有する点を、最小の総ポテンシャルＰＴを有し２２０で選択された制約を満足するＱｉ内の点に移動する。次に、ブロック３１８で、反復カウントＣ１を増分する。ブロック３２０で、反復カウントＣ１が、ある所定の最大値より大きいかどうかを判定する。そうでない場合には、この方法は、ブロック３１２にジャンプして、もう１つの反復を開始する。そうである場合には、この方法は、ブロック３２２で継続する。
【００５２】
ブロック３２２では、カウントＣ２を増やす。ブロック３２４で、ｎｉ個の点の現在の構成が、前に保存された構成に対してよりよいかどうかを判定する。「よりよい」は、Ｑｉ内のクラスタ化判断基準を満足するすべての点にまたがる対応するＰＴの最大値から最小値を引いた値が、より小さいことを意味するものとすることができる。そうである場合には、ブロック３２６で現在の構成を保存する。そうでない場合には、現在の構成は保存されない。ブロック３２８で、Ｃ２がある所定の最大値より小さいかどうか、およびある事前設定の客観的測定に従ってまたは視覚的検査によって、ｎｉ個の位置の保存された構成が満足なパターンを形成するかどうかを判定する。そうでない場合（すなわち、Ｃ２が大きすぎる場合、またはパターンが満足でない場合）には、ブロック３１０にジャンプすることによって、Ｑｉ内のｎｉ個の位置の新しいランダム集合を選択する。そうである場合には、ｎｉ個の点の保存された構成が、図２のブロック２２２で使用される最終構成になる。
【００５３】
当業者は、本発明を使用して、適当なグレイ・レベルおよび不適当なグレイ・レベルを生成するすべてのマスクを訂正できることを認めるであろう。また、本発明は、あるマスクが生成することのできる別個のグレイ・レベルの個数を変更するのに簡単に使用することができる。したがって、グレイ・レベルの個数を増やすことができ、あるいは、完了後に、増やされたマスクの連続するグレイ・レベルをグループ化することによって減らすことができる。さらに、較正されたマスクを、Ｗｕらによる論文に従って生成することができる。
【００５４】
図４を参照すると、図に、ディザ・マスクのパターンの集合およびグレイ・レベルが示されている。初期シーケンスのグレイ・レベルｇｉ、ｇｊ、およびｇｋでのオリジナル・パターンの集合である。スタータ・グレイ・レベルｇｊは、グレイ・レベルｇｉとｇｋとの間の補間されたパターンに伝搬される特殊な属性を有する。図５は、図２のブロック２３４および２３８で説明した望ましくないパターンがあるときのグレイ・レベルを示す図である。より具体的には、グレイ・レベルｇｊが望ましくないパターンに対応する場合に、グレイ・レベルｇｊの両側の２つの補間されたパターンが、選択され、補間方法が、繰り返され、これによって２つの選択された補間されたパターンの間の新しい補間されたパターンが作成される。新しいパターンは、ｇｊからのいくつかの特性も有するが、ｇｊは、もはや存在しない。
【００５５】
図６を参照すると、ブロック図に、本発明の実施形態による、それに従って本発明の１つまたは複数の構成要素／方法（たとえば、図１、２、３、４、および５で説明した構成要素／方法）を実施できるコンピューティング・システムの例示的ハードウェア実施形態が示されている。たとえば、図６のそのようなコンピューティング・システムに、図１のスキャナ１１０、イメージ・ストレージ１２０、ハーフトーン・コンパレータ１４０、およびプリンタ１５０を含めることができる。
【００５６】
図からわかるように、このコンピュータ・システムは、コンピュータ・バス５１８または代替接続配置を介して結合された、プロセッサ５１０、メモリ５１２、入出力デバイス５１４、およびネットワーク・インターフェース５１６により実施することができる。
【００５７】
本明細書で使用される用語「プロセッサ」が、たとえば、ＣＰＵ（中央処理装置）または他の処理回路あるいはその両方を含むものなど、すべての処理デバイスを含むことが意図されていることを了解されたい。また、用語「プロセッサ」が複数の処理デバイスを指すことができることと、処理デバイスに関連するさまざまな要素を他の処理デバイスによって共用できることとを理解されたい。
【００５８】
本明細書で使用される用語「メモリ」は、たとえば、ＲＡＭ、ＲＯＭ、固定メモリ・デバイス（たとえば、ハード・ディスク）、取り外し可能メモリ・デバイス（たとえば、ディスケット）、フラッシュ・メモリなど、プロセッサまたはＣＰＵに関連するメモリを含むことが意図されている。
【００５９】
さらに、本明細書で使用される用語「入出力デバイス」または「Ｉ／Ｏデバイス」は、たとえば、処理ユニットにデータを入力する１つもしくは複数の入力デバイス（たとえば、キーボード、マウス、スキャナなど）、または処理ユニットに関連する結果を提示する１つもしくは複数の出力デバイス（たとえば、スピーカ、ディスプレイ、プリンタなど）、あるいはその両方を含むことが意図されている。図１の入力イメージ１００を、１つまたは複数の入出力デバイスにより供給することができる。
【００６０】
さらに、本明細書で使用される句「ネットワーク・インターフェース」は、たとえば、コンピュータ・システムが適当な通信プロトコルを介して別のコンピュータ・システムと通信することを可能にする１つまたは複数のトランシーバを含むことが意図されている。
【００６１】
本明細書で説明した方法を実行する命令またはコードを含むソフトウェア構成要素を、関連するメモリ・デバイス（たとえば、ＲＯＭ、固定メモリ、または取り外し可能メモリ）のうちの１つまたは複数に保管することができ、利用の準備ができたときに、部分的にまたは全体的に（たとえばＲＯＭに）ＣＰＵによってロードし、実行することができる。
【００６２】
添付図面を参照して、本発明の例示的実施形態を本明細書で説明してきたが、本発明が、これらの正確な実施形態に限定されないことと、本発明の範囲または趣旨から逸脱せずに、当業者がさまざまな他の変更および修正を作ることができることを理解されたい。
【図面の簡単な説明】
【００６３】
【図１】本発明の実施形態による、ハーフトーニング・システムを示すブロック図である。
【図２】本発明の実施形態による、図１のシステムのディザ・マスク生成方法を示す流れ図である。
【図３】本発明の実施形態による、反復画素配置方法を示す流れ図である。
【図４】本発明の実施形態による、その間に補間されたパターンを有するパターンの初期シーケンスを示す図である。
【図５】本発明の実施形態による、２つの選択されたパターンの間の第２補間を示す図である。
【図６】本発明の実施形態による、それに従って本発明の１つまたは複数の構成要素／方法を実施できるコンピューティング・システムの例示的ハードウェア実施形態を示す図である。
【図１】
2008516468.tif 000003
【図２】
2008516468.tif 000004
【図３】
2008516468.tif 000005
【図４】
2008516468.tif 000006
【図５】
2008516468.tif 000007
【図６】
2008516468.tif 000008