画像マッチング方法、プログラムおよび応用装置
【課題】一般化ハフ変換が持つ処理時間・使用メモリ空間削減と精度・安定性の両立困難問題を解決する画像マッチング技術を提供する。
【解決手段】テンプレート画像と被探索画像の各々に対して、エッジ方位を利用した情報圧縮によりエッジ点群を代表する特徴点を抽出し、テンプレート画像と被探索画像の各特徴点間の相似変換パラメータ値によるパラメータ空間への投票により投票値の高い相似変換パラメータを抽出し、この相似変換パラメータにより被探索画像上へ変換された全てのテンプレートエッジ点とその近傍にある各対応エッジ点との誤差の総合値が最少となる方向に相似変換パラメータを調整し、誤差の総合値が基準値を下回るように調整できた相似変換パラメータの中から所定の基準により最終の相似変換パラメータとこれに対応する最終探索目標画像を特定する。
【解決手段】テンプレート画像と被探索画像の各々に対して、エッジ方位を利用した情報圧縮によりエッジ点群を代表する特徴点を抽出し、テンプレート画像と被探索画像の各特徴点間の相似変換パラメータ値によるパラメータ空間への投票により投票値の高い相似変換パラメータを抽出し、この相似変換パラメータにより被探索画像上へ変換された全てのテンプレートエッジ点とその近傍にある各対応エッジ点との誤差の総合値が最少となる方向に相似変換パラメータを調整し、誤差の総合値が基準値を下回るように調整できた相似変換パラメータの中から所定の基準により最終の相似変換パラメータとこれに対応する最終探索目標画像を特定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テンプレートの画像に相似な画像を被探索画像から探し出すための画像マッチング技術に関する。
【背景技術】
【０００２】
テンプレートの画像（以降、「テンプレート」ともいう）と探索目標画像の輪郭情報を用いたマッチング技術として、一般化ハフ変換という手法が知られており、将来の有用な技術と考えられる。この手法は、輪郭を細分化したエッジ点という構成要素を用いて演算を行なう。テンプレート画像および探索目標画像の存在する画像（以降、被探索画像ともいう）の双方からエッジ点を抽出し、それらの組み合わせから算出される相似変換パラメータ値を投票空間と呼ばれるメモリ配列に記録（投票）する。
この操作を、テンプレート画像および被探索画像の全てのエッジ点の組み合わせについて行ない、投票値を評価することにより、最も相似に近い被探索画像に対応する相似変換パラメータ値を得ることができる。
【０００３】
しかしながら、一般化ハフ変換には以下の問題点が存在し、一般化ハフ変換を利用した画像マッチングの世界においては、市場（例えば、ＦＡ市場）が要求する処理スピード、マッチング精度、マッチング安定性、および、さらに広い応用を図ろうとすれば、手法の汎用性等を兼ね備えた技術が必要となっている。しかしながら、この要求に応えることができる技術は、出願者の知りうる限りでは存在しない。
（１）計算量の多さ
一般的に、テンプレート画像、被探索画像の全てから得られるエッジ点は膨大であり、テンプレート画像のエッジ点の数をM、被探索画像の全てから得られるエッジ点の数をNとした場合はM×Nの計算量となる。
計算量を削減するために、対象物の形状に依存した処理（コーナー抽出など）が多く使われるが、曲線への対応が難しい、汚れや隠れに弱いなどの欠点があり、汎用的なマッチング手法を構築する妨げとなる。
（２）メモリ使用量の多さ
相似変換を扱う場合、推定するパラメータは4つとなり投票空間は4次元空間が必要である。標準的な画像サイズ（６４０×４８０）でも、テンプレート画像に対する被探索画像の相対角度差の最大値を３６０度、テンプレート画像に対する被探索画像のスケールの比が１に対して±２０％とし、それぞれ１画素、１度および１％刻みで投票するとすれば、６４０×４８０×３６０×４０＝４Ｇ（Ｂｙｔｅ）の空間が必要であり、このままでは実用性が乏しい。
（３）安定性
エッジ点という特徴量は、外乱（ノイズ、照明変動等）の影響、対象物自体の微小変化の影響により誤差が含まれる。この誤差は投票空間への投票精度に影響するため、実際のカメラから取得した映像を処理する際に、正しい回答が得られないことが多い。これを回避するために投票空間を圧縮する方法が知られているが、圧縮した分精度が低下する。
また、誤差を加味した投票方法(重複投票)もいくつか提案されているが、計算量の更なる増大を招くと共に、偽りの回答を生み出す可能性がある。
（４）精度の確保
上記の安定性の項にも記載したが、一般化ハフ変換において安定性と精度を共存させることは難しい。よって、何らかの新しい技術によるか、または他の技術と組み合わせることにより精度を確保しなくてはならない。
【特許文献１】特開２００７−１２８３７４
【非特許文献１】Hough変換に基づく図形検出法の新展開、和田俊和 外１名、情報処理第３６巻 第３号、社団法人情報処理学会、１９９５．０３、ｐ．２５３〜２６３
【非特許文献２】Hough変換の諸課題と新しいパターン計測 基礎編、森本正志 外１名、計測と制御 第３５巻 第１１号、１９９６．１１、ｐ．８６９〜８７７
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明が解決しようとする課題は、以下の４つの課題を解決し、画像マッチング技術において一般化ハフ変換が持つ問題点を解決する新たな視点からのパターンマッチング技術を提供することである。
（１）メモリ使用量およびメモリアクセス回数削減による処理速度の向上
（２）精度を確保するための新しい技術の実現
（３）安定性を改善するための投票方法、投票空間の圧縮の実現
（４）汎用性、安定性、汚れ、隠蔽への耐性を損なわないエッジ点圧縮手法の実現
【課題を解決するための手段】
【０００５】
本発明の課題を解決する手段は、以下に記載するものである。
【０００６】
テンプレート画像と被探索画像の双方に対して輪郭を構成する画素（以降、エッジ点ともいう）を抽出するエッジ点抽出ステップと、
テンプレート画像と被探索画像とを選択された圧縮率に基づいて情報圧縮することによってそれぞれの画像の画素群をグループ化（当該グループをセルという）し、テンプレート画像と被探索画像のそれぞれに対して、セル各々において、所定の方法で計測されるエッジ方位が所定の角度範囲にあるエッジ点群を１つのクラスとするクラスタリングを行い、所定の処理基準により当該クラスを代表するエッジ点を選定し、これを特徴点とするエッジ点圧縮を行う特徴点抽出ステップと、
テンプレート画像の特徴点（以降、テンプレート特徴点ともいう）の座標（以降、テンプレート座標ともいう）を基準にして被探索画像の特徴点（被探索物特徴点ともいう）の座標（以降、被探索物座標ともいう）の相似変換パラメータを計算し、その計算値に従って相似変換パラメータによるパラメータ空間（以降、投票空間ともいう）上の投票領域（以降、投票セルともいう）に投票することを、テンプレート座標のそれぞれと被探索物座標のそれぞれとの全ての組合せに対して実施した後、所定の閾値（以降、閾値１ともいう）を超える投票値を得た投票セルに対応する相似変換パラメータを全て抽出する対応点探索ステップ１と、
対応点探索ステップ１により抽出された相似変換パラメータを使用してテンプレート画像の各エッジ点（以降、テンプレートエッジ点ともいう）を前記被探索画像上に変換し、これらの変換されたエッジ点（以降、変換エッジ点ともいう）の所定の近傍内で当該変換エッジ点から最小の距離にある被探索画像のエッジ点（以降、対応エッジ点ともいう）を探し出し、全ての変換エッジ点に対する対応エッジ点との距離の総合値（以降、総合誤差値ともいう）を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを前記対応点探索ステップ１で抽出された相似変換パラメータとみなして上記本ステップの一連の処理手順を繰り返すことによって、当該総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行い、調整された相似変換パラメータの中から所定の基準を満足する相似変換パラメータを選び出す対応点探索ステップ２と、
対応点探索ステップ２で調整され選び出された各々の相似変換パラメータに対応し、総合誤差値の計算の対象となった被探索画像のエッジ点群を持つ画像パターン（以降、探索目標画像最終候補ともいう）の中から、マッチング探索の探索目標画像を特定するための相似変換パラメータを所定の処理により決定する被探索画像識別ステップと
により画像マッチングを行う。
上記テンプレート画像については、常識的には、ノイズを除いて、テンプレートが１個のみ存在するか、テンプレートが複数の所定の位置に配置された組合せテンプレートからなる場合にはその組合せテンプレートのみが存在する画像と考えてよい。
また、対応点探索ステップ２における所定の方法は、テンプレートエッジ点群をこのときの対応エッジ点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレートエッジ点群とこの対応エッジ点群を使って最小二乗法により算出する方法が好ましい。
【０００７】
特徴点抽出ステップにおいて、
テンプレート画像と被探索画像のそれぞれに対して、輪郭上の全ての画素を対象としてエッジ点を抽出するようにする。
また、輪郭上の相並ぶ複数画素毎を対象として所定の基準で１個のエッジ点（画素単位）を抽出するようにしてもよい。
更に、特徴点抽出ステップにおける所定の処理基準として、
クラスを代表するエッジ点を、当該エッジ点が存在するクラスの中で最初にエッジ方位が計測されたエッジ点とすることができる。
また、クラスを代表するエッジ点を、当該エッジ点が存在するクラスに属するエッジ点のエッジ方位の平均値に最も近いエッジ方位を持つエッジ点とすることもできる。
また、クラスを代表するエッジ点を、１つのクラスを構成するエッジ点群の重心に最も近いエッジ点とすることもできる。
【０００８】
相似変換パラメータが、以下の４個のパラメータのセット、
テンプレート座標に対する被探索物座標のＸ方向並進値（Tx）
【数１】
テンプレート座標に対する被探索物座標のＹ方向並進値（Ty）
【数２】
テンプレート座標に対する被探索物座標の回転値（Tq）
【数３】
テンプレート画像に対する被探索画像のスケール値（Ts）
ここに
MstX ：テンプレート画像の特徴点のＸ座標
MstY ：テンプレート画像の特徴点のＹ座標
Mstθ ：テンプレート画像の特徴点の方位
ObjX ：MstXに対応するべき被探索画像の特徴点のＸ座標
ObjY ：MstYに対応するべき被探索画像の特徴点のＹ座標
Objθ ：Mstθに対応するべき被探索画像の特徴点の方位
【数４】
【数５】
から構成されるようにする。
【０００９】
対応点探索ステップ１における相似変換パラメータに対応する投票空間への投票において、テンプレート座標に対する被探索物座標の回転値（Tq）に所定の範囲の誤差を加味した範囲の中で、とびとびに選択されるθ方向の誤差（Δθ）を加味した投票空間への重複投票を追加的に実施することが対応点探索ステップ１の安定性の観点から好ましい。
【００１０】
重複投票が、θ方向の誤差（Δθ）に依存したウエイトによる重複投票であることも同様に好ましい方法である。
【００１１】
対応点探索ステップ２における総合誤差値を、各々の変換エッジ点に対する対応エッジ点との距離の二乗和とすることができる。もちろん、距離の総和としてもかまわない。
【００１２】
対応点探索ステップ２が、エッジ点、テンプレートエッジ点、変換エッジ点および対応エッジ点をそれぞれ、特徴点、テンプレート特徴点、変換特徴点および対応特徴点と置き換えた対応点探索ステップ２の処理方法に従って、対応点探索ステップ１で抽出された相似変換パラメータを使用して全ての変換特徴点に対応する対応特徴点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな抽出された相似変換パラメータとして上記本ステップの一連の処理手順を繰り返すことによって、総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行う粗調整ステップと、
粗調整ステップで粗調整された相似変換パラメータ毎に、対応点探索ステップ２の処理方法に従って、当該相似変換パラメータを使用して全ての変換エッジ点に対する対応エッジ点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな当該粗調整された相似変換パラメータとして上記一連の処理手順を繰り返すことによって、総合誤差値が所定の他の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を行なう精調整ステップとからなるようにすることができる。
ここで、上記粗調整ステップにおける所定の方法は、テンプレート特徴点群をこのときの対応特徴点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレート特徴点群とこの対応特徴点群を使って最小二乗法により算出する方法が好ましい。
また、上記精調整ステップにおける所定の方法は、テンプレートエッジ点群をこのときの対応エッジ点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレートエッジ点群とこの対応エッジ点群を使って最小二乗法により算出する方法が好ましい。
【００１３】
対応点探索ステップ２を、エッジ点、テンプレートエッジ点、変換エッジ点および対応エッジ点をそれぞれ、特徴点、テンプレート特徴点、変換特徴点および対応特徴点と置き換えた対応点探索ステップ２の処理方法に従って、対応点探索ステップ１で抽出された相似変換パラメータを使用して全ての変換特徴点に対応する対応特徴点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな抽出された相似変換パラメータとして上記本ステップの一連の処理手順を繰り返すことによって、総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行うことで済ますようにすることもできる。
ここで、上記粗調整ステップにおける所定の方法は、テンプレート特徴点群をこのときの対応特徴点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレート特徴点群とこの対応特徴点群を使って最小二乗法により算出する方法が好ましい。
【００１４】
被探索画像識別ステップにおける所定の処理として、対応点探索ステップ２で調整された各々の相似変換パラメータ毎に、これを用いてテンプレートエッジ点を被探索画像上に変換し、変換されたテンプレートエッジ点各々の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値に基づいて、テンプレート画像と探索目標画像の最終候補との一致度を計算し、当該一致度の大きさに基づいて探索目標画像を特定することもできる。
一致度の計算方法の好ましい例は、当該変換されたテンプレートエッジ点の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値をテンプレートエッジ点の数により正規化する方法である。
【００１５】
被探索画像識別ステップにおける所定の処理としては、対応点探索ステップ２で調整され選び出された各々の相似変換パラメータの中から、当該調整過程における最終の総合誤差値の小ささに基づいて対応する相似変換パラメータを選定することができ、具体的には、最終の総合誤差値が最も小さいものが得られたときの相似変換パラメータを選定し、これに対応する探索目標画像の最終候補を探索目標画像として特定することができ、この処理は好ましい処理方法である。また、被探索物が同一画像内に複数ある場合等においては、相似変換パラメータの数値の違いの大きさに着目した条件設定により数値の近い相似変換パラメータのクラスタを特定し、各クラスタの中から総合誤差値が最も小さいものが得られたときの相似変換パラメータを選定することができる。
【００１６】
また、対応点探索ステップ２を、エッジ点の代わりに特徴点を使って実行する場合には、被探索画像識別ステップにおける所定の処理として、対応点探索ステップ２で調整された各々の相似変換パラメータ毎に、これを用いてテンプレートエッジ点を被探索画像上に変換し、変換されたエッジ点の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値に基づいて、テンプレート画像と探索目標画像の最終候補との一致度を計算し、当該一致度の大きさに基づいて探索目標画像を特定することももちろんできる。
この場合の一致度の好ましい例は、当該変換された特徴点の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値をテンプレート特徴点の数により正規化する方法である。
【００１７】
また、対応点探索ステップ２を、エッジ点の代わりに特徴点を使って実行する場合には、被探索画像識別ステップにおいて、対応点探索ステップ２における距離の総合値に基づいて探索目標画像を特定することもできる。
【００１８】
以上の「本発明の課題を解決する手段」で述べた画像マッチング方法に関する適切な手段の選択により、エッジ点抽出ステップと特徴点抽出ステップと対応点探索ステップ１と対応点探索ステップ２と被探索画像識別ステップとを、具備させ、上述の課題解決の手段のいずれかの組合せを実現する機能を持つコンピュータシステムにより、画像マッチング応用装置を作ることができる。
上記画像マッチング応用装置の好ましい基本的な例を具体的に示すと、
テンプレート画像と探索目標画像の存在する画像（被探索画像）の双方に対して輪郭を構成する画素（エッジ点）を抽出するエッジ点抽出ステップと、
テンプレート画像と被探索画像とを選択された圧縮率に基づいて情報圧縮することによってそれぞれの画像の画素群をグループ化（当該グループをセルという）し、テンプレート画像と被探索画像のそれぞれに対して、セル各々において、所定の方法で計測されるエッジ方位が所定の角度範囲にあるエッジ点群を１つのクラスとするクラスタリングを行い、所定の処理基準により当該クラスを代表するエッジ点を選定し、これを特徴点とするエッジ点圧縮を行う特徴点抽出ステップと、
テンプレート画像の特徴点（テンプレート特徴点）の座標（テンプレート座標）を基準にして被探索画像の特徴点（被探索物特徴点）の座標（被探索物座標）の相似変換パラメータを計算し、その計算値に従って相似変換パラメータによるパラメータ空間（投票空間）上の投票領域（投票セル）に投票することを、テンプレート座標のそれぞれと被探索物座標のそれぞれとの全ての組合せに対して実施した後、所定の閾値（閾値１）を超える投票値を得た投票セルに対応する相似変換パラメータを全て抽出する対応点探索ステップ１と、
対応点探索ステップ１により抽出された相似変換パラメータを使用してテンプレート画像の各エッジ点（テンプレートエッジ点）を前記被探索画像上に変換し、これらの変換されたエッジ点（変換エッジ点）の所定の近傍内で当該変換エッジ点から最小の距離にある被探索画像のエッジ点（対応エッジ点）を探し出し、全ての変換エッジ点に対する対応エッジ点との距離の総合値（総合誤差値）を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを前記対応点探索ステップ１で抽出された相似変換パラメータとみなして上記本ステップの一連の処理手順を繰り返すことによって、当該総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数まで繰返すまで当該相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行い、調整された相似変換パラメータの中から所定の基準を満足する相似変換パラメータを選び出す対応点探索ステップ２と、
対応点探索ステップ２で調整され選び出された各々の相似変換パラメータに対応し、総合誤差値の計算の対象となった被探索画像のエッジ点群を持つ画像パターン（探索目標画像最終候補）の中から、マッチング探索の探索目標画像を特定するための相似変換パラメータを所定の処理により決定する被探索画像識別ステップと
を具備し、上述の課題解決の手段のいずれかを実現する機能を持つ画像マッチングシステムとなる。
上記対応点探索ステップ２において、「エッジ点」を「特徴点」と置き換えることもできる。
【００１９】
当然のことながら、上記システムの中に搭載され、上記機能を実現するコンピュータプログラムも、本発明の権利範囲となる。
【発明の効果】
【００２０】
マッチング探索の最終探索目標画像の特定・確認のために当該最終探索目標画像に対応する相似変換パラメータの修正を行いながらテンプレート画像との一致度の究極値を確認する従来にない処理プロセス（パラメータ推定プロセス）を導入することで、安定性を得るために採る投票空間の圧縮による相似変換パラメータの精度ダウンの影響を相殺して、最終の実用上充分な安定性と精度を確保することができた。
更に、投票空間の圧縮によって引き起こされるθ方向の投票の不安定性を排除できる新たな投票方法を追加することにより、安定性の一層の向上に寄与できた。
更にまた、精度と安定性の共存困難の問題で一般化ハフ変換では実現不可能であった投票空間の圧縮が可能となったことにより、従来の一般化ハフ変換を使用する画像探索に比較して、使用するコンピュータ上の画像メモリ領域の大幅な削減が可能となり、またこれに関連して計算量の削減が可能になったことによるマッチング画像探索処理速度の向上も実現する等の付随効果が得られた。
これらにより、一般化ハフ変換が本質的に持つ問題点を解決するパターンマッチング技術を提供することができた。
【発明を実施するための最良の形態】
【００２１】
発明を実施するための最良の形態は、図１に実施例として示すように、大きく分けて５つの処理ステップを具備する。この内容について以下に説明する。
【００２２】
１．エッジ点抽出ステップ（図１のステップＳ１１０）
テンプレート画像と被探索画像の双方について、輪郭を構成する画素（以降、「エッジ点」ともいう）を抽出する。
エッジを抽出する方法は、従来から使われている技術であり、
（１）濃淡画像に対してＸ方向およびＹ方向の微分フィルタ処理を行うことによってＸ方向およびＹ方向濃度微分画像を得る。
（２）それぞれの濃度微分画像を走査することによって、微分値の山の頂上部分、および、微分値の谷の最下部分となっている画素を特定し、これを仮のエッジ位置（Ｘe，Ｙe）とする。
（３）仮のエッジ位置周辺の濃度微分波形から山の頂上部分、および、谷の最下部分を精度よく求める。エッジ方位は当該エッジ点の位置における輪郭の形状によって決まる特有の角度情報であり、本実施例では、代表的な角度情報として「当該エッジ点の位置における輪郭の接線に対する法線ベクトルの方位」を採用し、エッジ点（Ｘeij,Ｙeij）におけるエッジ方位をθijとすると、θijは、次の式から求められる。
【数６】
テンプレート画像と被探索画像の双方について、上記の方法によりエッジ位置を見出し、エッジ位置に対応する全ての画素をエッジ点としてエッジ方位と共に抽出する。
当然、エッジ位置とエッジ方位を見出す技術は他にもあり、適宜選んで使用することができる。
上の説明ではエッジ方位をエッジ点位置での輪郭の法線としているが、必ずしも輪郭の法線とする必要はなく、エッジ方位をエッジ位置での輪郭の接線方向としても良いし、その他任意に所定の基準で導き出すことができるエッジ位置での輪郭の角度としても良い。
【００２３】
２．特徴点抽出ステップ（図１のステップＳ１２０）
このステップにおいては、テンプレート画像と被探索画像の双方について、「エッジ抽出」処理によって抽出されたエッジ点に対して情報圧縮を行い、最終的に残したエッジ点を「特徴点」とする。
エッジ点の情報圧縮は、図２にその手順が示されているが、以下に図２に沿ってその詳細を説明する。
（ステップＳ２０１）
Ｘ方向およびＹ方向の圧縮レベルを指定する。（１／１、１／２、１／４、１／８、１／１６、１／３２等）
（ステップＳ２０２）
指定された圧縮レベルに従い、ＸＹ空間を情報圧縮する。具体的には、Ｘ方向およびＹ方向それぞれは指定されたそれぞれの圧縮レベルの逆数の画素が１つのセルに対応するようにセルがＸＹ空間に配置される。その圧縮されたＸＹ空間の例は、図５に示すようなもので、Ｘ方向の圧縮レベル＝１／８、Ｙ方向の圧縮レベル＝１／８のものである。破線は画素の境界を示し、実線はセルの境界を示す。
（ステップＳ２０３）
情報圧縮後のＸＹ空間の対応するセル内の対応する各画素にエッジ点をプロットする。（以降、エッジ点プロット後のＸＹ空間を「エッジマップ」ともいう。）
図６に輪郭が矩形である図形のエッジ点（黒点）をプロットしたエッジマップの１例を示す。
（ステップＳ２０４）
エッジマップ上の各セル内に複数のエッジ点がプロットされている場合は、エッジ方位を用いてクラスタリング（詳細は下記参照）を行ない、各クラスの代表点を特徴点とする。
エッジ方位を用いたクラスタリングとは、同一のセル内に存在しているエッジ点をエッジ方位の振れが所定の範囲にあるという条件で同一クラスに分類するもので、特徴点を導き出す前の処理である。
クラスタリングおよびクラスの代表点（特徴点）候補（仮のクラス代表点）を導き出す処理基準は、いかなる方向にエッジ点の有無をチェックしていくとしても、チェックされているエッジ点のエッジ方位が仮のクラス代表点のクラス方位±４５°未満のエッジ方位を持つ場合は仮のクラス代表点と同一のクラスに分類し、仮のクラス代表点のクラス方位±４５°以上のエッジ方位を持つ場合は当該チェックされているエッジ点において新しいクラスを生成し、このエッジ点を新しいクラスの仮のクラス代表点とするやり方をとる。以上の基準を、同一セル内にある全てのエッジ点に対して適用し、そのセルに含まれる各エッジ点のクラス分けを行い、各クラスから所定の処理基準によりクラス代表点（特徴点）を導き出す。
【００２４】
エッジ方位を用いたクラスタリングの手順の１例について、図６、図６ａ、および図６ｂを使いながら以下説明する。
図６ａは、図6のエッジマップ上のいくつかのセル（升目）のそれぞれに複数のエッジ点がプロットされている場合の１例を示すものであり、セル当たりのエッジ点の数は図を見やすくするために図６の場合の数とは異ならせてあるが、図6の矩形のエッジ点列部分の左上隅の部分の拡大図と考えてよい。黒点がエッジ点である。
（手順１）
エッジマップの中のエッジ点の探索は、好ましい例として、図６（詳しくは、図６ａ）の左上隅の画素から右方向に画素ラインに沿って、更に画素ラインについては上から下に走査してエッジ点があるかないか調べていく方法をとる。
上記のように画素ラインごとの走査によって最初に発見されたエッジ点は、黒点のエッジ点列の左上隅のエッジ点である。
本手順においては、そのセルにおいて最初に選択されたエッジ点をそのセルにおける最初のクラスの構成要素とし、最初にクラスの構成要素となったエッジ点を仮の当該クラス代表点とすると共に、この仮のクラス代表点の方位をクラス方位とする。
（手順２）
同一セル内で次に発見されたエッジ点は、仮のクラス代表点とされたエッジ点の右隣のエッジ点であり、このエッジ点のエッジ方位が仮のクラス代表点のクラス方位±４５°の範囲にあるか否かの判定を行う。
この場合、右隣のエッジ点は、当該範囲内にあるため直前に発見されたエッジ点と同一クラスに属し、またクラスの代表点となることもない。
（手順３）
更に右隣のエッジ点についても、同一セル内で、エッジ方位もクラス方位±４５°未満であるので、以上の３つのエッジ点が同一クラスを形成するものとし、仮の代表点をそのまま維持する。
（手順４）
このようにして、現在の走査画素ライン上のエッジ点について、右隣のセル内について上記基準と判定方法により、新しいクラスと仮のクラス代表点を決めていく。
更に、同一の走査画素ライン上のその先のセル内についても、同様の処理をしていく。
（手順５）
その下の走査ライン上の各セル内においても(手順１)から(手順４)と同様な処理をしていくが、現在の走査画素ライン上且つ同一セル内で、
（１）エッジ点が見つからなかった場合
手順６に移る。
（２）エッジ点が見つかった場合
当該エッジ点のエッジ方位をそれまでに決まっている仮の代表エッジ点（複数の場合はそれぞれの代表エッジ点）の持つクラス方位と比較し、当該クラス方位に対し±４５°未満にあるクラス方位を持つクラスがあればそのクラスに属させるし、なければ新しいクラスを作り当該エッジ点を新しいクラスの仮のクラス代表点とする。
（手順６）
当該セルについて、同一画素ラインについて先のセル全てに対して、（手順５）の処理を実施する。
（手順７）
更に現在の画素ラインが関係するセル群の最終の走査画素ラインとなるまで全ての走査画素ラインに対して（手順５）および（手順６）の処理を実施する。
（手順８）
（手順１）から（手順７）までの処理結果により、全てのセルの全てのクラス代表点（特徴点）を決定する。
この最終結果の例は、図６ｂに示されるようなものである。ここで、図６ｂの黒丸は特徴点である。
【００２５】
上記の実施例におけるクラス方位±４５°の４５°は、必ずしもこれにこだわる必要はなく、クラスを細かく分けたい場合は小さい数値（例えば、３０°）に変更することも可能であるし、クラスを更に粗く分けたい場合には大きな数値（例えば、６０°）に変更することも可能であり、被探索物の形状、精度その他の条件によって他の数値を任意に選んでかまわない。
４５°のメリットの一つは、ＦＡ等の世界において比較的多い矩形あるいは直角部分を含む外形を持ったワークが多いことから、４５°はエッジ方位が９０°異なる線分のエッジ点を異なるクラスのエッジ点として分離することが容易な最大の角度であり、クラスの数（即ち、特徴点の数）を多くの場合に最少とすることができることにある。
【００２６】
また、１つのセルのエッジ点の探索方式は、上記の実施例の方法に限定する必要はなく、他の探索方式として、例えば、同一セル内の全てのエッジ点についてその方位を記録し、同一セル内のエッジ点同士で上記「クラスタリングおよびクラスの代表点（特徴点）候補（仮のクラス代表点）を導き出す基準」による判定を行い、各エッジ点が属するクラスを決定し、所定の処理基準でクラス代表点（特徴点）を決定してもよい。所定の処理基準としては、例えば、同一クラスに属するエッジ点列が、奇数のときは中央に位置するエッジ点をクラス代表点（特徴点）として選び、偶数のときは中央に位置する２つのエッジ点の内の一つを画素ライン上あるいは画素ライン間の走査の方向を基準に選択するようにしても良い。
【００２７】
また、「クラスタリングおよびクラスの代表点（特徴点）候補（仮のクラス代表点）を導き出す処理基準」および「１つのセルのエッジ点の探索方式」についても以上の例に限ることはなく、他の処理基準あるいは方式によっても同様の効果が得られる輪郭情報の圧縮ができればよい。例えば、同一セル内の全てのエッジ点のエッジ方位を計測しておき、エッジ方位の範囲毎にクラス分けを行い、各クラスに属するエッジ点のエッジ方位の平均値に最も近いエッジ方位を持つエッジ点をクラスを代表するエッジ点としても良い。また、１つのクラスを構成するエッジ点群の重心に最も近いエッジ点をクラスを代表するエッジ点としても良い。
【００２８】
また、同一セル内で異なるクラスに属するエッジ点が錯綜するような場合は、上記のクラス代表点の決定方式では対処できなくなることが想定される。このようなことが起こるのは、情報圧縮レベルが高い（同一セルに属する画素数が多すぎる）ことに起因する場合が多く、情報圧縮レベルを下げて特徴点抽出ステップを実行することが望ましい。
【００２９】
以上の説明で、テンプレート画像と被探索画像の双方について、エッジ位置に対応する全ての画素をエッジ点として抽出するとしてきたが、 エッジ点抽出については、このやり方以外に、エッジに沿った複数画素（以降、画素ブロックともいう）に対して１画素を抽出するやり方を採ることもできる。実際に本発明が適用されるテンプレート画像の形状、被探索画像における探索目標画像の在り様、および実質的に満足できる画像マッチング精度レベルに合わせた抽出基準を用意すればよい。
この場合には、クラスタリングおよびクラスの代表点（特徴点）候補（仮のクラス代表点）を導き出す処理基準は、（ステップＳ２０４）の直下に記載した基準と同様である。
【００３０】
３．対応点探索ステップ１（全探索処理ステップ）（図１のステップＳ１３０）
この処理ステップにおいては、テンプレート画像の特徴点を基準とする被探索画像の特徴点の相似変換パラメータを導入し、テンプレート画像、被探索画像の全ての特徴点を用いてマッチング探索の探索目標画像の候補に対応すると想定される相似変換パラメータを抽出する処理を行なう。
図３にこの手順が示されているが、その手順を複数の段落に渡って以下に示す。
【００３１】
手順の説明に先立って、以下、「相似変換パラメータ」について説明する。
相似変換パラメータとして、以下の４つのパラメータTx、Ty、Tq、Tsを持ち込む。
Tx ：テンプレート座標に対する被探索物座標のＸ方向並進値
Ty ：テンプレート座標に対する被探索物座標のＹ方向並進値
Tq ：テンプレート座標に対する被探索物座標の回転値
Ts ：テンプレート画像に対する被探索画像のスケール値
これらの４つのパラメータは、
MstX ：テンプレート画像の特徴点のＸ座標
MstY ：テンプレート画像の特徴点のＹ座標
Mstθ ：テンプレート画像の特徴点の方位
ObjX ：MstXに対応するべき被探索画像の特徴点のＸ座標
ObjY ：MstYに対応するべき被探索画像の特徴点のＹ座標
Objθ ：Mstθに対応するべき被探索画像の特徴点の方位
MinScale ：テンプレート画像に対する被探索画像のスケール値の変動下限
MaxScale ：テンプレート画像に対する被探索画像のスケール値の変動上限
とすると、
【数７】
によって計算あるいは決定される。上記中間値は、所定の基準で決定することができるが、当該数値範囲の中央値であることが好ましい。
【００３２】
（ステップＳ３０１） 相似変換パラメータを投票するための投票空間を用意する。
以下に、「投票空間」について説明する。
投票空間の最小単位は投票箱に相当する最小セルである。最小セルは、相似変換パラメータの最小の分割単位である。即ち、４つのパラメータTx、Ty、Tq、Tsのそれぞれのとりうる数値範囲を上記最小セルによって決められる最小の単位によって分割した範囲Txr、Tyr、Tqr、Tsrの組合せにより区別される投票箱である。この投票箱への投票は、計算された４つのパラメータのセット（Tx、Ty、Tq、Ts）の値がどの投票箱の数値範囲にあるかによって、投票箱が選択されるものである。
一般的な投票空間のサイズは下式で算出される。
投票空間サイズ＝（Txrの数）＊（Tyrの数）＊（Tqrの数）＊（Tsrの数）
仮に、画像サイズ640×480画素（分割単位は画素）、回転範囲360°（分割単位は1°）、スケール変動範囲を１に対して±20％（分割単位は1％）とすると、
投票空間サイズ＝640×480×360×40＝4423680000 セル
となり、膨大な空間となることがわかる。
1セル当たりのバイト数を1(byte)とすると、上記投票空間を計算機上に保持するためには、約4G(byte)のメモリ空間が必要となる。
本発明では投票空間を圧縮することで、この問題を低減している。
圧縮値の例として、以下に示す数値とすると、
Txに関して、1/8
Tyに関して、1/8
Tqに関して、1/8
Tsに関して、1/4
投票空間サイズは1/2048に圧縮されることになり、上記同様のケースにおいて必要とされる投票空間サイズは、約2M(byte)となる。そしてXY空間に関する限りセルのサイズは80画素（X方向）×60画素（Y方向）となる。
上記圧縮値は予め設定しておくことでもよく、また使用者の都合に合わせて選択により可変としてもよい。選択可能な圧縮値としては、X方向およびY方向それぞれ、最大画素数に圧縮値を乗じた結果が整数となるようにしておくことが好ましい。
【００３３】
（ステップＳ３０２） テンプレートの撮像画像のテンプレート画像の特徴点に対する被探索画像の特徴点の相似変換パラメータを、テンプレート画像の特徴点の座標（テンプレート座標ともいう）と被探索画像の特徴点の座標（以降、被探索物座標ともいう）との組合せ間で算出する。
【００３４】
（ステップＳ３０３） 算出された相似変換パラメータに対応するパラメータ空間上の投票領域（投票セル）に投票を行なう（＋１を加算する）。
【００３５】
（ステップＳ３０４）、（ステップＳ３０２）および（ステップＳ３０３）を特徴点全ての組み合わせについて行なう。
【００３６】
（ステップＳ３０５） 全ての特徴点による投票処理実行後、所定の閾値（閾値１ともいう）を超える投票値を持つ（投票空間中の）セルに対応する相似変換パラメータを抽出する。当該抽出された相似変換パラメータに対応する特徴点を持つ被探索画像の画像パターンはマッチング探索の探索目標画像の候補と想定される。
閾値１としては、テンプレート画像の特徴点数に対する投票値の比率で、本発明の画像マッチング方法の使用者が使用条件によって適宜指定する値を使用することが好ましい。
【００３７】
（ステップＳ３０３）の投票において、当該相似変換パラメータにθ方向（方位）の誤差を加味した範囲の相似変換パラメータに対応する投票領域にも重複投票を追加的に行うことも実施しているが、これは、投票をより安定的にする効果があり好ましい。
以下、重複投票の例について説明する。
「相似変換パラメータ」の説明のところで記載した計算式により、相似変換パラメータが算出されるが、特徴点方位(Mstθ，Objθ)に含まれる誤差はTx，Tyを算出する際に更に拡大する。また、投票空間の圧縮によりTqの分解能が低下しているため、Tx，Tyの誤差の要因となっている。
そこで、TxおよびTyに関しては、Tqの値に所定の範囲(±20°など)の誤差を加味して投票を行なう。仮に所定の範囲を±20°とした場合は、Tq, Tx, Ty の算出式が以下のようになる。
【数８】
ここに、ΔQ は、所定の範囲−20° 〜 ＋20°から所定の基準に従って選択されたとびとびの数値（誤差値）である。
具体的な好ましい選択例としては、例えば回転方向の圧縮率が１/8であった場合はΔQの範囲（40°）に対応するTqの投票セルは5セル（=40/8）であるので、ΔQとして−20°、−10°、+10°、+20°の４個を選択することができる。ただし、この選択は必ずしも投票空間圧縮率とバランスをとる必要がないことは勿論である。
【００３８】
選択されたΔQそれぞれに対して上式により算出されたTx(ΔQ)、Ty(ΔQ)およびTq(ΔQ)に対応する投票空間中の投票セルに追加的に投票することで、θ方向の不安定性を排除している。即ち、ΔQ＝０のときのTxおよびTyに対応する投票セルだけに投票することにより誤差があった場合に真に投票するべき投票セルから離れた投票セルにのみ投票することになるよりは、Tqの値に所定の範囲の誤差値ΔQを加味したTq(ΔQ)によって得られるTx(ΔQ)およびTy(ΔQ)に対応する投票セルに投票することは、ΔQ＝０のときの投票投票セルの周辺で選択されたとびとびのΔQの大きさによって決まるとびとびの投票セルに投票する形で票をばら撒くことになり、投票されて然るべき投票セルの近辺に投票値が積み上がる効果により投票の安定性につながる効果がある。
処理時間が少し増えても、より投票の安定化をするには、ΔQの絶対値の最大値に対応するTq(ΔQ)、Tx(ΔQ)およびTy(ΔQ)に対応する投票セルとΔQ＝０に対応するTq、TxおよびTyに対応する投票セルの間に存在する投票セル全てに追加的に投票する方法もある。
当然のことながら、平均的に同じウエイトを持った票を投じる方法に限らず、ΔQ＝０により近いTq(ΔQ)から計算されるTx(ΔQ)およびTy(ΔQ)に対応するセルにはよりウエイトの高い票を投じる方法も好ましい方法である。
【００３９】
４．対応点探索ステップ２（周辺探索処理ステップ）（図１のステップＳ１４０）
この処理ステップにおいては、対応点探索ステップ１により抽出された全ての相似変換パラメータの各々毎に、相似変換パラメータによってテンプレートエッジ点を被探索画像上に変換し、変換されたテンプレートエッジ点群に対応する被探索画像のエッジ点（対応エッジ点）との距離（誤差値）を最小にするように、相似変換パラメータを調整し精度を向上させるパラメータ推定を行い、精度が向上した各々の相似変換パラメータの中から所定の基準により相似変換パラメータの最終候補を決定する処理を行なう。
この処理ステップが必要な理由は、以下に記述することにある。対応点探索ステップ１において抽出された相似変換パラメータは、情報圧縮がなされ精度の落ちたエッジデータに基づいて計算された相似変換パラメータの中から投票値の高いものが抽出されたものであり、基本的に精度の高いものとは言えない。即ち、当該相似変換パラメータによってテンプレート画像の各エッジ点を被探索画像上に変換しても、変換されたエッジ点は被探索画像のエッジ点が構成する画像の輪郭上にあるとは限らず、基本的に当該輪郭の近傍領域に存在する。即ち、対応点探索ステップ１においてはテンプレート画像のエッジ点集合からこのエッジ点集合と相似の可能性が高い被探索画像のエッジ点集合への真の相似変換パラメータに対しある程度の誤差を持った相似変換パラメータが抽出されていると考えてよい。
そのため、対応点探索ステップ２においては、換言すれば、一般化ハフ変換において相似変換パラメータの精度を向上させることと等価な効果を得るために、対応点探索ステップ１で抽出された相似変換パラメータの各々に対して、テンプレート画像とマッチング探索の探索目標画像の候補との間の相似度がどこまで上がるかを確認しながら精度を向上させ、探索目標画像の候補に対応する相似変換パラメータの候補を導き出す処理（パラメータ推定）を行なう。そして、導き出された相似変換パラメータの候補の中から所定の基準で相似変換パラメータの最終候補を決定する。即ち、探索目標画像の最終候補をより精度良く導き出すこととなる。
その詳細な処理手順の例は、図４に示されており、これに基づいてその詳細を以下に示す。
【００４０】
（ステップＳ４０１）
対応点探索ステップ１（全探索処理）により抽出された相似変換パラメータの1つを取り出す。
（ステップＳ４０２）
個々のテンプレートエッジ点を相似変換パラメータに従い、被探索画像上の点に変換する。以降、変換されたテンプレートエッジ点を変換エッジ点という。
この変換エッジ点の座標を
（MstXti、MstYti）
ここに、i＝１、・・・、ｎ （ｎは、変換エッジ点の数）
とする。
（ステップＳ４０３）
個々の変換エッジ点に対し、一定の誤差量を加味した近傍範囲（対応点探索範囲）を設定する。この対応点探索範囲は、予め設定しておくことが好ましい。例えば、変換エッジ点を中心とする半径３画素の円に含まれる範囲を対応点探索範囲とする。
（ステップＳ４０４）
変換エッジ点毎に、（ステップＳ４０３）で設定した対応点探索範囲の中にある被探索画像のエッジ点をピックアップし、これを変換エッジ点の対応候補点とする。
i番目の変換エッジ点に対する対応候補点の座標を
（ObjXaij、ObjYaij）
ここに、j＝１、・・・、ｍ （ｍは、ピックアップされた対応候補点の数）
とする。
（ステップＳ４０５）
個々の変換エッジ点毎に、対応候補点との距離（誤差に相当する）を算出し、対応候補点が複数ある場合は距離が最小となる対応候補点を対応エッジ点とする。
このときの当該個々の変換エッジ点とそれぞれの対応候補点との距離の代用としては、計算の都合上、下記（１０）式のように距離の二乗を使用し、これを各々の変換エッジ点の誤差とする。
【数９】
この場合、距離そのもの（Li）を比較して対応エッジ点を決定することもできるが、計算処理の時間が長くなり、比較的に不利となる問題がある。
（ステップＳ４０６）
（ステップＳ４０５）で算出した全ての対応点との距離の総合値（総合誤差値）として、
【数１０】
を算出する。
この場合、総合誤差値の他の選択肢として、
Ｅ＝L1＋L2＋・・・＋Ln
を採用することも可能であるが、計算処理の時間等の問題がある。
（ステップＳ４０７）
総合誤差値が所定の誤差値（以降、閾値２ともいう）を下回っているか否かを判定し、ＹＥＳならそのときの相似変換パラメータを探索目標画像の候補に対応する相似変換パラメータの候補として抽出し（ステップＳ４０９）に進む。ＮＯの場合、（ステップＳ４０２）から（ステップＳ４０６）を所定の回数だけ繰り返しているか否かを判定し、ＹＥＳなら原則としてそのときの相似変換パラメータは不適切であったとして抽出の対象からはずし、ＮＯなら（ステップＳ４０８）に進む。
当然のことながら、閾値２は本発明の方法を実施する者が諸条件を考慮して適宜決定する。
また、上記最後のＹＥＳの場合は、単純に上記抽出の対象からはずす前にその状態を表示等の手段を使って使用者に判断させるとか、あるいは上記抽出の対象からはずすか否かの別の自動決定の基準を作りそれを実行させる新たなステップを追加する等の処置を行うことが好ましい。
（ステップＳ４０８）
変換エッジ点のそれぞれと対応する対応エッジ点との距離が総合的に最小となるように、新たな相似変換パラメータを所定の方法によって算出し、これを対応点探索ステップ１により得られた相似変換パラメータと見做して（ステップＳ４０２）に進む。
上記変換エッジ点のそれぞれと対応する対応エッジ点との距離が総合的に最小となるように、新たな相似変換パラメータを所定の方法によって算出する具体的な方法は、テンプレートエッジ点群をこのときの対応エッジ点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレートエッジ点群とこの対応エッジ点群を使って最小二乗法により算出する方法である。本実施例のように総合誤差値をここの誤差の二乗和としたときには、誤差の二乗和を最小にする相似変換パラメータが最も適した相似変換パラメータであると考えられ、その条件を満足させられる方法が最小二乗法である。最小二乗法以外にも総合誤差値の態様に依存してロバスト推定法等の代替できる方法はある。
最小二乗法による相似変換パラメータの算出の具体的な方法については、次の段落００４１に記載する。
また、因みに付記すると、上記所定の方法で算出された相似変換パラメータは、当該変換エッジ点を得るために（ステップＳ４０２）において使用した相似変換パラメータに対してより適正なものに近づくように修正されたものになっている。そのため（ステップＳ４０２）から（ステップＳ４０８の繰返しにより相似変換パラメータは修正を繰返しより適したものに調整される。即ち、対応点探索ステップ１で抽出された相似変換パラメータは調整される。
（ステップＳ４０９）
対応点探索ステップ１により得られた、全ての相似変換パラメータに対して（Ｓ４０１）〜（Ｓ４０８）を実施する。そして、得られた相似変換パラメータの候補の中から所定の基準により相似変換パラメータの最終候補が決定される。当然のことながら相似変換パラメータの最終候補に対応する探索目標画像の最終候補が決定されていることになる。
上記所定の基準としては、対応する総合誤差値が所定の誤差値以下になっている相似変換パラメータに限定し、その中でも総合誤差値の少ない順に所定の数だけの相似変換パラメータを選び出す方法が好ましい。また、対応する総合誤差値が所定の誤差値以下になっている調整された相似変換パラメータがない場合は、その中でも総合誤差値の少ない順に所定の数だけの相似変換パラメータを選び出すこともできる。更にまた、本発明の実施の環境によって、その他の都合のよい基準を選ぶことができる。
【００４１】
以下、最小二乗法に基づいた最小二乗解を求める方法によって新たな相似変換パラメータを算出する方法について説明する。
いま、誤差を除けば相似な、テンプレートエッジ点群からなる点集合（点集合Ｇ）と（ステップＳ４０５）で求められる対応エッジ点群からなる点集合（点集合Ｈ）の２つの点集合を考える。
以下の理論では、点集合Ｈの各点が、点集合Ｇの各点と対応がとれていることが前提であるが、この前提は、点集合Ｈの各点が、対応点探索ステップ１で抽出された相似変換パラメータおよびそれ以降に（ステップＳ４０２）から（ステップＳ４０８）までの繰返し処理の中で算出された相似変換パラメータによって点集合Ｇの各点が変換された各変換エッジ点に対応する各対応エッジ点からなることにより満足されている。
いま、点集合Ｇを相似変換により点集合Ｈに重ね合わせたとき、対応する点同士の距離の総合値（距離の二乗和；総合誤差値）を最小になるように、点集合Ｇを点集合Ｈにマッチングさせることを考える。
図７に、このマッチングの理論的説明をするための点集合Ｇと点集合Ｈの関係を示す。点集合Ｇと点集合Ｈは同一の座標系ｘｙ上に配置されているものとする。
【数１１】
【００４２】
以下、最小二乗解を求める。
【数１２】
【数１３】
【数１４】
【数１５】
【００４３】
以上の理論から容易にわかるように、点集合Ｇを点集合Ｈにマッチングさせるときの相似変換パラメータの最小二乗解は、以下のようになる。
Tx ：テンプレート座標に対する被探索物座標のＸ方向並進値
Ty ：テンプレート座標に対する被探索物座標のＹ方向並進値
Tq ：テンプレート座標に対する被探索物座標の回転値
Ts ：テンプレート画像に対する被探索画像のスケール値
で定義される相似変換パラメータについて、
（１）Ｘ軸方向の並進値TxとＹ方向の並進値Tyは、（３４）式より、点集合Ｇと点集合Ｈの重心を合わせるように決めればよい。
（２）回転値Tqは、（３７）式と（４５）式から求めればよい。
（３）スケール値Tsは、（３７）式と（４４）式から求めればよい。
【００４４】
上述の対応点探索ステップ２の手順においては、対応点探索ステップ１により抽出された全ての相似変換パラメータ各々に対して、当該相似変換パラメータによってテンプレートエッジ点を被探索画像上に変換し、変換されたテンプレートエッジ点群（変換エッジ点群）に対応する被探索画像の対応エッジ点群を探し出し、変換エッジ点群と対応エッジ点群との距離の総合値である総合誤差値を最小にするようにテンプレートエッジ点群をこの対応点エッジ群にマッチングさせるとした場合に、最も適した相似変換パラメータをテンプレートエッジ点群とこの対応エッジ点群を使って所定の方法（最小二乗法）により算出し、算出された相似変換パラメータを対応点探索ステップ１で抽出された相似変換パラメータと見做して上記一連の処理を繰返し実行することを、原則として総合誤差値（評価関数）が所定の値を下回るまで行ない、相似変換パラメータを調整するパラメータ推定を行い、当該各々の相似変換パラメータの精度向上を行ない、探索目標画像の最終候補とそれに対応する相似変換パラメータを確認する処理について説明してきたが、画像マッチングの対象となるテンプレートの形状の複雑さの度合いやマッチングの要求精度によっては、「エッジ点」の代わりに「特徴点」を使う、即ち、テンプレートエッジ点および対応エッジ点の代わりにテンプレート画像の特徴点（テンプレート特徴点）および相似変換パラメータによって変換されたテンプレート特徴点群に対応する対応特徴点を使って対応点探索ステップ２の処理を行なうことによって、一定の目的を果たすことも可能である。この場合の上記総合誤差値は、変換特徴点と対応特徴点との距離の総合値である総合誤差値を用いればよく、その考え方は図４に記載してある考え方と同様である。
上述のように特徴点を用いることが可能な条件例を挙げるとすれば、 例えば、被探索物の形状が単純で、被探索画像もノイズあるいは被探索物と混ざっている物体との混同等が少ないといった条件が整うような場合には、相似変換パラメータの精度に関してある程度妥協しても画像マッチングが可能な場合が当然あり得る。
【００４５】
また、諸々の条件によっては、最初から、「テンプレートエッジ点および対応エッジ点」だけを使って対応点探索ステップ２の処理を行なうよりは、相似変換パラメータのある程度までの調整および基準に合わないものの排除による絞込み（粗調整）を「テンプレート特徴点および対応特徴点」を使って行い、後半の調整および絞込み（精調整）を「テンプレートエッジ点および対応エッジ点」によって行い、対応点探索ステップ２の処理時間を短縮することも可能となる。どの方法をとるかは、本発明の実施の条件により選択すればよい。この場合には、相似変換パラメータの粗調整と精調整における総合誤差値最小化の繰り返し処理工程の終了の判断基準である閾値２は、当然、双方で異なってくる。
【００４６】
５．パターン識別処理ステップ（図１のステップＳ１５０）
このステップは、対応点探索ステップ２で最終的に選択決定された相似変換パラメータの最終候補から最終の相似変換パラメータを決定するステップである。当然のことながら、これに応じて探索目標画像が特定されることになる。その実施例の詳細等を以下に述べる。
【００４７】
対応点探索ステップ２（周辺探索処理ステップ）により得られた探索目標画像の最終候補に対応する相似変換パラメータの確度を判断するために、当該相似変換パラメータを用いて最終目標画像の候補のエッジ点とテンプレートエッジ点との一致度を計算する。
即ち、個々の相似変換パラメータ毎に、これを用いてテンプレートエッジ点を被探索画像上に変換し、変換されたテンプレートエッジ点のＸＹ近傍領域に被探索画像のエッジ点が存在すればその数に関係なく１個とカウントし、全ての変換されたテンプレートエッジ点に対するカウントを合計したカウント値をテンプレートエッジ点の数により０〜１００の数値に正規化し、探索目標画像の最終候補のエッジ点と変換されたテンプレートエッジ点との一致度（スコア）とする。この一致度(スコア)に基づいて最終の相似変換パラメータを決定し、マッチング探索の探索目標画像を特定する。
上記のＸＹ近傍領域としては、本発明の実施の条件（例えば、マッチングの必要精度等）によって決めればよいが、注目している変換されたテンプレートエッジ点の８近傍画素を最小範囲としてステップワイズで範囲を広げられるようにすることが現実的に好ましい。
この特定の仕方の例は、一致度が最大のときの相似変換パラメータに対応する探索目標画像の最終候補を探索目標画像として特定する方法もあるし、一致度が所定の閾値（閾値３）以上であるときの相似変換パラメータに対応する探索目標画像の最終候補をすべて探索目標画像として特定することもできる。特に、探索目標画像が被探索画像内に複数個存在する場合などにおいてはこの特定の仕方が好ましい。どの方法をとるかは、本発明の方法を実施する者が決めればよいことである。
【００４８】
また、相似変換パラメータの確度を判断するために上記のような一致度（スコア）の計算方法に限る必要はなく、他の計算方法をとってもかまわないし、当該特定のための一致度評価・判定を行う所定の処理についても自由に基準を決めて行ってよい。
【００４９】
また、対応点探索ステップ２で相似変換パラメータの最終調整を変換されたテンプレート特徴点群に対応する対応特徴点を使って実施した場合は、パターン識別ステップにおける一致度を、特徴点を使って上記同様な方法で得て、これを基に最終探索目標画像を特定することも本発明の実施の結果に要求される条件によっては可能である。また、当然、上記同様エッジ点を使って得た一致度に基づいて最終探索目標画像を特定してもよい。
【００５０】
また、最終探索目標画像の特定は、上記の方法によらず、対応点探索ステップ２の（ステップＳ４０７）が終了したときの直前に、（ステップＳ４０６）で得られている誤差値を基にして行うこともできる。例えば、誤差値の最も少ないもの又は下位の所定の順位に入っている誤差値と共に得られる相似変換パラメータに対応するエッジ点を持つ画像をマッチング探索の最終探索目標画像として特定することができる。この方法は、上記の方法に比べて０〜１００の数値で当該特定の基準値を与えられないところ等、この方法を使った装置等において使用者の使い勝手が少し悪くなる場合がある可能性はあるが、実用上はなんら問題ではない。
【００５１】
本発明の技術的優位性について、発明の効果と重複する点があるが、記述する。
一般的には、エッジ点という諸々の外乱によって誤差を生じやすい特徴量を扱う場合には、投票空間を圧縮することによってその影響を回避することができるが、副作用として相似変換パラメータの精度は圧縮した分だけ低下する。
また、一般化ハフ変換においては、高精度の相似変換パラメータ値を期待しているが、投票空間の圧縮をすることによってこの精度の低下が起こったとすれば大きな問題となる。
これに対して、本発明においては、投票空間の圧縮を行い諸々の外乱により生じやすい誤差を回避する一方、「対応点探索ステップ２（周辺探索処理ステップ）」を導入することによって、圧縮による精度の低下は実質問題（副作用）とならず、対応点探索ステップ１の（ステップＳ３０５）で述べたマッチング探索の探索目標画像の候補と想定されるものを充分特定できる。
また、投票空間の圧縮、特にθ方向の圧縮は、パターンの大きさに比例して誤差が拡大する。通常の投票では、エッジ点対から得られる相似変換パラメータ上の１点のみに投票処理を行うが、本発明においては、誤差を少なくするために、投票終了後、θ方向の誤差を加味した相似変換パラメータに対応するＸ−Ｙ投票空間に追加的に投票することでθ方向の圧縮による不安定性を排除している。
また、エッジ点の誤差に関しても、投票空間を圧縮することで大部分を排除することができる。
以上のように、一般化ハフ変換による画像マッチングにおける欠点である投票空間のメモリ使用量の多さおよび相似変換パラメータ投票時のメモリアクセスコストの多さを回避し、精度の高い画像マッチング方法が実現できたことになる
【００５２】
以上の本発明に関する説明で、テンプレート画像および被探索画像の画素の単位は、テンプレートおよび被探索物の撮像画像の画素である場合でも、当該カメラによる撮像画像を予め情報圧縮した画像（例えば、４画素を１画素とした画像）の画素であってもかまわない。どちらの場合に対しても本発明は適用できる。
被探索物の形状が単純で画像マッチングにおける見分けがつきやすいとか、画像マッチングによる結果を被探索物の位置・姿勢の計測に利用する場合にその計測精度が上記画像マッチングを撮像画像の画素単位で行わなければならないほどの高さを必要としない場合等においては、後者の単位の画像、即ち、撮像画像を予め情報圧縮した画像による本発明の画像マッチング方法を採ることができる。当然、後者の場合には、前者の場合よりも処理速度の向上および使用するメモリ容量の節減が可能である。
【図面の簡単な説明】
【００５３】
【図１】本発明による画像パターンマッチング方法の主要な処理ステップの実施例の一つを示すフローチャートである。
【図２】図１の処理ステップＳ１２０の詳細を示すフローチャートである。
【図３】図１の処理ステップＳ１３０詳細を示すフローチャートである。
【図４】図１の処理ステップＳ１４０詳細を示すフローチャートである。
【図５】画素とセルの関係の１例を示す図である。
【図６】エッジマップの例を示す図である。
【図６ａ】図３のエッジマップ上のいくつかのセルのそれぞれに複数のエッジ点がプロットされている場合の１例を示す図である。
【図６ｂ】エッジ点のクラスタリングにより各セルにおける特徴点が選ばれた状態の例を示す図である。
【図７】最小二乗法によるマッチングの理論的説明をするための点集合Ｇと点集合Ｈの関係を示す図である。
【符号の説明】
【００５４】
・
【技術分野】
【０００１】
本発明は、テンプレートの画像に相似な画像を被探索画像から探し出すための画像マッチング技術に関する。
【背景技術】
【０００２】
テンプレートの画像（以降、「テンプレート」ともいう）と探索目標画像の輪郭情報を用いたマッチング技術として、一般化ハフ変換という手法が知られており、将来の有用な技術と考えられる。この手法は、輪郭を細分化したエッジ点という構成要素を用いて演算を行なう。テンプレート画像および探索目標画像の存在する画像（以降、被探索画像ともいう）の双方からエッジ点を抽出し、それらの組み合わせから算出される相似変換パラメータ値を投票空間と呼ばれるメモリ配列に記録（投票）する。
この操作を、テンプレート画像および被探索画像の全てのエッジ点の組み合わせについて行ない、投票値を評価することにより、最も相似に近い被探索画像に対応する相似変換パラメータ値を得ることができる。
【０００３】
しかしながら、一般化ハフ変換には以下の問題点が存在し、一般化ハフ変換を利用した画像マッチングの世界においては、市場（例えば、ＦＡ市場）が要求する処理スピード、マッチング精度、マッチング安定性、および、さらに広い応用を図ろうとすれば、手法の汎用性等を兼ね備えた技術が必要となっている。しかしながら、この要求に応えることができる技術は、出願者の知りうる限りでは存在しない。
（１）計算量の多さ
一般的に、テンプレート画像、被探索画像の全てから得られるエッジ点は膨大であり、テンプレート画像のエッジ点の数をM、被探索画像の全てから得られるエッジ点の数をNとした場合はM×Nの計算量となる。
計算量を削減するために、対象物の形状に依存した処理（コーナー抽出など）が多く使われるが、曲線への対応が難しい、汚れや隠れに弱いなどの欠点があり、汎用的なマッチング手法を構築する妨げとなる。
（２）メモリ使用量の多さ
相似変換を扱う場合、推定するパラメータは4つとなり投票空間は4次元空間が必要である。標準的な画像サイズ（６４０×４８０）でも、テンプレート画像に対する被探索画像の相対角度差の最大値を３６０度、テンプレート画像に対する被探索画像のスケールの比が１に対して±２０％とし、それぞれ１画素、１度および１％刻みで投票するとすれば、６４０×４８０×３６０×４０＝４Ｇ（Ｂｙｔｅ）の空間が必要であり、このままでは実用性が乏しい。
（３）安定性
エッジ点という特徴量は、外乱（ノイズ、照明変動等）の影響、対象物自体の微小変化の影響により誤差が含まれる。この誤差は投票空間への投票精度に影響するため、実際のカメラから取得した映像を処理する際に、正しい回答が得られないことが多い。これを回避するために投票空間を圧縮する方法が知られているが、圧縮した分精度が低下する。
また、誤差を加味した投票方法(重複投票)もいくつか提案されているが、計算量の更なる増大を招くと共に、偽りの回答を生み出す可能性がある。
（４）精度の確保
上記の安定性の項にも記載したが、一般化ハフ変換において安定性と精度を共存させることは難しい。よって、何らかの新しい技術によるか、または他の技術と組み合わせることにより精度を確保しなくてはならない。
【特許文献１】特開２００７−１２８３７４
【非特許文献１】Hough変換に基づく図形検出法の新展開、和田俊和 外１名、情報処理第３６巻 第３号、社団法人情報処理学会、１９９５．０３、ｐ．２５３〜２６３
【非特許文献２】Hough変換の諸課題と新しいパターン計測 基礎編、森本正志 外１名、計測と制御 第３５巻 第１１号、１９９６．１１、ｐ．８６９〜８７７
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明が解決しようとする課題は、以下の４つの課題を解決し、画像マッチング技術において一般化ハフ変換が持つ問題点を解決する新たな視点からのパターンマッチング技術を提供することである。
（１）メモリ使用量およびメモリアクセス回数削減による処理速度の向上
（２）精度を確保するための新しい技術の実現
（３）安定性を改善するための投票方法、投票空間の圧縮の実現
（４）汎用性、安定性、汚れ、隠蔽への耐性を損なわないエッジ点圧縮手法の実現
【課題を解決するための手段】
【０００５】
本発明の課題を解決する手段は、以下に記載するものである。
【０００６】
テンプレート画像と被探索画像の双方に対して輪郭を構成する画素（以降、エッジ点ともいう）を抽出するエッジ点抽出ステップと、
テンプレート画像と被探索画像とを選択された圧縮率に基づいて情報圧縮することによってそれぞれの画像の画素群をグループ化（当該グループをセルという）し、テンプレート画像と被探索画像のそれぞれに対して、セル各々において、所定の方法で計測されるエッジ方位が所定の角度範囲にあるエッジ点群を１つのクラスとするクラスタリングを行い、所定の処理基準により当該クラスを代表するエッジ点を選定し、これを特徴点とするエッジ点圧縮を行う特徴点抽出ステップと、
テンプレート画像の特徴点（以降、テンプレート特徴点ともいう）の座標（以降、テンプレート座標ともいう）を基準にして被探索画像の特徴点（被探索物特徴点ともいう）の座標（以降、被探索物座標ともいう）の相似変換パラメータを計算し、その計算値に従って相似変換パラメータによるパラメータ空間（以降、投票空間ともいう）上の投票領域（以降、投票セルともいう）に投票することを、テンプレート座標のそれぞれと被探索物座標のそれぞれとの全ての組合せに対して実施した後、所定の閾値（以降、閾値１ともいう）を超える投票値を得た投票セルに対応する相似変換パラメータを全て抽出する対応点探索ステップ１と、
対応点探索ステップ１により抽出された相似変換パラメータを使用してテンプレート画像の各エッジ点（以降、テンプレートエッジ点ともいう）を前記被探索画像上に変換し、これらの変換されたエッジ点（以降、変換エッジ点ともいう）の所定の近傍内で当該変換エッジ点から最小の距離にある被探索画像のエッジ点（以降、対応エッジ点ともいう）を探し出し、全ての変換エッジ点に対する対応エッジ点との距離の総合値（以降、総合誤差値ともいう）を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを前記対応点探索ステップ１で抽出された相似変換パラメータとみなして上記本ステップの一連の処理手順を繰り返すことによって、当該総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行い、調整された相似変換パラメータの中から所定の基準を満足する相似変換パラメータを選び出す対応点探索ステップ２と、
対応点探索ステップ２で調整され選び出された各々の相似変換パラメータに対応し、総合誤差値の計算の対象となった被探索画像のエッジ点群を持つ画像パターン（以降、探索目標画像最終候補ともいう）の中から、マッチング探索の探索目標画像を特定するための相似変換パラメータを所定の処理により決定する被探索画像識別ステップと
により画像マッチングを行う。
上記テンプレート画像については、常識的には、ノイズを除いて、テンプレートが１個のみ存在するか、テンプレートが複数の所定の位置に配置された組合せテンプレートからなる場合にはその組合せテンプレートのみが存在する画像と考えてよい。
また、対応点探索ステップ２における所定の方法は、テンプレートエッジ点群をこのときの対応エッジ点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレートエッジ点群とこの対応エッジ点群を使って最小二乗法により算出する方法が好ましい。
【０００７】
特徴点抽出ステップにおいて、
テンプレート画像と被探索画像のそれぞれに対して、輪郭上の全ての画素を対象としてエッジ点を抽出するようにする。
また、輪郭上の相並ぶ複数画素毎を対象として所定の基準で１個のエッジ点（画素単位）を抽出するようにしてもよい。
更に、特徴点抽出ステップにおける所定の処理基準として、
クラスを代表するエッジ点を、当該エッジ点が存在するクラスの中で最初にエッジ方位が計測されたエッジ点とすることができる。
また、クラスを代表するエッジ点を、当該エッジ点が存在するクラスに属するエッジ点のエッジ方位の平均値に最も近いエッジ方位を持つエッジ点とすることもできる。
また、クラスを代表するエッジ点を、１つのクラスを構成するエッジ点群の重心に最も近いエッジ点とすることもできる。
【０００８】
相似変換パラメータが、以下の４個のパラメータのセット、
テンプレート座標に対する被探索物座標のＸ方向並進値（Tx）
【数１】
テンプレート座標に対する被探索物座標のＹ方向並進値（Ty）
【数２】
テンプレート座標に対する被探索物座標の回転値（Tq）
【数３】
テンプレート画像に対する被探索画像のスケール値（Ts）
ここに
MstX ：テンプレート画像の特徴点のＸ座標
MstY ：テンプレート画像の特徴点のＹ座標
Mstθ ：テンプレート画像の特徴点の方位
ObjX ：MstXに対応するべき被探索画像の特徴点のＸ座標
ObjY ：MstYに対応するべき被探索画像の特徴点のＹ座標
Objθ ：Mstθに対応するべき被探索画像の特徴点の方位
【数４】
【数５】
から構成されるようにする。
【０００９】
対応点探索ステップ１における相似変換パラメータに対応する投票空間への投票において、テンプレート座標に対する被探索物座標の回転値（Tq）に所定の範囲の誤差を加味した範囲の中で、とびとびに選択されるθ方向の誤差（Δθ）を加味した投票空間への重複投票を追加的に実施することが対応点探索ステップ１の安定性の観点から好ましい。
【００１０】
重複投票が、θ方向の誤差（Δθ）に依存したウエイトによる重複投票であることも同様に好ましい方法である。
【００１１】
対応点探索ステップ２における総合誤差値を、各々の変換エッジ点に対する対応エッジ点との距離の二乗和とすることができる。もちろん、距離の総和としてもかまわない。
【００１２】
対応点探索ステップ２が、エッジ点、テンプレートエッジ点、変換エッジ点および対応エッジ点をそれぞれ、特徴点、テンプレート特徴点、変換特徴点および対応特徴点と置き換えた対応点探索ステップ２の処理方法に従って、対応点探索ステップ１で抽出された相似変換パラメータを使用して全ての変換特徴点に対応する対応特徴点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな抽出された相似変換パラメータとして上記本ステップの一連の処理手順を繰り返すことによって、総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行う粗調整ステップと、
粗調整ステップで粗調整された相似変換パラメータ毎に、対応点探索ステップ２の処理方法に従って、当該相似変換パラメータを使用して全ての変換エッジ点に対する対応エッジ点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな当該粗調整された相似変換パラメータとして上記一連の処理手順を繰り返すことによって、総合誤差値が所定の他の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を行なう精調整ステップとからなるようにすることができる。
ここで、上記粗調整ステップにおける所定の方法は、テンプレート特徴点群をこのときの対応特徴点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレート特徴点群とこの対応特徴点群を使って最小二乗法により算出する方法が好ましい。
また、上記精調整ステップにおける所定の方法は、テンプレートエッジ点群をこのときの対応エッジ点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレートエッジ点群とこの対応エッジ点群を使って最小二乗法により算出する方法が好ましい。
【００１３】
対応点探索ステップ２を、エッジ点、テンプレートエッジ点、変換エッジ点および対応エッジ点をそれぞれ、特徴点、テンプレート特徴点、変換特徴点および対応特徴点と置き換えた対応点探索ステップ２の処理方法に従って、対応点探索ステップ１で抽出された相似変換パラメータを使用して全ての変換特徴点に対応する対応特徴点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな抽出された相似変換パラメータとして上記本ステップの一連の処理手順を繰り返すことによって、総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行うことで済ますようにすることもできる。
ここで、上記粗調整ステップにおける所定の方法は、テンプレート特徴点群をこのときの対応特徴点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレート特徴点群とこの対応特徴点群を使って最小二乗法により算出する方法が好ましい。
【００１４】
被探索画像識別ステップにおける所定の処理として、対応点探索ステップ２で調整された各々の相似変換パラメータ毎に、これを用いてテンプレートエッジ点を被探索画像上に変換し、変換されたテンプレートエッジ点各々の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値に基づいて、テンプレート画像と探索目標画像の最終候補との一致度を計算し、当該一致度の大きさに基づいて探索目標画像を特定することもできる。
一致度の計算方法の好ましい例は、当該変換されたテンプレートエッジ点の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値をテンプレートエッジ点の数により正規化する方法である。
【００１５】
被探索画像識別ステップにおける所定の処理としては、対応点探索ステップ２で調整され選び出された各々の相似変換パラメータの中から、当該調整過程における最終の総合誤差値の小ささに基づいて対応する相似変換パラメータを選定することができ、具体的には、最終の総合誤差値が最も小さいものが得られたときの相似変換パラメータを選定し、これに対応する探索目標画像の最終候補を探索目標画像として特定することができ、この処理は好ましい処理方法である。また、被探索物が同一画像内に複数ある場合等においては、相似変換パラメータの数値の違いの大きさに着目した条件設定により数値の近い相似変換パラメータのクラスタを特定し、各クラスタの中から総合誤差値が最も小さいものが得られたときの相似変換パラメータを選定することができる。
【００１６】
また、対応点探索ステップ２を、エッジ点の代わりに特徴点を使って実行する場合には、被探索画像識別ステップにおける所定の処理として、対応点探索ステップ２で調整された各々の相似変換パラメータ毎に、これを用いてテンプレートエッジ点を被探索画像上に変換し、変換されたエッジ点の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値に基づいて、テンプレート画像と探索目標画像の最終候補との一致度を計算し、当該一致度の大きさに基づいて探索目標画像を特定することももちろんできる。
この場合の一致度の好ましい例は、当該変換された特徴点の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値をテンプレート特徴点の数により正規化する方法である。
【００１７】
また、対応点探索ステップ２を、エッジ点の代わりに特徴点を使って実行する場合には、被探索画像識別ステップにおいて、対応点探索ステップ２における距離の総合値に基づいて探索目標画像を特定することもできる。
【００１８】
以上の「本発明の課題を解決する手段」で述べた画像マッチング方法に関する適切な手段の選択により、エッジ点抽出ステップと特徴点抽出ステップと対応点探索ステップ１と対応点探索ステップ２と被探索画像識別ステップとを、具備させ、上述の課題解決の手段のいずれかの組合せを実現する機能を持つコンピュータシステムにより、画像マッチング応用装置を作ることができる。
上記画像マッチング応用装置の好ましい基本的な例を具体的に示すと、
テンプレート画像と探索目標画像の存在する画像（被探索画像）の双方に対して輪郭を構成する画素（エッジ点）を抽出するエッジ点抽出ステップと、
テンプレート画像と被探索画像とを選択された圧縮率に基づいて情報圧縮することによってそれぞれの画像の画素群をグループ化（当該グループをセルという）し、テンプレート画像と被探索画像のそれぞれに対して、セル各々において、所定の方法で計測されるエッジ方位が所定の角度範囲にあるエッジ点群を１つのクラスとするクラスタリングを行い、所定の処理基準により当該クラスを代表するエッジ点を選定し、これを特徴点とするエッジ点圧縮を行う特徴点抽出ステップと、
テンプレート画像の特徴点（テンプレート特徴点）の座標（テンプレート座標）を基準にして被探索画像の特徴点（被探索物特徴点）の座標（被探索物座標）の相似変換パラメータを計算し、その計算値に従って相似変換パラメータによるパラメータ空間（投票空間）上の投票領域（投票セル）に投票することを、テンプレート座標のそれぞれと被探索物座標のそれぞれとの全ての組合せに対して実施した後、所定の閾値（閾値１）を超える投票値を得た投票セルに対応する相似変換パラメータを全て抽出する対応点探索ステップ１と、
対応点探索ステップ１により抽出された相似変換パラメータを使用してテンプレート画像の各エッジ点（テンプレートエッジ点）を前記被探索画像上に変換し、これらの変換されたエッジ点（変換エッジ点）の所定の近傍内で当該変換エッジ点から最小の距離にある被探索画像のエッジ点（対応エッジ点）を探し出し、全ての変換エッジ点に対する対応エッジ点との距離の総合値（総合誤差値）を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを前記対応点探索ステップ１で抽出された相似変換パラメータとみなして上記本ステップの一連の処理手順を繰り返すことによって、当該総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数まで繰返すまで当該相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行い、調整された相似変換パラメータの中から所定の基準を満足する相似変換パラメータを選び出す対応点探索ステップ２と、
対応点探索ステップ２で調整され選び出された各々の相似変換パラメータに対応し、総合誤差値の計算の対象となった被探索画像のエッジ点群を持つ画像パターン（探索目標画像最終候補）の中から、マッチング探索の探索目標画像を特定するための相似変換パラメータを所定の処理により決定する被探索画像識別ステップと
を具備し、上述の課題解決の手段のいずれかを実現する機能を持つ画像マッチングシステムとなる。
上記対応点探索ステップ２において、「エッジ点」を「特徴点」と置き換えることもできる。
【００１９】
当然のことながら、上記システムの中に搭載され、上記機能を実現するコンピュータプログラムも、本発明の権利範囲となる。
【発明の効果】
【００２０】
マッチング探索の最終探索目標画像の特定・確認のために当該最終探索目標画像に対応する相似変換パラメータの修正を行いながらテンプレート画像との一致度の究極値を確認する従来にない処理プロセス（パラメータ推定プロセス）を導入することで、安定性を得るために採る投票空間の圧縮による相似変換パラメータの精度ダウンの影響を相殺して、最終の実用上充分な安定性と精度を確保することができた。
更に、投票空間の圧縮によって引き起こされるθ方向の投票の不安定性を排除できる新たな投票方法を追加することにより、安定性の一層の向上に寄与できた。
更にまた、精度と安定性の共存困難の問題で一般化ハフ変換では実現不可能であった投票空間の圧縮が可能となったことにより、従来の一般化ハフ変換を使用する画像探索に比較して、使用するコンピュータ上の画像メモリ領域の大幅な削減が可能となり、またこれに関連して計算量の削減が可能になったことによるマッチング画像探索処理速度の向上も実現する等の付随効果が得られた。
これらにより、一般化ハフ変換が本質的に持つ問題点を解決するパターンマッチング技術を提供することができた。
【発明を実施するための最良の形態】
【００２１】
発明を実施するための最良の形態は、図１に実施例として示すように、大きく分けて５つの処理ステップを具備する。この内容について以下に説明する。
【００２２】
１．エッジ点抽出ステップ（図１のステップＳ１１０）
テンプレート画像と被探索画像の双方について、輪郭を構成する画素（以降、「エッジ点」ともいう）を抽出する。
エッジを抽出する方法は、従来から使われている技術であり、
（１）濃淡画像に対してＸ方向およびＹ方向の微分フィルタ処理を行うことによってＸ方向およびＹ方向濃度微分画像を得る。
（２）それぞれの濃度微分画像を走査することによって、微分値の山の頂上部分、および、微分値の谷の最下部分となっている画素を特定し、これを仮のエッジ位置（Ｘe，Ｙe）とする。
（３）仮のエッジ位置周辺の濃度微分波形から山の頂上部分、および、谷の最下部分を精度よく求める。エッジ方位は当該エッジ点の位置における輪郭の形状によって決まる特有の角度情報であり、本実施例では、代表的な角度情報として「当該エッジ点の位置における輪郭の接線に対する法線ベクトルの方位」を採用し、エッジ点（Ｘeij,Ｙeij）におけるエッジ方位をθijとすると、θijは、次の式から求められる。
【数６】
テンプレート画像と被探索画像の双方について、上記の方法によりエッジ位置を見出し、エッジ位置に対応する全ての画素をエッジ点としてエッジ方位と共に抽出する。
当然、エッジ位置とエッジ方位を見出す技術は他にもあり、適宜選んで使用することができる。
上の説明ではエッジ方位をエッジ点位置での輪郭の法線としているが、必ずしも輪郭の法線とする必要はなく、エッジ方位をエッジ位置での輪郭の接線方向としても良いし、その他任意に所定の基準で導き出すことができるエッジ位置での輪郭の角度としても良い。
【００２３】
２．特徴点抽出ステップ（図１のステップＳ１２０）
このステップにおいては、テンプレート画像と被探索画像の双方について、「エッジ抽出」処理によって抽出されたエッジ点に対して情報圧縮を行い、最終的に残したエッジ点を「特徴点」とする。
エッジ点の情報圧縮は、図２にその手順が示されているが、以下に図２に沿ってその詳細を説明する。
（ステップＳ２０１）
Ｘ方向およびＹ方向の圧縮レベルを指定する。（１／１、１／２、１／４、１／８、１／１６、１／３２等）
（ステップＳ２０２）
指定された圧縮レベルに従い、ＸＹ空間を情報圧縮する。具体的には、Ｘ方向およびＹ方向それぞれは指定されたそれぞれの圧縮レベルの逆数の画素が１つのセルに対応するようにセルがＸＹ空間に配置される。その圧縮されたＸＹ空間の例は、図５に示すようなもので、Ｘ方向の圧縮レベル＝１／８、Ｙ方向の圧縮レベル＝１／８のものである。破線は画素の境界を示し、実線はセルの境界を示す。
（ステップＳ２０３）
情報圧縮後のＸＹ空間の対応するセル内の対応する各画素にエッジ点をプロットする。（以降、エッジ点プロット後のＸＹ空間を「エッジマップ」ともいう。）
図６に輪郭が矩形である図形のエッジ点（黒点）をプロットしたエッジマップの１例を示す。
（ステップＳ２０４）
エッジマップ上の各セル内に複数のエッジ点がプロットされている場合は、エッジ方位を用いてクラスタリング（詳細は下記参照）を行ない、各クラスの代表点を特徴点とする。
エッジ方位を用いたクラスタリングとは、同一のセル内に存在しているエッジ点をエッジ方位の振れが所定の範囲にあるという条件で同一クラスに分類するもので、特徴点を導き出す前の処理である。
クラスタリングおよびクラスの代表点（特徴点）候補（仮のクラス代表点）を導き出す処理基準は、いかなる方向にエッジ点の有無をチェックしていくとしても、チェックされているエッジ点のエッジ方位が仮のクラス代表点のクラス方位±４５°未満のエッジ方位を持つ場合は仮のクラス代表点と同一のクラスに分類し、仮のクラス代表点のクラス方位±４５°以上のエッジ方位を持つ場合は当該チェックされているエッジ点において新しいクラスを生成し、このエッジ点を新しいクラスの仮のクラス代表点とするやり方をとる。以上の基準を、同一セル内にある全てのエッジ点に対して適用し、そのセルに含まれる各エッジ点のクラス分けを行い、各クラスから所定の処理基準によりクラス代表点（特徴点）を導き出す。
【００２４】
エッジ方位を用いたクラスタリングの手順の１例について、図６、図６ａ、および図６ｂを使いながら以下説明する。
図６ａは、図6のエッジマップ上のいくつかのセル（升目）のそれぞれに複数のエッジ点がプロットされている場合の１例を示すものであり、セル当たりのエッジ点の数は図を見やすくするために図６の場合の数とは異ならせてあるが、図6の矩形のエッジ点列部分の左上隅の部分の拡大図と考えてよい。黒点がエッジ点である。
（手順１）
エッジマップの中のエッジ点の探索は、好ましい例として、図６（詳しくは、図６ａ）の左上隅の画素から右方向に画素ラインに沿って、更に画素ラインについては上から下に走査してエッジ点があるかないか調べていく方法をとる。
上記のように画素ラインごとの走査によって最初に発見されたエッジ点は、黒点のエッジ点列の左上隅のエッジ点である。
本手順においては、そのセルにおいて最初に選択されたエッジ点をそのセルにおける最初のクラスの構成要素とし、最初にクラスの構成要素となったエッジ点を仮の当該クラス代表点とすると共に、この仮のクラス代表点の方位をクラス方位とする。
（手順２）
同一セル内で次に発見されたエッジ点は、仮のクラス代表点とされたエッジ点の右隣のエッジ点であり、このエッジ点のエッジ方位が仮のクラス代表点のクラス方位±４５°の範囲にあるか否かの判定を行う。
この場合、右隣のエッジ点は、当該範囲内にあるため直前に発見されたエッジ点と同一クラスに属し、またクラスの代表点となることもない。
（手順３）
更に右隣のエッジ点についても、同一セル内で、エッジ方位もクラス方位±４５°未満であるので、以上の３つのエッジ点が同一クラスを形成するものとし、仮の代表点をそのまま維持する。
（手順４）
このようにして、現在の走査画素ライン上のエッジ点について、右隣のセル内について上記基準と判定方法により、新しいクラスと仮のクラス代表点を決めていく。
更に、同一の走査画素ライン上のその先のセル内についても、同様の処理をしていく。
（手順５）
その下の走査ライン上の各セル内においても(手順１)から(手順４)と同様な処理をしていくが、現在の走査画素ライン上且つ同一セル内で、
（１）エッジ点が見つからなかった場合
手順６に移る。
（２）エッジ点が見つかった場合
当該エッジ点のエッジ方位をそれまでに決まっている仮の代表エッジ点（複数の場合はそれぞれの代表エッジ点）の持つクラス方位と比較し、当該クラス方位に対し±４５°未満にあるクラス方位を持つクラスがあればそのクラスに属させるし、なければ新しいクラスを作り当該エッジ点を新しいクラスの仮のクラス代表点とする。
（手順６）
当該セルについて、同一画素ラインについて先のセル全てに対して、（手順５）の処理を実施する。
（手順７）
更に現在の画素ラインが関係するセル群の最終の走査画素ラインとなるまで全ての走査画素ラインに対して（手順５）および（手順６）の処理を実施する。
（手順８）
（手順１）から（手順７）までの処理結果により、全てのセルの全てのクラス代表点（特徴点）を決定する。
この最終結果の例は、図６ｂに示されるようなものである。ここで、図６ｂの黒丸は特徴点である。
【００２５】
上記の実施例におけるクラス方位±４５°の４５°は、必ずしもこれにこだわる必要はなく、クラスを細かく分けたい場合は小さい数値（例えば、３０°）に変更することも可能であるし、クラスを更に粗く分けたい場合には大きな数値（例えば、６０°）に変更することも可能であり、被探索物の形状、精度その他の条件によって他の数値を任意に選んでかまわない。
４５°のメリットの一つは、ＦＡ等の世界において比較的多い矩形あるいは直角部分を含む外形を持ったワークが多いことから、４５°はエッジ方位が９０°異なる線分のエッジ点を異なるクラスのエッジ点として分離することが容易な最大の角度であり、クラスの数（即ち、特徴点の数）を多くの場合に最少とすることができることにある。
【００２６】
また、１つのセルのエッジ点の探索方式は、上記の実施例の方法に限定する必要はなく、他の探索方式として、例えば、同一セル内の全てのエッジ点についてその方位を記録し、同一セル内のエッジ点同士で上記「クラスタリングおよびクラスの代表点（特徴点）候補（仮のクラス代表点）を導き出す基準」による判定を行い、各エッジ点が属するクラスを決定し、所定の処理基準でクラス代表点（特徴点）を決定してもよい。所定の処理基準としては、例えば、同一クラスに属するエッジ点列が、奇数のときは中央に位置するエッジ点をクラス代表点（特徴点）として選び、偶数のときは中央に位置する２つのエッジ点の内の一つを画素ライン上あるいは画素ライン間の走査の方向を基準に選択するようにしても良い。
【００２７】
また、「クラスタリングおよびクラスの代表点（特徴点）候補（仮のクラス代表点）を導き出す処理基準」および「１つのセルのエッジ点の探索方式」についても以上の例に限ることはなく、他の処理基準あるいは方式によっても同様の効果が得られる輪郭情報の圧縮ができればよい。例えば、同一セル内の全てのエッジ点のエッジ方位を計測しておき、エッジ方位の範囲毎にクラス分けを行い、各クラスに属するエッジ点のエッジ方位の平均値に最も近いエッジ方位を持つエッジ点をクラスを代表するエッジ点としても良い。また、１つのクラスを構成するエッジ点群の重心に最も近いエッジ点をクラスを代表するエッジ点としても良い。
【００２８】
また、同一セル内で異なるクラスに属するエッジ点が錯綜するような場合は、上記のクラス代表点の決定方式では対処できなくなることが想定される。このようなことが起こるのは、情報圧縮レベルが高い（同一セルに属する画素数が多すぎる）ことに起因する場合が多く、情報圧縮レベルを下げて特徴点抽出ステップを実行することが望ましい。
【００２９】
以上の説明で、テンプレート画像と被探索画像の双方について、エッジ位置に対応する全ての画素をエッジ点として抽出するとしてきたが、 エッジ点抽出については、このやり方以外に、エッジに沿った複数画素（以降、画素ブロックともいう）に対して１画素を抽出するやり方を採ることもできる。実際に本発明が適用されるテンプレート画像の形状、被探索画像における探索目標画像の在り様、および実質的に満足できる画像マッチング精度レベルに合わせた抽出基準を用意すればよい。
この場合には、クラスタリングおよびクラスの代表点（特徴点）候補（仮のクラス代表点）を導き出す処理基準は、（ステップＳ２０４）の直下に記載した基準と同様である。
【００３０】
３．対応点探索ステップ１（全探索処理ステップ）（図１のステップＳ１３０）
この処理ステップにおいては、テンプレート画像の特徴点を基準とする被探索画像の特徴点の相似変換パラメータを導入し、テンプレート画像、被探索画像の全ての特徴点を用いてマッチング探索の探索目標画像の候補に対応すると想定される相似変換パラメータを抽出する処理を行なう。
図３にこの手順が示されているが、その手順を複数の段落に渡って以下に示す。
【００３１】
手順の説明に先立って、以下、「相似変換パラメータ」について説明する。
相似変換パラメータとして、以下の４つのパラメータTx、Ty、Tq、Tsを持ち込む。
Tx ：テンプレート座標に対する被探索物座標のＸ方向並進値
Ty ：テンプレート座標に対する被探索物座標のＹ方向並進値
Tq ：テンプレート座標に対する被探索物座標の回転値
Ts ：テンプレート画像に対する被探索画像のスケール値
これらの４つのパラメータは、
MstX ：テンプレート画像の特徴点のＸ座標
MstY ：テンプレート画像の特徴点のＹ座標
Mstθ ：テンプレート画像の特徴点の方位
ObjX ：MstXに対応するべき被探索画像の特徴点のＸ座標
ObjY ：MstYに対応するべき被探索画像の特徴点のＹ座標
Objθ ：Mstθに対応するべき被探索画像の特徴点の方位
MinScale ：テンプレート画像に対する被探索画像のスケール値の変動下限
MaxScale ：テンプレート画像に対する被探索画像のスケール値の変動上限
とすると、
【数７】
によって計算あるいは決定される。上記中間値は、所定の基準で決定することができるが、当該数値範囲の中央値であることが好ましい。
【００３２】
（ステップＳ３０１） 相似変換パラメータを投票するための投票空間を用意する。
以下に、「投票空間」について説明する。
投票空間の最小単位は投票箱に相当する最小セルである。最小セルは、相似変換パラメータの最小の分割単位である。即ち、４つのパラメータTx、Ty、Tq、Tsのそれぞれのとりうる数値範囲を上記最小セルによって決められる最小の単位によって分割した範囲Txr、Tyr、Tqr、Tsrの組合せにより区別される投票箱である。この投票箱への投票は、計算された４つのパラメータのセット（Tx、Ty、Tq、Ts）の値がどの投票箱の数値範囲にあるかによって、投票箱が選択されるものである。
一般的な投票空間のサイズは下式で算出される。
投票空間サイズ＝（Txrの数）＊（Tyrの数）＊（Tqrの数）＊（Tsrの数）
仮に、画像サイズ640×480画素（分割単位は画素）、回転範囲360°（分割単位は1°）、スケール変動範囲を１に対して±20％（分割単位は1％）とすると、
投票空間サイズ＝640×480×360×40＝4423680000 セル
となり、膨大な空間となることがわかる。
1セル当たりのバイト数を1(byte)とすると、上記投票空間を計算機上に保持するためには、約4G(byte)のメモリ空間が必要となる。
本発明では投票空間を圧縮することで、この問題を低減している。
圧縮値の例として、以下に示す数値とすると、
Txに関して、1/8
Tyに関して、1/8
Tqに関して、1/8
Tsに関して、1/4
投票空間サイズは1/2048に圧縮されることになり、上記同様のケースにおいて必要とされる投票空間サイズは、約2M(byte)となる。そしてXY空間に関する限りセルのサイズは80画素（X方向）×60画素（Y方向）となる。
上記圧縮値は予め設定しておくことでもよく、また使用者の都合に合わせて選択により可変としてもよい。選択可能な圧縮値としては、X方向およびY方向それぞれ、最大画素数に圧縮値を乗じた結果が整数となるようにしておくことが好ましい。
【００３３】
（ステップＳ３０２） テンプレートの撮像画像のテンプレート画像の特徴点に対する被探索画像の特徴点の相似変換パラメータを、テンプレート画像の特徴点の座標（テンプレート座標ともいう）と被探索画像の特徴点の座標（以降、被探索物座標ともいう）との組合せ間で算出する。
【００３４】
（ステップＳ３０３） 算出された相似変換パラメータに対応するパラメータ空間上の投票領域（投票セル）に投票を行なう（＋１を加算する）。
【００３５】
（ステップＳ３０４）、（ステップＳ３０２）および（ステップＳ３０３）を特徴点全ての組み合わせについて行なう。
【００３６】
（ステップＳ３０５） 全ての特徴点による投票処理実行後、所定の閾値（閾値１ともいう）を超える投票値を持つ（投票空間中の）セルに対応する相似変換パラメータを抽出する。当該抽出された相似変換パラメータに対応する特徴点を持つ被探索画像の画像パターンはマッチング探索の探索目標画像の候補と想定される。
閾値１としては、テンプレート画像の特徴点数に対する投票値の比率で、本発明の画像マッチング方法の使用者が使用条件によって適宜指定する値を使用することが好ましい。
【００３７】
（ステップＳ３０３）の投票において、当該相似変換パラメータにθ方向（方位）の誤差を加味した範囲の相似変換パラメータに対応する投票領域にも重複投票を追加的に行うことも実施しているが、これは、投票をより安定的にする効果があり好ましい。
以下、重複投票の例について説明する。
「相似変換パラメータ」の説明のところで記載した計算式により、相似変換パラメータが算出されるが、特徴点方位(Mstθ，Objθ)に含まれる誤差はTx，Tyを算出する際に更に拡大する。また、投票空間の圧縮によりTqの分解能が低下しているため、Tx，Tyの誤差の要因となっている。
そこで、TxおよびTyに関しては、Tqの値に所定の範囲(±20°など)の誤差を加味して投票を行なう。仮に所定の範囲を±20°とした場合は、Tq, Tx, Ty の算出式が以下のようになる。
【数８】
ここに、ΔQ は、所定の範囲−20° 〜 ＋20°から所定の基準に従って選択されたとびとびの数値（誤差値）である。
具体的な好ましい選択例としては、例えば回転方向の圧縮率が１/8であった場合はΔQの範囲（40°）に対応するTqの投票セルは5セル（=40/8）であるので、ΔQとして−20°、−10°、+10°、+20°の４個を選択することができる。ただし、この選択は必ずしも投票空間圧縮率とバランスをとる必要がないことは勿論である。
【００３８】
選択されたΔQそれぞれに対して上式により算出されたTx(ΔQ)、Ty(ΔQ)およびTq(ΔQ)に対応する投票空間中の投票セルに追加的に投票することで、θ方向の不安定性を排除している。即ち、ΔQ＝０のときのTxおよびTyに対応する投票セルだけに投票することにより誤差があった場合に真に投票するべき投票セルから離れた投票セルにのみ投票することになるよりは、Tqの値に所定の範囲の誤差値ΔQを加味したTq(ΔQ)によって得られるTx(ΔQ)およびTy(ΔQ)に対応する投票セルに投票することは、ΔQ＝０のときの投票投票セルの周辺で選択されたとびとびのΔQの大きさによって決まるとびとびの投票セルに投票する形で票をばら撒くことになり、投票されて然るべき投票セルの近辺に投票値が積み上がる効果により投票の安定性につながる効果がある。
処理時間が少し増えても、より投票の安定化をするには、ΔQの絶対値の最大値に対応するTq(ΔQ)、Tx(ΔQ)およびTy(ΔQ)に対応する投票セルとΔQ＝０に対応するTq、TxおよびTyに対応する投票セルの間に存在する投票セル全てに追加的に投票する方法もある。
当然のことながら、平均的に同じウエイトを持った票を投じる方法に限らず、ΔQ＝０により近いTq(ΔQ)から計算されるTx(ΔQ)およびTy(ΔQ)に対応するセルにはよりウエイトの高い票を投じる方法も好ましい方法である。
【００３９】
４．対応点探索ステップ２（周辺探索処理ステップ）（図１のステップＳ１４０）
この処理ステップにおいては、対応点探索ステップ１により抽出された全ての相似変換パラメータの各々毎に、相似変換パラメータによってテンプレートエッジ点を被探索画像上に変換し、変換されたテンプレートエッジ点群に対応する被探索画像のエッジ点（対応エッジ点）との距離（誤差値）を最小にするように、相似変換パラメータを調整し精度を向上させるパラメータ推定を行い、精度が向上した各々の相似変換パラメータの中から所定の基準により相似変換パラメータの最終候補を決定する処理を行なう。
この処理ステップが必要な理由は、以下に記述することにある。対応点探索ステップ１において抽出された相似変換パラメータは、情報圧縮がなされ精度の落ちたエッジデータに基づいて計算された相似変換パラメータの中から投票値の高いものが抽出されたものであり、基本的に精度の高いものとは言えない。即ち、当該相似変換パラメータによってテンプレート画像の各エッジ点を被探索画像上に変換しても、変換されたエッジ点は被探索画像のエッジ点が構成する画像の輪郭上にあるとは限らず、基本的に当該輪郭の近傍領域に存在する。即ち、対応点探索ステップ１においてはテンプレート画像のエッジ点集合からこのエッジ点集合と相似の可能性が高い被探索画像のエッジ点集合への真の相似変換パラメータに対しある程度の誤差を持った相似変換パラメータが抽出されていると考えてよい。
そのため、対応点探索ステップ２においては、換言すれば、一般化ハフ変換において相似変換パラメータの精度を向上させることと等価な効果を得るために、対応点探索ステップ１で抽出された相似変換パラメータの各々に対して、テンプレート画像とマッチング探索の探索目標画像の候補との間の相似度がどこまで上がるかを確認しながら精度を向上させ、探索目標画像の候補に対応する相似変換パラメータの候補を導き出す処理（パラメータ推定）を行なう。そして、導き出された相似変換パラメータの候補の中から所定の基準で相似変換パラメータの最終候補を決定する。即ち、探索目標画像の最終候補をより精度良く導き出すこととなる。
その詳細な処理手順の例は、図４に示されており、これに基づいてその詳細を以下に示す。
【００４０】
（ステップＳ４０１）
対応点探索ステップ１（全探索処理）により抽出された相似変換パラメータの1つを取り出す。
（ステップＳ４０２）
個々のテンプレートエッジ点を相似変換パラメータに従い、被探索画像上の点に変換する。以降、変換されたテンプレートエッジ点を変換エッジ点という。
この変換エッジ点の座標を
（MstXti、MstYti）
ここに、i＝１、・・・、ｎ （ｎは、変換エッジ点の数）
とする。
（ステップＳ４０３）
個々の変換エッジ点に対し、一定の誤差量を加味した近傍範囲（対応点探索範囲）を設定する。この対応点探索範囲は、予め設定しておくことが好ましい。例えば、変換エッジ点を中心とする半径３画素の円に含まれる範囲を対応点探索範囲とする。
（ステップＳ４０４）
変換エッジ点毎に、（ステップＳ４０３）で設定した対応点探索範囲の中にある被探索画像のエッジ点をピックアップし、これを変換エッジ点の対応候補点とする。
i番目の変換エッジ点に対する対応候補点の座標を
（ObjXaij、ObjYaij）
ここに、j＝１、・・・、ｍ （ｍは、ピックアップされた対応候補点の数）
とする。
（ステップＳ４０５）
個々の変換エッジ点毎に、対応候補点との距離（誤差に相当する）を算出し、対応候補点が複数ある場合は距離が最小となる対応候補点を対応エッジ点とする。
このときの当該個々の変換エッジ点とそれぞれの対応候補点との距離の代用としては、計算の都合上、下記（１０）式のように距離の二乗を使用し、これを各々の変換エッジ点の誤差とする。
【数９】
この場合、距離そのもの（Li）を比較して対応エッジ点を決定することもできるが、計算処理の時間が長くなり、比較的に不利となる問題がある。
（ステップＳ４０６）
（ステップＳ４０５）で算出した全ての対応点との距離の総合値（総合誤差値）として、
【数１０】
を算出する。
この場合、総合誤差値の他の選択肢として、
Ｅ＝L1＋L2＋・・・＋Ln
を採用することも可能であるが、計算処理の時間等の問題がある。
（ステップＳ４０７）
総合誤差値が所定の誤差値（以降、閾値２ともいう）を下回っているか否かを判定し、ＹＥＳならそのときの相似変換パラメータを探索目標画像の候補に対応する相似変換パラメータの候補として抽出し（ステップＳ４０９）に進む。ＮＯの場合、（ステップＳ４０２）から（ステップＳ４０６）を所定の回数だけ繰り返しているか否かを判定し、ＹＥＳなら原則としてそのときの相似変換パラメータは不適切であったとして抽出の対象からはずし、ＮＯなら（ステップＳ４０８）に進む。
当然のことながら、閾値２は本発明の方法を実施する者が諸条件を考慮して適宜決定する。
また、上記最後のＹＥＳの場合は、単純に上記抽出の対象からはずす前にその状態を表示等の手段を使って使用者に判断させるとか、あるいは上記抽出の対象からはずすか否かの別の自動決定の基準を作りそれを実行させる新たなステップを追加する等の処置を行うことが好ましい。
（ステップＳ４０８）
変換エッジ点のそれぞれと対応する対応エッジ点との距離が総合的に最小となるように、新たな相似変換パラメータを所定の方法によって算出し、これを対応点探索ステップ１により得られた相似変換パラメータと見做して（ステップＳ４０２）に進む。
上記変換エッジ点のそれぞれと対応する対応エッジ点との距離が総合的に最小となるように、新たな相似変換パラメータを所定の方法によって算出する具体的な方法は、テンプレートエッジ点群をこのときの対応エッジ点群にマッチングさせるとした場合に最も適した相似変換パラメータをテンプレートエッジ点群とこの対応エッジ点群を使って最小二乗法により算出する方法である。本実施例のように総合誤差値をここの誤差の二乗和としたときには、誤差の二乗和を最小にする相似変換パラメータが最も適した相似変換パラメータであると考えられ、その条件を満足させられる方法が最小二乗法である。最小二乗法以外にも総合誤差値の態様に依存してロバスト推定法等の代替できる方法はある。
最小二乗法による相似変換パラメータの算出の具体的な方法については、次の段落００４１に記載する。
また、因みに付記すると、上記所定の方法で算出された相似変換パラメータは、当該変換エッジ点を得るために（ステップＳ４０２）において使用した相似変換パラメータに対してより適正なものに近づくように修正されたものになっている。そのため（ステップＳ４０２）から（ステップＳ４０８の繰返しにより相似変換パラメータは修正を繰返しより適したものに調整される。即ち、対応点探索ステップ１で抽出された相似変換パラメータは調整される。
（ステップＳ４０９）
対応点探索ステップ１により得られた、全ての相似変換パラメータに対して（Ｓ４０１）〜（Ｓ４０８）を実施する。そして、得られた相似変換パラメータの候補の中から所定の基準により相似変換パラメータの最終候補が決定される。当然のことながら相似変換パラメータの最終候補に対応する探索目標画像の最終候補が決定されていることになる。
上記所定の基準としては、対応する総合誤差値が所定の誤差値以下になっている相似変換パラメータに限定し、その中でも総合誤差値の少ない順に所定の数だけの相似変換パラメータを選び出す方法が好ましい。また、対応する総合誤差値が所定の誤差値以下になっている調整された相似変換パラメータがない場合は、その中でも総合誤差値の少ない順に所定の数だけの相似変換パラメータを選び出すこともできる。更にまた、本発明の実施の環境によって、その他の都合のよい基準を選ぶことができる。
【００４１】
以下、最小二乗法に基づいた最小二乗解を求める方法によって新たな相似変換パラメータを算出する方法について説明する。
いま、誤差を除けば相似な、テンプレートエッジ点群からなる点集合（点集合Ｇ）と（ステップＳ４０５）で求められる対応エッジ点群からなる点集合（点集合Ｈ）の２つの点集合を考える。
以下の理論では、点集合Ｈの各点が、点集合Ｇの各点と対応がとれていることが前提であるが、この前提は、点集合Ｈの各点が、対応点探索ステップ１で抽出された相似変換パラメータおよびそれ以降に（ステップＳ４０２）から（ステップＳ４０８）までの繰返し処理の中で算出された相似変換パラメータによって点集合Ｇの各点が変換された各変換エッジ点に対応する各対応エッジ点からなることにより満足されている。
いま、点集合Ｇを相似変換により点集合Ｈに重ね合わせたとき、対応する点同士の距離の総合値（距離の二乗和；総合誤差値）を最小になるように、点集合Ｇを点集合Ｈにマッチングさせることを考える。
図７に、このマッチングの理論的説明をするための点集合Ｇと点集合Ｈの関係を示す。点集合Ｇと点集合Ｈは同一の座標系ｘｙ上に配置されているものとする。
【数１１】
【００４２】
以下、最小二乗解を求める。
【数１２】
【数１３】
【数１４】
【数１５】
【００４３】
以上の理論から容易にわかるように、点集合Ｇを点集合Ｈにマッチングさせるときの相似変換パラメータの最小二乗解は、以下のようになる。
Tx ：テンプレート座標に対する被探索物座標のＸ方向並進値
Ty ：テンプレート座標に対する被探索物座標のＹ方向並進値
Tq ：テンプレート座標に対する被探索物座標の回転値
Ts ：テンプレート画像に対する被探索画像のスケール値
で定義される相似変換パラメータについて、
（１）Ｘ軸方向の並進値TxとＹ方向の並進値Tyは、（３４）式より、点集合Ｇと点集合Ｈの重心を合わせるように決めればよい。
（２）回転値Tqは、（３７）式と（４５）式から求めればよい。
（３）スケール値Tsは、（３７）式と（４４）式から求めればよい。
【００４４】
上述の対応点探索ステップ２の手順においては、対応点探索ステップ１により抽出された全ての相似変換パラメータ各々に対して、当該相似変換パラメータによってテンプレートエッジ点を被探索画像上に変換し、変換されたテンプレートエッジ点群（変換エッジ点群）に対応する被探索画像の対応エッジ点群を探し出し、変換エッジ点群と対応エッジ点群との距離の総合値である総合誤差値を最小にするようにテンプレートエッジ点群をこの対応点エッジ群にマッチングさせるとした場合に、最も適した相似変換パラメータをテンプレートエッジ点群とこの対応エッジ点群を使って所定の方法（最小二乗法）により算出し、算出された相似変換パラメータを対応点探索ステップ１で抽出された相似変換パラメータと見做して上記一連の処理を繰返し実行することを、原則として総合誤差値（評価関数）が所定の値を下回るまで行ない、相似変換パラメータを調整するパラメータ推定を行い、当該各々の相似変換パラメータの精度向上を行ない、探索目標画像の最終候補とそれに対応する相似変換パラメータを確認する処理について説明してきたが、画像マッチングの対象となるテンプレートの形状の複雑さの度合いやマッチングの要求精度によっては、「エッジ点」の代わりに「特徴点」を使う、即ち、テンプレートエッジ点および対応エッジ点の代わりにテンプレート画像の特徴点（テンプレート特徴点）および相似変換パラメータによって変換されたテンプレート特徴点群に対応する対応特徴点を使って対応点探索ステップ２の処理を行なうことによって、一定の目的を果たすことも可能である。この場合の上記総合誤差値は、変換特徴点と対応特徴点との距離の総合値である総合誤差値を用いればよく、その考え方は図４に記載してある考え方と同様である。
上述のように特徴点を用いることが可能な条件例を挙げるとすれば、 例えば、被探索物の形状が単純で、被探索画像もノイズあるいは被探索物と混ざっている物体との混同等が少ないといった条件が整うような場合には、相似変換パラメータの精度に関してある程度妥協しても画像マッチングが可能な場合が当然あり得る。
【００４５】
また、諸々の条件によっては、最初から、「テンプレートエッジ点および対応エッジ点」だけを使って対応点探索ステップ２の処理を行なうよりは、相似変換パラメータのある程度までの調整および基準に合わないものの排除による絞込み（粗調整）を「テンプレート特徴点および対応特徴点」を使って行い、後半の調整および絞込み（精調整）を「テンプレートエッジ点および対応エッジ点」によって行い、対応点探索ステップ２の処理時間を短縮することも可能となる。どの方法をとるかは、本発明の実施の条件により選択すればよい。この場合には、相似変換パラメータの粗調整と精調整における総合誤差値最小化の繰り返し処理工程の終了の判断基準である閾値２は、当然、双方で異なってくる。
【００４６】
５．パターン識別処理ステップ（図１のステップＳ１５０）
このステップは、対応点探索ステップ２で最終的に選択決定された相似変換パラメータの最終候補から最終の相似変換パラメータを決定するステップである。当然のことながら、これに応じて探索目標画像が特定されることになる。その実施例の詳細等を以下に述べる。
【００４７】
対応点探索ステップ２（周辺探索処理ステップ）により得られた探索目標画像の最終候補に対応する相似変換パラメータの確度を判断するために、当該相似変換パラメータを用いて最終目標画像の候補のエッジ点とテンプレートエッジ点との一致度を計算する。
即ち、個々の相似変換パラメータ毎に、これを用いてテンプレートエッジ点を被探索画像上に変換し、変換されたテンプレートエッジ点のＸＹ近傍領域に被探索画像のエッジ点が存在すればその数に関係なく１個とカウントし、全ての変換されたテンプレートエッジ点に対するカウントを合計したカウント値をテンプレートエッジ点の数により０〜１００の数値に正規化し、探索目標画像の最終候補のエッジ点と変換されたテンプレートエッジ点との一致度（スコア）とする。この一致度(スコア)に基づいて最終の相似変換パラメータを決定し、マッチング探索の探索目標画像を特定する。
上記のＸＹ近傍領域としては、本発明の実施の条件（例えば、マッチングの必要精度等）によって決めればよいが、注目している変換されたテンプレートエッジ点の８近傍画素を最小範囲としてステップワイズで範囲を広げられるようにすることが現実的に好ましい。
この特定の仕方の例は、一致度が最大のときの相似変換パラメータに対応する探索目標画像の最終候補を探索目標画像として特定する方法もあるし、一致度が所定の閾値（閾値３）以上であるときの相似変換パラメータに対応する探索目標画像の最終候補をすべて探索目標画像として特定することもできる。特に、探索目標画像が被探索画像内に複数個存在する場合などにおいてはこの特定の仕方が好ましい。どの方法をとるかは、本発明の方法を実施する者が決めればよいことである。
【００４８】
また、相似変換パラメータの確度を判断するために上記のような一致度（スコア）の計算方法に限る必要はなく、他の計算方法をとってもかまわないし、当該特定のための一致度評価・判定を行う所定の処理についても自由に基準を決めて行ってよい。
【００４９】
また、対応点探索ステップ２で相似変換パラメータの最終調整を変換されたテンプレート特徴点群に対応する対応特徴点を使って実施した場合は、パターン識別ステップにおける一致度を、特徴点を使って上記同様な方法で得て、これを基に最終探索目標画像を特定することも本発明の実施の結果に要求される条件によっては可能である。また、当然、上記同様エッジ点を使って得た一致度に基づいて最終探索目標画像を特定してもよい。
【００５０】
また、最終探索目標画像の特定は、上記の方法によらず、対応点探索ステップ２の（ステップＳ４０７）が終了したときの直前に、（ステップＳ４０６）で得られている誤差値を基にして行うこともできる。例えば、誤差値の最も少ないもの又は下位の所定の順位に入っている誤差値と共に得られる相似変換パラメータに対応するエッジ点を持つ画像をマッチング探索の最終探索目標画像として特定することができる。この方法は、上記の方法に比べて０〜１００の数値で当該特定の基準値を与えられないところ等、この方法を使った装置等において使用者の使い勝手が少し悪くなる場合がある可能性はあるが、実用上はなんら問題ではない。
【００５１】
本発明の技術的優位性について、発明の効果と重複する点があるが、記述する。
一般的には、エッジ点という諸々の外乱によって誤差を生じやすい特徴量を扱う場合には、投票空間を圧縮することによってその影響を回避することができるが、副作用として相似変換パラメータの精度は圧縮した分だけ低下する。
また、一般化ハフ変換においては、高精度の相似変換パラメータ値を期待しているが、投票空間の圧縮をすることによってこの精度の低下が起こったとすれば大きな問題となる。
これに対して、本発明においては、投票空間の圧縮を行い諸々の外乱により生じやすい誤差を回避する一方、「対応点探索ステップ２（周辺探索処理ステップ）」を導入することによって、圧縮による精度の低下は実質問題（副作用）とならず、対応点探索ステップ１の（ステップＳ３０５）で述べたマッチング探索の探索目標画像の候補と想定されるものを充分特定できる。
また、投票空間の圧縮、特にθ方向の圧縮は、パターンの大きさに比例して誤差が拡大する。通常の投票では、エッジ点対から得られる相似変換パラメータ上の１点のみに投票処理を行うが、本発明においては、誤差を少なくするために、投票終了後、θ方向の誤差を加味した相似変換パラメータに対応するＸ−Ｙ投票空間に追加的に投票することでθ方向の圧縮による不安定性を排除している。
また、エッジ点の誤差に関しても、投票空間を圧縮することで大部分を排除することができる。
以上のように、一般化ハフ変換による画像マッチングにおける欠点である投票空間のメモリ使用量の多さおよび相似変換パラメータ投票時のメモリアクセスコストの多さを回避し、精度の高い画像マッチング方法が実現できたことになる
【００５２】
以上の本発明に関する説明で、テンプレート画像および被探索画像の画素の単位は、テンプレートおよび被探索物の撮像画像の画素である場合でも、当該カメラによる撮像画像を予め情報圧縮した画像（例えば、４画素を１画素とした画像）の画素であってもかまわない。どちらの場合に対しても本発明は適用できる。
被探索物の形状が単純で画像マッチングにおける見分けがつきやすいとか、画像マッチングによる結果を被探索物の位置・姿勢の計測に利用する場合にその計測精度が上記画像マッチングを撮像画像の画素単位で行わなければならないほどの高さを必要としない場合等においては、後者の単位の画像、即ち、撮像画像を予め情報圧縮した画像による本発明の画像マッチング方法を採ることができる。当然、後者の場合には、前者の場合よりも処理速度の向上および使用するメモリ容量の節減が可能である。
【図面の簡単な説明】
【００５３】
【図１】本発明による画像パターンマッチング方法の主要な処理ステップの実施例の一つを示すフローチャートである。
【図２】図１の処理ステップＳ１２０の詳細を示すフローチャートである。
【図３】図１の処理ステップＳ１３０詳細を示すフローチャートである。
【図４】図１の処理ステップＳ１４０詳細を示すフローチャートである。
【図５】画素とセルの関係の１例を示す図である。
【図６】エッジマップの例を示す図である。
【図６ａ】図３のエッジマップ上のいくつかのセルのそれぞれに複数のエッジ点がプロットされている場合の１例を示す図である。
【図６ｂ】エッジ点のクラスタリングにより各セルにおける特徴点が選ばれた状態の例を示す図である。
【図７】最小二乗法によるマッチングの理論的説明をするための点集合Ｇと点集合Ｈの関係を示す図である。
【符号の説明】
【００５４】
・
【特許請求の範囲】
【請求項１】
テンプレート画像と探索目標画像の存在する画像（以降、被探索画像ともいう）の双方に対して輪郭を構成する画素（以降、エッジ点ともいう）を抽出するエッジ点抽出ステップと、
前記テンプレート画像と前記被探索画像とを選択された圧縮率に基づいて情報圧縮することによってそれぞれの画像の画素群をグループ化（当該グループをセルという）し、前記テンプレート画像と前記被探索画像のそれぞれに対して、前記セル各々において、所定の方法で計測されるエッジ方位が所定の角度範囲にあるエッジ点群を１つのクラスとするクラスタリングを行い、所定の処理基準により当該クラスを代表するエッジ点を選定し、これを特徴点とするエッジ点圧縮を行う特徴点抽出ステップと、
前記テンプレート画像の特徴点（以降、テンプレート特徴点ともいう）の座標（以降、テンプレート座標ともいう）を基準にして前記被探索画像の特徴点（被探索物特徴点ともいう）の座標（以降、被探索物座標ともいう）の相似変換パラメータを計算し、その計算値に従って相似変換パラメータによるパラメータ空間（以降、投票空間ともいう）上の投票領域（以降、投票セルともいう）に投票することを、前記テンプレート座標のそれぞれと前記被探索物座標のそれぞれとの全ての組合せに対して実施した後、所定の閾値（以降、閾値１ともいう）を超える投票値を得た投票セルに対応する相似変換パラメータを全て抽出する対応点探索ステップ１と、
前記対応点探索ステップ１により抽出された相似変換パラメータを使用して前記テンプレート画像の各エッジ点（以降、テンプレートエッジ点ともいう）を前記被探索画像上に変換し、これらの変換されたエッジ点（以降、変換エッジ点ともいう）の所定の近傍内で当該変換エッジ点から最小の距離にある被探索画像のエッジ点（以降、対応エッジ点ともいう）を探し出し、全ての変換エッジ点に対する対応エッジ点との距離の総合値（以降、総合誤差値ともいう）を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを前記対応点探索ステップ１で抽出された相似変換パラメータとみなして上記本ステップの一連の処理手順を繰り返すことによって、当該総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行い、調整された相似変換パラメータの中から所定の基準を満足する相似変換パラメータを選び出す対応点探索ステップ２と、
前記対応点探索ステップ２で調整され選び出された各々の相似変換パラメータに対応し、総合誤差値の計算の対象となった被探索画像のエッジ点群を持つ画像パターン（以降、探索目標画像最終候補ともいう）の中から、マッチング探索の探索目標画像を特定するための最終の相似変換パラメータを所定の処理により決定する被探索画像識別ステップと
を具備する画像マッチング方法。
【請求項２】
前記特徴点抽出ステップにおける所定の処理基準が、前記クラスを代表するエッジ点を、当該エッジ点が存在するクラスの中で最初にエッジ方位が計測されたエッジ点とすることを特徴とする請求項１に記載の画像マッチング方法。
【請求項３】
前記相似変換パラメータが、以下の４個のパラメータのセット、
テンプレート座標に対する被探索物座標のＸ方向並進値（Tx）
【数１】
テンプレート座標に対する被探索物座標のＹ方向並進値（Ty）
【数２】
テンプレート座標に対する被探索物座標の回転値（Tq）
【数３】
テンプレート画像に対する被探索画像のスケール値（Ts）
ここに、
MstX ：テンプレート画像の特徴点のＸ座標
MstY ：テンプレート画像の特徴点のＹ座標
Mstθ ：テンプレート画像の特徴点の方位
ObjX ：MstXに対応するべき被探索画像の特徴点のＸ座標
ObjY ：MstYに対応するべき被探索画像の特徴点のＹ座標
Objθ ：Mstθに対応するべき被探索画像の特徴点の方位
【数４】
【数５】
から構成されることを特徴とする請求項１または２に記載の画像マッチング方法。
【請求項４】
前記対応点探索ステップ１における相似変換パラメータに対応する投票空間への投票において、テンプレート座標に対する被探索物座標の回転値（Tq）に所定の範囲の誤差を加味した範囲の中で、とびとびに選択されるθ方向の誤差（Δθ）を加味した投票空間への重複投票を追加的に実施することを特徴とする請求項１から３のいずれかに記載の画像マッチング方法。
【請求項５】
前記重複投票が、前記θ方向の誤差（Δθ）に依存したウエイトによる重複投票であることを特徴とする請求項４に記載の画像マッチング方法。
【請求項６】
前記対応点探索ステップ２が、エッジ点、テンプレートエッジ点、変換エッジ点および対応エッジ点をそれぞれ、特徴点、テンプレート特徴点、変換特徴点および対応特徴点と置き換えた前記対応点探索ステップ２の処理方法に従って、前記対応点探索ステップ１で抽出された相似変換パラメータを使用して全ての変換特徴点に対応する対応特徴点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな抽出された相似変換パラメータとして上記本ステップの一連の処理を繰り返すことによって、総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、前記対応点探索ステップ１で抽出された相似変換パラメータ毎に行う粗調整ステップと、
前記粗調整ステップで粗調整された相似変換パラメータ毎に、前記対応点探索ステップ２の処理方法に従って、当該相似変換パラメータを使用して全ての変換エッジ点に対する対応エッジ点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな当該粗調整された相似変換パラメータとして上記一連の処理手順を繰り返すことによって、総合誤差値が所定の他の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を行なう精調整ステップとからなることを特徴とする請求項１から５のいずれかに記載の画像マッチング方法。
【請求項７】
前記対応点探索ステップ２が、エッジ点、テンプレートエッジ点、変換エッジ点および対応エッジ点をそれぞれ、特徴点、テンプレート特徴点、変換特徴点および対応特徴点と置き換えた前記対応点探索ステップ２の処理方法に従って、前記対応点探索ステップ１で抽出された相似変換パラメータを使用して全ての変換特徴点に対応する対応特徴点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな抽出された相似変換パラメータとして上記本ステップの一連の処理手順を繰り返すことによって、総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行うことを特徴とする請求項１から５のいずれかに記載の画像マッチング方法。
【請求項８】
前記被探索画像識別ステップにおける所定の処理が、前記対応点探索ステップ２で調整された各々の相似変換パラメータの中から、当該調整過程における最終の総合誤差値の小ささに基づいて対応する相似変換パラメータを選定し、これに対応する探索目標画像最終候補を探索目標画像として特定するものであることを特徴とする請求項１から６のいずれかに記載の画像マッチング方法。
【請求項９】
前記被探索画像識別ステップにおける所定の処理が、前記対応点探索ステップ２で調整された各々の相似変換パラメータ毎に、これを用いて前記テンプレートエッジ点を前記被探索画像上に変換し、変換されたテンプレートエッジ点の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値に基づいて、前記テンプレート画像と探索目標画像の最終候補との一致度を計算し、当該一致度の大きさに基づいて探索目標画像を特定するものであることを特徴とする請求項１から６のいずれかに記載の画像マッチング方法。
【請求項１０】
前記被探索画像識別ステップにおける所定の処理が、前記対応点探索ステップ２で調整された各々の相似変換パラメータ毎に、これを用いて前記テンプレート特徴点を前記被探索画像上に変換し、変換されたテンプレート特徴点の所定の近傍領域における被探索画像の特徴点の存否に依存するカウント値に基づいて前記テンプレート画像と探索目標画像最終候補との一致度を所定の方法で計算し、当該一致度の大きさに基づいて探索目標画像最終候補を特定するものであることを特徴とする請求項７に記載の画像マッチング方法。
【請求項１１】
前記エッジ点抽出ステップと前記特徴点抽出ステップと前記対応点探索ステップ１と前記対応点探索ステップ２と前記被探索画像識別ステップとを具備し、請求項１から１０のいずれかに記載の画像マッチング方法を実現する機能を持つことを特徴とする画像マッチングシステム。
【請求項１２】
請求項１１に記載の画像マッチングシステムに搭載され、請求項１から１０のいずれかに記載の画像マッチング方法を実現する機能を持つプログラム。
【請求項１】
テンプレート画像と探索目標画像の存在する画像（以降、被探索画像ともいう）の双方に対して輪郭を構成する画素（以降、エッジ点ともいう）を抽出するエッジ点抽出ステップと、
前記テンプレート画像と前記被探索画像とを選択された圧縮率に基づいて情報圧縮することによってそれぞれの画像の画素群をグループ化（当該グループをセルという）し、前記テンプレート画像と前記被探索画像のそれぞれに対して、前記セル各々において、所定の方法で計測されるエッジ方位が所定の角度範囲にあるエッジ点群を１つのクラスとするクラスタリングを行い、所定の処理基準により当該クラスを代表するエッジ点を選定し、これを特徴点とするエッジ点圧縮を行う特徴点抽出ステップと、
前記テンプレート画像の特徴点（以降、テンプレート特徴点ともいう）の座標（以降、テンプレート座標ともいう）を基準にして前記被探索画像の特徴点（被探索物特徴点ともいう）の座標（以降、被探索物座標ともいう）の相似変換パラメータを計算し、その計算値に従って相似変換パラメータによるパラメータ空間（以降、投票空間ともいう）上の投票領域（以降、投票セルともいう）に投票することを、前記テンプレート座標のそれぞれと前記被探索物座標のそれぞれとの全ての組合せに対して実施した後、所定の閾値（以降、閾値１ともいう）を超える投票値を得た投票セルに対応する相似変換パラメータを全て抽出する対応点探索ステップ１と、
前記対応点探索ステップ１により抽出された相似変換パラメータを使用して前記テンプレート画像の各エッジ点（以降、テンプレートエッジ点ともいう）を前記被探索画像上に変換し、これらの変換されたエッジ点（以降、変換エッジ点ともいう）の所定の近傍内で当該変換エッジ点から最小の距離にある被探索画像のエッジ点（以降、対応エッジ点ともいう）を探し出し、全ての変換エッジ点に対する対応エッジ点との距離の総合値（以降、総合誤差値ともいう）を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを前記対応点探索ステップ１で抽出された相似変換パラメータとみなして上記本ステップの一連の処理手順を繰り返すことによって、当該総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行い、調整された相似変換パラメータの中から所定の基準を満足する相似変換パラメータを選び出す対応点探索ステップ２と、
前記対応点探索ステップ２で調整され選び出された各々の相似変換パラメータに対応し、総合誤差値の計算の対象となった被探索画像のエッジ点群を持つ画像パターン（以降、探索目標画像最終候補ともいう）の中から、マッチング探索の探索目標画像を特定するための最終の相似変換パラメータを所定の処理により決定する被探索画像識別ステップと
を具備する画像マッチング方法。
【請求項２】
前記特徴点抽出ステップにおける所定の処理基準が、前記クラスを代表するエッジ点を、当該エッジ点が存在するクラスの中で最初にエッジ方位が計測されたエッジ点とすることを特徴とする請求項１に記載の画像マッチング方法。
【請求項３】
前記相似変換パラメータが、以下の４個のパラメータのセット、
テンプレート座標に対する被探索物座標のＸ方向並進値（Tx）
【数１】
テンプレート座標に対する被探索物座標のＹ方向並進値（Ty）
【数２】
テンプレート座標に対する被探索物座標の回転値（Tq）
【数３】
テンプレート画像に対する被探索画像のスケール値（Ts）
ここに、
MstX ：テンプレート画像の特徴点のＸ座標
MstY ：テンプレート画像の特徴点のＹ座標
Mstθ ：テンプレート画像の特徴点の方位
ObjX ：MstXに対応するべき被探索画像の特徴点のＸ座標
ObjY ：MstYに対応するべき被探索画像の特徴点のＹ座標
Objθ ：Mstθに対応するべき被探索画像の特徴点の方位
【数４】
【数５】
から構成されることを特徴とする請求項１または２に記載の画像マッチング方法。
【請求項４】
前記対応点探索ステップ１における相似変換パラメータに対応する投票空間への投票において、テンプレート座標に対する被探索物座標の回転値（Tq）に所定の範囲の誤差を加味した範囲の中で、とびとびに選択されるθ方向の誤差（Δθ）を加味した投票空間への重複投票を追加的に実施することを特徴とする請求項１から３のいずれかに記載の画像マッチング方法。
【請求項５】
前記重複投票が、前記θ方向の誤差（Δθ）に依存したウエイトによる重複投票であることを特徴とする請求項４に記載の画像マッチング方法。
【請求項６】
前記対応点探索ステップ２が、エッジ点、テンプレートエッジ点、変換エッジ点および対応エッジ点をそれぞれ、特徴点、テンプレート特徴点、変換特徴点および対応特徴点と置き換えた前記対応点探索ステップ２の処理方法に従って、前記対応点探索ステップ１で抽出された相似変換パラメータを使用して全ての変換特徴点に対応する対応特徴点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな抽出された相似変換パラメータとして上記本ステップの一連の処理を繰り返すことによって、総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、前記対応点探索ステップ１で抽出された相似変換パラメータ毎に行う粗調整ステップと、
前記粗調整ステップで粗調整された相似変換パラメータ毎に、前記対応点探索ステップ２の処理方法に従って、当該相似変換パラメータを使用して全ての変換エッジ点に対する対応エッジ点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな当該粗調整された相似変換パラメータとして上記一連の処理手順を繰り返すことによって、総合誤差値が所定の他の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を行なう精調整ステップとからなることを特徴とする請求項１から５のいずれかに記載の画像マッチング方法。
【請求項７】
前記対応点探索ステップ２が、エッジ点、テンプレートエッジ点、変換エッジ点および対応エッジ点をそれぞれ、特徴点、テンプレート特徴点、変換特徴点および対応特徴点と置き換えた前記対応点探索ステップ２の処理方法に従って、前記対応点探索ステップ１で抽出された相似変換パラメータを使用して全ての変換特徴点に対応する対応特徴点との距離の総合値である総合誤差値を算出し、算出された総合誤差値が所定の基準値を超えていれば当該総合誤差値が最小となるように所定の方法により当該相似変換パラメータを修正し、修正された相似変換パラメータを新たな抽出された相似変換パラメータとして上記本ステップの一連の処理手順を繰り返すことによって、総合誤差値が所定の基準値を下回るか又は前記一連の処理手順を所定の回数繰返すまで相似変換パラメータを調整する処理を、対応点探索ステップ１で抽出された相似変換パラメータ毎に行うことを特徴とする請求項１から５のいずれかに記載の画像マッチング方法。
【請求項８】
前記被探索画像識別ステップにおける所定の処理が、前記対応点探索ステップ２で調整された各々の相似変換パラメータの中から、当該調整過程における最終の総合誤差値の小ささに基づいて対応する相似変換パラメータを選定し、これに対応する探索目標画像最終候補を探索目標画像として特定するものであることを特徴とする請求項１から６のいずれかに記載の画像マッチング方法。
【請求項９】
前記被探索画像識別ステップにおける所定の処理が、前記対応点探索ステップ２で調整された各々の相似変換パラメータ毎に、これを用いて前記テンプレートエッジ点を前記被探索画像上に変換し、変換されたテンプレートエッジ点の所定の近傍領域における被探索画像のエッジ点の存否に依存するカウント値に基づいて、前記テンプレート画像と探索目標画像の最終候補との一致度を計算し、当該一致度の大きさに基づいて探索目標画像を特定するものであることを特徴とする請求項１から６のいずれかに記載の画像マッチング方法。
【請求項１０】
前記被探索画像識別ステップにおける所定の処理が、前記対応点探索ステップ２で調整された各々の相似変換パラメータ毎に、これを用いて前記テンプレート特徴点を前記被探索画像上に変換し、変換されたテンプレート特徴点の所定の近傍領域における被探索画像の特徴点の存否に依存するカウント値に基づいて前記テンプレート画像と探索目標画像最終候補との一致度を所定の方法で計算し、当該一致度の大きさに基づいて探索目標画像最終候補を特定するものであることを特徴とする請求項７に記載の画像マッチング方法。
【請求項１１】
前記エッジ点抽出ステップと前記特徴点抽出ステップと前記対応点探索ステップ１と前記対応点探索ステップ２と前記被探索画像識別ステップとを具備し、請求項１から１０のいずれかに記載の画像マッチング方法を実現する機能を持つことを特徴とする画像マッチングシステム。
【請求項１２】
請求項１１に記載の画像マッチングシステムに搭載され、請求項１から１０のいずれかに記載の画像マッチング方法を実現する機能を持つプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図６ａ】
【図６ｂ】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図６ａ】
【図６ｂ】
【図７】
【公開番号】特開２００９−１９９５７５（Ｐ２００９−１９９５７５Ａ）
【公開日】平成２１年９月３日（２００９．９．３）
【国際特許分類】
【出願番号】特願２００８−１５５３８２（Ｐ２００８−１５５３８２）
【出願日】平成２０年６月１３日（２００８．６．１３）
【特許番号】特許第４２０５７６０号（Ｐ４２０５７６０）
【特許公報発行日】平成２１年１月７日（２００９．１．７）
【出願人】（５９９１７３９５２）株式会社ファースト (16)
【Ｆターム（参考）】
【公開日】平成２１年９月３日（２００９．９．３）
【国際特許分類】
【出願日】平成２０年６月１３日（２００８．６．１３）
【特許番号】特許第４２０５７６０号（Ｐ４２０５７６０）
【特許公報発行日】平成２１年１月７日（２００９．１．７）
【出願人】（５９９１７３９５２）株式会社ファースト (16)
【Ｆターム（参考）】
[ Back to top ]