(57)【特許請求の範囲】
【請求項１】
複数の波形パターンからなる画素ブロックを並べて形成されたマクロブロックパターンを重畳した画像から電子透かし情報を検出する電子透かし検出装置であって、
入力された画像を離散フーリエ変換して得られるパワースペクトル行列における少なくとも２つのピーク位置情報と、予め定めた基準位置情報とを用いて、入力画像の一次変換歪補正を行なう一次変換歪補正手段と、
一次変換歪補正済み画像を、任意の位置から前記マクロブロックパターンのサイズのマクロブロックに分割し、分割して得られたマクロブロックを加算して加算マクロブロックを生成する加算マクロブロック生成手段と、
加算マクロブロックに対し、予め定められた複数種類の周波数に対応する各畳み込みオペレータによる畳み込み処理を施して、各周波数に対応したフィルタ処理済み画像群を得る各周波数毎フィルタ処理済み画像群生成手段と、
予め定められた探索範囲内の一の座標を設定する探索位置設定手段と、
前記一の座標をブロック切り出し位置とみなして前記画素ブロックのサイズで画像を分割するブロック分割を前記各周波数に対応したフィルタ処理済み画像群中の各画像に対して行い、各周波数に対応した各画像から、同じ一のブロック位置に対応する画素ブロック群を取得し、当該一のブロック位置に対する前記画素ブロック群の各画素ブロックについて、画素ブロック中の全画素の画素値の絶対値の和を求めて画素絶対値和群を取得し、画素絶対値和群の中で最大の値を最大絶対値和として求める処理を、全てのブロック位置に対して行って得られる最大絶対値和の総和をブロック切り出し位置応答値として出力するブロック切り出し位置応答値算出手段と、
前記探索位置設定手段により設定された前記探索範囲の各座標に対して前記ブロック切り出し位置応答値算出手段によりブロック切り出し位置応答値を求め、各座標に対応するブロック切り出し位置応答値の中で最大のブロック切り出し位置応答値に対応する座標をブロック切り出し位置として検出するブロック切り出し位置検出手段と、
前記ブロック切り出し位置検出手段により検出された前記ブロック切り出し位置を用いたブロック分割を、前記各周波数に対応したフィルタ処理済み画像群中の各画像に対して行い、各周波数に対応した各画像から、同じ一のブロック位置に対応する画素ブロック群の各画素ブロックについて、画素ブロック中の全画素の画素値の絶対値の和を求め、最大の絶対値和を取る画素ブロックに対応する周波数を少なくとも用いて、当該画素ブロックのブロック位置に対応する検出値行列の要素値を求める処理を各画素ブロックに対して行って検出値行列を求める検出値行列構成手段と、
検出値行列から検出対象系列を求め、検出対象系列を逆拡散することにより検出電子透かし情報を求める透かし情報逆拡散手段と
を有することを特徴とする電子透かし検出装置。
【請求項２】
前記透かし情報逆拡散手段は、
前記検出値行列の要素の並びを０度、９０度、１８０度、２７０度回転して得られる４つの行列を生成し、９０度、２７０度回転して得られた各行列の全要素値の符号を反転する回転手段と、
前記回転手段により得られた４つの行列の各々に対し、行列の一の要素位置が行列の所定の位置になるように要素をサイクリックシフトさせた行列を求める処理を各要素位置に対して行うことにより、変換済み検出値行列群を求める変換手段と、
変換済み検出値行列群における各行列から検出対象系列群を求め、検出対象系列群における各検出対象系列を逆拡散して得られる情報群のうち、最も信頼度の高い情報を検出電子透かし情報として出力する手段と
を有する請求項１に記載の電子透かし検出装置。
【請求項３】
前記複数の周波数は、＋の符号及び−の符号に対応付けられた２種類の周波数であり、
前記検出値行列構成手段は、＋の符号に対応する周波数に対応する画素ブロックの絶対値和から−の符号に対応する周波数に対応する画素ブロックの絶対値和を減算して得られた値を前記画素ブロックのブロック位置に対応する検出値行列の要素値とする請求項１に記載の電子透かし検出装置。
【請求項４】
前記複数の周波数は、＋の符号及び−の符号に対応付けられた２種類の周波数であり、
前記検出値行列構成手段は、２種類の周波数に対応する画素ブロックの絶対値和の差の絶対値に、大きいほうの絶対値和を取る画素ブロックに対応する周波数に対応する符号を付した値を前記画素ブロックのブロック位置に対応する検出値行列の要素値とする請求項１に記載の電子透かし検出装置。
【請求項５】
複数の波形パターンからなる画素ブロックを並べて形成されたマクロブロックパターンを重畳した画像から電子透かし情報を検出する電子透かし検出装置における電子透かし検出方法であって、
入力された画像を離散フーリエ変換して得られるパワースペクトル行列における少なくとも２つのピーク位置情報と、予め定めた基準位置情報とを用いて、入力画像の一次変換歪補正を行なう一次変換歪補正ステップと、
一次変換歪補正済み画像を、任意の位置から前記マクロブロックパターンのサイズのマクロブロックに分割し、分割して得られたマクロブロックを加算して加算マクロブロックを生成する加算マクロブロック生成ステップと、
加算マクロブロックに対し、予め定められた複数種類の周波数に対応する各畳み込みオペレータによる畳み込み処理を施して、各周波数に対応したフィルタ処理済み画像群を得る各周波数毎フィルタ処理済み画像群生成ステップと、
予め定められた探索範囲内の一の座標を設定する探索位置設定ステップと、
前記一の座標をブロック切り出し位置とみなして前記画素ブロックのサイズで画像を分割するブロック分割を前記各周波数に対応したフィルタ処理済み画像群中の各画像に対して行い、各周波数に対応した各画像から、同じ一のブロック位置に対応する画素ブロック群を取得し、当該一のブロック位置に対する前記画素ブロック群の各画素ブロックについて、画素ブロック中の全画素の画素値の絶対値の和を求めて画素絶対値和群を取得し、画素絶対値和群の中で最大の値を最大絶対値和として求める処理を、全てのブロック位置に対して行って得られる最大絶対値和の総和をブロック切り出し位置応答値として出力するブロック切り出し位置応答値算出ステップと、
前記探索位置設定ステップにより設定された前記探索範囲の各座標に対して前記ブロック切り出し位置応答値算出ステップによりブロック切り出し位置応答値を求め、各座標に対応するブロック切り出し位置応答値の中で最大のブロック切り出し位置応答値に対応する座標をブロック切り出し位置として検出するブロック切り出し位置検出ステップと、
前記ブロック切り出し位置検出ステップにより検出された前記ブロック切り出し位置を用いたブロック分割を、前記各周波数に対応したフィルタ処理済み画像群中の各画像に対して行い、各周波数に対応した各画像から、同じ一のブロック位置に対応する画素ブロック群の各画素ブロックについて、画素ブロック中の全画素の画素値の絶対値の和を求め、最大の絶対値和を取る画素ブロックに対応する周波数を少なくとも用いて、当該画素ブロックのブロック位置に対応する検出値行列の要素値を求める処理を各画素ブロックに対して行って検出値行列を求める検出値行列構成ステップと、
検出値行列から検出対象系列を求め、検出対象系列を逆拡散することにより検出電子透かし情報を求める透かし情報逆拡散ステップと
を有することを特徴とする電子透かし検出方法。
【請求項６】
前記透かし情報逆拡散ステップは、
前記検出値行列の要素の並びを０度、９０度、１８０度、２７０度回転して得られる４つの行列を生成し、９０度、２７０度回転して得られた各行列の全要素値の符号を反転する回転ステップと、
前記回転ステップにより得られた４つの行列の各々に対し、行列の一の要素位置が行列の所定の位置になるように要素をサイクリックシフトさせた行列を求める処理を各要素位置に対して行うことにより、変換済み検出値行列群を求める変換ステップと、
変換済み検出値行列群における各行列から検出対象系列群を求め、検出対象系列群における各検出対象系列を逆拡散して得られる情報群のうち、最も信頼度の高い情報を検出電子透かし情報として出力するステップと
を有する請求項５に記載の電子透かし検出方法。
【請求項７】
前記複数の周波数は、＋の符号及び−の符号に対応付けられた２種類の周波数であり、
前記検出値行列構成ステップは、＋の符号に対応する周波数に対応する画素ブロックの絶対値和から−の符号に対応する周波数に対応する画素ブロックの絶対値和を減算して得られた値を前記画素ブロックのブロック位置に対応する検出値行列の要素値とするステップを有する請求項５に記載の電子透かし検出方法。
【請求項８】
前記複数の周波数は、＋の符号及び−の符号に対応付けられた２種類の周波数であり、
前記検出値行列構成ステップは、２種類の周波数に対応する画素ブロックの絶対値和の差の絶対値に、大きいほうの絶対値和を取る画素ブロックに対応する周波数に対応する符号を付した値を前記画素ブロックのブロック位置に対応する検出値行列の要素値とするステップを有する請求項５に記載の電子透かし検出方法。
【請求項９】
請求項５ないし８のうちいずれか１項に記載の方法における各ステップをコンピュータに実行させるプログラム。
【請求項１０】
請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、画像や映像などのコンテンツに、別の副情報を人間に知覚されないように埋め込み、またこの副情報を読み取る技術である電子透かし技術に関するものである。今日、電子透かし技術は、コンテンツの著作権保護・管理システムや、コンテンツに関するサービス提供システムなどに用いられている。
【背景技術】
【０００２】  画像、映像や音声といったコンテンツの流通の際、コンテンツ識別・管理や著作権保護・管理、関連情報提供などの目的のため、コンテンツ内に知覚できないように別の情報を埋め込む電子透かし技術を用いる方法がある。一般に電子透かし検出対象画像は幾何変換を受けて幾何歪みが生じるものであり、このような幾何歪みに対する耐性を持つ電子透かし技術が求められている。【０００３】  上記の幾何変換を検出して補正を行なう従来技術として特許文献１に記載された技術がある。特許文献１に記載された技術では、埋め込み画像とは別に幾何変換補正用のパターンを埋め込み、そのパターンを用いて幾何変換を検出する。
【特許文献１】特開平１１−３５５５４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】  しかし、上記の従来技術では、幾何変換補正用のパターンと埋め込み画像とを別にしていることから、幾何変換補正用のパターンの信号と埋め込み画像の信号との間で干渉が生じるという問題がある。従って、幾何変換補正の精度を上げようとすればそのパターン信号を強めなければならないが、画質劣化を一定にしようとすれば必然的に埋め込み画像を弱めることになる。また、逆に埋め込み画像を強くすれば幾何変換補正用信号を弱くしなければならず、いずれにしても、埋め込み情報の検出精度は低下する。【０００５】  本発明は上記の点に鑑みてなされたものであり、従来のように電子透かし情報と別に幾何変換補正用の信号を独立に付加することなく幾何変換補正を可能とする電子透かし埋め込み技術及び電子透かし検出技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】  上記の課題は、画像にマクロブロックパターンを重畳することにより電子透かし情報を埋め込む電子透かし埋め込み装置であって、入力された電子透かし情報を拡散することにより、マクロブロックパターンにおける画素ブロック数に対応する長さの埋め込み系列を取得する電子透かし情報拡散手段と、一の画素ブロックの前記マクロブロックパターンにおける位置に対応する埋め込み系列の項値に応じて、予め定めた複数の周波数から少なくとも１つの周波数を選択し、選択された周波数に対応する波形パターンを前記一の画素ブロックにおける画素として設定する波形パターン設定手段と、前記波形パターン設定手段により各画素ブロックに対して波形パターンが設定されたマクロブロックパターンを埋め込み強度値で増幅し、入力された画像にタイル状に重畳するマクロブロックパターン重畳手段とを備えたことを特徴とする電子透かし埋め込み装置により解決できる。【０００７】  本発明におけるマクロブロックパターンは、埋め込み電子透かし情報に相当するとともに、検出時には幾何変換補正に用いることができるので、電子透かし情報と別に幾何変換補正用の信号を独立に付加することなく幾何変換補正が可能となる。【０００８】  前記波形パターン設定手段は、前記埋め込み系列の項値を量子化し、その量子化した値に応じて前記少なくとも１つの周波数を選択するようにしてもよいし、前記埋め込み系列の項値の符号に応じて前記少なくとも１つの周波数を選択するようにしてもよい。【０００９】  また、前記波形パターン設定手段は、前記マクロブロックパターン中の同一の周波数の波形パターンが設定された複数の画素ブロック間において、波形パターンの位相がマクロブロックパターン上で揃うように位相を変更しながら、各画素ブロックに対して波形パターンを設定するようにしてもよい。【００１０】  また、前記マクロブロックパターン重畳手段が、入力された画像に対してマクロブロックパターンを重畳する際、マクロブロックパターン中の画素ブロックに対し、同一周波数の波形パターンの位相がマクロブロックパターン重畳後の画像上で揃うように波形パターンの位相を変更しながら重畳を行うようにしてもよい。【００１１】  また、上記の課題は、複数の波形パターンからなる画素ブロックを並べて形成されたマクロブロックパターンを重畳した画像から電子透かし情報を検出する電子透かし検出装置であって、入力された画像を離散フーリエ変換して得られるパワースペクトル行列における少なくとも２つのピーク位置情報と、予め定めた基準位置情報とを用いて、入力画像の一次変換歪補正を行なう一次変換歪補正手段と、一次変換歪補正済み画像を、任意の位置から前記マクロブロックパターンのサイズのマクロブロックに分割し、分割して得られたマクロブロックを加算して加算マクロブロックを生成する加算マクロブロック生成手段と、加算マクロブロックに対し、予め定められた複数種類の周波数に対応する各畳み込みオペレータによる畳み込み処理を施して、各周波数に対応したフィルタ処理済み画像群を得る各周波数毎フィルタ処理済み画像群生成手段と、予め定められた探索範囲内の一の座標を設定する探索位置設定手段と、前記一の座標をブロック切り出し位置とみなして前記画素ブロックのサイズで画像を分割するブロック分割を前記各周波数に対応したフィルタ処理済み画像群中の各画像に対して行い、各周波数に対応した各画像から、同じ一のブロック位置に対応する画素ブロック群を取得し、当該一のブロック位置に対する前記画素ブロック群の各画素ブロックについて、画素ブロック中の全画素の画素値の絶対値の和を求めて画素絶対値和群を取得し、画素絶対値和群の中で最大の値を最大絶対値和として求める処理を、全てのブロック位置に対して行って得られる最大絶対値和の総和をブロック切り出し位置応答値として出力するブロック切り出し位置応答値算出手段と、前記探索位置設定手段により設定された前記探索範囲の各座標に対して前記ブロック切り出し位置応答値算出手段によりブロック切り出し位置応答値を求め、各座標に対応するブロック切り出し位置応答値の中で最大のブロック切り出し位置応答値に対応する座標をブロック切り出し位置として検出するブロック切り出し位置検出手段と、前記ブロック切り出し位置検出手段により検出された前記ブロック切り出し位置を用いたブロック分割を、前記各周波数に対応したフィルタ処理済み画像群中の各画像に対して行い、各周波数に対応した各画像から、同じ一のブロック位置に対応する画素ブロック群の各画素ブロックについて、画素ブロック中の全画素の画素値の絶対値の和を求め、最大の絶対値和を取る画素ブロックに対応する周波数を少なくとも用いて、当該画素ブロックのブロック位置に対応する検出値行列の要素値を求める処理を各画素ブロックに対して行って検出値行列を求める検出値行列構成手段と、検出値行列から検出対象系列を求め、検出対象系列を逆拡散することにより検出電子透かし情報を求める透かし情報逆拡散手段とを有することを特徴とする電子透かし検出装置によっても解決できる。【００１２】  本発明によれば、電子透かし情報として埋め込んだマクロブロックパターンを幾何変換補正に用いることができるようになる。【００１３】  前記透かし情報逆拡散手段は、前記検出値行列の要素の並びを０度、９０度、１８０度、２７０度回転して得られる４つの行列を生成し、９０度、２７０度回転して得られた各行列の全要素値の符号を反転する回転手段と、前記回転手段により得られた４つの行列の各々に対し、行列の一の要素位置が行列の所定の位置になるように要素をサイクリックシフトさせた行列を求める処理を各要素位置に対して行うことにより、変換済み検出値行列群を求める変換手段と、変換済み検出値行列群における各行列から検出対象系列群を求め、検出対象系列群における各検出対象系列を逆拡散して得られる情報群のうち、最も信頼度の高い情報を検出電子透かし情報として出力する手段とを備えて構成できる。【００１４】  また、前記電子透かし検出装置における前記複数の周波数は、＋の符号及び−の符号に対応付けられた２種類の周波数であり、前記検出値行列構成手段は、＋の符号に対応する周波数に対応する画素ブロックの絶対値和から−の符号に対応する周波数に対応する画素ブロックの絶対値和を減算して得られた値を前記画素ブロックのブロック位置に対応する検出値行列の要素値とするように構成できる。また、前記検出値行列構成手段は、２種類の周波数に対応する画素ブロックの絶対値和の差の絶対値に、大きいほうの絶対値和を取る画素ブロックに対応する周波数に対応する符号を付した値を前記画素ブロックのブロック位置に対応する検出値行列の要素値とするようにしてもよい。
【発明の効果】
【００１５】  本発明によれば、枠線などを用いずに画像に与えられたアフィン変換（一次変換＋平行移動）の補正をして電子透かしの検出が可能となる。また、従来のように電子透かし情報と別に幾何変換補正用の信号を独立に付加することなく、電子透かし情報を表すパターンが同時に幾何変換補正用の信号を兼ねることから、信号間の干渉の問題がなくなり、検出性能が向上するという効果がある。
【図面の簡単な説明】
【００１６】［図１］本発明の実施例における電子透かし埋め込み装置１０の構成図である。
［図２］電子透かし埋め込み装置１０の処理の流れを示す図である。
［図３］マクロブロックパターン生成部１１の構成図である。
［図４］マクロブロックパターン生成部１１の処理の流れを示す図である。
［図５］透かし情報拡散部１６の構成図である。
［図６］透かし情報拡散部１６の処理の流れを示す図である。
［図７］第１の例における周波数選定部１７の構成図である。
［図８］第１の例における周波数選定部１７の処理の流れを示す図である。
［図９］符号対応周波数データベース２７の内容を示す図である。
［図１０］第３の例における周波数選定部１７の構成図である。
［図１１］第３の例における周波数選定部１７の処理の流れを示す図である。
［図１２］埋め込み系列項量子化部２９の処理を説明する図である。
［図１３］量子化値対応周波数データベース３１の内容を示す図である。
［図１４］マクロブロックパターン設定部１９の処理を説明する図である。
［図１５］マクロブロックパターン生成部１１の処理を説明するための図である。
［図１６］マクロブロックパターンタイリング部１３の構成図である。
［図１７］マクロブロックパターンタイリング部１３の処理の流れを示す図である。
［図１８］マクロブロックパターンタイリング部１３の処理を説明するための図である。
［図１９］タイリング重畳部３４の処理を説明するための図である。
［図２０］本発明の実施例における電子透かし検出装置４０の構成図である。
［図２１］電子透かし検出装置４０の処理の流れを示す図である。
［図２２］一次変換歪補正部４１の構成図である。
［図２３］一次変換歪補正部４１の処理の流れを示す図である。
［図２４］一次変換歪補正部４１の処理の原理を説明するための図である。
［図２５］一次変換歪補正部４１の処理の原理を説明するための図である。
［図２６］離散フーリエ変換部４６の処理を説明するための図である。
［図２７］ピーク位置探索部４７の構成図である。
［図２８］ピーク位置探索部４７の処理の流れを示す図である。
［図２９］ピーク位置探索部４７の処理を説明するための図である。
［図３０］ピーク位置探索部４７の処理を説明するための図である。
［図３１］ピーク位置探索部４７の処理を説明するための図である。
［図３２］一次変換行列推定部４８の構成図である。
［図３３］一次変換行列推定部４８の処理の流れを示す図である。
［図３４］ピーク位置情報変換部５５の処理を説明するための図である。
［図３５］スペクトル空間上一次変換行列算出部５６の原理を説明するための図である。
［図３６］画像変換部４９の処理を説明するための図である。
［図３７］画像変換部４９の処理を説明するための図である。
［図３８］加算マクロブロック生成部４２の構成図である。
［図３９］加算マクロブロック生成部４２の処理の流れを示す図である。
［図４０］加算マクロブロック生成部４２の処理を説明するための図である。
［図４１］加算マクロブロック生成部４２の処理を説明するための図である。
［図４２］加算マクロブロックについて説明するための図である。
［図４３］検出値行列生成部４３の構成図である。
［図４４］検出値行列生成部４３の処理の流れを示す図である。
［図４５］各周波数に対応したフィルタ処理済み画像群生成部６２の処理の概要を示す図である。
［図４６］ブロック切り出し位置検出部６３の構成図である。。
［図４７］ブロック切り出し位置検出部６３の処理の流れを示す図である。
［図４８］探索位置情報について説明するための図である。
［図４９］ブロック切り出し位置応答値算出部６８の構成図である。
［図５０］ブロック切り出し位置応答値算出部６８の処理の流れを示す図である。。
［図５１］ブロック分割部７２の処理を説明するための図である。
［図５２］ブロック分割部７２の処理を説明するための図である。
［図５３］画素絶対値和計算部７３の処理を説明するための図である。
［図５４］ブロック切り出し位置応答値算出部６８の作用を説明するための図である。
［図５５］検出値行列構成部６４の構成図である。
［図５６］検出値行列構成部６４の処理の流れを示す図である。
［図５７］検出値行列構成部６４の処理を説明するための図である。
［図５８］検出値行列について説明するための図である。
［図５９］透かし情報逆拡散部４４の構成図である。
［図６０］透かし情報逆拡散部４４の処理の流れを示す図である。
［図６１］検出値行列変換部８２の構成図である。
［図６２］検出値行列変換部８２の処理の流れを示す図である。
［図６３］９０度毎回転部８９の処理を説明するための図である。
［図６４］９０度毎回転部８９の処理を説明するための図である。
［図６５］マクロブロック開始位置変換部９０の処理を説明するための図である。
［図６６］一次元化処理部８３の処理を説明するための図である。
［図６７］電子透かし有無指標値について説明するための図である。
【符号の説明】
【００１７】１０  電子透かし埋め込み装置
１１  マクロブロックパターン生成部
１２  画像入力部
１３  マクロブロックパターンタイリング部
１４  画像出力部
１６  透かし情報拡散部
１７  周波数選定部
１８  波形パターン生成部
１９  マクロブロックパターン設定部
２１  誤り訂正／検出符号化部
２２  擬似乱数生成器
２３  埋め込み系列生成部
２５  埋め込み系列項符号取得部
２６  選定部
２７  符号対応周波数データベース
２９  埋め込み系列項量子化部
３０  選定部
３１  量子化対応周波数データベース
３３  増幅部
３４  タイリング重畳部
４０  電子透かし検出装置
４１  一次変換歪補正部
４２  加算マクロブロック生成部
４３  検出値行列生成部
４４  透かし情報逆拡散部
４６  離散フーリエ変換部
４７  ピーク位置探索部
４８  一次変換行列推定部
４９  画像変換部
５１  最大ピーク位置探索部
５２  第２ピーク位置探索部
５３  ピーク位置情報出力部
５５  ピーク位置情報変換部
５６  スペクトル空間上一次変換行列算出部
５７  画像補正用一次変換行列算出部
５９  マクロブロック分割部
６０  マクロブロック生成部
６２  各周波数に対応したフィルタ処理済み画像群生成部
６３  ブロック切り出し位置検出部
６４  検出値行列構成部
６５  符号対応周波数データベース
６７  探索位置設定部
６８  ブロック切り出し位置応答値算出部
６９  ブロック切り出し位置応答値バッファ
７０  ブロック切り出し位置決定部
７２  ブロック分割部
７３  画素絶対値和計算部
７４  最大絶対値和判定部
７５  最大絶対値和加算部
７７  ブロック分割部
７８  画素絶対値和計算部
７９  最大エネルギー周波数判定部
８０  検出値行列要素値設定部
８２  検出値行列変換部
８３  一次元化処理部
８４  擬似乱数生成部
８５  逆拡散部
８６  復号対象情報選定部
８７  誤り訂正／検出復号部
８９  ９０度毎回転部
９０  マクロブロック開始位置変換部
【発明を実施するための最良の形態】
【００１８】  以下、図面を参照して本発明の実施例を説明する。本発明の実施例における電子透かし埋め込み装置の構成について図１に、処理の流れについて図２に示す。【００１９】  図１に示すように、本発明の実施例における電子透かし埋め込み装置１０は、マクロブロックパターン生成部１１、画像入力部１２、マクロブロックパターンタイリング部１３、画像出力部１４を有している。この構成における処理の流れを図２を参照して説明する。【００２０】  電子透かし埋め込み装置１０は、原画像と、埋め込み強度値（電子透かしの模様を画像にどれだけ強く重畳するかを指定するパラメータ。大きいほど埋め込み後の画質は劣化するが、電子透かしの検出が安定する）と、原画像中に埋め込む情報である透かし情報を入力とする（ステップ１）。【００２１】  マクロブロックパターン生成部１１は、透かし情報を拡散することにより、埋め込み系列を得て、埋め込み系列の項の値等に応じた周波数パターンを並べることにより、画像パターンであるマクロブロックパターンを生成する（ステップ２）。【００２２】  また、マクロブロックパターンタイリング部１３は、画像入力部１２において取得された原画像に対して、マクロブロックパターンをタイル状に重畳してタイリング済み画像データを得る（ステップ３）。そして、画像出力部１４において、タイリング済み画像データを電子透かし埋め込み済み画像として出力する（ステップ４）。【００２３】  以下、各部の処理をより詳細に説明する。【００２４】  本発明の実施例における電子透かし埋め込み装置１０の上記マクロブロックパターン生成部１１の構成を図３に、処理の流れを図４に示す。図３に示すように、マクロブロックパターン生成部１１は、透かし情報拡散部１６、周波数選定部１７、波形パターン生成部１８、マクロブロックパターン設定部１９を有している。図４のフローチャートを参照して、マクロブロックパターン生成部１１の処理の流れを説明する。【００２５】  マクロブロックパターン生成部１１は透かし情報を入力とし（ステップ２１）、まず透かし情報拡散部１６が、透かし情報を拡散して埋め込み系列｛ｅｉ｝を得る（ステップ２２）。【００２６】  透かし情報拡散部１６についてより詳細に説明する。【００２７】  図５に透かし情報拡散部１６の構成を示し、図６にその処理の流れを示す。透かし情報拡散部１６は、誤り訂正／検出符号化部２１、擬似乱数生成器２２、及び埋め込み系列生成部２３を有している。【００２８】  図６に示すように、まず透かし情報が入力され（ステップ３１）、誤り訂正／検出符号化部２１において透かし情報を誤り訂正／検出符号化する（ステップ３２）。誤り訂正／検出符号化方法としてはＢＣＨ符号やＲｅｅｄ  Ｓｏｌｏｍｏｎ符号など、どのようなものを用いても良い。次に埋め込み系列生成部２３は、擬似乱数生成器２２により生成される擬似乱数列を用いて、誤り訂正／検出符号化された透かし情報を長さｍ×ｎ（マクロブロックのサイズに依存する。後述するように本実施例ではｎ×ｎであるが、ここではより一般的にｍ×ｎについて説明している）の系列である埋め込み系列に拡散し（ステップ３３）、その埋め込み系列を出力する（ステップ３４）。なお、擬似乱数生成器２２における擬似乱数生成の初期値を、透かしの鍵パラメータとして外部から入力されるパラメータとしても良い。このようにすることで、異なる鍵パラメータで独立な電子透かし埋め込みを実現したり、埋め込みアルゴリズムの推測を困難にするなどの効果が得られる。【００２９】  埋め込み系列生成部２３における透かし情報の具体的な拡散方法の例（（Ａ）〜（Ｃ））を以下に示す：
（Ａ）誤り訂正／検出符号化された透かし情報（Ｓビットとする）を｛ｗｉ｝（ｉ＝０〜Ｓ−１）、擬似乱数列を｛ｒｉ｝（ｉ＝０〜ｍｎ−１（画素ブロックの総数））とした時に、埋め込み系列｛ｅｉ｝（ｉ＝０〜ｍｎ−１）を以下のようにして求める。
0004303243.tif 000002
ただしｗｉ＝１ｏｒ−１（誤り訂正／検出符号化された透かし情報のｉ番目のビット値が１ならば１、０ならば−１）とし、ｒｉ＝１ｏｒ−１の乱数列とする。またｘ％ｙはｘをｙで割った際の剰余を表す。
（Ｂ）誤り訂正／検出符号化された透かし情報（Ｓビットとする）を｛ｗｉ｝（ｉ＝０〜Ｓ−１）、擬似乱数列を２種類生成しそれぞれ｛ｒ１ｉ｝（ｉ＝０〜ｍｎ−１）、｛ｒ２ｉ｝（ｉ＝０〜ｍｎ−１）とした時に、まず｛ｒ１ｉ｝を用いて置換のための配列を生成する。例えば【００３０】
0004303243.tif 000003
0004303243.tif 000004
を表す配列｛ｐｉ｝（ｉ＝０〜ｍｎ−１）を以下のようにして決定する。ただしｒ１ｉは０〜ｍｎ−１以上の値をランダムに取るものと仮定する。
0004303243.tif 000005
次に、埋め込み系列｛ｅｉ｝（ｉ＝０〜ｍｎ−１）を以下のようにして求める。
0004303243.tif 000006
ただしｗｉ＝１ｏｒ−１（誤り訂正／検出符号化された透かし情報のｉ番目のビット値が１ならば１、
０ならば−１）とし、ｒ２ｉ＝１ｏｒ−１の乱数列とする。またｘ％ｙはｘをｙで割った際の剰余を表す。上記のように、｛ｒ１ｉ｝は｛ｐｉ｝を生成するための擬似乱数列であり、｛ｒ２ｉ｝は｛ｗｉ｝の拡散を行うための擬似乱数列である。
（Ｃ）誤り訂正／検出符号化された透かし情報（Ｓビットとする）を｛ｗｉ｝
（ｉ＝０〜Ｓ−１）、擬似乱数列を｛ｒｉ｝（ｉ＝０〜ｍｎ−１）とした時に、埋め込み系列｛ｅｉ｝（ｉ＝０〜ｍｎ−１）を以下のようにして求める。
0004303243.tif 000007
ただしｗｉ＝１ｏｒ−１（誤り訂正／検出符号化された透かし情報のｉ番目のビット値が１ならば１、０ならば−１）とし、ｒｉ＝１ｏｒ−１の乱数列とする。またｘ％ｙはｘをｙで割った際の剰余を表す。
なお、上記の例では２値化乱数系列を拡散に用いたが、別の乱数系列、例えばガウス分布に従う乱数系列などを用いて拡散を行っても構わない。【００３１】  以上透かし情報拡散部１６について説明したが、上述したように、本実施例ではマクロブロックパターンはｎ×ｎ個のブロックから構成されるものとするので、埋め込み系列の系列長はｎ２となる。【００３２】  図４のフローにおいて、次に、マクロブロックパターンをブロック毎に設定するため、埋め込み系列の項番を指定するカウンタｉを０に設定し（ステップ２３）、周波数選定部１７が、埋め込み系列のｉ番目の項ｅｉの値等に対応する周波数を選定する（ステップ２４）。次に、波形パターン生成部１８は、選定された周波数に対応した波形パターンを生成する（ステップ２５）。波形パターンは後で述べるブロックサイズの画素行列である。【００３３】  以下、周波数選定部１７及び波形パターン生成部１８の処理についてより詳細に説明する。以下、３つの処理方法の例について説明する。【００３４】  （１）まず、第１の例における周波数選定部１７及び波形パターン生成部１８について詳細に説明する。【００３５】  周波数選定部１７の構成を図７に、処理の流れを図８に示す。図７に示すように、周波数選定部１７は、埋め込み系列項符号取得部２５と選定部２６と符号対応周波数データベース２７を有している。【００３６】  図８に示すように、周波数選定部１７は、埋め込み系列項値を入力とし（ステップ４１）、埋め込み系列項符号取得部２５は埋め込み系列項値の符号を得る（ステップ４２）。符号としては（＋、−、０）の三値を取りうる。次に選定部２６が、埋め込み系列項値符号に対応する周波数を、符号対応周波数データベース２７から検索し、選定された周波数として出力する（ステップ４３）。符号対応周波数データベース２７の構成を図９に示す。符号対応周波数データベース２７には、埋め込み系列項符号取得部２５の各々の出力に対して、対応する周波数が記録・蓄積されている。一つの符号に対して対応する周波数が一つでなくとも良く、図９の符号“−”の場合のように、複数の周波数の組が対応していても良い。【００３７】  なお、本願明細書全体及び特許請求の範囲において、“周波数”の用語の意味は、特に区別して用いる場合を除き、単一の周波数のみならず、上記の符号“−”の場合のように、１つの符号（もしくは０、もしくは量子化値）に対応する複数の周波数も含むものとする。【００３８】  また、ここで周波数とは２次元波形パターンを表す２次元周波数であって、ブロックサイズを基準とした相対的な周波数を表すものとする。例えばＸ×Ｙ画素のブロックサイズに対して、ｘ方向で２波長の波形を表す周波数と、２Ｘ×２Ｙ画素のブロックサイズに対して、ｘ方向に２波長の波形を表す周波数は同じ値となるように画素サイズで正規化されているものとする。第１の例では、波形パターン生成部１８は、選定された周波数に対応する波形パターンを生成する。波形パターン生成部２５が生成する波形パターンは、ブロックと同じ大きさの２次元パターンとする。また、選定された周波数が複数ある場合は、それぞれの波形パターンを加算し、得られたパターンのエネルギーを周波数一つ��場合と同じとなるように振幅を正規化したものを波形パターンとする。【００３９】  （２）第２の例では、波形パターン生成部１８が波形パターンの振幅を、埋め込み系列項値の絶対値で増幅する点が第１の例と異なる。【００４０】  （３）次に、第３の例における周波数選定部１７及び波形パターン生成部１８について詳細に説明する。【００４１】  周波数選定部１７の構成を図１０に、処理の流れを図１１に示す。図１０に示すように、周波数選定部１７は、埋め込み系列項量子化部２９と選定部３０と量子化対応周波数データベース３１を有している。【００４２】  図１１に示すように、周波数選定部１７は、埋め込み系列項値を入力とし（ステップ５１）、埋め込み系列項量子化部２９が埋め込み系列項値を量子化し、量子化埋め込み系列項値を得る（ステップ５２）。そして、選定部３０が、量子化埋め込み系列項値に対応する周波数を、量子化値対応周波数データベース３１から検索し、選定された周波数を得て（ステップ５３）、それを出力する（ステップ５４）。【００４３】  埋め込み系列項量子化部２９による量子化の方法としては、図１２に示すような方法がある。図１２に示す（ａ）〜（ｃ）の量子化はそれぞれ以下のような演算により行われる：
（ａ）二値化
ｘを埋め込み系列項値とした時に、
ｘ＜０→  −１
ｘ＞＝０→  １
のように二値化する。
（ｂ）三値化
ｘを埋め込み系列項値とした時に
ｘ＜０→  −１
ｘ＝０→  ０
ｘ＞０→  １
のように三値化する。【００４４】  （ｃ）ｎ値化
ｘを埋め込み系列項値とした時に、【００４５】
0004303243.tif 000008
のようにｎ値化する。
なお、（ｃ）のように等幅量子化ではなく、不等幅量子化を用いても構わない。【００４６】  上記のステップ５３において選定部３０が参照する量子化値対応周波数データベース３１の構成を図１３に示す。なお、この例は上記の三値化の場合の例である。図１３に示すように、量子化値対応周波数データベース３１には、埋め込み系列項量子化部２９の各々の出力に対して、対応する周波数が予め記録・蓄積されている。この際、一つの量子化値に対して対応する周波数が一つでなくとも良く、図１３の量子化値０の場合のように、複数の周波数の組が対応していても良い。【００４７】  波形パターン生成部１８については第１の例もしくは第２の例と同様である。即ち、選択された周波数パターンの振幅をそのまま用いるか埋め込み系列項値の絶対値で増幅する。【００４８】  以上、周波数選定部１７、波形パターン生成部１８の例について説明したが、以下の説明において本実施例では、第１の例に基づくものとし、また、選定される周波数は２種類（ｆ０、ｆ１）であるものとする。そして、２種類の波形パターンの間には、一方を９０°回転したパターンがもう一方になるようなものとする。【００４９】  図４のフローにおいて、次に、マクロブロックパターン設定部１９は、予め用意されたマクロブロックパターンのバッファに対し、上記埋め込み系列の項番ｉに対応するブロック位置の画素ブロックを、上記波形パターンで置き換える（ステップ２６）。マクロブロックパターンは図１４に示すように、Ｎ×Ｎ画素の画素配列であり、縦横ｎ個のブロックから構成される。マクロブロックパターン設定部１９においては、例えば横ブロック位置ｍ０、縦ブロック位置ｎ０に対してｉ＝ｍ０＋ｎ０×ｎ等のようにして、埋め込み系列の項番ｉとブロック位置（ｍ０，ｎ０）を１対１対応させて、対応するブロック位置の画素ブロックを、対応する波形パターンで置き換える。【００５０】  埋め込み系列の項番を指定するカウンタｉをインクリメントさせ（ステップ２７）、全ての項について上記周波数選定部１７からマクロブロックパターン設定部１９までの処理を繰り返すことによって（ステップ２８）、マクロブロックパターンは図１５のように異なる周波数パターンを持つブロックを配置したものとして生成され、最後に全てのブロックを設定し終えたマクロブロックパターンを出力する（ステップ２９）。【００５１】  上記のマクロブロックパターン生成部１１の中のマクロブロックパターンタイリング部１３についてより詳細に説明する。本実施例におけるマクロブロックパターンタイリング部１３の構成を図１６に、処理の流れを図１７に示す。【００５２】  図１６に示すように、マクロブロックパターンタイリング部１３は、増幅部３３とタイリング重畳部３４を有している。この構成における処理の流れを図１７を参照して以下説明する。【００５３】  マクロブロックパターンタイリング部１３は、波形パターン生成部１１により生成されたマクロブロックパターン、及び埋め込み強度値、原画像を入力とする（ステップ６１）。増幅部３３が、マクロブロックパターンの振幅を埋め込み強度値を用いて増幅して（ステップ６２）、増幅されたマクロブロックパターンを出力する。増幅された��クロブロックパターンは、タイリング重畳部に入力される。【００５４】  次にタイリング重畳部３４は、原画像に対して、増幅されたマクロブロックパターンを図１８に示すようにタイル状に重畳する（ステップ６３）。この際、タイリングの開始位置は原画像の左上とは限らず、任意の位置からタイリングしても良い。また、原画像データの端などで、タイリングするマクロブロックパターンがはみ出してしまう場合は、はみ出した部分は切り捨てて、原画像が全てマクロブロックパターンで埋め尽くされるようにする。さらに、マクロブロックパターンを原画像に重畳する際、マクロブロックを構成するブロック波形パターンについて、図１９のように、同一の周波数を持つ波形パターンの原画像上での位相が揃うように、タイリング中のブロック毎に波形パターンの位相を変更しても良い。ここで、同一周波数の波形パターンの位相を揃えるとは、図１９のように、原画像と同じサイズの波形パターンの各ブロック位置の波形パターンが、原画像上の該当する位置においてタイリング中のブロックの波形パターンとなるようすることである。このようにすることで、後述する検出時の一次変換歪補正処理において、変換パラメータを推定するためのパワースペクトルのピークをより強めることができ、耐性の向上に寄与する。なお、ブロックサイズが波形パターンの波長の整数倍となっている場合については、特にブロック内の波形パターンの位相を変更せずとも、タイリング後の原画像上の波形パターンの位相が揃うため、上記のような処理を行う必要はない。【００５５】  マクロブロックパターンがタイリングされた原画像は、タイリング済み画像として、マクロブロックパターンタイリング部１３から出力される（ステップ６４）。そして、電子透かし埋め込み装置１０の画像出力部１４が、そのタイリング済み画像を電子透かし埋め込み済み画像として出力する。【００５６】  次に、上記のようにして生成された電子透かし埋め込み済み画像から電子透かしの検出を行う電子透かし検出装置４０について説明する。【００５７】  本実施例における電子透かし検出装置４０の構成を図２０に示し、処理の流れを図２１に示す。【００５８】  図２０に示すように、本実施例の電子透かし検出装置４０は、一次変換歪補正部４１、加算マクロブロック生成部４２、検出値行列生成部４３、透かし情報逆拡散部４４を有している。この構成を有する電子透かし検出装置４０における処理の流れを図２１を参照して説明する。【００５９】  電子透かし検出装置４０は、検出対象画像を入力とする（ステップ７１）。そしてまず一次変換補正部４１が、検出対象画像に施された一次変換のパラメータを推定し、逆変換により補正することで一次変換補正済み検出対象画像データを得る（ステップ７２）。【００６０】  次に加算マクロブロック生成部４２が、一次変換補正済み検出対象画像をマクロブロックの大きさに分割し、分割された領域を加算して加算マクロブロックを得る（ステップ７３）。次に検出値行列生成部４３が、加算マクロブロック中のブロック切り出し位置を探索し（ステップ７４）、ブロック切り出し位置に応じた検出値行列を生成する（ステップ７５）。次に透かし情報逆拡散部４４が、検出値行列を用いて、９０度毎回転・マクロブロック先頭位置を探索しながら逆拡散処理を行い、検出透かし情報を得て出力する（ステップ７６）。【００６１】  なお、上記の処理において、検出対象画像を入力したのち、検出対象画像を、予め定めた画素数の画像サイズとなるように拡大／縮小変換し、画像サイズを正規化したサイズ正規化検出対象画像を生成し、以降の処理の入力としてもよい。また、検出耐性向上を図るために、一次変換歪補正部４１もしくは加算マクロブロック生成部４２の前に前処理フィルタ部を設けて、検出対象画像もしくは一次変換歪補正済み検出対象画像に対してそれぞれ前処理フィルタ処理を施しても良い。また、検出対象画像と一次変換歪補正済み検出対象画像の各々に前処理フィルタ処理を施しても良い。【００６２】  前処理フィルタ処理について説明する。前処理フィルタ処理に用いるフィルタとして、埋め込みに用いた周波数パターンの周波数を通過させる帯域通過フィルタ（バンドパスフィルタ）を用いることが望ましい。帯域通過フィルタによる帯域制限処理により、低周波数成分が低減される。原画像の絵柄の周波数は低周波数成分が多いので、周波数パターンに対する原画像の絵柄の影響を軽減できる。なお、前処理フィルタ処理部として、画像信号データの波形を微分する微分回路を用いることもできる。フィルタ処理加えて、クリッピング処理を行うことにより検出性能を更に改善できる。クリッピング処理とは、例えばフィルタ処理済みの画像の信号波形のうち、予め定めた上限値と下限値を超える信号部分に丸め処理を施すことである。この結果、微弱な振幅の信号が相対的に強まることになる。従って、フィルタ処理済みの信号のレベルを設定値以内に抑えることができ、周波数パターンの検出感度を向上させることができる。【００６３】  次に、上記の電子透かし検出装置４０の各部についてより詳細に説明する。【００６４】  本実施例における一次変換歪補正部４１の構成を図２２に、処理の流れを図２３に示す。図２２に示すように、一次変換歪補正部４１は、離散フーリエ変換部４６、ピーク位置探索部４７、一次変換行列推定部４８、画像変換部４９を有している。図２３を参照して一次変換歪補正部４１の処理の流れを説明する。【００６５】  一次変換歪補正部４１は、検出対象画像を入力とし（ステップ８１）、まず離散フーリエ変換部４６が検出対象画像を２次元離散フーリエ変換し、パワースペクトル行列を得る（ステップ８２）。次にピーク位置探索部４７が、パワースペクトル行列の中で大きなピーク値をとる要素の位置を２点探索し、この２つの要素位置をピーク位置情報として取得する（ステップ８３）。【００６６】  次に一次変換行列推定部４８が、ピーク位置情報と、予め定められた基準位置とから、基準位置がピーク位置に変換される時の一次変換行列を算出し（ステップ８４）、さらにスペクトル空間上での一次変換行列を画素空間上での一次変換行列に変換して得られる行列のさらに逆行列を、画像補正用一次変換行列として出力する（ステップ８５）。最後に画像変換部４９が、画像補正用一次変換行列で表される画像の一次変換を、検出対象画像に対して施すことにより、検出対象画像に施されていた一次変換を補正し、一次変換歪補正済み検出対象画像データを得て出力する（ステップ８６）。【００６７】  一次変換歪補正部４６が検出対象画像における一次変換歪を補正する処理の原理を以下に説明する。【００６８】  まず本実施例の電子透かし埋め込み装置１０を用いて得られる画像をそのまま検出対象画像として入力した場合、図２４に示すように、検出対象画像を離散フーリエ変換して得られるパワースペクトルは、ブロックに重畳された２種類の周波数パターンに対応する周波数位置に大きなピークを持つ。この理由は、ブロック単位という局所領域では該ブロックに重畳された周波数パターンを表す周波数がピークを持つが、２種類の周波数パターンが、ほぼ等しい面積（拡散処理による）で検出対象画像を埋めつくしていることと、画像全体に対する離散フーリエ変換で得られるパワースペクトルの周波数位置は周波数パターンの局在性によらない、ということによる。【００６９】  次に図２５に示すように、検出対象画像に一次変換が施されている場合について考える。この場合は一般的に良く知られた事実として、検出対象画像に施された一次変換のうち、回転成分についてはスペクトル空間上での同じ角度の回転として反映され、スケーリング成分についてはスペクトル空間上での逆スケーリング成分として反映される。例えば画像空間上で角度θだけ回転し、かつｓ倍のスケーリングを行うような一次変換が施されると、スペクトル空間上では角度θの回転と１／ｓ倍のスケーリングを行うような一次変換が対応して引き起こされる。また、パワースペクトルは画像の平行移動量に対して不変であるという特徴を持つ。以上のことから図２５のように検出対象画像に一次変換が施されている場合、図２４のパワースペクトル行列に、当該一次変換に対応する一次変換が施され、そのため２種類の周波数パターンに対応するピーク位置も変換によって移動する。【００７０】  よって、図２５のように一次変換が施された検出対象画像から得られるパワースペクトル行列内の２つのピーク位置を検出し、図２４のように、歪のない状態で得られるパワースペクトル行列上のピーク位置を基準位置として、基準位置が、検出した２つのピーク位置に変換されるような一次変換を算出すれば、対応する画素空間上での一次変換も定まることになり、一次変換パラメータの推定と歪みの補正を行うことが可能となる。この際、画像のパワースペクトル配置が原点（直流成分位置）に対して点対称に並ぶこと、および２つのピーク点を見分ける方法がないこと、の２つの理由により、９０度毎回転についての不確定性が残る。即ち一次変換歪補正を行って得られる一次変換歪補正済み検出対象画像は、もともとの電子透かし埋め込み済み画像の状態と比べ、０度、９０度、１８０度、２７０度回転のいずれかの状態となるが、これは後の処理で９０度毎回転対応することで解決する。また、画像の鏡像変換の不確定性もあるが、これは後に述べる位置変換行列推定部以降の処理を２重に行うことで解決される。【００７１】  次に、本実施例の一次変換歪補正部４１における各部の処理を詳細に説明する。【００７２】  本実施例における離散フーリエ変換部４６の処理を図２６に示す。離散フーリエ変換部４６は検出対象画像を入力とし��、検出対象画像を離散フーリエ変換して得られるパワースペクトル行列を出力する。離散フーリエ変換のサイズとしては、検出対象画像のサイズそのものでも良いし、処理の高速化のためＦＦＴ（高速離散フーリエ変換）などを用いるために縦横のサイズが２の冪となるように設定してもよい。検出対象画像のサイズと離散フーリエ変換のサイズが異なる場合は、図２６のように、画像中心から離散フーリエ変換の対象となる画素をとり、離散フーリエ変換のサイズからはみ出した部分は切り捨て、離散フーリエ変換の必要サイズに満たない場合は画素値０で埋める、あるいは離散フーリエ変換のサイズ中の検出対象画像の部分領域の平均画素値で埋める、などとする。さらに高速化のため、検出対象画像を予め定まった倍率、例えば縦横１／２サイズに縮小してから離散フーリエ変換してもよい。このようにして得られるパワースペクトル行列の中には、上記理由により４点（対称性を考慮すれば独立な２点）の大きなピーク値が含まれている。【００７３】  本実施例におけるピーク位置探索部４７の構成を図２７に、その処理の流れを図２８に示す。図２７に示すように、本実施例のピーク位置探索部４７は、最大ピーク位置探索部５１、第２ピーク位置探索部５２、ピーク位置情報出力部５３を有している。以下、図２８を参照して処理の流れを説明する。【００７４】  ピーク位置探索部４７はパワースペクトル行列を入力とし（ステップ９１）、まず最大ピーク位置探索部５１が、図２９に示すように、離散フーリエ変換部４６により得られたパワースペクトル行列中の予め定めた帯域内で、最大のピーク値を取る周波数位置を探索により検出する（ステップ９２）。ここで帯域の定め方としては、低周波帯域を含まないようにして選択する。低周波を避ける理由は、原画像自体のエネルギーが低周波に集中するため、最大ピーク位置を誤検出する可能性があるためである。また、パワースペクトル行列の対称性から、上半分帯域のみ探索すれば十分である。【００７５】  なお、最大ピーク位置を探索する際、単純に予め定めた帯域中で最大値を取る周波数位置を検出した最大ピーク位置としてもよいし、例えば図３０のようにインパルス性（即ちピーク性）のある大きなパワーを取る周波数位置を見つけるために、ラプラシアンフィルタのような畳み込みオペレータの応答値が最大となる周波数位置を最大ピーク位置としても良い。さらに畳み込みオペレータを用いる場合は、一点のみからなるインパルスを検出するような（例えば３×３のラプラシアンフィルタ）ものより、多少の裾野の広がりを持つピークを検出できるように、例えば図３０のようにスパースな畳み込みオペレータなどを用いる方が良い。これはパワースペクトル行列中に現れるピークが、検出対象画像の若干の非線形歪みなどにより若干広がる可能性があることによる。最大ピーク位置探索部５１は、上記のようにして最大ピーク位置を検出して、これを最大ピーク位置情報として出力する。【００７６】  次に第２ピーク位置探索部５２が、図３１に示すように、最大ピーク位置情報で表されるパワースペクトル上の位置を９０度回転した点を中心とした予め定めたサイズの近傍領域である第２ピーク位置探索領域中で、最大ピークを取る周波���位置を探索し、検出した周波数位置を第２ピーク位置情報として出力する（ステップ９３）。ここで第２ピーク位置探索領域を、最大ピーク位置を９０度回転した点の近傍としているのは、電子透かし埋め込みに利用する周波数の波形パターンが、一方を９０度回転したパターンがもう一方になるようなもの２種類であることによる。【００７７】  また単純に最大ピーク位置を９０度回転した点を第２ピーク位置とするのではなく近傍領域を探索する理由は、検出対象画像に施された一次変換として、アスペクト比変更や、せん断といった変換成分があるため、最大ピーク位置を９０度回転した点からずれた位置にピーク位置がずれることが考えられるためである。第２ピーク位置探索領域のサイズは、一次変換歪補正部４１で対応するアスペクト比変更・せん断変換の程度によって予め定める。また、第２ピーク位置を探索する際には、最大ピーク位置探索部５１と同様に、第２ピーク位置探索領域中で最大値を取る周波数位置を検出した第２ピーク位置としても良いし、図３０のような畳み込みオペレータの応答値が最大となる周波数位置を第２ピーク位置としても良い。【００７８】  以上のようにして最大ピーク位置情報、第２ピーク位置情報を取得するが、別の方法として、図２９で示される予め定めた帯域中で最大のピーク値を取る位置を最大ピーク位置、２番目に大きなピーク値を取る点を第２ピーク値としても良い。【００７９】  最後にピーク位置情報出力部５３が、最大ピーク位置情報と第２ピーク位置情報を組にして、ピーク位置情報として出力する（ステップ９４）。【００８０】  続いて、一次変換歪補正部４１の中の一次変換行列推定部４８について詳細に説明する。本実施例における一次変換行列推定部４８の構成を図３２に、処理の流れを図３３に示す。図３２に示すように、一次変換行列推定部４８は、ピーク位置情報変換部５５、スペクトル空間上一次変換行列算出部５６、画像補正用一次変換行列算出部５７を有している。図３３を参照して一次変換行列推定部４８における処理の流れを説明する。【００８１】  一次変換行列推定部４８は、ピーク位置探索部４７により得られたピーク位置情報を入力とし（ステップ１０１）、まずピーク位置情報変換部５５においてピーク位置情報を変換し、変換済みピーク位置情報を得る（ステップ１０２）。そしてスペクトル空間上一次変換行列算出部５６が、予め保持している基準位置情報と、変換済みピーク位置情報を用いてスペクトル空間上一次変換行列を算出する（ステップ１０３）。最後に、画像補正用一次変換行列算出部５７が、スペクトル空間上一次変換行列を画素空間上一次変換行列に変換し、結果を画像補正用一次変換行列として出力する（ステップ１０４）。各部の処理を以下詳細に説明する。【００８２】  図３４にピーク位置情報変換部５５の処理内容を示す。ピーク位置情報変換部５５はピーク位置情報を入力とし、ピーク位置情報中の最大ピーク位置情報および第２ピーク位置情報について、それぞれの位置情報が表すパワースペクトル上の位置が、第１象限または第２象限にあるかを判定し、第１象限および第２象限になかった場合、点対称の位置を新たな位置とするように位置情報を変換する。図３４では第２ピー���位置が第１象限もしくは第２象限にないため、ピーク位置情報中の第２ピーク位置の点対称となる点を新たな第２ピーク位置とする。【００８３】  次に、どちらも第１象限または第２象限に存在する最大ピーク位置と第２ピーク位置について、そのｘ方向座標値が小さい、すなわちパワースペクトル行列上で左側に位置する方をピーク位置Ａ、もう一方をピーク位置Ｂと名称を変え、ピーク位置Ａを表すピーク位置情報Ａとピーク位置Ｂを表すピーク位置情報Ｂを組にして変換ピーク位置情報として出力する。なお、ピーク位置Ａとピーク位置Ｂのとり方を逆にした変換ピーク位置情報も生成し、以降の処理をすべて２重に行うことにより、画像の鏡像変換対応も実現できる。【００８４】  次にスペクトル空間上一次変換行列算出部５６の処理について図３５を用いて説明する。スペクトル空間上一次変換行列算出部５６は、電子透かし埋め込み直後の状態で得られるピーク位置、即ち埋め込みに用いた２種類の周波数パターンに対応する２つの周波数位置を、予め基準位置情報として保持している。基準位置情報のうち、ｘ方向座標値が小さい、すなわちパワースペクトル行列上で左側に位置する方を基準位置ａ、もう一方を基準位置ｂとする。このときスペクトル空間上位置変換行列は、図３５に示すように、基準位置ａをピーク位置Ａに、基準位置ｂをピーク位置Ｂに移す一次変換であり、以下の式によって算出される：
パワースペクトル行列の直流成分を原点とする２次元座標系で
基準位置ａ：（ａｘ，ａｙ）
基準位置ｂ：（ｂｘ，ｂｙ）
ピーク位置Ａ：（Ａｘ，Ａｙ）
ピーク位置Ｂ：（Ｂｘ，Ｂｙ）
とし、スペクトル空間上一次変換行列を【００８５】
0004303243.tif 000009
0004303243.tif 000010
とすれば【００８６】
0004303243.tif 000011
となるので、これを解いて【００８７】
0004303243.tif 000012
となる。【００８８】  次に画像補正用一次変換行列算出部５７の処理内容を説明する。画像補正用一次変換行列算出部５７は、スペクトル空間上一次変換行列を入力とする。図２５に示したとおり、画素空間上の一次変換とスペクトル空間上の一次変換の関係は、
＊スケーリング成分は逆変換
＊回転成分は同じ
となっている。この性質から、スペクトル空間上一次変換行列に対応する画素空間上一次変換行列を求める。
スペクトル空間上一次変換行列を【００８９】
0004303243.tif 000013
0004303243.tif 000014
とすると、対応する画素空間上一次変換行列は【００９０】
0004303243.tif 000015
となる。【００９１】  最終的に求めたい画像補正用一次変換行列は、上記画素空間上一次変換行列の逆行列であるので、【００９２】
0004303243.tif 000016
となり、スペクトル空間上一次変換行列の転置行列を画像補正用一次変換行列として出力すれば良い。【００９３】  次に、本実施例における電子透かし検出装置４０の中の一次変換歪補正部４１の中の画像変換部４９の処理の内容を図３６、３７を用いて説明する。【００９４】  画像変換部４９は、検出対象画像と、一次変換行列推定部４８で生成された画像補正用一次変換行列を入力として、検出対象画像を一次変換して得られる画像を一次変換歪補正済み検出対象画像として出力する。【００９５】  この際、図３６に示すように、一次変換によって検出対象画像外の領域ができる場合は、画素値０で埋める、または検出対象画像の平均画素値で埋めるなどの処理をする。また、図３７に示すように、一次変換歪補正済み検出対象画像の画像サイズを予め定めている場合については、固定サイズからはみ出した検出対象画像の部分は切り捨て、検出対象画像外の領域ができる場合は、画素値０で埋める、または検出対象画像の部分領域の平均画素値で埋めるなどをする。【００９６】  次に、電子透かし検出装置４０における加算マクロブロック生成部４２について説明する。本実施例における加算マクロブロック生成部４２の構成を図３８に、処理の流れを図３９に示す。【００９７】  図３８に示すように、加算マクロブロック生成部４２は、マクロブロック分割部５９とマクロブロック生成部６０を有している。図３９を参照して加算マクロブロック生成部４２における処理の流れを説明する。【００９８】  加算マクロブロック生成部４２は、一次変換歪補正部４１から出力された一次変換歪補正済み検出対象画像を入力とし（ステップ１１１）、まず図４０のようにして、一次変換歪補正済み検出対象画像の任意の位置から、予め定めたサイズ（埋め込み時と同じ値）のマクロブロックに分割してマクロブロック群を得る（ステップ１１２）。この際に画像の端などでマクロブロックに満たない画素領域からマクロブロックを得る場合には、画素値０で埋める、または検出対象画像の部分領域の平均画素値で埋めるなどをする。【００９９】  次にマクロブロック加算部６０は、図４１のようにマクロブロック群中の全てのマクロブロックを加算して加算マクロブロックを生成して、これを出力する（ステップ１１３）。【０１００】  一次変換歪を補正して得られる一次変換歪補正済み検出対象画像は、埋め込み直後の電子透かし埋め込み済み画像と比較すると、同じスケール、（９０度ごとの回転角度や鏡像変換の不確定性を同一視して）同じ向きであり、平行移動を伴っている状態であると考えることができる。すると、埋め込み直後の電子透かし埋め込み済み画像にタイリングされているマクロブロックパターンと同じサイズのマクロブロックで分割して得られるマクロブロック群中の各マクロブロックは、それぞれマクロブロックパターンが同じ量平行移動した状態で含まれた画素領域となる。そのためマクロブロックの総和である加算マクロブロックには、図４２のように位置のずれたマクロブロックパターンが加算回数分強まった形で集積されることになる。加算マクロブロックには埋め込み時のマクロブロックパターンがサイクリックシフトした形で含まれていることから、加算マクロブロック中で平��移動の対応をして、埋め込み時のマクロブロックパターンの先頭位置が見つかれば、埋め込まれた透かし情報を検出することが可能となる。このような観点から以下で説明する処理が行われることになる。なお、加算マクロブロック生成部４２はなくてもよい。すなわち、図４２のようにして切り出したマクロブロックと同じ大きさのブロック１つを以降の処理の入力としてもよい。ただし、以下は加算マクロブロック生成部４２を用いる場合を前提としている。【０１０１】  次に本実施例の電子透かし検出装置４０における検出値行列生成部４３について説明する。検出値行列生成部４３の構成を図４３に、処理の流れを図４４に示す。図４３に示すように、検出値行列生成部４３は、各周波数に対応したフィルタ処理済み画像群生成部６２、ブロック切り出し位置検出部６３、検出値行列構成部６４、符号対応周波数データベース６５を有している。以下、図４４を参照して検出値行列生成部４３の処理の流れを説明する。【０１０２】  検出値行列生成部４３は、加算マクロブロック生成部４２により生成された加算マクロブロックを入力とし（ステップ１２１）、まず各周波数に対応したフィルタ処理済み画像群生成部６２において、符号対応周波数データベース６５（または量子化値対応周波数データベース。埋め込みに用いたものと同じものを用いる。ここでは２種類の周波数が含まれるものとする。）に登録されている周波数に対応した畳み込みオペレータを用いて加算マクロブロックに対して畳み込み演算を行い、周波数の種類分の数（２つ）のフィルタ処理済み画像を生成し、これらを各周波数に対応したフィルタ処理済み画像群として出力する（ステップ１２２）。【０１０３】  そして、ブロック切り出し位置検出部６３が、ブロック切り出し位置の探索を行い、ブロック切り出し位置を検出する（ステップ１２３）。最後に検出値行列構成部６４が、検出したブロック切り出し位置に対応した検出値行列を構成し出力する（ステップ１２４）。【０１０４】  以下、各部について更に説明する。【０１０５】  図４５に各周波数に対応したフィルタ処理済み画像群生成部６２の処理の概要を示す。図４５に示す例では、予め定められた周波数はｆ０、ｆ１の２種類に対応して、フィルタ処理済み画像を２つ生成する。それぞれの周波数に対応した畳み込みオペレータを用いて、加算マクロブロックの各画素に対して畳み込み演算を順次走査しながら行うことにより、２つの周波数に対応したフィルタ処理済み画像が２つ生成される。この時、図４５に示すように、畳み込みオペレータが対応する周波数と、埋め込み時の周波数パターンとが一致するフィルタ処理済み画像の領域においては、大きな絶対値を持つ値が現れ、一致していない場合は小さな絶対値を持つ値が現れる（図４５では明：＋の大きな絶対値の値、暗：−の大きな絶対値の値を示している）。これは畳み込み演算が部分的に相関演算を行っているとみなせることから、同じパターン同士の時に大きな絶対値をもつ相関値をとり、異なるパターンの時には小さな絶対値を持つ相関値を取ることを考えれば自明である。これら２つのフィルタ処理済み画像を各周波数に対応したフィルタ処理済み画像群として出力する。なお、畳み込み演算の際���、加算マクロブロックの端点などで画素値を参照できない場合は、サイクリックシフトのように画像の反対側の辺に折り返して得られる画素値を参照して画素値を参照するものとする。【０１０６】  次にブロック切り出し位置検出部６３の構成を図４６に、処理の流れを図４７に示す。図４６に示すように、ブロック切り出し位置検出部６３は、探索位置設定部６７、ブロック切り出し位置応答値算出部６８、ブロック切り出し位置応答値バッファ６９、ブロック切り出し位置決定部７０を有している。図４７を参照してブロック切り出し位置検出部６３における処理の流れを説明する。【０１０７】  ブロック切り出し位置検出部６３は、各周波数に対応したフィルタ処理済み画像群を入力とする（ステップ１３１）。まず探索位置設定部６７が、予め定めた探索範囲の中の探索位置情報（ｏｘ，ｏｙ）を生成する（ステップ１３２）。次にブロック切り出し位置応答値算出部６８が、探索位置情報で示される座標をブロック切り出し位置と仮定した場合のブロック切り出し位置応答値を求める（ステップ１３３）。求めたブロック切り出し位置応答値は、対応する探索位置情報と組にしてブロック切り出し位置応答値バッファに格納される（ステップ１３４）。この処理を予め定めた探索範囲に含まれる全ての探索位置について行う（ステップ１３５）。最後にブロック切り出し位置決定部７０において、最大のブロック切り出し位置応答値を持つ探索位置情報を、検出したブロック切り出し位置情報として出力する（ステップ１３６）。【０１０８】  図４８に探索位置情報の例を示す。探索範囲は加算マクロブロックの左上端点（各周波数に対応したフィルタ処理済み画像群の各画像も同じサイズなのでこれらの左上端点でもある）を中心としたある大きさを持つ近傍領域であり、この近傍領域に含まれる座標（ｏｘ，ｏｙ）を探索位置情報として順次選択する。例えば探索範囲は加算マクロブロックの左上端を中心とした、ブロックサイズ矩形領域を探索範囲とする。入力時点での加算マクロブロック中のブロック切り出し位置が、加算マクロブロックの左上端から位置ずれしている場合でも、近傍内に正しいブロック切り出し位置がある場合、探索位置が正しいブロック切り出し位置と一致したときに、ブロック切り出し位置応答値が他の探索位置に比べ大きな値となるような応答値算出方法を用いれば、正しいブロック切り出し位置が検出できることになる。また、上記のような探索範囲を用いれば、探索範囲中に必ず一点正しいブロック切り出し位置が含まれることになり、探索によって確実に正しいブロック切り出し位置が検出できることになる。このような観点で以下の処理が行なわれている。【０１０９】  ブロック切り出し位置応答値算出部６８の構成を図４９に、処理の流れを図５０に示す。図４９に示すように、ブロック切り出し位置応答値算出部６８は、ブロック分割部７２、画素絶対値和計算部７３、最大絶対値和判定部７４、最大絶対値和加算部７５を有している。図５０を参照してその処理の流れを説明する。【０１１０】  ブロック切り出し位置応答値算出部６８は、各周波数に対応したフィルタ処理済み画像群と探索位置情報を入力とする（ステップ１４１）。また、最大値絶対和加算部７３の値を０に初期化する（ステップ１４２）。【０１１１】  次にブロック分割部７２は、各周波数に対応したフィルタ処理済み画像群中の各フィルタ処理済み画像について、探索位置情報で示される座標をブロック切り出し位置とした場合のブロック分割を行い、同じブロック位置にある各フィルタ処理済み画像に対応した画素ブロック群を順次取得する（ステップ１４３）。【０１１２】  次に画素絶対値和加算部７３が、同じブロック位置にある各フィルタ処理済み画像に対応した画素ブロック群中の各画素ブロックについて、画素ブロック中の画素値の絶対値和を計算し、各画素ブロックに対応した画素絶対値和群を得る（ステップ１４４）。次に最大絶対値和判定部７４が、各画素ブロックに対応した画素絶対値和群の中で最大の値を取るものを選び、この値を最大絶対値和として取得する（ステップ１４５）。最後に最大絶対値和加算部７５において、初期値０の値であるＳに最大絶対値和を加算する（ステップ１４６）。上記画素絶対値和計算部７３から最大絶対値和加算部７５までの処理を、ブロック分割で取得した全ての各フィルタ処理済み画像に対応した画素ブロック群について繰り返し行い、その結果として得られるＳをブロック切り出し位置応答値として出力する（ステップ１４７、ステップ１４８）。【０１１３】  次に、ブロック切り出し位置応答値算出部６８における各部の処理についてより具体的に説明する。【０１１４】  まず、ブロック分割部７２について説明する。図５１にブロック分割部７２の処理を説明する図を示す。【０１１５】  ブロック分割部７２は、各周波数に対応したフィルタ処理済み画像群と探索位置情報を入力とし、各周波数に対応したフィルタ処理済み画像群中の各フィルタ処理済み画像について、探索位置情報で示される座標をブロック切り出し位置とした場合のブロック分割を行い、同じブロック位置にある各フィルタ処理済み画像に対応した画素ブロック群を順次出力する。画素ブロックのサイズは、各フィルタ処理済み画像（全て同じサイズ）を予め定めたブロック個数で分割した場合に相当する大きさである。探索位置情報で示される座標によってブロック分割をした際に、画像サイズの外の画素を参照する場合については、図５２に示すように加算マクロブロックの反対側の辺に折り返して得られる画素値を参照する、いわゆるサイクリックシフトによって画素値を得るものとする。【０１１６】  図５３に画素絶対値和計算部７３の処理を説明する図を示す。画素絶対値和計算部７３は、各フィルタ処理済み画像に対応した画素ブロック群を入力とし、それぞれの画素ブロックについて、その中に含まれる画素値の絶対値の総和を計算し、結果を各画素ブロックに対応した画素絶対値和群として出力する。この処理は、各画素ブロック生成の際に対応付けられた周波数のエネルギーを計算することに相当する。なお、埋め込みの際に一つの符号もしくは量子化値に複数の周波数が対応付けられていた場合には、各々の周波数に対応する絶対値和（エネルギー）の合計を、その複数の周波数に対応する絶対値和とする。なお、本明細書中及び特許請求の範囲における“絶対値和”の用語は、特に区別して用いる場合を除き、上記の意味での“複数の周波数に対応する複数の絶対値和を加算したもの”を含む意味で用いる。【０１１７】  ブロック切り出し位置応答値算出部６８により、探索位置情報で示される座標が正しいブロック切り出し位置の場合に大きな値を出力される理由について説明する。図５４の上図のようなブロック切り出しを行った場合、探索位置情報が正しいブロック切り出し位置からずれている場合には、分割されて得られる各画素ブロックは電子透かし埋め込み時のブロック分割のされ方からずれているため、埋め込み時に重畳された周波数パターン以外の画素領域を画素ブロックに含むことになり、重畳された周波数のエネルギーは、下図のように正しくブロック切り出しした場合に比べて小さな値となる。すなわち探索位置情報で現れる座標が正しいブロック切り出し位置のときに、ブロック切り出し位置応答値が最大値をとることになる。【０１１８】  次に、電子透かし検出装置４０における検出値行列生成部４３の中の検出値行列構成部６４について説明する。図５５に検出値行列構成部６４の構成を、図５６に処理の流れを示す。図５５に示すように、検出値行列構成部６４は、ブロック分割部７７、画素絶対値和計算部７８、最大エネルギー周波数判定部７９、検出値行列要素値設定部８０を有している。図５６を参照して検出値行列構成部６４の処理の流れを説明する。【０１１９】  検出値行列構成部６４は、各周波数に対応したフィルタ処理済み画像群と、ブロック切り出し位置情報を入力とする（ステップ１５１）。ブロック分割部７７は、ブロック切り出し位置情報で示される座標をブロック切り出し位置として、各周波数に対応したフィルタ処理済み画像群中の各フィルタ処理済み画像をブロック分割し、同じブロック位置にある各フィルタ処理済み画像に対応した画素ブロック群を順次生成する（ステップ１５２）。【０１２０】  次に画素絶対値和計算部７８は、各フィルタ処理済み画像に対応した画素ブロック群を入力とし、それぞれの画素ブロックについて、その中に含まれる画素値の絶対値の総和を計算し、結果を各画素ブロックに対応した画素絶対値和群として出力する（ステップ１５３）。検出値行列構成部６４内のブロック分割部７７および画素絶対値和計算部７８の処理は、ブロック切り出し位置応答値算出部６８のブロック分割部７２および画素絶対値和計算部７３と全く同じである。次に最大エネルギー周波数判定部７９が、各画素ブロックに対応した画素絶対値和群の中で最大の値を取る時の画素ブロックが、どの周波数に対応したフィルタ処理済み画像から得られたブロックかを判定し、対応する周波数を最大エネルギーをもつ周波数として出力する（ステップ１５４）。【０１２１】  最後に検出値行列要素値設定部８０は、最大エネルギーをもつ周波数に対応する符号を符号対応周波数データベースから決定し、２つ（周波数が２種類のため）の画素絶対値和の差の絶対値を求め、２つの画素絶対値和の差の絶対値に上記符号を付けた値を検出値として、ブロック位置に相当する検出値行列の要素値として設定する（ステップ１５５）。ここで、＋に対応する周波数に対応する画素絶対値和から−に対応する周波数の画素絶対値和を減算した値を要素値としてもよい。なお、最大エネルギーをもつ周波数に対応��る符号を符号対応周波数データベースから決定し、その符号を上記最大の画素絶対値和に付けた値を要素値としてもよい。また、１を符号に付した値を要素値とすることもできる。更に、前述した量子化値対応周波数データベースを用いて埋め込みを行なう方法を用いている場合、最大エネルギーをもつ周波数に対応する量子化値を決定し、これを要素値とすることもできる。【０１２２】  上記画素絶対値和計算部７８から検出値行列要素値設定部８０までの処理を、全てのブロック位置に対して繰り返し行い（ステップ１５６）、その結果を検出値行列として出力する（ステップ１５７）。【０１２３】  図５７を用いて検出値行列構成部６４の処理の流れをより具体的に説明する。各周波数に対応したフィルタ処理済み画像群の中のフィルタ処理済み画像を、ブロック切り出し位置情報に対応する座標をブロック切り出し位置として各々ブロック分割して各フィルタ処理済み画像に対応した画素ブロック群を生成し、各ブロック位置毎に、画素ブロック群中の各画素ブロックの画素値の絶対値和（図５７のａ０とａ１）を求めて、最大の画素絶対値和を取る画素ブロックがどの周波数に対応したフィルタ処理済み画像から得られたブロックかを判定し（図５７ではａ０＞ａ１とする）、フィルタ処理済み画像に対応する周波数を最大エネルギー周波数として得る。そして符号対応周波数データベースから最大エネルギー周波数に対応する符号を決定し（図５６ではａ０＞ａ１なので“＋”）、二つの画素絶対値和の差の絶対値（図５７では｜ａ０−ａ１｜）を求め、上記符号を付けた値（図５７では“＋｜ａ０−ａ１｜”）を検出値とし、検出値行列のブロック位置に対応する要素値として設定する。【０１２４】  上記のようにして得られた検出値行列について図５８を用いて説明する。図５８左図は埋め込み時に生成されたマクロブロックパターン中の各ブロックに対応する埋め込み系列の項値の符号を示し、右図は上記のようにして得られる検出値行列の各要素の符号を示している。検出値行列生成部４３中で、ブロック切り出し位置を検出し、ブロック切り出し位置からブロックを切り出して検出値行列を生成するため、加算マクロブロックと埋め込み時のマクロブロックパターンの関係は、各ブロック中の平行移動量の同期は取れているが、ブロックの並びの平行移動、即ち検出値行列の要素の並びの平行移動の不確定さが残っている。図中の丸印は埋め込み時に生成されたマクロブロックパターン中の各ブロックの並びの先頭位置を表しているが、検出値行列では要素の並びが平行移動しているため、検出値行列のある要素位置が元の先頭位置に対応し、検出値行列全体としては要素値の並びが先頭位置を基準にサイクリックシフトした状態になっいる。また、これと同時に一次変換歪補正部４１で残っていた不確定性である、９０度毎回転成分が残っている。【０１２５】  上記の不確定要素について対応することが可能となれば、最終的に埋め込んだ透かし情報を正しく検出することができる。このような観点から本実施例の透かし情報逆拡散部４４は構成されている。以下、本実施例の透かし情報逆拡散部４４について説明する。【０１２６】  本実施例における透かし情報逆拡散部４４の構成を図５９に、処���の流れを図６０に示す。図５９に示すように、本実施例の透かし情報逆拡散部４４は、検出値行列変換部８２、一次元化処理部８３、擬似乱数生成部８４、逆拡散部８５、復号対象情報選定部８６、誤り訂正／検出復号部８７を有している。以下、図６０を参照して透かし情報逆拡散部４４の処理の流れを説明する。【０１２７】  透かし情報逆拡散部４４は、検出値行列生成部４３で生成された検出値行列を入力とし（ステップ１６１）、まず検出値行列変換部８２が、９０度毎回転・符号反転／マクロブロック開始位置のパラメータを振って検出値行列を変換して得られる変換済み検出値行列群を生成する（ステップ１６２）。次に一次元化処理部８３が、変換済み検出値行列群中の各変換済み検出値行列を一次元化し、検出対象系列群を得る（ステップ１６３）。【０１２８】  次に逆拡散部８５において、擬似乱数生成器８４で生成される擬似乱数列と検出対象系列群を入力して、検出対象系列群中の各検出対象系列に対して、擬似乱数列を用いて逆拡散処理を行い、復号対象情報群および電子透かし有無指標値群を得る（ステップ１６４）。【０１２９】  次に復号対象情報選定部８６が、全ての電子透かし有無指標値が予め定めた閾値未満の場合は電子透かし検出不可能を透かし情報逆拡散部の出力として処理を終了し（ステップ１６８）、そうでない場合は、最大の電子透かし有無指標を持つ復号対象情報を選定する（ステップ１６７）。【０１３０】  最後に誤り訂正／検出復号部８７が、選定された復号対象情報に対して誤り訂正／検出復号を行い、検出透かし情報を得る（ステップ１６９）。この際、復号対象情報中の誤り検出した場合、訂正可能であれば訂正して検出透かし情報として出力し、訂正不可能な誤りを検出した場合は電子透かし検出不可能を出力する。【０１３１】  以下、透かし情報逆拡散部４４の各部についてより詳細に説明する。【０１３２】  本実施例における検出値行列変換部８２の構成を図６１に、処理の流れを図６２に示す。図６１に示すように、検出値行列変換部８２は９０度毎回転部８９とマクロブロック開始位置変換部９０を有している。【０１３３】  図６２に示すように、検出値行列変換部８２は検出値行列を入力とし（ステップ１７１）、まず９０度毎回転部８９において、図６３に示すように、検出値行列の要素の並びを０度、９０度、１８０度、２７０度回転させた４つの行列を得る（ステップ１７２）。次に４つの行列のうち、９０度回転、２７０度回転に対応する行列の全要素値の符号を反転する処理を施す（ステップ１７３、ステップ１７４）。この理由は、図６４に示すように、画像が９０度回転または２７０度回転している場合は、埋め込み時の波形パターンが逆転するため、画像から得られる検出値の符号も反転してしまうためである。上記のような処理により、得られる４つの行列を、回転済み検出値行列群として取得する（ステップ１７５）。【０１３４】  次にマクロブロック開始位置変換部９０において、図６５に示すように、回転済み検出値行列群中の各回転済み検出値行列に対して、マクロブロック開始位置を行列の各要素位置としたときに、該要素位置を行列の左上に移動させるようにサイクリックシフトさせた行列を順次生成し、得られる全ての行列を変換済み検出値行列群とする（ステップ１７６）。検出値行列がｎ×ｎ行列とすると、変換済み検出値行列群は全部で４ｎ２個の変換済み検出値行列から成る。【０１３５】  続いて、本実施例における透かし情報逆拡散部４４における一次元化処理部８３の処理を図６６を用いて説明する。一次元化処理部８３では、変換済み検出値行列群を入力とし、各変換済み検出値行列に対して、埋め込み時のマクロブロック設定部１９と同様の規則で、行列の要素を一次元化して検出対象系列を得る。全ての変換済み検出値行列から各々検出対象系列を得たら、これらをまとめて検出対象系列群として出力する。【０１３６】  続いて、本実施例における逆拡散部８５について以下に説明する。逆拡散部８５は検出対象系列群と、擬似乱数生成器８４で生成される擬似乱数列を入力とする。擬似乱数列は電子透かし埋め込み装置１０と同一の擬似乱数生成器を用いて生成される。逆拡散部８５は、検出対象系列群中の各検出対象系列に対して、逆拡散処理を行い、復号対象情報を得る。【０１３７】  具体的な逆拡散方法としては、埋め込み時の拡散方法に対応して以下のようなものを用いることが考えられる：
（Ａ）検出対象系列｛ｄｉ｝（ｉ＝０〜ｍｎ−１）、擬似乱数列を｛ｒｉ｝（ｉ＝０〜ｍｎ−１）とした時に、復号対象情報（Ｓビットとする）を｛ｃｋ｝
（ｋ＝０〜Ｓ−１）を以下のようにして求める。【０１３８】
0004303243.tif 000017
を求め、
0004303243.tif 000018
のようにビット値を決定する。【０１３９】  ただし、ｒｉ＝１ｏｒ−１の乱数列とする。またｘ％ｙはｘをｙで割った際の剰余を、ＳＱＲＴ（・）は平方根を表す。【０１４０】  （Ｂ）検出対象系列｛ｄｉ｝（ｉ＝０〜ｍｎ−１）、擬似乱数列を２種類生成しそれぞれ｛ｒ１ｉ｝（ｉ＝０〜ｍｎ−１）、｛ｒ２ｉ｝（ｉ＝０〜ｍｎ−１）とした時に、復号対象情報（Ｓビットとする）を｛ｃｋ｝（ｋ＝０〜Ｓ−１）を以下のようにして求める。まず｛ｒ１ｉ｝を用いて置換のための配列｛ｐｉ｝を埋め込み時と同様に生成する。【０１４１】  次に、
0004303243.tif 000019
を求め、
0004303243.tif 000020
のようにビット値を決定する。ただしｒ２ｉ＝１ｏｒ−１の乱数列とする。またｘ％ｙはｘをｙで割った際の剰余を、ＳＱＲＴ（・）は平方根を表す。【０１４２】  （Ｃ）検出対象系列｛ｄｉ｝（ｉ＝０〜ｍｎ−１）、擬似乱数列を｛ｒｉ｝（ｉ＝０〜ｍｎ−１）とした時に、復号対象情報（Ｓビットとする）を｛ｃｋ｝（ｋ＝０〜Ｓ−１）を以下のようにして求める。【０１４３】
0004303243.tif 000021
を求め、
0004303243.tif 000022
のようにビット値を決定する。ただしｒｉ＝１ｏｒ−１の乱数列とする。またｘ％ｙはｘをｙで割った際の剰余を、ＳＱＲＴ（・）は平方根を表す。【０１４４】  また、逆拡散部８５においては、復号対象情報とあわせて、電子透かし有無指標値を生成する。これは、逆拡散によって得られる復号対象情報の検出信号強度を表す指標値であり、上記の（Ａ）、（Ｂ）、（Ｃ）の例では、例えば以下のようにして算出する：
電子透かし有無指標値をＥの例として、
0004303243.tif 000023
上記のような電子透かし有無指標値が有効に機能する理由について図６７を用いて説明する。図６７の（１）は、電子透かしの検出が正しく行える場合のＣｏｒｋの取る値について示している。また、（２）は電子透かしが埋め込まれていない、あるいは電子透かし信号が検出できないほど歪みが大きい検出対象画像が与えられた場合などにより、電子透かし検出を正しく行えない場合のＣｏｒｋの取る値について示している。図６７のように、正しく検出可能な場合は、埋め込みに用いた乱数列と、検出対象画像から得られる検出対象系列との相関値が高いことから、各Ｃｏｒｋの絶対値は大きな値となり、逆に検出が正しく行えない場合は、各Ｃｏｒｋの絶対値は小さな値となる。また、本実施例における逆拡散の例（Ａ）、（Ｂ）、（Ｃ）では、検出対象系列のノルムを常に正規化してから乱数列との相関を計算しているため、異なる検出対象画像、異なる透かし情報を埋め込んだ場合でも同じ尺度で評価することができる。以上のことから、図６７の右側に示すように、Ｃｏｒｋの絶対値和である電子透かし有無指標値Ｅは（１）の場合には大きな値となり、（２）の場合には小さな値となる。そこで、後で述べるように、予め定めた閾値αを用いて、電子透かしの検出が正しく行えるか否かの判定を行うことができる。また、誤り訂正符号を用いて検出透かし情報の一部誤りを訂正する場合において、一般的に誤り訂正符号では訂正能力を超える誤りが生じた場合に誤訂正（間違った符号に訂正してしまう）が起こる危険性があるが、後に述べるように電子透かし有無指標値の閾値判定と組み合わせることにより、誤訂正の問題を回避することが可能となる。【０１４５】  逆拡散部８５は、上記のようにして得られる全ての復号対象情報をまとめて復号対象情報群とし、また全ての電子透かし有無指標値をまとめて電子透かし有無指標値群として出力する。【０１４６】  本実施例における復号対象情報選定部８６について以下に説明する。復号対象情報選定部８６は、復号対象情報群と電子透かし有無指標値群を入力とし、電子透かし有無指標値群中の各電子透かし有無指標値について、予め定めた閾値を用いた閾値判定を行い、全ての電子透かし有無指標値が閾値未満の場合は電子透かし検出不能を透かし情報逆拡散部の出力として処理を終了する。また、一つでも閾値以上の電子透かし有無指標値が存在する場合は、最大の電子透かし有無指標値を特定し、最大の電子透かし有無指標値に対応する復号対象情報を復号対象情報群中から選定し、これを出力する。【０１４７】  本実施例における誤り訂正／検出復号部８７について以下に説明する。誤り訂正／検出復号部８７は復号対象情報を入力とし、復号対象情報に対して誤り訂正／検出復号処理を行い、検出透かし情報を得る。この際、復号対象情報中の誤り検出した場合、訂正可能であれば訂正して検出透かし情報として出力し、訂正不可能な誤りを検出した場合は電子透かし検出不可能を出力する。【０１４８】  なお、上記復号対象情報選定部８６と誤り訂正／検出復号部８７の順序を変えてもよい。即ち、まず誤り訂正／検出復号部８７において復号対象情報群の各復号対象情報に対して誤り訂正／検出復号処理を行い、訂正可能な誤りを含む復号対象��報を選定する。全て訂正不可能な誤りを検出した場合は電子透かし検出不可能を出力する。次に復号対象情報選定部８６において、訂正可能な誤りを含む復号対象情報に対応する電子透かし有無指標値について閾値判定を行い、全て閾値未満の場合は電子透かし検出不可能を出力し、そうでない場合は最大の電子透かし検出有無指標値に対応する復号対象情報を誤り訂正／検出復号して得られる情報を検出透かし情報として出力する、としても良い。【０１４９】  また、上記実施例では変換済み検出値行列を予め全部生成し、以降の処理も全てまとめて処理するように記述しているが、変換済み検出値行列の生成から誤り訂正／検出復号部８７までの処理を順次行うようにして、電子透かし有無指標値による閾値判定かつ誤り訂正／検出処理により訂正可能性チェックをパスした場合に処理を中断して検出透かし情報を出力するようにしても良い。このようにすれば検出処理が終了するまでの処理時間の期待値が、上記の例の約半分で済むことになる。またループ抜け判定を電子透かし有無指標値による閾値判定または誤り訂正／検出処理により訂正可能性チェックのどちらか一方のみとし、ループを抜けた時にもう一方のチェックを行い、チェックをパスすれば検出透かし情報出力、パスしなければループ処理を続けるとすることで、ループ内処理が高速になり、さらに高速化を図ることができる。【０１５０】  さらに電子透かし検出有無指標値・逆拡散演算を、検出対象系列の部分列のみに対して行う、例えば復号対象情報の前半ビット分までの演算を行うとして、得られる電子透かし有無指標値に対して閾値判定をし、閾値以上の場合に残りの逆拡散処理を行って誤り訂正／検出復号により検出透かし情報を出力するようにしてもよい。電子透かし検出有無指標値はある程度の部分列でも電子透かしの有無を判定するのに十分な値を出力する可能性があるためである。このようにすれば、電子透かし検出有無指標値・逆拡散演算の処理量が検出対象系列の部分列分だけで済むため、処理の高速化が実現できる。【０１５１】  これまでに説明したように本実施例によれば、枠線などを用いずに画像に与えられたアフィン変換（一次変換＋平行移動）の補正をして電子透かしの検出が可能となる。また、従来のように電子透かし情報と別に幾何変換補正用の信号を独立に付加することなく、電子透かし情報を表すパターンが同時に幾何変換補正用の信号を兼ねることから、信号間の干渉の問題がなくなり、検出性能が向上するという効果がある。【０１５２】  なお、本実施例において説明した装置は、当該装置の機能を実行させるためのプログラムを、ＣＰＵ、記憶装置等を有するコンピュータに搭載することにより実現することも可能である。そのプログラムは、ＣＤ−ＲＯＭ、メモリなどの記録媒体に記録して配布したり、ネットワークを介して配布することができる。【０１５３】  なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【図１】
0004303243.tif 000024
【図２】
0004303243.tif 000025
【図３】
0004303243.tif 000026
【図４】
0004303243.tif 000027
【図５】
0004303243.tif 000028
【図６】
0004303243.tif 000029
【図７】
0004303243.tif 000030
【図８】
0004303243.tif 000031
【図９】
0004303243.tif 000032
【図１０】
0004303243.tif 000033
【図１１】
0004303243.tif 000034
【図１２】
0004303243.tif 000035
【図１３】
0004303243.tif 000036
【図１４】
0004303243.tif 000037
【図１５】
0004303243.tif 000038
【図１６】
0004303243.tif 000039
【図１７】
0004303243.tif 000040
【図１８】
0004303243.tif 000041
【図１９】
0004303243.tif 000042
【図２０】
0004303243.tif 000043
【図２１】
0004303243.tif 000044
【図２２】
0004303243.tif 000045
【図２３】
0004303243.tif 000046
【図２４】
0004303243.tif 000047
【図２５】
0004303243.tif 000048
【図２６】
0004303243.tif 000049
【図２７】
0004303243.tif 000050
【図２８】
0004303243.tif 000051
【図２９】
0004303243.tif 000052
【図３０】
0004303243.tif 000053
【図３１】
0004303243.tif 000054
【図３２】
0004303243.tif 000055
【図３３】
0004303243.tif 000056
【図３４】
0004303243.tif 000057
【図３５】
0004303243.tif 000058
【図３６】
0004303243.tif 000059
【図３７】
0004303243.tif 000060
【図３８】
0004303243.tif 000061
【図３９】
0004303243.tif 000062
【図４０】
0004303243.tif 000063
【図４１】
0004303243.tif 000064
【図４２】
0004303243.tif 000065
【図４３】
0004303243.tif 000066
【図４４】
0004303243.tif 000067
【図４５】
0004303243.tif 000068
【図４６】
0004303243.tif 000069
【図４７】
0004303243.tif 000070
【図４８】
0004303243.tif 000071
【図４９】
0004303243.tif 000072
【図５０】
0004303243.tif 000073
【図５１】
0004303243.tif 000074
【図５２】
0004303243.tif 000075
【図５３】
0004303243.tif 000076
【図５４】
0004303243.tif 000077
【図５５】
0004303243.tif 000078
【図５６】
0004303243.tif 000079
【図５７】
0004303243.tif 000080
【図５８】
0004303243.tif 000081
【図５９】
0004303243.tif 000082
【図６０】
0004303243.tif 000083
【図６１】
0004303243.tif 000084
【図６２】
0004303243.tif 000085
【図６３】
0004303243.tif 000086
【図６４】
0004303243.tif 000087
【図６５】
0004303243.tif 000088
【図６６】
0004303243.tif 000089
【図６７】
0004303243.tif 000090