(57)【要約】【課題】パターンマッチング法による画像パターン抽出に、必要となる全パラメータを自動的に設定でき、画像パターン抽出を保証しながら計算量を削減する。【解決手段】手段２により画像のノイズ量を算定、および手段４によりテンプレートの特徴量を算定し、これら量および手段１のテンプレートマッチング法を基に、手段５により類似度を計算するための評価関数を決定し、手段６により評価関数に含まれるテンプレートをずらす際のずらし量パラメータ、多少のパターンの変形が発生している場合に必要なパターンの変形量パラメータ、抽出の可否を判断するためのしきい値からなる３パラメータを設定する。  この３パラメータを使用してテンプレートマッチング対象となる画像とテンプレートとの類似度から特定パターンの画像を抽出することも含む。【選択図】  図１
2006023976.tif 000002
【特許請求の範囲】
【請求項１】
テンプレートマッチング法によって、画像内から特定の画像パターンを抽出する画像パターン抽出方法におけるパラメータ設定方法であって、
テンプレートマッチング法を蓄積するテンプレートマッチング法蓄積ステップと、
テンプレートマッチング対象になる前記画像のノイズ量を算定するノイズ量算定ステップと、
少なくとも１つのテンプレートパターンを蓄積するテンプレート蓄積ステップと、
前記テンプレート蓄積ステップに蓄積されたテンプレートの特徴量を計算するテンプレート特徴量計算ステップと、
前記テンプレートマッチング法、ノイズ量およびテンプレート特徴量を用いてテンプレートマッチングを行う際の類似度低下を定量的に評価する類似度評価値決定ステップと、
前記テンプレートマッチング法蓄積ステップに蓄積されるテンプレートマッチング法と前記類似度評価値決定ステップで決定された類似度評価値を基に、画像上をテンプレートをずらしながら走査させる際のずらし量を決定するずらし量パラメータと、テンプレートまたは画像パターンの変形量を決める変形パラメータおよび画像パラメータの抽出可否を判断するしきい値からなる３パラメータを設定する３パラメータ設定ステップと、
を有することを特徴とするパラメータ設定方法。
【請求項２】
テンプレートマッチング法によって、画像内から特定の画像パターンを抽出する画像パターン抽出方法であって、
テンプレートマッチング法を蓄積するテンプレートマッチング法蓄積ステップと、
テンプレートマッチング対象になる前記画像のノイズ量を算定するノイズ量算定ステップと、
少なくとも１つのテンプレートパターンを蓄積するテンプレート蓄積ステップと、
前記テンプレート蓄積ステップに蓄積されたテンプレートの特徴量を計算するテンプレート特徴量計算ステップと、
前記テンプレートマッチング法、ノイズ量およびテンプレート特徴量を用いてテンプレートマッチングを行う際の類似度低下を定量的に評価する類似度評価値決定ステップと、
前記テンプレートマッチング法蓄積ステップに蓄積されるテンプレートマッチング法と前記類似度評価値決定ステップで決定された類似度評価値を基に、画像上をテンプレートをずらしながら走査させる際のずらし量を決定するずらし量パラメータと、テンプレートまたは画像パターンの変形量を決める変形パラメータおよび画像パラメータの抽出可否を判断するしきい値からなる３パラメータを設定する３パラメータ設定ステップと、
テンプレートマッチング対象になる前記画像を蓄積する画像蓄積ステップと、
前記テンプレート蓄積ステップに蓄積されたテンプレートを、前記３パラメータを利用して前記画像蓄積ステップに蓄積された画像の上を走査させ、前記テンプレートマッチング法によってパターンの類似を判断する類似パターン走査抽出ステップと、
を有することを特徴とする画像パターン抽出方法。
【請求項３】
テンプレートマッチング法によって、画像内から特定の画像パターンを抽出する画像パターン抽出装置におけるパラメータ設定装置であって、
テンプレートマッチング法を蓄積するテンプレートマッチング法蓄積手段と、
テンプレートマッチング対象になる前記画像のノイズ量を算定するノイズ量算定手段と、
少なくとも１つのテンプレートパターンを蓄積するテンプレート蓄積手段と、
前記テンプレート蓄積手段に蓄積されたテンプレートの特徴量を計算するテンプレート特徴量計算手段と、
前記テンプレートマッチング法、ノイズ量およびテンプレート特徴量を用いてテンプレートマッチングを行う際の類似度低下を定量的に評価する類似度評価値決定手段と、
前記テンプレートマッチング法蓄積手段に蓄積されるテンプレートマッチング法と前記類似度評価値決定手段で決定された類似度評価値を基に、画像上をテンプレートをずらしながら走査させる際のずらし量を決定するずらし量パラメータと、テンプレートまたは画像パターンの変形量を決める変形パラメータおよび画像パラメータの抽出可否を判断するしきい値からなる３パラメータを設定する３パラメータ設定手段と、
を有することを特徴とするパラメータ設定装置。
【請求項４】
テンプレートマッチング法によって、画像内から特定の画像パターンを抽出する画像パターン抽出装置であって、
テンプレートマッチング法を蓄積するテンプレートマッチング法蓄積手段と、
テンプレートマッチング対象になる前記画像のノイズ量を算定するノイズ量算定手段と、
少なくとも１つのテンプレートパターンを蓄積するテンプレート蓄積手段と、
前記テンプレート蓄積手段に蓄積されたテンプレートの特徴量を計算するテンプレート特徴量計算手段と、
前記テンプレートマッチング法、ノイズ量およびテンプレート特徴量を用いてテンプレートマッチングを行う際の類似度低下を定量的に評価する類似度評価値決定手段と、
前記テンプレートマッチング法蓄積手段に蓄積されるテンプレートマッチング法と前記類似度評価値決定手段で決定された類似度評価値を基に、画像上をテンプレートをずらしながら走査させる際のずらし量を決定するずらし量パラメータと、テンプレートまたは画像パターンの変形量を決める変形パラメータおよび画像パラメータの抽出可否を判断するしきい値からなる３パラメータを設定する３パラメータ設定手段と、
テンプレートマッチング対象になる前記画像を蓄積する画像蓄積手段と、
前記テンプレート蓄積手段に蓄積されたテンプレートを、前記３パラメータを利用して前記画像蓄積手段に蓄積された画像の上を走査させ、前記テンプレートマッチング法によってパターンの類似を判断する類似パターン走査抽出手段と、
を有することを特徴とする画像パターン抽出装置。
【請求項５】
請求項１に記載のパラメータ抽出方法又は請求項２に記載の画像パターン抽出方法を、コンピュータプログラムで記載してそれを実行可能に構成したことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テンプレートを用意して未知画像上を少しずつずらしながら走査させ、テンプレートに類似する特定パターンを抽出するパターンマッチング法における画像パターン抽出方法および装置に係り、特に画像パターン抽出用パラメータの設定方法および装置に関する。
【背景技術】
【０００２】
テンプレートマッチングによって画像の中の特定の画像パターンを抽出する方法では、計算量を際限なく増やすことができれば、つまり考えられる限りのノイズや変形が発生したテンプレートを用意し、考えられる限りの細かさで各テンプレートを走査させることができれば、原理的に抽出もれは発生しない。しかし、この方法では計算量が非常に大きくなって現実的には利用できない。
【０００３】
このため、従来は実験的に変形や走査量などのパラメータを設定して、さらに判定に利用するしきい値をマッチング結果を確認しながら設定して、テンプレートマッチングを利用して来た。
【０００４】
例えば、環境にあわせ、パラメータの一部をある程度自動的に決定（修正）して利用する方法が提案されている（例えば、特許文献１参照）。
【特許文献１】特開平５−５４１２７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献１の方法は、２値化のしきい値を自動補正することに限られており、パターンマッチングにおける他のパラメータは予め手動で設定することが必要である。
【０００６】
本発明の目的は、パターンマッチング法による画像パターン抽出に、必要となる全パラメータをテンプレートの特徴などから自動的に設定でき、この設定により特定の画像パターン抽出を保証しながら計算量を削減できるパラメータ抽出方法、画像パターン抽出方法、パラメータ抽出装置、画像パターン抽出装置、およびこれら方法のプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明は、前記の課題を解決するため、画像のノイズ量を算定およびテンプレートの特徴量を算定し、これら量から類似度を計算するための評価関数を決定し、評価関数に含まれるテンプレートをずらす際のずらし量パラメータ、多少のパターンの変形が発生している場合に必要なパターンの変形量パラメータ、抽出の可否を判断するためのしきい値からなる３パラメータを設定し、この３パラメータを使用してテンプレートマッチング対象となる画像とテンプレートとの類似度から特定パターンの画像を抽出するようにしたもので、以下の方法、装置およびプログラムを特徴とする。
【０００８】
（１）テンプレートマッチング法によって、画像内から特定の画像パターンを抽出する画像パターン抽出方法におけるパラメータ設定方法であって、
テンプレートマッチング法を蓄積するテンプレートマッチング法蓄積ステップと、
テンプレートマッチング対象になる前記画像のノイズ量を算定するノイズ量算定ステップと、
少なくとも１つのテンプレートパターンを蓄積するテンプレート蓄積ステップと、
前記テンプレート蓄積ステップに蓄積されたテンプレートの特徴量を計算するテンプレート特徴量計算ステップと、
前記テンプレートマッチング法、ノイズ量およびテンプレート特徴量を用いてテンプレートマッチングを行う際の類似度低下を定量的に評価する類似度評価値決定ステップと、
前記テンプレートマッチング法蓄積ステップに蓄積されるテンプレートマッチング法と前記類似度評価値決定ステップで決定された類似度評価値を基に、画像上をテンプレートをずらしながら走査させる際のずらし量を決定するずらし量パラメータと、テンプレートまたは画像パターンの変形量を決める変形パラメータおよび画像パラメータの抽出可否を判断するしきい値からなる３パラメータを設定する３パラメータ設定ステップと、
を有することを特徴とするパラメータ設定方法。
【０００９】
（２）テンプレートマッチング法によって、画像内から特定の画像パターンを抽出する画像パターン抽出方法であって、
テンプレートマッチング法を蓄積するテンプレートマッチング法蓄積ステップと、
テンプレートマッチング対象になる前記画像のノイズ量を算定するノイズ量算定ステップと、
少なくとも１つのテンプレートパターンを蓄積するテンプレート蓄積ステップと、
前記テンプレート蓄積ステップに蓄積されたテンプレートの特徴量を計算するテンプレート特徴量計算ステップと、
前記テンプレートマッチング法、ノイズ量およびテンプレート特徴量を用いてテンプレートマッチングを行う際の類似度低下を定量的に評価する類似度評価値決定ステップと、
前記テンプレートマッチング法蓄積ステップに蓄積されるテンプレートマッチング法と前記類似度評価値決定ステップで決定された類似度評価値を基に、画像上をテンプレートをずらしながら走査させる際のずらし量を決定するずらし量パラメータと、テンプレートまたは画像パターンの変形量を決める変形パラメータおよび画像パラメータの抽出可否を判断するしきい値からなる３パラメータを設定する３パラメータ設定ステップと、
テンプレートマッチング対象になる前記画像を蓄積する画像蓄積ステップと、
前記テンプレート蓄積ステップに蓄積されたテンプレートを、前記３パラメータを利用して前記画像蓄積ステップに蓄積された画像の上を走査させ、前記テンプレートマッチング法によってパターンの類似を判断する類似パターン走査抽出ステップと、
を有することを特徴とする画像パターン抽出方法。
【００１０】
（３）テンプレートマッチング法によって、画像内から特定の画像パターンを抽出する画像パターン抽出装置におけるパラメータ設定装置であって、
テンプレートマッチング法を蓄積するテンプレートマッチング法蓄積手段と、
テンプレートマッチング対象になる前記画像のノイズ量を算定するノイズ量算定手段と、
少なくとも１つのテンプレートパターンを蓄積するテンプレート蓄積手段と、
前記テンプレート蓄積手段に蓄積されたテンプレートの特徴量を計算するテンプレート特徴量計算手段と、
前記テンプレートマッチング法、ノイズ量およびテンプレート特徴量を用いてテンプレートマッチングを行う際の類似度低下を定量的に評価する類似度評価値決定手段と、
前記テンプレートマッチング法蓄積手段に蓄積されるテンプレートマッチング法と前記類似度評価値決定手段で決定された類似度評価値を基に、画像上をテンプレートをずらしながら走査させる際のずらし量を決定するずらし量パラメータと、テンプレートまたは画像パターンの変形量を決める変形パラメータおよび画像パラメータの抽出可否を判断するしきい値からなる３パラメータを設定する３パラメータ設定手段と、
を有することを特徴とするパラメータ設定装置。
【００１１】
（４）テンプレートマッチング法によって、画像内から特定の画像パターンを抽出する画像パターン抽出装置であって、
テンプレートマッチング法を蓄積するテンプレートマッチング法蓄積手段と、
テンプレートマッチング対象になる前記画像のノイズ量を算定するノイズ量算定手段と、
少なくとも１つのテンプレートパターンを蓄積するテンプレート蓄積手段と、
前記テンプレート蓄積手段に蓄積されたテンプレートの特徴量を計算するテンプレート特徴量計算手段と、
前記テンプレートマッチング法、ノイズ量およびテンプレート特徴量を用いてテンプレートマッチングを行う際の類似度低下を定量的に評価する類似度評価値決定手段と、
前記テンプレートマッチング法蓄積手段に蓄積されるテンプレートマッチング法と前記類似度評価値決定手段で決定された類似度評価値を基に、画像上をテンプレートをずらしながら走査させる際のずらし量を決定するずらし量パラメータと、テンプレートまたは画像パターンの変形量を決める変形パラメータおよび画像パラメータの抽出可否を判断するしきい値からなる３パラメータを設定する３パラメータ設定手段と、
テンプレートマッチング対象になる前記画像を蓄積する画像蓄積手段と、
前記テンプレート蓄積手段に蓄積されたテンプレートを、前記３パラメータを利用して前記画像蓄積手段に蓄積された画像の上を走査させ、前記テンプレートマッチング法によってパターンの類似を判断する類似パターン走査抽出手段と、
を有することを特徴とする画像パターン抽出装置。
【００１２】
（５）上記の（１）に記載のパラメータ抽出方法又は（２）に記載の画像パターン抽出方法を、コンピュータプログラムで記載してそれを実行可能に構成したことを特徴とするプログラム。
【発明の効果】
【００１３】
以上のように、本発明によれば、テンプレートマッチング法を利用して、テンプレートをテンプレートマッチング対象となる画像上をずらしながら特定の画像パターンを抽出する場合に、予めテンプレートの特徴量を計算し、ノイズ量を算定しておくことによって、見落としが発生しないようなずらし量パラメータ、変形量パラメータ、そしてしきい値を自動的に設定できる。さらに、画像パターン抽出に見落としが発生するか否かについて適確に判断できる。
【００１４】
また、設定した３パラメータを利用したテンプレートマッチングにより、特定の画像パターン抽出を保証しながら計算量を削減した効率的なパターン抽出ができる。
【発明を実施するための最良の形態】
【００１５】
図１は、本発明の実施形態を示すパラメータ設定装置のブロック構成図であり、各ブロックはコンピュータを構成するＣＰＵ、メモリ、ハードディスク、入出力装置などのハードウェアと、ＯＳやアプリケーションプログラムなどのソフトウェアとの有機的結合によって実現される。
【００１６】
テンプレートマッチング法蓄積手段１は、テンプレートと画像を照合する前処理としてのパラメータ設定までのテンプレートマッチング法を蓄積（格納）しておく。ノイズ量算定手段２は、テンプレートマッチング対象になる画像のノイズ量を算定し、そのデータを蓄積しておく。テンプレート蓄積手段３は、複数のテンプレートをパターンデータとして蓄積しておく。
【００１７】
テンプレート特徴量計算手段４は、テンプレート蓄積手段３に蓄積する複数のテンプレートをそれぞれ読み込み、各テンプレートが持つ特徴量を計算する。類似度評価値決定手段５は、ノイズ量算定手段２で算定するノイズ量およびテンプレート特徴量計算手段４で求めた特徴量を用いて、画像とテンプレートとの照合（マッチング）を行う際の類似度低下の下限値を決定する。３パラメータ設定手段６は、画像上をテンプレートをずらしながら走査させる際に、類似度評価値決定手段５で決定した類似度低下の下限値を基に、３つのパラメータ（マッチングする際のテンプレートのずらし量を決めるずらし量パラメータ、パターンの変形を決める変形パラメータ、抽出可否を判断するしきい値）を決定する。これら手段４〜６による処理は、テンプレートマッチング法蓄積手段１に蓄積するテンプレートマッチング法に応じて適宜決定される。
【００１８】
図２は、本発明の実施形態を示すパターン抽出装置のブロック構成図であり、図１の装置構成と異なる部分は、画像蓄積手段７と類似パターン走査抽出手段８を追加した点にある。
【００１９】
画像蓄積手段７は、テンプレートマッチング法により特定パターンを抽出しようとする画像を蓄積する。この蓄積は、パターンマッチング対象画像をイメージリーダ等によって読み込むか、カメラで撮影した画像をイメージデータとして読み込む。
【００２０】
類似パターン走査抽出手段８は、３パラメータ設定手段６で設定されたパラメータを利用し、テンプレートマッチング法蓄積手段１に蓄積するテンプレートマッチング法に従ってテンプレートを画像上を走査させ、パターンの類似度を実際に判断し、適合した画像パターンを抽出する。
【００２１】
以上の図１または図２の構成において、テンプレートマッチング法蓄積手段１は、テンプレートマッチング法、つまり２枚の画像を比較する方法、もしくは照合の方法（具体的には計算式）を蓄積する。２枚の画像を比較する照合の方法には様々なものが数多く存在するが、ここではその方法自体を蓄えておく。
【００２２】
なお、テンプレートを用いて未知画像に対しテンプレートマッチングを行う場合、未知画像の一部を切り出してテンプレートと同じ形と画素数を得、テンプレートマッチング法蓄積手段１に蓄えられた方法を利用して類似度を計算する。未知画像の一部を切り出す際は、切り出し方を決定することが必要であり、ここにパラメータが発生する。
【００２３】
まず、テンプレートを切り出す位置は、基準となる位置、例えば画像の隅からスタートする。これに続いてどれだけ近くの位置を基準として、テンプレートを切り出すかを決めるのが、ずらし量パラメータである。このパラメータは、例えば１画素単位、２画素単位といった画素単位でも良いし、サブピクセル単位となることもあり得る。
【００２４】
これとは独立に、パターンに変形（歪み、拡大縮小等）が発生する場合には、テンプレートを変形させるか、入力パターンを変形させるなどを行って、変形へ対応する必要がある。この変形の細かさを定義するのが変形パラメータである。
【００２５】
最後に、それぞれのテンプレートマッチングの演算により得られた数値（類似度）によって、類似（抽出の可否）を判断するためのしきい値が必要となる。
【００２６】
これらは３パラメータ設定手段６でなされ、この詳細を説明する。まず、テンプレートマッチングの方法には多くの方法がある。例えば、対応する画素値同士の差の絶対値の和の合計、差の２乗の合計を計算する方法がある。その値を類似度と呼ぶことができる。これを式で示すと、画像とテンプレートをそれぞれｆ，ｇとしたとき、‖ｆ−ｇ‖2である。
【００２７】
また別の例には、相関法がある。テンプレートと同じ大きさの画像、つまり画素数がテンプレートと同じものについて、統計的手法である相関値を計算する。計算する値は、
【００２８】
【数１】
2006023976.tif 000003
【００２９】
となる。
【００３０】
さらにこの際、予め平均値をオフセットし、相関値を計算する方法が正規化相関法である。この場合、計算する値は、
【００３１】
【数２】
2006023976.tif 000004
【００３２】
となる。ここで、ｆ，ｇの上線として「−」を付したものは、ｆ，ｇの平均値を意味する。
【００３３】
さらに別の例としては、相関値演算の前に、様々な前処理を行う方法がある。すなわち、平均を差し引く場合が正規化相関法である。例えば、平滑化処理、対数変換や微分処理が考えられる。
【００３４】
相関法そのものにはパラメータは存在しないが、利用する前処理によっては、パラメータが発生する場合がある。例えば、予めテンプレートと未知パターンを平滑化して高周波成分をカットしておく場合に平滑化の度合いをσで表すと、これが平滑化を伴う相関法におけるパラメータとなる。具体的な例として、微分処理と平滑化処理を相関値演算の前に行う方法の場合、計算する値は、
【００３５】
【数３】
2006023976.tif 000005
【００３６】
となる。ここで、＊は畳み込み演算、∇は微分処理、Ｇσはガウス関数である。つまり、
【００３７】
【数４】
2006023976.tif 000006
【００３８】
である。実際には、デジタル処理であるため、積分計算ではなく総和演算になる。
【００３９】
なお、前処理をどのように設定しても、最終的に相関法を用いる場合、得られる相関値は常に−１〜１の範囲となり、一致する場合は値が１、１に近いほど類似していると判断できる。
【００４０】
以上のように、テンプレートマッチング方法には様々なものが存在するが、本発明では特に規定しない場合はどの方法を用いても良い。
【００４１】
図３は、図２に対応する３パラメータ設定とパターン抽出のためのフローチャートを示す。以下、図３に従って詳細に説明する。
【００４２】
（Ｓ１）テンプレートマッチング法蓄積ステップ
テンプレートマッチング法蓄積は、前記のように、テンプレートマッチング法、つまり２枚の画像を比較する方法、もしくは照合の方法（具体的には計算式）を蓄積する。２枚の画像を比較する照合の方法には様々なものが数多く存在するが、ここではその方法自体を蓄積する。
【００４３】
（Ｓ２）ノイズ量算定ステップ
ノイズ量算定は、テンプレートマッチングを行う際、入力未知の画像のノイズ量を算定する。このノイズ量は、テンプレートマッチング法に依存する値となる。例えば、高周波成分を落とす前処理が導入された手法の場合には、高周波成分を中心としたノイズの影響は少なくなる。低周波成分を中心としたノイズの除去、例えば直流成分を除去する正規化相関法では、全体的な明るさ変化は直流成分そのものであるためノイズとはならない。
【００４４】
その計算方法は、例えば相関法や正規化相関法では、ノイズの量は一般的な指標であるＳ／Ｎ比である。これは自然な計算により求められる。これは、例えば信号の強さを、
【００４５】
【数５】
2006023976.tif 000007
【００４６】
と書き表すと、ノイズｎは自然な形で、
【００４７】
【数６】
2006023976.tif 000008
【００４８】
となり、この比をとればＳ／Ｎ比となるためである。同様にして、他の前処理を伴う相関法においても、同じような指標を取り入れることができる。例えば、線形の前処理Ｇを相関値演算で利用する場合にＧ＊ｇを前処理結果と表現すると、Ｐ（ｎ）＝‖Ｇ＊ｎ‖2がその値となる。
【００４９】
なお、ノイズの算定例は、テンプレートの特徴量に応じて適宜設定されるため、後に詳細を説明する。
【００５０】
（Ｓ３）テンプレート蓄積ステップ
テンプレート蓄積は、抽出しようとするパターンまたは類似するパターンを蓄積する。これはいわゆるテンプレートであり、パターン照合を行う際の辞書にあたるものである。テンプレートは、２値画像、濃淡画像、カラー画像、その他のマルチバンド画像などであり、ここでは限定しない。但し、実際にマッチング処理を行う画像の形式には依存する。
【００５１】
テンプレートを決定したとき、自動的にそのサイズ（一般な長方形の場合には縦横の画素数）が決まる。当然ながら、テンプレートの形が長方形でない場合は、縦横のような単純な数値でその形と大きさを表現することはできず、別の方法で規定する必要が発生する。しかしこの点は、本発明では任意の方法を採用でき、単に特徴量や照合結果の計算の際に、その形に応じた計算を行うことになる。
【００５２】
（Ｓ４）テンプレート特徴量計算ステップ
テンプレート特徴量計算は、テンプレートが持つ特徴量を計算する。この特徴量は、ノイズ量算定ステップで用いたと同じように、テンプレートマッチング法に依存する。
【００５３】
実際には、上記ノイズ量算定ステップの中で述べた信号の強さを利用する。この値は、もしもテンプレートマッチング法に内在するパラメータが存在しない場合は、ある１つの値となる。しかしもしも、テンプレートマッチング法に内在するパラメータが存在する場合は、そのパラメータ毎に１つの値が得られる。例えば、上記例で高周波成分をカットする場合、その高周波のカットの程度を示すパラメータσ毎に、特徴量が計算される。
【００５４】
以上を具体的な式で示すと、Ｇを相関値演算の前処理として利用する場合、テンプレートｇの特徴量は、Ｐ（ｇ）＝‖Ｇ＊ｇ‖2となる。もし、テンプレートマッチング法に内在するパラメータσが内在する場合は、前処理結果をＧσ＊ｇと書き、テンプレートの特徴量は、Ｐσ（ｇ）＝‖Ｇσ＊ｇ‖2と言うことができる。
【００５５】
なお、ｗをテンプレートに外接する円の直径を示す値（別の特徴量）とし、テンプレートのサイズとする。この値はマッチング法には依存しない値である。
【００５６】
（Ｓ５）類似度評価値決定ステップ
類似度評価値決定は、照合を行う際の類似度低下の下限を示す値を決定する。この値は、類似度の低下範囲を定量的に評価するための類似度評価関数によって計算される。この関数の形はテンプレートマッチング法毎に決まり、それぞれ異なるが、例えば相関法を基本とする照合法を利用する場合の類似度評価関数は、
【００５７】
【数７】
2006023976.tif 000009
【００５８】
という形である。ここで、σはマッチング法で利用する平滑化パラメータ、Ｆはマッチング法の相関値計算の前の処理に依存して決まる関数、ｓはずれ量を示す値、σ’は０以上σ以下の任意の値、Ｔはテンプレートの特徴量比、ｄ’は変形量を示す値、Ｎ1，Ｎ2はノイズの量を示す値である。平滑化を行わない場合はσ＝σ’＝０で固定と考えれば良い。これらの値を算定した上で類似度評価関数に代入することによって、類似度評価値が得られる。
【００５９】
まず、ずれ量ｓと変形量を示すｄ’の意味を述べる。ずれ量ｓは、後に行うテンプレートマッチングにおいて、テンプレートと比較する画像の間の、画素単位の位置ずれの最大値を示す。画像においては、物体を撮影する際の見かけの方向が変化すれば、変形も発生する。これも広い意味で位置ずれであり、このずれ量に含める。変形量を示すｄ’は、見かけの方向の変化や、対象となるパターンそのものの形の変化によって発生する変形の量を示す。
【００６０】
これらの見かけの変化については、テンプレートと対象画像の位置ずれを２次元ワープ関数（または変形ベクトル場、変形関数とも記す。非特許文献１参照）と表現することができる。
【００６１】
非特許文献１「変形関数による画像間対応関係の決定とその応用、電子情報通信学会論文誌 D-II,Vol.J82-D-II,No.9,pp.1374-1382，1999年9月」
見かけの変化表現は、２枚の画像の対応点の位置関係を関数で示すものであり、例えばｓ（ｘ，ｙ）を２次元ワープ関数としたとき、２枚の画像ｇ1，ｇ2はｇ2（ｘ，ｙ）＝ｇ1（ｓ（ｘ，ｙ））で表すことができる。この表現を利用すると、ｓは２次元ワープ関数の値の最大値、
【００６２】
【数８】
2006023976.tif 000010
【００６３】
となり、ｄ’は変形ベクトル場の変位の最大である。
【００６４】
次に、Ｆ、Ｔの具体的な例を示す。以下、Ｇσはガウス関数とし、平滑化を前処理とした相関値演算の場合、以下の式で表せる。
【００６５】
【数９】
2006023976.tif 000011
【００６６】
平滑化と一次微分処理を前処理とした相関値演算の場合、以下の式で表せる。
【００６７】
【数１０】
2006023976.tif 000012
【００６８】
平滑化と二次微分処理を前処理とした相関値演算の場合、以下の式で表せる。
【００６９】
【数１１】
2006023976.tif 000013
【００７０】
以上のように、Ｆは、（１−ｃｏｓξｓ）部分を除き、それぞれの前処理をフーリエ変換した式の２乗となる。微分のフーリェ変換はξを掛け合わせる処理、平滑化はガウス関数を掛け合わせる処理である。また、Ｔはそれぞれの前処理を施した後の２乗和から計算される値である。別の表現をすれば、異なるパラメータσ’、σのときのテンプレートの特徴量の比となる。
【００７１】
従って、以上の例以外であっても、微分処理と平滑化処理を組み合わせた前処理の場合は、同様の式を組み立てることができる。微分処理と平滑化処理以外の前処理を組み合わせる場合も、線形処理である限り、フーリエ変換後の処理を計算できるので同様に計算できる。
【００７２】
次に、ノイズの量を意味するＮ1，Ｎ2の一般的計算方法を述べる。これは、上で述べたすべての例において有効である。
【００７３】
Ｎ2はノイズとテンプレートそれぞれに前処理を施した後の２乗和の比、
【００７４】
【数１２】
2006023976.tif 000014
【００７５】
である。別の言い方をすれば、この値はノイズとテンプレートの特徴量の比である。ノイズの量は実測できないが、一般的なカメラのＳ／Ｎ比と、その他の変動を考慮した値を選べば良い。当然、この値は１（１はノイズの量Ｎが信号Ｓそのもの、すなわちテンプレートと同じという意味）よりかなり小さい値である。
【００７６】
また、Ｎ1はノイズとテンプレートに算定される相関値の絶対値の最大値と、Ｎ2の平方根との積である。一般的に、ノイズとテンプレートとの相関値は、ノイズがランダムである場合、一般的に−０.２〜＋０.２もしくは−０.４〜＋０.４程度に収まるので、この値を利用すれば良い。これらの例は、ノイズ量算定ステップにて直接利用することもできる。
【００７７】
以上は、前処理フィルタが線形であった場合の処理である。前処理に非線形処理が入る場合は、上記の議論から多少異なる処理が必要となる。つまりＮ1，Ｎ2には、非線形前処理でノイズ量が受ける影響が加算されたものとなる、
（Ｓ６）３パラメータ設定ステップ
３パラメータ設定は、画像上をテンプレートをずらしながら走査させる際に設定が必要な「ずらし量パラメータ」、パターンの変形を決める「変形パラメータ」、抽出可否を判断する「しきい値」を決定する。このうち、しきい値として利用するのは、類似度評価値である。その他の値の決定においても、類似度評価関数で類似度評価値を計算する際に利用する値が利用される。
【００７８】
ここで、ずらし量パラメータとは、ある画像上をテンプレート走査させてパターンの類似を判断する場合の、テンプレート走査（ずらす）量を意味する。当然ながら細かく設定すれば見落としがなくなるが、計算量が増加する。この値の単位は、ｄｏｔ（画素）である。
【００７９】
パターンの変形を決める変形パラメータとは、テンプレートまたは入力（未知）画像を強制的に変形させるための値（倍率、角度、曲率など）である。一般に画像では撮影されたパターンが変形（見かけの大きさ変化、斜めからの撮影による歪み、対象そのものの変化など）が発生する。このため、発生するであろう変形にあわせてテンプレートを変形させてパターンを走査させることで、変形に対応することができる。そのとき、様々な変形をすべて網羅することを考えれば、計算量は増加するが、見落としがなくなることが期待できる。
【００８０】
パターンの変形は、画像の見かけ上、どのような変形が発生するかによって決めれば良い。最も簡単には、拡大縮小である。斜め方向からの観測が入る場合は、回転や傾きを設定しても良い。見掛けの変形だけが発生する場合は、一般にアフィン変換で良い。透視投影まで行う場合はこれを設定しても良い。さらに、対象パターンの非線形歪みが発生する場合は、これを想定した変形を行う。
【００８１】
しきい値は、パターンを照合する際の、類似か否かを判断する値である。当然ながら、しきい値は小さいほど抽出もれは減少するが、誤抽出も増える。一般にこれはトレードオフの関係にあり、予め設定することは難しいとされている。
【００８２】
３パラメータ設定ステップは、以上の３種類のパラメータを定量的に決定するものである。これら３つのパラメータの値を具体的に決めるには、その指針が必要である。その１例が、見落としをなくしながら、できるだけ計算量を増やさない方法である。この条件を満たすパラメータの設定方法は、上記例で示した相関法の前処理に平滑化が含まれ、σがテンプレートマッチングに内在するパラメータとなっている場合は、以下のとおりである。
【００８３】
・ずらし量パラメータｓは、ｘ方向、ｙ方向共にσとする。
【００８４】
・変形パラメータｄ’をσ／ｗとする。
【００８５】
・しきい値を類似度評価関数で得られる値とする。
【００８６】
ここで、類似度評価関数で利用する数値は、ｓ＝σ×ｒ、ｄ’＝σ×ｒ／ｗ、σ’は類似度評価関数を最大とする数値、但しｒ＝０.５とする。なお、ｗはテンプレートの大きさを示し、テンプレートに外接する円の直径である。
【００８７】
次に、変形パラメータがｄ’とする場合の、実際の変形の方法について説明する。前述したように、ｄ’は変形ベクトル場の変位の最大値である。パターンを変形させる方法はいくつもあり、テンプレートを想定される変形ベクトル場によって変形させ、このときの変位の最大値がｄ’であれば良い。最も単純には、変形を２次元線形変換とする方法が考えられる。２次元線形変換は、自由度が６である（平行移動２、変形２）。この場合、変位に関係するパラメータは４つである。
【００８８】
例えば、縦横方向の拡大縮小率と、縦と横の傾きの４つのパラメータで表現することができる。例えば、縦または横の拡大率を１０％とするなら、ｄ’＝０.１となる。別の方法では、単純に変形を示す線形マトリクスの４つのパラメータを４次元と考えれば良い。いずれの場合も、変形を４次元のマトリクス、
【００８９】
【数１３】
2006023976.tif 000015
【００９０】
と表現したとき、ｄ’＝０は、
【００９１】
【数１４】
2006023976.tif 000016
【００９２】
であり、一般的には、｜ａ−１｜，｜ｂ｜，｜ｃ｜，｜ｄ−１｜の最大値がｄ’となる。ｄ’をσ／ｗ以下にするためには、これらの４つの値それぞれについて、σ／ｗ以下となるように設定する。例えば，傾きがない場合で、ｄ’を０.１以下にする場合であれば、ａとｂそれぞれを１±０.１、±０.２というように変化させていく。
【００９３】
別の例では、長方形が台形に見えるような歪みを考慮する方法も考えられるが、この場合も上記説明と同様に、変形パラメータをｄ’の範囲に収まるようにパラメータを設定すれば良い。
【００９４】
ここで、例えばσを整数にしておくことにより、ずらし量パラメータが整数となり、プログラム構成には適当である。
【００９５】
σの選択には、例えば平滑化と一次微分を用いた前処理を行う場合には、概ね、Ｐσ（ｇ）＝‖∇Ｇσ＊ｇ‖2とσ2との積が最大となるσを選ぶと良い。この場合、σ’は概ね０.７×σを利用すれば、類似度評価関数は最も大きな値となり、全部のσ’において計算を行う必要なない。この場合のＦは約０.１７６６であることは、数式を用いて計算できる。
【００９６】
また、ｒ＝０.５としているが、この数字は多少、大きくしても良い。しかし一般に、ｒを大きくすると、しきい値が下がってしまう。逆に小さくすると、ずらし量パラメータや変形パラメータを小さくしなければ、見落としが発生してしまうことになり、上で述べたような指針からは外れたことになる。
【００９７】
（Ｓ７）画像蓄積ステップ
画像蓄積は、テンプレートマッチングを利用してパターンを抽出しようとする画像を蓄積する。この画像は未知であるが、ノイズ量は予め算定した範囲であることとする。この画像は、濃淡画像、カラー画像、または動画像の１枚であっても良い。利用するテンプレートマッチングで利用でき、テンプレートと比較できることのみが条件である。
【００９８】
（Ｓ８）類似パターン走査抽出ステップ
類似パターン走査抽出は、すでに設定された３パラメータを利用して、画像上をテンプレートを走査させ、パターンの類似を実際に判断する。ここでは、上記画像蓄積ステップで蓄積された画像から、テンプレートと直接比較できる形（すなわちサイズ、分解能、形状）の部分画像を切り出し、テンプレートと切り出した部分画像の照合を行う。
【００９９】
もし、照合の結果がしきい値以上であれば、テンプレートに類似したパターンが見つかったと結論する。この、比較を行う位置（切り出す場所）は、３パラメータ設定ステップで決定されたずらし量パラメータに従って、順次動かす。さらに上記３パラメータ設定ステップで設定した、変形パラメータ毎に変形も行っていく。
【０１００】
なお、以上までの処理は、テンプレートを１つとして説明したが、当然ながら複数のテンプレートを利用して、複数種類のパターンを抽出する場合にも、それぞれのテンプレート毎に同じ処理が適用できる。
【０１０１】
また、他の前処理によって類似パターンを走査させる場所を限定することも可能である。これは、例えば動画像において、移動した部分だけを処理対象にするなどの場合が考えられる。
【０１０２】
また、本発明は、図３に示した方法の一部又は全部の処理機能をプログラムとして構成してコンピュータを用いて実現することができる。
【図面の簡単な説明】
【０１０３】
【図１】本発明の実施形態を示すパラメータ設定装置のブロック構成図。
【図２】本発明の実施形態を示す画像パターン抽出装置のブロック構成図。
【図３】本発明の実施形態を示す画像パターン抽出方法のフローチャート。
【符号の説明】
【０１０４】
１  テンプレートマッチング法蓄積手段
２  ノイズ量算定手段
３  テンプレート蓄積手段
４  テンプレート特徴量計算手段
５  類似度評価値決定手段
６  ３パラメータ設定手段
７  画像蓄積手段
８  類似パターン走査抽出手段
【図１】
2006023976.tif 000017
【図２】
2006023976.tif 000018
【図３】
2006023976.tif 000019