(57)【特許請求の範囲】
【請求項１】
ハーフトーン画像にマシンが読むことのできるデジタル情報を埋め込む方法であって、
トーンに写像するデータサンプルに従って、感知された前記トーンを個別のハーフトーンセルに与えるための、形状のそれぞれが、個々のセルの対角線のデータ軸について対称である、双曲線形状を生成するステップと、
デジタルデータ値をハーフトーン画像に埋め込むために、前記デジタルデータ値に従って、少なくとも幾つかの前記セルの前記双曲線形状のうちの少なくとも一つを強度変調するステップと、
を有する、ハーフトーン画像にマシンが読むことのできるデジタル情報を埋め込む方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ハーフトーン（中間調）画像へのマシンが読むことのできるデジタルデータの埋め込みに関し、特に、拡張されたトーンレンジ（階調範囲）に渡るそのような埋め込みデータを収容するための、解析的に画定されたハーフトーンパターンに関する。
【０００２】
【従来の技術】
種々の内容の画像にマシンが読むことのできるデジタルデータを埋め込むために、セルフクロッキンググリフコードが開発されてきた。このグリフコードをラインアート(lineart) 画像に統合するために、データは典型的には、小さな、同じようなサイズの、空間的に並べられた（spatially formatted)、楕円型またはスラッシュ状のマーク、即ち”グリフ”に埋め込まれ、グリフは、一般的に直交した配置において、左または右に傾斜され、それぞれが二進法の”０”または”１”をコード化する。通例、これらのグリフは、中心の空間的に周期的な２次元格子に、１平方インチ当たり約５００バイトまでのデータを記憶できる密度で、例えば普通紙文書上に書き出される。従って、明らかに、このグリフコードは、文字及び他のタイプのラインアート画像にデジタルデータチャネルを組み込むのに、よく適している。実際、前述のタイプのグリフコードの長所の一つは、それらが概ね均一なテクスチュアの外観を有しており、時には実質的に均質なグレースケールの外観を有するように見えることすらあるので、美的な妨げになるようには目立たない傾向があることである。
【０００３】
タウ(Tow) は、「ハーフトーン画像にマシンが読むことのできるデジタルデータを埋め込む方法及び手段（"Methods and Means for Embedding Machine Readable Digital Data in Halftone Images") 」として1994年 5月24日に発行され、本出願と同一の出願人に譲渡された米国特許第５，３１５，１１２号に、ハーフトーン画像にセルフクロッキンググリフコードを組み込むための”丸い非対称な”ハーフトーンドットの使用を記載している。これは、公知のまたは特定できる空間的な配列規則に従って、データが画像のミッドトーン（中濃度）領域に制限される場合に、有効な方法である。しかし残念なことに、画像の、より暗い、またはより明るい領域から、埋め込まれたデータを、許容できる信頼性をもって再生するには、過大な感受性が要求される。もう一つの短所は、この非対称なハーフトーンドットで構成されたハーフトーン画像中の背景ノイズが、これらの画像の感知される質を落とすかもしれないことである。例えば、４つの非対称なドットは、中心点から外に放射状に延びるパターンを形成するかもしれず、或いは、正方形の辺を形成することもあり得る。この回転に依存する相違は、画像中ですぐに目につくものであり、眺めた際に、望ましくないざらつき感及びノイズを生じる。
【０００４】
本発明の出願人と同一の出願人に譲渡され、「サーペンタインハーフトーン画像を生成する方法及び装置（"Method and Apparatus for Generating Serpentine Halftone Images"）」として1998年 1月 6日に発行された、米国特許第５，７０６，０９９号は、画像にデータを埋め込むために、丸いサーペンタイン(circular serpentine) のハーフトーンセル構造を導入することによって、上述の問題の部分的解決法を提供している。図１に示されるように、このサーペンタインハーフトーンセルは、回転しても、トーンが変わらない度合いが高い。実際には、このハーフトーンセルの円弧は、セルのトーンが変わるにつれて、太さが変化する。しかし、トーンに関係なく、各ハーフトーンセルの各円弧の中心軸は、隣接するセルの辺と、各辺の中点で交わる。このように、たとえ埋め込まれたデータの値が、セルのデータ軸（つまり対称軸）が、低速走査方向に対して＋45度または−45度の向きをなすようにしていても、これらの円弧の軸は、実質的に、隣接するどのハーフトーンセルの円弧の軸とも一致する。（図１参照。）セル境界のハーフトーンセルの形状が、セルの回転に関わらず類似しているので、回転に関連するノイズは大いに削減される。正方形の向かい合う角に四半円を有する、このタイプの構造は、トルーチェット(Truchet) タイルとしても知られている。
【０００５】
上記に参照した本発明の発明者の特許は、弧状のフィルパターン（fill pattern) が、回転により区別がつくハーフトーン構造の別の対を生成するために、ハーフトーンセル境界に関して45度回転されてもよいことを、教示している。この構造はマンハッタン (Manhattans) と呼ばれており、また、時として、直立サーペンタイン(ortho-serpentine)としても言及される。しかしながら、このマンハッタンまたは直立サーペンタイン構造は、回転によって、サーペンタインセル構造よりも大きくトーンが変化する。このようなわけで、マンハッタンまたは直立サーペンタイン構造は、各ハーフトーンセルに１対のデータビットを埋め込むのに必要となる、回転により区別がつく付加的なセル構造を提供するというような、特別の目的に主に向けられる。
【０００６】
残念ながら、本発明の発明者の上記特許に記載のハーフトーンセル構造の円弧の対は、そのようなセル構造で構成されたハーフトーン画像から、埋め込まれたマシンが読むことのできるデータが、効果的に再生される、ダイナミックトーンレンジに、望ましくない制約を課している。図２を参照すると、より暗いトーンを生成するために、円弧の線幅、即ち太さが増すにつれて、円弧は１５におけるように重なった状態に達し、トーンが暗くなるほど重なりの程度が増す。この重なりが生じてしまうと、埋め込まれた”０”を埋め込まれた”１”から区別するのは、セルの四隅の形状情報だけになり、特に重なりの量が増加するにつれて、形状情報が誤変換されるリスクを伴う。従って、回転しても実質的にトーンが変わらないだけでなく、拡張されたトーンレンジ全体に渡って容易に確認できる配置方向の目印をも提供する、ハーフトーンセルを構成する技術を有することは、明らかに有益である。
【０００７】
【発明が解決しようとする課題】
上述の目標を実現するために、本発明は、双曲線型のサーペンタイン及び直立サーペンタインハーフトーンセルを構成し、そのようなセルで構成されたハーフトーン画像にマシンが読むことのできるデジタル情報を埋め込む、方法及び手段を提供する。
【０００８】
【課題を解決するための手段】
本発明に従ったハーフトーンパターンを生成するために推奨される方法は、従来のハーフトーン生成方法と幾分異なる。本発明の目標は、ハーフトーンフィルパターンのエッジ、即ち”形状”の、ハイライトからシャドウへと大きくなるにつれての発展の仕方を、より正確に制御することである。
【０００９】
特に、従来のデジタルハーフトーン処理では、閾値アレイの適切な数のビットをオンにして、所望のトーンを生成する。アレイは、閾値が上昇するにつれて、中央ロケーションから外に向けてスパイラルを描く、閾値のシーケンスを保持する。ハーフトーンセル内のこれらのロケーションに対応するビットは、入ってくるデータ強度がそのビットロケーションの閾値に等しいか、または閾値より大きいと、”オンになる”。この方法は、閾値が次々と、強度値のレンジの例えば０から２５５までを、行ったり来たりするにつれて、非対称的に大きくなるハーフトーンドットを生成する。
【００１０】
しかし、サーペンタインパターンについては、より良い形状制御を維持するために、ハーフトーンフィルパターンを、パターンの周辺上の全ての位置で同時に大きくすることが望まれる。従って、ハーフトーンフィルパターンを生成するには、典型的に２ステップのプロセスが用いられる。第１に、ハイライト領域に当たる最も小さい形状から、ミッドトーンを経て、最後にハーフトーンセル全体を覆うまで、所定の発展に従って大きくなる、解析的形状関数が定義される。このステップでは、形状情報は、解析関数により”無限の精度”をもって維持される。第２に、形状の領域がより大きくなるにつれて、フィルパターン、即ち形状は、対応する形状を有するテキストまたはラインアートのセグメントであるかのように、描画される。ハーフトーンの形状及びトーンの発展が解析関数で定められるので、その結果、形状及びトーンをよりよく制御できる。それにも関わらず、サーペンタインを生成するためには、十分に大きな閾値アレイを前提とすれば、従来の閾値アレイを用いることができるであろうと信じられる。
【００１１】
形状関数を解析的に定義するにあたって、２つの主な目標がある。第１の目標は、強度値０の最も小さい形状から、例えば強度値２５５の最も大きい形状へと大きくなるまで、連続した形式で発展可能な関数を定義することである。関数の非連続性によって生じるトーンのとびは、どのようなものでも、ハーフトーン画像内ですぐに目につくであろう。第２の目標は、前記関数が、ハーフトーンセル内の任意の点から最も近い形状エッジの位置及び角度に対して、関数の発展の全段階で解析的な精度をもって、確実に解かれ得るようにすることである。上記目標の達成によって、形状が正確に描画される。
【００１２】
【発明の実施の形態】
図３は、ハーフトーンセルと基本双曲線型形状関数との関係を示している。この関係は、次の式のような、原点を中心としてＹ軸上に焦点を有する双曲線から始めて、展開される。
【００１３】
【数１】
0004010687.tif 000002
【００１４】
４つの線、ｘ＝ａ、ｘ＝−ａ、ｙ＝ｂ、ｙ＝−ｂの交点は、対角線が双曲線の漸近線を形成する矩形を画定する。次に、双曲線の焦点ｆのＹ軸に沿った位置をｃとした場合は、次式を満たす、辺ａ、ｂ、ｃからなる直角三角形ができる。
【００１５】
【数２】
0004010687.tif 000003
【００１６】
ハーフトーンセルの辺Ｓの長さは、ハーフトーンセルの画素サイズによって決定される。曲線群を作るのに用いられる戦略は、焦点を適当な値に固定し、それからハーフトーンセルの辺に沿ったｘ，ｙの値（図３でｐｘ，ｐｙと示される）を１つずつ、曲線群の各要素に対して選択することである。ｘ、ｙ及びｃが分かれば、方程式（１）及び（２）は２つの未知数ａ及びｂの連立方程式になる。従って、連立方程式を解いてａ及びｂの解を求めることができ、曲線群の各要素ごとに方程式（１）の１つの実例ができる。
【００１７】
認識されるように、もし焦点が原点に接近して配置されれば、生成される双曲線群は、原点付近で急激に方向を変え、他では概ね真っ直ぐであろう。一方、もし焦点がハーフトーンセルの一番上の頂点に接近するように選択されれば、曲線は、問題の領域全体で概ね真っ直ぐなままであろう。これら２つの極端な例の中間をとって、原点とセルの頂点との間の距離の２／３の値が焦点として選択されるのが適切である。従って、以下のｃを求める方程式でｋ＝２／３としておく。
【００１８】
【数３】
0004010687.tif 000004
【００１９】
すると、パラメータｂ及びａは、方程式（１）及び（２）を連立して解いた、以下の関係によって求められる。
【００２０】
【数４】
0004010687.tif 000005
【００２１】
図４は、焦点パラメータｋが２／３と設定されているときに、ハーフトーンセルの辺上の異なるｘ＝ｐｘ，ｙ＝ｐｙの値から生成された曲線の、幾つかの代表的な例を示している。
【００２２】
サーペンタインハーフトーンパターンのトーンを、回転しても実質的に変わらないようにしている性質の１つは、セルを９０度回転しても、隣合うハーフトーンセル間との境界で、ほとんど変化がないことである。これは、フィルパターン即ち形状を定める１対の曲線のそれぞれの交点を、ハーフトーンセルの辺Ｓの中点から等距離にあるように選択することによって、達成される。２つの双曲線が、サーペンタイン形状を画定するために用いられ、それらの曲線がハーフトーンセルの周辺と交わる点ｐｘ，ｐｙが選択されて、これらの交点はセルの辺Ｓの中点から反対方向に等しく置き換えられる。図５は、この場合の、１対の曲線ｃ１及びｃ２、並びに、対応する鏡像の１対の曲線ｃ３及びｃ４の一例を示している。これら２対の曲線及びハーフトーンセルの辺は、典型的に、サーペンタイン形状関数に対応するフィルイン（fill-in ）領域を定める。
【００２３】
前に指摘したように、本発明のハーフトーン形状は、形状がテキストまたはラインアートの一部であるかのように、描画されることが、有利である。ハーフトーン形状が定められる解析的精度を有効活用するために、形状のエッジの描画は、典型的に、レーザプリンタ（図示せず）のレーザを、走査スポットのサイズより細かい精度で変調することによって、実施される。例えば、走査スポットがスポット自体の直径をスウィープ（掃引）し終えるのに要する時間内に、レーザを変調するための８ビットまでのデジタル情報を供給できる。この目的のために、図６に示されるように、ハーフトーン処理装置は典型的に、複数の強度”プレーン（plane)”で構成される、階層分類的に組織されたテーブルルックアップメモリ２１を有する。各強度プレーンは、個々にアドレス可能なメモリセルの、例えば３２×３２アレイのような、２次元アレイで構成される。例えば、ルックアップメモリ２１は、受け取られる個々のデータ値によって選択的にアドレスされるように索引付けされた、２５６個の個別にアドレスできるデータプレーンを、有してもよい。一方、Ａ及びＢアキュムレータ、２２及び２３は、各強度プレーンに備えたメモリアレイのＡ（水平方向）及びＢ（垂直方向）の次元をモジュロとする（つまりモジュロ３２）数値を蓄積し、Ａ及びＢアキュムレータに蓄積された値が増分される比率によって決定されるスクリーン角度で、一連のハーフトーンセルを横断してスウィープする、走査ビームの位置を追跡する。
【００２４】
このテーブル検索技術は、各アクセスに応答して１バイトまでの出力データを生成する能力がある。Ａ及びＢアキュムレータ、２２及び２３は、米国特許第５，４１０，４１４号ではＸ及びＹアキュムレータとしてそれぞれ示されている。しかし、Ｘ及びＹは、本開示の目的のためには、プリントプロセスの高速走査及び低速走査の方向を示すためにとってあるので、アキュムレータ２２及び２３にはＡ及びＢという表示が、明確さを増すために適用されている。いずれにせよ、描画中のハーフトーンセル内のスポットの現在位置からの、特定の強度プレーンに対応するハーフトーンフィルパターンのエッジの距離及び角度を、有効活用するために、ルックアップメモリ２１の各強度プレーンの各メモリセルにロードされる値は、注意深く選択される。これが、トーン即ち濃度情報だけが分かっている従来のハーフトーン処理方法との、決定的な違いである。
【００２５】
特に、サーペンタイン形状関数のための２対の曲線の両方を一旦見つけてしまえば、課題は、任意の可能なスポット位置から、最も近い形状のエッジを見つけることである。これらの潜在的なスポット位置は、ハーフトーンセル内の各メモリロケーションに対応するので、各メモリロケーションは特定の空間位置に対応する。従って、ハーフトーンセル内の各メモリロケーションは、ｘ−ｙグリッド上のメモリロケーションの中心に対応するｘ0 ，ｙ0 と示すことができる。次いで、ｘ，ｙでの曲線の導関数の負の逆数を、ｘ0 ，ｙ0 及びｘ，ｙの間に引かれた線の傾きと等しくなるように設定することによって、曲線上の最も近い点が求められる。方程式（１）から求めたｙの解を代入することにより、ｙへの参照を全て消去でき、それによって唯一の未知数がｘである方程式を与える。
【００２６】
【数５】
0004010687.tif 000006
【００２７】
開方に適したルーチンを用いて、ｘの値を求めた。次いで、方程式（１）から、ｙの値を求めた。スポット位置ｘ0 ，ｙ0 とセルロケーションｘ，ｙとの間の距離及び角度が求められ、適切な変調値が、そのメモリセルに記憶される。このプロセスは、ｘ0 ，ｙ0 プレーンの中の全てのメモリロケーションに対して繰り返され、次にルックアップテーブル２１の全ての強度プレーンに対して再び繰り返される。これらの値は、ルックアップテーブル２１の各メモリロケーションに対して１回だけ計算されるため、平方根を求めるのに要する時間は重要ではない。テーブル検索は計算を必要とせず、プリント中にプリント速度を落とすことなく、実行できる。
【００２８】
理解されるであろうが、ルックアップテーブル２１は、プリントプロセスで要求される各強度に対応したトーンを供給する。例えば、テーブル２１は、２５６通りの異なるトーンを、可能なデータ入力強度値毎に１つ、供給してもよい。従って、前に指摘したように、ルックアップテーブル用のメモリは、ハーフトーンセル内のｘ，ｙスクリーン位置を定義する従来の２つの軸と、データの制御下で、異なる”強度プレーン”に索引をつけるための第３の軸という、３つの軸を有する。通常の８ビットデータ値用のテストプリントは、２５６通りの異なるｐｘ，ｐｙの値の直線の傾斜を用いて実施され、辺の中点から始まり（明るいトーン）、セルの頂点で終わる（暗いトーン）。このプリントは濃度計で測定でき、プリンタがプリントする実際のトーンが分かる。逆の作業をすることによって、２５６通りのｐｘ，ｐｙ値の直線の傾斜を、各入力強度値に対する正確なトーン出力をより良く表す曲線に、調整することができる。この曲線はトーン（階調）再現曲線と呼ばれており、”無限の精度”をもって形状関数が定義されるので、曲線の精度も高くすることができる。
【００２９】
コントラストは、高画質画像の重要な特性である。トーンがほとんど無い、若しくは全く無い領域、または、完全に飽和した（saturated ）暗いトーンの領域は、ハイライトからシャドウまでのトーンの連続体の中の、極端な部分を表す。人間である観察者が、明るい又は暗い領域を見る能力は、これらの濃度をもたらすプリントプロセスの能力を超えている。しかしながら、この能力の差は、プリントプロセスが、見る人を非常に満足させる画像を作ることを妨げるものではない。さらに、ルーペを用いて、肖像や風景といった多くの高画質画像を調べてみると、肉眼には、本当に白または黒に見える多くの領域が、完全には飽和してはいないことが分かるであろう。これは、明るい領域は小さなハーフトーン構造を有し、より暗い領域に囲まれているから、明るく見えるだけだからである。同様に、一見黒く見える領域も、ハーフトーンドット間に白い隙間を有することがあり、より明るい領域が近接しているから、黒く見えるのである。図７は、典型的な双曲線状サーペンタインハーフトーンフィルパターンが大きくなる様子を図示する。
【００３０】
明らかに、ハーフトーンドットが全く存在しない領域、またはドットが画像平面を完全に覆うほど、十分に飽和した領域には、データを埋め込めない。プリントプロセスにとってだけではなく人間の観察者にとっても、コントラストは相対的なものなので、特に、データが冗長に（redundantly ）記録されている、及び／またはデータ上で算出されたエラー修正コードによって保護されている場合には、殆どの画像のコントラストを適切に調整でき、そのような画像に埋め込まれたデータを信頼できるように再生できる。
【００３１】
図６の態様に示されているハーフトーン生成装置２１によって生成できる２５６通りの異なるハーフトーンセルは、サーペンタインが描画される方向とは無関係である。もし望むなら、ハーフトーン画像に埋め込まれるべきデータビットのシリアルストリームを、別個のチャネルを介して、例えば９番目のビットとして、少なくとも幾つかのデータサンプル用に、システムに入力可能である。しかしながら、カラーレーザプリンタ（図示せず）によって実行されるゼログラフィー（静電写真）プロセスは、各カラー層（イエロー、マゼンタ、シアン、及びブラック）ごとに、１２８通りだけの異なる（等しく間隔を置いた）トーンを再現するに限られることもある。その場合は、各データサンプルの最も重要でないビットを埋め込みデータ用にとっておくことで、８ビットデータチャネルを使用できる。そのような実施のために、サーペンタイン形状が、例えば、偶数番号のプレーンは左に傾斜した形状を収容し、奇数番号のプレーンは右に傾斜した形状を収容して、互い違いの方向で、ルックアップテーブル２１の各強度プレーンに描画されるのが、適切である。
【００３２】
１インチ当たり４００の走査線をプリントするプリンタでのプロトタイピングは、１インチ当たり１００個のサーペンタインハーフトーンドットをプリントする。各ハーフトーンドットは１ビットの埋め込み情報を有するため、１平方インチ当たり、ざっと10,000ビットつまり1250バイトの埋め込みデータがある。上述の米国特許第５，４５３，６０５号に記載の、標準グリフ”埋め込みデータブロック（embedded data block)”（ＥＤＢ）は、同期コード、及びデータ回復に備える冗長性を付与するために用いられた。上記は典型的に、１インチ当たり 500バイトの全体のデータ密度に対して、2.5 の係数で、データ密度を減らす。
【００３３】
各カラープレーンに同一の埋め込みデータが送られるので、フルカラー画像を再現する際、サーペンタイン形状は正確に重なる。もし、これがなされないとしたら、カラー制御は遙かに困難になろう。そうなると、カラー分解の重複は、イエロー、マゼンタ、シアン、またはブラックの層に埋め込まれたデータの差異の関数として変化するであろうから、色は画像データと同じく埋め込みデータにも依存することになろう。
【００３４】
サーペンタイン形状は、上書きする画像とは独立の、多くの異なる面白いパターンになるようにタイル貼り（tile) できる。データを非ランダムなパターンに密集させることによって、ある種の有用な形状が形成される。例えば、０と１をチェッカーボード上のように交互に配置すると、図８のように、丸い”ドーナツ”パターンのアレイが形成される。このタイプのパターンは、特に、このドーナツのようなパターンが、埋め込みデータ領域を囲む”フレーム”としてアレイになっている場所の、データ再生中のデータ同期に有用かもしれない。確かに、このマクロ形状で作られたフレームの方が、一定の、または擬似乱数的に変化する”０”及び”１”で作られたフレームより、認識しやすいかもしれない。
【００３５】
図９は、切れ目のない”１”の連なりを表す画像の一例を示している。この”波のような”パターンは、ラインスクリーン、即ち、画像全体が一連の縦線で描画され、トーンを添えるために線幅だけが変調される、ハーフトーンの１タイプに類似している。このサーペンタインの波のような性質は、そうでなければ概ね直線であろうものに、二次元的な性状を与える。このサーペンタインパターンは、相当する直線パターンよりも長い周辺を有しており、そのことは、このサーペンタインパターンが、所定のハーフトーン周波数において効果的に作られる差異のあるトーンレベルの数を増やすための、基礎であることを意味する。
【００３６】
埋め込みデータを密集させる別の方法は、文字の意味を有し、従って、装置による読み込みやコンピュータによるデコードを必要とせずに、人が読むことのできる可能性を有するパターンを形成することである。例えば、図１０のタイルパターンには、"read"という単語が埋め込まれている。この場合は、数十ビットの密集データが配置されて、標準８ビットASCII 文字コードに代表される文字に相当すると考えられてよい、英数字の文字を形成している。データを読み込んでデコードするコンピュータは不要なので、同期コードは不要である。そのような、人が読むことのできるパターンは、典型的に、パターンを含む画像中に、冗長にコード化されている。そのようなパターンによって表されるテキストのサイズ及びデザインに従って、冗長性の係数（redundancy factor ）は３から５の間であるのが、大体の基準となろう。
【００３７】
これまでに、人が読むことのできる様々なサイズ及び形状のパターンが構成されており、ルーペまたは拡大鏡を介した視野は限られがちであることから、通常は、小さいパターンの方が読みやすいことが分かっている。初めて画像を与えられた被験者は、できるだけ大きな範囲を見ることが有益である。被験者に、個々の文字が見えたら、一文字ずつ書き出すように頼むことも、役に立つ。被験者が画像とルーペを与えられ、単に、背景のハーフトーンに隠されたメッセージを見つけだすように頼まれると、通常、被験者が遭遇する問題は、どのようなスケールで、埋め込まれた言葉を探せばよいのか分からないということである。しかしながら、強調表示されているサンプルメッセージを有する拡大画像の形態でヒントを与えられた場合は、学習時間は大いに削減される。観察者が探すべきものを学習してしまえば、データを読む課題は容易になる。
【００３８】
このタイプの埋め込みデータを、多くの他のタイプから区別する特徴の１つは、メッセージのデコードに、低い技術だけを要することである。即ち、必要なのは拡大鏡だけであり、これは世界中でたやすく入手できる。従って、認証には、入力スキャナ、コンピュータ、入手困難なプラスチックのオーバーレイ、または他の、手元に無い、または容易に入手できないかもしれない装置は、不要である。
【００３９】
上述の議論は、ハーフトーン形状の９０度の回転で生じる違いを識別することを意図している。識別技術の限界のみを条件として、データを埋め込むために、より小さい回転変位を用いて、同時にデータチャネル容量を増加してもよい。例えば、左または右４５度に傾斜したハーフトーンの代わりに、画像に対して直交する関係を持つハーフトーン構造を作成して用いる方法を開発するのに、幾つかの努力が捧げられてきた。この直交するハーフトーンは、傾斜したハーフトーンと組み合わされると、データをハーフトーン画像に埋め込むための、４つの識別可能なハーフトーン構造を伴うシステムとなった。再び図５を参照すると、この追加のサーペンタインを構成するために、セル頂点が一番上になるようにセルが配向され、２対の曲線ｃ１とｃ２、並びに、ｃ３とｃ４が境界をなすサーペンタイン形状がフィルインされる。
【００４０】
単純にセルを４５度回転し、曲線間のフィルイン領域の補色をとること（complementing ）によって、新しいタイプの”直立サーペンタイン”形状を構成できる。これは図１１に示されている。このときのフィルイン領域は、ｃ１とセル頂部との間、ｃ４とセル底部との間、またはｃ２、ｃ３、及びセルの辺との間である。セル辺上のフィルイン領域の境界が等しくなるように、曲線の位置が依然として揃えられていることに注目されたい。これは、９０度の回転を介しても、セル境界でトーンが影響されないままであることを保証する。
【００４１】
これらのセルは、データを２方向に埋め込むために用いられた場合は、斜めに配向されたサーペンタインとして用いることができ、或いは４方向コード化（quadrature encoding ）を達成するために斜めのサーペンタインと組み合わせることができる。配置方向の垂直または水平の性質により、より多くの様々なパターンが構成できる。
【００４２】
残念ながら、この直立サーペンタイン形式のハーフトーンセル形状のパターン中での挙動は、斜めのサーペンタインほど好ましくない。問題は、この形状が各セルごとに２つの”行き止まり”を与えることである。すると、ハーフトーンの連続性が失われ、ハーフトーンの外観に”ノイズが多く”なる。しかしながら、より高いハーフトーン周波数を用いることによって、ノイズが減る可能性もあり、また、あまりノイズの影響を受けない画像内で、この構造の使い途があるかもしれない。
【００４３】
注目されるべきフィルイン領域及び形状の配置方向には、他に２つの置き換えもある。それらは、図１２に示されるように、上述したハーフトーンフィルパターンのフィルイン領域の補色をとることによって得られ、ハーフトーンセルの辺からではなく、角から発する形状を作り出す。図５の基本のサーペンタインパターンから導出された補足形状（complementary shape ）は、１対の”行き止まり”を有する形状のもう一つの例であるので、図１１の直立サーペンタイン形状から得られた補足形状は、より低いノイズ特性を有する傾向にある。
【００４４】
サーペンタイン埋め込みデータの興味深い拡張を、例えば、透かしに適用してもよい。透かしとは、文書中の、大変複写が困難な可視の二次的な埋め込み画像か、または画像中の、複写されないことが大変困難な不可視のデータ記号のことである。このサーペンタインの応用は、これらの透かし戦略の、第１のタイプに焦点をあてる。
【００４５】
図１３に示されるように、サーペンタインハーフトーン構造は、ハーフトーンセルの対角線のデータ軸に関して対称な２つの鏡像形状で、効果的に構成されている。ハーフトーンセルの対称な各半分は、各々のトーンまたはシェードが、画像の局所的なトーンから、ある所定の量だけ、独立してオフセット（offset）されるという、興味深い特性を有する。従って、サーペンタイン形状の、許容できる角度方向のそれぞれで、このオフセットの２つの置換が作成されてもよく、すると、２つの許容できる角度方向を有する形状は、この半分のセルの強度変調の区別できる置換を４つまで提供することができる。例えば、図１３で”２”と表示されているセルは、上右半分に０の強度オフセットを用いて構成されているので、セルのこの部分のトーンは画像データを忠実に表す。しかし、同じセルの下左半分のトーンは、画像値が最高強度の半分より低い場合は、画像に依存する強度レベルからプラスのオフセットで、画像値が最高強度の半分より高い場合は、画像に依存するレベルからマイナスのオフセットで、強度変調される。同様に、”４”と表示されているセルは、上右半分にそのような強度オフセットが適用されており、”６”と表示されているセルは、両方にそのようなオフセットが適用されている。認識されるように、この選択的トーン変調は、例えば、人が読むことのできる埋め込みデータパターンを、より人目につきやすくする利点のために用いられてもよい。そのような、埋め込まれた二次的データを構成するのに用いられるハーフトーンセル構造を完成するために、パターンは選択的に原画からオフセットされるであろう。例えば、この技術は、図１０の単語 "read" を、その周囲から視覚的にオフセットするのに用いることができそうである。
【００４６】
図１４に移ると、この選択的変調プロセスは、図６に示されるハーフトーン生成装置のデータチャネルを補って、コントローラ３１を、装置に含めることによって、すぐに実行できる。コントローラ３１は、所望の変調のデジタル記述、及び、プリント中のハーフトーンセルに関するレーザビーム存在位置のデジタル表現に応答する、データサンプルへの、またはデータサンプルからの、所定のデジタルオフセット値を選択的に加算または減算するために用いられる。任意に与えられた時間に構成中の、ハーフトーンセルの配置方向は、そのハーフトーンセルに埋め込まれているデータのビット値に依存する。しかしながら、左に傾斜したデータ軸を有するハーフトーンセルの半分からもう一方へのレーザビームの遷移は、Ａ及びＢアキュムレータの和が所定値（図示された例では３２）を通過する時に、確認される。それと似たように、右に傾斜したデータ軸を有するハーフトーンセルの半分からもう一方へのレーザビームの遷移は、Ａ及びＢアキュムレータの差がもう一つの所定値（この例では０）を通過する時に、確認される。従って、直列データに応答する閾値論理３２を用いて、アキュムレータ２２及び２３によって蓄積された値を演算的にモニターし、ハーフトーンセルのどちらの半分に走査スポットがあるかをコントローラ３１のために確認することができる。一方、所望の強度変調のデジタル記述は、典型的に、変調状態を区別するのに十分なビット長（例えば、図１３に示される８つの状態に備えるには、３ビットの長さの値）のデジタル値として、コントローラ３１に加えられる。
【００４７】
フルカラーでプリントされる、正確なカラーバランスとハーフトーン形状を有するサーペンタインを、複写術によって（reprographically）再現するのは非常に困難である。ハーフトーンセル内の、より暗い領域を表す、狭く斜めに延びる、色の無い領域（図７参照）は、忠実に再現するのが特に困難である。というのは、通常の複写は、近くに隣合う形状に、ぼけを生じて一緒にしてしまう傾向があり、セル方向の決定を補助する形状情報及び手掛かりを（消さないまでも）劣化させるからである。この顕著な特徴がないと、画像は”ワッフル（格子形の刻み目の）パターン”の形態をとり、偽造であることが容易に確認される。上記は、１インチ当たり約１００セルしかないスクリーン周波数でプリントされたハーフトーンで、観察されている。従って、このサーペンタインパターンの、フォトコピーによる偽造に対する阻止力は、典型的に１インチ当たり１５０から２００セルのハーフトーン周波数を有する、より高画質の画像では、増加すると信じられる。
【００４８】
典型的なカラー複写機が、高画質画像の正確なトーンの再現に優れているとしても、これをきちんとなすためには、複写機は独自のハーフトーンアルゴリズムを供給しなければならない。通常、複写機は、マシンのエレクトロニクスに独自の電子的ハーフトーン処理装置を埋め込んでおり、このハーフトーン処理装置は、典型的に、マシンに依存する調子再現曲線、及び、実行に依存するハーフトーンドット形状に合わせて、最適化されている。したがって、存在するサーペンタイン以外のハーフトーンが、サーペンタインハーフトーンを再現できるということは、およそありそうもない。サーペンタイン画像を再現できる別の方法は、画像を読み込み、セル配置方向を決定するために画像を処理し、”オリジナル”をプリントするのに必要なオリジナルデータファイルを再現することである。このためには、サーペンタインをプリントできるプリンタにアクセスする必要があり、通常の偽造者は、やりそうもないことである。
【００４９】
従って、サーペンタインは、信頼性の高いプリントアプリケーションのための、優れた候補である。このアプリケーションのために、１つまたはそれ以上のサーペンタインパターンを有するようにデザインされた原本の文書をプリントするために、典型的に、”信頼性の高いプリンタ”（例えば、官公庁のような、信頼性の高い団体によってコントロールされるプリンタ）が、使用される。所定のマシン及び／または人が読むことのできる情報は、各原本の文書にプリントされるサーペンタインパターンの少なくとも１つに埋め込まれ、そのような文書の任意に与えられたプリントは、問題の文書からこの既知の情報を再生しようと試みることによって、原本であるかどうかを、証明または否定される。上記は偽造に対抗する絶対的な安全対策ではないが、ゼログラフィーによる複写、または他の簡便に作成された複写を、原本としてつかませようとする人々への、大きな抑止力となる。
【００５０】
【発明の効果】
プリントされた文書に空間的にデータを埋め込むために使用できる、高い能力のハーフトーン形状が述べられてきた。サーペンタイン（serpentine) と呼ばれるのは、その蛇行する性質のせいであり、サーペンタインは、データを埋め込む能力とは別に、高画質画像を表示することもできる。円の代わりに、双曲線状の形状構造を基礎とすることで、ダイナミックトーンレンジを拡張する。この形状は正確なトーン制御を可能とし、カラープリントにも用いることができる。埋め込みデータは、標準グリフフォーマットに使用されるようなデータブロックのフレームにはめ込むことができ、また数字や文字のような形状のパターンに密集させることができる。この構造は、人が拡大鏡を補助具に用いて読むことができ、入力スキャナやコンピュータを使用する必要がないという、長所を有する。この形状を４５度回転することにより、斜めの構造に加えて、２つの代用”直立サーペンタイン”構造を構成でき、４つの配置方向を伴う埋め込みデータシステムを作り出す。この４方向システムは、より多くの変化に富んだパターンを作ることもできるが、付加的なノイズを短所とする。
【００５１】
サーペンタインに大きなダイナミックレンジを与える特徴は、また、サーペンタインの複写も困難にする。双曲線が、ハーフトーンセルを限定する対角線に漸近的に近づくにつれて、白の小さな領域は、コントラストを失わずに複写することが極端に困難になる。その結果生じる、ハーフトーンスクリーンの”ワッフル”の外観は、方向性を欠いて都合が良い。このサーペンタインの特徴は、画像認証及び偽造防止に向いている。
【００５２】
サーペンタイン埋め込みデータの複写が困難なことに依拠する、信頼性の高いプリント用アプリケーションが述べられた。プリントサービスを用いて安価なサーペンタインのオリジナルを作り、著者及び文書の所有者に戻る収益の流れを確立する。サーペンタインのオリジナルを作成するのは困難であり、利益を上げるには多数の複製をつくらなければならず、物理的な配布を通して摘発される危険があるため、価値の低いプリントの偽造は魅力がない。
【図面の簡単な説明】
【図１】円形サーペンタインハーフトーンセルで構成されるパターンを示す図である。
【図２】徐々に暗いトーン値になり、セルを構成する円弧の重なりを生じるトーン値を含む、一組の円形サーペンタインハーフトーンセルを示す図である。
【図３】ハーフトーンセルと、解析的に定義された双曲線形状関数との、典型的な関係を示す図である。
【図４】図３に示される形状関数に整合する双曲線群の代表的な例を示す図である。
【図５】図３に示される形状関数に整合する双曲線ハーフトーン形状を示す図である。
【図６】適切なハーフトーン生成装置の線図である。
【図７】双曲線ハーフトーン形状の成長を示す図である。
【図８】非ランダムサーペンタインパターンを示す図である。
【図９】別の非ランダムサーペンタインパターンを示す図である。
【図１０】人が読むことができる情報を含むサーペンタインパターンを示す図である。
【図１１】直立サーペンタインハーフトーンフィルパターンを示す図である。
【図１２】補足的サーペンタインハーフトーンフィルパターンを示す図である。
【図１３】データ変調サーペンタインパターンの、対称な構成要素の選択的強度変調を示す図である。
【図１４】図１２に示される選択的強度変調を実行するための、ハーフトーン生成装置を模式的に示す図である。
【符号の説明】
２１    テーブルルックアップメモリ
【図１】
0004010687.tif 000007
【図２】
0004010687.tif 000008
【図３】
0004010687.tif 000009
【図４】
0004010687.tif 000010
【図５】
0004010687.tif 000011
【図６】
0004010687.tif 000012
【図７】
0004010687.tif 000013
【図８】
0004010687.tif 000014
【図９】
0004010687.tif 000015
【図１０】
0004010687.tif 000016
【図１１】
0004010687.tif 000017
【図１２】
0004010687.tif 000018
【図１３】
0004010687.tif 000019
【図１４】
0004010687.tif 000020