ランレングスヒストグラム修正及び論理演算を使用した可逆的２値画像データ隠蔽のためのシステム及び方法
第１のデータセットの属性のヒストグラムを作成することを含むデータ隠蔽方法。ヒストグラムは、属性の実現値を含む。２つの隣接する実現値が選択され、２つの隣接する実現値のうち１つの回数がゼロである。選択された隣接する実現値と関連付けられた第１のデータセットのデータに、第２のデータセットが埋め込まれる。
【発明の詳細な説明】
【背景技術】
【０００１】
関連出願の相互参照
[0001] 本出願は、２００８年２月１日に出願された米国仮出願第６１／０６３，２４１号「REVERSIBLE BINARY IMAGE DATA HIDING USING RUN-LENGTH HISTOGRAM AND LOGICAL OPERATION」の優先権を主張する。
【０００２】
[0002] 開示の主題は、一般に、データ埋め込み及びデジタル形式画像からのデータ抽出に関する。より具体的には、開示は、ランレングスヒストグラム修正（run-length histogram modification）及び論理演算を使用した可逆的２値画像データ隠蔽に関する。
【発明の概要】
【課題を解決するための手段】
【０００３】
[0003] 代表的な実施形態は、いかなるタイプの２値画像（テキスト若しくはグラフ又はテキスト及び図の混成）及びハーフトーン画像にも適用することができる可逆的２値画像データ隠蔽技術に関する。可逆的データ隠蔽技術は、デジタル画像におけるデータを認知されずに隠蔽すること及び隠蔽されたデータが抽出された後にオリジナルの画像を歪めることなく再構築することをいう。
【０００４】
[0004] 少なくとも１つの代表的な実施形態によると、ランレングスヒストグラム修正が可逆的２値画像データ隠蔽に使用されている。具体的には、２値画像のランレングスが生成され、そのヒストグラムは、可逆的にデータを埋め込むために修正される。ヒストグラム修正及びシフトは無損失のデータ隠蔽を実現することができる。
【０００５】
[0005] 少なくとも１つの代表的な実施形態によると、黒と白のランレングス操作は、可逆的データ隠蔽に使用されるヒストグラムペア演算と組み合わされる。カバー２値画像内の孤立した白のピクセルが可逆性を損失しかねないという問題を解決するために黒と白のランレングスはどちらも操作される。データ埋め込み能力を向上させ、マークされた２値画像（データが中に隠蔽されている２値画像）のビジュアルクオリティを高めるために、ランレングスヒストグラム修正に基づく可逆的データ隠蔽を適用する前に、カバー２値画像に対して論理演算を含む変形が適用される。ランレングスヒストグラムに基づくデータ抽出技術を用いたデータ抽出の後に残っているものに対して、対応する逆変形が適用される。本明細書中に示される代表的な変形は、ＡＮＤ演算の使用及びＸＯＲ演算を含む。
【０００６】
[0006] 代表的な実施形態は、非ハーフトーン２値画像及びハーフトーン２値画像の両方に適用することができる。これらは、テキスト、グラフ及びテキストと図の混成の２値画像に使用することができる。これらの２値画像は、カメラ若しくはスキャナ、又はワードプロセッサ、又はコンピュータグラフィックソフトウェアによって生成されうる。ワードプロセッシングソフトウェアを必要とせずに、データは、２値画像に直接埋め込まれうる。２値テキスト画像への無損失データ隠蔽のために、「行分割」又は「語分割」を行う必要はない。代表的な実施形態で隠蔽されたデータを抽出する際、オリジナルの２値画像は必要でない。隠蔽されたデータを有する２値画像は、人間の視覚システムでは認識できない。ホスト２値画像の解像度が高いほど、多くの量のデータを埋め込むことができ、より良い性能が達成できる。代表的な実施形態は、画像認証、アノテーション及びカバーコミュニケーション（しばしばステガノグラフィと呼ばれる）を含む、２値画像を使用した多様な領域に適用することができる。
【０００７】
[0007] 本明細書に記載の代表的な実施形態は、ヒストグラムペアに基づく可逆的データ隠蔽を２値画像の黒のランレングスのヒストグラムに適用する可逆的２値画像データ隠蔽を提供する。適切に白及び黒のランレングスを操作することで、白の孤立点をうまく排除することができる。ＡＮＤ演算及びＸＯＲ演算などの論理演算は、埋め込み能力を大幅に向上させるためにも使用できる。
【０００８】
[0008] 既存の可逆的画像データ隠蔽のスキームと比較すると、本明細書に記載される代表的な実施形態は、同数の変化されたピクセル（従って、同じピーク信号対雑音比（ＰＳＮＲ）によって測定されたマークされた画像のビジュアルクオリティ）において、より多くのデータを埋め込むことができ、オリジナルの画像に対するマークされた画像の変化はより少なくなる。２値画像に同じ量のデータを埋め込むことは、２値非ハーフトーン画像及びハーフトーン画像の両方に適用することができる。すくなくとも１つの代表的な実施形態によると、ＡＮＤ演算での変形他が非ハーフトーン２値画像には好適であり、ＸＯＲ演算での変形がハーフトーン２値画像には適切であろう。
【０００９】
[0009] 他の主な特徴及び利点が、以下の図面、詳細な説明及び添付の請求の範囲をみると当業者には明らかとなろう。
【図面の簡単な説明】
【００１０】
[0010] 代表的な実施形態は、以後添付の図面を参照し説明される。
【図１（ａ）】[0011] 図１（ａ）は、オリジナルの画像のヒストグラムを示す図である。
【図１（ｂ）】[0012] 図１（ｂ）は、作成されたヒストグラムペアに伴いシフトされた図１（ａ）のヒストグラム図からの画像のヒストグラムを示す図である。
【図１（ｃ）】[0013] 図１（ｃ）は、ビット１，０が埋め込まれた後の図１（ｂ）のヒストグラム図からの画像のヒストグラムを示す図である。
【図２】[0014] 図２は、代表的な実施形態に従う、ＡＮＤ演算を含む、データ隠蔽処理を示すフロー図である。
【図３】[0015] 図３は、代表的な実施形態に従う、ＸＯＲ演算を含む、データ隠蔽処理を示すフロー図である。
【図４】[0016] 図４は、代表的な実施形態に従う、データ抽出処理を示すフロー図である。
【図５】[0017] 図５は、代表的な実施形態に従う、データ埋め込みを示すフロー図である。
【図６】[0018] 図６は、代表的な実施形態に従う、データ抽出を示すフロー図である。
【図７（ａ）】[0019] 図７（ａ）は、歩くミッキーマウスのオリジナルの画像を示す図である。
【図７（ｂ）】[0020] 図７（ｂ）は、１２８ビットでマークした図７（ａ）の画像を示す図である。
【図７（ｃ）】[0021] 図７（ｃ）は、１３７ピクセルが変更された図７（ａ）の画像を示す図である。
【図８（ａ）】[0022] 図８（ａ）は、図７（ａ）のヒストグラムを示す図である。
【図８（ｂ）】[0023] 図８（ｂ）は、ＡＮＤ演算後の図７（ａ）の画像のヒストグラムを示す図である。
【図９（ａ）】[0024] 図９（ａ）は、ヒヒのオリジナルの画像を示す図である。
【図９（ｂ）】[0025] 図９（ｂ）は、ＡＮＤ演算を使用して１０６３ビットでマークした図９（ａ）の画像を示す図である。
【図９（ｃ）】[0026] 図９（ｃ）は、１６４４ピクセルが変更された図９（ａ）の画像を示す図である。
【図１０（ａ）】[0027] 図１０（ａ）は、ヒヒのオリジナルのハーフトーン画像を示す図である。
【図１０（ｂ）】[0028] 図１０（ｂ）は、埋め込まれた７８９９ビットでマークされた図１０（ａ）の画像を示す図である。
【図１０（ｃ）】[0029] 図１０（ｃ）は、６７８７ビットが変更された図１０（ａ）の画像を示す図である。
【図１１（ａ）】[0030] 図１１（ａ）は、ＸＯＲ演算で変形する前のランレングスヒストグラムを示す図である。
【図１１（ｂ）】[0031] 図１１（ｂ）は、ＸＯＲ演算で変形した後のランレングスヒストグラムを示す図である。
【図１２（ａ）】[0032] 図１２（ａ）は、中国語文書のオリジナルの画像を示す図である。
【図１２（ｂ）】[0033] 図１２（ｂ）は、埋め込まれた１８，０３７ビットでマークされた図１２（ａ）を示す図である。
【図１２（ｃ）】[0034] 図１２（ｃ）は、９１０６ピクセルが変更された図１２（ａ）を示す図である。
【図１３（ａ）】[0035] 図１３（ａ）は、漫画のオリジナルの画像を示す図である。
【図１３（ｂ）】[0036] 図１３（ｂ）は、埋め込まれたビットでマークされた図１３（ａ）の画像を示す図である。
【図１３（ｃ）】[0037] 図１３（ｃ）は、ピクセルが変更された図１３（ａ）の画像を示す図である。。
【図１４（ａ）】[0038] 図１４（ａ）は、ニュースレターのオリジナルの画像を示す図である。
【図１４（ｂ）】[0039] 図１４（ｂ）は、ビット埋め込みマークした図１４（ａ）の画像を示す図である。
【図１４（ｃ）】[0040] 図１４（ｃ）は、ピクセル変更した図１４（ａ）の画像を示す図である。
【図１５（ａ）】[0041] 図１５（ａ）は、地図のオリジナルの画像を示す図である。
【図１５（ｂ）】[0042] 図１５（ｂ）は、埋め込まれた１８，０３７ビットでマークされた図１５（ａ）の画像を示す図である。
【図１５（ｃ）】[0043] 図１５（ｃ）は、９，１５９ピクセルが変更された図１５（ａ）の画像を示す図である。
【図１６】［0044］ 図１６は、代表的な実施形態の実施についての可逆的２値画像データ隠蔽コンピューティングシステムを示す図である。
【発明を実施するための形態】
【００１１】
［0045］ 図１（ａ）は、グレースケール画像の行の一部であり、可逆的データ隠蔽に使用され、５つのピクセル：３，３，１，２，１からなる１次元シーケンス[３，３，１，２，１]に対応するヒストグラムを示す。図１（ａ）のヒストグラムは、３つの垂直バーを含む。この３つの垂直バーは、ｈ（１）＝２、ｈ（２）＝１及びｈ（３）＝２によって表されることができる。ここでｈ（１）＝２は、この画像において、グレースケール値１であるピクセルが２つあることを意味する。
【００１２】
［0046］ 図１（ｂ）は、ヒストグラムペアを使用したデータの埋め込みを示す。ヒストグラムペアベースの無損失データ隠蔽の方法及び装置の一例が、参照により全体が本明細書に組み込まれる、２００７年２月１９日出願米国特許出願第１１／６７６，３９９号「Apparatus and Method for Reversible Data Hiding for JPEG Image」に開示されている。例としては、ヒストグラムにおいてグレースケール値２である点が０になるように、１及び／又は２と等しいグレースケールを有するピクセルにおいて、データが埋め込まれる。それゆえ、図１（ｂ）に示すとおり、ｈ（１）＝２は変更されない。しかしながら、ｈ（２）＝１は、ｈ（３）＝１にシフトされ、ｈ（２）＝０となり、１つのヒストグラムペア、すなわち[ｈ（１）＝２、ｈ（２）＝０]ができる。さらに、ｈ（３）＝２はｈ（４）＝２にシフトされ、これはｈ（２）とｈ（３）とがともに１単位、右方向へとシフトされたことを意味する。このようにして、データは、作成されたヒストグラムペア[ｈ（１）＝２，ｈ（２）＝０]に埋め込まれることができる。
【００１３】
［0047］ ２つのビット、１及び０は、作成されたヒストグラムペアに埋め込まれている。ピクセルシーケンスは、左から右へと走査される。グレースケール１を有する最初のピクセル（５つのピクセルのうち３番目）が発見されると、最初に埋め込まれるビットは１であると決定され、３番目のビットのグレースケール値が１から２へと変更される。ピクセルシーケンスは、走査され続ける。グレースケール１を有する２番目のピクセル（５つのピクセルのうち５番目）が発見されると、２番目に埋め込まれるビットは０であると決定され、グレースケール値は変更されない。全てのピクセルが走査されると、埋め込みが完了する。２に等しいグレースケールを有する２つのピクセルが、データ埋め込みに使用された。マークされた画像（データが内部に隠蔽された画像）の得られたヒストグラムを図１（ｃ）に示す。ピクセルクレースケール値シーケンスは、[４，４，２，３，１]となる。
【００１４】
［0048］ データ抽出の間、マークされた画像は、データ埋め込みの際に従った順番と同じ順番でピクセル毎に走査される。２に等しいグレースケール値を有するピクセル（５つのうちの３番目）が発見されると、ビット１が抽出される。１に等しいグレースケール値を有するピクセル（５つのうちの最後）が発見されると、ビット０が抽出される。ビットシーケンス１、０が抽出された後、２以上の全てのグレースケール値は、値が１つ減少される。このようにして、ピクセルグレースケール値シーケンスは、[４，４，２，３，１]から[３，３，１，２，１]へ戻される。このように、ヒストグラムベースデータ隠蔽スキームは可逆的である。すなわち、埋め込まれたデータは、エラーなく抽出されることができ、オリジナルのカバー画像は、無損失で回復されることができる。
【００１５】
［0049］ 以下は、ヒストグラムペアベース無損失データ隠蔽プロセスが２値画像のランレングス（ＲＬ）のヒストグラムにどのように適用されるかを示すさらなる例である。
【００１６】
［0050］ 第１の例では、ＲＬヒストグラムを操作することによるデータの２値画像への埋め込み方法が示される。変形前のオペレーションが含まれないことに留意されたい。２行及び１５列のみからなる単純な２値画像が、例示のために表１に示されており、０と１はそれぞれ、白のピクセルと黒のピクセルを示すために使用されている。
【表１】
【００１７】
[0051] ２値画像のＲＬ及びＲＬのヒストグラムが表２に示される。黒及び白のランを形成し、次いで対応するＲＬを数える際に、左から右へ、上の行から下の行へ走査が行われる。すなわち、行ｘ１の末尾が、行ｘ２の先頭とつながり、１次元（１−Ｄ）シーケンスを形成する。それから黒及び白のランレングスが決定される。２値画像全体を走査し１−Ｄシーケンスを形成する他の方法も、実現可能である。さらに、走査シークエンシングの間、黒のＲＬとそのすぐ隣の白のＲＬとは対を形成するように結合される。これは、黒のＲＬと白のＲＬの対、又は単純にＲＬ対と呼ばれる。黒のＲＬと白のＲＬの両方が考慮されることに留意されたい。
【表２】
【００１８】
[0052] 代表的な実施形態によると、ヒストグラムペアベース無損失データ隠蔽法は、２値画像にデータを埋め込むことができる。行ｘ１では、最初の１（行ｘ１、列１）について、最初に埋め込まれるビット１が検査される。黒のＲＬを１から２へ変えるために、行ｘ１及び列２においてピクセルは０から１へと変更される。続いて、対応する白のＲＬが１つ減少される。次の単一の黒の点（行ｘ２、列３）が検査され、ビット１が埋め込まれるので、白のピクセル（行ｘ２、列４）が黒へと変更される。行ｘ２、列６の単一の黒の点は、ビット０が埋め込まれるので、何も行われない。行２、列９の次の単一の黒の点は、ビット１が埋め込まれるので、次の白のピクセル（行ｘ２、列１０）が１へと変更される。行ｘ２、列１２の最後の単一の黒のピクセルは、ビット０が埋め込まれるので、何も行われない。結果として得られるデータ埋め込み後の２値画像が、表３に示されており、そのＲＬ及びＲＬが表４に示される。表４では、２つのパラメータＴ及びＴ１がリストされる。Ｔは、グレースケール画像のヒストグラムペアベース無損失データ隠蔽に使用されるパラメータであり、埋め込み開始位置を示す。ここで、２値画像について、Ｔは、データが無損失で埋め込まれた黒のＲＬ値を示す。本例では、Ｔ＝１である。Ｔ１は、黒のＲＬと、そのすぐ後に続く白のランのＲＬとの総和と等しく定義された別の閾値パラメータであり、これより低い場合は、ＲＬ対がデータ埋め込みに使用されない。本例では、Ｔ１＝３であり、これは、黒のＲＬとそのすぐ隣の白のＲＬとの総和が３より小さい場合には、データ埋め込みが黒のＲＬには適用されないことを意味する。
【００１９】
[0053] 隠蔽されたデータを抽出するプロシージャの例を説明する。この段階では、マークされた画像、すなわち、隠蔽されたデータを有する画像、が与えられている。本例では、マークされた画像データは、表３に示される。表３のマークされた画像に基づき、表４に示されるとおり、マークされた画像に関連付けられたＲＬ及びＲＬのヒストグラムを得ることが可能である。データ埋め込みにおける順番と同じ順番で、すなわち、左から右へ、上から下へ、全ての黒のランが１つずつ検査された。黒のＲＬが発見されると、ビット０が抽出される。黒のＲＬ２が発見されると、ビット１が抽出される。このようにして、ビットシーケンス「１，１，０，１，０」が抽出される。さらに、ビット１が抽出されると、対応する黒のＲＬ２が１に減少する。このようにして、オリジナルの画像は、全ての隠蔽されたデータが抽出された後に回復されることができる。
【表３】
【表４】
【００２０】
[0054] 別の代表的な実施形態によると、変形を伴うＲＬヒストグラムペア可逆的２値画像データ隠蔽処理は、ＡＮＤ演算を含む。この種の変形においては、カバー画像は初めに、偶数部分と奇数部分の２つの部分に分割される。偶数部分は、全ての偶数行の集合をいい、奇数部分は、全ての奇数行の集合をいう。カバー画像の代替的な分割、例えば、偶数の列の集合と奇数の列の集合、が可能である。偶数行及び奇数の行が、この記載においてカバー画像の２つの部分として使用される。
【００２１】
[0055] 図２は、ＡＮＤ演算を含む変形を伴う代表的なＲＬヒストグラムペア可逆的２値画像データ隠蔽プロセスにおいて実行されるオペレーションのフロー図を示す。特定の実施形態に応じて、追加的、より少ない、又は異なるオペレーションが実行されてよい。オペレーション２１において、カバー２値画像が、それぞれＸ１及びＸ２と表される、偶数部分と奇数部分に分離される。オペレーション２３では、Ｘ１のそれぞれの行が検査され、パターンが特定され、それぞれは１つの黒のピクセルから開始され、一連の連続する白のピクセルがこれに続く。
【００２２】
[0056] オペレーション２５では、オペレーション２３で特定されたパターンのそれぞれにつき、すぐ隣の行にある対応する部分のピクセルが検査される。先頭で連続する白のピクセル及び末尾で連続する黒のピクセルは、放棄される。オペレーション２７では、結果として得られた部分が、順にリンクされる。シークエンシングの例は、左から右へ、上から下へ、１次元（１−Ｄ）２値シーケンスを形成しながら行われる。オペレーション２９では、ランレングス技術が、この２値１−Ｄシーケンスに適用され、結果として得られる全てのランレングスのヒストグラムを形成する。ヒストグラムは、一般にマルチ値である。オペレーション３１では、ヒストグラムペアベース無損失データ隠蔽アルゴリズムが、生成されたＲＬヒストグラムを使用してデータを埋め込むために適用される。
【００２３】
[0057] ２行の２値画像の例は、ＡＮＤ演算を伴う事前変形を説明する。上述のとおり、黒と白のピクセル（黒と白の点とも呼ばれる）は、それぞれ１と０で表現される。
【表５】
【００２４】
[0058] 表５の最後の列（Ｌ３）は、上述のＡＮＤ演算から得られた２値シーケンスである。この結果として得られた２値シーケンスは、上述のとおり、２値画像にデータを無損失で埋め込むためのＲＬヒストグラムペアのために使用されることができる。
【００２５】
[0059] 表６では、４行、１５列を有する別の２値画像が考慮される。上述のプロシージャを適用することによって、画像中の点の３つのシーケンスを特定することが可能であり、これは表７に示される。表７のこれらの３つのシーケンスは、ＡＮＤ演算後の画像の一部である。ＲＬとそのヒストグラムが、表８に示される。黒のＲＬヒストグラム内にデータ埋め込みに使用することができるヒストグラムペアがあることが分かる。２値ビット「１，１，０，１」が埋め込まれた後の画像の部分が表９に示される。「１，１，０，１」が埋め込まれた後の画像の部分のＲＬとＲＬのヒストグラムが表１０に示される。この時点では、データ埋め込み後の画像の部分は、画像の偶数部分を形成するよう戻されている。この変更された偶数部分と変更されていない奇数部分を組み合わせることで、マークされた画像が作成され、表１１に示される。
【表６】
【表７】
【表８】
【表９】
【表１０】
【表１１】
【００２６】
[0060] 代表的な実施形態によると、表１１に与えられるマークされた２値からデータ抽出が開始される。マークされた２値を、奇数部分Ｘ１と偶数部分Ｘ２に分離することが可能である。データ埋め込みの間、奇数部分Ｘ１は変更されないままであるので、奇数部分Ｘ１は、データ抽出を手伝う。これは以下のとおりである。偶数部分が抽出された後、変更されていない奇数部分、この例ではとりわけ、ｘ１及びｘ３を使用して、マークされた画像の部分は、１）ｘ１及びｘ３内の「連続する０が後に続く１」のパターンの全てを検査すること、２）ｘ２及びｘ４の点シーケンスをそれぞれ行ｘ１及びｘ３の真下に置くこと、３）ついで、先頭で連続する白のピクセル及び末尾で連続する黒のピクセルが放棄されることによって特定される。結果として、表１２に示されるマークされた画像の部分が得られる。マークされた画像の部分のＲＬ及びＲＬヒストグラムが表１３に示される。表１３に示されるヒストグラムの部分[ｈ（１）＝１，ｈ（２）＝３]について、データ抽出プロシージャが適用され、ビット「１，１，０，１」が得られ、これは表１４に示されるマークされた画像の部分を変更したままにしておく。データ抽出後のマークされた画像の部分のＲＬ及びＲＬヒストグラムは、表１５に示される。データ抽出後のマークされた画像の部分（表１４）は、ついで偶数部分を回復するために戻されている。表１６に示されるとおり、奇数部分と偶数部分を組み合わせて、オリジナルの４行の２値画像が回復される。
【表１２】
【表１３】
【表１４】
【表１５】
【表１６】
【００２７】
[0061] 図３は、ＸＯＲ演算を含む変形を伴うＲＬヒストグラムペア可逆的２値画像データ隠蔽プロセスにおいて実行されるオペレーションのフロー図を示す。特定の実施形態に応じて、追加的、より少ない、又は異なるオペレーションが実行されてもよい。オペレーション３３において、カバー２値画像Ｘは、それぞれＸ１及びＸ２と表される奇数と偶数の２つの部分に分離される。Ｘ２のそれぞれの行について、オペレーション３５において、ＸＯＲ演算などの論理演算が行とその真上の行に適用される。オペレーション３７において、全ての行は、その上から下への順番を保ちながら、共にリストされ、それゆえ２次元アレイＹを形成する。オペレーション３９では、画像Ｙが行毎に上から下へ、左から右へ、先頭で連続する白のピクセル及び末尾で連続する黒のピクセルを無視しながら、走査される。オペレーション４１では、ＲＬヒストグラムペア無損失データ埋め込み方法が適用され、別の２次元アレイＺが結果として得られる。オペレーション４３では、Ｘ２の各偶数行は、上から下へ、対応するＺの行で置き換えられる。オペレーション４５では、Ｘ１とＺが組み合わされ、Ｘ１を奇数部分、Ｚを対応する偶数部分として扱い、隠蔽されたデータを有するオリジナルの画像である、マークされた画像が結果として得られる。
【００２８】
[0062] 表１７では、２行、奇数行ｘ１と偶数行ｘ２、１５列の２値画像の例が示される。データ埋め込み及び抽出の間、奇数行ｘ１は固定されるが、偶数行ｘ２は画像隠蔽及び抽出の間操作される。
【表１７】
【表１８】
【表１９】
【００２９】
[0063] 図４は、データ抽出プロシージャの例において実行されるオペレーションを説明する。特定の実施形態に応じて、追加的、より少ない又は異なるオペレーションが実行されてよい。オペレーション４７において、所与の２値画像は、それぞれＸ１とＸ２と表される偶数及び奇数の２つの部分に分離される。オペレーション４９において、各行について、ＸＯＲ演算などの論理演算がこの行及びその真上の行（Ｘ１に属する）に対して適用される。オペレーション５１において、全ての行は、その上から下への順番を保ちながら、共にリストされ、それゆえ２次元アレイＹを形成する。オペレーション５３では、画像Ｙは行毎に上から下へ、左から右へ、先頭で連続する白のピクセル及び末尾で連続する黒のピクセルを無視しながら走査される。オペレーション５５では、データ抽出プロシージャが適用され、抽出されたデータと別の２次元アレイＺが得られる。オペレーション５７では、Ｘ２の偶数行のそれぞれが、上から下へ、対応するＺの行と置き換えられる。オペレーション５９では、Ｘ１を奇数部分とし、Ｚを対応する偶数部分として扱い、Ｘ１とＺが組み合わされ、隠蔽されたデータを有するオリジナルの画像が得られる。
【００３０】
[0064] 得られたマークされた画像は表２０に示される。記載されたプロシージャを適用することで、抽出されたデータ「１，０，１」及びオリジナルの２値画像が得られる。中間結果ならびにＲＬ及びＲＬヒストグラムがそれぞれ、表２０、２１及び２２に示される。
【表２０】
【表２１】
【表２２】
【００３１】
[0065] グレースケール画像に関して、ヒストグラムペアベーススキームを使用したデータ埋め込みの後、空間領域のグレースケール値が許容範囲を超えるということを意味するアンダーフロー及び／又はオーバーフローを引き起こす可能性がある。例えば、整数ウェーブレット係数へデータが埋め込まれた後の８ビットグレースケール画像について、グレースケール値が[０，２５５]として記される０から２５５の範囲を超える可能性がある。結果として得られるグレースケール値が０より小さい場合、これはアンダーフローと呼ばれ、２５５を超える場合はオーバーフローと呼ばれる。２値画像への無損失データ隠蔽においても同様の問題が存在し、これを本明細書では境界問題と呼ぶ。
【００３２】
[0066] 本明細書に記載の代表的な実施形態は、データを埋め込むために、ヒストグラムベース無損失データ隠蔽スキームをランレングス（ＲＬ）のヒストグラムに適用する。上述のとおり、選択されたヒストグラムペアについて、ビット１を埋め込むことは、黒のランレングスを１つだけ増加させ直後の白のピクセルを１つだけ減らすことになる。この方法で、黒と白のランレングスの対を調整することによって、データ埋め込み後の２値画像の外観が、オリジナルの外観と類似したままとなる、すなわち、人間の視覚システムでは容易に変更を認識することができない。さらに、隠蔽されたデータは後にマークされた画像から無損失で抽出することができる。しかしながら、白のランレングスが１（孤立した白の点と呼ばれる）である場合、境界問題が起きえ、その直後の黒のランレングスが、ビット１を埋め込むために１だけ追加される。つまり、データ埋め込みルールによると、黒のランレングスは、１つだけ増加する必要があり、後続の白のスペースは１つ減少する必要があり、結果として白のランレングスが０になる。一度この現象が発生すると、データは可逆的に回復されることができなくなり、これは可逆性を損失する問題を示している。
【００３３】
[0067] 所与の２値画像が、ランレングスが１である白のランレングスを有さない場合、境界問題は存在しない。すなわち、２値画像が孤立した白の点を有さない場合である。２値画像への代表的な無損失データ隠蔽アプローチは、問題なく機能する。以下は、境界問題への解決方法を含む実施形態である。
【００３４】
[0068] 境界問題が発生した場合、代表的な実施形態を、２値画像に無損失データ隠蔽に適用するいくつかの方法がある。つまり、上述の境界問題を回避するいくつかの異なる方法がある。この境界問題を解決する１つの方法は、データ隠蔽に先立ち、所与の２値画像の解像度を２倍にすることである。孤立した白の点は、解像度が２倍にされた後で消失する。この高解像度２値画像に、無損失データ隠蔽スキームが適用される。データ抽出の後、解像度は、元に戻すことができる。このようにして、境界問題は、回避されることができる。しかし、マークされた画像は、２倍の解像度であることに留意されたい。
【００３５】
[0069] 境界問題を解決する別の方法は、無損失データ隠蔽の前に、所与の２値画像の境界問題が存在しないエリアを確認することである。ついで、代表的な実施形態が、所与の２値画像のこれらのエリアに対してのみ適用される。その際、復号側は、この情報を通知されるべきである。
【００３６】
[0070] 黒のランレングスの特定の範囲の値についてデータが埋め込まれた場合に境界問題が発見されないことが判明した場合、データは、この範囲内の黒のランレングスにのみ埋め込まれる。上述のケース２と同様に、いずれにしてもデータ抽出側はこの情報を通知されるべきである。
【００３７】
[0071] 境界問題の１つの対処法は、以下に説明するように事前処理に依存することである。すなわち、事前処理は、白のランレングスが１である状況、すなわち、２値画像の行に孤立した白のピクセルがある状況を排除することができる。このようなタイプの事前処理の１つは、孤立した白のピクセルを排除するためのローパスフィルタであることができ、孤立した白のピクセルがより長い黒のランレングスを形成するように黒のピクセルで置き換えられるということを意味する。この状況では、埋め込まれたデータは、無損失で回復されることができる。しかしながら、画像回復に関して、オリジナルの２値画像ではなく、事前処理された２値画像のみが無損失で回復されることができる。境界問題に対するこの解決案は、オリジナルの画像を正確に無損失で回復することができないが、デジタル埋め込み／透かしの新技術としていくつかのアプリケーションに応用することができる。
【００３８】
[0072] 少なくとも１つの代表的な実施形態が、孤立した白の点を円滑に対処する。全ての白のランレングス値は、データ埋め込みの前に検査される。白のランレングスが１である場合については、ランレングス対、すなわち、その直後の黒のランレングスとこの白のランレングス（この孤立した白の点と関連づけられる）、が考慮される。白のＲＬは１つだけ増加され、黒のＲＬ（このＲＬ対にある）は１つだけ減少される。このようにして、黒のＲＬと白のＲＬの総和が変化することなく、孤立した白の点が排除された。上述のとおり、この種の情報は、データ抽出及びオリジナルの画像回復において使用することができるよう、記録される必要がある。
【００３９】
[0073] 黒のＲＬと白のＲＬの総和が２である場合、つまり、黒のＲＬと白のＲＬの両方が１に等しい場合には、上述の提案された方法は機能しない場合があることに留意されたい。この起こりうる問題を解決するために、ＲＬ対内の黒のＲＬと白のＲＬの総和として画定される別の閾値Ｔ１が設定される。Ｔ１は少なくとも３である。言い換えると、ＲＬ対の黒のＲＬと白のＲＬの総和がＴ１と等しいか又はこれより大きいＲＬ対に対してのみデータが埋め込まれる。さらに、Ｔ１を選択することは、提案された無損失データ隠蔽スキームをより効果的にする。
【００４０】
[0074] 表２３において、２行、１５列の２値画像が示される。２行目の１４列目に位置し、下線がひかれた孤立した白の点が見られる。この２値画像のＲＬとＲＬヒストグラムが表２４に示される。ＲＬを算出する際、画像全体は、特定の順番で、例えば、左から右、又は上から下へと走査される。１行目の先頭で連続する白の点と２行目の末尾の連続する黒の点は、無視される。孤立した白の点含むＲＬ対は、＜２，１＞、すなわち、表２４に示される最後のＲＬ対である。この対では、黒のＲＬが２で、白のＲＬが１である。言い換えると、黒のＲＬと白のＲＬの総和は３である。それゆえ、上述の通り、孤立した白の点の一番左にある黒の点、すなわち、２行目、１３列に位置する黒の点を白の点に変更することによってこの孤立した白の点を排除することが可能である。この変更の後の、結果として得られる２値画像が表２５に示され、対応するＲＬとＲＬヒストグラムが表２６に示される。修正された２値画像は、データ隠蔽の準備がこれで整った。しかし、データ隠蔽における可逆性を達成するためには、この変更、すなわち、２行１３列目の黒の点が白の点へ変更されたことは、隠蔽されたデータの抽出の後で、オリジナルの２値画像回復の際に使用できるよう記録されるべきである。
【表２３】
【表２４】
【表２５】
【表２６】
【００４１】
[0075] 代表的なデータ埋め込み処理のブロック図が図５に示される。論理演算を含む変形は任意である。可逆的データ隠蔽において、変形は大抵よりよい性能をもたらすが、変形を使用せずともデータを２値画像に可逆的に埋め込むことができる。代表的なデータ抽出のブロック図が図６に示される。「論理演算を含む変形」はデータ埋め込みにおいては任意であるから、データ抽出においても任意である。
【００４２】
[0076] 代表的な実施形態の実施例が、以下の「歩いているミッキー」の画像及び中国語の画像の実験結果で実証される。「歩いているミッキー」の２値画像のサイズは、２７４×３１２である。画像は、ＡＮＤ演算を含む変形を伴う無損失データ隠蔽アルゴリズムが適用されている。計１２８ビットが一回の埋め込みで埋め込まれ、ブックキーピングデータは、この１２８ビットには含まれていない。マークされた画像中に、オリジナルの画像とは異なるピクセルが１３７ある。歩いているミッキーの画像及びＡＮＤ演算の前後の黒のランレングスのヒストグラムがそれぞれ図７及び図８に示される。図８（ａ）及び（ｂ）に示されるヒストグラムから、ＡＮＤ演算の後の黒のランレングス（ＲＬ）が短いＲＬの端により集中しているということが認められ、これはＡＮＤ演算が担う積極的な役割を意味する。VI Simposio Brasileiro em Seguranca da Incormacao e de Sistemas Computacionais(SBSeg), Santos, SP, Brasil, 2006におけるS.V.D.Pamboukian及びH.Y.Kimによる「Reversible Data Hiding and Reversible Authentication Watermarking for Binary Images」において、Pamboukianらは、同じ歩いているミッキー画像に１２８ビットを埋め込むために、彼らの可逆的２値画像データ隠蔽技術を使用し、データ埋め込みの後で変更されたピクセルが４９６得られた。Pamboukianらの方法と比べて、代表的な実施形態の技術は、同量の１２８ビットを埋め込む一方で、１３７ピクセルのみを異ならせる。
【００４３】
[0077] グレースケールのヒヒの画像にマトラボ（Matlab）でｉｍ２ｂｗオペレーションを適用することでヒヒの非ハーフトーン２値画像が得られる。サイズは、５１２×５１２である。１回の埋め込みで１０６３ビットが埋め込まれる。２３０ビットのブックキーピングデータは、１０６３ビットのペイロードには数えられていない。マークされた画像中にはオリジナルの２値画像と異なるピクセルが１６９４存在する。ヒヒのオリジナルの画像、マークされた画像、差異画像が、図９（ａ）、９（ｂ）及び９（ｃ）に示される。
【００４４】
[0078] 表２７は、ヒヒの５１２×５１２の非ハーフトーン２値画像へのＡＮＤ演算を用いた変形を伴う、データ埋め込みの一連の実験を含む。２値画像のＰＳＮＲは、以下の式を用いて算出される。Ｎが２値画像のピクセルの総数であり、Ｆ及びｆがピクセル値（２値画像では０か１）である。ｉ＝１，・・・，Ｎである。
【数１】
【表２７】
【００４５】
[0079] さらに、代表的な実施形態は、２値画像にデータを複数回埋め込むために使用されうる。その１つの方法は、複数回のデータ埋め込みを実施するために、交互に奇数部分（偶数部分は固定）にデータを埋め込み、ついで偶数部分（奇数部分は固定）にデータを埋め込む。別の方法は、複数回のデータ埋め込みのために、２値画像を９０度ずつ繰り返し回転させるものである。表２８は、ＡＮＤ演算を使用した変形を伴う非ハーフトーンのヒヒ画像への複数回のデータ埋め込みに関する情報を含む。
【表２８】
【００４６】
[0080] マトラボでディザーオペレーションをヒヒのグレースケール画像に適用することによってヒヒのハーフトーン画像が得られる。サイズは、５１２×５1２である。１回の埋め込みで総数７６９９ビットが埋め込まれ、１４９１ビットのブックキーピングデータは除外されている。データ隠蔽中に変更されたピクセルが６７８７ある。この変形においては、ＸＯＲ演算が使用された。ヒヒの画像及びＸＯＲ演算の前後の黒のランレングスのヒストグラムがそれぞれ図１０（ａ）、１０（ｂ）及び１０（ｃ）並びに図１１（ａ）及び図１１（ｂ）に示される。図１１（ｂ）から、ＸＯＲ演算を含む変形後の黒のランレングスのヒストグラムが、下側がより濃くなっていること、従ってデータ埋め込みが促進されていることが認められる。様々な容量でのヒヒのハーフトーン画像への１回のデータ埋め込みが表２９に示される。
【表２９】
【００４７】
[0081] 図１２（ａ）、１２（ｂ）及び１２（ｃ）において、３つの中国語の文書画像が示される。サイズは、１６５４×２３３８である。1１８，０３７ビットが可逆的に埋め込まれている。ＰＳＮＲは、２６．２８０５ｄＢである。オリジナルの画像、マークされた画像、差異画像を含む他の例示的画像は、漫画を示す図１３（ａ）から１３（ｃ）、ニュースレターを示す図１４（ａ）から１４（ｃ）及び地図を示す図１５（ａ）から１５（ｃ）に含まれる。
【００４８】
[0082] 図１６を参照し、代表的な実施形態を実装するための、可逆的２値画像データ隠蔽コンピューティングシステムが示される。図１６は、プロセッサ１１０、メモリ１２０及び１つ以上のドライブ１３０を含むコンピュータ１００を含む。ドライブ１３０及びこれらの関連コンピュータ記憶媒体は、コンピュータ１００に対してコンピュータ可読命令、データ命令、プログラムモジュール及び他のデータの保存を提供する。ドライブ１３０は、オペレーティングシステム１４０、アプリケーションプログラム１５０、プログラムモジュール１６０及びデータベース１８０を含むことができる。コンピュータ１００はさらに、これを介してユーザがコマンド及びデータを入力することができる入力装置１９０を含む。入力装置は、電子デジタイザ、マイクロフォン、キーボード及び一般にマウスと呼ばれるポインティング装置、トラックボール又はタッチパッドを含むことができる。他の入力装置は、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナなどを含みうる。
【００４９】
[0083] これらの及び他の入力装置は、プロセッサ１１０に、システムバスに連結されたユーザ入力インターフェースを介して接続されることができるが、他のインターフェース及びパラレルポート、ゲームポート又はユニバーサルシリアルバス（ＵＳＢ）などのバス構造によって連結されてもよい。コンピュータ１００などのコンピュータはまた、スピーカなどの、出力周辺インターフェース１９４などを介して接続されうる他の周辺出力装置を含みうる。
【００５０】
[0084] 示されるとおり、コンピュータ１００は、図１から１５に関して記述された代表的な埋め込み及び抽出の実施形態を実装する。一例として、メモリ１２０は、図２から６のフロー図に関して記載されたオペレーションを実行するためにプログラムされた命令を含むことができる。プロセッサ１１０は、メモリ１２０に含まれた命令を実行する。代表的な実施形態によると、オリジナルの画像は、あるデータを埋め込むために変形され、埋め込まれたデータを含む画像は、埋め込まれたデータを抽出するために変形される。よってこの方法のオペレーションは、コンピュータ１００などの特定の機械で実行され、さらに、この方法のオペレーションは、少なくとも画像へ埋め込むか又は画像から抽出することによってデータを変形させる。
【００５１】
[0085] コンピュータ１００は、ネットワークインターフェース１９６に接続されたリモートコンピュータなどの１つ以上のコンピュータへの論理接続を使用するネットワーク環境で動作する。リモートコンピュータは、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、又は他の共通のネットワークノードであってよく、コンピュータ１００に関する上述の多数の又は全ての要素を含むことができる。ネットワーク環境は、オフィスにおけるコモンプレイス、エンタープライズワイドエリアネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、イントラネット、及びインターネットである。例えば、本願の主題では、コンピュータ１００は、そこからデータが移動されてくるソース装置を備えてよく、リモートコンピュータは、デスティネーション装置を備えてもよく、その逆でもよい。ただし、ソース及びデスティネーション装置は、ネットワーク１０８又は他の手段によって接続される必要はないが、かわりに、データは、ソースプラットフォームによって書き込まれることができ、デスティネーションプラットフォームにより読み込むことができる媒体を介して移動されうる。ＬＡＮ又はＷＬＡＮネットワーク環境で使用される場合、コンピュータ１００は、ネットワークインターフェース１９６又はアダプタを介してＬＡＮに接続される。ＷＡＮネットワーク環境で使用される場合では、コンピュータ１００は典型的には、インターネット又はネットワーク１０８などのＷＡＮ上での通信を確立するためのモデム又は他の手段を含む。コンピュータ間の通信リンクを確立するための他の手段が使用されてよいことが理解されるだろう。
【００５２】
[0086] 上の記載は、例示及び説明のために提示されている。記載された正確な形態に対して排他的又は限定的であるようには意図されておらず、上述の教示に照らして改良及び変形が可能であり、記載された実施形態の実行から得られる。
【背景技術】
【０００１】
関連出願の相互参照
[0001] 本出願は、２００８年２月１日に出願された米国仮出願第６１／０６３，２４１号「REVERSIBLE BINARY IMAGE DATA HIDING USING RUN-LENGTH HISTOGRAM AND LOGICAL OPERATION」の優先権を主張する。
【０００２】
[0002] 開示の主題は、一般に、データ埋め込み及びデジタル形式画像からのデータ抽出に関する。より具体的には、開示は、ランレングスヒストグラム修正（run-length histogram modification）及び論理演算を使用した可逆的２値画像データ隠蔽に関する。
【発明の概要】
【課題を解決するための手段】
【０００３】
[0003] 代表的な実施形態は、いかなるタイプの２値画像（テキスト若しくはグラフ又はテキスト及び図の混成）及びハーフトーン画像にも適用することができる可逆的２値画像データ隠蔽技術に関する。可逆的データ隠蔽技術は、デジタル画像におけるデータを認知されずに隠蔽すること及び隠蔽されたデータが抽出された後にオリジナルの画像を歪めることなく再構築することをいう。
【０００４】
[0004] 少なくとも１つの代表的な実施形態によると、ランレングスヒストグラム修正が可逆的２値画像データ隠蔽に使用されている。具体的には、２値画像のランレングスが生成され、そのヒストグラムは、可逆的にデータを埋め込むために修正される。ヒストグラム修正及びシフトは無損失のデータ隠蔽を実現することができる。
【０００５】
[0005] 少なくとも１つの代表的な実施形態によると、黒と白のランレングス操作は、可逆的データ隠蔽に使用されるヒストグラムペア演算と組み合わされる。カバー２値画像内の孤立した白のピクセルが可逆性を損失しかねないという問題を解決するために黒と白のランレングスはどちらも操作される。データ埋め込み能力を向上させ、マークされた２値画像（データが中に隠蔽されている２値画像）のビジュアルクオリティを高めるために、ランレングスヒストグラム修正に基づく可逆的データ隠蔽を適用する前に、カバー２値画像に対して論理演算を含む変形が適用される。ランレングスヒストグラムに基づくデータ抽出技術を用いたデータ抽出の後に残っているものに対して、対応する逆変形が適用される。本明細書中に示される代表的な変形は、ＡＮＤ演算の使用及びＸＯＲ演算を含む。
【０００６】
[0006] 代表的な実施形態は、非ハーフトーン２値画像及びハーフトーン２値画像の両方に適用することができる。これらは、テキスト、グラフ及びテキストと図の混成の２値画像に使用することができる。これらの２値画像は、カメラ若しくはスキャナ、又はワードプロセッサ、又はコンピュータグラフィックソフトウェアによって生成されうる。ワードプロセッシングソフトウェアを必要とせずに、データは、２値画像に直接埋め込まれうる。２値テキスト画像への無損失データ隠蔽のために、「行分割」又は「語分割」を行う必要はない。代表的な実施形態で隠蔽されたデータを抽出する際、オリジナルの２値画像は必要でない。隠蔽されたデータを有する２値画像は、人間の視覚システムでは認識できない。ホスト２値画像の解像度が高いほど、多くの量のデータを埋め込むことができ、より良い性能が達成できる。代表的な実施形態は、画像認証、アノテーション及びカバーコミュニケーション（しばしばステガノグラフィと呼ばれる）を含む、２値画像を使用した多様な領域に適用することができる。
【０００７】
[0007] 本明細書に記載の代表的な実施形態は、ヒストグラムペアに基づく可逆的データ隠蔽を２値画像の黒のランレングスのヒストグラムに適用する可逆的２値画像データ隠蔽を提供する。適切に白及び黒のランレングスを操作することで、白の孤立点をうまく排除することができる。ＡＮＤ演算及びＸＯＲ演算などの論理演算は、埋め込み能力を大幅に向上させるためにも使用できる。
【０００８】
[0008] 既存の可逆的画像データ隠蔽のスキームと比較すると、本明細書に記載される代表的な実施形態は、同数の変化されたピクセル（従って、同じピーク信号対雑音比（ＰＳＮＲ）によって測定されたマークされた画像のビジュアルクオリティ）において、より多くのデータを埋め込むことができ、オリジナルの画像に対するマークされた画像の変化はより少なくなる。２値画像に同じ量のデータを埋め込むことは、２値非ハーフトーン画像及びハーフトーン画像の両方に適用することができる。すくなくとも１つの代表的な実施形態によると、ＡＮＤ演算での変形他が非ハーフトーン２値画像には好適であり、ＸＯＲ演算での変形がハーフトーン２値画像には適切であろう。
【０００９】
[0009] 他の主な特徴及び利点が、以下の図面、詳細な説明及び添付の請求の範囲をみると当業者には明らかとなろう。
【図面の簡単な説明】
【００１０】
[0010] 代表的な実施形態は、以後添付の図面を参照し説明される。
【図１（ａ）】[0011] 図１（ａ）は、オリジナルの画像のヒストグラムを示す図である。
【図１（ｂ）】[0012] 図１（ｂ）は、作成されたヒストグラムペアに伴いシフトされた図１（ａ）のヒストグラム図からの画像のヒストグラムを示す図である。
【図１（ｃ）】[0013] 図１（ｃ）は、ビット１，０が埋め込まれた後の図１（ｂ）のヒストグラム図からの画像のヒストグラムを示す図である。
【図２】[0014] 図２は、代表的な実施形態に従う、ＡＮＤ演算を含む、データ隠蔽処理を示すフロー図である。
【図３】[0015] 図３は、代表的な実施形態に従う、ＸＯＲ演算を含む、データ隠蔽処理を示すフロー図である。
【図４】[0016] 図４は、代表的な実施形態に従う、データ抽出処理を示すフロー図である。
【図５】[0017] 図５は、代表的な実施形態に従う、データ埋め込みを示すフロー図である。
【図６】[0018] 図６は、代表的な実施形態に従う、データ抽出を示すフロー図である。
【図７（ａ）】[0019] 図７（ａ）は、歩くミッキーマウスのオリジナルの画像を示す図である。
【図７（ｂ）】[0020] 図７（ｂ）は、１２８ビットでマークした図７（ａ）の画像を示す図である。
【図７（ｃ）】[0021] 図７（ｃ）は、１３７ピクセルが変更された図７（ａ）の画像を示す図である。
【図８（ａ）】[0022] 図８（ａ）は、図７（ａ）のヒストグラムを示す図である。
【図８（ｂ）】[0023] 図８（ｂ）は、ＡＮＤ演算後の図７（ａ）の画像のヒストグラムを示す図である。
【図９（ａ）】[0024] 図９（ａ）は、ヒヒのオリジナルの画像を示す図である。
【図９（ｂ）】[0025] 図９（ｂ）は、ＡＮＤ演算を使用して１０６３ビットでマークした図９（ａ）の画像を示す図である。
【図９（ｃ）】[0026] 図９（ｃ）は、１６４４ピクセルが変更された図９（ａ）の画像を示す図である。
【図１０（ａ）】[0027] 図１０（ａ）は、ヒヒのオリジナルのハーフトーン画像を示す図である。
【図１０（ｂ）】[0028] 図１０（ｂ）は、埋め込まれた７８９９ビットでマークされた図１０（ａ）の画像を示す図である。
【図１０（ｃ）】[0029] 図１０（ｃ）は、６７８７ビットが変更された図１０（ａ）の画像を示す図である。
【図１１（ａ）】[0030] 図１１（ａ）は、ＸＯＲ演算で変形する前のランレングスヒストグラムを示す図である。
【図１１（ｂ）】[0031] 図１１（ｂ）は、ＸＯＲ演算で変形した後のランレングスヒストグラムを示す図である。
【図１２（ａ）】[0032] 図１２（ａ）は、中国語文書のオリジナルの画像を示す図である。
【図１２（ｂ）】[0033] 図１２（ｂ）は、埋め込まれた１８，０３７ビットでマークされた図１２（ａ）を示す図である。
【図１２（ｃ）】[0034] 図１２（ｃ）は、９１０６ピクセルが変更された図１２（ａ）を示す図である。
【図１３（ａ）】[0035] 図１３（ａ）は、漫画のオリジナルの画像を示す図である。
【図１３（ｂ）】[0036] 図１３（ｂ）は、埋め込まれたビットでマークされた図１３（ａ）の画像を示す図である。
【図１３（ｃ）】[0037] 図１３（ｃ）は、ピクセルが変更された図１３（ａ）の画像を示す図である。。
【図１４（ａ）】[0038] 図１４（ａ）は、ニュースレターのオリジナルの画像を示す図である。
【図１４（ｂ）】[0039] 図１４（ｂ）は、ビット埋め込みマークした図１４（ａ）の画像を示す図である。
【図１４（ｃ）】[0040] 図１４（ｃ）は、ピクセル変更した図１４（ａ）の画像を示す図である。
【図１５（ａ）】[0041] 図１５（ａ）は、地図のオリジナルの画像を示す図である。
【図１５（ｂ）】[0042] 図１５（ｂ）は、埋め込まれた１８，０３７ビットでマークされた図１５（ａ）の画像を示す図である。
【図１５（ｃ）】[0043] 図１５（ｃ）は、９，１５９ピクセルが変更された図１５（ａ）の画像を示す図である。
【図１６】［0044］ 図１６は、代表的な実施形態の実施についての可逆的２値画像データ隠蔽コンピューティングシステムを示す図である。
【発明を実施するための形態】
【００１１】
［0045］ 図１（ａ）は、グレースケール画像の行の一部であり、可逆的データ隠蔽に使用され、５つのピクセル：３，３，１，２，１からなる１次元シーケンス[３，３，１，２，１]に対応するヒストグラムを示す。図１（ａ）のヒストグラムは、３つの垂直バーを含む。この３つの垂直バーは、ｈ（１）＝２、ｈ（２）＝１及びｈ（３）＝２によって表されることができる。ここでｈ（１）＝２は、この画像において、グレースケール値１であるピクセルが２つあることを意味する。
【００１２】
［0046］ 図１（ｂ）は、ヒストグラムペアを使用したデータの埋め込みを示す。ヒストグラムペアベースの無損失データ隠蔽の方法及び装置の一例が、参照により全体が本明細書に組み込まれる、２００７年２月１９日出願米国特許出願第１１／６７６，３９９号「Apparatus and Method for Reversible Data Hiding for JPEG Image」に開示されている。例としては、ヒストグラムにおいてグレースケール値２である点が０になるように、１及び／又は２と等しいグレースケールを有するピクセルにおいて、データが埋め込まれる。それゆえ、図１（ｂ）に示すとおり、ｈ（１）＝２は変更されない。しかしながら、ｈ（２）＝１は、ｈ（３）＝１にシフトされ、ｈ（２）＝０となり、１つのヒストグラムペア、すなわち[ｈ（１）＝２、ｈ（２）＝０]ができる。さらに、ｈ（３）＝２はｈ（４）＝２にシフトされ、これはｈ（２）とｈ（３）とがともに１単位、右方向へとシフトされたことを意味する。このようにして、データは、作成されたヒストグラムペア[ｈ（１）＝２，ｈ（２）＝０]に埋め込まれることができる。
【００１３】
［0047］ ２つのビット、１及び０は、作成されたヒストグラムペアに埋め込まれている。ピクセルシーケンスは、左から右へと走査される。グレースケール１を有する最初のピクセル（５つのピクセルのうち３番目）が発見されると、最初に埋め込まれるビットは１であると決定され、３番目のビットのグレースケール値が１から２へと変更される。ピクセルシーケンスは、走査され続ける。グレースケール１を有する２番目のピクセル（５つのピクセルのうち５番目）が発見されると、２番目に埋め込まれるビットは０であると決定され、グレースケール値は変更されない。全てのピクセルが走査されると、埋め込みが完了する。２に等しいグレースケールを有する２つのピクセルが、データ埋め込みに使用された。マークされた画像（データが内部に隠蔽された画像）の得られたヒストグラムを図１（ｃ）に示す。ピクセルクレースケール値シーケンスは、[４，４，２，３，１]となる。
【００１４】
［0048］ データ抽出の間、マークされた画像は、データ埋め込みの際に従った順番と同じ順番でピクセル毎に走査される。２に等しいグレースケール値を有するピクセル（５つのうちの３番目）が発見されると、ビット１が抽出される。１に等しいグレースケール値を有するピクセル（５つのうちの最後）が発見されると、ビット０が抽出される。ビットシーケンス１、０が抽出された後、２以上の全てのグレースケール値は、値が１つ減少される。このようにして、ピクセルグレースケール値シーケンスは、[４，４，２，３，１]から[３，３，１，２，１]へ戻される。このように、ヒストグラムベースデータ隠蔽スキームは可逆的である。すなわち、埋め込まれたデータは、エラーなく抽出されることができ、オリジナルのカバー画像は、無損失で回復されることができる。
【００１５】
［0049］ 以下は、ヒストグラムペアベース無損失データ隠蔽プロセスが２値画像のランレングス（ＲＬ）のヒストグラムにどのように適用されるかを示すさらなる例である。
【００１６】
［0050］ 第１の例では、ＲＬヒストグラムを操作することによるデータの２値画像への埋め込み方法が示される。変形前のオペレーションが含まれないことに留意されたい。２行及び１５列のみからなる単純な２値画像が、例示のために表１に示されており、０と１はそれぞれ、白のピクセルと黒のピクセルを示すために使用されている。
【表１】
【００１７】
[0051] ２値画像のＲＬ及びＲＬのヒストグラムが表２に示される。黒及び白のランを形成し、次いで対応するＲＬを数える際に、左から右へ、上の行から下の行へ走査が行われる。すなわち、行ｘ１の末尾が、行ｘ２の先頭とつながり、１次元（１−Ｄ）シーケンスを形成する。それから黒及び白のランレングスが決定される。２値画像全体を走査し１−Ｄシーケンスを形成する他の方法も、実現可能である。さらに、走査シークエンシングの間、黒のＲＬとそのすぐ隣の白のＲＬとは対を形成するように結合される。これは、黒のＲＬと白のＲＬの対、又は単純にＲＬ対と呼ばれる。黒のＲＬと白のＲＬの両方が考慮されることに留意されたい。
【表２】
【００１８】
[0052] 代表的な実施形態によると、ヒストグラムペアベース無損失データ隠蔽法は、２値画像にデータを埋め込むことができる。行ｘ１では、最初の１（行ｘ１、列１）について、最初に埋め込まれるビット１が検査される。黒のＲＬを１から２へ変えるために、行ｘ１及び列２においてピクセルは０から１へと変更される。続いて、対応する白のＲＬが１つ減少される。次の単一の黒の点（行ｘ２、列３）が検査され、ビット１が埋め込まれるので、白のピクセル（行ｘ２、列４）が黒へと変更される。行ｘ２、列６の単一の黒の点は、ビット０が埋め込まれるので、何も行われない。行２、列９の次の単一の黒の点は、ビット１が埋め込まれるので、次の白のピクセル（行ｘ２、列１０）が１へと変更される。行ｘ２、列１２の最後の単一の黒のピクセルは、ビット０が埋め込まれるので、何も行われない。結果として得られるデータ埋め込み後の２値画像が、表３に示されており、そのＲＬ及びＲＬが表４に示される。表４では、２つのパラメータＴ及びＴ１がリストされる。Ｔは、グレースケール画像のヒストグラムペアベース無損失データ隠蔽に使用されるパラメータであり、埋め込み開始位置を示す。ここで、２値画像について、Ｔは、データが無損失で埋め込まれた黒のＲＬ値を示す。本例では、Ｔ＝１である。Ｔ１は、黒のＲＬと、そのすぐ後に続く白のランのＲＬとの総和と等しく定義された別の閾値パラメータであり、これより低い場合は、ＲＬ対がデータ埋め込みに使用されない。本例では、Ｔ１＝３であり、これは、黒のＲＬとそのすぐ隣の白のＲＬとの総和が３より小さい場合には、データ埋め込みが黒のＲＬには適用されないことを意味する。
【００１９】
[0053] 隠蔽されたデータを抽出するプロシージャの例を説明する。この段階では、マークされた画像、すなわち、隠蔽されたデータを有する画像、が与えられている。本例では、マークされた画像データは、表３に示される。表３のマークされた画像に基づき、表４に示されるとおり、マークされた画像に関連付けられたＲＬ及びＲＬのヒストグラムを得ることが可能である。データ埋め込みにおける順番と同じ順番で、すなわち、左から右へ、上から下へ、全ての黒のランが１つずつ検査された。黒のＲＬが発見されると、ビット０が抽出される。黒のＲＬ２が発見されると、ビット１が抽出される。このようにして、ビットシーケンス「１，１，０，１，０」が抽出される。さらに、ビット１が抽出されると、対応する黒のＲＬ２が１に減少する。このようにして、オリジナルの画像は、全ての隠蔽されたデータが抽出された後に回復されることができる。
【表３】
【表４】
【００２０】
[0054] 別の代表的な実施形態によると、変形を伴うＲＬヒストグラムペア可逆的２値画像データ隠蔽処理は、ＡＮＤ演算を含む。この種の変形においては、カバー画像は初めに、偶数部分と奇数部分の２つの部分に分割される。偶数部分は、全ての偶数行の集合をいい、奇数部分は、全ての奇数行の集合をいう。カバー画像の代替的な分割、例えば、偶数の列の集合と奇数の列の集合、が可能である。偶数行及び奇数の行が、この記載においてカバー画像の２つの部分として使用される。
【００２１】
[0055] 図２は、ＡＮＤ演算を含む変形を伴う代表的なＲＬヒストグラムペア可逆的２値画像データ隠蔽プロセスにおいて実行されるオペレーションのフロー図を示す。特定の実施形態に応じて、追加的、より少ない、又は異なるオペレーションが実行されてよい。オペレーション２１において、カバー２値画像が、それぞれＸ１及びＸ２と表される、偶数部分と奇数部分に分離される。オペレーション２３では、Ｘ１のそれぞれの行が検査され、パターンが特定され、それぞれは１つの黒のピクセルから開始され、一連の連続する白のピクセルがこれに続く。
【００２２】
[0056] オペレーション２５では、オペレーション２３で特定されたパターンのそれぞれにつき、すぐ隣の行にある対応する部分のピクセルが検査される。先頭で連続する白のピクセル及び末尾で連続する黒のピクセルは、放棄される。オペレーション２７では、結果として得られた部分が、順にリンクされる。シークエンシングの例は、左から右へ、上から下へ、１次元（１−Ｄ）２値シーケンスを形成しながら行われる。オペレーション２９では、ランレングス技術が、この２値１−Ｄシーケンスに適用され、結果として得られる全てのランレングスのヒストグラムを形成する。ヒストグラムは、一般にマルチ値である。オペレーション３１では、ヒストグラムペアベース無損失データ隠蔽アルゴリズムが、生成されたＲＬヒストグラムを使用してデータを埋め込むために適用される。
【００２３】
[0057] ２行の２値画像の例は、ＡＮＤ演算を伴う事前変形を説明する。上述のとおり、黒と白のピクセル（黒と白の点とも呼ばれる）は、それぞれ１と０で表現される。
【表５】
【００２４】
[0058] 表５の最後の列（Ｌ３）は、上述のＡＮＤ演算から得られた２値シーケンスである。この結果として得られた２値シーケンスは、上述のとおり、２値画像にデータを無損失で埋め込むためのＲＬヒストグラムペアのために使用されることができる。
【００２５】
[0059] 表６では、４行、１５列を有する別の２値画像が考慮される。上述のプロシージャを適用することによって、画像中の点の３つのシーケンスを特定することが可能であり、これは表７に示される。表７のこれらの３つのシーケンスは、ＡＮＤ演算後の画像の一部である。ＲＬとそのヒストグラムが、表８に示される。黒のＲＬヒストグラム内にデータ埋め込みに使用することができるヒストグラムペアがあることが分かる。２値ビット「１，１，０，１」が埋め込まれた後の画像の部分が表９に示される。「１，１，０，１」が埋め込まれた後の画像の部分のＲＬとＲＬのヒストグラムが表１０に示される。この時点では、データ埋め込み後の画像の部分は、画像の偶数部分を形成するよう戻されている。この変更された偶数部分と変更されていない奇数部分を組み合わせることで、マークされた画像が作成され、表１１に示される。
【表６】
【表７】
【表８】
【表９】
【表１０】
【表１１】
【００２６】
[0060] 代表的な実施形態によると、表１１に与えられるマークされた２値からデータ抽出が開始される。マークされた２値を、奇数部分Ｘ１と偶数部分Ｘ２に分離することが可能である。データ埋め込みの間、奇数部分Ｘ１は変更されないままであるので、奇数部分Ｘ１は、データ抽出を手伝う。これは以下のとおりである。偶数部分が抽出された後、変更されていない奇数部分、この例ではとりわけ、ｘ１及びｘ３を使用して、マークされた画像の部分は、１）ｘ１及びｘ３内の「連続する０が後に続く１」のパターンの全てを検査すること、２）ｘ２及びｘ４の点シーケンスをそれぞれ行ｘ１及びｘ３の真下に置くこと、３）ついで、先頭で連続する白のピクセル及び末尾で連続する黒のピクセルが放棄されることによって特定される。結果として、表１２に示されるマークされた画像の部分が得られる。マークされた画像の部分のＲＬ及びＲＬヒストグラムが表１３に示される。表１３に示されるヒストグラムの部分[ｈ（１）＝１，ｈ（２）＝３]について、データ抽出プロシージャが適用され、ビット「１，１，０，１」が得られ、これは表１４に示されるマークされた画像の部分を変更したままにしておく。データ抽出後のマークされた画像の部分のＲＬ及びＲＬヒストグラムは、表１５に示される。データ抽出後のマークされた画像の部分（表１４）は、ついで偶数部分を回復するために戻されている。表１６に示されるとおり、奇数部分と偶数部分を組み合わせて、オリジナルの４行の２値画像が回復される。
【表１２】
【表１３】
【表１４】
【表１５】
【表１６】
【００２７】
[0061] 図３は、ＸＯＲ演算を含む変形を伴うＲＬヒストグラムペア可逆的２値画像データ隠蔽プロセスにおいて実行されるオペレーションのフロー図を示す。特定の実施形態に応じて、追加的、より少ない、又は異なるオペレーションが実行されてもよい。オペレーション３３において、カバー２値画像Ｘは、それぞれＸ１及びＸ２と表される奇数と偶数の２つの部分に分離される。Ｘ２のそれぞれの行について、オペレーション３５において、ＸＯＲ演算などの論理演算が行とその真上の行に適用される。オペレーション３７において、全ての行は、その上から下への順番を保ちながら、共にリストされ、それゆえ２次元アレイＹを形成する。オペレーション３９では、画像Ｙが行毎に上から下へ、左から右へ、先頭で連続する白のピクセル及び末尾で連続する黒のピクセルを無視しながら、走査される。オペレーション４１では、ＲＬヒストグラムペア無損失データ埋め込み方法が適用され、別の２次元アレイＺが結果として得られる。オペレーション４３では、Ｘ２の各偶数行は、上から下へ、対応するＺの行で置き換えられる。オペレーション４５では、Ｘ１とＺが組み合わされ、Ｘ１を奇数部分、Ｚを対応する偶数部分として扱い、隠蔽されたデータを有するオリジナルの画像である、マークされた画像が結果として得られる。
【００２８】
[0062] 表１７では、２行、奇数行ｘ１と偶数行ｘ２、１５列の２値画像の例が示される。データ埋め込み及び抽出の間、奇数行ｘ１は固定されるが、偶数行ｘ２は画像隠蔽及び抽出の間操作される。
【表１７】
【表１８】
【表１９】
【００２９】
[0063] 図４は、データ抽出プロシージャの例において実行されるオペレーションを説明する。特定の実施形態に応じて、追加的、より少ない又は異なるオペレーションが実行されてよい。オペレーション４７において、所与の２値画像は、それぞれＸ１とＸ２と表される偶数及び奇数の２つの部分に分離される。オペレーション４９において、各行について、ＸＯＲ演算などの論理演算がこの行及びその真上の行（Ｘ１に属する）に対して適用される。オペレーション５１において、全ての行は、その上から下への順番を保ちながら、共にリストされ、それゆえ２次元アレイＹを形成する。オペレーション５３では、画像Ｙは行毎に上から下へ、左から右へ、先頭で連続する白のピクセル及び末尾で連続する黒のピクセルを無視しながら走査される。オペレーション５５では、データ抽出プロシージャが適用され、抽出されたデータと別の２次元アレイＺが得られる。オペレーション５７では、Ｘ２の偶数行のそれぞれが、上から下へ、対応するＺの行と置き換えられる。オペレーション５９では、Ｘ１を奇数部分とし、Ｚを対応する偶数部分として扱い、Ｘ１とＺが組み合わされ、隠蔽されたデータを有するオリジナルの画像が得られる。
【００３０】
[0064] 得られたマークされた画像は表２０に示される。記載されたプロシージャを適用することで、抽出されたデータ「１，０，１」及びオリジナルの２値画像が得られる。中間結果ならびにＲＬ及びＲＬヒストグラムがそれぞれ、表２０、２１及び２２に示される。
【表２０】
【表２１】
【表２２】
【００３１】
[0065] グレースケール画像に関して、ヒストグラムペアベーススキームを使用したデータ埋め込みの後、空間領域のグレースケール値が許容範囲を超えるということを意味するアンダーフロー及び／又はオーバーフローを引き起こす可能性がある。例えば、整数ウェーブレット係数へデータが埋め込まれた後の８ビットグレースケール画像について、グレースケール値が[０，２５５]として記される０から２５５の範囲を超える可能性がある。結果として得られるグレースケール値が０より小さい場合、これはアンダーフローと呼ばれ、２５５を超える場合はオーバーフローと呼ばれる。２値画像への無損失データ隠蔽においても同様の問題が存在し、これを本明細書では境界問題と呼ぶ。
【００３２】
[0066] 本明細書に記載の代表的な実施形態は、データを埋め込むために、ヒストグラムベース無損失データ隠蔽スキームをランレングス（ＲＬ）のヒストグラムに適用する。上述のとおり、選択されたヒストグラムペアについて、ビット１を埋め込むことは、黒のランレングスを１つだけ増加させ直後の白のピクセルを１つだけ減らすことになる。この方法で、黒と白のランレングスの対を調整することによって、データ埋め込み後の２値画像の外観が、オリジナルの外観と類似したままとなる、すなわち、人間の視覚システムでは容易に変更を認識することができない。さらに、隠蔽されたデータは後にマークされた画像から無損失で抽出することができる。しかしながら、白のランレングスが１（孤立した白の点と呼ばれる）である場合、境界問題が起きえ、その直後の黒のランレングスが、ビット１を埋め込むために１だけ追加される。つまり、データ埋め込みルールによると、黒のランレングスは、１つだけ増加する必要があり、後続の白のスペースは１つ減少する必要があり、結果として白のランレングスが０になる。一度この現象が発生すると、データは可逆的に回復されることができなくなり、これは可逆性を損失する問題を示している。
【００３３】
[0067] 所与の２値画像が、ランレングスが１である白のランレングスを有さない場合、境界問題は存在しない。すなわち、２値画像が孤立した白の点を有さない場合である。２値画像への代表的な無損失データ隠蔽アプローチは、問題なく機能する。以下は、境界問題への解決方法を含む実施形態である。
【００３４】
[0068] 境界問題が発生した場合、代表的な実施形態を、２値画像に無損失データ隠蔽に適用するいくつかの方法がある。つまり、上述の境界問題を回避するいくつかの異なる方法がある。この境界問題を解決する１つの方法は、データ隠蔽に先立ち、所与の２値画像の解像度を２倍にすることである。孤立した白の点は、解像度が２倍にされた後で消失する。この高解像度２値画像に、無損失データ隠蔽スキームが適用される。データ抽出の後、解像度は、元に戻すことができる。このようにして、境界問題は、回避されることができる。しかし、マークされた画像は、２倍の解像度であることに留意されたい。
【００３５】
[0069] 境界問題を解決する別の方法は、無損失データ隠蔽の前に、所与の２値画像の境界問題が存在しないエリアを確認することである。ついで、代表的な実施形態が、所与の２値画像のこれらのエリアに対してのみ適用される。その際、復号側は、この情報を通知されるべきである。
【００３６】
[0070] 黒のランレングスの特定の範囲の値についてデータが埋め込まれた場合に境界問題が発見されないことが判明した場合、データは、この範囲内の黒のランレングスにのみ埋め込まれる。上述のケース２と同様に、いずれにしてもデータ抽出側はこの情報を通知されるべきである。
【００３７】
[0071] 境界問題の１つの対処法は、以下に説明するように事前処理に依存することである。すなわち、事前処理は、白のランレングスが１である状況、すなわち、２値画像の行に孤立した白のピクセルがある状況を排除することができる。このようなタイプの事前処理の１つは、孤立した白のピクセルを排除するためのローパスフィルタであることができ、孤立した白のピクセルがより長い黒のランレングスを形成するように黒のピクセルで置き換えられるということを意味する。この状況では、埋め込まれたデータは、無損失で回復されることができる。しかしながら、画像回復に関して、オリジナルの２値画像ではなく、事前処理された２値画像のみが無損失で回復されることができる。境界問題に対するこの解決案は、オリジナルの画像を正確に無損失で回復することができないが、デジタル埋め込み／透かしの新技術としていくつかのアプリケーションに応用することができる。
【００３８】
[0072] 少なくとも１つの代表的な実施形態が、孤立した白の点を円滑に対処する。全ての白のランレングス値は、データ埋め込みの前に検査される。白のランレングスが１である場合については、ランレングス対、すなわち、その直後の黒のランレングスとこの白のランレングス（この孤立した白の点と関連づけられる）、が考慮される。白のＲＬは１つだけ増加され、黒のＲＬ（このＲＬ対にある）は１つだけ減少される。このようにして、黒のＲＬと白のＲＬの総和が変化することなく、孤立した白の点が排除された。上述のとおり、この種の情報は、データ抽出及びオリジナルの画像回復において使用することができるよう、記録される必要がある。
【００３９】
[0073] 黒のＲＬと白のＲＬの総和が２である場合、つまり、黒のＲＬと白のＲＬの両方が１に等しい場合には、上述の提案された方法は機能しない場合があることに留意されたい。この起こりうる問題を解決するために、ＲＬ対内の黒のＲＬと白のＲＬの総和として画定される別の閾値Ｔ１が設定される。Ｔ１は少なくとも３である。言い換えると、ＲＬ対の黒のＲＬと白のＲＬの総和がＴ１と等しいか又はこれより大きいＲＬ対に対してのみデータが埋め込まれる。さらに、Ｔ１を選択することは、提案された無損失データ隠蔽スキームをより効果的にする。
【００４０】
[0074] 表２３において、２行、１５列の２値画像が示される。２行目の１４列目に位置し、下線がひかれた孤立した白の点が見られる。この２値画像のＲＬとＲＬヒストグラムが表２４に示される。ＲＬを算出する際、画像全体は、特定の順番で、例えば、左から右、又は上から下へと走査される。１行目の先頭で連続する白の点と２行目の末尾の連続する黒の点は、無視される。孤立した白の点含むＲＬ対は、＜２，１＞、すなわち、表２４に示される最後のＲＬ対である。この対では、黒のＲＬが２で、白のＲＬが１である。言い換えると、黒のＲＬと白のＲＬの総和は３である。それゆえ、上述の通り、孤立した白の点の一番左にある黒の点、すなわち、２行目、１３列に位置する黒の点を白の点に変更することによってこの孤立した白の点を排除することが可能である。この変更の後の、結果として得られる２値画像が表２５に示され、対応するＲＬとＲＬヒストグラムが表２６に示される。修正された２値画像は、データ隠蔽の準備がこれで整った。しかし、データ隠蔽における可逆性を達成するためには、この変更、すなわち、２行１３列目の黒の点が白の点へ変更されたことは、隠蔽されたデータの抽出の後で、オリジナルの２値画像回復の際に使用できるよう記録されるべきである。
【表２３】
【表２４】
【表２５】
【表２６】
【００４１】
[0075] 代表的なデータ埋め込み処理のブロック図が図５に示される。論理演算を含む変形は任意である。可逆的データ隠蔽において、変形は大抵よりよい性能をもたらすが、変形を使用せずともデータを２値画像に可逆的に埋め込むことができる。代表的なデータ抽出のブロック図が図６に示される。「論理演算を含む変形」はデータ埋め込みにおいては任意であるから、データ抽出においても任意である。
【００４２】
[0076] 代表的な実施形態の実施例が、以下の「歩いているミッキー」の画像及び中国語の画像の実験結果で実証される。「歩いているミッキー」の２値画像のサイズは、２７４×３１２である。画像は、ＡＮＤ演算を含む変形を伴う無損失データ隠蔽アルゴリズムが適用されている。計１２８ビットが一回の埋め込みで埋め込まれ、ブックキーピングデータは、この１２８ビットには含まれていない。マークされた画像中に、オリジナルの画像とは異なるピクセルが１３７ある。歩いているミッキーの画像及びＡＮＤ演算の前後の黒のランレングスのヒストグラムがそれぞれ図７及び図８に示される。図８（ａ）及び（ｂ）に示されるヒストグラムから、ＡＮＤ演算の後の黒のランレングス（ＲＬ）が短いＲＬの端により集中しているということが認められ、これはＡＮＤ演算が担う積極的な役割を意味する。VI Simposio Brasileiro em Seguranca da Incormacao e de Sistemas Computacionais(SBSeg), Santos, SP, Brasil, 2006におけるS.V.D.Pamboukian及びH.Y.Kimによる「Reversible Data Hiding and Reversible Authentication Watermarking for Binary Images」において、Pamboukianらは、同じ歩いているミッキー画像に１２８ビットを埋め込むために、彼らの可逆的２値画像データ隠蔽技術を使用し、データ埋め込みの後で変更されたピクセルが４９６得られた。Pamboukianらの方法と比べて、代表的な実施形態の技術は、同量の１２８ビットを埋め込む一方で、１３７ピクセルのみを異ならせる。
【００４３】
[0077] グレースケールのヒヒの画像にマトラボ（Matlab）でｉｍ２ｂｗオペレーションを適用することでヒヒの非ハーフトーン２値画像が得られる。サイズは、５１２×５１２である。１回の埋め込みで１０６３ビットが埋め込まれる。２３０ビットのブックキーピングデータは、１０６３ビットのペイロードには数えられていない。マークされた画像中にはオリジナルの２値画像と異なるピクセルが１６９４存在する。ヒヒのオリジナルの画像、マークされた画像、差異画像が、図９（ａ）、９（ｂ）及び９（ｃ）に示される。
【００４４】
[0078] 表２７は、ヒヒの５１２×５１２の非ハーフトーン２値画像へのＡＮＤ演算を用いた変形を伴う、データ埋め込みの一連の実験を含む。２値画像のＰＳＮＲは、以下の式を用いて算出される。Ｎが２値画像のピクセルの総数であり、Ｆ及びｆがピクセル値（２値画像では０か１）である。ｉ＝１，・・・，Ｎである。
【数１】
【表２７】
【００４５】
[0079] さらに、代表的な実施形態は、２値画像にデータを複数回埋め込むために使用されうる。その１つの方法は、複数回のデータ埋め込みを実施するために、交互に奇数部分（偶数部分は固定）にデータを埋め込み、ついで偶数部分（奇数部分は固定）にデータを埋め込む。別の方法は、複数回のデータ埋め込みのために、２値画像を９０度ずつ繰り返し回転させるものである。表２８は、ＡＮＤ演算を使用した変形を伴う非ハーフトーンのヒヒ画像への複数回のデータ埋め込みに関する情報を含む。
【表２８】
【００４６】
[0080] マトラボでディザーオペレーションをヒヒのグレースケール画像に適用することによってヒヒのハーフトーン画像が得られる。サイズは、５１２×５1２である。１回の埋め込みで総数７６９９ビットが埋め込まれ、１４９１ビットのブックキーピングデータは除外されている。データ隠蔽中に変更されたピクセルが６７８７ある。この変形においては、ＸＯＲ演算が使用された。ヒヒの画像及びＸＯＲ演算の前後の黒のランレングスのヒストグラムがそれぞれ図１０（ａ）、１０（ｂ）及び１０（ｃ）並びに図１１（ａ）及び図１１（ｂ）に示される。図１１（ｂ）から、ＸＯＲ演算を含む変形後の黒のランレングスのヒストグラムが、下側がより濃くなっていること、従ってデータ埋め込みが促進されていることが認められる。様々な容量でのヒヒのハーフトーン画像への１回のデータ埋め込みが表２９に示される。
【表２９】
【００４７】
[0081] 図１２（ａ）、１２（ｂ）及び１２（ｃ）において、３つの中国語の文書画像が示される。サイズは、１６５４×２３３８である。1１８，０３７ビットが可逆的に埋め込まれている。ＰＳＮＲは、２６．２８０５ｄＢである。オリジナルの画像、マークされた画像、差異画像を含む他の例示的画像は、漫画を示す図１３（ａ）から１３（ｃ）、ニュースレターを示す図１４（ａ）から１４（ｃ）及び地図を示す図１５（ａ）から１５（ｃ）に含まれる。
【００４８】
[0082] 図１６を参照し、代表的な実施形態を実装するための、可逆的２値画像データ隠蔽コンピューティングシステムが示される。図１６は、プロセッサ１１０、メモリ１２０及び１つ以上のドライブ１３０を含むコンピュータ１００を含む。ドライブ１３０及びこれらの関連コンピュータ記憶媒体は、コンピュータ１００に対してコンピュータ可読命令、データ命令、プログラムモジュール及び他のデータの保存を提供する。ドライブ１３０は、オペレーティングシステム１４０、アプリケーションプログラム１５０、プログラムモジュール１６０及びデータベース１８０を含むことができる。コンピュータ１００はさらに、これを介してユーザがコマンド及びデータを入力することができる入力装置１９０を含む。入力装置は、電子デジタイザ、マイクロフォン、キーボード及び一般にマウスと呼ばれるポインティング装置、トラックボール又はタッチパッドを含むことができる。他の入力装置は、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナなどを含みうる。
【００４９】
[0083] これらの及び他の入力装置は、プロセッサ１１０に、システムバスに連結されたユーザ入力インターフェースを介して接続されることができるが、他のインターフェース及びパラレルポート、ゲームポート又はユニバーサルシリアルバス（ＵＳＢ）などのバス構造によって連結されてもよい。コンピュータ１００などのコンピュータはまた、スピーカなどの、出力周辺インターフェース１９４などを介して接続されうる他の周辺出力装置を含みうる。
【００５０】
[0084] 示されるとおり、コンピュータ１００は、図１から１５に関して記述された代表的な埋め込み及び抽出の実施形態を実装する。一例として、メモリ１２０は、図２から６のフロー図に関して記載されたオペレーションを実行するためにプログラムされた命令を含むことができる。プロセッサ１１０は、メモリ１２０に含まれた命令を実行する。代表的な実施形態によると、オリジナルの画像は、あるデータを埋め込むために変形され、埋め込まれたデータを含む画像は、埋め込まれたデータを抽出するために変形される。よってこの方法のオペレーションは、コンピュータ１００などの特定の機械で実行され、さらに、この方法のオペレーションは、少なくとも画像へ埋め込むか又は画像から抽出することによってデータを変形させる。
【００５１】
[0085] コンピュータ１００は、ネットワークインターフェース１９６に接続されたリモートコンピュータなどの１つ以上のコンピュータへの論理接続を使用するネットワーク環境で動作する。リモートコンピュータは、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、又は他の共通のネットワークノードであってよく、コンピュータ１００に関する上述の多数の又は全ての要素を含むことができる。ネットワーク環境は、オフィスにおけるコモンプレイス、エンタープライズワイドエリアネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、イントラネット、及びインターネットである。例えば、本願の主題では、コンピュータ１００は、そこからデータが移動されてくるソース装置を備えてよく、リモートコンピュータは、デスティネーション装置を備えてもよく、その逆でもよい。ただし、ソース及びデスティネーション装置は、ネットワーク１０８又は他の手段によって接続される必要はないが、かわりに、データは、ソースプラットフォームによって書き込まれることができ、デスティネーションプラットフォームにより読み込むことができる媒体を介して移動されうる。ＬＡＮ又はＷＬＡＮネットワーク環境で使用される場合、コンピュータ１００は、ネットワークインターフェース１９６又はアダプタを介してＬＡＮに接続される。ＷＡＮネットワーク環境で使用される場合では、コンピュータ１００は典型的には、インターネット又はネットワーク１０８などのＷＡＮ上での通信を確立するためのモデム又は他の手段を含む。コンピュータ間の通信リンクを確立するための他の手段が使用されてよいことが理解されるだろう。
【００５２】
[0086] 上の記載は、例示及び説明のために提示されている。記載された正確な形態に対して排他的又は限定的であるようには意図されておらず、上述の教示に照らして改良及び変形が可能であり、記載された実施形態の実行から得られる。
【特許請求の範囲】
【請求項１】
データセットにデータを隠蔽する方法であって、
第１のデータセットの属性のヒストグラムであり、前記属性の実現値を含むヒストグラムを作成することと、
前記ヒストグラム内で隣接する２つの実現値であり、前記隣接する２つの実現値のうち１つの回数がゼロである実現値を選択することと、
前記選択された隣接する実現値と関連付けられた前記第１のデータセットのデータに、第２のデータセットを埋め込むことと、
を含む方法。
【請求項２】
前記選択された実現値と関連付けられた前記埋め込まれた第１のデータセットのデータ値を分析することと、
前記選択された実現値に基づき前記埋め込まれた第１のデータセットから前記第２のデータセットを抽出することと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記２つの隣接する実現値を作成するために、前記第１のデータセットを変更することをさらに含み、前記２つの隣接する実現値のうち１つの回数がゼロである、請求項１に記載の方法。
【請求項４】
前記第１のデータセットが画像を含む、請求項１に記載の方法。
【請求項５】
前記画像の行を連結させることによって、１次元シーケンスを形成することをさらに含む、請求項４に記載の方法。
【請求項６】
前記属性がデータ値を含む、請求項１に記載の方法。
【請求項７】
前記属性がデータ値のランレングスを含む、請求項１に記載の方法。
【請求項８】
前記データ値が、２進値を含む、請求項１に記載の方法。
【請求項９】
第１のウィンドウを選択することをさらに含み、前記第２のデータセットが、前記第１のウィンドウと関連付けられた前記第１のデータセットの偶数データにのみ埋め込まれる、請求項８に記載の方法。
【請求項１０】
前記第１のウィンドウが、前記第１のデータセットの奇数部分において、連続する第２の値が後に続く、第１のデータ値の少なくとも１つのシーケンスと関連付けられる、請求項８に記載の方法。
【請求項１１】
第２のウィンドウを選択することをさらに含み、前記第２のデータセットが、前記第２のウィンドウと関連づけられた前記第１のデータセットの偶数データのみに埋め込まれる、請求項９に記載の方法。
【請求項１２】
前記第２のウィンドウが、第１のデータ値の第１のシーケンス要素を含まず、第２のデータ値の最終シーケンス要素を含まない前記第１のウィンドウと関連付けられた少なくとも１つのシーケンスと関連付けられている、請求項１１に記載の方法。
【請求項１３】
前記第１のデータセットの偶数部分を、前記第１のデータセットの偶数部分及び奇数部分の排他的ＯＲと置き換えることと、
前記第１のデータセットの偶数部分の属性のヒストグラム作成することと、
前記第２のデータセットを、前記選択された実現値に関連付けられた前記第１のデータセットの前記偶数部分に埋め込むことと、
前記第１のデータセットの前記埋め込まれた偶数部分を、前記第１のデータセットの前記埋め込まれた偶数部分及び前記第１のデータセットの前記奇数部分の排他的ＯＲと置き換えることと、
を更に含む、請求項８に記載の方法。
【請求項１４】
前記第１のデータセットフィルタリングすることをさらに含む、請求項１に記載の方法。
【請求項１５】
前記ヒストグラムを作成する前に、前記第１のデータセットの解像度を２倍にすることをさらに含む、請求項１に記載の方法。
【請求項１６】
前記第２のデータセットが、前記第１のデータセットの対にのみ埋め込まれ、前記対の第１の値の第１の数と前記対の第２の値の第２の数との和が、閾値よりも大きい、請求項１に記載の方法。
【請求項１７】
前記埋め込まれた第１のデータセットの第２の属性の第２のヒストグラムであり、前記第２の属性の第２の実現値を含む前記第２のヒストグラムを作成することと、
２つの隣接する第２の実現値であり、前記２つの隣接する第２の実現値のうち１つの第２の回数がゼロである実現値を選択することと、
前記選択された第２の実現値と関連付けられた前記埋め込まれた第１のデータセットのデータに第３のデータセットを埋め込むことと、
をさらに含む、請求項１に記載の方法。
【請求項１８】
前記第２のヒストグラムを作成する前に、前記埋め込まれた第１のデータセットを操作することをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記埋め込まれた第１のデータセットを操作することが、前記埋め込まれた第１のデータセットを９０度回転させることを含む、請求項１８に記載の方法。
【請求項２０】
コンピュータ可読媒体であって、それに記憶されたコンピュータ可読命令を有し、前記命令がプロセッサによって実行される際に、コンピューティングデバイスに、
第１のデータセットの属性のヒストグラムであり、属性の実現値を含むヒストグラムを作成させ、
隣接する２つの実現値であり、前記隣接する２つの実現値のうち１つの回数がゼロである実現値を選択させ、
前記選択された実現値と関連付けられた前記第１のデータセットのデータに、第２のデータセットを埋め込ませる、コンピュータ可読媒体。
【請求項１】
データセットにデータを隠蔽する方法であって、
第１のデータセットの属性のヒストグラムであり、前記属性の実現値を含むヒストグラムを作成することと、
前記ヒストグラム内で隣接する２つの実現値であり、前記隣接する２つの実現値のうち１つの回数がゼロである実現値を選択することと、
前記選択された隣接する実現値と関連付けられた前記第１のデータセットのデータに、第２のデータセットを埋め込むことと、
を含む方法。
【請求項２】
前記選択された実現値と関連付けられた前記埋め込まれた第１のデータセットのデータ値を分析することと、
前記選択された実現値に基づき前記埋め込まれた第１のデータセットから前記第２のデータセットを抽出することと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記２つの隣接する実現値を作成するために、前記第１のデータセットを変更することをさらに含み、前記２つの隣接する実現値のうち１つの回数がゼロである、請求項１に記載の方法。
【請求項４】
前記第１のデータセットが画像を含む、請求項１に記載の方法。
【請求項５】
前記画像の行を連結させることによって、１次元シーケンスを形成することをさらに含む、請求項４に記載の方法。
【請求項６】
前記属性がデータ値を含む、請求項１に記載の方法。
【請求項７】
前記属性がデータ値のランレングスを含む、請求項１に記載の方法。
【請求項８】
前記データ値が、２進値を含む、請求項１に記載の方法。
【請求項９】
第１のウィンドウを選択することをさらに含み、前記第２のデータセットが、前記第１のウィンドウと関連付けられた前記第１のデータセットの偶数データにのみ埋め込まれる、請求項８に記載の方法。
【請求項１０】
前記第１のウィンドウが、前記第１のデータセットの奇数部分において、連続する第２の値が後に続く、第１のデータ値の少なくとも１つのシーケンスと関連付けられる、請求項８に記載の方法。
【請求項１１】
第２のウィンドウを選択することをさらに含み、前記第２のデータセットが、前記第２のウィンドウと関連づけられた前記第１のデータセットの偶数データのみに埋め込まれる、請求項９に記載の方法。
【請求項１２】
前記第２のウィンドウが、第１のデータ値の第１のシーケンス要素を含まず、第２のデータ値の最終シーケンス要素を含まない前記第１のウィンドウと関連付けられた少なくとも１つのシーケンスと関連付けられている、請求項１１に記載の方法。
【請求項１３】
前記第１のデータセットの偶数部分を、前記第１のデータセットの偶数部分及び奇数部分の排他的ＯＲと置き換えることと、
前記第１のデータセットの偶数部分の属性のヒストグラム作成することと、
前記第２のデータセットを、前記選択された実現値に関連付けられた前記第１のデータセットの前記偶数部分に埋め込むことと、
前記第１のデータセットの前記埋め込まれた偶数部分を、前記第１のデータセットの前記埋め込まれた偶数部分及び前記第１のデータセットの前記奇数部分の排他的ＯＲと置き換えることと、
を更に含む、請求項８に記載の方法。
【請求項１４】
前記第１のデータセットフィルタリングすることをさらに含む、請求項１に記載の方法。
【請求項１５】
前記ヒストグラムを作成する前に、前記第１のデータセットの解像度を２倍にすることをさらに含む、請求項１に記載の方法。
【請求項１６】
前記第２のデータセットが、前記第１のデータセットの対にのみ埋め込まれ、前記対の第１の値の第１の数と前記対の第２の値の第２の数との和が、閾値よりも大きい、請求項１に記載の方法。
【請求項１７】
前記埋め込まれた第１のデータセットの第２の属性の第２のヒストグラムであり、前記第２の属性の第２の実現値を含む前記第２のヒストグラムを作成することと、
２つの隣接する第２の実現値であり、前記２つの隣接する第２の実現値のうち１つの第２の回数がゼロである実現値を選択することと、
前記選択された第２の実現値と関連付けられた前記埋め込まれた第１のデータセットのデータに第３のデータセットを埋め込むことと、
をさらに含む、請求項１に記載の方法。
【請求項１８】
前記第２のヒストグラムを作成する前に、前記埋め込まれた第１のデータセットを操作することをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記埋め込まれた第１のデータセットを操作することが、前記埋め込まれた第１のデータセットを９０度回転させることを含む、請求項１８に記載の方法。
【請求項２０】
コンピュータ可読媒体であって、それに記憶されたコンピュータ可読命令を有し、前記命令がプロセッサによって実行される際に、コンピューティングデバイスに、
第１のデータセットの属性のヒストグラムであり、属性の実現値を含むヒストグラムを作成させ、
隣接する２つの実現値であり、前記隣接する２つの実現値のうち１つの回数がゼロである実現値を選択させ、
前記選択された実現値と関連付けられた前記第１のデータセットのデータに、第２のデータセットを埋め込ませる、コンピュータ可読媒体。
【図１（ａ）】
【図１（ｂ）】
【図１（ｃ）】
【図７（ａ）】
【図７（ｂ）】
【図７（ｃ）】
【図８（ａ）】
【図８（ｂ）】
【図９（ａ）】
【図９（ｂ）】
【図９（ｃ）】
【図１０（ａ）】
【図１０（ｂ）】
【図１０（ｃ）】
【図１１（ａ）】
【図１１（ｂ）】
【図１２（ａ）】
【図１２（ｂ）】
【図１２（ｃ）】
【図１３（ａ）】
【図１３（ｂ）】
【図１３（ｃ）】
【図１４（ａ）】
【図１４（ｂ）】
【図１４（ｃ）】
【図１５（ａ）】
【図１５（ｂ）】
【図１５（ｃ）】
【図２】
【図３】
【図４】
【図５】
【図６】
【図１６】
【図１（ｂ）】
【図１（ｃ）】
【図７（ａ）】
【図７（ｂ）】
【図７（ｃ）】
【図８（ａ）】
【図８（ｂ）】
【図９（ａ）】
【図９（ｂ）】
【図９（ｃ）】
【図１０（ａ）】
【図１０（ｂ）】
【図１０（ｃ）】
【図１１（ａ）】
【図１１（ｂ）】
【図１２（ａ）】
【図１２（ｂ）】
【図１２（ｃ）】
【図１３（ａ）】
【図１３（ｂ）】
【図１３（ｃ）】
【図１４（ａ）】
【図１４（ｂ）】
【図１４（ｃ）】
【図１５（ａ）】
【図１５（ｂ）】
【図１５（ｃ）】
【図２】
【図３】
【図４】
【図５】
【図６】
【図１６】
【公表番号】特表２０１１−５１２０８４（Ｐ２０１１−５１２０８４Ａ）
【公表日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願番号】特願２０１０−５４５１８５（Ｐ２０１０−５４５１８５）
【出願日】平成２１年１月３０日（２００９．１．３０）
【国際出願番号】ＰＣＴ／ＵＳ２００９／０３２５３９
【国際公開番号】ＷＯ２００９／０９９９１４
【国際公開日】平成２１年８月１３日（２００９．８．１３）
【出願人】（５０９３４９５１０）ニュー ジャージー インスティチュート オブ テクノロジー (8)
【Ｆターム（参考）】
【公表日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願日】平成２１年１月３０日（２００９．１．３０）
【国際出願番号】ＰＣＴ／ＵＳ２００９／０３２５３９
【国際公開番号】ＷＯ２００９／０９９９１４
【国際公開日】平成２１年８月１３日（２００９．８．１３）
【出願人】（５０９３４９５１０）ニュー ジャージー インスティチュート オブ テクノロジー (8)
【Ｆターム（参考）】
[ Back to top ]