JP2000207556A

JP2000207556A - パタ―ンマッチング方法と装置

Info

Publication number: JP2000207556A
Application number: JP11219477A
Authority: JP
Inventors: Takashi Anezaki; 隆姉崎
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1998-11-10
Filing date: 1999-08-03
Publication date: 2000-07-28

Abstract

(57)【要約】【課題】認識対象パターンに合った特徴形状について
配置された少ない演算点での演算で、低コスト、高速、
高精度にパターンマッチングできるようにする。【解決手段】画像データ１ａをパターンに合わせて設
定した粗サーチテンプレート２による粗サーチパターン
マッチングをし、検出マッチングパターンの正解パター
ンＴと不正解パターンＨ₁、Ｈ₂の別から、正解パター
ンＴのみに関する特徴形状データＰ２、不正解パターン
Ｈ₁、Ｈ₂のみに関する禁止特徴形状データＰ３を抽出
し、情報の過不足による補正をして間引き設定した最適
粗サーチテンプレートＴ２上の各設定位置でのみ画像デ
ータ１ａについて演算し、禁止特徴パターンとマッチン
グする画像データＨ₁、Ｈ₂についてのそれ以上の操作
を省きながら、特徴形状パターンＰ２とのマッチングし
た画像でーたパターンＴを検出するようにして、上記の
目的を達成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、民生および産業用
の画像処理方法および装置、特に電子部品実装機や半導
体組立などの高速・高精度な位置決めが要求される視覚
認識装置等において、対象物の位置などの必要な情報を
画像認識するために高速、高精度にパターンマッチング
を行う方法および装置に関するものである。

【０００２】

【従来の技術】パターンマッチングにおける従来技術の
１つに、テンプレートマッチング法がある。これは該当
部分画像（テンプレート）のポインティングのみでテン
プレートデータを教示できる。しかし、精度確保が要件
の場合にテンプレートサイズが大きくなり、大規模な画
像演算ハードウエアが不可欠となる。

【０００３】下記の式１はある演算点（座標）でのテン
プレートマッチング演算式を示す。

【０００４】

【数１】式１におけるＴは図５の左側に示したテンプレートで、
ｉ・ｊはテンプレートＴ上の位置を示す。従って、Ｔ
（ｉ、ｊ）はテンプレートＴ上ｉ・ｊの位置の濃淡値を
示す。またＧは図５の右側に示した対象画像で、同様に
ｘ・ｙはある演算点の位置、ｉ・ｊはある演算点からテ
ンプレートＴ上のオフセット位置を示す。従って、Ｇ
（ｘ＋ｉ，ｙ＋ｊ）は画像（ｘ＋ｉ）・（ｙ＋ｊ）の位
置の濃淡値を示す。また、Θは加算、乗算、エクスクル
ーシブ・オア、正規化相関等のマッチング演算を総称し
て示す。

【０００５】テンプレートマッチングは、通常、画像上
の全点に対し行う。このため、Θ演算をＯ（Ｍ・Ｎ・Ｘ
・Ｙ）の回数で行う。ここで、Ｍ・Ｎはテンプレートサ
イズ、Ｘ・Ｙは画像サイズである。精度確保のため大テ
ンプレートとするとＭ・Ｎが大きくなる。５０×５０の
テンプレートで５００×５００の画像に対して演算量を
概算すれば、ハードに要求される処理能力は約５０００
ＭＩＰＳ（Ｍｉｌｌｉｏｎｉｎｓｔｒｕｃｔｉｏｎｓ
ＰｅｒＳｅｃｏｎｄ）である。現在最速のマイクロ
プロセッサは約５００ＭＩＰＳ（概算値）程度であるた
め、専用ハードが必須となる。

【０００６】図６に、上記のような通常のテンプレート
マッチングの演算コストを改善した従来例を示してい
る。テンプレートＴに設定される演算位置を間引いてＯ
（Ｍ・Ｎ）を減らす。また、画像Ｇ上の演算点を間引い
てＯ（Ｘ・Ｙ）を減らす。間引き次第では、専用ハード
を使用せず、最速のマイクロプロセッサでのマッチング
演算ができるようになる。

【０００７】

【発明が解決しようとする課題】しかし、上記のような
間引き手法では、間引き演算点間の中央に実対象点があ
ったために正解を見落とす。あるいは、テンプレートの
規則的な間引きにより、ユニークな特徴点を間引いてし
まい、誤認識回数が増加する。などの危険が発生しやす
い。

【０００８】本発明の目的は、テンプレート上に認識対
象パターンに合った部分的な特徴形状についてだけ配置
された少ないポイントでの演算で、低コストに、高速か
つ高精度にパターンマッチング処理できるパターンマッ
チング方法およびその装置を提供することにある。

【０００９】

【課題を解決するための手段】上記のような目的を達成
するため、本発明のパターンマッチング方法は、対象物
を撮像した画像データにつき、対象物の情報を画像認識
するのに必要な特定のパターンに合わせて設定したサー
チテンプレートにより、予め設定した演算箇所およびパ
ターン一致閾値に基づく粗サーチパターンマッチングを
行い、検出された粗マッチングパターンにつき正解、不
正解の評価を行い、評価した正解パターンと不正解パタ
ーンとから、正解パターンに含まれ不正解パターンに含
まれない特徴形状データと、不正解パターンに含まれ正
解パターンに含まれない禁止特徴形状データとを抽出し
て、それらに正解、不正解パターンを検出するための検
出情報の過不足を補正する最適化処理をした特徴形状パ
ターンおよび禁止特徴形状パターンの位置データを持っ
た最適粗サーチテンプレートを設定し、この最適粗サー
チテンプレート上の特徴形状パターンおよび禁止特徴形
状パターンの各設定位置でのみ前記画像データとのマッ
チング演算をし、禁止特徴形状パターンとマッチングし
た画像データのそれ以上の処理操作を排除しながら、特
徴形状パターンとマッチングした画像データを検出して
対象物の必要情報が画像認識されるようにすることを１
つの特徴としている。

【００１０】このような構成では、対象物を撮像した画
像データにつき、対象物の位置などの情報を画像認識す
るのに必要な特定のパターンにつき設定したサーチテン
プレートにより、予め設定した所定の演算箇所およびパ
ターン一致閾値に基づく粗サーチパターンマッチングを
行うことにより、粗マッチングパターンが、前記演算箇
所およびパターン一致閾値を粗くした分だけ早期に安定
して得られる。得られた粗マッチングパターンにはパタ
ーン一致閾値が粗くされることにより正解パターンと不
正解パターンが含まれる。しかし、パターンの正解、不
正解は人が容易に評価できる。評価された正解、不正解
パターンから、正解パターンに含まれ不正解パターンに
含まれない特徴形状データと、不正解パターンに含まれ
正解パターンに含まれない禁止特徴形状データとを抽出
することにより演算データ数を間引くことができ、それ
らに正解、不正解パターンを検出するための検出情報の
過不足を補正する最適化処理を施すことにより、演算デ
ータ数が少ないが正解パターンおよび不正解パターンを
検出するには充分な特徴形状パターンおよび禁止特徴形
状パターンの位置データを持った最適粗サーチテンプレ
ートを設定することができる。従って、この最適粗サー
チテンプレート上の特徴形状パターンおよび禁止特徴形
状パターンによる少ない各設定位置でのみ前記画像デー
タとのマッチング演算をすることにより、禁止特徴パタ
ーンとマッチングした画像データのそれ以上の操作を省
きながら、特徴パターンとのマッチング画像データを検
出して対象物の必要な情報を画像認識できるようにする
ことが、低コストで、しかも高速かつ高精度に達成され
る。

【００１１】本発明のパターンマッチング方法は、ま
た、対象物を撮像した画像データにつき、対象物の情報
を画像認識するのに必要な特定のパターンにて、複数方
向の空間一次微分を行なって微分値の大きい点を各一次
微分プレーン上で１とする必要ビット数のサーチテンプ
レートを設定し、このサーチテンプレートにより、予め
設定した演算箇所およびパターン一致閾値に基づく粗サ
ーチパターンマッチングを行い、検出された粗マッチン
グパターンにつき正解、不正解の評価を行い、評価した
正解パターンと不正解パターンとから、正解パターンに
含まれ不正解パターンに含まれない特徴形状データと、
不正解パターンに含まれ正解パターンに含まれない禁止
特徴形状データとを抽出して、それらに正解、不正解パ
ターンを検出するための検出情報の過不足を補正する最
適化処理をした特徴形状パターンおよび禁止特徴形状パ
ターンの位置データを持った最適粗サーチテンプレート
を設定し、この最適粗サーチテンプレート上の特徴形状
パターンおよび禁止特徴形状パターンの各設定位置での
み前記画像データとのマッチング演算をし、禁止特徴形
状パターンとマッチングした画像データのそれ以上の処
理操作を排除しながら、特徴形状パターンとマッチング
した画像データを検出して対象物の必要情報が画像認識
されるようにすることを今１つの特徴としている。

【００１２】このような構成では、上記発明に加え、さ
らに、対象物を撮像した画像データにつき、対象物の位
置などの情報を画像認識するのに必要な特定の部分パタ
ーンに対する所定の一次微分操作によりパターンおよび
必要精度に合った粗さを満足して粗サーチテンプレート
を設定することができ、粗サーチパターンマッチングに
よるマッチング操作の省略を所定の検出精度を保証して
達成しやすい。

【００１３】最適化処理は、最適粗サーチテンプレート
での特徴形状パターンマッチングにおいて正解、不正解
パターンの検出上欠かせないか、不必要な位置データを
追加、除去するのが好適であり、最適粗サーチテンプレ
ートは、複数の対象物につき粗サーチパターンマッチン
グを繰り返し行って収集した正解パターンと不正解パタ
ーンとから生成するのが好適である。

【００１４】最適粗サーチテンプレートでの特徴形状パ
ターンマッチングでは誤検出しやすい微細特徴部分や非
認識部分と酷似する部分については、この部分に合った
精サーチテンプレートにより、粗サーチパターンマッチ
ングの場合よりは密な演算箇所にて精サーチパターンマ
ッチングを行い、特徴形状パターンマッチングおよび精
サーチパターンマッチング双方を満足した画像データを
検出して対象物の必要情報が画像認識されるようにする
と、最適粗サーチテンプレートでの特徴形状パターンマ
ッチングによる上記特徴を活かしながら、この特徴形状
パターンマッチングでは誤検出するような部分だけを精
サーチパターンマッチングを行って検出の必要精度を確
保することができる。

【００１５】本発明のパターンマッチング装置は、入力
される撮像された対象物の画像データを記憶する画像記
憶手段と、対象物の必要情報を画像認識するのに必要な
特定のパターンに合った粗サーチテンプレートを教示す
る粗サーチテンプレート教示手段と、教示された粗サー
チテンプレートにより予め設定された所定の演算箇所お
よびパターン一致閾値に基づき画像記憶手段からの画像
データにつき粗サーチパターンマッチングを行い、検出
した粗マッチングパターンを記憶するとともに表示する
粗サーチ処理手段と、検出された粗マッチングパターン
の人による正解、不正解の評価に基づく正解パターンと
不正解パターンとから、正解パターンに含まれ不正解パ
ターンに含まれない特徴形状データと、不正解パターン
に含まれ正解パターンに含まれない禁止特徴形状データ
とを抽出して表示し、かつそれらによる正解パターンお
よび不正解パターンの検出のための情報の過不足の教示
の基に特徴データおよび禁止特徴データを補正する最適
化処理して得た特徴形状パターンおよび禁止特徴形状パ
ターンの位置データを持った最適粗サーチテンプレート
を生成する粗サーチテンプレート最適化処理部とを備
え、粗サーチ処理手段はこの最適粗サーチテンプレート
上の特徴形状パターンおよび禁止特徴形状パターンの各
設定位置でのみ前記画像データとのパターンマッチング
の演算をし、演算の結果禁止特徴形状パターンとマッチ
ングした画像データについてのそれ以上の処理操作を省
きながら、特徴形状パターンとマッチングする画像デー
タを検出して対象物の必要情報が画像認識されるように
したことを１つの特徴としている。

【００１６】このような構成では、パターンに合った粗
サーチテンプレートの教示、教示される粗サーチテンプ
レートによる粗サーチパターンマッチング処理、および
この粗サーチパターンマッチングで検出される粗マッチ
ングパターンについての正解、不正解の評価の教示によ
る正解パターンおよび不正解パターンとから、上記特定
形状データおよび禁止特定形状データを得るとともに、
これら情報の過不足の教示に基づいた最適化処理にて位
置データを追加、削除した上記最適粗サーチテンプレー
トを生成し、この最適粗サーチテンプレートによる特徴
形状パターンマッチングすることを自動的に行い、上記
のパターンマッチング方法を容易にかつ的確に達成する
ことができる。

【００１７】本発明のパターンマッチング装置は、ま
た、上記装置に加え、粗サーチテンプレート教示手段
が、対象物の必要情報を画像認識するのに必要な特定の
部分パターンにて、必要精度に合った複数方向の空間一
次微分を行ない微分値の大きい点を各一次微分プレーン
上で１とした必要ビット数のパターンに合った粗サーチ
テンプレートを教示するものであり、部分パターンおよ
び必要精度に合った粗サーチテンプレートの教示が安定
して行なえる。

【００１８】最適粗サーチテンプレートによる特徴形状
パターンマッチングでは誤検出しやすい微細特徴部分や
認識対象部分と酷似する部分に合った精サーチテンプレ
ートを教示する精サーチ教示手段と、教示された精サー
チテンプレートにより粗サーチパターンマッチングの場
合よりは密な演算箇所にて精サーチパターンマッチング
を行う精サーチ処理手段とを備え、特徴形状パターンマ
ッチングおよび精サーチパターンマッチングの双方を満
足したパターンを検出して対象物の必要情報が画像認識
されるようにすると、特徴形状パターンマッチングの特
徴を活かしながら、特徴形状パターンマッチングでは誤
検出しやすい部分では精サーチパターンマッチングによ
り必要精度を確保したパターンマッチングが自動的に容
易かつ的確に達成される。

【００１９】なお、空間一次微分の方向を８方向、必要
ビット数を８と設定して精度保証上好適な結果が得られ
る。

【００２０】本発明のそれ以上の目的および特徴は以下
の詳細な説明と図面の記載によって明らかになる。本発
明の各特徴は、可能な限りにおいて、それ単独で、ある
いは種々な組み合わせで複合して用いることができる。

【００２１】

【発明の実施の形態】以下、本発明のパターンマッチン
グ方法、およびその装置に係る実施の形態について、実
施例とともに図１〜図４を参照しながら説明し、本発明
の理解に供する。

【００２２】本実施の形態のパターンマッチング方法
は、図３に示すように対象物１を撮像カメラなどの撮像
系１００により撮像した図１の（ａ）に示すような画像
データ１ａを、人が設定したサーチテンプレート２によ
りパターンマッチングを行って、対象物１の位置などの
情報を画像認識するための必要な特定のパターンに合っ
た粗サーチテンプレートを設定する。１つの実施例とし
ては、部分パターンにて、複数の方向、例えば必要精度
に合った８方向の空間一次微分を行ない微分値の大きい
点を一次微分プレーン上で１とした必要ビット数、例え
ば８ビットの粗サーチテンプレート２を設定する。この
設定した粗サーチテンプレート２により粗サーチパター
ンマッチングを行う。これの結果、粗サーチテンプレー
ト２と一致するものとして検出される粗マッチングパタ
ーンは、パターン一致閾値が緩和されているため、前記
特定のパターンとそれの類似のパターンを含み、類似の
パターンは複数検出されることが多い。そこで、粗サー
チパターンマッチングで検出されたマッチングパターン
につき人が図１の（ａ）に示すように正解、不正解の評
価を行い正解パターンＴと不正解パターンＨ₁、Ｈ₂・
・に分類する。

【００２３】もし正解パターンＴがなければ、正解パタ
ーンＴが得られるまで粗サーチパターンマッチングの演
算箇所を順次変えながら、粗サーチパターンマッチング
を繰り返し行えばよい。このようにしても画像データ１
ａの全画素について精サーチパターンマッチングを行う
場合よりも正解パターンＴを早期に得る確率は高く、作
業コストは大幅に低減する。一方、個々の対象物１が持
つ特定のパターンは全て正確に一致しているとは限ら
ず、バラツキのあることが多い。これに対処するため本
実施の形態では、複数の対象物１、敷衍していえば必要
なパターンマッチング精度、画像認識精度が得られるだ
けの数の対象物１について、粗サーチパターンマッチン
グを行い、得た各回の正解パターンＴ・・と不正解パタ
ーンＨ₁、Ｈ₂・・・を収集する。

【００２４】得られた図１の（ａ）に示すような正解パ
ターンＴ・・と不正解パターンＨ₁、Ｈ₂・・・とか
ら、正解パターンＴ・・に含まれ不正解パターンＨ₁、
Ｈ₂・・・に含まれない特徴形状データと、不正解パタ
ーンＨ₁、Ｈ₂・・・に含まれ正解パターンＴに含まれ
ない禁止特徴形状データとを抽出する。具体的には、全
正解パターンと全不正解パターンのＯＲ画像を算出し、
このＯＲ画像と各正解パターンとの画像間差分によって
対象物１の特定のパターンにのみ含まれる特徴形状デー
タを抽出し、前記ＯＲ画像と各候補パターンとの画像間
差分によって対象物１の特定のパターンに類似するパタ
ーンにのみ含まれる禁止特徴形状データを抽出する。こ
れによって、個々の対象物１でバラツキのある特定のパ
ターンに対応した特徴形状データと禁止特徴形状データ
とが得られる。

【００２５】説明の簡単のため、検出位置の数を極く少
なくして（例えば３０分の１程度）図１の（ａ）に示す
正解パターンＴと不正解パターンＨ₁との関係だけで具
体例を述べると、双方のＯＲ画像は図１の（ｂ）に示す
Ｐ１として得られる。図１の（ｂ）のＯＲ画像Ｐ１と図
１の（ａ）の正解パターンＴとの差分の有無によって図
１の（ｃ）に示す特定のパターンにのみ含まれる特徴形
状データＰ２が得られる。また、図１の（ｂ）のＯＲ画
像と図１の（ａ）の不正解パターンＨ₁との差分の有無
によって図１の（ｄ）に示す特定のパターンにのみ含ま
れる禁止特徴形状データＰ３が得られる。

【００２６】従って、特徴形状データＰ２は画像データ
１ａとのパターンマッチングによって、対象物１の特定
のパターンに対応する正解パターンＴを検出するのに役
立ち、禁止特徴形状データＰ３は画像データ１ａとのパ
ターンマッチングによって、対象物１の特定の正解パタ
ーンＴと類似していることにより誤検出されやすい不正
解パターンＨ₁をノイズとして検出するのに役立つ。そ
こで、本実施の形態ではこれら特徴形状データと禁止特
徴形状データとを含み、他の部分を間引き画素とした図
１の（ｅ）に黒丸と実線三角で演算点を示す初期最適粗
サーチテンプレートＴ１を設定する。

【００２７】このような手法で設定した初期最適粗サー
チテンプレートＴ１によって画像データ１ａとのパター
ンマッチングを行うことにより、禁止特徴形状データＰ
３がマッチングした不正解パターンＨ₁、Ｈ₂・・・に
ついてのそれ以上の操作を省きながら、特徴形状データ
Ｐ２がマッチングした特定のパターン、つまり正解パタ
ーンＴを検出して対象物１の必要な位置情報などを画像
認識できるようにすることが、低コストで高速かつ高精
度に達成される。

【００２８】しかし、前記設定した初期最適粗サーチテ
ンプレートＴ１の特徴形状データＰ２や禁止特徴形状デ
ータＰ３は、それぞれの検出の役目を果たすのに不可欠
の位置データが欠けたり、不必要な位置データが含んだ
りすることがときとしてある。これに対処するのに本実
施の形態では、前記初期最適粗サーチテンプレートＴ１
の各演算点である特徴形状、禁止特徴形状の各データＰ
２、Ｐ３につき前記情報の過不足を評価し、この評価結
果に対応して初期最適粗サーチテンプレートＴ１につき
不足する破線の丸や三角で示す演算点Ｐ２ａ１やＰ３ａ
１を追加し、問題となる演算点を削除する。これにより
得た最適粗サーチテンプレートＴ２により画像データ１
ａとの前記パターンマッチングを行い、初期最適粗サー
チテンプレートＴ１の位置データに過不足がある万一の
場合に対応できるようにしている。最適粗サーチテンプ
レートＴ２に設定される特徴形状パターンＰ２ｂおよび
禁止特徴形状パターンＰ３ｂに対する追加演算点Ｐ２ａ
１やＰ３ａ１は、特徴形状データＰ２および禁止特徴形
状データＰ３を抽出したときに空き演算点となる部分を
双方に振り分けて離散させ巧みに設定することができ
る。

【００２９】このような最適粗サーチテンプレートＴ２
がパターンマッチングの精度上最適に設定される形態で
は、複数の対象物１、敷衍していえば必要なパターンマ
ッチング精度、画像認識精度が得られるだけの数の対象
物１について、粗サーチパターンマッチングを行い、得
た各回の正解パターンＴ・・と不正解パターンＨ₁、Ｈ
₂・・・を検出する粗サーチパターンマッチングに際し
ての一致度閾値を順次小さく変化させていき、検出数が
最も少なくなるように収束させたときの結果を用いるの
が好適である。

【００３０】ここに、最適粗サーチテンプレートＴ２を
得るための操作は、収集した正解パターンＴ部分の画像
と最適粗サーチテンプレートＴ２との一致度平均と、不
正解パターンＨ₁、Ｈ₂・・・部分の画像と最適粗サー
チテンプレートＴ２との一致度平均との差が最大になる
間引き操作である。最適粗サーチテンプレートＴ２によ
る実際のパターンマッチング処理に際し、同種の対象物
１でも製造ロットが異なるなどのためにこの条件が崩
れ、検出にＮＧが生じるような場合がある。そのような
ときは最適粗サーチテンプレートＴ２を図２の処理フロ
ーに示すように設定し直せば対処できる。

【００３１】ところで、対象物１の特定のパターンに
は、上記特徴形状パターンマッチングでは誤検出しやす
い微細特徴部分や認識対象部分と酷似する部分がある。
このような場合、それらの部分のパターンに合った精サ
ーチテンプレートを設定し、この精サーチテンプレート
によって特徴形状パターンマッチングの場合よりは密な
演算箇所によって精サーチパターンマッチングを行い、
特徴形状パターンマッチングおよび精サーチパターンマ
ッチング双方を満足する特定のパターン、つまり正解パ
ターンＴを検出し、対象物１の位置などの必要な情報を
画像認識できるようにする。これにより、特徴形状パタ
ーンマッチングによる特徴を活かしながら、特徴形状パ
ターンマッチングでは誤検出するような部分だけを精サ
ーチパターンマッチングを行って必要な精度を確保する
ことができる。精サーチテンプレートによる精サーチパ
ターンマッチングでの演算箇所は特徴形状パターンマッ
チングの場合よりも多く設定すればよいが、必要な精度
によっては全画素について演算するようにすれば検出精
度を最大にすることができる。このようにしても、精サ
ーチパターンマッチングは特定のパターンのうちの一部
につき行うだけであるので、演算点が特に膨大になって
パターンマッチング操作が長時間に及ぶようなことはな
い。

【００３２】本実施の形態のパターンマッチング装置
は、上記のようなパターンマッチング方法を実現するた
め図３に示すような構成を有している。撮像系１００は
撮像素子、撮像回路、および撮像光学系よりなり、回路
基板に装着して電子回路基板を製造するために供給さ
れ、あるいは搬送され、あるいは装着される電子部品な
どの対象物１につき、その位置や種類などの必要な情報
を画像認識したい工程部分に設置される。撮像系１００
が対象物１を撮像した濃淡画像の画像データ１ａは例え
ばパターンマッチング対象となる単位で濃淡画像入力部
１０１にてＡ／Ｄ変換してデジタル画像データとし、こ
れを濃淡画像記憶部１０２に入力するとともに、ビデオ
コントローラ１２１を介してモニタ１２２に表示される
ようにする。濃淡画像記憶部１０２では入力された画像
データを記憶しておき粗サーチ処理部１０３および精サ
ーチ処理部１０４からの要求に応じて出力する。

【００３３】粗サーチ処理部１０３は、サーチテンプレ
ートに関する外部入力１３１の基に粗サーチ教示部１０
５を通じ教示されたパターンに合った粗サーチテンプレ
ートデータ１１３、１つの実施例としては特定の部分パ
ターンにて８方向の空間一次微分を行ない微分値の大き
い点を各一次微分プレーン上で１とした８ビット画像と
した粗サーチテンプレートデータ１１３により、濃淡画
像記憶部１０２からの画像データ１１１について、予め
設定された緩和された演算点および一致閾値に基づき粗
サーチパターンマッチングをまず行う。粗サーチ処理部
１０３はまた粗サーチテンプレートデータ１１３により
検出したマッチングパターンをビデオコントローラ１２
１を介してモニタ１２２に表示し、人による前記正解パ
ターンＴなどと不正解パターンＨ₁、Ｈ₂・・・などと
の評価に供する。

【００３４】この人がした前記評価結果は外部入力１３
１として粗サーチ教示部１０５に教示され、粗サーチ教
示部１０５は教示された正解パターンＴのデータと不正
解パターンＨ₁、Ｈ₂・・・のデータとから、正解パタ
ーンＴに含まれ、不正解パターンＨ₁、Ｈ₂・・・に含
まれない、正解パターンＴを間引きした特徴形状データ
Ｐ２と、不正解パターンＨ₁、Ｈ₂・・・に含まれ、正
解パターンＴに含まれない不正解パターンを間引きした
禁止特徴形状データＰ３とを併せ持った初期最適粗サー
チテンプレートＴ１を上記操作で自動生成する。

【００３５】自動生成した初期最適粗サーチテンプレー
トＴ１のデータは外部入力１３２として粗サーチテンプ
レート最適化部１０７に入力されるとともに、ビデオコ
ントローラ１２１を通じてモニタ１２２で表示される。
このモニタ１２２への表示によって初期最適粗サーチテ
ンプレートＴ１に設定した特徴検出のための演算点の過
不足の評価に供する。粗サーチテンプレート最適化部１
０７は自動生成された初期最適粗サーチテンプレートＴ
１に対し、前記演算点の過不足の評価結果１３２の入力
に基づき不可欠な演算点の追加、不必要な演算点の削除
を行って、最適粗サーチテンプレートＴ２を自動生成
し、これを粗サーチ教示部１０５を通じ粗サーチ処理部
１０３に入力する。

【００３６】ここで、粗サーチ処理部１０３はそれ以
降、与えられた最適粗サーチテンプレトＴ２によって画
像データ１ａとの粗パターンマッチングによる少ない演
算点での低コストで高速かつ高精度なパターンマッチン
グを自動的に達成することができる。

【００３７】一方、精サーチ処理部１０４は精サーチテ
ンプレートに関する外部入力１３３の基に精サーチ教示
部１０６から教示される精サーチテンプレートデータ１
１４により濃淡画像記憶部１０２からの画像データ１ａ
における精サーチパターンマッチング対象領域の全画素
あるいは粗サーチパターンマッチングの場合よりは密に
設定した演算点に関しての精パターンマッチングを行
う。

【００３８】しかして、粗サーチ処理部１０３および精
サーチ処理部１０４がなす包括サーチ処理部１２３は、
粗サーチパターンマッチングと精サーチパターンマッチ
ングとの双方を満足した画像データを検出して対象物１
の必要情報が画像認識できるようにする。なお、図３の
装置で図２のフローに対応する部分は図２に示してい
る。

【００３９】粗サーチテンプレートの最適化処理した自
動生成は、例えば図６に示すようにシミュレーテッドア
ニーリング法（ＳＡ：ＳｉｍｕｌａｔｅｄＡｎｎｅａ
ｌｉｎｇ模擬徐冷法）を用いる。これの具体例は図４
に示してある。図４の不正解パターンＨ₁、Ｈ₂・・・
Ｈ_nである候補パターンと正解パターンＴである評価パ
ターンとの間の演算は両パターン間の一致度を計算す
る。これは最適化問題を解く汎用近似解法の１つであ
る。ＳＡ法の具体的な所定手順例を示すと以下の通りで
ある。

【００４０】（１）評価パターン演算点列、温度、徐
冷段階の初期化（２）エネルギ（候補パターンと評価パターンの一致
度）の計算（３）摂動を加える（演算点の位置を変更する）（４）エネルギの計算（５）状態の受理（摂動パターンを評価パターンに置
き換える）（６）指定の回数を（３）から繰り返す（７）徐冷（温度の更新）（８）ある条件（温度、エネルギ）を満たすまで
（３）から繰り返す評価パターンおよび候補パターンより各々演算点を抽出
し、ＳＡ法を用いて最適な演算点よりなる粗サーチテン
プレートに収束させる。ＳＡ法において収束を得るため
の条件を下記の表１に粗サーチテンプレート自動生成仕
様として示した。

【００４１】

【表１】なお、収束が得られる条件は複数存在する。また、摂動
−徐冷の停止条件は、摂動させても一致度の改善がそれ
以上得られない場合とする。表１の場合で、一致度閾値
の設定は初期閾値Ｔｓ＝３０．０から最終閾値Ｔｆ＝
０．１まで高めている。このための収束条件の設定はそ
れぞれの立場でした実験や経験を活かして行われるが、
１／２ずつ閾値を小さくしていき、それ以上改善できな
い限界まで前記（３）から以下の処理を繰り返せば充分
である。閾値の更新回数は３００回位いが上限と考えら
れるが、これに限られることはない。演算点の抽出はマ
トリクス状に並ぶ画素群における基準画素から縦横の４
方向に演算画素を設定していってもよいし、これに斜め
方向を加えた８方向に演算画素を設定していってもよ
い。

【００４２】上記最終閾値０．１の場合で最終演算点例
は５０×５０の画素のテンプレートに対して３２点と少
なくなり、大きく間引きして高精度なパターンマッチン
グ結果が得られる。

【００４３】

【発明の効果】本発明によれば、所定の一次微分操作に
よりパターンに合った粗さを満足して迅速かつ安定して
得られる粗サーチテンプレートを用いた粗サーチパター
ンマッチング結果による正解パターンと、これに類似し
誤検出されやすい不正解パターンに関する特定部分の特
徴形状データ、禁止特徴形状データに、それらの検出情
報の過不足を補正する最適化処理を施しただけで、演算
データ数が少ないが正解パターンおよび不正解パターン
を検出するには充分な特徴形状パターンおよび禁止特徴
形状パターンの位置データを１つの最適粗サーチテンプ
レートに設定して、この最適粗サーチテンプレート上の
特徴形状パターンおよび禁止特徴形状パターンによる少
ない各設定位置でのみ前記画像データとのマッチング演
算をすることにより、禁止特徴形状パターンとマッチン
グした画像データのそれ以上の操作を省きながら、特徴
形状パターンとマッチングする特定のパターンを検出し
て対象物の必要な情報を画像認識できるようにすること
が、低コストで高速かつ高精度に達成される。

【００４４】最適粗サーチテンプレートでの特徴形状パ
ターンマッチングでは誤検出しやすい微細特徴部分や非
認識部分と酷似する部分については、この部分に合った
精サーチテンプレートにより、粗サーチパターンマッチ
ングの場合よりは密な演算箇所にて精サーチパターンマ
ッチングを行い、特徴形状パターンマッチングおよび精
サーチパターンマッチング双方を満足した画像データを
検出して対象物の必要情報が画像認識できるようにし
て、最適粗サーチテンプレートでの特徴形状パターンマ
ッチングによる上記特徴を活かしながら、この特徴形状
パターンマッチングでは誤検出するような部分だけを精
サーチパターンマッチングを行って検出の必要精度を確
保することができる。

【図面の簡単な説明】

【図１】本発明の実施の形態におけるパターンマッチン
グ方法の１つの実施例を模擬的に示す説明図である。

【図２】図１のパターンマッチング方法における最適粗
サーチテンプレートの生成を伴う処理フローを模擬的に
示すフローチャートである。

【図３】図１のパターンマッチング方法を実現する本発
明の実施の形態におけるパターンマッチング装置の１つ
の実施例を示すブロック結線図である。

【図４】図２の処理フローで採用しているＳＡ法の処理
フローを示すフローチャートである。

【図５】従来のパターンマッチング方法でのテンプレー
トマッチング手法を模擬的に示す説明図である。

【図６】従来のパターンマッチング方法での間引きテン
プレートマッチング手法を模擬的に示す説明図である。

【符号の説明】

１対象物１ａ画像データ２粗サーチテンプレート１００撮像系１０１濃淡画像入力部１０２濃淡画像記憶部１０３粗サーチ処理部１０４精サーチ処理部１０５粗サーチ教示部１０６精サーチ教示部１０７粗サーチテンプレート最適化処理部１２２モニタ１２３包括サーチ処理部Ｔ正解パターンＨ₁、Ｈ₂ 不正解パターンＰ１ＯＲ画像Ｐ２特徴形状データＰ３禁止特徴形状データＴ１初期最適粗サーチテンプレートＴ２最適粗サーチテンプレートＰ２ａ１、Ｐ３ａ１追加演算点Ｐ２ｂ特徴形状パターンＰ３ｂ禁止特徴形状パターン

Claims

【特許請求の範囲】

【請求項１】対象物を撮像した画像データにつき、対
象物の情報を画像認識するのに必要な特定のパターンに
合わせて設定したサーチテンプレートにより、予め設定
した演算箇所およびパターン一致閾値に基づく粗サーチ
パターンマッチングを行い、検出された粗マッチングパ
ターンにつき正解、不正解の評価を行い、評価した正解
パターンと不正解パターンとから、正解パターンに含ま
れ不正解パターンに含まれない特徴形状データと、不正
解パターンに含まれ正解パターンに含まれない禁止特徴
形状データとを抽出して、それらに正解、不正解パター
ンを検出するための検出情報の過不足を補正する最適化
処理をした特徴形状パターンおよび禁止特徴形状パター
ンの位置データを持った最適粗サーチテンプレートを設
定し、この最適粗サーチテンプレート上の特徴形状パタ
ーンおよび禁止特徴形状パターンの各設定位置でのみ前
記画像データとのマッチング演算をし、禁止特徴形状パ
ターンとマッチングした画像データのそれ以上の処理操
作を排除しながら、特徴形状パターンとマッチングした
画像データを検出して対象物の必要情報が画像認識され
るようにすることを特徴とするパターンマッチング方
法。
【請求項２】対象物を撮像した画像データにつき、対
象物の情報を画像認識するのに必要な特定の部分パター
ンにて、複数方向の空間一次微分を行なって微分値の大
きい点を各一次微分プレーン上で１とする必要ビット数
のサーチテンプレートを設定し、このサーチテンプレー
トにより、予め設定した演算箇所およびパターン一致閾
値に基づく粗サーチパターンマッチングを行い、検出さ
れた粗マッチングパターンにつき正解、不正解の評価を
行い、評価した正解パターンと不正解パターンとから、
正解パターンに含まれ不正解パターンに含まれない特徴
形状データと、不正解パターンに含まれ正解パターンに
含まれない禁止特徴形状データとを抽出して、それらに
正解、不正解パターンを検出するための検出情報の過不
足を補正する最適化処理をした特徴形状パターンおよび
禁止特徴形状パターンの位置データを持った最適粗サー
チテンプレートを設定し、この最適粗サーチテンプレー
ト上の特徴形状パターンおよび禁止特徴形状パターンの
各設定位置でのみ前記画像データとのマッチング演算を
し、禁止特徴形状パターンとマッチングした画像データ
のそれ以上の処理操作を排除しながら、特徴形状パター
ンとマッチングした画像データを検出して対象物の必要
情報が画像認識されるようにすることを特徴とするパタ
ーンマッチング方法。
【請求項３】空間一次微分の方向は８方向であり、必
要ビット数は８である請求項２に記載のパターンマッチ
ング方法。
【請求項４】最適化処理は、特徴形状データおよび禁
止特徴形状データにつき、特徴形状パターンマッチング
において正解、不正解パターンの検出上欠かせない位置
データを追加し、不必要な位置データを除去する請求項
１〜３のいずれか１項に記載のパターンマッチング方
法。
【請求項５】最適粗サーチテンプレートは、複数の対
象物につき粗サーチパターンマッチングを繰り返し行っ
て収集した正解パターンと不正解パターンとから生成す
る請求項１〜４のいずれか１項に記載のパターンマッチ
ング方法。
【請求項６】最適粗サーチテンプレートによる特徴形
状パターンマッチングでは誤検出しやすい微細な特徴部
分や認識対象部分と酷似する部分については、その部分
に合った精サーチテンプレートにより、特徴形状パター
ンマッチングの場合よりは密な演算箇所で精サーチパタ
ーンマッチングを行い、特徴形状パターンマッチングお
よび精サーチパターンマッチング双方を満足した画像デ
ータを検出して対象物の必要情報が画像認識されるよう
にする請求項１〜４のいずれか１項に記載のパターンマ
ッチング方法。
【請求項７】入力される撮像された対象物の画像デー
タを記憶する画像記憶手段と、対象物の必要情報を画像
認識するのに必要な特定のパターンに合った粗サーチテ
ンプレートを教示する粗サーチテンプレート教示手段
と、教示された粗サーチテンプレートにより予め設定さ
れた所定の演算箇所およびパターン一致閾値に基づき画
像記憶手段からの画像データにつき粗サーチパターンマ
ッチングを行い、検出した粗マッチングパターンを記憶
するとともに表示する粗サーチ処理手段と、検出された
粗マッチングパターンの人による正解、不正解の評価に
基づく正解パターンと不正解パターンとから、正解パタ
ーンに含まれ不正解パターンに含まれない特徴形状デー
タと、不正解パターンに含まれ正解パターンに含まれな
い禁止特徴形状データとを抽出して表示し、かつそれら
による正解パターンおよび不正解パターンの検出のため
の情報の過不足の教示の基に特徴データおよび禁止特徴
データを補正する最適化処理して得た特徴形状パターン
および禁止特徴形状パターンの位置データを持った最適
粗サーチテンプレートを生成する粗サーチテンプレート
最適化処理部とを備え、粗サーチ処理手段はこの最適粗
サーチテンプレート上の特徴形状パターンおよび禁止特
徴形状パターンの各設定位置でのみ前記画像データとの
パターンマッチングの演算をし、演算の結果禁止特徴形
状パターンとマッチングした画像データについてのそれ
以上の処理操作を省きながら、特徴形状パターンとマッ
チングする画像データを検出して対象物の必要情報が画
像認識されるようにしたことを特徴とするパターンマッ
チング装置。
【請求項８】入力される撮像された対象物の画像デー
タを記憶する画像記憶手段と、対象物の必要情報を画像
認識するのに必要な特定の部分パターンにて、複数方向
の空間一次微分を行ない微分値の大きい点を各一次微分
プレーン上で１とした必要ビット数のパターンに合った
粗サーチテンプレートを教示する粗サーチテンプレート
教示手段と、教示された粗サーチテンプレートにより予
め設定された所定の演算箇所およびパターン一致閾値に
基づき画像記憶手段からの画像データにつき粗サーチパ
ターンマッチングを行い、検出した粗マッチングパター
ンを記憶するとともに表示する粗サーチ処理手段と、検
出された粗マッチングパターンの人による正解、不正解
の評価に基づく正解パターンと不正解パターンとから、
正解パターンに含まれ不正解パターンに含まれない特徴
形状データと、不正解パターンに含まれ正解パターンに
含まれない禁止特徴形状データとを抽出して表示し、か
つそれらによる正解パターンおよび不正解パターンの検
出のための情報の過不足の教示の基に特徴データおよび
禁止特徴データを補正する最適化処理して得た特徴形状
パターンおよび禁止特徴形状パターンの位置データを持
った最適粗サーチテンプレートを生成する粗サーチテン
プレート最適化処理部とを備え、粗サーチ処理手段はこ
の最適粗サーチテンプレート上の特徴形状パターンおよ
び禁止特徴形状パターンの各設定位置でのみ前記画像デ
ータとのパターンマッチングの演算をし、演算の結果禁
止特徴形状パターンとマッチングした画像データについ
てのそれ以上の処理操作を省きながら、特徴形状パター
ンとマッチングする画像データを検出して対象物の必要
情報が画像認識されるようにしたことを特徴とするパタ
ーンマッチング装置。
【請求項９】空間一次微分の必要方向は８方向であ
り、必要ビット数は８である請求項８に記載のパターン
マッチング装置。
【請求項１０】最適粗サーチテンプレートによる特徴
形状パターンマッチングでは誤検出しやすい微細特徴部
分や認識対象部分と酷似する部分に合った精サーチテン
プレートを教示する精サーチテンプレート教示手段と、
教示された精サーチテンプレートにより粗サーチパター
ンマッチングの場合よりは密な演算箇所にて画像データ
との精サーチパターンマッチングを行う精サーチ処理手
段とを備え、特徴形状パターンマッチングおよび精サー
チパターンマッチングの双方を満足するパターンを検出
して対象物の必要情報が画像認識されるようにする請求
項７〜９のいずれか１項に記載のパターンマッチング装
置。