(57)【特許請求の範囲】
【請求項１】
自動画像処理システムに使用され、それぞれ既知の階調値と既知の座標点とを有する複数の画像画素で定義される画像の範囲内で対象物の位置を位置づける方法であって、
Ａ．座標点と、対応するエッジの方向と、の組から構成される複数のベクトルを使用してアブストラクトテンプレートを定義するステップであって、ここに、該座標点はそれぞれ、前記画像の範囲内の前記対象物のサイズおよび形状に対応するサイズおよび形状を有するテンプレートのエッジ上に存在し、前記画像の座標系に関して水平座標および垂直座標を有し、該対応するエッジの方向はそれぞれ、前記各座標点において前記エッジに垂直に前記座標点を通過し、前記画像の前記座標系に関する角度によって定義され、アブストラクトテンプレートは前記画像の範囲内の前記対象物の仮定された当初の回転角に基づいている、ステップと、
Ｂ．前記アブストラクトテンプレートを前記画像の部分との比較に用いるためのレンジングテンプレートに変換するステップであって、
前記座標点のそれぞれにおいて変位を選択するステップであって、変位は少なくとも１つのベクトルを有する前記テンプレートのエッジの最小サイズの半分以下である、ステップと、
前記アブストラクトテンプレートの各ベクトルについて、外側座標点と内側座標点とを計算するステップであって、ここに、該外側座標点は前記ベクトルの対応するエッジ方向を定義する角度の方向に沿って前記変位の正の値だけ前記ベクトルの座標点を変位させることによって得られ、該内側座標点は前記対応するエッジ方向を定義する前記角度と反対の方向に沿って前記変位の負の値だけ前記ベクトルの前記各座標点を変位させることによって得られ、前記外側座標点および内側座標点が前記レンジングテンプレートを定義する、ステップと、から構成されるステップと、
Ｃ．前記レンジングテンプレートを、前記画像の範囲内で複数の既知の座標点位置に変位させるステップと、
Ｄ．前記レンジングテンプレートと前記画像とを、最大相関値が得られるまで前記各位置で相関させることによって相関をとるステップと、
Ｅ．前記対象物の位置として最大相関値に対応する位置を保存するステップと、
Ｆ．前記変位をその初期値未満に減らすステップと、
Ｇ．前記アブストラクトテンプレートを、前記アブストラクトテンプレートの各ベクトルについて、外側座標点と内側座標点とを計算することによって、前記画像の部分との比較に用いるための改訂されたレンジングプレートに変換するステップであって、ここに、該外側座標点は前記ベクトルの対応するエッジ方向を定義する角度の方向に沿って前記減らされた変位の正の値だけ前記ベクトルの座標点を変位させることによって得られ、該角度は仮定された当初の回転角に近い前記対象物のあり得る回転角の組のうちの１つによって調整され、該内側座標点は前記対応するエッジ方向を定義する調整された前記角度と正反対の方向に沿って前記減らされた変位の負の値だけ前記ベクトルの前記各座標点を変位させることによって得られ、前記外側座標点および内側座標点が前記改訂されたレンジングテンプレートを定義する、ステップと、
Ｈ．前記改訂されたレンジングテンプレートを、前記最大相関値に対応する前記位置の近くに位置する前記画像の範囲内の複数の座標点位置のそれぞれに変位させる、ステップと、
Ｉ．改訂された最大相関値を得る前記位置のそれぞれにおいて前記画像と前記改訂されたレンジングテンプレートとを相関させることによって相関をとるステップと、
Ｊ．前記改訂された最大相関値に対応する位置へと対象物の位置を改訂するステップと、
を含むことを特徴とする方法。
【請求項２】
相関をとる際に用いる前記レンジングテンプレートの前記外側座標点および内側座標点のそれぞれに、前記内側座標点には負の重みを、前記外側座標点には正の重みを割り当てるステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記変位が最小値に等しくなるまで、ステップＦからＪを継続するステップであって、各ステップＦにおいて、前記変位がその前回の値の半分にされることによって減らされる、
ステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
Ｋ．仮定された当初の回転角から回転範囲を減じたものに等しい、ステップＧにおける前記ベクトルの対応するエッジ方向を定義する前記角度を設定するステップであって、ここに、回転範囲は仮定された当初の回転角に近い前記対象物のあり得る回転角の組を定義する、ステップと、
Ｌ．ステップＩからの前記改訂された最大相関値に対応する位置をステップＫからの前記角度と共に保存するステップと、
Ｍ．前記回転範囲にステップＬからの前記角度を加えることにより、ステップＧからの前記ベクトルの対応するエッジ方向を定義する新たな角度を計算するステップと、
Ｎ．新たな角度を用いてステップＧからＪまでおよびステップＬを繰り返すステップと、
Ｏ．対象物の回転角として、保存された最大相関値のうちの最も高い値を有するステップＬからの保存された角度のうちの１つを保存するステップと、
Ｐ．前記改訂された最大相関値に対応する位置に替えて、対象物の位置として保存された角度のうち１つに関連づけられた位置を保存するステップと
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
Ｑ．前記新たな角度が前記仮定された当初の回転角に前記回転範囲を加算したよりも大きくなるまでステップＭからＮまでを繰り返す、
ステップをさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
Ｒ．ステップＯからの前記回転角を前記仮定された当初の回転角に変えるステップと、
Ｓ．前記変位と前記回転範囲とをそれぞれ半分に削減し、
Ｔ．前記変位が最小の閾値となるまでステップＧからＳを繰り返す、
ステップをさらに含むことを特徴とする請求項５に記載の方法。
【請求項７】
それぞれ既知の階調値と既知の座標点とを有する複数の画像画素で定義される画像の範囲内で対象物の位置を位置づける装置であって、
Ａ．座標点と、対応するエッジの方向と、の組から構成される複数のベクトルを使用してアブストラクトテンプレートを定義する手段であって、ここに、該座標点はそれぞれ、前記画像の範囲内の前記対象物のサイズおよび形状に対応するサイズおよび形状を有するテンプレートのエッジ上に存在し、前記画像の座標系に関して水平座標および垂直座標を有し、該対応するエッジの方向はそれぞれ、前記各座標点において前記エッジに垂直に前記座標点を通過し、前記画像の前記座標系に関する角度によって定義され、アブストラクトテンプレートは前記画像の範囲内の前記対象物の仮定された当初の回転角に基づいている、手段と、
Ｂ．前記アブストラクトテンプレートを前記画像の部分との比較に用いるためのレンジングテンプレートに変換する手段であって、
前記座標点のそれぞれにおいて変位を選択する手段であって、変位は少なくとも１つのベクトルを有する前記テンプレートのエッジの最小サイズの半分以下である、手段と、
前記アブストラクトテンプレートの各ベクトルについて、外側座標点と内側座標点とを計算するステップであって、ここに、該外側座標点は前記ベクトルの対応するエッジ方向を定義する角度の方向に沿って前記変位の正の値だけ前記ベクトルの座標点を変位させることによって得られ、該内側座標点は前記対応するエッジ方向を定義する前記角度と反対の方向に沿って前記変位の負の値だけ前記ベクトルの前記各座標点を変位させることによって得られ、前記外側座標点および内側座標点が前記レンジングテンプレートを定義する、手段と、から構成される手段と、
Ｃ．前記レンジングテンプレートを、前記画像の範囲内で複数の既知の座標点位置に変位させる手段と、
Ｄ．前記レンジングテンプレートと前記画像とを、最大相関値が得られるまで前記各位置で相関させることによって相関をとる手段と、
Ｅ．前記対象物の位置として最大相関値に対応する位置を保存する手段と、
Ｆ．前記変位をその初期値未満に減らす手段と、
Ｇ．前記アブストラクトテンプレートを、前記アブストラクトテンプレートの各ベクトルについて、外側座標点と内側座標点とを計算することによって、前記画像の部分との比較に用いるための改訂されたレンジングプレートに変換する手段であって、ここに、該外側座標点は前記ベクトルの対応するエッジ方向を定義する角度の方向に沿って前記減らされた変位の正の値だけ前記ベクトルの座標点を変位させることによって得られ、該角度は仮定された当初の回転角に近い前記対象物のあり得る回転角の組のうちの１つによって調整され、該内側座標点は前記対応するエッジ方向を定義する調整された前記角度と正反対の方向に沿って前記減らされた変位の負の値だけ前記ベクトルの前記各座標点を変位させることによって得られ、前記外側座標点および内側座標点が前記改訂されたレンジングテンプレートを定義する、手段と、
Ｈ．前記改訂されたレンジングテンプレートを、前記最大相関値に対応する前記位置の近くに位置する前記画像の範囲内の複数の座標点位置のそれぞれに変位させる、手段と、
Ｉ．改訂された最大相関値を得る前記位置のそれぞれにおいて前記画像と前記改訂されたレンジングテンプレートとを相関させることによって相関をとる手段と、
Ｊ．前記改訂された最大相関値に対応する位置へと対象物の位置を改訂する手段と、
を含むことを特徴とする装置。
【請求項８】
Ｋ．仮定された当初の回転角から回転範囲を減じたものに等しい、要素Ｇにおける前記ベクトルの対応するエッジ方向を定義する前記角度を設定する手段であって、ここに、回転範囲は仮定された当所の回転角に近い前記対象物のあり得る回転角の組を定義する、手段と、
Ｌ．要素Ｉからの前記改訂された最大相関値に対応する位置を要素Ｋの設定手段からの前記角度と共に保存する手段と、
Ｍ．前記回転範囲に要素Ｌの保存手段からの前記角度を加えることにより、要素Ｇの変換手段において前記ベクトルの対応するエッジ方向を定義する新たな角度を計算する手段と、
Ｎ．新たな角度を用いて要素ＧからＪまでおよび要素Ｌの手段の動作を繰り返す手段と、
Ｏ．対象物の回転角として、保存された最大相関値のうちの最も高い値を有する要素Ｌの保存手段からの保存された角度のうちの１つを保存する手段と、
Ｐ．前記改訂された最大相関値に対応する位置に替えて、対象物の位置として保存された角度のうちに１つに関連づけられた位置を保存する手段と、
Ｑ．前記新たな角度が前記仮定された当初の回転角に前記回転範囲を加算したよりも大きくなるまで要素ＭからＮまでの手段の動作を繰り返す手段と、
をさらに備えることを特徴とする請求項７に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像をデジタル処理するためのシステムに関し、とりわけエッジで特徴付けられるパターンを自動的に位置付けるためのシステムに関する。特別に構成されたテンプレートが画像中で様々な点の周りを変位させられ、パターンを位置付ける。
【背景技術】
【０００２】
電子デジタル処理ハードウェアにおいて、画像は離散的な記憶装置に記憶される。画像は、通常数値からなる配列に分割され、各記憶位置が固有の空間座標点に対応し、画素（ピクセル）と呼ばれる記憶位置内の値がその座標点での画像の階調に対応する。図１Ａは、各画素座標点における階調が値で与えられている画像中の対象物の例を示す。
【０００３】
画像とテンプレートの相関
コンピュータ画像システムにおいて画像中の対象物を自動的に位置づける一般的な技術の１つに、相関或いはコンボリューションを用いるものがある。画像相関法には、コンボリューション、最小平均２乗誤差、最小平均絶対誤差を含む様々な種類のものがある。相関法の定義には、位置付けられるべき対象物と同様の形状を有する個別の小さな画像であるテンプレートすなわち核の決定と使用とが必要とされる。図１Ｂは、図１Ａに示す対象物と同様の形状をしたデンプレートを示す。対象物と同様に、テンブレートは各点での階調値を有する固有の座標点で表される。テンプレートは、画像中の関連領域の周囲でその位置を選択的に変位されて動かされる。画像中の新たなテンプレートの位置のそれぞれにおいて、共通の空間座標点における各画像画素に対応する値を有する各テンプレート画素の値を求めるために、積和が計算される。図１Ｃは、画像上で移動された図１Ｂのテンプレートの一位置を示す。この場合、変位に重なりがなく、積の合計は０である。相関或いはコンボリューションの計算出力は、テンプレートの形状が画像中のパターンの形状と最もマッチする位置において最大となる。図１Ｄは、画像を横断するテンプレートのすべての可能な相関を示す。数値はかなり大きくなるため、図１Ｄは、相関のおおよその相対的な指標のみを陰影の濃度によって示す。
【０００４】
離散２次元のコンボリューションの公式は、数式（１）で与えられる。
【数１】
0004494427.tif 000002
ここで、Ｉは画像、Ｋは核、ｘ及びｙは空間座標点で定義される画像座標である。ｕとｖとの総和は、テンプレート上の範囲となる。実際上、テンプレートは、位置が決定された対象物を含む画像よりも小さいものとなる。
【０００５】
正規化相関は、テンプレートの各要素の値に一定の階調因子が乗じられ、一定のオフセットが加算されることを除いて、相関に類似する方法として知られている。各テンプレート変位において、階調因子とオフセットとは、画像位置のそれぞれにおけるテンプレートの相関における誤差が最小となるように独立して調整される。テンプレートマッチングにおける正規化相関は、VISION '87 Conference Proceedingの5-33〜5-55ページにあるWillian Silverによる"Alignment and Gauging Using Normalized Correlation Search"と題された記事に詳細に述べられており、引用して具体化する。
【０００６】
最小平均２乗誤差法では、各テンプレートの点が対応する画像の点から減算され、それぞれの差が２乗される。そして、すべての差の平均が計算される。最小２乗誤差の公式は、数式（２）で与えられる。
【数２】
0004494427.tif 000003
ここで、Ｎは核中の画素の数である。最小平均２乗誤差の計算出力は、テンブレートの形状が画像中のパターンの形状と最もマッチする位置において最小となる。最小平均絶対誤差法では、各テンプレートの点が対応する画素の点から減算され、それぞれの差の絶対値が計算される。そしてすべての差の平均が計算される。最小絶対誤差の公式は、数式（３）で与えられる。
【数３】
0004494427.tif 000004
【０００７】
最小絶対誤差の計算結果も、テンプレートの形状が画像中のパターンの形状と最もマッチする位置において最小となる。上記の技術は、それ自体が濃淡画像であるテンプレートを、座標位置が関連する画像の範囲内にある対象物を含む対応する濃淡画像の周囲で、その位置を変位させるという意味において実質的に同一である。各位置において、隣接する画像の画素の値と共通の座標点において対応するテンプレートの値とにある関数が適用される。その結果は、座標点での各画素が、デンブレートがその点における画像中の対象物とどれくらい一致するかを示す１つの数値となる別の画像となる。
【０００８】
２値ベクトル相関
ベクトル相関或いはコンボリューションは、上述した相関法の代わりとなる接近法を提供するものである。ベクトル相関では、画像と選択されたテンプレートとは、ベクトルである画素によって構成される。２値ベクトル相関の理論は、IEEE Transactions on Systems, Man, and Cybernetics, Nov./Dec., 1989, vol.19, no.6の16 36~16 44ページにあるS. S. Wilsonによる"Vector Morphology and Iconic Neural Networks"と題された論文に述べられており、引用して具体化する。同様の技術が、19 91年Wiley‐Interscience刊のNeural and Intelligent Systems Integrationの１３５〜１６０ページにあるS. S. Wilsonによる"Teaching network connections for real‐time object recognition"と題された論文にさらに述べられている。簡単にいえば、２値ベクトル相関は、濃淡画像をいくつかの２値画像に変容させることからなる。ここで、２値画像の合成画像は、ベクトル画像中の各画素が２値画像の１つからそれぞれなるいくつかの構成要素を有するという意味でのベクトルで表される。次に、パターンを認識するために、ベクトルテンプレートが定義される。ベクトルテンプレートも、同数のベクトル画像としての構成要素からなる。
【０００９】
ベクトルテンプレートの位置は、画像中の関連領域の周囲でその位置を変位され、動かされる。各位置においてンテンプレート中のベクトル画素と、対応する座標点での画像中のベクトル画素とを求めるために内部積（すなわちドット積）の合計が計算される。数学的な観点では、離散２次元ベクトルコンボリューションの公式は、（４）で与えられる。
【数４】
0004494427.tif 000005
ここで、Ｊはベクトル画像、Ｋはベクトル核、ｘ及びｙは画像座標である。ｕとｖとの総和は、テンプレート上の範囲となる。
【００１０】
以下、ベクトル相関の技術を詳細に示す。画像を入力すると、最初に、水平有限差分と呼ばれる異なる画像を、入力画像の画素の値から右側に最小距離で変位する隣接画素の値を減算することによって形成する。結果の画像は、際だった垂直エッジがある座標点の周囲で正または負の大きな値を含むものとなる。水平有限差分画像中の正の値はイーストエッジと呼ばれ、左から右に向かって濃度が減少するエッジであることを示す。水平有限差分画像中の負の値はウエストエッジと呼ばれ、左から右に向かって濃度が増加するエッジであることを示す。
【００１１】
２番目に、垂直有限差分と呼ばれる異なる画像を、入力画像の画素の値から上方に最小距離で変位する隣接画素の値を減算することによって形成する。結果の画像は、際だった水平エッジがある座標点の周囲で正または負の大きな値を含むものとなる。垂直有限差分画像中の正の値はノースエッジと呼ばれ、上方に向かって濃度が減少するエッジであることを示す。垂直有限差分画像中の負の値はサウスエッジと呼ばれ、下方に向かって濃度が増加するエッジであることを示す。
【００１２】
２値ベクトル相関では３番目に、各画素が４つの磁針方向に対応するＮ、Ｓ、Ｅ及びＷとラベルされた４つの２進数値からなるベクトルを含む２値ベクトル画像を形成する。２進数Ｎは、垂直有限差分を閾値と呼ばれる小さな正の数と比較し、それらの値が閾値を超える場合には２進数の１を、それ以外は２進数の０を割り当てることによって計算される。２進数Ｓは、垂直有限差分を負の閾値と比較し、それらの値が閾値より小さい場合には２進数の１を、それ以外は２進数の０を割り当てることによって計算される。ＥとＷの２値要素は、水平有限差分画像を用いて同様の方法で計算される。
【００１３】
最後に４番目として、ベクトルテンプレートの位置を、原画像の関連領域の範囲内で変位させる。画像中の新たな位置のそれぞれで、内部積の合計が、対応する座標点で原画像中の各ベクトル画素に対応するデンプレート中の各ベクトル画素の値を求めるために計算される。
【００１４】
図２Ａは、水平有限差分と垂直有限差分との両方を用いたエッジ検出後のベクトル画像の例である。画像中での各座標点がベクトルとして描かれているが、０でない要素のラベルのみを描いて簡略化している。実際には２つの要素が、Ｎ及びＷなどの０でないものとすることはできるが、図２Ａの例では示されていない。図２Ｂは、水平有限差分画像と垂直有限差分画像の両方と所定の閾値とを用いて形成された、対応するベクトルテンプレートである。図２Ｂのテンプレートが図２Ａの画像の周囲でその位置を移動されたとき、図２Ｃにおおよそ示す相関結果が得られるのは明らかである。
【００１５】
ベクトル相関の利点
ベクトル相関は、パターンのエッジとの相関であり、非常に正確である。図２Ｃを参照すると、画像中のパターンの正確な位置からのテンプレートのわずかなオフセットは、テンプレートのエッジのほとんどがパターンと完全にミスコンタクトし、相関が得られないことを意味している。しかしながら、図１Ｄに示すように、通常の相関が用いられた場合には、画像がテンプレートと部分的にコンタクトする広い領域がある。
【００１６】
ベクトル相関は、パターンのエッジがひどく劣化していない限り、劣化した画像中のパターンを位置させることができる。劣化した画像は、関連するパターンを取り囲んで大きく乱れ、或いはパターン中で断片を失っている。通常の相関では、パターンを取り囲んでいる雑音から区別することができない。通常の相関では、テンプレートの画像が使用される。このため、対象物の視覚的特質がテンプレートとして用いられている対象物と実質的に異なれば、テンプレートマッチングは正確な結果を与えることができない。ベクトル相関は、対象物の重要なエッジ形状のみが対象物を識別するために用いられるので、通常の相関よりも優れている。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
ベクトル相関の問題点
ベクトル相関においては、ベクトル画像を形成して処理する特別なステップのために、徹底的な計算がされる。第１に、有限差分と算出されたエッジとを記憶するための記憶装置の必要量が増加する。第２に、探索すべきパターンを特徴付けるために使用されるテンブレートはベクトルであり、定義するのがより複雑となる。第３に、斜めのエッジは、正確に表されない。ノース方向とイースト方向とに斜めとなっているエッジは、同一の点に表されたノース及びイーストのエッジの両方を有するデンプレートによって表されなければならない。テンプレート中の斜めの点は、取り扱いがより困難になる。最後に、この方法は、高性能の並列プロセッサに限定される。
【００１８】
１または２のユニットを取り囲む小さな有限差分座標変位を使用すると、非常に狭小な有限差分画像のエッジが生成される。相関デンプレートがベクトル画像上で動かされると、狭小なエッジは相関に強度の局所性を与え、画像へのテンプレートのパターンマッチングに高い正確性をもたらす。しかしながら、パターンの位置は未知なので、一般に、パターンが探索されるまでに、テンプレートは多くの位置上を移動されなければならない。このことが、きめ細かい探索として引用される。この場合の未知のパターンは、デンプレートがどの位置でもフィットしないようにわずかに回転させられれば、失われてしまう。
【００１９】
有限差分は、単純な画像にはより大きく作成される。たとえば、１０のユニットを取り囲む有限差分座標変位は、１０画素の幅で探索すべき回転されたパターンを許すエッジを導く。さらに、パターンは、水平及び垂直方向の両方で１０ユニットまでを取り囲むステップにおいて徹底的にではなく、粗い格子内で画像上でテンプレートをサンプリングすることによって探索される。この例では、探索は１０の２乗、すなわち１００倍速くなる。しかしながら、パターンが探索された場合、正確性に乏しいものとなる。
【００２０】
妥協点として、エッジ検出は、粗く探索してパターンのおおよその位置を得、きめ細かい探索でパターンを合わせることが行われる。大きな有限差分で１回、小さな有限差分で１回の計２回行わなければならない。大容量の記憶装置と高性能の並列プロセッサとが、依然として必要とされる。
【課題を解決するための手段】
【００２１】
本発明は、画像中で対象物を自動的に位置させるシステムを教示する。画像は、それぞれ既知の階調値と既知の座標点とを有する複数の画像画素によって定義される。
【００２２】
本発明は、１つの処理に結合されたエッジ検出とパターン探索との組み合わせを用い、計算の複雑性が限られた範囲で、非常な柔軟性を提供する。最初に、対象物の見積もりに対応するマニュアルデンプレートが決定される。マニュアルテンプレートは、座標点と対応するエッジ方向のセットからなるベクトルの散在的なセットから構成されるアブストラクトテンプレートに変換される。各座標点は、マニュアルテンプレートのエッジ上にあり、対応するエッジ方向は、その座標点におけるエッジと垂直にその座標点を通過する。次に、アブストラクトテンプレートは、レンジングテンプレートに変換される。レンジングデンブレートは。対応するエッジ方向に沿ったアブストラクトテンプレートの各ベクトルの座標点から等間隔で配置されるように定義された座標点の対から構成される。正の座標点は、予め選択された変位の正の値に対応し、負の座標点は、同様の変位の負の値に対応する。レンジングテンプレートは、画像の範囲内で複数の既知の座標点位置のそれぞれに変位させられる。各位置において、レンジングテンプレートは画像と相関される。相関が向上し、画像の範囲での対象物の位置の見積もりがより正確となるように、異なるアブストラクト及びレンジングテンプレートが動的に再構成され、回転させられる。ベクトル相関の利点は保持されるが、エッジ検出が削減され、限られた数のみの座標点が必要とされるので、計算の負荷が削減される。エッジ検出した画像が記憶されないという点において、計算に要求される記憶装置が少なくなる。
【発明を実施するための最良の形態】
【００２３】
図３Ａ〜図３Ｄに図示するように、本発明は、画像２２内における対象物２０の座標点位置を位置づけるために用いられる自動画像処理システムに関する。図示した画像２２は、複数の画像画素からなる２次元のものである。各画像画素は、それぞれ既知の階調値と既知の座標点とを有する。座標点は、水平方向のｘ軸と垂直方向のｙ軸とによって定義される。このシステムは、最終的に画像２２内における対象物２０の座標点を決定する。
【００２４】
最初に、システムは、エッジ２６によって境界を定義したポシブルテンプレート２４をマニュアル操作で決定する。図示するように、テンプレート２４は、対象物と可能な限り一致する形状及び大きさに設定される。テンプレート２４が定義されると、コンピュータの記憶位置に容易に格納されるＮ個のベクトル（ｕ１，Ｖ１，θ１）、（ｕ２，ｖ２，θ２）、…（ｕＮ，ｖＮ，θＮ）によって定義されるアブストラクトテンプレート２８に変換される。
【００２５】
図３Ａに図式的に、及び図３Ｂにテーブルの形態で示すように、Ａ〜Ｉの各ベクトルは、それぞれテンプレートのエッジ２６の水平及び垂直座標及び水平座標点（ｕｉ，ｖｉ）となる座標点ｕｉ，ｖｉでの組で与えられる。座標点は、以下に述べるように、画像２０の座標系にマップすることができる。各座標点と関連付けて、座標点の位置で対応するエッジ２６に直交する対応する矢印θｉで示すエッジ方向がある。各矢印の末端はテンプレート２４の境界より内側あり、−方、各矢印の先端はテンプレートの外側にある。画像２２のｘ及びｙ軸に沿った対象物２０の位置の決定を同等に正確にするため、マニュアルテンプレート２４の実質的に垂直及び実質的に水平な範囲に沿ってＮとほぼ同数のベクトルがある。同一のベクトルが、水平及び垂直成分の両方を同時に有していてもよい。図３Ａに示すように、３つのベクトルが各水平及び垂直範囲に存在し、１つ以上のエッジを含む。たとえば、これら３つのエッジは、図３Ａの最右の垂直範囲を含む。
【００２６】
計算の複雑性を最小にするため、限られた数だけのエッジの点がベクトル（ｕｉ，ｖｉ，θｉ）に変換されることが必要とされる。しかしながら、エッジ間に十分に大きな角度差がない隣接するエッジでない限り、少なくとも１つのベクトルがマニュアル決定テンプレートのそれぞれ異なるエッジに用いられることが望ましい。図３Ａに示すように、エッジ２６のそれぞれは、アブストラクトテンプレート２８の一部分からなる少なくとも１つのベクトルを含む。
【００２７】
テンプレート２４がアブストラクトテンプレート２８のベクトルに変換されると、図３Ｃに示すように、レンジングテンプレート３０が形成される。レンジングテンプレートは、アブストラクトテンプレート２８の各ベクトル（ｕｉ，ｖｉ，θｉ）用の座標点（ｕｐｉ，ｖｐｉ）及び（ｕｎｉ，ｖｎｉ）を用いて定義される。点（ｕｐｉ，ｖｐｉ）は、方向θｉに沿った正の変位δによって生成され、点（ｕｎｉ，ｖｎｉ）は、方向θｉに沿った負の変位δによって生成される。前者の座標点は、マニュアル決定テンプレート２４のエッジ２６で定義される境界の外側に存在し、一方、後者の座標点は、境界の内側に存在する。数学的には、（ｕｐｉ，ｖｐｉ）＝（ｕｉ＋δｃｏｓθｉ，ｖｉ＋δｓｉｎθｉ）及び（ｕｎｉ，ｖｎｉ）＝（ｕｉ−δｃｏｓθｉ，ｖｉ−δｓｉｎθｉ）である。しかしながら、レンジングテンプレート３０が用いられる前に、テンプレートの座標点に重みを割り当てなければならない。たとえば、例示した実施の形態では、正の変位を有する点（ｕｐｉ，ｖｐｉ）用の重みは＋１であり、負の変位を有する点（ｕｎｉ，ｖｎｉ）用の重みは−１である。小さな白四角は負の重みを有するレンジングテンプレートの座標点を表し、小さな黒四角は正の重みを有するレンジングテンプレートの座標点を表す。レンジングテンプレート３０における非常に散在した座標点の組み合わせによる＋１または−１の重みを有することによって、相関の公式は非常に単純となる。
【数５】
0004494427.tif 000006
ここで、Ｉは画像２２、ｘ及びｙは画像の座標点、ｕ及びｖは上記で定義したレンジングデンプレート３０の座標点である。この公式での表記は、正の項Ｐｉ＝Ｉ（ｘ−ｕｐｉ，ｙ−ｖｐｉ）及び負の項Ｎｉ＝Ｉ（ｘ−ｕｎｉ，ｙ−ｖｎｉ）を代入することによって簡略化される。
【数６】
0004494427.tif 000007
変位δが大きければ計算速度は向上するが、少なくとも１つのベクトルを有するテンプレート２４のうちのエッジの最小サイズの半分程度よりは大きくならない。しかしながら、計算結果が不正確となりうる。図３Ｃに例示するように、アブストラクトテンプレート２８のベクトルＣ及びＤを用いて決定した座標点（ｕｎｉ，ｖｎｉ）は、互いに非常に隣接したものとなる。変位δがさらに大きくなれば、座標点が互いに通り抜け、望ましくない結果となる。たとえば、アブストラクトテンプレート２８では、最短のサイズは１０ユニット程度の長さとなる。変位δが３ユニットに設定されると、結果として得られたレンジングテンプレート３０は、３ユニットまでの範囲で対象物の中心から外れていても、対象物２０のパターンを検出することができる。このため、対象物２０は、６×６格子を用いて散在的に探索することによって探し出すことができる。しかしながら、画像２２における対象物２０の位置は、±３画素以上正確には探索されない。図３Ｄは、テンプレートが際だって中心から外れ、対象物２０が際だって回転している場合でも、レンジングテンプレート３０と画像２２内の対象物２０とが一致することを示す。
【００２８】
図４Ａは、回転されていない対象物のｘ軸に沿ったレンジングテンプレートの動きの関数として数式（６）を用いた相関のプロファイルである。レンジングテンプレート３０は変位δ＝３を有するので、最大相関は、６ユニットの幅を有する。本発明が使用される産業環境における実際の対象物の不規則でわずかにかすんだエッジは、０相関となるように最大相関から徐々に減少する結果となる。
【００２９】
図４Ｂを参照すると、他のレンジングテンプレート３０’が変位δ＝１ユニットを選択することによって生成される。得られたレンジングテンプレート３０’は、テンプレートが１ユニット以下の範囲で対象物２０の中心から外れている場合のみに、画像２２中の対象物２０を検出することができる。このため、対象物２０は、入力画像２２中のすべての位置を探索することによってのみ探し出される。しかしながら、対象物２０の中心は、１ユニットの正確性で探し出すことができる。図４Ｃは、水平方向ｘ軸に沿ってδ＝１であるレンジングテンプレート３０’の動きとして数式（６）を用いた相関のプロファイルである。産業環境での画像にとって、相関プロファイルは、相関のピークについて放物線を逆にしたものとほぼ同様になる。最もフィットする放物線の数学的な中心が画素のサイズよりもかなり小さいほどの正確性を導けることがわかるであろう。
【００３０】
図４Ａ及び４Ｃに示すプロファイルは、公式（６）でのベクトル相関の公式が、正規化相関の方法に従って変化しうることを示している。この発明の正規化公式は数式（７）で示される。
【数７】
0004494427.tif 000008
画像２２中の画素を示す各座標点の照度に任意の定数が乗算され、他の任意の定数が画素を表す各座標点の値に加算されるのであれば、相関ｃｏｒｒ’（ｘ，ｙ）の結果が変化しないことは、当技術分野の技術者には容易に立証できる。このため、正規化相関の公式は、照明レベル及びコントラストに従属しない相関の値を生成する。さらに、相関の値は、完全相関の１以下で、質の悪い相関の０以上となる。
【００３１】
本発明のシステムにおける動的処理を、図５のフローチャートに示す。ここでは、画像２２中で位置付けられる対象物２０の水平及び垂直方向の最小長は、１６ユニット程度であるものと仮定する。変位δは、上記した理由により１６ユニットの半分の８ユニットの最大値が設定される。最初に、対象物２２は回転されていないものと仮定する。従って、θＴｉの値は、０に等しくなる。しかしながら、回転ΔθＴの可能な範囲の正の変化は、後に使用する所定の値に設定される。ここでは、８に設定される。その後、位置５２においてポシブルテンプレート２４’がマニュアル操作で決定される（５２）。このマニュアルテンプレートは、上述したように、位置５４において簡略化したベクトル表記を用いてアブストラクトテンプレート２８’に変換される。次に、ベクトル表記の形態のアブストラクトデンプレート２８’は、位置５６においてレンジングテンプレート３０’’に変換される。位置５８では、レンジングデンプレート３０’’は、画像２２の範囲内での新たな位置に動かされる。レンジングデンプレート３０’’のサイズは、８ユニットの値をとるδの使用を含むので、レンジングテンプレートは１６×１６探索格子内の画像上で動かされ、位置６０においてそれぞれの新しい位置での正規化相関が計算される。新たな位置のそれぞれにおいて正規化ベクトル相関が計算されると、位置６２においてその値が予め設定された閾値と比較される。ここでは、この値は０．５に設定されている。この値が０．５よりも小さい場合には、位置６４に示すように、すべての画像位置が試行されていない限り、レンジングテンプレート３０’’は、画像２２の範囲で新たな探索範囲に動かされる。
【００３２】
すべての画像位置が試行され、受け入れ可能な最小の閾値に達しない場合には、対象物２０が画像２２中になかったとして、位置６５において正確に対象物が探索されないとことをシステムが応答することも可能である。しかしながら、システムが対象物を探索できなくても、対象物が実際に存在することが確証できる場合には、点線矢印６６，６８及び７０で示すように、３つの選択肢をとることができる。典型としては、位置５６において変位δにより大きな値を選択する。また、位置５４においてマニュアルテンプレート２４からアブストラクトテンプレート２８’への変換により多くのベクトルを用いてもよい。さらに、位置５２において異なるマニュアルデンプレート２４をマニュアル操作で選択してもよい。その後、位置６２で閾値が満足させられるまで、正規化されたベクトル表記が画像２２中の異なる位置のそれぞれで再び計算される。位置６２で正規化相関の最小の閾値が満足すると、画像中２２中の対象物２０の座標位置に最もよく対応して求められた相関における画像２２の範囲でのレンジングテンプレート３０’’の位置ｘｍ、ｙｍを保存する。そして、位置７６で変位δを半分に削減し、対象物２０の回転可能範囲△θＴを半分に削減する。これにより、上記に与えられた情報を使用すると、δ及び△θＴは、いずれも４となる。θＴＩが０の時、対象物２２の回転角度に対応するθＴの値は、−４となる。これら新しい値を用いて、位置７８では、２次元空間において座標点を回転するための標準公式に従ってアブストラクトデンプレート２８’が新たなアブストラクトテンプレート２８’’に変換される。
【数８】
0004494427.tif 000009
【数９】
0004494427.tif 000010
【数１０】
0004494427.tif 000011
【００３３】
アブストラクトテンプレートにおけるエッジ方向の角度も、回転させられる。そして、図５のフローチャートの位置８０に示すように、新たなアブストラクトテンプレート２８’’が新たなしンジングテンプレート３０’’’に変換される。レンジングテンプレート３０’’のための１６×１６の最初の格子サイズと異なり、レンジングテンブレート３０’’’のための格子サイズは、半分すなわち８×８となる。フローチャートの位置８２に示すように、最初に記憶された位置ｘｍ、ｙｍの周囲で異なる位置にレンジングテンプレート３０’’’を動かすことによって、最大正規化相関は、記憶すべき最大正規化相関に対応する最良の位置を用いたｘｍ、ｙｍのより正確な仕様とθＴの値とを決定することができる。位置８４に示すように、次に、直前のθＴの値を取得し、位置７６で決定した△θＴの値を加算することで、θＴを再計算する。フローチャートの位置８６でθＴ≦θＴｉ＋△θＴｉが満たされている限り、位置７８、８０、８２及び８４のステップが繰り返される。こうして、ここでは、最大相関の値が、３つの異なるθＴの値−４、０及び＋４に対応する３つの異なる画像２２中のレンジングデンプレートの位置ｘｍ、ｙｍ用として保存される。位置８８では、保存された値のうちで最大相関δ＝４を与えるθＴが決定され、レンジングテンプレート３０’’’による対象物２２の対応する位置が決定され、ｘｍ、ｙｍ及びθＴｉとして保存される。変位δ＝４であるデンプレート３０’’の強度が最も強い相関の位置と角度とが、さらに小さい変位δ＝２ユニットを有するレンジングテンプレート３０’’’’を使用した新たな探索のための開始ポイントとなる。直前で最良だった角度から回転角度θＴ＝−２、０及び＋２度が、よりおおよその回転θＴ及び位置ｘｍ、ｙｍを探索するために用いられる。より小さな変位と角度とがアブストラクトデンプレート２８から新たなレンジングテンプレートを算出するために用いられ、変位δが所定の最小値となるまで同様の方法によって関連パターンの探索が続けられる。フローチャートの位置９０に示す値は、１である。変位が１となると、本発明のシステムは、位置９２に示すように、適切な回転角度θＴに対応する画像２２中の対象物２０の座標位置ｘｍ、ｙｍを決定することを中止する。当技術分野における技術者であれば、多次元空間で関数の最大値を位置付けるための方法も、上記方法の一部と類似することがわかるであろう。多次元空間における勾配法は、1986年Cambridge University Press刊のW. Press, B Flannery, S. Teukolsky及びW. Vetterlingによる”Numerical Recipes the Art of Scientific Computing”の第10章に述べられており、引用して具体化する。
【００３４】
１つの処理でエッジ検出とパターン探索とを使用することにより、大変な柔軟性が与えられると共に、複雑なコンピュータ操作の必要性が削減される。このため、簡略化したベクトル表記を有するアブストラクトテンプレートを使用することにより、解像度の増加した画像２２の周囲で異なる位置に動かすことができる広い範囲の互いに異なるレンジングテンプレートを動的に変化させて生成できるという利点がある。画像２２中の対象物の位置及び回転角度を、各座標位置や最初にマニュアル操作で決定されたテンプレート２４のエッジを含む各点の対応する階調を記憶することなく、所望の正確性で、高速に位置あわせすることができる。好ましくは、本発明のシステムは、当技術分野における技術者に公知の標準的なコンピュータハードウェア及びソフトウェアを用いて実行されるものとすることができる。画像２２の対象物２０は、陰極管線（ＣＲＴ）から構成される通常のスクリーン上に表示されるものとすることができる。このシステムは、これらに限定されるものではないが、磁気テープ及びディスク、光学ドライブ、コンパクトディスクドライブ及び紙を含む様々な記憶媒体によってソフトウェアとして記憶させてもよい。本発明の好ましい実施の形態を開示した。しかしながら、当技術分野における通常の技術を有するものは、ある程度の変形がこの発明の教示の範囲に含まれることがわかるであろう。従って、以下の請求の範囲が、本発明の本来の範囲及び内容を決定するために検討されるべきである。
【図面の簡単な説明】
【００３５】
【図１Ａ】対象物の階調画像の例である。
【図１Ｂ】図１Ａの画像中の対象物の位置を探し出すためのデンプレートの例である。
【図１Ｃ】図１Ａの画像上で位置をずらされた図１Ｂのテンプレートの一位置を示す。
【図１Ｄ】画像中の対象物と画像の周囲を移動させられるテンプレートとの相関のおおよその指標を陰影の濃度によって示す。
【図２Ａ】２値ベクトル画像の例である。
【図２Ｂ】２値ベクトルテンプレートの例である。
【図２Ｃ】２値ベクトル画像中の対象物と画像の周囲で移動された２値ベクトルテンプレートとのベクトル相関の結果を示す。
【図３Ａ】本発明にかかる簡略したベクトル形式に変換されたマニュアル決定テンプレートを示す。
【図３Ｂ】図３Ａのアブストラクトベクトルテンプレート用のテーブルを示す。
【図３Ｃ】δ＝３の変位を有する図３Ｂのアブストラクトテンプレートから得られたレンジングテンプレートを示す。
【図３Ｄ】画像中でずれて回転された対象物に一致する図３Ｃのレンジングテンプレートを示す。
【図４Ａ】図３Ｃのレンジングテンプレートのための相関の水平プロファイルである。
【図４Ｂ】δ＝１の変位を有する作成されたレンジングテンプレートである。
【図４Ｃ】図４Ｂのレンジングテンプレートのための相関の水平プロファイルである。
【図５】本発明のシステムを使用して対象物を探し出すための有効な方法を示すフロー図である。
【符号の説明】
【００３６】
２０  対象物
２２  画像
２４  ポシブルテンプレート
２６  エッジ
２８  アブストラクトテンプレート
３０  レンジングテンプレート
【図１Ａ】
0004494427.tif 000012
【図１Ｂ】
0004494427.tif 000013
【図１Ｃ】
0004494427.tif 000014
【図１Ｄ】
0004494427.tif 000015
【図２Ａ】
0004494427.tif 000016
【図２Ｂ】
0004494427.tif 000017
【図２Ｃ】
0004494427.tif 000018
【図３Ａ】
0004494427.tif 000019
【図３Ｂ】
0004494427.tif 000020
【図３Ｃ】
0004494427.tif 000021
【図３Ｄ】
0004494427.tif 000022
【図４Ａ】
0004494427.tif 000023
【図４Ｂ】
0004494427.tif 000024
【図４Ｃ】
0004494427.tif 000025
【図５】
0004494427.tif 000026