(57)【特許請求の範囲】
【請求項１】
被探索画像ｆ中からテンプレート画像ｔのパターンを検出するテンプレートマッチング方法において、
前記被探索画像に含まれるノイズ分散値量Ｖfn、及び前記テンプレート画像に含まれるノイズ分散値量Ｖtnを推定し、
数式１に従い正規化相関値ｒを計算するテンプレートマッチング方法。
【数１】
0003817979.tif 000020
ただし、Ｖf は被検索画像ｆの分散値、Ｖt はテンプレート画像ｔの分散値、
Ｒftは被検索画像ｆとテンプレート画像ｔの相関値を表す。
【請求項２】
請求項１のテンプレートマッチング方法において、
前記被探索画像全体についてノイズ量の推定が行われるテンプレートマッチング方法。
【請求項３】
請求項１のテンプレートマッチング方法において、
前記被探索画像の予め定められた領域毎にノイズ量の推定が行われるテンプレートマッチング方法。
【請求項４】
被探索画像ｆ中からテンプレート画像ｔのパターンを検出するテンプレートマッチング方法において、
前記被探索画像ｆに含まれるノイズ量を低減した画像ｆ′、及び前記テンプレート画像ｔに含まれるノイズ量を低減した画像ｔ′を生成し、
数式２に従い正規化相関値ｒを計算するテンプレートマッチング方法。
【数２】
0003817979.tif 000021
ただし、Ｖf′はノイズ量を低減した被検索画像ｆ′の分散値、
Ｖt′はノイズ量と低減したテンプレート画像ｔ′の分散値、
Ｒftは被検索画像ｆとテンプレート画像ｔの相関値を表す。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ処理計算機の技術分野に属し、画像認識装置及びパターンマッチングの方法に関する。
【０００２】
【従来の技術】
画像処理のさまざまな応用分野において、被探索画像から、特定の画像パターン（これをテンプレートと呼ぶ）と類似した部分領域を探索するテンプレートマッチングが利用されている。このような技術は、例えば高木幹雄、下田陽久：  “画像解析ハンドブック”，東京大学出版会（１９９１）に記載されている。テンプレートマッチングでは、類似したかどうかを評価する尺度として正規化相関係数を用いることが多い。
【０００３】
ここで、テンプレートマッチングの概念について説明する。大きさＭ×Ｎのテンプレートｔ(ｍ，ｎ)と、被探索画像ｆ(ｘ，ｙ）の中の座標(ｉ，ｊ）を起点とする、大きさＭ×Ｎの部分画像ｆ(ｉ＋ｍ，ｊ＋ｎ)との正規化相関値ｒ(ｉ，ｊ)を求める。正規化相関値ｒ(ｉ，ｊ）は、テンプレートをｔ(ｍ，ｎ)(ｍ＝０，１，…，Ｍ−１，ｎ＝０，１，…，Ｎ−１)、部分画像をｆ(ｉ＋ｍ，ｊ＋ｎ)(ｍ＝０，１，…，Ｍ−１，ｎ＝０，１，…，Ｎ−１)、μfはｆの平均値、μt はｔの平均値としたとき、次式で与えられる。
【０００４】
【数１】
0003817979.tif 000002
【０００５】
但し、
【０００６】
【数２】
0003817979.tif 000003
【０００７】
正規化相関値は１の時、両者が全く一致していることを示し、−１の時、両者が全く一致しないことを示す。従って、値がより１に近ければより類似しており、値がより−１に近ければ似ていないことを表わしている。
【０００８】
数式１は、実用上は以下のように変形して計算を高速化する。
【０００９】
【数３】
0003817979.tif 000004
【００１０】
テンプレートマッチングを行うときは、複数の部分領域に対して上記正規化相関値を求め、正規化相関値が最大になる位置を求めたり、正規化相関値があるしきい値を超える位置を列挙したりして、１つまたは複数の類似領域を決定する。正規化相関の特徴は、テンプレートとサーチ画像で照明変動などにより同じ物体が異なる画素値になる場合でも、影響なく適切なマッチングが行える点にある。
しかしながら、正規化相関係数を用いたテンプレートマッチングでは、被探索画像やテンプレート画像にそれぞれノイズがのると、正規化相関値が小さくなる性質がある。特に電子顕微鏡の場合、電子のサーマルノイズが信号値と同等またはそれ以上の大きさで加わることが多く、正規化相関値が小さくなる傾向が顕著である。
【００１１】
これに対処するために、平滑化フィルタを用いてノイズ量を低減した画像を生成し、これを入力として用いることが一般に行われている。また、エッジ強調フィルタなどを施して信号変化を拡大したり、パターンの輪郭を抽出してマッチングを行ったりして、相対的にノイズ量を減らす効果を得ることが一般に行われている。
【００１２】
次に、従来のテンプレートマッチング方法について説明する。原画像ｆ0 は、ノイズＮf を加えられ、被探索画像となって入力される。また、原テンプレート画像ｔ0 は、ノイズＮt を加えられ、テンプレート画像となって入力される。被探索画像，テンプレート画像は、前処理によってノイズの影響を低減する効果のあるフィルタなどの画像処理を施され、ノイズ低減被探索画像ｆ，ノイズ低減テンプレート画像ｔに変換させられて、正規化相関に入力される。正規化相関は、数式１にもとづいて正規化相関値ｒを計算する。この正規化相関値は、ノイズの影響を受けて小さくなった値となっている。正規化相関値は判定部で、外部から入力されるしきい値Ｔｈにもとづき、しきい値以上の正規化相関値をとる部分画像をマッチング候補とし、マッチング候補に関する座標などの検出情報を生成する。
【００１３】
また、特開平10−187967号には、数式３をさらに単調減少関数の形に変形し、計算途中でしきい値を下回った部分画像に関し正規化相関値の計算を打ち切ることで、全体の計算量を減らすアイデアが開示されている。
【００１４】
さらに、ノイズ量を推定する方法として、Immerkaer, J.,“Fast Noise      Variance-Estimation”,Computer Vision and Image Understanding, Ｖol.６４，Ｎo.２，Sep. １９９６，ｐｐ.３００−３０２．がある。これは、ノイズとしてガウスノイズを仮定し、ガウスノイズの成分を推定するもので、画像ｆ（ｉ＋ｋ，ｊ＋ｌ)に対して、
ｎ(−１，−１)＝１    ｎ(０，−１)＝−２    ｎ(１，−１)＝１
ｎ(−１，０)＝−２    ｎ(０，０)＝４        ｎ(１，０)＝−２
ｎ(−１，１)＝１      ｎ(０，１)＝−２      ｎ(１，１)＝１
なる係数から成るカーネルでフィルタをかけ、以下の式に従ってノイズ分散推定値Ｖを求めるものである。
【００１５】
一次モードの時、
【００１６】
【数４】
0003817979.tif 000005
【００１７】
または、二次モードの時、
【００１８】
【数５】
0003817979.tif 000006
【００１９】
【発明が解決しようとする課題】
平滑化フィルタ，エッジ強調フィルタを用いると、確かにノイズの影響を減らすことが可能だが、探すべきパターンも変質してしまい、マッチングの精度が落ちるという問題がある。
【００２０】
平滑化フィルタでは、ノイズの低減に伴って、パターンもぼけてしまう。
【００２１】
エッジ強調フィルタでは、パターンが強調されるが、同様にノイズも増幅してしまう。
【００２２】
さらに、正規化相関値が小さくなることにより、判定に用いるしきい値も下げて定める必要があり、結果的に多くの候補に関して計算を行わなければならず、無駄な計算が増えて処理速度が遅くなる問題がある。
【００２３】
本発明の目的は、パターンを変質させるような前処理を行わずに、精度高く、また高速なパターンマッチング方法を提供することにある。
【００２４】
【課題を解決するための手段】
本発明は、上記課題を解決するために、被探索画像ｆ中からテンプレート画像ｔのパターンを検出するテンプレートマッチング方法において、
前記被探索画像に含まれるノイズ分散値量Ｖfn、及び前記テンプレート画像に含まれるノイズ分散値量Ｖtnを推定し、
数式１に従い正規化相関値ｒを計算することを特徴とするものである。
【数１】
0003817979.tif 000007
ただし、Ｖf は被検索画像ｆの分散値、Ｖt はテンプレート画像ｔの分散値、
Ｒftは被検索画像ｆとテンプレート画像ｔの相関値を表す。
また、本発明は、上記課題を解決するために、被探索画像ｆ中からテンプレート画像ｔのパターンを検出するテンプレートマッチング方法において、
前記被探索画像ｆに含まれるノイズ量を低減した画像ｆ′、及び前記テンプレート画像ｔに含まれるノイズ量を低減した画像ｔ′を生成し、
数式２に従い正規化相関値ｒを計算することを特徴とするものである。
【数２】
0003817979.tif 000008
ただし、Ｖf′はノイズ量を低減した被検索画像ｆ′の分散値、
Ｖt′はノイズ量と低減したテンプレート画像ｔ′の分散値、
Ｒftは被検索画像ｆとテンプレート画像ｔの相関値を表す。
【００２５】
【発明の実施の形態】
まず、ノイズが正規化相関値を小さくする原理を考察する。
【００２６】
一般に、被探索画像は信号成分ｆ0 と平均値が０のノイズ成分Ｎf から成り、テンプレート画像ｔは信号成分ｔ0と平均値が０のノイズ成分Ｎt から成るとモデル化することができる。
【００２７】
【数６】
ｆ(ｉ＋ｍ，ｊ＋ｎ)＝ｆ0(ｉ＋ｍ，ｊ＋ｎ)＋Ｎf(ｉ＋ｍ，ｊ＋ｎ)
ｔ(ｍ，ｎ)＝ｔ0(ｍ，ｎ)＋Ｎt(ｍ，ｎ)
ノイズ成分の平均値が０であることより、以下が成り立つ。
【００２８】
【数７】
0003817979.tif 000009
【００２９】
また、ノイズ成分は相関性がないと仮定すると、以下が成り立つ。
【００３０】
【数８】
0003817979.tif 000010
【００３１】
従って、数式７，数式８を用いると、次の式が成り立ち、数式３の分子はノイズの影響を受けないことがわかる。
【００３２】
【数９】
0003817979.tif 000011
【００３３】
一方、数式３の分母に関して、次の式が成り立つ。
【００３４】
【数１０】
0003817979.tif 000012
【００３５】
被探索画像のノイズ分散値Ｖf ，テンプレート画像のノイズ分散値Ｖt を以下のように定義する。
【００３６】
【数１１】
0003817979.tif 000013
【００３７】
すると、この被探索画像のノイズ分散値Ｖf ，テンプレート画像のノイズ分散値Ｖt を推定できれば、ノイズを含まない信号部分のみに関する正規化相関値
ｒ(ｉ，ｊ)を、次の数式で求めることができると考えられる。
【００３８】
【数１２】
0003817979.tif 000014
【００３９】
図１は、第一の実施例を示す。ノイズ推定１０４，ノイズ考慮正規化相関120,判定１２３からなる。原画像ｆ0 １０１は、ノイズＮf １０２を加えられ、被探索画像ｆ１０３となって入力される。また、原テンプレート画像ｔ0 １１１は、ノイズＮt １１２を加えられ、テンプレート画像ｔ１１３となって入力される。被探索画像ｆ１０３，テンプレート画像ｔ１１３は、ノイズ推定１０４によって画像全体のノイズの分散量を推定され、それぞれノイズ推定値Ｖf １０５，ノイズ推定値Ｖt １１５となってノイズ考慮正規化相関１２０に入力される。ノイズ考慮正規化相関１２０は、被探索画像ｆ１０３，テンプレート画像ｔ１１３，ノイズ推定値Ｖf １０５、及びノイズ推定値Ｖt １１５を入力し、数式１２にもとづき、ノイズ考慮正規化相関値ｒ１２１を計算する。ノイズ考慮正規化相関値ｒ１２１は、判定１２３で、外部から入力されるしきい値Ｔｈ１１２にもとづき、しきい値以上の正規化相関値をとる部分画像をマッチング候補とし、マッチング候補に関する座標などの検出情報１２４を生成する。
【００４０】
なお、テンプレート画像にはノイズの少ない画像を選ぶことが普通であるので、Ｎt ＝０とし、従ってノイズ考慮正規化相関１２０でＶt ＝０とし、テンプレート画像に対するノイズ推定１０４を削除する方法も、本実施例より容易に類推することができる。
【００４１】
図４にノイズ推定１０４のフローチャートを示す。まず、６０１で、対象画像をΔｉ画素×Δｊ画素の微小領域に分け、次の式のように、それぞれの微小領域の分散値ｖ(ｉ，ｊ)を求める。(ｉ，ｊ)は、微小領域の始点である。
【００４２】
【数１３】
0003817979.tif 000015
【００４３】
十分小さいΔｉ×Δｊの微小領域をとると、大部分の微小領域では信号ｆ0 の変化がほとんどなく、ほぼ一定値をとると考えられる。従って、
【００４４】
【数１４】
0003817979.tif 000016
【００４５】
が成立するので、
【００４６】
【数１５】
0003817979.tif 000017
【００４７】
となって、ノイズの分散値となる。ここで、多少とも含まれてしまう可能性のある信号成分を排除するために、最も多くの領域で分散値をとっているものをノイズの分散値と推定するのが妥当である。Δｉ，Δｊとしては、数式１４が成立すると考えられる程十分小さいサイズを選べばよく、例えば８画素程度となる。
【００４８】
次に６０２で、図５に示すような、分散値ｖ(ｉ，ｊ)を横軸とし、縦軸を度数とするヒストグラムを生成するため、ヒストグラムの該当する分散値の度数に１を加算する。
【００４９】
６０３で、６０１，６０２を、対象画像全体で繰り返してヒストグラムを完成させる。
【００５０】
最後に６０４で、ヒストグラムの最大度数をとる分散値を求め、最も多くの微小領域が有している分散値を、ノイズの分散値Ｖと推定する。
【００５１】
このように、本ノイズ分散量推定方法は、ノイズに相関がないという仮定のみに従うことにより、ガウス分布に従わないノイズを含んでいても正しいノイズ分散量を推定できる。
【００５２】
図２は、第二の実施例を示す。ノイズ推定１０４，部分画像ノイズ推定２０４，ノイズ考慮正規化相関２２０，判定１２３からなる。基本的に、図１の第一の実施例と同様であるので異なる点のみ説明する。図２で図１と異なる点は被探索画像に関する部分画像ノイズ推定２０４が、テンプレート画像に関するノイズ推定１０４と異なっている点である。ノイズ推定２０４は、テンプレートと重ねあわせて正規化相関演算させようとする部分画像に対してノイズ推定を行う。ノイズ推定２０４の出力は、部分画像のノイズ推定値Ｖf ２０５となって、ノイズ考慮正規化相関２２０に入力され、ノイズ考慮正規化相関２２０は、部分画像ごとに異なったノイズ推定値Ｖf ２０５を用いながら、数式１２にのっとり、ノイズ考慮正規化相関値１２１を計算する。
【００５３】
なお、テンプレート画像にはノイズの少ない画像を選ぶことが普通であるので、Ｎt ＝０とし、従ってノイズ考慮正規化相関２２０でＶt ＝０とし、テンプレート画像に対するノイズ推定１０４を削除する方法も、本実施例より容易に類推することができる。
【００５４】
ノイズ推定２０４は、ノイズ推定１０４と比較するとノイズ推定を行う対象が部分画像になっている点が異なるのみなので、処理の内容としてはノイズ推定１０４と全く同様に構成することができる。
【００５５】
図３は、第三の実施例を示す。前処理３０４，ノイズ考慮正規化相関３２０，判定１２３からなる。原画像ｆ0 １０１は、ノイズＮf １０２を加えられ、被探索画像ｆ１０３となって入力される。また、原テンプレート画像ｔ0 １１１は、ノイズＮt １１２を加えられ、テンプレート画像ｔ１１３となって入力される。被探索画像ｆ１０３，テンプレート画像ｔ１１３は、前処理３０４によってノイズを低減され、それぞれノイズ低減画像ｆ′３１５，ノイズ低減テンプレートｔ′３１５となってノイズ考慮正規化相関３２０に入力される。ノイズ考慮正規化相関３２０は、被探索画像ｆ１０３，テンプレート画像ｔ１１３，ノイズ低減画像ｆ′３１５、及びノイズ低減テンプレートｔ′３１５を入力し、ノイズ考慮正規化相関値ｒ１２１を計算する。ノイズ考慮正規化相関３２０がノイズ考慮正規化相関値ｒ１２１を計算する数式は次のとおりである。
【００５６】
【数１６】
0003817979.tif 000018
【００５７】
但し、
【００５８】
【数１７】
0003817979.tif 000019
【００５９】
つまり、正規化相関の分子を計算する時には、ノイズがのっているがパターンがはっきりしている元の被探索画像ｆ１０３，テンプレート画像ｔ１１３、を用い、正規化相関の分母を計算する時には、パターンがつぶれているかもしれないが、ノイズが低減されているノイズ低減画像ｆ′３１５，ノイズ低減テンプレートｔ′３１５を用いる、ということである。ノイズ考慮正規化相関値ｒ１２１は、判定１２３で、外部から入力されるしきい値Ｔｈ１１２にもとづき、しきい値以上の正規化相関値をとる部分画像をマッチング候補とし、マッチング候補に関する座標などの検出情報１２４を生成する。
【００６０】
【発明の効果】
本発明によれば、パターンを変質させるような前処理を行わないので、元のパターンをそのまま使うことができ、テンプレートマッチングを精度高く高速に実行できる。
【図面の簡単な説明】
【図１】本発明にかかるテンプレートマッチング方法の一実施例を示す図である。
【図２】本発明にかかるテンプレートマッチング方法の他の実施例を示す図である。
【図３】本発明にかかるテンプレートマッチング方法の他の実施例を示す図である。
【図４】ノイズ推定のフローチャートを示す図である。
【図５】ノイズ分散値ヒストグラムの説明図である。
【符号の説明】
１０４…ノイズ推定、１２０…ノイズ考慮正規化相関、１２３…判定。
【図１】
0003817979.tif 000022
【図２】
0003817979.tif 000023
【図３】
0003817979.tif 000024
【図４】
0003817979.tif 000025
【図５】
0003817979.tif 000026