(57)【要約】【課題】  流通の過程でデジタル信号に加えられた改変の量を自己相関関数を算出することにより推定する際に、デジタル信号に加えられた改変として拡大率が大きい場合に、自己相関関数の特徴点が検出できなくなることを解決する。【解決手段】  本発明は、改変が加えられたデジタル信号が入力されると、自己相関関数の算出に先立って所定の倍率で縮小し、自己相関関数から推定された改変の量と、縮小した倍率に従ってデジタル信号に加えられた改変の量を算出する。【選択図】  図２
2006295473.tif 000002
【特許請求の範囲】
【請求項１】
デジタル信号に対して、予め所定のパターンを繰り返し人間の知覚に感知されないように電子透かしとして該所定のパターンが埋め込まれ、改変が加えられたデジタル信号が入力されると、該改変が加えられたデジタル信号の自己相関関数を算出する手段を有し、該デジタル信号に加えられた改変の量を推定する電子透かし検出装置であって、
入力された前記改変が加えられたデジタル信号を前記自己相関関数の算出に先立って所定の倍率で縮小する信号縮小手段と、
前記自己相関関数から推定された改変の量と、前記信号縮小手段で縮小した倍率に従って前記デジタル信号に加えられた改変の量を算出する変換パラメータ算出手段と、
を有することを特徴とする電子透かし検出装置。
【請求項２】
前記信号縮小手段は、
複数の異なる倍率で上記改変の加えられたデジタル信号を縮小する手段を含み、
前記信号縮小手段で縮小された前記改変の加えられたデジタル信号毎に自己相関関数を算出する自己相関関数計算手段と、
前記自己相関関数計算手段で得られた自己相関関数毎に自己相関ピークを探索してその評価値を算出する自己相関ピーク点評価手段と、
前記自己相関ピーク点評価手段で得られた評価値に従って、埋込情報の検出対象に用いる自己相関ピーク点を決定する検出対象決定手段と、
を更に有する請求項１記載の電子透かし検出装置。
【請求項３】
異なる倍率によって縮小された前記改変の加えられたデジタル信号に対して、前記自己相関関数計算手段で得られた自己相関関数値が、互いに同程度の分布を持つように、該自己相関関数値を正規化する自己相関関数値正規化手段を更に有する、請求項２記載の電子透かし検出装置。
【請求項４】
異なる倍率によって縮小された前記改変の加えられたデジタル信号に対して、前記自己相関関数計算手段で得られた評価値が、互いに同程度の分布を持つように、該評価値を正規化する自己相関ピーク点評価値正規化手段を更に有する、請求項２または、３記載の電子透かし検出装置。
【請求項５】
前記検出対象決定手段は、
優先すべきピーク点候補の数Ｌを記憶する優先ピーク点候補数記憶手段と、
埋め込み情報検出処理を実施する上限の回数Ｍを記憶する埋め込み情報検出上限回数記憶手段と、
前記自己相関関数計算手段で得られた自己相関毎に、前記自己相関ピーク点評価手段で得られた自己相関ピーク点評価値について、評価の高いものから順に前記優先ピーク点候補数記憶手段に記憶された優先ピーク点候補数Ｌ個のピーク点評価値を選択し、これに所定の値ｐ０を加算する自己相関ピーク点評価値増加手段と、
前記自己相関ピーク点評価値増加手段によって増加されたピーク点評価値及び増加されなかったピーク点評価値の全てについて、評価の高いものから順に前記埋め込み情報検出上限回数記憶手段に記憶された埋め込み情報検出上限回数Ｍ個のピーク点評価値を選択し、これに対応するピーク点候補を検出対象として出力する埋め込み情報検出対象ピーク点候補選択手段と、
を更に有する請求項２、３または４記載の電子透かし検出装置。
【請求項６】
デジタル信号に対して、予め所定のパターンを繰り返し人間の知覚に感知されないように電子透かしとして該所定のパターンが埋め込まれ、改変が加えられたデジタル信号が入力されると、該改変が加えられたデジタル信号の自己相関関数を算出する手段を有し、該デジタル信号に加えられた改変の量を推定する電子透かし検出装置における、電子透かし検出方法であって、
入力された前記改変が加えられたデジタル信号を前記自己相関関数の算出に先立って所定の倍率で縮小する信号縮小ステップと、
前記自己相関関数から推定された改変の量と、前記信号縮小ステップで縮小した倍率に従って前記デジタル信号に加えられた改変の量を算出する変換パラメータ算出ステップと、
を行うことを特徴とする電子透かし検出方法。
【請求項７】
前記信号縮小ステップにおいて、
複数の異なる倍率で上記改変の加えられたデジタル信号を縮小するステップを行い、
前記信号縮小ステップで縮小された前記改変の加えられたデジタル信号毎に自己相関関数を算出する自己相関関数計算ステップと、
前記自己相関関数計算ステップで得られた自己相関関数毎に自己相関ピークを探索してその評価値を算出する自己相関ピーク点評価ステップと、
前記自己相関ピーク点評価ステップで得られた評価値に従って、埋込情報の検出対象に用いる自己相関ピーク点を決定する検出対象決定ステップと、
を更に行う請求項６記載の電子透かし検出方法。
【請求項８】
異なる倍率によって縮小された前記改変の加えられたデジタル信号に対して、前記自己相関関数計算ステップで得られた自己相関関数値が、互いに同程度の分布を持つように、該自己相関関数値を正規化する自己相関関数値正規化ステップを更に行う、請求項７記載の電子透かし検出方法。
【請求項９】
異なる倍率によって縮小された前記改変の加えられたデジタル信号に対して、前記自己相関関数計算ステップで得られた評価値が、互いに同程度の分布を持つように、該評価値を正規化する自己相関ピーク点評価値正規化ステップを更に行う、請求項７または、８記載の電子透かし検出方法。
【請求項１０】
前記検出対象決定ステップにおいて、
前記自己相関関数計算ステップで得られた自己相関毎に、前記自己相関ピーク点評価ステップで得られた自己相関ピーク点評価値について、優先すべきピーク点候補の数Ｌを記憶する優先ピーク点候補数記憶手段に記憶された優先ピーク点候補数Ｌ個のピーク点評価値を評価の高いものから順に選択し、これに所定の値ｐ０を加算する自己相関ピーク点評価値増加ステップと、
前記自己相関ピーク点評価値増加ステップによって増加されたピーク点評価値及び増加されなかったピーク点評価値の全てについて、埋め込み情報検出処理を実施する上限の回数Ｍを記憶する埋め込み情報検出上限回数記憶手段に記憶された埋め込み情報検出上限回数Ｍ個のピーク点評価値を評価の高いものから順に選択し、これに対応するピーク点候補を検出対象として出力する埋め込み情報検出対象ピーク点候補選択ステップと、
を更に行う請求項７，８または９記載の電子透かし検出方法。
【請求項１１】
デジタル信号に対して、予め所定のパターンを繰り返し人間の知覚に感知されないように電子透かしとして該所定のパターンが埋め込まれ、改変が加えられたデジタル信号が入力されると、該改変が加えられたデジタル信号の自己相関関数を算出することにより該デジタル信号に加えられた改変の量を推定する電子透かし検出プログラムであって、
前記請求項１乃至５記載の電子透かし検出装置の各手段の機能をコンピュータに実行させることを特徴とする電子透かし検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子透かし検出装置及び方法及びプログラムに係り、特に、電子透かしの埋め込まれた信号に対して、拡大・縮小、回転、アクペクト比変更、アフィン変換等の一次変換で表される改変が加えられた場合にも電子透かしの検出を容易にするための電子透かし検出装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
従来、デジタルコンテンツに対し、電子透かしを埋め込むことで、デジタルコンテンツの著作権情報保護を行ったり、デジタルコンテンツに関する著作権情報を参照したり、あるいは、デジタルコンテンツを広告としての印刷物などのアナログ媒体を介した上でデジタルカメラなどで撮影し、電子透かしを読み取ることで広告に関連した情報を取得させたりといったサービスが実現されるようになってきた。
【０００３】
例えば、電子透かしを埋め込む際に、埋め込み対象成分位置情報に基づいて、複素行列の実数成分と虚数成分を独立に変更するスペクトル拡散を行い、入力画像と独立に透かしパターンを生成し、実際の画像パターンの加算を行うことで埋め込み済み画像を生成し、電子透かしを検出する際には、検出対象成分位置情報に基づいて検出対象系列を生成し、オフセット情報を抽出し、検出対象系列を修正した後にスペクトル逆拡散を行い、切り出した画素ブロック内に埋め込まれている電子透かしを検出するような電子透かし方式がある（例えば、特許文献１参照）。
【０００４】
また、電子透かしにおいては、デジタルコンテンツを表すデジタル信号が、電子透かしの埋め込み後に受ける様々な改変に対して耐性を持つ、すなわち様々な改変を受けた上で電子透かしを検出できることが必要である。
【０００５】
例えば、電子透かしの情報とは別に、幾何的な補正を行うための信号をデジタル信号に埋め込んでおき、これを検出することでデジタル信号に加えられた改変の程度を推定する方法がある（例えば、特許文献２参照）。しかしながら、このような方法では電子透かしの情報に加えて幾何補正のための信号をデジタル信号に埋め込むため、電子透かしの埋め込まれたデジタル信号の品質の劣化や、電子透かし検出処理時間の増加につながる可能性があった。
【０００６】
これに対し、電子透かしの埋め込まれたデジタル信号（以下、電子透かし埋め込み済み信号と記す）から電子透かしを検出する方法として、予め共通の性質を有するパターンを信号の複数位置に電子透かしとして埋め込んでおき、電子透かし検出の際に電子透かし埋め込み済み信号の自己相関関数を求めることで、電子透かし埋め込み済み信号に加えられた拡大・縮小、回転、アスペクト比変更、アフィン変換等の一次変換で表される改変の程度を推定し、推定された改変の量に応じて、改変の加えられた電子透かし埋め込み済み信号を補正し、電子透かしを検出しやすくする様な電子透かし検出の方法が提案されてきた。
【０００７】
例えば、一対の同一特徴を有するマーカ画像をオリジナル画像内に埋め込んでマークを付けた画像を生成し、マーク付画像に回転や拡大／縮小された画像の自己相関関数に表れるピーク点の位置から、電子透かし埋め込み済み信号に加えられた回転や拡大／縮小の程度を算出する方法がある（例えば、特許文献３参照）。また、当該方法は、上記ピーク点を見つけるために、自己相関関数値を高域周波数通過フィルタ（ＨＰＦ）を用いてフィルタリングする（以下、従来方法３と記す）。
【０００８】
また、例えば、電子透かしとして埋め込む情報を有する埋め込みパターンそのものに、繰り返しを持つ周期的なパターンを用い、検出時に自己相関関数からその周期の変化を観測することによって拡大・縮小率を算出し、得られた拡大・縮小率に基づき電子透かしの検出処理を行う方法がある（例えば、特許文献４参照）。
【特許文献１】特開２００３−２１９１４８「電子透かし埋め込み方法及び電子透かし検出方法及び電子透かし埋め込み装置、及び電子透かし検出装置、及び電子透かし埋め込みプログラムを格納した記憶媒体、及び電子透かし検出プログラムを格納した記憶媒体」
【特許文献２】特開平１１−３５５５４７「幾何変換特定システム」
【特許文献３】特開２００１−２０９８０６「画像の回転または拡大／縮小を検出する方法およびコンピュータプログラム」
【特許文献４】特開２００２−１１１９９４「拡大縮小耐性を有する電子透かし方法及びシステム」
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来方法３にあるような自己相関関数を計算するにあたり、入力された信号のサイズ、例えば、２次元の画像信号の場合の画像の縦横のピクセル数などが大きい場合、信号全体に対する自己相関関数を計算するのは非常に時間を要する処理であるため、処理可能な小さな領域に対して離散フーリエ変換などを利用した自己相関関数の計算を行う必要がある。
【００１０】
しかしながら、信号に加えられた改変としての拡大率が大きい場合、自己相関関数計算の対象となる領域と比較して信号に埋め込まれたパターンの大きさが大きくなってしまい、結果として自己相関関数値にピーク点が現れなくなり、改変の程度を推定できなくなるという課題がある。
【００１１】
本発明は、上記の点に鑑みなされたもので、信号に与えられた改変としての拡大率が小さい場合と大きい場合の双方においても、広い領域の自己相関関数計算を不要とし、自己相関関数計算に必要な処理時間を抑制しつつ、高精度に自己相関関数値に現れるピーク点を探索し、電子透かしの検出を容易にすることが可能な電子透かし検出装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
図１は、本発明の原理構成図である。
【００１３】
本発明（請求項１）は、デジタル信号に対して、予め所定のパターンを繰り返し人間の知覚に感知されないように電子透かしとして該所定のパターンが埋め込まれ、改変が加えられたデジタル信号が入力されると、該改変が加えられたデジタル信号の自己相関関数を算出する手段を有し、該デジタル信号に加えられた改変の量を推定する電子透かし検出装置であって、
入力された改変が加えられたデジタル信号を自己相関関数の算出に先立って所定の倍率で縮小する信号縮小手段１０と、
自己相関関数から推定された改変の量と、信号縮小手段１０で縮小した倍率に従ってデジタル信号に加えられた改変の量を算出する変換パラメータ算出手段２０と、を有する。
【００１４】
また、本発明（請求項２）の電子透かし検出装置は、
請求項１の信号縮小手段１０において、
複数の異なる倍率で上記改変の加えられたデジタル信号を縮小する手段を含み、
信号縮小手段で縮小された改変の加えられたデジタル信号毎に自己相関関数を算出する自己相関関数計算手段と、
自己相関関数計算手段で得られた自己相関関数毎に自己相関ピークを探索してその評価値を算出する自己相関ピーク点評価手段と、
自己相関ピーク点評価手段で得られた評価値に従って、埋込情報の検出対象に用いる自己相関ピーク点を決定する検出対象決定手段と、を更に有する。
【００１５】
また、本発明（請求項３）は、請求項２の電子透かし検出装置において、
異なる倍率によって縮小された改変の加えられたデジタル信号に対して、自己相関関数計算手段で得られた自己相関関数値が、互いに同程度の分布を持つように、該自己相関関数値を正規化する自己相関関数値正規化手段を更に有する。
【００１６】
また、本発明（請求項４）は、請求項２または、３の電子透かし検出装置において、
異なる倍率によって縮小された改変の加えられたデジタル信号に対して、自己相関関数計算手段で得られた評価値が、互いに同程度の分布を持つように、該評価値を正規化する自己相関ピーク点評価値正規化手段を更に有する。
【００１７】
また、本発明（請求項５）の電子透かし検出装置は、
検出対象決定手段において、
優先すべきピーク点候補の数Ｌを記憶する優先ピーク点候補数記憶手段と、
埋め込み情報検出処理を実施する上限の回数Ｍを記憶する埋め込み情報検出上限回数記憶手段と、
自己相関関数計算手段で得られた自己相関毎に、自己相関ピーク点評価手段で得られた自己相関ピーク点評価値について、評価の高いものから順に優先ピーク点候補数記憶手段に記憶された優先ピーク点候補数Ｌ個のピーク点評価値を選択し、これに所定の値ｐ０を加算する自己相関ピーク点評価値増加手段と、
自己相関ピーク点評価値増加手段によって増加されたピーク点評価値及び増加されなかったピーク点評価値の全てについて、評価の高いものから順に埋め込み情報検出上限回数記憶手段に記憶された埋め込み情報検出上限回数Ｍ個のピーク点評価値を選択し、これに対応するピーク点候補を検出対象として出力する埋め込み情報検出対象ピーク点候補選択手段と、を更に有する。
【００１８】
図２は、本発明の原理を説明するための図である。
【００１９】
本発明（請求項６）は、デジタル信号に対して、予め所定のパターンを繰り返し人間の知覚に感知されないように電子透かしとして該所定のパターンが埋め込まれ、改変が加えられたデジタル信号が入力されると、該改変が加えられたデジタル信号の自己相関関数を算出することにより、該デジタル信号に加えられた改変の量を推定する電子透かし検出装置における、電子透かし検出方法であって、
入力された改変が加えられたデジタル信号を自己相関関数の算出に先立って所定の倍率で縮小する信号縮小ステップ（ステップ１、２）と、
自己相関関数から推定された改変の量と、信号縮小ステップで縮小した倍率に従ってデジタル信号に加えられた改変の量を算出する変換パラメータ算出ステップ（ステップ３，４）と、を行う。
【００２０】
また、本発明（請求項７）の電子透かし検出方法は、
請求項６の信号縮小ステップにおいて、
複数の異なる倍率で上記改変の加えられたデジタル信号を縮小するステップを行い、
信号縮小ステップで縮小された改変の加えられたデジタル信号毎に自己相関関数を算出する自己相関関数計算ステップと、
自己相関関数計算ステップで得られた自己相関関数毎に自己相関ピークを探索してその評価値を算出する自己相関ピーク点評価ステップと、
自己相関ピーク点評価ステップで得られた評価値に従って、埋込情報の検出対象に用いる自己相関ピーク点を決定する検出対象決定ステップと、を更に行う。
【００２１】
また、本発明（請求項８）は、請求項７の電子透かし検出方法において、
異なる倍率によって縮小された改変の加えられたデジタル信号に対して、自己相関関数計算ステップで得られた自己相関関数値が、互いに同程度の分布を持つように、該自己相関関数値を正規化する自己相関関数値正規化ステップを更に行う。
【００２２】
また、本発明（請求項９）は、請求項７または８の電子透かし検出方法において、
異なる倍率によって縮小された改変の加えられたデジタル信号に対して、自己相関関数計算ステップで得られた評価値が、互いに同程度の分布を持つように、該評価値を正規化する自己相関ピーク点評価値正規化ステップを更に行う。
【００２３】
また、本発明（請求項１０）の電子透かし検出方法は、
検出対象決定ステップにおいて、
自己相関関数計算ステップで得られた自己相関毎に、自己相関ピーク点評価ステップで得られた自己相関ピーク点評価値について、優先すべきピーク点候補の数Ｌを記憶する優先ピーク点候補数記憶手段に記憶された優先ピーク点候補数Ｌ個のピーク点評価値を評価の高いものから順に選択し、これに所定の値ｐ０を加算する自己相関ピーク点評価値増加ステップと、
自己相関ピーク点評価値増加ステップによって増加されたピーク点評価値及び増加されなかったピーク点評価値の全てについて、埋め込み情報検出処理を実施する上限の回数Ｍを記憶する埋め込み情報検出上限回数記憶手段に記憶された埋め込み情報検出上限回数Ｍ個のピーク点評価値を評価の高いものから順に選択し、これに対応するピーク点候補を検出対象として出力する埋め込み情報検出対象ピーク点候補選択ステップと、を更に行う。
【００２４】
本発明（請求項１１）は、デジタル信号に対して、予め所定のパターンを繰り返し人間の知覚に感知されないように電子透かしとして該所定のパターンが埋め込まれ、改変が加えられたデジタル信号が入力されると、該改変が加えられたデジタル信号の自己相関関数を算出することにより該デジタル信号に加えられた改変の量を推定する電子透かし検出プログラムであって、
請求項１乃至５記載の電子透かし検出装置の各手段の機能をコンピュータに実行させるプログラムである。
【発明の効果】
【００２５】
本発明の請求項１の電子透かし検出装置及び、請求項６の電子透かし検出方法によれば、入力された改変の加えられたデジタル信号を縮小してから自己相関関数を計算するため、小さな領域の自己相関関数計算でも必要な自己相関ピークを得ることができ、自己相関関数計算に要する処理時間を抑制し、効率的な電子透かし検出が可能となる。
【００２６】
本発明の請求項２の電子透かし検出装置及び請求項７の電子透かし検出方法によれば、複数の異なる倍率に縮小された信号毎にピーク点評価を行うため、信号に加えられた改変の程度が小さな拡大率から大きな拡大率まで広い範囲に想定される場合にも、自己相関ピーク点の探索を高精度に行うことができ、高精度な電子透かしの検出が可能となる。
【００２７】
本発明の請求項３，４の電子透かし検出装置及び請求項８，９の電子透かし検出方法によれば、複数のレンジ毎の自己相関関数値やピーク点評価値をそれぞれ正規化することで、レンジを跨ったピーク点評価値の比較において、正しいピーク点の得られているレンジのピーク点候補の評価値より、信号に加えられたノイズや元々の信号の自己相関性によって異なるレンジにおいて現れた誤ったピーク点候補の評価値を高く評価してしまうことによる検出失敗を抑制し、自己相関ピーク点の探索を高精度に行うことができ、高精度な電子透かしの検出が可能となる。
【００２８】
本発明の請求項５の電子透かし検出装置及び請求項１０の電子透かし検出方法によれば、各レンジのピーク点評価値において、正しいレンジの正しいピーク点候補の評価値よりも大きな評価値を持つ、誤ったレンジの誤ったピーク点候補が多数存在した場合にも、各レンジの上位にあるピーク点候補を優先する結果、正しいレンジの正しいピーク点候補を埋め込み情報検出の対象とすることができ、検出に失敗することを抑制することができると共に、全体として検出を行うピーク点候補の上限数を所定の数に限定することができるため、全体の検出処理時間の上限を限定することができる。また、個々の電子透かし検出において推定し得る信号に加えられた改変やノイズについての条件に応じて、どのようなピーク点候補を優先して検出対象にするかの埋め込み情報検出方法を、装置の構成の変更なしに容易に変更することが可能となり、効率よく電子透かしの検出を実施することができる。
【発明を実施するための最良の形態】
【００２９】
以下、図面と共に本発明の実施の形態を説明する。
【００３０】
本発明の電子透かし検出装置では、入力された電子透かし検出対象の信号に対して複数の縮小率で縮小した信号毎に自己相関関数を計算することにより、信号に対する改変として拡大率の大きい拡大がなされている場合においても、小さい領域での自己相関関数値の計算で自己相関ピークを発見できるようにすることを骨子とする。
【００３１】
以下では、まず、第１〜第３の実施の形態において、本発明の背景となる電子透かし埋め込み・検出方法について詳細を述べた後に、第４の実施の形態において、本発明の電子透かし検出装置について述べる。
【００３２】
最初に本発明で使用される用語について定義する。
【００３３】
本発明においては、電子透かしの埋め込み、検出が行われる対象となる情報を「信号」と称する。以下の実施の形態では、主として２次元の画像信号に対する処理を例に説明するが、映像や音声信号であっても構わない。また、任意のｎ次元の信号について同様の方法を適用することができることは言うまでもない。
【００３４】
次に、本発明で使用する「電子透かし埋め込み検出の通信モデル」について説明する。
【００３５】
図３は、本発明の背景となる電子透かし埋め込み・検出のモデルを示す図である。
【００３６】
系に与えられた埋め込み前信号１０１に対し、電子透かし埋め込み装置２００を用いて埋め込み情報１０２が埋め込まれる。埋め込み情報１０２は、後に検出して利用する情報であればどのような情報であってもよく、例えば、コンテンツの識別子、著作権情報、ＵＲＬ、コンテンツを購入したユーザの識別子や名前、住所、コンテンツを販売したトランザクションの識別子、コンテンツを生成したデジタルカメラなどの機器の識別子や機器の情報、コンテンツのコピー可否を制御するためのフラグ、コンテンツの改ざん検知を行うための信号などであってもよい。また、電子透かし検出によって後述する信号の改変１０７の大きさを求めること自体を目的とするような系においては、埋め込み情報１０２は所定の固定の値であってもよい。埋め込み情報１０２が固定の値である場合は、明示的に電子透かし埋め込み装置２００に入力されること無く、電子透かし埋め込み装置２００の内部に予め記憶されている値を用いるようにされていてもよいことは言うまでもない。
【００３７】
電子透かし埋め込み装置２００の出力した埋め込み済み信号１０４は、通信路１０５を経る中で加法的ノイズ１０６や信号の改変１０７といったノイズが付加される。
【００３８】
ここで、加法的ノイズ１０６は、例えば、画像信号における画素値やＤＣＴ係数などの、信号の時間的・空間的・周波数的に分割された要素のとる値に対して加減算的に加えられるノイズ成分であって、例えば、信号に加えられる雑音や、例えば、ＭＰＥＧやＪＰＥＧなどの信号の符号化ノイズであってもよい。
【００３９】
信号の改変１０７は、例えば、画像信号における被写体の形状などの、信号の時間的・空間的・周波数的な位置を変化させるような改変であって、例えば、信号の平行移動、拡大・縮小、回転、アクペクト比変更、アフィン変換等の一次変換、一部切り取りなどの改変であってもよい。
【００４０】
加法的ノイズ１０６、信号の改変１０７、人によって意図されたものであっても意図されないものであってもよい。また、加法的ノイズ１０６、信号の改変１０７の付加される順序は問わない。
【００４１】
また、通信路１０５上で上記以外の信号に対する変化が加えられても構わない。
【００４２】
通信路１０５を経て改変された埋め込み済み信号１０８が電子透かし検出装置４００に入力され、埋め込み情報１０２と同じ検出情報１１０が出力される。
【００４３】
［第１の実施の形態］
以下に、本発明により検出する電子透かしを埋め込む方法の例を示す。
【００４４】
図４は、第１の実施の形態における電子透かし埋め込み装置の構成例である。
【００４５】
電子透かし埋め込み装置２００は、透かしパターン生成部２０１、透かしパターン加算部２０２から構成される。
【００４６】
電子透かしの埋め込みは次のような手順に従って行われる。
【００４７】
１）  透かしパターン生成部２０１において、電子透かし埋め込み装置２００に入力された埋め込み情報１０２に基づき、信号に対して電子透かしとして埋め込む透かしパターン２０３を生成する。
【００４８】
透かしパターン２０３の生成の方法としては、例えば、前述の特許文献１の第１の実施例に述べられているような、埋め込み情報１０２に基づいて透かし係数行列を変更したものに対し、離散逆フーリエ変換を施して得られた信号パターンであっても構わない。２次元の画像信号を対象とした場合に生成された透かしパターンの例を、図５の透かしパターン３０１に示す。透かしパターン２０３の生成の方法はこれに限定するものではなく、後述する透かしパターンの加算の結果得られる埋め込み済み信号１０４において、透かしパターン２０３の存在が人間の知覚に感知されにくいように構成されるものであればどのようなパターンであっても構わず、例えば、他の既存の電子透かし埋め込み方法に基づいて構成されたパターンであっても構わない。
【００４９】
２）  透かしパターン加算部２０２において、透かしパターン生成部２０１で生成された透かしパターン２０３を、電子透かしの埋め込み装置２００に入力された埋め込み前信号１０１に、繰り返し並べて加算することで埋め込み済み信号１０４を得る。例えば、２次元の画像信号を対象とした場合には透かしパターン３０１を入力された画像信号である埋め込み前信号１０１に対し、図５に示す例のように繰り返しタイル状に加算する。
【００５０】
透かしパターン２０３の加算の方法としては、例えば、前述の特許文献１の第１の実施例に述べられているように、与えられた強度パラメータに従ってパターンを必要に応じて強調して加算するようにしてもよい。また、埋め込み前信号１０１の加算を行う部位の信号の特徴に応じ、例えば、加算されたパターンが目立つような部位ではパターンの強度を小さくし、パターンが目立たない部位ではパターンの強度を大きくするようにパターンの強度の程度を変化させるなどして、透かしパターンを加算するようにされていてもかまわない。
【００５１】
次に、電子透かし検出について説明する。
【００５２】
図６は、第１の実施の形態における電子透かし検出装置の構成例を示す。
【００５３】
電子透かし検出装置４００は、前述の電子透かし埋め込み装置２００を用いて得られる電子すかし埋め込み済み信号に、平行移動、拡大・縮小、回転、アスペクト比変更、アフィン変換等の一次変換、一部切り取り、非可逆圧縮などの処理が施された信号から、埋め込まれた電子透かしを検出するための装置である。
【００５４】
同図に示す電子透かし検出装置４００は、一次変換パラメータ推定部４０１、幾何変換補正部４０２、平行移動量推定部４０３、埋め込み情報検出部４０４とから構成される。
【００５５】
電子透かしの検出処理は大きく次の段階を経て行われる。
【００５６】
図７は、第１の実施の形態における電子透かし検出処理のフローチャートである。
【００５７】
ステップ１０１）  一次変換パラメータ推定：
一次変換パラメータ推定部４０１において、入力信号の４０５の自己相関値を算出し、自己相関値がピークをとる点を探索することにより、信号に与えられた変形の一次変換パラメータを推定し、推定一次変換パラメータ４０６を求める。
【００５８】
ステップ１０２）  一次変換による幾何補正：
幾何変換補正部４０２において、入力信号４０５に対し、ステップ１０１で推定された一次変換パラメータ４０６に対する逆変換を施し、信号を幾何的に補正する。
【００５９】
ステップ１０３）平行移動量推定：
平行移動量推定部４０３において、ステップ１０２で補正された幾何変換補正済み信号４０７に対して平行移動量の全探索を行うことで、信号に与えられた平行移動量を推定し、推定平行移動量４０８を求める。
【００６０】
ステップ１０４）  埋め込み情報の検出：
埋め込み情報検出部４０４において、ステップ１０３で推定された推定平行移動量４０８に基づき、ステップ１０２で補正された幾何変換補正済み信号４０７から残りの埋め込み情報を検出し、透かし検出情報４０９を得る。
【００６１】
埋め込み情報の検出は、例えば、前述の特許文献１に述べられているような、幾何変換検出対象係数行列を生成し、検出対象係数行列と埋め込み情報のシンボルに対応して電子透かし埋め込みで用いられたシンボル系列との相関値を求めることによってなされるものであってもよい。
【００６２】
次に、一次変換パラメータ推定部４０１の処理について説明する。
【００６３】
図８は、第１の実施の形態における一次変換パラメータ推定部の構成例である。
【００６４】
同図に示す一次変換パラメータ推定部４０１は、自己相関関数値配列生成部５０１、固定フィルタ探索部５０２、９０度ペア探索部５０３、詳細信号フィルタ探索部５０４、変換パラメータ推定部５０５とから構成される。
【００６５】
一次変換パラメータ推定部４０１による一次変換パラメータの推定の手順の例を以下に示す。
【００６６】
図９は、第１の実施の形態における一次変換パラメータの推定手順のフローチャートである。
【００６７】
ステップ２０１）  まず入力された入力信号５０６に対し、自己相関関数値配列生成部５０１を用いて入力信号５０６の自己相関関数値配列５０８を計算する。
【００６８】
ここで、自己相関関数値配列とは、ｎ次元の離散データとして与えられた入力信号の自己相関関数を計算し、得られたｎ次元データを配列に格納したものである。自己相関関数値配列５０８の例を図１０に示す。改変として回転・拡大・縮小が加えられた２次元の画像信号（図１０（ａ））に対して求められた自己相関関数値配列を、自己相関関数値の値を画像の輝度として表現したものが図１０（ｂ）である。ここで、入力信号に予め埋め込まれていたパターンの周期性から、自己相関関数値配列に格子状のピーク点が現れていることがわかる。
【００６９】
自己相関関数値配列５０８の計算方法は、例えば、「樋渡涓二編『画像工学ハンドブック』朝倉書店(1986) p.240」に記載されている。入力信号を離散フーリエ変換して得られたパワースペクトルを逆拡散フーリエ変換するなどの公知の手順が知られていた。
【００７０】
また、本実施の形態では、信号に埋め込まれた埋め込み情報により構成されるパターンの自己相関ピークを検出することを目的としているが、信号に対して直接自己相関関数を計算して自己相関関数値配列を算出したのでは、埋め込まれたパターンに対する自己相関ピークが十分明確に現れない場合がある。そこで、目的の自己相関ピークを効率的に検出するため、自己相関関数値配列の計算の前に、入力信号５０６に対し、埋め込みパターンの周波数特性に応じたフィルタを適用するようにしてもよい。例えば、埋め込み情報が信号の高周波数領域に埋め込まれている場合には、高周波通過フィルタを適用し、更にクリッピング処理を施すようにしてもよい。高周波通過フィルタとしては例えば、図１１のラプラシアンフィルタを用いてもよい。
【００７１】
ステップ２０２）  ステップ２０１で得られた自己相関関数値配列５０８に対し、固定フィルタ探索部５０２を用いて、上位Ｎ個の自己相関ピーク点を探索する。
【００７２】
固定フィルタ探索部５０２では、ステップ２０１で得られた自己相関関数値配列５０８に対し、信号に埋め込まれた埋め込み情報により構成されるパターンの周波数分布と同様の周波数分布を持つフィルタのインパルス応答の空間領域での形状を模倣した形状の固定のフィルタを用いて自己相関関数値配列５０８をフィルタリング処理し、上記の配列の中でフィルタリング後の信号の大きさが最も強い点から順に上位Ｎ個を選択してピーク点候補５０９として出力する。
【００７３】
埋め込み情報により構成されるパターンが、後述する詳細フィルタ探索部５０４の説明の例に示すようなｓｉｎｃ関数に基づいた形状を持っている場合には、フィルタ形状としてｓｉｎｃ関数に基づく形状を模倣し、図１２に示す形状のフィルタを用いてもよい。
【００７４】
ここで模倣というのは、理想的なフィルタ形状に対し大まかな形状が似るように固定フィルタを構成することを指している。すなわち、後述の詳細フィルタ探索部５０４で行われるように、理想的なフィルタ形状は、自己相関関数値配列上の位置によって異なってくるが、それらを共通の固定形状のフィルタで代用するために、例えば、図１２の理想的なｓｉｎｃ関数形状に対して、中心値が大きく、１ピクセル隔てた周囲の値が小さいような固定フィルタを構成することを指している。
【００７５】
自己相関関数値配列に現れるピーク点がどれだけ原点から離れているかは、信号に加えられた改変１０７における拡大・縮小の量と、埋め込まれたパターン（例えば、図５の透かしパターン３０１）の大きさとによって決まる。例えば、２次元の画像信号に繰り返し埋め込まれたパターンの場合で、パターンの１辺の長さがL、信号に加えられた改変１０７に０．５倍の縮小から１．５倍の拡大までが含まれるとすると、自己相関関数値配列において原点から距離０．５Lから１．５Lまでの範囲にあるピーク点を探索すればよい。
【００７６】
また、自己相関関数値の定義から自己相関関数値配列において原点対称な位置の自己相関関数値は共通であることから、自己相関関数値配列において２つの象限のみの探索を行えば十分である。
【００７７】
例えば、固定フィルタ探索部５０２でのピーク点探索範囲を図１３の太線で囲まれた枠内に限って行うようにしても構わない。
【００７８】
固定フィルタによるフィルタリング処理は、後述する詳細フィルタによる処理と比較して高速に処理することが可能であり、処理負荷の高い以降の処理において無駄な演算処理を行うことを回避することができ、効率的な一次変換パラメータの推定が可能となる。
【００７９】
ステップ２０３）  ステップ２０２で得られたN個のピーク点候補５０９に対して、９０度ペア探索部５０３を用いて、原点から各点に対するベクトルが互いに直交し、かつ、上記ベクトルの長さが一致するような点のペアを探索し、信号に加えられた一次変換の基底ベクトルの表す基底ベクトル候補５１０として選択する。但し、想定される信号に対して与えられた改変の量に応じて、上記の直交関係、ベクトルの長さの一致についてマージンを持たせて判定を行ってもよい。
【００８０】
基底ベクトル候補探索の概念を図１４に示す。図１４（ａ）、（ｂ）それぞれにおいて、矩形領域全体が自己相関関数値配列５０８を表し、矢印の交点に原点があるとする。図１４（ａ）の各点がステップ２０２で得られたピーク点候補とする。これらのピーク点候補の中から基底ベクトル候補５１０を選択した結果が図１４（ｂ）に示されており、ここでは２組の基底ベクトル候補が得られている。
【００８１】
９０度ペア探索部５０３の具体的な実現例については後述する。
【００８２】
なお、ここでは、埋め込み情報により構成されるパターンが、信号に正方格子状をなすように埋め込まれている場合の例を示しているが、埋め込みが異なる形状（例えば長方形や平行四辺形状）に行われた場合には、上記の手順において直交関係の代わりに埋め込み形状によって定まる所定の角度、ベクトルの長さの一致の代わりに埋め込み形状によって定まる所定のベクトル長の比を持つ点を選択するようになっていてもよい。
【００８３】
ステップ２０４）  ステップ２０３で得られた基底ベクトル候補５１０に対して、詳細フィルタ探索部５０４を用いてより詳細に候補を絞り込む。具体的には基底ベクトル候補中の各点の周囲の自己相関関数値に対して、予め信号に埋め込まれたパターンの周波数分布と同様の周波数分布を持つインパルス応答の空間領域での形状を持つフィルタを用いて各点に対応する評価値を算出する。各基底ベクトル候補について、基底ベクトル候補に含まれる２点の上記評価値の和を求め、和の値の大きい上位Ｍ組の基底ベクトル候補を選択し、推定基底ベクトル５１１とする。
【００８４】
詳細フィルタ探索５０４の具体的な実現例については後述する。
【００８５】
ステップ２０５）  変換パラメータ推定部５０５を用いて、ステップ２０４で得られた推定基底ベクトル５１１に基づいて信号に加えられた改変の一次変換パラメータを算出する。具体的には、信号に改変が加えられていないと仮定した場合の基底ベクトル位置（図１５（ａ））がステップ２０４で得られた基底ベクトル（例えば、図１５（ｂ））もしくは、その原点に対する対称点から構成されるいずれかのベクトルの組に変換されるような一次変換パラメータを求めればよく、この例の場合、ステップ２０４で得られた基底ベクトルが（ｘ１、ｙ１）、（ｘ２、ｙ２）であるとき、推定一次変換パラメータ行列は、
【００８６】
【数１】
2006295473.tif 000003
の４種類となる。
【００８７】
ここで、埋め込み情報検出部４０４が、信号が鏡像及び９０度回転されたものであっても埋め込み情報の検出が行えるように構成されているならば、上記行列のうち１通りのみを推定一次変換パラメータとして出力するようにしてもよい。
【００８８】
なお、ここでは、埋め込み情報により構成されるパターンが、信号に正方格子状をなすように埋め込まれている場合の例を示しているが、埋め込みが異なる形状（例えば長方形や平行四辺形）に行われた場合には、信号に改変が加えられていないと仮定した場合の基底ベクトル位置が図１５（ａ）とは異なった物となってくることに対応し、上記の推定一次変換パラメータ行列の計算式が他の形に変化していくことはいうまでもない。
【００８９】
上記で定められた推定一次変換パラメータ５０７を、一次変換パラメータ推定部４０１の出力として出力する。
【００９０】
次に、９０度ペア探索部５０３の実現例を説明する。
【００９１】
９０度ペア探索部５０３は、具体的には次のような手順を実施することで実現できる。
【００９２】
図１６は、第１の実施の形態における９０度ペア探索部の実現例のフローチャートである。
【００９３】
ステップ１２０１）  ９０度ペア探索部５０３の出力値である基底ベクトル候補を蓄積する集合λを空集合とし、ηを固定フィルタ探索部５０２で得られたピーク点の候補５０９の集合ξと等しい集合とする。
【００９４】
ステップ１２０２）  集合ηから一つのピーク点候補ｘ”を任意に取り出し、ηからは今取り出したｘ”を取り除く。
【００９５】
ステップ１２０３）  ｘ”を反時計回りに９０度回転した位置ｚを求める。
【００９６】
ステップ１２０４）  ξからｘ”を除いた要素の集合をζとする。
【００９７】
ステップ１２０５）  ζから一つのピーク点候補ｙ”を任意に取り出し、ζからは今取り出したｙ”を取り除く。
【００９８】
ステップ１２０６）  ｙ”がｚの近傍に存在するかどうかを判定する。近傍かどうかの判定基準は、信号に対する改変１０７としてどの程度の量のアスペクト比変更などの改変が行われた場合まで一次変換パラメータの推定を可能とするかに応じて広がりを持った領域内に存在するかどうかを判定基準とする。
【００９９】
近傍かどうかの具体的な判定基準については後述する。
【０１００】
ステップ１２０７）  ｙ”がｚの近傍と判定された場合は、（ｘ”，ｙ”）の組をλに追加する。
【０１０１】
ステップ１２０８）  ζが空になったかを判定し、空でなければ空になるまでステップ１２０５からステップ１２０８までを繰り返す。
【０１０２】
ζが空になった場合は、ステップ１２０９に移行する。
【０１０３】
ステップ１２０９）  ηが空になったかを判定し、空でなければηが空になるまでステップ１２０２からステップ１２０９を繰り返す。
【０１０４】
ηが空になった場合は、ステップ１２１０に移行する。
【０１０５】
ステップ１２１０）  それまでにλに蓄積された基底ベクトル候補５１０を出力して終了する。
【０１０６】
ここで、ピーク点候補５０９が、自己相関関数配列５０８中でｙ＞０の範囲に限られるように固定フィルタ探索部５０２が構成されているならば、ηはｘ＞０、ｙ＞０の範囲に限定して選択すれば十分であり、ステップ１２０１においてη←ξとする代わりに
η←｛（ｘ，ｙ）│（ｘ，ｙ）∈ξかつｘ＞０かつｙ＞０｝
とされていれば効率がよい。ピーク点候補５０９の存在範囲とステップ１２０３での回転方向に対応して、ここで限定して選択すべき範囲が変わってくることはいうまでもない。
【０１０７】
なお、上記の集合λ、η、ζ、ξは、メモリ等の記憶手段（図示せず）に格納されるものとする。
【０１０８】
上記のステップ１２０６における近傍の判定方法について、以下に説明する。
【０１０９】
図１７は、第１の実施の形態における９０度ペア探索における近傍の定義の例を示す。
【０１１０】
図１７（ａ）において、信号に対する改変１０７としてアスペクト比変更を含まない改変１３０１がなされた場合に、自己相関関数値配列５０８のピークが表す基底ベクトルをｘ及びｙで表す。また、信号に対する改変１０７として、上記の改変１３０１の前後にアスペクト比変更を更に加えた改変１３０２がなされた場合に、自己相関関数値配列５０８のピークが表す基底ベクトルをｘ”及びｙ”で表す。また、ｘ”を９０度回転された位置をｚとする。
【０１１１】
ここで、改変１３０２が加えられた場合に、実際にピーク点候補５０９として観測されるピーク点はｘ”やｙ”であるから、ステップ１２０６においては、想定されるアスペクト比変更の範囲でｚとｙ”がとりうる位置関係の範囲内であれば近傍にあると判断することができる。
【０１１２】
改変１３０２において、改変１３０１の前後に行われるアスペクト比変更をそれぞれ下記のＡ，Ｂに表す。
【０１１３】
【数２】
2006295473.tif 000004
とすると、ｙ”はｚを用いて次のように表される。
【０１１４】
【数３】
2006295473.tif 000005
α，βが１−ａ≦α≦１＋ａ，１−ｂ≦β≦１＋ｂ（但し、０＜ａ＜１，０＜ｂ＜１）を動くとき、ｚ＝（ｘ０，ｙ０）に対してｙ”＝（ｘ１，ｙ１）が動く範囲は図１７（ｂ）の双曲線と直線に囲まれた領域になる。
【０１１５】
従って、ステップ１２０６においては、与えられたｙ”，ｚに対して、ｙ”がzを囲む図１７（ｂ）の領域内に存在する場合に近傍にあると判定すればよい。
【０１１６】
なお、領域の判定を簡略化するため、図１７（ｂ）の領域をおおよそ含むような他の図形領域、例えば、台形領域や扇形領域等を定め、その範囲で近傍の判定を行うようになっていてもよい。さらに、演算を高速に処理するために判定を整数演算だけで行えるように式を変形して処理を行ってもよいことは言うまでもない。例えば、図１７（ｃ）の曲線で囲まれた扇形を切り取ったような領域をもって判定するとするならば、次式Ｆ１，Ｆ２，Ｆ３，Ｆ４の正負で判断するようにされていてもよい。
【０１１７】
Ｆ１＝ｂｍ２ｙ０ｘ−（ｂｍ−ｂｎ）２ｘ０ｙ
Ｆ２＝ｂｍ２ｙ０ｘ−（ｂｍ＋ｂｎ）２ｘ０ｙ
Ｆ３＝（ａｍ＋ａｎ）２（ｘ０２＋ｙ０２）−ａｍ２（ｘ２＋ｙ２）
Ｆ４＝（ａｍ−ａｎ）２（ｘ０２＋ｙ０２）−ａｍ２（ｘ２＋ｙ２）
但し、α＝１／α’、１−ａ’≦α’≦１＋ａ’とし、ａ’＝ａｎ／ａｍ，ｂ−ｂｎ／ｂｍ，ａｎ，ａｍ，ｂｎ，ｂｍは整数とする。
【０１１８】
次に、詳細フィルタ探索部５０４の実現例を説明する。
【０１１９】
自己相関関数値配列５０３は、元の信号に対するパワースペクトルの逆フーリエ変換として表されることから、自己相関関数値の周波数分布は信号に埋め込まれた透かしパターン（例えば、図５の透かしパターン３０１）の持つ周波数帯域形状と同様になることは自明である。特に、繰り返しタイリングして埋め込まれた透かしパターンの場合、自己相関関数値には周期的なインパルス状ピークが現れる。
【０１２０】
空間領域で繰り返すパターンのフーリエ変換は、周波数領域では疎に繰り返されるインパルス状の周波数分布になることが一般的に知られており、図１８の埋め込みパターンを繰り返しタイリングした埋め込みパターン（ｄ）の周波数分布は、同図の（ｃ）のようになる。
【０１２１】
観測される自己相関関数値配列５０８が、信号に対する改変１０７を受けたものであることを考えると、改変のない場合の基底ベクトル位置（ｘ０，ｙ０）が（ｘ，ｙ）に移される改変量Ａ（ｘ，ｙ）に対応した周波数領域での改変量Ｂ（ｘ，ｙ）を考え、元の周波数領域形状（ｃ）をＢ（ｘ，ｙ）で変換させ、パワースペクトル化した形状（ｇ）が、自己相関関数値（ｈ）の周波数分布となることがわかる。よって上記形状（ｇ）の帯域通過フィルタを用いて自己相関関数値配列５０８をフィルタリングして得られる信号値の大きさによって、自己相関関数値配列５０８に図１８の（ｈ）のようなピークが現れているかどうかを判断することができる。
【０１２２】
従って、詳細フィルタ探索部５０４に入力された基底ベクトル候補５１０のそれぞれに対して、基底ベクトル候補の位置に対応して変換された周波数領域での形状（ｇ）を持つ帯域通過フィルタを構成し、自己相関関数値配列生成部５０１の計算過程で得られたパワースペクトルをフィルタリングした後に、逆フーリエ変換を施し、基底ベクトル位置の信号強度を持って各基底ベクトル候補５１０の評価値とすればよい。
【０１２３】
次に、図７のステップ１０３の平行移動量推定の具体的な動作を説明する。
【０１２４】
平行移動量推定部４０３における平行移動量の推定は、次のように構成することができる。
【０１２５】
例えば、２次元の画像信号に対する透かし埋め込みの場合を考える。図５のように透かしパターンが信号中に繰り返し埋め込まれているため、透かしパターン３０１の大きさがｎ×ｎであれば、（０，０）から（ｎ−１，ｎ−１）の平行移動量の全てに対して電子透かしの検出を試行し、検出できたときの平行移動量をもって、改変１０７として与えられた平行移動量とすればよい。
【０１２６】
ここで、電子透かしの検出の試行により検出できたかどうかの判断は、検出結果の精度を示す値が所定の閾値を越えているかどうかで判断してもよい。また、上記検出結果の精度を表す値が最大となったときの平行移動量を持って検出できたと判断してもよい。例えば、前述の特許文献１の第２の実施例において述べられているようなシンボル検出部を用いて電子透かしの検出を行う場合には、上記特許文献１におけるシンボル系列と検出対象系列との相関値を上記検出結果の精度を表す値として用いても良い。
【０１２７】
図１９は、第１の実施の形態における平行移動量推定部の動作のフローチャートである。
【０１２８】
ステップ１５０１，１５０２，１５０３）  検出結果精度の最大値を保存する変数ｍａｘ及びオフセット位置ｘ、ｙを０に初期化する。但し、検出結果精度が負数も取りうるように構成されている場合は、ｍａｘに検出結果精度が取りうる最小の値を設定する。
【０１２９】
ステップ１５０４）  信号に対する改変１０７として（ｘ，ｙ）の平行移動が行われていると仮定した場合の透かし検出を実施し、検出結果の精度を表す値をｐに代入する。
【０１３０】
ステップ１５０５）  ｐがｍａｘよりも大きいかどうか判定し、大きくない場合はステップ１５０８に移行する。大きい場合はステップ１５０６に移行する。
【０１３１】
ステップ１５０６）  ｍａｘにｐを代入し、そのときの平行移動量ｘ，ｙをそれぞれｍｘ，ｍｙに代入して保存する。
【０１３２】
ステップ１５０７）  さらに、ｍａｘが予め決められた所定の閾値を越えているかを判定し、超えている場合はステップ１５１３に移行する。越えていない場合はステップ１５０８に移行する。
【０１３３】
ステップ１５０８）  横方向のオフセットｘに変位ｄｘを加える。ピクセル単位に変更移動量を推定する場合はｄｘは１でよい。
【０１３４】
ステップ１５０９）  ｘがｎ未満の場合はステップ１５０４に戻り、ｘがｎに達するまでステップ１５０４〜ステップ１５０８を繰り返す。
【０１３５】
ステップ１５１０）  縦方向のオフセットｙにｄｙを加える。ピクセル単位に平行移動量を推定する場合は、ｄｙは１でよい。
【０１３６】
ステップ１５１１）  ｙがｎ未満の場合はステップ１５０３に戻り、ｙがｎに達するまでステップ１５０３〜ステップ１５１０を繰り返す。
【０１３７】
ｙがｎに達した場合には、ステップ１５１２で最大の検出結果精度値を与えた平行移動量ｍｘ，ｍｙを推定平行移動量４０８として出力する。
【０１３８】
ステップ１５０７において、ｍａｘが閾値を越えていた場合に、ステップ１５１３〜ステップ１５２１の手順によって、全ての平行移動量を探索することなしに推定平行移動量を決定するようになっていてもよい。
【０１３９】
ステップ１５１３，１５１４）  変位量ｘｘ，ｙｙにそれぞれ−ｋを代入する。
【０１４０】
ステップ１５１５）  信号に対する改変１０７として（ｘ＋ｘｘ、ｙ＋ｙｙ）の平行移動が行われていると仮定した場合の透かし検出を実施し、検出結果の精度を表す値をｐに代入する。
【０１４１】
ステップ１５１６）ｐがｍａｘよりも大きいかどうかを判定し、大きくない場合はステップ１５１８に移行する。大きい場合は、ステップ１５１７に移行する。
【０１４２】
ステップ１５１７）  ｍａｘにｐを代入し、そのときの平行移動量ｘ＋ｘｘ，ｙ＋ｙｙをそれぞれｍｘ，ｍｙに代入して保存する。
【０１４３】
ステップ１５１８）  横方向の変位量ｘｘに変位ｄｘを加える。ピクセル単位に平行移動量を推定する場合はｄｘは１でよい。
【０１４４】
ステップ１５１９）  ｘｘがｋ以下の場合は、ステップ１５１５に戻り、ｘｘがｋに達するまでステップ１５１５〜ステップ１５１８を繰り返す。
【０１４５】
ステップ１５２０）  縦方向の変位量ｙｙにｄｙを加える。ピクセル単位に平行移動量を推定する場合はｄｙは１でよい。
【０１４６】
ステップ１５２１）  ｙｙがｋ以下の場合は、ステップ１５１４に戻り、ｙｙがｋに達するまでステップ１５１４〜ステップ１５２０を繰り返す。
【０１４７】
ｙｙがｋに達した場合には、ステップ１５１３〜ステップ１５２１によって、閾値を越えたオフセット位置（ｘ，ｙ）の近傍について検出を実施し、その中で最大を採った平行移動量を以て推定平行移動量とすることで、効率的に推定平行移動量を決定することができる。
【０１４８】
さらに、前述の特許文献１に述べられているように、電子透かし情報を複数のシンボルに分割して信号を埋め込んでいる場合は、複数のシンボルのうちの１つについて、上記の平行移動量探索を実施し、その結果得られた平行移動量を推定平行移動量４０８として出力し、残りのシンボルの検出処理は埋め込み情報検出部４０４で実施することで、効率的に電子透かしの検出を行うことができる。
【０１４９】
［第２の実施の形態］
本実施の形態では、前述の第１の実施の形態における詳細フィルタ探索部５０４を、より効率的に処理するための構成例を説明する。
【０１５０】
用語の定義、詳細フィルタ探索部５０３以外の構成については第１の実施の形態と同様である。
【０１５１】
上記の第１の実施の形態における詳細フィルタ探索部５０４の実現方法では、基底ベクトルの候補それぞれに対して逆フーリエ変換処理を実施する必要があるために処理に非常の時間がかかる上、パターンの繰り返しに対応して決まる周波数分布でのインパルス状ピークの繰り返し形状を持つフィルタは、離散フーリエ変換の丸め誤差の問題から精度よく構成することが困難であるという問題がある。
【０１５２】
そこで、周波数領域でのフィルタリングを行う代わりに空間領域の候補点周囲の所定の範囲に対してフィルタリングを行うことで、より効率的に詳細フィルタ探索部５０４を実現してもよい。
【０１５３】
以下に、２次元信号に対する詳細フィルタ探索を例に説明する。
【０１５４】
埋め込みパターンが図１８（ａ）のような周波数分布を持っている場合、回転のみ加えられた後の自己相関関数値（図２０の（ａ））に現れる個々のピークは、図２０（ｂ）のような周波数分布を持つ。矩形領域通過ローパスフィルタのインパルス応答がｓｉｎｃ関数
【０１５５】
【数４】
2006295473.tif 000006
となることから、ピークの空間領域での形状は、図２０（ｃ）のようなｓｉｎｃ関数の形状となる。但し、図２０（ｃ）は簡略化のため一次元で表現している。
【０１５６】
また、自己相関関数値配列５０８に現れる自己相関ピークの形状は、信号に埋め込まれた透かしパターン（例えば、図５の透かしパターン３０１）が、信号に対する改変１０７に伴ってどれだけ拡縮されているかによってなだらかになったり鋭くなったりする。これは拡縮によって透かしの情報の埋め込まれている周波数帯域がシフトすることによる。この様子を図２０（ｄ）〜（ｆ）に示す。
【０１５７】
０．５倍に縮小され回転を加えられた後の自己相関ピーク（図２０（ｄ））に基底ベクトルとして現れる個々のピークは、図２０（ｅ）のような周波数分布を持ち、その結果、ピークの空間領域での形状は図２０（ｆ）のように、１．０倍の時よりも鋭敏なｓｉｎｃ関数の形状となる。また、これらの２次元空間での形状は、信号に加えられた回転と同じだけ回転した形となっている。
【０１５８】
従って、理論的なピーク形状は、自己相関ピークの出現する位置に対応する改変量毎に決まるｓｉｎｃ関数の形状で表現できることになる。
【０１５９】
図１８（ａ）の周波数分布に対する空間領域形状は、矩形領域通過ローパスフィルタを組み合わせることで、逆フーリエ変換なしにｓｉｎｃ関数を用いて容易かつ高速に求めることができる。すなわち、埋め込みパターンの周波数分布（図１８（ａ））を持つフィルタを、複数の矩形領域通過型ローパスフィルタの並列型及び直列型のフィルタとして考え、さらに、並列型、直列型フィルタのインパルス応答は、空間領域における各フィルタのインパルス応答の和及び積で表現されることから、目的の理論的ピーク形状は各矩形領域通過型ローパスフィルタのインパルス応答であるｓｉｎｃ関数形状の和及び積の演算のみで求めることができる。
【０１６０】
さらに、対象としているピーク点位置に応じた回転量及び拡大縮小量に応じて、空間領域での回転、拡大縮小の座標変換を行うことで、目的の理論的ピーク形状を求めることができる。
【０１６１】
なお、演算で用いられるｓｉｎｃ関数の範囲は対象の周波数範囲によって限られているため、ｓｉｎｃ関数値はルックアップテーブルの形で表現することもでき、その場合さらに高速な処理が可能となる。
【０１６２】
上記で得られた理論的ピーク形状を用い、基底ベクトル候補５１０の各点に対して、候補点位置に応じた理論的な空間形状と各点の周囲の所定の領域の自己相関関数値との相関値を求めるようなフィルタリングを行うことで、基底ベクトル候補それぞれに対する逆フーリエ変換を必要とせずに、空間領域での相関演算のみにより効率的に評価値を求めることができる。例えば、図２１（ａ）の自己相関関数値配列１７０１に対し、候補点位置に応じて決まる理論的周波数分布から得られるピーク形状１７０２との相関値を求める。図２１は、１次元信号の例を示しているが、ｎ次元の信号の場合でも同様であることは言うまでもない。
【０１６３】
さらに、自己相関関数値系列５０８は、離散的な点の集合として表現されるため、基底ベクトル候補５１０も格子点の上の点として与えられるが、本当の基底ベクトル位置は格子点の中間位置にある場合もあり、基底ベクトル候補５１０の各点に対して微小のズレ量を考え、ズレ量を動かしたときにピーク形状と自己相関関数値配列との相関値が最大となるズレ量を求め、改めて基底ベクトル候補点として定めることでより精度の高い基底ベクトルを求めるようにしてもよい。例えば、図２１（ｂ）の自己相関関数値配列１７０４に対し、基底ベクトル候補点から左方向に微小にずれた位置をピークとする理論的ピーク形状１７０５との相関値を求めるものである。
【０１６４】
二次元信号の場合には、基底ベクトル候補５１０の各点について、ｘ方向及びｙ方向に例えば格子点間隔ａの１／１０のサブピクセルを単位に順に変位させ、各位置においてそれぞれピーク点が存在すると仮定したときの理論的ピーク形状と、観測された自己相関値との相関を、元の基底ベクトル候補の点の周囲の格子点について畳み込み演算により求め、相関値の最も大きいものを評価値とすればよい。また、そのときの変位量を以て、基底ベクトル候補の位置を補正してもよい。
【０１６５】
［第３の実施の形態］
本実施の形態では、前述の第１及び第２の実施の形態における一次変換パラメータ推定部４０１をより高精度に処理するための構成例を以下に示す。
【０１６６】
用語の定義、一次変換パラメータ推定部４０１以外の構成、及び一次変換パラメータ推定部４０１の下記に述べられていない部分の構成は、第１及び第２の実施の形態と同様である。
【０１６７】
前述の第１及び第２の実施の形態の一次変換パラメータ推定部４０１において、詳細フィルタ探索部５０４の出力する推定基底ベクトル５１１には、本来の基底ベクトルに従属して得られるピーク点を誤って基底ベクトルとして含んでしまう場合がある。ここで、本来の基底ベクトルに従属して得られるピーク点とは、例えば、図２２の正解基底ベクトル（ａ）の線形結合として表されるピーク点（ｂ）を指す。こうした点で構成される基底ベクトル候補についても詳細フィルタ探索部で高い評価値が得られる可能性があるが、このような基底ベクトル候補からは正しい推定一次変換パラメータを得ることはできず、その結果、電子透かしの検出に失敗してしまう可能性がある。本実施の形態では、このような基底ベクトル候補を除去する例を説明する。
【０１６８】
図２３は、第３の実施の形態における従属ピーク点除去を行う一次変換パラメータ推定部の構成例を示す。
【０１６９】
同図に示す構成は、図８の一次変換パラメータ推定部４０１に、従属ピーク点除去部１９１２を加えた構成である。
【０１７０】
従属ピーク点除去部１９１２は、詳細フィルタ探索部１９０４（図８の詳細フィルタ探索部５０４と同じ）の出力した推定基底ベクトル１９１１の中から、従属ピーク点になるような基底ベクトルの候補を除去し、残されたものを従属ピーク点を除去された推定基底ベクトル１９１３として出力する。
【０１７１】
また、従属ピーク点になるような基底ベクトルを除去する代わりに、本来の基底ベクトルに対応して詳細フィルタ探索部１９０４において得られた評価値と従属ピーク点になるような基底ベクトルに対して得られた評価値とに基づき、本来の基底ベクトルの評価値が、従属ピーク点となっている基底ベクトルの評価値よりも必ず大きくなるように、それぞれの評価値を変更させるようにしてもよい。このように評価値を変更することで、信号に対するノイズによって得られた誤った推定基底ベクトルに起因して正しい基底ベクトルを推定基底ベクトル１９１１から除去してしまい、透かしの検出に失敗することを防止することができる。
【０１７２】
変換パラメータ推定部１９０５は、従属ピーク点除去部１９１２が出力した従属ピーク点を除去された推定基底ベクトル１９１３に基づいて、推定一次変換パラメータ１９０７を求める。
【０１７３】
図２４は、第３の実施の形態における従属ピーク点除去部の動作のフローチャートである。
【０１７４】
ステップ２００１）  詳細フィルタ探索部１９０４が出力した推定基底ベクトル１９１１のペア（ｘ，ｙ）の集合をξとする。
【０１７５】
ステップ２００２）  ηをξと同じ要素を持つ集合とする。
【０１７６】
ステップ２００３）  ηから一つの推定基底ベクトルのペア（ｘ，ｙ）を任意に取り出し、ηからは今取り出した（ｘ，ｙ）を取り除く。
【０１７７】
ステップ２００４）  ξの中で（ｘ，ｙ）以外の全ての要素を持つ集合をζとし、これから探索する従属ピーク点を蓄積する集合ωを空集合とする。
【０１７８】
ステップ２００５）  ζから一つの推定基底ベクトルのペア（ｘ’，ｙ’）を任意に取り出し、ζからは今取り出した（ｘ’，ｙ’）を取り除く。
【０１７９】
ステップ２００６）  （ｘ’，ｙ’）が（ｘ，ｙ）の従属位置にあって、且（ｘ，ｙ）に対して詳細フィルタ探索部１９０４において求められた評価値ｐ［（ｘ，ｙ）］が、（ｘ’，ｙ’）に対する評価値ｐ［（ｘ’，ｙ’）］よりも小さいかどうか判定する。
【０１８０】
条件が成立しない場合は、ステップ２００８に移行する。条件が成立した場合はステップ２００７に移行する。
【０１８１】
ステップ２００７）  従属ピーク点を蓄積する集合ωに（ｘ’，ｙ’）を追加し、ステップ２００８に移行する。
【０１８２】
ステップ２００８）  ζが空になったかどうかを判定し、空になっていない場合は、ステップ２００５に戻り、空になるまでステップ２００５〜２００８を繰り返す。
【０１８３】
ζが空になった場合は、ステップ２００９に移行する。
【０１８４】
ステップ２００９）  次のように各推定基底ベクトルの評価値を変更する。
【０１８５】
・（ｘ，ｙ）の評価値ｐ［（ｘ，ｙ）］を見つかった従属ピーク（すなわちωに含まれる全ての推定基底ベクトルのペア）の評価値の中で最大の評価値に変更する。
【０１８６】
・見つかった従属ピーク（すなわちωに含まれる全ての推定基底ベクトルのペア）の評価値ｐ［（ｘ’，ｙ’）］を（ｘ，ｙ）の上記の変更前の元の評価値に変更する。
【０１８７】
すなわち、元の推定基底ベクトルの評価値が、従属ピーク点となっている推定基底ベクトルの評価値よりも必ず大きくなるように変更することで、従属ピーク点が優先されて検出が行われることが無いようにすることができる。
【０１８８】
ステップ２０１０）  ηが空集合になっているかを判定し、空集合になっている場合は、ステップ２００３に移行し、ηが空になるまでステップ２００３〜ステップ２０１０を繰り返す。
【０１８９】
なお、上記の集合η、ζ、ξ、ωは、メモリ等の記憶手段（図示せず）に格納されるものとする。
【０１９０】
ここで、ステップ２００９では、元の推定基底ベクトルの評価値と従属ピーク点となっている推定基底ベクトルの評価値が交換されるような例を示しているが、元の推定基底ベクトルの評価値が、従属ピーク点となっている推定基底ベクトルの評価値よりも必ず大きくなるように変更されるような変更の仕方であれば他の変更の仕方であっても構わない。例えば、元の推定基底ベクトルの評価値を従属ピーク点となっている推定基底ベクトルの最大の評価値の１．１倍の評価値とし、従属ピーク点となっている推定基底ベクトルの評価値を変更しないようにされていてもよい。
【０１９１】
また、ステップ２００６の判定条件として、（ｘ’，ｙ’）に対する評価値ｐ［（ｘ’，ｙ’）］と（ｘ，ｙ）に対する評価値ｐ［（ｘ，ｙ）］の比あるいは、差が所定の閾値未満であることを条件に加えても良い。通常、従属ピーク点と元のピーク点とは自己相関関数値配列１９０８において、同程度のピークとして得られるため、極端に評価値に差がある場合には（ｘ，ｙ）の基底ベクトルは何らかのノイズによって得られた誤った基底ベクトルである可能性がある。このため、上記のような条件を加えることで、評価値が大きく離れすぎている場合には、該当する基底ベクトルについては従属ピーク点除去の処理を行わずに、誤って正しい基底ベクトルを除去してしまうことを防ぐことができる。
【０１９２】
なお、ここでは評価値ｐの値が大きいほど基底ベクトルであることが確からしいことを表すことを前提として説明したが、逆に、評価値ｐの値が小さいほど基底ベクトルであることが確からしいことを表す評価指標を用いている場合には、評価値の増減の仕方が逆になることは言うまでもない。
【０１９３】
最後に従属位置の例を示す。
【０１９４】
図２５は、第３の実施の形態における従属位置を示す。基底ベクトルペア（Ａ，Ｂ）が第１及び第２象限に限定された場合、２倍の距離にある格子点まで考慮すると、誤認識する可能性のあるペアは、図２５（ａ）〜（ｋ）のいずれかの場合がある。
【０１９５】
［第４の実施の形態］
図２６は、本発明の第４の実施の形態における電子透かし検出装置の構成例を示す。
【０１９６】
同図に示す本発明の電子透かし検出装置２２００は、信号縮小部２２０１、自己相関関数計算部２２０２、自己相関関数値正規化部２２０３、自己相関ピーク点評価部２２０４、自己相関ピーク点評価値正規化部２２０５、検出対象決定部２２０６、幾何補正部２２０７、埋め込み情報検出部２２０８とから構成される。
【０１９７】
本実施の形態における電子透かしの検出処理は、大きく次の段階を経て行われる。
【０１９８】
図２７は、本発明の第４の実施の形態における電子透かし検出処理のフローチャートである。
【０１９９】
ステップ４０１）  信号縮小：
電子透かし検出装置２２００に入力された入力信号２２０９を、信号縮小部２２０１において、１倍、１／２倍、１／４倍，…，１／ｎ倍のように複数サイズに縮小する。
【０２００】
縮小とは、例えば、２次元の画像信号であった場合、画像のサイズが空間的に小さくなるように縮小する。画像の縮小は、例えば、文献「樋渡涓二編『画像工学ハンドブック』朝倉書店(1986).p.216」に記載されている幾何学的変換である伸縮として表現され、最近傍法、線形補間法などの補間処理が行われても構わない。
【０２０１】
ここで、図２６の構成例では、縮小率を１／２のべき乗として例を挙げているが、後の幾何補正部２２０７における補正と対応した値であればどのような縮小率を用いても構わない。例えば、１／１．５倍、１／３倍、１／５倍となるように構成してもよい。
【０２０２】
以降、信号縮小部２２０１で得られた各縮小信号毎に処理を行うが、それぞれの縮小信号に対する処理を「レンジ」と称することにする。
【０２０３】
ステップ４０２）  自己相関関数計算：
自己相関関数計算部２２０２において、信号縮小部２２０１で得られた縮小信号のそれぞれに対して自己相関関数を計算する。自己相関関数値の計算方法には、例えば、入力信号を離散フーリエ変換して得られたパワースペクトルを逆離散フーリエ変換するなどの公知の手順が知られている。自己相関関数計算部２２０２は、第１の実施の形態における自己相関関数値配列生成部５０１に対応する。
【０２０４】
ステップ４０３）  自己相関関数値正規化：
自己相関関数値正規化部２２０３において、自己相関関数計算部２２０２で得られた自己相関関数値に対し、レンジ毎に値の正規化を行う。この正規化は、レンジ毎の自己相関関数値が、互いに同程度の分布を持つように正規化を行う。例えば、二次元の画像信号の場合を例に、例えば、５１２×５１２のサイズの離散フーリエ変換を用いて求めた自己相関関数値は、５１２×５１２のサイズの配列の形で得られるが、上記配列の各要素の値の分布が、各レンジにおいて平均値０、分散１．０となるように次のような値の変換を行う。
【０２０５】
【数５】
2006295473.tif 000007
但し、ｆ（ｘ，ｙ）は位置ｘ，ｙにおける自己相関関数値、ｍはｆ（ｘ，ｙ）の平均値、σはｆ（ｘ，ｙ）の標準偏差であり、ｆ’（ｘ，ｙ）は、位置ｘ，ｙにおける変換後の自己相関関数値とする。
【０２０６】
自己相関関数値の正規化を行うことにより、後に自己相関関数値に基づいて自己相関ピーク点評価部２２０４において算出される評価値が、各レンジの間で同程度の分布をとるようにすることができ、他のレンジの誤ったピーク点を高く評価してしまうことを抑制することができる。
【０２０７】
自己相関関数値ｆ（ｘ，ｙ）の平均ｍ、標準偏差σを求める際には、もともとの自己相関関数値の原点付近の値を無視して値を算出するようにされていてもよい。即ち、
【０２０８】
【数６】
2006295473.tif 000008
ここで、上記の式では原点付近を除く領域として原点からの距離が所定の値ｒを越えている
【０２０９】
【数７】
2006295473.tif 000009
であることを条件としたが、例えば、原点を囲む矩形領域を除く領域（│ｘ│＞ａ，│ｙ│＞ｂ）であることを条件としてもよいし、その他の定義であっても構わない。
【０２１０】
自己相関関数の原点付近の値は信号における自分自身との相関値であり、原点では必ず大きな値（相関値１．０）をとり、また、例えば、画像などの信号である画素と隣接する画素の相関が高いことから原点付近の自己相関値も比較的の大きな値を取ることが明らかであるが、改変の大きさを推定するためのピーク点探索においては原点の相関値は無意味であるため、これを取り除いた領域で正規化を行うことで、より効果的にレンジ間で評価値をそろえることができる。
【０２１１】
ステップ４０４）  自己相関ピーク点評価：
自己相関ピーク点評価部２２０４において、自己相関関数値正規化部２２０３で正規化された各レンジ毎の自己相関関数値を用いて、自己相関ピーク点の探索と各ピーク点候補についての評価値を算出する。
【０２１２】
ピーク点の探索とピーク点候補についての評価値の算出は、例えば、前述の特許文献３に記載されているような自己相関関数値にＨＰＦを適用した値を用いてもよいし、前述の第１・第２の実施の形態に示したような詳細フィルタ探索による評価値を用いてもよい。
【０２１３】
自己相関ピーク点評価部２２０４の出力としては、各レンジ毎に１つまたは複数のピーク点候補の位置と、それに対する評価値の組が出力される。また、前述の第１の実施の形態における９０度ペア探索部５０３により得られる基底ベクトル候補のように、ピーク点候補が信号の次元に応じた数の基底ベクトルの組（例えば、二次元の画像信号の場合２つの基底ベクトルのペア）として表されていてもよい。
【０２１４】
自己相関ピーク点評価部２２０４は、前述の第１の実施の形態における一次変換パラメータ推定部４０１の固定フィルタ探索部５０２、９０度ペア探索部５０３、詳細フィルタ探索部５０４に対応するが、本発明においてはこれらの各部と同じ構成をとっていることに限定しない。即ち、自己相関ピーク点評価部２２０４は、自己相関ピーク点の探索と各ピーク点候補についての評価値を算出するように構成されているならばどのように構成されていてもよく、第１の実施の形態とは異なるように構成されていても構わない。
【０２１５】
ステップ４０５）  自己相関ピーク点評価値正規化：
自己相関ピーク点評価値正規化部２２０５において、自己相関ピーク点評価部２２０４で得られた各評価値を、レンジ毎に正規化する。この正規化は、レンジ毎のピーク点候補の評価値が、互いに同程度の分布を持つように正規化を行う。例えば、ｎ個のレンジに対し、それぞれレンジ毎にｍ組ずつのピーク点候補ｐ１，１，…，ｐ１，ｍ，…，ｐｎ，１，…，ｐｎ，ｍが得られている場合、各レンジ毎に例えば、平均０、標準偏差１．０となるように正規化する。
【０２１６】
【数８】
2006295473.tif 000010
但し、ｅ（ｐｎ，ｍ）はピーク点候補ｐｎ，ｍに対する評価値ｅ’（ｐｎ，ｍ）はピーク点候補ｐｎ，ｍに対する正規化後の評価値、Ｍｎはｅ（ｐｎ，１），…，ｅ（ｐｎ，ｍ）の平均値、σｎはｅ（ｐｎ，１），…，ｅ（ｐｎ，ｍ）の標準偏差とする。
【０２１７】
このような自己相関ピーク点評価値の正規化を行うことにより、各ピーク点の評価値が各レンジの間で同程度の分布をとるようにすることができ、他のレンジの誤ったピーク点を高く評価してしまうことを抑制することができる。
【０２１８】
ステップ４０６）  検出対象決定：
検出対象決定部２２０６において、自己相関ピーク点評価値正規化部２２０５で得られた各ピーク点評価値を用い、後の埋め込み情報検出部２２０８において埋め込み情報の検出を行う対象とするピーク点候補を選択する。
【０２１９】
選択の方法は最も単純にはレンジを横断して各ピーク点の評価値の最も高いものから順に上位Ｋ個（Ｋ≧１）を選択するというものであってもよい。
【０２２０】
また、非常に近い位置、または、同一の位置にある複数のピーク点が候補にあがっている場合には、それらの重複を除去し、まとめて１つのピーク点候補とした上で、検出対象を決定するようにしてもよく、これにより後述する幾何補正の結果が殆ど同一となるものについて重複して埋め込み情報の検出を行うことを抑制でき、無駄のない検出が可能となる。
【０２２１】
ステップ４０７）  変換パラメータ算出と幾何補正：
幾何補正部２２０７において、検出対象決定部２２０６で決定された検出対象の各ピーク点候補に対応し、信号に対して加えられた改変量を表す変換パラメータを算出した上で、入力信号２２０９に対して上記変換パラメータによる改変の逆変換を施すことで、信号の補正を行う。これは、第２の実施の形態で述べたように、自己相関関数値のピーク点として現れる点は、信号に加えられた拡大・縮小、回転などの改変量に応じてその位置が決まることを利用している。
【０２２２】
このとき、各レンジ毎に、信号縮小部２２０１において入力信号を縮小した上で自己相関関数を計算していることを考慮して逆変換を行う。例えば、２次元の画像信号を例にとった場合、電子透かしとして信号に繰り返し埋め込まれたパターンが１２８×１２８ピクセルのサイズを持っていたとする。信号縮小部２２０１において、１／２に縮小したレンジで、自己相関関数値の（９６，０）及び（０，９６）の位置にピーク点が現れていた場合、これは本来（即ち信号を縮小せずに自己相関関数を計算した場合には）（１９２，０）（０，１９２）の位置にピーク点が現れていることを示しており、その結果、信号に対する改変としては１．５倍の拡大が行われていたということを表す。従って、この場合幾何補正部２２０７においては、入力信号２２０９に対して１／１．５の縮小を施すことになる。もし、１／４に縮小したレンジで自己相関関数値の同様の位置にピーク点が現れていた場合は、１／３．０の縮小を施すことになる。
【０２２３】
なお、検出対象決定部２２０６における検出対象決定と、幾何補正部２２０７における幾何補正は順序が逆であっても構わない。即ち、検出対象決定を行う前に自己相関ピーク点評価値正規化部２２０５で得られた全てのピーク点候補に対して幾何補正を行ってしまい、その上で実際に検出対象を決定するようにしてもよい。
【０２２４】
ステップ４０８）  埋め込み情報検出：
埋め込み情報検出部２２０８において、幾何補正部２２０７で得られた補正済み信号を元に、埋め込み情報の検出を行う。埋め込み情報の検出方法は、電子透かしの埋め込み方法に依存した任意の方法であってよい。例えば、前述の特許文献１による電子透かしの検出方法であってもよい。
【０２２５】
検出された情報に応じ、どの程度の検出精度で検出が行われたかを判断し、最も検出精度の高かった検出結果もしくは、検出精度が所定の閾値を越えていた検出結果を出力するようにされていてもよい。例えば、前述の特許文献１の第２の実施例に述べられているようなシンボル検出部を用いて電子透かし検出を行う場合には、当該特許文献１におけるシンボル系列と検出対象系列との相関値を、検出精度を表す値として用いても良い。
【０２２６】
また、処理を効率的に行うため、検出を行う対象について、自己相関ピーク点評価値正規化部２２０５で得られた評価値に応じて、評価値の大きな候補の修正済み信号から順に検出を施し、検出精度が所定の閾値を越えた時点で残りの検出処理を中止し、閾値を越えた検出の検出結果を出力するようにしてもよい。これにより、複数の候補が得られている場合にも効率的に埋め込み情報検出処理を実施することができると共に、正しいピーク点の自己相関ピーク点評価値が、誤ったレンジ、ピーク点の候補の評価値より若干低く評価されてしまうような場合においても、最終的に埋め込み情報検出を成功させることができ、信頼性の高い埋め込み情報検出を行うことができる。
【０２２７】
次に、上記のステップ４０６の検出対象決定処理と、ステップ４０８の埋め込み情報検出の効率化について説明する。
【０２２８】
複数のレンジのピーク点候補に対して、複数回の埋め込み情報検出処理を行うにあたり、評価値の正規化をもってしても発生し得るレンジ間で誤ったピークを選択してしまうことによる検出失敗を補償しつつ、検出処理にかかる時間の上限を限定する、効率的な検出対象決定方法について述べる。
【０２２９】
図２８は、本発明の第４の実施の形態における検出対象決定のフローチャートであり、図２９は、本発明の第４の実施の形態における検出対象決定の例を示す
ステップ２３０１）
・各レンジにおいて優先すべきピーク点候補の数Ｌ
・全体として埋め込み情報検出処理を実施する上限の回数Ｍ
を決定する。これらは、電子透かし検出装置２２００において固定値が設定されていてもよいし、あるいは、電子透かし検出処理の開始時に入力されるようにしてもよい。図２９は、各レンジ毎のピーク点候補と評価値、これらから決定される検出対象の例を示しており、ここでは、Ｌ＝２、Ｍ＝８としている。
【０２３０】
入力された自己相関ピーク点候補について、レンジ毎に次の処理を行う。ここで、処理対象となっているレンジをｉとする。
【０２３１】
ステップ２３０２）  ζｉをレンジｉの自己相関ピーク点候補の集合とし、ｘ∈ζｉにおいてｐ（ｘ）をｘに対するピーク点評価値とする。
【０２３２】
ステップ２３０３）  ｘ∈ζｉに対する自己相関ピーク点評価値ｐ（ｘ）の大きい物から順に上位Ｌ個のピーク点候補について、自己相関ピーク点評価値に所定の数値ｐ０を加算する。即ち、ｐ（ｘ）←ｐ（ｘ）＋ｐ０とする。このときｐ０の値はいずれの自己相関ピーク点評価値よりも大きな値をとるように予め決定しておく。例えば、図２９のレンジ１では評価値が２４１，２１２と大きかったピーク点候補（ｕ，ｖ）及び（ｘ，ｙ）についてｐ０として１００００を加算し、それぞれの評価値を、１００２４１，１００２１２に変更している。なお、図２９では、上述の重複の除去についても示されており、例えば、レンジ１では重複しているピーク点候補（ｘ，ｙ）のうち一つが除去されている。
【０２３３】
ステップ２３０４）  全てのレンジｉについて処理を行ったかを判定し、未処理のレンジがある場合はそのレンジをｉと置き換えてステップ２３０２〜ステップ２３０３を繰り返す。
【０２３４】
ステップ２３０５）  全てのレンジのピーク点候補の集合をηとする。
【０２３５】
ステップ２３０６）  ｘ∈ηに対する自己相関ピーク点評価値ｐ（ｘ）の大きいものから順に上位Ｍ個のピーク点候補を取り出し、その集合をζとする。例えば、図２９では、ピーク点候補（ｎ，ｏ），（ｕ，ｖ），（ｘ，ｙ），…，（ｃ，ｄ）の８個のピーク点候補が選ばれている。
【０２３６】
ステップ２３０７）  決定された検出対象としてζを出力する。
【０２３７】
このように上位Ｌ個のピーク点候補についてピーク点評価値を増加させるように変更することで、上位Ｌ個のピーク点候補を優先して埋め込み情報検出の対象とすることができる。これにより、各レンジのピーク点評価値において、正しいレンジの正しいピーク点候補の評価値よりも大きな評価値を持つ、誤ったレンジの誤ったピーク点候補が多数存在した場合にも、正しいレンジの上位にあるピーク点候補を優先して埋め込み情報検出の対象とすることができる。その結果、誤ったピーク点候補により検出に失敗することを抑制することができると共に、全体として検出を行うピーク点候補の上限数を所定の数に限定することができるため、全体の検出処理時間の上限を限定することができる。
【０２３８】
また、上記の構成によれば、例えば、
（ａ）Ｌ＝０，Ｍ＝１とすれば全てのレンジを通して最も評価の高い１個のピーク点候補についての埋め込み情報検出を行う。
【０２３９】
（ｂ）Ｌ＝０，Ｍ＝３とすれば全てのレンジを通して評価の高いものから３個のピーク点候補についての埋め込み情報検出を行う。
【０２４０】
（ｃ）Ｌ＝１，Ｍ＝レンジの個数とすれば、各レンジ毎に評価の最も高い１個のピーク点候補を選び、各レンジ１個ずつのピーク点候補についての埋め込み情報検出を行う。
【０２４１】
（ｄ）Ｌ＝２，Ｍ＝１０とすれば、各レンジ毎に評価の高いものから２個のピーク点候補を優先して、全体として１０個のピーク点候補についての埋め込み情報検出を行う。
【０２４２】
といったように様々な埋め込み情報検出方法を決定することができ、装置の構成の変更なしに、容易に検出動作を変更することが可能となる。
【０２４３】
特に、電子透かしの埋め込み対象となっている信号１０１に、例えば、画像の場合の繰り返し模様や直線などの自己相関性の強い信号が含まれている場合や、高い圧縮率で圧縮符号化されている場合などに、求めたい自己相関ピークが信号の持つ自己相関ピーク（偽ピーク）に埋もれてしまっている場合には、
（i）同一のレンジの中で偽ピークが多く含まれている場合；
（ii）正しいピークのレンジには偽ピークは少ないが、他のレンジに多く偽ピークが含まれている場合；
とが信号や通信路で与えられるノイズに依存して変化するため、条件に応じてどちらの可能性が高いかを考慮して埋め込み情報の検出を行うことが重要である。例えば、上記（ｂ）の方法は、上記（i）の場合に適しており、上記（ｃ）の方法は、上記(ii)の場合に適しているため、これを容易に変更できることで効率的な電子透かしの検出が可能となる。
【０２４４】
なお、上記の第１〜４の実施の形態における図６、図８、図２３、図２６に示す構成の動作をプログラムとして構築し、電子透かし検出装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０２４５】
また、構築されたプログラムをハードディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、コンピュータにインストールする、または、配布することも可能である。
【０２４６】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０２４７】
本発明は、電子透かし検出の技術に適用可能である。
【図面の簡単な説明】
【０２４８】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の背景となる電子透かし埋め込み・検出のモデルである。
【図４】第１の実施の形態における電子透かし埋め込み装置の構成例である。
【図５】第１の実施の形態における透かしパターンのタイリングの例である。
【図６】第１の実施の形態における電子透かし検出装置の構成図である。
【図７】第１の実施の形態における電子透かし検出処理のフローチャートである。
【図８】第１の実施の形態における一次変換パラメータ推定部の構成例である。
【図９】第１の実施の形態における一次変換パラメータの推定手順のフローチャートである。
【図１０】第１の実施の形態における自己相関関数値配列の例である。
【図１１】第１の実施の形態におけるラプラシアンフィルタの例である。
【図１２】第１の実施の形態における固定フィルタの形状の例である。
【図１３】第１の実施の形態における自己相関ピーク点の探索範囲の例である。
【図１４】第１の実施の形態における９０度ペア（基底ベクトル）候補探索の例である。
【図１５】第１の実施の形態における基底ベクトルからの変換パラメータ計算の例である。
【図１６】第１の実施の形態における９０度ペア探索部実現例のフローチャートである。
【図１７】第１の実施の形態における９０度ペア探索における近傍の定義の例である。
【図１８】第１の実施の形態における自己相関関数値の周波数分布の説明図である。
【図１９】第１の実施の形態における平行移動量推定部の動作のフローチャートである。
【図２０】第２の実施の形態における自己相関ピーク点形状の周波数分布である。
【図２１】第２の実施の形態におけるサブピクセル単位での基底ベクトル候補の評価値算出を説明するための図である。
【図２２】第３の実施の形態における基底ベクトルに従属するベクトルの認識誤りの例である。
【図２３】第３の実施の形態における従属ピーク点除去を行う一次変換パラメータ推定部の構成例である。
【図２４】第３の実施の形態における従属ピーク点除去部の動作のフローチャートである。
【図２５】第３の実施の形態における従属位置の例である。
【図２６】本発明の第４の実施の形態における電子透かし検出装置の構成例である。
【図２７】本発明の第４の実施の形態における電子透かし検出処理のフローチャートである。
【図２８】本発明の第４の実施の形態における検出対象決定処理のフローチャートである。
【図２９】本発明の第４の実施の形態における検出対象決定の例である。
【符号の説明】
【０２４９】
１０  信号縮小手段
２０  変換パラメータ算出手段
１０１  埋め込み前信号
１０２  埋め込み情報
１０４  埋め込み済み信号
１０５  通信路
１０６  加法的ノイズ
１０７  信号の改変
１０８  改変された埋め込み済み信号
１１０  検出情報
２００  電子透かし埋め込み装置
２０１  透かしパターン生成部
２０２  透かしパターン加算部
２０３  透かしパターン
３０１  透かしパターン
４００  電子透かし検出装置
４０１  一次変換パラメータ推定部
４０２  幾何変換補正部
４０３  平行移動量推定部
４０４  埋め込み情報検出部
４０５  入力信号
４０６  推定一次変換パラメータ
４０７  幾何変換補正済み信号
４０８  推定平行移動量
４０９  透かし検出情報
５０１  自己相関関数値配列生成部
５０２  固定フィルタ探索手段、固定フィルタ探索部
５０３  ９０度ペア探索手段、９０度ペア探索部
５０４  詳細フィルタ探索手段、詳細フィルタ探索部
５０５  変換パラメータ算出手段、変換パラメータ推定部
５０６  入力信号
５０７  推定一次変換パラメータ
５０８  自己相関関数値配列
５０９  ピーク点候補
５１０  基底ベクトル候補
５１１  推定基底ベクトル
１３０１  アスペクト比変更を含まない改変
１３０２  １３０１の前後にアスペクト比変更を加えた改変
１７０１  自己相関関数値配列上のサンプル
１７０２  候補点位置に応じて決まる理論的周波数分布から得られるピーク形状
１７０３  格子点位置に対応した理論値
１７０４  自己相関関数値配列
１７０５  基底ベクトル候補点から左方向に微小にずれた位置をピークとする理論的ピーク形状
１９０１  自己相関関数値配列生成部
１９０２  固定フィルタ探索部
１９０３  ９０度ペア探索部
１９０４  詳細フィルタ探索部
１９０５  変換パラメータ推定部
１９０６  入力信号
１９０７  推定一次変換パラメータ
１９０８  自己相関関数値配列
１９０９  ピーク点候補
１９１０  基底ベクトル候補
１９１１  推定基底ベクトル
１９１２  従属ピーク点除去部
１９１３  従属ピーク点を除去された推定基底ベクトル
２２００  電子透かし検出装置
２２０１  信号縮小部
２２０２  自己相関関数計算部
２２０３  自己相関関数値正規化部
２２０４  自己相関ピーク点評価部
２２０５  自己相関ピーク点評価値正規化部
２２０６  検出対象決定部
２２０７  幾何補正部
２２０８  埋め込み情報検出部
２２０９  入力信号
２２１０  透かし検出情報
【図１】
2006295473.tif 000011
【図２】
2006295473.tif 000012
【図３】
2006295473.tif 000013
【図４】
2006295473.tif 000014
【図５】
2006295473.tif 000015
【図６】
2006295473.tif 000016
【図７】
2006295473.tif 000017
【図８】
2006295473.tif 000018
【図９】
2006295473.tif 000019
【図１０】
2006295473.tif 000020
【図１１】
2006295473.tif 000021
【図１２】
2006295473.tif 000022
【図１３】
2006295473.tif 000023
【図１４】
2006295473.tif 000024
【図１５】
2006295473.tif 000025
【図１６】
2006295473.tif 000026
【図１７】
2006295473.tif 000027
【図１８】
2006295473.tif 000028
【図１９】
2006295473.tif 000029
【図２０】
2006295473.tif 000030
【図２１】
2006295473.tif 000031
【図２２】
2006295473.tif 000032
【図２３】
2006295473.tif 000033
【図２４】
2006295473.tif 000034
【図２５】
2006295473.tif 000035
【図２６】
2006295473.tif 000036
【図２７】
2006295473.tif 000037
【図２８】
2006295473.tif 000038
【図２９】
2006295473.tif 000039