(57)【要約】【課題】透かしデータを埋め込んだ符号化画像を復号した場合でも透かしデータが確実に残るようにする。【解決手段】ブロックのＤＣＴ係数を量子化した後の、ランレングスの構造をブロックの数だけ並べてグループ化したものをハッシュ関数によって、Ｎビットのハッシュ値に変換する。ただし、各ブロックのランレングスの最後にダミーのランを一つ追加する。次にそのＮビットのハッシュ値と透かしデータとの排他的論理和をとって透かしデータを埋め込み、これを秘密鍵で暗号化してＮビットの署名データを得る。以上のようにして透かしデータを埋め込んだＮビットの署名データを各ブロックに１ビットずつ、そのビットが０のときはそのブロックのダミーのランの後の値を‐１とし、ビットが１のときはそのブロックのダミーのランの後の値を＋１とする。【選択図】        図１
2004242162.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ（Ｎは自然数）個のブロック毎の変換係数を量子化した量子化インデックスに対し、透かしデータを埋め込む電子透かし埋め込み方法において、
上記各ブロック毎に量子化インデックスをランレングス化し、そのランレングスデータを上記ブロック分並べたデータをＮビットのハッシュ値に変換し、上記Ｎビットのハッシュ値に透かしデータを埋め込んでＮビットの署名データを生成し、
上記Ｎビットの署名データの各ビットを上記Ｎ個のブロックそれぞれに１つずつ対応させて、その署名データの各ビットの値が０か１かに応じて異なる値の署名ビットを量子化インデックスの所定位置に入れる、電子透かし埋め込み方法。
【請求項２】
請求項１記載の電子透かし埋め込み方法において、さらに、
上記各ブロック毎に量子化インデックスをランレングス化した際、そのランレングスデータの最後にダミーのランを追加し、
上記Ｎビットの署名データの各ビットの値が０か１かに応じて異なる値の署名ビットを量子化インデックスの所定位置に入れる際は、上記ダミーのランの後に入れる、電子透かし埋め込み方法。
【請求項３】
請求項１または請求項２のいずれかの請求項に記載の電子透かし埋め込み方法において、
上記Ｎビットの署名データの各ビットを上記Ｎ個のブロックそれぞれに１つずつ対応させて、その署名データの各ビットの値が０か１かに応じて異なる値の署名ビットとは、＋１と−１とである、電子透かし埋め込み方法。
【請求項４】
請求項１〜３のいずれかの請求項に記載の電子透かし埋め込み方法により上記透かしデータを埋め込だ画像データに対し、量子化を含む符号化処理を施す際、その量子化ステップ幅を、上記ブロック数であるＮの平方根以上とする画像符号化方法。
【請求項５】
Ｎ（Ｎは自然数）個のブロック毎の変換係数を量子化した量子化インデックスに対し、透かしデータを埋め込む電子透かし埋め込み方法において、
上記量子化インデックスを生成する際、複数の量子化テーブルを用いて量子化をして量子化精度の異なる複数の量子化インデックスを生成し、
量子化精度の粗い量子化インデックスに対しては、上記各ブロック毎に当該量子化精度の粗い量子化インデックスをランレングス化し、そのランレングスデータを上記ブロック分並べたデータをＮビットのハッシュ値に変換し、上記Ｎビットのハッシュ値に透かしデータを埋め込んでＮビットの署名データを生成し、
量子化精度の細かい量子化インデックスに対しては、上記各ブロック毎に当該量子化精度の細かい量子化インデックスをランレングス化し、上記Ｎビットの署名データの各ビットを上記Ｎ個のブロックの当該量子化精度の細かい量子化インデックスのランレングスデータそれぞれに１つずつ対応させて、その署名データの各ビットの値が０か１かに応じて異なる値の署名ビットを上記量子化精度の細かい量子化インデックスの所定位置に入れる、電子透かし埋め込み方法。
【請求項６】
請求項１〜５のいずれかの請求項に記載の電子透かし埋め込み方法をコンピュータに実行させるようにした電子透かし埋め込みプログラム。
【請求項７】
ブロック毎の変換係数を量子化した量子化インデックスに対し、透かしデータを埋め込む電子透かし埋め込み装置において、
上記各ブロック毎に量子化インデックスをランレングス化し、上記各ブロック分のランレングスデータを並べたデータをハッシュ値に変換し、上記ハッシュ値に透かしデータを埋め込んで複数ビットからなる署名データを生成し、
上記署名データを構成する複数ビットそれぞれを上記各ブロックに対応させ、上記各ブロック毎に、対応した上記署名データのビットに応じ異なる値の署名ビットを量子化インデックスの所定位置に入れる、電子透かし埋め込み装置。
【請求項８】
請求項１〜５のいずれかの請求項に記載の電子透かし埋め込み方法により上記透かしデータを埋め込だ画像データを符号化処理する画像符号化方法。
【請求項９】
請求項８に記載の画像符号化方法によりＪＰＥＧ符号化画像に対し透かしデータを埋め込むようにした電子透かし埋め込み部を有する画像符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像の真正性を証明できる電子透かし埋め込み方法、電子透かし埋め込みプログラム、電子透かし埋め込み装置、画像符号化装置に関する。
【０００２】
【従来の技術】
従来、ＪＰＥＧ等により圧縮符号化した画像の真正性を証明する方法として、Ｗｏｎｇらの方法がある。これは、画像の上位７ビットのハッシュ値を透かし情報と鍵で暗号化して、ＬＳＢに埋め込むものである（例えば、非特許文献１参照。）。
【０００３】
【非特許文献１】
“Ｓｅｃｒｅｔ  ａｎｄ  Ｐｕｂｉｃ  Ｋｅｙ  Ｉｍａｇｅ  Ｗａｔｅｒｍａｒｋｉｎｇ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｉｍａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  Ｏｗｎｅｒｓｈｉｐ  Ｖｅｒｉｆｉｃａｔｉｏｎ”  ｂｙ  Ｐｉｎｇ  Ｗａｈ  Ｗｏｎｇ  ａｍｄ  Ｎａｉｓｅｒ  Ｍｅｍｏｎ  （ＩＥＥＥ  ＴＲＡＮＳＡＣＴＩＯＮＳ  ＯＮ  ＩＭＡＧＥ  ＰＲＯＣＥＳＳＳＩＮＧ，ＶＯＬ．１０，ＮＯ．１０，ＯＣＴＯＢＥＲ  ２００１）
【０００４】
【発明が解決しようとする課題】
しかし、この  Ｗｏｎｇらの方法では、画像が１ビットでも変更されれば、ほぼ確実にそれを検知することができるが、透かしデータをＬＳＢに埋め込んでいるため、ＪＰＥＧ等により圧縮すると、ＬＳＢに埋め込んだ透かしデータが切り捨てられてしまう、とい課題があった。
【０００５】
そこで、本発明は、透かしデータを埋め込んだ圧縮符号化画像を復号した場合でも透かしデータが確実に残り、画像の真正性を証明できるようにした電子透かし埋め込み方法、電子透かし埋め込みプログラム、電子透かし埋め込み装置、画像符号化装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
上記目的を達成するため、本発明では、画像データを量子化した量子化インデックスのランレングス構造を署名データとして画像データに埋めこむようにしたもので、具体的には、ブロック毎の変換係数を量子化した量子化インデックスに対し、透かしデータを埋め込む際、上記各ブロック毎に量子化インデックスをランレングス化し、上記各ブロック分のランレングスデータを並べたデータをハッシュ値に変換し、上記ハッシュ値に透かしデータを埋め込んで複数ビットからなる署名データを生成し、上記署名データを構成する複数ビットそれぞれを上記各ブロックに対応させ、上記各ブロック毎に、対応した上記署名データのビットに応じ異なる値の署名ビットを量子化インデックスの所定位置に入れるようにしたものである。
【０００７】
【発明の実施の形態】
実施の形態１．
図１は、本発明に係る電子透かし埋め込み方法が実行される実施の形態１の画像符号化装置の構成を示す図である。図において、この画像符号化装置は、入力画像に対しＪＰＥＧ圧縮符号化を行うＪＰＥＧ符号化部１と、ＪＰＥＧ圧縮符号化信号に対し本発明に係る電子透かし埋め込み方法により透かしデータを埋め込む電子透かし埋め込み部２とから構成されている。なお、ＪＰＥＧ符号化部１は、通常のＪＰＥＧ圧縮符号化を行うので、電子透かし埋め込み部２が行う、本発明に係る電子透かし埋め込み方法について以下に説明する。
【０００８】
まずは、本発明に係る電子透かし埋め込み方法の実施の形態１の概要を説明する。本発明の概要は、以下の通りで、まず、Ｎ個のＤＣＴブロックを１まとめとして、量子化されたＤＣＴ係数のランレングスの構造を符号化する。この符号化されたコードのハッシュ値（Ｎビット）を透かし情報と鍵で暗号化し、その結果を各ＤＣＴブロックのスキャンの最後に追加する。このとき、最後のＤＣＴ係数の値は、ビットが０ならば−１、１ならば１とする。追加する係数のラン長はあらかじめハッシュ値の計算に含めなければならない。この方法では、ＤＣＴ係数のランレングスの構造がＤＣＴブロックの最後に埋め込まれている。したがって、この構造が１ビットでも変更されれば、それを検知することができる。また、最後のＤＣＴ係数は＋１か−１かの値しか取らないから、それを他の値に変更すれば、確実に変更を検知できる。また、画像が復号された後でも、同じ量子化器を用いて、ランレングスの構造を調べれば、真正性の検査が可能である。計算機シミュレーションにより画像の劣化を評価したところ、ＰＳＮＲで３５．８ｄＢのＪＰＥＧ画像に対して透かしを埋め込むと、ＰＳＮＲは３３．７ｄＢとなった。
【０００９】
つまり、本実施の形態１では、まず、Ｎ個のＤＣＴブロックを１まとめとして、量子化されたＤＣＴ係数のランレングスの構造を符号化する。この符号化されたコードのハッシュ値（Ｎビット）を透かし情報と鍵で暗号化し、その結果を各ＤＣＴブロックのスキャンの最後に追加する。このとき、最後のＤＣＴ係数の値は、ビットが０ならば−１、１ならば１とする。追加する係数のラン長はあらかじめハッシュ値の計算に含めなければならない。この方法では、ＤＣＴ係数のランレングスの構造がＤＣＴブロックの最後に埋め込まれている。したがって、この構造が１ビットでも変更されれば、それを検知することができる。また、最後のＤＣＴ係数は＋１か−１かの値しか取らないから、それを他の値に変更すれば、確実に変更を検知できる。また、画像が復号された後でも、符号化側と同じ量子化器を用いて、ランレングスの構造を調べれば、真正性の検査が可能である。計算機シミュレーションにより画像の劣化を評価したところ、ＰＳＮＲで３５．８ｄＢのＪＰＥＧ画像に対して透かしを埋め込むと、ＰＳＮＲは３３．７ｄＢとなった。
【００１０】
なお、認証用の電子透かしにおいては、画像が変更されていない、すなわち画像が同一であるということを証明することが一つの目的である。このため、本発明において、何をもって符号化前および復号後の２つの画像を同一とみなすかを定義しておくと、本発明では、符号化前および復号後の２つの画像は生データの段階で全く同一であることは問題にせず、量子化された段階で同じであればよいと考える。つまり、本発明では、２つの画像のＤＣＴ係数を同じ量子化パラメータで符号化した場合に、量子化インデックスが全く同じになるとき、これらの画像は同一であるものとし、、量子化されたインデックスが１つでも異なれば、２つの画像は異なるとする。以下、この定義にもとづいて画像が変化、すなわち量子化インデックスが１つでも異なるとみなされたとき、それを確実に検出する電子透かしのアルゴリズムを提案する。
【００１１】
図１は、本発明に係る電子透かし埋め込み方法が実行される画像符号化装置の構成の一例を示す図である。図１において、この画像符号化装置は、ＤＣＴ部１、量子化部２、ジグザグスキャン部３、ランレングス化部４、ダミーラン付加部５、ハッシュ関数部６、排他的論理和（ＥＸＯＲ）部７、暗号化部８、透かし埋め込み部９、可変長符号化部１０、ストリーム符号化部１１を有しており、入力するホスト画像をＪＰＥＧ圧縮符号化する際、署名画像等の透かしデータを公開鍵暗号方式により暗号化して電子透かしとして埋め込み符号化ストリームとしてＮ（Ｎは自然数）個のブロック毎に変換され出力するように構成されている。なお、ＤＣＴ部１や、量子化部２、ジグザグスキャン部３、ランレングス化部４、可変長符号化部１０、ストリーム符号化部１１等は、通常のＪＰＥＧ圧縮符号化を行うので、主に、本発明に係る電子透かし埋め込み方法を中心に以下に説明する。
【００１２】
＜２．電子透かし埋め込み方法のアルゴリズム＞
実施の形態１では、８×８のＤＣＴブロックをＮ個まとめてマクロブロックを形成し、このマクロブロックの中に、ビットマップ形式の署名画像等の透かしデータを埋め込んだＮビットの署名データを埋め込む。
【００１３】
＜２．１  署名データの生成＞
透かしデータを埋め込んだ署名データは、以下のようにして作成される。
【００１４】
まず、ＤＣＴ部１が１つの画像を複数のマクロブロックに分割し、その各マクロブロックを８×８のＤＣＴ符号化単位であるＮ個の各ブロックに分割し、量子化部２がＮ個の各ブロック毎に各ブロックのＤＣＴ係数を量子化し、ジグザグスキャン部３がその量子化インデックスをジグザグにスキャンする。ランレングス部４は、ジグザグスキャンにより得られた量子化インデックスをランレングスにより表現する。ここまでは、従来と変わりない。
【００１５】
そして、本実施の形態１では、ハッシュ関数部６がそのランレングスデータをブロックの数、すなわちＮ個並べて、ブロックの数だけ並べたランレングスデータをハッシュ関数によってＮビットのハッシュ値に変換する。ただし、その前あるいはその際に、ダミーラン付加部５が各ブロックのランレングスの最後にダミーのランを一つ追加する。このダミーのランは、後に署名データをＪＰＥＧ  のビットストリームの中に埋め込むために用いるものである。なお、このダミーのランは、後述するように０でも、０以外でも良いので、必ず必要である、というものではない。また、後述するように、ここでは、ブロックの数であるＮ個だけ並べたランレングスデータをハッシュ関数によってＮビットのハッシュ値に変換しているが、これは後述するように、Ｎビットのハッシュ値の各ビットを１ビットずつＮ個の各ブロックのランレングスデータに対応させることが一番効率がよいためであって、本発明では、ブロックのランレングスの構造、すなわちＤＣＴ係数の量子化構造を署名データであるハッシュ値に反映し、その署名データをＮ個の各ブロックのランレングスデータそれぞれに対応さえできれば良いので、ブロックの数であるＮ個だけ並べたランレングスデータをＮビット以外、例えばＮの整数倍や、Ｎより小さいビット数のハッシュ値に変換して、Ｎ個の各ブロックそれぞれに複数ビットのハッシュ値を対応させたり、複数のブロックに同一のハッシュ値を対応させるようにしても勿論よい。
【００１６】
次に、排他的論理和部７が、そのＮビットのハッシュ値と、ビットマップ形式の署名画像等の透かしデータとの間で排他的論理和をとってＮビットのハッシュ値に透かしデータを埋め込み、暗号化部８がこれを秘密鍵で暗号化してＮビットの署名データを得る。なお、ここでは、透かしデータとの間で排他的論理和をとって透かしデータを埋め込んだＮビットのハッシュ値を秘密鍵で暗号化しているが、本発明では、これに限らず、共通鍵暗号方式のように送受同一の共通鍵で暗号したり、さらには、暗号化する必要がなければ、暗号処理自体を省略しても勿論かまわない。
【００１７】
次に、以上のＮビットの署名データを得るまでの処理を具体的に説明する。
あるブロックに対して、ＤＣＴ係数を量子化すると、例えば、図２の量子化インデックスが得られたとする。これから以下の（ラン、大きさ）の組が得られる。
【００１８】
（１５）、（１、−２）、（０、−１）、（０、−１）、（０、−１）、（２、−１）
【００１９】
ただし、最初の１５は、ＤＣ係数のインデックス、以下は（）内の前の値が０ランの数、後の値がＡＣ係数のインデックスである。ここで、ダミーのランとして、例えば３を付加し、
【００２０】
（１５）、（１、−２）、（０、−１）、（０、−１）、（０、−１）、（２、−１）、（３）
【００２１】
を得る。このデータを各ブロック分であるＮ個順番に並べたものをハッシュ関数の入力として、ハッシュ関数により、Ｎビットのハッシュ値を得る。
【００２２】
＜２．２  署名データの埋め込み＞
以上のようにして透かしデータを埋め込んだＮビットの署名データを、各ブロックに１ビットずつ、例えば、次のようにして埋め込む。
【００２３】
つまり、署名データのビットが０のときは、そのブロックのダミーのランの後の値を‐１とする。ビットが１のときは、そのブロックのダミーのランの後の値を＋１とする。
【００２４】
例えば、図２に示す例の場合、埋め込むビットが０ならば、量子化インデックスのランレングスの構造は、
【００２５】
（１５）、（１、−２）、（０、−１）、（０、−１）、（０、−１）、（２、−１）、（３、−１）
【００２６】
となる。あとは通常の符号化の場合と同様に、これにヘッダなどを付加するストリーム符号化を施すようにする。
【００２７】
＜２．３  認証能力の証明＞
以上のアルゴリズムで電子透かし埋め込まれた画像については、量子化後のインデックスが１つでも変わるとそれが確実に検出できることは、以下のようにして証明できる。
【００２８】
つまり、もし、量子化インデックスのランレングスの構造の中で、署名ビット、すなわちランレングスの最後にいれた＋１か‐１の値以外の部分が変化すると、ハッシュ値が変わるから、埋め込んだ透かしデータを検出できない。
【００２９】
その一方、署名ビットが変化すると、画像から検出されたハッシュ値と署名ビットが合わないから、埋め込んだ透かしデータが検出できない。以上から、埋め込んだデータが検出できるのは、署名ビットもそれ以外のインデックスも変化していない場合に限られる。
【００３０】
ここで、本実施の形態１の場合、署名ビットが＋１か、‐１の２種類しかないことは重要である。例えば、ロバストな電子透かしでよく用いられる、偶数または奇数に量子化して情報を埋め込む方法を用いると、偶数または奇数の値は１通りに決まらないから、ランレングス構造の異なる画像が同一であるとみなされる場合が生じるからである。なお、本発明の場合、署名ビットは、±１である必要は無く、予め決まって１通りに決まるのであれば、±１以外でも、３種類以上あっても勿論よい。
【００３１】
＜２．４  符号量の増加＞
このアルゴリズムでは、署名の埋め込みのために、各ブロックに（ラン、大きさ）の組を追加するから、ＪＰＥＧ後の符号量が増加する。ここで、署名ビットの大きさの値は±１しかないから、ランだけで符号量の増加量は決まる。
【００３２】
図３は、ｎが７まであるＪＰＥＧで（ｎ、±１）を符号化するためのハフマン符号の符号長である。この図３から、例えば、全てのブロックでダミーのランを３とすれば、１画素当りの符号量の増加は、
【００３３】
【数１】
2004242162.tif 000003
【００３４】
である。
【００３５】
＜２．５ 歪みの増加＞
署名の埋め込みのために用いる各ブロック最後の署名ビット±１のために、ＪＰＥＧ画像の歪みが増加する。この増加量は量子化の粗さに依存し、それが粗いほど増加量は大きい。例えば、図４の量子化テーブルを用いて、透かしの埋め込みが、ブロックの（３、３）の位置に対して行われたとすると、画素当りの歪みの増加量は、電力にして、およそ
【００３６】
【数２】
2004242162.tif 000004
【００３７】
である。この場合、ＰＳＮＲ＝４２ｄＢのＪＰＥＧ画像に透かしをいれたとき、そのＰＳＮＲは３ｄＢ減少することになる。
【００３８】
従って、ダミーのランの長さは、符号量と歪みの増加の観点から、適切に設定すべきである。
【００３９】
＜２．６  ＪＰＥＧ復号の問題について＞
次に、以上のようにして電子透かし埋め込み方法により符号化ストリームを復号する際の問題について説明する。
【００４０】
図５は、本発明に係る電子透かし埋め込み方法により符号化ストリームを復号する画像復号装置における透かしデータ検出回路の一例を示す図である。図５において、この画像復号装置は、ストリーム復号部２１、可変長復号部２２、透かし分離部２３、暗号復号部２４、逆ハッシュ関数部２５、排他的論理和部２６を有しており、図１に示す画像符号化装置により符号化された符号化ストリームを入力して、ストリーム復号、可変長復号、透かし分離、公開鍵を用いた暗号復号、逆ハッシュ関数、排他的論理和をとることにより、透かしデータを検出するように構成されている。なお、画像復号装置自体は、図１に示す画像符号化装置とは逆に処理するように構成されるので、ここでは説明しない。
【００４１】
ＪＰＥＧ符号化画像を復号した後、再度同じ量子化パラメータで符号化すると、ランレングスの構造が変化する場合がある。この場合、復号された画像は、既にその段階で真正性が崩れていることになる。これを防ぐため、ＪＰＥＧの復号は、再符号化したときに、量子化構造が同じとなるように行わなければならない。これによって、真正性はＪＰＥＧの復号後も保たれる。このような復号方法は可能であると思うが、本報告では、詳細な検討はしない。なお、復号後も透かしが残るという条件は重要である。なぜなら、単にＪＰＥＧのストリームの段階でその真正性を証明したいだけなら、透かしデータを用いなくても、例えばＭＡＣ（Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ）を付加するなどして、それを実現することができるからである。
【００４２】
＜３．評価＞
ある人物画像をＪＰＥＧ符号化し、その画像に署名を埋め込んで画質の劣化を評価した。ただし、署名の詳細はインプリメントしていない。署名データとしてランダムなビット系列を用いた。図４の量子化テーブルを用いてＪＰＥＧで符号化した人物画像に署名が埋め込まれていない場合に、この画像のＰＳＮＲが３５．８ｄＢであるとし、この画像にダミーのランを０とした署名を埋め込むとする。ただし、上述したように。署名ビットは、ジグザグスキャンの最後の非零係数の直後に埋めむ。すると、この署名ビット埋め込み後の画像のＰＳＮＲは、原画に対して、３３．７ｄＢである。透かしを埋め込んだ個所は、背景などの平坦な部分で、歪みがやや目立つが、この歪みは量子化を細かくすることで軽減される。
【００４３】
以上説明したように、本実施の形態１では、マクロブロックをＮ個に分割したブロック毎にＤＣＴ係数を量子化した後のランレングスの構造をブロックの数だけ並べたものをハッシュ関数によって、Ｎビットのハッシュ値に変換する際、各ブロックのランレングスの最後にダミーのランを一つ追加して、Ｎビットのハッシュ値に透かしデータを埋め込み、これを秘密鍵で暗号化してＮビットの署名データを得て、このＮビットの署名データを透かしデータとして各ブロックに１ビットずつビットが０のときは、そのブロックのダミーのランの後の値を‐１とする一方、ビットが１のときは、そのブロックのダミーのランの後の値を＋１として埋め込むようにしたので、画像のＤＣＴ係数や署名ビットの量子化値が少しでも変更されても、それをほぼ確実にその変更を検知することができる。
【００４４】
実施の形態２
上記実施の形態１では、ＪＰＥＧ画像の真正性を保証する電子透かしの方法を提案した。この方法を用いれば、ＪＰＥＧ画像が、発行者の署名後に改ざんされていないことを画像データだけから知ることができる。この方法は、ＤＣＴ係数の量子化の構造が変化しない限り透かしデータが残るが、ＤＣＴ係数の量子化の構造がわずかでも変化すると電子透かしは破壊されるということである。そのため、ＪＰＥＧ復号後の画像で透かしデータが残るためには、ＪＰＥＧ復号後の画像を再符号化したときに、もとの量子化の構造が完全に保持される必要がある。ところが、一般のＪＰＥＧ復号では、逆ＤＣＴされた画像データを通常８ビットの整数値に四捨五入してしまうので、復号画像を再度ＪＰＥＧ符号化するとその量子化の構造が変化する場合がある。そこで、本実施の形態２では、量子化のステップ幅をｓｑｒｔ（Ｎ）以上とすることによって、再符号化後の量子化の構造が保存されることを証明する。ここで、Ｎは、ＤＣＴのブロックサイズであり、８×８ＤＣＴの場合は６４である。したがって、ＤＣＴ係数の量子化を８より大きなステップ幅で行えば、ＪＰＥＧ復号した画像から電子透かしは消えることはない。実際にいくつかの標準画像について再符号化を試した結果では、ステップ幅を４以上とすれば、再符号化によって量子化の構造が変化することはなかった。
【００４５】
つまり、真正性を証明する電子透かしは、画像データが（１）由緒正しいものであり、（２）改ざんが行われていないという２つのことを証明するためのものである。Ｗｏｎｇ  らの方法によれば、（１）は画像の発行者が自分の秘密鍵で透かしデータを暗号化することで実現され、（２）は画像データのハッシュ値を（１）の暗号データとＸＯＲして画像に埋めこむことで実現されるとしているが、  Ｗｏｎｇは透かしデータを画像データのＬＳＢ  に入れたので、ＪＰＥＧ  などの圧縮画像に用いることができなかった。上記実施の形態１では、  Ｗｏｎｇ  のアルゴリズムをＪＰＥＧで符号化された画像に対して拡張した［。これによれば、ＪＰＥＧ  の量子化の構造がハッシュ関数に与えられ、それと暗号データのＸＯＲがＤＣＴブロックの最後に埋めこまれる。しかし、ＪＰＥＧで復号した画像を同じ量子化器を用いて再符号化しても、その量子化の構造が再現される保証がない。そのため、一旦ＪＰＥＧで復号すると、透かしデータが消えてしまう場合があるという問題があった。本実施の形態２では、量子化のステップサイズを８以上とすることで、ＪＰＥＧ復号による透かしの消滅がなくなるようにしたものである。また、実際の画像を用いてそのことを確認する。
【００４６】
＜１．ＪＰＥＧ復号がロスレスでない理由＞
ＪＰＥＧ符号化では、量子化されたＤＣＴ係数を逆量子化した後で、画素値を整数に打ち切っているので、一般に、復号後の画像をもう一度符号化すると同じビットストリームが得られる保証がない。このことを図６を用いて説明する。
【００４７】
図６は、２元アダマール変換の時間領域（ｘ−ｙ  座標）と、変換領域（ｕ−ｖ  座標）のサンプル点の構造を示している。アダマール変換は次式の数３で与えられる。
【００４８】
【数３】
2004242162.tif 000005
【００４９】
ここで、ｘ、ｙ  は時間領域の座標であり、画像データは整数であるからそのサンプル点は図の●で表される。上記数３の式から、２元アダマール変換は４５°の回転移動に等しいから、●は、変換領域では図のｕ−ｖ  座標で読み取った座標に変換される。今、ｕ、ｖをそれぞれ一様なステップ幅でスカラー量子化することを考える。ただし、ｕ  はｖ  より細かく量子化されているとすると、例えば、図の点線で示すような量子化の境界が得られる。この境界で囲まれたクラス毎に、量子化の代表値が○の位置で与えられる。さて、ハッチをかけたクラスｉ  に注目すると、このクラスには２つのベクトルｘｉ１、ｘｉ２  が存在し、変換後どちらもｘｉ  に量子化される。このｘｉ  が逆変換されて、整数値に戻されるとき、それに最も近い整数はクラスｉ  のベクトルでなく、クラスｊ  のベクトルｘｊ２  である。そのため、ｘｊ２  が再符号化されると、量子化後のベクトルはｘｊ  となって、ｘｉ  と一致しない。
【００５０】
このように、量子化代表値に最も近い整数ベクトルが必ずしも自分のクラスに属していないことが変換符号化がロスレスでないことの理由である。これは、アダマール変換に限らず、ＤＣＴ  でも起こり得るし、次数に関係無いことも明らかである。
【００５１】
図６の考察から、量子化幅を大きくすれば、代表値の周辺にはそのクラスの属する多くの整数ベクトルが存在し、再符号化でロスが生じにくくなるだろうと予想される。そこで、本実施の形態２では、次に説明するように、量子化幅をＮ（Ｎ  は変換の次数）より大きくすることにより、符号化は完全にロスレスとしたものである。
【００５２】
＜２．復号をロスレスとするための量子化の制限＞
符号化において、変換係数の量子化は、一様なスカラー量子化とする。復号において、逆変換されたベクトルは、ユークリッド距離が最も近い整数ベクトルに打ち切られるとする。また、変換、逆変換の演算誤差を無視すると、変換前後で距離が保たれなければならないが、直交変換の全ての変換係数に対して、Ｑｉ  ＞  √Ｎ  が満たされれば、逆変換されたベクトルに最も近い整数ベクトルは、もとの変換係数と同じクラスに属することになる。ただし、Ｑｉ  はｉ番目の変換係数の量子化ステップ幅、Ｎは変換の次数である。
【００５３】
これを証明しておく。逆変換されたベクトルを、
【００５４】
【数４】
2004242162.tif 000006
【００５５】
とする。ここで、一般性を失うことなく、
【００５６】
【数５】
2004242162.tif 000007
【００５７】
としてよい。ベクトルｃ  の周りの整数ベクトルを
【００５８】
【数６】
2004242162.tif 000008
【００５９】
とおけば、
【００６０】
【数７】
2004242162.tif 000009
【００６１】
を満たすｘ  は、２Ｎ個存在する。その中で、ｃ  に最も近いベクトルを
【００６２】
【数８】
2004242162.tif 000010
【００６３】
とすると、
【００６４】
【数９】
2004242162.tif 000011
【００６５】
であるから、次式の数１０が成り立つ。
【００６６】
【数１０】
2004242162.tif 000012
【００６７】
上記数１０の式と、条件Ｑ  ＞  √Ｎ  より、
【００６８】
【数１１】
2004242162.tif 000013
【００６９】
が成り立つ。ただし、Ｑ  は、量子化ステップ幅Ｑｉ  の最小値とする。一方、
【００７０】
【数１２】
2004242162.tif 000014
【００７１】
を満たすベクトルｘ  は必ずｃ  に量子化される。なぜなら、上記数１２の式が成り立てば、全てのｉ  について、
【００７２】
【数１３】
2004242162.tif 000015
【００７３】
が成り立つからである。以上より、ベクトルＸｃは、再符号化されると必ずクラスｃ  に属することが示された。
【００７４】
＜４．評価＞
５つのテスト画像を用いて、全てのＤＣＴ係数を同じステップ幅Ｑ  で量子化し、それを復号した後、再度符号化して、異なるクラスにマッピングされるブロックの数を調べた。
【００７５】
図７にその結果を示す。
画像のサイズは全て５１２×５１２であり、ブロックの数は４０９６である。表から、Ｑ＝８  とすれば全ての場合において、再符号化後同じクラスにマッピングされていることがわかる。なお、この例では、Ｑ＝４  とすればロスレスが成り立っていることがわかる。
【００７６】
以上説明したように、本実施の形態２によれば、上記実施の形態１の対しさらに量子化のステップ幅に制限を加えることにより、ＪＰＥＧ  圧縮がロスレスとなるようにした。これを用いれば、認証用の透かしデータがＪＰＥＧ復号後も消えないことを保証することができる。
【００７７】
なお、Ｑ＝８  の制約は、画質を重視する場合には強すぎるかも知れない。その場合には、ＪＰＥＧ  圧縮と、電子透かしで異なる量子化テーブルを用いることが可能である。そして、電子透かしの量子化テーブルについてだけＱ＝８  の制約を課すようにしても。このようにすると、上記数１２の式が満たされなくなるので、ＪＰＥＧ復号は透かしデータが消えないように整数化を行う必要がある。
そのような復号方法は可能であり、詳細は別途報告する。
【００７８】
実施の形態３．
上記実施の形態１では、ＪＰＥＧの量子化の構造を署名データとして埋めこむことによって、その画像が改ざんされていないことを証明する電子透かしの方法を提案した。また、実施の形態２では、ＤＣＴ係数の量子化ステップ幅を８以上とすることによって、ＪＰＥＧ復号後も透かしが残存するようにした。
【００７９】
この実施の形態３では、この量子化の制約を取り払い、高画質なＪＰＥＧ圧縮に適した認証用電子透かしの方法を提案する。概略をせつめいすると、この実施の形態３の方法は、圧縮のための量子化テーブルと、電子透かしのための量子化テーブルとを持ち、圧縮は細かく量子化する一方、電子透かしは粗く量子化することによって、符号化の画質と、電子透かしの残存とを両立させるようにしたものである。ここで、電子透かしの量子化ステップ幅は、８以上となるように設定される。しかし、この変更によって、逆ＤＣＴの結果を最も近い整数値に置きかえる一般的なＪＰＥＧ復号では、電子透かしの残存が保証されなくなる。そのため、本実施の形態３では、電子透かしの残存を保証したＪＰＥＧの復号方法を合わせて提案する。なお、本実施の形態３によれば、ＪＰＥＧ標準の量子化テーブルを用いた計算機実験により、スケールファクタを０．１まで小さくしても復号後の透かしデータが消えないことを確認した。このとき、透かしデータを埋めたＪＰＥＧ画像のＰＳＮＲは４０ｄＢ以上である。また、本実施の形態３が提案する電子透かしの方法は、局所的に量子化幅を変調する適応符号化や、さらにはＭＰＥＧなどの動画像符号化に対しても適用が可能である。
【００８０】
上記実施の形態１，２の方法を用いれば、ＪＰＥＧで圧縮された画像が（１）正規の発行者によるものであり、（２）改ざんされていないことを画像データだけから証明することができる。また、そのための電子透かしはＪＰＥＧで復号した後にも残ることが保証される。しかし、上記実施の形態２による制約は、ＪＰＥＧの量子化をステップ幅８以上で行うとするものであり、高画質のＪＰＥＧ圧縮に不適であった。本実施の形態３では、この制約が必要ない電子透かしのアルゴリズムと復号後に透かしが残るためのＪＰＥＧの復号方法を示す。
【００８１】
＜１．実施の形態３の電子透かしのアルゴリズム＞
アルゴリズムの詳細は、上記実施の形態１の場合と同様である。つまり、基本的なアルゴリズムは、画像のＤＣＴ係数の量子化構造を暗号化して、ＤＣＴブロックの最後に付加するものである。なお、上記実施の形態１，２までは、画像データ圧縮のための量子化器と、電子透かしのための量子化器とは同一の量子化部２１を用いていた。しかし、ＪＰＥＧ復号後の透かしの残存を保証するためには、上記実施の形態２にて説明したように電子透かしの量子化に対して一定の制約があり、あまり細かい量子化器を用いることができない。よって、本実施の形態３では、画像データ圧縮と、透かしとに、それぞれ別の量子化器を用いる方法を提案する。
【００８２】
図８は、本発明に係る電子透かし埋め込み方法が実行される実施の形態３の画像符号化装置の構成を示す図である。図８において、この画像符号化装置は、ＤＣＴ部１、２つの量子化部２Ａ，２Ｂ、２つのジグザグスキャン部３Ａ，３Ｂ、２つのランレングス化部４Ａ，４Ｂ、ダミーラン付加部５、ハッシュ関数部６、排他的論理和（ＥＸＯＲ）部７、暗号化部８、透かし埋め込み部９、可変長符号化部１０、ストリーム符号化部１１を有しており、入力するホスト画像をＪＰＥＧ圧縮符号化する際、署名画像等の透かしデータを公開鍵暗号方式により暗号化して電子透かしとして埋め込み符号化ストリームとしてＮ（Ｎは自然数）個のブロック毎に変換され出力するように構成されている。実施の形態１との違いは、入力したホスト画像を２つの量子化部２Ａ，２Ｂにより、それぞれ異なる量子化テーブル、すなわち圧縮のための量子化テーブルＱｃと、電子透かしのための異なる量子化テーブルＱｗとにより別々に量子化する点である。なお、上記実施の形態１の場合と同様に、ＤＣＴ部１や、量子化部２、ジグザグスキャン部３、ランレングス化部４、可変長符号化部１０、ストリーム符号化部１１等は、通常のＪＰＥＧ圧縮符号化を行うので、実施の形態３の電子透かし埋め込み方法を中心に以下に説明する。
【００８３】
まず、圧縮のための量子化部２Ａの量子化ステップをＱｃｉｊ、電子透かしのための量子化部２Ｂの量子化ステップをＱｗｉｊとする（ｉ，ｊ＝０，１，…，７）。ここで、全てのｉ，ｊについて、次の条件が満たされなければならない。
【００８４】
【数１４】
2004242162.tif 000016
【００８５】
【数１５】
2004242162.tif 000017
【００８６】
上記数１４の式の条件は、透かしデータが埋め込み可能なために必要である。また、上記数１５の式の条件は、ＪＰＥＧ復号後に透かしデータが残存するために必要である。この条件を満たすには、任意のＱｃｉｊに対して、Ｑｗｉｊを以下のように設定すればよい。
【００８７】
【数１６】
2004242162.tif 000018
【００８８】
ＤＣＴブロックに透かしデータを埋めこむには以下のようにする。
（１）ＤＣＴ係数ｆｉｊをＱｃｉｊで量子化して、ｆｃｉｊを得る。
（２）ｆｃｉｊをＱｃｉｊで逆量子化したものをＱｗｉｊで量子化し、そのランレングスの構造を上記実施の形態１の方法と同様に暗号化し、埋め込みビットｂと、埋め込み位置（ｐ，ｑ）を得る。
（３）ｆｃｐｑを以下のように変更する。
【００８９】
【数１７】
2004242162.tif 000019
【００９０】
次に、ＪＰＥＧの量子化テーブルを０．４倍した次式の数１８の量子化器で符号化を行う場合の具体例について説明する。。
【００９１】
【数１８】
2004242162.tif 000020
【００９２】
そして、上記数１６の式から、
【００９３】
【数１９】
2004242162.tif 000021
【００９４】
である。今、あるブロックのＤＣＴ係数が、次式で与えられるとする。
【００９５】
【数２０】
2004242162.tif 000022
【００９６】
これをＱｃｉｊで量子化すると、次式のインデックスが得られる。
【００９７】
【数２１】
2004242162.tif 000023
【００９８】
これをＱｃｉｊで逆量子化し、Ｑｗｉｊで再量子化すると、次式のインデックスを得る。
【００９９】
【数２２】
2004242162.tif 000024
【０１００】
この量子化構造を暗号化して、埋め込みビットが０ならば、上記数１７の式より、
【０１０１】
【数２３】
2004242162.tif 000025
【０１０２】
ただし、埋め込み位置は、ジグザグスキャンの直後の（０、３）の位置とした。したがって、透かしを埋め込んだ量子化インデックスは、
【０１０３】
【数２４】
2004242162.tif 000026
【０１０４】
となる。
【０１０５】
＜２．ＪＰＥＧの復号アルゴリズム＞
符号化の量子化マトリックスＱｃと、電子透かしの量子化マトリックスＱｗとが一致し、そのステップ幅が全て８以上であれば、逆ＤＣＴした実数値のベクトルをユークリッド距離が最も近い整数値のベクトルに置きかえる復号を行えば、復号後の画像から透かしデータが消えないことが証明できる。しかし、上述したように符号化と、電子透かしとで異なる量子化マトリックスを用いれば、そのことが保証されない。したがって、単純に近接の整数値ベクトルに復号すると透かしデータが消えてしまう場合がある。
【０１０６】
このことを、図９を用いて説明する。
図９は、復号ベクトルの空間を図示したものである。図８において、Ｃｔ  はＱｗ  で量子化したＤＣＴ  係数の復号ベクトル、ｙはＱｃ  で量子化したＤＣＴ  係数の復号ベクトル、○は整数ベクトル、実線で囲んだ領域はＱｗ  で量子化して符号化するとＣｔ  に復号されるベクトルの集合Ｃ  である。Ｃｔ  とｙとは実数値のベクトルであり、Ｃｔ  は復号する時点で既知である。Ｑｗ＝Ｑｃ  であるときは、ｙ＝Ｃｔ  である。今、Ｑｗ  とＱｃ  が異なり、ｙが図の位置に復号されたとする。このとき、ｙに最も近い整数ベクトルはｘ０であり、このベクトルは集合Ｃ  の属さない。これを再符号化するとその復号ベクトルはＣｔ  とならない。これが、復号ベクトルから透かしが消える原因である。ところが、今、我々はＣｔ  を知っている。したがって、ｘ０から近隣の整数ベクトルを辿ってＣｔ  に少しずつ近づいていけば、いつかは集合Ｃ  に属するベクトルに到着する。この観察から、次の復号アルゴリズムを得る。
【０１０７】
【数２５】
2004242162.tif 000027
【０１０８】
このアルゴリズムでは、繰返しの各回において、
【０１０９】
【数２６】
2004242162.tif 000028
【０１１０】
が成り立つ。また、Ｑｗ＞８であれば、Ｃｔ  の周辺に集合Ｃ  に属する整数ベクトルが存在する。
ゆえに、以上の復号アルゴリズムは常に収束する。
【０１１１】
＜３．評価＞
図１０は、テスト画像（５１２×５１２画素）に対して、符号化の量子化テーブルの細かさを変えて行った実験結果である。表でｓｃａｌｅは量子化の細かさを表す。量子化テーブルはＪＰＥＧのデフォルトのものをｓｃａｌｅの値で乗算して用いた。これが小さくなる程、量子化は細かくなる。また、ｓｃａｌｅが０．８の場合は、全ての量子化パラメータは８以上となり、符号化と透かしで同一の量子化が行われる。Ｎｂｌｋは復号後に整数ベクトルの修正が必要となったブロックの数である。また、Ｎｒｅｐ／Ｎｂｌｋはベクトルが修正された場合に必要とされた繰返し演算の数である。
【０１１２】
図１０から以下のことがわかる。
（１）ｓｃａｌｅ＝０．８の場合は、修正されたブロックは０であり、実施の形態２の結果と合致する。すなわち、全ての量子化パラメータが８以上であれば、ＪＰＥＧ復号後に必ず透かしが残存する。
（２）スケールを小さくすると修正されるブロック数は増加する。
（３）スケールを小さくすると修正に必要な繰り返し演算の数は増加する。しかし、この数は実験の範囲で高々４．５である。
【０１１３】
実験の結果、修正されなかったブロックは存在しない。すなわち、提案のアルゴリズムが確実に収束することが裏付けられた。
【０１１４】
以上説明したように、本実施の形態３によれば、符号化の際の量子化テーブルとは別に、電子透かし用の独立な量子化テーブルと持つことによって、高画質なＪＰＥＧ符号化に対応した認証用電子透かしのアルゴリズムを実現できる。また、復号画像に透かしデータが残存するための復号方法を示した。ここで示した方式はＭＰＥＧなどのブロック単位の符号化方式に展開が可能であると考える。
【０１１５】
なお、上記実施の形態１〜３では、説明の便宜のため、静止画をＪＰＥＧ圧縮符号化により符号化する場合に透かしデータを埋め込む方法について説明したが、本発明では、画像をブロック毎に分割し周波数変換および量子化した量子化インデックスに透かしデータを埋め込めれば良いので、ＤＣＴ変換を使用したＪＰＥＧに限定されず、例えば、ウエーブレット変換を使用するＪＰＥＧ２０００などにも適用可能であるし、さらにはＭＰＥＧ等の動画を圧縮する圧縮符号化手法にも適用可能である。
【０１１６】
【発明の効果】
以上説明したように、本発明によれば、画像データを量子化した量子化インデックスのランレングス構造を署名データとして画像データに埋めこむようにしたので、画像データが改ざんされていないことを証明することができる。
【図面の簡単な説明】
【図１】本発明に係る電子透かし埋め込み方法が実行される実施の形態１の画像符号化装置の構成を示す図。
【図２】量子化インデックスの一例を示す図。
【図３】ｎが７まであるＪＰＥＧで（ｎ、±１）を符号化するためのハフマン符号の符号長の一例を示す図。
【図４】量子化テーブルの一例を示す図。
【図５】本発明に係る電子透かし埋め込み方法により符号化ストリームを復号する画像復号装置における透かしデータ検出回路の一例を示す図。
【図６】２元アダマール変換の時間領域（ｘ−ｙ  座標）と、変換領域（ｕ−ｖ  座標）のサンプル点の構造の一例を示す図。
【図７】実施の形態１において５つのテスト画像を用いて全てのＤＣＴ係数を同じステップ幅Ｑで量子化し、それを復号した後、再符号化して異なるクラスにマッピングされるブロック数の一例を示す図。
【図８】本発明に係る電子透かし埋め込み方法が実行される実施の形態３の画像符号化装置の構成を示す図。
【図９】復号ベクトルの空間の一例を示す図。
【図１０】実施の形態３においてテスト画像に対し符号化の量子化テーブルの細かさを変えて行った実験結果の一例を示す図。
【符号の説明】
１  ＤＣＴ部、２  量子化部、３  ジグザグスキャン部、４  ランレングス化部、５  ダミーラン付加部、６  ハッシュ関数部、７  排他的論理和（ＥＸＯＲ）部、８  暗号化部、９  透かし埋め込み部、１０  可変長符号化部、１１  ストリーム符号化部。
【図１】
2004242162.tif 000029
【図２】
2004242162.tif 000030
【図３】
2004242162.tif 000031
【図４】
2004242162.tif 000032
【図５】
2004242162.tif 000033
【図６】
2004242162.tif 000034
【図７】
2004242162.tif 000035
【図８】
2004242162.tif 000036
【図９】
2004242162.tif 000037
【図１０】
2004242162.tif 000038