(57)【特許請求の範囲】
【請求項１】
第２世代の確率的ハーフトーン処理を用いて画像を２進化して、透かしを埋め込んだハーフトーン画像を生成する、コンピュータで実行する方法であって、
コントーンの入力画像及び透かし画像データを受け取るステップと、
前記画像内の所与の位置における前記入力画像のグレーレベル、及びそれらの位置における透かしの有無に基づいて、種の位置を決定するステップであって、透かし領域は第１のＦＭからＡＭへの遷移閾値を有し、非透かし領域は第２のＦＭからＡＭへの遷移閾値を有する、ステップと、
前記種の位置に基づいて、三角形分割を決定するステップと、
前記種の位置により決定された前記三角形分割に基づいて、ハーフトーンのスポット関数を計算して、前記入力画像内の画素ごとにスポット関数値を決定するステップと、
前記入力画像内の画素ごとに、入力画素値と、同じ位置のスポット関数値とを比較して、前記透かしを埋め込んだハーフトーン画像を生成するステップと、
前記透かしを埋め込んだハーフトーン画像を出力するステップと、を含む方法。
【請求項２】
透かし領域に関連する前記第１のＦＭからＡＭへの遷移閾値は、非透かし領域に関連する前記第２のＦＭからＡＭへの遷移閾値とは異なる、請求項１に記載の方法。
【請求項３】
前記第１のＦＭからＡＭへの遷移閾値の値と第２のＦＭからＡＭへの遷移閾値の値との間の距離が短くなると、前記透かしを埋め込んだハーフトーン画像の前記透かしの点が、人間の目には見えにくくなるよう、前記ＦＭからＡＭへの遷移閾値の値は調整可能である、請求項１に記載の方法。
【請求項４】
前記スポット関数は、
【数１】
0005872994.tif 000005
の式で規定され、「ａｉ」は前記「Ｈｉ」により規定された方向に沿ったドットの伸張を制御するパラメータであり、Ｑは前記スポット関数の出力値であり、ｈ１、ｈ２、ｈ３は、少なくとも１つの画素から、包含する三角形分割の三角形のそれぞれの底辺までの画素と交差する高さであり、前記三角形分割の三角形内には前記少なくとも１つの画素が存在し、前記包含する三角形分割の三角形は、高さＨ１、Ｈ２、Ｈ３を有し、前記スポット関数は、正規化された高さｈ１／Ｈ１、ｈ２／Ｈ２、ｈ３／Ｈ３を用いる、請求項１に記載の方法。
【請求項５】
前記スポット関数は、
【数２】
0005872994.tif 000006
の式で規定され、「ａｉ」は前記「Ｈｉ」により規定された方向に沿ったドットの伸張を制御するパラメータであり、Ｑは前記スポット関数の出力値であり、「γｉ」は前記ドットの辺の丸み、及びコーナーとの接触点の鮮明さを制御するパラメータであり、ｈ１、ｈ２、ｈ３は少なくとも１つの画素から、包含する三角形分割の三角形のそれぞれの底辺までの画素と交差する高さであり、前記三角形分割の三角形内には前記少なくとも１つの画素が位置し、前記包含する三角形分割の三角形は高さＨ１、Ｈ２、Ｈ３を有し、前記スポット関数は、正規化された高さｈ１／Ｈ１、ｈ２／Ｈ２及びｈ３／Ｈ３を用いる、請求項１に記載の方法。
【請求項６】
前記スポット関数は、
【数３】
0005872994.tif 000007
の式のように反転される、請求項５に記載の方法。
【請求項７】
請求項１に記載の方法を行うためのコンピュータが実行可能な命令を実行するよう構成されたプロセッサであって、前記命令はコンピュータ可読媒体に記憶される、プロセッサ。
【請求項８】
第２世代の確率的ハーフトーン処理を用いて画像を２進化して、透かしを埋め込んだハーフトーン画像を生成することを容易にするシステムであって、
プロセッサにより実行される、コンピュータが実行可能な命令を永続的に記憶するメモリと、
を備え、
前記プロセッサは、
コントーンの入力画像及び透かし画像データを受け取る手段と、
前記画像内の所与の位置における前記入力画像のグレーレベル、及び、前記画像内の前記所与の位置における透かしの有無に基づいて、種の位置を決定する手段であって、透かし領域は第１のＦＭからＡＭへの遷移閾値を有し、非透かし領域は第２のＦＭからＡＭへの遷移閾値を有する、手段と、
前記種の位置に基づいて、三角形分割を決定する手段と、
前記種の位置により決定された前記三角形分割に基づいて、ハーフトーンのスポット関数を計算して、前記入力画像内の画素ごとにスポット関数値を決定する手段と、
前記入力画像内の画素ごとに、入力画素値と、同じ位置のスポット関数値とを比較して、前記透かしを埋め込んだハーフトーン画像を生成する手段と、
前記透かしを埋め込んだハーフトーン画像を印刷する１又は複数のプリンタ、及び、前記前記透かしを埋め込んだハーフトーン画像を表示するグラフィカルユーザインターフェース（ＧＵＩ）に、前記透かしを埋め込んだハーフトーン画像を出力する手段と、
を含む、
ことを特徴とするシステム。
【請求項９】
透かし領域に関連する前記第１のＦＭからＡＭへの遷移閾値は、非透かし領域に関連する前記第２のＦＭからＡＭへの遷移閾値とは異なる、請求項８に記載のシステム。
【請求項１０】
前記第１のＦＭからＡＭへの遷移閾値の値と第２のＦＭからＡＭへの遷移閾値の値との間の距離が短くなると、前記透かしを埋め込んだハーフトーン画像の前記透かしの点が、人間の目には見えにくくなるよう、前記ＦＭからＡＭへの遷移閾値の値は調整可能である、請求項８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で開示する実施形態は、画像を印刷、再生又は表示する方法及びシステムに関する。より詳細には、本明細書で開示する教示は、クラスター型ドットのハーフトーン処理を行う方法及び装置に適用可能である。
【背景技術】
【０００２】
従来のハーフトーン処理を用いる透かしの埋め込み方法は、第１世代の確率的スクリーン（ＦＭ）に関して設計されている。当技術分野では、透かしを埋め込むための第２世代の確率的ハーフトーン処理を容易に行うシステム及び方法が所望される。
【発明の概要】
【課題を解決するための手段】
【０００３】
ある態様では、第２世代の確率的ハーフトーン処理を用いて画像を２進化して、透かしを埋め込んだハーフトーン画像を生成する、コンピュータで実行する方法は、コントーンの入力画像及び透かし画像データを受け取るステップと、画像内の所与の位置における入力画像のグレーレベル、及びその位置における透かしの有無に基づいて、種の位置を決定するステップと、を含み、透かし領域は第１のＦＭからＡＭへの遷移閾値を有し、非透かし領域は第２のＦＭからＡＭへの遷移閾値を有する。この方法は、種の位置に基づいて、三角形分割を決定するステップと、種の位置により決定された三角形分割に基づいて、ハーフトーンのスポット関数を計算して、入力画像内の画素ごとにスポット関数値を決定するステップと、入力画像内の画素ごとに入力画素値を同じ位置のスポット関数値と比較して、透かしを埋め込んだハーフトーン画像を生成するステップと、透かしを埋め込んだハーフトーン画像を出力するステップと、をさらに含む。
【０００４】
別の態様では、複数の第２世代の確率的ハーフトーンの閾値配列を用いて、透かしを埋め込んだハーフトーン画像を生成して画像を２進化する、コンピュータで実行する方法は、コントーン入力画像と、第１の第２世代の確率的ハーフトーンの閾値配列及び第２の第２世代の確率的ハーフトーンの閾値配列と、透かし画像データと、を受け取るステップと、透かし画像データの領域内の画素に関する第１の第２世代の確率的ハーフトーンの閾値配列から、ハーフトーンの閾値を選択するステップと、を含む。この方法は、非透かし画像データの領域内の画素に関するする第２の第２世代の確率的ハーフトーンの閾値配列から、ハーフトーンの閾値を選択するステップと、入力画像内の画素ごとに、入力画素値と同じ位置の選択された入力画素に関する閾値の値とを比較して、透かしを埋め込んだハーフトーン画像を生成するステップと、をさらに含む。この方法は、透かしを埋め込んだハーフトーン画像を出力するステップをさらに含む。
【０００５】
この特許のファイルには、少なくとも１枚のカラーで作成された図面が含まれる。カラー図面を含むこの特許の写しは、米国特許商標庁により、要求に応じて所定手数料を支払うだけで提供される。
【図面の簡単な説明】
【０００６】
【図１】図１は、第２世代のハーフトーン内での種の位置の空間分布を操作して、ハーフトーン処理及び印刷処理の一部として、画像への目に見えるデータ及び目に見えないデータの埋め込み及び／又は符号化を実現する、第２世代のハーフトーン処理の方法を示すフローチャートである。
【図２】図２は、画像の透かしを有する部分と、透かしを有さない画像の部分とのグレーレベルの関数としての単位面積ごとの種の数を示すグラフを示し、Ｔ１及びＴ２は、画像及び透かしがそれぞれＦＭからＡＭへ遷移したことを判定する閾値を示す。
【図３Ａ】図３Ａは、透かしが埋め込まれる、透かし領域を有する入力コントーン画像である。
【図３Ｂ】図３Ｂは、ハーフトーン画像の透かし領域内に埋め込まれる、透かし画像である。
【図３Ｃ】図３Ｃは、透かしが人間の目に見えるほど大きな透かし密度と画像密度との差を有する透かし画像を埋め込んだ透かし領域を拡大表示した２進バージョンの画像である。
【図３Ｄ】図３Ｄは、透かしが人間の目に見えるほど小さな透かし密度と画像度数との差を有する透かし画像を埋め込んだ透かし領域を拡大表示した２進バージョンの画像である。
【図４】図４は、２進画像を復号する方法を示すフローチャートである。
【図５】図５は、第２世代のスクリーンに関するグレーレベルの関数としてのドット数及びホール数を表すグラフであり、ＴはＦＭモードからＡＭモードへの遷移閾値を示す。
【図６】図６は、異なる２つの遷移閾値を用いた２つの第２世代のスクリーンに関するシグネチャを示すグラフであり、１方のシグネチャを実線で表し、もう１方を点線で表している。
【図７】図７は、暗い影の領域で形態学的浸食動作、及び明るい領域で形態学的拡張動作がそれぞれ行われた後の、異なる遷移閾値を有する第２世代のスクリーンに関するシグネチャ曲線のグラフである。
【図８】図８は、図４の方法で図３Ｄの画像内の目に見えない透かしを復号すること等により、生成された復号画像である。
【図９】図９は、本明細書に記載の１つ以上の特徴により、「活性」即ち「ｏｎ」と規定された、入力位置即ち種の配列の一例を示す説明図である。
【図１０】図１０は、点の集合に対する三角形の三角形分割の一例を示す説明図である。
【図１１】図１１は、頂点Ｐ１、Ｐ２、Ｐ３を有し、画素Ｐを包含する三角形を示す説明図である。
【図１２】図１２は、本明細書に記載の種々の方法の実行を容易にするシステムのブロック図である。
【発明を実施するための形態】
【０００７】
データを埋め込むための第２世代のハーフトーンのドットの種の空間分布を適用したハーフトーン処理方法を提供する。この方法では、透かしの有無に基づいて、順応的にハーフトーンのスクリーンのＦＭからＡＭへの遷移閾値を決定する。閾値を変更する量により、透かしが見えるかどうかが決定される。
【０００８】
図１は、第２世代ハーフトーン内の種の位置空間分布を操作して、画像への可視データ及び不可視データの組込み、及び／又は符号化を、ハーフトーン処理及び印刷処理の一部として実現する、第２世代のハーフトーン処理方法を示すフローチャートである。ある第２世代ハーフトーン処理方法では、密度変調（ＦＭ）の確率的な方法により特定なグレーレベルに達するまで核（種）を設け、次いで、その特定なレベルより上のレベルでは、大きさ変調（ＡＭ）の方法で、それらの核を大きく成長させる。本明細書に記載の方法では、所与の空間的位置での透かしの有無により、順応的にＦＭからＡＭへの遷移閾値が決定される。
【０００９】
ステップ１０、コントーンの画像データ（図３Ａ）及び透かしデータ（図３Ｂ）を受け取る。ステップ１２で、ハーフトーン画像の生成に関する種密度を決定する。透かし有無及び画像内の所与の位置における入力画像のグレーレベルに基づいて、種の位置（種の密度）を決定する。ステップ１４で、種を置く、即ち配置する。ステップ１６で、種を三角分割して、種を頂点として含む複数の三角形を形成する。ステップ１８で、種の位置により決定した三角形分割に基づいて、ハーフトーン処理のスポット関数を計算する。ステップ２０で、閾値アルゴリズムを実行する。つまり、スポット関数の閾値を画像に適用して、透かしを埋め込んだハーフトーンを生成する。ステップ２２で、原画像データ及び透かしデータを含むハーフトーン画像を生成し出力する。ＦＭからＡＭへの閾値を決定する量により、可透かしの視度が判定される。つまり、閾値の間隔が大きいことは、可視度が高いことを意味する。一実施形態では、画像の透かし領域と、非透かし領域とに関する、異なるＦＭからＡＭへの閾値を有する２つのスポット関数を用いて、２つの閾値配列を生成する。透かし位置と非透かし位置とを２つの閾値配列の間のスイッチとして用いることで、閾値を画像に適用する。高密度配列を発生させる種の集合は、低い密度配列を種の集合の上位集合である。すなわち、両方の配列は同じ集合の種を共有する。すなわち、種から低い密度配列が計算され、高い密度配列には追加の種が含まれ、これにより、種と種との間の距離が短くなり、透かし領域と非透かし領域との間の遷移が確保され、２進画像がスムーズになる。別の実施形態では、透かし位置及び非透かし位置に応じて種が生成され、それらの種に基づいて、スポット関数及び閾値が生成される。
【００１０】
一実施形態では、透かし領域に関して１つ、非透かし領域に関して１つの合計２つの透かしをスイッチとして用いる閾値配列を用いて、ハーフトーン処理を実行する。種スポット関数を用いて２つの閾値配列を生成する。種を用いて１方の配列を生成し、その種の上位集合の種を用いてもう１方の配列を生成する。上位集合で生成された配列は、高い方のＦＭからＡＭへの遷移閾値を有する。別の実施形態では、単一の確率的（ＦＭ）スクリーン処理を用いて、種を生成することができる。ＦＭ内の画素を用いて、低い方のＦＭからＡＭへの閾値を有する配列に対する種を、特定なグレーレベルの閾値まで生成する。ＦＭ内の画素を用いて、高い方のＦＭからＡＭへの閾値を有する配列に関する種を、グレーレベルの高い方の閾値まで生成する。同じＦＭスクリーンを用いて２つの集合の種を生成することにより、ハーフトーン処理される画像内の、透かし領域と非透かし領域との間の遷移が滑らかとなる。閾値に関する種を考慮して、上記のスポット関数のうち１つが適用されて、配列の範囲に閾値が生成される。印刷装置及び印刷特性のグレーの範囲に合わせるために、これらの閾値を補正又は調整等を行うことができる。所与の種の周りの複数の画素が同一の閾値を持たないように、第２の基準を用いて所与の閾値を上下させることできる。タイル状に配列を画像の範囲に埋め、配列に基づくハーフトーン処理を行う。画像内の各画素は、関連する同じ位置の閾値を配列内に有する。透かしのスイッチに基づいて、１方の配列、又はもう１方の配列のうちの１方から、閾値が選択される（即ち、閾値が選択された画素が、透かし領域内に存在するか、又は非透かし領域内に存在するか）。
【００１１】
別の実施形態では、第２世代の確率的ハーフトーン処理を用いて、透かしが埋め込まれたハーフトーン画像を生成して画像を２進化する。第１の主要密度の種の集合、及び第２の主要密度の種の集合をそれぞれ有するコントーン入力画像及び透かし画像データを、（例えば、プロセッサにより）受け取る。次いで、プロセッサは第１の集合及び第２の集合からの種を、それぞれ透かし画像データの領域内及び非透かし画像データの領域内に配置し、それによりもたらされる種の集合に関する三角形分割を決定し、それによりもたらされる三角形分割に対応するハーフトーンのスポット関数を計算する。次いで、プロセッサは、画素値と、同じ位置に存在するハーフトーンのスポット関数の値とを比較して、２進画素の値を生成し、（例えば、印刷するために）透かしが埋め込まれたハーフトーン画像を出力する。
【００１２】
図１による方法は、コンピュータ３０により実行することができ、このコンピュータ３０は、本明細書に記載の種々の機能を提供するためのコンピュータ可読命令を実行する（図１２プロセッサ３０４等の）プロセッサ及び、それを記憶する（図１２のメモリ３０６等の）メモリを含むことは言うまでもない。
【００１３】
コンピュータ３０は、本明細書に記載のシステム及び方法をサポートするための、ハードウェアの構成の１つの選択肢として用いることができる。独立型のアーキテクチャを示しているが、本実施形態により、好適な全てのコンピュータ環境を用いることができることは言うまでもない。例えば、独立型、マルチプロセッサ、分散型、クライアント／サーバ、ミニコンピュータ、メインフレーム、スーパーコンピュータ、デジタル式及びアナログ式等を含むコンピュータアーキテクチャを用いることができるが、それらには限定しない。
【００１４】
コンピュータ３０は、処理装置（例えば、図１２を参照）、システムメモリ（例えば、図１２を参照）、システムバス（図示せず）を含むことができ、このシステムバスは、システムメモリを含む種々システム構成要素と処理装置とを接続する。処理装置は、種々の全ての市販のプロセッサでよい。またダブルマイクロプロセッサ、及びその他のマルチプロセッサのアーキテクチャも処理装置として用いることができる。
【００１５】
一般にコンピュータ３０は、少なくとも何らかの形態のコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータのアクセスが可能な、市販の全ての媒体でよい。例えば、コンピュータ可読媒体には、コンピュータ記憶媒体及び通信媒体が含まれ得る。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、又はその他のデータ等の情報を記憶するための、全ての方法又は技術で実行される、揮発性媒体及び不揮発性媒体と、取外し可能媒体及び非取外し可能媒体とが含まれる。
【００１６】
一般に通信媒体は、コンピュータ可読命令、データ構造、プログラムモジュール又はその他のデータを具体化し、これらは搬送波又はその他の搬送機構等の変調データ信号内に含まれる。また通信媒体には、全ての情報発信媒体が含まれる。用語「変調データ信号」とは、その信号内の情報を符号化するために、その特性のうちの１つ以上の設定又は変更する信号のことを指す。例として、通信媒体には、有線ネットワーク又は直接有線接続等の有線媒体と、音響、ＲＦ、赤外線及びその他の無線媒体等の無線媒体と、が含まれるが、それらに限定されるわけではない。全ての上記の組合せも、コンピュータ可読媒体の範囲に含むことができる。
【００１７】
キーボード、ポインティングディバイス、マウス、スタイラスペン、音声入力、又はグラフィカルタブレット等の入力装置（図示せず）を介してユーザは、命令及び情報をコンピュータに入力することができる。コンピュータ３０は、１つ以上の遠隔コンピュータ（複数）と論理接続、及び／又は物理接続するネットワーク環境で動作することができる。上記の論理接続には、ローカル・エリア・ネットワーク（ＬＡＮ）及びワイド・エリア・ネットワーク（ＷＡＮ）が含まれる。
【００１８】
引き続いて図１を参照すると、図２には、透かしの埋め込まれた画像部分、及び透かしの埋め込まれていない画像部分に対する単位面積ごとの種の数を、グレーレベルの関数として示すグラフ４０が示される。Ｔ１及びＴ２は、画像と透かしのそれぞれのＦＭからＡＭへの遷移を判定する閾値を示す。但し、２本の曲線は互いに置換え可能である、即ち、透かしに、担体画像よりも高い（Ｔ２＞Ｔ１）種密度、又は担体画像よりも低い（Ｔ１＞Ｔ２）種密度を割り当てることができる。Ｔ１とＴ２との間の距離を調整することで、透かしの可視度を制御することができる。即ち、閾値の値の間の距離、即ち差を小さくすることで、透かしの可視度を下げられるように、Ｔ１とＴ２の閾値の値を調整して、透かしの可視度を制御することができ、またその逆も同じである。
【００１９】
図３Ａには、透かしが埋め込まれる透かし領域５２を有する入力コントーン画像５０が示される。図３Ｂには、ハーフトーン画像５０の透かし領域５２に埋め込まれる透かし画像６０が示される。図３Ｂの透かし画像６０は、異なる種密度間を選択するマスクのように用いられる。図面３Ｃ及び図３Ｄには、本明細書に記載のアルゴリズムにより、図３Ｂからの透かし画像６０を図３Ａからの画像に埋め込むことで、生成された透かし領域５２の２進バージョンが拡大表示される。文字「Ａ」は、２つの異なる種密度を有する透かしとして用いられ、アルゴリズムにより行われる可視度の制御の様子を示している。図３Ｃでは、透かしが簡単に見える程（例えば、Ｔ１＝６％、及びＴ２＝１５％）、透かしの密度と、画像密度との間の差が大きい。図３Ｄで用いられる閾値の差は、これより小さく、平均的な人間の知覚閾値（Ｔ１＝１２％  Ｔ２＝１５％）の近くまで縮み、その中の透かし画像６０は人間の目で見ることが難しくなっている。
【００２０】
図４には、図１の方法で符号化された２進画像を復号する方法が示される。この方法は、コンピュータ３０により実行することができる。用語「ドット」及び「ホール」は、８連結構成要素の集合であるＯＮ画素及びＯＦＦ画素をそれぞれ示す。この方法では、異なる主要密度を有する、異なる２つの第２世代の確率的スクリーン処理を用いて、画像の復号化を容易にする。ステップ８０で、受け取った透かしを埋め込んだハーフトーン画像に関する局所的なドット及びホールの総数を決定する。例えば、この局所的なドット及びホールの総数の決定は、受け取った画像内の画素のブロック即ち「ウィンドウ」（例えば、所定の最低ドット数（例えば、５ドット〜１０ドット等）を包含するのに十分な大きさを有する、画素の５０×５０ブロック、又はその他の好適な大きさの画素のブロック）を分析することで実現される。ウィンドウ、即ちブロックの大きさは１つ以上の因数の関数であり、それらの因数には印刷装置の解像度、分析するスクリーンの主要密度等が含まれるが、それらに限定されるわけではない。
【００２１】
ステップ８２で、ドット数がホール数より多いかどうかの判定が行われる。ドット数がホール数より多くない場合、ステップ８４で、形態学的拡張動作が必要かどうかに関する判定が行われる。必用でないと判定された場合、ステップ８６で、透かしに対応した総数かどうかが判定される。透かしに対応する総数の場合、次いで、復号された画像を出力する。
【００２２】
ステップ８２での判定により、ドット数がホール数より多いことが示された場合、ステップ８８で、形態学的浸食動作が必要かどうかに関する判定が行われる。必要でない場合、ステップ８６で、透かしに対応する総数かどうかに関する判定が行われる。透かしに対応する総数の場合、復号された画像を出力する。浸食処理が必要な場合、ステップ９０で、画像に対して浸食動作を行う。ステップ９２で、浸食される画像に関する局所的ドット総数を決定する。ステップ８６で、透かしに対応した総数かどうかが判定される。透かしに対応する総数の場合、次いで、復号された画像を出力する。
【００２３】
ステップ８４の判定で、形態学的拡張動作が必要であることが示された場合、ステップ９４で、拡張処理を行う。ステップ９６で、拡張された画像に関するホール総数が実行される。ステップ８６で、透かしに対応した総数かどうかが判定される。透かしに対応する総数の場合、次いで、復号された画像を出力する。
【００２４】
引き続いて図４を参照すると、図５には、第２世代のスクリーンに関するカバー領域（グレーレベル）の関数としてのドット数及びホール数（結合構成要素）を表すグラフが示されており、ＴはＦＭモードからＡＭモードへの遷移閾値を示す。カバー領域が０％から増加すると、ＦＭ領域内で種の数の増加に伴ってドット数が閾値まで着実に増加し、ＡＭモードが開始されるＴの位置からの平坦部１１２上においては、ドットどうしが接触を開始する位置まで一定であり、このドットどうしが接触を開始する位置から、スクリーン内の全ての画素がＯＮになるまで着実に減少する。カバー領域が０％から増加すると、白の結合領域が分離構成要素に区分し始めるのに十分な程、ドットどうしの接触が、拡散する位置までホールの数は一定であり、その位置から分離構成要素の数が増え始める。影、即ち大きなカバー領域を有する領域では、ＯＦＦの画素の数がゼロになるまで、着実に、ホールで埋まり始める。図５に示された形状は、特定なスクリーンに関するシグネチャであり、スクリーンに対して用いられる遷移閾値Ｔの選別に依存する。
【００２５】
図６には、異なる２つの遷移閾値を用いた２つの第２世代スクリーンに関するシグネチャを示すグラフ１２０が示され、第１のシグネチャは、実線で表され、第２のシグネチャは点線で表されている。グラフ１２０には、２つのスクリーンのシグネチャが示され、図４のステップ８６に関して記載したような、局所的なドット総数が透かしに対応しているかどうかの判定に、これらのスクリーンのシグネチャを用いることができる。例えば、図４の方法のステップ８０、ステップ９２、及び／又はステップ９６で行われた局所的なドットのカウントで検出されたドット数が、第１のシグネチャの平坦部１３２のドット数と同じ場合、ドット総数は受け取った画像の背景画像領域と一致していると判定される。しかし、局所的な総数が用語第２のスクリーンのシグネチャの平坦部１３４のドット数と同じと判定された場合、局所的な総数は、受け取った画像の透かしを埋め込んだ領域と一致していると判定される。
【００２６】
図６では、Ｔ１で第１のスクリーンのシグネチャがＦＭモードからＡＭモードに移り、Ｔ２で第２のスクリーンのシグネチャがＦＭモードからＡＭモードに移る。第２のスクリーンは第１のスクリーンよりも長い時間ＦＭモードを維持するため、より多い数の結合構成要素が実現され、第２のシグネチャの平坦部１２２の長さは、第１のシグネチャの平坦部１１２の長さより短くなる。より大きな遷移閾値が使用されると、可能な限り多くの結合構成要素が形成されるため、これにより、ドット及びホール総数は変化する。ハーフトーン及び影の部分のドット数とホール数とをそれぞれ用いて、両方のスクリーンの間を識別することができ、グレーレベルがＴ１より下の間、明るい影（小さいカバー領域又は低いグレーレベルを有する領域）、及び非常に暗い影（大きなカバー領域又は高いグレーレベルを有する領域）は復号目的で用いることはできないことが、図６の検証により判明している。形態学的浸食により、明るい影内のドット間の接触位置を止めることにより、及び形態学的拡張を介して、影をホールで埋めることにより、使用可能なグレースケールの範囲を広げることができる。浸食及び拡張を用いるかどうかの決定は、推定カバー領域の情報、又は局所的なドット及びホールの総数と、事前に規定された閾値との間の比較に基づいて行われる。
【００２７】
例えば、第１のスクリーンのシグネチャでは、グレーレベル５０からグレーレベル２００まで平坦部が延在することができる。第２のスクリーンのシグネチャでは、グレーレベル７０からグレーレベル１７０まで平坦部が延在することができる。第２のスクリーンのシグネチャのグレーレベルの平坦部は、第１のスクリーンのシグネチャのグレーレベル平坦部に包含された、グレーレベルのより短い間隔に沿って延在しているため、第２のスクリーンのシグネチャは、第１のスクリーンのシグネチャより高い密度を有していると判定される。即ち、ＦＭモードからＡＭモードへの第２のスクリーンの遷移は、より高いグレーレベルで行われるため、面積単位の結合構成要素のより高い密度が得られる。高い密度のスクリーンは、透かしシグネチャに対応し、低い密度のスクリーンは背景画像に対応する。
【００２８】
図７には、暗い影の領域及び明るい領域でそれぞれ、形態学的浸食動作及び形態学的拡張動作を行った後の、異なる遷移閾値を有する第２世代のスクリーンに関するシグネチャの曲線のグラフ１３０が示される。図示するように、Ｔ１で始まる平坦部１３２は、第１のスクリーンのシグネチャに関して延在する。同様に、Ｔ２で始まる平坦部１３４は、第２のシグネチャに関して延在する。
【００２９】
図８には、図４の方法等により、図３Ｄの画像内の目に見えない透かしを復号することで、生成された復号画像１４０が示される。白の画素により、透かしと識別されたデータが示されている。透かしのいくつかの部分は使用できないグレースケールの範囲に配置されるため、透かしの復号は完璧ではない可能性がある。
【００３０】
第２世代の確率的スクリーンを作るために、「種」又はクラスターの中心の位置を確率的に決定する。次いで、種の位置に基づいて、三角形の三角形分割を決定する。次いで、三角形分割の結果に基づいて、ハーフトーンのスポット関数を三角形ごとに計算する。次いで、完成した第２世代の確率的スクリーンに関する正規化した閾値配列を演算する。この透かしを埋め込むアプリケーションにおいて、一実施形態では、ＦＭからＡＭへの異なる閾値を有する２つのスポット関数を用いて２つの閾値配列を生成する。透かし位置と非透かし位置とを２つの閾値配列の間のスイッチとして用いた閾値が画像に適用される。別の実施形態では、透かし位置及び非透かし位置によって、種が生成され、これらの種に基づいて、スポット関数及び閾値が生成される。
【００３１】
本明細書に記載の第２世代の確率的スクリーンの生成の理解を容易にするために、図９〜図１１を参照して以下の説明を行う。図９には、「活性した」即ち「ｏｎ」として規定された入力位置、即ち種２１２の配列２１０の一例が示され、これらの種２１２は、例えば、ステップ１２（図１）で決定され、ステップ１４（図１）で設置、即ち配置され得る。種２１２は、スポット関数の増加に関する核を規定する位置である。これらの種は、第２世代の確率的スクリーンに関して用いられる規則的な格子上の位置、又は不規則的な位置でよい。これらの種は、画素格子の活性した（「ｏｎ」）画素として規定することができる、又は一般的な空間座標として表すことができる。一実施形態では、確率的スクリーンのハーフトーン処理を用いて、目標のグレーレベル、例えば、１５％のカバー領域、又はその他の所望されるグレーレベル、に達するまで、活性した画素として種が生成され、スポット関数により、それらの各種の周りで各ハーフトーンのドットが増加する。これらの種に関して用いられる確率的スクリーンの最適化として、従来行われているように、全てのグレー範囲に対して密度変調を用いるよりはむしろ、狭い範囲（例えば、０から１５％までのカバー領域、又はその他の所望される範囲）で密度変調（ＦＭ）を用いることができる。上記の方法を用いてハーフトーンのセルを生成するとき、種の分布が境界の周りで乱れがないように、これらのセルはハイパータイルとして処理される。
【００３２】
図１０には、本明細書に記載の１つ以上の態様に従って、ステップ１６（図１）で生成することができる、点の集合に関する三角形の三角形分割２２０の一例が示される。種２１２を考察すると、三角形の三角形分割は、種の位置に基づいて、規定される、又は生成される。３つの高さ等の三角形のパラメータを、各三角形２２２に関して決定する。ある実施例によれば、種の位置を含む画素領域を、三角形２２２に分割する。三角形の頂点は、ドットの種２１２である。全てのドットの種２１２を頂点として用いる。三角形分割を規定することで、三角形により空間が完全に埋められ、重なることはない。六角格子等の特定な周期的構造を種が形成する場合、三角形分割は、規則正しく、合同の三角形から形成され得る。不規則的な格子の場合、三角形分割は不規則で非合同三角形から形成される。
【００３３】
三角形の三角形分割の形成に関して複数の選択肢がある。例えば、ドロネー三角分割アルゴリズム又は技術を用いることができ、この分割法では、全ての三角形の外接円は、その他の三角形の頂点を含まない。ドロネー三角分割法では、頂点間の最小角度を最大限大きくし、これにより細い三角形が生成されることを避ける。ドロネー三角分割アルゴリズムは、上記の理由からハーフトーン処理のアプリケーションで用いることができる。ドロネー三角分割とは、ボロノイ分割の双対グラフであり、上記の方法は、元来２つのドロネー表示を用いて操作するのに適している。ドロネー三角分割法の最小角度は、それ以外の全ての頂点の三角分割と比較して、少なくとも、それ以外の最小角度と同じ大きさの角度となる。しかし、ドロネー三角分割法では、必ずしも最大角度を最小とはしない。
【００３４】
例えば、欲張り三角分割アルゴリズム又は技術が用いられ、これにより、各ステップにおいて、最も短い内側の対角線を三角分割法に加えることで、生成されるトータルの三角分割の辺の長さを最小限にする。別の態様によれば、ポリゴン三角分割アルゴリズム又は技術を用い、これにより、空間を効果的に三角分割可能な単調な多角形に分割する。さらに別の実施例では、径方向スイープアルゴリズム又は技術が用いられ、これにより、集合の中央の点をその他の点と放射状に接続する。次いで、これらの放射端を結ぶことにより三角形を形成する。
【００３５】
図１１には、本明細書に記載の種々の態様による、頂点Ｐ１、Ｐ２、Ｐ３を有し、画素Ｐを包含する三角形２２２が示される。この三角形は、高さＨ１、Ｈ２、Ｈ３、及び画素と交差する高さｈ１、ｈ’１、ｈ２及びｈ３を有する。所与の画素Ｐに関して、その画素Ｐの駐在する三角形を決定する。包含する三角形を決めた後、比較的簡単な幾何学的関係を用いて三角形の高さＨ１、Ｈ２、Ｈ３等の使用可能な三角形のパラメータを決定することができることは、当業者なら理解されよう。
【００３６】
包含する三角形を識別するとき、交点数技術又はアルゴリズムを用いることができ、これにより、画素を通過する放射線を辿り、その辺が放射線に辺ごとに１度の２度交差する画素Ｐの三角形を識別する。別の態様によると、巻き数技術又はアルゴリズムを用い、これにより、三角形が画素の周りを巻く回数をカウントする。巻き数が０の場合、その点は、三角形の外側になり、それ以外は三角形の内側になる。
【００３７】
画素が存在する画素格子と必ずしも一致しない空間座標を有する種の位置に関してではなくはむしろ、画素（例えば、「ｏｎ」「活性した」画素）上に存在する種の位置に関して、随意的に、包含する三角形を決定するステップを省くことができる。即ち、１つ以上の三角形の頂点上に存在する画素を包含する三角形を決定する必要はない。
【００３８】
画素ごとに、包含する三角形の頂点からの距離を判定する。三角形の高度を投影して判定する、又は同様に、各底辺への距離を判定する。三角形の高度とは、一頂点を通り、その頂点と反対の辺と垂直な直線であり、高度の全長は、所与の頂点に対する高さである。その反対側の辺を高度の底辺と呼ぶ。距離ｈ１、ｈ２、ｈ３は、画素Ｐからのそれぞれの頂点Ｐ１、Ｐ２、及びＰ３の反対側の各底辺までの距離である。互換性のある（例えば、制御成長と共に細分化しない）スポット関数を実行するために、上記の方法では、正規化された高さ（距離）：ｈ１／Ｈ１、ｈ２／Ｈ２及びｈ３／Ｈ３が用いられる。
【００３９】
判定された距離を用いて、スポット関数の値を決定して、ハーフトーンの閾値を生成する。即ち、図１のステップ１８に関して議論した通り、判定された距離をスポット関数に入力する。スポット関数は、パラメータを有し、そのパラメータを調整して、ハーフトーンの鮮明さ、及びその勾配を制御することができる。例えば、スポット関数は、それぞれが３つの距離の関数である、３つの余弦の加重和である。距離を代数的累乗することにより、隣接するドットとの各ドットの接触位置の鮮明さが制御される。隣接するドットどうしの接触が、異なるグレーレベルで起こるように、一連の接触は、余弦の重みにより制御され、これにより、同時に接触することで生じる不安定性を解消する。スポット関数それ自体を用いて、画像をハーフトーン処理することができる。又は、印刷装置内に効率的に実装するためにスポット関数のサンプルバージョンを閾値配列として適用することができる。全ての６つの距離の値が計算されると、画素ＰのＱ値は、下記の式で計算することができる。
【数１】
0005872994.tif 000002
ここで「ａｉ」は、「Ｈｉ」により規定された方向に沿ったドットの伸張を制御するパラメータである。余弦は、「π」の周りの対称関数であるため、距離「ｈｉ」が、三角形の辺に対して計算されたものか、又はその辺と平行の反対の頂点を通過する線に対して計算されたものかに関係なく、このＱの値は同じである。例えば、「ｈ１」の代わりに「ｈ’１＝Ｈ１−ｈ１」が使われても、Ｑの値は同じである。
【００４０】
ドットの辺の丸み、及びコーナーとの接触点の鮮明さに対する制御を所望する場合、一連の新しいパラメータγｉを取り入れることができる。
【数２】
0005872994.tif 000003
【００４１】
いくらかの「ｉ」に関し「γｉ≠０」のとき、「ｈｉ」に対するＱの対称性が失われるため、「ｈｉ」をどのように測定するかは、もはや任意ではないことに留意されたい。この場合の選択の範囲は、その点と、その点に最も近い線との間の距離に制限される、つまり、三角形の辺、又は、反対側の三角形の頂点を通過する架空の平行な複製線である。
【００４２】
下記の式のように、スポット関数を反転させることにより、別のレベルの制御が、可能となる。
【数３】
0005872994.tif 000004
反転させることにより、暗い画像の対象物に対して所望される「ホール」の十分な制御が可能となる。
【００４３】
その他の態様によると、データを正規化するステップが追加され、この正規化をスポット関数に伴って実行することができる。マトリックス内の全ての画素が処理された後、もたらされた入力値を変更・調整して、８ビットのシステムに関する［０，２５５］、又は１０ビット画像パスに関する［０，１０２３］等のデータ範囲に適合させる。
【００４４】
ドット内の複数の画素に対してスポット関数が同一の出力値又はほぼ同一の出力値を有する関連する態様によると、複数の画素の順番は、全て第２の基準の数により判定される。例えば、プロセスを通して、又はドットの辺の走査の最初、又はドットの辺の走査の終わりにレーザ撮像器が走査する方向に対して移動するとき、ドットの先端又はドットの後端等の辺に対して優先的に画素が加えた場合、マーキングプロセス又は撮像器は、より均一に画素をマークすることができる。例えば、画素を順に並べるとき、角度を考慮することができる。即ち、グレーレベルから、グレーレベルのドットの中心の移動を最小にするために、四分円（又は六分円等）のステップでドットの周りを回転することにより、ほぼ同一のドットの形状関数の値を有する画素を選択するときもある。別の実施例では、垂直方向、又は水平方向に優先的にドットを増加させ、ほぼ同一のスポット関数値を有する画素を並べて、好ましい方向をより増加させることで、印刷されたドットの均一性を実現するときもある。場合によっては、ほとんど同一のスポット関数値の画素を不規則に並べる、又は、複数の別の基準のうちのどれかにより選択するという要求を満たしてもよい。
【００４５】
図１２には、本明細書に記載の種々の方法の実行を簡単にするシステム３００が示される。このシステムは、本明細書に記載の種々の機能、方法、技術、ステップ等を行うための、コンピュータが実行可能な命令を実行するプロセッサ３０４と接続する印刷エンジン３０２と、それらの命令を記憶するメモリ３０６とを含む。これらのプロセッサ３０４及びメモリ３０６は、互いに組み合わせることも、又は分離させることもできるが、それらは互いに動作可能に接続する。別の実施形態では、プロセッサ１０４及びメモリ３０６は印刷装置３０２と一体型である。別の実施形態では、プロセッサ及びメモリは、印刷装置３０２に操作可能に接続するコンピュータ（例えば、図１のコンピュータ３０）内にある。
【００４６】
上述した通り、システム３００は、本明細書に記載の種々の機能、方法、手順等を行うための、１つ以上のコンピュータが実行可能なモジュール（例えば、プログラム、コンピュータが実行可能な命令等）を実行するプロセッサ３０４と、それらのモジュールを記憶するメモリ３０６を含む。さらに、当業者なら理解されようが、本明細書で使用される「モジュール」とは、一連のコンピュータが実行可能な命令、ソフトウェアコード、プログラム、ルーチン、又はその他のコンピュータが実行可能な上記の機能等を行うための手段のことを示す。さらに又はあるいは、１つ以上のモジュールに関する本明細書に記載の機能を手動で実行することもできる。
【００４７】
メモリは、ディスク、ハードドライブ等の制御プログラムを記憶するコンピュータ可読媒体でよい。不揮発性のコンピュータ可読媒体の一般的な形態には、プロセッサが読み込み、実行することができる、例えば、フロッピー（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープ又はその他の磁気記憶媒体、ＣＤ−ＲＯＭ、ＤＶＤ又はその他の光媒体、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、それら変化形、その他のメモリチップ又はカートリッジ、又はその他の有形的表現媒体が含まれる。このことに関連して、本明細書に記載のシステムは、１つ以上の汎用コンピュータ、専用コンピュータ、プログラム済みマイクロプロセッサ又はマイクロコントローラ、及び周辺集積回路素子、ＡＳＩＣ又はその他の集積回路、デジタルシグナルプロセッサ、個別素子回路等の配線電子回路又は配線理論回路、ＰＬＤ、ＰＬＡ、ＦＰＧＡ、グラフィックカードＣＰＵ（ＧＰＵ）、又はＰＡＬ等のプログラマブル理論装置を用いて、またそれ自体として実行可能である。
【００４８】
入力点即ち「種」３０８の集合は、確率的スクリーン３０９等の１次供給源から受け取られる。あるいは、入力点即ち「種」３０８の集合は、印刷装置３０２により走査された入力画像から、又はその他のいくつかの好適な供給源からプロセッサ３０４により生成された規則的な格子等内に配列した種位置を、不規則にばらばらにすることにより、生成される（即ち、種を入力画像から受け取る必要はない）。入力位置３０８及び確率的スクリーンをメモリ３０６は記憶される。プロセッサ３０４は、三角形の三角形分割モジュール３１０を実行して、種の位置に基づいて三角形の三角形分割を生成する。例えば、入力点即ち種３０８は、不規則に、即ち非均一的な格子状の模様に配列され得る。三角形分割モジュール３１０には、ドロネー三角分割モジュール３１２、欲張り三角分割モジュール３１４、ポリゴン三角分割モジュール３１６、径方向スイープ三角分割モジュール３１８、又はその他の好適な三角分割モジュールのうちの１つ以上のモジュールが含まれる。
【００４９】
例えば、ドロネー三角分割モジュール３１２用いることにより、全ての三角形の外接円は、その他の全ての位置の種に外接することなく、三角形を形成する３つの入力位置の種を通過するよう制限される。ドロネー三角分割法により、頂点の最小角度を最大限大きくし、これにより細長い三角形の生成が避けられる。別の実施例では、欲張り三角分割モジュール３１４が用いされ、これにより、各ステップにおいて最も短い内側の対角線を三角分割に加えることにより、生成される三角分割法のトータルの辺の長さを最小限にする。別の態様によれば、ポリゴン三角分割モジュール３１６が実行され、これにより、空間を効果的に三角分割可能な単調な多角形に分割する。さらに別の実施例では、径方向スイープモジュール３１８を用い、これにより、集合の中央点をその他の点と放射状に接続する。次いで、これらの放射端を結ぶことにより三角形を形成する。
【００５０】
プロセッサ３０４は、包含三角形識別モジュール３２０を含み、このモジュールは、画素が１個ずつ駐在する「包含する」三角形を識別する。例えば、交点数モジュール３２２を実行することができ、これにより、所与の画素を通過する放射線を辿り、その辺が放射線に辺ごとに１度の２度交差する画素Ｐの三角形を識別する。別の態様によると、巻き数モジュール３２４を実行し、これにより、三角形が画素の周りを巻く回数をカウントする。巻き数が０の場合、その点は、三角形の外側になり、それ以外は三角形の内側になる。
【００５１】
プロセッサ３０４は、距離判定モジュール３２６を実行し、これにより、その包含する三角形の底辺からの画素までの距離を判定又は計算する。即ち、各画素から各底辺、即ちその包含する三角形の辺までの距離を判定又は計算する。距離判定モジュール３２６は、各頂点からその反対の底辺即ち辺までの高さを含む三角形ごとの３つの高さも計算又は判定する。このように、３つの画素の高さｈ１、ｈ２、ｈ３と、３つの三角形の高さＨ１、Ｈ２、Ｈ３との６つの高さの値、又は距離の値を計算する。
【００５２】
画素ごとに６つの高さの値を判定した後、プロセッサは、画素ごとに高さ値をスポット関数（例えば、上記の図面に関する式（１）、（２）、及び／又は（３）を参照）に入力して、出力値を決定し、この出力値を用いてハーフトーンの閾値を生成する。一実施例では、画素ごとに高さの値が判明すると、すぐにスポット関数が実行される。別の実施例では、全ての画素の高さの値が判定された後、全ての画素に対して一度にスポット関数が実行される。次いで、プロセッサ３０４は、ハーフトーンモジュール３３０を実行し、随意的に１つ以上の第２の基準を使って、即ち考慮して、画素ごとのスポット関数の出力値を用いて、画像のハーフトーン処理を行う。メモリ３０６に記憶される画像データ３３２には、入力位置の種の格子を生成する入力画像データ、上記のプロセス中に様々な位置において生成される中間画像データ、ハーフトーン画像データ等の出力画像データ等が含まれ得る。出力画像データが印刷モジュール３３４に供給され、プロセッサ３０４が、このモジュール３３４を実行すると、一連の命令即ち指令が生成され、この命令をプロセッサ３０４及び／又は印刷装置３０２が実行して、ハーフトーン画像を印刷する。別の実施形態では、出力ハーフトーン画像は、グラフィカル・ユーザ・インターフェース３３６に画像で表示される。このグラフィカル・ユーザ・インターフェースには、印刷装置３０２と一体型のもの、分離しているが操作可能に接続するもの、又は図１のコンピュータ３０等のコンピュータに駐在するものが含まれ得る。このように、システム３００を用いて、画像を直接ハーフトーン処理することができる。即ち、システム３００を用いて、種の集合に関するスポット関数のサンプルバージョンを生成して、デジタルハーフトーンセルを作り出し、これを用いて画像のハーフトーン処理を行うことができる。
【００５３】
さらに、図１に関して記載した方法を行うためのデータ及びコンピュータが実行可能な命令をメモリが記憶する。そのデータには、コントーン入力画像データ３３８（図３Ａを参照）、及び透かしデータ３３９（図３Ｂを参照）が含まれるが、これらには限定しない。種密度分析モジュール３４０が、コントーン入力画像に関する種密度を判定する。この種密度は、透かしを埋め込むハーフトーン画像を生成するときに、種を配置する際に用いられる。透かしの有無及び画像内の所与の位置での入力画像のグレーレベルに基づいて、種の位置（種密度）を判定する。三角形分割モジュール３１０が、種を三角分割して、これらの種を頂点として有する複数の三角形を形成する。種の位置により決定された三角形分割に基づいて、ハーフトーン処理のスポット関数３２８が計算される。閾値モジュール３４２を、透かしを埋め込むハーフトーンの出力画像に対して実行する。即ち、スポット関数の閾値を画像に適用して、透かしを埋め込んだハーフトーンを作成する。原画像データ及び透かしデータを含む、透かしを埋め込んだ出力ハーフトーン画像３４４もメモリに記憶されて、印刷、又はユーザに表示される。閾値モジュール３４２により、変動されるＦＭからＡＭへの閾値を量で、透かしの可視度が決定する。つまり、閾値の差が大きいほど、より人間の目には見やすくなる。
【００５４】
透かしを埋め込んだ画像を復号する、図４に関して記載した方法を実行する復号モジュール３４６もメモリに記憶される。例えば、この復号モジュールは、様々なドット及びホールの総数（即ち、最初の総数、浸食後の総数、拡張後の総数等）をカウントし画像内に透かしが存在するかどうかを識別するために、浸食動作、又は拡張動作を画像に対して行うべきかどうかを判定する。このためには、メモリは復号モジュール３４６により起動されると、プロセッサ３０４により実行される浸食モジュール３４８及び拡張モジュール３５０を記憶する。このように、復号モジュールは、画像内に透かしが存在するかどうかを識別し、復号された画像を出力する。
【図１】
0005872994.tif 000008
【図２】
0005872994.tif 000009
【図３Ｂ】
0005872994.tif 000010
【図４】
0005872994.tif 000011
【図５】
0005872994.tif 000012
【図６】
0005872994.tif 000013
【図７】
0005872994.tif 000014
【図９】
0005872994.tif 000015
【図１０】
0005872994.tif 000016
【図１１】
0005872994.tif 000017
【図１２】
0005872994.tif 000018
【図３Ａ】
0005872994.tif 000019
【図３Ｃ】
0005872994.tif 000020
【図３Ｄ】
0005872994.tif 000021
【図８】
0005872994.tif 000022