(57)【要約】      （修正有）【課題】文書内にメッセージを目立ちにくく耐性がある方法で埋め込む。【解決手段】グリフのセット１２５を含む文書１２０内にメッセージ１１０を埋め込む。文書１２０内の個々のグリフ、文書１２０内のグリフのグループ、又は文書１２０全体が、対象となる形状からの距離値を含む距離場を使用して表される。メッセージ１１０の各シンボル１４０は距離場における距離値のサブセット１３６の変更として表される。この距離場における距離値のサブセット１３６は、上記変更に従って変更され、変更済み文書１５５内に変更済みグリフ１５６を生成する。メッセージ１１０内のシンボルは変更済みグリフ１５６内に埋め込まれる。【選択図】図１
2010157993.tif 000002
【特許請求の範囲】
【請求項１】
グリフのセットを含む文書内にメッセージのシンボルを埋め込む方法であって、
文書内のグリフを距離場として表すこと、
前記文書内に埋め込まれるメッセージ内のシンボルを、前記距離場における値のサブセットの変更として表すこと、及び
前記距離場における前記値のサブセットを前記変更に従って変更することであって、変更済み文書における変更済みグリフを生成し、前記メッセージ内の前記シンボルが前記変更済みグリフ内に埋め込まれる、変更すること、
を含む、方法。
【請求項２】
前記距離場は規則的にサンプリングされた距離場である、請求項１に記載の方法。
【請求項３】
前記距離場は適応的にサンプリングされた距離場（ＡＤＦ）である、請求項１に記載の方法。
【請求項４】
前記距離場はメモリ装置内のデータ構造内に格納される値のセットである、請求項１に記載の方法。
【請求項５】
前記距離場は、前記埋め込まれるメッセージシンボルに基づいて前記グリフを再構築及びレンダリングするプロシージャを含む、請求項１に記載の方法。
【請求項６】
前記変更は決定論的変更及び確率論的変更を含む、請求項１に記載の方法。
【請求項７】
前記距離場における前記値のサブセットを鍵に従って選択することをさらに含む、請求項１に記載の方法。
【請求項８】
前記変更は、前記距離場における前記値のサブセットの新たな値を規定する、請求項１に記載の方法。
【請求項９】
前記変更は、前記距離場における前記値のサブセットの補正値を規定する、請求項１に記載の方法。
【請求項１０】
前記変更は、前記距離場における前記値のサブセットのサンプリング密度の補正値を規定する、請求項１に記載の方法。
【請求項１１】
前記距離場における前記値のサブセットを局所的なサンプリング密度に従って選択することをさらに含む、請求項１に記載の方法。
【請求項１２】
前記距離場における前記値のサブセットを、前記グリフの形状の境界上の局所的に計算された勾配に従って選択することをさらに含む、請求項１に記載の方法。
【請求項１３】
前記メッセージ内に少なくとも１つのパケット化シンボルを挿入することをさらに含む、請求項１に記載の方法。
【請求項１４】
前記パケット化シンボルは、開始パケットシンボル、パケット数シンボル、及び同期シンボルを含むグループから選択される、請求項１３に記載の方法。
【請求項１５】
前記方法は、
変更された距離値を含む変更された距離場を用いて前記変更済みグリフを表すこと、
前記変更された距離場における前記変更された距離値のサブセットに関連付けられる埋め込まれた変更を検出すること、及び
前記埋め込まれた変更に基づいて前記メッセージの前記シンボルを求めること、
をさらに含む、請求項１に記載の方法。
【請求項１６】
前記変更された距離値のサブセットを鍵に従って求めることをさらに含む、請求項１５に記載の方法。
【請求項１７】
前記変更された距離値のサブセットを、グリフの形状要素のデータベースに従って求めることをさらに含む、請求項１５に記載の方法。
【請求項１８】
文書内にメッセージを埋め込む方法であって、
文書の少なくとも一部を距離値を含む距離場として表すこと、
前記文書内に埋め込まれるメッセージ内のシンボルを、前記距離場における前記値のサブセットの変更として表すこと、及び
前記距離場における前記値のサブセットを前記変更に従って変更することであって、変更済み文書を生成し、前記メッセージ内の前記シンボルが前記変更済み文書内に埋め込まれる、変更すること、
を含む、方法。
【請求項１９】
前記距離場における前記値のサブセットは、前記文書内のグリフに関連付けられる、請求項１８に記載の方法。
【請求項２０】
前記変更済み文書を処理することをさらに含む、請求項１８に記載の方法。
【請求項２１】
前記処理は、前記変更済み文書のレンダリング、コピー、印刷、ファックス、電子メール送信、表示、スキャン、該変更済み文書のファイル転送、又はそれらの組合せを含むグループから選択される、請求項２０に記載の方法。
【請求項２２】
前記距離場における前記値のサブセットを鍵に従って選択することをさらに含む、請求項１８に記載の方法。
【請求項２３】
前記方法は、
変更された距離場を用いて前記変更済み文書を表すこと、
前記変更された距離場における前記変更された距離値のサブセットに関連付けられる変更を検出すること、及び
前記変更に基づいて前記メッセージの前記シンボルを求めること、
をさらに含む、請求項１８に記載の方法。
【請求項２４】
前記変更された距離場における前記値のサブセットを鍵に従って求めることをさらに含む、請求項２３に記載の方法。
【請求項２５】
前記変更された距離場における前記値のサブセットを、グリフの形状要素のデータベースに従って求めることをさらに含む、請求項２３に記載の方法。
【請求項２６】
文書内にメッセージを埋め込む方法であって、
文書内のグリフを距離値を含む距離場として表すこと、
前記距離場における前記距離値を密度値のセットにマッピングすること、
前記文書内に埋め込まれるメッセージ内のシンボルを、前記密度値のセットのサブセットの変更として表すこと、及び
前記密度値のセットの前記サブセットを前記変更に従って変更することであって、変更済み文書を生成し、前記メッセージ内の前記シンボルが前記変更済み文書内に埋め込まれる、変更すること、
を含む、方法。
【請求項２７】
前記密度値のセットは前記文書内の前記グリフのピクセル強度を表す、請求項２６に記載の方法。
【請求項２８】
前記密度値のセットは前記文書内の前記グリフの色を表す、請求項２６に記載の方法。
【請求項２９】
前記密度値のセットは前記文書内の前記グリフのテクスチャを表す、請求項２６に記載の方法。
【請求項３０】
前記密度値のセットの前記サブセットを、ディスプレイ装置の色フリンジングのアーチファクトに従って選択することであって、該ディスプレイ装置はアドレス指定可能なピクセル構成要素を使用する、選択することをさらに含む、請求項２６に記載の方法。
【請求項３１】
前記密度値のセットの前記サブセットを、ディスプレイ装置のエイリアシングアーチファクトに従って選択することであって、該エイリアシングアーチファクトは前記グリフの表示位置に関連付けられる、選択することをさらに含む、請求項２６に記載の方法。
【請求項３２】
前記密度値のセットの前記サブセットを鍵に従って選択することをさらに含む、請求項２６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には文書内にメッセージを埋め込むことに関し、より詳細には距離場を使用して文書内にメッセージを埋め込むと共に文書内のメッセージを検出することに関する。
【背景技術】
【０００２】
以下の特許及び特許出願は、本出願に関連し、参照により本明細書に援用される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許第６３９６４９２号明細書
【特許文献２】米国特許第７００２５７０号明細書
【特許文献３】米国特許第７０３４８４５号明細書
【特許文献４】米国特許第７１２３２７１号明細書
【特許文献５】米国特許出願第１２／３２９８６９号明細書
【０００４】
透かし
透かしは、文書内にメッセージとして埋め込まれることが多い。埋め込みメッセージは、たとえば、セキュリティ、プライバシー、及び著作権保護のために使用することができる。
【０００５】
紙の「ハードコピー」文書のための透かしは、電子的な「ソフトコピー」透かしとは異なる。ソフトコピー文書の場合、透かし挿入、文書コピー、文書の品質引き下げ、及び透かし抽出のようなすべての操作は、デジタル領域、たとえばＰＤＦ文書又はＰｏｓｔｓｃｒｉｐｔ文書において発生する。逆に、ハードコピー文書の場合、文書の品質引き下げはハードコピー領域において発生する。ハードコピー文書における透かしは、文書がコピーされるか、スキャンされるか、ファックスされるか、又は他の態様で操作されるときに品質を引き下げられる可能性がある。ハードコピー透かしは、故意に又は意図されずに、物理的損傷を受ける、たとえばしわくちゃにされるか又は引き裂かれる可能性もある。
【０００６】
グリフ
グリフは、本明細書で定義される場合、基本図形物体である。グリフの最も一般的な例は、テキスト文字又は書記素である。グリフは合字、すなわち複合文字、又は発音区別符号とすることもできる。グリフは象形文字又は表意文字とすることもできる。用語グリフは非文字パターン又は複数文字パターンにも使用することができる。本明細書で使用される場合、グリフは何らかの任意の図形形状又は図形物体であり、これは２次元又はＮ次元である可能性がある。ここで、Ｎは２より大きい整数である。
【０００７】
メッセージ埋め込み
画像、ビデオ、及び音声のような媒体信号内に、隠しメッセージを埋め込む多くの既知の方法が存在する。しかしながら、構造化されたグリフの内部に隠しメッセージを埋め込むことは難しい問題である。構造、たとえば間隔及び配向に対する小さな変化であっても、人間の視覚系によって検出される可能性がある。したがって、透かしの目的のために、グリフに対する変更は非常に小さくなければならない。
【０００８】
この問題は、ハードコピー透かしの場合に一層困難である。ハードコピー文書は、持ち主が変わるか、引き裂かれるか、又は折りたたまれると、物理的劣化を受ける可能性がある。文書の電子バージョンでは検出可能であったメッセージは、印刷文書が写真複写又はスキャンされるときに失われる可能性があり、たとえばコピー後に階調レベルの微細な変化が失われる可能性がある。
【０００９】
従来のメッセージ埋め込み方法
幾つかの従来のメッセージ埋め込み方法はテキスト文書を画像として扱い、画像ベースの透かし技法を使用する。これらの方法の１つの不利な点は、これらの方法が主に個々のテキスト文字のビットマップ表現、又は色及び陰の中間調表現に対して動作するプリンタと上手く協働しないことである。
【００１０】
また、別の従来方法は、違いが目には知覚することができないがスキャナによって感知することができるように文字の色を微細に変化させる。埋め込みメッセージは不可視であるため、透かしを変化させることは困難である。しかしながら、この方法の不利な点は、色又は階調レベルの小さな違いが、文書がコピーされるときに簡単に失われることである。
【００１１】
さらに、別の方法は、個々の文字間、個々の単語間、又はテキストの連続する行の行間の距離を調節する。低い埋め込み率において、この方法は目にはほとんど不可視であり、コピーを乗り切る。しかしながら、この方法の不利な点は、高い埋め込み率において、文字間、単語間、又は行間の不均一な距離が、読み手にとって可視になると共に目障りになることである。
【００１２】
さらにまた、別の方法は、文字全体の境界上に格子状の白黒のドットパターンを配置し、文字全体を標準より狭くするか又は広くすることによってディザリング効果を用いる。しかしながら、この方法は写真複写に対してロバストではない。これは、個々のドットパターンが、写真複写後に保持されるには小さすぎるためである。
【００１３】
また、別の方法は、テキストの位置とは無関係な文書の背景にドットの擬似ランダムパターンを埋め込む。ドットは比較的目立たないが、依然として簡単に除去される可能性がある。さらに、ドットは小さく、２回以上の写真複写を乗り切ることができない場合がある。
【００１４】
ダーティペーパ符号化
ダーティペーパ符号化（ＤＰＣ）は、「ダーティペーパへの書き込み」とも呼ばれ、何らかの副次的情報の存在下でメッセージを符号化する方法である。副次的情報は符号化器には知られているが、復号器には知られていない。副次的情報は通常、符号化器における何らかの干渉信号から成る。符号化器の任務は、復号器が干渉信号のいかなる知識も所有することなくメッセージを回復することが必ずできるように所望のメッセージを符号化することである。換言すれば、復号器は、いずれの部分が実際のメッセージを構成し、いずれの部分がノイズであるのかを事前に知ることなく、「ダーティ」文書からメッセージを読み取ることができなくてはならない。これが「ダーティペーパ符号化」の名前の由来である。
【００１５】
距離場
物体、たとえばグリフの形状は、コンピュータシステムのメモリにおいて、Ｎ次元空間内の複数のサンプル点の集合として表すことができる。各サンプル点に、該サンプル点から形状の境界までの距離が関連付けられる。その距離は、サンプル点が境界の内側に位置するか又は外側に位置するかを示すために正又は負となり、厳密に境界上に位置するときはゼロとなる。関連付けられた距離値を有するサンプル点の集合は、サンプリングされた距離場と呼ばれる。距離場はコンピュータシステムのメモリ内に格納される解析プロシージャとして表すこともできる。
【００１６】
本発明では、一般的な用語の距離場を、サンプリングされた距離場及びサンプリングされていない距離場の両方の、すべてのタイプの距離場を指すものとして使用する。
【００１７】
距離場を使用して、色、階調、テクスチャのような、グリフの形状以外の属性を表すことができる。より正確には、グリフを表す距離場の距離値から、グリフの他の属性を表す密度値へのマッピングが存在する。
【００１８】
適応的にサンプリングされた距離場（ＡＤＦ）
適応的にサンプリングされた距離場（ＡＤＦ）において、サンプル点の密度は、形状の異なる部分を表すのに必要とされる詳細度によって決まる。たとえば、複雑な局所的な変化は、高いサンプル点密度を必要とする場合がある。したがって、ＡＤＦは、任意の形状、たとえば、テキスト文字、漫画、及びロゴのようなグリフの処理を可能にする表現である。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明の目的は、ソフトコピー文書及びハードコピー文書内にメッセージを透かしとして埋め込む方法を提供することである。
【００２０】
本発明のさらなる目的は、メッセージが文書の読み手に目立たない方法を提供することである。
【００２１】
本発明のさらなる目的は、比較的大きなメッセージを埋め込むのに適した方法を提供することである。
【００２２】
本発明のさらなる目的は、埋め込みメッセージの抽出が、文書の物理的劣化に対し耐性がある方法を提供することである。
【００２３】
本発明のさらなる目的は、メッセージを損なうことなく文書の物理コピーを可能にすることである。
【課題を解決するための手段】
【００２４】
本発明は、グリフを表す距離場における距離値を変更することによって、そのグリフの形状を微細に変更し、それによって文書内に隠しメッセージを埋め込むことが可能であるという認識からもたらされる。
【００２５】
本発明はさらに、グリフの基本距離場に関連付けられる密度値を変更することによって、グリフの外観を変更し、それによって文書内に隠しメッセージを埋め込むことが可能であるという認識からもたらされる。
【００２６】
ダーティペーパ符号化（ＤＰＣ）は、「ダーティペーパへの書き込み」とも呼ばれ、何らかの副次的情報の存在下でメッセージを符号化する方法である。副次的情報は符号化器には知られているが、復号器には知られていない。ＤＰＣに基づく透かしとの関連において、透かしは符号化されるメッセージの役割を果たし、文書は符号化器における干渉信号の役割を果たす。
【００２７】
適応的にサンプリングされた距離場（ＡＤＦ）は、デジタル表示のためのスケーラブル文字フォントを表す基本データ構造として広く採用されてきた。原則的に、ＡＤＦは距離値を含有し、距離値はたとえばフォントの選択によって指示されるグリフの形状を表す。
【００２８】
メッセージの埋め込みにＡＤＦを使用することによって、文字の形状及び／又は外観に対する微細な変更が一般の読み手には不可視であり、且つ該変更を回復する目的で設計される検出器のみが該変更を回復することができるようにすることを可能にする。
【００２９】
これによって、追跡情報、たとえば著作権情報、又は認証情報を、ポータブル文書フォーマット（ＰＤＦ）文書若しくはＷｏｒｄ文書、画像、ビデオ、企業ロゴ、及び印刷文書内に埋め込むことが可能になる。本発明の潜在的な用途は、著作権保護、電子メール追跡、ファイル転送追跡、文書認証、改ざん検出、並びにプリンタ及びデバイスのフォレンジックを含む。
【図面の簡単な説明】
【００３０】
【図１】本発明の実施形態による、グリフのセットを含む文書内に複数のシンボルから成るメッセージを埋め込む方法のブロック図である。
【図２】本発明の実施形態による、文書内のメッセージのシンボルを検出する方法のブロック図である。
【図３】本発明の実施形態による、グリフを表す四分木のブロック図である。
【図４】本発明の実施形態による、未変更グリフ及び変更済みグリフの図である。
【図５】本発明の実施形態による、グリフのセットを含む文書内に複数のシンボルから成るメッセージを埋め込む方法の流れ図である。
【図６】本発明の実施形態による、グリフのセットを含む文書内の複数のシンボルから成るメッセージを検出する方法の流れ図である。
【発明を実施するための形態】
【００３１】
本明細書において説明される例示的なグリフ及び文書は、適応的にサンプリングされた距離場（ＡＤＦ）によって表される。しかしながら、すべての実施形態が他のタイプの距離場、たとえば規則的にサンプリングされた距離場又は手続き型距離場（procedural distance field）とも等しく良好に機能する。
【００３２】
本発明の実施形態は、グリフのセットを含有する、すなわち含む文書内に、メッセージのシンボルを埋め込む方法を提供する。たとえば、グリフの形状はＡＤＦを使用して表され、ＡＤＦ内の距離値は埋め込まれるメッセージのシンボルに従って変更される。この結果、通常の観察条件の下では人間の視覚系に通常不可視であるグリフの形状の変更がもたらされる。したがって、形状におけるわずかな変化は位置特定及び改変することが困難であり、同時にこの変化は文書の写真複写のような操作に対してロバストである。
【００３３】
メッセージ埋め込み
図１は、本発明の実施形態による、グリフのセットを含む文書内にメッセージのシンボルを埋め込む方法１００のブロック図を示す。文書１２０は、グリフのセット１２５、たとえばグリフ１２５’を含む。グリフ１２５’’は、グリフ１２５’の視覚的例である。グリフ１２５’をＡＤＦ１３５として表す（１３０）。ＡＤＦ１３５は距離値を含む。代替的に又は付加的に、文書全体１２０を単一のＡＤＦ１３５として表す（１３０）。
【００３４】
文書１２０に埋め込まれるメッセージ１１０は、シンボルのセット１１５、たとえばシンボル１１５’を含む。方法１００はシンボル１１５’をＡＤＦ１３５における距離値のサブセット１３６の変更データ１４５として表す（１４０）。
【００３５】
本発明の幾つかの実施形態では、サブセット１３６は、変更されていないＡＤＦ１３５における候補距離値１３７から選択される。ＡＤＦ１３５のこれらの距離値のみが埋め込みの候補１３７となるべきである。これらを変更すると（１５０）、結果としてグリフ１２５’の形状全体に知覚することができない変化がもたらされる。候補距離値１３７を決定する１つの方法は、グリフ１２５’の境界を表すＡＤＦ１３５の隣接するセル間の形状における変化を測定し、近隣のセルにおける距離に非常に類似したセルの距離値を候補１３７として選択する。
【００３６】
そのような候補は、たとえばメッセージがグリフ１２５’の局所的な曲率のわずかな変更として埋め込まれる場合に使用される。候補距離値１３７を決定する別の方法は、グリフ１２５’の、ＡＤＦ１３５のサンプリング密度が最も高い部分を選択する。そのような候補は、メッセージ１１０が、グリフ１２５’をサンプリング密度をわずかに減少させてレンダリングすることによって埋め込まれる場合に使用される。候補距離値１３７を決定する方法の別の例は、グリフ１２５’の、局所勾配が非常に高いか又は非常に低いかのいずれかである部分を選択する。境界の勾配は、境界を含むセルの頂点においてＡＤＦ１３５の距離値から計算される。
【００３７】
本発明の幾つかの実施形態では、電子ディスプレイ又は紙に表示される文書内にメッセージ１１０を埋め込むために連続ストローク変調（Continuos Stroke Modulation）（ＣＳＭ）を使用する。これらの実施形態では、ＡＤＦ１３５の距離場における候補距離値１３７は、グリフの形状のみでなく、照明条件、グリフが表示される装置又は媒体の特徴等のような他の特性にも依存するマッピング関数を介して、密度値のセットに関連付けられる。密度値の例は、文書内のグリフ又は文書自体の一部分に関連付けられるピクセル強度、色値、グレースケール値、及びテクスチャを含む。
【００３８】
メッセージを符号化するために、方法１００は距離値１３７をそのままにしておくか又は変更するかを選択することができるが、関連付けられる密度値にのみ微細な変更を実施することができる。これらの実施形態は、グリフ１２５’のストロークの階調レベル、色、又は厚みにおける微細な局所的変更を引き起こす。これらの変更は機器によって検出可能であるが、人間の視覚系には気付かれずに済む。変更される候補距離値を決定するのに使用されるすべての決定論的技法及び確率論的技法は、候補密度値を決定するのにも適用することができる。
【００３９】
メッセージ埋め込みのためにすべての候補距離値又は候補密度値を変更する（１５０）必要はないことに留意されたい。適切な候補の中で、ＡＤＦにおける変更される距離値又は密度値の最終選択は、埋め込み器、たとえば方法１００、及び検出器、たとえば方法２００（図２を参照されたい）によって知られている秘密鍵１４１を使用して行うことができる。ＡＤＦ１３５における距離値のサブセット１３６は、シンボル１１５’を埋め込むために変更されるグリフ１２５’の形状の一部分を画定する。文書１２０全体がＡＤＦとして表される実施形態において、サブセット１３６は通常、文書１２０内に含まれる１つ又は複数のグリフの形状に関連付けられる。
【００４０】
変更データ１４５は、シンボル１１５’が埋め込まれるようにＡＤＦ１３６のセブセットを変更するのに必要な情報を含む。たとえば、変更データ１４５はサブセット１３６の新たな変更された距離値を含むことができる。代替的に、変更データ１４５は、シンボル１１５’を埋め込むためにサブセット１３６における距離値をどのように変更すべきかを示す補正値を含むことができる。
【００４１】
ＡＤＦ１３５における距離値のサブセット１３６を、変更済み文書１５５における変更済みグリフ１５６を生成するための変更データ１４５に従って変更する（１５０）。ここで、メッセージ１１０におけるシンボル１１５’が変更済みグリフ１５６内に埋め込まれる。サブセット１３６における距離値が変更される方法に依拠して、この動作の結果、グリフ１２５’と比較して、グリフ１５６の形状の局所的な曲率の微細な変化又は他の変更が生じることができ、これによってシンボル１１５’、たとえば０ビット又は１ビットが埋め込まれる。グリフ１５６’は変更済みグリフ１５６の視覚的例である。図４（Ａ）及び図４（Ｂ）に示すように、グリフ１５６の変更は拡大後にのみ見てとることができ、意図のない読み手にはほとんど不可視である。
【００４２】
埋め込みデータに起因するグリフの形状における変更は「決定論的」又は「確率論的」とすることができることに留意されたい。本発明において、「決定論的」とは、変更済みグリフ１５６の形状が、未変更グリフ１２５’の形状と、メッセージ１１０のシンボル１１５’とによって一意に決定されることを意味する。決定論的変更の例は、上述した変更、すなわち、サンプリング密度又は勾配に基づいて元のＡＤＦにおける候補位置を選択することを含む。
【００４３】
本発明において、「確率論的変更」とは、変更済みグリフ１５６の形状が、未変更グリフ１２５’とメッセージシンボルとによって一意に決定されるのではなく、埋め込み器及び抽出器にのみ知られている適切に選択されたランダム変数に従って変化することができることを意味する。そのようなランダム変数の一例は、未変更グリフのＡＤＦ内の埋め込み位置を選択するのに使用される秘密鍵１４１である。これは、或る未変更グリフが文書内に複数回出現する場合、（メッセージ埋め込み後の）変更済みグリフの外観が毎回異なることを意味する。このランダム化によって、攻撃者が埋め込み方式を逆行分析することが極度に困難になる。
【００４４】
変更済みグリフ１５６を含む変更済み文書１５５を、シンボル１１５’が文書１５６から抽出される前にレンダリングすることができる。レンダリングの例は、変更済み文書１５５のコピー、印刷、ファックス、電子メール送信、表示、スキャン、又はこれらの組合せを含む。
【００４５】
本発明の幾つかの実施形態では、メッセージ１１０のシンボルを複数のパケットにグループ化するために、パケット化シンボルがメッセージ１１０内に挿入される。パケット化シンボルの例は、開始パケットシンボル、パケット数シンボル、及び同期シンボルを含む。パケットシンボルをメッセージ内に挿入することの詳細な説明に関しては、関連の米国特許出願第１２／３２９，８６９号明細書を参照されたい。
【００４６】
メッセージ検出
図２は、本発明の実施形態による、文書内のメッセージのシンボルを検出する方法２００のブロック図である。変更済み文書２１０は変更済みグリフ２１５を含む。変更済み文書２１０は、図１の変更済み文書１５５を、たとえば印刷又は写真複写することによってレンダリングした結果である。変更済み文書２１０は変更済み文書１５５の全体又は部分を表すことができる。したがって、変更済みグリフ２１５は図１の変更済みグリフ１５６に類似する。
【００４７】
変更済み文書２１０及び／又は変更済みグリフ２１５をスキャンしてデジタル画像を取得することができる。次に、そのデジタル画像を、変更された距離値を含むＡＤＦ２３５として表す（２３０）ことができる。変更されたＡＤＦ２３０の変更された距離値のサブセット２３６に関連付けられる変更２４５を検出する（２４０）。変更された距離値のサブセット２３６を、鍵２４１を利用して選択することができる。鍵２４１は、図１の鍵１４１に関連し、たとえば鍵１４１と同一であるか、又は鍵１４１に基づいて決定される。代替的に又は付加的に、サブセット２３６は、グリフの共通形状要素のデータベース２４２を利用して求めることができる。変更２４５によって、埋め込まれたシンボル２５５が求められる（２５０）。
【００４８】
ＡＤＦを用いるグリフ形状表現
ＡＤＦの空間階層を、ウェーブレット分解、２次元四分木、３次元八分木、及びより高次の次元のための四面体メッシュのような、複数のデータ構造を使用して表すことができる。
【００４９】
図３に示すように、本発明の一実施形態は、他の表現も等しく適用可能であるが、四分木３００を使用してグリフ３１０を表現及び変更する。四分木３００は複数の四角形セル３０１を含む。各セルは角に４つの頂点３０２を有する。各頂点は、頂点からグリフの最も近い境界まで測定された符号付距離３０３に関連付けられる。各セルは、該セルによって表される形状を再構成するプロシージャを含む。たとえば、セルのセル頂点間で双一次補間プロシージャを実施してセル内の形状を再構築することができる。
【００５０】
規則的にサンプリングされた距離場の四分木表現から開始して、ＡＤＦを構築する幾つかの方法が存在する。それらのうちの２つを以下で説明する。
【００５１】
トップダウンの手法では、四分木表現は形状の粗い近似を提供する。この粗い表現におけるセルのうちの幾つかは形状を含み、他のセルは形状を含まない。形状の境界上のセルのうちの幾つかにとって、この粗い近似における補間された距離値は、形状を再構成するのに十分である。他のセルにとって、補間された距離値は、たとえば曲率、角、及び点のような高レベルの詳細を有する複雑な領域の場合に不正確である。これらのセルは、距離場が詳細の良好な近似を提供するまで再帰的に再分割される。良好な近似を良好でない近似と区別するのに使用することができる多数の判断基準が存在する。１つの例は、真の形状への距離と、双一次補間によって再構築された近似形状への距離との間の差である。
【００５２】
ボトムアップの手法では、四分木表現は特定の許容誤差までの形状の正確な表現を提供する。この場合、４つの隣接セルから成るグループを単一セルに結合した後、結果としての大きなセルの頂点に関連付けられる距離から補間される距離値によって特定の許容誤差まで形状を再構築することが可能である場合、該結合が可能である。
【００５３】
上記の手法のうちの任意のものを使用してＡＤＦに対し微細な変更を行うことができる。次に、変更されていないＡＤＦと変更されたＡＤＦとの間の微細な違いによって埋め込みメッセージを保有することができる。たとえば、グリフの左のエッジの曲率におけるわずかな変更は０ビットを符号化することができ、右のエッジにおける同様の変更は１ビットを符号化することができる。メッセージのシンボルを埋め込むために、グリフ３１０の形状の他の変更が可能である。
【００５４】
選択される特定の変更は用途によって決まる。ハードコピー文書の場合、写真複写に対するロバスト性が所望されるとき、グリフ３１０の形状における変更はグリフの色又は階調レベルにおける変更よりもロバストである可能性が高い。
【００５５】
メッセージ埋め込みのための色フリンジング
本発明の一実施形態は、電子スクリーン上に表示される文書内にメッセージを埋め込むために、ＡＤＦ１３５の距離場に関連付けられる密度値を使用する。密度値は、ＬＣＤ及びＬＥＤのような表示装置上にレンダリングされるグリフの色を表し、それらはアドレス指定可能なピクセル構成要素を有する。そのような装置上でグリフのサブピクセルレンダリングを行うことの結果として、グリフの境界において色フリンジングのアーチファクトが出現する。文書の表示及び内容の特徴が知られている場合、色フリンジングが出現するロケーションを求めることが可能である。これらのロケーションは、上述したように、メッセージのシンボルを埋め込むことができる候補密度値を与える。
【００５６】
エイリアシングアーチファクト
当該技術分野において既知であるように、デジタルディスプレイ上でグリフをレンダリングすることによって、既知のジャギーのようなエイリアシングアーチファクトがもたらされる（援用される参照文献を参照されたい）。本発明の一実施形態において、メッセージはエイリアシングアーチファクト内に埋め込まれる。換言すれば、本発明では、密度値のセットの、エイリアシングアーチファクトが発生するサブセットを選択する。
【００５７】
実施形態例
文書内へのメッセージの埋め込み
図５は、グリフのセットを含む文書５０２内にメッセージ５０１のシンボルを埋め込む方法を示している。文書内のグリフはＡＤＦによって表される。
【００５８】
メッセージを文書に対する意図的な攻撃及び意図的でない変更から守るために、誤り訂正符号（ＥＣＣ）を使用してメッセージのシンボルを符号化する（５１０）。パケット化シンボルは、誤り及びノイズの存在下でメッセージの復号を可能にするように付加される。印刷文書の場合、誤り及び消失は、文書の物理的劣化及び検出器の制限に起因して発生し得る。ポータブル文書フォーマット（ＰＤＦ）文書のような電子文書の場合、物理的劣化又は送信誤りが起こる可能性はより小さい。しかしながら、検出器が埋め込みメッセージの誤った推定を回復するとき、誤りは依然として発生し得る。ＥＣＣは、代数的復号又は確率論的（軟判定）復号を可能にする。好都合な選択は、リード・ソロモン符号を使用することである。これらの符号は消失訂正に最適である。さらに、リード・ソロモン復号の成功は、一定の最低限の数のビットが正確に復号される限り、誤りのパターンに関わらず保証される。
【００５９】
メッセージのシンボル及びパリティシンボルを、同期シンボルを含む複数のパケットになるように構成する（５２０）。これによって、検出器における同期の損失が低減され、ひいては復号が容易になる。
【００６０】
グリフごと又は文書全体に対してＡＤＦ５０２が構築される。ＡＤＦは、シンボルを埋め込む（５４０）ことができる位置又はサブセット、すなわち頂点を求める（５３０）ためにトラバースされる。ＡＤＦのトラバースは、ラスタ走査順、形状の外周に沿って、又は任意の他の好都合な方式で行うことができる。好ましい実施形態では、トラバースはＡＤＦによって表される形状から独立している。
【００６１】
メッセージ埋め込みに適していると共に、たとえば候補距離値によって記述される候補位置のうち、幾つかの位置は埋め込み器及び検出器によって知られている秘密鍵５３１を使用して選択される。
【００６２】
次に、シンボルは、選択された位置において１つずつ埋め込まれる。１つの単純な方法は、位置においてＡＤＦを局所的にサブサンプリングすることである。この動作によって、形状の関連部分を表す忠実度がわずかに低減される。
【００６３】
別の方法は、埋め込み位置の近隣における距離値をわずかに変更する。距離が変更される方法に応じて、この操作の結果はグリフの形状の局所的な曲率における微細な変化となり得る。この変化によって、次にシンボル、すなわち０ビット又は１ビットが埋め込まれる。
【００６４】
次に、変更されたＡＤＦを使用して文書をレンダリングする（５５０）ことができる。次に、用途に応じて、文書を、たとえば印刷するか、電子メール送信するか、又はスクリーン上に表示する（５６０）ことができる。
【００６５】
各グリフのＡＤＦを独立して変更する代わりに、一実施形態はＡＤＦの普遍性を利用する。任意の数のグリフを含む文書内の領域を特定することができると共に、単一のＡＤＦを構築してその領域を表すことができる。したがって、メッセージ埋め込みの目的のために、本方法は一度に複数のグリフ、若しくはテキストのページ全体、又は何らかの他のグラフィックを処理することができる。グリフの任意の集合物内にメッセージを埋め込むための唯一の要件は、ＡＤＦを使用してその集合物を表すことが可能でなくてはならないということである。
【００６６】
文書内のメッセージの検出
図６は変更済み文書５６０内のメッセージ６５０を検出する方法を示している。ＡＤＦを文書５６０から構築する（６１０）。上述したように、ＡＤＦは個々のグリフ又はグリフのグループを表すことができる。この情報は、埋め込み器及び検出器によって共有されるか、又は副次的情報として検出器に明示的に送信されるかのいずれかである。検出器は、グリフが表示される解像度、すなわちグリフに関連付けられる四分木３００の分解レベルも知っている。
【００６７】
検出器は、各グリフを表すＡＤＦのデータベース６０１を或る所定の解像度で維持することができる。代替的に、データベースは、より複雑なグリフを構築するための構成要素として使用される、ストローク又はセリフのような基本形状のセットを格納することができる。
【００６８】
鍵５３１を使用して、ＡＤＦにおける、メッセージシンボル及びパリティシンボルが埋め込まれている位置（頂点）を特定し、位置における距離値を検出して（６２０）メッセージのシンボルを回復する。
【００６９】
たとえば、特定の位置において受信される文書５６０において表される形状と、所与の解像度における形状との間の誤差が所定の閾値を超える場合、０ビットが埋め込まれたと推定し、そうでない場合、１ビットが埋め込まれたと推定する。
【００７０】
回復されたシンボルをパケット化解除（depacketize）し（６３０）、ＥＣＣ復号６４０を適用してメッセージ６５０を推定する。
【００７１】
発明の用途
本発明は、文書内に含まれるグリフ内にメッセージを埋め込む。本明細書内で使用される場合、用語「グリフ」は、任意の言語の任意のフォントのテキスト文字、句読点、数字、及び飾り文字を含むが、これらに限定されない。この用語「グリフ」は、英語に似たアルファベット、又は日本語、中国語、韓国語、若しくはサンスクリット語デバナーガリ文字のフォントのようなストロークベースのフォントを含む。グリフは、アイコン、ロゴ、クリップアート、漫画、及び上記のすべてのもののアニメーションバージョンとすることもできる。
【００７２】
本発明は、プリンタ、プロッタ、又はファックス機の出力であるハードコピー文書、電子メールの添付ファイルとして送信されるか又はファイル転送プロトコル（ＦＴＰ）を使用してインターネットを介して転送されることが多いＰＤＦファイル又はＰＳファイルのような電子文書、ＭＳ  Ｗｏｒｄ若しくはＰａｇｅｓのような文書処理プログラム又はＡｄｏｂｅ  Ｐｈｏｔｏｓｈｏｐのようなグラフィック編集ソフトの出力である電子文書、２Ｄデジタルディスプレイ又は３Ｄデジタルディスプレイ上にレンダリングされる文書におけるグリフに適用することができる。
【００７３】
本発明によって以下の用途、すなわち、著作権保護及びデジタル著作権管理（ＤＲＭ）、文書認証、改ざん検出、文書、たとえば電子メールの流通経路の追跡、印刷、写真複写の反復、スキャン、再印刷、及びデバイスフォレンジックが可能になる。
【００７４】
本発明を特定の好ましい実施形態を参照して説明してきたが、本発明の精神及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【図１】
2010157993.tif 000003
【図２】
2010157993.tif 000004
【図３】
2010157993.tif 000005
【図４】
2010157993.tif 000006
【図５】
2010157993.tif 000007
【図６】
2010157993.tif 000008
【外国語明細書】
2010157993.tif 000009
2010157993.tif 000010
2010157993.tif 000011
2010157993.tif 000012
2010157993.tif 000013
2010157993.tif 000014
2010157993.tif 000015
2010157993.tif 000016
2010157993.tif 000017
2010157993.tif 000018
2010157993.tif 000019
2010157993.tif 000020
2010157993.tif 000021
2010157993.tif 000022
2010157993.tif 000023
2010157993.tif 000024
2010157993.tif 000025
2010157993.tif 000026
2010157993.tif 000027
2010157993.tif 000028
2010157993.tif 000029
2010157993.tif 000030
2010157993.tif 000031
2010157993.tif 000032
2010157993.tif 000033
2010157993.tif 000034
2010157993.tif 000035
2010157993.tif 000036
2010157993.tif 000037
2010157993.tif 000038
2010157993.tif 000039
2010157993.tif 000040
2010157993.tif 000041
2010157993.tif 000042