JP3573198B2

JP3573198B2 - 画像位置合わせ方法

Info

Publication number: JP3573198B2
Application number: JP24002899A
Authority: JP
Inventors: マクガイアモーガン
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1999-03-18
Filing date: 1999-08-26
Publication date: 2004-10-06
Anticipated expiration: 2019-08-26
Also published as: GB2354131A; JP2000268178A; GB2354131B; GB0006548D0; US6266452B1

Description

【０００１】
【発明の属する技術分野】
本発明は、画像処理に関し、特に、画像の位置合わせ（レジストレーション）の新規な方法に関する。
【０００２】
【従来の技術】
Ａ．画像位置合わせ
画像位置合わせ（ｉｍａｇｅｒｅｇｉｓｔｒａｔｉｏｎ）は、両方の画像にある画素（ピクセル）が同じ位置に配置されるように、基準（リファレンス）画像の上にパターン画像を整列させるというプロセスである。このプロセスは、例えば、テンプレート上への取得画像のアライメント（整列）、同一場面（シーン）の時系列画像のアライメント、あるいは合成画像における個々のバンドのアライメント（コレジストレーション（ｃｏｒｅｇｉｓｔｒａｔｉｏｎ））などにおいて有用である。このプロセスの実際の適用例を２つ挙げると、医療用画像の分野における放射線像のアライメントと、環境科学の分野における衛星画像のアライメントがある。
【０００３】
典型的な画像位置合わせの問題においては、基準画像とパターン画像とが何らかの形で互いに関係していることが、既知であるかあるいは予想されている。すなわち、基準画像とパターン画像とが、一部の要素を共有している、あるいは同じ表示対象または場面に関連していることが、既知であるかあるいは予想されている。このような典型的な画像位置合わせ問題では、２個の画像間の差の発生源を、以下の４種類のカテゴリに分けることができる。
【０００４】
１．アライメントの差：
画像間のアライメントの差は、一方の画像から他方の画像への空間写像によって生じる。典型的な写像では、並進移動、回転、ゆがみおよび拡大／縮小（スケーリング）が起こる。無限連続領域の画像の場合、これらの差は、一方の画像から他方の画像への空間写像の結果である。例えば画像センサの向きまたはパラメータを変えることで、アライメントの差がもたらされる。
【０００５】
２．妨害（オクルージョン：ｏｃｃｌｕｓｉｏｎ）による差：
アライメントの差により有限画像の一部が画像枠（画像フレーム）から出ていったり有限画像の画像枠に新たなデータが入ってくる場合、あるいは画像センサと画像化対象との間に障害物が来る場合に、視点の妨害による差が生じる。例えば衛星画像では、雲がしばしば地球を妨害し、地表画像における妨害が生じる。
【０００６】
３．ノイズによる差：
ノイズによる差は、画像センサにおけるサンプリング誤差やバックグラウンドノイズによって、さらには画像センサ誤差によってもたらされる原因不明の無効データから生じ得る。
【０００７】
４．変化による差：
変化による差は、画像化される対象物もしくは場面間の実際の差である。衛星画像では、変化による差の例として、照明、侵食、建設および森林伐採がある。場合によっては、変化による差とノイズによる差とを区別できないことがある。
【０００８】
代表的には、複数の画像を位置合わせして、特定場面での変化を検出する。したがって、良好に位置合わせが行われれば、アライメント、妨害およびノイズによる差を検出して消去したりあるいは解消しながら、変化による差を保存することができる。位置合わせ方法では、画像の内容に関して変化は小さいものと仮定しなければならない。すなわち、アライメント、妨害およびノイズによる差を解消した後には、位置合わせされる画像は「視覚的に同様」であると仮定される。さらに、両方の画像で、十分な量の対象物もしくは場面が見えなければならない。例えば、基準画像の内容の５０％以上が、その基準画像に対して位置合わせされるパターン画像にも存在するものと仮定することができる。実際には、医療用センサおよび衛星センサは、画像の内容の９０％以上を共有するように、十分な精度をもってそれらの画像に向けることができるのが普通である。
【０００９】
Ｂ．回転−拡大／縮小−並進移動変換：
本発明は、ノイズおよびアライメントによる妨害（オクルージョン）の存在下で回転−拡大／縮小−並進移動（「ＲＳＴ：Ｒｏｔａｔｉｏｎ−Ｓｃａｌｅ−Ｔｒａｎｓｌａｔｉｏｎ」）変換によって互いに異なっている２個の画像を位置合わせ（レジストレーション）するために有効な方法を提供する。ＲＳＴ変換は、単一の並進ベクトル、単一の回転係数および単一の拡大／縮小係数（スケール係数）という３種類の変換パラメータの組み合わせとして表現され、これらのパラメータはいずれも画像面で作用する。本発明は、２個の画像からそれら３種類のパラメータを復元することで、基準画像に関するパターン画像の回転、拡大／縮小および移動を「取り消す（ｕｎｄｏ）」ことにより、基準画像にパターン画像を位置合わせすることができるようにする。本発明は、さらに、回転係数もしくは拡大／縮小係数を単独で復元する新規な方法を含むものでもあり、この方法は、基準画像とパターン画像の間のアライメントが上記係数の１個のみによって影響を受けることがわかっている場合に有用であろう。
【００１０】
ＲＳＴ変換は、基準画像ｒをパターン画像ｐ中にマッピング（写像）する画素マッピング関数Ｍとして表現される。実際には、これらの関数は有限画像に作用し、変換中に画像の枠から出て行ったり枠に入ってきたりしなかったデータのみを処理することができる。２次元無限連続基準画像ｒとパターン画像ｐとがＲＳＴ変換によって関係してｐ＝Ｍ（ｒ）となっている場合、その基準画像ｒにおける各点ｒ（ｘ_ｒ，ｙ_ｒ）は、下記の行列式にしたがって、対応する点ｐ（ｘ_ｐ，ｙ_ｐ）に写像される。
【００１１】
【数１】

同様に、任意の画素ｐ（ｘ，ｙ）については、下記の関係が成り立つ。
【００１２】
【数２】

この表記において、φ，ｓおよび（Δｘ，Δｙ）は、それぞれ変換の回転パラメータ、拡大／縮小パラメータおよび並進パラメータである。ここで、φは反時計方向の回転角であり、ｓは拡大／縮小係数であり、（Δｘ，Δｙ）は並進ベクトルである。有限で離散型の基準画像ｒおよびパターン画像ｐの場合、ｒとｐは画素面積Ｎ（大きさＮ^１／２×Ｎ^１／２）の正方形であると仮定する。有限画像のＲＳＴ変換により、若干のデータが画像枠内へまたは画像枠外へ動くことによって、妨害による差が生じることに留意する。
【００１３】
Ｃ．フーリエ−メリン（Ｆｏｕｒｉｅｒ−Ｍｅｌｌｉｎ）不変量：
フーリエ変換は、ＲＳＴ変換下で、ある特徴を有することから、位置合わせ問題に有用である。２個の２次元無限連続画像ｒ，ｐが上記式（２）で与えられる関係にしたがうものとする。フーリエシフト、拡大／縮小および回転の定理により、それぞれ画像ｒおよびｐのフーリエ変換であるＦ_ｒとＦ_ｐとの間の関係は、次式によって与えられる。
【００１４】
【数３】

フーリエ変換Ｆ_ｐの複素絶対値はＦ_ｒの絶対値のｓ^２倍であり、それはΔｘおよびΔｙとは独立であることに留意する。さらに、Ｆ_ｐの絶対値は、Ｆ_ｒを−φだけ回転させ、その大きさを係数ｓだけ縮小させることで、Ｆ_ｒの絶対値から誘導される。このことは、Ｆ_ｐの絶対値に対する独立した操作によって回転と拡大／縮小のパラメータを回復することを可能にする。
【００１５】
式（３）は、画素領域（ｐｉｘｅｌｄｏｍａｉｎ）における画像を角度φだけ回転させることが、そのフーリエ変換の絶対値をφだけ回転させることと等価であることを示している。画素領域における画像を拡大／縮小係数ｓだけ拡大することは、それのフーリエ変換の絶対値の広がりをｓだけ縮小させ、フーリエ変換の絶対値の高さ（振幅）にｓ^２を乗ずることと等価である。画素領域での並進移動は、フーリエ変換の絶対値に影響しない。その不変性から、フーリエ変換の絶対値は、「フーリエ−メリン不変量（Ｆｏｕｒｉｅｒ−Ｍｅｌｌｉｎｉｎｖａｒｉａｎｔ）」と称され、フーリエ絶対値空間は「フーリエ−メリン領域（Ｆｏｕｒｉｅｒ−Ｍｅｌｌｉｎｄｏｍａｉｎ）」と称される。画像ｒおよびｐそれぞれのフーリエ−メリン変換ＲおよびＰは、Ｒ＝｜Ｆ_ｒ｜およびＰ＝｜Ｆ_ｐ｜である。
【００１６】
多くの先行技術の位置合わせ法では、その処理が並進移動不変のフーリエ−メリン空間で行われ、そうしてから「極−対数」座標に変換することから、回転および拡大／縮小の効果は、直交するθ軸およびｌｏｇ_Ｂρ軸方向の並進移動として現れる。ここでＢは大域定数対数底である。例えば、Ｂ．Ｒｅｄｄｙｅｔａｌ．， ”ＡｎＦＦＴ−ＢａｓｅｄＴｅｃｈｎｉｑｕｅＦｏｒＴｒａｎｓｌａｔｉｏｎ，Ｒｏｔａｔｉｏｎ，ＡｎｄＳｃａｌｅＩｎｖａｒｉａｎｔＩｍａｇｅＲｅｇｉｓｔｒａｔｉｏｎ，” ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｍａｇｅＰｒｏｃｅｓｓｉｎｇ，Ｖｏｌ．３，Ｎｏ．８，ｐｐ．１２６６−１２７０（１９９６年８月）；ＤＬｅｅｅｔａｌ．， ”ＡｎａｌｙｓｉｓＯｆＳｅｑｕｅｎｔｉａｌＣｏｍｐｌｅｘＩｍａｇｅｓ，ＵｓｉｎｇＦｅａｔｕｒｅＥｘｔｒａｃｔｉｏｎＡｎｄＴｗｏ−ＤｉｍｅｎｓｉｏｎａｌＣｅｐｓｔｒｕｍＴｅｃｈｎｉｑｕｅｓ，” ＪｏｕｒｎａｌｏｆｔｈｅＯｐｔｉｃａｌＳｏｃｉｅｔｙｏｆＡｍｅｒｉｃａ，Ｖｏｌ．６，Ｎｏ．６，ｐｐ．８６３−８７１（１９８９年６月）；Ｅ．ＤｅＣａｓｔｒｏｅｔａｌ．， ”ＲｅｇｉｓｔｒａｔｉｏｎＯｆＴｒａｎｓｌａｔｅｄＡｎｄＲｏｔａｔｅｄＩｍａｇｅｓＵｓｉｎｇＦｉｎｉｔｅＦｏｕｒｉｅｒＴｒａｎｓｆｏｒｍｓ，” ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅ，Ｖｏｌ．ＰＡＭＩ−９，Ｎｏ．５，ｐｐ．７００−７０３（１９８７）；Ｓ．Ａｌｌｉｎｅｙ， ”ＳｐａｔｉａｌＲｅｇｉｓｔｒａｔｉｏｎＯｆＭｕｌｔｉｓｐｅｃｔｒａｌＡｎｄＭｕｌｔｉｔｅｍｐｏｒａｌＤｉｇｉｔａｌＩｍａｇｅｒｙＵｓｉｎｇＦａｓｔ−ＦｏｕｒｉｅｒＴｒａｎｓｆｏｒｍＴｅｃｈｎｉｑｕｅｓ，” ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅ，Ｖｏｌ．１５，Ｎｏ．５，ｐｐ．４９９−５０４（１９９３年５月）；Ｑ． −Ｓ．Ｃｈｅｎｅｔａｌ．， ”ＳｙｍｍｅｔｒｉｃＰｈａｓｅ−ＯｎｌｙＭａｔｃｈｅｄＦｉｌｔｅｒｉｎｇＯｆＦｏｕｒｉｅｒ−ＭｅｌｌｉｎＴｒａｎｓｆｏｒｍｓＦｏｒＩｍａｇｅＲｅｇｉｓｔｒａｔｉｏｎＡｎｄＲｅｃｏｇｎｉｔｉｏｎ，” ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅ，Ｖｏｌ．１６，Ｎｏ．１２，ｐｐ．１１５６−１１６８（１９９４年１２月）を参照。極−対数空間では、これらの軸方向のシフトの関数としてのＲおよびＰの正規化相関係数は、座標（−φ，−ｓ）で最大となる。シフトｊでの一次元正規化相関係数は下記式によって与えられる。
【００１７】
【数４】

これが単純に、２次元極−対数空間に拡大される。
【００１８】
式（３）は無限画像に適用されるものであって、有限画像には適用されない。それが有限画像に当てはまったとしたら、フーリエ−メリン極−対数係数を得るのにＯ（ＮｌｏｇＮ）回の演算（すなわち、ＮｌｏｇＮのオーダーの回数の演算）が必要であり、係数の全ての循環シフトについて正規化相関係数を計算するのに、畳込み定理によって、Ｏ（ＮｌｏｇＮ）回の演算が必要であると考えられる。そこで、回転および拡大／縮小は、Ｏ（ＮｌｏｇＮ）回検出することになると考えられる。連続画像ではなく離散画像を用いると、２個の画像間でのおよび極−対数表示の計算での若干のサンプリング誤差が生じる。
【００１９】
【発明が解決しようとする課題】
実際には、高解像度画像および画素間補間を用いることで、それらの誤差を最低限にすることができる。残念ながら、以下の２つの理由から、この理論は有限画像には適用されない。
【００２０】
１．妨害（オクルージョン）誤差：
有限画像の回転、拡大／縮小または並進移動によって、画素データの一部が画像枠から出て行くか、あるいはいくらかの新たな画素データがその枠に入るようになる。
【００２１】
２．タイリング（Ｔｉｌｉｎｇ）誤差：
有限画像のＦＦＴ（高速フーリエ変換）は、画像面内においてタイル貼りするようにその画像を無限に反復することで求められる。このような反復処理がなされた画像のことをタイリング画像と呼ぶ。回転と拡大／縮小は、タイリングでは可換ではない。
【００２２】
画像が、図１（ａ）のように、一様で十分に大きい背景（バックグラウンド）に対して形を描く場合、変換中は一様なバックグラウンドの画素のみが画像枠を出入りすることから、データの損失がない。これは、例えばＭＲＩ（磁気共鳴イメージング）などのように、検査対象画像が人体外の一様なバックグラウンドとともに人体断面を描出するような一部の医療用イメージング作業に当てはまる。図２（ａ）に示したように背景が一様でなかったりパディング（ｐａｄｄｉｎｇ）が不十分である画像の場合、変換によって妨害誤差が生じて、相関ピークが別の位置にシフトしたり、重大な劣化が生じる場合がある。
【００２３】
ストーンらが回転および拡大／縮小について指摘しているように（Ｈ．Ｓｔｏｎｅｅｔａｌ．， ”ＡＮｏｔｅＯｎＴｒａｎｓｌａｔｉｏｎ，Ｒｏｔａｔｉｏｎ，ＡｎｄＳｃａｌｅ−ＩｎｖａｒｉａｎｔＩｍａｇｅＲｅｇｉｓｔｒａｔｉｏｎ，” ＮＥＣＲｅｓｅａｒｃｈＩｎｓｔｉｔｕｔｅＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ，Ｎｏ．９７−１１５Ｒ（１９９７））、さらにはアリニーらが並進移動について指摘しているように（Ａｌｌｉｎｅｙｅｔａｌ．， ”ＤｉｇｉｔａｌＲｅｇｉｓｔｒａｔｉｏｎＵｓｉｎｇＰｒｏｊｅｃｔｉｏｎｓ，” ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅ，Ｖｏｌ．ＰＡＭＩ−８，Ｎｏ．２，ｐｐ．２２２−２３３，１９８６年３月）、９０°の整数倍の回転の場合およびパディングされた画像の短距離の並進移動の場合を除き、タイリング画像のＦＦＴをとる場合には、タイリング誤差が不可避である。離散有限画像のフーリエ変換は、高強度の「＋」形状としてフーリエ−メリン空間に現れるタイル間の境界を有する（図２での列（Ｂ）を参照）。このアーティファクト（偽像）は、画像内容の残りの部分からの係数よりも顕著である。ある先行技術の位置合わせ方法では、回転対称な画像枠を利用して、フーリエ−メリン空間でそのアーティファクトが見えるのを回避する（上記のＥ．ＤｅＣａｓｔｒｏｅｔａｌ．を参照）。本発明は、以下に説明し、また未処理の正方形画像を用いるという従来のアプローチと両方の方法を比較する実験の結果によって確認されるように、より有効なアプローチを提供するものである。
【００２４】
いかなる誤差発生源とは無関係に、有限画像においてフーリエ−メリンによる手法が良好に機能するよう十分に、無限画像の場合および有限画像の場合が密接に関連づけられる。しかしながら、文献に報告の方法では、相関関数において、ピーク相関が低く、信号／ノイズ比が小さい（Ｂ．Ｒｅｄｄｙｅｔａｌ．の上記文献；Ｌ．Ｂｒｏｗｎ， ”ＡＳｕｒｖｅｙＯｆＩｍａｇｅＲｅｇｉｓｔｒａｔｉｏｎＴｅｃｈｎｉｑｕｅｓ，” ＡＣＭＣｏｍｐｕｔｉｎｇＳｕｒｖｅｙｓ，Ｖｏｌ．２４，Ｎｏ．４，ｐｐ．３２５−３７６（１９９２）を参照）。
【００２５】
それとは対照的に本発明は、相関関数における１に近いピーク相関と高い信号／ノイズ比を達成し、それらがあいまって位置合わせの正確さを大幅に向上させる方法を提供する。
【００２６】
【課題を解決するための手段】
全般的に言えば、本発明によれば、基準画像にパターン画像を位置合わせする方法が提供される。パターン画像と基準画像とは、拡大／縮小係数（スケール係数）ｓ、回転係数φおよび並進ベクトル（Δｘ，Δｙ）によって規定される回転−拡大／縮小−移動（Ｒｏｔａｔｉｏｎ−Ｓｃａｌｅ−Ｔｒａｎｓｌａｔｉｏｎ：ＲＳＴ）変換によって互いに異なっている。フーリエ−メリン不変量を用いて、基準画像ｒとパターン画像ｐとの間のＲＳＴ変換の回転パラメータ、拡大／縮小変化パラメータおよび並進移動パラメータを分離することにより、画像位置合わせを行う。
【００２７】
本発明の好ましい実施態様においては、本発明の方法には、前処理の段階、拡大／縮小の段階、回転の段階および並進移動の段階が含まれる。
【００２８】
前処理の段階では、基準画像とパターン画像を、画素領域からフーリエ−メリン領域に変換して、それぞれ変換基準画像および変換パターン画像を得る。次に、変換基準画像と変換パターン画像をデカルト座標（ｘ，ｙ）座標から極−対数（ｌｏｇ_Ｂ（半径），角度）座標に変換する。ここで、Ｂは大域定数対数底である。
【００２９】
拡大／縮小の段階では、１以上の可能な（ｐｏｔｅｎｔｉａｌ）拡大／縮小係数が復元される。極−対数（ｌｏｇ_Ｂ（半径），角度）基準画像と極−対数（ｌｏｇ_Ｂ（半径），角度）パターン画像が、それらの角度軸方向に沿って合計されて、それぞれ基準スケールシグネチュア（ｓｃａｌｅｓｉｇｎａｔｕｒｅ）およびパターンスケールシグネチュアを与える。次に、正規化相関を用いて、基準サイズスケールシグネチュアをパターンスケールシグネチュアに相関させ、相関スケールシグネチュアを得る。スケールシグネチュアの組を含んでいる相関スケールシグネチュアの極大を検出する。最後に、対数底Ｂを、各スケールシグネチュアでべき乗し、１以上の可能な拡大／縮小係数を得る。実際の拡大／縮小係数は、並進の段階においてこの１以上の可能な拡大／縮小係数から求められる。
【００３０】
回転の段階では、回転係数φが復元される。極−対数（ｌｏｇ_Ｂ（半径），角度）基準画像および極−対数（ｌｏｇ_Ｂ（半径），角度）パターン画像がそれらのｌｏｇ_Ｂ（半径）軸方向に合計されて、それぞれ基準回転シグネチュアとパターン回転シグネチュアを与える。次に、正規化円形相関を用いて、基準回転シグネチュアをパターン回転シグネチュアに相関させて、相関回転シグネチュアを得る。最後に、回転係数φを含んでいる相関回転シグネチュアの最大値を得る。
【００３１】
並進移動の段階では、実際の拡大／縮小係数（スケール係数）ｓおよび並進ベクトル（Δｘ，Δｙ）が復元される。パターン画像を−φだけ回転して、回転パターン画像を得る。各可能な拡大／縮小係数について、可能な拡大／縮小係数の逆数によって、回転パターンを再び拡大／縮小させて、候補パターンを得る。各候補パターンについて、可能な並進ベクトルを求める。可能な並進ベクトルは、候補パターンをその可能な並進ベクトルだけ並進移動させた場合に、基準画像と並進後の候補パターンとの間の最も高い相関を与えるもののことである。最後に、基準画像に対して最高の相関を与える並進後の候補パターンを選択する。可能な拡大／縮小係数と選択された候補パターンに関連する可能な並進ベクトルは、それぞれ、実際の拡大／縮小係数ｓと実際の並進ベクトル（Δｘ，Δｙ）を含む。したがって、各ＲＳＴ変換パラメータが効果的に復元される。
【００３２】
別の実施態様は、拡大／縮小係数ｓまたは回転係数φのいずれかが既知である場合に、残りのＲＳＴ変換パラメータを復元するためのものである。
【００３３】
画像位置合わせの正確さを高めるために本発明の方法において使用できる各種のオプションのフィルタが提供される。
【００３４】
従って、本発明の目的は、所与の基準画像に合致してパターン画像をアライメントすることができる画像位置合わせ方法を提供することにある。
【００３５】
本発明の別の目的は、２個の画像の間のＲＳＴ変換を規定する変換パラメータを復元する画像位置合わせ方法を提供することにある。
【００３６】
本発明のさらに別の目的は、相関関数における高いピーク相関と高い信号／ノイズ比を達成し、これらがあいまって位置合わせの正確さを大いに向上させる画像位置合わせ方法を提供することにある。
【００３７】
本発明の他の目的は、添付の図面と関連させた以下の説明を考慮することで、より容易に理解できよう。
【００３８】
【発明の実施の形態】
上記のように本発明は、ノイズおよびアライメントからの妨害（オクルージョン）の存在下に、回転−拡大／縮小−移動（「ＲＳＴ；Ｒｏｔａｔｉｏｎ−Ｓｃａｌｅ−Ｔｒａｎｓｌａｔｉｏｎ」）変換によって互いに異なっている２個の画像を位置合わせする方法を提供する。詳細には、フーリエ−メリン（Ｆｏｕｒｉｅｒ−Ｍｅｌｌｉｎ）不変量を用いて、基準画像ｒとパターン画像ｐの間のＲＳＴ変換の回転パラメータ、拡大／縮小パラメータおよび並進パラメータを分離することによって、画像位置合わせ（ｉｍａｇｅｒｅｇｉｓｔｒａｔｉｏｎ）を行う。本発明の方法の各工程および処理は、好適にプログラミングされた汎用コンピュータを用いて行うのが好ましいが、そのような処理は所望に応じて、専用のハードウェアその他の特殊装置で行うこともできることに留意すべきである。そこで、本明細書に記載のプログラム、アルゴリズム、プロセス、方法などは、いかなる形でも特定のコンピュータまたは装置に限定されるものではない。
【００３９】
本発明の方法について説明する前に、有限画像についてのフーリエ−メリン法を説明することが、本発明に関しての理解を深める上で役立つだろう。
【００４０】
Ａ．有限画像についてのフーリエ−メリン法：
この節では、単純なフーリエ−メリン法を用いた場合、特定の性質を有する人工的な理想化された画像については、全ての発生源からの上述の累積誤差が小さいものとなり得ることを示す。しかしながら、現実に遭遇する実際の非理想画像の場合、その誤差は大きいことが示される。
【００４１】
フーリエ−メリン不変量の特性が有限画像に与える効果を強調する２種類の実験について説明する。図１に示した第１の実験は、フーリエ−メリン空間における無限画像とかなり類似した挙動を示す種類の理想画像の一つを調べるものである。図１の列（Ａ）に示した、一様な（黒）の背景を有する高コントラストの単純な画像は、ほぼ円形であって、対比を高める背景上に置かれたある種の理想画像を代表するものである。図２に示した第２の実験は、実際の衛星画像類の一つを調べるものである。図２の列（Ａ）に示した画像枠にある低コントラストで詳細な画像は、衛星画像およびある種の医療画像の典型的なものであり、誤差が無視できない実際の非理想画像類の代表するものである。
【００４２】
図１の列（Ａ）には、左から右へ水平方向に配置された、（１）６４×６４画素の理想化された有限離散基準画像；（２）角度４５°だけ回転した基準画像に相当する回転画像；（３）係数２．００だけ拡大した基準画像に相当する拡大／縮小画像；（４）（−１６，−１６）画素だけ移動した基準画像に相当する並進移動画像の４個の画像を示してある。離散画像を回転・拡大／縮小することで生じる誤差を最小にするため、回転画像および拡大／縮小画像についての画素値を計算する際に、線形補間を用いた。図１の列（Ｂ）には、上記４種類の画像のおのおのについて、フーリエ−メリン係数のうち非ゼロである係数の等高線プロットを示してあり、変換（回転、拡大／縮小、並進移動）の効果を観察することができる。この基準画像の場合、画素領域での角度φの回転は、フーリエ−メリン領域での−φの回転とほぼ等価であることに留意する。画素領域でｓだけ拡大するということは、フーリエ−メリン領域でｓだけ縮小し、さらに振幅にｓ^２を乗ずることとほぼ等価である。並進移動による効果はない。調べると、図１におけるフーリエ−メリン変換が、無限画像の変換の特性に非常に近い特性を示して、回転パラメータおよび拡大／縮小パラメータを復元することが、明らかである。
【００４３】
図２には、実際の衛星画像について行った同じ実験の結果を示してある。図２の列（Ａ）は、図１の列（Ａ）に示した単純な基準画像と同じ変換（回転、拡大／縮小、並進移動）を行った６４×６４画素の衛星画像（「基準画像」）を示してある。図２の列（Ｂ）には、図２の列（Ａ）に示す画像のフーリエ−メリン変換を示してある。「＋」形状のアーティファクトによって、回転あるいは拡大／縮小された係数の動きが不鮮明になっていることに留意する。並進画像のフーリエ−メリン変換が元の基準画像の変換と同一ではないことから、フーリエ−メリン領域は、並進移動に対して不変ではない。
【００４４】
画素レベルの変換Ｍが、回転、拡大／縮小および並進移動の組み合わせである場合、フーリエ−メリン空間における理想の場合（無限画像の場合）の係数および実際の（有限画像の場合）係数からの差は累積的であることから、先行技術のフーリエ−メリン変換に基づく方法では、十分な性能が得られない。
【００４５】
Ｂ．新規な画像位置合わせ方法：
本発明の画像位置合わせ方法は、拡大／縮小係数（スケール係数）ｓ、回転係数φおよび並進ベクトル（Δｘ，Δｙ）というＲＳＴ変換の３種類の変換パラメータそれぞれについて１段階の計３段階で機能するものである。図３は、本発明の方法の全体を示すフローチャートである。本発明の方法は、前処理段階１０、拡大／縮小段階２０、回転段階３０および並進移動段階４０を有する。前処理段階１０では、基準画像とパターン画像を作成し、これらを拡大／縮小段階と回転段階で使用するのに適した形に変換する。拡大／縮小段階２０では、１以上の可能な（ｐｏｔｅｎｔｉａｌ）拡大／縮小係数を復元する。後述するように、１またはそれ以上の可能な拡大／縮小係数を復元することができる。可能な拡大／縮小係数が１個のみ復元された場合、その１個の可能な拡大／縮小係数が実際の拡大／縮小係数ｓとなる。本発明の方法はまた回転段階３０を備えているが、そこでは、回転係数φが復元される。本発明の方法はさらに並進移動段階４０を備えているが、そこでは並進ベクトル（Δｘ，Δｙ）が復元される。最後に、拡大／縮小段階２０で復元される「１以上の可能な拡大／縮小係数」が複数の可能な拡大／縮小係数である場合、実際の拡大／縮小係数ｓは、並進移動段階４０において、その複数の可能な拡大／縮小係数から求められる。拡大／縮小段階２０と回転段階３０とは独立であり、並行して行うことができる。回転係数および１以上の可能な拡大／縮小係数が分かってからでなければ、並進移動段階４０に進むことはできない。
【００４６】
本発明の方法についての以下の説明は、無限の連続画像についての変換パラメータを復元するために、フィルタ、変換および相関をどのように用いるかを説明するものである。一般理論が有限の離散画像には完全には適用されない理由について説明し、妥当な近似を行う本発明の方法について説明する。最後に、本発明の方法が、非常に正確で、高い信号／ノイズ比を有することを確認する実験結果を示す。
【００４７】
１．スケールシグネチュアおよび位置合わせの拡大／縮小段階：
拡大／縮小段階の目的は、式（２）における拡大／縮小係数ｓ、あるいは実際の拡大／縮小係数を含む可能な拡大／縮小係数の集合を復元することにある。並進移動および回転がある場合にこのパラメータを復元するために、画像を並進移動・回転不変空間に写像する。その新たな空間で、画像についての「スケールシグネチュア（ｓｃａｌｅｓｉｇｎａｔｕｒｅ）」を計算する。スケールシグネチュアは、拡大／縮小に伴って変化し、有限画像に対する回転や並進移動に対しては不変である。有限の離散画像の場合、スケールシグネチュアが並進移動および回転の変化に対して抵抗力を有し、したがって、スケールシグネチュアを用いて拡大／縮小係数ｓを効果的に復元できることが、実験の結果から明らかになっている。
【００４８】
写像変換Ｓは、基本的には、フーリエ−メリン並進不変性に基づいたものである。フーリエ−メリン領域の極−対数写像では、画素の拡大／縮小操作および回転操作は、直交軸方向に行われる。θ軸方向に積分し、半径と総画像エネルギーとの積によって除算することで、画像回転に対して不変の一次元関数Ｓ_ｒ（ｌｏｇ_Ｂ ρ）が得られる。この一次元関数がスケールシグネチュアある。無限画像の場合、スケールシグネチュアは、基準画像を係数ｓだけ拡大もしくは縮小させることが、Ｓ_ｒを−ｌｏｇ_Ｂｓだけ並進移動させることと等価である、という性質を有する。正規化相関をスケールシグネチュアについて実行すると、正規化係数は相関ピークの位置に影響しないことから、その正規化係数は無関係になる。正規化を無視すると、ｒ（ｘ，ｙ）からＳ_ｒ（ｌｏｇ_Ｂ ρ）への変換は下記式で与えられる。
【００４９】
【数５】

式中、Ｇは、有限画像の場合のアーティファクトを補正するのに使用される非線形フィルタである。無限画像の場合、Ｇは単位フィルタ（ｉｄｅｎｔｉｔｙｆｉｌｔｅｒ）である。実際の画像のフーリエ変換は１８０°回転対称性を有することから、積分範囲は２のファクタだけ小さくし得ることに留意する。画素領域における任意のＲＳＴ変換は、Ｓ領域における−ｌｏｇ_Ｂｓだけの並進移動（シフト）に等価であることから、２個の画像のスケールシグネチュア間の正規化（非円形）一次元相関係数は、−ｌｏｇ_Ｂｓにおいて１．０となるだろう。これは、単純な一次元相関を用いて拡大／縮小パラメータを復元できることを意味している。
【００５０】
離散画像の場合、連続関数Ｓ_ｒは、その係数がθに関する極−対数フーリエ−メリン空間における補間点上の合計を意味する離散関数である（補間によって生じる誤差を最小化するのに使用できるデカルト画像から極−フーリエ画像への直接変換は公知である。例えば、上記のＡｌｌｉｎｅｙｅｔａｌ．を参照。）。有限画像の場合、画像領域での拡大／縮小操作によって生じるＳ領域シフトによって、一部の画像画素が、Ｓ_ｒの元の範囲から出入りすることがある。拡大／縮小操作によっても一部の画像画素が元の画像枠から出入りすることがあり、フーリエ変換の個々の係数とともに、フーリエ変換の全体的な振幅を変化させる。有限フーリエ変換時における画像の内在的なタイリングによって生じる不連続は、フーリエ−メリン係数に対して、強度の大きい、拡大／縮小に対して不変の「＋」形状を付与し、この「＋」形状は、画像固有の係数の拡大／縮小に比べて著しく大きくなり、拡大／縮小変化を観察することを困難にする。
【００５１】
少なくとも１つの可能な拡大／縮小係数（実際の拡大／縮小係数ｓを含む）の好ましい復元方法が、図４、図５のフローチャートに示してある。図４には、すくなくとも１つの可能なサイズ変化係数と回転係数φとの両方を復元する上で一般的な、ある前処理を示してある。この前処理への入力は、基準画像ｒ（１１０ｒ）とパターン画像ｐ（１１０ｐ）である。各画像は、一連のステップで処理され、そのうちのいくつかのステップは、基準画像とパターン画像の両方で類似しており、これらは、図４および図５では、基準画像についての添字「ｒ」とパターン画像についての添字「ｐ」によって区別してある。
【００５２】
前処理は、オプションのステップ１１２から始まり、そこでは、各画像についてウェーブレット分解１１２を行うことができる。次に、好ましくは、フィルタ処理ステップ１１４を各ウェーブレット分解画像について行い、アーティファクト除去プレフィルタＧを用いてアーティファクト（偽像）を除去する。アーティファクトは、その操作を行わなければ後のフーリエ−メリン変換時に生じて、実際のデータを不鮮明にする望ましくない影響を与え、正確な相関を妨害する。次に、各画像、典型的には最初は画素領域にある各画像について、ステップ１１６においてフーリエ−メリン変換を行って、それらの画像をフーリエ−メリン領域に変換する。フーリエ−メリン変換によって、デカルト座標（ｘ，ｙ）座標にフーリエ−メリン変換画像が得られ、次にそれをステップ１１８において極−対数（ｌｏｇ_Ｂ（半径），角度）座標（Ｂは大域定数対数底）に変換する。Ｂは任意の定数であり、それの特定の値はさほど重要ではなく、何らかの所望の形で選択することができる。例えば、Ｂについての好適な値は２である。別の有用な値は、Ｂ＝（０．４２５Ｎ）^{（１／Ｎ）}を用いて計算することができる。式中、Ｎは、（ｌｏｇ_Ｂ（半径），角度）座標系のあるコンピュータ表現での離散表現での半径値の数値である。
【００５３】
ステップ１１６と１１８は、好ましくは、当業界で公知であって、例えば上述のアリネー（Ｓ．Ａｌｌｉｎｅｙ）の論文に記載されているように、１回の操作で行われる。後述するように、ステップ１１０からステップ１１８までを含む前処理は、拡大／縮小段階２０において少なくとも１つの可能な拡大／縮小係数を復元する前と、回転段階３０において回転係数φを復元する前に、全く同様に行われる。
【００５４】
前処理が完了し、変換画像を極座標に変化した後、少なくとも１つの可能な拡大／縮小係数を復元するための専用の処理を図５に示したように進める。最初に、ステップ１２０においで、ステップ１１８（図４）で得られた極−対数基準画像および極−対数パターン画像をそれぞれ、それらの角度軸方向に合計して、それぞれ一次元基準スケールシグネチュアおよび一次元パターンスケールシグネチュアを得る。次に、所望に応じて、オプションのステップ１２２において、スケールシグネチュアを安定させスケールシグネチュアの信号／ノイズ比を上昇させるフィルタＨを用いてスケールシグネチュアについてフィルタ処理を行い、後述するように、相関の正確さを向上させることができる。次に、ステップ１２４で、正規化相関を用いて、フィルタ処理されたスケールシグネチュアを相関させる。正規化相関によって、１以上の極大（スケールシグネチュアシフト）を有する相関スケールシグネチュア得られ、この相関スケールシグネチュアは、ステップ１２６で検出される。最後に、ステップ１２８において、対数底Ｂを各スケールシグネチュアだけべき乗し、少なくとも１つの可能な拡大／縮小係数１３０を得る。スケールシグネチュアの相関によって、複数の可能な拡大／縮小係数が得られる。実際には、後述するように、最終的な並進移動段階４０の実行中に１〜５個のピークを調べて、実際の拡大／縮小係数ｓを同定することが必要である。
【００５５】
２個の有限離散画像におけるスケールシグネチュアを調べることでいつも拡大／縮小係数を復元できるとは限らないが、実際には、Ｇを選択して有限変換によって生じるアーティファクトを最小化すれば、スケールシグネチュアにおいて全体的なシフトを肉眼で見ることができる場合が多い。本発明は、ステップ１１４（図４）においてこの観察を用い、拡大／縮小パラメータの復元を試みるものである。
【００５６】
相関（ステップ１２４）以前のステップは、フィルタ処理されたＳ変換を実行するものである。Ｗは計算範囲を縮小するために使用されるウェーブレット分解である。正規化相関とそれに続くピーク検出によって、正規化相関係数が極大となるＳ領域シフトのリストが返される。極−対数写像で使用される対数底Ｂの逆数をこれら各シフトでべき乗することで、拡大／縮小係数の集合が得られる。これらの各拡大／縮小係数は、基準画像ｒおよびパターン画像ｐに関係する拡大／縮小係数についての可能性の高い値である。実際の拡大／縮小係数を求めるには、この節で後述するように回転パラメータを復元し、画像上での回転を取り消し、並進移動相関が最大である拡大／縮小係数を選択する。拡大／縮小係数について上限または下限が分かっている場合には、その範囲外の全ての候補を除外して、必要な計算量を減らすことができる。
【００５７】
ＧがＯ（ＮｌｏｇＮ）となるように選択されると仮定すると、フーリエ−メリン変換および極−対数写像にはＮｌｏｇＮの程度の回数の計算が必要である。ｌｏｇ_Ｂ ρ軸への投影（θによる積分）には、さらにＮ−Ｎ^１／２回の加算を必要とする。そこで、スケールシグネチュアＳ_ｒおよびＳ_ｒを得るには、総計算回数はＯ（ＮｌｏｇＮ）となる。さらに追加のＮ^１／２ｌｏｇＮ程度の回数の演算を行うことで、一次元正規化相関およびピーク検出を行うことができる。基準画像ｒおよびパターン画像ｐについてｋ次のウェーブレット分解を行い、フーリエ−メリン変換への入力として低−低サブバンドを用いることで、全体の計算を４^ｋのファクタで高速化することができる。ｋ次ウェーブレット分解の低−低サブバンドは、実質的に、元の画像が各次元方向にｋのファクタだけ解像度低下したものである（Ｇ．Ｓｔｒａｎｇｅｔａｌ．，ＷａｖｅｌｅｔｓＡｎｄＦｉｌｔｅｒＢａｎｋｓ，Ｗｅｌｌｅｓｌｅｙ−ＣａｍｂｒｉｄｇｅＰｒｅｓｓ，ｐｐ．１５−３５（１９９６）参照）。拡大／縮小変換が解像度とは独立であることから、ウェーブレット分解を用いても、ｋが大きすぎて画像における形状の大半がサンプリング解像度より小さくならない限り、位置合わせの結果にはほとんど影響しない。ウェーブレットの使用を組み入れることで、位置合わせのうち拡大／縮小段階の総計算回数はＯ（（ＮｌｏｇＮ）／４^ｋ）回となる。
【００５８】
２．回転シグネチュアおよび位置合わせの回転段階：
回転段階の目的は、式（２）における基準画像ｒおよびパターン画像ｐに関係する回転パラメータφを復元することにある。スケールシグネチュアを用いて回転および並進移動不変領域での拡大／縮小情報を復元できるように、同様のアプローチを回転に用いることができる。Φを変換関数として、Φ_ｒ＝Φ（ｒ）が無限連続基準画像ｒの並進移動・拡大／縮小不変回転シグネチュアであるとする。有限離散型画像の場合、実験から、Φが元の画像の並進移動および拡大／縮小に対して抵抗力を有することが明らかになっている。ただし、全体的な絶対値の大きさの変化は起こり得る。
【００５９】
ρ軸方向での極フーリエ−メリン係数を積分することで、並進移動および拡大／縮小に不変である角度の一次元関数が得られる。Φは総画像エネルギーに関して正規化されていないが、正規化相関に影響を与えない。Φ（ｒ）は下記式によって与えられる。
【００６０】
【数６】

式中、Ｊは、拡大／縮小係数がない（ｓ＝１）ことが分かっている有限画像の場合に適用される点別の重み関数である。それ以外の場合、Ｊは１であると仮定する。
【００６１】
無限連続画像の場合、画像領域で角度φだけ回転することは、Φ領域で−φだけシフトすることに相当する。これは、Φ_ｒとΦ_ｐの正規化円形相関が−φで１であることを意味している。フーリエ係数のように、回転シグネチュアは１８０°回転対称性を有することに留意する（Φ_ｒ（θ）＝Φ_ｐ（θ＋απ）（αは整数である））。従って、回転シグネチュアから、モジュロ１８０°での回転パラメータを求めることができる。回転が±９０°より大きいか否かが不明の場合は、１回の画素レベルの逆回転および画像相関を行って、複数の選択肢のうちの１個を除外する必要がある。回転対称画像の場合、回転シグネチュアは一様であり、回転を復元することはできない。
【００６２】
離散型で有限の画像についてのスケールシグネチュアに関する説明は、回転シグネチュアについてもよく当てはまる。無限連続画像の場合と有限離散画像の場合の間で認められる最大の不一致点は、有限離散画像の場合にはフーリエ−メリン係数において「＋」形のアーティファクトであるのが普通であるということである。Ｇを適切に選択することで、以下に説明するように、そのアーチファクトが低減される。Ｇによる画素領域フィルタに加えて、フィルタＪを用いて、画像テクスチャにおけるエッジ部からのフーリエ−メリン係数をより強く重み付けする。スケールシグネチュアの場合とは異なり、回転シグネチュアの相関によって、しばしば、実際の回転パラメータの近くに１に近い値を有する狭いピークが得られ、高い信号／ノイズ比が示される。そのため、回転シグネチュアの正規化相関の単一ピークのみを用いて、回転パラメータをモジューロ１８０°で正確に求めることができる場合が多い。
【００６３】
回転係数φを復元するための好ましい処理を図４および図６のフローチャートに示してある。図４は前処理を示し、図６は回転段階３０に固有の好ましい操作を示している。拡大／縮小段階の場合同様に、基準画像ｒ（１１０ｒ）とパターン画像ｐ（１１０ｐ）について、図４に示しかつ上述した前処理を行う。再度、各画像を一連のステップで処理する。その際、最初の部分は両方の画像で同様であり、図４および図６では、基準画像についての添え字「ｒ」およびパターン画像についての添え字「ｐ」によって両者を区別してある。ステップ１１０〜１１８の前処理（基準画像とパターン画像の両方について）は、回転段階３０の以前の部分においては、拡大／縮小段階２０の以前に実施される同じステップと同一である。これらの前処理段階は、拡大／縮小段階と回転段階との各段階について別個に行うことができるが、そうではなく、それらの段階をまとめて行い、次にステップ１１８の出力を、拡大／縮小段階２０におけるステップ１２０および回転段階３０におけるステップ１４０の両方で用いることが好ましいということは、留意すべき点である。
【００６４】
回転段階３０では、ステップ１１８の出力を、ステップ１４０でオプションのフィルタＪを用いてフィルタ処理することで、そこに存在するエッジ部を強調することができる。その後、ステップ１１８（図４）で得られる極−対数（ｌｏｇ_Ｂ（半径）、角度）基準画像および極−対数（ｌｏｇ_Ｂ（半径），角度）パターン画像をそれぞれ、ステップ１４２でそれらのｌｏｇ_Ｂ（半径）軸方向に合計して、それぞれ一次元基準回転シグネチュアおよび一次元パターン回転シグネチュアを得る。次にステップ１４４で、正規化円形相関を用いて、回転シグネチュアを相関させる。正規化円形相関によって、単一の最大値を有する相関回転シグネチュアが得られ、それはステップ１４６で検出される。その最大値を与える角度シフトが、結果として得られる回転係数φ１４８である。
【００６５】
位置合わせの回転段階におけるフーリエ−メリン変換（「ＦＭＴ」）は、拡大／縮小段階について使用されるものと同一であることから、Ｏ（ＮｌｏｇＮ）回の計算は１回だけ行う必要がある。回転については、Ｊ重み付け係数を用いる場合、さらにＮ回の乗算が必要である。ρ軸への投影では、Ｎ−Ｎ^１／２回の加算を必要とする。従って、回転シグネチュアは、Ｏ（ＮｌｏｇＮ）回の演算で得ることができる。一次元円形相関では、さらにＯ（Ｎ^１／２ｌｏｇＮ）回の演算が必要である。拡大／縮小の場合同様、回転は、妥当な画像解像度で検出できることから、入力画像のｋ次ウェーブレット変換によって、Ｏ（（ＮｌｏｇＮ）／４^ｋ）回の演算で回転パラメータを復元することができる。拡大／縮小段階と回転段階について同じフィルタ処理フーリエ−メリン−ウェーブレット変換を用いる場合、回転段階では、拡大／縮小段階を行った後に、Ｎ／４^ｋ程度の回数の独立の演算を行う必要がある。
【００６６】
３．位置合わせの並進移動段階：
並進移動段階の目的は、回転係数φと１以上の可能な拡大／縮小係数を与えられて、並進移動パラメータΔｘおよびΔｙを求めるとともに、１以上の可能な拡大／縮小係数のどれが実際の拡大／縮小係数ｓであるかを決定することにある。並進移動段階４０（図３）について好ましい処理を図７のフローチャートに示す。並進移動段階は、パターン画像を−φだけ回転させて回転パターン画像を得るステップ１６０から開始する。これにより、回転パターン画像では回転が「取り消される」ことになる。次に、各可能な拡大／縮小係数について、その可能な拡大／縮小係数の逆数だけ回転パターン画像を拡大あるいは縮小することにより、候補パターンを得る（ステップ１６２）。したがって、各候補パターンは、１個の可能な拡大／縮小係数と関連し、各候補パターンでは、回転と拡大／縮小の両方の影響が取り消される。ある候補パターンについて取り消される拡大／縮小は、その候補パターンと関連する可能な拡大／縮小係数に相当する。次のステップ１６４では、各候補パターンについて、可能な並進ベクトルを求める。可能な並進ベクトルは、候補パターンをその可能な並進ベクトルだけ並進移動させた場合に、基準画像と並進移動後の候補パターンとの間に最も高い相関を生じる（１９９９年２月２日発行のＳｈａｍｏｏｎらによる米国特許５，８６７，６０９号およびＨ．Ｓｔｏｎｅ， ”ＰｒｏｇｒｅｓｓｉｖｅＷａｖｅｌｅｔＣｏｒｒｅｌａｔｉｏｎＵｓｉｎｇＦｏｕｒｉｅｒＭｅｔｈｏｄｓ，” ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＳｉｇｎａｌＰｒｏｃｅｓｓｉｎｇ，Ｖｏｌ．４７，Ｎｏ．１，ｐｐ．９７−１０７（１９９９年１月）参照）。最後に、ステップ１６６において、基準画像との最高の相関を生じる並進移動後の候補パターンを選択する。選択した候補パターンと関連する可能な拡大／縮小係数と可能な並進ベクトルはそれぞれ、実際の拡大／縮小係数ｓおよび実際の並進ベクトル（Δｘ，Δｙ）を含む。
【００６７】
画像において無効であることが分かっているデータがある場合、基準画像ｒおよびパターン画像ｐについてそれぞれマスクｍおよびｈを用いることで、追加の計算を行うことなく、並進移動段階中それらの閉塞領域を無視することができる。これらのマスクでは、対応する画像画素が有効である場合には値が“１”であり、対応する画素が無効である場合には値が“０”である。これらのマスクでは、補間およびウェーブレット分解によって得られる小数値をとることができる。以下、拡大／縮小係数が分かっている場合を誘導し、多くの可能な拡大／縮小係数がある場合にこの場合をどの程度拡張できるかを示す。多くの可能な拡大／縮小係数がある場合が、位置合わせの拡大／縮小段階の実際の出力に合致する。
【００６８】
基準画像ｒおよびパターン画像ｐは、無限連続画像であるとする。画像ｐ’は、回転および拡大／縮小の影響を取り消した後の画像ｐであるとする。ｈ’は、回転および拡大／縮小の影響を取り消した後のマスクｈであるとする。φとｓが正確に復元された場合、画像ｐ’は並進移動シフトのみ基準画像ｒと異なる。有限画像の場合、画像ｐ’および基準画像ｒも、データが画像枠から出入りする時に生じる妨害（オクルージョン）だけ異なり得る。これらの妨害は、マスクｈ’によって自動的に考慮される。
【００６９】
パターンマスクの大きさが画像マスクの大きさより小さい場合について、バイナリ（二値）有効性マスクを用いて、フーリエ領域での正規化相関係数を計算することが知られている（Ｈ．Ｓｔｏｎｅ， ”ＰｒｏｇｒｅｓｓｉｖｅＷａｖｅｌｅｔＣｏｒｒｅｌａｔｉｏｎＵｓｉｎｇＦｏｕｒｉｅｒＭｅｔｈｏｄｓ，” ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓＯｎＳｉｇｎａｌＰｒｏｃｅｓｓｉｎｇ，Ｖｏｌ．４７，Ｎｏ．１，ｐｐ．９７−１０７（１９９９年１月）参照）。パターン画像の並進移動の関数としての正規化相関係数は、画像を適切に整列するシフト位置で、ほぼ１の値を有する。この方法を拡張して、画像の低解像度表示のための小数有効性マスクが用いられている（Ｍ．ＭｃＧｕｉｒｅｅｔａｌ．， ”ＴｅｃｈｎｉｑｕｅｓＦｏｒＭｕｌｔｉ−ＲｅｓｏｌｕｔｉｏｎＩｍａｇｅＲｅｇｉｓｔｒａｔｉｏｎＩｎＴｈｅＰｒｅｓｅｎｃｅＯｆＯｃｃｌｕｓｉｏｎｓ，” ＰｒｏｃｅｅｄｉｎｇｓＯｆＴｈｅ１９９７ＩｍａｇｅＲｅｇｉｓｔｒａｔｉｏｎＷｏｒｋｓｈｏｐ，ｐｐ．１０１−１２２（１９９７年１１月）参照）。有効性マスクｍおよびｈ’を有する画像ｒおよびｐ’の全ての並進移動シフトについての正規化円形相関係数は下記式で表される。
【００７０】
【数７】

式中、
【００７１】
【外１】

は円形相関を表し、
【００７２】
【数８】

である。ここで、
【００７３】
【外２】

は、ポイント−バイ−ポイント（逐点）の配列乗算である。畳込み定理により、このプロセスは有限画像においてＯ（ＮｌｏｇＮ）回で実効的に計算することができる。
【００７４】
有限画像の場合、式（８）は、パターンマスクでの非ゼロの範囲がいずれの方向でも画像マスクの大きさの１／２より小さいことを仮定していることに、留意すべきである。この仮定に反すると、円形シフトは並進移動とはもはや等価ではなくなり、フーリエ領域では計算を行うことができなくなる。画素領域での相関を計算するには、Ｏ（Ｎ^２）回の演算が必要である。画像が同様の大きさである場合に、Ｏ（Ｎ^２）回の演算を行うのを回避するため、各次元における大きさを２倍にするためにパディングされた画像およびマスクの版について相関を計算することができる。このパディングに関し、パディングされていない画像については、画素法よりフーリエ法の方が高速である。
【００７５】
本発明での並進移動段階は、復元したパラメータφとｓを用いてパターンにおける回転と拡大／縮小を取り消し、画像ｐ’とマスクｈ’を得るものである。次に、式（８）によって、全ての並進移動についての正規化相関係数を計算する。そのピークの位置は、基準画像ｒとパターン画像ｐとの間の並進移動差に直接関係する。ピークが（Ｄ_ｘ，Ｄ_ｙ）のシフト位置で起こる場合、式（２）についての並進パラメータは以下のようになる。
【００７６】
【数９】

並進移動によれば相関に関与する画素が非常に少ないことから、ｐ’のわずかな部分のみがｒと重複し、誤った結果を与え得る並進移動を扱う場合には、いくばくかの注意を払う必要がある。
【００７７】
並進移動段階では、拡大／縮小および回転を取り消すのにＯ（Ｎ）回の演算を行い、正規化相関を実行するのにＯ（ＮｌｏｇＮ）回の演算を行う必要がある。ｋ次のウェーブレットを用いて並進移動のおおまかな推算値を求め、位置合わせを行うことが望ましい。ｋ次ウェーブレット分解によって、各方向に±２^ｋ−１画素の範囲で位置合わせ点を大まかに求めることができる。その大まかな推算値を考慮して、同じ粗並進移動への写像を行う４^ｋ回の可能な精密並進移動によって、最高の分解能で、実際の並進移動の正確な値についての詳細な検索を行うことができる。相関関数がピーク値付近で平滑であると仮定すると、それは、バイナリ（二値）検索アルゴリズムによって、たったの２ｋ回の並進移動のみの調査に減らすことができる。この特性は画像に依存し、一般的には、連続性を示す画像に当てはまる。この手順を用いると、並進移動段階についての総計算回数はＯ（（ＮｌｏｇＮ）／４^ｋ＋Ｎｋ）回である。
【００７８】
上記の議論は、拡大／縮小係数が既知である場合を検討したものである。しかしながら、本発明の方法の拡大／縮小段階では、単一の拡大／縮小係数は得られない。拡大／縮小段階では、可能性の高い拡大／縮小係数のリストが得られる。どの拡大／縮小係数が正しいかを決定するためには、各拡大／縮小係数ごとに並進移動段階を繰り返して、最も高い並進移動相関ピークを与える拡大／縮小係数を選択する。高分解能検索を適用する必要があるのは、粗分解能検索で最も高いピークを与えた拡大／縮小係数のみに対してのみである。ｎ_ｓが位置合わせの拡大／縮小段階によって得られる拡大／縮小係数の数であるとすると、並進移動段階での真の計算回数はＯ（（ｎ_ｓＮｌｏｇＮ）／４^ｋ＋Ｎｋ）回である。回転、拡大／縮小変化および並進移動の各パラメータの復元における総計算回数は、Ｏ（（ｎ_ｓＮｌｏｇＮ）／４^ｋ＋Ｎｋ）回である。
【００７９】
４．フィルタＧ、ＨおよびＪ：
ａ．フィルタＧ
位置合わせの回転段階および拡大／縮小段階においてフーリエ−メリン変換（「ＦＭＴ」）を計算する場合に、フィルタＧを用いることにより、有限画像の内在的なタイリングの影響を小さくすることができる。図８の列（Ａ）には、同一画像の３種類の版、すなわち（１）フィルタ処理されていない画像、（２）「ディスク（円板状）」のフィルタまたはマスクを用いてフィルタ処理した画像、（３）本発明の「ぼかし」フィルタを用いてフィルタ処理した画像を示してある。図８の列（Ｂ）には、それら画像のフーリエ−メリン変換の非ゼロ係数を示してある。
【００８０】
フィルタ処理されていない画像の場合、実際に画像のテクスチャを代表する中央の係数の上に、「＋」形状のアーティファクトが重畳している。このアーティファクトは、上記の内在的タイリングによってのみ生じて実際のデータを不鮮明にし、正確な相関を妨害することから、望ましくない。
【００８１】
回転対称の画像枠を用いることで、このアーティファクトを回避することができる（ＤｅＣａｓｔｒｏｅｔａｌ．の上記の文献）。簡単な実験によって、それが有効であることが確認される。図８の列（Ａ）の２番目の画像は、回転対称画像枠を適用した後の画像である。この場合、フィルタＧはディスク状のマスクであり、所定の半径の外側の画素がゼロに設定されている。ディスクフィルタで処理された画像のフーリエ−メリン変換は、「＋」形状のアーティファクトを示さない。しかしながら、変換から「＋」アーティファクトを除去した後でも、残りの係数は、元の画像のものとは正確には一致しない。フィルタ処理されていない画像とディスクフィルタで処理された画像を比較すると、ディスクフィルタで処理された画像は大きい円形エッジ部を有し、画素が約２５％少ない。それに応じて、フィルタ処理されていない画像のＦＭＴと比較して、ディスクフィルタで処理された画像のＦＭＴでは、半径方向に分布したいくばくかのノイズと、形状の全体的変化とがある。これによって相関ピークが小さくなり、正確さに影響が出る場合がある。ただし、「＋」アーティファクトが除去されることから、ディスクフィルタで処理された画像は、フィルタ処理されていないものよりも優れている。
【００８２】
本発明では、先行技術におけるフィルタ処理されていない画像やディスクフィルタの使用に対して、改良が行われている。詳細には、フィルタＧ、は好ましくは、対向する境界に対して画像の境界をぼかす新規な「ぼかし」フィルタからなる。このフィルタにより、変えられる必要がある画素はごくわずかとなる。図８の列（Ａ）の３番目の画像は、このようなぼかしフィルタで処理した画像である。ぼかしフィルタによって行われるぼかしを図９に特に示してあり、そこでは、図８の列（Ａ）の３番目の画像の９枚のコピーを互いにエッジ同士でタイル状に隣接させて配置してある。好ましくは、そして図９の中央にある画像に関して示されているように、ぼかしフィルタによって、画像の境界の所定数の画素内に画素を補間して、画像の右縁部から画像の左縁部あたりまで（または図９に示したように、元の画像に隣接している場合には、画像のコピーの左縁部あたりまで）、そして画像の上縁部から画像の下縁部あたりまで（または図９に示したように、元の画像に隣接している場合には、画像のコピーの下縁部当たりまで）、滑らかな線形遷移（画素値の移り変わり）が形成される。図８の列（Ａ）に示した大きさの画像では、フィルタは好ましくは画像境界の８画素の範囲内の画素を補間するものであるが、その数字は必須のものではなく、所望に応じて調節することができる。画素を滑らかにして上記の遷移を行うフィルタは、所望のぼかし効果を得るのに十分である。
【００８３】
画像の境界付近の画素以外についてそのようなフィルタを用いても効果がないことから、大半の画素が変化しない。ぼかしフィルタで処理された画像のＦＭＴは、その画像のフーリエ−メリン係数の非ゼロ成分を示すものである。ディスクフィルタ同様、このぼかしフィルタは、図８の列（Ｂ）に示したように、「＋」アーティファクトを有効に除去する。しかしながら、ぼかしフィルタで処理された画像のＦＭＴは、フィルタ処理されていない画像のＦＭＴとほぼ同一であるが、望ましくない「＋」アーティファクトが除去されている。従って、画像を循環的に取り巻くエッジ部をぼかすフィルタＧは、有効なフーリエ−メリン係数をほとんど変えることなく、「＋」アーティファクトを除去する上で優れており、それによって全体的な相関の正確さが向上する。
【００８４】
ｂ．フィルタＨ
フィルタＨは、拡大／縮小段階において、相関前のスケールシグネチュアの信号／ノイズ比を上昇させるために使用される。画素が画像枠から外に出て行ったり画像枠の中に入ってきたりするため、拡大／縮小変換下では、有限画像の内容が大きく変化する場合がある。そこでフィルタＨを用いて、スケールシグネチュアを安定させることができる。移動平均を引くことでスケールシグネチュアから一次の傾向（ｔｒｅｎｄ）を除去するフィルタによって、その安定化が得られる。それを得る一つの方途は、ｘを画像データを表す長さＮのベクトルとするというものである。以下のようにする。
【００８５】
【数１０】

上記のアルゴリズムを用いると、得られるベクトルは、Ｈフィルタで処理された出力となる。
【００８６】
ｃ．フィルタＪ
画像におけるエッジ部に対応するフーリエ−メリン係数を選択的に重み付けするために、フィルタＪが使用される。画素領域での拡大はフーリエ−メリン係数を縮小し、それらの係数は適切には重み付けされないことから、拡大／縮小係数がない場合にフィルタＪを適用するのが最も良い。フーリエ−メリン変換の極表示では、画像テクスチャのエッジに対応する係数は、θ軸に平行かつρ軸の中心近くにある。ρが小さい係数は、画像におけるＤＣ（直流）オフセットと低周波数成分を符号化するものであり、ρが大きい係数は、非常に高い周波数情報とノイズを表す。ＤＣ成分およびノイズ成分を低く抑えながらエッジ部の係数を強調するガウス重み付けは、「＋」アーティファクト、画像における強度シフトおよびノイズの残りのものを抑制しながら、形状のエッジ部を強調するものである。フィルタＪは、特定の種類の画像に適合するようチューニングして性能を高めたり、あるいは任意の拡大／縮小変換のある任意の画像の一般的な場合については除外することができる。
【００８７】
５．要旨および結論：
本発明は、実際の画像対および極端な変換という困難な場合に、良好に機能する。回転、拡大／縮小および並進移動の検出を分離することで、検索空間の大きさを小さくする。プログレッシブなウェーブレット検索の使用とフーリエ領域での相関の計算により、全ての計算が非常に効率的となる。実際、本発明をテストする際に、試験用の画像対を得るのに要する時間は、本発明の方法によりそれらを位置合わせするのにかかった時間より長いことが認められた。画素フィルタとフーリエ−メリンフィルタを導入することで、有限離散フーリエ変換によるアーティファクトが低減され、正確な位置合わせが達成される。Ｇ、ＨおよびＪフィルタを特定の分野からの画像に対してチューニングすることで、より優れた結果を得ることができる。
【００８８】
ＲＳＴ変換に加え、本発明の方法は、基準画像とパターン画像との間の輝度差が定数または線形である場合に良好に機能すると予想される。それらの輝度変化は、フーリエ−メリン領域では一定の線形関数であることから、正規化相関関数によって無視される。並進移動を復元するのに使用される正規化画素相関の値は、線形および一定の輝度変化に対して不変であることは公知である。
【００８９】
以上、各種の画像位置合わせ方法について説明・図示したが、本明細書に添付の特許請求の範囲のみによって限定される本発明の精神および広義の内容から逸脱しない限りにおいて、変更および修正が可能であることは、当業者には明らかであろう。
【００９０】
【発明の効果】
以上説明したように本発明は、基準画像とパターン画像との間のＲＳＴ変換を規定する変換パラメータを少ない演算量で正確に復元でき、相関関数における１に近いピーク相関と高い信号／ノイズ比を達成し、基準画像とパターン画像との位置合わせの正確さが大幅に向上するという効果がある。
【図面の簡単な説明】
【図１】基準画像とその基準画像を回転させた画像、拡大／縮小した画像、並進移動させた画像からなる画素領域における４個の理想化された画像と、これら画像のフーリエ−メリン領域における非ゼロ係数の等高線プロットとを示す図である。
【図２】基準画像とその基準画像を回転させた画像、拡大／縮小した画像、並進移動させた画像からなる画素領域における４個の実際の画像と、これら画像のフーリエ−メリン領域における非ゼロ係数の等高線プロットとを示す図である。
【図３】本発明の画像位置合わせ方法の全体的な処理を示すフローチャートである。
【図４】本発明の画像位置合わせ方法における、基準画像とパターン画像の前処理を示すフローチャートである。
【図５】本発明の画像位置合わせ方法における、１以上の可能な拡大／縮小係数を復元する処理を示すフローチャートである。
【図６】本発明の画像位置合わせ方法における回転係数φを復元する処理を示すフローチャートである。
【図７】本発明の画像位置合わせ方法における、並進ベクトル（Δｘ，Δｙ）および実際の拡大／縮小係数ｓを復元する処理を示すフローチャートである。
【図８】フィルタ処理されていない画像、フィルタ処理されていない画像にディスクフィルタ処理した画像およびフィルタ処理されていない画像にぼかしフィルタ処理した画像からなる画素領域の３種類の画像（実線の黒い境界は画像の一部を含むものではなく、単に各画像の外側の境界を示すためのものである）と、フーリエ−メリン領域におけるこれら画像の非ゼロ係数に対応する等高線プロットを示す図である。
【図９】図８の列（Ａ）に示すぼかしフィルタ処理された画像を９枚、エッジ部同士で隣接するようにタイル状に配置した状態を示す図である。
【符号の説明】
１０前処理段階
２０拡大／縮小段階
３０回転段階
４０並進移動段階

Claims

パターン画像と基準画像とが拡大／縮小係数ｓ、回転係数φおよび並進ベクトル(Δｘ，Δｙ)によって決まる回転−拡大／縮小−並進移動変換によって互いに異なっているときに、前記基準画像に前記パターン画像を位置合わせする方法であって、
（ａ）前記基準画像と前記パターン画像を前処理する段階であって、
（ａ−１）前記基準画像と前記パターン画像をフィルタ処理して、前記基準画像と前記パターン画像の内在的タイリングによって生じるアーティファクトを防止するステップと、
（ａ−２）前記アーティファクトを防止するステップ（ａ−１）の後、前記基準画像と前記パターン画像を、画素領域からフーリエ−メリン領域に変換して、それぞれ変換基準画像および変換パターン画像を得るステップと、
（ａ−３）前記変換基準画像と前記変換パターン画像をデカルト(ｘ，ｙ)座標から極−対数（ｌｏｇ_B (半径)，角度）座標（Ｂは大域定数対数底である）に変換するステップと、を含む段階と；
（ｂ）少なくとも１つの可能な拡大／縮小係数を復元する段階であって、
（ｂ−１）前記極−対数（ｌｏｇ_B (半径)，角度）座標での変換基準画像と前記極−対数（ｌｏｇ_B (半径)，角度）座標での変換パターン画像を、それぞれ、それらの角度軸方向に合計して、基準スケールシグネチュアとパターンスケールシグネチュアを得るステップと、
（ｂ−２）正規化相関を用いて前記基準スケールシグネチュアを前記パターンスケールシグネチュアに相関させ、相関スケールシグネチュアを得るステップと、
（ｂ−３）スケールシグネチュアシフトの集合からなる、前記相関スケールシグネチュアの極大を検出するステップと、
（ｂ−４）対数底Ｂを前記各スケールシグネチュアシフトでべき乗して、少なくとも１つの可能な拡大／縮小係数を得るステップと、を含む段階と；
（ｃ）回転係数φを復元する段階であって、
（ｃ−１）前記極−対数（ｌｏｇ_B (半径)，角度）座標での変換基準画像および前記極−対数（ｌｏｇ_B (半径)，角度）座標での変換パターン画像を、それぞれ、それらのｌｏｇ_B (半径)軸方向に合計して、基準回転シグネチュアとパターン回転シグネチュアを得るステップと、
（ｃ−２）正規化円形相関を用いて前記基準回転シグネチュアをパターン回転シグネチュアと相関させ、相関回転シグネチュアを得るステップと、
（ｃ−３）回転係数φからなる、前記相関回転シグネチュアの最大値を検出するステップと、を含む段階と；
（ｄ）実際の拡大／縮小係数ｓおよび並進ベクトル(Δｘ，Δｙ)を復元する段階であって、
（ｄ−１）前記パターン画像を−φだけ回転して、回転パターン画像を得るステップと、
（ｄ−２）前記各可能な拡大／縮小係数ごとに、その可能な拡大／縮小係数の逆数によって前記回転パターン画像を再度拡大／縮小させ、候補パターンを得るステップと、
（ｄ−３）各候補パターンごとに、可能な並進ベクトルであって、その候補ベクトルをその可能な並進ベクトルによって並進移動させたときに前記基準画像と並進移動後の候補パターンとが最も高い相関を示す可能な並進ベクトルを求めるステップと、
（ｄ−４）前記基準画像に対して最高の相関を与える並進移動後の候補パターンを選択することで、その候補パターンに関連する可能な拡大／縮小係数と可能な並進ベクトルとが、それぞれ、実際の拡大／縮小係数ｓと実際の並進ベクトル(Δｘ，Δｙ)を含むようにするステップと、を含む段階と；
を有する画像位置合わせ方法。
前記基準画像および前記パターン画像の前処理の段階（ａ）が、さらに、前記アーティファクトを防止するステップ（ａ−１）の後であって前記変換ステップ（ａ−２）の前に、前記基準画像と前記パターン画像をウェーブレット分解するステップを有する請求項１に記載の画像位置合わせ方法。
アーティファクトを防止するための前記フィルタ処理のステップが、ぼかしフィルタによって前記基準画像および前記パターン画像をフィルタ処理し、アーティファクトを除去するステップである請求項１に記載の画像位置合わせ方法。
前記少なくとも１つの可能な拡大／縮小係数を復元する段階（ｂ）が、さらに、前記合計するステップ（ｂ−１）の後であって前記相関させるステップ（ｂ−２）の前に、前記基準スケールシグネチュアおよび前記パターンスケールシグネチュアをフィルタ処理して、各スケールシグネチュアの信号／ノイズ比を高くするステップを有する、請求項１に記載の画像位置合わせ方法。
前記回転係数φを復元する段階（ｃ）が、さらに、合計するステップ（ｃ−１）の前に、前記極−対数（ｌｏｇ_B (半径)，角度）座標による変換基準画像および前記極−対数（ｌｏｇ_B (半径)，角度）座標による前記変換パターン画像をフィルタ処理して、そこに存在するエッジ部を強調するステップを有する、請求項１に記載の画像位置合わせ方法。
パターン画像と基準画像とが拡大／縮小係数ｓ、回転係数φおよび並進ベクトル(Δｘ，Δｙ)によって決まる回転−拡大／縮小−並進移動変換によって互いに異なっており、前記拡大／縮小係数ｓが既知であるときに、前記基準画像に前記パターン画像を位置合わせする方法であって、
（ａ）前記基準画像と前記パターン画像を前処理する段階であって、
（ａ−１）前記基準画像と前記パターン画像をフィルタ処理して、前記基準画像と前記パターン画像の内在的タイリングによって生じるアーティファクトを防止するステップと、
（ａ−２）前記アーティファクトを防止するステップ（ａ−１）の後、前記基準画像と前記パターン画像を、画素領域からフーリエ−メリン領域に変換して、それぞれ変換基準画像および変換パターン画像を得るステップと、
（ａ−３）前記変換基準画像と前記変換パターン画像をデカルト(ｘ，ｙ)座標から極−対数（ｌｏｇ_B (半径)，角度）座標（Ｂは大域定数対数底である）に変換するステップと、を含む段階と；
（ｂ）回転係数φを復元する段階であって、
（ｂ−１）前記極−対数（ｌｏｇ_B (半径)，角度）座標での変換基準画像および前記極−対数（ｌｏｇ_B (半径)，角度）座標での変換パターン画像を、それぞれ、それらのｌｏｇ_B (半径)軸方向に合計して、基準回転シグネチュアとパターン回転シグネチュアを得るステップと、
（ｂ−２）正規化円形相関を用いて前記基準回転シグネチュアをパターン回転シグネチュアと相関させ、相関回転シグネチュアを得るステップと、
（ｂ−３）回転係数φからなる、前記相関回転シグネチュアの最大値を検出するステップと、を含む段階と；
（ｃ）並進ベクトル(Δｘ，Δｙ)を復元する段階であって、
（ｃ−１）前記パターン画像を−φだけ回転して、回転パターン画像を得るステップと、
（ｃ−２）前記拡大／縮小係数ｓの逆数によって前記回転パターン画像を再度拡大／縮小させ、候補パターンを得るステップと、
（ｃ−３）前記候補パターンを並進ベクトル(Δｘ，Δｙ)によって並進移動させたときに前記基準画像と並進移動後の候補パターンとが最も高い相関を示すように、並進ベクトル(Δｘ，Δｙ)を求めるステップと、を含む段階と；
を有する画像位置合わせ方法。
前記基準画像および前記パターン画像の前処理の段階（ａ）が、さらに、前記アーティファクトを防止するステップ（ａ−１）の後であって前記変換ステップ（ａ−２）の前に、前記基準画像と前記パターン画像をウェーブレット分解するステップを有する請求項６に記載の画像位置合わせ方法。
アーティファクトを防止するための前記フィルタ処理のステップが、ぼかしフィルタによって前記基準画像および前記パターン画像をフィルタ処理し、アーティファクトを除去するステップである請求項６に記載の画像位置合わせ方法。
前記回転係数φを復元する段階（ｂ）が、さらに、合計するステップ（ｂ−１）の前に、前記極−対数（ｌｏｇ_B (半径)，角度）座標による変換基準画像および前記極−対数（ｌｏｇ_B (半径)，角度）座標による前記変換パターン画像をフィルタ処理して、そこに存在するエッジ部を強調するステップを有する、請求項６に記載の画像位置合わせ方法。
パターン画像と基準画像とが拡大／縮小係数ｓ、回転係数φおよび並進ベクトル(Δｘ，Δｙ)によって決まる回転−拡大／縮小−並進移動変換によって互いに異なっており、前記回転係数φが既知であるときに、前記基準画像に前記パターン画像を位置合わせする方法であって、
（ａ）前記基準画像と前記パターン画像を前処理する段階であって、
（ａ−１）前記基準画像と前記パターン画像をフィルタ処理して、前記基準画像と前記パターン画像の内在的タイリングによって生じるアーティファクトを防止するステップと、
（ａ−２）前記アーティファクトを防止するステップ（ａ−１）の後、前記基準画像と前記パターン画像を、画素領域からフーリエ−メリン領域に変換して、それぞれ変換基準画像および変換パターン画像を得るステップと、
（ａ−３）前記変換基準画像と前記変換パターン画像をデカルト(ｘ，ｙ)座標から極−対数（ｌｏｇ_B (半径)，角度）座標（Ｂは大域定数対数底である）に変換するステップと、を含む段階と；
（ｂ）少なくとも１つの可能な拡大／縮小係数を復元する段階であって、
（ｂ−１）前記極−対数（ｌｏｇ_B (半径)，角度）座標での変換基準画像と前記極−対数（ｌｏｇ_B (半径)，角度）座標での変換パターン画像を、それぞれ、それらの角度軸方向に合計して、基準スケールシグネチュアとパターンスケールシグネチュアを得るステップと、
（ｂ−２）正規化相関を用いて前記基準スケールシグネチュアを前記パターンスケールシグネチュアに相関させ、相関スケールシグネチュアを得るステップと、
（ｂ−３）スケールシグネチュアシフトの集合からなる、前記相関スケールシグネチュアの極大を検出するステップと、
（ｂ−４）対数底Ｂを前記各スケールシグネチュアシフトでべき乗して、少なくとも１つの可能な拡大／縮小係数を得るステップと、を含む段階と；
（ｃ）実際の拡大／縮小係数ｓおよび並進ベクトル(Δｘ，Δｙ)を復元する段階であって、
（ｃ−１）前記パターン画像を−φだけ回転して、回転パターン画像を得るステップと、
（ｃ−２）前記各可能な拡大／縮小係数ごとに、その可能な拡大／縮小係数の逆数によって前記回転パターン画像を再度拡大／縮小させ、候補パターンを得るステップと、
（ｃ−３）各候補パターンごとに、可能な並進ベクトルであって、その候補ベクトルをその可能な並進ベクトルによって並進移動させたときに前記基準画像と並進移動後の候補パターンとが最も高い相関を示す可能な並進ベクトルを求めるステップと、
（ｃ−４）前記基準画像に対して最高の相関を与える並進移動後の候補パターンを選択することで、その候補パターンに関連する可能な拡大／縮小係数と可能な並進ベクトルとが、それぞれ、実際の拡大／縮小係数ｓと実際の並進ベクトル(Δｘ，Δｙ)を含むようにするステップと、を含む段階と；
を有する画像位置合わせ方法。
前記基準画像および前記パターン画像の前処理の段階（ａ）が、さらに、前記アーティファクトを防止するステップ（ａ−１）の後であって前記変換ステップ（ａ−２）の前に、前記基準画像と前記パターン画像をウェーブレット分解するステップを有する請求項１０に記載の画像位置合わせ方法。
アーティファクトを防止するための前記フィルタ処理のステップが、ぼかしフィルタによって前記基準画像および前記パターン画像をフィルタ処理し、アーティファクトを除去するステップである請求項１０に記載の画像位置合わせ方法。
前記少なくとも１つの可能な拡大／縮小係数を復元する段階（ｂ）が、さらに、前記合計するステップ（ｂ−１）の後であって前記相関させるステップ（ｂ−２）の前に、前記基準スケールシグネチュアおよび前記パターンスケールシグネチュアをフィルタ処理して、各スケールシグネチュアの信号／ノイズ比を高くするステップを有する、請求項１０に記載の画像位置合わせ方法。