(57)【要約】【課題】画像、音声、映像およびマルチメディアデータに応用できるデータのデジタル電子透かし入れ手順を得る。【解決手段】電子透かし入れされるデータを、ＭＰＥＧの８×８画素ブロック等の、１連のｎ×ｎブロックへ分割し、これらのブロックを合計して電子透かしを挿入する１つの合計ブロックを形成する。同じ電子透かし信号をさまざまな方法で一連のブロック全体に配分でき、復号器に影響を及ぼすことなく挿入アルゴリズムを変えられる。復号では、最初に各８×８ブロックのＤＣＴ係数を合計し、次に合計したブロックから電子透かしを抽出する。ＤＣＴブロックの合計は画素値ブロックの合計のＤＣＴに等しいため、空間および周波数ドメインの両方で効率的な復号が行われる。復号過程の対称性により、幾何学的歪みを空間ドメインで処理し、他の信号歪みを周波数ドメイン領域で処理することができる。【選択図】図１
2010136456.tif 000002
【特許請求の範囲】
【請求項１】
２次元のマルチメディアデータをブロック分割して得られる各ブロックにＤＣＴ変換を行って電子透かしを挿入する電子透かし挿入方法であって、
前記ブロックのデータを全て加算した際に透かし同期用のレジストレーションパターンが現れるように、前記ブロックの各データの値を変更することを特徴とする、電子透かし挿入方法。
【請求項２】
前記レジストレーションパターンをＤＣＴ変換して、レジストレーションパターンの変換係数を取得し、
さらに、同じ変換係数インデックスを有する変換係数間で、前記各ブロックの変換係数を全て加算した際に得られる値が、前記レジストレーションパターンの変換係数と強い相関を有するように、前記ブロックの変換係数の各値を変更することを特徴とする、請求項１に記載の電子透かし挿入方法。
【請求項３】
電子透かし挿入画像が予め規定された歪みを受けた後であっても電子透かし信号が抽出できるように、抽出可能な電子透かし信号を画像に挿入する電子透かし挿入方法であって、
電子透かし挿入対象画像をコピーするステップと、
前記電子透かし挿入対象画像のコピーに、予め規定された歪みを加え、歪み画像を生成するステップと、
前記歪み画像内に電子透かし信号を挿入して、第１の電子透かし挿入画像を生成するステップと、
前記第１の電子透かし挿入画像から、前記歪み画像を差し引いて、第１の電子透かしパターンを生成するステップと、
前記第１の電子透かしパターンに対して、前記予め規定された歪みを戻す操作を施し、第２の電子透かしパターンを生成するステップと、
前記電子透かし挿入対象画像と前記第２の前記電子透かしパターンとを結合して、第２の電子透かし挿入画像を得るステップと、
を含む、電子透かし挿入方法。
【請求項４】
前記予め規定された歪みがパンスキャンモード画像への変換である請求項３に記載の電子透かし挿入方法。
【請求項５】
前記予め規定された歪みがレターボックスモード画像への変換である請求項３に記載の電子透かし挿入方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像、映像およびマルチメディアデータを含むデータのデジタル電子透かし入れ（デジタル・ウォーターマーキング；digital watermarking）に関する。特に本発明は、電子透かし入れの目的で埋め込まれた信号の挿入と、検出または抽出とに関する。その挿入、検出手順は、データの小領域（サブリージョン; subregion）の合計に対して適用される。本発明では、これらの小領域がＭＰＥＧ(moving picture experts group)やＪＰＥＧ(joint photograph coding experts group)による圧縮および伸長に使用される８×８ピクセル（画素）のブロックに対応する場合には、電子透かし入れ手順をこれらの圧縮アルゴリズムと密接に結合して計算量の著しい節減を達成することができる。本発明はさらに、電子透かし入れされたデータが、電子透かしの挿入の時点と検出の時点との間で歪みを受けることがあるかもしれないような場合における、電子透かし入れのための信号の挿入と、挿入された信号の検出とに関する。
【背景技術】
【０００２】
画像（イメージ）、映像（ビデオ）およびマルチメディア等のデジタル化されたメディアの普及により、その物の源泉の識別を容易にするセキュティシステムに対するニーズが生じている。
【０００３】
コンテンツプロバイダ、すなわちデジタルデータ形式の作品の所有者には、著作権所有の認証、コピーコントロールおよび管理のために、ソフトウエアおよび／またはハードウエア装置により後にでも検出できるような信号を、映像／画像／マルチメディアデータに埋め込みたいというニーズがある。
【０００４】
例えば、データを複製してはならないことを示すために、符号化された信号をデータへ挿入することができる。埋め込まれる信号は、画像の忠実性（画質）を保存し、通常の信号変換に対してロバスト（頑強）でありかつタンパリング（改ざん；tampering）に耐える性質を有していなければならない。さらに、現在の要求ではフレーム当たり数ビットと比較的低いものであるが、システムが提供できるデータレートも考慮しなければならない。
【０００５】
１９９５年９月２８日に出願された米国特許出願第08/534,894号（対応日本出願：特開平9-191394号公報参照）“安全なマルチメディアデータ用スペクトラム拡散電子透かし入れ(Secure Spread Spectrum Watermarking for Multimedia Data)”には、コンテンツの所有者を識別するために、画像の知覚的な意味のある領域に電子透かし信号を埋め込むスペクトラム拡散電子透かし入れ方法が提示されている。この方法の長所は、電子透かしを除去するのが非常に困難なことである。事実、この方法では、比較のための原画像または原データが入手可能な場合にしか、電子透かしを読み出すことができない。これは、電子透かしの原スペクトラムが非線形乗法手順により画像のスペクトラムに整形（シェーピング）されており、このようなスペクトルシェーピングは、マッチドフィルタによる検出の前に除去されなければならないからである。これに加え、最大の方からＮ個のスペクトル係数に電子透かしが挿入されるが、その係数の大きさの順序は、電子透かし挿入後は挿入前とは変わってしまい、挿入された係数を特定できなくなるからである。したがって、この方法によって埋め込まれた電子透かしは、いかなるソフトウエアおよびハードウエア装置をもってしても、電子透かし入れされていないオリジナル（原画）にアクセスすることなしに、直接読み出すことはできない。
【０００６】
インターネット上のＷＷＷ(World Wide Web)サイトhttp://www.neci.nj.nec.com/tr/index.html（Technical Report No. 95-10）から入手できるコックス等（Cox et al.）の文献“安全なマルチメディア用スペクトラム電子透かし入れ(Secured Spectrum Watermarking for Multimedia)”では、電子透かし入れの目的でデジタルデータに擬似乱数ノイズ列を埋め込むスペクトラム拡散電子透かし入れが記載されている。
【０００７】
上述した従来技術の電子透かしを抽出する方法では、原画像スペクトラムを電子透かし画像スペクトラムから減じる必要がある。そのため、復号器が原画像もしくは原画像スペクトラムを利用できない場合には、この方法の使用は制約される。応用によっては、このことは大きな困難を伴う。例えば、ある種の操作（例えばコンテンツのコピー）を行ったり、もしくはその操作を拒否したりするための情報を電子透かしとして埋め込んで、サードパーティから提供される装置でこの情報を読み出して制御を行う場合、前述の原画を必要とする方法を用いることはほとんど不可能である。
【０００８】
アール．ディー．プリュース等(R. D. Preuss et al.)の米国特許第5,319,735号“埋め込みシグナリング(Embedded Signaling)”では、デジタル情報が符号化されてコードシンボル系列が作り出される。コードシンボル系列は、そのコードシンボル系列を表す対応するスペクトラム拡散コード信号系列を発生することにより、オーディオ信号へ埋め込まれる。コード信号の周波数成分は、オーディオ信号の帯域幅内の予め選定されたシグナリング帯域内に本質的に閉じ込められ、コード信号の連続するセグメントは系列内の連続するコードシンボルに対応する。オーディオ信号は、シグナリング帯域を包含する周波数帯域にわたって連続的に周波数解析され、コード信号は、その解析結果の関数としてダイナミックにフィルタ処理される。これにより、コード信号から、各瞬時において対応する周波数範囲内のオーディオ信号周波数成分のレベルの予め選定された部分であるような周波数成分レベルを本質的に有する、修正されたコード信号が得られる。修正されたコード信号およびオーディオ信号を結合して、デジタル情報が埋め込まれた合成オーディオ信号が得られる。次に、この合成オーディオ信号は、記録媒体上に記録されるか、あるいは送信チャネルへ送られる。この過程での２つのキーとなる要素は、それぞれ、挿入段階および抽出段階で生じるスペクトル整形（シェーピング）およびスペクトル等化であり、これにより、埋め込まれた信号は、電子透かし入れがなされていない原データへアクセスすることなく、抽出することができる。
【０００９】
コックス(Cox)の米国特許第5,848,155号“埋め込みシグナリング用スペクトラム拡散電子透かし(A Spread Spectrum Watermark for Embedded Signaling)”には、原データあるいは電子透かし入れされていないデータを使用せずに、電子透かし入れされた画像や映像から、埋め込まれたデータ中の電子透かしを抽出する方法が記載されている。
【００１０】
シグナリングを埋め込む目的で画像や画像データに電子透かしを挿入するこの方法では、画像全体のＤＣＴ（離散コサイン変換；Discrete Cosine Transform）およびその逆変換（ＩＤＣＴ）が計算される必要がある。Ｎを画像内の画素数として、ＤＣＴを（Ｎ ｌｏｇ Ｎ）のオーダの計算量で計算する高速アルゴリズム、すなわち、画素数Ｎの増加に対して計算量がたかだか（Ｎ ｌｏｇ Ｎ）に比例して長くなるような高速アルゴリズムがある。しかしながら、Ｎ＝５１２×５１２（横５１２画素、縦５１２画素）であるような画像に対しては、要求される計算量は依然として大きい。符号化および抽出処理が、映像レート、すなわち毎秒３０フレームの速度で行われなければならない場合は、特にそうである。この方法は、ＭＰＥＧ−２伸長に必要な計算量に比べておよそ３０倍の計算量を必要とする。
【００１１】
リアルタイムで映像電子透かし入れを達成する１つの方法は、Ｎ番目ごとのフレームにしか電子透かし入れをしないことである。しかしながら、コンテンツのオーナは、全ての映像フレームを保護したいと望む。さらに、どのフレームに埋め込まれた信号が含まれるかが分かってしまえば、映像信号を著しく劣化させることなくそれらのフレームを除去することは簡単である。したがって、この方法を用いるのは好ましくない。
【００１２】
別のオプションは、ｎ≪Ｎとして、画像（小画像）中のｎ×ｎ画素からなるブロックに電子透かしを挿入することである。ブロックサイズを８×８、すなわち、ＭＰＥＧ画像圧縮に使用するのと同サイズ、に選定すると、電子透かし挿入および抽出手順をＭＰＥＧの圧縮および伸長アルゴリズムと密接に結合することができる。電子透かしの挿入や抽出において最もコストがかかる計算は、ＤＣＴおよびその逆変換の計算に関連しており、これらのステップは圧縮および伸長アルゴリズムの一部として既に計算されているため、相当な計算の節減を達成することができる。したがって、電子透かし入れを行うことに伴うコスト増分は非常にわずかなものとなり、典型的にはＭＰＥＧに伴う計算要求量の５％よりも少ない。
【００１３】
１９９６年９月１９日に出願された米国特許出願第08/715,953号（対応日本出願：特開平10-308867号公報参照）“ＭＰＥＧ／ＪＰＥＧ係数を使用する画像データの電子透かし入れ(Watermarking of Image Data Using MPEG/JPEG Coefficients)”では、ＭＰＥＧ／ＪＰＥＧ係数を使用して画像データを符号化することにより、この作業を進展させている。
【００１４】
１９９６年１１月５日に出願された米国特許出願第08/746,022号（対応日本出願：特開平10-145757号公報参照）“デジタル電子透かし入れ(Digital Watermarking)”には、電子透かし情報を小画像（サブイメージ）内に格納し、小画像から電子透かし情報を抽出することが記載されている。
【００１５】
１９９７年２月９〜１４日、Proc. of EI '97, vol. 30-16のコックス(Cox et al.)等の文献"A review of watermarking and the improvement of perceptual modeling"は、電子透かし入れについての最近の動向をまとめた総説である。
【００１６】
ＭＰＥＧ映像やＪＰＥＧ静止画像に電子透かし入れを行うためのいくつかの提案がなされている。いずれの場合も、各８×８ＤＣＴブロック（８画素×８画素のサイズのブロックに、ＤＣＴを行って得られる８×８のブロック）は、電子透かしやその一部を含むように修正される。したがって、電子透かしを復号するには、各８×８ブロックを個別に解析してその中に含まれる電子透かし信号を抽出する必要がある。次に、個別に抽出された信号を結合して合成電子透かしを形成し、既知の電子透かしと比較する。各ブロックを個別に解析しなければならないため、非圧縮画像をブロックベースでのＤＣＴ表現へ変換し戻さなければならず、それはコストのかかる計算である。したがって、復号器は、ＤＣＴドメイン（領域）データでは計算の観点からは効率的ではあるが、空間ドメインデータから電子透かしを抽出するのには、はるかにコストがかかる。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】特開平９−１９１３９４号公報
【特許文献２】米国特許第５，３１９，７３５号明細書
【特許文献３】米国特許第５，８４８，１５５号明細書
【特許文献４】特開平１０−３０８８６７号公報
【特許文献５】特開平１０−１４５７５７号公報
【非特許文献】
【００１８】
【非特許文献１】Andrew B. Watson, "DCT Quantization Matrices Usually Optimized for Indirect Images", SPIE, vol. 1913(1993), pp. 202-216
【非特許文献２】Christine I. Podilchuk and Wenjun Zeng, "Digital Image Watermarking Using Visual Models", Proc. of EI '97, vol. 3016
【非特許文献３】Albert J. Ahumada Jr. and Heidi A. Peterson, "Luminance-Model-Based DCT Quantization for Color Image Compression", SPIE, Vol. 1666(1992), pp. 365-374
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明の目的は、デジタルデータへ電子透かしを挿入するためのよりシンプルで効率的でロバストであり、かつ、アルゴリズムの変更に柔軟に対応できる電子透かしの挿入方法と、デジタルデータから電子透かしを抽出するためのよりシンプルで効率的でロバストであり、かつ、アルゴリズムの変更に柔軟に対応できる電子透かしの検出方法を提供することにある。さらに本発明は、さまさまな幾何学的歪みの存在下であっても電子透かしを検出できる電子透かしの挿入方法および検出方法とを提供することも目的とする。
【課題を解決するための手段】
【００２０】
本発明の第１の面に従えば、電子透かし入れがなされているデータの複数のｎ×ｎブロックを有する電子透かし入れされたデータを受信するステップと、電子透かし入れがなされているデータの複数のｎ×ｎブロックを合計して、少なくとも１つのｎ×ｎブロックの合計電子透かしデータを作成するステップと、各ｎ×ｎブロックからの所定の電子透かし入れされたデータを合計して、抽出された電子透かしの各要素を生じることにより、少なくとも１つのｎ×ｎブロックから電子透かしを抽出するステップと、を有する、電子透かし入れがなされたデータから電子透かしを検出する方法が、提供される。
【００２１】
すなわち本発明は、画像の忠実度を遥かに良好に制御する人間の視覚系の特定のモデルを利用する、電子透かしの新しい挿入方法に関係している。本発明によれば、原画とは区別できないように電子透かしを挿入した画像であっても、フィッシャーのＺ変換値にして１５以上となる（すなわち、電子透かし挿入画像と電子透かしとが無相関である確率が、正規分布において標準偏差の１５倍よりも外側の領域に相当する確率以下となる）ような大きなレスポンスが得られることがテストから判っている。
【００２２】
本発明の方法では、種々のタイプのアタックに対するロバストさ（ロバストネス）の程度を、その特定のアタックと容易に関連づけられる方法によって制御する。
【００２３】
本発明の方法は適応性を有するため、検出器を変えることなしで、人間の視覚系モデルおよびアタック処理技術をあとで変更できる。その結果、すでに多くの検出器を取り付けた後であっても、電子透かし入れ、特にＤＶＤ（デジタルビデオディスク；digital video disk）の電子透かし挿入方式の改良を継続することができる。それは、既存の復号器を変えずに符号化技術を改良できるＭＰＥＧビデオの状況に似ている。
【００２４】
本発明の挿入方法を使用すれば、ＭＰＥＧドメインもしくは伸長ドメイン内でのシンプルな検出アルゴリズムが可能となる。
【００２５】
本発明は、また、着信映像がＭＰＥＧ圧縮であっても伸長されたものであっても、実施が容易で、分析が容易で、かつ計算コストが低い新しい検出方法にも関連している。
【００２６】
本発明において、複数のｎ×ｎブロックを合計するとは、ｎ×ｎブロックが数学上のｎ×ｎ行列であるとみなして、これら複数のｎ×ｎブロックのそれぞれに対応する行列の行列和を算出し、すなわち、行列の要素ごとに加算を行い、算出結果のｎ×ｎ行列に対応するｎ×ｎブロックを求めることである。算出結果のｎ×ｎブロックのことを合計ブロックともいう。
【００２７】
本発明は、さらに、データの中に多数のパターンを隠す新しい挿入方法にも関する。これらのパターンは２つのカテゴリーに分類され、それらは、１）検出中に並進シフトを補償するためのレジストレーション（位置決め）パターンと、２）電子透かしの情報内容を符号化する電子透かしパターンである。
【００２８】
すなわち本発明の第２の面に従えば、電子透かし入れされたデータが歪みを受けた後であっても電子透かし信号が抽出できるように、抽出可能な電子透かし信号を画像データに挿入する電子透かし挿入方法であって、電子透かし入れされるべき画像データを準備するステップと、画像データをコピーするステップと、画像データのコピーに、予め規定された歪みを加えるステップと、画像データの歪んだコピー内に電子透かし信号を挿入するステップと、画像データの歪んだコピーに電子透かし信号を挿入して得られた被電子透かし入れ画像データから、歪んだ画像データのコピーを差し引いて、電子透かしパターンを生成するステップと、電子透かしパターンに対して逆歪み操作を施し、歪んでいない画像データに対する電子透かし入れされたパターンを発生するステップと、電子透かし入れされるべき画像データと、歪んでいない画像データに対する電子透かしパターンとを結合して、電子透かし入れされたデータを得るステップと、を含む、電子透かし挿入方法が提供される。
【００２９】
本発明の第１の面に従えば、２次元並進歪みを受けている電子透かし入れされた画像データから電子透かしを抽出する電子透かし検出方法であって、受信した歪んでいる電子透かし入れされた画像データを一連の複数のｎ×ｎブロックへ分割するステップと、所定数のｎ×ｎブロック内の電子透かし入れされた画像データをまとめて合計するステップと、合計されたｎ×ｎブロックが空間ドメインでのものでない場合には、その合計されたｎ×ｎブロックを空間ドメインでのものに変換するステップと、合計されたｎ×ｎブロックの２次元並進歪みを決定するステップと、決定された歪みに従って、合計されたｎ×ｎブロックをシフトするステップと、シフトされたｎ×ｎブロックを変換係数ドメインでのものに変換するステップと、変換されたｎ×ｎブロックから、考えられる電子透かし信号を抽出するステップと、考えられる電子透かしと既知の電子透かしとの相関を計算するステップと、考えられる電子透かしの巡回シフトに対して相関を計算するステップを繰り返すステップと、相関を計算するステップでの結果に基づいて電子透かしの存在を決定するステップと、を有する、電子透かし検出方法が、提供される。
【００３０】
本発明によれば、電子透かし入れされたデータ（被電子透かし入れデータ）が予め規定されたスケール変化を受けた後であっても、電子透かし検出器を変更することなく、電子透かしを検出することができる電子透かしの挿入方法が提供される。
【００３１】
本発明によれば、さらに、ＭＰＥＧドメインにおいても伸長ドメイン（非圧縮ドメイン）においても計算コストが低廉である電子透かしの検出方法が提供される。
【００３２】
またさらに、本発明によれば、検出器を変更する必要なく、アタックに耐えるデジタル電子透かし方法が提供される。
【発明の効果】
【００３３】
以上説明したように本発明によれば、種々のアタックに対してロバストであり、検出器を変えることなく挿入／抽出アルゴリズムの変更に対応でき、シンプルかつ少ない計算量で電子透かしの挿入や抽出を行えるようになるという効果がある。さらに本発明は、さまさまな幾何学的歪みの存在下であっても電子透かしを検出できるようになるという効果がある。
【００３４】
空間ドメインおよびＤＣＴドメインの両方で電子透かしを計算効率よく検出できるようにするために、本発明では、ＤＣＴドメイン内において全ての８×８ブロックを合計した結果、もしくはＤＣＴドメイン内において全ての８×８ブロックのサブセットを合計した結果に、電子透かしを挿入することができる。この方法の主要な利点は、画像が空間ドメイン内でしか得られない場合には、空間ドメイン内で総和を計算することもできる。この場合は、総和をとることによっていくつかの８×８ブロックを求め、次に、この１ブロックだけをＤＣＴドメインへ変換すればよい。それは、ＤＣＴブロックの合計が、画素値の合計にＤＣＴを行った結果に等しいためである。したがって、ＤＣＴドメインおよび空間ドメイン内での復号の計算コストはほぼ同じになる。
【００３５】
ＤＣＴブロックを合計した結果に電子透かしを挿入することの第２の利点は、画像全体に電子透かしを配分する等価な方法が無数にあることである。例えば、電子透かしを挿入するために、ＤＣＴブロックを合計して得られるブロックの第ｉ番目の係数をΔｉだけ変化させる必要がある場合、画像内にＭブロックがあれば、個別の各ブロックへΔｉ／Ｍを加算することができる。あるいは、画像忠実度の一時的な問題点を無視すれば、ブロック１においては第ｉ番目の係数にΔｉを加算して、残りのＭ−１ブロックは不変とすることができる。この１対多マッピング（ある１つの電子透かし挿入結果を実現する方法が複数存在すること）により、復号器を変えずに挿入アルゴリズムを変えることができる。このことは非常に重要な特徴である。なぜなら、ある電子透かし入れの応用では、多数のハードウェア復号器が出荷されると、復号器を変更することは現実的でなくなるためである。しかしながら、ここに記載する方法を使用することによって、電子透かしの挿入アルゴリズムを改良すれば、復号器を変えなくても検出結果を改善することができるのである。
【００３６】
ＤＣＴブロックを合計した結果に電子透かし入れを行うことの第３の利点は、それらの和から抽出される電子透かし信号が、忠実性の問題を引き起こすことなくその信号を変更できる量と比較して、変動が小さいという点である。これはすなわち、得られる画像がオリジナルのものと同一に見えることを条件としても、合計ＤＣＴブロックが必要な電子透かし信号と完全に一致するように画像を変化させることが、多くの場合に可能であるということである。
【００３７】
最後に、人間の視覚系をモデル化するなどのある種の問題は周波数ドメインで最もよく実行され、幾何学変換などの他の種の問題は空間ドメインでより簡便に対処されることが、良く知られている。電子透かしを復号する計算コストは今や対称的になったため、電子透かしを改変させることがあるさまざまな信号変換に対する修正を行うために、空間ドメインから周波数ドメインへ意のままに切り替えることができる。
【図面の簡単な説明】
【００３８】
【図１】本発明の好ましい実施の形態における、メディアデータに電子透かしを挿入する方法の概略を示すフローチャートである。
【図２】ＭＰＥＧ−２符号化器の構成を模式的に示すブロック図である。
【図３】電子透かし入れがなされたデータ内の電子透かしの劣化を低減すべく改良されたＭＰＥＧ−２符号化器の構成を模式的に示すブロック図である。
【図４】電子透かし入れがなされたデータ内の電子透かしの劣化を低減すべく改良された別のＭＰＥＧ−２符号化器の構成を模式的に示すブロック図である。
【図５】図３および図４に示す符号化器における電子透かし修正部で実行される処理を説明するフローチャートである。
【図６】図５のステップ５０６で実行される処理を示すフローチャートである。
【図７】図５のステップ５０６で実行される処理の別の例を示すフローチャートである。
【図８】ＭＰＥＧ映像データから電子透かしを検出する方法を示すデータフロー図である。
【図９】伸長された映像（非圧縮映像）データから電子透かしを検出する方法を示すデータフロー図である。
【図１０】レジストレーションパターンを用いてＭＰＥＧ映像データから電子透かしを検出する方法を示すデータフロー図である。
【図１１】レジストレーションパターンを用いて、伸長された映像（非圧縮映像）データから電子透かしを検出する方法を示すデータフロー図である。
【発明を実施するための形態】
【００３９】
次に、本発明の好ましい実施の形態について、図面を参照して説明する。
【００４０】
以下の説明で使用される画像および画像データという用語は、映像（ビデオ）、画像（イメージ）およびマルチメディアデータにも同等に適用できることを理解されたい。“電子透かし（ウォータマーク；watermark）”という用語には、埋め込まれたデータ、シンボル、画像、命令もしくは任意の他の識別情報が含まれる。
【００４１】
本発明についての理解を深めるため、最初に、基本的な電子透かし入れ方法について概要を説明し、次に本発明を含む改良についての追加の説明を行う。
【００４２】
最初に、いくつかの表記について定義する。ある画像に埋め込まれる電子透かしをＮ次元のベクトルとし、Ｗ[１,...,Ｎ]と表す。以下の記述においては、Ｗ[１,...,Ｎ]はＷ[ｋ]（ｋ＝１,...,Ｎ）と同様に用いる。Ｖ[１,...,Ｎ]は、画像から抽出されるベクトル値を表し、その場合、要素Ｖ[ｋ]はＷ[ｋ]に対応する。具体的には、値Ｖ[ｋ]は、以下の式によって与えられるＤＣＴ係数の重み付け和である。
【００４３】
Ｖ[ｋ]＝Ｄ_ｋ[１]Ｆ_ｋ[１]＋Ｄ_ｋ[２]Ｆ_ｋ[２]＋…＋Ｄ_ｋ[ｎ_ｋ]Ｆ_ｋ[ｎ_ｋ]
式中、Ｄ_ｋ[ｉ]（ｉ＝１,...,ｎ_ｋ）は、Ｖ[ｋ]を計算するのに使用されるＤＣＴ係数の集合の項（メンバ）を示し、ｎ_ｋは項の数を示し、Ｆ_ｋ[ｉ]（ｉ＝１,...,ｎ_ｋ）は、フィルタ処理に関係する重み付け係数である。Ｆ_ｋの概念は、各係数についてどの程度の大きさのノイズが予想できるかに従って、ＤＣＴ係数に重み付けを行おうというものである。Ｖ[１,...,Ｎ]を計算するには、画像全体にわたって最初にｎ×ｎのＤＣＴ係数を計算する。次に、その係数をＮ個の集合に分類し、そのそれぞれをＶ[１,...,Ｎ]の各要素に関連づける。ＤＣＴ係数の分類の規則は予め設定したものであり、電子透かしの挿入および検出の両方に同じ規則を使用する。
【００４４】
画像中に電子透かしを挿入する前に、画像中に既に存在する電子透かしを見つけるために、検出アルゴリズムを画像に適用する。画像が電子透かしを含まない場合、抽出値Ｖ[１,...,Ｎ]は、いかなる電子透かしＷ[１,...,Ｎ]とも相関しない、正規分布乱数となろう。電子透かしＷ[１,...,Ｎ]は、各Ｄ_ｋ[１,...,ｎ_ｋ]（ｋ−１,...,Ｎ）をわずかに変化させて抽出値Ｖ[１,...,Ｎ]が電子透かしＷ[１,...,Ｎ]に強く相関するようにすることによって、画像中に挿入される。ここで、Ｖ[１,...,Ｎ]のターゲット値をω[１,...,Ｎ]で表す。すなわち、電子透かしＷ[１,...,Ｎ]を挿入することで、値Ｖ[１,...,Ｎ]をω[１,...,Ｎ]に変える。ターゲット値ω[１,...,Ｎ]は、電子透かしＷ[１,...,Ｎ]と非常に高い相関を有し、後述するように決定される。
【００４５】
ターゲット値ω[１,...,Ｎ]を決定した後、差ω[ｋ]−Ｖ[ｋ]を、ＤＣＴ係数Ｄ_ｋ[１,...,ｎ_ｋ]の間で配分する。次に、割り当てられた差値を、対応するＤＣＴ係数Ｄ_ｋ[１,...,ｎ_ｋ]に加えることで、電子透かしを挿入する。このＤＣＴ係数の変更は、画像の外観（見た目）を変えないように行わなければならない。
【００４６】
差ω[ｋ]−Ｖ[ｋ]を配分するに当たり、人間の視覚プロセスの特性を考慮する。画像に視覚でわかる変化を起こさない変化量は、各ＤＣＴ係数Ｄ_ｋ[ｉ]で異なる。その量は、人間の視覚プロセスによって決まり、この人間の視覚プロセスは、計算モデルによってほぼシミュレーション可能である。この変化量のことを「スラック(slack)」と称する。スラックを各ＤＣＴ係数について計算し、それを、ＤＣＴ係数間での差ω[ｋ]−Ｖ[ｋ]の配分に使用する。次に、人間の視覚プロセスのモデルを用いてスラックの値を計算する方法について、説明する。
【００４７】
本発明に使用される人間の視覚感度の好ましい計算モデルは、SPIE, vol. 1913(1993), pp. 202-216のアンドリュー  ビー．  ワトソン(Andrew B. Watson)の文献"DCT Quantization Matrices Usually Optimized for Indirect Images"に見られる。このモデルは、１９９７年２月９〜１４日のクリスティン  アイ．  ポディルチャック(Christine I. Podilchuk)およびウェンジュン  ツゥエング(Wenjun Zeng)の文献"Digital Image Watermarking Using Visual Models", Proc. of EI '97, vol. 3016で電子透かし入れに応用されている。本発明は、(i)復号器において元の非電子透かし入れ画像を必要としない、(ii)個別の８×８ブロックからではなく、８×８ブロックの集合の合計からウォータマークを抽出する、の各点においてポディルチャックおよびツゥエングのそれとは異なっている。現在はこの視覚モデルを用いているが、他の計算モデルも使用できる。
【００４８】
画像のブロックＤＣＴの各要素ｄ[ｉ,ｊ]について、このモデルは、その要素の「スラック」と呼ばれる値Ｓ[ｉ,ｊ]を計算する。このスラック値は、変化が肉眼で認められるようになるまでに、ある特定のｄ[ｉ,ｊ]値をどれだけ変えることができるかを示すものである。スラック値は３段階で計算される。第１段階では、人間の視覚系のコントラストマスキング現象をモデル化し、各種周波数での視覚感度をモデル化し、変化に対する視覚感度の周波数間での差を処理する。第２段階では、人間の視覚系の輝度マスキング現象をモデル化し、視覚系が明領域での変化より暗領域での変化に対して感受性が高いという事実を処理する。第３段階では、変化に対する感受性が、部分的に、周波数が変化するパーセンテージによって決まる（すなわち、小さい値を有するＤＣＴ係数はわずかしか変化しないが、相対的に大きい値を有する係数は相対的に大きい変化を起こし得る）という事実を処理する。
【００４９】
その知覚モデルは、空間８×８ＤＣＴの異なる係数に対する人間の視覚系の相対感度を示す値の行列を利用する。この行列を計算する式は、アルバート  ジェー．  アヒュマダ  ジュニア(Albert J. Ahumada Jr.)およびヘイディ  エイ．  ピーターソン(Heidi A. Peterson)の文献"Luminance-Model-Based DCT Quantization for Color Image Compression", SPIE, Vol. 1666(1992), pp. 365-374から得られる。
【００５０】
画像の８×８ＤＣＴ係数の全てについてのスラックを計算した後、スラックを各Ｄ_ｋ[１,...,ｎ_ｋ]に割り付けることができる。これらのスラックをＳ_ｋ[１,...,ｎ_ｋ]と称する。そこで、視覚的影響を最小限としながら、全Ｄ_ｋにＶの変化を配分することが可能である。これは、下記式に従って行う。
【００５１】
【数１】
2010136456.tif 000003
【００５２】
式中、Ｄ’_ｋ[１,...,ｎ_ｋ]は、修正された８×８ＤＣＴ係数であり、ω[ｋ]およびＶ[ｋ]は、それぞれωおよびＶのｋ番目の要素である。この式の効果は、電子透かしベクトル（ω[ｋ]−Ｖ[ｋ]）の所定の要素における所望の変化を、Ｖ［ｋ］算出の際に合計するＤＣＴ係数の全体にわたって、それらＤＣＴ係数のスラックに応じて比例配分することである。説明のため、２つの簡単な例を考える。１）スラックＳ_ｋ[ｍ]を除く全てのスラックがゼロである場合、Ｓ_ｋ[ｊ]Ｆ_ｋ[ｊ]の全ての値の合計はＳ_ｋ[ｍ]Ｆ_ｋ[ｍ]に等しく、Ｄ_ｋ[ｍ]のみが変化する。それは（ω[ｋ]−Ｖ[ｋ]）の全値だけ変化する。２）全てのスラックが等しく、全ての係数Ｆ_ｋ[ｉ]＝１の場合、各Ｄ_ｋ[ｉ]は同じ量だけ変化する。
【００５３】
これらの変化を行った後、全ての８×８ＤＣＴを空間ドメインに変換し戻され、その結果は、電子透かし入れされた画像となる。与えられたｋについての全てのＤ_ｋ[ｉ]Ｆ_ｋ[ｉ]の合計がω[ｋ]に等しいことを示すのは容易である。これを行う処理は、「画像へのオメガの挿入」と称される。画像に対してアタックがまだ行われていない場合、得られた画像から抽出される電子透かしは、正確にωであり、ω＋ノイズではない。
【００５４】
議論すべき重要な問題が２つある。第１は、ターゲット値ωの決定方法であり、第２は、どのように電子透かしをロバストにするかである。
【００５５】
以前のやり方では、ωに相当する値は次式のように計算していた。
【００５６】
ω＝Ｖ＋α＊Ｗ
ここで、αは小さい定数であり、Ｗはゼロ平均電子透かし信号である。ここでは同じ式を使用することもできるが、制約が大きいため、本発明によって本来可能である強い電子透かしを実現することはできない。そこで、このかわりに次式を用いる。
【００５７】
ω＝ｍｅａｎ(Ｖ)＋β＊（Ｖ−ｍｅａｎ(Ｖ)））＋α＊Ｗ
ここでｍｅａｎ（）は平均値を与える関数である。これによって、大抵の場合は、画像に知覚できる変化を生じることなく、電子透かしＷと完全な相関を有するωを挿入することができる。
【００５８】
この式で得られる結果は、電子透かし信号と、原信号のノイズ（画像）信号成分との重み付け和である。βが０に設定されると、結果はＷと完全な相関を有するωとなる。
【００５９】
非アタック画像に対する信号対ノイズ比は、次式で表される。
【００６０】
ＳＮＲ＝α＊ｓｔｄ(Ｗ)／β＊ｓｔｄ(Ｖ)
ここで、ｓｔｄ(Ｘ)はＸの標準偏差である。
【００６１】
忠実性またはロバストさなどの異なる基準を最大とする最適化に基づいて、αおよびβを選択する方法が数多くある。
【００６２】
この時点まででも、電子透かし挿入方法は完成している。しかしながら、この方法には、明示的な人間の視覚のモデリングが含まれるが、電子透かしをロバストにするための方法は、明示的には何も含まれていない。事実、これまでに記載した方法では、高い周波数が最大スラックを有するため、電子透かしのできるだけ多くの部分を高い周波数へ配分するよう試みるが、それはロバストさの点からは思わしくないことである。
【００６３】
所与の１組のアタックもしくは信号劣化に対して電子透かしをロバストとするために、最初に、これらのアタックが画像内の８×８ＤＣＴのさまざまな係数にどのように影響するかを考慮する必要がある。次に、アタックもしくは信号劣化により同じように影響されるＤＣＴ係数が分類され、あたかも独立した画像であるかのように電子透かし入れがなされる。
【００６４】
次に、簡単な例を示す。ここでは簡単のため、考えられる２つのアタックのみを配慮するものとする。画像の左側から２４列（カラム）の画素（ピクセル）を切り取る、もしくは画像の右側から２４列の画素を切り取るものとする。その結果、３グループのＤＣＴ係数が生じ、それは、左端３列の８×８ＤＣＴブロックからのもの、右端３列からのもの、および画像の残りの列からのものである。これらの各グループ内の全てのＤＣＴ係数が、任意の所与のアタックにより、共に生き残るかもしくは破壊される。各グループが独立した画像であるかのように電子透かし入れされると、少なくとも１グループからの電子透かしが一般的にアタックから生き残り（２４列の切り取り攻撃が考えられる唯一のアタックであるとする）、抽出される電子透かしはそのグループからの正しい電子透かしと、アタックによりダメージを受けたグループからの幾分ノイズの多い電子透かしを合わせたものとなる。
【００６５】
より興味深い例は、低域および高域フィルタアタックである。全ての低周波数成分を一つのグループに分類することが可能であり、全ての高周波数成分を１以上の他のグループに分類することができる。ＤＣＴ係数をＮ個の集合に分類するための所定の規則が、各集合が多くの異なる周波数の係数を含むように作られている場合、完全な電子透かしを各グループに挿入することができる。このとき、もし高周波数成分が除去されても、電子透かしはまだ低周波数成分で検出することができ、その逆もいえる。
【００６６】
より多くのグループへＤＣＴ係数が分割されると、電子透かしは一層ロバストとなる。しかし、目に見える歪みを生じることなく変化を分散させることが次第に困難となるため、コストが生じる。よって、グループの数とこのコストとのバランスをとることが重要になる。
【００６７】
ここで注目すべき重要な点は、たとえ検出器が広範に使用されるに至った後であっても、分割でのグループ数とコストとの最善のバランスを達成できるということである。検出器を全く変えることなく、多様なアタックに対して電子透かしをロバストにすべく挿入アルゴリズムを修正することができる。
【００６８】
現在、３つのグループのみを使用している。一つのグループは、ほとんどの低周波数ＤＣＴ係数をまとめるたものである。他の２つのグループは、それぞれ、より高い周波数を代表するものである。
【００６９】
好ましい方法においては、相対的に高い周波数には電子透かしを入れない。その理由は、それらがアタック（検出で使用されるフィルタの設計によって処理される）の影響を受けやすいからではない。むしろ、相対的に高い周波数に電子透かしを入れると、ＭＰＥＧ圧縮率がかなり低くなるからである。ただし、より高い周波数を含む他のグループを加えることも、別の選択肢として考えられよう。
【００７０】
次に、前述の方法を実現する電子透かし挿入手順について具体的に説明する。
【００７１】
図１は、上述した電子透かしの挿入方法のフローチャートである。ステップ１０において、デジタル画像が、ｎ×ｎブロック（縦横それぞれｎ画素であるブロック）からなる集まり、好ましくは複数個の８×８ブロック、へ分割される。そして、各ブロックの離散コサイン（余弦）変換（ＤＣＴ）が周知の方法で計算され（ステップ１２）、さまざまなアタックに対して同じように応答するグループへＤＣＴ係数を分離する（ステップ１４）。そしてまず、第１のグループＧを選択する（ステップ１６）。
【００７２】
次に、選択されたグループＧ内のＤＣＴ係数だけを使用して、電子透かしＶを抽出する（ステップ１８）。Ｖに類似しているが電子透かしＷと高い相関を有するように、新しい信号（ターゲット値）ωを決定する（ステップ２０）。
【００７３】
知覚スラックに従って、グループＧ内のＤＣＴ係数にω−Ｖの端数を加算する（ステップ２２）。そして、グループＧが最後のグループであるかどうか確認する（ステップ２４）。最後のグループでなければ、次のグループＧを選択して（ステップ２６）、ステップ１８に戻り、ステップ１８において、次のグループＧ内の項だけを使用して電子透かしＶを抽出し、ステップ２４において最後のグループＧが見つかるまで、この手順を継続する。ステップ２４で最後のグループであると判断したときは、次に、ステップ２８において、ブロックの逆ＤＣＴを計算して、電子透かし入れされた画像を得る。
【００７４】
この挿入方法には、いくつかの別の工程も考えられる。例えば、ＤＣＴ係数間でのωとＶとの間の差の分配を推計的に行って、タンパリングの防止を助け、タンパリングへの感受性を低減することができる。
【００７５】
また、ロバストさのためのＤＣＴ係数のグループ分けをダイナミックに実行することができる。例えば、挿入プログラムは、画像へのさまざまなアタックをシミュレートして、ＤＣＴ係数の値に及ぼす影響を求めることができる。そしてプログラムは、同様な影響を受けるグループへ適切に係数を割り当てることができる。
【００７６】
電子透かしの挿入装置ではユーザインターフェイスを設計し、それにより、ユーザは、２つのパラメータを設定することができる。２つのパラメータは、（１）原画像と電子透かし入れされた画像との間の最大知覚差（Ｊ）と、（２）所定の集合のアタックのいずれかの後で検出できなくなることへの最大許容確率と、である。アルゴリズムは、許容知覚変化Ｊにしたがい、多数の画像内へ自動的に電子透かしを挿入する。そして、アタックのシミュレーションを行って各々の画像をチェックする。もし、画像が、指定されたロバストさ制約（検出もれの最大許容確率）を満たすことができない場合には、ユーザに知らせ、ユーザは画像忠実度を補償するかどうか、あるいはロバストネスに対して画像忠実度を釣り合わせるかどうかを手動で決定することができる。
【００７７】
さらに、ＤＣＴ係数全体でのωとＶの間の差の配分を変えて、ＭＰＥＧ量子化による劣化を明示的に補償することができる。上述の電子透かし挿入方法を用いると、電子透かし入れされたデータでの電子透かしの劣化が生じる場合がある。電子透かし入れされたデータにおいてＭＰＥＧ圧縮後に電子透かしを増強するために、いくつかの方法が可能である。
【００７８】
図２は、典型的なＭＰＥＧ−２符号化器の構成を模式的に示す図である。図２には、ＰピクチャのＭＰＥＧ−２符号化を実行する上で、あるいは組み合わされたフレーム間予測とＤＣＴ符号化を実行する上で、不可欠の要素を示してある。入力画像データ（入力画像シーケンス）から予測画像を減じるための減算器３０が設けられており、入力画像データは減算器３０の一方の入力に与えられる。予測画像は、フレームメモリ３２内に格納され、減算器３０の他方の入力に与えられている。また、符号化器には、減算器３０の出力側に接続して離散コサイン変換（ＤＣＴ）を行うＤＣＴ計算器３４と、ＤＣＴ計算器３４の出力に接続した量子化器３６と、量子化器３６の出力がそれぞれ入力される可変長符号化器３８および逆量子化器４０と、逆量子化器４０の出力が入力される逆ＤＣＴ計算器４２と、ＩＤＣＴ計算器４２の出力とフレームメモリ３２からの（前フレームの）予測画像とを加算してフレームメモリ３２に格納する加算器４４とが設けられている。
【００７９】
減算器３０において、入力画像から予測画像が差し引かれる。ＤＣＴ計算器３４は、減算器３０からの出力信号に対し、離散余弦変換（ＤＣＴ）を行い、得られたＤＣＴ係数は、量子化装置３６で量子化される。量子化装置３６の出力である量子化ＤＣＴ係数は、ハフマン符号化が行われる可変長符号化器３８に送られ、このハフマン符号化の結果は、符号列として可変長符号化器３８から出力される。量子化ＤＣＴ係数は、逆量子化装置４０にも送られてそこで逆量子化され、この逆量子化されたＤＣＴ係数は、逆ＤＣＴ計算器４２によって、逆離散コサイン変換（ＩＤＣＴ；逆ＤＣＴ）を施される。逆ＤＣＴの結果は、加算器４４で、フレームメモリ３２から出力された予測画像に加算され、これにより、復号器で取得されるものと同じであると予想される画像を再構築する。再構築画像は、「局所復号画像」と称する。この局所復号画像をフレームメモリ３２に保存して、予測画像を形成する。
【００８０】
次に、ＭＰＥＧ量子化を補償する方式について述べる。
【００８１】
図３は、電子透かし入れがなされたデータ内の電子透かしの劣化を低減すべく改良されたＭＰＥＧ−２符号化器の構成を模式的に示すブロック図である。
【００８２】
この符号化器は、図２に示す符号化器と比較すると、減算器３０の前段側に、入力画像データへのＤＣＴを実行するＤＣＴ計算器５０と、ＤＣＴ計算器５０の出力に電子透かしを加算する加算器５２と、加算器５２の出力に対して逆ＤＣＴを実行して加算器３０に出力する逆ＤＣＴ計算器５４と、予測画像に対してＤＣＴを実行するＤＣＴ計算器５６と、量子化器３６の出力が入力されるもう一つの逆量子化器５８と、ＤＣＴ計算器５６の出力と逆量子化器５８の出力とを加算する加算器６０と、量子化器３６からの量子化情報を利用し、加算器６０からの出力に基づいて電子透かしの修正を行う電子透かし修正部６２と、量子化器３６の出力と電子透かし修正部６２の出力とを加算する加算器６４と、を設けた点で相違し、加算器６４の出力が可変長符号化器３８および逆量子化器４０に入力されている。
【００８３】
この符号化器では、ＭＰＥＧ−２符号化を行う前に、ＤＣＴ計算器５０において入力画像についてＤＣＴが実行され、加算器５２において、ＤＣＴ計算器５０からのＤＣＴ係数に電子透かし信号が加算される。電子透かし情報を含む出力ＤＣＴ係数に対して、逆ＤＣＴ計算器５４で逆ＤＣＴが施される。逆ＤＣＴ計算器５４の出力は、電子透かしを含む画像である。これらの電子透かし入れされた画像は、ＭＰＥＧ−２符号化器へ送られ、上述したようにＭＰＥＧ−２符号化が行われる。さらにこの実施の形態では、ＭＰＥＧ−２圧縮に適合するように、電子透かし情報が修正される。
【００８４】
電子透かし情報の修正に関しては、まず、予測画像についてのＤＣＴ係数をＤＣＴ計算器５６によって計算する。量子化器３６から出力された量子化値を、逆量子化器５８で逆量子化する。これら逆量子化の結果とＤＣＴ計算器５６から出力されたＤＣＴ係数とは、加算器６０によって加算される。この加算結果は、復号器で形成されると予想される復号画像についてのＤＣＴ係数と対応する。そのＤＣＴ係数は、電子透かし修正部６２に入力する。電子透かし修正部６２は、電子透かし補正信号を出力する。加算器６４は、電子透かし修正部６２からの電子透かし補正信号を、量子化器３６からの量子化値に加算する。加算装置６４の出力は、可変長符号化器３８および逆量子化装置４０への入力として用いられる。
【００８５】
次に、電子透かし修正部６２で実行される処理について説明する。最初に、この処理を説明するために、いくつかの新たな表記を導入する。Ｄ_ｋ[ｉ]に相当する量子化値、すなわち値Ｖを計算するためのｋ番目の集合のｉ番目の項の量子化値をＤｑ_ｋ[ｉ]とする。Ｄｑ_ｋ[ｉ]を得る上で使用される量子化ステップサイズの大きさをＱ_ｋ[ｉ]とする。逆量子化器５８で計算されたＤｑ_ｋ[ｉ]の逆量子化値を、ＤＣＴ計算器５６から出力された対応するＤＣＴ係数に加算することで得られる加算器６０の出力値を、Ｄｒ_ｋ[ｉ]とする。電子透かしの挿入において値Ｖ[１,...,Ｎ]を計算したのと同じ方法で、加算器６０の出力値Ｄｒ_ｋ[ｉ]から抽出された値を、Ｖｒ[１,...,Ｎ]とする。電子透かし修正部６２では、ターゲット値ω[１,...,Ｎ]も利用可能であると仮定する。
【００８６】
図５は、電子透かし修正部６２で実行される処理を説明するフローチャートである。最初に、電子透かし要素の指数（インデックス）ｋを１に設定する（ステップ５００）。次に、Ｖｒ[ｋ]の値を下記式によって計算する（ステップ５０２）。
【００８７】
Ｖｒ[ｋ]＝Ｆ_ｋ[１]Ｄｒ_ｋ[１]＋…＋Ｆ_ｋ[ｎ_ｋ]Ｄｒ_ｋ[ｎ_ｋ]
式中、重み付け係数Ｆ_ｋ[１,...,ｎ_ｋ]は、Ｖ[ｋ]の計算で使用したものと同じ値である。次に、値Ｖｒ[ｋ]とターゲット値ω[ｋ]との間の差の絶対値と、その差の符号を、以下の式によって計算する（ステップ５０４）。
【００８８】
Ｄｉｆ＝｜Ｖｒ[ｋ]−ω[ｋ]｜
ｓ＝Ｓｉｇｎ（Ｖｒ[ｋ]−ω[ｋ]）
ここで、
【００８９】
【数２】
2010136456.tif 000004
【００９０】
である。
【００９１】
この値Ｄｉｆは、量子化プロセスにおいて発生した、加算器５２で挿入された電子透かしの歪みに対応する。
【００９２】
絶対値Ｄｉｆと符号ｓに基づいて、ステップ５０６において、電子透かし補正信号を発生する。ステップ５０６での処理は後述する。電子透かしのｋ番目の要素に関係するＤＣＴ係数についての電子透かし補正信号の発生の後、ステップ５０８において指数ｋをＮと比較する。ｋ＞Ｎの場合、処理は終了する。ｋ≦Ｎの場合、ステップ５１０で値ｋを１だけ増加させ、処理をステップ５０２に戻す。このようにして電子透かし補正処理が行われ、得られた電子透かし補正信号が最終的に加算器６４に出力される。
【００９３】
次に、図６のフローチャートを用いて、図５のステップ５０６で実行される処理について、さらに詳しく説明する。このステップ５０６では、電子透かしのｋ番目の要素に関係するＤＣＴ係数についての電子透かし補正信号を発生する。
【００９４】
最初に、ステップ５２０において、配列ΔＤｑ_ｋ[ｉ]（ｉ＝１,...,ｎ_ｋ）を全てゼロに設定する。次に、ステップ５２２において、値ｊを１に設定する。そして、ステップ５２３において、並べ替え関数ｐ(ｊ)によって、ＤＣＴ係数の指数（インデックス）ｉを見出す。関数ｐ(ｊ)は、１からｎ_ｋまでの整数を並べ換えた後に得られた順列のｊ番目の値を返す。最も簡単な例はｐ(ｊ)＝ｊである。次に、ステップ５２４において、ΔＤｑ_ｋ[ｉ]に値−ｓを格納し、値ＤｉｆをＱ_ｋ[ｉ]Ｆ_ｋ[ｉ]だけ小さくする。これは、加算器６４でΔＤｑ_ｋ[ｉ]をＤｑ_ｋ[ｉ]に加算することで、量子化値Ｄｑ_ｋ[ｉ]を−ｓだけ変化させることを示している。値ｓは１または−１であり、このことから、量子化値における変化は１である。すなわち、復号器の逆量子化器で得られた逆量子化値は、−Ｑ_ｋ[ｉ]、すなわち１ステップサイズだけ変化する。その更新後の値Ｄｉｆは、補正された量子化値Ｄｑ_ｋ[ｉ]＋ΔＤｑ_ｋ[ｉ]（ｉ＝１,...,ｎ_ｋ）を用いて計算したω[ｋ]とＶｒ[ｋ]との間の差の絶対値と同一である。ステップ５２４の後、ステップ５２６において、値Ｄｉｆとゼロ、および指数ｊとｎ_ｋとを比較する。Ｄｉｆ＜０またはｊ＞ｎ_ｋの場合、このサブルーチンは終了する。この条件が満足されない場合は、ステップ５２８で指数ｊを一定量Δｊだけ大きくしてから、処理をステップ５２３に戻す。
【００９５】
図６に示した手順ではなく、図７に示した別の手順を、ステップ５０６の処理手順として用いることができる。図７に示した処理手順では、量子化値Ｄｑ_ｋ[ｉ]がゼロであるか否かをチェックするステップ５３０を、図６におけるステップ５２３とステップ５２４の間に加え、ステップ５２４が、量子化値Ｄｑ_ｋ[ｉ]がゼロ以外の値である場合にのみ実行されるようにする。ゼロからゼロ以外の値への量子化値の変更によってビット数が大幅に上昇するのが一般的であることから、これによって、電子透かし情報を補正したことに起因するビット数の上昇を抑えることができる。
【００９６】
図４は、電子透かし入れがなされたデータ内の電子透かしの劣化を低減すべく改良された別のＭＰＥＧ−２符号化器の構成を模式的に示すブロック図である。この符号化器の基本的概念は、図３を用いて説明したものと同じであるが、入力原画像からの予測画像の減算を、空間ドメインではなく、ＤＣＴドメイン内で実行している点で相違する。したがって、図４に示す符号化器は、図３に示す符号化器と比較して、減算器３０、ＩＤＣＴ計算器５４、ＤＣＴ計算器３４,５６が設けられておらず、その代わり、予測画像のＤＣＴを実行するＤＣＴ計算器７０と、加算器５２の出力からＤＣＴ計算器７０の出力を減算する減算器７２を設けた構成となっている。減算器７２の出力が量子化器３６に与えられるとともに、ＤＣＴ計算器７０の出力は加算器６０にも与えられている。この符号化器では、入力画像データのＭＰＥＧ圧縮のためのＤＣＴは、初段のＤＣＴ計算器５０で行われる。
【００９７】
フレームメモリ３２から出力された予測画像に対し、ＤＣＴ計算器７０によりＤＣＴが実行され、その結果は、減算器７２により、電子透かし入れされたＤＣＴ係数から差し引かれる。減算の結果は量子化器３６に送られ、その後、図３に示したものと同様にして、電子透かし補正が実行される。減算器７２から出力される結果は、ＤＣＴの線形性により、図３でのＤＣＴ計算器３４から出力された結果と同じである。従って、これらの処理とそれに続く量子化器３６での量子化によって得られた結果は、図３に示したものと同じである。図４に示す符号化器によれば、図３に示すものよりも、ＤＣＴ計算の回数が減る。
【００９８】
次に、画像内の電子透かしを検出する検出手順について説明する。
【００９９】
ＭＰＥＧビデオが入力画像データ形式である場合、以下の検出プロセスによって、電子透かしＷが存在するか否かを決定する。ここで、Ｗ[１,...,Ｎ]は、試験対象の電子透かしである。
【０１００】
ハフマンコードを復号するが、逆ＤＣＴは計算しないようにすることで、各フレーム（少なくとも各Ｉフレーム）に関して、８×８のＤＣＴ係数のアレイが得られる。
【０１０１】
次に、電子透かしの挿入時に行ったものと同じＤＣＴ係数の加算を行って、ベクトルＶを得る。ベクトルＶと試験対象の電子透かしＷとの間の相関係数Ｃを以下のように計算する。
【０１０２】
【数３】
2010136456.tif 000005
【０１０３】
最後に、相関係数Ｃを正規化フィッシャー(Fisher)Ｚ統計値に変換する。
【０１０４】
【数４】
2010136456.tif 000006
【０１０５】
ここでＮは電子透かしの長さである。
【０１０６】
Ｚ値は、電子透かしが存在するか否かを示す。Ｚについての好ましいしきい値は４であるが（すなわち、Ｚ≧４の場合は、電子透かしが存在することを意味する）、間違ったアラームおよび検出の見落としについての所望の発生確率に応じて、他の値を用いることもできる。
【０１０７】
図８は、ＭＰＥＧ映像入力に対する検出方法を示すデータフロー図である。入力ＭＰＥＧ映像は、ハフマン復号器・パーシャルパーサ８０へ送られる。ハフマン復号器・パーシャルパーサ８０の出力は、映像入力のｎ×ｎ、好ましくは８×８の大きさのブロックのＤＣＴ係数の集合である。
【０１０８】
ハフマン復号器・パーシャルパーサ８０から出力するｎ×ｎＤＣＴ係数は、電子透かしアキュムレータ（蓄積器）８２へ与えられる。電子透かしアキュムレータ８２は、電子透かしの長さと同じ長さのメモリを備えている。ハフマン復号器・部分パーサ８０からのＤＣＴ係数は、所定の規則に従って分類され、前述のような電子透かし抽出のために加算され、結果はメモリに蓄積される。抽出された電子透かしは比較器（コンパレータ）８４へ与えられ、そこで、前述のように抽出された電子透かしと可能性のある電子透かしとの間の相関係数を計算することにより、画像内にある可能性がある電子透かしと比較される。可能性のある電子透かしとは、映像データ内へ挿入されているであろう電子透かしの全体である。電子透かしアキュムレータやコンパレータの詳細は、例えば、上述した米国特許出願第08/746,022号に記載されている。
【０１０９】
比較器８４の出力は、検出された電子透かしが、ある電子透かしと等しい可能性を表す尤度（正規化されたフィッシャーＺ統計値）であり、尤度は可能性のある電子透かしそれぞれに対して算出される。そして、最尤電子透かしが決定され、それが画像内の電子透かしであるとみなされる。あるいは、どの電子透かしに対する尤度も所定のしきい値を越えない場合には、電子透かしは画像中に存在しないと判定する。
【０１１０】
別法として、入ってくる入力データが非圧縮画像を含む場合、画像全体について８×８ＤＣＴを実行することで得られたＤＣＴ係数に上記の方法を提供することで、埋め込まれた電子透かしを検出することができる。その場合、各８×８ブロックについてＤＣＴを行わなければならないが、ＤＣＴ係数をＮ個の集合に分類する上で精巧に作成された規則によって、ＤＣＴを多数回実行することが回避される。ＤＣＴ計算を減らす方法について説明する前に、いくつかの表記について定義する。
【０１１１】
電子透かしの要素の指数（インデックス）ｋに、８×８ＤＣＴ係数（ｉ,ｊ）の周波数の指数をマッピングする関数集合をｈ_ｍ(ｉ,ｊ)（ｉ＝１,...,８，ｊ＝１,...,８，ｍ＝０,...,Ｍ−１）とする。Ｍは関数の数を示す。従って、ｋ＝ｈ_ｍ(ｉ,ｊ)の場合、指数が（ｉ,ｊ）であるＤＣＴ係数をＤＣＴ係数のｋ番目の集合に分類して、値Ｖ[ｋ]を計算する。ここでは、Ｍ個の異なる関数ｈ_ｍ(ｉ,ｊ)（ｍ＝０,...,Ｍ−１）を準備する。ある８×８ブロックについてどの関数を選択するかは、そのブロックの行と列の番号がそれぞれｒおよびｃで示されるとして、そのブロックの数値ｒおよびｃに依存する。そうして最初に、値ｒおよびｃに従って、関数の指数ｍを見出し、次に、ｈ_ｍ(ｉ,ｊ)によって、各ＤＣＴ係数に対する集合の指数ｋを求める。本明細書において、発明の詳細な説明のここ以降の部分では、ＤＣＴ係数の分類において、この関数ｈ_ｍ(ｉ,ｊ)を用いるものとする。
【０１１２】
この場合、次のようにしてＤＣＴ計算の回数を減らすことができる。最初に、指数ｍが同一であるブロックの和を各ｍ＝０,...,Ｍ−１について計算する。その加算ブロックをＶＢ_ｍ[ｉ,ｊ]（ｍ＝０,...,Ｍ−１）で表す。次に、Ｍ個の加算ブロックＶＢ_ｍ[ｉ,ｊ]（ｍ＝０,...,Ｍ−１）についてＤＣＴを実行する。最後に、加算ブロックのＤＣＴ係数を、値ｈ_ｍ(ｉ,ｊ)に従ってＮ個の集合に分類し、各集合内で加算して、Ｖ[１,...,Ｎ]を得る。ＤＣＴが線形変換であることから、すなわちＤＣＴブロックの合計がブロックの合計についてのＤＣＴの結果に等しいことから、得られた結果Ｖ[１,...,Ｎ]は、上記の方法によって得られたＶ[１,...,Ｎ]と同じである。Ｍが画像中のブロックの総数よりかなり小さい場合は、ＤＣＴ計算の回数は大幅に減少する。そうしてこの方法によって、小さい計算コストで電子透かしを抽出することができる。
【０１１３】
図９は、上記のような非圧縮映像入力データに対する検出方法を示すデータフロー図である。
【０１１４】
非圧縮映像データは、ｎ×ｎブロックを格納するｎ×ｎアキュムレータ、好ましくは８×８ブロックを格納する８×８アキュムレータ９０へ、与えられる。メモリの必要量は、関数ｈ_ｍ(ｉ,ｊ)の数のｎ2倍である。各指数ｍについて、同じ指数ｍを有するブロックを加算し、得られたＭ個の加算ブロックをメモリで蓄積する。
【０１１５】
出力は、各ｎ×ｎブロックを加算した信号である。この出力は、ＤＣＴ計算器９２によって、離散コサイン変換が施される。変換の回数は、関数ｈ_ｍ(ｉ,ｊ)の数に比例する。変換結果は、ｎ×ｎＤＣＴの一群であり、関数ｈ_ｍ(ｉ,ｊ)に従ってＮ個の集合に分類され、加算されて、上述の電子透かし抽出が行われる。得られた電子透かしは、電子透かしアキュムレータ９４に供給され、蓄積される。電子透かしアキュムレータ９４についてのメモリの必要量は、電子透かしの長さに比例する。抽出された電子透かしは、入力として比較器９６に供給される。比較器９６への他の入力は、入力画像データに挿入されているかもしれない、と考えられる電子透かしである。比較器は、各考えられる電子透かしごとにその電子透かしが画像データ中に挿入されている確率（正規化フィッシャーＺ統計値）すなわち尤度を計算する。最も可能性の高い電子透かし（最尤電子透かし）が決定され、それが画像中の電子透かしであるみなされる。
【０１１６】
ブロックに基づくＤＣＴ法の限界は、画像の空間シフトに対するその感受性である。例えば、画像が右方向に２画素移動すると、ＤＣＴ係数が大幅に変わるために、電子透かしを検出することができない。さらに、スケーリングや回転などの一般的な変形によっても、電子透かしを検出できなくなる。
【０１１７】
これらの問題を解決するため、上記の挿入方法および抽出方法を、２つの方法で修正することができる。第１の可能な変更点は、映像の規定された歪みに耐えるように設計された複数の電子透かしを画像データに挿入することであり、第２の変更点は、複数回の加算を行うことなく、並進を補償できるよう配置するというものである。必要に応じて、その第２の変更点は、映像の任意の並進を補償するために、改良された電子透かし検出器が使用することができるレジストレーションパターンを各電子透かしに対応して１つずつ挿入するように、さらに修正することができる。
【０１１８】
上述の基本的な方法を用いて挿入された電子透かしを検出する場合、電子透かしの挿入時に使用されたのと同じｎ×ｎブロックのグリッドに基づいて、画像を分割する必要がある。ここでｎ×ｎブロックのグリッドとは、画像をｎ画素×ｎ画素の複数のブロックに分割する際のブロック間の境界となるべき線のことである。電子透かしの挿入後に画像が並進していれば、電子透かしの検出時に、挿入時のグリッドに適合するように正しくグリッドを決定することが困難となる。多くの応用において、ある特定のこのような変換が画像に施されることが考えられるため、これは重要な問題である。例えば、ＤＶＤ（デジタル・ビデオ・ディスク；digital Video Disk）に記録された映像は、“パンスキャン(panscan)”もしくは“レターボックス(letterbox)”モードへ変換し、これによってこの映像を標準テレビ画面に適合するように修正することが考えられる。“パンスキャン”モードでは、水平解像度が高くなり、画面は所定のオフセットで切り取られて、得られる画像は３×４アスペクト（縦横）比のテレビ画面上で見る時に正しくなるようにされる。“レターボックス”モードでは、画像は垂直にスケーリング（この場合は縮小）され、画面の上端部および下端部に黒が加えられて、全体画像が３×４アスペクト比の画面に正しく適合するようにされる。これら２つの幾何学的変換は、他の変換よりも多く使用されるため、特にこれらパンスキャンモードおよびレターボックスモードへの変換に対応できるようにすることが妥当である。
【０１１９】
電子透かし入れされた映像への所定のスケーリングや変換の問題は、本発明により、使用頻度の高い各変換に対応して付加的な電子透かしを挿入することにより解決される。こ
れらの各付加的な電子透かしは、電子透かしの挿入後に画像に対して対応する既知の変換を行う場合に、電子透かしの挿入時に使用したｎ×ｎブロックのグリッドが、検出時に使用される所定のグリッドと一致するように設計されている。したがって、例えばＤＶＤの場合、画像に対して変換が施されない場合には、検出時のグリッドは（何の変換もうけていない）通常の電子透かしのものと一致し、通常の電子透かしが検出される。付加的な電子透かしとして、“パンスキャン”用の電子透かしを挿入しておけば、画像に対して“パンスキャン”変換を行うと、検出時のグリッドが“パンスキャン”用の電子透かしのものと一致し、“パンスキャン”用の電子透かしが検出される。“レターボックス”変換もしくは任意他の所定の変換についても同様に、対応する付加的な電子透かしを挿入することによって対処できるようになる。
【０１２０】
特定の変換を行った後に検出される電子透かしの挿入手順には、下記のステップが含まれる。
【０１２１】
１．    電子透かし入れされる画像ＩのコピーＩTを生成し、補償対象となる変換を画像に適用する。例えば、ＩTは、垂直方向に収縮することにより画像Ｉを“レターボックス”モードへ変換したもののコピーになる。
【０１２２】
２．    上述した一般的な電子透かし入れ方法にしたがって、変換された画像ＩT’の電子透かし入れされたバージョンを生成する。
【０１２３】
３．    電子透かし挿入後の画像ＩT’から挿入前の画像ＩTを減じ、電子透かし挿入によって生じる差分ＷT＝ＩT’−ＩTを空間ドメインで求める。
【０１２４】
４．    差分ＷTに対して画像Ｉから画像ＩTを求めたときの逆変換を実施して、変換前の画像Ｉに対応する差分画像Ｗを得る。例えば、補償すべき変換が“レターボックス”モードへの変換であった場合には、ＷTを垂直に拡張してＷが得られる。
【０１２５】
５．    Ｉ’＝Ｉ＋Ｗを、所与の変換のための電子透かしが付加された画像とする。
【０１２６】
電子透かし入り画像Ｉ’に変換が適用されると、結果はほぼＩT’となる。その結果、電子透かし挿入時に用いたグリッドが通常のグリッドに一致するようになるため、通常の電子透かしを検出するように設計された同じ手順により、電子透かしが検出される。
【０１２７】
このようにして、複数の付加的な電子透かしを挿入すると画像が劣化し、かつ画像内の他の電子透かしの検出可能性（検出度）が低下するため、この手順は考慮する変換の数が少ない場合にしか使用できない。しかしながら、３つの電子透かし、すなわち、変換された画像に対する２つの電子透かしと変換されない画像に対する１つの電子透かしを挿入した場合であっても、画像の忠実度を許容できる範囲内に保ちながら電子透かしの良好な検出度が得られることが、テストにより判明した。別法として、ビデオについては、各電子透かしを時間多重の形態で挿入することができる。
【０１２８】
画像に対して行われる変換が規定されていないもしくは予め定められていないか、あるいは、各変換ごとに独立した電子透かしを挿入するとしてそのような変換が非常に多くあることが考えられる場合には、上述した変換補償方法は最適ではない。したがって、本発明には、電子透かしの挿入時と電子透かしの検出時との間で画像に対して加えられた任意の並進を補償する改良が、加えられている。
【０１２９】
任意の並進は、２つの方法で補償される。一つの方法は、８×８ブロックを使用した場合における、ｘ方向またはｙ方向の８ピクセルのちょうど整数倍だけの距離の並進によるものである。関数ｈ_ｍ(ｉ,ｊ)の指数ｍとブロックの行ｒおよび列ｃとの間の関係に以下の制約を課すことによって、任意の並進を容易に補償することができる。まず、下記式によって、指数ｍを求める。
【０１３０】
ｍ＝ｆ(ｒ,ｃ) ｍｏｄ Ｍ
式中、ｆ(ｒ,ｃ)はｒおよびｃの線形関数であり、ｆ(０,１)およびｆ(１,０)は整数である。さらに、ｈ_ｍ(ｉ,ｊ)を下記式で表される関数とする。
【０１３１】
ｈ_ｍ(ｉ,ｊ)＝(ｈ_０(ｉ,ｊ)＋ａ×ｍ) ｍｏｄ Ｎ
式中、ａは整数である。      
【０１３２】
本明細書のここ以降の部分においては、ここで述べた制約条件を仮定する。この場合、試験対象の電子透かしの全ての巡回シフトと抽出された電子透かしとの相関を計算することによる基本検出アルゴリズムにより、シフト補償を実行する。それは、水平方向および／または垂直方向に８の倍数画素だけ移動した電子透かし入れされた画像から得られたＶＢ_ｍ[ｉ,ｊ]値が、指数ｍを巡回シフトしている点を除き、移動前の画像から得られる値ＶＢ_ｍ[ｉ,ｊ]（ｍ＝０,...,Ｍ−１）と同一であるためである。結果的に、８の複数倍画素だけ移動した電子透かし入れされた画像から得られる抽出値Ｖ[１,...,Ｎ]は、要素Ｖ[ｋ]が巡回シフトされている点を除き、移動前の画像から得られる値Ｖ[１,...,Ｎ]と同一である。ｎ×ｎグリッド形式の場合、水平方向および／または垂直方向でのｎの複数倍の移動に同じことが当てはまる。
【０１３３】
ｘ方向および／またはｙ方向への８画素よりも少ない整数画素精度のシフトに対しては、全部で６４（＝８2）通りの考えられる場合の全数探索を実施して、６４×Ｍ個のＺ値（尤度）の組の中から最大のＺ値を取り出す。Ｍは８×８アキュムレータの数である。本発明者らのテストでは、Ｍとして６４を選択した。ここでＭをかけているのは、各シフトに対する検出では、Ｍ通りの巡回シフトを考慮するためである。これによって、８画素よりも少ないシフト量を求めることができる。
【０１３４】
全数探索では、空間ドメイン内のM個の８×８アキュムレータアレイの値をシフトさせ、次にM個の８×８ブロックの各々のＤＣＴを実施する必要がある。これは考えられる各シフトごとに１回ずつ、計６４回実施される。したがって、６４×Ｍ回の８×８ＤＣＴを実施する必要がある。Ｍの値が大きく、この計算に時間や費用がかかり過ぎる場合には、後述する代わりの方法を使用することができる。
【０１３５】
ｎ画素の非整数倍の並進を補償する第２の方法は、電子透かし挿入と検出とでグリッドを合わせるためのパターンを用いる方法である。このパターンのことをレジストレーション（位置決め）パターンと呼ぶことにする。レジストレーションパターンは、電子透かしの挿入時に挿入することができる。電子透かしの検出時に、レジストレーションパターンが予め規定されたパターンと最も一致する位置を見つけることにより、復号器は、電子透かしを抽出する前にどれだけデータをシフトすべきかを決定することができる。このシフトは空間ドメインで行わなければならないが、後述するように、アキュムレータにより実施することができ、それによって、画像全体のブロック全てに対して変換を行うことが回避される。
【０１３６】
また、この方法では、６４×Ｍ回の８×８ＤＣＴを計算する必要はなく、代わりに、正しい位置決めを空間ドメイン内で行い、アキュムレータアレイ内で画素をシフトすることにより、画像の並進の補償がなされる。Ｍ個の８×８アキュムレータだけがＤＣＴドメインに変換され、上述したようにして電子透かしの抽出が実行される。
【０１３７】
レジストレーションパターンは、８×８画素ブロックの全部の和がそのパターンと強く相関するように画像中に挿入された、８×８空間パターンである。ビデオがｎ×ｎブロックである場合は、ｎ×ｎ空間パターンを用いる。レジストレーションパターンは、上述した電子透かし挿入方法を用いることで挿入することができる。全ての８×８画素ブロックを合計してできる合計ブロックとレジストレーションパターンのＤＣＴ係数同士が相互に大きな相関を有する場合、合計ブロックは、レジストレーションパターンと高い相関性を有するようになる。さらに、合計ブロックのＤＣＴ係数は、ＤＣＴの線形性により、全ＤＣＴブロックの合計に等しい。そのようにして、レジストレーションパターンのＤＣＴ係数を電子透かしＷとみなし、全ての８×８ＤＣＴブロックの合計を値Ｖとみなすことにより、上記の電子透かし挿入方法と類似の方法を用いて、レジストレーションパターンを挿入することができる。
【０１３８】
レジストレーションパターンをＤＣＴドメインへ変換し、次に、ＤＣＴ係数Ｄkおよびフィルタ係数Ｆkが異なる上述の基本的な挿入アルゴリズムを使用することによって、レジストレーションパターンの挿入が実施される。ここでは、レジストレーションパターンのＤＣＴ係数での各ＡＣ（交流）項は、電子透かしの１つの要素Ｗ[ｋ]と考えられる。すなわち、指数（インデックス）ｋは、ＤＣＴ係数の周波数インデックスそのものに相当する。したがって、この要素を抽出するために一緒に合計される１組のＤＣＴ係数Ｄkは、単純に、Ｗ[ｋ]と同じ周波数指数をもつ画像内の８×８ＤＣＴ係数の全てである。そして、全てのＦkが１に設定される。これらのＤkおよびＦkを使用して、挿入アルゴリズムによりレジストレーションパターンが、画像データに挿入される。これと一緒に、元のＤkおよびＦkによる電子透かしも挿入される。
【０１３９】
検出中に、下記のようにレジストレーション処理が実施される。まず、所定数のブロックを合計して、典型的には８×８である、単一のｎ×ｎ画素ブロックを形成する。本発明者らの試験では、適宜に６４個のブロックを使用した。この単一のブロックは、挿入過程によってそこに配置されたレジストレーションパターンを含んでいる。次に、フレームの水平方向及び垂直方向の並進量を決定するために、空間ドメインにおいて８×８画素平均ブロックとレジストレーションパターンとの相関を調べる処理（以後相関プロセスと呼ぶ）を実施し、これらの並進によるオフセットを決定する。可能である８通りの水平並進量及び８通りの垂直並進量の各々について相関プロセスが実施され、計６４回の相関プロセスが実施される。８×８パッチ領域を水平方向または垂直方向にシフトする際、ラップアラウンドシフト、すなわち前と重なり合うようなシフト動作が実施される。
【０１４０】
ここで、グリッドの移動の求め方について説明する。以下の方法では、整数値ｆ(０,１)およびｆ(１,０)がＭに対しては互いに素であると仮定する。
【０１４１】
最初に、ＤＣＴ係数の分類において同じ関数ｈ_ｍ(ｉ,ｊ)が用いられるブロックを、空間ドメイン内で一緒に加算して、各ｍについて１つの合計ブロックＶＢ_ｍ[ｉ,ｊ]を得る。ＡＢ[ｉ,ｊ]によって示される、全てのｎ×ｎ個のブロックについての合計を、下記式によって計算する。
【０１４２】
【数５】
2010136456.tif 000007
【０１４３】
次に、Ｒ[ｉ,ｊ]によって表されるレジストレーションパターンとＡＢ[ｉ,ｊ]との間の相関係数を計算する。この相関係数の計算後、値ＡＢ[ｉ,ｊ]を水平方向に１列だけ巡回シフトさせ、ＡＢ[ｉ,ｊ]とＲ[ｉ,ｊ]との間の相関係数を同様に計算する。各シフトについて同じ演算を繰り返す。ｎ回シフトさせた後、ＡＢ[ｉ,ｊ]は、最初のシフトを行う前のＡＢ[ｉ,ｊ]と同一となる。次に、値ＡＢ[ｉ,ｊ]を垂直方向に１行だけ巡回シフトさせ、相関係数の計算と水平方向への１列だけのシフトを繰り返す。このようにして、全てのｎ2個の可能なシフトについての相関係数を計算することができる。同時に、最大の相関係数を与える、（Ｘ,Ｙ）で表されるシフト値（オフセット）を調べる。
【０１４４】
オフセット（Ｘ,Ｙ）を求めた後、それに応じて、Ｍ個の合計ブロックＶＢ_ｍ[ｉ,ｊ]を空間ドメインでシフトさせる。
【０１４５】
次に、水平方向でのシフト値Ｘを補償する方法を説明する。この補償を行うためには、最初に、値ＶＢ_ｍ[ｉ,ｊ]（ｍ＝０,...,Ｍ−１）を、ｎ×ｎＭの配列ＶＢ１[ｉ,ｊ]（ｉ＝１,...,ｎ，ｊ＝１,...,ｎＭ）にコピーする。値ＶＢ_ｍ[ｉ,ｊ]をコピーする際に、ブロック間の空間的関係、すなわちあるブロックがどのブロックに隣接しているかを考慮する。関数ｆ(ｒ,ｃ)は線形であることから、下記式のようになる。
【０１４６】
ｆ(ｒ,ｃ＋１)＝ｆ(ｒ,ｃ)＋ｆ(０,１)
これは、指数ｍが
ｍ１＝（ｍ０＋ｆ(０,１)） ｍｏｄ Ｍ
に等しいブロックが、ｍ＝ｍ０であるブロックに隣接していることを意味している。そこで、行列ＶＢ１において、値ＶＢ_ｍ１を値ＶＢ_ｍ０の隣りにコピーする。そのため、各Ｉ（Ｉ＝０,...,Ｍ−１）について、ＶＢ_ｍ’[ｉ,ｊ]（ｉ＝１,...,ｎ，ｊ＝１,...,ｎ，ｍ’＝Ｉ×ｆ(０,１) ｍｏｄ Ｍ）を、左上の角の指数を（１,ｎＩ＋１）とする、ＶＢ１内のｎ×ｎの正方形領域にコピーする。全ての値Ｉをコピーした後、ｆ(０,１)とＭが互いに素であることから、配列ＶＢ１は値ＶＢ_ｍ[ｉ,ｊ]で埋まる。次に、配列ＶＢ１中の値を水平方向にＸだけ巡回シフトさせる。
【０１４７】
次に、左上の角の指数が（１,ｎＩ＋１）であるＶＢＩ中のｎ×ｎ領域における値を、各Ｉ（Ｉ＝０,...,Ｍ）について、ＶＢ_ｍ’[ｉ,ｊ]（ｉ＝１,...,ｎ，ｊ＝１,...,ｎ，ｍ’＝Ｉ×ｆ(０,１) ｍｏｄ Ｍ）に代入することで、ＶＢ１における値をＶＢ_ｍに返す。こうして、全体画像自体をシフトさせることなく、水平方向オフセット値Ｘを補償することができる。
【０１４８】
次に、垂直方向における移動値Ｙを補償する。この補償を行うには、まず、値ＶＢ_ｍ[ｉ,ｊ]（ｍ＝０,...,Ｍ−１）をｎＭ×ｎの配列ＶＢ２[ｉ,ｊ]（ｉ＝１,...,ｎＭ，ｊ＝１,...,ｎ）にコピーする。値ＶＢ_ｍ[ｉ,ｊ]をコピーする際に、ブロック間の空間的関係を考慮する。関数ｆ(ｒ,ｃ)が線形であることから、下記式のようになる。
【０１４９】
ｆ(ｒ＋１,ｃ)＝ｆ(ｒ,ｃ)＋ｆ(１,０)
これは、指数ｍが
ｍ１＝（ｍ０＋ｆ(１,０)）ｍｏｄ Ｍ
に等しいブロックが、ｍ＝ｍ０であるブロック下にあることを意味している。そこで、行列ＶＢ２において、値ＶＢ_ｍ１を値ＶＢ_ｍ０下にコピーする。そのため、各Ｉ（Ｉ＝０,...,Ｍ−１）に対して、ＶＢ_ｍ’[ｉ，ｊ]（ｉ＝１,...,ｎ，ｊ＝１,...,ｎ，ｍ’＝Ｉ×ｆ(０,１) ｍｏｄ Ｍ）を、左上の角の指数を（ｎＩ＋１,１）とする、ＶＢＩ内のｎ×ｎの正方形領域にコピーする。全ての値Ｉをコピーした後、ｆ(１,０)とＭが互いに素であることから、配列ＶＢ２は値ＶＢ_ｍ[ｉ,ｊ]で埋まる。次に、配列ＶＢ２中の値を垂直方向にＹだけ巡回シフトさせる。
【０１５０】
次に、ＶＢ２中の左上の角の指数が（ｎＩ＋１,１）であるｎ×ｎ領域における値を、各Ｉ（Ｉ＝０,...,Ｍ）について、ＶＢ_ｍ’[ｉ,ｊ]（ｉ＝１,...,ｎ，ｊ＝１,...,ｎ，ｍ’＝Ｉ×ｆ(０,１) ｍｏｄ Ｍ）に代入することで、ＶＢ２における値をＶＢ_ｍに返す。こうして、全体画像自体をシフトさせることなく、垂直方向オフセット値Ｙを補償することができる。
【０１５１】
ｎ×ｎグリッドのオフセットは、上記の処理によって補償される。これらの処理は、後述のように、図１０のレジストレーション処理１０８で行われる。ｎの倍数の移動はこれらの処理を行った後にも残っているが、上述したように電子透かしを巡回的にシフトさせることによって電子透かしＷと抽出値Ｖとの間の相関係数が計算されるので、そのシフトは電子透かしの検出には影響を及ぼさない。以上のレジストレーション処理を適用した後、Ｍ個のブロックＶＢ_ｍ（ｍ＝０,...,Ｍ−１）をＤＣＴドメインに変換し戻す。
【０１５２】
図１０および図１１は、それぞれ、ＭＰＥＧ映像入力の場合と非圧縮映像（伸長された映像）の場合における、並進レジストレーションを補償するように修正された基本的な検出アルゴリズムを示している。
【０１５３】
ＭＰＥＧ映像入力の場合（図１０）、最初に、ＭＰＥＧビデオストリームから得られる８×８ＤＣＴブロックを、関数ｈ_ｍ(ｉ,ｊ)の指数ｍに従ってＭ個のグループに分類し、Ｍ個の合計ブロックを生成するためにグループ内で加算し、その後、得られた合計ブロックを８×８アキュムレータ１０２で蓄積する。次に、８×８アキュムレータ１０２内のＭ個の合計ブロックは、逆ＤＣＴ変換器１０４で逆ＤＣＴ演算を行うことで空間ドメインに変換され、８×８アキュムレータ１０６に蓄積される。８×８グリッドのオフセット値の検索とそのオフセットの補償を、上記の方法に従って、レジストレーション処理１０８において、８×８アキュムレータ１０６からの出力について実行する。レジストレーション処理１０８から出力されたレジストレーションデータは、８×８アキュムレータ１１０に蓄積され、ＤＣＴ変換器１１２によってＤＣＴドメインに変換される。ＤＣＴ変換器１１２の出力に対し、８×８アキュムレータ１１４、電子透かし抽出器１１６および電子透かし復号器１１８を使用して、電子透かし抽出が行われる。
【０１５４】
電子透かし抽出器１１６では、８×８アキュムレータ１１４から出力されたＤＣＴ係数が、関数ｈ_ｍ(ｉ,ｊ)に従ってＮ個の集合に分類され、加算され、これによって電子透かし抽出が行われる。得られた電子透かしは電子透かし復号器１１８に出力される。電子透かし復号器１１８は、抽出された電子透かしに対応する電子透かしを検索するために、図８に示す比較器８４での処理を実行する。挿入されたと考えられる電子透かしが、電子透かし復号器１１８から出力される。
【０１５５】
非圧縮データの場合は（図１１）、入力データが、８×８のブロックに分割され、関数ｈ_ｍ(ｉ,ｊ)の指数に従って８×８アキュムレータ１０６に蓄積される。その後、レジストレーション処理１０８を行ってから、ＤＣＴ変換器１１２でＤＣＴドメインに変換され、その後は、ＭＰＥＧ映像の場合と同様に処理が行われる。
【符号の説明】
【０１５６】
３０，７２    減算器
３２    フレームメモリ
３４，５０，５６，７０，    ＤＣＴ計算器
３６    量子化器
３８    可変長符号化器
４０，５８    逆量子化器
４２，５４    逆ＤＣＴ計算器
４４，５２，６０，６４    加算器
６２    電子透かし修正部
８０    ハフマン復号器・パーシャルパーサ
８２，９４    電子透かしアキュムレータ（蓄積器）
８４，９６    比較器
９０，１０２，１０６，１１０，１１４    ８×８アキュムレータ
９２，１１２    ＤＣＴ変換器
１０４    逆ＤＣＴ変換器
１０８    レジストレーション処理
１１６    電子透かし抽出器
１１８    電子透かし復号器
【図１】
2010136456.tif 000008
【図２】
2010136456.tif 000009
【図３】
2010136456.tif 000010
【図４】
2010136456.tif 000011
【図５】
2010136456.tif 000012
【図６】
2010136456.tif 000013
【図７】
2010136456.tif 000014
【図８】
2010136456.tif 000015
【図９】
2010136456.tif 000016
【図１０】
2010136456.tif 000017
【図１１】
2010136456.tif 000018