(57)【要約】      （修正有）【課題】複雑且つ大きい被探索画像、又は大きな原図形の場合にも、任意形状、任意姿勢、任意サイズ及び一部隠れの被探索図形を高速に探索可能な方法を提供すること。【解決手段】図形の輪郭の法線と輪郭の交点である第１の特徴点と第２の特徴点とから特徴点ペアを作り、輪郭上の複数の特徴点ペア各々を基準として図形を基準座標系に変換し離散化してハッシュテーブルに図形基準情報を登録し、被探索画像に対して同様な方法で各特徴点ペア各々に対して基準座標系上で図形を離散化して、登録されている図形基準情報により図形基準投票箱に投票するジオメトリックハッシング法によって、目的の図形群を探索し、対象ポーズ計算によって被探索図形を絞り込む方法を基本とし、被探索画像上の特徴点ペア間隔及び投票のための図形離散化の範囲に制限を加え、複雑な原図形は分割し、分割原図形に対して探索を行い、全体の一致を確認する方法をとる。【選択図】図２
2006309718.tif 000002
【特許請求の範囲】
【請求項１】
原パターンの輪郭上に所定の方法１によって複数の特徴点を設定し、該複数の特徴点を使用して所定の方法２によって第１特徴点と第２特徴点からなる特徴点ペア（以下、原パターン基底ペアともいう）を複数組設定する原パターン特徴点・ペア設定ステップと
前記原パターン基底ペアの第１特徴点を始点とし第２特徴点を終点とするベクトル（以降、原パターン基底ベクトルともいう）を正規化し、正規化された前記原パターン基底ベクトルと所定の関係を保って配置される原パターン局部座標系上に前記原パターンの形状を代表する点群を前記原パターン基底ベクトルとの相対的な位置関係を保って原パターン局部座標点群として正規化して展開し、該原パターン局部座標点群を基準座標系上に座標変換して原パターン基準座標点群とし、前記基準座標系の所定領域を小領域に分割し、分割された各々の前記小領域に対応する情報セルからなるハッシュテーブル上の、前記原パターン基準座標点群のどれかが存在する小領域に対応する前記情報セルに前記原パターン基底ペアの識別情報を書き込む手順を、必要な複数組の前記原パターン基底ペアに対して実行する原パターン特徴登録ステップとから
原パターンを登録する原パターン登録プロセスと、
被探索画像上のパターンの輪郭上に前記所定の方法１によって複数の特徴点を設定し、該複数の特徴点を使用して前記所定の方法２によって第１特徴点と第２特徴点からなる特徴点ペア（以降、パターン基底ペアともいう）を設定するパターン特徴点・ペア設定ステップと
前記パターン基底ペアの第１特徴点を始点とし第２特徴点を終点とするベクトル（以降、パターン基底ベクトルともいう）を正規化し、正規化された前記パターン基底ベクトルに対して、前記登録プロセスにおける前記原パターン基底ベクトルと前記原パターン局部座標系との関係と同一の前記所定の関係を保って配置されるパターン局部座標系上に前記パターンの形状を代表する点群を前記パターン基底ベクトルとの相対的な位置関係を保ってパターン局部座標点群として正規化して展開し、該パターン局部座標点群を前記基準座標系上に座標変換してパターン基準座標点群とし、前記小領域に前記パターン基準座標点群のどれかが存在する場合に当該小領域が対応する前記ハッシュテーブルの情報セルに記述されている前記原パターン基底ペアの識別情報の各々に対応して設けられた投票箱（以下、基底ペア投票箱ともいう）に投票することを全ての前記小領域の各々について実施し、その結果、最も高い得票数且つ所定の閾値より高い得票数を獲得した投票箱に対応する原パターン基底ペアとそのときのパターン基底ペアとの相似・姿勢・位置関係を表す諸元である対象ポーズの計算を行う一連の手順を、必要な複数組の前記パターン基底ペアに対して実行することによって複数の対象ポーズを得る第１探索ステップと
得られた複数の対象ポーズの分布から最も正確らしい対象ポーズを所定の方法で１個以上選定し、選定された対象ポーズの計算対象となっているパターン基底ペアを基底ベクトルとして前記基準座標系上に展開されているパターンを前記原パターンと同一かまたは相似の可能性が高いパターンとして選び出す第２探索ステップとから
前記原パターンと同一かまたは相似の可能性の高い１個以上の被探索画像上のパターンを選び出すパターン探索プロセスとを
経ることにより被探索画像上のパターンを探索することを特徴とする高速画像探索方法。
【請求項２】
前記所定の方法1が、前記原パターンまたは前記パターンの輪郭上に所定の間隔で複数の特徴点を設定する方法であり、前記所定の方法２が、該特徴点を第１の特徴点として、１個の第１特徴点を通り当該第１特徴点における前記輪郭の法線の方向に対し所定の角度を持つ直線（以降、特徴点設定線ともいう）が前記輪郭と交差する１個以上の第２の点を第２特徴点として設定し、前記第１特徴点と、当該第１特徴点と同一の特徴点設定線上にある１個以上の前記第２特徴点の各々とを特徴点ペアとして設定する手順を前記第１特徴点の各々に対して実行することによって複数組の特徴点ペアを設定する方法であることを特徴とする請求項１に記載の高速画像探索方法。
【請求項３】
前記パターン特徴点・ペア設定ステップにおいて、前記パターン基底ペアの第１特徴点と第２特徴点との距離が第１の所定の距離以内の条件を満足するように前記パターン基底ペアを設定することを特徴とする請求項１または２に記載の高速画像探索方法。
【請求項４】
前記第１の所定の距離が、前記原パターンの最大直径に相当する距離であることを特徴とする請求項３に記載の高速画像探索方法。
【請求項５】
前記第１探索ステップにおいて、前記パターン局部座標点群を展開する方法が、前記パターン基底ペアと前記パターン局部座標点群の各々に対応する前記被探索画像上の点との距離が第２の所定の距離以内となる条件を満足する特徴点に対して前記パターン局部座標系上での座標計算を行って前記パターン局部座標点群を展開することを特徴とする請求項１乃至４のいずれかに記載の高速画像探索方法。
【請求項６】
前記第１探索ステップにおいて、前記パターン局部座標点群を展開する方法が、前記パターン基底ペアを代表する所定位置と前記パターン局部座標点群の各々に対応する前記被探索画像上の点との距離が第２の所定の距離以内となる条件を満足する特徴点に対して前記パターン局部座標系上での座標計算を行って前記パターン局部座標点群を展開することを特徴とする請求項１乃至５のいずれかに記載の高速画像探索方法。
【請求項７】
前記第２の所定の距離が、前記原パターンの最大直径に相当する距離に前記パターン基底ペアの長さを考慮した距離であることを特徴とする請求項５または６に記載の高速画像探索方法。
【請求項８】
前記第２探索ステップにおいて、前記所定の方法が、得られた前記対象ポーズの各々を基準対象ポーズとして、基準対象ポーズごとに当該基準対象ポーズとその他の対象ポーズとのポーズ間距離を求め、然る後に、基準対象ポーズごとに、当該基準対象ポーズとの違いが所定の範囲内にある全ての他の対象ポーズの各々とのポーズ間距離に対して、ポーズ間距離に依存し且つポーズ間距離の増加に対し減少する関係にある所定の関数の値を計算し、各計算結果の加算値を当該基準対象ポーズのスコアとして、該スコアが所定の数値以上であった当該基準対象ポーズを対象ポーズの小集合（以降、クラスタともいう）の核として認定する手順を全ての基準対象ポーズに対して実行し、該認定された基準対象ポーズの中で前記スコアが最も高い基準対象ポーズを最も正確らしい対象ポーズとして選定する方法であることを特徴とする請求項１乃至７に記載の高速画像探索方法。
【請求項９】
前記所定の範囲内が、
前記基準対象ポーズを（ｔｘｏ、ｔｙｏ、θｏ、ｓｏ）
前記他の対象ポーズを（ｔｘ、ｔｙ、θ、ｓ）
としたとき、
（ｔｘ−ｔｘｏ）の絶対値が（所定最大許容範囲ｔｘｍａｘ）未満
（ｔｙ−ｔｙｏ）の絶対値が（所定最大許容範囲ｔｙｍａｘ）未満
（θ−θｏ）の絶対値が（所定最大許容範囲θｍａｘ）未満
（ｓ−ｓｏ）の絶対値が（所定最大許容範囲ｓｏｍａｘ）未満
を満たす（ｔｘ、ｔｙ、θ、ｓ）の範囲であることを特徴とする請求項８に記載の高速画像探索方法。
【請求項１０】
前記所定の関数が、
前記基準対象ポーズを（ｔｘｏ、ｔｙｏ、θｏ、ｓｏ）
前記他の対象ポーズを（ｔｘ、ｔｙ、θ、ｓ）
該基準対象ポーズと該他の対象ポーズのポーズ間距離を
ｄ（（ｔｘ、ｔｙ、θ、ｓ），（ｔｘｏ、ｔｙｏ、θｏ、ｓｏ））
としたとき、
１／｛０．５＋ｄ（（ｔｘ、ｔｙ、θ、ｓ），（ｔｘｏ、ｔｙｏ、θｏ、ｓｏ））｝
であることを特徴とする請求項８に記載の高速画像探索方法。
【請求項１１】
前記原パターン局部座標点群および前記パターン局部座標点群が、前記原パターンおよび前記パターンそれぞれの、輪郭上で選択された特徴点ペアを構成する複数個の特徴点か、前記輪郭上で選択された複数個の特徴点ペアを構成する特徴点と前記輪郭上で所定の方法で選択されたその他の点との組合せかのいずれかであることを特徴とする請求項１乃至１０に記載の高速画像探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータによる画像探索方法に係り、更に詳しくは、コンピュータを使用して、探索したい文字パターンを含む任意形状の元図形パターン（以降、原パターンともいう）と相似あるいは同一な関係にあり、また任意姿勢で更にその一部が隠れていることもある被探索画像上のパターンを高速に探し出す方法に関する。
【背景技術】
【０００２】
従来、コンピュータを使用して、原パターンと相似あるいは同一な関係にあるパターンを被探索画像の中から探し出す方式については、
原パターンが特定のパターンであり被探索画像上のパターンが重なりがなく分離されているようなときによく使われるところの正規化相関法を使用したテンプレートマッチングによる方法があり、原パターンが任意図形で被探索画像上のパターンが部分隠れの図形が含まれていたり、連続する図形が途切れていたり、ノイズ成分が多く含まれているようなときには、一般化Ｈｏｕｇｈ変換の一般的理論を使用する方法、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇの一般的理論を使用する方法、および特表２０００−５０２８２４（Ｐ２０００−５０２８２４Ａ）で開示されている方法等がある。
【０００３】
正規化相関法を使用したテンプレートマッチングによる方法は、被探索画像上のパターンが任意姿勢、相似サイズあるいは部分隠れの被探索図形に対して適用することができない。
一般化Ｈｏｕｇｈ変換およびＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇの一般的理論を使用する方法は、原パターンが任意形状の場合、被探索画像上のパターンが一部隠れあるいは原パターンに対し任意姿勢、相似あるいは同一サイズの場合のすべてに適用できるが、原パターンが複雑化した場合または大きなサイズとなった場合、または被探索画像が大きなサイズになった場合には、特徴点の数が増加し、その結果、計算回数が多くなり処理時間の長くかかる方法である。特に、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇの一般的理論を使用する方法においては、原パターンを正規化して基準座標系へ登録するとき、あるいは被探索画像の中のパターンを登録されている原パターンと比較するために正規化して基準座標系に展開するときの正規化の基準となる特徴点基底ペアの選択の組合せが、基本的に特徴点の数の２乗のオーダとなり、原パターンの複雑化、大サイズ化により、計算の回数が多くなり処理時間が長くなることは明白である。
特表２０００−５０２８２４（Ｐ２０００−５０２８２４Ａ）で開示されている方法も、原パターンが任意形状の場合、被探索画像上のパターンが一部隠れあるいは原パターンに対し任意姿勢、相似あるいは同一サイズの場合のすべてに適用できるが、原パターンが複雑化した場合または大きなサイズとなった場合、または被探索画像が大きなサイズになった場合には処理時間の長くかかる方法である。
【特許文献１】特表２０００−５０２８２４（Ｐ２０００−５０２８２４Ａ）
【非特許文献１】コンピュータビジョン：技術評論と将来展望    １４９ページから１６１ページ新技術コミュニケーションズ社発行
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の技術においては、原パターンが複雑化した場合あるいは大きなサイズとなった場合、または被探索画像のサイズが大きくなった場合には、特徴点の数が多くなり処理時間が長くかかる問題がある。
一方で、多くの画像探索業務において必要な性能として、原パターンが任意形状の場合、被探索画像上のパターンが一部隠れあるいは原パターンに対し任意姿勢、相似あるいは同一サイズの場合が扱える能力を持ちながら、原パターンが複雑な外形形状を持っている、あるいは、いろいろな図形あるいは文字が複合あるいは組合わされて大きなサイズとなった場合にも被探索画像の中から高速に探索したい、あるいは更に、被探索画像が非常に大きなサイズとなった場合も高速に探索したいとの要求が多い。
本発明においては、原パターンが任意形状の場合、被探索画像上のパターンが一部隠れおよび原パターンに対し任意姿勢、相似あるいは同一サイズのすべてのケースに相当する被探索図形に適用でき、短い処理時間で、探したいパターンを被探索画像の中から高速に探し出す方法を提供することである。
【課題を解決するための手段】
【０００５】
原パターンの輪郭上に所定の方法１によって複数の特徴点を設定し、該複数の特徴点を使用して所定の方法２によって第１特徴点と第２特徴点からなる特徴点ペア（以下、原パターン基底ペアともいう）を複数組設定する原パターン特徴点・ペア設定ステップと
原パターン基底ペアの第１特徴点を始点とし第２特徴点を終点とするベクトル（以降、原パターン基底ベクトルともいう）を正規化し、正規化された原パターン基底ベクトルと所定の関係を保って配置される原パターン局部座標系上に原パターンの形状を代表する点群を原パターン基底ベクトルとの相対的な位置関係を保って原パターン局部座標点群として正規化して展開し、原パターン局部座標点群を基準座標系上に座標変換して原パターン基準座標点群とし、基準座標系の所定領域を小領域に分割し、分割された各々の小領域に対応する情報セルからなるハッシュテーブル上の、原パターン基準座標点群のどれかが存在する小領域に対応する情報セルに原パターン基底ペアの識別情報を書き込む手順を、必要な複数組の原パターン基底ペアに対して実行する原パターン特徴登録ステップとから
原パターンを登録する原パターン登録プロセスと、
被探索画像上のパターンの輪郭上に所定の方法１によって複数の特徴点を設定し、該複数の特徴点を使用して所定の方法２によって第１特徴点と第２特徴点からなる特徴点ペア（以降、パターン基底ペアともいう）を設定するパターン特徴点・ペア設定ステップと
パターン基底ペアの第１特徴点を始点とし第２特徴点を終点とするベクトル（以降、パターン基底ベクトルともいう）を正規化し、正規化されたパターン基底ベクトルに対して、登録プロセスにおける原パターン基底ベクトルと原パターン局部座標系との関係と同一の所定の関係を保って配置されるパターン局部座標系上に前記パターンの形状を代表する点群をパターン基底ベクトルとの相対的な位置関係を保ってパターン局部座標点群として正規化して展開し、パターン局部座標点群を基準座標系上に座標変換してパターン基準座標点群とし、前記小領域にパターン基準座標点群のどれかが存在する場合に当該小領域が対応するハッシュテーブルの情報セルに記述されている原パターン基底ペアの識別情報の各々に対応して設けられた投票箱（以下、基底ペア投票箱ともいう）に投票することを全ての前記小領域の各々について実施し、その結果、最も高い得票数且つ所定の閾値より高い得票数を獲得した投票箱に対応する原パターン基底ペアとそのときのパターン基底ペアとの相似・姿勢・位置関係を表す諸元である対象ポーズの計算を行う一連の手順を、必要な複数組のパターン基底ペアに対して実行することによって複数の対象ポーズを得る第１探索ステップと
得られた複数の対象ポーズの分布から最も正確らしい対象ポーズを所定の方法で１個以上選定し、選定された対象ポーズの計算対象となっているパターン基底ペアを基底ベクトルとして基準座標系上に展開されているパターンを原パターンと同一かまたは相似の可能性が高いパターンとして選び出す第２探索ステップとから
原パターンと同一かまたは相似の可能性の高い１個以上の被探索画像上のパターンを選び出すパターン探索プロセスとを
経ることにより被探索画像上のパターンを探索する方法をとる。
原パターン基底ベクトルと原パターン局部座標系の所定の関係として、原パターン基底ベクトルの中点に原パターン局部座標系の原点を置き、原パターン基底ベクトルと原パターン局部座標系のＸ軸またはＹ軸とを重ね合わせる関係を採ることは、処理の便宜を考慮した場合、好ましい方法のひとつである。当然、その他一義的に決まる関係であればどのような関係であってもよい。
【０００６】
所定の方法1を、原パターンまたはパターンの輪郭上に所定の間隔で複数の特徴点を設定する方法であり、所定の方法２が、該特徴点を第１の特徴点として、１個の第１特徴点を通り当該第１特徴点における輪郭の法線の方向に対し所定の角度を持つ直線（以降、特徴点設定線ともいう）が輪郭と交差する１個以上の第２の点を第２特徴点として設定し、第１特徴点と、当該第１特徴点と同一の特徴点設定線上にある１個以上の第２特徴点の各々とを特徴点ペアとして設定する手順を第１特徴点の各々に対して実行することによって複数組の特徴点ペアを設定する方法とすることが望ましい。
上記特徴点設定の所定の間隔は、所定の方式で決まる特徴点の２点間の間隔であればよく、必ずしも一定間隔である必要はないが、基本的に一定間隔であることが好ましい。
【０００７】
パターン特徴点・ペア設定ステップにおいて、パターン基底ペアの第１特徴点と第２特徴点との距離を、第１の所定の距離以内の条件を満足するようにパターン基底ペアを設定することが望ましい。
【０００８】
第１の所定の距離として、原パターンの最大直径に相当する距離を採用することが出来る。
【０００９】
更にまた、第１探索ステップにおいて、パターン局部座標点群を展開する方法として、パターン基底ペアとパターン局部座標点群の各々に対応する被探索画像上の点との距離が第２の所定の距離以内となる条件を満足する特徴点に対してパターン局部座標系上での座標計算を行ってパターン局部座標点群を展開することが望ましい。
【００１０】
記第１探索ステップにおいて、パターン局部座標点群を展開する方法として、パターン基底ペアを代表する所定位置とパターン局部座標点群の各々に対応する被探索画像上の点との距離が第２の所定の距離以内となる条件を満足する特徴点に対してパターン局部座標系上での座標計算を行ってパターン局部座標点群を展開することもできる。
ここに、パターン基底ペアを代表する所定位置については、パターン基底ペアの中点であることが処理の便宜上好ましい。
【００１１】
第２の所定の距離として、原パターンの最大直径に相当する距離にパターン基底ペアの長さを考慮した距離を採用することができる。
【００１２】
第２探索ステップにおいて、所定の方法を、
得られた対象ポーズの各々を基準対象ポーズとして、基準対象ポーズごとに当該基準対象ポーズとその他の対象ポーズとのポーズ間距離を求め、然る後に、基準対象ポーズごとに、当該基準対象ポーズとの違いが所定の範囲内にある全ての他の対象ポーズの各々とのポーズ間距離に対して、ポーズ間距離に依存し且つポーズ間距離の増加に対し減少する関係にある所定の関数の値を計算し、各計算結果の加算値を当該基準対象ポーズのスコアとして、該スコアが所定の数値以上であった当該基準対象ポーズを対象ポーズの小集合（以降、クラスタともいう）の核として認定する手順を全ての基準対象ポーズに対して実行し、認定された基準対象ポーズの中でスコアが最も高い基準対象ポーズを最も正確らしい対象ポーズとして選定する方法とすることが望ましい。
【００１３】
所定の範囲内を、
基準対象ポーズを（ｔｘｏ、ｔｙｏ、θｏ、ｓｏ）
他の対象ポーズを（ｔｘ、ｔｙ、θ、ｓ）
としたとき、
（ｔｘ−ｔｘｏ）の絶対値が（所定最大許容範囲ｔｘｍａｘ）未満
（ｔｙ−ｔｙｏ）の絶対値が（所定最大許容範囲ｔｙｍａｘ）未満
（θ−θｏ）の絶対値が（所定最大許容範囲θｍａｘ）未満
（ｓ−ｓｏ）の絶対値が（所定最大許容範囲ｓｏｍａｘ）未満
を満たす（ｔｘ、ｔｙ、θ、ｓ）の範囲とすることができる。
【００１４】
所定の関数を、
基準対象ポーズを（ｔｘｏ、ｔｙｏ、θｏ、ｓｏ）
他の対象ポーズを（ｔｘ、ｔｙ、θ、ｓ）
基準対象ポーズと他の対象ポーズのポーズ間距離を
ｄ（（ｔｘ、ｔｙ、θ、ｓ），（ｔｘｏ、ｔｙｏ、θｏ、ｓｏ））
としたとき、
１／｛０．５＋ｄ（（ｔｘ、ｔｙ、θ、ｓ），（ｔｘｏ、ｔｙｏ、θｏ、ｓｏ））｝
とすることができる。
【００１５】
また、原パターン局部座標点群およびパターン局部座標点群を、原パターンおよびパターンそれぞれの、輪郭上で選択された特徴点ペアを構成する複数個の特徴点か、輪郭上で選択された複数個の特徴点ペアを構成する特徴点と輪郭上で所定の方法で選択されたその他の点との組合せかのいずれかとすることができる。
上記その他の点を選択する所定の方法については、第１特徴点を基準に隣り合う第１特徴点との間で、輪郭上で直線距離か輪郭沿線距離かどちらかの点間距離を測りその他の点として選択する方法等がある。
【発明の効果】
【００１６】
本発明により、原パターンが任意形状の場合、いろいろな図形あるいは文字が複合あるいは組合わされることにより複雑化した場合、または大きなサイズとなった場合において、被探索画像上のパターンが原パターンに対し任意姿勢、相似あるいは同一サイズの場合、一部隠れの場合、または大きなサイズとなった場合においても、短い処理時間で、探したいパターンを被探索画像の中から高速に探し出すことが可能になった。
通常、実際の画像探索においては、所定の探索条件において原パターンに合致する被探索画像上のパターンを最初の探索作業で探し出すことで十分な場合と、原パターンに概略合致すると思われる被探索画像上のパターンを第１番目の作業としてまず探し出し（この探索作業を祖サーチという場合が多い）、第２番目の作業として、探し出したパターンに対して正確に合致しているか否かのチェックと必要に応じて探し出したパターンの正確な姿勢を求める作業（この作業を精サーチと呼ぶ場合が多い）を行う場合の両方があるが、前者の場合または後者の場合の第１番目の祖サーチに相当する作業を本発明による手段で行うことによって探索時間が大幅に短縮できる効果がある。
【発明を実施するための最良の形態】
【００１７】
本発明を実施するための最良の形態について実施例と共に説明する。
【実施例１】
【００１８】
本発明における実施例１の高速画像探索方法は、基本的に、探索したい元図形パターン（原パターン）を探索に先立って予めジオメトリックハッシング手法を使用して登録する登録プロセスを実行した後、被探索画像の中の探索対象となる図形パターン（対象パターン）をジオメトリックハッシング手法を使用して探索する探索プロセスを実行することにより、被探索画像において探索したい原パターンと同一または相似の関係にある１個以上の図形パターンを高速に探し出す方法であり、課題解決のための第１から第４の手段に係る方法である。
【００１９】
登録プロセスにつき、図１に示す登録プロセスの一例を示すフロ−チャートをベースに、以下説明する。
＜ステップＳ１０１＞
被探索画像において探索したい図形パターンの元図形パターンである原パターンの輪郭上に２個の特徴点の組（第１の特徴点をＰｉ１、第２の特徴点をＰｉ２とする）からなる特徴点ペアを複数組（ｉ＝１、２、・・・、ｎ）抽出・設定する。
特徴点抽出・設定の方法は、原パターンの輪郭を明確にするための前処理、エッジ抽出、細線化、追跡等の適切な処理により得られた原パターンの輪郭上全域にわたって、予め決められた間隔で第１の特徴点Ｐｉ１を設定する。つぎに、各第１の特徴点Ｐｉ１における輪郭の法線（以降、特徴点設定線ともいう）
を求め、該法線が輪郭と交差するＰｉ１以外の点を第２の特徴点Ｐｉ２として抽出する。当然のことながら、同じ第１の特徴点Ｐｉ１に対して複数の第２の特徴点Ｐｉ２が抽出されることはあり得る。
ここで、第１の特徴点Ｐｉ１の設定における「予め決められた間隔」は、隣り合う２個の第１の特徴点間の直線距離が予め決められた画素数となるように決める方式を採る。他の方式として、上記方式において「直線距離」の代わりに「輪郭に沿って（輪郭が通過する）画素数」を採用することもできる。以上の「予め決められた間隔」を決める画素数は、原パターンの形状の複雑度、サイズ、画像探索の精度と探索に要する時間の制限等に依存して最適な画素数が選択される。また一般的には、上記間隔は固定の間隔である必要はなく、定数であることも包含する所定の関数に従って決められる間隔（所定の間隔）であってもよい。
＜ステップＳ１０２＞
任意の新たな特徴点ペア（Ｐｉ１、Ｐｉ２）を選択する。特徴点ペア（Ｐｉ１、Ｐｉ２）を原パターン基底ペアとも呼ぶ。
＜ステップＳ１０３＞
選択された特徴点ペアからなるベクトル（第１の特徴点Ｐｉ１を始点とし第２の特徴点Ｐｉ２を終点とする原パターン基底ベクトル）を正規化し、正規化された単位ベクトル上に局部座標系（ｘｉｙｉ座標系）のｘｉ軸が存在し、局部座標系の原点が単位ベクトルの始点と終点の中点と一致するように局部座標系を定め、これを基準に当該特徴点ペア以外の特徴点についても特徴点ペアの正規化に対応する正規化を行い、これらの局部座標を計算し原パターンを局部座標系上に展開する。この展開のための計算を第１の特徴点Ｐｉ１だけからなる点群に限って行うか、第１の特徴点Ｐｉ１と第２の特徴点Ｐｉ２の両方を含んだ点群で行うかは、原パターンを局部座標系上で展開するときの精度と本発明の目的である高速探索のための計算時間短縮の比較バランスによって選択すればよい。
＜ステップＳ１０４＞
局部座標と同一座標目盛を持つ基準座標系上に局部座標系上に展開された正規化された原パターンを変換するために、局部座標系上に展開されている特徴点（一般的には、上述の点群）の座標（局部座標）を基準座標系上の座標に変換する。
＜ステップＳ１０５＞
基準座標系の所定の領域を所定の基準で細分化し、細分化された小領域に対応する情報セルをもつハッシュテーブル上の、計算された各特徴点（あるいは、上述の点群）が存在する小領域に対応する情報セルにそのとき選択されている特徴点ペアの識別情報を登録する。識別情報としては、特徴点ペアの番号ｉを使用することが便宜的である。基準座標系を細分化する基準は、特徴点Ｐｉ１の設定ピッチより細かいことが望ましい。
ステップ６において、登録するために設定されたｎ組の特徴点ペアの選択がすべて済んだかどうかを判定し、選択がすべて済んでいなければステップＳ１０２へジャンプし以降のステップを再度実行し、選択がすべて済んでいれば登録プロセス終了とする。
【００２０】
つぎに、探索プロセスにつき、図２示す探索プロセスの一例を示すフローチャートをベースに、以下説明する。
＜ステップＳ２０１＞
被探索画像上のパターンの輪郭上に２個の特徴点の組（第１の特徴点をＯｊ１、第２の特徴点をＯｊ２とする）からなる特徴点ペアを複数組（ｊ＝１、２、・・・、ｍ）抽出・設定する。その方法は、図１のステップＳ１０１において２個の特徴点の組（第１の特徴点をＰｉ１、第２の特徴点をＰｉ２とする）からなる特徴点ペアを複数設定した方法と同様である。
ここで、一般的には、被探索画像は各種図形パターンが混在し、また重なって一部が隠れている等、原パターンとは様相が異なる複雑図形であることが多いことから、抽出・設定された特徴点ペアの数は原パターンの場合より多くなるのが通例である。
これに対し、特徴点ペアの数を更に減らして画像探索の高速化を計る手段として、後述するような、選択する特徴点ペア間距離を第１の所定の距離以下に限定する手段をとる。
＜ステップＳ２０２＞
被探索画像上のパターンの輪郭上の任意の新たな特徴点ペア（Ｏｊ１、Ｏｊ２）を選択し、新たな特徴点ペアに対するステップＳ２０３の作業のために基準座標系上の全てのデータを消去（リセット）する。特徴点ペア（Ｏｊ１、Ｏｊ２）を被探索画像上のパターン基底ペアとも呼ぶ。
＜ステップＳ２０３＞
選択された特徴点ペアからなるベクトル（特徴点Ｏｊ１を始点とし特徴点Ｏｊ２を終点とする被探索画像上のパターン基底ベクトル）を正規化し、正規化された単位ベクトル上に局部座標系（ｘｊｙｊ座標系）のｘｊ軸が存在し、局部座標系の原点が単位ベクトルの始点と終点の中点と一致するように局部座標系を定め、これを基準に被探索画像上のパターンを局部座標系上に展開するために、当該特徴点ペア以外の特徴点についても当該特徴点ペアの正規化に対応する正規化を行い、これらの局部座標を計算する。然る後に、基準座標系上に局部座標系上に展開された正規化された対象パターンを変換するために、局部座標系上に展開されている特徴点の座標（局部座標）を基準座標系上の座標に変換する。
基準座標系については、一般には座標システムについての制限はないが、実用面からは局部座標系と同一のシステムの座標系であることが好ましい。また、座標軸の目盛システムが局部座標系と同一であることが更に好ましい。
上記「当該特徴点ペア以外の特徴点についても当該特徴点ペアの正規化に対応する正規化を行い、これらの局部座標を計算する」ことを行う際に、計算する特徴点の数を減らして画像探索の高速化を計る手段として、後述するような、局部座標計算対象となる特徴点の範囲を局部座標系の所定位置から所定の関係にある第２の所定の距離以下の範囲に限定する手段をとる。
＜ステップＳ２０４＞
変換した各特徴点の座標に対応したハッシュテーブルの情報セルに原パターンの特徴点ペアの識別情報が存在すれば、存在する全ての識別情報の各々が示す原パターンの特徴点ペアに対応した投票箱（以降、特徴点ペア投票箱ともいう）に投票する。
＜ステップＳ２０５＞
特徴点ペア投票箱の中で得票数の最も高いものを選び、その得票数が所定の閾値より高いときに、この特徴点ペア投票箱に対応する原パターンの特徴点ペアと選択されている被探索画像上のパターンの特徴点ペアの間の位置・角度（姿勢）・尺度（相似）の関係（以下、対象ポーズともいう）を計算する。対象ポーズの定義の例については後述する。  
＜ステップＳ２０６＞
設定されたｍ組の特徴点ペアの各々の選択に対してステップＳ２０２以降の実行がすべて済んだかどうかを判定し、すべて済んでいなければステップＳ２０２へジャンプし以降のステップを再度実行し、すべて済んでいればステップＳ２０７に進む。
＜ステップＳ２０７＞
以上のステップで求められた１個以上の類似群分布を持つ対象ポーズ群から後述するクラスタリング方法により１個以上の類似群分布の各々において最も正確度の高い対象ポーズを選び出すことにより、そのときの対象ポーズの計算対象となった被探索画像上のパターンを原パターンに最も類似しているパターンとして選び出すことによって、１個以上の最も類似しているパターンを選び出す。
【００２１】
対象ポーズの定義およびクラスタリング方法による最も正確度の高い対象ポーズの選び出し方を以下に説明する。
【００２２】
実施例１における対象ポーズの定義の例を以下に示す。
ステップＳ２０５において記載した「特徴点ペア投票箱の中で得票数の最も高いものを選び、その得票数が所定の閾値より高いときに、この特徴点ペア投票箱に対応する原パターンの特徴点ペアと選択されている被探索画像上のパターンの特徴点ペア」について、「この特徴点ペア投票箱に対応する原パターン」を図３（ａ）に示すパターンとし、そのときの特徴点ペアを（Ｐ１、Ｐ２）とする。また、そのとき選択されている被探索画像上のパターンを図３（ｂ）に示すパターンとし、そのときの特徴点ペアを（Ｏ１、Ｏ２）とする。
直方四辺形の画面上の原画像および被探索画像共通に、画面の直交する２辺に各々平行座標軸ｘおよびｙを持つｘｙ座標系を想定する。
原パターンの存在する原画像に対する被探索画像の尺度をｓ、原パターンに対する被探索画像上のパターンの相対的角度をθ、原パターンの基準点（図３には、例としてＰｒを基準点としてある）に対応する被探索画像上のパターンの基準点（例として、Ｏｒを基準点としてある）の相対的位置をｘ方向にｔｘ、ｙ方向にｔｙとすると、
対象ポーズは、ｓ、θ、ｔｘ、ｔｙのセット（ｓ、θ、ｔｘ、ｔｙ）として、（１）式から（４）式のように定義される。
【数１】
2006309718.tif 000003
【００２３】
つぎに、対象ポーズ群の中から最も正確度の高い対象ポーズの決定の仕方について説明する。
【数２】
2006309718.tif 000004
【数３】
2006309718.tif 000005
【数４】
2006309718.tif 000006
【００２４】
ここで、ステップＳ２０１で述べた、選択する特徴点ペア間距離を第１の所定の距離以下に制限する手段について述べる。この制限について、以降、第１の制限ともいう。
原パターンに対して同一または相似の関係にあるパターンを探す際に、被探索画像上のパターンの特徴点ペアの選択において、探索対象画像の中で同一または相似の関係にあり得るパターンの特徴点ペア間距離は、最大でも原パターンの輪郭上で最も距離が離れた２点間距離（便宜上、これを原パターン最大径ともいう）相当の被探索画像上の距離以内であり、これを超えることはありえないことから、第１特徴点Ｏｊ１と第２特徴点Ｏｊ２との距離は、原パターンの最大径に相当する被探索画像上の距離を第１の所定の距離の１例として採用し、この距離以内となるように選択する。
原パターンの最大径に相当する被探索画像上の距離の計算は、次のように求める。
予め、「探索対象画像」対「原画像」の尺度関係が明確な場合は、原パターンの最大径に対してこの尺度関係を乗じて計算する。原パターンの最大径については、現実的には、目視で最大径に近い原パターン輪郭上の２点を決め、距離を計測し、その値が真の最大径を下回らない程度の安全係数をかけた原パターン見做し最大径を使用する方法をとってもよい。また、最大径に近い原パターン輪郭上の２点の決定については、原パターンの特徴点ペア間距離の最大のものに決定することも可能である。そのときは、安全係数も現状に合わせて変更する。当然、その他の簡易計算方法をとることは可能である。
以上の第１の制限は、不要な特徴点ペアを選択することによって計算時間が増え、被探索画像上のパターン探索時間が不要に長くなることを防止できる効果を持つものである。
【００２５】
ここで、ステップＳ２０３で述べた、局部座標計算対象となる特徴点の範囲を局部座標系の所定位置から第２の所定の関係にある距離以下の範囲に制限する手段について述べる。この制限を、以降、第２の制限ともいう。
被探索画像上のパターンの各特徴点ペア（各パターン基底ペア）を正規化して局部座標系に配置し、パターン基底ペア以外の特徴点についてパターン基底ペアの正規化に対応する正規化を行い、これらの局部座標を計算して正規化したパターンを局部座標系上に展開するときに、不要に遠くの特徴点まで計算することがないように制限を加えるものである。
その手段は、計算されるべき特徴点は全て、いくら遠くても、パターン基底ペアをベクトル表示したパターン基底ベクトルから原パターン見做し最大径以内にあることを利用するものであり、パターン基底ベクトルから特徴点までの距離を計算し、その距離が原パターン最大径に相当する被探索画像上の距離以下の場合にのみ、特徴点の局部座標計算を行うものである。
この場合、現実的には、パターン基底ベクトル上の全ての点から特徴点までの距離の計算を厳密にやることは時間を要することでもあり、本発明の目的の高速化を妨げる方向に働きかねない。そのため、簡略方式の一つとして、第１の制限によって被探索画像上のパターンの特徴点ペア間距離の最大値を原パターン最大径相当の被探索画像上の距離以内に制限していることを鑑み、パターン基底ベクトルの中点（局部座標の原点に対応）から各特徴点までの距離が、原パターン最大径相当の被探索画像上の距離に第１の制限のところで述べた考え方の安全係数を乗じた距離からパターン基底ベクトルの長さの２分の１を差し引いた距離を第２の所定の関係にある距離の１例として、第２の所定の関係にある距離以内にある特徴点だけについて局部座標計算を行うようにするものである。
上記距離の計算において、パターン基底ベクトルの中点から各特徴点までの距離を計算しているが、必ずしもパターン基底ベクトルの中心からの距離である必要はなく、所定の方法で選択されパターン基底ベクトルの位置を代表する他の点（所定位置）からの距離であってもよい。この所定位置によって第２の所定の関係にある距離は、上記の所定位置がパターン基底ベクトルの中点であるときの考え方にならって適正に変えられることは当然である。また当然、その他の簡易計算方法は容易に考えられるものであり、どのようなものも使用することは可能である。
【００２６】
Ｓ１０１において、各第１の特徴点Ｐｉ１における輪郭の法線を求め、該法線が輪郭と交差するＰｉ１以外の点を第２の特徴点Ｐｉ２として抽出する方式を述べたが、必ずしもその方式に限定する必要はなく、上記法線に対し所定の角度をなす直線を特徴点設定線として求め、これと輪郭の第２の交点を第２の特徴点Ｐｉ２とする方式でもかまわない。一般的に、法線の方向は輪郭を求めるときに濃度分布から一義的に決められるものであり、そのように決められた法線の方向に対して所定の角度を持った直線の方向も一義的に決められることから、原パターンおよび被探索画像上のパターン双方において共通の所定の方式で特徴点ペア（Ｐｉ１、Ｐｉ２）を設定できるからである。
【００２７】
ステップＳ１０３あるいはステップＳ２０３において、局部座標系にパターンを展開するときにパターンの輪郭上の複数の特徴点ペアを構成する特徴点の局部座標を計算するとしているが、これに限る必要はなく、特徴点ペアを構成する特徴点と所定の方法によって輪郭上で選択されたその他の点の組合せか、あるいは輪郭上で選択された特徴点ペアを構成する特徴点以外の点のいずれかの複数の点群について局部座標を計算することもできる。
上記「特徴点ペアを構成する特徴点とその他の輪郭上で選択された点の組合せ」の点群について局部座標を計算する場合のひとつの方法として、予め特徴点を細かく設定しておき、特徴点ペアに使用する特徴点を所定の整数個とびに選び、パターンの展開は全ての特徴点群について計算する方法がある。また、２つの特徴点の間で一方の特徴点から所定の距離にある輪郭上の点をその他の点として選んでいく方法もある。
【００２８】
ステップＳ１０３あるいはステップＳ２０３において、局部座標系の原点を特徴点ペアベクトルの始点と終点の中点に置くとしてきたが、これに限定される必要はない。理論的には、原点は特徴点ペアベクトルと相対的に所定の関係にあればよく、正規化された単位ベクトルの始点が局部座標系（ｘｙ座標）の原点と一致し、終点がｘ軸上の１単位座標に一致するように局部座標系を定めることもできる。また、局部座標系のｘ軸についても特徴点ペアベクトルと一致させるとしてきたが、理論的には一致させる必要もなく、相互に所定の関係にあれば問題はない。ただ、本実施例の関係であれば、第２の制限にかかわる距離計算の簡略化等、諸々の計算が比較的容易になるメリットがある。
【００２９】
実施例１において、各第１の特徴点Ｐｉ１における輪郭の法線を求め、該法線が輪郭と交差するＰｉ１以外の点を第２の特徴点Ｐｉ２として抽出する方式、あるいは第１の特徴点Ｐｉ１を通り上記法線に対し所定の角度をなす直線を特徴点設定線として求め、これと輪郭の第２の交点を第２の特徴点Ｐｉ２とする方式をとることを述べてきたが、必ずしもこれらの方式に限定する必要はなく、これらとは異なるいかなる方式で輪郭上に特徴点Ｐｉ１とＰｉ２のペアを抽出しても差し支えない。ただ、その場合は、２つの特徴点の抽出の過程が短いほど処理時間および精度上好ましい。
【００３０】
また、実施例１では、ステップS２０７において最も正確度の高い対象ポーズを選び出す方式として、クラスタリング方法を選ぶと書いてきたが、必ずしもクラスタリング方法に限定する必要はない。その他の方法であってもよい。
【実施例２】
【００３１】
本実施例は、形状を表現するための特徴点の数が多い原パターンを含む画像（以降、原画像ともいう）を複数の小画像（以降、分割原画像ともいう）に分割し、任意に定めた原画像内の基準に対する各分割原画像境界枠の配置情報（位置、傾き、尺度情報であり、以降、境界枠配置情報ともいう）と各分割原画像境界枠に対する分割された原パターン（以降、分割原パターンともよぶ）の配置情報（位置、傾き、尺度情報であり、以降、分割原パターン配置情報ともいう）を登録し、被探索画像の中で各分割原パターンと同一かまたは相似の可能性の高いパターン（以降、分割パターンとも呼ぶ）を探索し、境界枠配置情報と分割原パターン配置情報とを使用して、探索された分割パターンに分割原パターンを重ねるようにして被探索画像に分割前の原パターン（あるいは、原画像）を重ねたときに、探索された分割パターン以外の分割パターンが被探索画像の中に原パターンと重なっていると見做せる状態で存在するかどうか検証することによって原パターンと同一かまたは相似のパターンを高速に探索する方法に関するもので、課題解決の第５の手段に関するものである。その内容を以下に示す。  
【００３２】
原パターンが複雑であったり大きかったりで、形状を表現するための特徴点の数が多い場合に、この様な原パターンに同一または相似のパターンを被探索画像の中から探索することは、時間がかかりすぎ、問題になることが多い。因みに計算量は、特徴点の数の３乗のオーダーとなる。
実施例２は、この問題を避けるための方法を実現した実施例であり、原画像を分割し、結果として計算に供される特徴点の数を減らすことによって高速に画像探索を行う方法に係るものである。図５（ａ）は、５個の文字列からなる原画像の例で、本実施例の方法が適用されるにふさわしい原パターンの１例である。図５（ｂ）は、図５（ａ）の原画像を５個の文字に対応して５分割した例である。
以下実施例２につき、図４に示す本実施例の方法を示すフローチャートを参照しながら原パターンの登録と対象パターンの探索の方法について説明する。
＜ステップＳ３０１＞
原パターンを含む原画像を複数の分割原画像に分割する。
そして、各分割原画像境界枠の相互位置・角度・尺度の関係である境界枠配置情報と、各分割原画像境界枠と分割原パターンの相互配置位置・角度・尺度の関係である分割原パターン配置情報が記憶される。境界枠配置情報のあり方はいろいろ考えられるが、原画像の任意に決めた基準と各分割画像境界枠の関係を数値化しておくことが好ましい方法のひとつである。
＜ステップＳ３０２＞
分割原パターン各々に対し、「分割原パターン」を「原パターン」に置き換えて、前述の図１をベースにして前述した原パターンの登録方法を実行して各分割原パターンを登録し、図２をベースにして前述した被探索画像上のパターン探索方法を実行して各分割原パターンと同一または相似関係にあるパターンを被探索画像の中から１個以上（「１個以上」は、「検出できるパターンは全て」を意味する）探索する。
＜ステップＳ３０３＞
原画像の尺度を被探索画像の尺度と合わせて、探索されたパターンの内の新たに選択されたパターンに、当該パターンに対応する分割原パターンを重ね合わせるようにして原パターンあるいは原画像と被探索画像を重ねる。
探索されたパターンの内の新たに選択されたパターンに、当該パターンに対応する分割原パターンを重ね合わせる方法は、双方の正規化相関をとり重ね合わせる等の統計的な方法をとる。ただし、一般的には必ずしも統計的な方法に限定する必要はなく、その他の一般に知れている重ね合わせの方式が採れる。
＜ステップＳ３０４＞
つぎに、被探索画像に重ねられた分割原パターン以外の原パターン部分と被探索画像との比較を、一致している画素については得票を与え、一致していない画素に対しては票を与えない方式で、画素ごとに行い、所定の基準で比較の結果を数値化し、原パターンと一致するパターンがその重ね合わせの状態で被探索画像の中に存在するか否かを当該数値によって判断し、存在する場合はそのパターンを一致リストに記憶し、存在しない場合はそのまま、ステップＳ３０５に進む。
上記比較の方式は、ステップＳ３０３で重ね合わせた分割原パターン以外の原パターン部分の輪郭を挟んだ周辺の所定の幅に当該原パターンに対応するパターンが存在するか否かを探るために、その中心に対する所定の画素範囲の画素の状態を選択的に検査するためのソフト的なウインドウを用意し、このウインドウの中心を当該の分割原パターンの輪郭に沿って移動させながら被探索画像上のパターンの存在を調べ、存在すれば投票し、最終的に「投票数」対「調べた輪郭上の点の数」の比が所定の数値以上であれば当該原パターンに一致するパターンがあったと判断する方式であり、ウインドウの大きさを調整することによって対象パターン探索時の誤差、上記重ね合わせの誤差等を吸収できる。
比較の基準・方式はこの基準・方式に限る必要は必ずしもなく、他の方式をとってもかまわない。
＜ステップＳ３０５＞
分割原パターン各々に対して、ステップＳ３０２で探索された全てのパターンに対してステップＳ３０３およびステップＳ３０４が実行されているかどうか確認し、実行されていなければ、新たな探索されたパターンを選択してステップＳ３０３に移行する。実行されていれば、一致リストに記憶されている全てのパターンを分割前の原パターンに同一か相似である可能性が高いと判断し、この高速画像探索を終了する。
【００３３】
以上の二つの実施例各々単独でも、従来の技術より進んだ画像の高速探索性能が得られるが、二つの実施例を組合せることによって、更に進んだ高速探索性能が得られる。  
【図面の簡単な説明】
【００３４】
【図１】実施例１における登録プロセスの一例を示すフローチャート
【図２】実施例１における探索プロセスの一例を示すフローチャート
【図３】対象ポーズ計算の原パターンと被探索画像上のパターンの画面上の配置を示す例である。（ａ）は、特徴点ペア投票箱に対応する原パターンに対するものであり、（ｂ）は、選択されている被探索画像上のパターンに対するものである。
【図４】実施例２の方法の１例を示すフローチャート
【図５】原画像の分割がふさわしい原画像と分割後の原画像の１例を示す図である。（ａ）は、５個の文字列からなる原画像である。（ｂ）は、原画像（ａ）を５個の文字に対応して５分割した例である。
【符号の説明】
【００３５】
Ｐ１        特徴点ペア投票箱に対応する原パターン基底ベクトルの始点
Ｐ２        特徴点ペア投票箱に対応する原パターン基底ベクトルの終点
Ｐｒ        原パターンの基準点
Ｏ１        選択されている被探索画像上のパターン基底ベクトルの始点
Ｏ２        選択されている被探索画像上のパターン基底ベクトルの終点
Ｏｒ        被探索画像上のパターンの基準点
ｓ          原画像に対する被探索画像の尺度
θ          原パターンに対する被探索画像上のパターンの相対的角度
ｔｘ        原パターンの基準点に対応する被探索画像上のパターンの基準点の相対的位置（ｘ方向）
ｔｙ        原パターンの基準点に対応する被探索画像上のパターンの基準点の相対的位置（ｙ方向）
【図１】
2006309718.tif 000007
【図２】
2006309718.tif 000008
【図３】
2006309718.tif 000009
【図４】
2006309718.tif 000010
【図５】
2006309718.tif 000011