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