(57)【要約】【課題】意図的でない攻撃および意図的な攻撃に対して耐性のある、画像への透かし入れ方法を提供する。【解決手段】本発明の一態様による方法は、データを画像に挿入することを含み、この挿入することは、画像においてエッジを検出し、エッジと既知の空間関係を有する画像の一部を特定し、この画像の一部に変換を行って、データを画像に挿入するデータ空間を提供することを含む。本発明の別の態様によれば、画像に符号化されたデータを検出する方法は、画像においてエッジを検出し、エッジと既知の空間関係を有する画像の一部を特定し、この画像の一部に変換を行って、データを検出するためのデータ空間を提供することを含む。
2005524348.tif 000002
【特許請求の範囲】
【請求項１】
データを画像に挿入する方法であって、
前記画像（図１）のエッジを検出し４０１，１６０２、
前記エッジと既知の空間的な関係を有する前記画像の部分を識別し４０２，１６０７、
前記画像の前記部分に変換を適用して４０２，１６０７、前記データを前記画像に挿入１６０８，１７０５するデータ空間を供給する
ステップを含む方法。
【請求項２】
前記エッジを検出する前記ステップは、
照度、色および図柄を含むセットから選択された前記画像の特徴において、不連続性を検出する
ステップを含む
請求項１に記載の方法。
【請求項３】
前記エッジに隣接する、前記画像の部分を、線形セグメントに再マッピングするステップをさらに含む
請求項１に記載の方法。
【請求項４】
前記部分の画像要素８０４を、前記エッジのエッジ点の最も近い要素９０１に関係づけ、
前記画像要素と、前記エッジ点のそれぞれ関係づけられた要素との距離１２０３を判定し、
前記距離に基づいて、互いに関係する前記画像要素を再マッピング（図１３）する
ステップをさらに含む
請求項１に記載の方法。
【請求項５】
前記再マッピングすることは、
前記画像要素と、前記エッジ点のそれぞれ関係づけられた要素との線形距離を、情報距離に変換する
ステップをさらに含む
請求項４に記載の方法。
【請求項６】
電子透かし１６０８を、前記データ空間に、電子迷彩的(steganographical)に挿入するステップをさらに含む
請求項１に記載の方法。
【請求項７】
前記画像（図１）の複数のエッジ４０１を検出し１６０２、
選択基準を満足する或る前記エッジを選択し１６０３，１６０４、
前記データを、前記選択されたエッジに関係づけられた前記画像の領域に、電子迷彩的(steganographical)に符号化する１６０８
ステップをさらに含む
請求項１に記載の方法。
【請求項８】
画像中に符号化されたデータを検出する方法であって、
前記画像（図１）のエッジ４０１，１６０２を検出し、
前記エッジと既知の空間的な関係を有する前記画像の部分４０２，１６０７を識別し、
前記画像の前記部分に変換を適用して１９０２、前記データが検出された空間からデータ空間を供給する
ステップを含む方法。
【請求項９】
前記部分の画像要素８０４を、前記エッジのエッジ点の最も近い要素９０１に関係づけ、
前記画像要素と、前記エッジ点のそれぞれ関係づけられた要素との距離１２０３を判定し、
前記距離に基づいて、互いに関係する前記画像要素を再マッピング（図１３）する
ステップをさらに含む
請求項８に記載の方法。
【請求項１０】
データを画像に挿入するシステムであって、
前記画像のエッジを検出する手段１６０２，２０００と、
前記エッジと既知の空間的な関係を有する前記画像の部分を識別する手段１６０７，１７０４，２０００と、
前記画像の前記部分に変換を適用して、前記データを前記画像に挿入するためのデータ空間を供給する手段１６０７，１７０４，２０００と
を含むシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、デジタル画像を対象とし、詳細には、確実な透かし、および保護画像からの透かしの復元を対象とする。
【背景技術】
【０００２】
［発明の背景］
インターネット等の設備によって提供されるネットワーク接続機能とともに、コンピュータシステムが普及し、利用可能となったことにより、データを広く、ほとんど労力を要することなく配布する手段が、提供されている。
電子形態では、情報は、容易に複製され、ほとんど無限の数の受信者に、容易に送信されうる。
この情報は、デジタル化された画像または映像を含みうる。
デジタル化された作品は、容易に複製を多数作成されるために、基礎となる作品に著作権を主張したり、基礎となる作品が著作権の対象となるかどうかを判断したりすることは、多くの場合困難である。
【０００３】
デジタル画像の著作権保護に取り組むいくつかの技法が、提案されている。
著作権情報を画像データに組み込むことを試みる技法は、一般に、著作権情報を画像データに混在させる「透かし」として知られている。
このような情報を画像データに組み込む１つの技法は、ステガノグラフィーを使用する。
ステガノグラフィーをついては、多くが記述されており、ワールドワイドウェブ上で、以下のＵＲＬにおいて、容易に入手できる。
すなわち、http://www.jjtc.com/steganography/、http://www.stegoarchive.com/、http://www.cl.cam.ac.uk/~fapp2/publications/index.html等において容易に入手できる。
透かしを対象とした特許は、さらに多くの情報を与える。
この特許には、２００１年８月２３日に公開されたRhoadsの「Method and Apparatus for Discerning Image Distortion by Reference to Encoded Marker Signals」という発明の名称の米国特許公開第ＵＳ２００１／００１６０５１Ａ１号、１９９７年９月２日に発行されたLeightonの「Watermarking Process Resilient to Collusion Attacks」という発明の名称の米国特許第５，６６４，０１８号、２００１年３月６日に発行されたMaes等の「Embedding And Detecting a Watermark in Images」という発明の名称の米国特許第６，１９８，８３２号、および、２００１年１１月２９日に公開されたWongの「Method and Apparatus for Digital Watermarking of Images」という発明の名称の米国特許公開第ＵＳ２００１／００４６３０７Ａ１号が、含まれる。
これらのすべては、その全内容が参照により、本明細書に援用される。
【０００４】
一般に、これらの透かし技法は、透かし情報を画像データの或る部分に挿入することによって、見えない電子透かしを提供する。
この或る部分は、通常、原画像の歪みを最小にするために、画像データの最下位ビット（ＬＳＢ）である。
この場合、所定のピクセルの輝度値（intensity value）のＬＳＢが、輝度値に代わって、著作権情報を符号化ために使用される。
著作線情報を抽出するには、受信者は、指定されたピクセルのＬＳＢから情報を抽出するために、著作権情報を含んだピクセルを知って特定できなければならない。
したがって、このような透かし方式の１つの弱点は、偶然の攻撃（attack）または意図的な攻撃の双方に対して、脆弱であることである。
これは、一般に、このような技法が、画像の回転や拡大縮小等、クロッピング歪み（cropping distortion）および／またはアフィン歪み（affine distortion）のような、動作によって引き起こされた画像データの歪みの影響を受けやすいことによる。
画像のこのような歪みは、透かしの復元を困難にしたり、事実上不可能にしたりする。
【０００５】
ステガノグラフィー技法は、透かしとしての使用に加えて、作成日、作者、表題等の他の情報を画像とともに符号化して、情報を秘密送信するためにも使用される。
しかしながら、透かしと同様に、この情報は、画像の比較的軽微な歪みによって、抽出不能にされる場合がある。
【特許文献１】米国特許出願公開第２００２／０１５５０８号
【特許文献２】米国特許出願公開第２００１／０３２３１５号
【特許文献３】国際公開第０２／３３６５０号
【特許文献４】米国特許出願公開第２００２／１９１８１２号
【特許文献５】米国特許出願公開第２００１／００１６０５１号
【特許文献６】米国特許第５，６６４，０１８号
【特許文献７】米国特許第６，１９８，８３２号
【特許文献８】米国特許公開第２００１／００４６３０７号
【非特許文献１】http://www.jjtc.com/steganography/
【非特許文献２】http://www.stegoarchive.com/
【非特許文献３】http://www.cl.cam.ac.uk/~fapp2/publications/index.html
【非特許文献４】http://www.digimarc.com/support.cswater03.htm
【非特許文献５】http://www.icaen.uiowa.edu/~dip/LECTURE/PreProcessing3.html#edge for further examples.
【非特許文献６】Jitendra Malik、Serge Belongie、Thomas LeungおよびJianbo Shiの「Contour and Texture Analysis for Image Segmentation」,International Journal of Computer Vision, January 2000
【非特許文献７】K.L. BoyerおよびS. Sarkarの編集者のPerceptual Organization for Artificial Vision Systems, Academic Publishers, 2000
【非特許文献８】http://www.digimarc.com
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、この技術分野では、意図的でない攻撃および意図的な攻撃に対して耐性のあるローバストな透かしおよび／またはステガノグラフィーデータ符号化技法を提供する必要がある。
【課題を解決するための手段】
【０００７】
［発明の概要］
本発明の一態様による方法は、データを画像に挿入することを含み、この挿入することは、画像においてエッジを検出し、エッジと既知の空間関係を有する画像の一部を特定し、この画像の一部に変換を行って、データを画像に挿入するデータ空間を提供することを含む。
【０００８】
本発明の別の態様によれば、画像に符号化されたデータを検出する方法は、画像においてエッジを検出し、エッジと既知の空間関係を有する画像の一部を特定し、この画像の一部に変換を行って、データを検出するためのデータ空間を提供することを含む。
【発明を実施するための最良の形態】
【０００９】
［発明の詳細な説明］
本発明の一実施の形態は、透かしデータが埋め込まれたファイルの特定可能な特徴に、透かしを関連付けることによって、透かしデータの挿入および復元を提供する。
この特徴は、後の透かし情報を特定および抽出するための基準点である。
特に、ファイルの特徴は、通常の攻撃によるデータの歪みによる影響が、最小限で局所的であるように、選択されうる。
したがって、特徴の特定は、たとえ歪みを受けた後であっても、透かしデータの復元の基礎を提供する。
本発明の一実施の形態によれば、このような特徴は、例えば、画像内に含まれるエッジを含む。
このエッジは、特徴のいずれかの変化または特徴の変化の組み合わせによって、形成さる。
例えば、エッジは、輝度（luminance）の変化、クロミナンスの変化、図柄の変化、または、あらゆるタイプの領域セグメント化によって決定された他の画像境界の変化に基づいて、特定されうる。
透かしデータは、後にこの透かしデータを抽出するための基準点を提供するように、アンカ（anchor）として、エッジに付記されうる。
透かしデータ自体は、空間領域において、透かしデータをピクセル値に組み込むことによって、選択される１つまたは複数のエッジの近傍において、画像の周波数領域表現に透かしデータを組み込むことによって、または、それらの組み合わせによって等、さまざまな方法で、符号化されうる。
一実施の形態は、或る程度の雑音、歪みおよび／またはデータ損失に幾分耐性があり、かつ／または、それらを許容する、ローバストなさまざまの符号化／復号方式の使用を含む。
或る歪みおよび再サンプリングに耐え抜きうるこのようなデータ符号化／復号技法は、例えばDigimarcから入手できる。
これについては、例えば、http://www.digimarc.com/support.cswater03.htmを参照されたい。
【００１０】
図１は、透かし挿入前の原画像である。
この画像は、白黒の場合もあるし、カラーの場合もある。
画像は、本発明の一実施の形態に従って処理され、図２に示すように、当該画像からエッジを抽出または特定できる。
これらのエッジは、例えば、照度（illuminance）に基づいて、特定されることができ、この場合、Sobel、Roberts、Prewitt等のエッジ抽出方法で特定されうる（http://www.icaen.uiowa.edu/~dip/LECTURE/PreProcessing3.html#edge for further examples.を参照）。
さらに、クロミナンス等の他の画像境界特定属性、および／または、画像の図柄間の境界等のあらゆるタイプの領域セグメント化態様も、上記照度と組み合わせるか、または、上記照度の代わりに使用されうる（International Journal of Computer Vision, January 2000に提出されたJitendra Malik、Serge Belongie、Thomas Leung、および、Jianbo Shiの「Contour and Texture Analysis for Image Segmentation」、ならびに、K.L. BoyerおよびS. Sarkarの編集者のPerceptual Organization for Artificial Vision Systems, Academic Publishers, 2000を参照されたい）。
本発明の実施の形態は、エッジの検出において、ラプラス演算子、ガウスの平滑化、ＬＯＧ演算子、ガウス関数の差分（ＤＯＧ（Difference of Gaussian））演算子および／またはキャニーエッジ検出器（Canny edge detector）等のさまざまな２階（second order）微分演算子を利用できる。
【００１１】
エッジの組は、透かしデータの組み込みに適していないあまり望ましくないエッジを除くように処理されうる。
このようなエッジは、例えば、短いエッジおよび高度に回旋状となったエッジを含む。
【００１２】
短いエッジを除去する一方法は、設定されたしきい値または可変のしきい値よりも多い所定の個数の連続したピクセルを有しないあらゆるエッジを除去することである。
エッジ検出ルーチンが十分長いエッジを特定できない場合には、最少の個数のエッジを選択するために、適応型しきい値が使用されうる。
これに加えてまたはこれに代えて、反復プロセスが使用されて、エッジ検出プロセスの感度を上げて、より多くの、かつ／または、より長いエッジを特定できる。
【００１３】
高度に回旋状になったエッジ、曲がりくねったエッジ、および／または、より直線的なエッジとして長方形データ空間への変換が容易にサポートされないエッジも、考慮の対象から除外されうる。
回旋状になったエッジまたは回旋状になったエッジセグメントは、例えば、容認できない小さな曲率半径を有するエッジを特定し、考慮の対象から除外することによって、除去されうる。
この曲率半径は、例えば、急旋回またはエッジ方向の突然の変化に特徴的な所定のしきい値よりも小さい。
小さな半径を有するエッジの一部は、回旋の一方の側のエッジセグメントを残すように除去されうる。
エッジの一部の除去によって、残りのエッジが、あまりにも短くなると、その短いエッジも、同様に廃棄されうる。
図３は、最小の長さおよび直線性という所望の特性を有する、原画像（図２）において特定されたエッジを示している。
【００１４】
一組の容認できるエッジが特定されると、そのエッジに隣接した画像データは、そのエッジとともに空間変換されて、画像ブロックを形成できる。
本発明の一実施の形態による変換は、エッジを効果的に直線にすることによって、エッジおよび隣接する画像データを、単一次元の直線方向に変換し、エッジからの距離は、直線にされたエッジから、線形関係または非線形関係（べき関数等）で計算される。
【００１５】
図４を参照して、エッジ４０１は、エッジのいずれかの側の画素とともに特定される。
このデータは、挿入４０２に示される長方形データ空間に変換される。
変換後、エッジ４０１は、直線にされており、エッジピクセルに関連したピクセルは、対応するエッジピクセルとともに、垂直に配列されうる。
データを変換するプロセスの一実施の形態を、以下にさらに詳細に説明する。
【００１６】
図５を参照して、エッジの周囲の画像領域が変換されて、画像ブロック４０２が生成されると、図５に示すように、変換された領域に透かしを入れることができる。
透かしは、Ｄｉｇｉｍａｒｃ（www.digimarc.comを参照）等、任意の多数の方法を使用して、挿入されうる。
したがって、透かしは、ピクセル輝度データ、あるいは、かわりに、変換された領域の周波数領域表現に挿入されうる。
この後者の場合には、離散コサイン変換（ＤＣＴ）等の適切な変換が使用されて、空間表現（すなわち、位置的にアドレス指定可能な輝度データ）から周波数領域に、画像ブロックデータを変換できる。
画像の周波数領域表現は、次に、透かしデータで、ステガノグラフィーにより、符号化されうる。
ステガノグラフィーにより印を付けられた周波数表現は、逆変換を受けることによって、透かし入り画像ブロックを提供できる。
いずれの場合も、透かし入り画像ブロックが得られると、原画像のようなその元の形状を取り戻すために、空間逆変換を受けることができる。
逆変換された透かし入り画像ブロックは、次に、図６に示されるように、原画像のその元の位置６０１に挿入されうる。
最終的な透かし入り画像は、特定されたエッジのすべてまたは一部に、透かし入りデータを埋め込むことにより、生成される。
透かし入りデータの量およびエッジの長さに応じて、透かし入り情報は、画像全体にわたって複製されうるし、画像全体にわたって拡散されうることに留意されたい。
透かし入り画像は、図７に示される。
【００１７】
本発明の一実施の形態による単一のエッジを処理する方法を、図８〜図１３との関連においてさらに示す。
まず、図８を参照して、エッジ８０１は、本発明の一実施の形態に従って、適切なエッジ抽出ルーチンの後、短いエッジまたはエッジセグメント、および、回旋状エッジまたはエッジセグメントを除去することによって、特定されうる。
残りのエッジ８０１は、ヘッド端部８０２およびテール端部８０３を特定するように処理されうる。
多数のプロトコルが、実施されて、エッジのヘッド端部およびテール端部を特定できる。
このプロトコルは、例えば、画像の所定のコーナに最も近い端部を、ヘッドとして特定し、その反対側の端部をテールとすることを含む。
他の技法も、使用されうる。
この技法は、輝度値に基づいて、エッジの特定の側を、そのエッジの反対側の輝度と比較して特定し、エッジの左側および右側に対して、ヘッドおよびテールを定義することを含む。
【００１８】
エッジのヘッド端部およびテール端部が特定されると、エッジの各側の画像ピクセルが特定されることができ、画像領域を変換することによって、長方形データ空間を形成する処理が実行される。
したがって、例えば、画像ピクセル８０４は、画像ピクセル８０４に最も近いエッジ上のピクセルに関連付けられる。
この最も近いピクセルは、エッジ８０１への最小距離８０５およびそのエッジにおける対応する「接点」ピクセルを特定することによって、決定されうる。
図９を参照して、画像ピクセル８０４は、エッジ８０１の接点ピクセル９０１に関連付けられている。
次に、エッジの接点側を決定する処理が、行われうる。
これは、エッジ８０１に沿って中心の接点ピクセル９０１に隣接した前のピクセル９０２および次のピクセル９０３を特定することによって、達成されうる。
図１０から分かるように、接点ピクセル９０１と画像ピクセル８０４との間の第１の距離１００１が決定されて、一続きのピクセル９０２、９０１および９０３によって規定されたエッジに沿った方向（すなわち、ヘッド端部８０２からテール端部８０３への方向）に対して、曲線８０１の左に測定された最初の値を提供する。
逆に、エッジ８０１の右側に向かって発する図１１に示されるようなラインセグメント１１０１は、方向の変更を必要とし、ラインセグメント１００１よりも長い。
これらの測定から、画像ピクセル８０４は、接点ピクセル９０１およびエッジ８０１の左に、適切に特定される。
【００１９】
エッジからの画像ピクセルの相対的な距離は、エッジに直交する方向で表される一方、エッジを効果的に直線にする長方形データ空間を形成する処理は、単一次元で表されるように実行されうる。
図１２に示すように、Ｘ軸１２０１は、ヘッド端部８０２からテール端部８０３に向かうエッジ８０１に沿った形状および距離を通る。
エッジ８０１上の各接点ピクセル９０１と、関連付けられた画像ピクセル８０４との間の距離は、Ｙ軸１２０２に沿った距離１２０３の２乗を表す。
画像空間におけるライン距離と、長方形空間におけるデータ距離との間のこの２乗関係は、距離に関する位置的不確実性の原因となる。
これは、関係Ｙ２＝Ｙ／（Ｙ）１／２によって表される。
ここで、Ｙ２は、ラインからの変換されたＹの距離である。
これは、位置的確実性がエッジからの距離が長くなるにしたがい減少することと一致する。
すなわち、ガウス雑音を距離見積もりに追加する或る種のランダムプロセスによって、画像が歪みを受けると、位置的確実性は、距離の２乗として減少する。
例えば、歪みのない画像においてエッジから１０ピクセル離れた点は、画像の歪み後、もはや１０ピクセル離れていない。
例えば、ランダムな歪みがその点を１ピクセルだけ移動させると、エッジから２倍の２０ピクセル移動させ、予想された誤差は、２ピクセルの平方根となる。
これは、第２のセグメントの誤差が、時に、第１のセグメントの誤差をキャンセルするので、誤差の２倍よりも小さい。
したがって、本発明の一実施の形態によれば、２乗関数が追加されて、誤差が一定となる空間に、画像データを再マッピングする。
【００２０】
本発明の一実施の形態の変換は、図１３に示すように、回旋状のエッジおよび隣接する画像データを、直線表現に変換する。
ここで、Ｘ軸は、ヘッドからテールに向かうエッジに沿った距離を規定し、Ｙ軸１２０３は、エッジから画像ピクセル８０４への距離の２乗を表す。
その結果の変換は、図５に示されるような上記データ空間を生成し、このデータ空間に、透かし入りデータが、ステガノグラフィー等によって、符号化される。
図１４に示すように、符号化された透かし入りデータは、複数のエッジ１４０１〜１４０５に含まれうる。
各エッジは、同じまたは異なるデータを含む。
【００２１】
多くのエッジは、突然終了するのではなく、次第に消える傾向があるので、本発明の一実施の形態は、エッジに沿って符号化されたデータの開始と終了を信号で通知する識別子をさらに含む。
これは、符号が開始される時および終了される時を特定するために、図１５の示すヘッド端部停止マーカ１５０１やテール端部停止マーカ１５０２等の停止マーカを、エッジ内に符号化することによって、達成されうる。
停止マーカ配置の判定基準は、エッジ検出ルーチンによって提供された品質印を含むことができる。
さまざまな技法が使用されて、停止マーカを符号化でき、これらの技法は、例えば、エッジを形成するピクセルの最下位ビットに、センチネルを形成する特定の符号化列を組み込むことを含む。
【００２２】
本発明の一実施の形態による方法が、図１６のフローチャートとの関連で示される。
このフローチャートでは、ステップ１６０１において開始した後、ステップ１６０２において、エッジが画像から抽出される。
上述したように、エッジは、この場合は、画像データであるファイルの多数の特徴によって特定されうる。
この多数の特徴には、例えば、輝度の変化、クロミナンスの変化、図柄の変化等が含まれる。
固定されたエッジ抽出判定基準および感度を使用できる一方、最少の個数のエッジを特定するために、可変のしきい値を含む動的なシステムが使用されうる。
適切な一組のエッジが特定されると、ステップ１６０３は、短いエッジを除去する。
この短いエッジは、価値のあるデータ量を符号化するのに十分な情報距離を提供しないか、または、クロッピング、回転、ブレ等によって画像が歪みを受けると、特定できなくなったり失われたりするおそれがある。
ステップ１６０４において、回旋状エッジまたは回旋状エッジセグメントが、残りのエッジから、除去される。
高度に回旋状になったセグメントのみが除去される場合には、エッジの残りの部分は、短すぎるエッジを再度除去するように処理される。
エッジを除去するための回旋状の判定基準は、それ未満の曲率半径ではエッジが除去される最小の曲率半径でしきい値処理できる。
【００２３】
判定１６０５は、残りのエッジまたはその或るサブセットを反復するループの開始点を形成する。
ステップ１６０７において、各エッジの周囲の画像領域が、画像ブロックに変換されるように、ステップ１６０６において、処理が開始する。
変換プロセスは、図１８との関連で、さらに説明される。
変換が完了すると、ステップ１６０８において、領域は、任意の多数の透かし入れ方法を使用して、透かしを入れられる。
この多数の透かし入れ方法には、空間領域または周波数領域のいずれかに適用される上記ステガノグラフィー技法が含まれる。
透かし入れの際に、画像ブロックは、長方形空間から原画像空間への逆空間変換を受け、原画像に挿入される。
処理は、透かし入れが要求されるすべてのエッジを取り扱うまで続き、完了すると、ステップ１６１０で終了する。
【００２４】
透かしが、例えば、ピクセル値の擬似ランダム摂動（pseudo-random perturbation）によって、空間領域の画像を調整する場合、調整の空間位置は、エッジ変換を通じて、調整の座標を変換することにより、決定されうる。
例えば、画像に透かしを入れる一方法は、各ピクセル値の擬似ランダム摂動によって、「画像にラバースタンプを行う（rubber stamp it）」ことである。
ランダムオフセットのカーネルが生成され、これは、さまざまな位置で、画像に加えられる。
このカーネルは、画像に加えられる前に、各エッジ用に変換されうる。
【００２５】
マーキングカーネルを使用してデータを挿入する代替的な方法は、カーネル自体に対して、Ｕ，ＶからＸ，Ｙへ、逆変換を実行する。
変換されたカーネルは、原画像に適用される。
カーネルを画像空間に変換する１つの利点は、画像データの再サンプリングが回避されることである。
【００２６】
透かしを挿入する代替的な方法は、図１７のフローチャートに示される。
ステップ１６０１において開始すると、ステップ１６０２〜１６０４が、この場合も、画像からエッジを抽出し、短すぎるエッジおよび回旋状でありすぎるエッジを含む不適切なエッジを除去する。
ステップ１７０１は、空間操作カーネルを計算する。
これは、例えば、ラバースタンプ方法のランダムオフセットの座標Ｕ，Ｖを有する２次元マトリクスでありうる。
【００２７】
ステップ１７０２において、各エッジまたはその或るサブセットに透かし情報を組み込む処理が、開始される。
各エッジは、ステップ１７０３において開始して、選択され、処理される。
ステップ１７０４において、各エッジに対して、カーネルにおけるＵ，Ｖと、エッジ近傍の画像におけるＸ，Ｙと間の変換が、計算される。
１７０５において、変換されたカーネルは、エッジの周囲の画像エリアに適用される。
例えば、ランダムオフセットが、画像に加えられうる。
すべてのエッジの処理が完了すると、ステップ１６０１において、プロセスは終了する。
【００２８】
エッジの周囲のデータを、長方形データ空間へおよび長方形データ空間から、変換する方法が、図１８のフローチャートに示される。
ステップ１８０１において開始して、ステップ１８０２において、エッジの１つの端部が、ヘッドとして割り当てられ、１つの端部が、テールとして割り当てられる。
この割り当ては、例えば、照度エッジの暗い側を左として有するヘッドを選ぶことによって、行われうる。
クロミナンスエッジの場合、例えば、左の２つの色のうち、より青い色を有するヘッドが、選ばれうる。
図柄エッジの場合、より高い周波数エネルギーを有する図柄が、左として選ばれうる。
多くの異なる方法が使用されて、１つの端部をヘッドとして、１つの端部をテールとして、一貫して割り当てることができる。
あるいは、ヘッドまたはテールは、任意に、割り当てられうるが、これは、復号器に対して、或る困難さをもたらしうる。
この理由は、開始端部の指定がないと、復号器が、エッジに沿って両方の向きに、データをチェックする必要があるか、または、エッジの巡回方向が要因とならないように、コードが、鏡面対称である必要があることによる。
【００２９】
ステップ１８０３は、変換された画像の長方形データ空間を形成する。
このデータ空間は、エッジの長さに対応する長さを有しうるが、エッジよりも細かくまたは粗く、サンプリングされうる。
長方形データ空間は、任意の幅を有しうる、実際には、この幅は、長さの数分の１（４分の１等）であるように選択されうる。
幅の中央における最も左の点は、データ空間のヘッドとして、割り当てられ、最も右の点は、テールとして、割り当てられうる。
【００３０】
ステップ１８０４において、データ空間の各点の送信処理が、開始される。
本発明の一実施の形態による変換は、ステップ１８０５〜１８０７を含む。
ステップ１８０５において、データ空間のあらゆる点と、画像のあらゆる点との間の変換が、決定される。
ステップ１８０６は、幅の中央をＵ軸として有し、長さの中央をＶ軸として有するデータ空間において、一組のデカルト座標を形成する。
ステップ１８０７において、長方形空間の点Ｕ，Ｖについて、画像の対応する点Ｘ，Ｙが見つけられる。
これは、エッジの最も近い点からその対応する点までの距離がＶとなり、エッジの最も近い点のエッジのヘッドまでの、エッジに沿った経路に従った距離がＵとなるように行われる。
さらに、ステップ１８０８において、画像の任意の点Ｘ，Ｙについても、Ｕ，Ｖの対応する点が、決定されうる。
すなわち、点Ｕ，Ｖについて、画像の対応する点Ｘ，Ｙが、見つけられる。
これは、エッジの最も近い点からその点までの距離がＶとなり、エッジの最も近い点のエッジのヘッドまでの、エッジに沿った経路に従った距離がＵとなるように行われる。
この関数は、Ｕに比例してもよいし、Ｕ＝Ｘ／Ｘ２等のＵの非線形関数であってもよい。
【００３１】
データ空間の点Ｕ，Ｖと画像の点Ｘ，Ｙとの間の変換が決定された後、ステップ１８０９において、双三次補間等の任意の標準的な再サンプリング方法を使用することによって、画像ブロックが、データ空間に変換されるか、または、データ空間のカーネルが、画像座標に変換される。
すべての点の処理が完了すると、ステップ１８１０において、この方法は終了する。
【００３２】
画像からの透かしの復元は、透かしを加えるプロセスと類似している。
このプロセスの一実施の形態は、図１９に示される。
図１９に示すように、復号プロセスは、画像に透かしを符号化する方法とほぼ同じである。
一方、Ｕ，Ｖの長方形ブロックの抽出の際に、透かしデータは、符号化器によって挿入される代わりに、復号器によって抽出される。
より具体的には、透かしの読み出しまたは復元を行う方法は、ステップ１６０１において開始して、上記で詳述したようなステップ１６０２〜１７０１を含んで、隠されたデータを符号化する画像のエリアの特定および画定をするエッジを特定し、画像空間（Ｘ，Ｙ）と長方形データ空間（Ｕ，Ｖ）との間の変換を定式化する。
ステップ１９０１は、特定されたエッジの検査に使用されるループの開始点である。
特定された各エッジは、ステップ１７０３において処理され、ステップ１９０２において、エッジ近傍の画像のＸ，Ｙと、カーネルのＵ，Ｖとの間の逆変換が、計算される。
ステップ１９０３において、データが、逆カーネル変換を使用して、エッジの周囲の画像エリアから抽出される。
【００３３】
図２０は、本発明の一実施の形態によるデータ構造体の実施および保持を行うメモリ記憶プログラムのサポートおよび実行を行うことができるコンピュータシステムの図である。
このように、本発明は、広範なデータ構造体、プログラミング言語、オペレーティングシステムならびにハードウェアプラットフォームおよびシステムに適合できるが、図２０は、本発明のさまざまな実施の形態のサポートに適合したプラットフォームを備えるこのようなコンピュータシステム２０００上に示している。
このむしろ例示の汎用コンピュータシステムは、システムバス２００２に接続された中央処理装置（ＣＰＵ）２００１を含む。
ＣＰＵ２００１は、ＨＰ  ＰＡ−８５００やＩｎｔｅｌ  Ｐｅｎｔｉｕｍ（登録商標）プロセッサ等の任意の汎用ＣＰＵであってよい。
しかしながら、本発明は、ＣＰＵ２００１が本明細書で説明したような本発明の動作をサポートする限り、ＣＰＵ２００１のアーキテクチャ、例えばポインタの使用、によって限定されない。
システムバス２００２は、ランダムアクセスメモリ（ＲＡＭ）２００３に接続されている。
このＲＡＭ２００３は、ＳＲＡＭ、ＤＲＡＭまたはＳＤＲＡＭであってよい。
ＲＯＭ２００４も、システムバス２００２に接続されている。
このＲＯＭ２００４は、ＰＲＯＭ，ＥＰＲＯＭまたはＥＥＰＲＯＭであってよい。
ＲＡＭ２００３およびＲＯＭ２００４は、この技術分野において既知であるように、ユーザデータおよびシステムデータならびにプログラムを保持する。
【００３４】
システムバス２００２は、入出力（Ｉ／Ｏ）コントローラカード２００５、通信アダプタカード２０１１、ユーザインターフェースカード２００８および表示カード２００９にも接続されている。
Ｉ／Ｏカード２００５は、ハードドライブ、ＣＤドライブ、フロッピィディスクドライブ、テープドライブの１つまたは複数等の記憶デバイス２００６を、コンピュータシステムに接続する。
通信カード２０１１は、コンピュータシステム２０００をネットワーク２０１２に接続するように、適合されている。
ネットワーク２０１２は、電話網、ローカルエリアネットワーク（ＬＡＮ）および／もしくはワイドエリアネットワーク（ＷＡＮ）、イーサネット（登録商標）ネットワークならびに／またはインターネットネットワークの１つまたは複数であってよく、また、有線であってもよいし、無線であってもよい。
ユーザインターフェースカード２００８は、キーボード２０１３やポインティングデバイス２００７等のユーザ入力デバイスを、コンピュータシステム２００に接続する。
表示カード２００９は、ＣＰＵ２００１に駆動されて、表示デバイス２０１０を制御する。
【図面の簡単な説明】
【００３５】
【図１】透かし挿入前の原画像を示す図である。
【図２】エッジを特定するために処理された図１の画像を示す図である。
【図３】透かしデータの符号化に最も適していると最初に特定されたエッジの中からエッジを特定することを示す図である。
【図４】選択されたエッジに隣接する図１に示す画像の一部、および、エッジの直線化に対応する長方形データ空間への画像の対応する変換を示す図である。
【図５】変換された画像への透かしデータの挿入を示す図である。
【図６】図１の原画像への変換された画像データの組み込み戻しを示す図である。
【図７】本発明の一実施の形態に従って透かしが入れられた画像を示す図である。
【図８】画像において特定されたエッジの図である。
【図９】隣接する画像ピクセルをエッジの接点ピクセルに関連付けることを含んだエッジの図である。
【図１０】画像ピクセルの接点側の決定を示す図である。
【図１１】画像ピクセルの接点側の決定に使用されるエッジセグメントの図である。
【図１２】エッジ、および、そのエッジに対する画像データの再マッピングを提供するエッジのトラバースの図である。
【図１３】直線化されたエッジに対して再マッピングされた画像データの図である。
【図１４】画像内のデータの１つまたは２つ以上のパケットを保持するのに使用されるエッジを示す図である。
【図１５】エッジに沿って挿入された、符号化された停止マーカを含むエッジの図である。
【図１６】透かし情報を画像に挿入する方法のフローチャートである。
【図１７】透かし情報を画像に挿入する代替的な方法のフローチャートである。
【図１８】エッジの周囲の画像領域を変換して画像ブロックを形成する方法のフローチャートである。
【図１９】画像から透かし情報を復元する方法のフローチャートである。
【図２０】画像データに透かしを挿入し、かつ、画像データから透かしを復元するシステムのブロック図である。
【符号の説明】
【００３６】
４０１・・・エッジ
４０２・・・画像ブロック
６０１・・・元の位置
８０１・・・エッジ
８０２・・・ヘッド端部
８０３・・・テール端部
８０４・・・画像ピクセル
８０５・・・最小距離
９０１・・・接点ピクセル
９０２・・・接点ピクセルに隣接する前のピクセル
９０３・・・接点ピクセルに隣接する次のピクセル
１００１・・・第１の距離
１１０１・・・ラインセグメント
１２０１・・・Ｘ軸
１２０２・・・Ｙ軸
１２０３・・・Ｙ軸に沿った距離
１５０１・・・ヘッド端部停止マーカ
１５０２・・・テール端部停止マーカ
２０００・・・コンピュータシステム
２００１・・・ＣＰＵ
２００３・・・ＲＡＭ
２００４・・・ＲＯＭ
２００５・・・Ｉ／Ｏアダプタ
２００６・・・記憶デバイス
２００７・・・ポインティングデバイス２００７
２００８・・・ユーザインターフェースアダプタ
２００９・・・表示アダプタ
２０１０・・・表示デバイス
２０１１・・・通信アダプタ
２０１２・・・ネットワーク
２０１３・・・キーボード
【図１】
2005524348.tif 000003
【図２】
2005524348.tif 000004
【図３】
2005524348.tif 000005
【図４】
2005524348.tif 000006
【図５】
2005524348.tif 000007
【図６】
2005524348.tif 000008
【図７】
2005524348.tif 000009
【図８】
2005524348.tif 000010
【図９】
2005524348.tif 000011
【図１０】
2005524348.tif 000012
【図１１】
2005524348.tif 000013
【図１２】
2005524348.tif 000014
【図１３】
2005524348.tif 000015
【図１４】
2005524348.tif 000016
【図１５】
2005524348.tif 000017
【図１６】
2005524348.tif 000018
【図１７】
2005524348.tif 000019
【図１８】
2005524348.tif 000020
【図１９】
2005524348.tif 000021
【図２０】
2005524348.tif 000022
【国際調査報告】
2005524348.tif 000023
2005524348.tif 000024
2005524348.tif 000025