JPH11355547A

JPH11355547A - 幾何変換特定システム

Info

Publication number: JPH11355547A
Application number: JP10140726A
Authority: JP
Inventors: Shuichi Shimizu; 周一清水; Akio Koide; 昭夫小出
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1998-05-22
Filing date: 1998-05-22
Publication date: 1999-12-24
Also published as: US6671386B1

Abstract

(57)【要約】【課題】原画像を用いずに画像になされた幾何変換を容
易に精度よく高速に求めることのできる方法およびシス
テムを提供することである。【解決手段】本発明の２次元波パターンの埋め込みによ
る幾何補正システムの概要は、対称軸を持たない２次元
波からなるパターンの作成、２次元波からなるパターン
の実空間での埋め込み、埋め込み２次元波の抽出による
施された幾何変換の算出からなる。２次元波からなるパ
ターンの作成とは、本発明の幾何補正システムに適し
たパターンを作るための２次元波パラメータ・セットを
算出することを言う。２次元波からなるパターンの実空
間での埋め込みとは、原画像に２次元波からなるパター
ンを加えることを言う。埋め込み２次元波の抽出による
施された幾何変換の算出とは、幾何変換が施された画像
から埋め込まれた２次元波のパラメータを算出し、埋め
込んだパターンの２次元波パラメータ・セットと比較す
ることより、埋め込み画像に施された幾何変換を求める
ことを言う。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本願は、２次元波を埋め込んだ画
像が幾何変換されたとき、その画像から歪んだ２次元波
を検出し、元の２次元波との対応により、適用された幾
何変換を精度よく求める方法およびシステム、またこれ
を利用した幾何変換耐性をもつ電子透かしシステムに関
する。より詳細には、多数の２次元波を意図的に画像に
埋め込んでおくことにより、埋め込んだ２次元波の周期
の大きさと方向がどのように変換されたかの情報を算出
することで、２次元波を埋め込む前のオリジナルの原画
像を使用せずに、画像に施された幾何変換を高速に精度
よく求める方法およびシステムに関する発明である。

【０００２】

【従来の技術】従来、空間の回転が周波数空間（Fourie
r Transformed Space）の分布にも回転を起こすこと自
体は知られいる。E.De CastroとC. Morandi (IEEE Tran
s.Pattern Analysis and Machine Intelligent, Vol.PA
MI-9, No.5, pp.700-703, 1987)は回転された画像の幾
何補正（geometrical registration）にこの原理を適用
しているが、意図的に２次元波を埋め込むことをせず、
原画像と回転された画像との周波数空間での相関を最大
にする回転角を繰り返し探索する方法を用いている。従
って、オリジナルの原画像を用いることにより初めて、
施された線形変換が求められる。USP 5636292 "STEGANO
GRAPHY METHODS EMPLYING EMBEDDED CALIBRATION DATA"
では、２次元パターン自体に多重ビットの同定機能を埋
め込む電子透かしの方法が記載されている。この発明で
は電子透かしとして埋め込む情報（informationsigna
l）と、画像になされた変形を割り出す情報（informati
on signal）が一体化されており、複数の２次元波から
なるパターンの埋め込みに当たって、埋め込みパターン
が対称軸を少なくとも一つは持つ。しかしながら、この
ような対称性があると、パターン抽出の際の線形変換が
複数の解をもつこととなり、幾何変換の特定が完全には
できない。また USP 5636292では、２次元波パターンの
埋め込まれた画像を、別の空間（周波数空間）に変換し
てフィルターをかけ、再度、実空間に戻す方法を取る。
しかしながら、このような方法では、不可視性や画質の
劣化の制御が容易ではない。著作権保護のために埋め込
む電子透かしは、それを取り除く操作に対しての対抗策
を必要とする。電子透かしを取り除く操作として、切抜
き、回転、拡大縮小、非等方拡大縮小などの幾何変換
（geometrical transformation）がある。しかしなが
ら、従来の技術はこれらの電子透かしを含む画像になさ
れた幾何変換を正確に高速に特定し、補正するための単
独の手段を提供していない。さらに製造工程で、製造物
の精密な位置制御を必要とする場合、外的環境の変化に
より、製造物が幾何変形を受けた時の位置制御を可能と
する手段を従来の技術は提供しない。

【０００３】

【発明が解決しようとする課題】従って、本発明が解決
しようとする課題は、オリジナルの原画像を用いずに画
像になされた幾何変換を容易に精度よく高速に求めるこ
とのできる方法およびシステムを提供することである。
また別の課題は、不可視性や画質の劣化の制御が容易
な、画像へ２次元波を埋め込む方法及びシステムを提供
することである。また別の課題は、電子透かしを含む画
像に対してなされた幾何変換を、精度よく高速に求める
ことのできる方法およびシステムを提供することであ
る。また別の課題は、電子透かし画像への、切抜き、回
転、拡大縮小、非等方拡大縮小などが行われても、原画
像に施された幾何変換を検出することのできる方法およ
びシステムを提供することである。また別の課題は、精
密な位置補正を行う必要のある製造物になされた幾何変
換を読み取り、該製造物の的確な位置制御を行う方法及
びシステムを提供することである。

【０００４】

【課題を解決するための手段】本発明の２次元波パター
ンの埋め込みによる幾何補正システムの概要は、対称軸
を持たない２次元波からなるパターンの作成、２次元波
からなるパターンの実空間での埋め込み、埋め込み２次
元波の抽出による施された幾何変換の算出からなる。２
次元波からなるパターンの作成とは、本発明の幾何補
正システムに適したパターンを作るための２次元波パラ
メータ・セットを算出することを言う。２次元波からな
るパターンの実空間での埋め込みとは、原画像に２次元
波からなるパターンを加えることを言う。埋め込み２次
元波の抽出による施された幾何変換の算出とは、幾何変
換が施された画像から埋め込まれた２次元波のパラメー
タを算出し、埋め込んだパターンの２次元波パラメータ
・セットと比較することより、埋め込み画像に施された
幾何変換を求めることを言う。

【０００５】図１に本発明の幾何補正システムのブロッ
ク図を示す。まずブロック１３０で、記憶装置に記憶さ
れた原画像１２０へステップ１１０で作成され記憶され
た、対称軸を持たない２次元波を実空間で埋め込む。こ
のようにして作成された埋め込み画像１４０が、何らか
の要因より、幾何変換され、変換画像１５０となる。こ
こで何らかの要因とはたとえば人為的に変換された幾何
変換や、スキャナー、ファックスなどにより機械的な幾
何変換等を含む。ブロック１６０で画像に埋め込まれた
２次元波を抽出し、予め定義された２次元波と、抽出さ
れた２次元波を比較し、この比較結果により、画像にな
された、拡大縮小率、回転角、反転、非等方拡大縮小
率、平行移動量を含む、線形座標変換を算出する。画像
になされた幾何変換を特定するだけであればここまでの
処理で終わる。されに幾何補正を行うには、特定された
幾何変換を用いて幾何補正（逆変換）をすることによ
り、幾何変換データ１７０が作成される。

【０００６】対称軸を持たない２次元波を意図的に埋め
込み抽出する方法は、原画像を用いずに画像になされた
幾何変換を容易に精度よく高速に求めることができる。
また実空間で埋め込むので不可視性や画質の劣化の制御
が容易になる。さらに、電子透かしと独立に単独に機能
するので、電子透かし画像への、切抜き、回転、拡大縮
小、非等方拡大縮小などが行われても、原画像に施され
た幾何変換を正確に高速に検出することが可能になる。

【０００７】

【発明の実施の形態】本発明の基本となる実施例を説明
する。 ☆基本原理画像の座標を u = (x,y) としたとき、多数の２次元波
からなるパターンとは、次式をいう。 P(u) = Σ_m r_m exp( 2 πｉ ( w_m ^T u + q_m ) ) 式(１)

【０００８】ここで、各画素点は x および y が整数値
上にあるとする。また、 w_m = (w_xm,w _ym) は２次元波の
波数ベクトルで、r_m は２次元波の振幅、 q_m はその位
相を表す。 i は虚数単位、Tは転置ベクトルおよび転置
行列を作る作用素である。肩に転置作用素Tなければベ
クトルは縦ベクトルとし、あれば横ベクトルとする。従
って、w_m ^Tu は転置作用素Tの定義に従い、内積 w_m ^Tu =
w_xm x + w_ym y を表す。画素値は実数なので、埋め込
みパターンも実数でなければならず、必ず、逆向きの波
がある。便宜上、mに対する逆向きの波を -m と記す
と、以下の関係が成立する。 w_-m= - w_m, r_-m= r_m, q_-m = q_m 式（２）

【０００９】これにより、式 (１) は、次にように書き
換えることができる。 P(u) = Σ_m r_m cos {2 p( w_m ^Tu + q_m) ) } 式（３)

【００１０】点 u の線形変換は次のようになる。 u' = A u + b 式（４）

【００１１】ここで点 u' に移動する幾何変換を画像 I
(u) に施したとき、新しい画素点 u'での画素値 I'
(u') は次式で与えられる。 I' (u') = I (A^-1(u'-b) ) = I (u) 式（５）

【００１２】これにともない、変換された画像での埋め
込みパターン P'(u)はつぎのようになる。 P'(u') = P(A^-1(u'-b) ) 式（６）

【００１３】ここで Bを次のように置く。 B = (A^-1 )^T 式（７）

【００１４】式（６）の P に式（１）を代入すると、
変換された画像では、元の２次元波数w_mの代わりに w'_m
=B w_mについて和をとり、次のように表せる。 r'_m = r(w_m), q'_m = q_m - (Bw_m)^T b 式（８）

【００１５】すなわち、変換された画像においても埋め
込まれたパターンは依然として２次元波の集まりからな
る。従って、埋め込んだパターンの２次元波の波数ベ
クトルを w_mとし、変換を施した画像から抽出されたパ
ターンの２次元波の波数ベクトルを w'_m とすると、次
のようになる。 w'_m = B w_m 式（９）

【００１６】行列 B を求めることにより、式（７）の
逆変換を用いて座標変換 A を求めることができる。こ
れが本発明の基本原理−その１である。 A = (B^-1 )^T 式（１０）

【００１７】なお、下記に述べる本発明では、埋め込ま
れた２次元波の波数ベクトルw'_mを抽出するのに、離散
的Fourier Transformation （DFT)を用いる。この変換
は、次式のようにかける。 G(k) = Σ_u exp( - 2 πｉ k^T u / N ) P(u) 式（１１）

【００１８】ここで、Nは DFT を行うときの領域の幅
で、和をとる u = (x,y) は次式のように、一辺が N 個
の画素点からなる正方形の領域上を走ることになる。 x = x₀, x₀+1, x₀+2, ..., x₀+N - 1, y = y₀, y₀+1, y₀+2, ..., y₀+N - 1 式（１２）

【００１９】G(k) はk =(k_x,k_y)の各k_x と k_y とに関
し周期 N の関数になるので、本明細では、説明の便宜
上、次式のような原点を含む格子点（整数値の組）の領
域でG(k)を計算するものとする。 k_x = -N/2+1, -N/2+2, ... 0, 1, 2, ..., N/2 k_y = -N/2+1, -N/2+2, ... 0, 1, 2, ..., N/2 式（１３）

【００２０】DFTで各２次元波がどのように変換される
かを見るために、式（１１）のP(u) に２次元波 exp( 2
πｉ ( w^T u ) ) を代入すると、次式のようになる。 | G(k) | = |sin (Np(w_x -k_x/N)) /sin(p(w_x - k_x/N))||sin (Np(w_y - k_y/N)) /sin(p(w_y - k_y/N))| 式（１４）

【００２１】式（１４）は、波数ベクトル w = (w_x,w_y)
の各成分が必ずしも整数をDFTの周期 N で割った値で
なくても、DFTによって、近いk_x/N、k_y/Nで検出できる
ことを意味する。G(k)がkに関して最大となるのは、kの
値がNwに近いときである。 wが格子点上にあるとき、す
はわち、k=Nwとなるkが存在すれば、そこで最大値G(k)=
N²をとり、他の格子点での値はゼロである。 G(k)の最
大値が最も小さくなるのはwが格子点の対角線上にくる
とき、すなわち、(k_x+1/2,k_y+1/2)=Nwとなるkが存在す
るときは、そこで最大値G(k)=(1/sin(p/2N))²、約 0.4N
² をとり、格子点が離れるとその差の逆数に比例して緩
やかに減衰する。また、式(11)のDFTでwindowing funct
ion (S. M. Kay and S. L. Marple, Jr. , "Spectrum
analysis-amodern perspective," Proc. IEEE, vol. 6
9, no. 11, pp. 1380-1419, 1981)を使うことで、すな
わち、式(11)に周辺の影響を補正する比重を挿入する
ことで、格子点kが波数ベクトルNwから離れたときにG
(k)が大きく減衰するように改良できる。従って、DFT
の幅 Nを２のべき乗にとってFast Fourier Transformat
ion （FFT）(*)を使用しても、回転、拡大縮小しても、
DFTを行ったとき、埋め込んだパターンの各２次元波の
近似値が格子点上にピークとしてG(k)に現れる。これ
が、本発明の基本原理−その２である。

【００２２】☆２次元波からなる埋め込みパターンの作
成２次元波からなる埋め込みパターンの作成では、人間
の目で検知しにくく、かつ、プログラムからは波数ベク
トルの抽出や幾何変換の行列の算出がしやすいよう、
式（１）及び（３）で定義されるパターンの２次元波パ
ラメータ・セット、波数ベクトルw_mを選択し、振幅 r_m
及び位相 q_mの値の設定する。図４に示すように、非対
称な分布の波数ベクトルw_mを疑似ランダムに生成し、２
次元波の振幅 r_mを人間の目に検知しにくい大きさに設
定し、埋め込みパターンの絶対値 |P(u)| の格子点上で
の最大値が小さくなるよう、２次元波の位相q_mを最適化
する。この手続きを計算機上で自動的に行うことによ
り、鍵に応じた埋め込みパターンを作成し、２次元波か
らなる埋め込みパターンを所有者同定マークやカテゴリ
特定として使用できる。ここで、波数ベクトルの分布が
対称性 S を持つということは、埋め込みパターンに含
まれる任意の波数のベクトル w_m に対し、次式を満足す
る m' が必ず存在することをいう。 w_m' = S w_m 式（１５）

【００２３】もし、かかる対称性 S があると、行列 B
が式（９）を満たせば、埋め込んだ波数ベクトルと抽
出された波数ベクトルとの対応関係を変更することによ
り、行列 BS も式（９）を満たすようになる。埋め込
みパターンが実数であるため、式（２）の示す、原点対
称は避けられず、行列 B と -B との二つの解を持たざ
るを得ないが、それ以外の解は、波数ベクトルの分布に
おいて意図的に対称性を破ることにより、避けることが
できる。この対称性の破れは、波数ベクトルの部分集合
についても成立すべきである。なぜならば、２次元波が
元の画像にある周期性の影に隠れたたり、また、幾何変
換以外の画像処理で壊されたりして、必ずしもすべての
２次元波の波数ベクトルが画像から抽出できるわけでな
いからである。それゆえ、ランダム性の導入によって対
称性を破る波数ベクトル分布を作成する手法が有効であ
る。このランダム性は、回転したとき、偶然、多くの点
がX軸上、あるいはY軸上に揃うことを防ぐためにも重要
である。具体的には、下記のようにしてランダムな波数
ベクトル分布を作成する。

【００２４】［全域ランダム分布作成法］図５に示す
ように、波数ベクトルの範囲、例えば、原点を含む正方
領域を定めておき、ランダムに波数ベクトルを発生さ
せ、次に、それぞれの波数ベクトルが所定の距離以上離
れるために、近い波数ベクトルの組があれば互いに反対
の向きに波数ベクトルを移動させる操作を、すべての組
について所定の距離だけ離れるまでつづける。図５で、
波数ベクトルの個数から、ステップ５２０で擬似乱数を
用いてランダムに波数ベクトルを生成し、ステップ５４
０で、波数ベクトルが互いに離れているかどうかを判断
し、もし離れていない場合は、ステップ５３０で、それ
ぞれの波数ベクトルが所定の距離以上離れるために、近
い波数ベクトルの組があれば互いに反対の向きに波数ベ
クトルを移動させる。このようにしてすべての組につい
て所定の距離だけ離れるまでつづけることにより、ステ
ップ５５０において、非対称な分布の波数ベクトルがで
きる。

【００２５】［細胞ランダム分布作成法］図６に示す
ように、ステップ６１０で各波数ベクトルが1個入る領
域を事前に定めておき、その領域で波数ベクトルをステ
ップ６２０でランダムに発生させ、次に、ステップ６４
０で隣り合った領域の波数ベクトル組が所定の距離より
近い場合、ステップ６３０で互いに反対の向きに移動さ
せ、各、隣り合った領域の波数ベクトルの組が所定の距
離以上の離れるようにする。これによりステップ６５０
で非対称な分布の波数ベクトルができる。各波数ベクト
ルが入る領域を最初から離しておけば、所定の距離以上
の離れるようにするステップ６３０を省略できる。図９
は、細胞ランダム分布作成法で作成された波数ベクトル
の分布の例である。中央が原点で、128個の波数ベクト
ルがランダムに分布している。

【００２６】［螺旋ランダム分布作成法］図７に示す
ように、ステップ７２０で波数ベクトルを一定の側に順
次、原点からの距離が増加するよう、ランダムに発生さ
せる。ステップ７４０及びステップ７３０で直前の波数
ベクトルからの距離、原点からの距離の増加分に範囲を
持たせ、ランダムに波数ベクトルを発生させる。図１１
が螺旋ランダム分布作成法で作成した波数ベクトル分布
の例である。中央が原点で、86個の波数ベクトルがラン
ダムに分布している。

【００２７】埋め込んだパターンが人間の目に見えない
ようにするには、式（１）及び（３）の r_m は小さい値
にする。 r_m は一定値にとるか、ほぼ一定値にとるか、
または、原点に近いほど緩やかに大きくなるようにす
る。原点に近いほど大きな値に取るのは、自然画像にD
FTをかけた場合、小さい波数ほど、大きなスペクトルパ
ワーをもつことが多いからである。埋め込んだ画像か
ら２次元波を抽出するとき、２次元波の振幅 r_m のとり
うる範囲が限定されていることを利用する。２次元波の
波数ベクトル w_m 、振幅 r_m が定まっても、２次元波の
位相 q_m によって、式（１）及び（３）のP(u)の大きさ
は変わる。整数ｕ上での |P(u)| の最大値が最小になる
よう、その位相q_mに関して最適化する。

【００２８】図８は、１２８個の２次元波からなるパタ
ーンの実空間での表示例である。人間の目に見えるよう
濃淡を強調してある。多数の２次元波からなるパターン
は、実空間では、見えたとしてもこのようにノイズのよ
うにしか見えない。図９は、そのパターンをDFT(Digita
l Fourier Transformation）した例である。画面中央が
原点で、白い点が個々の２次元波である。図１０は、同
じパターンを30度回転したものにDFTを施した像であ
る。画面中央が原点で、DFTの像も回転していることが
わかる。画像に施された回転、拡大縮小などの幾何変換
がDFT像にも反映される。

【００２９】☆埋め込み図１２は２次元からなるパターンを画像に埋め込む手順
を示す。埋め込みは実空間で画質の劣化を制御しながら
行う。２次元波の集まりからなるパターンP(u)を配列上
で事前に計算しておき、人間の目に検知できない、ある
いは、気にならない強度で、その配列の値を画像の各画
素値に加えたり引いたりする。他の手法による埋め込み
パターンと共存を図る場合は、この２次元波からなるパ
ターンは他の埋め込みによって壊れることがほとんどな
いので先に埋め込み、壊れやすい他の電子透かしの埋め
込みを後にすれば良い。２次元波の集まりからなるパタ
ーンは、式（３）を画像の各点で計算し直接画像に埋め
込んで良いが、埋め込みパターン P(u) に周期性をもた
せることにより、その周期をサイズとする配列上でのみ
事前に計算しておき、その値を画像上の各画素点に加え
るほうが計算の負荷が軽い。正の整数 N_x とN_yに対し
て、各波数ベクトルw_m = (w_xm,w_ym)をその格子点にと
る。 w_xm = k_xm / N_x, w_ym = k_ym / N_y 式（１６）

【００３０】ここでk_xm と k_ym とは整数である。この
とき、P(u) はｘ軸方向に周期 N_x 、y軸方向に周期N_yと
なる。よって、横N_x 、縦N_y の配列上でP(u)を計算し、
その値を繰り返して使用する。式(16)の代わりに、次式
のようにすることもできる。 w_xm = ( 2 k_xm+1 ) / 2 N_x w_ym = ( 2 k_ym+1 ) / 2 N_y 式（１７）

【００３１】この場合、P(u) はｘ軸方向に周期２N
_x 、y軸方向に周期２N_yとなるが、その半分の周期 N
_x 、N_y に対し、符号を反転する、すなわち、n=(N_x,N_y)
とすると、次式のようになる。 P(u+n) = -P(u) 式（１８）

【００３２】この場合も、横 N_x 、縦 N_y の配列上でP
(u)を計算し、その値を必要に応じて符号反転しながら
繰り返して使用する。そして、各画素にパターン P(u)
を加えるとき、その画素点の周りの画像の性質に応じて
弱く埋め込む。すなわち、次式のように、α の値を画
素値が滑らかに変わる領域では小さくとる。 I'(u) = I(u) + α P(u) where 0 <= α <= 1 式（１９）

【００３３】☆２次元波の抽出と線形座標変換の算出２
次元波の集まりからなるパターンが埋め込まれた画像か
ら、その画像に施された線形座標変換を求める手続き
は、図１３に示すように、次の手順からなる。＜１＞ステップ１３２０において、画像にDFTを適用
し、得られた像G(k)に画像処理を行い、２次元波の波数
ベクトルの集合 {w'_m} を抽出する。＜２＞ステップ１３３０において、抽出した波数ベク
トルと埋め込んだ波数ベクトルとの対応の一部を初期設
定（対応を与える）する。＜３＞ステップ１３４０において、設定された対応を
もとに二乗平均誤差を表す次式を最小にする行列 B を
求める。 d(B) = (1/M) Σ_m | w'_m - B w_m |² 式（２０）

【００３４】または、二乗平均誤差を表す次式を最小に
する行列 B を求めてもよい。 d(B) = (1/Σ_m r_m) Σ_m r_m | w'_m - B w_m |² 式（２１）

【００３５】ここでMは波数ベクトルの数である。式
（２１）で比重 r_m が同じければ、式（２０）と等価で
ある。＜４＞ステップ１３５０で、d(B) が所定の値より大
きいとき、波数ベクトルの対応を再設定し、ステップ１
３４０に戻る。さもなければ、対応づける抽出した波数
ベクトルと埋め込んだ波数ベクトルの対応の数を増加
し、ステップ１３４０に戻る。すべての対応付けが終わ
り、d(B) が所定の値より小さいとき、ステップ１３６
０において次式より幾何変換行列である、線形座標変換
A を求める。 A = (B^-1 )^T 式（２２）

【００３６】得られた線形座標変換 A には A または -
A の不定性がある。さらに電子透かしの応用では、本発
明の手法以外で埋め込んだ情報を取り出す場合に、式
（４）の平行移動量ｂを求める必要が生じる。すなわ
ち、次の手続きが必要となる。＜５＞ステップ１３７０で、抽出された２次元波の位
相を使って平行移動量ｂを求めるか、または／及び、別
の手法で埋め込んだ情報の検出信頼度を最大にする平行
移動量ｂを探索するかする。以下＜１＞から＜５＞の手順をより詳細に説明する。

【００３７】＜１＞２次元波の抽出図１４は２次元波からなるパターンの埋め込まれた画像
のDFT像である。図９の２次元波パターンのDFT像との差
は、原画像によるものである。図１４の示唆するよう
に、埋め込んだ２次元波を抽出するには、変換像のDFT
像に適切な処理を行う必要がある。図１５は、本発明で
の変換画像から埋め込んだ２次元波の波数ベクトルの集
合 {w'} を抽出する手順を示す。（１）まずステップ１５２０で、画像の複数の領域でDF
TまたはFFTを行い、得られた変換像 G(k)のpower |G
(k)| を足し合わせる。（２）次にステップ１５３０で、足し合わせによって得
られた画像 G_sum(k)から、周りより多い値の大きい点を
選び出す。（３）さらにステップ１５４０で、選び出した点につい
て、その点の値からから周りの点の最大値を引き、その
値がゼロ以下であれば、棄却し、正であれば、その値
で、選び出された点を大きい順にならべる。（４）最後にステップ１５５０で、選ばれた点が原点か
または原点に非常に近い場合や、その点でのG_sum(k)が
残りの点での G_sum(k)よりはるかに大きい場合、それら
の点を取り除き、ステップ１５３０での大きい順に埋め
込んだ２次元波の数を超えない個数の波数ベクトルを抽
出する。

【００３８】基本原理で述べたように、画像値が実数で
ある条件から、DFTの結果得られた像のpower |G(k)|、
また、埋め込み波数ベクトルの集合、抽出の波数ベクト
ルの集合は原点対称である。従って、この原点対称性を
使うことで、ステップ１５２０の変換像のpower の足し
合わせや、ステップ１５３０の探索範囲は半分で良い。
また、埋め込み波数ベクトルの集合、抽出の波数ベクト
ルの集合の記憶領域の保存も半分ですむ。ステップ１５
２０でのDFTの領域の幅は埋め込みでP(u)の配列や周期
の幅と同じである必要はない。DFT領域の幅Nが大きいほ
うが抽出において原画像との分離や式（９）の行列Bの
算出精度が上がる。DFTでwindowing functionを使うと
より鮮明な像を得ることができる。ステップ１５３０で
得られる周りの点とステップ１５４０で得られる周りの
点と同一である必要はない。ステップ１５３０は局所最
大である点を選択するためであり、ステップ１５４０
は、他より大きいという事実が偶然ではなく、意図的な
ものであることを周りより飛びぬけて大きいことによ
り、確認するためのものである。基本原理その２で式
（１４）で示したように、波数ベクトルがDFT上での格
子点(w_x =k_x/N, w_y = k_y/N)上でないと、連続した格子
点に像として現れる。従って、ステップ１５４０で得ら
れる周りの点とは、直接隣接点を除いた近傍の点とした
方が結果が良い。

【００３９】＜２＞埋め込んだ２次元波と抽出した２
次波との対応の設定抽出された波数ベクトルの数をM'、埋め込んだ波数ベ
クトル数をMとすると、可能な対応関係は、 M! /(M-M')
! 通りとなる。さらに、抽出された波数ベクトルには原
画に起因する偽者ものも含まれるので、この組み合わせ
はもっと増加する。従って、抽出した波数ベクトルと埋
め込んだ埋め込んだ波数ベクトルとの対応を効率的に設
定することが重要となる。もし、画像に施される幾何的
処理が回転、反転、拡大縮小だけであれば、変換Bによ
って波数ベクトルの大小の順序が変わらない。しか
し、波数ベクトルの大小関係の保存は近似的なものにす
ぎない。一方、変換行列 Bで対応付けられ波数ベクトル
間には、幾何変換の際に生じる誤差を無視すれば、次の
関係は正確に成り立つ。 det (w'_m w'n ) = β det ( w_m wn ) 式（２３）

【００４０】ここで det() は行列式を表し、すなわ
ち、det (ab)= a_xb_y -a_yb_x で、βは β=det(B) なる
定数である。この関係は次式により明らかである。 det ( w'_m w'n ) = det( B w_m B wn ) = det( B ( w_m wn) ) = det(B) det( w_m wn ) 式（２４）

【００４１】式（２３）の関係を使って、図１６または
図１７に示すように、次のように、効率的に対応関係を
決めていくことができる。いずれの方法でも、埋め込み
波数ベクトルの集合 {w}、抽出波数ベクトルの集合
{w'}は原点対称の半分が記憶域に保存されているものと
する。

【００４２】［大小関係法］図１６に示すように、埋め
込み波数ベクトルの集合{w}、抽出された波数ベクトル
の集合{w'}について、それぞれ、その波数ベクトルの大
小の順に並べ、その間の対応関係を次第に拡大してい
く。まずステップ１６２０で抽出された波数ベクトルの
集合、埋め込んだ波数ベクトル集合をその大きさの順に
並べる。次にステップ１６３０で、抽出波数ベクトルの
集合{w'}から、並べた順に、1つ取り出し、w_m'をとす
る。このとき、行列式 det (w'_m-2 w'_m) または det
(w'_m-1 w'_m)の絶対値が大きいほうに対して、行列式の
値が正となるよう、w_m' の符号を選択する。そしてステ
ップ１６４０で、対応付けられていない埋め込み波数ベ
クトルの集合{w}から、並べた順に、1つ取り、w_mとす
る。このとき、ステップ１６３０での符号の選択に対応
し、行列式 det (w_m-2 w_m) または det (w_m-1 w_m)が正
になるようにw_m'の符号を選択する。そしてステップ１
６５０で、対応が与えられたm個の波数ベクトルに対
し、次節で述べる方法により、最小の二乗誤差の平均
（式（２０）または式（２１））を求め、それが充分に
小さいかをテストする。充分に小さければ、ステップ１
６７０へ進む。もし小さくなければ、ステップ１６６０
で、試されていない別の埋め込み波数べクトルを取り出
し、w_mとし、ステップ１６４０と同様にw_mの符号をw_m'
の符号に合わせて調整し、再度ステップ１６５０に進
む。別の埋め込み波数べクトルがもう残っていなけれ
ば、w_m'が偽者の抽出波数ベクトルとして、対応関係か
ら除外する。ステップ１６７０で、すべての抽出波数ベ
クトルが、取り出されたとき、対応付けられた波数ベク
トルの数が所定の個数に達していれば、処理はステップ
１６８０で終了する。満たないとき、事前に決めておい
た試行回数だけ、 w₁'、 w₂'の選択を変えて、処理はス
テップ１６０に戻る。

【００４３】［分解法］まず線形結合の式は以下の通り
である。 w_m = C_m1 w₁ + C_m2 w₂ 式（２５）

【００４４】分解とは、二つの波数ベクトルで他の波数
ベクトルを、上式の係数 (C_m1，C_m2 )で表すことをい
う。この係数は前述の行列式を使って、次のように求ま
る。 C_m1 = det(w_m w₂)/det(w₁ w₂) C_m2 = det(w₁ w_m)/det(w₁ w₂) 式（２６）

【００４５】従って、対応する埋め込み波数ベクトルと
抽出波数ベクトルは同じ分解係数を持つ。図１７に、分
解係数を利用した対応関係の作成法を示す。まずステッ
プ１７２０で、最初に、抽出された波数ベクトルの集合
{w'}と埋め込んだ波数ベクトル集合{w}について、それ
ぞれ、det(w'_m w'n)、det(w_m wn)を計算しておく。次に
ステップ１７３０で、抽出された波数ベクトルの集合
{w'}と埋め込んだ波数ベクトル集合{w}とから、ステッ
プ１７２０で求めた行列式の絶対値が大きい順に、それ
ぞれ、二つの波数ベクトル{w'₁ , w'₂}と{w₁ , w₂}と
を選択する。行列式が正になるよう、w'₂とw₂の符号を
とる。そしてステップ１７４０で、選択された{w'₁ ,
w'₂}と{w₁ , w₂}とを使って、抽出された波数ベクトル
w'と埋め込んだ波数ベクトルwとを式（２６）を用いて
分解する。そしてステップ１７５０で、分解係数を比較
し、抽出された波数ベクトルw'_mと埋め込んだ波数ベク
トルw_mとの対応関係を定める。例えば、各埋め込み波数
ベクトルをその分解係数がもっとも近い抽出波数ベクト
ルに対応づけ、このとき、複数の埋め込み波数ベクトル
が同一の抽出波数ベクトルに対応付けられたときには、
分解係数が最も近いものを対応として一つ選択する。次
にステップ１７６０で、得られた波数ベクトルの対応関
係を二乗誤差を用いて確認し、確認された対応関係の数
を数える。例えば、対応の組を順次、増加させながら、
次節で述べる方法により、最小の二乗誤差の平均（式
（２０）または式（２１））を求め、それが大きければ
棄却し、小さければ、有効な対応関係として残す。最後
にステップ１７７０で、有効な対応関係の数が所定の個
数に達しており、二乗誤差の平均も小さければ、処理は
ステップ１７８０で終了する。もし満たないときは、事
前に決めておいた試行回数だけ、 {w'₁ , w'₂}と{w₁ ,
w₂}の選択を変えて、ステップ１７３０に戻る。

【００４６】＜３＞、＜４＞２次元波の対応関係から
線形座標変換の算出画像から抽出された波数ベクトルは、回転・拡大などで
の画像のリサンプリングや抽出におけるDFTの量子化幅
のため、次式のようにランダムノイズを含んでいるかも
しれない。 w'_m = B w_m + random noise 式（２７）

【００４７】従って、式（２０）または（２１）で与え
たように、埋め込んだ波数ベクトルに線形変換したもの
と抽出された波数ベクトルとの二乗誤差の平均または合
計を最小化する線形変換 Bにより、式（９）の B を求
める。式（１１）のDFTの領域の幅をNとすると量子化
幅は1/N、従って、リサンプリングによる影響よりDFTの
量子化幅が大きいとすると、仮定された対応関係の棄却
の条件は、Bについて最小化した二乗誤差の平均が次式
を満たす時である。 d(B) > (1/N)² 式（２８）

【００４８】式（２０）は式（２１）の特別な場合に当
たるので、式で（２１）に対し、最小化する行列Bの算
出手続きを記述する。行列SとVを次式とする。 S = Σ_m r_m w_m w_m ^T 式（２９） V = Σ_m r_m w'_m w_m ^T 式（３０）

【００４９】この時、式(２１)を最小化する線形変換
B は、次式でで求めることができる。 B = VS^-1 式（３１）

【００５０】ここで、 b a^T は転置作用素Tの定義に従
い、次の成分を有する行列である。 b_x a_x b_x a_y b_y a_x b_y a_y 上式の証明は省略する。

【００５１】＜５＞平行移動量の算出一旦、変換行列 B が求まると、平行移動量 b は、２次
元波からなるパターンの埋め込み・抽出によっても、ま
た、電子透かしの抽出を位置をずらして総あたりで試す
ことによっても求めることができる。

【００５２】☆２次元波からなるパターンの位相を用い
る方法抽出された２次元波の位相と埋め込んだ２次元波の位相
との関係、式（８）をもとに平行移動量 b を求めるこ
とができる。ただし、画像からの直接的な測定量はDFT
像 G(u) なので、位相q'_m には 2p の整数倍だけの不定
性が残る。また、個々の位相q'_mは埋め込みの際に原画
像に起因する２次元波によってみだされている。従っ
て、次に示す手順で平行移動量b を求める。（１）対応の確定した抽出２次元波の位相q'_mとその信
頼度p_mをDFT像から求める。信頼度は周りの点からの値
の差などを使用する。（２）平行移動量 b に関して次式をを最小化する。 E(b) = Σ_m p_m { 1 - cos(2p (q_m -q'_m - w'_m ^T b) ) } = Σ_m p_m 2 sin2 (p (q_m -q'_m - w'_m ^T b)) 式（３２）

【００５３】E(b) は複素数面での位相のずれの比重付
き和にあたる。計算負荷を軽くするには、式(３２)を近
似して簡単にして計算を加速するか、または、信頼度の
高い少数の２次元波の位相を用いて式（３２）で候補を
絞り、その候補の周りですべての確定２次元波の位相を
用いて式（３２）を最小化する。

【００５４】☆信号とノイズとの分離最大による方法２次元波からなるパターンの利用で変換行列Bが求めら
れ、平行移動を除き、画像の回転、拡大縮小などの幾何
変換が補正されたとする。平行移動量 b は、２次元波
の位相を使わずに、電子透かしの抽出を位置をずらして
総あたりで試すことによっても求めることができる。こ
の場合の要点は、総あたりの計算量を減らすために表を
使うことと、最善の平行移動量か否かを判定する基準が
重要となる。今、多重ビット情報を埋め込む電子透かし
が、切り取り耐性のために、同じパターンで画像上に周
期的に埋め込まれたとする。また、ブロック（矩形領
域）の画素値を入力とし鍵で制御される演算を機構があ
り、その出力の和の符号で１ビット検出するとする。こ
のとき、次の手順で最前の平行移動量を求める。（１）周期で囲まれる領域の各画素点について、それ
を端点とする矩形領域について先に演算機構に入力し、
その値 f(u,k) を求めて表にのせておく。ここで、uは
画素点の位置、kは鍵で定まるブロックパターンとす
る。（２）周期で囲まれる領域の各画素点について、それを
鍵の基準点とし、次式を手順（１）で作成された表をも
とに計算し、最大になる画素点を鍵の基準点とする。 S_u M(f(u,k_u)) 式（３３）

【００５５】u はビットに対応する表上の値である。M
は信号とノイズを分離する関数で次式で表される。 M(x) = log (|x| + a) 式（３４）

【００５６】または、式（３４）の近似関数である。も
し、鍵の基準点選択が正しければビットは f(u,k_u) の
符号で与えられる。ビットの値は検出装置は知らないの
で、正か負かはわからないが、ノイズの期待値ゼロか
ら離れた値でビット情報が埋め込まれているはずであ
る。従ってゼロとの差異を強調する関数が有効である。
M(x) = x² より M(x) = |x| が有効で、M(x) = |x|
より M(x) = log (|x|+ a) が有効である。パラメー
タ a は x=0で特異点にならないよう加えてある。対数
関数は計算負荷が大きいので、ゼロとの差異を強調する
単純増加関数、例えば次に関数を近似関数として使用す
る。 M(x) = - 1/ (|x| + a) 式（３５）

【００５７】または M(x) = - 1/ (|x|² + a) 式（３６）

【００５８】

【実施例】以下、図面を参照して、本発明の２次元波埋
め込み、画像の幾何変換特定、幾何補正、電子透かしを
行うハードウェアの１実施例を説明する。図１８には、
本発明において使用されるシステムのハードウェア構成
の一実施例を示す概観図が示されている。システム１０
０は、中央処理装置（ＣＰＵ）１とメモリ４とを含んで
いる。ＣＰＵ１とメモリ４は、バス２を介して、補助記
憶装置としてのハードディスク装置１３（またはＭＯ、
ＣＤ−ＲＯＭ２３、ＤＶＤ等の記憶媒体駆動装置）とＩ
ＤＥコントローラ２５を介して接続してある。同様にＣ
ＰＵ１とメモリ４は、バス２を介して、補助記憶装置と
してのハードディスク装置３０（またはＭＯ２８、ＣＤ
−ＲＯＭ２９、ＤＶＤ３１等の記憶媒体駆動装置）とＳ
ＣＳＩコントローラ２７を介して接続してある。フロッ
ピーディスク装置２０はフロッピーディスクコントロー
ラ１９を介してバス２へ接続されている。好ましくは、
埋め込む対象となる画像および作成された２次元波はハ
ードディスク装置、ＭＯ２８、ＣＤ−ＲＯＭ２９、ＤＶ
Ｄ３１等の記憶媒体駆動装置に記憶され、適宜メモリ４
などにロードされ処理される。埋め込まれた画像、幾何
補正された画像も好ましくは上記記憶媒体駆動装置に記
憶される。

【００５９】フロッピーディスク装置２０には、フロッ
ピーディスクが挿入され、このフロッピーディスク等や
ハードディスク装置１３（またはＭＯ、ＣＤ−ＲＯＭ、
ＤＶＤ等の記憶媒体）、ＲＯＭ１４には、オペレーティ
ングシステムと協働してＣＰＵ等に命令を与え、本発明
を実施するためのコンピュータ・プログラムのコード若
しくはデータを記録することができ、メモリ４にロード
されることによって実行される。このコンピュータ・プ
ログラムのコードは圧縮し、または、複数に分割して、
複数の媒体に記録することもできる。システム１００は
更に、ユーザ・インターフェース・ハードウェアを備
え、入力をするためのポインティング・デバイス（マウ
ス、ジョイスティック等）７またはキーボード６や、視
覚データをユーザに提示するためのディスプレイ１２を
有することができる。また、パラレルポート１６を介し
てプリンタを接続することや、シリアルポート１５を介
してモデムを接続することが可能である。このシステム
１００は、シリアルポート１５およびモデムまたは通信
アダプタ１８(イーサネットやトークンリング・カード)
等を介してネットワークに接続し、他のコンピュータ等
と通信を行うことが可能である。またシリアルポート１
５若しくはパラレルポート１６に、遠隔送受信機器を接
続して、赤外線若しくは電波により画像データの送受信
を行うことも可能である。原画を外部から取り込む場合
は、シリアルポート１５、はパラレルポート１６、もし
くはＳＣＳＩコントローラ２７に接続された画像入力装
置（デジタルカメラ、スキャナ、デジタルビデオカメラ
等）から画像を取り込む。そのほかフロッピーディス
ク、ＣＤ−ＲＯＭなどの記録媒体を用いてもよいし、本
システムのユーザ・インターフェース・ハードウェアで
作成しても構わない。

【００６０】スピーカ２３は、オーディオ・コントロー
ラ２１によってＤ／Ａ（デジタル／アナログ変換）変換
された音声信号を、アンプ２２を介して受領し、音声と
して出力する。また、オーディオ・コントローラ２１
は、マイクロフォン２４から受領した音声情報をＡ／Ｄ
（アナログ／デジタル）変換し、システム外部の音声情
報をシステムにとり込むことを可能にしている。このよ
うに、本発明のシステムは、通常のパーソナルコンピュ
ータ（ＰＣ）やワークステーション、ノートブックＰ
Ｃ、パームトップＰＣ、ネットワークコンピュータ、コ
ンピュータを内蔵したテレビ等の各種家電製品、通信機
能を有するゲーム機、電話、ＦＡＸ、携帯電話、ＰＨ
Ｓ、電子手帳、等を含む通信機能有する通信端末、また
は、これらの組合せによって実施可能であることを容易
に理解できるであろう。ただし、これらの構成要素は例
示であり、その全ての構成要素が本発明の必須の構成要
素となるわけではない。

【００６１】図２に本発明の幾何補正システムを従来の
電子透かしと組み合わせた、幾何変換に耐性を持つ電子
透かしシステムを示す。まずブロック２１０で予め定義
され作成された２次元波からなるパターンを、原画像２
２０に、ブロック２３０で埋め込んだ後、ブロック２４
０で電子透かしを埋め込む。このようにしてできた埋め
込み画像２５０に、何らかの要因により幾何変換が施さ
れたものが変換画像２６０である。ブロック２７０では
この変換画像２６０を入力として、埋め込み２次元波の
抽出を行う。これにより施された幾何変換を算出し、ブ
ロック２８０でその画像に幾何補正を行うことにより原
画像の再生を行う。その後、ブロック２９０で電子透か
しを検出する。このように本発明の対称軸を持たない２
次元波を意図的に埋め込み抽出する方法は、電子透かし
と独立に単独に機能するので、電子透かし画像への、切
抜き、回転、拡大縮小、非等方拡大縮小などが行われて
も、原画像に施された幾何変換を正確に高速に検出する
ことが可能になる。つまり電子透かし技術に非常に親和
性の高い幾何補正が可能となる。

【００６２】図３は、本発明を印刷物の向きの制御への
応用を示した実施例である。まずブロック３１０で２次
元波パターンを作成する。これをブロック３３０で向き
を制御したい原画像３２０に埋め込む。ブロック３４０
で、この２次元波パターンが埋め込まれた画像を印刷し
ておく。印刷物が回転、移動した後、ブロック３７０で
デジタルビデオカメラ等の画像読み取り装置の出力から
埋め込んだ２次元波の抽出を行い、幾何変換を算出す
る。それに基づきブロック３８０で印刷物を所望の方向
に回転、移動し、その向き、位置を制御する。デジタル
ビデオカメラを、CCDセンサー等に置き換え、実時間で
画像から２次元波を検出することにより、工場でのベル
トコンベア上の物の向き、位置などを自動制御すること
も可能である。この場合、印刷物は２次元波が埋め込ま
れた画像が貼られた３次元物体でも構わない。また物体
そのものに本発明の２次元波を埋め込むことも可能であ
る。例えば、製造工程で精密な位置補正を行う必要のあ
る製造物(物体)の表面に直接、本発明の２次元波を埋め
込む。位置制御を行う場合はデジタルカメラ等の画像か
ら幾何変換を算出し、所望の位置制御を正確に行うこと
ができる。この場合の位置制御とは、回転、拡大縮小、
非等方拡大縮小、平行移動等に対応できることに注意さ
れたい。２次元波が埋め込まれた物体が、製造工程で外
的環境（温度、湿度など）の変化により、幾何変形を受
けた場合にもその物体の位置制御が可能になる。

【００６３】

【発明の効果】本発明により、原画像を用いずに画像に
なされた幾何変換を容易に精度よく高速に求めることが
できる。また不可視性や画質の劣化の制御が容易な２次
元波を埋め込み方法及びシステムが提供される。さらに
電子透かしを含む画像に対してなされた切抜き、回転、
拡大縮小、非等方拡大縮小などを含む幾何変換を、精度
よく高速に求めることのできる方法およびシステムが提
供される。本発明の２次元波を埋め込まれた電子透かし
画像が、流通過程で人為的に幾何変換を施されたり、た
とえばスキャナー、ファックスなどにより機械的な幾何
変換を受けたとしても、その幾何変換を特定し、これを
補正することにより電子透かし画像の再生が可能とな
る。すなわちデジタルコンテンツの流通を促進するため
の著作権保護等への技術的な手段を提供することができ
る。

【００６４】

【図面の簡単な説明】

【図１】２次元波パターンの埋め込みによる幾何補正シ
ステム

【図２】幾何補正システムの電子透かしへの応用

【図３】幾何補正システムの印刷物の向きの制御への応
用

【図４】２次元波からなるパターンの作成

【図５】全域ランダム分布作成法

【図６】細胞ランダム分布作成法

【図７】螺旋ランダム分布作成法

【図８】細胞ランダム分布の作成例の実空間での表示

【図９】細胞ランダム分布の作成例のDFT像

【図１０】画像の回転に伴う２次元波パターンのDFT像
での回転

【図１１】螺旋ランダム分布の作成例のDFT像

【図１２】２次元波パターンの埋め込みの手順

【図１３】２次元波パターンから幾何補正情報抽出の手
順

【図１４】２次元波パターンの埋め込まれた画像のDFT
像

【図１５】画像から波数ベクトルの抽出手順

【図１６】埋め込まれた波数ベクトルと抽出された波数
ベクトルの対応関係の作成−１

【図１７】埋め込まれた波数ベクトルと抽出された波数
ベクトルの対応関係の作成−２

【図１８】本発明の２次元波埋め込み、画像の幾何変換
特定、電子透かし、幾何補正、位置制御を行うハードウ
ェアの１実施例である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者小出昭夫神奈川県大和市下鶴間1623番地14 日本アイ・ビー・エム株式会社東京基礎研究所内

Claims

【特許請求の範囲】

【請求項１】画像になされた幾何変換を特定するための
２次元波を画像に埋め込む、２次元波埋め込みシステム
であって、（１）画像を記憶装置に記憶する手段と、
（２）対称性を持たない２次元波の集まりからなるパタ
ーンを記憶装置に記憶する手段と、（３）前記記憶装置
に記憶された画像に、前記パターンを実空間で埋め込む
手段と、を含むことを特徴とする、画像への２次元波埋
め込みシステム。
【請求項２】電子透かし埋め込みシステムであって、
（１）画像を記憶装置に記憶する手段と、（２）対称性
を持たない２次元波の集まりからなるパターンを記憶装
置に記憶する手段と、（３）前記記憶装置に記憶された
画像に、前記パターンを実空間で埋め込む手段と、
（４）前記パターンの埋め込まれた画像にさらに電子透
かしを埋め込む手段と、を含むことを特徴とする、電子
透かし埋め込みシステム。
【請求項３】位置補正パターン印刷システムであって、
（１）画像を記憶装置に記憶する手段と、（２）対称性
を持たない２次元波の集まりからなるパターンを記憶装
置に記憶する手段と、（３）前記記憶装置に記憶された
画像に、前記パターンを実空間で埋め込む手段と、
（４）前記パターンの埋め込まれた画像を印刷する手段
と、を含むことを特徴とする、位置補正パターン埋め込
みシステム。
【請求項４】位置補正パターン埋込みシステムであっ
て、（１）物体の画像を記憶装置に記憶する手段と、
（２）対称性を持たない２次元波の集まりからなるパタ
ーンを記憶装置に記憶する手段と、（３）前記記憶装置
に記憶された画像に、前記パターンを実空間で埋め込む
手段と、（４）前記パターンの埋め込まれた画像を物体
に埋め込む手段と、を含むことを特徴とする、位置補正
パターン埋め込みシステム。
【請求項５】前記パターンを埋め込む手段（３）が、前
記パターンを実空間で画質を劣化させないよう制御しな
がら埋め込む手段である、請求項１乃至４の何れかに記
載のシステム。
【請求項６】２次元波が埋め込まれた画像から、前記２
次元波を抽出することにより、画像になされた幾何変換
を特定する、幾何変換特定システムであって、（１）記
憶装置に記憶された画像から、画像に埋め込まれた２次
元波を抽出する手段と、（２）予め定義された対称性を
もたない２次元波と、前記抽出された２次元波を比較す
る手段と、（３）前記比較の結果により、画像になされ
た、拡大縮小率、回転角、反転、非等方拡大縮小率、平
行移動量を含む、線形座標変換を算出する手段と、を含
むことを特徴とする、幾何変換特定システム。
【請求項７】２次元波が埋め込まれた画像から、前記２
次元波を抽出することにより、画像になされた幾何変換
を特定し、補正する幾何補正システムであって、（１）
記憶装置に記憶された画像から、画像に埋め込まれた２
次元波を抽出する手段と、（２）予め定義された対称性
をもたない２次元波と、前記抽出された２次元波を比較
する手段と、（３）前記比較の結果により、画像になさ
れた、拡大縮小率、回転角、反転、非等方拡大縮小率、
平行移動量を含む、線形座標変換を算出する手段と、
（４）前記算出された線形座標変換を用いて、前記画像
の幾何補正を行う手段と、を含むことを特徴とする、幾
何補正システム。
【請求項８】電子透かし抽出システムであって、（１）
記憶装置に記憶された画像から、画像に埋め込まれた２
次元波を抽出する手段と、（２）予め定義された対称性
をもたない２次元波と、前記抽出された２次元波を比較
する手段と、（３）前記比較の結果により、画像になさ
れた、拡大縮小率、回転角、反転、非等方拡大縮小率、
平行移動量を含む、線形座標変換を算出する手段と、
（４）前記算出された線形座標変換を用いて、前記画像
の幾何補正を行う手段と、（５）前記幾何補正の行われ
た画像から電子透かしを抽出する手段と、を含むことを
特徴とする、電子透かし抽出システム。
【請求項９】位置制御システムであって、（１）記憶装
置に記憶された物体の画像から、画像に埋め込まれた２
次元波を抽出する手段と、（２）予め定義された対称性
をもたない２次元波と、前記抽出された２次元波を比較
する手段と、（３）前記比較の結果により、画像になさ
れた、拡大縮小率、回転角、反転、非等方拡大縮小率、
平行移動量を含む、線形座標変換を算出する手段と、
（４）前記算出された線形座標変換を用いて、前記画像
を有する物体の位置制御を行う手段と、を含むことを特
徴とする、位置制御システム。
【請求項１０】前記画像になされた線型座標変換を算出
する手段（３）が、拡大縮小率、回転角、反転、非等方
拡大縮小率、平行移動量を含む線型座標変換を同時に算
出することを特徴とする、請求項６乃至９の何れかに記
載のシステム。
【請求項１１】画像になされた幾何変換を特定するため
の２次元波を画像に埋め込む、２次元波埋め込み方法で
あって、（１）画像を記憶装置に記憶する段階と、
（２）対称性を持たない２次元波の集まりからなるパタ
ーンを記憶装置に記憶する段階と、（３）前記記憶装置
に記憶された画像に、前記パターンを実空間で埋め込む
段階と、を含むことを特徴とする、画像への２次元波埋
め込み方法。
【請求項１２】電子透かし埋め込み方法であって、
（１）画像を記憶装置に記憶する段階と、（２）対称性
を持たない２次元波の集まりからなるパターンを記憶装
置に記憶する段階と、（３）前記記憶装置に記憶された
画像に、前記パターンを実空間で埋め込む段階と、
（４）前記パターンの埋め込まれた画像にさらに電子透
かしを埋め込む段階と、を含むことを特徴とする、電子
透かし埋め込み方法。
【請求項１３】２次元波が埋め込まれた画像から、前記
２次元波を抽出することにより、画像になされた幾何変
換を特定する、幾何変換特定方法であって、（１）記憶
装置に記憶された画像から、画像に埋め込まれた２次元
波を抽出する段階と、（２）予め定義された対称性をも
たない２次元波と、前記抽出された２次元波を比較する
段階と、（３）前記比較の結果により、画像になされ
た、拡大縮小率、回転角、反転、非等方拡大縮小率、平
行移動量を含む、線形座標変換を算出する段階と、を含
むことを特徴とする、幾何変換特定方法。
【請求項１４】電子透かし抽出方法であって、（１）記
憶装置に記憶された画像から、画像に埋め込まれた２次
元波を抽出する段階と、（２）予め定義された対称性を
もたない２次元波と、前記抽出された２次元波を比較す
る段階と、（３）前記比較の結果により、画像になされ
た、拡大縮小率、回転角、反転、非等方拡大縮小率、平
行移動量を含む、線形座標変換を算出する段階と、
（４）前記算出された線形座標変換を用いて、前記画像
の幾何補正を行う手段と、（５）前記幾何補正の行われ
た画像から電子透かしを抽出する段階と、を含むことを
特徴とする、電子透かし抽出方法。
【請求項１５】画像になされた幾何変換を特定するため
の２次元波を画像に埋め込むプログラムを含む媒体であ
って、該プログラムが、（１）画像を記憶装置に記憶す
る機能と、（２）対称性を持たない２次元波の集まりか
らなるパターンを記憶装置に記憶する機能と、（３）前
記記憶装置に記憶された画像に、前記パターンを実空間
で埋め込む機能と、を含むことを特徴とする、プログラ
ムを含む媒体。
【請求項１６】電子透かしを埋め込むためのプログラム
を含む媒体であって、該プログラムが、（１）画像を記
憶装置に記憶する機能と、（２）対称性を持たない２次
元波の集まりからなるパターンを記憶装置に記憶する機
能と、（３）前記記憶装置に記憶された画像に、前記パ
ターンを実空間で埋め込む機能と、（４）前記パターン
の埋め込まれた画像にさらに電子透かしを埋め込む機能
と、を含むことを特徴とする、プログラムを含む媒体。
【請求項１７】２次元波が埋め込まれた画像から、前記
２次元波を抽出することにより、画像になされた幾何変
換を特定するプログラムを含む媒体であって、該プログ
ラムが、（１）記憶装置に記憶された画像から、画像に
埋め込まれた２次元波を抽出する機能と、（２）予め定
義された対称性をもたない２次元波と、前記抽出された
２次元波を比較する機能と、（３）前記比較の結果によ
り、画像になされた、拡大縮小率、回転角、反転、非等
方拡大縮小率、平行移動量を含む、線形座標変換を算出
する機能と、を含むことを特徴とする、プログラムを含
む媒体。
【請求項１８】電子透かしを抽出するためのプログラム
を含む媒体であって、該プログラムが、（１）記憶装置
に記憶された画像から、画像に埋め込まれた２次元波を
抽出する機能と、（２）予め定義された対称性をもたな
い２次元波と、前記抽出された２次元波を比較する機能
と、（３）前記比較の結果により、画像になされた、拡
大縮小率、回転角、反転、非等方拡大縮小率、平行移動
量を含む、線形座標変換を算出する機能と、（４）前記
算出された線形座標変換を用いて、前記画像の幾何補正
を行う手段と、（５）前記幾何補正の行われた画像から
電子透かしを抽出する機能と、を含むことを特徴とす
る、プログラムを含む媒体。