画像間のアフィン関係を推定する方法
第１の画像と第２の画像とのアフィン関係を推定する方法（４００）が開示される。第１の画像及び第２の画像の各々は、少なくとも４本の互いに平行でない線を有する。方法（４００）は、各々の画像の中に現れる線の複数組の交点を識別すること（４０６）により開始される。次に、方法（４００）は、第１の組の交点及び第２の組の交点から、交点間に関係が存在するか否かを判定する（４１２）。関係が存在する場合、第１の画像及び第２の画像はアフィン関係にあり、アフィン歪は反転されてもよい（４１８）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、画像処理に関し、特に、画像間のアフィン関係を推定することに関する。
【背景技術】
【０００２】
背景
電子透かしは、情報を知覚不可能に画像中に埋め込むために頻繁に使用される。しかし、一般に使用されている電子透かしの多くは、スケーリング、回転、せん断歪(shearing)、アナモフィックスケーリング(anamorphic scaling)などの歪により破壊される。電子透かし検出方法の中には、平行移動を感知するものさえある。
【０００３】
これまで、電子透かしを検出するための様々な方法が提案されてきたが、それらの方法のいくつかは、アフィン歪に対して不変であるといえる。しかし、アフィン歪に対して不変である方法の多くは、いずれかの段階で、アフィン歪を定義するパラメータの空間全体にわたる広範囲の検索を必要とする。そのような検索は、多次元であり、通常、相当に大きな計算容量を消費すると考えられる。
【０００４】
最近、まず平行移動を除去し、次にスケーリング及び回転を２つの直交方向の別の平行移動効果とする変換を実行することにより、検索空間を縮小するいくつかの方法が提案されている。それらの方法は、ＲＳＴ（回転、スケール及び平行移動）に対して不変な方法として知られる。通常、この技術は埋め込み手順と検出手順との相補性を必要とする。
【０００５】
他の技術は、回転対称などの特殊な対称特性を有するパターンを埋め込み、次に、非対称歪パラメータの広範囲な検索によりそれらのパターンを検出することに依存する。
【０００６】
上述の方法はいずれも完全アフィン歪の不変性を有していないため、完全不変性を確保するためには、歪パラメータ空間のうちの１つ以上の広範囲な検索が依然として必要とされる。従って、パラメータ空間の広範囲にわたる検索を必要とせずに、アフィン歪のパラメータを推定する方法が必要とされる。
【発明の開示】
【０００７】
概要
本発明の目的は、既存の構成の１つ以上の欠点を克服すること又は少なくとも改善することである。
【０００８】
上述の問題に対処する構成が開示される。かかる構成は、画像に埋め込まれた線の交点と画像の歪バージョンに埋め込まれた線の交点との対応性を識別することにより、画像に適用されたアフィン歪のパラメータを推定するものである。
【０００９】
本発明の１つの側面によれば、各々が少なくとも４本の互いに平行でない線を有する第１の画像と第２の画像との間のアフィン関係を推定する方法であって、
前記第１の画像中に現れる前記線の第１の組の交点を識別するステップと、
前記第２の画像中に現れる前記線の第２の組の交点を識別するステップと、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係が存在するか否かを判定するステップとから成り、前記関係が存在する場合、前記第１の画像及び前記第２の画像はアフィン関係にある方法が提供される。
【００１０】
本発明の別の側面によれば、補助パターンを有し、少なくとも４本の互いに平行でない線を有し、前記線が所定の位置で第１の組の交点を形成する第１の画像のアフィン歪バージョンである第２の画像の中の前記補助パターンを検出する方法であって、
前記第２の画像中に現れる前記線の第２の組の交点を識別するステップと、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係を識別するステップと、
前記第１の組の交点及び前記第２の組の交点を使用して、前記アフィン歪パラメータを推定するステップと、
歪補助パターンを形成するために、前記アフィン歪パラメータにより定義される前記アフィン歪を前記補助パターンに適用するステップと、
前記第２の画像中の前記歪補助パターンを検出するステップとから成る方法が提供される。
【００１１】
本発明の更に別の側面によれば、上記の方法のうちのいずれか１つを実現するための装置が提供される。
【００１２】
本発明の別の側面によれば、先に説明された方法のうちのいずれか１つを実現するためのコンピュータプログラムが記録されたコンピュータ可読媒体を含むコンピュータプログラム製品が提供される。
【００１３】
本発明の他の面も開示される。
【発明を実施するための最良の形態】
【００１４】
添付図面のうちのいずれか１つ以上において、同一の図中符号を有するステップ及び／又は特徴が参照される場合、以下の説明中、特に指示のない限り、それらのステップ及び／又は特徴は同一の機能又は動作を有するものとする。
【００１５】
図１Ａに一例が示されるような画像中の１本の直線nについて考える。直線nを表現する方法がいくつかあることは、当業者には理解されるであろう。例えば、直線nを表現するために２つの点が使用されてもよい。また、直線nは、画像に埋め込まれてもよく、あるいは画像中の１つ以上の特徴と関連付けられてもよい。
【００１６】
直線nは、デカルト座標の縦軸（Ｙ軸）に対して角度βnをなし、直線nに対して垂直な方向に、座標の原点から距離rnの位置にある。直線nは、１対のパラメータ{rn, βn}により一意に記述される。図１Ｂは、極座標空間において直線nを定義するパラメータ対{rn, βn}を示す。
【００１７】
再び図１Ａを参照すると、直線n上の１点(x, y)及び直線nに沿った距離λnは、標準形式で次のように表されてもよい。
【００１８】
【数１】
【００１９】
ここで、直線nを含む画像に適用される一般的なアフィン歪を考える。アフィン歪は、回転、スケーリング、せん断歪、鏡映、平行移動及びアナモフィックスケーリングのうちの１つ以上を含んでもよい。アフィン歪後の当初の点(x, y)の画像中の変換座標を(x〜, y〜)とすると、点(x〜, y〜)は次のように表される。
【００２０】
【数２】
【００２１】
式中、aijは、回転、スケーリング、せん断歪、鏡映及びアナモフィックスケーリングを定義するパラメータであり、(x0, y0)は、平行移動を定義する。ここで、以下のように仮定する。
【００２２】
【数２−２】
【００２３】
更に、以下に示す場合は、鏡映が起こったことを示す。
【００２４】
【数２−３】
【００２５】
パラメータaijにより適用される総歪(total distortion)は、次のように、基本歪(prime distortions)、すなわち回転、アナモフィックスケーリング(anamorphic scaling)及びせん断歪の組み合わせに分解されてもよい。
【００２６】
【数３】
【００２７】
式中、角度ωの回転は、以下の行列により表される。
【００２８】
【数４】
【００２９】
Ｘ軸及びＹ軸に沿ったアナモフィックスケーリングは、アスペクト比変化(aspect ratio change)と呼ばれる場合もあり、次の形式を有する。
【００３０】
【数５】
【００３１】
ｘ方向のせん断歪は、次の形式を有する。
【００３２】
【数６】
【００３３】
また、|ω|≦４５°であるように、回転歪を正しい象限に配置するために適用される転位(transposition)は、次の４つのオプションのうちの１つから選択される。
【００３４】
【数７】
【００３５】
アフィン歪は、アフィン歪中、どの直線も線の平行性(parallelism of lines)と共に保持されるが、長さ及び角度は変化するという特性を有する。従って、画像中の直線nは変形後の画像中の直線に変換されるが、変形後の画像中の直線はパラメータ対{r〜n,β〜n}により定義される。このパラメータ対{r〜n,β〜n}は、通常、アフィン歪前の直線nのパラメータ対{rn,βn}とは異なる。
【００３６】
略語cn=cosβn、sn=sinβnを使用すると、式（１）及び（２）から次の関係が成り立つ。
【００３７】
【数８】
【００３８】
及び
【００３９】
【数９】
【００４０】
アフィン歪(affine distortion)を定義する６つの未知のパラメータ{a11, a12, a21, a22, x0, y0}を含む式（８）及び（９）によって、各直線nがパラメータ対{rn, βn}により定義される３本の直線を画像中に含め、アフィン歪画像(affine distorted image)中の３本の直線を検出し、アフィン歪直線(affine distorted line)ごとにパラメータ対{r〜n,β〜n}を判定し、式（８）及び（９）を解くことにより、パラメータ{a11, a12, a21, a22, x0, y0}が計算されてもよい。鏡映(reflection)を識別するために、直線を画像中に配置するとき、左右の非対称も要求される。
【００４１】
しかし、式（８）及び（９）から、直線にアフィン歪が適用される場合、一般に、パラメータ対{r〜n,β〜n}はかなり複雑で曖昧な方式で変換されることがわかる。この曖昧さは、直線nと平行な方向の平行移動又はスケーリングが、パラメータ対{rn,βn}に全く影響を及ぼさないために起こる。
【００４２】
また、アフィン歪前の画像中の直線nに対応する歪後の直線を識別することも明らかではない。これを例示するために、図２Ａは歪前の極座標空間における３本の線のパラメータ対{rn,βn}を示し、図２Ｂは歪後の同一の３本の線のパラメータ対{r〜n,β〜n}を示す。歪前と歪後のパラメータ対{rn,βn}及び{r〜n,β〜n}の対応性は、曖昧になり、その結果、縮退や、不確かさを招く可能性がある。
【００４３】
アフィン歪前とアフィン歪後の各直線の対応性を一意に識別するために、いくつかの技術が使用されてもよい。１つの技術は複数の線を埋め込む。この場合、線自体が一意性を有し、線の一意性はアフィン歪により破壊されない。例えば、各直線を一意に識別するために、それぞれ異なる型、色などを有する線が使用されてもよい。
【００４４】
アフィン歪の別の有用な特性は、１本の直線の２つの線分の比がアフィン歪に関して不変であるということである。好ましい実現形態においては、アフィン歪前とアフィン歪後の各直線の対応性を一意に識別するために使用されるのがこの特性である。
【００４５】
１つの画像の中にN本の直線があると考えると、各直線は、先の場合と同様に、パラメータ対{rn, βn}、ｎ＝１→により一意に記述され、ｎ≠ｍであるとき、角度はβn≠βmである。従って、それらの直線は互いに平行ではない。
【００４６】
直線は互いに平行ではないので、各直線はその長さに沿って他の直線と互いに交差する。N本の（互いに平行でない）直線の交点の最大数は、三角数N(N-1)/2である。直線mが直線kと交差する点(xkm, ykm)は、次のように表される。
【００４７】
【数１０】
【００４８】
式中、λkmは、直線ｍが交差する直線ｋに沿った距離である。同様に、距離λmkは、直線ｋが交差する直線ｍに沿った距離である。
【００４９】
式（１０）の連立方程式を解くと、距離λkmは次の式により表される。
【００５０】
【数１１】
【００５１】
直線の本数Ｎ＝４である場合を考える。各直線kは、他の３本の直線ｍとの間に３つの交点(xkm, ykm)を有するであろう。この段階で、直線kに沿ったそれぞれの交点(xkm, ykm)までの距離λkmを、大きさに従って次のように順序付けると有用である。
【００５２】
【数１２】
【００５３】
線分の長さξk1及びξk2を次のように定義すると、
【００５４】
【数１３】
【００５５】
及び
【００５６】
【数１４】
【００５７】
直線ｋの長さ比Ｒkは次のように定義される。
【００５８】
【数１５】
【００５９】
直線のパラメータ対{rn, βn}を適切に選択すると、各直線kの比Ｒkは、他のどの直線ｍの長さ比とも明確に異なる。比Ｒkは、アフィン歪に関して不変であるため、アフィン歪前とアフィン歪後の各直線の対応性を一意に判定できる。
【００６０】
対応する直線が識別されたならば、直線kにより表現される各方向に沿ったスケーリング係数を推定するために、アフィン歪前とアフィン歪後の異なる直線に沿った距離λkmが比較されてもよい。また、アフィン歪の回転成分を推定するために、各直線の向きの変化が使用されてもよい。
【００６１】
式（４）及び（５）にそれぞれ定義されるように、当初の画像に回転が適用され、続いてアナモフィックスケーリング(anamorphic scaling)が適用された特定のケースを考える。アナモフィックスケーリングは、水平デカルト座標軸（Ｘ軸）と平行な方向に係数Aのスケーリングを有し、それに対して垂直な方向に係数Bのスケーリングを有する。角度ωは回転角である。一般に、角度βnにおける長さlnの線分は、角度β〜nで長さl〜nの線分にマッピングされる。このとき、
【００６２】
【数１６】
【００６３】
【数１７】
【００６４】
式（１６）及び（１７）は、３つの未知数、すなわち、スケーリング係数Ａ及びＢ並びに角度ωを含む。当初の画像に４本の線が埋め込まれているので、次のように、長さlnとして、各直線の外側の交点の距離を使用すると、
【００６５】
【数１８】
【００６６】
４対の式が得られる。最小２乗方法を用いて、このような過剰制約付き系(over-constrained system)を解くことができる。
【００６７】
尚、式（１６）及び（１７）は、平行移動に対して不変であり、平行移動(x0, y0)を想定しない。また、計算されるべき式（２）で定義される一般アフィン歪の全てのパラメータに対して、式（４）及び（５）の行列は式（３）におけるように組み合わされるが、せん断歪係数Ｒは０である。
【００６８】
あるいは、アフィン歪前とアフィン歪後の各直線の対応性から、パラメータ対{rn, βn}及び{r〜n, β〜n}の対応性が一意に判定される。式（１０）に式（１１）を代入すると、交点(xkm, ykm)は、次のように表される。
【００６９】
【数１９】
【００７０】
直線は互いに平行ではないので、sin(βk-βm)≠0である。実際の状況においては、sin2 (β〜k-β〜m)≧0.25が成立するように、それぞれの角度βk及びβmが選択される。これと同等に、直線k及びmが交差する角度は、30°＜|β〜k-β〜m|＜150°を満たす。
【００７１】
同様に、交点(xkm, ykm)に対応する変換後の点(x〜km, y〜km)は、次の式により表される。
【００７２】
【数２０】
【００７３】
式（１９）及び（２０）にパラメータ対{rn, βn}及び{r〜n,β〜n}を代入し、対応する交点(xkm, ykm)及び(x〜km, y〜km)を使用して式（２）を解くと、アフィン歪パラメータ{a11, a12, a21, a22, x0, y0}が得られる。
【００７４】
アフィンパラメータ推定の好ましい方法は、直線の交点(xkm, ykm)とアフィン歪後の交点(x〜km, y〜km)との最小２乗フィッティング(least squares fitting)（ＬＳＦ）を使用する。交点(xkm, ykm)及び(x〜km, y〜km)の対応関係は既知であるため、このＬＳＦは大幅に簡略化される。交点(xkm, ykm)及び(x〜km, y〜km)の対応関係が一意に識別されなければ、可能な全ての順列、この場合には、６！=７２０について、ＬＳＦを評価する必要がある。
【００７５】
検出され、（一意に）順序付けされた交点を(x＾km, y＾km)により表すものとする。先の場合と同様に、当初の（歪前の）交点は(xkm, ykm)であり、歪後の交点は(x〜km, y〜km)である。誤差エネルギー(error energy)は、ユークリッドノルム尺度(Euclidean norm measure) Eとして定義される。
【００７６】
【数２１】
【００７７】
変換パラメータpに関する誤差エネルギー最小化(Error energy minimization) により、６つの式が得られる。
【００７８】
【数２２】
【００７９】
変換パラメータpは、変換を定義するパラメータa11、a12、a21、a22、x0及びy0（式（２））のうちの１つである。
【００８０】
幸いなことに、p=aijに関する偏導関数のために、式（２２）において表される６つの式は大幅に簡略化される。
【００８１】
【数２３】
【００８２】
そこで、式（２２）において表される６つの式は、以下の加算を整合することと同等である。
【００８３】
【数２４】
【００８４】
式（２２）及び（２３）からの全変換パラメータ(full transform parameters)を埋めることにより、同一の対称行列乗数(same symmetric matrix multiplier) Mを有する１対の３×３行列式が得られる。
【００８５】
【数２５】
【００８６】
【数２６】
【００８７】
【数２７】
【００８８】
行列Mの逆行列は、別の対称行列M-1である。
【００８９】
【数２８】
【００９０】
【数２９】
【００９１】
式（２５）及び（２６）を反転すると、６つの歪パラメータ全ての最小２乗推定(least squares estimate)のための最終解は次のように明示される。
【００９２】
【数３０】
【００９３】
【数３１】
【００９４】
最小誤差エネルギー(minimum error energy) Eは、式（２１）を用いて計算されてもよく、許容限界(allowable limit)と比較されてもよい。誤差エネルギーEが許容限界より大きい場合、アフィン整合(affine match)が探索されなかったと想定される。交点(xkm, ykm)及び(x〜km, y〜km)を比較することにより、最大点偏差(maximum point deviations)を計算することも可能であり、これは推定される歪の信頼性尺度(reliability measure)を確定する上で有用である。特に信頼性推定に関して有用な別のパラメータは、正規化エネルギー(normalized energy)、すなわち、任意の点の集合ｎ＝1→Ｍに対して次のように定義される中心平均２乗点分布(centred mean square point distribution) Gにより誤差エネルギーE(error energy)を除算した値である。すなわち、
【００９５】
【数３２】
【００９６】
式中、測定された点分布の重心(centroid)は、(x＾￣n,y＾￣n)として定義される。
【００９７】
図３は、少なくとも４本の互いに平行でない直線を含む画像からアフィン歪のパラメータを検出する方法２００の概略的なフローチャートを示す。一実施形態においては、互いに平行でない直線は、それらの直線が人間の目に見えないように画像中に埋め込まれる。図４は、電子透かしを使用して直線を埋め込む方法３００の概略的なフローチャートを示す。
【００９８】
方法２００及び３００は、図５に示されるような汎用コンピュータシステム１００を使用して実施されるのが好ましい。その場合、方法２００及び３００のステップは、コンピュータシステム１００内部で実行するソフトウェアとして実現される。特に、方法２００及び３００のステップは、コンピュータシステム１００により実行されるソフトウェア中の命令により実現される。ソフトウェアは、例えば、以下に説明される記憶装置を含むコンピュータ可読媒体に格納されてもよい。ソフトウェアは、コンピュータ可読媒体からコンピュータにロードされ、コンピュータシステム１００により実行される。そのようなソフトウェア又はコンピュータプログラムが記録されたコンピュータ可読媒体は、コンピュータプログラム製品である。
【００９９】
コンピュータシステム１００は、コンピュータモジュール１０１と、キーボード１０２、マウス１０３及び撮像装置(imaging device)１２２などの入力装置と、プリンタ１１５及び表示装置１１４を含む出力装置とにより形成される。撮像装置１２２は、デジタル画像を収集するために使用されるスキャナ又はデジタルカメラであってもよい。変復調器（モデム）トランシーバ装置１１６は、例えば、電話回線１２１又は他の機能媒体を介して接続可能な通信ネットワーク１２０との間で通信を実行するために、コンピュータモジュール１０１により使用される。
【０１００】
通常、コンピュータモジュール１０１は、少なくとも１つのプロセッサユニット１０５と、例えば、半導体ランダムアクセスメモリ（ＲＡＭ）及び読み取り専用メモリ（ＲＯＭ）から形成されるメモリユニット１０６とを含む。モジュール１０１は、ビデオ表示装置１１４に結合するビデオインタフェース１０７、キーボード１０２、マウス１０３及び撮像装置１２２に対応する入出力（Ｉ／Ｏ）インタフェース１１３並びにモデム１１６及びプリンタ１１５に対応するインタフェース１０８を含む複数のＩ／Ｏインタフェースを更に含む。記憶装置１０９が設けられ、通常、記憶装置１０９は、ハードディスクドライブ１１０及びフロッピー（登録商標）ディスクドライブ１１１を含む。ＣＤ‐ＲＯＭドライブ１１２は、通常、不揮発性データ源として設けられる。通常、コンピュータモジュール１０１の構成要素１０５〜１１３は、当業者には周知の従来のコンピュータシステム１００の動作モードが得られるように相互接続バス１０４を介して通信する。
【０１０１】
通常、ソフトウェアは、ハードディスクドライブ１１０に常駐し、プロセッサ１０５により読み取られ、ソフトウェアの実行はプロセッサ１０５により制御される。場合によっては、ソフトウェアは、ＣＤ‐ＲＯＭ又はフロッピー（登録商標）ディスクに符号化された形でユーザに供給され、対応するドライブ１１２又は１１１により読み取られてもよく、あるいはユーザによりネットワーク１２０からモデム装置１１６を介して読み取られてもよい。更に、他のコンピュータ可読媒体からコンピュータシステム１００へソフトウェアをロードすることも可能である。
【０１０２】
少なくとも４本の互いに平行でない直線を含む画像からアフィン歪のパラメータを検出する方法２００及び電子透かしを使用して直線を埋め込む方法３００は、上述のようなソフトウェアではなく、方法の機能又は部分機能を実行する１つ以上の集積回路などの専用ハードウェアにおいて実現されてもよい。そのような専用ハードウェアは、グラフィックプロセッサ、デジタルシグナルプロセッサ又は１つ以上のマイクロプロセッサ及び関連メモリを含んでも良い。
【０１０３】
まず図４を参照すると、パラメータ対{rn, βn}により各直線nが定義されるような複数の直線を電子透かしを使用して埋め込む方法３００はステップ３１０で始まり、ステップ３１０においては、各直線nと関連するパターンが生成される。
【０１０４】
埋め込まれるべき直線のパラメータ対{rn,βn}を選択する場合、１つのオプションは、全角度範囲にわたり一様に分布する角度βn、すなわち、０°、４５°、９０°、１３５°を有する４本の直線を選択することである。図６は、そのように配列された４本の直線を示す。
【０１０５】
４本の直線のいくつかの配列は、極めて対称性の高い結果をもたらす。図示される配列はそれほど対称ではない。この配列は、配列の鏡映歪バージョン(reflected and distorted version)と明確に識別できる６つの交点(xkm, ykm)を含む。３本以上の線が１点で出会う縮退配列(degenerate arrangement)においては、交点は６つより少なくなることも可能であるが、ここではそのようなケースを考慮しない。
【０１０６】
図６には、別のパラメータeに基づいて、線分６００の長さpに関連して定義されたn=１〜４に対する線分の長さξn1及びξn2も示される。パラメータeの関数として式（１５）で定義される線分の長さ比Rnは、式（１８）で定義される線分の長さlnと共に、表１に示されるように計算される。
【０１０７】
【表１】
【０１０８】
図７は、線分の長さ比Rnをパラメータeの関数として表す。特定の値e≒0.31により、全く異なる４つの別個の長さ比Rnが求められることが図７からわかる。別の興味深い有用な長さ比Rnの集合は、e=0.5に対して現れる。この場合、４本の直線の全てが中心の基準点から等距離にある。それらの等距離がアフィン歪により均等に変換されない可能性があるため、第７の点はせん断歪又はアナモフィックスケーリングに対して真の不変性を維持しない点であるが、本質的には第７の点を定義できる。
【０１０９】
好ましい実施形態（e=0.31）においては、４本の直線は次のようなパラメータを伴って埋め込まれる。
【０１１０】
【数３３】
【０１１１】
式中、pは画像幅に設定される。尚、rnに対応する角度βnが１８０°回転されるのであれば、負の値であるrnはそれを相補する正の値と等価である。
【０１１２】
好ましい方向付け角度βnを選択することにより、いずれか１本の直線nと画像境界(image boundaries)との一致は最大限に回避される。
【０１１３】
直線が電子透かしとして埋め込まれる場合、各電子透かしは、電子透かしが埋め込まれている画像がアフィン歪を受けた後であっても検出可能であるという特性を有していなければならない。好ましい実施形態によれば、各パターンは一方向にのみの変化を有し、その方向は直線nに対して垂直である。パターンは軸を更に有し、その軸は線と一致する（奇数又は偶数）対称の軸又は指定された軸であってもよい。通常、パターンは、変化の方向に適用される１次元基底関数(one-dimensional base function)から生成され、軸と平行に繰り返される。
【０１１４】
好ましい実施形態においては、基底関数は下記の形態の複素同次関数(complex homogeneous function)である。
【０１１５】
【数３４】
【０１１６】
式中、vは１次元座標であり、必ずしも正ではない。α及びpは定数である。基底関数g(v)は、基底関数がパターン画像のナイキスト周波数(Nyquist frequency)を超える周波数を有する領域において減衰されるのが好ましい。式（３４）は、位相関数(phase function)を振幅変調(amplitude modulating)する振幅関数(amplitude function)としても考えられ、その場合、位相関数は対数位相(logarithmic phase)を有する。そのような複素同次関数g(v)が、例えば係数aによってスケーリングされる場合、スケーリングは次のような複素定数係数(complex constant factor)のみを導入する。
【０１１７】
【数３５】
【０１１８】
複素同次関数の利点は、複素同次関数の自己相関(auto-correlation)が複素同次関数のスケールバージョン(scaled version)を伴う複素同次関数の相互相関(cross-correlation)に正比例することである。この「スケール不変(scale-invariant)」特性は、スケール変換後であっても、画像を基底関数と相関することにより画像中の電子透かしの検出を可能にする。
【０１１９】
図８は、式（３４）の基底関数の実数部を使用して次のように生成されるパターンの一例を示す。
【０１２０】
【数３６】
【０１２１】
尚、パターン画像のナイキスト周波数を超える周波数を有する値を除去するために、対称軸に隣接する領域において、マスキングが適用されている。パターンとそのパターンに埋め込まれた直線との関係も示される。直線自体はパターンの一部を形成せず、次のステップにおいては画像に追加されないことが理解される。この例のパターンを示すに際して、パターン値は[0,255]の範囲の値にマッピングされており、０の値は黒色として表現され、２５５の値は白色として表現される。
【０１２２】
再び図４を参照すると、ステップ３１０においては、１つのパターン画像を形成するために、複数の別個のパターンが加算される。パターン画像は、生成後にメモリ１０６又はＨＤＤ１１０に格納されてもよい。
【０１２３】
観測者が知覚不可能なパターンを埋め込むために、ステップ３２０において、メモリ１０６からパターン画像が検索され、低輝度変化(low intensity variation)を有する画像の領域に対応するパターンのレベルを大幅に減少し、且つ高輝度変化(high intensity variation)を有する画像の領域に対応するパターンのレベルをそれより少ない量だけ減少するために、パターン画像はプロセッサ１０５により知覚マスキングされる。輝度変化の尺度の一例は、画像中の輝度の局所勾配の大きさである。他の尺度には、輝度の偏導関数、「エネルギー」又は周波数コンテンツの局所推定値(local estimates)、局所分散(local variance)及び更に精巧な人間の視覚系統のマスキングの推定値などがある。
【０１２４】
ステップ３３０において、知覚マスキングされたパターン画像が画像に追加される。このパターン画像は電子透かしと呼ばれてもよい。画像がカラー画像である場合、電子透かしはカラー画像の輝度部分に追加されるのが好ましい。これにより、電子透かし入り画像がカラーからグレイスケール表現に変換されるときに電子透かしは残存できる。あるいは、電子透かしは、カラー画像のＲ、Ｇ、Ｂ、Ｈ、Ｖ、Ｓ、ｕ、ｖなどのチャネルのうちの１つ以上又はそれらのチャネルの何らかの組み合わせに追加されてもよい。画像への電子透かしの追加は、単純な代数加算の他にディザリング及びハーフトーン化を更に含む。複素基底関数の実数部及び虚数部が、カラー画像の２つ以上のチャネルに独立して追加されてもよい。
【０１２５】
電子透かしが埋め込まれた画像は、tiff、gif、jpeg、mpegなどのデジタル画像フォーマットで記憶装置１０９（図５）に格納されてもよい。電子透かし入り画像のハードコピーを作成するために、電子透かし入り画像はプリンタ１１５（図５）で印刷されてもよく、あるいはネットワーク１２０を使用して別のコンピュータモジュール１０１へ通信されてもよい。
【０１２６】
画像中に直線が埋め込まれ、画像がアフィン歪を受けているため、直線及びそのパラメータ対{r〜n,β〜n}が検出されなければならない。図４を参照して説明したように、電子透かしを使用して直線が埋め込まれているので、次に図３を参照して、画像からアフィン歪のパラメータを検出する方法２００を説明する。方法２００はステップ２０２で始まり、ステップ２０２において、歪画像のデジタルコピーが獲得される。通常、画像は既にデジタル画像フォーマットになっており、記憶装置１０９（図５）に格納されてもよい。そのような場合、画像は画素値のアレイに変換される。その時点で画像が写真などのハードコピーフォーマットのままである場合には、まず、撮像装置１２２（図５）を使用してハードコピーを走査することにより、ハードピー画像はデジタルフォーマットに変換される。
【０１２７】
続くステップ２０５において、プロセッサ１０５は、まず、画像から知覚マスクを形成し、次に、画像の値を知覚マスクの対応する値で除算することにより画像を知覚マスクで強調し、知覚マスキングを解消する。尚、近似知覚マスクが適切である。
【０１２８】
次に、ステップ２１０において、得られた画像に射影変換(projective transform)が適用される。射影変換は、画像中の直線に沿って値を加算することによりエネルギーを累積する。ラドン（Radon）（又は等価のHough）変換は、ステップ２１０において使用されてよい射影変換の１つであり、次のように定義される。
【０１２９】
【数３７】
【０１３０】
離散型データセットに対してラドン変換(Radon transform)の実施形態を導き出すために、画像関数h（x, y）の射影(projection)とその関数のフーリエ変換のスライスとの対応性が使用されるが、その対応性は、「射影‐スライス定理(projection-slice theorem)として知られる。
【０１３１】
射影‐スライス定理は、２次元関数の射影の１次元フーリエ変換がその関数の２次元フーリエ変換の半径方向のスライス(radial slice)に等しいと規定する。尚、
【０１３２】
【数３８】
【０１３３】
であり、式中、H(u, v)は画像h(x, y)の２次元（２Ｄ）フーリエ変換である。擬似極座標空間(quasi polar space)において、角度は範囲(-π/2, π/2)であり、距離は範囲(-∞, ∞)にある。フーリエドメイン(Fourier domain)において擬似極座標(quasi-polar coordinate)(q,φ)を定義することにより、座標変換は、u=qcosφ、v＝qsinφであり、射影‐スライス定理の１つの形態は、次のように、ラドン射影角(Radon projection angle) φ＝θに対応するフーリエ極座標角(Fourier polar angle)について求められる。
【０１３４】
【数３９】
【０１３５】
式（３９）により離散的画像の２Ｄ‐ＦＦＴの半径方向のスライスとしてラドン射影の（フーリエ変換の）推定が可能になるため、式（３９）は有用である。これは、まず、２Ｄ-ＦＦＴを実行し、続いて、再サンプリング(resampling)を実行するためにbicubic又はchirp-zなどの適切な補間を使用してデカルト座標から極座標への再マッピング(remapping)を実行することにより、離散的ラドン変換(discrete Radon transform)を評価できることを示唆する。
【０１３６】
方向付け角度(orientation angle)β〜n及び垂直変位(perpendicular displacement) r〜nを有する１次元基底関数g(v)に基づいてN個のパターンが埋め込まれている画像h(x, y)は、画像自体の画素値を無視すると、次のように書き表される。
【０１３７】
【数４０】
【０１３８】
方向付け角度(orientation angle)β〜nにある１つの方向にのみ変化を有するパターンに射影変換が適用された場合、角度θが角度θの他の全ての値と比較される方向付け角度β〜nに等しいときに、射影の値は著しく大きくなる。図９は、図８に示される歪前のパターンの例の射影を擬似極座標空間(quasi-polar space)において示す図である。角度θが角度βｎと等しいとき、射影の値は特に大きくなることがわかる。射影は、オフセット距離rnに関して対称性を更に有する。
【０１３９】
従って、式（４０）の関数に対してラドン変換(Radon transforms)を適用することにより、以下に示されるような関数のラドン変換はθ＝β〜nである線に制約されることがわかる。
【０１４０】
【数４１】
【０１４１】
ラドン変換を用いることにより、パターンg(v)が埋め込まれた画像関数(image function)h(x, y)を擬似極座標空間内のN本の直線に集中したので、極座標角(polar angle) θの全ての値に対して１-Ｄ擬似半径方向相関(1-D quasi-radial correlations)（座標rにおける）を用いることにより、更に、各直線に含まれるエネルギーを単一の点（又は１つの点の付近の狭い領域）に集中することが可能である。
【０１４２】
従って、続くステップ２２０において、プロセッサ１０５は、極座標角θの可能な全ての値に対して、擬似半径方向座標(quasi-radial coordinate)rにおける射影(projection)と基底関数(base function)g(v)との１-Ｄ相関(1-D correlations)を実行する。用語「相関(correlation)」は、位相相関(phase correlation)及びエネルギーによりスケーリングされた位相相関を更に含む。その結果得られる相関は、擬似極座標(r＾n,β＾n)にピークを有する。
【０１４３】
ステップ２３０において、プロセッサ１０５は相関の絶対ピーク(absolute
peaks)を探索する。各歪埋め込みパターンの方向付け角度(orientation angle)β〜n及び垂直変位(perpendicular displacement)r＾nは、ピークの擬似極座標(r＾n,β＾n)から直接求められる。また、埋め込み直線のパラメータ対{rn, βn}も利用可能である。
【０１４４】
検出器の前処理段階は、最高相関大きさピーク(highest correlation magnitude peaks)に基づいて、通常は約６４本である複数の候補線を探索する。この数から、４本の直線の全ての組み合わせが精査される。可能な組み合わせの数は、６４！／（６０！４！）=６３５３７６である。４本の直線の角度の中に、少なくとも１５°の差を有していない直線が存在する場合、その組み合わせは放棄され、次の段階に進まない。直線の１つの組み合わせがこの段階をパスしたと仮定すると、その後、式（１９）を用いて６つの交点が計算され、４組の線分比R＾nが評価される。線分比R＾nは、この後、サイズが大きくなる順に配列される。次に、予測線比(expected line ratios)（同様に、サイズが大きくなる順に配列される）に対する当てはめの近接度(closeness)に関するメリット関数(merit function)が次のように評価される。
【０１４５】
【数４２】
【０１４６】
ある閾値（好ましくは０．１）以下のメリット関数を有する全ての組み合わせは、その後の処理に際して、「候補組み合わせ(candidate combinations)」としてラベル付けされる。
【０１４７】
尚、他のメリット関数も使用可能である。例えば、線強度(line strength)（線相関大きさ(line correlation magnitude)に関する）を反映し、それにより検出レベルが劣る線からの寄与を減少するために、上記のメリット関数を重み付けすることも可能である。
【０１４８】
次に、候補組み合わせごとに、以下の処理が実行される。
【０１４９】
ステップ２４０において、プロセッサは、アフィン歪前とアフィン歪後の各直線nの対応性を一意に識別する。好ましい実現形態においては、歪後の線の長さ比R＾nは歪前の長さ比Ｒ＾nと整合され、式（１５）に関連して説明されたように、アフィン歪前とアフィン歪後の各直線の対応性を一意に識別するために使用される。
【０１５０】
アフィン歪前とアフィン歪後の各直線の対応性を一意に識別するために使用されてもよい別の技術は、各直線を埋め込むためにそれぞれ異なるパラメータを有する基底関数を使用する方法である。そのような実現形態においては、基底関数ごとにステップ２２０及び２３０が繰り返される。
【０１５１】
次のステップ２５０においては、プロセッサ１０５は、式（２０）を使用して交点 (x＾km,y＾km)を計算する。最後に、ステップ２６０において、式（２１）〜（３２）に関連して先に説明されたＬＳＦを用いて、アフィン歪パラメータ{a11, a12, a21, a22, x0, y0}が推定される。
【０１５２】
最終的なアフィン歪パラメータは、全ての候補組み合わせに対して最低の最小誤差エネルギー(lowest minimum error energy) Ｅ（式（２１））を生成するパラメータになるように選択される。
【０１５３】
アフィン歪パラメータ{a11, a12, a21, a22, x0, y0}が推定されたならば、アフィン歪は反転されてもよく、これは矯正(rectification)又はレジストレーション(registration)と呼ばれることもある。
【０１５４】
アフィン歪が反転された後、相関処理を経て擬似ランダムノイズ（pseudo random noise）（ＰＲＮ）シーケンスの検出などの従来の方法を使用して、ステップ３３０（図４）においてパターンを追加する以前に画像中に存在していた補助パターンと名付けられた追加パターンが検出されてもよい。そのような処理は、スペクトル拡散電子透かし(spread-spectrum watermarking)としても知られており、幾何学歪(geometric distortion)に対して極めて高い感度を示すことで知られている。通常、数パーセントのスケールの変化でも相関を実質的に破壊するのに十分であり、そのため、わずかにひずんだ画像の中のＰＲＮを検出することは不可能である。
【０１５５】
しかし、画像の歪を除去し、整列する処理は、補間及び再サンプリングを含み、これらの処理は、通常、計算のために高いコストを必要とする。従って、補助パターンを検出するときに相補歪を含む検出テンプレートを使用することにより、画像を矯正するのを回避することが提案される。
【０１５６】
この方式の大きな利点は、テンプレートをフーリエドメインで定義できることである。空間ドメインにおけるアフィン歪は、平行移動歪に関連する線形位相係数(linear phase factors)と共に、フーリエドメインにおける対応するアフィン歪をもたらす。フーリエアフィン対応性(Fourier affine correspondence)は、文献に十分詳細に記載されている。本質的には、式（２）のフーリエバージョンがテンプレートに適用される。連続フーリエ変換を次のように定義し、離散的にサンプリングされた画像並びに離散フーリエ変換（ＤＦＴ）に厳密に対応する関係が適応されることに注意すると、その更に効率のよい実現形態である高速フーリエ変換（ＦＦＴ）は、次のようになる。
【０１５７】
【数４３】
【０１５８】
歪テンプレート関数のフーリエ変換は、次の通りである。
【０１５９】
【数４４】
【０１６０】
フーリエドメインにおける式（２）のアフィン歪は、次の式により表される。
【０１６１】
【数４５】
【０１６２】
ここで、式中、係数κは実正規化定数(real normalization constant)及び線形位相係数(linear phase factor)を含むが、歪フーリエテンプレート(distorted Fourier template)J(u〜,v〜)には影響を及ぼさないので、歪フーリエテンプレートJ(u〜,v〜)は相関検出のフーリエドメインにおける実現形態で直接使用される。従って、フーリエテンプレート(Fourier template)J(u〜,v〜)が確定的な解析関数記述子(analytic functional descriptor)により定義されるのであれば、補間(interpolation)又は再サンプリング(resampling)の必要なく、いくつかのテンプレートj(x, y)は、式（４５）を使用して歪を受けてもよい。テンプレート整合前(template matching)に、フーリエ座標u及びvのみが歪を受けるだけでよい。
【０１６３】
例えば、ＵＲＬ又はＵＲＬに対するポインタを使用して、何らかのデータ又はそのデータに対するポインタを符号化するために、補助パターンが使用されてもよい。また、画像からアフィン歪のパラメータを検出する方法２００を使用すると、その画像の何らかの特性に関するデータ又は特性を参照するデータであるいわゆる画像メタデータは、画像がひずんでいたとしても、画像からメタデータを検索できるという意味で画像に拘束されることになる。メタデータが対抗できる歪は上述の射影変換を含むが、印刷、写真複写／複写、走査、色除去、ガンマ修正(gamma correction)、ガンマ変更(gamma change)、ＪＰＥＧ圧縮／一般圧縮(general compression)、フォーマット変換（すなわち、ＢＭＰからＧＩＦへ）、ノイズ追加及びノイズ除去(noise addition and removal)、低域フィルタリング(low-pass filtering)などのフィルタリング、クロッピング(cropping)及び画像の基本認識可能度(basic recognizability)を維持するほぼ全ての編集操作(editing operations)を更に含む。
【０１６４】
いくつかの適用用途においては、直線を知覚不可能なように埋め込む必要がない。また、エングレービング(engraving)又はエッチング(etching)により任意の平坦な面に直線が埋め込まれてもよい。そのような平坦な面はシリコンウェハを含む。その場合、歪後の直線は、光学系（カメラなど）、電磁システム又は近接度に基づくシステムであってもよい何らかのシステムにより検出されてもよい。その後、検出された直線は、表面の位置及び向きを判定するために利用されてもよい。
【０１６５】
以上、N本の直線を埋め込むことに基づく実施形態を説明した。画像中の特徴と関連して複数本の直線を含む画像に対して、方法２００の改訂バージョンが適用されてもよい。そのような固有の直線に対して、可能な４本１組の直線の各組について４つの交差比(intersection ratios)を事前に制約することは不可能である。しかし、第１の画像における現存の直線比を第２の画像における現存の直線比と比較することは可能である。４つ１組の整合比(matching ratios)（任意の規定許容差範囲内）の各組について、方法２００のステップ２４０〜２６０を使用して対応するアフィン変換が計算される。その後、整合比の組ごとに、ステップ２４０〜２６０は繰り返される。対応するアフィン変換が一貫している（すなわち、アフィンパラメータがクラスタリング(clustering)を示す）場合、アフィン変換を経て、それら２つの画像が互いに関連している確率は高い。従って、２つの画像を比較し、第２の画像がアフィン変換を経て第１の画像と関連しているか否かを推定することは可能である。
【０１６６】
第１の画像I1 (x, y)がアフィン変換又は空間歪(spatial distortion)(x, y)→ (x〜,y〜)により第２の画像I2 (x, y)と関連付けられるものとする。尚、アフィン変換は、式（２）で定義される変換である。第１の画像I1 (x, y)と第２の画像I2 (x, y)との関係は、次のように書き表される。
【０１６７】
【数４６】
【０１６８】
式中、μは画像輝度増率(image intensity multiplying factor)（又は利得）であり、n(x, y)は第１の画像と第２の画像との差を考慮する関数である。
【０１６９】
従来の画像整合方法（例えば、相関を使用する）は、より一般的なアフィン歪に対しては容易に実現できないことが知られている。それは、一般に、６次元空間（６つのアフィンパラメータの）の全体にわたる検索が要求されるためである。従って、本発明の開示によれば、第１の画像I1 (x, y)と第２の画像I2 (x, y)とを比較するための更に有効な方法は、それらの画像自体の中で自然に発生する線構造(line structures)の交差比を比較するという方法である。多くの画像は、まっすぐな縁部(straight edges)などのいくつかの線構造又は部分線構造を含む。そのような線構造は、例えば、画素輝度の勾配の係数を使用することにより強調されるのが好ましい。ラプラシアン(Laplacian)などの他の演算子が使用されてもよい。
【０１７０】
図１０は、第２の画像I2 (x, y)が第１の画像I1 (x, y)のアフィン歪バージョンであるか否かを推定する方法４００の概略的なフローチャートを示す。方法４００も、図５に示される汎用コンピュータシステム１００を使用して実施されるのが好ましく、その場合、方法４００のステップは、コンピュータシステム１００の内部で実行されるソフトウェアとして実現される。
【０１７１】
方法４００はステップ４０２で始まる。ステップ４０２において、方法２００のステップ２１０に関連して先に説明されたように、画像I1 (x, y)及びI2 (x, y)の各々に対してラドン変換などの射影変換が適用される。
【０１７２】
実際には、ラドン変換後のエンハンスメントが好ましいことが明らかになっている。従って、続くステップ４０４において、勾配エンハンスメント(gradient enhancement)が実行され、その結果、画像ごとの２Ｄ-分布関数(2-D distribution function)Ωj (r, θ)が求められる。
【０１７３】
【数４７】
【０１７４】
ステップ４０６において、分布関数Ωj(r, θ)の各々でピークが検出される。その目的は、対応する４つ１組の線構造を探索することである。従って、各々の画像I1 (x, y)及びI2 (x, y)の中の３２個の最も重要な線構造を表現する各々の分布関数Ωj (r, θ)の中の３２個の最高ピークを探索することにより、４本の直線について可能な組み合わせの数は３５９６０通りとなる。
【０１７５】
次に続くステップ４０８において、プロセッサ１０５は、方法２００に関連して先に詳細に説明したように、４本の直線の組み合わせごとに４つのピークの(r, θ)値から交差比を計算する。ステップ４１０において、４つ１組の比の３５９６０通りの組み合わせは、順序付けシーケンス(ordered sequence)として配列される。先の場合と同様に、いずれかの比が１より大きい場合、それは反転される。シーケンスは、値が大きくなる順に順序付けされる。特に、４つ１組の比の全ての組み合わせは、第１の画像I1(x, y)に関して４次元テーブルに配列され、第２の画像I2 (x, y)に関しては別個のテーブルに配列される。
【０１７６】
次に、ステップ４１２において、第１の画像I1 (x, y)及び第２の画像I2 (x, y)の比シーケンス(ratio sequences)が比較される。特に、ユークリッド距離(Euclidean distance)又は式（４２）に示されるメリット関数(merit function)に基づいて、第１の画像I1 (x, y)のテーブルにおける各順序付けシーケンスと第２の画像I2 (x, y)のテーブル２における各順序付けシーケンスとの対応性が評価される。規定の距離の中の対応性のみが許容される。メリット関数の計算は、計算に関して相当に過酷であり、試される点(points)（シーケンス(sequences)）の数の２乗とも関連付けられる。更に効率のよい方式は、４Ｄ-比(4-D ratio)テーブルの粗ビンニング(coarse binning)を実行し（例えば、0.2のビン幅(bin widths)は、５４=６２５ビン(bins)を提供する）、単純に、対応するビン又は隣接するビンにおけるシーケンスのメリット関数を評価するという方法である。
【０１７７】
メリット関数が規定の量より小さい場合、４つ１組の直線は整合すると想定され、その結果、ステップ４１４において、式（２１）〜（３２）を使用して、アフィン変換パラメータが交点から計算される。メリット条件を満たす全ての整合シーケンスに対してステップ４１４が繰り返され、６つのアフィンパラメータが作表(tabulated)される。
【０１７８】
続くステップ４１６において、第１の画像I1 (x, y)と第２の画像I2 (x, y)とのアフィン関係の尤度(likelihood)が推定される。例えば、テーブル中のアフィンパラメータエントリの著しく大きなクラスタリング(clustering)が存在する場合、第１の画像I1 (x, y)と第２の画像I2 (x, y)とのアフィン関係又は整合の尤度は高い。クラスタリング統計からアフィン整合の尤度の更に定量的な推定を導き出すことができる。
【０１７９】
ステップ４１６において、第１の画像I1 (x, y)と第２の画像I2 (x, y)との整合の尤度が低いと考えられる場合、ステップ４１７において、例えば画像I1 (x, y)と画像I2 (x, y)との整合は存在しないことをユーザインタフェースに指示することにより、方法４００は終了する。しかし、第１の画像I1 (x, y)と第２の画像I2 (x, y)との整合の尤度が高いと考えられる場合には、ステップ４１８において、第１の画像I1 (x, y)が第２の画像I2 (x, y)と整合するように、第１の画像I1 (x, y)に対して逆アフィン歪(inverse affine distorted)が適用される。
【０１８０】
最後に、ステップ４２０において、正規化相関により整合のクオリティ(quality of the match)が判定される。0.9の値は、高レベルの整合を示すであろう。他の尺度（例えば、視覚）は、画像がどれほどよく整合するか及びアフィン歪パラメータがどれほど適切に推定されたかを更に適切に指示できるであろう。
【０１８１】
以上、本発明のいくつかの実施形態のみを説明したが、本発明の趣旨の範囲から逸脱せずに、上述の実施形態に対して変形及び／又は変形を実施できる。上述の実施形態は単なる例示であり、本発明を限定するものではない。
【０１８２】
本明細書に関する限り、「具備する（comprising）」という言葉は、「主要な要素として含むが、必ずしも単独に含むのではない」又は「有する(having)」又は「含む(including)」という意味であり、「その要素のみから構成される」という意味ではない。「comprise」及び「comprises」などの「comprising」という言葉の変形は、相応して変更された意味を有するものである。
【図面の簡単な説明】
【０１８３】
【図１Ａ】画像中に埋め込まれた直線及び直線を定義するパラメータを示す図である。
【図１Ｂ】極座標空間において図１Ａの直線を定義するパラメータを示す図である。
【図２Ａ】歪前及び歪後の極座標空間における同一の３本の線のパラメータ対を示す図である。
【図２Ｂ】歪前及び歪後の極座標空間における同一の３本の線のパラメータ対を示す図である。
【図３】画像からアフィン歪のパラメータを検出する方法を概略的に示すフローチャートである。
【図４】電子透かしを使用して直線を埋め込む方法を概略的に示すフローチャートである。
【図５】説明される構成を実施できる汎用コンピュータを概略的に示すブロック図である。
【図６】線の方向付け角度βnが全角度範囲にわたり一様に分布するように配列された４本の線を示す図である。
【図７】線分の長さ比をパラメータeの関数として示す図である。
【図８】電子透かしとして使用されてもよいパターンの一例を示す図である。
【図９】擬似極座標空間で表された図８に示される例の歪前のパターンの射影を示す図である。
【図１０】第２の画像が第１の画像のアフィン歪バージョンであるか否かを推定する方法を概略的に示すフローチャートである。
【技術分野】
【０００１】
本発明は、一般に、画像処理に関し、特に、画像間のアフィン関係を推定することに関する。
【背景技術】
【０００２】
背景
電子透かしは、情報を知覚不可能に画像中に埋め込むために頻繁に使用される。しかし、一般に使用されている電子透かしの多くは、スケーリング、回転、せん断歪(shearing)、アナモフィックスケーリング(anamorphic scaling)などの歪により破壊される。電子透かし検出方法の中には、平行移動を感知するものさえある。
【０００３】
これまで、電子透かしを検出するための様々な方法が提案されてきたが、それらの方法のいくつかは、アフィン歪に対して不変であるといえる。しかし、アフィン歪に対して不変である方法の多くは、いずれかの段階で、アフィン歪を定義するパラメータの空間全体にわたる広範囲の検索を必要とする。そのような検索は、多次元であり、通常、相当に大きな計算容量を消費すると考えられる。
【０００４】
最近、まず平行移動を除去し、次にスケーリング及び回転を２つの直交方向の別の平行移動効果とする変換を実行することにより、検索空間を縮小するいくつかの方法が提案されている。それらの方法は、ＲＳＴ（回転、スケール及び平行移動）に対して不変な方法として知られる。通常、この技術は埋め込み手順と検出手順との相補性を必要とする。
【０００５】
他の技術は、回転対称などの特殊な対称特性を有するパターンを埋め込み、次に、非対称歪パラメータの広範囲な検索によりそれらのパターンを検出することに依存する。
【０００６】
上述の方法はいずれも完全アフィン歪の不変性を有していないため、完全不変性を確保するためには、歪パラメータ空間のうちの１つ以上の広範囲な検索が依然として必要とされる。従って、パラメータ空間の広範囲にわたる検索を必要とせずに、アフィン歪のパラメータを推定する方法が必要とされる。
【発明の開示】
【０００７】
概要
本発明の目的は、既存の構成の１つ以上の欠点を克服すること又は少なくとも改善することである。
【０００８】
上述の問題に対処する構成が開示される。かかる構成は、画像に埋め込まれた線の交点と画像の歪バージョンに埋め込まれた線の交点との対応性を識別することにより、画像に適用されたアフィン歪のパラメータを推定するものである。
【０００９】
本発明の１つの側面によれば、各々が少なくとも４本の互いに平行でない線を有する第１の画像と第２の画像との間のアフィン関係を推定する方法であって、
前記第１の画像中に現れる前記線の第１の組の交点を識別するステップと、
前記第２の画像中に現れる前記線の第２の組の交点を識別するステップと、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係が存在するか否かを判定するステップとから成り、前記関係が存在する場合、前記第１の画像及び前記第２の画像はアフィン関係にある方法が提供される。
【００１０】
本発明の別の側面によれば、補助パターンを有し、少なくとも４本の互いに平行でない線を有し、前記線が所定の位置で第１の組の交点を形成する第１の画像のアフィン歪バージョンである第２の画像の中の前記補助パターンを検出する方法であって、
前記第２の画像中に現れる前記線の第２の組の交点を識別するステップと、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係を識別するステップと、
前記第１の組の交点及び前記第２の組の交点を使用して、前記アフィン歪パラメータを推定するステップと、
歪補助パターンを形成するために、前記アフィン歪パラメータにより定義される前記アフィン歪を前記補助パターンに適用するステップと、
前記第２の画像中の前記歪補助パターンを検出するステップとから成る方法が提供される。
【００１１】
本発明の更に別の側面によれば、上記の方法のうちのいずれか１つを実現するための装置が提供される。
【００１２】
本発明の別の側面によれば、先に説明された方法のうちのいずれか１つを実現するためのコンピュータプログラムが記録されたコンピュータ可読媒体を含むコンピュータプログラム製品が提供される。
【００１３】
本発明の他の面も開示される。
【発明を実施するための最良の形態】
【００１４】
添付図面のうちのいずれか１つ以上において、同一の図中符号を有するステップ及び／又は特徴が参照される場合、以下の説明中、特に指示のない限り、それらのステップ及び／又は特徴は同一の機能又は動作を有するものとする。
【００１５】
図１Ａに一例が示されるような画像中の１本の直線nについて考える。直線nを表現する方法がいくつかあることは、当業者には理解されるであろう。例えば、直線nを表現するために２つの点が使用されてもよい。また、直線nは、画像に埋め込まれてもよく、あるいは画像中の１つ以上の特徴と関連付けられてもよい。
【００１６】
直線nは、デカルト座標の縦軸（Ｙ軸）に対して角度βnをなし、直線nに対して垂直な方向に、座標の原点から距離rnの位置にある。直線nは、１対のパラメータ{rn, βn}により一意に記述される。図１Ｂは、極座標空間において直線nを定義するパラメータ対{rn, βn}を示す。
【００１７】
再び図１Ａを参照すると、直線n上の１点(x, y)及び直線nに沿った距離λnは、標準形式で次のように表されてもよい。
【００１８】
【数１】
【００１９】
ここで、直線nを含む画像に適用される一般的なアフィン歪を考える。アフィン歪は、回転、スケーリング、せん断歪、鏡映、平行移動及びアナモフィックスケーリングのうちの１つ以上を含んでもよい。アフィン歪後の当初の点(x, y)の画像中の変換座標を(x〜, y〜)とすると、点(x〜, y〜)は次のように表される。
【００２０】
【数２】
【００２１】
式中、aijは、回転、スケーリング、せん断歪、鏡映及びアナモフィックスケーリングを定義するパラメータであり、(x0, y0)は、平行移動を定義する。ここで、以下のように仮定する。
【００２２】
【数２−２】
【００２３】
更に、以下に示す場合は、鏡映が起こったことを示す。
【００２４】
【数２−３】
【００２５】
パラメータaijにより適用される総歪(total distortion)は、次のように、基本歪(prime distortions)、すなわち回転、アナモフィックスケーリング(anamorphic scaling)及びせん断歪の組み合わせに分解されてもよい。
【００２６】
【数３】
【００２７】
式中、角度ωの回転は、以下の行列により表される。
【００２８】
【数４】
【００２９】
Ｘ軸及びＹ軸に沿ったアナモフィックスケーリングは、アスペクト比変化(aspect ratio change)と呼ばれる場合もあり、次の形式を有する。
【００３０】
【数５】
【００３１】
ｘ方向のせん断歪は、次の形式を有する。
【００３２】
【数６】
【００３３】
また、|ω|≦４５°であるように、回転歪を正しい象限に配置するために適用される転位(transposition)は、次の４つのオプションのうちの１つから選択される。
【００３４】
【数７】
【００３５】
アフィン歪は、アフィン歪中、どの直線も線の平行性(parallelism of lines)と共に保持されるが、長さ及び角度は変化するという特性を有する。従って、画像中の直線nは変形後の画像中の直線に変換されるが、変形後の画像中の直線はパラメータ対{r〜n,β〜n}により定義される。このパラメータ対{r〜n,β〜n}は、通常、アフィン歪前の直線nのパラメータ対{rn,βn}とは異なる。
【００３６】
略語cn=cosβn、sn=sinβnを使用すると、式（１）及び（２）から次の関係が成り立つ。
【００３７】
【数８】
【００３８】
及び
【００３９】
【数９】
【００４０】
アフィン歪(affine distortion)を定義する６つの未知のパラメータ{a11, a12, a21, a22, x0, y0}を含む式（８）及び（９）によって、各直線nがパラメータ対{rn, βn}により定義される３本の直線を画像中に含め、アフィン歪画像(affine distorted image)中の３本の直線を検出し、アフィン歪直線(affine distorted line)ごとにパラメータ対{r〜n,β〜n}を判定し、式（８）及び（９）を解くことにより、パラメータ{a11, a12, a21, a22, x0, y0}が計算されてもよい。鏡映(reflection)を識別するために、直線を画像中に配置するとき、左右の非対称も要求される。
【００４１】
しかし、式（８）及び（９）から、直線にアフィン歪が適用される場合、一般に、パラメータ対{r〜n,β〜n}はかなり複雑で曖昧な方式で変換されることがわかる。この曖昧さは、直線nと平行な方向の平行移動又はスケーリングが、パラメータ対{rn,βn}に全く影響を及ぼさないために起こる。
【００４２】
また、アフィン歪前の画像中の直線nに対応する歪後の直線を識別することも明らかではない。これを例示するために、図２Ａは歪前の極座標空間における３本の線のパラメータ対{rn,βn}を示し、図２Ｂは歪後の同一の３本の線のパラメータ対{r〜n,β〜n}を示す。歪前と歪後のパラメータ対{rn,βn}及び{r〜n,β〜n}の対応性は、曖昧になり、その結果、縮退や、不確かさを招く可能性がある。
【００４３】
アフィン歪前とアフィン歪後の各直線の対応性を一意に識別するために、いくつかの技術が使用されてもよい。１つの技術は複数の線を埋め込む。この場合、線自体が一意性を有し、線の一意性はアフィン歪により破壊されない。例えば、各直線を一意に識別するために、それぞれ異なる型、色などを有する線が使用されてもよい。
【００４４】
アフィン歪の別の有用な特性は、１本の直線の２つの線分の比がアフィン歪に関して不変であるということである。好ましい実現形態においては、アフィン歪前とアフィン歪後の各直線の対応性を一意に識別するために使用されるのがこの特性である。
【００４５】
１つの画像の中にN本の直線があると考えると、各直線は、先の場合と同様に、パラメータ対{rn, βn}、ｎ＝１→により一意に記述され、ｎ≠ｍであるとき、角度はβn≠βmである。従って、それらの直線は互いに平行ではない。
【００４６】
直線は互いに平行ではないので、各直線はその長さに沿って他の直線と互いに交差する。N本の（互いに平行でない）直線の交点の最大数は、三角数N(N-1)/2である。直線mが直線kと交差する点(xkm, ykm)は、次のように表される。
【００４７】
【数１０】
【００４８】
式中、λkmは、直線ｍが交差する直線ｋに沿った距離である。同様に、距離λmkは、直線ｋが交差する直線ｍに沿った距離である。
【００４９】
式（１０）の連立方程式を解くと、距離λkmは次の式により表される。
【００５０】
【数１１】
【００５１】
直線の本数Ｎ＝４である場合を考える。各直線kは、他の３本の直線ｍとの間に３つの交点(xkm, ykm)を有するであろう。この段階で、直線kに沿ったそれぞれの交点(xkm, ykm)までの距離λkmを、大きさに従って次のように順序付けると有用である。
【００５２】
【数１２】
【００５３】
線分の長さξk1及びξk2を次のように定義すると、
【００５４】
【数１３】
【００５５】
及び
【００５６】
【数１４】
【００５７】
直線ｋの長さ比Ｒkは次のように定義される。
【００５８】
【数１５】
【００５９】
直線のパラメータ対{rn, βn}を適切に選択すると、各直線kの比Ｒkは、他のどの直線ｍの長さ比とも明確に異なる。比Ｒkは、アフィン歪に関して不変であるため、アフィン歪前とアフィン歪後の各直線の対応性を一意に判定できる。
【００６０】
対応する直線が識別されたならば、直線kにより表現される各方向に沿ったスケーリング係数を推定するために、アフィン歪前とアフィン歪後の異なる直線に沿った距離λkmが比較されてもよい。また、アフィン歪の回転成分を推定するために、各直線の向きの変化が使用されてもよい。
【００６１】
式（４）及び（５）にそれぞれ定義されるように、当初の画像に回転が適用され、続いてアナモフィックスケーリング(anamorphic scaling)が適用された特定のケースを考える。アナモフィックスケーリングは、水平デカルト座標軸（Ｘ軸）と平行な方向に係数Aのスケーリングを有し、それに対して垂直な方向に係数Bのスケーリングを有する。角度ωは回転角である。一般に、角度βnにおける長さlnの線分は、角度β〜nで長さl〜nの線分にマッピングされる。このとき、
【００６２】
【数１６】
【００６３】
【数１７】
【００６４】
式（１６）及び（１７）は、３つの未知数、すなわち、スケーリング係数Ａ及びＢ並びに角度ωを含む。当初の画像に４本の線が埋め込まれているので、次のように、長さlnとして、各直線の外側の交点の距離を使用すると、
【００６５】
【数１８】
【００６６】
４対の式が得られる。最小２乗方法を用いて、このような過剰制約付き系(over-constrained system)を解くことができる。
【００６７】
尚、式（１６）及び（１７）は、平行移動に対して不変であり、平行移動(x0, y0)を想定しない。また、計算されるべき式（２）で定義される一般アフィン歪の全てのパラメータに対して、式（４）及び（５）の行列は式（３）におけるように組み合わされるが、せん断歪係数Ｒは０である。
【００６８】
あるいは、アフィン歪前とアフィン歪後の各直線の対応性から、パラメータ対{rn, βn}及び{r〜n, β〜n}の対応性が一意に判定される。式（１０）に式（１１）を代入すると、交点(xkm, ykm)は、次のように表される。
【００６９】
【数１９】
【００７０】
直線は互いに平行ではないので、sin(βk-βm)≠0である。実際の状況においては、sin2 (β〜k-β〜m)≧0.25が成立するように、それぞれの角度βk及びβmが選択される。これと同等に、直線k及びmが交差する角度は、30°＜|β〜k-β〜m|＜150°を満たす。
【００７１】
同様に、交点(xkm, ykm)に対応する変換後の点(x〜km, y〜km)は、次の式により表される。
【００７２】
【数２０】
【００７３】
式（１９）及び（２０）にパラメータ対{rn, βn}及び{r〜n,β〜n}を代入し、対応する交点(xkm, ykm)及び(x〜km, y〜km)を使用して式（２）を解くと、アフィン歪パラメータ{a11, a12, a21, a22, x0, y0}が得られる。
【００７４】
アフィンパラメータ推定の好ましい方法は、直線の交点(xkm, ykm)とアフィン歪後の交点(x〜km, y〜km)との最小２乗フィッティング(least squares fitting)（ＬＳＦ）を使用する。交点(xkm, ykm)及び(x〜km, y〜km)の対応関係は既知であるため、このＬＳＦは大幅に簡略化される。交点(xkm, ykm)及び(x〜km, y〜km)の対応関係が一意に識別されなければ、可能な全ての順列、この場合には、６！=７２０について、ＬＳＦを評価する必要がある。
【００７５】
検出され、（一意に）順序付けされた交点を(x＾km, y＾km)により表すものとする。先の場合と同様に、当初の（歪前の）交点は(xkm, ykm)であり、歪後の交点は(x〜km, y〜km)である。誤差エネルギー(error energy)は、ユークリッドノルム尺度(Euclidean norm measure) Eとして定義される。
【００７６】
【数２１】
【００７７】
変換パラメータpに関する誤差エネルギー最小化(Error energy minimization) により、６つの式が得られる。
【００７８】
【数２２】
【００７９】
変換パラメータpは、変換を定義するパラメータa11、a12、a21、a22、x0及びy0（式（２））のうちの１つである。
【００８０】
幸いなことに、p=aijに関する偏導関数のために、式（２２）において表される６つの式は大幅に簡略化される。
【００８１】
【数２３】
【００８２】
そこで、式（２２）において表される６つの式は、以下の加算を整合することと同等である。
【００８３】
【数２４】
【００８４】
式（２２）及び（２３）からの全変換パラメータ(full transform parameters)を埋めることにより、同一の対称行列乗数(same symmetric matrix multiplier) Mを有する１対の３×３行列式が得られる。
【００８５】
【数２５】
【００８６】
【数２６】
【００８７】
【数２７】
【００８８】
行列Mの逆行列は、別の対称行列M-1である。
【００８９】
【数２８】
【００９０】
【数２９】
【００９１】
式（２５）及び（２６）を反転すると、６つの歪パラメータ全ての最小２乗推定(least squares estimate)のための最終解は次のように明示される。
【００９２】
【数３０】
【００９３】
【数３１】
【００９４】
最小誤差エネルギー(minimum error energy) Eは、式（２１）を用いて計算されてもよく、許容限界(allowable limit)と比較されてもよい。誤差エネルギーEが許容限界より大きい場合、アフィン整合(affine match)が探索されなかったと想定される。交点(xkm, ykm)及び(x〜km, y〜km)を比較することにより、最大点偏差(maximum point deviations)を計算することも可能であり、これは推定される歪の信頼性尺度(reliability measure)を確定する上で有用である。特に信頼性推定に関して有用な別のパラメータは、正規化エネルギー(normalized energy)、すなわち、任意の点の集合ｎ＝1→Ｍに対して次のように定義される中心平均２乗点分布(centred mean square point distribution) Gにより誤差エネルギーE(error energy)を除算した値である。すなわち、
【００９５】
【数３２】
【００９６】
式中、測定された点分布の重心(centroid)は、(x＾￣n,y＾￣n)として定義される。
【００９７】
図３は、少なくとも４本の互いに平行でない直線を含む画像からアフィン歪のパラメータを検出する方法２００の概略的なフローチャートを示す。一実施形態においては、互いに平行でない直線は、それらの直線が人間の目に見えないように画像中に埋め込まれる。図４は、電子透かしを使用して直線を埋め込む方法３００の概略的なフローチャートを示す。
【００９８】
方法２００及び３００は、図５に示されるような汎用コンピュータシステム１００を使用して実施されるのが好ましい。その場合、方法２００及び３００のステップは、コンピュータシステム１００内部で実行するソフトウェアとして実現される。特に、方法２００及び３００のステップは、コンピュータシステム１００により実行されるソフトウェア中の命令により実現される。ソフトウェアは、例えば、以下に説明される記憶装置を含むコンピュータ可読媒体に格納されてもよい。ソフトウェアは、コンピュータ可読媒体からコンピュータにロードされ、コンピュータシステム１００により実行される。そのようなソフトウェア又はコンピュータプログラムが記録されたコンピュータ可読媒体は、コンピュータプログラム製品である。
【００９９】
コンピュータシステム１００は、コンピュータモジュール１０１と、キーボード１０２、マウス１０３及び撮像装置(imaging device)１２２などの入力装置と、プリンタ１１５及び表示装置１１４を含む出力装置とにより形成される。撮像装置１２２は、デジタル画像を収集するために使用されるスキャナ又はデジタルカメラであってもよい。変復調器（モデム）トランシーバ装置１１６は、例えば、電話回線１２１又は他の機能媒体を介して接続可能な通信ネットワーク１２０との間で通信を実行するために、コンピュータモジュール１０１により使用される。
【０１００】
通常、コンピュータモジュール１０１は、少なくとも１つのプロセッサユニット１０５と、例えば、半導体ランダムアクセスメモリ（ＲＡＭ）及び読み取り専用メモリ（ＲＯＭ）から形成されるメモリユニット１０６とを含む。モジュール１０１は、ビデオ表示装置１１４に結合するビデオインタフェース１０７、キーボード１０２、マウス１０３及び撮像装置１２２に対応する入出力（Ｉ／Ｏ）インタフェース１１３並びにモデム１１６及びプリンタ１１５に対応するインタフェース１０８を含む複数のＩ／Ｏインタフェースを更に含む。記憶装置１０９が設けられ、通常、記憶装置１０９は、ハードディスクドライブ１１０及びフロッピー（登録商標）ディスクドライブ１１１を含む。ＣＤ‐ＲＯＭドライブ１１２は、通常、不揮発性データ源として設けられる。通常、コンピュータモジュール１０１の構成要素１０５〜１１３は、当業者には周知の従来のコンピュータシステム１００の動作モードが得られるように相互接続バス１０４を介して通信する。
【０１０１】
通常、ソフトウェアは、ハードディスクドライブ１１０に常駐し、プロセッサ１０５により読み取られ、ソフトウェアの実行はプロセッサ１０５により制御される。場合によっては、ソフトウェアは、ＣＤ‐ＲＯＭ又はフロッピー（登録商標）ディスクに符号化された形でユーザに供給され、対応するドライブ１１２又は１１１により読み取られてもよく、あるいはユーザによりネットワーク１２０からモデム装置１１６を介して読み取られてもよい。更に、他のコンピュータ可読媒体からコンピュータシステム１００へソフトウェアをロードすることも可能である。
【０１０２】
少なくとも４本の互いに平行でない直線を含む画像からアフィン歪のパラメータを検出する方法２００及び電子透かしを使用して直線を埋め込む方法３００は、上述のようなソフトウェアではなく、方法の機能又は部分機能を実行する１つ以上の集積回路などの専用ハードウェアにおいて実現されてもよい。そのような専用ハードウェアは、グラフィックプロセッサ、デジタルシグナルプロセッサ又は１つ以上のマイクロプロセッサ及び関連メモリを含んでも良い。
【０１０３】
まず図４を参照すると、パラメータ対{rn, βn}により各直線nが定義されるような複数の直線を電子透かしを使用して埋め込む方法３００はステップ３１０で始まり、ステップ３１０においては、各直線nと関連するパターンが生成される。
【０１０４】
埋め込まれるべき直線のパラメータ対{rn,βn}を選択する場合、１つのオプションは、全角度範囲にわたり一様に分布する角度βn、すなわち、０°、４５°、９０°、１３５°を有する４本の直線を選択することである。図６は、そのように配列された４本の直線を示す。
【０１０５】
４本の直線のいくつかの配列は、極めて対称性の高い結果をもたらす。図示される配列はそれほど対称ではない。この配列は、配列の鏡映歪バージョン(reflected and distorted version)と明確に識別できる６つの交点(xkm, ykm)を含む。３本以上の線が１点で出会う縮退配列(degenerate arrangement)においては、交点は６つより少なくなることも可能であるが、ここではそのようなケースを考慮しない。
【０１０６】
図６には、別のパラメータeに基づいて、線分６００の長さpに関連して定義されたn=１〜４に対する線分の長さξn1及びξn2も示される。パラメータeの関数として式（１５）で定義される線分の長さ比Rnは、式（１８）で定義される線分の長さlnと共に、表１に示されるように計算される。
【０１０７】
【表１】
【０１０８】
図７は、線分の長さ比Rnをパラメータeの関数として表す。特定の値e≒0.31により、全く異なる４つの別個の長さ比Rnが求められることが図７からわかる。別の興味深い有用な長さ比Rnの集合は、e=0.5に対して現れる。この場合、４本の直線の全てが中心の基準点から等距離にある。それらの等距離がアフィン歪により均等に変換されない可能性があるため、第７の点はせん断歪又はアナモフィックスケーリングに対して真の不変性を維持しない点であるが、本質的には第７の点を定義できる。
【０１０９】
好ましい実施形態（e=0.31）においては、４本の直線は次のようなパラメータを伴って埋め込まれる。
【０１１０】
【数３３】
【０１１１】
式中、pは画像幅に設定される。尚、rnに対応する角度βnが１８０°回転されるのであれば、負の値であるrnはそれを相補する正の値と等価である。
【０１１２】
好ましい方向付け角度βnを選択することにより、いずれか１本の直線nと画像境界(image boundaries)との一致は最大限に回避される。
【０１１３】
直線が電子透かしとして埋め込まれる場合、各電子透かしは、電子透かしが埋め込まれている画像がアフィン歪を受けた後であっても検出可能であるという特性を有していなければならない。好ましい実施形態によれば、各パターンは一方向にのみの変化を有し、その方向は直線nに対して垂直である。パターンは軸を更に有し、その軸は線と一致する（奇数又は偶数）対称の軸又は指定された軸であってもよい。通常、パターンは、変化の方向に適用される１次元基底関数(one-dimensional base function)から生成され、軸と平行に繰り返される。
【０１１４】
好ましい実施形態においては、基底関数は下記の形態の複素同次関数(complex homogeneous function)である。
【０１１５】
【数３４】
【０１１６】
式中、vは１次元座標であり、必ずしも正ではない。α及びpは定数である。基底関数g(v)は、基底関数がパターン画像のナイキスト周波数(Nyquist frequency)を超える周波数を有する領域において減衰されるのが好ましい。式（３４）は、位相関数(phase function)を振幅変調(amplitude modulating)する振幅関数(amplitude function)としても考えられ、その場合、位相関数は対数位相(logarithmic phase)を有する。そのような複素同次関数g(v)が、例えば係数aによってスケーリングされる場合、スケーリングは次のような複素定数係数(complex constant factor)のみを導入する。
【０１１７】
【数３５】
【０１１８】
複素同次関数の利点は、複素同次関数の自己相関(auto-correlation)が複素同次関数のスケールバージョン(scaled version)を伴う複素同次関数の相互相関(cross-correlation)に正比例することである。この「スケール不変(scale-invariant)」特性は、スケール変換後であっても、画像を基底関数と相関することにより画像中の電子透かしの検出を可能にする。
【０１１９】
図８は、式（３４）の基底関数の実数部を使用して次のように生成されるパターンの一例を示す。
【０１２０】
【数３６】
【０１２１】
尚、パターン画像のナイキスト周波数を超える周波数を有する値を除去するために、対称軸に隣接する領域において、マスキングが適用されている。パターンとそのパターンに埋め込まれた直線との関係も示される。直線自体はパターンの一部を形成せず、次のステップにおいては画像に追加されないことが理解される。この例のパターンを示すに際して、パターン値は[0,255]の範囲の値にマッピングされており、０の値は黒色として表現され、２５５の値は白色として表現される。
【０１２２】
再び図４を参照すると、ステップ３１０においては、１つのパターン画像を形成するために、複数の別個のパターンが加算される。パターン画像は、生成後にメモリ１０６又はＨＤＤ１１０に格納されてもよい。
【０１２３】
観測者が知覚不可能なパターンを埋め込むために、ステップ３２０において、メモリ１０６からパターン画像が検索され、低輝度変化(low intensity variation)を有する画像の領域に対応するパターンのレベルを大幅に減少し、且つ高輝度変化(high intensity variation)を有する画像の領域に対応するパターンのレベルをそれより少ない量だけ減少するために、パターン画像はプロセッサ１０５により知覚マスキングされる。輝度変化の尺度の一例は、画像中の輝度の局所勾配の大きさである。他の尺度には、輝度の偏導関数、「エネルギー」又は周波数コンテンツの局所推定値(local estimates)、局所分散(local variance)及び更に精巧な人間の視覚系統のマスキングの推定値などがある。
【０１２４】
ステップ３３０において、知覚マスキングされたパターン画像が画像に追加される。このパターン画像は電子透かしと呼ばれてもよい。画像がカラー画像である場合、電子透かしはカラー画像の輝度部分に追加されるのが好ましい。これにより、電子透かし入り画像がカラーからグレイスケール表現に変換されるときに電子透かしは残存できる。あるいは、電子透かしは、カラー画像のＲ、Ｇ、Ｂ、Ｈ、Ｖ、Ｓ、ｕ、ｖなどのチャネルのうちの１つ以上又はそれらのチャネルの何らかの組み合わせに追加されてもよい。画像への電子透かしの追加は、単純な代数加算の他にディザリング及びハーフトーン化を更に含む。複素基底関数の実数部及び虚数部が、カラー画像の２つ以上のチャネルに独立して追加されてもよい。
【０１２５】
電子透かしが埋め込まれた画像は、tiff、gif、jpeg、mpegなどのデジタル画像フォーマットで記憶装置１０９（図５）に格納されてもよい。電子透かし入り画像のハードコピーを作成するために、電子透かし入り画像はプリンタ１１５（図５）で印刷されてもよく、あるいはネットワーク１２０を使用して別のコンピュータモジュール１０１へ通信されてもよい。
【０１２６】
画像中に直線が埋め込まれ、画像がアフィン歪を受けているため、直線及びそのパラメータ対{r〜n,β〜n}が検出されなければならない。図４を参照して説明したように、電子透かしを使用して直線が埋め込まれているので、次に図３を参照して、画像からアフィン歪のパラメータを検出する方法２００を説明する。方法２００はステップ２０２で始まり、ステップ２０２において、歪画像のデジタルコピーが獲得される。通常、画像は既にデジタル画像フォーマットになっており、記憶装置１０９（図５）に格納されてもよい。そのような場合、画像は画素値のアレイに変換される。その時点で画像が写真などのハードコピーフォーマットのままである場合には、まず、撮像装置１２２（図５）を使用してハードコピーを走査することにより、ハードピー画像はデジタルフォーマットに変換される。
【０１２７】
続くステップ２０５において、プロセッサ１０５は、まず、画像から知覚マスクを形成し、次に、画像の値を知覚マスクの対応する値で除算することにより画像を知覚マスクで強調し、知覚マスキングを解消する。尚、近似知覚マスクが適切である。
【０１２８】
次に、ステップ２１０において、得られた画像に射影変換(projective transform)が適用される。射影変換は、画像中の直線に沿って値を加算することによりエネルギーを累積する。ラドン（Radon）（又は等価のHough）変換は、ステップ２１０において使用されてよい射影変換の１つであり、次のように定義される。
【０１２９】
【数３７】
【０１３０】
離散型データセットに対してラドン変換(Radon transform)の実施形態を導き出すために、画像関数h（x, y）の射影(projection)とその関数のフーリエ変換のスライスとの対応性が使用されるが、その対応性は、「射影‐スライス定理(projection-slice theorem)として知られる。
【０１３１】
射影‐スライス定理は、２次元関数の射影の１次元フーリエ変換がその関数の２次元フーリエ変換の半径方向のスライス(radial slice)に等しいと規定する。尚、
【０１３２】
【数３８】
【０１３３】
であり、式中、H(u, v)は画像h(x, y)の２次元（２Ｄ）フーリエ変換である。擬似極座標空間(quasi polar space)において、角度は範囲(-π/2, π/2)であり、距離は範囲(-∞, ∞)にある。フーリエドメイン(Fourier domain)において擬似極座標(quasi-polar coordinate)(q,φ)を定義することにより、座標変換は、u=qcosφ、v＝qsinφであり、射影‐スライス定理の１つの形態は、次のように、ラドン射影角(Radon projection angle) φ＝θに対応するフーリエ極座標角(Fourier polar angle)について求められる。
【０１３４】
【数３９】
【０１３５】
式（３９）により離散的画像の２Ｄ‐ＦＦＴの半径方向のスライスとしてラドン射影の（フーリエ変換の）推定が可能になるため、式（３９）は有用である。これは、まず、２Ｄ-ＦＦＴを実行し、続いて、再サンプリング(resampling)を実行するためにbicubic又はchirp-zなどの適切な補間を使用してデカルト座標から極座標への再マッピング(remapping)を実行することにより、離散的ラドン変換(discrete Radon transform)を評価できることを示唆する。
【０１３６】
方向付け角度(orientation angle)β〜n及び垂直変位(perpendicular displacement) r〜nを有する１次元基底関数g(v)に基づいてN個のパターンが埋め込まれている画像h(x, y)は、画像自体の画素値を無視すると、次のように書き表される。
【０１３７】
【数４０】
【０１３８】
方向付け角度(orientation angle)β〜nにある１つの方向にのみ変化を有するパターンに射影変換が適用された場合、角度θが角度θの他の全ての値と比較される方向付け角度β〜nに等しいときに、射影の値は著しく大きくなる。図９は、図８に示される歪前のパターンの例の射影を擬似極座標空間(quasi-polar space)において示す図である。角度θが角度βｎと等しいとき、射影の値は特に大きくなることがわかる。射影は、オフセット距離rnに関して対称性を更に有する。
【０１３９】
従って、式（４０）の関数に対してラドン変換(Radon transforms)を適用することにより、以下に示されるような関数のラドン変換はθ＝β〜nである線に制約されることがわかる。
【０１４０】
【数４１】
【０１４１】
ラドン変換を用いることにより、パターンg(v)が埋め込まれた画像関数(image function)h(x, y)を擬似極座標空間内のN本の直線に集中したので、極座標角(polar angle) θの全ての値に対して１-Ｄ擬似半径方向相関(1-D quasi-radial correlations)（座標rにおける）を用いることにより、更に、各直線に含まれるエネルギーを単一の点（又は１つの点の付近の狭い領域）に集中することが可能である。
【０１４２】
従って、続くステップ２２０において、プロセッサ１０５は、極座標角θの可能な全ての値に対して、擬似半径方向座標(quasi-radial coordinate)rにおける射影(projection)と基底関数(base function)g(v)との１-Ｄ相関(1-D correlations)を実行する。用語「相関(correlation)」は、位相相関(phase correlation)及びエネルギーによりスケーリングされた位相相関を更に含む。その結果得られる相関は、擬似極座標(r＾n,β＾n)にピークを有する。
【０１４３】
ステップ２３０において、プロセッサ１０５は相関の絶対ピーク(absolute
peaks)を探索する。各歪埋め込みパターンの方向付け角度(orientation angle)β〜n及び垂直変位(perpendicular displacement)r＾nは、ピークの擬似極座標(r＾n,β＾n)から直接求められる。また、埋め込み直線のパラメータ対{rn, βn}も利用可能である。
【０１４４】
検出器の前処理段階は、最高相関大きさピーク(highest correlation magnitude peaks)に基づいて、通常は約６４本である複数の候補線を探索する。この数から、４本の直線の全ての組み合わせが精査される。可能な組み合わせの数は、６４！／（６０！４！）=６３５３７６である。４本の直線の角度の中に、少なくとも１５°の差を有していない直線が存在する場合、その組み合わせは放棄され、次の段階に進まない。直線の１つの組み合わせがこの段階をパスしたと仮定すると、その後、式（１９）を用いて６つの交点が計算され、４組の線分比R＾nが評価される。線分比R＾nは、この後、サイズが大きくなる順に配列される。次に、予測線比(expected line ratios)（同様に、サイズが大きくなる順に配列される）に対する当てはめの近接度(closeness)に関するメリット関数(merit function)が次のように評価される。
【０１４５】
【数４２】
【０１４６】
ある閾値（好ましくは０．１）以下のメリット関数を有する全ての組み合わせは、その後の処理に際して、「候補組み合わせ(candidate combinations)」としてラベル付けされる。
【０１４７】
尚、他のメリット関数も使用可能である。例えば、線強度(line strength)（線相関大きさ(line correlation magnitude)に関する）を反映し、それにより検出レベルが劣る線からの寄与を減少するために、上記のメリット関数を重み付けすることも可能である。
【０１４８】
次に、候補組み合わせごとに、以下の処理が実行される。
【０１４９】
ステップ２４０において、プロセッサは、アフィン歪前とアフィン歪後の各直線nの対応性を一意に識別する。好ましい実現形態においては、歪後の線の長さ比R＾nは歪前の長さ比Ｒ＾nと整合され、式（１５）に関連して説明されたように、アフィン歪前とアフィン歪後の各直線の対応性を一意に識別するために使用される。
【０１５０】
アフィン歪前とアフィン歪後の各直線の対応性を一意に識別するために使用されてもよい別の技術は、各直線を埋め込むためにそれぞれ異なるパラメータを有する基底関数を使用する方法である。そのような実現形態においては、基底関数ごとにステップ２２０及び２３０が繰り返される。
【０１５１】
次のステップ２５０においては、プロセッサ１０５は、式（２０）を使用して交点 (x＾km,y＾km)を計算する。最後に、ステップ２６０において、式（２１）〜（３２）に関連して先に説明されたＬＳＦを用いて、アフィン歪パラメータ{a11, a12, a21, a22, x0, y0}が推定される。
【０１５２】
最終的なアフィン歪パラメータは、全ての候補組み合わせに対して最低の最小誤差エネルギー(lowest minimum error energy) Ｅ（式（２１））を生成するパラメータになるように選択される。
【０１５３】
アフィン歪パラメータ{a11, a12, a21, a22, x0, y0}が推定されたならば、アフィン歪は反転されてもよく、これは矯正(rectification)又はレジストレーション(registration)と呼ばれることもある。
【０１５４】
アフィン歪が反転された後、相関処理を経て擬似ランダムノイズ（pseudo random noise）（ＰＲＮ）シーケンスの検出などの従来の方法を使用して、ステップ３３０（図４）においてパターンを追加する以前に画像中に存在していた補助パターンと名付けられた追加パターンが検出されてもよい。そのような処理は、スペクトル拡散電子透かし(spread-spectrum watermarking)としても知られており、幾何学歪(geometric distortion)に対して極めて高い感度を示すことで知られている。通常、数パーセントのスケールの変化でも相関を実質的に破壊するのに十分であり、そのため、わずかにひずんだ画像の中のＰＲＮを検出することは不可能である。
【０１５５】
しかし、画像の歪を除去し、整列する処理は、補間及び再サンプリングを含み、これらの処理は、通常、計算のために高いコストを必要とする。従って、補助パターンを検出するときに相補歪を含む検出テンプレートを使用することにより、画像を矯正するのを回避することが提案される。
【０１５６】
この方式の大きな利点は、テンプレートをフーリエドメインで定義できることである。空間ドメインにおけるアフィン歪は、平行移動歪に関連する線形位相係数(linear phase factors)と共に、フーリエドメインにおける対応するアフィン歪をもたらす。フーリエアフィン対応性(Fourier affine correspondence)は、文献に十分詳細に記載されている。本質的には、式（２）のフーリエバージョンがテンプレートに適用される。連続フーリエ変換を次のように定義し、離散的にサンプリングされた画像並びに離散フーリエ変換（ＤＦＴ）に厳密に対応する関係が適応されることに注意すると、その更に効率のよい実現形態である高速フーリエ変換（ＦＦＴ）は、次のようになる。
【０１５７】
【数４３】
【０１５８】
歪テンプレート関数のフーリエ変換は、次の通りである。
【０１５９】
【数４４】
【０１６０】
フーリエドメインにおける式（２）のアフィン歪は、次の式により表される。
【０１６１】
【数４５】
【０１６２】
ここで、式中、係数κは実正規化定数(real normalization constant)及び線形位相係数(linear phase factor)を含むが、歪フーリエテンプレート(distorted Fourier template)J(u〜,v〜)には影響を及ぼさないので、歪フーリエテンプレートJ(u〜,v〜)は相関検出のフーリエドメインにおける実現形態で直接使用される。従って、フーリエテンプレート(Fourier template)J(u〜,v〜)が確定的な解析関数記述子(analytic functional descriptor)により定義されるのであれば、補間(interpolation)又は再サンプリング(resampling)の必要なく、いくつかのテンプレートj(x, y)は、式（４５）を使用して歪を受けてもよい。テンプレート整合前(template matching)に、フーリエ座標u及びvのみが歪を受けるだけでよい。
【０１６３】
例えば、ＵＲＬ又はＵＲＬに対するポインタを使用して、何らかのデータ又はそのデータに対するポインタを符号化するために、補助パターンが使用されてもよい。また、画像からアフィン歪のパラメータを検出する方法２００を使用すると、その画像の何らかの特性に関するデータ又は特性を参照するデータであるいわゆる画像メタデータは、画像がひずんでいたとしても、画像からメタデータを検索できるという意味で画像に拘束されることになる。メタデータが対抗できる歪は上述の射影変換を含むが、印刷、写真複写／複写、走査、色除去、ガンマ修正(gamma correction)、ガンマ変更(gamma change)、ＪＰＥＧ圧縮／一般圧縮(general compression)、フォーマット変換（すなわち、ＢＭＰからＧＩＦへ）、ノイズ追加及びノイズ除去(noise addition and removal)、低域フィルタリング(low-pass filtering)などのフィルタリング、クロッピング(cropping)及び画像の基本認識可能度(basic recognizability)を維持するほぼ全ての編集操作(editing operations)を更に含む。
【０１６４】
いくつかの適用用途においては、直線を知覚不可能なように埋め込む必要がない。また、エングレービング(engraving)又はエッチング(etching)により任意の平坦な面に直線が埋め込まれてもよい。そのような平坦な面はシリコンウェハを含む。その場合、歪後の直線は、光学系（カメラなど）、電磁システム又は近接度に基づくシステムであってもよい何らかのシステムにより検出されてもよい。その後、検出された直線は、表面の位置及び向きを判定するために利用されてもよい。
【０１６５】
以上、N本の直線を埋め込むことに基づく実施形態を説明した。画像中の特徴と関連して複数本の直線を含む画像に対して、方法２００の改訂バージョンが適用されてもよい。そのような固有の直線に対して、可能な４本１組の直線の各組について４つの交差比(intersection ratios)を事前に制約することは不可能である。しかし、第１の画像における現存の直線比を第２の画像における現存の直線比と比較することは可能である。４つ１組の整合比(matching ratios)（任意の規定許容差範囲内）の各組について、方法２００のステップ２４０〜２６０を使用して対応するアフィン変換が計算される。その後、整合比の組ごとに、ステップ２４０〜２６０は繰り返される。対応するアフィン変換が一貫している（すなわち、アフィンパラメータがクラスタリング(clustering)を示す）場合、アフィン変換を経て、それら２つの画像が互いに関連している確率は高い。従って、２つの画像を比較し、第２の画像がアフィン変換を経て第１の画像と関連しているか否かを推定することは可能である。
【０１６６】
第１の画像I1 (x, y)がアフィン変換又は空間歪(spatial distortion)(x, y)→ (x〜,y〜)により第２の画像I2 (x, y)と関連付けられるものとする。尚、アフィン変換は、式（２）で定義される変換である。第１の画像I1 (x, y)と第２の画像I2 (x, y)との関係は、次のように書き表される。
【０１６７】
【数４６】
【０１６８】
式中、μは画像輝度増率(image intensity multiplying factor)（又は利得）であり、n(x, y)は第１の画像と第２の画像との差を考慮する関数である。
【０１６９】
従来の画像整合方法（例えば、相関を使用する）は、より一般的なアフィン歪に対しては容易に実現できないことが知られている。それは、一般に、６次元空間（６つのアフィンパラメータの）の全体にわたる検索が要求されるためである。従って、本発明の開示によれば、第１の画像I1 (x, y)と第２の画像I2 (x, y)とを比較するための更に有効な方法は、それらの画像自体の中で自然に発生する線構造(line structures)の交差比を比較するという方法である。多くの画像は、まっすぐな縁部(straight edges)などのいくつかの線構造又は部分線構造を含む。そのような線構造は、例えば、画素輝度の勾配の係数を使用することにより強調されるのが好ましい。ラプラシアン(Laplacian)などの他の演算子が使用されてもよい。
【０１７０】
図１０は、第２の画像I2 (x, y)が第１の画像I1 (x, y)のアフィン歪バージョンであるか否かを推定する方法４００の概略的なフローチャートを示す。方法４００も、図５に示される汎用コンピュータシステム１００を使用して実施されるのが好ましく、その場合、方法４００のステップは、コンピュータシステム１００の内部で実行されるソフトウェアとして実現される。
【０１７１】
方法４００はステップ４０２で始まる。ステップ４０２において、方法２００のステップ２１０に関連して先に説明されたように、画像I1 (x, y)及びI2 (x, y)の各々に対してラドン変換などの射影変換が適用される。
【０１７２】
実際には、ラドン変換後のエンハンスメントが好ましいことが明らかになっている。従って、続くステップ４０４において、勾配エンハンスメント(gradient enhancement)が実行され、その結果、画像ごとの２Ｄ-分布関数(2-D distribution function)Ωj (r, θ)が求められる。
【０１７３】
【数４７】
【０１７４】
ステップ４０６において、分布関数Ωj(r, θ)の各々でピークが検出される。その目的は、対応する４つ１組の線構造を探索することである。従って、各々の画像I1 (x, y)及びI2 (x, y)の中の３２個の最も重要な線構造を表現する各々の分布関数Ωj (r, θ)の中の３２個の最高ピークを探索することにより、４本の直線について可能な組み合わせの数は３５９６０通りとなる。
【０１７５】
次に続くステップ４０８において、プロセッサ１０５は、方法２００に関連して先に詳細に説明したように、４本の直線の組み合わせごとに４つのピークの(r, θ)値から交差比を計算する。ステップ４１０において、４つ１組の比の３５９６０通りの組み合わせは、順序付けシーケンス(ordered sequence)として配列される。先の場合と同様に、いずれかの比が１より大きい場合、それは反転される。シーケンスは、値が大きくなる順に順序付けされる。特に、４つ１組の比の全ての組み合わせは、第１の画像I1(x, y)に関して４次元テーブルに配列され、第２の画像I2 (x, y)に関しては別個のテーブルに配列される。
【０１７６】
次に、ステップ４１２において、第１の画像I1 (x, y)及び第２の画像I2 (x, y)の比シーケンス(ratio sequences)が比較される。特に、ユークリッド距離(Euclidean distance)又は式（４２）に示されるメリット関数(merit function)に基づいて、第１の画像I1 (x, y)のテーブルにおける各順序付けシーケンスと第２の画像I2 (x, y)のテーブル２における各順序付けシーケンスとの対応性が評価される。規定の距離の中の対応性のみが許容される。メリット関数の計算は、計算に関して相当に過酷であり、試される点(points)（シーケンス(sequences)）の数の２乗とも関連付けられる。更に効率のよい方式は、４Ｄ-比(4-D ratio)テーブルの粗ビンニング(coarse binning)を実行し（例えば、0.2のビン幅(bin widths)は、５４=６２５ビン(bins)を提供する）、単純に、対応するビン又は隣接するビンにおけるシーケンスのメリット関数を評価するという方法である。
【０１７７】
メリット関数が規定の量より小さい場合、４つ１組の直線は整合すると想定され、その結果、ステップ４１４において、式（２１）〜（３２）を使用して、アフィン変換パラメータが交点から計算される。メリット条件を満たす全ての整合シーケンスに対してステップ４１４が繰り返され、６つのアフィンパラメータが作表(tabulated)される。
【０１７８】
続くステップ４１６において、第１の画像I1 (x, y)と第２の画像I2 (x, y)とのアフィン関係の尤度(likelihood)が推定される。例えば、テーブル中のアフィンパラメータエントリの著しく大きなクラスタリング(clustering)が存在する場合、第１の画像I1 (x, y)と第２の画像I2 (x, y)とのアフィン関係又は整合の尤度は高い。クラスタリング統計からアフィン整合の尤度の更に定量的な推定を導き出すことができる。
【０１７９】
ステップ４１６において、第１の画像I1 (x, y)と第２の画像I2 (x, y)との整合の尤度が低いと考えられる場合、ステップ４１７において、例えば画像I1 (x, y)と画像I2 (x, y)との整合は存在しないことをユーザインタフェースに指示することにより、方法４００は終了する。しかし、第１の画像I1 (x, y)と第２の画像I2 (x, y)との整合の尤度が高いと考えられる場合には、ステップ４１８において、第１の画像I1 (x, y)が第２の画像I2 (x, y)と整合するように、第１の画像I1 (x, y)に対して逆アフィン歪(inverse affine distorted)が適用される。
【０１８０】
最後に、ステップ４２０において、正規化相関により整合のクオリティ(quality of the match)が判定される。0.9の値は、高レベルの整合を示すであろう。他の尺度（例えば、視覚）は、画像がどれほどよく整合するか及びアフィン歪パラメータがどれほど適切に推定されたかを更に適切に指示できるであろう。
【０１８１】
以上、本発明のいくつかの実施形態のみを説明したが、本発明の趣旨の範囲から逸脱せずに、上述の実施形態に対して変形及び／又は変形を実施できる。上述の実施形態は単なる例示であり、本発明を限定するものではない。
【０１８２】
本明細書に関する限り、「具備する（comprising）」という言葉は、「主要な要素として含むが、必ずしも単独に含むのではない」又は「有する(having)」又は「含む(including)」という意味であり、「その要素のみから構成される」という意味ではない。「comprise」及び「comprises」などの「comprising」という言葉の変形は、相応して変更された意味を有するものである。
【図面の簡単な説明】
【０１８３】
【図１Ａ】画像中に埋め込まれた直線及び直線を定義するパラメータを示す図である。
【図１Ｂ】極座標空間において図１Ａの直線を定義するパラメータを示す図である。
【図２Ａ】歪前及び歪後の極座標空間における同一の３本の線のパラメータ対を示す図である。
【図２Ｂ】歪前及び歪後の極座標空間における同一の３本の線のパラメータ対を示す図である。
【図３】画像からアフィン歪のパラメータを検出する方法を概略的に示すフローチャートである。
【図４】電子透かしを使用して直線を埋め込む方法を概略的に示すフローチャートである。
【図５】説明される構成を実施できる汎用コンピュータを概略的に示すブロック図である。
【図６】線の方向付け角度βnが全角度範囲にわたり一様に分布するように配列された４本の線を示す図である。
【図７】線分の長さ比をパラメータeの関数として示す図である。
【図８】電子透かしとして使用されてもよいパターンの一例を示す図である。
【図９】擬似極座標空間で表された図８に示される例の歪前のパターンの射影を示す図である。
【図１０】第２の画像が第１の画像のアフィン歪バージョンであるか否かを推定する方法を概略的に示すフローチャートである。
【特許請求の範囲】
【請求項１】
各々が少なくとも４本の互いに平行ではない線を有する第１の画像と第２の画像とのアフィン関係を推定する方法であって、
前記第１の画像中に現れる前記線の第１の組の交点を識別するステップと、
前記第２の画像中に現れる前記線の第２の組の交点を識別するステップと、
前記第１の組の交点及び前記第２の組の交点から、交点間に関係が存在するか否かを判定するステップとを備え、前記関係が存在する場合、前記第１の画像及び前記第２の画像はアフィン関係にあることを特徴とする方法。
【請求項２】
前記第１の組の交点及び前記第２の組の交点を用いて、アフィン歪パラメータを推定するステップを更に備えることを特徴とする請求項１に記載の方法。
【請求項３】
アフィン歪を反転するステップを更に備え、前記アフィン歪は、前記アフィン歪パラメータにより定義されることを特徴とする請求項２に記載の方法。
【請求項４】
正規化相関により前記関係の尺度を判定するステップを更に備えることを特徴とする請求項３に記載の方法。
【請求項５】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点の間に特有の線分比を有し、前記判定するステップは、
前記第２の画像中の各線の線分比を判定するサブステップと、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合するサブステップと、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別するサブステップとを備えることを特徴とする請求項１に記載の方法。
【請求項６】
前記線の各々は前記第１の画像中に１つのパターンを埋め込むことにより前記第１の画像中に埋め込まれ、各パターンは実質的に１次元基底関数から形成されており、前記方法は、
前記第２の画像の射影変換を計算する初期ステップと、
角度の選択するために、前記射影変換と前記基底関数との１次元相関を計算する初期ステップと、
前記相関のピークを探索する初期ステップとを備え、前記ピークの各々の位置は、前記埋め込みパターンのうちの１つのパターンの空間パラメータを提供することを特徴とする請求項１又は５に記載の方法。
【請求項７】
補助パターンと少なくとも４本の互いに平行でない線とを有し、前記線が所定の位置で第１の組の交点を形成する第１の画像のアフィン歪バージョンである第２の画像の中の補助パターンを検出する方法であって、
前記第２の画像中に現れる前記線の第２の組の交点を識別するステップと、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係を識別するステップと、
前記第１の組の交点及び前記第２の組の交点を用いて、前記アフィン歪パラメータを推定するステップと、
歪補助パターンを形成するために、前記アフィン歪パラメータにより定義される前記アフィン歪を前記補助パターンに適用するステップと、
前記第２の画像中の前記歪補助パターンを検出するステップとを備えることを特徴とする方法。
【請求項８】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点の間に特有の線分比を有し、前記交点間の関係を識別するステップは、
前記第２の画像中の各線の線分比を判定するサブステップと、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合するサブステップと、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別するサブステップとを備えることを特徴とする請求項７に記載の方法。
【請求項９】
前記線の各々は前記第１の画像中に１つのパターンを埋め込むことにより前記第１の画像中に埋め込まれ、各パターンは実質的に１次元基底関数から形成されており、前記方法は、
前記第２の画像の射影変換を計算する初期ステップと、
角度の選択するために、射影変換と前記基底関数との１次元相関を計算する初期ステップと、
前記相関のピークを探索する初期ステップとを備え、前記ピークの各々の位置は、前記埋め込みパターンのうちの１つのパターンの空間パラメータを提供することを特徴とする請求項７又は８に記載の方法。
【請求項１０】
各々が少なくとも４本の互いに平行でない線を有する第１の画像と第２の画像とのアフィン関係を推定する装置であって、
前記第１の画像中に現れる前記線の第１の組の交点を識別する手段と、
前記第２の画像中に現れる前記線の第２の組の交点を識別する手段と、
前記第１の組の交点及び前記第２の組の交点から、交点間に関係が存在するか否かを判定する手段とを備え、前記関係が存在する場合、前記第１の画像及び前記第２の画像はアフィン関係にあることを特徴とする装置。
【請求項１１】
前記第１の組の交点及び前記第２の組の交点を用いて、アフィン歪パラメータを推定する手段を更に備えることを特徴とする請求項１０に記載の装置。
【請求項１２】
アフィン歪を反転する手段を更に備え、前記アフィン歪は、前記アフィン歪パラメータにより定義されることを特徴とする請求項１１に記載の装置。
【請求項１３】
正規化相関により、前記関係の尺度を判定する手段を更に備えることを特徴とする請求項１２に記載の装置。
【請求項１４】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点間に特有の線分比を有し、前記判定する手段は、
前記第２の画像中の各線の線分比を判定する手段と、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合する手段と、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別する手段とを備えることを特徴とする請求項１０に記載の装置。
【請求項１５】
補助パターンと少なくとも４本の互いに平行でない線とを有し、前記線が所定の位置で第１の組の交点を形成する第１の画像のアフィン歪バージョンである第２の画像の中の補助パターンを検出する装置であって、
前記第２の画像中に現れる前記線の第２の組の交点を識別する手段と、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係を識別する手段と、
前記第１の組の交点及び前記第２の組の交点を用いて、前記アフィン歪パラメータを推定する手段と、
歪補助パターンを形成するために、前記アフィン歪パラメータにより定義される前記アフィン歪を前記補助パターンに適用する手段と、
前記第２の画像中の前記歪補助パターンを検出する手段とを備えることを特徴とする装置。
【請求項１６】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点の間に特有の線分比を有し、前記交点間の関係を識別する手段は、
前記第２の画像中の各線の線分比を判定する手段と、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合する手段と、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別する手段とを備えることを特徴とする請求項１５に記載の装置。
【請求項１７】
各々が少なくとも４本の互いに平行でない線を有する第１の画像と第２の画像とのアフィン関係を推定するためのコンピュータ可読媒体に格納されたプログラムであって、
前記第１の画像中に現れる前記線の第１の組の交点を識別するためのコードと、
前記第２の画像中に現れる前記線の第２の組の交点を識別するためのコードと、
前記第１の組の交点及び前記第２の組の交点から、交点間に関係が存在するか否かを判定するためのコードとを備え、前記関係が存在する場合、前記第１の画像及び前記第２の画像はアフィン関係にあることを特徴とするプログラム。
【請求項１８】
前記第１の組の交点及び前記第２の組の交点を用いて、アフィン歪パラメータを推定するためのコードを更に備えることを特徴とする請求項１７に記載のプログラム。
【請求項１９】
アフィン歪を反転するためのコードを更に備え、前記アフィン歪は、前記アフィン歪パラメータにより定義されることを特徴とする請求項１８に記載のプログラム。
【請求項２０】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点の間に特有の線分比を有し、前記判定するためのコードは、
前記第２の画像中の各線の線分比を判定するためのコードと、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合するためのコードと、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別するためのコードとを含むことを特徴とする請求項１７に記載のプログラム。
【請求項２１】
補助パターンと少なくとも４本の互いに平行でない線とを有し、前記線が所定の位置で第１の組の交点を形成する第１の画像のアフィン歪バージョンである第２の画像の中の補助パターンを検出するためのコンピュータ可読媒体に格納されたプログラムであって、
前記第２の画像中に現れる前記線の第２の組の交点を識別するためのコードと、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係を識別するためのコードと、
前記第１の組の交点及び前記第２の組の交点を用いて、前記アフィン歪パラメータを推定するためのコードと、
歪補助パターンを形成するために、前記アフィン歪パラメータにより定義される前記アフィン歪を前記補助パターンに適用するためのコードと、
前記第２の画像中の前記歪補助パターンを検出するためのコードとを備えることを特徴とするプログラム。
【請求項２２】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点間に特有の線分比を有し、前記交点間の関係を識別するためのコードは、
前記第２の画像中の各線の線分比を判定するためのコードと、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合するためのコードと、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別するためのコードとを備えることを特徴とする請求項２１に記載のプログラム。
【請求項２３】
実質的に添付の図面を参照して説明されることを特徴とする方法。
【請求項２４】
実質的に添付の図面を参照して説明されることを特徴とする装置。
【請求項１】
各々が少なくとも４本の互いに平行ではない線を有する第１の画像と第２の画像とのアフィン関係を推定する方法であって、
前記第１の画像中に現れる前記線の第１の組の交点を識別するステップと、
前記第２の画像中に現れる前記線の第２の組の交点を識別するステップと、
前記第１の組の交点及び前記第２の組の交点から、交点間に関係が存在するか否かを判定するステップとを備え、前記関係が存在する場合、前記第１の画像及び前記第２の画像はアフィン関係にあることを特徴とする方法。
【請求項２】
前記第１の組の交点及び前記第２の組の交点を用いて、アフィン歪パラメータを推定するステップを更に備えることを特徴とする請求項１に記載の方法。
【請求項３】
アフィン歪を反転するステップを更に備え、前記アフィン歪は、前記アフィン歪パラメータにより定義されることを特徴とする請求項２に記載の方法。
【請求項４】
正規化相関により前記関係の尺度を判定するステップを更に備えることを特徴とする請求項３に記載の方法。
【請求項５】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点の間に特有の線分比を有し、前記判定するステップは、
前記第２の画像中の各線の線分比を判定するサブステップと、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合するサブステップと、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別するサブステップとを備えることを特徴とする請求項１に記載の方法。
【請求項６】
前記線の各々は前記第１の画像中に１つのパターンを埋め込むことにより前記第１の画像中に埋め込まれ、各パターンは実質的に１次元基底関数から形成されており、前記方法は、
前記第２の画像の射影変換を計算する初期ステップと、
角度の選択するために、前記射影変換と前記基底関数との１次元相関を計算する初期ステップと、
前記相関のピークを探索する初期ステップとを備え、前記ピークの各々の位置は、前記埋め込みパターンのうちの１つのパターンの空間パラメータを提供することを特徴とする請求項１又は５に記載の方法。
【請求項７】
補助パターンと少なくとも４本の互いに平行でない線とを有し、前記線が所定の位置で第１の組の交点を形成する第１の画像のアフィン歪バージョンである第２の画像の中の補助パターンを検出する方法であって、
前記第２の画像中に現れる前記線の第２の組の交点を識別するステップと、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係を識別するステップと、
前記第１の組の交点及び前記第２の組の交点を用いて、前記アフィン歪パラメータを推定するステップと、
歪補助パターンを形成するために、前記アフィン歪パラメータにより定義される前記アフィン歪を前記補助パターンに適用するステップと、
前記第２の画像中の前記歪補助パターンを検出するステップとを備えることを特徴とする方法。
【請求項８】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点の間に特有の線分比を有し、前記交点間の関係を識別するステップは、
前記第２の画像中の各線の線分比を判定するサブステップと、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合するサブステップと、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別するサブステップとを備えることを特徴とする請求項７に記載の方法。
【請求項９】
前記線の各々は前記第１の画像中に１つのパターンを埋め込むことにより前記第１の画像中に埋め込まれ、各パターンは実質的に１次元基底関数から形成されており、前記方法は、
前記第２の画像の射影変換を計算する初期ステップと、
角度の選択するために、射影変換と前記基底関数との１次元相関を計算する初期ステップと、
前記相関のピークを探索する初期ステップとを備え、前記ピークの各々の位置は、前記埋め込みパターンのうちの１つのパターンの空間パラメータを提供することを特徴とする請求項７又は８に記載の方法。
【請求項１０】
各々が少なくとも４本の互いに平行でない線を有する第１の画像と第２の画像とのアフィン関係を推定する装置であって、
前記第１の画像中に現れる前記線の第１の組の交点を識別する手段と、
前記第２の画像中に現れる前記線の第２の組の交点を識別する手段と、
前記第１の組の交点及び前記第２の組の交点から、交点間に関係が存在するか否かを判定する手段とを備え、前記関係が存在する場合、前記第１の画像及び前記第２の画像はアフィン関係にあることを特徴とする装置。
【請求項１１】
前記第１の組の交点及び前記第２の組の交点を用いて、アフィン歪パラメータを推定する手段を更に備えることを特徴とする請求項１０に記載の装置。
【請求項１２】
アフィン歪を反転する手段を更に備え、前記アフィン歪は、前記アフィン歪パラメータにより定義されることを特徴とする請求項１１に記載の装置。
【請求項１３】
正規化相関により、前記関係の尺度を判定する手段を更に備えることを特徴とする請求項１２に記載の装置。
【請求項１４】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点間に特有の線分比を有し、前記判定する手段は、
前記第２の画像中の各線の線分比を判定する手段と、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合する手段と、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別する手段とを備えることを特徴とする請求項１０に記載の装置。
【請求項１５】
補助パターンと少なくとも４本の互いに平行でない線とを有し、前記線が所定の位置で第１の組の交点を形成する第１の画像のアフィン歪バージョンである第２の画像の中の補助パターンを検出する装置であって、
前記第２の画像中に現れる前記線の第２の組の交点を識別する手段と、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係を識別する手段と、
前記第１の組の交点及び前記第２の組の交点を用いて、前記アフィン歪パラメータを推定する手段と、
歪補助パターンを形成するために、前記アフィン歪パラメータにより定義される前記アフィン歪を前記補助パターンに適用する手段と、
前記第２の画像中の前記歪補助パターンを検出する手段とを備えることを特徴とする装置。
【請求項１６】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点の間に特有の線分比を有し、前記交点間の関係を識別する手段は、
前記第２の画像中の各線の線分比を判定する手段と、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合する手段と、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別する手段とを備えることを特徴とする請求項１５に記載の装置。
【請求項１７】
各々が少なくとも４本の互いに平行でない線を有する第１の画像と第２の画像とのアフィン関係を推定するためのコンピュータ可読媒体に格納されたプログラムであって、
前記第１の画像中に現れる前記線の第１の組の交点を識別するためのコードと、
前記第２の画像中に現れる前記線の第２の組の交点を識別するためのコードと、
前記第１の組の交点及び前記第２の組の交点から、交点間に関係が存在するか否かを判定するためのコードとを備え、前記関係が存在する場合、前記第１の画像及び前記第２の画像はアフィン関係にあることを特徴とするプログラム。
【請求項１８】
前記第１の組の交点及び前記第２の組の交点を用いて、アフィン歪パラメータを推定するためのコードを更に備えることを特徴とする請求項１７に記載のプログラム。
【請求項１９】
アフィン歪を反転するためのコードを更に備え、前記アフィン歪は、前記アフィン歪パラメータにより定義されることを特徴とする請求項１８に記載のプログラム。
【請求項２０】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点の間に特有の線分比を有し、前記判定するためのコードは、
前記第２の画像中の各線の線分比を判定するためのコードと、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合するためのコードと、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別するためのコードとを含むことを特徴とする請求項１７に記載のプログラム。
【請求項２１】
補助パターンと少なくとも４本の互いに平行でない線とを有し、前記線が所定の位置で第１の組の交点を形成する第１の画像のアフィン歪バージョンである第２の画像の中の補助パターンを検出するためのコンピュータ可読媒体に格納されたプログラムであって、
前記第２の画像中に現れる前記線の第２の組の交点を識別するためのコードと、
前記第１の組の交点及び前記第２の組の交点から、交点間の関係を識別するためのコードと、
前記第１の組の交点及び前記第２の組の交点を用いて、前記アフィン歪パラメータを推定するためのコードと、
歪補助パターンを形成するために、前記アフィン歪パラメータにより定義される前記アフィン歪を前記補助パターンに適用するためのコードと、
前記第２の画像中の前記歪補助パターンを検出するためのコードとを備えることを特徴とするプログラム。
【請求項２２】
前記線の各々は、前記第１の画像中に埋め込まれ、前記第１の画像中に埋め込まれたその他の線との交点間に特有の線分比を有し、前記交点間の関係を識別するためのコードは、
前記第２の画像中の各線の線分比を判定するためのコードと、
対応する線分比を有する前記第１の画像及び前記第２の画像中の線を整合するためのコードと、
前記第１の組の交点及び前記第２の組の交点から、前記交点間の関係を識別するためのコードとを備えることを特徴とする請求項２１に記載のプログラム。
【請求項２３】
実質的に添付の図面を参照して説明されることを特徴とする方法。
【請求項２４】
実質的に添付の図面を参照して説明されることを特徴とする装置。
【図１Ａ】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公表番号】特表２００７−５１０３３５（Ｐ２００７−５１０３３５Ａ）
【公表日】平成１９年４月１９日（２００７．４．１９）
【国際特許分類】
【出願番号】特願２００６−５３７００８（Ｐ２００６−５３７００８）
【出願日】平成１６年１１月４日（２００４．１１．４）
【国際出願番号】ＰＣＴ／ＡＵ２００４／００１５３２
【国際公開番号】ＷＯ２００５／０４５７６３
【国際公開日】平成１７年５月１９日（２００５．５．１９）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公表日】平成１９年４月１９日（２００７．４．１９）
【国際特許分類】
【出願日】平成１６年１１月４日（２００４．１１．４）
【国際出願番号】ＰＣＴ／ＡＵ２００４／００１５３２
【国際公開番号】ＷＯ２００５／０４５７６３
【国際公開日】平成１７年５月１９日（２００５．５．１９）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]