(57)【要約】ある画像の好ましくは１つの高周波サブバンドに対するＩＷＴ（整数ウェーブレット変換）係数のブロックを提供すること、前記ブロック内の前記係数の平均値を求めること、ならびに論理０ビット値および論理１ビットの一方を第１のブロックに埋め込むために符号化された平均値を設定することを含む方法を提供する。
2007522693.tif 000002
【特許請求の範囲】
【請求項１】
画像の少なくとも１つの周波数サブバンドに対するＩＷＴ（整数ウェーブレット変換）係数のブロックを提供することと、
前記ブロック内の前記係数の平均値を求めることと、
論理０ビット値と論理１ビットの一方を第１のブロックに埋め込むために符号化された平均値を設定することと
を含む方法。
【請求項２】
前記設定は、前記ブロックに論理０値を埋め込むために前記平均値を変更しないことを含む、請求項１に記載の方法。
【請求項３】
前記設定は、前記ブロックに論理１ビット値を埋め込むために前記平均値を変更することを含む、請求項１に記載の方法。
【請求項４】
ＩＷＴ係数の前記ブロックにおける変更によって影響を受ける空間領域ブロック内の画素のグレースケール値に対してモジュロ２５６加算を使用しないことをさらに含む、請求項１に記載の方法。
【請求項５】
ＩＷＴ係数の前記ブロックに対応する空間領域ブロック内の画素のグレースケール値の切捨てを、前記グレースケール値のモジュロ２５６加算を使用せずに回避することをさらに含む、請求項１に記載の方法。
【請求項６】
前記設定により生じたエラー・ビットが存在する場合にはエラー符号訂正を用いてそれを訂正することをさらに含む、請求項１に記載の方法。
【請求項７】
前記ＩＷＴ係数の影響を受ける空間領域内の画素のグレースケール値の分布を識別することと、
前記グレースケール値の分布に従って前記設定をカスタマイズすることと
をさらに含む、請求項１に記載の方法。
【請求項８】
前記ＩＷＴ係数はＬＬ１係数を含む、請求項１に記載の方法。
【請求項９】
前記変更は、ＨＬ１サブバンド内のブロックの少なくとも１つの係数をあるシフト量だけシフトすることを含む、請求項３に記載の方法。
【請求項１０】
前記変更は、ＬＬ１サブバンド内の対応するブロックの少なくとも１つの係数を前記シフト量の約４分の１だけシフトすることをさらに含む、請求項９に記載の方法。
【請求項１１】
画像の少なくとも１つの周波数バンドに対するＩＷＴ（整数ウェーブレット変換）係数を複数の非オーバラップ・ブロックに分割することと、
前記ブロックのうちの第１のブロック内の係数の平均値を求めることと、
１つまたは複数のビットのデータを埋め込むために前記係数の前記平均値を修正することと
を含む方法。
【請求項１２】
前記修正による修正の対象となる少なくとも１つの係数、および前記修正の間に変更されない少なくとも１つの係数を識別することをさらに含む、請求項１１に記載の方法。
【請求項１３】
前記平均値の修正は、前記平均値にあるシフト量を加算することを含む、請求項１１に記載の方法。
【請求項１４】
前記平均値の修正は、前記平均値からあるシフト量を減算することを含む、請求項１１に記載の方法。
【請求項１５】
画像の少なくとも１つの周波数バンドに対するＩＷＴ（整数ウェーブレット変換）係数を複数の非オーバラップ・ブロックに分割することと、
前記ブロックのうちの第１のブロック内の係数の平均値を求めることと、
前記平均値を閾値と比較することと、
前記比較に基づいて前記ブロックからビット値を抽出することと
を含む方法。
【請求項１６】
前記抽出は、前記平均値の絶対値が前記閾値の絶対値よりも大きい場合に前記ブロックから論理１ビット値を抽出することを含む、請求項１５に記載の方法。
【請求項１７】
前記抽出は、前記平均値の絶対値が前記閾値の絶対値よりも小さい場合に前記ブロックから論理０ビット値を抽出することを含む、請求項１５に記載の方法。
【請求項１８】
前記抽出により生じたビット・エラーが存在する場合にはエラー訂正符号復号化を使用してそれを訂正することをさらに含む、請求項１５に記載の方法。
【請求項１９】
前記第１のブロックの影響を受ける空間領域ブロック内の画素のグレースケール値にオーバフローまたはアンダーフロー状態を生じさせない場合に限り、前記平均値の前記絶対値を、先行するデータ埋め込み工程の間に使用されたシフト量だけ減少させることをさらに含む、請求項１６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像中にデータを埋め込むための、また埋めまれたデータをそこから復元するための方法および装置に関する。
【背景技術】
【０００２】
データ秘匿とも呼ばれるデータ隠蔽は、有用なデータ（情報）を画像データなどのカバー・メディアに埋め込むための方法である。データが埋め込まれたカバー・メディアのことを、本明細書では「マーク・メディア（marked media）」と呼ぶ。データ隠蔽は、識別、注釈、著作権保護、認証などのために使用することができる。このような用途では、隠蔽データとカバー・メディアが密接に関連づけられていることもある。この種のデータ埋め込みは、透かし、あるいはより一般的には「マーキング」と呼ばれることも多い。隠蔽データは知覚的に透明であることが望ましい。言い換えれば、マーク・メディアはカバー・メディアにできる限り類似している必要がある。
【０００３】
カバー・メディアは一般に、埋め込まれたデータが存在することによりある種の歪みを受けることになる。さらに、埋め込まれたデータが除去された後でさえ、一般にカバー・メディアをそのデータが埋め込まれる前の状態に戻すことは困難である。具体的には、カバー・メディアのある種の永久歪みは、一般に隠蔽データが抽出された後でもそのまま残ることになる。歪みの原因には、丸め誤差、切捨て誤差、量子化誤差などがある。医学的診断や法の執行など、用途によっては隠蔽データが取り出された後でカバー・メディアを埋め込み前の状態に正確に復元することが重要になるので、このような歪みは問題になる。この要求を満たすマーキング技術は、無損失または無歪みと呼ばれる。このようなマーキング技術は可逆なマーキング技術とも呼ばれており、一般に元のメディア・データを正確に復元しなければならない用途に適するものである。
【０００４】
最近になって、いくつかの無損失マーキング技術が文献で報告されている。第１の方法は画像空間領域で行われるものである。シー．ダブリュ．ホンジンガー（C. W. Honsinger）、ピー．ジョーンズ（P. Jones）、エム．ラバニ（M. Rabbani）、およびジェイ．シー．ストッフェル（J. C. Stoffel）による「埋め込まれたデータを含むオリジナル画像の無損失復元（Lossless Recovery of an Original Image Containing Embedded Data）」と題する米国特許第６，２７８，７９１号（本明細書では「ホンジンガー」と呼ぶ）を参照されたい。この特許の開示は本願明細書に組み込まれる。
【０００５】
他の空間領域技術は、“ジェイ．フリードリッヒ（J. Fridrich）、エム．ゴルジャン（M. Goljan）およびアール．デュ（R. Du）、「可逆認証（Invertible authentication）」、Proc. SPIE、マルチ・メディア・コンテンツのセキュリティおよび透かし技術（Security and Watermarking of Multimedia Contents）、カリフォルニア州サンノゼ、２００１年１月（本明細書では「フリードリッヒ」と呼ぶ）”に報告されている。この文献の全体の開示は本願明細書に組み込まれる。変換領域での無歪みマーキング技術も存在する。ビー．マック（B. Macq）およびエフ．デューヤンド（F. Deweyand）、「医用画像のための信頼できるヘッダー（Trusted headers for medical images）」、DFG VIII-D II Watermarking Workshop、ドイツ  エルランゲン、１９９９年１０月（本明細書では「マック」と呼ぶ）。この文献の全体の開示は本願明細書に組み込まれる。
【０００６】
“シー．デ  ブリースコーワー（C. De Vleeschouwer）、ジェイ．エフ．ドレーグル（J. F. Delaigle）およびビー．マック（B. Macq）、「可逆透かしのヒストグラムの循環分析（Circular Interpretation on histogram for reversible watermarking）」、IEEE International Multimedia Signal Processing Workshop、フランス  カンヌ、３４５〜３５０ページ、２００１年１０月（本明細書では「デ  ブリースコーワー」と呼ぶ）”に報告されている方法の機能もまた、高品質ＪＰＥＧ圧縮に対して頑強性を示すことを除けば非常に限定されたものである。この文献の全体の開示は本願明細書に組み込まれる。これらの技術は、データ隠蔽よりもむしろ認証を対象としたものである。したがって、カバー・メディアに埋め込まれるデータの総量は限られている。
【０００７】
高埋め込み率のデータ隠蔽に適する最初の無損失マーキング技術は、“エム．ゴルジャン（M. Goljan）、ジェイ．フリードリッヒ（J. Fridrich）およびアール．デュ（R. Du）、「無歪みデータ埋め込み（Distortion-free data embedding）」、Proceedings of 4th Information Hiding Workshop、ペンシルベニア州ピッツバーグ、２００１年４月（本明細書では「ゴルジャン」と呼ぶ）”に示されている。この文献の全体の開示は本願明細書に組み込まれる。ゴルジャンでは、画像中の各画素は、各々がいくつかの隣接する画素からなる非オーバラップのブロックに分割される。例えば、このブロックは４つの連続する画素を含む水平ブロックでもよい。識別機能は、各ブロックを３つの異なるカテゴリに分類するように設定される。すなわち、正規（Regular）、特異（Singular）、および使用不能（Unusable）の各カテゴリである。著者らは各グループの滑らかさ（smoothness）を捕捉するためにこの識別機能を使用した。
【０００８】
各グループに可逆操作を適用することができる。詳細には、可逆操作は、あるグレー・レベル値を他のグレー・レベル値にマップすることができる。この操作は可逆である。なぜならば、この操作をあるグレー・レベル値に２回適用すると、元のグレー・レベル値が生成されるからである。したがって、この可逆操作は「フリッピング」と呼ばれる。代表的な画像については、小さな振幅でのフリッピングにより識別機能が増し、結果として正規グループが増加し、特異グループが減少する。このバイアスによって無歪みデータ隠蔽が可能になる。このアプローチはカバー・データを歪ませることなくデータを隠蔽するが、この技術を用いて隠蔽できるデータの量は、やはり特定の用途に対しては十分ではない。ゴルジャンによると、５１２×５１２×８のグレーの画像のペイロードは、３，０００ビットから２４，０００ビットの範囲にあると推定される。この方法についての他の問題は、画像に埋め込まれるデータの量が増大するにつれて、画像の視覚品質が低下することである。例えば、ＰＳＮＲ（ピーク信号対雑音比）は３５ｄＢ（デシベル）まで低下することがあり、画像中にある種の望ましくないアーチファクトが生じる可能性がある。
【０００９】
整数ウェーブレット変換に基づいた“グオロン  シュエン（Guorong Xuan）、ジードン  チェン（Jidong Chen）、ジエン  ヂュー（Jian Zhu）、ユン  キュー．シー（Yun Q. Shi）、ヂーチョン  ニー（Zhicheng Ni）およびウェイ  スー（Wei Su）、「整数ウェーブレット変換に基づく無歪みデータ隠蔽（Distortionless Data Hiding Based on Integer Wavelet Transform）」、IEEE International Workshop on Multimedia Signal Processing、米領バージン諸島  セントトマス、２００２年１２月（本明細書では「シュエン」と呼ぶ）”の方法は、最近提案された大量のデータを埋め込むことができる可逆データ隠蔽技術である。この文献は本願明細書に組み込まれる。シュエンの主要なアイデアは以下のとおりである。元の画像に整数ウェーブレット変換を適用した後で、サブバンドＬＨ，ＨＬ，ＨＨの各ビット・プレーンにおける２進の１と２進の０の間のバイアスは大幅に増加する。したがって、これらのビット平面における１と０を無損失に圧縮してデータ埋め込みのための多くの格納スペースを確保することができる。データ埋め込みの後で、マーク画像を形成するために逆整数ウェーブレット変換が適用される。この技術で得られる容量は極めて大きい。しかし、オーバフローまたはアンダーフロー状態を避けるために適用されるヒストグラム修正のために、マーク画像のＰＳＮＲは大きくない。画像によっては、ＰＳＮＲはわずかに２８ｄＢである。
【００１０】
ヒストグラム操作に基づく一つの方法は、最近発表された無損失データ隠蔽技術である。この技術は、大部分の画像に対して（ＰＳＮＲが４８ｄＢを越えることが保証された）高い画像品質を維持しながら大量のデータ（５１２×５１２×８のグレースケール画像の場合に５Ｋ〜８０Ｋビット）を埋め込むことができる。ズィ．ニー（Z. Ni）、ワイ．キュー．シー（Y. Q. Shi）、エヌ．アンサリ（N. Ansari）、およびダブリュ．スー（W. Su）、「可逆データ隠蔽（Reversible data hiding）」、IEEE International Symposium on Circuits and Systems、２００３年５月、タイ  バンコク（本明細書では「ニー」と呼ぶ）。この文献は本願明細書に組み込まれる。この文献（ニー）は、単に本特許出願の「背景技術」部分に記載したことにより従来技術であると認めるものではない。
【００１１】
しかしながら、ただ１つの従来の無損失データ隠蔽技術（デ  ブリースコーワー）だけがステゴ画像（埋め込みデータを含む画像）に適用された圧縮に対して頑強である。詳細には、ブリースコーワーだけが、圧縮によってステゴ・メディアが失われた後でもやはり、隠蔽データを正しく抽出することができる。他の既存の技術を用いた場合は、ステゴ・メディアの圧縮の後では、エラーなしに埋め込みデータを復元することはできない。
【００１２】
図１Ａおよび図１Ｂを参照すると、デ  ブリースコーワーの技術は圧縮に対して頑強であるが、その技術はモジュロ２５６加算を使用するので、面倒なごま塩状雑音を発生する。すなわち、画像グレースケール値が２５６（最も明るい）および／または０（最も暗い）に近づいたとき、モジュロ２５６加算は最も明るいグレー値と最も暗いグレー値の間でフリッピングを引き起こす可能性が高い。これは医用画像に関して発生することが多い。この種のごま塩状雑音は多くの用途で容認できないものである。
【特許文献１】米国特許第６，２７８，７９１号
【非特許文献１】ジェイ．フリードリッヒ（J. Fridrich）、エム．ゴルジャン（M. Goljan）およびアール．デュ（R. Du）、「可逆認証（Invertible authentication）」、Proc. SPIE、マルチ・メディア・コンテンツのセキュリティおよび透かし技術（Security and Watermarking of Multimedia Contents）、カリフォルニア州サンノゼ、２００１年１月
【非特許文献２】ビー．マック（B. Macq）およびエフ．デューヤンド（F. Deweyand）、「医用画像のための信頼できるヘッダー（Trusted headers for medical images）」、DFG VIII-D II Watermarking Workshop、ドイツ  エルランゲン、１９９９年１０月
【非特許文献３】シー．デ  ブリースコーワー（C. De Vleeschouwer）、ジェイ．エフ．ドレーグル（J. F. Delaigle）およびビー．マック（B. Macq）、「可逆透かしのヒストグラムの循環分析（Circular Interpretation on histogram for reversible watermarking）」、IEEE International Multimedia Signal Processing Workshop、フランス  カンヌ、３４５〜３５０ページ、２００１年１０月
【非特許文献４】エム．ゴルジャン（M. Goljan）、ジェイ．フリードリッヒ（J. Fridrich）およびアール．デュ（R. Du）、「無歪みデータ埋め込み（Distortion-free data embedding）」、Proceedings of 4th Information Hiding Workshop、ペンシルベニア州ピッツバーグ、２００１年４月
【非特許文献５】グオロン  シュエン（Guorong Xuan）、ジードン  チェン（Jidong Chen）、ジエン  ヂュー（Jian Zhu）、ユン  キュー．シー（Yun Q. Shi）、ヂーチョン  ニー（Zhicheng Ni）およびウェイ  スー（Wei Su）、「整数ウェーブレット変換に基づく無歪みデータ隠蔽（Distortionless Data Hiding Based on Integer Wavelet Transform）」、IEEE International Workshop on Multimedia Signal Processing、米領バージン諸島  セントトマス、２００２年１２月
【非特許文献６】ズィ．ニー（Z. Ni）、ワイ．キュー．シー（Y. Q. Shi）、エヌ．アンサリ（N. Ansari）、およびダブリュ．スー（W. Su）、「可逆データ隠蔽（Reversible data hiding）」、IEEE International Symposium on Circuits and Systems、２００３年５月、タイ  バンコク
【発明の開示】
【発明が解決しようとする課題】
【００１３】
したがって当技術分野では、一定量の頑強なデータを可逆な方法でカバー・メディアに埋め込む（ごま塩状雑音なしで元のカバー・メディアを保存することを可能にする）ためのシステムおよび方法が必要とされている。
【課題を解決するための手段】
【００１４】
ある画像の少なくとも１つの周波数サブバンドに対するＩＷＴ（整数ウェーブレット変換）係数のブロックを提供することと、そのブロック内の前記係数の平均値を求めることと、論理０ビット値と論理１ビットの一方を第１のブロックに埋め込むために符号化された平均値を設定することとを含む方法を提供する。
【００１５】
その他の態様、特徴、利点などは、本明細書に記載の本発明の好ましい実施形態に関する説明を添付の図面と併せて読むことによって、当業者には明らかになるであろう。
【発明を実施するための最良の形態】
【００１６】
本発明者らは画像ウェーブレット変換の諸機能を研究し、高周波サブバンド（ＨＬｎ、ＬＨｎ、またはＨＨｎ）の係数がゼロ平均およびラプラシアンに似た分散を有することを見出した。その一例が、Ｎ１Ａと呼ばれる、図２に示されたＮ１Ａ  ＪＰＥＧ２０００テスト画像のＨＬ１サブバンドである。図２で、Ｘ軸はＩＷＴ（整数ウェーブレット変換）係数値を表し、Ｙ軸はそれぞれの係数値を取る係数の数を表す。本発明者らはさらにこのサブバンドを、サイド長さＢの非オーバラップ矩形ブロックに分割し、各ブロックにおける係数値の平均を計算した。
【００１７】
【数１】
2007522693.tif 000003
上式で、上付きの添え字（ｔ）は、ｔ番目のブロックを表し、
【００１８】
【数２】
2007522693.tif 000004
は、ｔ番目のブロックのＩＷＴ係数を表す。図３はこれらの平均値の分布の一例を示す。図３において、Ｘ軸はＮ１Ａ  ＪＰＥＧ２０００テスト画像のＨＬ１サブバンドにおける１０×１０の非オーバラップ・ブロック（すなわち、サイド長さＢ＝１０）の平均値を表し、Ｙ軸はそれぞれの平均値を有するブロックの数を表す。図３に示された平均値の分散が係数それ自体の分散よりもはるかに小さいことが観測される。
【００１９】
本発明者らが提案するセミフラジャイル無損失データ隠蔽アルゴリズムの１態様はこの特性を利用する。好ましくは、１ビットのデータが非オーバラップ・ブロックの各々に埋め込まれる。最初に、すべてのブロックをスキャンし、ｍｍａｘで示される係数の絶対平均値の最大を求める。
【００２０】
【数３】
2007522693.tif 000005
ここでも「ｔ」はブロックの指標を示し、Ｍａｘは最大値を取る操作を示す。閾値Ｔはｍｍａｘ以上の最小の整数値に設定される。その結果、すべてのブロックの「平均値」の絶対値はＴ以下となる。次に、各ブロックの平均値を設定（または操作）することによって各非オーバラップ・ブロックに１ビットを埋め込むことができる。論理１のビット値がブロックに埋め込まれた場合は、そのブロックの平均値はシフト量Ｓだけ０から離れる方向にシフトされる。シフト量Ｓは好ましくはＴ以上である。論理０のビット値が埋め込まれた場合は、そのブロックおよびそのブロックのＩＷＴ係数の平均値は好ましくは不変である。したがって、Ｔより大きい絶対値を有するブロックの係数の平均値は、好ましくはブロック内に隠蔽された２進の「１」を表す。Ｔより小さい平均係数値は、好ましくは、埋め込まれた２進の「０」を表す。
【００２１】
好ましくは、すべてのブロックに対するシフト量Ｓは固定されているので、逆操作、すなわち論理１ビット値（「１」ビット）が埋め込まれたブロックのＩＷＴ係数からＳを減算することによって元の係数を復元することができる。したがって、埋め込み操作は、好ましくは可逆である。その結果、ステゴ画像が歪められていない場合は、カバー・メディアはエラーなしに元の状態に戻すことができる。さらに、１つのブロック内のＩＷＴ係数の平均値を制御することによってデータを埋め込むので、ＪＰＥＧ／ＪＰＥＧ２０００圧縮などの意図しない実施によって生じた画像の小さな変更が平均値を大幅に変化させることもない。したがって、好ましくはステゴ画像がわずかに変更された場合でも、隠蔽データの正確な検出がやはり可能になる。この主張については、本出願中で後に検証する。
【００２２】
無損失の透かしを入れることが、無損失データ隠蔽工程を通じて元のカバー・メディア情報はすべてマークされた画像内に保存しなければならないという情報理論の原理に基づくものであることを指摘しておく必要がある。したがって、マークされた画像が損失の多い圧縮を受けた場合は、元の画像に関する情報が失われている可能性があるので、一般に元のカバー・メディアを復元することはできない。また一般に、データを埋め込むためにＨＬ１またはＬＨ１高周波サブバンドが選択されることにも留意されたい。すなわち、より高いレベルの高周波サブバンド、ＨＬｎまたはＬＨｎ（ｎ＞１）のＩＷＴ係数のブロックの平均値分布もまた上述の理論に従って動作するが、本発明者らは一般にこれら高レベルＩＷＴ係数にデータを埋め込むことはしない。なぜならば、高レベル・サブバンドに対する変更は、画像品質を大幅に低下させる可能性があるからである。
【００２３】
提案する無損失データ隠蔽アルゴリズム
最初に、オーバフロー／アンダーフローをどのように防止するかについての問題に取り組む。次いで、提案のデータ埋め込み手順を提示する。
【００２４】
オーバフロー／アンダーフローの原因
取り扱うすべての画像がＪＰＥＧ２０００形式である場合には、前のセクションで提案した方法で十分であろう。ここで、ＪＰＥＧ２０００形式の画像があるものと想定する。“シー．クリストプロス（C. Christopoulos）、エイ．スコドラス（A. Skodras）およびティ．エブラヒミ（T. Ebrahimi）、「ＪＰＥＧ２０００静止画像符号化システム：概説（The JPEG2000 still image coding system: an overview）」、IEEE Trans. On Consumer Electronics、第４６巻、第４号、１１０３〜１１２７ページ、２０００年１１月（本明細書では「クリストポロス」と呼ぶ）”に開示されているように、第２層の復号化に続く第１層の復号化によって、すべてのＩＷＴ係数を画像ファイルから導くことができる。この文献は本願明細書に組み込まれる。
【００２５】
次に、隠蔽データを高周波ＩＷＴ係数に埋め込むことができる。変更された係数を再度符号化して、マークされたＪＰＥＧ２０００ファイルを形成することができる。このファイルは、そのままで送信や印刷などの用途に使用することができる。受信端では、マークされたＪＰＥＧ２０００画像ファイルから隠蔽データを抽出することができる。マークされた画像が変更されていない場合は、好ましくは、データ埋め込みに使用されたシフト量の値がデータ抽出手順において知られていると想定すると、すべての修正された係数は元の値に戻すことができる。したがって、好ましくは元の画像と同一の画像の復元されたバージョンが得られる。なぜならば、好ましくはＪＰＥＧ２０００符号化によってウェーブレット係数が切り捨てられないことが保証されるからである。http://www.jpeg.org/public/fcd15444-1.pdfから入手可能な、JPEG 2000 Part I Final Committee Draft Version 1.0. ISO/IEC JTC 1/SC 29/WG 1 N1646Rを参照されたい。この文献の開示の全体は本願明細書に組み込まれる。したがって、好ましくはオーバフローおよび／またはアンダーフローは発生しない。
【００２６】
しかし、ステゴ画像はＪＰＥＧ２０００形式以外の形式に変換されることもある。ファイル形式の変更は許容されるものと考えるべきであり、元のカバー・メディアはファイル形式変更後も保存される必要がある。それにもかかわらず、本発明者らは、ＪＰＥＧ２０００形式から他の形式、例えばビットマップ形式に形式変更された後で、復元されたメディアが元のメディアと異なっている場合があることに気付いた。その理由は、空間領域における画素グレースケール値が、好ましくは固定長のビット列（通常は８ビット、１６ビットのこともある）で表されるからである。カラー画像では、画素の各基本カラー成分も８ビットで表されることが多い。埋め込み操作によってＩＷＴ係数が変更された後で、埋め込み操作の結果として、いくつかの画素のグレースケール値が許容されるグレースケール値範囲から外れる可能性がある。代表的なグレースケール範囲は、８ビット・グレースケール画像については０〜２５５である。
【００２７】
この現象はオーバフロー／アンダーフローと呼ばれ、以下のように説明される。本発明のアルゴリズムでは、データ隠蔽操作においていくつかのＩＷＴ係数が修正される。また、各ブロックを空間領域に変換する際の係数値のこの変更は、関連する変更を空間領域における画素グレースケール値に生じさせる。さらに、画素グレースケール値のこの変更は、０〜２５５などの代表的なグレースケール値の制限範囲を越えることがあり、アンダーフロー状態および／またはオーバフロー状態が生じることになる。結果として、一般に切捨てが行われる。２５５を越える（オーバフロー）画素グレースケール値は、好ましくは２５５に設定され、ゼロより小さい（アンダーフロー）画素グレースケール値は好ましくは０に設定される。情報理論の観点からは、切捨てによって情報損失が生じる。したがって、後でデータ抽出工程において、完全に正確には元の画像を復元することができなくなる。
【００２８】
オーバフロー／アンダーフローの防止
一般に、空間領域におけるマークされた画像の画素グレースケール値が許容範囲内にとどまる限りは、上で論じたオーバフロー／アンダーフロー問題は生じない。以下では、画素グレースケール値が８ビットで表され、許容されるグレースケール値範囲が［０，２５５］であると想定する。ある種の画像に対して許容される範囲が［０，２５５］以外の場合にも、提案された原理はやはり有効であり、対応する解を容易に導くことができる。
【００２９】
この方法の好ましい実施形態は、ブロック・ベースである。詳細には、この方法は、好ましくは選択された高周波サブバンドを非オーバラップのブロックに分割し、データ隠蔽は、好ましくはブロック単位で実施される。考慮中のブロックに隣接する各ブロックのＩＷＴ係数値の修正は、このブロックに対応する画素のグレースケール値と干渉する可能性がある。このことは、後ほど本明細書中で明らかにする。したがって、隣接するＩＷＴ係数ブロックからの干渉を除去することができる場合には、オーバフロー／アンダーフローを回避することがはるかに容易になる。したがって、好ましくは図４のマスクが使用される。
【００３０】
マスクの境界上にある外部要素は「０」でマークされ、内部要素は「１」でマークされる。マスクにおいて、「０」は変更されないＩＷＴ係数を識別し、「１」はデータ埋め込み工程の間に変更される係数を識別する。言い換えると、ビット埋め込み段階において、ＩＷＴ係数ブロックの平均値を変更するためには、好ましくは上記のマスクでその位置が「１」のビットに関連する係数だけを変更し、好ましくはブロックの外部境界の係数を不変に保つ。クリストプロスのＩＷＴ理論を用いると、選択されたブロックのＩＷＴ係数が図４に示されたマスクを用いて変更されたとき、隣接するブロック中の画素のグレースケール値が影響を受けないことが容易に示される。すなわち、隣接ブロック間の干渉は、好ましくはこのアプローチを使用することで除去される。
【００３１】
隣接するブロック間の干渉が除去されると、アンダーフロー／オーバフローの防止に関する議論は単一のブロックだけに注目することができる。基本的な考えについて以下で説明する。ＩＷＴ係数ブロックＢｗ、およびそれに対応する空間領域中のブロックＢｓについて考える。ここで、「対応する」という用語は、そのグレースケール値がＩＷＴ係数ブロックに関連している画素のグループを意味する。この対応関係は、既存のＩＷＴ理論に従って容易に決定することができる。最大画素グレースケール値変更の絶対値がＳｍａｘであると想定する。Ｂｓにおいては、ａ）（２５５−Ｓｍａｘ）を越えるグレースケール値を有する画素が存在し、かつｂ）ビット埋め込み工程の結果としてそのグレースケール値を増加させる必要がある場合に、オーバフローが生ずる可能性がある。Ｓｍａｘよりも小さいグレースケール値を有する画素が存在し、かつビット埋め込み工程の結果として空間領域画素グレースケール値を減少させる必要があるときには、アンダーフローが生じる可能性がある。
【００３２】
オーバフローおよびアンダーフローを回避するためには、上記２つのシナリオを発生させてはならない。本発明者らは［０，Ｓｍａｘ］を０ゾーンと呼び、（２５５−Ｓｍａｘ，２５５）を２５５ゾーンと呼ぶ。空間領域では、これら２つのゾーンに関連したブロックの画素値の配置に基づいて、各ブロックを以下で論ずる４つのカテゴリのうちの１つに分類することができる。理想的な場合、すなわちタイプＡブロックの場合には、図５Ａに示したように上記のゾーン中に画素は存在しない。このような理想的な場合には、オーバフロー／アンダーフロー問題に関して心配する必要はない。
【００３３】
Ｂｓにおいて、図５Ｂの実線によって示されるように、０ゾーンに画素は存在するが２５５ゾーンに画素が存在しない場合、すなわちタイプＢブロックの場合には、画素グレースケール値が正方向だけに変化すれば、アンダーフロー問題を回避することができる。データ隠蔽後に結果として得られるヒストグラムは、図５Ｂの破線によって示される。図５Ｂでは、２５５より大きい、またはゼロより小さいグレースケール値を持つ画素は存在せず、したがってオーバフロー／アンダーフローが生じないことが示される。
【００３４】
好ましくは、タイプＢブロックに関して、ブロックの平均係数値が−Ｔより小さい（すなわち、負の値が大きい）場合には、ブロックに埋め込まれる予定のビットの値にかかわらず、シフト値はそのブロックには適用されない。
【００３５】
図５Ｃは、図５Ｂと反対の場合を示す。このブロックの画素が０ゾーンに存在しない場合、すなわちタイプＣブロックの場合は、このグループの画素に対するすべての変更が減少方向である場合には安全である。最悪の場合は図５Ｄによって示される。この場合、０ゾーンの画素と２５５ゾーンの画素のどちらもが単一のブロック、すなわちタイプＤブロックの中に存在する。この場合、アンダーフローまたはオーバフローを避けるために、好ましくは平均係数値はシフトされない。したがって、データの抽出において誤りが生ずる恐れがあり、何らかの追加の措置を取る必要がある。エラー符号訂正は、上記の理由でブロック中に埋め込まれた任意のエラーに対処する１つの方法である。データ抽出におけるエラーに対処するための手段については、本明細書中で後述する。
【００３６】
オーバフロー／アンダーフローの防止
ここまで、ＩＷＴ係数にビットを埋め込むための好ましいシステムおよび方法について提案し、上述のように、ビットの埋め込みによるグレースケール値への影響を考慮することによって、オーバフロー／アンダーフローを避ける方法について論じてきた。好ましい実施形態では、ＨＬ１またはＬＨ１サブバンドのあるブロックに、あるビットを埋め込む方法を見つけることができ、影響を受ける空間領域画素のグレースケール値がすべて切捨てを行う必要がない方向だけに移動する場合には、オーバフロー／アンダーフロー問題を回避することができる。以下で、この問題についてさらに検討する。
【００３７】
ＪＰＥＧ２０００標準では、可逆な画像符号化のためのデフォルト・フィルタとして一般に５／３ウェーブレット・フィルタ・バンクが使用される。５／３フィルタ・バンクは、ル  ガル（Le Gall）およびエイ．タバタバイ（A. Tabatabai）、「対称性ショート・カーネル・フィルタおよび演算符号化技術を用いたデジタル画像のサブバンド符号化（Sub-band coding of digital images using symmetric short kernel filters and arithmetic coding techniques）」、Proc. of IEEE International Conference on Acoustics、音声およびシグナル処理（Speech and Signal Processing）、ニューヨーク、７６１〜７６５ページ、１９８８年（本明細書では「ガル」と呼ぶ）の中でル  ガルらによって最初に提案されたものであり、この文献の開示の全体は本願明細書に組み込まれる。５／３ウェーブレット・フィルタ・バンクの係数は図６で与えられる。
【００３８】
本発明者らの目的は、画像の整数ウェーブレット変換（ＩＷＴ）の高周波サブバンドにデータを埋め込むことである。この場合、ウェーブレット係数を変更することによる空間領域の対応部分への影響を調査する必要がある。
【００３９】
図６から、合成フィルタはＺ変換を用いて次のように表すことができる。
ローパス・フィルタ：
【００４０】
【数４】
2007522693.tif 000006
ハイパス・フィルタ：
【００４１】
【数５】
2007522693.tif 000007
２次元画像については次式となる。
【００４２】
ｘ軸のローパス・フィルタ：
【００４３】
【数６】
2007522693.tif 000008
ｘ軸のハイパス・フィルタ：
【００４４】
【数７】
2007522693.tif 000009
ｙ軸のローパス・フィルタ：
【００４５】
【数８】
2007522693.tif 000010
ｙ軸のハイパス・フィルタ：
【００４６】
【数９】
2007522693.tif 000011
ＨＬサブバンドについては、合成フィルタは最初に行（ｘ方向）にハイパスを適用し、次いで列（ｙ方向）にローパスを適用する。その結果は次式となる。
【００４７】
【数１０】
2007522693.tif 000012
ＬＨサブバンドについては、合成フィルタは最初に行（ｘ方向）にローパス・フィルタリングを適用し、次いで列（ｙ方向）にハイパス・フィルタリングを適用する。その結果は次式となる。
【００４８】
【数１１】
2007522693.tif 000013
ＬＬサブバンドについては、どちらの方向にもローパス・フィルタを適用する。その結果は次式となる。
【００４９】
【数１２】
2007522693.tif 000014
式（９）から、ＨＬ１サブバンドの（ｉ，ｊ）位置に存在するＩＷＴ係数に対して行われる変更に対する空間領域における単位ステップ応答は、図７の行列ＧＨＬで表すことができる。詳細には、（２ｉ−１，２ｊ）に中心がある、サイズ３×５の空間領域における画素グレースケール値の配列（図１０参照）は、ＨＬ１サブバンドのＩＷＴ係数（ｉ，ｊ）が１だけ増加した場合に、この行列（図７）の各要素によって指定された量だけ変化することになる。
【００５０】
ＬＨ１およびＬＬ１サブバンドの係数に対する対応する単位ステップ応答は、それぞれ図８および図９に示されたＧＬＨおよびＧＬＬによって示されることが分かる。これらは、ＬＨ１またはＬＬ１サブバンドのＩＷＴ係数（ｉ，ｊ）が１だけ増加した場合の空間領域におけるグレースケール値の変化の大きさを示す。中心はＧＬＨおよびＧＬＬに対して、それぞれ（２ｉ，２ｊ−１）および（２ｉ−１，２ｊ−１）に位置する。
【００５１】
ＨＬ１がキャリア・サブバンドだと想定する。図７は、ウェーブレット係数変更の影響を受ける各画素のグレースケール値が、増加および減少のどちらの方向にも変化することを示す。このことは同様に、キャリア・サブバンドとしてＬＨ１が使用された場合にも成り立つ。図９の行列によれば、画素グレースケール値は１方向にだけ移動する。ここで、オーバフロー／アンダーフローに対処するための１つの好ましいアプローチは、ＬＬサブバンドの係数を操作して、結果として得られる空間領域画素グレースケール値の変化を１方向だけに生じさせることである。
【００５２】
最初に、
【００５３】
【数１３】
2007522693.tif 000015
によって示される、位置（ｉ，ｊ）のＨＬ１係数への単位入力を考える。空間領域での出力応答を
【００５４】
【数１４】
2007522693.tif 000016
で示す。上式で、ｋは振幅を表し、
【００５５】
【数１５】
2007522693.tif 000017
は、影響を受ける空間領域内の点の座標を示す。上記の単位入力、および空間領域内でのその応答は次式で表される。
【００５６】
【数１６】
2007522693.tif 000018
上式で、
【００５７】
【数１７】
2007522693.tif 000019
は、
【００５８】
【数１８】
2007522693.tif 000020
が、（ｉ，ｊ）位置のＨＬ１係数への単位入力によって生じた応答であることを意味し、
【００５９】
【数１９】
2007522693.tif 000021
は、この応答が空間領域内の（２ｉ−２，２ｊ−２）に位置するものであることを意味する。
【００６０】
単位入力が、（ｉ，ｊ）位置のＬＬ係数に適用された場合、対応する応答は次式となる。
【００６１】
【数２０】
2007522693.tif 000022
次式が成り立つことが証明できる。
【００６２】
【数２１】
2007522693.tif 000023
（ｉ，ｊ）位置のＨＬ１係数をＳだけ変更し、（ｉ，ｊ）および（ｉ，ｊ＋１）位置のＬＬ１係数をＳ／４だけ変更した場合、空間領域内の画素値変化はＳと同じ符号を持つことになる。
【００６３】
同様に、ＬＨサブバンドの係数については、次式が得られる。
【００６４】
【数２２】
2007522693.tif 000024
上式は、以下で説明する本発明の方法についての基本を成すものである。次に、ＬＬ係数の単位応答について調べる。（ｉ，ｊ）位置でのＬＬ１係数については、単位ステップ応答の中心は空間領域中の（２ｉ−１，２ｊ−１）となり、（ｉ，ｊ＋１）位置のＬＬ１係数については、単位ステップ応答の中心は（２ｉ−１，２ｊ＋１）となることが推論できる。図１０は、ＩＷＴ係数と結果として得られた空間領域内の単位ステップ応答との関係を示す。実線の矢印および実線のボックスは、ＨＬ１サブバンド内の係数（ｉ，ｊ）および空間領域内で影響を受ける画素を示すものである。点線の矢印および点線のボックスは、ＬＬ１係数（ｉ，ｊ）および空間領域内でその係数の影響を受ける画素を示すものである。また、破線の矢印および破線のボックスは、ＬＬ１係数（ｉ，ｊ＋１）および空間領域内でその係数の影響を受ける画素を示すものである。
【００６５】
ＬＬ１係数（ｉ，ｊ）および（ｉ，ｊ＋１）の単位ステップ応答に対応する、結合された２次元のアレイは３×５のサイズを有し、ＩＷＴのＨＬ１係数（ｉ，ｊ）の単位ステップ応答に対応する画素とまったく同一の画素のグループをカバーする。ＨＬ１サブバンドの（ｉ，ｊ）における係数を示すのにＣＨＬ（ｉ，ｊ）を使用し、ＬＬ１サブバンドの（ｉ，ｊ）における係数を示すためにＣＬＬ（ｉ，ｊ）を使用する。次に、ＣＨＬ（ｉ，ｊ）の単位ステップ応答、ＣＬＬ（ｉ，ｊ）単位ステップ応答の１／４、およびＣＬＬ（ｉ，ｊ＋１）単位ステップ応答の１／４の組み合わされた影響が図１１の行列によって表せることは容易に検証できる。
【００６６】
図１１の行列は、空間領域におけるすべての変化が、好ましくは同じ符号を有すること示している。言い換えれば、ＨＬ１サブバンドにデータを埋め込むことに決定した場合、（ｉ，ｊ）でＨＬ１係数をＳだけ変更し、（ｉ，ｊ）と（ｉ，ｊ＋１）の両方でＬＬ１係数をＳ／４だけ変更した場合に、空間領域における画素グレースケール値の変化はＳと同じ符号を有することになる。埋め込みの後で、空間領域における最大画素グレースケール値変化がやはりＳであることに留意されたい。同様に、ＬＨ１がキャリア・サブバンドとして機能する場合には、同じ目的を、（ｉ，ｊ）でＬＨ１係数をＳだけ変化させ、（ｉ，ｊ）と（ｉ＋１，ｊ）の両方でＬＬ１係数をＳ／４だけ変化させることによって達成することができる。次のセクションでは、提案のデータ埋め込み手順を提示し、オーバフローおよびアンダーフローがどのように回避できるかを明らかにする。
【００６７】
データ埋め込み
好ましい実施形態では、データはサブバンドＨＬ１またはサブバンドＬＨ１に埋め込むことができる。ＨＬ１が使用されると想定して、本発明者らの方法を説明する。最初に、ＨＬ１サブバンドはＮ係数×Ｎ係数のサイズを有する非オーバラップのブロックに分割される。各ブロックにおいて、平均値は０であるかまたはほぼゼロである。同様に、平均の絶対値は閾値「Ｔ」よりも小さくなければならない。基本的な考えは、ビット「１」が埋め込まれる場合に、ブロックの絶対平均値が、好ましくはＴより大きい量だけ０から離れる方向にシフトされるということである。ここで、このブロックのすべての係数を変更するという訳ではない。その代わりに、図４のマスクを使用する。この例では、上記のマスクでその位置が「１」でマークされている係数だけを変更する。言い換えれば、ブロックの外側の境界は不変に保たれる。こうすることによって、あるブロックにおいて係数を変更することの効果が、隣接ブロックにおいて係数を変更することの効果と干渉しないようになる。
【００６８】
ＨＬ１サブバンドの（ｉ，ｊ）での係数が量Ｓ（Ｓは正でも負でもよい）だけ変更された場合には、ＬＬ１サブバンドの（ｉ，ｊ）および（ｉ，ｊ＋１）の２つの係数をそれぞれ量Ｓ／４だけ修正する。その結果は、対応する３×５アレイ中の影響を受けるすべての画素が増加する（Ｓ＞０の場合）か、または減少する（Ｓ＜０の場合）ことになる。あるいは、埋め込みキャリアとしてＬＨ１サブバンドが使用され、ＬＨ１サブバンドにおける（ｉ，ｊ）の係数が変更される場合は、ＬＬ１サブバンドの（ｉ，ｊ）および（ｉ＋１，ｊ）の２つの対応する係数をＳ／４だけ変更する必要がある。同様に、空間領域中の影響を受ける画素のすべてが増加（Ｓ＞０の場合）するか、または減少（Ｓ＜０の場合）することになる。本明細書中で前述したように、本発明者らのアルゴリズムにおいては、あるブロックの平均値変更は、好ましくは図４で「１」のマスク値を有するすべての係数を同じ量だけ変更することによって達成される。値をＳだけ変更する必要があるＨＬ１またはＬＨ１サブバンドの各係数に対してその値をＳだけ変更し、さらに前述のようにＬＬ１サブバンドの２つの対応する係数についても値をＳ／４だけ変更する。
【００６９】
埋め込み工程の前に、好ましくは埋め込まれる情報ビットに誤り訂正符号化およびカオス的混合が適用される。好ましい方法においてこの２つの技術を適用する目的は、この方法の頑強性を高めることである。符号化されたビット・ストリームおよびカバー画像は埋め込みシステムおよび方法に対する入力になる。
【００７０】
ＨＬ１またはＬＨ１サブバンドにおけるＩＷＴ係数のブロックＢｗにビットを埋め込むときは、最初に、埋め込みによって影響を受ける可能性がある対応する空間ブロックＢｓを見つけ出す。次いで、好ましくはＢｓの画素グレースケール値がチェックされ、好ましくはそのブロックが図５に示された４つのカテゴリに分類される。
Ａ：  このブロックには、（２５５−Ｓｍａｘ）より大きい、すなわち２５５ゾーンの画素グレースケール値、およびＳｍａｘより小さい、すなわち０ゾーンの画素グレースケール値は存在しない。
Ｂ：  このブロックには、Ｓｍａｘより小さいグレースケール値は存在するが、（２５５−Ｓｍａｘ）より大きい画素値は存在しない。
Ｃ：  このブロックには、（２５５−Ｓｍａｘ）より大きい画素グレースケール値は存在するが、Ｓｍａｘより小さい画素値は存在しない。
Ｄ：  このブロックには、Ｓｍａｘより小さい画素グレースケール値と（２５５−Ｓｍａｘ）より大きい画素グレースケール値の両方が存在する。
【００７１】
異なるカテゴリごとに異なる操作が適用され、このことが本発明のこの実施形態のキー・ポイントの１つである。これらの操作を以下に示す。
タイプＡブロックに対して
この場合は、オーバフローおよびアンダーフローは発生しない。以下で論ずるように、ブロック中のキャリア・サブバンド（ＨＬ１またはＬＨ１）係数の平均値を増加させること、あるいは平均値を減少させることができる。図５Ａに示されているように、平均値はゼロより大きくなること、またはゼロより小さくなることがある。詳細は、図１２に示される。「１」ビットが埋め込まれる場合は、平均値はシフト量Ｓだけ０から離れる方向にシフトされる。平均値が最初にａである場合は、好ましくはａ’にシフトされる。平均値が最初にｂである場合は、好ましくはｂ’にシフトされる。好ましい実施形態では、本明細書中で前述したようにＬＬサブバンドの対応する係数をＳ／４だけ修正する。ビット「０」に対しては、このブロックの係数の平均は、好ましくは不変である。
【００７２】
タイプＢブロックに対して
好ましい実施形態では、タイプＢのブロックには、図５Ｂに示されるように０ゾーンだけにいくつかの画素グレースケール値が存在する。このタイプのブロックではオーバフローは発生しない。ビット「０」の埋め込みについては、好ましくはブロックは不変に保たれる。ビット「１」の埋め込みについては、平均の絶対値は好ましくはＳだけシフトされる。図１３の−ａ−の場合のように元の平均値がゼロ以上の場合には、平均は−ａ’−にシフトすることができる。さらに、ＬＬサブバンドの対応する係数をＳ／４だけ修正する。結果として、空間領域中の画素値は変更がなされた後に増加するだけである。したがって、アンダーフローは避けられる。例えば−ｂ−のように、平均値が負の場合は、平均値の絶対値をＴより大きくするために、平均値をシフト量Ｓの分だけ減算することだけが可能である。しかし、この減算を実施したときは、アンダーフローが生じる可能性がある。したがって、平均値−ｂ−は、好ましくはシフトされない。ただし、ブロックを不変に保つことはビット「０」を埋め込むことに相当する。したがって、結果として生じたエラーを訂正するために、好ましくはエラー訂正符号化が使用される。
【００７３】
タイプＣブロックに対して
好ましい実施形態では、このタイプのブロックには、図５Ｃに示されているように２５５ゾーンにだけいくつかの画素グレースケール値が存在する。この場合は、あらゆることがタイプＢブロックと逆であることを除けば、前の場合と類似している。ビット「０」の埋め込みについては、操作は不要である。ビット「１」の埋め込みについては、ビット「１」の隠蔽のために負の平均係数値を持つブロックだけを使用することができる。ビット「１」を埋め込むことになっているが、そのブロックの平均値が正である場合には、そのビットを埋め込むことはできない。その代わりに、この状況では、好ましくはブロックは不変に保たれる。このことは、「０」ビットを埋め込むことと等価である。したがって、エラー・ビットが埋め込まれる可能性がある。好ましくは、エラー訂正符号化（ＥＣＣ）および／またはエラー訂正復号化（ＥＣＤ）を使用して、ビット・エラーが存在すればそれらを訂正する。図１４は、タイプＣのブロックの平均値に関する詳細を示す。
【００７４】
タイプＤブロックに対して
一般に、図５Ｄに示されているように、このタイプのブロックには、いくつかの０ゾーンの画素グレースケール値といくつかの２５５ゾーンのグレースケール値とが同時に存在する。一般に、どちらの方向に平均値をシフトしても、オーバフローまたはアンダーフローが生ずることになる。ここで、情報ビット「０」が埋め込まれる場合は、問題は生じない。しかし、「１」ビットを埋め込む必要がある場合には、エラーが生じることになる。ここでもまた、ＥＣＣおよび／またはＥＣＤを利用して、結果として生じたエラー・ビットを訂正する。
【００７５】
よく使用される画像については、ほとんどのブロックがタイプＡに属することに留意されたい。例えば、よく知られている「レナ」画像についてはすべてのブロックがタイプＡブロックである。この絵のマークされたバージョンを図２１及び図２２に示す。このタイプのブロックについては、エラーを訂正するためにＥＣＣを使用する必要がないこともある。
【００７６】
場合によっては、エラーが集中的に発生することもある。これは文字通り「バースト・エラー」と呼ばれている。すなわち、タイプＢ、Ｃ、Ｄのブロックが、所与の画像のある領域に集中していることがある。この状況では、ＥＣＣが効率的にエラーを訂正できないことがある。バースト・エラーに対処するために、好ましくはカオス的混合（または他の種類の並べ替え）が導入される。この混合により、バースト・エラーを均一に分散させることができる。図１５は、本発明の好ましい実施形態によるデータ埋め込み方法の構成図を示す。
【００７７】
好ましい実施形態では、ブロック・サイズＢ、閾値Ｔ、シフト量Ｓ、キャリアとして選択されたサブバンドの識別は副次的情報として保存され、それらの情報を後でデータ抽出やカバー・メディアの復元のために使用することができる。異なる視点から、この副次的情報をキーとして扱うことができる。言い換えると、好ましくはそのキーは個別のセキュアなチャネルを介して送信される。好ましくは、許可された人だけが提供された副次的情報を用いて隠蔽された情報を抽出することができる。代替方法としては、すべての画像に対して同一のＢ、Ｔ、Ｓおよびサブバンドを使用することである。その結果、好ましくは副次的情報が不要になる。この代替方法の欠点は、このような方法で処理される画像にとってパラメータが最適でない場合があることである。
【００７８】
データ抽出および元の画像の復元
受信側では、ステゴ画像が入力になる。データ抽出および元のカバー画像の復元が実施される。
【００７９】
隠蔽データの抽出
好ましい実施形態では、隠蔽データ抽出にはステゴ画像および／または副次的情報が必要になる。好ましくは、ステゴ画像の高周波整数ウェーブレット係数が最初に取得される。次いで、好ましくはキャリア・サブバンドがサイズＢの非オーバラップ・ブロックに分割される。好ましくは、各ブロックから１ビットのデータが抽出される。
【００８０】
平均値と閾値Ｔを比較することによってビット「０」が抽出されるのか、またはビット「１」が抽出されるのかを判定することができる。テスト画像がＪＰＥＧ２０００形式の場合は、ＩＷＴ係数がウェーブレット変換を実施することなくＪＰＥＧ２０００ビット・ストリームから直接取得できることに留意されたい。好ましくは、余分な変換を必要としないのでデータ抽出が効率的になる。
【００８１】
隠蔽データ抽出は、好ましくは埋め込みより容易である。ＩＷＴ領域において、データがＨＬ１サブバンドに埋め込まれている場合には、埋め込み段階と同じ方法でそのサブバンドをブロックに分割する。次いで、好ましくは各ブロックの係数の平均値が計算される。
【００８２】
次いでこの方法は、好ましくは、各ブロックごとにそのブロックの１ビットを抽出し、そのブロックの平均係数値をそのブロックの元の値に戻す。詳細には、好ましくはこの方法は、埋め込み後でかつ抽出前の平均係数値の絶対値が閾値Ｔ以上の場合に論理１ビットを抽出する。好ましくはこの方法は、そのブロックの埋め込み後でかつ抽出前の平均係数値が閾値Ｔより小さい場合に論理０ビットを抽出する。したがって、データ抽出段階において、好ましくはこの方法は、埋め込み段階の間に実施されたシフト動作を逆方向に実施することによって、そのブロックの平均係数値の元の値を復元する。詳細には、データビットが抽出された後で、好ましくはこの方法は、そのブロックの平均係数値の絶対値を、その平均係数値の符号を維持しながら、埋め込み工程中に使用されたシフト量Ｓの大きさ分だけ減少させる。
【００８３】
好ましくは、「１」ビット・ブロックについては、ＨＬ１またはＬＬ１サブバンドにおける係数が０の方向にシフトされ、埋め込み前の値に戻る。結果として、元のＩＷＴ係数が復元される。隠蔽データの抽出および元の画像の復元のために、好ましくは空間領域に戻る必要がないことに留意されたい。この特徴はＪＰＥＧ２０００画像にとって非常に好都合なものである。
【００８４】
前述において、各ブロックの初期平均値がゼロまたはゼロに近い、あるいは少なくとも閾値Ｔよりも小さいものと想定した。式（２）で定義したように、Ｔはｍｍａｘより大きいので、後者は保証される。
【００８５】
カバー・メディアの復元
すべての隠蔽データが抽出された後で、元のカバー・メディアを復元することができる。ここで、２つの可能性が存在する。最初の可能性は、ステゴ画像がいかなる変更も受けていない場合である。もう１つの可能性は、ステゴ画像が何らかの変更を受けている場合である。最初の可能性に関しては、好ましくは元の画像を復元することができる。図１６は、本発明の１つまたは複数の好ましい実施形態による、元の画像を復元するための方法を示すフロー図である。復元される画像が変更されている場合には、元のカバー画像が完全には復元できない場合があることに留意されたい。
【００８６】
実験結果と性能解析
一般に埋め込まれるビット・ストリームは、Matlab（商標）のrandint()関数（関数randintは０または１のランダム・スカラーを等確率で生成する）を使用してランダムに生成される。本発明者らは、本発明のアルゴリズムをＵＳＣ  ＳＩＰＩ画像データベース、CorelDraw（商標）画像データベース、ＪＰＥＧ２０００テスト画像における画像など様々な画像に適用した。本発明者らが提案したアルゴリズムはテスト画像のすべてに対してうまく機能した。図１７はマークされた医用画像、図１８はマークされたＪＰＥＧ２０００テスト画像（Ｎ１Ａ）であり、どちらも本発明者らが提案したアルゴリズムを用いて生成されたものである。したがって、同じサイズの画像には同じ量のデータが埋め込まれる。本明細書で開示したシステムおよび方法については、ごま塩状雑音の問題が生じないこと、ならびに本発明者らが提案したアルゴリズムによって生成されるステゴ画像の視覚品質が従来技術によるものよりはるかに高いことに留意されたい。詳細には、マークされていない元のバージョンに対するマークされた医用画像（図１７）のＰＳＮＲは、従来技術での９．２８ｄＢの代わりに３８．５３ｄＢとなる。また、Ｎ１Ａ  ＪＰＥＧ２０００テスト画像については、ＰＳＮＲは、従来技術での１８．０１ｄＢの代わりに（本明細書で開示した好ましいシステムおよび方法を用いると）４２．６７ｄＢとなる。
【００８７】
提案されたアルゴリズムの性能解析については、画像処理分野で最も一般的に使用される画像であり、５１２×５１２サイズの８ビット・グレースケール画像であるレナ画像に関するテスト結果を詳細に提示する。
【００８８】
データ埋め込み容量
本発明者らのアルゴリズムにおいて、データ埋め込み容量は、好ましくはブロック・サイズＢによって決定される。Ｂが小さくなるほど、より多くのブロックが存在することになる。したがって、より多くのビットを埋め込むことができる。図１９の表はブロック・サイズと容量の間の関係を示したものである。エラー訂正符号化は、好ましくは本発明のアルゴリズムの頑強性を高めるために使用される。ここで使用されたＥＣＣ符号化方式はＢＣＨ符号［１３］である。しかし、他のエラー訂正符号化／復号化方法を使用することもできる。一般に、エラー訂正機能が強化されるほど、埋め込み容量は小さくなる。この実験的研究ではＢＣＨ（１５，１１）符号が使用された。したがって、容量は次式で計算される。
【００８９】
【数２３】
2007522693.tif 000025
上式でＭ、Ｎは画像のサイズであり、Ｂはブロック・サイズである。図１９において、「ＥＣＣ有りの容量」は上式を用いて決定された容量を示し、「ピュア・ペイロード」と呼ばれることもある。一方、「ＥＣＣ無しの容量」はＥＣＣを使用しなかった場合に得られる容量を示す。
【００９０】
マーク画像の視覚品質
元の画像に関連するステゴ画像の視覚品質は、ピーク信号対雑音比（ＰＳＮＲ）のパラメータを使用して評価することができる。
【００９１】
図１９から、より小さなブロック・サイズを使用することにより、より大きなデータ保存容量が提供できることが分かる。しかし、先に式（２）で定義した、ブロックにおけるＩＷＴ係数の絶対平均値の最大値ｍｍａｘは大きくなる。したがって、一般にブロック・サイズをより小さくすることにより、シフト量Ｓをより大きくすることが必要になり、それによってマークされた画像の質を低下させてＰＳＮＲを減少させる。図２０のデータはこの観測を支持する傾向を示す。実際には、「最小シフト値」はｍｍａｘより大きい最小の整数として定義される。
【００９２】
図２１および図２２は、異なるブロック・サイズに対する最小シフト値を用いてマークされた「レナ」画像を示す。図２１のマークされた画像の視覚品質の方が図２２のものより劣っていることが分かる。図２２（ｂ）の画像のＰＳＮＲは図２２の画像のＰＳＮＲよりも９ｄＢ大きい。
【００９３】
同じブロック・サイズを用いて異なるシフト値を適用することもできる。後で、シフト値を大きくするほどステゴ画像はより頑強になることが分かる。図２３は、様々なブロック・サイズ、様々なシフト値に対するステゴ画像のＰＳＮＲを示すものである。シフト値の値が大きくなるほどＰＳＮＲ値は低下する、すなわち画像品質が低下することが分かる。
【００９４】
隠蔽データの頑強性
大部分の無損失透かしアルゴリズムと異なり、提案したＩＷＴベースの無損失透かしアルゴリズムは偶発的な変化に対して頑強である。
【００９５】
最初に、このアルゴリズムはＪＰＥＧ２０００圧縮に対して頑強である。実験的な研究では、マークされた画像は圧縮比の増大とともに損失が増えるＪＰＥＧ２０００圧縮されている。ＪＰＥＧ２０００圧縮に対する頑強性はデータ生存率によって評価される。すなわち、圧縮後の結果として得られたデータ率がデータ生存データ率以上のときは、隠蔽データはエラーなしに確実に抽出される。言い換えると、データ生存率が低いほど、ステゴ画像はより頑強になる。
【００９６】
図２４は、様々なブロック・サイズの下での、ステゴ画像のＰＳＮＲとデータ生存率の間の関係を示す。一般に、所与のブロック・サイズＢに対して、ＰＳＮＲが低いほどデータ生存率が低くなることが観測される。所与のデータ生存率に対して、より大きなブロック・サイズを選択するほど、より高いＰＳＮＲを得ることができる。その結果、より良い画像品質が得られるが、データ埋め込み容量は低下する。画像視覚品質、隠蔽データの頑強性、および埋め込み容量はすべて相互に関係しており、その一部が相互に競合することは明らかである。これらの特性のすべてに対して、同時に最適性能を達成することはできない。一般に、各個別の用途ごとに、これらの特性の最適組合せを達成することは可能である。
【００９７】
圧縮に加えて、提案した透かし方式は、メディアン・フィルタの使用に対しても同様に頑強である。３×３サイズのメディアン・フィルタをステゴ画像に適用することができる。次いで、隠蔽データの抽出は、好ましくはフィルタされたステゴ画像に関して実施される。図２５は、データ抽出手順の間に復号されたエラー・ビットの数を測定したテスト結果を示す。より大きなブロック・サイズ、およびより大きなシフト値を用いることで、マークされた画像がメディアン・フィルタの使用に対してより頑強になることは明白である。
【００９８】
付加したガウス雑音は、通信システムでしばしば生じる種類の雑音である。本発明者らの実験では、平均がゼロで分散が０．００１のガウス雑音をマーク画像に追加した。隠蔽データ抽出におけるエラー・ビットをカウントし、図２６に結果を示した。前と同様に、一般にブロック・サイズが大きくなるほどシフト値が大きくなり、ステゴ画像はより頑強になる。
【００９９】
本明細書では、新しいセミフラジャイル無損失データ隠蔽方式を開示した。データは整数ウェーブレット領域に埋め込まれる。本明細書で開示した好ましい方法は、好ましくはＪＰＥＧ２０００標準にシームレスに統合される。オーバフローおよびアンダーフローの問題は本方式において解決される。マーク画像が変更されていない場合は、隠蔽データ抽出の後で元のカバー・メディアを復元することができる。隠蔽されたデータは、例えば損失の多い圧縮など悪意のない損傷に対して、ある程度頑強である。性能解析が実施され、提案のアルゴリズムの利点が示される。マーク画像の視覚品質は優れたものである。ステゴ画像中のごま塩状雑音および他のアーチファクトはうまく回避される。この方法は、コンテンツベースの画像認証や他のいくつかの用途に適用することができる。
【０１００】
以下の文献についての全体の開示はすべて本願明細書に組み込まれる。
［１］ディ．ゾウ（D. Zou）、シー．ダブリュ．ウー（C. W. Wu）、ジー．シュエン（G. Xuan）およびワイ．キュー．シー（Y. Q. Shi）、「無損失データ隠蔽によるコンテンツ・ベースの画像認証システム（A content-based image authentication system with lossless data hiding）」、Proc. of IEEE International Conference on Multimedia and Expo、第２巻、６〜９ページ、ボルチモア（Ｂａｌｔｉｍｏｒｅ）、メリーランド（Ｍａｒｙｌａｎｄ）、２００３年７月。
【０１０１】
［２］シー．ダブリュ．ホンジンガー（C. W. Honsinger）、ピー．ジョーンズ（P. Jones）、エム．ラバニ（M. Rabbani）、およびジェイ．シー．ストッフェル（J. C. Stoffel）、「埋め込まれたデータを含むオリジナル画像の無損失復元（Lossless recovery of an original image containing embedded Data）」、米国特許第６２７８７９１号、２００１年。
【０１０２】
［３］ジェイ．フリードリッヒ（J. Fridrich）エム．ゴルジャン（M. Goljan）およびアール．デュ（R. Du）、「可逆認証（Invertible authentication）」、Proc. SPIE、マルチ・メディア・コンテンツのセキュリティおよび透かし技術（Security and Watermarking of Multimedia Contents）、第４３１４巻、１９７〜２０８ページ、カリフォルニア州サンノゼ、２００１年１月。
【０１０３】
［４］エム．ゴルジャン（M. Goljan）、ジェイ．フリードリッヒ（J. Fridrich）、およびアール．デュ（R. Du）、「無歪みデータ埋め込み（Distortion-free data embedding）」、Proc. of 4th Information Hiding Workshop、第２１３７巻、２７〜４１ページ、ペンシルベニア州ピッツバーグ、２００１年４月。
【０１０４】
［５］ジー．シュエン（G. Xuan）、ジェイ．チェン（J. Chen）、ジェイ．ヂュー（J. Zhu）、ワイ．キュー．シー（Y. Q. Shi）、ズィ．ニー（Z. Ni）およびダブリュ．スー（W. Su）、「整数ウェーブレット変換に基づく無歪みデータ隠蔽（Distortionless data hiding based on integer wavelet transform）」、IEEE Electronics Letters、第３８巻、第２５号、１６４６〜１６４８ページ、２００２年１２月。
【０１０５】
［６］ズィ．ニー（Z. Ni）、ワイ．キュー．シー（Y. Q. Shi）、エヌ．アンサリ（N. Ansari）、エス．ウェイ（S. Wei）、「可逆データ隠蔽（Reversible data hiding）」、Proc． of the International Symposium on Circuits and Systems 2003、第２巻、２５〜２８ページ、タイ  バンコク、２００３年５月。
【０１０６】
［７］シー．デ  ブリースコーワー（C. De Vleeschouwer）、ジェイ．エフ．ドレーグル（J. F. Delaigle）およびビー．マック（B. Macq）、「メディア資産管理のための無損失透かしにおける全単射変換の循環分析（Circular interpretation of bijective transformations in lossless watermarking for media asset management）」、IEEE Transactions on Multimedia、第５巻、９７〜１０５ページ、２００３年３月。
【０１０７】
［８］エイ．スコドラス（A. Skodras）、シー．クリストプロス（C. Christopoulos）およびティ．エブラヒミ（T. Ebrahimi）、「ＪＰＥＧ２０００静止画像圧縮規格（The JPEG2000 still image compression standard）」、IEEE Signal Processing Magazine、第１８巻、第５号、３６〜５８ページ、２００１年９月。
【０１０８】
［９］シー．クリストプロス（C. Christopoulos）、エイ．スコドラス（A. Skodras）およびティ．エブラヒミ（T. Ebrahimi）、「ＪＰＥＧ２０００静止画像符号化システム：概説（The JPEG2000 still image coding system: an overview）」、IEEE Trans. On Consumer Electronics、第４６巻、第４号、１１０３〜１１２７ページ、２０００年１１月。
【０１０９】
［１０］エル．ガル（L. Gall）およびエイ．タバタバイ（A. Tabatabai）、「対称性ショート・カーネル・フィルタおよび演算符号化技術を用いたデジタル画像のサブバンド符号化（Sub-band coding of digital images using symmetric short kernel filters and arithmetic coding techniques）」、Proc. of IEEE International Conference on Acoustics、音声およびシグナル処理（Speech and Signal Processing）、ニューヨーク、７６１〜７６５ページ、１９８８年。
【０１１０】
［１１］エイ．アール．カルダーバンク（A. R. Calderbank）、アイ．ドベシィ（I. Daubechies）、ダブリュ．スウェルデン（W. Sweldens）およびビー．−エル．ヨー（B. -L. Yeo）、「整数を整数にマップするウェーブレット変換（Wavelet transforms that map integers to integers）」、Applied and Computational Harmonic Analysis（ACHA）、第５巻、３３２〜３６９ページ、１９９８年。
【０１１１】
［１２］JPEG2000 Part I Final Committee Draft Version 1.0. ISO/IEC JTC 1/SC 29/WG 1 N1646R、http://www.jpeg.org/public/fcd15444-1.pdfで入手可能。
［１３］ジェイ．ジー．プロアキス（J. G. Proakis）、デジタル・コミュニケーション（Digital Communications）、第３版、マグローヒル株式会社、ニューヨーク、１９９５年。
【０１１２】
［１４］ジー．ヴォヤツィス（G. Voyatzis）およびアイ．ピタス（I. Pitas）、「デジタル画像のカオス的混合および透かしへの応用（Chaotic mixing of digital images and applications to watermarking）」、Proceedings of European Conference of Multimedia Applications， Services Techniques (ECMAST’ 96)、６８７〜６９５ページ、１９９６年５月。
【０１１３】
［１５］ＵＳＣイメージ・データベース（USC image database）、http://sipi.usc.edu/services/database/Database.htmlで入手可能。
本明細書では、特定の実施形態を参照しながら本発明について説明してきたが、これらの実施形態が本発明の原理および用途についての単なる例示に過ぎないことを理解されたい。したがって、添付の特許請求の範囲によって規定された本発明の趣旨および範囲を逸脱することなく、例示の実施形態に対する多くの修正を実施し得ること、および他の構成を考案し得ることを理解されたい。
【図面の簡単な説明】
【０１１４】
【図１Ａ】従来のデータ隠蔽技術を使用することで生じる、望ましくないごま塩効果を示す画像の図。
【図１Ｂ】従来のデータ隠蔽技術を使用することで生じる、望ましくないごま塩効果を示す画像の図。
【図２】本発明の１つまたは複数の態様によるマーキングに適したテスト画像（Ｎ１Ａと呼ばれる、ＪＰＥＧ２０００テスト画像の赤色平面）のＨＬ１サブバンドにおけるＩＷＴ係数のヒストグラムを示すグラフ。
【図３】本発明の１つまたは複数の態様によるマーキングに適したＮ１Ａテスト画像のＨＬ１サブバンドにおける１０×１０ブロックの係数についての平均値のヒストグラムを示すグラフ。
【図４】本発明の１つまたは複数の態様に従って実施されるデータ埋め込み操作の間にどのグループのＩＷＴ係数を修正すべきかを決定する際に使用するマスクを識別するための情報を含む行列。
【図５Ａ】本発明の１つまたは複数の態様による、マーキングのためのブロックの４つのそれぞれのカテゴリに対する、画像のブロックの各画素についての空間領域グレースケール値の分布を示すヒストグラム。
【図５Ｂ】本発明の１つまたは複数の態様による、マーキングのためのブロックの４つのそれぞれのカテゴリに対する、画像のブロックの各画素についての空間領域グレースケール値の分布を示すヒストグラム。
【図５Ｃ】本発明の１つまたは複数の態様による、マーキングのためのブロックの４つのそれぞれのカテゴリに対する、画像のブロックの各画素についての空間領域グレースケール値の分布を示すヒストグラム。
【図５Ｄ】本発明の１つまたは複数の態様による、マーキングのためのブロックの４つのそれぞれのカテゴリに対する、画像のブロックの各画素についての空間領域グレースケール値の分布を示すヒストグラム。
【図６】本発明の１つまたは複数の態様に従って使用するのに適した５／３ウェーブレット・フィルタのフィルタ係数を示すデータ・テーブル。
【図７】本発明の１つまたは複数の態様による、ＨＬ１サブバンドの（ｉ，ｊ）位置におけるＩＷＴ係数の値の変化に対する空間領域での単位ステップ応答を示す行列。
【図８】本発明の１つまたは複数の態様による、ＬＨ１サブバンドの（ｉ，ｊ）位置におけるＩＷＴ係数の値の変化に対する空間領域での単位ステップ応答を示す行列。
【図９】本発明の１つまたは複数の態様による、ＬＬ１サブバンドの（ｉ，ｊ）位置におけるＩＷＴ係数の値の変化に対する空間領域での単位ステップ応答を示す行列。
【図１０】本発明の１つまたは複数の態様による、ＩＷＴ係数と空間領域で影響を受ける画素のグループとの間の関係を示すブロック図。
【図１１】本発明の１つまたは複数の態様による、ＣＬＬ（ｉ，ｊ）の単位ステップ応答の４分の１およびＣＬＬ（ｉ，ｊ＋１）の単位ステップ応答の４分の１を示す行列。
【図１２】本発明の１つまたは複数の態様による、タイプＡのブロックのデータ埋め込みルールを示すグラフ。
【図１３】本発明の１つまたは複数の態様による、タイプＢのブロックのデータ埋め込みルールを示すグラフ。
【図１４】本発明の１つまたは複数の態様による、タイプＣのブロックのデータ埋め込みルールを示すグラフ。
【図１５】本発明の１つまたは複数の態様によるデータ埋め込みのためのシステムおよび方法を示すブロック図。
【図１６】本発明の１つまたは複数の態様によるカバー・メディア・データを復元する方法を示すフロー図。
【図１７】本発明の１つまたは複数の態様による好ましいデータ埋め込み方法に従ってマークされた医用画像の図。
【図１８】本発明の１つまたは複数の態様による好ましいデータ埋め込み方法に従ってマークされたテスト（Ｎ１Ａ）画像の図。
【図１９】本発明の１つまたは複数の態様による方法を使用して画像をマーキングする際の、ブロック・サイズとデータ記憶容量を相互に関連づける実験結果のデータ・テーブル。
【図２０】本発明の１つまたは複数の態様による、平均ブロック係数値へのブロック・サイズの影響を示す実験結果のデータ・テーブル。
【図２１】本発明の１つまたは複数の態様による、可変ブロック・サイズ＝５およびシフト量＝８を用いてマークされ、４０．０９ｄＢ（デシベル）のＰＳＮＲ（ピーク信号対雑音比）を生ずる画像の図。
【図２２】本発明の１つまたは複数の態様による、可変ブロック・サイズ＝１２およびシフト量＝２を用いてマークされ、４９．４６ｄＢのＰＳＮＲを生ずる画像の図。
【図２３】本発明の１つまたは複数の態様による、ブロック・サイズとシフト量の様々な組合せで生ずるＰＳＮＲの値を示すデータ・テーブル。
【図２４】本発明の１つまたは複数の態様による、様々なブロック・サイズにおけるデータ生存率に対するＰＳＮＲをプロットしたグラフ。
【図２５】本発明の１つまたは複数の態様による、３×３のメディアン・フィルタを使用したテスト結果を示すデータ・テーブル。
【図２６】本発明の１つまたは複数の態様による、平均がゼロで分散が０．００１の追加のガウス雑音が存在する状況でのテスト結果を示すデータ・テーブル。
【図１Ａ】
2007522693.tif 000026
【図１Ｂ】
2007522693.tif 000027
【図２】
2007522693.tif 000028
【図３】
2007522693.tif 000029
【図４】
2007522693.tif 000030
【図５Ａ】
2007522693.tif 000031
【図５Ｂ】
2007522693.tif 000032
【図５Ｃ】
2007522693.tif 000033
【図５Ｄ】
2007522693.tif 000034
【図６】
2007522693.tif 000035
【図７】
2007522693.tif 000036
【図８】
2007522693.tif 000037
【図９】
2007522693.tif 000038
【図１０】
2007522693.tif 000039
【図１１】
2007522693.tif 000040
【図１２】
2007522693.tif 000041
【図１３】
2007522693.tif 000042
【図１４】
2007522693.tif 000043
【図１５】
2007522693.tif 000044
【図１６】
2007522693.tif 000045
【図１７】
2007522693.tif 000046
【図１８】
2007522693.tif 000047
【図１９】
2007522693.tif 000048
【図２０】
2007522693.tif 000049
【図２１】
2007522693.tif 000050
【図２２】
2007522693.tif 000051
【図２３】
2007522693.tif 000052
【図２４】
2007522693.tif 000053
【図２５】
2007522693.tif 000054
【図２６】
2007522693.tif 000055