(57)【要約】可逆なウォーターマーキングに対する多くの方法（元のホスト信号の完全な再構成を可能にする埋め込みスキーム）は、ウォーターマーク入りコンテンツのわずかな修正が、元の信号及び埋め込まれた補助データの両方のリカバリを妨げる点で非常に脆弱である。送信又はチャネル誤差に対するロバスト性を得るために、本発明による埋め込み方法は、データ埋め込み容量の一部に誤差補正データを収容する。有利な実施例において、ホスト信号（３６）はセグメントに分割され、セグメント（Ｓ(ｎ)）に対する誤差補正データ（ｐ(ｎ)）は、前記ホスト信号を再構成する復元データ（ｒ(ｎ)）と一緒に次のセグメント（Ｓ(ｎ＋１)）に埋め込まれているデータ（３７）に収容される。前記埋め込み容量の残りの部分は、ペイロード（ｗ）に対して使用される。
2006516848.tif 000002
【特許請求の範囲】
【請求項１】
ホスト信号に補助データを埋め込む方法であって、
埋め込み率及び歪を持つデータ埋め込み方法を使用して複合信号を生成するステップと、
前記ホスト信号を復元する復元データを収容するために前記埋め込み率の第１の部分を使用し、前記補助データを埋め込むために前記埋め込み率の第２の部分を使用するステップと、
を有する方法において、
前記方法が、前記復元データ及び／又は前記補助データ内の誤差を補正する誤差補正データを埋め込むために前記埋め込み率の第３の部分を使用するステップを有することを特徴とする方法。
【請求項２】
ホスト信号に補助データを埋め込む方法であって、
前記ホスト信号をセグメント化するステップと、
所定の埋め込み率及び歪を持つ所定のデータ埋め込み方法を使用してホスト信号セグメントにデータを埋め込み、それぞれの複合信号セグメントを生成するステップと、
前記複合信号セグメントを条件として前記ホスト信号セグメントを識別する復元データを決定するステップと、
前記埋め込み率の一部を使用して前記復元データを次のホスト信号セグメントに埋め込むステップと、
を有する方法において、前記方法が、
前記複合信号セグメント内の誤差を補正する誤差補正データを生成するステップと、
前記埋め込み率の他の部分を使用して前記誤差補正データを前記次のホスト信号セグメントに埋め込むステップと、
前記埋め込み率の残りの部分を使用して前記ホスト信号セグメントに前記補助データを埋め込むステップと、
を有することを特徴とする方法。
【請求項３】
各セグメントが、前記補助データ並びに前のセグメントに対する前記復元データ及び前記誤差補正データを有する、請求項２に記載の方法。
【請求項４】
前記セグメントが等しい長さを持つ、請求項３に記載の方法。
【請求項５】
（ａ）所定の長さを持つ第１のホスト信号セグメントのみに補助データを埋め込むステップと、
（ｂ）次のセグメントに前のセグメントに対する前記復元データ及び前記誤差補正データを埋め込むステップと、
（ｃ）前記次のセグメントの長さを前記復元データ及び前記誤差補正データの量に適合するステップと、
（ｄ）前記次のセグメントの長さが所定の閾値より小さくなるまで前記ステップ（ｂ）及び（ｃ）を繰り返すステップと、
を有する請求項２に記載の方法。  
【請求項６】
ホスト信号に補助データを埋め込む装置であって、
前記ホスト信号をセグメント化するセグメント化手段と、
ホスト信号セグメントにデータを埋め込んでそれぞれの複合信号セグメントを生成する所定の埋め込み率及び歪を有する所定のデータ埋め込み器と、
前記複合信号セグメントを条件として前記ホスト信号セグメントを識別する復元データを決定する手段と、
を有し、
前記データ埋め込み器が、前記埋め込み率の一部を使用して前記復元データを次のセグメントに埋め込むように構成される、
当該装置において、
前記装置が更に、前記複合信号セグメント内の誤差を補正する誤差補正データを生成する手段を有し、前記データ埋め込み器が更に、前記埋め込み率の他の部分を使用して前記誤差補正データを前記次のホスト信号セグメントに埋め込み、前記埋め込み率の残りの部分を使用して前記ホスト信号セグメントに前記補助データを埋め込むように構成されることを特徴とする装置。
【請求項７】
請求項２ないし５のいずれか一項に記載の方法により生成された複合信号からホスト信号を再構成する方法において、
前記複合信号をセグメント化するステップと、
複合信号セグメントから埋め込まれた誤差補正データを取り出すステップと、
前記誤差補正データを前の複合信号セグメント内の誤差を補正するために使用するステップと、
前記複合信号セグメントから埋め込まれた復元データを取り出すステップと、
前記前の複合信号セグメントを鑑みて前のホスト信号セグメントを再構成するために前記復元データを使用するステップと、
を有する方法。
【請求項８】
請求項２ないし５のいずれか一項に記載の方法により生成された複合信号からホスト信号を再構成する装置において、
前記複合信号をセグメント化するセグメント化手段と、
複合信号セグメントから埋め込まれた誤差補正データを取り出す手段と、
前記誤差補正データを使用して前の複合信号セグメント内の誤差を補正する誤差補正手段と、
前記複合信号セグメントから埋め込まれた復元データを取り出す手段と、
前記復元データを使用して前記前の複合信号セグメントを鑑みて前のホスト信号セグメントを再構成する手段と、
を有する装置。
【請求項９】
埋め込まれたデータを持つセグメントの形式の複合情報信号において、複合信号セグメントに埋め込まれた前記データが、前の複合信号セグメントを条件として前のホスト信号セグメントを識別する復元データを有し、更に前記前の複合信号セグメント内の誤差を補正する誤差補正データを有する、複合情報信号。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ホスト信号に補助データを埋め込む方法であって、複合信号を生成するために埋め込み率及び歪を持つデータ埋め込み方法を使用するステップと、前記ホスト信号を復元する（restore）復元データを収容するために前記埋め込み率の第１の部分を使用し、前記補助データを埋め込むために前記埋め込み率の第２の部分を使用するステップとを有する方法に関する。本発明は、ホスト信号に補助データを埋め込む対応する装置にも関する。
【０００２】
本発明は更に、このようなホスト信号を再構成する方法及び装置、並びに埋め込まれたデータを有する複合情報信号に関する。
【背景技術】
【０００３】
多くのウォーターマーキング及びデータ隠蔽（data-hiding）スキームの不所望な副作用は、補助データが埋め込まれるホスト信号が歪まされることである。したがって、埋め込まれる情報量と引き起こされる歪との間の最適なバランスを見つけることは、活発な研究分野である。近年、ウォーターマーキング及びデータ隠蔽スキームの歪に対する容量の基本的な限度の理解において大きな進展があった。しかしながら幾つかの応用に対しては、どんなに小さくても補助データによる歪は許されない。これらの場合、可逆な（reversible）データ隠蔽方法の使用が、解決法を提供する。可逆なデータ隠蔽スキームは、元のホストデータの完全な且つ目に見えない（blind）復元（即ち追加の信号無し）を可能にするスキームとして定められる。
【０００４】
冒頭の段落で定められた可逆なデータ隠蔽方法は、J. Friedrich, M. Goljan, and R. Du,“Lossless Data Embedding For All Image Formats”, Proceedings of SPIE, Security and Watermarking of Multimedia Contents, San Jose, 2000に記載されているが、理論的な制限についてはほとんど注目されていない。このFriedrich他の文書において、信号ＸのフィーチャのサブセットＢ（例えばビットマップ画像の特定のビット面、又はＪＰＥＧ画像の特定のＤＣＴ係数の最小有効ビット）は、（ｉ）Ｂが無損失で圧縮されることができるように、且つ（ｉｉ）Ｂの無作為化がほとんど影響力をもたないように得られる。無損失なデータ隠蔽は、この場合、Ｂの無損失圧縮、補助データとのビットストリームの連結及び元のセットＢの置き換えにより達成される。
【０００５】
T. Kalker and F. Willems,“Capacity Bounds And Constructions For Reversible Data-Hiding”, Proceedings of the International Conference on Digital Signal Processing”, 1, pp. 71-76, June 2002において、可逆なウォーターマーキングスキームの容量に関する幾つかの最初の結果が得られている。この文書において、Kalker他は、所定の埋め込み率及び歪を有する所定の埋め込み器を使用する。Kalker他は、埋め込み容量が、複合信号を条件として（conditioned on）ホスト信号を識別する復元データをホスト信号に埋め込むことにより増加されることができることを示した。これは、前記復元データが、前記複合信号を鑑みて、いずれのホスト信号サンプルが、埋め込み処理によりいずれの修正を受けるのかを定めることを意味すると理解される。実際の実施例において、Kalker他は、前記ホスト信号をセグメントに分割し、このようなセグメントに対する復元データを次のセグメントに埋め込み、埋め込み率の残りの部分を補助データの埋め込みに使用する。このような可逆なデータ隠蔽スキームは、“再帰的な”可逆埋め込みと称される。本発明は、このような再帰的な可逆埋め込みスキームをも扱う。
【０００６】
Kalker他の再帰的な可逆埋め込みスキームを含む可逆埋め込みスキームの問題は、極めて脆弱な性質を持つことである。ウォーターマーク入りデータの単一のビットの変更は、元のホスト信号及び埋め込まれた補助データの両方のリカバリを妨げる。これは、可逆なウォーターマーキングスキームの有用性に厳しい制限を加える。所有者がウォーターマーク入りデータ（例えばアーカイブ）を完全に制御する状況、又は認証に関連した状況のみに、これらのウォーターマーキングスキームは、有用な応用を持つ。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、改良された可逆なデータ埋め込み方法及び装置、並びに対応する元のホスト信号を再構成する方法及び装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明の第１の態様によると、請求項１に記載の方法が提供される。本発明は、可逆な埋め込みスキームの埋め込み容量の一部が、ペイロード及び前記ペイロードを運ぶホスト信号のエラー保護に対して使用されることができるという洞察を利用する。したがって、前記埋め込みスキームは、チャネル誤差に対してロバストである。
【０００９】
ウォーターマーク入りホスト信号に誤差補正データを埋め込むことは、米国特許出願ＵＳ２００３／０００９６７０の特定の段落［０４１９］から既知であることに注意すべきである。しかしながら、この刊行物において、誤差補正データは、ウォーターマークペイロードのみを保護する。
【００１０】
他の独立請求項２に記載の本発明の他の態様によると、複合信号の所定のセグメントに対する誤差補正データは、ホスト信号の次のセグメントに埋め込まれる。このようにして、高い埋め込み率を持つロバストな再帰的な可逆埋め込みスキームが得られる。前記誤差補正データが、他のデータの処理と互換性のあるように処理されることができることは、本発明の特定の利点である。
【発明を実施するための最良の形態】
【００１１】
図１は、本発明によるホスト信号に補助データを埋め込む埋め込み装置３と、前記ホスト信号を再構成する再構成装置５とを有するシステムを概略的に示す。前記システムは、不連続な（discrete）文字（alphabet）からシンボルのホストシーケンスｘ1N=ｘ1ｘ2..ｘNを生成する不連続なメモリレスソース１を有する。好適な実施例において、ソース１はバイナリソースであり、シンボルｘiは、例えば、ビットマップ画像の特定のビット面のビット、又はＪＰＥＧ画像の特定のＤＣＴ係数の最小有効ビットである。しかしながら、本発明はバイナリソースに限定されない。
【００１２】
補助データ又はメッセージソース２は、ｘ1Nと独立に、確率１／Ｍのメッセージ指標（index）又はメッセージシンボルｗ∈{１,２,..,Ｍ}を生成する。埋め込み装置３は、メッセージｗをホストシーケンスｘ1Nに埋め込み、シンボルの複合信号シーケンスｙ1N＝ｙ1ｙ2..ｙNを形成する。シーケンスｙ1Nはｘ1Nに近くなければならない、即ち平均歪はある特定の歪尺度Ｄに対して小さくなくてはならないことを必要とする。ソースシンボル毎のビットの埋め込み率Ｒは、
Ｒ＝(１／Ｎ)log2(Ｍ)
と定義される。
【００１３】
前記複合シーケンスは、ウォーターマーク入りシーケンスｙ1Nの劣化バージョンｚ1Nを生成するために遷移確率行列Ｑ(・|・)を持つメモリレスアタックチャネル（memoryless attack channel）４を通って送信される。単語アタックチャネルは、能動的且つ理性的なアタッカ（attacker）の存在を示唆するので、幾分か誤称である。しかしながら、この記載において、このような暗示的な意味は意図されておらず、単語‘アタック’は、ウォーターマーキングの文献の一般的な用語を反映するように選択されただけである。再構成装置５は、ホストシーケンスｘ1Nの推定を生成し、複合シーケンスｚ1Nから埋め込まれたメッセージｗを取り出す。
【００１４】
本発明はバイナリソースに限定されないが、ここで文字ｘi＝{０,１}を有するメモリレスバイナリソース１を考え、歪尺度としてハミング距離（Hamming distance）を使用する。ｐ1＝Ｐｒ{ｘi＝１}及びｐ0＝Ｐｒ{ｘi＝０}＝１−ｐ1とする。アタックチャネル４は、ｄに等しい０→１遷移確率を持つバイナリ対称チャネルとして与えられるものとする。この場合、歪Ｄav＝０.５を持つロバストな可逆データ隠蔽スキームを構築するのは、理論的に及び漸近的に容易である。
【００１５】
脆弱な可逆ウォーターマーキングをロバストな可逆ウォーターマーキングに拡張する複数の可能性が存在する。第一に、ロバスト性は、ウォーターマークペイロードのロバスト性に帰することができ、即ちチャネル劣化は、ペイロードのリカバリに干渉しない。第二に、ロバスト性は、可逆性の側面に帰することができ、即ち元のホスト信号は、チャネル劣化後に依然としてリカバされることができる。この第２のオプションは、元のホスト信号が復元されることができる度合いに関して更に詳細に述べられることができる。一方の極端な場合には、前記元のホスト信号は完全にリカバされることができ、他方の極端な場合には、前記元のホスト信号は、前記チャネル劣化と両立する歪までしか取り出されることができない。第三に及び最後に、ロバスト性は、ペイロード及び可逆性の両方に帰することができる。これら第１及び第２のオプションは、可逆ウォーターマーキングの所望の性質の２つのうち１つが失われるので（ペイロード又は可逆性）、限定された適用性を持つ。本発明は、ロバスト性がペイロード及び可逆性の両方の側面に帰する第３のオプションに焦点を合わせる。
【００１６】
Fridrich他の教示によると、長さＮのホスト信号シンボルｘ1Nのストリングは、長さＫのストリングｙ1Kに圧縮され、ここでＫはおよそＮ×ｈ(ｐ1)に等しく、ｈ(・)はバイナリエントロピを示す。これは、全シーケンスｘ1N又は前記シーケンスが分割されることができる連続したセグメントｘ1Nに適用されることができることに注意する。この圧縮は、追加ビットを加えるために利用されることができるＮ−Ｋビットのスペースを残す。本発明によると、送信又はチャネル誤差に対するロバスト性は、ここでこのスペースの一部に誤差補正ビットを収容することにより得られる。大きなＮに対して、補正されるべき誤差の数はｄ×Ｎである。加えられなければならないパリティ確認ビットの数がＮ×ｈ(ｄ)に等しいような誤差補正コードが存在することを示すのは非常に容易である。残りの部分は、補助（メッセージ）データビットｗで埋められることができる。加えられることができる補助データビットの数は、Ｒ(ｐ1,ｄ)×Ｎで示されるものとし、ここでＲ(ｐ1,ｄ)は埋め込み率を示す。この“単純な”ロバストな埋め込みスキームの前記埋め込み率は、この場合、
Ｎ×ｈ(ｐ1)＋Ｎ×ｈ(ｄ)＋Ｎ×Ｒ(ｐ1,ｄ)＝Ｎ、又は
Ｒ(ｐ1,ｄ)＝１−ｈ(ｐ1)−ｈ(ｄ)
から得られる。明らかに、このロバスト性は、ｈ(ｄ)＞１−ｈ(ｐ1)であるアタックチャネルに対して達成されることができない。
【００１７】
関連した復号手順は、この埋め込み手順の単純な反転である。第一に、劣化シーケンスｚ1Nが誤差補正復号を受ける。第二に、誤差補正データを減算した補正されたシーケンスは、長さＮのシーケンスが得られるまで展開される（decompressed）。残りのビットは、この場合、補助メッセージビットとして自動的に得られる。
【００１８】
上述の埋め込みスキームは、ｘ1N内のシンボルの一部分αのみに対して上述の構成を実行することによりわずかに一般化されることができる。これは、しばしば“タイムシェアリング（time-sharing）”と称される。結果として生じる歪及び情報率は、この場合、
Ｄav＝α／２  及び
Ｒ(ｐ1,ｄ)＝α(１−ｈ(ｐ1))−ｈ(ｄ)
により与えられる。換言すると、上記の式の右辺が正である場合には、漸近的に率−歪関数Ｒ(Ｄ)、即ち
Ｒ(Ｄ)＝２Ｄ(１−ｈ(ｐ1))−ｈ(ｄ)  （１）
を達成することができる。このタイムシェアリング構成において、全ストリングに対する前記パリティ確認ビットは、圧縮されている部分において符号化されるべきであることに注意すべきである。パリティ確認ビットの包含を別にすると、このロバストな可逆データ隠蔽の方法は、本質的にFridrich他により提案されたものと同じ方法である。
【００１９】
Kalker他は、誤差無しチャネル４に対して、Fridrich他のスキームが最適でないことを示した。本発明者は、ここでロバストな埋め込みに対して、式（１）で与えられた結果が最適でないことも発見した。
【００２０】
図２は、送信又はチャネル誤差に対してロバストであり、より高い埋め込み率を持つ埋め込み装置３の実施例を示す。誤差補正符号化回路３５を別にすると、前記装置は、Kalker他の刊行物の教示にしたがう。この装置の動作は、本出願人の予定日まで公開されない国際特許出願ＷＯ０３／１０７６５３に余すところ無く記載されており、ここでは簡潔に要約される。
【００２１】
前記装置は、長さＮのホスト信号シーケンスｘ1Nを長さＫのセグメントｘ1Kに分割するセグメント化段３０を有する。まず、全てのセグメントが同じ長さＫを持つと仮定されるが、後に前記セグメントが異なる長さを持つ実施例が記載される。再び、ホスト信号Ｘが文字{０,１}を持つバイナリ信号であると仮定される。
【００２２】
前記装置は、データ埋め込み器３１を有し、データ埋め込み器３１は、前記ホスト信号のサンプルを修正し、したがって前記ホスト信号の歪を取り込むことにより所定の埋め込み率でペイロードｄを埋め込むという意味で従来的である。埋め込み器３１は、各ホスト信号セグメントＸ1Kに対して１つの複合信号セグメントＹ1Kを生成する。セグメント結合（desegmentation）回路３２は、前記セグメントを連結して複合信号シーケンスＹ1Nを形成する。
【００２３】
前記装置の好適な実施例において、埋め込み器３１は、M. van Dijk及びF.M.J. Willemsによる記事“Embedding Information in Grayscale Images”, Proceedings of the 22nd Symposium on Information Theory in the Benelux, Enschede, The Netherlands, May 15-16, 2001, pp. 147-154の教示にしたがって動作する。この記事において、著者は、効率的な率−歪比を持つ損失性埋め込みスキームを記載している。より具体的には、複数Ｌ（Ｌ＞１）のホスト信号サンプルが、ホストシンボルのブロック又はベクトルを与えるように一緒にグループ分けされる。メッセージシンボルｄをＬのホストシンボルのブロックＸ1Lに埋め込むために、前記埋め込み器は、出力ブロックＹ1Lのシンドローム（syndrome）が、所望のメッセージシンボルｄを表し、ハミング（Hamming）の意味でＸ1Lに最も近くなるように、前記ブロックの１つ又は複数のホストシンボルを修正する。データワード又はベクトルのシンドロームは、これに所定の行列を乗算した結果である。
【００２４】
これを説明するために、ブロック長Ｌ＝３を持つハミングコード（Hamming code）を使用するデータ埋め込み法が、ここで簡潔に要約される。このコードは、２ビットがブロックに埋め込まれることを可能にする（Ｒ＝２／３ビット／シンボル）。全ての数学的演算が２進法演算であることに注意する。
【００２５】
３ビットのブロック又はベクトルのシンドロームを計算するために、前記ベクトルは、以下の３×２の行列、即ち
【数１】
2006516848.tif 000003
で乗算される。例えば、
【数２】
2006516848.tif 000004
なので、入力ベクトル(００１)のシンドロームは(１１)である。このシンドローム(１１)が前記埋め込まれたデータを表す。明らかに、ホストベクトルのシンドロームは、一般に埋め込まれるべきメッセージと等しくない。したがって、前記ホストシンボルの１つは、しばしば修正されなければならない。例えばメッセージ(０１)が(１１)の代わりに埋め込まれるべきである場合に、埋め込み器２３は、第２のホストシンボルを変更し、この結果、元のホストベクトル(００１)は(０１１)に修正される、即ち
【数３】
2006516848.tif 000005
である。“２乗誤差”が、しばしば歪を表すのに使用され、即ち
Ｄ(ｘ,ｙ)＝(ｙ−ｘ)2
である。この埋め込みスキームの３シンボル毎の歪は、(１／４)・０2＋(３／４)・１2＝３／４（前記ホスト信号のいずれも変更されない確率１／４及び１つのシンボルが±１だけ変更される確率３／４）であり、この結果、シンボル毎の平均歪はＤ＝１／４である。前記埋め込み率は、ブロック毎に２ビットであり、即ち２／３ビット／シンボルである。
【００２６】
同様に、３データビットが７の信号シンボルのブロックに埋め込まれることができ、４ビットが１５の信号シンボルに埋め込まれることができ、以下同様である。より一般的には、ハミングコードに基づく埋め込みスキームは、多くとも１のホストシンボルを修正することにより、ｍのメッセージシンボルがＬ＝２m−１のホストシンボルのブロックに埋め込まれることを可能にする。前記埋め込み率は、
Ｒ＝ｍ／(２m−１)  （２）
であり、前記歪は、
Ｄ＝１／２m  （３）
である。
【００２７】
元のホスト信号Ｘ1Nを再構成することを可能にするために、復元符号化器３３は、各ホスト信号セグメントＸ1K及び複合信号Ｙ1Kを受信する。前記復元符号化器は、Ｙ1Kを条件としてＸ1Kを符号化し、これはＹ1Kを鑑みてＸ1Kを符号化するとも表されることができる。実際に、符号化器３３は、いずれのホストシンボルがいずれの修正を受けたのかに関する記録を保持し、この情報を復元データｒに符号化する。表現“いずれのホストシンボルがいずれの修正を受けたのか”は、幅広く解釈されなければならない。前記歪がＤ＝０又はＤ＝１のいずれかである場合（本実施例の場合）には、いずれのシンボルが歪を受けたのかを識別するのに十分である。他のタイプの埋め込み器３１に対して、前記歪の量が、同様に符号化されなければならない。ビット／シンボル単位での復元データ率は、埋め込み器３１の埋め込み率より小さいことが示されることができる。
【００２８】
復元符号化器３３が、本発明の機能的フィーチャを表すことに注意すべきである。この回路は、これ自体で物理的に存在する必要はない。この後に示される装置の実際的な実施例において、いずれのシンボルが歪まされているかに関する情報は、埋め込み器３１自体により固有に生成される。
【００２９】
本例において、埋め込み容量の一部は、前記信号サンプルの１つが修正されているかどうか、及び修正されていれば、いずれのサンプルが修正されているサンプルであるかを識別するために使用される。ブロック長３（ｍ＝２、Ｌ＝３）を持つハミングコードに対して、４つの可能性が存在し、即ち、３つのホストシンボルのいずれも変更されていないか、第１のシンボルが修正されているか、第２のシンボルが修正されているか、又は第３のシンボルが修正されているかである。ホスト信号ソースのエントロピＨ(ｐ)が１と等しい場合に、全ての事象は等しい確率を持つ。この場合、ブロック毎のメッセージビットの両方が復元に必要とされる。しかしながら、前記信号ソースのエントロピＨ(ｐ)が１に等しくない場合に、前記事象は異なる確率を持ち、ｍより少ない復元ビットが必要とされる。これは、他のデータを前記ホスト信号に埋め込むスペースを残す。
【００３０】
ｐ0＝０.９であると仮定する。したがって、前記ソースがホストベクトル(０００)を生成する確率ｐ(ｘ＝０００)は、(０.９)3＝０.７２９である。前記ソースが、ホストベクトル(００１)を生成する確率ｐ(ｘ＝００１)は、(０.９)2×(０.１)＝０.０８１であり、以下同様である。前記装置の埋め込み器３１は、複合ベクトルｙ＝０００を生成したと仮定する。元のホストベクトルｘは、(０００)であった可能性がある。この場合、前記元の信号サンプルのいずれも修正されていない。しかしながら、前記元のホストベクトルは、(００１)、(０１０)又は(１００)であった可能性もある。この場合、前記ホストシンボルの１つが修正されている。ｙ＝０００を鑑みて、前記ホストベクトルがｘ＝０００である確率は、
ｐ(ｘ＝０００|ｙ＝０００)＝ｐ(ｘ＝０００)／(ｐ(ｘ＝０００)＋ｐ(ｘ＝００１)＋ｐ(ｘ＝０１０)＋ｐ(ｘ＝１００))＝０.７５
である。
【００３１】
同様に、ｙ＝０００がホストベクトル(００１)、(０１０)又は(１００)から生じる確率が計算されることができる。これは、
ｐ(ｘ＝００１|ｙ＝０００)＝０.０８３
ｐ(ｘ＝０１０|ｙ＝０００)＝０.０８３
ｐ(ｘ＝１００|ｙ＝０００)＝０.０８３
を生じる。
【００３２】
したがって、各複合ベクトルｙは、条件付き確率ｐ(ｘ|ｙ)の関連したセットを持つ。これらは以下の表に要約される。前記表は、各ブロックｙに対して、対応する条件付きエントロピＨ(ｘ|ｙ)をも含む。前記条件付きエントロピは、ベクトルｙを鑑みて、元のベクトルｘの不確実性を表す。前記表は、メッセージ００、０１、１０及び１１が等しい確率１／４を持つと仮定すると、各ベクトルｙに対して、確率ｐ(ｙ)をも含む。例えば、確率ｐ(ｙ＝０００)は、
ｐ(ｙ＝０００)＝(１／４)ｐ(ｘ＝０００)＋(１／４)ｐ(ｘ＝００１)＋(１／４)ｐ(ｘ＝０１０)＋(１／４)ｐ(ｘ＝１００)＝０.２４３０
と計算されている。
【表１】
2006516848.tif 000006
【００３３】
全てのブロックｙに対して平均された前記ソースの条件付きエントロピＨ(Ｘ|Ｙ)は、ｙを鑑みてｘを再構成するためのビット数を表す。本例において、前記平均エントロピは、
Ｈ(Ｘ|Ｙ)＝Σyｐ(ｙ)Ｈ(ｘ|ｙ)＝０.８６４２ビット／ブロック
に等しい。
【００３４】
したがって、ブロック毎に０.８６４２の復元ビットが、元のブロックを識別するために必要とされる。これは、他のデータを埋め込むために２−０.８６４２＝１.１３５８ビット／ブロックを残す。この容量がペイロードを埋め込むために使用される場合、データ率Ｒは、
Ｒ＝１.１３５８／３＝０.３７８６ビット／シンボル
である。
【００３５】
前記複合信号の歪Ｄは、ここで埋め込まれるデータｄに割り当てられた特定の意味の影響を受けないことに注意する。前に述べられたように、この無損失埋め込みスキームの歪はＤ＝１／４である。
【００３６】
本発明によると、残りの埋め込み容量の一部は、ここで送信又はチャネル誤差に対するロバスト性を達成するために誤差補正データを収容するために使用される。
【００３７】
このために、埋め込み装置３（図２参照）は、パリティビットｐを生成する誤差補正符号化回路３５を有することによりロバストにされる。セグメント内のｄ×Ｋの誤差を補正するために必要とされるパリティビットの数は、シンボル毎にｈ(ｄ)ビットであり、ここで遷移パラメータｄを持つ対称チャネルを仮定した。例えば、ｄ＝０.０５の場合、シンボル毎にｈ(ｄ)＝０.２８６４のパリティビットが埋め込まれるべきである。
【００３８】
前記残りの埋め込み容量は、補助データ又はペイロードｗを埋め込むために使用される。本例において、シンボル毎に０.３７８６−０.２８６４＝０.０９２２のペイロードビットｗが埋め込まれることができる。復元データｒ、パリティビットｐ及びペイロードｗは、連結回路３５において連結される。連結されたデータｄが、埋め込みのために埋め込み器３１に印加される。
【００３９】
より一般的に、本発明者は、以下の定理を考案した。Ｄは、平均歪Ｄav＝Δ及び率ρを持つブロック長Ｋに対するデータ隠蔽方法であるとする。Ｄをシーケンスｘ1Nからシーケンスｙ1Nまでの（必ずしもメモリレスではない）テストチャネルと見なす。Ｃは上記の再帰的な構成であるとする。この場合、Ｃ(Ｄ)は、平均歪Δ及び率ρ−Ｈ(Ｘ1K|Ｙ1K)／Ｋ−ｈ(ｄ)を持つ可逆データ隠蔽スキームである。
【００４０】
Kalker他の従来技術の刊行物に開示されている可逆な埋め込み装置は再帰的である。これは、連結回路３５が、１セグメントの遅延で復元データｒを埋め込み器３１に印加することを意味すると理解される。したがって、あるセグメントに対する復元データは、次のセグメントに埋め込まれる。本発明の好適な実施例によると、連結回路３５は、遅延、好ましくは同じ１セグメントの遅延で前記セグメントの誤差補正データｐをも埋め込み器３１に印加する。したがって、前記セグメントに対する前記誤差補正データも、前記次のセグメントに埋め込まれる。図２を参照して理解されるように、これは、誤差補正データｐが、復元データｒと同様に及び互換性を持って処理されることができるという利点を持つ。したがって、ロバストな再帰的な可逆データ埋め込み装置３は、複雑ではない（ハードウェア又はソフトウェア）構成を持つ。
【００４１】
復元データｒ及びパリティデータｐを次のセグメントに埋め込む特定の方法の２つの実際的な例が、ここに記載される。これらの例において、埋め込み器３１は、ブロック長３を持つ上述のタイプの埋め込み器であると仮定される。式（２）及び（３）によると、この非ロバスト及び不可逆な埋め込み器３１の歪はＤ＝１／４であり、埋め込み率はＲ＝２／３ビット／シンボルである。更に、前述のように、前記ホスト信号はシンボル確率ｐ0＝０.９を持ち、チャネル４は遷移確率ｄ＝０.０５を持つと仮定される。
【００４２】
第１の例において、前記ホスト信号は、Ｋ＝３０００シンボル（ビット）の等しい長さのセグメントＳ(ｎ)に分割される。これは、図３の参照符号３６により図示される。この図の参照符号３７は、埋め込まれたデータｄを示す。前記埋め込み率はＲ＝２／３ビット／シンボルであり、したがって２０００ビットが各セグメントに埋め込まれることができる。以前に計算されたように、ブロック毎の０.８６４２の復元ビットｒ（０.２８８ビット／シンボル、セグメント毎に８６４ビット）が、セグメントＹを鑑みてセグメントＸを再構成するために必要とされる。前記図に示されるように、セグメントＳ(ｎ)に関連した復元ビットｒ(ｎ)は、次のセグメントＳ(ｎ＋１)に埋め込まれ、セグメントＳ(ｎ)に埋め込まれた復元ビットは、前のセグメントＳ(ｎ−１)を再構成する復元ビットｒ(ｎ−１)である。前記数は、統計的な平均数であることに注意する。復元ビットの正確な数は、セグメント毎に異なる可能性がある。例えば、復元ビットの各系列に適切な終点コードを設けることにより、復元ビットｒと前記埋め込まれたデータの残りとの間の境界を識別することは有利である。
【００４３】
以前にも示されたように、シンボル毎の０.２８６４のパリティビット（セグメント毎の８６０ビット）が、誤差補正のために埋め込まれるべきである。セグメントＳ(ｎ)と関連したパリティビットは、ｐ(ｎ)で示される。図３は、これらが次のセグメントＳ(ｎ＋１)にも埋め込まれることを示す。これは、ペイロードｗを埋め込むために、平均してセグメント毎に２０００−８６４−８６０＝２７６ビットを残す。したがって、前記ロバストな再帰的な可逆埋め込み器の埋め込み率は、３０００のシンボル毎に２７６ビットであり、これは既に前に述べられた０.０９２２ビット／シンボルに対応する。
【００４４】
本実施例において、シーケンスの最初及び最後のセグメントは、異なって処理されなければならないことに注意する。前記最初のセグメントにおいて、ペイロードデータｗのみが埋め込まれることができる。前記最後のセグメントにおいて、前述の“単純な”埋め込み方法が、前記最後のセグメントに関する復元データｒ及び誤差補正データｐを収容するために使用されることができる。
【００４５】
図４は、ホスト信号Ｘをセグメント化する第２の例を示す。本実施例において、所定の初期長さを持つ最初のセグメントＳ(０)は、ペイロードｗのみを備える。このセグメントに対する復元ビットｒ(０)及びパリティビットｐ(０)は、次のセグメントＳ(１)に収容される。次のセグメントＳ(１)は、ここで復元ビットｒ(０)及びパリティビットｐ(０)を収容するのに必要とされる長さを割り当てられる。次のセグメントＳ(１)は、新しい複数の復元ビットｒ(１)及びパリティビットｐ(１)が更に他のセグメントＳ(２)に埋め込まれる必要があり、以下同様である。このプロセスは、複数回、例えば前記次のセグメントが所定の閾値より小さくなるまで繰り返される。ペイロードｗは前記次のセグメントには埋め込まれない。全プロセスは、この場合、所定の初期長さを持つ新しい最初のセグメントＳ(０)に対して繰り返される。
【００４６】
図５は、受信された複合信号から元のホスト信号を再構成する装置の概略図を示す。前記装置は、アタックチャネル４からシーケンスＺ1Nを受信する（図１参照）。セグメント化回路５０は、前記シーケンスを長さＫのセグメントＺ1Kに分割する。セグメントＺ1Kは、データ取り出し回路５１及び誤差検出及び補正回路５２に反転された順序で印加される。
【００４７】
データ取り出し回路５１は、前記複合信号に埋め込まれているデータｄを取り出す。データｄが長さＬのハミングコードを使用して埋め込まれている好適な実施例において、取り出し回路５１は、Ｌのシンボルの各ブロックのシンドロームを決定する。前記回路は、前記取り出されたデータを誤差補正データｐ、復元データｒ及び補助ペイロードｗに分割する。
【００４８】
誤差補正データｐは、セグメントＺ1K内の誤差を補正するために誤差検出及び補正回路５２に印加される。これの出力は、推定された複合信号セグメント
2006516848.tif 000007
である。再構成ユニット５３は、取り出された復元データｒを使用して元のホスト信号Ｘ1Kに加えられた修正を元に戻すように構成される。前記好適な実施例において、復元データｒは、セグメントＹ1K内のシンボルの１つが修正されているか、及び修正されている場合には、いずれのシンボルが修正されているシンボルであるかを識別する。この復元は、推定された複合信号セグメント
2006516848.tif 000008
に適用され、元のホスト信号セグメントＸ1Kの推定値
2006516848.tif 000009
を生じる。埋め込まれた誤差補正データのため、この再構成は、ビット誤差が前記アタックチャネルにより生じた場合でさえも完全である。再構成されたホスト信号セグメント
2006516848.tif 000010
は、最後にセグメント結合回路５４において再び順序付けられ、セグメント結合される。
【図面の簡単な説明】
【００４９】
【図１】本発明によるホスト信号に補助データを埋め込む装置と、ホスト信号を再構成する装置とを有するシステムを概略的に示す。
【図２】図１に示された埋め込み装置の実施例を概略的に示す。
【図３】本発明の好適な実施例によりホスト信号をセグメントに分割する実際の例を示す。
【図４】本発明の好適な実施例によりホスト信号をセグメントに分割する実際の例を示す。
【図５】図１に示されたホスト信号を再構成する装置の実施例を概略的に示す。
【図１】
2006516848.tif 000011
【図２】
2006516848.tif 000012
【図３】
2006516848.tif 000013
【図４】
2006516848.tif 000014
【図５】
2006516848.tif 000015
【国際調査報告】
2006516848.tif 000016
2006516848.tif 000017
2006516848.tif 000018