(57)【要約】【課題】  テンプレート照合の高速化をはかる。【解決手段】  テンプレートからサイズの異なるサブテンプレートを生成し、小さいものから順に照合操作を行い、類似性があると判断されたときに段階的にサイズの大きなサブテンプレートで照合を行う。サブテンプレートを用いた照合の計算途中で類似性がないと判断された場合、その照合をうち切り、同時にその近傍の領域との照合も省略する。また、類似するテンプレート同士をグループ化し、グループ内で異なるテンプレートに含まれるサブテンプレート間の自己距離値を事前に算出しておくことで、ある参照サブテンプレートで照合した結果をグループ内で反映し、三角不等式の原理で計算の省略を行う。【選択図】      図１
2006031392.tif 000002
【特許請求の範囲】
【請求項１】
テンプレートとして与えられる既知の信号と類似する信号を、入力され取り込まれる入力信号から検出し、その位置を求めるテンプレート照合装置であって、
前記テンプレートから段階的にサイズの異なるサブテンプレートを生成するサブテンプレート生成部と、
前記入力信号と、前記サブテンプレート生成部によって順次生成されるサブテンプレートとの距離値を計算し、類似することが確認された場合、テンプレート全体との距離値を追加計算するマッチング演算部と、
を具備することを特徴とするテンプレート照合装置。
【請求項２】
前記マッチング演算部は、
前記段階的にサイズの異なるすべてのサブテンプレートについて、前記テンプレート上の当該サブテンプレートと同じ大きさのあらゆる部分領域との距離値を計算する自己距離値計算部と、
前記入力信号上で、前記テンプレートと同じ大きさのあらゆる局所領域を設定する局所領域設定部と、
前記局所領域の順序を並び換える局所領域順序設定部と、
前記局所領域順序設定部で設定された順に一つの局所領域を取り出し候補局所領域とし、該候補局所領域と前記テンプレート間の距離下限値をあらかじめ定義された閾値と比較した結果、次に照合すべき候補局所領域を選択する候補局所領域選択部と、
前記段階的サブテンプレート生成部で得られる複数のサブテンプレートから、サイズの小さい順にサブテンプレートを一つ選択するサブテンプレート選択部と、
前記候補局所領域選択部から得られる候補局所領域の一部の領域と、前記サブテンプレート選択部で得られるサブテンプレートとを逐次照合して部分距離値を計算する部分距離値計算部と、
前記部分距離値計算部で得られた部分距離値が類似する場合、前記テンプレートの残りの領域と、前記候補局所領域の残りの領域との距離を追加して、前記テンプレートと当該候補局所領域間との距離値を求める追加距離値計算部と、
前記追加距離値計算部で得られた距離値が目標とする閾値を下回る場合、その検出結果と前記閾値を更新する検出結果更新部と、
前記自己距離値計算部、ならびに前記部分距離値計算部で計算され出力されるそれぞれの距離値を用いて、前記候補局所領域近傍の局所領域の距離下限値を更新することにより、前記テンプレートに類似する信号が存在する可能性がない局所領域候補を削除する候補局所領域枝刈部と、
を具備することを特徴とする請求項１に記載のテンプレート照合装置。
【請求項３】
テンプレートとして与えられる既知の信号と類似する信号を、入力され取り込まれる入力信号から検出し、その位置を求めるテンプレート照合装置であって、
前記テンプレートから所定のサイズのサブテンプレートを複数生成するサブテンプレート生成部と、
前記サブテンプレートから照合を行う参照サブテンプレートを前記テンプレート毎に決定する参照サブテンプレート決定部と、
前記テンプレートのうち特徴が類似するテンプレートをグルーピングし、当該グループ内で前記テンプレートに跨るサブテンプレートの自己距離値を事前に算出し、前記ある参照サブテンプレートで照合した結果を前記グループ内に反映させるマッチング演算部と、
を具備することを特徴とするテンプレート照合装置。
【請求項４】
前記マッチング演算部は、
前記参照サブテンプレート決定部で決定される参照サブテンプレートと、同グループ内のサブテンプレートとの距離値をテンプレートに跨ってすべて計算する自己距離値計算部と、
前記入力信号上で前記テンプレートと同じサイズのあらゆる局所領域を設定する局所領域設定部と、
前記局所領域の順序を並び換える局所領域順序設定部と、
前記参照サブテンプレート決定部で決定された参照サブテンプレートの集合から、順次参照サブテンプレートを取り出す参照サブテンプレート選択部と、
前記局所領域順序設定部により設定された順に一つの局所領域を取り出し候補局所領域とする候補局所領域選択部と、
前記候補局所領域選択部で選択された候補局所領域と前記テンプレートとの距離下限値をあらかじめ定義された閾値と比較する距離下限値評価部と、
前記候補局所領域選択部から得られる候補局所領域の一部と、前記参照サブテンプレート選択部で選択された参照サブテンプレートとを照合し、部分距離値を計算する部分距離値計算部と、
前記部分距離値計算部で得られた部分距離値が類似する場合、前記テンプレートの残りの領域と、前記候補局所領域の残りの領域との距離を追加して、前記テンプレートと候補局所領域間との距離値を計算する追加距離値計算部と、
前記追加距離値計算部で得られた距離値が、目標とする閾値を下回る場合に、その検出結果と前記閾値を更新する検出結果更新部と、
前記自己距離値計算部、ならびに前記部分距離値計算部で計算されたそれぞれの距離値を用い、前記候補局所領域近傍の局所領域の距離下限値を更新することにより前記テンプレートに類似する信号が存在する可能性のない局所領域候補を削除する候補局所領域枝刈部と、
を具備することを特徴とする請求項３に記載のテンプレート照合装置。
【請求項５】
前記部分距離値計算部、および前記追加距離値計算部は、
前記距離値を順次計算し、近似的に計算の必要がない、もしくは既に計算の必要がないと判断された時点で計算を終了することを特徴とする請求項２または４に記載のテンプレート照合装置。
【請求項６】
前記サブテンプレート生成部は、
前記自己距離値計算部によって算出される自己距離値の最大値が、最小になるサブテンプレートを段階的に生成することを特徴とする請求項２に記載のテンプレート照合装置。
【請求項７】
前記参照テンプレート決定部は、
グループ内のすべてのサブテンプレート間距離値の最大値が、最小となるようなサブテンプレートを参照サブテンプレートとして決定することをと特徴とする請求項４に記載のテンプレート照合装置。
【請求項８】
前記局所領域順序設定部は、
所定の間隔を空けて前記順序の並び替えを行うことを特徴とする請求項２または４に記載のテンプレート照合装置。
【請求項９】
前記局所領域順序設定部は、
前記距離値の分布に基づき、適当な間隔を持つように並び替えを随時行うことを特徴とする請求項２または４に記載のテンプレート照合装置。
【請求項１０】
前記局所領域順序設定部は、
前記入力信号を再帰的に分割したピラミッド画像の中心の位置を大きな画像から順に並べ、前記候補局所領域を取り出す順序に用いることを特徴とする請求項２または４に記載のテンプレート照合装置。
【請求項１１】
前記局所領域順序設定部は、
前記局所領域候補順序を２進数表現し、最上位の１より下位の値をビット反転し、昇順もしくは降順に並べ直したものから順に並べ、前記候補局所領域を取り出す順序に用いることを特徴とする請求項２または４に記載のテンプレート照合装置。
【請求項１２】
前記入力信号および前記テンプレートに１次元の音信号を用いることを特徴とする請求項１〜４のいずれか１項に記載のテンプレート照合装置。
【請求項１３】
前記入力信号およびテンプレートに１次元の映像信号を用いることを特徴とする請求項１〜４のいずれか１項に記載のテンプレート照合装置。
【請求項１４】
前記入力信号およびテンプレートに２次元の画像信号を用いることを特徴とする請求項１〜４のいずれか１項に記載のテンプレート照合装置。
【請求項１５】
テンプレートとして与えられる既知の信号と類似する信号を、入力され取り込まれる入力信号から検出し、その位置を求めるテンプレート照合方法であって、
前記テンプレートから段階的にサイズの異なるサブテンプレートを生成する第１のステップと、
前記入力信号と、順次生成されるサブテンプレートとの距離値を計算し、類似することが確認された場合、テンプレート全体との距離値を追加計算する第２のステップと、
を有することを特徴とするテンプレート照合方法。
【請求項１６】
前記第２のステップは、
前記段階的にサイズの異なるすべてのサブテンプレートについて、前記テンプレート上の当該サブテンプレートと同じ大きさのあらゆる部分領域との距離値を計算するサブステップと、
前記入力信号上で、前記テンプレートと同じ大きさのあらゆる局所領域を設定するサブステップと、
前記局所領域の順序を並び換えるサブステップと、
前記設定された順に一つの局所領域を取り出し候補局所領域とし、該候補局所領域と前記テンプレート間の距離下限値をあらかじめ定義された閾値と比較した結果、次に照合すべき候補局所領域を選択するサブステップと、
前記複数のサブテンプレートから、サイズの小さい順にサブテンプレートを一つ選択するサブステップと、
前記選択された候補局所領域の一部の領域と、前記選択されたサブテンプレートとを逐次照合して部分距離値を計算するサブステップと、
前記得られた部分距離値が類似する場合、前記テンプレートの残りの領域と、前記候補局所領域の残りの領域との距離を追加して、前記テンプレートと当該候補局所領域間との距離値を求めるサブステップと、
前記得られた距離値が目標とする閾値を下回る場合、その検出結果と前記閾値を更新するサブステップと、
前記計算され出力される自己距離値ならびに部分距離値を用いて、前記候補局所領域近傍の局所領域の距離下限値を更新することにより、前記テンプレートに類似する信号が存在する可能性がない局所領域候補を削除するサブステップと、
を有することを特徴とする請求項１５に記載のテンプレート照合方法。
【請求項１７】
テンプレートとして与えられる既知の信号と類似する信号を、入力され取り込まれる入力信号から検出し、その位置を求めるテンプレート照合方法であって、
前記テンプレートから所定のサイズのサブテンプレートを複数生成する第１のステップと、
前記サブテンプレートから照合を行う参照サブテンプレートを前記テンプレート毎に決定する第２のステップと、
前記テンプレートのうち特徴が類似するテンプレートをグルーピングし、当該グループ内で前記テンプレートに跨るサブテンプレートの自己距離値を事前に算出し、前記ある参照サブテンプレートで照合した結果を前記グループ内に反映させる第３のステップと、
を有することを特徴とするテンプレート照合方法。
【請求項１８】
前記第３のステップは、
前記決定される参照サブテンプレートと、同グループ内のサブテンプレートとの自己距離値をテンプレートに跨ってすべて計算するサブステップと、
前記入力信号上で前記テンプレートと同じサイズのあらゆる局所領域を設定するサブステップと、
前記局所領域の順序を並び換えるサブステップと、
前記決定された参照サブテンプレートの集合から、順次参照サブテンプレートを選択するサブステップと、
前記設定された順に候補局所領域を選択するサブステップと、
前記選択された候補局所領域と前記テンプレートとの距離下限値をあらかじめ定義された閾値と比較するサブステップと、
前記選択された候補局所領域の一部と、前記選択された参照サブテンプレートとを照合し、部分距離値を計算するサブステップと、
前記部分距離値が類似する場合、前記テンプレートの残りの領域と、前記候補局所領域の残りの領域との距離を追加して、前記テンプレートと候補局所領域間との距離値を計算するサブステップと、
前記得られた前記テンプレートと候補局所領域間の距離値が、目標とする閾値を下回る場合に、その検出結果と前記閾値を更新するサブステップと、
前記計算された自己距離値ならびに部分距離値を用いて、前記候補局所領域近傍の局所領域の距離下限値を更新することにより、前記テンプレートに類似する信号が存在する可能性のない局所領域候補を削除するサブステップと、
を有することを特徴とする請求項１７に記載のテンプレート照合方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テンプレートとして与えられる既知の信号と類似する信号を、入力され取り込まれる入力信号から検出し、その位置を求めるテンプレート照合装置および方法であって、例えば、入力信号が音・映像の場合は、テレビ・ラジオ放送などからのＣＭ・楽曲検出技術などに、画像の場合は、人物や物体などのコンテンツの検索・位置推定などに用いて好適な、テンプレート照合装置および方法に関する。
【背景技術】
【０００２】
画像から目的の物体を探索して見つけ出す技術は，画像データベースからの検索、映像データに対するインデックスの付与、物体の追跡など、広範な応用分野における要素技術である。代表的な技術にテンプレート照合法がある（例えば、非特許文献１参照）。
【０００３】
テンプレート照合法は、目的物体の画像(テンプレート)と類似する入力画像上の部分領域を見つけ出す技術である。テンプレート内の各画素のＲＧＢ値を要素とするベクトルをＴと表記する。テンプレート照合法では、入力画像上にテンプレートＴと同じサイズの窓をあて、窓とテンプレートの距離を計算する。その距離には，絶対値距離(ＳＡＤ：Sum of Absolute Differences)や２乗距離(ＳＳＤ：Sum of Square Differences)が広く用いられる。画像上のある位置(u,v)における窓の各面素のＲＧＢ値を要素とするベクトルをＷ(u,v)で表現したとき、絶対値距離ＳＡＤは、以下の式（１）で示される。
【０００４】
【数１】
2006031392.tif 000003
【０００５】
ここで、Ｔｐ、ＷｐはそれぞれＴ，Ｗ(u,v)のｐ番目の輝度である。入力画像上で窓を走査して(u,vを変えて)距離を計算し、距離が最小、あるいはあらかじめ設定した閾値以下の位置を求める。
テンプレート照合法では、テンプレートと窓の距離の計算量が大きく、また、走査する窓の数が多いという問題がある。計算量を削減するために、距離の計算量を削減する手法と、距離計算回数を削減する手法がある。
【０００６】
距離の計算量を削減する代表的な手法には、逐次残差検定法(ＳＳＤＡ：Sequential Similarity Detection Algorithm)がある（例えば、非特許文献２参照）。逐次残差検定法では、距離計算の途中で閾値と随時比較し、閾値を超えたとき、その処理を終了する。Chaoらは、距離計算時における閾値を計算した画素数に応じて適切に変えることで、ＳＳＤＡを効果的に実行している（例えば、非特許文献３参照）。
【０００７】
距離計算の回数を削減する代表的な手法には、２段階テンプレート照合法がある（例えば、非特許文献４参照）。２段階テンプレートでは、テンプレートの一部であるサブテンプレートを用いて、各窓での、距離下限値を計算し、距離下限値が閾値以下の窓のみテンプレート全休で照合を行う。また、Liらは、テンプレートＴのベクトルの大きさ|T|と各窓のベクトルＷの大きさ|W|に対して三角不等式を適用し、照合不要な領域を算出している（非特許文献５参照）。
Leeらは、低解像度の画像で距離を計算し、その距離から高解像度画像での距離下限値を計算することによって、効率的に照合不要な領域を計算している（例えば、非特許文献６参照）。しかしながら、上記の手法は、既に照合した窓とテンプレートの距離と、閾値との差から削減可能かどうかを判定するものがほとんどであるため、計算量の削減幅には限界があった。
【０００８】
一方、これまで我々が開発してきたアクティブ探索法は、ある窓での照合結果を利用してその近傍の窓における類似値の上限値を計算し、上限値が閾値を下回る場合に、照合を省略するため、極めて効率よく、不要な照合を省略できる（例えば、非特許文献７、８、特許文献１、２参照）。
しかしながら、特徴にヒストグラムを利用するため、形状情報や色の距離情報が失われ、細かい形の違いや、位置決め制度が重要になる場合には適用することが難しく、また類似色ヒストグラムを持つ異なる窓を誤検出することも起こりえた。
【０００９】
また、我々はこれまで、テンプレート内のサブテンプレートの類似性を利用して効率よ<照合の省略を行うSkipping Template Matching（ＳＴＭ）法を開発した（例えば、非特許文献９、１０参照）。
ここに開示された技術によれば、目的とする物体のテンプレートから生成されるサブテンプレート間の類似性が高いことが多い場合には、上記した従来の手法よりも効果的に照合操作を省略できる。
【００１０】
しかしながら、物体が３次元形状を持つ場合、カメラと物体の位置関係によって、カメラが撮影した物体の画像は、見え方(物体の向きや大きさ)が異なるため、見え方に対応した多数のテンプレートを準備する必要がある。物休の画像が異なっても高速に探索する技術には、サイズや向きの異なる多数の物体の画像を探索する手法がある。多数のテンプレートを用いることによる計算量の増大を軽減するため、部分空開法を使ってテンプレートの次元数を圧縮する手法などが提案されている（例えば、非特許文献１１参照）。しかしながら、次元圧縮の計算量コストが大きく、さらなる高速化が期待されている。
【非特許文献１】尾上(編):“画像処理ハンドブッグ、昭晃堂(1987)
【非特許文献２】D.I. Barnea and H.F. Silverman: A class of algorithms for fast digital image registration￥", IEEE Trans. on Comput・, C-21, 2, pp.179-186(1972)
【非特許文献３】H.C. Chao, Y.P.Hung and W.L Hwang:Adaptive early jump-out technique for fast motion estimation in video coding", Proc. 0f ICPR1996,Vol.2, pp.864-868(1996)
【非特許文献４】A, Hatabu, T, Miyazaki and I.Kuroda:‘'Optimization of decision-timing for early termination of SDDA-based block matching", Proc. of 1CME 2003, vol・2，pp.821-824 (2003)
【非特許文献５】G.J, Vanderbrug and A・ Rosenfeld: "Two stage template matching",IEEE Trans. on Comput・ , C-26, 4, pp.384-393, 1 977
【非特許文献６】W. Li and E， Salari: '‘Successive elimination algorithm for motion estimation"FIEEE Trans. on Image Processing, 4.1 , pp. 105-107 (1995)
【非特許文献７】V.V, Vinod and H . M urase: ‘'Focused color intersection with efficient searching for object extraction“, Pattern Recognition, 30, 10pp. 1787-1797(1997)
【非特許文献８】T. Kawanishi, H. M urase, S. Takagi and M. Werner:j' Dynamic Active Search for quick object detection with pantilt-zoom camera", Proc. of ICIP 2001,Vol. 31 pp. 716-719(2001)
【非特許文献９】川西、黒住、柏野、高木:“参照画像の部分領域の残瀋情報を利用した高速テンプレート照合法", FIT2003情報科学技術フォーラム情報レターズ，2，pp.175-176 (2003)
【非特許文献１０】T, Kawanishi, T. Kurozumi, S. Takagi and K, Kashino: “Skipping Template Matching guaranteeing same accuracy as exhaustive search", Proc. of the Fifth Intl.Conf.of Advances on Pattern Recognition, pp. 209-212 (2003）
【非特許文献１１】村瀬，S.K.Nayer：“２次元照合による３次元物体認識−パラメトリック固有空間法−”信学会（D-II），J77-D-II，11，pp.2179-2187(1994)
【特許文献１】特開平９３３０４０４号公報
【特許文献２】特開２００２−３１２３４３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は上記事情に鑑みてなされたものであり、ヒストグラムを用いない場合であっても全照合とおなじ照合精度を保証しながら、テンプレートの一部であるサブテンプレートとある局所領域の一部での照合結果を利用して、テンプレートとその局所領域、さらにはその近傍の局所領域との照合を極力省略し、上記したテンプレート照合の一層の高速化をはかった、テンプレート照合装置および方法を提供することを目的とする。
【００１２】
また、上記したように３次元物体の認識では多数のテンプレートが必要となり、ＳＴＭ法を個々のテンプレートに独立に適用すれば、計算時間はテンプレートの枚数に比例して増大し、このため、向きやカメラまでの距離等の撮影パラメータが類似したテンプレート同士は、類似性を持つと予想される。このため、テンプレート間の類似性を利用することにより照合回数を削減することのできるテンプレート照合装置および方法を提供することも目的とする。
【課題を解決するための手段】
【００１３】
上記した課題を解決するために本発明は、テンプレートとして与えられる既知の信号と類似する信号を、入力され取り込まれる入力信号から検出し、その位置を求めるテンプレート照合装置であって、前記テンプレートから段階的にサイズの異なるサブテンプレートを生成するサブテンプレート生成部と、前記入力信号と、前記サブテンプレート生成部によって順次生成されるサブテンプレートとの距離値を計算し、類似することが確認された場合、テンプレート全体との距離値を追加計算するマッチング演算部と、を具備することを特徴とする。
【００１４】
また、本発明において、前記マッチング演算部は、前記段階的にサイズの異なるすべてのサブテンプレートについて、前記テンプレート上の当該サブテンプレートと同じ大きさのあらゆる部分領域との距離値を計算する自己距離値計算部と、前記入力信号上で、前記テンプレートと同じ大きさのあらゆる局所領域を設定する局所領域設定部と、前記局所領域の順序を並び換える局所領域順序設定部と、前記局所領域順序設定部で設定された順に一つの局所領域を取り出し候補局所領域とし、該候補局所領域と前記テンプレート間の距離下限値をあらかじめ定義された閾値と比較した結果、次に照合すべき候補局所領域を選択する候補局所領域選択部と、前記段階的サブテンプレート生成部で得られる複数のサブテンプレートから、サイズの小さい順にサブテンプレートを一つ選択するサブテンプレート選択部と、前記候補局所領域選択部から得られる候補局所領域の一部の領域と、前記サブテンプレート選択部で得られるサブテンプレートとを逐次照合して部分距離値を計算する部分距離値計算部と、前記部分距離値計算部で得られた部分距離値が類似する場合、前記テンプレートの残りの領域と、前記候補局所領域の残りの領域との距離を追加して、前記テンプレートと当該候補局所領域間との距離値を求める追加距離値計算部と、前記追加距離値計算部で得られた距離値が目標とする閾値を下回る場合、その検出結果と前記閾値を更新する検出結果更新部と、前記自己距離値計算部、ならびに前記部分距離値計算部で計算され出力されるそれぞれの距離値を用いて、前記候補局所領域近傍の局所領域の距離下限値を更新することにより、前記テンプレートに類似する信号が存在する可能性がない局所領域候補を削除する候補局所領域枝刈部と、を具備することを特徴とする。
【００１５】
また、本発明は、テンプレートとして与えられる既知の信号と類似する信号を、入力され取り込まれる入力信号から検出し、その位置を求めるテンプレート照合装置であって、前記テンプレートから所定のサイズのサブテンプレートを複数生成するサブテンプレート生成部と、前記サブテンプレートから照合を行う参照サブテンプレートを前記テンプレート毎に決定する参照サブテンプレート決定部と、前記テンプレートのうち特徴が類似するテンプレートをグルーピングし、当該グループ内で前記テンプレートに跨るサブテンプレートの自己距離値を事前に算出し、前記ある参照サブテンプレートで照合した結果を前記グループ内に反映させるマッチング演算部と、を具備することを特徴とする。
【００１６】
また、本発明において、前記マッチング演算部は、前記参照サブテンプレート決定部で決定される参照サブテンプレートと、同グループ内のサブテンプレートとの距離値をテンプレートに跨ってすべて計算する自己距離値計算部と、前記入力信号上で前記テンプレートと同じサイズのあらゆる局所領域を設定する局所領域設定部と、前記局所領域の順序を並び換える局所領域順序設定部と、前記参照サブテンプレート決定部で決定された参照サブテンプレートの集合から、順次参照サブテンプレートを取り出す参照サブテンプレート選択部と、前記局所領域順序設定部により設定された順に一つの局所領域を取り出し候補局所領域とする候補局所領域選択部と、前記候補局所領域選択部で選択された候補局所領域と前記テンプレートとの距離下限値をあらかじめ定義された閾値と比較する距離下限値評価部と、前記候補局所領域選択部から得られる候補局所領域の一部と、前記参照サブテンプレート選択部で選択された参照サブテンプレートとを照合し、部分距離値を計算する部分距離値計算部と、前記部分距離値計算部で得られた部分距離値が類似する場合、前記テンプレートの残りの領域と、前記候補局所領域の残りの領域との距離を追加して、前記テンプレートと候補局所領域間との距離値を計算する追加距離値計算部と、前記追加距離値計算部で得られた距離値が、目標とする閾値を下回る場合に、その検出結果と前記閾値を更新する検出結果更新部と、前記自己距離値計算部、ならびに前記部分距離値計算部で計算されたそれぞれの距離値を用い、前記候補局所領域近傍の局所領域の距離下限値を更新することにより前記テンプレートに類似する信号が存在する可能性のない局所領域候補を削除する候補局所領域枝刈部と、を具備することを特徴とする。
【００１７】
また、本発明において、前記部分距離値計算部、および前記追加距離値計算部は、前記距離値を順次計算し、近似的に計算の必要がない、もしくは既に計算の必要がないと判断された時点で計算を終了することを特徴とする。
【００１８】
また、本発明において、前記サブテンプレート生成部は、前記自己距離値計算部によって算出される自己距離値の最大値が、最小になるサブテンプレートを段階的に生成することを特徴とする。
【００１９】
また、本発明において、前記参照テンプレート決定部は、グループ内のすべてのサブテンプレート間距離値の最大値が、最小となるようなサブテンプレートを参照サブテンプレートとして決定することを特徴とする。
【００２０】
また、本発明において、前記局所領域順序設定部は、所定の間隔を空けて前記順序の並び替えを行うことを特徴とする。
【００２１】
また、本発明において、前記局所領域順序設定部は、前記距離値の分布に基づき、適当な間隔を持つように並び替えを随時行うことを特徴とする。
【００２２】
また、本発明において、前記局所領域順序設定部は、前記入力信号を再帰的に分割したピラミッド画像の中心の位置を大きな画像から順に並べ、前記候補局所領域を取り出す順序に用いることを特徴とする。
【００２３】
また、本発明において、前記局所領域順序設定部は、前記局所領域候補順序を２進数表現し、最上位の１より下位の値をビット反転し、昇順もしくは降順に並べ直したものから順に並べ、前記候補局所領域を取り出す順序に用いることを特徴とする。
【００２４】
また、本発明において、前記入力信号および前記テンプレートに１次元の音信号を用いることを特徴とする。
【００２５】
また、本発明において、前記入力信号およびテンプレートに１次元の映像信号を用いることを特徴とする。
【００２６】
また、本発明において、前記入力信号およびテンプレートに２次元の画像信号を用いることを特徴とする。
【００２７】
また、本発明は、テンプレートとして与えられる既知の信号と類似する信号を、入力され取り込まれる入力信号から検出し、その位置を求めるテンプレート照合方法であって、前記テンプレートから段階的にサイズの異なるサブテンプレートを生成する第１のステップと、前記入力信号と、順次生成されるサブテンプレートとの距離値を計算し、類似することが確認された場合、テンプレート全体との距離値を追加計算する第２のステップと、を有することを特徴とする。
【００２８】
また、本発明において、前記第２のステップは、前記段階的にサイズの異なるすべてのサブテンプレートについて、前記テンプレート上の当該サブテンプレートと同じ大きさのあらゆる部分領域との自己距離値を計算するサブステップと、前記入力信号上で、前記テンプレートと同じ大きさのあらゆる局所領域を設定するサブステップと、前記局所領域の順序を並び換えるサブステップと、前記設定された順に一つの局所領域を取り出し候補距離所領域とし、該候補局所領域と前記テンプレート間の距離下限値をあらかじめ定義された閾値と比較した結果、次に照合すべき候補局所領域を選択するサブステップと、前記複数のサブテンプレートから、サイズの小さい順にサブテンプレートを一つ選択するサブステップと、前記選択された候補局所領域の一部の領域と、前記選択されたサブテンプレートとを逐次照合して部分距離値を計算するサブステップと、前記得られた部分距離値が類似する場合、前記テンプレートの残りの領域と、前記候補局所領域の残りの領域との距離を追加して、前記テンプレートと当該候補局所領域間との距離値を求めるサブステップと、前記得られた距離値が目標とする閾値を下回る場合、その検出結果と前記閾値を更新するサブステップと、前記計算され出力される自己距離値ならびに部分距離値を用いて、前記候補局所領域近傍の局所領域の距離下限値を更新することにより、前記テンプレートに類似する信号が存在する可能性がない局所領域候補を削除するサブステップと、を有することを特徴とする。
【００２９】
また、本発明は、テンプレートとして与えられる既知の信号と類似する信号を、入力され取り込まれる入力信号から検出し、その位置を求めるテンプレート照合方法であって、前記テンプレートから所定のサイズのサブテンプレートを複数生成する第１のステップと、前記サブテンプレートから照合を行う参照サブテンプレートを前記テンプレート毎に決定する第２のステップと、前記テンプレートのうち特徴が類似するテンプレートをグルーピングし、当該グループ内で前記テンプレートに跨るサブテンプレートの自己距離値を事前に算出し、前記ある参照サブテンプレートで照合した結果を前記グループ内に反映させる第３のステップと、
を有することを特徴とする。
【００３０】
また、本発明において、前記第３のステップは、前記決定される参照サブテンプレートと、同グループ内のサブテンプレートとの自己距離値をテンプレートに跨ってすべて計算するサブステップと、前記入力信号上で前記テンプレートと同じサイズのあらゆる局所領域を設定するサブステップと、前記局所領域の順序を並び換えるサブステップと、前記決定された参照サブテンプレートの集合から、順次参照サブテンプレートを選択するサブステップと、前記設定された順に候補局所領域を選択するサブステップと、前記選択された候補局所領域と前記テンプレートとの距離下限値をあらかじめ定義された閾値と比較するサブステップと、前記選択された候補局所領域の一部と、前記選択された参照サブテンプレートとを照合し、部分距離値を計算するサブステップと、前記部分距離値が類似する場合、前記テンプレートの残りの領域と、前記候補局所領域の残りの領域との距離を追加して、前記テンプレートと候補局所領域間との距離値を計算するサブステップと、前記得られた前記テンプレートと候補局所領域間の距離値が、目標とする閾値を下回る場合に、その検出結果と前記閾値を更新するサブステップと、前記計算された自己距離値ならびに部分距離値を用いて、前記候補局所領域近傍の局所領域の距離下限値を更新することにより、前記テンプレートに類似する信号が存在する可能性のない局所領域候補を削除するサブステップと、を有することを特徴とする。
【発明の効果】
【００３１】
本発明によれば、テンプレートからサイズの異なるサブテンプレートを生成し、小さいものから順に照合操作を行い、距離値が近いと判断されたときに段階的にサイズの大きなサブテンプレートで照合することで、従来技術における２段階テンプレートマッチング法、ＳＳＤＡ法、ＡＥＪＯ法に比べ、ある領域を照合した結果、距離下限値が閾値を上回った場合に、その領域だけでなく周辺の照合を省略できるため、照合回数を少なくすることができ、このためも目的とする信号を高速に探索することができる。
【００３２】
また、特徴にヒストグラムを利用するアクティブ探索法に比べて、形状の情報や色の距離情報を含めて照合を行うため、細かい形の違いが重要になる場合や明度の変化などの影響を大きく受ける場合に精度が良い。特に、テンプレート内の特徴に低周波成分が多い場合には効果が大きい。
【００３３】
また、本発明によれば、類似するテンプレート同士をグループ化し、グループ内でテンプレートに跨ったサブテンプレートの自己距離値を事前に算出しておくことで、ある参照サブテンプレートで照合した結果をグループ内で反映し、三角不等式の原理で計算の省略を行う。このため、ＳＳＤＡ法やテンプレート照合法、或いは部分空間法に比べて、ある領域を照合した結果、距離下限値が閾値を上回った場合、その領域だけでなく周辺の照合を省略できるため照合回数を少なくすることができ、目的とする信号を高速に探索できる。特に、テンプレートをグループ化したことで、テンプレートを跨っても距離下限値を計算することができ、従来のＳＴＭ法を高速化することができる。幾つものテンプレートを同時に照合することから、多数のテンプレートが存在する3次元物体の探索に顕著な効果が得られる。
【発明を実施するための最良の形態】
【００３４】
以下、本発明実施形態に関し、図面を用いて詳細に説明する。図１は、本発明を適用した一実施形態を示すブロック図である。
本発明のテンプート照合装置は、テンプレート入力部１と、サブテンプレート生成部２と、段階的サブテンプレート生成部３と、自己距離値計算部４と、入力信号取込み部５と、局所領域設定部６と、局所領域順序設定部７と、候補局所領域選択部８と、サブテンプレート選択部９と、部分距離値計算部１０と、追加距離値計算部１１と、検出結果更新部１２と、局所領域枝刈部１３とで構成され、テンプレートと入力信号を入力とし、入力信号にテンプレートが含まれているか否かを検出し、含まれている場合にその位置と距離値を出力する機能を持つ。
なお、図１中、実線矢印は処理の流れを、点線矢印はデータ流れを示し、また、各機能ブロックは、ソフトウェアないしハードウェアによって構成されるものであり、またソフトウェアとハードウェアの組み合わせによっても実現できるものである。図２にその処理手順を、図３にテンプレート画像を、図４に入力画像の一例を示す。
【００３５】
ここでは、テンプレートと入力信号中の一部の領域を、距離値によって評価する。はじめに適当な閾値を与え、探索中に見つけた最小値ｄminを閾値として更新することによって最も類似する局所領域を発見する方法を述べる。閾値を更新せず、閾値を下回る全てを記録してその結果を返すことももちろん容易に構成できる。
ここでは、２次元の例を用いているが、Ｆ個の要素からなる１次元の入力信号を１xＦの２次元と考えることで、１次元の信号も全く同様に扱えることは明らかであり、３次元以上の信号にもまったく同じ手法で扱える。また、画像以外にも、気象データ、地図データ、遺伝子データなどの多次元ベクトル系列にも適用できる。
【００３６】
具体的に、テンプレート入力部１は、さまざまな画像フォーマットで与えられた２次元画像ファイル、あるいはさまざまなフォーマットで与えられた動画ファイルから切り出された１フレームの画像の一部、リアルタイムでキャプチャされる１フレームの画像の一部から、窓関数などを用いて物体領域を抽出し、サブテンプレート生成部２に送出する（Ｓ２１）。例えば、物体の窓関数としては、矩形形状でその内側だけを取り出すもの、円形状で内の内側だけを取り出すもの、物体の形状に合わせた形でその内側だけを取り出すものなどの窓関数が上げられる。ここでは矩形形状の例で説明する。
この取り出された信号をテンプレートと呼ぶ。テンプレートは、その画素値を要素とするベクトルで表現される。このテンプレートをＴと表現する。サブテンプレート生成部２は、テンプレート入力部１から受理したテンプレートＴからその内部のサブテンプレートＲを生成する（Ｓ２２）。ここで、例えば、テンプレートのもっとも左上の領域、あるいはもっとも右下の領域を用いる。また、１つのテンプレートを、多数の入力画像から探索する場合には自己距離値計算部４における自己距離値の最大値が、最小となるようなサブテンプレートを生成することもできる。
【００３７】
段階的サブテンプレート生成部３は、サブテンプレート生成部２から受理したサブテンプレートを最大値ＲＱとする大きさの異なる複数の段階的サブテンプレートＲｑを生成する。このとき、図に示されるように、段階的に拡大する多数のサブテンプレートＲＯ,…,ＲＱが得られる。テンプレートの左上を原点として、位置（ｉ，ｊ)のサブテンプレートをＲｑ（ｉ，ｊ）と表現する。
サブテンプレート生成部２で、テンプレートの最も左上の領域をサブテンブレートに用いた場合、このサブテンプレートはＲ（０，０）と表現できる。この場合、段階的サブテンプレート生成部３でもサブテンプレートＲ（０，０）左上の領域、すなわちテンプレートの原点を基点として拡大する段階的サブテンプレートＲｑ（０，０）を生成する（Ｓ２３）。一方、サブテンプレート生成部２で、テンプレートの最も右下の領域をサブテンプレートとして生成したならば、段階的サブテンプレートはテンプレートの左下を基点に生成されることになる。これらのすべてのサブテンプレートを、自己距離値計算部４に送出する（Ｓ２４）。
【００３８】
自己距離値計算部４は、段階的サブテンプレート生成部３で得られた段階的サブテンプレートＲｑ（ｉ，ｊ）と、テンプレート上の段階的サブテンプレートＲｑ（ｉ，ｊ）と同じサイズのテンプレート部分領域Ｔｑ（ｋ，ｌ）との距離値(または類似値)を、全ての大きさの異なる段階的サプテンプレートについて求める。仮にテンプレートの大きさより（ｍ，ｎ)小さいサブテンプレートの場合、図６に示されるような重なりを許した多数のテンプレート部分領域が得られる。その総数はこのサブテンプレートあたりｍ×ｎである。テンプレート本手法の距離尺度には、絶対値距離、２乗距離などが利用でき、類似尺度として、例えば、「足立他“正規化相互相関テンプレートマッチングのＫＬ展開を用いたＳＳＤＡ化”，信学技報PRMU96-173, pp. 23-30, 1997.」に示される正規化相互相関値も用いることができる。以下の例では、式（２）に示す絶対値距離を用いる。
【００３９】
【数２】
2006031392.tif 000004
【００４０】
次に、段階的サブテンプレート生成部３から受理したサブテンプレートＲｑ（ｉ，ｊ）と大きさが対応するすべてのテンプレート部分領域Ｔｑ（ｋ，ｌ）間の距離ｄ（Ｒｑ（ｋ，ｌ），Ｔｑ（ｋ，ｌ）)を段階的にあらかじめ計算する。さらにその距離ｄ（Ｒｑ（ｋ，ｌ），Ｔｑ（ｋ，ｌ）)と、距離ｄ（Ｒｑ（ｉ，ｊ），Ｔｑ（ｋ，ｌ）)の最大値ｄｍａｘとを局所領域枝刈部１３に送出する（Ｓ３１）。
【００４１】
一方、入力信号入力部５は、さまざまな画像フォーマットのいずれかで与えられた２次元画像ファイル、あるいはさまざまなフォーマットのうちのいずれかで与えられた動画ファイルから切り出された１フレームの画像の一部または全部、リアルタイムでキャプチャされる１フレームの画像に一部または全部を受理し、得られた画素値のベクトルＳを、局所領域設定部６に送出する（Ｓ２５）。
局所領域設定部６は、入力信号取込み部5から受理した入力画像中の照合すべき全ての局所領域の集合を作成し、局所領域順序設定部７に送出する（Ｓ２６）。局所領域の大きさは、テンプレートＴと同じ大きさである。入力画像Ｓ上の、座標（u,v)に位置する、テンプレートＴと同じ大きさの局所領域Ｓ（u,v）と表記する。局所領域の集合Ｗ＝｛S(u,v)|u,v}としたとき、テンプレートマッチシグ法による探索は、Ｗの中から、距離ｄ(T,S(ｕ,v)）が最小になる位置S(ｕ,v)を見つける技術である。Ｗ中の全てのS（u,v)に対して距離下限値bound (u,v)を導入する。全ての(u,v)に対するbound (u,v)の初期値は０にする。bound(u,v)=０。
【００４２】
局所領域順序設定部８は、Ｗに含まれる局所領域の順序（入力画像上をスキャンする順序)を設定する（Ｓ２７）。例えば、サブテンプレート生成部２でテンプレートの最も左上の領域をサブテンプレートとして取り出し照合をおこなう場合には、「右下から左上へ」の順の走査である。
逆にテンプレートの最も右下の領域をサプテンプレートに使って照合する場合には、「左上から右下へ」の順の走査になる。これは左上のテンプレートの場合には、左方向上方向へずらした局所領域の省略を可能にでき、右下のサブテンプレートの場合には、右方向下方向へずらした局所領域の省略を可能にするからである。逆に走査した場合には探索省略の効果はみられない。
【００４３】
一方、高速化のため、適当な間隔をあけるように並び替えを行った局所領域を順に選んだ方が効果的である。この方法には、距離値の分布に基づいた適当な間隔を持つように並び替えを随時行う方法や、入力信号を再帰的に分割したピラミッド画像の中心の位置を大きな画像から順に並べたものを局所領域候補順序に用いた方法、連続的な局所領域候補順序（左上から右下など)を、２進数表現し、最上位の１より下位の値をピット反転し、小さい順または大きい順に並べ直す方法などがある。このように作成したＷを候補局所領域選択部８へ送出する。
【００４４】
候補局所領域選択部８は、局所領域順序設定部７から受理した局所領域の集合Ｗからテンプレートがある可能性のある候補局所領域を選び出し、サブテンプレート選択９へ送出する（Ｓ２８）。そしてＷから先頭のS(u,v)を取り出す。ここで、bound(u,v)＞dminなら、候補局所領域選択部８による候補局所領域選択操作をもう一度実行する。bound(u,v)≦dminなら、(ｕ,v)をサブテンプレート選択部９へ送出する（Ｓ２９）。Ｗに含まれる局所領域がなくなった場合には探索を終了する。
サブテンプレート選択部９は、段階的サブテンプレート生成部３で得られた大きさの異なるサブテンプレート群から小さい順にサプテンプレートＲｑ(ｉ，ｊ)を選び出し、部分距離値計算部１０へ送出する。部分距離値計算部１０は、候補局所領域選択部８から候補局所領域の位置(u,v)を受理すると、段階的サブテンプレートの最小サブテンプレートを取り出し、(u.v)とともに部分距難値計算部１０に送出する。部分距離値計算部９から、目的の信号である可能性があるとこれらの値が帰ってきた場合、次に大きいサブテンプレートＲｑ＋１(ｉ，ｊ)を選択する。
【００４５】
部分距離値計算部１０は、サブテンプレート選択部９から受理したサブテンプレートＲｑ(ｉ，ｊ)と、候補局所領域選択部９から受理した候補局所領域S(u,v)のＲｑ(ｉ，ｊ)と同じ位置、サイズの一部の領域S(ｉ，ｊ) (u,v)との間で、距離ｄ(Ｒｑ(ｉ，ｊ) S(ｉ，ｊ) (u,v))を計算する。この距離計算の途中において、距離置計算が終了した画素が単調増加するため、距離値も同様に単調増加する。そこで、部分距離値計算部１０は、この計算途中で、遂次的に距離値が閾値を越えるかどうかを近似的に評価し、計算を打ち切るか否かを判断する（Ｓ３０）。このように構成することで、不要な距離計算を省略するＳＳＤＡ法またはＡＥＪＯ法を用いることができる。
【００４６】
ここで、閾値として、ｄｍｉｎ＋dｍａｘを用いる。距離値が、ｄｍｉｎ＋dｍａｘを越えた場合、部分距離値計算部１０は、この部分局所領域及び周辺の部分局所領域には目的の物体が含まれないことから、計算を打ち切る。または、全ての距離計算が終了後、その距離値がｄｍｉｎを越えた場合、同様に、この局所領域には、目的の物体が含まれない。距離値がｄｍｉｎ以上の場合、部分距離値計算部１０は、周辺領域に物体が含まれるかどうかを更に調べるために、その距離値ｄを、局所領域枝刈部１３に送出する。
【００４７】
一方、全ての計算が終了後、その距離値がｄｍｉｎを越えない場合、目的の物体である可能性があるので、さらに大きな領域で距離を計算するためサブテンプレート選択部９を再度実行し、次に大きいサブテンプレートＲｑ＋１(ｉ，ｊ)を選択する。最大のサブテンプレートＲＱ(ｉ，ｊ)の距離計算が終了後、距離値d(ＲＱ(ｉ，ｊ)，SＱ(ｉ，ｊ)（u,v）がｄminを越えない場合、その距離値を、追加距離値計算部１１へ送出する。
【００４８】
追加距離値計算部１１は、部分距離値計算部１０で計算した領域の距離値に、テンプレートの残りの部分と、局所領域の残りの部分との間の距離を加えることによって、テンプレートと局所領域間の距離を求める（Ｓ３２）。
ここで、テンプレートの領域がＴで、サブテンプレートＲＱ(ｉ，ｊ)に含まれない領域が~ＲＱ(ｉ，ｊ)とすれば、テンプレートＴからサブテンプレートＲＱ(ｉ，ｊ)の領域を差し引いた領域はＴ∩~ＲＱ(ｉ，ｊ)である。同様に、局所領域S(u,v)から部分局所領域ＳＱ(ｉ，ｊ)(u,v)を差し引いた領域は以下の式（３）で表現される。
【００４９】
【数３】
2006031392.tif 000005
【００５０】
つまり、部分距離計算部１０で得られた部分距離値d(ＴＱ(ｉ，ｊ)(u,v), ~ＲＱ（ｉ，ｊ））に、これらの間の距離d(Ｔ∩~ＲＱ(ｉ，ｊ)，Ｓ(u,v) ∩~ＳＱ(ｉ，ｊ)(u,v)を加えることで、テンプレートと候補局所領域の距離d(T,S(u,v))が得られる。すなわち、以下の式（４）で示される。
【００５１】
【数４】
2006031392.tif 000006
【００５２】
ここでも、部分距離値計算部１１と同様にＳＳＤＡ法またはＡＥＪＯ法を用いる。逐次的に距離値を計算した結果が、途中でｄｍｉｎを越えた場合、目的の物体ではないので、距離値計算を中断し、候補局所領域選択部９による局所領域選択処理を実行する。最後の画業まで計算して、テンプレートの距離と局所領域間の距離ｄがｄｍｉｎを越えないとき、ｄを検出結果更新部１２に送出する。
検出結果更新部１２は、追加距離値計算部１１から得た距離値ｄにより最小値ｄｍｉｎを更新し、その位置(u.v)を記録して候補局所領域選択部８による候補局所領域選択を実行する（Ｓ３３）。
【００５３】
一方、局所領域枝刈部１３は、得られた段階的サブテンプレートと、局所領域の一部との距離関係から、テンプレートと周囲における局所領域の距離値の下限値を実行する。大きな下限値を得た局所領域では、候補局所領域選択部８においてその局所領域での照合が省略できるため、精度を犠牲にすることなく探索を高速化できる。その原理を以下に示す。
ＡＥＪＯ法を用いることができる距離は、画素毎の距離を逐次的に加算することによって距離値が得られるため、比較する画素が増えると、その距離値も単調に増加する。このため、図７で示されるようなサブテンプレートＲｑ（ｉ，ｊ）と、サブテンプレートと同じ大きさの局所領域の一部Ｓｑ（ｉ，ｊ）(u,v)との距離と、テンプレートと局所領域の距離d(T,S(u,v)）との間に以下の式（５）の関係が成り立つ。
【００５４】
【数５】
2006031392.tif 000007
【００５５】
すなわち、サブテンプレートでの照合の結果不一致の場合、テンプレート全体で照合しても不一致である。さらにサブテンプレートＲｑ（ｉ，ｊ）、テンプレート部分領域Ｔｑ（ｋ，ｌ）と、Ｓｑ（ｉ，ｊ）(u,v)に関して三角不等式の原理を適用すると、以下の式（６）が成り立つ。
【００５６】
【数６】
2006031392.tif 000008
【００５７】
以上の原理に基づき、u+j-m<x<=u+i、v+j-n<y<=v+jを満たす（x,y）に関して以下の式（７）で示す下限値bound(x,y)を更新する。
【００５８】
【数７】
2006031392.tif 000009
【００５９】
上記した本発明実施形態によるテンプレート照合装置が従来手法に比べてどの程度高速であるかにつき評価を行った結果を以下に説明する。
ここでは、図４に示す画像のＲＧＢ各８ビット、ＣＩＦサイズ（３５２×２８８）画素を持つ画像を使用し、そしてその内部に合まれる５種類の物体（人、猫、梟、達磨、熊）を切り出した画像をテンプレートとした。各テンプレートの大きさは５０×５０画素である。また、入力画像には、図４に示す画像にガウスノイズを加えて生成したＳ／Ｎ比２０ｄＢの人工画像１０枚を用いた。
実験にはＣＰＵとしてIntel社製のPentium4（登録商標）プロセッサ (3.06GHZ)、ＯＳとして Red Hat Linux 8.0 の計算機を用い、コンパイラにGNU ｇ++、最適化オプションに-03を用いて生成した実行ファイルを使用した。コードの重要な部分には、Pentium 4 SSE2命令を使用した。
【００６０】
本発明実施形態によれば、サブテンプレートをどの程度の大きさで選ぶかによって、探索時間が異なる。仮に、テンプレートの大きさより(m,n)だけ小さいサブテンプレートを考える。(m,n)が大きいほど、照合を省略できる範囲が増える一方、テンプレートの類似性が小さ<距離が大きくなるため、下限値が小さくなり照合を省略できる可能性が小さくなる。このトレードオフを検討するため、サブテンプレートの大きさを(m=n=0,1,2,‥・,9)のように変化させその探索時間を調べた。但し、(m=n=0)は、ＳＳＤＡ法と一致する。部分距離値を計算するサブテンプレートは最も左上のサブテンプレートR(o,・)を用い、左下から右上へ順に探索した。
【００６１】
上記による実験結果を図８に示す。結果、どの物体に関しても、３〜７程度小さいサブンプレートを用いたときに探索時間が最小になった。５以上小さいサブテンプレートを用いても探索時間の変化は小さかった。このため、３から４あたりのマージンサイズを選択すればよいと考えられる。
【００６２】
また、サブテンプレートの大きさを最遠の直に設定し、初期閾値を150000としてその割合を１０−３から１００に変化させて探索時間を測定した。実験結果を図９に示す。結果、閾値の割合が小さくなるにしたがって近似の傾向が強まり、ＡＥＪＯ法も提案手法も探索時間が短くなる。一方、本発明実施形態によれば、１０−２より小さくなると検出漏れを生じた。
これは、ＡＥＪＯ法がサブテンプレート選択部９で選択されたサブテンプレートによる検出漏れ以外生じないのに比べ、本発明実施形態では。他のサブテンプレートによる検出漏れが生じるためである。検出率１００％になる初期閾値の割合が１０−２より大きい範囲において常に本発明実施形態による手法がＡＥＪＯ法よりも高速であった。
【００６３】
以上説明のように本発明実施形態によれば、従来技術と同じ結果を得ることを保証し、更に、従来技術より高速に目的とする信号を検出できるという優れた効果を奏し得る。この結果、本発明を画像に適用した場合には人物や物体などのコンテンツの検索、動画像中からの移動物体の追跡、ステレオ照合における対応点検出などに役立つ。また、音・映像情報に対して本発明を適用した場合には、ＣＭや希望シーンの検索などの高精度化、高速化に役立つ。
【００６４】
図１０は、本発明の他の実施形態を示すブロック図である。ここでは、本発明のテンプレート照合装置は、マルチテンプレート入力部１０１と、サブテンプレート生成部１０２と、リファレンスサブテンプレート決定部１０３と、マルチテンプレートグループ化部１０４と、自己距離値計算部１０５と、入力信号取込み部１０６と、局所領域設定部１０７と、局所領域順序設定部１０８と、リファレンスサブテンプレート選択部１０９と、候補局所領域選択部１１０と、距離下限値評価部１１１と、部分距離値計算部１１２と、追加距離値計算部１１３と、検出結果更新部１１４と、局所領域枝刈部１１５で構成され、多数のテンプレートと入力信号を入力し、入力信号中にテンプレートと類似する信号が含まれているか否かを判断し、含まれている場合に、その位置と距離値を出力する機能を持つ。
【００６５】
なお、図１０中、実線矢印は処理の流れを、点線矢印はデータ流れを示し、また、各機能ブロックは、ソフトウェアないしハードウェアによって構成されるものであり、またソフトウェアとハードウェアの組み合わせによっても実現できるものである。図１１にその処理手順が、図１２にテンプレート画像の一例が示されている。また、図１３に、マルチテンプレート入力部１０１、サブテンプレート生成部１０２、リファレンスサブテンプレート決定部１０３のそれぞれにおいて処理されるテンプレートの一例が（ａ）〜（ｃ）に、図１４に、マルチテンプレートグループ化部１０４、自己距離値計算部１０５のそれぞれにおいて処理されるテンプレートの一例が、（ａ）〜（ｃ）に示されている。
【００６６】
ここでは図１２にテンプレートの一例が示されるように、複数のテンプレートを用いて入力画像から目的の３次元物体を探索する。ここでは、テンプレートと入力信号中の一部の領域を、距離値によって評価する。はじめに適当な閾値を与え、探索中に見つけた最小値ｄｍｉｎを閾値として更新することによって最も類似する局所領域を発見する方法を述べる。閾値を更新せず、閾値を下回る全てを記録してその結果を返すことももちろん容易に構成できる。また、ここでは、２次元の例を用いているが、Ｆ個の要素からなる１次元の入力信号を1×Ｆの２次元と考えることで、１次元の信号も全く同様に扱えることは明らかであり、３次元以上の信号にも全く同じ手法で扱える。また、画像以外にも、気象データ、地図データ、遺伝子データなどの多次元ベクトル系列にも適用できる。
【００６７】
以下、詳細について説明する。マルチテンプレート入力部１０１は、さまざまな画像フォーマットで与えられた２次元画像ファイル、あるいはさまざまなフオーマットで与えられた動画ファイルから切り出された１フレームの画像の一部、リアルタイムでキャプチャされる１フレームの画像の一部から、窓関数などを用いて物体領域を抽出し、サブテンプレート生成部１０２へ送出する（Ｓ１１１）。例えば物体の窓関数としては、矩形形状でその内側だけを取り出すもの、円形状で円の内側だけを取り出すもの、物体の形状に合わせた形でその内側だけを取り出すものなどの窓関数が上げられる。ここでは図１３（ａ）に示されるように、矩形形状テンプレートの例で説明する。また、テンプレートは以下に示す方法で系統的に作成されたものとする。すなわち、物体をある軸のまわりに回転させる、スケールを段階的に変える等である。前者は、計算機などで、回転角を制御可能な回転音に物体をのせ、回転台を回転させながら物体を撮影することでテンプレートが得られる。後者は、ズームカメラのズームパラメータを変え、あるいはカメラと物体の距離を変えて物休を撮影することで所望のテンプレートが得られる。また、得られた画像をコンピュータグラフィックス処理により拡大縮小しても得られる。
【００６８】
サブテンプレート生成部１０２は、マルチテンプレート入力部1で得られた、すべてのテンプレートＴからその内部のサブテンプレートＴsubを生成する(Ｓ１１２）。図１３（ｂ）に示されるように、仮に、テンプレートの大きさより(m,n)だけ小さいサブテンプレートを考える。テンプレートの左上を原点として、位置(k,l)のサブテンプレートをＴsub（k,j）と表現する。このとき、図１５に示されるように重なりを許した多数のサブテンプレートＴsub（k,j）…Ｔsub（ｍ−ｌ，ｎ−ｌ）が得られる。その総数はテンプレートあたりｍ×ｎである。これらのすべてのサブテンプレートを、リファレンスサブテンプレート決定部１０３に送出する。
【００６９】
リファレンスサブテンプレート決定部１０３は、サブテンプレート生成部１０２で生成された多数のサブテンプレートから、テンプレート毎にリファレンスサブテンプレートＴsub（ｉ,j）を決定する(図１３（ｃ）およびＳ１１３)。このとき、左上端あるいは、右下端のサブテンプレートを用いる。また、１つのテンプレートを、多数の入力画像から探索する場合には、効果的に高速化を実現するために、自己距離値計算部１０５におけるグループ内の全サブテンプレート間距離値の最大値が、最小となるようなサブテンプレートをリファレンスサブテンプレートとして選択することもできる。ここで生成されたリファレンスサブテンプレートの集合をＱとする。
【００７０】
マルチテンプレートグループ化部１０４は、マルチテンプレート入力部１０１で系統的に生成された多数のテンプレートを、角度、あるいはスケールの類似性によりグループ化し、自己距離値計算部１０５に送出する（Ｓ１１４）。本発明実施形態では、テンプレートごとに、そのテンプレートＴに類似するテンプレートT'を集合させたグループのテンプレート数は最大Ｎ枚とした。ここで、グループ数はマルチテンプレートの数だけ存在する(図１４（ａ）)。
自己距離計算部１０５は、リファレンスサブテンプレート決定部１０４から受理したリファレンスサブテンプレートと、グループ内における他のサブテンプレートの距離を計算する(図１４（ｂ）、およびＳ１１５)。ここでは、距離尺度に絶対値距離、２乗距離などが利用でき、類似尺度として、上記した正規化相互相関値も用いることができる。以下の例では、以下の式（８）で示される絶対値距離を用いる。
【００７１】
【数８】
2006031392.tif 000010
【００７２】
リファレンスサブテンプレート部１０４から受理したリファレンスサブテンプレートＴsub（ｉ,j）とグループ内のすべてのサブテンプレートＴsub（ｋ,ｌ）間の距離ｄ（Ｔsub（ｉ,j）,Ｔsub（ｋ,ｌ））をテンプレートに跨って計算する。さらにその距離ｄ（Ｔsub（ｉ,j）,Ｔsub（ｋ,ｌ））と、距離ｄ（Ｔsub（ｉ,j）,Ｔsub（ｋ,ｌ））の最大値を局所領域枝刈部１１５に送出する（Ｓ１１５）。
入力信号取込み部１０６は、さまざまな画像フォーマットのいずれかで与えられた２次元画像ファイル、あるいはさまざまなフォーマットのうちのいずれかで与えられた動画ファイルから切り出された1フレームの画像の一部または全部、リアルタイムでキャプチャされる1フレームの画像に一部または全部を受理し、得られた画素値のベクトルＷを、局所領域設定部１０７に送出する（Ｓ１１６）。局所領域設定部１０７は、入力信号取込み部１０６から受理した入力画像中の照合すべき全ての局所領域の集合を作成し、局所領域順序設定部１０８に送出する（Ｓ１１７）。局所領域の大きさは、テンプレートと同じ大きさである。入力画像Ｗ上の、座標(u,v)に位置する、テンプレートと同じ大きさの局所領域をＷ(u,v)と表記する。ここでは、局所領域の集合をＷ＝｛S(u,v)|u,v}としたとき、Ｗ中のすべてのＷ(u,v)に対して距離下限値bound (u,v)を導入し、距離ｄ（Ｔ,Ｗ(u,v)）が最小になる位置Ｗ(u,v)を見つける。全ての(u,v)に対するbound (u,v)の初期値は実装において適宜設定されるものであるが、以下、一例として、bound(u,v)=0として説明する。
【００７３】
局所領域順序設定部１０８は、Ｗに合まれる局所領域の順序(入力画像上をスキヤンする順序)を設定する（Ｓ１１８）。例えば、リファレンスサブテンプレート生成部１０２でテンプレートの最も左上の領域Ｔsub（ｉ,j）をリファレンスサブテンプレートとして取り出し照合をおこなう場合には、「右下から左上へ」の順の走査である。逆にテンプレートの最も右下の領域Ｔsub（ｉ,j）_（ｋ,ｌ）をリファレンスサブテンプレートに使って照合する場合には、「左上から右下へ」の順の走査になる。これは左上のテンプレートの場合には、左方向上方向へずらした局所領域の省略を可能にでき、右下のサブテンプレートの場合には、右方向下方向へずらした局所領域の省略を可能にするからである。逆に走査した場合には探索省略の効果はみられない。
【００７４】
一方、高速化のため、中央付近のリファレンスサブテンプレートを使って照合する場合には、適当な間隔を空けるように並び替えを行った局所領域を順に選んだ方が効果的である。この方法には、距離値の分布に基づいた適当な間隔を持つように並び替えを随時行う方法や、入力信号を再帰的に分割したピラミッド画像の中心の位置を大きな画像から順に並べたものを局所領域候補順序に用いた方法、連続的な局所領域候補順序(左上から右下など)を、２進数表現し、最上位の1より下位の値をビット反転し、小さい順または大きい順に並べ直す方法などがある。
【００７５】
リファレンスサブテンプレート選択部１０９は、リファレンスサブテンプレート決定部１０３で決定されたリファレンスサブテンプレートの集合Ｑから順にリファレンスサブテンプレートＴsub（ｉ,j）を取り出し、候補局所領域選択部１１０に送出する（Ｓ１１９）。集合Ｑに含まれるリファレンスサブテンプレートがなくなった場合には探索を終了する。
候補局所領域選択部１１０は、リファレンスサブテンプレート選択部１０９からリファレンスサブテンプレートＴsub（ｉ,j）を受理すると、局所領域の集合ＷからテンプレートＴに類似した信号が含まれる可能性のある候補局所領域Ｗ（u,v）を、局所領域順序設定部１０９で設定された順に選び出し、距離下限値評価部１１１へ送出する。Ｗに含まれる局所領域がなくなった場合には、リファレンスサブテンプレート選択部１０９による選択処理を再度実行する。
【００７６】
距離下限値評価部１１１は、候補局所領域選択部１１０で取り出されたＷ（u,v）について、距離下限値bound(u,v)と閾値ｄminとを比較する（Ｓ１２１）。このとき、bound(u,v)＞ｄminとなる場合、つまり、距離下限値が閾値より大きい場合、候補局所領域選択部１１０による候補局所領域選択を再度実行する。また、比較の結果、bound(u,v)≦ｄminとなる場合、距離下限値評価部１１１は、この候補局所領域Ｗ（u,v）にテンプレートＴに類似した信号が含まれる可能性があることから、位置(u,v)を部分距離値計算部１１２へ送出する。
【００７７】
部分距離値計算部１１２は、リファレンスサブテンプレート選択部１０９から受理したリファレンスサブテンプレートＴsub（ｉ,j）と、候補局所領域選択部１１０で取り出されたＷ（u,v）と同じ位置、サイズの一部の領域Ｗsub（u,v）(ここでは部分局所領域という)との間で、距離ｄ（Ｔsub（ｉ,j）,Ｗsub（u,v））を計算する（Ｓ１２２）。
この距離計算過程において、距離値計算が終了した画集が単調増加するため、距離鎧も同様に単調に増加する。そこで、部分距離値計算部１１２は、この計算の途中で、逐次的に距離値が閾値を越えるかどうかを評価し、計算を打ち切るか否か判定する。このように構成することで、不要な距離計算を省略するＳＳＤＡ法を用いることができる。ここで、閾値として、ｄmin＋ｄmaxを用いる。距離値がｄmin＋ｄmaxを越えた場合、この部分候補局所領域Ｗsub（u,v）および周辺の部分候補局所領域には目的の物体が含まれないことから、計算を打ち切る。また、すべての距離計算が終了後、その距離値がｄminを越えた場合、同様に、この候補局所領域Ｗ（u,v）には目的の物体が含まれない。
【００７８】
距離値がｄmin以上の場合、部分距離値計算部１１２は、Ｗ（u,v）周辺領域に物体が含まれるか否かを調べるために、その距離値ｄを局所領域枝刈部１１５に送出する。
一方、全ての距離計算が終了後、その距離値がｄmin以下の場合、目的の物体である可能性があるため、部分距離値計算部１１２は、その距離値ｄを追加距離値計算部１１３へ送出する。追加距離値計算部１１３は、部分距離値計算部１１２で計算した領域の距離値に、テンプレートの残りの部分と、局所領域の残りの部分との間の距離を加えることによって、テンプレートと局所領域間の距離を求める。
【００７９】
ここで、テンプレート上の領域がＴで、リファレンスサブテンプレートＴsub（ｉ,j）に含まれない領域が~Ｔsub（ｉ,j）であるなら、テンプレートからリファレンスサブテンプレートの領域を差し引いた領域はＴ∩~Ｔsub（ｉ,j）である。同様に、局所領域Ｗ（ｕ,ｖ）から部分局所領域Ｗsub（ｕ,ｖ）を差し引いた領域はＷ（ｕ,ｖ）∩~Ｗsub（ｕ,ｖ）である。
つまり、部分距離計算部１１２で得られた部分距離値ｄ（Ｔsub（ｉ,j）,Ｗsub（u,v））に、これらの間の距離ｄ（Ｔ∩~Ｔsub（ｉ,j）,Ｗ（ｕ,ｖ）∩~Ｗsub（ｕ,ｖ）を加えることで、テンプレートと候補局所領域の距離ｄ（Ｔ, Ｗ（ｕ,ｖ））が得られる。このため、テンプレートと候補局所領域の距離ｄ（Ｔ, Ｗ（ｕ,ｖ））は、以下の式（９）によって示される。
【００８０】
【数９】
2006031392.tif 000011
【００８１】
このとき、部分距離値計算部１１２と同様にＳＳＤＡ法を用いる。そして、逐次的に距離値を計算した結果、途中でｄminを越えた場合、目的の物体ではないことから、追加距離値計算部１１３は、距離値計算を中断し、候補局所領域選択部１１０において次の候補局所領域を選択する。一方、最後の画素まで計算して、テンプレートの距離と、局所領域間の距離ｄがｄminを越えないとき、追加距離値計算部１１３は、距離ｄを検出結果更新部１１４に送出する。
検出結果更新部１１４は、追加距離値計算部１１３から得た距離値ｄにより最小値ｄminを更新し（ｄmin＝dとなる）、その位置（u,v）を記録する（Ｓ１２４）。そして、集合Ｗが空集合でなければ、候補局所領域選択部１１０による候補局所領域選択処理を実行し、次の候補局所領域を選択する。
【００８２】
局所領域枝刈部１１５は、リファレンスサブテンプレートと、局所領域の一部との距離関係から、テンプレートと周囲の局所領域の距離下限値bound(u,v)の更新処理を実行する。大きな距離下限値bound(u,v)が得られた局所領域では、距離下限値評価部１１１に、bound(u,v)＞ｄminが成立する局所領域においては、その局所領域での照合が省略できる。したがって、精度を犠牲にすることなく探索を高速化できる。
【００８３】
自己距離値計算部１０５で得られた、リファレンステンプレートと類似したテンプレートのサブテンプレートの自己距離値により、リファレンスサブテンプレートと局所領域の部分領域の距離計算を行った場合には、他のテンプレートにまたがって距離下限値の計算を行うことができる。以下にその原理を示す。
ＳＳＤＡ法を適用する距離値は、局所領域の画素およびサブテンプレートの画素毎の距離を逐次的に加算して得られる。すなわち、比較する画素が増えると、その距離値も単調に増加する。このため、図１５で示されるようなリファレンスサブテンプレートＴsub（ｉ,j）と、リファレンスサブテンプレートと同じ大きさの局所領域の一部Ｗsub（ｕ,ｖ）との距離ｄ（Ｔsub（ｉ,j）,Ｗsub（ｕ,ｖ））と、テンプレートと局所領域の距離ｄ（Ｔ,Ｗ（ｕ,ｖ））との間に以下の式（１０）が成り立つ。
【００８４】
【数１０】
2006031392.tif 000012
【００８５】
すなわち、リファレンスサブテンプレートでの照合の結果不一致の場合、テンプレート全体で照合しても不一致である。さらにリファレンスサブテンプレートＴsub（ｉ,j）と、同じグループ内の他のサブテンプレートＴ’sub（ｉ,j）、更にＷsub（ｕ,ｖ）に関して三角不等式の原理を適用すると、以下の式（１１）で示される関係が成り立つ。
【００８６】
【数１１】
2006031392.tif 000013
【００８７】
リファレンスサブテンプレートＴsub（ｉ,j）と、部分候補局所領域Ｗsub（ｕ,ｖ）との照合結果を用いて、他のテンプレートＴ'で照合するときの距離下限値も同様に計算することができる。例えば、以下の式（１２）で示される。
【００８８】
【数１２】
2006031392.tif 000014
【００８９】
以上の原理に基づき、u-m < x <= u、v-n＜y<=vを満たす(x,y)に関して下限値bound(x,y)を更新する。更新は以下の式（１３）で示すことができる。
【００９０】
【数１３】
2006031392.tif 000015
【００９１】
上記した本発明実施形態が従来手法に比べてどの程度高速であるかの評価を行った結果を以下に説明する。
ここでは、マージンm=n、同時に処理を行うテンプレート数Ｎを変化させたときの探索時間を測定し、他の手法と比較した。実験は、回転角のみを変化させたテンプレート、スケールのみを変化させたテンプレートの２種類に分けて行った。実験にはＣＰＵとしてIntel社製のXEON CPU (2.2GHz)、3GBメモリ、ＯＳとして、Microsoft社製のWindows XP（登録商標） Professional(SP1)の計算機を用い、ソフトにMATLABを使用した。
【００９２】
前者の「回転角を変化させたテンプレートによる探索」では、対象物体を１０度おきに撮影した３６枚のテンプレートを用いた。また、テンプレートのサイズは４８×４８画素、入力画像のサイは３２０×３２０画素とした。閾値は１度おきに撮影した３６０枚の入力画像からテンプレートと角度が異なる３２４枚を使用して探索を行い、Precision=Recall=１００％となる閾値を測定して求めた値1×１０５に設定した。
上記したＮとｍを変化させて本発明を適用したときの探索時間（物体は図１７（ｄ）に示す「fuku」とした)について図１８にグラフ表示した。
マージンに関しては、ｍが１３付近で探索時間が最短となり、同時に処理を行うテンプレート数に関しては、Ｎが３あたりまで探索時間が急激に減少し、以後ほぼ変化がないことがわかる。また、探索時間が最短となるＮ＝１１において、ｍを変化させたときの探索時間を図１９に示す。図１９によれば、ｍが増加すると探索時間は急激に減少し、９[pixel]から１３[pixel]付近で最短となって、その後増加する。マージンを大きくとると、１回の照合で省略可能な領域が増大するもののサブリファレンス間の距離が大きくなり照合省略の可能性が減少する。単純な物体ほどｍを大きくとることで探索時間が減少している。
【００９３】
同様に、図１８に示す例より探索時間が最短となるｍ＝１３においてＮを変化させたときの探索時間を図２０に示す。
図２０によれば、探索時間はＮ＝４付近まで急激に減少し、以後変化が少ない。各物体とも同じ減少傾向を示しているが、高周波成分を含む画像ほど探索時間が最短となるＮが減少している様子が確認できる。
【００９４】
比較のため、ＳＴＭ、ＳＳＤＡ、部分空間法，テンプレート照合法による探索時間を測定した。ＳＴＭおよびＳＳＤＡは上記した閾値を用いた。また、部分空間法はPrecision=Recall=100%となる最小の次元数で探索時間を測定した。その結果を図２４（ａ）に＜表１＞として示してある。いずれも探索時間が最短となったときの時間である。本発明方法によれば、ＳＴＭ法に比べ約２．７倍、部分空開法に比べ７倍の速度で探索を終えていることがわかる。
【００９５】
後者の「スケールを変化させたテンプレートによる探索」について説明する。ここでは、撮影画像から切り抜いた４８×８３ピクセルの画像を（１５／１６）ｋに縮小したものをテンプレートして用いた。但し、k=1、‥・,14。また、入力画像には３２０×２４０の撮影画像を縦横７０％に縮小したものを用いる。また、閾値は、Precision=Recall=100%となる閾値を測定して１ピクセルあたり３０になるように設定した。
【００９６】
物体を「fuku」とし、その結果が図２１にグラフ表示されている。図２１によれば、マージンに関しては、ｍが９付近で探索時間が最短となり、同時に処理を行うテンプレート数に関しては、Ｎが３あたりまで探索時間が急激に減少し、以後、緩やかに増加していることがわかる。図２１から探索時間が最短となるＮ＝３においてｍを変化させたときの各物体の探索時間について図２２に示す。図２２から、ｍが７から９付近で各物体とも探索時間が最短となっていることがわかる。
同様に、探索時間が最短となるｍ＝９付近においてＮを変化させたときの各物体の探索時間を図２３に示す。図２３によれば、各物体ともＮ＝３付近で探索時間が最短となり、その後暖やかに増加している。
【００９７】
更に、他の手法との比較のため、ＳＴＭ、ＳＳＤＡ、テンプレートマッテング法による探索時間を測定した。ここでは、ＳＴＭおよびＳＳＤＡは上記した閾値を用いた。その結果を、図２４（ｂ）に＜表２＞として示している。いずれも探索時間が最短となったときの時間である。＜表２＞によれば、ＳＴＭ法に比べ約２倍、ＳＳＤＡ法に比べ２０倍の速度で探索を終えていることがわかる。
【００９８】
以上説明のように本発明実施形態によれば、回転角、スケールを変化させた多数のテンプレートを用いて３次元物体を高速に探索できるようにテンプレート照合方法を拡張することができる。具体的に、複数のテンプレートを纏めて探索可能となり、またサイズの異なるテンプレートを纏めて扱えるようになる。このことにより、回転する物体に対して実験を行った結果、従来のＳＴＭ法と比べ約２．７倍、部分空開法に比べ約７倍の高速化を実現できる。また、撮影サイズが変化する物体に対してＳＴＭ法と比べ約２倍、ＳＳＤＡ法と比べ約２０倍の高速化を実現することができる。
この結果、本発明を画像に適用した場合には人物や物体などのコンテンツの検索、動画像中からの移動物体の追跡、ステレオ照合における対応点検出などに役立つ。また、音・映像情報に対して適用した場合には、ＣＭや希望シーンの検索などの高精度化、高速化に役立つ。
【図面の簡単な説明】
【００９９】
【図１】本発明の一実施形態を示すブロック構成図である。
【図２】本発明一実施形態の動作を説明するために引用したフローチャートである。
【図３】本発明実施形態に係わるテンプレートの一例である。
【図４】本発明実施形態に係わる入力信号の一例である。
【図５】入力信号中からテンプレートと類似する領域を検出した結果の一例を示す図である。
【図６】テンプレート内に含まれる段階的サブテンプレートの一例を示す図である。
【図７】本発明の一実施形態の動作を説明するために引用した動作概念図である。
【図８】サブテンプレートのサイズを変化させたときの探索時間の変化を示した実験結果をグラフ表示した図である。
【図９】閾値を変えたときの従来手法と本発明の探索時間の変化を示した実験結果を表す図である。
【図１０】本発明の他の実施形態を示すブロック構成図である。
【図１１】本発明の他の実施形態の動作を説明するために引用したフローチャートである。
【図１２】本発明の他の実施形態において探索される物体の一例を示す図である。
【図１３】図１０に示す構成の一部とテンプレートとの関係を説明するために引用した図である。
【図１４】図１０に示す構成の一部とテンプレートとの関係を説明するために引用した図である。
【図１５】テンプレート内に含まれるサブテンプレートの一例を示す図である。
【図１６】本発明の他の実施形態における動作を説明するために引用した動作概念図である。
【図１７】本発明の他の実施形態において探索する３次元物体の一例を示す図である。
【図１８】図１７に示す回転物体(fuku)の探索時間を説明するために引用したグラフである。
【図１９】探索時間のマージン依存性と回転物体との関係をグラフ表示した図である。
【図２０】探索時間のグループサイズ(Ｎ)依存性と回転物体との関係をグラフ表示した図である。
【図２１】図１７に示すサイズ変化物体(fuku)の探索時間を説明するために引用したグラフである。
【図２２】探索時間のマージンサイズ依存性とサイズ変化物体との関係をグラフ表示した図である。
【図２３】探索時間のグループサイズ(Ｎ)依存性とサイズ変化物体との関係をグラフ表示した図である。
【図２４】探索時間に関し、本発明実施形態と従来例との対比を表形式で示した図である。
【符号の説明】
【０１００】
１…テンプレート入力部、２…サブテンプレート生成部、３…段階的サブテンプレート生成部、４…自己距離値計算部、５…入力信号取込み部、６…局所領域設定部、７…局所領域順序設定部、８…候補局所領域選択部、９…サブテンプレート選択部、１０…部分距離値計算部、１１…追加距離値計算部、１２…検出結果更新部、１３…候補局所領域枝刈部、１０１…マルチテンプレート入力部、１０２…サブテンプレート生成部、１０３…リファレンスサブテンプレート決定部、１０４…マルチテンプレートグループ化部、１０５…自己距離値計算部、１０６…入力信号取込み部、１０７…局所領域設定部、１０８…局所領域順序設定部、１０９…リファレンスサブテンプレート選択部、１１０…候補局所領域選択部、１１１…距離下限値評価部、１１２…部分距離値計算部、１１３…追加距離値計算部、１１４…検出結果更新部、１１５…候補局所領域枝刈部
【図１】
2006031392.tif 000016
【図２】
2006031392.tif 000017
【図３】
2006031392.tif 000018
【図４】
2006031392.tif 000019
【図５】
2006031392.tif 000020
【図６】
2006031392.tif 000021
【図７】
2006031392.tif 000022
【図８】
2006031392.tif 000023
【図９】
2006031392.tif 000024
【図１０】
2006031392.tif 000025
【図１１】
2006031392.tif 000026
【図１２】
2006031392.tif 000027
【図１３】
2006031392.tif 000028
【図１４】
2006031392.tif 000029
【図１５】
2006031392.tif 000030
【図１６】
2006031392.tif 000031
【図１７】
2006031392.tif 000032
【図１８】
2006031392.tif 000033
【図１９】
2006031392.tif 000034
【図２０】
2006031392.tif 000035
【図２１】
2006031392.tif 000036
【図２２】
2006031392.tif 000037
【図２３】
2006031392.tif 000038
【図２４】
2006031392.tif 000039