(57)【特許請求の範囲】
【請求項１】
テンプレート画像と、サーチ画像における該テンプレート画像と同一サイズの部分画像との類似度を正規化相関関数により評価する処理を、上記サーチ画像の複数の部分画像に対して行い、その評価値に応じて、上記複数の部分画像のうち、上記テンプレート画像と類似する部分画像を決定するテンプレートマッチング方法において、
テンプレート画像とサーチ画像におけるテンプレート画像と同一サイズの部分画像から評価尺度となるしきい値を求め、上記テンプレート画像及び上記部分画像から順次１画素ずつ画素値の差の二乗を求め累積加算し、上記累積加算値が上記しきい値を越えた時に、上記テンプレート画像と上記部分画像との評価処理を終了することを特徴とするテンプレートマッチング方法。
【請求項２】
テンプレート画像と、サーチ画像における該テンプレート画像と同一サイズの部分画像との類似度を正規化相関演算により評価する処理を、上記サーチ画像の複数の部分画像に対して行い、その評価値に応じて、上記複数の部分画像のうち、上記テンプレート画像と類似する部分画像を決定するテンプレートマッチング方法において、
予めもとめた上記テンプレート画像の画素値の総和（Ａ），上記テンプレート画像の画素値の二乗和（Ｂ），上記部分画像の画素値の総和（Ｃ）、及び、上記部分画像の画素値の二乗和（Ｄ）と、予め定めた１以下の正数（Ｅ）及び上記テンプレート画像の画素数
（Ｐ）から、
【数１】
0003721681.tif 000006
に基づいてしきい値Ｆを算出し、上記テンプレート画像と上記部分画像の対応する各画素毎に差の二乗を求め累積加算し、上記累積加算値が上記しきい値Ｆを超過したとき、上記部分画像との類似度の評価を打ち切ることを特徴とするテンプレートマッチング方法。
【請求項３】
請求項２において、
予め求めた、部分画像の画素値の総和及び二乗和を利用して、該部分画像の近傍の部分画像の画素値の総和及び二乗和を求めることを特徴とするテンプレートマッチング方法。
【請求項４】
請求項２において、
上記累積加算値の最終結果が上記しきい値より小さい場合、上記テンプレート画像と上記部分画像との正規化相関係数を求め、この求めた正規化相関係数を上記正数（Ｅ）とすることを特徴とするテンプレートマッチング方法。
【請求項５】
請求項１において、テンプレート画像とサーチ画像におけるテンプレート画像と同一サイズの部分画像から評価尺度となるしきい値を求め、上記テンプレート画像及び上記部分画像との画素値の差の二乗和を求め、上記二乗和がしきい値を超えたときに評価を打ち切り、上記二乗和が上記しきい値を越えない部分画像を評価結果として抽出することを特徴とするテンプレートマッチング方法。
【請求項６】
テンプレート画像と、サーチ画像における該テンプレート画像と同一サイズの部分画像との類似度を正規化相関関数により評価する処理を、上記サーチ画像の複数の部分画像に対して行い、その評価値に応じて、上記複数の部分画像のうち、上記テンプレート画像と類似する部分画像を決定するテンプレートマッチング装置において、
テンプレート画像及びサーチ画像を記憶する記憶装置と、
上記記憶装置からテンプレート画像及びサーチ画像を読み出し、読み出したテンプレート画像及びサーチ画像から、対象となる部分画像を評価するためのしきい値を求め、上記テンプレート画像及び上記サーチ画像から順次１画素ずつ画素値の差の二乗を求め累積加算し、上記累積加算値が上記しきい値を越えた時に、上記テンプレート画像と上記サーチ画像との評価処理を終了する処理装置とを備えたことを特徴とするテンプレートマッチング処理装置。
【請求項７】
テンプレート画像と、サーチ画像における該テンプレート画像と同一サイズの部分画像との類似度を正規化相関関数により評価する処理を、上記サーチ画像の複数の部分画像に対して行い、その評価値に応じて、上記複数の部分画像のうち、上記テンプレート画像と類似する部分画像を決定するテンプレートマッチング装置において、
テンプレート画像を記憶する第１の記憶手段と、
サーチ画像を記憶する第２の記憶手段と、
上記第１の記憶手段からテンプレート画像の画素値を読み出して該画素値の総和及び二乗和を計算し、上記第２の記憶手段からサーチ画像の画素値を読み出して、上記テンプレート画像と同サイズの部分画像における画素値の総和及び二乗和を求める第１の演算器と、
上記求めたテンプレート画像の総和及び二乗和、上記求めた部分画像の総和及び二乗和をそれぞれ保持するレジスタと、
外部から与えられる値と上記テンプレート画像の画素数及び上記レジスタに格納されたテンプレート画像の総和及び二乗和と部分画像の総和及び二乗和から評価の尺度となるしきい値を求める第２の演算器と、
上記テンプレート画像の画素値と上記部分画像の画素値の差の二乗の累積加算値を計算する第３の演算器と、
上記第３の演算器で求めた累積加算値が上記第２の演算器で求めたしきい値を越えた時に、上記テンプレート画像と上記部分画像との評価処理を終了することを特徴とするテンプレートマッチング装置。
【請求項８】
請求項７において、
上記第１の演算器は、
サーチ画像について横方向に１画素、縦方向にテンプレートと同じ画素数で構成した領域の画素値の総和をそれぞれ求め、上記求めた複数の領域の画素値の総和を組み合わせて部分画像の画素値の総和を求め、
サーチ画像について横方向に１画素、縦方向にテンプレートと同じ画素数で構成した領域の画素値の二乗和をそれぞれ求め、上記求めた複数の領域の画素値の二乗和を組み合わせて部分画像の画素値の二乗和を求めることを特徴とするテンプレートマッチング装置。
【請求項９】
請求項７において、
上記第１の演算器は、
サーチ画像について横方向に１画素、縦方向にテンプレート画像と同じ画素数で構成した領域の画素値の総和をサーチ画像の１ラインについてそれぞれ求め、
他のラインについては上記求めた領域の画素値の総和から新たに含まれる画素の画素値を加算し、含まれなくなった画素の画素値を減算して上記他のラインについて横方向に１画素、縦方向にテンプレート画像と同じ画素数で構成した領域の画素値の総和を求め、
上記求めた複数の領域の画素値の総和を組み合わせて部分画像の画素値の総和を求め、
サーチ画像について横方向に１画素、縦方向にテンプレートと同じ画素数で構成した領域の画素値の二乗和をそれぞれ求め、
他のラインについては上記求めた領域の画素値の二乗和から新たに含まれる画素の画素値を加算し、含まれなくなった画素の画素値を減算して上記他のラインについて横方向に１画素、縦方向にテンプレート画像と同じ画素数で構成した領域の画素値の二乗和を求め、
上記求めた複数の領域の画素値の二乗和を組み合わせて部分画像の画素値の二乗和を求めることを特徴とするテンプレートマッチング装置。
【請求項１０】
テンプレート画像と、サーチ画像における該テンプレート画像と同一サイズの部分画像との類似度を正規化相関関数により評価する処理を、上記サーチ画像の複数の部分画像に対して行い、その評価値に応じて、上記複数の部分画像のうち、上記テンプレート画像と類似する部分画像を決定するテンプレートマッチングを行う画像処理システムにおいて、
サーチ画像及びテンプレート画像を取り込むための画像入力装置と、
テンプレート画像及びサーチ画像を記憶する記憶部と、
上記記憶装置からテンプレート画像及びサーチ画像を読み出し、読み出したテンプレート画像及びサーチ画像から、対象となる部分画像を評価するためのしきい値を求め、上記テンプレート画像及び上記サーチ画像から順次１画素ずつ画素値の差の二乗を求め累積加算し、上記累積加算値が上記しきい値を越えた時に、上記テンプレート画像と上記サーチ画像との評価処理を終了する処理部とを少なくとも有する画像処理プロセッサと、上記画像処理プロセッサの処理を管理するホスト計算機と、上記画像入力装置で入力された画像を表示するとともに、上記画像処理プロセッサで処理された相関度の高い部分画像を表示するための表示装置とを有することを特徴とする画像処理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、半導体製品の位置決め、ＦＡラインでの部品探索，リモートセンシング等のパターン認識方法及び装置に関する。
【０００２】
【従来の技術】
画像処理のさまざまな応用分野において、センサより得られた画像（これをサーチ画像と呼ぶ）から、特定の画像パターン（これをテンプレートと呼ぶ）と類似した部分領域を探索するテンプレートマッチングが利用されている。このような技術は、例えば高木幹雄、下田陽久：“画像解析ハンドブック”、東京大学出版会（１９９１）に記載されている。ここで、各画素をｎビット（ｎ＞１）で表される多階調画像を対象とし、類似したかどうかを評価する尺度として正規化相関係数を用いることが多い。正規化相関係数ｒ（ｉ，ｊ）は、テンプレートをｔ（ｍ，ｎ)(ｍ＝０，１，…，Ｍ−１，ｎ＝０，１，…，Ｎ−１）、類似度を評価する部分画像をｓ（ｉ＋ｍ，ｊ＋ｎ）（ｍ＝０，１，…，Ｍ−１，ｎ＝０，１，…，Ｎ−１；ｉ，ｊは部分画像の起点）、テンプレートの画素数をＰとしたとき、次式で与えられる。
【０００３】
【数２】
0003721681.tif 000002
【０００４】
テンプレートマッチングを行うときは、複数の部分領域に対して上記正規化相関係数を求め、その値に応じて１つまたは複数の類似領域を決定する。正規化相関の特徴は、テンプレートとサーチ画像で照明変動などにより同じ物体が異なる画素値になる場合でも、影響なく適切なマッチングが行えるということである。
上記、正規化相関を用いたテンプレートマッチングでは、正規化相関係数を求めるための演算量が膨大であるため、効率良く求める手法が検討されている。
【０００５】
従来、正規化相関を用いた高速なテンプレートマッチング方法については、対象の部分画像とテンプレートの正規化相関係数を求めるのと同時に、対象の部分画像とテンプレートの対応する画素の差の絶対値を累積加算し、その加算値があらかじめ定めたしきい値を超過したとき、上記対象の部分画像とテンプレートの正規化相関係数を求める処理を打ち切るという方法がある。
【０００６】
【発明が解決しようとする課題】
上記従来方法は、対象の部分画像とテンプレートの対応する画素の差の絶対値を累積加算した値を打切りの評価尺度としているため、対象の部分画像とテンプレートに照明変動などによる画素値のずれがある場合、本来類似性の高い画像同士でも、画素値の差が累積し、打ち切られるという問題がある。この点について、図１３及び図１４を用いて具体的に説明する。
【０００７】
図１３はテンプレート、図１４はテンプレートを探索するサーチ画像である。矩形は画素を表し、矩形の中に記された数字はその画素の画素値（輝度）を表す。画像の類似性は、対応する画素における画素値の絶対量の近さではなく、近傍画素間の画素値の変動量に基づいているため、図１３のテンプレートに最も類似した図１４の部分画像は、１４０３，１４０４，１４０５，１４０８，１４０９，１４１０，１４１３，１４１４，１４１５で表される右上の部分画像である。実際、この部分画像とテンプレートとの正規化相関係数は１になる。ところが、従来方法の打切り評価尺度を計算すると４６０になり、１４１１，１４１２，
１４１３，１４１６，１４１７，１４１８，１４２１，１４２２，１４２３から構成される左下の部分画像とテンプレートとの打切り評価尺度８０と比べてはるかに大きな数値になる。従って、しきい値を８０から４６０の間に設定すると、左下の部分画像は類似画像の対象になるが、右上の部分画像は類似画像の対象から除外される。なお、この左下の部分画像は横縞模様の画像である。
【０００８】
また、上記以外の場合でも、しきい値を適切に定めることは容易とは言えない。
【０００９】
本発明の目的は、正規化相関係数が高い部分画像における処理の打切りを抑止し、しきい値を容易に定めることができるテンプレートマッチング方法及び装置を提供することにある。
【００１０】
【課題を解決するための手段】
上記目的は、テンプレート画像と、サーチ画像における該テンプレート画像と同一サイズの部分画像との類似度を正規化相関関数により評価する処理を、上記サーチ画像の複数の部分画像に対して行い、その評価値に応じて、上記複数の部分画像のうち、上記テンプレート画像と類似する部分画像を決定するテンプレートマッチング方法において、テンプレート画像とサーチ画像におけるテンプレート画像と同一サイズの部分画像から評価尺度となるしきい値を求め、上記テンプレート画像及び上記部分画像から順次１画素ずつ画素値の差の二乗を求め累積加算し、上記累積加算値が上記しきい値を越えた時に、上記テンプレート画像と上記部分画像との評価処理を終了することにより達成することができる。
【００１１】
【発明の実施の形態】
以下、本発明の実施例を図面に従って説明する。図１は、本発明によるテンプレートマッチング方法を記したフローチャートである。ここでは、汎用計算機により図１４のサーチ画像から図１３のテンプレート画像のテンプレートマッチングを行う場合について説明する。テンプレート画像及びサーチ画像は、例えばイメージスキャナーなどの取り込み装置によって共に外部記憶に格納されている。まず、図１３のテンプレート画像と図１４のサーチ画像を外部記憶装置から読み出し、それぞれ、ｔ（ｍ，ｎ)(ｍ＝０，１，２，ｎ＝０，１，２），ｓ（ｉ，ｊ）（ｉ＝０，１，…，４，ｊ＝０，１，…，４）の配列として計算機内部のメモリに格納する（１０１，１０２）。
【００１２】
次に、テンプレートの画素値の総和及び二乗和を計算する（１０３）。図１３のテンプレート画像の画素値の総和Ａ＝２３０、二乗和Ｂ＝６５００となる。一方、サーチ画像についてはテンプレートと同じサイズの画像領域（以下、「部分画像」という。）のすべてに対して、画素値の総和及び二乗和を計算し、計算機内部のメモリに格納する（１０４）。
【００１３】
ここで、サーチ画像におけるテンプレート画像と同じサイズの部分画像における画素値の総和及び二乗和を効率良く求める方法を、図２〜図６を用いて説明する。図２及び図３に効率化の基本的な考え方を示す。図２において、サーチ画像２００の中の、テンプレートと同サイズの部分画像２０１における画素値の総和Ｇ′は、部分画像２０１から１画素分主走査方向と逆にずれた部分画像２０２における画素値の総和Ｇから、領域２０３に含まれる画素値の総和Ｕを引いて、領域２０４に含まれる画素値の総和Ｖを足したものになる。すなわち、Ｇ′＝Ｇ−Ｕ＋Ｖである。さらに、図３に示すように、領域２０４に含まれる画素値の総和Ｖは、領域２０４から１ライン上にずれた領域２０５に含まれる画素値の総和Ｗから、画素２０６の値ｙを引いて、画素２０７の値ｚを足したもの、すなわち、Ｖ＝Ｗ−ｙ＋ｚになる。従って、部分画像２０２における画素値の総和Ｇ、及び、領域２０３に含まれる画素値の総和Ｕが事前に計算されていれば、部分画像２０１における画素値の総和Ｇ′は基本的に４回の加減算で求めることができる。
【００１４】
図４は、サーチ画像におけるテンプレートと同じサイズのすべての部分画像における画素値の総和を求めるフローチャートであり、図２及び図３で示した計算方法を実現したものである。
【００１５】
まず、（ｉ，０)(ｉ＝０，１，…，Ｉ−Ｍ：但し、Ｉはサーチ画像の横の画素数、Ｍはテンプレート画像の横の画素数である。）を起点とする（Ｉ−Ｍ＋１）個の部分画像について画素値の総和を求めるため、（ｉ，０)(ｉ＝０，１…，Ｉ−１）を起点とし縦をテンプレートと同じＮ画素、横を１画素とした領域における画素値の総和をそれぞれ計算する（４０１）。次に、求めた縦Ｎ画素、横１画素の領域における画素値の総和をＭ個加算することにより、（０，０）を起点とする部分画像の画素値の総和を求める（４０２）。以降、差分となる縦Ｎ画素、横１画素の領域における画素値の総和を加減算することにより、それぞれ（１，０),（２，０），…，（Ｉ−Ｍ，０）を起点とする部分画像における画素値の総和を順に求める（４０３）。
【００１６】
さらに、（ｉ，１)(ｉ＝０，１，…，Ｉ−Ｍ）を起点とする（Ｉ−Ｍ＋１）個の部分画像における画素値の総和を求めるため、（ｉ，１)(ｉ＝０，１，…，Ｉ−１）を起点とし、縦がテンプレートと同じＮ画素、横を１画素とする領域の画素値の総和をそれぞれ計算する（４０５）。ここでは、既に求めた、（ｉ，０）（ｉ＝０，１，…，Ｉ−１）を起点とし縦がテンプレートと同じ画素、横１画素のＩ個の領域における画素値の総和を利用し、差分となる画素値を加減算して求める。このようにして求めた縦Ｎ画素，横１画素の領域における画素値の総和をＭ個加算することにより、（０，１）を起点とする部分画像における画素値の総和を求める（４０６）。以降、差分となる縦Ｎ画素，横１画素の領域における画素値の総和を加減算することにより、（１，１),（２，１），…，(Ｉ−Ｍ，１)を起点とするそれぞれの部分画像についての画素値の総和を順に求める(４０７)。
【００１７】
ｊ＝２，…，Ｊ−Ｎに対しても、ｊ＝１のときと同様、事前に求めた計算結果を用いて、各々の部分画像における画素値の総和を求める（４０５〜４０９）。（ｉ，ｊ）を起点とする部分画像における画素値の総和をＣ（ｉ，ｊ）で表すと、図１４のサーチ画像のＣ（ｉ，ｊ)(ｉ＝０，１，２，ｊ＝０，１，２）は下記のようになる。
【００１８】
(C(0,0),C(0,1),C(0,2),C(1,0),C(1,1),C(1,2),C(2,0),C(2,1),C(2,2))＝
(390，580，690，270，380，470，270，310，380)
すべての部分画像における画素値の二乗和を求める処理は、テンプレート画像，サーチ画像の画素値の二乗値を求め、上述した画素値の総和と同様に求めることができる。（ｉ，ｊ）を起点とする部分画像の画素値の二乗和をＤ（ｉ，ｊ）で表すと、図１４のサーチ画像のＤ(ｉ，ｊ)(ｉ＝０，１，２，ｊ＝０，１，２)は下記のようになる。
【００１９】
(D(0,0),D(0,1),D(0、2),D(1,0),D(1,1),D(1,2),D(2,0),D(2,1),D(2,2))＝
(20900，44800，58500，9500，20400，30100，8700，11900，19600)
図５及び図６は効率の良い計算方法の別の方法を示したものである。図２及び図３が、主走査方向と逆に１画素分ずれた部分画像２０２との差分で部分画像
２０１における画素値の総和Ｇ′を計算したのに対し、図５及び図６は１ライン上にずれた部分画像５０２との差分で計算する。
【００２０】
図１のフローチャートの説明に戻る。演算を打ち切るためのしきい値Ｅを与える（１０５）。ここで、しきい値Ｅは正規化相関係数に対応する値としている。正規化相関係数は、−１〜１の値をとり、−１は対象とする画像がテンプレート画像と全く一致しない場合にとる値であり、１は対象とする画像が全てテンプレート画像と一致している場合にとる値である。従って、−１〜１の値の何れかを正規化相関係数のしきい値として与えればよいため未経験者でも直感的に与えることができる。尚、この値は図１の処理を開始する前に与えてもよい。本実施例では、Ｅ＝０.７ と設定した場合について説明する。
【００２１】
以上がテンプレートマッチングにおける前処理であり、テンプレート画像及びサーチ画像をそれぞれ１回ずつスキャンするだけで、テンプレート及びサーチ画像の部分画像の総和、二乗和を求めることができる。次に、各部分画像に対して、正規化相関係数を求める処理を行う。まず、（０，０）を起点とする部分画像を選択し（１０６）、数３に基づいてしきい値Ｆ（０，０）を求める(１０７)。
【００２２】
【数３】
0003721681.tif 000003
【００２３】
但し、Ａ          ：テンプレート画像の画素値の総和
Ｂ          ：テンプレート画像の画素値の二乗和
Ｃ（ｉ，ｊ）：（ｉ，ｊ）を起点とする部分画像の画素値の総和
Ｄ（ｉ，ｊ）：（ｉ，ｊ）を起点とする部分画像の画素値の二乗和
Ｅ          ：正規化相関係数のしきい値
Ｆ（ｉ，ｊ）：（ｉ，ｊ）を起点とするしきい値
Ｐ          ：テンプレート画像の画素数
である。従って、テンプレート画像の画素値の総和（Ａ）は２３０、テンプレート画像の画素値の二乗和（Ｂ）は６５００、（０，０）を起点とする部分画像の画素値の総和（Ｃ（０，０））は３９０、（ｉ，ｊ）を起点とする部分画像の画素値の二乗和（Ｄ（０，０））は２０９００、相関係数のしきい値Ｅは０.７ 、テンプレートの画素数Ｐは９より、（０，０）を起点とするしきい値Ｆ(０，０)は５２５８となる。ここで、Ｆ(０，０）は部分画像とテンプレート画像が０.７以上の正規化相関係数をもつためのテンプレート画像と部分画像の対応する各画素間の差の二乗和の上限値であり、テンプレート画像と部分画像の対応する各画素間の差の二乗和がＦ（０，０）より大きいときは、正規化相関係数は０.７ を下回る。尚、このことは、テンプレート画像と部分画像の対応する各画素間の差の二乗和＞Ｆ（０，０）と、数３及び数２から証明することができる。
【００２４】
次に、テンプレートと部分画像の対応する各画素間の差の二乗を１画素ずつ求めて累積加算し、その値がＦ（０，０）を超過していないか判定する（１０８〜１１１）。この累積加算値は単調増加するため、累積加算値が、一旦Ｆ(０，０)を超過したならば、以降の処理でＦ（０，０）を下回ることはありえないので、累積加算値がＦ（０，０）を超過した時点で処理を打切り、別の部分画像に対して同様の処理を行う。すべての画素間の差の二乗和を求めてもＦ（０，０）を超過しなければ、（０，０）を起点とする部分画像とテンプレートの正規化相関係数は０.７ 以上であることになり、部分画像の起点となる座標（０，０）を登録する。図１５は、サーチ画像の各起点の部分画像のしきい値Ｆ（ｉ，ｊ）、テンプレート画像とサーチ画像の部分画像との差の二乗の累積加算値を示したものである。サーチ画像の（０，０）を起点とする部分画像についてみるとテンプレートの第１画素値が３０、（０，０）を起点とする部分画像の第１画素値が３０、差の二乗和が０であり、Ｆ（０，０）＝５２５８を超過しないので第２画素以降に対して差の二乗を求め、累積加算すると、第６画素で累積加算値が５７００になり、Ｆ（０，０）＝５２５８を超過するため第７画素以降の処理を行わず、次の部分画像の処理に移行する。
【００２５】
これによると（０，１),（１，０),（１，１),（１，２),（２，０),(２，１)，（２，２）をそれぞれ起点とする部分画像に対して、第９画素，第３画素，第６画素，第６画素，第７画素，第７画素，第７画素の累積加算でそれぞれしきい値Ｆを超過し、（０，２）を起点とする部分画像では最後まで超過しない。従って、部分画像の起点となる座標（０，２）を０.７ より大きい正規化相関係数をもつ部分画像の位置として登録する。
【００２６】
このように、正規化相関係数に対応するしきい値Ｅを設定するだけで、このしきい値Ｅを下回らない部分画像を抽出することができる。さらに、部分画像の全ての画素についてテンプレート画像との差の二乗和を求める訳ではないので、高速に処理を実行することができる。
【００２７】
そして、このようにして得られたテンプレートとマッチングがとれた部分画像は、起点とする座標が登録されているので、汎用計算機に接続されているＣＲＴ等の表示装置にサーチ画像を表示するとともに、マッチングがとれている部分を枠で囲んで表示してオペレータに教示する。尚、多数の部分画像が登録された場合において、テンプレート画像に最も近い部分画像を得るためには、更にそれぞれの部分画像について正規化相関係数を求めて最も大きい値をとるものを選ぶようにすればよい。
【００２８】
図７は、本発明の他の実施例を示したものである。図７は、図１のフローチャートに示したテンプレートマッチング方法の変形例であり具体的には、求めた正規化相関係数がＥより大きい場合に、Ｅをその求めた正規化相関係数に置き換えた処理を追加している。尚、正規化相関については次の数４により求める。
【００２９】
【数４】
0003721681.tif 000004
【００３０】
但し、Ａ          ：テンプレート画像の画素値の総和
Ｂ          ：テンプレート画像の画素値の二乗和
Ｃ（ｉ，ｊ）：（ｉ，ｊ）を起点とする部分画像の画素値の総和
Ｄ（ｉ，ｊ）：（ｉ，ｊ）を起点とする部分画像の画素値の二乗和
Ｅ          ：正規化相関係数のしきい値
Ｇ（ｉ，ｊ）：（ｉ，ｊ）を起点とする部分画像の画素値とテンプレート画像の画素値の差の二乗和
Ｐ          ：テンプレート画像の画素数
ｒ(ｉ，ｊ)は(ｉ，ｊ)を起点とする部分画像に対する正規化相関係数である。この方法によればサーチ画像の中で最も相関度の高い部分画像をサーチすることができる。また、この方法によれば正規化相関係数に対応する値Ｅについて最適な値が分からない場合であっても、最終的にサーチ画像の中で最も相関度の高い部分画像をサーチすることができる。
【００３１】
図８に本発明の他の実施例を示す。図８は、図１のフローチャートに示したテンプレートマッチング方法の変形例であり部分画像とテンプレート画像との正規化相関係数を求める処理の直前に、全ての部分画像における画素値の総和及び二乗和を求めている。図８の処理手順にすることにより、部分画像における画素値の総和及び二乗和を記憶するためのメモリ要領を削減することができる。
【００３２】
これまでは１つのテンプレート画像に対するマッチングを行う場合について説明したが、これは複数のテンプレート画像に対するテンプレートマッチングにも適用することができる。例えば、その適用対象の１つとしてカラー画像に対するテンプレートマッチングが挙げられる。
【００３３】
図１６は、カラー画像に対するテンプレートマッチング方法を示したものである。まず、外部記憶装置からテンプレート画像及びサーチ画像をＲ(赤色の成分)，Ｇ（緑色の成分），Ｂ（青色の成分）ごとに取り込みを行う（１６０１）。取り込んだ画像に対して、Ｒ，Ｇ，Ｂの画像毎に先に述べたのと同様の方法でテンプレートマッチングを行い、テンプレート画像と相関度が高い部分画像をそれぞれＲ，Ｇ，Ｂ毎に抽出する（１６０２）。このように抽出されたＲ，Ｇ，Ｂそれぞれの部分画像から最終的な部分画像を決定する（１６０３）。これは、Ｒ，Ｇ，Ｂについて行ったテンプレートマッチングで抽出された部分画像の起点とする座標を比較して、最も多く抽出された座標を起点とする部分画像を最終的な部分画像として決定するものである。
【００３４】
尚、しきい値ＥについてはＲ，Ｇ，Ｂ共通としてもよく、また色成分に応じてしきい値Ｅを変えてもよい。また、特定の色成分に関しては打切りを実施しないなど、適用対象に応じて使い分ける。
【００３５】
図１７はテンプレートマッチングを行う装置を示したものである。本装置は、テンプレートマッチング処理部に処理開始命令を行うCPU1701 、テンプレート画像とサーチ画像を取り込んで、テンプレートマッチングを行うテンプレートマッチング処理部１７０２，テンプレート画像を記憶する画像メモリ１７０３，サーチ画像を記憶する画像メモリ１７０４から構成されている。図９にテンプレートマッチング処理部の構成を示す。図９において、９０３，９０４はそれぞれ、画像メモリ１７０３，１７０４のリードアドレスを発生するアドレス生成器、905は、画像メモリ１７０３及び１７０４から読み出されたデータを選択して出力するセレクタ、９０６は乗算器、９０７はセレクタである。９０８は加算器、909はレジスタで、９０８と９０９で累積加算を実行する。９１０は、サーチ画像における部分画像の画素値の総和及び二乗和を効率良く計算する演算器である。
【００３６】
９１５，９１６，９１７，９１８，９１９及び９２０は、それぞれ、テンプレートの画素数，正規化相関のしきい値，テンプレートにおける画素値の総和、テンプレートにおける画素値の二乗和，対象部分画像の画素値の総和を格納するレジスタ、及び、対象部分画像の画素値の二乗和を格納するレジスタである。レジスタ９１５，９１６，９１７，９１８，９１９及び９２０に格納されている値をそれぞれ、Ｐ，Ｅ，Ａ，Ｂ，Ｃ及びＤとしたとき、９２１は、Ｐ，Ｅ，Ａ，Ｂ，Ｃ及びＤに対して次の数５で記した計算を行う演算器、９２２は演算器９２１で計算された値を格納するレジスタである。また、９１１は減算器、９１２は乗算器、９１３は加算器、９１４は加算器９１３の中途計算結果を格納するレジスタである。
【００３７】
【数５】
0003721681.tif 000005
【００３８】
９２３は、レジスタ９２２に格納されたしきい値とレジスタ９１４に格納された中途計算結果を比較し、レジスタ９１４の値がレジスタ９２２の値より大きくなったとき、現在対象としている部分画像の処理を打ち切り、次の部分画像に対する処理に移行するための制御信号を出力する比較器である。
【００３９】
図９に示す構成の装置を用いたテンプレートマッチングは以下の要領で行う。まず、センサ等で入力したテンプレート画像及びサーチ画像を、それぞれ画像メモリ１７０３及び１７０４に格納する。また、CPU1701からテンプレートの画素数をレジスタ９１５、正規化相関係数のしきい値をレジスタ９１６に格納する。
次に、画像メモリ１７０３のデータを加算器９０８に入力させるように、    CPU1701 はセレクタ９０５及び９０７を設定し、アドレス生成器９０３でテンプレート画像を１画素ずつリードさせ、加算器９０８とレジスタ９０９で累積加算を求めることによりテンプレートの画素値の総和を計算する。計算結果はレジスタ９１７に格納する。同様に、画像メモリ１７０３のデータ二乗値を加算器908に入力させるように、CPU1701 はセレクタ９０５及び９０７を設定し、アドレス生成器９０３でテンプレート画像を１画素ずつリードさせ、加算器９０８とレジスタ９０９で累積加算を求めることによりテンプレートの画素値の二乗和を計算する。計算結果はレジスタ９１８に格納する。
【００４０】
続いて、画像メモリ１７０４のデータを演算器９１０に入力させるように、  CPU1701 はセレクタ９０５及び９０７を設定し、アドレス生成器９０４でサーチ画像を１画素ずつリードさせ、サーチ画像における対象部分画像の画素値の総和を計算する。計算結果はレジスタ９１９に格納する。同様に、画像メモリ1704のデータの二乗値を演算器９１０に入力させるように、ＣＰＵはセレクタ９０５及び９０７を設定し、アドレス生成器９０４でサーチ画像を１画素ずつリードさせ、サーチ画像における対象部分画像の画素値の二乗和を計算する。計算結果はレジスタ９２０に格納する。演算器９２１は、上記レジスタ９１５,９１６,９１７，９１８，９１９，９２０に格納された値を用いて、数５に示した計算を行う。演算器９２１で計算された値は処理打切り用のしきい値としてレジスタ９２２に格納される。
【００４１】
以上が、それぞれの部分画像とテンプレートの正規化相関係数を求める処理において、事前に行う処理である。正規化相関係数を求める処理では、画像メモリ１７０３からテンプレートを、画像メモリ１７０４からサーチ画像の対象部分画像を、それぞれ１画素ずつ読み出し、減算器９１１,乗算器９１２,加算器９１３によって各画素値の差の二乗を累積加算し、レジスタ９１４に格納する。比較器９２３では、上記９２２に格納されたしきい値とレジスタ９１４に格納された累積加算値を比較し、比較結果を出力する。ここで、レジスタ９１４に格納された累積加算値がレジスタ９２２に格納されたしきい値を超過したとき、レジスタ
９１９及び９２０には、現対象部分画像の次の対象部分画像における画素値の総和及び二乗和を格納し、レジスタ９２２には次の対象部分画像との正規化相関係数処理の打切りしきい値を格納すると共に、アドレス生成器９０３及び９０４のアドレスをテンプレート画像及び次対象部分画像の先頭画素アドレスに変更し、CPU1701 へ変更を知らせる。
【００４２】
図１０に演算器９１０の構成例を示す。図１０において、１０００は演算器
９１０に対応する演算器、１００１は、少なくともテンプレートと同ライン数の、各ラインが少なくともサーチ画像と同画素数の記憶領域をもつラインメモリ、１００２及び１００５は減算器、１００３及び１００６は加算器、１００４は、少なくともサーチ画像と同画素数の記憶領域をもつ１ラインのラインメモリ、
１００７はレジスタ、１００８は演算結果を記憶するメモリ、１００９はメモリ１００８をアクセスするアドレスを発生するアドレス生成器である。ラインメモリ１００１，１００４、及び、レジスタ１００７は最初すべて０に初期化されているものとする。
【００４３】
図２及び図３を併用して、サーチ画像における部分画像の画素値の総和を求めるときの図１０の演算器の動作を説明する。演算器１０００にはサーチ画像の画素がラスタスキャン順に入力するものとする。演算器１０００に入力されたデータ（ｚとする）はラインメモリに格納されると共に、減算器１００２に入力される。ここで、現在入力された画素データを、図３の画素２０７であるとする。また、ラインメモリ１００１からデータｚに対応する画素のサーチ画像上Ｎライン（＝テンプレートのライン数）上方に対応するデータ（ｙとする）を読み出し、減算器１００２に入力する。この画素データは図３の画素２０６に対応する。ここで、データｙに対応する画素がサーチ画像上にないときは、ｙとして初期値０が読み出される。減算器１００２でｚ−ｙが実行される。ラインメモリ１００４は縦Ｎライン横１画素の画像を画素値の総和を１ライン分格納したメモリである。加算器１００３では、減算器１００２で計算されたｚ−ｙと、ラインメモリ
１００４から読み出した図３の領域２０５に対応する画像の画素値の総和（Ｗとする）を加算し、図２の領域２０４に対応する画像の画素値の総和（Ｖとする）を出力する。加算器１００３から出力されたデータはラインメモリ１００４に格納されると共に、減算器１００５に入力される。減算器１００５では、上記Ｖから、ラインメモリ１００４から読み出した図２の領域２０３に対応する画像の画素値の総和（Ｕとする）を引いた結果を出力する。加算器１００６では、上記減算結果と、レジスタ１００７に格納されている図２の部分画像２０２の画素値の総和（Ｇとする）を加算することにより、部分画像２０１の画素値の総和を計算する。計算された部分画像２０１の画素値の総和は、レジスタ１００７に格納されると共に、メモリ１００８にも格納される。
【００４４】
以降、サーチ画像を１画素読み出す毎に、隣接した部分画像の画素値の総和を計算することを繰り返す。サーチ画像における部分画像の画素値の二乗和も同様に計算し、メモリ１００８に格納する。特定の部分画像に対する正規化相関係数を求める演算では、対象部分画像の画素値の総和及び二乗和を、メモリ１００８からアドレス生成器１００９を用いて順に読み出すことにより、図９のレジスタ９１９及び９２０に格納する。
【００４５】
図１１に画像処理システムの構成を示す。システム構成としては、画像処理プロセッサ１１０１，ホストプロセッサ１１０２,センサ１１０３,モニタ１１０４からなる。画像処理プロセッサの構成を図１２に示す。図１２において、1201，１２０２が画像メモリ、１２０３はテンプレートマッチング部、１２０４はフィルタリングなどの画像前処理部、１２０５は端子１２０９から入力された映像信号をライトバス１２１４に出力する映像入力処理部、１２０６はリードバス1212のデータを映像信号として端子１２１０に出力する映像表示処理部、１２０７はホストプロセッサとの信号の入出力を司るホストインタフェース、１２０８は、画像メモリ１２０１及び１２０２と、上記の演算部あるいはインタフェース部とのデータパス制御，アドレス制御などを行うバス制御部である。
【００４６】
テンプレートマッチング部１２０３の構成としては、図９から、アドレス生成器９０３及び９０４を除いたものと同じであり、アドレス発生器９０３，９０４の機能はバス制御部が担う。
【００４７】
ここで、画像処理プロセッサ１１０１として、図１２の１２００が対応し、センサ１１０３が端子１２０９，モニタ１１０４が端子１２１０，ホストプロセッサ１１０２が端子１２１１にそれぞれ接続される。
【００４８】
テンプレートマッチングを行う前に、テンプレート画像とサーチ画像を画像メモリ１１０１または１１０２に格納する。このとき、テンプレートはセンサ1103から入力した画像を端子１１０９,映像入力処理部１２０６,ライトバス１２１４，バス制御部１２０８を経由して画像メモリ１２０１または１２０２に格納するか、もしくは、ホストプロセッサが有する情報を端子１２１１，ホストインタフェース１２０７，バス１２０８を経由して画像メモリ１２０１または１２０２に格納する。サーチ画像はセンサ１１０３から入力した画像を端子１２０９，映像入力処理部１２０５，ライトバス１２１４，バス制御部１２０８を経由して画像メモリ１２０１または１２０２に格納する。
【００４９】
テンプレート画像，サーチ画像にはノイズが含まれていることが一般的なので、ノイズを低減するため、フィルタリングなどの前処理を実施する。すなわち、テンプレート或いはサーチ画像を画像メモリ１２０１または１２０２からバス制御部１２０８，リードバス１２１２または１２１３を経由して読み出し、前処理部１２０４で適当な前処理演算を行う。処理した結果は、ライトバス１２１４，バス制御部１２０８を経由して、画像メモリ１２０１または１２０２に格納する。どういう前処理を行うかはホストプロセッサから端子１２１１，ホストインタフェース１２０７を経由して設定される。処理結果は、バス制御部１２０８，ライトバス１２１４，映像表示処理部１２０６を経由してモニタに表示し、確認することができる。
【００５０】
テンプレートマッチングは画像メモリ１２０１または１２０２からバス制御部１２０８を経由して、テンプレート及びサーチ画像を読み出し、テンプレートマッチング部で正規化相関係数を計算することにより行う。ここで、図９における比較結果などに応じて相関度の高い位置を記憶しておき、全部分画像を処理した後、記憶している相関度の高い位置情報をホストインタフェース１２０７を経由し、ホストプロセッサに示す。
【００５１】
この例では、すべての演算を画像処理プロセッサで行っているが、しきい値計算における複雑な演算をホストプロセッサで行うように構成してもよい。
【００５２】
【発明の効果】
本発明により、正規化相関を用いたテンプレートマッチングを、類似性の高い画像を対象外にすることなく高速化を図ることができる。
【図面の簡単な説明】
【図１】本発明のテンプレートマッチングの手順を示すフローチャートである。
【図２】本発明の部分画像の画素値の総和及び二乗和を求めるための説明図である。
【図３】本発明の部分画像の画素値の総和及び二乗和を求めるための説明図である。
【図４】本発明の部分画像の画素値の総和及び二乗和を求めるフローチャートである。
【図５】本発明の部分画像の画素値の総和及び二乗和を他の方法により求めるための説明図である。
【図６】本発明の部分画像の画素値の総和及び二乗和を他の方法により求めるための説明図である。
【図７】本発明のテンプレートマッチングの他の手順を示すフローチャートである。
【図８】本発明のテンプレートマッチングの他の手順を示すフローチャートである。
【図９】本発明のテンプレートマッチング処理部の内部構成を示す図である。
【図１０】本発明のテンプレートマッチング処理部における部分画像の画素値の総和及び二乗和を求める演算器の内部構成を示す図である。
【図１１】本発明を適用した画像処理システムを示す図である。
【図１２】本発明を適用した画像処理システムの画像処理プロセッサの構成図である。
【図１３】テンプレート画像の一例を示した図である。
【図１４】サーチ画像の一例を示した図である。
【図１５】本発明によりテンプレートマッチングを行った場合の部分画像としきい値との関係を示した図である。
【図１６】本発明のテンプレートマッチングをカラー画像に適用した場合の処理手順を示したフローチャートである。
【図１７】本発明のテンプレートマッチング装置の構成を示した図である。
【符号の説明】
９０３，９０４…アドレス生成器、９０５,９０７…セレクタ、９０６,９１２…乗算器、９０８，９１３…加算器、９１１…減算器、９１０，９２１…演算器、９０９，９１４，９１５，９１６，９１７，９１８，９１９，９２０，９２２…レジスタ、９２３…比較器、１１０３…センサ、１１０４…モニタ。
【図１】
0003721681.tif 000007
【図２】
0003721681.tif 000008
【図３】
0003721681.tif 000009
【図４】
0003721681.tif 000010
【図５】
0003721681.tif 000011
【図６】
0003721681.tif 000012
【図７】
0003721681.tif 000013
【図８】
0003721681.tif 000014
【図９】
0003721681.tif 000015
【図１０】
0003721681.tif 000016
【図１１】
0003721681.tif 000017
【図１２】
0003721681.tif 000018
【図１３】
0003721681.tif 000019
【図１４】
0003721681.tif 000020
【図１５】
0003721681.tif 000021
【図１６】
0003721681.tif 000022
【図１７】
0003721681.tif 000023