(57)【要約】【課題】電子透かしが入れられたイメージに対して行い得る攻撃のタイプを考慮した電子透かしシステムを提供する。【解決手段】量子化およびデータ埋め込みのシステムを示す。７００は計算システム、７０２はマーキングコンポーネント、７０４は変換コンポーネント、７０６は線形統計ジェネレータ、７０８は格子量子化器、７１０は電子透かしジェネレータ、７１２は電子透かし埋め込み器、７１４は電子透かしレシーバである。電子透かしが入れられるべきイメージに変換が適用され、そのイメージに関連した統計情報が計算される。計算された統計情報は対称格子を使用して量子化され、そしてその格子量子化された統計情報を使用して電子透かしが計算される。次に、電子透かしがイメージに挿入される。【選択図】図７
2011176840.tif 000002
【特許請求の範囲】
【請求項１】
ｎ行とｎ列で構成されるｎ次元の対称格子を生成するステップと、
電子透かしを入れるべきイメージに関連した統計情報を計算し、前記対称格子を用いて前記計算された統計情報を量子化するステップと、
前記量子化された統計情報を使用して、電子透かしを計算するステップと、
前記計算された電子透かしを使用して、関連したイメージにマークを付けるステップと
を備え、
前記イメージに関連した統計情報を計算することは、
前記イメージの１つあるいは複数の領域を選択することと、
前記選択された領域それぞれに関連した重みを生成することと、
変換行列を形成することと、
前記変換行列および前記生成された重みを使用して、前記統計情報を計算することと
含むことを特徴とするコンピュータで実施される方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は量子化(quantization)およびデータ埋込み(data embedding)の方法およびシステムに関する。
【背景技術】
【０００２】
電子透かし(watermarking)はデジタルイメージがその中に埋め込まれたマークを有するようになる処理を意味する。埋め込まれた電子透かし(embedded watermark)はそのイメージの所有者(owner)、そのイメージが配付(distribute)されたエンティティ(entity)、その他同様なものを示すことができる。当然ながら、電子透かしを入れられたイメージは許可されていない方法でそのイメージを盗んだり、あるいはさもなければ使用することを望む無節操な個人による攻撃を受けることがあり得る。これらの個人が電子透かしを攻撃するために使用する多くの異なる方法がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】“Watermarking via Optimization Algorithms for Quantizing Randomized Statistics of image Regions”, M.K.Mihcak,R.Venkatesan、およびM.Kesal, Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, October, 2002, Monticello,IL 10 pages.
【非特許文献２】“Watermarking via Optimization Algorithms for Quantizing Randomized Image Characteristics”, M.K.Mihcak、R.Venkatesan、およびT.Liu, IEEE Transactions on Signal Processing, Special Issue on Secure Media, November, 2003, 30 pages.
【非特許文献３】“Cryptanalysis of Discrete-Sequence Spread Spectrum Watermarks”, M.K.Mihcak,R.Venkatesan,M.Kesal, Proceedings of 5th International Information Hiding Workshop（ＩＨ２００２）, October, 2002,Noordwijkerhout 21 pages.
【非特許文献４】“Attacks on Digital Watermarks: Classification, Estimation-Based Attacks, and Benchmarks”, S.Voloshynovskiy,S.Pereira,T.Pun,J.J.Eggers、およびJ.K.Su, IEEE Communications Magazine, August, 2001, Vol.39,No.8,pp.118-127.
【非特許文献５】”Sphere Packings,Lattices and Groups”,第一章および第六章J.H.ConwayおよびN.J.A.Sloun １９８８年
【発明の概要】
【発明が解決しようとする課題】
【０００４】
したがって、電子透かしが入れられたイメージに対して行い得る攻撃(attack)のタイプを考慮して電子透かしシステム(watermarking system)を設計することが重要になる。
【課題を解決するための手段】
【０００５】
本発明は、改良された電子透かしのシステムおよび方法を提供することに関連した関心から生じている。
【０００６】
本発明は、量子化およびデータ埋め込みのための方法およびシステムに関する。いくつかの実施形態では、電子透かしが入れられるべきイメージに変換(transform)が適用(apply)され、そのイメージに関連した統計情報(statistics)が計算(compute)される。その計算された統計情報(computed statistics)は対称格子(symmetric lattice)を使用(using)して量子化(quantize)され、その格子量子化された統計情報(lattice quantized statistics)を使用して電子透かし(watermark)が計算(compute)される。次に、その電子透かしはイメージ中に挿入(insert)される。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施形態における処理手順を記述したフローチャートである。
【図２】本発明の一実施形態における処理手順を記述したフローチャートである。
【図３】本発明の一実施形態における処理手順を記述したフローチャートである。
【図４】本発明の一実施形態における処理手順を記述したフローチャートである。
【図５】多くの無作為なイメージおよびキーの組み合わせに対するソフトウェア検出器出力に対する動作上の分布を示し、本実施形態の態様を理解するために有効な図である。
【図６】多くの無作為なイメージおよびキーの組み合わせに対する動作上のＲＯＣ曲線を示し、本実施形態の態様を理解するために有効な図である。
【図７】本実施形態を実現するために使用可能な例示的計算システムを示すブロック図である。
【発明を実施するための形態】
【０００８】
（概説）
以下に詳述する実施形態では、量子化およびデータ埋め込みという目的に適合する対称格子のクラス(class of symmetric lattice)を紹介してある。後に説明するように、任意の次元(arbitrary dimension)ｎに対して、対称格子によれば、最も近い格子点(nearest lattice point)に対する所定のベクトル(given vector)を量子化するために、線形（ｎ次元の）時間アルゴリズム(linear (in n) time algorithm)を可能にする。提案する格子構造(lattice construction)としては、特殊なケースとして、周知のＡｎ格子(well-known An lattice)を含む。このような格子については、１９８８年の、J.H.ConwayおよびN.J.A.Sloanによる、SpringerーVerlag社の、Sphere Packings,Lattices and Groupsにて議論されている。提案された格子構造の適用として、与えられた信号が適切な擬似ランダムに形成された統計情報ベクトルに写像され、引き続き対称格子を使用して量子化される。
【０００９】
当業者は、本説明における議論の観点から理解するであろうが、量子化された統計情報ベクトル(quantized statistics vector)を、識別あるいは認証目的(identification or authentication purpose)のために使用することが可能である。それに応じてこの文書では、マークが埋め込まれた信号の統計情報ベクトルが、マークのない信号(unmarked signal)の統計情報ベクトル(statistics vector)の格子量子化されたバージョン(lattice-quantized version)になるように、埋め込まれるマーク(embedded mark)を設計することにより、信号へのデータ埋め込みを行うタスクに関する検討について議論する。これらの埋め込み処理に関連して、評価量（yield）と呼ばれる１つの測度を定義する。評価量は、格子のパッキング半径のカバーリング半径に対する率である。本発明のアプローチは評価量という意味で最適な対称格子を導き出す。大きな次元の格子を組み立てるための労力は推定攻撃に耐える電子透かしシステムの設計の必要性により動機付けられている。たとえば、非特許文献１および非特許文献２を参照されたい。
【００１０】
周囲空間の次元が大きければ大きいほど、このような推定攻撃（estimation attack）の有効性は小さくなり、適切な仮定の下で、精密に特徴付けることが可能である。推定攻撃の例としては、非特許文献３および非特許文献４を参照されたい。推定攻撃に対し強固な設計の例としては、非特許文献１および非特許文献２を参照されたい。
【００１１】
以下の議論では、次のような表記法を使用する。小文字の太字文字は実数のベクトルを意味し、大文字の太字文字は実数のマトリクスを意味する。添字はこれらのベクトルあるいはマトリクスの個々の要素を意味する。たとえば、ａｉおよびＡｉｊはそれぞれ、実数のベクトルａのｉ番目の要素、および実数のマトリクスＡの（ｉ,ｊ）番目の要素を表す。以下の議論では、ベクトルは列ベクトルであり、特に指定されない限り用いられる計量単位はユークリッドノルムであるという仮定がなされる。
【００１２】
議論では最初に、「対称格子および線形時間の量子化アルゴリズム」と題したセクションでの対称格子および量子化アルゴリズムの説明がすぐ次から始まる。この題材の説明に続いて、「マーク埋め込み」と題したセクションでは量子化アルゴリズムが電子透かしの分野でどのように適用されるかについて記述する。
【００１３】
対称格子および線形時間の量子化アルゴリズム
このセクションでは、対称格子のクラスが定義される。データ埋め込みのアプリケーションに対する評価量（yield）という意味で最適な対称格子が見付かる対称格子のクラスに対して線形時間の量子化アルゴリズムが与えられる。
【００１４】
定義２．１：対称格子Ｌn（α）（αで、パラメータ化されて）は次のように定義される。
【００１５】
【数１】
2011176840.tif 000003
【００１６】
ここで、
【００１７】
【数２】
2011176840.tif 000004
【００１８】
および
【００１９】
【数３】
2011176840.tif 000005
【００２０】
次元ｎでα＝１／２の対称格子は、この文書では（寸法係数（scaling factor）までの）Ａｎ格子と呼ばれることに注意すべきである。これらの格子には、いくつかの最適化プロパティがある。詳細な網羅的な議論については、非特許文献５を参照されたい。上の式（２．１）では、対称格子がｊと異なるｉに対して同一の角度値αを持つように定義されていることを認識し、理解するべきである。ｊと異なるｉに対して、αの周りに集中した確率分布から、平均値としてαを持つ、それぞれの角度値αを選択することもまた、可能である。そうすることにより、このアルゴリズムが平均について同様に機能すると期待することができる。それぞれの異なるｉ,ｊの対に対して異なるアルファの周りに角度値を集中するようにさせることにより、さらに攻撃を弱体化（weakening）することができる。ユニモジュラー変換を格子の基底に適用することによりこの格子を作ることができることを理解されたい。
【００２１】
定義２．２：Ｌn（α）に対する格子マトリクスＬn（α）はｎｘｎの実数行列であり、その行は
【００２２】
【数４】
2011176840.tif 000006
【００２３】
に含まれ、上記式（２．１）を満たす。
【００２４】
次の２つのサブセクションでは、第１のサブセクションで格子マトリクスＬn（α）を組み立てるためのアルゴリズムを記述し、第２のサブセクションで対称格子Ｌn（α）に対する量子化のためのアルゴリズムを記述する。
【００２５】
Ｌn（α）を組み立てるためのアルゴリズム
【００２６】
【数５】
2011176840.tif 000007
【００２７】
【数６】
2011176840.tif 000008
【００２８】
【数７】
2011176840.tif 000009
【００２９】
ここで、
【００３０】
【数８】
2011176840.tif 000010
【００３１】
のすべてが結合されてＬn（α）を形成する。より詳しく述べると、列挙されたステップ１〜４は全体で格子マトリクスＬn（α）の個々の行を定義する。これらのステップをｎ回実行すると、ｎ次元の格子マトリクスが定義される。
【００３２】
定義２．３：Ｌn（α）に対する格子マトリクスＭn（α）はｎｘｎ＋１の実数行列であり、その行は
【００３３】
【数９】
2011176840.tif 000011
【００３４】
に含まれ、式（２．１）を満たす。
【００３５】
以下の規則を使用してＭn（α）を組み立てることは直裁的であることに注意すべきである。すなわち、
【００３６】
【数１０】
2011176840.tif 000012
【００３７】
Ｍn（α）の（ｉ,ｊ）エントリは、ｊ＝１なら
【００３８】
【数１１】
2011176840.tif 000013
【００３９】
に、ｊ＝ｉ＋１なら
【００４０】
【数１２】
2011176840.tif 000014
【００４１】
に、そして
【００４２】
【数１３】
2011176840.tif 000015
【００４３】
の他のすべてで０に等しい。さらに、Ｌn（α）およびＭn（α）の両方の行が上の式（２．１）を満たすことを示すことができる。
【００４４】
Ｌn（α）に対する量子化のためのアルゴリズム
ここで、Ｌn（α）に量子化されるべきサイズ１ｘｎの入力ベクトル
【００４５】
【数１４】
2011176840.tif 000016
【００４６】
が与えられていると仮定する。ここで［・］は、最も近い整数に丸める演算子を意味する。図示され、記述された実施形態によると、Ｌn（α）およびＭn（α）は上で記述されたように生成される。次に、入力ベクトルｘ１は以下のようにｎ＋１次元に写像され、ｘ２を提供する：
ｘ２＝ｘ１（Ｌn（α））-1Ｍn（α）。
【００４７】
ここで、ｘ３が次のように生成される：
【００４８】
【数１５】
2011176840.tif 000017
【００４９】
ｘ３が見つけられると、ｘ４が
【００５０】
【数１６】
2011176840.tif 000018
【００５１】
のように計算される。ここで、ｘ４とｘ３の間の差が計算され、ｆ＝ｘ４−ｘ３が提供され、かつｑが次のように計算される：
【００５２】
【数１７】
2011176840.tif 000019
【００５３】
ｑの値に依存して、処理は異なる経路を取ることがあり得る。すなわち、ｑは０に対して、等しいか、より大きいか、あるいはより少ない場合があり得る。これらのそれぞれの場合により、量子化された出力に到達するための処理はいくらか異なって実行される。
【００５４】
ｑ＝０の場合の処理
計算されたｑの値が０の事象では、
【００５５】
【数１８】
2011176840.tif 000020
【００５６】
中の量子化出力
【００５７】
【数１９】
2011176840.tif 000021
【００５８】
は次のように生成される：
【００５９】
【数２０】
2011176840.tif 000022
【００６０】
【数２１】
2011176840.tif 000023
【００６１】
中の量子化出力が与えられると、
【００６２】
【数２２】
2011176840.tif 000024
【００６３】
中の量子化出力はここで次のように計算される：
【００６４】
【数２３】
2011176840.tif 000025
【００６５】
ｑ＞０の場合の処理
計算されたｑの値が０より大の事象では、
【００６６】
【数２４】
2011176840.tif 000026
【００６７】
中の量子化出力
【００６８】
【数２５】
2011176840.tif 000027
【００６９】
は次のように生成される：
１．最初に、ｈ＝ｆ1と定義し、かつ、
【００７０】
【数２６】
2011176840.tif 000028
【００７１】
を
【００７２】
【数２７】
2011176840.tif 000029
【００７３】
のように定義する。
【００７４】
２．ｇを降順にソートして、ソーティング順列を記録する。
【００７５】
３．
【００７６】
【数２８】
2011176840.tif 000030
【００７７】
を見付ける。ここで、
【００７８】
【数２９】
2011176840.tif 000031
【００７９】
４．
【００８０】
【数３０】
2011176840.tif 000032
【００８１】
を形成する。ここで、
【００８２】
【数３１】
2011176840.tif 000033
【００８３】
５．上のステップ２からのソーティング順列の逆を使用して、ｆ*を並べ換える。
【００８４】
６．
【００８５】
【数３２】
2011176840.tif 000034
【００８６】
中の量子化出力
【００８７】
【数３３】
2011176840.tif 000035
【００８８】
を次のように生成する：
【００８９】
【数３４】
2011176840.tif 000036
【００９０】
７．
【００９１】
【数３５】
2011176840.tif 000037
【００９２】
中の量子化出力が与えられると、
【００９３】
【数３６】
2011176840.tif 000038
【００９４】
中の量子化出力はここで次のように計算される：
【００９５】
【数３７】
2011176840.tif 000039
【００９６】
ｑ＜０の場合の処理
計算されたｑの値が０より小の事象では、
【００９７】
【数３８】
2011176840.tif 000040
【００９８】
中の量子化出力
【００９９】
【数３９】
2011176840.tif 000041
【０１００】
は次のように生成される：
１．最初に、ｈ＝ｆ1と定義し、かつ、
【０１０１】
【数４０】
2011176840.tif 000042
【０１０２】
を
【０１０３】
【数４１】
2011176840.tif 000043
【０１０４】
のように定義する。
【０１０５】
２．ｇを昇順にソートして、ソーティング順列を記録する。
【０１０６】
３．
【０１０７】
【数４２】
2011176840.tif 000044
【０１０８】
を見付ける。ここで、
【０１０９】
【数４３】
2011176840.tif 000045
【０１１０】
４．
【０１１１】
【数４４】
2011176840.tif 000046
【０１１２】
を形成する。ここで、
【０１１３】
【数４５】
2011176840.tif 000047
【０１１４】
５．このサブセクションのステップ２からのソーティング順列の逆を使用して、ｆ*を並べ換える。
【０１１５】
６．
【０１１６】
【数４６】
2011176840.tif 000048
【０１１７】
中の量子化出力
【０１１８】
【数４７】
2011176840.tif 000049
【０１１９】
を次のように生成する：
【０１２０】
【数４８】
2011176840.tif 000050
【０１２１】
７．
【０１２２】
【数４９】
2011176840.tif 000051
【０１２３】
中の量子化出力が与えられると、
【０１２４】
【数５０】
2011176840.tif 000052
【０１２５】
中の量子化出力はここで次のように計算される：
【０１２６】
【数５１】
2011176840.tif 000053
【０１２７】
補助定理２．１
このアルゴリズムが与えられたベクトルｘ１に対し最も近いベクトルを正しく出力する。
【０１２８】
この補助定理の証明の概要は以下の通りである。ｑ＝０の場合は、ｘ４が既に
【０１２９】
【数５２】
2011176840.tif 000054
【０１３０】
空間中の格子ベクトルであることに注意されたい。そのうえ、ｘ４はｘ３に座標的に最も近くにある。これはｑ＝０の場合に対する主張を立証する。ｑ＞０の場合には、その場合は、すべての座標の合計からｑを差し引く必要がある。αが１−αと等しくない場合があるので、最初の座標は特別であるかもしれない。したがって、最初の座標に関してこのアルゴリズムはすべての可能性を試みる。アルゴリズムが最初の座標からｔを引き算すると、アルゴリズムは次に、さらに他の座標からｑ−ｔを引き算する必要である。Ｌ２ノルム（norm）に関して、任意の座標（最初の座標以外の）から２を引き算することの不利益は、切り上げられた２つの異なった座標（ここでも最初の座標以外の）から１を引き算することより大きいということに注意されたい。したがって、ｑ−ｔ（個）の異なる座標から１を減少させるほうがよい。再び、切り上げ幅が最も大な座標が切り下げられると、Ｌ２ノルムに関しては、最も少ない不利益で済む。以上がまさにこのアルゴリズムがすることである。同様な議論がｑ＜０の場合にも適用される。
【０１３１】
補助定理２．２：量子化アルゴリズムの複雑さは最悪の場合で、ｎに線形である。
【０１３２】
定理２．３：ｎを与えると、電子透かしに対する評価量を最大にするという意味で最適な対称格子はＬn（０．５）であり、ここで評価量（yield）は、「別の格子セルに移動する最小の攻撃ひずみ」（パッキング半径）および「格子量子化における最大の埋め込みひずみ」（カバー半径）の率として定義される。
【０１３３】
上の定理の証明の概要は以下の通りである。最初に、Ｌn（０．５）の場合に対する評価量を見つけよう。次に、Ｌn（０．５）の評価量が他の任意のＬnに対する評価量に関する上限であることが示されるであろう。Ｌnの代わりに、Ｍnを取り扱うことの方が、より都合がよい。別の格子セルに移動してしまう最小の攻撃ひずみは、最も短いノンゼロ格子ベクトルの長さの半分であることに注意されたい。最も短いノンゼロ格子ベクトルの長さは１である（少なくとも２つの座標はノンゼロでなければならない）。それで、別の格子セルに移動するための最小の攻撃雑音のノルムは１／２である。次に、我々は格子量子化によって引き起こされる最大の埋め込みひずみを計算する。ｎ＋１が偶数であると仮定する。漸近的には、この仮定は重要ではない。慎重に技術的に分析すると、丸めに対して最も悪いベクトルは、Ｌ２ノルムに関しては、
【０１３４】
【数５３】
2011176840.tif 000055
【０１３５】
空間中で
【０１３６】
【数５４】
2011176840.tif 000056
【０１３７】
であることが示される。その場合、あらゆる座標は少なくとも
【０１３８】
【数５５】
2011176840.tif 000057
【０１３９】
により丸められる。したがって、最大の埋め込みひずみは
【０１４０】
【数５６】
2011176840.tif 000058
【０１４１】
となるであろう。これは評価量
【０１４２】
【数５７】
2011176840.tif 000059
【０１４３】
を与える。これが直交格子（すなわち、α＝０に対する対称格子）より４１％大きいことに注意されたい（これはスカラー量子化の場合である）。
【０１４４】
ここで、α＝１／２に対する評価量が
【０１４５】
【数５８】
2011176840.tif 000060
【０１４６】
に対する評価量の上限であることを証明する。このためには、「別の格子セルに移動するための最小の攻撃ひずみ」に関する上限、および「格子量子化における最大の埋め込みひずみ」の下限を示し、かつその限界がα＝１／２により達成されることを示すことで十分である。
【０１４７】
【数５９】
2011176840.tif 000061
【０１４８】
空間中でまだ動作している我々のタスクを、最初にα＜０．５、および次に、α＞０．５の２つの部分に分割する。
【０１４９】
α＜０．５の場合には、最も短いノンゼロ格子ベクトルに関する上限としてＭnの行の１つを選ぶことができる。その半分が「別の格子セルに移動するための最小の攻撃ひずみ」に関する上限であり、そのノルムは１／２である。次に、最も近い格子点に丸められるべきベクトルとして、
【０１５０】
【数６０】
2011176840.tif 000062
【０１５１】
を取る。我々は最も近い格子点にこのベクトルを量子化してしまう、そして、これが最大の埋め込みひずみに関する下限になると思われる、必要な最小のひずみを計算する。座標的には、最初の座標（それに対する最小ひずみが
【０１５２】
【数６１】
2011176840.tif 000063
【０１５３】
である）を除いて、必要とされる最小のひずみは
【０１５４】
【数６２】
2011176840.tif 000064
【０１５５】
である。したがって、０＜α＜１／２に対する評価量に関する上限として、我々は
【０１５６】
【数６３】
2011176840.tif 000065
【０１５７】
を得る。０＜α＜１／２における
【０１５８】
【数６４】
2011176840.tif 000066
【０１５９】
の上限は
【０１６０】
【数６５】
2011176840.tif 000067
【０１６１】
であり、これはＬn（０．５）の評価量である。
【０１６２】
α＞０．５の場合には、最も短いノンゼロ格子ベクトルに関する上限としてＭnの最初の２つの行の差を選ぶことができる。この半分は
【０１６３】
【数６６】
2011176840.tif 000068
【０１６４】
である。最大の埋め込みひずみに関する下限を計算するために、我々は同じベクトル
【０１６５】
【数６７】
2011176840.tif 000069
【０１６６】
を取る。一方、同じ方法を使用して、評価量に関する上限として我々は
【０１６７】
【数６８】
2011176840.tif 000070
【０１６８】
を得る。この上限は我々がα＝０．５の場合に対して計算した評価量よりもわずかである。以上が、証明の概要である。
【０１６９】
マーク埋め込み
本文書では、マーク埋め込みの問題もまた、「電子透かし」として言及される。電子透かし問題群の中で、我々は次の検証問題を考慮する、すなわち、レシーバは、受信された信号に、電子透かしが入っているか、あるいは電子透かしが入っていないか、のどちらであるかの判定を下す。我々は、レシーバが先験的に埋め込まれた情報の存在を知っていて、それを解読しようとする、復号化問題は考慮しない。
【０１７０】
以下の議論では、埋込みアルゴリズムが提供され、かつ秘密鍵Ｋが埋め込み器およびレシーバの両方により共有されているという仮定が為される。Ｋ（攻撃者にとって未知であるべきである）はすぐ次で記述されるアルゴリズムのランダム化されたステップにおける、安全な擬似乱数ジェネレータ（Pseudo Random Number Generator：ＰＲＮＧ）のシード（seed）として使用される。したがって、以下で記述されるアルゴリズムのランダム化されたステップは、攻撃者にとって実際に、無作為に見える。しかしながら、そのランダム化されたステップは埋め込み器およびレシーバの両方にとっては既知である。以下の議論においては、アルゴリズムはサイズ５１２ｘ５１２の濃淡イメージに対する記述として述べられる。しかしながら、様々なサイズのカラーイメージおよび音響信号のような、他のタイプの信号に対して、このアルゴリズムの拡張が容易に設計し得ることに注意すべきである。
【０１７１】
埋め込みアルゴリズム概要
図１は、ここに記述された実施形態による埋め込みアルゴリズムにおけるステップを示すフローチャートである。任意の適切なハードウェア、ソフトウェア、ファームウェア、またはその組合せに関連してこの方法を実施することができる。さらに、記述されようとしている方法はコンピュータコンピュータ可読媒体上に有るコンピュータで読み取り可能な命令の形をしていることが可能である。これらの命令は、コンピュータあるいは計算システムで処理されると、記述されようとしている方法を実施することが可能である。
【０１７２】
ステップ１００は、イメージＩを与えられると、そのイメージに変換を適用する。ここで図示され、記述された実施形態では、そのイメージに３レベルの離散ウェーブレット変換を適用する。Ｓ（サイズｎｘｎ）は、水平および垂直の両方向に対する低周波サブバンドを意味する。ステップ１０２においてで、イメージに関連した擬似ランダム線形統計情報を計算する。ここで図示され、記述された実施形態では、このステップでＳからの統計情報ａ（サイズｍｘ１）を計算する。これが如何にして為し得るかに関する一例が図２で詳細に記述してある。ステップ１０４において、擬似ランダム線形統計情報を格子量子化する。格子量子化の一般的な概念は上に記述されている。この格子量子化がマーク埋め込みに関連してどのように実行されるかに関する一例は、図３で詳細に説明する。ステップ１０６では、量子化された擬似ランダム線形統計情報を使用して電子透かしを計算する。この実施形態において、これが如何に為されるかに関する一例は図４に詳細に記述してある。電子透かしが計算されると、ステップ１０８において、ステップ１００からの変換されたイメージに電子透かしを埋め込む。
【０１７３】
擬似ランダム線形統計情報の計算
図２は、本発明の一実施形態による擬似ランダム線形統計情報を計算するための方法におけるステップを記述したフローチャートである。ステップ２００において、イメージの１つあるいは複数の擬似ランダム領域を選択する。その領域は長方形、正方形や同様のものなどの任意の適切な形状の領域より成ることが可能である。進行中の議論の目的のために、その領域の形状は正方形とする。区間［ｌL,ｌH]からの一様確率変数の具現化として、この方法ではｉ番目の正方形に対してそのサイズｌiを生成する。その左上隅（ｌｏｃxi，ｌｏｃyi）の座標は区間［ｎ−ｌi＋１］からの一様確率変数の独立した具現化として生成される。
【０１７４】
ステップ２０２において、それぞれの領域に関連した擬似ランダム重みを生成する。
【０１７５】
図示した実施形態では、それぞれの正方形ｉ，
【０１７６】
【数６９】
2011176840.tif 000071
【０１７７】
に対して、この方法では、最初に行列Ｐi（サイズｌiｘｌi）（
【０１７８】
【数７０】
2011176840.tif 000072
【０１７９】
、
【０１８０】
【数７１】
2011176840.tif 000073
【０１８１】
が、単位分散、０平均のガウス分布から独立に生成されたような）を形成する。その方法は次に、周波数０＜ｆweight＜１に帯域幅制限されたｌiｘｌiの行列の全寸法に拡がる部分空間へＰiを投影する。ここで、
【０１８２】
【数７２】
2011176840.tif 000074
【０１８３】
をその投影の結果とする。次に、その方法は、結果のＬ２−ノルムがＮになるように、それぞれの
【０１８４】
【数７３】
2011176840.tif 000075
【０１８５】
の寸法を合わせる。Ｑiを寸法合わせにより得られたサイズｌiｘｌiの行列であるとしよう。
【０１８６】
ステップ２０４において、擬似ランダム統計情報変換行列を形成する。事実上、このステップでは以下に記述する擬似ランダム線形統計情報の計算に対する線形演算子変換行列を準備する。図示した実施形態では、それぞれの正方形ｉに対して、その方法は初めに、ａｌｌ−０行列
【０１８７】
【数７４】
2011176840.tif 000076
【０１８８】
（サイズｎｘｎ）を生成する。その方法は次に、ｉ番目の正方形のエントリを、Ｑi（置き換えにおいてはｌiおよび（ｌｏｃxi，ｌｏｃyi）を使用することにより）で置き換えることにより、Ｒiを形成する。その方法は次に、１ｘｎ2ベクトルｒiを形成するためにＲiの要素を再配置する。ここで、ｒiがＴ（サイズｍｘｎ2）の第ｉ行を形成する。
【０１８９】
擬似ランダム統計情報変換行列Ｔを形成すると、ステップ２０６において、この変換行列を使用して擬似ランダム線形統計情報を計算する。事実上、このステップは、選択された領域の位置および重みの両方を使用して線形統計情報を計算する。ここで図示され、記述された実施形態では、擬似ランダム線形統計情報は、ａ＝Ｔｓにより見つけられる。ここで、ｓ（サイズｎ2ｘ１）はＳの再配置された要素により形成される。
【０１９０】
上で記述した処理は、図１におけるステップ１０２に関連して以前に記述した処理を脚色したものである。次のセクションでは、擬似ランダム線形統計情報の格子量子化に関する、図１のステップ１０４にて行われた処理を脚色するものである。
【０１９１】
統計情報の格子量子化
図３は、擬似ランダム線形統計情報を格子量子化するための方法におけるステップについて記述してある。以下の議論において、線形統計情報ａは、以下のステップを使用し、格子Ｌ（α）およびひずみ制約条件βを使用して、ｂに量子化される（ａ，ｂは、ともにサイズｍｘ１である）。記述されるべき構造ではパラメータαが対称格子Ｌm（α）を一意に決定することに注意されたい。考慮されるべき格子の特性およびそれらに対する線形時間量子化アルゴリズムについては上で議論してある。
【０１９２】
したがって、ステップ３００において、格子のそれぞれのセルのスケーリングパラメータを計算する。ひずみ制約条件βおよび格子パラメータαが与えられると、その方法により、Δ（その格子のそれぞれのセルのスケーリングパラメータ）がわかる。一実施形態では、与えられたβおよびαに合致するようにΔを見付けるために、コードブック検索法を使用している。この例では、コードブックはオフライン的に準備される。
【０１９３】
ステップ３０２において、変換ベクトルを疑似ランダム的に生成する。本実施形態では、変換ベクトルｔが生成される。ここで、ｔiは［０、１００］、
【０１９４】
【数７５】
2011176840.tif 000077
【０１９５】
での一様分布の具現化である。
【０１９６】
ステップ３０４では、スケーリングパラメータおよび変換ベクトルを使用して量子化された統計情報を計算する。ここで図示した実施形態では、量子化された統計情報はｂ＝Ｒm（ａ／Δ＋ｔ、α）−ｔで与えられる。ここで、Ｒm（・，α）は次元ｍおよびパラメータαの単位セル対称格子Ｌm（α）に対する量子化アルゴリズムを示し、対称格子のクラスおよび量子化アルゴリズムＲm（・，α）は上で詳細に説明した通りである。
【０１９７】
擬似ランダム線形統計情報を格子量子化したので、量子化された擬似ランダム線形統計情報を使用して電子透かしを計算する処理を行う。処理のこの態様は次のセクションで説明する。
【０１９８】
電子透かしの計算
図４は、電子透かしを計算する方法におけるステップを記述したものであり、図１のステップ１０６における処理を脚色するフローチャートである。
【０１９９】
ステップ４００では、統計ドメインでの量子化雑音を計算する。ここで図示され、記述された実施形態では、この領域の量子化雑音をｑ＝ｂ−ａとして与える。ここで、ａは前に計算された擬似ランダム線形統計情報を構成し、ｂは上で計算された量子化された統計情報を構成する。
【０２００】
次に、ステップ４０２において、離散ウェーブレット変換（Discrete Wavelet Transform：ＤＷＴ）領域における量子化雑音を計算する。図示した実施形態では、ｑが与えられたとき、ＤＷＴドメインにおける量子化雑音Ｗ（サイズｎｘｎ）を以下のように計算する。まず最初に、その方法は周波数０＜ｆwm＜１に帯域制限されたｎｘｎの行列の全寸法に拡がる部分空間に直交する部分空間に対して投影行列Ｄ（サイズｋｘｎ2）を生成する（ｆwmを与えられると、ｋは一意的に決定される）。
【０２０１】
投影行列Ｄが生成されると、ベクトル形式ｗ（サイズｎ2ｘ１）における量子化雑音が
【０２０２】
【数７６】
2011176840.tif 000078
【０２０３】
で与えられる。ここで、
【０２０４】
【数７７】
2011176840.tif 000079
【０２０５】
は転置演算子、
【０２０６】
【数７８】
2011176840.tif 000080
【０２０７】
（サイズｍ＋ｋｘｎ2）、
【０２０８】
【数７９】
2011176840.tif 000081
【０２０９】
（サイズｍ＋ｋｘ１）、０はサイズｋｘ１の全−０ベクトルである。
【０２１０】
次に、サイズｎｘｎのＷを得るためにｗを再配列する。
【０２１１】
ここで記述された例では、Ｗがイメージに埋め込まれるべき計算された電子透かしを構成する。
【０２１２】
電子透かしの埋め込み
上で述べたように電子透かしを計算したので、次は電子透かしをイメージに埋め込む処理となる。図示した実施形態では、これは以下の通りに達成される。電子透かしが入れられたＤＷＴ−ＬＬサブバンドはＸ＝Ｓ＋Ｗで与えられる。ここで、Ｓは上で記述された３レベル離散ウェーブレット変換が適用された後のイメージＩを構成する。図１におけるステップ１００から、Ｘと他の変化のないサブバンドの組み合わせに逆ＤＷＴを適用すると、電子透かしを入れたイメージが得られる。
【０２１３】
追加的検討および備考
ベクトル形式、
【０２１４】
【数８０】
2011176840.tif 000082
【０２１５】
における量子化雑音は次の最適化問題に対する一意な解である、ことを示すことができる：
【０２１６】
【数８１】
2011176840.tif 000083
【０２１７】
ＤＷＴドメインにおいて、Ｔｗ＝ｑおよびＤｗ＝０の両方を満たす（２番目の制約条件は、何らかの意味における「滑らか」の制約条件をｗに課すものであり、知覚的目的に対して重要である）ような、ｗを見つけることが望ましい。
【０２１８】
【数８２】
2011176840.tif 000084
【０２１９】
により与えられた解は、これらの制約条件の両方を満たす最小のＬ２−ノルムの量子化雑音である。我々は
【０２２０】
【数８３】
2011176840.tif 000085
【０２２１】
が正則（full-rank）であると仮定する。我々の実験によると、これは現実にはほとんど常に満足される。
【０２２２】
我々は、ｋ＋ｍが大きく、ｋ≫ｍである場合に、
【０２２３】
【数８４】
2011176840.tif 000086
【０２２４】
を計算することが手間がかかる可能性があることを発見した。この場合、以下の結果が有益である：
定理３．１：実数行列Ｍ：
【０２２５】
【数８５】
2011176840.tif 000087
【０２２６】
ここで一般に、Ａ11はｍｘｍ、Ａ22はｎｘｎ，Ａ12はｍｘｎ，Ａ21はｎｘｍで、ｍ≠ｎを与えられると、
【０２２７】
【数８６】
2011176840.tif 000088
【０２２８】
ここで、Ａ11およびＡ22がともに可逆的であると仮定すると、
【０２２９】
【数８７】
2011176840.tif 000089
【０２３０】
である。
【０２３１】
この結果をＵに適用すると、我々は
【０２３２】
【数８８】
2011176840.tif 000090
【０２３３】
ここで、
【０２３４】
【数８９】
2011176840.tif 000091
【０２３５】
およびＤの行は元来直交しているので、
【０２３６】
【数９０】
2011176840.tif 000092
【０２３７】
を得る。
【０２３８】
次に、我々は「盲目の（blind）」マーク検出アルゴリズム、すなわち、マークなしのソースではなく、キーの存在を仮定する、検出アルゴリズムを提供する。我々は、秘密鍵Ｋが検出機構側で分かっていると仮定する。組み込み機構でのように、アルゴリズムのランダム化されたステップにおける、擬似ランダムジェネレータのシードとしてＫが使用される。ここでアルゴリズムの記述を行う。
【０２３９】
まず最初に入力イメージＩ’が与えられると、量子化雑音ｑ’を見つけるために、図１における１００、１０２、１０４と全く同じステップに従う。次に、
【０２４０】
【数９１】
2011176840.tif 000093
【０２４１】
を計算する。ｄ＜τの場合には、イメージが「電子透かし済みである」と宣言し、それ以外の場合には、イメージが「電子透かしなしである」と宣言する。
【０２４２】
検出アルゴリズムで、最も近い格子点への受信信号の統計情報ベクトルのＬ２距離が決定統計情報として使用されることに注意されたい。この検出規則が、ＡＷＧＮ攻撃チャンネルに対するエラー確率という意味で、最適であることを示すことができる。これは検出理論からの標準的な結果である。
【０２４３】
実験成果および議論
図５は、標準偏差１００のＡＷＧＮ攻撃を受けた５０００件の無作為なイメージおよびキーの対に対するソフトウェア検出機構出力の動作上の分布を図示する。実線および破線は、α＝０に対する電子透かし済み、および電子透かしなしのイメージに対するソフトウェア検出機構出力を示している。一点鎖線および点線は、α＝０．５に対する電子透かし済み、および電子透かしなしのイメージに対するソフトウェア検出機構出力を示している。
【０２４４】
エラーの動作上の確率という意味における電子透かしの問題に対して、我々は異なったタイプの対称格子を実験的に比較した。我々の実験では、我々は無作為に選ばれたキーを持つ、サイズ４０００のイメージデータベースから無作為に選ばれたイメージを使用した。それぞれの選ばれたイメージおよびキーに対して、我々は電子透かし済み、および電子透かしなしのイメージの場合に対して最も近い格子点への距離（すなわち、上記の「マーク埋め込み」のセクションの検出の部分で与えられたｄの値）を計算した。
【０２４５】
実際には、検出機構で「電子透かし済み」、あるいは「電子透かしなし」の判定をもたらす距離ｄに、しきい値分け（thresholding）が適用される。同一分布（identical distribution）を持つメモリー無しの攻撃に対するエラー確率という意味では、この検出規則が最適であることを示すことができる。
【０２４６】
我々は合計５０００回の試行について実験を行った（すなわち、５０００個の無作為に選ばれたイメージおよびキーの対が結果を出すために使用されている）。量子化パラメータΔは、電子透かしひずみ（Ｌ２の意味において）がすべての場合において、ほとんど同じに（およびユーザーの規定値と等しく）なるように選ばれている。図５では、我々は、攻撃が標準偏差１００のＡＷＧＮ（Additive White Gaussian Noise：付加的白色ガウス雑音）である場合の、ソフトウェア検出機構出力（すなわち、ｄ）の分布を示す。実線はα＝０、一点鎖線はα＝０．５に対する電子透かしを入れられたイメージに対する検出機構の出力を示す。破線はα＝０、点線はα＝０．５に対する電子透かしのないイメージに対する検出機構の出力を示す。図６では、我々は、攻撃が標準偏差１５０のＡＷＧＮである場合の検出機構のＲＯＣ曲線を示す。誤警報の確率を水平軸で、見逃しの確率を垂直軸で示す。実線、破線、一点鎖線、および点線はそれぞれαパラメータ０、０．３、０．５、および０．７の対称格子に対応している。α＝０．５の値が評価量という意味で最適であるように示されるが、たとえば、図５および６で分かるように、我々は、αの値の異なる対称格子の性能は、広い種類の攻撃に対して、ほとんど同じであることを実験的に観測した。これには一様スカラー量子化に対応する直交格子（α＝０）を含むことに注意されたい。
【０２４７】
例示的システム
図７は、上述した実施形態を実施するための例示的システムを示す計算システム７００は上で記述したようにイメージをマークするために利用されるマーキングコンポーネント７０２を備える。マーキングコンポーネント７０２は、任意の適切なハードウェア、ソフトウェア、ファームウェア、またはその組み合わせに関連して実施することができる。本実施形態では、マーキングコンポーネント７０２はソフトウェアで実施される。したがって、マーキングコンポーネントはプロセッサで実行可能な１つまたは複数のコンピュータコンピュータ可読媒体上のコンピュータで読み取り可能な命令の形で存在することができる。
【０２４８】
この例では、マーキングコンポーネント７０２は、変換コンポーネント７０４、線形統計情報ジェネレータ７０６、格子量子化器７０８、電子透かしジェネレータ７１０、および電子透かし埋め込み器７１２を備える。これらのコンポーネントがそれぞれ別々のコンポーネントとして図示されているが、実際にはそのような要求は必ずしも必須ではないということを認識し、理解されたい。
【０２４９】
動作的には、デジタルイメージは、システム７００に受け取られ、処理され、電子透かしを入れられたイメージを提供する。この例では、変換コンポーネント７０４を、図１のステップ１００で記述した処理に対応する方法で動作するように構成する。線形統計情報ジェネレータ７０６は、図１のステップ１０２および図２で記述した処理に対応する方法で動作するように構成する。格子量子化器７０８は、図１のステップ１０４および図３で記述した処理に対応する方法で動作するように構成する。電子透かしジェネレータ７１０は、図１のステップ１０６および図４で記述した処理に対応する方法で動作するように構成する。電子透かし埋め込み器７１２は、図１のステップ１０８で記述した処理に対応する方法で動作するように構成する。
【０２５０】
イメージが適切な電子透かしによりマークされると、上述したように電子透かしレシーバ７１４が、イメージを受け取り処理する。電子透かしレシーバは、Ｗｉｎｄｏｗｓ（登録商標）のＭｅｄｉａ Ｐｌａｙｅｒなどのアプリケーションのコンポーネントを通常含む。
【０２５１】
結論
これまで説明してきた実施形態では、ユーザあるいは悪意ある攻撃が、イメージ、ビデオ、および音響信号を操作するための、商品によって使用される信号処理変換などのように実行される可能性のある、いくつかの通常の信号処理変換に耐える改良された電子透かしおよびデータ埋め込みのシステムおよび方法を提供する。
【０２５２】
なお、構造上の特色、および／または、方法論のステップとして特有な言語を用いて説明してきたが、請求の範囲で定義される本発明は、これら特定の特徴あるいはステップに必ずしも限定されるわけではないことを理解されたい。その特定の特徴あるいはステップは、本発明を実施するのに好適な実施形態として開示したものである。
【符号の説明】
【０２５３】
７００  計算システム
７０２  マーキングコンポーネント
７０４  変換コンポーネント
７０６  線形統計ジェネレータ
７０８  格子量子化器
７１０  電子透かしジェネレータ
７１２  電子透かし埋め込み器
７１４  電子透かしレシーバ
【図１】
2011176840.tif 000094
【図２】
2011176840.tif 000095
【図３】
2011176840.tif 000096
【図４】
2011176840.tif 000097
【図５】
2011176840.tif 000098
【図６】
2011176840.tif 000099
【図７】
2011176840.tif 000100