(57)【要約】【課題】電子透かしが埋め込まれたコンテンツデータにはさまざまな操作が加えられるため、電子透かしの耐性を強化しなければならない。【解決手段】マルチプレクサ２０は、透かしデータＸの先頭に異なる初期データを挿入してＬ種類のビット系列を生成する。スクランブラ２２はそのＬ種類のビット系列をそれぞれスクランブルして、Ｌ種類のスクランブルされた透かしデータＸ'を生成し、ＥＣＣ部２４はそれぞれに誤り訂正のためのパリティを付加する。埋め込みブロック選択部１８は、ホストデータＶから透かしデータＸ'を埋め込むべきブロックを選択する。埋め込み部２６は、Ｌ種類のスクランブルされた透かしデータＸ'のそれぞれをホストデータＶの選択されたブロックに埋め込み、ＳＮＲ計算部２８は、透かしの埋め込まれたホストデータＶのそれぞれについて、透かしデータＸの耐性を評価する。セレクタ３０は、耐性の最も強いものを選択し、最終的な埋め込みホストデータＷとして出力する。【選択図】        図２
2004163855.tif 000002
【特許請求の範囲】
【請求項１】
スクランブルして生成された複数の電子透かしデータの候補をホストデータの指定されたブロックに埋め込み、それらの電子透かしの耐性を評価して、その評価が良好である前記電子透かしデータの候補が埋め込まれたホストデータを取得することを特徴とする電子透かし埋め込み方法。
【請求項２】
電子透かしデータを埋め込むべきホストデータから複数のブロックを選択するブロック選択部と、
前記ブロック選択部により選択された前記複数のブロックの各々に異なる電子透かしデータを独立に埋め込む埋め込み部とを含むことを特徴とする符号化装置。
【請求項３】
前記ブロック選択部は、離散ウェーブレット変換によるフィルタリング処理が施された前記ホストデータの各サブバンドから同一の空間領域を構成するウェーブレット変換係数を選択し、それらの係数の集合を、前記電子透かしデータの埋め込みブロックとして用いることを特徴とする請求項２に記載の符号化装置。
【請求項４】
前記ブロック選択部は、前記ホストデータに離散コサイン変換によるフィルタリング処理を施したときに生成される離散コサイン変換係数を前記電子透かしデータの埋め込みブロックとして選択することを特徴とする請求項２に記載の符号化装置。
【請求項５】
電子透かしデータを埋め込むべきホストデータから特定のブロックを選択するブロック選択部と、
前記電子透かしデータをスクランブルして複数の透かしデータの候補を生成するスクランブル部と、
前記ブロック選択部により選択された前記ホストデータの前記特定のブロックに前記複数の透かしデータの候補のそれぞれを埋め込み、複数の埋め込みホストデータの候補を生成する埋め込み部と、
前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する評価部と、
前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択して出力する選択部とを含むことを特徴とする符号化装置。
【請求項６】
電子透かしデータを埋め込むべきホストデータのブロックを選択するブロック選択部と、
前記電子透かしデータが埋め込まれる前記ホストデータの前記ブロックの埋め込み位置の候補を複数生成する位置情報生成部と、
前記ブロック選択部により選択された前記ホストデータの前記ブロックの前記複数の埋め込み位置の候補のそれぞれに前記透かしデータを埋め込み、複数の埋め込みホストデータの候補を生成する埋め込み部と、
前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する評価部と、
前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択して出力する選択部とを含むことを特徴とする符号化装置。
【請求項７】
前記ブロック選択部は、前記特定のブロックとして、異なる周波数成分をもつ複数のブロックの組み合わせを選択することを特徴とする請求項５または６に記載の符号化装置。
【請求項８】
前記ブロック選択部は、前記特定のブロックとして、離れた位置にある複数のブロックの組み合わせを選択することを特徴とする請求項５または６に記載の符号化装置。
【請求項９】
前記評価部は、前記耐性を、前記ホストデータを前記透かしデータに対するノイズと見なした場合に計算されるＳＮ比により評価することを特徴とする請求項５または６に記載の符号化装置。
【請求項１０】
前記評価部は、前記埋め込みホストデータに対して有用性のある操作を施した上で、前記耐性を評価することを特徴とする請求項５から９のいずれかに記載の符号化装置。
【請求項１１】
前記評価部は、前記埋め込みホストデータを圧縮符号化する際の量子化誤差を考慮して前記耐性を評価することを特徴とする請求項５から９のいずれかに記載の符号化装置。
【請求項１２】
ホストデータから電子透かしの埋め込まれた複数のブロックを選択するブロック選択部と、
前記ブロック選択部により選択された前記複数のブロックの各々から独立にスクランブルされた透かしデータを抽出する抽出部と、
前記スクランブルされた透かしデータのスクランブルを解除するデスクランブル部とを含むことを特徴とする復号装置。
【請求項１３】
ホストデータから電子透かしの埋め込まれたブロックを選択するブロック選択部と、
電子透かしが埋め込まれた前記ホストデータの前記ブロックの埋め込み位置の候補を複数生成する位置情報生成部と、
前記複数の埋め込み位置の候補のそれぞれを用いて、前記ブロック選択部により選択された前記ホストデータの前記ブロックに埋め込まれた透かしデータの候補を複数抽出する抽出部と、
前記抽出された複数の透かしデータの候補を想定される透かしデータとの間で照合する照合部と、
前記照合部による照合結果に基づいて前記複数の透かしデータの候補の一つを選択して出力する選択部とを含むことを特徴とする復号装置。
【請求項１４】
電子透かしデータを埋め込むべきホストデータから特定のブロックを選択する工程と、
前記電子透かしデータをスクランブルして複数の透かしデータの候補を生成する工程と、
前記ブロック選択部により選択された前記ホストデータの前記特定のブロックに前記複数の透かしデータの候補のそれぞれを埋め込み、複数の埋め込みホストデータの候補を生成する工程と、
前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する工程と、
前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択する工程とをコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項１５】
ホストデータのダイジェストデータをスクランブルして複数の電子透かしデータの候補を生成し、それらの透かしデータの候補がそれぞれ前記ホストデータに埋め込まれた場合における当該電子透かしの耐性を評価し、その評価が良好であるものを前記ダイジェストデータが埋め込まれたホストデータとして取得することを特徴とする電子透かし埋め込み方法。
【請求項１６】
前記ダイジェストデータは、前記ホストデータの量子化の影響を受けない上位ビットのデータを用いて生成されることを特徴とする請求項１５に記載の電子透かし埋め込み方法。
【請求項１７】
前記ダイジェストデータは、前記ホストデータの前記透かしデータの埋め込みに利用されない上位ビットのデータを用いて生成されることを特徴とする請求項１５または１６に記載の電子透かし埋め込み方法。
【請求項１８】
ホストデータのダイジェストデータを生成するダイジェスト生成部と、
前記ダイジェストデータをスクランブルして複数の透かしデータの候補を生成するスクランブル部と、
前記複数の透かしデータの候補をそれぞれ前記ホストデータに埋め込み、複数の埋め込みホストデータの候補を生成する埋め込み部と、
前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する評価部と、
前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択して出力する選択部とを含むことを特徴とする符号化装置。
【請求項１９】
ホストデータから特定のブロックを選択するブロック選択部をさらに含み、前記ダイジェスト部は前記ホストデータの前記特定のブロックから前記ダイジェストデータを生成し、前記埋め込み部は、前記ホストデータの前記特定のブロックに前記複数の透かしデータの候補のそれぞれを埋め込み、前記複数の埋め込みホストデータの候補を生成することを特徴とする請求項１８に記載の符号化装置。
【請求項２０】
前記ダイジェスト生成部は、離散ウェーブレット変換された前記ホストデータの低周波成分から前記ダイジェストデータを生成することを特徴とする請求項１８または１９に記載の符号化装置。
【請求項２１】
前記ダイジェスト生成部は、離散コサイン変換された前記ホストデータの低周波成分から前記ダイジェストデータを生成することを特徴とする請求項１８または１９に記載の符号化装置。
【請求項２２】
前記ダイジェスト生成部は、前記ホストデータの量子化の影響を受けない上位ビットのデータを用いて前記ダイジェストデータを生成することを特徴とする請求項１８から２１のいずれかに記載の符号化装置。
【請求項２３】
前記ダイジェスト生成部は、前記ホストデータの前記透かしデータの埋め込みに利用されない上位ビットのデータを用いて前記ダイジェストデータを生成することを特徴とする請求項１８から２２のいずれかに記載の符号化装置。
【請求項２４】
前記ダイジェスト生成部は、離散ウェーブレット変換された前記ホストデータの異なる階層のサブバンドから前記ダイジェストデータを生成し、高周波の階層のサブバンドほど、前記ダイジェストデータとして利用するビットを量子化の影響を受けない、より上位のビットに制限することを特徴とする請求項１８または１９に記載の符号化装置。
【請求項２５】
前記ダイジェスト生成部は、前記ホストデータの隣接サンプル間で差分を取った上で前記ダイジェストデータを生成することを特徴とする請求項１８から２４のいずれかに記載の符号化装置。
【請求項２６】
ホストデータから電子透かしとして埋め込まれたダイジェストデータを抽出する抽出部と、
前記ホストデータからダイジェストデータを生成するダイジェスト生成部と、
前記ダイジェスト生成部により生成されたダイジェストデータを前記抽出部により抽出されたダイジェストデータと照合することにより、前記ホストデータに対する改ざんの有無とともに改ざんのおおまかな位置を特定する照合部とを含むことを特徴とする復号装置。
【請求項２７】
ホストデータから電子透かしの埋め込まれたブロックを選択するブロック選択部をさらに含み、前記抽出部は、前記ホストデータの前記ブロックから前記ダイジェストデータを抽出し、前記ダイジェスト生成部は、前記ホストデータの前記ブロックから前記ダイジェストデータを生成することを特徴とする請求項２６に記載の復号装置。
【請求項２８】
ホストデータからダイジェストデータを生成する工程と、
生成されたダイジェストデータをスクランブルして複数の透かしデータの候補を生成する工程と、
前記ホストデータに前記複数の透かしデータの候補のそれぞれを埋め込み、複数の埋め込みホストデータの候補を生成する工程と、
前記複数の埋め込みホストデータの候補の各々について、当該電子透かしの耐性を評価する工程と、
前記耐性の評価値に基づいて前記複数の埋め込みホストデータの候補の一つを選択する工程とをコンピュータに実行させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、電子透かし技術に関し、特に電子透かしの埋め込み方法、およびその方法を利用可能な符号化装置と復号装置に関する。
【０００２】
【従来の技術】
ここ数年、インターネット利用人口が急増し、インターネット利用の新たなステージともいえるブロードバンド時代に入ろうとしている。ブロードバンド通信では通信帯域が格段に広がるため、音声、静止画、動画などデータ量の大きいコンテンツの配信も気軽にできるようになる。このようなデジタルコンテンツの流通が盛んになると、コンテンツの著作権の保護がより一層求められることになる。
【０００３】
ネットワーク上に流通するコンテンツのデータは他人に容易にコピーされ、著作権に対する保護が十分ではないのが現状である。そこで著作権を保護するために、コンテンツの作成者や利用者の情報を電子透かしとしてコンテンツデータに埋め込む技術が開発されている。この電子透かし技術を用いることにより、ネットワーク上で流通するコンテンツデータから電子透かしを抽出して、不正利用を検出したり、不正コピーの流通経路を追跡することが可能となる。
【０００４】
従来の電子透かしの埋め込み技術には、電子透かし情報を埋め込む処理の自由度を維持しつつ、耐性の強い電子透かしの埋め込みを可能とするものがある（たとえば、特許文献１参照）。
【０００５】
また、従来のデジタル署名による画像認証技術には、画像に対するＪＰＥＧ（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）したときに得られるＤＣＴブロックを用いる場合、各サブセットｖ＋ｉ、ｖ−ｉのｍ個のサンプルデータは、透かしの埋め込み対象として選択された１つのＤＣＴブロックに含まれるｍ個のＤＣＴ係数である。図７は、埋め込みブロック選択部１８により選択される透かしデータＸ'の埋め込みブロックを説明する図である。同図のように、ＪＰＥＧで用いられている離散コサイン変換では、ホストデータＶの空間領域が縦横８ピクセルからなるブロックに分割され、それぞれのブロック内で各ピクセルが空間周波数成分に変換される。埋め込みブロック選択部１８は、透かしビット列ｘｋを埋め込むブロックとして、同図のようにＤＣＴブロック１２０を選択する。
【００６３】
図８は、８×８のＤＣＴブロック内の２ｍ個のＤＣＴ係数に透かしビットｘｋｉ（ｉ＝０，１，・・・，ｎ＋ｒ−１）が埋め込まれる様子を示している。各サブセットｖ＋ｉ、ｖ−ｉとして選ばれるそれぞれｍ個のＤＣＴ係数は、秘密鍵Ｋに基づいて選択される。このようにして（ｎ＋ｒ）ビットの透かしデータが同一のブロックに埋め込まれる。なお、上記の説明では透かし埋め込み対象のブロックとして１つのＤＣＴブロックを選択したが、埋め込み対象のブロックを、離散コサイン変換の最小処理単位であるＤＣＴブロックとする必要はなく、ある程度の大きさをもった分割領域であってもよい。その場合は、いくつかのＤＣＴブロックの集合を１つの埋め込み対象ブロックとみなして、同様の透かし埋め込み処理を行えばよい。
【００６４】
透かしデータの埋め込み対象のブロックの他の例として、ホストデータＶを離散ウェーブレット変換したときに得られるウェーブレット変換係数の集合を考える。図９は、離散ウェーブレット変換されたホストデータＶの各サブバンドから選択された、同一の空間領域を構成するウェーブレット変換係数の集合を説明する図である。同図に示すとおり、ホストデータＶは離散ウェーブレット変換により４つの周波数サブバンドへ分割される。これらのサブバンドは、縦横両方向において低周波成分を有するＬＬサブバンドと、縦横のいずれかひとつの方向において低周波成分を有し、かつもう一方の方向において高周波成分を有するＨＬおよびＬＨサブバンドと、縦横両方向において高周波成分を有するＨＨサブバンドである。各サブバンドの縦横のピクセル数は処理前のホストデータＶのそれぞれ１／２であり、一回のフィルタリングでサイズが１／４のサブバンドデータが得られる。
【００６５】
こうして得られたサブバンドのうち、ＬＬサブバンドに対して離散ウェーブレット変換によるフィルタリング処理が再度施され、さらにＬＬ、ＨＬ、ＬＨ、ＨＨの４つのサブバンドに分割される。このフィルタリングは所定の回数行われ、最後のフィルタリングで生じたＬＬサブバンドがホストデータＶのＤＣ成分に最も近いデータとなる。
【００６６】
離散ウェーブレット変換前のホストデータＶの特定の空間領域に対応するウェーブレット変換係数を各階層のサブバンドから選択すると、図９に示すように、ツリー構造のウェーブレット変換係数の集合１００〜１０９が得られる。すなわち第３階層のＬＬサブバンドＬＬ３、ＨＬサブバンドＨＬ３、ＬＨサブバンドＬＨ３、およびＨＨサブバンドＨＨ３からはそれぞれ１ピクセルからなるウェーブレット変換係数１００、１０１、１０２、および１０３が選択され、第２階層のＨＬサブバンドＨＬ２、ＬＨサブバンドＬＨ２およびＨＨサブバンドＨＨ２からはそれぞれ２×２のウェーブレット変換係数１０４、１０５および１０６が選択され、最後に第１階層のＨＬサブバンドＨＬ１、ＬＨサブバンドＬＨ１およびＨＨサブバンドＨＨ１からはそれぞれ４×４のウェーブレット変換係数１０７、１０８および１０９が選択される。これらのウェーブレット変換係数の集合は、離散ウェーブレット変換前のホストデータＶにおける特定の空間領域のデータが階層的に空間周波数成分に変換されたものである。したがって、これらのウェーブレット変換係数の集合を透かしデータＸ'の埋め込みブロックとして選択して透かしデータＸ'を埋め込むなら、透かしデータＸ'はホストデータＶの特定の空間領域に埋め込まれたことになる。各サブセットｖ＋ｉ、ｖ−ｉとしてこのようなツリー構造のウェーブレット変換係数の集合を用いてもよい。
【００６７】
図１０は、ウェーブレット変換係数の集合内の２ｍ個のウェーブレット変換係数に透かしビットｘｋｉが埋め込まれる様子を示している。図９の３つの階層から選択されたウェーブレット変換係数を集めると、図１０のように８×８のウェーブレット変換係数の集合１１０が得られる。ウェーブレット変換の階層数をＨとすると、２Ｈ×２Ｈのウェーブレット変換係数のマトリックスが得られる。もっともこれは、最小サイズの埋め込みブロックを説明したものであり、ホストデータＶの透かし埋め込み領域として、ある程度の大きさをもった分割領域を選択すると、その領域に対応するウェーブレット変換係数のマトリックスのサイズは当然大きくなる。こうして得られるウェーブレット変換係数のマトリックスを埋め込みブロックとして扱い、この埋め込みブロック内のｍ個のウェーブレット変換係数に透かしビットｘｋｉ（ｉ＝０，１，・・・，ｎ＋ｒ−１）を図８と同様の方法で埋め込む。
【００６８】
図１１に戻り、ＳＮＲ計算部２８は、Ｌ種類の埋め込みホストデータの候補Ｗｋに対して透かしデータｘｋの耐性、すなわち埋め込み強度を評価し（Ｓ１６）、セレクタ３０は埋め込み強度が最大となる埋め込みホストデータの候補Ｗｋを最終的な埋め込みホストデータＷとして選択する（Ｓ１８）。
【００６９】
埋め込み強度の評価式を与える前に、埋め込みホストデータＷに対して信号処理や画像処理などにより変形が加えられた場合に、透かしデータＸ'がどのように検出されるかを検討する。埋め込みホストデータＷに加えられる変形をノイズＮとして扱い、ノイズＮが加わった埋め込みホストデータＷを埋め込みホスト信号Ｗ'と呼ぶ。この埋め込みホスト信号Ｗ'から透かしデータＸ'を抽出する方法を説明する。埋め込みホスト信号の集合のペア（Ｗ'＋，Ｗ'−）を次のように定義する。埋め込みホスト信号の集合Ｗ'＋，Ｗ'−は次のようにそれぞれ（ｎ＋ｒ）個の要素をもつ。
【００７０】
Ｗ'＋＝｛ｗ'＋０，ｗ'＋１，・・・，ｗ'＋ｎ＋ｒ−１｝
Ｗ'−＝｛ｗ'−０，ｗ'−１，・・・，ｗ'−ｎ＋ｒ−１｝
ここで埋め込みホスト信号の集合Ｗ'＋，Ｗ'−の要素である各サブセットｗ'＋ｉ、ｗ'−ｉは、電子透かしの埋め込み位置に対応して、次のように埋め込みホスト信号Ｗ'のｍ個のサンプルデータからなる。
ｗ'＋ｉ＝｛ｗ'＋ｉ，０，ｗ'＋ｉ，１，・・・，ｗ'＋ｉ，ｍ−１｝
ｗ'−ｉ＝｛ｗ'−ｉ，０，ｗ'−ｉ，１，・・・，ｗ'−ｉ，ｍ−１｝
【００７１】
透かしビットｘｋｉを検出するために、次の判定値ｚｉを計算する。
2004163855.tif 000003
ここでΣｊ＝０ｍ−１（ｖ＋ｉ，ｊ−ｖ−ｉ，ｊ）はｍが十分に大きいとき、一般にガウス分布に従い、０に近づく。またノイズの項Σｊ＝０ｍ−１（ｎ＋ｉ，ｊ−ｎ−ｉ，ｊ）についても同様に０に近づく。したがって、ｚｉはΣｊ＝０ｍ−１［（α＋ｉ，ｊ＋α−ｉ，ｊ）・ｘｋｉ］の値で近似できる。（α＋ｉ，ｊ＋α−ｉ，ｊ）は正であるから、透かしビットｘｋｉが１ならばｚｉは正であり、透かしビットｘｋｉが−１ならばｚｉは負である。したがってｚｉの正負により透かしビットｘｋｉの値を判定することができる。
【００７２】
埋め込み強度の評価は、ホストデータＶを透かしデータＸに対するノイズとみなして、埋め込まれた透かしデータｘｋに対して検出される透かしデータの分散を計算することにより行われる。分散が小さいほど、耐性が強いと考えることができる。埋め込みホストデータの候補のペア（Ｗ＋ｋ，Ｗ−ｋ）に対して次式によりＳＮ比を評価して、最適な候補Ｋを選択する。
【００７３】
Ｋ＝ａｒｇｍａｘｋ（Ｐｋ／（２σｋ２））
Ｐｋ＝Σｉ＝０ｎ＋ｒ−１｜Σｊ＝０ｍ−１（ｗ＋ｋｉ，ｊ−ｗ−ｋｉ，ｊ）｜２／（ｎ＋ｒ）
σｋ２＝Σｉ＝０ｎ＋ｒ−１｜Σｊ＝０ｍ−１（ｗ＋ｋｉ，ｊ−ｗ−ｋｉ，ｊ）−Ｐｋ１／２・ｘｋｉ｜２／（ｎ＋ｒ）
【００７４】
透かしビットｘｋｉが｛１，−１｝のいずれであるかを判定するための前述の判定値ｚｉは、埋め込みホストデータＷにノイズが付加される前の状態では、ｚｉ＝Σｊ＝０ｍ−１（ｗ＋ｋｉ，ｊ−ｗ−ｋｉ，ｊ）で与えられることを考慮すると、分散σｋ２は、透かしビットに関する検出値ｚｉと実際に埋め込まれた透かしビットの平均値Ｐｋ１／２・ｘｋｉとの差の自乗をｉ＝０，・・・，ｎ＋ｒ−１について評価して平均化したものであると言える。ただし、Ｐｋは検出値ｚｉのｉ＝０，・・・，ｎ＋ｒ−１についての自乗平均であり、埋め込まれた透かしの平均パワーを示す。したがって、埋め込まれた透かしデータｘｋと抽出される透かしデータとの間のユークリッド距離が小さく、透かしビットを検出するための判定値の絶対値が大きいほど、Ｐｋ／（２σｋ２）の値は大きくなる。言い換えれば、Ｐｋ／（２σｋ２）が最大となる候補を選択することは、透かしビットの検出誤差が最小である候補を選択することを意味する。
【００７５】
判定値ｚｉについて、ｖ＋ｉ，ｊ＞ｖ＋ｉ，ｊかつｘｋｉ＝１ならばｚｉ＞＞０となり、ｖ＋ｉ，ｊ＜ｖ＋ｉ，ｊかつｘｋｉ＝−１ならばｚｉ＜＜０となる。したがって前述の評価により最適な透かしデータｘｋの候補を選択することは、判定値ｚｉによる透かしビットｘｋｉの検出性能を向上させるために、ｖ＋ｉ，ｊ＞ｖ＋ｉ，ｊならばｘ'ｉ＝１となり、ｖ＋ｉ，ｊ＜ｖ＋ｉ，ｊならばｘ'ｉ＝−１となるように、元の透かしビットｘｉをｘ'ｉに変更することを意味する。これがＧＳ方式のガイディングルールであり、これにより判定値ｚｉのレスポンスが改善する。
【００７６】
復号装置４０の抽出部４２は、ノイズの付加された埋め込みホスト信号Ｗ'を受け取ると、ＥＣＣ復号部４４が硬入力の復号器で構成される場合には、判定値ｚｉを次のように計算し、判定値ｚｉの正負で、透かしビットｘ'が｛−１，１｝のいずれであるかを判定し、透かしデータＸ'を得る。また、ＥＣＣ復号部４４が軟入力の復号器で構成される場合には、判定値ｚｉを｛−１，１｝に硬判定することなく、そのまま、ＥＣＣ復号部４４に送る。
【００７７】
2004163855.tif 000004
【００７８】
抽出された透かしデータＸ'はさらにＥＣＣ復号部４４により誤り訂正がなされ、デスクランブラ４６によりスクランブルを解除され、元の透かしデータＸが得られる。
【００７９】
以上述べたように、実施の形態によれば、ＧＳ方式を用いて、電子透かしを埋め込む画像や音声などのメディアデータが与えられると、透かしビット系列をそのメディアデータに埋め込みやすいビット系列に変換した上で埋め込むことができる。したがって信号処理、幾何変換、圧縮、データの改ざんなどに対する電子透かしの耐性を強化することができ、透かしの検出精度が大幅に改善する。また透かしビットの埋め込み対象として特定のブロックを選択し、ブロックごとに独立に、透かしビットを埋め込むため、ブロックごとに透かしの検出を行うことで、ブロック単位で改ざんの有無を調べることができる。したがって、画像の特定の部分を変更したり、オブジェクトを新たに追加するなどの改ざんが行われた箇所をブロック単位で検出可能となる。
【００８０】
上記の実施の形態では、図２で示したように、Ｌ種類の透かしデータの候補を生成するために、Ｌ個のマルチプレクサ２０、スクランブラ２２、ＥＣＣ部２４、埋め込み部２６、およびＳＮＲ計算部２８が並列に設けられたが、これらの部材を単一構成にして、Ｌ種類の透かしデータの候補を逐次的に生成、評価して最適な候補を選択してもよい。
【００８１】
図１２は、そのような逐次型の電子透かしの埋め込み手順を説明するフローチャートである。埋め込みブロック選択部１８は、ホストデータＶから透かしデータを埋め込むべきブロックをあらかじめ選択する（Ｓ１９）。変数ｉを１に初期化する（Ｓ２０）。マルチプレクサ２０は、暗号化部１２により暗号化された透かしデータＸの先頭にｉ番目の初期データを挿入して符号系列を生成し（Ｓ２２）、スクランブラ２２は、その符号系列をスクランブルして、ｉ番目のスクランブルされた透かしデータＸ'を生成する（Ｓ２４）。スクランブラ２２によって生成されたｉ番目のスクランブルされた透かしデータＸ'は、必要に応じてＥＣＣ部２４により誤り訂正のためのパリティを付加された後に、埋め込み部２６によりホストデータＶの選択されたブロックに埋め込まれる（Ｓ２６）。ＳＮＲ計算部２８は、ｉ番目の埋め込みホストデータの候補Ｗｉに対して透かしデータｘｉの耐性、すなわち埋め込み強度Ｓｉを評価する（Ｓ２８）。セレクタ３０は、埋め込み強度Ｓｉが最低の評価値を保証する基準値Ｔより大きいかどうかを判定する（Ｓ３０）。もし埋め込み強度Ｓｉが基準値Ｔより大きければ（Ｓ３０のＹ）、変数Ｋに現在の変数ｉの値を代入し（Ｓ３２）、Ｋ番目の埋め込みホストデータの候補を最終的な埋め込みホストデータＷとして選択する（Ｓ４０）。埋め込み強度Ｓｉが基準値Ｔ以下の場合（Ｓ３０のＮ）、現在の変数ｉの値がＬに等しいなら（Ｓ３４のＹ）、これまで調べた埋め込み強度Ｓｋの値が最大となる添え字ｋを変数Ｋに代入し（Ｓ３８）、Ｋ番目の埋め込みホストデータの候補を最終的な埋め込みホストデータＷとして選択する（Ｓ４０）。現在の変数ｉの値がＬより小さいなら（Ｓ３４のＮ）、変数ｉを１だけインクリメントして（Ｓ３６）、ステップＳ２２に戻る。
【００８２】
この繰り返し処理により、埋め込み強度が所望の基準値以上である候補が得られた時点で、その候補を最終的な埋め込みホストデータＷとして選択し、そのような候補が生成されなければ、Ｌ個の埋め込みホストデータの候補を生成して、その中から埋め込み強度が最大であるものを最終的な埋め込みホストデータＷとして選択することができる。
【００８３】
上記の説明では、埋め込みブロック選択部１８は、透かしビット列ｘｋを埋め込むブロックとして１つのブロックを選択した。しかしながら選択されたブロックが背景画像や単調な画像である場合には、高周波成分が少なく透かしデータの埋め込みが困難である場合もある。そこで埋め込みブロック選択部１８は、透かしビット列ｘｋの埋め込み対象として、２つ以上のブロックを組み合わせて選択してもよい。この場合、２つ以上のブロックに透かしビット列ｘｋが埋め込まれるため、組み合わせのブロックのいずれかで改ざんが行われたかどうかを検出することができるが、いずれのブロックであるかは特定できない。
【００８４】
図１３は、離散コサイン変換されたホストデータＶから選択された２つのＤＣＴブロック１２０および１３０を示す。たとえば一方のＤＣＴブロック１２０は透かしデータが埋め込み難い低周波成分を主に含み、他方のＤＣＴブロック１３０は透かしデータを埋め込み易い高周波成分を主に含むといった組み合わせを選択する。ＤＣＴブロックに含まれる周波数成分はＤＣＴ係数をもとに判断してもよく、またＤＣＴブロック内のピクセル値の分散に基づいて判断してもよい。また、隣接するブロックは互いに似た周波数成分をもつことが多いため、位置がなるべく離れたブロックを組み合わせてもよい。またこのような組み合わせブロックはランダムに選択されてもよい。ブロックの組み合わせを透かしデータの埋め込み単位とすることにより、ブロック間での埋め込み強度の違いを吸収して、埋め込み強度の平均化を図ることができる。
【００８５】
図１４は、離散ウェーブレット変換されたホストデータＶから選択された２つのウェーブレット変換係数の集合を示す。図９で説明した離散ウェーブレット変換前のホストデータＶの特定の空間領域に対応するウェーブレット変換係数の集合１００〜１０９の他に、ホストデータＶの別の特定の空間領域に対応するウェーブレット変換係数の集合２００〜２０９が図１４に斜線を付けて示されている。これら２つのウェーブレット変換係数の集合は、図１３のＤＣＴブロックの組み合わせと同様、たとえば低周波成分を多く含む空間領域と高周波成分を多く含む空間領域にそれぞれ対応している。
【００８６】
図１３および図１４で説明した埋め込みブロックの組み合わせは、秘密鍵Ｋに基づいて決定されるため、復号装置４０の埋め込みブロック選択部４１は、秘密鍵Ｋを用いて、透かしデータＸ'が埋め込まれたブロックを選択することができる。すなわち秘密鍵Ｋにより、復号装置４０は、符号化装置１０が埋め込んだブロックの組み合わせと同一のブロックの組み合わせを特定することが可能である。
【００８７】
さらに別のブロックの組み合わせ方法として、埋め込みブロック選択部１８は、何らかの特徴量にもとづいて互いに異なる特徴をもつブロックを選択して組み合わせてもよい。たとえばピクセル値の分散などの特徴量を評価して、物体の表面のようなテクスチャタイプのブロックと、背景のようにフラットなタイプのブロックとを組み合わせてもよい。
【００８８】
このように特徴量にもとづいて組み合わせブロックを選択した場合、復号装置４０の埋め込みブロック選択部４１において、同様の特徴量を評価して埋め込みブロックを正しく選択することは難しくなる。なぜなら、改ざんによりこのような特徴量は一般に変化するからである。このように特徴量にもとづいて組み合わせブロックを選択した場合、埋め込みブロックを特定するための情報を秘密鍵として復号装置４０に送信することで対処することができる。あるいは復号装置４０の埋め込みブロック選択部４１が特徴量にもとづいて埋め込みブロックを決定することにして、多くのブロックにおいて透かしデータが正しく抽出できなかった場合には、改ざんがあったと判定することにしてもよい。もっとも、この場合にはブロック単位で改ざんを検出することはできず、単に改ざんの有無を検出することができるだけになる。
【００８９】
実施の形態２
図１５は実施の形態２に係る符号化装置１１の構成を示す。本実施の形態では、電子透かしの埋め込まれたホストデータＶが受ける圧縮符号化などの特定の処理をあらかじめ想定し、透かしの埋め込み時にその特定の処理による影響を考慮して、電子透かしに耐性をもたせる。実施の形態１と共通する構成については同一符号を付して説明を省き、実施の形態１とは異なる構成と動作について説明する。
【００９０】
変更部１５は、透かしデータＸをスクランブルする際、ホストデータＶが受ける特定の処理による歪みＤを考慮して耐性の強い透かしデータのビット系列を選択し、スクランブルされた透かしデータＸ'を出力する。図１６は変更部１５と埋め込み部１６の機能構成図である。重みつきＳＮＲ計算部２９は、Ｌ種類のスクランブルされた透かしデータＸ'ｃが埋め込まれたホストデータＷの候補について、透かしデータＸの耐性を評価する際に、特定の処理により想定される歪みＤを考慮に入れる。具体的には、埋め込まれた透かしデータと検出される透かしデータとの間のＳＮＲにより埋め込み強度を評価する際に、埋め込みホストデータＷに対する特定の処理による劣化を考慮した以下の重み付けＳＮＲを用いる。
【００９１】
Ｋ＝ａｒｇｍａｘｋ（Ｐｋ／（２σｋ２））
Ｐｋ＝Σｉ＝０ｎ＋ｒ−１｜Σｊ＝０ｍ−１（ｗ＊＋ｋｉ，ｊ−ｗ＊−ｋｉ，ｊ）｜２／（ｎ＋ｒ）
σｋ２＝Σｉ＝０ｎ＋ｒ−１｜Σｊ＝０ｍ−１（ｗ＊＋ｋｉ，ｊ−ｗ＊−ｋｉ，ｊ）−Ｐｋ１／２・ｘｋｉ｜２／（ｎ＋ｒ）
ここでｗ＊＋ｋｉ，ｊ、ｗ＊−ｋｉ，ｊは特定の処理がなされた後の埋め込みホストデータＷである。特定の処理がたとえばＪＰＥＧ２０００による圧縮であると分かっている場合、ｗ＊＋ｋｉ，ｊ、ｗ＊−ｋｉ，ｊはＪＰＥＧ２０００の量子化方法を用いて計算することができる。
【００９２】
ＪＰＥＧ２０００の規格書「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）により定められる人間が知覚できる限界の透かし埋め込みレベルであり、これより下位のビットであれば、透かしを埋め込んでも人間の目ではわからない。もっとも、ＪＮＤの境界ぎりぎりまで、ダイジェストや透かし埋め込みに利用する必要はなく、ホストデータＶの圧縮率を上げるため、ＪＮＤの境界の上下に多少の余裕をもたせて、ダイジェストに使用可能なビットＡおよび透かし埋め込み可能なビットＢを決めてもよい。
【０１１６】
ダイジェストデータはホストデータＶの特徴を端的に表すものであればよいため、一般には画像の低周波成分により構成することができる。たとえば、ウェーブレット変換係数の場合は、もっとも低周波の階層のＬＬサブバンドをダイジェストデータとする。ＤＣＴ係数の場合は、ＤＣＴブロックの左上の低周波成分をダイジェストデータとする。しかしながら、画像の低周波成分からダイジェストデータを生成した場合、その空間周波数よりも高い周波数をもつ細かな改ざんがあっても、ダイジェストデータには改ざんの痕跡が残らない。そこで、より細かい改ざんの検出を可能とするため、ホストデータＶの低周波成分以外に高周波成分も用いてダイジェストデータを生成してもよい。
【０１１７】
たとえば、ウェーブレット変換係数の場合、低周波の階層のサブバンドだけでなく、高周波の階層のサブバンドも用いて、ダイジェストデータを生成する。その場合でも、上述のように、ＪＮＤで決まる境界より上位のビットをダイジェストデータに利用し、境界より下位で量子化により省略されないビットを透かしデータの埋め込みに利用すればよいが、量子化により省略される下位のビット数は高周波成分ほど多くなることに注意する。
【０１１８】
図２５（ａ）〜（ｃ）は、それぞれ、第３階層、第２階層、第１階層のサブバンドにおけるウェーブレット変換係数のサンプルのビット構成である。量子化により省略されるビットＣは、第３階層では２ビットであるが、第２階層では３ビット、第１階層では４ビットに増えており、高周波成分になるほど量子化の影響を受けるビット数は増えていく。これに伴い、透かし埋め込み可能なビットＢを固定ビット数とすると、ダイジェストに使用可能なビットＡのビット数は高周波成分になるほど少なくなる。
【０１１９】
ＤＣＴ係数の場合は、ＤＣＴブロックの右下に行くほど高周波成分になる。ＤＣＴブロックの左上の低周波成分だけでなく、右下の高周波成分も利用してダイジェストデータを生成する。このとき、ＤＣＴブロックの右下に行くほど、量子化により落とされるビット数が増え、ダイジェストデータに使用可能なビット数は制限される。
【０１２０】
本実施の形態によれば、ホストデータの特定のブロックから生成したダイジェストデータを耐性の強化された透かしとしてホストデータＶのブロックに埋め込むことができる。ホストデータを受け取った側では、ホストデータからダイジェストデータを生成し、ホストデータから電子透かしとして抽出されるダイジェストデータと照合することにより、ホストデータの改ざんの有無を検出することができる。
【０１２１】
ダイジェストデータは透かしとしてロバストに埋め込まれているため、誤り訂正により訂正可能な程度の軽度の改ざんの場合は、透かしとして抽出されるダイジェストデータは埋め込まれたものと同じものとなる可能性が高い。一方、ホストデータから生成されるダイジェストデータは、ホストデータの特徴を表したものであり、もともとホストデータの変更により壊れやすい性質をもつため、軽度の改ざんでも異なったものになる。特にダイジェストデータを一方向性関数でハッシングする場合は、わずかの変更でも大きく異なったものになる。したがって、壊れやすいダイジェストと、耐性の強い透かしデータとの比較により、軽度の改ざんでも検出することができる。
【０１２２】
また、透かしビットが壊されるような大きな改ざんがあった場合には、改ざんされたホストデータから生成されるダイジェストデータは、本来のダイジェストデータとは大きく異なるものになる。また、当然、透かしデータも改ざんの影響を受けるので、透かしとして抽出される比較対象のダイジェストデータも改ざんにより一部が破壊されて抽出されることになる。しかし、両者が偶然に一致するように改ざんすることは困難であり、改ざんのあったホストデータから生成されるダイジェストデータと、透かしとして抽出されるダイジェストデータとは一致しないことから、この場合にも改ざんがあったことを検出することができる。
【０１２３】
実施の形態５
図２６は実施の形態５に係る符号化装置１０の構成を示す。本実施の形態では、ホストデータＶのブロックを特定することなく、ホストデータＶ全体からダイジェストデータを生成して、電子透かしとして埋め込む点が、実施の形態４とは異なる。実施の形態４の符号化装置１０と共通する構成については同一符号を付して説明を省き、実施の形態４とは異なる構成と動作について説明する。
【０１２４】
ダイジェスト生成部１３は、ホストデータＶの特徴を端的に表したダイジェストデータを生成し、必要であれば秘密鍵Ｋにより暗号化する。このダイジェストデータは、ホストデータＶ全体から抽出されたものであり、ホストデータＶのあるブロックが変更されると、ダイジェストデータの対応するビットが変更されるという対応関係があり、ホストデータＶのブロックの改ざんを識別可能に構成されている。ダイジェスト生成部１３はこうして得られるダイジェストデータを透かしデータＸとして出力する。実施の形態４と同様に、変更部１４は、透かしデータＸをスクランブルし、スクランブルされた透かしデータＸ'を出力し、埋め込み部１６は、秘密鍵Ｋを用いて、埋め込みブロック選択部１８により選択されたホストデータＶのブロックにスクランブルされた透かしデータＸ'を埋め込み、埋め込みホストデータＷを出力する。
【０１２５】
図２７は実施の形態５に係る復号装置４０の構成を示す。実施の形態４の復号装置４０とは異なる構成と動作について説明する。ダイジェスト生成部４３は、埋め込みホスト信号Ｗ'からダイジェストデータを生成し、秘密鍵Ｋにより暗号化する。ダイジェスト生成部１３はこうして得られるダイジェストデータを比較部４９に与える。比較部４９は、抽出部４２以降の処理により透かしとして抽出されたダイジェストデータを、ダイジェスト生成部４３により生成されたダイジェストデータと照合することにより、改ざんの有無を判定し、判定結果を出力する。ここで、ダイジェストデータは、前述のようにホストデータＶの全体から抽出され、ホストデータＶのブロックの改ざんを識別可能に構成されており、またハッシングされていないデータであるため、照合によりダイジェストデータに不一致のあるビットが見つかると、それに対応するホストデータＶのブロックが改ざんされていることがわかる。
【０１２６】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【０１２７】
そのような変形例として、実施の形態２における特定の処理を想定して埋め込み強度を評価する方法は、実施の形態３における埋め込み強度の評価の際にも適用することができる。
【０１２８】
複数の透かしデータの候補または埋め込み位置の候補を生成するために、多様性に富んだ候補の生成が可能なＧＳ方式を用いたが、他のスクランブル方式を適用してもよく、また何らかの方法でランダムに候補のデータを生成してもよい。また実施の形態では、逆スクランブルにより、生成された透かしデータの候補から元の透かしデータを再現したが、生成された透かしデータの候補と元の透かしデータとを対応づけたテーブルを備え、このテーブルを参照して元の透かしデータを求めてもよい。
【０１２９】
またスクランブルの際に初期データとして使用した識別データは、透かしデータの先頭に挿入されて復号側に提供されていたが、この識別データを透かしには埋め込まずに、符号化側で秘密鍵として保持、管理してもよい。その場合、復号側はこの秘密鍵を取得した上で、透かしデータのスクランブルを解除する。また実施の形態３では、復号側でこの識別データを秘密鍵として入手する場合は、埋め込み位置が秘密鍵から特定されるため、整合フィルタ６２による埋め込み位置の検出作業が不要となり、したがってあらかじめ想定される透かしビットを用意しておく必要もなくなる。
【０１３０】
なお、実施の形態１の変形として、逐次型の候補の生成、評価のための構成と動作を説明したが、同様の逐次型の構成と動作が、実施の形態２から５のいずれにも適用できることはいうまでもない。
【０１３１】
実施の形態３では、埋め込み位置の候補をスクランブル方式により生成したが、埋め込み位置の候補を次に述べるテーブルマッチングによりランダムに生成してもよい。このために、電子透かしの埋め込み側と抽出側は、埋め込み位置の候補を識別するための識別データと埋め込む位置とを対応づけたテーブルを備える。このテーブルは、透かしデータの第１ビットについて、たとえば、「識別番号０の場合は（１，２９）の位置、識別番号１の場合は（９８３，２５１）の位置、・・・、識別番号１５の場合は（５４２，３７）の位置に埋め込む」といった識別番号と埋め込み座標との対応関係を格納する。第２番目から第ｎ番目のビットについてもそれぞれ埋め込み位置が異なる対応関係が格納される。埋め込み位置は何らかの方法でランダムに生成される。埋め込み側では、このテーブルを参照して、埋め込み位置の候補の識別データに対応づけて埋め込み位置の候補を生成し、透かしデータをその候補の位置に埋め込む。抽出側では、埋め込み位置の候補の識別データにもとづいてこのテーブルを参照することにより、埋め込み位置を特定し、透かしデータをその位置から抽出する。この方法によれば、埋め込み位置のランダム性が十分に保証され、頑強な埋め込みを実現することができる。また抽出側では、埋め込み位置の候補の識別データ以外にこのテーブルをもっていなければ、埋め込み位置を知ることができないため、セキュリティを高めることができる。
【０１３２】
実施の形態５では、ダイジェストデータに使用されるビットと透かし埋め込みに使用されるビットの間で干渉が起こらないように、ＪＮＤで与えられる境界よりも上位のビットからダイジェストデータを生成したが、透かし埋め込みに利用されるビットの領域も利用してダイジェストデータを生成し、復号装置において透かしを抽出して照合する際に、透かし埋め込みによる影響分を調整してダイジェストデータの比較を行うようにしてもよい。この場合、符号化装置においてＪＮＤを決める処理を省略することができる。
【０１３３】
【発明の効果】
本発明によれば、電子透かしの耐性が向上し、透かしの検出精度が改善する。
【図面の簡単な説明】
【図１】実施の形態１に係る符号化装置の構成図である。
【図２】図１の変更部と埋め込み部の機能構成図である。
【図３】実施の形態１に係る復号装置の構成図である。
【図４】元の透かしデータとＬ種類のスクランブルされた透かしデータとの関係を説明する図である。
【図５】符号化時の畳み込み演算を説明する図である。
【図６】復号時の畳み込み演算を説明する図である。
【図７】離散コサイン変換されたホストデータにおける透かしデータの埋め込みブロックを説明する図である。
【図８】図７のブロックにスクランブルされた透かしデータを埋め込む方法を説明する図である。
【図９】離散ウェーブレット変換されたホストデータにおける、透かしデータが埋め込まれるウェーブレット変換係数の集合を説明する図である。
【図１０】図９のウェーブレット変換係数の集合にスクランブルされた透かしデータを埋め込む方法を説明する図である。
【図１１】符号化装置による電子透かしの埋め込み手順を説明するフローチャートである。
【図１２】符号化装置による別の電子透かしの埋め込み手順を説明するフローチャートである。
【図１３】離散コサイン変換されたホストデータにおける透かしデータの埋め込みブロックのペアを説明する図である。
【図１４】離散ウェーブレット変換されたホストデータにおける、透かしデータが埋め込まれるウェーブレット変換係数の集合のペアを説明する図である。
【図１５】実施の形態２に係る符号化装置の構成図である。
【図１６】図１５の変更部と埋め込み部の機能構成図である。
【図１７】実施の形態３に係る符号化装置の構成図である。
【図１８】図１７の位置検出部と埋め込み部の機能構成図である。
【図１９】実施の形態３に係る復号装置の構成図である。
【図２０】実施の形態４に係る符号化装置の構成図である。
【図２１】図２０の変更部と埋め込み部の機能構成図である。
【図２２】実施の形態４に係る復号装置の構成図である。
【図２３】透かしデータの埋め込みブロックの変換係数の差分処理を説明する図である。
【図２４】透かしデータが埋め込まれるサンプルのビット構成を説明する図である。
【図２５】透かしデータが埋め込まれるウェーブレット変換係数のビット構成を階層別に説明する図である。
【図２６】実施の形態５に係る符号化装置の構成図である。
【図２７】実施の形態５に係る復号装置の構成図である。
【符号の説明】
１０  符号化装置、  １２  ビット長伸長部、  １３  ダイジェスト生成部、１４  変更部、  １６  埋め込み部、  １８  埋め込みブロック選択部、  ２０  マルチプレクサ、  ２２  スクランブラ、  ２４  ＥＣＣ部、  ２６  埋め込み部、  ２８  ＳＮＲ計算部、  ２９  重みつきＳＮＲ計算部、  ３０  セレクタ、  ４０  復号装置、  ４１  埋め込みブロック選択部、  ４２  抽出部、４４  ＥＣＣ復号部、  ４６  デスクランブラ、  ４９  比較部、  ５０  符号化装置、  ５２  位置検出部、  ５４  埋め込み部、  ５６  埋め込みブロック選択部、  ６０  位置情報生成部、  ６１  埋め込みブロック選択部、  ６２整合フィルタ、  ６４  セレクタ、  ７０  復号装置。
【図１】
2004163855.tif 000005
【図２】
2004163855.tif 000006
【図３】
2004163855.tif 000007
【図４】
2004163855.tif 000008
【図５】
2004163855.tif 000009
【図６】
2004163855.tif 000010
【図７】
2004163855.tif 000011
【図８】
2004163855.tif 000012
【図９】
2004163855.tif 000013
【図１０】
2004163855.tif 000014
【図１１】
2004163855.tif 000015
【図１２】
2004163855.tif 000016
【図１３】
2004163855.tif 000017
【図１４】
2004163855.tif 000018
【図１５】
2004163855.tif 000019
【図１６】
2004163855.tif 000020
【図１７】
2004163855.tif 000021
【図１８】
2004163855.tif 000022
【図１９】
2004163855.tif 000023
【図２０】
2004163855.tif 000024
【図２１】
2004163855.tif 000025
【図２２】
2004163855.tif 000026
【図２３】
2004163855.tif 000027
【図２４】
2004163855.tif 000028
【図２５】
2004163855.tif 000029
【図２６】
2004163855.tif 000030
【図２７】
2004163855.tif 000031