(57)【要約】【課題】最小二乗法を用いた精密位置決めの精度、特に回転角度の精度を向上させる。【解決手段】登録画像から輪郭を抽出し、登録画像のパターンモデルを構築する工程と、サーチ対象画像を取得すると共に、該サーチ対象画像中に含まれる登録画像に対応する初期位置を取得し、該初期位置に従って、前記パターンモデルをサーチ対象画像上に重ねるように配置する工程と、前記パターンモデルを構成する各円弧セグメントに対応するサーチ対象画像上の個々の対応エッジ点を求める工程と、各円弧セグメントとその対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように、前記与えられた初期位置の精度よりも高い精度で精密位置決めを行う工程とを含む。【選択図】図１
2010067248.tif 000002
【特許請求の範囲】
【請求項１】
予め登録された登録画像に対応するパターンモデルを用いて、サーチ対象画像中から登録画像に類似する対象物をサーチして位置決めを行う際に、当初与えられた初期位置よりも高い精度で位置決めを行う画像処理におけるパターンモデルの位置決め方法であって、
登録画像から複数のエッジ点を抽出する工程と、
抽出された複数のエッジ点の内、隣接しているエッジ点同士を連結して連続したチェーンを作成する工程と、
一以上のチェーンに対して、各々少なくとも円弧で近似したセグメントを作成し、セグメントの集合を輪郭とすることで、登録画像から輪郭を抽出し、登録画像のパターンモデルを構築する工程と、
サーチ対象画像を取得すると共に、該サーチ対象画像中に含まれる登録画像に対応する初期位置を取得し、該初期位置に従って、前記パターンモデルをサーチ対象画像上に重ねるように配置して、前記パターンモデルを構成する各円弧セグメントに対応するサーチ対象画像上の個々の対応エッジ点を求める工程と、
各円弧セグメントとその対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように、前記与えられた初期位置の精度よりも高い精度で精密位置決めを行う工程と、
を含むことを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項２】
請求項１に記載の画像処理におけるパターンモデルの位置決め方法において、
前記登録画像のパターンモデルを構築する工程が、抽出された輪郭上に、一以上の基点を設定すると共に、各基点に対して、基点を通りかつ輪郭と略直交する所定長さの対応点探索ラインを割り当てるものであり、
前記対応エッジ点を求める工程が、前記サーチ対象画像上の、少なくとも対応点探索ラインに沿った位置におけるエッジ角度に基づいて、基点と対応するサーチ対象画像上の対応エッジ点を各対応点探索ラインについて求めるものであり、
前記精密位置決めを行う工程が、各々基点と該基点の対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように精密位置決めを行うことを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項３】
請求項１又は２に記載の画像処理におけるパターンモデルの位置決め方法において、
前記精密位置決めを行う工程が、パターンモデルの位置及び姿勢を求めるために、サーチ対象画像及びパターンモデルに含まれる各エッジ点のエッジ角度を各々比較して一致度を計算するものであることを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項４】
請求項１から３のいずれか一に記載の画像処理におけるパターンモデルの位置決め方法において、
前記精密位置決めを行う工程が、前記評価値の累積値を、各円弧セグメントとその対応エッジ点との距離を用いて、最小二乗法で用いるエラー値又はウェイト値を演算するものであることを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項５】
請求項１から４のいずれか一に記載の画像処理におけるパターンモデルの位置決め方法において、
前記登録画像のパターンモデルを構築する工程におけるパターンモデルが、一以上のチェーンを各々円弧又は線分で近似した円弧セグメント及び線分セグメントで構成され、
前記精密位置決めを行う工程における前記最小二乗法が、円弧セグメントに対しては、対応エッジ点と円弧の距離を計算するエラー関数を適用し、線分セグメントに対しては、対応エッジ点と直線の距離を計算するエラー関数を適用してなることを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項６】
請求項５に記載の画像処理におけるパターンモデルの位置決め方法において、
前記パターンモデルは、該パターンモデルを構成する各セグメントの種別として、少なくとも円弧又は線分であるを示すセグメント種別パラメータの情報を有することを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項７】
請求項４から６のいずれか一に記載の画像処理におけるパターンモデルの位置決め方法において、
前記精密位置決めを行う工程における最小二乗法が、円弧セグメントのパターンモデルの中心とサーチ対象画像の対応エッジ点との距離と、円弧セグメントの半径との差の絶対値をエラー値とするエラー関数を適用してなることを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項８】
請求項４から６のいずれか一に記載の画像処理におけるパターンモデルの位置決め方法において、
前記精密位置決めを行う工程における最小二乗法で用いる円弧セグメントのエラー関数を、円弧セグメントを中心とする理想半径と、円弧の中心と対応エッジ点の距離の差とすることを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項９】
請求項４から８のいずれか一に記載の画像処理におけるパターンモデルの位置決め方法において、
前記精密位置決めを行う工程における最小二乗法で用いる円弧セグメントのエラー関数が、次式で表現されることを特徴とする画像処理におけるパターンモデルの位置決め方法。
【数１】
2010067248.tif 000026
【請求項１０】
請求項４から８のいずれか一に記載の画像処理におけるパターンモデルの位置決め方法において、
前記精密位置決めを行う工程における最小二乗法で用いる円弧セグメントのエラー関数が、次式で表現されることを特徴とする画像処理におけるパターンモデルの位置決め方法。
【数２】
2010067248.tif 000027
【請求項１１】
請求項４から１０のいずれか一に記載の画像処理におけるパターンモデルの位置決め方法において、
前記精密位置決めを行う工程における最小二乗法の重みが、エラー値の関数であることを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項１２】
請求項４から１０のいずれか一に記載の画像処理におけるパターンモデルの位置決め方法において、
前記精密位置決めを行う工程における最小二乗法の重みが、セグメントの法線の向きと対応エッジ点のエッジ角度の向きの差の関数であることを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項１３】
請求項１から１２のいずれか一に記載の画像処理におけるパターンモデルの位置決め方法において、
前記エッジ角度画像を演算する工程が、前記エッジ角度情報を含むエッジ角度画像に加え、画像を構成する各画素におけるエッジ強度情報を含むエッジ強度画像を演算することを特徴とする画像処理におけるパターンモデルの位置決め方法。
【請求項１４】
予め登録された登録画像に対応するパターンモデルを用いて、サーチ対象画像中から登録画像に類似する対象物をサーチして位置決めを行う際に、当初与えられた初期位置よりも高い精度で位置決めを行う画像処理装置であって、
登録画像及びサーチ対象画像を取得する画像入力手段と、
前記画像入力手段で取得された登録画像から複数のエッジ点を抽出し、抽出された複数のエッジ点の内、隣接しているエッジ点同士を連結して連続したチェーンを作成するチェーン作成手段と、
前記チェーン作成手段で作成された一以上のチェーンに対して、各々少なくとも円弧で近似したセグメントを作成するセグメント作成手段と、
前記セグメント作成手段で作成されたセグメントから登録画像のパターンモデルを構築するパターンモデル構成手段と、
前記画像入力手段で取得されたサーチ対象画像中に含まれる登録画像に対応する初期位置を取得し、該初期位置に従って、前記パターンモデルをサーチ対象画像上に重ねるように配置して、前記パターンモデルを構成する各円弧セグメントに対応するサーチ対象画像上の個々の対応エッジ点を求め、各円弧セグメントと、その対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように、当初与えられた初期位置よりも高い精度で精密位置決めを行うための精密位置決め手段と、
を備えることを特徴とする画像処理装置。
【請求項１５】
予め登録された登録画像に対応するパターンモデルを用いて、サーチ対象画像中から登録画像に類似する対象物をサーチして位置決めを行う際に、当初与えられた初期位置よりも高い精度で位置決めを行う画像処理プログラムであって、
登録画像及びサーチ対象画像を取得する画像入力機能と、
前記画像入力機能で取得された登録画像から複数のエッジ点を抽出し、抽出された複数のエッジ点の内、隣接しているエッジ点同士を連結して連続したチェーンを作成するチェーン作成機能と、
前記チェーン作成機能で作成された一以上のチェーンに対して、各々少なくとも円弧で近似したセグメントを作成するセグメント作成機能と、
前記セグメント作成機能で作成されたセグメントの集合を輪郭とし、登録画像から輪郭を抽出する輪郭抽出機能と、
前記輪郭抽出機能で抽出された輪郭から登録画像のパターンモデルを構築するパターンモデル構成機能と、
前記画像入力機能で取得されたサーチ対象画像中に含まれる登録画像に対応する初期位置を取得し、該初期位置に従って、前記パターンモデルをサーチ対象画像上に重ねるように配置して、前記パターンモデルを構成する各円弧セグメントに対応するサーチ対象画像上の個々の対応エッジ点を求め、各円弧セグメントと、その対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように、当初与えられた初期位置よりも高い精度で精密位置決めを行うための精密位置決め機能と、
をコンピュータに実現させることを特徴とする画像処理プログラム。
【請求項１６】
請求項１５に記載の画像処理プログラムにおいて、さらに、
前記画像入力機能で取得されたサーチ対象画像を所定の縮小率で縮小するための画像縮小機能と、
前記画像縮小機能で縮小された縮小サーチ対象画像に対し、画像を構成する各画素に対して、エッジ角度情報を含むエッジ角度画像を演算するエッジ角度画像作成機能と、
前記エッジ角度画像作成機能で作成したエッジ角度画像の各画素につき、予め規定された一定幅の角度を示すエッジ角度ビットで表現したエッジ角度ビット画像に変換するエッジ角度ビット画像作成機能と、
前記エッジ角度ビット画像を縮小したエッジ角度ビット縮小画像を生成するために、該エッジ角度ビット画像を縮小する縮小率に応じて決定されるＯＲ演算領域に含まれるすべての画素のエッジ角度ビットをＯＲ演算し、各ＯＲ演算領域を表す縮小エッジ角度ビットデータで構成されたエッジ角度ビット縮小画像を生成するエッジ角度ビット画像縮小機能と、
前記画像縮小機能により第１の縮小率で縮小された第１縮小サーチ対象画像に関して、前記エッジ角度ビット画像縮小機能で生成される第１エッジ角度ビット縮小画像に対して、該第１の縮小率にて生成された第１の粗サーチ用パターンモデルをテンプレートとしてパターンサーチを行い、前記第１エッジ角度ビット縮小画像の全域から前記第１の粗サーチ用パターンモデルに対応する第１の位置及び姿勢を、第１の精度で求めると共に、前記画像縮小機能により第１の縮小率以下で等倍以上の第２の縮小率に縮小された第２縮小サーチ対象画像に関して、前記エッジ角度ビット画像縮小機能で生成される第２エッジ角度ビット縮小画像に対して、該第２の縮小率にて生成された第２の粗サーチ用パターンモデルをテンプレートとしてパターンサーチを行い、前記第２縮小サーチ対象画像の、前記第１の位置及び姿勢を基準とする所定の領域中から第２の粗サーチ用パターンモデルに対応する第２の位置及び姿勢を、前記第１の精度よりも高精度な第２の精度で求める粗サーチ機能と、
をコンピュータに実現させ、
前記精密位置決め機能は、サーチ対象画像を必要に応じて等倍以上かつ第２の縮小率以下である第３の縮小率に縮小した第３縮小サーチ対象画像の、前記第２の位置及び姿勢を用いて、パターンモデルを第３縮小サーチ対象画像上に重ねるように配置し、前記パターンモデルを構成する輪郭に対応する第３縮小サーチ対象画像上の対応エッジ点を求め、各輪郭とその対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように、前記第２の精度よりも高い第３の精度で精密位置決めを行うことを特徴とする画像処理プログラム。
【請求項１７】
請求項１５又は１６に記載のプログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予め登録された登録画像に対応するパターンモデルを、サーチ対象画像中からサーチして位置決めを行う際に、より高い精度で精密位置決めを行う画像処理におけるパターンモデルの位置決め方法、画像処理装置、画像処理プログラム及びコンピュータで読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
撮像素子で撮像した画像を処理する画像処理装置は一般に、画像処理対象物（以下、「ワーク」とも呼ぶ）を撮像する撮像装置と、その撮像装置により撮像した画像のデータを記憶する画像データ記憶手段と、画像データ記憶手段に記憶された画像データを処理する画像データ処理手段とを備える。例えば、撮像装置をＣＣＤカメラで構成した画像処理装置においては、撮像面を構成する多数の電荷結合素子の各電荷量に基づいて２５６階調や１０２４階調等の輝度データ（いわゆる多値データ）を得、それによりサーチ対象物であるワークのサイズ、位置、回転角度等を求めることができる。従来、画像データを処理して画像処理でサーチ対象物をサーチする手法として、画像間の画素差分値の絶対値の合計値をサーチに用いた差分サーチや、画像間の正規化相関値をサーチに用いた正規化相関サーチ等が知られている。これらのサーチは予めサーチしたいサーチ対象物をテンプレート画像として登録して、その画像に基づいて、サーチ対象画像中からサーチ対象物のサーチを実行する。これらのサーチ処理においては、従来は画像データを使った領域ベースのサーチが主流であった。しかしながら、このような従来の、画像の濃淡等に基づく領域ベースのサーチは、画像撮像時の照度変化等の影響を受けやすいといった問題があった。
【０００３】
一方で、登録画像とサーチ対象画像に対してエッジ抽出処理を行って、エッジ情報に基づきサーチを行う方法も提案されている。この方法では、画像データを構成する画素の濃度値でなく濃度値の変化量に基づいたエッジデータを用いるため、撮像時の照度の変動による影響を受け難いという利点が得られる。特に近年は、そのロバスト性の高さからエッジを特徴量としたエッジベースのパターンサーチが注目を集め、工業用途等での実用化が行われている。
【０００４】
パターンサーチの処理速度を向上させる手法として、コース・トゥ・ファイン（coarse to fine）のアプローチが知られている。すなわち、最初に低解像度の画像（コース画像）を用いて粗くサーチし、大まかな位置を特定した後に、高解像度の画像（ファイン画像）を用い、詳細な位置決めを行うことで位置や姿勢の精度を高めている。コース・トゥ・ファイン型のテンプレートマッチングでエッジベースのサーチを行う場合は、オリジナルデータに対して圧縮（「間引き」等とも呼ばれる。）した粗いデータでサーチを行い、大まかな位置を特定した上で、詳細なデータを用いてサーチを行うピラミッドサーチが利用される。ピラミッドサーチの概念を図８７に示す。この図に示すように、縮小率の高い、低解像度の画像を用いて粗いサーチ（「粗サーチ」等と呼ばれる。）を行い、大まかな位置を求めた後、解像度を上げた中間の縮小率でその近辺のサーチを行い、最終的にオリジナルサイズ又はそれに近い縮小率の画像に対して詳細なサーチを行う。このようにピラミッドサーチにおいては一般に、解像度を変更した複数の画像を用意し、まず最低解像度の画像で概略位置を検出する。以降の処理では、徐々に解像度を高めながら、探索の範囲を前回の検出位置近傍に絞って探索する。これにより、処理の段階が進む毎に検出位置の精度が高まり、最終的に元画像又はそれに近い解像度で高精度の位置の検出が可能となる。この方法では広い探索範囲を解像度の低い画像で探索することで、効率良く位置検出が行える。
【０００５】
このようなコース・トゥ・ファイン型のテンプレートマッチングで位置や姿勢を高精度に求める精密位置決めに関する技術としては、特許文献１の画像処理装置が知られている。また、このような精密位置決めにおいては、従来最小二乗法が多く利用されてきた。
【０００６】
従来の最小二乗法を用いた精密位置決めにおいては、点と接線の距離をエラー関数として演算されている。図４７及び図４８に基づいて、従来の最小二乗法を用いた精密位置決めの例として、一部を平面状に切り欠いたワークのパターンマッチングを行う場合を説明する。これらの図において、図４７は粗サーチを行い、ある程度の位置決めが終了した状態を、図４８はさらに精密位置決めを行ってパターンモデルＰＭをサーチ対象画像に重ねようとした状態を、それぞれ示している。またこれらの図において、太線はパターンモデルＰＭを、細線はサーチ対象画像のエッジ点（入力エッジ点ＩＥ）を、それぞれ示す。さらに入力エッジ点ＩＥの注目点を破線矢印で示すと共に、この入力エッジ点の接線ＳＬを破線で示す。なお実際の接線ＳＬはもっと短く、細線のパターンモデルＰＭに重なる状態で存在しているが、これらの図においては説明の便宜上長く表示している。
【０００７】
最小二乗法では、入力エッジ点と接線ＳＬの距離をエラー関数とし、この距離が小さくなるようにパターンモデルＰＭを移動（回転）させる。今、図４７のように粗サーチの結果、ある程度パターンモデルＰＭと入力エッジ点が重なっている状態にあるとする。この状態からさらに精密位置決めを行うならば、図４８に示すようにパターンモデルＰＭを時計回りに回転させて（あるいは入力エッジ点側を時計回りに回転させて）パターンモデルＰＭと入力エッジ点とを一致させることが期待される。
【０００８】
しかしながら、本件発明者らが検討した結果、このようなほぼ円形のワークに対して最小二乗法を適用した場合、適切な位置決めが行われないケースが発生することが判明した。すなわち、矢印で示す位置にある入力エッジ点と接線ＳＬの関係を見ると、図４８に示すように矢印で示す入力エッジ点が接線ＳＬから離れる方向に回転している。このことは、点と接線ＳＬの距離をエラー関数として最小二乗法を適用し、エラーが小さくなる方向に回転させると仮定するならば、図４８のような回転は解として生じ得ないことを意味する。
【０００９】
このため、粗サーチの結果、回転角度が不適切な場合は、たとえ精密位置決めを複数回繰り返したとしても、適切な回転位置の出力が得られない虞があり、位置決め角度の精度が不十分となるという問題が生じる。
【特許文献１】特許第３７５９９８３号公報
【特許文献２】特開平７−１２８０１７号公報
【特許文献３】米国特許第６４０８１０９Ｂ１号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、このような問題点を解決するためになされたものである。本発明の一の目的は、最小二乗法を用いた精密位置決めの精度、特に回転角度の精度を向上させた画像処理におけるパターンモデルの位置決め方法、画像処理装置、画像処理プログラム及びコンピュータで読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段及び発明の効果】
【００１１】
上記目的を実現するために、第１の画像処理におけるパターンモデルの位置決め方法は、予め登録された登録画像に対応するパターンモデルを用いて、サーチ対象画像中から登録画像に類似する対象物をサーチして位置決めを行う際に、当初与えられた初期位置よりも高い精度で位置決めを行う画像処理におけるパターンモデルの位置決め方法であって、登録画像から複数のエッジ点を抽出する工程と、抽出された複数のエッジ点の内、隣接しているエッジ点同士を連結して連続したチェーンを作成する工程と、一以上のチェーンに対して、各々少なくとも円弧で近似したセグメントを作成し、セグメントの集合を輪郭とすることで、登録画像から輪郭を抽出し、登録画像のパターンモデルを構築する工程と、サーチ対象画像を取得すると共に、該サーチ対象画像中に含まれる登録画像に対応する初期位置を取得し、該初期位置に従って、前記パターンモデルをサーチ対象画像上に重ねるように配置して、前記パターンモデルを構成する各円弧セグメントに対応するサーチ対象画像上の個々の対応エッジ点を求める工程と、各円弧セグメントとその対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように、前記与えられた初期位置の精度よりも高い精度で精密位置決めを行う工程とを含むことができる。これにより、円状のワークにおいて少ない回数の精密位置決めで高い角度の精度の達成が期待できる。
【００１２】
また第２の登録画像におけるパターンモデルの位置決め方法は、前記登録画像のパターンモデルを構築する工程が、抽出された輪郭上に、一以上の基点を設定すると共に、各基点に対して、基点を通りかつ輪郭と略直交する所定長さの対応点探索ラインを割り当てるものであり、前記対応エッジ点を求める工程が、前記サーチ対象画像上の、少なくとも対応点探索ラインに沿った位置におけるエッジ角度に基づいて、基点と対応するサーチ対象画像上の対応エッジ点を各対応点探索ラインについて求めるものであり、前記精密位置決めを行う工程が、各々基点と該基点の対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように精密位置決めを行うことができる。これにより、基点上に設定された対応点探索ラインで対応エッジ点を求め、この対応エッジ点と基点との距離に基づいた正確な位置決めが行える。また対応点探索ラインの長さを変更することで、容易に対応エッジ点の探索範囲を変更でき、位置決めの精度を調整できる利点も得られる。
【００１３】
さらに第３の登録画像におけるパターンモデルの位置決め方法は、前記精密位置決めを行う工程が、パターンモデルの位置及び姿勢を求めるために、サーチ対象画像及びパターンモデルに含まれる各エッジ点のエッジ角度を各々比較して一致度を計算することができる。これにより、エッジ角度情報を用いた高精度な位置決めが可能となる。
【００１４】
さらにまた第４の登録画像におけるパターンモデルの位置決め方法は、前記精密位置決めを行う工程が、前記評価値の累積値を、各円弧セグメントとその対応エッジ点との距離を用いて、最小二乗法で用いるエラー値又はウェイト値を演算するものとできる。これにより、各基点の対応エッジ点について、最小二乗法計算で得られる連立方程式を解くことで、パターンモデルの位置及び姿勢を求めることができる。特に、粗サーチである程度モデルとサーチ対象画像のエッジ点が重なっている状態、いいかえると平行移動が不要で回転のみにより精密位置決めが行える状態においては、サーチ対象画像のエッジ点につき最小二乗法でエラーが小さくなるように回転させることが期待でき、高精度な位置決め結果が得られる。特に、円弧に近い部分は円弧セグメントでパターンモデル化するため、パターンモデル又はサーチ対象画像のエッジ点を相対的に回転させても、サーチ対象画像のエッジ点と円弧セグメントとの距離が大きく、変化しない。このため、回転が最小二乗法の解として存在し得、結果として正確な回転による位置決めが期待できる高精度なパターンマッチングが実現できる。
【００１５】
さらにまた第５の登録画像におけるパターンモデルの位置決め方法は、前記登録画像のパターンモデルを構築する工程におけるパターンモデルが、一以上のチェーンを各々円弧又は線分で近似した円弧セグメント及び線分セグメントで構成され、前記精密位置決めを行う工程における前記最小二乗法が、円弧セグメントに対しては、対応エッジ点と円弧の距離を計算するエラー関数を適用し、線分セグメントに対しては、対応エッジ点と直線の距離を計算するエラー関数を適用することができる。これにより、円弧セグメントの回転移動を妨げることなく、効果的な最小二乗法による精密位置決めが実現できる。
【００１６】
さらにまた第６の登録画像におけるパターンモデルの位置決め方法は、前記パターンモデルは、該パターンモデルを構成する各セグメントの種別として、少なくとも円弧又は線分であるを示すセグメント種別パラメータの情報を有することができる。これにより、パターンモデルを構成する各セグメントについて、円弧か線分かを区別できるので、精密位置決め等の各処理において適切なセグメントの選択やセグメントに応じた処理の選択が可能となる。
【００１７】
さらにまた第７の登録画像におけるパターンモデルの位置決め方法は、前記精密位置決めを行う工程における最小二乗法が、円弧セグメントのパターンモデルの中心とサーチ対象画像の対応エッジ点との距離と、円弧セグメントの半径との差の絶対値をエラー値とするエラー関数を適用できる。これにより、回転が解として十分生じるため、高精度な位置決めが期待できる。
【００１８】
さらにまた第８の登録画像におけるパターンモデルの位置決め方法は、前記精密位置決めを行う工程における最小二乗法で用いる円弧セグメントのエラー関数を、円弧セグメントを中心とする理想半径と、円弧の中心と対応エッジ点の距離の差とすることができる。これにより、回転が解として十分生じるため、高精度な位置決めが期待できる。
【００１９】
さらにまた第９の登録画像におけるパターンモデルの位置決め方法は、前記精密位置決めを行う工程における最小二乗法で用いる円弧セグメントのエラー関数を、次式で表現できる。
【００２０】
【数３】
2010067248.tif 000003
【００２１】
さらにまた第１０の登録画像におけるパターンモデルの位置決め方法は、前記精密位置決めを行う工程における最小二乗法で用いる円弧セグメントのエラー関数を、次式で表現できる。
【００２２】
【数４】
2010067248.tif 000004
【００２３】
さらにまた第１１の登録画像におけるパターンモデルの位置決め方法は、前記精密位置決めを行う工程における最小二乗法の重みを、エラー値の関数とできる。
【００２４】
さらにまた第１２の登録画像におけるパターンモデルの位置決め方法は、前記精密位置決めを行う工程における最小二乗法の重みを、セグメントの法線の向きと対応エッジ点のエッジ角度の向きの差の関数とできる。
【００２５】
さらにまた第１３の登録画像におけるパターンモデルの位置決め方法は、前記エッジ角度画像を演算する工程が、前記エッジ角度情報を含むエッジ角度画像に加え、画像を構成する各画素におけるエッジ強度情報を含むエッジ強度画像を演算することができる。これにより、エッジ角度情報のみならずエッジ強度情報に基づいたエッジ画像データを用いた高精度なパターンモデルの位置決めが実現できる。
【００２６】
さらにまた第１４の画像処理装置は、予め登録された登録画像に対応するパターンモデルを用いて、サーチ対象画像中から登録画像に類似する対象物をサーチして位置決めを行う際に、当初与えられた初期位置よりも高い精度で位置決めを行う画像処理装置であって、登録画像及びサーチ対象画像を取得する画像入力手段と、前記画像入力手段で取得された登録画像から複数のエッジ点を抽出し、抽出された複数のエッジ点の内、隣接しているエッジ点同士を連結して連続したチェーンを作成するチェーン作成手段と、前記チェーン作成手段で作成された一以上のチェーンに対して、各々少なくとも円弧で近似したセグメントを作成するセグメント作成手段と、前記セグメント作成手段で作成されたセグメントから登録画像のパターンモデルを構築するパターンモデル構成手段と、前記画像入力手段で取得されたサーチ対象画像中に含まれる登録画像に対応する初期位置を取得し、該初期位置に従って、前記パターンモデルをサーチ対象画像上に重ねるように配置して、前記パターンモデルを構成する各円弧セグメントに対応するサーチ対象画像上の個々の対応エッジ点を求め、各円弧セグメントと、その対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように、当初与えられた初期位置よりも高い精度で精密位置決めを行うための精密位置決め手段とを備えることができる。これにより、粗サーチである程度モデルとサーチ対象画像のエッジ点が重なっている状態、いいかえると平行移動が不要で回転のみにより精密位置決めが行える状態においては、サーチ対象画像のエッジ点につき最小二乗法でエラーが小さくなるように回転させることが期待でき、高精度な位置決め結果が得られる。特に、円弧に近い部分は円弧セグメントでパターンモデル化するため、パターンモデル又はサーチ対象画像のエッジ点を相対的に回転させても、サーチ対象画像のエッジ点と円弧セグメントとの距離が大きく、変化しない。このため、回転が最小二乗法の解として存在し得、結果として正確な回転による位置決めが期待できる高精度なパターンマッチングが実現できる。
【００２７】
さらにまた第１５の画像処理プログラムは、予め登録された登録画像に対応するパターンモデルを用いて、サーチ対象画像中から登録画像に類似する対象物をサーチして位置決めを行う際に、当初与えられた初期位置よりも高い精度で位置決めを行う画像処理プログラムであって、登録画像及びサーチ対象画像を取得する画像入力機能と、前記画像入力機能で取得された登録画像から複数のエッジ点を抽出し、抽出された複数のエッジ点の内、隣接しているエッジ点同士を連結して連続したチェーンを作成するチェーン作成機能と、前記チェーン作成機能で作成された一以上のチェーンに対して、各々少なくとも円弧で近似したセグメントを作成するセグメント作成機能と、前記セグメント作成機能で作成されたセグメントの集合を輪郭とし、登録画像から輪郭を抽出する輪郭抽出機能と、前記輪郭抽出機能で抽出された輪郭から登録画像のパターンモデルを構築するパターンモデル構成機能と、前記画像入力機能で取得されたサーチ対象画像中に含まれる登録画像に対応する初期位置を取得し、該初期位置に従って、前記パターンモデルをサーチ対象画像上に重ねるように配置して、前記パターンモデルを構成する各円弧セグメントに対応するサーチ対象画像上の個々の対応エッジ点を求め、各円弧セグメントと、その対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように、当初与えられた初期位置よりも高い精度で精密位置決めを行うための精密位置決め機能とをコンピュータに実現させることができる。これにより、粗サーチである程度モデルとサーチ対象画像のエッジ点が重なっている状態、いいかえると平行移動が不要で回転のみにより精密位置決めが行える状態においては、サーチ対象画像のエッジ点につき最小二乗法でエラーが小さくなるように回転させることが期待でき、高精度な位置決め結果が得られる。特に、円弧に近い部分は円弧セグメントでパターンモデル化するため、パターンモデル又はサーチ対象画像のエッジ点を相対的に回転させても、サーチ対象画像のエッジ点と円弧セグメントとの距離が大きく、変化しない。このため、回転が最小二乗法の解として存在し得、結果として正確な回転による位置決めが期待できる高精度なパターンマッチングが実現できる。
【００２８】
さらにまた第１６の画像処理プログラムは、さらに前記画像入力機能で取得されたサーチ対象画像を所定の縮小率で縮小するための画像縮小機能と、前記画像縮小機能で縮小された縮小サーチ対象画像に対し、画像を構成する各画素に対して、エッジ角度情報を含むエッジ角度画像を演算するエッジ角度画像作成機能と、前記エッジ角度画像作成機能で作成したエッジ角度画像の各画素につき、予め規定された一定幅の角度を示すエッジ角度ビットで表現したエッジ角度ビット画像に変換するエッジ角度ビット画像作成機能と、前記エッジ角度ビット画像を縮小したエッジ角度ビット縮小画像を生成するために、該エッジ角度ビット画像を縮小する縮小率に応じて決定されるＯＲ演算領域に含まれるすべての画素のエッジ角度ビットをＯＲ演算し、各ＯＲ演算領域を表す縮小エッジ角度ビットデータで構成されたエッジ角度ビット縮小画像を生成するエッジ角度ビット画像縮小機能と、前記画像縮小機能により第１の縮小率で縮小された第１縮小サーチ対象画像に関して、前記エッジ角度ビット画像縮小機能で生成される第１エッジ角度ビット縮小画像に対して、該第１の縮小率にて生成された第１の粗サーチ用パターンモデルをテンプレートとしてパターンサーチを行い、前記第１エッジ角度ビット縮小画像の全域から前記第１の粗サーチ用パターンモデルに対応する第１の位置及び姿勢を、第１の精度で求めると共に、前記画像縮小機能により第１の縮小率以下で等倍以上の第２の縮小率に縮小された第２縮小サーチ対象画像に関して、前記エッジ角度ビット画像縮小機能で生成される第２エッジ角度ビット縮小画像に対して、該第２の縮小率にて生成された第２の粗サーチ用パターンモデルをテンプレートとしてパターンサーチを行い、前記第２縮小サーチ対象画像の、前記第１の位置及び姿勢を基準とする所定の領域中から第２の粗サーチ用パターンモデルに対応する第２の位置及び姿勢を、前記第１の精度よりも高精度な第２の精度で求める粗サーチ機能とをコンピュータに実現させ、前記精密位置決め機能は、サーチ対象画像を必要に応じて等倍以上かつ第２の縮小率以下である第３の縮小率に縮小した第３縮小サーチ対象画像の、前記第２の位置及び姿勢を用いて、パターンモデルを第３縮小サーチ対象画像上に重ねるように配置し、前記パターンモデルを構成する輪郭に対応する第３縮小サーチ対象画像上の対応エッジ点を求め、各輪郭とその対応エッジ点との関係を評価値とし、該評価値の累積値が最小又は最大となるように、前記第２の精度よりも高い第３の精度で精密位置決めを行うことができる。これにより、画像データを更に縮小してもエッジ角度情報が保持されるため、サーチ精度を落とすことなく、データサイズを縮小した高速なサーチが可能となる。
【００２９】
さらにまた第１７のコンピュータで読み取り可能な記録媒体は、上記プログラムを格納するものである。記録媒体には、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷやフレキシブルディスク、磁気テープ、ＭＯ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒ、ＤＶＤ＋Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ＋ＲＷ、Ｂｌｕ−ｒａｙ、ＨＤ  ＤＶＤ（ＡＯＤ）等の磁気ディスク、光ディスク、光磁気ディスク、半導体メモリその他のプログラムを格納可能な媒体が含まれる。またプログラムには、上記記録媒体に格納されて配布されるものの他、インターネット等のネットワーク回線を通じてダウンロードによって配布される形態のものも含まれる。さらに記録媒体にはプログラムを記録可能な機器、例えば上記プログラムがソフトウェアやファームウェア等の形態で実行可能な状態に実装された汎用もしくは専用機器を含む。さらにまたプログラムに含まれる各処理や機能は、コンピュータで実行可能なプログラムソフトウエアにより実行してもよいし、各部の処理を所定のゲートアレイ（ＦＰＧＡ、ＡＳＩＣ）等のハードウエア、又はプログラムソフトウエアとハードウェアの一部の要素を実現する部分的ハードウエアモジュールとが混在する形式で実現してもよい。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の実施の形態を図面に基づいて説明する。ただし、以下に示す実施の形態は、本発明の技術思想を具体化するための画像処理におけるパターンモデルの位置決め方法、画像処理装置、画像処理プログラム及びコンピュータで読み取り可能な記録媒体を例示するものであって、本発明は画像処理におけるパターンモデルの位置決め方法、画像処理装置、画像処理プログラム及びコンピュータで読み取り可能な記録媒体を以下のものに特定しない。また、本明細書は特許請求の範囲に示される部材を、実施の形態の部材に特定するものでは決してない。特に実施の形態に記載されている構成部品の寸法、材質、形状、その相対的配置等は特に特定的な記載がない限りは、本発明の範囲をそれのみに限定する趣旨ではなく、単なる説明例にすぎない。なお、各図面が示す部材の大きさや位置関係等は、説明を明確にするため誇張していることがある。さらに以下の説明において、同一の名称、符号については同一もしくは同質の部材を示しており、詳細説明を適宜省略する。さらに、本発明を構成する各要素は、複数の要素を同一の部材で構成して一の部材で複数の要素を兼用する態様としてもよいし、逆に一の部材の機能を複数の部材で分担して実現することもできる。
【００３１】
本発明の実施例において使用される画像処理装置とこれに接続される操作、制御、表示、その他の処理等のためのコンピュータ、プリンタ、外部記憶装置その他の周辺機器との接続は、例えばＩＥＥＥ１３９４、ＲＳ−２３２ｘやＲＳ−４２２、ＵＳＢ等のシリアル接続、パラレル接続、あるいは１０ＢＡＳＥ−Ｔ、１００ＢＡＳＥ−ＴＸ、１０００ＢＡＳＥ−Ｔ等のネットワークを介して電気的、あるいは磁気的、光学的に接続して通信を行う。接続は有線を使った物理的な接続に限られず、ＩＥＥＥ８０２．１ｘ等の無線ＬＡＮやＢｌｕｅｔｏｏｔｈ（登録商標）等の電波、赤外線、光通信等を利用した無線接続等でもよい。さらにデータの交換や設定の保存等を行うための記録媒体には、メモリカードや磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等が利用できる。なお本明細書において画像処理装置とは、エッジ抽出やパターンマッチング等を行う装置本体のみならず、これにコンピュータ、外部記憶装置等の周辺機器を組み合わせた輪郭抽出システムも含む意味で使用する。
【００３２】
また、本明細書において画像処理におけるパターンモデルの位置決め方法、画像処理装置、画像処理プログラム及びコンピュータで読み取り可能な記録媒体は、エッジ抽出や計測領域設定、エッジ点連結を行うシステムそのもの、ならびに各種画像の撮像、取得に関連する入出力、表示、演算、通信その他の処理をハードウェア的に行う装置や方法に限定するものではない。ソフトウェア的に処理を実現する装置や方法も本発明の範囲内に包含する。例えば汎用の回路やコンピュータにソフトウェアやプログラム、プラグイン、オブジェクト、ライブラリ、アプレット、コンパイラ、モジュール、特定のプログラム上で動作するマクロ等を組み込んでエッジ抽出やエッジ点連結そのもの、あるいはこれに関連する処理を可能とした装置やシステムも、本発明の画像処理におけるパターンモデルの位置決め方法、画像処理装置、画像処理プログラム及びコンピュータで読み取り可能な記録媒体のいずれかに該当する。また本明細書においてコンピュータには、汎用あるいは専用の電子計算機の他、ワークステーション、端末、携帯型電子機器、ＰＤＣやＣＤＭＡ、Ｗ−ＣＤＭＡ、ＦＯＭＡ（登録商標）、ＧＳＭ、ＩＭＴ２０００や第４世代等の携帯電話、ＰＨＳ、ＰＤＡ、ページャ、スマートフォンその他の電子デバイスも包含する。さらに本明細書においてプログラムとは、単体で使用されるものに限られず、特定のコンピュータプログラムやソフトウェア、サービス等の一部として機能する態様や、必要時に呼び出されて機能する態様、ＯＳ等の環境においてサービスとして提供される態様、環境に常駐して動作する態様、バックグラウンドで動作する態様やその他の支援プログラムという位置付けで使用することもできる。
（画像処理の大まかな流れ）
【００３３】
図１に、画像処理装置１００のブロック図を示す。この画像処理装置１００は、図２に示すように予めサーチしたい画像を登録しておき、この登録画像からパターンモデルを作成し、実際の運転時においては、入力されるサーチ対象画像中から該パターンモデルに対応する位置を求める。ここで、パターンモデル作成時の動作の概要を、図３のフローチャートに示す。本実施の形態においては、図２（ａ）に示すように、サーチしたい登録画像ＲＩに対して、パターンモデルを作成する領域、すなわちパターンウインドウＰＷをユーザが設定する（図３におけるステップＳ３０１）。このパターンウィンドウＰＷを設定した領域を含む画像を、図２（ｂ）に示すように必要に応じて縮小する（同ステップＳ３０２）。さらに縮小パターンウィンドウＲＰＭから、図２（ｃ）に示すように登録画像ＲＩに対応する、サーチパターンとしてのパターンモデルＰＭを作成する（同ステップＳ３０３）。このように画像処理装置は、サーチ対象画像中からサーチしたい登録画像ＲＩに対応するパターンモデルＰＭを、実際にサーチを行う運転時に先立ち予め作成しておく。
【００３４】
さらにパターンモデルＰＭは、図２（ｄ）に示すように第１エッジ角度ビット画像用の縮小率、第２エッジ角度ビット画像用の縮小率（後述）に縮小されて、運転時に利用される（同ステップＳ３０４）。このような縮小パターンモデルＲＰＭの作成は、登録時に予め行うこともできるし、また運転時にその都度行うこともできる。
【００３５】
一方、運転時の動作の概要を図４のフローチャートに示す。運転時には、ステップＳ４０１でサーチ対象画像ＯＩを入力した後（図２（ｅ））、ステップＳ４０２で必要に応じてこのサーチ対象画像ＯＩを縮小し、縮小サーチ対象画像ＲＯＩとする（図２（ｆ））。次にステップＳ４０３で縮小サーチ対象画像ＲＯＩからエッジ角度ビット画像ＥＢを生成する（図２（ｇ）：詳細は後述）。さらにステップＳ４０４で、エッジ角度ビット画像ＥＢを縮小したエッジ角度ビット縮小画像ＲＥＢを作成する（図２（ｈ））。このようにして得られたエッジ角度ビット縮小画像ＲＥＢに対して、ステップＳ４０５で、登録時に得られたパターンモデルを用いてパターンサーチを実行する。
（画像処理装置１００）
【００３６】
次に画像処理装置１００の構成を説明する。図１のブロック図に示す画像処理装置１００は、画像処理装置本体１００Ａと、画像を入力する画像入力手段１と、画像や各種データを表示する表示手段３と、ユーザが各種操作を行うための操作手段２と、画像処理装置本体１００Ａにて画像処理した結果を外部に出力するための出力インターフェースを構成する出力手段５とを備える。画像入力手段１は、ＣＣＤ等の撮像手段で構成される。画像入力手段１から入力される入力画像は、Ａ／Ｄ変換手段を介して画像処理装置本体１００Ａに取り込まれる。また表示手段３は、入力画像の原画像や、その原画像を例えばエッジ画像処理によって画像処理したエッジ画像を表示する。
（画像処理装置本体１００Ａ）
【００３７】
画像処理装置本体１００Ａは、各種データを記憶する記憶手段４と、画像処理に関する各種演算を行う演算手段６を備える。記憶手段４は、画像入力手段１からＡ／Ｄ変換手段を介して入力された登録画像の他、この登録画像をテンプレート画像として生成されるパターンモデル、サーチ対象画像、並びに登録画像からパターンモデルを生成する際やサーチの際に作成される一時的なデータの保持、記憶に使用するワーク領域等を備えている。
（演算手段６）
【００３８】
演算手段６は、画像に対してエッジ検出を行い、輪郭を抽出する輪郭抽出手段６２と、輪郭情報からチェーンを作成するチェーン作成手段６３と、チェーンからセグメントを作成するセグメント作成手段６８と、その他の各種手段とを含む。その他の手段としては、エッジ角度ビット画像作成手段６９、エッジ角度ビット画像縮小手段７８、画像を所定の倍率に縮小する画像縮小手段７７、パターンモデルを構成するパターンモデル構成手段７０、粗サーチを行う粗サーチ手段７１、エッジ情報に基づき登録画像のパターンモデルでサーチ対象画像内での精度の高い位置決めを行う精密位置決め手段７６等が挙げられる（詳細は後述する）。この演算手段６は、上述の通りパターンモデルの登録と、登録されたパターンモデルを用いたサーチ対象画像でのサーチを行う。このような動作を行うため、チェーン作成手段６３、セグメント作成手段６８、及びパターンモデル構成手段７０は、パターンモデルの登録時に利用される。また粗サーチ手段７１と精密位置決め手段７６は、実際の運転時に利用される。さらに画像縮小手段７７、輪郭抽出手段６２、チェーン作成手段６３等は、登録時の動作及び運転時の動作共に使用され、エッジ角度ビット画像作成手段６９及びエッジ角度ビット画像縮小手段７８は、運転時に使用される。なおチェーン作成手段６３は、本実施の形態では登録時のみに使用されるが、運転時にサーチ対象画像に対してチェーン化を行うこともできる。
（輪郭抽出手段６２）
【００３９】
輪郭抽出手段６２は、エッジ画像としてエッジ角度画像及びエッジ強度画像を作成するエッジ角度・エッジ強度画像作成手段６０と、エッジ点の細線化を行う細線化手段６１を備える。詳細には、エッジ角度・エッジ強度画像作成手段６０は、画像入力手段１にて入力された多値画像（オリジナルサイズの原画像もしくは後述する画像縮小手段７７で縮小された縮小画像）に対して、エッジ点を抽出するために知られているフィルタ、例えばＸ方向とＹ方向の各々に対してソーベルフィルタ（Ｓｏｂｅｌ  ｆｉｌｔｅｒ）を用いて、ＸＹ各方向におけるエッジ強度画像（Ｘ方向エッジ強度画像成分ならびにＹ方向エッジ強度画像成分）を生成すると共に、これらのＸＹ各方向のエッジ強度画像から２次元的なエッジ角度画像を生成する。また細線化手段６１は、このエッジ角度・エッジ強度画像作成手段６０にて作成されたエッジ画像に対して、例えばエッジ強度の非極大点抑制処理によってエッジ点の細線化を行う。
【００４０】
なお本明細書においてエッジ強度とは、一の画素がエッジ（暗→明）の一部であるかどうかの度合いを表す数値である。一般にエッジ強度は、注目画素とその周囲に位置する９画素の画素値から算出される。またエッジ角度とは、一の画素におけるエッジの方向を示しており、一般には上述したＸ方向とＹ方向のソーベルフィルタ等により求められたＸ方向とＹ方向のエッジ強度から計算される。
（チェーン作成手段６３）
【００４１】
一方、チェーン作成手段６３、セグメント作成手段６８は、登録画像の一部をテンプレート画像とするパターンモデルを生成する際に用いられるものである。本実施例におけるチェーン作成手段６３は、エッジチェーン化手段６４と、チェーンフィルタ手段６６とを備える。詳細には、エッジチェーン化手段６４は、輪郭抽出手段６２によって生成されたエッジ画像に含まれる複数のエッジ点の内、隣接する複数のエッジ点同士を連結してチェーンを作成する。またチェーンフィルタ手段６６は、エッジチェーン化手段６４で生成された複数のチェーン群に対して、チェーンの各種特徴量でフィルタリングを行う。
（セグメント作成手段６８）
【００４２】
またセグメント作成手段６８は、エッジチェーンセグメント化手段６５と、セグメント選択手段６７とを備える。エッジチェーンセグメント化手段６５は、エッジチェーン化手段６４で作成され、かつチェーンフィルタ手段６６でフィルタリングされた各チェーンに対して、近似を行ってセグメントを作成する。セグメントは、ここではチェーンを最小二乗法で近似した線分及び／又は円弧である。またセグメント選択手段６７は、セグメントに対してフィルタリングを行う。
【００４３】
さらにセグメント選択手段６７は、パターン特徴選択機能を備えることもできる。すなわち、サーチ対象物から得られるパターンの特徴に応じて、パターンモデルを構成するセグメントの選択基準を変更させることで、より安定した位置決めが実現できる。詳細については後述する。
（パターンモデル構成手段７０）
【００４４】
パターンモデル構成手段７０は、上述した記憶手段に記憶させるパターンモデルを生成する手段である。具体的には、登録画像に対して、上述した輪郭抽出手段６２及びチェーン作成手段６３、セグメント作成手段６８により処理を施して、生成された各セグメントをパターンモデル構成手段７０で加工する。パターンモデルの詳細については、後述する。
（画像縮小手段７７）
【００４５】
一方で画像縮小手段７７は、登録画像及びサーチ対象画像を縮小する手段である。この縮小率は、自動縮小率決定モードによって自動的に設定される。具体的には、上述の通り本実施の形態においては、ユーザが登録画像に対して、パターンモデルとしたい領域を設定している。ここでの縮小率は、ユーザが設定した領域、すなわちパターンモデルを指定するパターンウインドウＰＷの大きさによって自動的に決定される。例えばパターンウィンドウＰＷが矩形状の場合、短い辺の長さに応じて縮小率を決定する。
【００４６】
なお本明細書において「縮小率を上げる」又は「縮小率が大きい」、「縮小率が高い」とは、縮小度合い又は圧縮率を大きくすることであって、例えば縮小率１／８の縮小画像を縮小率１／１６に、より縮小することを指す。逆に「縮小率を下げる」又は「縮小率が小さい」、「縮小率が低い」とは、縮小の程度を抑え、例えば縮小された画像を等倍画像側に近付ける意味であって、例えば縮小率１／１６の画像を１／８にすることを指す。また「等倍以上の縮小率」とは、等倍画像を拡大する意味でなく、等倍画像すなわち縮小率１よりも縮小率が高いか、縮小率１の等倍画像という意味である。
【００４７】
またこのような自動縮小率決定モード以外に、ユーザが所望の縮小率を選択して決定する手動縮小率決定モードとすることもできる。図５に示すユーザインターフェースの例では、大域サーチ用縮小率として異なる複数の縮小率、ここでは１／２、１／４、１／８の選択肢の中から、ユーザに選択させる。縮小率は、任意の数値で指定させても良い。また、ここで選択した縮小率で画像を縮小すると元画像がどのように変形するかを示すイメージを併せて表示させてもよい。このようにして、大域サーチ用縮小率（大域用縮小率）の他、局所サーチ用縮小率（中間縮小率）、精密位置決め縮小率も設定できる。
【００４８】
さらに、局所サーチ用縮小率を自動で追加することもできる。具体的には、大域サーチ用縮小率と局所サーチ用縮小率の比率が所定値よりも大きい場合、これら大域サーチ用縮小率と局所サーチ用縮小率との間で追加の縮小率（局所サーチ用縮小率）に設定された局所サーチ（追加局所サーチ）を自動的に追加する（図１０参照）。また、追加の局所サーチは、複数回行うこともできる。このようにして、大域サーチ用縮小率と局所サーチ用縮小率との比率を所定値以内に維持でき、サーチ速度の短縮化を図る。
【００４９】
画像縮小手段７７は、パターンモデルを生成する登録画像、及び該登録画像で設定された縮小率と同一の縮小率にて縮小されるサーチ対象画像に対して活用される。いいかえると、登録画像で設定した縮小率で、サーチ対象画像も縮小されることになる。
（エッジ角度ビット画像作成手段６９）
【００５０】
エッジ角度ビット画像作成手段６９は、サーチ対象画像、及び該サーチ対象画像を上述した画像縮小手段７７で縮小した縮小画像に対し、上述した演算手段６のエッジ角度・エッジ強度画像作成手段６０によって生成したエッジ角度画像を用いて、エッジ角度ビット画像を生成するものである。すなわちエッジ角度ビット画像作成手段６９は、運転時にサーチ対象画像のエッジ角度ビット画像を生成するために使用される。いいかえると、パターンモデルの登録時には利用されない。
【００５１】
より具体的には、図６に示すように、エッジ角度である０〜３６０°の値を４５°単位で８分割した８ビットデータとし（図６（ｂ））、エッジ角度画像の各画素に対応して求められているエッジ角度が、これら８分割された分割領域の各々に割り当てられたビット位置であるかを判断し（図６（ａ））、判断したビット位置に１のフラグを立てることにより、エッジ角度画像をエッジ角度ビット画像に変換する（図６（ｃ））。本実施の形態では、演算手段６のエッジ角度・エッジ強度画像作成手段６０によって生成したエッジ角度画像を用いて、エッジ角度ビット画像作成手段６９にてエッジ角度ビット画像を生成している（詳細は、図３０等に基づいて後述する）。ただ、この方法に限られず、例えば演算手段６の細線化手段６１にて細線化されたエッジ角度画像を用いて、エッジ角度ビット画像作成手段６９にてエッジ角度ビット画像を生成しても良い。
（エッジ角度ビット画像縮小手段７８）
【００５２】
エッジ角度ビット画像縮小手段７８は、上述したエッジ角度ビット画像作成手段６９にて生成されたエッジ角度ビット画像を縮小する手段である。これによりエッジ角度ビット縮小画像が得られる。
【００５３】
本実施の形態におけるエッジ角度ビット縮小画像の縮小率は、登録画像に対して、ユーザがパターンモデルとしたい領域を設定するパターンウインドウＰＷの大きさに従って決定する。したがって、このエッジ角度ビット画像縮小手段７８における縮小率を自動的に決定する場合、この登録画像に対して設定されているパターンウインドウＰＷの大きさを反映させている。ただ、この方法に限定されるものでなく、該パターンモデルの縮小率を確認することによって、エッジ角度ビット画像縮小手段７８における縮小率を直接的に設定してもよいことは言うまでもない。
【００５４】
この様子を従来の方法との対比で説明すると、従来の方法でエッジ角度ビット画像を縮小する場合は、例えば縮小率がサーチ対象画像のオリジナル画像サイズに対して１／８である場合、８×８画素の領域、つまり６４画素を代表する一つの画素のエッジ角度、又は６４画素の平均値が縮小された一つの画素のエッジ角度を、その領域の代表値としていた。これに対し、本実施の形態に係るエッジ角度ビット画像縮小手段７８によるエッジ角度ビット画像の縮小では、例えば縮小率がサーチ対象画像のオリジナルに対して１／８である場合、８×８画素の領域の６４画素の各画素が有するビット位置、つまり角度ビットの位置をＯＲ演算によりそのまま保存する形式で、図７に示すように６４画素が保有する全ての角度に対応するビット位置に１のフラグを立てた状態を維持する。これによって、エッジ角度ビット画像の情報は、画像縮小後でも損なわれないように保持でき、パターンモデルを用いたサーチにおいて正確さを得られる。
【００５５】
ここで、ＯＲ演算を行うＯＲ演算領域は、エッジ角度ビット画像を縮小する縮小率に応じて決定される。例えば、エッジ角度ビット画像を１／８に縮小したエッジ角度ビット縮小画像を生成する場合、８×８の領域がＯＲ演算領域となる。すなわち、エッジ角度ビット画像は８×８のＯＲ演算領域に区分され、各ＯＲ演算領域においては、ＯＲ演算領域に含まれるすべての画素のエッジ角度ビットをＯＲ演算した結果を、各ＯＲ演算領域を表す縮小エッジ角度ビットデータとする。このようにして得られた各ＯＲ演算領域毎の縮小エッジ角度ビットデータの集合が、エッジ角度ビット縮小画像となる。
【００５６】
またＯＲ演算とは、和演算、特にビット和を意味する。さらに画素のＯＲ演算を行う際には、単なるビット和とする他、エッジ角度ビットを有する画素の数に下限値を設けても良い。例えば、加算対象のエッジ角度ビットを有する画素数が予め設定された所定の画素数閾値に満たない場合は、このエッジ角度ビットを無視する。すなわち、加算される画素数が１個乃至数個である等、他よりも極端に少ないエッジ角度ビットについては、ノイズやエラーである可能性があるため、このような信憑性の低い画素については無視して、信頼性が高いと思われる角度ビットのみに基づいた信頼性の高いエッジ角度ビット縮小画像を生成できる。
（その他のＯＲ演算  飽和加算）
【００５７】
さらにＯＲ演算として、上記和演算以外の演算を利用することができる。ここでは一例として飽和加算を説明する。例えばＯＲ演算で縮小処理や膨張処理をする場合、ｎｘｎのエッジ角度ビット画像のピクセルデータをＯＲ演算する。この演算の拡張となるのが「各角度に対応するビットに対して飽和加算を行い、その結果から次の代表値を決定する」ことである。ここで飽和加算とは、加算結果に上限を設けておき、通常の加算を行った後にその上限を超える場合、その上限の値にクリッピングする加算処理をいう。例えば上限を１００とすると、
１０＋８９＝９９
１１＋８９＝１００
１２＋８９＝１００
１０＋１００＝１００
といった具合に、上限値を１００に制限する。
【００５８】
次に、飽和加算を用いた縮小処理の具体例を図５２に基づいて説明する。ここで図５２（ａ）は各ピクセルがエッジ角度を有するエッジ角度画像、図５２（ｂ）はこのエッジ角度画像を構成する各ピクセルを８ビットのエッジ角度ビットデータで表現するためのエッジ角度区分を示す模式図を、それぞれ示している。なおエッジ角度方向をエッジ角度ビットで表現するために角度を区分けしたエッジ角度区分については、図３１で後述する。図５２（ｂ）の例では、水平又は垂直方向から２２．５°ずらして８等分し、真右から時計回りに４５°幅でＥ、ＳＥ、Ｓ、ＳＷ、Ｗ、ＮＷ、Ｎ、ＮＥのエッジ角度区分にラベル分けし、各エッジ角度区分に対してエッジ角度ビットのラベルをそれぞれ０、１、２、３、４、５、６、７と付与している。図５２（ａ）のエッジ角度画像を構成する９個のピクセルａ〜ｉを、図５２（ｂ）のエッジ角度区分に従いエッジ角度ビットで表現して得られるエッジ角度ビット画像は、以下のようなエッジ角度ビットデータを有する。
【００５９】
７６５４３２１０
ａ：００００１０００
ｂ：１０００００００
ｃ：１０００００００
ｄ：００００１０００
ｅ：１０００００００
ｆ：１０００００００
ｇ：００００１０００
ｈ：０００００１００
ｉ：１００００１０１
【００６０】
そして、新しい縮小画像でのエッジ角度ビット画像は、それぞれの角度に対応するａ〜ｉのビットをすべて飽和加算する。ここでは飽和加算の上限を３とする。例えば、ｅの位置の縮小エッジ角度ビットデータｅ’は
ｅ’＝ａ＋ｂ＋ｃ＋ｄ＋ｅ＋ｆ＋ｇ＋ｈ＋ｉ
で計算することができ、その結果は下のようになる。
【００６１】
７７６６５５４４３３２２１１００
ｅ’：１１００００００１１１００００１；２進表示
ｅ’：  ３  ０  ０  ０  ３  ２  ０  １；１０進表示
【００６２】
上記演算結果に、飽和加算処理の特徴が表れる。すなわち３以上はすべて３にクリッピングされる。このように和の結果が所定のクリッピング閾値以上になると、その値でクリッピングする加算を飽和加算と呼ぶ。この縮小エッジ角度ビットデータｅ’をサーチの処理でそのまま使うこともできる。例えば２以上のもののみを１にして、その他を０にした縮小エッジ角度ビットデータｅ”を以下のように表現してサーチに用いることもできる。
【００６３】
７６５４３２１０
ｅ”：１０００１１００；２進表示
（粗サーチ手段用のパターンモデルＸ）
【００６４】
パターンモデル構成手段７０はパターンモデルとして、後述する粗サーチ手段７１で用いられる粗サーチ用のパターンモデルＸと、精密位置決め手段７６にて用いられる精密位置決め用のパターンモデルＹの二種類を作成する（図８）。粗サーチ用パターンモデルＸとしては、各セグメント上に、予め定めた条件に基づいて基点を決定し、さらに各基点でのセグメントの法線方向で、且つエッジの向きを設定した角度が設定される。
（精密位置決め用のパターンモデルＹ）
【００６５】
一方、精密位置決め用パターンモデルＹとしては、上述した粗サーチ用パターンモデルＸの持つ情報に加え、各基点は、データとして、対応する各セグメントを表現するセグメント種別パラメータ（例えば、線分や円弧からなるセグメントを定義できるパラメータ）と、上述した各基点から、各基点でのセグメントの法線方向で、且つエッジの方向に延長されたセグメント法線の一種であって、さらに予め定めた長さを有する線分（以下「対応点探索ライン」という。）を設定したものが生成される。対応点探索ラインは、基点を中心として法線方向に前後に延長される。なお基点は、各セグメント上に少なくとも１以上設定されることが好ましい。言い換えると、基点を設定しないセグメントは、パターンモデルに含める必要がない。
（粗サーチ手段７１）
【００６６】
運転時のサーチは、登録時に作成された専用のパターンモデルを用いて、粗サーチ手段７１と精密位置決め手段７６により行われる。粗サーチ手段７１は、運転時において粗サーチを行う手段である。粗サーチは一回のみ行う他、異なる縮小率で複数回行うことができる。複数回の粗サーチを行う場合は、２回目の粗サーチは第１回目の粗サーチよりも縮小率を低く抑えて、すなわち解像度を高める等、オリジナルサイズに近付けたより詳細なデータに基づいて行うことが好ましい。また２回目の粗サーチでは、１回目の粗サーチ結果に基づいて、走査範囲を絞って行うことが好ましい。ここで運転時のサーチの概要を図９のフローチャート及び図１０の模式図に示す。本実施の形態では、図９のステップＳ９０１に示すように、サーチ対象画像の全域を、大域用縮小率で縮小された第２のパターンモデルを用いてサーチする第１の粗サーチ（大域サーチ）を行う。その上でステップＳ９０２に示すように、該第１の粗サーチで得られた「検出候補」の領域及びその周辺領域に対して、第１の粗サーチよりも低い中間縮小率のサーチ対象画像にてサーチを行う第２の粗サーチ（局所サーチ）を行っている。さらにステップＳ９０３にて、精密位置決め用のパターンモデルＹを用いて、精密位置決め手段７６で精密位置決めを行う。
【００６７】
なお、登録時にパターンモデルを作成する順序と、運転時にサーチを実行する順序とを、必ずしも一致させる必要はない点に留意されたい。例えば、登録時には縮小率の低い（オリジナルサイズに近い）パターンモデルから順に作成する（第１のパターンモデル→第２のパターンモデル、等）。これにより、画像の縮小につれて細かな情報が失われる事態を極減できる。これに対し、運転時には逆に縮小率の高い（解像度が低い、圧縮率が高い等）パターンモデルから順にサーチを行う（第１の粗サーチ→第２の粗サーチ）。これによってコース・トゥ・ファインのアプローチで効率よくサーチを行える。この結果、運転時には第２のパターンモデルを用いて第１の粗サーチを行い、次に第１のパターンモデルを用いて第２の粗サーチを行っている。
（第１の粗サーチ）
【００６８】
次に、粗サーチ手段７１が行う粗サーチの概要を説明する。まず第１の粗サーチでは、登録されたパターンモデルを用いてサーチ対象画像の全域に対して大まかなサーチを行い、大まかな位置、すなわち検出候補を抽出する。ここでは、上述したエッジ角度ビット画像縮小手段７８にて生成されたサーチ対象画像のエッジ角度ビット縮小画像に対して、同一の縮小率の登録画像から生成されたパターンモデルをスキャンさせる。具体的には、例えばオリジナルサイズから１／８倍に縮小されたエッジ角度ビット縮小画像の全領域に対してスキャンを行うために、エッジ角度ビット縮小画像の左上から、特定の回転角度を持つ姿勢に設定されたパターンモデルを右下方向に向かってスキャンさせる。これにより、エッジ角度ビット縮小画像の全領域に対して、パターンモデルに類似する検出候補の領域を特定する。このスキャンは、パターンモデルに対して個別に設定される、複数の異なる回転姿勢の全てを用いて同様のスキャンが実行される。すなわち、回転角度を変化させたスキャンを複数回繰り返す。この結果、パターンモデルに類似する検出候補の領域の全てが、パターンモデルに対するマッチング候補として抽出される。ここで、パターンモデルを回転させた結果エッジ角度ビットが変化する様子を図１１に示す。この例では、大域サーチ用パターンモデル（ａ）を時計回りに６０°回転させた場合（ｃ）の、エッジ角度ビットの変化（ｂ）→（ｄ）を示している。また検出候補は、類似度を表す評価値（スコア値）を各々演算して、ある閾値よりも高いスコア値を持つものを検出候補として抽出している。また各検出候補は、その位置と姿勢、すなわちパターンモデルのＸＹ座標と、角度θとスコアの情報を有する。なお、スコアの詳細については、後述する。
（第２の粗サーチ）
【００６９】
次に粗サーチ手段７１は、第１の粗サーチの結果に基づいて第２の粗サーチを行う。第２の粗サーチは、上述した第１の粗サーチで用いたサーチ対象画像の縮小率よりも縮小率の小さい、言い換えると情報量の多い縮小率を用いる。例えば１／４倍の縮小率のエッジ角度ビット縮小画像を用いて、第１の粗サーチで用いた１／８倍の縮小率のエッジ角度ビット縮小画像にて抽出された、全てのパターンモデルに類似する検出候補の周辺領域に対してのみ、同縮小率のパターンモデルを用いて、検出候補の絞込みを行う。この第２の粗サーチは、エッジ角度ビット縮小画像の一部を用いて行うサーチであるため、検出候補の絞込みを効率良く実行することができる。このように粗サーチを複数段行うことで、効率のよいサーチが可能となる。すなわち第１の粗サーチで全域をスキャンし、大まかな位置を特定した上で、縮小率を低くした画像で第２の粗サーチを、該特定された領域（検出候補又は「対象らしさ」）又はその近傍で行う。このような多段の粗サーチによって、サーチ精度の維持とサーチ時間の短縮を両立させることができる。また局所サーチを、縮小率に応じて複数回行うこともできる。
（精密位置決め手段７６）
【００７０】
以上のように粗サーチ手段７１で検出候補あるいはこの近辺でさらに粗サーチを行った「より対象らしき検出候補」を求めた後、精密位置決め手段７６で精密位置決めを行う。精密位置決めでは、縮小していないオリジナルサイズの画像、又は粗サーチで用いた縮小率よりも低い、オリジナルサイズに近い縮小率の画像にてサーチを行う。なお、ここではオリジナルサイズの画像も、縮小率１の縮小画像として扱う。また粗サーチでは、サーチ対象画像がエッジ角度ビット画像であるのに対し、精密位置決めでは原画像又はその縮小画像である。
【００７１】
精密位置決め手段７６は、サーチ対象画像上で得られた、パターンモデルに類似する検出候補の領域に対して、精密位置決め用パターンモデルＹの対応点探索ラインをサーチ対象画像上に重ねるように配置する。具体的には、上述した粗サーチ手段７１を用いて２つの異なる縮小率のエッジ角度ビット縮小画像とパターンモデルとのサーチによって絞り込んだ、パターンモデルに類似する検出候補の領域に対して、サーチ対象画像と同倍率のパターンモデルを用いてサーチを行い、最終的な位置決めを行うサーチ手段である。
【００７２】
以上の粗サーチ手段７１や精密位置決め手段７６にて用いられるパターンモデルは、画像処理に使用するデータとして画像（以下「画像データ」という。）そのものでなく、画像データから得られた各エッジ点に対応する少なくともＸ座標位置、Ｙ座標位置、エッジ角度の値を一次元的にリスト化したデータである。このようなデータから構成されたものが「パターンモデル」であり、画像データでなくリスト化したデータで構成されたパターンモデルを用いることで処理の高速化が図られる。一方で画像データは、いわゆるイメージデータであって、例えば６４０×４８０ビットのデータサイズであれば、全面の各画素について、座標位置毎の値を保有しなければならない。これに対し、パターンモデルを利用する場合は、エッジ画像のエッジ部分に相当する位置と角度のみの値で構成することができる。このためデータ量が相対的に少なく、必要な処理量も低減できる。したがって画像データに変わってパターンモデルを用いることで、より高速な処理が可能となる。
【００７３】
なお本明細書において登録画像とは、サーチしたい画像のオリジナルである。一方、パターンモデルは、登録画像と同様のものをサーチ対象画像中からサーチするためのサーチに適した上述したリスト化されたデータである。本実施の形態ではパターンモデルとして、パターンモデルを構成する各点のＸＹ座標及び角度θの情報を有する。なお、後述するように、精密位置決めにおけるパターンモデルを構成するデータとしては、各点のＸＹ座標及び角度θの情報に加え、後述する対応点探索ラインの情報を有する。
【００７４】
図１に示す各部材は、複数の部材を統合したり、あるいは一の機能を個別の部材に分けて実行することもできる。例えば、画像を縮小する画像縮小手段７７を、輪郭抽出手段６２に統合してもよい。またこれら演算手段６の各機能は、一のＣＰＵやＬＳＩ等で処理することもできるが、例えば前処理を行う専用のＦＰＧＡと、画像処理を行う専用のＤＳＰ等に機能を分散してもよい。この画像処理装置１００では、画像処理はＤＳＰ等で構成された画像処理部で実行し、画像イメージやサーチ結果の表示はＣＰＵで処理する。このように各機能を分散処理することで、処理の高速化が図られる。各機能を実行する部材は、任意に構成できる。
【００７５】
画像入力手段１は、外部機器で撮像、作成された画像処理の対象となる入力画像を取得する。入力画像データは通信やＩ／Ｏにより外部機器から取得される他、記録媒体を介してデータファイルの形で入力することもできる。また画像処理装置自体に入力画像を撮像する機能を持たせてもよい。この場合、画像入力手段１は撮像手段や画像生成手段として機能する。撮像手段としてＣＣＤやＣＭＯＳ等の固体撮像素子を利用したカメラを使用し、画像処理の対象となる電子部品等のワークを撮像すると、ワークに照射された光の反射光と背景に照射された光の反射光の光量が異なるため、ワークに対応する部分と背景に対応する部分とでは固体撮像素子の電荷量に差が生ずる。すなわちワークと背景で画像の輝度差が生じるため、この輝度差をワークの輪郭やエッジとして検出できる。なお、ワークのＣＡＤデータ等として登録画像の輪郭データを入力することも可能である。このようにして画像入力手段１から入力されたデータは、必要に応じてＡ／Ｄ変換して画像処理装置本体部に送られる。
【００７６】
記憶手段４は、各種変換及びテンプレートマッチング等の計算に必要な各種データを記憶したパラメータファイル、登録画像のパターンモデル、サーチ対象画像用エッジ画像等のデータを保持する。このように記憶手段４は、設定内容を保持する他、入力画像のデータを記憶する領域としても利用できる。このような記憶手段４には、ＤＲＡＭやフラッシュメモリ等の半導体素子、あるいはハードディスク等の固定記憶手段が利用できる。
【００７７】
操作手段２は、画像処理装置１００を操作するための入力デバイスである。例えば、ユーザがマウス８１及びキーボード８２を操作して手動で処理領域を指定する場合は、入力デバイスが処理領域指定手段５として機能する。一方、画像処理装置１００側で画像処理に基づき演算手段６で演算することで、自動的に処理領域を指定することもできる。
【００７８】
入力デバイスは画像処理装置１００と有線もしくは無線で接続され、あるいは固定されている。一般的な入力デバイスとしては、例えばマウスやキーボード、スライドパッド、トラックポイント、タブレット、ジョイスティック、コンソール、ジョグダイヤル、デジタイザ、ライトペン、テンキー、タッチパッド、アキュポイント等の各種ポインティングデバイスが挙げられる。またこれらの入力デバイスは、輪郭抽出プログラムをインストールしたコンピュータを画像処理装置１００と接続する態様、あるいは輪郭抽出プログラムをインストールしたコンピュータを画像処理装置や輪郭抽出装置とする態様において、輪郭抽出プログラムの操作の他、画像処理装置自体やその周辺機器の操作にも利用できる。さらに、インターフェース画面を表示するディスプレイ自体にタッチスクリーンやタッチパネルを利用して、画面上をユーザが手で直接触れることにより入力や操作を可能としたり、又は音声入力その他の既存の入力手段を利用、あるいはこれらを併用することもできる。図１の例では、入力デバイスはマウスやキーボード等のポインティングデバイスで構成される。
【００７９】
表示手段３は、外付けの液晶モニタやＣＲＴモニタ等のディスプレイが利用できる。またタッチパネル等入力機能を備えるタイプを使用すれば、表示手段と操作手段を兼用することもできる。表示手段３は、外部接続する形態の他、画像処理装置自体に組み込むこともできる。
【００８０】
以上の構成は例示であって、例えば画像処理装置自体に表示手段、操作手段等を含んでいてもよく、また各部材は、一の部材で兼用したり、演算手段６に統合することもできる。以下、汎用のコンピュータに輪郭抽出プログラムをインストールしてエッジ連結処理や輪郭抽出処理を実行する例について説明する。
（画像処理の詳細な手順）
【００８１】
この画像処理装置は、画像入力手段１で取得された登録画像（基準画像、参照画像等とも呼ばれる）及びサーチ対象画像に対し、前処理（膨張、収縮、平滑化、ソーベル等）を行った後、特徴抽出としてエッジを抽出する。そして、登録画像から得られたパターンモデルを用いて、運転時にはエッジベースのパターンサーチを行う。本実施の形態では上述の通り、事前にパターンモデルを登録しておき（図３）、実際の運転時にはサーチ対象画像について処理を行う（図４）。このように登録時と運転時の処理を分散することで、処理を高速化できる。
【００８２】
登録時の動作をより具体的に説明すると、登録画像を上述した輪郭抽出手段６２にて処理することにより、登録画像の輪郭部分がエッジとして抽出され、幅約１画素の点の集合で表現される登録画像用エッジ画像が生成される。登録画像用エッジ画像は、記憶手段４の登録画像用エッジ画像メモリに一時的に保持される。さらに、登録画像用エッジ画像から、セグメント作成手段６８ならびにパターンモデル構成手段７０によりパターンモデルが生成される。サーチに使用されるパターンモデルは、記憶手段４のパターンモデルメモリに保持されており、必要に応じて呼び出される。
（登録時のパターンモデルの作成）
【００８３】
ここで登録時のパターンモデルの作成手順のフローチャートを図１２に示す。パターンモデルの作成には、上述したようにサーチ対象画像内から抽出したい対象の画像のマスタ画像を登録画像として指定し、一時的に記憶手段４に記憶する。このため登録画像にパターンウィンドウを設定する（ステップＳ１２０１）。この登録画像に対して、縮小率を決定した上で（ステップＳ１２０２）、画像縮小手段７７により画像の縮小化を図る（ステップＳ１２０３）。さらに縮小された画像から輪郭を抽出する。具体的にはエッジ抽出処理とチェーン化処理を行う（ステップＳ１２０４）。さらにチェーンを連結するセグメント化を行う（ステップＳ１２０５）。以上のようにして、縮小画像に対して、輪郭抽出手段６２及びチェーン作成手段６３、セグメント作成手段６８によりエッジデータのセグメント化を図る。そしてパターンモデル構成手段７０によりパターンモデルが生成される（ステップＳ１２０６）。
【００８４】
上述の通り、本実施の形態においてはパターンモデルとして、粗サーチ用のパターンモデルＸと、精密位置決め用のパターンモデルＹの二種類が生成される。また、粗サーチ用のパターンモデルのデータ構造は、任意に設定されている原点に対する各エッジ点のＸ方向とＹ方向の座標位置、及びエッジ角度により構成され、精密位置決め用のパターンモデルのデータ構造は、任意に設定されている原点に対する各エッジ点のＸ方向とＹ方向の座標位置、及びエッジ角度ならびに、後述する対応点探索ラインから構成される。
（エッジ角度）
【００８５】
エッジ角度は、エッジ点におけるエッジの濃度勾配方向を示すものである。ここでは、エッジ角度を示すために、０°から３６０°を２５６段階で表現している。
（エッジ強度）
【００８６】
なお各エッジ点のエッジ強度については、本実施の形態では予め定められた強度値より大きな強度値を有するエッジ点のみで構成しているため、データとしてその値を保有していない。ただ、本発明はこの方法に限定されるものでなく、例えばサーチアルゴリズムにおいて、そのエッジ強度値の類似性に基づいて後述するスコア計算による評価や重み付け等を行う場合は、パターンモデルのデータ構造の値としてエッジ強度のデータを保有させても良い。
（画像の縮小率の決定）
【００８７】
また、登録時に縮小した画像を用いる際には、その縮小率が運転時にも影響を与えるため、縮小率の選定が非常に重要となる。ここでは、サーチに必要な画像の特徴点を保持しつつ、ノイズを削除し、サーチ時間を短縮できる適切な縮小率に設定する。例えば、サーチ精度とサーチ時間とのバランスにおいて、サーチ時間をある程度犠牲し、サーチ精度に重きを置く場合は、縮小率を比較的低くした特定の縮小率とする。あるいは、ユーザが試行錯誤によって決定した最適な縮小率を活用することもできる。本実施の形態においては、自動的に縮小率を決定するオートモードと、ユーザが縮小率を指定するマニュアルモードとを切り替え可能としている。ここでオートモードにおいては、パターンウィンドウＰＭの矩形領域を画定する短い方の辺の長さに基づいて縮小率を決定する。またマニュアルモードでは、縮小率に応じてパターンモデルが実際にどのように変形するかをユーザが目で確認しながら、最適値を選択するようにすれば、設定作業を感覚的として容易にできる。図１３のユーザインターフェースの例では、マニュアルモードを選択すると、ドロップダウンリストで縮小率を選択できると共に、選択した縮小率に応じて画像がどのように変形するかをイメージで示している。縮小率を高くする程、画像の角の部分がなまって変形が激しくなる。このようなイメージの変化を参考にしながら、ユーザは用途や目的に応じて適切な縮小率を選択できる。
【００８８】
あるいは、他の実施例としてサーチ精度とサーチ時間とのバランスを自動的に決定する手法を採用してもよい。例えば、ユーザが重視する項目として、サーチ精度か、サーチ時間か、又は両方かを選択肢として提示し、ユーザに選択させた上で、該選択に応じて適切な設定を自動で行う。
（粗サーチ用パターンモデルＸ）
【００８９】
粗サーチとは、後述する精密位置決めに先立って、サーチ対象画像内から、登録画像と同一の画像が存在する可能性の高い領域を検出候補として、効率よく短時間で絞り込むためのサーチである。このため粗サーチは、オリジナルのサーチ対象画像や登録画像から縮小した画像を活用することによって、上述した目的を達成している。より具体的には、図８７に示すピラミッドサーチのように、オリジナルサイズの画像を縮小した縮小画像を用いて、粗いサーチを行う。この粗サーチにおいては、縮小率の高い、低解像度の画像を用いる。そして粗サーチで得られた粗い位置（検出候補）に対して、精密値決めを行う。この精密位置決めにおいては、粗サーチよりも縮小率の低い、解像度の高い画像を用いる。
【００９０】
ここで粗サーチ用パターンモデルＸを作成する手順を説明する。ステップＳ１２０１でサーチ対象画像内から検出したい対象の画像のマスタ画像を登録画像として、一時的に記憶手段４の登録画像メモリに記憶する。より具体的には、撮像手段から取り込み、表示手段に表示される画像に対して、登録画像として必要な部分の位置とその大きさを、図２に示すように矩形状のパターンウインドウＰＷを用いて、ユーザが画面上にて設定する。
【００９１】
次にこの登録画像に対して、画像縮小手段７７により画像を縮小化する際の縮小率を決定する（ステップＳ１２０２）。本実施の形態においては、後述するパターンモデルの大域用縮小率は、このパターンウインドウＰＷの大きさ、すなわち矩形内に含まれる画素数によって決定される。
【００９２】
つまり、登録画像としての画素数が比較的多い場合は、縮小率を高く設定しても、画像の内の特徴点の喪失が少ないため、ある程度縮小率を高く設定する。一方、登録画像としての画素数が比較的少ない場合は、縮小率が高いと、画像の内の特徴点が喪失される可能性が高くなるため、ある程度縮小率を低く設定する。なお、最適な縮小率の設定は、縮小によって、画像内のノイズが除去され、且つ画像の特徴点を喪失しない程度の縮小率が好ましい。
【００９３】
縮小率を決定する他の手法としては、例えば登録画像を、同じ登録画像に対してＸ方向ならびにＹ方向に所定量ずつシフトさせる。ここで自己相関が緩やかに変化する場合は、ある程度マッチングすれば相関値が変化し難い特徴のある画像と判断できるため、縮小率を高くする。一方で自己相関が急激に変化する場合は、相関値が変化しやすい特徴のある画像と判断できるため、縮小率を低く抑える。このように自己相関に基づいて縮小率を決定することもできる。
【００９４】
以上のようにして決定された縮小率に基づき、オリジナルサイズの登録画像が画像縮小手段７７により縮小される（ステップＳ１２０３）。詳細には、画像縮小手段７７では、パターンウインドウＰＷのサイズによって決定された最終の縮小率ではなく、まず画像のオリジナルサイズと大域用縮小率の間に位置する中間縮小率にて、画像の縮小が実行される。ここでは、画像縮小手段７７により中間縮小率にて縮小された画像に対して、さらに輪郭抽出手段６２及びチェーン作成手段６３、セグメント作成手段６８により、エッジのセグメント化を図る（ステップＳ１２０４、ステップＳ１２０５）。なお中間縮小率は、第２の粗サーチにおける縮小率に対応している。
【００９５】
ここで、先にオリジナルサイズの画像を縮小した後、次いで画像のエッジデータ化ならびにセグメント化を図る理由は、逆にオリジルサイズの画像をエッジデータ化ならびにセグメント化した後で縮小する手順に比べ、オリジナル画像の保有する特徴点を保存しつつ、ノイズを低減できるからである。またこの方法は、パターンモデルに類似する検出候補の領域を抽出する粗サーチの目的にも合致している。このため、中間縮小率は、オリジナルサイズの画像の特徴点を保持しつつ、ノイズをある程度低減できるように、ユーザがそのセグメントを見ながら手動で決定するマニュアル設定とすることもできる。あるいは、パターンウインドウＰＷのサイズに応じて自動的に決定する自動設定とすることもできる。
（第１のパターンモデル作成）
【００９６】
次にステップＳ１２０６で、パターンモデル構成手段７０は、セグメント作成手段６８にてセグメント化されたデータを用いて、上述した中間縮小率での第１のパターンモデルを生成する。この第１のパターンモデルは粗サーチの内、局所サーチ用である（図９のステップＳ９０２）。図８に、各パターンモデルの例を示す。第１のパターンモデルは、図８（ａ）に示すように、エッジ画像データ内に存在する各セグメント上に、予め定めた条件に基づいて、基点を決定し、さらに各基点に対して、セグメントの法線方向で、且つエッジの向きにエッジ角度を設定したエッジモデル点が規定される。
（第２のパターンモデル作成）
【００９７】
さらにパターンモデル構成手段７０は、セグメント作成手段６８にてセグメント化されたデータを用いて、上述した大域用縮小率での第２のパターンモデルを生成する（図８（ｂ））。この粗サーチ用の第２のパターンモデルは、第１のパターンモデルと同様に、エッジ画像データ内に存在する各セグメント上に、予め定めた条件に基づいて、基点を決定し、各基点に対して、セグメントの法線方向で、且つエッジの向きにエッジ角度を設定している。これらパターンモデルは縮小率に応じて個別に作成せずとも、１つのみを作成し、運転時においてはサーチ対象画像の縮小率に応じてパターンモデルを拡大縮小して利用することができる。
【００９８】
第１のパターンモデルと第２のパターンモデルの相違点は、各セグメント上に設定される基点が複数存在する場合、図８（ａ）、（ｂ）に示すように、その基点間の距離が第１のパターンモデルのものに比べ、第２のパターンモデルのものが長くなっている点である。これは、２つのパターンモデルの縮小率が相違することに起因している。基点間の距離が相違する度合いは、中間縮小率と大域用縮小率との違いに支配されている。
【００９９】
ここで、具体的な粗サーチは、図９に示したように、大域用縮小率の第２のパターンモデルを用いてサーチ対象画像の全範囲に対して実施される「大域サーチ」（ステップＳ９０１）と、この「大域サーチ」によって抽出された検出候補の候補領域に対してのみ、中間縮小率の第１のパターンモデルを用いて実施される「局所サーチ」（ステップＳ９０２）で構成される。
【０１００】
本実施の形態の説明においては、粗サーチは、一の大域用縮小率のパターンモデルを用いた１回の「大域サーチ」と、一の中間縮小率のパターンモデルを用いた１回の「局所サーチ」を行っている。具体的には、画像のオリジナルサイズに対して中間縮小率が、
（１）１／√２倍以下の場合、大域用縮小率を中間縮小率の１／２倍、
（２）１／√２倍〜１／４倍の場合、大域用縮小率を中間縮小率の１／３倍、及び
（３）１／４以上の場合、大域用縮小率を中間縮小率の１／４倍に、それぞれ設定している。このように中間縮小率に応じて大域用縮小率を決定することで、サーチの効率と、オリジナル画像からの特徴点の保存を両立させている。
【０１０１】
ここで、局所サーチを複数回行うこともできる。上記（３）のように、画像のオリジナルサイズに対して中間縮小率が著しく高い場合、例えば画像のオリジナルサイズに対して、中間縮小率が１／４倍に設定された場合、大域用縮小率は、画像のオリジナルサイズに対して１／１６倍となる。この場合は、大域用縮小率と中間縮小率との比率が４倍も異なるため、大域用縮小率の第２のパターンモデルを用いて抽出した検出候補の候補領域とその周辺をサーチの最小とする「局所サーチ」に時間がかかりすぎる恐れがある。
【０１０２】
そこで、本実施の形態においては、中間縮小率と大域用縮小率の比率が２倍より大きい場合、隣接する縮小率同士の比率が２倍以下となるように、自動的に更にサーチを１回又はそれ以上追加するように、追加的な中間縮小率が設定される。すなわち、局所サーチを２回以上行うことで、１回の局所サーチに要する時間の短縮化を図っている。このような中間縮小率（局所サーチ用縮小率）の自動追加は、例えば図５に示すユーザインターフェース画面で、「自動で局所サーチ用縮小率を追加する」オプションにチェックを入れて設定できる。
【０１０３】
上述したように、パターンモデルは、任意に設定されている原点に対する各エッジ点のＸ方向とＹ方向の座標位置及びエッジ角度から構成されるデータ構造である。したがって、追加の中間縮小率が設定された場合、その追加の中間縮小率に対応するパターンモデルは、上述した第１のパターンモデルや第２のパターンモデルと同様に、セグメントから生成される。追加の中間縮小率のパターンモデルと、第１のパターンモデルや第２のパターンモデルとの相違は、各セグメント上に設定される基点が複数存在する場合、その基点間の距離が第１のパターンモデルのものに比べ長く、かつ第２のパターンモデルのものに比べて短いことである。なお、パターンモデルを縮小しても、パターンモデル自体が座標位置等のデータで構成されているため、画像データの縮小に比べ、縮小による情報の欠損を極減できる。
（大域サーチ）
【０１０４】
ここで、説明の便宜ためサーチの運転時の動作についても説明する。図９のステップＳ９０１に示すように、大域用縮小率のパターンモデルを用いた「大域サーチ」を実行することにより、検出候補の候補領域を抽出する。そして、抽出された検出候補の候補領域を、大域用縮小率の次に縮小率の高い第２のパターンモデルを用いて、「局所サーチ」を実行する。これにより、サーチ結果に基づいて、より精度の高い検出候補の候補領域を絞り込む。その後、縮小率の高い順に、設定される中間縮小率のパターンモデルを用いて、絞り込まれた検出候補の候補領域に対して、「局所サーチ」を実行し、検出候補の候補領域を絞り込むステップを繰り返す。
（精密位置決め縮小率）
（手動縮小率決定モード）
【０１０５】
また上述したように、ユーザが図５のユーザインターフェースを用いて縮小率を選択する手動縮小率決定モードの場合は、ユーザは、一の中間縮小率と、一の大域用縮小率、及び精密位置決め手段７６を用いる際の精密位置決め縮小率を選択することができる。ただこの場合でも、選択された中間縮小率と大域用縮小率との比率が２倍より大きい場合には、自動的にこれらの縮小率の間に上述した条件に基づいた更なる中間縮小率を自動的に生成されるように設定してもよい。また、精密位置決め手段７６を用いる際の精密位置決め縮小率については、縮小率の候補をユーザに選択させる際、粗サーチ用に設定された縮小率の内で最も低い値か、これよりもさらに低い縮小率の値（画像のオリジナルサイズを含む）しか選択できないように、選択対象の値を制限している。これにより、誤って前段の粗サーチよりも縮小率の高い、粗いデータで精密位置決めを行う事態を回避できる。
（精密位置決め用パターンモデル）
【０１０６】
精密位置決めサーチは、図９のステップＳ９０３に示すように、上述した粗サーチの「局所サーチ」によって絞り込まれた、一つ又は複数の検出候補の候補領域に対して、「局所サーチ」において最後に用いた最終中間縮小率又はこれよりも低い（画像のオリジナルサイズを含む）縮小率のパターンモデルを用いて、精密な位置決めを行うものである。好ましくは、精密位置決めに用いるパターンモデルの縮小率は、等倍画像すなわちオリジナルサイズの原画像とする。
（エッジの鮮鋭度）
【０１０７】
上述の通り、精密位置決めにおいては必ずしもオリジナルサイズのサーチ対象画像を用いるものでなく、前段の局所サーチにおいて最後に用いた最終中間縮小率を超えない範囲の縮小率（精密位置決め縮小率）で縮小した画像を用いることもできる。これによって、特にサーチ対象画像がぼけている場合にも好適なサーチ結果が期待できる。
【０１０８】
例えば、オリジナルサイズのエッジ画像の輝度データの波形が尖鋭である程、鮮鋭度が高く、逆になだらかである程、画像がぼやけているといえる。そこで、エッジの部分の鮮鋭度が予め定められた値より低い場合、すなわちエッジが幅方向において所定の幅以上に分散して、画像がぼやけている場合は、適切な精密位置決め縮小率に設定して画像をこの縮小率に縮小することで、この画像の鮮鋭度を低減してエッジの鮮鋭度を増すことができ、この結果安定した位置決め精度を得ることができる。
【０１０９】
例えば図５３に示すような画素の変化が急峻な二値画像の場合、この画像の輪郭すなわちエッジは、図５４に示すように画素の濃度すなわち画素値が階段状に変化する、いわゆるステップエッジである。このため、エッジの強度変化は図５５に示すように、境界線がシャープに現れる傾向にあり、正確な位置決めが期待できる。一方、二値画像が不鮮明な場合は、境界部分の変化が図５６に示すようになだらかとなり、この結果エッジの強度変化が図５７に示すように起伏の乏しい曲線となって、照度や光量変化といった周囲環境の僅かな変動でエッジ検出精度が左右され、安定したエッジ検出ができず画像認識等の画像処理の信頼性も低下するという問題があった。そこで本実施の形態では、適切な位置決め縮小率に縮小することでエッジの鮮鋭度を向上させる。
（エッジのサブピクセル座標の決定）
【０１１０】
具体的には、エッジ情報を用いた精密位置決めにおいては、登録画像から抽出したエッジの位置情報に基づき生成するパターンモデルと、サーチ対象画像から抽出したエッジの位置情報に基づき高精度な位置決めを行う。このため、エッジの位置情報は極めて重要となる。
【０１１１】
従来、エッジのサブピクセル位置を決定する手法として、特許文献２、３等の技術が知られている。これらの方法では、注目画素のエッジ強度と、その周囲に位置する２つの画素のエッジ強度の、合計３つのデータを用いて二次関数補完を用いてサブピクセル座標を求めている。図５８に、特許文献２に係るサブピクセル座標の計算方法の概要を示す。この図において、ＥＭｃ（Edge Magnitude center）は、エッジの細線化のための非極大点抑制処理（nonmaxsupress）後に残ったエッジ点である注目エッジ点のエッジ強度値である。またＥＭｆ（Edge Magnitude forward）は、注目エッジ点のエッジ角度の向きにある矢印での推定エッジ強度値である。さらにＥＭｂ（Edge Magnitude backward）は、注目エッジ点のエッジ角度の向きにある丸印での推定エッジ強度値である。さらにまたＥＭｆ1、ＥＭｂ1の添え字の１は、十字方向のエッジ点の特徴量に、ＥＭｆ2、ＥＭｂ2の添え字の２は、対角方向のエッジ点の特徴量に、それぞれ与えられる。以下の例では、エッジ角度が水平方向となす角度ＥＡｃ＜４５°について考える。他の角度については、対称性を考慮して求めることができる。ここで、次式が成立する。
【０１１２】
ＥＭｆ＝ＥＭｆ1＊（１−ｔａｎＥＡｃ）＋ＥＭｆ2＊ｔａｎＥＡｃ
ＥＭｂ＝ＥＭｂ1＊（１−ｔａｎＥＡｃ）＋ＥＭｂ2＊ｔａｎＥＡｃ
【０１１３】
上式のＥＭｃとＥＭｆとＥＭｂの３つのエッジ強度データを用いて、ＥＭｃの位置からのサブピクセル位置のオフセット量は、次式で計算できる。
【０１１４】
ｘ＝（ＥＭｆ−ＥＭｂ）／（２（２ＥＭｃ−ＥＭｆ−ＥＭｂ））
ｙ＝ｘ＊ｔａｎθ
【０１１５】
以上のようにして、サブピクセル位置を演算することができる。次に、ピントの合ったエッジ強度の様子と、不鮮明な画像でのエッジ強度の様子を、図５５及び図５７に示す。図５５から明らかなように、ある程度ピントの合ったエッジ強度はピークが尖鋭となり、エッジ位置は明確に決定できる。一方、図５７に示すように不鮮明でぼやけた画像の場合は、極大付近がかなりフラットな状態となり、エッジ強度の誤差によるサブピクセル座標への影響が大きくなる。その影響を評価するために、ＥＭｆ＝ＥＭｂでＥＭｆに誤差が１階調ある場合を検討する。エッジ強度の誤差とサブピクセル位置との関係を、次式に示す。
【０１１６】
【数５】
2010067248.tif 000005
【０１１７】
【数６】
2010067248.tif 000006
【０１１８】
上記関数において、ｘ＝ａ＋１付近の状況を調べると、以下の通りとなる。
【０１１９】
【数７】
2010067248.tif 000007
【０１２０】
【数８】
2010067248.tif 000008
【０１２１】
上式において、Ｘ＝ｃ−ａとすると、
【０１２２】
【数９】
2010067248.tif 000009
となる。これをグラフで表現すると、図５９のようになる。この図に示すように、ＥＭｆ＝ＥＭｂ付近で、X→０、つまりｃ→ａでエッジ強度がフラットになっていくと、エッジ強度の誤差によるエッジ位置の誤差への影響が大きくなることが判る。同様の傾向がＥＭｆ≠ＥＭｂでも見られる。そこで、本実施の形態では、エッジ点の鮮鋭度を演算し、この値を用いてエッジのサブピクセル位置計算を行うための画像データ縮小率を計算する。さらに、画像データ縮小率に縮小した画像データを用いて、エッジ抽出を行う。このように画像データを縮小することで、図５７のようななだらかな波形を図５５のような尖鋭な波形とし、エッジ位置を安定させ、位置決めの精度を向上させることができる。
【０１２３】
エッジ点の鮮鋭度に基づき、画像データ縮小率を決定する手順を、図６０のフローチャートに基づいて説明する。まずステップＳ６００１において、等倍画像からエッジ画像を作成する。次にステップＳ６００２において、エッジ画像のエッジの細線化を図り、一方でステップＳ６００３において、エッジ画像の各エッジ点の鮮鋭度の演算を行う。エッジの細線化処理は、エッジ連結処理に先立ち、非極大点抑制処理のために行われる。さらにステップＳ６００４で、細線化された対象のエッジ点の鮮鋭度の平均値を演算する。そしてステップＳ６００５で、この鮮鋭度の平均値に基づいて、画像データの縮小率を決定する。ここでエッジ点の位置精度が所定以上に維持されるように画像データ縮小率を決定する。
（エッジのモデル関数）
【０１２４】
次に、エッジのモデル関数について検討する。抽出されるエッジの多くは、ステップ状のエッジであると考え、以下に示すエッジのモデル関数で表現できると仮定する。このエッジのモデル関数のσsを、エッジ点の鮮鋭度とする。この場合エッジの理想型は、次式で表現できる。
【０１２５】
【数１０】
2010067248.tif 000010
【０１２６】
【数１１】
2010067248.tif 000011
【０１２７】
上式の関数のグラフを、図６１に示す。この図に示すエッジの理想的な形状（プロファイル）は、次式でプロットされる（ｘ軸に沿ってＩ＝２、ｌ＝０、σs＝０．６の場合）。
【０１２８】
【数１２】
2010067248.tif 000012
（画像データ縮小率を適用したパターンサーチの手順）
【０１２９】
次に、画像データ縮小率を用いた具体的な画像処理におけるパターンサーチの手順を、図６２、図６３のフローチャートに基づいて説明する。これらの図において、図６２は登録時の動作を、図６３は運転時の動作を、それぞれ示している。
（画像データ縮小率を適用した登録時の動作）
【０１３０】
まず登録時の動作を図６２に基づいて説明すると、ステップＳ６２０１において、粗サーチ用のパターンモデルを作成する。次にステップＳ６２０２において、等倍画像でエッジ抽出を行い、抽出されたエッジ点毎に標準偏差σsを求める。標準偏差σsを求めるに際して、実際に画像データから抽出されるエッジの形状は、上記図６１のモデルに近似していると仮定する。ここでは、所定のエッジ強度閾値以上のエッジ点における各エッジのサブピクセル位置を計算するために、図６４に示す近接する３点Ｂ、Ｃ、Ｆのエッジ強度ＥＭｂ、ＥＭｃ、ＥＭｆを用いて、対数エッジ強度の二次微分の近似式である次式を用いる。
【０１３１】
【数１３】
2010067248.tif 000013
上式のｔを用いて、標準偏差σsが次式から計算できる。
【０１３２】
【数１４】
2010067248.tif 000014
なお上式のｔを用いると標準偏差σsを1価関数で表現できるということが重要であり、上式に特別な意味があるわけではない。
【０１３３】
一方で、ステップＳ６２０３において、画像データから抽出されたエッジを、チェーン作成手段６３、セグメント作成手段６８でチェーン化、セグメント化して、仮のパターンモデルを作成する。さらにステップＳ６２０４において、この仮のパターンモデルの作成に際して用いた各エッジのσsのみを用いた平均値σaを演算する。次いでステップＳ６２０５で、この平均値σaを用いて、画像データ縮小率ｒを次式で求める。ここでは、精密位置決め縮小率となる。
【０１３４】
【数１５】
2010067248.tif 000015
【０１３５】
この例では、エッジ強度の対数の差分値を求めて、この差分値から縮小度を計算した。ただ、この例に限られず、エッジ強度の対数の微分値に関する各種近似値を用いて、画像データ縮小率を演算することもできる。またここでいう近似値には、エッジ強度の微分値の近似値も含む。
【０１３６】
このようにして画像データ縮小率ｒが得られると、ステップＳ６２０６で登録画像を改めて精密位置決め縮小率に合わせて縮小し、さらにステップＳ６２０７で、縮小した登録画像から、精密位置決め用のパターンモデルを作成する。
（画像データ縮小率を適用した運転時の動作）
【０１３７】
次に、画像データ縮小率を用いた登録動作を受けて行う運転時の動作を図６３に基づいて説明する。まずステップＳ６３０１において、上記で得られた精密位置決め縮小率を用いて、サーチ対象画像を、精密位置決め用の縮小サーチ対象画像に縮小する。一方でステップＳ６３０２として、サーチ対象画像から、粗サーチ用の縮小画像を作成し、そしてステップＳ６３０３で、粗サーチ用パターンモデルと粗サーチ用縮小画像を用いて、検出候補の位置と姿勢を求める。最後にステップＳ６３０４で、これら精密位置決め用パターンモデルと、精密位置決め用縮小サーチ対象画像と、検出候補の位置及び姿勢を用いて、精密位置決めを実行する。
（画像縮小の前処理・後処理）
【０１３８】
なお、画像データ縮小後でもエッジ位置の情報が可能な限り維持されるように、画像データの縮小を行う。具体的には、画像データ縮小率に応じたローパスフィルタを適用した後に、サブサンプリングを行う。サブサンプリング後の画像データに対して、エッジの抽出を行うことで、精度の良いエッジ位置情報を得ることが可能となる。
【０１３９】
以上のようにして、元画像のぼやけ等不鮮明が原因で生じる精度の低下を抑制できる。さらに、画像データを縮小してデータ量を小さくすることで、以降の処理を高速、軽負荷にできるという副次的な利点も得られる。
【０１４０】
本実施の形態において精密位置決め縮小率は、「局所サーチ」において最後に用いた最終中間縮小率（第１縮小率）を上限とする縮小率に自動的に設定する。また精密位置決めに用いるパターンモデルは、精密位置決め縮小率と同一になるよう縮小された登録画像から生成される。このように精密位置決め縮小率は、オリジナルサイズのエッジ画像のエッジの鮮鋭度に基づいて、画像のオリジナルサイズから局所サーチにおいて最後に用いた最終中間縮小率の範囲で決定される。
【０１４１】
このように精密位置決め縮小率を調整することで、鮮鋭度を一定以上に維持して、鮮鋭度の高い状態で利用することにより位置決め精度の安定性を確保できる。
（パターンモデルの登録時の動作）
【０１４２】
再びパターンモデルの登録動作の説明に戻って、精密位置決め用パターンモデルを登録する手順について、図１４のフローチャートに基づいて説明する。精密位置決め用パターンモデルは、上述した粗サーチ用パターンモデルにて説明した登録画像と同一の画像を用いて作成する。まずステップＳ１４０１において、画像縮小手段７７による処理に先立ち、輪郭抽出手段６２によって、登録画像に対するオリジナルサイズのエッジ画像を生成し、エッジの鮮鋭度を評価する。これに基づいて、ステップＳ１４０２で最適な縮小率を決定する。このようにして登録画像に対して決定された最適な精密位置決め縮小率に基づいて、ステップＳ１４０３で画像縮小手段７７により、画像の縮小化を図る。さらに、画像縮小手段７７により決定された縮小率（縮小率１倍も含む）にて縮小された画像に対して、輪郭抽出手段６２及びチェーン作成手段６３、セグメント作成手段６８により、エッジのセグメント化を図る（ステップＳ１４０４、ステップＳ１４０５）。具体的には、縮小された画像に対して、エッジを抽出するエッジ抽出処理と、エッジ点からチェーンを作成するチェーン化処理を行い、さらにチェーンを連結するセグメント化を行う。次に、パターンモデル構成手段７０は、セグメント作成手段６８にてセグメント化されたデータを用いて、決定された精密位置決め縮小率での精密位置決め用パターンモデルを生成する（ステップＳ１４０６）。
【０１４３】
さらに精密位置決め用パターンモデルは、上述した粗サーチ用パターンモデルと同様に、エッジ画像データ内に存在する各セグメント上に、予め定めた条件に基づいて、基点を決定する（ステップＳ１４０７）。また各基点に対して、角度の設定を行う（ステップＳ１４０８）。ここではセグメントの法線方向で、且つエッジの向きに角度を設定する。さらに各基点について、その基点が設けられているセグメントの種類（線分や円弧等のセグメントの種類）、そのセグメントを表すパラメータ（線分や円弧からなるセグメントを定義できるパラメータ）、セグメントの法線の向きでエッジの角度に近い向きの角度、及びセグメントの法線方向に予め定めた長さを有する線分情報、すなわち対応点探索ラインを設定する（ステップＳ１４０９）。
（対応点探索ラインの線分長さ）
【０１４４】
ここで、各基点に対して与えられる対応点探索ラインの線分長さは、各基点に対して同じ長さのものが設定される。その長さは、局所サーチにおいて最後に用いた最終中間縮小率と、精密位置決めで用いる精密位置決め縮小率との比率によって決定される。言い換えれば、最終中間縮小率と精密位置決め縮小率との比率が大きければ、線分の長さは長く、比率が小さければ、線分の長さは短くなるように設定されている。
【０１４５】
例えば、局所サーチにおいて最後に用いた最終中間縮小率が、画像のオリジナルサイズに対して１／４倍であり、精密位置決めの縮小率が等倍であった場合、最終中間縮小率と、精密位置決め縮小率との比率は４倍であるため、局所サーチでの１ピクセルが、精密位置決めでは４ピクセルに相当することになる。そのため、精密位置決め用パターンモデルでの線分の長さは、基点から、エッジの正と負の向きに各々４ピクセルをカバーする長さに設定される。ただし、この線分の長さは、位置決めの精度とサーチ時間に影響を与えるため、縮小率の比率によって対応するピクセル数を全てカバーすることが必ずしも必要でない。例えば、要求される処理時間に応じて対応点探索ラインの線分長さを短く設定する。あるいは逆に、対応するピクセル数以上の長さを持たせても良い。例えば、縮小率の比率に応じた線分長さに、マージンを設定することで、一層の処理の安定性を図ることができる。
（対応点探索ラインの線分長さの変化）
【０１４６】
また、対応点探索ラインの長さを、基点に対して前後に均等でなく、一方を長く又は短くするように変化させることもできる。この処理はパターンモデル構成手段７０等により行われる。ここで、対応点探索ラインの長さを変化させた例を、図２７及び図２８に基づいて説明する。これらの図において、図２７は基点からの長さが等しい場合、図２８は基点からの長さが異なる場合を、それぞれ示している。なお、これらの図において内側の矩形領域で発生する対応点探索ラインは、フィルタリングされている。図２７に示すように、基点から延長される対応点探索ラインの長さを、基点の前後左右で一定にすると、内側の矩形状と重なり合い、誤判定を生じる虞がある。そこで、内側に向かう方向には対応点探索ラインを延長させず、図２８のように外側に向かう方向のみに対応点探索ラインを設定すれば、より誤判定の少ない、正確なサーチ結果が期待できる。
（対応点探索ラインの設定間隔）
【０１４７】
対応点探索ラインは、セグメント上に端部を除いて設定される。このような端部は、位置をずらした際の影響が大きいためである。したがってこのような位置ずれした場合の影響が大きい部分を排除して対応点探索ラインを設定することで、安定した処理が見込まれる。
【０１４８】
対応点探索ラインを設定する間隔や本数は、要求されるパターンサーチの処理速度や精度に応じて決定される。セグメントを構成する各線分や円弧に少なくとも１つは、対応点探索ラインを配置するよう設定することでパターンサーチの精度を維持できる。最も簡単には、セグメント上の中心に一つの基点を配置してその点からセグメント上に等間隔に基点を設定する。また、セグメントの内、エッジ角度が曖昧な部分については基点の設定を間引き、確実に検出されている部分で密に基点を設定することで、精度を高められる。
【０１４９】
また、対応点探索ラインはセグメントの中央に少なくとも１つは必ず割り当てるようにすることが好ましい。これにより、パターンモデルの一部を構成するセグメントに対しては、短いものであっても一つは対応点探索ラインを設定するよう保証する。
（運転時のサーチ対象画像に対する前処理）
【０１５０】
以上、パターンモデルの登録時の動作、すなわち粗サーチ用、精密位置決め用パターンモデルの作成について説明した（図３、図１２）。運転時においては、これらのパターンモデルを使用したサーチを行う（図４）。サーチにあたっては、撮像手段から入力されたサーチ対象画像に対して所定の前処理が施される。ここで、運転時のサーチにおいて、サーチ対象画像に対する前処理を行う手順を図１５のフローチャートに基づいて説明する。
【０１５１】
まずステップＳ１５０１において、入力されたサーチ対象画像に基づき、画像縮小手段７７は、登録時に登録画像に対して用いた、粗サーチ用の第１のパターンモデルの中間縮小率（第１縮小率）を用いて、縮小画像を生成する。
【０１５２】
一方でステップＳ１５０２において、輪郭抽出手段６２のエッジ角度・エッジ強度画像作成手段６０が、エッジ角度画像及びエッジ強度画像を生成する。また細線化手段６１が、このエッジ角度画像及びエッジ強度画像に基づいて、細線化されたエッジ角度画像を生成する。
【０１５３】
次にステップＳ１５０３において、エッジ角度ビット画像作成手段６９が、輪郭抽出手段６２にて生成され、細線化されたエッジ角度画像に基づいて、粗サーチ用の第１のパターンモデルの中間縮小率に対応したエッジ角度ビット画像を作成する。言うまでもなく、ここで生成されたエッジ角度ビット画像が、サーチ動作において、粗サーチ用の第１のパターンモデルを用いた「局所サーチ」に適用される。
【０１５４】
さらにステップＳ１５０４において、エッジ角度ビット画像縮小手段７８は、エッジ角度ビット画像作成手段６９にて生成されたエッジ角度ビット画像に基づいて、「大域サーチ」用の第２のパターンモデルの大域用縮小率に対応したエッジ角度ビット縮小画像を生成する。
【０１５５】
なお、粗サーチの中間縮小率の設定の説明において述べたように、最初に設定される中間縮小率と大域用縮小率との間の追加の中間縮小率に基づいて、追加のパターンモデルが作成される場合は、任意的なステップＳ１５０５として、この前処理においても、エッジ角度ビット画像縮小手段７８にて、エッジ角度ビット画像作成手段６９にて生成されたエッジ角度ビット画像に基づいて、追加のパターンモデルの中間縮小率に対応したエッジ角度ビット縮小画像が生成される。
【０１５６】
なお、上述した運転時の前処理においては、運転時に行う粗サーチの大域サーチ及び局所サーチ、並びに精密位置決めとは逆の順序で、サーチ対象画像に対する処理を行っているが（図８参照）、パターンモデルの作成順序は特に限定されるものでなく、精密位置決め用のパターンモデルを先に作成した後、粗サーチ用のパターンモデルを作成してもよいことはいうまでもない。一方、運転時においては縮小率の高い画像を用いて粗いサーチを行い、徐々に縮小率を下げてオリジナルサイズに近い画像で細かいサーチを行う。
【０１５７】
以上のようにして運転時の前処理が終了した後、生成されたエッジ角度ビット縮小画像、エッジ角度ビット画像等を用いて、粗サーチの大域サーチ、局所サーチを行い、検出候補の座標を求めた後に精密位置決めを行う（図９）。
（登録時の各動作の詳細）
【０１５８】
以上、登録時と運転時の動作の概要について説明した。次に、登録時における画像処理動作の詳細について説明する。登録時において、エッジ角度・エッジ強度画像作成手段６０は、登録画像に対してソーベルフィルタを適用し、登録画像を構成する各点毎にエッジ強度及びエッジ角度を求め、エッジ強度、エッジ角度、エッジ位置を含むエッジ情報を演算する。これらエッジ情報に基づいて、細線化処理を行ってエッジ点を求める。細線化処理の具体例としては、エッジ強度の非極大点抑制処理が利用できる。ここでは、細線化により幅１ピクセルの線状としている。
【０１５９】
なおエッジ点は、サブピクセル位置の精度で求めることもできる。例えば、２次関数補間（例えば、特開平７−１２８０１７号公報参照）を利用してサブピクセル位置が演算できる。
【０１６０】
さらに得られたエッジ点を連結して、連続したチェーンを作成する。ここでは、エッジチェーン化手段６４が、エッジ角度がほぼ同一方向である隣接したエッジ点同士を連結するエッジ連結処理を行い、一続きの線分要素（チェーン）を作成する。ここで得られるチェーンも、ｘｙサブピクセル座標を有する。各チェーンは、エッジ点の集合であり、個々のチェーンにはチェーン同士を区別するための識別子としてチェーンインデックスが付与される。
【０１６１】
さらにエッジチェーンセグメント化手段６５で、チェーンを近似してセグメントを生成する。セグメントは、最小二乗法を利用してチェーンを線分及び円弧で近似するフィッティングによって求められる。フィッティングは、まず線分での近似を行い、線分による近似の誤差が所定の閾値を超えると、円弧でのフィッティングに切り替える。円弧で近似しても誤差が減少しない場合は、線分でのフィッティング結果を用いる。このようにして、線分と円弧の組み合わせで順次フィッティングする作業を繰り返し、フィッティング結果の誤差が閾値を超えた時点で、その前までに得られたデータが十分長ければ、連続線としてのセグメントとする。エッジ点がサブピクセル位置で求められているため、セグメントもサブピクセルオーダーの高精度な位置で得られる。
【０１６２】
ここでは、チェーンを線分と円弧で近似したセグメントが形成される。線分のセグメントは、直線を表す式（例えばａｘ＋ｂｙ＋ｃ＝０）と端点の座標等で表現できる。一方円弧のセグメントは、中心の座標と半径、開始角度と終了角度等で表現できる。例えば（ｘ−ｘo）2＋（ｙ−ｙo）2＝ｒo2における円弧の中心座標（ｘo、ｙo）及び半径ｒoで円弧セグメントを表現する。このようにして生成した各セグメント上に、所定間隔で基点を設定する。
【０１６３】
なお上記は、セグメントとして線分又は円弧による近似の例を説明したが、これに限らず、円錐曲線、スプライン曲線、ベジエ曲線等も適宜利用できる。これにより、円形状や楕円形状、三角形状、矩形状といった一定の幾何学形状を基準として、これらの単独若しくは組み合わせとしてパターンモデルを作成できるので、パターンサーチ作成やその後の各処理を簡素化できる。
（パターンモデルの縮小）
【０１６４】
また、サーチの運転時にはパターンモデルを縮小する。この縮小率は、後述する運転時においてサーチ対象画像を粗サーチのために縮小する縮小率となる。この縮小処理があるため、パターンモデルのモデルエッジ点としての基点は、その縮小処理の結果として同じ座標を指定することのないように、基点同士の間隔が設定される。この結果、図１６のパターンモデルは、図１７のようになる。
（粗サーチ用パターンモデルと精密位置決め用パターンモデルとの相違点）
【０１６５】
粗サーチ用パターンモデルと精密位置決め用パターンモデルとは、それぞれオリジナルサイズの登録画像（もしくはその縮小画像）から作成される。いいかえると、粗サーチ用パターンモデルのセグメントは、精密位置決め用パターンモデルのセグメントから作成されているものでなく、両者のセグメントは必ずしも一致しない。また粗サーチ用パターンモデルと精密位置決め用パターンモデルとは、パターンモデルの大きさが異なるため、基点間の距離も異なる。その基点間を等倍換算した距離の相違は、縮小率に依存する。
【０１６６】
さらに粗サーチ用パターンモデルでは、基点の座標と、基点におけるエッジの向き（角度情報）が与えられている。いいかえると、対応点探索ラインの長さ情報を有しないセグメントの法線方向でエッジの向きに近い角度が設定される。この粗サーチ用パターンモデルを用いた粗サーチでは、パターンモデルをサーチ対象画像上に置き、基点の位置にエッジがあるかどうか、そのエッジの向きがパターンモデルの向きと一致するかどうかを確認する。
【０１６７】
これに対して精密位置決め用パターンモデルでは、粗サーチ用パターンモデルである上記基点の座標、基点におけるエッジの向きに加えて、基点を通り、セグメントと略直交する方向に伸びる所定長さの対応点探索ライン（すなわちセグメント法線の長さを規定したもの）と、セグメントの種別（例えば線分又は円弧といった属性）とを有している。この違いは、各サーチの処理内容に対応している。すなわち、精密位置決めにおいては、対応点探索ラインの範囲内で対応するエッジを探索する。このように精密位置決め用パターンモデルは、基点に対応する対応エッジ点を選択する対応エッジ点選択手段として機能する。
【０１６８】
なお、輪郭の抽出においては、必ずしもセグメントを作成する必要はない。セグメントでなくチェーンから直接対応点探索ラインを設定することもできる。例えば、ある輪郭に対して基点を３点設定する場合、その輪郭に相当するチェーンを構成するエッジ点３点を等間隔に設定し、各法線方向に対応点探索ラインを設定する。この方法であれば、セグメントを作成しない分高速な処理が見込まれる反面、チェーンを直線や円弧で近似していないため精度が多少低下する。特にチェーンは単にエッジ点を連結しただけであって、直線性に劣ることがある一方、セグメントは直線や円弧で近似しているため、より正確な演算結果が得られ、位置決め精度も安定する。
（運転時の粗サーチの詳細）
【０１６９】
次に、以上のようにして登録されたパターンモデルを用いて、実際にサーチ対象画像中から一致する部位をサーチする運転時の動作を説明する。まず粗サーチで粗い位置及び姿勢を求める手順の詳細を、図１８のフローチャートに基づいて説明する。本実施の形態では、粗サーチを大域サーチと局所サーチに分けて行い、検出候補を求める。
（ステップＳ１８０１  サーチ対象画像の縮小）
【０１７０】
まず、ステップＳ１８０１で、サーチ対象のサーチ対象画像を、登録画像の縮小率に合わせて縮小する。例えば図１９（ａ）に示すサーチ対象画像を、登録画像と同じ倍率に縮小して、図１９（ｂ）に示す縮小サーチ対象画像を得る。ここではまず粗サーチ用として、中間縮小率まで縮小する。いいかえると、縮小率の大きい大域用縮小率への縮小を先に行うことはせず、先に縮小率の小さい中間縮小率まで縮小する。
（ステップＳ１８０２  エッジ角度画像、エッジ強度画像の取得）
【０１７１】
次にステップＳ１８０２で、縮小サーチ対象画像からエッジ強度画像及びエッジ角度画像を、エッジ計算手段でそれぞれ求める。エッジ計算法としてはソーベルフィルタ等が使用できる。
【０１７２】
ここでソーベル法について説明する。ソーベル法は、オペレータ（カーネル）として３×３の行列を用いる。この方法は、対象点を中心とする周囲の点につき、画素値（例えば輝度）に係数を乗じて加算したものを中央点の画素値として抽出する。この方法は水平方向、垂直方向のフィルタであり、また平滑化の操作を含むためノイズに強いという特性を備える。ソーベルフィルタで使用するカーネルを、以下に示す。
【０１７３】
【数１６】
2010067248.tif 000016
【０１７４】
この結果、サーチ対象画像のエッジ強度画像とエッジ角度画像が、それぞれ得られる。
（ステップＳ１８０３  サーチ対象画像のエッジ角度ビット画像の作成）
【０１７５】
さらにステップＳ１８０３で、エッジ角度画像とエッジ強度画像から、エッジ角度ビット画像作成手段６９でエッジ角度ビット画像を作成する。エッジ角度ビット画像とは、エッジ角度画像を構成する各点のエッジ角度を、角度ビット情報として表現した画像データである。この結果、エッジ角度ビット画像が得られる。エッジ角度画像からエッジ角度ビット画像への変換については、後述する。
（ステップＳ１８０４  エッジ角度ビット画像の縮小）
【０１７６】
さらにステップＳ１８０４で、得られたエッジ角度ビット画像をエッジ角度ビット画像縮小手段７８で縮小する。縮小率は、大域サーチ用の第２のパターンモデルを作成する場合は大域用縮小率に、局所サーチ用の第１のパターンモデルを作成する場合は中間縮小率に、それぞれ設定される。この結果、エッジ角度ビット画像の縮小画像が得られる。
（ステップＳ１８０５  大域サーチの実行）
【０１７７】
次に、ステップＳ１８０４で縮小されたエッジ角度ビット縮小画像に対して、予め縮小されたパターンモデルで大域サーチを行う。具体的には、左上から右下に走査するように、パターンモデルの角度を変化させながら全ての範囲でサーチを行う。それによって、検出候補の領域を抽出する。検出候補の位置は、例えばｘｙ座標、姿勢は、例えば角度θ等で表現される。ここで、検出候補はスコア計算によって行われ、粗サーチ手段７１によって、縮小パターンモデルを探索位置及び姿勢の自由度で移動させ、それぞれの位置及び姿勢にてスコアを計算する。
（スコア計算）
【０１７８】
大域サーチにおけるスコア計算は、サーチ対象画像を大域用縮小率に縮小して得られたエッジ角度ビット画像及びパターンモデルに含まれる各エッジ点のエッジ角度ビットを各々比較して、一致度を計算することにより行われる。サーチの際は、基点の位置と角度のデータをスコア計算を行う位置及び姿勢に合わせ変化させる。その後に角度をエッジ角度ビット画像と同様に変換して、縮小後のエッジ角度ビット画像データの画素値に対してＡＮＤ処理を行い、残ったビットの数の合計値を期待される合計値のマックス値で割った値を一致度とし、粗サーチ手段７１で演算する。また、角度方向に複数のビットを割り当て、重みの概念を付加することもできる。
（ステップＳ１８０６  局所サーチの実行）
【０１７９】
さらに、大域サーチで見出した検出候補の領域に対して、局所サーチを行う。局所サーチにおいては、大域サーチ用のパターンモデルよりも縮小率を低くした局所サーチ用のパターンモデルを用いる。また、サーチ対象画像としてのエッジ角度ビット画像も、大域サーチ用縮小率よりも縮小率の低い局所サーチ用縮小率で縮小した縮小画像が用いられる。
【０１８０】
また、局所サーチの際には、大域サーチで見出した検出候補の領域をそのまま利用するのみならず、その近傍の一定領域、例えば３×３画素、５×５画素といった周囲の画素についても、局所サーチを行ってもよい。これによって安定したサーチ結果が期待できる。
（膨張処理）
【０１８１】
すなわち、スコア計算の結果を安定させるために、粗サーチの際に膨張処理を行うこともできる。一般にサーチ対象画像の縮小率が小さくなって精度が上がると、僅かな位置のずれでもスコアが大きく低下する傾向を示す。スコアの急激な変化を回避するためには、回転角度を細かく変化させればよいが、この場合は処理量が増えるというデメリットを生じる。そこで処理量の軽減と精度の向上のバランスを考慮して、サーチ対象画像であるエッジ角度ビット画像を所定量だけ膨張させる。例えば、画素のＸＹ方向に対し、所定の画素数、例えば１画素分を２倍した２×２画素分拡張させる。これにより、僅かな角度のずれによる急激なスコア値の変動が抑制され、安定したスコア値を得ることができる。
【０１８２】
このようにして、計算されたスコアに基づき、縮小パターンモデルの縮小サーチ対象画像における粗位置を決定する。また、必要に応じて上記工程を繰り返して、粗位置の精度を高めることができる。すなわち、単に粗サーチを大域サーチと局所サーチの２回に分けるのみならず、局所サーチを複数回行い、サーチ対象画像の縮小率を徐々に下げて、より大きな縮小サーチ対象画像を用いることで、より高精度な位置決めを行うことができる。
【０１８３】
なお、大域サーチはサーチ範囲が広く処理量が多いため、通常１回のみ行う。ただ、要求される精度やタクトタイムに応じて、大域サーチを複数回行うことも可能である。また、サーチの手法としては、エッジサーチや正規化相関サーチ、一般化ハフ変換、ジオメトリックハッシング等の既知のサーチ技術が利用できる。
（運転時の精密位置決めの詳細）
【０１８４】
以上のようにして粗サーチを行い、パターンモデルが存在する検出候補の位置、姿勢のデータを求めた上で、精密位置決め手段７６により精密位置決めを行う。次に、精密位置決めの詳細手順を、図２０のフローチャートに基づき詳述する。
【０１８５】
まずステップＳ２００１において、粗サーチで得られた検出候補の粗い位置及び姿勢に基づき、精密位置決め用パターンモデルをサーチ対象画像に重ねる。ここでは、粗サーチで最終的に得られた位置及び姿勢を開始位置、開始姿勢として、オリジナルサイズのサーチ対象画像及び精密位置決め用パターンモデルを使用することが好ましい。ただし、オリジナルサイズ（縮小率１）よりも高く、かつ粗サーチで最後に使用した縮小率よりも低い縮小率にて精密位置決めを行うこともできる。
【０１８６】
さらにステップＳ２００２で、精密位置決め用パターンモデルの対応点探索ラインに沿って対応エッジ点となる点を求める。対応点探索ラインは、上述の通りセグメントの法線方向に延びる所定長さの線分であり、線分の両端の一方である起点を探索開始点、終点を探索終了点とする。ここでは、まず対応点探索ラインに沿ってエッジ計算を行い、エッジベクトルを取得する。エッジ計算の手法としては、上述の通りソーベルが適宜用できる。このエッジ計算で得られたエッジベクトルから、対応点探索ライン上の各点のエッジ角度、エッジ強度、エッジ位置等を求める。なおエッジベクトルとは、エッジの強度と向きをベクトル表現したもので（Ｅx，Ｅy）のように表現することができる。例えば図４６に示すようにエッジ強度をＥM、エッジ角度をθEとすると、エッジ角度θE＝Ａｔａｎ（Ｅｙ／Ｅx）、エッジ強度ＥM＝ｓｑｒｔ（Ｅx2＋Ｅy2）で表現できる。
（対応エッジ点探索処理）
【０１８７】
またこれらエッジベクトル、エッジ角度、エッジ強度、エッジ位置等の情報に基づいて、対応点探索ラインの基点を含むセグメントに対応する対応エッジ点を求める。対応エッジ点を決める方法の例としては、上述したエッジベクトルを用いることで高速に行える。また別の方法として、以下説明する通りエッジ強度とエッジ角度を用いて計算することもできるが、この場合は後述の通りＡｔａｎの演算が必要になるため、演算が複雑になる。以下、エッジ強度とエッジ角度を用いて対応エッジ点を求める手順を説明する。
【０１８８】
まずエッジ強度が所定のエッジ強度閾値より大きい極大点で、さらにエッジ角度と基点が持つ角度の差の絶対値が所定のエッジ角度閾値よりも小さい点を対応エッジ点の候補とする。さらにその対応エッジ点候補の中から最も基点に近い点を最終的に対応エッジ点とする。
【０１８９】
さらに、その対応エッジ点のエッジのサブピクセル位置を求めて（ステップＳ２００３）、その位置と、セグメントの幾何データを使ってエラー値を求め、最小二乗法計算を行い（ステップＳ２００４）、精密な位置を求める（ステップＳ２００５）。エラー値の例としては、線分セグメントでは対応エッジ点と直線の距離がエラー値、円弧セグメントでは対応エッジ点と中心位置との距離と半径との差の絶対値がエラー値として挙げられる。
【０１９０】
以上のようにして、最小二乗法計算で用いるエラー値やウェイト値を精密位置決め手段７６で計算し、その値から最小二乗法で得られる連立方程式を取得する。ここではセグメントを理想形状とし、セグメントと対応する複数の対応点との誤差を最小とするように最小二乗法を適用している。さらに連立方程式を解き、高精度の位置及び姿勢を求める。
このようにして、位置Ｘの補正量Δｘ、位置Ｙの補正量Δｙ、角度θの補正量Δθ、スケールｓの補正量Δｓ（ｓ：ｓｃａｌｅ）が得られる。
【０１９１】
精密位置決めにおいては、粗サーチで得られた位置、姿勢のデータを用いて基点をサーチ対象画像に重ねる。そして、対応点探索ラインに沿ってソーベルフィルタ等のエッジ計算を行い、エッジベクトルを取得している。なおエッジベクトルは、ソーベルフィルタを適用した結果で表され、（Ｓx，Ｓy）等で表現できる。またエッジ強度ＥMは、ＥM＝√（Ｓx2＋Ｓy2）、エッジ角度θEは、θE＝Ａｔａｎ（Ｓy／Ｓx）等として表現できる。さらに、エッジベクトルから対応エッジ点上のピクセルのエッジ角度、エッジ強度と位置を求め、これらエッジベクトル、エッジ角度、エッジ強度、位置から対応エッジ点の基点を含むセグメントに対応する対応エッジ点を精密位置決め手段７６で求める。
【０１９２】
この様子を図２１（ａ）に基づき説明すると、まず太字実線で示すパターンモデルＰＭを、粗サーチで求めたサーチ対象画像（破線で示すエッジ角度ビット縮小画像ＥＡＢＲ）の検出候補の位置に、精密位置決め手段７６で重ねて配置する。そしてパターンモデルＰＭ上に設定された基点ＫＴを通り、パターンモデルのセグメントにほぼ垂直な対応点探索ラインＴＬに沿って、基点ＫＴと対応する対応エッジ点ＴＴを求める。図２１（ａ）において対応点探索ラインＴＬは細線実線で示されている。なお、対応点探索ラインＴＬは仮想的に設定されたラインであって、実際にラインを引くわけではない。対応エッジ点ＴＴは、対応点探索ラインＴＬと縮小画像ＥＡＢＲとの交点となる。ここで対応エッジ点ＴＴは、サブピクセル座標位置を求めることができる。この位置と、セグメントの幾何データを使って、精密位置決め手段７６で精密位置決めを行う。
【０１９３】
具体的には、セグメントの幾何データ（この場合は線分）と対応エッジ点との関係を評価値とし、評価値の累積値が最小又は最大となるようにスコア計算を行う。評価値としては、典型的には距離が利用でき、この距離をエラー値として、エラー値が最小となるよう最小二乗法計算を行うことで精密な位置を求めることができる。距離には、セグメントとその対応エッジ点とのユークリッド距離が利用できる。つまりセグメントが線分の場合は対応エッジ点と直線の距離、セグメントが円弧の場合は対応エッジ点と中心位置との距離と半径との差の絶対値を用いる。最小二乗法による解法で得られる連立方程式を解くことで、高精度の位置及び姿勢を求めることができる。また評価値は距離に限られず、基点と基点の対応エッジ点とがなす角度としてもよい。
【０１９４】
また、精密位置決め手段７６が対応エッジ点を求める対応エッジ点探索処理の様子を図２１（ｂ）に示す。この図において、図２１（ａ）と同様、破線はサーチ対象画像の縮小画像ＥＡＢＲ、太字実線はパターンモデルＰＭ、細線実線は基点ＫＴ上に設定された対応点探索ラインＴＬを、それぞれ示している。ここでは、縮小画像ＥＡＢＲの３×３画素の領域ＳＲでソーベルフィルタを適用した座標位置ｘ、ｙを求める。この計算の中心座標は、ブレゼンハムの直線データ生成アルゴリズムを用いて行われる。図２１（ｂ）の例では、モデルエッジ点Ａに対して、ピクセルＢが対応エッジ点として抽出される。
【０１９５】
図２１（ｂ）に示す方法は、対応エッジ点が自動的に抽出されたセグメント上で適当に選択された点を基点として配置される点で上述した特許文献１と相違する。特に特許文献１では、シークラインの配置方法が規定されていない。さらに、対応エッジ点の決定に際して、エッジ強度のみならず、エッジ角度やエッジ位置等のデータを用いることで、対応エッジ点の信頼性が向上する。加えて、エッジ角度やエッジ強度を求める処理で用いるカーネルをよりコンパクトとしており、演算処理を低負荷としている。さらに対応エッジ点に対してはサブピクセル精度で位置を求めることができる。加えて、最小二乗法を用いることにより、様々な形状のモデルにも対応できる利点が得られる。
【０１９６】
以上のようにして、パターンサーチにおける高速且つ高精度な位置決めが可能となる。特にこの方法では、対応点探索ラインの線分長さを変えることで、簡単に対応点探索ラインによる対応エッジ点の探索範囲を変えることができ、必要な安定性を調整できる利点が得られる。すなわち、繰り返し最小二乗法を適用する際に、対応点探索ラインの線分長さを徐々に短くしていくことで、より高精度で高速な位置決めが簡単に実現できる。
【０１９７】
加えて、パターンモデルをセグメントで表現するので、図２２に示すようなエッジ位置の波打現象を解消できる。すなわち、点と点での精密位置決めを行う場合、波の高いところとペアリングするのと低いところとペアリングするので位置が大きくずれることがあるが、そのような影響を低減できる。
【０１９８】
また、これに代わってあるいはこれに加えて、最小二乗法を繰り返す毎に、エッジ角度閾値を変化させてもよい。すなわち、エッジ角度閾値を最小二乗法の繰り返し回数に応じて徐々に小さくすることでも、より安定した位置決めを実現できる。
【０１９９】
なお、粗サーチで得られた初期位置あるいは再度の粗サーチで得られた精密位置決め開始位置に基づいてサーチ対象画像にパターンモデルを重ねる際は、サーチ対象画像は未処理のいわゆる原画像データを、パターンモデルは原画像データに対応したパターンモデルを用いる。
【０２００】
この方法であれば、サーチ対象画像の原画像データの、すべての画素をエッジ画像データに変換する必要が無く、処理の高速化が図られる。特に、タクトタイムが要求あれるインライン処理においては、このような低負荷で高速な処理は好ましい。なお、全体で事前にエッジデータを抽出した方が効率的な場合は、サーチ対象画像のすべての点をエッジ画像データに変換してパターンサーチを行うことも可能であることはいうまでもない。
【０２０１】
また、パターンモデルのすべてをサーチ対象画像に重ねて配置する必要はなく、少なくとも対応点探索ラインを重ねて配置すれば足りる。特に対応点探索ラインは直線であるため、演算で容易に求めることができる。したがって、本明細書において「重ねる」とは、現実に画像を重ねることを必ずしも意味せず、対応点探索ラインに従って対応エッジ点を決定する処理を意味するものとして使用する。また、ここでいう「重ねて配置する」とは、上述の通り重ねることで各画像の対応位置を把握しやすくしたことを説明するためのものであり、あくまでも計算上における仮想的なものにすぎず、実際にデータを重ねる作業は必要でないことはいうまでもない。
【０２０２】
この方法によれば、従来の方法に比べ高精度なエッジベースのサーチが実現できる。上述した特許文献１の手法では、エッジの方向や角度成分を検討しておらず、予め規定されたエッジの方向しか見ないため、複雑な形状での安定性が期待できない。これに対し、本実施の形態に係る手法では、エッジの方向が重要となるため、対応エッジ点の信頼性を高めることができる。さらに本実施の形態ではソーベルフィルタのようなカーネルの小さなフィルタを用いて差分を計算するため、ワークが細長いものであってもエッジを検出できる。このように、特許文献１の手法に比べ、複雑な形状のサーチ対象にも対応できる安定したエッジベースのサーチが実現できる。
【０２０３】
また、パターンモデルのサーチ対象画像中における検出候補の位置、すなわち局所サーチの初期位置を粗サーチで求める際に、サーチ対象画像を縮小してパターンサーチを行うことで、低負荷で高速に行える利点がある。ただ、縮小により一部の情報が失われる結果、精度が低下する虞があるので、情報量を維持するような縮小を行うことが望ましい（詳細は後述）。さらにパターンモデルの初期位置は、粗サーチで求める形態の他、ユーザが手動で初期位置を指定することもできる。
【０２０４】
なお上記の例において点とは、サーチ対象画像や登録画像を構成する点、すなわち一画素（ピクセル）を指すが、複数画素（例えば４画素）を一つの点として扱うことも可能であることは言うまでもない。したがって本明細書において点とは、一又は所定の画素数を意味するものとする。
【０２０５】
また「基点に基づいて」とは、基点上でエッジ検出を行うのみならず、基点の近傍でエッジ検出を行うことも包含する意味で使用する。例えば、基点の周囲１画素〜１０画素等、指定された範囲内でエッジ検出を行う。
【０２０６】
さらにセグメントとは、線分及び／又は円弧の組み合わせで構成される連続した有限長の線をいう。また線分や円弧に加えて、円錐曲線、スプライン曲線、ベジエ曲線等を組み合わせることもできる。また対応点探索ラインのデータには、基点の座標、対応点探索ラインの角度、長さが含まれる
（最小二乗法）
【０２０７】
最小二乗法は、線分セグメントに対しては直線のエラー関数を適応する。直線のエラー関数は、点と直線の距離をエラー関数にした最小二乗法である。また円弧セグメントに対しては、円弧のエラー関数を適応する。円弧のエラー関数は、点と円弧の距離をエラー関数にした最小二乗法である。この詳細については、後述する。
【０２０８】
最小二乗法の問題点として、大きく懸け離れた値が１つでも存在すると、この点に影響されて精度が極端に悪くなる点が挙げられる。そこで本手法においては、このような点に対する重み付けを低くするようウェイト値を持たせた重み付き最小二乗法を用いて、影響を抑制している。
【０２０９】
また、最小二乗法において使用する自由度としては、Ｘ方向移動、Ｙ方向移動、回転、拡大／縮小、スキュー、アスペクト等が利用できる。これらを選択することで、ｘｙ方向の平行移動のみならず、登録画像の回転や拡大縮小、歪み等にも対応できる。
（最小二乗法のエラー関数の一般化）
【０２１０】
ここで、最小二乗法のエラー関数を一般化して展開する。まずエラー関数Ｅ（ｐo，ｐ1，・・・，ｐn）がアフィンパラメータｐo，ｐ1，・・・，ｐnで決定されると考える（例えばｐ0＝ｘ、ｐ1＝ｙ等）。ここで最適なアフィンパラメータｐoo，ｐ1o，・・・，ｐnoでエラー関数Ｅ（ｐo，ｐ1，・・・，ｐn）が最小になると仮定する（o：optimized）。このときエラー関数Ｅ（ｐo，ｐ1，・・・，ｐn）を次式で表現する。
【０２１１】
【数１７】
2010067248.tif 000017
【０２１２】
上式におけるパラメータの意味は、以下の通りである。
i：対応エッジ点のindex
ωi：対応エッジ点とモデルとの位置関係で決まるウェイトであり、例えば対応エッジ点と線分との点と直線の距離が遠い場合、０に近づくように定義される。
ｅ（ｐ0，ｐ1，・・・，ｐn）：対応エッジ点とモデルとの幾何的な距離で決まる個別エラー関数であり、対応エッジ点と線分との点と直線の距離等で表される。
ｐ0〜ｐn：平行ｘ移動量，平行ｙ移動量，回転角度，スケール値等のアフィンパラメータ
【０２１３】
上記エラー関数Ｅ（ｐo，ｐ1，・・・，ｐn）を最小にするアフィンパラメータｐoo，ｐ1o，・・・，ｐnoを求めるために、その値に十分近いことが期待される粗サーチや一つ前に行われた精密位置決めで求めたアフィンパラメータｐ0t，ｐ1t，・・・，ｐntからの変位量
【０２１４】
【数１８】
2010067248.tif 000018
を求める。
【０２１５】
Δｐ0，Δｐ1，・・・，Δｐnは、以下の連立方程式を解くことで得られる。
【０２１６】
【数１９】
2010067248.tif 000019
【０２１７】
上述の通り、画像のエッジ強度のみならず、エッジの角度を用いることで、方向成分を加味することができ、ノイズ成分に強いより安定な位置決めが可能となる。特に画像データに対して微分処理を利用することで、照度の変動に影響を受け難い安定したサーチが可能となる。
（対応点探索ラインフィルタ処理）
【０２１８】
特に、登録画像に対して対応点探索ライン探索処理を行い、対応点探索ラインの選択が困難な可能性が高い場合には、そのような位置をパターンサーチから排除することが好ましい。例えば図２３のような登録画像がある場合を考えるとき、このパターンに対して対応点探索ラインを自動設定すると、図２４のようになる。この図に示すとおり、周辺輪郭のみならず、内部の中心付近に位置する濃淡差のある部分にも、対応点探索ラインが設定されることになる。このような中心付近に設定された対応点探索ラインでエッジのマッチングを行うと、エッジ角度が類似する部分が多々生じる。その結果、この対応点探索ラインを用いてパターンサーチを行うと、対応エッジ点検出で対応エッジ点が曖昧になる可能性が高くなる。
【０２１９】
本実施の形態においては、このような曖昧な対応点探索ラインを排除することで、安定した精度の高いサーチを可能としている。具体的には、対応点探索ラインフィルタ手段により、このような好ましくない領域に設定された対応点探索ラインをフィルタリングして、エッジ強度とエッジ角度が似ているものが存在する場合はこれを排除する。図２５に、図２４から対応点探索ラインをフィルタリングした結果の例を示す。
【０２２０】
このように、対応点探索ラインの候補に対して、対応点探索ラインフィルタ手段が対応点探索ラインフィルタ処理を行う手順の一例を、図２６のフローチャートに基づいて説明する。まずステップＳ２６０１で、登録画像に対して対応点探索ライン生成処理を行い、対応点探索ラインの候補を作成する。次にステップＳ２６０２で、登録画像に対して対応点探索ラインの候補を配置する。対応点探索ラインが作成された位置に配置されると、対応点探索ラインの候補の中間近辺で、対応点探索ライン候補が検出できる。
【０２２１】
さらにステップＳ２６０３で、対応点探索ラインの候補に沿って対応点探索ライン候補探索を行い、対応点探索ライン候補の数をそれぞれ計数する。またステップＳ２６０４でフィルタリング処理を行い、対応点探索ライン候補の数が２以上の場合、その対応点探索ラインでの対応点探索ラインは曖昧である可能性が高いと判断して、対応点探索ライン候補から排除する。そしてステップＳ２６０５で、残った対応点探索ラインを最終の対応点探索ラインとする。この処理により、不確実な対応点探索ラインを排除して、より安定したパターンサーチ結果が見込まれる。
【０２２２】
なお、精密位置決めの工程を繰り返す場合は、対応点探索ラインの線分長さを繰り返し回数に応じて短くしていくため、一旦行った対応点探索ラインフィルタ処理で選択された対応点探索ラインを記録しておき、繰り返し工程においてはこの情報を利用することができる。あるいは、対応点探索ラインを短くした場合も同様に対応点探索ラインフィルタ処理を行い、その結果選択された対応点探索ラインを記録しておくこともできる。
（対応点探索ライン）
【０２２３】
また対応点探索ラインの線分長さを変化させることで、精密位置決めの安定度の向上と高速化が期待できる。対応点探索ラインの線分長さは、粗サーチと精密位置決めの縮小率の差で決定する。例えば、精密位置決めを等倍の画像で行い、最終的な粗サーチを１／４倍とする場合、２＊４＝８ピクセル程度の長さとする。
（チェーンフィルタ手段６６）
【０２２４】
上記の例では、すべてのセグメントに対して少なくとも一の基点を設定している。本実施の形態においては、セグメントを生成する際に、セグメントを構成するチェーンを選別することにより、予め信頼性の高いセグメントを構築し、各セグメントに基点を設定している。このような特定のチェーンの選択又は排除は、図１のブロック図に示したチェーンフィルタ手段６６で行う。チェーンフィルタ手段６６がチェーンを選択する基準としては、平均エッジ強度、チェーンの長さ等が挙げられる。
【０２２５】
このチェーンフィルタ手段６６は、登録時及び運転時にチェーンの選択を行う。登録時においては、セグメントを構成するのに値するチェーンを抽出する。具体的には所定のチェーン長閾値に満たない短いチェーンや、所定のエッジ強度閾値に満たない平均エッジ強度の低いチェーンについて、これらのチェーンからセグメントを作成しても、セグメントデータの信頼性が低いことが予想されるため、これらのチェーンを排除するようにフィルタリングする。
【０２２６】
一方、運転時においては、長さの短いチェーンはノイズである可能性が高いため、サー対象画像の状況に応じて使用するかどうかを選択する。例えば、ユーザが長さの閾値を設定し、短いチェーンを排除する。以下、これらの詳細を順次説明する。
【０２２７】
まず平均エッジ強度でチェーンをフィルタリングする場合は、各チェーンに対して含まれるエッジ点の平均エッジ強度をチェーンフィルタ手段６６が演算し、予め設定された平均エッジ強度閾値と比較してフィルタリングする。すなわち、平均エッジ強度の低いチェーンを排除し、一定以上の平均エッジ強度を有するチェーンのみに対してセグメント化し、得られたセグメントに対して基点を設定し、パターンモデル化することで、確度の高いエッジに基づいたパターンサーチが見込まれ、サーチ精度を高めることができる。平均エッジ強度閾値は、パターンモデルの輪郭を識別するのに十分なエッジ強度を含む程度に、ユーザが設定できる。
【０２２８】
またチェーン長でフィルタリングする場合は、各チェーンの長さを予め設定されたチェーン長閾値と比較して、チェーンフィルタ手段６６がフィルタリングする。すなわち、一定長さ以上のチェーンのみを選択し、それよりも短いチェーンを排除することで、安定したエッジに基づいたパターンサーチが可能となり、精度向上に寄与する。
【０２２９】
一方、チェーンで構成されたセグメントに対してフィルタリングを行うセグメント選択手段６７を利用することもできる。セグメント選択手段６７がセグメントの選択する基準としては、上記チェーンフィルタ手段６６と同様に平均エッジ強度、セグメントの長さ、近傍に類似するエッジ角度を有するセグメントが存在するか否か、あるいは理想エッジ角度の偏在の排除、等が挙げられる。また、単に短いセグメントを一律に排除するのでなく、セグメントを構成する線分や円弧の組み合わせに応じて、セグメントのフィルタリング方法を変更してもよい。例えば、セグメントの集合から十分長いセグメントを抽出し、それらの組み合わせを評価し、円弧のセグメントが一以上ある場合は、線分も一以上あれば、短いセグメントは不要としてこれらを排除又は削除する。また、すべてのセグメントが線分の場合、長いセグメントが３本以上あれば、他の短いセグメントを排除しても十分な精度を維持できる。このように、セグメントを構成する組み合わせに応じてセグメント選択手段６７によるフィルタリングを変更し、適切なセグメントを選別してより効率よくサーチを実行できる。
【０２３０】
なお、ここでセグメント長とは、パターンモデルを構成するセグメントの、線分や円弧の端から端までの直線もしくは曲線の長さを指す。また、線分長さと円弧長さについて、それぞれセグメント長閾値を個別に設けることもできる。セグメント長閾値は、登録画像や要求される精度等に応じて設定され、又は登録画像やサーチ対象画像の平均セグメント長に基づいて設定できる。
【０２３１】
さらに近傍に類似するエッジ角度を有するセグメントが存在するか否かに基づいてフィルタリングする場合は、各セグメントに含まれるエッジ点のエッジ角度について、近傍に類似するエッジ角度を有する別のセグメントが存在するかどうかをセグメント選択手段６７が判定し、存在する場合は該セグメントを排除する。すなわち、同じようなエッジ角度を有するセグメントについては、パターンサーチ結果が安定しない虞があることを考慮し、このようなセグメントを排除して基点を設定することにより、パターンサーチ結果の安定性を高めることができる。
（仮対応エッジ点）
【０２３２】
次に図２９に基づき、精密位置決めにおいて基点に対応する対応エッジ点の座標を求める手順を説明する。ここでは、まず対応点探索ラインＴＬ上で対応エッジ点を見つけ、次にもう一方のペアとなる対応エッジ点を見つけ、その二つから平均座標を求めてその座標を真の対応エッジ点座標とする。
【０２３３】
具体的には、図２９において、円弧状のセグメントの一部（図において○で示す位置）に基点ＫＴが設定され、この点を通る対応点探索ラインＴＬが左上から右下方向に延長されている。まず、対応点探索ラインＴＬに沿って、サーチ対象画像の各点のエッジ強度を調べる。図２９の例では、基点ＫＴをベースとしてエッジ強度を求めている。ここでは、基点ＫＴを含む枡目状の各頂点ａ、ｂ、ｃ、ｄの４点につき、各点のエッジ強度を調べる。そして最もエッジ強度の高い点のサブピクセル位置を、仮対応エッジ点として求める。その結果、例えばａ点のサブピクセル位置としてｅが仮対応エッジ点として演算されたとすると、次にこの仮対応エッジ点ｅに対応するペア点を選択する。ペア点は、仮対応エッジ点ｅとペア点とで基点ＫＴを挟むように選択される。ここでは、ペア点としてｆが選択されたとする。さらに、これら仮対応エッジ点ｅ及びそのペア点ｆから平均座標を求める。そして、得られた平均座標を真の対応エッジ点座標として扱う。
【０２３４】
このようにすることで、対応エッジ点が波打状に演算されることを抑制して、安定した演算結果を得ることができる。すなわち、点と点での精密位置決めを行う場合、波の高いところでペアリングするのと、低いところでペアリングするので位置が大きくずれることがあるが、上記手法によりその影響を低減できる。
（近傍エッジ点を用いて対応エッジ点の座標を求める方法）
【０２３５】
また対応エッジ点の座標をサブピクセル単位で求める方法は、上記に限られず他の方法も利用できる。例えば、対応点探索ライン上で対応エッジ点をピクセル単位で探索し、得られた点を仮対応エッジ点とする。この仮対応エッジ点の周囲にある近傍エッジ点をピクセル単位で複数求め、該仮対応エッジ点と該複数の近傍エッジ点のサブピクセル座標を求めた上で、これらの平均座標を求めることでも実現できる。この方法であれば、仮対応エッジ点と近接する複数の近傍エッジ点を用いて真の対応エッジ点の位置を求めることができるため、対応エッジ点の座標位置がサブピクセル単位で精度よく得られる。また、対応点探索ラインによらず、仮対応エッジ点の周囲で適宜選択される複数の近傍エッジ点を利用することで、より簡素に対応エッジ点の座標位置を正確に決定できる。
【０２３６】
近傍エッジ点の選択は、仮対応エッジ点の周囲で、同じ輪郭あるいはセグメント上に位置するエッジ点とできる。また、仮対応エッジ点のエッジ角度を用いることで、エッジ角度の似た近傍エッジ点が得られる。好ましくは、仮対応エッジ点のエッジ角度方向を中心として、左右に近接するエッジ点を近傍エッジ点として各々選択する。また、仮対応エッジ点から近傍エッジ点までの距離は、近接していることが望ましく、例えば２ピクセル以内、好適には１ピクセル程度とする。離れすぎると、精度が悪くなるからである。以下、近傍エッジ点を用いて対応エッジ点の座標を求める手順を、図６５の模式図及び図６６のフローチャートに基づいて説明する。
【０２３７】
まずステップＳ６６０１で、対応点探索ライン上で仮対応エッジ点をピクセル単位で探索する。図６５において、斜線で示す白丸が基点ＫＴであり、基点ＫＴを通る対応点探索ラインＴＬ上で、輪郭を構成するセグメントの対応位置を見つける。探索はピクセル単位、すなわち図６５の格子状のグリッドの交点を基準として行われ、ここではピクセル座標で（ｘ、ｙ）＝（２，３）が選択される。
【０２３８】
次にステップＳ６６０２で、ピクセル単位の仮対応エッジ点の周囲で、近傍エッジ点をピクセル単位で選択する。ここでは、仮対応エッジ点のエッジ角度が、対応点探索ラインと重なる方向のベクトルを有しているため、対応点探索ラインを挟んで左右に位置するエッジ点であって、所定値以上のエッジ強度を有するエッジ点を近傍エッジ点として各々選択する。具体的には、右側に位置する第１の近傍エッジ点、左側に位置する第２の近傍エッジ点の２つを選択する。図６５の例では、第１の近傍エッジ点のピクセル座標は（２，２）、第２の近傍エッジ点のピクセル座標は（１，３）となる。この際、各近傍エッジ点のエッジ角度は、仮対応エッジ点に近傍するエッジ点であることから類似のエッジ角度を有している可能性が高く、確認しなくともよい。もちろん、エッジ角度の類似性が高いことを確認した上で近傍エッジ点として選択することもできる。なお、近傍の位置に所定値以上のエッジ強度を有するエッジ点が無い場合は、近傍エッジ点を選択しない。この場合は、得られたエッジ点（仮対応エッジ点と他方の近傍エッジ点）のみを利用して、後述の真の対応エッジ点を演算する。また、この例では左右の近傍エッジ点を計２個選択しているが、近傍エッジ点の選択数は１、又は３以上とすることもできる。ただ、精度と演算処理の付加のバランスを考慮すると、２個が好ましい。
【０２３９】
さらにステップＳ６６０３で、仮対応エッジ点、近傍エッジ点に基づき、真の対応エッジ点の座標を演算する。ここでは、仮対応エッジ点及び近傍エッジ点のサブピクセル位置から、その平均座標として、真の対応エッジ点の座標位置を決定する。図６５の例では、仮対応エッジ点のサブピクセル位置である黒丸で示すＴＰ1、第１の近傍エッジ点のサブピクセル位置である斜線の丸ＴＰ2、第２の近傍エッジ点のサブピクセル位置であるクロスハッチングの丸ＴＰ3の３点の平均から、対応エッジ点を決定する。各エッジ点のサブピクセル位置は、その周囲の画素値から予め演算しておく。サブピクセル位置の演算方法は、既知の方法が利用でき、例えば各エッジ点を中心とする３×３の周囲の画素値から、あるいはエッジ角度の方向にある近接するエッジ点の情報を用いる等して、サブピクセル位置を計算できる。なお各エッジ点のサブピクセル位置を演算するタイミングは特に限定されず、ピクセル単位でのエッジ点が決定した直後でも、平均座標演算の直前でも良い。
【０２４０】
以上のようにして、エッジ点３点のサブピクセル座標の平均から対応エッジ点をサブピクセル単位で演算できる。この方法であれば、仮対応エッジ点から容易に３点のエッジ点を抽出できるので、多くのエッジ点を利用した高精度な対応エッジ点が決定できる。例えば基点の数が１０個の場合、通常であれば対応エッジ点は１０個となるが、上記方法であれば１０個の仮対応エッジ点各々に対し、左右の点を付加して３０個のエッジ点から対応エッジ点を演算できるので、平均化効果によって精度を向上できる。特に、図２９に基づき上述したペア点と仮対応エッジ点の２つから平均座標を求める方法に比べ、仮対応エッジ点に２つの近傍エッジ点を加えた３点で平均座標を求めるため、精度的に有利となる。なお上記では、３点を求めて平均としているが、それぞれ３点を個別に精密位置決め計算に用いることもできる。
（エッジ角度画像からエッジ角度ビット画像への変換）
【０２４１】
次に、エッジ角度画像からエッジ角度ビット画像への変換について、図３０〜図３３に基づいて説明する。コース・トゥ・ファインのアプローチを取る際は、最初の粗サーチに際しての縮小画像の設定は容易でない。画像の縮小によって、サーチに必要な特徴量の情報が失われてしまう場合があるためである。特にエッジベースのサーチにおいては、探索精度向上のためエッジ角度情報が重要となる。そこで本実施の形態では、画像縮小手段６１で画像を縮小する際、縮小率を高くしてもエッジ角度情報を維持可能なエッジ角度ビット画像作成手段６９、エッジ角度ビット画像縮小手段７８を備えることで、十分な特徴量を残しつつデータ量を低減し、処理の高速化を図っている。
【０２４２】
以下、画像縮小手段６１で画像を縮小する際にエッジ角度情報を取得し、これを保持する手順を説明する。まず、エッジ角度画像のエッジ点毎にエッジ強度を調べ、設定されたエッジ強度閾値よりもエッジ強度が大きい場合は、エッジ角度の向きに対応するビットを１にして、それ以外を０に設定する。例えば、図３０に示す画素ａ〜ｄの４画素（エッジ点）で構成された２ｘ２画素のエッジ角度画像から、エッジ角度ビット画像作成手段６９でエッジ角度ビット画像を生成する場合を考える。各画素ａ〜ｄは、エッジ強度が閾値よりも大きく、かつそれぞれが矢印で示すエッジ角度を有している。このエッジ角度を、エッジ角度とビットの対応を表したエッジ角度区分に従って０〜７の８種類のエッジ角度ビットで表現する。
（エッジ角度ビット画像）
【０２４３】
このエッジ角度画像をエッジ角度ビット画像に変換する際、エッジ角度情報はエッジ角度ビットに変換される。エッジ角度ビットとは、エッジ角度方向を所定角度毎に区分けしたコードである。図３１に示すエッジ角度区分は、上述した図６（ｂ）と同様のものが利用できる。図３１の例では、エッジ角度方向として、濃度勾配方向を４５°刻みで８つの区分に区分けしており、各区分にエッジ角度ビットを割り当てている。あるいはこの例に限られず、図３１の姿勢から反時計回りに２２．５°回転させて、水平又は垂直方向から２２．５°ずらして８等分し、真右から時計回りに４５°幅でＥ、ＳＥ、Ｓ、ＳＷ、Ｗ、ＮＷ、Ｎ、ＮＥのエッジ角度区分にラベル分けし、各エッジ角度区分に対してエッジ角度ビットのラベルをそれぞれ０、１、２、３、４、５、６、７と付与してもよい（上述した図５２（ｂ））。もちろん、このような区分けは例示であって、例えば１６等分や４等分、さらには３等分や５等分に区分けすることもできる。
【０２４４】
以上から、図３０に示すエッジ角度画像データを、図３１のエッジ角度区分に基づいて２ｘ２のエッジ角度ビット画像に変換すると図３２のようになる。このように、ａ、ｂ、ｃ、ｄのラベルで区別された４つのエッジ点に対して、各々のエッジ角度に対応したエッジ角度区分にビットが立つ。
【０２４５】
なお、エッジ角度ビット画像を取得する方法としては、上述したように、あるエッジ強度しきい値以上の部分のみに対して処理を施す手法の他に、ある程度の幅を有するエッジ角度ビット画像を取得するために、エッジ強度画像とエッジ角度画像を用いて細線化処理を施し、その細線化処理を行ったエッジ角度画像を用いて上述したようなエッジ角度ビット画像を取得する方法もある。細線化処理を行う手法の場合、上述した手法に比べ処理時間が比較的かかるものの、サーチ対象物の輪郭部分を限定できるため、ノイズを排除しやすいというメリットがある。
（エッジ角度ビット画像の縮小）
【０２４６】
このようにエッジ角度ビット画像で表現した後に、エッジ角度の情報が十分残るようにデータを縮小する。具体的には、エッジ角度ビットラベル毎に各画素のエッジ角度ビットのＯＲ又はビット和をとるように合成する。例えば、縮小する２ｘ２のデータが図３２の状態である場合に、これを縦１／２×横１／２（＝１／４）に縮小して画素ａ〜ｄの４画素をａ’の１画素で表現すると、図３３のようになる。この図に示すように、画素ａ〜ｄのエッジ角度ビットを纏めたエッジ角度ビット縮小画像に、各画素のエッジビットが合成されて、０〜７のエッジ角度ビットラベルの該当欄に、エッジ角度ビットが立つ。このエッジ角度ビット縮小画像にエッジ角度情報を保持する処理は、エッジ角度ビット画像縮小手段７８で行われる。これにより、データ量を減少させつつ、エッジ角度情報が縮小後も維持されるので、縮小を繰り返すことで縮小率を高くしてもサーチに十分な特徴を残すことができる。
【０２４７】
以上の圧縮処理によって、従来の問題であった、サーチに十分な特徴量を残すよう縮小率を抑えると、サーチの処理速度が不十分となってしまう状況が改善される。エッジ検出を行う縮小率は、例えば１／２に固定にしても、このエッジ角度ビット画像の縮小処理によって十分高速なサーチが可能になる。エッジ検出を行う縮小率は、登録画像のサイズ、パターンモデルの特徴データの少なくともいずれかに基づいて自動的に決定できる。また、ユーザが独自に設定するようにしてもよい。
【０２４８】
ここで、エッジ角度ビット画像を縮小してエッジ角度ビット縮小画像を生成する手順の例を、図３４〜図３７に基づいて説明する。エッジ角度ビット縮小画像を作成する際に、注意すべき点として切り出し問題がある。つまり、単純にサブサンプリング処理で縮小処理をしただけでは、その処理の開始座標やサーチ対象の入力画像における位置の微妙なずれにより、後述するスコアの計算に大きな変動が生じる可能性がある。この切り出し問題を回避する縮小の方法として、以下の２つの方法が考えられる。
【０２４９】
１つ目の方法は、縮小処理を行った後に膨張を行う方法である。この方法を図３４、図３５を用いて、１／ｎ（ｎ＝２）に縮小する処理の例で説明する。まず、図３４のそれぞれの四角の領域に含まれるｎｘｎのエッジ角度ビットデータでＯＲ演算を行う。その結果を先のそれぞれのｎｘｎの領域のエッジ角度ビットデータを代表するエッジ角度ビットデータとして置き換える。この処理を行うことで、元の画像の１／ｎに縮小される。
【０２５０】
このままでは、切り出し問題が発生することがあるので、この縮小画像に対して膨張を行う。ここでは、図３５のように縮小後の画像のそれぞれの四角いｍｘｍ（この例ではｍ＝２）の領域のエッジ角度ビットデータに対してＯＲ演算を行って、その結果をそれぞれのそのｍｘｍの領域を代表するエッジ角度ビットデータとして置き換える。この処理では画像の縮小は生じない。この例ではｍ＝２であるが、サーチ対象の形や大きさの予想される変動に応じて、ｍを大きくすることも考えられる。
【０２５１】
もう一つの方法は、上記の縮小処理で行うＯＲ演算の範囲を広めに取り縮小し、その後の膨張を行わない方法である。この方法を図３６を用いて１／ｎ（ｎ＝２）に縮小する処理の場合で説明する。図３６のそれぞれの四角の領域に含まれる（ｎ＋ｍ）ｘ（ｎ＋ｍ）（ｎ＝１，ｍ＝１）のエッジ角度ビットデータでＯＲ演算を行う。その結果を先の領域の中心付近のｎｘｎエッジ角度ビットデータを代表するエッジ角度ビットデータとして置き換える。この処理を行うことで、元の画像の１／ｎに縮小される。図３７は２番目の方法でｎ＝２、ｍ＝１の場合を示してる。
【０２５２】
ここで図３６に示すように、膨張なしで通常の２ｘ２の縮小を繰り返す場合は、切り出し位置の問題が発生することがある。すなわち、サーチ領域の左上の座標が１ピクセル変化することで、縮小する時の画素のセットが変化して、登録画像とサーチ対象画像が同一画像にもかかわらず、スコア計算が低下してしまうことが起こり得る。これに対し、膨張を行うとこのような問題が発生しないという利点が得られる。
（角度境界におけるエッジ角度ビット変換処理）
【０２５３】
さらに、エッジ角度ビット変換に際して、エッジ角度が角度境界付近である場合のエッジ角度ビットを、境界を構成する２つの角度領域に対応するビットを２つたてることで、安定性を向上させる効果が期待できる。例えば、上述した図３０に示す画素ａ〜ｄの４画素で構成されたエッジ角度画像を変換した図３１のエッジ角度ビット画像において、エッジ角度がＥとＳＥの境界付近にある場合は、ノイズによってＥの区分のエッジ角度ビットが立ったり、ＳＥのエッジ角度ビットが立つことがある。このようなぶれが原因となり、本質的でない影響が一致度の計算において生じることが予想される。そこで、エッジ角度が境界にある場合は、境界を区画する両方のエッジ角度区分のエッジ角度ビットを１に設定する。これにより、ノイズによるぶれを無くし、安定した一致度の計算結果が期待できる。具体的には、エッジ角度区分の境界を中心とする所定幅内（例えば５．６２５°）にエッジ角度が位置する場合に、境界に面した両方のエッジ角度ビットを１とする。
【０２５４】
なお、この角度境界におけるエッジ角度ビット変換処理は、サーチ対象のエッジ角度ビット変換処理についてのみ行い、パターンモデルのエッジ角度ビット変換では行わない。パターンのエッジ角度の変換に対しても同様の処理を行うと、各エッジ点に対して不自然なウェイトの変化が生じてしまうためである。
（エッジ角度ビット隣接処理）
【０２５５】
また、上記の例ではエッジ角度画像からエッジ角度ビット画像への変換においてエッジ角度ビットを１のみ立てているが、該当するエッジ角度区分を中心として、隣接したエッジ角度区分についてもエッジ角度ビットを立てるようなエッジ角度ビット隣接処理を行うこともできる。例えば、該当するエッジ角度区分及び左右に隣接するエッジ角度区分に、それぞれ１ビットのエッジ角度ビットを付与する。または該当するエッジ角度区分に２ビット、左右に隣接するエッジ角度区分にそれぞれ１ビットのエッジ角度ビットを付与するよう、重み付けを行うこともできる。さらに、パターンモデルのエッジ角度とサーチ対象画像のエッジ角度が十分一致しているときは３、少しずれている場合はエッジ角度ビットを１、ずれが大きい場合は０というように、ファジー的な効果を付して重み付けすることもできる。
【０２５６】
このようなエッジ角度ビット隣接処理に際しても、上述の通り境界付近にエッジ角度が存在する場合はノイズによるぶれの影響が考えられるため、サーチ対象画像のエッジ角度ビットがエッジ角度区分の境界にある場合は、その境界を中心として隣接するエッジ角度区分に各々２ビットを立てることにより、ぶれの影響を回避できる。
【０２５７】
なお、上記の例ではエッジ角度の角度分解能として８ビットを用いたが、これに限らず１６ビットや３２ビットのように、さらに角度分解能の高い変換を行うこともできる。
（並列化）
【０２５８】
また、パターンモデルのエッジ角度をエッジ角度ビットに変換した値を並列化することでサーチ処理の高速化を図ることができる。パターンモデルのエッジデータを並列化した例を図３８〜図３９に示す。図３８は、並列前のパターンモデルの概念図、図３９は並列後のパターンモデルの概念図である。これらの図に示すように、パターンモデル上の１つの基点のエッジ角度ビットデータを複数、横に配置することで並列化が図られ、処理の高速化が可能となる。ここで演算部を構成する一般的なＣＰＵは、４バイトから８バイトの並列処理が可能で、４〜８倍速処理が可能となる。このように並列化処理により粗サーチを高速化できる。
（エッジ角度ビット縮小画像を用いた粗サーチ）
【０２５９】
以下、このような縮小データを用いて粗サーチを行う手順を説明する。ここでは、縮小を行って１／８のエッジ角度ビット縮小画像が得られたとする。このエッジ角度ビット縮小画像は、例えば等倍画像のサイズが６４０ｘ４８０であったとして、エッジ抽出を行ったのが１／２の３２０×２４０であったとすると、１／８の圧縮処理を行ったエッジ角度ビット画像のサイズは４０×３０となる。このエッジ角度ビット縮小画像に対するサーチは、以下のようにして行われる。まず、サーチ処理前のパターンモデル登録時に、図４０のようなデータを作成する。この図に示すように、パターンモデルは位置と角度情報を持つエッジデータの配列として保持されている。図４０（ａ）パターンモデルの一例、図４０（ｂ）はエッジデータのパターンモデルの一例を、それぞれ示している。図４０（ｂ）においてｘ，ｙはエッジの座標位置であり、θはエッジの角度である。このパターンモデルは、図４０（ｂ）に示すように座標位置と角度情報を持つエッジデータの配列として保持されている。
【０２６０】
上記のデータとサーチ対象画像のエッジ角度ビット画像を使って、パターンの位置及び姿勢を繰り返し変化させて、パターンの各位置及び姿勢に対して一致度を順次計算していく。この計算は以下のようにして行われる。まず、一致度を調べたい位置及び姿勢を表すアフィン変換値を決定する。このアフィン変換値は、パターンモデルの縮尺とサーチ対象画像の縮尺も考慮して作成される。このアフィン変換値を使って、エッジの位置ｘi，ｙiとエッジの角度θiを変換する。ここで変換後のエッジの位置をＸi，Ｙiとし、変換後のエッジ角度をφiとする（ｉはエッジのｉｎｄｅｘを表す添え字）。この一致度は、エッジ角度をφiをサーチ対象画像と同じ方法でビットデータに変換して計算する。一致度Ｓの計算式は、次式で表される。
【０２６１】
【数２０】
2010067248.tif 000020
【０２６２】
このようにして、精密位置決め手段７６がサーチ対象画像及びパターンモデルに含まれる各エッジ点のエッジ強度及びエッジ角度を各々比較して、一致度を計算する。上記の一致度Ｓが高いことは、その位置及び姿勢にパターンモデルが存在する確率を高いことを示す。このようにして、サーチを行うのに十分な特徴量を残すように決定した縮小率で、そのままサーチすると十分な処理速度にならないような状況が改善される。また、エッジ抽出を行う縮小率を、例えば１／２固定にしても十分高速なサーチが可能になるので、一般的に複雑であるエッジ抽出を行う縮小率の決定を行わなくても良いという利点も得られる。
（サーチ対象画像の縮小工程）
【０２６３】
このような縮小処理で、縮小率が高くてもサーチに十分な特徴を残すことができるようになる。サーチ対象画像に対してソーベルフィルタ等のエッジ抽出処理を行う際、オリジナルサイズの等倍画像のままではノイズも多く、粗サーチのための特徴を抽出するのに不適切となる虞がある。そこで本実施の形態では、先に縮小画像を作成した上で、エッジ抽出処理を行う。これにより、画像データを縮小することによって平均化効果も得られ、ノイズ低減にも寄与する。ここでは、最初の縮小率（第１縮小率）としてオリジナルサイズの１／２に設定している。このサイズであれば、サーチに必要な特徴を十分に残しつつ、平均化によるノイズ低減効果も得られる。
（エッジ方向の極性）
【０２６４】
さらにこの方法では、エッジ方向の極性の有無を設定できる。このため極性に応じて、エッジ角度に対する処理方法を変化させることができる。従来はこのような極性の概念は考慮されておらず、エッジの方向（角度）の概念のみであったため、例えば０〜１８０°として扱われる結果、向きの異なるベクトルを区別できず誤サーチが生じる問題があった。これに対して上述の方法では、極性の概念を考慮することで０〜３６０°をカバーできるようになり、一層正確なサーチが実現される。
【０２６５】
極性無視の場合、サーチ対象側のエッジ角度ビット変換において、逆向きのビットも同時に立てるという処理で簡単に実現できる。もしくは、向きではなく、エッジ方向に対して均等にビットを割り付けることもできる。例えば粗サーチにおいて、エッジ分解能である８ビットのエッジ角度ビットを、エッジ方向に対して均等に割り付けることにより、エッジの極性よりもエッジの方向の分解能の方を重視したサーチ結果を得ることができる。
（回転角度に関する精密位置決め）
【０２６６】
次に、点と円弧の距離をエラー関数とした最小二乗法で円弧セグメントの精密位置決めを行う手順について、図４１〜図４５に基づいて説明する。ここでは、パターンモデルＰＭとして図４１に太線で示すような、一部を切り欠いた円形を円弧セグメントと線分セグメントで表現したパターンで、サーチ対象画像に対して精密位置決めを行う場合を考える。図４１のパターンモデルＰＭは、１の円弧セグメントと１の線分セグメントで構成されており、このようなワーク形状は、オリエンテーションフラット面を設けたウェハ等で一般的に用いられている。このパターンモデルＰＭでサーチ対象画像に対して粗サーチを行い、パターンモデルＰＭを検出候補の位置に配置した、ある程度の位置決めがなされた状態を図４２に示す。ここでは、サーチ対象画像のエッジ点に対してパターンモデルＰＭがほぼ重ねられており、切り欠き部分の線分セグメントのみが不一致となった状態を考える。なおこれらの図において、太線はパターンモデルＰＭを、細線はサーチ対象画像のエッジ点（入力エッジ点ＩＥ）を、それぞれ示す。さらに入力エッジ点ＩＥの注目点を破線矢印で示すと共に、この入力エッジ点の接線ＳＬを破線で示す。なお実際の接線ＳＬはもっと短く、細線のパターンモデルＰＭに重なる状態で存在しているが、これらの図においては説明の便宜上長く表示している。
【０２６７】
この状態から精密位置決めを行うと、線分セグメント部分が一致するよう相対的に回転すること、すなわち図４２において矢印で示す位置の入力エッジ点に対し、最小二乗法を適用しても、回転によって必ずしもエラーが大きくならないことが期待される。ここでは、円弧セグメントに対しては点と直線でなく、点と円弧の距離をエラー関数とした最小二乗法を適用する。具体的には、円弧状のパターンモデルの中心と、サーチ対象画像のエッジ点を円弧とする半径との差の絶対値をエラー値として、最小二乗法を適用する。すなわち、最小二乗法で用いる円弧セグメントのエラー関数を、円弧セグメントを中心とする理想半径と、円弧の中心と対応エッジ点の距離の差とする。この円弧セグメントのエラー関数は、次式で表現できる。
【０２６８】
【数２１】
2010067248.tif 000021
【０２６９】
【数２２】
2010067248.tif 000022
【０２７０】
この結果、図４３に示すように矢印の入力エッジ点と円弧モデルとの距離は、あまり変化しない。すなわち、図４３のようなパターンモデルＰＭの反時計方向への回転も十分解として生じることを意味する。これにより、円弧状のワークにおいて少ない回数の精密位置決めで高い角度の精度の達成が期待できる。なお図４２、図４３の例では、点線で示す円弧の領域は実際にはパターンモデルの細線と重なっているが、説明の便宜上、これらの図においてはパターンモデルと少しずらして表示している。
【０２７１】
一方で従来の最小二乗法では、入力エッジ点と接線の距離をエラー関数とし、この距離が小さくなるようにパターンモデルを移動させていた。このため、パターンモデルが正しい回転方向に回転せずに、却って位置ずれが大きくなることも考えられる。例えば、図４７の状態から図４８に示すようにパターンモデルＰＭを反時計回りに回転させることが期待できない場合があった。すなわち、図４７において矢印で示す位置にある入力エッジ点と接線の関係から、図４８に示すようにパターンモデルＰＭを回転させると、入力エッジ点が接線から離れる方向となるため、このような回転が解として生じ得ない結果となっていた。これに対し本実施の形態では、上述の通り点と円弧の距離をエラー関数とした最小二乗法を採用しているため、円状のワークにおいて少ない回数の精密位置決めで高い角度の精度の達成が期待できる。
（対応エッジ点生成処理）
【０２７２】
さらに図４１のパターンモデルＰＭに対して対応点探索ライン生成処理を行った例を、図４４に示す。このように、基点は円弧セグメント、線分セグメント上の中心に一つ割り当てられ、その点から一定間隔で端縁付近を除いて設定され、さらに各基点上でセグメントの法線方向で、内側から外側に向かって対応点探索ラインが設定される。このパターンモデルで、サーチ対象画像に対して粗サーチを行い、決定された検出候補の位置及び姿勢にパターンモデルＰＭを重ねた状態を、図４５に示す。
【０２７３】
この状態で、各対応点探索ラインに沿ってエッジ抽出を行い、各セグメントに対する対応エッジ点を探索する。対応エッジ点は、各対応点探索ラインとサーチ対象画像のエッジ点（細線）とが交差する点となるので、例えば図４５において×で示す点が対応エッジ点となる。図４５の例では、粗サーチの結果得られた検出候補の位置に配置されるパターンモデルと入力エッジ点とで円弧部分がほぼ重なっているため、円弧セグメントの対応エッジ点はほぼ円弧セグメントに一致している。このため、円弧状のワークを相対的に回転させても、円弧のエラー関数は大きくならないので、この自由度は回転を阻害しない。したがって、回転移動を解とすることが期待できる。
【０２７４】
一方、線分セグメントの対応エッジ点の多くは、線分セグメント上にない。線分セグメントに対する最小二乗法では、点と直線の距離がエラー関数になっているので、全体的に反時計周りに回転することでそのエラー関数の値が減少するであろうことが推測される。これらのことから、最小二乗法で得られる解として、反時計周りの回転が得られることが十分期待できることが判る。
（対応エッジ点候補が複数ある場合の重み付け処理）
【０２７５】
さらにまた、基点に対応する対応エッジ点候補が複数ある場合に、各対応エッジ点に対して重み付けを行うことで、対応エッジ点の決定が曖昧であった場合の精密位置決めの精度を向上させることができる。この様子を図４９に基づいて説明する。ここではパターンモデルとして図４９（ａ）に太線で示すような、長方形に２本の縦線が入ったパターンモデルＰＭを用いて、精密位置決めを行う例を考える。この場合に、粗サーチで図４９（ｂ）に細線で示すようなセグメントＳＧ1、ＳＧ2が得られたとする。ここでは、図４９（ｂ）においてワークの左右に位置する２本のセグメントＳＧ1、ＳＧ2のみを考える。これらセグメントの対応点探索ラインＴＴＬ1、ＴＴＬ2は、上述の通り基点ＫＴ1、ＫＴ2を通る各セグメントＳＧ1、ＳＧ2の法線方向（エッジの方向）に設定される。各セグメントＳＧ1、ＳＧ2に対して、基点ＫＴ1、ＫＴ2のそれぞれに対応点探索ラインＴＴＬ1、ＴＴＬ2を破線で示すように設定すると、各対応点探索ラインＴＴＬ1、ＴＴＬ2上に位置する対応エッジ点候補が得られる。ここで、右側のセグメントＳＧ1に対しては対応エッジ点候補ＴＴAが１個のみであるが、左側のセグメントＳＧ2に対しては対応エッジ点候補ＴＴB、ＴＴCが２つある。対応エッジ点の決定は、対応エッジ点候補の内で基点との距離が最も近いものを選択するため、ＴＴA、ＴＴBがそれぞれ対応エッジ点となる。ここで、図４９（ｂ）の例では左側のセグメントＳＧ2に対しては対応エッジ点候補が複数あるため、曖昧さを含んでいると言える。この場合に、いずれの方向にセグメントすなわちパターンモデルを移動させるかが問題となる。特に図４９（ｂ）の例ではＴＴBが対応エッジ点として選択される結果、セグメント全体すなわちパターンモデルが右に移動することとなれば、所望する精密位置決めとは逆方向に移動されることとなり、好ましくない。
【０２７６】
そこで、最小二乗法の計算を行う際に、各対応エッジ点に対して重み付けを行う。図４９（ｂ）の例では、右側のセグメントＳＧ1に対しては基点ＫＴ1の対応点探索ラインＴＴＬ1上に存在する対応エッジ点ＴＴAが１個のみであるため、重み「１．０」を与える。一方、左側のセグメントＳＧ2に関しては、基点ＫＴ2の対応点探索ラインＴＴＬ2上に、基点ＫＴ2を挟んで左右に対応エッジ点候補ＴＴB、ＴＴCが位置している。そこで、基点ＫＴ2に関する対応エッジ点ＴＴBの重み付けを、基点ＫＴ2から各対応エッジ点候補までの距離に応じて設定する。重み付けを決定する式の例としては、図４９（ｄ）に示すように、第１の対応エッジ点候補と基点との距離をｄ1、第２の対応エッジ点候補と基点との距離をｄ2（ｄ1≦ｄ2）とするとき、
【０２７７】
重みＷ＝１−α（ｄ1／ｄ2）
ただし０＜α＜１
とする。上式において、対応エッジ点候補が１個の場合はＷ＝１となリ、複数の場合は小さくなる。このように、対応エッジ点候補が１個の場合、すなわち曖昧さが無いと考えられる場合の重み付けを大きくすることで、より確からしい方向への移動が期待できる。また対応エッジ点候補が２個以上あった場合は、最も近接している対応エッジ点候補を対応エッジ点としつつ、対応エッジ点と対応エッジ点候補の位置関係が、理想点を挟む場合は上記の式Ｗ＝１−α（短い方の距離）／（長い方の距離）となり、また理想点を挟んでいない場合はＷ＝１となる。このような重み付け作業及び重み付け後のセグメント移動方向の決定は、図１の演算手段６に含まれる精密位置決め手段７６を重み付け演算手段として行われる。
（スコア計算）
【０２７８】
また、最小二乗法を用いて精密位置決め計算を行う際に、類似度を表すスコアも同時に計算することができる。すなわち、対応点探索ラインに対し最小二乗法を適用し、最終の最小二乗法処理での対応点の数と基点の数の比でスコアを計算する。簡易的には、対応点の数を基点の数で除算した値を類似度と考えて、以下の式でスコアを求めることができる。
【０２７９】
【数２３】
2010067248.tif 000023
Ｓ：スコア
ｎ：対応点の数
ｍ：基点の数
【０２８０】
また、基点の理想エッジ角度と対応エッジ点のエッジ角度の類似度もスコアに反映させることもできる。この場合は、最終の最小二乗法処理での対応エッジ点のエッジ角度と、これに対応する基点のエッジ角度との差から得られる重みの合計と、基点の数との比をスコアとして計算する。具体的には、以下の式で演算できる。
【０２８１】
【数２４】
2010067248.tif 000024
Ｓ：スコア
ｎ：対応点の数
ｍ：基点の数
ω（ｘ）：ｘ＝０のとき１で、ｘが大きくなるにつれて単調減少する関数
θi：対応点のエッジ角度
θip：対応点に対応する基点の角度（基点の理想角度）
【０２８２】
ここで基点の理想エッジ角度は、例えばセグメントが線分の場合は線分の法線方向となり、対応点探索ラインと重なる。この方法では、各対応エッジ点のエッジ角度と、該対応エッジ点と対応する基点の理想エッジ角度との差が小さい程、重みが１に近づくように、逆に角度差が大きい程０に近づくように設定される。例えば、角度差が０°〜１８°の場合は０、１８°〜３６°の場合は０．１、・・・、１６２°〜１８０°なら１となるように、重みを設定する。このようにして基点毎に重みを演算し、最終的に得られた重みを平均することでスコアを演算する。
【０２８３】
図４９（ｂ）の例では、右側の対応エッジ点Ａに対して重み１、左側の対応エッジ点Ｂに対して重み「０．９」が与えられる。この結果、右側のセグメントＳＧ1に対してはパターンモデルを左側に移動させる作用が働き、逆に左側のセグメントＳＧ2に対しては、パターンモデルを右側へ移動させようとする作用が働く。よって、これらを総合すると、セグメントの左側へ移動させようとする重みは１．０、右側へ移動させようとする重みは０．９で、結果として左側に移動され、図４９（ｃ）のようになる。同様に、図４９（ｃ）の状態から再度重み付けを行い、該重み付け結果に基づく移動処理が繰り返されて、最終的な精密位置決めが確定する。このように、位置決めに際してパターンモデルを移動させる方向を、対応エッジ点候補と基点との距離に応じた重み付けで評価した上で行うことにより、相対的に確からしい方向に移動させることができ、位置決めの信頼性と安定性向上が期待できる。
（位置決め方向を考慮したセグメントの選択方法）
【０２８４】
上記のようなケースは、特に線分のセグメントが特定方向に集中して多い場合に起こり得る。図４９（ｂ）の例では、縦方向（Ｙ軸方向）のセグメントのみであり、Ｘ軸方向については正確な位置決めが期待できる反面、横方向（Ｘ軸方向）に伸びる線分のセグメントがないため、Ｙ軸方向を規定できず、この方向での位置決めを曖昧にしている。そこで、パターンモデルを構築するセグメントを選択する際に、位置決め方向を特定方向に集中させないように、言い換えるとＸ軸方向及びＹ軸方向といった、交差する関係にあるセグメントを意識的に選択することによって、安定した位置決め結果が期待できる。以下、位置決め方向に配慮したセグメントの選択方法について、図５０のフローチャートに基づいて説明する。
【０２８５】
まずステップＳ４９０１で、複数のセグメントの候補が得られた状態で、該セグメント候補を、長さ順にソートする。なお、円弧のセグメントの場合は、円弧の長さをセグメント長さとする。
【０２８６】
次にステップＳ４９０２で、最も長いセグメント候補をセグメントとして選択すると共に、これを基準セグメントに設定する。この基準セグメントの法線方向を基準角度とする。なお円弧セグメントが選択された場合は、基準角度は無効状態になる。基準角度が無効の場合は共役セグメントの選択は、角度によらずセグメント候補の長さのみで行う。
【０２８７】
さらにステップＳ４９０３で、基準セグメントに対する共役セグメントとなるセグメント候補を抽出する。ここでは、該基準角度から、所定の角度範囲、ここでは第１の角度範囲内に含まれるセグメント候補があるか、探索する。第１の角度範囲の一例を図５１（ａ）に示すと、基準セグメントの法線方向（９０°）を中心として±４５°の範囲、すなわち４５°〜１３５°の範囲、トータルで９０°の範囲に含まれるセグメント候補を抽出する。
【０２８８】
図５１（ｂ）に示すセグメント候補の例では、○を付したセグメント候補が抽出され、×を付したセグメント候補が除外される。共役セグメントとして線分セグメントが選択された場合は、基準角度はそのセグメントの法線方向になり。有効状態になる。なお、セグメントが線分でなく円弧の場合は、無条件に抽出される。円弧の場合は角度変化が大きいことが期待できるので、位置決めに有用な情報となり得るからである。また、円弧の場合、基準角度の状態は変化しない。
【０２８９】
セグメント候補が抽出された場合はステップＳ４９０４−１に進み、この内で最も長いセグメント候補をセグメントとして選択すると共に、これを該基準セグメントに対する共役セグメントに設定する。さらにステップＳ４９０５で、選択済みのセグメント数が規定数に達したかどうかを判定し、達している場合は処理を終了し、未だの場合はステップＳ４９０６に進み、共役セグメントを新たに基準セグメントに設定し直した後、ステップＳ４９０３に戻って処理を繰り返す。なお、共役セグメントに円弧セグメントが選択された場合、該円弧セグメントを基準セグメントとする場合の共役セグメントの選択は、基準角度が無効状態の場合は上述の通り角度によらず長さのみで選択されることになり、有効の場合は前述したしょりと同じ処理を行って共役セグメントの抽出が行われる。
【０２９０】
一方、ステップＳ４９０３で、第１の角度範囲内に含まれるセグメント候補が存在しない場合はステップＳ４９０４−２に進み、第１の角度範囲内よりも範囲を広げた第２の角度範囲内に含まれるセグメント候補が無いか、同様に探索する。第２の角度範囲内の例としては、図５１（ａ）の例では第１の角度範囲よりも±５°広げた４０°〜１４０°の範囲としている。ここでセグメント候補が発見された場合はステップＳ４９０４−１にジャンプし、上記と同様最も長いセグメントを選択して共役セグメントに設定する。
【０２９１】
第２の角度範囲内でも発見されない場合は、さらにステップＳ４９０４−３で、第２の角度範囲内よりもさらに範囲を広げた第３の角度範囲内に含まれるセグメント候補が無いか、同様に探索する。第２の角度範囲内の例としては、図５１（ａ）の例では第２の角度範囲よりもさらに±５°広げた３５°〜１４５°の範囲としている。ここでセグメント候補が発見された場合は同様にステップＳ４９０４−１にジャンプし、最も長いセグメントを選択して共役セグメントに設定する。発見されない場合は、ステップＳ４９０２に戻り、セグメント候補中から最も長いセグメントを基準セグメントに選択し直す。なお、角度範囲の数値や、角度範囲の際設定の回数等は適宜変更でき、例えばステップＳ４９０４−３でセグメントが発見されない場合は、さらに角度範囲を広げた探索を行ってもいいし、逆にステップＳ４９０４−３を省略し、ステップＳ４９０４−２でセグメントが発見されない場合に、直ちにステップＳ４９０２に戻って基準セグメントを再設定することもできる。
【０２９２】
このようにして、基準セグメントに対して、直交方向に近い共役セグメントを選択する作業を繰り返し、結果として角度が分散したセグメントが選択されるので位置決めの安定性を向上できる。このようなセグメントの選択はセグメント作成手段６８のセグメント選択手段６７で行われる。
（パターン特徴選択機能）
【０２９３】
さらに、サーチ対象物から得られるパターンの特徴に応じて、パターンモデルを構成するセグメントの選択基準を変更可能なパターン特徴選択機能を備えることもできる。具体的には、図６７に示すような登録画像において特に有効である。図６７の登録画像では、碁盤目状の枠の中に異なる文字や数字が表示されている。このような画像中に、パターンウィンドウＰＷを設定すると、作成されるパターンモデルは、図６７に示すように枠の部分に多くのセグメントＳＧWが設定され、逆に枠内の文字にはセグメントＳＧMがあまり設定されなくなる。このようなパターンモデルでは、枠の部分のみで位置決めが行われる結果、枠内の文字が無視され、あるいは重視されないこととなり、認識が困難となって、枠単位で位置がずれてしまう等、位置決めに失敗する虞があった。
【０２９４】
この原因は、セグメントの選択基準にある。すなわち、従来の考え方では、ノイズ成分を排除すると共に、より鮮明に検出されたエッジ点を重視することで位置決め精度が向上するとの観点から、長いセグメントを優先的に選択することが行われていた。なぜなら、短い輪郭はノイズの成分が多いと考えられ、逆に長い線分ほど正しくエッジ情報を抽出しているとの推測に基づいて、長い線分から自動的に選択するように設定されていた。いいかえると、短い線分を優先して選択可能とした画像処理方法等は、従来存在しなかった。このため図６７のような例では、直線で囲まれた枠部分はエッジ検出が比較的容易で鮮明になる傾向があるため、枠部分に生成されたセグメントが選択されやすくなり、上述のような位置決めの失敗を生じていた。特に粗サーチにおいては、簡易的な検索であることから抽出されたエッジやチェーン、セグメント等の輪郭情報をすべて使用せず、一部の輪郭のみを選択するため、優先的に選択される輪郭が正確な位置決めに資するものでなかった場合には、このような誤検出の問題が生じる。
【０２９５】
これに対し本実施の形態では、逆に短い輪郭から昇順に選択可能な機能を設けることで、登録画像に応じた適切なサーチ結果を得られるようにしたものである。またノイズ成分については、閾値を設定して所定長さ以下の線分を排除することにより実現している。この結果、ノイズ成分は有効に排除しつつ、かつ信頼性の高いサーチ結果を得ることができる。
（輪郭の長さ順でソート）
【０２９６】
次に、このような短い輪郭を選択する方法を２つ説明する。まず、輪郭を長さ順にソートし、短いものから所定数選択する方法について、図６８のユーザインターフェース画面に基づいて説明する。図６８は、パターンモデルを用いてサーチ対象画像中から登録画像に類似する部分をサーチする画像処理プログラムにおいて、登録画像のパターンモデルを構築する輪郭を適切に選択するためのパターン特徴選択機能の設定画面２００のユーザインターフェースを示すイメージ図である。この画面では、設定項目としてエッジ強度上限８１、エッジ強度下限８２、輪郭長下限８３、輪郭選択本数８４、輪郭登録順序８５のそれぞれについて、ユーザが粗サーチと精密位置決めの各々に対して設定を行うことができる。この内、パターン特徴選択機能に関する項目は、輪郭長下限８３、輪郭選択本数８４、輪郭登録順序８５となる。
【０２９７】
エッジ強度上限８１及びエッジ強度下限８２では、エッジとして検出するための範囲を規定しており、エッジ強度が上限値より高い、あるいは下限値よりも低いものについては排除するようフィルタリング条件を指定する。
（輪郭長下限設定手段）
【０２９８】
輪郭長下限８３は、輪郭として検出するための下限値を設定する輪郭長下限設定手段として機能する。すなわち、輪郭長下限８３で規定した下限値よりも長さが短い輪郭を、長さフィルタでフィルタリングする。これにより、短い輪郭として表れたノイズを排除できる。またこの値をユーザが調整可能とすることで、フィルタリングの強度を使用環境や用途に応じて適宜調整できる。また、環境によっては、輪郭長下限を固定値としてもよい。
（選択数決定手段）
【０２９９】
輪郭選択本数８４は、選択される輪郭の本数を規定する選択数決定手段として機能する。パターンモデルとして使用する輪郭の本数の上限を規定することで、パターンモデルを簡素化して処理量を低減し、サーチ時間の短縮化が図られる。また、選択本数を多くすると、処理量が多くなる反面、より高精度なサーチ結果が期待できる。なお、輪郭選択本数を固定値（例えば５０本）とすることで、上述の通り設定作業の簡素化を図ることもできる。
（選択順序決定手段）
【０３００】
輪郭登録順序８５は、輪郭の選択順序を、輪郭の長さの昇順と降順とに切り替え可能な選択順序決定手段として機能する。これにより、画像処理の対象となる画像に応じて、長さの昇順又は降順の適切な選択方法に設定して、より柔軟で高精度な画像処理が可能となる。
【０３０１】
以上の設定項目を設定することで、複数の輪郭の内から、ノイズに近いような極短い輪郭をフィルタリングすると共に、長さの短いものから順に選択可能として、ノイズ成分を有効に排除しつつ、位置決めの精度を左右するセグメントを適切に選択して効果的なパターンモデルを構築できる。
【０３０２】
例えば、図６９に示すような碁盤目状の枠の中に異なる文字や数字が表示されている登録画像に対して、パターンウィンドウＰＷを設定してパターンモデルを構成するセグメントを選択する例を考える。図７０に示すような設定の場合は、輪郭登録順序８５が「長さ降順」、すなわち長いものから短いものへと順に選択するよう設定されているため、図６９のように枠の部分のセグメントＳＧWが多く選択されてしまい、識別に重要となる文字や数字の部分のセグメントＳＧMの選択が少なく、このままでは位置決めの精度が期待できない。
【０３０３】
これに対し、図７１に示すように輪郭登録順序８５を「長さ昇順」、すなわち短いものから長いものへと順に選択するよう設定を変更することで、図７２のように枠内の文字や数字のセグメントＳＧMが多く選択されるようになり、このような登録画像に適した輪郭情報を備えるパターンモデルを構築できる。
【０３０４】
なお図６８の例では、各設定項目を粗サーチと精密位置決めの各々で個別に設定可能としているが、いずれか一方のみで設定可能とすることもできるし、また特定の項目については画像処理プログラムあるいは画像処理装置側で規定し、ユーザによる調整を禁止する構成としてもよい。特に操作に詳しくないユーザでも簡便に利用できるよう、設定項目を少なくすることで、操作性を向上できる。
【０３０５】
また輪郭としては、セグメントの他、チェーン等他の輪郭情報も利用できる。例えば、チェーン作成手段６３で得られたチェーンを、線分や円弧のセグメントに近似することなく、そのまま輪郭情報として利用する場合に、該チェーンの選択基準に、上述の通り短いチェーンから選択したり、選択の順序を長さの昇順、降順に切り替え可能としたり、所定の閾値よりも短いチェーンや長いチェーンを排除したりといった手法が適用でき、これによっても同様の作用効果を得ることができる。次に、図７３、図７４のフローチャートに基づいて、輪郭の長さ順でソートする具体的な手順を説明する。
【０３０６】
まずセグメントの長さを用いてソートする場合について、図７３に基づき説明する。最初に輪郭を抽出する。ここではまずステップＳ７３０１で、登録画像に対してソーベルを行い、エッジ角度画像、エッジ強度画像をそれぞれ求め、次にステップＳ７３０２で、エッジ角度画像及びエッジ強度画像を用いてエッジ点の細線化を行い、輪郭点を求める。具体的には輪郭抽出手段６２のエッジ角度・エッジ強度画像作成手段６０でエッジ角度画像及びエッジ強度画像を作成した後、細線化手段６１でエッジ強度の非極大点抑制処理により、エッジ点の細線化を行う。さらにステップＳ７３０３で、チェーン作成手段６３によりチェーンを作成する。具体的にはエッジチェーン化手段６４が隣接するエッジ点同士を連結してチェーンを作成する。また必要に応じてチェーンフィルタ手段６６で、チェーンの各種特徴量でフィルタリングを行う。
【０３０７】
次にステップＳ７３０４で、セグメントを作成する。ここではセグメント作成手段６８のエッジチェーンセグメント化手段６５が、各チェーンを線分や円弧で近似したセグメントを作成する。さらにステップＳ７３０５で、短いセグメントをフィルタリングする。ここではセグメント選択手段６７が輪郭長下限設定手段として、セグメント長が下限値以下のものを排除し、ノイズ成分を除去する。
【０３０８】
最後にステップＳ７３０６で、セグメントの長さでソートして、セグメント長の短いものから順に、パターンモデルを構成するセグメントを選択する。ここではセグメント選択手段６７が、輪郭を長順にソートする輪郭ソート手段として機能し、セグメントを長さ順にソートし、さらに選択順序決定手段で規定された選択順序、ここではセグメント長の昇順、すなわち短いものから順に、選択数決定手段で規定された本数選択する。これによって、上述した図７２のような登録画像に適したパターンモデルが構築される。
【０３０９】
一方、輪郭としてセグメントを介することなく、チェーンのままで利用する例を、図７４のフローチャートに基づいて説明する。ここでは、輪郭点を抽出してチェーンを作成するまでの手順は、上記図７３と同じである。すなわち、まずステップＳ７４０１で、登録画像に対してソーベルを行い、エッジ角度画像、エッジ強度画像をそれぞれ求め、次にステップＳ７４０２で、エッジ角度画像及びエッジ強度画像を用いてエッジ点の細線化を行い、輪郭点を求め、さらにステップＳ７４０３でチェーンを作成する。
【０３１０】
そしてステップＳ７４０４で、短いチェーンをフィルタリングする。ここでは、輪郭長下限設定手段で設定された下限値に従い、チェーン作成手段６３のチェーンフィルタ手段６６が、輪郭長下限８３よりも短いチェーンを排除する。その上でステップＳ７４０５で、チェーンの長さ順にソートして、チェーン長の短いものから順に、パターンモデルを構成するチェーンを選択する。ここでも、チェーンフィルタ手段６６が輪郭ソート手段として機能し、チェーンを長さ順にソートし、さらに選択順序決定手段で規定された選択順序、ここではチェーン長の昇順に、選択数決定手段で規定された本数のチェーンを選択する。これによって、図７２のような登録画像に適したパターンモデルがチェーンで構築される。
【０３１１】
この方法であれば、一旦セグメントで近似する処理を省略できるので、その分だけ処理を簡素化できる。反面、チェーンは線分や円弧のような一定の幾何図形に近似されていないランダムな線分の連結体となるため、以降の各個の処理は複雑になる。いずれを選択するかは、登録画像がシンプルな図形であるかどうかや、エッジ点の検出精度等に応じて決定される。
（長い輪郭をフィルタリング）
【０３１２】
なお上記の例では輪郭の長さ順にソートを行っているが、ソートを行うことなく、輪郭の長いものを排除することでもパターンモデルを構築できる。以下、この方法を図７５のユーザインターフェース画面に基づいて説明する。図７５も、画像処理プログラムにおいて登録画像のパターン特徴選択機能を設定する設定画面３００のユーザインターフェースを示すイメージ図である。この画面では、設定項目としてエッジ強度上限８１、エッジ強度下限８２、輪郭長下限８３に加え、輪郭長上限８６が挙げられている。エッジ強度上限８１、エッジ強度下限８２、輪郭長下限８３については、上述した図６８と同様であるので、詳細説明を省略する。
（輪郭長上限設定手段）
【０３１３】
輪郭長上限８６は、輪郭の上限値を設定する輪郭長上限設定手段として機能する。すなわち、輪郭長上限８６で規定した上限値よりも長い輪郭をフィルタリングする。これにより、長い輪郭を意図的に排除し、短い輪郭のみを残してパターンモデルを構築できるので、結果的に短い輪郭を優先的に選択したのと同様の効果が得られる。
【０３１４】
なお、図７５の例では選択数決定手段を設けておらず、予め設定された規定値の輪郭が自動的に選択される。ただ、選択数決定手段を設けてユーザが手動で輪郭数を設定することもできる。
【０３１５】
このようにして、長さ順でソートせずとも、短い輪郭を優先的に選択したパターンモデルを構築でき、図６７のような登録画像に対しても有効なパターンサーチが実現できる。例えば、図７６に示すような設定条件では、図７７に示すように枠の部分のセグメントＳＧWが多く選択されたパターンモデルとなるが、図７８に示すように輪郭長上限８６を１００から２０に変更することで、図７９に示すように枠内の文字や数字のセグメントＳＧMを多く含んだパターンモデルを構築できる。
【０３１６】
ここで、長い輪郭をフィルタリングする手順を、図８０、図８１のフローチャートに基づいて説明する。まず図８０は、輪郭としてセグメントを用いた場合を説明している。この方法でも、上述した輪郭長でソートする場合と同様に、輪郭点を抽出してチェーンを作成する。すなわち、まずステップＳ８００１で、登録画像に対してソーベルを行い、エッジ角度画像、エッジ強度画像をそれぞれ求め、次にステップＳ８００２で、エッジ角度画像及びエッジ強度画像を用いてエッジ点の細線化を行い、輪郭点を求める。さらにステップＳ８００３でチェーンを作成し、次いでステップＳ８００４で、セグメントを作成する。
【０３１７】
最後にステップＳ８００５で、長いセグメントと短いセグメントを削除する。ここでは、セグメント選択手段６７が輪郭長下限設定手段として、セグメント長が下限値以下のものを排除することに加え、さらにセグメント選択手段６７は輪郭長上限設定手段としても機能し、輪郭長上限８６よりも長いセグメントについても削除する。この結果、ノイズ成分を除去した上で、短いセグメントを選択できるので、図７９のような場合に位置決めに有効なセグメントを含んだパターンモデルが構築される。なおセグメントの選択本数は、固定値としているが、選択数決定手段を別途設けてユーザが手動で設定可能とできることは上述の通りである。
【０３１８】
また、セグメントに代えてチェーンでセグメントを構成する例について、図８１に基づいて説明する。ここでも、輪郭点を抽出してチェーンを作成するまでの手順は、上述した図７４と同様である。すなわち、ステップＳ８１０１で登録画像にソーベルを行い、エッジ角度画像、エッジ強度画像を求め、ステップＳ８１０２でエッジ角度画像及びエッジ強度画像を用いてエッジ点の細線化を行い、輪郭点を求め、ステップＳ８１０３でチェーンを作成する。
【０３１９】
そしてステップＳ８１０４で、長いチェーンと短いチェーンを削除する。ここでは、チェーンフィルタ手段６６が輪郭長下限設定手段として、輪郭長下限値以下のチェーンを排除すると共に、輪郭長上限設定手段としても機能し、輪郭長上限８６よりも長いチェーンについても削除する。この結果、ノイズ成分を除去した上で、短いチェーンを選択できるので、図７９のような登録画像の位置決めに有効なチェーンを含めたパターンモデルを構築できる。なおチェーンの選択本数は、固定値としているが、上述の通り選択数決定手段を別途設けてユーザが手動で設定可能とできることも同様である。
（セグメントの方向を考慮したセグメント選択機能との組み合わせ）
【０３２０】
さらに、パターン特徴選択機能を、上述した位置決め方向あるいは角度を考慮したセグメント選択機能と併用することもできる。すなわち、セグメントを長さ順にソートした後、あるいは長いセグメントをフィルタリングした後、どのセグメントをパターンモデル構築のために選択するかを決定する手法として、図５０のフローチャート等で示した方法である、基準セグメントに対して、直交方向に近い共役セグメントを選択する方法を採用できる。なお、この方法はセグメントの選択に対して利用でき、チェーンについては適用しない。チェーンは線分や円弧で近似していないため、セグメントのような角度や方向を有しないためである。
【０３２１】
以下、ソートあるいはフィルタリング後に、セグメントを選択するに際してセグメントの法線方向を考慮する例を、図８２、図８３のフローチャートに基づいて説明する。まず図８２は、セグメント長でソートする例について示している。ここでも、輪郭点を抽出してチェーン、セグメントを作成し、得られたセグメントの内で短いものをフィルタリングし、ソートするまでの手順は、上述した図７３等と同様である。すなわち、まずステップＳ８２０１で、登録画像に対してソーベルを行い、エッジ角度画像、エッジ強度画像をそれぞれ求め、次にステップＳ８２０２で、エッジ角度画像及びエッジ強度画像を用いてエッジ点の細線化を行い、輪郭点を求める。さらにステップＳ８２０３でチェーンを作成し、次いでステップＳ８２０４で、セグメントを作成し、次いでステップＳ８２０５で、短いセグメントをフィルタリングする。そしてステップＳ８２０６で、フィルタリング後のセグメントを、セグメント長でソートして短い順に並べる。
【０３２２】
この状態でステップＳ８２０７で、セグメントの法線方向を考慮しつつ、セグメントの短いものから順に選択していく。ここで図８２のＳ８２０６以降の具体的な手順について、図８４のフローチャートに示す。このフローチャートは、図５０のフローチャートのほぼ同様であるが、ステップＳ８４０１において、ソートの順序をセグメント長の降順でなく、短いものから順に並べた昇順とした点、及びステップＳ８４０２において、最も短いセグメントをセグメント候補として選択し、基準セグメントにする点、並びにステップＳ８４０４−１において、最も短いセグメントをセグメント候補として選択し、共役セグメントにする点、が異なる。それ以外は図５０と同様であるので、詳細説明を省略する。
【０３２３】
この方法によれば、特に短いセグメントが位置決めに有効な登録画像に対して効果的となり、また略直交するセグメントを交互に選択することで、法線角度が交差する関係にあるセグメントを意識的に選択したパターンモデルを構築できるので、縦横方向に安定した位置決めの結果が期待できる。
【０３２４】
同様に、セグメント長の長いものをフィルタする方法に、セグメントの法線方向を考慮した例を、図８３のフローチャートに基づいて説明する。ここでも、輪郭点を抽出してチェーン、セグメントを作成し、得られたセグメントの内で短いものと長いものをフィルタリングするまでの手順は、上述した図８０等と同様である。すなわち、まずステップＳ８３０１で、登録画像に対してソーベルを行い、エッジ角度画像、エッジ強度画像をそれぞれ求め、次にステップＳ８３０２で、エッジ角度画像及びエッジ強度画像を用いてエッジ点の細線化を行い、輪郭点を求める。さらにステップＳ８３０３でチェーンを作成し、次いでステップＳ８３０４で、セグメントを作成し、次いでステップＳ８３０５で、短いセグメントと長いセグメントをフィルタリングする。この状態でステップＳ８３０６で、上記図８４と同様の方法で、セグメントの法線方向を考慮しつつセグメントの短いものから順に選択していく。この場合は、ステップＳ８３０６でセグメント長でソートする作業がどのみち必要となるため、この点からは上述した図８２の方法が効率的といえる。その他の効果としては、図８２と同様であり、基準セグメントに対して、直交方向に近い共役セグメントが選択される結果、角度が分散したセグメントがパターンモデルに選択されるので、位置決めの安定性を向上できる。
（最小二乗法の安定性向上）
【０３２５】
次に、精密位置決め工程で行われる最小二乗法の安定性を向上させる手法について説明する。最小二乗法には大別すると線形と非線型があり、この内で線形の最小二乗法においては、理論的には解を一義的に求めることができる。一方、非線形の最小二乗法では、一般には二次式までで近似するため、近似した解が正しいとは限らない。場合によっては精密位置決め工程において、粗サーチで得られた検出候補の位置よりも、精度が悪くなる方向に位置が移動、回転されることもあり得る。例えば、図８５に示す円状のような対称性の高い図形（外円の中心座標と内円の中心座標が微妙に異なる。）に対して精密位置決めを行う場合、円の中心を回転軸として回転させてもエラー値が殆ど変化しないため、本来の回転すべき方向とは逆の方向に回転することが生じ得、また、角度の変化が大きく平行移動量も大きくずれた結果となること等もある。
【０３２６】
二次式で近似した非線形の最小二乗法の一般的な解法では、エラー関数Ｅ（ｐｉ）を、最小二乗法の変数である試行パラメータの組ｐｉの近傍で、試行パラメータの２次の冪数までで近似した近似エラー関数を作成し、該近似エラー関数を使ってエラー関数が最小となるような試行パラメータの組ｐｉを見つけるという手順を踏む。
【０３２７】
このような非線形最小二乗法において、エラー値の小さい解を得るための解法として、以下の逆ヘッセ法が提案されている。
【０３２８】
近似エラー関数を求め、そのエラー関数から最小となる試行パラメータの組を求めた上で、一度に次段のより精度の高い試行パラメータの組を求める方法である。ただし、この逆ヘッセ法を用いてエラー値の小さい解を求める場合、以下のような不具合が発生する恐れがある。このことを図８６に基づいて説明する。図８６（ａ）及び図８６（ｂ）の各々において、実線はエラー関数を、破線はこのエラー関数を近似した近似エラー関数をそれぞれ示している。図８６（ａ）及び図８６（ｂ）にてエラー関数を示す曲線上に設けられるＰ１は、上述した粗サーチにて求められた位置（ｘ，ｙ，θ）を示し、このＰ１の近傍のエラー関数の値に基づいて二次関数として求められたものが、破線で示す近似エラー関数を示す破線の二次曲線である。
【０３２９】
さらに、図８６（ａ）に示すケースの場合は、逆ヘッセ法が適切に作用したケースを説明する図であり、この近似エラー関数を示す破線の二次曲線の最もエラー値の小さな位置、つまりＰ２が実線で示されるエラー関数の最もエラー値の小さい位置Ｐに近接しているため、より正確なエラー値の小さな位置Ｐ２が求められているケースを示している。
【０３３０】
一方、図８６（ｂ）に示すケースの場合は、逆ヘッセ法が不適切に作用したケースを説明する図であり、近似エラー関数を示す破線の二次曲線の最もエラー値の小さな位置、つまりＰ２が実線で示されるエラー関数の最もエラー値の小さい位置Ｐから離れた位置として求められるため、正しくないエラー値の小さな位置Ｐ２が求められているケースを示している。
【０３３１】
上記の内、図８６（ｂ）に示したケースの場合、逆ヘッセ法でそのまま解を求めようとすると、上述の通り試行パラメータの大きな変位を解としてしまうことがあり、その結果精密位置決めの精度が低下する問題があった。本願発明者は、図８６（ｂ）に示す、逆ヘッセ法が不適切に作用したケースの発生を抑制する手法として、パターンモデルに対して、移動や回転に関する制限を設ける手法を見出した。すなわち、逆ヘッセ法に基づく最小二乗法の解法として、エラー関数に新たな項を追加する。具体的には、上述した距離に関する項（第１エラー関数）に加えて、試行パラメータからの変位によってエラー値が大きくなるような項（第２エラー関数Ｅd）を追加する。これにより、極度に大きな変化が第２エラー関数Ｅdで抑制され、図８６（ａ）に示すような適切な近似が期待できる。このように精密位置決め工程において正しい方向に収束する条件を付加して、意図しない方向への回転や発散を回避し、位置決めの信頼性を向上できる。第２エラー関数は、最小二乗法の試行パラメータをＰiとするとき、Ｐi−Ｐ0iの関数となる。この結果得られるエラー関数Ｅ（Ｐ）の連立方程式の例を、次式に示す。
【０３３２】
【数２５】
2010067248.tif 000025
【０３３３】
上式において、全体のエラー関数Ｅ（Ｐ）は、各セグメントとその対応エッジ点との距離を示す第１エラー関数Ｅoと、この第１エラー関数における試行パラメータを変化させる際の該変化量を第２エラー値とし、該第２エラー値の累積値を演算する第２エラー関数Ｅdとの和で表現される。このように最小二乗法の演算において、理想の位置と一致したときに最小となる項に加えて、第２エラー関数Ｅdを追加したことで、両方の項が小さくなるような方向に解を探すこととなり、極度に大きな試行パラメータの変化が抑制されるので、精密位置決めに際して誤った方向に回転したり発散するといった事態を回避でき、処理結果が安定するという利点が得られる。
【産業上の利用可能性】
【０３３４】
本発明の画像処理におけるパターンモデルの位置決め方法、画像処理装置、画像処理プログラム及びコンピュータで読み取り可能な記録媒体は、ＦＡ分野で利用される画像処理におけるワークの座標位置や回転角度等の位置検出、外径や内径、幅等の位置計測、認識、識別、判定、検査等に好適に適用できる。例えば、ＩＣの電極のボンディングのための電極の位置決め等に利用できる。
【図面の簡単な説明】
【０３３５】
【図１】画像処理装置の一例を示すブロック図である。
【図２】パターンモデルの登録時及びこれを用いてサーチを行う運転時の動作の概要を示す模式図である。
【図３】パターンモデル登録時の動作の概要を示すフローチャートである。
【図４】実際にサーチを行う運転時の動作の概要を示すフローチャートである。
【図５】手動縮小率決定モードにおける縮小率を設定するユーザインターフェース画面を示すイメージ図である。
【図６】エッジ角度ビットの概要を示す模式図である。
【図７】エッジ角度ビット画像を生成し圧縮する様子を示す模式図である。
【図８】各パターンモデルの例を示す模式図であり、図８（ａ）は局所サーチ用パターンモデル、図８（ｂ）は大域サーチ用パターンモデル、図８（ｃ）は精密位置決め用パターンモデルを、それぞれ示している。
【図９】運転時のサーチの手順の概要を示すフローチャートである。
【図１０】運転時のサーチの概念を示す模式図である。
【図１１】パターンモデルを回転させた結果エッジ角度ビットが変化する様子を示す模式図である。
【図１２】登録時のパターンモデルの作成手順を示すフローチャートである。
【図１３】サーチ精度とサーチ時間の優先度に応じてこれらを自動設定するユーザインターフェース画面を示すイメージ図である。
【図１４】精密位置決め用パターンモデルを登録する手順を示すフローチャートである。
【図１５】運転時において、サーチ対象画像に対する前処理を行う手順を示すフローチャートである。
【図１６】対応点探索ラインが設定されたパターンモデルを示すイメージ図である。
【図１７】図１６のパターンモデルを間引いた状態を示す模式図である。
【図１８】運用時においてパターンサーチを行う手順を示すフローチャートである。
【図１９】図１９（ａ）はサーチ対象画像の一例、図１９（ｂ）は図６（ａ）の登録画像と同じ倍率に縮小した縮小サーチ対象画像を示すイメージ図である。
【図２０】運用時におけるパターンサーチの手順を示すフローチャートである。
【図２１】対応エッジ点を求める対応エッジ点探索処理を示す模式図である。
【図２２】エッジ位置の波打現象を説明する模式図である。
【図２３】対応点探索ラインの選択が困難な可能性のある登録画像の一例を示す模式図である。
【図２４】図２３のパターンに対して対応点探索ラインを自動設定した状態を示す模式図である。
【図２５】図２４から対応点探索ラインをフィルタリングした結果を示す模式図である。
【図２６】対応点探索ラインフィルタ処理の手順を示すフローチャートである。
【図２７】基点からの長さが等しい対応点探索ラインを設定した状態を示すイメージ図である。
【図２８】基点からの長さが異なる対応点探索ラインを設定した状態を示すイメージ図である。
【図２９】対応エッジ点の座標を求める手順を説明する模式図である。
【図３０】画素ａ〜ｄの４画素で構成されたエッジ角度画像を示す模式図である。
【図３１】エッジ角度ビットを定義するエッジ角度区分を示す模式図である。
【図３２】図３０のエッジ角度画像を変換したエッジ角度ビット画像を示す模式図である。
【図３３】図３２のエッジ角度ビット画像を縮小したエッジ角度ビット縮小画像を示す模式図である。
【図３４】元のエッジ角度ビット画像を２×２画素単位で縮小する様子を説明する模式図である。
【図３５】図３４の縮小処理後に膨張を行う様子を説明する模式図である。
【図３６】元のエッジ角度ビット画像を１／２に縮小する様子を説明する模式図である。
【図３７】元のエッジ角度ビット画像を１／３に縮小する様子を説明する模式図である。
【図３８】並列処理前のパターンモデルを示す概念図である。
【図３９】並列処理後のパターンモデルを示す概念図である。
【図４０】パターンモデル登録のデータを示す概念図である。
【図４１】一部を切り欠いた円形を円弧セグメントと線分セグメントで表現したパターンモデルの一例を示すイメージ図である。
【図４２】入力画像に対して図４１のパターンモデルを用いて粗サーチを行い、ある程度の位置決めがなされた状態を示すイメージ図である。
【図４３】図４２の状態から、点と円弧の距離をエラー関数とした最小二乗法を適用して精密位置決めを行った状態を示すイメージ図である。
【図４４】図４１のパターンモデルに対して対応点探索ライン生成処理を行った例を示すイメージ図である。
【図４５】図４４のパターンモデルで、サーチ対象画像に対して粗サーチを行い、決定された位置及び姿勢でパターンモデルを重ねた状態を示すイメージ図である。
【図４６】エッジ強度ＥM、エッジ角度θEを有するエッジベクトル（Ｅx，Ｅy）を示す模式図である。
【図４７】円形状ワークに対して粗サーチを行い、ある程度の位置決めが終了した状態を示す概念図である。
【図４８】図４７から精密位置決めを行ってパターンモデルをサーチ対象画像に重ねようとした状態を示す概念図である。
【図４９】対応エッジ点候補が複数ある場合の重み付け処理を説明する模式図である。
【図５０】位置決め方向に考慮したセグメントの選択手順を示すフローチャートである。
【図５１】図５０において角度範囲の設定を更新する様子を説明する模式図である。
【図５２】飽和加算を用いた縮小処理の一例を示す模式図であり、図５２（ａ）は各ピクセルがエッジ角度を有するエッジ角度画像、図５２（ｂ）は各ピクセルのエッジ角度ビットデータを８ビットで表現するエッジ角度区分を示す模式図を、それぞれ示している。
【図５３】二値画像の一例を示すイメージ図である。
【図５４】図５３の画素値を示すグラフである。
【図５５】鮮鋭度の高い画像のエッジの強度変化を示すグラフである。
【図５６】不鮮明な画像の画素値を示すグラフである。
【図５７】鮮鋭度の低い画像のエッジの強度変化を示すグラフである。
【図５８】特許文献２に係るサブピクセル座標の計算方法を示す模式図である。
【図５９】エッジ強度の誤差とサブピクセル位置との関係を示すグラフである。
【図６０】エッジ点の鮮鋭度に基づき画像データ縮小率を決定する手順を示すフローチャートである。
【図６１】エッジのモデル関数を示すグラフである。
【図６２】画像データ縮小率を用いた登録時の動作を示すフローチャートである。
【図６３】画像データ縮小率を用いた運転時の動作を示すフローチャートである。
【図６４】近接する３点Ｂ、Ｃ、Ｆのエッジ強度を示す模式図である。
【図６５】近傍エッジ点を用いて対応エッジ点の座標を求める手順を示す模式図である。
【図６６】図６５の対応エッジ点の座標を求める手順を示すフローチャートである。
【図６７】枠の中に文字が表示された対象画像にパターンモデルを設定する様子を示すイメージ図である。
【図６８】画像処理プログラムにおいて長さ順にソートするパターン特徴選択機能を設定するユーザインターフェース画面を示すイメージ図である。
【図６９】碁盤目状の枠の中に異なる文字や数字が表示されている登録画像においてパターンモデルとして選択されたセグメントを示すイメージ図である。
【図７０】図６８のユーザインターフェース画面で輪郭登録順序を「長さ降順」に設定した様子を示すイメージ図である。
【図７１】図７０のユーザインターフェース画面で輪郭登録順序を「長さ昇順」に設定した様子を示すイメージ図である。
【図７２】図６９の登録画像において図７１の設定条件でセグメントが選択された状態を示すイメージ図である。
【図７３】セグメントの長さ順でソートする手順を示すフローチャートである。
【図７４】チェーンの長さ順でソートする手順を示すフローチャートである。
【図７５】画像処理プログラムにおいて長い輪郭をフィルタリングするパターン特徴選択機能を設定するユーザインターフェース画面を示すイメージ図である。
【図７６】図７５のユーザインターフェース画面で輪郭長上限を高めに設定した様子を示すイメージ図である。
【図７７】図６９の登録画像において図７６の設定条件でセグメントが選択された状態を示すイメージ図である。
【図７８】図７５のユーザインターフェース画面で輪郭長上限を低めに設定した様子を示すイメージ図である。
【図７９】図６９の登録画像において図７８の設定条件でセグメントが選択された状態を示すイメージ図である。
【図８０】長いセグメントをフィルタリングする手順を示すフローチャートである。
【図８１】長いチェーンをフィルタリングする手順を示すフローチャートである。
【図８２】セグメント長でソート後にセグメントを選択する手順を示すフローチャートである。
【図８３】フィルタリング後にセグメントを選択する手順を示すフローチャートである。
【図８４】セグメントの法線方向を考慮したセグメントの選択手順を示すフローチャートである。
【図８５】対称性の高い図形に対して精密位置決めを行う例を示す模式図である。
【図８６】逆ヘッセ法でエラー関数を近似する様子を示す模式図である。
【図８７】ピラミッドサーチの概念を示す模式図である。
【符号の説明】
【０３３６】
１００…画像処理装置
１００Ａ…画像処理装置本体
２００、３００…画像処理プログラムの設定画面
１…画像入力手段
２…操作手段
３…表示手段
４…記憶手段
５…出力手段
６…演算手段
６０…エッジ角度・エッジ強度画像作成手段
６１…細線化手段
６２…輪郭抽出手段
６３…チェーン作成手段
６４…エッジチェーン化手段
６５…エッジチェーンセグメント化手段
６６…チェーンフィルタ手段
６７…セグメント選択手段
６８…セグメント作成手段
６９…エッジ角度ビット画像作成手段
７０…パターンモデル構成手段
７１…粗サーチ手段
７６…精密位置決め手段
７７…画像縮小手段
７８…エッジ角度ビット画像縮小手段
８１…エッジ強度上限
８２…エッジ強度下限
８３…輪郭長下限
８４…輪郭選択本数
８５…輪郭登録順序
８６…輪郭長上限
ＲＰＭ…縮小パターンウィンドウ
ＲＯＩ…縮小サーチ対象画像
ＥＢ…エッジ角度ビット画像
ＲＥＢ…エッジ角度ビット縮小画像
ＥＡＢＲ…縮小画像
ＫＴ…基点
ＴＬ、ＴＴＬ1、ＴＴＬ2…対応点探索ライン
ＴＴ…対応エッジ点
ａ、ｂ、ｃ、ｄ…頂点
ｅ…仮対応エッジ点
ｆ…ペア点
ＴＴA、ＴＴB、ＴＴC…対応エッジ点候補
ＲＩ…登録画像
ＰＷ…パターンウインドウ
ＰＭ…パターンモデル
ＯＩ…サーチ対象画像
ＫＴ1、ＫＴ2…基点
ＳＧ1、ＳＧ2、ＳＧW、ＳＧM…セグメント
ｄ1…第１の対応エッジ点候補と基点との距離
ｄ2…第２の対応エッジ点候補と基点との距離
ＥM…エッジ強度
θE…エッジ角度
ＩＥ…入力エッジ点
ＳＬ…接線
ＳＲ…領域
ＥＭｃ…注目エッジ点のエッジ強度値
ＥＭｆ…矢印での推定エッジ強度値
ＥＭｂ…丸印での推定エッジ強度値
ＥＭｆ1、ＥＭｂ1…十字方向のエッジ点の特徴量
ＥＭｆ2、ＥＭｂ2…対角方向のエッジ点の特徴量
ＥＡｃ…エッジ角度が水平方向となす角度
ＴＰ1、ＴＰ2、ＴＰ3…仮対応エッジ点のサブピクセル位置
【図１】
2010067248.tif 000028
【図２】
2010067248.tif 000029
【図３】
2010067248.tif 000030
【図４】
2010067248.tif 000031
【図６】
2010067248.tif 000032
【図７】
2010067248.tif 000033
【図８】
2010067248.tif 000034
【図９】
2010067248.tif 000035
【図１０】
2010067248.tif 000036
【図１１】
2010067248.tif 000037
【図１２】
2010067248.tif 000038
【図１４】
2010067248.tif 000039
【図１５】
2010067248.tif 000040
【図１６】
2010067248.tif 000041
【図１７】
2010067248.tif 000042
【図１８】
2010067248.tif 000043
【図２０】
2010067248.tif 000044
【図２２】
2010067248.tif 000045
【図２３】
2010067248.tif 000046
【図２４】
2010067248.tif 000047
【図２５】
2010067248.tif 000048
【図２６】
2010067248.tif 000049
【図２７】
2010067248.tif 000050
【図２８】
2010067248.tif 000051
【図２９】
2010067248.tif 000052
【図３０】
2010067248.tif 000053
【図３１】
2010067248.tif 000054
【図３２】
2010067248.tif 000055
【図３３】
2010067248.tif 000056
【図３４】
2010067248.tif 000057
【図３５】
2010067248.tif 000058
【図３６】
2010067248.tif 000059
【図３７】
2010067248.tif 000060
【図３８】
2010067248.tif 000061
【図３９】
2010067248.tif 000062
【図４０】
2010067248.tif 000063
【図４１】
2010067248.tif 000064
【図４２】
2010067248.tif 000065
【図４３】
2010067248.tif 000066
【図４４】
2010067248.tif 000067
【図４５】
2010067248.tif 000068
【図４６】
2010067248.tif 000069
【図４７】
2010067248.tif 000070
【図４８】
2010067248.tif 000071
【図４９】
2010067248.tif 000072
【図５０】
2010067248.tif 000073
【図５１】
2010067248.tif 000074
【図５２】
2010067248.tif 000075
【図５３】
2010067248.tif 000076
【図５４】
2010067248.tif 000077
【図５５】
2010067248.tif 000078
【図５６】
2010067248.tif 000079
【図５７】
2010067248.tif 000080
【図５８】
2010067248.tif 000081
【図５９】
2010067248.tif 000082
【図６０】
2010067248.tif 000083
【図６１】
2010067248.tif 000084
【図６２】
2010067248.tif 000085
【図６３】
2010067248.tif 000086
【図６４】
2010067248.tif 000087
【図６５】
2010067248.tif 000088
【図６６】
2010067248.tif 000089
【図６８】
2010067248.tif 000090
【図７０】
2010067248.tif 000091
【図７１】
2010067248.tif 000092
【図７３】
2010067248.tif 000093
【図７４】
2010067248.tif 000094
【図７５】
2010067248.tif 000095
【図７６】
2010067248.tif 000096
【図７８】
2010067248.tif 000097
【図８０】
2010067248.tif 000098
【図８１】
2010067248.tif 000099
【図８２】
2010067248.tif 000100
【図８３】
2010067248.tif 000101
【図８４】
2010067248.tif 000102
【図８５】
2010067248.tif 000103
【図８６】
2010067248.tif 000104
【図８７】
2010067248.tif 000105
【図５】
2010067248.tif 000106
【図１３】
2010067248.tif 000107
【図１９】
2010067248.tif 000108
【図２１】
2010067248.tif 000109
【図６７】
2010067248.tif 000110
【図６９】
2010067248.tif 000111
【図７２】
2010067248.tif 000112
【図７７】
2010067248.tif 000113
【図７９】
2010067248.tif 000114
【手続補正書】
【提出日】平成20年11月21日(2008.11.21)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０１６２
【補正方法】変更
【補正の内容】
【０１６２】
ここでは、チェーンを線分と円弧で近似したセグメントが形成される。線分のセグメントは、直線を表す式（例えばａｘ＋ｂｙ＋ｃ＝０）と端点の座標等で表現できる。一方円弧のセグメントは、中心の座標と半径、開始角度と終了角度等で表現できる。例えば（ｘ−ｘo）2＋（ｙ−ｙo）2＝ｒo2における円弧の中心座標（ｘo、ｙo）及び半径ｒoで円弧セグメントを表現する。このようにして生成した各セグメント上に、所定間隔で基点を設定する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０１８６
【補正方法】変更
【補正の内容】
【０１８６】
さらにステップＳ２００２で、精密位置決め用パターンモデルの対応点探索ラインに沿って対応エッジ点となる点を求める。対応点探索ラインは、上述の通りセグメントの法線方向に延びる所定長さの線分であり、線分の両端の一方である起点を探索開始点、終点を探索終了点とする。ここでは、まず対応点探索ラインに沿ってエッジ計算を行い、エッジベクトルを取得する。エッジ計算の手法としては、上述の通りソーベルが適宜用できる。このエッジ計算で得られたエッジベクトルから、対応点探索ライン上の各点のエッジ角度、エッジ強度、エッジ位置等を求める。なおエッジベクトルとは、エッジの強度と向きをベクトル表現したもので（Ｅx，Ｅy）のように表現することができる。例えば図４６に示すようにエッジ強度をＥM、エッジ角度をθEとすると、エッジ角度θE＝Ａｔａｎ（Ｅｙ／Ｅx）、エッジ強度ＥM＝ｓｑｒｔ（Ｅx2＋Ｅy2）で表現できる。
（対応エッジ点探索処理）
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０１９１
【補正方法】変更
【補正の内容】
【０１９１】
精密位置決めにおいては、粗サーチで得られた位置、姿勢のデータを用いて基点をサーチ対象画像に重ねる。そして、対応点探索ラインに沿ってソーベルフィルタ等のエッジ計算を行い、エッジベクトルを取得している。なおエッジベクトルは、ソーベルフィルタを適用した結果で表され、（Ｓx，Ｓy）等で表現できる。またエッジ強度ＥMは、ＥM＝√（Ｓx2＋Ｓy2）、エッジ角度θEは、θE＝Ａｔａｎ（Ｓy／Ｓx）等として表現できる。さらに、エッジベクトルから対応エッジ点上のピクセルのエッジ角度、エッジ強度と位置を求め、これらエッジベクトル、エッジ角度、エッジ強度、位置から対応エッジ点の基点を含むセグメントに対応する対応エッジ点を精密位置決め手段７６で求める。