JPH02159682A - テンプレートマッチング方式 - Google Patents
テンプレートマッチング方式Info
- Publication number
- JPH02159682A JPH02159682A JP31535688A JP31535688A JPH02159682A JP H02159682 A JPH02159682 A JP H02159682A JP 31535688 A JP31535688 A JP 31535688A JP 31535688 A JP31535688 A JP 31535688A JP H02159682 A JPH02159682 A JP H02159682A
- Authority
- JP
- Japan
- Prior art keywords
- level
- value
- template
- correlation
- threshold
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Image Analysis (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は画像によるテンプレートマツチング方式に係り
、特に高速認識を可能とするとともに二値画像処理より
も照明やノイズの影響に強いパターン位置検出方式に関
する。
、特に高速認識を可能とするとともに二値画像処理より
も照明やノイズの影響に強いパターン位置検出方式に関
する。
従来、テンプレートを用いた位置検出方式におけるテン
プレートマツチングは、濃淡画像によるテンプレートを
検出対象画面に対して１画素ずつ平行移動させて、テン
プレートが被覆する範囲について相互相関値を計算し、
その最も値の大きい所をみつけてパターンの位置を求め
るものである。
プレートマツチングは、濃淡画像によるテンプレートを
検出対象画面に対して１画素ずつ平行移動させて、テン
プレートが被覆する範囲について相互相関値を計算し、
その最も値の大きい所をみつけてパターンの位置を求め
るものである。
相互相関値は９次のように定義される。
いま、入力画像ｌが、Ｆｉｊ（ただしｉ＝１．Ｎ；Ｊ−
１，Ｍ）なる画素により構成されているとする。ここで
、ｉ＝ｌ、Ｎは横方向についての画素識別添字であり、
ｊ＝１．Ｍは画面上方より下方に向けての画素識別添字
である。テンプレートは。
１，Ｍ）なる画素により構成されているとする。ここで
、ｉ＝ｌ、Ｎは横方向についての画素識別添字であり、
ｊ＝１．Ｍは画面上方より下方に向けての画素識別添字
である。テンプレートは。
Ｔｉｊ（ただしｉ＝１．ｎ； ｊ＝１．ｍ）なる画素に
より構成されているとする。そして５部分画像（テンプ
レートが人力画像上で被覆する範囲の画像）の左上の位
置をｉ、ｊとしたときの相互相関値ｒｉｊは２次式で表
される。
より構成されているとする。そして５部分画像（テンプ
レートが人力画像上で被覆する範囲の画像）の左上の位
置をｉ、ｊとしたときの相互相関値ｒｉｊは２次式で表
される。
（ΣＦ０））
・ ・ ・（１）
ただし、Ｓ二ｎ−ｍ
Σ＝ΣΣ
に１ 淑電１１６１
ｐ−１＋ （ｋ−１）
ｑ−ｊ＋ （ｊ！−１）
テンプレート画像の値のみに関する計算値（ΣＴ、、Σ
Ｔ−など）は、あらかじめ計算されるため定数値として
処理できる。
Ｔ−など）は、あらかじめ計算されるため定数値として
処理できる。
この相互相関値ｒｌｊは、−１≦ｒｉＪ≦１の範囲の値
を取り、値１が完全にテンプレートと入力画像が同じで
あることを表す、ｒｉｊ≦Ｏの場合は。
を取り、値１が完全にテンプレートと入力画像が同じで
あることを表す、ｒｉｊ≦Ｏの場合は。
２つの画像の間には何の関係もないことを示す。
通常のテンプレートマツチングでは、テンプレートを入
力画像に対して１画素ずつ移動させて。
力画像に対して１画素ずつ移動させて。
（１）式で与えられる相関値を算出して行き、その値が
ある値（相関値は、テンプレートとどれだけ相関がある
かを表すものであるため、パターンを認識させるため、
あるしきい値以上であることをもって判断をする。）以
上で、かつ、最大になる所をパターンの存在する位置と
して検出するものである。このときの計算量は、■画素
当りの計算量を１とすれば、１つの相互相関値を計算す
るのに（ｎＸｍ）、それに移動できる所が（Ｎ−ｍ＋１
）Ｘ（Ｍ−ｍ＋１）だけあるので全体の計算量は。
ある値（相関値は、テンプレートとどれだけ相関がある
かを表すものであるため、パターンを認識させるため、
あるしきい値以上であることをもって判断をする。）以
上で、かつ、最大になる所をパターンの存在する位置と
して検出するものである。このときの計算量は、■画素
当りの計算量を１とすれば、１つの相互相関値を計算す
るのに（ｎＸｍ）、それに移動できる所が（Ｎ−ｍ＋１
）Ｘ（Ｍ−ｍ＋１）だけあるので全体の計算量は。
（（ｎＸｍ）Ｘ （Ｎ−ｎ＋１）Ｘ （Ｍ−ｍ＋１）・
・・（２） となる。
・・（２） となる。
この従来のテンプレートマツチング方式では。
２値化の方式に比べて、照明やノイズの影響に強いこと
が特徴であるが、テンプレートの大きさや範囲によって
その演算量が多くなり、パターンの位置検出を高速に実
行できないという問題があっ本発明は、この問題を解決
した演算回数の少ない高速のテンプレートマツチング方
式を提供することを目的とする。
が特徴であるが、テンプレートの大きさや範囲によって
その演算量が多くなり、パターンの位置検出を高速に実
行できないという問題があっ本発明は、この問題を解決
した演算回数の少ない高速のテンプレートマツチング方
式を提供することを目的とする。
本発明は、上記課題を解決するために、テンプレートの
大きさに応じて、相互相関値を計算する際のテンプレー
トとテンプレートが被覆する入力画像の計算対象画素の
間隔を数レベルに階層化し。
大きさに応じて、相互相関値を計算する際のテンプレー
トとテンプレートが被覆する入力画像の計算対象画素の
間隔を数レベルに階層化し。
そのレベル毎に下位のレベルにいける条件のためのしき
い値をあらかじめ設定しておき、まず、計算対象画素が
少ないレベル（一番上のレベル）から、粗い位置間隔で
相関値を計算していき、しきい値以上で周りより値の高
い位置を見出したら。
い値をあらかじめ設定しておき、まず、計算対象画素が
少ないレベル（一番上のレベル）から、粗い位置間隔で
相関値を計算していき、しきい値以上で周りより値の高
い位置を見出したら。
その位置とその近傍をもっと下位のレベルで計算して、
つぎつぎとレベルを下げていき、ついには最下位レベル
（１画素単位）での相関値の最大値の位置を求めるもの
である。
つぎつぎとレベルを下げていき、ついには最下位レベル
（１画素単位）での相関値の最大値の位置を求めるもの
である。
本発明によれば、最初は粗い位置間隔でパターンが存在
しそうな所をしきい値を使って求め、その位置を次々と
下位レベルで検索するため、下位レベルでの演算回数が
少なくなり、全体としての演算回数も少なくなる。従来
の１画素ずつずらして相互相関値を計算するのに比べて
計算・回数を大幅に短縮でき、高速化がはかれる。（た
だし、テンプレートの大きさと認識する画像の大きさに
よってこの度合は変化する。） 〔実施例〕 本発明の実施例を図面を用いて説明する。
しそうな所をしきい値を使って求め、その位置を次々と
下位レベルで検索するため、下位レベルでの演算回数が
少なくなり、全体としての演算回数も少なくなる。従来
の１画素ずつずらして相互相関値を計算するのに比べて
計算・回数を大幅に短縮でき、高速化がはかれる。（た
だし、テンプレートの大きさと認識する画像の大きさに
よってこの度合は変化する。） 〔実施例〕 本発明の実施例を図面を用いて説明する。
第１図、第２図は、それぞれ本発明の詳細な説明図であ
る。
る。
本実施例の対象となる画像は、第２図に示すように、ラ
スクスキャン方式により走査される画像である。第１図
において、入力画像ｌから、テンプレート３と同一の大
きさの部分画像２を切り出しテンプレート３と各々の対
応画素について相互相関値を計算する。そして、その値
は切り出した部分画像２の左上の位置に対応するものと
する。
スクスキャン方式により走査される画像である。第１図
において、入力画像ｌから、テンプレート３と同一の大
きさの部分画像２を切り出しテンプレート３と各々の対
応画素について相互相関値を計算する。そして、その値
は切り出した部分画像２の左上の位置に対応するものと
する。
テンプレート３は、第１図に示すように、テンプレート
抽出用人力画像４から任意の所を切り出した部分画像で
ある。
抽出用人力画像４から任意の所を切り出した部分画像で
ある。
まず、テンプレート抽出用入力画像４の部分画像を切り
出してテンプレート用メモリに格納し。
出してテンプレート用メモリに格納し。
テンプレートとする。この時、テンプレートの階層化レ
ベルの設定とレベル毎のしきい値の設定を行う、まず、
テンプレートの階層化レベルの設定であるが、テンプレ
ートの縦または横のどちらか長い方の画素数をｔｐとす
れば、 （第２図のようにテンプレートの大きさがｎＸ
ｍで０２ｍであるとすればｔｐ＝ｎとなる。） ｔ ｐ ／ ２ Ｌ ＊−１≦Ａ
・・・（３）である。
ベルの設定とレベル毎のしきい値の設定を行う、まず、
テンプレートの階層化レベルの設定であるが、テンプレ
ートの縦または横のどちらか長い方の画素数をｔｐとす
れば、 （第２図のようにテンプレートの大きさがｎＸ
ｍで０２ｍであるとすればｔｐ＝ｎとなる。） ｔ ｐ ／ ２ Ｌ ＊−１≦Ａ
・・・（３）である。
Ａは、最大レベル番号Ｌｍにおける計算対象画素のたて
方向の数とよこ方向の数のうち最大の画素数で、適宜な
値を設定する必要がある。ここで。
方向の数とよこ方向の数のうち最大の画素数で、適宜な
値を設定する必要がある。ここで。
テンプレートの大きさを１００Ｘ１００画素。
Ａ＝１６とすれば、Ｌｍ＝４となる。第３図〜第６図は
それぞれ各レベルにおける相互相関値を計算する位置と
計算対象画素を表す図である。
それぞれ各レベルにおける相互相関値を計算する位置と
計算対象画素を表す図である。
各レベルにおけるしきい値の設定であるが、これレート
の計算対象画素を２４−１画素（８画素）おきにし９テ
ンプレートを切り出した入力画像の位ように、レベル３
でも同様に、計算対象画素を４ベル３のしきい値の最高
値とする。レベル２．レベル１も同様にそれぞれ２画素
、１画素間隔の八つの近傍内で相互相関値を計算する。
の計算対象画素を２４−１画素（８画素）おきにし９テ
ンプレートを切り出した入力画像の位ように、レベル３
でも同様に、計算対象画素を４ベル３のしきい値の最高
値とする。レベル２．レベル１も同様にそれぞれ２画素
、１画素間隔の八つの近傍内で相互相関値を計算する。
（第５図。
第６図にレベル２．１の場合を示す、）各レベルのしき
い値は、各レベルにおいてもっと下位レベルで探索をす
るかどうかの尺度となる。
い値は、各レベルにおいてもっと下位レベルで探索をす
るかどうかの尺度となる。
実際に使用するしきい値は、これまでに求めたしきい値
に適当な係数を掛けて各レベルのしきい値として使用す
る。だいたい、使用する係数は０．８〜０．９ぐらいで
ある。このようにして、しきい値を適切に設定する。し
きい値は、非常に重要でこの値が低すぎれば計算回数が
非常に多くなり。
に適当な係数を掛けて各レベルのしきい値として使用す
る。だいたい、使用する係数は０．８〜０．９ぐらいで
ある。このようにして、しきい値を適切に設定する。し
きい値は、非常に重要でこの値が低すぎれば計算回数が
非常に多くなり。
また、高すぎればパターンの検出ができなくなる。
以下、各レベル４，３，２．１の最終的なしきい値をｔ
１１ａ＋ ｔ １１３．ｔ １１１＋ ｔ ｈｌ
とする。
１１ａ＋ ｔ １１３．ｔ １１１＋ ｔ ｈｌ
とする。
第７図は１本発明のテンプレートマツチング方式を詳細
に説明する図である。まず、レベル４において、テンプ
レートマツチングを行う入力画像上を走査線に従い、２
’＋１ｉ１素間隔（１７７画素毎に相互相関値を計算し
ていく、レベル４での相関値の計算に使用される画素は
、レベル４での計算対象画素２４−１画素間隔（８！素
間隔）で行われる。これは、他のレベルでも同様である
。そして、ある位ＩＦ（ｉ、Ｊ）で相関値ｒｉｊがしき
い値ｔｈ、より大きくなったとすると、その位置の２’
−’ｉ！ｊ素間隔（８ｍ！素間隔）の八つの近傍位置（
ｌ−８，ｊ−８） （１−８，Ｊ） （１−８，ｌ
＋８）（ｉ、Ｊ−８）（１，ｌ＋８）（Ｎ＋８゜Ｊ−８
）０十８．Ｊ）（ｌ＋８．Ｊ＋ｓ）にっいてレベル４で
の相関値を計算する。求める位置が、（Ｎ＋３．ｊ
３）であったとすれば、相関値はその位置からより近い
所の方が高い性質を持っているため（ｉ、ｊ）の位置が
レベル４で最も高くなる。もし、他の位置が高ければ、
その位置のへ近傍で計算されていない位置について相互
相関値を計算し、しきい値以上でまわりの八つの近傍よ
り値が高い位置を求めて行（。次に、この位置が見つか
れば、レベルを１つ下ケ、レベル３での探索となる。
に説明する図である。まず、レベル４において、テンプ
レートマツチングを行う入力画像上を走査線に従い、２
’＋１ｉ１素間隔（１７７画素毎に相互相関値を計算し
ていく、レベル４での相関値の計算に使用される画素は
、レベル４での計算対象画素２４−１画素間隔（８！素
間隔）で行われる。これは、他のレベルでも同様である
。そして、ある位ＩＦ（ｉ、Ｊ）で相関値ｒｉｊがしき
い値ｔｈ、より大きくなったとすると、その位置の２’
−’ｉ！ｊ素間隔（８ｍ！素間隔）の八つの近傍位置（
ｌ−８，ｊ−８） （１−８，Ｊ） （１−８，ｌ
＋８）（ｉ、Ｊ−８）（１，ｌ＋８）（Ｎ＋８゜Ｊ−８
）０十８．Ｊ）（ｌ＋８．Ｊ＋ｓ）にっいてレベル４で
の相関値を計算する。求める位置が、（Ｎ＋３．ｊ
３）であったとすれば、相関値はその位置からより近い
所の方が高い性質を持っているため（ｉ、ｊ）の位置が
レベル４で最も高くなる。もし、他の位置が高ければ、
その位置のへ近傍で計算されていない位置について相互
相関値を計算し、しきい値以上でまわりの八つの近傍よ
り値が高い位置を求めて行（。次に、この位置が見つか
れば、レベルを１つ下ケ、レベル３での探索となる。
レベル３では、（ｉ、Ｊ）と２４−２画素間隔（４画素
間隔）の八つの近傍位置 （１−４，ｊ−４） （ｉ−４，ｊ） （ｉ−４，
ｌ＋４）（ｉ、ｊ ４）（ｉ、ｌ＋４）（ｌ＋４゜ｊ
−４）（ｌ＋４．Ｎ （ｌ＋４．ｌ＋４）の相関値を
計算する。ここで、（＋＋４．ｊ ４）がしきい（！
！ｔｈｚより大きく九つの中で最大となる。
間隔）の八つの近傍位置 （１−４，ｊ−４） （ｉ−４，ｊ） （ｉ−４，
ｌ＋４）（ｉ、ｊ ４）（ｉ、ｌ＋４）（ｌ＋４゜ｊ
−４）（ｌ＋４．Ｎ （ｌ＋４．ｌ＋４）の相関値を
計算する。ここで、（＋＋４．ｊ ４）がしきい（！
！ｔｈｚより大きく九つの中で最大となる。
次には、（＋＋４．ｊ−４）の値が周りより大きいかど
うかを確かめるために、その八つの近傍の未計算位置 （ｉ、 Ｊ−８） （ｉ−１−４，Ｊ−８） Ｎ
＋８． ｊ−８） （１＋８． Ｊ−４） （
１＋８． ｊ）の５個所について計算を行い、これら
の値と（ｌ＋４．３−４）での値の中で最も高い値の位
置を探す、レベル３で（ｌ＋４．Ｊ ４）が見つけら
れたため１次は、レベル２での探索となる。もし。
うかを確かめるために、その八つの近傍の未計算位置 （ｉ、 Ｊ−８） （ｉ−１−４，Ｊ−８） Ｎ
＋８． ｊ−８） （１＋８． Ｊ−４） （
１＋８． ｊ）の５個所について計算を行い、これら
の値と（ｌ＋４．３−４）での値の中で最も高い値の位
置を探す、レベル３で（ｌ＋４．Ｊ ４）が見つけら
れたため１次は、レベル２での探索となる。もし。
このレベル３で、すべての値がしきい値ｔｈ、より小さ
ければ、レベル４に戻って次の位１（＋＋１１．３）の
計算を行う。
ければ、レベル４に戻って次の位１（＋＋１１．３）の
計算を行う。
なお、Ｂは計算位置が（ｉ、ｊ）のときのテンプレート
と部分画像が重なる部分である。
と部分画像が重なる部分である。
レベル２では、レベル３と同様に（１＋４．ｊ−４）と
八つの近傍位置 （ｌ＋２． Ｊ−６） （１＋２． Ｊ−４）
（ｌ＋２゜Ｊ−２）（ｌ＋４．Ｊ−６）（１−）−４
，Ｊ〜２）（１＋６．ｊ−６）（Ｎ＋６．ｊ−４）（１
＋６゜ｊ−２） の相関値を計算する。そうすると１次の四つの位置 （１＋２． ｊ−４） （１＋２． ｊ−２）
（１＋４゜ｊ−４） Ｎ＋４． ｊ−２） のどれかがしきい値ｔｈ、以上で最大値をとることにな
る。これは、レベル３で行ったのと同様の方法で求めら
れる。もし、このレベルでしきい値以上の位置が求めら
れなければ、レベル３と同様にレベル４に戻る。
八つの近傍位置 （ｌ＋２． Ｊ−６） （１＋２． Ｊ−４）
（ｌ＋２゜Ｊ−２）（ｌ＋４．Ｊ−６）（１−）−４
，Ｊ〜２）（１＋６．ｊ−６）（Ｎ＋６．ｊ−４）（１
＋６゜ｊ−２） の相関値を計算する。そうすると１次の四つの位置 （１＋２． ｊ−４） （１＋２． ｊ−２）
（１＋４゜ｊ−４） Ｎ＋４． ｊ−２） のどれかがしきい値ｔｈ、以上で最大値をとることにな
る。これは、レベル３で行ったのと同様の方法で求めら
れる。もし、このレベルでしきい値以上の位置が求めら
れなければ、レベル３と同様にレベル４に戻る。
レベル２で、仮に、 （ｌ＋２．ｊ−２）の位置が求
められたとすると１次には、レベル１での探索となる。
められたとすると１次には、レベル１での探索となる。
レベル１では、今までと同様に、（ｌ＋２．ｊ−２）と
その八つの近傍位置 （Ｎ＋１． ｊ−３） （ｉ＋ｌ、 ｊ−２） （Ｎ＋
１゜ｊ−１）（ｌ＋２．ｊ−３）（ｌ＋２、ｊ−１）（
＋＋３．ｊ−３）（Ｎ＋３．ｊ−２）（Ｎ＋３゜ｊ−１
） の相関値を計算する。そうすると、（Ｎ＋３．ｊ−３）
がしきい値Ｌｈ、以上で最大値の位置となる。そして、
この位置が周りの八つの近傍より大きいことを確かめ、
このパターンの位置が求まる。
その八つの近傍位置 （Ｎ＋１． ｊ−３） （ｉ＋ｌ、 ｊ−２） （Ｎ＋
１゜ｊ−１）（ｌ＋２．ｊ−３）（ｌ＋２、ｊ−１）（
＋＋３．ｊ−３）（Ｎ＋３．ｊ−２）（Ｎ＋３゜ｊ−１
） の相関値を計算する。そうすると、（Ｎ＋３．ｊ−３）
がしきい値Ｌｈ、以上で最大値の位置となる。そして、
この位置が周りの八つの近傍より大きいことを確かめ、
このパターンの位置が求まる。
もし、レベル１でしきい値ｔｈ＋以上の所がなければレ
ベル３と同様にレベル４に戻る。
ベル３と同様にレベル４に戻る。
このようにして、パターンの位置検出を行うわけである
が、パターンを検出すべき人力画像の中にしきい値以上
の相関値を持つパターンがただ１つしかないことが、あ
らかじめ分かっているとすれば、レベル１での探索が終
わったところでテンプレートマツチングは終わることに
なる。ところが、入力画像の中に同じようなパターンが
あるとすれば、レベル１での探索の終了後も引き続き上
位レベルに戻って、未探索個所についてより高い相関値
をもつパターン位置を検索して行く必要がある。
が、パターンを検出すべき人力画像の中にしきい値以上
の相関値を持つパターンがただ１つしかないことが、あ
らかじめ分かっているとすれば、レベル１での探索が終
わったところでテンプレートマツチングは終わることに
なる。ところが、入力画像の中に同じようなパターンが
あるとすれば、レベル１での探索の終了後も引き続き上
位レベルに戻って、未探索個所についてより高い相関値
をもつパターン位置を検索して行く必要がある。
第８図は本発明を実施するための具体的回路例を示す図
である。Ａ／Ｄ変換された画像信号は。
である。Ａ／Ｄ変換された画像信号は。
マルチプレクサ１０３を通って入力画像メモリ９２に格
納される。この時、入力画像メモリ９２のアドレスは画
像格納用アドレス発生回路９６から供給される。テンプ
レートは、この入力画像メモリ９２のある矩形領域部分
をテンプレートメモ１Ｊ９３に転送して得られる。ＣＰ
Ｕ９１は、テンプレートメモリ９３を読みだして定数値
（ΣＴ。
納される。この時、入力画像メモリ９２のアドレスは画
像格納用アドレス発生回路９６から供給される。テンプ
レートは、この入力画像メモリ９２のある矩形領域部分
をテンプレートメモ１Ｊ９３に転送して得られる。ＣＰ
Ｕ９１は、テンプレートメモリ９３を読みだして定数値
（ΣＴ。
ΣＴ”）を計算しておく。それから、ＣＰＵ９１は。
アドレス発生回路９４．９５にアドレスのスタートと間
隔とエンドを与え人力画像メモリ９２．テンプレートメ
モリ９３のそれぞれのアドレスを発生させ２両メモリの
データを読みだし、積和演算器９７で入力画像データの
総和、ΣＦ、積和演算器９８で入力画像データの２乗の
総和、ΣＦ２積和演算器９９で入力画像データとテンプ
レートデータとの積の総和ΣＴ−Ｆを並列処理して求め
る。ＣＰＵ９１は、積和演算器のデータを読み込み、テ
ンプレートとテンプレートを切り出した入力画像との相
関値を計算し、しきい値を求める。
隔とエンドを与え人力画像メモリ９２．テンプレートメ
モリ９３のそれぞれのアドレスを発生させ２両メモリの
データを読みだし、積和演算器９７で入力画像データの
総和、ΣＦ、積和演算器９８で入力画像データの２乗の
総和、ΣＦ２積和演算器９９で入力画像データとテンプ
レートデータとの積の総和ΣＴ−Ｆを並列処理して求め
る。ＣＰＵ９１は、積和演算器のデータを読み込み、テ
ンプレートとテンプレートを切り出した入力画像との相
関値を計算し、しきい値を求める。
次に、探索画像を人力画像に取り込み、前述のようにし
て相関値を計算するためのデータを積和演算器９７．９
８．９９で生成し、ＣＰＵ９１で相関値を計算する。
て相関値を計算するためのデータを積和演算器９７．９
８．９９で生成し、ＣＰＵ９１で相関値を計算する。
第９図は５本発明のテンプレートマツチング方式を表す
フローチャートである。
フローチャートである。
以上説明したように、この方式では、上位レベルでの探
索段階でしきい値をもとにパターンが存在しそうな所を
見つけ、その位置で下位レベルの探索を行うため、下位
レベルでの計算回数が少なくなり、全体的な計算回数は
かなり減少する。
索段階でしきい値をもとにパターンが存在しそうな所を
見つけ、その位置で下位レベルの探索を行うため、下位
レベルでの計算回数が少なくなり、全体的な計算回数は
かなり減少する。
いま、テンプレートの大きさを１００Ｘ１００画素、入
力画像の大きさを５１２Ｘ４８０画素。
力画像の大きさを５１２Ｘ４８０画素。
Ａ＝１６とすれば、１画素毎に移動して行〈従来の方式
では、（２）式で計算され、総計算回数＝ （１００ｘ
１００）ｘ （５１２−１００＋ｔ）Ｘ （４８０−１
００＋１） ＝１５７３５３ｘｌＯ’回 となる。
では、（２）式で計算され、総計算回数＝ （１００ｘ
１００）ｘ （５１２−１００＋ｔ）Ｘ （４８０−１
００＋１） ＝１５７３５３ｘｌＯ’回 となる。
一方１本発明の方式では、レベル毎に次のような計算回
数となる。（整数の除算は切り捨ての整数になる。） レベル４での計算回数 ＝ （１００／８ｘｌＯＯ／８） Ｘ ［（５１２−１００＋１）／１７Ｘ （４８０−１
００＋１）／１７＋Ｎ４１ ＝７６０３２＋１４４・Ｎ４ レベル３での計算回数 ＝（１００／４Ｘ１００／４）ＸＮ３ −６２５・Ｎ３ レベル２での計算回数 ＝ （１００／２ｘ １００／２） ｘＮ２＝２５００
・Ｎ２ レベル１での計算回数 ＝ （１００Ｘ１００）ＸＮＩ ＝１００００・Ｎ１ したがって、総計算回数 ＋１４４・Ｎ４＋６２５・Ｎ３＋２５００・Ｎ２＋１０
０００・Ｎｌ となる、ここで、Ｎ４．Ｎ３．Ｎ２．Ｎｌ≧Ｏでまった
く相関のない画像を探索すると、Ｎ４＝Ｎ３＝Ｎ２＝Ｎ
１＝Ｏとなる。
数となる。（整数の除算は切り捨ての整数になる。） レベル４での計算回数 ＝ （１００／８ｘｌＯＯ／８） Ｘ ［（５１２−１００＋１）／１７Ｘ （４８０−１
００＋１）／１７＋Ｎ４１ ＝７６０３２＋１４４・Ｎ４ レベル３での計算回数 ＝（１００／４Ｘ１００／４）ＸＮ３ −６２５・Ｎ３ レベル２での計算回数 ＝ （１００／２ｘ １００／２） ｘＮ２＝２５００
・Ｎ２ レベル１での計算回数 ＝ （１００Ｘ１００）ＸＮＩ ＝１００００・Ｎ１ したがって、総計算回数 ＋１４４・Ｎ４＋６２５・Ｎ３＋２５００・Ｎ２＋１０
０００・Ｎｌ となる、ここで、Ｎ４．Ｎ３．Ｎ２．Ｎｌ≧Ｏでまった
く相関のない画像を探索すると、Ｎ４＝Ｎ３＝Ｎ２＝Ｎ
１＝Ｏとなる。
もし、最適な探索を行った場合（下位しにルでの探索が
１度しか起こらなかった場合）を考えると Ｎ４−８＋５＝１３ Ｎ５＝９＋５＝１４ Ｎ２＝９＋５＝１ ４ Ｎｌ−９＋５＝１４ となり。
１度しか起こらなかった場合）を考えると Ｎ４−８＋５＝１３ Ｎ５＝９＋５＝１４ Ｎ２＝９＋５＝１ ４ Ｎｌ−９＋５＝１４ となり。
総計算回数
＝２６１．６５４回で従来の方式の約６０００分の１の
回数となる。
回数となる。
しかし、実際には、テンプレート画像、入力画像。
そして、しきい値の設定などで変わり、上位レベルでの
回数が多くなり２従来の方式の１０００分の１の回数ぐ
らいになる。
回数が多くなり２従来の方式の１０００分の１の回数ぐ
らいになる。
濃淡画像のテンプレートマツチングを用いた位置の検出
は、二値画像のパターンの位置検出に比べ照明の変化や
ノイズ影響に強いが、計算回数が膨大になって速度が遅
すぎる点が問題であったがこのように１本発明の方式で
は、従来の方式に比べ大部分の場合において大幅に計算
回数を軽減することができ、テンプレートマツチングを
高速に行えるようになる。
は、二値画像のパターンの位置検出に比べ照明の変化や
ノイズ影響に強いが、計算回数が膨大になって速度が遅
すぎる点が問題であったがこのように１本発明の方式で
は、従来の方式に比べ大部分の場合において大幅に計算
回数を軽減することができ、テンプレートマツチングを
高速に行えるようになる。
第１図、第２図は、それぞれ本発明の実施例ののテンプ
レートマツチング方式を詳細に説明する図、第８図は本
発明を実施するための具体的回路例を示す図、第９図は
本発明のテンプレートマツチング方式を表すフローチャ
ートである。 ｌ・・・・・・入力画像 ２・・・・・・部分画像 ３・・・・・・テンプレート ４・・・・・・テンプレート抽出用入力画像９１・・・
・・・ＣＰＬ） ９２・・・・・・入力画像メモリ ９３・・・・・・テンプレートメモリ ９４．９５・・・・・・アドレス発生回路９６・・・・
・・画像格納用アドレス発生回路９７．９８．９９・・
・・・・積和演算器ｌＯＯ〜１０２．１０７〜１１０ ・・・・・・バッファゲート １０３．１０４・・・・・・マルチプレクサ１０５・・
・・・・Ｄ／Ａ変換器 第 １ 回 特許出願人 株式会社安川電機製作所 第 図 （しベル４） 第５図 第 図 ｃレベル３） 第 図 図面の浄書（内容に変更なし）゛ 第 圓 しベル１での探索 レベル２での採崇 手 続 補 正 書 （方式） 事件の表示 昭和６３年特許願第３１５３５６号 発明の名称 テンプレートマツチング方式 補正をする者 事件との関係 特許出願人 願書に最初に添付した図面の浄書 別紙の通り（内容に変更なし）
レートマツチング方式を詳細に説明する図、第８図は本
発明を実施するための具体的回路例を示す図、第９図は
本発明のテンプレートマツチング方式を表すフローチャ
ートである。 ｌ・・・・・・入力画像 ２・・・・・・部分画像 ３・・・・・・テンプレート ４・・・・・・テンプレート抽出用入力画像９１・・・
・・・ＣＰＬ） ９２・・・・・・入力画像メモリ ９３・・・・・・テンプレートメモリ ９４．９５・・・・・・アドレス発生回路９６・・・・
・・画像格納用アドレス発生回路９７．９８．９９・・
・・・・積和演算器ｌＯＯ〜１０２．１０７〜１１０ ・・・・・・バッファゲート １０３．１０４・・・・・・マルチプレクサ１０５・・
・・・・Ｄ／Ａ変換器 第 １ 回 特許出願人 株式会社安川電機製作所 第 図 （しベル４） 第５図 第 図 ｃレベル３） 第 図 図面の浄書（内容に変更なし）゛ 第 圓 しベル１での探索 レベル２での採崇 手 続 補 正 書 （方式） 事件の表示 昭和６３年特許願第３１５３５６号 発明の名称 テンプレートマツチング方式 補正をする者 事件との関係 特許出願人 願書に最初に添付した図面の浄書 別紙の通り（内容に変更なし）
Claims (1)
- 【特許請求の範囲】 １、画像をカメラから取り込み、これをＡ／Ｄ変換して
画像メモリに格納し、その画像メモリに格納された入力
画像のデータを処理してパターン認識するパターン認識
方式において、縦方向ｎ画素、横方向ｍ画素（ｎ、ｍは
自然数）の濃淡画像のテンプレートを規定し、前記画像
メモリに格納された入力画像に対して、テンプレートが
被覆する範囲について、入力画像と該テンプレートとの
相互相関値を求め、その値があらかじめ定められたしき
い値以上で一番高い値を示す位置を求めることにより認
識対象の存在位置を探索することを特徴とするテンプレ
ートマッチング方式。 ２、テンプレートの大きさに応じて、相互相関値を計算
する際の演算対象画素の間隔を数レベルに階層化し、そ
のレベル毎に相関値のしきい値をあらかじめ設定してお
き、最も画素間隔の大きいレベルから１階層ずつ下のレ
ベルに向かう下記［１］から［５］の手順からなること
を特徴とするテンプレートマッチング方式。 ［１］レベル番号Ｌｍの最も画素間隔の大きいレベルで
は、前記入力画像に対して２＾Ｌ＾ｍ＋１画素ずつ必要
な画面につき該テンプレートを平行移動させて走査し、
該テンプレートが被覆する範囲について、２＾Ｌ＾ｍ−
１の画素間隔で、前記相互相関を計算し、その値が設定
されたしきい値以上であるかを判断する。しきい値未満
であれば、つぎの位置の計算に行く、しきい値以上であ
れば、［２］へ行く。 ［２］その位置を中心とした２＾Ｌ＾ｍ−１画素間隔の
八つの近傍の位置での相互相関値の計算をし、中心の値
より大きい所があれば今度はその位置を中心としまわり
の八つの近傍の位置の値を計算し、中心値が八つの近傍
より大きい位置を求めて、［３］へ行く。 ［３］現在のレベル番号Ｌが１であれば現在の位置が認
識対象の存在位置となる、レベルが１でなければ［４］
へ行く。 ［４］その位置で、レベル番号を１つ下げてその位置と
その位置を中心とした２＾Ｌ＾ｍ−１画素間隔の八つの
近傍位置での相互相関値を計算する。すべての値がその
レベルのしきい値未満であれば、レベルを最大レベル番
号にして［１］に戻る。 そうでなければ、［５］へ行く。 ［５］最も大きい値を現在の位置とし、その位置を中心
とし、まわりの八つの近傍の位置の値を計算し、現在の
位置の値より大きな値の位置を求める、現在位置の八つ
の近傍に高い値がなくなれば［３］へ行く。 ３、各レベルにおいてテンプレートの位置をそのレベル
の画素間隔の八つの近傍まで１画素ずつずらして、その
レベルの画素間隔での相互相関値を計算し、その八つの
値の最も小さい値をそのレベルのしきい値の最高値とし
、この値に適当な係数を掛けてそれぞれのレベルのしき
い値とすることを特徴とする請求項１または２記載のテ
ンプレートマッチング方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP31535688A JPH02159682A (ja) | 1988-12-13 | 1988-12-13 | テンプレートマッチング方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP31535688A JPH02159682A (ja) | 1988-12-13 | 1988-12-13 | テンプレートマッチング方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH02159682A true JPH02159682A (ja) | 1990-06-19 |
Family
ID=18064430
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP31535688A Pending JPH02159682A (ja) | 1988-12-13 | 1988-12-13 | テンプレートマッチング方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH02159682A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0689333A (ja) * | 1992-09-07 | 1994-03-29 | Chuo Denshi Kk | 印影の自動照合方法 |
| JP2001351109A (ja) * | 2000-06-09 | 2001-12-21 | Matsushita Electric Ind Co Ltd | 画像検出方法 |
| US7835543B2 (en) | 2006-10-20 | 2010-11-16 | Hitachi, Ltd. | Object detection method |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS56108181A (en) * | 1980-01-29 | 1981-08-27 | Hitachi Ltd | Feature point searching device |
| JPS57137978A (en) * | 1981-02-20 | 1982-08-25 | Toshiba Corp | Pattern detecting device |
| JPS63211474A (ja) * | 1987-02-27 | 1988-09-02 | Yaskawa Electric Mfg Co Ltd | 階層化構造的テンプレ−ト・マツチング方法 |
-
1988
- 1988-12-13 JP JP31535688A patent/JPH02159682A/ja active Pending
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS56108181A (en) * | 1980-01-29 | 1981-08-27 | Hitachi Ltd | Feature point searching device |
| JPS57137978A (en) * | 1981-02-20 | 1982-08-25 | Toshiba Corp | Pattern detecting device |
| JPS63211474A (ja) * | 1987-02-27 | 1988-09-02 | Yaskawa Electric Mfg Co Ltd | 階層化構造的テンプレ−ト・マツチング方法 |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0689333A (ja) * | 1992-09-07 | 1994-03-29 | Chuo Denshi Kk | 印影の自動照合方法 |
| JP2001351109A (ja) * | 2000-06-09 | 2001-12-21 | Matsushita Electric Ind Co Ltd | 画像検出方法 |
| US7835543B2 (en) | 2006-10-20 | 2010-11-16 | Hitachi, Ltd. | Object detection method |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Bhattacharya et al. | Interleaved deep artifacts-aware attention mechanism for concrete structural defect classification | |
| CN113095106A (zh) | 一种人体姿态估计方法、装置 | |
| CN102142168A (zh) | 纸币清分机高速高分辨率号码采集装置及其识别方法 | |
| KR20170134158A (ko) | 이미지 내의 물체 인식 시스템 및 방법 | |
| CN112037254B (zh) | 目标跟踪方法及相关装置 | |
| JPH06333054A (ja) | 映像内の目標パターン探知方式 | |
| CN114419056A (zh) | 一种逐步精细的医学图像分割系统 | |
| US20210183116A1 (en) | Map building method, computer-readable storage medium and robot | |
| CN115050066B (zh) | 人脸伪造检测方法、装置、终端及存储介质 | |
| CN107577979A (zh) | DataMatrix型二维码快速识别方法、装置及电子设备 | |
| JP2019125204A (ja) | 目標認識装置、目標認識方法、プログラム及び畳み込みニューラルネットワーク | |
| JP5264457B2 (ja) | 物体検出装置 | |
| CN110399868A (zh) | 一种滨海湿地鸟类检测方法 | |
| CN109034100B (zh) | 人脸图样检测方法、装置、设备及存储介质 | |
| CN111291611A (zh) | 一种基于贝叶斯查询扩展的行人重识别方法及装置 | |
| CN110334751B (zh) | 用于捆扎节点的图像处理方法及装置、终端 | |
| CN114549982A (zh) | 一种基于分组梯度学习策略的伪装物体检测方法及系统 | |
| RU2557755C1 (ru) | Способ сжатия изображения при фрактальном кодировании | |
| KR20190048597A (ko) | 딥 러닝을 이용한 이종 센서 정보 융합 장치 및 방법 | |
| CN110766003A (zh) | 一种基于卷积神经网络的片段和链接的场景文字的检测方法 | |
| RU2582853C2 (ru) | Устройство для определения расстояния и скоростей объектов на основе стереоподхода | |
| CN117314944A (zh) | 一种图像处理方法及相关设备 | |
| Won et al. | Image pattern recognition in natural environment using morphological feature extraction | |
| Wang et al. | The small target recognition method of neural network based on spatial and temporal information | |
| JPH08279044A (ja) | パターン認識装置およびジェスチャ認識装置 |