(57)【要約】【課題】予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出方法等において、逆フーリエ変換等の複雑な処理を行うことなく、安価で高速に実現可能とする。【解決手段】パターン検出方法は、登録画像および入力画像の直交座標をそれぞれ対数・極座標に変換するステップと、所定のサンプリング周期で離散化するステップと、離散化された登録画像および入力画像をそれぞれ離散フーリエ変換するステップと、離散フーリエ変換された登録画像および入力画像に基づき、位相限定合成を演算するステップと、離散フーリエ変換された入力画像に位相限定合成の複素共役を積算して、補正された入力画像を演算するステップと、補正された入力画像と登録画像との相関値を演算するステップと、演算された相関値に基づき、入力画像中から登録画像のパターン検出を行うステップとを備える。【選択図】図９
2004326728.tif 000002
【特許請求の範囲】
【請求項１】
予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出を行うパターン検出装置であって、
外部から入力画像を入力し保持するための入力画像記憶部(1)と、
検出すべき登録画像を記憶するための登録画像記憶部(2)と、
前記入力画像記憶部(1)および登録画像記憶部(2)から各々の画像データを読み取り、登録画像および入力画像を構成する各画素の極座標に基づきそれぞれフーリエ変換し、フーリエ変換された登録画像および入力画像に基づき位相成分を抽出して、位相成分を合成して得られる位相限定合成の複素共役をフーリエ変換された入力画像に積算して入力画像を補正し、補正された入力画像と登録画像との相関値を演算し、演算された相関値に基づき入力画像中から登録画像のパターン検出を行うための画像処理部(3)と、
を備えることを特徴とするパターン検出装置。
【請求項２】
予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出を行うパターン検出装置であって、
外部から入力画像を入力し保持するための入力画像記憶部(1)と、
検出すべき登録画像を記憶するための登録画像記憶部(2)と、
前記入力画像記憶部(1)および登録画像記憶部(2)から各々の画像データを読み取り、登録画像および入力画像を構成する各画素の直交座標をそれぞれ極座標に変換する極座標変換部と、
前記極座標変換部で変換された登録画像および入力画像の極座標を、それぞれ所定のサンプリング周期でサンプリングするサンプリング部と、
前記サンプリング部でサンプリングされた登録画像および入力画像をそれぞれ離散フーリエ変換する離散フーリエ変換部と、
前記離散フーリエ変換部でフーリエ変換された登録画像および入力画像に基づき、位相限定合成を演算する位相限定合成部と、
前記フーリエ変換部でフーリエ変換された入力画像に前記位相限定合成部で演算された位相限定合成の複素共役を積算して、補正された入力画像を演算するための複素共役積算部と、
前記複素共役積算部で補正された入力画像と登録画像との相関値を演算する相関演算部と、
前記相関演算部で演算された相関値に基づき、入力画像中から登録画像のパターン検出を行うパターン検出部と、
を備えることを特徴とするパターン検出装置。
【請求項３】
請求項１または２のパターン検出装置であって、
前記極座標変換部が各画素の直交座標をそれぞれ対数・極座標に変換することを特徴とするパターン検出装置。
【請求項４】
予め登録された登録データを入力データ中から検索するパターン検出方法であって、
登録データを構成する各データの極座標に基づいてフーリエ変換を行うステップと、
入力データを構成する各データの極座標に基づいてフーリエ変換を行うステップと、
前記フーリエ変換された登録データおよび入力データから位相限定合成を演算するステップと、
前記フーリエ変換された入力データに位相限定合成の複素共役を積算して、補正された入力データを演算するステップと、
補正された入力データと登録データとの相関値を演算するステップと、
演算された相関値に基づき、入力データ中から登録データの検出を行うステップと、
を備えることを特徴とするパターン検出方法。
【請求項５】
予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出方法であって、
登録画像を構成する各画素の極座標に基づいてフーリエ変換を行うステップと、
入力画像を構成する各画素の極座標に基づいてフーリエ変換を行うステップと、
前記フーリエ変換された登録画像および入力画像から位相限定合成を演算するステップと、
前記フーリエ変換された入力画像に位相限定合成の複素共役を積算して、補正された入力画像を演算するステップと、
補正された入力画像と登録画像との相関値を演算するステップと、
演算された相関値に基づき、入力画像中から登録画像のパターン検出を行うステップと、
を備えることを特徴とするパターン検出方法。
【請求項６】
予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出方法であって、
登録画像および入力画像を構成する各画素の直交座標をそれぞれ極座標に変換するステップと、
極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化するステップと、
離散化された登録画像および入力画像をそれぞれ離散フーリエ変換するステップと、
離散フーリエ変換された登録画像および入力画像に基づき、位相限定合成を演算するステップと、
前記離散フーリエ変換された入力画像に位相限定合成の複素共役を積算して、補正された入力画像を演算するステップと、
補正された入力画像と登録画像との相関値を演算するステップと、
演算された相関値に基づき、入力画像中から登録画像のパターン検出を行うステップと、
を備えることを特徴とするパターン検出方法。
【請求項７】
請求項６のパターン検出方法であって、
極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する際、サンプリングされた登録画像および入力画像それぞれの画素に対し、その画素の周辺の画素の周辺の画素に基づいて平滑化を行うことを特徴とするパターン検出方法。
【請求項８】
請求項６または７のパターン検出方法であって、
極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する際、サンプリングされた登録画像および入力画像それぞれの画素に対し、所定の条件を満たす直交座標上の点を、対応する極座標上の点に各画素の振幅成分を加算することによって集約化することを特徴とするパターン検出方法。
【請求項９】
請求項５から８のいずれかのパターン検出方法であって、
補正された入力画像と登録画像との相関値を演算する際、振幅成分が所定の閾値以上の画素について積算することことを特徴とするパターン検出方法。
【請求項１０】
請求項５から９のいずれかのパターン検出方法であって、
補正された入力画像と登録画像との相関値を演算する際、各画素の振幅成分の変位量に基づき加重平均をとることにより、振幅成分に基づく強調処理を行うことを特徴とするパターン検出方法。
【請求項１１】
請求項４から１０のいずれかのパターン検出方法であって、
登録データおよび入力データを構成する各データの座標をそれぞれ対数・極座標に変換することを特徴とするパターン検出方法。
【請求項１２】
予め登録された登録データを入力データ中から検索するパターン検出プログラムであって、コンピュータに、
登録データを構成する各データの極座標に基づいてフーリエ変換を行う機能と、
入力データを構成する各データの極座標に基づいてフーリエ変換を行う機能と、
前記フーリエ変換された登録データおよび入力データから位相限定合成を演算する機能と、
前記フーリエ変換された入力データに位相限定合成の複素共役を積算して、補正された入力データを演算する機能と、
補正された入力データと登録データとの相関値を演算する機能と、
演算された相関値に基づき、入力データ中から登録データの検出を行う機能と、
を実現させるためのパターン検出プログラム。
【請求項１３】
予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出プログラムであって、コンピュータに、
登録画像を構成する各画素の極座標に基づいてフーリエ変換を行う機能と、
入力画像を構成する各画素の極座標に基づいてフーリエ変換を行う機能と、
前記フーリエ変換された登録画像および入力画像から位相限定合成を演算する機能と、
前記フーリエ変換された入力画像に位相限定合成の複素共役を積算して、補正された入力画像を演算する機能と、
補正された入力画像と登録画像との相関値を演算する機能と、
演算された相関値に基づき、入力画像中から登録画像のパターン検出を行う機能と、
を実現させるためのパターン検出プログラム。
【請求項１４】
予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出プログラムであって、コンピュータに、
登録画像および入力画像を構成する各画素の直交座標をそれぞれ極座標に変換する機能と、
極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する機能と、
離散化された登録画像および入力画像をそれぞれ離散フーリエ変換する機能と、
離散フーリエ変換された登録画像および入力画像に基づき、位相限定合成を演算する機能と、
前記離散フーリエ変換された入力画像に位相限定合成の複素共役を積算して、補正された入力画像を演算する機能と、
補正された入力画像と登録画像との相関値を演算する機能と、
演算された相関値に基づき、入力画像中から登録画像のパターン検出を行う機能と、
を実現させるためのパターン検出プログラム。
【請求項１５】
請求項１４のパターン検出プログラムであって、
極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する際、サンプリングされた登録画像および入力画像それぞれの画素に対し、その画素の周辺の画素の周辺の画素に基づいて平滑化を行うことを特徴とするパターン検出プログラム。
【請求項１６】
請求項１４または１５のパターン検出プログラムであって、
極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する際、サンプリングされた登録画像および入力画像それぞれの画素に対し、所定の条件を満たす直交座標上の点を、対応する極座標上の点に各画素の振幅成分を加算することによって集約化することを特徴とするパターン検出プログラム。
【請求項１７】
請求項１４から１６のいずれかのパターン検出プログラムであって、
補正された入力画像と登録画像との相関値を演算する際、振幅成分が所定の閾値以上の画素について積算することことを特徴とするパターン検出プログラム。
【請求項１８】
請求項１４から１７のいずれかのパターン検出プログラムであって、
補正された入力画像と登録画像との相関値を演算する際、各画素の振幅成分の変位量に基づき加重平均をとることにより、振幅成分に基づく強調処理を行うことを特徴とするパターン検出プログラム。
【請求項１９】
請求項１２から１８のいずれかのパターン検出プログラムであって、
登録データおよび入力データを構成する各データの座標をそれぞれ対数・極座標に変換することを特徴とするパターン検出プログラム。
【請求項２０】
請求項１２から１９のいずれかのパターン検出プログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばパターンサーチやパターンマッチング、位置検出等に利用される画像等のデータ処理に関する技術であって、予め登録された所定の登録データを、サーチの対象となる入力データ中から検索するパターン検出装置、パターン検出方法、パターン検出プログラムおよびコンピュータで読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
画像処理は、工場における電子部品の製造や実装など、様々な分野で使用されている。特に、ビデオなどで撮像した映像をデータ化して、この中から所望のパターンを探し出すパターンマッチングは、位置決めなどの用途で利用されている。パターンマッチングの例を図１に示す。図１に示す入力画像は、領域を複数の画素Ｇに分割したマトリックス状の配列で構成している。この図に示すように、入力画像のエリアＳＡ１を予め登録された登録画像ＲＦ１を所定量移動させながら正規化相関法などの手法によりマッチングを行い、検出したい画像ＯＢの位置する座標を求める。
【０００３】
このような画像パターンの検出に関する手法は様々なものが開発されている。一般に画像データから詳細な特徴量抽出を行う手法ほど、正確な検出が可能となる反面、必要な計算量やデータ量が膨大となり、これに対応可能な高速、大容量の設備が要求される。そこで、組み込み機器などに実装可能な仕様で、かつ実用に耐え得る精度と速度を備える画像検索システムが望まれており、研究が進んでいる。
【０００４】
例えば、上述した正規化相関法では、登録画像と入力画像との一致度を、２つのデータ群の関係を演算する正規化相関により求める。正規化相関によるマッチングでは、サーチ領域内で登録画像を１画素ずつずらしながら入力画像との間の相関値を計算し、最大の相関値が得られる位置に登録画像が存在するとみなし、そのときの一致度を求める。
【０００５】
正規化相関法に関して、例えば位相限定相関を利用したパターン抽出装置が開発されている（特許文献１）。この手法の概要を図２に示す。まず、入力画像中から検索したい登録画像をフーリエ変換することによって、振幅成分と位相成分（周波数成分ｓ）に分離する。ここで、画像の振幅成分は画像を構成する画素の濃淡に関する情報であり、一方の位相成分は画像の構造に関する情報である。位相限定相関法は、フーリエ位相相関とも呼ばれ、フーリエ変換を用いて相関を計算する過程において、振幅成分の情報量を削除している。言い換えると、画像の濃淡でなく形状に関する位相成分を取り扱うことにより、画像の類似を判定する。
【０００６】
一方、入力画像についても同様にフーリエ変換し、位相成分を抽出する。そして、これら登録画像および入力画像の位相成分を合成する。そして、これを逆フーリエ変換することで登録画像と入力画像の相関画像を得ることができる。
【０００７】
位相限定相関法は、通常の相関を行う方法に比べて同一のものを識別する特性が優れている。図３に、登録画像と入力画像を同じとして相互相関をとった自己相関の結果を、（ａ）通常の相関と（ｂ）位相限定相関についてそれぞれ示している。自己相関では本来相関値が最大となるべきであるところ、図３（ａ）に示すように通常の相関では相関値が不規則に変化するブロードな波形となっている。一方の位相限定相関では、中央部にデルタ関数状のピークが得られ、同一画像であることが明確に判別されている。また、この方法では位置ずれの検出も正確に行うことができる。図４に、登録画像を水平に移動させた入力画像について位相限定相関を演算した結果を示す。この図に示すように、入力画像の位置ずれに応じてデルタ関数状のピークの位置がずれている。ピークの位置は、位置ずれの方向と変位量に対応している。このように、位相限定相関のピーク位置を測定することで極めて正確な位置ずれ検出が可能となる。
【０００８】
正規化相関法では、以上のようにして画像間の相互相関を求めることができる。ただ、この手法ではそのままでは回転に対して不変ではないため、回転を含む画像の検出に利用することはできない。上記の例において、登録された登録画像が、検索対象の入力画像中に同じ姿勢で存在している場合は、入力画像を順次走査することで、パターンマッチングを実行できる。しかしながら、登録画像が傾いていたり回転した状態で入力画像中に存在する場合は、通常のパターンマッチングによりそのまま走査しただけでは検出できない。この場合は、登録画像を所定の角度で回転させ、回転毎にパターンマッチングを繰り返すリピートマッチング検索を行う必要がある。この方法では、回転角のピッチに応じて計算量が肥大化し必要な演算処理が膨大になるという問題があった。
【０００９】
これに対して、画像中の各画素のｘ、ｙ座標を極座標に変換することで、回転不変の正規化相関を得ることができる（非特許文献１）。例えば、上記の位相限定相関を利用したパターン抽出装置において、図５に示すように入力画像中から検索したい登録画像を先ず極座標変換すると、図６に示すように回転移動量を平行移動量に変換される。この極座標系に基づいてフーリエ変換を行うことによって、平行移動量を演算でき、さらにこれを逆フーリエ変換すれば回転量を演算することが可能となる。例えば離散値のフーリエ変換Ｘ（ｋ）に対して、逆フーリエ変換ｘ（ｎ）は以下の数１で求められる。
【００１０】
【数１】
2004326728.tif 000003
【００１１】
しかしながら、上記の位相限定相関法では、いずれの場合も逆フーリエ変換が必須となるという問題があった。パターン検出方法では、実用的な利用を考えると処理の負担を軽減し、かつ高速化することが必須となる。位相限定相関法は一旦フーリエ変換して位相成分を合成した後、相関画像に戻すために逆フーリエ変換を行っている。ただ、逆フーリエ変換の実行には三角関数の演算が含まれること等から、演算が複雑になり実行のためのコストがかさむという問題があった。複雑な演算の実行には処理の負荷がかかるため、これに見合う高級な回路が必要となり、かつ処理量の増大に対応して処理の高速化も要求されるため、消費電力も増大する。このように処理速度や記憶領域、電源容量といったハードウェア的な面で高スペックが要求されると、実用レベルの回路への実装が困難となる。例えば小型の組込機器への実装を考えると、コスト、電源容量、実装面積等の制約から、利用可能な演算装置や、記憶容量に自ずと制約が生じるため、複雑な演算を行う手法では高負荷となり実装が困難であるという問題があった。
【特許文献１】特許３０３５６５４号
【非特許文献１】佐々木慶文他「回転およびスケール変化に不変な位相限定画像照合の性能評価」第４５回自動制御連合講演会（２００２年１１月２６日−２７日）
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、このような問題点に鑑みてなされたものである。本発明の目的は、回転状態の登録画像等のデータの検索が可能で、かつ安価に実現可能なパターン検出装置、パターン検出方法、パターン検出プログラムおよびコンピュータで読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段】
【００１３】
上記目的を実現するために、本発明の請求項１に係るパターン検出装置は、予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出を行うパターン検出装置であって、外部から入力画像を入力し保持するための入力画像記憶部１と、検出すべき登録画像を記憶するための登録画像記憶部２と、前記入力画像記憶部１および登録画像記憶部２から各々の画像データを読み取り、登録画像および入力画像を構成する各画素の極座標に基づきそれぞれフーリエ変換し、フーリエ変換された登録画像および入力画像に基づき位相成分を抽出して、位相成分を合成して得られる位相限定合成の複素共役をフーリエ変換された入力画像に積算して入力画像を補正し、補正された入力画像と登録画像との相関値を演算し、演算された相関値に基づき入力画像中から登録画像のパターン検出を行うための画像処理部３とを備えることを特徴とする。
【００１４】
これによって、入力画像中に登録画像が回転した状態で含まれていても、言い換えると入力画像と登録画像に位相のずれがあっても、位相のずれによる影響を排除したパターン検出が実現される。特に逆フーリエ変換を行わずとも実行できるので、計算コストを安価に抑えることができる。
【００１５】
また、本発明の請求項２のパターン検出装置は、予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出を行うパターン検出装置であって、外部から入力画像を入力し保持するための入力画像記憶部１と、検出すべき登録画像を記憶するための登録画像記憶部２と、前記入力画像記憶部１および登録画像記憶部２から各々の画像データを読み取り、登録画像および入力画像を構成する各画素の直交座標をそれぞれ極座標に変換する極座標変換部と、前記極座標変換部で変換された登録画像および入力画像の極座標を、それぞれ所定のサンプリング周期でサンプリングするサンプリング部と、前記サンプリング部でサンプリングされた登録画像および入力画像をそれぞれ離散フーリエ変換する離散フーリエ変換部と、前記離散フーリエ変換部でフーリエ変換された登録画像および入力画像に基づき、位相限定合成を演算する位相限定合成部と、前記フーリエ変換部でフーリエ変換された入力画像に前記位相限定合成部で演算された位相限定合成の複素共役を積算して、補正された入力画像を演算するための複素共役積算部と、前記複素共役積算部で補正された入力画像と登録画像との相関値を演算する相関演算部と、前記相関演算部で演算された相関値に基づき、入力画像中から登録画像のパターン検出を行うパターン検出部とを備えることを特徴とする。
【００１６】
さらに、本発明の請求項３のパターン検出装置は、請求項１または２のパターン検出装置であって、前記極座標変換部が各画素の直交座標をそれぞれ対数・極座標に変換することを特徴とする。
【００１７】
これによって、画像の回転のみならず拡大縮小に対しても位相のずれによる影響を排除したパターン検出が実現される。
【００１８】
また、本発明の請求項４のパターン検出方法は、予め登録された登録データを入力データ中から検索するパターン検出方法であって、登録データを構成する各データの極座標に基づいてフーリエ変換を行うステップと、入力データを構成する各データの極座標に基づいてフーリエ変換を行うステップと、前記フーリエ変換された登録データおよび入力データから位相限定合成を演算するステップと、前記フーリエ変換された入力データに位相限定合成の複素共役を積算して、補正された入力データを演算するステップと、補正された入力データと登録データとの相関値を演算するステップと、演算された相関値に基づき、入力データ中から登録データの検出を行うステップとを備えることを特徴とする。
【００１９】
これによって、入力データ中に登録データに位相のずれがあっても、位相のずれによる影響を排除したパターン検出が実現される。特に逆フーリエ変換を行わずとも実行できるので、計算コストを安価に抑えることができる。
【００２０】
さらに、本発明の請求項５のパターン検出方法は、予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出方法であって、登録画像を構成する各画素の極座標に基づいてフーリエ変換を行うステップと、入力画像を構成する各画素の極座標に基づいてフーリエ変換を行うステップと、前記フーリエ変換された登録画像および入力画像から位相限定合成を演算するステップと、前記フーリエ変換された入力画像に位相限定合成の複素共役を積算して、補正された入力画像を演算するステップと、補正された入力画像と登録画像との相関値を演算するステップと、演算された相関値に基づき、入力画像中から登録画像のパターン検出を行うステップとを備えることを特徴とする。
【００２１】
これによって、入力画像中に登録画像が回転した状態で含まれていても、言い換えると入力画像と登録画像に位相のずれがあっても、位相のずれによる影響を排除したパターン検出が実現される。特に逆フーリエ変換を行わずとも実行できるので、計算コストを安価に抑えることができる。
【００２２】
さらにまた、本発明の請求項６のパターン検出方法は、予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出方法であって、登録画像および入力画像を構成する各画素の直交座標をそれぞれ極座標に変換するステップと、極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化するステップと、離散化された登録画像および入力画像をそれぞれ離散フーリエ変換するステップと、離散フーリエ変換された登録画像および入力画像に基づき、位相限定合成を演算するステップと、前記離散フーリエ変換された入力画像に位相限定合成の複素共役を積算して、補正された入力画像を演算するステップと、補正された入力画像と登録画像との相関値を演算するステップと、演算された相関値に基づき、入力画像中から登録画像のパターン検出を行うステップとを備えることを特徴とする。
【００２３】
さらにまた、本発明の請求項７のパターン検出方法は、請求項６のパターン検出方法であって、極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する際、サンプリングされた登録画像および入力画像それぞれの画素に対し、その画素の周辺の画素の周辺の画素に基づいて平滑化を行うことを特徴とする。
【００２４】
これによって、量子化誤差を平滑化し、対象となる画素に重み付けを持たせた極座標変換が実現される。
【００２５】
さらにまた、本発明の請求項８のパターン検出方法は、請求項６または７のパターン検出方法であって、極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する際、サンプリングされた登録画像および入力画像それぞれの画素に対し、所定の条件を満たす直交座標上の点を、対応する極座標上の点に各画素の振幅成分を加算することによって集約化することを特徴とする。
【００２６】
これによって、サンプリングにより離散化された極座標データを集約できる。
【００２７】
さらにまた、本発明の請求項９のパターン検出方法は、請求項５から８のいずれかのパターン検出方法であって、補正された入力画像と登録画像との相関値を演算する際、振幅成分が所定の閾値以上の画素について積算することことを特徴とする。
【００２８】
これによって、登録画像において振幅成分の小さいデータを演算から排除でき、演算量を低減して処理の負担減、高速化に寄与し得る。
【００２９】
さらにまた、本発明の請求項１０のパターン検出方法は、請求項５から９のいずれかのパターン検出方法であって、補正された入力画像と登録画像との相関値を演算する際、各画素の振幅成分の変位量に基づき加重平均をとることにより、振幅成分に基づく強調処理を行うことを特徴とする。
【００３０】
これによって、登録画像において振幅成分の小さいデータを演算から排除でき、演算量を低減すると共に誤差の影響を抑えて安定化させ、なおかつ振幅成分の大きいデータに基づいて演算を行えるので、結果の信頼性も向上する。
【００３１】
さらにまた、本発明の請求項１１のパターン検出方法は、請求項４から１０のいずれかのパターン検出方法であって、登録データおよび入力データを構成する各データの座標をそれぞれ対数・極座標に変換することを特徴とする。
【００３２】
これによって、画像の回転のみならず拡大縮小に対しても位相のずれによる影響を排除したパターン検出が実現される。
【００３３】
また、本発明の請求項１２のパターン検出プログラムは、予め登録された登録データを入力データ中から検索するパターン検出プログラムであって、コンピュータに、登録データを構成する各データの極座標に基づいてフーリエ変換を行う機能と、入力データを構成する各データの極座標に基づいてフーリエ変換を行う機能と、前記フーリエ変換された登録データおよび入力データから位相限定合成を演算する機能と、前記フーリエ変換された入力データに位相限定合成の複素共役を積算して、補正された入力データを演算する機能と、補正された入力データと登録データとの相関値を演算する機能と、演算された相関値に基づき、入力データ中から登録データの検出を行う機能とを実現させるためのパターン検出プログラムである。
【００３４】
これによって、入力画像中に登録画像が回転した状態で含まれていても、言い換えると入力画像と登録画像に位相のずれがあっても、位相のずれによる影響を排除したパターン検出が実現される。特に逆フーリエ変換を行わずとも実行できるので、計算コストを安価に抑えることができる。
【００３５】
さらに、本発明の請求項１３のパターン検出プログラムは、予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出プログラムであって、コンピュータに、登録画像を構成する各画素の極座標に基づいてフーリエ変換を行う機能と、入力画像を構成する各画素の極座標に基づいてフーリエ変換を行う機能と、前記フーリエ変換された登録画像および入力画像から位相限定合成を演算する機能と、前記フーリエ変換された入力画像に位相限定合成の複素共役を積算して、補正された入力画像を演算する機能と、補正された入力画像と登録画像との相関値を演算する機能と、演算された相関値に基づき、入力画像中から登録画像のパターン検出を行う機能とを実現させるためのパターン検出プログラムである。
【００３６】
さらにまた、本発明の請求項１４のパターン検出プログラムは、予め登録された登録画像を入力画像中から検索する画像処理におけるパターン検出プログラムであって、コンピュータに、登録画像および入力画像を構成する各画素の直交座標をそれぞれ極座標に変換する機能と、極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する機能と、離散化された登録画像および入力画像をそれぞれ離散フーリエ変換する機能と、離散フーリエ変換された登録画像および入力画像に基づき、位相限定合成を演算する機能と、前記離散フーリエ変換された入力画像に位相限定合成の複素共役を積算して、補正された入力画像を演算する機能と、補正された入力画像と登録画像との相関値を演算する機能と、演算された相関値に基づき、入力画像中から登録画像のパターン検出を行う機能とを実現させるためのパターン検出プログラムである。
【００３７】
さらにまた、本発明の請求項１５のパターン検出プログラムは、請求項１４のパターン検出プログラムであって、極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する際、サンプリングされた登録画像および入力画像それぞれの画素に対し、その画素の周辺の画素の周辺の画素に基づいて平滑化を行うことを特徴とする。
【００３８】
これによって、量子化誤差を平滑化し、対象となる画素に重み付けを持たせた極座標変換が実現される。
【００３９】
さらにまた、本発明の請求項１６のパターン検出プログラムは、請求項１４または１５のパターン検出プログラムであって、極座標で表示される登録画像および入力画像をそれぞれ所定のサンプリング周期で離散化する際、サンプリングされた登録画像および入力画像それぞれの画素に対し、所定の条件を満たす直交座標上の点を、対応する極座標上の点に各画素の振幅成分を加算することによって集約化することを特徴とする。
【００４０】
これによって、サンプリングにより離散化された極座標データを集約できる。
【００４１】
さらにまた、本発明の請求項１７のパターン検出プログラムは、請求項１４から１６のいずれかのパターン検出プログラムであって、補正された入力画像と登録画像との相関値を演算する際、振幅成分が所定の閾値以上の画素について積算することことを特徴とする。
【００４２】
これによって、登録画像において振幅成分の小さいデータを演算から排除でき、演算量を低減して処理の負担減、高速化に寄与し得る。
【００４３】
さらにまた、本発明の請求項１８のパターン検出プログラムは、請求項１４から１７のいずれかのパターン検出プログラムであって、補正された入力画像と登録画像との相関値を演算する際、各画素の振幅成分の変位量に基づき加重平均をとることにより、振幅成分に基づく強調処理を行うことを特徴とする。
【００４４】
これによって、登録画像において振幅成分の小さいデータを演算から排除でき、演算量を低減すると共に誤差の影響を抑えて安定化させ、なおかつ振幅成分の大きいデータに基づいて演算を行えるので、結果の信頼性も向上する。
【００４５】
さらにまた、本発明の請求項１９のパターン検出プログラムは、請求項１２から１８のいずれかのパターン検出プログラムであって、登録データおよび入力データを構成する各データの座標をそれぞれ対数・極座標に変換することを特徴とする。
【００４６】
これによって、画像の回転のみならず拡大縮小に対しても位相のずれによる影響を排除したパターン検出が実現される。
【００４７】
また、本発明の請求項２０のコンピュータで読み取り可能な記録媒体は、請求項１２から１９のいずれかのパターン検出プログラムを記録したものである。記録媒体には、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷやフレキシブルディスク、磁気テープ、ＭＯ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒ、ＤＶＤ＋Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ＋ＲＷなどの磁気ディスク、光ディスク、光磁気ディスク、半導体メモリその他のプログラムを格納可能な媒体が含まれる。また上記のプログラムは、ネットワークを介してダウンロード可能な形態も含まれる。
【発明の効果】
【００４８】
本発明のパターン検出装置、パターン検出方法、パターン検出プログラムおよびコンピュータで読み取り可能な記録媒体によれば、入力画像中から任意形状の登録画像を回転や拡大縮小に関わらず高速に検索可能である。特に、本発明のパターン検出装置、パターン検出方法、パターン検出プログラムおよびコンピュータで読み取り可能な記録媒体では、位相限定相関に逆フーリエ変換を使用せず、複素共役を乗算することによって登録画像の回転や拡大縮小にロバストな（不変性のある）パターン検出を得ている。これによって画像間相関値の演算を主として積和演算によって実行でき、逆フーリエ変換の実行に必要な三角関数等の複雑な演算を省くことができる。このため演算の負荷が低減され、処理が軽量化されるので、演算のための回路構成を簡素にして消費電力の低減、処理速度の向上を図ることができ、さらにリピートマッチング検索のような回転変換が不要であることと相まって計算量自体が大きく低減されるため、さらに高速化に寄与し、比較的小規模な装置にも実装可能な安価なパターン検出が実現される。また、振幅成分に基づく処理を付加することで、さらに正確なパターン検出が得られる。特に振幅の小さいデータを無視し、振幅の大きいデータを強調することで、差異が強調されて確実なパターン検出が得られ易くなるという利点がある。
【発明を実施するための最良の形態】
【００４９】
以下、本発明の実施の形態を図面に基づいて説明する。ただし、以下に示す実施の形態は、本発明の技術的思想を具体化するためのパターン検出装置、パターン検出方法、パターン検出プログラムおよびコンピュータで読み取り可能な記録媒体を例示するものであって、本発明はパターン検出装置、パターン検出方法、パターン検出プログラムおよびコンピュータで読み取り可能な記録媒体を以下のものに特定しない。
【００５０】
さらに、この明細書は、特許請求の範囲を理解し易いように、実施の形態に示される部材に対応する番号を、「特許請求の範囲の欄」、および「課題を解決するための手段の欄」に示される部材に付記している。ただ、特許請求の範囲に示される部材を、実施の形態の部材に特定するものでは決してない。なお、各図面が示す部材の大きさや位置関係等は、説明を明確にするため誇張していることがある。さらに以下の説明において、同一の名称、符号については同一もしくは同質の部材を示しており、詳細説明を適宜省略する。さらにまた、本発明を構成する各要素は、複数の要素を同一の部材で構成して一の部材で複数の要素を兼用する態様としてもよいし、逆に一の部材の機能を複数の部材で分担して実現することもできる。
【００５１】
本明細書においてパターン検出装置とは、主に位相限定相関法を使用したパターン検出を実行可能なハードウェアを指す。このハードウェアは、例えば図７に示すような構成で、汎用もしくは専用のパーツや回路、装置で構成される。ただしこれ以外にも、汎用の回路やコンピュータにソフトウェアやプログラム、プラグイン、オブジェクト、ライブラリ、アプレット、コンパイラなどを組み込んで位相限定相関法を使用したパターン検出を実施可能としたものもパターン検出装置に含む。つまり本発明の実施の形態は、ハードウェア的に構成することもできるし、ソフトウェア的に実現することもできる。ソフトウェアとして実現する場合、位相限定相関法を使用したパターン検出方法は汎用あるいはカスタマイズされた専用のコンピュータ、ワークステーション、端末、携帯型電子機器、ＰＤＡ、ページャ、スマートフォンその他の電子デバイスにおいて、プログラムとして実行される。
【００５２】
［パターン検出装置］
本発明の実施の形態に係るパターン検出装置を図７に基づいて説明する。図７に示すパターン検出装置は、外部から画像データを入力する入力画像記憶部１と、パターン検出すべき登録画像を記憶する登録画像記憶部２と、これら入力画像記憶部１および登録画像記憶部２に接続されて各々の画像データを読み取り、パターン検出に必要な各種の処理を行う画像処理部３と、画像処理部３でパターン検出を行うための制御や必要な設定を行うための制御部４と、パターン検出結果を表示するための表示部５と、ユーザがパターン検出装置の操作や設定を行うための入力部６とを備える。なお、相互の部材同士の関係や接続形態は図７に示す例に限定されず、例えば画像処理部３と制御部４を入れ替えたり、入力部６と表示部５を共通としたりすることも可能である。
【００５３】
入力画像記憶部１は、これに接続される画像ソース７から入力される画像をデータとして記憶する。例えば、撮像カメラで撮影されたリアルタイムの画像や、予め記録された再生画像などを入力画像とし、これを例えばＡ／Ｄコンバータでアナログ信号からデジタル信号に変換して二値化データや多階調のグレースケールデータなどの画像データとする。入力画像記憶部１には入力画像データを記憶するメモリ、例えば揮発性メモリであるＲＡＭなどが使用される。
【００５４】
登録画像記憶部２は、パターン検出でサーチしたい画像のデータを記憶するものある。パターン検出実行に先立ち、サーチの基準となる所望の登録画像を予め登録しておく。例えば、入力画像記憶部１と同様に外部の画像ソース７と接続して（例えば入力画像記憶部１と切り替えるようにして）登録画像を含む画像データを入力する。ユーザは取り込まれた画像中から、登録画像としたい領域を指定する。指定された領域を登録画像として、登録画像記憶部２に保持する。登録画像記憶部には、不揮発性のＲＯＭや揮発性のＲＡＭなどが使用できる。
【００５５】
画像処理部３は、入力画像記憶部１および登録画像記憶部２からそれぞれ入力画像データ、登録画像データを読み取って、パターン検出を行う作業領域となる。画像処理部３に接続された制御部４は、入力画像記憶部１および登録画像記憶部２から画像データを呼び出すアドレスを指定する。制御部４はＣＰＵやシステムＬＳＩ、ＡＳＩＣ等で構成され、制御部４に指定されたアドレスに従って画像処理部３は必要な画像データを読み出し、パターン検出を実施する。パターン検出を実行するために、画像処理部３と制御部４は、登録画像および入力画像を構成する各画素の直交座標をそれぞれ極座標に変換する極座標変換部と、極座標変換部で変換された登録画像および入力画像の極座標を、それぞれ所定のサンプリング周期でサンプリングするサンプリング部と、サンプリング部でサンプリングされた登録画像および入力画像をそれぞれ離散フーリエ変換する離散フーリエ変換部と、離散フーリエ変換部でフーリエ変換された登録画像および入力画像に基づき、位相限定合成を演算する位相限定合成部と、フーリエ変換部でフーリエ変換された入力画像に位相限定合成部で演算された位相限定合成の複素共役を積算して、補正された入力画像を演算するための複素共役積算部と、複素共役積算部で補正された入力画像と登録画像との相関値を演算する相関演算部と、相関演算部で演算された相関値に基づき、入力画像中から登録画像のパターン検出を行うパターン検出部として機能する。
【００５６】
画像処理部３と制御部４で実行されたパターン検出の結果は、表示部５にて表示される。あるいは、その後の処理のために外部接続機器に出力される。一方、ユーザは入力部６からパターン検出装置を操作する。入力部６はマウスやキーボード、スライドパッド、タブレット、デジタイザ、ライトペン、テンキー、ジョグダイヤル、タッチパッド、アキュポイント、タッチパネルなどの各種ポインティングデバイスが利用できる。例えばパターン検出装置をコンピュータで実現する場合、入力部６はコンピュータに接続されたマウスやキーボードなどの入出力デバイスで、表示部５はディスプレイ、画像処理部３および制御部４はＣＰＵ、入力画像記憶部１および登録画像記憶部２はメモリに相当する。
【００５７】
［位相限定相関法］
次に、本発明の実施の形態１に係る位相限定相関法を用いたパターン検出方法について、図８および図９のフローチャートに基づき説明する。パターンマッチングまたはパターンサーチは、予め検索したい登録画像を登録しておき、サーチ対象領域である入力画像を走査して登録されたパターンを検索していく画像の検索方法である。本実施の形態では、位相限定相関を応用して回転不変な画像間相関に基づくパターン検出を行っている。具体的には、対象となる登録画像を極座標系に変換し、円周方向に離散フーリエ変換を行った後、位相限定相関を用いて回転ずれによる画像間の位相差を補正することにより、回転不変な画像間相関値を求める。以下、基本原理を図８に基づき説明する。
【００５８】
［極座標変換ステップ］
まず、パターン検出の対象となる入力画像と事前に登録された登録画像を、それぞれ極座標系で表現する。ステップＳ１では、外部の画像ソースなどから取得された入力画像が入力画像記憶部から画像処理部に取得され、直交座標系（ｘ，ｙ）上でＩ１（ｘ，ｙ）、登録画像記憶部から取得された登録画像がＩ２（ｘ，ｙ）として与えられる。ステップＳ２で、これらの直交座標を以下の数２に基づき極座標（ρ，θ）上に変換し、極座標上の入力画像をＩ１（ρ，θ）、登録画像をＩ２（ρ，θ）として表現する。ここでρは絶対値、θは偏角である。なお、入力画像と登録画像が直交座標を介さず直接極座標系で与えられる場合は、ステップＳ１は省略できる。
【００５９】
【数２】
2004326728.tif 000004
【００６０】
［離散フーリエ変換］
次にステップＳ３では極座標の離散化を行う。具体的には、入力画像Ｉ１（ρ，θ）、登録画像Ｉ２（ρ，θ）のそれぞれについて、半径方向（距離または変位）にサンプリング間隔ＴｒでＭ個、円周方向（角度または位相）に２π／ＮでＮ個のサンプリングを行い、離散値Ｉ’１（ｒ，ｔ）、Ｉ’２（ｒ，ｔ）（ｒ＝０，１，．．．，Ｍ−１；ｔ＝０，１，．．．，Ｎ−１）を得る。さらにステップＳ４で、この離散値に対して、位相ｔに沿って離散フーリエ変換を行う。この結果、次式数３で示すＦ１（ｒ，ｓ）、Ｆ２（ｒ，ｓ）が得られる。
【００６１】
【数３】
2004326728.tif 000005
【００６２】
ここで、入力画像Ｉ１が、登録画像Ｉ２を極座標ｒ＝０の点を中心としてθ１回転したものであった場合、数４の関係が成立する。
【００６３】
【数４】
2004326728.tif 000006
【００６４】
この場合、高周波成分によるエイリアシングを無視すれば、数３のＦ１（ｒ，ｓ）、Ｆ２（ｒ，ｓ）の間には、数５の関係が成立する。
【００６５】
【数５】
2004326728.tif 000007
【００６６】
［位相限定合成］
次にステップＳ５で、入力画像Ｉ１および登録画像Ｉ２の離散フーリエ変換Ｆ１およびＦ２に基づき、これらの位相限定合成Ｒ（ｓ）を数６に基づいて演算する。数６に示すように、Ｆ１（ｒ，ｓ）にＦ２（ｒ，ｓ）の複素共役を乗算したものを振幅成分で除算することにより、大きさが１とされる、言い換えると振幅成分、ここでは画像の輝度情報が正規化により無視され、角度毎の位相成分のみが抽出されることになる。
【００６７】
【数６】
2004326728.tif 000008
【００６８】
［入力画像の補正］
数６から、各周波数ｓにおける回転角θ１による位相のずれを抽出することができる。そしてステップＳ６で、上記のＲ（ｓ）を用いて入力画像Ｆ１を数７のように補正し、回転による位相差の影響を排除した形の入力画像Ｆ’１（ｒ，ｓ）に戻すことができる。数７は、フーリエ変換したＦ１（ｒ，ｓ）に数６で得られたＲ（ｓ）の複素共役を乗算したものである。したがって、この状態でステップＳ７にて入力画像と登録画像との相関値を求めれば、回転による影響を排除した状態での相関値を求めることができる。そしてステップＳ８にて、相関値に基づいて制御部が画像の検出を行い、必要に応じて表示部への出力等を行う。
【００６９】
【数７】
2004326728.tif 000009
【００７０】
［応用例］
以上の方法によって、回転による位相のずれを解除した相関値を得ることができる。ただし、実際には画像取得時のノイズや量子化誤差の他、画像データが通常は直交座標上で離散的に得られること等から、極座標系への変換時に誤差が発生する。そこで、以上の基本原理を考慮して、実際に画像間の相関値を計算するためのアルゴリズムを、以下図９に基づき説明する。
【００７１】
［極座標上での集約化］
ステップＳ’１およびＳ’２では、図８と同様に入力画像と登録画像の取得および直交座標から極座標への変換を行う。そしてステップＳ’３−１では極座標で得られたデータを離散化し、集約化する。ここでは、入力画像から、登録画像と同じ大きさの範囲を切り出し、数２とサンプリング間隔Ｔｒ、２π／Ｎを用いて直交座標から極座標への変換と、離散化を行った。この際、上述の各種誤差を軽減するため、次式数８の関係を満たす直交座標（ｘ，ｙ）上の点を、対応する極座標（ｒ，ｔ）上の点に各画素の輝度値を加算することによって集約化した。これによって離散化された画像データは、離散化された極座標上の刻幅に集約されることになる。
【００７２】
【数８】
2004326728.tif 000010
【００７３】
［極座標上での平滑化］
さらにステップＳ’３−２において、極座標上において任意の画素の周辺４近傍を用いた平滑化を、次式数９のように行う。この例では、図１０に示すような平滑化フィルタを用いている。すなわち、対象となる画素に対して、その上下左右に隣接する画素を１／４倍して平滑化している。
【００７４】
【数９】
2004326728.tif 000011
【００７５】
［離散フーリエ変換および位相限定合成の平均化］
ステップＳ’４では極座標に変換された画像データに対して、数３に従って円周方向に離散フーリエ変換を行う。さらにステップＳ’５において、数６に基づき位相限定合成を求める。ただし、本来は同一の画像が一定角度回転している場合、半径方向に対して数６の値は不変となるはずであるが、実際には各種誤差のために変動が生じる。よってステップＳ’５では、半径方向の平均を求め、以下の演算ではこの平均値Ｒａｖｅ（ｓ）を数６の値とする。
【００７６】
［振幅成分に基づく強調処理］
ステップＳ’６では、数７を用いて入力画像を補正しＦ’１（ｒ，ｓ）を得る。そしてステップＳ’７において、補正後の入力画像Ｆ’１（ｒ，ｓ）と登録画像Ｆ２（ｒ，ｓ）の相互相関ｃ（ｒ）を、次式数１０より演算する。この相関値に基づき、ステップＳ’８にて回転不変な画像検出が実行される。
【００７７】
【数１０】
2004326728.tif 000012
【００７８】
ただし、上式においてＲｅ（＊）は＊の実数部である。またＧｓ、Ｇ（ｒ）は次式数１１で示す通りである。
【００７９】
【数１１】
2004326728.tif 000013
【００８０】
上記のように、各半径における画素の密度であるＧ（ｒ）によって加重平均をとることにより、登録画像において画素密度の高い部分での相関が強調されることとなる。言い換えると、振幅成分（画像の輝度情報）の小さいデータを無視している。数１１において、Ｇ（ｒ）が０のデータについては、数１０のｃ（ｒ）は考慮されず、演算対象から除去される。０のデータとは、二値画像では黒の画素であり、画像情報のないデータである。このような画素を検索対象から除くことで、高速かつ高精度なパターン検出を実現できる。一般に画像を構成する画素の内、画素値の低い、あるいはゼロのデータからは、正確なパターン検出ができず、むしろ計算結果を不安定にして誤差を増大する。そこでこのようなデータを排除して計算の安定化を図ると共に、必要な演算量を低減して高速化に寄与する。加えて、振幅成分の大きいデータが強調されることによって、画像の内で輝度の高い、明るい部分に基づいた相関が得られる。このように振幅成分に基づく強調処理を行うことによって、振幅（スペクトル）の存在するデータのみを演算対象とし、高速でかつ回転に対してロバスト性のあるパターン検出が確実に実現される。
【００８１】
上記のパターン検出方法では、登録画像の回転角度を詳細に検討することなく、回転成分をキャンセルした形でパターン検出が実行される。このため、回転を考慮して画像を走査する必要が無くなり、平行移動成分の検出のみを扱うため格段に計算回数が低減され、低負荷で高速な演算が実現される。さらに逆フーリエ変換を行う必要が無く、また角度検出のための相関ピークの抽出ステップも不要となるため、この点においても演算が簡単で高速に実行可能なパターン検出が実現できる。
【００８２】
なお、この方法では回転に依存しないパターン検出は実行できるが、回転角度自体の検出は行われない。回転角度の検出が必要なアプリケーションにおいては、回転角度を別途計算するアルゴリズムを併用あるいは付加できることはいうまでもない。このパターン検出方法は、画像処理装置における高速かつ安価なパターンサーチ等に利用できる。例えば、製品の検査工程における画像抽出や指紋照合等に適用できる。また詳細な位置検出や回転角度検出でなく、その前処理として大まかな位置検出に利用し、その後必要に応じて検出位置近傍での角度検出を含む詳細なパターン検出を行わせることも可能である。
【００８３】
［シミュレーション実験結果］
次に、上記で説明した手法を用いた場合の有効性を確認すべく、各種画像に対するパターン検出のシミュレーション実験を行った結果を示す。
【００８４】
［単純な図形の相関性］
まず、図１１および図１２に示す単純な図形を含むテスト画像１およびテスト画像２それぞれについて、上記実施の形態に係るパターン検出方法により相関の評価を行い、この手法が回転に対し一意性を備えること、および似通った図形との相関値の差異について検証を行った。なお、本実施の形態で用いた各画像は、１２８×１２８画素の二値画像であり、極座標での格子点数は、半径方向、円周方向とも３２としている。ここでは、テスト画像１を登録された登録画像とし、テスト画像１、テスト画像２を各々入力画像１、２として、入力画像を０〜π／２まで、π／１８刻みで回転した場合について相関値を求めた。
【００８５】
回転角度毎に得られた相関値を、図１３のグラフに示す。図において、上方の折れ線がテスト画像１の自己相関であり、下方の折れ線がテスト画像１とテスト画像２との相互相関をそれぞれ示している。この図から明らかなように、画像を回転した場合でも、登録画像１自身の自己相関の相関値が、入力画像２との相関値を常に上回っており、しかも自己相関の最小値と、入力画像２との相関値の最大値との間にも十分な開きが認められる。したがって、上記の手法によりパターン検出を行った場合、テスト画像１とテスト画像２との識別が十分可能であることが確認できる。パターン検出を実際に行うための相関値の閾値は、入力画像や登録画像によって決まるため、得られた相関値のデータから統計的に処理される。
【００８６】
なお、図１３は理想的には回転の角度に依らず上方の相関値が１のまま一定であることが望まれるが、回転角が０およびπ／２の位置を除いて自己相関値が１となっていない。すなわち、回転に対して完全に不変とはなっていない。これは、上述した極座標変換時における誤差や、画像を順次回転して入力画像を生成する際に画素位置の量子化誤差が発生し、原画像と回転後の画像が厳密に一致しなくなっているためと考えられる。特に本シミュレーション実験では二値画像を用いているため、その影響が大きくなっている。ただ、実際の応用において２５６階調等の多値画像を用いた場合には、画像取得時に光学系によるアンチエイリアシングがかかること等から、このような影響は少ないと考えられる。
【００８７】
［高度な相関性］
次に、より高度な画像検出においても上記実施の形態に係るパターン検出方法が有効であることを確認するため、図１４および図１５のような画像をテスト画像として相関値を演算し、図１４に示すテスト画像３を登録画像とした場合の自己相関、および図１５に示すテスト画像４を入力画像とした場合の相関値とを比較した。その結果を図１６のグラフに示す。図１４および図１５のテスト画像はそれぞれ、画像の中心から一定の半径の位置では画素数の分布が同一となっている。このため、入力登録画像３と入力画像４を通常の相関値で評価すれば同一と判定されてしまう。よって、中心から同一半径における画素分布を周波数領域で見る場合、位相成分を考慮しなければ判別ができないことになり、高度なパターン検出が要求される。このような高度な画像検出においても、図１６に示すとおりすべての角度において自己相関との間に明確な相関値の差が認められ、入力画像３と入力画像４の相関値の最大値と自己相関の最低値と間においても明確な開きが認められ、位相成分を考慮した相関値の手法の有効性が確認できた。
【００８８】
［ノイズに対するロバスト性の評価］
次に、画像に含まれるノイズに対する耐性を評価するため、図１１に示した画像に対してランダムに５００点の画素を選択し、選択された画素の画素値を反転させることにより、ノイズの付加を行った。ノイズ付加後の画像をテスト画像５として、図１７に示す。実際の製品検査等の場合、ＣＣＤカメラより取得した原画像にこのようなスパイクノイズが直接含まれることは考え難い。ただ、多値画像として画像を取得後、前処理としてＳｏｂｅｌフィルタ等を用いてエッジ検出を行った場合に、原画像における画像の濃淡むらがこのようなノイズとなることも起こり得る。同様に入力画像２にも同様の処理を行い、入力画像６（図示せず）として、上記と同様の相関値の評価試験を行った。その結果を図１８のグラフに示す。
【００８９】
このシミュレーション結果より、上記と同じくテスト画像５の自己相関とテスト画像６との相関値に開きが認められ、両者の区別が可能であることが確認できる。なお、図１８を見ると、図１３の結果に比して、登録画像５自身の相関値が回転によって低下している。これはランダムノイズによって画像の高周波成分が増加し、数５が成立しない割合が増加したためと考えられる。ただし、この場合はテスト画像５とテスト画像６との間の相関値も自己相関値と同様に低下しており、この手法によって識別は十分可能である。ただ、実際にはこれ以上のノイズが付加された画像を扱うことは希であると思われ、本実施の形態によって実用上十分な精度をもったパターン検索が実現できる。また、上述した例はいずれも評価目的のため判別が困難な画像に対してパターン検出を実行しているが、実際のパターン検出においてはより明確な相違が検出され、十分な精度でのパターン検出が実現される。
【００９０】
［複数の対象が含まれる入力画像からの抽出］
次に、より実際的な場合のシミュレーションとして、図１９に示すように複数の文字が含まれるテスト画像７中から、対象となる文字を抽出する場合について評価を行った。ここでは、複数のアルファベットを斜め、水平に配置した入力画像中から、登録画像として図２０に示すテスト画像８の「Ｆ」を検索することとした。図１９のテスト画像７には、様々な傾きの「Ｆ」が３つ含まれている。なお、図１９のみ、画像の大きさは５１２×５１２画素とし、図２０は上記と同様１２８×１２８画素とした。この評価試験では、実施の形態に係るパターン検出方法の回転不変性の評価を目的としているので、縦、横方向のパターン走査については、単純に１画素毎に順次探索を行っている。走査の高速化を図るため、実際のアプリケーションにおいては、既知の、あるいは将来開発される他の手法と組み合わせることができる。この演算結果を図２１のグラフに示す。
【００９１】
図２１ではｘ、ｙ軸を、図２０の登録画像を図１９に示すテスト画像７において左上を原点とするｘ、ｙ直交座標で縦、横方向にずらした画素数とし、ｚ軸として各座標位置における相関値をプロットしている。ここでは判りやすくするため、相関値が０．８５以上のもののみを表示している。図２１のグラフには３つのピークが認められ、これらのピークがそれぞれ、図１９のテスト画像７に含まれる「Ｆ」の位置、すなわち上、中、下の位置に対応している。このように、本発明の実施の形態に依れば、入力画像中から登録画像が傾きや回転に関わらず良好に検出されることが確認された。なお、図２１中の各ピークに矢印で示す数値は、左から順に検出位置におけるｘ座標、ｙ座標、相関値をそれぞれ示している。
【００９２】
［処理速度］
次に、本発明の実施の形態に係るパターン検出方法の処理速度について検討を行う。本発明の方法に依らず、一般的な正規化相関法を用いて回転によるずれを含む画像の検出を行う場合は、上述したように登録画像を適当な刻幅によって順次回転し、回転後の登録画像と、入力画像との相互相関をとることが行われる。この場合、回転の刻幅を小さくするに応じて処理時間が増大するが、２分検索等と併用して用いられるため、必ずしも、刻幅に反比例して処理時間が増大するという訳ではない。ただ、画像の回転変換に要する処理時間は必ず必要となる。ここでは、本実施の形態に係るパターン検出方法によって、従来の正規化相関法と比較して処理速度が向上されたことを確認するため、同じ画像の組に対して一回の相互相関を求めるために必要な処理時間を、本実施の形態に係るパターン検出方法と、画像の回転変換に正規化相関を演算するリピートマッチング検索法とで比較した。比較に用いた画像は、上記のテスト画像１とテスト画像２の組み合わせとした。各々、１０００回の処理を行い、その平均値を求めて比較している。本発明の実施の形態に係るパターン検出方法では、極座標変換時に画像の大きさを１／１６としてるため、正規化相関についても同様に縦横それぞれ１／４となるよう縮小を行っている。
【００９３】
なお、処理時間の計測に使用した計算機は、ＣＰＵとして動作周波数１．２ＧＨｚのＰｅｎｔｉｕｍＩＩＩ（登録商標）、ＯＳとしてＦｒｅｅＢＳＤ  Ｒ４．７、Ｃｏｍｐｉｌｅｒとしてｇｃｃ２．９５．４を使用した。
【００９４】
この結果、処理時間の１０００回平均は、本実施の形態に係るパターン検出方法では、１．９ｍｓ、通常の正規化相関と回転変換を組み合わせた手法では１１．１ｍｓとなった。このことから、本実施の形態に係るパターン検出方法では、一回の処理について通常の正規化相関と比べ５倍以上高速であることが確認された。これは、回転変換を行うための計算時間が本実施の形態の方法では不要となることが大きく寄与していると考えられる。このため処理すべき演算量が低減され、処理の高速化が得られている。
【００９５】
なお本実施の形態に係るパターン検出方法においても、直交座標から極座標系への座標変換が必要である。ただ、登録画像と極座標系への変換後のサイズが決まれば、予め画素間の対応関係を計算し、毎回の検索時には、変換表等を用意することによって一意に対応画素へと変換を行うことができるため、行列演算を行う必要はない。また、２分検索等を併用した場合でも、従来の手法で回転不変でない相関値を用いている場合には、任意の回転角に対応するためには複数回の処理が必要であるため、実際の処理時間の差はさらに大きなものとなる。
【００９６】
なお、上記の例においては対象画像を固定して入力画像を回転させる例で説明したが、対象画像を回転させても同じ結果が得られることはいうまでもない。
【００９７】
以上のように、位相限定相関を利用することにより、回転不変な画像間相関値を定義し、これによって高速かつ入力画像の回転に依存しない検出が可能であることが、各種のシミュレーションによって確認された。しかも、この実施の形態に係るパターン検出方法は、逆フーリエ変換が不要であり、主として積和演算で実行可能な複素共役を使用している。これによって処理の負荷は大きく軽減され、処理の軽量化、高速化によって小規模な組み込みシステムにも実装可能なシステムが実現できる。特に、近年安価に入手可能となった積和演算命令をもつプロセッサを用いることにより、高速に実行可能となる。
【００９８】
［拡大縮小］
また、極座標変換と併せて、半径方向にｌｏｇ変換を行うことにより、登録画像の回転のみならず、拡大・縮小に対しても対応可能とすることができる。ｌｏｇ変換による拡大・縮小については、上述した非特許文献１等、既知の手法や将来開発される手法が適宜利用できる。これによって、登録画像の回転、拡大、縮小に対しても高速かつロバストなパターン検出が実現される。以下、本発明の実施の形態２として、拡大縮小および回転に対して不変なパターン検出の一例について説明する。
【００９９】
図２２および図２３のフローチャートは、位相限定相関法を用いた拡大縮小・回転不変なパターン検出の流れを示す。この方法では、対象となる登録画像を対数・極座標系に変換し、半径・円周方向に離散フーリエ変換を行った後、位相限定相関を用いて拡大縮小・回転ずれによる画像間の位相差を補正することにより、拡大縮小・回転不変な画像間相関値を求める。以下、基本原理を図２２に基づき説明する。
【０１００】
［対数・極座標変換ステップ］
まず、パターン検出の対象となる入力画像と事前に登録された登録画像を、それぞれ対数・極座標系で表現する。ステップＳ”１では、外部の画像ソースなどから取得された入力画像が入力画像記憶部から画像処理部に取得され、直交座標系（ｘ，ｙ）上でＩ１（ｘ，ｙ）、登録画像記憶部から取得された登録画像がＩ２（ｘ，ｙ）として与えられる。ステップＳ”２で、これらの直交座標を以下の数１２に基づき対数・極座標（ρ，θ）上に変換し、対数・極座標上の入力画像をＩ１（ρ，θ）、登録画像をＩ２（ρ，θ）として表現する。ここでρは絶対値、θは偏角である。数２と異なり、ρ＝０は特異点となる。なお、入力画像と登録画像が直交座標を介さず直接、対数・極座標系で与えられる場合は、ステップＳ”１は省略できる。
【０１０１】
【数１２】
2004326728.tif 000014
【０１０２】
［二次元離散フーリエ変換］
次にステップＳ”３では、図８と同様に対数・極座標の離散化を行う。半径方向（距離または変位）にサンプリング間隔ＴｒでＭ個、円周方向（角度または位相）に２π／ＮでＮ個のサンプリングを行い、離散値Ｉ’１（ｒ，ｔ）、Ｉ’２（ｒ，ｔ）（ｒ＝０，１，．．．，Ｍ−１；ｔ＝０，１，．．．，Ｎ−１）を得る。さらにステップＳ”４では、得られた離散値に対してｒ、ｔに沿って二次元離散フーリエ変換を行う。この結果、次式数１３で示すＦ１（ｕ，ｓ）、Ｆ２（ｕ，ｓ）が得られ、半径方向成分と円周方向成分の項が現れる。
【０１０３】
【数１３】
2004326728.tif 000015
【０１０４】
ここで、入力画像Ｉ１が、登録画像Ｉ２を対数・極座標ρ＝０の点を中心としてρ１拡大縮小し、θ１回転したものであった場合、数１４の関係が成立する。
【０１０５】
【数１４】
2004326728.tif 000016
【０１０６】
この場合、高周波成分によるエイリアシングを無視すれば、数１３のＦ１（ｕ，ｓ）、Ｆ２（ｕ，ｓ）の間には、数１５の関係が成立する。
【０１０７】
【数１５】
2004326728.tif 000017
【０１０８】
［位相限定合成］
次にステップＳ”５で、入力画像Ｉ１および登録画像Ｉ２の離散フーリエ変換Ｆ１およびＦ２に基づき、これらの位相限定合成Ｒ（ｕ，ｓ）を数１６に基づいて演算する。数１６に示すように、Ｆ１（ｕ，ｓ）にＦ２（ｕ，ｓ）の複素共役を乗算したものを振幅成分で除算することにより、大きさが１とされる、言い換えると振幅成分、ここでは画像の輝度情報が正規化により無視され、角度毎の位相成分のみが抽出されることになる。
【０１０９】
【数１６】
2004326728.tif 000018
【０１１０】
［入力画像の補正］
数１６から、各周波数ｕ、ｓにおける拡大縮小率ρ１、回転角θ１による位相のずれを抽出することができる。そしてステップＳ”６で、上記のＲ（ｕ，ｓ）を用いて入力画像Ｆ１を数１７のように補正し、拡大縮小・回転による位相差の影響を排除した形の入力画像Ｆ’１（ｕ，ｓ）に戻すことができる。数１７は、フーリエ変換したＦ１（ｕ，ｓ）に数１６で得られたＲ（ｕ，ｓ）の複素共役を乗算したものである。したがって、この状態でステップＳ”７にて入力画像と登録画像との相関値を求めれば、拡大縮小・回転による影響を排除した状態での相関値を求めることができる。そしてステップＳ”８にて、相関値に基づいて制御部が画像の検出を行い、必要に応じて表示部への出力等を行う。
【０１１１】
【数１７】
2004326728.tif 000019
【０１１２】
［応用例］
以上の方法によって、拡大縮小・回転による位相のずれを解除した相関値を得ることができる。ただし、実際には画像取得時のノイズや量子化誤差の他、画像データが通常は直交座標上で離散的に得られること等から、対数・極座標系への変換時に誤差が発生する。そこで、以上の基本原理を考慮して、実際に画像間の相関値を計算するためのアルゴリズムを、以下図２３に基づき説明する。
【０１１３】
［対数・極座標上での集約化］
ステップＳ”’１およびＳ”’２では、図２２と同様に入力画像と登録画像の取得および直交座標から対数・極座標への変換を行う。そしてステップＳ”’３−１では対数・極座標で得られたデータを離散化し、集約化する。ここでは、入力画像から、登録画像と同じ大きさの範囲を切り出し、数１２とサンプリング間隔Ｔｒ、２π／Ｎを用いて直交座標から対数・極座標への変換と、離散化を行った。この際、上述の各種誤差を軽減するため、次式数１８の関係を満たす直交座標（ｘ，ｙ）上の点を、対応する対数・極座標（ｒ，ｔ）上の点に各画素の輝度値を加算することによって集約化した。これによって離散化された画像データは、離散化された対数・極座標上の刻幅に集約されることになる。
【０１１４】
【数１８】
2004326728.tif 000020
【０１１５】
［対数・極座標上での平滑化］
さらにステップＳ”’３−２において、対数・極座標上において任意の画素の周辺４近傍を用いた平滑化を、上記数９のように行う。この例でも、図１０に示すような平滑化フィルタを用いて、対象となる画素に対してその上下左右に隣接する画素を１／４倍して平滑化している。
【０１１６】
［離散フーリエ変換および位相限定合成の平均化］
ステップＳ”’４では対数・極座標に変換された画像データに対して、数１３に従って半径・円周方向に二次元離散フーリエ変換を行う。さらにステップＳ”’５において、数１６に基づき位相限定合成を求める。ここで、同一の画像が一定の倍率で拡大縮小され、一定角度回転している場合、数１６は拡大縮小のみの成分と回転のみの成分とに分離して、次式数１９で表現できる。
【０１１７】
【数１９】
2004326728.tif 000021
【０１１８】
このため、フーリエ変換後の直流成分Ｒ（ｕ，０）、Ｒ（０，ｓ）のみを用いて補正を行えばよい。ここでは、数１９の値を数１６の値として、数１７を補正する。なお、入力画像が登録画像と異なっている場合は、数１４が成立せず、数１６の値も画像の差を反映して各周波数において独立な位相差が現れるため、数１９のような直流成分の積で表現できない。よってこの場合は数１９による補正を行っても登録画像に近付くことはない。
【０１１９】
［画像間の相関］
ステップＳ”’６では、数１７を用いて入力画像を補正しＦ’１（ｕ，ｓ）を得る。そしてステップＳ”’７において、補正後の入力画像Ｆ’１（ｕ，ｓ）と登録画像Ｆ２（ｕ，ｓ）の相互相関ｃを、次式数２０より演算する。この相関値に基づき、ステップＳ”’８にて拡大縮小・回転不変な画像検出が実行される。
【０１２０】
【数２０】
2004326728.tif 000022
【０１２１】
ここで、上式においてＲｅ（＊）は＊の実数部である。またＧ１、Ｇ２は次式数２１で示す通りである。
【０１２２】
【数２１】
2004326728.tif 000023
【０１２３】
数２０においてｅ（ｕ，ｓ）は位相成分による画像間の相関を表しており、この部分を１とすれば、画像の振幅成分（輝度情報）のみを用いた正規化相関と同一となる。上記のパターン検出方法では、登録画像の拡大縮小・回転成分をキャンセルした形でパターン検出が実行される。このため、拡大縮小・回転を考慮して画像を走査する必要が無くなり、平行移動成分の検出のみを扱うため格段に計算回数が低減され、低負荷で高速な演算が実現される。さらに逆フーリエ変換を行う必要が無く、また角度検出のための相関ピークの抽出ステップも不要となるため、この点においても演算が簡単で高速に実行可能なパターン検出が実現できる。なお、この方法では拡大縮小・回転に依存しないパターン検出は実行できるが、拡大縮小率や回転角度自体の検出は行われない。拡大縮小率や回転角度の検出が必要なアプリケーションにおいては、拡大縮小率・回転角度を別途計算するアルゴリズムを併用あるいは付加できることはいうまでもない。
【０１２４】
［シミュレーション実験結果］
次に、上記で説明した手法を用いた場合の有効性を確認すべく、各種画像に対するパターン検出のシミュレーション実験を行った結果を示す。
【０１２５】
［単純な図形の相関性］
まず、上記と同様の図１１および図１２に示す図形を含むテスト画像１およびテスト画像２それぞれについて、上記実施の形態２に係るパターン検出方法により相関の評価を行い、この手法が拡大縮小・回転に対し一意性を備えること、および似通った図形との相関値の差異について検証を行った。ここでは、テスト画像１を登録された登録画像とし、テスト画像１、テスト画像２を各々入力画像として、入力画像を登録画像に対して０．８倍、１．０倍、１．２倍に拡大縮小し、さらに０〜π／２まで、π／１８刻みで回転した場合について相関値を求めた。この結果を図２４〜図２６のグラフに示す。図２４は０．８倍に縮小、図２５は拡大縮小しない１．０倍、図２６は１．２倍に拡大した入力画像につき、それぞれ回転角度毎に得られた相関値をグラフ上に示している。これらの図において、上方の折れ線がテスト画像１の自己相関であり、下方の折れ線がテスト画像１とテスト画像２との相互相関をそれぞれ示している。
【０１２６】
この図から明らかなように、画像を拡大縮小・回転した場合でも、登録画像１自身の自己相関の相関値が、登録画像２との相関値を常に上回っており、しかも自己相関の最小値と、登録画像２との相関値の最大値との間にも十分な開きが認められる。したがって、上記の手法によりパターン検出を行った場合、テスト画像１とテスト画像２との識別が十分可能であることが確認できる。パターン検出を実際に行うための相関値の閾値は、入力画像や登録画像によって決まるため、得られた相関値のデータから統計的に処理される。図の例では、相関値０．８５を閾値に設定することで、図２４〜図２６のすべてについて画像の識別が可能となる。
【０１２７】
なお、図２４〜図２６では理想的には拡大縮小率・回転の角度に依らず上方の相関値が１のまま一定であることが望まれるが、図２５の等倍、回転無しにあたる回転角が０およびπ／２の位置を除いて自己相関値が１となっていない。すなわち、拡大縮小・回転に対して完全に不変とはなっていない。これは、上述した対数・極座標変換時における誤差や、画像を順次拡大縮小・回転して入力画像を生成する際に画素位置の量子化誤差が発生し、原画像と変換後の画像が厳密に一致しなくなっているためと考えられる。特に本シミュレーション実験では二値画像を用いているため、その影響が大きくなっている。ただ、実際の応用において２５６階調等の多値画像を用いた場合には、画像取得時に光学系によるアンチエイリアシングがかかること等から、このような影響は少ないと考えられる。
【０１２８】
［比較試験］
次に、位相成分を用いることについての上記実施の形態２に係るパターン検出方法の有効性を確認するため、位相成分を考慮しないで相関値を演算した。具体的には、上記と同じく図１１および図１２のテスト画像を登録画像・入力画像として、拡大縮小率、回転角などの条件は図２４〜図２６と同じとし、数２０のｅ（ｕ，ｓ）を１とした場合の相関値を演算した。この結果を図２７〜図２９に示す。これらの図から明らかなように、この方法では位相情報を用いず振幅情報のみでの比較となるため、全体として画像間の差異が減少し、相関値が高くなった。しかしながら、テスト画像１自身に対する相関値の最小値が、テスト画像２に対する相関値の最大値を下回っているため、単一の閾値でテスト画像１とテスト画像２を区別することはできない。このことから、上記実施の形態２に係るパターン検出方法による位相成分を考慮した相関値による有効性が確認できた。
【０１２９】
［ノイズに対するロバスト性の評価］
次に、画像に含まれるノイズに対する耐性を評価するため、入力画像の背景を無地でなく特定のパターンを持たせてパターン検出を行った。ここでは、図１２に示す画像に対して、図３０に示すように斜線の背景パターンを合成したテスト画像９を入力画像とし、図１１のテスト画像１を登録画像として相関値を演算した。なお、図１１を図３０と直接相関値を演算した場合、登録画像の無地の部分に対して背景パターンの面積が大きいため、相関値が著しく低下する。そこで、この例では背景パターンは既知であると仮定し、入力画像と背景パターンとの差分を取り、これを相関の対象としている。この結果を図３１〜図３３に示す。なお、図３１〜図３３において比較対象となる図１１のテスト画像１においては、同じく背景と合成したものを入力画像として相関を演算しているため、倍率１．０、回転角０の場合でも相関値は１とならない。これらの図に示す結果を上記図２４〜図２６と比較すると、背景部分を除去したことによる画像の劣化により、テスト画像１自身に対する相関値が低下し、図３０のテスト画像９に対する相関値が一部で増加している。このため、背景のない場合に比較して峻別がより困難となっているが、この例でも閾値を０．８５に設定することによって両者の識別は十分可能である。
【０１３０】
［複数の対象が含まれる入力画像からの抽出］
次に、より実際的な場合のシミュレーションとして、図３４に示すように複数の文字が様々なサイズ、傾きで含まれるテスト画像１０中から、対象となる文字を抽出する場合について評価を行った。ここでは、複数のアルファベットを斜め、水平に配置した入力画像中から、登録画像として図３５に示すテスト画像１１の「Ｆ」を検索することとした。図３４のテスト画像１０には、他のアルファベットに混じって様々な傾きの「Ｆ」が３つ含まれている。なお、図３４は画像の大きさを５１２×５１２画素とし、図３５は上記と同様１２８×１２８画素とした。この評価試験では、本発明の実施の形態２に係るパターン検出方法の拡大縮小・回転不変性の評価を目的としているので、縦、横方向のパターン走査については、単純に１画素毎に順次探索を行っている。走査の高速化を図るため、実際のアプリケーションにおいては、既知の、あるいは将来開発される他の手法と組み合わせることができる。この演算結果を図３６のグラフに示す。
【０１３１】
図３６ではｘ、ｙ軸を、図３５の登録画像を図３４に示すテスト画像１０において左上を原点とするｘ、ｙ直交座標で縦、横方向にずらした画素数とし、ｚ軸として各座標位置における相関値をプロットしている。ここでは判りやすくするため、相関値が０．６以上のデータのみを表示している。図３６のグラフには複数のピークが認められ、このうち特に顕著な３つのピークがそれぞれ、図３４のテスト画像１０に含まれる「Ｆ」の位置、すなわち上、中、下の位置に対応している。このように、本発明の実施の形態２に依れば、入力画像中から登録画像が傾きや回転、拡大縮小に関わらず良好に検出されることが確認された。なお、図３６中の各ピークに示す数値は、左から順に検出位置におけるｘ座標、ｙ座標、相関値をそれぞれ示している。図３４における３つの「Ｆ」の正確な位置は、上から下にそれぞれｘ・ｙ座標が（１８０，４０）、（１８０，１８０）、（１８０，３２０）である。また倍率は１．２、１．０、０．８であり、回転角は時計回りを正として＋３０°、０°、−４５°である。なお、回転角０°である中央のＦでは検出結果と完全に一致するが、拡大縮小・回転したＦについてはそれぞれ真値から１画素だけずれて検出された。これは、上述したように各種誤差の他、入力画像を生成する際に行った文字の拡大縮小・回転によって、文字自身の形状が劣化していることも一因と考えられる。
【０１３２】
［処理速度］
最後に、本発明の実施の形態２のパターン検出方法の処理速度について検討を行う。ここでも上記実施の形態１と同様、実施の形態２に係るパターン検出方法によって、従来の正規化相関法と比較して処理速度が向上されたことを確認するため、同じ画像の組に対して一回の相互相関を求めるために必要な処理時間を、本実施の形態２に係るパターン検出方法と、画像の拡大縮小・回転変換に正規化相関を演算するリピートマッチング検索法とで比較した。比較に用いた画像は、上記のテスト画像１とテスト画像２の組み合わせとし、各々１０００回の処理を行い、その平均値を求めて比較している。本発明の実施の形態２に係るパターン検出方法では、対数・極座標変換時に画像の大きさを１／１６としてるため、正規化相関についても同様に縦横それぞれ１／４とし、相関を求める際の大きさは同じく原画像の１／１６となるように縮小を行っている。なお処理時間の計測に使用した計算機も、実施の形態１と同様とした。
【０１３３】
この結果、処理時間の１０００回平均は、本実施の形態２に係るパターン検出方法では、２．９ｍｓ、通常の正規化相関と拡大縮小・回転変換を組み合わせた手法では１０．５ｍｓとなった。このことから、本実施の形態２に係るパターン検出方法では、一回の処理について通常の正規化相関と比べ３倍以上高速であることが確認された。これは、拡大縮小・回転変換を行うための計算時間が本実施の形態２の方法では不要となることが大きく寄与していると考えられる。このため処理すべき演算量が低減され、処理の高速化が得られている。なお参考として、変換を行わず単純に正規化相関のみを行った場合の処理時間は０．５ｍｓであった。ただし、この場合は当然ながら拡大縮小・回転ずれを含む画像の検出を行うことはできない。
【０１３４】
本実施の形態２に係るパターン検出方法においても、直交座標から対数・極座標系への座標変換が必要であるが、実施の形態１と同様に変換表等を利用すれば行列演算を行う必要はない。また、上記の例においては対象画像を固定して入力画像を拡大縮小・回転させる例で説明したが、対象画像を拡大縮小・回転させても同じ結果が得られることはいうまでもない。
【０１３５】
以上のように、位相限定相関を利用することにより、拡大縮小・回転不変な画像間相関値を定義し、これによって高速かつ入力画像の拡大縮小・回転に依存しない検出も実現可能であることが、各種のシミュレーションによって確認された。
【０１３６】
さらに、以上の例では二値画像を用いた例を説明したが、８階調、１６階調、２５６階調といったグレースケール画像（濃淡画像）やフルカラー画像等の多値画像にも適用可能であることはいうまでもない。このような多値画像では二値画像に比べ情報量が多く、より精度や信頼性の高い検索が得られる。カラー画像の場合は、ＲＧＢ成分や輝度、色度等の所定の情報に基づいて相関を求める。
【０１３７】
さらにまた、以上の例においては簡単のため２次元での演算について説明したが、２次元のみならず１次元、あるいはより多次元の検索にも応用可能であることはいうまでもない。多くの特徴量を抽出して検索を行う場合は、より多次元の検索となり、さらに計算量が肥大化するが、このような場合においても本発明の実施の形態に係るパターン検出方法によれば、安価なコストで高速な回転不変、あるいは拡大縮小にも不変の検索を実現できる。
【０１３８】
さらに、本明細書においては平面画像の検索を例に挙げて説明したが、本発明は２次元の画像検索のみならず、立体画像や音声その他のマルチメディアデータの検索にも応用できる。このように本発明は、空間周波数特性に基づいてＮ次元のパターンの照合を行い、登録パターンと入力パターンとの相違点や移動パターンを抽出するパターン検出に利用できる。よって本発明のパターン検出装置、パターン検出方法、パターン検出プログラムおよびコンピュータで読み取り可能な記録媒体は、その名称に関わらず、画像以外のデータの検索も対象として権利範囲に包含する。
【産業上の利用可能性】
【０１３９】
本発明を利用して、パターンマッチングや画像認識をより安価に、しかも高速に行うことができる。積和演算で実現できるため、例えば組み込み機器用途への適用も容易となる。
【図面の簡単な説明】
【０１４０】
【図１】パターンマッチング手法の一例を示す概略図である。
【図２】位相限定相関を利用したパターン抽出を示す概略図である。
【図３】登録画像の自己相関を通常の相関と位相限定相関で演算した結果を示す概略図である。
【図４】登録画像を水平に移動させた入力画像について位相限定相関を演算した結果を示す概略図である。
【図５】画像を極座標変換して位相限定相関を利用したパターン抽出を示す概略図である。
【図６】極座標変換により回転移動量が平行移動量に変換される様子を示す概略図である。
【図７】本発明の一実施の形態に係るパターン検出装置の構成を示すブロック図である。
【図８】本発明の実施の形態１に係るパターン検出方法を示すフローチャートである。
【図９】図８のパターン検出方法の変形例を示すフローチャートである。
【図１０】極座標上での平滑化に使用する平滑化フィルタの概念を示す概略図である。
【図１１】テスト画像１を示すイメージ図である。
【図１２】テスト画像２を示すイメージ図である。
【図１３】本発明の実施の形態１に係るパターン検出方法でテスト画像１の自己相関と、テスト画像２との相互相関を演算した結果を示すグラフである。
【図１４】テスト画像３を示すイメージ図である。
【図１５】テスト画像４を示すイメージ図である。
【図１６】本発明の実施の形態１に係るパターン検出方法でテスト画像３の自己相関と、テスト画像４との相互相関を演算した結果を示すグラフである。
【図１７】テスト画像５を示すイメージ図である。
【図１８】本発明の実施の形態１に係るパターン検出方法でテスト画像５の自己相関と、テスト画像６との相互相関を演算した結果を示すグラフである。
【図１９】テスト画像７を示すイメージ図である。
【図２０】テスト画像８を示すイメージ図である。
【図２１】本発明の実施の形態１に係るパターン検出方法で、テスト画像７からテスト画像８を検出した結果を示すグラフである。
【図２２】本発明の実施の形態２に係るパターン検出方法を示すフローチャートである。
【図２３】本発明の他の実施の形態に係るパターン検出方法を示すフローチャートである。
【図２４】本発明の実施の形態２に係るパターン検出方法にて、０．８倍の縮小率でテスト画像１の自己相関と、テスト画像２との相互相関を演算した結果を示すグラフである。
【図２５】本発明の実施の形態２に係るパターン検出方法にて、等倍でテスト画像１の自己相関と、テスト画像２との相互相関を演算した結果を示すグラフである。
【図２６】本発明の実施の形態２に係るパターン検出方法にて、１．２倍の拡大率でテスト画像１の自己相関と、テスト画像２との相互相関を演算した結果を示すグラフである。
【図２７】図２４の条件において、位相成分を考慮しないで相関値を演算した結果を示すグラフである。
【図２８】図２５の条件において、位相成分を考慮しないで相関値を演算した結果を示すグラフである。
【図２９】図２６の条件において、位相成分を考慮しないで相関値を演算した結果を示すグラフである。
【図３０】テスト画像９を示すイメージ図である。
【図３１】本発明の実施の形態２に係るパターン検出方法にて、０．８倍の縮小率でテスト画像１の自己相関と、テスト画像９との相互相関を演算した結果を示すグラフである。
【図３２】本発明の実施の形態２に係るパターン検出方法にて、等倍でテスト画像１の自己相関と、テスト画像９との相互相関を演算した結果を示すグラフである。
【図３３】本発明の実施の形態２に係るパターン検出方法にて、１．２倍の拡大率でテスト画像１の自己相関と、テスト画像９との相互相関を演算した結果を示すグラフである。
【図３４】テスト画像１０を示すイメージ図である。
【図３５】テスト画像１１を示すイメージ図である。
【図３６】本発明の実施の形態２に係るパターン検出方法で、テスト画像１０からテスト画像１１を検出した結果を示すグラフである。
【符号の説明】
【０１４１】
１・・・入力画像記憶部
２・・・登録画像記憶部
３・・・画像処理部
４・・・制御部
５・・・表示部
６・・・入力部
７・・・画像ソース
【図１】
2004326728.tif 000024
【図２】
2004326728.tif 000025
【図３】
2004326728.tif 000026
【図４】
2004326728.tif 000027
【図５】
2004326728.tif 000028
【図６】
2004326728.tif 000029
【図７】
2004326728.tif 000030
【図８】
2004326728.tif 000031
【図９】
2004326728.tif 000032
【図１０】
2004326728.tif 000033
【図１１】
2004326728.tif 000034
【図１２】
2004326728.tif 000035
【図１３】
2004326728.tif 000036
【図１４】
2004326728.tif 000037
【図１５】
2004326728.tif 000038
【図１６】
2004326728.tif 000039
【図１７】
2004326728.tif 000040
【図１８】
2004326728.tif 000041
【図１９】
2004326728.tif 000042
【図２０】
2004326728.tif 000043
【図２１】
2004326728.tif 000044
【図２２】
2004326728.tif 000045
【図２３】
2004326728.tif 000046
【図２４】
2004326728.tif 000047
【図２５】
2004326728.tif 000048
【図２６】
2004326728.tif 000049
【図２７】
2004326728.tif 000050
【図２８】
2004326728.tif 000051
【図２９】
2004326728.tif 000052
【図３０】
2004326728.tif 000053
【図３１】
2004326728.tif 000054
【図３２】
2004326728.tif 000055
【図３３】
2004326728.tif 000056
【図３４】
2004326728.tif 000057
【図３５】
2004326728.tif 000058
【図３６】
2004326728.tif 000059