(57)【特許請求の範囲】
【請求項１】
それぞれが少なくとも１つのデータ値に関連する一組のアイテムからなるコンテンツデータに、ウォータマークを付して、変更コンテンツデータを生成するウォータマーク付与方法において、
分割手段により、上記コンテンツデータを複数のサブセクションに分割するステップと、
並替え手段により、少なくとも１つの秘密鍵を用いて、複数のアイテムを、それぞれが各サブセクションのアイテムを含むグループに関連付けるステップと、
変更手段により、各グループ内の少なくとも１つのアイテムのパリティを、そのグループ内の全てのアイテムから導出される値を用いて、逆のパリティに変更して、上記変更コンテンツデータを生成するステップとを有するウォータマーク付与方法。
【請求項２】
上記全てのグループについて、上記変更されるアイテムは、同じ１つのサブセクション内にあることを特徴とする請求項１記載のウォータマーク付与方法。
【請求項３】
上記並替え手段により、
上記複数のサブセクションのうちの第１のサブセクションを除いた各サブセクションに対して、上記少なくとも１つの秘密鍵を用いて、そのサブセクションのアイテムのそれぞれが並べ替えられたシーケンスを定義し、
上記並べ替えられたシーケンスに基づいて、上記第１のサブセクションのそれぞれのアイテム及び他のサブセクションの対応するアイテムとして、各グループを定義することを特徴とする請求項１又は２記載のウォータマーク付与方法。
【請求項４】
上記変更手段により、一連のウォータマークデータの少なくとも１つの各ビットを、上記アイテムの各グループに関連するデータ値の組に埋め込むことを特徴とする請求項１乃至３いずれか１項記載のウォータマーク付与方法。
【請求項５】
上記変更手段により、
各グループの各アイテムに関連するデータ値を用いて、少なくとも１つバイナリの固有値を導出し、
上記各固有値を、上記ウォータマークデータの各ビットと比較し、
上記比較の結果に基づいて、上記グループのデータ値の少なくとも１つを変更することによって、上記固有値のパリティを変更することを特徴とする請求項４記載のウォータマーク付与方法。
【請求項６】
上記各グループは、バイナリのパリティ値である唯一の固有値を有することを特徴とする請求項５記載のウォータマーク付与方法。
【請求項７】
上記各グループは、それぞれが上記アイテムのグループの異なる各サブセットから導出された複数の固有値を有することを特徴とする請求項５記載のウォータマーク付与方法。
【請求項８】
上記変更手段により、上記コンテンツデータに冗長性を導入することを特徴とする請求項１乃至３いずれか１項記載のウォータマーク付与方法。
【請求項９】
上記変更手段により、上記グループの少なくとも１つのデータ値の少なくとも１つの最下位ビットを、該グループの少なくとも１つのデータ値の少なくとも１つの最上位ビットを用いて得られる固有値に基づいて、該固有値が隠されるように変更することを特徴とする請求項８記載のウォータマーク付与方法。
【請求項１０】
上記アイテムは、静止画像又はビデオシーケンスのフレームの画素であることを特徴とする請求項１乃至９いずれか１項記載のウォータマーク付与方法。
【請求項１１】
上記変更されたアイテムを含むサブセクションは、上記静止画像又は上記フレームの周囲のサブセクションであることを特徴とする請求項１０記載のウォータマーク付与方法。
【請求項１２】
上記データ値は、グレースケール値であることを特徴とする請求項１０又は１１記載のウォータマーク付与方法。
【請求項１３】
上記静止画像又は上記フレームは、カラー画像であり、上記データ値は、画像の輝度であることを特徴とする請求項１０又は１１記載のウォータマーク付与方法。
【請求項１４】
上記コンテンツデータは、ブロックに分割され、ブロック毎にＤＣＴ変換され、上記データ値は、ＤＣＴ変換データであることを特徴とする請求項１乃至１３いずれか１項記載のウォータマーク付与方法。
【請求項１５】
上記変更は、中間の空間周波数に対応するデータ値に対してのみ実行されることを特徴とする請求項１４記載のウォータマーク付与方法。
【請求項１６】
上記アイテムは、上記ＤＣＴ変換データのブロックであることを特徴とする請求項１４又は１５記載のウォータマーク付与方法。
【請求項１７】
上記アイテムは、上記ＤＣＴ変換データのブロック内の空間周波数振幅であり、上記各グループは、各ＤＣＴ変換データのブロック内の同じ各位置におけるアイテムからなることを特徴とする請求項１４又は１５記載のウォータマーク付与方法。
【請求項１８】
上記ＤＣＴ圧縮データを伸長して、上記コンテンツデータを導出するステップと、
上記変更コンテンツデータを再圧縮するステップとを更に有する請求項１４乃至１７いずれか１項記載のウォータマーク付与方法。
【請求項１９】
少なくとも１つの更なる秘密鍵を用いて、上記各サブセクションのアイテムを含む他のグループに複数のアイテムを関連付けるステップと、
上記他のグループ内の全てのアイテムから得られた値を用いて、該他のグループ内の少なくとも１つのアイテムを変更して、上記変更コンテンツデータを生成するステップとを更に有する請求項１乃至１８いずれか１項記載のウォータマーク付与方法。
【請求項２０】
それぞれが少なくとも１つのデータ値に関連する一組のアイテムからなる、ウォータマークが付されたコンテンツデータに加えられた変更を検出する認証方法において、
上記該ウォータマークが付されたコンテンツデータは、
（１）第１の分割手段により、上記コンテンツデータを複数のサブセクションに分割し、
（２）第１の並替え手段により、少なくとも１つの秘密鍵を用いて、複数のアイテムを、それぞれが各サブセクションのアイテムを含むグループに関連付け、
（３）第１の変更手段により、各グループ内の少なくとも１つのアイテムのパリティを、そのグループ内の全てのアイテムから導出される値を用いて、逆のパリティに変更して、変更コンテンツデータを生成することによって、生成されており、
当該認証方法は、
第２の並替え手段により、上記少なくとも１つの秘密鍵を用いて、上記アイテムのグループを入手するステップと、
比較手段により、上記アイテムのグループのデータ値を用いて、該グループのデータ値が、上記ステップ（３）によって生成された変更コンテンツデータに一致するか否かを判定し、一致しない場合、該グループのデータ値に、改竄の可能性があることを示すラベルを付すステップとを有する認証方法。
【請求項２１】
コンテンツデータから得られたウォータマークが付されたコンテンツデータを用いて、該ウォータマークが付されたコンテンツデータに隠された追加的データを検出するコンテンツデータの使用方法において、
上記ウォータマークが付されたコンテンツデータは、
（１）第１の分割手段により、上記コンテンツデータを複数のサブセクションに分割し、
（２）第１の並替え手段により、少なくとも１つの秘密鍵を用いて、複数のアイテムを、それぞれが各サブセクションのアイテムを含むグループに関連付け、
（３）第１の変更手段により、各グループ内の少なくとも１つのアイテムのパリティを、そのグループ内の全てのアイテムから導出される値を用いて、逆のパリティに変更して、一連のウォータマークデータの少なくとも１つの各ビットが埋め込まれており、
当該コンテンツデータの使用方法は、
第２の並替え手段により、上記少なくとも１つの秘密鍵を用いて、上記アイテムのグループを入手するステップと、
推定手段により、上記アイテムのグループのデータ値を用いて、上記追加的データを抽出するステップとを有するコンテンツデータの使用方法。
【請求項２２】
コンピュータシステムによって実行されて、該コンピュータシステムに請求項１乃至１９いずれか１項記載のウォータマーク付与方法の各手順を実行させるためのプログラム命令を含むコンピュータプログラム。
【請求項２３】
コンピュータシステムによって実行されて、該コンピュータシステムに請求項２０記載の認証方法の各手順を実行させるためのプログラム命令を含むコンピュータプログラム。
【請求項２４】
コンピュータシステムによって実行されて、該コンピュータシステムに請求項２１記載のコンテンツデータの使用方法の各手順を実行させるためのプログラム命令を含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータを変更する（「ウォータマーキング」する）ウォータマーク付与方法に関し、詳しくは、特に後のデータの改竄を検出できるようにデータを変更するウォータマーク付与方法に関する。更に、本発明は、改竄を検出する方法に関する。また、本発明は、デジタルデータ内で、追加的データを任意に隠し、隠されたデータを後に再生する方法に関する。また、本発明は、これらの方法を実行する装置に関する。
【背景技術】
【０００２】
デジタルウォータマーキングは、デジタルコンテンツデータ、例えばデジタルオーディオデータ、デジタル画像データ及びデジタルビデオデータに情報を挿入する技術である。ウォータマーク（watermark：ＷＭ）は、コンテンツデータに直接（添付ではなく）埋め込まれ、通常、（オーディオデータの場合）聞こえない、又は（画像データ又はビデオデータの場合）見えないデータである。ウォータマークは、コンテンツデータの通常の使用に影響を与えない。しかしながら、ウォータマークは、ウォータマークが付されたコンテンツデータから抽出することができ、又はウォータマークが付されたコンテンツデータ内で検出することができる。ウォータマークの一般的な用途としては、ウォータマークを用いて、著作権保護のためにコンテンツデータの所有権を識別することである。このようなウォータマークは、一般的な画像処理、例えば圧縮、スケーリング、回転、並びにＡ／Ｄ変換及びＤ／Ａ変換に対してさえもロバストである必要がある。
【０００３】
また、他の用途として、ウォータマークは、認証に用いることができ、コンテンツデータが改竄されたことを、例えば他の画像の一部を切り取って貼り付けることにより、画像の一部が変更されたことを検出することができる。ビデオフィルムの改竄の具体例として、例えば、映画「ミッション・インポッシブル（Mission Impossible）」及び映画「スピードＩ（Speed I）」では、何者かが、安全監視システムのビデオコンテンツを故意に変更する場面がある。このようなことは現実世界でも起こる可能性がある。現在の世界では、テロリズムが人間の生命に対して重大な脅威となり、ビデオ監視システムの活用の重要性が高まっており、ビデオフィルムが改竄されていないことを認証できる能力は重要である。
【０００４】
認証用途では、ウォータマークは、コンテンツデータに対するあらゆる改竄が検出できるように付与される。認証のために用いられるウォータマークは、ウォータマークが付されたコンテンツデータに対する僅かな変更も検出でき、すなわち、ウォータマークが埋め込まれた後に、デジタルコンテンツが変更されたことを確認できるようにするという意味において、脆弱である必要がある。
【０００５】
脆弱なウォータマークを実現する技術は、参考文献として示すように、多くの非特許文献及び特許文献において開示されている。これらの技術は、許容可能な変更をどのように定義するかによって、ハードな脆弱なウォータマーキング（Hard fragile watermarking）と、ソフトな脆弱なウォータマーキング（soft fragile watermarking）の２つのクラスに分類することができる（例えば、非特許文献１参照。）。ハードな脆弱なウォータマークは、非常に感度が高く、非常に小さい変更、例えば１つの画素に対する１ビットのみの変更を検出するこことできる。ハードな脆弱なウォータマークの幾つかの具体例は、非特許文献２〜５、特許文献１、２に開示されている。非特許文献２〜５において提案されている方法は、画像の画素領域で機能し、変更された可能性がある位置を判定することができる。非特許文献２では、ウォータマークビットマップ及びランダムルックアップテーブルに基づいて、画像のデータ値が変更される。この方法の主な短所は、ウォータマーキング方式が極めて容易に攻撃されるという点である。非特許文献３では、非特許文献２の方法を改善し、所定の画素に埋め込むウォータマークビットを、その画素に隣接する画素を用いて決定している。したがって、ウォータマーキング方式を破ることは、非常に難しい。非特許文献４には、画像のチェックサムを、ランダムに選択された幾つかの画素位置に隠す非常に簡単なウォータマーキング方式が提案されている。非特許文献５には、秘密鍵及びハッシュ関数を用いて、ウォータマーキングビットを生成するブロックベースのウォータマーキング方式が提案されている。この方式は、如何なる変更にも非常に敏感である。特許文献１及び特許文献２には、ウォータマーキングビットが、ＤＣＴ係数に埋め込まれるという点で、画像領域データを圧縮するために用いるウォータマーキング方式が開示されている。特許文献１及び特許文献２では、変更位置を検出する能力が識別が不足しているという共通の問題がある。
【０００６】
ソフトな脆弱なウォータマーキング技術は、画像コンテンツ又は品質が大幅に変更されない限り、通常の幾つかの処理、例えば画像圧縮、変換、輝度調整等を許容するという意味において、ハードな脆弱なウォータマーキングほど敏感ではない。非特許文献１及び特許文献３は、ソフトな脆弱なウォータマーキングの幾つかの具体例を開示している。
【０００７】
要約すれば、上述したハードな脆弱なウォータマーキング方式は、いずれも、以下に示す必要な性質のうちの１つ以上を欠いている：１）ウォータマーキング方式は、小さな変更をも検出できるように十分に敏感であるべきである。２）ウォータマークを埋め込む際、元のコンテンツのデータの変更は最小限に抑えるべきである。３）変更された可能性がある位置を検出できるべきである。４）ウォータマーキングアルゴリズムは、簡単に実施できるように十分に単純であるべきである。５）ウォータマーク方式は、第３者が攻撃することが困難であるべきである。
【０００８】
【非特許文献１】B B. Zhu, M. D. Swanson and A. H. Tewfik "When Seeing Isn't Believing" IEEE Signal Processing Magazine, Vol.21, No.2, 2004, pp40-49
【非特許文献２】M. M. Yeung and F. Mintzer " An Invisible Watermarking Technique for Image Verification" Proc. IEEE Int. Conf. Image Processing, 1997,pp680-683
【非特許文献３】J. Fridrich, M. Goljan and A. C. Baldoza "New Fragile Authentication Watermark for Images" Proc IEEE Int. Conf. Image Processing, 2000, pp428-437
【非特許文献４】Steve Walton "Image Authentication for a Slippery New Age" Dr. Dobb's J., Vol.20, No.4, 1995, pp18-26
【非特許文献５】P. W. Wong and N. Memon "Secret and Public Key Image Watermarking Schemes for Image Authentication and Ownership Verification" IEEE Trans. On Image Processing, Vol. 10, No. 10, 2001, pp1593-1601
【特許文献１】米国特許第６０６４７６４号明細書
【特許文献２】米国特許第６２７５５９９号明細書
【特許文献３】米国特許第６５３２５４１号明細書
【特許文献４】米国特許第６０３７９８４号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、コンテンツデータにウォータマークを付与する新規で有用な技術を提供することである。
【課題を解決するための手段】
【００１０】
包括的に言えば、本発明は、データ値を有する一組のアイテムから構成されたコンテンツデータ（例えば、コンテンツデータが画像データである場合、アイテムは、画像データの画素であってもよく、データ値は、グレースケール値又は輝度値であってもよい）をサブセクションに分割することを提案する。サブセクションのアイテムは、秘密鍵を用いて、グループに関連付けられ、各グループは、各サブセクションのアイテムを含む。各グループ内の少なくとも１つのアイテムは、そのグループ内の全てのアイテムから導出される値を用いて変更される。このようにして、ウォータマークが付されたデータが生成される。
【００１１】
認証を行うときは、秘密鍵を用いて、データ値のグループを再び抽出し、これらのデータ値が上述した変更処理に一致しているか否かを判定する。不一致が検出された場合、ウォータマークが付された後に、グループ内の少なくとも１つのデータ値が改竄された虞があるので、グループ内の全てのデータ値は、変更の疑いがあるとみなされる。
【００１２】
本発明のウォータマーキング方式の好ましい実施の形態では、上に列挙した５つの必要な性質を有する。
【００１３】
具体的には、他の脆弱なウォータマーク技術に比べて、本発明の実施の形態では、各グループ内の多くても１つのデータ値を変更すれば足りるので、元のデータに加えられる変更は最小である（後述するように、その変更は、非常に少ない）。
【００１４】
これにもかかわらず、本発明のウォータマーク付与方法の実施の形態は、僅かな改竄にも敏感である。
【００１５】
本発明の実施の形態は、ウォータマーク付与処理及び認証処理のいずれにおいても、演算を簡単にすることができる。例えば、各グループは、第１のサブセクションのそれぞれのアイテム、及び少なくとも１つの秘密鍵を用いて生成されたそれぞれの変更シーケンスに基づく、第１のサブセクションに対応する他のサブセクションのアイテムとして定義することができる。
【００１６】
したがって、本発明の実施の形態によって生成されたウォータマークが付されたデータは、ウォータマーク付与の際のシーケンスの並べ替えにより、アイテムのグループ間に、コンテンツデータとの相関性が低い相関関係が導入されるので、攻撃に対して非常に強い。
【００１７】
このウォータマーク付与方法における変更（ウォータマーキング）ステップは、様々な方法で実行することができる。第１の可能性として、例えば、鍵（ロバスト性を高めるために、秘密鍵を用いてもよい）を用いて自動的に生成された一連のウォータマークデータ（ここでは、ウォータマークビットマップと呼ぶ。）を用いてもよい。なお、埋込ウォータマークビットマップは、後に、ウォータマークが付されたコンテンツデータから抽出されるデータ（例えば、秘密のデータ）であってもよい。この場合、ウォータマークの埋込／検出の目的は、実際には、コンテンツデータの認証ではなく、ウォータマークビットマップを送信／受信ことである。
【００１８】
ウォータマークビットマップが埋め込まれる場合、この変更では、一連のウォータマークデータの少なくとも１つの各ビットを、各アイテムのグループに関連するデータ値の組に埋め込む。これは、例えば、各グループの各アイテムに関連するデータ値を用いて、少なくとも１つバイナリの固有値（例えば、パリティ値）を導出し、この固有値をウォータマークビットマップのそれぞれのビットと比較することによって実行できる。これらの値が異なる場合、グループのデータ値の少なくとも１つを変更して、ウォータマークビットに一致するように、固有値を変化させる。あるいは、データ値の各グループに複数のウォータマークビットを埋め込んでもよい（「連結ウォータマーキングの組み合わせ（concatenated watermarking）」）。
【００１９】
これに代えて、（例えば、ウォータマークデータを利用することなく）コンテンツデータに検出可能な冗長性を導入することによって、変更（ウォータマーク付与）ステップを実行してもよい。例えば、この変更において、グループの少なくとも１つのデータ値の少なくとも１つの最上位ビットを、そのグループのデータ値のより上位のビットに基づいて変更してもよい。
【００２０】
本発明のある実施の形態では、ウォータマークを付すデータは、特に画像データが適当であるが、これに代えて、コンテンツデータは、他の形式のデジタルデータ、例えばデジタルオーディオデータであってもよい。また、コンテンツデータが画像データである場合、画像データは、静止画像であっても、ビデオ画像のフレームであってもよい。画像は、白黒画像であってもよく（すなわち、データ値は、グレースケール値であってもよく）、カラー画像であってもよい。
【００２１】
更に、コンテンツデータが静止画像又はビデオ画像を表している場合、本発明に基づくウォータマーク付与方法は、画像の画素領域又は変換された領域のいずれにも適用することができる。例えば、データは、画像／ビデオファイルを圧縮する方式、例えばＪＰＥＧ、ＭＰＥＧ１、ＭＰＥＧ２、ＭＰＥＧ４及びＨ．２６４で採用された方法で変換してもよい。これらの方式では、データは、通常、ブロック毎に変換され、コンテンツデータのデータ値は、空間周波数の振幅、例えばＤＣＴデータを表している。本発明のウォータマーク付与方法では、個々のブロックをグループに関連付けられるアイテムとして扱ってもよく、又は空間周波数値をアイテムとして扱ってもよい。なお、コンテンツデータが圧縮データの形式で供給される場合、ウォータマーク付与方法は、ウォータマーク付与及び後の再圧縮の前に、この圧縮データを伸長する予備的なステップを含んでいてもよい。
【００２２】
特に、使用されるコンテンツデータの種類に基づいて、本発明に基づくウォータマーク付与方法の１つ以上の所望の特性を向上させるために、本発明の範囲内で様々な変形が可能である。
【００２３】
例えば、コンテンツデータが画像データである場合、画像の全てのサブセクションを確実に変更することが望ましい場合もあれば、静止画像又はフレームの周囲のサブセクションのみに対して変更を加える方が望ましい場合もある。更なる実施の形態として、コンテンツデータが空間周波数領域に変換されたデータである場合、ある空間周波数値、例えば中間の空間周波数のデータ値のみを変更してもよい。
【００２４】
本発明の更に可能な拡張として、グループの第２の組（すなわち、第１のサブセクションのアイテムと、それぞれの他のサブセクションの異なるそれぞれのアイテムとの間の関係）を定義する。これらの第２のグループは、第１のグループに関連して上述した方法により、ウォータマークを付与するために用いることができる。すなわち、「二重の」ウォータマークをデータに付与してもよい。所定のアイテムに対する改竄は、このアイテムに関連した２つのグループの両方で検出される。この考えは、原理的には、如何なる数のグループを含むように拡張することができる。更に、サブセクションの定義は、各ウォータマーク付与動作が元の画像を余り変化させないので、各ウォータマーク付与動作に対して同一である必要がない。
【００２５】
本発明の実施の形態は、典型的には、ハードな脆弱なウォータマーキングと呼ばれる技術分野に属する。
【００２６】
本発明の第１の側面であるウォータマーク付与方法は、それぞれが少なくとも１つのデータ値に関連する一組のアイテムから構成されたコンテンツデータにウォータマークを付与するウォータマーク付与方法において、コンテンツデータを複数のサブセクションに分割するステップと、少なくとも１つの秘密鍵を用いて、それぞれが各サブセクションのアイテムを含むグループに複数のアイテムを関連付けるステップと、グループ内の全てのアイテムから導出される値を用いて、各グループ内の少なくとも１つのアイテムを変更し、変更コンテンツデータを生成するステップとを有する。
【００２７】
本発明の第２の側面である認証方法は、それぞれが少なくとも１つのデータ値に関連する一組のアイテムから構成されたウォータマークが付されたコンテンツデータに加えられた変更を検出する認証方法であって、ウォータマークが付されたコンテンツデータは、コンテンツデータを複数のサブセクションに分割し、少なくとも１つの秘密鍵を用いて、それぞれが各サブセクションのアイテムを含むグループに複数のアイテムを関連付け、グループ内の全てのアイテムから導出される値を用いて、各グループ内の少なくとも１つのアイテムを変更し、変更コンテンツデータを生成することによって生成され、認証方法は、少なくとも１つの秘密鍵を用いて、アイテムのグループを入手し、アイテムのグループのデータ値を用いて、グループのデータ値が、ステップによって生成されたデータに一致するか否かを判定し、一致しない場合、グループのデータ値に、変更の可能性があることを示すラベルを付すステップとを有する。
【００２８】
また、本発明は、ソフトウェアによって制御されて、上述した２つの方法のいずれかを実行するプロセッサを有する装置として表現することもできる。
【００２９】
更に、本発明は、コンテンツデータにアクセスする手段を有するコンピュータ装置によって実行され、このコンピュータ装置に、上述した２つの方法のいずれかを実現させる（例えば、記録媒体に保存される）コンピュータプログラムとして表現することもできる。
【発明を実施するための最良の形態】
【００３０】
図１は、本発明の第１の実施の形態を示している。この実施の形態は、画像の画素領域において動作する（後述するように、他の実施の形態では、本発明は、この点に制限されない）。画像は、グレースケール画像であっても、カラー画像であってもよい。以下では、説明のために、画像をグレースケール画像であると仮定し、したがって、各画素は、グレースケール値であるデータ値に関連付けられている。なお、画像がカラー画像である場合、この実施の形態を、変更することなく、カラー画像の輝度成分（例えば、ＮＴＳＣのＹＩＱカラー画像表現のＹ成分）であるデータ値に適用することができる。
【００３１】
この実施の形態は、以下のステップを含んでいる。
（１）画像フィールド全体を重なり合わないｎ（≧２）個のサブセクション１１、１２、１３、１４に分割する。例えば、図１は、ｎ＝４の場合であり、各サブセクション１１、１２、１３、１４が画像の水平方向のストライプ（horizontal stripe）である単純な場合を示している。各サブセクション１１、１２、１３、１４は、同数の画素を含んでいる。
（２）サブセクション１１、１２、１３、１４のそれぞれに対して、画素のシーケンスを定義する。例えば、各シーケンスを、各サブセクションの左上コーナの画素から開始し、１番目の行の左側から右側の画素とし、以下、２番目以降の行も同様とすると定義することができる。ここでは、第１のサブセクション１１の画素シーケンスをＳ１とする。また、サブセクションｊの画素位置ｋのデータ値をｐｊ（ｋ）とする。
（３）秘密鍵を用いたランダム置換関数（permutation function）によって、他の３つのサブセクション１２、１３、１４の画素シーケンスをランダムに配列（rank）して、３つのランダムシーケンスＳ２、Ｓ３、Ｓ４を生成する。この処理を、ブロック２２、２３、２４に示す。ランダム置換関数は、例えば、ＭＡＴＬＡＢ（マットラブ）における既知の初期シードを用いたrandperm関数であってもよい。このシードは、ウォータマークを検出するときに、同じランダムシーケンスＳ２、Ｓ３、Ｓ４を再生するための秘密鍵として、後で用いることができる。また、画素シーケンスＳ１は、手動で擬似ランダム的方法で並べ替えることができ、この場合、手動で並べ替えられたシーケンス自体は、秘密鍵として保存しなければならない。
（４）ブロック３０に示すように、サブセクション１１内の各画素のデータ値は、サブセクション１２、１３、１４から並べ替えられたランダムシーケンスＳ２、Ｓ３、Ｓ４の対応する位置のデータ値に加算される。換言すれば、サブセクション１１の画素数に等しい数のグループが定義され、これらの各グループは、サブセクション１１内のそれぞれ１つの画素と、他の３つのサブセクション１２、１３、１４からのそれぞれ１つの画素とを含んでおり、グループの各画素のデータ値は、互いに加算されて、合計値Ｖ（ｉ）が求められている。ここで、インデクスｉは、グループ（又は第１のサブセクション１１の画素）のラベルである。例えば、４つのシーケンスが、Ｓ１＝（１，２，３，・・・）、Ｓ２＝（３７８，１０５２，７６５，・・・）、Ｓ３＝（１３４９，１２５，５３４，・・・）、Ｓ４＝（４７６，２８９，１１７９，・・・）である場合は、合計値Ｖ（ｉ）は以下のようになる。
Ｖ（１）＝ｐ１（１）＋ｐ２（３７８）＋ｐ３（１３４９）＋ｐ４（４７６）    （１）
Ｖ（２）＝ｐ１（２）＋ｐ２（１０５２）＋ｐ３（１２５）＋ｐ４（２８９）    （２）
Ｖ（３）＝ｐ１（３）＋ｐ２（７６５）＋ｐ３（５３４）＋ｐ４（１１７９）    （３）
・・・
そして、各グループについて、値が１の合計値（バイナリ表現）Ｖ（ｉ）の数をカウントする。そして、値が１の合計値Ｖ（ｉ）のこの数のパリティ値（奇数／偶数）を判定する。したがって、画素のそれぞれのグループに対してパリティ値が存在する。
（５）パリティ値が奇数である場合、合計値Ｖ（ｉ）を表すためにパリティビットを１にする。パリティ値が偶数の場合、パリティビットを０にする。そして、ブロック３１に示すように、各グループのパリティビットを、ウォータマークビットマップ（すなわち、各要素が０又は１であるストリング）のそれぞれのビットと比較する。ブロック３２によって示すウォータマークビットマップは、既知のビットマップ画像、例えば企業ロゴ又は擬似ランダムシーケンスとすることができる。データを隠す場合は、ビットマップは、画像に隠すデータ／情報である。ウォータマークビットマップのビット数は、画像のサブセクション１１の画素数と同じである。パリティビットがウォータマークビットマップのそれぞれのビットと同じである場合、変更は必要ない。パリティビットがウォータマークビットマップのそれぞれのビットと異なる場合、第１のサブセクション１１の対応する画素を変更する（本発明の他の実施の形態では、この変更は、サブセクション１１、１２、１３、１４のいずれか１つの対応するビットを変更することによって、一般化することができ、あるいは、変更する画素を、グループのデータ値に適用される幾つかの検査に基づいて、異なるグループ毎に選択的に変えてもよい）。
【００３２】
この変更は、ブロック３３として示すステップにおいて実行される。変更処理は、以下の通りである。
【００３３】
合計値Ｖ（ｉ）が奇数である場合、サブセクション１１のデータ値をｐ１（ｉ）＝ｐ１（ｉ）−１に変更する。
【００３４】
合計値Ｖ（ｉ）が偶数である場合、サブセクション１１（ａとして示す）のデータ値をｐ１（ｉ）＝ｐ１（ｉ）＋１に変更する。
【００３５】
このように、この単純な操作によって、値が１の合計値のパリティは、変更され、すなわちそれぞれのウォータマークビットマップ値と同じになるように変更される。このようにして、ウォータマークビットマップが元の画像に埋め込まれ、ウォータマークが付された画像が生成される。
【００３６】
なお、ステップ２２、２３、２４は、平行して実行することができ、例えば、同じグループ内の３つの画素に対して同時に実行することができる。これらのステップ２２、２３、２４及びステップ６０、６１、６２（図４）のそれぞれは、各グループに対して実行される。実際の実施の形態では、ステップ６０、６１、６２のいずれも第１の所定のグループに対して、ステップ２２、２３、２４がそれとは異なる１つのグループに対して実行されているときに、同時に実行することができる。
【００３７】
図１ｂは、ウォータマークが付されたデータを用いたウォータマークの検出を示している。ここでも、画像は、画素領域においてサブセクション１１、１２、１３、１４（図１ａに示すサブセクションと同じ）に分割されている。そして、ステップ４２、４３、４４において、上述したステップ２２、２３、２４と同じ方法で、同じ秘密鍵を用いて、これらのサブセクション１２、１３、１４の画素を並べ替えて、画素の同じグループを生成する。各グループのデータ値を加算し（ステップ５１）、ステップ５２において、値が１の合計値のパリティを表すパリティビットを、図１ａで用いたものと同じウォータマークビットマップのそれぞれのビットと比較する。ウォータマークビットマップは、既知のものであってもよく、ステップ５３で再生したものであってもよい。ステップ５４において、パリティビットとウォータマークビットマップの対応するビット間の全ての相異を用いて、グループ内の４つの画素のうちの少なくとも１つに対して何らかの改竄があったことを推定する。すなわち、４つの画素の全ては疑わしいと推定する。
【００３８】
なお、ここでは、画像内の対応する４つの（各サブセクションの１つずつ含まれる）画素位置のうちの１つ（又は１つ以上）が変更された可能性があるが、これだけでは、これらの４つの画素位置のうちのどれが変更されたを判定することはできない。しかしながら、殆どの全ての意味がある改竄は、多くの画素を含む連続した領域に対して行われているので（独立した１つの画素の値を変更しても、通常、画像の内容は変化しないので）、疑わしい画素は、実際に改竄された領域では集中（clustering）し、他の領域では分散（scattering）する。したがって、真の改竄位置は、疑わしい画素の相対的な集中に基づいて判定することができる。
【００３９】
このような具体例を図２に示す。図２（ａ）は、元の画像である。図２（ｂ）は、図２（ａ）の画像を変更することによって得られた画像であり、詳しくは、（１）図１ａで説明した方法を適用し、（２）小さい矩形領域内の各画素に１を加えることによって、ウォータマークが付された画像を変更し、（３）図１ｂで説明した方法を適用し、（４）疑わしい画素をそれぞれ黒い点でマークすることによって、得られた画像である。画像の左上の部分に黒い点が集中していることから、この領域が、ステップ（２）においてウォータマークが付されたデータに変更が加えられた領域が、「改竄された領域」としてマークさた１つであることを容易に判断することができる。このようにして、真の改竄位置は、集中に基づいて推定することができる。
【００４０】
なお、ステップ（２）で加えられた変更は、非常に小さいものである。これらの変更された画素の殆どが検出されたという事実は、ここに提案するウォータマーキング方式が非常に敏感であることを示している。
【００４１】
以下、本発明の範囲内で第１の実施の形態に加えることができる様々な変更について説明する。
【００４２】
まず、サブセクションの数は、サブセクションを定義する方法が変更できるのと同様に、変更することができる。第１の実施の形態では、ウォータマークビットマップは、サブセクション１１内のデータ値を変更することによって埋め込まれるので、サブセクション１１は、視覚的に重要ではない領域、例えば画像の端の領域を占めるように選択することができる。なお、画像をサブセクションに分割する際に求められる唯一の条件は、各サブセクション内の画素数を略同じにすることである。
【００４３】
幾つかの具体例を図３（ａ）及び図３（ｂ）に示す。図３（ａ）では、３つのサブセクションのみが定義され、（図１ａのサブセクション１１に対応する）第１のサブセクションは、画像の４つのコーナ領域から構成された不連続な領域である。図３（ｂ）では、（図１ａのサブセクション１１に対応する）第１のサブセクションは、画像の端の領域である。図１ａに示すサブセクション１１の定義に比べて、図３（ａ）及び図３（ｂ）に示す定義では、変更される領域が画像の端に存在するので、ウォータマーキング処理によって生じる画像の視覚的変化が目立たないようにされている。
【００４４】
本発明の第２の実施の形態を図４を用いて説明する。第１の実施の形態に対するこの変形例では、データの変更を検出する能力が更に強化されている。ここでは、ウォータマークビットマップを用いない。具体的には、第２の実施の形態では、ウォータマークビットマップを、それぞれのグループの４つの画素のデータ値の合計のパリティに基づいて埋め込むことに代えて、グループの４つの画素の第７ビットの最上位ビット（most significant bit：ＭＳＢ）の合計を算出し、この合計における１の数（１のパリティではない）を４つの画素のそれぞれの最下位ビット（lowest significant bit：ＬＳＢ）に隠す（ここでは、画像データ値を８ビット値であると仮定している）。８ビットのデータ値を有する画像の４つの画素の第７ビットのＭＳＢの合計（バイナリで表現される）は、９ビットを超えることはなく、したがって、１の数は最大でも９個である。範囲０〜９の値は、４ビットでコード化することができる。したがって、１の数を隠すには、４つの画素のＬＳＢ位置を用いれば十分である。
【００４５】
この方法の手順を図４に示す。図１ａの方法と同様に、４つのサブセクション１１、１２、１３、１４を定義し（上述した如何なる方法を用いてもよい）、並べ替えられたランダムシーケンスＳ２、Ｓ３、Ｓ４を生成する。この処理は、図１ａを用いて説明した方法と同じであり、したがって、これらのステップには、同じ指示符号２２、２３、２４を付している。ステップ６０において、各グループについて、各画素の第７ビットのＭＳＢの合計を算出する。ステップ６１において、各グループについて、この合計における１の数を算出する。ステップ６２において、この値をバイナリに変換し、グループの画素のそれぞれのＬＳＢに隠す。
【００４６】
この第２の実施の形態では、第１の実施の形態に比べて、より多くの画像データ値を変更しなくてはならない。したがって、ウォータマークが付された画質は、第１の実施の形態を用いた場合に比べて、若干劣る。
【００４７】
本発明の第３の実施の形態を図５に示す。この実施の形態は、連結された脆弱なウォータマーク方式（concatenated fragile WM scheme）であり、この方式では、ウォータマークパターンの３つのビットを画素の各グループに埋め込む（オプションとして、ステップ７９において生成される）。第３の実施の形態の第１のステップは、第１及び第２の実施の形態と同じであり、すなわち、秘密鍵を用いてランダムシーケンスＳ２、Ｓ３、Ｓ４を生成し（ステップ２２、２３、２４）、それぞれサブセクションにおいて、４つの画素のグループを得る。ステップ７０において、４つの全てのサブセクションからの４つのデータ値を直接加算するのではなく、まず、サブセクション１及びサブセクション２の対応するデータ値を加算する。そして、ステップ７１において、この結果における１の数のパリティを、ウォータマークビットマップの第１のビットとチェックする。このパリティチェックの結果が一致しなかった場合、ステップ７２において、（例えば）サブセクション２のデータ値を変更することによって、第１のウォータマークビットを埋め込む。
【００４８】
そして、ステップ７３において、サブセクション２の画素の変更されたデータ値を、サブセクション３内のグループの画素の対応するデータ値に加算する。そして、ステップ７４及びステップ７５において、サブセクション３のデータ値を変更することによって、ウォータマークビットマップの第２のウォータマークビットをこの新たな合計に埋め込む。
【００４９】
ステップ７６において、サブセクション３の画素の変更されたデータ値を、サブセクション４内のグループの画素の対応するデータ値に加算する。そして、ステップ７７及びステップ７８において、ウォータマークビットマップの第３のウォータマークビットをサブセクション４内のグループの画素のデータ値に埋め込む。
【００５０】
本発明のこの第３の実施の形態によって、ウォータマークの変更に対する感度を改善することができる。例えば、サブセクション２内の画素が改竄によって変更された場合、この変更は、（サブセクション１及びサブセクション２に埋め込まれている）第１のウォータマークビットからも、（サブセクション２及びサブセクション３に埋め込まれている）第２のウォータマークビットからも、又はこれらの両方からも検出することができる。このように、サブセクション２は、二重のウォータマークによって保護されているとみなすことができ、したがって、変更に対してより敏感である。更に、変更された位置を判定する能力も高められる。例えば、ウォータマークビットマップの変更が第１のウォータマークビットで検出され、第２及び第３のウォータマークビットで検出されない場合、改竄によって変更された画素は、サブセクション１の画素であると判定することができる。この連結された脆弱なウォータマーク方式の短所は、より多くのウォータマークビットを埋め込むために、より多くの画素の変更が必要であるという点である。
【００５１】
また、本発明は、例えばＪＰＥＧ、ＭＰＥＧ２、ＭＰＥＧ４等の圧縮画像領域及び／又は圧縮ビデオ領域に適用することができる。ここでは、本発明をＪＰＥＧに適用した具体例を説明する。ＪＰＥＧ圧縮方式では、画像は、まず、多くのブロックに分割される。各ブロックは、通常、８×８個の画素から構成される。そして、各ブロック内で二次元離散コサイン変換（ＤＣＴ）を行った後、ＤＣＴ係数を量子化する。そして、量子化ＤＣＴ係数を、所謂ジグザグ走査によって１次元ベクトルにした後、ランレングス符号化及びエントロピ符号化（ハフマン符号化）を行う。
【００５２】
ＪＰＥＧ圧縮方式と組み合わせるのに適した本発明の第４の実施の形態を図６に示す。ここでは、脆弱なウォータマークをＪＰＥＧ画像に埋め込むために、先の３つの実施の形態における画素に代えて、基本的な処理要素（「アイテム」）として、ブロックを用いる。図６に示す実施の形態において用いられているデータ値は、８×８のブロックに配列された画像の量子化ＤＣＴ係数である（したがって、１アイテム当たり６４個のデータ値がある）。画像は、この圧縮画像領域においてサブセクションに分割される。これらのサブセクションは、先の３つの実施の形態と同じであってもよいが、これらの各サブセクション８１、８２、８３、８４には、ＤＣＴデータがある。画素の並替えに代えて、第４の実施の形態では、サブセクション２、３、４内のブロックシーケンスをランダムに並べ替える（ステップ９２、９３、９４）。そして、４つのサブセクション内の対応するブロックの量子化ＤＣＴ係数を選択する。そして、各グループついて、グループの異なるブロック内の同じ位置を占める複数のＤＣＴ係数を、以下のように加算する（ステップ９５）。
ｖ（ｉ，ｊ）＝ｄ１，ｌ（ｉ，ｊ）＋ｄ２，ｋ（ｉ，ｊ）＋ｄ３，ｍ（ｉ，ｊ）＋ｄ４，ｎ（ｉ，ｊ）      （４）
ここで、Ｖ（ｉ，ｊ）は、ブロック内のｉ番目の行及びｊ番目の列におけるＤＣＴ係数の合計値であり、ｄ１，ｌ（ｉ，ｊ）は、サブセクション１内のｌ番目のブロックの量子化ＤＣＴ係数である。また、ｋ、ｌ及びｎは、サブセクション２、３及び４における対応するブロックである。ステップ９６において、Ｖ（ｉ，ｊ）における１の数のパリティを、ウォータマークビットマップ９７のそれぞれのビットと比較する。これらが一致しない場合、これらのＤＣＴ係数の１つに対して、上述した＋１又は−１による変更処理を行う。
【００５３】
なお、この実施の形態は、必ずしもサブセクション１を変更しなくてもよく、これに代えて、変更する４つの係数のうち、最も大きい係数の１つ（例えば、最も大きい係数自体）を選択してもよい。このような処理を行う理由は、最も大きい係数を選択することによって、変更の影響を最小限にできるからである。これにより、画質が良好に維持され、また、圧縮画像のサイズは、それほど影響を受けない。例えば、１つ以上のブロックが画像の変化がない領域（flat area）にある場合、その（それらの）ＤＣＴ係数の殆どは、量子化の後にゼロになる。これらの係数に＋１又は−１を加算した場合、伸長された画像における変化が比較的大きくなり、また、ハフマン符号が大幅に変更されるので、ＪＰＥＧ画像のサイズも増加する。４つのサブセクションは、互いに離間しているので、１つ以上のブロック（例えば、式（４）におけるｄ１，ｌ（ｉ，ｊ）及びｄ３，ｍ（ｉ，ｊ））が画像の変化がない領域にある場合、他のブロック（例えば、式（４）におけるｄ２，ｋ（ｉ，ｊ）及びｄ４，ｎ（ｉ，ｊ））は、画素の変化が大きい領域にあり、そのため、大きなＤＣＴ係数を有する可能性が非常に高い。これらの大きなＤＣＴ係数に対しては、＋１又は−１による変更は、比較的影響が小さく、したがって、ウォータマークの可視性は下がり、まあ、符号化ファイル長の変化も小さい。
【００５４】
なお、ウォータマークビットマップは、４つの対応するＤＣＴ係数の全てのグループに埋め込まなくてもよい。圧縮比が高い画像の高周波係数の多くは、量子化によってゼロになり、したがって、ウォータマークビットを埋め込むには適していない。本願の発明者は、元のＤＣＴ係数が大きいことと、量子化ステップが小さいことの両方の理由から、低周波数成分又は中周波数成分にウォータマークビットを埋め込む方がよいことを見出した。好ましくは、ＤＣ（すなわち、ゼロ空間周波数）係数にウォータマークビットを埋め込むと、ブロックの局所的な明るさが変わり、視覚的な違和感が生じることが多いので、ＤＣ係数には、如何なるウォータマークビットも埋め込んでならない。
【００５５】
１つのブロック内の複数のＤＣＴ係数にウォータマークビットを埋め込むので、ブロック内のＤＣＴ係数の如何なる不一致もそのブロックに対する変更であるとみなすことができる。もちろん、この具体例では、最小の変更位置は、画素ではなく、ブロックとして識別することができるだけである。
【００５６】
上述したように、図６は、量子化ＤＣＴ係数が利用可能であることを前提としている。図７は、更なる変形例として、量子化ＤＣＴ係数の代わりに、圧縮ＪＰＥＧ画像ファイルが利用可能である場合の手順を示している。この実施の形態では、ＪＰＥＧファイルを部分的に復号して、量子化ＤＣＴ係数を得て（ステップ１０１）、そして、（図７に示す複数のステップ１０２において）図６と同様の方法でウォータマークを埋め込む。脆弱なウォータマークを埋め込んだ後、変更されたＤＣＴ係数をホフマン符号化し（ステップ１０３）、ウォータマークが付された圧縮画像ファイルを生成する。この場合も、上述した方法と同様に、ウォータマークが付されたＪＰＥＧファイルの画像サイズの変化を、非常に小さく維持することができる。これには、以下のような主に２つの理由がある。（１）４つのサブセクション内で最も大きいＤＣＴ係数を選択して、ＷＭビットを埋め込む。（２）殆どのＤＣＴ係数は、変更されない（４つのサブセクションを用いた場合、平均的に８７．５％のＤＣＴ係数が変更されない。更に、各ブロック内において、ＤＣＴ係数の一部サブセットのみにウォータマークビットを埋め込めば、変更されないＤＣＴ係数は、更に多くなる）。
【００５７】
上述のように、ブロックベースのウォータマーク方式においては、最小検出範囲は、ブロックの大きさである。したがって、第１の実施の形態の画素領域から類推されるように、ウォータマークビットマップに１つの誤りが検出された場合、誤り位置に関連する４つのブロックのいずれもが、誤りの原因である可能性がある。二重のウォータマーク方式を採用することによって、誤り検出能力を高めた本発明の更なる実施の形態を図８に示す。各ブロックは、２つのそれぞれのＷＭ方式に関連している。なお、２つの方式は、ブロックを配列するために、異なるランダムシーケンスを有する。例えば、第１のウォータマーク方式において、サブセクション１のブロック１に関連するブロックは、それぞれサブセクション２、３、４のブロック１３８、４３９、７６であってもよく、すなわち（１，１３８，４３９，７６）としてグループ化される。第２のウォータマーク方式では、第１のサブセクションのブロック１を含むグループは、グループ（１，２７５，９３，３４７）である。第１のグループは、例えばＤＣＴ係数ｄ（３，４）、ｄ（３，５）を変更することによって、ブロックの第１のグループのＤＣＴ係数に第１のＷＭビットマップを埋め込むために用いられる。同様に、ＤＣＴ係数ｄ（３，８）、ｄ（４，８）は、第２のビットマップを埋め込むために、変更することができる。したがって、第１及び第２のグループの両方が、誤り含むと検出された場合、真の改竄位置は、これらの２つのグループに共通の要素であるサブセクション１のブロック１内にあると判定することができる。
【００５８】
本発明の幾つかの実施の形態のみを詳細に説明したが、本発明の範囲内でこれらの実施の形態を様々に変形できることは、当業者にとって明らかである。例えば、上述した様々な実施の形態の個々の特徴を組み合わせてもよい。
【００５９】
更に、上述した圧縮領域ウォータマーキング処理は、ビデオ領域、例えばＭＰＥＧ２、ＭＰＥＧ４、Ｈ．２６４等において用いられるに拡張してもよい。一具体例として、映像圧縮のイントラフレームに、上述と同様の処理を用いることができる。埋め込むウォータマークビットマップは、ソースの名称、フレームの日時等の情報とすることができる。一方、インタフレームについては、動き予測誤差にウォータマークを埋め込むことができる。この場合、通常、１つのインタフレームに埋め込むことができるウォータマークビットは少ない。したがって、ウォータマークビットマップは、単に、フレーム番号等とする。このように、あらゆるデータ変更、及びビデオシーケンスのフレームの挿入又は欠落をチェックすることができる。
【００６０】
更に、請求の範囲に定義されている本発明の基本構造を本質的に変更することなく、ウォータマーク埋込及び検出処理を他のフォーマットに変更することもできる。
【００６１】
更に、上述の実施の形態では、コンテンツデータの全てのアイテムにウォータマークを付与しているが、これは本発明の必要条件ではない。これに代えて、例えば、コンテンツデータが画像データである場合、所定の割合（例えば、半分）の画素のみをグループに関連付け、これにウォータマークを付与してもよい。
【００６２】
更に、ウォータマークビットマップをデータに埋め込む上述した実施の形態の全ては、データを隠すために用いてもよい。この場合、ウォータマークビットマップは、画像に隠される追加的なデータ／情報である。検出処理では、ウォータマークが付された画像から再生されるビットマップは、目的の情報である。この場合、例えば、図１ｂのステップ５２及びステップ５３は、実行されない。ステップ５２において、パリティチェックを実行し、パリティ結果を出力するのみである。
【図面の簡単な説明】
【００６３】
【図１ａ】脆弱なウォータマークを画像データの画素領域に埋め込む本発明の第１の実施の形態であるウォータマーキング処理の手順を示すフローチャートである。
【図１ｂ】図１ａのウォータマーキング処理を用いて生成されたウォータマークが付されたデータに対する認証処理の手順を示すフローチャートである。
【図２】図２（ａ）は、元の画像であり、図２（ｂ）は、図１ａに示す実施の形態に基づいて図２（ａ）の画像にウォータマークを付与し、画像を改竄し、図１ｂに示す方法で改竄の可能性を検出し、検出された位置を黒い点でマークした結果を示している。
【図３】図１ａの実施の形態における画像の分割方法の他の変形例を示す図である。
【図４】本発明の第２の実施の形態のフローチャートである。
【図５】本発明の第３の実施の形態のフローチャートである。
【図６】本発明の第４の実施の形態のフローチャートである。
【図７】ウォータマークを圧縮画像ファイルに埋め込む更なる実施の形態のフローチャートである。
【図８】圧縮画像のブロック化されたＤＣＴ係数に二重のウォータマークを埋め込む更なる実施の形態を図式的に示す図である。
【図１ａ】
0004696777.tif 000002
【図１ｂ】
0004696777.tif 000003
【図２】
0004696777.tif 000004
【図３】
0004696777.tif 000005
【図４】
0004696777.tif 000006
【図５】
0004696777.tif 000007
【図６】
0004696777.tif 000008
【図７】
0004696777.tif 000009
【図８】
0004696777.tif 000010