(57)【要約】【課題】電子透かし検出装置が電子透かしの埋め込み位置を正確に特定することができるように、電子透かしを埋め込むことができる電子透かし埋め込み装置及び電子透かし埋め込みプログラムを得ることを目的とする。【解決手段】複雑度算出部２により算出された各ブロックにおける複雑度を比較して、複雑度が上位ｍ個のブロックを選択するブロック選択部３を設け、電子透かし埋め込み部４がブロック選択部３により選択されたブロックにおける所定位置の信号の信号値を変更する電子透かしの埋め込み処理を行う。【選択図】図１
2008288885.tif 000002
【特許請求の範囲】
【請求項１】
複数のブロックに分割された信号を格納する信号格納手段と、上記信号格納手段に格納された信号の各ブロックにおける複雑度を算出する複雑度算出手段と、上記複雑度算出手段により算出された各ブロックにおける複雑度を比較して、複雑度が上位のブロックを選択するブロック選択手段と、上記ブロック選択手段により選択されたブロックにおける所定位置の信号の信号値を変更する電子透かしの埋め込み処理を行う電子透かし埋め込み手段とを備えた電子透かし埋め込み装置。
【請求項２】
複雑度算出手段は、ブロック内の多くの信号の信号値が零値であるスパースな信号が信号格納手段に格納される場合、ブロック内の先頭の信号から一番後ろの非零値の信号までの個数が当該ブロックの複雑度であるとして、先頭の信号から一番後ろの非零値の信号までの個数を計数することを特徴とする請求項１記載の電子透かし埋め込み装置。
【請求項３】
複雑度算出手段は、ブロック内の多くの信号の信号値が零値であるスパースな信号が信号格納手段に格納される場合、ブロック内の信号値が非零値の信号の個数が当該ブロックの複雑度であるとして、ブロック内の信号値が非零値の信号の個数を計数することを特徴とする請求項１記載の電子透かし埋め込み装置。
【請求項４】
ブロック選択手段は、ブロック内の信号の個数がＮ個である場合、複雑度がＮのブロックと複雑度がＮ−１のブロックについては、複雑度が同値であるとみなし、複雑度が同値のブロックについては、検索順序が先のブロックを優先的に選択することを特徴とする請求項２または請求項３記載の電子透かし埋め込み装置。
【請求項５】
電子透かし埋め込み手段は、ブロック選択手段により選択されたブロック内の信号を一定の規則で並べ、一番後ろの非零値の信号が、当該ブロックの最後の信号でなければ、一番後ろの非零値の信号の次の信号の信号値を非零値に変更し、一番後ろの非零値の信号が、当該ブロックの最後の信号であれば、当該ブロックの最後の信号の信号値を変更することを特徴とする請求項１から請求項４のうちのいずれか１項記載の電子透かし埋め込み装置。
【請求項６】
複数のブロックに分割された信号を格納する信号格納手段と、上記信号格納手段に格納された信号の各ブロックにおける複雑度を算出する複雑度算出手段と、上記複雑度算出手段により算出された各ブロックにおける複雑度を比較して、複雑度が上位のブロックを選択するブロック選択手段と、上記ブロック選択手段により選択されたブロックにおける所定位置の信号の信号値から埋め込まれた電子透かしを復号する電子透かし復号手段とを備えた電子透かし検出装置。
【請求項７】
ブロック選択手段は、複雑度算出手段により算出された複雑度が同値のブロックについては、検索順序が先のブロックを優先的に選択することを特徴とする請求項６記載の電子透かし検出装置。
【請求項８】
複数のブロックに分割された信号を格納する信号格納処理手順と、上記信号格納処理手順により格納された信号の各ブロックにおける複雑度を算出する複雑度算出処理手順と、上記複雑度算出処理手順により算出された各ブロックにおける複雑度を比較して、複雑度が上位のブロックを選択するブロック選択処理手順と、上記ブロック選択処理手順により選択されたブロックにおける所定位置の信号の信号値を変更する電子透かしの埋め込み処理を行う電子透かし埋め込み処理手順とをコンピュータに実行させるための電子透かし埋め込みプログラム。
【請求項９】
複数のブロックに分割された信号を格納する信号格納処理手順と、上記信号格納処理手順により格納された信号の各ブロックにおける複雑度を算出する複雑度算出処理手順と、上記複雑度算出処理手順により算出された各ブロックにおける複雑度を比較して、複雑度が上位のブロックを選択するブロック選択処理手順と、上記ブロック選択処理手順により選択されたブロックにおける所定位置の信号の信号値から埋め込まれた電子透かしを復号する電子透かし復号処理手順とをコンピュータに実行させるための電子透かし検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば、画像信号や音声信号に電子透かしを埋め込む電子透かし埋め込み装置及び電子透かし埋め込みプログラムと、画像信号や音声信号に埋め込まれている電子透かしを検出する電子透かし検出装置及び電子透かし検出プログラムとに関するものである。
【背景技術】
【０００２】
従来より、デジタル画像の改ざんを検出することができるようにするために、電子透かしをデジタル画像に埋め込む電子透かし埋め込み装置が開発されている。
例えば、以下の特許文献１に開示されている電子透かし埋め込み装置では、ＪＰＥＧなどのデジタル画像を適用対象として、そのデジタル画像をＤＣＴ（Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）によって周波数領域に変換する。
そして、電子透かし埋め込み装置は、周波数領域の信号を量子化し、その量子化係数をブロック毎にスキャンして、所定の順序で並べ替えた後、最後の非零の係数の直後に位置する一つの零の係数を“＋１”または“−１”に変更することによって、１ビットの情報を埋め込むようにしている。
【０００３】
ただし、並べ替えた最後の係数が“０”でない場合は、最後の係数を強制的に“＋１”または“−１”に変更するようにしてもよいが、画質の劣化を防止するため、最後の係数だけ、図７に示すようなテーブルにしたがって変更してもよい。
この場合、埋め込み情報が“０”であれば、「…、−５、−３、−１、＋２、＋４、＋６、…」の中で、現在の値に最も近い値に係数を変更する（最初から、これらの値の一つならば、変更しなくてよい）。
埋め込み情報が“１”であれば、現在の係数を「…、−６、−４、−２、＋１、＋３、＋５、…」のいずれかの値とする。
これにより、変更量は高々“１”となるので、電子透かしの埋め込みに伴う画質の劣化が軽減されることになる。
【０００４】
ここで、デジタル画像を構成する複数のブロックのうち、電子透かしを埋め込むブロックが予め定められている場合（例えば、全てのブロックに１ビットの情報を埋め込む場合や、乱数で抽出されたブロックに順番に情報を埋め込む場合）、電子透かし埋め込み装置と電子透かし検出装置が、予め定められているブロックの情報を共有すれば、電子透かし検出装置が電子透かし埋め込み装置により埋め込まれた電子透かしを誤りなく検出することができる。
【０００５】
しかし、電子透かしの埋め込み対象となる信号は、一般に画像信号や音信号など、人間が知覚する信号であり、そのような信号に対して、意味内容と無関係に信号を変更する電子透かしの埋め込み処理を行うと、電子透かしの埋め込み場所によっては、その信号の変更が主観的な劣化として知覚されてしまうことがある。
そこで、電子透かしの埋め込み処理においては、一般的に、変更が知覚され難い部分を選択し、そのような部分に電子透かしの埋め込みを行う適応処理が用いられる。
【０００６】
このような適応処理の多くは、人間の知覚のマスキング効果を利用している。
マスキング効果は、新たに加えられる信号が、原信号と似たものであれば、原信号をマスクすることによって、変更が劣化として知覚され難くなる性質のことである。
このことから、例えば、画像信号の場合、明るさや色の変化が激しい部分では、電子透かしによって信号を変更しても劣化が目立たないが、変化が緩やかで平坦な部分では、電子透かしによって信号を変更すると、劣化が目立つため、あまり大きな変更を加えることができないことになる。
【０００７】
例えば、以下の非特許文献１には、原信号を複数の周波数成分に分解して、電子透かし信号の周波数成分に近い成分の大きさを局所的に計算し、電子透かし信号の周波数成分に近い成分の大きさに応じて、電子透かし信号の大きさをコントロールする手法が開示されている。
このように、原信号の局所的な変化を計算し、目的の信号処理によって導入される歪みが原信号にマスクされるように、歪みの強度を調整する手法は、広く画像処理一般に用いられている手法であり、電子透かしの埋め込みにおいても例外ではない。
【０００８】
しかし、このような埋め込み制御を有する従来の電子透かし埋め込み装置には、以下の問題点がある。
まず、電子透かしの埋め込み方法に依存して、適応処理によって選択された埋め込み箇所が正確に特定できなくても、埋め込んだ情報を検出することができる場合がある。
例えば、原信号と相関のない微弱な信号を原信号に足し合わせ、相関によって微弱な信号を検出することにより、埋め込んだ情報を復号する方法がある。
このような場合には、足し合わせる信号に若干の変化があっても（適応処理によって、部分的に信号の変化量を減衰させている場合）、多くの場合、微弱な信号を検出することが可能である。
また、特許文献１のように、一部の信号の状態（例えば、図７のようなテーブルで定義される特定の信号の信号値）によって情報を埋め込む場合でも、誤り訂正の手法を用いれば、適応処理によって部分的に埋め込めなかった部分があったとしても、その部分の誤りを訂正することによって、高い確率で埋め込んだ情報を正しく検出することができる。
【０００９】
しかし、これらの方法は、いずれも、埋め込み方法に一定の自由度を与えることによって、電子透かしの検出において、厳密な埋め込み場所の特定を回避するものである。
これは、埋め込んだ後の信号を若干変更しても、電子透かしの情報が変更されないことにつながり、冒頭に述べたデジタル画像の改ざんの検出の目的に適さない。
その理由は、電子透かしの情報を変えない自由度の範囲内の変更と、悪意のある改ざんを区別することは、厳密には困難だからである。
改ざんの検出を目的とする場合は、適応的に埋め込みを行った後の信号から、埋め込み箇所を正確に復元できることが望ましく、このようにすれば、信号が僅かでも変化したことを確実に検知することができる。
【００１０】
【特許文献１】特開２００４−２４２１６２号公報（段落番号［０００７］から［００１０］、図１）
【非特許文献１】IEEE Journal of selected areas in communication, vol. 16, no. 4, pp. 540-550, May 1998, M. D. Swanson, B. Zhu, and A. H. Tewfik, “Multiresolution Scene-Based Video Watermarking Using Perceptual Models”.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来の電子透かし埋め込み装置は以上のように構成されているので、適応処理では、原信号を基準にして、電子透かしの埋め込みの可否を制御しているが、電子透かし検出装置では、一般に、電子透かしが埋め込まれる前の信号がわからない。このため、電子透かし検出装置では、電子透かしが埋め込まれた位置を正確に特定することができず、電子透かしを正確に復元することができないことがある課題があった。
【００１２】
この発明は上記のような課題を解決するためになされたもので、電子透かし検出装置が電子透かしの埋め込み位置を正確に特定することができるように、電子透かしを埋め込むことができる電子透かし埋め込み装置及び電子透かし埋め込みプログラムを得ることを目的とする。
また、この発明は、電子透かし埋め込み装置により埋め込まれた電子透かしの埋め込み位置を正確に特定することができる電子透かし検出装置及び電子透かし検出プログラムを得ることを目的とする。
【課題を解決するための手段】
【００１３】
この発明に係る電子透かし埋め込み装置は、複雑度算出手段により算出された各ブロックにおける複雑度を比較して、複雑度が上位のブロックを選択するブロック選択手段を設け、電子透かし埋め込み手段がブロック選択手段により選択されたブロックにおける所定位置の信号の信号値を変更する電子透かしの埋め込み処理を行うようにしたものである。
【発明の効果】
【００１４】
この発明によれば、複雑度算出手段により算出された各ブロックにおける複雑度を比較して、複雑度が上位のブロックを選択するブロック選択手段を設け、電子透かし埋め込み手段がブロック選択手段により選択されたブロックにおける所定位置の信号の信号値を変更する電子透かしの埋め込み処理を行うように構成したので、電子透かし検出装置が電子透かしの埋め込み位置を正確に特定することができるように、電子透かしを埋め込むことができる効果がある。
【発明を実施するための最良の形態】
【００１５】
実施の形態１．
図１はこの発明の実施の形態１による電子透かし埋め込み装置を示す構成図であり、図において、メモリ１は複数のブロックに分割されたデジタル信号を入力し、そのデジタル信号を記憶する信号格納手段を構成している。
ここで、デジタル信号は、例えば、画像信号や音声信号などが該当する。
画像信号や音声信号は、空間的に隣接する信号間の相関が強いため、信号を周波数領域に変換すると、低域の周波数成分に電力が集中する。
このとき、変換係数を粗く量子化すれば、多くの高域周波数成分は“０”に切り捨てられる。このような信号をスパースな信号と称する。
以下、メモリ１に入力されるデジタル信号は、複数のブロックに分割されたスパースな信号であるものとする。
なお、デジタル信号を周波数領域に変換する際、一般に、ＤＣＴ（Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）やウェーブレット変換などが用いられる。
【００１６】
複雑度算出部２はメモリ１に格納されたデジタル信号の各ブロックにおける複雑度を算出する処理を実施する。なお、複雑度算出部２は複雑度算出手段を構成している。
ブロック選択部３は複雑度算出部２により算出された各ブロックにおける複雑度を比較して、複雑度が上位ｍ個のブロックを選択する処理を実施する。なお、ブロック選択部３はブロック選択手段を構成している。
電子透かし埋め込み部４はブロック選択部３により選択されたブロックにおける所定位置の信号の信号値を変更する電子透かしの埋め込み処理を実施する。なお、電子透かし埋め込み部４は電子透かし埋め込み手段を構成している。
【００１７】
図１の例では、電子透かし埋め込み装置の構成要素である複雑度算出部２、ブロック選択部３及び電子透かし埋め込み部４がそれぞれ専用のハードウェア（例えば、ＣＰＵなどを実装している半導体集積回路基板）で構成されているものを想定しているが、電子透かし埋め込み装置がコンピュータで構成される場合、複雑度算出部２、ブロック選択部３及び電子透かし埋め込み部４の処理内容が記述されている電子透かし埋め込みプログラムをコンピュータのメモリに記憶し、当該コンピュータのＣＰＵが当該メモリに記憶されている電子透かし埋め込みプログラムを実行するようにしてもよい。
【００１８】
図２はこの発明の実施の形態１による電子透かし検出装置を示す構成図であり、図において、メモリ１１は電子透かし埋め込み装置により電子透かしが埋め込まれたデジタル信号を入力し、そのデジタル信号を記憶する信号格納手段を構成している。
複雑度算出部１２はメモリ１１に格納されたデジタル信号の各ブロックにおける複雑度を算出する処理を実施する。なお、複雑度算出部１２は複雑度算出手段を構成している。
【００１９】
ブロック選択部１３は複雑度算出部１２により算出された各ブロックにおける複雑度を比較して、複雑度が上位ｍ個のブロックを選択する処理を実施する。なお、ブロック選択部１３はブロック選択手段を構成している。
電子透かし復号部１４はブロック選択部１３により選択されたブロックにおける所定位置の信号の信号値から埋め込まれた電子透かしを復号する処理を実施する。なお、電子透かし復号部１４は電子透かし復号手段を構成している。
【００２０】
図２の例では、電子透かし検出装置の構成要素である複雑度算出部１２、ブロック選択部１３及び電子透かし復号部１４がそれぞれ専用のハードウェア（例えば、ＣＰＵなどを実装している半導体集積回路基板）で構成されているものを想定しているが、電子透かし検出装置がコンピュータで構成される場合、複雑度算出部１２、ブロック選択部１３及び電子透かし復号部１４の処理内容が記述されている電子透かし検出プログラムをコンピュータのメモリに記憶し、当該コンピュータのＣＰＵが当該メモリに記憶されている電子透かし検出プログラムを実行するようにしてもよい。
【００２１】
図３はこの発明の実施の形態１による電子透かし埋め込み装置の処理内容を示すフローチャートである。
図４はこの発明の実施の形態１による電子透かし検出装置の処理内容を示すフローチャートである。
【００２２】
次に動作について説明する。
最初に、図１の電子透かし埋め込み装置による電子透かしの埋め込み処理について説明する。
複数のブロックに分割されたスパースな信号であるデジタル信号が電子透かし埋め込み装置に入力されると、そのデジタル信号がメモリ１に格納される（図３のステップＳＴ１）。
【００２３】
複雑度算出部２は、デジタル信号がメモリ１に格納されると、そのデジタル信号のブロック毎に、当該ブロックの複雑度を算出する（ステップＳＴ２）。
以下、各ブロックにおける複雑度の算出処理を具体的に説明する。
ここでは、スパースな信号であるデジタル信号のブロックサイズが、例えば、８×８のサイズであるものとする。
【００２４】
複雑度算出部２は、スパースな信号であるデジタル信号を量子化し、例えば、デジタル信号がＤＣＴによって周波数領域に変換されている場合、図５に示すようなスキャン順序で、その量子化係数の読み出しを行う。
ここで、図５の左上の量子化係数は周波数が低く、右下に行くほど周波数が高くなる。
例えば、画像信号などのデジタル信号では、高域周波数の電力が小さいため、図５に示すような順序で信号を並べると、多くの場合、あるところ以上で、全ての信号値が“０”になる。
複雑度算出部２は、最後の非零の量子化係数がｎ番目に現われ、ｎ番目以降の量子化係数が全て“０”であれば、当該ブロックの複雑度が“ｎ”であるとする。
【００２５】
また、複雑度算出部２は、スパースな信号であるデジタル信号が、例えば、ウェーブレット変換によって周波数領域に変換されている場合、図６に示すようなスキャン順序で、量子化係数の読み出しを行う。
ウェーブレット変換の場合は、一般に変換がブロック内に閉じていないが、その場合でも、空間的に近い量子化係数をまとめてブロックに分割することができる。
図６の例でも、周波数の低い左上の成分から順番にスキャンが行われるが、ウェーブレット変換では、高域の周波数成分が粗く分割されるので、ＤＣＴの場合とは異なるスキャン順序になっている。
ウェーブレット変換の場合も、最後の非零の量子化係数がｎ番目に現われ、ｎ番目以降の量子化係数が全て“０”であれば、当該ブロックの複雑度が“ｎ”であるとする。
【００２６】
複雑度算出部２は、上記のようにして、各ブロックの複雑度を算出するが、スパースな信号であるデジタル信号が、ＤＣＴによって周波数領域に変換されている場合でも、ウェーブレット変換によって周波数領域に変換されている場合でも、予めスキャン順序が決められていれば、ブロックの複雑度を一意に決定することができる。
【００２７】
ブロック選択部３は、複雑度算出部２が各ブロックの複雑度を算出すると、各ブロックの複雑度を比較して、複雑度が上位ｍ個のブロックを選択する（ステップＳＴ３）。
ただし、ブロック選択部３は、ブロック内の信号の個数がＮ個である場合（ブロックサイズが８×８である場合、Ｎ＝６４）、複雑度がＮのブロック（複雑度が最大のブロック）と複雑度がＮ−１のブロックについては、複雑度が同値であるものとして取り扱う。また、複雑度が同値のブロックについては、検索順序が先のブロックを優先的に選択するものとする。
以下、ブロック選択部３におけるブロックの選択処理を具体的に説明する。
【００２８】
ブロック選択部３は、全てのブロックに順番に１〜ｋの番号をつけて、複雑度算出部２により算出された複雑度が大きい順にブロックをソートする。
ソートの詳細は以下の通りである。
ただし、ｉ番目のブロックをＢｉ、ｊ番目のブロックをＢｊと表記し、ブロックＢｉの複雑度をＣ（Ｂｉ）、ブロックＢｊの複雑度をＣ（Ｂｊ）と表記する。
【００２９】
ブロック選択部３は、ブロックＢｉとブロックＢｊが、次の関係を満たすように、ブロックＢ１〜Ｂｋの並べ替えを行う。
（１）ｍｉｎ（Ｃ（Ｂｉ），Ｎ−１）＞ｍｉｎ（Ｃ（Ｂｊ），Ｎ−１）の場合
→  ブロックＢｉの順位をブロックＢｊの順位より上にする
（２）ｍｉｎ（Ｃ（Ｂｉ），Ｎ−１）＝ｍｉｎ（Ｃ（Ｂｊ），Ｎ−１）の場合
ｉ＜ｊ  →  ブロックＢｉの順位をブロックＢｊの順位より上にする
ｉ≧ｊ  →  ブロックＢｉの順位をブロックＢｊの順位より下にする
（３）ｍｉｎ（Ｃ（Ｂｉ），Ｎ−１）＜ｍｉｎ（Ｃ（Ｂｊ），Ｎ−１）
→  ブロックＢｉの順位をブロックＢｊの順位より下にする
ただし、ｍｉｎ（Ａ，Ｂ）は、ＡとＢのうち、大きくない方を選択する旨を表す演算子である。
【００３０】
上記のブロックのソートでは、複雑度が大きいブロックが、複雑度が小さいブロックよりも順位が上になる。
ただし、ブロックＢｉの複雑度がＮ（最大の複雑度）、ブロックＢｊの複雑度がＮ−１であれば、複雑度が同値であるものとしてソートされる。
２つのブロックＢｉ，Ｂｊの複雑度が同値の場合には、番号が小さいブロック（検索順序が先のブロック）の方が、順位が上になる。
【００３１】
ブロック選択部３は、ブロックＢ１〜Ｂｋの並べ替えを行うと、順位が“１”から“ｍ”までのブロックを選択する。ｍは電子透かしを埋め込む情報のビット数である。
ここで、図８は複雑度算出部２により算出された各ブロックの複雑度の数値例を示す説明図であり、図８では、ブロックの総数が１０個である例を示している。
また、図９はブロック選択部３によるソート結果を示す説明図である。
図９において、ブロックＢ６，Ｂ７の順位がブロックＢ８の順位より上である理由は、ブロックＢ８の複雑度が６４（＝Ｎ）であり、ブロックＢ６，Ｂ７の複雑度が６３（＝Ｎ−１＝６４−１）であるため、ブロックＢ６，Ｂ７，Ｂ８の複雑度が同値であるものとして扱われ、番号が小さいブロックの方が、順位が上になるようにしているからである。
【００３２】
例えば、ビット数がｍ＝５の情報を埋め込む場合、ブロック選択部３は、上位５個のブロックとして、ブロックＢ３，Ｂ６，Ｂ７，Ｂ８，Ｂ２を選択する。
なお、ブロック選択部３は、上位ｍ個のブロックを選択すれば足りるため、ソートは全てのブロックについて行う必要はない。ソート処理を上位ｍ個のブロックに制限すれば、ブロック選択部３の処理の簡単化を図ることができる。
【００３３】
電子透かし埋め込み部４は、ブロック選択部３が上位ｍ個のブロックを選択すると、上位ｍ個のブロックにおける所定位置の信号の信号値を変更する電子透かしの埋め込み処理を実施する（ステップＳＴ４）。
即ち、電子透かし埋め込み部４は、ブロック選択部３により選択されたブロック毎に、当該ブロック内の量子化係数を一定の規則で並び替えを行う（例えば、図５や図６のスキャン順に並び替えを行う）。
【００３４】
そして、電子透かし埋め込み部４は、一番後ろの非零の量子化係数が、当該ブロックの最後の量子化係数でなければ、一番後ろの非零の量子化係数の次の量子化係数を“＋１”または“−１”に変更することによって、１ビットの情報の埋め込みを行う。
一方、一番後ろの非零の量子化係数が、当該ブロックの最後の量子化係数であれば、当該ブロックの最後の量子化係数だけ、図７に示すようなテーブルにしたがって変更する。
この場合、埋め込み情報が“０”であれば、「…、−５、−３、−１、＋２、＋４、＋６、…」の中で、現在の量子化係数に最も近い値に量子化係数を変更する（最初から、これらの値の一つならば、変更しなくてよい）。
埋め込み情報が“１”であれば、現在の量子化係数を「…、−６、−４、−２、＋１、＋３、＋５、…」のいずれかの値とする。
【００３５】
電子透かし埋め込み部４による電子透かしの埋め込み処理では、ブロックの複雑度が高々“１”しか増加しない。
即ち、電子透かしが埋め込まれた量子化係数が、ブロック最後の量子化係数でない場合は、複雑度は“１”だけ増加し、電子透かしが埋め込まれた量子化係数が、ブロック最後の量子化係数である場合は、複雑度は変化しない。
このため、電子透かしが埋め込まれた後のブロックから、ブロック選択部３により選択されたブロックを、順序とともに正確に特定することができる。
【００３６】
その理由は、ブロック選択部３により選択されたブロックの複雑度が全てＮであるならば、ブロック番号を参照すれば、ブロック選択部３により選択されたブロックを特定することができる。
例えば、ブロック選択部３により選択されたブロックにおいて、電子透かしが埋め込まれる前の複雑度がＮ−１である場合には、電子透かしの埋め込みによって複雑度がＮになる。
このとき、ブロック選択部３は、複雑度がＮとＮ−１のブロックについては、同一の複雑度であるとしてソートしているので、複雑度がＮのブロックをブロック番号の順番に選択すれば、ブロック選択部３により選択されたブロックを特定することができるとともに、選択されたブロックの順序を特定することができる。
また、埋め込み前の複雑度がＮ−２以下のブロックが選択された場合には、埋め込み前後で順位が変わらないので、特定することができる。
【００３７】
図１０は電子透かしが埋め込まれた前後の複雑度の変化を示す説明図である。
図１０の例では、上位５個のブロックに電子透かしが埋め込まれており、ブロックＢ３とＢ８については、埋め込み前において既に複雑度が６４であるため、透かしの埋め込みによって複雑度の変化がない。
電子透かしの埋め込み後の複雑度に注目すると、ブロックＢ３，Ｂ６，Ｂ７，Ｂ８のブロックの複雑度は６４であるため、ブロックＢ３，Ｂ６，Ｂ７，Ｂ８をブロック番号の順番に並べれば、１位から４位までのブロックが決まる（１位：ブロックＢ３、２位：ブロックＢ６、３位：ブロックＢ７、４位：ブロックＢ８）。
なお、５位のブロックは、次に複雑度が大きいブロックＢ２である。
【００３８】
電子透かし埋め込み部４により電子透かしの埋め込まれたブロックはメモリ１に書き込まれ、その後、メモリ１から電子透かしの埋め込まれたブロックを含む全てのブロックが読み出される（ステップＳＴ５）。
【００３９】
次に、図２の電子透かし検出装置による電子透かしの検出処理について説明する。
複数のブロックに分割されたスパースな信号であるデジタル信号が電子透かし検出装置に入力されると、そのデジタル信号がメモリ１１に格納される（図４のステップＳＴ１１）。
【００４０】
複雑度算出部１２は、デジタル信号がメモリ１１に格納されると、電子透かし埋め込み装置の複雑度算出部２と同様の方法で、そのデジタル信号のブロック毎に、当該ブロックの複雑度を算出する（ステップＳＴ１２）。
【００４１】
ブロック選択部１３は、複雑度算出部１２が各ブロックの複雑度を算出すると、各ブロックの複雑度を比較して、複雑度が上位ｍ個のブロックを選択する（ステップＳＴ１３）。
以下、ブロック選択部３におけるブロックの選択処理を具体的に説明する。
【００４２】
ブロック選択部１３は、全てのブロックに順番に１〜ｋの番号をつけて（ブロック番号は、埋め込み時と同じ規則で付ける）、複雑度算出部１２により算出された複雑度が大きい順にブロックをソートする。
ソートの詳細は以下の通りである。
ただし、ｉ番目のブロックをＢｉ、ｊ番目のブロックをＢｊと表記し、ブロックＢｉの複雑度をＣ（Ｂｉ）、ブロックＢｊの複雑度をＣ（Ｂｊ）と表記する。
【００４３】
ブロック選択部１３は、ブロックＢｉとブロックＢｊが、次の関係を満たすように、ブロックＢ１〜Ｂｋの並べ替えを行う。
（１）Ｃ（Ｂｉ）＞Ｃ（Ｂｊ）
→  ブロックＢｉの順位をブロックＢｊの順位より上にする
（２）Ｃ（Ｂｉ）＝Ｃ（Ｂｊ）の場合
ｉ＜ｊ  →  ブロックＢｉの順位をブロックＢｊの順位より上にする
ｉ≧ｊ  →  ブロックＢｉの順位をブロックＢｊの順位より下にする
（３）Ｃ（Ｂｉ）＜Ｃ（Ｂｊ）
→  ブロックＢｉの順位をブロックＢｊの順位より下にする
【００４４】
なお、ブロック選択部１３は、電子透かし埋め込み装置のブロック選択部３と異なり、複雑度がＮとＮ−１のブロックを同じ複雑度に分類しないので、並べ替えの規則において、演算子ｍｉｎ（）を使用していない。
ブロック選択部１３が、電子透かし埋め込み装置のブロック選択部３により選択されたブロックを正確に特定（順序の特定を含む）することができる理由は、上述した通りである。
【００４５】
電子透かし復号部１４は、ブロック選択部１３が上位ｍ個のブロックを選択すると、上位ｍ個のブロックにおける所定位置の信号の信号値から埋め込まれた電子透かしを復号する処理を実施する（ステップＳＴ１５）。
即ち、電子透かし復号部１４は、電子透かし埋め込み装置の電子透かし埋め込み部４と同一の規則を用いて、ブロック内の量子化係数の並び替えを行う。つまり、ブロック選択部１３により選択されたブロック毎に、当該ブロック内の量子化係数を、例えば、図５や図６のスキャン順に並び替えを行う。
【００４６】
電子透かし復号部１４は、ブロック内の量子化係数を並び替えると、最後の非零の量子化係数の値によって、電子透かし埋め込み装置によって埋め込まれた情報が“０”または１であるのかを判定する。
電子透かし復号部１４は、上記の判定処理をブロック選択部１３により選択されたブロックの個数だけ繰り返し実施し、その判定結果をｍビットのバイナリ信号（電子透かしの復号信号）として出力する。
【００４７】
ここでは、デジタル信号の全体がメモリ１１に格納されるものとして説明したが、電子透かしの埋め込みの場合と異なり、メモリ１１から意味のある信号として、再び読み出す必要がないので、電子透かしの検出に必要な最低限の情報だけをメモリ１１が保持するようにしてもよい。
例えば、ブロックの複雑度が算出された後は、その複雑度の値とブロックの最後の非零の量子化係数とを格納しておけば、電子透かしの検出には十分である。
【００４８】
以上で明らかなように、この実施の形態１によれば、複雑度算出部２により算出された各ブロックにおける複雑度を比較して、複雑度が上位ｍ個のブロックを選択するブロック選択部３を設け、電子透かし埋め込み部４がブロック選択部３により選択されたブロックにおける所定位置の信号の信号値を変更する電子透かしの埋め込み処理を行うように構成したので、電子透かし検出装置が電子透かしの埋め込み位置を正確に特定することができるように、電子透かしを埋め込むことができる効果を奏する。
【００４９】
また、この実施の形態１によれば、複雑度算出手部１２により算出された各ブロックにおける複雑度を比較して、複雑度が上位ｍ個のブロックを選択するブロック選択部１３を設け、電子透かし復号部１４がブロック選択部１３により選択されたブロックにおける所定位置の信号の信号値から埋め込まれた電子透かしを復号するように構成したので、電子透かし埋め込み装置により埋め込まれた電子透かしの埋め込み位置を正確に特定して、正確に電子透かしを復号することができる効果を奏する。
【００５０】
実施の形態２．
上記実施の形態１では、複雑度算出部２，１２がブロック内の先頭の量子化係数から最後の非零の量子化係数までの個数を当該ブロックの複雑度として算出するものについて示したが、ブロック内の非零の量子化係数を計数し、ブロック内の非零の量子化係数の個数を当該ブロックの複雑度として算出するようにしてもよい。
この場合も、電子透かし埋め込み装置は、複雑度を高々１しか増加させないので、上記実施の形態１と同様の効果を得ることができる。
【図面の簡単な説明】
【００５１】
【図１】この発明の実施の形態１による電子透かし埋め込み装置を示す構成図である。
【図２】この発明の実施の形態１による電子透かし検出装置を示す構成図である。
【図３】この発明の実施の形態１による電子透かし埋め込み装置の処理内容を示すフローチャートである。
【図４】この発明の実施の形態１による電子透かし検出装置の処理内容を示すフローチャートである。
【図５】スパースな信号であるデジタル信号がＤＣＴによって周波数領域に変換されている場合の量子化係数のスキャン順序を示す説明図である。
【図６】スパースな信号であるデジタル信号がウェーブレット変換によって周波数領域に変換されている場合の量子化係数のスキャン順序を示す説明図である。
【図７】埋め込み情報と量子化された係数の値を示す説明図である。
【図８】複雑度算出部２により算出された各ブロックの複雑度の数値例を示す説明図である。
【図９】ブロック選択部３によるソート結果を示す説明図である。
【図１０】電子透かしが埋め込まれた前後の複雑度の変化を示す説明図である。
【符号の説明】
【００５２】
１，１１  メモリ（信号格納手段）、２，１２  複雑度算出部（複雑度算出手段）、３，１３  ブロック選択部（ブロック選択手段）、４  電子透かし埋め込み部（電子透かし埋め込み手段）、１４  電子透かし復号部（電子透かし復号手段）。
【図１】
2008288885.tif 000003
【図２】
2008288885.tif 000004
【図３】
2008288885.tif 000005
【図４】
2008288885.tif 000006
【図５】
2008288885.tif 000007
【図６】
2008288885.tif 000008
【図７】
2008288885.tif 000009
【図８】
2008288885.tif 000010
【図９】
2008288885.tif 000011
【図１０】
2008288885.tif 000012