(57)【要約】【課題】適応型テンプレート分解による高速テンプレートマッチング法が提供される。【解決手段】前記テンプレート分解技法はテンプレートを多数の水平および／または垂直細分割に細分割し、前記細分割について一次元特徴づけが決定される。前記テンプレート分解は、対応するユーザインタフェースの支援のもと、汎用精密マシンビジョン検査システムの学習モード操作の間に適合させることができる。一つ以上のテンプレート分解設定に対するマッチング結果は、ユーザによりまたは自動分解設定評価ルーチンによって評価でき、速度とマッチング位置精度間に所望のトレードオフを提供する設定が決定される。自動測定物検査命令は、前記検査システムのランモード操作の間に最適の速度対精度のトレードオフを繰り返して提供する設定を実行することができる。【選択図】図２
2007026446.tif 000002
【特許請求の範囲】
【請求項１】
画像においてマッチング測定物形体を探索するのに使用可能であるテンプレートを定義するために、制御システム部およびユーザインタフェースを含む精密マシンビジョン検査システムを操作する方法であって、
前記方法には、
マッチさせるテンプレート形体を含むテンプレートをセットアップし、
前記定義されたテンプレートにおいて実行される、定義されたテンプレート分解設定を決定し、
前記定義されたテンプレート分解設定に対応するデータを含む前記定義されたテンプレートを保存する
工程が含まれ、
テンプレート分解設定が複数の細分割を含む
ことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、
前記定義されたテンプレート分解設定に対応する前記データが、
ａ）前記定義されたテンプレート分解設定に対応する前記複数の細分割のレイアウトを定義するデータ、および
ｂ）前記定義されたテンプレート分解設定に対応する前記複数の細分割の一次元特徴づけを含むデータ  、
のうちの少なくとも１つを備える
ことを特徴とする方法。
【請求項３】
請求項１に記載の方法において、
前記定義されたテンプレート分解設定の決定には、
前記テンプレートを少なくとも１つのそれぞれのテンプレート分解設定に分解し、
少なくとも１つのそれぞれのテンプレート分解設定についてそれぞれのマッチング操作を実施して、少なくとも１つのそれぞれのマッチング結果を決定し、
少なくとも１つのそれぞれのマッチング結果を評価して、容認できるマッチング結果を決定し、
容認できるマッチング結果に対応するそれぞれのテンプレート分解設定を、前記定義されたテンプレート分解設定として決定する
工程が含まれる
ことを特徴とする方法。
【請求項４】
請求項３に記載の方法において
それぞれのマッチング結果の評価には、ユーザによるそれぞれのマッチング結果の評価および自動分解設定評価ルーチンによるそれぞれのマッチング結果の評価、のうちの少なくとも１つが含まれる
ことを特徴とする方法。
【請求項５】
請求項３に記載の方法において、
テンプレート分解設定が、
水平方向に沿い、各々が水平寸法を有する第１数ｎ１個の細分割と、
垂直方向に沿い、各々が垂直寸法を有する第２数ｎ２個の細分割と
を備え、
ｎ１とｎ２の少なくとも１つは少なくとも２であり、
それぞれのテンプレート分解設定についてそれぞれのマッチング操作を実施する工程には、
前記水平方向に沿ったそれぞれの細分割の各々に対し、それぞれの一次元水平特徴づけを決定して、ｎ１個の一次元水平特徴づけを提供し、
前記垂直方向に沿ったそれぞれの細分割の各々に対し、それぞれの一次元垂直特徴づけを決定して、ｎ２個の一次元垂直特徴づけを提供し、
少なくとも１つのそれぞれの水平擬似画像を決定し、
少なくとも１つのそれぞれの垂直擬似画像を決定し、
各それぞれの一次元水平特徴づけを、対応するそれぞれの水平擬似画像と相関させて、ｎ１個の相関サブマップを提供し、
各それぞれの一次元垂直特徴づけを、対応するそれぞれの垂直擬似画像と相関させて、ｎ２個の相関サブマップを提供し、
３つの相関サブマップは前記ｎ１個の相関サブマップの少なくとも１つと前記ｎ２個の相関サブマップの少なくとも１つを含み、前記少なくとも３つの相関サブマップの組み合わせに基づいて完全な相関マップを決定し、
前記完全な相関マップを解析して、それぞれのマッチング結果を決定する
工程が含まれる
ことを特徴とする方法。
【請求項６】
請求項５に記載の方法において、
ａ）前記ｎ１個の細分割の各々が同じ水平寸法を有し、前記少なくとも１つのそれぞれの水平擬似画像が単一の水平擬似画像からなり、前記単一の水平擬似画像が各それぞれの一次元水平特徴づけと相関されている、
ｂ）前記ｎ２個の細分割の各々が同じ垂直寸法を有し、前記少なくとも１つのそれぞれの垂直擬似画像が単一の垂直擬似画像からなり、前記単一の垂直擬似画像が各それぞれの一次元垂直特徴づけと相関されている、
ことのうち少なくとも１つをさらに含む
ことを特徴とする方法。
【請求項７】
請求項６に記載の方法において、
前記ｎ１個の細分割が、前記水平方向に沿ってオーバーラップする少なくとも２つの細分割を備える
ことを特徴とする方法。
【請求項８】
請求項６に記載の方法において、
前記ｎ２個の細分割が、前記垂直方向にオーバーラップする少なくとも２つの細分割を備える
ことを特徴とする方法。
【請求項９】
請求項５に記載の方法において、
前記精密マシンビジョン検査システムの学習モードの間に実施され、前記定義されたテンプレートがその後前記精密マシンビジョン検査システムのランモードの間に実行される方法であって、
前記定義されたテンプレートが前記それぞれの一次元水平特徴づけと前記それぞれの一次元垂直特徴づけを備え、
ランモードの間に前記定義されたテンプレートを実行する工程には、
ランモードの間に取得した測定物画像に基づいて少なくとも１つのそれぞれの一次元水平特徴づけを決定するのに使用される操作に対応する態様で決定される水平擬似画像を決定し、
ランモードの間に取得した測定物画像に基づいて少なくとも１つのそれぞれの垂直擬似画像を決定し、前記少なくとも１つの垂直擬似画像は、少なくとも１つのそれぞれの一次元垂直特徴づけを決定するのに使用される操作に対応する態様で決定され、
各それぞれの一次元水平特徴づけを対応するそれぞれの水平擬似画像と相関させて、ｎ１の相関サブマップを提供し、
各それぞれの一次元垂直特徴づけを対応するそれぞれの垂直擬似画像と相関させて、ｎ２の相関サブマップを提供し、
３つの相関サブマップは前記ｎ１の相関サブマップの少なくとも１つと前記ｎ２の相関サブマップの少なくとも１つを含み、前記少なくとも３つの相関サブマップを組み合わせることに基づき、完全な相関マップを決定し、
前記完全な相関マップを解析して、ランモードの間にそれぞれのマッチング結果を決定する
工程が含まれる
ことを特徴とする方法。
【請求項１０】
請求項３に記載の方法において、
前記テンプレートを少なくとも１つのそれぞれのテンプレート分解設定に分解する工程には、
前記テンプレートを少なくとも１つのそれぞれのテンプレート分解設定に分解するユーザによる操作、および
前記テンプレートを少なくとも１つのそれぞれのテンプレート分解設定に分解するテンプレート定義ツールによる操作、
のうちの少なくとも１つが含まれる
ことを特徴とする方法。
【請求項１１】
請求項１０に記載の方法において、
前記テンプレート定義ツールが行なう操作には、
前記テンプレートを、水平方向に沿い、各々が水平寸法を有する第１数ｎ１個の細分割に分解し、
前記テンプレートを、垂直方向に沿い、各々が垂直寸法を有する第２数ｎ２個の細分割に分解する
操作が含まれ、
ｎ１とｎ２の少なくとも１つは少なくとも２であり、
前記細分割が、
（ｉ）前記水平および垂直方向の寸法の各々は、最大限でも画素の所定の最大数である画素数を含む基準、
（ｉｉ）前記水平および垂直方向の寸法の各々は、少なくとも４画素および最大限でも３０画素を含む基準、
（ｉｉｉ）前記水平および垂直方向の寸法は、テンプレート上で実施される空間周波数解析に基づいて決定される基準、
（ｉｖ）前記水平および垂直方向に沿った細分割の数は、容認できるテンプレートマッチング位置精度を提供することに基づいて決定される基準、
（ｖ）前記水平および垂直方向に沿った細分割の数は、細分割の数が増えると、テンプレートマッチング位置精度における逓減改善の解析に基づいて決定される基準、
（ｖｉ）前記水平および垂直方向に沿った細分割の数は、完全な２Ｄテンプレートマッチングに対する目標スピードアップに基づいて決定される基準、
のうち少なくとも１つを満たすことにより決定される
ことを特徴とする方法。
【請求項１２】
請求項１に記載の方法において、
前記テンプレート形体をオーバーレイするテンプレート分解設定を表示するためにユーザインタフェースを操作することをさらに含む
ことを特徴とする方法。
【請求項１３】
請求項１２に記載の方法において、
前記テンプレート形体をオーバーレイする前記テンプレート分解設定を調整するために前記ユーザインタフェースを操作することをさらに含む
ことを特徴とする方法。
【請求項１４】
請求項１２に記載の方法において、
ａ）前記テンプレート形体をオーバーレイする前記テンプレート分解設定をテストし、
ｂ）前記テストで得られたマッチング結果を表示し、
ｃ）前記テストで得られた前記マッチング結果が容認できるマッチング結果かどうか評価し、
ｄ）前記テストで得られた前記マッチング結果が容認できる場合、前記テンプレート形体をオーバーレイする前記テンプレート分解設定マッチングを前記定義されたテンプレート分解設定として使用する
工程をさらに含む
ことを特徴とする方法。
【請求項１５】
請求項１４に記載の方法において、
前記テストで得られた前記マッチング結果が容認できない場合、
以前にテストしたテンプレート分解設定に対して細分割の数を増したテンプレート分解設定を決定し、
細分割の数を増した前記テンプレート分解設定をテストして、対応するマッチング結果を決定し、
前記対応するマッチング結果が容認できるマッチング結果であるかどうか評価する、
および前記対応するマッチング結果が容認できる場合、
細分割の数を増した前記テンプレート分解設定を前記定義されたテンプレート分解設定として使用する、
工程を、容認できるマッチング結果が決定されるまで繰り返すことをさらに含む
ことを特徴とする方法。
【請求項１６】
請求項１に記載の方法において、
前記精密マシンビジョン検査システムの学習モードの間に実施される方法であって、
前記定義されたテンプレートがその後前記精密マシンビジョン検査システムのランモードの間に実行される
ことを特徴とする方法。
【請求項１７】
測定物を検査するための精密マシンビジョン検査システムにおいて、マッチング測定物の形体を同定するのに使用される好ましいテンプレートを定義する方法であって、
テンプレートはｎ１個の水平細分割とｎ２個の垂直細分割を備え、ｎ１とｎ２は１対の変数で、ｎ１とｎ２の各々は任意の正の整数であってよく、ｎ１とｎ２の任意の対についてｎ１とｎ２の少なくとも１つは少なくとも２で、
（ａ）前記テンプレートをｎ１個の水平細分割において水平にフィルタリングして、ｎ１個の水平１Ｄ特徴づけをそれぞれ生み出し、
（ｂ）前記テンプレートをｎ２個の垂直細分割において垂直にフィルタリングして、ｎ２個の垂直１Ｄ特徴づけをそれぞれ生み出し、
（ｃ）前記ｎ１個の水平１Ｄ特徴づけの各々を対応する水平に処理された画像と相関させて、ｎ１個の水平相関サブマップを生み出し、
（ｄ）前記ｎ２個の垂直１Ｄ特徴づけの各々を対応する垂直に処理された画像と相関させて、ｎ２個の垂直相関サブマップを生み出し、
（ｅ）ｎ１個の水平相関サブマップとｎ２個の垂直サブマップを組み合わせて、完全な相関マップを得て、
（ｆ）ステップ（ｅ）で取得した前記完全な相関マップに基づいて決定された結果を評価して、前記ｎ１個の水平細分割とｎ２個の垂直細分割が好ましい結果を提供するかどうか決定する、
工程が含まれる
ことを特徴とする方法。
【請求項１８】
請求項１７に記載の方法において、
ステップ（ｆ）において、前記ｎ１個の水平細分割とｎ２個の垂直細分割が好ましい結果を提供しないことが示される場合、ｎ１とｎ２の少なくとも１つを増加し、ステップ（ａ）ないし（ｆ）を繰り返す工程をさらに含む
ことを特徴とする方法。
【請求項１９】
請求項１７に記載の方法において、
前記完全な相関マップに基づいて決定された前記結果はテンプレートマッチング結果を含み、
容認できるテンプレートマッチング結果を生成するｎ１個の水平細分割とｎ２個の垂直細分割の１つ以上の容認できるセットを同定するために、ｎ１とｎ２の異なるそれぞれのセットに対してステップ（ａ）ないし（ｆ）が実施され、
ステップ（ｆ）は、ｎ１＋ｎ２は容認できるセットの中で最小である前記容認できるセットの１つを、前記好ましいテンプレートを定義するのに使用するｎ１の水平細分割とｎ２の垂直細分割のセットとして同定する
工程を備える
ことを特徴とする方法。
【請求項２０】
請求項１７に記載の方法において、
前記完全な相関マップに基づいて決定された前記結果はテンプレートマッチング結果を含み、
前記テンプレートマッチング結果を決定する工程には、
前記完全な相関マップを閾値化し、
連結構成要素解析を実施して、適格画素の局所セットを同定し、
前記適格画素の同定された局所セットの各々を標識し、
それぞれのセットに含まれる前記適格画素の相関値に基づいて適格画素の標識された各局所セットそれぞれに強度値の属性を付け、
前記強度値に基づき、標識された局所セットの１つ以上をテンプレートマッチング位置に対応するものとして選択する
工程が含まれる
ことを特徴とする方法。
【請求項２１】
請求項１７に記載の方法において、
（ｇ）前記ｎ１の水平相関サブマップおよびｎ２の垂直相関サブマップのうちで、１つ以上で、全数より少ないサブマップを選択的に組み合わせて、１つ以上の組み合わせサブマップを生み出し、
（ｈ）ステップ（ｅ）で得られた前記完全な相関マップと比較して、１つ以上の組み合わせサブマップを解析して、前記完全な相関マップによって提供された前記結果に密接に対応するマッチング結果を提供するであろう好ましい組み合わせサブマップを決定し、
（ｉ）前記好ましいテンプレートを定義するときに前記完全な相関マップに代えて前記好ましい組み合わせサブマップを実行する
工程がさらに含まれる
ことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、載荷台上の測定物の選択された形体もしくはパターンをスキャンおよび検査するために、互いに複数の方向に可動なカメラと載荷台を具備したマシンビジョン検査システムの操作方法に関し、さらに詳しくは２Ｄテンプレート（パターン）を複数の細分割に適応的に分解して、それらを測定物の画像と相関させて高速テンプレートマッチングならびに位置測定（パターン探索）を行なうシステムと方法に関する。
【背景技術】
【０００２】
精密マシンビジョン検査システム（または単に“ビジョンシステム”）は、検査対象物の正確な寸法測定を行いかつ種々のそのほかの対象物の特性を検査するのに利用できる。かかるシステムはコンピュータ、カメラおよび光学系、ならびに検査する測定物の形体をカメラがスキャンできるように複数の方向に可動な精密載荷台を備え得る。市販の一つの例示的先行技術システムは、イリノイ州オーロラにあるミツトヨアメリカコーポレーション（ＭＡＣ）から購入できる、パソコンベースのビジョンシステムＱＵＩＣＫ  ＶＩＳＩＯＮ（登録商標）シリーズとＱＶＰＡＫ（登録商標）ソフトウエアである。ビジョンシステムのＱＵＩＣＫ  ＶＩＳＩＯＮ（登録商標）シリーズとＱＶＰＡＫ（登録商標）ソフトウエアの機能と操作は、たとえば２００３年１月刊行のＱＶＰＡＫ  ３Ｄ  ＣＮＣ画像測定機ユーザーズガイドと１９９６年９月刊行のＱＶＰＡＫ  ３Ｄ  ＣＮＣ画像測定機操作ガイドに一般的な説明があり、いずれもその全体を参照することによりここに引用したものとする。この製品は、たとえばＱＶ−３０２ ＰＲＯモデルで例示されるように、顕微鏡型の光学系を使用して種々の倍率における測定物の画像を提供可能で、任意の単一ビデオ画像のリミットを越えて測定物の表面を横断するために載荷台を必要に応じて移動させることができる。単一のビデオ画像は典型的には、所望の倍率、測定分解能およびかかるシステムの物理的なサイズの制限が与えられておれば、観察または検査する測定物の一部分のみを包含する。
【０００３】
マシンビジョン検査システムは一般に自動化されたビデオ検査を利用する。例えば特許文献１に記載のものはかかる自動化ビデオ検査の種々な局面を教示しており、そのすべての内容は参照により本願明細書に引用したものとする。前記特許文献１が教示するように、自動化ビデオ検査度量衡計器は一般にプログラミングの能力を有しており、これによりそれぞれの特定測定物の構成に対してユーザが定義する自動検査事象シーケンスが可能になる。これはたとえばテキストベースのプログラミングによって、またはユーザが行なう一連の検査操作に対応した一連の機械制御命令を保存することによって検査事象シーケンスを漸次“学習する”記録モードを通して、あるいは両者の組み合わせを通して実行が可能となる。かかる記録モードはしばしば“学習モード”または“トレーニングモード”と呼称されることが多い。“学習モード”において検査事象シーケンスが定義されてしまえば、かかるシーケンスを使用して、“ランモード”の間に測定物の画像を自動的に取得し（さらに解析または検査）することができる。
【０００４】
特定の検査事象シーケンス（すなわち、各画像をどのように取得するかおよび取得した各画像をどのように解析／検査するか）を含む機械制御命令は、一般に特定の測定物の構成に特異的な“パートプログラム”または“測定物プログラム”として保存される。たとえばパートプログラムは、測定物に対してカメラをどのように位置するか、どの照明レベルまたはどの倍率レベルを使用するか、などの各画像をいかに取得するかを定義する。さらにパートプログラムは、たとえばテンプレートマッチングビデオツールのようなビデオツールを一つ以上使用することによって、取得した画像をどのように解析／検査するかを定義する。
【０００５】
パートプログラムには、いくつかある操作の中で、測定物画像における事前定義テンプレート（パターン）を同定するためのテンプレートマッチング（パターン探索）の命令を含むことができる。操作には、同定された測定物パターンの位置を正確に決定することを含み得る。特許文献２はスパースサーチブロックと積分投影を使用した動作概算プロセスおよびシステムを開示しており、そのすべての内容は参照により本願明細書に引用したものとする。テンプレートマッチング操作における積分投影の使用は、完全２Ｄ相関タイプのテンプレートマッチングと比較して、速度が実質的に増大することが知られている。
【０００６】
【特許文献１】米国特許第６，５４２，１８０号
【特許文献２】米国特許第６，１２８，０４７号
【発明の開示】
【発明が解決しようとする課題】
【０００７】
現在では、テンプレートのマッチングは、完全２Ｄ相関タイプの方法に基づいて実施されている。一般に、テンプレートマッチングの完全２Ｄ相関タイプでは、Ｍ×Ｎ画素の画像においてＴ×Ｓ画素のテンプレートをマッチングさせる（または探索する）ために、マッチングの前に画像スケーリングまたはサブサンプリングを行なわないと仮定すれば、要求される画素ベースの操作の総数はＭ×Ｎ×Ｔ×Ｓである。したがって画像のサイズが６４０×４８０画素で、テンプレートのサイズが７０×７０画素に対して、１５億画素ベースもの操作が必要となり、最新のプロセッサーにとってもこれは重大なことである。これは、特に大型のテンプレートではマッチングプロセスの過度のスローダウンを起こし得て、カメラの分解能が向上するにつれてこの問題がよく起こるようになる。
【０００８】
一方で、特許文献２のように、積分投影を使用する公知のタイプのテンプレートマッチングは、あるタイプのパターンをマッチする場合ロバスト性に欠ける。中でも積分投影の形成に起因するパターン情報の欠如により、誤りのあるまたは精度が不十分なテンプレートマッチングを引き起こし得る。テンプレートマッチングのロバスト性の欠如と精度が不十分なテンプレートの位置測定は（すなわち、テンプレートにマッチする測定物の形体の正確な測定）、多種多様な測定物の形体の画素またはサブ画素分解能レベルで正確な測定を提供すると期待されている、汎用精密マシンビジョン検査システムに関する特定の問題である。
【０００９】
したがって、増大した速度の利点を提供しなおかつロバストなテンプレートマッチングと、多種多様な測定物の形体に対して高精度テンプレート位置結果を保証するテンプレートのマッチング手法の必要性が存在する。
【課題を解決するための手段】
【００１０】
本発明により、積分投影の技法を新規のテンプレート分解技法と組み合わせたテンプレートマッチングの方法が提供される。前記新規のテンプレート分解技法は、定義されたテンプレートを、ロバストなテンプレートマッチングと、多種多様な測定物の形体に対して高精度テンプレート位置結果を保証する多数のセグメントに細分割し、なおかつこれを短縮されたおよび／またはほぼ最適処理時間で行なうものである。
【００１１】
テンプレートの分解および／または前記方法で使用するあるタイプのフィルタリングを、所望であれば、特定の測定物の形体にマッチさせるそれらの能力に依存する態様で、汎用精密マシンビジョン検査システムの学習モード操作の間に適合させてよい。学習モード操作の間に一つ以上のテンプレートの分解設定に対するマッチング結果をユーザによりまたは自動分解設定評価ルーチンにより評価して、速度とマッチングロバスト性／マッチング位置精度間の所望のトレードオフを提供する分解設定を決めることができる。次に、所望のトレードオフを提供する分解設定を自動測定物検査命令に（すなわち、パートプログラム中に）組み入れて、精密マシンビジョン検査システムのランモード操作の間、最適速度 対 ロバスト性および／または精度のトレードオフを繰り返し提供することができる。
【００１２】
本発明の一態様によれば、テンプレートの分解設定または生成すべき水平方向および垂直方向のテンプレート細分割（subdivisions）は、次のいずれかの一つに基づいて決定することができる。すなわちａ）ユーザ入力に基づく細分割における所望の最大画素数、ｂ）ユーザ入力に基づく所望の細分割数、ｃ）テンプレート上で実施する空間周波数解析、またはｄ）細分割数が増した場合のテンプレートマッチング位置ロバスト性および／または精度における逓減改善の解析のいずれかにより決定することができる。
【００１３】
さらに本発明の態様によれば、水平方向テンプレートの各細分割の水平方向投影が、測定物の対応する水平方向に処理した画像（“水平擬似画像”）に相関されて、水平方向の相関サブマップを提供する。同様に、垂直方向テンプレートの各細分割の垂直方向投影が、対応する垂直方向に処理した画像（“垂直擬似画像”）に相関されて、垂直方向の相関サブマップを提供する。
【００１４】
さらに本発明の態様によれば、それぞれの水平および垂直相関サブマップのすべてを組み合わせて（たとえば合計する）、完全な相関マップを提供し、この完全な相関マップを解析してテンプレートマッチング測定物の形体および／または位置を決定する。
【００１５】
さらに本発明の態様によれば、例示的実施形態において、スムージング操作または他の前処理により、その結果生じる相関マップを閾値化し、相関マップの閾値を超える画素に連結構成要素解析を行って適格画素の局所セットまたはブロブを同定し（たとえば、望まない弱相関例を拒否する）、同定した連結ブロブのそれぞれを標識し、それぞれの組み込み相関値に基づいてそれぞれのブロブに強度値を指定し、そして最強または十分に強力なブロブ（複数）をテンプレートマッチング測定物の形体を示すものとして選択することによって、完全な相関マップを解析することができる。
【００１６】
本発明の他の態様によれば、学習モード操作の間に、それぞれの水平および垂直相関サブマップを組み合わせて、テンプレートマッチング測定物の形体を同定するのに使用可能な完全相関マップを形成した後で、一つ以上の相関サブマップを選択的に組み合わせて、より少ない数のサブマップを組み合わせて完全なマップに十分に密接に対応する相関マップを提供できるかどうかを決定する。相関サブマップのすべてより少ない組み合わせが完全なマップに十分に密接に対応することがわかれば、サブマップのこのような組み合わせを完全相関マップに代えてさらなる解析に使用でき、その後のテンプレートマッチング操作で未使用のサブマップに対応する水平または垂直テンプレート投影の処理を捨てて、この方法の速度の利点を高めることができる。
【００１７】
本発明のさらに他の態様によれば、学習モード操作の間に、決定済みのテンプレートマッチング位置を使用して、対応位置にある測定物の形体のリアルタイム表示の上にオーバーレイされたテンプレートパターンを表示でき、そしてユーザはこの決定済みテンプレートマッチング位置が容認できるかどうか決定する。テンプレートマッチング位置はさらに、または別法として、数値座標結果として表示できる。もしユーザが、決定済みのテンプレートマッチング位置が容認できないと判断すると、水平および垂直テンプレートの細分割の数の少なくとも一つを増やして、テンプレートの細分割の増大数に基づいて、テンプレートマッチング操作を繰り返すことができる。もしユーザが、決定済みのテンプレートマッチング位置が容認できると判断すると、対応する数の水平および垂直テンプレート細分割、並びにテンプレートマッチング位置を決定するのに使用した任意のほかの対応するテンプレートマッチングパラメータをパートプログラムに組み入れて、ランモード操作の間対応する測定物の検査に使用できる。
【００１８】
発明のさらに他の態様によれば、学習モード操作の間、ユーザはそれぞれの数のテンプレート分解細分割に対応する決定済みテンプレートマッチング位置結果の複数のそれぞれの表示を“ステップスルー”し、測定物の形体のリアルタイム表示上にオーバーレイされた対応するそれぞれのテンプレートマッチング位置（複数）（および／または対応する数値座標結果）を観察し、それぞれの結果を容認するかまたは拒否することができる。さらに本発明の態様によれば、一つ以上の容認した結果に対応する細分割の最小数は、自動的に同定されかつパートプログラム中に組み入られて、ランモード操作の間対応する測定物の検査に使用できる。
【００１９】
本発明のさらに他の態様によれば、現在定義されているテンプレートの分解細分割が、学習モード操作の間表示されるテンプレート定義ツールと関連して表示される。さらに本発明の態様によれば、テンプレート定義ツールにはユーザがテンプレートの分解細分割を調整するための手段が含まれ、調整されたテンプレートの分解細分割が表示される。
【発明を実施するための最良の形態】
【００２０】
図1は、本発明による一つの例示的なマシンビジョン検査システム１０のブロック図である。マシンビジョン検査システム１０は、制御システム部として機能する制御コンピュータシステム１４とデータと制御信号を交換するように動作可能に連結された画像測定機１２を含む。制御コンピュータシステム１４は、データと制御信号をモニタ１６、プリンタ１８、ジョイスティック２２、キーボード２４およびマウス２６と交換するようにさらに動作可能に連結されている。モニタすなわちディスプレイ１６は、マシンビジョン検査システム１０の操作を制御および／またはプログラミングするのに適切なユーザインタフェースを表示できる。
【００２１】
画像測定機１２は可動測定物載荷台３２と、ズームレンズまたは交換レンズを含むことのできる光学画像システム３４を含む。ズームレンズまたは交換レンズは一般に、光学画像システム３４によって提供される画像に対して種々の倍率を提供する。マシンビジョン検査システム１０は、一般に上述したビジョンシステムのＱＵＩＣＫ  ＶＩＳＩＯＮ（登録商標）シリーズとＱＶＰＡＫ（登録商標）ソフトウエア、および市販されている類似の最新技術の精密マシンビジョン検査システムに匹敵する。マシンビジョン検査システム１０は、米国特許出願第１０／９７８，２２７号にも記述されており、そのすべての内容は参照により本願明細書に引用したものとする。
【００２２】
図２は、本発明によるマシンビジョン検査システム１００の制御システム部１２０とビジョン構成要素部分２００の略図である。以下にさらに詳細に説明するように、制御システム部１２０はビジョン構成要素部分２００を制御するのに利用される。ビジョン構成要素部分２００は光学アセンブリ部２０５、光源２２０、２３０および２４０、ならびに透過照明部２１２を有する測定物載荷台２１０を含む。測定物載荷台２１０は、測定物２０を配置可能な載荷台の表面に略平行な面にあるＸおよびＹ軸周りに制御可能に可動である。光学アセンブリ部２０５はカメラシステム２６０、交換対物レンズ２５０を含み、ターレットレンズアセンブリ２８０および同軸光源２３０を含んでよい。ターレットレンズアセンブリの代わりに、固定または手動交換倍率変更レンズまたはズームレンズ構成などを含めることができる。光学アセンブリ部２０５は、以下に詳細を説明するように、制御可能なモータ２９４を使用することによって、Ｘ軸およびＹ軸に略直交するＺ軸周りに制御可能に可動である。
【００２３】
マシンビジョン検査システム１００を使用して画像化される測定物２０は測定物載荷台２１０上に配置される。一つ以上の光源２２０，２３０および２４０はそれぞれ、測定物２０を照明するのに使用できる光源光２２２，２３２，または２４２を放つ。光源２２０，２３０および／または２４０が放った光は、測定物２０を照明し測定物光２５５として反射または伝達され、この光は交換対物レンズ２５０とターレットレンズアセンブリ２８０を通過してカメラシステム２６０に集光される。カメラシステム２６０によって捕捉された測定物２０の画像は、信号ライン２６２に載せて制御システム部１２０に出力される。
【００２４】
測定物２０を照明するのに使用される光源２２０，２３０および２４０は、リングライトまたはプログラム可能なリングライトのような載荷台光２２０、同軸光２３０および面光２４０を含むことが可能で、これらはいずれも信号ラインまたはバス２２１，２３１および２４１を通して制御システム部１２０に接続される。マシンビジョン検査システム１００の一次光学アセンブリとして、光学アセンブリ部２０５は、上述した構成要素に加えて、そのほかのレンズおよび開口のようなそのほかの光学素子、同軸照明を行なうのに必要となるビームスプリッタなど、またはそのほかの好ましいマシンビジョン検査システム機能を含むことができる。マシンビジョン検査システム１００の二次光学アセンブリとして含まれた場合には、ターレットレンズアセンブリ２８０は少なくとも第１のターレットレンズ位置およびレンズ２８６および第２のターレットレンズ位置およびレンズ２８８を含む。制御システム部１２０は、少なくとも第１と第２のターレットレンズ位置間で、信号ラインまたはバス２８１を経由して、ターレットレンズアセンブリ２８０を軸２８４周りに回転させる。
【００２５】
測定物載荷台２１０と光学アセンブリ部２０５間の距離は、カメラシステム２６０で捕捉した測定物２０の画像の焦点を変更するのに調整可能である。中でも、種々な実施例において、光学アセンブリ部２０５は、アクチュエータ、接続ケーブルなどを駆動する制御可能なモータ２９４を使用して測定物載荷台２１０に対して垂直Ｚ軸方向に可動で、光学アセンブリ部２０５をＺ軸に沿って移動させる。本明細書で使用する用語Ｚ軸は、光学アセンブリ部２０５で取得した画像の合焦に使用することを意図した軸を指す。制御可能なモータ２９４は、使用される場合、信号ライン２９６を経由して入出力インタフェースに接続される。
【００２６】
図２に示すように、種々の例示的実施形態において、制御システム部１２０はコントローラ１２５、入出力インタフェース１３０、メモリ１４０、測定物プログラム発生器およびエクゼキュータ１７０、ＣＡＤファイル特徴抽出部１８０、および電源部１９０を含む。これらの構成要素並びに以下に記述する追加の構成要素は、一つ以上のデータ／制御バスおよび／またはアプリケーションプログラミングインタフェースによって相互接続できること、または種々の要素間で直接接続できることを理解されたい。
【００２７】
入出力インタフェース１３０は、画像制御インタフェース１３１、動き制御インタフェース１３２、照明制御インタフェース１３３およびレンズ制御インタフェース１３４を含む。動き制御インタフェース１３２は位置制御要素１３２ａと速度／加速制御要素１３２ｂを含む。しかし種々の例示的実施形態において、かかる要素は結合されおよび／または区別できないかもしれないことを理解されたい。照明制御インタフェース１３３は、光源２２０，２３０および２４０のようなマシンビジョン検査システム１００の種々な対応する光源のための、たとえば選択、電源、オン／オフスイッチおよびストローブパルスタイミング（前記当する場合）を制御する照明制御要素１３３ａ〜１３３ｎを含む。
【００２８】
メモリ１４０は、画像ファイルメモリ部１４１、一つ以上のパートプログラムを含むことのできる測定物プログラムメモリ部１４２など、およびビデオツール部１４３を含む。ビデオツール部１４３は、対応するツールのそれぞれに対してＧＵＩ、画像処理操作などを決定するツール部１４３ａ〜１４３ｍを含む。本発明の種々な例示的実施形態において、ビデオツール部１４３はＧＵＩ、画像処理操作などを決定する、適応型テンプレート分解技法にしたがってテンプレートを定義するための、そしてマシンビジョン検査システムの学習モード操作で使用される、テンプレート定義ツール１４８も含む。ビデオツール部１４３は、テンプレート定義ツール１４８で行なわれたテンプレート分解の結果（すなわちテンプレート定義ツール１４８で同定された水平および／または垂直テンプレート細分割）、並びにそのほかの任意のテンプレートマッチングパラメータを、ランモード操作の間に（および“テスト”ランにおける学習モード操作の間にも）対応する測定物の検査に使用するために保存するテンプレートマッチングツール１４５をさらに含み、これによって定義されたテンプレートが保存される。さらにビデオツール部１４３は、ビデオツール部１４３に含まれる種々のビデオツールで操作可能な種々な対象の領域を定義する、自動、半自動および／または手動操作をサポートする対象の領域生成装置１４３ｘを含む。一般にメモリ部１４０は、取得した測定物２０の画像が所望の特性を有するように、測定物２０の画像を捕捉または取得するためにビジョンシステム構成要素部分２００を操作するのに使用できるデータを保存している。メモリ部１４０はさらに、手動または自動のいずれかで、取得した画像上で種々の検査と測定操作を実施するためのマシンビジョン検査システム１００を操作し、結果を入出力インタフェース１３０経由で出力するのに使用できるデータも保存している。
【００２９】
載荷台光２２０、同軸光２３０および面光２４０のそれぞれの信号ラインまたはバス２２１、２３１および２４１は、すべて入出力インタフェース１３０に接続されている。カメラシステム２６０からの信号ライン２６２と制御可能なモータ２９４からの信号ライン２９６は、入出力インタフェース１３０に接続されている。画像データを搬送するのに加えて、信号ライン２６２は画像の取得を開始するコントローラ１２５からの信号を搬送することができる。
【００３０】
一つ以上の表示装置１３６と一つ以上の入力装置１３８も入出力インタフェース１３０に接続可能である。表示装置１３６と入力装置１３８はパートプログラムをビュー、作成および／または修正し、カメラシステム２６０で捕捉した画像をビューし、ビジョンシステム構成要素部分２００を直接制御可能である。事前定義パートプログラム（または測定物プログラム）を有する全自動化システムでは、表示装置１３６および／または入力装置１３８を省略できる。
【００３１】
ＣＡＤファイル特徴抽出部１８０に関し、測定物を表すＣＡＤファイルのような情報はマシンビジョン検査システムの産業への利用においてしばしば利用できる。ＣＡＤファイルにおけるエッジ、境界および／または測定物の形体パターンの場所は、手動で、半自動の態様でまたは全自動で決定でき、かかる情報は測定物のパートプログラミングまたは所望の測定物形体へナビゲートするのに有用なことがある。
【００３２】
種々な例示的実施形態において、測定物２０についてユーザが測定物画像取得プログラムを作成するのにマシンビジョン検査システム１００を利用する場合、ユーザは測定物プログラミング言語を使用して命令を自動で、半自動でまたは手動で明示的にコーディングすることによるかまたは測定物のプログラム命令がトレーニングシーケンスを捕捉するように、画像取得トレーニングシーケンスを経てマシンビジョン検査システム１００を移動させることにより、ユーザは測定物プログラム命令を生成する。この方法は、捕捉すべき１組の画像において複数の画像について繰り返される。これらの命令は実行されると、測定物２０の特定の部分がカメラシステム２６０の視野内にあり、取得すべき１組の画像のそれぞれについて所望の焦点状態になるように、マシンビジョン検査システムに対して測定物載荷台２１０および／またはカメラシステム２６０をある速度（複数）で操作させる。カメラと測定物の相対運動を制御するプログラム命令に加えて、測定物画像取得プログラムも、それぞれの画像取得の間に測定物２０の所望の照明を提供するために、一つ以上の光源２２０〜２４０をアクティブにするプログラム命令を含む必要がある。
【００３３】
１組の測定物画像取得命令が一度定義されると、本発明の種々の例示的実施形態において、制御システム１２０が命令を実行し、命令にしたがって測定物２０の一つ以上の画像を捕捉するようカメラシステム２６０に指示する。次いで制御システム１２０はコントローラ１２５の制御下で、入出力インタフェース１３０を経由して捕捉した画像（複数）を入力し、メモリ１４０に捕捉した画像（複数）を保存する。コントローラ１２５は捕捉した画像を表示装置１３６上に表示することもできる。
【００３４】
さらに、制御システム部１２０は、捕捉して保存した測定物の検査画像の呼び出し、かかる測定物検査画像中の測定物の形体の検査と解析、および検査結果の保存および／または出力にも使用できる。これらの方法は典型的には、テンプレートマッチングツール１４５、エッジ／境界検出ツール、寸法測定ツール、座標マッチングツールなどの、メモリ１４０のビデオツール部１４３に含まれている種々のビデオツールにおいて具体化される。これらのツールの一部は、ビジョンシステムのＱＵＩＣＫ  ＶＩＳＩＯＮ（登録商標）シリーズと関連のＱＶＰＡＫ（登録商標）ソフトウエアのような、多様な市販のマシンビジョン検査システムにおいてごく普通に使用されている。
【００３５】
これらのビデオツールの一つ以上を使用して画像検査／解析操作が完了すると、制御システム１２０は各解析／検査操作の結果を入出力インタフェースに出力して、ビデオディスプレイ、プリンタなどの種々の表示装置１３６に出力する。制御システム１２０は、各検査操作の結果をメモリ１４０に保存することもできる。
【００３６】
上記発明の背景の章で説明したように、公知の完全２Ｄ相関タイプのテンプレートマッチングは高精度テンプレートマッチング位置結果を提供できるが、これらは計算集約的であり、これがマシンビジョンシステムの検査能力を制限する要因の一つになっている。一方、積分投影の公知の方法を使用するテンプレートマッチング法は完全な２Ｄ相関よりも相対的に速いかもしれないが、往々にしてロバスト性に欠けおよび／または高精度テンプレートマッチング位置結果を提供できない。本発明の種々の例示的実施形態において、積分投影技法を新規の適応型テンプレート分解技法と組み合わせるテンプレートマッチングの方法が提供されている。この方法は、テンプレートを、速度（テンプレートマッチング実行時間）とテンプレートマッチングロバスト性および／または位置精度間の所望のトレードオフを提供するのに十分な多数のセグメントに適応的に細分割する。
【００３７】
図３は積分投影を使用したテンプレートマッチングの概念を図示したもので、図４は図３の方法を取り入れた、本発明の一態様による新規の適応型テンプレート分解法の概念を図示したものである。図３に示すように、テンプレート３００はサイズがＴ×Ｓ（たとえば５０×５５画素）の対象の領域（ＲＯＩ）サイズを備え、テンプレート形体３０１を備え得る。図３に示す例では、テンプレート３００は３つのテンプレート形体部分３０２、３０４および３０６から成り、これらは説明のために均一である画素強度としている。より一般的には、グレースケール（または色）強度はテンプレート全面にわたって変動することがある。テンプレート３００のＲＯＩの残りは、説明の都合上、形体なしとしており、ゼロの画素強度（実際の測定物画像ではまったく暗黒であろう）を有すると仮定している。テンプレート３００のＲＯＩ内の画素強度値は垂直に投影されて（すなわち、垂直のカラムに沿って画素値が加算される）垂直の投影Ｖ０を形成し、これは垂直投影ライン３０８上に表示され、テンプレート３００のＲＯＩ内の画素強度値は水平に投影され（すなわち、水平の列に沿って画素値が加算される）水平の投影Ｈ０を形成し、これは水平投影ライン３１０上に表示される。具体的には、この簡単な例では背景部分が画素強度に貢献しないと想定されるので、テンプレート形体部分３０２と３０４を含む列は共に水平に投影されて水平投影部分３１２を形成し、テンプレート形体部分３０６を含む列は水平に投影されてて水平投影部分３１４を形成し、投影部分３１２と３１４は共同で水平投影ライン３１０上に水平投影Ｈ０を形成する。同様に、テンプレート形体部分３０２、３０４および３０６を含むカラムは共に垂直に投影されて、垂直投影ライン３０８上で垂直投影部分３１６を備えた垂直投影Ｖ０を形成する。垂直投影部分３１６は、テンプレート形体部分３０２と３０４が隔置されており、減少したセクション３１８における垂直投影に貢献しないので、減少したセクション３１８を含む。
【００３８】
図示した例では投影Ｈ０とＶ０は平均されている。たとえば、水平投影Ｈ０については、各水平列における画素のすべてのグレースケール（または色）値が合計され（すなわち、対応する横方向のヒストグラムが創られる）、総計を水平方向の列の幅寸法３６０（または水平方向の列における画素数）で除す。同様に、垂直投影Ｖ０については、各垂直カラムにおける画素のすべてのグレースケール（または色）値が合計され（すなわち、対応する横方向のヒストグラムが創られる）、総計を垂直方向のカラムでの高さ寸法３６２（または垂直方向のカラムにおける画素数）で除す。別法として、横方向のヒストグラムそのものを、それらを幅／高さで除することなく、投影として使用してよい。平均投影を使用することと横方向のヒストグラムを使用することに定性的な差はなく、平均投影（または“積分投影”）は単に縮尺した横方向のヒストグラムで、グレースケール（またはカラースケール）範囲を超えることのない投影値となる。上記の単なる総和に基づいた方法以外の種々な方法を、２Ｄテンプレート３００の一次元（１Ｄ）特徴付けを生成するのに使用できることにさらに留意されたい。かかる方法は加重和、ガウスフィルタリング、非ガウス荷重による線形フィルタリング、中央値、最大値および最小値フィルタリングを含む非線形フィルタリングを含むが、これらに限定されない。かかる特徴付けは、本明細書で開示した種々の例示的方法における簡単な総和に基づいた１Ｄ投影に代えて使用できる。
【００３９】
テンプレート３００の水平投影Ｈ０と垂直投影Ｖ０（またはより広範囲には、任意の水平および垂直１Ｄテンプレート特徴付け）を入手した後で、任意の現在公知のまたは後日開発されるグレースケールまたはカラー相関手法を使用して、投影をサイズがＭ×Ｎ（図示せず）の入力画像（たとえば測定物画像）に基づいたデータで相関することが可能である。これによって、測定物画像を含む入力画像を、テンプレートを用いて探索することが可能である。同様に特徴付けられた入力画像に適用できるサンプル相関手法は、乗法相関、絶対差相関（ＡＤＣ）とも称する絶対差の和（ＳＡＤ）、平方差の和（ＳＳＤ）、ユークリッド距離（テンプレートを多次元ベクトルとして扱う）、ドット積を使用する余弦手法（テンプレートと画像サブ領域をベクトルとして扱う）、正規化グレースケール相関および形体に基づく方法（すなわちエッジ画素の数／位置を相関する）を含むが、これらに限定されない。カラー画像／テンプレートについては、１Ｄテンプレート表現を生み出す前に、標準手法を使用して画像／テンプレートのカラーチャネルを組み合わせて、グレースケール画像を形成すれば、上記に概要を述べた方法の一つを使用するテンプレートマッチングを実施可能である。代案として、上記に概要を述べた方法の一つを使用するテンプレートマッチングを、画像の各カラーチャネルにおいて別途実施可能で、各カラーチャネルはユニークなまたは二重テンプレートマッチを返すことができる。それぞれのカラーチャネルについて複製されたテンプレートマッチについて決定された位置値は、たとえば平均化または加重平均により（たとえば、それぞれの相関の強度にしたがって重みづけして）組み合わせることができる。別法として、画像および／またはテンプレートの各カラーチャネルについて、たとえば本適用例で開示された任意のグレースケールに基づく方法に同等な方法を使用して相関マップを別途決定可能で、その結果各カラーチャネルについて得た相関マップを組み合わせて（たとえば加算）、本適用例を通じて記述したほかの完全相関マップ（複数）に同様に使用される完全なカラー組み合わせ相関マップを提供可能である。
【００４０】
相関操作を行なう前に、テンプレートの投影（または１Ｄ特徴付け）を得るのに使用した方法とまったく同じまたは同等の方法で、入力画像に基づいたデータを処理しなければならないことに留意されたい。たとえば、図３を参照して概要を説明したようにして取得したテンプレートの投影に関し、たとえば各画像列における画素について、テンプレート幅寸法３６０に対応する多数の画素を有する平均化カーネルを使用して、入力画像を水平方向に沿ってフィルタできる。本質的には、テンプレートについて水平投影値を決定したのと同じ要領で、十分な数の（たとえば、幅寸法３６０に対応する数）水平近隣（neighbors）を持った入力画像の各画素について“水平投影値”が決定される。この方法は“水平投影擬似画像”を提供すると記述でき、より一般的には入力画像の“水平擬似画像”である。同様に、各画像カラムにある画素に対してたとえばテンプレート高さ寸法３６２を有する平均化カーネルを使用するなどして、入力画像を垂直方向に沿ってフィルタできる。本質的には、テンプレートに対して垂直投影値が決定されたのと同じ態様で、十分な数（たとえば高さ寸法３６２に対応する数）の垂直近隣を有する入力画像の各画素について“垂直投影値”が決定される。この方法は“垂直投影擬似画像”、より一般的には画像入力の“垂直擬似画像”、を提供すると記述できる。次いでテンプレート３００の水平投影Ｈ０および垂直投影Ｖ０を水平および垂直投影擬似画像にそれぞれ相関させて、以下のようにして水平および垂直相関サブマップを作成する。それぞれの投影擬似画像における各画素に対し、その画素位置に対応する相関操作に由来する相関値を、相関サブマップにおけるその画素位置（ｘ、ｙ）に指定する。最後に、水平および垂直相関サブマップを組み合わせて、一つ以上の十分なまたは最善の相関（たとえばテンプレートに“最も類似した”入力画像（複数）における領域（複数））を同定する完全な相関マップを生み出すことができる。完全な相関マップは、以下にさらに詳細を説明するように、連結構成要素解析などを使用して閾値化によってさらに解析できる。
【００４１】
相関サブマップに関して、水平相関サブマップにある一つ以上の相関値のピークは一般に垂直位置（複数）を指し、ここでは水平投影Ｈ０が水平投影擬似画像にマッチし、理想的には垂直方向すなわちｙ軸方向の座標位置を指し、ここではテンプレート３００が入力画像における形体にマッチする。垂直方向すなわちｙ軸方向の座標位置の精度は、水平相関サブマップから決められた水平方向すなわちｘ軸方向の座標位置より一般に良好であるが、これは１Ｄ水平テンプレート投影と水平投影擬似画像がいずれも水平にあいまいであるかまたはフィルタを通したことによるものである。同様に、垂直相関サブマップにおける一つ以上の相関値のピークは一般に水平位置(複数)を指し、ここでは垂直投影Ｖ０が垂直投影擬似画像を指し、理想的には水平方向すなわちｘ軸方向の座標位置を指し、ここではテンプレート３００が入力画像における形体にマッチする。水平方向すなわちｘ軸方向の座標位置の精度は、垂直相関サブマップから決められた垂直方向すなわちｙ軸方向の座標位置より一般に良好であるが、これは１Ｄ垂直テンプレート投影と水平投影擬似画像がいずれも垂直にあいまいであるかまたはフィルタを通したことによるものである。相関サブマップを組み合わせると（たとえば合同画像画素に対応する結果を、対応する画素位置に加えるかまたは重ねる）、完全相関サブマップにおける一つ以上の相関値のピークが一般に（ｘ、ｙ）位置（複数）を指し、ここではテンプレート３００が入力画像における形体にマッチする。
【００４２】
上記の背景のセクションにおいて、完全２Ｄ相関タイプのテンプレートマッチングは計算集約的で、Ｍ×Ｎ画素の画像においてＴ×Ｓ画素のテンプレートをマッチングさせる（または探索する）ために、一般に画素ベースの操作をＭ×Ｎ×Ｔ×Ｓ数要求する と議論された。積分投影を使用したテンプレートマッチングの方法では、上記のように計算はより少なく集約的になる。特には、サイズがＭ×Ｎ画素の画像とサイズがＴ×Ｓ画素のテンプレートに対し、最終（完全）相関マップを計算するのに必要な画素ベースの大体の操作数は、下記に基づいて計算可能である:
１．水平テンプレート投影Ｈ０を取得するためのＴ×Ｓ操作。
２．垂直テンプレート投影Ｖ０を取得するためのＴ×Ｓ操作。
３．入力画像を水平方向にフィルタにかけ（フィルタ幅Ｔ）、水平方向投影擬似画像を提供するためのＭ×Ｎ×Ｔ操作。
４．入力画像を垂直方向にフィルタにかけ（フィルタ高さＳ）、垂直方向投影擬似画像を提供するためのＭ×Ｎ×Ｓ操作。
５．水平投影擬似画像を水平テンプレート投影Ｈ０と相関させ、水平相関サブマップを生み出すためのＭ×Ｎ×Ｓ操作。
６．垂直投影擬似画像を垂直テンプレート投影Ｖ０と相関させ、垂直相関サブマップを生み出すためのＭ×Ｎ×Ｔ操作×。
７．水平および垂直相関サブマップを組み合わせるためのＭ×Ｎ操作（複数）。
したがって、完全相関マップを生み出すための操作の総数は、２ＴＳ＋２ＭＮ（Ｔ＋Ｓ＋１／２）である。完全２Ｄ相関計算と比較すると、必要な操作数の比率は［２ＴＳ＋２ＭＮ（Ｔ＋Ｓ＋１／２）］／（ＭＮＴＳ）である。合計の最初の項（２ＴＳ）／（ＭＮＴＳ）は ≫０であるので、無視できる。さらに、１／２＜＜（Ｔ＋Ｓ）から１／２も無視できる。よって最終の比率は約２（Ｔ＋Ｓ）／（ＴＳ）となる。換言すれば、積分投影を使用したテンプレートマッチング法は、完全２Ｄ相関タイプのテンプレートマッチング法と比較して約（ＴＳ）／［２（Ｔ＋Ｓ）］早く実施でき、これにより４×４画素より大きいテンプレートに対するテンプレートマッチングのスループットが実際に改善される。
【００４３】
しかし、積分投影を使用する方法によって取得した完全相関マップは、完全２Ｄ相関タイプの方法によって得た相関マップの単なる近似である。オリジナルの２Ｄテンプレートは、僅か２つの１Ｄ投影（または１Ｄ特徴付け）で表されている（または抽象されている）ので、マッチングに関する情報量は劇的に少なくなり、水平相関と垂直相関を組み合わせることによる結果は、真の２Ｄ相関を概略で近似できるに過ぎない。要するに、積分投影を使用した先行技術のテンプレートマッチングは速度の改善はできるが、あるタイプのテンプレート（パターン）をマッチングする場合にはロバスト性に欠け、誤りのあるマッチ（偽陽性または偽陰性）を生じるかまたは不十分に正確なテンプレートマッチング位置結果を生じることがある。かかる問題の一例は図３を参照して説明できる。テンプレートの形体部分３０２、３０４をそれぞれ図３において点線で輪郭を描いた位置３０２’、３０４’に再配置しても、テンプレートのパターンには有意な差があるが、水平投影Ｈ０と垂直投影Ｖ０は不変であると理解されたい。以下に説明する新規の適応型テンプレート分解技法は、かかる問題を効率的でかつユーザフレンドリーな態様で解決する。
【００４４】
図４は本発明の一局面による新規の適応型テンプレート分解技法の概念を説明したもので、この方法は積分投影に基づく方法の速度の利点と、十分に正確なテンプレートマッチング結果を出すのに必要なシステムのロバスト性のいずれをも提供する。テンプレート３００は図３に示したのと同じテンプレート形体３０１を含み、テンプレート形体部分３０２、３０４および３０６から成る。しかし図４において、テンプレート３００は２つの水平テンプレート細分割３２０と３２２に分割され、それぞれがテンプレート３００の垂直高さを通過して伸長し、細分割寸法３７０および３７２をそれぞれ有している。同様に、テンプレート３００は３つの垂直テンプレート細分割３２４、３２６および３２８に分割され、それぞれがテンプレート３００の水平幅を通過して伸長し、細分割寸法３７４、３７６および３７８をそれぞれ有している。
【００４５】
水平テンプレート細分割３２０と３２２は水平に投影され、それぞれ水平投影Ｈ１とＨ２を形成し、これらは水平投影ライン３２８と３３０上にそれぞれ表示される。水平投影Ｈ１は水平投影部分３３２と３３４から成り、これらはテンプレート形体部分３０４と水平テンプレート細分割３２０に含有されるテンプレート形体部分３０６のセグメントを含む。水平投影Ｈ２は水平投影部分３３６と３３８から成り、テンプレート形体部分３０２と水平テンプレート細分割３２２に含有されるテンプレート形体部分３０６のセグメントを含んでいる。垂直テンプレート細分割３２４、３２６および３２８は垂直に投影され、それぞれ垂直投影Ｖ１、Ｖ２およびＶ３を形成し、これらは垂直投影ライン３４０、３４２および３４４上にそれぞれ表示される。垂直投影Ｖ１は、垂直テンプレート細分割３２４に含有されるテンプレート形体部分３０６の投影を含む、垂直投影部分３４６から成る。垂直投影Ｖ２は、テンプレート形体部分３０４の投影および垂直テンプレート細分割３２６に含有されるテンプレート形体部分３０２のセグメントを含む、垂直投影部分３４８および３５０から成る。最後に、垂直投影Ｖ３は、垂直テンプレート細分割３２６に含有されるテンプレート形体部分３０２のセグメントの投影を含む垂直投影部分３５２から成る。
【００４６】
図３を参照して上記に説明したように、２Ｄテンプレート３００の１Ｄ特徴づけを生成するのに種々な方法が使用できる。同様に、任意の２Ｄテンプレート細分割の１Ｄ特徴づけを生成するのに種々の方法が使用でき、これには画像投影法（部分和、横方向のヒストグラム）、平均化投影法（垂直および水平方向への平均フィルタリング）、ガウスフィルタリング、非ガウス荷重による線形フィルタリングおよび、中央値、最大値および最小値フィルタリングを含む非線形フィルタリングを含むが、これらに限定されない。かかる特徴づけは、テンプレート細分割処理のために本明細書で開示された種々の例示的方法において、簡単な総和ベースの１Ｄ投影に代えて使用できる。
【００４７】
図３を参照する上記の説明と同様に、それぞれの相関についてそれぞれのテンプレート細分割投影（より一般的には、それらの１Ｄ特徴づけ）を使用して相関操作を実施する前に、それぞれのテンプレート投影（または１Ｄ特徴づけ）を取得するのに使用された方法とまったく同じかまたは同等な方法を使用して、入力画像に基づいたデータを処理すべきである。たとえば、それぞれのテンプレートの水平細分割投影Ｈ１が“平均化された”投影の場合、投影Ｈ１について相関操作を行なう前に、十分な数の水平近隣を有する各画素について、寸法３７０と同じ幅を有する平均化カーネルを使用して、入力画像を水平方向に沿ってフィルタして、投影Ｈ１への相関が適切な水平投影を生成できる。水平細分割タイプの投影Ｈ２に対応した寸法３７２が寸法３７０と同じであれば、同じ水平投影擬似画像は投影Ｈ２への相関が適切である。しかしもし寸法３７２が異なっておれば、寸法３７２と同じ幅を有する平均化カーネルを使用して、入力画像を水平方向に沿ってフィルタリングすることによって適切な擬似画像が提供されなければならない。このように、テンプレートマッチングのスループットを増大するには、ほかの考慮事項により容認されれば、単一の水平投影擬似画像はテンプレートの個々の水平細分割投影の少なくとも２つとの相関が適切であるように、少なくとも水平細分割が同じ寸法をもつのが好ましい。同様の考慮事項が、テンプレートの垂直細分割に関連した処理と寸法に適用される。このように、テンプレートマッチングのスループットを増大するには、ほかの考慮事項により容認されれば、たとえば単一の垂直投影擬似画像はテンプレートの個々の垂直細分割投影の少なくとも２つとの相関が適切であるように、高さ寸法３７６および３７８について図示したように、少なくとも２つの垂直細分割が同じ寸法を持つことも好ましい。もちろんほかの考慮事項により容認されれば、すべての水平細分割が同じ寸法を有しさらにすべての垂直細分割が同じ寸法を有するのが最も有利である。
【００４８】
それぞれの水平投影Ｈ１とＨ２は次いで対応する水平方向に処理された水平投影擬似画像と相関し得て、それぞれの水平相関サブマップを生成する。同様に、それぞれの垂直投影Ｖ１、Ｖ２およびＶ３は対応する垂直方向に処理された垂直擬似画像と相関し得て、それぞれの垂直相関サブマップを生成する。これまでのように、任意の現在公知のまたは後日開発される相関方法は使用でき、乗法相関、絶対差の和（ＳＡＤ）すなわち絶対差相関（ＡＤＣ）、平方差の和（ＳＳＤ）、ユークリッド距離（テンプレートを多次元ベクトルとして扱う）、ドット積を使用する余弦手法（テンプレートと画像サブ領域をベクトルとして扱う）、正規化グレースケール相関および形体に基づく方法（すなわちエッジ画素の数／位置を相関する）を含むが、これらに限定されない。水平相関サブマップ並びに垂直相関サブマップがそれぞれ水平投影と垂直投影Ｈ１，Ｈ２，Ｖ１，Ｖ２およびＶ３に基づいて生成されると、これらをすべて組み合わせて、後で記述するように、テンプレート３００とマッチする形体（複数）の位置を同定するのに使用される完全な相関マップを生み出し得る。
【００４９】
本発明の種々な例示的実施形態によれば、新規の適応テンプレート分解法は、２Ｄテンプレートの１Ｄ投影（または１Ｄ特徴づけ）の適応シリーズに積分投影法を使用する。ロバストなテンプレートマッチングおよび／または良好なテンプレートマッチング位置精度を提供するために、この方法は一つ以上のテンプレート細分割および対応する１Ｄ投影を、水平および／または垂直方向のそれぞれに採用可能である。適応細分割および対応する投影を使用して、オリジナルの２Ｄテンプレートの非常に重要な情報を保護し、こうしてテンプレートマッチングにおける精度を改善する。水平投影と垂直投影の数は等しくする必要はなく（図４の例では２つの水平投影と３つの垂直投影が作られている）、テンプレートの形状に基づいて水平投影と垂直投影の数を調整可能である（たとえば、長くて薄い垂直テンプレートは、水平方向よりも垂直方向においてより多くサンプリング可能である）。さらに、水平テンプレート細分割のいずれも互いにオーバーラップでき、垂直テンプレート細分割のいずれも互いにオーバーラップできる。適応型テンプレート分解技法の利点の一つは、良好なマッチング精度と速度の改善の両方を各アプリケーションにおいて達成するように、それを水平／垂直テンプレート細分割の数とサイズを調整するのに使用できることである。たとえば、図３を参照して上記に説明した問題に関し、テンプレートの形体部分３０２、３０４のそれぞれが、図４を参照して上記に説明したように、図３において点線で輪郭を描いた位置３０２’、３０４’にそれぞれ再配置されると、テンプレートのパターンの差が２つの対応する水平投影Ｈ１、Ｈ２に反映されることを理解されたい。したがって、テンプレートの異なる設定は適切に区別され、正しいマッチングができるが、時間のかかる完全２Ｄ相関技法は使用せずにすむ。
【００５０】
図７は、マシンビジョン検査システムの学習モードの間に実施されるルーチン７００の全体を示すフローチャートで、ここには本発明の一局面による適応型テンプレート分解法を使用してテンプレートを生み出すための操作が含まれる。ブロック７０５において、マシンビジョン検査システムは学習モードまたはトレーニングモードに入る。ブロック７１５において、ルーチンは第１の入力（測定物）画像を獲得する。ブロック７２０において、現在の画像の解析のためにテンプレートの創造が必要と決まれば、次のブロック７２５〜７４５による操作が実施される。特には、ブロック７２５において、マッチさせるテンプレート形体を含むテンプレートをセットアップし、２Ｄテンプレートを定義するのにテンプレート定義ツール（たとえば図２における１４８）がセットアップまたは調整される。テンプレート定義ツール１４８は、テンプレートの定義のために、後で説明する図８〜１０に示すように、種々の画像処理操作を行い、ＧＵＩを提供する。ブロック７３０において、テンプレートのトレードオフモードがアクティブであるかどうか決定される。一般に、テンプレート創造ビデオツール１４８は、トレードオフモードでもデフォルトモードでも作動する。トレードオフモードでは、前記ツールが２Ｄテンプレートを複数の水平および／または垂直テンプレート細分割に適応的に分解し、これが速度とマッチングのロバスト性と位置精度間の好ましいトレードオフを提供する。たとえば、デフォルトモードではツールが潜在的な速度の増大を犠牲にして、オリジナルの２Ｄテンプレートの使用のみで、完全な２Ｄ相関技法を使用して従来のテンプレートマッチング法を実施できる。テンプレートのトレードオフモードがアクティブでなければ、すなわちテンプレートの定義ツールがデフォルトモードであれば、ブロック７３５において、オリジナルの２Ｄテンプレートと任意の関連パラメータが保存される。一方、テンプレートのトレードオフモードがアクティブであれば、ブロック７４０において種々の実施形態において、テンプレート定義ツールおよび／またはテンプレートマッチングツール（図２の１４５）が、２Ｄテンプレートを速度と精度間の所望のトレードオフを達成する複数のテンプレート細分割に適応的に分解するように、セットアップまたは調整または設定される。
【００５１】
特には、ステップ７４５において、テンプレート定義ツールにおいて定義されたオリジナルテンプレートの分解設定、並びにテンプレートマッチング位置を決定するのに使用されるそのほかのパラメータまたはテンプレート定義ツール１４８および／またはテンプレートマッチングツール１４５の操作が、容認できるテンプレートマッチング結果が提供されるまで（また所望であれば、十分に高い速度のテンプレートマッチングも提供される）調整される。たとえば、一例示的実施形態において、テンプレート定義ツール１４８を使用してテンプレートの分解設定（たとえばテンプレート細分割および／またはそれぞれのテンプレート細分割投影またはほかの１Ｄ特徴づけを）を定義でき、またテンプレートマッチングツール１４５を使用して、一つ以上の分解設定またはテンプレート定義ツール１４８で定義されたテンプレート細分割のセットに対して実際のテンプレートマッチングを実施できる（たとえば、それぞれのテンプレート細分割投影またはほかの１Ｄ特徴づけに対応するそれぞれの水平および垂直擬似画像生成、対応するそれぞれの相関サブマップ生成および完全な相関マップの生成とテンプレートマッチング解析）。これでテンプレート分解設定のマッチング結果をユーザまたは自動分解設定評価ルーチンが評価して、速度と精度間の所望のトレードオフを提供する分解設定を決定できる。これについては後で図５を参照してさらに詳細に説明する。次いで決定されたテンプレート分解設定並びに所望のテンプレートマッチング操作の実施に使用されたパラメータが保存される。ブロック７５０において、検査すべき画像がさらにあるかかどうか決定される。検査する場合、ルーチン７５０はブロック７１５に戻り、新しい（次の）画像を処理する。検査する画像がそれ以上なければ、決定された所望のテンプレート設定を含め、ブロック７５５において操作のランモードの間テンプレートマッチングツール１４５によって使用されるテンプレートマッチングパラメータがパートプログラムに保存される。これでマシンビジョン検査システムは学習モードから出ることができる。種々の操作および／または保存されたパラメータまたはテンプレート定義ツールの結果、またはテンプレートマッチングツールの割り当ては、実施形態が異なれば異なることを理解されたい。かかる割り当ては任意であることができるプログラミングによるか、またはある利点またはあるアプリケーションで所望される機能によって支配される。したがって、本明細書においてそれらの記述は例示的にすぎず、制限するものではない。さらに種々な実施形態において、テンプレート定義ツールとテンプレートマッチングツールの操作は単一ツールに結合するおよび／または区別できないようにできる。
【００５２】
図５は、本発明による適応型テンプレート分解技法ルーチン５００の一実施形態を説明したフローチャートである。ルーチン５００は一般に図７のブロック７２５〜７４５と７５５に対応する。図５のブロック５０５において、マッチさせるテンプレート形体を含むテンプレートをセットアップし、テンプレート定義ツールがセットアップされる。特には、テンプレートの対象の領域（ＲＯＩ）と、テンプレート細分割における所望の画素最大数および／または生み出すテンプレート細分割の所望数のようなそのほかのテンプレートパラメータを、ユーザ入力および／または場合によってはデフォルト値に基づいて定義できる。ブロック５１０において、“ｎ”の最初の値または次の値に対してテンプレートＲＯＩは“ｎ”の小領域または細分割に分解される。本発明の種々な例示的実施形態によれば、定義されたテンプレートにおいて、実行されるべきテンプレートの分解設定または生成する水平および垂直細分割の数は以下のうちの一つに基づいて決定される。すなわち（ａ）ユーザ入力またはデフォルト値に基づいた細分割における画素の所望の最大数（たとえば水平または垂直方向のそれぞれにおける画素の所望数）、（ｂ）ユーザ入力またはデフォルト値に基づいた所望の細分割数、および（ｃ）テンプレート上で実施する空間周波数解析のいずれかに基づいて決定される。
【００５３】
ブロック５１５において、２Ｄテンプレートの１Ｄ特徴づけの生成と入力画像のフィルタリングのために実施するそれぞれの水平および垂直投影操作は、それぞれの水平および垂直テンプレート細分割に基づいて定義される。ブロック５２０において、入力画像のすべてまたは一部がそれぞれの水平および垂直投影操作に対応する態様でフィルタされ、それぞれの水平および垂直擬似画像が生み出される。上記に概要を説明したように、それぞれの水平および垂直擬似画像の必要数は水平および垂直細分割に使用する多くの異なる寸法に左右されることになる。ブロック５２５では、水平／垂直テンプレート細分割のそれぞれに対し、次のブロック５３０〜５４５が実施されるべきである。
【００５４】
特には、ブロック５３０において、現在のテンプレート細分割に対し、細分割の１Ｄ特徴づけ（たとえば１Ｄ投影）を生み出すために対応する水平または垂直投影操作が行われる。上記に概要を説明したように、１Ｄ水平特徴づけ、または１Ｄ垂直特徴づけのそれぞれを決める方法は、そのそれぞれの１Ｄ特徴づけに相関されるであろう、対応するそれぞれの擬似画像を決めるのに使用する方法に通常は対応しなければならない。ブロック５３５において、現在のテンプレート細分割に対して対応する水平または垂直基準座標が決められる。
【００５５】
基準座標とも称される水平および垂直基準座標、（ｘ、ｙ）に関して、テンプレートマッチング操作の一つの目標は、入力画像における測定物の形体が完全なテンプレートと最善にマッチする単一場所を同定するのに、種々のテンプレート細分割がすべて貢献することを理解されたい。ある意味では、２Ｄ測定物の形体に帰する座標位置は任意であってよい。つまり測定物の形体（または測定物の形体に関して既知の位置）上にある定義された“基準”点が所望の座標系に関して定義されておれば、２Ｄ測定物の形体のそのほかの測定または寸法は基準点に関して決定でき、したがって所望の座標系に関して決定できる。テンプレートの細分割に対して、似たような種類の座標“ブックキーピング”を適用できることを理解されたい。つまり全体のテンプレートは、測定物の画像における対応する基準点にマップするまたは合致する定義された基準点を有することができ、この画像が“テンプレートマッチング座標”として報告される。同様に、テンプレートの細分割のそれぞれは、テンプレートの基準点に関して決められた細分割基準座標を有することができ、このようにして所望の座標系に関して決めることができる。細分割基準座標は全体のテンプレートに関して細分割の位置によって決まり、細分割に関連した種々なフィルタリングおよび／または相関操作、および／または相関サブマップ組み合わせ操作などが、幾何学的に適切かつ矛盾のない態様で実行および／または組み合わされるように、座標系を使用できることを理解されたい。このような適切な座標関係のブックキーピング、フィルタ操作結果の擬似画像の適当場所への保存などの必要性とそれを達成する態様は、本開示の利点を有する当業者によって理解されよう。
【００５６】
ブロック５４０において、対応するそれぞれの（ブロック５２０で生み出された）擬似画像と対応するそれぞれの水平または垂直１Ｄ投影または（ブロック５３０で創られた）１Ｄ特徴づけに相関させることで、現在のテンプレート細分割について相関サブマップが生み出される。それぞれの完全な相関サブマップ相互の、および／または全体のテンプレートに対する、および／または入力画像に対する関係またはアライメントは、上記に概要を説明したように細分割の基準座標に基づいて追跡できる。ブロック５４５において、相関サブマップが任意の正の整数であることができる“ｎ”個の細分割のすべてについて生み出されたかどうか決定される。生み出されていないと、ルーチンはブロック５２５に戻る。
【００５７】
すべての相関サブマップが生み出されると、ルーチンはブロック５５０に進み、ここでこれらの相関サブマップを完全な相関マップに組み合わせることができ、次いでこのマップを解析して現在のテンプレート分解設定に起因しかつ対応する（すなわち“ｎ”個の細分割に対応する）テンプレートマッチング結果、すなわちテンプレートマッチング位置（複数）を決定する。ブロック５５５において、前記当する場合、ブロック５５０で決められたテンプレートマッチング位置（複数）に基づいて、“高精度”テンプレートマッチング操作を実行できる。たとえば、ブロック５５０で決められたテンプレートマッチング位置は妥当な精度で既知であるから、完全な２Ｄテンプレート相関操作（たとえば既知の高精度タイプのテンプレート相関）を短時間で非常に小さい探索範囲で実施できる。たとえばブロック５５０で決められた位置の周りの各方向に数画素の範囲で、改善されたテンプレートマッチング位置精度が提供される。
【００５８】
決定ブロック５６０において、テンプレートマッチングの結果が容認できるかどうかが決められる。たとえば、（たとえば図１０を参照して概要を説明したような）ユーザによる視覚検証を含むマッチング結果の評価または自動分解設定評価ルーチンによって、適当数のマッチが同定されたかどうかおよび／または十分に正確なマッチング位置が同定されたかどうかが決定される。たとえば、自動分解設定評価ルーチンは、相関サブマップのそれぞれのばらつき（均一性）および／または結果としての完全な相関マップを解析して、サブマップおよび／または完全な相関マップが“十分に強力な”相関ピークを含有しているか、または逆にそれらが過度に均一であるかどうかを決めることができる。“十分に強力な”相関ピークがなければまたはマップ（複数）が過度に均一であれば、テンプレート探索におけるそれらの“解像度”は低く、ゆえに細分割の数を増大して、相関サブマップおよび／または完全な相関マップにおいて有意なピークをさらに生成すべきである。テンプレートマッチング結果が容認できない場合は、ルーチン５００はブロック５１０に戻り、テンプレートＲＯＩを異なる設定で再度分解する。例示的実施形態において、ブロック５１０に戻る場合に、たとえば水平または垂直方向の少なくとも１つに沿って少なくとも一つの追加の細分割のように、異なる設定がさらなる細分割を含んで、“ｎ” 個の値が大きくなることがある。上記操作は容認できる結果が提供されるまで、繰り返される。一方テンプレートマッチングの結果が容認できる場合は、ブロック５６５において、テンプレートパラメータおよび／または容認できるマッチング結果に対応する操作が、定義されたテンプレート分解設定として決定され、パートプログラムに保存され、マシンビジョン検査システムのランモードにおけるテンプレートマッチング操作に使用され、これでルーチンは終了する。
【００５９】
パートプログラムに保存されたテンプレートパラメータおよび／または操作は、容認できるテンプレートマッチングの結果に対応する複数の細分割のレイアウトを定義するデータおよび／または容認できるマッチングの結果を決めるのに使用されるそれぞれの１Ｄ特徴づけを含むデータ、ならびにランモードの間にそれぞれの１Ｄ特徴づけに相関されるであろう対応するそれぞれの擬似画像を決めるのに十分なデータを含むことができる。より一般的には、テンプレートのパラメータおよび／または操作の任意の組み合わせを含むデータを保存でき、これによりランモードの間に類似のテンプレート分解設定に対応して定義されたテンプレートを実行して、取得すべき類似のマッチング結果が得られる。
【００６０】
本発明の種々な例示的実施形態において、ブロック５６０において、決定されたテンプレートマッチング位置（複数）を使用して、対応する位置（複数）における測定物の形体のリアルタイム表示にオーバーレイしたテンプレートパターンが表示され、決定されたテンプレートマッチング位置（複数）が容認できるかどうかユーザが決定する。（後で説明する図１０を参照）。テンプレートマッチング位置は数値座標結果として表示することもできる。決定されたテンプレートマッチング位置が容認できないとユーザが決めた場合は、ブロック５１０に戻り、水平および垂直テンプレート細分割の数の少なくとも一つが増大され、増大された数のテンプレート細分割に基づいてテンプレートマッチング操作が繰り返される。
【００６１】
本発明の様々な他の例示的実施形態において、ユーザはそれぞれの数のテンプレート分解細分割に対応する決定されたテンプレートマッチング位置結果の複数のそれぞれの表示を“ステップスルー”し、測定物の形体のリアルタイム表示上にオーバーレイされた対応するそれぞれのテンプレートマッチング位置（および／または対応する数値座標結果）を観察し、各結果を容認または拒否できる。換言すれば図５のブロック５１０〜５６０は、ブロック５６０においてテンプレートマッチング結果が（たとえば、いくつかのデフォルト基準にしたがって）容認できるかどうかを毎回調べることとは無関係に、ある複数の回数繰り返される。本発明のさらに他の態様によれば、複数のそれぞれの結果がユーザによって容認されると、最少数の細分割（最大速度の利点となる）に対応する容認された結果が自動的に同定され、パートプログラムに組み込まれてランモードの間に対応する測定物の検査に使用される。細分割の数が増えると、この方法はテンプレートマッチング位置精度における逓減改善の解析に基づくことができる。
【００６２】
図６は相関マップ解析ルーチン６００の一例示的実施形態を説明するフローチャートで、本発明によるテンプレートマッチング位置（複数）の同定に使用される（図５のブロック５５０を参照）。ブロック６０５において、一つ以上の相関サブマップが全体のまたは完全な相関マップ（全体相関マップ）と組み合わされる。このサブマップは、公知のあいまい理論またはニューラルプログラミングトレーニング法を追加または使用するなどして、任意の適切な態様で組み合わせることができる。ブロック６１０において、全体相関マップが閾値化される。場合によっては、相関マップ上でスムージング操作（たとえば、平均、ガウスまたは中央値フィルタリング）を実施して、閾値化操作の前にスプリアスノイズを除去することができる。ブロック６１５において、閾値化された全体相関マップ上で形態学的クロージング操作（複数）（膨張処理に続き収縮処理を行う操作）が行なわれて、その中にあるすべての小さな穴を閉じる。ブロック６２０において、連結構成要素（領域）解析を行なって全体相関マップにおける適格画素の局部的セットを同定し、結果として生じた領域がテンプレートマッチング領域の候補として当該適格画素の同定された局所セットの各々によって標識される。ブロック６２５において、当該適格画素の同定された局所セットの各々によって標識されるテンプレートマッチング領域の各候補について、たとえば候補領域におけるすべての相関“画素値”を合計することにより、その“強度”が計算され、その強度値が候補領域の属性となる。候補領域の“強度”は、基礎をなす相関操作が良好なマッチに対応する高相関値を生じる場合、たとえば乗法相関操作が使用される場合、大きな和（大きなピーク）で示すことができることを理解されたい。逆に言えば候補領域の“強度”は、基礎をなす相関操作が良好なマッチに対応する小相関値を生じる場合、たとえば絶対差相関（ＡＤＣ）操作が使用される場合、小さな和（大きな谷）で示すことができる。ブロック６３０において、たとえば候補領域における相関値加重“画素位置”に基づいた領域セントロイド座標を決定することにより、各候補領域に対する代表的位置または場所が決められる。ブロック６３５において、当該候補領域の強度値に基づき、十分なまたは最大の“強度”を有する１以上の候補テンプレートマッチング領域が、見込みテンプレートマッチング領域（複数）として選択され同定される。前記該当する場合、見込みテンプレートマッチング領域（複数）はそのほかの基準、たとえば測定物上の期待されたまたは“デザイン通りの”形体場所と比較したそれらの場所、相互の場所関係、候補マッチング領域のサイズなどによって選別される。ブロック６４０において、それぞれの見込みテンプレートマッチング領域（複数）に対応する代表的な場所（複数）が同定され、テンプレートマッチング場所として出力される。
【００６３】
本発明の様々な例示的実施形態によれば、完全相関マップを形成するためにそれぞれの水平および垂直相関サブマップを組み合わせた後、一つ以上の相関サブマップを選択的に組み合わせて、サブマップのどの組み合わせが完全相関マップに十分に対応するかを決めることができる。すべての相関サブマップより少ない組み合わせが、完全相関マップに十分に密接に対応することがわかれば、サブマップのかかる組み合わせを完全な相関マップに代えてテンプレートマッチングに使用でき、テンプレートマッチング速度すなわちスループットが対応して増大する。また当該テンプレートを定義するときに、完全な相関マップに代えてサブマップのかかる組み合わせを実行してもよい。換言すれば、“すべてより少ない”相関サブマップの組み合わせに起因するテンプレートマッチング場所を評価することが可能で、テンプレートマッチング場所（複数）の精度の改善に有意に貢献しないサブマップを放棄することができる。もちろんサブマップを“放棄する”と、そのサブマップの作成に特有の操作のいずれも実行する必要はない。たとえばランタイムにおいて、そのサブマップに関連した細分割の１Ｄ特徴づけならびにそのサブマップに特有に関連したすべてのフィルタリングと相関操作は省略できる。上記に概要を説明したように、相関サブマップはそれらのばらつきまたは均一性の解析に基づき放棄できる（有意な相関ピークまたは谷がない場合、これらを放棄してよい）。これらは系統的なトライアルアンドエラー試験に基づいて放棄してもよい。いずれにせよ、テンプレートマッチング場所の結果を決定しかつ評価することによってサブマップの組み合わせの十分性をテスト可能で、容認されると対応する細分割と対応する操作のみをパートプログラムで使用してランモードで実行する必要がある。このアプローチはユーザが非常に大きいテンプレートを作成し、ここで多分僅かの形体のみが実際にマッチに貢献している場合（たとえば、大きいテンプレートの中央領域が一つの均一に暗い集団で、この領域がマッチを提供しないかまたは貢献しない場合）に特に有用である。幾つかの空間的変動を含むこれらサブマップのみを選択しかつ使用することで、完全な相関マップを使用するのとほぼ同じ全体のテンプレートマッチングが達成でき、スピードアップの利点も得られる。
【００６４】
本発明の一態様による適応型テンプレート分解技法を実施するのに必要な画素ベースの操作の数は、次のようにして計算可能である。画像のサイズがＭ×Ｎ画素で、テンプレートのサイズがＴ×Ｓ画素に対して、水平テンプレート細区分数“Ａ”と垂直テンプレート細区分数“Ｂ”を使用して、最終の（完全な）相関マップを計算するのに必要な画素ベース操作のおおよその数は、以下に基づいて得ることが可能である:
１．（Ｔ／Ｓ）×Ｓ×Ａ  ＝Ｔ×Ｓ  すべての水平テンプレート投影Ｈｉ（ここでは１＜ｉ＜Ａ）を得るための操作数。
２．Ｔ×（Ｓ／Ｂ）×Ｂ＝Ｔ×Ｓ  すべての垂直テンプレート投影Ｖｉ（ここで１＜ｉ＜Ｂ）を計算するための操作数。
３．３×Ｍ×Ｎ  部分総和法、幅がＴ／Ａのフィルタで、たとえば部分和法を使用して入力画像を水平にスムージングする（フィルタする）ための操作数。スムージングは、すべてのその後の相関操作がそれぞれの水平テンプレート投影に関して行なわれる前に一度実施すればよい（図５のブロック５２０参照）。
４．３×Ｍ×Ｎ  部分総和法、たとえば高さＳ／Ｂのフィルタで、たとえば部分和法を使用して入力画像を垂直にスムージングする（フィルタする）ための操作数。スムージングは、すべてのその後の相関操作がそれぞれの垂直テンプレート投影に関して行なわれる前に一度実施すればよい（図５のブロック５２０参照）。
５．Ａ×Ｍ×Ｎ×Ｓ  水平にスムージングした入力画像をすべての水平テンプレート投影Ｈｉに相関させて、水平相関サブマップを“Ａ”だけ生み出す操作数。
６．Ｂ×Ｍ×Ｎ×Ｔ  垂直にスムージングした入力画像をすべての垂直テンプレート投影Ｖｉに相関させて、垂直相関サブマップを“Ｂ”だけ生み出す操作数。
７．（Ａ×Ｂ−１）×Ｍ×Ｎ  すべてのＡ×Ｂ水平および垂直相関サブマップを組み合わせる（たとえば加算）するための操作数。
【００６５】
したがって必要な操作の合計数は、２ＴＳ＋ＭＮ［６＋ＡＳ＋ＢＴ＋（ＡＢ−１）］となり、２ＴＳ＋ＭＮ（ＡＳ＋ＢＴ＋ＡＢ＋Ｃ）と簡略化される。ここでＣ＜＜Ｔ、Ｓである。完全な２Ｄ相関タイプのテンプレートマッチングと比較すると、必要な操作数に対する割合は［２ＴＳ＋ＭＮ（ＡＳ＋ＢＴ＋ＡＢ＋Ｃ）］／（ＭＮＴＳ）である。合計の最初の構成要素は（２ＴＳ）／（ＭＮＴＳ）≫０であるためこれは無視できる。またＣは合計の３つのほかの構成要素よりずっと小さいと期待されるので、これを無視できる。したがってこの割合はほぼ（ＡＳ＋ＢＴ＋ＡＢ）／（ＴＳ）となる。換言すれば、新規の適応型テンプレート分解技法を使用したテンプレートマッチング法は、完全な２Ｄ相関タイプのテンプレートマッチング法よりほぼ（ＴＳ）／（ＡＳ＋ＢＴ＋ＡＢ）速くなる。（ＴＳ）／（ＡＳ＋ＢＴ＋ＡＢ）は本明細書において“スピードアップ式”と称する。
【００６６】
極端な場合、Ｔ水平投影とＳ垂直“投影”を使用すると（すなわちあらゆる単一のテンプレートカラムと列が投影として処理されると）、適応型テンプレート分解法の性能は（ＴＳ）／（ＴＳ＋ＳＴ＋ＴＳ）＝１／３に低下する。換言すれば、適応型テンプレート構成法は、完全な２Ｄ相関タイプのテンプレートマッチング法より３倍遅くなる。これは、このような高密度“投影”を使用すると、２回計算された完全２Ｄテンプレートの相関が生じてしまうとの事実による（最初カラムとカラムを掛け、次いで列と列を掛ける）。したがってテンプレートの寸法ＴとＳと同程度の数ＡとＢを使用すると、速度の利点は何も得られない。しかし、多様な例示的アプリケーションにおいて、Ａ＜＜ＴおよびＢ＜＜Ｓであり、したがって十分な速度の利点が得られと共に、水平および／または垂直方向へ複数のテンプレート細区分を使用することにより十分に正確なテンプレートマッチング結果が得られる。
【００６７】
一例として、７０×７０のテンプレートと水平および垂直方向への２つの投影に対し、スピードアップはスピードアップ式にしたがって次のように計算される:７０×７０／（２×７０＋２×７０＋２×２）＝４９００／２８４＝１７．２５倍となり、これは完全２Ｄ相関タイプのテンプレートマッチングに対して有意な速度の利点となる。有意に速いテンプレートマッチングをもたらす妥当な数の水平および垂直投影は、テンプレートのサイズとテンプレートにおける詳細量によって左右される。大きなテンプレートは小さなテンプレートより多くの投影を持たせてサンプリングされ、しかもスピードアップの利点を失うことがないが；逆に、詳細が僅かなテンプレートは多くの細かい事項を有するテンプレートより僅かな投影を持たせてサンプリングされ、標準２Ｄマッチングに対して信頼性／精度を失うことがない。本発明のさらなる実施形態において、スピードアップの式（ＴＳ）／（ＡＳ＋ＢＴ＋ＡＢ）を使ってＡとＢの値を動的に推定し、所望のスピードアップの利点を満たすことができる。さらなる実施形態において、スピードアップの式を使って、水平または垂直方向へのテンプレートの細分割に含まれるべき画素の適切な数“Ｎ”を求めることが可能である。既知のテンプレート寸法（Ｔ×Ｓ）について達成すべき目標スピードアップをたとえば１０倍と仮定し、Ａ＝Ｔ／ＮとＢ＝Ｓ／Ｎにしたがって目標のスピードアップを達成するＮを計算できる。ここでＮはＴとＳのいずれよりも小さい。得られたＡとＢは、目標のスピードアップを達成するのに必要な各方向への投影の数を表しており、より正確には、目標のスピードアップを提供可能な投影の最大可能数で、しかもＮが両方向に同じであるため、テンプレートは両方向に均一にサンプリングされる。水平および垂直方向にＮ画素ごとに行なわれるテンプレート投影のための一般的な理論スピードアップ式は（Ｎ＾２）／（２Ｎ＋１）で、これはＮ／２でおおよそ近似可能である。実際には、ある方法で達成されたスピードアップは小さくＮ／３に近いもので、これは相関サブマップの割り当て、処理、組み合わせおよび割り当て解除に要するオーバーヘッドによるものである。したがって実際面では、テンプレートの投影を水平および垂直にたとえばオリジナルのテンプレートの１２画素ごとに生み出すと、標準の２Ｄテンプレートマッチングに対して、処理において約４倍のスピードアップが得られる。
【００６８】
上記に参照した部分総和技法に関し、画像処理の分野における当事者に公知である適用できる技法を使用できる。一般に、部分総和法を使用すると、前処理段階が犠牲になるが画像データへのアクセスがスピードアップされ、これにより部分和の表が作成される。次にこの表を画像の任意の長方形領域におけるグレーレベルの合計の計算に使用し、これは種々な画像フィルタリング操作に有用である。部分総和技法は、“部分総和法を使用した高速空間画像処理”、技術報告ＣＵＥＤ／Ｆ−ＩＮＦＥＮＧ／ＴＲ.２４５、ケンブリッジ大学工学部、１９９６年１月の１６〜１８ページにおける教示にしたがって理解できる。これは範囲探索を行なうためのベクトルドミナンスの使用に似ており、計算幾何学で使われる技法で、たとえば計算幾何学：序論、ＰｒｅｐａｒａｔａとＳｈａｍｏｓ著、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、１９８５に記述がある。
【００６９】
種々な例示的実施形態において、テンプレートの適応型分解は上記に概要を説明したように、生成する必要のある相関擬似画像が最小数となるように、同等の水平寸法を有する所望数の水平細分割および／または同等の垂直寸法を有する所望数の垂直細区分を決定することを含む。上記に説明したように、任意の水平テンプレート細分割が相互にオーバーラップし、任意の垂直テンプレート細分割が相互にオーバーラップしてよい。水平細分割をオーバーラップさせると、同等の水平寸法を有する水平細分割が容易になり、垂直細分割をオーバーラップさせると、同等の垂直寸法を有する垂直細分割が容易になる。種々なほかの実施形態において、それぞれのテンプレート細分割の境界位置は、与えられたテンプレートの細分割に存在する形体の量すなわち形状の情報（たとえばエッジの画素）に応じて調整できる。換言すれば、相対的に大きな細分割を使用して相対的に大きなスムーズな（形体のない）テンプレート区域を包含でき、さらなるテンプレート細分割をさらなる詳細を含むテンプレート区域で使用できる。どのテンプレート区域にさらなる詳細が含まれているかを決めるために、エッジの画素を検出し、種々なテンプレート区域におけるそれらの密度を比較することが可能である。異なるサイズの細分割が使用されている場合、上記に概要を説明したように、決定する必要のある相関擬似画像の数が相応して増大することになる。
【００７０】
図８はテンプレート定義ビデオツール８００のサンプル画面例で、ユーザがテンプレートの分解設定を定義および／または確認できるユーザインターフェースの一例を説明したものである。図８に示す実施形態において、テンプレート定義ビデオツール８００はテンプレートの対象の領域と一致しているテンプレート８１５を含み、これを実線またはツール表示にあるほかのインジケータで示すことができる。テンプレート８１５はテンプレート形体８１６を含む。テンプレート定義ビデオツール８００は“テスト”ボタン８３０を含み、たとえば図１０を参照して次に概要を説明するように、選択されるとテンプレート定義ツール８００の現在のパラメータをテストする。それは“ＯＫ”ボタン８４０も含み、選択されるとテンプレート定義ビデオツール８００の現在のパラメータを受け付けて保存する。
【００７１】
この例においては、テンプレート定義ビデオツール８００はトレードオフモードウインドウ８０３に示すように、テンプレートのトレードオフモードにあり、“ＯＮ”アナンシエータおよび／または制御ボタンならびに“ＯＦＦ” アナンシエータおよび／または制御ボタンを含む。したがってテンプレート８１５は、適切な基準にしたがって複数の水平および／または垂直テンプレート細分割に分解される。図示例ではテンプレート８１５は２つの水平テンプレート細分割８０２と８０４、３つの垂直細分割８０６、８０８および８１０に分解され、これらを点線またはツール表示にあるほかのインジケータで示すことができる。トレードオフモードパラメータウインドウ８０５は、テンプレート定義ビデオツール８００がテンプレートトレードオフモードにあるときアクティブになっている。それ以外では、場合によっては、トレードオフモードパラメータウインドウ８０５はインアクティブおよび／または視野から隠されている。トレードオフモードパラメータウインドウ８０５は、テンプレート定義ビデオツール８００を使用してテンプレートを定義する場合、なされるトレードオフを支配するパラメータを決定する所望のサブモードをユーザが選択できるようにできる。たとえば、テンプレートのトレードオフモード内にあるサブモードの一つは、“概略発見のみ”アナンシエータおよび／または制御ボタンで示されるように、“概略発見のみ”サブモードであってよい。概略発見のみサブモードの選択は、テンプレートマッチングにおける相対的に低いレベルの精度で十分であることを示している。したがって、たとえばテンプレートマッチングの速度またはスループットが向上するように、相対的に少ないテンプレートの細分割を含んでテンプレートが定義されるようにツールパラメータを設定できる。テンプレートトレードオフモード内の第２のサブモードは、高精度位置必要アナンシエータおよび／または制御ボタンで示されるように、“高精度位置必要”である。高精度位置必要サブモードの選択は、テンプレートマッチングにおいて相対的に高レベルの精度が必要なことを示している。したがって、たとえばテンプレートマッチングの精度が向上するように、相対的に多くのテンプレートの細分割を含んでテンプレートが定義されるようにツールパラメータを設定できる。これら２つのサブモードの例示的実施形態は図９を参照して後で説明する。
【００７２】
テンプレートトレードオフモード内の第３のサブモードは、手動細分割編集アナンシエータおよび／または制御ボタンで示されるように、“手動細分割編集”である。例示的実施形態において、本モードの一つの特徴は、生み出されそして表示される垂直細分割の数と水平細分割の数をそれぞれ、ユーザがアクティブにする“＋”（増）および“−”（減）ボタン８１７および８２７でそれぞれ細分割数ウインドウ８０７で制御できる。例示的実施形態において、以下に概要を説明するようにユーザが細分割の境界を明示的に移動または追加しない限り、上記の理由で、テンプレート定義ビデオツール８００の操作は、細分割の数が変更されると、各細分割の調整を同じ寸法を持つことをデフォルトとできる。加えてユーザは、たとえば“領域を無視”アナンシエータおよび／または制御８０９を選択でき、たとえばスクリーンカーソルをその上に置き、マウスボタンを押し下げ、そのコピーをマッチング操作の間無視すべきテンプレート８１５の細分割された区域に “ドラッグ”する。一つの特定例として、細分割がテンプレートの形体の特徴のない“内部区域”で完全に満たされておれば、またはそうでなければ完全に均一であれば、かかる細分割はテンプレートのマッチを見つけるのに有用な情報をほとんどまたはまったく提供しないので、ユーザはかかる細分割をテンプレートマッチング操作から明示的に除外したいと望む。
【００７３】
例示的実施形態において、手動細分割編集サブモードの一つの特長は、ユーザが画面のカーソル（図示せず）を垂直または水平細分割の境界インジケータ上に置いて、たとえばテンプレート８１５に示す点線の一つ、たとえばコンピュータのマウスボタンをクリックするかまたは押し下げて、次いでドラッグするかさもなければ境界を制御してマウスを垂直または水平位置に移動して、境界インジケータをアクティブにできる。代替法としてまたは追加で、ユーザは画面のカーソルを現在の境界インジケータから離してテンプレート８１５内に置き、任意の共通線描画技法を使って追加の細分割を“描く”ことができる。
【００７４】
もちろん上記に概要を説明したテンプレート定義ツール８００の任意の機能を、異なる名前で、異なる組み合わせで、もしくはテンプレートまたはテンプレートマッチングに関連するそのほかのビデオツールに割り当てられた一つまたはそれ以上の機能として、代替えのユーザインタフェース配置に提供できる。加えて、細区分の垂直および／または水平寸法を画素数Ｎに関して指示および／または制御する機能を追加できる。かかる機能は、たとえば手動細分割編集サブモードで提供される。上記に述べたようにＮと完全２Ｄテンプレートマッチングに関連したスピードアップの関係は、典型的にはＮ／３であるため、実際の方法において一部のユーザはこのような機能を評価している。代替または追加として、“ＳＰＥＥＤＵＰ”を指示および／または制御する機能を、たとえば完全な２Ｄテンプレートマッチングに関連して追加でき、画素数Ｎに関した細分割の適切な寸法が、上記に説明した一つ以上のスピードアップの関係に少なくとも部分的に基づいて決定されよう。かかる機能は、たとえば概略発見のみサブモードで提供できる。
【００７５】
図９は例示的テンプレート探索またはパターン探索ツールウインドウ９００のサンプル画面例で、ユーザが種々のテンプレートマッチングパラメータを定義および／または確認できるユーザインタフェースの一例を説明したものである。手動操作または学習モード操作の間にテンプレートマッチング操作が必要な場合、またはたとえばパートプログラムを編集する場合、ツールウインドウ９００が現れる。ツールウインドウ９００は７つの例示的パラメータウインドウを含む。現在のパターンファイル名ウインドウ９０２は、テンプレートマッチング操作に使用すべき現在のパターン（テンプレート）ファイルを示しており、ユーザインタフェースと図８に示すものと似た表示を、テンプレートの定義のさらなる調整またはレビューのために呼び出すことのできる“オープンテンプレート”制御ボタン、およびさらなる調整またはレビューのために、定義されたテンプレートに関連した種々のパラメータを表形式に、またはパラメータウインドウになどに表示する“プロパティ”制御ボタンも含んでいる。
【００７６】
精度ウインドウ９０４は、“テンプレートパラメータを使用せよ”アナンシエータまたは制御が選択されている場合、ユーザが定義されたテンプレートに関連した精度“トレードオフ”を使用すべきであることを確認し、“最大可能”アナンシエータまたは制御が選択されている場合、ユーザが定義されたテンプレートをオーバーライドして最大可能精度を提供できるようにする。たとえば、“テンプレートパラメータを使用せよ”アナンシエータまたは制御が選択されている場合、テンプレート定義ツール８００を使用して定義されたパラメータなどに基づき、テンプレートマッチング操作は本開示で概要を説明した種々の方法を含むことができる。“最大可能”アナンシエータまたは制御が選択されている場合、たとえば市販されているシステムにおける公知の慣習にしたがって、テンプレート８１５とテンプレート形体８１６を単に使用して完全２Ｄテンプレートマッチングを提供でき、このような場合には任意の細分割と関連のパラメータを単に無視してよい。
【００７７】
探索領域ウインドウ９０５は、ユーザが探索する画像全体を指定するか、またはテンプレートとのマッチを探索する画像全体の中の領域の公称位置（ｘ、ｙ）とサイズ（幅と高さ）を定義可能にする。パターン探索ツールは、たとえばグラフィカルボックスを位置決めしサイジングすることによって、ユーザが対象の探索領域を入力画像上に定義できる関連ユーザインタフェース（図示せず）を備えることができる。このような場合、探索領域ウインドウにおける数は最初は対象の定義された領域を反映しているが、その後編集できる。探索区域ウインドウ９０６におけるマッチ数で、たとえば期待数のマッチを測定物のデザインに基づいて定義可能であれば、ユーザは特定の探索区域で見つける最大および最小マッチ数を設定できる。このような場合、ランタイムに実行されるテンプレートマッチングツール操作は、“ベスト”テンプレートマッチを選択するかまたはテンプレートマッチ数を増すか、探索区域における期待数のマッチに対応するために、相関強度情報にアクセスおよび／または制御するルーチンおよび／または上記に概要を説明した閾値設定を含めることができる。最大または最小期待数を設定しない場合は、ユーザは“任意”を選択できる。
【００７８】
テンプレートマッチング操作が、（検査時にいろいろな角度で現れることのあるテンプレート形体とマッチさせるため）入力画像またはテンプレートを探索する角度範囲にわたって回転させる能力を含んでおれば、探索角度範囲ウインドウ９０７によってユーザは探索する角度範囲を定義できる。同様に、テンプレートマッチング操作が、（検査時にいろいろなサイズで現れることのあるテンプレート形体とマッチさせるため）入力画像またはテンプレートを探索する“倍率”の範囲にわたってスケールする能力を含んでおれば、スケール範囲ウインドウ（図示せず）によってユーザは探索するスケール範囲を定義できる。
【００７９】
候補ウインドウ９０８に対する閾値によってユーザは、テンプレートマッチング位置候補を同定するために、閾値レベルを“低”から“高”に調整できる。このような場合、ランタイムに実行されるテンプレートマッチングツール操作は、テンプレートマッチのための候補場所として考えられる相関ピークの数を増減させるために、上記に概要を説明した相関強度閾値設定にアクセスおよび／または制御するルーチンを含めることができる。閾値は、たとえば候補領域においてすべての相関“画素値”を合計して計算した各テンプレートマッチング位置候補の“強度”値に関して設定できる。一例を示すと、もし特定の数または範囲が、探索区域ウインドウ９０６におけるマッチ数において決定されておれば、（“偽陰性”の機会を低減しかつロバスト性を持たせるため、すべての可能性のあるマッチング候補が考慮されるように）閾値レベルを相対的に低い値に設定し、（マッチングの信頼性を得るために）“マッチ数”で実際のマッチ数を制限させるのが効果的である。
【００８０】
マッチ確実性ウインドウ９０９によってユーザは確実性のレベルを０％から１００％に設定できる。一例として、テンプレートマッチング時に確実性レベルは２次相関閾値チェックを提供できる。すなわち候補ウインドウ９０８の閾値における設定をパスした候補マッチは、もしそれらが確実性レベルの設定によって不合格となると拒否されることがある。保守的なテンプレートマッチングのアプローチが適切な場合は、確実性のレベルを上げると“偽陽性”の発生が減少し、最終テンプレートマッチの信頼性が向上する。様々な実施形態において、たとえば最高のマッチング信頼性を保証しおよび／または低質な入力画像を検出し、またはテンプレートにマッチする測定物の形体の品質の低下を検出することなどが好ましい場合、確実性のレベルが探索区域ウインドウ９０６におけるマッチ数の設定をオーバーライドできる。
【００８１】
図１０は、パターンまたはテンプレート探索対象領域（ＲＯＩ）オーバーレイ１０００、およびユーザ入力部１００５を含むユーザインタフェース表示のサンプル画面例で、この画面は、図８を参照して記述したテンプレート定義ビデオツール８００、および／またはテンプレートマッチングツール１４５（図２に示す）、または図９を参照して記述したテンプレート探索またはパターン探索ツールウインドウ９００の場合のように、学習モードの間および／またはテンプレート定義ビデオツール１４８（図２に示す）のトレーニングまたはパラメータの最終決定に関して表示される。（ＲＯＩ）オーバーレイ１０００およびユーザ入力部１００５によってユーザは、学習モードにおけるトライアルまたは最初のテンプレートマッチング操作に起因するテンプレートマッチング位置を容認または拒否できる。たとえば学習モードにおいて、上記に概要を説明したようにテンプレート定義ビデオツール８００に対して一つ以上パラメータを定義した後、“テスト”ボタンを選択して、定義されたパラメータに基づき、入力画像全体でテンプレートマッチを探索できる。代替法として、テンプレートを定義した後、学習モードにおいて、テンプレートマッチングツールを探索対象領域でテストできる。いずれの場合でも、次いで（ＲＯＩ）オーバーレイ１０００を表示してマッチング結果を示し、ユーザ入力部１００５を示すことができる。ＲＯＩオーバーレイ１０００は入力画像全体または定義されておれば対象の探索領域のいずれかを包含する。この場合ＲＯＩオーバーレイ１０００において、入力画像上の定義されたマッチング位置においてテンプレート形体をオーバーレイすることによって、５つのテンプレートマッチング位置１００２ａ〜１００２ｅが同定されている。ユーザはそれぞれの位置の隣に表示されている“ＯＫ”アイコンまたは“間違い”アイコン１００３の一つを選択することによって、５つの位置のそれぞれをを評価して、視覚で確認（容認）または拒否できる。すべてのマッチが正しくかつそれらの位置も容認できれば、ユーザはＲＥＳＵＬＴＳウインドウ１００５にある“全てＯＫ”を選択でき、テスト時に教え込んだツールのパラメータが容認され、それらの現在の設定に保存される。全てＯＫボタンも表示を戻すか、またはテスト操作の直前の操作および／または表示から操作を継続できる。“間違い”アイコンを選択することによってマッチの一部が拒否されると、ユーザはＲＥＳＵＬＴウインドウ１００５にある“再度ラン”アイコンを選択して、細分割の数を増やすなどの調整をしたテンプレートパラメータでテストを再試行させ、新しい結果がＲＯＩオーバーレイ１０００に表示される。このような場合、一実施形態において、たとえば、基礎をなすテンプレート定義ツールの相関閾値パラメータを調整または制御して、確認したまたは容認したマッチに対応する相関強度を容認し拒否されたマッチに対応する相関強度を拒否できる。
【００８２】
すべてのマッチが正しいがそれらの位置の一つ以上が容認できない場合、ユーザはＲＥＳＵＬＴＳウインドウ１００５にある“精度を改善”アイコンを、続いて“再度ラン”アイコンを選択して、調整されたテンプレートパラメータとＲＯＩオーバーレイ１０００に表示されている新しい結果を使ってテストを再度ランさせてよい。このような場合、基礎をなすテンプレート定義ツールのパラメータを調整または制御して、たとえば細分割の数を増加できる。代替法として、細分割が最大数になると、完全な２Ｄテンプレートマッチング操作を実行し、新しい結果がＲＯＩオーバーレイ１０００に表示されているときに“精度を改善”アイコンを“最大精度表示”通知に置換できる。調整されたテンプレート分解設定であるテンプレートパラメータをテストして得られるマッチング結果を決定し、そのようなマッチング結果が容認できるか否か評価する。容認できる場合には、当該テンプレートパラメータを定義されたテンプレート分解設定として使用するが、容認できない場合には、容認できるマッチング結果が決定されるまで、上記ステップを繰り返す。
【００８３】
テンプレートマッチング操作によってすべてのマッチング形体が同定されているとは限らないとユーザが決めると、ユーザはＲＥＳＵＬＴＳウインドウ１００５にある“さらに探す”アイコンを選択して調整されたテンプレートパラメータとＲＯＩオーバーレイウインドウ１０００に表示されている新しい結果を使ってテストを再試行させてよい。このような場合、一実施形態において、基礎をなすテンプレート定義ツールの相関閾値パラメータを調整または制御して、同定すべき追加のマッチング形態を通常もたらす低相関強度を、もし存在すれば、容認できる。
【００８４】
上記に概要を説明した種々のシステムおよび方法は、説明のために種々の画像、“擬似画像”および“マップ”を提供しかつそれらの上で作動すると記述したが、かかる画像、“擬似画像”および“マップ”はいろいろな代替えの設定内に組織化され、保存されおよび／または数学的に表されるデータを本質的に含むことを理解されたい。したがってこれらの用語は本質的には、かかる設定が従来の画像、“擬似画像”および“マップ”として容易に認識されるかどうかとは無関係に、本明細書で開示される基本的な教示によって使用可能ないろいろなデータ設定を参照することを理解されたい。本発明の好ましい実施形態と例示的実施形態を説明し記述したが、本発明の趣旨および範囲を逸脱することなく、本発明の原理にしたがって様々な変更が可能であることを理解されたい。
【図面の簡単な説明】
【００８５】
【図１】汎用マシンビジョン検査システムの種々の典型的な構成要素を示す図である。
【図２】マシンビジョン検査システムの制御システム部とビジョン構成要素部分の図である。
【図３】積分投影を使用するテンプレートマッチング法を説明した図である。
【図４】本発明の一局面による適応型テンプレート分解による高速テンプレートマッチング手法を説明した図である。
【図５】本発明の一局面にしたがって、マシンビジョン検査システムの学習モード操作の間に行なう、適応型テンプレート分解技法を使用したテンプレートの定義方法を説明したフローダイアグラムである。
【図６】テンプレートマッチング位置（複数）を同定するための相関マップを解析する方法を説明したフローダイアグラムである。
【図７】マシンビジョン検査システムの学習モードの間に、本発明の一局面にしたがって実施する全体の操作を説明したフローダイアグラムである。
【図８】ユーザが本発明の一局面にしたがって所望のテンプレート分解設定を決定し定義するのに適切な、テンプレート定義ツールＧＵＩの例を説明した画面例である。
【図９】ユーザが本発明の一局面にしたがって所望のテンプレート分解設定を決定し定義するのに適切な、テンプレート定義ツールＧＵＩの例を説明した画面例である。
【図１０】ユーザが本発明の一局面にしたがって所望のテンプレート分解設定を決定し定義するのに適切な、テンプレート定義ツールＧＵＩの例を説明した画面例である。
【符号の説明】
【００８６】
１０          マシンビジョン検査システム
１２          画像測定機
１４          制御コンピュータシステム
１６          ディスプレイ（またはモニタ）
１８          プリンタ
２０          測定物
２２          ジョイスティック
２４          キーボード
２６          マウス
３２          可動測定物載荷台
３４          光学画像システム
１００        マシンビジョン検査システム
１２０        制御システム部（または制御システム）
１２５        コントローラ
１３０        入出力インタフェース
１３１        画像制御インタフェース
１３２        制御インタフェース
１３２ａ      位置制御要素
１３２ｂ      加速制御要素
１３３        照明制御インタフェース
１３３ａ-１３３ｎ    照明制御要素
１３４        レンズ制御インタフェース
１３６        表示装置
１３８        入力装置
１４０        メモリ部（またはメモリ）
１４１        画像ファイルメモリ部
１４２        測定物プログラムメモリ部
１４３        ビデオツール部
１４３ａ-１４３ｍ    ツール部
１４３ｘ      領域生成装置
１４５        テンプレートマッチングツール
１４８        テンプレート定義ツール（またはテンプレート定義ビデオツールもしくはテンプレート創造ビデオツール）
１７０        エクゼキュータ
１８０        ファイル特徴抽出部
１９０        電源部
２００        ビジョン構成要素部分（またはビジョンシステム構成要素部分）
２０５        光学アセンブリ部
２１０        測定物載荷台
２１２        透過照明部
２２０        光源（または載荷台光）
２２１        バス
２２２        光源光
２３０        同軸光（または同軸光源もしくは光源）
２３１        バス
２３２        光源光
２４０        面光
２５０        交換対物レンズ
２５５        測定物光
２６０        カメラシステム
２６２        信号ライン
２８０        ターレットレンズアセンブリ
２８１        バス
２８４        軸
２８６        レンズ
２８８        レンズ
２９４        モータ
２９６        信号ライン
３００        テンプレート
３０１        テンプレート形体
３０２        テンプレート形体部分（または形体部分）
３０４        テンプレート形体部分
３０６        テンプレート形体部分
３０８        垂直投影ライン
３１０        水平投影ライン
３１２        投影部分（または水平投影部分）
３１４        水平投影部分
３１６        垂直投影部分
３１８        セクション
３２０        水平テンプレート細分割
３２２        水平テンプレート細分割
３２４        垂直テンプレート細分割
３２６        垂直テンプレート細分割
３２８        垂直テンプレート細分割（または水平投影ライン）
３３２        水平投影部分
３３６        水平投影部分
３４０        垂直投影ライン
３４６        垂直投影部分
３４８        垂直投影部分
３５２        垂直投影部分
３６０        テンプレート幅寸法（幅寸法）
３６２        寸法
３７０        細分割寸法（寸法）
３７２        寸法
３７４        細分割寸法
３７６        寸法
５００        適応型テンプレート分解技法ルーチン（またはルーチン）
５０５-５５５   ブロック
５６０        決定ブロック（またはブロック）
５６５        ブロック
６００        相関マップ解析ルーチン
６０５-６４０   ブロック
７００        ルーチン
７０５-７４０   ブロック
７４５        ステップ
７５０        ルーチン（またはブロック）
７５５        ブロック
８００        テンプレート定義ツール（またはテンプレート定義ビデオツール）
８０２        水平テンプレート細分割
８０３        トレードオフモードウインドウ
８０５        トレードオフモードパラメータウインドウ
８０６        垂直細分割
８０７        細分割数ウインドウ
８０９        制御
８１５        テンプレート
８１６        テンプレート形体
８１７        “＋”（増）および“−”（減）ボタン
８３０        テストボタン
８４０        ＯＫボタン
９００        パターン探索ツールウインドウ（またはツールウインドウ）
９０２        パターンファイル名ウインドウ
９０４        精度ウインドウ
９０５        探索領域ウインドウ
９０６        探索区域ウインドウ
９０７        探索角度範囲ウインドウ
９０８        候補ウインドウ
９０９        マッチ確実性ウインドウ
１０００      オーバーレイウインドウ（またはオーバーレイ）
１００２ａ-１００２ｅ  テンプレートマッチング位置
１００３      アイコン
１００５      ＲＥＳＵＬＴウインドウ（またはユーザ入力部）
【図１】
2007026446.tif 000003
【図２】
2007026446.tif 000004
【図３】
2007026446.tif 000005
【図４】
2007026446.tif 000006
【図５】
2007026446.tif 000007
【図６】
2007026446.tif 000008
【図７】
2007026446.tif 000009
【図８】
2007026446.tif 000010
【図９】
2007026446.tif 000011
【図１０】
2007026446.tif 000012