(57)【特許請求の範囲】
【請求項１】
参照画像上から、テンプレート画像領域に類似する画像領域の位置を検出するテンプレートマッチング装置が行うテンプレートマッチング方法であって、
前記テンプレート画像領域に対する前記画像領域の類似度を疎な位置間隔で計算し、
前記類似度が計算されない位置における類似度を、前記計算された類似度から、複数の方向別に独立に求められる類似度の勾配を利用して推定し、
前記類似度推定値と、前記推定に利用する周囲の類似度との差又は前記類似度の勾配が、閾値を超えないように、前記類似度推定値の値域を制限し、
前記類似度の計算値もしくは推定値が小さい位置を、類似する画像領域の位置とすることを特徴とする、テンプレートマッチング方法。
【請求項２】
多段探索法にもとづいて類似画像領域の位置を段階的に絞り込むテンプレートマッチング方法であって、その最終段以前の探索段において、請求項１に記載のテンプレートマッチング方法で類似画像領域の位置を検出することを特徴とする、テンプレートマッチング方法。
【請求項３】
類似度を推定する位置から、前記近傍画像領域の位置を引くことで得られる推定方向ベクトルに対して、前記テンプレート画像領域を前記推定方向ベクトルと同じもしくは反対の方向に動かして得られる画像領域と、前記テンプレート画像から計算される類似度の大小をもとに、前記閾値を決定することを特徴とする、請求項１又は２に記載のテンプレートマッチング方法。
【請求項４】
前記類似度推定において、直線上に順に位置する５個の参照画像領域Ａ、Ｂ、Ｃ、Ｄ、Ｅに対して、前記画像領域Ａ、Ｂにおける類似度から、勾配連続性を仮定して外挿される補間値と、前記画像領域Ｄ、Ｅにおける類似度から、勾配連続性を仮定して外挿される補間値とから、前記位置Ｃにおける類似度を推定することを特徴とする、請求項１乃至３の何れか１項に記載のテンプレートマッチング方法。
【請求項５】
参照画像上から、テンプレート画像領域に類似する画像領域の位置を検出するテンプレートマッチング装置であって、
前記テンプレート画像領域に対する前記画像領域の類似度を疎な位置間隔で計算する手段と、
前記類似度が計算されない位置における類似度を、前記計算された類似度から、複数の方向別に独立に求められる類似度の勾配を利用して推定する手段と、
前記類似度推定値と、前記推定に利用する周囲の類似度との差又は前記類似度の勾配が、閾値を超えないように、前記類似度推定値の値域を制限する手段と、
前記類似度の計算値もしくは推定値が小さい位置を、類似する画像領域の位置とする手段と、
を備えることを特徴とする、テンプレートマッチング装置。
【請求項６】
多段探索法にもとづいて類似画像領域の位置を段階的に絞り込むテンプレートマッチング装置であって、その最終段以前の探索段において、請求項５に記載のテンプレートマッチング装置で類似画像領域の位置を検出することを特徴とする、テンプレートマッチング装置。
【請求項７】
類似度を推定する位置から、前記近傍画像領域の位置を引くことで得られる推定方向ベクトルに対して、前記テンプレート画像領域を前記推定方向ベクトルと同じもしくは反対の方向に動かして得られる画像領域と、前記テンプレート画像から計算される類似度の大小をもとに、前記閾値を決定する手段を備えることを特徴とする、請求項５又は６に記載のテンプレートマッチング装置。
【請求項８】
前記類似度推定において、直線上に順に位置する５個の参照画像領域Ａ、Ｂ、Ｃ、Ｄ、Ｅに対して、前記画像領域Ａ、Ｂにおける類似度から、勾配連続性を仮定して外挿される補間値と、前記画像領域Ｄ、Ｅにおける類似度から、勾配連続性を仮定して外挿される補間値とから、前記位置Ｃにおける類似度を推定する手段を備えることを特徴とする、請求項５乃至７の何れか１項に記載のテンプレートマッチング装置。
【請求項９】
参照画像上から、テンプレート画像領域に類似する画像領域の位置を検出するテンプレートマッチング方法をコンピュータに行なわせるためのプログラムを記録したコンピュータ読取り可能な記録媒体において、
前記方法では、
前記テンプレート画像領域に対する前記画像領域の類似度を疎な位置間隔で計算し、
前記類似度が計算されない位置における類似度を、前記計算された類似度から、複数の方向別に独立に求められる類似度の勾配を利用して推定し、
前記類似度推定値と、前記推定に利用する周囲の類似度との差又は前記類似度の勾配が、閾値を超えないように、前記類似度推定値の値域を制限し、
前記類似度の計算値もしくは推定値が小さい位置を、類似する画像領域の位置とすることを特徴とする記録媒体。
【請求項１０】
多段探索法にもとづいて類似画像領域の位置を段階的に絞り込むテンプレートマッチング方法をコンピュータに行なわせるためのプログラムを記録したコンピュータ読取り可能な記録媒体において、
前記方法では、
その最終段以前の探索段において、請求項９に記載の記録媒体に記録されたプログラムがコンピュータに行なわせるためのテンプレートマッチング方法で類似画像領域の位置を検出することを特徴とする、記録媒体。
【請求項１１】
前記方法において、
類似度を推定する位置から、前記近傍画像領域の位置を引くことで得られる推定方向ベクトルに対して、前記テンプレート画像領域を前記推定方向ベクトルと同じもしくは反対の方向に動かして得られる画像領域と、前記テンプレート画像から計算される類似度の大小をもとに、前記閾値を決定することを特徴とする、請求項９又は１０に記載の記録媒体。
【請求項１２】
前記方法において、
前記類似度推定において、直線上に順に位置する５個の参照画像領域Ａ、Ｂ、Ｃ、Ｄ、Ｅに対して、前記画像領域Ａ、Ｂにおける類似度から、勾配連続性を仮定して外挿される補間値と、前記画像領域Ｄ、Ｅにおける類似度から、勾配連続性を仮定して外挿される補間値とから、前記位置Ｃにおける類似度を推定することを特徴とする、請求項９乃至１１の何れか１項に記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、参照画像上からテンプレート画像領域に類似する画像領域の位置を検出するテンプレートマッチング方法及びその装置に関するものである。
【背景技術】
【０００２】
テンプレートマッチングは、テンプレート画像領域への相関が最も高い画像領域を参照画像上から検出する処理である。テンプレートマッチングは、類似画像検索や物体追跡、動画像符号化における動きベクトル検出処理等で利用されている。【０００３】
テンプレートマッチングの従来技術に関しては、非特許文献１の６章が詳しい。【０００４】
１．テンプレートマッチング手法として、マッチング候補となる参照画像上の部分領域（参照画像領域）とテンプレート画像との差異を表す類似度を定義し、類似度を最小化する参照画像領域を求める方法が一般的である。類似度としては、例えば、参照画像領域とテンプレート画像の各画素の信号値差分の平均値（MAD：Mean Absolute Difference）、信号値差分の２乗の平均値（MSE：Mean Square Error）などを用いる。【０００５】
このようなテンプレートマッチングの基本的な手法として、類似度を全候補に対して計算し、それを最小化する参照画像領域を検出する手法は、全探索法と呼ばれている。全探索法は、類似度を最小化する参照画像領域を誤りなく検出することが可能であるが、計算量の観点では非常に効率が悪い。【０００６】
テンプレートマッチングの計算量を効率良く削減する従来技術として、多段探索法あるいは粗密探索法と呼ばれる手法が広く使われている。これは、テンプレートマッチング処理を複数の段に分け、その１段目では、類似領域候補となる参照画像領域の位置を疎な間隔で間引いて評価することで画像領域を広く粗く探索し、２段目以降のマッチングでは、前段で選択された画像領域周辺のみを狭く細かく探索することで、段階的に類似領域候補を絞りこむ手法である。【０００７】
図２は多段探索法の一例を示す模式図である。図中の升目模様は、マッチング候補となる参照画像領域の座標を示している。この例では、テンプレートマッチング処理を２段階に分けて実行する。１段目では、図２において１でラベルされた参照画像領域の類似度を計算し、評価値を最小化する画像領域を類似画像領域として選択する。図２における丸で囲まれた１で示す参照画像領域が選択されたとすると、次の２段目では、図２において２でラベルされた参照画像領域の類似度を計算し、丸で囲まれた１および２でラベルされた参照画像領域の中で類似度を最小化するものを、類似画像領域として選択する。【０００８】
この例では、１５×１５＝２２５個の参照画像領域がマッチング候補となっているため、全探索法でマッチング処理を行うと２２５回の類似度計算が必要である。これを、多段探索法を利用することで、１段目で７×７＝４９回、２段目で８回、合計５７回まで削減することができる。【０００９】
なお、実用的には、多段探索法の計算量を更に削減するために、前の段のマッチングで、低解像度に縮小された参照画像とテンプレート画像を用いる方法が良く利用される。例えば、図１の例の１段目において、水平垂直ともに１／２に縮小された解像度を持つ画像を用いて類似度を計算すると、類似度計算１回の計算量が約１／４になるため、単純な多段探索法より計算量を削減可能である。【００１０】
しかしながら、多段探索法は、マッチングが精度良く行われる前提条件として、類似度が参照画像領域の位置に対して滑らかに変化する性質を仮定している。このため、細かい絵柄やエッジを多く含む画像、ノイズを多く含む画像を入力すると、この前提が成立せず、１段目のマッチングで類似度が小さくない画像領域を検出することがある。【００１１】
図３に誤検出例を示す。グラフはテンプレート画像と参照画像から得られる類似度を示している。この例では、類似度の極小点が２つ存在し、その右側が最も類似する正解の参照画像領域に対応する。左側の極小点は、右側に比べると類似性のあまりない局所的な最小点であるとする。この例に対し多段探索法を適用し、１段目マッチングにおける類似度計算を、折れ線内の大きい黒丸が示す位置だけに限定すると、局所的な最小点に過ぎない左側の極小点が誤って検出される。【００１２】
このような誤検出は、類似度の極小点が２つ以上存在し、最小点をとる類似度の計算が間引かれる場合に発生しやすい。特に、ＭＡＤのように、各画素の差分の合計を含む類似度を用いると、図３のように、極小点から少しはずれるだけで類似度が大きくなることが多いので、誤検出率が高くなる。【００１３】
このような検出誤りを防ぐためには、１段目で類似度を計算する参照画像領域の間隔を小さくするか、１段目で選択するマッチング画像領域を複数個にして、２段目で複数の画像領域周辺でマッチングを行うのが、本質的な対策である。しかしながら、類似度の計算回数が大きく増加するため、計算量の観点からは現実的でない。【００１４】
類似度計算の回数を増やさずに、１段目マッチングの精度を向上させる方法として、疎な位置間隔で計算された類似度から、間の位置における類似度を補間推定する方法が考えられている。例えば、非特許文献２のパラメトリックテンプレート法は、相関係数を２次形式の連続関数で表現して補間することで、多段探索の１段目の検出精度を向上させる。ただし、この手法は、類似度が相関係数に限定される制約がある。また、補間に必要な行列計算の負荷が問題になることもある。【００１５】
類似度を補間する方法として知られている、等角フィッティング、パラボラフィッティングと呼ばれる類似度の補間手法を、多段探索法の１段目で利用する方法も考えられる。等角補間とパラボラ補間は、計算された３点の類似度に対し、極小点を中心に対称な折れ線、もしくは対称な放物線を当てはめることで、３点間の類似度を連続に補間する（図１４）。これらは、入力画像の解像度よりも高い精度で位置推定を行う、サブピクセル推定と呼ばれる問題で使われており、一度、整数画素精度で類似画像の位置を求めた後に、その位置を高精度化するために利用されている（非特許文献３）。しかし、多段探索で誤検出が起こるような状況では、テンプレート画像のきめ細かさに対して類似度の計算間隔が不十分であったり、ノイズを多く含んでいたり、類似度が極小点で対称にならないことが多い。このような場合においても、局所最小解に落ち込むことの少ない類似度推定方法が必要である。
【非特許文献１】A Murat Tekalp, "Digital Video Processing," Prentice Hall PTR, 1995.
【非特許文献２】K. Tanaka, M. Sano, S. Ohara, M. Okudaira, "A parametric template method and its application to robust matching," in Proc. of IEEE Conference on Computer Vision and Pattern Recognition, 2000.
【非特許文献３】Masao Shimizu and Masatoshi Okutomi, "Significance and Attributes of Sub-Pixel Estimation on Area-Based Matching", Systems and Computers in Japan, Vol.34, No.12, pp.1-10, November 2003.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
前述したように、全探索法によるテンプレートマッチングは類似度計算に要する計算量が大きい。多段探索法を用いると、全探索法よりも計算量を削減することが可能であるが、細かい絵柄やエッジを多く含む画像、あるいはノイズを多く含む画像に対して、１段目マッチングで誤った画像領域を検出する問題がある。その誤検出を防ぐための類似度補間手法も十分な精度とは言えない。【００１７】
そこで、本発明の目的は、少ない計算量で高い検出精度を備えるテンプレートマッチング方法及びその装置を提供することにある。特に、多段探索法の１段目マッチングのように、類似度計算の位置間隔を疎にすることで計算量を削減する場合においても、計算されない位置における類似度を精度良く推定し、誤検出確率を小さく抑えるテンプレートマッチング方法及びその装置を提供することにある。
【課題を解決するための手段】
【００１８】
本発明によれば参照画像上から、テンプレート画像領域に類似する画像領域の位置を検出するテンプレートマッチング装置が行うテンプレートマッチング方法であって、前記テンプレート画像領域に対する前記画像領域の類似度を疎な位置間隔で計算し、前記類似度が計算されない位置における類似度を、前記計算された類似度から、複数の方向別に独立に求められる類似度の勾配を利用して推定し、前記類似度推定値と、前記推定に利用する周囲の類似度との差又は前記類似度の勾配が、閾値を超えないように、前記類似度推定値の値域を制限し、前記類似度の計算値もしくは推定値が小さい位置を、類似する画像領域の位置とすることを特徴とする、テンプレートマッチング方法が提供される。
【００２０】
本発明によれば、多段探索法にもとづいて類似画像領域の位置を段階的に絞り込むテンプレートマッチング方法であって、その最終段以前の探索段において、上記のテンプレートマッチング方法で類似画像領域の位置を検出することを特徴とする、テンプレートマッチング方法が提供される。【００２２】
上記のテンプレートマッチング方法において、類似度を推定する位置から、前記近傍画像領域の位置を引くことで得られる推定方向ベクトルに対して、前記テンプレート画像領域を前記推定方向ベクトルと同じもしくは反対の方向に動かして得られる画像領域と、前記テンプレート画像から計算される類似度の大小をもとに、前記閾値を決定するようにしてもよい。【００２３】
上記のテンプレートマッチング方法において、前記類似度推定において、直線上に順に位置する５個の参照画像領域Ａ、Ｂ、Ｃ、Ｄ、Ｅに対して、前記画像領域Ａ、Ｂにおける類似度から、勾配連続性を仮定して外挿される補間値と、前記画像領域Ｄ、Ｅにおける類似度から、勾配連続性を仮定して外挿される補間値とから、前記位置Ｃにおける類似度を推定することを特徴とするようにしてもよい。
【発明の効果】
【００２４】
本発明は、少ない計算量で検出精度の高いテンプレートマッチング方法を提供する効果がある。
【図面の簡単な説明】
【００２５】
【図１】本発明の類似度推定方法を説明する模式図
【図２】従来の多段探索法に基づくテンプレートマッチング手法を説明する模式図
【図３】従来の多段探索法の問題点と本発明の効果を示す模式図
【図４】テンプレート画像、参照画像、参照画像領域の関係を示す模式図
【図５】本発明の実施形態において参照画像領域を分類する方法の例を示す模式図
【図６】本発明の実施形態の構成を示すブロック図
【図７】本発明の実施形態の処理手順を示すシーケンス図
【図８】本発明の実施形態において類似度補間に用いる参照画像領域の位置を示す模式図
【図９】本発明の実施形態において丸め閾値計算の意味を説明する模式図
【図１０】本発明の実施例において参照画像領域を分類する方法を示す模式図
【図１１】本発明の実施例の構成を示すブロック図
【図１２】従来例と本発明の実施例の計算量比較を示す表
【図１３】本発明の実施例を動き推定処理に適用した結果を示すグラフ
【図１４】等角補間とパラボラ補間の例を示す図である。
【符号の説明】
【００２６】
６０１  参照画像記憶
６０２  テンプレート画像記憶
６０３  類似度計算
６０４  類似度最小化候補検出
６０５  丸め閾値決定
６０６  類似度推定
６０７  類似度記憶変数
【発明を実施するための最良の形態】
【００２７】
以下、図面を参照して本発明を実施するための最良の形態について詳細に説明する。【００２８】
＜実施形態１＞
本発明の第１実施形態を説明する。図４は、説明に用いる関数、変数、座標の関係を示したものである。Ｓ（ｉ，ｊ）はテンプレート画像、Ｗ（ｉ，ｊ）は参照画像を示す。（ｉ，ｊ）は画像内の座標であり、この実施形態では整数値をとるとする。マッチング候補となる参照画像領域の位置を、参照画像Ｗ（ｉ，ｊ）内の座標（ｕ，ｖ）で表す。この実施形態で、（ｕ，ｖ）は整数値をとるとする。【００２９】
［マッチング評価基準］
テンプレート画像と、参照画像領域（ｕ，ｖ）の類似度をｅ（ｕ，ｖ）で表す。ｅ（ｕ，ｖ）は、ｅ（ｕ，ｖ）が小さいほど参照画像領域（ｕ，ｖ）がテンプレート画像に類似していることを示すとする。本実施形態におけるテンプレートマッチングは、ｅ  （ｕ，ｖ）が小さい参照画像領域  （ｕ，ｖ）を検出する処理である。【００３０】
数式１に示すｅ  ＭＡＤ（ｕ，  ｖ）は、類似度ｅ  （ｕ，ｖ）の具体例である。ｅ  ＭＡＤ  （ｕ，ｖ）は、２画像領域間の距離を画素信号の差分絶対値平均で表した量であり、ＭＡＤ（Ｍｅａｎ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ）と呼ばれる。数式１において、集合Ｒは平均をとる画素の集合を示し、｜Ｒ｜は集合Ｒの要素数を表す。
【数１】
0004404095.tif 000002
【００３１】
［マッチング処理の概要］
一般にｅ  （ｕ，  ｖ）の計算は、Ｒに含まれる画素の個数分のだけ差分計算を要するため、これを何回も繰り返すと計算量が大きくなる。そこで本発明では、マッチング候補として与えられた参照画像領域の一部に対してのみ、類似度ｅ  （ｕ，ｖ）  を計算することで、マッチング処理の計算量を削減する。その代わり、類似度の計算を省略した位置に関しては、計算された類似度から補間することで推定し、検出精度の低下を防ぐ。【００３２】
説明のため、参照画像領域（ｕ，ｖ）の類似度を周囲の類似度から推定した結果をｅｓｔｉｍａｔｅ＿ｅ（ｕ，ｖ）で表す。類似度ｅ（ｕ，ｖ）を、計算して得られた結果もしくは推定して得られた結果をｃａｌｃ＿ｅ（ｕ，ｖ）で表す。【００３３】
類似度を実際に計算する参照画像領域  （ｕ，ｖ）の集合を、Ｇ（１）で表す。類似度を計算せずに推定する参照画像領域  （ｕ，ｖ）を、推定処理の実行順で番号付けられた  （Ｋ−１）個の集合Ｇ（２），Ｇ（３），  …，  Ｇ（Ｋ）に分類する。このとき、同一の集合Ｇ（ｋ）に属する参照画像領域（ｕ，ｖ）は、同じ方法で類似度の推定がなされるとする。【００３４】
類似度を計算する候補Ｇ（１）の選び方については様々な方法があるが、多段探索法の１段目マッチングと同様に、探索範囲内の参照画像領域を疎な密度で網羅できるように間引いて選ぶのが好適である。類似度を推定する候補の分類はＧ（２），  Ｇ（３），  …，  Ｇ（Ｋ）は、Ｇ（１）に属する画像領域との相対的な位置関係から決めるのが好適である。【００３５】
図５の（ａ），  （ｂ），  （ｃ）は、マッチング候補をＧ（１），  Ｇ（２），  …，  Ｇ（Ｋ）に分類する方法を例示した図である。図中の格子模様は参照画像領域の座標（ｕ，ｖ）を示し、格子１マスが座標１画素分に相当するとする。１とラベルされた参照画像領域（ｕ，ｖ）は、Ｇ（１）に属するとし、同様に２、３、４とラベルされた参照画像領域（ｕ，ｖ）は、Ｇ（２），  Ｇ（３），  Ｇ（４）に属するとする。数字が書かれていないマスに対応する画像領域はマッチング候補から除外する。【００３６】
図５（ａ）の例では、「１」とラベルされた領域が縦横２画間隔で配置されている。これらの「１」に対し類似度を計算する。次に、「１」と「１」に横方向で挟まれた「２」の類似度を推定し、「１」と「１」に縦方向で挟まれた「３」の類似度を推定し、最後に「４」の類似度を推定する。図５（ｂ）と  （ｃ）の例では、「１」とラベルされた領域が横２画間隔で配置されている。最初に「１」の類似度を計算し、次に「２」と書かれた残りの候補の類似度を推定する。【００３７】
図６は、第１実施形態におけるテンプレートマッチング方法を示すブロック図である。参照画像Ｗ（ｉ，ｊ）、テンプレートデータＳ（ｉ，ｊ）は、外部から画像記憶６０１、６０２に入力される。６０３は、Ｇ（１）に属するマッチング候補（ｕ，ｖ）の類似度ｅ（ｕ，ｖ）を計算し、得られた結果をｃａｌｃ＿ｅ（ｕ，ｖ）として配列記憶６０７に格納する。６０５は、テンプレート画像Ｓ（ｉ，ｊ）から補間値丸め用の閾値ｃｌｉｐ＿ｔｈｒｅｓｈ（ｄｕ，ｄｖ）を計算し、結果を６０６に供給する。６０６は、６０７に記憶された類似度ｃａｌｃ＿ｅ（ｕ，ｖ）と、６０５で計算された丸め閾値から、Ｇ（２），  …，  Ｇ（Ｋ）に属する（ｕ，ｖ）の類似度を推定し、結果ｅｓｔｉｍａｔｅ＿ｅ（ｕ，ｖ）をｃａｌｃ＿ｅ（ｕ，ｖ）として記憶６０７に格納する。６０３と６０６が出力するｃａｌｃ＿ｅ（ｕ，ｖ）は、６０４にも出力され、６０４はｃａｌｃ＿ｅ（ｕ，ｖ）を最小化する候補（ｕ＊，ｖ＊）を、テンプレートマッチングの検出結果として外部に出力する。【００３８】
第１実施形態におけるテンプレートマッチング処理の流れを示したのが、図７である。Ｓ７０１において、参照画像の集合Ｇ（１）に属する参照画像領域（ｕ，ｖ）に対し、類似度ｅ（ｕ，ｖ）を計算し、結果ｃａｌｃ＿ｅ（ｕ，ｖ）を記憶する。ｃａｌｃ＿ｅ（ｕ，ｖ）を最小化する（ｕ，ｖ）の検出も同時に行う。次にＳ７０２において、類似度の補間推定に用いる丸め閾値ｃｌｉｐ＿ｔｈｒｅｓｈ（ｄｕ，ｄｖ）を計算し、結果を変数に記憶する。Ｓ７０３からＳ７０５において、Ｇ（１），  Ｇ（２），  …，  Ｇ（Ｋ）に属する（ｕ，ｖ）の類似度推定を順番に行い、推定結果ｅｓｔｉｍａｔｅ＿ｅ（ｕ，ｖ）をｃａｌｃ＿ｅ（ｕ，ｖ）として記憶する。同時に、ｃａｌｃ＿ｅ（ｕ，ｖ）を最小化する（ｕ，ｖ）の検出も同時に行い、Ｓ７０６で、最終的に得られた  （ｕ，ｖ）をマッチング結果として出力する。【００３９】
［類似度推定］
類似度の推定方法を説明する。図３のように、テンプレート画像と参照画像から計算される類似度に局所最小値が存在し、かつ、最類似画像における類似度計算が間引かれた場合でも誤検出が生じないように、精度よく推定することが必要である。このとき問題になるのは、極小点付近で類似度が急激に変化することである。極小点から見て左側と右側では、類似度が異なる勾配を持つために、線形補間やスプライン補間など、曲線の滑らかさを仮定する補間方法では、効果的な推定が難しい。【００４０】
そこで本発明は、推定される点から見て異なる方向に位置する画像領域の類似度からは、別々に補間を行うことで、極小点における勾配不連続性の問題を回避する。より具体的には、複数の方向から独立に求められる類似度の勾配を利用して、補間値もしくは補間曲線を外挿する手順と、得られた複数の補間結果を組み合わせて最終的な推定値を決定する手順の２段階で類似度推定を行うことで、検出精度を高める。ここで、複数の方向とは、左、右、上、下などの片方向を指す。左側と右側での勾配の対象性は仮定しない。それぞれの方向別の補間処理では、類似度の勾配が滑らかに変化するとして、線形補間やスプライン補間など一般的な手法で補間する。【００４１】
例えば、図３において、大きい黒丸が付いていない点の類似度を、各点からみて左側に位置する黒丸の類似度と、右側に位置する黒丸の類似度とから別々に補間曲線を求め、得られた２つの補間曲線の交点を類似度推定値とする。これにより、右側の極小点の類似度の推定値は、左側の類似度よりも小さくなり、類似度計算の間引きによる誤検出を生じなくすることができる。【００４２】
以下に、類似度推定の手順を詳細に説明する。本発明では、参照画像領域（ｕ，ｖ）における類似度ｅ（ｕ，ｖ）の推定値ｅｓｔｉｍａｔｅ＿ｅ（ｕ，ｖ）を、（ｕ，ｖ）近傍における類似度の補間曲線、または（ｕ，ｖ）における補間値Ｉ（ｕ，ｖ；ｍ）をＭ個（Ｍ≧２）求める手順と、得られた補間曲線もしくは補間値Ｉ（ｕ，ｖ；ｍ）から推定値ｅｓｔｉｍａｔｅ＿ｅ（ｕ，ｖ）を求める手順の２段階で、決定する。ここで、ｍは補間曲線もしくは補間値に付けられた識別番号である。各々のＩ（ｕ，ｖ；ｍ）  （ｍ≦Ｍ）を生成するため使う補間値は、（ｕ，ｖ）から見て異なる方向に位置する参照画像領域の補間値であるとする。【００４３】
図８は具体例である。図において格子１マスが１画素に対応する。ここで、参照画像領域Ｐの類似度推定値ｅｓｔｉｍａｔｅ＿ｅ（Ｐ）は、まず、参照画像領域Ａ１１，  Ａ１２の類似度ｃａｌｃ＿ｅ（Ａ１１），  ｃａｌｃ＿ｅ（Ａ１２）  からＩ（Ｐ；１）を求め、次に、ｃａｌｃ＿ｅ（Ａ２１），  ｃａｌｃ＿ｅ（Ａ２２）からＩ（Ｐ；２）を求め、最後にＩ（Ｐ；１）とＩ（Ｐ；２）から、ｅ（Ｐ）の推定値ｅｓｔｉｍａｔｅ＿ｅ（Ｐ）を決定する。ここで、Ａ１１，  Ａ１２とＡ２１，  Ａ２２をＰから見たとき、その位置する方向はＡ１１，  Ａ１２とＡ２１，  Ａ２２で逆になっていることに注意する。【００４４】
参照画像領域Ｑの類似度推定は、Ｐの推定と同様である。参照画像領域Ｂ１１，  Ｂ１２の類似度からＩ（Ｑ；１）を計算し、次にＢ１１，  Ｂ１２と別の方向に位置するＢ２１，  Ｂ２２の類似度からＩ（Ｑ；２）を計算する。最後に、Ｉ（Ｑ；１）とＩ（Ｑ；２）から、ｅｓｔｉｍａｔｅ＿ｅ（Ｑ）を決定する。【００４５】
参照画像領域Ｒの類似度推定は、４個の補間値を計算する例である。Ｒの周囲に位置する８点を方向別に４組に分け、それぞれの２つの類似度からＲにおける類似度を補間する。具体的には、Ｉ（Ｒ；１）をＣ１１，  Ｃ１２の類似度から、Ｉ（Ｒ；２）をＣ２１，  Ｃ２２から、Ｉ（Ｒ；３）をＣ３１，  Ｃ３２から、Ｉ（Ｒ；４）をＣ４１，  Ｃ４２の類似度から補間する。このように求まった４つの補間値Ｉ（Ｒ；１），  Ｉ（Ｒ；２），  Ｉ（Ｒ；３），  Ｉ（Ｒ；４）から、最終的な推定値ｅｓｔｉｍａｔｅ＿ｅ（Ｒ）を決定する。【００４６】
（ｕ，ｖ）の類似度に対する個々の補間曲線もしくは補間値Ｉ（ｕ，ｖ；ｍ）は、（ｕ，ｖ）および補間に用いる参照画像領域が存在する領域内で、類似度ｅ（ｕ，ｖ）が連続かつ緩やかに変化する勾配を持つことを仮定して算出する。補間方法は、線形補間やスプライン補間など、連続関数を補間するために一般的に知られている手法を利用する。【００４７】
図１は、参照画像領域Ｐの類似度をＡ１１，Ａ１２，Ａ２１，Ａ２２の類似度から補間推定する方法の一例を示すグラフである。グラフにおいて、横軸は、参照画像領域の座標ｕを示し、縦軸は類似度を示す。黒丸は計算された類似度ｃａｌｃ＿ｅ（ｕ，ｖ）である。Ｉ（Ｐ；１）はＡ１１，  Ａ１２から線形補間した曲線であり、Ｉ（Ｐ；２）はＡ２１，  Ａ２２から線形補間で求めた曲線である。Ｉ（Ｐ；１；Ｐ）およびＩ（Ｐ；２；Ｐ）は２つの補間曲線がＰで取る値を示し、Ｉｉｓ（Ｐ）は２曲線の交点上の類似度を示す。【００４８】
具体例として、Ａ１２，Ａ１１，Ａ２１，Ａ２２が等間隔で配置され、かつＰがＡ１１とＡ２２の間の中央に位置する場合に、Ｉ（Ｐ；１；Ｐ）とＩ（Ｐ；２；Ｐ）は、数式２，３，４のようになる。数式４において（e2-e1）は、Ａ１２とＡ１１から求められる類似度の勾配である。これに、Ｐ−Ａ１１間の距離とＡ１１−Ａ１２間の距離の比１／２をかけたものをe1から引くことで、Ｐにおける左側からの補間値を決定している。位置間隔が異なる場合は、数式４の係数をＰ，Ａ１１，Ａ１２間の距離比に応じて変更する。
【数２】
0004404095.tif 000003
【数３】
0004404095.tif 000004
【数４】
0004404095.tif 000005
【００４９】
Ｐにおける類似度の推定値を、補間曲線Ｉ（Ｐ；１），  Ｉ（Ｐ；２）がＰ近傍でとる値から決定する。その方法も多様ではあるが、例えば、Ｉ（Ｐ；１；Ｐ）とＩ（Ｐ；２；Ｐ）の最大値Ｉｍａｘ（Ｐ）、最小値Ｉｍｉｎ（Ｐ）、平均値Ｉａｖｅ（Ｐ）を推定量とするのが一つの方法である。あるいは、Ｉｍａｘ（Ｐ）とＩｍｉｎ（Ｐ）の線形和Ｉｍｉｘ（Ｐ）で推定値を表現するのも一つの方法である。これらを、数式５から数式８に示す。
【数５】
0004404095.tif 000006
【数６】
0004404095.tif 000007
【数７】
0004404095.tif 000008
【数８】
0004404095.tif 000009
【００５０】
Ｐにおける補間値ではなく、Ｐに対し補間した２つの曲線の交点における類似度ＩＩＳ（Ｐ）を推定値とするのも一例である。具体例として、Ａ１２，Ａ１１，Ａ２１，Ａ２２が等間隔に位置する場合に、左右から線形補間した直線の交点を計算することで、数式９、１０で示す推定値が与えられる。
【数９】
0004404095.tif 000010
【数１０】
0004404095.tif 000011
【００５１】
図８のＲのように、４個の補間曲線Ｉ（Ｒ；１），  Ｉ（Ｒ；２），  Ｉ（Ｒ；３），  Ｉ（Ｒ；４）から推定値を決定する方法としては、例えば、４つの補間曲線のＰにおける値Ｉ（Ｒ；１）（Ｐ），  Ｉ（Ｒ；２）  （Ｐ），  Ｉ（Ｒ；３）  （Ｐ），  Ｉ（Ｒ；４）  （Ｐ）を値の大きい順に並び替えてＩｓｏｒｔ（Ｒ；１），  Ｉｓｏｒｔ  （Ｒ；２），  Ｉｓｏｒｔ  （Ｒ；３），  Ｉｓｏｒｔ  （Ｒ；４）とし、これら４つの値を比率（１−θ１−θ２−θ３）：θ１：θ２：θ３を線形和で混合したＩｍｉｘ（Ｒ）で表す方法がある（数式１１）。
【数１１】
0004404095.tif 000012
【００５２】
以上で説明したように、類似度推定を行うことで、図３に示すように類似度が複数の極小値を持ち、極小点付近で勾配が大きく変化する補間の難しい例でも、実際の値に近い推定が可能になるため、結果として、誤検出確率を小さくすることが可能である。【００５３】
［誤検出防止用の補間推定値丸め］
ノイズを含む画像を用いて計算された類似度から推定処理を行うと、誤検出確率が高まることがある。例えば、図１の例において、Ｐが類似度を最小値する参照画像領域ではないときに、Ａ１２とＡ１１における類似度の差がノイズの影響で大きくなると、Ｐにおける類似度が実際の値よりも小さく推定され、結果的にＰをマッチング領域として誤検出する確率が高まる。特に、この現象は、類似度変化が少ない平滑な画像で問題である。そこで、ノイズ混入による誤った推定を防ぐために、補間曲線の勾配に制約を加えて、極端に小さい補間値が出ないようにする。【００５４】
具体的には、参照画像領域Ｐにおけるｍ番目の補間曲線Ｉ（Ｐ；ｍ）に対し、その勾配を一定値以下に制約し、数式１２のＩ’（Ｐ；ｍ）を類似度補間に用いる。数式１２において、Ｉ（Ｐ；ｍ；Ｑ）は、Ｐの近傍に位置する参照画像領域Ｑにおける補間値を表す。Ａｍ１は補間に利用した近傍の参照画像領域とし、｜｜Ｑ−Ａ｜｜はＱ，  Ａ間の距離を示す。ｃｌｉｐ＿ｔｈｒｅｓｈ（Ｐ，  Ａｍ１）は、ｅ（Ａｍ１）とｅｓｔｉｍａｔｅ＿ｅ（Ｐ）の差分の上限値であり、これをＰＡｍ１間の距離｜｜Ｑ−Ａｍ１｜｜で割ったものが、勾配の上限である。
【数１２】
0004404095.tif 000013
【００５５】
マッチングを安定化させるために、複数個の補間曲線毎に勾配を制限するのではなく、最終的な推定値ｅｓｔｉｍａｔｅ＿ｅ（Ｐ）を丸める方法をとっても類似した効果が得られる。数式１３のｅｓｔｉｍａｔｅ＿ｅ’（Ｐ）は、その具体的表現である。数式１３において、Ｍは補間曲線の個数である。
【数１３】
0004404095.tif 000014
【００５６】
この丸め閾値ｃｌｉｐ＿ｔｈｒｅｓｈ（Ｐ，Ａ）には固定値を設定しても良いが、入力画像特性によって最適値が異なる。本実施形態では、以下の考察に基づいて丸め閾値を決定する。【００５７】
ｌｉｐ＿ｔｈｒｅｓｈ（Ｐ，Ａ）は、ｅ（Ａ）とｅ（Ｐ）の差分の最大値を示している。画像領域Ｐの類似度を推定する目的は、Ｐがテンプレート画像に類似するか検査するためであるから、画像領域Ｐがテンプレート画像に類似している場合に取り得るｅ（Ａ）とｅ（Ｐ）の差分を設定すると、マッチングを安定化できると考えられる。【００５８】
類似度ｅ（Ｐ）の定義を拡張し、テンプレート画像領域と同じ形状を持つ任意の画像領域Ｐと画像領域Ｑ間のマッチングを評価する量を定義し、ｅ（Ｐ，Ｑ）とする。（注釈：これは、本発明の考え方を示すために定義するものあるから、実際にｅ（Ｐ，Ｑ）を定義できなくても良い。）図９に、参照画像上の領域Ｐ、Ａおよびテンプレート画像Ｓの関係を示す。【００５９】
ｅ（Ｐ，Ｑ）は、画像領域間の距離とみなせるから、三角不等式より、数式１４の関係が成り立つ。ｅ（Ｓ，Ｐ），  ｅ（Ｓ，  Ａ）が類似度に等しいことを考慮すると、これは数式１５に変形できる。ここで、画像領域Ｐがテンプレート画像にマッチングする状況を仮定すると、ＰＡ間の距離ｅ（Ｐ，Ａ）は、テンプレート画像Ｓとテンプレート画像Ｓを補間方向（Ｐ→Ａ）にずらした画像Ｓ（Ａ−Ｐ）の間の距離ｅ（Ｓ，  Ｓ（Ａ−Ｐ））で近似できる。数式１６は、ｅ（Ｓ，Ｔ）がｅ（Ａ）とｅ（Ｐ）の差分の上限を近似的に与えることを示している。
【数１４】
0004404095.tif 000015
【数１５】
0004404095.tif 000016
【数１６】
0004404095.tif 000017
【００６０】
そこで本実施形態では、画像領域Ｐにおける類似度をＡからの補間する際の丸め閾値ｃｌｉｐ＿ｔｈｒｅｓｈ（Ｐ，Ａ）を、ＡからＰを引いた差分ベクトル（ｄｕ，ｄｖ）と同じ方向、もしくは反対方向に移動させたテンプレート画像と、テンプレート画像から計算される類似度をもとに決定する。【００６１】
図８のＰの補間では、例えば数式１７のように閾値を定める。λ０，λ１（＞０）は調整用のパラメータである。テンプレート画像を並行移動した領域Ｔ内の画素が部分的にしか取得できない場合は、計算可能な一部の画素からｅ（Ｓ，Ｔ）を求め、その値を定数倍するなどの方法で補正する。なお、ＳからＴへのテンプレート画像ずらし量は、ずらす方向が（ｄｕ，ｄｖ）と同じもしくは反対方向である限り、（ｄｕ，ｄｖ）に等しい必要はなく、この場合はＳとＴ間の距離とＰとＡ間の距離の比に応じてパラメータλ１を調整する。数式１８に示すｃｌｉｐ＿ｔｈｒｅｓｈ２は、類似度として数式１に示したｅＭＡＤを使用する場合の具体例である。
【数１７】
0004404095.tif 000018
【数１８】
0004404095.tif 000019
【００６２】
このような丸め閾値ｃｌｉｐ＿ｔｈｒｅｓｈは、補間方向ベクトル（ｄｕ，ｄｖ）とテンプレート画像Ｓ（ｉ，ｊ）の関数となっており、参照画像Ｗ（ｉ，ｊ）を式に含まない。このため、丸め閾値の計算は、テンプレートマッチング開始時に１回だけ実行するだけでよく、参照画像領域の位置を変える毎に再計算する必要はない。【００６３】
［まとめ］
以上、説明したように、本実施形態は、類似度の計算を疎な位置間隔で間引き、類似度が計算されない位置における類似度は周囲の参照画像領域に対する類似度から補間により推定することで、検出精度の低下を最小限に抑えながら計算量を削減する。【００６４】
このとき、類似度の勾配が極小点付近で大きく変化する性質を考慮して、補間点から見て複数の方向別に独立に求められる勾配を利用して補間曲線もしくは補間値を求め、得られた複数の補間結果から類似度を決定する手順で推定することで、誤検出確率を小さくしている。【００６５】
また、本実施形態は、テンプレート画像を補間方向と同じもしくは反対方向にずらした画像と、テンプレート画像の類似度の大小から前記丸め閾値を定め、類似度の補間値もしくは推定値の値域を、近傍の類似度から前記閾値を引いた値より下回らないように制限することで、入力画像へのノイズ混入による類似度推定誤りを防いでいる。【００６６】
本実施形態は、多段探索法に基づくテンプレートマッチングの１段目マッチングで用いると、計算量削減と検出精度の両立において、高い効果が得られる。例えば、１段目マッチングにおいて、図５（ａ）のＧ（１）に属する参照画像領域の類似度を計算する多段探索法と比較すると、本実施形態はＧ（２），  Ｇ（３），  Ｇ（４）の類似度を推定するため、類似画像領域の誤検出確率が小さくなる。従来の多段探索法に比べて増加する計算量は、類似度推定であるが、これは類似度を画像から正確に計算する場合の負荷に比べればわずかである。【００６７】
＜実施形態２＞
本発明の第２実施形態を説明する。第２実施形態におけるテンプレートマッチング方法は、計算量削減のため類似度計算に縮小画像を用いる点と、その結果類似度の定義と丸め閾値の計算方法が異なる点を除いて、第１実施形態と変わらない。よって、第１実施形態との差分のみを説明する。【００６８】
画像の縮小比率は、説明簡略化のため、縦横ともに１／２の縮小比率である場合だけを想定する。テンプレート画像Ｓ（ｉ，ｊ），  参照画像Ｗ（ｉ，ｊ）を縮小することで作成された画像を、Ｓ２（ｉ，ｊ），  Ｗ２（ｉ，ｊ）で表す。縮小後の座標（ｉ，ｊ）に対応する画素は、縮小前の座標（２ｉ，２ｊ）に対応するとする。【００６９】
テンプレート画像と参照画像領域（ｕ，ｖ）間の類似度を、第１実施例と同様にｅ（ｕ，ｖ）で表す。座標（ｕ，ｖ）は、縮小画像上の座標ではなく、縮小前の画像上の座標値を示すとする。本実施形態では、参照画像領域（ｕ，ｖ）の類似度を縮小画像Ｓ２（ｉ，ｊ），  Ｗ２（ｉ，ｊ）から計算する。数式１９におけるｅＭＡＤ２（２ｕ，２ｖ）は、ｅ（ｕ，ｖ）の一例である。ここで、ｕ，  ｖはともに偶数であるとし、Ｕもしくはｖが奇数の場合は定義しない。集合Ｒ２は、縮小されたテンプレート画像内で、差分を評価する画素の集合とする。
【数１９】
0004404095.tif 000020
【００７０】
類似度を計算する（ｕ，ｖ）と、類似度を補間推定する（ｕ，ｖ）の分類は、図５（ａ）のパタンとする。升目１マスは、縮小前画像における１画素に対応する。Ｇ（１）に属する（ｕ，ｖ）については、ｕもｖも偶数であり、数式１９のｅＭＡＤ２（ｕ，ｖ）が計算可能である。Ｇ（２），  Ｇ（３），Ｇ（４）が属する（ｕ，ｖ）については、本発明の推定手順に従って求めた類似度の値を、（ｕ，ｖ）における類似度ｅ（ｕ，ｖ）とみなすことにする。【００７１】
類似度の推定方法は関しては、類似度の定義の差異を除き、第１実施形態と同じ方法で推定するのが実施の一例である。また、別の例として、丸め閾値ｃｌｉｐ＿ｔｈｒｅｓｈ（ｄｕ，ｄｖ）を、縮小されたテンプレート画像Ｓ２（ｉ，ｊ）から計算してもよい。数式２０のｃｌｉｐ＿ｔｈｒｅｓｈ３に、その例を示す。ｃｌｉｐ＿ｔｈｒｅｓｈ３（ｄｕ，ｄｖ）は、縮小テンプレート画像を（ｄｕ，ｄｖ）だけずらした画像とテンプレート画像の差から計算されるが、縮小画像における（ｄｕ，ｄｖ）のずらし量は、縮小前画像において２倍になるため、得られた差分の平均を１／２倍する補正を行っている。
【数２０】
0004404095.tif 000021
【００７２】
以上説明した事項を除き、第２実施形態のテンプレートマッチング方法は、第１実施形態のマッチング方法と同じ手順に基づいて行われる。【００７３】
効果も第１実施形態と同様であるが、縮小画像を用いるため、第１実施形態に比較して類似度の計算量が小さくなる。本実施形態は、縮小画像を用いた多段テンプレートマッチングの１段目マッチングで用いると、効果的である。【００７４】
＜実施形態３＞
本発明の第３実施形態を、第１実施形態との差分を示す方法で説明する。【００７５】
第３実施形態におけるテンプレートマッチング方法は、０．５画素精度でマッチング画像領域を推定する。従って、第１実施形態と異なり、参照画像領域の座標（ｕ．ｖ）は０．５画素単位の値をとる。類似度は、例えば数式１に示すｅＭＡＤ（ｕ，ｖ）であるとする。参照画像Ｗ（ｉ，ｊ）を０．５画素単位で参照する必要があるが、これはテンプレートマッチングの使用目的に合わせ、適切な方法で内挿された画素を定義する。【００７６】
第３実施形態において、類似度を計算する（ｕ，ｖ）と、類似度を補間推定する（ｕ，ｖ）の分類は、図５（ａ）で示すパタンとする。ただし、第１実施例と異なり、格子１マスが１画素ではなく０．５画素分に相当するとし、Ｇ（１）に属する（ｕ，ｖ）が整数の座標値を持つとする。すなわち、本実施形態においては、ｕ，  ｖともに整数である参照画像領域に対し類似度を計算し、ｕ，ｖのどちらかに非整数の座標を持つ参照画像領域に対しては、類似度を補間推定する。【００７７】
類似度の推定方法は、丸め閾値ｃｌｉｐ＿ｔｈｒｅｓｈの計算を除き、第１実施形態と同じとする。ｃｌｉｐ＿ｔｈｒｅｓｈ（ｄｕ，ｄｖ）の計算については、数式１８のｃｌｉｐ＿ｔｈｒｅｓｈ２と同じ定義にもとづき計算するのが一つの方法である。このとき、（ｄｕ，ｄｖ）が整数未満の座標値であるため、テンプレート画像Ｓ（ｉ，ｊ）を０．５画素単位で参照する必要があるが、Ｗ（ｉ，ｊ）のと同様の方法でＳ（ｉ，ｊ）を内挿する。他の計算方法としては、数式２１のｃｌｉｐ＿ｔｈｒｅｓｈ４（ｄｕ，ｄｖ）のように、（ｄｕ，ｄｖ）を２倍することで、整数座標の画素を参照するように変更した計算式にもとづき、閾値を計算する。
【数２１】
0004404095.tif 000022
【００７８】
以上説明した事項を除き、第３実施形態のテンプレートマッチング方法は、第１実施形態のマッチング方法と同じ手順に基づいて行われる。【００７９】
本実施形態は、０．５画素精度のテンプレートマッチングを、１画素精度テンプレートマッチングと同じ、少ない類似度計算回数で実現でき、１画素精度で粗くテンプレートマッチングを行う方法に比較して、高い精度のマッチングが可能である。１段目で整数精度のマッチングを行い、２段目で０．５画素精度のマッチングを行うような、多段探索法の１段目マッチングに、本実施形態を適用すると、効果的である。
【実施例１】
【００８０】
本発明の第１実施例として、縮小画像を用いた２段の多段探索法に基づくテンプレートマッチング処理において、その１段目マッチング処理に、本発明にもとづくテンプレートマッチング方法を利用した実施例を説明する。【００８１】
本実施例において、テンプレート画像はＳ（ｉ，ｊ）１６×１６画素の矩形であり、座標ｉ，ｊの範囲は０以上１６未満の整数とする。参照画像Ｗ（ｉ，ｊ）は４８×４８画素の矩形であり、座標ｉ，ｊの範囲は−１６以上３２未満の整数とする。参照画像領域（ｕ，ｖ）の範囲は、ｕ，ｖともに−１６以上１６以下の整数であるとする。参照画像領域の個数は３３×３３＝１０８９個である。【００８２】
１段目マッチングでは、縦横１／２に縮小した８×８のテンプレート画像Ｓ２（ｉ，ｊ）と、同じ比率で縮小した２４×２４の参照画像を用いて、類似度を最小化する画像領域を検出する。図１０は、本実施例における参照画像領域（ｕ，ｖ）を格子模様のマス目で示した模式図である。この図において１とラベルされた参照画像領域に対し類似度が計算され、次に、２、３とラベルされた参照画像領域に対しては、類似度が補間推定される。【００８３】
具体的なマッチングの手順は、参照画像領域の分類が図１０に従う点を除き、第２実施形態で説明した方法と同様であるとする。類似度は、数式１９で定義されたものとする。集合Ｒ２には、８×８のテンプレート画像が含む画素全てが属するとする。類似度の補間は、図８の参照画像領域Ｐ，Ｑと同様の位置関係にある参照画像領域の類似度から行い、数式２、数式３、数式４、数式７で示した式に従って補間値を推定する。補間値の丸めは、数式１３および数式２０に従う。【００８４】
２段目ッチングでは、縮小前の画像を用いて類似度を正確に計算しながら、１段目で検出した画像領域の周辺を１画素おきに探索する。探索範囲は、１段目のマッチング結果からの差分が、縦横ともに−１以上１以下となる９点とする。類似度は数式１で定義されたものとする。【００８５】
図１１は本実施例の構成を示すブロック図である。１１０１に参照画像を、１１０２にテンプレート画像を入力する。入力された２つの画像は、１１０３で縦横１／２に縮小され、１１０４に縮小参照画像が、１１０５に縮小テンプレート画像が格納される。１１０６は、１１０４の縮小参照画像と１１０５の縮小テンプレート画像から１段目のテンプレートマッチング処理を行い、１１０７に検出された参照画像領域の座標（ｕ，ｖ）を出力する。１１０７は、１１０１の参照画像と１１０２のテンプレートが亜像から２段目のテンプレートマッチング処理を行い、最終的なマッチング結果を示す参照画像領域の座標（ｕ，ｖ）を外部に出力する。【００８６】
本実施例の効果を比較により示す。比較する方式としては、全探索法を適用した従来例Ａと、多段探索法にもとづく従来例Ｂを用意する。従来例Ｂは、本実施例と類似した手順でマッチングが行われ、本実施例とは１段目マッチング処理だけが異なる。従来例Ｂでは、１段目マッチングにおいて類似度の推定を行わず、図１０において「１」とラベルされた参照画像領域に対してのみ、類似度が計算される。【００８７】
計算量の比較を示す。テンプレートマッチングに要する計算量を、画素の差分計算の回数で集計した結果を図１２に示す。この集計において、縮小前画像による類似度計算１回あたり２５６回、縮小画像による類似度計算１回あたり６４回、縮小画像を用いた丸め閾値計算１回あたり６４回の差分計算が行われるとした。その他の評価値の推定処理、最小値検出処理や、画像縮小の計算量は含んでいない。この結果からは、本実施例は、多段探索法に基づく従来例２とほぼ変わらない計算量であり、全探索法に基づく従来例１に比較して１３分の１未満の計算量しか必要としないことが分かる。【００８８】
マッチング精度の実験により比較した結果を示す。本実施例、従来例Ａ、従来例Ｂのテンプレートマッチングの精度を比較するため、これらのテンプレートマッチング処理を動画像の動き推定に適用した。入力画像は７２０×４８０画素、毎秒３０フレーム、プログレッシブのモノクロ画像とし、１６×１６画素のブロック単位で類似度を最小化する画像ブロックを、時間的に１つ前のフレーム内から検出した。マッチング精度の評価するため、テンプレートマッチング処理で得られた類似度最小値をフレーム内で平均したものを指標として用いた。この指標が小さいほど、誤検出の少ないテンプレートマッチングが行われていることを示し、この指標が大きいと誤検出確率が高いことを示す。【００８９】
図１３は、評価動画像１３ＳＤ＿Ｃｈｕｒｃｈに対する動き推定から得られた類似度平均を示すグラフである。グラフ（ａ）は、各フレームの類似度平均を示したもので、横軸はフレーム番号を示す。いずれのフレームにおいても実施例Ａの類似度平均が最小となるが、それは全探索法であるゆえ誤検出確率が０になるからである。グラフからは、フレームにもよるが、従来例Ｂによる類似度平均の増大が大きいことが分かる。これに対し、本実施例は従来例Ａと大きく変わらない類似度平均を示している。【００９０】
図１３（ｂ）は、従来例Ａに対する本実施例と従来例Ａの類似度平均の比を示したグラフであり、本実施例と従来例Ａの類似度平均の差が顕著に読み取れる。従来例Ｂで、最大２５％程度増大していた類似度平均が、本実施例では５％程度まで抑えられている。このように、本実施例は、多段探索法にもとづく従来例Ｂに比較してマッチング精度が向上し、全探索法にもとづく従来例Ａに近いマッチング精度が得られている。【００９１】
以上示したように、本実施例では、多段探索法による従来例とほぼ変わらない計算量で、全探索法に近い精度のテンプレートマッチングを実現可能である。【００９２】
以上説明したように、テンプレート画像とマッチング参照画像領域間の類似度を、疎な位置間隔で間引かれた参照画像領域に限定して実行し、類似度が計算されない位置における類似度を、計算された類似度と推定された類似度から、複数の方向別に独立して求められる勾配を利用して推定するため、少ない計算量でマッチング処理を行えるとともに、従来の多段探索法では【００９３】
誤検出が生じるような類似度を持つ画像を入力した場合においても、誤検出の確率を防ぐことができる。【００９４】
さらに、前記類似度推定値と、前記推定に利用する周囲の類似度との差又は前記類似度の勾配が、閾値を超えないように、前記類似度推定値の値域を制限する。これにより、参照画像およびテンプレート画像にノイズ成分が加わった場合でも、ノイズに起因する補間推定の誤りを小さくし、マッチングの精度を高めることができる。【００９５】
前記近傍に位置する参照画像領域の座標から、前記補間対象の参照画像領域の座標を減じることで得られる補間方向ベクトル対して、前記閾値を一意に定義する。これにより、前記閾値を、補間方向ベクトル毎に１回だけ定めればよいため、参照画像領域の位置を変える毎に閾値を設定する必要がなくなり、必要な計算量が削減される。【００９６】
当該テンプレート画像領域を前記補間方向ベクトルと同じもしくは反対の方向に動かすことで得られる画像領域と、当該テンプレート画像領域との類似度を評価した値を元に、前記閾値を決定する。この方法で決定された閾値は、評価値勾配の大きさの上界を良く近似できるため、参照画像やテンプレート画像にノイズ成分が加わった場合でも、ノイズに起因するマッチング精度の低下を防ぐことができる。さらに、補間方向ベクトル別に閾値を設定しているため、水平方向と垂直方向で、その周波数特性が異なる画像信号が入力された場合でも、精度の高いマッチングを行うことができる。【００９７】
前記補間による類似度推定を、ある時点までに計算もしくは推定された類似度を、局所的に最小化する参照画像領域の近傍に位置する候補領域に対してのみ実行する。これにより、類似度の推定に必要な計算量を削減することができるので、本発明によるテンプレートマッチングの計算量を一層削減することが可能である。【００９８】
以上説明した方法は、コンピュータがプログラムを記録媒体から読み込んで実行することによっても実現することができる。
【図１】
0004404095.tif 000023
【図２】
0004404095.tif 000024
【図３】
0004404095.tif 000025
【図４】
0004404095.tif 000026
【図５】
0004404095.tif 000027
【図６】
0004404095.tif 000028
【図７】
0004404095.tif 000029
【図８】
0004404095.tif 000030
【図９】
0004404095.tif 000031
【図１０】
0004404095.tif 000032
【図１１】
0004404095.tif 000033
【図１２】
0004404095.tif 000034
【図１３】
0004404095.tif 000035
【図１４】
0004404095.tif 000036