(57)【要約】【課題】頑健で高精度かつ高速な画像間の対応点推定方法を提供すること【解決手段】変形前の画像上の注目点に対応する、変形後の画像上の対応点をテンプレートマッチングによって推定する。まず変形前の画像を複数の小領域に分割する。一つ以上の小領域を含む複数のテンプレートを作成し、変形後の画像に対し作成されたテンプレートを用いたテンプレートマッチングを行なって複数のマッチング点を求める。求められた複数のマッチング点を観測データとし、変形後の画像に対する、注目点を含む複数の小領域の変位を未知パラメータとし、該小領域の面積に比例した値を成分とする重みベクトルの各成分を各行の成分とする行列を観測行列として、一般線形回帰モデルの最小分散推定により複数の小領域の変位の推定値を得る。得られた推定値に基づいて対応点を推定する。【選択図】    図１
2004326688.tif 000002
【特許請求の範囲】
【請求項１】
変形前の画像上の注目点に対応する、変形後の画像上の対応点をテンプレートマッチングによって推定する対応点推定方法であって、
前記変形前の画像を複数の小領域に分割するステップと、
一つ以上の前記小領域を含むテンプレートを作成するステップと、
前記変形後の画像に対し前記テンプレートを用いたテンプレートマッチングを行なってマッチング点を求めるステップと、
前記マッチングステップにより得られた複数のマッチング点を観測データとし、前記変形後の画像に対する、前記注目点を含む前記複数の小領域の変位を未知パラメータとし、該小領域の面積に比例した値を成分とする重みベクトルの各成分を各行の成分とする行列を観測行列として、一般線形回帰モデルの最小分散推定により前記複数の小領域の変位の推定値を得るステップと、
前記推定値に基づいて前記対応点を推定するステップとを具備することを特徴とする対応点推定方法。
【請求項２】
前記複数の小領域の各々の変位は、変形前の該小領域内の各点の変位の平均値により定義されることを特徴とする請求項１に記載の方法。
【請求項３】
変形前の画像上の注目点に対応する、変形後の画像上の対応点をテンプレートマッチングによって推定する対応点推定方法であって、
前記変形前の画像を複数の小領域に分割するステップと、
一つ以上の前記小領域をそれぞれ含む複数のテンプレートを作成するステップと、
前記変形後の画像に対し前記複数のテンプレートをそれぞれを用いたテンプレートマッチングを行なって複数のマッチング点および正規化相関値を求めるステップと、
前記複数のテンプレートをフーリエ展開して得られるフーリエ係数をｘ方向に対する添え字ｊとｙ方向に対する添え字ｋで表すとともに、前記フーリエ係数の絶対値の２乗をｊ２で重み付けした和に２π２を掛けてｘ方向の周期の２乗で割った値をＡｘｘとし、前記フーリエ係数の絶対値の２乗をｋ２で重み付けした和に２π２を掛けてｙ方向の周期の２乗で割った値をＡｙｙとするとき、１から前記正規化相関値を引いた値に前記テンプレートの輝度分散を掛けて前記Ａｘｘと前記Ａｙｙの和で割った値からなるテンプレートマッチングの推定誤差分散値を計算するステップと、
前記推定誤差分散値の逆数で重み付けしたマッチング点の加重平均に基づいて前記対応点を推定するステップとを具備することを特徴とする対応点推定方法。
【請求項４】
前記対応点と前記マッチング点との間の距離と、前記推定誤差分散値の平方根との比が閾値よりも大きい場合に、該マッチング点が外れ値であると判定する外れ値判定ステップをさらに具備することを特徴とする請求項３に記載の方法。
【請求項５】
変形前の画像上の注目点に対応する、変形後の画像上の対応点を推定するテンプレートマッチングシステムであって、
前記変形前の画像を複数の小領域に分割する手段と、
一つ以上の前記小領域をそれぞれ含む複数のテンプレートを作成する手段と、
前記変形後の画像に対し前記複数のテンプレートをそれぞれを用いたテンプレートマッチングを行なって複数のマッチング点を求める手段と、
前記複数のマッチング点を観測データとし、前記変形後の画像に対する、前記注目点を含む前記複数の小領域の変位を未知パラメータとし、前記複数の小領域の面積に比例した値を成分とする重みベクトルの各成分を各行の成分とする行列を観測行列として、一般線形回帰モデルの最小分散推定により前記複数の小領域の変位の推定値を得る手段と、
前記推定値に基づいて前記対応点を推定する手段とを具備することを特徴とするテンプレートマッチングシステム。
【請求項６】
前記複数の小領域の各々の変位は、変形前の該小領域内の各点の変位の平均値により定義されることを特徴とする請求項５に記載のシステム。
【請求項７】
変形前の画像上の注目点に対応する、変形後の画像上の対応点を推定するテンプレートマッチングシステムであって、
前記変形前の画像を複数の小領域に分割する手段と、
一つ以上の前記小領域をそれぞれ含む複数のテンプレートを作成する手段と、前記変形後の画像に対し前記複数のテンプレートをそれぞれを用いたテンプレートマッチングを行なって複数のマッチング点および正規化相関値を求める手段と、
前記複数のテンプレートをフーリエ展開して得られるフーリエ係数をｘ方向に対する添え字ｊとｙ方向に対する添え字ｋで表すとともに、前記フーリエ係数の絶対値の２乗をｊ２で重み付けした和に２π２を掛けてｘ方向の周期の２乗で割った値をＡｘｘとし、前記フーリエ係数の絶対値の２乗をｋ２で重み付けした和に２π２を掛けてｙ方向の周期の２乗で割った値をＡｙｙとするとき、１から前記正規化相関値を引いた値に前記テンプレートの輝度分散を掛けて前記Ａｘｘと前記Ａｙｙの和で割った値からなるテンプレートマッチングの推定誤差分散値を計算する手段と、
前記推定誤差分散値の逆数で重み付けしたマッチング点の加重平均に基づいて前記対応点を推定する手段とを具備することを特徴とするテンプレートマッチングシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、変形前後の画像間の対応付けを、テンプレートマッチングを利用して頑健、高精度かつ高速に行う画像間の対応点推定方法に関する。また、同方法を用いたテンプレートマッチングシステムに関する。
【０００２】
【従来の技術】
画像に写る人物の顔（頭部）の位置や姿勢の自動認識技術は、様々な分野に応用可能である。例えば、セキュリティ技術における本人認証、運転者の不注意検知、エアバッグ作動の可否判定や、コンソール端末操作者のインターフェース向上、キーボードやマウスの操作に不自由を感じるユーザへの入力支援、ゲーム機器とのインターフェース、見物客への自動提示装置などが想定される。しかしながら、画像処理の対象としての人物の顔は、その動きと向きの多様性、表情変化による変形、照明変化、個人差などにより、非常に難しい認識対象であるとされている。
【０００３】
既に製品化されたある顔認識技術においては、画像から目鼻孔の４点を検出し、４点の座標を元に画像を正規化し、相互部分空間法などを用いて辞書との類似度を計算し、認識を行っている（例えば、非特許文献１、２参照。）。そのため、目鼻孔が隠れていなければ高精度で顔を検出し、登録されている人物であるかどうかを判別することができる。
【０００４】
しかしながら、目鼻の一部が背後に隠れるほど大きく横を向いた顔（頭部）の位置と姿勢を自動認識するためには、変形した画像として入力される顔特徴点を頑健かつ精度良く追跡する必要がある。これまで、多種多様な特徴点追跡方法が提案されてきた。特徴点の追跡問題は、単純化すると、２枚の画像（変形前画像と変形画像）間の対応点推定の問題として捉えられる。
【０００５】
いわゆるテンプレートマッチングによる対応点推定の従来技術には、以下のようなものがある。特許文献１に記載の技術は、対応点探索の精度向上を目的とし、各色成分毎にテンプレートマッチングを行い、誤差で重み付け処理して対応点を求めるものである。しかしながら、この従来技術はカラー画像にしか適用できない。
【０００６】
特許文献２に記載の技術は、テンプレートマッチングの際に、参照点周囲の画像情報を利用するものであり、最適な参照点、テンプレートサイズ、および解像度の選択を行う手法である。しかし、変形の大きさとマッチング類似度との定量的関係を導くには至っていない。
【０００７】
特許文献３に記載の技術は、画像の変形を滑らかな関数で近似し、２次元ＤＰで対応点の検出を行うものである。しかし、ＤＰは１次元において非常に効果的に機能するものの、２次元においては精度と計算コストの面で必ずしも有効な手法であるとは言えない。
【０００８】
特許文献４に記載の技術は、画像間の対応付けを高精度に行うために、変形テンプレートを用いるものである。しかし、計算時間と安定性の両者の観点で問題がある。変形をテンプレート類似度のみで推定しているため効率的でない。
【０００９】
特許文献５に記載の技術では、物体の自動抽出を行うためにテンプレートを変形させる方法を採用している。しかし、特許文献４と同様の問題がある。
【００１０】
特許文献６に記載の技術では、ブロックマッチングの正確さを向上させることを目的に、エッジ強度（マッチング強度）とローカルサポートを利用している。しかし、各種パラメタを経験的に決めなければならないため、ローカルサポートの最適利用は困難である。
【００１１】
特許文献７に記載の技術では、テンプレートマッチングによる対応点抽出精度の向上を目的とし、視差の分布が急峻に変化するところはテンプレートサイズを小さくするといったことを行っている。しかし、大きいサイズのテンプレートマッチングの情報を利用できない、最適サイズの設定が難しいなどの問題がある。
【００１２】
テンプレートマッチングによる対応点推定において変形画像を対象とする従来技術として以下のものがある。
【００１３】
ステレオ視における対応点推定を行う際のテンプレートマッチングのローカルサポートを統計的に論じた研究があり（非特許文献３乃至６参照。）、適応的にマッチングの窓幅を変えることで画像変形を克服しようとしている。しかしながら、変形量とマッチング結果との定量的関係を導くには至っていない。また、最適な窓幅を数値計算によって決定し、様々なサイズの窓幅によるマッチング結果のうち最適な一つを採用しており、採用されなかった窓幅のマッチング結果を活用できていない。
【００１４】
また、ステレオ視におけるマッチングウィンドウを、物体の局所勾配を利用してアフィン変形させて対応付けの精度を向上させることが行われている（非特許文献７参照。）。この研究では、変形画像に対するテンプレートマッチングを処理している。しかしながら、変形の大きさとマッチング結果との定量的関係を導くには至っておらず、採用されなかったアフィン変形のマッチング結果を活用できていない。
【００１５】
差の２乗和（ＳＳＤ：  Ｓｕｍ  ｏｆ  Ｓｑｕａｒｅｄ  Ｄｉｆｆｅｒｅｎｃｅ）を利用してテンプレートマッチングを行った場合に、誤りベクトルの分散・共分散行列の固有値の性質を利用して最適な特徴点を選択したり、テンプレート更新の判定を行う研究がある（非特許文献８参照。）。しかしながら、選択された特徴点を使う段階において、変形の大きさとマッチング結果との定量的関係を導くには至っておらず、大小サイズのテンプレートによるマッチング結果を活用することまではできていない。
【００１６】
また、最適な追跡ブロックをＦｉｓｈｅｒ情報行列の固有値に基づいて選択し、対象画像のアフィン変形モデルを仮定し、ロバスト推定でモデル推定と追跡をする方法が提案されている（非特許文献９参照。）。しかしながら、変形の大きさとマッチング結果との定量的関係を導くには至っておらず、大小サイズのテンプレートによるマッチング結果を活用することまではできていない。
【００１７】
非特許文献１０では、特徴点の位置精度と画像の共分散行列との関係を数値実験で検証している。そこでは、注目点近傍の自己残差を２次関数で近似し、ヘッセ行列を用いて表す。このとき、ヘッセ行列の逆行列が位置の不確定性を表す共分散行列であるとみなし、予め定めたノイズレベルσを用いてテンプレートマッチング結果の真値からのずれを正規分布で近似したとしている。画像の変形はノイズとして扱っている。基本的な考え方は、「残差曲面の曲率が大きいと移動により濃淡値が急激に変化するのでマッチングで位置を定め易い」というものだが、曲率の大きな画像が変形量が増えるに従い急激にマッチングを失敗し易くなる現象を旨く説明したり利用したりできない。
【００１８】
【特許文献１】
特開２００２−３５２２４１公報
【００１９】
【特許文献２】
特開２００２−２６９５５９公報
【００２０】
【特許文献３】
特開２００２−２６６１４４公報
【００２１】
【特許文献４】
特開２００１−１０９８７９公報
【００２２】
【特許文献５】
特開平１１−２３８１３８号公報
【００２３】
【特許文献６】
特開平１０−２５５０４９号公報
【００２４】
【特許文献７】
特開平９−２３１３５８号公報
【００２５】
【非特許文献１】
山口，福井，「顔向きや表情の変化にロバストな顔認識システム”Ｓｍａｒｔｆａｃｅ”」，電子情報通信学会論文誌，２００１年６月，第Ｊ８４−Ｄ−ＩＩ巻，第６号，ｐ．１０４５−１０５２
【００２６】
【非特許文献２】
福井，山口，「形状抽出とパターン照合の組合わせによる顔特徴点抽出」，電子情報通信学会論文誌，１９９７年８月，第Ｊ８０−Ｄ−ＩＩ巻，第８号，ｐ．２１７０−２１７７
【００２７】
【非特許文献３】
Ｍ．Ｏｋｕｔｏｍｉ  ａｎｄ  Ｔ．Ｋａｎａｄｅ，”Ａ  ｌｏｃａｌｌｙ  ａｄａｐｔｉｖｅ  ｗｉｎｄｏｗ  ｆｏｒ  ｓｉｇｎａｌ  ｍａｔｃｈｉｎｇ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ３ｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  （ＩＣＣＶ９０），（大阪），１９９０年，ｐ．１９０−１９９
【００２８】
【非特許文献４】
Ｍ．Ｏｋｕｔｏｍｉ  ａｎｄ  Ｔ．Ｋａｎａｄｅ，”Ａ  ｌｏｃａｌｌｙ  ａｄａｐｔｉｖｅ  ｗｉｎｄｏｗ  ｆｏｒ  ｓｉｇｎａｌ  ｍａｔｃｈｉｎｇ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，１９９２年，第７巻，第２号，ｐ．１４３−１６２
【００２９】
【非特許文献５】
Ｔ．Ｋａｎａｄｅ  ａｎｄ  Ｍ．Ｏｋｕｔｏｍｉ，”Ａ  ｓｔｅｒｅｏ  ｍａｔｃｈｉｎｇ  ａｌｇｏｒｉｔｈｍ  ｗｉｔｈ  ａｎ  ａｄａｐｔｉｖｅ  ｗｉｎｄｏｗ：  Ｔｈｅｏｒｙ  ａｎｄ  ｅｘｐｅｒｉｍｅｎｔ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １９９１  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒｏｂｏｔｉｃｓ  ａｎｄ  Ａｕｔｏｍａｔｉｏｎ，（Ｃａｌｉｆｏｒｎｉａ，  米国），１９９１年，ｐ．１０８８−１０９５
【００３０】
【非特許文献６】
Ｔ．Ｋａｎａｄｅ  ａｎｄ  Ｍ．Ｏｋｕｔｏｍｉ，”Ａ  ｓｔｅｒｅｏ  ｍａｔｃｈｉｎｇ  ａｌｇｏｒｉｔｈｍ  ｗｉｔｈ  ａｎ  ａｄａｐｔｉｖｅ  ｗｉｎｄｏｗ：  Ｔｈｅｏｒｙ  ａｎｄ  ｅｘｐｅｒｉｍｅｎｔ”，ＩＥＥＥ  Ｔｒａｎｓ．  Ｐａｔｔｅｒｎ  Ａｎａｌ．  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌ．，１９９４年，第１６巻，第９号，ｐ．９２０−９３２
【００３１】
【非特許文献７】
服部寛，「物体表面の勾配を考慮したステレオマッチング」，情報処理学会論文誌：コンピュータビジョンとイメージメディア，２００１年６月，第４２巻，第ＳＩＧ６（ＣＶＩＭ２）号，ｐ．２２−３２
【００３２】
【非特許文献８】
金子敏充，堀修，「テンプレートマッチングに適した追跡点選択手法」，電子情報通信学会技術研究報告，２００１年３月，第ＰＲＭＵ２０００−２２１号，ｐ．１４７−１５４
【００３３】
【非特許文献９】
金子敏充，堀修，「小領域のブロックマッチングを複数用いたロバストなオブジェクト追跡法」，電子情報通信学会論文誌，２００２年７月，第Ｊ８５−Ｄ−ＩＩ巻，第７号，ｐ．１１８８−１２００
【００３４】
【非特許文献１０】
金澤靖，金谷健一，「画像の特徴点に共分散行列は本当に必要か」，電子情報通信学会論文誌，２００２年２月，第Ｊ８５−Ａ巻，第２号，ｐ．２３１−２３９
【００３５】
【発明が解決しようとする課題】
本発明は、頑健で高精度かつ高速な画像間の対応点推定方法および同方法を用いたテンプレートマッチングシステムを提供することを目的とする。
【００３６】
【課題を解決するための手段】
一の観点に係る本発明の対応点推定方法は、変形前の画像上の注目点に対応する、変形後の画像上の対応点をテンプレートマッチングによって推定する対応点推定方法である。まず変形前の画像を複数の小領域に分割する。一つ以上の小領域を含むテンプレートを作成し、変形後の画像に対しテンプレートを用いたテンプレートマッチングを行なって複数のマッチング点を求める。求められた複数のマッチング点を観測データとし、変形後の画像に対する、注目点を含む複数の小領域の変位を未知パラメータとし、該小領域の面積に比例した値を成分とする重みベクトルの各成分を各行の成分とする行列を観測行列として、一般線形回帰モデルの最小分散推定により複数の小領域の変位の推定値を得る。得られた推定値に基づいて対応点を推定する。
【００３７】
他の観点に係る本発明の対応点推定方法は、変形前の画像上の注目点に対応する、変形後の画像上の対応点をテンプレートマッチングによって推定する対応点推定方法である。まず変形前の画像を複数の小領域に分割する。一つ以上の小領域をそれぞれ含む複数のテンプレートを作成し、変形後の画像に対し複数のテンプレートをそれぞれを用いたテンプレートマッチングを行なって複数のマッチング点および正規化相関値を求める。複数のテンプレートをフーリエ展開して得られるフーリエ係数をｘ方向に対する添え字ｊとｙ方向に対する添え字ｋで表すとともに、該フーリエ係数の絶対値の２乗をｊ２で重み付けした和に２π２を掛けてｘ方向の周期の２乗で割った値をＡｘｘとし、該フーリエ係数の絶対値の２乗をｋ２で重み付けした和に２π２を掛けてｙ方向の周期の２乗で割った値をＡｙｙとするとき、１から正規化相関値を引いた値にテンプレートの輝度分散を掛けてＡｘｘとＡｙｙの和で割った値からなるテンプレートマッチングの推定誤差分散値を計算する。この推定誤差分散値の逆数で重み付けしたマッチング点の加重平均に基づいて対応点を推定する。
【００３８】
【発明の実施の形態】
以下、図面を参照しながら本発明の実施形態を説明する。
【００３９】
まず画像の変形とテンプレートマッチングの相関値との定量的関係について説明し、次に重なりを許した複数のテンプレートマッチングの結果が満たさなければならない拘束式について説明する。かかる定量的関係および拘束式はいずれも本実施形態に深く係わる。
【００４０】
従来、テンプレートマッチングに用いるテンプレートは十分に小さいと考え、変形前画像のある画素（Ｘ，Ｙ）に対応する別フレームの真の対応点（Ｘ’，Ｙ’）は、テンプレートマッチングの結果得られる類似度最大点の座標（以下これを「マッチング点」と呼ぶ）で推定されるものと暗黙のうちに想定してきた。
【００４１】
これに対し本実施形態では、対応点とマッチング点とのずれを問題にし、両者を別物として扱う。テンプレートがある大きさを持つ領域とし、それに含まれるｎ個の微小領域の変位（ｄｉｓｐｌａｃｅｍｅｎｔ）ΔＸｉ（ｉ＝１，…，ｎ）を考える。この変位はオプティカルフローに相当する。対応点の変位のことを「対応点変位」とも呼ぶことにする。そして「対応点変位」を推定することを「対応点推定」と呼ぶことにする。
【００４２】
＜１次元画像の相関関数（有限区間）の解析＞これからまず最初に行おうとする解析は、図２における順問題の定式化である。テンプレート画像の行列Ａ、変位ΔＸｉ、変位の統計量（平均値ΔＸ￣、分散σΔＸ）、テンプレートの位置ｄなどによって、テンプレートマッチングの結果であるマッチング点ｄｍ、相関値Ｃがどのように表されるかということを導き出す。そして、その逆問題としての変形画像の対応点推定手法を導出する。
【００４３】
従来の考え方では、マッチング点が求まれば、その点によって対応点が求められるのでそれで十分と考える。しかし、大きさの異なる複数のテンプレートマッチングを組み合わせて対応点推定を行う本実施形態によれば、外れ値を効果的に検出したり、最適なテンプレートサイズを自動的に判定したり、効果的な正則化を行ったり、推定精度を見積もったり、テンプレートサイズよりも微細な精度で対応点推定を行うといったことが可能となる。
【００４４】
「外れ値」とは、一般的には、直観的にみて「他からずいぶん離れている」値のことであり、通常の処理方法では処理が困難であって、別扱いしなければならない値のことを言う。また、外れ値のことを「例外値」や「異常値」と言うこともある。特に、テンプレートマッチングに関して外れ値と言うときには、得られたマッチング点の座標値（ｘ，ｙ）が真の値から大きく外れているときに、その外れた座標値のことを言う。また、マッチング点座標値が外れ値であるとき、そのマッチング処理結果そのものを外れ値と言う場合もある。
【００４５】
本実施形態では、汎用的なテンプレートマッチングの外れ値の判定方法を提供する。画像にノイズや変形が加えられた場合に、マッチング点座標値の真の値からのずれ量がどうなりやすいかを、真の値を平均値とする正規分布で統計学的に表現する。そのとき、確率分布の広がりを表す分散共分散行列の値を基準にして、その正規分布では説明することが困難なほど平均値から離れた点にマッチング点が観測された場合に、外れ値であると判定する。単独のテンプレートマッチングの結果からは、平均値からのずれを見積もることができないが、本実施形態では複数のテンプレートマッチングの結果を有機的に組み合わせているのでこれが可能である。
【００４６】
＜画像が一様に拡大（縮小）したときの相関関数の解析＞ここでは説明の簡単の為、まず１次元画像の解析から始め、簡単な変形とみなせる拡大または縮小によって正規化相互相関がどのように減少し、マッチング点がどのように移動するかを解析する。このような解析を行う理由は、変形とテンプレートマッチングとの定量的関係を明らかにすることで、テンプレートマッチングの結果から変形を見積もることができ、さらには変形画像に対する高性能の対応点推定手法を導けるからである。また、近似を行う理由は、見通しがよい簡単な関係式を導くことで、その逆問題を解いてテンプレートマッチングの結果（相関値、マッチング点）から変形画像の振る舞いを予測するためである。
【００４７】
本明細書においては一貫してノイズは無い、或いは、ノイズは変形として扱うこととする。
【００４８】
座標ｘにおける輝度がＩ（ｘ）で与えられる、標本化と量子化を行う前のアナログ画像を対象とする。Ｉ（ｘ）に何らかの変形または平行移動が加えられた画像をＩ１（ｘ）とする。元の画像Ｉ（ｘ）の区間［Ｘ−ｈ，Ｘ＋ｈ］をテンプレートとしたとき、（アナログ画像の）Ｉ１（ｘ）に対する「相関関数」を式（１）で定義する。
【００４９】
【数１】
2004326688.tif 000003
Ｉ￣（ｘ）はＩ（ｘ）の複素共役を表すが、輝度の値は実数値であるので、Ｉ￣（ｘ）＝Ｉ（ｘ）である。
【００５０】
式（１）の相関関数はフーリエ解析における相関関数とは定義が若干異なる。相関関数は、これについて調べることで正規化相互相関と２乗残差和の両方を議論することができる便利な量である。
【００５１】
変形画像Ｉ１（ｘ）が、Ｉ（ｘ）をｘ＝Ｘを中心にｒ倍に拡大したもの（図３）であるとすると、Ｉ（ｘ）を用いて式（２）のように表される。
【００５２】
【数２】
2004326688.tif 000004
さらに、Ｉ（ｘ）をフーリエ級数に展開して、式（３）で表されるものとする。
【００５３】
【数３】
2004326688.tif 000005
Ｉ￣（ｘ）＝Ｉ（ｘ）よりｃ−ｋ＝ｃ￣ｋである。図３に示すように、テンプレートマッチングにおけるテンプレート重ね合わせ位置をｘＴとすると、式（１）、（２）、（３）から相関関数は、重ね合わせ位置ｘＴ、拡大中心Ｘ、テンプレート幅ｈ、拡大率ｒの関数として式（４）で表される。
【００５４】
【数４】
2004326688.tif 000006
＜一般の画像変形に対する相関関数＞一般の画像変形は、十分に多くの局所的な一様拡大（縮小）の組み合わせで表すことができる（図４）と考えられる。この場合の相関関数を式（５）で定義する。
【００５５】
【数５】
2004326688.tif 000007
元の位置を基準にしたテンプレートの重ね合わせ位置をｄ、個々の微小領域の変位（オプティカルフローに相当する）を式（６）で定義すると、各微小領域ｉの相関関数は、式（７）で近似することができる。
【００５６】
【数６】
2004326688.tif 000008
領域数がｎ個であるとすると、式（５）の相関関数は、式（８）、（９）のように計算することができる。式（９）をあらためてＲＩ２とおく。
【００５７】
【数７】
2004326688.tif 000009
マッチング点（ｄ＝ｄｍ）上で式（９）のＲＩ２が最大値を持つと考えると、式（１０）が成り立つが、そのためには式（１１）、（１２）が成立しなければならない。
【００５８】
【数８】
2004326688.tif 000010
式（１２）は１次元画像において成り立つ第１の重要な結果である。即ち、テンプレート内の任意の微小領域ｉの変位ΔＸｉの期待値がマッチング点変位ｄｍで与えられるのである。ｎ個の微小領域は互いに区別できないので、どの微小領域の変位もｄｍが推定値となる。
【００５９】
変位ΔＸｉの分散を式（１３）で定義すると、マッチング点上では式（９）は、式（１４）となり、ｄ≠ｄｍのときは、式（１５）が成り立つ。
【００６０】
【数９】
2004326688.tif 000011
相関関数Ｒと正規化相関Ｃとの関係は以下の式（１６）−（２０）で与えられる。
【００６１】
【数１０】
2004326688.tif 000012
したがって、式（１６）の正規化相関は、画像Ｉ（ｘ）が図４のような変形をした場合、式（２１）で近似的に表すことができる。
【００６２】
【数１１】
2004326688.tif 000013
式（２１）は１次元画像において成り立つ第２の重要な結果である。即ち、テンプレートマッチングの正規化相関は、テンプレート画像内の変位の分散σΔＸ２に比例して減少し、また、テンプレート重ね合わせ位置のマッチング点からのずれ量ｄ−ｄｍの２乗に比例して減少し、比例係数はフーリエ係数から計算される。変位の分散σΔＸ２は変形そのものであり、且つ、推定された対応点変位の推定精度でもある。要するに、相関値Ｃと、画像の特性と、変形の大きさと、対応点推定精度との関係式が導かれたことになる。
【００６３】
画像Ｉ（ｘ）のフーリエ係数は、式（２２）で計算する。有限フーリエ級数を用いることなく、積分を近似して求めているのは、フーリエ級数で再構成した画像がガタガタする（凸凹する）のを避けるためである。
【００６４】
【数１２】
2004326688.tif 000014
＜２次元画像の相関関数＞これまでに導出した１次元画像の変形と相関値との関係式を以下では２次元の場合に拡張する。
【００６５】
＜２次元画像の変形＞座標ｘ＝（ｘ，ｙ）Ｔにおける輝度がＩ（ｘ）＝Ｉ（ｘ，ｙ）で与えられるアナログ画像を対象とする。Ｉ（ｘ，ｙ）に何らかの変形または平行移動が加えられた画像をＩ１（ｘ，ｙ）とする。元の画像Ｉ（ｘ，ｙ）領域すなわちＸ−ｈｘ≦ｘ≦Ｘ＋ｈｘ、Ｙ−ｈｙ≦ｙ≦Ｙ＋ｈｙをテンプレートとしたとき、アナログ画像の「相関関数」を式（２３）で定義する。Ｉ￣（ｘ，ｙ）はＩ（ｘ，ｙ）の複素共役を表すが、輝度の値は実数値であるので、Ｉ￣（ｘ，ｙ）＝Ｉ（ｘ，ｙ）である。
【００６６】
【数１３】
2004326688.tif 000015
変形画像Ｉ１（ｘ，ｙ）が、Ｉ（ｘ，ｙ）を（ｘ，ｙ）Ｔを中心にｘ方向にｒ倍に、ｙ方向にｓ倍に拡大したものであるとすると、Ｉ（ｘ，ｙ）を用いて式（２４）で表される。
【００６７】
【数１４】
2004326688.tif 000016
さらに、Ｉ（ｘ，ｙ）をフーリエ級数に展開して、式（２５）で表されるものとする。
【００６８】
【数１５】
2004326688.tif 000017
Ｉ￣（ｘ，ｙ）＝Ｉ（ｘ，ｙ）よりＣ−ｋｘ，  −ｋｙ＝Ｃ￣ｋｘ，  ｋｙである。テンプレートマッチングにおけるテンプレート重ね合わせ位置をｘＴとすると、式（２３）、（２４）、（２５）から、２次元の相関関数は、式（２６）で表される。
【００６９】
【数１６】
2004326688.tif 000018
一般の画像変形は、回転による変形が無いものとすると、十分に多くの局所的な一様拡大（縮小）の組み合わせで表すことができると考えられる。相関関数は１次元の式（５）を拡張して式（２７）で定義する。ｎｘはｘ方向の微小領域分割数であり、ｎｙはｙ方向の微小領域分割数である。総微小領域数はｎ＝ｎｘｎｙとする。
【００７０】
【数１７】
2004326688.tif 000019
元の位置を基準にしたテンプレートの重ね合わせ位置をｄ、個々の微小領域ｉの変位を式（２８）で定義すると、各微小領域ｉの相関関数は式（２９）で近似することができる。
【００７１】
【数１８】
2004326688.tif 000020
式（２７）の相関関数は式（３０）、（３１）で表される。行列Ａを式（３２）で定義すると、式（３１）は式（３３）で表される。行列Ａは２乗残差曲面の曲率のようなものである。
【００７２】
【数１９】
2004326688.tif 000021
マッチング点（ｄ＝ｄｍ）上で式（３３）のＲＩ２が最大値を持つと考えると、式（３４）、（３５）が成り立つ。ゆえに、式（３６）が成り立つ。式（３６）は２次元画像において成り立つ第１の重要な結果であり、１次元画像の式（１２）に相当するものである。即ち、テンプレート内の任意の微小領域ｉの変位ΔＸｉの期待値（＝推定値）がマッチング点変位ｄｍで与えられるのである。ｎ個の微小領域は互いに区別できないので、どの微小領域の変位ΔＸｉに対してもｄｍが推定値となる。
【００７３】
【数２０】
2004326688.tif 000022
ΔＸｉの共分散行列を式（３７）で表し、行列Ａの成分を式（３８）で表すと、マッチング点上では式（３３）は、式（３９）で表される。式（３９）において（・，・）は行列の内積を表す。ＲＩ２をあらためてσΔＸの関数として式（４０）で表す。ｄ≠ｄｍのときは、式（４１）が成り立つ。
【００７４】
【数２１】
2004326688.tif 000023
さて、相関関数Ｒと正規化相関Ｃとの関係は式（４２）−（５１）で与えられる。式（４２）−（４６）はアナログ画像の場合である。
【００７５】
【数２２】
2004326688.tif 000024
式（４７）−（５１）はデジタル画像の場合である。
【００７６】
【数２３】
2004326688.tif 000025
したがって、式（４２）、（４７）の正規化相関は、局所的な回転の無い変形の場合、式（５２）のように近似的に表すことができる。
【００７７】
【数２４】
2004326688.tif 000026
式（５２）は２次元画像において成り立つ第２の重要な結果であり、１次元画像における式（２１）に相当するものである。即ち、テンプレートマッチングの正規化相関は、テンプレート画像内の変位の共分散行列σΔＸに比例して減少し、また、テンプレート重ね合わせ位置のマッチング点からのずれ量｜ｄ−ｄｍ｜の２乗に比例して減少し、比例係数は行列Ａを輝度分散σＩ２で正規化したもので与えられる。
【００７８】
変位の共分散行列σΔＸは変形そのものであり、且つ、対応点変位の推定値ｄｍ推定精度でもある。要するに、相関値Ｃと変形量と対応点推定精度との定量的関係が導かれたことになる。行列Ａはテンプレートマッチングにおけるテンプレートの特性を凝縮したものであり、ゆっくり変化する性質の画像の場合は小さく、細かく変化する性質の画像の場合は大きな値をとる。正規化相関を議論する場合はＡ／σＩ２大きさが重要となり、２乗残差（ＳＳＤ）を議論する場合はＡの大きさが重要となる。本明細書では、Ａ／σＩ２をテンプレート特性と称している。
【００７９】
一様拡大の場合のσΔＸ、式（５３）で計算できる。
【００８０】
【数２５】
2004326688.tif 000027
＜対応点推定の数値実験＞ここで、１つの画像モデルを設定し単体の相関マッチングの推定誤差を組み合わせた対応点推定の数値実験を行った結果を説明する。対象画像において同心の正方形を６つ設定し、６つの領域を考える（図５を参照）。ただし、変形モデルにΔＸ１￣＝ΔＸ２￣＝…＝ΔＸ６￣という制約を加える。
【００８１】
各テンプレート内の変位の分散は、等方的であると仮定して、各テンプレートの特性Ａから式（５４）、（５５）で計算を行う。ただし、画像を縮小してから式（５５）によって求めた値は、縮小前のスケールにおける値に戻すため、１／（縮小率）を掛ける必要がある。
【００８２】
【数２６】
2004326688.tif 000028
対応点の推定値は、マッチング点ｄｍｔ（ｔ＝１，…，６）を用いて、式（５６）で計算した。
【００８３】
【数２７】
2004326688.tif 000029
また、外れ値は２個と仮定し、全ての４個のマッチング結果の組み合わせによる式（５６）の計算を行い、判定誤差が最小となる組み合わせを選択した。その際の判定誤差は式（５７）で見積もった。
【００８４】
【数２８】
2004326688.tif 000030
この式（５７）は、マッチング結果の相関値Ｃと連動して式（５５）から推定される位置推定精度σｔのスケールに対して、相対的にそのマッチング点が推定対応点からどれだけ逸脱しているかを定量化している。このような方法により、ノイズだけの画像や相関値の小さいマッチング結果は外れ値になり易く、はっきりとしたコーナー点や相関値の大きいマッチング結果は重視するという効果を、経験的な調整パラメタ無しに取り込むことができた。
【００８５】
＜複数のテンプレートマッチングを組み合わせた対応点推定＞ここまでで明らかになった画像の変形と相関マッチングとの定量的関係を纏めると次のようになる。
【００８６】
・テンプレート内の任意の微小領域ｉ変位ΔＸｉ（オプティカルフローに相当）の推定値は、マッチング点変位ｄｍで与えられる（式（３６））。微小領域ｉはどれも等価なので、どの微小領域の変位ΔＸｉに対してもｄｍが推定値となる。
【００８７】
・正規化相関Ｃと、変位の共分散行列σΔＸと、テンプレート重ね合わせ位置のマッチング点からのずれ量ｄ−ｄｍとの間に成り立つ関係式が式（５２）で与えられる。この式におけるＡ／σＩ２はテンプレート画像の特性を表現し、画像のフーリエ係数から計算できる量、すなわちテンプレート特性である。輝度変化が細かい画像はテンプレート特性Ａ／σＩ２が大きくなり、少しの位置ずれや変形で相関値が減少してマッチングを失敗し易い。
【００８８】
・変位の共分散行列σΔＸは変形そのものであり、且つ、推定された対応点変位の推定値ｄｍの推定精度でもある。なお、σΔＸはいわゆる「画像の共分散行列」ではないことに注意すべきである。
【００８９】
これらの結果の活用方法は、まず、画像マッチングによる画像パターン探索を行う場合において、探索刻み幅や拡大率の変化刻み幅を見積もることである。例えば、テンプレート特性Ａ／σＩ２の成分の大きさが２倍になれば、探索刻みは１／２にする、などである。また、上述した対応点推定の数値実験のように精度情報を含んだ個々のテンプレートマッチングの結果を組み合わせることにより、テンプレートマッチング全体の性能を向上させることである。
【００９０】
発明者によるさらなる研究により、複数のテンプレートマッチングを有機的に組み合わせた対応点推定問題への応用可能性があることが判明した。我々は経験的に、顔画像の領域を追跡する場合に目鼻などを利用し、髪や頬は使わない。また、大きすぎず小さすぎず適度な大きさの領域を追跡している。このようなテンプレートの大きさと場所の選択を、これまでに得られた知識を用いて自動で最適化することができる。即ち、大小取り混ぜた複数のテンプレートマッチングを行い、それらの結果から対応点や変形をいくらでも高精度で逆算する手法が構築できる。
【００９１】
＜テンプレート内の変位ΔＸｉが満たす連立方程式＞本実施形態に係るモデルでは、テンプレートをある大きさを持った領域と考え、その中の微小領域ｉの振る舞いに着目する。このモデルは容易に、互いに重なりを有する複数のテンプレートを用いたテンプレートマッチングの解析方法へと拡張することができる。図６に示すように対象画像（１次元）をｎＡ個の小領域に分割する。各小領域ｉにはｎｉ個の微小領域があるものとする。小領域ｉの変位の平均ΔＸ￣ｉを式（５８）、（５９）で定義する。また、分散σΔＸｉ２を式（６０）で定義する。
【００９２】
【数２９】
2004326688.tif 000031
複数の小領域にまたがるｎＴ個のテンプレートを用いて相関マッチングを行う。テンプレートｔ（ｔ＝１，…，ｎＴ）内の微小領域ｊの変位をΔＺｔｊとおくと、ｔ内の変位の平均ΔＺ￣ｔと分散σΔＺｔ２は式（６１）−（６４）で計算される。ただし、テンプレートｔが小領域ｉを構成要素として含むときはｓｔｉ＝１とし、小領域ｉを含まないときはｓｔｉ＝０となるようにｓｔを設定する。例えば、図６のテンプレート（Ｔｅｍｐｌａｔｅ）２の場合は、ｓ２＝（１  １  ０  …  ０）Ｔとなる。
【００９３】
【数３０】
2004326688.tif 000032
上述の式（３６）によって、小領域内の変位の平均値ΔＸ￣がマッチング点ｄｍで与えられことが判明している。ここで、複数のテンプレートを用いた場合のこの定式化において式（３６）に対応する式は、ｄｍｔ＝ΔＺ￣ｔとなる。即ち、テンプレートｔによるテンプレートマッチングのマッチング点ｄｍｔによってテンプレートｔ内の微小領域の変位の平均値が推定される。
【００９４】
式（６１）、（６２）におけるΔＺ￣ｔとσΔＺｔ２は、相関マッチングのマッチング点変位ｄｍ，相関値Ｃと、式（３６）、（５２）で関係づけられている。したがって、この連立方程式は、画像変形の結果から決まる量ΔＸｉｊ、σΔＸｉ２から、マッチング点変位ｄｍと相関値Ｃを導く式となっている。これは図２における順問題のマルチテンプレート版である。
【００９５】
これの逆問題は、マッチング点変位ｄｍと相関値Ｃから、連立方程式（６１）−（６４）を用いて、ある点Ｘｉｊの変位の期待値ΔＸ￣ｉとその推定誤差σΔＸｉを求めることである。この連立方程式は、複数のテンプレートマッチングの結果が互いにつじつまが合い無矛盾（ｃｏｈｅｒｅｎｔ）でなければならないことを要請するものであり、変形画像に対するテンプレートマッチングの拘束式といえる。
【００９６】
２次元画像の場合の拘束式は、１次元の式（６１）−（６２）を拡張した式（６５）−（６８）で与えられる。
【００９７】
【数３１】
2004326688.tif 000033
＜実装上の工夫＞上述の連立方程式（６５）−（６８）によって対応点推定を行う場合に注意すべき点は、不良設定問題を回避することと、テンプレートマッチングの失敗への対処である。
【００９８】
不良設定問題は、ｎＴ＜ｎＡのときに生じる。これを回避するには、大小様々なテンプレートを用いてテンプレート個数ｎＴが多くなるようにするか、ΔＸ￣ｉ（ｉ＝１，…，ｎＡ）に滑らかさなどの制約を加える。
【００９９】
テンプレートマッチングが失敗すると、そのテンプレートｔに対応するΔＺ￣ｔとσΔＺｔは全く外れた値となり、他の対応点の推定精度にも悪影響を与える。これは、連立方程式（６５）−（６８）が対応点近傍の振る舞いを２次式で近似している為である。これを回避するには外れ値を除外する。ある観測値ΔＺ￣ｔが外れ値かどうか判定するのに、連立方程式（６６）が活用できる。因みに、顔の特徴点の追跡に対してＲＡＮＳＡＣと呼ばれる外れ値除去アルゴリズムが有効であることが判っており（例えば、参考文献「Ａ．Ｇｅｅ  ａｎｄ  Ｒ．Ｔ．Ｃｉｐｏｌｌａ，”Ｆａｓｔ  ｖｉｓｕａｌ  ｔｒａｃｋｉｎｇ  ｂｙ  ｔｅｍｐｏｒａｌ  ｃｏｎｓｅｎｓｕｓ”，Ｉｍａｇｅ  ａｎｄ  Ｖｉｓｉｏｎ  Ｃｏｍｐｕｔ．，１９９６年，第１４巻，ｐ．１０５−１１４」を参照）、外れ値処理は本実施形態の手法に限らず顔画像の特徴点追跡には必須である。
【０１００】
式（６５）と式（６６）を比べると、式（６５）は線形であり、σΔＺｔとσΔＸｉを含まないので、それ単独で解くことができる。そこで、まず式（６５）を用いてΔＸｉを求め、次にそれらの推定値を利用して式（６６）を解くという２段階の処理（あるいはそれらの反復計算）によってこの逆問題を数値計算で解くことができる。それぞれは線形の連立方程式であり、一般線形回帰モデルの解法が利用できる。
【０１０１】
式（６５）を、式（６９）−（７３）のように行列形式に書き直し、これに一般線形回帰モデル（カルマンフィルタの観測過程に相当）を当てはめる。
【０１０２】
【数３２】
2004326688.tif 000034
観測値ΔＺの誤差をｖ〜Ｎ（０，Ｒ）とし、未知パラメータΔＸがΔＸ〜Ｎ（Ｘ￣，Ｐ）に従うとすると、ΔＸの最小分散推定値は式（７４）で与えられる。
【０１０３】
【数３３】
2004326688.tif 000035
Ｒには相関マッチングにおける相関値から見積もられる位置精度を反映させ、Ｐには変形モデルの滑らかさの制約を反映させることで推定性能を向上させることができる。
【０１０４】
式（７４）は、大小様々に重なり合う複数のテンプレートマッチングの結果（ΔＺ）から、対応点変位（ΔＸ）を求める式となっている。参考文献（松尾淳，工藤博幸，「対応点探索問題の正則化のための多重解像度空間における確率的緩和法」，電子情報通信学会技術研究報告，２００２年１０月，第ＰＲＭＵ２００２−１０３号，ｐ．５−１０）によると、大小のテンプレートマッチングを利用した疎密探索において、疎から密ブロックへ確率を伝播させるモデルを用いて、疎領域のテンプレートマッチングに正則化の働きをさせることができるという。式（７４）による対応点推定においても、モデルに滑らかさの制約を陽に加えることなく、大小テンプレートを混ぜて推定することにより大きなテンプレートによるマッチング結果が正則化の効果を発揮する。
【０１０５】
＜本実施形態と上述の非特許文献１０との比較＞本実施形態では、画像の変形を考慮した相関関数を式（４１）で近似しており、これを用いるとアナログ画像の残差は式（７５）で与えられる。ここで、（・，・）は行列の内積である。画像のノイズは変形として扱っている。
【０１０６】
【数３４】
2004326688.tif 000036
さらに、変形無しσΔＸ＝０で、マッチング点座標をｄｍ＝０とすると、この残差はさらに簡単に書くことができ、例えば式（７６）で表される。
【０１０７】
【数３５】
2004326688.tif 000037
従って、式（３２）で与えられる行列Ａが上述の非特許文献１０に記載のヘッセ行列Ｈに相当する。ただし、画素（ｉ，ｊ）に対してではなく、ある大きさを持ったテンプレートに対してテンプレートの大きさに依存してその残差曲面の曲率がＡで表される。
【０１０８】
本実施形態における残差曲面の曲率の使い方（解釈）は、輝度の分散σＩ２で正規化したテンプレート特性Ａ／σＩ２の大きさを用いて正規化相関を表し、「テンプレート特性Ａ／σＩ２が大きいと僅かな位置ずれ（ｄ）や僅かな変形（σΔＸ）で相関値が大幅に減少し外れ値になり易い」とするものである。
【０１０９】
従来、テンプレートは十分に小さいと考え、対応点変位ΔＸｉとマッチング点変位ｄｍは暗黙のうちに同一視されていた。これに対し本実施形態では、対応点変位ΔＸｉとマッチング点変位ｄｍを別物として処理している。テンプレートがある大きさを持ったものと考え、テンプレート内の多くの微小領域毎の変位ΔＸｉを想定し、テンプレートマッチングによってそれらの期待値ΔＸ￣がマッチング点ｄｍで推定されると考えている。推定精度は曲率Ａの影響は受けるがむしろ、（推定精度）＝（テンプレート内変位の分散σΔＸ）＝（変形の大きさ）であると解釈し、テンプレートマッチングの結果として得られる相関値Ｃに依存して、式（５２）によって計算される。例えば、Ｃ＝１のときには、式（５２）から推定誤差は０となる。
【０１１０】
画像内の「空の一様なところ」や「白い壁」の扱い方に着目すると、本実施形態では、「空の一様なところ」は実は正規化することにより細かなノイズが拡大されてテンプレート特性Ａ／σＩ２が大きくなり、僅かな変形（σΔＸ）で相関値が大幅に減少し外れ値になり易いために、精度は期待できないと解釈される。これは、従来、「空の一様なところは輝度変化が少なくてヘッセ行列Ｈが小さく、共分散行列が大きくなるので、テンプレートマッチングの精度は低い」という解釈を行っていたことと比べて、同じ「精度は低い」という解釈でも両者で考え方が異なる。
【０１１１】
本実施形態に係る解析方法は、機能面で考察すると、マッチング結果の類似度（相関値、２乗残差）と精度との定量的関係が導かれ、変形による類似度変化の定量的予測も可能であるという点で優れている。
【０１１２】
図１は本発明の一実施形態に係るテンプレートマッチングシステムの概略構成を示すブロック図、図７は同実施形態に係るテンプレートマッチング処理の一例を示す流れ図である。本実施形態に係るテンプレートマッチングシステム１は変形画像に対するテンプレートマッチングを実行する。
【０１１３】
テンプレートマッチングシステム１は、変形前画像入力部２、注目点入力部３、変形画像入力部６、領域分割設定部１１、テンプレート設定部４、テンプレート特性計算部５、マッチング処理部７、変位計算部８、変位分散計算部９、外れ値判定部１０から構成されている。このテンプレートマッチングシステム１は変形前画像と変形画像が入力されると、２つの画像中の注目点の対応点または全画素の対応関係を計算し、推定対応点と推定誤差を出力する。注目点情報は、それが入力されれば注目点に関する推定対応点を出力し、入力されなければ全画素或いは予め設定された座標値に対して推定対応点を出力する。
【０１１４】
変形前画像入力部２は、変形前画像を受け取り、テンプレート設定部４に画像を送る。
【０１１５】
注目点入力部３は、注目点情報が入力された場合はそれを受け取り、テンプレート設定部４に注目点の座標値や要求精度などの情報を送る。
【０１１６】
テンプレート設定部４は、変形前画像入力部２から変形前画像を受け取り、注目点入力部３から注目点情報を受け取り、必要な複数のテンプレートを設定し、設定情報をテンプレート特性計算部５に送る。
【０１１７】
テンプレート特性計算部５は、設定されたテンプレートに関して変形前画像を利用してテンプレート特性Ａ／σＩ２を計算し、テンプレート設定情報とともにマッチング処理部７に送る。
【０１１８】
変形画像入力部６は、変形画像を受け取り、マッチング処理部７に変形画像を送る。
【０１１９】
マッチング処理部７は、テンプレート特性計算部５からテンプレート設定情報とテンプレート特性を受け取り、変形画像入力部６から変形画像を受け取り、外れ値判定部１０から外れ値情報を受け取り、必要ならば外れ値に該当するテンプレートを除外して、これらの情報を利用してテンプレートマッチング処理を行い、マッチング点やマッチングの類似度（正規化相互相関Ｃ）などのマッチング結果情報を変位計算部８へ送る。
【０１２０】
変位計算部８は、式（７４）を用いて変位の推定値ΔＸ＾を計算し、計算結果を変位分散計算部９と外れ値判定部１０へ送る。
【０１２１】
変位分散計算部９は、変位計算部８から変位の推定値ΔＸ＾を受け取り、外れ値判定部１０から外れ値情報を受け取り、式（６６）を用いて変位の分散σΔＸｉを計算し、計算結果を変位計算部８と外れ値判定部１０へ送る。
【０１２２】
外れ値判定部１０は、変位計算部８から変位の推定値ΔＸ＾を受け取り、変位分散計算部９から変位の分散σΔＸｉを受け取り、それらの首尾一貫性により、外れ値を判定し、判定結果を変位計算部８と変位分散計算部９とマッチング処理部７に送る。
【０１２３】
領域分割設定部１１は、変形前画像入力部２から変形前画像を受け取り、注目点入力部３から注目点情報を受け取り、変形前の画像の一部或いは全部を複数個の小領域に分割し、変形前画像と注目点情報と小領域分割設定情報をテンプレート設定部４に送る。小領域への分割の仕方は、注目点情報に従う。注目点を含む画像の部分を注目点の対応点が精度よく求められるように、注目点周辺は密に分割し、注目点から離れた部分は疎に分割するか、あるいは小領域を割り当てないようにすることもできる。例えば、図８に示すようにテンプレートｔより小さい面積の小領域ｉを設定し、注目点が中心になるように、図９に示すように３×３＝９個の小領域を設定する。このとき、これら９個の小領域の外側の部分は小領域に割り当てられない部分となる。注目点が画像全体のときや注目点が明示的に与えられない場合には、画像全体をカバーするように多くの小領域を全体に割り当てる。
【０１２４】
テンプレート設定部４は、領域分割設定部１１から変形前画像と注目点情報と小領域分割設定情報を受け取り、必要なｎＴ個のテンプレートを設定し、小領域分割設定情報とテンプレート設定情報をテンプレート特性計算部５に送る。テンプレートは１つ以上の小領域から構成され、大小取り混ぜて互いにその一部が重なり合うように設定する。テンプレートの設定では、不良設定問題が生じないように、小領域数ｎＡよりもテンプレート数ｎＴが大きくなるようにする。例えば、図８に示すように小領域ｉより大きい面積のテンプレートｔを設定し、図９に示すように４つの小領域から構成されるようなテンプレートは４つ設定することができる。他に、１個の小領域から構成される小さいテンプレートを９つ設定し、これら９つの小領域から構成される大きなテンプレートを１つ設定することで、合計１４個のテンプレートを設定することができる。
【０１２５】
テンプレート特性計算部５は、設定されたテンプレートに関してテンプレート特性Ａ／σＩ２を計算し、小領域分割設定情報とテンプレート設定情報とテンプレート特性をマッチング処理部７に送る。テンプレート特性Ａ／σＩ２は、行列Ａをテンプレートの画像の輝度分散σＩ２で割ったものであり、行列Ａは式（３２）を利用して計算され、輝度分散σＩ２は式（５０）を利用して計算される。行列Ａの計算はテンプレートをフーリエ級数に展開して求めたフーリエ係数を利用する。
【０１２６】
変形画像入力部６は、変形画像を受け取り、マッチング処理部７に変形画像を送る。
【０１２７】
マッチング処理部７は、テンプレート特性計算部５から小領域分割設定情報とテンプレート設定情報とテンプレート特性を受け取り、変形画像入力部６から変形画像を受け取り、外れ値判定部１０から外れ値情報を受け取り、必要ならば外れ値に該当するテンプレートを除外して、これらの情報を利用してテンプレートマッチング処理を行い、マッチング点やマッチングの類似度（正規化相互相関Ｃ）などのマッチング結果情報を、小領域分割設定情報とテンプレート設定情報とテンプレート特性とともに変位計算部８へ送る。
【０１２８】
テンプレートマッチング処理における「マッチング」とは、同じサイズの２つの画像があるとき、両者を重ね合わせてその違いを見ることでそれらが同じものか否かを判断することをいう（例えば、「画像処理標準テキストブック編集委員会（編），画像処理標準テキストブック，画像情報教育振興協会（ＣＧ−ＡＲＴＳ），１９９７年」を参照）。なお「マッチング」を「照合」と称する場合もある。
【０１２９】
２つの画像の違いを測る尺度として例えば差の絶対値の和（ＳＡＤ：Ｓｕｍ  ｏｆ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ）や正規化相互相関や差の自乗和が用いられるが、マッチングの尺度が定義されるならば、用いられるテンプレートが元の画像そのままではなく変換されたものである場合もある。尺度を別の言葉で、「類似度」、「相違度」と呼ぶことがある。このとき、２つの画像の違いが小さいほど大きな値をとる場合は「類似度」、違いが小さいほど小さな値をとる場合は「相違度」と呼ぶ。
【０１３０】
システムに入力された画像がテンプレートより大きなサイズであり、比較すべき対象画像が、その画像中のどこに含まれているか予め分かっていない場合は、画像中をテンプレートを移動させながら両画像の類似度を調べていく。そして、最大類似度が、予め設定しておいた閾値よりも大きい場合に、テンプレートと同じものが最大類似度を与える位置に検出されたと判断する。最大類似度が、予め設定しておいた閾値よりも小さい場合は、入力された画像中にテンプレートと同じものは検出されなかったと判断する。
【０１３１】
テンプレートの画像サイズよりも大きな画像サイズの対象画像を検出することが必要な場合がある。そのときは、画像中をテンプレートを移動させることと同時に画像を縮小することを行ってマッチングをとる。例えば、顔を検出するための顔テンプレートの画像サイズが１５×１５で、画像中の顔領域のサイズが１００×１００である場合などである。この場合、画像を縮小率＝１５／１００で縮小する処理と画像中をテンプレートを移動させる処理との両方を行う。顔領域のサイズが予め分かっていない場合は、縮小率も変化させる必要があり、様々な縮小率の値についてマッチングをとる。テンプレートのサイズを画像中の対象領域のサイズよりも小さくすることで、計算機処理時間やメモリ量の節約になる。
【０１３２】
このようにしてテンプレートマッチングの処理により、テンプレートと同じものが画像中に存在するかどうか、存在するとすればその検出位置と大きさを知ることができる。存在すると判断された場合は「検出された」という。検出位置は、テンプレートと重ね合わせたときのテンプレートの中心位置や、テンプレートの左上隅、右下隅の位置など、その後の処理に便利な方法で表現する。
【０１３３】
変位計算部８は、式（７４）を用いて変位の推定値ΔＸ＾を計算し、変位情報を、小領域分割設定情報とテンプレート設定情報とテンプレート特性とともに変位分散計算部９と外れ値判定部１０へ送る。式（７４）を用いた変位の推定値ΔＸ＾の計算は、一般線形回帰モデルの最小分散推定の計算方法であり、ΔＸが平均ΔＸ￣、共分散行列Ｐの正規分布に従い、観測値（ここではテンプレートマッチングのマッチング点）ΔＺの誤差が平均値０、共分散行列Ｒの正規分布に従うと仮定している。ここでは、テンプレート特性と正規化相互相関Ｃを用いて式（５４）、（５５）で計算されるσΔＺｔを、Ｒの対角成分として代入し、ΔＸ￣＝０とし、Ｐはその分布の広がりが画像全体の広さと等しくなるように設定する。
【０１３４】
変位計算部８における変位計算方法として、上記の方法以外に、各テンプレートによる対応点推定を独立に行い、各推定誤差分散の逆数で重み付けしたマッチング点の加重平均を計算する方法を用いることもできる。この方法は、求めたい対応点の個数が少ない場合や計算時間を節約したい場合などに計算時間を短くする効果がある。
【０１３５】
変位分散計算部９は、変位計算部８から小領域分割設定情報とテンプレート設定情報とテンプレート特性と変位の推定値ΔＸ＾を受け取り、外れ値判定部１０から外れ値情報を受け取り、式（６６）を用いて変位の分散σΔＸｉを計算し、変位分散情報を、変位計算部８と外れ値判定部１０へ送る。さらに、小領域分割設定情報とテンプレート設定情報とテンプレート特性と変位の推定値ΔＸ＾を外れ値判定部１０へ送る。
【０１３６】
外れ値判定部１０は、変位計算部８から小領域分割設定情報とテンプレート設定情報とテンプレート特性と変位の推定値ΔＸ＾を受け取り、変位分散計算部９から変位の分散σΔＸｉを受け取り、それらの首尾一貫性により、外れ値を判定し、判定結果を変位計算部８と変位分散計算部９とマッチング処理部７に送る。外れ値の判定方法の一つは、全てのσΔＸｉが正値となることを確認することである。外れ値があると式（６６）において（ΔＺ￣ｔ−ΔＸ￣ｉ）が異常に大きな値を取り、その結果として負値のσΔＸｉが得られる。従って、ｎＴ個のマッチング結果のうち幾つかのデータを除外することにより全てのσΔＸｉが正値となるようなマッチング結果の組みあわせを求めることで外れ値が除去されたことを確認することができる。
【０１３７】
もう一つの外れ値の判定方法は、テンプレートｔのマッチング結果ΔＺ￣ｔを除外して求めたΔＸ￣ｉを用いて式（６５）でΔＺ￣ｔを計算し、この別々の方法で求めた２つのΔＺ￣ｔの差を利用する方法である。この差の絶対値を式（５４）、（５５）で計算されるσΔＺｔで割った値が１より著しく大きいときに外れ値であると判定することができる。
【０１３８】
図７は本実施形態におけるテンプレートマッチング処理手順を示す流れ図である。
【０１３９】
まず変形前画像を入力し、変形前画像入力部２が変形前画像をテンプレート設定部４へ送る（ＳＴ１）。次に、注目点情報の入力を行い、注目点入力部３が注目点情報をテンプレート設定部４へ送る（ＳＴ２）。次に、テンプレート設定部４は、受け取った変形前画像と注目点情報を元にテンプレートの設定を行い、その設定情報をテンプレート特性計算部５へ送る（ＳＴ３）。
【０１４０】
テンプレート特性計算部５は、テンプレート特性Ａ／σＩ２を計算する（ＳＴ４）。
【０１４１】
次に、テンプレートマッチングシステム１に入力された変形画像を変形画像入力部６がマッチング処理部７へ送る（ＳＴ５）。
【０１４２】
次に、マッチング処理部７がマッチング処理を行い（ＳＴ６）、その結果に基づき、変位計算部８が変位の推定値ΔＸ＾を計算し（ＳＴ７）、その結果に基づき変位分散計算部９が変位の分散σΔＸｉを計算し、計算結果を変位計算部８および外れ値判定部１０に送る（ＳＴ８）。
【０１４３】
ステップＳＴ９では、変位分散の整合性に基づき外れ値を判定し（ＳＴ９）、外れ値がある場合は、その外れ値情報を変位計算部８と変位分散計算部９とマッチング処理部７に送るとともにステップＳＴ１１に進む。外れ値が無い場合はステップＳＴ１２に進む（ＳＴ１０）。
【０１４４】
ステップＳＴ１１では、外れ値に対応するテンプレートに固有の識別子を付加し、以降の処理においてそれらのテンプレートを除外してマッチング処理と変位の計算を行うように設定をする。
【０１４５】
ステップＳＴ１２では、計算された推定対応点と推定誤差を出力し、テンプレートマッチング処理を終了する。
【０１４６】
以上説明した本発明の実施形態によれば、頑健で高精度かつ高速なテンプレートマッチングシステムおよび画像間の対応点推定方法を提供できる。本発明はモノクロ画像を処理対象とすることができる。また、画像の変形とマッチング類似度との定量的関係を導くようにし、一部重なりも許すマッチング結果を最適に活用していることから、線形計算により高速に対応付けが行える。また、経験的パラメタを用いることなくローカルサポートを利用でき、大きなサイズのテンプレートによるテンプレートマッチングの結果を有効活用できる。
【０１４７】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【０１４８】
【発明の効果】
以上説明したように本発明によれば、頑健で高精度かつ高速な画像間の対応点推定方法および同方法を用いたテンプレートマッチングシステムを提供できる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係るテンプレートマッチングシステムの概略構成を示すブロック図
【図２】同実施形態に係るテンプレートマッチングに内在する順問題と逆問題を説明する概念図
【図３】同実施形態に係る拡大した画像に対するテンプレートマッチングを説明する概念図
【図４】同実施形態に係る一般の変形画像に対するテンプレートマッチングを説明する概念図
【図５】同実施形態に係る複数のテンプレートの構成例を示す概念図
【図６】同実施形態に係る互いに重なりを許した複数のテンプレートによるテンプレートマッチングを説明する概念図
【図７】同実施形態に係るテンプレートマッチング処理の一例を示す流れ図
【図８】同実施形態に係る小領域ｉとテンプレートｔを説明する概念図
【図９】同実施形態に係る小領域分割とテンプレート設定を説明する概念図
【符号の説明】
１…テンプレートマッチングシステム、２…変形前画像入力部、３…注目点入力部、４…テンプレート設定部、５…テンプレート特性計算部、６…変形画像入力部、７…マッチング処理部、８…変位計算部、９…変位分散計算部、１０…外れ値判定部
【図１】
2004326688.tif 000038
【図２】
2004326688.tif 000039
【図３】
2004326688.tif 000040
【図４】
2004326688.tif 000041
【図５】
2004326688.tif 000042
【図６】
2004326688.tif 000043
【図７】
2004326688.tif 000044
【図８】
2004326688.tif 000045
【図９】
2004326688.tif 000046