(57)【要約】【課題】被写体の拡大／縮小、回転及び平行移動があっても、テンプレート画像と対象画像との間での同定を可能とする。また、被写体の拡大率又は回転角度の推定を可能とする。【解決手段】テンプレート画像及び対象画像のそれぞれについて、LACRドメインを生成し、これらのLACRドメインについて位相限定相関を行う。これにより、両画像の間（すなわち被写体の間）における拡大率及び回転角度を推定できる。ここで両画像についてのLACRドメインの生成は、(a)画像へのRadon変換によるRadonドメインの生成；(b)Radonドメインにおける動径方向での自己相関の算出；(c)Radonドメインの自己相関における動径軸の対数化；(d)自己相関の動径方向における差分の算出、により行われる。LACRドメインの自己相関により生成したLACR自己相関ドメインどうしを比較することにより、画像どうしの同定を行うことができる。【選択図】図１８
2008250610.tif 000002
【特許請求の範囲】
【請求項１】
以下のステップを有することを特徴とするパターンマッチング方法：
（１）第１画像を用いて、前記第１画像についての第１のLACRドメインを生成するステップ；
（２）第２画像を用いて、前記第２画像についての第２のLACRドメインを生成するステップ；
（３）前記第１のLACRドメインと、前記第２のLACRドメインとの間の位相限定相関により、前記第１画像と前記第２画像との間における、拡大率又は回転角度を推定するステップ；
ここで、前記第１画像及び前記第２画像についての、前記各LACRドメインの生成は、それぞれ、以下のステップを含む方法により行われる：
（ａ）前記第１又は第２画像へのRadon変換を行うことでRadonドメインを生成するステップ；
（ｂ）その後、前記Radonドメインにおける動径方向での自己相関を算出するステップ；
（ｃ）その後、前記Radonドメインの自己相関における動径軸を対数化するステップ；
（ｄ）その後、前記自己相関の動径方向における差分を算出することによってLACRドメインを生成するステップ。
【請求項２】
以下のステップを有することを特徴とするパターンマッチング方法：
（１）第１画像を用いて、前記第１画像についての第１のLACR自己相関ドメインを生成するステップ；
（２）第２画像を用いて、前記第２画像についての第２のLACR自己相関ドメインを生成するステップ；
（３）前記第１のLACR自己相関ドメインと、前記第２のLACR自己相関ドメインとを比較することにより、第１画像と第２画像との同定を行うステップ；
ここで、前記第１画像及び前記第２画像についての、前記各LACR自己相関ドメインは、請求項１記載の方法で生成された前記LACRドメインの自己相関によりそれぞれ生成される。
【請求項３】
請求項２に記載の方法により同定された前記第１画像と前記第２画像との間における拡大率又は回転角度を推定するパターンマッチング方法であって、
前記第１画像についての第１のLACRドメインと、前記第２画像についての第２のLACRドメインとの位相限定相関又は平行移動量により、前記拡大率又は前記回転角度を推定する、パターンマッチング方法。
【請求項４】
請求項３に記載の方法により拡大率又は回転角度が推定された前記第１画像と前記第２画像との間におけるパターンマッチング方法であって、
前記推定された拡大率又は回転角度に基づいて、前記第１画像及び前記第２画像の一方を補正することによって、両者間での拡大率及び回転角度を実質的に一致させ、
ついで、前記変換された第１画像と第２画像との間で位相限定相関を行うことにより、第１画像及び第２画像のうちの一方に対する他方の平行移動量を推定する、パターンマッチング方法。
【請求項５】
被写体の同定部を備えており、
前記被写体の同定部は、第１画像についての第１のLACR自己相関ドメインと、第２画像についての第２のLACR自己相関ドメインとの比較により同定を行う構成となっており；
前記第１画像及び前記第２画像についての前記各LACR自己相関ドメインは、それぞれ、以下のステップにより生成される、パターンマッチング装置：
（ａ）前記第１又は第２画像へのRadon変換を行うことでRadonドメインを生成するステップ；
（ｂ）その後、前記Radonドメインにおける動径方向での自己相関を算出するステップ；
（ｃ）その後、前記Radonドメインの自己相関における動径軸を対数化するステップ；
（ｄ）その後、前記自己相関の動径方向における差分を算出することによってLACRドメインを生成するステップ；
（ｅ）前記LACRドメインの自己相関によりLACR自己相関ドメインを生成するステップ。
【請求項６】
さらに、拡大率及び回転角度の推定部を備えており、
前記拡大率及び回転角度の推定部は、前記第１画像についての第１のLACRドメインと、前記第２画像についての第２のLACRドメインとの間の位相限定相関により、第１画像と第２画像との間における、拡大率又は回転角度を推定する構成となっており；
前記第１画像及び前記第２画像についての前記各LACRドメインは、それぞれ、前記ステップ（ｄ）により生成される、
請求項５に記載のパターンマッチング装置。
【請求項７】
さらに、拡大／縮小及び回転の処理部と、平行移動量の推定部とを備えており、
前記拡大／縮小及び回転の処理部は、前記拡大率及び回転角度の推定部により推定された拡大率又は回転角度に基づいて前記第１画像及び前記第２画像の一方を補正することによって、両者間での拡大率及び回転角度を実質的に一致させる構成となっており；
前記平行移動量の推定部は、前記補正された第１画像と第２画像との間で位相限定相関を行うことにより、第１画像及び第２画像のうちの一方に対する他方の平行移動量を推定する構成となっている、
請求項６に記載のパターンマッチング装置。
【請求項８】
請求項１又は２に記載の各ステップをコンピュータに実行させるためのコンピュータプログラム。
【請求項９】
以下のステップにより生成されたLACRドメインのデータ：
（ａ）原画像へのRadon変換を行うことでRadonドメインを生成するステップ；
（ｂ）その後、前記Radonドメインにおける動径方向での自己相関を算出するステップ；
（ｃ）その後、前記Radonドメインの自己相関における動径軸を対数化するステップ；
（ｄ）その後、前記自己相関の動径方向における差分を算出することによってLACRドメインを生成するステップ。
【請求項１０】
以下のステップにより生成されたLACR自己相関ドメインのデータ：
（ａ）原画像へのRadon変換を行うことでRadonドメインを生成するステップ；
（ｂ）その後、前記Radonドメインにおける動径方向での自己相関を算出するステップ；
（ｃ）その後、前記Radonドメインの自己相関における動径軸を対数化するステップ；
（ｄ）その後、前記自己相関の動径方向における差分を算出することによってLACRドメインを生成するステップ；
（ｅ）前記LACRドメインの自己相関によりLACR自己相関ドメインを生成するステップ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターンマッチング方法及び装置に関するものである。より詳しくは、一つ又は複数の被写体を撮影した画像の間で、画像どうしの、すなわち被写体どうしのパターンマッチングを行う方法及び装置に関するものである。
【背景技術】
【０００２】
テンプレート画像を用いたパターンマッチングは、物体（すなわち被写体）の認識における最も重要な技術である。これまでに、Hough 変換法、一般化Hough変換法、位相限定相関法、Log-Polar 変換を用いた方法、Radon・Fourier変換法、Radon変換と一次元位相限定相関とを用いた方法が提案され、種々のアプリケーションに応用されている。
【０００３】
一般に、パターンマッチングには、外部環境の変動並びに被写体の形状及び位置や姿勢に依存しない特性が要求される。特に、被写体の拡大縮小、平行移動、回転に影響されにくいパターンマッチングが求められている。
【０００４】
被写体の移動が平行移動のみに限定されている場合には、画像の畳み込みによる相互相関によってパターンマッチングすることが可能である。また、各画像の自己相関は平行移動に不変な特徴量となるので、自己相関を比較することによるマッチングも可能である。
【０００５】
Kuglinらは、画像をFourier変換し、変換ドメインの位相成分のみを用いてマッチングする方法(位相限定相関)を提案している[非特許文献1]。この方法は、明るさの変化や雑音に強い特性があり、指紋認証などに広く応用されている[非特許文献2]。しかしながら、位相限定相関を用いるこの方法では、被写体が拡大縮小、回転するとマッチングができないという問題がある。
【０００６】
被写体が拡大／縮小、回転する場合については、画像をLog-Polar変換した後に相互相関や自己相関を算出してパターンマッチングすることが可能である[非特許文献3]。
【０００７】
Log-Polar変換の極座標表現と対数化とによって、被写体の拡大縮小と回転とがLog-Polarドメインの平行移動に置換される。したがって、Log-Polarドメインの畳み込みによる相互相関によって、拡大率や回転角度の検出が可能となる。また、Log-Polarドメインの畳み込みによる自己相関によって、拡大／縮小や回転に依存しない特徴量を抽出することができる。
【０００８】
しかしながら、被写体の平行移動については、Log-Polarドメインが複雑に変形するために処理が困難である。一方、SrinivasaらやAverbuchらは、画像をFourier変換した後、パワースペクトルを極座標表現する方法を提案している[非特許文献4]、[非特許文献5]。また、Liuらは、動径方向の対数化を提案している(Log-Polar Fourier変換)[非特許文献6]。パワースペクトルを用いることによって、被写体の平行移動に不変なドメインが得られる。
【０００９】
大西、平井らは、Radon変換に着目し、被写体が平行移動するとRadonドメインが動径方向に変動することを指摘した。この方法では、Radonドメインを動径方向にFourier 変換してパワースペクトルを算出する。このパワースペクトルによるドメインは、被写体の平行移動に不変である(Radon・Fourier変換法) [非特許文献7]、 [非特許文献8]。
【００１０】
Radon 変換の極座標表現により、被写体の回転はドメインの偏角方向の平行移動に置換される。また、被写体の拡大縮小はドメインを動径方向に拡大縮小することで対応できる。さらに、坪井らは、動径方向に対して一次元位相限定相関を適用する方法を提案している[非特許文献9]。この方法では、被写体の回転に影響されずにパターンマッチングが可能であるが、被写体が拡大縮小するとマッチングができないという問題がある。
【非特許文献１】[1] C. D. Kuglin and D.C. Hines, "The phase correlation image alignment method," Proc. Int. Conf. on Cybernetics and Society, pp.163-165, 1975.
【非特許文献２】[2] K. Ito, H. Nakajima, K. Kobayashi, T. Aoki, and T. Higuchi, "A fingerprint matching algorithm using phase-only correlation," IEICE Trans. Fundamentals, Vol.E87-A, No.3, Mar. 2004.
【非特許文献３】[3] 栗田多喜夫，堀田一弘，三島健稔，"Log-Polar 画像の高次局所自己相関特徴を用いた大きさに不変な顔画像の認識，" 信学論，D-II，Vol. J80-D-II，8，pp.2209-2217，Aug. 1997．
【非特許文献４】[4] B. Srinivasa Reddy and B. N. Chatterji, "An FFT-based technique for translation, rotation, and scale-invariant image registration," IEEE Trans. on Image Processing, vol.5, No.8, Aug. 1996.
【非特許文献５】[5] A. Averbuch, R. R. Coifman, D. L. Donoho, M. Elad, and M. Israeli, "Fast and accurate polar Fourier transform," Appl. Comput. Harmon. Anal. 21, pp.145-167, 2006.
【非特許文献６】[6] H. Liu, B. Guo, and Z. Feng, "Pseudo-Log-Polar Fourier transform for image registration," IEEE Signal Processing Letters, Vol.13, No.1, Jun. 2006.
【非特許文献７】[7] H. Onishi and H. Suzuki, "Detection of Rotation and Parallel Translation Using Hough and Fourier Transforms," Proc. 1996 Int. Conf. on Image Processing, Vol.3, pp.827-830, 1996.
【非特許文献８】[8] 平井慎一，"知能ロボットとシステムLSI，" 計測自動制御学会論文集，40，12，Dec. 2001．
【非特許文献９】[9] 坪井辰彦，平井慎一，"ラドン変換と一次元位相限定相関を用いた複数物体の平面運動検出，" 信学論，D-II，Vol. J87-D-II， 10，pp.1963-1972，Oct. 2004．
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、前記した状況に鑑みてなされたものである。本発明の第１の目的は、被写体の拡大／縮小、回転及び平行移動があっても、テンプレート画像と対象画像との間での同定が可能なパターンマッチングの手段を提供することである。
【００１２】
また、本発明の第２の目的は、被写体の拡大率又は回転角度の推定が可能なパターンマッチングの手段を提供することである。
【００１３】
さらに、本発明の第３の目的は、被写体の平行移動量の推定が可能なパターンマッチングの手段を提供することである。
【課題を解決するための手段】
【００１４】
項目１に係るパターンマッチング方法は、以下のステップを有する：
（１）第１画像を用いて、前記第１画像についての第１のLACRドメインを生成するステップ；
（２）第２画像を用いて、前記第２画像についての第２のLACRドメインを生成するステップ；
（３）前記第１のLACRドメインと、前記第２のLACRドメインとの間の位相限定相関により、前記第１画像と前記第２画像との間における、拡大率又は回転角度を推定するステップ。
【００１５】
ここで、前記第１画像及び前記第２画像についての、前記各LACRドメインの生成は、それぞれ、以下のステップを含む方法により行われる：
（ａ）前記第１又は第２画像へのRadon変換を行うことでRadonドメインを生成するステップ；
（ｂ）その後、前記Radonドメインにおける動径方向での自己相関を算出するステップ；
（ｃ）その後、前記Radonドメインの自己相関における動径軸を対数化するステップ；
（ｄ）その後、前記自己相関の動径方向における差分を算出することによってLACRドメインを生成するステップ。
【００１６】
項目２に係るパターンマッチング方法は、以下のステップを有する：
（１）第１画像を用いて、前記第１画像についての第１のLACR自己相関ドメインを生成するステップ；
（２）第２画像を用いて、前記第２画像についての第２のLACR自己相関ドメインを生成するステップ；
（３）前記第１のLACR自己相関ドメインと、前記第２のLACR自己相関ドメインとを比較することにより、第１画像と第２画像との同定を行うステップ；
ここで、前記第１画像及び前記第２画像についての、前記各LACR自己相関ドメインは、項目１の方法で生成された前記LACRドメインの自己相関によりそれぞれ生成される。
【００１７】
項目３に係るパターンマッチング方法は、項目２の方法により同定された前記第１画像と前記第２画像との間における拡大率又は回転角度を推定するものである。この方法では、前記第１画像についての第１のLACRドメインと、前記第２画像についての第２のLACRドメインとの位相限定相関又は平行移動量により、前記拡大率又は前記回転角度を推定する。
【００１８】
項目４に係るパターンマッチング方法は、項目３の方法により拡大率又は回転角度が推定された前記第１画像と前記第２画像との間におけるパターンマッチングを行うものである。この方法においては、まず、前記推定された拡大率又は回転角度に基づいて、前記第１画像及び前記第２画像の一方を補正することによって、両者間での拡大率及び回転角度を実質的に一致させる。ついで、前記変換された第１画像と第２画像との間で位相限定相関を行うことにより、第１画像及び第２画像のうちの一方に対する他方の平行移動量を推定する。
【００１９】
項目５に係るパターンマッチング装置は、被写体の同定部を備えている。前記被写体の同定部は、第１画像についての第１のLACR自己相関ドメインと、第２画像についての第２のLACR自己相関ドメインとの比較により同定を行う構成となっている。前記第１画像及び前記第２画像についての前記各LACR自己相関ドメインは、それぞれ、以下のステップにより生成される：
（ａ）前記第１又は第２画像へのRadon変換を行うことでRadonドメインを生成するステップ；
（ｂ）その後、前記Radonドメインにおける動径方向での自己相関を算出するステップ；
（ｃ）その後、前記Radonドメインの自己相関における動径軸を対数化するステップ；
（ｄ）その後、前記自己相関の動径方向における差分を算出することによってLACRドメインを生成するステップ；
（ｅ）前記LACRドメインの自己相関によりLACR自己相関ドメインを生成するステップ。
【００２０】
項目６に係るパターンマッチング装置は、項目５のものにおいて、さらに、拡大率及び回転角度の推定部を備えている。前記拡大率及び回転角度の推定部は、前記第１画像についての第１のLACRドメインと、前記第２画像についての第２のLACRドメインとの間の位相限定相関により、第１画像と第２画像との間における、拡大率又は回転角度を推定する構成となっている。前記第１画像及び前記第２画像についての前記各LACRドメインは、それぞれ、前記ステップ（ｄ）により生成される。
【００２１】
項目７に係るパターンマッチング装置は、項目６のものにおいて、さらに、拡大／縮小及び回転の処理部と、平行移動量の推定部とを備えている。前記拡大／縮小及び回転の処理部は、前記拡大率及び回転角度の推定部により推定された拡大率又は回転角度に基づいて前記第１画像及び前記第２画像の一方を補正することによって、両者間での拡大率及び回転角度を実質的に一致させる構成となっている。前記平行移動量の推定部は、前記補正された第１画像と第２画像との間で位相限定相関を行うことにより、第１画像及び第２画像のうちの一方に対する他方の平行移動量を推定する構成となっている。
【００２２】
項目８に係るコンピュータプログラムは、項目１又は２における各ステップをコンピュータに実行させるためのものである。このようなプログラムは、コンピュータにより読み取り可能な適宜の記録媒体に格納することができる。
【００２３】
項目９に係る、LACRドメインのデータは、以下のステップにより生成されたものである：
（ａ）原画像へのRadon変換を行うことでRadonドメインを生成するステップ；
（ｂ）その後、前記Radonドメインにおける動径方向での自己相関を算出するステップ；
（ｃ）その後、前記Radonドメインの自己相関における動径軸を対数化するステップ；
（ｄ）その後、前記自己相関の動径方向における差分を算出することによってLACRドメインを生成するステップ。
【００２４】
このLACRドメインのデータを用いることにより、被写体の拡大率又は回転角度の推定が可能となる。ここで、原画像とは、マッチングのために取得された画像である。例えば、第１画像（例えばテンプレート画像）と第２画像（例えば対象画像）とのマッチングを行う場合、これら第１画像及び第２画像のそれぞれが原画像に対応する。したがって、LACRドメインのデータは、マッチングの対象となるそれぞれの画像に対応して生成される。
【００２５】
項目１０に係る、LACR自己相関ドメインのデータは、以下のステップにより生成されたものである：
（ａ）原画像へのRadon変換を行うことでRadonドメインを生成するステップ；
（ｂ）その後、前記Radonドメインにおける動径方向での自己相関を算出するステップ；
（ｃ）その後、前記Radonドメインの自己相関における動径軸を対数化するステップ；
（ｄ）その後、前記自己相関の動径方向における差分を算出することによってLACRドメインを生成するステップ；
（ｅ）前記LACRドメインの自己相関によりLACR自己相関ドメインを生成するステップ。
【００２６】
このLACR自己相関ドメインのデータを用いることにより、第１画像（例えばテンプレート画像）と第２画像（例えば対象画像）との間での同定が可能になる。ここで、原画像の意味は、LACRドメインのデータを生成する場合と同様である。
【発明の効果】
【００２７】
前記した項目２に記載の本発明によれば、LACR自己相関ドメインを用いて比較を行うことにより、被写体の拡大／縮小、回転及び平行移動があっても、第１画像（例えばテンプレート画像）と第２画像（例えば対象画像）との間での同定が可能なパターンマッチングの手段を提供することが可能になる。
【００２８】
また、前記した項目１に記載の本発明によれば、LACRドメインを用いることにより、被写体の拡大率又は回転角度の推定が可能なパターンマッチングの手段を提供することが可能になる。
【００２９】
さらに、前記した項目４に記載の本発明によれば、被写体の平行移動量の推定が可能なパターンマッチングの手段を提供することができる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の一実施形態を、添付図面を参照しながら説明する。
【００３１】
（本実施形態の概略）
本実施形態の概略をまず説明する。ここでは、画像（テンプレート画像及び対象画像のそれぞれ）をRadon変換した後、動径方向の自己相関を算出し、さらに動径を対数化して、動径方向における差分を算出する。今後、説明を簡略化するために、この処理で得たドメインをRadon変換対数自己相関(LACR)と呼ぶ。LACRは被写体の平行移動に不変であり、ドメインの畳み込みによる相互相関によって拡大率と回転角度とが検出できる。また、LACRの自己相関は、拡大縮小、回転及び平行移動に不変である。
【００３２】
従来のRadon・Fourier変換法との違いは、本実施形態においては、パワースペクトルではなく自己相関を用いることと、動径を対数化する点である。被写体の拡大縮小はパワースペクトルドメインの動径方向の拡大縮小でも対応できるが、離散化されたパワースペクトルを調整するよりも、自己相関の方が連続的に柔軟に調整できる。また、動径の対数化により、拡大率と回転角度とをドメインの畳み込みによる相互相関で算出できる点が優れている。さらに、LACRの自己相関は拡大縮小、回転、平行移動に不変である点が特有である。
【００３３】
パワースペクトルの逆Fourier 変換は自己相関となる。パワースペクトル、および自己相関は被写体の移動不変性を示し、一方、位相成分は位相限定相関により被写体の移動量を示す。そこで、本実施形態では、LACRと位相限定相関を組み合わせたパターンマッチング方法を提案している。以降においては、Radon変換自体を解説し、ついで、LACRの導出について説明し、拡大縮小した場合の特性について述べ、さらには、テスト画像を用いてLACR の特性を検証する。その後、本実施形態に係るパターンマッチング装置及びパターンマッチング方法を説明する。
【００３４】
（Radon変換の説明）
ここでは、ディジタル濃淡画像のRadon変換を定義し、その特性を述べる。なお、以降では、Radon変換について述べるが、Radon変換は、いわゆるHough変換と実質的に同義であり、いわゆるHough変換を、本明細書におけるRadon変換として用いることも可能である。Radon変換は、Radon-Hough変換と呼ばれることもある。
【００３５】
まず、画像が与えられている2 次元領域R2の座標を位置ベクトルxで表し、ベクトルxにおける画像の輝度値をf(x)とする。
【００３６】
画像f(x) のRadon 変換は、デルタ関数δ(t)を用いて
2008250610.tif 000003
と定義される。なお、ξ = (cosθ，sinθ) とする。すなわち、偏角θ、動径r を通り、原点からの距離がr の直線を積分路としたf(x) の線積分が
2008250610.tif 000004
となる。
2008250610.tif 000005
をRadonドメインと呼ぶ。偏角θを横軸、動径rを縦軸とするディジタル濃淡画像により、Radonドメインを表すことができる。
【００３７】
ところで、画像f(x) をS 倍に拡大した画像をg(x) とする。すなわち、g(x) = f(x/S) である。画像g(x) のRadon 変換
2008250610.tif 000006
は、
2008250610.tif 000007
となる。Radonドメイン
2008250610.tif 000008
は動径方向(縦方向)にS倍され、値もS倍される。ドメインのスケーリングのみではなく、値が変更することに注意する。
【００３８】
また、画像f(x) をα度回転した画像をg(x) とする。すなわち、
2008250610.tif 000009
とすると、g(x) = f(A-1x) である。画像g(x)のRadon変換
2008250610.tif 000010
は、
2008250610.tif 000011
となる。Radonドメイン
2008250610.tif 000012
は偏角方向(水平方向)にαだけ移動される。
【００３９】
さらに、画像f(x)をベクトルaだけ平行移動した画像をg(x) とする。すなわち、g(x) = f(x-a)である。画像g(x) のRadon変換
2008250610.tif 000013
は、
2008250610.tif 000014
となる。Radonドメイン
2008250610.tif 000015
は各偏角θについて動径方向(垂直方向)に-a・ξだけ平行移動される。Radonドメインを離散化して行列で考えると、列は垂直移動するが、行は水平移動しない。
【００４０】
（Radonドメインの対数自己相関）
被写体の平行移動は、Radonドメインの各偏角における垂直移動となる。すなわち、各偏角θについて動径方向(垂直方向)の自己相関
2008250610.tif 000016
は、平行移動に不変な特徴量となる。ところで、被写体をS倍に拡大した画像g(x)の自己相関ACRg(θ，β)については、式(2)より、
2008250610.tif 000017
である。すなわち、自己相関ACR(θ，β)は動径方向(縦方向)にS倍され、値はS3倍される。なお、被写体をα度回転する場合、自己相関ACR(θ，β)はαだけ水平移動される。
【００４１】
（動径の対数変換及び差分算出）
Radon変換の自己相関ACR(θ，β)における動径(垂直方向)を対数化した
2008250610.tif 000018
について考える。なお、γ=lnβである。さらに、ACRドメインの動径方向における差分をとることで、LACRドメインを算出することができる。被写体をS倍に拡大する場合、対数自己相関LACR(θ，γ)は動径方向(縦方向) にln Sだけ移動され、値はS3倍される。また、被写体がα度回転する場合、LACR(θ，γ)は水平方向にα移動される。
【００４２】
（LACR自己相関）
さらに、LACR(θ，γ)の自己相関
2008250610.tif 000019
について考える。被写体をS倍に拡大する場合、ACLACR'(θ，δ)の値はS6倍される。そこで、
2008250610.tif 000020
と正規化する。正規化されたLACR自己相関ドメインである、ACLACR(ε，δ)は、被写体の拡大縮小、回転及び平行移動に不変な特徴量となる。
【００４３】
（Radon変換の実験例）
Radon変換についてより詳しく説明するために、以下、実際の画像を用いた実験例を説明する。
【００４４】
（実験に用いる画像とそのRadon変換）
図1(a)にテスト画像「SADO」を示す。この画像は縦512画素、横512画素のデジタル白黒画像である。画像の中心をxy座標系の原点とする。テスト画像「SADO」をRadon変換した結果を図1(b)に示す。図1(b)の横軸は偏角θを、縦軸は動径rを示す。ここでは、偏角θの範囲を0°から180°まで、動径の範囲を
2008250610.tif 000021
とする。
【００４５】
また、テスト画像「HOKKAIDO」を図2(a)に示し、この画像をRadon変換した結果を図2(b) に示す。画像が異なると、Radon 変換した結果も異なる。
【００４６】
テスト画像「SADO」の被写体を右方向に80画素、上方向に40画素平行移動した画像を図3(a)に示し、この画像をRadon 変換した結果を図3(b)に示す。被写体が平行移動すると、Radonドメインが垂直方向に移動していることがわかる。なお、各偏角に応じて垂直方向の移動量は異なるが、水平方向には移動していない。
【００４７】
また、テスト画像「SADO」の被写体を0.8 倍に拡大し、時計回りに25°回転させた画像を図4(a)に示し、この画像をRadon変換した結果を図4(b)に示す。被写体の拡大によってRadonドメインが垂直方向に0.8倍に拡大し、値が0.8倍になっていることが確認できる。また、被写体の回転によってRadonドメインが水平方向に25移動していることがわかる。
【００４８】
（Radon 変換の対数自己相関と不変性）
図1(b)に示すRadonドメインについて、動径方向(垂直方向)の自己相関を算出した画像(ACRドメイン)を図5(a)に示す。また、動径を対数化し、さらに動径方向での差分をとった画像(LACRドメイン)を図5(b)に示す。ここでは、負数の対数化を避けるために、図5(a)のACRドメインを上下に2 分し、上部を180°回転させて右側に接続する。すなわち、動径の範囲を正に制限し、偏角の範囲を0°〜360°の範囲に変更してから対数化する。
【００４９】
被写体を平行移動した図3(a)のLACRドメインを図6(a)に示す。図5(b)と図3(a)とは等しく、被写体を移動させてもLACRドメインは変化しないことが確認できる。また、被写体を拡大して回転させた図4(a)のLACRドメインを図6(b)に示す。動径が0となる図5(b)の一行と、動径がln 0.8となる図6(b)の一行を図7に示す。図6(b)は図5(b)を左方向に25、上方向にln 0.8移動し、値が0.51倍になっている。すなわち、被写体が拡大・回転すると、式(7)に示すようにLACRドメインが平行移動し、値が被写体の拡大率の3乗倍になっていることが確認できる。LACRドメインの相互相関によって、被写体の拡大率、回転角度の検出が可能である。
【００５０】
テスト画像「SADO」のLACRドメイン（図5(b)参照）の自己相関を図8(a)に示す。また、被写体が拡大・回転する場合のLACRドメイン（図6(b)参照）における自己相関を図8(b)に示す。2つのドメインは等しく、LACRドメインの自己相関は、被写体の拡大縮小、回転、平行移動に不変な特徴量となることが確認できる。
【００５１】
（本実施形態に係るパターンマッチング装置の構成）
ついで、本発明の一実施形態に係るパターンマッチング装置の構成を、図９〜図１３に基づいて説明する。この装置は、画像取得部１と、テンプレート画像処理部２と、対象画像処理部３と、記憶部４と、マッチング部５とを備えている（図９参照）。
【００５２】
画像取得部１は、画像データを取得する機能を備えている。このような画像取得部１は、デジタルカメラやイメージスキャナなどの適宜な装置により構成することができる。画像取得部１は、この実施形態では、デジタル画像を取得するものである。
【００５３】
記憶部４は、ハードディスク、光ディスク、光磁気ディスク、半導体メモリなどの、デジタルデータを記録可能な適宜の装置により構成されている。記憶部４は、テンプレート用のデータを記録するテンプレート用記憶部４１と、対象画像用のデータを記録する対象画像用記憶部４２とを備えている。これらの記憶部４１及び４２は、格納するデータに対応して便宜的に別のブロックとされているが、物理的に同じ記憶装置により構成されていてもよいし、別の記憶装置により構成されていてもよい。
【００５４】
テンプレート画像処理部２は、Radon変換部２１と、動径方向での自己相関算出部２２と、対数変換部２３と、差分算出部２４と、LACR自己相関ドメインの算出部２５とを備えている（図１０参照）。このようなテンプレート用画像処理部２は、例えば、コンピュータソフトウエアとコンピュータハードウエアとの組み合わせにより実現できる。テンプレート画像処理部２の詳細な動作は、後述する実施形態のパターンマッチング方法において詳しく説明する。
【００５５】
対象画像処理部３は、Radon変換部３１と、動径方向での自己相関算出部３２と、対数変換部３３と、差分算出部３４と、LACR自己相関ドメインの算出部３５とを備えている（図１１参照）。このような対象画像処理部３は、例えば、コンピュータソフトウエアとコンピュータハードウエアとの組み合わせにより実現できる。対象画像処理部３の詳細な動作は、後述する実施形態のパターンマッチング方法において詳しく説明する。
【００５６】
マッチング部５は、被写体の同定部５１と、拡大率及び回転角度の推定部５２と、拡大／縮小及び回転の処理部５３と、平行移動量の推定部５４とを備えている（図１２参照）。
【００５７】
被写体の同定部５１は、第１画像（例えばテンプレート画像）についての第１のLACR自己相関ドメインと、第２画像（例えば対象画像）についての第２のLACR自己相関ドメインとの比較により同定を行う構成となっている。
【００５８】
拡大率及び回転角度の推定部４２は、第１画像についての第１のLACRドメインと、第２画像についての第２のLACRドメインとの間の位相限定相関により、第１画像と第２画像との間における、拡大率又は回転角度を推定する構成となっている。
【００５９】
拡大／縮小及び回転の処理部５３は、推定された拡大率又は回転角度に基づいて第１画像及び第２画像の一方を補正することによって、両画像の間で拡大率及び回転角度を実質的に一致させる構成となっている。もちろん両画像を共に補正することは可能である。つまり、「一方を補正」というのは、両画像を共に補正する場合を含む意味で用いている。
【００６０】
平行移動量の推定部５４は、変換された第１画像と第２画像との間で位相限定相関を行うことにより、第１画像及び第２画像のうちの一方に対する他方の平行移動量を推定する構成となっている。
【００６１】
このようなマッチング部５は、例えば、コンピュータソフトウエアとコンピュータハードウエアとの組み合わせにより実現できる。マッチング部５の詳細な動作は、後述する実施形態のパターンマッチング方法において詳しく説明する。
【００６２】
（ハードウエア構成例）
本実施形態に係るパターンマッチング装置を実現するためのハードウエア構成例を、図１３に示す。この構成例は、画像入力装置７と、CPU８と、記憶装置９と、通信路１０とを備えている。
【００６３】
画像入力装置７は、前記した画像取得部１に対応するハードウエアであり、例えばカメラやスキャナにより構成される。CPU８は、例えばマイコンや汎用プロセッサである。CPU８は、記憶装置９に格納されたコンピュータプログラムに従って、所定の動作を行うようになっている。記憶装置９は、前記した記憶部４に対応するハードウエアであり、例えば磁気的記録装置、光学式記憶装置、半導体メモリ等により構成することができる。
【００６４】
通信路１０は、各要素間でのデータのやりとりを可能にするものであり、例えばバスラインである。ただし、通信路１０としては、無線による通信路でもよく、物理的な構成は制約されない。また、通信に用いられるプロトコルも特に制約されない。
【００６５】
もちろん、本実施形態のパターンマッチング装置を実現するためのハードウエア構成は、これに限るものではなく、例えば、画像処理用に設計されたハードウエア回路を、コンピュータプログラムの一部の機能を実現するために用いることも可能である。
【００６６】
（本実施形態に係るパターンマッチング方法）
つぎに、本実施形態に係るパターンマッチング方法を、図１４〜図１９を参照しながら説明する。
【００６７】
（パターンマッチングの概要）
まず、本実施形態におけるパターンマッチング全体の概要を、図１４を参照しながら説明する。
【００６８】
（図１４のステップＳＡ−１）
まず、テンプレート画像（第１画像に対応）を取得した後、その画像を処理し、パターンマッチングに必要なデータを生成しておく。ここで、テンプレート画像の数は、使用目的に応じて決定される。個人認証を考えた場合、一般には、一人あたり複数のテンプレート画像を用意することが多い。また、複数人のためのテンプレート画像を準備しておくことが通常である。
【００６９】
（図１４のステップＳＡ−２）
ついで、対象画像（第２画像に対応）を取得する。その後、テンプレート画像の場合と同様に、対象画像を処理し、パターンマッチングに必要なデータを生成する。
【００７０】
（図１４のステップＳＡ−３）
ついで、対象画像とテンプレート画像とのマッチングを行う。以降の説明では、テンプレート画像の処理、対象画像の処理、マッチングの順序で説明するが、各処理が並列的に行われても良い。各処理の順序は、使用目的に適するように、適宜に設定することができる。
【００７１】
（テンプレート画像の処理）
ついで、テンプレート画像の処理について、図１５を参照しながら説明する。
【００７２】
（図１５のステップＳＢ−１及びＳＢ−２）
まず、画像取得部１により、テンプレート画像（すなわちテンプレート用の原画像）を取得する。取得した原画像は、テンプレート用の記憶部４１に格納される。原画像の取得枚数は、使用目的に応じて決定される。以降については、一枚の原画像を例にして説明するが、原則として、各原画像について、同様の処理が行われる。テンプレート画像の一例を図１６（ａ）に示す。この例では、人の手首部分の静脈画像が用いられている。
【００７３】
（図１４のステップＳＢ−３）
ついで、テンプレート画像処理部２のRadon変換部２１により、前記において説明したRadon変換を、テンプレート画像に対して行う。すなわち、画像f(x,y)について、デルタ関数δ(t)を用いて、
2008250610.tif 000022
とRadon変換する。Radon変換後の
2008250610.tif 000023
をRadonドメインと呼び、横軸を偏角θ、縦軸を動径rとする。Radonドメインの一例を図１６（ｂ）に示す。この図の横軸は偏角（左：０〜右：πまで）、縦軸は動径（上側：負、中央：０、下側：正）である。なお、ここでのRadon変換を示す式で用いる記号は、説明の便宜上、前記とは若干異なっている。以降の説明においても同様である。
【００７４】
（図１４のステップＳＢ−４）
ついで、自己相関算出部２２により、Radonドメインにおける動径方向での自己相関を算出する。すなわち、Radonドメイン
2008250610.tif 000024
について
2008250610.tif 000025
という計算を行うことによって、動径方向での自己相関を得ることができる。自己相関の結果を図１６（ｃ）に示す。
【００７５】
（図１４のステップＳＢ−５）
ついで、対数変換部２３により、図１６（ｃ）に示す自己相関の動径（すなわち縦軸の値）を対数変換する。すなわち、ドメイン
2008250610.tif 000026
について
2008250610.tif 000027
とすることで、動径軸を対数化できる。ここで、動径軸を対数化するためには、動径軸が正である必要がある。そこで、対数化の前処理として、ドメイン
2008250610.tif 000028
を上下に分けて、上部を１８０°回転させてから、下部の右側に接続する。これにより、動径の範囲が正のみとなり、さらに、偏角の範囲が０〜２πとなる。その後、前記の対数化を行う。対数化の結果を図１６（ｄ）に示す。
【００７６】
（図１４のステップＳＢ−６及びＳＢ−７）
ついで、差分算出部２４により、ドメイン
2008250610.tif 000029
について、その動径方向における差分を、以下のようにして算出する。
2008250610.tif 000030
【００７７】
この計算により、LACRドメイン
2008250610.tif 000031
を得ることができる。ここで、自己相関を算出する際に、LACR(θ,γ)は、巡回しているか閉じている必要がある。偏角については２π周期に巡回しているが、対数化された動径が閉じているとは限らない。特に、原画像の原点が被写体に含まれる場合、対数化された動径の負領域は閉じない。そこで、差分算出により、LACR(θ,γ)を動径方向において閉じる必要がある。本実施形態では、前記のように差分を取ることにより、LACRドメインの上下（つまり動径方向）を閉じることができる。また、LACRドメインの偏角においては、２πで巡回している。LACRドメイン
2008250610.tif 000032
は、被写体の平行移動に不変となる。また、被写体を拡大縮小、回転させると、このドメインが平行移動する。このため、LACRドメインの比較（具体的には位相限定相関）に基づいて、被写体の拡大率、回転角度を推定することが可能である。LACRドメインの例を図１６（ｅ）に示す。
【００７８】
生成されたLACRドメインは、テンプレート用記憶部４１に格納される。
【００７９】
（図１４のステップＳＢ−８及びＳＢ−９）
ついで、算出部２５により、LACRドメイン
2008250610.tif 000033
についての自己相関を、以下のようにして算出する。
2008250610.tif 000034
【００８０】
ここでは、LACRドメイン
2008250610.tif 000035
の自己相関を、偏角θが２πで巡回することを考慮して算出する。これにより、LACR自己相関ドメイン
2008250610.tif 000036
を生成することができる。
【００８１】
LACR自己相関ドメイン
2008250610.tif 000037
は被写体の拡大縮小、平行移動、回転に不変であるという性質を持つ。したがって、このドメインの比較によって、物体を同定することができる。LACR自己相関ドメインの例を図１６（ｆ）に示す。
【００８２】
生成されたLACR自己相関ドメインは、テンプレート用記憶部４１に格納される。
【００８３】
（対象画像の処理）
次に、対象画像の処理について、図１７を参照しながら説明する。対象画像の処理は、基本的には、テンプレート画像と同様なので、対象画像については処理の概要のみ説明する。また、処理される画像データの変遷については、図１６に示す例と基本的に同様なので、必要に応じて図１６を参照する。
【００８４】
（図１７のステップＳＣ−１及びＳＣ−２）
まず、画像取得部１により、対象画像（すなわち認証の対象となる原画像）を取得する。取得した原画像は、対象画像用の記憶部４２に格納される。対象となる原画像の取得枚数は、使用目的に応じて決定される。以降については、一枚の原画像を例にして説明するが、原則として、各原画像について、同様の処理が行われる。
【００８５】
（図１４のステップＳＣ−３）
ついで、対象画像処理部３のRadon変換部３１により、前記において説明したRadon変換を対象画像に対して行う（図１６（ｂ）参照）。
【００８６】
（図１４のステップＳＣ−４）
ついで、自己相関算出部３２により、Radonドメインにおける動径方向での自己相関を算出する（図１６（ｃ）参照）。
【００８７】
（図１４のステップＳＣ−５）
ついで、対数変換部３３により、Radonドメインの自己相関における動径を対数変換する（図１６（ｄ）参照）。
【００８８】
（図１４のステップＳＣ−６及びＳＣ−７）
ついで、差分算出部３４により、動径が対数変換されたドメインについて、その動径方向における差分を算出する（図１６（ｅ）参照）。生成されたLACRドメインは、対象画像用記憶部４２に格納される。
【００８９】
（図１４のステップＳＣ−８及びＳＣ−９）
ついで、算出部３５により、LACRドメインについての自己相関を偏角θが２πで巡回することを考慮して算出する（図１６（ｆ）参照）。生成されたLACR自己相関ドメインは、対象画像用記憶部４２に格納される。
【００９０】
（マッチング処理）
ついで、マッチング処理の手順を、図１８及び図１９を参照しながら説明する。
【００９１】
（図１８のステップＳＤ−１）
本実施形態のマッチング処理においては、テンプレート画像（第１画像に相当）と対象画像（第２画像に相当）との同定をまずはじめに行う。マッチング部５の同定部５１（図１２参照）は、テンプレート画像についてのLACR自己相関ドメイン（図１９（ａ）参照）と、対象画像についてのLACR自己相関ドメイン（図１９（ｂ）参照）とを比較する。ここで、既に説明したように、LACR自己相関ドメインは、被写体の拡大縮小、平行移動及び回転に対して不変である。したがって、LACR自己相関ドメインを比較することによって、対象画像とテンプレート画像とを同定することができる。例えば、複数のテンプレート画像の内から、対象画像に対応する１枚あるいは複数枚を選択することができる。比較方法としては、例えば、２つのLACR自己相関ドメインの２乗誤差を計測し、予め設定しておいた許容誤差以内であれば、対象画像とテンプレート画像とは同じであると判定することができる。もちろん、比較方法はこれだけに制約されない。
【００９２】
（図１８のステップＳＤ−２）
ついで、マッチング部５の推定部５２は、同定した画像におけるLACRドメインどうしの位相限定相関を行う（図１９（ｃ）及び（ｄ）参照）。これにより、一方の画像（例えばテンプレート画像）に対する他方の画像（例えば対象画像）の拡大率及び回転角度を推定することができる。
【００９３】
（図１８のステップＳＤ−３）
ついで、マッチング部５の処理部５３は、推定された拡大率及び回転角度を用いて、一方の画像（通常は対象画像であるがテンプレート画像でもよい）の原画像を拡大／縮小及び回転して補正（すなわち変換）する。これにより、両画像間での拡大率及び回転角度を実質的に一致させることができる。ここで「実質的に一致」とは、目的とするマッチングの精度確保に必要な程度に一致させるという意味であり、多少の相違があることは許容される。もちろん、完全に一致させるように処理を行う設計としてもよい。
【００９４】
変換された原画像は、処理部５３により、対象画像用の記憶部４２に格納される。
【００９５】
（図１８のステップＳＤ−４）
ついで、マッチング部５の推定部５４は、変換された原画像（図１９（ｅ）参照）と、テンプレート用の原画像（図１９（ｆ）参照）との位相限定相関によって、相対的な平行移動量を推定する。本実施形態では、回転角度及び縮尺がほぼ等しい画像を用いているので、一次元での位相限定相関により、相対的な平行移動量を精度良く算出することができる。
【００９６】
なお、本発明の範囲は、前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加え得ることはもちろんである。
【００９７】
例えば、前記した各構成要素は、機能ブロックとして存在していればよく、独立したハードウエアとして存在しなくても良い。また、実装方法としては、ハードウエアを用いてもコンピュータソフトウエアを用いても良い。さらに、本発明における一つの機能要素が複数の機能要素の集合によって実現されても良い。本発明における複数の機能要素が一つの機能要素により実現されても良い。
【００９８】
また、機能要素は、物理的に離間した位置に配置されていてもよい。この場合、機能要素どうしがネットワークにより接続されていても良い。
【００９９】
また、前記実施形態では、第１画像としてテンプレート画像、第２画像として対象画像を例にしたが、第１画像として対象画像、第２画像としてテンプレート画像を用いることも可能である。
【０１００】
また、前記した第１画像及び第２画像の一方あるいは両方において動画を用いることも可能である。動画は静止画の組み合わせにより表現されるので、動画を構成する静止画を用いて、前記した方法により、マッチングを行うことができる。
【図面の簡単な説明】
【０１０１】
【図１】図（ａ）は、実験例で用いたテスト画像「SADO」である。図（ｂ）は、そのRadonドメインであり、横軸は偏角（°）、縦軸は動径である。
【図２】図（ａ）は、実験例で用いたテスト画像「HOKKAIDO」である。図（ｂ）は、そのRadonドメインであり、横軸は偏角（°）、縦軸は動径である。
【図３】図（ａ）は、実験例で用いたテスト画像「SADO」を平行移動した例である。図（ｂ）は、そのRadonドメインであり、横軸は偏角（°）、縦軸は動径である。
【図４】図（ａ）は、実験例で用いたテスト画像「SADO」を縮小及び回転させた例である。図（ｂ）は、そのRadonドメインであり、横軸は偏角（°）、縦軸は動径である。
【図５】図（ａ）は、実験例で用いたテスト画像「SADO」のACRドメインである。図（ｂ）は、そのLACRドメインである。これらの図において、横軸は偏角（°）、縦軸は動径である。
【図６】図（ａ）は、被写体を平行移動させた場合のLACRドメインを示す。図（ｂ）は、被写体を拡大して回転させた場合のLACRドメインを示す。これらの図において、横軸は偏角（°）、縦軸は動径である。
【図７】LACRドメインの断面を示すグラフである。この図において横軸は偏角、縦軸はLACRドメインの値である。
【図８】図（ａ）は、実験例でのテスト画像におけるLACR自己相関ドメインを示す図である。図（ｂ）は、テスト画像での被写体を拡大させかつ回転させた場合のLACR自己相関ドメインを示す図である。これらの図において、横軸は偏角（°）、縦軸は動径である。
【図９】本発明の一実施形態に係るパターンマッチング装置の概略的な構成を説明するためのブロック図である。
【図１０】テンプレート画像処理部の概略的な構成を説明するためのブロック図である。
【図１１】対象画像処理部の概略的な構成を説明するためのブロック図である。
【図１２】マッチング部の概略的な構成を説明するためのブロック図である。
【図１３】パターンマッチング装置を構成するためのハードウエア構成例を示すブロック図である。
【図１４】パターンマッチング方法の基本的な手順を説明するためのフローチャートである。
【図１５】登録用テンプレート画像の処理手順を説明するためのフローチャートである。
【図１６】登録用テンプレート画像の処理手順に用いるデータの例を説明するための説明図である。
【図１７】対象画像の処理手順を説明するためのフローチャートである。
【図１８】パターンマッチングの手順を説明するためのフローチャートである。
【図１９】パターンマッチングに用いるデータの例を説明するための説明図である。
【符号の説明】
【０１０２】
１  画像取得部
２  テンプレート画像処理部
２１  Radon変換部
２２  動径方向での自己相関算出部
２３  対数変換部
２４  差分算出部
２５  LACR自己相関ドメインの算出部
３  対象画像処理部
３１  Radon変換部
３２  動径方向の自己相関算出部
３３  対数変換部
３４  差分算出部
３５  LACR自己相関ドメインの算出部
４  記憶部
４１  テンプレート用記憶部
４２  対象画像用記憶部
５  マッチング部
５１  被写体の同定部
５２  拡大率及び回転角度の推定部
５３  拡大／縮小及び回転処理部
５４  平行移動量の推定部
７  画像入力装置
８  ＣＰＵ
９  記憶装置
１０  通信路
【図７】
2008250610.tif 000038
【図９】
2008250610.tif 000039
【図１０】
2008250610.tif 000040
【図１１】
2008250610.tif 000041
【図１２】
2008250610.tif 000042
【図１３】
2008250610.tif 000043
【図１４】
2008250610.tif 000044
【図１５】
2008250610.tif 000045
【図１６】
2008250610.tif 000046
【図１７】
2008250610.tif 000047
【図１８】
2008250610.tif 000048
【図１９】
2008250610.tif 000049
【図１】
2008250610.tif 000050
【図２】
2008250610.tif 000051
【図３】
2008250610.tif 000052
【図４】
2008250610.tif 000053
【図５】
2008250610.tif 000054
【図６】
2008250610.tif 000055
【図８】
2008250610.tif 000056