(57)【要約】システムが、画像記憶域、ディジタルハッシングユニット、および透かしエンコーダを備える。ディジタル画像ハッシングユニットは、視覚的に類似する画像は同じハッシュ値にハッシュされ、視覚的に異なる画像は異なるハッシュ値にハッシュされるようにして、ディジタル画像を表すハッシュ値を計算する。ハッシュ値は、画像ハッシュテーブルに記憶され、このテーブルを介して元画像と関連付けられる。この画像ハッシュテーブルを使用して、画像記憶域を索引付けすることができる。透かしエンコーダは、ハッシュ値および秘密に基づいて透かしを計算する。両方の値を使用することにより、ＢＯＲＥ（Ｂｒｅａｋ  Ｏｎｃｅ，Ｒｕｎ  Ｅｖｅｒｙｗｈｅｒｅ、一度破られればどこへでも流入する）攻撃に耐える透かしがもたらされる。というのは、包括的な透かし秘密が発見されたとしても、攻撃者は、画像の攻撃を成功させるにはやはり各画像のハッシュ値を必要とするからである。このシステムは、インターネットを警備して海賊コピーを検出するように構成することができる。このシステムは、リモートウェブサイトからランダムに画像を収集し、同じハッシング関数を使用して画像をハッシュする。次いでシステムは、画像ハッシュを元画像のハッシュと比較する。ハッシュが合致する場合は、収集した画像は元画像のコピーであることが疑われる。
2004526340.tif 000002
【特許請求の範囲】
【請求項１】
画像をハッシュするためのコンピュータ実装される方法であって、
画像を受け取るステップ、および
視覚的に異なる画像が相互にほぼ独立したハッシュ値となり、視覚的に類似する画像が同一のハッシュ値となるように、前記画像を表すハッシュ値を導出するステップを含むことを特徴とする方法。
【請求項２】
前記画像に関連して前記ハッシュ値を記憶するステップをさらに含むことを特徴とする請求項１に記載のコンピュータ実装される方法。
【請求項３】
前記ハッシュ値を使用して前記画像を索引付けするステップをさらに含むことを特徴とする請求項１に記載のコンピュータ実装される方法。
【請求項４】
前記ハッシュ値を一部に使用して前記ディジタル画像に透かしを入れ、透かし入り画像を生成するステップをさらに含むことを特徴とする請求項１に記載のコンピュータ実装される方法。
【請求項５】
前記ハッシュ値を、別の画像から導出された別のハッシュ値と比較するステップをさらに含むことを特徴とする請求項１に記載のコンピュータ実装される方法。
【請求項６】
画像をハッシュするためのコンピュータ実装される方法であって、
前記画像を画像変換物に変換するステップ、
前記画像変換物をランダムに複数のタイルに分割するステップであって、各タイルが複数のピクセルに関するピクセルデータを含むステップ、
前記各タイルにつき前記ピクセルデータを平均化して、対応するタイル平均値を生成するステップ、
前記タイル平均値に部分的に基づいて、異なる複数の量子化レベルを有する指数分布を生成するステップ、
前記各タイル平均値をランダムに前記量子化レベルのうちの１つに丸めて、丸めた値を生成するステップ、および
前記丸めた値の合成値をハッシュするステップを含むことを特徴とする方法。
【請求項７】
前記変換するステップは、フーリエ変換、ウェーブレット変換、およびＤＣＴ変換からなる関数グループから選択される変換関数に従って行われることを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項８】
前記変換するステップは、前記画像を複数のウェーブレットサブバンドに分解するステップを含むことを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項９】
前記分割するステップは、重なり合わない矩形のタイルを形成するステップを含むことを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項１０】
前記分割するステップは、重なり合う矩形のタイルを形成するステップを含むことを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項１１】
前記平均化するステップは、前記タイル平均値がほぼ０である場合は前記ピクセルデータの分散を計算することを含むことを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項１２】
前記丸めるステップは、前記量子化レベルのうちのより近いレベルの方に丸めるステップであって、ただし前記量子化レベルのうちのより遠いレベルの方に丸める可能性を等しく示すランダム性をもって丸めるステップを含むことを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項１３】
前記ハッシュするステップは、前記丸めた値を処理して、視覚的に異なる画像の場合は中間ハッシュ値が時間の約６０％で異なり、視覚的に類似する画像の場合は中間ハッシュ値が時間の約２０％を除いてすべて一致するように、中間ハッシュ値を生成するステップを含むことを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項１４】
前記ハッシュするステップは、Ｒｅｅｄ−Ｍｕｌｌｅｒ エラー訂正コード復号器を使用して、前記丸めた値を処理するステップを含むことを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項１５】
前記ハッシュするステップは、Ｒｅｅｄ−Ｍｕｌｌｅｒ エラー訂正コード復号器を指数擬似ランダムノルムと共に使用して、前記丸めた値を処理するステップを含むことを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項１６】
前記ハッシュするステップは中間ハッシュ値を生成し、さらに、エラー訂正プロセスを介して前記中間ハッシュ値のサイズを削減するステップを含むことを特徴とする請求項６に記載のコンピュータ実装される方法。
【請求項１７】
コンピュータ実装されるハッシング方法であって、
視覚的に異なる画像が相互にほぼ独立したハッシュ値となり、視覚的に類似する画像が同一のハッシュ値となるように、ディジタル画像を表すハッシュ値を計算するステップ、および
前記ハッシュ値を前記ディジタル画像との関連で記憶するステップを含むことを特徴とする方法。
【請求項１８】
コンピュータ実装されるハッシング方法であって、
視覚的に異なる画像が相互にほぼ独立したハッシュ値となり、視覚的に類似する画像が同一のハッシュ値となるように、ディジタル画像を表すハッシュ値を計算するステップ、
前記ハッシュ値を前記ディジタル画像との関連で記憶するステップ、
前記ハッシュ値を一部に使用して前記ディジタル画像に透かしを入れ、透かし入り画像を生成するステップ、
その後、ネットワークを介して前記透かし入り画像を配信するステップ、
前記ネットワーク上のリモートサイトから画像を収集するステップ、
前記リモートサイトから収集した前記画像のハッシュ値を計算するステップ、
前記収集した画像の前記ハッシュ値を、前記記憶したハッシュ値と比較するステップ、および
前記ハッシュ値が合致する場合は、前記収集した画像を前記ディジタル画像の海賊版として識別するステップを含むことを特徴とする方法。
【請求項１９】
コンピュータ実装されるハッシング方法であって、
ディジタル画像を表すハッシュ値を計算するステップ、および
前記ハッシュ値を一部に使用して導出した透かしによって前記ディジタル画像に透かしを入れるステップを含むことを特徴とする方法。
【請求項２０】
ディジタル画像を処理するためのシステムであって、
視覚的に異なる画像が相互にほぼ独立したハッシュ値となり、視覚的に類似する画像が同一のハッシュ値となるように、ディジタル画像を表すハッシュ値を計算するための画像ハッシングユニットと、
前記ハッシュ値を保持するための記憶域とを備えることを特徴とするシステム。
【請求項２１】
ディジタル画像を処理するためのシステムであって、
視覚的に異なる画像が相互にほぼ独立したハッシュ値となり、視覚的に類似する画像が同一のハッシュ値となるように、ディジタル画像を表すハッシュ値を計算するための画像ハッシングユニットと、
前記ハッシュ値を一部に使用して前記ディジタル画像に透かしを入れ、透かし入り画像を生成するための透かしエンコーダとを備えることを特徴とするシステム。
【請求項２２】
前記画像を画像変換物に変換する手段と、
前記画像変換物を、複数のピクセルに関するピクセルデータをそれぞれが含む複数のタイルにランダムに分割する手段と、
前記各タイルにつき前記ピクセルデータを平均化して、対応するタイル平均値を生成する手段と、
前記タイル平均値に部分的に基づいて、異なる複数の量子化レベルを有する指数分布を生成する手段と、
前記各タイル平均値を前記量子化レベルのうちの１つにランダムに丸めて、丸めた値を生成する手段と、
前記丸めた値の合成値をハッシュする手段とを備えることを特徴とするディジタル画像ハッシュシステム。
【請求項２３】
コンピュータ実行可能命令を有するコンピュータ可読媒体であって、プロセッサ上で実行されたとき、
視覚的に異なる画像が相互にほぼ独立したハッシュ値となり、視覚的に類似する画像が同一のハッシュ値となるように、ディジタル画像を表すハッシュ値を計算すること、および
前記ハッシュ値を前記ディジタル画像との関連で記憶することを、コンピュータに指示することを特徴とするコンピュータ可読媒体。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、ディジタル画像などのディジタルビットストリームをハッシュするためのシステムおよび方法に関する。本発明はさらに、ハッシング技法を用いて、ビットストリームを索引付け（ｉｎｄｅｘ）し、ビットストリーム中の著作権を保護するためのデータベースシステムおよび方法に関する。
【０００２】
（発明の背景）
ディジタル画像は、画質および伝送の容易さの点で、従来の媒体に勝る多くの利点を備える。しかし、ディジタル画像は多量のメモリ空間を消費する。インターネットの普及が絶えず増大しているなかで、ディジタル画像はウェブ体験の主力要素となっており、インターネットを介したデータ搬送の速度などの進歩やこのような画像をレンダリングするブラウザ技術の改良によって支えられている。毎日、世界中で膨大なディジタル画像がウェブサイトに追加されている。
【０００３】
画像データベースが増大するにつれて、これらを索引付けし、画像中の著作権を保護する必要性が、ますます重要になりつつある。次世代のデータベース管理ソフトウェアは、ディジタル画像を速く効率的に索引付けするための、かつこれらのディジタル画像中の著作権を保護するための解決法に対応することが必要になるであろう。
【０００４】
画像の索引付けおよび著作権保護の問題に対する有望な解決法の一つは、ハッシュ関数である。ハッシュ関数は、データベース管理、照会、暗号など多くの領域で、また多量の生データを使用するその他多くの分野で使用されている。ハッシュ関数は、構造化されていない大きな生データを、構造化された比較的短い識別子にマッピングする（識別子は「ハッシュ値」または単に「ハッシュ」とも呼ばれる）。生データに構造および順序を導入することにより、ハッシュ関数は、生データのサイズを短い識別子に激減させる。ハッシュ関数は、多くのデータ管理問題を単純化し、大きなデータベースにアクセスするのに必要な計算リソースを削減する。
【０００５】
したがって、よいハッシュ関数の属性の一つは、小さなサイズのハッシュ値を生成する能力である。大きな生データと比較して、より小さな識別子に対しては、探索およびソートをずっと効率的に行うことができる。例えば、より小さな識別子は、標準的な方法を用いてより容易にソートおよび探索することができる。したがって、ハッシングは一般に、小さなハッシュ値が使用されるほど大きな利益をもたらす。
【０００６】
残念ながら、ハッシュ値が小さくなりすぎて、多量のデータ項目を一意的に表す望ましい品質を損ない始める段階点がある。すなわち、ハッシュ値のサイズが小さくなるにつれて、異なる複数の生データが同じハッシュ値にマッピングされる可能性が増大し、これが起こることは「衝突（ｃｏｌｌｉｓｏｎ）」と呼ばれる。数学的には、各ハッシュディジットにＡ個の英字があり、ハッシュ値の長さがｌの場合、可能性あるすべてのハッシュ値の上限はＡｌである。異なる生データの数がこの上限よりも多い場合、衝突が発生することになる。
【０００７】
したがって、よいハッシュ関数のもう一つの属性は、衝突の可能性を最小限に抑えることである。ただし、ハッシュ値の長さにおいてかなりの利益が達成できる場合は、衝突に耐えるだけの妥当性があると認められることもある。したがって、ハッシュ値の長さは衝突の可能性と引換えである。よいハッシュ関数は、衝突の可能性とハッシュ値の長さとの両方を最小限に抑えるべきである。このことは、コンパイラ中のハッシュ関数と暗号アプリケーション中のメッセージ認証コード（ＭＡＣ）との両方の設計に関わる。
【０００８】
多くの種類のディジタルデータ用に、よいハッシュ関数が長く存在している。これらの関数は、よい特性を有し、よく理解されている。画像データベース管理用のハッシュ関数の概念は、非常に有用であり、データ検索および著作権保護のために画像を識別するのに使用できる可能性がある。残念ながら、よい関数が多く存在する一方、ディジタル画像は、画像が人間の観察者による評価を受けるという独特のことがあるせいで、他のディジタルデータでは経験されない独特の一連の困難を呈する。画像をわずかに刈り込んだり（ｃｒｏｐｐｉｎｇ）移動させたりしても人間の目にはそれほど違いを生じないが、ディジタル領域では、このような変化は非常に異なって表れる。したがって、従来のハッシング関数を使用すると、画像の移動バージョンは、元画像と比較して、見た目は基本的に同一であっても非常に異なるハッシュ値を生成する。別の例は、画像から線を１本削除することである。画像自体の中では、ほとんどの人はこの削除を認識しないであろうが、データ領域で見ると、ディジタルデータは大きく改変されている。
【０００９】
人間の目は、画像中のある種の変化に対していくぶん耐性がある。例えば人間の目は、画像の高周波数成分に対する感度が低周波数成分の場合よりもずっと低い。さらに、平均（すなわちＤＣ成分）は、我々の目には画像の輝度として解釈され、これは、ある範囲内で変更される可能性があり、観察者には目に見える違いが最小限しか生じない。我々の目はまた、ほとんどの画像中の小さな地理的変形を捉えることができない。
【００１０】
有利にも、人間の視覚系のこれらの特性の多くを、ディジタル画像の送達および提示に用いることができる。例えば、いくらかの画像データは損なわれるか使用されない場合があるものの、このような特性により、ＪＰＥＧのような圧縮手法で画像を圧縮してよい結果を生むことができる。今日、人間の視覚系に向けて特に調整された多くの画像復元／向上アルゴリズムが利用可能である。市販の写真編集システムは、しばしばこのようなアルゴリズムを含む。
【００１１】
同時に、人間の視覚系のこれらの特性は、不法または不道徳な目的に利用される可能性もある。例えば著作権侵害者が、向上した画像処理技法を用いて、画像を視覚的に改変せずに画像から著作権表示または埋込みの透かしを除去する恐れがある。このような悪意ある画像変更は「攻撃」と呼ばれ、データ領域で変更を生じる。残念ながら、ユーザはこれらの変更を知覚することができず、著作権侵害者が非合法なやり方でうまく無許可コピーを配布することを許してしまう。従来のハッシュ関数は、元画像と海賊コピーとが同じ画像に見えても非常に異なるハッシュ値にハッシュされるので、ほとんど役立たない。
【００１２】
したがって、人間の目に許容可能または検出不可能でありながら異なるハッシュ値にならないわずかな画像変更を可能にする、ディジタル画像用のハッシュ関数が必要とされている。画像ハッシュ関数が有用なものになるには、人間の視覚系の特性に対応し、今日のディジタル画像処理で一般的である様々な画像操作処理に耐える必要がある。よい画像ハッシュ関数は、元画像に何らかの形の攻撃が加えられても、改変された画像が元画像と比較して人間の観察者にとって妥当な類似性を有するなら、同じ固有の識別子を生成すべきである。しかし、修正された画像が視覚的に異なるか、攻撃が観察者の気に障るものである場合は、ハッシュ関数はこのような程度の変更を認識し、元画像と異なるハッシュ値を生成すべきである。
【００１３】
（発明の概要）
本発明は、人間の目に検出可能または不可能な適度の画像変更を許容しながらも、元画像と修正画像とで異なるハッシュ値を生じない形で、ディジタル画像をハッシュするためのシステムおよび方法に関する。
【００１４】
一実装形態によれば、システムが、元画像をデータベースに記憶する。画像ハッシングユニットが、個々の画像をハッシュして、画像を一意的に表すハッシュ値を生成する。画像ハッシングユニットはハッシング関数Ｈを実施するが、このハッシング関数Ｈは、画像Ｉおよび任意選択の秘密のランダムストリングを入力とし、以下の属性に従ってハッシュ値Ｘを出力する。
１．任意の画像Ｉｉに対し、画像のハッシュＨ（Ｉｉ）は、等しい長さの２進ストリング間でほぼランダムである。
２．異なる２つの画像Ｉ１とＩ２に対し、第１の画像のハッシュ値Ｈ（Ｉ１）は第２の画像のハッシュ値Ｈ（Ｉ２）からほぼ独立している。これは、Ｈ（Ｉ１）があっても、Ｈ（Ｉ１）の生成に使用された秘密鍵を知らなければＨ（Ｉ２）を予測することができないからである。
３．２つの画像Ｉ１とＩ２が視覚的に同じまたは同様である場合、第１の画像のハッシュ値Ｈ（Ｉ１）は第２の画像のハッシュ値Ｈ（Ｉ２）と等しくなるべきである。
【００１５】
ハッシュ値は、画像ハッシュテーブルに記憶され、このテーブルを介して、ハッシュがそれから計算された元画像Ｉと関連付けられる。この画像ハッシュテーブルを使用して、画像記憶域を索引付けすることができる。
【００１６】
この処理システムはまた、個々の画像に透かしを入れる透かしエンコーダを有する。透かしエンコーダは、ハッシュ値Ｘおよび秘密Ｗに基づいて透かしを計算する。両方の値を効果的に使用して、個々の画像に固有の秘密を生成する。したがって、包括的な透かし秘密が発見されたとしても、攻撃者は、画像の攻撃を成功させるにはやはり各画像のハッシュ値を必要とする。この結果、このシステムは、ＢＯＲＥ（Ｂｒｅａｋ  Ｏｎｃｅ，Ｒｕｎ  Ｅｖｅｒｙｗｈｅｒｅ、一度破られればどこにでも流入する）攻撃に耐え、したがって画像に追加の保護をもたらす。
【００１７】
透かしエンコーダは、透かしを元画像Ｉ中にエンコードして、透かし入り画像Ｉ′を生成する。このシステムは、透かし入り画像を記憶および／または配信することができる。
【００１８】
本発明の一態様によれば、このシステムは、インターネット全体を探索して海賊コピーを検出するように構成することができる。このシステムは、リモートウェブサイトから画像をランダムに収集し、同じハッシング関数Ｈを使用して画像をハッシュする。次いでシステムは、画像ハッシュを元画像のハッシュと比較する。ハッシュが合致する場合は、収集した画像は元画像のコピーであることが疑われる。
【００１９】
図面を通し、同じ要素および機能に言及するためには同じ番号を使用する。
【００２０】
（好ましい実施形態の詳細な説明）
本発明を、ディジタル画像をハッシュする技法として以下に述べる。したがって、述べるハッシュ技法は特に、人間の視覚系の特性に対応し、今日のディジタル画像処理で一般的である様々な画像操作処理に耐えるように適合されている。しかし本発明は、ディジタル画像への適用に限定したものではない。そうではなく、述べる技法は、ディジタル化されたオーディオストリームなど、サンプリングまたはディジタル化された他の媒体ストリームにも適用することができる。
【００２１】
述べるハッシュ技法は、元画像に何らかの形の攻撃が加えられても、改変された画像が元画像と比較して人間の観察者にとって妥当な類似性を有するなら、同じ固有の識別子を生成する。しかし、改変された画像が視覚的に異なるか、攻撃が観測者の気に触るものである場合は、ハッシュ関数はこのような程度の変更を認識し、元画像と異なるハッシュ値を生成する。
【００２２】
本明細書に述べる様々なシステムおよび方法によって実施されるハッシュ関数を、Ｈとして表す。画像Ｉが入力された場合、ハッシュ関数Ｈは、以下のように短い２進ストリングＸを生成する。
【００２３】
Ｈ（Ｉ）＝Ｘ
【００２４】
ハッシュ関数Ｈは、以下の属性を有する。
４．任意の画像Ｉｉに対し、画像のハッシュＨ（Ｉｉ）は、等しい長さの２進ストリング間でほぼランダムである。
５．異なる２つの画像Ｉ１とＩ２に対し、第１の画像のハッシュ値Ｈ（Ｉ１）は第２の画像のハッシュ値Ｈ（Ｉ２）からほぼ独立している。これは、Ｈ（Ｉ１）があっても、Ｈ（Ｉ１）の生成に使用された秘密鍵を知らなければＨ（Ｉ２）を予測することができないからである。
６．２つの画像Ｉ１とＩ２が視覚的に同じまたは同様である場合、第１の画像のハッシュ値Ｈ（Ｉ１）は第２の画像のハッシュ値Ｈ（Ｉ２）と等しくなるべきである。
【００２５】
第３の属性の特別なケースは、元画像が、透かしまたは著作権表示を除去する攻撃を受ける場合である。この場合、元画像ＩＯが透かしを含むように修正され、したがって透かし入り画像ＩＷＭが生成されると仮定する。属性３を用いた場合、この画像は視覚的に同一であり、したがってＨ（ＩＯ）＝Ｈ（ＩＷＭ）である。ここで、透かし入り画像にディジタル画像処理技法を用いた攻撃が加えられ、透かしが除去されて海賊画像ＩＰが生成されると仮定する。この海賊画像は、元画像ＩＯおよび透かし入り画像ＩＷＭと視覚的に同一である。この場合、ハッシュ値もまた同じであり、すなわちＨ（ＩＷＭ）＝Ｈ（ＩＰ）である。
【００２６】
以下、ハッシング関数Ｈの例示的な一実装形態についてより詳細に述べる。さらに、様々なシステムおよび方法におけるハッシング技法の例示的な実装形態についても以下に述べるが、インターネットなどのネットワークを介してディジタル画像を電子配信するためのアーキテクチャから始める。
【００２７】
システムアーキテクチャ
図１に画像配信システム２０を示すが、このシステムは、ディジタル画像を製作する、かつ／またはネットワーク２４を介してクライアント２６にディジタル画像を配信する、コンテンツプロデューサ／プロバイダ２２を有する。コンテンツプロデューサ／プロバイダ２２は、ディジタル画像を記憶するための画像記憶域３０と、配信前に画像を処理するための処理システム３２と、ネットワーク２４（例えばインターネット、ＬＡＮ、ＷＡＮなど）を介して画像を配信するための配信サーバ３４とを備える。サーバ３４はさらに、ネットワーク２４を介してコンテンツを配信する前に従来の圧縮技法および暗号化技法を用いて画像を圧縮および／または暗号化するように構成することもできる。
【００２８】
処理システム３２は、個々の画像をハッシュして画像を一意的に表すハッシュ値を生成する画像ハッシングユニット４０を備える。画像ハッシングユニット４０はハッシング関数Ｈを実施するが、この関数は、画像Ｉを入力として、前述の属性に従ってハッシュ値Ｘを出力する。ハッシュ値は、記憶域３０中の画像ハッシュテーブル４４に記憶され、このテーブル４４を介して、ハッシュがそれから計算された元画像Ｉと関連付けられる。この画像ハッシュテーブル４４を使用して、画像記憶域３０を索引付けすることができる。
【００２９】
処理システム３２はまた、個々の画像に透かしを入れるための透かしエンコーダ４２も備える。透かしは、周知の暗号技法を用いて生成されて、ディジタル画像の見た目に影響を与えることなく画像に埋め込まれるビット配列である。透かしエンコーダ４２は、ハッシュ値Ｘを受け取り、ハッシュ値Ｘおよび秘密Ｗに部分的に基づいて透かしを計算する。透かしエンコーダ４２は、元画像Ｉ中に透かしをエンコードして、透かし入り画像Ｉ′を生成する。システム３２は、透かし入り画像Ｉ′を画像記憶域３０に記憶することもでき、かつ／またはネットワーク２４を介してクライアント２６に配信されるように配信サーバ３４に渡すこともできる。
【００３０】
ハッシュ値Ｘに基づいて透かしを計算することの利点は、画像ごとのセキュリティが追加されることである。通常は、透かし秘密Ｗに基づく単一の透かしが、記憶域３０中のすべての画像に包括的に加えられる。対照的に、画像ハッシュユニットは、各画像につき別個の異なるハッシュ値Ｘを生成する。次いで、透かしエンコーダ４２は、これらの値を透かし秘密Ｗと共に使用して、個々の画像に固有の秘密を効果的に生成する。したがって、透かし秘密が発見されたとしても、攻撃者は、画像の攻撃を成功させるにはやはり各画像のハッシュ値を必要とする。この結果、このシステムは、ＢＯＲＥ（一度破られればどこにでも流入する）攻撃に耐え、したがって画像に追加の保護をもたらす。
【００３１】
画像ハッシングユニット４０および透かしエンコーダ４２は、ソフトウェアまたはファームウェア中に実装できることに留意されたい。これらのコンポーネントは、処理システムの一部として構築してもよく、他のアプリケーションまたはオペレーティングシステムに組み込んでもよく、別個のスタンドアロンモジュールとして形成してもよい。コンテンツプロデューサ／プロバイダ２２は、ディジタル画像を記憶、処理、および配信するように構成された１つまたは複数のサーバコンピュータを含めて、多くの形で実装することができる。
【００３２】
クライアント２６には、プロセッサ５０、メモリ５２、および１つまたは複数の媒体出力装置５４が備わる。プロセッサ５０は、画像を圧縮する、データを暗号化解除する、および／または制御（サイズ、回転など）を加えるツールなど、様々なディジタル画像処理ツールを実行する。メモリ５２は、Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎから出ているＷｉｎｄｏｗｓ（登録商標）ブランドのオペレーティングシステムなど、プロセッサ上で実行されるオペレーティングシステム５６を記憶する。クライアント２６は、コンピュータ、ハンドヘルド娯楽デバイス、セットトップボックス、テレビジョンなどを含めた多くの様々な方法で具体化することができる。
【００３３】
オペレーティングシステム５６は、あるいはクライアントマシン上の信頼できるいずれかのソフトウェアまたはハードウェアは、ディジタル画像中の透かしを検出するためのクライアント側透かし検出器５８を実装することができる。透かしがある場合は、そのコンテンツが原版であり再生することができるとの確信がクライアントにもたらされる。透かしがない場合は、画像が元画像の海賊コピーであることを示す。オペレーティングシステム５６および／またはプロセッサ５０は、コンテンツプロデューサ／プロバイダ（または著作権所有者）から課される何らかの規則を施行するように構成することもできる。例えば、オペレーティングシステムおよび／またはプロセッサは、透かしのない偽画像またはコピー画像を受け入れないように構成することができる。
【００３４】
画像ハッシュユニット
図２に、画像ハッシュユニット４０をより詳細に示す。画像ハッシュユニット４０は、ランダム線形コーダ７０、画像変換器７２、タイル生成および平均化モジュール７８、ランダム化丸めモジュール７６、中間ハッシングモジュール７８、およびエラー訂正モジュール８０を備える。これらのコンポーネントは、その全部または一部をファームウェアまたはハードウェア中に実装することもできるが、ソフトウェア中に実装することが好ましい。
【００３５】
ランダム線形コーダ７０は、ランダム線形コードＣを選択する。これは後でエラー訂正モジュールによる処理で使用される。この選択は初期化中に一度行われ、線形コードＣはすべての画像に使用される。線形コードＣは選択可能な３つのパラメータｎ′、ｋ′、ｄ′を有するが、ｎ′はランダムストリングの長さを表し、ｋ′は元のメッセージの長さを表し、ｋ′はハミング距離を表す。線形コードＣは以下の属性を有する。
【００３６】
Ｃ＝｛Ｂ：ＡＢ＝０ｍｏｄ２｝
【００３７】
上式で、Ａは、ｍ′×ｎ′の行列（ｍ′はｎ′、ｋ′、ｄ′から計算される）であり、各エントリは値のセット｛０，１｝からランダムに選択される。Ｂは、ｎ′×１の行列であり、これは擬似乱数生成器によって生成されるｎ′ビットの配列を含む。例として、パラメータのセット｛ｎ′，ｋ′，ｄ′｝は（３２，１５，５）に等しい。
【００３８】
画像変換器７２は、元画像Ｉを受け取り、変換関数ｆを使用して画像の変換を計算するものであり、ｆ＝（ｆ１，ｆ２．．．，ｆｎ）である。変換器７２は、フーリエ変換、ウェーブレット変換、ＤＣＴ（離散コサイン変換）変換など、多くの従来型変換のうちの１つを用いることができる。例示的な一実装形態として、画像変換器７２は、ウェーブレット変換を用いて画像を３つのサブバンドレベルに圧縮解除する。すなわち、コアースサブバンド（ｃｏａｒｓｅ ｓｕｂａｎｄ）、高−低サブバンド、および低−高サブバンドである。
【００３９】
タイル生成および平均化モジュール７４は、画像変換画像を複数のタイルｔにランダムに分割する。各タイルは画像中の複数のピクセルに関するデータを含む。タイルを構築するための可能な２つの技法は、（１）重なり合わない矩形タイルの形成、および（２）重なり合う矩形タイルの生成である。
【００４０】
図３に、重なり合わないタイルを形成するプロセスを示す。画像変換物９０がある場合、タイル生成モジュール７４は、底辺の３分の１と３分の２の間のどこかで点Ｐ１をランダムに選択し、画像変換物９０を横に並んだ矩形に分割する。次いでモジュール７４は、高さの３分の１と３分の２の間のどこかで点Ｑ１をランダムに選択し、左側の矩形を分割する。このとき、画像をほぼ等しい部分に分割する任意の適した配分を用いることができる。同様に、モジュール７４は、高さの３分の１と３分の２の間のどこかで点Ｑ２をランダムに選択し、右側の矩形を分割する。このプロセスを、所定数のタイルが生成されるまで各サブ矩形に対して繰り返す。
【００４１】
図４に、重なり合うタイルを形成するプロセスを示す。画像変換物９０がある場合、タイル生成モジュール７４は、所定数のタイルが生成されるまで、空間全体にわたって一連の矩形をランダムに描く。
【００４２】
ウェーブレット変換を用いる継続中の例示的な実装形態では、コアース、低−高、および高−低の各サブバンドが、ランダムなサイズの小さな６４個の矩形に分割される。コアースサブバンドは、図３の重なり合わないプロセスを用いて分割され、高および高−高サブバンドは、図４の重なり合うプロセスを用いて分割される。これにより、１つの画像につき１９２個のタイルが生成される。
【００４３】
タイル生成の後、タイル生成および平均化モジュール７４は、各タイルｔの平均値を計算する。ウェーブレット変換を用いる継続中の例では、変換される画像のタイルがピクセルｇ１，ｇ２，．．．，ｇＮに関するデータを有すると仮定する。タイル生成および平均化モジュール７４は、以下のように各タイルｔについて平均値μを生成する。
【００４４】
【数１】
2004526340.tif 000003
【００４５】
高および高−高サブバンドでは、平均値は０である場合がある。これらの場合、平均値の代わりに以下のように分散が計算される。
【００４６】
【数２】
2004526340.tif 000004
【００４７】
コアースサブバンドでは、モジュール７４は、タイル平均値の絶対値に基づいて、タイル平均値を異なる８つ（例示的な値）のレベルに量子化する。コアースサブバンドの場合の最大値は２０４０（すなわち２５５＊８）であり、この値を８つに分割して、異なる８つの量子化レベルを生み出す。６４個のランダムなタイルおよびそれらの組合せについて、合計１２６個の値が計算される。
【００４８】
高−低および低−高サブバンドに関しては、平均値が０であることが保証された場合、分散が計算されて、異なるほぼ８つのレベルに値が含まれるように指数分布によって適合される。画像の移動によってタイルの端が除かれる／含まれることからくる影響を低減するために、タイルの周りでウィンドウ関数を使用して端の影響を低減する。
【００４９】
タイル生成および平均化モジュール７４は、画像中のｔ個のタイルについての平均値を有する平均値ベクトルμ＝（μ１，μ２，．．．，μｔ）を出力する。
【００５０】
図２を続けて参照すると、ランダム化丸めモジュール７６が平均値ベクトルを受け取り、各サブバンドごとにすべてのタイルの分散の平均値を計算する。丸めモジュール７６は、この平均値を使用して指数分布を生み出し、この分布に基づいて、異なる８つの量子化レベルを生成する。各量子化レベルは８分の１の確率量を有し、このことは、ランダムなタイルにつき、丸めの結果が各量子化レベルにわたって一様に分布されることを意味する。量子化レベルはＡ０からＡ７で表される。丸めモジュール７６は、各タイルｔについての各平均値μｉを８つの量子化レベルのうちの１つに丸める。
【００５１】
図５に丸めプロセスを示す。平均値μｉが、量子化レベルＡ２とＡ３の間にあると仮定する。丸めモジュール７６は、２つの量子化レベルのうちの近い方、この場合はレベルＡ２の方に平均値μｉを丸めることに偏る傾向がある。ただし、丸めモジュール７６はいくらかのランダム性もまた導入して、攻撃者が丸めの結果を予測するのをより困難にする。このランダム性は、本質的に、丸めた後の結果の数学的期待値が丸められた量の元の値と等しい、コインはじき（ｃｏｉｎ ｆｌｉｐ）の戦略を課す。別の言い方をすれば、結果の数学的期待値は、丸められた値の連続関数と等しくなるべきである。また、バッファリングされる丸めの戦略を用いることもでき、この場合、所与の量（μｉ）は、最も近い数までの距離が何らかの所定の境界よりも短ければ、最も近い数Ａ２またはＡに丸められる。この結果、丸めモジュール７６は、２つの量子化レベルのうちの近い方に丸めることにわずかに偏ったコインはじきに従って、平均値μｉを２つの量子化レベルのうちの一方に向かって効果的に丸める。さらに、量子化レベルは第一に、丸めの期待値を元の値と等しくする目的で生成され、所与の量におけるどんな小さな変化も、最終的な丸め出力の期待値の小さな変化を生じることになることにも留意されたい。
【００５２】
数学的には、μｉと最も近い２つの量子化レベルＡ２およびＡ３に関係する距離パラメータを、ρで表すことにする。これにより以下の式が表される。
【００５３】
ρ＝（μｉ−Ａ２）／（Ａ３−Ａ２）；ｏｒ
【００５４】
ここで、表が出る偏りρと裏が出る偏り１−ρを有するコインをはじく。次いで、表が出た場合は、μｉをＡ３に丸める。そうでない場合は、Ａ２に丸める。距離パラメータρは、近い方の値への偏りを生成し、乱数ｒは、いくらかのランダム性をもたらして、攻撃者が結果を予測するのをより困難にする。
【００５５】
丸められた値は、ｋビットの２進ストリングｑ１，ｑ２，．．．，ｑｔにマッピングされ、各タイルｔにつきストリングは１つである。我々の継続中の例では、丸められた値は、量子化ポイントＡ０〜Ａ７を表す３ビットの２進ストリングにマッピングされる。Ａ０に丸められる値μｉは、２進ストリング「０００」にマッピングされ、Ａ１に丸められる値μｉは「００１」にマッピングされ、Ａ２に丸められる値μｉは「０１０」にマッピングされ、以下同様である。前述のように、ポイントＡ０〜Ａ７は、ランダムなタイルにつき丸めステップが一様に分布した３ビットの２進ストリングを生み出すように選択される。ｋビットの２進ストリングは、共に付加されて合成値Ｑを形成する。この値が、ランダム化丸めモジュール７６から出力される。
【００５６】
丸めサブプロセスは、画像ハッシングプロセスに対して特定の利点を提供する。丸められた値は、後でハッシュ値を計算する際に正確な平均値の代わりに使用される。このようにすれば、画像に対するハッシュ値を変更せずに、画像にわずかな修正を加えることができる。すなわち、攻撃者が、透かしの除去などの小さな変更を行う可能性があり、これにより、いくつかまたはすべてのタイルについての平均値μｉが変更される。丸めおよび後続のエラー訂正セクションなしでは、これらの変更は異なるハッシュ値を生じることになる。しかし、丸めプロセスおよびエラー訂正により、これらの変更は得られる丸め値には達せず、したがって、２つの画像に対するハッシュ値は同一のままである。
【００５７】
中間ハッシュモジュール７８は、合成値Ｑを受け取り、以下の属性を備える中間ハッシュＩＨを生成する。
１．視覚的に異なる２つの画像Ｉ１とＩ２では、中間ハッシュ値は時間の約６０％で異なる。
２．視覚的に類似する２つの画像Ｉ１とＩ２では、中間ハッシュ値は時間の約２０％を除いてすべて一致する。
【００５８】
上述の数（６０％、２０％）は、例示的な実装形態を示すものであり、ディジタル化ストリームの特性に応じて様々である可能性がある。
【００５９】
継続中の例では、中間ハッシングモジュール７８は、一次 Ｒｅｅｄ−Ｍｕｌｌｅｒ エラー訂正コードデコーダを実装している。このようなデコーダは周知であり、他のエラー訂正コードデコーダを使用することもできる（例えばＮＪＡ  ＳｌｏａｎｅおよびＭｃＷｉｌｌｉａｍｓの「Ｔｈｅｏｒｙ  ｏｆ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ」、Ｎｏｒｔｈ  Ｈｏｌｌａｎｄ参照）。ただし、Ｒｅｅｄ−Ｍｕｌｌｅｒ デコーダ（または他の適したデコーダ）は、指数擬似ノルム（ｅｘｐｏｎｅｎｔｉａｌ ｐｓｅｕｄｏ−ｎｏｒｍ）と呼ぶ距離関数を扱うように修正される。ベクトルｖ＝（ｖ１，ｖ２，．．．，ｖｌ）である場合、擬似ランダムノルムは以下のとおりである。
【００６０】
【数３】
2004526340.tif 000005
【００６１】
画像ハッシュユニット４０は、相補型エンコーダは採用せずデコーダだけを採用することに留意されたい。
【００６２】
エラー訂正モジュール８０は、中間ハッシュＩＨを受け取り、ハッシュサイズを縮小しエラー発生数を減少させる。我々の継続中の例では、エラー訂正モジュール８０は、中間ハッシュＩＨからビットのサブセットを抽出する。ビットのサブセットは、コアースサブバンドから約２分の１のビットが抽出され、２つの高周波サブバンドそれぞれから４分の１のビットが抽出されるように選択される。中間ハッシュＩＨ中には何百ものビットがあり、抽出されるビットのサブセットの数は、通常は１００未満である。
【００６３】
エラー訂正モジュール８０はさらに、サブセットから、３２ビットなど減少したビットセットを抽出する。次いで、この減少したビットセットは、リスト復号プロセスを用いて小さなリスト｛Ｘ１，Ｘ２，．．．，Ｘｒ｝に処理される。ｒは小さい。リスト復号は周知である。リスト復号に関するごく簡単な考察については、読者にはＬ．Ａ．Ｌｅｖｉｎｅの「Ｏｎｅ−Ｗａｙ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  Ｐｓｅｕｄｏ−Ｒａｎｄｏｍ  Ｇｅｎｅｒａｔｏｒｓ」、Ｃｏｍｂｉｎａｔｏｒｉｃａ７、１９８７年、３５７〜３６３ページの最終章およびＰ．Ｅｌｉａｓの「Ｐｅｒｓｏｎａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｔｏ  Ｌ．Ａ．Ｌｅｖｉｎ」、１９８８年を挙げておく。また、以下の参考文献も参照されたい。  ・Ｓｕｄａｎ，Ｍａｄｈｕ、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ３７ｔｈ  Ａｎｎｕａｌ  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、「Ｍａｘｉｍｕｍ  Ｌｉｋｅｌｉｈｏｏｄ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ  Ｓｏｌｏｍｏｎ  Ｃｏｄｅｓ」、１９９６年（この論文の、「Ｄｅｃｏｄｉｎｇ  Ｒｅｅｄ  Ｓｏｌｏｍｏｎ  Ｃｏｄｅｓ  Ｂｅｙｏｎｄ  ｔｈｅ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｏｎ  Ｂｏｕｎｄ」という題名のより新しいバージョンが、ＭＩＴコンピュータサイエンス研究所に請求することによって入手可能であり、本明細書執筆時、インターネット上の「ｈｔｔｐ：／／ｔｈｅｏｒｙ．ｌｃｓ．ｍｉｔ．ｅｄｕ／〜ｍａｄｈｕ／ｐａｐｅｒｓ／ｒｅｅｄｓｏｌｏｍｏｎ．ｐｓ」で入手可能である。）
・Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｌｅｘｉｔｙ、Ｓｐｅｃｉａｌ  ｉｓｓｕｅ  ｄｅｄｉｃａｔｅｄ  ｔｏ  Ｓｈｍｕｅｌ  Ｗｉｎｏｇｒａｄ，１３（１）、１８０〜１９３、１９９７年３月
【００６４】
このリストから、画像パラメータ／セマンティクスを用いて１ワードが選択され、最終的なハッシュ値Ｘが生成される。具体的には、最尤法を用いてワードが選択される。この例では、得られるハッシュ値は３２ビットである。ただし、この値で衝突の可能性がより高くなる場合は、プロセスを２回実行して２つの３２ビット値を生成するか、線形コードユニット７０のパラメータを増加させてより長い符号化済みメッセージを生成することにより、より長いハッシュ値を得ることができる。
【００６５】
例示的なコンテキスト
画像ハッシングユニット４０中で実施される前述の画像ハッシングプロセスは、多くの方式およびいくつかのコンテキストで用いることができる。例えば、この画像ハッシングプロセスは、大きな画像データベース用の索引付けシステムとして用いることができる。このコンテキストでは、画像ハッシュＸを索引付けテーブル４４（図１）に記憶し、画像記憶域３０中の関連画像を素早く索引付けするのに使用する。
【００６６】
別の例示的なコンテキストは、インターネット全体を警備探索して海賊コピーを検出する方法として画像ハッシングプロセスを用いることである。一般にこれは、画像をランダムに収集し、ハッシュし、画像ハッシュを元画像のハッシュと比較することによって行う。ハッシュが合致する場合は、収集した画像は元画像のコピーであることが疑われる。
【００６７】
図６に、透かし入りディジタル画像を配信し、監視によって画像ハッシュプロセスを用いてディジタル画像の海賊版を検出する詳細なプロセスを示す。このプロセスは、いくつかの態様はハードウェアおよびファームウェアを使用して実装することもできるが、主にソフトウェア中に実装される。このプロセスについて、図１を参照しながらさらに述べる。
【００６８】
ステップ１００で、コンテンツプロデューサ／プロバイダ２２の処理システム３２が、画像記憶域３０から画像を取り出し、画像に関連する画像ハッシュＸを計算する。画像ハッシュＸは、画像ハッシュテーブル４４に記憶され、元画像と関連付けられる。次いで処理システム３２は、画像ハッシュＸと、透かしを生成するための秘密鍵Ｗとを使用して、画像に透かしを入れる（ステップ１０２）。このように秘密を組み合わせることにより、透かしは、すべての画像に対して包括的ではなく各画像に固有となる。透かし入り画像は、任意選択で画像記憶域３０に記憶してもよい。
【００６９】
ステップ１０４で、配信サーバ３４が、ネットワーク２４を介してクライアント２６に透かし入り画像Ｉ′を配信する。この場合では、クライアントが、画像を攻撃して透かしを除去しようとする著作権侵害者であると仮定する（ステップ１０６）。攻撃を通して、著作権侵害者は、視覚的に同一であるか酷似するが透かしのない、画像の海賊版を作成することができる（ステップ１０８）。次いで著作権侵害者は、不法な利益のために海賊版を再配信する（ステップ１１０）。
【００７０】
標準的な監視を実施することにより、元のコンテンツプロデューサ／プロバイダ２２は、様々なウェブサイトから機械的かつランダムに画像を集める。コンテンツプロデューサ／プロバイダ２２は、機械的にスイープする際に、海賊版をその他の画像と共に収集する（ステップ１１２）。コンテンツプロデューサ／プロバイダ２２は、画像ハッシュユニット４０を使用して、収集した各画像の画像ハッシュを計算する（ステップ１１４）。次いでコンテンツプロデューサ／プロバイダ２２は、収集した画像の各画像ハッシュを、画像ハッシュテーブル４４に記憶された画像ハッシュと比較して、合致が生じるかどうかを評価する（ステップ１１６）。収集した画像の画像ハッシュが記憶済み画像ハッシュと合致する場合（すなわちステップ１１８から延びる「ｙｅｓ」の枝）は、この画像は海賊版である可能性があると検出される（ステップ１２０）。反対に、合致が生じない場合は、収集したバージョンは、元画像の複製または改変バージョンとは見なされない（ステップ１２２）。
【００７１】
結び
本発明を構造的特長および／または方法ステップに特有の言葉で述べたが、添付の特許請求の範囲に定義する本発明は、述べた具体的な特徴またはステップに必ずしも限定されないことを理解されたい。そうではなく、これらの特徴および方法は、特許請求する本発明を実施する好ましい形として開示する。
【図面の簡単な説明】
【図１】
コンテンツプロデューサ／プロバイダがディジタル画像をハッシュして透かしを入れ、続いてネットワークを介してクライアントにそれらを配信する、画像配信システムのブロック図である。
【図２】
ディジタル画像をハッシュするために図１のコンテンツプロデューサ／プロバイダにおいて実装される画像ハッシュユニットの機能ブロック図である。
【図３】
画像変換物を重なり合わない複数のタイルに分割するプロセスを示す図である。
【図４】
画像変換物を重なり合う複数のタイルに分割するプロセスを示す図である。
【図５】
タイル平均値を量子化ポイントの１つに丸めるプロセスを実証するための、量子化ポイントを示す図である。
【図６】
ネットワークを介して透かし入りディジタル画像を配信し、監視によってハッシュ比較操作を用いてディジタル画像の海賊版を検出する方法を示す流れ図である。
【図１】
2004526340.tif 000006
【図２】
2004526340.tif 000007
【図３】
2004526340.tif 000008
【図４】
2004526340.tif 000009
【図５】
2004526340.tif 000010
【図６】
2004526340.tif 000011
【国際公開パンフレット】
2004526340.tif 000012
2004526340.tif 000013
2004526340.tif 000014
2004526340.tif 000015
2004526340.tif 000016
2004526340.tif 000017
2004526340.tif 000018
2004526340.tif 000019
2004526340.tif 000020
2004526340.tif 000021
2004526340.tif 000022
2004526340.tif 000023
2004526340.tif 000024
2004526340.tif 000025
2004526340.tif 000026
2004526340.tif 000027
2004526340.tif 000028
2004526340.tif 000029
2004526340.tif 000030
2004526340.tif 000031
2004526340.tif 000032
2004526340.tif 000033
2004526340.tif 000034
2004526340.tif 000035
2004526340.tif 000036
2004526340.tif 000037
2004526340.tif 000038
2004526340.tif 000039
2004526340.tif 000040
2004526340.tif 000041
2004526340.tif 000042
2004526340.tif 000043
【国際公開パンフレット（コレクトバージョン）】
2004526340.tif 000044
2004526340.tif 000045
【国際調査報告】
2004526340.tif 000046
2004526340.tif 000047
2004526340.tif 000048