JP4266677B2

JP4266677B2 - Digital watermark embedding method and encoding device and decoding device capable of using the method

Info

Publication number: JP4266677B2
Application number: JP2003065808A
Authority: JP
Inventors: 亜輝臣国狭
Original assignee: Sanyo Electric Co Ltd
Current assignee: Sanyo Electric Co Ltd
Priority date: 2002-09-20
Filing date: 2003-03-11
Publication date: 2009-05-20
Anticipated expiration: 2023-03-11
Also published as: JP2004163855A

Description

【０００１】
【発明の属する技術分野】
この発明は、電子透かし技術に関し、特に電子透かしの埋め込み方法、およびその方法を利用可能な符号化装置と復号装置に関する。
【０００２】
【従来の技術】
ここ数年、インターネット利用人口が急増し、インターネット利用の新たなステージともいえるブロードバンド時代に入ろうとしている。ブロードバンド通信では通信帯域が格段に広がるため、音声、静止画、動画などデータ量の大きいコンテンツの配信も気軽にできるようになる。このようなデジタルコンテンツの流通が盛んになると、コンテンツの著作権の保護がより一層求められることになる。
【０００３】
ネットワーク上に流通するコンテンツのデータは他人に容易にコピーされ、著作権に対する保護が十分ではないのが現状である。そこで著作権を保護するために、コンテンツの作成者や利用者の情報を電子透かしとしてコンテンツデータに埋め込む技術が開発されている。この電子透かし技術を用いることにより、ネットワーク上で流通するコンテンツデータから電子透かしを抽出して、不正利用を検出したり、不正コピーの流通経路を追跡することが可能となる。
【０００４】
従来の電子透かしの埋め込み技術には、電子透かし情報を埋め込む処理の自由度を維持しつつ、耐性の強い電子透かしの埋め込みを可能とするものがある（たとえば、特許文献１参照）。
【０００５】
また、従来のデジタル署名による画像認証技術には、画像に対するＪＰＥＧ（Joint Photographic Expert Group）圧縮は許容するが、その他の不正な操作があった場合には、画像の認証が不成立になるデジタル署名の生成を可能とするものがある（たとえば、非特許文献１参照）。
【０００６】
【特許文献１】
特開２０００−１３５８７号公報（全文、第１−１５図）
【非特許文献１】
Ching-Yung Lin and Shih-Fu Chang, "A Robust Image Authentication Method Distinguishing JPEG Compression from Malicious Manipulation," IEEE Trans. on Circuits and Systems for Video Technology, pp.153 -168, Feb. 2001.
【０００７】
【発明が解決しようとする課題】
電子透かしは、不正利用者による改ざんを防止するために、利用者には分からないようにコンテンツデータに埋め込まれる。しかしコンテンツデータは、流通過程や利用過程で、圧縮符号化や各種フィルタリングなどの信号処理が加えられたり、ユーザにより加工されたり、あるいは透かし情報が改ざんされるなど、さまざまな操作を受けることがあり、その過程で埋め込まれた電子透かしデータの一部が変更されたり、消失する可能性がある。したがって電子透かしはこういった操作に対する耐性が要求される。
【０００８】
特許文献１には、電子透かしの耐性を高めるための電子透かしの埋め込み技術が提案されているが、人間の視覚特性に合わせて、画像のエッジ部分やテクスチャ領域の中でも変化の大きな部分など高周波成分に電子透かしを埋め込む方法であり、個々のコンテンツデータの内容に強く依存し、透かし埋め込み後のコンテンツデータに対するさまざまな操作に対して耐性を強化するには、汎用性や柔軟性の面で限界がある。
【０００９】
本発明はこうした状況に鑑みてなされたもので、その目的は、耐性の強い電子透かしを埋め込み、電子透かしの検出誤差を低減することの可能な技術の提供にある。
【００１０】
【課題を解決するための手段】
本発明のある態様は電子透かし埋め込み方法に関する。この方法は、スクランブルして生成された複数の電子透かしデータの候補をホストデータの指定されたブロックに埋め込み、それらの電子透かしの耐性を評価して、その評価が良好である前記電子透かしデータの候補が埋め込まれたホストデータを取得する。
【００１１】
ホストデータは、電子透かしを埋め込む対象となるオリジナルデータであり、たとえば静止画、動画、音声などのデータである。埋め込まれる電子透かしには、オリジナルデータの識別情報、作成者情報、利用者情報などが含まれる。その他、認証を目的として、ホストデータのダイジェストデータ、すなわちホストデータの特徴を端的に表したデータを電子透かしとして埋め込むことも可能である。電子透かしの耐性とは、電子透かしの埋め込まれたホストデータが改変されるなどの攻撃を受けた場合や、電子透かしの埋め込まれたホストデータに圧縮符号化やフィルタリングなどの信号処理が施された場合など、電子透かしの埋め込み後のホストデータに対して何らかの操作が加えられた場合に電子透かしデータがもつ頑強性をいう。
【００１２】
電子透かしを埋め込む側では、電子透かしデータをスクランブルする際、元の電子透かしデータを複数の透かしデータの候補に対応づける１対多の写像が用いられる。電子透かしを抽出する側では、逆写像を行って、スクランブルされた透かしデータから元の電子透かしデータを得る。そのため電子透かしを抽出する側では、元の電子透かしデータと複数の透かしデータの候補の対応テーブルが利用されてもよい。また、電子透かしを埋め込む側で、元の電子透かしデータから所定の初期値のもとで複数の透かしデータの候補を生成するスクランブル関数が利用されてもよい。この場合、電子透かしを抽出する側では、スクランブルに利用された初期値とスクランブル関数にもとづいて、抽出された電子透かしの逆スクランブルが行われる。
【００１３】
本発明の別の態様は符号化装置に関する。この装置は、電子透かしデータを埋め込むべきホストデータから複数のブロックを選択するブロック選択部と、前記ブロック選択部により選択された前記複数のブロックの各々に異なる電子透かしデータを独立に埋め込む埋め込み部とを含む。
【００１４】
ここでいうブロックとは、ホストデータの分割単位であり、ホストデータに対して空間周波数成分に変換するフィルタリング処理が施される場合には、フィルタリング処理が施される前のホストデータにおける空間領域に対応する。たとえば、ホストデータに離散ウェーブレット変換によるフィルタリング処理が施された場合は、離散ウェーブレット変換後のホストデータの各サブバンドから選択された、離散ウェーブレット変換前のホストデータにおける同一の空間領域を構成するウェーブレット変換係数の集合が、電子透かしデータの埋め込みブロックとなる。
【００１５】
別の例として、ホストデータがブロック分割され、各ブロックに離散コサイン変換によるフィルタリング処理が施された場合は、離散コサイン変換後のホストデータの各ブロックは、そのまま離散コサイン変換前のホストデータの各ブロックに対応するので、この離散コサイン変換係数を含むブロックが電子透かしデータの埋め込みブロックとなる。もっとも、離散コサイン変換の最小処理単位であるブロックの１つ分を埋め込みブロックにするとは限らず、ここではホストデータのある部分領域を埋め込みブロックとする趣旨であるから、離散コサイン変換の処理単位であるブロックをいくつか集めたものを埋め込みブロックとしてもよい。
【００１６】
本発明のさらに別の態様も符号化装置に関する。この装置は、電子透かしデータを埋め込むべきホストデータから特定のブロックを選択するブロック選択部と、前記電子透かしデータをスクランブルして複数の透かしデータの候補を生成するスクランブル部と、前記ブロック選択部により選択された前記ホストデータの前記特定のブロックに前記複数の透かしデータの候補のそれぞれを埋め込み、複数の埋め込みホストデータの候補を生成する埋め込み部と、前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する評価部と、前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択して出力する選択部とを含む。
【００１７】
本発明のさらに別の態様も符号化装置に関する。この装置は、電子透かしデータを埋め込むべきホストデータのブロックを選択するブロック選択部と、前記電子透かしデータが埋め込まれる前記ホストデータの前記ブロックの埋め込み位置の候補を複数生成する位置情報生成部と、前記ブロック選択部により選択された前記ホストデータの前記ブロックの前記複数の埋め込み位置の候補のそれぞれに前記透かしデータを埋め込み、複数の埋め込みホストデータの候補を生成する埋め込み部と、前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する評価部と、前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択して出力する選択部とを含む。
【００１８】
前記ブロック選択部は、前記特定のブロックとして、異なる周波数成分をもつ複数のブロックの組み合わせを選択してもよい。たとえば、主に高周波成分を含むブロックと主に低周波成分を含むブロックの組み合わせを選択してもよい。また、前記特定のブロックとして、ホストデータにおいて所定量だけ離れた位置にあり、隣接しない複数のブロックの組み合わせを選択してもよい。このように複数のブロックの組み合わせが選択された場合、この組み合わせが透かしデータの埋め込みおよび抽出の単位となる。
【００１９】
前記評価部は、前記耐性を、前記ホストデータを前記透かしデータに対するノイズと見なした場合に計算されるＳＮ比により評価してもよい。前記評価部は、前記埋め込みホストデータに対して有用性のある操作を施した上で、前記耐性を評価してもよい。有用性のある操作とは、たとえば圧縮符号化や各種フィルタリングなどの信号処理、スケーリングや回転などの幾何学的変換などである。前記評価部は、前記埋め込みホストデータを圧縮符号化する際の量子化誤差を考慮して前記耐性を評価してもよい。前記耐性をＳＮ比で評価する場合、埋め込みホストデータに有用性のある操作を施した後に抽出される透かしデータと実際に埋め込まれた透かしデータとの間の分散を評価してもよい。
【００２０】
本発明のさらに別の態様は復号装置に関する。この装置は、ホストデータから電子透かしの埋め込まれた複数のブロックを選択するブロック選択部と、前記ブロック選択部により選択された前記複数のブロックの各々から独立にスクランブルされた透かしデータを抽出する抽出部と、前記スクランブルされた透かしデータのスクランブルを解除するデスクランブル部とを含む。これによりブロックごとに改ざんの有無を検出することができる。
【００２１】
本発明のさらに別の態様も復号装置に関する。この装置は、ホストデータから電子透かしの埋め込まれたブロックを選択するブロック選択部と、電子透かしが埋め込まれた前記ホストデータの前記ブロックの埋め込み位置の候補を複数生成する位置情報生成部と、前記複数の埋め込み位置の候補のそれぞれを用いて、前記ブロック選択部により選択された前記ホストデータの前記ブロックに埋め込まれた透かしデータの候補を複数抽出する抽出部と、前記抽出された複数の透かしデータの候補を想定される透かしデータとの間で照合する照合部と、前記照合部による照合結果に基づいて前記複数の透かしデータの候補の一つを選択して出力する選択部とを含む。
【００２２】
本発明のさらに別の態様はコンピュータプログラムに関する。このプログラムは、電子透かしデータを埋め込むべきホストデータから特定のブロックを選択する工程と、前記電子透かしデータをスクランブルして複数の透かしデータの候補を生成する工程と、前記ブロック選択部により選択された前記ホストデータの前記特定のブロックに前記複数の透かしデータの候補のそれぞれを埋め込み、複数の埋め込みホストデータの候補を生成する工程と、前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する工程と、前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択する工程とをコンピュータに実行させる。
【００２３】
本発明のさらに別の態様は電子透かし埋め込み方法に関する。この方法は、ホストデータのダイジェストデータをスクランブルして複数の電子透かしデータの候補を生成し、それらの透かしデータの候補がそれぞれ前記ホストデータに埋め込まれた場合における当該電子透かしの耐性を評価し、その評価が良好であるものを前記ダイジェストデータが埋め込まれたホストデータとして取得する。
【００２４】
前記ダイジェストデータは、前記ホストデータを特徴づけるサンプルデータの上位ビットを用いて生成されてもよい。ホストデータは圧縮符号化の際、量子化され、下位ビットの情報が落とされる。そこで、サンプルデータの上位ビットからダイジェストデータを生成するとき、量子化で落とされる下位ビットを使用しないようにしてもよい。また、サンプルデータの比較的下位の位置にあるビットは、透かしデータの埋め込みにも使用される。そこで、サンプルデータの上位ビットからダイジェストデータを生成するとき、量子化の影響を受けない下位ビットであっても、透かしデータの埋め込みに利用されるビットを使用しないようにしてもよい。
【００２５】
本発明のさらに別の態様は符号化装置に関する。この装置は、ホストデータのダイジェストデータを生成するダイジェスト生成部と、前記ダイジェストデータをスクランブルして複数の透かしデータの候補を生成するスクランブル部と、前記複数の透かしデータの候補をそれぞれ前記ホストデータに埋め込み、複数の埋め込みホストデータの候補を生成する埋め込み部と、前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する評価部と、前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択して出力する選択部とを含む。
【００２６】
ホストデータから特定のブロックを選択するブロック選択部をさらに含み、前記ダイジェスト部は前記ホストデータの前記特定のブロックから前記ダイジェストデータを生成し、前記埋め込み部は、前記ホストデータの前記特定のブロックに前記複数の透かしデータの候補のそれぞれを埋め込み、前記複数の埋め込みホストデータの候補を生成してもよい。このように、ホストデータのブロックを指定してダイジェストを生成することにより、ダイジェストデータを一方向性関数によりハッシングするような場合でも、ホストデータの改ざん箇所をブロック単位で検出できるようになる。
【００２７】
本発明のさらに別の態様は復号装置に関する。この装置は、ホストデータから電子透かしとして埋め込まれたダイジェストデータを抽出する抽出部と、前記ホストデータからダイジェストデータを生成するダイジェスト生成部と、前記ダイジェスト生成部により生成されたダイジェストデータを前記抽出部により抽出されたダイジェストデータと照合することにより、前記ホストデータに対する改ざんの有無とともに改ざんのおおまかな位置を特定する照合部とを含む。ダイジェストデータはホストデータの低周波成分などによりホストデータのおおまかな特徴を表したものであるため、照合部によりダイジェストデータの一部のビットに不一致が発見されると、その不一致のビットに対応するホストデータの箇所に変更があったと考えられ、改ざんのおおまかな位置をつかむことができる。
【００２８】
ホストデータから電子透かしの埋め込まれたブロックを選択するブロック選択部をさらに含み、前記抽出部は、前記ホストデータの前記ブロックから前記ダイジェストデータを抽出し、前記ダイジェスト生成部は、前記ホストデータの前記ブロックから前記ダイジェストデータを生成してもよい。このように、ダイジェストデータが生成されるブロックが決まっていることにより、抽出されるダイジェストデータが一方向性関数によりハッシングされているような場合でも、改ざん箇所をブロック単位で特定することができる。
【００２９】
本発明のさらに別の態様はコンピュータプログラムに関する。このプログラムは、ホストデータからダイジェストデータを生成する工程と、生成されたダイジェストデータをスクランブルして複数の透かしデータの候補を生成する工程と、前記ホストデータに前記複数の透かしデータの候補のそれぞれを埋め込み、複数の埋め込みホストデータの候補を生成する工程と、前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する工程と、前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択する工程とをコンピュータに実行させる。
【００３０】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【００３１】
【発明の実施の形態】
実施の形態１
図１は、実施の形態１に係る符号化装置１０の構成を示す。この構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリにロードされた電子透かし埋め込み機能のあるプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。
【００３２】
符号化装置１０は、ホストデータＶに透かし情報Ｉを埋め込む処理を行い、埋め込みホストデータＷを出力する。ホストデータＶは、たとえば音声、静止画、動画などのデータである。透かし情報Ｉは、そのホストデータＶの識別情報、作成者情報、利用者情報など著作権に関する情報、ホストデータＶの改ざん検出を行う認証情報、タイムスタンプなどである。透かし情報Ｉは、一般にこれらの情報を暗号化したものである。
【００３３】
ビット長伸長部１２は、ホストデータＶ内のある特定ブロックに埋め込むべきｓビットの透かし情報Ｉに対して秘密鍵Ｋによる演算を施して、よりビット長の長いｔビットの透かしデータＸに変換する。ここで、ｓ、ｔは自然数であり、ｔ≧ｓを満たす。暗号化の関数をｆ_０とすると、この処理は変換式Ｘ＝ｆ_０（Ｉ，Ｋ）で表される。また、透かしが埋め込まれるブロックが静止画のように二次元のデータ列として構成され、かつ、そのブロックサイズがＭ×Ｎの場合、t≦Ｍ×Ｎの関係が成り立つ。
【００３４】
変更部１４は、透かしデータＸとホストデータＶを用いて、透かしデータＸをスクランブルし、スクランブルされた透かしデータＸ'を出力する。スクランブルの関数をｆ_２とすると、この処理は変換式Ｘ'＝ｆ_２（Ｘ，Ｖ）で表される。
【００３５】
埋め込みブロック選択部１８は、透かしデータＸを埋め込むべきホストデータＶのブロックを選択する。透かし情報Ｉがブロック識別情報などで構成される場合は、識別情報が示すブロックを選択する。あるいは、ブロックと無関係の情報、もしくは、その情報の一部を透かし情報Ｉとして取り扱う場合には、秘密鍵Ｋを用いて、ランダムに埋め込むブロックを選択する。埋め込み部１６は、秘密鍵Ｋを用いて、埋め込みブロック選択部１８により選択されたホストデータＶのブロックにスクランブルされた透かしデータＸ'を埋め込み、埋め込みホストデータＷを出力する。埋め込みの関数をｆ_１とすると、この処理は変換式Ｗ＝ｆ_１（Ｖ，Ｘ'，Ｋ）で表される。秘密鍵Ｋに依存しない埋め込み方式の場合は、Ｗ＝ｆ_１（Ｖ，Ｘ'）となる。
【００３６】
変更部１４と埋め込み部１６は協同して、複数のスクランブルされた透かしデータＸ'を生成し、それぞれをホストデータＶの選択されたブロックに埋め込み、複数の埋め込みホストデータＷの候補を生成し、それらの候補の一つを選択する機能をもつ。以上の透かし埋め込み処理を、透かしを埋め込むべきホストデータＶの全てのブロックに対して、繰り返し行うことで、各ブロックに独立に透かしが埋め込まれることになる。
【００３７】
図２は変更部１４と埋め込み部１６の機能構成図である。Ｌ個のマルチプレクサ２０は、透かしデータＸの先頭にそれぞれ初期データＣ_０〜Ｃ_Ｌ−１を挿入したＬ種類のビット系列Ｘ_ｂを生成する。Ｌ個のスクランブラ２２はＬ種類のビット系列をそれぞれスクランブルして、Ｌ種類のスクランブルされた透かしデータＸ'_ｂを生成する。Ｌ個のＥＣＣ（Error Correction Code）部２４はＬ種類のスクランブルされた透かしデータＸ'_ｂのそれぞれに誤り訂正のためのパリティを付加した透かしデータＸ'_ｃを生成する。ＥＣＣ部２４は、透かしビットの検出率を向上させるためのオプションであって、アプリケーションによっては必要ない場合もあり、この構成を省略してもよい。また、スクランブラ２２とＥＣＣ部２４の順序を逆にして、Ｌ種類のビット系列に誤り訂正のためのパリティを付加した後に、それらをスクランブルして、Ｌ種類のスクランブルされた透かしデータを生成してもよい。
【００３８】
Ｌ個の埋め込み部２６は、Ｌ種類のスクランブルされた透かしデータＸ'_ｃのそれぞれを、埋め込みブロック選択部１８により選択されたホストデータＶのブロックに埋め込み、Ｌ種類の埋め込みホストデータＷの候補を生成する。Ｌ個のＳＮＲ計算部２８は、Ｌ種類の埋め込みホストデータＷの候補のそれぞれについて、透かしデータＸの耐性を評価する。セレクタ３０は、耐性の評価値が最良である埋め込みホストデータＷの候補を選択し、それを最終的な埋め込みホストデータＷとして出力する。
【００３９】
図３は、実施の形態１に係る復号装置４０の構成を示す。符号化装置１０により電子透かしが埋め込まれた埋め込みホストデータＷは、ネットワーク上で流通し、コンピュータにおいて利用される。その過程で埋め込みホストデータＷは圧縮符号化や改ざんなどの操作を受ける。画像データであれば、ＪＰＥＧ圧縮、フィルタリング、量子化、色補正などの信号処理や、スケーリング、クロッピング、回転、並行移動等の幾何学的な変換など有用性のある操作が施されたり、電子透かしを除去したり改変するなどの不正な攻撃が加えられたりする。そのような操作による変形を埋め込みホストデータＷに対するノイズＮとみなし、ノイズＮが付加した埋め込みホストデータＷを埋め込みホスト信号Ｗ'（＝Ｗ＋Ｎ）とする。復号装置４０は、埋め込みホスト信号Ｗ'から埋め込まれた透かし情報Ｉを抽出する処理を行う。
【００４０】
埋め込みブロック選択部４１は、必要な場合は秘密鍵Ｋを用いて、埋め込みホスト信号Ｗ'から透かしデータの埋め込まれたブロックを選択する。抽出部４２は、秘密鍵Ｋを用いて、埋め込みホスト信号Ｗ'から選択されたブロックに埋め込まれた透かしデータＸ'_ｃを抽出する。ＥＣＣ復号部４４はこの透かしデータＸ'_ｃに付加されているパリティビットを用いて誤り訂正を行い、透かしデータＸ'_ｂを生成する。デスクランブラ４６は秘密鍵Ｋを用いて、誤り訂正後の透かしデータＸ'_ｂのスクランブルを解除し、透かしデータＸ_ｂを出力する。ビット長復元部４８は、秘密鍵Ｋを用いて、この透かしデータＸ_ｂのビット長を復元して元の透かし情報Ｉを出力する。以上の透かし抽出処理を、透かしが埋め込まれたホストデータＶの全てのブロックに対して、繰り返し行うことで、各ブロックから独立に透かしを抽出することができる。また、透かしが正しく抽出できなかったブロックが存在した場合には、そのブロックの改ざんが行われたものと判断することで、ブロック単位による改ざん検出が可能となる。
【００４１】
以上の構成の符号化装置１０および復号装置４０による電子透かしの埋め込みと抽出の手順を説明する。図１１は、符号化装置１０による電子透かしの埋め込み手順を説明するフローチャートである。フローチャートの説明にあたり、図４から図１０を適宜参照する。マルチプレクサ２０は、ビット長伸長部１２によりビット長が伸長された透かしデータＸの先頭にＬ種類の初期データを挿入してＬ個の符号系列を生成し（Ｓ１０）、スクランブラ２２は、それらの符号系列をスクランブルしてＬ種類のスクランブルされた透かしデータＸ'を生成する（Ｓ１２）。
【００４２】
図４は、透かしデータＸとＬ種類のスクランブルされた透かしデータＸ'との関係を示す。ｎビットの透かしデータＸの先頭に、ｒビットの冗長語を識別データＩＤ［０］〜ＩＤ［Ｌ−１］として付加し、Ｌ種類の透かしデータの候補を作成する。最大２^ｒ種類の候補が作成される。これらの候補に含まれる透かしデータＸのビット列はこれから述べるスクランブル方式により、スクランブルされる。
【００４３】
スクランブル方式の一例として、伝送や磁気記録におけるデジタル変調の際に利用されるＧＳ（Guided Scramble）方式を採用する。ＧＳ方式は、ある一定のデータブロック長からなる情報系列に対して、Ｌ種類の符号系列を生成し、これらを次に送信する符号系列の候補として扱う。これらの候補の中から、伝送媒体の性質に合わせて最適なものを選択して最終的な符号系列とする。このＧＳ方式により、多様性に富んだ符号系列の候補を簡単な方法で生成することができる。
【００４４】
符号化装置１０におけるマルチプレクサ２０とスクランブラ２２がＧＳ符号化器内の符号系列の候補生成部として機能する。ＧＳ符号化器は、ｎビットからなる情報系列Ｄ（ｘ）の直前にＬ種類のｒビットの冗長語ｃ_ｉ（ｉ＝０，・・・，Ｌ−１）を付加し、Ｌ種類の符号系列ｃ_ｉｘ^ｎ＋Ｄ（ｘ）を生成する。この符号系列の符号長は（ｎ＋ｒ）ビットとなる。このようにして冗長語が付加された符号系列に対して、次式のようにＮ次元のスクランブル多項式Ｓ（ｘ）で除算することにより商Ｔ_ｉ（ｘ）を求める。
【００４５】
Ｔ_ｉ（ｘ）＝Ｑ_Ｓ（ｘ）［（ｃ_ｉｘ^ｎ＋Ｄ（ｘ））ｘ^Ｎ］（１）
ただし、Ｑ_ａ［ｂ］はｂをａで除算した商を示す。商集合｛Ｔ_０（ｘ），・・・，Ｔ_Ｌ−１（ｘ）｝がスクランブル後の符号系列の候補である。これらの候補の各々について、その符号系列が実際に用いられた際の性能を評価し、その評価値が最良であるものを最終的な符号系列として選択する。
【００４６】
復調時には、復号装置４０におけるデスクランブラ４６がＧＳ復号器として機能し、符号系列にＳ（ｘ）を乗算し、下位Ｎビットと上位ｒビットの変換情報を捨てることにより、元の情報系列Ｄ（ｘ）が得られる。
【００４７】
ここでスクランブル多項式Ｓ（ｘ）として、Ｓ（ｘ）＝ｘ^ｒ＋１を用いた場合を説明する。ｎｍｏｄｒ＝０の場合、（１）式は次式に示す畳み込み演算で表現可能である。
【００４８】
ｔ_ｊ＝ｄ_ｊ（＋）ｃ_ｉ（ｊ＝０）
ｔ_ｊ＝ｄ_ｊ（＋）ｔ_ｊ−１（ｊ＝１，・・・，ｎ／ｒ−１）
ただし、ｉ＝０，・・・，Ｌ−１であり、ｄ_ｊは元の情報系列Ｄ（ｘ）をｒビットずつ区切ったビット列、ｔ_ｊは変換後の符号系列Ｔ_ｉ（ｘ）の先頭のｒビットの冗長語ｃ_ｉ以降をｒビットずつ区切ったビット列である。また（＋）は排他的論理和（ＥＸ−ＯＲ）演算を示す。
【００４９】
図５はこの符号化時の畳み込み演算を説明する図である。たとえば、ｎ＝６、ｒ＝２の場合を考える。元の情報系列Ｄ（ｘ）＝（１，０，１，０，０，１）に対して、冗長語ｃ_０＝（０，０）を付加して、変換後の符号系列Ｔ_０（ｘ）を生成する。上記の符号化時の畳み込み演算により、ｔ_０＝ｄ_０（＋）ｃ_０＝（１，０）（＋）（０，０）＝（１，０）、ｔ_１＝ｄ_１（＋）ｔ_０＝（１，０）（＋）（１，０）＝（０，０）、ｔ_２＝ｄ_２（＋）ｔ_１＝（０，１）（＋）（０，０）＝（０，１）となり、変換後の符号系列Ｔ_０＝（０，０，１，０，０，０，０，１）が得られる。ここで変換後の符号系列Ｔ_０の先頭の２ビットは冗長語ｃ_０であることに注意する。
【００５０】
同様にして、冗長語ｃ_１＝（０，１）、ｃ_２＝（１，０）、ｃ_３＝（１，１）に対して、それぞれ変換後の符号系列Ｔ_１＝（０，１，１，１，０，１，０，０）、Ｔ_２＝（１，０，０，０，１，０，１，１）、Ｔ_３＝（１，１，０，１，１，１，１，０）が得られる。
【００５１】
復号時は次式のように畳み込み演算を行うことにより、元の情報系列Ｄ（ｘ）が得られる。
【００５２】
ｄ_ｊ＝ｔ_ｊ（＋）ｃ_ｉ（ｊ＝０）
ｄ_ｊ＝ｔ_ｊ（＋）ｔ_ｊ−１（ｊ＝１，・・・，ｎ／ｒ−１）
【００５３】
図６はこの復号時の畳み込み演算を説明する図である。前述の例において、変換後の符号化系列Ｔ_０＝（０，０，１，０，０，０，０，１）が与えられると、先頭の２ビットから冗長語ｃ_０＝（０，０）が得られ、上記の復号時の畳み込み演算により、ｄ_０＝ｔ_０（＋）ｃ_０＝（１，０）（＋）（０，０）＝（１，０）、ｄ_１＝ｔ_１（＋）ｔ_０＝（０，０）（＋）（１，０）＝（１，０）、ｄ_２＝ｔ_２（＋）ｔ_１＝（０，１）（＋）（０，０）＝（０，１）となり、元の情報系列Ｄ（ｘ）＝（１，０，１，０，０，１）が得られる。他の変換後の符号化系列Ｔ_１，Ｔ_２，Ｔ_３についてもこの畳み込み演算により、元の情報系列Ｄ（ｘ）が得られる。
【００５４】
再び図１１を参照する。埋め込みブロック選択部１８は、ホストデータＶから透かしデータＸ'を埋め込むべきブロックを選択する（Ｓ１３）。スクランブラ２２によって生成されたＬ種類のスクランブルされた透かしデータＸ'は、ＥＣＣ部２４により誤り訂正のためのパリティを付加された後に、埋め込み部２６によりホストデータＶの選択されたブロックに埋め込まれる（Ｓ１４）。
【００５５】
Ｌ種類のスクランブルされた透かしデータＸ'をｘ^０，ｘ^１，・・・，ｘ^Ｌ−１とする。各透かしデータの候補のビット系列は、次式のように表される。先頭のｒビットは識別データである。また、スクランブル処理後のビット０は、−１に置き換えて、以下の処理を行う。
【００５６】
ｘ^０＝｛−１，・・・，−１，−１，ｘ^０ _０，ｘ^０ _１，・・・，ｘ^０ _ｎ−１｝
ｘ^１＝｛−１，・・・，−１，１，ｘ^１ _０，ｘ^１ _１，・・・，ｘ^１ _ｎ−１｝・・・
ｘ^Ｌ−１＝｛１，・・・，１，１，ｘ^Ｌ−１ _０，ｘ^Ｌ−１ _１，・・・，ｘ^Ｌ−１ _ｎ−１｝
【００５７】
埋め込みブロック選択部１８は、（ｎ＋ｒ）ビットからなる透かしデータの埋め込み対象として、一つのブロックを選択する。さらに、その選択されたブロック内から、サンプル集合のペア（Ｖ^＋，Ｖ⁻）を選択する。埋め込みサンプルの集合Ｖ^＋，Ｖ⁻は、それぞれ次のように（ｎ＋ｒ）個の要素をもつ。
【００５８】
Ｖ^＋＝｛ｖ^＋ _０，ｖ^＋ _１，・・・，ｖ^＋ _{ｎ＋ｒ−１}｝
Ｖ⁻＝｛ｖ⁻ _０，ｖ⁻ _１，・・・，ｖ⁻ _{ｎ＋ｒ−１}｝
ここでサンプルの集合Ｖ^＋，Ｖ⁻の要素であるサブセットｖ^＋ _ｉ、ｖ⁻ _ｉ（ｉ＝０，１，・・・，ｎ＋ｒ−１）は、いずれも同一のブロック内でランダムに選択されたｍ個のサンプルデータからなる。
【００５９】
ｖ^＋ _ｉ＝｛ｖ^＋ _ｉ，０，ｖ^＋ _ｉ，１，・・・，ｖ^＋ _{ｉ，ｍ−１}｝
ｖ⁻ _ｉ＝｛ｖ⁻ _ｉ，０，ｖ⁻ _ｉ，１，・・・，ｖ⁻ _{ｉ，ｍ−１}｝
【００６０】
透かしデータの候補ｘ^ｋ（ｋ＝０，・・・，Ｌ−１）をサンプル集合のペア（Ｖ^＋，Ｖ⁻）に次のように埋め込み、Ｌ種類の埋め込みホストデータの候補Ｗ^ｋを生成する。
【００６１】
ｗ^＋ｋ _ｉ，ｊ＝ｖ^＋ _ｉ，ｊ＋α^＋ _ｉ，ｊ・ｘ^ｋ _ｉ
ｗ^−ｋ _ｉ，ｊ＝ｖ⁻ _ｉ，ｊ−α⁻ _ｉ，ｊ・ｘ^ｋ _ｉ
ここでα^＋ _ｉ，ｊおよびα⁻ _ｉ，ｊは人間の視覚モデルにもとづいて知覚されるノイズを減少するためのスケーリングパラメータであり、いずれも正の値である。あるいは、α^＋ _ｉ，ｊおよびα⁻ _ｉ，ｊは、ある確率分布、たとえばガウシアン分布、一様分布などに従うように、秘密鍵Ｋによって生成される正の値であってもよい。この場合、透かしの埋め込み強度は減少するが、埋め込まれた透かしの秘匿性は向上する。このようにして、ｋ番目の透かしデータの候補の各ビットｘ^ｋ _ｉは各サブセットｖ^＋ _ｉ、ｖ⁻ _ｉのそれぞれｍ個のサンプルに重複して埋め込まれる。重複の数ｍが大きいほど、透かしビットが失われる可能性が低くなり、検出誤差が小さくなる一方で、ホストデータに埋め込むことができる透かしのビット数が減少する。α^＋ _ｉ，ｊおよびα⁻ _ｉ，ｊは、視覚上の劣化を検知できないように各ピクセル毎に設定される値であり、原理的には、埋め込むピクセル数ｍを増やしても、人間の視覚上、画質の劣化は検知されない。しかし、１ビットを埋め込むのに費やすピクセル数が増加するということは、埋め込み領域には制限があるため、埋め込むことができるビット数が減少することを意味し、したがって埋め込み率の低下を招くことになる。
【００６２】
透かしデータの埋め込み対象のブロックの一例として、ホストデータＶを離散コサイン変換（Discrete Cosine Transform）したときに得られるＤＣＴブロックを用いる場合、各サブセットｖ^＋ _ｉ、ｖ⁻ _ｉのｍ個のサンプルデータは、透かしの埋め込み対象として選択された１つのＤＣＴブロックに含まれるｍ個のＤＣＴ係数である。図７は、埋め込みブロック選択部１８により選択される透かしデータＸ'の埋め込みブロックを説明する図である。同図のように、ＪＰＥＧで用いられている離散コサイン変換では、ホストデータＶの空間領域が縦横８ピクセルからなるブロックに分割され、それぞれのブロック内で各ピクセルが空間周波数成分に変換される。埋め込みブロック選択部１８は、透かしビット列ｘ^ｋを埋め込むブロックとして、同図のようにＤＣＴブロック１２０を選択する。
【００６３】
図８は、８×８のＤＣＴブロック内の２ｍ個のＤＣＴ係数に透かしビットｘ^ｋ _ｉ（ｉ＝０，１，・・・，ｎ＋ｒ−１）が埋め込まれる様子を示している。各サブセットｖ^＋ _ｉ、ｖ⁻ _ｉとして選ばれるそれぞれｍ個のＤＣＴ係数は、秘密鍵Ｋに基づいて選択される。このようにして（ｎ＋ｒ）ビットの透かしデータが同一のブロックに埋め込まれる。なお、上記の説明では透かし埋め込み対象のブロックとして１つのＤＣＴブロックを選択したが、埋め込み対象のブロックを、離散コサイン変換の最小処理単位であるＤＣＴブロックとする必要はなく、ある程度の大きさをもった分割領域であってもよい。その場合は、いくつかのＤＣＴブロックの集合を１つの埋め込み対象ブロックとみなして、同様の透かし埋め込み処理を行えばよい。
【００６４】
透かしデータの埋め込み対象のブロックの他の例として、ホストデータＶを離散ウェーブレット変換したときに得られるウェーブレット変換係数の集合を考える。図９は、離散ウェーブレット変換されたホストデータＶの各サブバンドから選択された、同一の空間領域を構成するウェーブレット変換係数の集合を説明する図である。同図に示すとおり、ホストデータＶは離散ウェーブレット変換により４つの周波数サブバンドへ分割される。これらのサブバンドは、縦横両方向において低周波成分を有するＬＬサブバンドと、縦横のいずれかひとつの方向において低周波成分を有し、かつもう一方の方向において高周波成分を有するＨＬおよびＬＨサブバンドと、縦横両方向において高周波成分を有するＨＨサブバンドである。各サブバンドの縦横のピクセル数は処理前のホストデータＶのそれぞれ１／２であり、一回のフィルタリングでサイズが１／４のサブバンドデータが得られる。
【００６５】
こうして得られたサブバンドのうち、ＬＬサブバンドに対して離散ウェーブレット変換によるフィルタリング処理が再度施され、さらにＬＬ、ＨＬ、ＬＨ、ＨＨの４つのサブバンドに分割される。このフィルタリングは所定の回数行われ、最後のフィルタリングで生じたＬＬサブバンドがホストデータＶのＤＣ成分に最も近いデータとなる。
【００６６】
離散ウェーブレット変換前のホストデータＶの特定の空間領域に対応するウェーブレット変換係数を各階層のサブバンドから選択すると、図９に示すように、ツリー構造のウェーブレット変換係数の集合１００〜１０９が得られる。すなわち第３階層のＬＬサブバンドＬＬ_３、ＨＬサブバンドＨＬ_３、ＬＨサブバンドＬＨ_３、およびＨＨサブバンドＨＨ_３からはそれぞれ１ピクセルからなるウェーブレット変換係数１００、１０１、１０２、および１０３が選択され、第２階層のＨＬサブバンドＨＬ_２、ＬＨサブバンドＬＨ_２およびＨＨサブバンドＨＨ_２からはそれぞれ２×２のウェーブレット変換係数１０４、１０５および１０６が選択され、最後に第１階層のＨＬサブバンドＨＬ_１、ＬＨサブバンドＬＨ_１およびＨＨサブバンドＨＨ_１からはそれぞれ４×４のウェーブレット変換係数１０７、１０８および１０９が選択される。これらのウェーブレット変換係数の集合は、離散ウェーブレット変換前のホストデータＶにおける特定の空間領域のデータが階層的に空間周波数成分に変換されたものである。したがって、これらのウェーブレット変換係数の集合を透かしデータＸ'の埋め込みブロックとして選択して透かしデータＸ'を埋め込むなら、透かしデータＸ'はホストデータＶの特定の空間領域に埋め込まれたことになる。各サブセットｖ^＋ _ｉ、ｖ⁻ _ｉとしてこのようなツリー構造のウェーブレット変換係数の集合を用いてもよい。
【００６７】
図１０は、ウェーブレット変換係数の集合内の２ｍ個のウェーブレット変換係数に透かしビットｘ^ｋ _ｉが埋め込まれる様子を示している。図９の３つの階層から選択されたウェーブレット変換係数を集めると、図１０のように８×８のウェーブレット変換係数の集合１１０が得られる。ウェーブレット変換の階層数をＨとすると、２^Ｈ×２^Ｈのウェーブレット変換係数のマトリックスが得られる。もっともこれは、最小サイズの埋め込みブロックを説明したものであり、ホストデータＶの透かし埋め込み領域として、ある程度の大きさをもった分割領域を選択すると、その領域に対応するウェーブレット変換係数のマトリックスのサイズは当然大きくなる。こうして得られるウェーブレット変換係数のマトリックスを埋め込みブロックとして扱い、この埋め込みブロック内のｍ個のウェーブレット変換係数に透かしビットｘ^ｋ _ｉ（ｉ＝０，１，・・・，ｎ＋ｒ−１）を図８と同様の方法で埋め込む。
【００６８】
図１１に戻り、ＳＮＲ計算部２８は、Ｌ種類の埋め込みホストデータの候補Ｗ^ｋに対して透かしデータｘ^ｋの耐性、すなわち埋め込み強度を評価し（Ｓ１６）、セレクタ３０は埋め込み強度が最大となる埋め込みホストデータの候補Ｗ^ｋを最終的な埋め込みホストデータＷとして選択する（Ｓ１８）。
【００６９】
埋め込み強度の評価式を与える前に、埋め込みホストデータＷに対して信号処理や画像処理などにより変形が加えられた場合に、透かしデータＸ'がどのように検出されるかを検討する。埋め込みホストデータＷに加えられる変形をノイズＮとして扱い、ノイズＮが加わった埋め込みホストデータＷを埋め込みホスト信号Ｗ'と呼ぶ。この埋め込みホスト信号Ｗ'から透かしデータＸ'を抽出する方法を説明する。埋め込みホスト信号の集合のペア（Ｗ'^＋，Ｗ'⁻）を次のように定義する。埋め込みホスト信号の集合Ｗ'^＋，Ｗ'⁻は次のようにそれぞれ（ｎ＋ｒ）個の要素をもつ。
【００７０】
Ｗ'^＋＝｛ｗ'^＋ _０，ｗ'^＋ _１，・・・，ｗ'^＋ _{ｎ＋ｒ−１}｝
Ｗ'⁻＝｛ｗ'⁻ _０，ｗ'⁻ _１，・・・，ｗ'⁻ _{ｎ＋ｒ−１}｝
ここで埋め込みホスト信号の集合Ｗ'^＋，Ｗ'⁻の要素である各サブセットｗ'^＋ _ｉ、ｗ'⁻ _ｉは、電子透かしの埋め込み位置に対応して、次のように埋め込みホスト信号Ｗ'のｍ個のサンプルデータからなる。
ｗ'^＋ _ｉ＝｛ｗ'^＋ _ｉ，０，ｗ'^＋ _ｉ，１，・・・，ｗ'^＋ _{ｉ，ｍ−１}｝
ｗ'⁻ _ｉ＝｛ｗ'⁻ _ｉ，０，ｗ'⁻ _ｉ，１，・・・，ｗ'⁻ _{ｉ，ｍ−１}｝
【００７１】
透かしビットｘ^ｋ _ｉを検出するために、次の判定値ｚ_ｉを計算する。
ｚ_ｉ＝Σ_ｊ＝０ ^ｍ−１（ｗ'^＋ _ｉ，ｊ−ｗ'⁻ _ｉ，ｊ）
＝Σ_ｊ＝０ ^ｍ−１［（ｗ^＋ _ｉ，ｊ＋ｎ^＋ _ｉ，ｊ）−（ｗ⁻ _ｉ，ｊ＋ｎ⁻ _ｉ，ｊ）］
＝Σ_ｊ＝０ ^ｍ−１［（ｖ^＋ _ｉ，ｊ−ｖ⁻ _ｉ，ｊ）＋（α^＋ _ｉ，ｊ＋α⁻ _ｉ，ｊ）・ｘ^ｋ _ｉ＋（ｎ^＋ _ｉ，ｊ−ｎ⁻ _ｉ，ｊ）］
ここでΣ_ｊ＝０ ^ｍ−１（ｖ^＋ _ｉ，ｊ−ｖ⁻ _ｉ，ｊ）はｍが十分に大きいとき、一般にガウス分布に従い、０に近づく。またノイズの項Σ_ｊ＝０ ^ｍ−１（ｎ^＋ _ｉ，ｊ−ｎ⁻ _ｉ，ｊ）についても同様に０に近づく。したがって、ｚ_ｉはΣ_ｊ＝０ ^ｍ−１［（α^＋ _ｉ，ｊ＋α⁻ _ｉ，ｊ）・ｘ^ｋ _ｉ］の値で近似できる。（α^＋ _ｉ，ｊ＋α⁻ _ｉ，ｊ）は正であるから、透かしビットｘ^ｋ _ｉが１ならばｚ_ｉは正であり、透かしビットｘ^ｋ _ｉが−１ならばｚ_ｉは負である。したがってｚ_ｉの正負により透かしビットｘ^ｋ _ｉの値を判定することができる。
【００７２】
埋め込み強度の評価は、ホストデータＶを透かしデータＸに対するノイズとみなして、埋め込まれた透かしデータｘ^ｋに対して検出される透かしデータの分散を計算することにより行われる。分散が小さいほど、耐性が強いと考えることができる。埋め込みホストデータの候補のペア（Ｗ^＋ｋ，Ｗ^−ｋ）に対して次式によりＳＮ比を評価して、最適な候補Ｋを選択する。
【００７３】
Ｋ＝ａｒｇｍａｘ_ｋ（Ｐ_ｋ／（２σ_ｋ ^２））
Ｐ_ｋ＝Σ_ｉ＝０ ^{ｎ＋ｒ−１}｜Σ_ｊ＝０ ^ｍ−１（ｗ^＋ｋ _ｉ，ｊ−ｗ^−ｋ _ｉ，ｊ）｜^２／（ｎ＋ｒ）
σ_ｋ ^２＝Σ_ｉ＝０ ^{ｎ＋ｒ−１}｜Σ_ｊ＝０ ^ｍ−１（ｗ^＋ｋ _ｉ，ｊ−ｗ^−ｋ _ｉ，ｊ）−Ｐ_ｋ ^１／２・ｘ^ｋ _ｉ｜^２／（ｎ＋ｒ）
【００７４】
透かしビットｘ^ｋ _ｉが｛１，−１｝のいずれであるかを判定するための前述の判定値ｚ_ｉは、埋め込みホストデータＷにノイズが付加される前の状態では、ｚ_ｉ＝Σ_ｊ＝０ ^ｍ−１（ｗ^＋ｋ _ｉ，ｊ−ｗ^−ｋ _ｉ，ｊ）で与えられることを考慮すると、分散σ_ｋ ^２は、透かしビットに関する検出値ｚ_ｉと実際に埋め込まれた透かしビットの平均値Ｐ_ｋ ^１／２・ｘ^ｋ _ｉとの差の自乗をｉ＝０，・・・，ｎ＋ｒ−１について評価して平均化したものであると言える。ただし、Ｐ_ｋは検出値ｚ_ｉのｉ＝０，・・・，ｎ＋ｒ−１についての自乗平均であり、埋め込まれた透かしの平均パワーを示す。したがって、埋め込まれた透かしデータｘ^ｋと抽出される透かしデータとの間のユークリッド距離が小さく、透かしビットを検出するための判定値の絶対値が大きいほど、Ｐ_ｋ／（２σ_ｋ ^２）の値は大きくなる。言い換えれば、Ｐ_ｋ／（２σ_ｋ ^２）が最大となる候補を選択することは、透かしビットの検出誤差が最小である候補を選択することを意味する。
【００７５】
判定値ｚ_ｉについて、ｖ^＋ _ｉ，ｊ＞ｖ^＋ _ｉ，ｊかつｘ^ｋ _ｉ＝１ならばｚ_ｉ＞＞０となり、ｖ^＋ _ｉ，ｊ＜ｖ^＋ _ｉ，ｊかつｘ^ｋ _ｉ＝−１ならばｚ_ｉ＜＜０となる。したがって前述の評価により最適な透かしデータｘ^ｋの候補を選択することは、判定値ｚ_ｉによる透かしビットｘ^ｋ _ｉの検出性能を向上させるために、ｖ^＋ _ｉ，ｊ＞ｖ^＋ _ｉ，ｊならばｘ'_ｉ＝１となり、ｖ^＋ _ｉ，ｊ＜ｖ^＋ _ｉ，ｊならばｘ'_ｉ＝−１となるように、元の透かしビットｘ_ｉをｘ'_ｉに変更することを意味する。これがＧＳ方式のガイディングルールであり、これにより判定値ｚ_ｉのレスポンスが改善する。
【００７６】
復号装置４０の抽出部４２は、ノイズの付加された埋め込みホスト信号Ｗ'を受け取ると、ＥＣＣ復号部４４が硬入力の復号器で構成される場合には、判定値ｚ_ｉを次のように計算し、判定値ｚ_ｉの正負で、透かしビットｘ'が｛−１，１｝のいずれであるかを判定し、透かしデータＸ'を得る。また、ＥＣＣ復号部４４が軟入力の復号器で構成される場合には、判定値ｚ_ｉを｛−１，１｝に硬判定することなく、そのまま、ＥＣＣ復号部４４に送る。
【００７７】
ｚ_ｉ＝Σ_ｊ＝０ ^ｍ−１（ｗ'^＋ _ｉ，ｊ−ｗ'⁻ _ｉ，ｊ）
＝Σ_ｊ＝０ ^ｍ−１［（ｗ^＋ _ｉ，ｊ＋ｎ^＋ _ｉ，ｊ）−（ｗ⁻ _ｉ，ｊ＋ｎ⁻ _ｉ，ｊ）］
＝Σ_ｊ＝０ ^ｍ−１［（ｖ^＋ _ｉ，ｊ−ｖ⁻ _ｉ，ｊ）＋（α^＋ _ｉ，ｊ＋α⁻ _ｉ，ｊ）・ｘ'_ｉ＋（ｎ^＋ _ｉ，ｊ−ｎ⁻ _ｉ，ｊ）］
【００７８】
抽出された透かしデータＸ'はさらにＥＣＣ復号部４４により誤り訂正がなされ、デスクランブラ４６によりスクランブルを解除され、元の透かしデータＸが得られる。
【００７９】
以上述べたように、実施の形態によれば、ＧＳ方式を用いて、電子透かしを埋め込む画像や音声などのメディアデータが与えられると、透かしビット系列をそのメディアデータに埋め込みやすいビット系列に変換した上で埋め込むことができる。したがって信号処理、幾何変換、圧縮、データの改ざんなどに対する電子透かしの耐性を強化することができ、透かしの検出精度が大幅に改善する。また透かしビットの埋め込み対象として特定のブロックを選択し、ブロックごとに独立に、透かしビットを埋め込むため、ブロックごとに透かしの検出を行うことで、ブロック単位で改ざんの有無を調べることができる。したがって、画像の特定の部分を変更したり、オブジェクトを新たに追加するなどの改ざんが行われた箇所をブロック単位で検出可能となる。
【００８０】
上記の実施の形態では、図２で示したように、Ｌ種類の透かしデータの候補を生成するために、Ｌ個のマルチプレクサ２０、スクランブラ２２、ＥＣＣ部２４、埋め込み部２６、およびＳＮＲ計算部２８が並列に設けられたが、これらの部材を単一構成にして、Ｌ種類の透かしデータの候補を逐次的に生成、評価して最適な候補を選択してもよい。
【００８１】
図１２は、そのような逐次型の電子透かしの埋め込み手順を説明するフローチャートである。埋め込みブロック選択部１８は、ホストデータＶから透かしデータを埋め込むべきブロックをあらかじめ選択する（Ｓ１９）。変数ｉを１に初期化する（Ｓ２０）。マルチプレクサ２０は、暗号化部１２により暗号化された透かしデータＸの先頭にｉ番目の初期データを挿入して符号系列を生成し（Ｓ２２）、スクランブラ２２は、その符号系列をスクランブルして、ｉ番目のスクランブルされた透かしデータＸ'を生成する（Ｓ２４）。スクランブラ２２によって生成されたｉ番目のスクランブルされた透かしデータＸ'は、必要に応じてＥＣＣ部２４により誤り訂正のためのパリティを付加された後に、埋め込み部２６によりホストデータＶの選択されたブロックに埋め込まれる（Ｓ２６）。ＳＮＲ計算部２８は、ｉ番目の埋め込みホストデータの候補Ｗ^ｉに対して透かしデータｘ^ｉの耐性、すなわち埋め込み強度Ｓ_ｉを評価する（Ｓ２８）。セレクタ３０は、埋め込み強度Ｓ_ｉが最低の評価値を保証する基準値Ｔより大きいかどうかを判定する（Ｓ３０）。もし埋め込み強度Ｓ_ｉが基準値Ｔより大きければ（Ｓ３０のＹ）、変数Ｋに現在の変数ｉの値を代入し（Ｓ３２）、Ｋ番目の埋め込みホストデータの候補を最終的な埋め込みホストデータＷとして選択する（Ｓ４０）。埋め込み強度Ｓ_ｉが基準値Ｔ以下の場合（Ｓ３０のＮ）、現在の変数ｉの値がＬに等しいなら（Ｓ３４のＹ）、これまで調べた埋め込み強度Ｓ_ｋの値が最大となる添え字ｋを変数Ｋに代入し（Ｓ３８）、Ｋ番目の埋め込みホストデータの候補を最終的な埋め込みホストデータＷとして選択する（Ｓ４０）。現在の変数ｉの値がＬより小さいなら（Ｓ３４のＮ）、変数ｉを１だけインクリメントして（Ｓ３６）、ステップＳ２２に戻る。
【００８２】
この繰り返し処理により、埋め込み強度が所望の基準値以上である候補が得られた時点で、その候補を最終的な埋め込みホストデータＷとして選択し、そのような候補が生成されなければ、Ｌ個の埋め込みホストデータの候補を生成して、その中から埋め込み強度が最大であるものを最終的な埋め込みホストデータＷとして選択することができる。
【００８３】
上記の説明では、埋め込みブロック選択部１８は、透かしビット列ｘ^ｋを埋め込むブロックとして１つのブロックを選択した。しかしながら選択されたブロックが背景画像や単調な画像である場合には、高周波成分が少なく透かしデータの埋め込みが困難である場合もある。そこで埋め込みブロック選択部１８は、透かしビット列ｘ^ｋの埋め込み対象として、２つ以上のブロックを組み合わせて選択してもよい。この場合、２つ以上のブロックに透かしビット列ｘ^ｋが埋め込まれるため、組み合わせのブロックのいずれかで改ざんが行われたかどうかを検出することができるが、いずれのブロックであるかは特定できない。
【００８４】
図１３は、離散コサイン変換されたホストデータＶから選択された２つのＤＣＴブロック１２０および１３０を示す。たとえば一方のＤＣＴブロック１２０は透かしデータが埋め込み難い低周波成分を主に含み、他方のＤＣＴブロック１３０は透かしデータを埋め込み易い高周波成分を主に含むといった組み合わせを選択する。ＤＣＴブロックに含まれる周波数成分はＤＣＴ係数をもとに判断してもよく、またＤＣＴブロック内のピクセル値の分散に基づいて判断してもよい。また、隣接するブロックは互いに似た周波数成分をもつことが多いため、位置がなるべく離れたブロックを組み合わせてもよい。またこのような組み合わせブロックはランダムに選択されてもよい。ブロックの組み合わせを透かしデータの埋め込み単位とすることにより、ブロック間での埋め込み強度の違いを吸収して、埋め込み強度の平均化を図ることができる。
【００８５】
図１４は、離散ウェーブレット変換されたホストデータＶから選択された２つのウェーブレット変換係数の集合を示す。図９で説明した離散ウェーブレット変換前のホストデータＶの特定の空間領域に対応するウェーブレット変換係数の集合１００〜１０９の他に、ホストデータＶの別の特定の空間領域に対応するウェーブレット変換係数の集合２００〜２０９が図１４に斜線を付けて示されている。これら２つのウェーブレット変換係数の集合は、図１３のＤＣＴブロックの組み合わせと同様、たとえば低周波成分を多く含む空間領域と高周波成分を多く含む空間領域にそれぞれ対応している。
【００８６】
図１３および図１４で説明した埋め込みブロックの組み合わせは、秘密鍵Ｋに基づいて決定されるため、復号装置４０の埋め込みブロック選択部４１は、秘密鍵Ｋを用いて、透かしデータＸ'が埋め込まれたブロックを選択することができる。すなわち秘密鍵Ｋにより、復号装置４０は、符号化装置１０が埋め込んだブロックの組み合わせと同一のブロックの組み合わせを特定することが可能である。
【００８７】
さらに別のブロックの組み合わせ方法として、埋め込みブロック選択部１８は、何らかの特徴量にもとづいて互いに異なる特徴をもつブロックを選択して組み合わせてもよい。たとえばピクセル値の分散などの特徴量を評価して、物体の表面のようなテクスチャタイプのブロックと、背景のようにフラットなタイプのブロックとを組み合わせてもよい。
【００８８】
このように特徴量にもとづいて組み合わせブロックを選択した場合、復号装置４０の埋め込みブロック選択部４１において、同様の特徴量を評価して埋め込みブロックを正しく選択することは難しくなる。なぜなら、改ざんによりこのような特徴量は一般に変化するからである。このように特徴量にもとづいて組み合わせブロックを選択した場合、埋め込みブロックを特定するための情報を秘密鍵として復号装置４０に送信することで対処することができる。あるいは復号装置４０の埋め込みブロック選択部４１が特徴量にもとづいて埋め込みブロックを決定することにして、多くのブロックにおいて透かしデータが正しく抽出できなかった場合には、改ざんがあったと判定することにしてもよい。もっとも、この場合にはブロック単位で改ざんを検出することはできず、単に改ざんの有無を検出することができるだけになる。
【００８９】
実施の形態２
図１５は実施の形態２に係る符号化装置１１の構成を示す。本実施の形態では、電子透かしの埋め込まれたホストデータＶが受ける圧縮符号化などの特定の処理をあらかじめ想定し、透かしの埋め込み時にその特定の処理による影響を考慮して、電子透かしに耐性をもたせる。実施の形態１と共通する構成については同一符号を付して説明を省き、実施の形態１とは異なる構成と動作について説明する。
【００９０】
変更部１５は、透かしデータＸをスクランブルする際、ホストデータＶが受ける特定の処理による歪みＤを考慮して耐性の強い透かしデータのビット系列を選択し、スクランブルされた透かしデータＸ'を出力する。図１６は変更部１５と埋め込み部１６の機能構成図である。重みつきＳＮＲ計算部２９は、Ｌ種類のスクランブルされた透かしデータＸ'_ｃが埋め込まれたホストデータＷの候補について、透かしデータＸの耐性を評価する際に、特定の処理により想定される歪みＤを考慮に入れる。具体的には、埋め込まれた透かしデータと検出される透かしデータとの間のＳＮＲにより埋め込み強度を評価する際に、埋め込みホストデータＷに対する特定の処理による劣化を考慮した以下の重み付けＳＮＲを用いる。
【００９１】
Ｋ＝ａｒｇｍａｘ_ｋ（Ｐ_ｋ／（２σ_ｋ ^２））
Ｐ_ｋ＝Σ_ｉ＝０ ^{ｎ＋ｒ−１}｜Σ_ｊ＝０ ^ｍ−１（ｗ^＊＋ｋ _ｉ，ｊ−ｗ^＊−ｋ _ｉ，ｊ）｜^２／（ｎ＋ｒ）
σ_ｋ ^２＝Σ_ｉ＝０ ^{ｎ＋ｒ−１}｜Σ_ｊ＝０ ^ｍ−１（ｗ^＊＋ｋ _ｉ，ｊ−ｗ^＊−ｋ _ｉ，ｊ）−Ｐ_ｋ ^１／２・ｘ^ｋ _ｉ｜^２／（ｎ＋ｒ）
ここでｗ^＊＋ｋ _ｉ，ｊ、ｗ^＊−ｋ _ｉ，ｊは特定の処理がなされた後の埋め込みホストデータＷである。特定の処理がたとえばＪＰＥＧ２０００による圧縮であると分かっている場合、ｗ^＊＋ｋ _ｉ，ｊ、ｗ^＊−ｋ _ｉ，ｊはＪＰＥＧ２０００の量子化方法を用いて計算することができる。
【００９２】
ＪＰＥＧ２０００の規格書「ISO/IEC 15444-1: JPEG 2000 image coding system, JPEG 2000 final committee draft, 18 August 2000」にもとづいて、ＪＰＥＧ２０００の量子化方法を簡単に説明する。サブバンドｂにおける量子化前のウェーブレット変換係数をａ_ｂ（ｕ，ｖ）、サブバンドｂにおける量子化後のウェーブレット変換係数をｑ_ｂ（ｕ，ｖ）とすると、ＪＰＥＧ２０００では以下の量子化式を用いてウェーブレット変換係数の量子化が行われる。
【００９３】
ｑ_ｂ（ｕ，ｖ）＝ｓｉｇｎ（ａ_ｂ（ｕ，ｖ））・［｜ａ_ｂ（ｕ，ｖ）｜／Δｂ］
ここで［ｘ］はｘを越えない最大の整数を表す。Δｂはサブバンドｂにおける量子化ステップであり、次式で与えられる。
Δｂ＝２＾（Ｒ_ｂ−ε_ｂ）・（１＋μ_ｂ／２^１１）
ここでＲ_ｂはサブバンドｂにおけるダイナミックレンジ、ε_ｂはサブバンドｂにおける量子化の指数、μ_ｂはサブバンドｂにおける量子化の仮数である。
【００９４】
このようにＪＰＥＧ２０００では、同一のサブバンドに属するウェーブレット変換係数は同じ量子化ステップで除算され、整数の値に丸められる。ホストデータＶに埋め込まれる透かしデータＸはこのような量子化演算に対して耐性をもつ必要があるため、ＪＰＥＧ２０００による量子化がなされた後の埋め込みホストデータＷの値を算出して、上述のようにその算出されたホストデータＷに対して透かしデータの耐性を評価する。
【００９５】
本実施の形態によれば、透かしの埋め込み時に、埋め込み後のホストデータに対する特定の処理を想定して埋め込み強度を評価し、埋め込み強度の高い透かしデータのビット系列を選択するため、特定の処理に対する耐性の強い電子透かし埋め込みデータを生成することができる。
【００９６】
実施の形態３
図１７は、実施の形態３に係る符号化装置５０の構成を示す。この符号化装置５０は、透かしデータＸをホストデータＶの複数の埋め込み位置の候補に埋め込み、透かしの耐性が強くなる候補を選択して、最終的な埋め込みホストデータＷとして出力する。実施の形態１と共通する構成については同一符号を付して説明を省き、実施の形態１とは異なる構成と動作について説明する。
【００９７】
埋め込みブロック選択部５６は、秘密鍵Ｋを用いてホストデータＶからＱ個のブロックを選択する。各ブロックのサイズがＭ×Ｎであれば、Ｑ×Ｍ×Ｎサンプルの埋め込み候補が得られる。実施の形態１のＤＣＴ係数に透かしを埋め込む例では、Ｑ＝１、Ｍ＝８、Ｎ＝８と限定した場合について説明を行ったが、本実施の形態では、これらのパラメータを特定することなく説明を行う。位置検出部５２は、このＱ×Ｍ×Ｎサンプルの埋め込み候補の中からスクランブルされた埋め込み位置Ｐを生成し、埋め込み部５４は、秘密鍵Ｋを用いて、ホストデータＶの埋め込み位置Ｐに透かしデータＸを埋め込み、埋め込みホストデータＷを出力する。位置検出部５２と埋め込み部５４は協同して、複数の埋め込み位置Ｐを生成し、それぞれの埋め込み位置Ｐに透かしデータＸを埋め込み、複数の埋め込みホストデータＷの候補を生成し、それらの候補の一つを選択する機能をもつ。
【００９８】
図１８は位置検出部５２と埋め込み部５４の機能構成図である。ＥＣＣ部２４は透かしデータＸ_ｂに誤り訂正のためのパリティを付加した透かしデータＸ_ｃを生成する。位置情報生成部６０は、埋め込みブロック選択部５６によりホストデータＶから選択されたＱ個のブロックについてＬ個の埋め込み位置Ｐの候補を生成する。位置情報生成部６０は、初期埋め込み位置Ｐ^＊に対して、Ｌ種類の初期データＣ_０〜Ｃ_Ｌ−１を与えて、実施の形態１に述べたＧＳ方式により、初期埋め込み位置Ｐ^＊をスクランブルすることで、Ｌ個のスクランブルされた埋め込み位置Ｐの候補を生成する。
【００９９】
埋め込み部２６はＬ個の埋め込み位置Ｐの候補のそれぞれに透かしデータＸ_ｃを埋め込み、Ｌ種類の埋め込みホストデータＷの候補を生成する。ＳＮＲ計算部２８により、Ｌ種類の埋め込みホストデータＷの候補のそれぞれについて透かしデータＸの耐性が評価され、耐性の評価値が最良である埋め込みホストデータＷがセレクタ３０から出力される。このようにして、埋め込みブロック選択部５６により選択されたＱ個の埋め込みブロックに、透かしデータＸを埋め込む際の最適な埋め込み位置が決定される。
【０１００】
図１９は、実施の形態３に係る復号装置７０の構成を示す。この復号装置は、埋め込みホスト信号Ｗ'から埋め込まれた透かしデータＸ_ｃを抽出し、この透かしデータＸ_ｃに対して誤り復号し、誤り訂正がなされた透かしデータＸ_ｂを得る処理を行う。
【０１０１】
埋め込みブロック選択部６１は、秘密鍵Ｋを用いて、埋め込みホスト信号Ｗ'から透かしデータの埋め込まれたＱ個のブロックを選択する。位置情報生成部６０は、図１８に示した符号化装置５０における位置情報生成部６０と同様に、埋め込みブロック選択部６１により選択されたＱ個のブロックについてＬ個の埋め込み位置Ｐの候補を生成する。Ｌ個の抽出部４２は、秘密鍵Ｋを用いて、位置情報生成部６０により与えられたＬ個の埋め込み位置Ｐの候補から、埋め込みホスト信号Ｗ'に埋め込まれたＬ種類の透かしデータＸ_ｃの候補を抽出する。Ｌ個の埋め込み位置Ｐの候補の内、一つの候補が正しい埋め込み位置である。整合フィルタ６２は、Ｌ種類の透かしデータＸ_ｃの候補と、想定される透かしデータＹとの間で相関を計算し、マッチングをとる。セレクタ６４が相関の最も高い透かしデータＸ_ｃの候補を選択することで、正しい埋め込み位置にある透かしデータＸ_ｃが得られる。
【０１０２】
さらに透かしデータＸ_ｃは、ＥＣＣ復号部４４により誤り訂正がなされる。ビット長復元部４８は、秘密鍵Ｋを用いて、この透かしデータＸ_ｂのビット長を復元して元の透かし情報Ｉを出力する。
【０１０３】
想定される透かしデータＹは、ホストデータＶに埋め込まれた透かしデータＸがあらかじめわかっている場合に与えられる。たとえば、ホストデータＶの作成者があらかじめわかっており、その作成者の透かしデータＸがホストデータＶに埋め込まれているかどうかを確認する場合がある。一般に、本実施の形態は、埋め込まれている電子透かし情報があらかじめ想定されているが、透かしデータの埋め込み位置が候補としてしか与えられていない場合に適用することができる。
【０１０４】
本実施の形態によれば、電子透かしを埋め込む対象となるメディアデータが与えられると、そのメディアデータに応じて、透かしデータを埋め込み易い位置を検出して、透かしデータを埋め込むことができ、埋め込まれる透かしの耐性を強化することができる。
【０１０５】
実施の形態４
図２０は実施の形態４に係る符号化装置１０の構成を示す。本実施の形態では、ホストデータＶから生成されるダイジェストデータを電子透かしとしてホストデータＶに埋め込む。実施の形態１の符号化装置１０と共通する構成については同一符号を付して説明を省き、実施の形態１とは異なる構成と動作について説明する。
【０１０６】
ダイジェスト生成部１３は、埋め込みブロック選択部１８により選択されたホストデータＶのブロックの特徴を端的に表したダイジェストデータを生成する。このダイジェストデータは、ホストデータＶの圧縮符号化によっても壊れないデータであり、たとえばホストデータＶが画像である場合は、画像を空間周波数成分に変換したときの低周波成分から得られる。ダイジェスト生成部１３は、一方向性関数によりダイジェストデータをハッシングする。セキュリティを高めたい場合は、ダイジェスト生成部１３は、さらに、ダイジェストデータを秘密鍵Ｋにより暗号化する。ダイジェスト生成部１３はこうして得られるダイジェストデータを透かしデータＸとして出力する。実施の形態１と同様に、変更部１４は、透かしデータＸをスクランブルし、スクランブルされた透かしデータＸ'を出力し、埋め込み部１６は、秘密鍵Ｋを用いて、埋め込みブロック選択部１８により選択されたホストデータＶのブロックにスクランブルされた透かしデータＸ'を埋め込み、埋め込みホストデータＷを出力する。
【０１０７】
図２１は変更部１４と埋め込み部１６の機能構成図である。埋め込みブロック選択部１８により選択されるホストデータＶのブロックがダイジェスト生成部１３に入力されて、ダイジェスト生成部１３によりダイジェストデータが生成され、透かしデータＸが出力される。この透かしデータＸが実施の形態１と同様にスクランブルされてホストデータＶのブロックに埋め込まれ、埋め込みホストデータＷが出力される。ＳＮＲ計算部２８による透かしデータＸの埋め込み強度の評価は、実施の形態２で説明した、ＪＰＥＧ２０００などの圧縮符号化を想定した評価方法を用いる。
【０１０８】
図２２は実施の形態４に係る復号装置４０の構成を示す。実施の形態１の復号装置４０とは異なる構成と動作について説明する。ダイジェスト生成部４３は、埋め込みブロック選択部４１により選択された埋め込みホスト信号Ｗ'のブロックからダイジェストデータを生成し、一方向性関数によりダイジェストデータをハッシングする。さらに、符号化装置１０のダイジェスト生成部１３において、秘密鍵Ｋにより埋め込みデータの暗号化がなされている場合は、ダイジェスト生成部４３は、さらに、ダイジェストデータを秘密鍵Ｋにより暗号化する。ダイジェスト生成部１３はこうして得られるダイジェストデータを比較部４９に与える。
【０１０９】
第１の実施の形態と同様に、抽出部４２は、秘密鍵Ｋを用いて、埋め込みブロック選択部４１により選択された埋め込みホスト信号Ｗ'のブロックに埋め込まれた透かしデータＸ'_ｃを抽出する。ＥＣＣ復号部４４はこの透かしデータＸ'_ｃに付加されているパリティビットを用いて誤り訂正を行い、透かしデータＸ'_ｂを生成する。デスクランブラ４６は秘密鍵Ｋを用いて、誤り訂正後の透かしデータＸ'_ｂのスクランブルを解除し、透かしデータＸ_ｂを出力する。こうして得られた透かしデータＸ_ｂは、ハッシングされたダイジェストデータである。
【０１１０】
比較部４９は、ダイジェスト生成部４３により生成されたダイジェストデータを、抽出部４２以降の処理により透かしとして抽出されたダイジェストデータと照合することにより、改ざんの有無を判定し、判定結果を出力する。透かしとして埋め込まれたダイジェストデータは、埋め込みブロック選択部４１により選択されるブロックから作られたものであり、照合されるダイジェストデータに不一致があることは、その選択されたブロックに改ざんがあったことを意味するから、改ざんの有無とともに改ざんのあったブロックを特定することもできる。このようにダイジェストデータを生成するブロックをはじめから決めておくことで、改ざんの有無とともに改ざんの行われたおおまかな位置を特定することができるようになる。
【０１１１】
本実施の形態では、ダイジェスト生成部４３においてダイジェストデータの暗号化を行ったが、ダイジェスト生成部４３では暗号化は行わずに、デスクランブラ４６の直後に、暗号の復号器を設置する構成も可能である。この場合は、比較部４９では、暗号化されていないダイジェストデータの比較を行うことになる。
【０１１２】
図２３から図２５を用いて、透かしデータの埋め込み対象のブロックからダイジェストデータを生成する方法を説明する。透かしデータの埋め込みブロックは、実施の形態１で説明した図７のＤＣＴブロックまたは図９のウェーブレット変換係数の集合である。埋め込みブロックの変換係数の値をａ_ｉ，ｊとすると、この変換係数値ａ_ｉ，ｊの上位ビットをダイジェストデータとして用いることができる。また別の方法として、次式にしたがって、縦、横、斜めの３方向で隣接サンプルとの絶対値差分を計算し、ある固定のビット数に丸めた値ｂ_ｉ，ｊをダイジェストとして用いてもよい。
ｂ_ｉ，ｊ＝〈｜ａ_ｉ，ｊ−（ａ_{ｉ＋１，ｊ}＋ａ_{ｉ，ｊ＋１}＋ａ_{ｉ＋１，ｊ＋１}）／３｜〉_ｐ
ここで〈〉_ｐは上位ｐビットに丸める演算を示す。
【０１１３】
図２３（ａ）は、透かしデータの埋め込みブロックの変換係数の例を示し、図２３（ｂ）はその変換係数を上記のように隣接サンプルとの間で差分処理した後の値を示す。この例では下位５ビットを除去している。このように差分演算することにより、画像のエッジ部のみに大きな値が得られ、画像のオブジェクトの付加や除去などエッジの変化を伴う改ざんの検出が容易になる。また、自然画像のように多くの平坦部を含む画像においては、近傍画素は非常に近い値を取る場合がほとんどであるため、差分を取ることにより値が０に近づく。そのため、ダイジェストデータに必要なビット数を抑えることができる。
【０１１４】
図２４は、透かしデータが埋め込まれるサンプルのビット構成を説明する図である。ダイジェストデータはサンプルの特徴を表現する上位ビットを用いて作られる。一方、透かしデータは人間に知覚できないレベルで埋め込むために、サンプルの特徴にあまり関係のない下位ビットを使用して埋め込むのがよい。しかし、サンプルの下位ビットはＪＰＥＧ２０００などの圧縮符号化における量子化処理で落とされるため、透かしデータは量子化により落とされない中位ビットを利用して埋め込まれることになる。したがって、サンプルは、ＭＳＢ（Most Significant Bit）からＬＳＢ（Least Significant Bit）の間で上位から順に、ダイジェストに使用可能なビットＡ、透かし埋め込み可能なビットＢ、および量子化により省略されるビットＣに分けられる。
【０１１５】
ダイジェストに使用可能なビットＡと透かし埋め込み可能なビットＢの境界であるＪＮＤ（Just Noticeable Difference）は、ＨＶＳ（Human Visual System）により定められる人間が知覚できる限界の透かし埋め込みレベルであり、これより下位のビットであれば、透かしを埋め込んでも人間の目ではわからない。もっとも、ＪＮＤの境界ぎりぎりまで、ダイジェストや透かし埋め込みに利用する必要はなく、ホストデータＶの圧縮率を上げるため、ＪＮＤの境界の上下に多少の余裕をもたせて、ダイジェストに使用可能なビットＡおよび透かし埋め込み可能なビットＢを決めてもよい。
【０１１６】
ダイジェストデータはホストデータＶの特徴を端的に表すものであればよいため、一般には画像の低周波成分により構成することができる。たとえば、ウェーブレット変換係数の場合は、もっとも低周波の階層のＬＬサブバンドをダイジェストデータとする。ＤＣＴ係数の場合は、ＤＣＴブロックの左上の低周波成分をダイジェストデータとする。しかしながら、画像の低周波成分からダイジェストデータを生成した場合、その空間周波数よりも高い周波数をもつ細かな改ざんがあっても、ダイジェストデータには改ざんの痕跡が残らない。そこで、より細かい改ざんの検出を可能とするため、ホストデータＶの低周波成分以外に高周波成分も用いてダイジェストデータを生成してもよい。
【０１１７】
たとえば、ウェーブレット変換係数の場合、低周波の階層のサブバンドだけでなく、高周波の階層のサブバンドも用いて、ダイジェストデータを生成する。その場合でも、上述のように、ＪＮＤで決まる境界より上位のビットをダイジェストデータに利用し、境界より下位で量子化により省略されないビットを透かしデータの埋め込みに利用すればよいが、量子化により省略される下位のビット数は高周波成分ほど多くなることに注意する。
【０１１８】
図２５（ａ）〜（ｃ）は、それぞれ、第３階層、第２階層、第１階層のサブバンドにおけるウェーブレット変換係数のサンプルのビット構成である。量子化により省略されるビットＣは、第３階層では２ビットであるが、第２階層では３ビット、第１階層では４ビットに増えており、高周波成分になるほど量子化の影響を受けるビット数は増えていく。これに伴い、透かし埋め込み可能なビットＢを固定ビット数とすると、ダイジェストに使用可能なビットＡのビット数は高周波成分になるほど少なくなる。
【０１１９】
ＤＣＴ係数の場合は、ＤＣＴブロックの右下に行くほど高周波成分になる。ＤＣＴブロックの左上の低周波成分だけでなく、右下の高周波成分も利用してダイジェストデータを生成する。このとき、ＤＣＴブロックの右下に行くほど、量子化により落とされるビット数が増え、ダイジェストデータに使用可能なビット数は制限される。
【０１２０】
本実施の形態によれば、ホストデータの特定のブロックから生成したダイジェストデータを耐性の強化された透かしとしてホストデータＶのブロックに埋め込むことができる。ホストデータを受け取った側では、ホストデータからダイジェストデータを生成し、ホストデータから電子透かしとして抽出されるダイジェストデータと照合することにより、ホストデータの改ざんの有無を検出することができる。
【０１２１】
ダイジェストデータは透かしとしてロバストに埋め込まれているため、誤り訂正により訂正可能な程度の軽度の改ざんの場合は、透かしとして抽出されるダイジェストデータは埋め込まれたものと同じものとなる可能性が高い。一方、ホストデータから生成されるダイジェストデータは、ホストデータの特徴を表したものであり、もともとホストデータの変更により壊れやすい性質をもつため、軽度の改ざんでも異なったものになる。特にダイジェストデータを一方向性関数でハッシングする場合は、わずかの変更でも大きく異なったものになる。したがって、壊れやすいダイジェストと、耐性の強い透かしデータとの比較により、軽度の改ざんでも検出することができる。
【０１２２】
また、透かしビットが壊されるような大きな改ざんがあった場合には、改ざんされたホストデータから生成されるダイジェストデータは、本来のダイジェストデータとは大きく異なるものになる。また、当然、透かしデータも改ざんの影響を受けるので、透かしとして抽出される比較対象のダイジェストデータも改ざんにより一部が破壊されて抽出されることになる。しかし、両者が偶然に一致するように改ざんすることは困難であり、改ざんのあったホストデータから生成されるダイジェストデータと、透かしとして抽出されるダイジェストデータとは一致しないことから、この場合にも改ざんがあったことを検出することができる。
【０１２３】
実施の形態５
図２６は実施の形態５に係る符号化装置１０の構成を示す。本実施の形態では、ホストデータＶのブロックを特定することなく、ホストデータＶ全体からダイジェストデータを生成して、電子透かしとして埋め込む点が、実施の形態４とは異なる。実施の形態４の符号化装置１０と共通する構成については同一符号を付して説明を省き、実施の形態４とは異なる構成と動作について説明する。
【０１２４】
ダイジェスト生成部１３は、ホストデータＶの特徴を端的に表したダイジェストデータを生成し、必要であれば秘密鍵Ｋにより暗号化する。このダイジェストデータは、ホストデータＶ全体から抽出されたものであり、ホストデータＶのあるブロックが変更されると、ダイジェストデータの対応するビットが変更されるという対応関係があり、ホストデータＶのブロックの改ざんを識別可能に構成されている。ダイジェスト生成部１３はこうして得られるダイジェストデータを透かしデータＸとして出力する。実施の形態４と同様に、変更部１４は、透かしデータＸをスクランブルし、スクランブルされた透かしデータＸ'を出力し、埋め込み部１６は、秘密鍵Ｋを用いて、埋め込みブロック選択部１８により選択されたホストデータＶのブロックにスクランブルされた透かしデータＸ'を埋め込み、埋め込みホストデータＷを出力する。
【０１２５】
図２７は実施の形態５に係る復号装置４０の構成を示す。実施の形態４の復号装置４０とは異なる構成と動作について説明する。ダイジェスト生成部４３は、埋め込みホスト信号Ｗ'からダイジェストデータを生成し、秘密鍵Ｋにより暗号化する。ダイジェスト生成部１３はこうして得られるダイジェストデータを比較部４９に与える。比較部４９は、抽出部４２以降の処理により透かしとして抽出されたダイジェストデータを、ダイジェスト生成部４３により生成されたダイジェストデータと照合することにより、改ざんの有無を判定し、判定結果を出力する。ここで、ダイジェストデータは、前述のようにホストデータＶの全体から抽出され、ホストデータＶのブロックの改ざんを識別可能に構成されており、またハッシングされていないデータであるため、照合によりダイジェストデータに不一致のあるビットが見つかると、それに対応するホストデータＶのブロックが改ざんされていることがわかる。
【０１２６】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【０１２７】
そのような変形例として、実施の形態２における特定の処理を想定して埋め込み強度を評価する方法は、実施の形態３における埋め込み強度の評価の際にも適用することができる。
【０１２８】
複数の透かしデータの候補または埋め込み位置の候補を生成するために、多様性に富んだ候補の生成が可能なＧＳ方式を用いたが、他のスクランブル方式を適用してもよく、また何らかの方法でランダムに候補のデータを生成してもよい。また実施の形態では、逆スクランブルにより、生成された透かしデータの候補から元の透かしデータを再現したが、生成された透かしデータの候補と元の透かしデータとを対応づけたテーブルを備え、このテーブルを参照して元の透かしデータを求めてもよい。
【０１２９】
またスクランブルの際に初期データとして使用した識別データは、透かしデータの先頭に挿入されて復号側に提供されていたが、この識別データを透かしには埋め込まずに、符号化側で秘密鍵として保持、管理してもよい。その場合、復号側はこの秘密鍵を取得した上で、透かしデータのスクランブルを解除する。また実施の形態３では、復号側でこの識別データを秘密鍵として入手する場合は、埋め込み位置が秘密鍵から特定されるため、整合フィルタ６２による埋め込み位置の検出作業が不要となり、したがってあらかじめ想定される透かしビットを用意しておく必要もなくなる。
【０１３０】
なお、実施の形態１の変形として、逐次型の候補の生成、評価のための構成と動作を説明したが、同様の逐次型の構成と動作が、実施の形態２から５のいずれにも適用できることはいうまでもない。
【０１３１】
実施の形態３では、埋め込み位置の候補をスクランブル方式により生成したが、埋め込み位置の候補を次に述べるテーブルマッチングによりランダムに生成してもよい。このために、電子透かしの埋め込み側と抽出側は、埋め込み位置の候補を識別するための識別データと埋め込む位置とを対応づけたテーブルを備える。このテーブルは、透かしデータの第１ビットについて、たとえば、「識別番号０の場合は（１，２９）の位置、識別番号１の場合は（９８３，２５１）の位置、・・・、識別番号１５の場合は（５４２，３７）の位置に埋め込む」といった識別番号と埋め込み座標との対応関係を格納する。第２番目から第ｎ番目のビットについてもそれぞれ埋め込み位置が異なる対応関係が格納される。埋め込み位置は何らかの方法でランダムに生成される。埋め込み側では、このテーブルを参照して、埋め込み位置の候補の識別データに対応づけて埋め込み位置の候補を生成し、透かしデータをその候補の位置に埋め込む。抽出側では、埋め込み位置の候補の識別データにもとづいてこのテーブルを参照することにより、埋め込み位置を特定し、透かしデータをその位置から抽出する。この方法によれば、埋め込み位置のランダム性が十分に保証され、頑強な埋め込みを実現することができる。また抽出側では、埋め込み位置の候補の識別データ以外にこのテーブルをもっていなければ、埋め込み位置を知ることができないため、セキュリティを高めることができる。
【０１３２】
実施の形態５では、ダイジェストデータに使用されるビットと透かし埋め込みに使用されるビットの間で干渉が起こらないように、ＪＮＤで与えられる境界よりも上位のビットからダイジェストデータを生成したが、透かし埋め込みに利用されるビットの領域も利用してダイジェストデータを生成し、復号装置において透かしを抽出して照合する際に、透かし埋め込みによる影響分を調整してダイジェストデータの比較を行うようにしてもよい。この場合、符号化装置においてＪＮＤを決める処理を省略することができる。
【０１３３】
【発明の効果】
本発明によれば、電子透かしの耐性が向上し、透かしの検出精度が改善する。
【図面の簡単な説明】
【図１】実施の形態１に係る符号化装置の構成図である。
【図２】図１の変更部と埋め込み部の機能構成図である。
【図３】実施の形態１に係る復号装置の構成図である。
【図４】元の透かしデータとＬ種類のスクランブルされた透かしデータとの関係を説明する図である。
【図５】符号化時の畳み込み演算を説明する図である。
【図６】復号時の畳み込み演算を説明する図である。
【図７】離散コサイン変換されたホストデータにおける透かしデータの埋め込みブロックを説明する図である。
【図８】図７のブロックにスクランブルされた透かしデータを埋め込む方法を説明する図である。
【図９】離散ウェーブレット変換されたホストデータにおける、透かしデータが埋め込まれるウェーブレット変換係数の集合を説明する図である。
【図１０】図９のウェーブレット変換係数の集合にスクランブルされた透かしデータを埋め込む方法を説明する図である。
【図１１】符号化装置による電子透かしの埋め込み手順を説明するフローチャートである。
【図１２】符号化装置による別の電子透かしの埋め込み手順を説明するフローチャートである。
【図１３】離散コサイン変換されたホストデータにおける透かしデータの埋め込みブロックのペアを説明する図である。
【図１４】離散ウェーブレット変換されたホストデータにおける、透かしデータが埋め込まれるウェーブレット変換係数の集合のペアを説明する図である。
【図１５】実施の形態２に係る符号化装置の構成図である。
【図１６】図１５の変更部と埋め込み部の機能構成図である。
【図１７】実施の形態３に係る符号化装置の構成図である。
【図１８】図１７の位置検出部と埋め込み部の機能構成図である。
【図１９】実施の形態３に係る復号装置の構成図である。
【図２０】実施の形態４に係る符号化装置の構成図である。
【図２１】図２０の変更部と埋め込み部の機能構成図である。
【図２２】実施の形態４に係る復号装置の構成図である。
【図２３】透かしデータの埋め込みブロックの変換係数の差分処理を説明する図である。
【図２４】透かしデータが埋め込まれるサンプルのビット構成を説明する図である。
【図２５】透かしデータが埋め込まれるウェーブレット変換係数のビット構成を階層別に説明する図である。
【図２６】実施の形態５に係る符号化装置の構成図である。
【図２７】実施の形態５に係る復号装置の構成図である。
【符号の説明】
１０符号化装置、１２ビット長伸長部、１３ダイジェスト生成部、１４変更部、１６埋め込み部、１８埋め込みブロック選択部、２０マルチプレクサ、２２スクランブラ、２４ＥＣＣ部、２６埋め込み部、２８ＳＮＲ計算部、２９重みつきＳＮＲ計算部、３０セレクタ、４０復号装置、４１埋め込みブロック選択部、４２抽出部、４４ＥＣＣ復号部、４６デスクランブラ、４９比較部、５０符号化装置、５２位置検出部、５４埋め込み部、５６埋め込みブロック選択部、６０位置情報生成部、６１埋め込みブロック選択部、６２整合フィルタ、６４セレクタ、７０復号装置。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a digital watermark technique, and more particularly to a digital watermark embedding method and an encoding device and a decoding device that can use the method.
[0002]
[Prior art]
Over the past few years, the Internet population has increased rapidly and is entering a broadband era, a new stage of Internet usage. With broadband communication, the communication band is greatly expanded, so it is possible to easily distribute content with a large amount of data such as voice, still images, and moving images. When such digital content distribution becomes popular, protection of the copyright of the content will be further demanded.
[0003]
The content data distributed on the network is easily copied by others and the copyright protection is not sufficient. Therefore, in order to protect the copyright, a technique for embedding information of a content creator and a user into content data as a digital watermark has been developed. By using this digital watermark technology, it is possible to extract digital watermarks from content data distributed on the network, detect unauthorized use, and track distribution routes of unauthorized copies.
[0004]
Some conventional digital watermark embedding techniques enable embedding of a highly durable digital watermark while maintaining the degree of freedom of the process of embedding digital watermark information (see, for example, Patent Document 1).
[0005]
The conventional digital signature image authentication technology allows JPEG (Joint Photographic Expert Group) compression on an image, but if there is any other unauthorized operation, the digital signature of the image is not authenticated. There is one that can be generated (for example, see Non-Patent Document 1).
[0006]
[Patent Document 1]
Japanese Patent Laid-Open No. 2000-13587 (full text, FIG. 1-15)
[Non-Patent Document 1]
Ching-Yung Lin and Shih-Fu Chang, "A Robust Image Authentication Method Distinguishing JPEG Compression from Malicious Manipulation," IEEE Trans. On Circuits and Systems for Video Technology, pp.153 -168, Feb. 2001.
[0007]
[Problems to be solved by the invention]
The digital watermark is embedded in the content data so as not to be understood by the user in order to prevent tampering by an unauthorized user. However, content data may be subjected to various operations in the distribution process and usage process, such as signal processing such as compression coding and various filtering, processing by the user, and alteration of watermark information. In this process, a part of the embedded digital watermark data may be changed or lost. Therefore, the digital watermark is required to be resistant to such operations.
[0008]
Patent Document 1 proposes a digital watermark embedding technique for enhancing the resistance of a digital watermark, but in accordance with human visual characteristics, a high-frequency component such as an edge portion of an image or a portion having a large change in a texture region. This is a method for embedding digital watermarks, and is highly dependent on the contents of individual content data, and there are limitations in terms of versatility and flexibility to enhance resistance to various operations on content data after watermark embedding. is there.
[0009]
The present invention has been made in view of such circumstances, and an object thereof is to provide a technique capable of embedding a strong digital watermark and reducing a detection error of the digital watermark.
[0010]
[Means for Solving the Problems]
One embodiment of the present invention relates to a digital watermark embedding method. This method embeds a plurality of digital watermark data candidates generated by scrambling in a specified block of host data, evaluates the resistance of the digital watermark, and evaluates the watermark data of which the evaluation is good. Get host data with embedded candidates.
[0011]
The host data is original data to be embedded with a digital watermark, and is data such as a still image, a moving image, and audio, for example. The embedded digital watermark includes original data identification information, creator information, user information, and the like. In addition, for the purpose of authentication, digest data of host data, that is, data that directly represents the characteristics of host data can be embedded as a digital watermark. Digital watermark tolerance refers to the case where the host data with embedded digital watermark is subjected to an attack such as alteration, or the host data with embedded digital watermark is subjected to signal processing such as compression coding or filtering. This refers to the robustness of the digital watermark data when some operation is applied to the host data after the digital watermark is embedded.
[0012]
On the electronic watermark embedding side, when the digital watermark data is scrambled, a one-to-many mapping that associates the original digital watermark data with a plurality of watermark data candidates is used. On the digital watermark extraction side, reverse mapping is performed to obtain the original digital watermark data from the scrambled watermark data. Therefore, on the side of extracting a digital watermark, a correspondence table of original digital watermark data and a plurality of watermark data candidates may be used. In addition, a scramble function for generating a plurality of watermark data candidates based on a predetermined initial value from the original digital watermark data may be used on the side of embedding the digital watermark. In this case, on the side of extracting the digital watermark, the extracted digital watermark is descrambled based on the initial value and the scramble function used for scrambling.
[0013]
Another aspect of the present invention relates to an encoding apparatus. The apparatus includes a block selection unit that selects a plurality of blocks from host data in which digital watermark data is to be embedded, and an embedding unit that independently embeds different digital watermark data in each of the plurality of blocks selected by the block selection unit; including.
[0014]
The block here is a division unit of the host data. When the filtering process for converting the host data into the spatial frequency component is performed, in the spatial region in the host data before the filtering process is performed. Correspond. For example, if filtering processing is applied to the host data by the discrete wavelet transform, the wavelets that make up the same spatial region in the host data before the discrete wavelet transformation selected from each subband of the host data after the discrete wavelet transformation A set of transform coefficients becomes an embedded block of digital watermark data.
[0015]
As another example, when host data is divided into blocks and each block is subjected to filtering processing by discrete cosine transform, each block of host data after discrete cosine transform is directly converted into each block of host data before discrete cosine transform. Since the block corresponds to the block, the block including the discrete cosine transform coefficient is an embedded block of digital watermark data. However, one block that is the minimum processing unit of discrete cosine transform is not necessarily an embedding block, and here, since a partial area with host data is an embedding block, it is a processing unit of discrete cosine transform. A collection of several blocks may be used as an embedded block.
[0016]
Yet another embodiment of the present invention also relates to an encoding apparatus. The apparatus includes a block selection unit that selects a specific block from host data in which digital watermark data is to be embedded, a scramble unit that scrambles the digital watermark data to generate a plurality of watermark data candidates, and the block selection unit. For each of the plurality of embedded host data candidates, an embedding unit that embeds each of the plurality of watermark data candidates in the specific block of the selected host data and generates a plurality of embedded host data candidates. An evaluation unit that evaluates the resistance of the digital watermark; and a selection unit that selects and outputs one of the plurality of embedded host data candidates based on the evaluation value of the resistance.
[0017]
Yet another embodiment of the present invention also relates to an encoding apparatus. The apparatus includes a block selection unit that selects a block of host data in which digital watermark data is to be embedded, a position information generation unit that generates a plurality of candidates for the embedded position of the block of the host data in which the digital watermark data is embedded, An embedding unit that embeds the watermark data in each of the plurality of embedding position candidates of the block of the host data selected by the block selecting unit, and generates a plurality of embedding host data candidates; and the plurality of embedding hosts For each data candidate, an evaluation unit that evaluates the resistance of the digital watermark and a selection unit that selects and outputs one of the plurality of embedded host data candidates based on the evaluation value of the resistance.
[0018]
The block selection unit may select a combination of a plurality of blocks having different frequency components as the specific block. For example, a combination of a block mainly containing high frequency components and a block mainly containing low frequency components may be selected. Further, as the specific block, a combination of a plurality of blocks which are located at a predetermined distance in the host data and are not adjacent to each other may be selected. When a combination of a plurality of blocks is selected in this way, this combination becomes a unit for embedding and extracting watermark data.
[0019]
The evaluation unit may evaluate the tolerance based on an S / N ratio calculated when the host data is regarded as noise with respect to the watermark data. The evaluation unit may evaluate the tolerance after performing a useful operation on the embedded host data. Useful operations include, for example, signal processing such as compression coding and various filtering, and geometric transformation such as scaling and rotation. The evaluation unit may evaluate the tolerance in consideration of a quantization error when compressing and encoding the embedded host data. When the tolerance is evaluated by the SN ratio, the variance between the watermark data extracted after performing useful operations on the embedded host data and the actually embedded watermark data may be evaluated.
[0020]
Yet another embodiment of the present invention relates to a decoding apparatus. The apparatus includes: a block selection unit that selects a plurality of blocks in which electronic watermarks are embedded from host data; and an extraction that extracts scrambled watermark data independently from each of the plurality of blocks selected by the block selection unit. And a descrambling unit for descrambling the scrambled watermark data. Thereby, the presence or absence of falsification can be detected for each block.
[0021]
Yet another embodiment of the present invention also relates to a decoding apparatus. The apparatus includes: a block selection unit that selects a block in which electronic watermarks are embedded from host data; a position information generation unit that generates a plurality of embedded position candidates for the blocks in the host data in which electronic watermarks are embedded; An extraction unit that extracts a plurality of watermark data candidates embedded in the block of the host data selected by the block selection unit, using each of a plurality of embedding position candidates, and the extracted plurality of watermark data A collation unit that collates with the assumed watermark data, and a selection unit that selects and outputs one of the plurality of watermark data candidates based on the collation result by the collation unit.
[0022]
Yet another embodiment of the present invention relates to a computer program. The program includes a step of selecting a specific block from host data in which digital watermark data is to be embedded, a step of generating a plurality of watermark data candidates by scrambling the digital watermark data, and a block selection unit. Embedding each of the plurality of watermark data candidates in the specific block of the host data to generate a plurality of embedded host data candidates; and for each of the plurality of embedded host data candidates, Causing the computer to execute a step of evaluating the resistance and a step of selecting one of the plurality of embedded host data candidates based on the evaluation value of the resistance.
[0023]
Yet another embodiment of the present invention relates to a digital watermark embedding method. This method scrambles the digest data of the host data to generate a plurality of watermark data candidates, and evaluates the tolerance of the watermark when each of the watermark data candidates is embedded in the host data, What has a good evaluation is acquired as host data in which the digest data is embedded.
[0024]
The digest data may be generated using upper bits of sample data characterizing the host data. The host data is quantized at the time of compression encoding, and information of lower bits is dropped. Therefore, when the digest data is generated from the upper bits of the sample data, the lower bits dropped by quantization may not be used. In addition, bits in a relatively lower position of the sample data are also used for embedding watermark data. Therefore, when the digest data is generated from the upper bits of the sample data, the bits used for embedding the watermark data may not be used even if the lower bits are not affected by the quantization.
[0025]
Yet another embodiment of the present invention relates to an encoding device. The apparatus includes a digest generation unit that generates digest data of host data, a scramble unit that scrambles the digest data to generate a plurality of watermark data candidates, and each of the plurality of watermark data candidates as the host data. An embedding unit that generates a plurality of embedded host data candidates, an evaluation unit that evaluates the resistance of the digital watermark for each of the plurality of embedded host data candidates, and the plurality of the plurality of embedded host data based on the resistance evaluation value A selection unit that selects and outputs one of the embedded host data candidates.
[0026]
A block selection unit that selects a specific block from the host data; wherein the digest unit generates the digest data from the specific block of the host data; and the embedding unit includes the specific block of the host data. Each of the plurality of watermark data candidates may be embedded to generate the plurality of embedded host data candidates. Thus, by generating a digest by designating a block of host data, it becomes possible to detect a falsified portion of the host data in units of blocks even when the digest data is hashed with a one-way function.
[0027]
Yet another embodiment of the present invention relates to a decoding apparatus. The apparatus includes: an extractor that extracts digest data embedded as digital watermark from host data; a digest generator that generates digest data from the host data; and the extractor that generates digest data generated by the digest generator And a collation unit for identifying a rough position of the falsification together with whether or not the host data has been falsified by collating with the digest data extracted by the above. Digest data represents the general characteristics of host data due to the low-frequency component of the host data. Therefore, if a mismatch is found in some bits of the digest data by the collation unit, it corresponds to the mismatched bit. It is thought that there was a change in the location of the host data, and it is possible to grasp the rough position of the alteration.
[0028]
A block selection unit that selects a block in which a digital watermark is embedded from the host data; wherein the extraction unit extracts the digest data from the block of the host data; and the digest generation unit includes the digest of the host data. The digest data may be generated from the block. As described above, since the block in which the digest data is generated is determined, even when the extracted digest data is hashed by the one-way function, the tampered portion can be specified in units of blocks.
[0029]
Yet another embodiment of the present invention relates to a computer program. The program includes a step of generating digest data from host data, a step of scrambling the generated digest data to generate a plurality of watermark data candidates, and each of the plurality of watermark data candidates in the host data. Embedding, generating a plurality of embedded host data candidates, evaluating each digital watermark resistance for each of the plurality of embedded host data candidates, and the plurality of embeddings based on the resistance evaluation value Selecting one of the host data candidates.
[0030]
It should be noted that any combination of the above-described constituent elements and a conversion of the expression of the present invention between a method, an apparatus, a system, a recording medium, a computer program, and the like are also effective as an aspect of the present invention.
[0031]
DETAILED DESCRIPTION OF THE INVENTION
Embodiment 1
FIG. 1 shows a configuration of encoding apparatus 10 according to Embodiment 1. This configuration can be realized in hardware by a CPU, memory, or other LSI of an arbitrary computer, and in software, it is realized by a program with a digital watermark embedding function loaded in the memory. So, functional blocks that are realized by their cooperation are drawn. Therefore, those skilled in the art will understand that these functional blocks can be realized in various forms by hardware only, software only, or a combination thereof.
[0032]
The encoding device 10 performs processing for embedding the watermark information I in the host data V, and outputs embedded host data W. The host data V is data such as audio, still images, and moving images. The watermark information I is information relating to copyright such as identification information of the host data V, creator information, user information, authentication information for detecting falsification of the host data V, a time stamp, and the like. The watermark information I is generally obtained by encrypting such information.
[0033]
The bit length decompression unit 12 performs an operation with the secret key K on the s-bit watermark information I to be embedded in a specific block in the host data V, and converts it into t-bit watermark data X having a longer bit length. . Here, s and t are natural numbers and satisfy t ≧ s. The encryption function is f₀If this is the case, this processing is converted to X = f₀It is represented by (I, K). Further, when the block in which the watermark is embedded is configured as a two-dimensional data string like a still image and the block size is M × N, the relationship of t ≦ M × N is established.
[0034]
The changing unit 14 scrambles the watermark data X using the watermark data X and the host data V, and outputs scrambled watermark data X ′. Scramble function f₂Then, this processing is performed using the conversion formula X ′ = f₂It is represented by (X, V).
[0035]
The embedding block selection unit 18 selects a block of host data V in which the watermark data X is to be embedded. When the watermark information I is composed of block identification information or the like, the block indicated by the identification information is selected. Alternatively, when information unrelated to the block or a part of the information is handled as the watermark information I, a block to be embedded at random is selected using the secret key K. The embedding unit 16 embeds the scrambled watermark data X ′ in the block of the host data V selected by the embedding block selection unit 18 using the secret key K, and outputs embedded host data W. Embed function f₁Then, this processing is converted to W = f₁(V, X ′, K). In the case of an embedding method that does not depend on the secret key K, W = f₁(V, X ′).
[0036]
The changing unit 14 and the embedding unit 16 cooperate to generate a plurality of scrambled watermark data X ′, embed each in a selected block of the host data V, and generate a plurality of embedded host data W candidates. It has a function to select one of those candidates. By repeating the above watermark embedding process for all the blocks of the host data V in which the watermark is to be embedded, the watermark is independently embedded in each block.
[0037]
FIG. 2 is a functional configuration diagram of the changing unit 14 and the embedding unit 16. The L multiplexers 20 have initial data C at the head of the watermark data X, respectively.₀~ C_L-1L-type bit sequence X with inserted_bIs generated. The L scramblers 22 scramble each of the L types of bit sequences, and the L types of scrambled watermark data X ′._bIs generated. The L ECC (Error Correction Code) sections 24 include L types of scrambled watermark data X ′._bWatermark data X ′ with parity for error correction added to each_cIs generated. The ECC unit 24 is an option for improving the watermark bit detection rate and may not be necessary depending on the application, and this configuration may be omitted. Further, the order of the scrambler 22 and the ECC unit 24 is reversed, and parity for error correction is added to the L types of bit sequences, and then scrambled to generate L types of scrambled watermark data. May be.
[0038]
The L embedding units 26 are provided with L types of scrambled watermark data X ′._cAre embedded in a block of host data V selected by the embedded block selector 18 to generate L types of embedded host data W candidates. The L SNR calculators 28 evaluate the tolerance of the watermark data X for each of the L types of embedded host data W candidates. The selector 30 selects a candidate for embedded host data W having the best tolerance evaluation value, and outputs it as final embedded host data W.
[0039]
FIG. 3 shows a configuration of decoding apparatus 40 according to Embodiment 1. The embedded host data W in which the digital watermark is embedded by the encoding device 10 is distributed on the network and used in the computer. In the process, the embedded host data W is subjected to operations such as compression encoding and tampering. For image data, useful operations such as signal processing such as JPEG compression, filtering, quantization, and color correction, and geometric transformations such as scaling, cropping, rotation, and translation are performed. Unauthorized attacks such as removing or altering The deformation caused by such an operation is regarded as noise N with respect to the embedded host data W, and the embedded host data W added with the noise N is set as an embedded host signal W ′ (= W + N). The decoding device 40 performs processing for extracting the embedded watermark information I from the embedded host signal W ′.
[0040]
The embedded block selection unit 41 selects a block in which watermark data is embedded from the embedded host signal W ′ using the secret key K if necessary. The extraction unit 42 uses the secret key K to watermark data X ′ embedded in the block selected from the embedded host signal W ′._cTo extract. The ECC decoding unit 44 uses the watermark data X ′._cError correction using the parity bit added to the watermark data X ′_bIs generated. The descrambler 46 uses the secret key K, and the watermark data X ′ after error correction._bUnscramble the watermark data X_bIs output. The bit length restoration unit 48 uses the secret key K to generate the watermark data X_bAre restored and the original watermark information I is output. By repeating the above-described watermark extraction processing for all the blocks of the host data V in which the watermark is embedded, the watermark can be extracted independently from each block. Also, if there is a block for which the watermark could not be extracted correctly, it is possible to detect tampering in units of blocks by determining that the block has been tampered with.
[0041]
A procedure for embedding and extracting a digital watermark by the encoding apparatus 10 and the decoding apparatus 40 having the above configuration will be described. FIG. 11 is a flowchart for explaining a digital watermark embedding procedure by the encoding apparatus 10. In the description of the flowchart, FIGS. 4 to 10 are appropriately referred to. The multiplexer 20 inserts L types of initial data at the head of the watermark data X whose bit length has been expanded by the bit length expansion unit 12 to generate L code sequences (S10), and the scrambler 22 The code sequence is scrambled to generate L types of scrambled watermark data X ′ (S12).
[0042]
FIG. 4 shows the relationship between the watermark data X and the L types of scrambled watermark data X ′. At the beginning of the n-bit watermark data X, r-bit redundant words are added as identification data ID [0] to ID [L-1] to create L types of watermark data candidates. 2 max^rKind candidates are created. The bit string of the watermark data X included in these candidates is scrambled by the scramble method described below.
[0043]
As an example of the scramble system, a GS (Guided Scramble) system used for digital modulation in transmission or magnetic recording is adopted. In the GS method, L types of code sequences are generated for an information sequence having a certain data block length, and these are treated as candidates for a code sequence to be transmitted next. Among these candidates, an optimum one is selected in accordance with the properties of the transmission medium to obtain a final code sequence. By this GS method, a variety of code sequence candidates can be generated by a simple method.
[0044]
The multiplexer 20 and the scrambler 22 in the encoding device 10 function as a code sequence candidate generation unit in the GS encoder. The GS encoder performs L types of r-bit redundant words c immediately before an n-bit information sequence D (x)._i(I = 0,..., L−1) is added, and L types of code sequences c_ixⁿ+ D (x) is generated. The code length of this code sequence is (n + r) bits. By dividing the code sequence to which redundant words are added in this way by an N-dimensional scrambled polynomial S (x) as shown in the following equation, the quotient T_i(X) is obtained.
[0045]
T_i(X) = Q_{S (x)}[(C_ixⁿ+ D (x)) x^N] (1)
However, Q_a[B] indicates a quotient obtained by dividing b by a. Quotient set {T₀(X), ..., T_L-1(X)} is a scrambled code sequence candidate. For each of these candidates, the performance when the code sequence is actually used is evaluated, and the one with the best evaluation value is selected as the final code sequence.
[0046]
At the time of demodulation, the descrambler 46 in the decoding device 40 functions as a GS decoder, multiplies the code sequence by S (x), and discards the conversion information of the lower N bits and the upper r bits, thereby removing the original information sequence D ( x) is obtained.
[0047]
Here, S (x) = x as scramble polynomial S (x)^rA case where +1 is used will be described. When n mod r = 0, the expression (1) can be expressed by the convolution operation shown in the following expression.
[0048]
t_j= D_j(+) C_i  (J = 0)
t_j= D_j(+) T_j-1  (J = 1,..., N / r-1)
Where i = 0,..., L−1 and d_jIs a bit string obtained by dividing the original information series D (x) by r bits, t_jIs the converted code sequence T_iThe first r-bit redundant word c in (x)_iThis is a bit string obtained by dividing the rest by r bits. (+) Indicates an exclusive OR (EX-OR) operation.
[0049]
FIG. 5 is a diagram for explaining the convolution operation at the time of encoding. For example, consider the case where n = 6 and r = 2. For the original information series D (x) = (1, 0, 1, 0, 0, 1), the redundant word c₀= (0,0) is added, and the converted code sequence T₀(X) is generated. By the above convolution operation at the time of encoding, t₀= D₀(+) C₀= (1, 0) (+) (0, 0) = (1, 0), t₁= D₁(+) T₀= (1,0) (+) (1,0) = (0,0), t₂= D₂(+) T₁= (0,1) (+) (0,0) = (0,1), and the converted code sequence T₀= (0,0,1,0,0,0,0,1) is obtained. Here, the converted code sequence T₀The first 2 bits of the redundant word c₀Note that
[0050]
Similarly, the redundant word c₁= (0,1), c₂= (1,0), c₃= (1, 1) for each converted code sequence T₁= (0,1,1,1,0,1,0,0), T₂= (1, 0, 0, 0, 1, 0, 1, 1), T₃= (1,1,0,1,1,1,1,0) is obtained.
[0051]
At the time of decoding, the original information series D (x) is obtained by performing a convolution operation as in the following equation.
[0052]
d_j= T_j(+) C_i  (J = 0)
d_j= T_j(+) T_j-1  (J = 1,..., N / r-1)
[0053]
FIG. 6 is a diagram for explaining the convolution operation at the time of decoding. In the above example, the converted encoded sequence T₀= (0, 0, 1, 0, 0, 0, 0, 1), the redundant word c from the first two bits₀= (0,0) is obtained, and by the above convolution operation at the time of decoding, d₀= T₀(+) C₀= (1,0) (+) (0,0) = (1,0), d₁= T₁(+) T₀= (0,0) (+) (1,0) = (1,0), d₂= T₂(+) T₁= (0,1) (+) (0,0) = (0,1), and the original information series D (x) = (1,0,1,0,0,1) is obtained. Other converted encoded sequence T₁, T₂, T₃Also, the original information series D (x) is obtained by this convolution operation.
[0054]
Refer to FIG. 11 again. The embedding block selection unit 18 selects a block in which the watermark data X ′ is to be embedded from the host data V (S13). The L types of scrambled watermark data X ′ generated by the scrambler 22 are added with parity for error correction by the ECC unit 24 and then embedded in the selected block of the host data V by the embedding unit 26. (S14).
[0055]
L types of scrambled watermark data X ′ are x⁰, X¹, ..., x^L-1And The bit sequence of each watermark data candidate is expressed as follows. The leading r bits are identification data. Also, bit 0 after the scramble process is replaced with -1, and the following process is performed.
[0056]
x⁰= {-1, ...,-1, -1, x⁰ ₀, X⁰ ₁, ..., x⁰ _n-1}
x¹= {-1, ...,-1,1, x¹ ₀, X¹ ₁, ..., x¹ _n-1} ...
x^L-1= {1, ..., 1,1, x^L-1 ₀, X^L-1 ₁, ..., x^L-1 _n-1}
[0057]
The embedding block selection unit 18 selects one block as an embedding target of watermark data composed of (n + r) bits. Further, from within the selected block, a pair of sample sets (V⁺, V⁻) Is selected. Set of embedded samples V⁺, V⁻Each have (n + r) elements as follows.
[0058]
V⁺= {V⁺ ₀, V⁺ ₁, ..., v⁺ _{n + r-1}}
V⁻= {V⁻ ₀, V⁻ ₁, ..., v⁻ _{n + r-1}}
Here a set of samples V⁺, V⁻A subset v that is an element of⁺ _i, V⁻ _i(I = 0, 1,..., N + r−1) are composed of m sample data randomly selected in the same block.
[0059]
v⁺ _i= {V⁺ _{i, 0}, V⁺ _{i, 1}, ..., v⁺ _{i, m-1}}
v⁻ _i= {V⁻ _{i, 0}, V⁻ _{i, 1}, ..., v⁻ _{i, m-1}}
[0060]
Watermark data candidate x^k(K = 0,..., L−1) is a sample set pair (V⁺, V⁻) Embedded as follows, and L types of embedded host data candidates W^kIs generated.
[0061]
w^{+ K} _{i, j}= V⁺ _{i, j}+ Α⁺ _{i, j}・ X^k _i
w^-K _{i, j}= V⁻ _{i, j}-Α⁻ _{i, j}・ X^k _i
Where α⁺ _{i, j}And α⁻ _{i, j}Is a scaling parameter for reducing noise perceived based on the human visual model, and is a positive value. Or α⁺ _{i, j}And α⁻ _{i, j}May be a positive value generated by the secret key K so as to follow a certain probability distribution, such as a Gaussian distribution, a uniform distribution, or the like. In this case, the embedding strength of the watermark is reduced, but the confidentiality of the embedded watermark is improved. In this way, each bit x of the kth watermark data candidate^k _iIs each subset v⁺ _i, V⁻ _iAre embedded in m samples. The greater the number of duplicates m, the less likely the watermark bits are lost and the smaller the detection error, while the fewer the number of watermark bits that can be embedded in the host data. α⁺ _{i, j}And α⁻ _{i, j}Is a value set for each pixel so that visual deterioration cannot be detected. In principle, even if the number m of pixels to be embedded is increased, deterioration of image quality is not detected by human vision. However, an increase in the number of pixels used to embed one bit means that the number of bits that can be embedded is reduced because the embedment area is limited, thus leading to a decrease in the embedment rate. Become.
[0062]
As an example of a block to be embedded with watermark data, when a DCT block obtained by performing discrete cosine transform on the host data V is used, each subset v⁺ _i, V⁻ _iThe m sample data are m DCT coefficients included in one DCT block selected as a watermark embedding target. FIG. 7 is a diagram for explaining an embedded block of the watermark data X ′ selected by the embedded block selecting unit 18. As shown in the figure, in the discrete cosine transform used in JPEG, the spatial region of the host data V is divided into blocks each consisting of 8 pixels vertically and horizontally, and each pixel is converted into a spatial frequency component within each block. The embedding block selection unit 18 uses the watermark bit string x^kThe DCT block 120 is selected as a block to be embedded as shown in FIG.
[0063]
FIG. 8 shows that 2m DCT coefficients in an 8 × 8 DCT block are divided into watermark bits x^k _i(I = 0, 1,..., N + r−1) is embedded. Each subset v⁺ _i, V⁻ _iEach of the m DCT coefficients selected as is selected based on the secret key K. In this way, (n + r) -bit watermark data is embedded in the same block. In the above description, one DCT block is selected as a watermark embedding target block. However, the embedding target block does not need to be a DCT block that is a minimum processing unit of discrete cosine transform, and has a certain size. It may be a divided area. In that case, a similar watermark embedding process may be performed by regarding a set of several DCT blocks as one embedding target block.
[0064]
As another example of a block to be embedded with watermark data, a set of wavelet transform coefficients obtained when the host data V is subjected to discrete wavelet transform is considered. FIG. 9 is a diagram for explaining a set of wavelet transform coefficients constituting the same spatial region, selected from each subband of the host data V subjected to discrete wavelet transform. As shown in the figure, the host data V is divided into four frequency subbands by discrete wavelet transform. These subbands include LL subbands having low frequency components in both vertical and horizontal directions, HL and LH subbands having low frequency components in any one of vertical and horizontal directions, and high frequency components in the other direction. This is an HH subband having a high frequency component in both the vertical and horizontal directions. The number of vertical and horizontal pixels of each subband is 1/2 of the host data V before processing, and subband data having a size of 1/4 is obtained by one filtering.
[0065]
Of the subbands obtained in this way, the filtering process by the discrete wavelet transform is performed again on the LL subband, and further divided into four subbands of LL, HL, LH, and HH. This filtering is performed a predetermined number of times, and the LL subband generated by the last filtering becomes data closest to the DC component of the host data V.
[0066]
When wavelet transform coefficients corresponding to a specific spatial region of the host data V before the discrete wavelet transform are selected from the subbands of each layer, a set of wavelet transform coefficients 100 to 109 having a tree structure is obtained as shown in FIG. . That is, the third layer LL subband LL₃, HL subband HL₃, LH subband LH₃, And HH subband HH₃, Wavelet transform coefficients 100, 101, 102, and 103 each consisting of one pixel are selected, and the second level HL subband HL is selected.₂, LH subband LH₂And HH subband HH₂From which 2 × 2 wavelet transform coefficients 104, 105 and 106 are selected, respectively, and finally the HL subband HL of the first layer₁, LH subband LH₁And HH subband HH₁Are used to select 4 × 4 wavelet transform coefficients 107, 108, and 109, respectively. These sets of wavelet transform coefficients are obtained by hierarchically transforming specific spatial domain data in the host data V before discrete wavelet transform into spatial frequency components. Therefore, if a set of these wavelet transform coefficients is selected as an embedding block of the watermark data X ′ and the watermark data X ′ is embedded, the watermark data X ′ is embedded in a specific spatial region of the host data V. Each subset v⁺ _i, V⁻ _iA set of wavelet transform coefficients having such a tree structure may be used.
[0067]
FIG. 10 shows that the 2m wavelet transform coefficients in the set of wavelet transform coefficients are converted into watermark bits x.^k _iShows the state of embedded. When the wavelet transform coefficients selected from the three layers of FIG. 9 are collected, an 8 × 8 wavelet transform coefficient set 110 is obtained as shown in FIG. If the number of wavelet transform layers is H, 2^H× 2^HA matrix of wavelet transform coefficients is obtained. However, this is a description of the minimum-size embedding block. When a divided area having a certain size is selected as the watermark embedding area of the host data V, the size of the matrix of wavelet transform coefficients corresponding to that area is selected. Will naturally grow. The wavelet transform coefficient matrix thus obtained is treated as an embedding block, and the m wavelet transform coefficients in the embedding block are converted into watermark bits x^k _i(I = 0, 1,..., N + r−1) are embedded by the same method as in FIG.
[0068]
Returning to FIG. 11, the SNR calculator 28 selects the candidate W of L types of embedded host data.^kWatermark data x^kResistance, that is, the embedding strength is evaluated (S16), and the selector 30 selects the embedded host data candidate W having the maximum embedding strength.^kIs selected as the final embedded host data W (S18).
[0069]
Before the embedding strength evaluation formula is given, it will be examined how the watermark data X ′ is detected when the embedding host data W is deformed by signal processing, image processing, or the like. The deformation applied to the embedded host data W is treated as noise N, and the embedded host data W with the noise N added is called an embedded host signal W ′. A method for extracting the watermark data X ′ from the embedded host signal W ′ will be described. A pair of embedded host signals (W '⁺, W '⁻) Is defined as follows. A set W ′ of embedded host signals⁺, W '⁻Each has (n + r) elements as follows.
[0070]
W '⁺= {W '⁺ ₀, W '⁺ ₁, ..., w '⁺ _{n + r-1}}
W '⁻= {W '⁻ ₀, W '⁻ ₁, ..., w '⁻ _{n + r-1}}
Here, a set W ′ of embedded host signals⁺, W '⁻Each subset w ′ that is an element of⁺ _i, W '⁻ _iCorresponds to m sample data of the embedded host signal W ′ as follows, corresponding to the embedded position of the digital watermark.
w '⁺ _i= {W '⁺ _{i, 0}, W '⁺ _{i, 1}, ..., w '⁺ _{i, m-1}}
w '⁻ _i= {W '⁻ _{i, 0}, W '⁻ _{i, 1}, ..., w '⁻ _{i, m-1}}
[0071]
Watermark bit x^k _iIn order to detect_iCalculate
z_i= Σ_{j = 0} ^m-1(W '⁺ _{i, j}−w ′⁻ _{i, j})
= Σ_{j = 0} ^m-1[(W⁺ _{i, j}+ N⁺ _{i, j})-(W⁻ _{i, j}+ N⁻ _{i, j}]]
= Σ_{j = 0} ^m-1[(V⁺ _{i, j}-V⁻ _{i, j}) + (Α⁺ _{i, j}+ Α⁻ _{i, j}) X^k _i+ (N⁺ _{i, j}-N⁻ _{i, j}]]
Where Σ_{j = 0} ^m-1(V⁺ _{i, j}-V⁻ _{i, j}) Generally follows a Gaussian distribution and approaches 0 when m is sufficiently large. The noise term Σ_{j = 0} ^m-1(N⁺ _{i, j}-N⁻ _{i, j}) Approaches 0 in the same manner. Therefore, z_iIs Σ_{j = 0} ^m-1[(Α⁺ _{i, j}+ Α⁻ _{i, j}) X^k _i]. (Α⁺ _{i, j}+ Α⁻ _{i, j}) Is positive, so the watermark bit x^k _iZ is 1_iIs positive and the watermark bit x^k _iZ if -1_iIs negative. Therefore z_iWatermark bit x^k _iCan be determined.
[0072]
The embedding strength is evaluated by regarding the host data V as noise with respect to the watermark data X, and the embedded watermark data x^kIs performed by calculating the variance of the detected watermark data. It can be considered that the smaller the variance, the stronger the tolerance. Candidate pair of embedded host data (W^{+ K}, W^-K) To evaluate the signal-to-noise ratio according to the following equation and select an optimal candidate K.
[0073]
K = argmax_k(P_k/ (2σ_k ²))
P_k= Σ_{i = 0} ^{n + r-1}｜ Σ_{j = 0} ^m-1(W^{+ K} _{i, j}-W^-K _{i, j}) ｜²/ (N + r)
σ_k ²= Σ_{i = 0} ^{n + r-1}｜ Σ_{j = 0} ^m-1(W^{+ K} _{i, j}-W^-K _{i, j}-P_k ^1/2・ X^k _i｜²/ (N + r)
[0074]
Watermark bit x^k _iIs the above-mentioned determination value z for determining which of {1, -1}_iIs z before the noise is added to the embedded host data W._i= Σ_{j = 0} ^m-1(W^{+ K} _{i, j}-W^-K _{i, j}), The variance σ_k ²Is the detected value z for the watermark bits_iAnd the average value P of the watermark bits actually embedded_k ^1/2・ X^k _iIt can be said that the squares of the differences are evaluated and averaged for i = 0,..., N + r−1. However, P_kIs the detected value z_iOf squares of i = 0,..., N + r−1, and indicates the average power of the embedded watermark. Therefore, the embedded watermark data x^kAnd Euclidean distance between the extracted watermark data and the extracted watermark data are smaller and the absolute value of the determination value for detecting the watermark bit is larger._k/ (2σ_k ²) Value increases. In other words, P_k/ (2σ_k ²Selecting the candidate that maximizes ()) means selecting the candidate with the smallest watermark bit detection error.
[0075]
Judgment value z_iV⁺ _{i, j}> V⁺ _{i, j}And x^k _i= 1 if z_i>> 0 and v⁺ _{i, j}<V⁺ _{i, j}And x^k _i== z if -1_i<< 0. Therefore, the optimum watermark data x is evaluated according to the above evaluation.^kSelecting a candidate of_iWatermark bit x by^k _iIn order to improve the detection performance of⁺ _{i, j}> V⁺ _{i, j}Then x '_i= 1, v⁺ _{i, j}<V⁺ _{i, j}Then x '_i= Original watermark bit x such that = 1_iX '_iMeans to change. This is the GS method guiding rule, and the judgment value z_iResponse is improved.
[0076]
When the extraction unit 42 of the decoding device 40 receives the embedded host signal W ′ to which noise has been added, if the ECC decoding unit 44 is configured by a hard input decoder, the determination value z_iIs calculated as follows, and the judgment value z_iWhether the watermark bit x ′ is {−1, 1} or not is obtained, and watermark data X ′ is obtained. When the ECC decoding unit 44 is composed of a soft input decoder, the determination value z_iIs sent to the ECC decoding unit 44 as it is without making a hard decision to {-1, 1}.
[0077]
z_i= Σ_{j = 0} ^m-1(W '⁺ _{i, j}−w ′⁻ _{i, j})
= Σ_{j = 0} ^m-1[(W⁺ _{i, j}+ N⁺ _{i, j})-(W⁻ _{i, j}+ N⁻ _{i, j}]]
= Σ_{j = 0} ^m-1[(V⁺ _{i, j}-V⁻ _{i, j}) + (Α⁺ _{i, j}+ Α⁻ _{i, j}X)_i+ (N⁺ _{i, j}-N⁻ _{i, j}]]
[0078]
The extracted watermark data X ′ is further subjected to error correction by the ECC decoding unit 44, descrambled by the descrambler 46, and the original watermark data X is obtained.
[0079]
As described above, according to the embodiment, when media data such as an image or sound in which a digital watermark is embedded is given using the GS method, the watermark bit sequence is converted into a bit sequence that can be easily embedded in the media data. Can be embedded above. Therefore, it is possible to enhance the digital watermark resistance against signal processing, geometric transformation, compression, data tampering, and the like, and the watermark detection accuracy is greatly improved. In addition, since a specific block is selected as a watermark bit embedding target and a watermark bit is embedded independently for each block, the presence or absence of tampering can be checked for each block by detecting the watermark for each block. Therefore, it is possible to detect, in units of blocks, portions where alterations such as changing a specific part of the image or adding a new object have been performed.
[0080]
In the above embodiment, as shown in FIG. 2, in order to generate candidates for L types of watermark data, L multiplexers 20, scramblers 22, ECC units 24, embedding units 26, and SNR calculation units 28 are provided in parallel, but these members may be configured in a single configuration, and L types of watermark data candidates may be sequentially generated and evaluated to select the optimal candidate.
[0081]
FIG. 12 is a flowchart for explaining such a sequential digital watermark embedding procedure. The embedding block selection unit 18 selects in advance the block in which the watermark data is to be embedded from the host data V (S19). The variable i is initialized to 1 (S20). The multiplexer 20 inserts the i-th initial data at the beginning of the watermark data X encrypted by the encryption unit 12 to generate a code sequence (S22), and the scrambler 22 scrambles the code sequence, The i-th scrambled watermark data X ′ is generated (S24). The i-th scrambled watermark data X ′ generated by the scrambler 22 is added with parity for error correction by the ECC unit 24 as necessary, and the host data V is selected by the embedding unit 26. It is embedded in the block (S26). The SNR calculation unit 28 uses the i-th embedded host data candidate WⁱWatermark data xⁱResistance, ie embedding strength S_iIs evaluated (S28). The selector 30 has an embedding strength S_iIs greater than the reference value T that guarantees the lowest evaluation value (S30). If the embedding strength S_iIs larger than the reference value T (Y in S30), the value of the current variable i is substituted for the variable K (S32), and the Kth embedded host data candidate is selected as the final embedded host data W (S40). ). Embedding strength S_iIs equal to or less than the reference value T (N in S30), if the current value of the variable i is equal to L (Y in S34), the embedding strength S examined so far_kThe subscript k with the largest value is substituted for the variable K (S38), and the Kth embedded host data candidate is selected as the final embedded host data W (S40). If the current value of the variable i is smaller than L (N in S34), the variable i is incremented by 1 (S36), and the process returns to step S22.
[0082]
When a candidate having an embedding strength equal to or higher than a desired reference value is obtained by this iterative process, the candidate is selected as the final embedded host data W. If such a candidate is not generated, L candidates are generated. Candidates for the embedded host data are generated, and the one having the maximum embedding strength can be selected as the final embedded host data W.
[0083]
In the above description, the embedding block selection unit 18 performs the watermark bit sequence x^kOne block was selected as a block to be embedded. However, when the selected block is a background image or a monotonous image, there are cases where it is difficult to embed watermark data because there are few high-frequency components. Therefore, the embedded block selection unit 18 performs the watermark bit sequence x.^kA combination of two or more blocks may be selected as the target to be embedded. In this case, the watermark bit string x is assigned to two or more blocks.^kSince it is embedded, it is possible to detect whether or not any of the combination blocks has been tampered with, but it is not possible to identify which block.
[0084]
FIG. 13 shows two DCT blocks 120 and 130 selected from the discrete cosine transformed host data V. For example, one DCT block 120 mainly includes a low-frequency component in which watermark data is difficult to be embedded, and the other DCT block 130 selects a combination mainly including a high-frequency component in which watermark data is easily embedded. The frequency component included in the DCT block may be determined based on the DCT coefficient, or may be determined based on the variance of pixel values in the DCT block. Also, since adjacent blocks often have frequency components similar to each other, blocks whose positions are as far apart as possible may be combined. Such combination blocks may be selected at random. By using a combination of blocks as a watermark data embedding unit, it is possible to absorb the difference in embedding strength between the blocks and average the embedding strength.
[0085]
FIG. 14 shows a set of two wavelet transform coefficients selected from the host data V subjected to discrete wavelet transform. In addition to the set of wavelet transform coefficients 100 to 109 corresponding to a specific spatial region of the host data V before the discrete wavelet transform described in FIG. 9, the wavelet transform coefficients corresponding to another specific spatial region of the host data V The sets 200 to 209 are shown with hatching in FIG. The sets of these two wavelet transform coefficients correspond to, for example, a spatial region containing many low-frequency components and a spatial region containing many high-frequency components, as in the combination of DCT blocks in FIG.
[0086]
Since the combination of the embedding blocks described in FIGS. 13 and 14 is determined based on the secret key K, the embedding block selection unit 41 of the decryption apparatus 40 embeds the watermark data X ′ using the secret key K. Selected blocks. That is, with the secret key K, the decryption device 40 can specify the same block combination as the block combination embedded by the encoding device 10.
[0087]
As yet another block combination method, the embedding block selection unit 18 may select and combine blocks having different features based on some feature amount. For example, a feature amount such as dispersion of pixel values may be evaluated, and a texture type block such as the surface of an object may be combined with a flat type block such as a background.
[0088]
When the combination block is selected based on the feature amount in this way, it is difficult for the embedded block selection unit 41 of the decoding device 40 to evaluate the same feature amount and correctly select the embedded block. This is because such feature amounts generally change due to tampering. Thus, when a combination block is selected based on the feature amount, it can be dealt with by transmitting information for specifying the embedded block to the decryption device 40 as a secret key. Alternatively, the embedding block selection unit 41 of the decoding device 40 determines an embedding block based on the feature amount, and when the watermark data cannot be correctly extracted in many blocks, it is determined that the tampering has occurred. Also good. In this case, however, tampering cannot be detected in units of blocks, and only the presence / absence of tampering can be detected.
[0089]
Embodiment 2
FIG. 15 shows a configuration of encoding apparatus 11 according to the second embodiment. In the present embodiment, a specific process such as compression encoding received by the host data V in which the digital watermark is embedded is assumed in advance, and the effect of the specific process is considered at the time of embedding the watermark, thereby making the digital watermark resistant. Give it. Configurations common to the first embodiment are denoted by the same reference numerals, description thereof is omitted, and configurations and operations different from the first embodiment will be described.
[0090]
When the watermark data X is scrambled, the changing unit 15 selects a bit sequence of highly resistant watermark data in consideration of distortion D caused by a specific process received by the host data V, and outputs scrambled watermark data X ′. . FIG. 16 is a functional configuration diagram of the changing unit 15 and the embedding unit 16. The weighted SNR calculator 29 generates L types of scrambled watermark data X ′._cWhen the tolerance of the watermark data X is evaluated for the candidate of the host data W in which is embedded, the distortion D assumed by a specific process is taken into consideration. Specifically, when evaluating the embedding strength based on the SNR between the embedded watermark data and the detected watermark data, the following weighted SNR is used in consideration of deterioration due to a specific process for the embedded host data W.
[0091]
K = argmax_k(P_k/ (2σ_k ²))
P_k= Σ_{i = 0} ^{n + r-1}｜ Σ_{j = 0} ^m-1(W^{* + K} _{i, j}-W^{* -K} _{i, j}) ｜²/ (N + r)
σ_k ²= Σ_{i = 0} ^{n + r-1}｜ Σ_{j = 0} ^m-1(W^{* + K} _{i, j}-W^{* -K} _{i, j}-P_k ^1/2・ X^k _i｜²/ (N + r)
Where w^{* + K} _{i, j}, W^{* -K} _{i, j}Is the embedded host data W after a specific process is performed. If it is known that the specific process is, for example, compression by JPEG2000, w^{* + K} _{i, j}, W^{* -K} _{i, j}Can be calculated using the JPEG2000 quantization method.
[0092]
Based on the JPEG2000 standard "ISO / IEC 15444-1: JPEG 2000 image coding system, JPEG 2000 final committee draft, 18 August 2000", the quantization method of JPEG 2000 will be briefly described. The wavelet transform coefficient before quantization in subband b is expressed as a_b(U, v), the wavelet transform coefficient after quantization in subband b is q_bAssuming that (u, v), in JPEG 2000, the wavelet transform coefficient is quantized using the following quantization formula.
[0093]
q_b(U, v) = sign (a_b(U, v)) ・ [| a_b(U, v) | / Δb]
Here, [x] represents the maximum integer not exceeding x. Δb is the quantization step in subband b and is given by:
Δb = 2 ^ (R_b−ε_b) ・ (1 + μ_b/ 2¹¹)
Where R_bIs the dynamic range in subband b, ε_bIs the quantization index in subband b, μ_bIs the mantissa of quantization in subband b.
[0094]
Thus, in JPEG2000, wavelet transform coefficients belonging to the same subband are divided by the same quantization step and rounded to an integer value. Since the watermark data X embedded in the host data V needs to be resistant to such a quantization operation, the value of the embedded host data W after being quantized by JPEG2000 is calculated, as described above. Then, the tolerance of the watermark data is evaluated for the calculated host data W.
[0095]
According to the present embodiment, when embedding a watermark, the embedding strength is evaluated assuming a specific process for the embedded host data, and a bit sequence of watermark data with a high embedding strength is selected. It is possible to generate digital watermark embedded data having high tolerance.
[0096]
Embodiment 3
FIG. 17 shows a configuration of encoding apparatus 50 according to Embodiment 3. The encoding device 50 embeds the watermark data X in a plurality of embedding position candidates of the host data V, selects a candidate having a strong watermark resistance, and outputs it as final embedded host data W. Configurations common to the first embodiment are denoted by the same reference numerals, description thereof is omitted, and configurations and operations different from the first embodiment will be described.
[0097]
The embedded block selection unit 56 selects Q blocks from the host data V using the secret key K. If the size of each block is M × N, embedding candidates of Q × M × N samples are obtained. In the example of embedding a watermark in the DCT coefficient according to the first embodiment, the case where Q = 1, M = 8, and N = 8 has been described. However, in the present embodiment, these parameters are not specified. Give an explanation. The position detection unit 52 generates a scrambled embedding position P from the Q × M × N sample embedding candidates, and the embedding unit 54 uses the secret key K to watermark the embedding position P of the host data V. Data X is embedded and embedded host data W is output. The position detection unit 52 and the embedding unit 54 cooperate to generate a plurality of embedding positions P, embed the watermark data X in each embedding position P, generate a plurality of embedded host data W candidates, Has a function to select one.
[0098]
FIG. 18 is a functional configuration diagram of the position detection unit 52 and the embedding unit 54. The ECC unit 24 uses the watermark data X_bWatermark data X with error correction parity added_cIs generated. The position information generation unit 60 generates L embedding position P candidates for the Q blocks selected from the host data V by the embedding block selection unit 56. The position information generator 60 generates an initial embedded position P^*In contrast, L types of initial data C₀~ C_L-1By using the GS method described in the first embodiment, the initial embedding position P^*Are scrambled to generate L scrambled embedding position P candidates.
[0099]
The embedding unit 26 adds watermark data X to each of the L embedding positions P candidates._cAnd L types of embedded host data W candidates are generated. The SNR calculation unit 28 evaluates the resistance of the watermark data X for each of the L types of embedded host data W candidates, and the embedded host data W having the best resistance evaluation value is output from the selector 30. In this way, the optimum embedding position for embedding the watermark data X in the Q embedding blocks selected by the embedding block selection unit 56 is determined.
[0100]
FIG. 19 shows a configuration of decoding apparatus 70 according to Embodiment 3. This decoding apparatus uses the watermark data X embedded from the embedded host signal W ′._cTo extract this watermark data X_cWatermark data X that has been subjected to error decoding and error correction_bProcess to get.
[0101]
The embedded block selection unit 61 uses the secret key K to select Q blocks in which watermark data is embedded from the embedded host signal W ′. The position information generation unit 60 generates L embedding position P candidates for the Q blocks selected by the embedding block selection unit 61 in the same manner as the position information generation unit 60 in the encoding device 50 shown in FIG. To do. The L extraction units 42 use the secret key K to select L types of watermark data X embedded in the embedded host signal W ′ from the L embedded position P candidates given by the position information generation unit 60._cExtract candidates. Of the L candidates for the embedding position P, one candidate is the correct embedding position. The matched filter 62 is provided with L types of watermark data X_cThe correlation is calculated between the candidate and the assumed watermark data Y to obtain matching. Watermark data X having the highest correlation by the selector 64_cBy selecting a candidate, watermark data X at the correct embedding position_cIs obtained.
[0102]
Watermark data X_cThe error is corrected by the ECC decoding unit 44. The bit length restoration unit 48 uses the secret key K to generate the watermark data X_bAre restored and the original watermark information I is output.
[0103]
The assumed watermark data Y is given when the watermark data X embedded in the host data V is known in advance. For example, there is a case where the creator of the host data V is known in advance and it is confirmed whether or not the watermark data X of the creator is embedded in the host data V. In general, the present embodiment assumes that embedded digital watermark information is assumed in advance, but can be applied to the case where the embedded position of watermark data is given only as a candidate.
[0104]
According to the present embodiment, given media data to be embedded with a digital watermark, a position where the watermark data can be easily embedded can be detected according to the media data, and the watermark data can be embedded and embedded. Watermark resistance can be enhanced.
[0105]
Embodiment 4
FIG. 20 shows a configuration of encoding apparatus 10 according to Embodiment 4. In the present embodiment, digest data generated from the host data V is embedded in the host data V as a digital watermark. Configurations common to the encoding apparatus 10 of the first embodiment are denoted by the same reference numerals, description thereof is omitted, and configurations and operations different from those of the first embodiment are described.
[0106]
The digest generation unit 13 generates digest data that directly represents the characteristics of the block of the host data V selected by the embedded block selection unit 18. This digest data is data that is not broken even by compression encoding of the host data V. For example, when the host data V is an image, it is obtained from a low-frequency component when the image is converted into a spatial frequency component. The digest generation unit 13 hashes the digest data using a one-way function. When it is desired to increase security, the digest generation unit 13 further encrypts the digest data with the secret key K. The digest generation unit 13 outputs the digest data thus obtained as watermark data X. As in the first embodiment, the changing unit 14 scrambles the watermark data X and outputs the scrambled watermark data X ′, and the embedding unit 16 selects the embedding block selection unit 18 using the secret key K. The scrambled watermark data X ′ is embedded in the block of the host data V thus output, and the embedded host data W is output.
[0107]
FIG. 21 is a functional configuration diagram of the changing unit 14 and the embedding unit 16. A block of host data V selected by the embedded block selection unit 18 is input to the digest generation unit 13, digest data is generated by the digest generation unit 13, and watermark data X is output. The watermark data X is scrambled and embedded in a block of host data V as in the first embodiment, and embedded host data W is output. For the evaluation of the embedding strength of the watermark data X by the SNR calculation unit 28, the evaluation method assuming compression encoding such as JPEG2000 described in the second embodiment is used.
[0108]
FIG. 22 shows a configuration of decoding apparatus 40 according to Embodiment 4. A configuration and operation different from those of the decoding device 40 according to the first embodiment will be described. The digest generation unit 43 generates digest data from the block of the embedded host signal W ′ selected by the embedded block selection unit 41, and hashes the digest data using a one-way function. Further, in the digest generation unit 13 of the encoding device 10, when the embedded data is encrypted with the secret key K, the digest generation unit 43 further encrypts the digest data with the secret key K. The digest generation unit 13 gives the digest data thus obtained to the comparison unit 49.
[0109]
Similar to the first embodiment, the extraction unit 42 uses the secret key K to watermark data X ′ embedded in the block of the embedded host signal W ′ selected by the embedded block selection unit 41._cTo extract. The ECC decoding unit 44 uses the watermark data X ′._cError correction using the parity bit added to the watermark data X ′_bIs generated. The descrambler 46 uses the secret key K, and the watermark data X ′ after error correction._bUnscramble the watermark data X_bIs output. Watermark data X obtained in this way_bIs the hashed digest data.
[0110]
The comparison unit 49 compares the digest data generated by the digest generation unit 43 with the digest data extracted as a watermark by the processing after the extraction unit 42, thereby determining the presence or absence of falsification and outputting the determination result. The digest data embedded as a watermark is created from the block selected by the embedded block selection unit 41, and there is a mismatch in the digest data to be verified that the selected block has been tampered with. Therefore, it is possible to identify the block that has been tampered with along with the presence or absence of tampering. Thus, by determining the block for generating digest data from the beginning, it is possible to specify the approximate position where the alteration has been performed, along with the presence or absence of the alteration.
[0111]
In the present embodiment, the digest generation unit 43 encrypts the digest data. However, the digest generation unit 43 does not perform encryption, and a configuration in which an encryption decoder is installed immediately after the descrambler 46 is also possible. It is. In this case, the comparison unit 49 compares digest data that is not encrypted.
[0112]
A method for generating digest data from a block to be embedded with watermark data will be described with reference to FIGS. The watermark data embedding block is the DCT block of FIG. 7 described in the first embodiment or the set of wavelet transform coefficients of FIG. The value of the conversion coefficient of the embedded block is a_{i, j}Then, this conversion coefficient value a_{i, j}Can be used as digest data. As another method, the absolute value difference with the adjacent sample is calculated in three directions of vertical, horizontal, and diagonal in accordance with the following formula, and the value b rounded to a fixed number of bits_{i, j}May be used as a digest.
b_{i, j}= <| A_{i, j}-(A_{i + 1, j}+ A_{i, j + 1}+ A_{i + 1, j + 1}) / 3 |>_p
here<>_pIndicates an operation for rounding to upper p bits.
[0113]
FIG. 23A shows an example of a transform coefficient of a watermark data embedding block, and FIG. 23B shows a value after differential processing of the transform coefficient between adjacent samples as described above. In this example, the lower 5 bits are removed. By calculating the difference in this way, a large value can be obtained only in the edge portion of the image, and it becomes easy to detect tampering accompanied by a change in the edge such as addition or removal of an object in the image. Further, in an image including many flat portions such as a natural image, neighboring pixels often take very close values, and thus the value approaches 0 by taking a difference. Therefore, the number of bits necessary for the digest data can be suppressed.
[0114]
FIG. 24 is a diagram for explaining a bit configuration of a sample in which watermark data is embedded. Digest data is created using upper bits representing the characteristics of the sample. On the other hand, in order to embed the watermark data at a level that cannot be perceived by humans, it is preferable to embed the watermark data using lower bits that are not so much related to the characteristics of the sample. However, since the lower bits of the sample are dropped by quantization processing in compression encoding such as JPEG2000, the watermark data is embedded using the middle bits that are not dropped by quantization. Therefore, the sample is, from the MSB (Most Significant Bit) to the LSB (Least Significant Bit), in order from the top, bit A that can be used for digest, bit B that can be watermark embedded, and bit C that is omitted by quantization. Divided.
[0115]
JND (Just Noticeable Difference), which is the boundary between bit A that can be used for digest and bit B that can be embedded in watermark, is the limit of watermark embedding perceivable by humans defined by HVS (Human Visual System). If it is a bit, even if the watermark is embedded, it is not understood by human eyes. However, it is not necessary to use for digest and watermark embedding until the boundary of JND, and in order to increase the compression rate of host data V, bits A and A that can be used for digest are provided with some margin above and below the JND boundary. Bit B that can be embedded with a watermark may be determined.
[0116]
Since the digest data only needs to express the characteristics of the host data V, it can be generally composed of low-frequency components of the image. For example, in the case of wavelet transform coefficients, the LL subband of the lowest frequency layer is used as digest data. In the case of DCT coefficients, the low frequency component at the upper left of the DCT block is used as digest data. However, when digest data is generated from low-frequency components of an image, no trace of tampering remains in the digest data even if there is a fine tampering with a frequency higher than the spatial frequency. Therefore, in order to enable finer alteration detection, digest data may be generated using a high-frequency component in addition to the low-frequency component of the host data V.
[0117]
For example, in the case of a wavelet transform coefficient, digest data is generated using not only a low-frequency subband but also a high-frequency subband. Even in that case, as described above, bits higher than the boundary determined by JND may be used for digest data, and bits lower than the boundary may be used for embedding watermark data, but may be omitted due to quantization. Note that the lower number of bits to be played increases with higher frequency components.
[0118]
FIGS. 25A to 25C are bit configurations of wavelet transform coefficient samples in the third, second, and first subbands, respectively. The number of bits C to be omitted by quantization is 2 bits in the third layer, but increases to 3 bits in the second layer and 4 bits in the first layer. Will increase. Accordingly, if the number of bits B that can be embedded with a watermark is a fixed number of bits, the number of bits A that can be used for the digest becomes smaller as the frequency becomes higher.
[0119]
In the case of the DCT coefficient, the higher the frequency, the lower the DCT block. Digest data is generated using not only the upper left low frequency component of the DCT block but also the lower right high frequency component. At this time, the lower the right side of the DCT block is, the more bits are dropped due to quantization, and the number of bits usable for digest data is limited.
[0120]
According to the present embodiment, digest data generated from a specific block of host data can be embedded in a block of host data V as a watermark with enhanced durability. On the host data receiving side, it is possible to detect whether the host data has been tampered with by generating digest data from the host data and comparing it with the digest data extracted from the host data as a digital watermark.
[0121]
Since the digest data is robustly embedded as a watermark, the digest data extracted as the watermark is likely to be the same as the embedded data in the case of slight alteration that can be corrected by error correction. On the other hand, the digest data generated from the host data represents the characteristics of the host data, and originally has the property of being easily broken by the change of the host data. In particular, when hashing digest data with a one-way function, even a slight change can be very different. Therefore, it is possible to detect even a slight tampering by comparing a fragile digest with highly resistant watermark data.
[0122]
In addition, when there is a large alteration such that the watermark bit is broken, the digest data generated from the altered host data is significantly different from the original digest data. Of course, since the watermark data is also affected by the alteration, a part of the digest data to be compared extracted as a watermark is also destroyed and extracted by the alteration. However, since it is difficult to falsify so that both coincide by chance, the digest data generated from the falsified host data and the digest data extracted as a watermark do not match. It can be detected that tampering has occurred.
[0123]
Embodiment 5
FIG. 26 shows a configuration of encoding apparatus 10 according to Embodiment 5. The present embodiment is different from the fourth embodiment in that digest data is generated from the entire host data V without specifying a block of the host data V and embedded as a digital watermark. Configurations common to the encoding apparatus 10 of the fourth embodiment are denoted by the same reference numerals, description thereof is omitted, and configurations and operations different from those of the fourth embodiment are described.
[0124]
The digest generation unit 13 generates digest data that directly represents the characteristics of the host data V, and encrypts it with the secret key K if necessary. This digest data is extracted from the entire host data V. When a certain block of the host data V is changed, there is a correspondence relationship that the corresponding bit of the digest data is changed. It is configured to be able to identify tampering. The digest generation unit 13 outputs the digest data thus obtained as watermark data X. As in the fourth embodiment, the changing unit 14 scrambles the watermark data X and outputs the scrambled watermark data X ′, and the embedding unit 16 selects the embedding block selection unit 18 using the secret key K. The scrambled watermark data X ′ is embedded in the block of the host data V thus output, and the embedded host data W is output.
[0125]
FIG. 27 shows a configuration of decoding apparatus 40 according to the fifth embodiment. A configuration and operation different from the decoding device 40 of the fourth embodiment will be described. The digest generation unit 43 generates digest data from the embedded host signal W ′ and encrypts it with the secret key K. The digest generation unit 13 gives the digest data thus obtained to the comparison unit 49. The comparison unit 49 compares the digest data extracted as a watermark by the processing after the extraction unit 42 with the digest data generated by the digest generation unit 43, thereby determining whether or not the data has been tampered with, and outputs a determination result. Here, the digest data is extracted from the entire host data V as described above, is configured to be able to identify alteration of the block of the host data V, and is data that has not been hashed. If a bit that does not match is found, it is found that the corresponding block of host data V has been tampered with.
[0126]
The present invention has been described based on the embodiments. Those skilled in the art will understand that these embodiments are exemplifications, and that various modifications can be made to combinations of the respective constituent elements and processing processes, and such modifications are also within the scope of the present invention. By the way.
[0127]
As such a modification, the method of evaluating the embedding strength assuming a specific process in the second embodiment can be applied to the evaluation of the embedding strength in the third embodiment.
[0128]
In order to generate a plurality of watermark data candidates or embedding position candidates, a GS method capable of generating a variety of candidates is used. However, other scramble methods may be applied, or in some way. Candidate data may be randomly generated. In the embodiment, the original watermark data is reproduced from the generated watermark data candidates by descrambling. However, the table includes a table that associates the generated watermark data candidates with the original watermark data. , The original watermark data may be obtained.
[0129]
The identification data used as the initial data at the time of scrambling was inserted at the beginning of the watermark data and provided to the decoding side, but this identification data is not embedded in the watermark but is held as a secret key on the encoding side. , You may manage. In that case, the decryption side acquires the secret key and then descrambles the watermark data. In the third embodiment, when the identification data is obtained as a secret key on the decryption side, since the embedding position is specified from the secret key, the operation of detecting the embedding position by the matched filter 62 is not necessary, and is assumed in advance. There is no need to prepare watermark bits.
[0130]
As a modification of the first embodiment, the configuration and operation for generating and evaluating the sequential candidates have been described. However, the same sequential configuration and operation can be applied to any of the second to fifth embodiments. Needless to say, it can be done.
[0131]
Although the embedding position candidates are generated by the scramble method in the third embodiment, the embedding position candidates may be randomly generated by table matching described below. For this purpose, the digital watermark embedding side and the extraction side include a table in which identification data for identifying candidates for embedding positions and embedding positions are associated with each other. This table shows the first bit of the watermark data, for example, “if the identification number is 0, the position of (1,29), if the identification number is 1, the position of (983,251),..., The identification number 15 In this case, the correspondence between the identification number such as “embed at the position (542, 37)” and the embedded coordinates is stored. Correspondences with different embedding positions are also stored for the second to nth bits. The embedding position is randomly generated by some method. On the embedding side, by referring to this table, an embedding position candidate is generated in association with the embedding position candidate identification data, and watermark data is embedded at the candidate position. On the extraction side, by referring to this table based on the identification data of the candidate for the embedding position, the embedding position is specified, and the watermark data is extracted from the position. According to this method, the randomness of the embedding position is sufficiently ensured, and robust embedding can be realized. On the extraction side, if this table is not included other than the identification data of the candidate for the embedding position, the embedding position cannot be known, so that security can be improved.
[0132]
In the fifth embodiment, digest data is generated from bits higher than the boundary given by JND so that interference does not occur between bits used for digest data and bits used for watermark embedding. The digest data is also generated using the bit area used for embedding, and when the watermark is extracted and verified in the decoding device, the influence of the watermark embedding is adjusted and the digest data is compared. Good. In this case, the process of determining JND in the encoding device can be omitted.
[0133]
【The invention's effect】
According to the present invention, the tolerance of digital watermarking is improved and the watermark detection accuracy is improved.
[Brief description of the drawings]
FIG. 1 is a configuration diagram of an encoding apparatus according to Embodiment 1. FIG.
FIG. 2 is a functional configuration diagram of a changing unit and an embedding unit in FIG. 1;
3 is a configuration diagram of a decoding apparatus according to Embodiment 1. FIG.
FIG. 4 is a diagram illustrating a relationship between original watermark data and L types of scrambled watermark data.
FIG. 5 is a diagram illustrating a convolution operation at the time of encoding.
FIG. 6 is a diagram illustrating a convolution operation at the time of decoding.
FIG. 7 is a diagram illustrating an embedded block of watermark data in discrete cosine transformed host data.
FIG. 8 is a diagram illustrating a method of embedding scrambled watermark data in the block of FIG.
FIG. 9 is a diagram illustrating a set of wavelet transform coefficients in which watermark data is embedded in host data subjected to discrete wavelet transform.
10 is a diagram for explaining a method of embedding scrambled watermark data in the set of wavelet transform coefficients of FIG. 9. FIG.
FIG. 11 is a flowchart for explaining a digital watermark embedding procedure by the encoding apparatus.
FIG. 12 is a flowchart illustrating another digital watermark embedding procedure performed by the encoding apparatus.
FIG. 13 is a diagram for explaining a pair of embedded blocks of watermark data in the host data subjected to discrete cosine transform.
FIG. 14 is a diagram illustrating a pair of wavelet transform coefficient sets in which watermark data is embedded in host data subjected to discrete wavelet transform.
FIG. 15 is a configuration diagram of an encoding apparatus according to Embodiment 2.
16 is a functional configuration diagram of the changing unit and the embedding unit of FIG. 15;
FIG. 17 is a configuration diagram of an encoding apparatus according to Embodiment 3.
18 is a functional configuration diagram of the position detection unit and the embedding unit of FIG. 17;
FIG. 19 is a configuration diagram of a decoding apparatus according to Embodiment 3.
FIG. 20 is a configuration diagram of an encoding apparatus according to Embodiment 4.
FIG. 21 is a functional configuration diagram of the changing unit and the embedding unit of FIG. 20;
22 is a block diagram of a decoding apparatus according to Embodiment 4. FIG.
FIG. 23 is a diagram for describing a difference process between transform coefficients of watermark data embedded blocks;
FIG. 24 is a diagram illustrating a bit configuration of a sample in which watermark data is embedded.
FIG. 25 is a diagram illustrating the bit configuration of wavelet transform coefficients in which watermark data is embedded, by layer.
26 is a block diagram of an encoding apparatus according to Embodiment 5. FIG.
27 is a block diagram of a decoding apparatus according to Embodiment 5. FIG.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 10 encoding apparatus, 12-bit length expansion part, 13 digest production | generation part, 14 change part, 16 embedding part, 18 embedding block selection part, 20 multiplexer, 22 scrambler, 24 ECC part, 26 embedding part, 28 SNR calculation part, 29 weighted SNR calculation unit, 30 selector, 40 decoding device, 41 embedding block selection unit, 42 extraction unit, 44 ECC decoding unit, 46 descrambler, 49 comparison unit, 50 encoding device, 52 position detection unit, 54 embedding unit 56 embedded block selection unit, 60 position information generation unit, 61 embedded block selection unit, 62 matched filter, 64 selector, 70 decoding device.

Claims

The processor embeds a plurality of digital watermark data candidates generated by scrambling into a specified block of host data, evaluates the resistance of the watermark, and evaluates the watermark data having the best resistance evaluation value . An electronic watermark embedding method, comprising: obtaining host data in which candidates are embedded.

A block selection unit for selecting a specific block from the host data to be embedded with the digital watermark data;
A scramble unit that scrambles the digital watermark data to generate a plurality of watermark data candidates;
An embedding unit that embeds each of the plurality of watermark data candidates in the specific block of the host data selected by the block selection unit, and generates a plurality of embedded host data candidates;
For each of the plurality of embedded host data candidates, an evaluation unit that evaluates the resistance of the digital watermark;
And a selection unit that selects and outputs the embedded host data candidate having the best resistance evaluation value among the plurality of embedded host data candidates based on the resistance evaluation value. .

Selecting a specific block from the host data in which the watermark data is to be embedded;
Scrambling the digital watermark data to generate a plurality of watermark data candidates;
Embedding each of the plurality of watermark data candidates in the specific block of the host data selected by the block selection unit to generate a plurality of embedded host data candidates;
For each of the plurality of embedded host data candidates, evaluating the resistance of the digital watermark;
A computer program causing a computer to execute a step of selecting a candidate of embedded host data having the best resistance evaluation value from among the plurality of embedded host data candidates based on the resistance evaluation value .

By the processor, scrambles the digest data of the host data to generate a plurality of candidate electronic watermark data, evaluates the resistance of the electronic watermark in the case where the candidate of their watermark data is embedded in each of the host data, resistance A method for embedding a digital watermark, comprising obtaining the best evaluation value as host data in which the digest data is embedded.

5. The digital watermark embedding method according to claim 4 , wherein the digest data is generated using upper bit data that is not affected by quantization of the host data.

5. The digital watermark embedding method according to claim 4, wherein the digest data is generated using upper bit data not used for embedding the watermark data of the host data.

A digest generator for generating digest data of the host data;
A scramble unit that scrambles the digest data to generate a plurality of watermark data candidates;
An embedding unit that embeds each of the plurality of watermark data candidates in the host data and generates a plurality of embedded host data candidates;
For each of the plurality of embedded host data candidates, an evaluation unit that evaluates the resistance of the digital watermark;
And a selection unit that selects and outputs the embedded host data candidate having the best resistance evaluation value among the plurality of embedded host data candidates based on the resistance evaluation value. .

A block selection unit that selects a specific block from the host data; wherein the digest generation unit generates the digest data from the specific block of the host data; and the embedding unit includes the specific block of the host data. 8. The encoding apparatus according to claim 7 , wherein each of the plurality of watermark data candidates is embedded to generate the plurality of embedded host data candidates.

The encoding apparatus according to claim 7 or 8 , wherein the digest generation unit generates the digest data from a low-frequency component of the host data subjected to discrete wavelet transform.

The encoding apparatus according to claim 7 or 8 , wherein the digest generation unit generates the digest data from a low frequency component of the host data subjected to discrete cosine transform.

The encoding apparatus according to claim 7 or 8 , wherein the digest generation unit generates the digest data using upper bit data that is not affected by quantization of the host data.

The encoding apparatus according to claim 7 or 8 , wherein the digest generation unit generates the digest data using higher-order bit data that is not used for embedding the watermark data of the host data.

The digest generation unit generates the digest data from subbands of different layers of the host data subjected to discrete wavelet transform, and the bits used as the digest data are affected by quantization in the subbands of higher frequency layers. The encoding apparatus according to claim 7 or 8 , wherein the encoding apparatus is limited to higher-order bits.

The encoding apparatus according to claim 7 or 8 , wherein the digest generation unit generates the digest data after taking a difference between adjacent samples of the host data.

Generating digest data from host data;
Scrambling the generated digest data to generate a plurality of watermark data candidates;
Embedding each of the plurality of watermark data candidates in the host data to generate a plurality of embedded host data candidates;
For each of the plurality of embedded host data candidates, evaluating the resistance of the digital watermark;
A computer program causing a computer to execute a step of selecting a candidate of embedded host data having the best resistance evaluation value from among the plurality of embedded host data candidates based on the resistance evaluation value .