(57)【要約】  ひずみの低い画像透かし入れを行うシステム及び方法を提供する。画像の複数の画素及び／又は領域間のパリティ関係を、本明細書で説明するように活用して、画像に透かしを埋め込むのに必要とされる反転の量を低減することができる。これによって、透かし効率が上がり、透かし入り画像に導入される視覚アーチファクトが低減される。本明細書では、ブロック重ね合わせ式パリティ検査（ＢＯＰＣ）アルゴリズム、シャンパンピラミッド式パリティ検査（ＣＰＰＣ）アルゴリズム、及び木構造に基づくパリティ検査（ＴＢＰＣ）アルゴリズムを含めて、パリティ関係を活用するための様々なアルゴリズムが説明される。
2010532595.tif 000002
【特許請求の範囲】
【請求項１】
中間調画像及び前記画像に埋め込むべき２値透かしを識別するステップと、
データを埋め込むための前記画像内の候補位置を探索するステップと、
前記探索された候補位置を複数の重なり合うグループに形成するステップと、
個々の候補位置のグループのパリティ値を求めるステップと、
前記個々の候補位置のグループの前記パリティ値が前記２値透かし内の対応するビットとマッチするように、前記画像内の候補位置の中間調値を反転させるステップと
を含む、中間調画像に２値データを埋め込む方法。
【請求項２】
前記探索するステップは、前記画像内のマスタ候補位置及びスレーブ候補位置を探索するステップを有し、前記形成するステップは、前記探索されたマスタ候補位置を重なり合うグループに形成するステップを有し、前記求めるステップは、個々のマスタ候補位置のグループのパリティ値を求めるステップを有し、前記反転させるステップは、マスタ候補位置と、前記マスタ候補位置に隣接して前記マスタ候補位置と相補的なスレーブ候補位置とを有する個々の位置ペアの中間調値を反転させるステップを有する請求項１に記載の方法。
【請求項３】
前記探索するステップは、個々の擬似ランダム位置のところの前記中間調画像内の所定数の画素を、データを埋め込むための候補位置として識別するステップを有する請求項１に記載の方法。
【請求項４】
前記形成するステップは、前記候補位置をマップし、前記マップされた候補位置を複数の重なり合うブロックにグループ化するステップを有し、前記求めるステップは、個々のマップされた候補位置のブロックのパリティ値を求めるステップを有し、前記反転させるステップは、前記ブロックの前記パリティ値が前記２値透かし内の対応するビットとマッチしない個々のマップされた候補位置のブロックに位置する候補位置の中間調値を反転させるステップを有する請求項１に記載の方法。
【請求項５】
前記求めるステップは、前記個々のマップされた候補位置のブロックの前記求められたパリティ値に基づいてパリティマップを構築するステップをさらに有し、前記反転させるステップは、前記パリティマップ内の個々の値と前記２値透かし内の対応するビットとの比較から得られる結果を使用して反転マップを構築し、前記反転マップが前記ブロックの前記パリティ値と前記２値透かしの対応するビットとの間の不一致を示す個々のブロックに位置する候補位置の中間調値を反転させるステップをさらに有する請求項４に記載の方法。
【請求項６】
前記反転させるステップは、前記２値透かし内の対応するビットとマッチしないパリティ値を有する個々の交差するブロックに対応する前記反転マップ上の位置のグループを形成し、前記反転マップ上の前記位置のグループで表される前記候補位置のブロックに共通の候補位置の中間調値を反転させるステップをさらに有する請求項５に記載の方法。
【請求項７】
前記形成するステップは、前記探索された候補位置を、前記１つ又は複数のピラミッド構造の最下位層のところのノードの数が前記２値透かし内のビットの数と等しくなるような１つ又は複数の２値ピラミッド構造に形成するステップを有し、前記求めるステップは、前記１つ又は複数のピラミッド構造の前記最下位のところの個々のノードのパリティ値を、ピラミッド構造の前記最下位層にあるノードと前記最下位層にある前記ノードを直接又は間接の後続ノードとして有する前記ピラミッド構造内の個々のノードとを備える個々のグループのパリティを求めることによって求めるステップを有する請求項１に記載の方法。
【請求項８】
前記反転させるステップは、
求められたノードのパリティ値が対応する前記２値透かしのビットと異なるピラミッド構造の前記最下位のところの個々のノードの反転指示を提供するステップと、
ノードの反転指示が提供される連続するノードのグループを識別するステップと、
識別された連続するノードのグループ内の各ノードによって提供される反転指示を、前記識別された連続するノードのグループ内の各ノードに共通の最低位の先行ノードで置き換えるステップと、
ノードの反転指示が提供される前記ピラミッド構造内のノードに対応する前記中間調画像内の個々の候補位置の中間調値を反転させるステップと
を有する請求項７に記載の方法。
【請求項９】
前記求めるステップは、ノードに対応する候補位置の前記中間調値と、パリティ値が計算される前記ノードの左ソースノードのパリティ値と、パリティ値が計算される前記ノードの右ソースノードのパリティ値と、前記左ソースノード及び前記右ソースノードの共通ソースノードである上ソースノードのパリティ値とに対する排他的論理和演算を行うことによって前記ノードのパリティ値を求めるステップを有する請求項７に記載の方法。
【請求項１０】
前記形成するステップは、前記探索された候補位置を、葉ノードの数が前記２値透かし内のビットの数と等しくなるような１つ又は複数の完全Ｎ進木構造に形成するステップを有し、前記求めるステップは、前記１つ又は複数の木構造の個々の葉ノードのパリティ値を、前記個々の葉ノードから根ノードまでのパス内のノードのパリティを求めることによって求めるステップを有する請求項１に記載の方法。
【請求項１１】
前記反転させるステップは、
前記１つ又は複数の木構造の前記葉ノードの個々のパリティ値と前記２値透かし内の対応するビットとを比較することによって反転配列を獲得するステップと、
少なくとも一部は、前記反転配列の個々の要素を葉ノードとして使用することによって、前記１つ又は複数の木構造に対応する１つ又は複数の反転木を構築するステップと、
そのすべての葉ノードが、前記葉ノードのパリティ値が前記２値透かし内の対応するビットとマッチしないことを示す前記１つ又は複数の反転木内の個々の最高位ノードに対応する前記中間調画像内の個々の候補位置の中間調値を反転させるステップと
を有する請求項１０に記載の方法。
【請求項１２】
前記求めるステップは、木構造内のノードのパリティ値を、前記ノードに対応する候補位置の前記中間調値と、パリティ値が計算される前記ノードの親ノードのパリティ値との間で排他的論理和演算を行うことによって求めるステップを有する請求項１０に記載の方法。
【請求項１３】
請求項１に記載の方法を実行するように動作する命令が記憶されているコンピュータ可読媒体。
【請求項１４】
中間調ホスト画像を受け取り、データを埋め込むための前記ホスト画像内の１つ又は複数の候補位置を識別する埋め込み候補選択構成要素と、
前記識別された候補位置を重なり合うグループに形成し、前記個々のグループを構成する前記候補位置の個々の中間調値のグループのパリティを求めるパリティ検査構成要素と、
個々のグループのパリティを前記ロゴの対応する情報ビットと比較し、前記グループの前記パリティが前記ロゴの前記対応する情報ビットとマッチしない個々のグループ内の候補位置の前記中間値を反転させるデータ隠蔽構成要素と
を備える、中間調ホスト画像にロゴに対応するデータを隠し込むシステム。
【請求項１５】
前記埋め込み候補選択構成要素は、前記ホスト画像内の候補マスタ位置の集合及び候補スレーブ位置の集合を擬似ランダムに識別し、
前記パリティ検査構成要素は、前記識別されたマスタ候補位置の集合を使用してマスタマップを構築し、マップされたマスタ候補位置の重なり合うブロックについて得られたパリティ値に基づいてパリティマップを構築し、
前記データ隠蔽構成要素は、前記パリティマップの個々の要素を前記ロゴ内の対応する情報ビットと比較することによって反転マップを構築し、非マッチングパリティが示されるマスタ候補位置の重なり合うブロックに対応する前記反転マップ内の要素をグループ化し、非マッチングパリティが示される前記反転マップ内の要素の個々のグループについてマスタ候補位置と逆の中間調値を有する隣接するスレーブ候補位置とを備える候補位置のペアの中間調値を反転させる
請求項１４に記載のシステム。
【請求項１６】
前記パリティ検査構成要素は、前記１つ又は複数の識別された候補位置に基づく個々の要素を備える１つ又は複数のシャンパンピラミッド構造を、前記１つ又は複数のシャンパンピラミッド構造の最下位層のところの要素の数が前記ロゴ内の情報ビットの数と等しくなるように構築し、前記１つ又は複数のシャンパンピラミッド構造の前記最下位層のところの前記要素の個々のパリティ値を獲得し、
前記データ隠蔽構成要素は、前記個々の要素の前記パリティ値が前記ロゴ内の前記対応する情報ビットとマッチしない前記１つ又は複数のシャンパンピラミッド構造の前記最下位層のところの個々の要素を判定し、識別された要素の連続するグループを識別し、前記識別されたグループについての前記１つ又は複数のシャンパンピラミッド構造内の最低位の共通先行ノードに対応する候補位置の中間調値を反転させる
請求項１４に記載のシステム。
【請求項１７】
前記パリティ検査構成要素は、前記１つ又は複数の識別された候補位置に基づく個々の要素を備える１つ又は複数のマスタツリー構造を、前記１つ又は複数のマスタツリー構造内の葉ノードの数が前記ロゴ内の情報ビットの数と等しくなるように構築し、前記１つ又は複数のマスタツリー構造の前記葉ノードの個々のパリティ値を獲得し、
前記データ隠蔽構成要素は、前記１つ又は複数のマスタツリー構造内の個々の葉ノードのパリティ値と前記ロゴ内の対応する情報ビットとの比較を反転配列に取り込み、前記１つ又は複数のマスタツリーに対応する１つ又は複数の反転木を、少なくとも一部は、前記反転配列内の前記比較を前記１つ又は複数の反転木の葉ノードとして利用することによって構築し、共通の親ノードのすべての子ノードによって提供される個々の反転指示を、前記親ノードの単一の反転指示で繰り返し置き換え、反転指示を提供する前記１つ又は複数の反転木のノードに対応する候補位置の中間調値を反転させる
請求項１４に記載のシステム。
【請求項１８】
原ホスト画像を識別し、少なくとも一部は前記原ホスト画像を処理することによって１つ又は複数の中間調ホスト画像を生成し、前記１つ又は複数の生成された中間調ホスト画像を前記埋め込み候補選択構成要素に提供する画像処理構成要素をさらに備える請求項１４に記載のシステム。
【請求項１９】
前記画像処理構成要素は、少なくとも一部は、所定の閾値を上回る値を有する原ホスト画像内の個々の画素を第１の中間調値に変換し、前記所定の閾値を下回る値を有する前記原ホスト画像内の個々の画素を第２の中間調値に変換することによって前記原ホスト画像から中間調ホスト画像を生成する請求項１８に記載のシステム。
【請求項２０】
データを埋め込むことのできる中間調画像内の画素を決定する手段と、
前記決定された画素を複数の交差するグループにグループ化する手段と、
前記複数の交差するグループの個々のパリティ値を取得する手段と、
前記取得されたパリティ値を透かしの対応する情報ビットと比較する手段と、
少なくとも一部は、個々のグループの前記パリティ値と前記透かしの前記対応する情報ビットとの間に不一致が存在する前記個々のグループと関連付けられる決定された画素の中間値を変更することによって、前記中間調画像に前記透かしを埋め込む手段と
を備える、中間調画像の透かし入れを円滑に行わせるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
［相互参照］
本出願は、２００７年４月４日に出願された、「ＭＵＬＴＩＭＥＤＩＡ  ＷＡＴＥＲＭＡＲＫＩＮＧ  ＴＥＣＨＮＩＱＵＥＳ  ＷＩＴＨ  ＬＯＷ  ＤＩＳＴＯＲＴＩＯＮ」という名称の米国仮特許出願第６０／９０７５１３号の利益を主張するものである。
【０００２】
［発明の分野］
本開示は一般には画像処理に関し、より詳細には、画像に透かし情報を埋め込む技法に関する。
【背景技術】
【０００３】
マルチメディアアプリケーションの人気が高まり、インターネット及び無線技術が進歩するにつれて、画像などのディジタルメディアの使用が急速に増大している。例えば、今ではワールド・ワイド・ウェブを介して多くの画像にアクセスすることができる。しかし、これらのディジタル画像は、そのアクセスが容易であるがゆえに、無許可のユーザにより予期せぬ目的のために簡単にダウンロードされ、使用されるおそれがある。このためしばしば、電子透かし入れの技法を使用して、ディジタルメディアの所有権及び信憑性を証明するために、メディアに、ランダムシーケンスやロゴといった情報が隠し込まれる。
【０００４】
画像における透かしのセキュリティを高めるには、透かしが知覚透過的で、ロバストであるように透かしを画像に埋め込むべきであることが理解される。しかし、大部分の既存の画像透かし入れの技法は損失が多く、埋め込みプロセスの間にホスト画像に永久的なひずみを導入し、その結果としてホスト画像に永久的なピーク信号対雑音比（ＰＳＮＲ）損失が生じる。このため、多くの既存の透かし入れの技法は、医用分野、軍事分野、及び／又はひずみを埋め込むことの影響を受けやすく、永久的な信号忠実度の損失が禁じられる用途には適用することができない。したがって、そのような用途には、ホスト信号から透かしを抽出する際に元のホスト信号を完全に回復することのできる、損失なしの可逆的透かし入れ方式が必要である。可逆的透かし入れのアルゴリズムも提案されている。しかし、そのようなアルゴリズムのペイロードは、損失の多い透かし入れアルゴリズムのペイロードと比べると法外に小さい。
【０００５】
さらに、白黒の画素のみを含む中間調白黒画像を利用する書籍、雑誌、新聞、印刷機出力、ファックス文書といった特定の応用例では、著作権保護及び／又は認証目的のために、企業ロゴといった付加価値を付ける不可視データを隠蔽することが望ましい場合が多い。しかし、大部分の既存のデータ隠蔽アルゴリズムは、簡単には、これら及び／又は類似の中間調信号にデータを埋め込むのに適用することができない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
以上を鑑みると、ディジタル画像のための効率のよい、高ペイロードの透かし入れの技法が求められている。
【０００７】
以下、特許請求する主題のいくつかの態様の基本的な理解を提供するための、特許請求する主題の簡略化した概要を示す。この概要は、特許請求する主題を網羅的に総括するものではない。特許請求する主題の重要な、又は不可欠な要素を識別することも、特許請求する主題の範囲を正確に叙述することも意図するものではない。この概要の唯一の目的は、後述するより詳細な説明の前段として特許請求する主題のいくつかの概念を簡略化された形で提示することにある。
【０００８】
本開示は、ひずみの低い中間調画像の透かし入れのシステム及び方法を提供するものである。一態様によれば、画像の複数の画素及び／又は領域間のパリティ関係を活用して、画像に透かしを埋め込むのに必要な反転の量が低減され、それによって透かしの効率が上がり、透かし入り画像に導入される視覚的アーチファクトが低減される。
【０００９】
一例では、ブロック重ね合わせ式パリティ検査（ＢＯＰＣ：Ｂｌｏｃｋ−Ｏｖｅｒｌａｐｐｉｎｇ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）アルゴリズムを利用して、データ隠蔽スマートペア反転（ＤＨＳＰＴ：Ｄａｔａ  Ｈｉｄｉｎｇ  Ｓｍａｒｔ  Ｐａｉｒ  Ｔｏｇｇｌｉｎｇ）といった従来の中間調画像データ隠蔽アルゴリズムを拡張し、そうした従来のアルゴリズムを使用して透かしを入れた画像の視覚品質を改善することができる。ホスト画像のブロック重ね合わせ式パリティ検査の様々な特性を決定し、それらを活用することによって、ＤＨＳＰＴ及び／又は類似の従来からのデータ隠蔽アルゴリズムに必要とされるペア反転操作の回数を低減することができる。
【００１０】
別の例では、シャンパンピラミッド式パリティ検査（ＣＰＰＣ：Ｃｈａｍｐａｇｎｅ  Ｐｙｒａｍｉｄ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）アルゴリズム及び／又は木構造に基づくパリティ検査（ＴＢＰＣ：Ｔｒｅｅ−Ｂａｓｅｄ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）アルゴリズムを利用して、従来の可逆的透かし入れの技法によって処理された画像の視覚品質を改善することができる。ホスト画像内のデータ埋め込みのための候補位置を階層構造として表わすことによって、ＣＰＰＣアルゴリズム及び／又はＴＢＰＣアルゴリズムは、透かし挿入プロセスの間に必要とされる画素変更の総数を低減させることができ、それによって効率が上がり、透かし入り画像に導入されるひずみが低減される。
【００１１】
以上及び関連の目的を達成するため、本明細書では、特許請求する主題のいくつかの例示的態様を、以下の説明及び添付の図面との関連で説明する。しかし、これらの態様は、特許請求する主題の原理を用いることのできる様々なやり方のうちのいくつかを示すにすぎない。特許請求する主題は、このようなすべての態様及びこれらの均等物を含むものである。特許請求する主題の他の利点及び新規の特徴は、以下の詳細な説明を図面と併せて考察すれば明らかになるものである。
【図面の簡単な説明】
【００１２】
【図１】様々な態様による画像を処理し、伝えるシステムを示すハイレベルブロック図である。
【図２】様々な態様による画像に情報を埋め込む個々のシステムを示すブロック図である。
【図３】様々な態様による画像に情報を埋め込む個々のシステムを示すブロック図である。
【図４】本明細書で説明する様々な態様による中間調画像にデータを隠し込む例示的技法を実行するシステムを示すブロック図である。
【図５】本明細書で説明する１つ又は複数のデータ隠蔽の技法と関連させて実行することのできるマッピング操作の例を示す図である。
【図６】本明細書で説明する１つ又は複数のデータ隠蔽の技法と関連させて実行することのできるマッピング操作の例を示す図である。
【図７】本明細書で説明する１つ又は複数のデータ隠蔽の技法と関連させて実行することのできるバブル形成操作の例を示す図である。
【図８】本明細書で説明する１つ又は複数のデータ隠蔽の技法と関連させて実行することのできるバブル形成操作の例を示す図である。
【図９】本明細書で説明する１つ又は複数のデータ隠蔽の技法と関連させて実行することのできる反転操作の例を示す図である。
【図１０】本明細書で説明する様々な態様による画像に２値ロゴを埋め込む例示的技法を実施するシステムを示すブロック図である。
【図１１】本明細書で説明する１つ又は複数のデータ埋め込みの技法と関連させて利用することのできるデータ構造の例を示す図である。
【図１２】本明細書で説明する１つ又は複数のデータ埋め込みの技法と関連させて利用することのできるデータ構造の例を示す図である。
【図１３】本明細書で説明する１つ又は複数のデータ埋め込みの技法と関連させて利用することのできるデータ構造の例を示す図である。
【図１４】本明細書で説明する１つ又は複数のデータ埋め込みの技法と関連させて実行することのできる更新操作及び反転操作の例を示す図である。
【図１５】本明細書で説明する１つ又は複数のデータ埋め込みの技法と関連させて実行することのできる更新操作及び反転操作の例を示す図である。
【図１６】本明細書で説明する様々な態様による画像の透かし入れを円滑に行わせるシステムを示すブロック図である。
【図１７】本明細書で説明する１つ又は複数の透かし入れの技法に利用することのできるデータ構造の例を示す図である。
【図１８】本明細書で説明する１つ又は複数の透かし入れの技法と関連させて実行することのできる個々の操作を示す図である。
【図１９】本明細書で説明する１つ又は複数の透かし入れの技法と関連させて実行することのできる個々の操作を示す図である。
【図２０】画像に透かし情報を埋め込む個々の方法を示す流れ図である。
【図２１】画像に透かし情報を埋め込む個々の方法を示す流れ図である。
【図２２】画像に透かし情報を埋め込む個々の方法を示す流れ図である。
【図２３】画像に透かし情報を埋め込む個々の方法を示す流れ図である。
【図２４】本明細書で説明する様々な態様が機能しえる動作環境の例を示すブロック図である。
【図２５】本明細書で説明する様々な態様が機能しえるネットワーク接続されたコンピュータ環境の例を示すブロック図である。
【発明を実施するための形態】
【００１３】
次に、図面を参照して特許請求する主題を説明する。図面において類似の符番は全体を通して類似の要素を指し示すのに使用される。以下の記述では、特許請求する主題の十分な理解を提供するために説明として多くの具体的詳細が示される。しかし、特許請求する主題はこれらの具体的詳細なしでも実施され得ることは明らかであろう。場合によっては、特許請求する主題の説明を容易にするために周知の構造及び装置をブロック図として示す。
【００１４】
本出願で使用する場合、「構成要素（ｃｏｍｐｏｎｅｎｔ）」、「システム（ｓｙｓｔｅｍ）」などの用語は、コンピュータ関連のエンティティ、すなわち、ハードウェア、ハードウェアとソフトウェアの組み合わせ、ソフトウェア、又は実行中のソフトウェアのいずれかを指し示すためのものである。例えば、構成要素は、それだけに限らないが、プロセッサ上で走るプロセス、プロセッサ、オブジェクト、実行形式のファイル、実行のスレッド、プログラム、及び／又はコンピュータとすることができる。例えば、サーバ上で走るアプリケーションも、そのサーバも構成要素とすることができる。１つ又は複数の構成要素が１つのプロセス及び／又は実行のスレッド内にあってもよく、構成要素は、１台のコンピュータ上に局在化されていてもよく、及び／又は２台以上のコンピュータ間に分散されていてもよい。また、特許請求する主題の方法及び装置、又はそのいくつかの態様もしくは部分は、フロッピィディスケット、ＣＤ−ＲＯＭ、ハードドライブ、他の任意の機械可読記憶媒体といった有形の媒体に組み込まれたプログラムコード（すなわち命令）の形を取ってもよく、その場合、プログラムコードがコンピュータなどの機械にロードされ、実行されると、その機械は特許請求する主題を実施する装置になる。各構成要素は、１つ又は複数のデータパケット（ローカルシステム、分散システムにおいて別の構成要素と、かつ／又はインターネットなどのネットワークを介して信号により他のシステムとやりとりするある構成要素からのデータなど）を有する信号などによるローカル及び／又はリモートのプロセスを介してやりとりすることもできる。
【００１５】
図面を参照すると、図１には、本明細書で説明する様々な態様による、画像を処理し、伝えるシステム１００のハイレベルブロック図が示されている。一例では、システム１００は、ホスト画像１０２に透かし１０４を埋め込むことによりホスト画像１０２から透かし入り画像１２０を作成することのできる透かし入れ構成要素１１０を含む。透かし１０４は、システム１００において、外部ソースから透かし入れ構成要素１１０に提供されるものとして示されているが、代替として、透かし入れ構成要素１１０が透かし１０４を内部で作成することもできることを理解すべきである。さらに、システム１００は２次元画像の透かし入れを示しているが、透かし入れ構成要素１１０は、代替として、３空間次元のオブジェクトの図形表現や、それぞれの持続時間を有する一連の２次元ビデオフレームを含むビデオシーケンスといった、３次元以上のデータを受け取ることもできることを理解すべきである。そのような例では、透かし入れ構成要素１１０は、ホスト信号の個々の２次元断面又はフレームを、透かし入れ構成要素１１０がそこに１つ又は複数の透かし１０４を埋め込んで対応する透かし入り画像１２０を生成することのできる一連のホスト画像１０２として処理することができる。
【００１６】
一態様によれば、透かし入れ構成要素１１０を利用して、中間調ホスト画像１０２に２値透かし１０４を埋め込むことができる。本明細書で使用する場合、また当分野において一般に、中間調画像は、画像内のすべての画素が、それぞれ２進数字「０」及び「１」で表すことのできる２つの可能な画素値のうちの１つ（黒又は白など）を有するように生成される。そのような画像は、書籍、雑誌、新聞、印刷機出力、ファックス文書などでマルチトーングレースケール画像を表わすのに広く使用されている。多くの既存のデータ隠蔽の技法はマルチトーン画像用に設計されており、したがって、中間調画像には適用できない。これらの限界を克服するために、透かし入れ構成要素１１０は、ブロック重ね合わせ式パリティ検査（ＢＯＰＣ）、シャンパンピラミッド式パリティ検査（ＣＰＰＣ）、木構造に基づくパリティ検査（ＴＢＰＣ）などといった１つ又は複数のアルゴリズムを実施して、中間調ホスト画像１０２に透かしデータを埋め込むことができる。ＢＯＰＣ、ＣＰＰＣ及びＴＢＰＣの各アルゴリズムについては、後で詳細に説明する。
【００１７】
別の態様によれば、１つ又は複数の通信路を介して、透かし入り画像１２０から個々の透かし１０４を抽出することにより透かし入り画像１２０から個々のホスト画像１０２を回復することのできる抽出構成要素１３０に、透かし入れ構成要素１１０によって生成された透かし入り画像１２０を送ることができる。一例では、抽出構成要素１３０は、ＢＯＰＣ、ＣＰＰＣ、及び／又はＴＢＰＣといったデータ隠蔽アルゴリズムを用いて、画像内のどの画素が透かし１０４に関連するデータを提供するか判定することにより、透かし入り画像１２０に埋め込まれている２値透かし１０４を獲得することができる。次いで、判定された画素及び／又は画素を取り囲む領域を調べて、透かし１０４を含むデータを確認することができる。一例では、透かし入れ構成要素１１０によって利用される透かし１０４のサイズ及び形状を透かし入れ構成要素１１０から抽出構成要素１３０に送ることができ、かつ／又は事前に抽出構成要素１３０に知らせることができる。
【００１８】
システム１００内のエンティティ間の透かし入り画像１２０のやりとりを円滑に行わせるために、１つ又は複数の有線（イーサネット（登録商標）、ＩＥＥＥ８０２．３など）及び／又は無線（ＩＥＥＥ８０２．１１、ブルートゥース（商標）など）ネットワーク技術を利用することができる。加えて、抽出構成要素１３０は、透かし入れ構成要素１１０に直接接続することも、第三者装置（不図示）を介して間接的に接続することもできる。例えば、抽出構成要素１３０は、インターネット・サービス・プロバイダ（ＩＳＰ）によるインターネットを介してメディアコンテンツを提供するウェブサーバから透かし入り画像１２０を受け取るクライアントコンピュータと関連付けることもできる。別の例として、抽出構成要素１３０は、ＧＳＭ通信（Ｇｌｏｂａｌ  Ｓｙｓｔｅｍ  ｆｏｒ  Ｍｏｂｉｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）、ＣＤＭＡ（符号分割多元接続）通信システム、及び／又は別の適切なセルラ通信ネットワークなどといったセルラ通信ネットワークを介してメディアコンテンツにアクセスする移動端末と関連付けることもできる。
【００１９】
次に図２を参照すると、画像に情報を埋め込むシステム２００のブロック図が示されている。一態様によれば、システム２００は透かし入れ構成要素２１０を含むことができ、この要素は、入力として原画像とロゴを受け取り、原画像へのロゴの埋め込みを円滑に行わせ、出力として透かし入り画像を提供することができる。一例では、原画像にロゴを埋め込んで透かし入り画像を生成するのを円滑に行わせるために、透かし入れ構成要素２１０は、埋め込み候補選択構成要素２２０、パリティ検査構成要素２３０、及び／又はデータ隠蔽構成要素２４０を備えることができる。
【００２０】
一態様によれば、埋め込み候補選択構成要素２２０は、データを埋め込むための原画像内の候補位置を識別するために原画像の探索、走査、及び／又はその他の処理を行うことができる。画像内の候補位置は、個々の画素とすることもでき、かつ／又は隣接する、もしくは隣接しない画素のグループとすることもできる。一例では、埋め込み候補選択構成要素は、画像内の「マスタ」候補位置と「スレーブ」候補位置を識別することができる。次いで、マスタ候補埋め込み位置とスレーブ候補埋め込み位置の集合に基づき、データ隠蔽アルゴリズムを、マスタ位置を反転させるときに、さらに逆の中間調値を有する近隣のスレーブ位置も反転させるように構成することができる。そうすることにより、マスタ位置を含む画像領域の局所的輝度を保存することができ、それによって画像全体の視覚品質が改善される。
【００２１】
埋め込み候補選択構成要素２２０がデータを埋め込むための画像内の候補位置を識別した後で、それらの候補位置をパリティ検査構成要素２３０に提供することができる。一態様によれば、パリティ検査構成要素２３０は候補位置をグループに分けることができる。次いでこれらのグループを、個々のグループを構成する候補位置の中間調値のパリティによって特徴付けることができる。非限定的な具体例としては、中間調値を２進数字「０」又は「１」として表わすことができ、そのような中間調値のグループのパリティを、例えば、「１」という中間調値を有するグループ内の候補位置の数が奇数である場合にはグループのパリティを「１」とし、候補位置の数が偶数である場合には「０」とするような奇偶パリティとすることができる。しかし、これは単に、位置のグループのパリティを得ることのできる１つのやり方を構成するにすぎず、どんな適切な技法でも使用し得ることを理解すべきである。
【００２２】
一態様によれば、パリティ検査構成要素２３０によって形成される原画像内の候補位置の個々のグループのパリティを利用して、ロゴ内の情報ビットを表わすことができる。さらに、パリティ検査構成要素は、候補位置のグループを、それらが重なり合うように形成することができ、それによって、単一の候補位置の中間調値を反転させることにより複数のグループのパリティを変更させることが可能になる。そうすることにより、原画像にロゴを埋め込むのに必要な反転の量を低減することができ、それによって、埋め込み効率が上がり、透かし入り画像に導入されるひずみが低減される。本明細書で説明する様々な態様によれば、パリティ検査構成要素２３０は、画像の効率的な透かし入れを円滑化するために原画像内の候補位置の集合をグループに分けるための様々なアルゴリズムを利用することができる。利用できるアルゴリズムの例については後で詳細に説明する。
【００２３】
パリティ検査構成要素２３０による処理の後、パリティ検査構成要素２３０によって形成された原画像内の候補位置のグループ及び各グループのパリティ値を、原画像へのロゴの埋め込みを円滑に行わせるためにデータ隠蔽構成要素２４０に提供することができる。一例では、データ隠蔽構成要素２４０は、ロゴの個々の情報ビットを、原画像内の候補位置のパリティ又は対応するグループと比較することができる。ロゴ内の情報ビットとこれに対応する候補位置のグループのパリティがマッチしないと判定される場合、グループ内の候補位置を反転させて、グループのパリティをマッチが作成されるように変更することができる。一態様によれば、パリティ検査構成要素２３０によって提供される候補位置の個々のグループは、候補位置を共有し、かつ／又は別のやり方で重なり合うものとすることができる。その結果、複数のグループのパリティを単一の反転操作で変更することができ、それによって、画像にロゴを埋め込むのに必要とされる反転操作の量が低減される。一例では、反転は、単一位置の単純反転やマスタ／スレーブ位置ペアのペア反転といった、当分野で公知の１つ又は複数の技法に基づくものとすることができる。
【００２４】
図３を参照すると、画像にデータを埋め込む別のシステム２５０のブロック図が示されている。一態様によれば、システム２５０は、画像処理構成要素２６０を含むことができ、この要素は、原画像又はホスト画像を受け取り、その原画像を様々なやり方で処理して処理画像を生成することができる。次いで、処理画像及び２値ロゴを透かし入れ構成要素２７０に提供することができ、この要素は、透かし入れ構成要素２１０と同様に、かつ／又は後述する様々な態様に従って処理画像に２値ロゴを埋め込むように機能することができる。
【００２５】
一例では、透かし入れ構成要素２７０は、２値中間調画像といった特定のクラスの画像のための透かし入れを行うように動作させることができ、画像処理構成要素２６０は、原画像を受け取り、その原画像を、透かし入れ構成要素２７０が操作する画像クラスに合致するように処理することができる。非限定的な具体例では、透かし入れ構成要素２７０は、２値中間調画像に２値ロゴを埋め込むように動作することができ、画像処理構成要素２６０は、グレースケール画像などといった連続する画像又はマルチトーン画像を受け取ることができる。そのような例では、画像処理構成要素２６０は、例えば、所与の閾値を上回るマルチトーン値を有するマルチトーン画像内の画素を第１の中間調値に変換し、閾値を下回るマルチトーン値を有する画素を第２の中間調値に変換することなどによって、マルチトーン画像を中間調画像に変換することができる。次いで、本明細書で示す様々な態様による透かし入れ構成要素２７０によって、結果として生じる中間調画像に２値ロゴを埋め込むことができる。
【００２６】
別の非限定的な具体例では、画像処理構成要素２６０は、透かし入れ構成要素２７０において２値ロゴを埋め込むべきカラー画像を受け取ることができる。そのような例では、画像処理構成要素２６０は、原カラー画像を様々なやり方で処理することができる。例えば、画像処理構成要素２６０は、原カラー画像をその個々の色成分に分けることができ、次いでそれらの色成分を個別に中間調で表現して一連のカラー中間調画像を作成することができる。具体例を挙げると、そのような例における画像処理構成要素は、カラー画像を３つの画像に分割することができ、それらの３画像はそれぞれ、画像の赤色成分、青色成分、及び緑色成分だけを含む。次いで、これらの成分画像を個別に中間調で表現し、そこにデータを埋め込むために透かし入れ構成要素２７０に提供することができる。別の例として、画像処理構成要素２６０は、原画像内の個々の画素のところの色及び／又は階調に対応する２進値を獲得することもできる。次いでこれらの２進値を透かし入れ構成要素２７０に提供することができ、続いて透かし入れ構成要素２７０は、原画像の個々の画素を表わす２進色値に透かし情報を埋め込むことができる。別の例として、画像処理構成要素２６０は、２値ロゴを埋め込むべき、漫画画像などの少ない色の画像を受け取ることができる。次いで画像処理構成要素は、画像内に存在する色の組を判定し、識別された各色を、第１の集合内の色は第１の２値ビットを表わし、第２の集合内の色は第２の２値ビットを表わすような２つの集合に分けることができる。次いで、その少ない色の画像及び各色集合を画像処理構成要素２６０から透かし入れ構成要素２７０に提供することができ、透かし入れ構成要素２７０は、本明細書で説明する様々な態様により、必要に応じて、第１の色集合内の色を有する画素を第２の色集合内の選択された色に反転させることによって、又はその逆によって、画像に２値ロゴを埋め込むことができる。色集合内での反転に使用される色は、任意の適切なやり方で選択することができる。
【００２７】
前述の図３の操作に関連する各例は例として示したにすぎず、添付の特許請求の範囲を限定するためのものではないことを理解すべきである。さらに、システム２５０の動作に関連して一連の例を説明しているが、システム２５０は画像への透かし挿入を円滑に行わせるのに適したどんなやり方で動作してもよいことも理解すべきである。
【００２８】
次に図４を見ると、本明細書で説明する様々な態様による、中間調画像にデータを隠し込む技法の例を実行するシステム３００のブロック図が示されている。一例では、サイズＬＸ×ＬＹのディジタルロゴＬ３１０を透かし入れ構成要素３４０がサイズＳＸ×ＳＹの原又はホスト中間調画像Ｓ３２０に埋め込んで、透かし入り中間調画像Ｗ３３０を形成することができる。
【００２９】
一態様によれば、透かし入れ構成要素３４０は、原画像３２０にロゴ３１０を埋め込むためにＢＯＰＣアルゴリズムを実施することができる。図４で示すように、透かし入れ構成要素３４０は、下位構成要素３４２〜３５０を利用してＢＯＰＣアルゴリズムを実施することができる。まず、原画像３２０を、ロゴ３１０に対応するデータを埋め込むための原画像３２０内の候補マスタ及びスレーブ画素を識別するために、マスタ／スレーブ画素選択構成要素３４２に提供することができる。一例では、マスタ／スレーブ画素選択構成要素３４２は、従来からのデータ隠蔽スマートペア反転（ＤＨＳＰＴ）アルゴリズムと同様のやり方で原画像３２０内の候補画素を選択することができる。より詳細には、ＤＨＳＰＴアルゴリズムと同様に、マスタ／スレーブ画素選択構成要素３４２は、データを隠蔽するための擬似ランダム位置の集合を選択することができる。さらに、マスタ／スレーブ画素選択構成要素３４２は、マスタ及びスレーブの各画素集合を、原画像３２０内のマスタ画素が反転される場合、逆の中間調値を有する近隣のスレーブ画素も反転させて局所的輝度を保存し、結果として生じる透かし入り画像３３０が視覚的に高品質になるように構成することができる。
【００３０】
しかし、ＤＨＳＰＴなどの従来のアルゴリズムとは異なり、透かし入れ構成要素３４０にはさらに、ＤＨＳＰＴの強みを採り入れると同時に、性能も向上させるという特徴が加わる。例えば、マスタ／スレーブ画素選択構成要素３４２によって識別されたマスタ及びスレーブの各画素集合をブロック重ね合わせ式パリティ検査構成要素３４４に提供することができ、そこで、識別された画素集合からマスタマップやパリティマップといったデータ構造を作成して、データ隠蔽に必要な反転の量を、ＤＨＳＰＴなどの従来のデータ隠蔽の技法と比べて低減することができる。次いで、反転マップ形成構成要素３４６を使用して、ブロック重ね合わせ式パリティ検査構成要素が生成したパリティマップをロゴ３１０と比較することにより、原画像３１０の反転マップを生成することができる。反転マップが生成された後で、バブル形成構成要素３４８は、反転マップを処理して、原画像３２０内でスマートペア反転を適用すべき位置を選択することができる。最後に、ペア反転構成要素３５０を利用して、バブル形成構成要素３４８が決定した位置において原画像３２０の画素を反転させることにより、原画像３２０にロゴ３１０を埋め込んで透かし入り画像３３０を生成することができる。
【００３１】
一態様によれば、透かし入れ構成要素３４０は、画像３２０にロゴ３１０を埋め込むためのＢＯＰＣアルゴリズムを以下のように用いることができる。まず、マスタ／スレーブ画素選択構成要素３４２は原画像Ｓ内の各画素をマスタ画素及びスレーブ画素のグループに分けることができる。一例では、必要な場合にはペア反転構成要素３５０でマスタ画素を反転させて埋め込みロゴデータを格納することもできる。マスタ画素が反転されるときには、画像３２０における局所的輝度を保存するために補完的に近隣のスレーブ画素も反転させることができる。具体例としては、既知のシードＫを有する擬似乱数発生器を利用して、マスタ／スレーブ画素選択構成要素３４２が画像Ｓ内の（２ＬＸ＋１）×（２ＬＹ＋１）擬似ランダム位置の集合を生成することができ、次いでそれらの位置をマスタ画素として利用することができる。マスタ画素選択の例を図４のホスト画像４１０で示す。一態様によれば、ペア反転構成要素３５０は、近隣のマスタ画素とスレーブ画素との対を反転させることができる。したがって、マスタ／スレーブ画素選択構成要素３４２は、マスタ画素を、各マスタ画素がそれぞれその３×３の近傍内の８個のスレーブ画素によって取り囲まれるように選択することができる。
【００３２】
マスタ／スレーブ画素選択構成要素３４２によって決定されたマスタ画像の位置に基づき、ブロック重ね合わせ式パリティ検査構成要素３４４はマスタ画素をまとめてグループ化してマスタマップＭを形成することができる。マスタマップグループ化の例を図５にマスタマップ４２０で示す。次いでブロック重ね合わせ式パリティ検査構成要素３４４はさらに、マスタマップ４２０に個々の画素の位置を、位置マッピング表４３０にホスト画像を記憶させることができる。次いで、図６の図解５００で示すように、ブロック重ね合わせ式パリティ検査構成要素３４４が、マスタマップＭ内の各要素を重なり合うブロックに分けることができる。図解５００には３×３ブロックのマスタ画素が示されているが、ブロック重ね合わせ式パリティ検査構成要素３４４によって作成されるブロックは任意の適切なサイズとすることができることを理解すべきである。さらに、各ブロックは均一なサイズとすることも、不均一なサイズとすることもできる。
【００３３】
一態様によれば、透かし入れ構成要素３４０は、ブロックのパリティを使用してマスタマップＭに１つのロゴビットを隠し込むことができる。よって、ブロック重ね合わせ式パリティ検査構成要素３４４は、次式に従って図解５００に示すようにサイズＬＸ×ＬＹのパリティマップＰを形成することができる。
【数１】
2010532595.tif 000003
【００３４】
同様に、透かし入り画像３３０からのロゴ３１０の抽出では、透かし入れに使用されたのと同じシードＫを有する擬似乱数発生器によってマスタマップを構築することができ、パリティマップもやはり式（１）に基づいて形成することができる。攻撃を受けなければ、抽出時に生成されるパリティマップは、透かし入れ構成要素３４０において入力された透かしと同じに見えるはずであることが理解できる。
【００３５】
一例では、反転マップ形成構成要素３４６は、パリティマップＰ及びロゴＬ３１０に基づき、以下のように動作することができる。画像３２０にロゴ３１０を埋め込むには、ＰｉｊがＬｉｊと異なる位置において、パリティマップＰがロゴＬとマッチするようにＰｉｊの値を反転させる必要があることが理解できる。よって、ＰとＬとの間で画素別の排他的論理和（ＸＯＲ）演算を行って比較することにより反転マップＴを形成することができる。これらの演算は次式で表すことができる。
【数２】
2010532595.tif 000004
【００３６】
あるｉ及びｊについてＰｉｊとＬｉｊとが同じである場合、Ｔｉｊは０になり、反転は不要である。他方、ＰｉｊとＬｉｊとが異なる場合、Ｔｉｊは「１」になる。このため、ペア反転構成要素３５０は、Ｍ（２ｉ）（２ｊ）を中心とするブロック内の画素の１つを、ＰｉｊとＬｉｊが等しくなるように反転させることができる。
【００３７】
１つの非限定的な具体例では、いくつかのマスタ画素が複数のブロックによって共有されるように、マスタマップＭ内のすべてのブロックを、それぞれの近隣ブロックと重なり合うように構成することができる。したがって、１≦ｉ≦ＬＸかつ１≦ｊ≦ＬＹの場合、所与の位置においてマスタ画素を共有するブロックの数は以下の表１で与えられる。
【００３８】
【表１】
2010532595.tif 000005
【００３９】
一態様によれば、透かし入れ構成要素３４０によって実行されるＢＯＰＣアルゴリズムは、反転させるべき画素を選択する際に表１で示す画素共有特性を利用することができ、それによって視覚品質の改善が実現される。表１からわかるように、ある画像に対応するマスタマップＭ内の単一の反転は、パリティマップＰ内の１、２、又は４情報ビットの反転を生じさせることができる。よって、ロゴ３１０を埋め込むのに必要な反転の量を最小限に抑えるために、バブル形成構成要素３４８を以下のように利用することができる。
【００４０】
一例では、バブル形成構成要素３４８は、反転マップＴ内の類似の値のグループ、すなわち「バブル」を形成することができる。バブル形成構成要素３４８が利用することのできるバブル配置の例を、図７の図解６００に示す。最初に、「１」の値を有する反転マップＴ内のあらゆる位置を、サイズ１×１の基本バブルとして初期設定することができる。この操作に続いて、近隣のバブルを組み合わせて個々の複合バブルを形成することができる。これらの複合バブルの許容される配置の例を図解６００に示す。一態様によれば、バブル形成構成要素３４８は、最小限の量のバブルを使用して反転マップＴ内のすべての「１」の値を囲い込むことを目的として動作することができる。一例では、Ｔの各要素を、それらの要素がそれぞれバブルに囲い込まれる際に、それらの要素が囲い込まれているバブルの種類に対応するグループ番号を反映するように更新することができる。このプロセスの例を図８の図解７００に示す。
【００４１】
別の例では、バブル形成構成要素３４８は、２パス法を利用して、以下のように、低い計算量で少数のバブルを実現することができる。第１のパスでは、反転マップＴをラスタ走査順に走査することができる。このパスでは、図解６００に示すグループ４（近隣の「１」の値の２×２グループなど）に属するバブルをすべて値「４」でマークすることができる。第２のパスでは、次いで、反転マップＴを再度ラスタ走査順に走査することができる。要素Ｔｉｊが「１」の値を有し、図解６００に示すグループ２又はグループ３のバブルにグループ化し得る場合、Ｔｉｊから縦下方向に連続する「１」の値とＴｉｊから横右方向に連続する「１」の値との数をチェックすることができる。一例では、縦方向の連続が偶数であり、横方向の連続が奇数である場合、Ｔｉｊはグループ２のバブルにグループ化することができる。そうではない場合には、グループ３のバブルを使用することができる。
【００４２】
予期される１埋め込みビット当たりのバブルの数は、埋め込むべきロゴ３１０のサイズに関連することを理解すべきである。さらに、予期されるバブルの数は、例えば、２つの条件の下で低減され得ることも理解できる。第１に、予期されるバブルの数は、ロゴ３１０を埋め込むべき画像３２０の寸法が１つ又は複数の方向に増大する場合に低減され得る。この条件は、反転マップＴ内に存在する要素の数が増大するにつれて、小さいバブルが組み合わさってより大きいバブルを形成することになる可能性がより高まることによるものである。第２に、予期されるバブルの数は、所与の透かしペイロードについて、画像３２０の寸法の差が増大する場合に低減され得る。この条件が当てはまるのは、画像寸法間の差が大きいと、より多くの内部エッジがもたらされるためにバブルの組み合わせに有利に働くことによるものである。一態様によれば、各バブルは、ホスト画像３２０におけるペア反転を表わし、これは、前述のように、透かし入り画像Ｗ３３０の視覚品質の低下をもたらし得る。例えば、従来のＤＨＳＰＴアルゴリズムなどでは、予期される１埋め込みビット当たりに必要な反転操作の数は０．５である。しかし、ブロックパリティ及びバブル形成を利用することにより、ＢＯＰＣアルゴリズムは、１２８×１２８ロゴでの予期される１埋め込みビット当たりの反転操作（バブルなど）の数を０．２６まで低減することができる。
【００４３】
バブル形成構成要素３４８によるバブル形成の後、ペア反転構成要素３５０がスマートペア反転を実行して、以下のように透かし入れプロセスを完了させることができる。バブル形成プロセスの後、バブル形成プロセスの後、反転マップＴ内のバブルの数は、対応するマスタマップＭにおいて必要とされる画素反転操作の数を表わすことが理解できる。一例では、Ｔｉｊは、反転マップＴにおけるバブルのラスタ走査順で第１の要素を表わすことができる。Ｔｉｊに基づき、ペア反転構成要素３５０は、以下の表２に示すように、Ｔｉｊが属するバブルグループに基づいてマスタ画素を選択することができる。
【００４４】
【表２】
2010532595.tif 000006
【００４５】
反転操作の例を図９の図解８００で示す。図解８００で示されるように、反転させるべきホスト画像３２０内のすべてのマスタ画素位置を見つけた後で、ホスト画像３２０上でスマートペア反転を行うことができる。一例では、ペア反転構成要素３５０によって行われる反転は、反転されるマスタ画素のスレーブ画素グループにおいて相補的反転の相手方が現れなければならないという制約条件を受ける。
【００４６】
次に図１０を参照すると、本明細書で説明する様々な態様による、画像９２０に２値ロゴ９１０を埋め込む技法の例を実施するシステム９００のブロック図が示されている。一例では、透かし入れ構成要素９４０が２値ロゴ９１０を原又はホスト画像９２０に埋め込んで透かし入り中間調画像９３０を形成することができる。一態様によれば、透かし入れ構成要素９４０は、下位構成要素９４２〜９５２を利用して、原画像９２０にロゴ９１０を埋め込むためのＣＰＰＣアルゴリズムを実施することができる。
【００４７】
一態様によれば、透かし入れ構成要素９４０は、ＣＰＰＣアルゴリズムを利用して、透かし挿入プロセスの間に変更する必要のある原画像９２０内の位置の総数を低減することにより、透かし入り画像９３０の視覚品質を改善することができる。一例では、ＣＰＰＣアルゴリズムを従来のデータ隠蔽及び／又は透かし入れアルゴリズムと組み合わせて使用して、ディジタル画像９２０にロゴ９１０を埋め込むことができる。より詳細には、ＣＰＰＣアルゴリズムを利用してそのような従来の技法を改善することができ、それによって結果として生じる透かし入り画像９３０の視覚品質が改善される。
【００４８】
透かし入れ構成要素９４０は、従来からのデータ隠蔽及び／又は透かし入れの技法の機能を、そのような技法の様々な要素の機能を採り入れ、追加要素を適用することによって拡張して、それらの性能を改善することができる。非限定的な具体例として、透かし入れ構成要素９４０は、従来の透かし入れアルゴリズムに一般的に見られる３つのステップを利用することができる。第１に、透かし入れ構成要素９４０は、埋め込み可能位置探索構成要素９４２を含むことができ、この要素は、埋め込みプロセスに適するホスト画像９２０内の位置を求めて目標ドメインのホスト画像９２０において探索を行うことができる。本明細書で使用する場合、これらの位置を単に「埋め込み可能位置」をいう。第２に、次いで、透かし入れ構成要素９４０は、埋め込み可能位置の中間調値をグループに分類することができる。例えば、「０」という中間調値を有する位置を第１のグループに分類することができ、「１」という中間調値を有する位置を第２のグループに分類することができる。第３に、比較構成要素９４８及び／又は透かし挿入構成要素９５２を利用して、原画像９２０内の識別された埋め込み可能位置に、ロゴ９１０内の対応する情報ビットと同じ値を含めさせることができる。
【００４９】
一態様によれば、透かし入れ構成要素９４０は、３つの追加下位構成要素を用いることによって、ＣＰＰＣアルゴリズムを利用してそのような従来からの技法の機能を拡張することができる。第１に、ホスト画像９２０内で利用できるすべての埋め込み可能位置を探索した後で、シャンパンピラミッド形成構成要素９４４を利用することができる。シャンパンピラミッド形成に続き、パリティ計算構成要素９４６を使用して、ロゴ９１０のサイズと同じサイズを有するホスト画像９２０内の埋め込み可能位置に対応する情報ビットの配列を識別することができる。識別された配列をロゴと比較した後、風味付け最適化構成要素９５０を利用して、識別された情報ビットの配列をロゴ９１０とマッチさせるために反転させなければならない位置の最小限の数を見つけることができる。次いで、風味付け最適化構成要素９５０によってマークされた位置に対し、透かし挿入構成要素９５２により透かし挿入処理を行うことができる。次に、シャンパンピラミッド形成構成要素９４４、パリティ計算構成要素９４６、及び風味付け最適化構成要素９５０の動作をさらに詳細に説明する。
【００５０】
別の態様によれば、透かし入れ構成要素９４０が使用することのできるシャンパンピラミッド式パリティ検査アルゴリズムの名前は、このアルゴリズムがシャンパンピラミッドにおいて観測することのできる様々な特性を活用することによるものである。例えば、１から１５まで番号をふった１５個のワイングラスによって構築された２次元５層シャンパンピラミッド１０００を図１１で示す。シャンパンがピラミッド１０００の最高位のグラスに注がれた場合、シャンパンは、溢れ出てピラミッド１０００を流れ落ちる際に、最高位のグラスの下にあるすべてのグラスを満たすことが理解できる。同様に、より複雑なシナリオでは、ピラミッド１０００の最高位のところのグラス１には風味なしのシャンパンを注ぐことができ、グラス４にはリンゴ風味のシャンパンを注ぐことができる。注入が続く間に時間が経過するにつれて、ピラミッド１０００内のすべてのグラスがシャンパンで満たされることが理解できる。しかし、ピラミッド１０００の最下位層のところのグラスを考えると、グラス１１からグラス１３までは、そのときにリンゴ風味のシャンパンを含むはずであり、グラス１４及び１５はそうならないはずであることが理解できる。
【００５１】
以上に基づき、ピラミッド１０００の各層に最下位から番号をふることができる。図１１に示すように、グラス１１から１５は第１層にあり、グラス１は第５層にある。よって、Ｌ層のピラミッド１０００について、ピラミッド１０００の最下位層にあるＮ個の連続したグラスは、シャンパンがピラミッド１０００の最下位層に流れ込むまでピラミッド１０００の第Ｎ層のグラスに注がれた場合、上記第Ｎ層のグラスと同じ風味のシャンパンを含むことになる。このため、最下位層にあるＮ個の連続したグラスに共通の風味を加えようとする場合、所望の風味を、最下位層のＮ個のグラスすべてに加えるのではなく、ピラミッド１０００の第Ｎ層にある１個のグラスに注げばよいことが理解できる。
【００５２】
同様に、シャンパンピラミッド形成構成要素９４４は、埋め込み可能位置を前述の特性を示す構造に配置することができる。一例では、シャンパンピラミッド形成構成要素９４４は、埋め込み可能位置探索構成要素９４２によって識別された埋め込み可能位置の集合、及びこれらの位置に対応する２進値を入力として取ることができる。次いで、これらの位置をそれぞれ、事前に定義された走査順を有するピラミッド構造内のワイングラスとして扱うことができる。このような構造の例を、図１２の図解１１００で示す。図解１１００にはさらに、シャンパンピラミッド構造によって保持され得る情報ビットの数が、ピラミッドの最下位層にある要素の数に等しいことも示されている。よって、画像９２０内の埋め込み可能位置の数（Ｍなど）は限られており、埋め込むべきロゴ９１０のサイズ（Ｌなど）は固定されているため、画像９２０内の埋め込み可能位置の数は、単一のＬ層のシャンパンピラミッドを構築するのに十分ではない可能性がある。そのような場合には、代わりに、複数のＮ層のピラミッドを構築することができる。一例では、次式によってΝを制約することができる。
【数３】
2010532595.tif 000007
【００５３】
一態様によれば、ＣＰＰＣを使用して画像９２０に埋め込まれる隠蔽情報は、シャンパンピラミッド形成構成要素９４４によって構築される（１つ又は複数の）ピラミッド構造の最下位層に依存するものとすることができる。図解１０００を参照して前述したように、構造を流れるデータは、シャンパンピラミッドの最上位から、最終的にピラミッドの最下位層にあるすべてのグラスが満たされるように注がれる液体として視覚化することができる。よって、パリティ計算構成要素９４６は、（１つ又は複数の）ピラミッド構造の処理を、ワイングラスの関心領域ｎ、すなわちＲＯＩ（ｎ）を、ピラミッドの最上位のグラスからグラスｎまでの可能なパスに属するグラスの集合として定義することから開始することができる。よって、ピラミッド１０００では、ＲＯＩ（１１）＝｛１，２，４，７，１１｝であり、ＲＯＩ（１３）＝｛１，２，３，４，５，６，８，９，１３｝である。
【００５４】
上述のように、ピラミッド１０００内の各ワイングラスは、画像９２０内の埋め込み可能位置及びその位置に対応する２進値を表わすことができる。よって、ピラミッド１０００内の各ワイングラスは、「０」又は「１」の値を含むことができる。これに基づき、パリティ計算構成要素９４６は、ピラミッドの最下位層にある各グラスの関心領域内の「１」を含むグラスの数を数えることができる。一例では、そのようなグラスの数があるグラスについて偶数である場合、そのグラスのパリティは「０」に設定される。同様に、そのようなグラスの数が所与のグラスについて奇数である場合、そのグラスのパリティは、そうではなく「１」に設定することができる。この計算の後、埋め込むべきロゴ９１０と同じサイズを有する情報配列（ＩＡ）を形成することができる。図１２の図解１１００に、パリティ計算の例を示す。
【００５５】
一例では、ピラミッド構造の最下位層にある各ノードごとに、パリティ計算構成要素９４６は、ＲＯＩを定義し、次いで、定義された領域内の「１」の値を含むノードの数を数えることができる。非限定的な具体例として、そのような操作の計算量は、ＲＯＩの様々な特性を使用して低減することができる。まず、ピラミッド構造の最下位層にある各ノードｘごとに、パリティ計算構成要素は、図１３の図解１２００に示すように、ｘの「左ソース」ＬＳ（ｘ）、ｘの「右ソース」ＲＳ（ｘ）、及びｘの「上ソース」ＵＳ（ｘ）を定義することができる。ＬＳ（ｘ）、ＲＳ（ｘ）、及び／又はＵＳ（ｘ）が存在しない場合もあり得ることを理解すべきである。
【００５６】
存在しないノードのＲＯＩは空集合として表わすことができる。そうでない場合、ノードｘについて、ＲＯＩを以下のように計算することができる。
ＲＯＩ（ＵＳ（ｘ））＝ＲＯＩ（ＬＳ（ｘ））∩ＲＯＩ（ＲＳ（ｘ））    （４）
ＲＯＩ（ｘ）＝ＲＯＩ（ＬＳ（ｘ））∪ＲＯＩ（ＲＳ（ｘ））＋｛ｘ｝
＝ＲＯＩ（ＬＳ（ｘ））＋ＲＯＩ（ＲＳ（ｘ））−ＲＯＩ（ＵＳ（ｘ））＋｛ｘ｝    （５）
式（４）〜（５）で計算されるノードｘのＲＯＩに基づき、ノードｘのパリティを以下のように計算することができる。
【数４】
2010532595.tif 000008
【００５７】
よって、式（６）から、パリティ計算構成要素９４６は、スマートパリティ計算法を次のように利用することができる。パリティ計算構成要素９４６は、ピラミッドの最上位から開始して、図解１０００に示すように、グラス番号の昇順に各ノードを処理することができる。所与のノードについて、ＵＳ（ｘ）が「０」である場合、それ以上の操作は不要である。そうでない場合には、ＬＳ（ｘ）、ＲＳ（ｘ）、及びｘが含む値を、図１４の図解１３１０及び図解１３２０で示すように反転させることができる。
【００５８】
パリティ計算構成要素９４６においてＩＡが生成されると、そのＩＡを、比較構成要素９４８において排他的論理和（ＸＯＲ）演算子を使用して、埋め込まれるロゴ９１０に対応する配列で処理することができる。結果として生じる配列に出現する「１」の値ごとに、ピラミッド構造の最下位層にある対応する位置を、図１５の図解１４１０に示すように、「風味を加えるべき（Ｔｏ  Ｂｅ  Ｆｌａｖｏｒｅｄ）」（ＴＢＦ）とマークすることができる。理論的には、ピラミッドの最下位層にあるノードは、０．５の確率でＴＢＦとマークされることになることが理解できる。次いで、風味付け最適化構成要素９５０が、ピラミッドの最下位層にあるＮ個の連続したワイングラスに風味を加えることは第Ｎ層にある１つのワイングラスに風味を加えることと等価であるという知見を用いて、反転最適化を実行することができる。よって、ピラミッド構造内のＮ個の連続したノードがＴＢＦとマークされる場合、風味付け最適化は、Ｎ個の位置すべての反転を求めるのではなく、ホスト画像９２０内のただ１つの位置を反転させるよう指定することができる。
【００５９】
透かし挿入及び抽出と関連させて使用される風味付け最適化の例を、図１５の図解１４１０及び１４２０で示す。図１５に示すように、図１２に示すピラミッド構造１１００及び５ビットのロゴ｛１１０００｝が与えられた場合、ＩＡの反転を行った結果として｛０１１１０｝という配列を得ることができる。図解１４１０で示すように、次いで、最下位層にある第２、第３、及び第４のノードをＴＢＦとマークすることができる。しかし、透かし入れ構成要素９４０は、３つのグラスすべてを反転させるのではなく、第３層にある１つのグラスだけを反転させることによってロゴを完全に埋め込むことができる。
【００６０】
次に図１６を参照すると、本明細書で説明する様々な態様による画像１５２０の透かし入れを円滑に行わせるシステム１５００が示されている。一例では、透かし入れ構成要素１５４０が原中間調画像１５２０に２値ロゴ１５１０を埋め込んで透かし入り中間調画像１５３０を形成することができる。一態様によれば、透かし入れ構成要素１５４０は、下位構成要素１５４２〜１５５４を利用することによって、原画像１５２０にロゴ１５１０を埋め込むためのＴＢＰＣアルゴリズムを実施することができる。
【００６１】
一態様によれば、透かし入れ構成要素１５４０はＴＢＰＣアルゴリズムを、既存のデータ隠蔽の技法のためのプラグインプロセスとして利用することができる。よって、例えば、透かし入れ構成要素１５４０は、従来の透かし入れアルゴリズムにおいて一般的に見られる様々な処置を行うことができる。例えば、透かし入れ構成要素１５４０は、埋め込み可能位置探索構成要素１５４２を利用して、ホスト画像１５２０内の埋め込み可能位置を探索し、比較構成要素１５４８を利用して埋め込み可能位置に含まれる２進値を対応する埋め込むべきデータと比較し、変更位置決定構成要素１５５２を利用して、どの埋め込み可能位置が埋め込むべきデータを保持するために変更を必要とするか決定することができる。次いで、変更構成要素１５５４により比較に基づいて変更を行うことができる。原画像１５２０が変更されるときには、透かし入り画像１５３０にひずみが導入されることが理解できる。さらに、事前情報が知られていないため、各埋め込み可能位置に含まれる値を、埋め込むべきデータに対して独立のものとみなし得ることも理解できる。よって、１つ１つの埋め込むべきビットについて、原画像が変更を必要とする確率は０．５である。大部分の従来のデータ隠蔽アルゴリズムはこれらの変更によって生じるひずみを最小限に抑えようとする。これに対して、透かし入れ構成要素１５４０が使用できるＴＢＰＣアルゴリズムは、原画像１５２０を変更する確率を低減しようとする。
【００６２】
一態様によれば、透かし入れ構成要素１５４０は、ＴＢＰＣアルゴリズムを利用して、透かし入り画像１５３０の視覚品質の改善を実現することができる。一例では、透かし入れ構成要素１５４０は、木構造形成構成要素１５４４、パリティ計算構成要素１５４６、及び／又は噴水調査構成要素１５５０を用いて、ＴＢＰＣアルゴリズムによる従来のデータ隠蔽方式の機能を拡張することができる。一般に、ＴＢＰＣアルゴリズムは、透かし入れ構成要素１５４０に、Ｎ進木内の先祖と子孫との間の関係を利用して透かし入り画像１５３０の視覚品質を改善させることができる。以下の考察では、木構造形成構成要素１５４４、パリティ計算構成要素１５４６、及び噴水調査構成要素１５５０の動作例をさらに詳細に説明する。本明細書では、埋め込むべきロゴのサイズをＬで表す。
【００６３】
例えば、木構造形成構成要素１５４４は以下のように動作し得る。従来のデータ隠蔽アルゴリズムでは、画像の埋め込み可能位置を見つけた後で、これらの位置の値を「０」又は「１」に分類することができる。分類の直後に、これらの値は対応するロゴビットと比較される。個々の値が埋め込むべきビットと同じである場合には、それ以上の操作は行われない。そうでない場合、値を反転させるために１つ又は複数のひずみ作成プロセスが実行される。これに対して、木構造形成構成要素１５４４は、本明細書で「マスタツリー」と呼ぶＮ進の完全木に、埋め込み可能位置探索構成要素１５４２によって探索された埋め込み可能位置の値を取り込むことができる。マスタツリーはＮ進完全木であるため、葉ノードを除くマスタツリーのあらゆるノードをＮ個の子ノードを持つように構成することができる。一例では、１つの葉ノードを利用して１情報ビットを保持することができる。したがって、Ｌビットのロゴ１５１０を埋め込むには、Ｌ個の葉をもつマスタツリーが必要とされ得ることが理解できる。図１７に、Ｎ＝２、Ｌ＝１６の場合に木構造形成構成要素１５４４によって作成され得るマスタツリー１６００の例を示す。
【００６４】
木構造形成構成要素１５４４によって構築されたマスタツリーに基づき、パリティ計算構成要素１５４６を利用して、マスタツリー内の各葉ノードで表される情報ビットを決定することができる。一例では、これは、ある葉ノードについて、その葉ノードからマスタツリーの根ノードまで進むことにより達成することができる。「１」の値の出現数が奇数である場合、その葉ノードの情報ビットを「１」とみなすことができる。そうでない場合には、その情報ビットを「０」とみなすことができる。これらの計算を図１７のマスタツリー１６００についてさらに示す。
【００６５】
次に、ロゴ１５１０の個々のビットとマスタツリーに含まれる情報との間でビット別の排他的論理和（ＸＯＲ）演算を行うことにより、比較構成要素１５４８は反転配列を獲得することができる。この比較の例として、例示のマスタツリー１６００では、獲得される情報配列は｛１１１０１１０１０１１１１０００｝であることがわかる。ロゴ配列が｛００１０００１００１０１１１１０｝であると仮定すると、比較構成要素１５４８によって獲得される結果の反転配列は、｛１１００１１１１００１００１１０｝になる。この比較を、図１８に図解１７００で示す。
【００６６】
一態様によれば、反転配列内の個々の「１」の値は、対応する原画像１５２０の埋め込み可能位置が反転を必要とすることを表わすことができる。しかし、原画像１５２０内のどんな変更によっても視覚アーチファクトが導入されることが理解できる。したがって、透かし入り画像１５３０の視覚品質を改善するために、ＴＢＰＣを利用して反転配列内の「１」値の数を最小限にすることができる。図１７に戻って、マスタツリー１６００をよく調べると、「１」から「０」であれ、「０」から「１」であれ、あらゆるノードにおける１回の変更が、変更されたノードの子孫すべてのパリティの変更を生じ得ることがわかる。よって、マスタツリー１６００内のＮ個の兄弟ノードの値を変更するのではなく、それらに共通の親ノード１つを変更するだけで同じ効果を得ることができる。
【００６７】
前述の知見を活用するために、噴水調査構成要素１５５０は、マスタツリーと同じサイズの反転木を構築することができる。一例では、反転木の各葉ノードに、反転配列の各要素を、それらの要素が反転配列に出現する順に取り込むことができる。木構造内の残りのノードには、最初に、任意の適切な値を使用して要素を取り込むことができる。一例では、次いで噴水調査構成要素は、反転木の根において以下のように分析を開始することができる。所与のノードについて、その所与のノードのＮ個の子ノードすべてが値「１」を含む場合、それらの子ノードは値「０」で更新され、調査対象のノードを「１」にリセットすることができる。そうでない場合には、処理対象のノードを「０」にリセットすることができる。前述の例示の反転配列のための反転木生成及び噴水調査プロセスの例を図解１７００に示す。
【００６８】
一例では、原画像１５２０にロゴ１５１０を埋め込むために、次いで、個々の「１」の値を有する反転木内の位置に対応するマスタツリー内の埋め込み可能位置を反転させることができる。このようにして生成される透かし入り画像１５３０を復号するには、その場合、同じ順序の埋め込み可能位置を探索し、それらを使用してマスタツリーを構築することができる。マスタツリーのパリティ計算の後、獲得される情報配列は、埋め込まれるロゴ１５１０に対応するロゴ配列とマッチするはずである。復号プロセスの例を図１９の図解１８００で示す。
【００６９】
一態様によれば、透かし入れ構成要素１５４０の達成可能な最大のペイロードは以下のように見つけることができる。最初に、原画像１５２０内の埋め込み可能位置の数は限られているため、木構造形成プロセスにおいて形成することのできるマスタツリーのサイズも限られることが理解できる。さらに、前述のように、マスタツリーは、Ｌ個のロゴビットを表わすのにＬ個の葉ノードを持つ必要がある。よって、Ｌ個の葉ノードを持つＮ進完全木を形成するために、必要なノードの総数、ｎＮｏｄｅｓは、次式によって見つけることができる。
【数５】
2010532595.tif 000009
【００７０】
式（８）から、Ｎが増加するにつれて、マスタツリーで必要とされるノードの数が減少することがわかる。よって、埋め込み可能位置の数は限られているため、透かし入れ構成要素１５４０によって埋め込むことのできるペイロードはＮが増加するにつれて増加する。固定のロゴサイズＬ及び利用可能な埋め込み可能位置の数Ｍについて、使用し得る最小のＮは以下のように見つけることができる。
【数６】
2010532595.tif 000010
【００７１】
別の態様によれば、パリティ計算構成要素１５４６は、低複雑度パリティ計算の技法を使用して以下のように動作することができる。まず、ｐａｒｉｔｙ（ｘ）を、ノードｘからマスタツリーの根ノードまでのパス内の「１」の出現数のパリティとして定義することができる。ｐａｒｉｔｙ（ｘ）は、ビットごとの加算を使用して、ｐａｒｉｔｙ（ｐａｒｅｎｔ（ｘ））の値にノードｘの値を足したものに等しいことがわかる。よって、パリティ計算構成要素１５４６は、木構造の根から開始してマスタツリーを進み、処理対象の各ノードｘごとに、その子ノードｙのパリティを、ノードｘのパリティとノードｙの値を加算することによって更新することができる。
【００７２】
次に図２０〜図２３を参照すると、本明細書で説明する様々な態様によって実施され得る方法が示されている。説明を簡単にするために、各方法を一連のブロックとして説明し、図示するが、特許請求する主題は、各ブロックの順序によって制限されるものではなく、ブロックによっては、特許請求する主題によれば、本明細書で図示し、説明する順序と異なる順序で、かつ／又は他のブロックと同時に行われてもよいことを理解し、認めるべきである。さらに、特許請求する主題による方法を実施するのに必ずしも図示のブロックすべてが必要とされるとは限らない。
【００７３】
さらに、特許請求する主題は、１つ又は複数の構成要素によって実行される、プログラムモジュールといったコンピュータ実行可能命令の一般的状況において説明され得る。一般に、プログラムモジュールには、個々のタスクを実行し、又は個々の抽象データ型を実施する、ルーチン、プログラム、オブジェクト、データ構造などが含まれる。典型的には、プログラムモジュールの機能は、様々な実施形態において求めに応じて組み合わされ、又は分散され得る。さらに、当然ながら、開示の前述のシステム及び後述する方法の様々な部分は、人口知能又は知識又は規則に基づく構成要素、下位構成要素、プロセス、手段、方法、又は機構（サポート・ベクタ・マシン、ニューラルネットワーク、エキスパートシステム、ベイジアン信念ネットワーク、ファジィ論理、データ融合エンジン、分類器など）を含み、又はそれらから構成することができる。そのような構成要素は、特に、システム及び方法の各部分を、より適応性があり、しかも効率的で、インテリジェントなものにするために、それらの構成要素が実行するいくつかの機構又はプロセスを自動化することができる。
【００７４】
図２０を参照すると、画像に透かし情報を埋め込む方法２０００が示されている。２００２において、ロゴ及びロゴを埋め込むべき画像が識別される。２００４において、２００２で識別された画像内の候補位置が（透かし入れ構成要素２１０のところの埋め込み候補選択構成要素２２０などによって）探索される。２００６において、（パリティ検査構成要素２３０などによって）２００４で探索された候補位置の重なり合うグループの集合が、個々のグループが２００２で識別されたロゴ内の個々の情報ビットに対応するように形成される。２００８において、（データ隠蔽構成要素２４０などによって）ロゴが、少なくとも一部は、２００６で形成された個々の候補位置のグループがロゴ内の対応する情報ビットの値とマッチするように２００４で探索された画像内の候補位置を反転させることによって画像に埋め込まれる。
【００７５】
次に図２１を参照すると、中間調画像（原画像３２０など）に２値透かし（ロゴ３１０など）を埋め込む方法２１００が示されている。一態様によれば、方法２１００を利用して、透かし入り画像（透かし入り画像３３０など）を生成するためにブロック重ね合わせ式パリティ検査（ＢＯＰＣ）アルゴリズムを実施することができる。２１０２において、中間調画像及び画像に埋め込むべき２値透かしが識別される。２１０４において、２１０２で識別された画像内の画素が、（透かし入れ構成要素３４０のところのマスタ／スレーブ画素選択構成要素３４２などによって）マスタ画素とスレーブ画素とに分けられる。２１０６において、２１０６において決定されたマスタ画素が（ブロック重ね合わせ式パリティ検査構成要素３４４などによって）マップされ、隣接してマップされたマスタ画素が重なり合うブロックにグループ化される。２１０８において、２１０６で作成された個々のマスタ画素のブロックのパリティを表わすパリティマップが構築される。
【００７６】
２１１０において、反転マップが、（反転マップ形成構成要素３４６などによって）２１０８で構築されたパリティマップ内の個々の位置の値と、２１０２で識別された２値透かし内の対応するビットとの比較から得られた結果を使用して生成される。２１１２において、２１１０で決定されたパリティマップと透かしの間の差分に対応する反転マップ内の位置が、（バブル形成構成要素３４８などによって）１つ又は複数の所定のサイズのバブルにグループ化される。２１１４において、２１１０で生成された反転マップ内の２１１２で作成された各バブルに対応するマスタ画素及び近隣の画素を（ペア反転構成要素３５０などによって）反転させることにより、透かしが画像に埋め込まれる。
【００７７】
図２２に、中間調画像（原画像９２０など）に２値ロゴ（ロゴ９１０など）を埋め込む方法２２００を示す。一態様によれば、方法２２００を利用して、透かし入り画像（透かし入り画像９３０など）を生成するためにシャンパンピラミッド式パリティ検査（ＣＰＰＣ）アルゴリズムを実施することができる。２２０２において、中間調画像及び画像に埋め込むべき２値ロゴが識別される。２２０４において、データを埋め込むための２２０２で識別された画像内の候補画素が（透かし入れ構成要素９４０のところの埋め込み可能位置探索構成要素９４２などによって）識別される。
【００７８】
２２０６において、２２０４で識別された候補画素に対応するノードを持つ２値ピラミッド構造が、（シャンパンピラミッド形成構成要素９４４などによって）ピラミッド構造の最下位層にあるノードの数が２２０２で識別された２値ロゴ内のビットの数と等しくなるように構築される。２２０８において、２２０６で構築されたピラミッドの最下位層のところの各ノードごとに、個々のノードと、個々のノードがそのノードの直接又は間接の後続ノードであるピラミッド内の他のすべてのノードとが組み合わさった集合のパリティが（パリティ計算構成要素９４６などによって）計算される。
【００７９】
２２１０において、２２０８で計算されたピラミッドの最下位層のところの個々のノードのパリティが、（比較構成要素９４８などによって）対応するロゴのビットと比較される。２２１２において、２２１０の比較で対応するロゴビットと異なるパリティ値を持つことを示した連続するノードのグループが（風味付け最適化構成要素９５０などによって）識別される。２２１４において、少なくとも一部は、（透かし挿入構成要素９５２等を使用して）２２１２で識別されたグループの個々の最低位の共通先行ノードに対応する画素を反転させることによって、ロゴが画像に埋め込まれる。
【００８０】
図２３を参照すると、中間調画像（原画像１５２０など）に２値透かし（ロゴ１５１０など）を埋め込む別の方法２３００が示されている。一態様によれば、方法２３００を利用して、透かし入り画像（透かし入り画像１５３０など）を生成するために木構造に基づくパリティ検査（ＴＢＰＣ）アルゴリズムを実施することができる。２３０２において、中間調画像及び画像に埋め込むべき２値透かしが識別される。２３０４において、２３０２で識別された画像内の埋め込み可能位置が（透かし入れ構成要素１５００のところの埋め込み可能位置探索構成要素１５４２などによって）探索される。
【００８１】
２３０６において、１つ又は複数のＮ進マスタツリーが、（木構造形成構成要素１５４４などによって）１つ又は複数の木構造内の葉ノードの数が２３０２で識別された透かし内のビットの数と等しくなるように、２３０４で探索された埋め込み可能位置を使用して構築される。２３０８において、２３０６で構築されたマスタツリー内の各葉ノードごとに、（パリティ計算構成要素１５４６などによって）葉ノードから、その葉ノードが属するマスタツリーの根ノードまでのパス内のノードのパリティが計算される。２３１０において、反転配列が、（比較構成要素１５４８などによって）２３０８で計算された個々のパリティ値と２３０２で識別された対応する透かしのビットとの間で排他的論理和演算を行うことによって獲得される。２３１２において、２３０６で構築された１つ又は複数のマスタツリーに対応する１つ又は複数の反転木が、２３１０で獲得された反転配列を葉ノードとして使用して構築される。最後に、２３１４において、少なくとも一部は、すべての葉ノードが反転指示を示す（と、例えば噴水調査構成要素１５５０及び／又は変更位置決定構成要素１５５２によって決定された）２３１２で構築された反転木内の個々の最高位ノードに対応する、２３０４で探索された探索埋め込み可能位置を（変更構成要素１５５４などによって）反転させることによって、画像に透かしが埋め込まれる。
【００８２】
図２４及び以下の考察は、本明細書で説明する様々な態様についての状況をさらに示すために、特許請求する主題の様々な態様が実施され得る適切なコンピュータ環境２４００の簡単な一般的説明を提供するものである。加えて、以上の各特徴は、１つ又は複数のコンピュータ上で実行され得るコンピュータ実行可能命令の一般的状況において説明されているが、これらの特徴は、別のプログラムモジュールと組み合わせて、かつ／又はハードウェアとシソフトウェアの組み合わさったものとして実施することもできることを当業者は理解するであろう。
【００８３】
一般に、プログラムモジュールには、個々のタスクを実行し、又は個々の抽象データ型を実施するルーチン、プログラム、構成要素、データ構造などが含まれる。さらに、特許請求する主題は、それぞれ、１つ又は複数の関連装置に動作可能な状態で結合され得る、シングルプロセッサ又はマルチプロセッサのコンピュータシステム、ミニコンピュータ、メインフレームコンピュータ、ならびにパーソナルコンピュータ、ハンドヘルド式コンピュータ機器、マイクロプロセッサベースの、又はプログラム可能な家電製品などを含む、他のコンピュータシステム構成と共に実施することもできることも当業者は理解するであろう。
【００８４】
また、例示の各態様は、いくつかのタスクが通信ネットワークを介してリンクされた遠隔処理装置によって行われる分散コンピュータ環境においても実施され得る。分散コンピュータ環境では、プログラムモジュールを、ローカルの記憶装置とリモートの記憶装置の両方に位置させることができる。
【００８５】
コンピュータは通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータでアクセスすることができる任意の利用可能な媒体とすることができ、揮発性と不揮発性両方の媒体、取り外し可能と取り外し不能両方の媒体が含まれる。例えば、それだけに限らないが、コンピュータ可読媒体には、コンピュータ記憶媒体と通信媒体が含まれ得る。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュールなどのデータといった情報の記憶のための任意の方法又は技術で実施される、揮発性と不揮発性両方の媒体、取り外し可能と取り外し不能両方の媒体が含まれ得る。コンピュータ記憶媒体には、それだけに限らないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリなどのメモリ技術、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）などの光ディスク記憶、磁気カセット、磁気テープ、磁気ディスク記憶などの磁気記憶装置、又は所望の情報を記憶させるのに使用することができ、コンピュータでアクセスすることのできる他の任意の媒体が含まれる。
【００８６】
通信媒体は通常、コンピュータ可読命令、データ構造、プログラムモジュールなどのデータを、搬送波や他の搬送機構といった変調データ信号として実施し、これには任意の情報送達媒体が含まれる。「変調データ信号」という用語は、その特性の１つ又は複数が、信号において情報を符号化するようなやり方で設定され、又は変更されている信号を意味する。例えば、それだけに限らないが、通信媒体には、有線ネットワークや直接接続といった有線媒体、及び音響、ＲＦ、赤外線、その他の無線媒体といった無線媒体が含まれる。また、上記のいずれかの組み合わさったものも、コンピュータ可読媒体の範囲内に含めるべきである。
【００８７】
再び図２４を参照する。本明細書で説明する様々な態様を実施するための例示的環境２４００は、コンピュータ２４０２を含み、コンピュータ２４０２は、処理装置２４０４、システムメモリ２４０６及びシステムバス２４０８を含む。システムバス２４０８は、それだけに限らないが、システムメモリ２４０６を含む各システム構成要素と、処理装置２４０４とに結合されている。処理装置２４０４は、様々な市販のプロセッサのいずれかとすることができる。また、デュアルマイクロプロセッサ及びその他のマルチプロセッサアーキテクチャが処理装置２４０４として用いられてもよい。
【００８８】
システムバス２４０８は、（メモリコントローラあり又はなしの）メモリバス、周辺バス、及び様々な市販のバスアーキテクチャのいずれかを使用するローカルバスと、さらに相互接続され得る数種類のバス構造のいずれかとすることができる。システムメモリ２４０６は、読取り専用メモリ（ＲＯＭ）２４１０及びランダム・アクセス・メモリ（ＲＡＭ）２４１２を含む。基本入出力システム（ＢＩＯＳ）は、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭといった不揮発性メモリ２４１０に記憶されており、起動時などに、コンピュータ２４０２内の各要素間での情報転送を補助する基本ルーチンを含む。また、ＲＡＭ２４１２は、データをキャッシュに入れるためのスタティックＲＡＭなどの高速ＲＡＭを含むこともできる。
【００８９】
コンピュータ２４０２はさらに、内蔵ハード・ディスク・ドライブ（ＨＤＤ）２４１４（ＥＩＤＥ、ＳＡＴＡなど）、（例えば、取り外し可能ディスケット２４１８との間で読取り、書込みを行うなどための）磁気フロッピィ・ディスク・ドライブ（ＦＤＤ）２４１６、及び（例えば、ＣＤ−ＲＯＭディスク２４２２を読み取ったり、ＤＶＤなど他の大容量光媒体との間で読取り又は書込みを行ったりするための）光ディスクドライブ２４２０を含み、内蔵ハード・ディスク・ドライブ２４１４は、適切なシャーシ（不図示）において外付けとして構成されていてもよい。ハード・ディスク・ドライブ２４１４、磁気ディスクドライブ２４１６、及び光ディスクドライブ２４２０は、それぞれ、ハード・ディスク・ドライブ・インターフェース２４２４、磁気ディスク・ドライブ・インターフェース２４２６、及び光ドライブインターフェース２４２８によってシステムバス２４０８に接続することができる。外付けドライブ実装用のインターフェース２４２４には、ユニバーサル・シリアル・バス（ＵＳＢ）及びＩＥＥＥ１３９４インターフェース技術の少なくとも一方又は両方を含む。他の外部ドライブ接続技術も本開示の企図に含まれる。
【００９０】
各ドライブ及び各ドライブと関連付けられるコンピュータ可読媒体は、データ、データ構造、コンピュータ実行可能命令などの不揮発性記憶を提供する。コンピュータ２４０２では、各ドライブ及び媒体は、適切なディジタル形式での任意のデータの記憶に対応する。以上のコンピュータ可読媒体の説明では、ＨＤＤ、取り外し可能磁気ディスケット、及びＣＤやＤＶＤといった取り外し可能光媒体に言及しているが、例示的動作環境では、ｚｉｐドライブ、磁気カセット、フラッシュ・メモリ・カード、カートリッジなどといった、コンピュータで読取り可能な別の種類の媒体が使用されてもよく、さらに、そのような媒体はいずれも、本明細書で説明する方法を実行するためのコンピュータ実行可能命令を含むことができることを当業者は理解するはずである。
【００９１】
各ドライブ及びＲＡＭ２４１２には、オペレーティングシステム２４３０、１つ又は複数のアプリケーションプログラム２４３２、その他のプログラムモジュール２４３４及びプログラムデータ２４３６を含むいくつかのプログラムモジュールを記憶させることができる。また、オペレーティングシステム、アプリケーション、モジュール、及び／又はデータの全部又は一部をＲＡＭ２４１２にキャッシュすることもできる。特許請求する主題は、様々な市販のオペレーティングシステム又はオペレーティングシステムの組み合わせを用いて実施することができることが理解される。
【００９２】
ユーザは、キーボード２４３８やマウス２４４０などのポインティングデバイスといった１つ又は複数の有線／無線入力装置によってコンピュータ２４０２にコマンド及び情報を入力することができる。他の入力装置（不図示）には、マイクロホン、ＩＲ遠隔制御装置、ジョイスティック、ゲームパッド、スタイラスペン、タッチスクリーンなどが含まれ得る。上記及びその他の装置は、多くの場合、システムバス２４０８に結合された入力装置インターフェース２４４２を介して処理装置２４０４に接続されるが、パラレルポート、シリアルポート、ＩＥＥＥ１３９４ポート、ゲームポート、ＵＳＢポート、ＩＲインターフェースなどといった他のインターフェースによって接続することもできる。
【００９３】
また、システムバス２４０８には、ビデオアダプタ２４４６などのインターフェースを介して、モニタ２４４４又は別種の表示装置も接続される。モニタ２４４４に加えて、コンピュータは通常、スピーカ、プリンタなどといった他の周辺出力装置（不図示）も含む。
【００９４】
コンピュータ２４０２は、リモートコンピュータ２４４８など、１つ又は複数のリモートコンピュータへの有線及び／又は無線通信による論理接続を使用したネットワーク接続環境において動作し得る。リモートコンピュータ２４４８は、ワークステーション、サーバコンピュータ、ルータ、パーソナルコンピュータ、携帯式コンピュータ、マイクロプロセッサベースの娯楽機器、ピアデバイス又はその他一般のネットワークノードとすることができ、典型的には、コンピュータ２４０２に関連して説明した各要素の多く又は全部を含むが、簡単にするために、メモリ／記憶装置２４５０だけが示されている。図示の各論理接続は、ローカル・エリア・ネットワーク（ＬＡＮ）２４５２及び／又は、広域ネットワーク（ＷＡＮ）２４５４などのより大規模なネットワークへの有線／無線接続を含む。そのようなＬＡＮ及びＷＡＮネットワーク環境は、オフィスや企業においてよくみられ、イントラネットなどの企業規模のコンピュータネットワークを円滑化するものであり、これらはすべて、インターネットなどのグローバル通信ネットワークに接続されていてもよい。
【００９５】
ＬＡＮネットワーク環境で使用されるとき、コンピュータ２４０２は、有線及び／又は無線通信ネットワークインターフェース又はアダプタ２４５６を介してローカルネットワーク２４５２に接続される。アダプタ２４５６は、ＬＡＮ２４５２への有線又は無線通信を円滑化することができ、ＬＡＮ２４５２には、無線アダプタ２４５６とやりとりするために配置された無線アクセスポイントを含んでいてもよい。
【００９６】
ＷＡＮネットワーク環境で使用されるとき、コンピュータ２４０２は、モデム２４５８を含むことができ、又はＷＡＮ２４５４上の通信サーバに接続され、又はインターネットによるものなど、ＷＡＮ２４５４を介した通信を確立する他の手段を備える。モデム２４５８は、内蔵又は外付けの、有線又は無線機器とすることができ、シリアル・ポート・インターフェース２４４２を介してシステムバス２４０８に接続される。ネットワーク接続環境では、コンピュータ２４０２との関連で図示されているプログラムモジュール、又はその一部を、リモートメモリ／記憶装置２４５０に記憶させることができる。図示のネットワーク接続は例示であり、コンピュータ間の通信リンクを確立する別の手段を使用することもできることが理解されるであろう。
【００９７】
コンピュータ２４０２は、無線通信において動作するように配置された任意の無線機器又はエンティティ、例えば、プリンタ、スキャナ、デスクトップ及び／又は携帯式コンピュータ、携帯情報端末、通信衛星、無線で検出可能なタグと関連付けられた任意の装置又は位置（キオスク、新聞売店、トイレなど）、電話機などとやりとりするように動作することができる。これには、少なくともＷｉ−Ｆｉ及びブルートゥース（商標）無線技術が含まれる。よって、通信は、従来のネットワークと同様の事前定義構造とすることもでき、少なくとも２台の機器間の単純なアドホック通信とすることもできる。
【００９８】
Ｗｉ−Ｆｉ（Ｗｉｒｅｌｓｓ  Ｆｉｄｅｌｉｔｙ）とは、機器が基地局の範囲内のどこでもデータを送受信することができるようにする、携帯電話で使用されるのと同様の無線技術である。Ｗｉ−ＦｉネットワークはＩＥＥＥ８０２．１１（ａ、ｂ、ｇなど）無線技術を使用して、セキュアで、信頼性が高く、高速の無線接続を提供する。Ｗｉ−Ｆｉネットワークを使用して、コンピュータ同士、コンピュータとインターネット、コンピュータと（ＩＥＥＥ８０２．３又はイーサネット（登録商標）を使用する）有線ネットワークを接続することができる。Ｗｉ−Ｆｉネットワークは、免許不要の２．４ＧＨｚ及び５ＧＨｚの電波帯域において、１３Ｍｂｐｓ（８０２．１１ａ）又は５４Ｍｂｐｓ（８０２．１１ｂ）のデータ転送速度で、又は両帯域を含む（デュアルバンド）製品を用いて動作する。よって、Ｗｉ−Ｆｉ無線技術を使用するネットワークは、１０ＢａｓｅＴ有線イーサネット（登録商標）ネットワークと同様の実際の性能を提供することができる。
【００９９】
次に図２５を参照すると、開示のアーキテクチャを実行するように動作する例示的コンピュータ・コンパイル・システムの概略的ブロック図が示されている。システム２５００は、１つ又は複数のクライアント２５０２を含む。クライアント２５０２は、ハードウェア及び／又はソフトウェア（スレッド、プロセス、コンピュータ機器など）とすることができる。一例では、クライアント２５０２は、本明細書で説明する１つ又は複数の機構を用いることによってクッキー及び／又は関連するコンテキスト情報を収容することができる。
【０１００】
また、システム２５００は、１つ又は複数のサーバ２５０４も含む。サーバ２５０４も、ハードウェア及び／又はソフトウェア（スレッド、プロセス、コンピュータ機器など）とすることができる。一例では、サーバ２５０４は、本明細書で説明する１つ又は複数の機構を用いることによって変換を実行するスレッドを収容することができる。クライアント２５０２とサーバ２５０４の間の可能な通信の１つは、２つ以上のコンピュータプロセスの間で送信されるように適合されたデータパケットの形でのものとすることができる。データパケットは、例えば、クッキー及び／又は関連するコンテキスト情報などを含んでいてもよい。システム２５００は、クライアント２５０２とサーバ２５０４の間の通信を円滑化するのに用いられ得る通信フレームワーク２５０６（例えば、インターネットなどのグローバル通信ネットワーク）を含む。
【０１０１】
通信は、（光ファイバを含む）有線及び／又は無線技術によって円滑に行わせることができる。クライアント２５０２は、クライアント２５０２にとってローカルの情報（クッキー及び／又は関連するコンテキスト情報など）を記憶させるのに用いられ得る１つ又は複数のクライアント・データ・ストア２５０８に動作可能な状態で接続される。同様に、サーバ２５０４も、サーバ２５０４にとってローカルの情報を記憶させるのに用いられ得る１つ又は複数のサーバ・データ・ストア２５１０に動作可能な状態で接続される。
【０１０２】
本明細書では、例を用いて特許請求する主題を説明している。誤解を回避するためにいうと、本明細書で開示する主題は、そのような例によって限定されるものではない。加えて、本明細書で「例示的」として説明するあらゆる態様又は設計は、必ずしも他の態様又は設計に優って好ましく、又は有利であると解釈すべきものであるとは限らず、当業者に知られている等価の例示的構造及び技術を除外するためのものでもない。さらに、誤解を回避するためにいうと、「含む（ｉｎｃｌｕｄｅｓ）」、「有する（ｈａｓ）」、「含む（ｃｏｎｔａｉｎｓ）」という用語、及び他の類似の単語は、詳細な説明及び特許請求の範囲において使用される限りにおいて、どんな追加の、又は別の要素も排除することなく、非排他的移行語としての「備える（ｃｏｍｐｒｉｓｉｎｇ）」という用語と同様に含むことを意図するものである。
【０１０３】
加えて、開示の主題は、本明細書で詳述する各態様を実施するようにコンピュータ又はプロセッサベースの装置を制御するソフトウェア、ファームウェア、ハードウェア、又はこれらの任意の組み合わせを製作するための標準的なプログラミング及び／又はエンジニアリングの技法を使用したシステム、方法、装置、又は製造品として実施することができる。「製造品」、「コンピュータプログラム製品」という用語、又は類似の用語は、本明細書で使用する場合、任意のコンピュータ可読装置、搬送波、又は媒体からアクセスすることのできるコンピュータプログラムを包含するためのものである。例えば、コンピュータ可読媒体には、それだけに限らないが、磁気記憶装置（ハードディスク、フロッピィディスク、磁気ストリップなど）、光ディスク（コンパクトディスク（ＣＤ）、ディジタル多用途ディスク（ＤＶＤ）など）、スマートカード、及びフラッシュメモリ装置（カード、スティックなど）が含まれ得る。加えて、電子メールを送受信する際に、又はインターネットやローカル・エリア・ネットワーク（ＬＡＮ）といったネットワークにアクセスする際に使用されるようなコンピュータ可読電子データを搬送するのに搬送波を用いることができることも知られている。
【０１０４】
前述の各システムは、いくつかの構成要素間の相互作用に関連して説明されている。そのようなシステム及び構成要素は、それらの様々な置換及び組み合わせに従って、それらの構成要素もしくは指定の下位構成要素、指定の構成要素もしくは下位構成要素の一部、及び／又は追加の構成要素を含み得ることが理解できる。また、下位構成要素も、例えば階層構造に従って、親構成要素内に含まれるのではなく、他の構成要素に通信可能な状態で結合された構成要素として実施することができる。加えて、１つ又は複数の構成要素を、集約的機能を提供する単一の構成要素に組み合わせることも、いくつかの別々の下位構成要素に分割することもでき、統合された機能を提供するためにそのような下位構成要素に通信可能な状態で結合するための管理層などの任意の１つ又は複数の中間層を設けることもできることにも留意すべきである。また、本明細書で説明するどんな構成要素も、本明細書で具体的に説明されていないが、当業者に一般に知られている１つ又は複数の別の構成要素と相互に作用することもできる。
【図１】
2010532595.tif 000011
【図２】
2010532595.tif 000012
【図３】
2010532595.tif 000013
【図４】
2010532595.tif 000014
【図５】
2010532595.tif 000015
【図６】
2010532595.tif 000016
【図７】
2010532595.tif 000017
【図８】
2010532595.tif 000018
【図９】
2010532595.tif 000019
【図１０】
2010532595.tif 000020
【図１１】
2010532595.tif 000021
【図１２】
2010532595.tif 000022
【図１３】
2010532595.tif 000023
【図１４】
2010532595.tif 000024
【図１５】
2010532595.tif 000025
【図１６】
2010532595.tif 000026
【図１７】
2010532595.tif 000027
【図１８】
2010532595.tif 000028
【図１９】
2010532595.tif 000029
【図２０】
2010532595.tif 000030
【図２１】
2010532595.tif 000031
【図２２】
2010532595.tif 000032
【図２３】
2010532595.tif 000033
【図２４】
2010532595.tif 000034
【図２５】
2010532595.tif 000035
【国際調査報告】
2010532595.tif 000036