(57)【要約】      （修正有）【課題】文書を処理するための改竄防止方法を提供する。【解決手段】符号化工程に関して、記録されるべきＮ値レベル画像に関して、画像の画素を、Ｎ個の可能な値を有する主成分に分解する工程（ステップ２３０３）と、主成分、及び画像内の画素の位置に依存するパターン要素を選択する工程（ステップ２３０３）と、選択パターン要素を転送媒体上に記録する工程（ステップ２３０８）とから成る。対応する復号工程に関して、方法は、画素に対する検索パターン要素を、記録文書から抽出する工程と、検索パターン要素から抽出された主成分、及び記録文書上の画素の位置に依存するパターン要素を判定する工程と、検索パターン要素及び判定パターン要素を比較する工程とから成る。【選択図】図３
2006014280.tif 000002
【特許請求の範囲】
【請求項１】
不正顕示機能付文書を処理するための方法であって、
（ａ）記録されるべきＮ値レベル画像に関して、前記画像の少なくとも１つの画素をＮ個の可能な値を有する主成分に分解する工程と、
（ｂ）少なくとも１つの所定のパターンからパターン要素を選択する工程であって、前記選択が、（ａｉ）前記主成分及び（ａｉｉ）前記画像内の前記少なくとも１つの画素の位置に依存する工程と、
（ｃ）前記少なくとも１つの画素に対する選択された前記パターン要素を転送媒体上に記録する工程と、
（ｄ）前記少なくとも１つの画素に対する検索パターン要素を記録文書から抽出する工程と、
（ｅ）（ｄｉ）前記検索パターン要素から抽出された主成分及び（ｄｉｉ）前記記録文書上の前記少なくとも１つの画素の位置に依存するパターン要素を判定する工程と、
（ｆ）前記検索パターン要素と判定された前記パターン要素とを比較する工程と
を有することを特徴とする方法。
【請求項２】
前記記録工程が、前記少なくとも１つの画素に対する前記選択パターン要素を印刷媒体上に印刷し、
前記抽出工程が、前記少なくとも１つの画素に対する走査パターン要素を印刷文書から抽出し、
前記判定工程が、前記走査パターン要素から抽出された主成分、及び前記記録文書上の前記少なくとも１つの画素の前記位置に依存するパターン要素を判定し、
前記比較工程が、前記走査パターン要素と判定された前記パターン要素とを比較する
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記検索パターン要素が判定された前記パターン要素と一致しない場合、前記記録文書の前記画素の前記主成分が改竄されたと宣言する工程をさらに有することを特徴とする請求項１に記載の方法。
【請求項４】
不正顕示機能付文書を処理するための方法であって、
（ａ）記録されるべきＮ値レベル画像に関して、前記画像の少なくとも１つの画素をＮ個の可能な値を有する主成分、並びに（ａｉ）前記主成分及び（ａｉｉ）前記画像内の前記少なくとも１つの画素の位置に依存する対応するランダム化副成分に分解する工程と、
（ｂ）前記少なくとも１つの画素に対する前記主成分及び前記ランダム化副成分を転送媒体上に記録する工程と、
（ｃ）前記少なくとも１つの画素に対する前記主成分を記録文書から抽出する工程と、
（ｄ）（ｄｉ）前記抽出主成分及び（ｄｉｉ）前記記録文書上の前記少なくとも１つの画素の位置に依存する前記対応するランダム化副成分を判定する工程と、
（ｅ）前記少なくとも１つの画素に対する前記印刷ランダム化副成分を印刷文書から測定する工程と、
（ｆ）測定された前記印刷ランダム化副成分が判定された前記ランダム化副成分と一致しない場合、前記印刷文書の前記画素が改竄されたと宣言する工程と
を有することを特徴とする方法。
【請求項５】
前記少なくとも１つの所定のパターンが、位置に基づいた少なくとも１つの公知のシーケンスであることを特徴とする請求項１に記載の方法。
【請求項６】
前記少なくとも１つの所定のパターンが、少なくとも１つの暗号フィールドであることを特徴とする請求項５に記載の方法。
【請求項７】
（ｇ）前記分解する工程（ａ）が、
（ｇａ）Ｎ箇所の暗号フィールドを生成する工程と、
（ｇｂ）前記Ｎ値レベル画像を使用して、前記暗号フィールドを位置決めする工程と、
（ｇｃ）前記主成分値に依存する前記暗号フィールドのうちの１つを選択する工程と、
（ｇｄ）前記画像内の前記少なくとも１つの画素の前記位置に依存する前記選択暗号フィールドから前記パターン要素を選択する工程とを有し、
（ｉ）前記記録する工程の後であって前記判定する工程の前に、前記方法が、
（ｉａ）前記Ｎ箇所の暗号フィールドを生成する工程と、
（ｉｂ）記録された前記画素の前記位置が設定可能となるように、前記記録されるべきＮ値レベル画像を使用して、前記暗号フィールドを位置決めする工程とをさらに有することを特徴とする請求項６に記載の方法。
【請求項８】
前記位置決めする工程（ｇｂ）は、前記Ｎ値レベル画像を使用して、画素が合同となるように行われ、
前記位置決めする工程（ｉｂ）は、画素が合同となるように行われる
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記位置決めする工程（ｉｂ）は、前記暗号フィールドを前記記録画像とブロック相関付けするブロック相関付け工程を更に含むことを特徴とする請求項８記載の方法。
【請求項１０】
前記記録する工程は、位置決めマークを前記転送媒体上に記録することを更に有し、前記位置決めマークは、少なくとも２つの登録マークを有することを特徴とする請求項８に記載の方法。
【請求項１１】
前記位置決めマークは、少なくとも１つの線形波形関数を有することを特徴とする請求項８に記載の方法。
【請求項１２】
不正顕示機能付文書を記録するための方法であって、
（ａ）記録されるべきＮ値レベル画像に関して、前記画像の少なくとも１つの画素を、Ｎ個の可能な値を有する主成分に分解する工程と、
（ｂ）少なくとも１つの所定のパターンからパターン要素を選択する工程であって、前記パターン要素が、（ｂｉ）前記主成分及び（ｂｉｉ）前記画像内の前記少なくとも１つの画素の位置に依存する工程と、
（ｃ）前記少なくとも１つの画素に対する前記パターン要素を、転送媒体上に記録する工程と
を有することを特徴とする方法。
【請求項１３】
不正顕示機能付文書を記録するための方法であって、
（ａ）記録されるべきＮ値レベル画像に関して、前記画像の少なくとも１つの画素を、Ｎ個の可能な値を有する主成分、並びに（ａｉ）前記主成分及び（ａｉｉ）前記画像内の前記少なくとも１つの画素の位置に依存する対応するランダム化副成分に分解する工程と、
（ｂ）前記少なくとも１つの画素に対する前記主成分及び前記ランダム化副成分を、転送媒体上に記録する工程と
を有することを特徴とする方法。
【請求項１４】
前記少なくとも１つの所定のパターンは、位置に基づいた少なくとも１つの公知のシーケンスであることを特徴とする請求項１２に記載の方法。
【請求項１５】
前記少なくとも１つの所定のパターンは、少なくとも１つの暗号フィールドであることを特徴とする請求項１４に記載の方法。
【請求項１６】
（ｃ）前記分解工程（ａ）は、
（ｃａ）Ｎ箇所の暗号フィールドを生成すること、
（ｃｂ）前記Ｎ値レベル画像を使用して、画素が合同となるように前記暗号フィールドを配置すること、
（ｃｃ）前記主成分値に依存する前記暗号フィールドのうちの１つを選択すること、
（ｃｄ）前記画像内の前記少なくとも１つの画素の前記位置に依存する前記選択暗号フィールドから前記副成分を選択すること
とを有することを特徴とする請求項１５に記載の方法。
【請求項１７】
記録不正顕示機能付文書の妥当性検証を行うための方法であって、
（ａ）検索パターン要素を、記録文書内の位置から抽出する工程と、
（ｂ）（ｂｉ）前記検索パターン要素の特性及び（ｂｉｉ）前記位置に依存するパターン要素を選択する工程と、
（ｃ）前記検索パターン要素と選択された前記パターン要素とを比較する工程と
を有することを特徴とする方法。
【請求項１８】
前記検索パターン要素が、選択された前記パターン要素と一致しない場合、前記記録文書内の前記位置における特性が改竄されたと確定する工程をさらに有することを特徴とする請求項１７に記載の方法。
【請求項１９】
記録不正顕示機能付文書の妥当性検証を行うための方法であって、
（ａ）少なくとも１つの記録画素に対して、Ｎ個の可能な値を有する主成分を前記記録文書から抽出する工程と、
（ｂ）（ｂｉ）前記抽出主成分及び（ｄｉｉ）前記少なくとも１つの記録画素の位置に依存する対応するランダム化副成分を判定する工程と、
（ｃ）前記少なくとも１つの画素に対する記録ランダム化副成分を前記記録文書から測定する工程と、
（ｄ）測定された前記記録ランダム化副成分と判定された前記ランダム化副成分とを比較する工程と
を有することを特徴とする方法。
【請求項２０】
測定された前記記録ランダム化副成分が判定された前記ランダム化副成分と一致しない場合、前記記録文書の前記画素が改竄されたと確定する工程をさらに有することを特徴とする請求項１９に記載の方法。
【請求項２１】
前記特性が、前記文書の人間の読み手には可視であることを特徴とする請求項１７に記載の方法。
【請求項２２】
選択された前記パターン要素が、位置に基づいた公知のシーケンスである所定のパターンから選択されることを特徴とする請求項１７に記載の方法。
【請求項２３】
前記所定のパターンは、暗号フィールドであることを特徴とする請求項２２に記載の方法。
【請求項２４】
前記選択される前に、
（ｅ）Ｎ箇所の暗号フィールドを生成する工程と、
（ｆ）前記検索パターン要素の前記位置と暗号フィールド位置との関連付けが可能となるように、前記記録画像を使用して、前記暗号フィールドを位置決めする工程と
をさらに有することを特徴とする請求項２３に記載の方法。
【請求項２５】
位置決めマークが前記文書上に記録され、前記位置決めマークは、少なくとも２つの登録マークを有することを特徴とする請求項２４に記載の方法。
【請求項２６】
前記位置決めマークは、少なくとも１つの線形波形関数を有することを特徴とする請求項２４に記載の方法。
【請求項２７】
前記位置決めする工程（ｆ）が、前記暗号フィールドを前記記録画像とブロック相関付けすることをさらに有することを特徴とする請求項２４に記載の方法。
【請求項２８】
Ｎ値レベル画像が記録された不正顕示機能付文書であって、
前記画像の少なくとも１つの画素に関して、（ａ）前記画素のレベル及び（ｂ）記録された前記文書の前記画素の位置に依存する暗号値を有し、且つ前記画素の前記レベルに可視的に近似する記録パターン要素を有することを特徴とする不正顕示機能付文書。
【請求項２９】
Ｎ値レベル画像が記録された不正顕示機能付文書であって、
前記画像の少なくとも１つの記録画素に関して、Ｎ個の可能な値を有する記録主成分と、（ａ）前記主成分及び（ｂ）前記記録文書内の前記少なくとも１つの記録画素の位置に依存する記録ランダム化副成分とを有することを特徴とする不正顕示機能付文書。
【請求項３０】
プロセッサに上記の方法のうちのいずれかを実行させるためのコンピュータプログラムが記録されたコンピュータ読み取り可能な記憶媒体を具備することを特徴とするコンピュータプログラムプロダクト。
【請求項３１】
プロセッサに上記の方法のうちのいずれかを実行させるためのコンピュータプログラム。
【請求項３２】
セキュリティ文書の改竄を検知する方法であって、
（ａ）前記文書に対応する走査データを生成する工程と、
（ｂ）前記走査データと少なくとも１つの２次元暗号フィールドとの間の領域マッチングを行うことにより、位置決め情報を得る工程と、
（ｃ）前記位置決め情報及び前記走査データを使用して、前記セキュリティ文書内の改竄を検知する工程と
を有することを特徴とする方法。
【請求項３３】
前記領域マッチングが、ブロック相関付けであることを特徴とする請求項３２に記載の方法。
【請求項３４】
前記改竄の検知が、前記走査データと前記少なくとも１つの２次元暗号フィールドとの比較により特徴付けられることを特徴とする請求項３３に記載の方法。
【請求項３５】
前記走査データが、少なくとも１つのグラフィック要素を含むことを特徴とする請求項３２に記載の方法。
【請求項３６】
前記グラフィック要素が、可読テキスト文字であることを特徴とする請求項３５に記載の方法。
【請求項３７】
改変を明らかにするプロセスが、暗号鍵の知識を必要な条件とし、前記プロセスにより明らかにされない実質的な改変を行う困難度が、鍵空間の大きさにほぼ比例することを特徴とする請求項３２に記載の方法。
【請求項３８】
改変された前記記録文書のうちの実質的な副次部分のいずれかにおける改変を明らかにすることが、改変された前記記録文書の残る部分の知識と独立であることを特徴とする請求項３２に記載の方法。
【請求項３９】
記録画像内の改竄を検知する方法であって、
（ａ）画像を少なくとも１つの２次元暗号信号と結合することにより第２の画像を形成する工程と、
（ｂ）前記第２の画像を記録することにより記録画像を形成する工程と、
（ｃ）前記記録画像を処理することにより検索画像を作成する工程と、
（ｄ）前記少なくとも１つの２次元暗号信号に対する前記検索画像の配列を検出する工程と、
（ｅ）前記配列、前記検索画像及び前記少なくとも１つの２次元暗号信号を使用して、改竄を検知する工程と
を有することを特徴とする方法。
【請求項４０】
セキュリティ文書を作成するための装置であって、
（ａ）オリジナル文書を検索し、且つ文書画像を作成するための検索部と、
（ｂ）前記文書画像をセキュリティパターンでマーキングすることにより、マーク文書画像を作成するためのマーキング部と、
（ｃ）前記マーク文書画像を記録することにより、セキュリティ文書を作成するための記録部とを備え、
前記セキュリティ文書が前記オリジナル文書の可読表現であって、前記セキュリティパターンが前記オリジナル文書と前記セキュリティ文書との間の改変を検知することを特徴とする装置。
【請求項４１】
前記オリジナル文書が、可読テキストを含み、
前記セキュリティ文書が、等価の可読テキストを含み、
前記オリジナル文書の可読テキストと前記セキュリティ文書の可読テキストとの間の等価性を認証することを特徴とする請求項４０に記載の装置。
【請求項４２】
改変された記録文書と非改変形態との間の改変を明らかにするための装置であって、
（ａ）前記記録文書に対応する検索データを作成する検索手段と、
（ｂ）前記検索データにおけるグラフィック要素の形状と、前記非改変形態におけるグラフィック要素の形状との間の少なくとも１つのグラフィック要素の形状の前記改変を判定し、且つ前記非改変形態を感知できない判定手段と、
（ｃ）前記形状の前記判定された改変を出力する出力手段と
を備えることを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記録文書の作成及び処理に関し、特に、不正顕示機能付文書の作成及び不正顕示機能付文書の改竄の検知に関する。説明を容易にし、且つ説明の一貫性を維持するために、まず、印刷文書に関する説明を行う。しかしながら、開示された方法は、情報が記録された他の形態の文書にも同様に適用できる。
【０００２】
［背景］
最初に印刷文書を作成した時期から、その印刷文書がある不正な方法で改変されていないことを保証することは、多くの場合において望ましい。例えば、ある日時に同意され、署名された契約は、その後に不正に改変されている可能性がある。このような改変を詳細に検知できることは、望ましい。同様に、小切手及び通貨代替物を含む様々な種類の有価証券は、不正に改変され易い価値を記録している。不正な改変に対する検知は、いずれの場合においても望ましい。このような検知が自動的に行われ、この検知により改変の正確な特徴を明らかにすることは、更に望ましい。文書に対する不正な改竄を検知することに加えて、このような文書が、不正な改変を可視的に防止できることは望ましい。
【０００３】
文書に対する不正な改変の防止及び検知には、様々な方法が、提案され、使用されてきた。
【０００４】
高品質カラースキャナ及びプリンタが市販される以前の使用方法の一つは、その時期では再現が困難であった特殊なフォントを使用して、又は特殊な陰影を施して重要情報（金額等）を印刷する方法であった。しかしながら、現代のプリンタ及びスキャナを使用すれば、このような技法に対しての攻撃が容易となった。
【０００５】
改変検知の公知の一方法では、文書のページの一部に印刷された２次元バーコードを使用して、署名領域等のいくつかの他の部分の表現を符号化する（暗号的に行われる可能性がある）。この２次元バーコードは、復号できる。オペレータは、生成された画像と、類似性確認を意図した領域とを比較できる。
【０００６】
関連研究の中心は、印刷／走査サイクルが施されていないデジタル画像の改竄の検知である。多くの「フラジャイル（fragile）透かし」技法は、この研究分野において知られる。しかしながら、印刷文書が、ノイズ、ローテーション／スケーリング／トランスレーション（ＲＳＴ）、再サンプリング及び局所変形（印刷／走査サイクルにおいて発生する）の導入に対する耐久力に乏しいため、これらの改竄検知技法は、一般に、印刷文書の改竄検知には適用できない。これらの改竄検知技法のうちのいくつかでは、画像の画素の最下位ビットの全て又はいくつかを、各画素内に残るビットのチェックサム等の形態で置換することにより演算を行う。
【０００７】
また、多くの「セミフラジャイル（semi-fragile）透かし」システムは、既に説明された。これらのセミフラジャイル透かしシステムは、相互相関を使用して、画像部分の簡易埋め込みシフトコピーの存在を検知するシステムを含む。別の技法は、透かしを画像ブロック内に埋め込み、その後、これらの埋め込まれた透かしの検知強度を比較することにより、改変されたブロックが存在するか否かを認識する方法である。これらのセミフラジャイル透かしシステムでは、透かしの検知能力が改善されると、位置推定能力が小さくなる傾向がある。また、それらの位置推定能力が改善されると、これらのセミフラジャイル透かしシステムは、よりノイズ及び他の変形に対する感受性が高くなるため、印刷文書の局所変化の検知に使用できない。
【０００８】
他の技法では、特殊な素材を利用して、文書改変を困難にする。このような技法は、ラミネートに対する損傷が明らかな印刷表面を被覆する複数のラミネートを含む。しかしながら、特殊な素材の利用により、文書作成は複雑化するため、特殊な素材の利用は、普通紙用途に適用できない。また、特殊な素材には、自動検知を施すことができない。
【０００９】
多くの既存の技法における追加的な欠点は、暗号セキュリティが脆弱であることである。多くの場合、一旦、採用されるべき暗号アルゴリズムが識別されると、このアルゴリズムは、直接識別された方法を攻撃するための破壊方法となる。
【００１０】
本技法の別の共通の欠点は、ページの広い領域にわたるか、又は認証されるべき画像領域に完全に分離された領域にもわたる改変検知情報の分布である（上記のバーコード法と同様）。認証されるべき画像領域から離れた領域内の文書の偶発的な汚れが存在する場合、この改変検知情報の分布が問題となる。これらの改竄検知技法の多くは、文書全体の領域の認証に使用できないため、文書は、これら技法を含めるために特殊なデザインが施される必要がある。
【００１１】
更なる種類の技法では、文書のオリジナル非改変形態に関する情報を、認証処理へ独立して転送する方法を使用する。この方法は、独立した知識を有する人物への電話呼び出しと同様に単純であり、安全保証位置内の文書の完全なコピーを維持するために拡張されてもよい。このような技法は、この技法がこのような独立情報の処理及び格納を必要とするため、多くの実施上の不都合な点を有する。
【特許文献１】米国特許第６，４５７，６５１号明細書
【特許文献２】米国特許第０，６３６，６９６号明細書
【特許文献３】米国特許第５，２９１，２４３号明細書
【特許文献４】米国特許第６，１６７，１４７号明細書
【特許文献５】米国特許第５，５０９，６９２号明細書
【００１２】
［要約］
本発明の目的は、既存の構成の１つ以上の欠点をほぼ解決するか、あるいは、少なくとも改善することである。
【００１３】
本発明は、印刷を所望する情報の処理形態（「ソース」情報と呼ばれる）を印刷文書に印刷する（記録情報に印刷された形態が使用される場合）ことにより、上述の問題の解決方法を探索する構成、一般に、「改竄防止方法」と呼ばれるを開示する。上述の処理手順では、印刷され、可視摂動されたソース情報形態を作成する。摂動は、人間又は機械手段（例えば、ビデオ検知及びビデオ処理を使用して）が、印刷文書からソース情報を読み取ることを可能とするために、印刷摂動情報が、ソース情報に関して十分な忠実度を保持することである。しかしながら、「摂動」がソース情報への空間的な手掛かりであるため、ソース情報は、印刷文書の各領域における摂動の詳細を確立する。
【００１４】
説明を容易にし、説明の一貫性を維持するために、まず、印刷文書への開示された改竄防止方法の用途に関する説明を行う。しかしながら、開示された方法は、情報が記録された文書の他の形態にも同様に適用できる。従って、例えば、改竄防止方法は、情報が光学的に記録された撮影フィルム（銀塩等）を有する文書に適用できる。
【００１５】
摂動情報を形成するためのソース情報の処理では、暗号的に安全な鍵を使用する。一般に、この鍵の知識を使用しない印刷文書への改竄では、改竄領域内に「正確な」摂動要素を発生させることはない。印刷文書の改竄状態を認証するために、最初に、印刷文書の認証者は、目視により、あるいはビデオ処理を使用して、摂動ソース情報を抽出する。次に、ユーザは、ユーザの暗号コードの知識を使用して、文書上の摂動を再現する。改竄が行われた領域において、改竄情報と関連付けられた摂動は、この再現によって発生する。しかしながら、改竄者が、正確な摂動を正確に作成することが暗号的に妨げられたため、これらの摂動は、予め規定された信頼水準に対して正確ではない。
【００１６】
改竄防止方法は、本来、不正顕示機能付文書を作成するために使用された暗号フィールド（の再生）を使用して精位置決めが施されるべき不正顕示機能付文書を必要とする。フィールドは、フィールドが機密（この場合、鍵）に基づくという意味で暗号的である。フィールドは、フィールドの断片が知られている場合においても、鍵の知識を使用せずにフィールドを完全に生成するためには実際的ではないという性質を有する。一構成によると、不正顕示機能付文書が暗号フィールドに関して変形されなかった場合、単純な登録ポイントは、不正顕示機能付文書内に組み込むことができる。これらの登録ポイントは、不正顕示機能付文書と妥当性検証に使用された暗号フィールドとの間の精位置決めを得るために使用できる。実現の観点から、図２に関して説明されるように、不正顕示機能付文書１０５が走査された場合、登録ポイントは、スキャナ２２１８（図１を参照）により検出できる。粗位置決め工程は、任意である。多くの用途において、特に、改竄が文書の小さな領域内で検知される場合、他の粗位置決め方法は、使用できる。いくつかの例においては、手動粗位置決めさえも利用できる。別の構成において、手動粗位置決めは、走査／印刷サイクルにより引き起こされた文書変形に対してよりロバストである。分散「粗」位置決め情報及び分散「精」位置決め情報は、不正顕示機能付文書内に埋め込まれ、その後、不正顕示機能付文書の妥当性検証時に、位置決めを実現するために使用される。
【００１７】
本発明の一態様によれば、不正顕示機能付文書を処理するための方法であって、
（ａ）記録されるべきＮ値レベル画像に関して、前記画像の少なくとも１つの画素を、Ｎ個の可能な値を有する主成分に分解する工程と、
（ｂ）少なくとも１つの所定のパターンからパターン要素を選択する工程であって、前記選択が、（ａｉ）前記主成分及び（ａｉｉ）前記画像内の前記少なくとも１つの画素の位置に依存する工程と、
（ｃ）前記少なくとも１つの画素に対する前記選択パターン要素を、転送媒体上に記録する工程と、
（ｄ）前記少なくとも１つの画素に対する検索パターン要素を、前記記録文書から抽出する工程と、
（ｅ）（ｄｉ）前記検索パターン要素から抽出された主成分及び（ｄｉｉ）前記記録文書上の前記少なくとも１つの画素の位置に依存するパターン要素を判定する工程と、
（ｆ）前記検索パターン要素と前記判定パターン要素とを比較する工程とから成ることを特徴とする方法を提供する。
【００１８】
本発明の別の態様によれば、不正顕示機能付文書を処理するための方法であって、
（ａ）記録されるべきＮ値レベル画像に関して、前記画像の少なくとも１つの画素を、Ｎ個の可能な値を有する主成分、並びに（ａｉ）前記主成分及び（ａｉｉ）前記画像内の前記少なくとも１つの画素の位置に依存する対応するランダム化副成分に分解する工程と、
（ｂ）前記少なくとも１つの画素に対する前記主成分及び前記ランダム化副成分を、転送媒体上に記録する工程と、
（ｃ）前記少なくとも１つの画素に対する前記主成分を、前記記録文書から抽出する工程と、
（ｄ）（ｄｉ）前記抽出主成分及び（ｄｉｉ）前記記録文書上の前記少なくとも１つの画素の位置に依存する前記対応するランダム化副成分を判定する工程と、
（ｅ）前記少なくとも１つの画素に対する前記印刷ランダム化副成分を、前記印刷文書から測定する工程と、
（ｆ）前記測定印刷ランダム化副成分が、前記判定ランダム化副成分と一致しない場合、前記印刷文書の前記画素は、改竄されたと宣言する工程とから成ることを特徴とする方法を提供する。
【００１９】
本発明のさらに別の態様によれば、不正顕示機能付文書を記録するための方法であって、
（ａ）記録されるべきＮ値レベル画像に関して、前記画像の少なくとも１つの画素を、Ｎ個の可能な値を有する主成分に分解する工程と、
（ｂ）少なくとも１つの所定のパターンからパターン要素を選択する工程であって、前記パターン要素が、（ｂｉ）前記主成分及び（ｂｉｉ）前記画像内の前記少なくとも１つの画素の位置に依存する工程と、
（ｃ）前記少なくとも１つの画素に対する前記パターン要素を、転送媒体上に記録する工程とから成ることを特徴とする方法を提供する。
【００２０】
本発明のさらに別の態様によれば、不正顕示機能付文書を記録するための方法であって、
（ａ）記録されるべきＮ値レベル画像に関して、前記画像の少なくとも１つの画素を、Ｎ個の可能な値を有する主成分、並びに（ａｉ）前記主成分及び（ａｉｉ）前記画像内の前記少なくとも１つの画素の位置に依存する対応するランダム化副成分に分解する工程と、
（ｂ）前記少なくとも１つの画素に対する前記主成分及び前記ランダム化副成分を、転送媒体上に記録する工程とから成ることを特徴とする方法を提供する。
【００２１】
本発明のさらに別の態様によれば、記録不正顕示機能付文書の妥当性検証を行うための方法であって、
（ａ）検索パターン要素を、前記記録文書内の位置から抽出する工程と、
（ｂ）（ｂｉ）前記検索パターン要素の特性及び（ｂｉｉ）前記位置に依存するパターン要素を選択する工程と、
（ｃ）前記検索パターン要素と前記選択パターン要素とを比較する工程とから成ることを特徴とする方法を提供する。
【００２２】
本発明のさらに別の態様によれば、記録不正顕示機能付文書の妥当性検証を行うための方法であって、
（ａ）少なくとも１つの記録画素に対して、Ｎ個の可能な値を有する主成分を前記記録文書から抽出する工程と、
（ｂ）（ｂｉ）前記抽出主成分及び（ｄｉｉ）前記少なくとも１つの記録画素の位置に依存する対応するランダム化副成分を判定する工程と、
（ｃ）前記少なくとも１つの画素に対する前記記録ランダム化副成分を、前記記録文書から測定する工程と、
（ｄ）前記測定記録ランダム化副成分と前記判定ランダム化副成分とを比較する工程とから成ることを特徴とする方法を提供する。
【００２３】
本発明のさらに別の態様によれば、Ｎ値レベル画像が記録された不正顕示機能付文書であって、
前記画像の少なくとも１つの画素に関して、（ａ）前記画素のレベル及び（ｂ）前記記録文書の前記画素の位置に依存する暗号値を有し、且つ前記画素の前記レベルに可視的に近似する記録パターン要素を有することを特徴とする不正顕示機能付文書を提供する。
【００２４】
本発明のさらに別の態様によれば、Ｎ値レベル画像が記録された不正顕示機能付文書であって、
前記画像の少なくとも１つの記録画素に関して、Ｎ個の可能な値を有する記録主成分と、（ａ）前記主成分及び（ｂ）前記記録文書内の前記少なくとも１つの記録画素の位置に依存する記録ランダム化副成分とを有することを特徴とする不正顕示機能付文書を提供する。
【００２５】
本発明のさらに別の態様によれば、プロセッサに上記の方法のうちのいずれかを実行させるためのコンピュータプログラムが記録されたコンピュータ可読媒体を具備することを特徴とするコンピュータプログラムプロダクトを提供する。
【００２６】
本発明のさらに別の態様によれば、プロセッサに上記の方法のうちのいずれかを実行させるためのコンピュータプログラムを提供する。
【００２７】
本発明のさらに別の態様によれば、セキュリティ文書の改竄を検知する方法であって、
（ａ）前記文書に対応する走査データを生成する工程と、
（ｂ）前記走査データと少なくとも１つの２次元暗号フィールドとの間の領域マッチングを行うことにより、位置決め情報を得る領域マッチング工程と、
（ｃ）前記位置決め情報及び前記走査データを使用して、前記セキュリティ文書内の改竄を検知する改竄検知工程とから成ることを特徴とする方法を提供する。
【００２８】
本発明のさらに別の態様によれば、記録画像内の改竄を検知する方法であって、
（ａ）画像を少なくとも１つの２次元暗号信号と結合することにより、第２の画像を形成する結合工程と、
（ｂ）前記第２の画像を記録することにより、記録画像を形成する記録工程と、
（ｃ）前記記録画像を処理することにより、検索画像を作成する記録画像処理工程と、
（ｄ）前記少なくとも１つの２次元暗号信号に対する前記検索画像の配列を検出する配列検出工程と、
（ｅ）前記配列、前記検索画像及び前記少なくとも１つの２次元暗号信号を使用して、改竄を検知する改竄検知工程とから成ることを特徴とする方法を提供する。
【００２９】
本発明のさらに別の態様によれば、セキュリティ文書を作成するための装置であって、
（ａ）オリジナル文書を検索し、且つ文書画像を作成するための検索要素と、
（ｂ）前記文書画像をセキュリティパターンでマーキングすることにより、マーク文書画像を作成するためのマーキング要素と、
（ｃ）前記マーク文書画像を記録することにより、セキュリティ文書を作成するための記録要素とを具備し、
前記セキュリティ文書は、前記オリジナル文書の可読表現であり、前記セキュリティパターンは、前記オリジナル文書と前記セキュリティ文書との間の改変の検知を提供することを特徴とする装置を提供する。
【００３０】
本発明のさらに別の態様によれば、改変記録文書と非改変形態との間の改変を明らかにするための装置であって、
（ａ）前記記録文書に対応する検索データを作成する検索手段と、
（ｂ）前記検索データにおけるグラフィック要素の形状と、前記非改変形態におけるグラフィック要素の形状との間の少なくとも１つのグラフィック要素の形状の前記改変を判定し、且つ前記非改変形態を感知できない判定手段と、
（ｃ）前記形状の前記判定された改変を出力する出力手段とを具備することを特徴とする装置を提供する。
【００３１】
本発明の他の態様もまた開示される。
【００３２】
［最良の形態を含む詳細な説明］
本発明は、１つ以上の添付の図面のステップ及び／又は特徴と関連させて説明される。１つ以上の添付の図面において、同一符号で示すステップ及び／又は特徴は、別途特定されない限り、同一の１つ以上の機能又は動作を表す。
【００３３】
尚、「背景技術」及び従来技術の構成に関連する以上の記載は、それぞれ刊行物及び／又は実施を通して公知技術を形成する複数の文献又は装置の記載に関する。当該記載は、これらの文献や装置が多少なりとも当該技術分野における周知技術の一部を形成するものとして本発明者又は出願人が説明したものと解釈するべきではない。
【００３４】
開示された「改竄防止方法」により、モノクロのオリジナル文書を特定セキュリティマーキングにより印刷する（又は、再印刷する）ことが可能となる。この説明は、２値レベル（例えば、モノクロ）文書に関するが、開示された改竄防止方法は、例えば、黒ソース情報、グレーソース情報及び白ソース情報を使用した多値レベル文書に利用できる。あるいは、改竄防止方法では、ディザ法又は網点を使用して、黒画素及び白画素で階調を表現してもよい。生成された「不正顕示機能付」文書は、人間により直接に認識及び読み取りが行われ、走査及び解析を施すことにより、改竄（改変等）が行われたか否かを検知できる。読み手にとっての印刷文書上での可視事象とオリジナル文書上での可視事象との間の局所化された詳細な差異は、例えば、ノイズ、退色、物理的変形、及び印刷／走査処理により導入される多くの変化等の印刷文書に対する微小な損傷でさえも明らかにできる。不正顕示機能付文書に適用される妥当性検証処理は、オリジナルのソース情報の知識を必要としない。差異は、局所化された詳細な状態で明らかにされるので、明らかにされた差異を見る人物は、汚れ又は偶発的なペンマーク等の些細な変化から金額の変化等の重要な変化までを容易に識別できる。妥当性検証処理は、予め規定された信頼水準までは、「中継者」攻撃に対して、暗号的に安全である。中継者攻撃は、鍵を所有していない場合における悪意のある介入による攻撃を説明するために使用される暗号法用語である。
【００３５】
妥当性検証解析は、物質的な（印刷された）不正顕示機能付文書及び共通秘密鍵へのアクセスのみに必要である。好適な構成において、この共通秘密鍵は、システムの暗号安全管理を疑問視することなく、多くの文書に対して同一であってもよい。特に、本発明の方法では、同一の鍵でマーキングした異なるページの情報に基づく攻撃を受け易くなることはない。
【００３６】
次のいくつかの部分の説明では、コンピュータメモリ内のデータの演算アルゴリズム及び演算記号表現を、明示的又は黙示的に提示する。これらのアルゴリズムの説明及び表現は、データ処理の当業者の業務の実質内容を最も効果的に他の当業者に受け渡すために、データ処理の当業者により使用される方法である。ここで、一般に、アルゴリズムは、所望の結果を導出する工程の自己矛盾のないシーケンスであると考えられる。この工程は、物理量の物理的処理を必要とする工程である。これらの量は、必ずしも必要ではないが、通常、格納、転送、結合、比較及び他の操作を施すことが可能な電気信号又は磁気信号の形態をとる。主に慣用的な理由により、ビット、値、要素、記号、文字、用語、数等として、これらの信号を示すことが好都合な場合があることが判明している。
【００３７】
しかしながら、上記の用語及び類似の用語は、適切な物理量と関連付けられるべきであり、これらの物理量に適用される好都合な表現に過ぎないことを理解すべきである。特に説明はしないが、次の説明から明らかなように、本明細書を通して、「走査」、「算出」、「判定」、「交換」、「生成」、「初期化」、「出力」等の用語を使用する説明が、コンピュータシステム又は類似の電子装置の動作及び処理に関連することは理解できる。コンピュータシステム又は類似の電子装置は、レジスタ内及びコンピュータシステムのメモリ内の物理（電子）量として表現されたデータを処理し、このデータをコンピュータシステムのメモリ内、レジスタ内又は他の情報記憶装置内、情報送信装置内又は情報表示装置内の物理量として同様に表現される他のデータに変換する。
【００３８】
また、本明細書は、本発明の方法を実施する装置を開示する。このような装置は、要求される目的に応じて特別に構築されてもよい。あるいは、このような装置は、汎用コンピュータ又はコンピュータ内に格納されたコンピュータプログラムにより選択的に実行又は再構成される他の装置を具備してもよい。この説明において提示された複数のアルゴリズム及び表示は、本質的に、いずれかの特定コンピュータ又は他の装置と関連付けられていない。様々な汎用機械は、この説明の教示に従ったプログラムと共に使用されてもよい。あるいは、必要な方法工程を実行するためのより特殊化された装置の構築が、適切である。従来の汎用コンピュータの構造は、以下の説明から明らかとなる。
【００３９】
また、開示された構成は、暗黙のうちに、１つ以上のコンピュータプログラムモジュールを開示する。この開示において、当業者には明らかなように、ここで説明する方法の個々の工程は、１つ以上のコンピュータコードモジュールにより実行される。１つ以上のコンピュータプログラムが、任意の特定プログラミング言語及びその特定プログラミング言語の実現に限定されることは、意図されていない。様々なプログラミング言語及びプログラミング言語のコーディングが、この説明に含まれる本開示の教示を実現するために使用できることは、理解できる。更に、コンピュータプログラムは、任意の特定制御フローに限定されることは、意図されていない。そのため、多くの他のコンピュータプログラムの変形が存在する。この変形では、開示された構成の趣旨の範囲を逸脱せずに、異なる制御フローを使用できる。更に、コンピュータプログラムの１つ以上のステップは、連続的にではなく、並行に実行されてもよい。
【００４０】
このようなコンピュータプログラムは、任意の１つ以上のコンピュータ可読媒体内に格納されてもよい。コンピュータ可読媒体は、磁気ディスク、光ディスク、メモリチップ又は１つ以上の汎用コンピュータとインタフェースで連結するのに適切な他の記憶装置等の記憶装置を含む。また、コンピュータ可読媒体は、インターネットシステムで例証される１つ以上のハードワイヤード媒体、又はＧＳＭ移動式電話システムで例証される無線媒体を含んでもよい。コンピュータプログラムモジュールは、汎用コンピュータ等内に読み込まれ、実行されることにより、好適な方法の工程を実現する装置において、効果的に得られる。
【００４１】
図１は、説明される改竄防止構成が実現可能な汎用コンピュータを概略的に示すブロック図である。改竄防止方法は、図１に示すような汎用コンピュータシステム２２００を使用して実現されることが好ましい。この場合、図３、図４、図６、図７、図１２〜図１５、図１７、図１８の処理は、コンピュータシステム２２００内で実行する改竄防止アプリケーションプログラム等のソフトウェアとして実現されてもよい。特に、改竄防止方法の工程は、コンピュータにより実行される改竄防止アプリケーションソフトウェアの命令により実行される。命令は、各々が１つ以上の特定タスクを実行する１つ以上のコードモジュールとして構成されてもよい。また、改竄防止アプリケーションソフトウェアは、２つの個別の区分に分割されてもよい。この個別の区分において、第１の区分は、改竄防止方法を実行し、第２の区分は、第１の区分とユーザとの間のユーザインタフェースを管理する。改竄防止アプリケーションソフトウェアは、例えば、以下に説明する記憶装置を含むコンピュータ可読媒体内に格納されてもよい。改竄防止アプリケーションソフトウェアは、コンピュータ可読媒体からコンピュータ内に読み込まれ、コンピュータにより実行される。このようなソフトウェア又はコンピュータプログラムが記録されたコンピュータ可読媒体は、コンピュータプログラムプロダクトである。コンピュータ内のコンピュータプログラムプロダクトの使用は、改竄防止に有用な装置に対して有効である。
【００４２】
コンピュータシステム２２００は、コンピュータモジュール２２０１と、キーボード２２０２、マウス２２０３及びスキャナ２２１８等の入力装置と、プリンタ２２１５、表示装置２２１４及びスピーカ２２１７を含む出力装置とにより構成される。変調器−復調器（モデム）トランシーバ装置２２１６は、例えば、電話回線２２２１又は他の機能媒体を介して接続可能な通信ネットワーク２２２０との通信のために、コンピュータモジュール２２０１により使用される。モデム２２１６は、インターネットへのアクセス、及びローカルエリアネットワーク（ＬＡＮ）又は広域ネットワーク（ＷＡＮ）等の他のネットワークシステムへのアクセスの獲得のために使用できる。また、モデム２２１６は、いくつかの実現例において、コンピュータモジュール２２０１に内蔵されてもよい。
【００４３】
コンピュータモジュール２２０１は、通常、少なくとも１つのプロセッサユニット２２０５及びメモリユニット２２０６を含む。メモリユニット２２０６は、例えば、半導体ランダムアクセスメモリ（ＲＡＭ）及び半導体読み取り専用メモリ（ＲＯＭ）から構成される。また、モジュール２２０１は、多数の入出力（Ｉ／Ｏ）インタフェースを含む。多数の入出力（Ｉ／Ｏ）インタフェースは、ビデオ表示装置２２１４及びスピーカ２２１７に接続されるオーディオ／ビデオインタフェース２２０７と、キーボード２２０２、マウス２２０３及び任意のジョイスティック（不図示）用のＩ／Ｏインタフェース２２１３と、モデム２２１６、スキャナ２２１８及びプリンタ２２１５用のインタフェース２２０８とを含む。いくつかの実現例において、モデム２２１６は、インタフェース２２０８内等のコンピュータモジュール２２０１に内蔵されてもよい。記憶装置２２０９は、コンピュータモジュール２２０１内に設けられ、通常、ハードディスクドライブ２２１０と、フロッピディスクドライブ２２１１とを含む。更に、コンピュータモジュール２２０１は、磁気テープドライブ（不図示）を使用してもよい。ＣＤ−ＲＯＭドライブ２２１２は、通常、不揮発性データの供給源として設けられる。
【００４４】
コンピュータモジュール２２０１の構成要素２２０５から構成要素２２１３は、通常、関連技術の当業者に知られるコンピュータシステム２２００の従来の動作モードが得られるように、相互接続バス２２０４を介して通信を行う。上述の構成を実現可能なコンピュータの例は、複数のＩＢＭ−ＰＣと、ＩＢＭ−ＰＣの互換機と、Ｓｕｎ  Ｓｐａｒｃｓｔａｔｉｏｎｓ又はＳｕｎ  Ｓｐａｒｃｓｔａｔｉｏｎｓから派生した類似のコンピュータシステムとを含む。
【００４５】
通常、改竄防止アプリケーションプログラムは、ハードディスクドライブ２２１０上に常駐する。改竄防止アプリケーションプログラムは、プロセッサ２２０５により、ハードディスクドライブ２２１０の作動時に読み取られ、制御される。プログラム及びネットワーク２２２０から取り込まれた任意のデータの中間格納は、半導体メモリ２２０６を使用して実現されてもよく、ハードディスクドライブ２２１０との協働により行われてもよい。いくつかの例において、改竄防止アプリケーションプログラムは、それぞれ、破線２２２４で示すように、ＣＤ−ＲＯＭ２２２５上で、又は破線２２２３で示すように、フロッピディスク２２２２上で符号化され、且つ対応するドライブ２２１２又はドライブ２２１１を介して読み取られた状態でユーザに提供されてもよい。あるいは、改竄防止プログラムは、モデム装置２２１６を介してネットワーク２２２０からユーザにより読み取られてもよい。更に、改竄防止アプリケーションソフトウェアは、他のコンピュータ可読媒体からコンピュータシステム２２００内に読み込み可能である。本明細書で用いられる「コンピュータ可読媒体」とは、実行及び／又は処理のために、命令及び／又はデータを、コンピュータシステム２２００へ提供することに関わる任意の記憶媒体又は送信媒体である。記憶媒体の例には、フロッピディスク、磁気テープ、ＣＤ−ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、又はＰＣＭＣＩＡカード等のコンピュータ可読カードが含まれる。これらの装置は、コンピュータモジュール２２０１の内部又は外部のいずれに設けられてもよい。送信媒体の例は、無線送信チャネル又は赤外線送信チャネルと、別のコンピュータ又はネットワーク装置へのネットワーク接続回路と、ウェブサイト等に記録された電子メール送信及び情報を含むインターネット又はイントラネットとを含む。
【００４６】
改竄防止技法の好適な構成は、コンピュータシステム２２００のような汎用コンピュータシステム上で実行される１つ以上のソフトウェアモジュールとして実現される。しかしながら、改竄防止技法は、複合機等の埋め込み型システムの改竄防止アプリケーションソフトウェアモジュールとして実現されてもよい。また、改竄防止技法は、特定用途向け集積回路又はＦＰＧＡ（Field Programmable Gate Array）等の固定論理又はプログラマブル固体論理回路により実現されてもよい。
【００４７】
図２は、開示された改竄防止システムの機能ブロック図の一例を示す図である。図２は、不正顕示機能付文書１０５及び不正顕示機能付文書１０５’を作成する作成サブシステム１２６と、不正顕示機能付文書１０５及び不正顕示機能付文書１０５’が改竄されたか否かを検知する（妥当性検証を行う）妥当性検証サブシステム１２７とを有する。
【００４８】
不正顕示機能付文書１０５を作成する作成サブシステム１２６を考えると、選択モジュール１０４は、走査ベースの２値レベルソース信号１１７の値に応じて、２つの同期させた暗号信号１１５及び暗号信号１１６のうちの１つから選択する。信号１１７は、印刷されるべきソース情報であり、２値レベルソース画像１０１から導出される。それぞれ、暗号信号１１５は、暗号信号供給源１０２により生成されたストリーム暗号であり、暗号信号１１６は、暗号信号供給源１０３により生成されたストリーム暗号である。暗号信号供給源１０２は、鍵生成モジュール１３４からの矢印１３５で示すように、秘密鍵ベース情報を受け取る。暗号信号供給源１０３は、鍵生成モジュール１３４からの矢印１３６で示すように、秘密鍵ベース情報を受け取る。鍵生成モジュール１３４、暗号信号供給源１０２及び暗号信号供給源１０３の動作は、図６に関して更に説明される。ソース文書１０１が紙文書の形態である場合、スキャナ２２１８（図１を参照）を使用して、信号１１７を紙文書１０１から発生させることができる。ソース文書が電子文書形式（Adobe PDF等）である場合、信号１１７をラスタ画像プロセッサ（ＲＩＰ）から発生させることができる。ＲＩＰは、電子文書を、信号１１７を形成する画素に変換する。あるいは、ソース画像１０１が、メモリ（不図示）内にデジタル画像形態で格納された場合、信号１１７は、走査ベース方式でメモリから読み出すことができる。
【００４９】
ソース信号１１７を使用して、暗号信号１１５と暗号信号１１６との間からいずれかの信号を選択することにより、それぞれのルックアップテーブル１３０及びルックアップテーブル１３１と関連させて変調された合成暗号信号１１８を形成する。変調された合成暗号信号１１８は、ソース情報１０１の可視摂動バージョンである。本例において、ソース画像１０１は、黒画素及び白画素で合成された２値レベル画像である。一構成例によると、合成信号１１８は、「暗」画素及び「明」画素で合成された多値レベル画像を表現する。そのため、一例において、「暗」画素は、黒並びに完全な純色の赤、緑及び青のうちの１色であってもよい。「明」画素は、白、シアン、マゼンダ及びイエロのうちの１色であってもよい。
【００５０】
そのため、ソース画像１０１が２値レベルである本例において、２つの各暗号信号１１５及び暗号信号１１６は、それぞれのルックアップテーブル１３０及びルックアップテーブル１３１を介して、非暗号であり且つ相互に識別可能な主成分を有する信号と関連付けられる。信号１１５及び信号１１６のうちの他方と関連付けられた主成分は、常時、視覚的に暗い。一方、信号１１５及び信号１１６のうちの他方と関連付けられた主成分は、常時、視覚的に明るい。更に、２つの各暗号信号１１５及び暗号信号１１６は、それぞれのルックアップテーブル１３０及びルックアップテーブル１３１を介して、暗号副成分（例えば、色変化の形態をとる）と関連付けられる。
【００５１】
「非暗号」は、相互に識別可能な複数の主成分が、暗号を考慮せずに互いに区別できることを意味する。
【００５２】
多値レベル（Ｎ段階の異なる色調を有するＮ値レベル）文書において、Ｎ個の暗号供給源１０２，・・・，１０３が使用される。Ｎ個の各暗号供給源は、それぞれのルックアップテーブルを介して、暗号信号と関連付けられる。この暗号信号は、非暗号であり、且つ相互に識別可能なＮ個の主成分、及びＮ個の暗号副成分を有する。
【００５３】
図２の２値レベル文書の場合に戻ると、合成暗号信号１１８は、組み合わせモジュール１１４内で組み合わせ処理が実行される。生成された合成されたコンポジット信号１２２は、記録モジュール（図１のプリンタ２２１５等）により転送媒体上に記録され、本例においては、印刷不正顕示機能付文書１０５を形成する。転送媒体は、通常、印刷文書を形成するために使用される紙である。この場合、転送媒体を印刷媒体と呼ぶ。転送媒体の別の例は、銀塩フィルムである。また、合成されたコンポジット信号のデジタル転送も、可能である。
【００５４】
多くの場合、この説明における「文書」という用語は、合成されたコンポジット信号１２２がプリンタ（図１のプリンタ２２１５等）により印刷される印刷（転送）媒体を有する印刷文書のコンテキストにおいて使用されるが、文書という用語は、より一般的な意味を有する。従って、文書という用語は、合成されたコンポジット信号１２２が適切な光学処理及び／又は光学装置を使用して記録された銀塩フィルム（転送）媒体を有する記録文書等にも適用できる。
【００５５】
更に別の構成において、マーキング処理及び認証処理は、複数のデジタル文書画像の準備、格納、転送及び認証において使用されてもよい。この構成において、開示された改竄防止方法を内蔵するコンピュータアプリケーションは、まず、マーキング処理をデジタル文書画像に適用する。このデジタル文書画像は、走査処理の一部として作成された。しかしながら、このデジタル文書画像は、デジタル手段のみにより作成してもよい。その後、アーカイブ、送信、再符号化（異なるデジタル画像標準への変換等）、再サンプリング（画像スケーリング中に作成する）、及び圧縮又は再圧縮（ベースラインＪＰＥＧ圧縮等の所謂「非可逆」圧縮を含む）のうちの１つ以上の処理が、文書画像に対して実行される。これらの動作のうちの１つ以上の動作の後、コンピュータアプリケーションは、開示された認証処理、及び第２のコンピュータアプリケーションを使用して表示された結果を使用して、生成された画像を認証してもよい。上述のマーキング処理及び認証処理の使用は、画像変換により画像のデジタルビットパターン又は画像の符号化に重要な変化を施す場合においても、画像の出現に対して有効な可視変化を施さない画像変換に対してロバストである。
【００５６】
合成されたコンポジット信号１２２を構築する暗号信号１１５及び暗号信号１１６と関連付けられた主成分は、オリジナルのソース画像１０１を読み取り可能とした場合と同様の方法によって、人間又は機械が不正顕示機能付文書１０５を読み取ることを可能とする。ソース画像１０１内の情報に対する追加としての副摂動成分は、不正顕示機能付文書１０５内で可視であるが、この摂動が微小なため、人間（又は機械）の読み手又は読取り装置では認識されない。そのため、不正顕示機能付文書１０５は、ソース画像１０１から可視摂動が行なわれるが、ソース画像１０１と明確に等価である。換言すれば、印刷媒体上に印刷された場合に摂動されたソース情報は、人間又は機械により読み取り可能な状態である。
【００５７】
妥当性検証サブシステム１２７における位置決め処理のロバストさを改善するために、粗位置決め提供源１１１からの任意の視覚的に微弱な粗位置決め信号１２８は、組み合わせモジュール１１４により変調された合成暗号信号１１８上に重畳される。位置決めが（ａ）手動登録マーク方法又は（ｂ）精位置決め処理のみのいずれかに依存するため、粗位置決め信号は、任意である。十分な計算資源が利用可能な場合、精位置決め処理のみを使用して位置決めを実現することができる。尚、この方法では、検索を行う必要がある。開示された精位置決め処理は、手動粗位置決め方法又は別の粗位置決め方法を使用して十分に実行される。更に、複数の異なる不正顕示機能付文書１０５…，１０５’からの合成信号１２０の試験により、暗号信号１１５及び暗号信号１１６の潜在的な回復を防止するために、暗号信号１１５及び暗号信号１１６を生成する秘密鍵（図６のステップ２５０１を参照）は、２つの要素から作成される。第１の要素は、複数の文書１０５，・・・，１０５’のために固定される。この第１の要素は、文書１０５，・・・，１０５’の任意の１つに適用されるような妥当性検証サブシステム１２７により実行される妥当性検証処理に必要とされる。第２の要素は、ソルト生成器１１２からの「ソルト」値１２９と呼ばれる。ソルト値は、各文書１０５，・・・，１０５’（図６のステップ２５０８及びステップ２５０１を参照）に対して固有である。ソルト値の使用は、暗号法分野において公知の技法である。ソルト値１２９は、組み合わせモジュール１１４により各不正顕示機能付文書１０５，・・・，１０５’の変調された合成暗号信号１１８内にわずかに埋め込まれる。また、ソルト値１２９は、矢印１４２で示すように、鍵生成モジュール１３４に提供される。ソルト値１２９は、妥当性検証処理中に粗位置決め／ソルト回復モジュール１１３により再び回復できる。そのため、妥当性検証サブシステム１２７による不正顕示機能付文書１０５の妥当性検証処理は、秘密鍵及びソルト値１２９の（共通の）第１の要素を必要とする。ソルト値１２９は、秘密鍵の第２の要素と同様に、不正顕示機能付文書１０５に対して固有である。不正顕示機能付文書１０５’の妥当性検証処理は、秘密鍵及びソルト値の（共通の）第１の要素を必要とする。ソルト値は、秘密鍵の第２の要素と同様に、不正顕示機能付文書１０５’に対して固有である。
【００５８】
秘密鍵の共通の第１の要素１４０は、管理手段（例えば、オペレータに手動で妥当性検証サブシステム１２７に入力させるために渡された密封封筒内の第１の要素を提供する）等により妥当性検証サブシステム１２７に提供される。要素１４０は、矢印１４１で示すように、暗号信号供給源１０２’及び暗号信号供給源１０３’に提供される。各不正顕示機能付文書１０５からの妥当性検証サブシステム１２７は、秘密鍵の第２の文書固有要素を抽出できる。
【００５９】
改竄検知（妥当性検証とも呼ばれる）のために使用された妥当性検証サブシステム１２７に戻ると、走査ベース不正顕示信号１２０は、図１のスキャナ２２１８を使用して、作成サブシステム１２６により作成した不正顕示機能付文書１０５を走査することにより導出される。信号１２０は、主成分（オリジナル情報１１７を反映すると仮定される）及び副成分（選択モジュール１０４の制御下において、暗号信号１１５及び暗号信号１１６により導入されると仮定される）を含む。粗位置決め／ソルト回復モジュール１１３は、不正顕示機能付文書１０５の粗位置決めを実行し、「粗位置決め」走査ベース不正顕示機能付文書１２１を作成する。また、ソルトモジュール１１３は、信号１２０からソルト値を抽出し、矢印１３９で示すように、暗号信号供給源１０２’及び暗号信号供給源１０３’にソルト値を提供する。精位置決めモジュール１０６は、粗位置決め信号１２１の色成分と、同期させた暗号信号１１５’及び暗号信号１１６’、並びにルックアップテーブル１３４からの色１３８及びルックアップテーブル１３５からの色１３７を組み合わせる（すなわち、平均化する）ことにより作成された信号とを相関させる。尚、色１３７と色１３８とは、関連付けられている。図４に関してより詳細に説明するように、上記の組み合わされた暗号信号１１５’及び暗号信号１１６’、並びに色１３７及び色１３８は、暗号信号１１５’及び暗号信号１１６’のカラー画像バージョンを形成する。
【００６０】
信号１１５’は、暗号信号供給源１０２’からの暗号信号であり、信号１１６’は、暗号信号供給源１０３’からの暗号信号である。暗号信号供給源１０２’及び暗号信号供給源１０３’は、通常、暗号信号供給源１０２及び暗号信号供給源１０３から物理的に離間されているが、同一である。精位置決めモジュール１０６により実行された相関付けにより、粗位置決め不正顕示信号１２１と暗号信号１１５’及び暗号信号１１６’との間の精スケール同期（すなわち、位置決め）は、不正顕示機能付文書１０５内を人間又は機械が読み取り可能な強力な主成分と独立して実現される。この位置決めは、「精位置決め」走査ベース不正顕示信号１２３を形成する。
【００６１】
その後、妥当性検証サブシステム１２７における妥当性検証処理では、閾化モジュール１０７を使用して、精位置決め不正顕示信号１２３内に存在する複数の暗号信号の複数の主成分を識別することにより、２値レベル信号１１９を形成する。２値レベル信号１１９は、（オリジナル）２値レベル信号１１７と仮定される。ソース信号１１７がＮ値レベルである場合、仮定文書信号１１９は、Ｎ値レベル信号である。ソース信号１１７が２値レベルソースの本例では、文書信号１１９は、２値レベルである。次に、比較モジュール１０８において、１２３で示す信号と同一の信号である精位置決め不正顕示信号１２４は、選択モジュール１０９の制御下で、第１の暗号信号１１５’と関連付けられたルックアップテーブル１３４からの値、又は第２の暗号信号１１６’と関連付けられたルックアップテーブル１３５からの値のいずれかの値と比較される。選択モジュール１０９は、対応する走査位置の信号１１９の２値レベルの値に従って切り替えられる。選択モジュール１０９は、対応する走査位置の信号１１９の２値レベルの値に従って変調された合成暗号信号１２５を出力する。不正顕示機能付文書１０５からの信号１１９の副成分と、対応する変調された合成暗号信号１２５からの副成分とが一定の許容範囲内で一致しない複数の走査位置（画素位置と呼ばれる）は、妥当性検証信号モジュール１１０により（例えば、改変の導入を介して）改竄されたことが明らかにされる。
【００６２】
＜不正顕示機能付文書形成方法の詳細な説明＞
本実施例において、２値レベルソース画像１０１からの２値レベル信号供給源１１７は、デジタル形式の白黒文書画像を表現する。この（ソース）画像１０１は、ラスタ化処理（ＲＩＰ）提供元、走査提供元又は他の等価の提供元の出力として発信できる。不正顕示機能付文書１０５を作成するために、このソース画像１０１の導出を紙転送媒体上にマーキングすることにより、ソース画像１０１は、不正顕示機能付文書１０５となる。妥当性検証サブシステム１２７により実行される妥当性検証（すなわち、改竄検知）処理は、媒体（文書１０５に対して使用される）がオリジナルのソース画像１０１の各サンプルに対する３つ以上の識別可能な値を支持する必要がある。従って、オリジナルのソース画像１０１の解像度を、このような処理が実現されるように設定する必要がある。
【００６３】
不正顕示機能付文書１０５は、必要な情報を保持可能にするため、十分に高度な解像度を有する必要がある。例えば、プリンタがハーフトーン装置である場合、不正顕示機能付文書１０５は、装置画素の収集を利用して複数の識別可能な値を得る。
【００６４】
実現可能な空間解像度は、印刷技術と共に変化する。電子写真（レーザ）印刷技術及び熱インクジェット技術を含む多くの現代印刷技術に対して、オリジナルのソース画像１０１の解像度は、約２００ＤＰＩである。多くの場合において、より高度な解像度は、実現可能である。ソース画像１０１に対する解像度が低下すると共に、解像度は、徐々によりロバストになる（すなわち、印刷処理及び走査処理に固有の誤り及び劣化の許容度が高くなる）。しかしながら、解像度の品質は、明らかに低い。
【００６５】
暗号信号供給源１０２からの暗号信号１１５及び暗号信号供給源１０３からの暗号信号１１６は、ストリーム暗号から生成された２次元暗号フィールドから導出される。上述の構成において、暗号信号１１５及び暗号信号１１６は、５２ビット鍵を有するＲＣ４ストリーム暗号のマスタ・インスタンシエーションを使用して生成される。暗号信号１１５及び暗号信号１１６は、まず、単一のマスタＲＣ４ストリームから、暗号信号（１１５等）へ交互バイトを指向させ、且つ次に他の暗号信号（１１６等）へ指向させることにより生成される。他のストリーム暗号又は擬似ランダムシーケンス生成器は、異なる鍵長さで、交互に利用できる。別の技法の例は、一対の最大期間の線形フィードバックシフトレジスタを使用して、暗号信号１１５及び暗号信号１１６を生成することである。この例は、図６に関連してより詳細に説明する。
【００６６】
図３は、図２のシステムを使用して、開示された改竄防止方法に係る不正顕示機能付文書を作成する方法ステップのフローチャートとして、プロセス２３００を示す。プロセス２３００は、ステップ２３０１で開始する。ステップ２３０１では、ソース画像１０１からの次の画素を読み取る。その後、判断ステップ２３０２では、上記の画素値を判定する。この説明のバルクが２値レベルである場合、ステップ２３０１において読み取られた画素は、２つの可能な値のうちの１つを有する。しかしながら、一般に、ソース画像１０１は、Ｎ段階のレベルを有することが可能である。そのため、一般に、判断ステップ２３０２では、ステップ２３０１において読み取られた画素が、複数のＮ値のうちの１つの値を有することが可能であることを考慮すると、その画素は、そのうちのどの値を有するかを判定する。ステップ２３０２において、画素値がＢに等しいと判定された場合、プロセス２３００は、矢印Ｂに従って、ステップ２３０３へ進む。ステップ２３０３では、（ａ）画素値に従って暗号フィールドＢを選択し、（ｂ）次に、当該画素の位置に依存する上記の暗号フィールドから値を選択し、且つ（ｃ）最後に、多値レベル画素値を判定するために、暗号フィールドＢから選択された値を使用してルックアップテーブルＢを索引することにより、多値レベル画素値を判定する。続くステップ２３１１では、この画素値を格納する。その後、プロセス２３００は、判断（検査）ステップ２３０４へ進む。ステップ２３０４では、ソース画像１０１内で更なる画素が使用できるか否かが判定される。更なる画素が使用できる場合、プロセス２３００は、矢印ＹＥＳに従って、ステップ２３０１へ戻る。
【００６７】
判断（検査）ステップ２３０２へ戻ると、画素が値Ａを有すると判定された場合、プロセス２３００は、矢印Ａに従って、ステップ２３０５へ進む。ステップ２３０５は、ステップ２３０３と同様に機能する。その後、プロセス２３００は、ステップ２３１１へ進む。
【００６８】
判断ステップ２３０２へ戻ると、画素が値Ｃを有すると判定された場合、プロセス２３００は、破線矢印Ｃに従って処理ブロック（不図示）へ進む。処理ブロックは、ブロック２３０３及びブロック２３０５と等価である。ソース文書１０１がＮ段階のレベルを有する一般的な場合において、判断ステップ２３０２では、Ｎ通りの判断のうちの１つを行うことができる。
【００６９】
判断ステップ２３０４へ戻ると、更なる画素が使用できない場合、プロセス２３００は、矢印ＮＯに従って、ステップ２３０７へ進む。ステップ２３０７では、多値レベル画素データと粗位置決めマーク及びソルト値とを組み合わせる。その後、ステップ２３０８では、合成されたコンポジット信号を印刷媒体上に印刷する。ステップ２３０８の結果、破線矢印２３０９で示すように、不正顕示機能付文書１０５が得られる（図２を参照）。
【００７０】
図４は、図３の不正顕示機能付文書が改竄されたか否かを判定する方法ステップのフローチャートとして、プロセス２４００を示す。プロセス２４００は、ステップ２４１７で開始する。ステップ２４１７では、安全保証文書１０５を走査する。その後、ステップ２４０１では、粗位置決めマークを回復する。その後、ステップ２４０２では、回復された粗位置決めマークを使用して暗号フィールドに対して不正顕示機能付文書１０５の粗位置決めを行う。続くステップ２４２２では、文書１０５からソルト値を回復する。その後、ステップ２４０３では、不正顕示機能付文書１０５と暗号フィールドとの間の精位置決めを行う。精位置決めステップ２４０３は、３つのサブプロセスを有する。第１のサブプロセス２４０３Ａでは、図１５に関してより詳細に説明するように、ブロック相関付けを行うことにより、置換マップを形成する。第２のサブプロセス２４０３Ｂでは、図１７に関してより詳細に説明するように、置換マップに関して補間を行う。第３のサブプロセス２４０３Ｃでは、図１８に関してより詳細に説明するように、ワーピングを行うことにより、精位置決め文書を形成する。
【００７１】
次のステップ２４０４では、走査文書１０５の次の画素を読み取る。その後、判断（検査）ステップ２４０５では、２値レベルソース画像１０１に対して、画素の主成分が値Ａ又は値Ｂを有するか否かを検査する。図３に関して説明された場合と同様に、ソース画像１０１がＮ段階のレベルを有する場合、判断ステップ２４０５は、Ｎ回の判断ブランチを有する。
【００７２】
本例において、画素の主成分が値Ａを有する場合、プロセス２４００は、矢印Ａで示すように、ステップ２４０７へ進む。ステップ２４０７では、上記の画素位置の仮定副成分を判定する。この判定は、当該画素位置の暗号フィールドＡを考慮し、且つこの暗号フィールド値を使用して関連ルックアップテーブル（図２の１３０及び１３１を参照）を索引することにより行われる。この判定により、仮定副成分が生成される。その後、ステップ２４１７では、印刷文書１０５から当該画素位置の実際の副成分値を読み取る。続く判断ステップ２４０９では、ステップ２４０７からの仮定副成分値が、ある許容度の範囲内でステップ２４１７からの実際の読み取り副成分値に等しいか否かが確認される。仮定副成分値が実際の副成分値と等しくない場合、プロセス２４００は、矢印ＮＯに従って、ステップ２４１５へ進む。ステップ２４１５では、上記の画素位置において改竄が行われたことを宣言する。
【００７３】
判断ステップ２４０５へ戻ると、画素の主成分が値Ｂを有すると判定された場合、プロセス２４００は、矢印Ｂに従って、ステップ２４１１へ進む。ステップ２４１１は、ステップ２４０７と同様に、すなわち、当該画素位置の仮定副成分を判定するために、当該画素位置の暗号フィールドＢを参照し、且つ暗号フィールド値の使用により図２からの関連ルックアップテーブル１３０又はルックアップテーブル１３１を索引することによって機能する。その後、プロセス２４００は、ステップ２４１７へ進む。
【００７４】
判断ステップ２４０９へ戻ると、ステップ２４０７及びステップ２４０８からの仮定副成分が、受け入れ可能な許容範囲まで、ステップ２４１７の印刷文書からの実際の読み取り副成分に等しい場合、プロセス２４００は、矢印ＹＥＳに従って、ステップ２４１３へ進む。ステップ２４１３では、関心画素位置において改竄が検知されなかったことを宣言する。その後、プロセスは、矢印２４１４に従って、ステップ２４０４へ進む。プロセス２４００は、ステップ２４１５からもステップ２４０４へ進む。
【００７５】
＜２次元暗号フィールドの生成＞
図５は、２次元暗号フィールド（２次元暗号フィールドとも呼ばれる）の生成を表す図である。図５は、ストリーム暗号から２次元暗号フィールド３０６及び２次元暗号フィールド３０７を生成するための２つの方法を示す。暗号フィールドの生成は、図６に関して説明するプロセス２５００に従って、暗号信号供給源１０２及び暗号信号供給源１０３（図２を参照）により作成サブシステム１２６において、並びに暗号信号供給源１０２’及び暗号信号供給源１０３’により妥当性検証サブシステム１２７において行われる。
【００７６】
妥当性検証処理において暗号鍵データを使用するため、暗号フィールドを再生できるように、ストリーム暗号を２次元暗号フィールドに変換することが望ましい。特に、オリジナルのソース画像１０１の走査線の長さに依存することを回避することが望ましい。例えば、ストリーム暗号が、ラスタ順に単純に暗号フィールドに変換された場合、この走査線の長さへの依存は、引き起こされる。また、暗号フィールド３０６及び暗号フィールド３０７は、ラスタ順に生成されることが望ましい。暗号フィールド３０６及び暗号フィールド３０７は、ソース画像１０１の公称中心位置に対して生成される。この公称中心位置は、通常、画像１０１の空間的中心付近に位置決めされるが、必ずしも空間的中心付近ではない。
【００７７】
図５の暗号フィールド３０６を考慮すると、鍵Ｋ１（すなわち、鍵３０１）は、２つの暗号信号供給源（図２の暗号信号供給源１０２又は暗号信号供給源１０３）のうちの１つによる利用のために生成された第１の５２ビットシーケンスである。ストリーム暗号の次の５２ビットセグメントは、以前に生成された鍵（Ｋ１等）上における鍵位置（Ｋ２等）、及び以前に生成された鍵（Ｋ１等）下における鍵位置（Ｋ３等）に、交互に割り当てられる。このようにして、最初の５２ビットシーケンス鍵の中心スパイン（Spine）３０８は、生成される。スパイン３０８は、垂直方向の任意の所望の長さを有する。これらの各５２ビット鍵Ｋ１、Ｋ２、．．．、は、生成されるべき暗号フィールド３０６の水平走査線（走査線３０５等）と関連付けられる。
【００７８】
暗号フィールド３０６の任意の特定走査線（走査線３０５等）を生成するために、第２のＲＣ４暗号生成器は、その特定走査線と関連付けられた鍵を使用して初期化される。従って、例えば、３０２で示される鍵Ｋ４は、走査線３０５に関して使用される。連続多値ビット「Ｓ」値は、第２のＲＣ４暗号生成器から生成される。連続多値ビット「Ｓ」値は、その走査線上の以前に生成された「Ｓ」値の右の（Ｓ４１等における）「Ｓ」値及び次の左の（Ｓ４２等における）「Ｓ」値と交互に関連付けられる。各多値ビット「Ｓ」値は、暗号フィールド３０６内に値（Ｓ４２等）を形成する。マスタ暗号ストリームとの同期を維持するために、信号供給源１０２及び信号供給源１０３と関連付けられた２つの暗号フィールド３０６及び暗号フィールド３０６’（後者は不図示）は、同時に生成される。
【００７９】
スパイン３０８は、暗号フィールド３０６及び暗号フィールド３０６’を形成するために使用される。しかしながら、スパイン３０８は、暗号フィールド自体の一部を形成するものではない。暗号フィールド３０６及び暗号フィールド３０６’は、「Ｓ」値のみにより構成される。スパイン３０８（すなわち、「Ｋ」値）は、５２ビット鍵で構成される。「Ｓ」値（暗号フィールドを形成する）は、本例において２ビット値である。
【００８０】
暗号フィールドを発生させる他の方法は、可能である。符号３０７は、別の暗号フィールドを示す。別の暗号フィールドにおいて、符号３０３は、ラスタグリッド３０４を埋め込む別の渦巻ベース構成の開始を指示する。この構成３０７は、単一のストリーム暗号エンジンのみを必要とする点で有用であるが、いくつかの実現例においては特殊バッファリングを必要とする。
【００８１】
暗号フィールド３０６及び暗号フィールド３０７の絶対サイズは、必ずしもソース文書１０１の大きさと同一ではないが、暗号フィールドのＳ値は、ソース画像１０１の画素と「合同」であるとする。この合同において、ソース画像１０１の各画素と、暗号信号供給源１０２及び暗号信号供給源１０３により出力された暗号フィールドの対応するＳ値との間に固有の１：１対応が成立するようにする。改竄防止方法を行うために、妥当性検証サブシステム１２７により行われた位置決めは、この合同を再確立する。
【００８２】
図６は、図５の暗号フィールドのうちの１つを生成する方法ステップのフローチャートとして、プロセス２５００を示す。プロセス２５００は、図２に関して説明されたように、鍵生成モジュール１３４及び暗号信号供給源Ａ（すなわち、暗号信号供給源１０２）により実現される。鍵生成モジュール１３４へ戻ると、図６の第１のステップ２５０８では、ソルト値が生成される。ステップ２５０８の破線アウトラインで示すように、ステップ２５０８は、任意のステップである。その後、ステップ２５０１では、ステップ２５０８のオプションが選択された場合、ソルト値を使用して５２ビット秘密鍵を生成する。続くステップ２５０２では、ＲＣ４暗号ストリームを生成する。次のステップ２５０３では、矢印１３５で示すように、連続する５２ビットバイトの暗号ストリームを、暗号信号供給源１０２等の連続する暗号信号供給源に割り当てる。矢印１３６は、交互の５２ビットバイトが信号供給源１０３へ指向されることを示す。
【００８３】
信号供給源１０２において、第１のプロセスステップ２５０４では、図５に関して説明されたように、鍵生成モジュール１３４から受け取られた連続する５２ビットバイトを、暗号フィールドのスパイン位置に割り当てる。その後、ステップ２５０５では、スパイン位置ごとに、関連走査線に対してＲＣ４ストリーム暗号を生成する。次のステップ２５０６では、走査線ストリーム暗号ごとに、連続する２ビットバイトを走査線上の連続する画素位置に割り当てる。その後、ステップ２５０７では、２ビット暗号フィールド値が出力される。
【００８４】
＜オリジナル画像と暗号フィールドとの結合＞
尚、図２に戻り、特に、選択モジュール１０４の動作に関して、選択動作（図３の対応するステップ２３０２、ステップ２３０３及びステップ２３０５を参照）として、まず、暗号供給源１０２及び暗号供給源１０３からの２つの暗号フィールド、並びにソース画像１０１からのオリジナル画像は、暗号フィールド及びオリジナル画像の公称中心位置上に位置決めされる。選択段階（図３のプロセス２３１２に対応）において、位置決め位置の選択は、公称である。しかしながら、選択された位置決め位置は、不正顕示機能付文書１０５内へロックされ且つ符号化された状態となり、妥当性検証サブシステム１２７による回復処理（図４を参照）における位置決めのベースを形成する。
【００８５】
好適な構成において、暗号信号供給源１０２及び暗号信号供給源１０３（図２を参照）により生成された２つの各２次元暗号フィールド（暗号フィールド３０６（図５を参照）等）内の各値は、２ビット精度を有する。そのため、説明される例において、ソース情報１１７は、１ビット精度を有する２値レベルである。一方、不正顕示機能付文書１０５は、各々が２ビット精度を有する２組の４値レベルを有する。２組の４値レベルは、各ソース文書画素の対応する印刷形態に対して合計８つの可能な状態を与える。暗号信号（図２の暗号信号１１５及び暗号信号１１６等）が各入力画素（図２のソース画像１０１からの信号１１７において）に関するので、各暗号信号に対する状態（すなわち、この例では振幅解像度）の数は、変化する。好適な構成は、４つの状態（そのため、２ビットである）を使用するが、２つ以上のいずれの状態の数であっても効果的である。
【００８６】
偽造者が、画素値を黒から白へ、又は白から黒へ変化させる場合、暗号値１１５及び暗号値１１６に対して使用する状態の数の選択は、不正顕示機能付文書１０５上の印刷画素の副信号の正しい値を「推測」する偽造者の能力に影響を及ぼす。本例における２ビットの選択が、偽造者が７５％の時間を誤って推測する可能性があることを意味するので、その選択は、画素集合が小さい場合においても、偽造の強力な指示を提供できる。
【００８７】
多値レベル（すなわち、１画素当たり２ビット以上を有する）不正顕示機能付画像組み合わせ信号１２２（図２を参照）は、関連暗号信号供給源１０２及び関連暗号信号供給源１０３により出力された対応する暗号フィールドからの関連暗号信号値１１５又は関連暗号信号値１１６を使用して、それぞれのルックアップテーブル１３０及びルックアップテーブル１３１を索引することにより、オリジナルのソース画像１０１の画素ごとに生成される。好適な構成において、不正顕示機能付文書１０５を印刷するために使用された出力装置は、プリンタ２２１５である。本例では、プリンタ２２１５は、カラープリンタである。不正顕示機能付文書１０５上の多値レベル画像は、本実施例において、２４ビットＲＧＢ画像である。
【００８８】
図７は、暗号信号供給源１０２及び暗号信号供給源１０３、並びに信号供給源１０２及び信号供給源１０３のそれぞれのルックアップテーブル１３０及びルックアップテーブル１３１（図２を参照）に関連して、選択モジュール１０４が動作する方法の特定例４０６を示す図である。プロセス４０６では、ソース情報１１７内の２値レベル画素値を、変調された合成暗号信号１１８（図２を参照）内の多値レベル画素値に変換する。矢印２３１５（図３を参照）は、ステップ４０１へリードする。ステップ４０１では、オリジナルのソース画像１０１の画素を考慮する。考慮中の画素が黒である場合、プロセス４０６は、矢印「Ｙｅｓ」に従って、ステップ４０２へ進む。ステップ４０２では、Ｂ（黒）暗号フィールドより、考慮中の画素と関連付けられた暗号フィールド内の位置から２ビット値を選択する。しかしながら、画素が白である場合、プロセス４０６は、矢印「Ｎｏ」に従って、ステップ４０３へ進む。ステップ４０３では、Ｗ（白）暗号フィールドより、考慮中の画素と関連付けられた位置から２ビット値を選択する。ステップ４０１〜ステップ４０３は、それぞれの暗号供給源１０２（図２を参照）からの暗号信号１１５と、暗号供給源１０３（図２を参照）からの暗号信号１１６との間の選択を行う選択モジュール１０４により実行される。
【００８９】
考慮中の画素が黒である場合、ステップ４０２において暗号フィールド「Ｂ」から選択された２ビット暗号値を使用して、差分ルックアップテーブル４０４を索引する。ルックアップテーブル４０４内の画素は、全て、黒又は何らかの暗色のいずれかである。好適な構成において、この画素には、黒並びに完全な純色の赤、緑及び青が使用される。考慮中の画素が白である場合、ステップ４０３において暗号フィールド「Ｗ」から選択された暗号値を使用して、差分ルックアップテーブル４０５を索引する。ルックアップテーブル４０５内の画素は、全て、白又は何らかの明色のいずれかである。好適な構成において、この画素には、白、シアン、マゼンダ及びイエロが使用される。これらの色が使用されるのは、人間の目又は自動ビデオ抽出技法の使用のいずれによっても、視覚的な相互識別が容易であるためである。この色選択の結果、ロバストな妥当性検証システム１２７が得られる。しかしながら、この色選択では、他の色が使用されてもよい。ルックアップテーブル４０４及びルックアップテーブル４０５は、図２のルックアップテーブル１３０及びルックアップテーブル１３１の特定例である。
【００９０】
例えば、ステップ４０２において、Ｂ暗号フィールドから暗号値「１０」が発生した場合、この値「１０」は、「１０」における（ＲＧＢ）ルックアップテーブル４０４を索引する。これにより、赤（Ｒ）チャネルがＦＦ（１６進法において）であり、緑（Ｇ）チャネルが００であり、且つ青（Ｂ）チャネルが００である出力が得られる。この出力は、赤の出力に等しい。
【００９１】
ステップ４０１〜ステップ４０５では、ステップ２３１１（図３を参照）において格納された多値レベル画素値を発生させる。その後、プロセス４０６は、矢印２３１４（図３を参照）に従って、処理を進める。
【００９２】
また、非色ベース方式も使用できる。例えば、完全なグレースケール方式において、セキュリティ文書に対して印刷及び走査が行われた後、大多数の場合に異なる階調間を識別可能であれば、この異なる階調を使用できる。別の使用可能な方法は、各ソース文書画素に対応するセル内の２値レベル（通常、黒及び白）装置画素の１組の小パターンである。小パターンのうちの１つは、暗号フィールドの各状態を示す。
【００９３】
図８は、２値レベル画像７０１（図２のソース画像１０１と関連付けられた２値レベル画像等）の多値レベル画像７０５（不正顕示機能付文書１０５と関連付けられた多値レベル画像等）への変換の描画表現を示す図である。オリジナル画像７０１（図２のソース画像１０１の特定例）は、画素単位ベースで選択モジュール７０４（図２の選択モジュール１０４の特定例）を制御するために使用される。
【００９４】
選択モジュール７０４は、画像７０１からの画素値７０６により制御された１画素ベースで、２つの暗号フィールド由来カラーグリッド７０２及び暗号フィールド由来カラーグリッド７０３の色オプションから選択する。カラーグリッドは、次のようにして生成される。「黒」色グリッド７０２内の画素位置７０７に対する画素値は、「黒」暗号フィールド（不図示）内の上記の画素位置７０７に対する対応する暗号値を使用して判定される。黒暗号フィールドは、対応する暗号供給源１０２により生成された暗号フィールド１１５の特定例である。黒暗号フィールドからの上記の暗号値は、図７のテーブル４０４と同様に、対応するルックアップテーブル（不図示）内に多値レベル色値を索引するために使用される。「白」色グリッド７０３内の画素位置７０７’に対する画素値は、「白」暗号フィールド（不図示）内の上記の画素位置に対する対応する暗号値を使用して判定される。これにより、図７のテーブル４０５と同様に、対応するルックアップテーブル（不図示）内に多値レベル色値を索引する。
【００９５】
オリジナル画像７０１内の画素位置７０８における画素値が白であるため、選択モジュール７０４は、不正顕示機能付画像７０５内の画素位置７０８’において挿入されるべきカラーグリッド７０３内の画素位置７０７’の色値を選択する。
【００９６】
複数の画素７０９は、改竄検知に関して図１９に関連させて説明される。
【００９７】
＜粗位置決めマーク＞
図９は、粗位置決めに使用された２次元線形波形関数の２値レベル表現を示す図である。図２の妥当性検証サブシステム１２７において使用された精位置決めモジュール１０６により行われた精位置決めを支援するために、図９の波形関数を使用した粗位置決めマークは、粗位置決め提供元１１１及び組み合わせモジュール１１４により合成暗号信号１１８内に組み込まれる。これにより、不正顕示機能付文書１０５（図２を参照）上に印刷された多値レベル画像を形成する。好適な構成において、図９に示す関数を使用した微弱な粗位置決めパターン画像は、組み合わせモジュール１１４により、変調された合成暗号信号１１８（図２を参照）と混合される。この画像混合は、変調された合成暗号信号１１８内の各画素値の１つ以上のカラーチャネルに適切な値を加算することにより、あるいは、カラーチャネルから適切な値を減算することにより、行われる。加算量は、非常に小さいため、妥当性検証処理１２７において閾化モジュール１０７により行われる複数の色間の識別に影響を与えない。位置決めパターンは、図９に示す複数の１次元スケール不変関数の特定構成から形成される。１次元スケール不変関数は、フーリエ法を使用して効率的に検出できる。選択された１次元スケール不変関数の特定構成は、関数の対称軸が、アフィン変換下において不変である一定長さ比を有する線セグメントを規定する点で交差するように選択される。アフィン変換は、図１２に関して、特に、ステップ１７９０に関して、更に説明される。
【００９８】
位置決めパターン画像は、図９に示すように、４つの１次元スケール不変パターンの重ね合わせである。１次元スケール不変パターンは、横方向に延在して図２のソース画像１０１を被覆する。単一の１次元スケール不変パターンは、数学的に次式により表される。
2006014280.tif 000003
ここで、γは、パターン振動速度を特定する定数であり（パターン振動の高速化と共に、距離５０１は短縮される）、ｘ０は、パターンに対する対称線５０２を特定する。
【００９９】
図１０は、図９に示した線形波形関数のグラフィック表現を示す図である。尚、横方向に延在した１次元スケール不変パターンは、２つのパラメータ、すなわち、パターン半径ｒ及びパターン角度αにより特定される。このようなパターンの２次元関数形態（図９に示す）は、数学的に次式により表される。
2006014280.tif 000004
ここで、ｒ（図９の半径５０３を参照）は、パターン半径であり、α（図９の角度５０４を参照）は、パターン角度である。
【０１００】
所望の位置決めパターン（図２の信号１２８において）を形成するために重ね合わせされた４つの１次元スケール不変パターンは、１次元スケール不変パターンに、相互に関連した特定の空間的構成（図１１を参照）を与えるｒパラメータ値及びαパラメータ値を有する。特定の空間的構成は、位置決めパターン１２８が組み込まれた不正顕示機能付文書１０５の位置決めを判定する際に好都合である。この空間的構成は、図１１において表現される。
【０１０１】
図１１は、配列検出の際に使用された複数の線形波形関数に基づく対称軸の構成を示す図である。図１４に関して更に説明されるように、これらの対称軸を確立するパラメータの組は、特に、対称軸が、アフィン変換下において不変である一定長さ比（比１１０１：１１０２により例証される）を有する線セグメントを規定するように選択される。
【０１０２】
好適な構成において、オリジナルのソース画像１０１は、幅（ｘ）寸法及び高さ（ｙ）寸法の両方において、少なくとも１，０２４画素の最小画素寸法を有する。しかしながら、最小画素寸法は、いずれか又は両方の寸法において、より大きくてもよい。この最小画素寸法は、以下の式において、Ｎｍｉｎとする。一般に、ソース画像１０１は、幅Ｎ画素及び高さＭ画素の寸法を有する。この場合、Ｍ≧Ｎｍｉｎ且つＮ≧Ｎｍｉｎである。位置決めマーク１２８を形成するために使用された４通りのパターンに対するパターンパラメータｒ値及びパターンパラメータα値は、次式により表される。
2006014280.tif 000005
ここで、
2006014280.tif 000006
である。
【０１０３】
また、ナイキスト半径ＲＮＹＱも、特定される。ナイキスト半径は、パターン対称軸に基づく画素数である。この場合、パターン周波数は、画像のナイキスト周波数に等しい。対称軸から第１の可視波形までの距離は、ナイキスト周波数を表す。
【０１０４】
ｊ番目のパターンに対して、パラメータｒｊ及びパラメータαｊを使用すると、中間量Ｄｊ、Ｘｊ、Ｙｊ及びＲｊは、
2006014280.tif 000007
のように事前に算出される。
【０１０５】
オフセット（ｘ，ｙ）における画素に対するｊ番目のパターンの「影響」Ｐｊ（ｘ，ｙ）は、
2006014280.tif 000008
により与えられる。
【０１０６】
改竄防止方法を効果的に実行可能とした状態で、ソース画像１０１が受け入れ不可能な程度まで変形されることを防止するために、パターン影響を使用して、位置決め信号１２８及びソルト信号１２９を適切にスケーリングする。
【０１０７】
＜ディクショナリ攻撃防止のためのソルト値加算＞
図２へ戻ると、同一の暗号鍵（図６のステップ２５０１により生成された鍵等）が２ページ以上の不正顕示機能付文書１０５を生成するために使用された場合、暗号信号供給源１０２及び暗号信号供給源１０３により生成された暗号フィールド１１５及び暗号フィールド１１６は、文書１０５の異なるページから明領域及び暗領域を採取することにより潜在的に発見できる。この可能性を防止するために、好適な構成では、ソルト生成器１１２により提供されるソルト値を採用する。ソルトは、ディクショナリ攻撃を防止するための暗号法の分野において知られる技法である。ソルト技法は、このように、不正顕示機能付文書１０５の異なる２ページ上の暗号ストリームの類似性に基づいた攻撃を防止する場合においても使用できる。
【０１０８】
好適な構成において、例えば、図６のステップ２５０１により生成された鍵は、不正顕示機能付文書１０５の生成器（すなわち、作成サブシステム１２６のユーザ）及び不正顕示機能付文書１０５の妥当性検証者（すなわち、妥当性検証サブシステム１２７のユーザ）によく知られていることが望ましい。しかしながら、不正顕示機能付文書１０５の２ページに対する暗号ストリームの類似性に基づいた攻撃を防止するために、不正顕示機能付文書１０５の各ページに対して異なる鍵を使用する必要がある。これらの両方の目的を達成するために、好適な実施の形態では、鍵を２つの要素で形成する。例えば、４０ビットの長さの鍵の第１の要素は、作成サブシステム１２６及び妥当性検証サブシステム１２７の両方によく知られる。この第１の要素は、不正顕示機能付文書１０５の各ページに対して同一である。鍵の残る要素、すなわち、この例では１２ビット長さのソルトは、不正顕示機能付文書１０５の各ページに対して異なる。このソルトは、不正顕示機能付文書１０５の各ページに対して暗号的に（すなわち、「乱」数を効果的に使用して）生成される。ソルト値は、暗号化されない状態で関連ページ内に埋め込まれる。図６のステップ２５０１により生成された実際の５２ビット鍵は、固定４０ビットと１２ビットソルトとの連接結果である。この実際の５２ビット鍵は、作成サブシステム１２６の各信号１１５及び信号１１６、並びに妥当性検証サブシステム１２７の各信号１１５’及び信号１１６’に対して使用されたものである。
【０１０９】
暗号的に（ランダムに）生成された１２ソルトビットは、２つの６ビット部分Ｓａ及び６ビット部分Ｓｒに分割される。それぞれ、６ビット部分Ｓａは、図９に示すスケール不変パターンと類似する第５のスケール不変パターンの角度を表し、６ビット部分Ｓｒは、図１１に示すスケール不変パターンと類似する第５のスケール不変パターンの位置を表す。Ｓａ及びＳｒの両方には、６４個の異なる値を仮定できる。特定角度及び特定位置を有するこの第５のスケール不変パターンが、信号１１８内に埋め込まれることにより、作成サブシステム１２６の不正顕示機能付文書１０５は、形成される。妥当性検証サブシステム１２７は、この第５のスケール不変パターンを抽出することにより、パターンの関連角度及び関連位置を判定する。この角度及び位置は、２つの６ビットソルト値部分を確立する。第５のスケール不変パターンは、特に、他の４つのパターンに対して説明した方法と同様の方法で埋め込まれるが、振動定数γが異なる場合を除く。
2006014280.tif 000009
ここで、パラメータは、
2006014280.tif 000010
により計算される。
【０１１０】
第５のスケール不変パターンの異なる振動定数の選択は、ソルト値と粗位置決めパターンとの間の検知空間におけるある程度の分離を引き起こす。干渉は、粗位置決めマークにおいて使用された角度に近似する特定角度を無効にすることにより、更に低減させることが可能である。
【０１１１】
＜粗位置決めとソルトパターンとの組み合わせ＞
図２の組み合わせモジュール１１４の機能へ戻ると、位置決めパターン及びソルトパターンにより引き起こされたネット影響は、次式の合計
2006014280.tif 000011
により判定される。
【０１１２】
この値は、−５から５までの範囲で変化する。次に、この値は、−１５から１５の範囲までスケールアップされ、組み合わせモジュール１１４により、変調された合成暗号信号１１８の各チャネルに直接加算される。変調された合成暗号信号１１８は、多値レベルＲＧＢ画像であり、０．．．２５５の範囲まで結果をクランピングする。このスケーリング演算は、文書１０５内のオリジナルのソース情報１０１を過度に摂動させない状態で、粗位置決めマーク及びソルト値を文書１０５から抽出することを可能とする。
【０１１３】
＜マーキング処理の結果＞
図２の信号１２２における最終の多値レベル画像は、カラープリンタ２２１５を使用して不正顕示機能付文書１０５上に印刷される。カラープリンタ２２１５は、例えば、Ｃａｎｏｎ  ＩＲ  Ｃ３２００電子写真複合機又はＣａｎｏｎ  ｉ９５０熱インクジェットプリンタであってもよい。プリンタ解像度に対する２００ＤＰＩ画像のスケーリングは、単純な画素複製を使用して実現されることが好ましい。例えば、Ｃａｎｏｎ  ＩＰ  Ｃ３２００は、６００ＤＰＩの装置解像度を有する。このプリンタでは、最終の多値レベル画像の各２００ＤＰＩ画素は、Ｃａｎｏｎ  ＩＰ  Ｃ３２００装置画素の３×３グループ内に複製される。
【０１１４】
組み合わせモジュール１１４により行われたマーキング処理の結果は、オリジナル２値レベルデジタル画像１０１の黒値及び白値に対応する明領域及び暗領域の効果により、人間が読み取り可能な印刷文書１０５である。このマーキングの例は、図８に示される。
【０１１５】
尚、図８へ戻ると、それぞれ、画素位置７０７’等の明領域及び画素位置７０７等の暗領域は、各々が副成分を含む。それぞれの副成分は、画素位置７０７’における単方向断面線、及び画素位置７０７における双方向断面線により示される。これらの副成分を生成する鍵が非存在中の副成分は、有用な情報を含まず、この副成分の偽造は、困難である。しかしながら、２つの副成分の存在間に正確な相関性は存在し、各画素の全体の暗度及び明度は、それぞれ、各画素における主成分を表現する。それぞれの主成分及び副成分の知識を有する検査者は、この相関性の存在又は不足を認証できる。偽造者が関連副成分を相応に変化させることはできないため、偽造者は、画素（すなわち、主成分に対する）を明領域から暗領域へ（又は暗領域から明領域へ）適切に変化させることができる可能性は少ない。偽造者が、既定の画素位置における別の主成分に対する副成分の値を知らないため、偽造者は、相関性を維持することができない。
【０１１６】
＜認証処理＞
図２の妥当性検証サブシステム１２７へ戻ると、まず、カラースキャナ２２１８（図１を参照）により、認証されるべき不正顕示機能付文書１０５を走査することにより、２４ビットＲＧＢ不正顕示信号１２０を発生させる。スキャナ２２１８の走査解像度は、オリジナル画像１０１の解像度より高いか、又は画像１０１の解像度に等しいことが要求される。好適な構成において、２００ＤＰＩオリジナル画像１０１（図２を参照）の全体にわたり大きなマージンを提供する６００ＤＰＩスキャナ２２１８は、使用される。
【０１１７】
＜粗位置決め処理の概要＞
図２の粗位置決め／ソルト回復モジュール１１３の動作へ戻ると、粗位置決めパターン（本実施例において、組み合わせモジュール１１４により、わずかに不正顕示機能付文書１０５の印刷前の信号１１８に加算された４つの位置決めマークを有する）に検出及び解析を施すことにより、走査文書１２０の方向を暗号フィールドと関連付けるアフィン変換を発生させる。
【０１１８】
図１２は、図２の粗位置決め／ソルト回復モジュール１１３により行われた図４の粗位置決め処理２４１９を示す図である。走査不正顕示信号１２０の輝度チャネルの形態の走査文書は、ステップ１７１０において、まず、幅及び高さの最小値が２５６画素から５１１画素の範囲内になるように調整されるまで、生成された画像が、連続半減処理により、リサイズされる。半減処理は、信号１２０の形態の画像を低域フィルタで畳み込み、且つ畳み込みの結果を間引くことにより行われてもよい。
【０１１９】
次に、生成されたリサイズ画像は、ステップ１７２０において、２次元高速フーリエ変換（ＦＦＴ）が施される。この結果は、ステップ１７３０において、準極周波数空間中に再サンプリングされる。ステップ１７３０では、バイキュービック補間を使用してＦＦＴを極グリッド上に再サンプリングすることにより、ステップ１１７２０から２次元ＦＦＴの極変換を直接使用できる。この方法は、演算が単純な一方で、検知に悪影響を及ぼす可能性のあるアーテファクトを発生させる。ステップ１７３０において使用された好適な準極方法は、図１３に関して説明される。
【０１２０】
ステップ１７２０においてＦＦＴを計算する前に、画像縁部に近接する画像値（強度）は、まず、減衰されることが好ましい。この減衰は、画像値が、画像縁部に向かうと共に徐々に且つスムーズにゼロにフェードするように行われる。ステップ１７３０では、水平列が、ステップ１７２０で得られた２次元ＦＦＴにおける半径スライスに対応する複素画像を作成する。角度スペーシング及び半径スケーリングは、一定である必要はない。
【０１２１】
ステップ１７５０において、ステップ１７４０により与えられた１次元基底関数の１次元フーリエ変換は、実行される。ステップ１７４０により与えられた基底関数は、数学的に次式により表される。
2006014280.tif 000012
この式は、式（１）の複素バージョンである。そのため、γは、パターン振動速度を特定する定数であり、 は、パターンに対する対称点を特定する。あるいは、ステップ１７４０の基底関数は、数学的に変換できる。すなわち、式（９）のフーリエ変換の解析解導出後、この解を使用することにより、フーリエ変換１７５０を直接発生させることができる。
【０１２２】
次に、ステップ１７５０から得られた基底関数の変換は、ステップ１７６０において、画素単位で、全ての角度値に対する水平列（２次元ＦＦＴの半径線を表現する）に沿ったステップ１７３０の出力値の複素共役で乗算される。その後、生成された複素画素値は、ステップ１７６０により、複素画素値が大きくとも単位大きさを有するように基準化される。次に、ステップ１７７０では、水平列に沿ったステップ１７６０の出力の１次元逆高速フーリエ変換（ＩＦＦＴ）を判定する。
【０１２３】
ステップ１７７０の結果、図２の走査文書信号１２０内の１次元基底関数（すなわち、４つの位置決めマーク）の方向及びスケールに対応する画像の大きさにピークを有する複素画像が得られる。これらのピークは、ピーク検出処理１７８０（図１４に関してより詳細に説明される）を使用して検出される。最後に、ステップ１７９０において、ステップ１７８０で検出されたピークの位置を使用して、図２の信号１２０における走査文書を、図２の暗号フィールド１１５’及び暗号フィールド１１６’のデジタル形態と関連付けるアフィンパラメータを判定する。
【０１２４】
ステップ１７９０において、交点のアフィン変換に最小二乗適合度を与える４つのピークの結合に対応するアフィン変換は、図２の信号１２０における走査文書の方向を図２の暗号フィールド１１５’及び暗号フィールド１１６’の方向と関連付けるアフィン変換として選択される。最小二乗適合度の詳細は、後述される。
【０１２５】
次に、図４のステップ２４０２において、アフィン変換が使用され、バイキュービック補間を使用して走査文書が変換される。走査文書の変換により、粗位置決め走査文書を表す信号１２１（図２を参照）が形成される。この文書は、本例において、約６００ＤＰＩの解像度を有する。
【０１２６】
＜準極マッピング処理の詳細＞
前述の構成において、粗位置決めに対する不変パターンマッチングを行う好適な方法では、チャープＺ変換を使用してステップ１７２０により行われるフーリエ変換の準極変換（図１２のステップ１７３０を参照）を提供する。チャープＺ変換は、信号のフーリエ変換のスケーリング部分を計算するための方法である。
【０１２７】
図１３は、図１２のステップ１７３０をより詳細に示す図である。図１３は、フーリエ変換の準極マッピングを算出するための準極変換を行うプロセスである。ステップ１８１０において、図１２のステップ１７２０により出力された大きさ（Ｘ，Ｙ）を有するリサイズ画像１８０１は、２つのコピーＩ１（符号１８０２により示される）及びコピーＩ２（符号１８０３により示される）として複製される。ステップ１８２０において、第１のコピーＩ１を、幅Ｗ＝２＊ＭＡＸ（Ｘ，Ｙ）までＸ方向にゼロでパディングすることにより、大きさ（Ｗ，Ｙ）の画像１８０４を得る。パディングは、コピーＩ１の列オフセット
2006014280.tif 000013
が、パッド画像１８０４の列オフセット
2006014280.tif 000014
に対応するように行われる。
【０１２８】
ステップ１８３０において、第２のコピーＩ２を、高さＷまでＹ方向にゼロでパディングすることにより、画像１８０５を形成する。ステップ１８４０において、画像１８０５を９０°回転させることにより、大きさ（Ｗ，Ｘ）の画像１８０６が得られる。パディングは、コピーＩ２の行オフセット
2006014280.tif 000015
が、パッド画像１８０６の行オフセット
2006014280.tif 000016
に対応するように行われる。
【０１２９】
ステップ１８５０及びステップ１８６０において、画像１８０４及び画像１８０６を、各行の１次元フーリエ変換計算により変換することにより、それぞれ、画像１８０４の変換画像１８０７及び画像１８０６の変換画像１８０８を形成する。
【０１３０】
ステップ１８７０及びステップ１８８０において、画像１８０７及び画像１８０８を、各列の個別のチャープＺ変換計算により変換することにより、それぞれ、画像１８０７の変換画像１８０９及び画像１８０８の変換画像１８１１を形成する。
【０１３１】
ステップ１８７０及びステップ１８８０により行われた各チャープ変換を行うことにより、それぞれのステップ１８７０及びステップ１８８０の列の範囲内の位置
2006014280.tif 000017
における各列の中心位置を保存する。
【０１３２】
ステップ１８７０及びステップ１８８０における各列 に対するスケーリング係数は、
2006014280.tif 000018
であり、各スケール係数ｍｚは、垂直フリップに対応する
2006014280.tif 000019
である場合、負の数となる。また、
2006014280.tif 000020
である場合、スケーリング係数は規定されない。この場合、中心画素位置は、列全体にわたり複製される。
【０１３３】
不正顕示機能付文書１０５からの正方形画像を仮定すると、変換画像１８０９及び変換画像１８１１は、リサイズされ、ウィンドウ化され、且つ変換画像１８０９及び変換画像１８１１を有する入力画像のフーリエ変換の準極変換を表現する。変換画像１８０９は、［−π／４．．π／４］ の範囲内の角度を有し、変換画像１８１１は、［π／４．．３π／４］の範囲内の角度を有する。不正顕示機能付文書１０５からの画像が矩形である場合、角度の範囲は、［−ａｔａｎ２（Ｙ，Ｘ）．．ａｔａｎ２（Ｙ，Ｘ）］及び［ａｔａｎ２（Ｙ，Ｘ）．．π−ａｔａｎ２（Ｙ，Ｘ）］から変化する。準極変換の各行が、正半径及び負半径を含むため、各行は、全て［０．．２π］ラジアンの範囲内の角度を有する。
【０１３４】
ステップ１８９０において、画像１８１２の上部に画像１８０９の画素を複製し、且つ画像１８１２の下部に画像１８１１の画素を複製することにより、２つの入力画像１８０９及び入力画像１８１１を結合して、（Ｗ，Ｙ＋Ｘ）寸法の画像１８１２を形成する。
【０１３５】
＜ピーク検出処理の詳細＞
図１４は、図１２のピーク検出処理１７８０の一例を示す流れ図である。図１２のステップ１７７０の結果、図２の走査文書信号１２０内の１次元基底関数（すなわち、４つの位置決めマーク）の方向及びスケールに対応する画像の大きさにピークを有する複素画像は、得られる。そのため、ピーク検出ステップ１７８０への入力は、上記の複素画像である相関画像１６１０で示される。複素画像において、Ｐ個の最大ピーク（好適な構成において、Ｐは６４である）の位置の決定が所望される。換言すれば、Ｐ個の最大ピークは、相関画像の大きさのＰ個の最大局所極大である。
【０１３６】
ピークは、多数のピークが相互に近接集合したノイズのある領域において発生する。一定の閾半径内の最大ピークのみを考慮することにより、１０個の画素のデフォルトの閾半径が選択されることが好ましい。ステップ１６２０において、相関画像１６１０は、走査され、画素値の大きさが画素値の全ての隣接値より大きい点のリストが、構築される。次のステップ１６３０において、このピークのリストは、画素値の大きさ順にソートされる。次のステップ１６４０において、ソートリストの各ピークは、大きさの降順に考慮され、半径距離閾値内のリスト上のソート後の任意のピークは、ピークリストから排除される。次のステップ１６５０において、ステップ１６４０で発生したピークのソートリストは、切り捨てられ、長さリストＰとなる。
【０１３７】
上記の切り捨てリストは、高精度で決定可能なＰ個のピークの位置を含む。ステップ１６６０において、ループ入力により、同様にＰ個の各ピークを取り入れる。次のステップ１６７０において、考慮中のピークの位置にセンタリングされた２７画素単位の領域は、ＦＦＴに入力され、その後、係数２７により、ピークに焦点を合わせてズーミングするチャープＺ変換に入力される。チャープＺ変換は、任意のスペーシングでの離散フーリエ変換（ＤＦＴ又は逆ＤＦＴ）の計算を可能にする。チャープＺ変換は、例えば、ＤＦＴを離散周期的畳み込みとして表現することにより行われる。このような畳み込みが、複数のＦＦＴを使用して実現可能であるため、全体の計算には、ＦＦＴ速度を利用できる。スペーシングの適切な選択により、チャープＺ変換は、例えば、ＤＦＴを選択領域全体にわたり精密にサンプリングする（すなわち、ズーミングする）ことが可能な補間技法となる。
【０１３８】
最大の大きさを有する２７画素単位の画像は、次のステップ１６８０において判定され、このピークのサブ画素位置は、双放物適合を使用して判定される。このサブ画素精度ピーク位置は、ピーク検出ステップ１７８０の出力である。
【０１３９】
＜粗位置決めを判定するための検出ピークの使用＞
その後、図１４のステップ１７８０（図１２も参照）から出力されたピークは、図１２のステップ１７９０により、４つのピークの各可能な結合を順次選択し、且つ次の解析を行うことにより、更に処理される。これにより、４つのピークの結合のうちのこの解析の条件を最も満足する経路を保持する。
【０１４０】
各ピークｓｉ及びピークβｉの半径及び角度は、図１３の準極マップ１８１２内の各ピークのオフセット（ｘ，ｙ）から計算される。
【０１４１】
１８１３の準極座標（ｘ，ｙ）から極座標（ｓ，β）へのこの変換は、次式により計算される。
【０１４２】
入力画像１８１２は、大きさ（Ｗ，Ｘ＋Ｙ）画素の画像であり、次のパラメータ
2006014280.tif 000021
が設定される。
【０１４３】
もし、ｙ＜Ｙである場合は、
2006014280.tif 000022
あるいは、ｙ≧Ｙである場合は、
2006014280.tif 000023
ここで、Ｙ２、Ｘ２、Ｗ２、ｙｓ及びｘｓは、中間値である。
【０１４４】
線形変換パラメータ（ａ１１、ａ１２、ａ２１、ａ２２、ｘ０、ｙ０）により説明されるアフィン変換は、４つの選択ピークから判定される。線形変換パラメータは、１次元基底関数のパラメータｒｉ及びパラメータαｉの最初の組（式（３）からの組であり、便宜上式（１４）で再生される）を、パラメータｓｉ及びパラメータβｉにマッピングする。位置決めマークが埋め込まれたセキュリティ文書１０５において使用された１次元基底関数パラメータの予め規定された組は、式（３）から次式により再生される。
2006014280.tif 000024
この場合、
2006014280.tif 000025
である。ここで、Ｎ＝１０２４である。
【０１４５】
このパラメータの組は、パラメータの組が表現する１次元基底関数の対称軸が、アフィン変換下において不変である一定長さ比を有する線セグメントを規定する点で交差するように、特定の方法で選択されている。
【０１４６】
４つのピークの結合が満足すべき第１の条件は、４つのピークが、正確な長さ比（例えば、図１１の１１０１：１１０２を参照）を有する線セグメントの組を生成することである。４つのピークが、正しい長さ比を有する線セグメントの組を生成しなかった場合、ピーク結合が、アフィン変換により変形された４つのオリジナルベースパターンに対応せず、この結合は、破棄される。
【０１４７】
前述したように、ピークの半径座標ｓｉ及び角度座標βｉは、セキュリティ文書内に埋め込まれた１次元スケール不変パターンのうちの１つの対称軸を表す。これらの線パラメータにおける変化を直接通して画像に適用されたアフィン変換が判定されるのではなく、アフィン変換は、４つの選択ピークにより特定された４つの対称軸の交点から判定される。２つの対称線｛ｓｋ，βｋ｝の軸と対称線｛ｓｍ，βｍ｝の軸との交点は、（ｘｋｍ，ｙｋｍ）でラベル付けされ、次の行列式（１６）
2006014280.tif 000026
により与えられる。
【０１４８】
線が平行である場合、交点は存在しないため、ｓｉｎ（βｋ−βｍ）≠０の制約が課される。実施状況において、ｓｉｎ２（βｋ−βｍ）≧０．２５であれば、良好な交点位置を確保するためには十分である。線のパラメータ式は、原点を通るその線の垂直二等分線に対してその線上の任意の点の線形距離を特定する。４つの相互に平行でない線の現在の場合において、各線は、線の長さ（例えば、図１１の線３に対する点１１０３〜点１１０５を参照）に沿って３つの交点を有し、交点間隔比（図１１の線３に対する１１０１：１１０２）は、アフィン変形に対して不変の状態を維持する。ｍ番目の線が交差するｋ番目の線に沿った距離λｋｍ は、次式
2006014280.tif 000027
により与えられる。
【０１４９】
次に、上記の式（１７）は、ｋ≠ｍである全ての組み合わせλｋｍに対して列挙され、線に沿った位置を含む表（１８）は、次式
2006014280.tif 000028
により生成される。
【０１５０】
次に、表（１８）のパラメータは、大きさ順に次式により表される。
｛λｋｍ｝ｍａｘ＞｛λｋｍ｝ｍｉｄ＞｛λｋｍ｝ｍｉｎ（各線ｋのｍ＝１→４）である。これにより、次の式（１９）
2006014280.tif 000029
【０１５１】
に示すように、長さ比Ｒｋ’を求める。
【０１５２】
この式により、４つの対称軸から、４つの比が生成される。また、４つの比は、１次元基底関数パラメータｒｉ及び１次元基底関数パラメータαｉの最初の組から生成されてもよい。これらの（最初の）比がＲｋとして示される場合、４つのピークの選択された組に対する比測定における誤りは、次式
2006014280.tif 000030
により規定される。
【０１５３】
この誤りが０．１を超える場合、このピークの組は、破棄される。誤りが０．１未満である場合、線形最小二乗適合モデルを適用することにより、最適アフィン変換を判定する。最適アフィン変換は、４つの選択ピークにより生成された対称軸の交点の組を、埋め込みパターンの対称軸の交点の最初の組へマッピングし直す。最適アフィン変換を求める方法は、後述される。
【０１５４】
＜ソルト値の抽出＞
図４へ戻ると、一旦、粗位置決めマークが回復され、且つステップ２４０１及びステップ２４０２に従って粗位置決めが行われた場合、次に、ステップ２４２２においてソルトは、回復される。ソルトパターンに対応するピークは、粗位置決めマークに対して上述した方法と同様の方法を使用して回復される。ソルト振動定数γを有するベースパターンの最有力検出候補のピークを使用して、検出ピークの角度及び半径から２つの６ビット値は、回復される。これらの値が結合されることにより、１２ビットソルト値は、形成される。
【０１５５】
＜暗号フィールド及び合成暗号位置決め画像の再生＞
図４の精位置決めステップ２４０３に先行して、図２の妥当性検証サブシステム１２７の暗号フィールドを再生する必要がある。この再生は、図５及び図６に関して説明した方法と同様の方法で、オリジナル鍵（図６のステップ２５０１を参照）を使用して行われる。オリジナル鍵は、オペレータにより入力されるか、妥当性検証サブシステム１２７にとって既知であるか、あるいは、作成サブシステム１２６から、又は他の手段により転送されてもよい。オリジナル鍵（図６のステップ２５０１により使用された）は、前述した方法と同様の方法により、ソルト値（図６のステップ２５０８から）と組み合わされる。その後、暗号フィールドは、信号供給源１０２及び信号供給源１０３に関して説明した方法と同様の方法で、図２の暗号信号供給源１０２’及び暗号信号供給源１０３’により生成される。図１の粗位置決め／ソルト回復モジュール１１３により実行された粗位置決めステップ２４０１及び粗位置決めステップ２４０２（図４を参照）により判定されたように、信号供給源１０２’及び信号供給源１０３’により生成された暗号フィールド空間領域は、粗位置決め走査文書１２１の等価領域に制限できる。
【０１５６】
次に、信号供給源１０２’及び信号供給源１０３’により生成された暗号フィールドのカラー画像バージョンは、精位置決めモジュール１０６内で作成される。図７に関して説明した方法と同様の方法で、これらの各カラー画像バージョン（図７に関して暗号フィールド由来カラーグリッドと呼ぶ）は、各画素における２ビット暗号値に、カラールックアップテーブル１３４及びルックアップテーブル１３５内の索引付けをすることにより作成される。その後、各暗号フィールドの各生成カラー画像バージョンを、画素複製により各寸法の係数３でアップスケーリングすることにより、６００ＤＰＩ画像（走査文書１２０と同一の解像度）を形成する。６００ＤＰＩ画像は、暗号フィールドの「原寸」カラー画像バージョンを形成する。最後に、暗号フィールドの合成カラー画像バージョンは、暗号フィールドの２つのカラー画像バージョンを平均化することにより生成される。
【０１５７】
＜ブロックベースマッチングによる精位置決め＞
図１５は、図４の精位置決め処理２４０３における置換マップを形成するために使用されたブロックベース相関付け副処理２４０３Ａを示す図である。ブロックベース相関付け処理２４０３Ａでは、ワープ（すなわち、故意の事前細粒変形）を表現する置換マップＤを生成する。ワープは、図２の信号１２１における粗位置決め走査文書の画素を、カラー暗号フィールドのそれぞれの画素位置にマッピングするために必要とされる。不正顕示信号１２０を発生させるために、印刷／走査動作が、不正顕示機能付文書１０５の印刷の際にプリンタ２２１５により実行され、且つ文書１０５の走査の際にスキャナ２２１８により実行されたため、ワーピングでは、粗位置決め走査文書において行われた変形を考慮する。このワーピングは、粗位置決め文書１２１、暗号フィールド１１５’及び暗号フィールド１１６’の精位置決めの一部を構成する。
【０１５８】
ブロックベース相関付け処理２４０３Ａでは、入力として、（ａ）図２の信号１２１における粗位置決め走査文書（図１５の画像１である２０１０で示される）及び（ｂ）暗号フィールドの合成カラー画像バージョン（画像２である２０２０で示される）を受け取る。粗位置決め走査文書は、幅Ｎ画素及び高さＭ画素を有し、合成カラー画像バージョンも、幅Ｎ画素及び高さＭ画素を有する。画像１（すなわち、２０１０）は、図４の粗位置決めステップ２４１９の結果１２１であるため、２つの画像２０１０及び画像２０２０は、相互の数画素の範囲内に大まかに位置決めされる。
【０１５９】
ブロックベース相関付け処理２４０３Ａは、ブロックの大きさＱ及び段差の大きさＰの選択を含む。これらの大きさは、変更可能である。ブロックの大きさＱを増大させると、より大きい空間領域（及びより多くの計算時間）にわたりＱを平均化する代償として、より高度な測定精度が得られる。段差の大きさＰを減少させると、計算時間は増大するが、より大きな空間ディテールが得られる。考慮中の例では、Ｑ＝２５６、且つＰ＝３２である。これは、高さ２５６画素及び幅２５６画素を有し、且つ水平方向及び垂直方向に増分３２画素で画像２０１０及び画像２０２０に沿って段差付けされているブロックを表す。
【０１６０】
図１６は、相関付けのためのブロックの選択を示し、ブロック相関付け処理２４０３Ａにおけるブロックの大きさ及び段差の大きさを示す図である。相関ブロック２１００は、画像１（すなわち、２０１０）上に示される。ブロック２１００は、水平寸法「Ｑ」及び垂直寸法「Ｑ」を有する。ブロック２１００は、水平方向に増分「Ｐ」（２１０１で示す）で、垂直方向に増分「Ｐ」（２１０２で示す）で段差付けが施されている。
【０１６１】
図１５へ戻ると、ステップ２０８０におけるブロックベース相関付け処理２４０３Ａの出力は、置換マップ「Ｄ」である。置換マップＤは、次の式（２１）により規定された寸法を有するラスタ画像である。
2006014280.tif 000031
ここで、Ｄｘは水平寸法であり、Ｄｙは垂直寸法であり、Ｎは画像２０１０の幅画素であり、Ｍは画像２０１０の高さ画素であり、Ｑは選択ブロックの大きさである。
【０１６２】
要素数は、Ｄｘ＊Ｄｙである。Ｐは、固定である。置換マップＤの各要素は、置換ベクトル及び信頼度推定を有する。置換マップＤ内の各置換ベクトル及び信頼度推定は、ブロック相関付けの結果である。
【０１６３】
画像２０１０及び画像２０２０の処理は、画像２０１０及び画像２０２０からの全ての相関ブロックＢｐ及び相関ブロックＢｑにわたるステップ２０３０のループの入力により開始する。この場合、それぞれ、相関ブロックのサブスクリプト「ｐ」は、［０．．Ｄｘ−１］の範囲内において、サブスクリプト「ｑ」は、［０．．Ｄｙ−１］の範囲内で変化する。画像２０１０からのブロックＢｍと画像２０２０からのブロックＢｎとの既定の対に対して、置換マップＤにおける画素（ｉ，ｊ）を考えると、各々のブロックＢｍ及びブロックＢｎは、次の式（２２）で表現される画素（ｉ，ｊ）の画素オフセットにおいてこれらのブロックの左上の画素を有する。
2006014280.tif 000032
ここで、式（２２）内の最初の項は、水平方向のオフセットを表し、２番目の項は、垂直方向のオフセットを表す。
【０１６４】
次のステップ２０４０において、それぞれ、全体の選択ブロックＢｍが画像２０１０の範囲内に、選択ブロックＢｎが画像２０２０の範囲内に存在するか否かが確認される。全体のブロックがそれぞれの画像の範囲内に存在しない場合、置換マップＤ内の画素（ｉ，ｊ）に対する信頼度推定は、０に設定され、ループは、継続される。しかしながら、全体のブロックＢｍが画像２０１０の範囲内に、全体のブロックＢｎが画像２０２０の範囲内に存在する場合、次のステップ２０５０では、（ＲＧＢ）ブロックＢｍ及び（ＲＧＢ）ブロックＢｎのＹｕｖカラー空間バージョンを生成する。その後、ステップ２０５０では、ｕを対応するＹｕｖブロックからの実数要素として、ｖを対応するＹｕｖブロックからの虚数要素として取り扱うことにより、それぞれ、ブロックＢｍからの新規の複素画像Ｂ”ｍ 及びＢｎからの新規の複素画像Ｂ”ｎを形成する。ｕ値及びｖ値に基づいた新規のブロックＢ”ｍ及び新規のブロックＢ”ｎは、Ｙｕｖカラー空間の主にＹ要素に閉じ込められた主成分の効果を低減する。ステップ２０５０では、更に、ウィンドウ関数で新規のブロックＢ”ｍ及び新規のブロックＢ”ｎを乗算することにより、それぞれのウィンドウ化ブロックＢ’ｍ及びウィンドウ化ブロックＢ’ｎを形成する。上述の構成では、垂直方向に二乗されたハニングウィンドウおよび水平方向に二乗されたハニングウィンドウを使用する。次のステップ２０６０では、２つのウィンドウ化ブロックＢ’ｍ及びウィンドウ化ブロックＢ’ｎに対して位相相関付けを行う。
【０１６５】
相関付けステップは、以下の相相関付けを使用して行われる。相相関付けにおいて、ブロックＢ’ｍのＦＦＴは、ブロックＢ’ｎのＦＦＴの複素共役で乗算され、Ｂｐｈｍｎ で示されるこの乗算結果は、基準化されて単位大きさの最大値を有するようになる。基準化された結果は、Ｂｐｈｎｍｎで示される。その後、ステップ２０５０では、Ｂｐｈｎｍｎに逆ＦＦＴを適用して、「Ｃ」で示す相関ブロックを形成する。
【０１６６】
相関ブロックＣは、（本実施例では）複素値のＱ×Ｑ寸法のラスタアレイである。その後、複素値は、ピーク検出ステップ２０７０に入力される。ステップ２０７０は、図１２のピーク検出ステップ１７８０の動作に類似する。ステップ２０７０では、ブロックＣの中心に対する相関ブロックＣの最大ピークの位置をサブ画素精度で判定する。ステップ２０８０において、ブロックＣの中心に対するこのサブ画素精度位置は、相関付け結果の信頼度推定として、ピーク高さの平方根に沿った位置（ｉ，ｊ）における置換マップＤ内に格納される。ループ２０３０は、未処理のブロックが存在しなくなるまで継続される。
【０１６７】
次に、図１７に関して説明されるように、補間処理２４０３Ｂでは、図１５のブロック相関付け副処理２４０３Ａから出力された置換マップＤを使用して、変形マップＤ’を形成する。変形マップＤ’は、粗位置決め走査文書１２１内の各画素を、暗号フィールドの座標空間内の画素と関連付ける。変形マップＤ’のいくつかの部分は、粗登録文書１２１内の画素を、暗号フィールド境界線の外側の画素にマッピングしてもよい。この動作の理由は、撮影装置が、文書全体を撮影しなかったためである。
【０１６８】
図１７は、変形マップＤ’を形成するために、置換マップＤを補間するための補間処理２４０３Ｂを示す図である。補間処理２４０３Ｂでは、ステップ１９１０において、図１５のステップ２０８０において格納された置換マップＤを受け取る。次のステップ１９２０では、置換マップＤを使用して、置換マップＤに最適な線形変換パラメータ（ｂ１１，ｂ１２，ｂ２１，ｂ２２，Δｘ，Δｙ）の組を判定する。
【０１６９】
暗号フィールド内の任意の点（ｘｉｊ，ｙｉｊ）（尚、このような点のｘ、ｙの位置は、文書１２１内の画素とは対照的に、位置上の変形を受けなかった）は、次の数学的関係に係る置換マップＤ内の対応する画素（ｉ，ｊ）
2006014280.tif 000033
にマッピングされる。
【０１７０】
次の演算を実行することによって、置換マップを使用して暗号フィールド点を置換し、対応する置換暗号フィールド点座標
2006014280.tif 000034
を生成する。
2006014280.tif 000035
ここで、Ｄ（ｉ，ｊ）は、考慮中の画素（ｉ，ｊ）に対する置換マップＤの置換ベクトル部分である。
【０１７１】
非変形点（ｘｉｊ，ｙｉｊ）に割り当てられた線形変換パラメータ（ｂ１１，ｂ１２，ｂ２１，ｂ２２，Δｘ，Δｙ）は、次式により、アフィン変換点
2006014280.tif 000036
2006014280.tif 000037
を生成する。
【０１７２】
最適アフィン変換は、置換座標
2006014280.tif 000038
の間の誤りの最小化により判定され、アフィン変換点
2006014280.tif 000039
は、アフィン変換パラメータを変化させることにより判定される。最小化すべき誤り関数は、次式
2006014280.tif 000040
により規定されたユークリッドノルム測度Ｅである。
【０１７３】
最小化の解は、次式により与えられる。
2006014280.tif 000041
この場合、
2006014280.tif 000042
2006014280.tif 000043
且つ
2006014280.tif 000044
である。ここで、合計は、置換マップＤ内の置換ベクトル上のゼロでない信頼度推定を使用して、置換画素全体にわたって実行される。
【０１７４】
次のステップ１９３０では、次式
2006014280.tif 000045
により各置換マップ画素を置換することにより、置換マップから最適線形変換を排除する。
【０１７５】
その後、次のステップ１９４０では、最適線形変換を、バイキュービック補間を使用して排除した後、置換マップをＤｘＰ×ＤｙＰ寸法の置換マップに補間する。置換マップが、バイキュービック補間カーネルの隣接部分内に信頼度ゼロを有する画素を有する場合、補間ステップにおいて、複雑化が発生する可能性がある。複雑化が発生した場合、信頼度ゼロを有する画素自体を、画素の信頼値により重み付けされた隣接画素の平均を使用して、推定値で置換する。隣接画素が、正の信頼度を有していない場合、画素値を判定するために、アルゴリズム発展領域は、使用される。次に、補間置換画素は、置換マップ内の置換画素に沿った正の信頼度を有する画素を使用するバイキュービック補間を使用して計算される。
【０１７６】
次のステップ１９５０では、次式により、以前に排除された最適線形変形を補間置換マップＤ’に再び適用する。
2006014280.tif 000046
ここで、
2006014280.tif 000047
である。
【０１７７】
Ｄ’（ｉ，ｊ）は、変形マップであり、補間処理２４０３Ｂのステップ１９５０からの出力を形成する。
【０１７８】
＜精位置決めに対する画像ワーピング＞
図１８は、図１７のステップ１９５０の変形マップＤ’から精位置決め文書を形成するために使用されたワーピング処理２４０３Ｃを示す図である。画像ワーピング処理２４０３Ｃでは、入力として、走査文書１２１と、図１２のステップ１７９０において粗登録処理により生成されたアフィン変換パラメータと、図１７のステップ１９５０の変形マップＤ’とを使用し、出力として、カラー暗号フィールドに精密に登録された走査文書のワープ形態（精位置決め走査文書と呼ぶ）を使用する。画像ワーピング処理２４０３Ｃにおける第１のステップ２６０１では、変形マップＤ’を、暗号フィールド内の画素と走査文書１２１内の画素とを関連付ける関連マップＤ’ｃに修正する。この修正は、次式を実行することによって、粗登録ステップ（図１２のステップ１７９０）において判定されたアフィン変換を、変形マップＤ’に戻り加算することにより行われる。
2006014280.tif 000048
ここで、（ａ１１，ａ１２，ａ２１，ａ２２，ｘ０，ｙ０）は、粗登録ステップにおいて判定されたアフィン変換パラメータである。
【０１７９】
その後、更にステップ２６０１において、暗号フィールド内の画素に対応する走査文書１２１内の画素は、（ａ）関連マップＤ’ｃを使用して、走査文書１２１内の各画素に対して、暗号フィールド内の画素位置に対応する走査文書１２１上のサブ画素位置を判定し、且つ（ｂ）バイキュービック補間を使用して、その位置における走査文書１２１を補間することにより、識別される。
【０１８０】
次のステップ２６０２では、粗位置決め走査文書１２１と同一の大きさを有する空画像Ｉｅを形成する。その後、ステップ２６０３では、上記の空画像Ｉｅ内の次の画素を読み取る。次の判断ステップ２３０４では、Ｉｅ内の全ての画素が処理されたか否かが検定される。Ｉｅ内の全ての画素が処理された場合、プロセス２４０３Ｃは、図４の矢印２４２３である矢印ＹＥＳに従って進み、２４２３（図４を参照）で精位置決め文書を出力する。これに対して、Ｉｅ内に未処理の画素が残存する場合、プロセス２４０３Ｃは、ステップ２３０４から「ＮＯ」に従って、ステップ２６０６へ進む。
【０１８１】
ステップ２６０６において、空画像Ｉｅ内の考慮中の画素に対して、（ｘ，ｙ）座標は、関連マップＤ’ｃ内の対応する画素から取り出される。その後、ステップ２６０７では、この（ｘ，ｙ）座標を使用して、バイキュービック補間により、粗位置決め走査文書１２１の対応する「真の」画素値を計算する。次のステップ２６０８では、当該画素に関してワープ（真の）画素値をＩｅ内に書き込むことにより、精位置決め走査文書を形成する。その後、プロセス２４０３Ｃは、矢印２６０９によりステップ２６０３へ戻る。尚、Ｉｅは、特に、赤強度成分、緑強度成分及び青強度成分のようないくつかの成分を含む。
【０１８２】
６００ＤＰＩの精位置決め走査文書Ｉｅ及びカラー画像暗号フィールドは、各 ブロックの中央画素をサンプリングすることにより、２００ＤＰＩに減少する。この減少により、２００ＤＰＩ画素間のいくつかの混色値を有する画素を、回避する。
【０１８３】
＜精位置決め走査文書の認証＞
図１９は、改竄検知の一例を示す図である。画素８０１は、（図２の信号１２３又は信号１２４における）精位置決め走査文書８１２の一部を形成する。４つの画素８０２は、図８の不正顕示機能付文書７０５に示す比較可能なオリジナル画素７０９から変化した。そのため、非認証人物は、図８の文字「ＥＦ」を図１９の「ＦＥ」に変化させるために、２対の画素８０２を変化させた。
【０１８４】
最初の工程として、矢印８１３で示すように、精位置決め走査文書８１２に対して、各画素の輝度値を考慮する閾化モジュール１０７内で閾値演算が施される。輝度が５０％未満の画素は、黒として分類され、残る画素は、白として分類される。オリジナルのソース画像（不図示）として仮定された画像８０４は、閾値演算の結果として作成される。
【０１８５】
文書８０２の最初の符号化の際に使用された次のカラー画像バージョン暗号フィールド８０５は、精位置決め走査文書８１２を被覆するために、十分な領域内に再生される。この再生は、図６のステップ２５０１からのオリジナル鍵を使用して行われる。オリジナル鍵は、オペレータにより入力されるか、妥当性検証サブシステム１２７にとって既知であるか、あるいは、作成サブシステム１２６から、又は他の手段により転送されてもよい。オリジナル鍵は、図６のステップ２５０８からのソルト値と組み合わされる。
【０１８６】
次に、選択モジュール１０９は、閾化画像８０４内の各画素の値８１４を使用して選択を制御する。この制御８１４下において、選択モジュール１０９は、１つのカラー画像バージョン暗号フィールド又は他のカラー画像バージョン暗号フィールドから画素値８１６又は画素値８１５を選択することにより、基準画像８０７を作成する。この基準画像の作成は、符号化処理において使用された処理と等価の処理である。比較モジュール１０８内では、基準画像内のこのような各選択画素（画素８０７等）に対して、選択画素（本例では、画素８０７）と位置決め走査画像（この場合、画素８０１）の対応する画素との比較が行われる。画素８０７の色の副成分及び画素８０１の色の副成分が、要求された許容範囲内で一致しない場合、画素は、画素の元の状態から改竄されたとして規定される。一構成例によると、画素の色成分のうちの任意の成分が、線形ＲＧＢカラー空間内で測定された既定の色に対して通常の補正値２５％を越える差異を有する場合、画素は、「一致」状態を満足できなかったとみなされる。各色に対する通常の補正値は、サンプル色のサンプル色パッチ走査により、又は、推定値のみに基づいて判定できる。閾化画像に沿ったこの情報は、新規の認証画像８０９を構築するために使用される。説明された例において、マゼンダ以外の全ての画素が、閾化画像に係る黒又は白のいずれかである状態で、マゼンダの複数の画素８１０は、再生される。
【０１８７】
改竄された画素は、改竄されたポイントにおいて、適切なランダムフィールド（副成分を含む）と偶然にも同一色を有することにより、明らかにされない可能性がある。この状態は、画素が白から黒に変化したにもかかわらず、認証画像内で改変としてフラグされていない場合を示す画素８１１で示される。上述の構成において、通常、２５％までの画素の改変は、検知できない可能性がある。このことは、暗号フィールドが２ビット精度を使用している事実から導出される。検出された画素の７５％が、通常、ユーザに対して改変の発生及び特徴を警告するためには十分である。従って、大きな領域（例えば、５２ビット鍵内のビット数を超える画素を有する領域）にわたって、検出不可能な不正改変方法を施すことの困難性は、鍵空間の大きさにほぼ比例する。
【０１８８】
最終認証画像８０９は、通常、オペレータによる試験のためにカラープリンタ上に印刷される。しかしながら、認証画像８０９は、改変画素の数又は改変画素の稠密領域の存在に基づいた自動解析も施されてもよい。
【０１８９】
改変画素を明らかにすることが、固有に且つ精密にスケーリングされるため、それを示すように、オリジナル文書７０８の画素スケールを発生させる。また、改変画素を明らかにすることは、オリジナル文書７０８を感知できないため、疑わしい文書８１２及びこれらの改変を明らかにするためのオリジナル鍵のみを必要とする。
【０１９０】
説明された方法の実質的な利点は、文書８１２の副次部分の改変を明らかにすることが、文書８１２の残る部分と無関係であることである。尚、粗位置決め情報及びソルト情報は、高度な冗長を実現するために、空間領域内及び周波数領域内の情報の非常な広域分散に対して十分な信号強度を提供する技法を使用して、文書内に組み込まれる。これは、文書８１２の残る部分と関連することなく、これらの信号が、文書８１２の任意の副次部分から回復できることを意味する。上述の構成において、文書の任意の２５％の領域からのこれらの信号の回復は、容易に実現できる。尚、精位置決め工程及び認証工程は、局所的処理及び不可視部分に対する高度なロバストさも提供する。従って、システム全体は、柔軟性が高く（特殊な構成を有していない任意の文書の全領域に適用可能である）、且つ部分的な転送又は偶発的文書損害に対してロバストな認証方法を提供する。
【０１９１】
＜プリンタドライバにおけるマーキング処理の使用＞
改竄防止方法は、マイクロソフトのウィンドウズ（登録商標）ベースコンピュータ等の汎用コンピュータ上のプリンタドライバの一部として内蔵していてもよい。この構成において、プリンタドライバの特性には、改竄防止方法を可能とするためにオペレータが選択できるユーザインタフェースエレメントと、鍵（又はパスワード）の入力が可能な第２のユーザインタフェースエレメントとが設けられている。この構成の一変形例において、プリンタドライバは、応用データを印刷待ち画像に変化させるラスタ化処理を含む。この段階において、印刷待ち画像は、改竄防止方法で説明したように、プリンタドライバにより修正され、生成された画像は、プリンタ装置に送信される。
【０１９２】
第２の変形例において、改竄防止方法は、プリンタ装置内で実行される。この方法は、改竄防止方法が、高周波データを印刷データ内に導入するので、利便性が高い。プリンタへのデータ転送処理、又はプリンタの内部処理が、画像圧縮を採用する場合、この高周波データが存在するため、画像圧縮への効果は少ない。しかしながら、プリンタ装置へのデータ転送後、改竄防止方法が実行された場合、プリンタ装置は、圧縮及び解凍の終了後に、後段の処理において高周波データを加算できる。
【０１９３】
＜複合機におけるマーキング及び認証の使用＞
改竄防止方法の別の構成では、Ｃａｎｏｎ  ＩＲ  Ｃ３２００等の複合機の能力として、改竄防止方法を採用する。この構成において、複合機は、セキュリティコピー動作の一部として改竄防止方法を採用可能とするユーザインタフェースエレメントを提供する。プリンタドライバの場合、第２のユーザインタフェースが、鍵入力を可能とする。この実現されたオプションを使用してコピーされた文書が走査され、上述のように、デジタル走査画像がマーキングされ、且つこの生成されたデジタル画像が印刷されることにより、セキュリティコピー動作を提供できる。また、同一の多機能装置又は別の多機能装置は、認証特徴を採用する。この認証特徴も、ユーザインタフェースエレメント及び第２の鍵入力エレメントにより実現できる。このオプションの範囲下においてコピーされた文書は、上述の認証処理が施される。印刷文書は、非改変領域の黒及び白が再現される状態で、マゼンダ（又は他の強調表示色）が明らかにされた改変領域を有する認証処理結果である。
【０１９４】
＜スキャナを使用した文書の認証＞
改竄防止方法の別の構成では、ＵＳＢインタフェースを介してマイクロソフトのウィンドウズ（登録商標）を稼動し、且つ改竄防止処理を採用したソフトウェアアプリケーションを稼動している汎用コンピュータに接続されたＣａｎｏｎ  ＣａｎｏＳｃａｎ  ８０００Ｆ等のスキャナ装置が使用される。この構成において、ソフトウェアアプリケーションは、ＴＷＡＩＮスキャナドライバを使用して、オペレータにより提供された紙文書から文書画像を得る。各文書画像は、改竄防止方法に従って解析される。妥当性検証結果は、オペレータによる検査のために、コンピュータ画面上に表示される。
【０１９５】
＜枚葉紙スキャナを使用した大容量文書の認証＞
改竄防止方法の別の構成では、Ｃａｎｏｎ  ＤＲ−５０８０Ｃ等のデスクトップ型高速枚葉スキャナが使用される。この構成において、大容量文書は、オペレータが介入することなく走査される。妥当性検証処理が、走査処理と同期して使用されることにより、改変された文書は、発見される。この構成において、妥当性検証処理の結果であるデジタル画像は、改変画素の閾値を越える画素を含む複数の小さなパッチに対して試験される。パッチの大きさ及び閾値は、オペレータによる設定が可能である。また、文書の異なる領域における異なる閾値及びパッチを設定すること、並びに文書が形態認識システムにより識別されたこれらの領域を有することも可能である。
【０１９６】
［産業上の利用可能性］
上述したように、上記の構成が、文書処理産業に適用できることは、明らかである。
【０１９７】
先の説明は、本発明のいくつかの実施の形態のみを説明したが、本発明の趣旨の範囲を逸脱せずに、本発明の変形及び／又は変更を行うことができる。実施の形態は、例証するものであって、限定するものではない。
【図面の簡単な説明】
【０１９８】
【図１】上述の改竄防止構成が実施可能な汎用コンピュータを概略的に示すブロック図である。
【図２】開示された改竄防止システムの機能ブロック図の一例を示す図である。
【図３】図２のシステムを使用して、不正顕示機能付文書を作成するプロセスを示す図である。
【図４】図２のシステムを使用して、図３からの不正顕示機能付文書の妥当性検証、すなわち、文書が改竄されたか否かを判定するプロセスを示す図である。
【図５】ストリーム暗号から２次元暗号フィールドを生成する２つの方法を表す図である。
【図６】図５の暗号フィールドを生成するプロセスを示す図である。
【図７】２値レベルソース画素を多値レベル不正顕示機能付画素に変換するために使用された図２の選択処理の一例を示す図である。
【図８】多値レベル画像に変換されるべき２値レベル画像の描画例を示す図である。
【図９】粗位置決めに使用された２次元線形波形関数の２値レベル表現を示す図である。
【図１０】図９の線形波形関数のグラフィック表現を示す図である。
【図１１】不正顕示機能付文書の粗位置決めにおいて使用された位置決めマークを形成するために使用された４つの線形波形関数の予め規定された組からの対称軸の一例を示す図である。
【図１２】図４の粗位置決め処理をより詳細に示す図である。
【図１３】図１２の準極変換処理をより詳細に示す図である。
【図１４】図１２のピーク検出処理をより詳細に示す図である。
【図１５】図４の精位置決め処理における置換マップを形成するために使用されたブロックベース相関付け副処理を示す図である。
【図１６】図１５のブロック相関付け処理におけるブロックの大きさ及び段差の大きさを示す図である。
【図１７】図１５の置換マップから変形マップを形成するために使用された補間副処理を示す図である。
【図１８】図１７の置換マップから精位置決め文書を形成するために使用されたワーピング処理を示す図である。
【図１９】改竄検知の一例を示す図である。
【図１】
2006014280.tif 000049
【図２】
2006014280.tif 000050
【図３】
2006014280.tif 000051
【図４】
2006014280.tif 000052
【図５】
2006014280.tif 000053
【図６】
2006014280.tif 000054
【図７】
2006014280.tif 000055
【図８】
2006014280.tif 000056
【図９】
2006014280.tif 000057
【図１０】
2006014280.tif 000058
【図１１】
2006014280.tif 000059
【図１２】
2006014280.tif 000060
【図１３】
2006014280.tif 000061
【図１４】
2006014280.tif 000062
【図１５】
2006014280.tif 000063
【図１６】
2006014280.tif 000064
【図１７】
2006014280.tif 000065
【図１８】
2006014280.tif 000066
【図１９】
2006014280.tif 000067
【手続補正書】
【提出日】平成17年6月16日(2005.6.16)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
更なる種類の技法では、文書のオリジナル非改変形態に関する情報を、認証処理へ独立して転送する方法を使用する。この方法は、独立した知識を有する人物への電話呼び出しと同様に単純であり、安全保証位置内の文書の完全なコピーを維持するために拡張されてもよい。このような技法は、この技法がこのような独立情報の処理及び格納を必要とするため、多くの実施上の不都合な点を有する。
【特許文献１】米国特許第６，４５７，６５１号明細書
【特許文献２】米国特許第６，３６６，６９６号明細書
【特許文献３】米国特許第５，２９１，２４３号明細書
【特許文献４】米国特許第６，１６７，１４７号明細書
【特許文献５】米国特許第５，５０９，６９２号明細書
【外国語明細書】
[Title of the Invention]
SECURE RECORDED DOCUMENTS
[Field of the Invention]
The current invention relates to production and processing of recorded documents, and in particular, to the production of tamper evident documents and detection of tampering in such documents.  The description is directed primarily, for ease and consistency of description, to printed documents, however the disclosed method can be equally applied to other forms of documents upon which information is recorded.
[Background]
It is often desirable to ensure that a printed document has not been altered in some unauthorised manner from the time it was first produced.  For example, a contract that has been agreed upon and signed on some date may subsequently be fraudulently altered. It is desirable to be able to detect such alterations in detail.  Similarly, security documents of various sorts including cheques and monetary instruments record values that are vulnerable to fraudulent alteration.  Detection of any fraudulent alteration is desirable.  Further, it is desirable that such detection be performed automatically, and that the detection reveal the exact nature of the alteration.  In addition to detection of fraudulent tampering with a document, it is desirable that such documents offer a visible deterrent to fraudulent alteration.
Various methods of deterring and detecting fraudulent alteration to documents have been proposed and used.
One class of methods in use before high quality colour scanners and printers became commonly available was to print important information such as monetary amounts in special fonts or with special shadows that were, at the time, difficult to reproduce.  However, with modern printers and scanners, such techniques have become vulnerable to attack.
One known method of detecting alteration uses a 2D barcode printed on one part of a document page to encode (possibly cryptographically) a representation of some other portion, such as a signature area.  This 2D barcode can be decoded and the resulting image compared by an operator to the area it is intending to represent to check for similarity.
A related body of work is the detection of tampering in digital images that are not subject to print/scan cycles.  A number of "fragile watermark" techniques are known in this field, however these techniques are generally not applicable to tamper detection in printed documents because they cannot withstand the introduction of noise, Rotation, Scaling and Translation (RST), re-sampling, and local distortion that occurs in a print/scan cycle.  Some of these techniques operate by replacing all or some of the least significant bits of pixels of an image with some form of checksum of remaining bits in each pixel. 
A number of "semi-fragile" systems have also been described.  These include systems that use cross-correlation to detect the presence of a lightly embedded shifted copy of a portion of the image.  Another technique is to embed watermarks into image blocks, and then compare the detection strength of these watermarks to discern if any blocks have been altered.  These systems tend to have less localisation ability as their detection ability improves, and as their localisation ability improves, they become more sensitive to noise and other distortions and so cannot be used to detect local changes in printed documents.
Other techniques use special materials to make alteration difficult. Such techniques include laminates covering the printed surface where damage to the laminate is obvious.  However using special materials introduces production complexity, and is not applicable to plain paper applications.  They are also not amenable to automatic detection.
An additional failing in many existing techniques is weak cryptographic security.  In many cases, once the cryptographic algorithm being employed is identified, the identification leads directly to a subversion method to attack the identified method.
Another common failing of present techniques is the distribution of alteration detection information over wide areas of the page, or even areas completely separate to the image area to be authenticated (as in the barcode method above).  This introduces problems if there is incidental soiling of the document in areas apart from the image area being authenticated.  Many of these techniques cannot be used to authenticate the entire area of a document, so documents must be specifically designed to accommodate them.
A further class of techniques uses independent transfer of information about the original unaltered form of the document to the verification process.  This could be as simple as a telephone call to a person with independent knowledge, and may extend to keeping a complete copy of the document in a secure location.  Such techniques have many practical disadvantages because they require handling and storage of such independent information.
[Patent Document 1]  US Patent No.6457651
[Patent Document 1]  US Patent No.0636696
[Patent Document 1]  US Patent No.5291243
[Patent Document 1]  US Patent No.6167147
[Patent Document 1]  US Patent No.5509692
[Summary]
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.
Disclosed are arrangements, referred to generally as the "anti-tampering approach", which seek to address the above problems by printing (if this form of recording information is used), on the printed document, a processed form of the information which is desired to be printed (which is referred to as the "source" information).  The aforementioned processing produces a printed, visually perturbed, form of the source information.  The perturbation is such that the printed perturbed information retains sufficient fidelity, relative to the source information, to enable the source information to be read from the printed document by a person, or by machine means (using video-detection and processing for example).  The "perturbations", however, are spatially keyed to the source information, so that the source information establishes the specifics of the perturbation at each region of the printed document.
Although this description is directed primarily, for ease and consistency of description, to application of the disclosed anti-tampering approach to printed documents, the method can be equally applied to other forms of documents upon which information is recorded. Thus, for example, the anti-tampering approach can be applied to documents comprising photographic film (eg silver halide) upon which information is recorded optically.
The processing of the source information to form the perturbed information uses a cryptographically secure key. Without knowledge of this key, tampering with the printed document will generally not, in the region of the tampering, produce the "correct" perturbation components.  In order to verify the tamper-status of the printed document, the authorised reader of the printed document firstly extracts, either visually or using video processing, the purported source information.  The user then uses his or her knowledge of the cryptographic code to re-create the perturbations on the document.  In the region where tampering has taken place, this re-creation will produce perturbations associated with the tampered information. These perturbations however will not be correct, to a predefined level of confidence, because the tamperer would have been cryptographically prevented from correctly creating the correct perturbations.
The anti-tampering approach requires the tamper-evident document to be precisely aligned with (reproductions of) cryptographic fields that were originally used to produce the tamper-evident document. The fields are cryptographic in the sense that they are based on a secret (in this case, a key). The fields have the property that it is impractical to completely generate them without knowledge of the key, even if a fragment of the field is known.  According to one arrangement, and provided that the tamper-evident document has not been distorted relative to the cryptographic fields, simple registration points can be incorporated into the tamper-evident document.  These registration points can be used to obtain precise alignment between the tamper-evident document and the cryptographic fields used for validation.  From an implementation perspective the registration points can be detected by a scanner 2218 (see Fig. 1) when a tamper-evident document 105 is scanned as described in relation to Fig. 2. The coarse alignment step is optional. In many applications, in particular when the tampering is only to be detected in a small field of a document, other coarse alignment methods can be used.  In some instances, even manual coarse alignment can be utilised.  In another arrangement, that is more robust in the face of document distortion caused by the scan/print cycle, distributed "coarse" and "fine" alignment information is embedded into the tamper-evident document, and later used to achieve the alignment when validating the tamper-evident document.
According to a first aspect of the present invention, there is provided a method for processing a tamper-evident document, the method comprising the steps of:
(a)  resolving, in regard to an N-level image to be recorded, at least one pixel of the image into a major component having N possible values,
(b)  selecting a pattern element from at least one predetermined pattern, said selection depending upon (ai) the major component and (aii) the position of the at least one pixel in the image;
(c)  recording the selected pattern element for said at least one pixel onto a transfer medium;
(d)  extracting, from the recorded document, a retrieved pattern element for said at least one pixel;
(e)  determining a pattern element depending upon (di) a major component extracted from said retrieved pattern element and (dii) the position of the at least one pixel on the recorded document; and
(f)  comparing the said retrieved pattern element and the said determined pattern element.
According to another aspect of the present invention, there is provided a method for processing a tamper-evident document, the method comprising the steps of:
(a)  resolving, in regard to an N-level image to be recorded, at least one pixel of the image into a major component having N possible values, and a corresponding randomised minor component, said randomised minor component depending upon (ai) the major component and (aii) a position of the at least one pixel in the image;
(b)  recording the major component and the randomised minor component for said at least one pixel onto a transfer medium;
(c)  extracting, from the recorded document, the major component for said at least one pixel;
(d)  determining the corresponding randomised minor component depending upon (di) the extracted major component and (dii) a position of the at least one pixel on the recorded document;
(e)  measuring, from the printed document, the printed randomised minor component for said at least one pixel; and
(f)  declaring that the pixel of the printed document has been tampered with if the measured printed randomised minor component does not match the determined randomised minor component.
According to another aspect of the present invention, there is provided a method for recording a tamper-evident document, the method comprising the steps of:
(a)  resolving, in regard to an N-level image to be recorded, at least one pixel of the image into a major component having N possible values,
(b)  selecting a pattern element from at least one predetermined pattern, said pattern element depending upon (bi) the major component, and (bii) the position of the at least one pixel in the image; and
(c)  recording the pattern element for said at least one pixel onto a transfer medium.
According to another aspect of the present invention, there is provided a method for recording a tamper-evident document, the method comprising the steps of:
(a)  resolving, in regard to an N-level image to be recorded, at least one pixel of the image into a major component having N possible values, and a corresponding randomised minor component, said randomised minor component depending upon (ai) the major component, and (aii) a position of the at least one pixel in the image; and
(b)  recording the major component and the randomised minor component for said at least one pixel onto a transfer medium.
According to another aspect of the present invention, there is provided a method for validating a recorded tamper-evident document, the method comprising the steps of:
(a)  extracting, from a position in the recorded document, a retrieved pattern element; 
(b)  selecting a pattern element depending upon (bi)  a characteristic of the said retrieved pattern element and (bii) the position;
(c)  comparing the retrieved pattern element and the selected pattern element.
According to another aspect of the present invention, there is provided a method for validating a recorded tamper-evident document, the method comprising the steps of:
(a)  extracting, from the recorded document, a major component, having N possible values, for at least one recorded pixel;
(b)  determining a corresponding randomised minor component depending upon (bi) the extracted major component and (bii) a position of the at least one recorded pixel;
(c)  measuring, from the recorded document, the recorded randomised minor component for said at least one pixel; and
(d)  comparing the measured recorded randomised minor component and the determined randomised minor component.
According to another aspect of the present invention, there is provided a tamper-evident document upon which is recorded an N-level image, the document comprising, in regard to at least one pixel of the image, a recorded pattern element that visually approximates the level of said pixel and also has a cryptographic value depending upon (a) the level of said pixel, and (b) the position of said pixel in the recorded document.
According to another aspect of the present invention, there is provided a tamper-evident document upon which is recorded an N-level image, the document comprising, in regard to at least one recorded pixel of the image, a recorded major component having N possible values, and a recorded randomised minor component, said recorded randomised minor component depending upon (a) the major component, and (b) a position of the at least one recorded pixel in the recorded document.
According to another aspect of the present invention, there is provided a computer program product having a computer readable medium having a computer program recorded therein for directing a processor to execute any of the above methods.
According to another aspect of the present invention, there is provided a computer program for directing a processor to execute any of the above methods.
According to another aspect of the present invention, there is provided a method of detecting tampering of a security document, comprising:
(a)  generating scan data corresponding to said document;
(b)  performing region matching between said scan data and at least one two-dimensional cryptographic field to obtain alignment information;
(c)  using said alignment information and said scan data to detect tampering in said security document.
According to another aspect of the present invention, there is provided a method of detecting tampering in a recorded image, said method including the steps of:
(a)  combining an image with at least one two-dimensional cryptographic signal to form a second image,
(b)  recorded said second image to form a recorded image,
(c)  processing said recorded image to make a retrieved image,
(d)  detecting alignment of said retrieved image with respect to said at least one two-dimensional cryptographic signal, and
(e)  using said alignment and said retrieved image and the said at least one cryptographic signal to detect tampering.
According to another aspect of the present invention, there is provided an apparatus for producing a security document, said apparatus comprising:
(a)  a retrieving element for retrieving an original document and producing a document image
(b)  a marking element for marking said document image with a security pattern to produce a marked document image, and
(c)  a recording element for recording said marked document image to produce a security document,
wherein said security document is a readable rendition of said original document and said security pattern provides for detection of alteration between said original document and said security document.
According to another aspect of the present invention, there is provided an apparatus for revealing alterations between an altered recorded document and an unaltered form, said apparatus being characterised by:
(a)  a retrieval means to produce retrieved data corresponding to said recorded document,
(b)  a means to determine the alteration of the shape of at least one graphic element between its shape in the retrieved data and its shape in the unaltered form, said means being blind to the unaltered form,
(c)  a means to output the determined alteration in the shape.
Other aspects of the invention are also disclosed.
[Detailed Description including Best Mode]
Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.
It is to be noted that the discussions contained in the "Background" section and that above relating to prior art arrangements relate to discussions of documents or devices that form public knowledge through their respective publication and/or use.  Such should not be interpreted as a representation by the present inventor(s) or patent applicant that such documents or devices in any way form part of the common general knowledge in the art.
The disclosed "anti-tampering approach" allows an original black and white document to be printed (or re-printed) with a special security marking.  Although the description is directed to bi-level (eg black and white) documents, the disclosed anti-tampering approach can be used on multi-level documents using, for example, black, grey and white source information. Alternately, by using dithering or half toning grey levels may be represented using black and white pixels. The resulting "tamper-evident" document can be recognised and read directly by a human, and can also be scanned and analysed to detect whether any tampering (such as alteration) has taken place.  Detailed and localised differences between what is visible to a human reader on the printed document and the original document can be revealed, even in the presence of minor damage to the printed document, such as noise, fading, physical distortion, and the many changes introduced by the print/scan process.  No knowledge of the original source information is required for this validation process as applied to the tamper-evident document.  Because the revelation of the differences is detailed and localised, a person viewing the revealed differences can easily distinguish important alterations, such as an altered monetary amount, from unimportant ones, such as a stain or accidental pen mark.  The process is cryptographically secure, to a predefined confidence level, against "man in the middle" attacks.  A man in the middle attack is a term used in cryptography to describe an attack made by a malicious intermediary not in possession of the key.
The validation analysis only requires access to the physical (printed) tamper-evident document and a common private key.  In the preferred arrangement this common private key can be the same for many documents without challenging the cryptographic safety of the system.  In particular, the method does not become vulnerable to attacks based on knowledge of different pages marked with the same key.
Some portions of the description that follows are explicitly or implicitly presented in terms of algorithms and symbolic representations of operations on data within a computer memory.  These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art.  An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result.  The steps are those requiring physical manipulations of physical quantities.  Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated.  It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.  
It should be borne in mind, however, that the above and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities.  Unless specifically stated otherwise, and as apparent from the following, it will be appreciated that throughout the present specification, discussions utilizing terms such as "scanning", "calculating", "determining", "replacing", "generating" "initializing", "outputting", or the like, refer to the action and processes of a computer system, or similar electronic device, that manipulates and transforms data represented as physical (electronic) quantities within the registers and memories of the computer system into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.  
The present specification also discloses apparatus for performing the operations of the methods.  Such apparatus may be specially constructed for the required purposes, or may comprise a general purpose computer or other device selectively activated or reconfigured by a computer program stored in the computer.  The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus.  Various general purpose machines may be used with programs in accordance with the teachings herein.  Alternatively, the construction of more specialized apparatus to perform the required method steps may be appropriate.  The structure of a conventional general purpose computer will appear from the description below.  
In addition, the disclosed arrangements also implicitly disclose one or more computer program modules, in that it would be apparent to the person skilled in the art that the individual steps of the methods described herein are to be put into effect by computer code module(s).  The computer program(s) are not intended to be limited to any particular programming language and implementation thereof.  It will be appreciated that a variety of programming languages and coding thereof may be used to implement the teachings of the disclosure contained herein.  Moreover, the computer program(s) are not intended to be limited to any particular control flow.  There are many other variants of the computer program(s), which can use different control flows without departing the spirit or scope of the disclosed arrangement.  Furthermore one or more of the steps of the computer program(s) may be performed in parallel rather than sequentially.  
Such computer program(s) may be stored on any computer readable medium(s).  The computer readable medium(s) may include storage devices such as magnetic or optical disks, memory chips, or other storage devices suitable for interfacing with one or more general purpose computers.  The computer readable medium(s) may also include hard-wired medium(s) such as exemplified in the Internet system, or wireless medium such as exemplified in the GSM mobile telephone system.  The computer program module(s) when loaded and executed on such a general-purpose computer effectively result in an apparatus that implements the steps of the preferred method.
Fig. 1 is a schematic block diagram of a general purpose computer upon which the anti-tampering arrangements described can be practiced.  The method of anti-tampering is preferably practiced using a general-purpose computer system 2200, such as that shown in Fig. 1 wherein the processes of Figs. 3-4, 6-7, 12-15 and 17-18 may be implemented as software, such as an anti-tampering application program executing within the computer system 2200.  In particular, the steps of method of anti-tampering are effected by instructions in the anti-tampering application software that are carried out by the computer.  The instructions may be formed as one or more code modules, each for performing one or more particular tasks.  The anti-tampering application software may also be divided into two separate parts, in which a first part performs the anti-tampering methods and a second part manages a user interface between the first part and the user.  The anti-tampering application software may be stored in a computer readable medium, including the storage devices described below, for example.  The software is loaded into the computer from the computer readable medium, and then executed by the computer.  A computer readable medium having such software or computer program recorded on it is a computer program product.  The use of the computer program product in the computer preferably effects an advantageous apparatus for anti-tampering.
The computer system 2200 is formed by a computer module 2201, input devices such as a keyboard 2202, mouse 2203, and scanner 2218, output devices including a printer 2215, a display device 2214 and loudspeakers 2217.  A Modulator-Demodulator (Modem) transceiver device 2216 is used by the computer module 2201 for communicating to and from a communications network 2220, for example connectable via a telephone line 2221 or other functional medium.  The modem 2216 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN), and may be incorporated into the computer module 2201 in some implementations.
The computer module 2201 typically includes at least one processor unit 2205, and a memory unit 2206, for example formed from semiconductor random access memory (RAM) and read only memory (ROM).  The module 2201 also includes an number of input/output (I/O) interfaces including an audio-video interface 2207 that couples to the video display 2214 and loudspeakers 2217, an I/O interface 2213 for the keyboard 2202 and mouse 2203 and optionally a joystick (not illustrated), and an interface 2208 for the modem 2216, the scanner 2218 and the printer 2215.  In some implementations, the modem 2216 may be incorporated within the computer module 2201, for example within the interface 2208.  A storage device 2209 is provided and typically includes a hard disk drive 2210 and a floppy disk drive 2211.  A magnetic tape drive (not illustrated) may also be used.  A CD-ROM drive 2212 is typically provided as a non-volatile source of data.  
The components 2205-2213 of the computer module 2201, typically communicate via an interconnected bus 2204 and in a manner which results in a conventional mode of operation of the computer system 2200 known to those in the relevant art.  Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations or like computer systems evolved therefrom.  
Typically, the anti-tampering application program is resident on the hard disk drive 2210 and read and controlled in its execution by the processor 2205.  Intermediate storage of the program and any data fetched from the network 2220 may be accomplished using the semiconductor memory 2206, possibly in concert with the hard disk drive 2210.  In some instances, the anti-tampering application program may be supplied to the user encoded on a CD-ROM 2225 or a floppy disk 2222 and read via the corresponding drive 2212 or 2211 as depicted by respective dashed lines 2224 and 2223.  Alternatively the anti-tampering application program may be read by the user from the network 2220 via the modem device 2216.  Still further, the anti-tampering application software can also be loaded into the computer system 2200 from other computer readable media.  The term "computer readable medium" as used herein refers to any storage or transmission medium that participates in providing instructions and/or data to the computer system 2200 for execution and/or processing.  Examples of storage media include floppy disks, magnetic tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module 2201.  Examples of transmission media include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like.
The preferred arrangement of the anti-tampering technique is implemented as software module(s) executing on a general purpose computer system such as 2200.  It may, however, also be implemented as anti-tampering application software modules in an embedded system such as a multi-function copier.  It may also be implemented by fixed or programmable solid-state logic such as an Application Specific Integrated Circuit or a Field Programmable Gate Array.
Fig. 2 shows one example of a functional block diagram for the disclosed anti-tampering system.  Fig. 2 comprises a production sub-system 126 for producing tamper-evident documents 105, 105', and a validation sub-system 127 for detecting (validating) whether the tamper-evident documents 105, 105' have been tampered with. 
Considering the production sub-system 126 that produces the tamper-evident document 105, a selection module 104 makes a selection from one of two synchronised cryptographic signals 115, 116, depending on the value of a scan-based bi-level source signal 117.  The signal 117 is the source information to be printed, and is derived from a bi-level source image 101.  The cryptographic signals 115, 116 are stream ciphers generated by respective cryptographic signal sources 102, 103 that receive private key based information as depicted by respective arrows 135, 136 from a key generation module 134.  The operation of the key generation module 134 and the cryptographic signal sources 102 and 103 is described further in regard to Fig. 6.  If the source document 101 is in paper document form, then the signal 117 can be produced from the paper document 101 using the scanner 2218 (see Fig. 1). If the source document is in electronic document format (such as Adobe PDF), the signal 117 can be produced from a Raster Image Processor (RIP) that converts the electronic document to pixels that form the signal 117. Alternately, if the source image 101 is stored in digital image form in a memory (not shown), then the signal 117 can be read from the memory in a scan-based fashion.
The source signal 117 is used to select between the cryptographic signals 115, 116 to form, in conjunction with respective lookup tables 130, 131, a modulated composite cryptographic signal 118, this being a visually perturbed version of the source information 101.  The source image 101, in the present example, is a bi-level image composed of black and white pixels.  According to one arrangement, the composite signal 118 represents a multi-level image composed of "dark" and "light" pixels.  The dark pixels may thus be, in one example, one of black and fully saturated red, green and blue.  The "light" pixels may be one of white, cyan, magenta and yellow.
Accordingly, in the present example in which the source 101 is bi-level, the two cryptographic signals 115, 116 each are associated, through the respective lookup tables 130 and 131, with signals that have non-cryptographic and mutually distinguishable major components.  The major component associated with one of the signals 115, 116 is always visually dark, while the major component associated with the other one of the signals 115, 116 is always visually light.  Furthermore, the two cryptographic signals 115, 116 each are associated, through the respective lookup tables 130 and 131, with a cryptographic minor component (which may take the form of colour variations, for example).
The term "non-cryptographic" means that the mutually distinguishable major components can be distinguished from each other without reference to cryptographic considerations.  
In multi-level (eg N-level, with N distinct color tones) documents, N cryptographic sources 102, .., 103 would be used.  Each of the N sources would be associated, through respective lookup tables, with a cryptographic signal having N non-cryptographic and mutually distinguishable major components, and N cryptographic minor components. 
Returning to the bi-level case in Fig. 2, the composite cryptographic signal 118 undergoes a merging process in a merge module 114, and a resultant merged composite signal 122 is recorded by a recording module (such as the printer 2215 in Fig. 1) onto a transfer medium to form, in the present example a printed tamper-evident document 105.  The transfer medium is typically paper, used to form a printed document, in which case the transfer medium is referred to as a print medium.  Another example of a transfer medium is silver halide film.  A digital transfer of the merged composite signal is also possible. 
Although the term "document" in this description is most often used in the context of a printed document comprising a print (transfer) medium upon which the merged composite signal 122 is printed by a printer (such as 2215 in Fig. 1), the term document has a more general meaning. Thus the term document can equally, for example, be applied to a recorded document comprising a silver halide film (transfer) medium upon which the merged composite signal 122 is recorded using a suitable optical process and/or device.
In yet another arrangement, the marking and verification process may be used in the preparation, storage, transfer and verification of digital document images. In this arrangement a computer application incorporating the disclosed anti-tampering approach firstly applies the marking process to digital document images. These images may have been produced as part of a scanning process, however they may alternately have been produced by purely digital means. The document images may then be subjected to one or more of archiving, transmission, re-encoding (such as conversion to a different digital image standard), re-sampling (such as occurs during image scaling), and compression or recompression (including so-called "lossy" compression such as baseline JPEG compression). After one or more of these operations the resultant image may then be verified using the disclosed verification process, and the results displayed using a second computer application. The use of the aforementioned marking and verification process is robust in the face of image transformations that do not make significant visual changes to the appearance of the image, even though they make substantial changes to the digital bit pattern of the image or its encoding.
The major components associated with the cryptographic signals 115, 116 making up the merged composite signal 122 allow the tamper-evident document 105 to be read by a person, or by a machine, in the same manner as the original source image 101 can be read.  The minor perturbation component, that is additional to the information in the source image 101, may be visible in the tamper-evident document 105, but this perturbation is minor enough to be ignored by a human (or machine) reader.  Accordingly, the tamper-evident document 105 is visually perturbed from, but intelligibly equivalent to, the source image 101. In other words, the source information, which is perturbed when printed onto the print medium, is still readable by person or machine.
In order to improve the robustness of the alignment process in the validation sub-system 127, an optional, visually faint coarse alignment signal 128 from a coarse alignment source 111 is superimposed, by the merging module 114, onto the modulated composite cryptographic signal 118.  The coarse alignment signal is optional, because reliance can be placed on either (a) a manual registration mark approach, or (b) solely on the fine alignment process.  Provided that sufficient computing resources are available, the fine alignment process alone can be used to achieve alignment, noting that this approach requires that a search be instituted.  The disclosed fine alignment process will perform satisfactorily with either manual or alternate coarse alignment approaches.   Further, in order to prevent the potential recovery of the cryptographic signals 115, 116 by examination of the composite signal 120 from multiple different tamper-evident documents 105,…, 105', the private key (see a step 2501 in Fig. 6) that generates the cryptographic signals 115, 116 can be made from two parts.  The first part is fixed for multiple documents 105,…, 105' and this first part is required for the validation process performed by the validation sub-system 127 as it applies to any one of the documents 105,…, 105'.  The second part is referred to as a "salt" value 129 from a salt generator 112, the salt value being unique for each document 105,…, 105' (see steps 2508 and 2501 in Fig. 6).  Use of salt values is a known technique is the field of cryptography.  The salt value 129 is faintly embedded by the merging module 114 into the modulated composite cryptographic signal 118 of each respective tamper-evident document 105,…, 105'.  The salt value 129 is also provided, as depicted by an arrow 142, to the key generation module 134.  The salt value 129 is recoverable by a coarse alignment and salt recovery module 113, during the validation process.  Validation of the tamper-evident document 105 by the validation sub-system 127 thus requires the (common) first part of the private key and the salt value 129 that is specific to the tamper-evident document 105 as the second part of the private key.  Validation of the document tamper-evident 105' requires the (common) first part of the private key and the salt value specific to the document 105' as the second part of the private key.
A common first part 140 of the private key is provided to the validation sub-system 127 by, for example, administrative means (eg by providing the first part in a sealed envelope handed to an operator for manual input into the validation sub-system 127).  This part 140 is provided, as depicted by an arrow 141, to the crypto signal sources 102' and 103'.  The second document-specific part of the private key can be extracted by the validation sub-system 127 from each tamper evident document 105.
Turning to the validation sub-system 127 that is used for tamper-detection (also referred to as validation) a scan-based tamper-evident signal 120 is derived by scanning, using the scanner 2218 in Fig. 1, the tamper-evident document 105 that has been produced by the production sub-system 126.  The signal 120 contains a major component (purportedly reflecting the original information 117) and a minor component (purportedly introduced by the cryptographic signals 115, 116 under control of the selection module 104).  The coarse alignment and SALT recovery module 113 performs coarse alignment of the tamper-evident document 105 to produce a "coarsely aligned" scan based tamper-evident signal 121.  The salt module 113 also extracts the salt values from the signal 120 and provides the salt values, as depicted by arrows 139, to the crypto-signal sources 102' and 103'.  A fine alignment module 106 correlates the chroma component of the coarsely aligned signal 121 with a signal made by merging (i.e. averaging) the synchronised cryptographic signals 115', 116' and associated colours 138, 137 from lookup tables 134, 135.  The aforementioned merged cryptographic signals 115', 116' and the colours 137, 138 form a colour image version of the cryptographic signals 115', 116' as will be described in more detail in regard to Fig. 4. 
The signals 115', 116' are cryptographic signals from cryptographic signal sources 102', 103' that are typically physically separate from, but identical to, the cryptographic signal sources 102, 103.  The correlation performed by the fine alignment module 106 achieves fine scale synchronisation (i.e. alignment) between the coarsely aligned tamper-evident signal 121 and the cryptographic signals 115', 116' independently of the stronger major component that is human or machine readable in the tamper-evident document 105.  This alignment forms a "finely aligned" scan based tamper-evident signal 123. 
The validation process in the validation sub-system 127 then distinguishes, using a threshold module 107, between the major components of the cryptographic signals that are present in the finely aligned tamper-evident signal 123, to thereby form a bi-level signal 119. The bi-level signal 119 purports to be the (original) bi-level signal 117.  The purported document signal 119 is an N-level signal if the source signal 117 is N-level, and is 2-level for the present bi-level source example.  The finely aligned tamper-evident signal 124, which is the same signal as indicated at 123, is then compared in a comparison module 108, with either a value from a lookup table 134 that is associated with the first cryptographic signal 115' or a value from a lookup table 135 that is associated with the second cryptographic signal 116' under control of a selection module 109 that is switched according to the bi-level value of the signal 119 at the corresponding scan position.  The selection module 109 outputs a modulated composite cryptographic signal 125 according to the bi-level value of the signal 119 at the corresponding scan position.  Scan positions (which are equivalently referred to as pixel positions) where the minor components of the signal 119 from the tamper-evident document 105, and the minor components from the corresponding modulated composite cryptographic signal 125 do not match within a certain tolerance are revealed as having been tampered with (eg via introduction of alterations) by a validated signal module 110.
＜Detailed description of how the tamper-evident document is formed＞
The bi-level signal source 117 from the bi-level source image 101 represents, in the present example, a black and white document image in digital form.  This (source) image 101 can originate as the output of a rasterisation process (RIP), a scan, or other equivalent source.  In order to produce the tamper-evident document 105, a derivation of this source image 101 is marked onto the paper transfer media to become the tamper-evident document 105.  The validation (i.e. tamper detection) process performed by the validation sub-system 127 requires that the media (used for the document 105) support more than two distinguishable values for each sample of the original source image 101.  Thus the resolution of the original source image 101 must be such that this can be achieved. 
The tamper evident document 105 must have high enough resolution to hold the necessary information. For example, if the printer is a halftone device, distinguishable values are obtained by using collections of device pixels. 
The achievable spatial resolution varies with the printing technology.  For most modern printing technologies, including electro photographic (laser) printing and thermal inkjet technology, the resolution of the original source image 101 should be approximately 200 Dots-per-Inch (DPI).  In many cases higher resolutions are achievable.  Lower resolutions for the source image 101 become increasingly more robust (that is, tolerant of errors and degradation inherent in the printing and scanning process), however have the obvious quality disadvantage.
The cryptographic signal 115 from the cryptographic signal source 102, and the cryptographic signal 116 from the cryptographic source 103 are derived from two-dimensional cipher fields generated from a stream cipher.  In the described arrangement the cryptographic signals 115, 116 are generated using a master instantiation of the RC4 stream cipher with a 52-bit key.  The cryptographic signals 115, 116 are generated by directing alternating bytes from the single master RC4 stream first to one (eg 115), then the other cryptographic signal (eg 116).  Other stream ciphers or pseudo-random sequence generators can alternately be used, with different key lengths.  An example of another technique is to use a pair of maximal-period Linear Feedback Shift Registers to generate the cryptographic signals 115, 116.  This is described in more detail in relation to Fig. 6.
Fig. 3 shows a process 2300 as a flow chart of method steps for producing a tamper-evident document according to the disclosed anti-tampering approach using the system of Fig. 2.  The process 2300 commences with a step 2301, which reads the next pixel from the source image 101.  Thereafter a decision step 2302 determines the value of the aforementioned pixel.  In a bi-level case, to which the bulk of the present description is directed, the pixel that is read in the step 2301 will have one of two possible values.  In a general case, however, the source image 101 can have N levels.  In a general case, therefore, the decision step 2302 makes a determination as to which value the pixel read in the step 2301 has, noting that one of N values is possible.  If the step 2302 determines that the pixel value is equal to B, then the process 2300 is directed according to an arrow B to a step 2303.  The step 2303 determines a multi-level pixel value by (a) selecting a cipher field B, according to the pixel value, and then (b) selecting a value from the aforementioned cipher field depending on the position of the pixel in question, and finally (c) using the value chosen from the cipher field B to index a lookup table B in order to determine the multi-level pixel value.  A subsequent step 2311 stores this pixel value and then the process 2300 proceeds to a testing step 2304.  The step 2304 determines if more pixels are available in the source image 101.  If this is the case, then the process 2300 is directed by a YES arrow back to the step 2301.  
Returning to the testing step 2302, if it is determined that the pixel has a value A, then the process 2300 is directed according to an A arrow to a step 2305.  The step 2305 functions in a similar manner to the step 2303, after which the process 2300 is directed to the step 2311.  
Returning to the testing step 2302, if it is determined that the pixel has a value C then the process 2300 is directed in accordance with a dashed arrow C to a processing block (not shown) that is equivalent to the blocks 2303 and 2305.  In the general case where the source document 101 has N levels, then the decision step 2302 can make one of N decisions.  
Returning to the testing step 2304, if no further pixels are available then the process 2300 is directed according to a NO arrow to a step 2307.  The step 2307 merges the multi-level pixel data with the course alignment mark and the salt value.  Thereafter, a step 2308 prints the merged composite signal onto a print medium. This step results, as depicted by a dashed arrow 2309, in the tamper evident document 105 (see Fig. 2).
Fig. 4 shows a process 2400 as a flow chart of method steps for determining whether the tamper-evident document of Fig. 3 has been tampered with.  The process 2400 commences with the step 2417, which scans the secure document 105.  Thereafter, a step 2401 recovers the course alignment mark, after which a step 2402 performs course alignment of the tamper-evident document 105 to the cipher fields using the recovered course alignment mark.  A subsequent step 2422 recovers the SALT value from the document 105.  Thereafter, a step 2403 performs fine alignment between the tamper-evident document 105 and the cipher fields.  The fine alignment step 2403 comprises three sub-processes. A first sub-process 2403A performs block correlation to form a displacement map, as described in more detail in regard to Fig. 15.  A second sub-process 2403B performs interpolation in regard to the displacement map as described in more detail in regard to Fig. 17.  A third sub-process 2403C performs warping to form the finely aligned document, as described in more detail in regard to Fig. 18.  
A following step 2404 reads a next pixel of the scanned document 105 after which a testing step 2405 tests, for a bi-level source image 101, whether the major component of the pixel has the value A or the value B.  In a similar fashion to that described in relation to Fig. 3 if the source image 101 has N levels, then the testing step 2405 has N decision branches.  
In the present example if the pixel major component has the value A then the process 2400 is directed by an A arrow to a step 2407.  The step 2407 determines the purported minor component at the noted pixel position.  This is done by considering the cipher field A at the pixel position in question, and using this cipher field value to index the relevant lookup table (see 130 and 131 in Fig. 2).  This generates the purported minor component. Thereafter, a step 2417 reads the actual minor component value at the pixel position in question from the printed document 105.  A subsequent testing step 2409 checks whether the purported minor component value from the step 2407 equals the actual read minor component value from the step 2417 within some tolerance.  If this is not the case, then the process 2400 is directed by a NO arrow to a step 2415 that declares that tampering has taken place at the pixel position noted.  
Returning to the testing step 2405 if the pixel major component has the value B then the process 2400 is directed according to a B arrow to a step 2411.  The step 2411 functions in a similar manner to the step 2407, i.e., by referencing the cipher field B at the pixel position in question, and using the cipher field value to index the relevant lookup table 130 or 131 from Fig. 2 in order to determined the purported minor component at the pixel position in question.   Thereafter, the process 2400 is directed to the step 2417.  
Returning to the testing step 2409, if the purported minor component from the steps 2407, 2408 equals the actual read minor component from the printed document from the step 2417 to an acceptable tolerance, then the process 2400 is directed according to a YES arrow to a step 2413.  The step 2413 declares that no tampering has been detected at the pixel position of interest.  The process is then directed by an arrow 2414 to the step 2404.  From the step 2415 the process 2400 is also directed to the step 2404.  
＜Generating a two-dimensional cipher field＞
Fig. 5 depicts the generation of a two-dimensional cipher field (also referred to as a two-dimensional cryptographic field), and shows two approaches for generating two-dimensional cipher fields 306, 307 from a stream cipher.  Generation of cipher fields is performed both in the production sub-system 126 by the sources 102 and 103 (see Fig. 2), and in the validation sub-system 127 by the sources 102' and 103' (see Fig. 2) according to a process 2500 that will be described in relation to Fig. 6.
It is desirable to convert the stream ciphers into two-dimensional cipher fields in such a way that the cipher fields can be reproduced for use in the validation process with only the cryptographic key data.  In particular, it is desirable to avoid any dependence on the scanline length of the original source image 101, which would occur, for example, if the stream ciphers were simply converted to cipher fields in raster order.  It is also desirable to generate the cryptographic fields 306, 307 in raster order.  The fields 306, 307 are generated with respect to a nominal centre position of the source image 101, which is typically, although not necessarily aligned approximately with the spatial centre of the image 101. 
Considering the cipher field 306 in Fig. 5, a key K1 (ie 301) is a first 52 bit sequence generated for utilisation by one of the cryptographic signal sources (102 or 103 in Fig. 2).  Subsequent 52 bit segments of the stream cipher are assigned to key positions alternately above (eg at K2) the one previously generated (eg K1), and below (eg at K3) the one previously generated (eg K1).  In this manner a central spine 308 of initial 52 bit sequence keys is generated, the spine 308 being of any desired length in the vertical direction.  Each of these 52 bit keys K1, K2, …, is associated with a horizontal scanline (eg 305) of the cipher field 306 being generated. 
To generate any particular scanline (eg 305) of the cipher field 306, a second RC4 cipher generator is initialised with the key associated with that particular scanline. Thus, for example, the key K4, also referred to as 302, is used in relation to the scan line 305. Successive multi-bit "S" values are generated from the second RC4 cipher generator, and are alternatively associated to the right (eg at S41), then left (eg at S42), of previously generated "S" values on that scanline.  Each multi-bit "S" value forms a value (such as S42) in the cipher field 306.  Two cipher fields 306 and 306' (the latter not being shown), associated with the sources 102 and 103, are concurrently generated in order to maintain synchronisation with the master cipher stream.
The spine 308 is used to form the cipher fields 306 and 306', but the spine 308 does not form part of the cipher fields themselves.  The cipher fields 306, 306' are made up of the "S" values only.  The spine 308 (ie the "K" values) is formed of 52 bit keys, and the "S" values (which form the cipher fields) are 2-bit values in the present example.
Other methods of producing cipher fields are possible.  The reference numeral 307 shows another cipher field in which 303 indicates the commencement of an alternate spiral based arrangement of filling a raster grid 304.  This arrangement 307 has the advantage of only requiring a single stream cipher engine, but requires extra buffering in some implementations.
Although the absolute size of the cipher fields 306, 307 are not necessarily the same size as the source document 101, the S values of the cipher fields are referred to as being "congruent" with the pixels of the source image 101 so that there is a unique 1:1 correspondence between each pixel of the source image 101 and corresponding S values of the cipher fields output by the cryptographic signal sources 102, 103.  The alignment that is performed by the validation sub-system 127 re-establishes this congruency in order to perform the anti-tampering method.  
Fig. 6 shows a process 2500 as a flow chart of method steps for generating one of the cipher fields in Fig. 5.  The process 2500 is implemented by the key generating module 134 and the cryptographic signal source A (ie., 102) as described in relation to Fig. 2.  Turning to the key generation module 134 a first step 2508 in Fig. 6 generates a SALT value.  This is an optional step as depicted by the dashed outline for the step 2508.  Thereafter, a step 2501 generates a 52 bit private key, using the SALT value if this option has been elected.  A subsequent step 2502 generates an RC4 cipher stream.  A following step 2503 assigns successive 52 bit bytes of the cipher stream to successive cryptographic signal sources such as the source 102, as depicted by an arrow 135. An arrow 136 depicts how alternating 52 bit bytes are directed to the signal source 103.
Considering the signal source 102, a first process step 2504 assigns successive 52 bit bytes received from the key generating module 134 to spine positions of the cipher field as described in relation to Fig. 5.  Thereafter a step 2505, for each spine position, generates an RC4 stream cipher for the associated scanlines.  A following step 2506, for each scanline stream cipher, assigns successive two bit bytes to successive pixel positions on the scanline.  Thereafter a step 2507 outputs 2 bit cipher fields values.
＜Combining the original image and the cipher fields＞
Returning to consider Fig. 2, particularly in regard to the operation of the selection module 104, it is noted that for the selection operation (see the corresponding steps 2302, 2303 and 2305 in Fig. 3) the two cipher fields from the cryptographic sources 102, 103 and the original image from the source 101 are firstly aligned on their nominal centres.  At this selection stage (corresponding to the process 2312 in Fig. 3) the choice of alignment position is nominal.  The alignment position selected however, becomes locked and encoded into the tamper-evident image 105 and forms the basis for alignment in the recovery process (see Fig. 4) by the validation sub-system 127.
In the preferred arrangement, each value in each of the two 2-dimensional cipher fields such as 306 (see Fig. 5) that are generated by the cryptographic signal sources 102, 103 (see Fig. 2) has 2-bits of precision.  Accordingly, in the described example the source information 117 is bi-level, having 1-bit of precision, while the tamper-evident document 105 has two sets of four-levels, having 2-bits of precision each, giving a total of eight possible states for the corresponding printed form of each source document pixel.  The number of states (ie the amplitude resolution in this example) for each cipher signal (eg 115, 116 in Fig. 2) as the cipher signal relates to each input pixel (at 117 from the source image 101 in Fig. 2) can be varied.  The preferred arrangement uses 4 states (thus the 2 bits), however anything from 2 states upwards will be effective.
The choice of how many states to use for the cipher values 115, 116 influences the ability of a forger to "guess" what the correct value of the minor signal of a printed pixel on the tamper-evident document 105 will be when the forger changes the value of the pixel from black to white or vice versa.  The choice of 2 bits in the present example means that a forger will probably guess incorrectly 75% of the time, thus providing a strong indication of forgery with even small collections of pixels.
The multi-level (i.e. having more than one bit per pixel) tamper-evident image merged signal 122 (see Fig. 2) is generated for each pixel of the original source image 101 using the associated cryptographic signal value 115 or 116 from the corresponding cipher fields output by the associated cryptographic signal sources 102, 103 to index the respective lookup tables 130, 131.  In the preferred arrangement the output device used to print the tamper-evident document 105 is the printer 2215, which for the present example is a colour printer.  The multi-level image on the tamper-evident document 105 is a 24 bit RGB image in the present example.
Fig. 7 shows a particular example 406 of how the selection module 104 operates in conjunction with the cryptographic signal sources 102, 103 and their respective lookup tables 130, 131 (see Fig. 2).  The process 406 converts a bi-level pixel value in the source information 117 into a multi-level pixel value in the modulated composite cryptographic signal 118 (see Fig 2).  The arrow 2315 (see Fig. 3) leads to a step 401, which considers a pixel of the original source image 101.  If the pixel under consideration is black, the process 406 follows a "Yes" arrow to a step 402, which selects, from a B (for Black) cipher field, the 2 bit value from the position in the cipher field associated with the pixel being considered.  However, if the pixel is white, the process 406 follows a "No" arrow to a step 403 which selects, from a W (for White) cipher field, the 2 bit value from the position associated with the pixel under consideration.  The steps 401-403 are performed by the selection module 104 selecting between the cipher signals 115, 116 from the respective cipher sources 102, 103 (see Fig. 2).
If the pixel being considered is Black, then the 2-bit cipher value that is selected in the step 402 from the cipher field "B" is used to index a difference lookup table 404.  The pixels in the lookup table 404 are all either black, or some dark colour.  In the preferred arrangement, black and fully saturated red, green and blue are used.  If the pixel being considered is White, then the cipher value that is selected in the step 403 from the cipher field "W" is used to index a difference lookup table 405.  The pixels in the lookup table 405 are all either white, or some light colour. In the preferred arrangement, white, cyan, magenta and yellow are used.  These colours are used because they are easy to visually distinguish from each other, either by a human eye or using automatic video extraction techniques.  This selection of colours results in a robust validation system 127.  Other colours may, however, be used. The lookup tables 404, 405 are particular examples of the lookup tables 130, 131 in Fig. 2.
If, for example, the step 402 produces a cipher value "10" from the B cipher field, then this value "10" indexes the (RGB) lookup table 404 at "10" to result in an output of FF (in hexadecimal notation) for the R channel, 00 for the Green channel, and 00 for the Blue channel, which equates to an output of Red.
The steps 401-405 produce a multi-level pixel value that is stored at the step 2311 (see Fig. 3), after which the process 406 proceeds according to the arrow 2314 (see Fig. 3).
Non-colour based schemes can also be used.  For example, in a pure grey-scale scheme, different levels of grey could be used, as long as it is possible to discriminate between them in a high majority of cases after the security document has been printed and scanned.  Another method that can be used is a set of small patterns, one for each state of the cipher fields, of bi-level (typically black and white) device pixels, in a cell corresponding to each source document pixel. 
Fig. 8 shows a pictorial representation of conversion of a bi-level image 701 (such as that associated with the source image 101 in Fig. 2) to a multi-level image 705 (such as that associated with the tamper-evident document 105).  The original image 701, (which is a particular instance of the source image 101 in Fig. 2), is used to control a selection module 704, (which is a particular instance of the selection module 104 in Fig. 2), on a pixel by pixel basis. 
The selection module 704 selects, on a per-pixel basis controlled by pixel values 706 from the image 701, between the colour options of two cipher field derived colour grids 702 and 703.  The colour grids are generates as follows.  A pixel value for the pixel position 707 in the "black" colour grid 702 is determined by using a corresponding cipher value for the noted pixel position 707 in a "black" cipher field (not shown).  The black cipher field is a specific instance of the cipher field 115 that is generated by the corresponding cryptographic source 102.  The aforementioned cipher value from the black cipher field is used to index a multi-level colour value in a corresponding lookup table (not shown) similar to the table 404 in Fig. 7.  A pixel value for the pixel position 707' in the "white" colour grid 703 is determined by using a corresponding cipher value for the noted pixel position in a "white" cipher field (not shown), to index a multi-level colour value in a corresponding lookup table (not shown) similar to the table 405 in Fig. 7. 
Since the pixel value at a pixel position 708 in the original image 701 is white, the selection module 704 selects the colour value of the pixel position 707' in the colour grid 703 to be inserted at the pixel position 708' in the tamper evident image 705.
The pixels 709 will be referred to in regard Fig. 19 in relation to tamper detection.
＜The coarse alignment mark＞
Fig. 9 shows a bi-level representation of a two-dimensional linear corrugated function used for alignment.  In order to aid the precision alignment that is performed by the fine alignment module 106 used in the validation sub-system 127 in Fig. 2, a coarse alignment mark using the corrugated function of Fig. 9 is incorporated by the coarse alignment source 111 and the merge module 114, into the composite cryptographic signal 118 to form the multi-level image printed onto the tamper-evident document 105 (see Fig. 2).  In the preferred arrangement a faint coarse alignment pattern image using the function depicted in Fig. 9 is mixed by the merge module 114 with the modulated composite cryptographic signal 118 (see Fig. 2).  This mixing is performed by addition or subtraction of suitable values to one or more of the color channels of each pixel value in the modulated composite cryptographic signal 118.  The amount added is too small to affect the discrimination between colors that will be performed by the threshold module 107 in the validation process 127.  The alignment pattern is formed from a particular configuration of the one-dimensional scale invariant functions shown in Fig. 9 that can be efficiently detected using Fourier methods.  The particular configuration of the one-dimensional scale invariant functions that is selected is chosen so that the symmetry axes of the functions intersect at points that define line segments that have certain ratios of lengths that are invariant under affine transformations.  This will be described further in regard to Fig. 12, particularly in regard to step 1790.
The alignment pattern image is a superposition of four 1-dimensional scale invariant patterns as shown in Fig. 9 that have been extended in the transverse direction to cover the source image 101 of Fig. 2.  A single one-dimensional scale invariant pattern may be represented mathematically as follows:
2006014280.tif 000068
where γ is a constant that specifies how quickly the pattern oscillates (the faster the oscillations the smaller a distance 501 becomes) and x0 specifies a line of symmetry 502 for the pattern. 
Fig. 10 shows a graphical representation of the linear corrugated function depicted in Fig. 9. It is noted that a one dimensional scale invariant pattern that has been extended in the transverse direction is specified by two parameters, its radius, r, and its angle, α.  The two-dimensional functional form (shown in Fig. 9) of such a pattern is represented mathematically by:
2006014280.tif 000069
where r(see 503 in Fig. 9) is the radius of the pattern, and α(see 504 in Fig. 9) is its angle.
The four one-dimensional scale invariant patterns that are superimposed to form the desired alignment pattern (at 128 in Fig. 2) have r and α parameter values that give them a particular spatial configuration relative to each other (see Fig. 11) that is advantageous in determining the alignment of the tamper-evident document 105 into which the alignment pattern 128 has been incorporated.  This spatial configuration is represented in Fig. 11.
Fig. 11 shows a configuration of axes of symmetry from linear corrugated functions used in alignment detection.  As will be described further in regard to Fig. 14, the set of parameters establishing these axes of symmetry are specially chosen so that the symmetry axes define line segments that have certain ratios of lengths (exemplified by the ratio 1101:1102) that are invariant under affine transformations.
In the preferred arrangement the original source image 101 has a minimum pixel dimension of at least 1024 pixels in both the width (x) and height (y) dimension, although it may be larger in either or both.  This minimum pixel dimension is referred to as Nmin in the equations below. In general, the source image 101 has dimensions of N pixels wide by M pixels high where  M≧Nmin. and N≧Nmin.  The values of the pattern parameters r and α for the 4 patterns used to form the alignment mark 128 are as follows:
2006014280.tif 000070
where:
2006014280.tif 000071
The Nyquist radius RNYQ, is also specified. The Nyquist radius is the number of pixels from the axis of symmetry of the pattern where the frequency of the pattern is equal to the Nyquist frequency of the image.  The distance from the axis of symmetry to the first visible corrugation represents the Nyquist frequency.
For the jth pattern, with parameters rj and αj the intermediate quantities Dj, Xj, Yj, and Rj are pre-calculated as follows:
2006014280.tif 000072
The "influence", Pj(x,y), of the jth pattern to the pixel at offset (x, y) is given by
2006014280.tif 000073
The influence of the patterns are used to suitably scale the alignment and salt signals (128 and 129 respectively) in order not to unacceptably distort the source image 101 while allowing the anti-tampering approach to be effectively performed.
＜Adding a SALT value to prevent dictionary attacks＞
Returning to Fig. 2, if the same cryptographic key (such as generated by the step 2501 in Fig. 6) is used to generate more than one page of the tamper-evident document 105, the cipher fields 115, 116 generated by the cryptographic signal sources 102, 103 are potentially discoverable by harvesting light and dark areas from different pages of the document 105.  To prevent this possibility, the preferred arrangement employs a salt value provided by the salt generator 112.  A salt is a known technique in the field of cryptography for preventing dictionary attacks.  The salt technique can also be used in this case to prevent attacks based on the similarity of the cipher stream on two different pages of the tamper-evident document 105. 
In the preferred arrangement, it is desired that keys such as are generated by the step 2501 in Fig. 6 be well known to the generator (i.e. the user of the production sub-system 126) of the tamper-evident document 105 and to the verifier thereof (i.e. the user of the validation sub-system 127).  However, to prevent attacks based on the similarity of the cipher stream for two pages of the tamper-evident document 105, a different key should be used for each page thereof.  To achieve both these aims, the preferred arrangement forms the keys in two parts.  The first part of the key, say of length 40 bits, is well known to both the production sub-system 126 and the validation sub-system 127.  This first part is the same for each page of the tamper-evident document 105.  The remaining part of the key, i.e. the salt of length 12 bits in this case, is different for each page of the tamper-evident document 105.  This salt is generated cryptographically (i.e. using effectively "random" numbers) for each page of the tamper-evident document 105.  The salt value is embedded in the associated page without being encrypted.  The actual 52-bit key generated by the step 2501 in Fig. 6 which is used for each signal 115, 116 in the production sub-system 126 and 115' 116' in the validation sub-system 127 is the concatenation of the fixed 40 bits with the 12 bit salt.
The 12 cryptographically (randomly) generated salt bits are divided into 2 6-bit sections sa and sr these sections representing, respectively, the angle and position of a fifth scale-invariant pattern similar to those shown in Figs. 9 and 11. Both sa and sr can assume 64 distinct values.  This fifth scale-invariant pattern having a particular angle and position is embedded into the signal 118 to thereby form the tamper-evident document 105 in the production sub-system 126.  The validation sub-system 127 extracts this fifth pattern, thereby determining the associated angle and position of the pattern.  This angle and position establish the 2 6-bit salt value sections.  The fifth scale-invariant pattern is embedded in the same manner described for the other four patterns, except with a different oscillation constant γ, in particular:
2006014280.tif 000074
where:  The parameters are calculated as:
2006014280.tif 000075
The selection of a different oscillation constant for the fifth pattern causes some degree of separation in the detection space between the SALT value and the coarse alignment pattern. Interference can be further reduced by avoiding particular angles that are close to the angles used in the coarse alignment mark.
＜Merging the coarse alignment and SALT patterns＞
Turning to the function of the merging module 114 in Fig. 2, the net influence caused by the alignment and salt patterns is determined by the sum 
2006014280.tif 000076
This value ranges from -5 to 5.  The value is then scaled up to range from -15 to 15 and added directly by the merging module 114 to each channel of the modulated composite cryptographic signal 118, this being a multi-level RGB image, clamping the result to the range 0 ... 255.  This scaling operation enables the coarse alignment mark and the SALT value to be extracted from the document 105 while not unduly perturbing the original source information 101 in the document 105.  
＜Result of the marking process＞
The final multi-level image at 122 of Fig. 2 is printed onto the tamper-evident document 105 using the colour printer 2215 which can, for example, be a Canon IR C3200 electro-photographic multi-function copier or a Canon i950 thermal inkjet printer. Scaling of the 200DPI image to the printer resolution is preferably achieved with simple pixel replication.  For example, a Canon IR C3200 has a device resolution of 600DPI. For this printer each of the 200DPI pixels of the final multi-level image is replicated in a 3x3 group of the IR C3200 device pixels.  
The result of the marking process effected by the merging module 114 is the printed document 105 that is human-readable by virtue of the light and dark areas that correspond to the black and white values of the original bi-level digital image 101.  An illustration of this marking is depicted in Fig. 8.
Returning to Fig. 8, it is noted that the light and dark areas such as 707' and 707 respectively each contain a minor component, respectively depicted by uni-directional cross hatching at 707' and bi-directional cross-hatching at 707.  These minor components, in the absence of the key that generates them, contain no useful information, and cannot easily be forged.  However there is an exact correspondence between the presence of the two minor components, and the overall darkness and lightness of each pixel that respectively represent the major components at each pixel.  An inspector with knowledge of the respective major and minor components can verify the existence or lack of this correspondence.  It is improbable that a forger could appropriately change a pixel (i.e. with respect to the major component) from light to dark (or vice versa) because the forger will not be able to correspondingly change the associated minor component.  The forger cannot maintain the correspondence because the forger does not know the value of the minor components for an alternate major component at a given pixel position.
＜The verification process＞
Turning to the validation sub-system 127 in Fig. 2, the tamper-evident document 105 which is to be verified is first scanned with the colour scanner 2218 (see Fig. 1) to produce a 24 bit RGB tamper-evident signal 120.  The scan resolution of the scanner 2218 must be higher than or equal to the resolution of the original image 101.  In the preferred arrangement a 600DPI scanner 2218 is used, which provides a generous margin over the 200DPI original image 101 (see Fig. 2). 
＜Overview of the coarse alignment process＞
Turning to the operation of the coarse alignment and salt recovery module 113 in Fig. 2, the coarse alignment pattern (which comprises, in the present example, four alignment marks that were faintly added by the merge module 114 to the signal 118 before printing the tamper-evident document 105) is detected and analysed to produce an affine transform that relates the orientation of the scanned document 120 to the cipher fields.
Fig. 12 shows the coarse alignment process 2419 of Fig. 4 that is performed by the coarse alignment and salt recovery module 113 of Fig. 2.  The scanned document, in the form of the luminance channel of the scanned tamper-evident signal 120, is first resized in a step 1710 by a process of successive halving until a resultant image is sized such that the smallest of the width and height are in the range 256 to 511 pixels.  The halving process may be performed by convolving the image, in the form of the signal 120, with a low-pass filter and decimating the result of the convolution.
The resulting resized image then undergoes a two-dimensional Fast Fourier Transform (FFT) in a step 1720, and the result is resampled in a step 1730 into a quasi-polar frequency space.  The step 1730 can use a direct polar transform of the two-dimensional FFT from the step 1720 by resampling the FFT onto a polar grid using bicubic interpolation.  Whilst simple, this method produces artefacts that can adversely affect detection. A preferred quasi-polar method used in the step 1730 is described with regard to Fig. 13.
Preferably, before computing the FFT in the step 1720, the image values (intensities) near the image edges are first attenuated so that the image values fade to zero gradually and smoothly towards the edges of the image.  The step 1730 produces a complex image where horizontal rows correspond to radial slices in the two-dimensional FFT that resulted from the step 1720.  The angular spacing and the radial scaling need not be constant.
In a step 1750, a one-dimensional Fourier transform of a one-dimensional basis function provided by a step 1740 is performed.  The basis function provided by the step 1740 is described mathematically as:
2006014280.tif 000077
where this equation is a complex version of equation (1). Accordingly, γ is a constant that specifies how quickly the pattern oscillates and x0 specifies the symmetry point for the pattern.  Alternatively, the basis function from the step 1740 can be mathematically transformed.  That is, the analytic solution to the Fourier transform of equation (9) can be derived and used to produce 1750 directly. 
Next, the transform of the basis function resulting from the step 1750 is multiplied in a pixel by pixel fashion in a step 1760 with the complex conjugate of the values of the output of the step 1730 along horizontal rows (that represent radial lines in the two-dimensional FFT) for all angle values.  The resultant complex pixel values are then normalized by the step 1760 so that they have, at most, unit magnitude.  A step 1770 then determines a one-dimensional Inverse Fast Fourier Transform (IFFT) of the output of the step 1760 along horizontal rows. 
The result of the step 1770 is a complex image which has peaks in image magnitude corresponding to the orientation and scale of the 1-D basis functions (i.e. the four alignment marks) within the scanned document signal 120 in Fig. 2.  These peaks are detected using a peak detection process 1780 (that is described in more detail in regard to Fig. 14).  Finally, in a step 1790 the location of the peaks detected in the step 1780 are used to determine the affine parameters that relate the scanned document at 120 in Fig. 2 to the digital form of the cipher fields 115' and 116' in Fig. 2. 
In the step 1790, the affine transformation corresponding to the combination of 4 peaks that gives the best least squares fit to an affine transformation of the intersection points is selected as the affine transformation that relates the orientation of the scanned document at 120 in Fig. 2 to the orientation of the cipher fields 115' and 116' in Fig. 2.  The details of the least squares fit are described in a later section.
The affine transform is then used in step 2402 of Fig. 4 to transform the scanned document, using bi-cubic interpolation.  This forms the signal 121 (see Fig. 2) that represents the coarsely aligned scanned document. This document has a resolution, in the present example, of approximately 600DPI. 
＜Details of the quasi-polar mapping process＞
In the described arrangement, the preferred method of performing the invariant pattern matching for coarse alignment uses the Chirp-Z transform to provide a quasi-polar transform (see the step 1730 in Fig. 12) of the Fourier transform performed by the step 1720.  The Chirp-Z transform is a method for computing a scaled portion of a Fourier Transform of a signal.
Fig. 13 shows the step 1730 of Fig. 12 in more detail. Fig. 13 shows a process for performing a quasi-polar transform in order to calculate a quasi-polar mapping of a Fourier Transform.  In a step 1810 the resized image 1801 having size (X,Y), that is output by the step 1720 of Fig. 12, is replicated into two copies I1 and I2 (referred to by respective reference numerals 1802 and 1803). In a step 1820, the first copy I1 is padded with zeros in the X direction to a width of W=2*MAX(X,Y), resulting in an image 1804 of size (W,Y).  The padding is performed so that column offset 
2006014280.tif 000078
in I1 corresponds to column offset 
2006014280.tif 000079
in the padded image 1804.
In a step 1830, the second copy I2 is padded with zeros in the Y direction to a height of W to form an image 1805, and in a step 1840 the image 1805 is rotated by 90 degrees resulting in an image 1806 of size (W,X). The padding is performed so that row offset 
2006014280.tif 000080
in I2 corresponds to row offset 
2006014280.tif 000081
in the padded image 1806.
In steps 1850 and 1860, the images 1804 and 1806 are transformed by computing the one-dimensional Fourier transform of each row to respectively form the transformed images 1807 and 1808.
In steps 1870 and 1880, the images 1807 and 1808 are transformed by computing individual chirp-Z transforms on each of the columns to form the transformed images 1809 and 1811.
Each chirp transform performed by the steps 1870 and 1880 is performed to preserve the centre position of each column, at positions 
2006014280.tif 000082
within the columns for the steps 1870 and 1880 respectively.
The scaling factors  for each column z in the steps 1870 and 1880 are
2006014280.tif 000083
Each scale factor mz is negative for 
2006014280.tif 000084
corresponding to a vertical flip. Where the scaling factor is undefined for 
2006014280.tif 000085
the central pixel position is replicated across the whole column.
Assuming a square image from the tamper-evident document 105, the transformed images 1809 and 1811 represent quasi-polar transforms of the Fourier Transforms of the resized, windowed input image, with 1809 having angles within the range [-π/4..π/4], and 1811 having angles in the range [π/4.. 3π/4].  If the image from the tamper-evident document 105 is rectangular, the angular ranges will be from [-atan2(Y,X)..atan2(Y,X)] and [atan2(Y,X) ..π-atan2(Y,X)].  Because each row of the quasi-polar transform contains positive and negative radii, it has all angles within [0..2π] radians.
In a step 1890, the two input images 1809 and 1811 are combined to form an image, 1812, of dimension (W,Y+X), by replicating the pixels of image 1809 into the top part of 1812 and replicating the pixels of image 1811 into the bottom part of 1812.
＜Details of the peak detection process＞
Fig. 14 is a flow diagram showing one example of the peak detection process 1780 in Fig. 12.  The result of the step 1770 in Fig. 12 is a complex image which has peaks in image magnitude corresponding to the orientation and scale of the 1-D basis functions (i.e. the four alignment marks) within the scanned document signal 120 in Fig. 2.  The input to the peak detection step 1780 is thus referred to as a correlation image 1610, which is the aforementioned complex image in which we wish to find the location of the highest P peaks (in the preferred arrangement, P is 64), or in other words the P highest local maxima of the magnitude of the correlation image. 
Peaks may occur in noisy regions where there are many peaks clustered close together.  It is preferable to only consider the largest peak within a certain radius threshold, and a default radial threshold of 10 pixels is chosen.  In a step 1620, the correlation image 1610 is scanned and a list of points where the magnitude of the pixel value is greater than all of its neighbours is constructed. In a next step 1630, this list of peaks is sorted in order of the magnitude of the pixel values.  In a next step 1640, each peak in the sorted list is considered in decreasing order of magnitude, and any peak that is after it on the list that is within the radial distance threshold is removed from the list.  In a next step 1650, the sorted list of peaks produced by the step 1640 is truncated to a list P in length. 
The aforementioned truncated list contains the locations of the P peaks that can be found with high precision. In a step next 1660, a loop is entered that takes each of the P peaks in turn, and in a following step 1670 a 27 pixel by 27 pixel region centred on the location of the peak being considered is input to an FFT and then input into a chirp-z transform which zooms in on the peak by a factor of 27.  The chirp-z transform allows computation of the discrete Fourier transform (DFT or the inverse DFT) with arbitrary spacing.  The chirp transform is performed by expressing the DFT as a discrete, cyclic convolution.  Because such convolutions can be implemented using FFTs it is possible for the entire computation to take advantage of the FFT speed.  By suitable choice of spacing, the chirp-z transform becomes an interpolation technique, so that, for example, a DFT can be finely sampled (that is to say zoomed) over a selected region.
The pixel in this 27 by 27 image with the highest magnitude is determined in a following step 1680, and the sub-pixel location of this peak is determined using a biparabolic fit.  This sub-pixel accurate peak location is the output of the peak detection step 1780.
＜Using the detected peaks to determine coarse alignment＞
The peaks output from the step 1780 in Fig. 14 (see also Fig. 12) are then further processed by the step 1790 in Fig. 12 by selecting, in turn, each possible combination of 4 peaks and performing the following analysis, keeping track of which combination of 4 peaks best satisfies the conditions of this analysis. 
The radius and angle of each peak si and βi are computed from its (x, y) offset in the quasi-polar map 1812 in Fig. 13. 
This conversion from of quasi-polar coordinates in 1813, (x,y), to polar coordinates (s,β) is computed as follows:
The input image, 1812 is of size (W,X+Y) pixels, and the following parameters are set:
2006014280.tif 000086
If y＜Y,
2006014280.tif 000087
else if y≧Y,
2006014280.tif 000088
where Y2, X2, W2, ys and xs are intermediate values. 
An affine transformation described by linear transformation parameters (a11, a12 , a21, a22, x0, y0) that maps the original set (from equation (3) and reproduced at equation (14) for convenience) of one-dimensional basis function parameters ri and αi to parameters si and βi is determined from the 4 selected peaks.  The pre-defined set of one-dimensional basis function parameters used in the security document 105 with alignment mark embedded are reproduced from (3) as follows:
2006014280.tif 000089
with
2006014280.tif 000090
where N is 1024.
This set of parameters has been specially chosen so that the symmetry axes of the one-dimensional basis functions they represent intersect at points that define line segments that have certain ratios of lengths that are invariant under affine transformations. 
The first condition that the combination of 4 peaks must satisfy is that they generate sets of line segments with the correct length ratios (eg see 1101:1102 in Fig. 11).  If they do not generate sets of line segments with the correct length ratios then the combination of peaks does not correspond to the four original basis patterns modified by an affine transform and this combination can be discarded.
As previously described, the radial and angular coordinates of a peak, si and βi, describe the axis of symmetry of one of the one-dimensional scale invariant patterns embedded in the security document. Rather than determine the affine transform applied to the image through the changes in these line parameters directly, the affine transform is determined from the intersection points of the 4 axes of symmetries specified by the 4 selected peaks.  The intersection of two axes of symmetry lines {sk,βk} and {sm,βm} is labelled (xkm,ykm), and is given by the matrix equation (16) as follows:
2006014280.tif 000091
There is no intersection if the lines are parallel, and so the equivalent constraint sin(βk-βm)≠0 is imposed.  In practical situations sin2(βk-βm)≧0.25 is sufficient to ensure good localization of the intersection point.  The parametric equation of a line specifies the linear distance of any point on that line relative to the perpendicular bisector of that line that passes through the origin. In the current case of four mutually non-parallel lines, each line has three intersection points along its length (eg see points 1103-1105 for the line 3 in Fig. 11) and the ratio of the intersection intervals (1101:1102 for the line 3 in Fig. 11) remains invariant to affine distortions. The distance λkm, along the kth line where the mth line intersects, is given by
2006014280.tif 000092
The above equation (17) is then enumerated for all combinations λkm, all k≠m and a table (18) generated which contains the locations along lines as follows:
2006014280.tif 000093
The parameters in (18) are then ordered by size as follows:
{λkm}max＞{λkm}mid＞{λkm}min, m＝1→4 of each line k, in order to thus find the length ratios Rk' as shown in (19) as follows:
2006014280.tif 000094
This generates 4 ratios from the 4 axes of symmetry.  There are also 4 ratios that may be generated from the original set of one-dimensional basis function parameters ri and αi.  If these (original) ratios are denoted as Rk then the error in the ratio measure for the selected set of 4 peaks is defined as:
2006014280.tif 000095
If this error is greater than 0.1 this set of peaks is discarded. If it is less than 0.1, a linear least squares fitting model is applied to determine the best fitting affine transform that maps the set of intersection points of the axes of symmetry generated by the 4 selected peaks back to the original set of intersection points of the axes of symmetry of the embedded pattern.  The method of finding the best fitting affine transform is described in a later section.
＜Extracting the salt value＞
Returning to Fig. 4, once the coarse alignment marks have been recovered, and the coarse alignment has been performed according to the steps 2401 and 2402, next the salt is recovered in the step 2422.  The peak corresponding to the salt pattern is recovered using the same methods described above for the coarse alignment marks.  The strongest detected candidate peak of the basis pattern with the salt oscillation constant γ is used and the two 6 bit values recovered from the angle and radius of the detected peak.  These are combined to form the 12 bit salt value.
＜Regenerating the cipher fields and a composite cipher alignment image＞
Preparatory to the precision alignment step 2403 in Fig. 4, it is necessary to regenerate the cipher fields in the validation sub-system 127 of Fig. 2. This can done in the same manner described in relation to Figs. 5 and 6, using the original key (see 2501 in Fig. 6), which may be entered by an operator, or known to the validation sub-system 127, or transferred from the production sub-system 126 or by some other means.  The original key (used by the step 2501 in Fig. 6) is combined with the salt value (from the step 2508 in Fig. 6) in the same manner as previously described.  The cipher fields are then generated by the cryptographic signal sources 102' and 103' in Fig. 2 in the same manner as described in relation to the sources 102, 103.  The spatial area of cipher field generation by the sources 102' and 103' can be limited to the equivalent area of the coarsely aligned scanned document 121, as determined by the coarse alignment steps 2401-2402 (see Fig. 4) that is performed by the coarse alignment and salt recovery module 113 in Fig. 1.
Next, colour image versions of the cipher fields generated by the sources 102', 103' are created in the fine alignment module 106.  Each of these colour image versions (referred to as cipher field derived colour grids in relation to Fig. 7) is created by indexing the 2 bit cipher value at each pixel into the colour lookup tables 134, 135 in the same manner as described in relation to Fig. 7.  Each resultant colour image version of each cipher field is then up-scaled by a factor of 3 in each dimension by pixel replication to form a 600DPI image (the same resolution as the scanned document 120).  This forms the "full size" colour image versions of the cipher fields.  Finally, a composite colour image version of the cipher fields is generated by averaging the two colour image versions of the cipher fields.
＜Fine alignment by block based matching＞
Fig. 15 shows the block based correlation sub-process 2403A used to form a displacement map in the fine alignment process 2403 in Fig. 4.  The process 2403A generates a displacement map D that represents the warp (i.e. the fine grain deliberate pre-distortion) that is required to map the pixels of the coarsely aligned scanned document at 121 in Fig. 2 to the respective pixel positions of the colour cipher fields.  This warping takes account of distortion that may have taken place in the coarsely aligned scanned document because of the print/scan operations performed by the printer 2215 in printing the tamper-evident document 105, and by the scanner 2218 in scanning the document 105 to produce the tamper-evident signal 120.  This warping constitutes part of the fine alignment of the coarsely aligned document 121 and the cipher fields 115' 116'.
The block based correlation process 2403A receives as inputs (a) the coarsely aligned scanned document at 121 in Fig. 2 (referred to as 2010 being image 1 in Fig. 15), which is N pixels wide and M pixels high, and (b) the composite colour image version of the cipher fields (referred to as 2020 being image 2), which is also N pixels wide and M pixels high.  As image 1 (i.e. 2010) is the result 121 of the coarse alignment steps 2419 in Fig. 4, the two images 2010 and 2020 are roughly aligned, to within a few pixels of each other. 
The block based correlation process 2403A involves selection of a block size Q and a step size P.  These sizes can be varied. Larger sizes of Q give more measurement precision, at the expense of averaging it over a larger spatial area (and more computation time).  Smaller values of P give more spatial detail, but increase computation time.  For the example being considered, Q＝256 and P＝32.  This represents a block 256 pixels high by 256 pixels wide, stepped along the images 2010 and 2020, in both horizontal and vertical directions, in 32 pixel increments. 
Fig. 16 depicts the choice of blocks for correlation, and is an illustration of the block size and step size of the blocks in the block correlation process 2403A.  A correlation block 2100 is shown on the Image 1 (i.e. 2010).  The block 2100 has horizontal and vertical dimensions "Q".  The block 2100 is stepped in the horizontal direction in increments "P" (referred to as 2101 ) and in the vertical direction in increments "P" (referred to as 2102).
Returning to Fig. 15, the output of the block based correlation process 2403A at the step 2080 is the displacement map "D".  The displacement map D is a raster image whose dimensions are defined by (21) as follows:
2006014280.tif 000096
where: Dx is the horizontal dimension, Dy is the vertical dimension, N is the width of the image 2010 in pixels, M is the height of the image 2010 in pixels, and Q is the selected block size.
The number of elements is Dx * Dy. P is fixed.  Each element of the displacement map D comprises a displacement vector and a confidence estimate.  Each displacement vector and confidence estimate in the displacement map D is the result of a block correlation.
Processing of the images 2010 and 2020 begins by entering a loop in a step 2030 over all correlation blocks Bp and Bq from the images 2010 and 2020 where the correlation block subscripts "p" and "q" vary over [0 .. Dx-1] and [0 .. Dy-1] respectively. For a given pair of blocks Bm and Bn from the respective images 2010 and 2020, and considering a pixel (i, j) in the displacement map D, the block Bm and the block Bn each have their upper left pixel at a pixel offset from the pixel (i, j) expressed at (22) as follows:
2006014280.tif 000097
where the first term in (22) represents the offset in the horizontal direction, and the second term represents the offset in the vertical direction.  
In a following step 2040, a check is performed to see if the selected blocks Bm and Bn lie wholly within their respective images 2010 and 2020. If this is not the case, the confidence estimate for pixel (i, j) in D is set to 0 and the loop continues. If however the blocks Bm and Bn do lie wholly within their respective images 2010 and 2020, then a following step 2050 generates Yuv colour space versions of the (RGB) blocks Bm and Bn. The step 2050 then treats the u as a real components and the v as the imaginary components from the corresponding Yuv blocks to form respective new complex images B"m and B"n from the blocks Bm and Bn.  The new blocks B"m and B"n, being based on the u and v values, reduce the effect of the major component which is primarily confined to the Y component of the Yuv colour space.  The step 2050 further multiplies the new blocks B"m and B"n by a window function to form respective windowed blocks B'm and B'n.  The described arrangement uses a Hanning window squared in the vertical direction and a Hanning window squared in the horizontal direction.  A following step 2060 then phase correlates the two windowed blocks B'm and B'n.
The correlation step is performed using phase correlation, in which the FFT of the block B'm is multiplied by the complex conjugate of the FFT of the block B'n, and the result of this multiplication, referred to as Bphmn, is normalised to have a maximum of unit magnitude, the normalised result being referred to as Bphnmn. The step 2050 then applies an inverse FFT to Bphnmn to form a correlation block referred to a "C".
The correlation block C is a raster array of dimension Q by Q (for the present example) of complex values that is then input to a peak detection step 2070.  The step 2070 is similar in operation to the peak detection step 1780 in Fig. 12.  The step 2070 determines the location of the highest peak in the correlation block C, relative to the centre of the block C, to sub-pixel accuracy. In a step 2080 this sub-pixel accurate location relative to the centre of the block C is stored in the displacement map D at location (i, j) along with the square root of the peak height as a confidence estimate of the result of the correlation.  The loop 2030 continues until there are no blocks left to process.  
Next, as will be described in relation to Fig. 17, an interpolation process 2403B takes the displacement map D that is output from the block correlation sub-process 2403A of Fig. 15 and forms a distortion map D'.  The distortion map D' relates each pixel in the coarsely aligned scanned document 121 to a pixel in the coordinate space of the cipher fields. Some parts of the distortion map D' may map pixels in the coarsely registered document 121 to pixels outside the boundary of the cipher fields.  This is because the imaging device may not have imaged the entire document.
Fig. 17 shows the interpolation process 2430B for interpolating the displacement map D to form the distortion map D'.  The interpolation process 2430B receives, at a step 1910, the displacement D map that was stored in the step 2080 of Fig. 15. A following step 1920 takes the displacement map D and determines a set of linear transform parameters, (b11, b12, b21, b22, Δx, Δy) that best fit the displacement map D. 
An arbitrary point (xij, yij) in a cipher field (noting that the x,y position of such a point has not suffered positional distortion in contrast to the pixels in the document 121) maps to a corresponding pixel (i, j) in the displacement map D according to the following mathematical relationship:
2006014280.tif 000098
The cipher field point is displaced using the displacement map to yield corresponding displaced cipher field point coordinates 
2006014280.tif 000099
by performing the following operation:
2006014280.tif 000100
where D(i, j)is the displacement vector part of the displacement map D for the pixel (i,j) being considered.
The linear transformation parameters (b11, b12, b21, b22, Δx, Δy) when applied to the undistorted points (xij, yij) yield affine transformed points 
2006014280.tif 000101
as follows:
2006014280.tif 000102
The best fitting affine transformation is determined by minimising the error between the displaced coordinates 
2006014280.tif 000103
, and the affine transformed points 
2006014280.tif 000104
by changing the affine transform parameters.  The error functional to be minimised is the Euclidean norm measure E that is defined as follows:
2006014280.tif 000105
The minimising solution is given by the following:
2006014280.tif 000106
with
2006014280.tif 000107
2006014280.tif 000108
and
2006014280.tif 000109
where the sums are carried out over all displacement pixels with non-zero confidence estimates on the displacement vectors in the displacement map D.
A following step 1930 removes the best fitting linear transformation from the displacement map by replacing each displacement map pixel as follows:
2006014280.tif 000110
A following step 1940 then interpolates the displacement map, after the best fitting linear transform has been removed by using bi-cubic interpolation, to a displacement map of dimension DxP by DyP.  A complication can arise in the interpolation step if the displacement map has a pixel with zero confidence in the neighbourhood of the bicubic interpolation kernel. If this occurs, the pixel with zero confidence is itself substituted by an estimated value using an average of neighbouring pixels weighted by their confidence value.  If no neighbouring pixels have positive confidence, a region growing algorithm is used to determine the pixel value.  The interpolated displacement pixel is then computed using bicubic interpolation using the pixels with positive confidence along with the substituted pixels in the displacement map. 
A following step 1950 reapplies the previously removed best fit linear distortion to the interpolated displacement map D' as follows:
2006014280.tif 000111
where in this case
2006014280.tif 000112
The map D'(i, j) is the distortion map and forms the output from the step 1950 in the interpolation process 2403B.
＜Image warping for fine alignment＞
Fig. 18 shows the warping process 2403C that is used to form the finely aligned document from the distortion map D' from the step 1950 of Fig. 17. The image warping process 2403C takes as inputs the scanned document 121, the affine transformation parameters generated by the coarse registration process in step 1790 of Fig. 12 and the distortion map D' from the step 1950 in Fig. 17, and outputs a warped form of the scanned document, which is referred to as the precisely aligned scanned document, that is accurately registered to the colour cipher fields. The first step 2601 in the image warping process 2403C modifies the distortion map D' to a relational map D'c relating pixels in the cipher fields to pixels in the scanned document 121. This is done by adding the affine transformation determined in the coarse registration step (step 1790 of Fig. 12) back into the distortion map D' by performing the following: 
2006014280.tif 000113
where (a11, a12, a21, a22, x0, y0) are the affine transformation parameters determined in the coarse registration step. 
Thereafter, still in the step 2601, pixels in the scanned document 121 corresponding to pixels in the cipher fields are identified by (a) using this relational map D'c to determine, for each pixel in the scanned document 121, the sub-pixel location on the scanned document 121 that corresponds to the pixel position in the cipher fields, and (b) interpolating the scanned document 121 at that location using bi-cubic interpolation.
A following step 2602 forms an empty image Ie that is the same size as the coarsely aligned scanned document 121. Thereafter a step 2603 reads the next pixel in the aforementioned empty image Ie.  A following decision step 2304 tests whether all pixels in Ie have been processed.  If this is the case, then the process 2403C is directed according to a YES arrow, this being the arrow 2423 in Fig. 4, to output the finely aligned document at 2423 (see Fig. 4).  If on the other hand unprocessed pixels remain in Ie, then the process 2403C is directed from the step 2304 by a "NO" to a step 2606.
In the step 2606, for the pixel being considered in the empty image Ie, an (x, y) coordinate is taken from the corresponding pixel in the relational map D'c. Thereafter, a step 2607 uses this (x, y) coordinate to calculate, by bicubic interpolation, the corresponding "true" pixel value from the coarsely aligned scanned document 121. A following step 2608 writes the warped (true) pixel value into Ie to form, in relation to the pixel in question, the precisely aligned scanned document. The process 2403C is then directed by an arrow 2609 back to the step 2603. It is noted that Ie contains several components, in particular red, green, blue intensity components.
The 600DPI precisely aligned scanned document Ie and the colour image cipher fields are reduced to 200DPI by sampling the middle pixel of each 3x3 block.  This avoids pixels which have some mixed colour values between 200DPI pixels.
＜Verifying the precisely aligned scanned document＞
Fig. 19 shows an illustrative example of tamper detection. The pixel 801 forms part of a precisely aligned scanned document 812 (at 123 or 124 of Fig. 2). Four pixels 802 have been altered from the comparable original pixels 709 shown in the tamper-evident document 705 in Fig. 8. An unauthorised person has thus changed the two pairs of pixels 802 to change the letters "EF" in Fig. 8 to "FE" in Fig. 19.
As a first step, the precisely aligned scanned document 812 is subjected, as depicted by an arrow 813, to a threshold operation in a threshold module 107 which considers the luminance value of each pixel. Pixels below 50% luminance are classified as black, and the remaining pixels are classified as white. An image 804, purporting to be the original source image (not shown) is produced as the result of the threshold operation.
Next colour image version cipher fields 805, used in the original encoding of the document 802 are reproduced in sufficient area to cover the precisely aligned scanned document 812. This is done by using the original key from the step 2501 in Fig. 6, which may be entered by an operator, or known to the validation sub-system 127, or transferred from the production sub-system 126 or by some other means. The original key is combined with the salt value from the step 2508 in Fig. 6.
Next the value 814 of each pixel in the threshold image 804 is used to control selection by a selection module 109. Under this control 814 the selection module 109 selects a pixel value 816 or 815 from the one colour image version cipher field or the other, to produce a reference image 807. This is the equivalent process used in the encoding process. For each such selected pixel (eg 807) in the reference image, a comparison is made in a comparison module 108 between the selected pixel, in this example the pixel 807, and the corresponding pixel from the aligned scanned image, in this case the pixel 801. If the minor components of the colors of the pixels 807 and 801 fail to match within a required tolerance, the pixel is defined to have been tampered with from its original condition. According to one arrangement, a pixel is considered to have failed to meet the "match" condition if any of its colour components is more than 25% different from a typical correct value for the given color measured in a linear RGB color space. A typical correct value for each color can be determined by scanning a sample color patch of that color, or based merely on an estimated value.  This information, along with the thresholded image, is used to build a new verification image 809. In the described example pixels 810 are reproduced in magenta, while all other pixels are either black or white according to the thresholded image.
There is a possibility that a pixel that has been tampered with will, by chance, have the same color as the appropriate random field (comprising the minor component) at that point and thus not be revealed. This is illustrated in 811 where a pixel that was changed from white to black, is nonetheless not flagged as an alteration in the verification image. In the described arrangement, typically up to 25% of altered pixels can be failed to be detected. This derives from the fact that the cipher fields use 2 bits of precision. The 75% of pixels that are detected is normally more than sufficient to alert a user to the presence and nature of an alteration. Thus over large areas (for example, areas with more pixels than the number of bits in the 52 bit key) the difficulty of making fraudulent undetectable alteration approaches proportionality to the key space size.
The final verification image 809 is typically printed on a color printer for examination by an operator. However, it may also be subject to automatic analysis based on the number of altered pixels or the presence of dense regions of altered pixels.
The revelation of altered pixels is both specific and fine scaled, occurring as it does at the scale of pixels of the original document 708. The revelation is also blind to the original document 708, requiring as it does only the suspect document 812 and the original key to reveal these alterations.
A substantial advantage of the described method is that revelation of alteration of one sub-section of the document 812 is independent of remaining parts of the document 812. It will be noted that the coarse alignment and salt information are incorporated into the document using a technique that provides for very wide dispersal of the information in both spatial and frequency domains with sufficient signal strength to achieve a high degree of redundancy. This means that these signals can be recovered from any sub section of the document 812 without reference to the remainder of the document 812. In the described arrangement recovery of these signals from any 25% of the area of the document is easily achievable. It will be noted that the precision alignment and verification steps also provide for local processing and a high degree of robustness against missing sections. Thus overall the system provides a method of authentication that is highly flexible (applicable to the full area of any document without special arrangement) and robust against partial transfer or incidental document damage.
＜Using the marking process in a printer driver＞
The anti-tampering approach may be incorporated as part of a printer driver on a general purpose computer, such as a Microsoft Windows based computer. In this arrangement the printer driver properties are provided with a user interface element that an operator may select to enable the anti-tampering approach, and a second user interface element where the key (or password) may be entered. In one variation of this arrangement, the printer driver includes the rasterisation process that turns the application data into a ready-to-print image. At this stage the ready-to-print image is modified by the printer driver as described in the anti-tampering approach, and the resulting image passed to the printer device.
In a second variation, the anti-tampering approach is carried out within the printer device. This approach can be advantageous because the anti-tampering approach introduces high frequency data into the print data. If the process of transferring data to the printer, or the internal processes of the printer employ image compression, the image compression will be rendered less effective by the presence of this high frequency data. However if the anti-tampering approach is carried out after transfer to the printer device, the printer device can add the high frequency data at a later stage of processing, after compression and decompressions is complete.
＜Using the marking and verification in a multi-function copier＞
Another arrangement of the anti-tampering approach employs the anti-tampering approach as a capability of a multi-function copier such as a Canon IR C3200. In this arrangement the multi-function copier provides a user interface element that enables the anti-tampering approach to be employed as part of a security copy operation. As in the case of the printer driver, a second user interface element allows entry of the key. A document copied with this option enabled is scanned, and the digital scanned image is marked as described above, and the resulting digital image is printed, thus providing a security copy operation. The same, or another, multi-function device also employs a verification feature. This feature is also enabled by a user interface element and a second key entry element. A document copied under the scope of this option will be subject to the verification process described above and the printed document will be the result of the verification process with altered areas revealed in magenta (or other highlighting) while non-altered areas will be reproduced in black and white.
＜Verifying a document with a scanner＞
Another arrangement of the anti-tampering approach uses a scanner device such as a Canon CanoScan 8000F, connected via a USB interface to a general purpose computer running Microsoft Windows and also running a software application employing the anti-tampering approach process. In this arrangement the software application uses a TWAIN scanner driver to obtain document images from paper documents provided by an operator. Each document image is analysed according to the anti-tampering approach. The results of the validation are displayed on the computer screen for the operator to inspect.
＜Verifying large volumes of documents with a sheet-fed scanner＞
Another arrangement of the anti-tampering approach uses a high speed desktop sheet-fed scanner such as a Canon DR-5080C. In this arrangement a large volume of documents are scanned without operator intervention. The validation process is used in synchronisation with the scanning process to discover documents that have alterations. In this arrangement the digital image that is the result of the validation process is examined for small patches that contain more than a threshold of altered pixels. The patch size and threshold can be set by the operator. It is also possible to set different thresholds and patches in different areas of the document and have these areas identified by a form recognition system.
[Industrial Applicability]
It is apparent from the above that the arrangements described are applicable to the document processing industry.
The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive. 
[Brief Description of the Drawings]
One or more embodiments of the present invention will now be described with reference to the drawings, in which:
Fig. 1 is a schematic block diagram of a general purpose computer upon which the anti-tampering arrangements described can be practiced;
Fig. 2 shows one example of a functional block diagram for the disclosed anti-tampering system;
Fig. 3 shows process, using the system of Fig. 2, for producing a tamper-evident document;
Fig. 4 shows a process, using the system of Fig. 2, for validating the tamper-evident document from Fig. 3, ie for determining whether the document has been tampered with;
Fig. 5 depicts two approaches for generating a two-dimensional cipher field from a stream cipher;
Fig. 6 shows a process for generating the cipher field in Fig. 5;
Fig. 7 shows one example of the selection process of Fig. 2 that is used to convert a bi-level source pixel into a multi-level tamper-evident pixel;
Fig. 8 shows a pictorial example of a bi-level image being converted to a multi-level image;
Fig. 9 shows a bi-level representation of a two-dimensional linear corrugated function used for coarse alignment;
Fig. 10 shows a graphical representation of the linear corrugated function of Fig. 9;
Fig. 11 shows an example of axes of symmetry from a predefined set of four linear corrugated functions used to form the alignment mark used in coarse alignment of the tamper-evident document;
Fig. 12 shows the coarse alignment process of Fig. 4 in more detail;
Fig. 13 shows the quasi-polar transform process of Fig. 12 in more detail;
Fig. 14 shows the peak detection process of Fig. 12 in more detail;
Fig. 15 shows a block-based correlation sub-process, used to form a displacement map in the fine alignment process of Fig. 4;
Fig. 16 illustrates block and step size in the block correlation process of Fig. 15;
Fig. 17 shows an interpolation sub-process, used to form a distortion map from the displacement map of Fig. 15;
Fig. 18 shows a warping process, used to form the finely aligned document from the displacement map of Fig. 17; and
Fig. 19 shows an example of tamper detection.
1.      A method for processing a tamper-evident document, the method comprising the steps of:
(a)  resolving, in regard to an N-level image to be recorded, at least one pixel of the image into a major component having N possible values,
(b)  selecting a pattern element from at least one predetermined pattern, said selection depending upon (ai) the major component and (aii) the position of the at least one pixel in the image;
(c)  recording the selected pattern element for said at least one pixel onto a transfer medium;
(d)  extracting, from the recorded document, a retrieved pattern element for said at least one pixel;
(e)  determining a pattern element depending upon (di) a major component extracted from said retrieved pattern element and (dii) the position of the at least one pixel on the recorded document; and
(f)  comparing the said retrieved pattern element and the said determined pattern element.
2.      A method according to claim 1, wherein:
the recording step prints the selected pattern element for said at least one pixel onto a print medium;
the extracting step extracts, from the printed document, a scanned pattern element for said at least one pixel;
the determining step determines a pattern element depending upon a major component extracted from said scanned pattern element, and the position of the at least one pixel on the printed document; and
the comparing step compares the said scanned pattern element and the said determined pattern element.
3.      A method according to claim 1, comprising a further step of:
declaring that the major component of the pixel of the recorded document has been tampered with if the said retrieved pattern element does not match the said determined pattern element.
4.      A method for processing a tamper-evident document, the method comprising the steps of:
(a)  resolving, in regard to an N-level image to be recorded, at least one pixel of the image into a major component having N possible values, and a corresponding randomised minor component, said randomised minor component depending upon (ai) the major component and (aii) a position of the at least one pixel in the image;
(b)  recording the major component and the randomised minor component for said at least one pixel onto a transfer medium;
(c)  extracting, from the recorded document, the major component for said at least one pixel;
(d)  determining the corresponding randomised minor component depending upon (di) the extracted major component and (dii) a position of the at least one pixel on the recorded document;
(e)  measuring, from the printed document, the printed randomised minor component for said at least one pixel; and
(f)  declaring that the pixel of the printed document has been tampered with if the measured printed randomised minor component does not match the determined randomised minor component.
5.      A method according to claim 1, wherein the said at least one predetermined pattern is at least one known sequence based on position.
6.      A method according to claim 5, wherein the said at least one predetermined pattern is at least one cipher field.
7.      A method according to claim 6, wherein:
(g)  the resolving step (a) comprises:
(ga)  generating N cipher fields;
(gb)  aligning the cipher fields with the N-level image;
(gc)  selecting one of the cipher fields dependent upon the value of the major component; and
(gd)  choosing the pattern element from the selected cipher field dependent upon the position of the at least one pixel in the image;
(i)  subsequent to the recording step and prior to the determining step the method comprises the further steps of:
(ia)  generating said N cipher fields; and
(ib) aligning the cipher fields with the N-level recorded image so that the position of the recorded pixel can be established.
8.      A method according to claim 7, wherein:
the aligning step (gb) is performed in a pixel congruent manner with the N-level image; and
the aligning step (ib) is performed in a pixel congruent manner.
9.      A method according to claim 8, wherein the aligning step (ib) further comprises block correlating the cipher fields with the recorded image.
10.     A method according to claim 8 wherein the recording step further comprises recording an alignment mark onto the transfer medium and the alignment mark comprises at least two registration marks.
11.     A method according to claim 8 wherein the alignment mark comprises at least one linear corrugated function.
12.     A method for recording a tamper-evident document, the method comprising the steps of:
(a)  resolving, in regard to an N-level image to be recorded, at least one pixel of the image into a major component having N possible values,
(b)  selecting a pattern element from at least one predetermined pattern, said pattern element depending upon (bi) the major component, and (bii) the position of the at least one pixel in the image; and
(c)  recording the pattern element for said at least one pixel onto a transfer medium.
13.     A method for recording a tamper-evident document, the method comprising the steps of:
(a)  resolving, in regard to an N-level image to be recorded, at least one pixel of the image into a major component having N possible values, and a corresponding randomised minor component, said randomised minor component depending upon (ai) the major component, and (aii) a position of the at least one pixel in the image; and
(b)  recording the major component and the randomised minor component for said at least one pixel onto a transfer medium.
14.     A method according to claim 12, wherein the said at least one predetermined pattern is at least one known sequence based on position.
15.     A method according to claim 14, wherein the said at least one predetermined pattern is at least one cipher field.
16.     A method according to claim 15, wherein:
(c)  the resolving step (a) comprises:
(ca)  generating N cipher fields;
(cb)  arranging the cipher fields in a pixel congruent manner with the N-level image;
(cc)  selecting one of the cipher fields dependent upon the value of the major component; and
(cd)  choosing the minor component from the selected cipher field dependent upon the position of the at least one pixel in the image.
17.     A method for validating a recorded tamper-evident document, the method comprising the steps of:
(a)  extracting, from a position in the recorded document, a retrieved pattern element; 
(b)  selecting a pattern element depending upon (bi) a characteristic of the said retrieved pattern element and (bii) the position;
(c)  comparing the retrieved pattern element and the selected pattern element.
18.     A method according to claim 17, comprising the further step of:
establishing that the characteristic at the position in the recorded document has been tampered with if the retrieved pattern element does not match the selected pattern element.
19.     A method for validating a recorded tamper-evident document, the method comprising the steps of:
(a)  extracting, from the recorded document, a major component, having N possible values, for at least one recorded pixel;
(b)  determining a corresponding randomised minor component depending upon (bi) the extracted major component and (bii) a position of the at least one recorded pixel;
(c)  measuring, from the recorded document, the recorded randomised minor component for said at least one pixel; and
(d)  comparing the measured recorded randomised minor component and the determined randomised minor component.
20.     A method according to claim 19, comprising the further step of:
establishing that the pixel of the recorded document has been tampered with if the measured recorded randomised minor component does not match the determined randomised minor component.
21.     A method according to claim 17, wherein the characteristic is visible to a human reader of the document.
22.     A method according to claim 17, wherein the selected pattern element is selected from a predetermined pattern which is a known sequence based on position.
23.     A method according to claim 22, wherein the said predetermined pattern is a cipher field.
24.     A method according to claim 23, wherein prior to the selection step the method comprises the further steps of:
(e)  generating N cipher fields; and
(f)  aligning the cipher fields with the recorded image so that the position of the retrieved pattern element and a cipher field location can be related.
25.     A method according to claim 24 wherein an alignment mark is recorded on the document and the alignment mark comprises at least two registration marks.
26.     A method according to claim 24 wherein the alignment mark comprises at least one linear corrugated function.
27.     A method according to claim 24, wherein the aligning in the step (f) further comprises block correlating the cipher fields with the recorded image.
28.     A tamper-evident document upon which is recorded an N-level image, the document comprising, in regard to at least one pixel of the image, a recorded pattern element that visually approximates the level of said pixel and also has a cryptographic value depending upon (a) the level of said pixel, and (b) the position of said pixel in the recorded document.
29.     A tamper-evident document upon which is recorded an N-level image, the document comprising, in regard to at least one recorded pixel of the image, a recorded major component having N possible values, and a recorded randomised minor component, said recorded randomised minor component depending upon (a) the major component, and (b) a position of the at least one recorded pixel in the recorded document.
30.     A computer program product having a computer readable medium having a computer program recorded therein for directing a processor to execute any of the above methods.
31.     A computer program for directing a processor to execute any of the above methods.
32.     A method of detecting tampering of a security document, comprising:
(a)  generating scan data corresponding to said document;
(b)  performing region matching between said scan data and at least one two-dimensional cryptographic field to obtain alignment information;
(c)  using said alignment information and said scan data to detect tampering in said security document.
33.     A method according to claim 32 wherein said region matching is block correlation.
34.     A method according to claim 33 wherein said tamper detection is characterised by comparison of said scan data and said at least one two-dimensional cryptographic field.
35.     A method according to claim 32 wherein said scan data includes at least one graphic element.
36.     A method according to claim 35 wherein said graphic element is a readable text character.
37.     A method according to claim 32 wherein the process of revealing alterations is subject to the requirement of knowledge of a cryptographic key and the degree of difficulty of making substantial alterations that are not revealed by said process is substantially proportional to the size of the key space.
38.     A method according to claim 32 wherein revelation of alterations in any substantial sub-section of the altered recorded document is independent of knowledge of the remaining sections of the altered recorded document.
39.     A method of detecting tampering in a recorded image, said method including the steps of:
(a)  combining an image with at least one two-dimensional cryptographic signal to form a second image,
(b)  recording said second image to form a recorded image,
(c)  processing said recorded image to make a retrieved image,
(d)  detecting alignment of said retrieved image with respect to said at least one two-dimensional cryptographic signal, and
(e)  using said alignment and said retrieved image and the said at least one cryptographic signal to detect tampering.
40.     An apparatus for producing a security document, said apparatus comprising:
(a)  a retrieving element for retrieving an original document and producing a document image
(b)  a marking element for marking said document image with a security pattern to produce a marked document image, and
(c)  a recording element for recording said marked document image to produce a security document,
wherein said security document is a readable rendition of said original document and said security pattern provides for detection of alteration between said original document and said security document.
41.     A claim according to claim 40 wherein said original document contains readable text and said security document contains equivalent readable text and said verification provides for verification of the equivalence between said original document readable text and said security document readable text.
42.     An apparatus for revealing alterations between an altered recorded document and an unaltered form, said apparatus being characterised by:
(a)  a retrieval means to produce retrieved data corresponding to said recorded document,
(b)  a means to determine the alteration of the shape of at least one graphic element between its shape in the retrieved data and its shape in the unaltered form, said means being blind to the unaltered form,
(c)  a means to output the determined alteration in the shape.
[Abstract]
An anti-tampering method for processing documents is disclosed. The method comprises, in regard to an encoding step, the steps of resolving (in a step 2303) in regard to an N-level image to be recorded, a pixel of the image into a major component having N possible values, selecting (in the step 2303) a pattern element depending upon the major component and the position of the pixel in the image, and recording the selected pattern element (in a step 2308) onto a transfer medium. In regard to a corresponding decoding step the method comprises extracting (in a step 2405) from the recorded document, a retrieved pattern element for said pixel, determining a pattern element (in a step 2407) depending upon a major component extracted from the retrieved pattern element and the position of the pixel on the recorded document, and comparing (in a step 2409) the retrieved pattern element and the said determined pattern element.
[Seleted Drawing]
Figure 3
【図１】
2006014280.tif 000114
【図２】
2006014280.tif 000115
【図３】
2006014280.tif 000116
【図４】
2006014280.tif 000117
【図５】
2006014280.tif 000118
【図６】
2006014280.tif 000119
【図７】
2006014280.tif 000120
【図８】
2006014280.tif 000121
【図９】
2006014280.tif 000122
【図１０】
2006014280.tif 000123
【図１１】
2006014280.tif 000124
【図１２】
2006014280.tif 000125
【図１３】
2006014280.tif 000126
【図１４】
2006014280.tif 000127
【図１５】
2006014280.tif 000128
【図１６】
2006014280.tif 000129
【図１７】
2006014280.tif 000130
【図１８】
2006014280.tif 000131
【図１９】
2006014280.tif 000132