(57)【要約】【課題】平行移動、スケール変化（拡大／縮小）に対する耐性の高い画像類似度が得られるパターンマッチング方法及び装置を提供することを目的とする。【解決手段】入力された第１の画像から、周波数平面上での前記第１の画像の周波数成分の変化を示す第１の関数を求めるとともに、入力された第２の画像から、前記周波数平面上での前記第２の画像の周波数成分の変化を示す第２の関数を求め、前記周波数平面上の各点について、前記第１の関数の位相と前記第２の関数の位相との類似度を示す位相類似度を計算し、前記周波数平面上での周波数軸に対して互いに線対称の位置にある２つの点の組合せ毎に前記位相類似度の積を計算するとともに、前記周波数平面上の各組合せについて求めた前記積の総和を計算することにより、前記第１の画像と前記第２の画像との類似度を示す画像類似度を計算する。【選択図】      図３
2008191937.tif 000002
【特許請求の範囲】
【請求項１】
第１の画像及び第２の画像を入力する入力ステップと、
周波数平面上での前記第１の画像の周波数成分の変化を示す第１の関数を求める第１の変換ステップと、
前記周波数平面上での前記第２の画像の周波数成分の変化を示す第２の関数を求める第２の変換ステップと、
前記周波数平面上の各点について、前記第１の関数の位相と前記第２の関数の位相との類似度を示す位相類似度を計算する位相類似度計算ステップと、
前記周波数平面上で周波数軸に対して互いに線対称の位置にある２つの点の組合せ毎に前記位相類似度の積を計算するとともに、前記周波数平面上の各組合せについて求めた前記積の総和を計算することにより、前記第１の画像と前記第２の画像との類似度を示す画像類似度を計算する画像類似度計算ステップと、
を含むパターンマッチング方法。
【請求項２】
前記位相類似度計算ステップは、前記周波数平面上の第１及び第４の象限内の各点（ｉ、ｊ）における前記第１の関数と前記第２の関数との位相類似度γ1,iγ*2,iと、前記周波数平面上の第２及び第３の象限内の各点（−ｉ、ｊ）における第１の関数と第２の関数との位相類似度γ1,-iγ*2,-iを計算し、
前記画像類似度計算ステップは、前記画像類似度Ｓ（１、２）
【数１】
2008191937.tif 000019
を計算することを特徴とする請求項１記載のパターンマッチング方法。
【請求項３】
前記位相類似度計算ステップは、前記周波数平面上の第１及び第４の象限内の各点（ｉ、ｊ）における前記第１の関数と前記第２の関数との位相類似度γ1,iγ*2,iと、前記周波数平面上の第２及び第３の象限内の各点（−ｉ、ｊ）における第１の関数と第２の関数との位相類似度γ1,-iγ*2,-iを計算し、
前記画像類似度計算ステップは、振幅の総和により正規化を行った前記画像類似度Ｓ（１、２）
【数２】
2008191937.tif 000020
を計算することを特徴とする請求項１記載のパターンマッチング方法。
【請求項４】
第１の画像及び第２の画像を入力する入力ステップと、
周波数平面上での前記第１の画像の周波数成分の変化を示す第１の関数を求める第１の変換ステップと、
前記周波数平面上での前記第２の画像の周波数成分の変化を示す第２の関数を求める第２の変換ステップと、
前記周波数平面上の各点について、前記第１の関数の位相と前記第２の関数の位相との類似度を示す位相類似度を計算する位相類似度計算ステップと、
前記周波数平面の原点に関し互いに点対称の位置にある２つの点の組合せ毎に前記位相類似度の積を計算するとともに、前記周波数平面上の各組合せについて求めた前記積の総和を計算することにより、前記第１の画像と前記第２の画像との類似度を示す画像類似度を計算する画像類似度計算ステップと、
を含むパターンマッチング方法。
【請求項５】
前記位相類似度計算ステップは、前記周波数平面上の第１の象限内の各点（ｉ、ｊ）における前記第１の関数と前記第２の関数との位相類似度γ1i,j(γ2i,j)*と、前記周波数平面上の第２の象限内の各点（−ｉ、ｊ）における第１の関数と第２の関数との位相類似度γ1-i,j(γ2-i,j)*と、前記周波数平面上の第３の象限内の各点（−ｉ、−ｊ）における第１の関数と第２の関数との位相類似度γ1-i,-j(γ2-i,-j)*と、前記周波数平面上の第４の象限内の各点（ｉ、−ｊ）における第１の関数と第２の関数との位相類似度γ1i,-j(γ2i,-j)*を計算し、
前記画像類似度計算ステップは、前記画像類似度Ｓ（１、２）
【数３】
2008191937.tif 000021
を計算することを特徴とする請求項４記載のパターンマッチング方法。
【請求項６】
前記位相類似度計算ステップは、前記周波数平面上の第１の象限内の各点（ｉ、ｊ）における前記第１の関数と前記第２の関数との位相類似度γ1i,j(γ2i,j)*と、前記周波数平面上の第２の象限内の各点（−ｉ、ｊ）における第１の関数と第２の関数との位相類似度γ1-i,j(γ2-i,j)*と、前記周波数平面上の第３の象限内の各点（−ｉ、−ｊ）における第１の関数と第２の関数との位相類似度γ1-i,-j(γ2-i,-j)*と、前記周波数平面上の第４の象限内の各点（ｉ、−ｊ）における第１の関数と第２の関数との位相類似度γ1i,-j(γ2i,-j)*を計算し、
前記画像類似度計算ステップは、振幅の総和により正規化を行った前記画像類似度Ｓ（１、２）
【数４】
2008191937.tif 000022
を計算することを特徴とする請求項４記載のパターンマッチング方法。
【請求項７】
第１の画像及び第２の画像を入力する入力手段と、
周波数平面上での前記第１の画像の周波数成分の変化を示す第１の関数及び前記第２の画像の周波数成分の変化を示す第２の関数を求める変換手段と、
前記周波数平面上の各点について、前記第１の関数の位相と前記第２の関数の位相との類似度を示す位相類似度を計算する位相類似度計算手段と、
前記周波数平面上で周波数軸に対して互いに線対称の位置にある２つの点の組合せ毎に前記位相類似度の積を計算するとともに、前記周波数平面上の各組合せについて求めた前記積の総和を計算することにより、前記第１の画像と前記第２の画像との類似度を示す画像類似度を計算する画像類似度計算手段と、
を具備したことを特徴とするパターンマッチング装置。
【請求項８】
前記位相類似度計算手段は、前記周波数平面上の第１及び第４の象限内の各点（ｉ、ｊ）における前記第１の関数と前記第２の関数との位相類似度γ1,iγ*2,iと、前記周波数平面上の第２及び第３の象限内の各点（−ｉ、ｊ）における第１の関数と第２の関数との位相類似度γ1,-iγ*2,-iを計算し、
前記画像類似度計算手段は、前記画像類似度Ｓ（１、２）
【数５】
2008191937.tif 000023
を計算することを特徴とする請求項７記載のパターンマッチング装置。
【請求項９】
前記位相類似度計算手段は、前記周波数平面上の第１及び第４の象限内の各点（ｉ、ｊ）における前記第１の関数と前記第２の関数との位相類似度γ1,iγ*2,iと、前記周波数平面上の第２及び第３の象限内の各点（−ｉ、ｊ）における第１の関数と第２の関数との位相類似度γ1,-iγ*2,-iを計算し、
前記画像類似度計算手段は、振幅の総和により正規化を行った前記画像類似度Ｓ（１、２）
【数６】
2008191937.tif 000024
を計算することを特徴とする請求項７記載のパターンマッチング装置。
【請求項１０】
第１の画像及び第２の画像を入力する入力手段と、
周波数平面上での前記第１の画像の周波数成分の変化を示す第１の関数及び前記第２の画像周波数成分の変化を示す第２の関数を求める変換手段と、
前記周波数平面上の各点について、前記第１の関数の位相と前記第２の関数の位相との類似度を示す位相類似度を計算する位相類似度計算手段と、
前記周波数平面の原点に関し互いに点対称の位置にある２つの点の組合せ毎に前記位相類似度の積を計算するとともに、前記周波数平面上の各組合せについて求めた前記積の総和を計算することにより、前記第１の画像と前記第２の画像との類似度を示す画像類似度を計算する画像類似度計算手段と、
を具備したことを特徴とするパターンマッチング装置。
【請求項１１】
前記位相類似度計算手段は、前記周波数平面上の第１の象限内の各点（ｉ、ｊ）における前記第１の関数と前記第２の関数との位相類似度γ1i,j(γ2i,j)*と、前記周波数平面上の第２の象限内の各点（−ｉ、ｊ）における第１の関数と第２の関数との位相類似度γ1-i,j(γ2-i,j)*と、前記周波数平面上の第３の象限内の各点（−ｉ、−ｊ）における第１の関数と第２の関数との位相類似度γ1-i,-j(γ2-i,-j)*と、前記周波数平面上の第４の象限内の各点（ｉ、−ｊ）における第１の関数と第２の関数との位相類似度γ1i,-j(γ2i,-j)*を計算し、
前記画像類似度計算手段は、前記画像類似度Ｓ（１、２）
【数７】
2008191937.tif 000025
を計算することを特徴とする請求項１０記載のパターンマッチング装置。
【請求項１２】
前記位相類似度計算手段は、前記周波数平面上の第１の象限内の各点（ｉ、ｊ）における前記第１の関数と前記第２の関数との位相類似度γ1i,j(γ2i,j)*と、前記周波数平面上の第２の象限内の各点（−ｉ、ｊ）における第１の関数と第２の関数との位相類似度γ1-i,j(γ2-i,j)*と、前記周波数平面上の第３の象限内の各点（−ｉ、−ｊ）における第１の関数と第２の関数との位相類似度γ1-i,-j(γ2-i,-j)*と、前記周波数平面上の第４の象限内の各点（ｉ、−ｊ）における第１の関数と第２の関数との位相類似度γ1i,-j(γ2i,-j)*を計算し、
前記画像類似度計算手段は、振幅の総和により正規化を行った前記画像類似度Ｓ（１、２）
【数８】
2008191937.tif 000026
を計算することを特徴とする請求項１０記載のパターンマッチング装置。
【請求項１３】
コンピュータを、
第１の画像及び第２の画像を入力する入力手段、
周波数平面上での前記第１の画像の周波数成分の変化を示す第１の関数及び前記第２の画像の周波数成分の変化を示す第２の関数を求める変換手段、
前記周波数平面上の各点について、前記第１の関数の位相と前記第２の関数の位相との類似度を示す位相類似度を計算する位相類似度計算手段、
前記周波数平面上での周波数軸に対して互いに線対称の位置にある２つの点の組合せ毎に前記位相類似度の積を計算するとともに、前記周波数平面上の各組合せについて求めた前記積の総和を計算することにより、前記第１の画像と前記第２の画像との類似度を示す画像類似度を計算する画像類似度計算手段、
として機能させるためのプログラム。
【請求項１４】
コンピュータを、
第１の画像及び第２の画像を入力する入力手段、
周波数平面上での前記第１の画像の周波数成分の変化を示す第１の関数及び前記第２の画像の周波数成分の変化を示す第２の関数を求める変換手段、
前記周波数平面上の各点について、前記第１の関数の位相と前記第２の関数の位相との類似度を示す位相類似度を計算する位相類似度計算手段、
前記周波数平面の原点に関し互いに点対称の位置にある２つの点の組合せ毎に前記位相類似度の積を計算するとともに、前記周波数平面上の各組合せについて求めた前記積の総和を計算することにより、前記第１の画像と前記第２の画像との画像類似度を計算する画像類似度計算手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターンマッチング方法及び装置に関する。
【背景技術】
【０００２】
コンピュータビジョンの分野において画像の対応点探索やパターンと対応する領域の切り出しなどの処理は、最も基本的ではあるが、多くの問題がある。これには、ノイズの影響や、照明変動や、スケール変化（拡大・縮小）と回転に対する直積空間での探索が必要となるなどがある。物体領域はいくつかの手法を用いて抽出することは可能であるが、実際には抽出は微少ながらスケールと位置に対して変動させる必要がある。そのため画像の比較を行うための、平行移動とスケールに対して不変性を有する記述子の開発が求められる。
【０００３】
そのような変動が存在する画像の比較を行う場合、局所的には変動の影響は小さく無視できると考えられていたが、平行移動の影響が画像に著しい変化をもたらす。画像の小さい平行移動は、細かな不連続値の近くで著しく輝度値に影響し、局所的に画像間で小さな誤対応か、全体に精度の低い比較結果をもたらす。
【０００４】
非特許文献１記載の手法は、平行移動に対しては耐性を有する画像類似度の計算手法を提供する。
【非特許文献１】Z. Wang, E.P. Simoncelli, Translation insensitive image similarity in complex wavelet domain. In Proceedings of IEEE Conference Acoustic, Speech and Signal Processing, 2005.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１のように、従来の画像マッチング手法では、平行移動に対しては耐性を有する画像類似度を計算することができるが、スケールの変化や、回転などを含むアフィン変換に対しては、画像類似度が低下するという問題点があった。
【０００６】
そこで、本発明は、上記問題点に鑑み、平行移動、スケール変化（拡大／縮小）に対する耐性の高い画像類似度が得られ、互いに相似するパターンに対し、高い認識率が得られる画像類似度を計算することができるパターンマッチング方法及び装置を提供することを目的とする。
【０００７】
また、本発明は、平行移動、スケール変化（拡大／縮小）の他にさらに、回転に対する耐性の高い画像類似度が得られ、互いに相似するパターンに対し、高い認識率が得られる画像類似度を計算することができるパターンマッチング方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
（ａ）入力された第１の画像から、周波数平面上での前記第１の画像の周波数成分の変化を示す第１の関数を求めるとともに、入力された第２の画像から、前記周波数平面上での前記第２の画像の周波数成分の変化を示す第２の関数を求め、（ｂ）前記周波数平面上の各点について、前記第１の関数の位相と前記第２の関数の位相との類似度を示す位相類似度を計算し、（ｃ）前記周波数平面上での周波数軸に対して互いに線対称の位置にある２つの点の組合せ毎に前記位相類似度の積を計算するとともに、前記周波数平面上の各組合せについて求めた前記積の総和を計算することにより、前記第１の画像と前記第２の画像との類似度を示す画像類似度を計算する。
【０００９】
（ａ）入力された第１の画像から、周波数平面上での前記第１の画像の周波数成分の変化を示す第１の関数を求めるとともに、入力された第２の画像から、前記周波数平面上での前記第２の画像の周波数成分の変化を示す第２の関数を求め、（ｂ）前記周波数平面上の各点について、前記第１の関数の位相と前記第２の関数の位相との位相類似度を計算し、（ｃ）前記周波数平面の原点に関し互いに点対称の位置にある２つの点の組合せ毎に前記位相類似度の積を計算するとともに、前記周波数平面上の各組合せについて求めた前記積の総和を計算することにより、前記第１の画像と前記第２の画像との類似度を示す画像類似度を計算する。
【発明の効果】
【００１０】
本発明によれば、平行移動、スケール変化（拡大／縮小）に対する耐性の高い画像類似度が得られ、互いに相似するパターンに対し、高い認識率が得られる。
【００１１】
また、平行移動、スケール変化（拡大／縮小）、回転に対する耐性の高い画像類似度が得られ、互いに相似するパターンに対し、高い認識率が得られる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施形態について図面を参照して説明する。
【００１３】
まず、各画像の信号をウェーブレット変換した結果得られる関数を用いて、位相と位相に基づく平行移動に対する不変性について説明する。その後、平行移動に対する不変性を維持するとともに、スケール変化（拡大率・縮小率の変化）に対する不変性をも有する画像類似度の計算方法と、さらにアフィン変換に対する不変性を有する画像類似度の計算方法について説明する。
【００１４】
位相は、数学的には、Ｈｉｌｂｅｒｔ変換とＲｉｅｓｚ変換の２つの関数の比である。一次元では、位相が９０度ずれるため、２つの関数が直交する。簡単な例として、正弦と余弦がある。
【００１５】
ｅｊωφ＝ｃｏｓωφ＋ｊｓｉｎωφ
ここでｊ＝（−１）1/2、ω＝２πｆ、ｆは周波数、φは位相の角度である。
【００１６】
１つの周波数から構成される信号の比は簡単に得ることができるが、より複雑な信号の位相は通常、１つ以上の周波数帯域での平均位相から求める。画像のような信号の位相は、Ｒｉｅｓｚ変換の関連要素である分析的ウェーブレットの偶関数と奇関数の成分の応答の比から定義できる。
【００１７】
一般的に、分析的ウェーブレットは、ガウス関数により正弦波と余弦波を畳み込んだ正弦窓関数から形成することと同じである。
【００１８】
【数９】
2008191937.tif 000003
【００１９】
ここで、σはガウス分布の広り、ωは周波数である。
【００２０】
一次と二次のガウシアンの導関数と対照的なガボールウェーブレットを使用する主な利点は、線形位相が得られることである。距離δｘ（＝λ（δφ／２π）、λはフィルタの波長）だけ信号を一様にシフトさせると、位相もまた比例してシフトする。この特性は平行移動に対する不変性を意味する。
【００２１】
任意の信号がわずかな距離で平行移動するなら、振幅差を詳細に予測することはできないが、エルゴード的な信号であるなら、局所的な変化であるため予測することが可能となり、局所的な位相差はどこでも同じになる。以下に、比較関数の観測結果から類似度を求める方法を示す。
【００２２】
２つの角度φ１、φ２の位相差を簡単に、φ１−φ２とし、
位相もまた
ｅｊφ＝ｃｏｓφ＋ｊｓｉｎφ＝α＋ｊβ＝γ
とする。
【００２３】
自明であるが、以下のようになる。
【００２４】
【数１０】
2008191937.tif 000004
【００２５】
＊は共役複素数を示す。ここでは、位相差φ１−φ２を（間接的に）表すγ1γ*2を位相類似度と呼ぶ。
【００２６】
一方がδｘだけシフトした２つの同一の信号に関して第１の信号と第２の信号は、全ての点における位相差が一定となり、位相差がｃωとなる。すなわち、第１の信号の任意の点ｘにおける周波数平面上での位相と、第２の信号の任意の点ｘにおける周波数平面上での位相類似度をγx,1γ*x,2と表すと、次式（３）のように表すことができる。
【００２７】
【数１１】
2008191937.tif 000005
【００２８】
また、第１の信号と、該信号をわずかに平行移動させた第２の信号との間では、周波数平面（画像平面）上の全領域に対し、次式（４）が成立する。
【００２９】
【数１２】
2008191937.tif 000006
【００３０】
しかし、異なる２つの信号の場合、すなわち、信号間の差がランダムである場合には、式（４）は成立しない。信号間の差がランダムである場合、位相差の合計が確率変数になる。この考えに基づき、以下ように、２つの画像間の画像類似度を定義する。
【００３１】
【数１３】
2008191937.tif 000007
【００３２】
図１は、式（５）に示した画像類似度の算出方法を説明するための図である。
【００３３】
図１では、第１の画像と第２の画像との間の画像類似度を算出する場合を示している。まず、第１の画像（各画素の位置（ｘ、ｙ）と該画素の画素値との関数Ｉ1（ｘ、ｙ））を、例えば、ガボールウェーブレット変換（ガボール変換）により、周波数平面上の関数Ｇ1（ｕ、ｖ）へ周波数変換する。なお、図１（ｅ）では、説明の簡単のために、関数Ｇ1（ｕ）のみを示している。
【００３４】
また、第２の画像（各画素の位置（ｘ、ｙ）と該画素の画素値との関数Ｉ2（ｘ、ｙ））を、例えば、ガボール変換により、周波数平面上の関数Ｇ2（ｕ、ｖ）へ周波数変換する。なお、図３（ｅ）では、説明の簡単のために、関数Ｇ2（ｕ）のみを示している。
【００３５】
ここで、ｕ、ｖで表される周波数平面は複素数平面となる。また、関数Ｇ1（ｕ）、Ｇ2（ｕ）の振幅は、当該局所領域の画素値に依存する値となる。さらに、周波数平面上の点（ｉ、ｊ）における上記Ｇ1（ｕ、ｖ）、Ｇ2（ｕ、ｖ）を、Ｇ1i,j（ｕ、ｖ）、Ｇ2i,j（ｕ、ｖ）と表す。
【００３６】
次に、周波数平面上の各点（ｉ、ｊ）における、上記関数Ｇ1i,j（ｕ、ｖ）、Ｇ2i,j（ｕ、ｖ）を用いて、関数Ｇ1i,j（ｕ、ｖ）とＧ2i,j（ｕ、ｖ）との位相類似度γ1i,j(γ2i,j)*を求める。なお、図１（ｅ）では、説明の簡単のため、各局所領域における位相類似度をγ1γ*2と表している。このとき位相類似度は、複素ベクトルとなる。
【００３７】
式（５）では、第１の画像の周波数平面上での点（ｉ、ｊ）における位相情報をγ1,i、第２の画像の周波数平面上の点（ｉ、ｊ）における位相情報をγ2,iと表し、Ｎは周波数平面上での探索範囲であり、ηは、分母が「０」となることを防ぐための極小の定数値である。
【００３８】
式（５）では、周波数平面上の各点で求めた位相類似度γ1,iγ*2,iの総和を求めて、これを画像類似度としている。より具体的には、この総和を全エネルギーで正規化した値が式（５）で計算される画像類似度である。
【００３９】
式（５）の画像類似度を照明変動に対して安定させるため、式（５）の分母においてγ1,iとγ2,iとのそれぞれの絶対値の総和とする。コントラストに対して不変性を有する画像類似度が求められる場合、分母をγ1,iとγ2,iとのそれぞれの振幅の総和にすることにより実現できる。しかしながら位相類似度γ1,iγ*2,iは、γ1,iとγ2,iの一方が「０」であるなら、位相類似度も「０」となるため、γｉ≠０となる点ｉで計算した場合においてのみ信頼性がある。どの点ｉにおいてもγiが「０」であるなら、このとき位相類似度はパターンの情報の存在を無視することになり、望ましい結果ではなくなる。
【００４０】
式（５）は、信号と該信号を平行移動して得られる信号との位相の合同性を高い確率で認識できる画像類似度を計算することができる。すなわち、平行移動に対し不変性を有する画像類似度を計算することができる。
【００４１】
なお、式（５）は、エッジ検出やオプティカルフローに使用されている。
【００４２】
図２は、平行移動して得られる２つの相似的な信号の位相の合同性について説明するためのものである。図２（ａ）は、信号Ｓ1（ｘ）と、信号Ｓ1（ｘ）をｄｘだけシフトした信号Ｓ1（ｘ−ｄｘ）を示す。図２（ａ）において、Ｖｉは、各点ｉにおける信号Ｓ1（ｘ）と信号Ｓ1（ｘ−ｄｘ）との間の位相差を示す。図２（ｂ）は、信号Ｓ1（ｘ）と、信号Ｓ1（ｘ）とは異なる他の信号Ｓ2（ｘ）を示す。
【００４３】
図２（ｃ）は、図２（ａ）の信号Ｓ1（ｘ）と信号Ｓ1（ｘ−ｄｘ）との間の各点ｉにおける位相差Ｖｉを複素平面上で示したものである。図２（ｄ）は、図２（ｂ）の信号Ｓ1（ｘ）と信号Ｓ2（ｘ）との間の各点ｉにおける位相差Ｖｉを複素平面上で示したものである。なお、ここでは、各信号の位相は、分析的なバンドパスフィルタ（複素ウェーブレット）を用いて推定している。
【００４４】
図２（ａ）、図２（ｃ）では、信号Ｓ1（ｘ）が平行移動しているだけであるため、位相差はほぼ一定である。但し、各点における位相差の違いは雑音に依存する。図２（ｂ）、図２（ｄ）では、各点における位相差の違いが、信号の差となる。そのため、各点における位相差の総和の絶対値と、各点における位相差の絶対値の総和との間の比は等しくならない。
【００４５】
式（５）は、フーリエ（Fourier）変換により、次式（６）に示すように、信号位置のシフトに対して不変性を有する。
【００４６】
【数１４】
2008191937.tif 000008
【００４７】
ｔがｔ＝ｇ（ｘ）である時、上記式（６）は成り立たない。これは、式（５）において空間上での総和が有効であるためである。
【００４８】
式（５）により計算される画像類似度は、平行移動に対し不変性（高い耐性）を有し、ある信号と該信号を平行移動して得られる信号に対して、高い認識率が得られる。しかし、スケール（拡大・縮小の度合い）の変化や回転などを含むアフィン変換に対しては、画像類似度が低下する。
【００４９】
そこで、次に、スケール（拡大・縮小の度合い）に対する不変性を有する画像類似度の計算手法について説明する。
【００５０】
（第１の画像類似度の計算手法）
スケーリングは、ｓを拡大／縮小のためのパラメータとすると、ｘ´→（ｘ／ｓ）と示すことができ、二次元平面上では、ｓxをｘ軸上での拡大／縮小のためのパラメータ、ｓyをｙ軸上での拡大／縮小のためのパラメータとすると、
（ｘ´、ｙ´）→（ｘ／ｓx、ｙ／ｓy）
と示すことができる。ここで、スケールの逆数をωとし、1周期のなかでは振動数を変更することでスケーリングが可能になる。信号はスケールが大きくなれば（拡大すると）振動数は減少し、スケールが小さくなれば（縮小すると）振動数は増大する。振動数に伴い位相も変換する。
【００５１】
【数１５】
2008191937.tif 000009
【００５２】
振動数が１つだけなら、位相φ0と位置ｘ＝０で、一般的な位置ｘでは、位相が
φ（ｘ）＝φ0＋ωｘ
となる。
【００５３】
また、位相関数の勾配が、定数ｄφ／ｄｘ＝ω  となり、大きさにより位相は変数ｘの関数から他の関数に写像する。
【００５４】
【数１６】
2008191937.tif 000010
【００５５】
位相の差は［０，２π］の範囲で、どの点に関しても増加する。差が一定でないため、式（５）の画像類似度には、スケール変化に対する不変性はなく、それぞれ同じ点での差に依存する。しかしながら、式（８）は二つの対称な級数を許容せず、点対称ではない。
【００５６】
【数１７】
2008191937.tif 000011
【００５７】
同様に、信号と該信号とスケールだけが異なる信号との間の位相の差から、次式（１１）に示すような級数を得ることができる。
【００５８】
【数１８】
2008191937.tif 000012
【００５９】
一方、局所的にオリジナルの点に対する位相の差が点対称ではないことがわかる。これは位相が局所的に線形関数である部分において、位相変化がスケール変数を推定できることを意味する。
【００６０】
そこで、この原理を用いて、平行移動に対する不変性を維持しながら、スケールに対する不変性を有する、画像間の比較手法、すなわち、画像類似度の計算方法について説明する。
【００６１】
最も簡単なアプローチは、１点について半分の級数を組み合わせて、式（５）に類似した計算を行うことである。
【００６２】
【数１９】
2008191937.tif 000013
【００６３】
式（１２）において、第１の画像の周波数平面上の第１及び第４の象限内の点（ｉ、ｊ）における位相情報をγ1,i、第２及び第３象限内の点（−ｉ、ｊ）における位相情報をγ1,-iと表し、第２の画像の周波数平面上の第１及び第４の象限内の点（ｉ、ｊ）における位相情報をγ2,i、第２及び第３の象限内の点（−ｉ、ｊ）における位相情報をγ2,-i、と表している。Ｎは周波数平面上の探索範囲であり、ηは、分母が「０」となることを防ぐための極小の定数値である。
【００６４】
図３は、式（１２）に示した第１の画像類似度の算出方法を説明するための図である。
【００６５】
図３では、第１の画像と第２の画像との間の第１の画像類似度（以下簡単に画像類似度と呼ぶ）を算出する場合を示している。まず、図３（ａ）（ｂ）に示すように、第１の画像（各画素の位置（ｘ、ｙ）と該画素の画素値（輝度値）との関数Ｉ1（ｘ、ｙ））を、例えば、ガボールウェーブレット変換（ガボール変換）することにより、画像平面上の輝度変化から、図３（ｅ）に示すように、周波数平面上での第１の画像の周波数成分の変化を示す関数Ｇ1（ｕ、ｖ）へ周波数変換を行う。なお、図３（ｅ）では、説明の簡単のために、関数Ｇ1（ｕ）のみを示している。また、図３（ｃ）（ｄ）に示すように、第２の画像（各画素の位置（ｘ、ｙ）と該画素の画素値（輝度値）との関数Ｉ2（ｘ、ｙ））を、例えば、ガボール変換することにより、画像平面上の輝度変化から、図３（ｅ）に示すように、周波数平面上での第２の画像の周波数成分の変化を示す関数Ｇ2（ｕ、ｖ）へ周波数変換を行う。なお、図３（ｅ）では、説明の簡単のために、関数Ｇ2（ｕ）のみを示している。
【００６６】
ここで、ｕ、ｖで表す周波数平面は複素数平面で表される。また、周波数平面上の点（ｉ、ｊ）における上記Ｇ1（ｕ、ｖ）、Ｇ2（ｕ、ｖ）を、Ｇ1i,j（ｕ、ｖ）、Ｇ2i,j（ｕ、ｖ）と表す。
【００６７】
次に、周波数平面上の第１及び第４の象限内の点（ｉ、ｊ）における上記関数Ｇ1i,j（ｕ、ｖ）、Ｇ2i,j（ｕ、ｖ）を用いて、関数Ｇ1i,j（ｕ、ｖ）とＧ2i,j（ｕ、ｖ）との位相類似度γ1i,j(γ2i,j)*を求める。また、周波数平面上で上記点（ｉ、ｊ）とは、周波数平面上の原点を通る軸（周波数軸）に関し線対称の位置にある、周波数平面上の第２及び第３象限内の点（−ｉ、ｊ）における上記関数Ｇ1-i,j（ｕ、ｖ）、Ｇ2-i,j（ｕ、ｖ）を用いて、関数Ｇ1-i,j（ｕ、ｖ）とＧ2-i,j（ｕ、ｖ）との位相類似度γ1-i,j(γ2-i,j)*を求める。これら位相類似度は、複素ベクトルとなる。
【００６８】
なお、式（１２）では、説明の簡単のため、ｖ成分を省略し、周波数平面上の第１、第４象限にある局所領域（ｉ、ｊ）における上記２つの関数の間の位相類似度をγ1,iγ*2,i、点（ｉ、ｊ）とは、周波数平面上の原点を通る軸（周波数軸）に関し線対称の位置にある周波数平面上の第２、第３象限上の点（−ｉ、ｊ）における上記２つの関数の間の位相類似度をγ1,-iγ*2,-iと表している。
式（１２）では、周波数平面上で周波数軸に対し互いに線対称の位置にある２つの点（ｉ、ｊ）（−ｉ、ｊ）の組合せ毎に、位相類似度の積（γ1,iγ*2,i）（γ1,-iγ*2,-i）を求めて、その総和を求めることにより、画像類似度を計算する。より具体的には、この総和を全エネルギーで正規化した値が式（１２）で計算される画像類似度である。
【００６９】
例えば、周波数平面上で周波数軸に対し互いに線対称の位置にある２つの点（ｉ、ｊ）（−ｉ、ｊ）の組合せ毎に、位相類似度の積（γ1,iγ*2,i）（γ1,-iγ*2,-i）の総和を求め、さらに、次式に示すように、振幅の総和により正規化を行って上記第１の画像類似度が計算される。
【００７０】
【数２０】
2008191937.tif 000014
【００７１】
式（１２）により計算される２つの画像間の画像類似度は、スケールの変化に対して不変性を得ることができる。基本的には式（５）と同様である。主な改良点は、画像の中心点に関する組み合わせであり、論点が周波数だけに集中しているが、画像はフィルタの通過帯域に含まれる周波数を重み付け平均した位相であるため、バンドパスフィルタを用いることでその他も証明できる。二次元の信号での総和は適切なｘ軸とｙ軸について分割される。２つの半分ずつの級数が、結果として生じる。
【００７２】
したがって、スケーリングした信号と対応関係を求めるための関数は、同じバンドパスフィルタの通過帯域の中での応答により制限される。たとえば、２オクターブの通過帯域があるフィルタに関しては、４から１／４まで拡大変化は理論的には検出可能である。関数が平行移動に対して不変性を有するために、範囲［ｐｉ，π）を超えて、シフトしたかを求めることはフィルタの範囲外では情報が失われてしまうため不可能であることと同様に、上記の制限は不可能である。
【００７３】
スケール変化に対しての不変性を加えた、式（１２）により計算される、２つの画像間の画像類似度は、平行移動に対しても不変性を有する。
【００７４】
図４は、第１の画像の信号Ｓ1（ｘ）と、信号Ｓ1（ｘ）を原点で固定して両端を引き延ばすようにスケール変化させた信号Ｓ1（ｘ−ｄｘ）との間の位相の合同性について説明するための図である。図４（ａ）では、信号Ｓ1（ｘ）の周波数成分ｕ、ｖの変化を示す関数Ｇ1（ｕ）、Ｇ1（ｖ）のうちの関数Ｇ1（ｕ）と、信号Ｓ1（ｘ−ｄｘ）の周波数成分ｕ、ｖの変化を示す関数Ｇ1（ｕ−ｄｕ）、Ｇ1（ｖ−ｄｖ）のうちの関数Ｇ1（ｕ−ｄｕ）を示している。
【００７５】
位相差は、周波数平面上の点ｉ１、ｉ２、ｉ３、ｉ４、…のそれぞれと、これらの点と該周波数平面上で線対称の位置にある点−ｉ１、−ｉ２、−ｉ３、−ｉ４、…のそれぞれで計算されるが、位相の合同性については、周波数平面上で線対称の位置にある２つの点の組合せ（ｉ１、−ｉ１）、（ｉ２、−ｉ２）、（ｉ３、−ｉ３）、（ｉ４、−ｉ４）、…について計算される。
【００７６】
図４（ａ）において、点ｉ１における関数Ｇ1（ｕ）と関数Ｇ1（ｕ−ｄｕ）との位相差はＶi1であり、点−ｉ１における関数Ｇ1（ｕ）と関数ＧＳ1（ｕ−ｄｕ）との位相差はＶ-i1であり、図４（ｂ）に示すように、線対称の位置にある２つの点の組合せ（ｉ１、−ｉ１）についての位相の合同性Ｖ１は、Ｖi1＋Ｖ-i1と表す。同様に、点ｉ２における２つの信号の位相差はＶi2であり、点−ｉ２における２つの信号の位相差はＶ-i2であり、図４（ｂ）に示すように、線対称の位置にある２つの点の組合せ（ｉ２、−ｉ２）についての位相の合同性Ｖ2は、Ｖi2＋Ｖ-i2とである。点ｉ３における２つの信号の位相差はＶi3であり、点−ｉ３における２つの信号の位相差はＶ-i3であり、図４（ｂ）に示すように、線対称の位置にある２つの点の組合せ（ｉ３、−ｉ３）についての位相の合同性Ｖ3は、Ｖi3＋Ｖ-i3とである。点ｉ４における２つの信号の位相差はＶi4であり、点−ｉ４における２つの信号の位相差はＶ-i4であり、図４（ｂ）に示すように、線対称の位置にある２つの点の組合せ（ｉ４、−ｉ４）についての位相の合同性Ｖ4は、Ｖi4＋Ｖ-i4とである。
【００７７】
図４（ｂ）では、図２（ｃ）（ｄ）と同様に、複素平面上に、線対称の位置にある２つの点の組合せについての上記位相差を示している。図４（ｂ）に示すように、信号Ｓ1（ｘ）と、信号Ｓ1（ｘ）をスケール変化させた信号Ｓ1（ｘ−ｄｘ）との間には、周波数平面上の線対称の位置にある２つの点の組合せについては、位相の合同性が維持されていることがわかる。
【００７８】
（第２の画像類似度の計算手法）
次に、アフィン変換に対する不変性を有する第２の画像類似度の計算手法について説明する。
【００７９】
アフィン変換に対する不変性と、スケール変化や平行移動に対する不変性との大きな違いは、アフィン変換は１次元の写像では表せないことである。平行移動やスケール変化は線形位相の形が１次元でも２次元でも同様であるが、アフィン変換は、回転移動成分を含むため１次元ではない。また、ある方向への信号の垂直成分がゆっくりと変化する場合、その方向と協調しないシフトや平行移動は、式（５）や式（１２）に示した画像類似度の計算に大きく影響する。
【００８０】
アフィン変換に対する不変性にとって、に、軸の回転は局所的な線形性の仮定を簡単に壊してしまうことを意味する。１次元以上で位相を評価できる２つの手法を示す。
【００８１】
（１）方向の定数のために、固定軸に関連する定数は、ガウシアンか余弦関数のような関数により角度的に拡張されたバンドパスフィルタの位相の応答を計算する。この手法は画像のｘ軸とｙ軸に沿って適用された２個のフィルタを持つ最も簡単なフィルタバンクを生成する。
【００８２】
（２）方向の定数のために、局所構造の方向の推定に関連するセットは、いくつかの関数により角度的に拡張されたバンドバスフィルタの応答を計算する。この場合最も適切であるのは、Structure Multivector （参考文献：M Felsberg. Low level image processing with the structure multivector. PhD thesis, Christian-Albrechts-University, Kiel, Institute for Information and Practical mathematics, Kiel University, Olshausenstrasse 40, D24098 Kiel, Germany, 2002.）であり、これは、局所的な構造の方向の二乗平均推定のために平行方向と垂直方向の２つの位相ベクトルAmj;Amn を計算する。
【００８３】
１つ目の手法は、より高速に実行でき、２つ目の手法より正確であるが、アフィン変換に対する不変性を獲得する点に関しては２つ目の手法と差はほとんどない。Structure Multivector は局所的な方向に関する構造を分離するため、局所的な回転の優位性が、画素間の対応を取り除く回転と小さな領域に対して、基点で計算された２つの位相ベクトルでの効果はなくなる。その結果、不変性を目的とする各手法間で選択することはほとんどない。しかしながら、Structure Multivector は、局所的な線形位相を増加すべき直交した方向への位相を分離するには有利である。
【００８４】
一般的に、点（ｘ、ｙ）のアファイン変換において、ｘ軸方向のスケール変数ｓx、ｙ軸方向のスケール変数ｓy、ｘ軸方向及びｙ軸方向のスケール変数ｓxyとすると、以下の式が導かれる。
【００８５】
【数２１】
2008191937.tif 000015
【００８６】
ここで、傾斜項ｙｓxy cosθ−ｙｓxy. sinθ は、無視される。
【００８７】
スケール変化に対し、局所的に線形にある場合には、点（ｘ、ｙ）における位相と、点（−ｘ、−ｙ）における位相との差は不変となる。
【００８８】
すなわち、位相がδφ（ｉ、ｊ＋δｊ）＝δφ（−ｉ、−ｊ−δｊ）の形で、局所的になめらかであるなら、点（ｉ、ｊ）と点（−ｉ、−ｊ）の位相の差は、
【００８９】
【数２２】
2008191937.tif 000016
【００９０】
という特性を持つ。これらの点の組み合わせは、次式（１６）を導く。
【００９１】
【数２３】
2008191937.tif 000017
【００９２】
なお、式（１６）において、Ｎは周波数平面上の探索範囲であり、ηは、分母が「０」となることを防ぐための極小の定数値である。
【００９３】
図５は、式（１６）に示した第２の画像類似度の算出方法を説明するための図である。
【００９４】
図５では、第１の画像と第２の画像との間の第２の画像類似度（以下簡単に画像類似度と呼ぶ）を算出する場合を示している。まず、図５（ａ）（ｂ）に示すように、第１の画像（各画素の位置（ｘ、ｙ）と該画素の画素値との関数Ｉ1（ｘ、ｙ））を、例えば、ガボールウェーブレット変換（ガボール変換）することにより、局所的な周波数成分の変化を示す周波数平面上の関数Ｇ1（ｕ、ｖ）を求める。また、図５（ｃ）（ｄ）に示すように、第２の画像（各画素の位置（ｘ、ｙ）と該画素の画素値との関数Ｉ2（ｘ、ｙ））を、例えば、ガボール変換することにより、局所的な周波数成分の変化を示す関数Ｇ2（ｕ、ｖ）を求める。
【００９５】
ここで、ｕ、ｖで表される周波数平面は複素数平面となる。また、周波数平面上の点（ｉ、ｊ）における上記Ｇ1（ｕ、ｖ）、Ｇ2（ｕ、ｖ）を、Ｇ1i,j（ｕ、ｖ）、Ｇ2i,j（ｕ、ｖ）と表す。
【００９６】
次に、周波数平面上の第１象限にある点（ｉ、ｊ）における上記関数Ｇ1i,j（ｕ、ｖ）、Ｇ2i,j（ｕ、ｖ）を用いて、関数Ｇ1i,j（ｕ、ｖ）とＧ2i,j（ｕ、ｖ）との位相類似度γ1i,j(γ2i,j)*を求める。また、周波数平面上で上記点（ｉ、ｊ）とは、周波数平面上の原点に関し点対称の位置にある周波数平面上の第３象限にある点（−ｉ、−ｊ）における上記関数Ｇ1-i,-j（ｕ、ｖ）、Ｇ2-i,-j（ｕ、ｖ）を用いて、関数Ｇ1-i,-j（ｕ、ｖ）とＧ2-i,-j（ｕ、ｖ）との間の位相類似度γ1-i,-j(γ2-i,-j)*を求める。
【００９７】
さらに、周波数平面上の第４象限にある点（ｉ、−ｊ）における上記関数Ｇ1i,-j（ｕ、ｖ）、Ｇ2i,-j（ｕ、ｖ）を用いて、関数Ｇ1i,-j（ｕ、ｖ）とＧ2i,-j（ｕ、ｖ）との位相類似度γ1i,-j(γ2i,-j)*を求める。また、周波数平面上で上記点（ｉ、−ｊ）とは、周波数平面上の原点に関し点対称の位置にある周波数平面上の第２象限にある点（−ｉ、ｊ）における上記関数Ｇ1-i,j（ｕ、ｖ）、Ｇ2-i,j（ｕ、ｖ）を用いて、関数Ｇ1-i,j（ｕ、ｖ）とＧ2-i,j（ｕ、ｖ）との位相類似度γ1-i,j(γ2-i,j)*を求める。
【００９８】
これら位相類似度は、複素ベクトルで表すことができ、ここでは、周波数平面上の原点は、第１及び第２の画像の中心点に対応しているが、この場合に限らず、第１及び第２の画像中の任意の点を周波数平面上の原点としてもよい。
【００９９】
式（１６）では、周波数平面の原点に関し点対称の位置にある第１象限内の点（ｉ、ｊ）及び第３象限内の点（−ｉ、−ｊ）との組合せ毎に、位相類似度の積（γ1i,j(γ2i,j)*）（γ1-i,-j(γ2-i,-j)*）を求めて、その総和（第１の総和）を求めるとともに、周波数平面の原点に関し点対称の位置にある第４象限内の点（ｉ、−ｊ）及び第２象限内の点（−ｉ、ｊ）との組合せ毎に、位相類似度の積（γ1i,-j(γ2i,-j)*）（γ1-i,j(γ2-i,j)*）を求めて、その総和（第２の総和）を求め、第１及び第２の総和を加算することにより画像類似度を計算する。より具体的には、第１の総和と第２の総和をそれぞれ正規化して加算した値が式（１６）で計算される画像類似度である。
【０１００】
例えば、次式に示すように、振幅の総和により正規化を行って、上記第２の画像類似度が計算される。
【０１０１】
【数２４】
2008191937.tif 000018
【０１０２】
式（５）と式（１２）と式（１６）は、全て線形位相の仮定が成立する場合に限定される。画像サイズが大きくなると、画像上で位相が滑らかである確率が低くなる。アフィン変換に対して仮定の正当性は、スケール不変性のための距離２ｉか２ｊに対して、距離２sqrti２＋ｊ２で、点（ｉ、ｊ）と点（−ｉ、−ｊ）をつなぐとするなら、スケール不変性に対する仮定は成立する範囲よりもゆるくなる。この距離は、データが線形位相などの局所的な仮定が成立するかに依存するため、実際に値を推定することは困難である。
【０１０３】
（パターンマッチング装置の構成）
画像信号の周波数変換を、例えばガボールフィルタなどによるフィルタリングにより実現する場合、全てのフィルタリングの計算のために１０ピクセルの波長と、主軸にそって２つの方向を持つ単一の大きさのガボールウェーブレットを用いて実現する。
【０１０４】
式（１２）と式（１６）に示した画像類似度では、周波数平面上の原点を画像の中心に設定してもよいし、画像中の任意の点に設定してもよい。
【０１０５】
図６は、本実施形態に係るパターンマッチング装置１００の構成例を示したものである。
【０１０６】
パターンマッチング装置１００は、画像入力部１０１、変換部１０２、位相類似度計算部１０３と、画像類似度計算部１０４を含む。
【０１０７】
以下、図６のパターンマッチング装置の処理動作について、図７に示すフローチャートを参照して説明する。図７は、上述した第１の画像類似度の計算手法を適用したパターンマッチング装置の処理動作を説明するためのフローチャートである。
【０１０８】
パターンマッチング装置１００の画像入力部１０１には、比較対称の２つの画像、すなわち、第１の画像及び第２の画像が入力される（ステップＳ１）。第１の画像及び第２の画像は、それぞれ各画素の位置（ｘ、ｙ）と該画素の画素値との関数として表されるもので、ここでは、第１の画像をＩ1（ｘ、ｙ）、第２の画像をＩ2（ｘ、ｙ）と表す。
【０１０９】
次に、変換部１０２では、入力された２つの画像（画像信号Ｉ1（ｘ、ｙ）、Ｉ2（ｘ、ｙ））のそれぞれを、ガウス関数を用いたガボール変換等のウェーブレット変換を施し、周波数成分の変化を示す、周波数平面上の関数に変換する（ステップＳ２）。なお、ここでは、ウェーブレット変換のみに限らず、フーリエ変換を用いて、周波数平面上の関数に変換してもよい。画像信号Ｉ1（ｘ、ｙ）から得られた、周波数平面上の点（ｉ、ｊ）における周波数平面上の関数をＧ1i,j（ｕ、ｖ）、画像信号Ｉ2（ｘ、ｙ）から得られた、周波数平面上の点（ｉ、ｊ）における周波数平面上の関数をＧ2i,j（ｕ、ｖ）とする。
【０１１０】
次に、位相類似度計算部１０３は、周波数平面上の第１及び第４象限内の点（ｉ，ｊ）における関数Ｇ1i,j（ｕ、ｖ）と関数Ｇ2i,j（ｕ、ｖ）とから、関数Ｇ1i,j（ｕ、ｖ）と関数Ｇ2i,j（ｕ、ｖ）との位相類似度γ1i,j(γ2i,j)*を計算する（ステップＳ３ａ）。
【０１１１】
さらに、位相類似度計算部１０３は、上記点（ｉ，ｊ）と、周波数平面上で原点を通る軸に関し線対称の位置にある、周波数平面上の第２及び第３象限内の点（−ｉ、ｊ）における関数Ｇ1-i,j（ｕ、ｖ）と関数Ｇ2-i,j（ｕ、ｖ）とから、関数Ｇ1-i,j（ｕ、ｖ）と関数Ｇ2-i,j（ｕ、ｖ）との位相類似度γ1-i,j(γ2-i,j)*を計算する（ステップＳ４ａ）。
【０１１２】
すなわち、ステップＳ３ａ、ステップＳ３ａでは、周波数平面上の各象限（第１乃至第４象限）内の各点について、Ｇ1（ｕ、ｖ）と関数Ｇ2（ｕ、ｖ）との位相類似度を計算する。
【０１１３】
最後に、画像類似度計算部１０４は、式（１２）を用いて、周波数平面上で互いに線対称の位置にある２つの点（ｉ、ｊ）（−ｉ、ｊ）の組合せ毎の位相類似度の積（γ1i,j(γ2i,j)*）（γ1-i,j(γ2-i,j)*）と、その総和を求める。この総和を正規化することにより、第１の画像と第２の画像との間の画像類似度を計算する（ステップＳ５ａ）。
【０１１４】
次に、図６のパターンマッチング装置の他の処理動作について、図８に示すフローチャートを参照して説明する。図８は、上述した第２の画像類似度の計算手法を適用したパターンマッチング装置の処理動作を説明するためのフローチャートである。なお、図８において、図７と同一部分には同一符号を付し、異なる部分についてのみ説明する。すなわち、図７のステップＳ３ａ、ステップＳ４ａ及びステップＳ５ａが、図８では、ステップＳ３ｂ、ステップＳ４ｂ及びステップＳ５ｂに置き換わっている。
【０１１５】
図８のステップＳ３ｂでは、位相類似度計算部１０３は、周波数平面上の第１象限内の点（ｉ，ｊ）における関数Ｇ1i,j（ｕ、ｖ）と関数Ｇ2i,j（ｕ、ｖ）とから、関数Ｇ1i,j（ｕ、ｖ）と関数Ｇ2i,j（ｕ、ｖ）との位相類似度γ1i,j(γ2i,j)*を計算するとともに、第１象限内の点（ｉ，ｊ）と、周波数平面の原点に関し点対称の位置にある、周波数平面上の第３象限内の点（−ｉ、−ｊ）における関数Ｇ1-i,-j（ｕ、ｖ）と関数Ｇ2-i,-j（ｕ、ｖ）とから、関数Ｇ1-i,-j（ｕ、ｖ）と関数Ｇ2-i,-j（ｕ、ｖ）との位相類似度γ1-i,-j(γ2-i,-j)*を計算する。
【０１１６】
ステップＳ４ｂでは、位相類似度計算部１０３は、周波数平面上の第４象限内の点（ｉ，−ｊ）における関数Ｇ1i,-j（ｕ、ｖ）と関数Ｇ2i,-j（ｕ、ｖ）とから、関数Ｇ1i,-j（ｕ、ｖ）と関数Ｇ2i,-j（ｕ、ｖ）との位相類似度γ1i,j(γ2i,j)*を計算するとともに、点（ｉ，−ｊ）と、周波数平面の原点に関し点対称の位置にある、周波数平面上の第２象限内の点（−ｉ、ｊ）における関数Ｇ1-i,j（ｕ、ｖ）と関数Ｇ2-i,j（ｕ、ｖ）とから、関数Ｇ1-i,j（ｕ、ｖ）と関数Ｇ2-i,j（ｕ、ｖ）との位相類似度γ1-i,j(γ2-i,j)*を計算する。
【０１１７】
すなわち、ステップＳ３ｂ及びステップＳ４ｂでは、周波数平面上の各象限（第１乃至第４象限）内の各点について、Ｇ1（ｕ、ｖ）と関数Ｇ2（ｕ、ｖ）との位相類似度を計算する。
【０１１８】
そして、ステップＳ５ｂでは、画像類似度計算部１０４は、式（１６）を用いて、周波数平面の原点に関し、互いに点対称の位置にある２つの点（ｉ、ｊ）（−ｉ、−ｊ）の組合せ毎の位相類似度の積（γ1i,j(γ2i,j)*）（γ1-i,-j(γ2-i,-j)*）と、その総和を求め、この総和を正規化した値を求めるとともに、周波数平面上で互いに点対称の位置にある２つの点（ｉ、−ｊ）（−ｉ、ｊ）の組合せ毎の位相類似度の積（γ1i,-j(γ2i,-j)*）（γ1-i,j(γ2-i,j)*）と、その総和を求め、この総和を正規化した値を求める。そして、両者の和を求めることにより、第１の画像と第２の画像との間の画像類似度を計算する。
【０１１９】
（サンプル画像ヘの第１／第２の画像類似度の適用例）
図９（ａ）に示すような、与えられたサンプル画像から、ランダムに中心点を選択した画像を切り出す。これをパッチとする。式（１２）や式（１６）に示した画像類似度を評価するために、このパッチを中心点から引き延ばしたり、縮めたりして、スケールを変化させた、拡大率の異なる複数の（例えば４つの）パッチ画像（図９（ｂ）〜（ｅ））を生成する。
【０１２０】
図９（ｂ）〜（ｅ）では、サンプル画像とサンプル画像から双線型の内挿法により切り出したサイズの異なる４つのパッチ画像を示す。図９（ｂ）は、サンプル画像から切り出されたパッチを０．５倍したパッチ画像、図９（ｃ）は１，０倍したパッチ画像、図９（ｄ）は１，５倍したパッチ画像、図９（ｅ）は２，０倍したパッチ画像である。なお、図９（ｃ）のパッチ画像のサイズは、６１×６１ピクセルである。
【０１２１】
図１０は、サンプル画像と、上記４種類のパッチ画像を拡大率の異なる複数のパッチ画像との間の画像類似度を式（１２）を用いて計算した場合（第１の画像類似度）と、式（１６）を用いて計算した場合（第２の画像類似度）と、式（５）に示したような従来の画像類似度とについての比較結果を示したものである。
【０１２２】
図１０が示すように、第１及び第２の画像類似度は、拡大率０．５から１．３の範囲でスケール変化させた場合のパッチ画像に対して非常に安定していて、０．９５以上を保っている。
【０１２３】
図６のパターンマッチング装置の各構成部は、コンピュータに実行させることのできるプログラムとして実現することができ、このプログラムは、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、半導体メモリなどの記録媒体に格納して頒布することもできる。
【０１２４】
以上説明したように、上記実施形態によれば、（ａ）入力された第１の画像から、周波数平面上での第１の画像の周波数成分の変化を示す第１の関数を求めるとともに、入力された第２の画像から、該周波数平面上での第２の画像の周波数成分の変化を示す第２の関数を求め、（ｂ）該周波数平面上の各点について、該第１の関数の位相と該第２の関数の位相との類似度を示す位相類似度を計算し、（ｃ）該周波数平面上での周波数軸に対して互いに線対称の位置にある２つの点の組合せ毎に該位相類似度の積を計算するとともに、該周波数平面上の各組合せについて求めた該積の総和を計算することにより、該第１の画像と該第２の画像との間の画像類似度を計算することより、平行移動、スケール変化（拡大／縮小）に対する耐性の高い画像類似度が得られ、互いに相似するパターンに対し、高い認識率が得られる。
【０１２５】
（ａ）入力された第１の画像から、周波数平面上での第１の画像の周波数成分の変化を示す第１の関数を求めるとともに、入力された第２の画像から、該周波数平面上での第２の画像の周波数成分の変化を示す第２の関数を求め、（ｂ）該周波数平面上の各点について、該第１の関数の位相と該第２の関数の位相との類似度を示す位相類似度を計算し、（ｃ´）該周波数平面の原点に関し互いに点対称の位置にある２つの点の組合せ毎に該位相類似度の積を計算するとともに、該周波数平面上の各組合せについて求めた該積の総和を計算することにより、該第１の画像と該第２の画像との間の画像類似度を計算することにより、平行移動、スケール変化（拡大／縮小）、回転に対する耐性の高い画像類似度が得られ、互いに相似するパターンに対し、高い認識率が得られる。
【０１２６】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１２７】
【図１】平行移動に対し耐性を有する画像類似度の計算方法を説明するための図。
【図２】平行移動して得られる２つの相似的な信号の位相の合同性について説明するための図。
【図３】平行移動及びスケール変換に対し耐性を有する第１の画像類似度の計算方法を説明するための図。
【図４】スケールを変化させた信号間の位相の合同性について説明するための図。
【図５】アフィンへ間に対し耐性を有する第２の画像類似度の計算方法を説明するための図。
【図６】パターンマッチング装置の構成例を示した図。
【図７】図６のパターンマッチング装置の処理動作を説明するためのフローチャート。
【図８】図６のパターンマッチング装置の他の処理動作を説明するためのフローチャート。
【図９】図９（ａ）は、与えられたサンプル画像を示し、図９（ｂ）〜図９（ｅ）は、該サンプル画像から生成した拡大率の異なる４つのパッチ画像を示した図。
【図１０】サンプル画像と、異なる複数のパッチ画像との間の第１の画像類似度と、第２の画像類似度と、従来の画像類似度とについての比較結果を示した図。
【符号の説明】
【０１２８】
１００…パターンマッチング装置、１０１…画像入力部、１０２…変換部、１０３…位相類似度計算部、１０４…画像類似度計算部
【図１】
2008191937.tif 000027
【図２】
2008191937.tif 000028
【図３】
2008191937.tif 000029
【図４】
2008191937.tif 000030
【図５】
2008191937.tif 000031
【図６】
2008191937.tif 000032
【図７】
2008191937.tif 000033
【図８】
2008191937.tif 000034
【図９】
2008191937.tif 000035
【図１０】
2008191937.tif 000036