(57)【要約】【課題】照合ベクトル数の削減、照合処理の簡略化による高速化、無駄なテンプレート変動の削除による照合回数の削減の３つを総合的に制御することによって、形状ベースの回転・スケール変動に対応するマッチング処理における高速化を図る。【解決手段】モデル領域におけるエッジ点のｘ、ｙ位置と、勾配方向θとで濃度勾配ベクトルを表わし、複数の濃度勾配ベクトルからなるテンプレートデータを用いる形状マッチング処理において、予め、サーチ画像の回転・スケール等の変動範囲に合わせて、テンプレートを構成するベクトルを変動させ、ベクトルが存在し得る位置を網羅し、その位置における重み情報を持ったマスクパターンを作成し、サーチ画像上の任意の位置で変動照合が必要かどうかを、このマスクパターンを用いて計算した一致度で判定し、一致度が低い場合、無駄な回転・スケール等の変動による照合処理を削減して、高速化を図る。【選択図】図１３
2008293073.tif 000002
【特許請求の範囲】
【請求項１】
モデル領域におけるエッジ点のｘ、ｙ位置と、勾配方向θとで濃度勾配ベクトルを表わし、複数の濃度勾配ベクトルからなるテンプレートデータを用いる形状マッチング処理において、
予め、サーチ画像の回転・スケール等の変動範囲に合わせて、テンプレートを構成するベクトルを変動させ、ベクトルが存在し得る位置を網羅し、その位置における重み情報を持ったマスクパターンを作成し、
サーチ画像上の任意の位置で変動照合が必要かどうかを、このマスクパターンを用いて計算した一致度で判定し、
一致度が低い場合、無駄な回転・スケール等の変動による照合処理を削減して、高速化を図ることを特徴とする画像のマッチング処理方法。
【請求項２】
前記サーチ画像の回転・スケール等の変動範囲に合わせて、テンプレートを構成するベクトルを変動させ、マスクパターンを作成する際に、ベクトル軌跡の重複点において重複数をカウントし、ベクトルが存在する頻度や共通形状を示す重み情報として付加し、一致度の重み付け、照合演算の順序制御に用い、より早期に照合演算を打ち切ることを特徴とする請求項１に記載の画像のマッチング処理方法。
【請求項３】
前記テンプレートとの相関値を計算する過程で、未計算部分の結果が最大値であると見做し、その時点での最高点を予測し、現在の最高点を上回ることができないと判断した場合に照合演算を打ち切ることを特徴とする請求項１又は２に記載の画像のマッチング処理方法。
【請求項４】
前記モデル領域をいくつかのブロックに分け、それぞれに属する濃度勾配ベクトル方向データの分散を求め、分散値が低いブロック、即ち方向変化が少ない部分のベクトルを抽出し、ベクトル自身の重み情報を設定し、ベクトル自身の重み情報をそのベクトルが関与するマスクパターンの重み情報に加味し、マスクパターンの重み情報をフィードバックし、ベクトル自身の重み情報を再調整して、相関値の演算結果をより安定させ、マッチング結果の繰り返し精度を向上させることを特徴とする請求項１に記載の画像のマッチング処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子部品の位置決めや方向判別等のためにベクトル相関マッチングを行なう際に、高速に位置合わせするための画像のマッチング処理方法に関する。
【背景技術】
【０００２】
従来、電子部品搭載装置では、吸着ノズルで吸着された電子部品の吸着姿勢を認識するのに、ＣＣＤカメラにより撮像された電子部品の画像と、予め作成された電子部品のテンプレートによるテンプレートマッチンクが用いられている。
【０００３】
このテンプレートマッチングにおいて、画像の全ての画素のデータについてマッチング演算を行なうと、演算量が膨大になるので、従来から、対象となる画素を何らかの条件で絞り込み、演算の高速化を図る手法が採られている。例えば、エッジ強度が強いものを選択する方法があり、ソーベル等のエッジ検出フィルタをかけて、エッジ強さを求め、ある閾値を設けて、対象となる画素を絞り込んでいた。又、エッジ点列の曲率の大きい部分は密に、曲率の小さな部分は粗にするという方法（特許文献１）や、テンプレート画像上での空間分布やエッジの方向性が、ある程度一様になるように間引く（特許文献２）等の方法がある。
【０００４】
【特許文献１】特許第２９８９６８８号公報
【特許文献２】特許第２６８１３８２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、エッジ強さ等を用いて照合ベクトル数を削減する方法だけでは、回転変動や倍率（スケール）変動等、更に変動範囲を拡大した場合の演算量の増加に対して、無駄なテンプレート変動を削減することができず、十分な高速化を行なうことはできない。
【０００６】
形状ベースマッチングでは対象が輪郭線だけであり、相関値は濃度情報を全部用いた正規化相関法に比べて、変動に対して急峻な特性を持つ。そのため、正規化相関法のように近傍のマッチング結果で変動範囲を間引くと、漏れが発生する可能性がある。しかし、変動範囲を間引かずに全て演算すると、膨大な演算量となってしまう。又、形状ベースのマッチングにおいては、実画像のコントラストの変動に合わせて、コントラストが変化してもサーチできるように、コントラストのロバスト性を考慮しなければならない。従って、サーチ画像について、コントラストによって変化するエッジ強さで照合ベクトルを絞り込むことはできない。
【０００７】
その他の高速化手法として、ＳＳＤＡ（Ｓiquential  Ｓimilarity  Ｄetection  Ａlgorithm）法（残差逐次検査法）等、照合処理を途中で打ち切り、高速化を図る方式もあるが、ベクトル数の削減と同様、無駄なテンプレート変動を削除する方法ではないので、やはり、変動範囲を拡大した場合の演算量の増加に対して効果は小さい。又、打ち切りのための閾値の設定をどのように制御すればいいのかという問題や、打ち切りのタイミングをより早めるための照合演算の順序をどのように制御すればいいのかという問題もある。従来は、コントラスト情報を用いて制御する方法が一般的であるが、コントラストのロバスト性を考慮する場合、別の判定基準が必要である。
【０００８】
本発明は、前記従来の問題点を解消するべくなされたもので、照合ベクトル数の削減、照合処理の簡略化による高速化、無駄なテンプレート変動の削除による照合回数の削減の３つを総合的に制御することによって、形状ベースの回転・スケール変動に対応するマッチング処理における高速化を図ることを課題とする。
【課題を解決するための手段】
【０００９】
本発明は、モデル領域におけるエッジ点のｘ、ｙ位置と、勾配方向θとで濃度勾配ベクトルを表わし、複数の濃度勾配ベクトルからなるテンプレートデータを用いる形状マッチング処理において、予め、サーチ画像の回転・スケール等の変動範囲に合わせて、テンプレートを構成するベクトルを変動させ、ベクトルが存在し得る位置を網羅し、その位置における重み情報を持ったマスクパターンを作成し、サーチ画像上の任意の位置で変動照合が必要かどうかを、このマスクパターンを用いて計算した一致度で判定し、一致度が低い場合、無駄な回転・スケール等の変動による照合処理を削減して、高速化を図ることにより、前記課題を解決したものである。
【００１０】
又、前記サーチ画像の回転・スケール等の変動範囲に合わせて、テンプレートを構成するベクトルを変動させ、マスクパターンを作成する際に、ベクトル軌跡の重複点において重複数をカウントし、ベクトルが存在する頻度や共通形状を示す重み情報として付加し、一致度の重み付け、照合演算の順序制御に用い、より早期に照合演算を打ち切ることができる。
【００１１】
又、前記テンプレートとの相関値を計算する過程で、未計算部分の結果が最大値であると見做し、その時点での最高点を予測し、現在の最高点を上回ることができないと判断した場合に照合演算を打ち切ることができる。
【００１２】
又、前記モデル領域をいくつかのブロックに分け、それぞれに属する濃度勾配ベクトル方向データの分散を求め、分散値が低いブロック、即ち方向変化が少ない部分のベクトルを抽出し、ベクトル自身の重み情報を設定し、ベクトル自身の重み情報をそのベクトルが関与するマスクパターンの重み情報に加味し、マスクパターンの重み情報をフィードバックし、ベクトル自身の重み情報を再調整して、相関値の演算結果をより安定させ、マッチング結果の繰り返し精度を向上させることができる。
【発明の効果】
【００１３】
本発明によれば、重み情報付きマスクパターンを用いて、サーチ画像上の任意の位置で変動照合が必要かどうか判定でき、無駄なテンプレート変動による照合処理を削減でき、高速化が図れる。
【００１４】
又、マスクパターンの重み情報の順に照合演算を行なうことで、早期に照合演算を打ち切ることができ、高速化が図れる。マスクパターンの重み情報は、テンプレートを変動させた場合に取得できる重複カウントを元に設定する（変動テンプレートの共通部分の重みが高くなる）。
【００１５】
更に、類似度を計算する過程で、未計算部分の結果が最大値であるとみなし、その時点での最高点を予測し、現在の最高点を上回ることができないと判断した場合に照合演算を打ち切ることで、高速化が図れる。
【００１６】
又、濃度勾配ベクトルの方向変化が少なく、分散値が小さい直線状の部分について、この重みを更に上げることで、安定した一致度を得ることができ、位置決め結果の繰り返し精度が向上する。
【００１７】
又、階層マッチングの上位層において、この重み情報を用いて照合ベクトル数の削減をすることで、高速化が図れる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照して、本発明の実施形態を詳細に説明する。
【００１９】
図１は、本発明を実施するのに用いられるシステムの構成図である。
【００２０】
このシステムは、電子部品２を吸着し、撮像位置へセットするための吸着ノズル１と、該吸着ノズル１や照明装置３等の動作を制御するマシン制御装置１３と、電子部品２を撮像するための標準カメラ４及び高解像度カメラ５と、撮像された画像を処理して画像内のある位置に存在する対象物の位置検出や形状を判別する画像処理装置１２とによって構成される。
【００２１】
前記マシン制御装置１３は、通常、電子部品の電極サイズによって、撮像するカメラ４又は５を選択し、電子部品２を吸着ノズル１で吸着し、選択したカメラの撮像位置にセットする。更に、照明装置３を選択したカメラで撮像できるよう移動、点灯させ、画像処理装置１２にインタフェース１１を介して、選択したカメラチャネル情報と共に処理実行を指示する。
【００２２】
前記画像処理装置１２は、指定されたカメラ４又は５を制御し、電子部品の画像を撮像し、Ａ／Ｄコンバータ６でデジタル化し、画像メモリ７に多値画像データとして記憶させる。この画像処理装置１２は、画像メモリ７のデータに対して、各種処理を行ない、電子部品２の位置決め、形状判別のためのテンプレートデータを作成する。途中、生成させる処理データは、作業用メモリ８に記憶される。
【００２３】
以下、図２を参照して、テンプレート作成の手順を詳細に説明する。
【００２４】
まず、電子部品の画像を撮像し、Ａ／Ｄコンバータ６でデジタル化し、画像メモリ７に多値画像データとして記憶させる（Ｓ１）。
【００２５】
次いで、エッジ抽出処理を行ない、抽出データを作業用メモリ８に格納する（Ｓ２）。
【００２６】
次に、抽出したエッジ点についてラベリング処理を行ない、連結し、輪郭線として分類したデータ管理を行なえるようにする（Ｓ３）。
【００２７】
輪郭線で表される形状のサイズが小さいと細かな形状の判別ができないので、エッジエンベロプ検査を行ない、一定サイズ以下の場合は必要な形状サイズが得られるように、画像メモリ７のデータに対して拡大処理を行ない、再度、エッジ抽出処理を行なう（Ｓ７）。
【００２８】
更に、ノイズ成分の除去（Ｓ４）を行ない、高速化のために有効なエッジのみに絞り込み（Ｓ５）、最後に、テンプレートデータとして、テンプレートデータ格納メモリ１０に格納する（Ｓ６）。
【００２９】
図３にテンプレートデータの構成を示す。データは、テンプレート自体の属性を示すデータと、濃度勾配ベクトルデータの２つに分類できる。テンプレート属性データには、テンプレートサイズ、中心オフセット、ピクセルレート、類似度の閾値、拡大倍率等がある。濃度勾配ベクトルは、座標、方向で表現できる。これに重みを加えたものを基本データ構造とする。更に、検出状況の解析のために検出に用いたフィルタサイズ、検出したベクトル強さ等のデータを追加しておいてもよい。
【００３０】
本発明は、このように作成したテンプレートデータを用いて、回転・スケール変動のある対象物を含む任意の入力画像から高速に対象物の位置検出をするためのマッチング処理方法に関するものである。
【００３１】
本発明では、予め、サーチ画像内での対象物の回転・スケール等の変動範囲に合わせて、テンプレートを構成するベクトルを変動させ、ベクトルが存在し得る位置を網羅したマスクパターンを作成する。
【００３２】
図４にマスクパターン概念を示す。例えば、テンプレート画像として、塗りつぶされた四角形の対象物（図４（Ａ））を登録する。このとき、得られるテンプレートデータのイメージは、図４（Ｂ）のようになる。四角形のエッジ部分が抽出され、輪郭線上のベクトルデータがテンプレートデータとして構成される。
【００３３】
マスクパターンとは、サーチ画像の任意の点において、サーチ画像内での対象物の変動範囲を考慮して、これらテンプレートを構成するベクトルが存在し得る位置を示したデータである。即ち、図４（Ｂ）を最大範囲で変動させたときの軌跡のＯＲ画像となる。
【００３４】
このとき、ベクトル軌跡の各位置において重複数をカウントし、ベクトルが存在する頻度や共通部分を示す情報（以下、重み情報と記載）として記録しておく。サーチ画像上の任意の位置で、このマスクパターンとの一致度を計算し、照合処理が必要かどうかを判定し、無駄な回転・スケール等の変動による照合処理を削減して、高速化を図ることができる。
【００３５】
マスクパターンのデータ構造を図５に示す。マスクパターンは、ビットマップデータとして表現する（図５（Ａ））。該当位置にベクトルが存在し得ない場合には０、ベクトルが存在し得る場合は、軌跡の重なり度と、そのベクトル自体の重み情報から、その位置の重み情報を計算し、設定する。マスクパターンフィッティング判定を高速化するためには、より重みの高い点から演算してやればよい。
【００３６】
重み情報の大きい、即ち影響力の大きなベクトルから演算するようにすれば、より早期に打ち切り判定ができ、高速化を図ることができる。そのために、各点のフィッティング順序を記述したインデックス配列を用意しておく（図５（Ｂ））。例えば、重みの高い順に、もし同一であるならラスタスキャンの順に並べていけばよい。
【００３７】
このような考え方は、照合演算の順序制御に用いることもできる。この場合は、ベクトル自体の重み情報を利用してやればよい。
【００３８】
ベクトルの重み付けは、例えば図６（Ａ）に示す如く、モデル領域をいくつかのブロックに分け、それぞれに属する濃度勾配ベクトル方向データの分散を求め、この値を元に設定することができる。分散値は、ベクトルが同じ方向に揃っていれば小さく、ばらばらであれば大きくなる。図６（Ｂ）は、分散値を用いて、ブロック毎に１０段階で重み付けした例であり、ベクトルが同じ方向に揃っている程、重みは大きくなる。
【００３９】
分散値が低いブロック、即ち方向変化が少ない部分のベクトル群は、直線形状を示し安定しているので、これらのベクトルに重み付けすることで、相関値の演算結果をより安定させ、マッチング結果の繰り返し精度を向上させることができる。
【００４０】
又、分散値が高いブロック、即ち方向変化が激しい部分のベクトル群は、複雑な形状を示す部分であり、形状が不一致の場合、相関値は著しく低下する性質を持つので、先に演算して、計算を早く打ち切れるようにした方がよい。このような情報、更にこれらのベクトル群が関与するマスクパターンの重み情報を調整し、重みの大きい順に、図７に示すベクトルインデックスを用いて、データ本体でなくインデックスについて順序制御することで、先に記載した高速化の効果を増幅させることができる。
【００４１】
又、階層マッチングの上位層データ作成において、この情報を用いて、照合ベクトルの選定を行ない、ベクトル数を削減し、高速化を図ることもできる。
【００４２】
図８に階層データの構造を示す。階層データは、ある局所領域の中で重み付け情報を参照し、最低値以上で、且つ最大のものを選ぶようにして作成する。例えば、１層は近隣の２×２の４画素を、２層は４×４の１６画素を、３層は８×８の６４画素を局所領域として処理する。一つ下の層のデータを用いて、常に４画素を局所領域として処理すれば高速化が図れる。このとき、階層インデックスは早期打ち切りのための演算順序を考慮した並べ替えを同時に行なっておく。
【００４３】
このように本発明のマッチング処理では、照合ベクトル数の削減、照合処理の高速化、無駄なテンプレート変動の削除の３つの要素をマスクパターンを通して相互に組み合わせ、高速化を実現している。
【００４４】
次に、フローチャートに沿って、図１の画像処理装置１２での個々の処理について詳細に説明する。
【００４５】
図９はテンプレート前処理の手順を示す。画像処理装置１２は、テンプレートデータ格納メモリ１０より、該当するテンプレートデータを探し出し、作業用メモリ８に展開し、処理を行なう。これらの処理はマッチング処理の前に行なっておく。
【００４６】
まず、テンプレートを構成するベクトル毎の重みを計算する（Ｓ１１）。重みの計算はいろいろな手段が考えられるが、より精度を安定させるために、影響度を大きくすべきベクトルに重み付けを行なうという考え方で手段を実装しなければならない。図１０に、その一例を示す。
【００４７】
図１０に示したベクトルの重み計算の具体的な手順は、次のとおりである。
【００４８】
（１）テンプレート領域ブロック分割（Ｓ２１）
分割数はいくつでも構わない。処理時間や対象物の形状を考慮して決めればよい。例えば、図６のようにテンプレート領域を９の領域に分割する。
【００４９】
（２）各部ブロック内ベクトル勾配方向分散計算（Ｓ２２）
各ブロック内のベクトルに対して、勾配方向の分散を計算する。
【００５０】
（３）処理ブロック更新（Ｓ２３）
処理ブロックを更新し、全てのブロックに対して（Ｓ２２）の処理を繰り返す。
【００５１】
（４）分散値の正規化と調整（Ｓ２４）
分散値の最小値、最大値を求め、１０段階に正規化、その他の重み付け要素（重複数カウント値）と調整する。例えば、重複数カウント値との荷重平均をとる。
【００５２】
（５）ベクトルデータに重みとして展開（Ｓ２５）
Ｓ２３で決まった重みをブロック内の各ベクトルに展開する。
【００５３】
（６）インデックスに演算情報として展開（Ｓ２６）
重み情報を用いて、ベクトルの演算順序を決め、図７に示したベクトルインデックスに展開する。
【００５４】
次に図９に戻り、テンプレートを構成するベクトル座標点を変動させた軌跡を重ね合わせ、マスクパターンを作成する（Ｓ１２）。マスクパターンの各点の重み情報は、ベクトル自体の重みと、その重なり度で計算する。マスクパターンの各点の重み情報は、マスクパターン完成後にベクトル毎の重みにフィードバックし、ベクトル自身の重みも変動時の重なり度を加味したものとする。
【００５５】
図９のステップＳ１２のマスクパターン作成は、図１１に示す手順に従って行なう。
【００５６】
（１）テンプレート変動領域サイズ計算（Ｓ３１）
テンプレートを変動範囲の最大に拡大し、４５°回転させたときのエンベロプ（対角長さ）がマスクパターンのサイズとなる。マスクパターンは作業用メモリ８に確保される。マスクパターンは、マスクパターン中心とテンプレート中心を一致させてテンプレートを配置し、テンプレートの左上を原点とする座標系で管理する。
【００５７】
（２）ビットマップデータクリア（Ｓ３２）
Ｓ３１で確保したマスクパターンを全て０でクリアする。
【００５８】
（３）回転変動（Ｓ３３）
対象物の回転変動範囲の最小値を初期値として設定、最大値まで更新を繰り返す。
【００５９】
（４）スケール変動（Ｓ３４）
対象物のスケール変動範囲の最小値を初期値として設定、最大値まで更新を繰り返す。
【００６０】
（５）軌跡（重複カウント）セット（Ｓ３５）
Ｓ３３、Ｓ３４で設定された変動量でテンプレートデータをアフィン変換し、ビットマップデータ上の座標を計算、軌跡座標のデータをカウントアップしていく。このとき、各ベクトルに設定された重み情報をカウント値として足し込んでいく。
【００６１】
（６）膨張処理（Ｓ３６）
対象物の形状ずれを考慮して、Ｓ３５までの処理で得られたパターンに対して膨張処理を行なう。膨張レベルは、対象物の形状の誤差を考慮して設定すればよい。
【００６２】
（７）重み情報正規化（Ｓ３７）
重み情報を０〜１０の範囲で正規化する。
【００６３】
（８）フィッティング順序インデックス作成（Ｓ３８）
マスクパターンを重み情報の上位から順にラスタスキャンし、設定する。インデックスはマスクパターンの全ての点を網羅する必要はない。そこにパターンがないと判断できる数まで作成すればよい。
【００６４】
（９）重み情報をベクトルデータにフィードバックする（Ｓ３９）
具体的な計算方法は、いろいろ考えられるが、例えば、各ベクトルの変動軌跡上の重みの平均値を求め、更に元の重み情報と平均する。
【００６５】
Ｓ３９終了後、図９に戻り、最後に、階層テンプレートを作成する（Ｓ１３）。
【００６６】
図１２にマッチング処理全体フローを示す。
【００６７】
まず、サーチ画像よりベクトルを抽出する（Ｓ４１）。基本的に、図２に示すテンプレート画像に対する処理と同じ処理となる。但し、サーチ画像の場合、エッジ選択処理（図２のＳ５）は行なわない。サーチ画像には、テンプレートとして登録された以外の形状も含まれることがあり、テンプレート画像と同じ基準で絞り込みを行なうことはできない。ノイズ成分を取り除いた全てのベクトルを残す。抽出されたベクトルは、方向と強さ、それぞれ独立したビットマップ形式のデータとして作業用メモリ８に出力される。
【００６８】
次に、サーチ領域の絞り込みを行なう（Ｓ４２）。サーチ画像内のベクトルが存在する矩形領域をマッチング領域とすることで、無駄な照合を省き、高速化を図ることができる。
【００６９】
次に、絞り込んだサーチ領域について、階層データを作成する（Ｓ４３）。サーチ画像の階層データは、ベクトルの強さで照合ベクトルを選択する。局所領域の最大強さのベクトルを照合ベクトルとして選択する。入力画像と同様に、抽出されたベクトルは、方向と強さ、それぞれ独立したビットマップ形式のデータとして作業用メモリ８に出力される。
【００７０】
そして、階層サーチ（Ｓ４４）を行ない、変動範囲に絞り込んだ後、最終層のサーチ（Ｓ４５）を行ない、位置検出が完了する。
【００７１】
本発明の演算処理の打ち切りは、Ｓ４４の階層サーチに適用される。最終層サーチは、ほぼそこに対象物があることが前提であり、より高精度の位置検出を行なう処理であるので、本発明の手法は適用しない。演算の打ち切り判定処理を省く方が高速になる。
【００７２】
図１２のＳ４４の階層サーチとは、図１３に詳細に示す如く、より粗い解像度の上位の層から順にサーチを繰り返し、下位の層のサーチ領域の絞り込みを行ない、高速化を図る手法である。最終層−１でのサーチが終了したら（Ｓ５１）終了となる。
【００７３】
階層サーチでは、まずサーチ階層の変動テンプレートの作成を行なう（Ｓ５２）。基準姿勢のテンプレートをアフィン変換して、回転・スケール変動範囲に合わせて複数枚のテンプレートを作成する。メモリ容量があれば、テンプレート前処理の階層テンプレート作成の中に含め、予め作成しておくことでより高速化が図れる。
【００７４】
照合処理は、テンプレートの平行移動を基準に行なう（Ｓ５３、Ｓ５７）。
【００７５】
まず、サーチ画像上で（ｘ，ｙ）を設定し、その位置に対して、マスクパターンフィッティング（Ｓ５４）を行なう。
【００７６】
図１４にマスクパターンフィッティングの具体的な手順を示す。このマスクパターンフィッティングの手順は、次のとおりである。
【００７７】
（１）フィッティングインデックスカウンタ初期化（Ｓ６１）
カウンタを０に初期化する。
【００７８】
（２）入力画像位置計算（Ｓ６２）
カウンタが示すインデックス番号を取得、参照するマスクパターン位置情報を取り出し、入力画像の参照位置を計算する。
【００７９】
（３）ベクトル強さ参照（Ｓ６３）
Ｓ６２の位置のベクトル強さを参照し、その位置にベクトルが存在するか判定する。
【００８０】
（４）一致度更新（Ｓ６４）
ベクトルが存在するならば、一致度をカウントアップしていく。
【００８１】
（５）一致度判定（Ｓ６５）
テンプレートのベクトル数に対して設定された最低値に対して比較を行なう。
【００８２】
（６）照合処理必要（Ｓ６７）
Ｓ６５の結果、最低値以上の一致度が確認できたならば、照合処理が必要と判定し、即座にフィッティング処理を打ち切り、照合処理へ移る。
【００８３】
（７）フィッティングインデックスカウンタ更新（Ｓ６６）
そうでない場合は、カウンタを更新し、次のベクトルについての処理に移る。
【００８４】
（８）照合処理不要（Ｓ６８）
全てのベクトルについて行なっても、一致度が上がらなかった場合は、照合処理不要と判定する。
【００８５】
図１４終了後、図１３に戻り、マスクパターンフィッティングの戻り値により、照合処理の有無を判定する（Ｓ５５）。マスクパターンとの一致度が低い場合、その位置での照合処理は省くことができ、高速化が図れる。
【００８６】
照合処理が必要と判断したならば、回転・スケール変動照合処理（Ｓ５６）を行なう。
【００８７】
これらの処理をサーチ領域内で繰り返し行ない（Ｓ５７）、最大値の座標点を検出し、その周辺を下位の層のサーチ領域として（Ｓ５８）、同様の処理を繰り返す。
【００８８】
図１５に、図１３のＳ５６の回転・スケール変動照合処理の具体的な手順を示す。
【００８９】
回転・スケール変動は、テンプレート中心を基準として行なう。変動範囲の最小値を初期値とし、最大値になるまで、回転・スケールについてそれぞれ繰り返し処理を行なう。まず、回転速度、スケールを設定し、照合演算（Ｓ７３）を行ない、類似度を算出する。
【００９０】
図１６に、図１５のＳ６３の照合演算処理の具体的な手順を示す。この照合演算処理の手順は、次のとおりである。
【００９１】
（１）ベクトルインデックスカウンタ初期化（Ｓ８１）
カウンタを０に初期化する。
【００９２】
（２）入力画像位置計算（Ｓ８２）
カウンタが示すインデックス番号を取得、テンプレート・ベクトルの位置情報を取り出し、入力画像の参照位置を計算する。
【００９３】
（３）ベクトル強さ参照（Ｓ８３）
Ｓ８２の位置のベクトル強さを参照し、その位置にベクトルが存在するか判定する。
【００９４】
（４）相関演算（Ｓ８４）
ベクトルが存在するならば、相関値を演算する。相関演算は２つのベクトルの類似度を示す値で、０〜１の値として表現する。一般的にはベクトルの内積を用いて計算される。
2008293073.tif 000003
【００９５】
本実施形態では、２つのベクトルの勾配方向θの差分の余弦（cos）を取り、重み付けしている。
2008293073.tif 000004
【００９６】
（５）相関値予測値変更（Ｓ８５）
未計算部分のベクトルの相関値が全て１であったとした場合の平均相関値を予測値とする。
【００９７】
（６）相関値予測値判定（Ｓ８６）
現在の最高点を上回ることができるかできないかを判定する。
【００９８】
（７）打ち切り終了（Ｓ８７）
現在の最高点を上回ることができないことが確定した場合、演算は打ち切り、終了となる。
【００９９】
（８）ベクトルインデックスカウンタ更新（Ｓ８８）
確定しない場合は、カウンタをインクリメントし、次のベクトルに対して、Ｓ８２〜Ｓ８６の処理を繰り返す。
【０１００】
相関値が低い箇所での照合演算は途中で打ち切り、最後まで計算されない。又、演算が打ち切られた場合は、最終的な相関値は求まらない。
【０１０１】
図１６終了後、図１５に戻り、算出した相関値が現在の最大値を超えるか判定し（Ｓ６４）、最大値を超えるならば、最大値を更新する（Ｓ６５）。
【０１０２】
これらの処理をスケールを変動させ、繰り返し行なう（Ｓ６２〜Ｓ６６）。
【０１０３】
更に、回転角度を変動させ、繰り返し行なう（Ｓ６１〜Ｓ６７）。
【０１０４】
本実施形態においては、階層サーチデータ上位層の作成において、重み情報を用いて照合ベクトル数を削減し、更にインデックス配列を用いて、元ベクトルのデータを指し示すようにしたので、演算順序を制御し、高速化を図りつつ、且つ階層サーチデータをコンパクトにすることができる。
【図面の簡単な説明】
【０１０５】
【図１】本発明に用いられる画像処理装置の構成を示したブロック図
【図２】本発明の実施形態におけるテンプレート作成の手順を示す流れ図
【図３】同じくテンプレートデータの例を示す図
【図４】同じくマスクパターンの概念を示す図
【図５】同じくマスクパターンのデータ構造の例を示す図
【図６】同じくベクトルの重み計算方法を説明する図
【図７】同じくベクトルインデックス（演算順序）の例を示す図
【図８】同じく階層データの例を示す図
【図９】同じくテンプレート前処理の手順を示す流れ図
【図１０】同じくベクトルの重み計算の手順を示す流れ図
【図１１】同じくマスクパターンの作成手順を示す流れ図
【図１２】同じくマッチング処理全体の処理手順を示す流れ図
【図１３】同じく階層サーチの処理手順を示す流れ図
【図１４】マスクパターンのフィッティング手順を示す流れ図
【図１５】同じく回転・スケール変動照合処理の手順を示す流れ図
【図１６】同じく照合演算処理の手順を示す流れ図
【符号の説明】
【０１０６】
２…電子部品
７…画像メモリ
９…演算部
１０…テンプレートデータ格納メモリ
１２…画像処理装置
１３…マシン制御装置
【図１】
2008293073.tif 000005
【図２】
2008293073.tif 000006
【図３】
2008293073.tif 000007
【図４】
2008293073.tif 000008
【図６】
2008293073.tif 000009
【図７】
2008293073.tif 000010
【図８】
2008293073.tif 000011
【図９】
2008293073.tif 000012
【図１０】
2008293073.tif 000013
【図１１】
2008293073.tif 000014
【図１２】
2008293073.tif 000015
【図１３】
2008293073.tif 000016
【図１４】
2008293073.tif 000017
【図１５】
2008293073.tif 000018
【図１６】
2008293073.tif 000019
【図５】
2008293073.tif 000020