(57)【特許請求の範囲】
【請求項１】
電子透かし情報のビット列を含む第一符号語を生成する符号語生成部と、
前記電子透かし情報に基づいて巡回シフト系列を生成するシフト系列生成部と、
生成された前記巡回シフト系列に基づいて前記第一符号語の所定領域を巡回シフトして第二符号語を生成するシフト部と、
生成された前記第二符号語をコンテンツに埋め込む埋め込み部と、
を備える電子透かし埋め込み装置。
【請求項２】
前記シフト系列生成部は、
複数の乱数の系列に対して、前記電子透かし情報のビット列が示す数字を開始位置に決定し、前記開始位置からの乱数の系列を前記巡回シフト系列とする請求項１記載の電子透かし埋め込み装置。
【請求項３】
前記シフト部は、
前記巡回シフト系列の乱数をシフト量にして前記第一符号語の所定領域を巡回シフトして第二符号語を生成する処理を、乱数の系列順に繰り返し、
前記埋め込み部は、
前記コンテンツの最後に到達するまで、前記乱数の系列順に生成された第二符号語を、前記コンテンツに順番に埋め込む請求項２記載の電子透かし埋め込み装置。
【請求項４】
前記第一符号語は、前記電子透かし情報に、前記第一符号語の開始位置を表す位置検出符号及び前記シフト部のシフト量の特定に用いるシフト量検出符号を付加した符号であり、前記第一符号語の所定領域は、前記電子透かし情報と前記シフト量検出符号の領域である請求項１乃至３いずれか一項に記載の電子透かし埋め込み装置。
【請求項５】
電子透かし情報のビット列を含む第一符号語を生成し、
前記電子透かし情報に基づいて巡回シフト系列を生成し、
生成された前記巡回シフト系列に基づいて前記第一符号語の所定領域を巡回シフトして第二符号語を生成し、
生成された前記第二符号語をコンテンツに埋め込む処理をコンピュータが実行する電子透かし埋め込み方法。
【請求項６】
透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語の所定領域が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出する符号語検出部と、
一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行うシフト系列検出部と、
検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成する候補生成部と、
前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する照合部と、
を備える電子透かし検出装置。
【請求項７】
前記巡回シフト系列が、複数の乱数の系列に対して、前記電子透かし情報のビット列が示す開始位置からの乱数の系列である場合、
前記候補生成部は、
前記シフト系列と、前記乱数の系列との類似度が所定値以上である位置の数字を表すビット列を前記候補とする請求項６記載の電子透かし検出装置。
【請求項８】
透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語の所定領域が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出し、
一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行い、
検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成し、
前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する処理をコンピュータが実行する電子透かし検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子化されたコンテンツに対して電子透かし情報を用いる電子透かし埋め込み装置、電子透かし埋め込み方法、電子透かし検出装置及び電子透かし検出方法に関する。
【背景技術】
【０００２】
電子透かしは、画像データや音声データに対し、人間が認識できないように付加情報を埋め込む技術である。コンテンツの著作権情報やユーザの購入情報などを電子透かしとして埋め込むと、コンテンツが不正流出した場合に著作権情報の有無や流出元を特定できる。
【０００３】
また、画像や動画コンテンツが透かし埋め込み対象の場合、電子透かしは電子広告（デジタルサイネージ）にも応用可能である。街頭スクリーンやテレビに映った広告動画からカメラ付き携帯電話等で電子透かしを検出することで、商品の詳しい情報等、付加情報を取得することができる。
【０００４】
電子透かしが埋め込まれたコンテンツは、データ圧縮や切り取り、フィルタ処理等を経て劣化する可能性があり、考えられ得る劣化要因に対して耐性を持つことが求められる。とりわけ、電子透かしを著作権保護の目的で用いる場合、電子透かしが埋め込まれたコンテンツは、悪意のあるユーザによる透かしを解析、無効化する攻撃に耐え得ることが望ましい。
【０００５】
そのような攻撃として「結託攻撃」と呼ばれるものがある。結託攻撃は、複数のユーザがそれぞれの透かし入りコンテンツを持ち寄り、データの異なる部分を比較することで電子透かしを解析、無効化する攻撃である。
【０００６】
典型的な結託攻撃に平均化攻撃があり、平均化攻撃は、複数の透かし入りコンテンツの平均値を取ることで、透かしが劣化した新たなコンテンツを生成する攻撃である。例えばユーザＡのコンテンツのある位置にビット"0"を表す透かしがあり、ユーザＢのコンテンツの同位置にビット"1"の透かしがあるとする。二人のユーザが結託して平均化攻撃を行うと、対象位置のユーザＡのビット"0"とユーザＢのビット"1"の透かしが平均化され、消去されてしまう。
【０００７】
このように結託者同士は、透かし情報の異なる部分を結託攻撃の対象とする。一般に結託者数が多いほど攻撃可能な範囲は広がる。このような結託攻撃に耐性を持つ従来技術として、例えば以下の二つがある。
【０００８】
一つ目は、結託耐性符号を用いた電子透かし埋め込みである。これは、ｃ人が結託した場合に結託者でないユーザを誤って検出する確率がεとなる符号（ｃ−ｓｅｃｕｒｅ  ｗｉｔｈ  ε  ｅｒｒｏｒ）が提案され、結託耐性符号と呼ばれている。
【０００９】
結託耐性符号の生成に必要な符号長は、ｃ（結託者数）の四乗のオーダーであることが理論的に示されている。また、符号長がｃの二乗オーダーで結託耐性符号を実現できる技術もある。このような条件の下で、結託耐性符号の符号長を短縮するアプローチが行われている。
【００１０】
二つ目は、鍵を用いてユーザ毎に透かしデータを異なる方法で拡散させる電子透かし埋め込みである。この技術では、鍵に基づき透かしデータをスクランブルすることで拡散を実現する。埋め込んだ透かしは、透かし埋め込みで使用した鍵で拡散したデータを復元することで検出する。結託攻撃された場合、透かし検出時に鍵に対応しないユーザの透かし情報をランダムノイズ化できるため、結託耐性のある透かし埋め込みを実現できる。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００７−１７８８５７号公報
【特許文献２】特開２００７−３２４７２０号公報
【非特許文献】
【００１２】
【非特許文献１】D. Boneh and J. Shaw, "Collusion secure fingerprinting for digital data," in Proc. Crypto'95, LNCS 963, pp.452-465.
【非特許文献２】Tarodos，G．"Optimal Probabilistic Fingerprinting Codes．" In：STOC'03，ACM（2003）pp.116-125
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、上述した従来技術は、各々に課題がある。一つ目の技術は、結託攻撃を受けた場合の電子透かし情報の検出精度を理論的に保証する符号化方式であるが、動画データや音声データに透かしとして埋め込むには符号長が非常に長い。そのため、この技術は実用的でないという課題がある。また、透かし検出対象のコンテンツが結託攻撃されていない場合、より短い符号長で透かしを検出できるにも関わらず、不必要に長い符号を付加しなければならない。
【００１４】
二つ目の技術は、ユーザ毎に異なる鍵で符号化しているため、検出時にユーザが未知の場合に全ての鍵で検出を試みなければならず、処理効率の観点で実用的ではないという課題がある。
【００１５】
そこで、開示の技術は、上記問題に鑑みてなされたものであり、結託攻撃に対する耐性を持ち、実用性を向上させることができる電子透かし埋め込み装置、電子透かし埋め込み方法、電子透かし検出装置及び電子透かし検出方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
開示の一態様における電子透かし埋め込み装置は、電子透かし情報のビット列を含む第一符号語を生成する符号語生成部と、前記電子透かし情報に基づいて巡回シフト系列を生成するシフト系列生成部と、生成された前記巡回シフト系列に基づいて前記第一符号語の所定領域を巡回シフトして第二符号語を生成するシフト部と、生成された前記第二符号語をコンテンツに埋め込む埋め込み部と、を備える。
【００１７】
また、開示の他の態様における電子透かし検出装置は、透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語の所定領域が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出する符号語検出部と、一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行うシフト系列検出部と、検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成する候補生成部と、前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する照合部と、を備える。
【発明の効果】
【００１８】
開示の技術によれば、結託攻撃に対する耐性を持ち、実用性を向上させることができる。
【図面の簡単な説明】
【００１９】
【図１】情報処理装置の構成の一例を示す図。
【図２】制御部における電子透かし埋め込み機能の一例を示すブロック図。
【図３】基準符号語の生成を説明するための図。
【図４】巡回シフト系列の生成を説明するための図。
【図５】巡回シフトを説明するための図。
【図６】コンテンツへの修正符号語の埋め込みを説明するための図。
【図７】実施例１における電子透かし埋め込み処理の一例を示すフローチャート。
【図８】制御部における電子透かし検出機能の一例を示すブロック図。
【図９】シフト系列検出部の構成の一例を示すブロック図。
【図１０】コンテンツからの符号検出を説明するための図。
【図１１】シフト系列の検出を説明するための図。
【図１２】三人の結託者で結託攻撃を受けたコンテンツにおけるシフト系列の検出を説明するための図。
【図１３】第二検出符号の生成を説明するための図。
【図１４】透かし情報候補の生成を説明するための図。
【図１５】実施例２における電子透かし検出処理の一例を示すフローチャート。
【図１６】シフト系列検出部の処理の一例を示すフローチャート。
【図１７】透かし情報照合部の処理の一例を示すフローチャート。
【発明を実施するための形態】
【００２０】
以下、各実施例について、添付図面を参照しながら説明する。
【００２１】
［実施例１］
＜構成＞
図１は、情報処理装置１の構成の一例を示す図である。図１に示す情報処理装置１は、電子透かし情報を埋め込む電子透かし埋め込み装置として機能する。図１に示す情報処理装置１は、制御部１０、主記憶部２０、補助記憶部３０、通信部４０、記録媒体Ｉ／Ｆ装置５０を有する。各部は、バスを介して相互にデータ送受信可能に接続されている。
【００２２】
制御部１０は、コンピュータの中で、各装置の制御やデータの演算、加工を行うＣＰＵ（Central Processing Unit）である。また、制御部１０は、主記憶部２０や補助記憶部３０に記憶されたプログラムを実行する演算装置であり、通信部４０や各記憶部からデータを受け取り、演算、加工した上で、出力部や各記憶部に出力する。
【００２３】
また、制御部１０は、例えば補助記憶部３０に記憶される電子透かし情報を埋め込むためのプログラムを実行することで、電子透かし埋め込み機能の役割を果たす。
【００２４】
主記憶部２０は、ＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）などであり、制御部２０が実行する基本ソフトウェアであるＯＳやアプリケーションソフトウェアなどのプログラムやデータを記憶又は一時保存する記憶装置である。
【００２５】
補助記憶部３０は、ＨＤＤ（Hard Disk Drive）などであり、アプリケーションソフトウェアなどに関連するデータを記憶する記憶装置である。補助記憶部３０には、通信部４０から取得された映像や音楽などの電子化されたコンテンツや電子透かし情報を記憶する。
【００２６】
また、補助記憶部３０は、記録媒体６０などから取得されたコンテンツや電子透かし情報を記憶しておいてもよい。
【００２７】
通信部４０は、有線又は無線で通信を行う。通信部４０は、例えば、サーバなどから映像や音楽などのコンテンツや電子透かし情報を取得し、例えば補助記憶部３０に記憶させる。
【００２８】
記録媒体Ｉ／Ｆ部５０は、ＵＳＢ（Universal Serial Bus）などのデータ伝送路を介して接続された記録媒体６０（例えば、フラッシュメモリなど）と情報処理装置１とのインターフェースである。
【００２９】
また、記録媒体６０に、所定のプログラムを格納し、この記録媒体６０に格納されたプログラムは記録媒体Ｉ／Ｆ（インターフェース）部５０を介して情報処理装置１にインストールされる。インストールされた所定のプログラムは、情報処理装置１により実行可能となる。
【００３０】
なお、記録媒体６０を例えばＳＤカードとした場合は、記録媒体Ｉ／Ｆ部５０は、ＳＤカードスロットである。
【００３１】
＜電子透かし情報の埋め込み機能＞
次に、電子透かし情報を埋め込む機能を有する制御部１０について詳しく説明する。図２は、制御部１０における電子透かし埋め込み機能の一例を示すブロック図である。図２に示す制御部１０は、符号語生成部１０１、シフト系列生成部１０２、シフト部１０３及び埋め込み部１０４を有する。
【００３２】
符号語生成部１０１は、電子透かし情報のビット列を含む基準符号語を生成する。基準符号語は第一符号語とも呼ぶ。符号語生成部１０１は、電子透かし情報を通信部４０又は補助記憶部３０などから取得する。基準符号語は、位置検出符号と、シフト量検出符号と、電子透かし情報を修正した修正透かし情報とを含む。
【００３３】
位置検出符号は、基準符号語の位置を特定するための符号である。シフト量検出符号は、後述するシフト量を特定するために用いる符号である。修正透かし情報は、電子透かし情報に対し、誤り検出符号及び／又は誤り訂正符号を付加した情報である。
【００３４】
シフト系列生成部１０２は、シフト部１０３で巡回シフトするシフト量の系列を、電子透かし情報に基づいて生成する。シフト系列生成部１０２の処理については、図４を用いて後述する。
【００３５】
シフト部１０３は、取得した基準符号語のうち、位置検出符号を除いた部分、例えば、シフト量検出符号及び修正透かし情報を、取得したシフト系列が示すシフト量で巡回シフトすることで、修正符号語を生成する。修正符号語は、第二符号語とも呼ばれる。
【００３６】
また、シフト部１０３は、一つのコンテンツに対して、一つの基準符号語から複数の修正符号語を生成する。その際、シフト部１０３は、各修正符号語に対するシフト量として、シフト系列生成部１０２から取得した巡回シフト系列のシフト量を順番に用いる。
【００３７】
埋め込み部１０４は、シフト部１０３で生成された修正符号語を、画像や音声等の埋め込み対象のコンテンツに電子透かしとして埋め込む。コンテンツは、補助記憶部３０や通信部４０から取得される。埋め込み部１０４は、電子透かし情報を埋め込むために、コンテンツに応じた様々な電子透かし情報の埋め込み方法の何れかを利用することができる。
【００３８】
例えば、コンテンツが音声データである場合、埋め込み部１０４は、人の非可聴域に修正符号語を埋め込む。その際、埋め込み部１０４は、修正符号語に含まれるビット毎に、そのビットの値に応じた信号を生成する。そして、埋め込み部１０４は、修正符号語の先頭のビットから順に、各ビットの値に応じた信号を時系列に沿って音声データの非可聴域に重畳する。
【００３９】
また、コンテンツが動画像データである場合、埋め込み部１０４は、動画像データに含まれる時系列順に並んだ複数の画像に対して、修正符号語の先頭のビットから順に、一つずつビットを埋め込む。例えば、埋め込み部１０４は、各画像のそれぞれの所定位置の画素の輝度値を、修正符号語の先頭のビットから順に、そのビットの値に応じた輝度値にする。なお、所定位置は、例えば、画像の４隅のいずれかの画素とすることができる。よって、実施例では、コンテンツに透かしを埋め込む方法については特に限定せず、種々の方法を適用することが可能である。
【００４０】
＜各部の詳細処理＞
次に、電子透かし埋め込み処理の各処理について詳しく説明する。
《基準符号語の生成》
図３は、基準符号語の生成を説明するための図である。図３に示す例では、符号語生成部１０１に入力された電子透かし情報には、埋め込み対象のコンテンツの著作権情報や、販売店情報、購入者情報などが含まれる。図３に示す例では、電子透かし情報は、ビット列ｂ１１に符号化されている。
【００４１】
符号語生成部１０１は、この符号化された電子透かし情報を、誤り訂正および誤り検出可能な修正透かし情報ｂ１２に変換する。すなわち、符号語生成部１０１は、取得した電子透かし情報に対する誤り訂正符号及び誤り検出符号を算出し、修正透かし情報ｂ１２を生成する。誤り検出符号と誤り訂正符号は、埋め込んだ電子透かし情報が圧縮や結託攻撃等を受けて発生する符号の誤りを検出、訂正するのに使用する。
【００４２】
誤り検出符号には、ＣＲＣ（Cyclic Redundancy Checking）符号など、また誤り訂正符号にはリードソロモン符号やＬＤＰＣ（Low Density Parity Check）符号などを使用可能とする。なお、基準符号語は、誤り検出符号及び／又は誤り訂正符号を含まなくてもよい。
【００４３】
さらに、符号語生成部１０１は、修正透かし情報ｂ１２の先頭に位置検出符号ｂ１３及びシフト量検出符号ｂ１４を付加することで基準符号語を生成する。位置検出符号ｂ１３は、電子透かし情報が埋め込まれたコンテンツにおいて、後述する修正符号語の位置を示すための符号である。シフト量検出符号ｂ１４は、修正符号語におけるシフト量を、電子透かし検出装置が検出するために用いられる符号である。
【００４４】
位置検出符号ｂ１３及びシフト量検出符号ｂ１４は、電子透かし検出装置が正確に位置検出符号及びシフト量検出符号を検出することができるように、互いに直交する所定量のビット列として設定されることが望ましい。
【００４５】
例えば、位置検出符号ｂ１３は、「1111111100000000」、シフト量検出符号ｂ１４は「0000111100001111」の１６ビットの符号として設定する。なお、位置検出符号ｂ１３及びシフト量検出符号ｂ１４は、１６ビット以外にも、互いに直交する８ビットや３２ビットなどでもよい。
【００４６】
上記の例の位置検出符号ｂ１３及びシフト量検出符号ｂ１４は、ビット「０」を「−１」とみなして１６次元ベクトルの内積を取ると０になるため、直交する例である。
【００４７】
基準符号語のうち、修正透かし情報ｂ１２とシフト量検出符号ｂ１４は、後述のシフト部１０３で巡回シフトの対象となる。
【００４８】
なお、符号語生成部１０１は、符号語を生成する前に、電子透かし情報の暗号化、電子透かし情報に含まれるビット列を所定のブロック単位で入れ替えるスクランブル処理の実行、又はスペクトル拡散などの前処理を行ってもよい。この場合、符号語生成部１０１は、前処理が行われた電子透かし情報を基準符号語に含める。
【００４９】
また、符号語生成部１０１は、電子透かし情報が所定のビット長よりも長いビット列で表される場合、そのビット列をその所定のビット長単位で分割し、分割されたビット列ごとに基準符号語を生成してもよい。符号語生成部１０１は、生成した基準符号語をシフト部１０３に出力する。
【００５０】
《巡回シフト系列の生成》
図４は、巡回シフト系列の生成を説明するための図である。図４に示す例では、電子透かし情報のビット列ｂ１１が表す数字ｗから得られるシフト系列は、wの関数
【００５１】
【数１】
0005974463.tif 000002
として表現できる。
【００５２】
巡回シフト系列Ｓ（ｗ）の各要素Ｓｉ（ｗ）が、巡回シフトのシフト量を表す。シフト部１０３は、このシフト量を用いて巡回シフトの対象領域を巡回シフトする。以後、シフト量Ｓｉ（ｗ）を簡便化のためＳｉと表記する。
【００５３】
巡回シフト系列Ｓ（ｗ）の生成方法の一例として、擬似乱数を用いる方法が考えられる。使用する擬似乱数は、線形合同法やメルセンヌ・ツイスタ、ＡＥＳ暗号を用いた乱数生成法等、様々な方式が適用可能である。電子透かし情報ｗの全ての場合の数をｎｗ、擬似乱数のｔ番目の値をＲ［ｔ］とする。
【００５４】
図４に示す乱数系列Ｒ［ｔ］（t=0,1,2,・・・,w,・・・）は、擬似乱数により生成された乱数の系列である。この乱数系列に対して、電子透かし情報ｗを開始位置とすると、シフト量Ｓｉは、透かし情報ｗを乱数の種として、次の式（２）で表される。
【００５５】
【数２】
0005974463.tif 000003
【００５６】
ここでは簡便化のため、電子透かし情報ｗは、０からｎｗ−１までの値を取り得るものとする。また、乱数系列Ｒ［ｔ］は、巡回シフトの対象となる符号長よりも小さな値を取るものとする。シフト系列生成部１０２は、生成した巡回シフト系列Ｓｉをシフト部１０３に出力する。
【００５７】
《巡回シフト》
図５は、巡回シフトを説明するための図である。図５に示す例では、巡回シフトは、基準符号語の先頭の位置検出符号ｂ１３を除く符号領域に適用する。巡回シフトのシフト量Ｓｉは、シフト系列生成部１０２から得られた巡回シフト系列より設定する。
【００５８】
シフト量Ｓｉは、巡回シフト系列のｉ番目の値である。図５に示すように、シフト部１０３は、巡回シフトにより巡回シフト対象領域の左端のビットａｂｃを、Ｓｉだけ右にシフトし、右端のビットＸＹＺのように右シフト後にシフト対象領域の外側にはみ出るものは、シフト対象領域の左側に移動して配置する。
【００５９】
なお、一つのコンテンツに対して生成される修正符号語の数は、そのコンテンツのデータ量が多いほど多くなるように設定されてもよい。例えば、生成される修正符号語の数は、コンテンツのデータ量を、一つの修正符号語を埋め込むために必要なデータ量で除した値とすることができる。ただし、その値が所定の上限値を超える場合、シフト部１０３は、生成される修正符号語の数をその上限値としてもよい。この上限値は、例えば１０とする。シフト部１０３は、生成した１又は複数の修正符号語を埋め込み部１０４に出力する。
【００６０】
《埋め込み処理》
図６は、コンテンツへの修正符号語の埋め込みを説明するための図である。図６に示す例では、シフト部１０３は、埋め込み対象のコンテンツのサイズに応じて、シフト量を用いて修正符号語を複数生成する。
【００６１】
基準符号語に対する巡回シフト量は、図６に示すように、シフト系列生成部１０２で生成された巡回シフト系列からＳ０，Ｓ１，Ｓ２，…の順に設定される。埋め込み部１０４は、生成された複数の修正符号語を、コンテンツに対して所定の埋め込み方法で埋め込んでいく。
【００６２】
これにより、結託攻撃への耐性があり、実用性が向上した修正符号語を、埋め込み対象コンテンツに埋め込むことができる。
【００６３】
＜動作＞
次に、電子透かし埋め込み装置の動作について説明する。図７は、実施例１における電子透かし埋め込み処理の一例を示すフローチャートである。図７に示すステップＳ１０１で、符号語生成部１０１は、電子透かし情報から基準符号語を生成する。基準符号語は、例えば、位置検出符号、シフト量検出符号、修正透かし情報を含む。
【００６４】
ステップＳ１０２で、シフト系列生成部１０２は、電子透かし情報から巡回シフト系列Ｓ０，Ｓ１，Ｓ２，…を生成する。シフト系列生成部１０２は、例えば、乱数の系列に対して、電子透かし情報のビット列が示す数字を開始位置とし、この開始位置からの乱数系列を巡回シフト系列とする。
【００６５】
ステップＳ１０３で、シフト部１０３は、透かし埋め込みの繰り返し回数を表すインデックスｉを０に設定する。
【００６６】
ステップＳ１０４で、シフト部１０３は、埋め込み対象のコンテンツに透かしが挿入されていない領域があるかどうかを判定する。未挿入の領域があれば（ステップＳ１０４−ＹＥＳ）ステップＳ１０５に進み、未挿入の領域がなければ（ステップＳ１０４−ＮＯ）処理を終了する。
【００６７】
なお、未挿入の領域は、いまだに修正符号語が埋め込まれておらず、かつ、修正符号語を埋め込むことが可能な領域である。例えば、コンテンツが音声データであれば、修正符号語が埋め込まれておらず、かつ、修正符号語のデータ量を重畳可能な非可聴域が、未挿入の領域である。また、コンテンツが動画像データであれば、例えば、修正符号語が埋め込まれておらず、かつ、修正符号語に含まれるビットの総数に対応する複数の画像が、未挿入の領域である。
【００６８】
ステップＳ１０５で、シフト部１０３は、基準符号語（厳密には、基準符号語から位置検出符号を除いた符号）をＳｉだけ巡回シフトして修正符号語を生成する。
【００６９】
ステップＳ１０６で、埋め込み部１０４は、シフト部１０３で生成された修正符号語を、透かし未挿入の領域に挿入する。
【００７０】
ステップＳ１０７で、シフト部１０３は、ステップＳ１０６の処理後、ｉに１を加算し、Ｓ１０４の判定処理に戻る。
【００７１】
以上、実施例１によれば、結託攻撃に対する耐性を持ち、実用性を向上させることができる電子透かし情報を含む符号語をコンテンツに埋め込むことができる。
【００７２】
［実施例２］
次に、実施例２における情報処理装置について説明する。実施例２における情報処理装置は、電子透かし検出装置として機能し、実施例１における電子透かし埋め込み装置で埋め込まれた電子透かし情報を検出する装置である。
【００７３】
＜構成＞
実施例２における情報処理装置は、実施例１における情報処理装置１と同様であるため、その説明を省略する。なお、実施例２における情報処理装置の構成を説明する際、図１に示す符号と同じ符号を用いて説明する。
【００７４】
＜電子透かし情報の検出機能＞
次に、電子透かし情報を検出する機能を有する制御部１０について詳しく説明する。図８は、制御部１０における電子透かし検出機能の一例を示すブロック図である。図８に示す制御部１０は、符号語検出部２０１、シフト系列検出部２０２、候補生成部２０３、透かし情報検出部２０４及び透かし情報照合部２０５を有する。
【００７５】
符号語検出部２０１は、コンテンツに埋め込まれた複数の修正符号語を検出する。例えば、符号語検出部２０１は、コンテンツに埋め込まれた複数の修正符号語の各ビットを、実施例１における電子透かし埋め込み方法に応じた検出方法を用いて検出する。
【００７６】
例えば、コンテンツが音声データであり、その音声データの非可聴域に修正符号語に含まれる各ビットの値に応じた信号が付加されているとする。この場合、符号語検出部２０１は、その信号に対応するテンプレートと非可聴域の信号とのテンプレートマッチングにより非可聴域内でテンプレートと一致する信号を検出する。符号語検出部２０１は、一致したテンプレートに対応するビット値を修正符号語に含まれるビットとして検出する。
【００７７】
また、コンテンツが動画像データであり、各画像の所定の画素が修正符号語に含まれるビット値に応じた値を持っている場合、符号語検出部２０１は、その所定の画素の値に応じたビット値を検出する。符号語検出部２０１は、検出した符号語を第一検出符号としてシフト系列検出部２０２に出力する。
【００７８】
シフト系列検出部２０２は、図９を用いて説明する。図９は、シフト系列検出部２０２の構成の一例を示すブロック図である。図９に示すシフト系列検出部２０２は、シフト量算出部３０１、逆シフト部３０２、符号更新部３０３及び第二検出符号生成部３０４を有する。
【００７９】
シフト量算出部３０１は、符号語検出部２０１から取得した第一検出符号に基づき、電子透かし埋め込み時に基準符号語を巡回シフトしたシフト量の系列（シフト系列とも呼ぶ）を算出する。シフト量算出部３０１は、例えば、第一検出符号内の任意の一の符号を基準とし、他の符号との間で相互相関値を用いて、シフト量を算出する。
【００８０】
なお、シフト量算出部３０１は、二回目以降のシフト量算出において基準とする一の符号を、符号更新部３０３により更新された符号とする。
【００８１】
逆シフト部３０２は、シフト量算出部３０１で算出されたシフト量を用いて、相互相関値を算出した他の符号を逆シフトする。逆シフトした他の符号を、符号更新部３０３に出力する。
【００８２】
符号更新部３０３は、逆シフトされた他の符号と、基準となる一の符号とを加算し、一の符号を更新して新たな符号を生成する。シフト量算出部３０１、逆シフト部３０２、符号更新部３０３は、この処理を、一の符号以外の他の符号全てに対して行う。
【００８３】
他の符号がなくなった場合、シフト量算出部３０１は、求めた各シフト量を並べてシフト系列を生成し、生成したシフト系列を第二検出符号生成部３０４に出力する。また、符号更新部３０３は、最終的に更新された符号を第二検出符号生成部３０４に出力する。
【００８４】
第二検出符号生成部３０４は、符号更新部３０３から取得した符号に基づき、透かし検出用の符号である第二検出符号を生成する。第二検出符号生成部３０４は、符号からシフト量検出符号の位置を特定し、このシフト量検出符号が先頭にくるように逆シフトする。
【００８５】
第二検出符号生成部３０４は、逆シフトした符号からシフト量検出符号を除いた符号を第二検出符号として生成する。第二検出符号は、修正透かし情報に対応する符号である。第二検出符号生成部３０４は、生成した第二検出符号を透かし情報検出部２０４及び透かし情報照合部２０５に出力する。
【００８６】
また、第二検出符号生成部３０４は、シフト量算出部３０１から取得したシフト系列を、逆シフトした量分だけ逆シフトし、シフト系列を更新する。第二検出符号生成部３０４は、更新したシフト系列を候補生成部２０３に出力する。
【００８７】
図８に戻り、候補生成部２０３は、シフト系列検出部２０２で得られたシフト系列から、検出対象の電子透かし情報の候補を１又は複数生成する。候補生成部２０３は、生成した１又は複数の候補を透かし情報照合部２０５に出力する。
【００８８】
透かし情報検出部２０４では、シフト系列検出部２０２で生成された第二検出符号から電子透かし情報として埋め込んだ透かし情報を検出し、出力する。透かし情報検出部２０４で透かしを検出できなかった場合は、透かし情報照合部２０５で最適な電子透かし情報を求めさせる。
【００８９】
透かし情報照合部２０５は、候補生成部２０３で生成された電子透かし情報の各候補と、第二検出符号との類似度を求め、電子透かし情報の候補から最適なものを電子透かし情報として出力する。
【００９０】
＜各部の詳細処理＞
次に、電子透かし検出処理の各処理について詳しく説明する。
《第一検出符号の検出処理》
電子透かし情報が埋め込まれたコンテンツから、透かしに対応する第一検出符号が検出される。第一検出符号を検出する処理は、実施例１の埋め込み部１０４での埋め込み方法に対応した検出方法である。この検出方法は、埋め込み部１０４の埋め込み方法に対応するため、特定の処理に限定されるものではない。
【００９１】
第一検出符号は、透かし埋め込み時に生成した修正符号語が異なるシフト量で繰り返し並べられた符号に対応する。透かしが埋め込まれているコンテンツは、データ圧縮やフィルタ処理、ビデオ撮影、結託攻撃などを経て劣化している可能性がある。よって、劣化したコンテンツから検出される第一検出符号は、埋め込み時に生成された符号とは必ずしも一致せず、誤りを含む場合もある。
【００９２】
《巡回シフト系列と第二検出符号の検出処理》
シフト系列検出部２０２は、第一検出符号から、透かし埋め込み時に繰り返し生成された修正符号語の各々のシフト量を求め、第一検出符号から、透かし検出用の第二検出符号を生成する。求められた各々のシフト量を並べたシフト系列は、巡回シフト系列に相当する。
【００９３】
図１０は、コンテンツからの符号検出を説明するための図である。図１０に示す例では、符号語検出部２０１が、コンテンツから第一検出符号を検出する。次に、シフト系列検出部２０２は、第一検出符号から、巡回シフト系列と第二検出符号を検出するための符号を検出する。この符号をＣ［ｉ］と表記する。なお、第二検出符号を検出するための符号は、後述する符号Ｃ'［ｉ］、Ｃ＊［ｉ］も含む。
【００９４】
符号Ｃ［ｉ］は、シフト量算出部３０１により、位置検出符号を検出することで求められる。ここで、位置検出符号は、各々の修正符号語の先頭位置を表す。よって、シフト量算出部３０１は、各位置検出符号に続く符号が修正符号語の巡回シフトされた箇所であることがわかる。
【００９５】
以下、各Ｃ［ｉ］を用いて巡回シフト系列と第二検出符号とを生成する処理を説明する。各Ｃ［ｉ］は、基準符号語を異なるシフト量で巡回シフトしたものである。よって、シフト量算出部３０１は、Ｃ［ｉ］のうちの二つの符号の相互相関値を求めると、両者の巡回シフト量の差に相当する部分の相互相関値が最大となる。
【００９６】
したがって、シフト量算出部３０１は、Ｃ［０］とそれ以外の符号Ｃ［ｉ］との相互相関値が最大となる巡回シフト量を求めることで、Ｃ［０］を基準とした相対的なシフト系列Ｓ［０］，Ｓ［１］，Ｓ［２］を求めることができる。
【００９７】
ここで、Ｓ［０］は、符号Ｃ［０］とＣ［０］の相互相関値、つまりＣ［０］の自己相関値が最大の巡回シフト値を表しており、必ず０となる。次に、相互相関値の算出方法を説明する。Ｎを修正符号語の数、ＭをＣ［ｉ］の符号長（全てのｉで同じ）、ｃ［ｉ］［ｋ］をＣ［ｉ］のｋ番目（０≦ｋ≦（Ｍ−１））のビット情報とし、ビット０をｃ［ｉ］［ｋ］＝−１、ビット１をｃ［ｉ］［ｋ］＝１に対応させる。
【００９８】
また、Ｃ'［ｉ］は、逆シフト部３０２によりＣ［ｉ］をＳ［ｉ］で逆巡回シフトした符号系列とし、ｃ'［ｉ］［ｋ］は、Ｃ'［ｉ］のｋ番目のビット情報である。また、Ｃ＊［ｉ］は、符号更新部３０３により、相互相関値が最大の位置でＣ［０］からＣ［ｉ］までを加算した符号系列であり、ｃ＊［ｉ］［ｋ］は、Ｃ＊［ｉ］のｋ番目のビット情報とする。
【００９９】
この時、Ｃ［ｉ］をｊだけ巡回シフトした場合のＣ＊［ｉ−１］とＣ［ｉ］の相互相関値をｒ［ｉ］［ｊ］として、次式の繰り返し計算を行う。
【０１００】
＜１＞初期化
【０１０１】
【数３】
0005974463.tif 000004
【０１０２】
【数４】
0005974463.tif 000005
＜２＞式（５）〜（８）はｉ＝１〜Ｎ−１の範囲で繰り返す
【０１０３】
【数５】
0005974463.tif 000006
【０１０４】
【数６】
0005974463.tif 000007
【０１０５】
【数７】
0005974463.tif 000008
【０１０６】
【数８】
0005974463.tif 000009
【０１０７】
ここで、式（５），（７）中の「％」は剰余演算子を表し、Ａ％Ｂは「ＡをＢで割った余り」を意味する。また、式（６）のａｒｇｍａｘはｊを０からＭ−１まで変化させた場合に、ｒ［ｉ］［ｊ］が最大となるインデックスをＳ［ｉ］に返す関数である。
【０１０８】
さらに、式（３）と式（８）の計算はＣ［ｉ］，Ｃ'［ｉ］，Ｃ＊［ｉ］の各要素で行われるものとする。これらの繰り返し計算により、Ｃ［０］を基準とした相対的な巡回シフト系列Ｓ［ｉ］、および各Ｃ［ｉ］を相互相関値が最大の位置に合わせて累積した符号系列Ｃ＊［Ｎ−１］を得る。
【０１０９】
図１１は、シフト系列の検出を説明するための図である。図１１に示す例で、Ｃ［ｉ］、Ｃ'［ｉ］及びＣ＊［ｉ］の右隣にある横長の長方形は、各符号のビット列を表す。ビット列は、符号系列とも呼ばれる。
【０１１０】
図１１に示す例では、まず、シフト量算出部３０１は、相互相関値として、式（６）を用いてＣ＊［０］とＣ［１］の巡回シフト量の差に相当するＳ［１］を求める。図１１に示すように、シフト量と相互相関値とのグラフを見ると、シフト量Ｓ［１］のところに相互相関値のピークが現れる。
【０１１１】
逆シフト部３０２は、式（７）を用いてＣ［１］をＳ［１］で逆巡回シフトし、Ｃ'［１］を生成する。次に、符号更新部３０３は、式（８）を用いてＣ＊［１］＝Ｃ＊［０］＋Ｃ'［１］によりＣ＊［１］を求める。
【０１１２】
図１１に示すように、シフト系列検出部２０２は、式（５）〜（８）の処理を繰り返すことで、相互相関値のピークの位置に合わせてＣ［ｉ］を累積した符号系列Ｃ＊［Ｎ−１］を生成することができる。このＣ＊［Ｎ−１］は、第二検出符号を検出するための符号である。なお、Ｃ＊［Ｎ−１］の各要素ｃ＊［Ｎ−１］［ｋ］は、巡回シフトを行う前の基準符号語の同位置のビット情報が加算されたものとなっている。
【０１１３】
図１２は、三人の結託者で結託攻撃を受けたコンテンツにおけるシフト系列の検出を説明するための図である。図１２に示すように、まず、シフト量算出部３０１は、相互相関値として、式（６）を用いてＣ＊［０］とＣ［１］の巡回シフト量の差に相当するＳ［１］を求める。
【０１１４】
このとき、図１２に示すように、Ｃ［１］において、３人の結託者の巡回シフトの量はそれぞれ異なるため、Ｃ＊［０］とＣ［１］で相互相関値を計算すると、各結託者に対応する３つのピークが現れる。
【０１１５】
図１２に示す例では、結託者３に対応する巡回シフト量の相互相関値が最大となり、結託者３の巡回シフト位置に合わせてＣ＊［１］が生成される。この時、Ｃ＊［１］は、Ｃ［１］の逆巡回シフトにより結託者３に対応する符号位置で揃えられてＣ＊［０］と加算された符号系列となっている。よって、結託者３の符号系列が強調される。
【０１１６】
一方で、結託者１，２に対応する符号系列は全くランダムな位置関係で加算されているため、ランダムノイズ化されて相互相関値の大きさが弱まる。したがって、Ｃ＊［１］とＣ［２］の相互相関値をさらに計算すると、結託者３の巡回シフト量に対応する相互相関値のピークがより顕著に現れる。
【０１１７】
図１２に示す例で、シフト系列検出部２０２により、式（５）〜（８）の処理を繰り返されることで、加算により得られる符号系列Ｃ＊［Ｎ−１］は、結託者３の符号系列がより強調され、結託者１，２の符号系列がよりランダムノイズ化され弱まる。
【０１１８】
一つの符号系列のみでは結託攻撃により各々の透かし情報は破壊されているため、透かし情報を検出することは極めて困難である。しかしながら、上記の方法で相互相関値を用いて複数の符号系列を加算すると、結託者のうちの特定の一人の透かし情報が強調される。よって、破壊された透かし情報を復元し、結託攻撃を受けた符号からも透かしを検出できる可能性が高まる。
【０１１９】
これにより、シフト系列検出部２０２は、式（６）によりシフト系列Ｓ［ｉ］を求めることができ、式（８）により第二検出符号を検出するための符号Ｃ＊［Ｎ−１］を求めることができる。
【０１２０】
次に、第二検出符号を生成する処理について説明する。図１３は、第二検出符号の生成を説明するための図である。第二検出符号生成部３０４は、まず、符号系列Ｃ＊［Ｎ−１］から基準符号語のシフト量を表すシフト量検出符号を検出し、シフト量検出符号が先頭に来るようにＣ＊［Ｎ−１］を左に逆巡回シフトする。図１３に示す例では、Ｃ＊［Ｎ−１］におけるシフト量検出符号の先頭位置からのずれをＳ＊とする。
【０１２１】
第二検出符号生成部３０４は、Ｃ＊［Ｎ−１］を逆巡回シフトして得られる符号系列から、シフト量検出符号を除いたものを第二検出符号とする。以後、図１３にも示すように、第二検出符号を示す記号をＣ＾とする。
【０１２２】
第二検出符号Ｃ＾の生成手順を数式で示す。Ｌをシフト量検出符号の符号長、ｃ＾［ｉ］を第二検出符号のｉ番目の要素とすると、ｃ＾［ｉ］を次式（９）〜（１０）により求めることができる。
【０１２３】
【数９】
0005974463.tif 000010
【０１２４】
【数１０】
0005974463.tif 000011
【０１２５】
また、第二検出符号を生成する際の逆巡回シフトに合わせて、各Ｓ［ｉ］も次式によりＳ＊だけ左に逆巡回シフトして値を更新する。
【０１２６】
【数１１】
0005974463.tif 000012
以上の手順により、第二検出符号生成部３０４は、第二検出符号とシフト系列Ｓ［ｉ］とを求めることができる。
【０１２７】
《透かし情報候補の生成》
次に、透かし情報候補の生成について説明する。図１４は、透かし情報候補の生成を説明するための図である。候補生成部２０３は、シフト系列検出部２０２で得られたシフト系列Ｓ［ｉ］に基づいて、検出対象の電子透かし情報の候補を生成する。
【０１２８】
図１４に示す例では、まず、候補生成部２０３は、実施例１のシフト系列生成部１０２と同様の乱数系列を用意する。次に、候補生成部２０３は、乱数系列の中でシフト系列と一致する箇所を探索する。なお、候補生成部２０３は、シフト系列と、所定箇所の乱数系列との類似度が所定値以上であれば、これらの系列は一致すると判断してもよい。
【０１２９】
シフト系列と一致する部分が見つかった場合、その位置に対応する透かし情報を透かし候補として生成する。図１４に示す例では、透かし候補をｗ［０］〜ｗ［ＮＷ−１］と表記する。なお、図１４に示す例では、透かし候補がＮＷ個生成された場合を示す。
【０１３０】
候補生成部２０３は、透かし候補ｗ［ｉ］を、後述の透かし情報照合部２０５で第二検出符号Ｃ＾と照合可能にするため、実施例１の符号語生成部１０１と同様の手順で修正透かし符号Ｗ［ｉ］に変換する。候補生成部２０３は、修正透かし候補Ｗ［ｉ］を透かし情報照合部２０５に出力する。
【０１３１】
《透かし情報の検出》
透かし情報検出部２０４は、シフト系列検出部２０２で検出された第二検出符号に基づき、電子透かし情報を検出する。第二検出符号は、透かし埋め込み処理の符号語生成部１０１で生成した修正透かし情報ｂ１２に対応し、元の電子透かし情報を誤り訂正および誤り検出可能な形式に変換したものである。
【０１３２】
そこで、透かし情報検出部２０４は、第二検出符号に誤り訂正と誤り検出を適用して逆変換し、誤り検出処理において誤りがないと判定されたら逆変換した符号系列を透かし情報として検出し、透かし検出処理を終了する。一方、誤りが検出された場合は、透かし情報検出部２０４は、誤りが検出された旨を透かし情報照合部２０５に通知する。
【０１３３】
《透かし情報の照合》
透かし情報照合部２０５は、候補生成部２０３で生成された電子透かし情報の各候補Ｗ［ｉ］と第二検出符号Ｃ＾との類似度を求め、電子透かし情報の候補から最適なものを透かし情報として出力する。
【０１３４】
透かし情報照合部２０５は、ｗ［ｉ］［ｊ］をＷ［ｉ］のｊ番目の要素のビット情報とすると、Ｗ［ｉ］とＣ＾の類似度ｓｉｍ［ｉ］は、例えば、次式（１２）の相関値計算により求められる。
【０１３５】
【数１２】
0005974463.tif 000013
【０１３６】
透かし情報照合部２０５は、式（１２）を用いて類似度ｓｉｍ［ｉ］を全ての電子透かし情報候補で求める。透かし情報照合部２０５は、類似度が最大となる電子透かし情報候補を選択し、最大の類似度が閾値より大きい等の一定の条件を満たす場合に、電子透かし情報を検出する。なお、第二検出符号Ｃ＾は、類似度計算のため「０」の値を「−１」にしていたため、検出した電子透かし情報では、「−１」を「０」に戻しておく。
【０１３７】
これにより、第二検出符号に誤りがあり、訂正できない場合にも、シフト系列から電子透かし情報の候補を生成することで、電子透かし情報の検出精度を高めることができる。よって、結託攻撃に耐性をもち、実用性が向上した電子透かし技術を提供することができる。
【０１３８】
＜動作＞
次に、実施例２における情報処理装置の動作について説明する。図１５は、実施例２における電子透かし検出処理の一例を示すフローチャートである。図１５に示すステップＳ２０１で、符号語検出部２０１は、透かしが埋め込まれたコンテンツから透かしに対応する第一検出符号を検出する。
【０１３９】
ステップＳ２０２で、シフト系列検出部２０２は、検出された第一検出符号から透かし検出用の第二検出符号と各修正符号語に対するシフト量を示すシフト系列を生成する。ステップＳ２０２の詳細な処理は、図１６を用いて後述する。
【０１４０】
ステップＳ２０３で、候補生成部２０３は、シフト系列検出部２０２で生成されたシフト系列を用いて電子透かし情報の候補を生成する。
【０１４１】
ステップＳ２０４で、透かし情報検出部２０４は、シフト系列検出部２０２で生成された第二検出符号に対し、誤り訂正と誤り検出を適用して逆変換し、電子透かし情報の検出を試みる。
【０１４２】
ステップＳ２０５で、透かし情報検出部２０４は、電子透かし情報を検出できたか否かを判定する。電子透かし情報が検出できれば（ステップＳ２０５−ＹＥＳ）ステップＳ２０８に進み、電子透かし情報が検出できなければ（ステップＳ２０５−ＮＯ）ステップＳ２０６に進む。
【０１４３】
ステップＳ２０６で、透かし情報照合部２０５は、第二検出符号と電子透かし情報の各候補との類似度を求め、電子透かし情報の候補から最適なものを電子透かし情報として検出する。
【０１４４】
ステップＳ２０７で、透かし情報照合部２０５は、電子透かし情報を検出できたか否かの判定を行う。電子透かし情報が検出できれば（ステップＳ２０７−ＹＥＳ）ステップＳ２０８に進み、電子透かし情報が検出できなければ（ステップＳ２０７−ＮＯ）ステップＳ２０９に進む。
【０１４５】
ステップＳ２０８で、透かし情報検出部２０４、又は透かし情報照合部２０５は、検出した電子透かし情報を出力する。
【０１４６】
ステップＳ２０９で、透かし情報照合部２０５は、電子透かし情報の検出に失敗したとみなす。なお、Ｓ２０６〜Ｓ２０９の詳細な処理は、図１７を用いて後述する。
【０１４７】
これにより、実施例１の電子透かし埋め込み処理で埋め込まれた電子透かし情報を、適切に検出することができる。
【０１４８】
図１６は、シフト系列検出部２０２の処理の一例を示すフローチャートである。なお、図１６に示すフローチャート内で説明なしで使われている変数は、上記で既出の変数と同じものとする。
【０１４９】
ステップＳ３０１で、シフト量算出部３０１は、第一検出符号から位置検出符号を検出して各修正符号語の先頭位置を特定し、Ｃ［ｉ］を生成する。
【０１５０】
ステップＳ３０２で、シフト量算出部３０１は、Ｃ［０］の相互相関値が最大の巡回シフト値Ｓ［０］は必ず０なので、予めＳ［０］＝０に設定し、Ｃ＊［０］をＣ［０］とする。
【０１５１】
ステップＳ３０３で、シフト量算出部３０１は、Ｃ［ｉ］に対応するループ変数ｉを１に設定する。
【０１５２】
ステップＳ３０４で、シフト量算出部３０１は、ｉがＮより小さいか否かの判定を行う。ｉがＮより小さければ（ステップＳ３０４−ＹＥＳ）Ｓ３０５に進み、ｉがＮ以上であれば（ステップＳ３０４−ＮＯ）Ｓ３１６に進む。
【０１５３】
ステップＳ３０５で、シフト量算出部３０１は、シフト量に対応するループ変数ｊを０とする。
【０１５４】
ステップＳ３０６で、シフト量算出部３０１は、相互相関値の現時点の最大値を表す変数ｍａｘ＿ｔｍｐを、相互相関値が取り得る値よりも小さい値ＳＭＡＬＬに予め設定する。
【０１５５】
ステップＳ３０７で、シフト量算出部３０１は、ｊがＣ［ｉ］の符号長Ｍより小さいか否か判定を行う。ｊがＭよりも小さければ（ステップＳ３０７−ＹＥＳ）Ｓ３０８に進み、ｊがＭ以上であれば（ステップＳ３０７−ＮＯ）Ｓ３１３に進む。
【０１５６】
ステップＳ３０８で、シフト量算出部３０１は、Ｃ［ｉ］をｊだけ巡回シフトした場合のＣ＊［ｉ−１］とＣ［ｉ］の相互相関値ｒ［ｉ］［ｊ］を式（５）により算出する。
【０１５７】
ステップＳ３０９で、シフト量算出部３０１は、算出したｒ［ｉ］［ｊ］がｍａｘ＿ｔｍｐより大きいか否かを判定する。ｒ［ｉ］［ｊ］がｍａｘ＿ｔｍｐより大きければ（ステップＳ３０９−ＹＥＳ）Ｓ３１０に進み、ｒ［ｉ］［ｊ］がｍａｘ＿ｔｍｐ以下であれば（ステップＳ３０９−ＮＯ）Ｓ３１２に進む。
【０１５８】
ステップＳ３１０で、シフト量算出部３０１は、Ｓ［ｉ］をｊとする。ステップＳ３１１で、シフト量算出部３０１は、ｍａｘ＿ｔｍｐにｒ［ｉ］［ｊ］を代入する。ステップＳ３１２で、シフト量算出部３０１は、ｊに１を足して、Ｓ３０７の処理に戻る。
【０１５９】
ステップＳ３１３で、逆シフト部３０２は、式（７）によりＣ［ｉ］をＳ［ｉ］だけ逆巡回シフトした符号系列をＣ'［ｉ］に代入する。
【０１６０】
ステップＳ３１４で、符号更新部３０３は、Ｃ［ｉ］を相互相関値が最大となる位置に合わせて累積した符号系列Ｃ＊［ｉ］を式（８）により更新する。ステップＳ３１５で、符号更新部３０３は、ｉに１を足して、Ｓ３０４の処理に戻る。
【０１６１】
ステップＳ３１６で、第二検出符号生成部３０４は、Ｃ＊［Ｎ−１］からシフト量検出符号を検出する。
【０１６２】
ステップＳ３１７で、第二検出符号生成部３０４は、Ｃ＊［Ｎ−１］をシフト量Ｓ＊だけ逆巡回シフトして、シフト量検出符号の後ろに位置する第二検出符号を生成する。
【０１６３】
ステップＳ３１８で、第二検出符号生成部３０４は、各Ｓ［ｉ］をＳ＊だけ逆巡回シフトして、シフト量検出符号を基準としたシフト系列Ｓ［ｉ］を生成する。
【０１６４】
これにより、第二検出符号と、シフト系列とを生成し、以降の電子透かし検出処理に用いることができる。
【０１６５】
図１７は、透かし情報照合部２０５の処理の一例を示すフローチャートである。図１７に示すステップＳ４０１で、透かし情報照合部２０５は、類似度計算のインデックスｉを０に設定する。
【０１６６】
ステップＳ４０２で、透かし情報照合部２０５は、類似度の最大値ｍａｘ＿ｔｍｐを０に設定する。
【０１６７】
ステップＳ４０３で、透かし情報照合部２０５は、電子透かし情報候補Ｗ［ｉ］の候補数をＮＷとし、ｉがＮＷより小さいか否かを判定する。ｉがＮＷより小さければ（ステップＳ４０３−ＹＥＳ）ステップＳ４０４に進み、ｉがＮＷ以上であれば（ステップＳ４０３−ＮＯ）ステップＳ４０９に進む。
【０１６８】
ステップＳ４０４で、透かし情報照合部２０５は、Ｗ［ｉ］とＣ＾の類似度ｓｉｍ［ｉ］を式（１２）により計算する。
【０１６９】
ステップＳ４０５で、透かし情報照合部２０５は、ｓｉｍ［ｉ］がｍａｘ＿ｔｍｐよりも大きいか否かを判定する。ｓｉｍ［ｉ］がｍａｘ＿ｔｍｐよりも大きれば（Ｓ４０５−ＹＥＳ）ステップＳ４０６に進み、ｓｉｍ［ｉ］がｍａｘ＿ｔｍｐ以下であれば（Ｓ４０５−ＮＯ）ステップＳ４０８に進む
ステップＳ４０６で、透かし情報照合部２０５は、ｓｉｍ［ｉ］が最大となるインデックスとｉ＿ｍａｘとして、ｉ＿ｍａｘにｉを代入する。
【０１７０】
ステップＳ４０７で、透かし情報照合部２０５は、ｍａｘ＿ｔｍｐにｓｉｍ［ｉ］を代入する。
【０１７１】
ステップＳ４０８で、透かし情報照合部２０５は、ｉの値に１を足して、ステップＳ４０３に戻る。
【０１７２】
ステップＳ４０９で、透かし情報照合部２０５は、電子透かし情報を検出するかどうかを判定する閾値をｓｉｍ＿ｔｈｒｅとして、最大の類似度ｓｉｍ［ｉ＿ｍａｘ］がｓｉｍ＿ｔｈｒｅ以上か否かを判定する。この処理は、図１５に示すステップＳ２０７に対応する。
【０１７３】
ｓｉｍ［ｉ＿ｍａｘ］がｓｉｍ＿ｔｈｒｅ以上であれば（ステップＳ４０９−ＹＥＳ）ステップＳ４１０に進み、ｓｉｍ［ｉ＿ｍａｘ］がｓｉｍ＿ｔｈｒｅ未満であれば（ステップＳ４０９−ＮＯ）ステップＳ４１１に進む。
【０１７４】
ステップＳ４１０で、透かし情報照合部２０５は、Ｗ［ｉ＿ｍａｘ］を電子透かし情報として出力する。この処理は、図１５に示すステップＳ２０８に対応する。
【０１７５】
ステップＳ４１１で、透かし情報照合部２０５は、透かし検出失敗とみなす。この処理は、図１５に示すステップＳ２０９に対応する。
【０１７６】
なお、透かし情報を検出する処理で、閾値ｓｉｍ＿ｔｈｒｅを定めるのは、類似度計算による透かし情報の誤検出を防ぐためである。例えば、シフト系列検出部２０２でシフト系列Ｓ［ｉ］を正しく求められなかった場合、第二検出符号Ｃ＾も全く関係ない系列を生成してしまい、透かし情報照合部２０５から正しい電子透かし情報を求めるのは不可能である。
【０１７７】
このような場合、どの電子透かし情報候補の類似度も値が小さくなるが、類似度が最大の透かし情報候補は求められてしまう。よって、類似度の最大値のみで電子透かし情報を選択すると誤検出してしまう。そこで、閾値ｓｉｍ＿ｔｈｒｅを設定し、誤検出を防ぐ。誤検出を防ぐためのｓｉｍ＿ｔｈｒｅの値は、例えば０．７５から０．８０の間であることが望ましい。
【０１７８】
以上、実施例２によれば、実施例１における電子透かし埋め込み処理で埋め込まれた電子透かし情報を検出することができる。
【０１７９】
［変形例］
なお、前述した各実施例で説明した電子透かし埋め込み処理及び電子透かし検出処理を実現するためのプログラムを記録媒体に記録することで、各実施例での電子透かし埋め込み処理及び電子透かし検出処理をコンピュータに実施させることができる。例えば、このプログラムを記録媒体に記録し、このプログラムが記録された記録媒体をコンピュータや携帯装置に読み取らせて、前述した電子透かし埋め込み処理及び電子透かし検出処理を実現させることも可能である。
【０１８０】
なお、記録媒体は、ＣＤ−ＲＯＭ、フレキシブルディスク、光磁気ディスク等の様に情報を光学的，電気的或いは磁気的に記録する記録媒体、ＲＯＭ、フラッシュメモリ等の様に情報を電気的に記録する半導体メモリ等、様々なタイプの記録媒体を用いることができる。
【０１８１】
情報処理装置で実行されるプログラムは、各実施例で説明した各部を含むモジュール構成となっている。実際のハードウェアとしては、制御部１０が補助記憶部３０からプログラムを読み出して実行することにより上記各部のうち１又は複数の各部が主記憶部２０上にロードされ、１又は複数の各部が主記憶部２０上に生成されるようになっている。
【０１８２】
以上、実施例について詳述したが、特定の実施例に限定されるものではなく、特許請求の範囲に記載された範囲内において、種々の変形及び変更が可能である。また、前述した各実施例の構成要素を全部又は複数を組み合わせることも可能である。
【０１８３】
なお、以上の各実施例に関し、さらに以下の付記を開示する。
（付記１）
電子透かし情報のビット列を含む第一符号語を生成する符号語生成部と、
前記電子透かし情報に基づいて巡回シフト系列を生成するシフト系列生成部と、
生成された前記巡回シフト系列に基づいて前記第一符号語を巡回シフトして第二符号語を生成するシフト部と、
生成された前記第二符号語をコンテンツに埋め込む埋め込み部と、
を備える電子透かし埋め込み装置。
（付記２）
前記シフト系列生成部は、
複数の乱数の系列に対して、前記電子透かし情報のビット列が示す開始位置を決定し、前記開始位置からの乱数の系列を前記巡回シフト系列とする付記１記載の電子透かし埋め込み装置。
（付記３）
前記巡回シフト部は、
前記巡回シフト系列の乱数をシフト量にして前記第一符号語を巡回シフトして第二符号語を生成する処理を、乱数の系列順に繰り返し、
前記埋め込み部は、
前記コンテンツの最後に到達するまで、前記乱数の系列順に生成された第二符号語を、前記コンテンツに順番に埋め込む付記２記載の電子透かし埋め込み装置。
（付記４）
前記第一符号語は、前記電子透かし情報に、前記第一符号語の開始位置を表す位置検出符号及び前記巡回シフト部のシフト量の特定に用いるシフト量検出符号を付加した符号である付記１乃至３いずれか一項に記載の電子透かし埋め込み装置。
（付記５）
電子透かし情報のビット列を含む第一符号語を生成し、
前記電子透かし情報に基づいて巡回シフト系列を生成し、
生成された前記巡回シフト系列に基づいて前記第一符号語を巡回シフトして第二符号語を生成し、
生成された前記第二符号語をコンテンツに埋め込む処理をコンピュータが実行する電子透かし埋め込み方法。
（付記６）
透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出する符号語検出部と、
一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行うシフト系列検出部と、
検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成する候補生成部と、
前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する照合部と、
を備える電子透かし検出装置。
（付記７）
前記巡回シフト系列が、複数の乱数の系列に対して、前記電子透かし情報のビット列が示す開始位置からの乱数の系列である場合、
前記候補生成部は、
前記シフト系列と、前記乱数の系列との類似度が所定値以上である位置の数字を表すビット列を前記候補とする付記６記載の電子透かし検出装置。
（付記８）
前記シフト系列検出部は、
前記一の第二符号語に対し、他の第二符号語を巡回シフトしながら求める相互相関値に基づき、シフト量を算出するシフト量算出部と、
算出されたシフト量で、前記他の第二符号語を逆シフトする逆シフト部と、
逆シフトされた符号語と、前記一の第二符号語とを累積する符号更新部と、
累積された前記一の第二符号語に基づき、前記第一符号語に対応する第二検出符号と、シフト量を並べたシフト系列とを生成する第二検出符号生成部と、
を備える付記６又は７記載の電子透かし検出装置。
（付記９）
透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出し、
一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行い、
検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成し、
前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する処理をコンピュータが実行する電子透かし検出方法。
【符号の説明】
【０１８４】
１  情報処理装置
１０  制御部
２０  主記憶部
３０  補助記憶部
４０  通信部
５０  記録媒体Ｉ／Ｆ部
１０１  符号語生成部
１０２  シフト系列生成部
１０３  シフト部
１０４  埋め込み部
２０１  符号語検出部
２０２  シフト系列検出部
２０３  候補生成部
２０４  透かし情報検出部
２０５  透かし情報照合部
３０１  シフト量算出部
３０２  逆シフト部
３０３  符号更新部
３０４  第二検出符号生成部
【図１】
0005974463.tif 000014
【図２】
0005974463.tif 000015
【図３】
0005974463.tif 000016
【図４】
0005974463.tif 000017
【図５】
0005974463.tif 000018
【図６】
0005974463.tif 000019
【図７】
0005974463.tif 000020
【図８】
0005974463.tif 000021
【図９】
0005974463.tif 000022
【図１０】
0005974463.tif 000023
【図１１】
0005974463.tif 000024
【図１２】
0005974463.tif 000025
【図１３】
0005974463.tif 000026
【図１４】
0005974463.tif 000027
【図１５】
0005974463.tif 000028
【図１６】
0005974463.tif 000029
【図１７】
0005974463.tif 000030