(57)【要約】【課題】  ヒストグラムを用いる方法と同程度の照合精度を保証しながら、テンプレートとある局所領域での照合結果を利用して、テンプレートとその近傍の局所領域との照合を極力省略し、高速処理するテンプレートマッチング方法、装置、プログラム及びその記録媒体を提供する。【解決手段】  入力信号から取り出す候補局所領域とテンプレートとの距離下限値と、閾値とを比較して、閾値以上であれば、次に照合すべき候補局所領域を選択する。  部分距離値が閾値以下であれば、さらに、他のテンプレートの領域と他の局所領域との距離値をさらに加算し、閾値以下であれば、閾値を更新する。  また、自己距離値と、部分距離値又はテンプレートと局所領域とから計算される距離値とを比較し、距離下限値を更新する。【選択図】  図４
2005063206.tif 000002
【特許請求の範囲】
【請求項１】
入力信号からテンプレートと対応する局所領域を検索するテンプレートマッチング方法であって、
前記テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択し、
前記入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、前記候補局所領域の一部である部分局所領域と前記テンプレートとの距離下限値と閾値とを比較して、前記閾値以上であれば、次に照合すべき候補局所領域を選択し、
前記選択した１のサブテンプレートと前記候補局所領域における部分局所領域とから計算される部分距離値が前記閾値以下であれば、前記テンプレートにおける１のサブテンプレート以外の領域と前記候補局所領域における部分局所領域以外の領域との距離値をさらに加算し、前記テンプレートと前記候補局所領域とから計算される距離値が前記閾値以下であれば、最も類似する領域として当該位置を記録するとともに、前記閾値を更新し、
前記テンプレートから取り出した複数のサブテンプレートと前記１のサブテンプレートとから計算される自己距離値と、前記部分距離値又は前記テンプレートと前記候補局所領域とから計算される距離値とを比較し、候補局所領域周辺の局所領域の前記距離下限値を更新する
ことを特徴とするテンプレートマッチング方法。
【請求項２】
前記部分距離値計算途中において、又は、前記テンプレートと前記局所領域とからの距離値計算途中において、前記距離値が所定の閾値を超えたか否かを逐次的に評価し、前記閾値を超えた場合、距離値計算を打ち切る
ことを特徴とする請求項１に記載のテンプレートマッチング方法。
【請求項３】
前記１のサブテンプレートは、他の複数のサブテンプレートとの距離の最大値が最小になるように選択される
ことを特徴とする請求項１又は請求項２に記載のテンプレートマッチング方法。
【請求項４】
前記複数の候補局所領域を取り出す順序を並び替える
ことを特徴とする請求項１又は請求項２に記載のテンプレートマッチング方法。
【請求項５】
前記部分距離値又は前記テンプレートと前記局所領域とから計算される距離値の分布に基づいて、前記複数の候補局所領域を取り出す順序を並び替える
ことを特徴とする請求項１又は請求項２に記載のテンプレートマッチング方法。
【請求項６】
前記入力信号は再帰的にピラミッド画像に分割され、前記ピラミッド画像の中心の位置を大きなものから順に前記複数の候補局所領域を取り出す順序に用いる
ことを特徴とする請求項１又は請求項２に記載のテンプレートマッチング方法。
【請求項７】
前記複数の候補局所領域を取り出す順序を２進数表現して、最上位の１より下位の値をビット反転し、小さい順または大きい順に前記複数の候補局所領域を取り出す順序を並び替える
ことを特徴とする請求項１又は請求項２に記載のテンプレートマッチング方法。
【請求項８】
前記入力信号又は前記テンプレートが、１次元の音信号、１次元の映像信号、又は、２次元の画像信号のいずれかの信号である
ことを特徴とする請求項１から請求項７のいずれかの項に記載のテンプレートマッチング方法。
【請求項９】
入力信号からテンプレートと対応する局所領域を検索するテンプレートマッチング装置であって、
前記テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択するサブテンプレート選択手段と、
前記テンプレートから取り出した複数のサブテンプレートと、前記サブテンプレート選択手段が選択した１のサブテンプレートとの自己距離値を計算する自己距離値計算手段と、
前記入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、前記候補局所領域の一部である部分局所領域と前記テンプレートとの距離下限値と閾値とを比較して、前記閾値以上であれば、次に照合すべき候補局所領域を選択する候補局所領域選択手段と、
前記候補局所領域選択手段が選択した候補局所領域における部分局所領域と、前記サブテンプレート選択手段が選択した１のサブテンプレートとの部分距離値を計算する部分距離値計算手段と、
前記部分距離値計算手段が計算した部分距離値が前記閾値以下であれば、前記テンプレートにおける前記サブテンプレート選択手段が選択した１のサブテンプレート以外の領域と、前記取り出した局所領域における候補局所領域選択手段が選択した前記候補局所領域における部分局所領域以外の領域との距離値をさらに加算して、前記テンプレートと前記候補局所領域との距離値を計算する追加距離値計算手段と、
前記追加距離値計算手段が計算した距離値が前記閾値以下であれば、最も類似する領域として当該位置を記録するとともに、前記閾値を更新する検出結果更新手段と、
前記自己距離値計算手段が計算した自己距離値と、前記部分距離値計算手段が計算した距離値又は前記追加距離値計算手段が計算した距離値とを比較し、前記距離下限値を更新する局所領域枝刈手段と
を備えることを特徴とするテンプレートマッチング装置。
【請求項１０】
前記部分距離値計算手段、又は、前記追加距離値計算手段は、計算途中の距離値が所定の閾値を超えたか否かを逐次的評価し、前記閾値を超えた場合、距離値計算を打ち切る
ことを特徴とする請求項９に記載のテンプレートマッチング装置。
【請求項１１】
前記サブテンプレート選択手段は、他の複数のサブテンプレートとの距離の最大値が最小になるように、前記１のサブテンプレートを選択する
ことを特徴とする請求項９又は請求項１０に記載のテンプレートマッチング装置。
【請求項１２】
前記複数の候補局所領域を取り出す順序を並び替える局所領域順序設定手段
をさらに具備することを特徴とする請求項９又は請求項１０に記載のテンプレートマッチング装置。
【請求項１３】
前記候補局所領域順序変更手段は、前記部分距離値計算手段が計算した距離値又は前記追加距離値計算手段が計算した距離値の分布に基づいて、前記複数の候補局所領域を取り出す順序を並び替える
ことを特徴とする請求項９又は請求項１０に記載のテンプレートマッチング装置。
【請求項１４】
前記候補局所領域順序変更手段は、入力信号を再帰的に分割したピラミッド画像の中心の位置を大きな画像から順に並び替える
ことを特徴とする請求項９又は請求項１０に記載のテンプレートマッチング装置。
【請求項１５】
前記候補局所領域順序変更手段は、前記複数の候補局所領域を取り出す順序を２進数表現して、最上位の１より下位の値をビット反転し、小さい順または大きい順に並び替える
ことを特徴とする請求項９又は請求項１０に記載のテンプレートマッチング装置。
【請求項１６】
前記入力信号又は前記テンプレートが、１次元の音信号、１次元の映像信号、又は、２次元の画像信号のいずれかの信号である
ことを特徴とする請求項９から請求項１６のいずれかの項に記載のテンプレートマッチング装置。
【請求項１７】
入力信号からテンプレートと対応する局所領域を検索する処理をコンピュータに実行させるためのプログラムであって、
前記テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択する処理と、
前記入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、前記候補局所領域の一部である部分局所領域と前記テンプレートとの距離下限値と閾値とを比較して、前記閾値以上であれば、次に照合すべき候補局所領域を選択する処理と、
前記選択した１のサブテンプレートと前記候補局所領域における部分局所領域とから計算される部分距離値が前記閾値以下であれば、前記テンプレートにおける１のサブテンプレート以外の領域と前記候補局所領域における部分局所領域以外の領域との距離値をさらに加算し、前記テンプレートと前記候補局所領域とから計算される距離値が前記閾値以下であれば、最も類似する領域として当該位置を記録するとともに、前記閾値を更新する処理と、
前記テンプレートから取り出した複数のサブテンプレートと前記１のサブテンプレートとから計算される自己距離値と、前記部分距離値又は前記テンプレートと前記候補局所領域とから計算される距離値とを比較し、候補局所領域周辺の局所領域の前記距離下限値を更新する処理と
をコンピュータに実行させるためのテンプレートマッチングプログラム。
【請求項１８】
入力信号からテンプレートと対応する局所領域を検索する処理をコンピュータに実行させるためのプログラムを記録した記録媒体であって、
前記テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択する処理と、
前記入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、前記候補局所領域の一部である部分局所領域と前記テンプレートとの距離下限値と閾値とを比較して、前記閾値以上であれば、次に照合すべき候補局所領域を選択する処理と、
前記選択した１のサブテンプレートと前記候補局所領域における部分局所領域とから計算される部分距離値が前記閾値以下であれば、前記テンプレートにおける１のサブテンプレート以外の領域と前記候補局所領域における部分局所領域以外の領域との距離値をさらに加算し、前記テンプレートと前記候補局所領域とから計算される距離値が前記閾値以下であれば、最も類似する領域として当該位置を記録するとともに、前記閾値を更新する処理と、
前記テンプレートから取り出した複数のサブテンプレートと前記１のサブテンプレートとから計算される自己距離値と、前記部分距離値又は前記テンプレートと前記候補局所領域とから計算される距離値とを比較し、候補局所領域周辺の局所領域の前記距離下限値を更新する処理と
をコンピュータに実行させるためのテンプレートマッチングプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テンプレートとして与えられた既知の信号と類似する信号を、大量の信号系列から検出し、その位置を求めるテンプレートマッチング方法、装置、プログラム及びその記録媒体に関する。
【背景技術】
【０００２】
従来、一般に膨大な信号中から、既知の目的信号を検出する技術にテンプレートマッチング法が知られている。
しかし、テンプレートマッチング法では、既知の目的信号のパターン（テンプレート）と、入力信号上の多数の局所領域とを照合して目的信号の場所を求めるため、膨大な照合時間が必要になる。
その高速化手法に、２段階テンプレートマッチング法（非特許文献１参照）やＳＳＤＡ法（Sequential Similarity Ｄetection Algorithm、非特許文献２参照）がある。
しかし、これらの手法でもテンプレートと全ての局所領域で照合を行うため、計算時間が大きい。
一方、出願人が、これまで開発してきた画像に適用したアクティブ探索法（特許文献１参照）、及び、音・映像に適用したアクティブ探索法（特許文献２参照）は、テンプレートと、ある局所領域との照合結果を利用して、テンプレートとその近傍の局所領域との類似値の上限値を計算し、上限値が閾値を下回る場合にテンプレートと、その近傍局所領域との照合を省略するため、きわめて高速に探索できる。
【特許文献１】特開平９−３３０４０４号公報
【特許文献２】特開２０００−３１２３４３号公報
【非特許文献１】G.J.Vanderbrug et.al.，“Two stage template matching"，                IEEE Trans.on Computers， Vol.C-26， N0.4， pp.384-393，1977.
【非特許文献２】Ｄ.I.Barnea et.al.，"A class of Algorithms  for fast digital image Registration"， IEEE Trans. On Computers，Vol.C-21，No.2， pp. 179-186， 1972.
【非特許文献３】足立他：正規化相互相関テンプレートマッチングのKL展開を用いたＳＳＤＡ化¨，信学技報PＲMU96-173， pp. 23-30， 1997.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、特許文献１、２に記載されたテンプレートマッチング法では、特徴にヒストグラムを利用するため、形状の情報や色の距離情報が失われ、細かい形・波形の違いが重要になる場合や、明度の変化などを大きく受ける場合などに適用することが難しい。
【０００４】
本発明は、このような事情を考慮してなされたものであり、その目的は、ヒストグラムを用いない場合であっても全照合と同等の照合精度を保証しながら、テンプレートとある局所領域での照合結果を利用して、テンプレートとその近傍の局所領域との照合を極力省略し、ヒストグラムを用いる方法と同程度の高速処理を保証することができるテンプレートマッチング方法、装置、プログラム及びその記録媒体を提供することにある。
【課題を解決するための手段】
【０００５】
この発明は上記の課題を解決すべくなされたもので、本発明は、入力信号からテンプレートと対応する局所領域を検索するテンプレートマッチング方法であって、前記テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択し、前記入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、前記候補局所領域の一部である部分局所領域と前記テンプレートとの距離下限値と閾値とを比較して、前記閾値以上であれば、次に照合すべき候補局所領域を選択し、前記選択した１のサブテンプレートと前記候補局所領域における部分局所領域とから計算される部分距離値が前記閾値以下であれば、前記テンプレートにおける１のサブテンプレート以外の領域と前記候補局所領域における部分局所領域以外の領域との距離値をさらに加算し、前記テンプレートと前記候補局所領域とから計算される距離値が前記閾値以下であれば、最も類似する領域として当該位置を記録するとともに、前記閾値を更新し、前記テンプレートから取り出した複数のサブテンプレートと前記１のサブテンプレートとから計算される自己距離値と、前記部分距離値又は前記テンプレートと前記候補局所領域とから計算される距離値とを比較し、候補局所領域周辺の局所領域の前記距離下限値を更新することを特徴とする。
【０００６】
また、本発明は、前記部分距離値計算途中において、又は、前記テンプレートと前記局所領域とからの距離値計算途中において、前記距離値が所定の閾値を超えたか否かを逐次的に評価し、前記閾値を超えた場合、距離値計算を打ち切ることを特徴とする。
【０００７】
また、本発明は、前記１のサブテンプレートは、他の複数のサブテンプレートとの距離の最大値が最小になるように選択されることを特徴とする。
【０００８】
また、本発明は、前記複数の候補局所領域を取り出す順序を並び替えることを特徴とする。
【０００９】
また、本発明は、前記部分距離値又は前記テンプレートと前記局所領域とから計算される距離値の分布に基づいて、前記複数の候補局所領域を取り出す順序を並び替えることを特徴とする。
【００１０】
また、本発明は、前記入力信号は再帰的にピラミッド画像に分割され、前記ピラミッド画像の中心の位置を大きなものから順に前記複数の候補局所領域を取り出す順序に用いることを特徴とする。
【００１１】
また、本発明は、前記複数の候補局所領域を取り出す順序を２進数表現して、最上位の１より下位の値をビット反転し、小さい順または大きい順に前記複数の候補局所領域を取り出す順序を並び替えることを特徴とする。
【００１２】
また、本発明は、前記入力信号又は前記テンプレートが、１次元の音信号、１次元の映像信号、又は、２次元の画像信号のいずれかの信号であることを特徴とする。
【００１３】
また、本発明は、入力信号からテンプレートと対応する局所領域を検索するテンプレートマッチング装置であって、前記テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択するサブテンプレート選択手段と、前記テンプレートから取り出した複数のサブテンプレートと、前記サブテンプレート選択手段が選択した１のサブテンプレートとの自己距離値を計算する自己距離値計算手段と、前記入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、前記候補局所領域の一部である部分局所領域と前記テンプレートとの距離下限値と閾値とを比較して、前記閾値以上であれば、次に照合すべき候補局所領域を選択する候補局所領域選択手段と、前記候補局所領域選択手段が選択した候補局所領域における部分局所領域と、前記サブテンプレート選択手段が選択した１のサブテンプレートとの部分距離値を計算する部分距離値計算手段と、前記部分距離値計算手段が計算した部分距離値が前記閾値以下であれば、前記テンプレートにおける前記サブテンプレート選択手段が選択した１のサブテンプレート以外の領域と、前記取り出した局所領域における候補局所領域選択手段が選択した前記候補局所領域における部分局所領域以外の領域との距離値をさらに加算して、前記テンプレートと前記候補局所領域との距離値を計算する追加距離値計算手段と、前記追加距離値計算手段が計算した距離値が前記閾値以下であれば、最も類似する領域として当該位置を記録するとともに、前記閾値を更新する検出結果更新手段と、前記自己距離値計算手段が計算した自己距離値と、前記部分距離値計算手段が計算した距離値又は前記追加距離値計算手段が計算した距離値とを比較し、前記距離下限値を更新する局所領域枝刈手段とを備えることを特徴とする。
【００１４】
また、本発明は、前記部分距離値計算手段、又は、前記追加距離値計算手段は、計算途中の距離値が所定の閾値を超えたか否かを逐次的評価し、前記閾値を超えた場合、距離値計算を打ち切ることを特徴とする。
【００１５】
また、本発明は、前記サブテンプレート選択手段は、他の複数のサブテンプレートとの距離の最大値が最小になるように、前記１のサブテンプレートを選択することを特徴とする。
【００１６】
また、本発明は、前記複数の候補局所領域を取り出す順序を並び替える局所領域順序設定手段をさらに具備することを特徴とする。
【００１７】
また、本発明は、前記候補局所領域順序変更手段は、前記部分距離値計算手段が計算した距離値又は前記追加距離値計算手段が計算した距離値の分布に基づいて、前記複数の候補局所領域を取り出す順序を並び替えることを特徴とする。
【００１８】
また、本発明は、前記候補局所領域順序変更手段は、入力信号を再帰的に分割したピラミッド画像の中心の位置を大きな画像から順に並び替えることを特徴とする。
【００１９】
また、本発明は、前記候補局所領域順序変更手段は、前記複数の候補局所領域を取り出す順序を２進数表現して、最上位の１より下位の値をビット反転し、小さい順または大きい順に並び替えることを特徴とする。
【００２０】
また、本発明は、前記入力信号又は前記テンプレートが、１次元の音信号、１次元の映像信号、又は、２次元の画像信号のいずれかの信号であることを特徴とする。
【００２１】
また、本発明は、入力信号からテンプレートと対応する局所領域を検索する処理をコンピュータに実行させるためのプログラムであって、前記テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択する処理と、前記入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、前記候補局所領域の一部である部分局所領域と前記テンプレートとの距離下限値と閾値とを比較して、前記閾値以上であれば、次に照合すべき候補局所領域を選択する処理と、前記選択した１のサブテンプレートと前記候補局所領域における部分局所領域とから計算される部分距離値が前記閾値以下であれば、前記テンプレートにおける１のサブテンプレート以外の領域と前記候補局所領域における部分局所領域以外の領域との距離値をさらに加算し、前記テンプレートと前記候補局所領域とから計算される距離値が前記閾値以下であれば、最も類似する領域として当該位置を記録するとともに、前記閾値を更新する処理と、前記テンプレートから取り出した複数のサブテンプレートと前記１のサブテンプレートとから計算される自己距離値と、前記部分距離値又は前記テンプレートと前記候補局所領域とから計算される距離値とを比較し、候補局所領域周辺の局所領域の前記距離下限値を更新する処理とをコンピュータに実行させるためのテンプレートマッチングプログラムである。
【００２２】
また、本発明は、入力信号からテンプレートと対応する局所領域を検索する処理をコンピュータに実行させるためのプログラムを記録した記録媒体であって、前記テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択する処理と、前記入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、前記候補局所領域の一部である部分局所領域と前記テンプレートとの距離下限値と閾値とを比較して、前記閾値以上であれば、次に照合すべき候補局所領域を選択する処理と、前記選択した１のサブテンプレートと前記候補局所領域における部分局所領域とから計算される部分距離値が前記閾値以下であれば、前記テンプレートにおける１のサブテンプレート以外の領域と前記候補局所領域における部分局所領域以外の領域との距離値をさらに加算し、前記テンプレートと前記候補局所領域とから計算される距離値が前記閾値以下であれば、最も類似する領域として当該位置を記録するとともに、前記閾値を更新する処理と、前記テンプレートから取り出した複数のサブテンプレートと前記１のサブテンプレートとから計算される自己距離値と、前記部分距離値又は前記テンプレートと前記候補局所領域とから計算される距離値とを比較し、候補局所領域周辺の局所領域の前記距離下限値を更新する処理とをコンピュータに実行させるためのテンプレートマッチングプログラムを記録した記録媒体である。
【発明の効果】
【００２３】
以上説明したように、本発明によれば、テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択し、入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、候補局所領域の一部である部分局所領域とテンプレートとの距離下限値と閾値とを比較して、閾値以上であれば、次に照合すべき候補局所領域を選択し、選択した１のサブテンプレートと候補局所領域における部分局所領域とから計算される部分距離値が閾値以下であれば、テンプレートにおける１のサブテンプレート以外の領域と候補局所領域における部分局所領域以外の領域との距離値をさらに加算し、テンプレートと候補局所領域とから計算される距離値が閾値以下であれば、最も類似する領域として当該位置を記録するとともに、閾値を更新し、テンプレートから取り出した複数のサブテンプレートと１のサブテンプレートとから計算される自己距離値と、部分距離値又はテンプレートと候補局所領域とから計算される距離値とを比較し、候補局所領域周辺の局所領域の距離下限値を更新する。
このように構成することで、以下のような作用が得られる。
すなわち、２段階テンプレートマッチング法やＳＳＤＡ法に比べて、ある領域を照合した結果、距離下限値が閾値を上回った場合、その領域だけでなく周辺の照合を省略できる。
したがって、照合回数を大幅に削減することが出来、高速に探索できる効果が得られる。
また特徴にヒストグラムを利用するアクティブ探索法に比べて、形状の情報や色の距離情報を含めて照合を行うので、細かい形の違いが重要になる場合や明度の変化などの影響を大きく受ける場合においても高精度の探索を実現することができる効果が得られる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明を実施するための最良の形態について説明する。
【実施例１】
【００２５】
以下、図面を参照して、本発明のテンプレートマッチング装置の一実施形態について説明する。図１は、本実施形態のテンプレートマッチング装置の構成を示す機能ブロック図である。
図１に示すように、本実施形態のテンプレートマッチング装置は、テンプレート入力手段１と、サブテンプレート生成手段２と、サブテンプレート選択手段３と、自己距離値計算手段４と、入力信号入力手段５と、局所領域設定手段６と、局所領域順序設定手段７と、候補局所領域選択手段８と、部分距離値計算手段９と、追加距離値計算手段１０と、検出結果更新手段１１と、局所領域枝刈手段１２とから構成され、これらの手段が有機的に結合することで、目的信号であるテンプレートと、テンプレートの有無の検索対象である入力信号について、テンプレートが含まれているかどうかを判定し、含まれている場合にはその位置と距離値とを出力する。
【００２６】
なお、図１では、各機能ブロックを○○手段と呼んでいるが、○○部もしくは○○装置と読み替えることができるものであって、ソフトウェアないしハードウェアによって全てを構成でき、またソフトウェアとハードウェアの組み合わせによっても実現できるものである。
また、一実施形態として、２次元の画像をテンプレート及び入力信号とした場合の例を図２（ａ）、（ｂ）に示す。
また、図３は、図２に示す入力信号（くま、だるま、招き猫、パイナップル、おじいさんが写った画像信号）からテンプレート（パイナップルが写った画像信号）の有無を判定し、入力信号におけるテンプレートの位置を特定する具体的なイメージを示す。
【００２７】
図２、３に示す例は、テンプレートと入力信号中の一部の領域との間の距離値によって評価する場合を示す。具体的には、テンプレートと入力信号中の一部の領域との間の距離値として、予め適当な閾値を設定しておき、テンプレート探索中に見つけた距離値の最小値ｄminで閾値を更新することによって最も類似するサブテンプレートを高速に発見する。もちろん閾値を更新せず、閾値を下回る全てを記録してその結果を返すようにしてもよい。
また、この例では２次元の例を用いているが、Ｎ個の要素からなる１次元の入力信号を１×Ｎの２次元と考えることで、１次元の信号も全く同様に扱えることは明らかであり、３次元以上の信号にもまったく同じ手法で扱える。また、画像以外にも、音データ、気象データ、地図データ、遺伝子データなどの多次元ベクトル系列にも適用できる。
【００２８】
次に上述の各機能ブロックについて説明する。
テンプレート入力手段１は、テンプレートを入力する。
サブテンプレート生成手段２は、テンプレート入力手段１で得られたテンプレート中から、所定の大きさのサブテンプレートを全て取り出す。
サブテンプレート選択手段３は、テンプレート入力手段１で入力するテンプレートから、サブテンプレート生成手段２が取り出した複数のサブテンプレートより、１のサブテンプレートを選択する。このとき、サブテンプレート選択手段３は、左上端、あるいは、右下端のサブテンプレートを選択する。なお、他の複数のサブテンプレートとの距離の最大値が最小になるように、１のサブテンプレートを選択するようにしてもよい。
自己距離値計算手段４は、サブテンプレート生成手段２で得られた複数（全て）のサブテンプレートと、サブテンプレート選択手段３が選択した１のサブテンプレートとの自己距離値(または類似値)をすべてのサブテンプレートについて計算する。
【００２９】
入力信号入力手段５は、入力信号を入力する。
局所領域設定手段６は、入力信号入力手段５で得られた入力信号上でテンプレートと同じ大きさのあらゆる（ｕ、ｖ）に対する局所領域を設定する（後述する）。
局所領域順序設定手段７は、複数の候補局所領域を取り出す順序を並び替える。このとき、候補局所領域順序変更手段７は、部分距離値計算手段９が計算した距離値又は追加距離値計算手段１０が計算した距離値の分布に基づいて、複数の候補局所領域を取り出す順序を並び替える。また、他の実施形態として、候補局所領域順序変更手段７は、入力信号を再帰的に分割したピラミッド画像の中心の位置を大きな画像から順に並び替える。さらに他の実施形態として、候補局所領域順序変更手段７は、複数の候補局所領域を取り出す順序を２進数表現して、最上位の１より下位の値をビット反転し、小さい順または大きい順に並び替える。
候補局所領域選択手段８は、入力信号入力手段５が入力した入力信号において、局所領域設定手段６が設定した複数の局所領域から順に１の局所領域を取り出して、取り出した候補局所領域の一部である部分局所領域とテンプレートとの距離下限値（類似上限値）と、閾値とを比較して、閾値以上であれば、次に照合すべき候補局所領域を選択する。
部分距離値計算手段９は、候補局所領域選択手段８が選択した候補局所領域における部分局所領域と、サブテンプレート選択手段３が選択した１のサブテンプレートとを照合し、部分距離値を計算する。
【００３０】
追加距離値計算手段１０は、部分距離値計算手段９が計算した部分距離値が閾値以下である場合、つまり、取り出した局所領域の一部である候補局所領域とテンプレートとが、ある程度類似する場合、テンプレートの残りの領域（テンプレートにおけるサブテンプレート選択手段３が選択した１のサブテンプレート以外の領域）と、候補局所領域の残りの領域（候補局所領域選択手段８が選択した候補局所領域以外における部分局所領域の領域）との距離を追加してテンプレート全体と候補領域全体との距離値を求める。
なお、部分距離値計算手段９、又は、追加距離値計算手段１０は、計算途中の距離値が所定の閾値を超えたか否かを逐次的評価し、閾値を超えた場合、距離値計算を打ち切る。
検出結果更新手段１１は、追加距離値計算手段１２が計算した距離値が閾値以下であれば、検出結果や閾値を更新する。
局所領域枝刈手段１２は、自己距離値計算手段４が計算した自己距離値と、部分距離値計算手段９が計算した距離値又は追加距離値計算手段１０が計算した距離値とを比較し、候補局所領域内の近傍の局所領域の距離下限値(または類似値上限値)を更新する、あるいはテンプレートに類似する信号が存在する可能性のない局所領域候補を削除する。
【００３１】
次に、本実施形態のテンプレートマッチング装置の動作について説明する。
図４は、本実施形態のテンプレートマッチング装置におけるテンプレートマッチング処理の過程を示すフローチャートである。
図４に示すように、まずテンプレート入力手段１は、さまざまな画像フォーマットで与えられた２次元画像ファイル、あるいはさまざまなフォーマットで与えられた動画ファイルから切り出された１フレームの画像の一部、リアルタイムでキャプチャされる１フレームの画像の一部から、窓関数などを用いて物体領域を抽出し、サブテンプレート生成手段２に送出する。
例えば物体の窓関数としては、矩形形状でその内側だけを取り出すもの、円形状で円の内側だけを取り出すもの、物体の形状に合わせた形でその内側だけを取り出すものなどの窓関数が上げられる。ここでは矩形形状の例で説明する。
この取り出された信号をテンプレートと呼ぶ。テンプレートは、その画素値（非負整数）を要素とするベクトルで表現される。このテンプレートをＲと表現する。
【００３２】
サブテンプレート生成手段２は、テンプレート入力手段１から受理したテンプレートＲから、その内部のサブテンプレートを生成する。
今、仮にテンプレートの大きさより（ｍ，ｎ）だけ小さいサブテンプレートを考える。
テンプレートの左上を原点（０，０）として、位置（ｉ，ｊ）のサブテンプレート
【００３３】
【数１】
2005063206.tif 000003
【００３４】
と表現する。このとき図５に示すように０≦ｉ≦ｍ，０≦ｊ≦ｎの制約条件も設け、重なりを許した場合、サブテンプレート
【００３５】
【数２】
2005063206.tif 000004
【００３６】
が得られる。その総数はｍ×ｎである。これらのすべてのサブテンプレートを、自己距離計算手段３に送出する。
【００３７】
サブテンプレート選択手段３は、サブテンプレート生成手段２から受理したすべてのサブテンプレート中から１つのサブテンプレートを適当に選択する。たとえば、もっとも左上のサブテンプレートや、もっとも右下のテンプレートを用いる。また、１つのテンプレートを、多数の入力画像から探索する場合には、自己距離計算手段４における全サブテンプレート間距離値の最大値が、最小となるようなサブテンプレートを選択することもできる。
【００３８】
自己距離計算手段４は、サブテンプレート生成手段２から受理した全てのサブテンプレートとサブテンプレート選択手段３で選択したサブテンプレートの距離
【００３９】
【数３】
2005063206.tif 000005
【００４０】
を計算する。本手法の距離尺度には、絶対値距離、２乗距離などが利用でき、類似尺度として正規化相互相関値（非特許文献３参照）も用いることができる。以下の例において、自己距離計算手段４は、絶対値距離
【００４１】
【数４】
2005063206.tif 000006
【００４２】
を用いる。
すなわち、自己距離計算手段４は、サブテンプレート選択手段３から受理したサブテンプレート
【００４３】
【数５】
2005063206.tif 000007
【００４４】
とすべてのサブテンプレート
【００４５】
【数６】
2005063206.tif 000008
【００４６】
間の距離
【００４７】
【数７】
2005063206.tif 000009
【００４８】
を予めすべてについて計算する。次に、自己距離計算手段４は、計算したすべての距離
【００４９】
【数８】
2005063206.tif 000010
【００５０】
とそのすべての距離の中で最大値ｄmaｘとなるものを局所領域枝刈手段１２に送出する（非特許文献３を参照）。
【００５１】
次に、入力信号入力手段５は、さまざまな画像フォーマットのいずれかで与えられた２次元画像ファイル、あるいはさまざまなフォーマットのうちのいずれかで与えられた動画ファイルから切り出された１フレームの画像の一部または全部、リアルタイムでキャプチャされる１フレームの画像に一部または全部を受理し、得られた画素値のベクトルSを、局所領域設定手段６に送出する。
【００５２】
局所領域設定手段６は、入力信号入力手段５から受理した入力画像中の照合すべき全ての局所領域の集合を作成し、局所領域順序設定手段７に送出する。
局所領域の大きさは、テンプレートと同じ大きさである。入力画像S上の座標（u，ｖ）に位置するテンプレートと同じ大きさの局所領域をS（u，ｖ）と表記する。
局所領域の集合Ｗ＝｛S（u，ｖ）｜ｕ，ｖ｝としたとき、テンプレートマッチング法による探索は、Ｗの中から、距離ｄ（Ｒ，S（ｕ，ｖ））が最小になる位置（u，ｖ）を見つける技術である。
ここで、本実施形態のテンプレートマッチング法においては、さらに、局所領域の集合Ｗの中のすべてのS（u，ｖ）に対して、距離下限値ｂｏｕｎｄ（ｕ，ｖ）を導入する。
すべての（ｕ，ｖ）に対するｂｏｕｎｄ（ｕ，ｖ）の初期値は実装において適宜設定されるものであるが、以下、一例として、ｂｏｕｎｄ（ｕ，ｖ）＝０として説明する。
【００５３】
局所領域順序設定手段７は、局所領域設定手段６において作成された局所領域の集合Ｗに含まれる局所領域の順序（入力画像上をスキャンする順序）を設定する。
たとえば最も左上のサブテンプレート
【００５４】
【数９】
2005063206.tif 000011
【００５５】
を使って照合する場合、局所領域順序設定手段７は、「右下から左上へ」の順の走査に設定する。逆に最も右下のサブテンプレート
【００５６】
【数１０】
2005063206.tif 000012
【００５７】
を使って照合する場合、局所領域順序設定手段７は、「左上から右下へ」の順の走査に設定する。これは左上のテンプレートの場合には、左方向上方向へずらした局所領域の省略を可能にでき、右下のサブテンプレートの場合には、右方向下方向へずらした局所領域の省略を可能にするからである。逆に走査した場合には探索省略の効果はみられない。
一方、高速化のため、中央付近のサブテンプレートを使って照合する場合には、適当な間隔をあけるように並び替えを行った局所領域を順に選んだ方が効果的である。
この方法には、距離値の分布に基づいた適当な間隔を持つように並び替えを随時行う方法や、入力信号を再帰的に分割したピラミッド画像の中心の位置を大きな画像から順に並べたものを局所領域候補順序に用いた方法、連続的な局所領域候補順序（左上から右下など）を、２進数表現し、最上位の１より下位の値をビット反転し、小さい順または大きい順に並べ直す方法などがある。
局所領域順序設定手段７は、このように作成した集合Ｗを候補局所領域選択手段８へ送出する。
【００５８】
候補局所領域選択手段８は、局所領域設定手段７から受理した局所領域の集合Ｗからテンプレートがある可能性のある候補局所領域を選び出し、部分距離値計算手段９へ送出する。具体的には、候補局所領域選択手段８は、まず集合Ｗから、設定された順序において先頭の候補局所領域S（ｕ，ｖ）を取り出す。 
取り出した候補局所領域S（ｕ，ｖ）について、候補局所領域選択手段８は、距離下限値ｂｏｕｎｄ（ｕ，ｖ）と閾値ｄminとを比較する。このとき、
ｂｏｕｎｄ（ｕ，ｖ）＞ｄmin
となる場合、つまり、距離下限値が閾値より大きい場合、候補局所領域選択手段８は、次のS（ｕ，ｖ）を取り出して、再度比較処理を実行する。
また、比較の結果、 
ｂｏｕｎｄ（u，ｖ）≦ｄmin
となる場合、候補局所領域選択手段８は、この候補局所領域S（ｕ，ｖ）にテンプレートがある可能性のあることから、位置（u，ｖ）を部分距離値計算手段９へ送出する。
一方、集合Ｗに含まれる局所領域がなくなった場合には探索を終了する。
【００５９】
部分距離値計算手段９は、サブテンプレート選択手段３から受理したサブテンプレート
【００６０】
【数１１】
2005063206.tif 000013
【００６１】
と、候補局所領域選択手段から受理した候補局所領域S（ｕ，v）の
【００６２】
【数１２】
2005063206.tif 000014
【００６３】
と同じ位置・大きさの一部の領域（本明細書ではこれを部分局所領域という）
【００６４】
【数１３】
2005063206.tif 000015
【００６５】
との間で、
【００６６】
【数１４】
2005063206.tif 000016
【００６７】
を計算する。
【００６８】
この距離計算過程において、距離値計算が終了した画素が単調増加するため、距離値も同様に単調に増加する。そこで、部分距離値計算手段９は、この計算途中で、逐次的に距離値が閾値を越えるかどうかを評価し、計算を打ち切るか否かを判定する。
このように構成することで、不要な距離計算を省略するＳＳＤＡ法を用いることができる。ここで、閾値としては、ｄmin＋ｄmaｘを用いる。
距離値がｄmin＋ｄmaｘを越えた場合、部分距離値計算手段９は、この局所領域及び周辺の局所領域には目的の物体が含まれないことから、計算を打ち切る。また、全ての距離計算が終了後、その距離値がｄminを越えた場合、同様に、この局所領域には目的の物体が含まれない。
距離値がｄmin以下の場合、部分距離値計算手段９は、周辺領域に物体が含まれるかどうかをさらに調べるために、その距離値ｄを局所領域枝刈手段１２に送出する。
一方、全ての距離計算が終了後、その距離値がｄminを越えない場合、目的の物体である可能性があるので、部分距離値計算手段９は、その距離値ｄを、追加距離値計算手段１０へ送出する。
【００６９】
追加距離値計算手段１０は、部分距離値計算手段９で計算した領域の距離値に、テンプレートの残りの部分
【００７０】
【数１５】
2005063206.tif 000017
【００７１】
と、局所領域の残りの部分
【００７２】
【数１６】
2005063206.tif 000018
【００７３】
と間の距離
【００７４】
【数１７】
2005063206.tif 000019
【００７５】
を加えることによって、テンプレートと局所領域間の距離ｄ（Ｒ，S（ｕ，ｖ））を求める。
【００７６】
【数１８】
2005063206.tif 000020
【００７７】
このとき、追加距離値計算手段１０は、部分距離値計算手段９と同様にＳＳＤＡ法を用いる。
そして、逐次的に距離値を計算した結果、途中でｄminを越えた場合、目的の物体ではないことから、追加距離値計算手段１０は、距離値計算を中断し、候補局所領域選択手段８において、再度比較処理を実行する。
一方、最後画素まで計算して、テンプレートの距離と、局所領域間の距離ｄがｄminを越えないとき、追加距離値計算手段１０は、距離ｄを検出結果更新手段１１に送出する。
【００７８】
検出結果更新手段１１は、追加距離値計算手段８から得た距離値ｄにより、最小値ｄminを更新し（ｄmin＝ｄとなる）、その位置（u，v）を記録する。
そして、集合Ｗが空集合でなければ、候補局所領域選択手段８において、再度比較処理を実行する。
【００７９】
局所領域枝刈手段１２は、得られたサブテンプレートと、局所領域の一部との距離関係から、テンプレートと周囲の局所領域の距離下限値ｂｏｕｎｄ（ｕ，ｖ）の更新処理を実行する。
大きな距離下限値ｂｏｕｎｄ（ｕ，ｖ）が得られた局所領域では、候補局所領域選択手段８において、
ｂｏｕｎｄ（ｕ，ｖ）＞ｄmin
が成立する局所領域においては、その局所領域での照合が省略できる。したがって、精度を犠牲にすることなく探索を高速化できる。
【００８０】
その原理を以下に示す。
ＳＳＤＡ法を適用する距離値は、局所領域の画素及びサブテンプレートの画素毎の距離を逐次的に加算して得られる。すなわち、比較する画素が増えると、その距離値も単調に増加する。このため、図６で示されるようなサブテンプレート
【００８１】
【数１９】
2005063206.tif 000021
【００８２】
とサブテンプレートと同じ大きさの局所領域の一部（部分局所領域）
【００８３】
【数２０】
2005063206.tif 000022
【００８４】
との距離
【００８５】
【数２１】
2005063206.tif 000023
【００８６】
と、テンプレートと局所領域の距離ｄ（Ｒ，S（ｕ，ｖ））との間に次の関係が成り立つ。
【００８７】
【数２２】
2005063206.tif 000024
【００８８】
すなわち、サプテンプレートでの照合の結果、不―致の場合、テンプレート全休で照合しても不一致である。さらに２つのサブテンプレート
【００８９】
【数２３】
2005063206.tif 000025
【００９０】
と
【００９１】
【数２４】
2005063206.tif 000026
【００９２】
に関して三角不等式の原理を適用すると、以下の関係が成り立つ。
【００９３】
【数２５】
2005063206.tif 000027
【００９４】
以上の原理に基づき、
ｕ＋ｉ−ｍ＜ｘ≦ｕ＋ｉ
ｖ＋ｊ−ｎ＜ｙ≦ｖ＋ｊ
を満たす位置（ｕ、ｖ）の近傍領域の（ｘ，ｙ）に関して、距離下限値ｂｏｕｎｄ（ｘ，ｙ）を更新する。すなわち、
ｂｏｕｎｄ(ｘ，ｙ)＝
maｘ(ｂｏｕｎｄ(ｘ，ｙ)，ｄ−ｄ(Ｒ(ｉ，ｊ），Ｒ(ｕ＋ｉ−ｘ，ｖ＋ｊ−ｙ))
【００９５】
次に、上記実施例の場合に、以上で説明した本実施形態のテンプレートマッチング装置が、従来手法に比べてどの程度高速であるかの評価を行った例を下記に説明する。
この評価では、図３に示すＲＧＢ各８ビット、ＣＩＦサイズ（３５２×２８８）の画像を使用した。その内部に含まれる５種類の物体を切り出した画像をテンプレートとした。
テンプレートの大きさは５０×５０である。入力画像には、図３の画像にガウスノイズを加えて生成したＳ／N比２０ｄBの人工画像１０枚を用いた。実験にはＣＰＵ：Ｉｎｔｅｌ  Ｐｅｎｔｉｕｍ（登録商標）４（３．０６ＧＨｚ）、ＯＳ：ＲｅｄＨａｔ  Ｌｉｎｕｘ８．０の計算機を用い、コンパイラにＧＮＵ  ｇ＋＋、最適化オプションに−Ｏ３を用いて生成した実行ファイルを使用した。
【００９６】
本実施形態のテンプレートマッチング装置では、サブテンプレートをどの程度の大きさで選ぶかによって、探索時間が異なる。例えば、（m，n）が大きいほど、照合を省略できる範囲が増える一方、テンプレートの類似性が小さく距離が大きくなるため、下限値が小さくなり照合を省略できる可能性が小さくなる。
このトレードオフを検討するため、サブテンプレートの大きさ（ｍ＝ｎ＝０，１，２，・・・，９）と変えて探索時間を調べた。ただし、（ｍ＝ｎ＝０）は、ＳＳＤＡ法と一致する。
部分距離値を計算するサブテンプレートは最も左上のサブテンプレートを用い、右下から左上へ順に探索した。
【００９７】
実験結果を図７に示す。ほとんどの物体で３〜５程度小さいサブテンプレートを用いたときに探索時間が最小になり、５以上小さいサプテンプレートを用いても探索時間の変化は小さかった。
さらにサプテンプレートの大きさを最速の値に設定し、初期閾値を１０００００〜４５００００と変えて実験を行った。実験結果を図８に示す。
【００９８】
ＳＳＤＡ法も提案手法も初期閾値が小さいほど探索時間が短くなるが、提案手法の方が短い時間で探索でき、初期閾値１００００の場合にＳＳＤＡ法の約１／６の時間で探索できた。以上の実験では正解率１００％であり、位置誤りもなかった。
【００９９】
参考までに、ＲＧＢの上位４ビットで表現される４０９６色の色空間に対して色ヒストグラムを作成したアクティブ探索法を用いて同じ条件下で探索した結果をあげると、平均探索時間は約．１５〜．２秒、正解率は９０％、正解の場合の平均位置ずれ誤差は約５画素であった。
【０１００】
以上説明したように、本実施形態のテンプレートマッチング装置によれば、テンプレートから複数のサブテンプレートを取り出して、１のサブテンプレートを選択し、入力信号において、複数の局所領域を設定し、該設定した複数の局所領域から順に１の局所領域を取り出して候補局所領域とし、候補局所領域の一部である部分局所領域とテンプレートとの距離下限値と閾値とを比較して、閾値以上であれば、次に照合すべき候補局所領域を選択し、選択した１のサブテンプレートと候補局所領域における部分局所領域とから計算される部分距離値が閾値以下であれば、テンプレートにおける１のサブテンプレート以外の領域と候補局所領域における部分局所領域以外の領域との距離値をさらに加算し、テンプレートと候補局所領域とから計算される距離値が閾値以下であれば、最も類似する領域として当該位置を記録するとともに、閾値を更新し、テンプレートから取り出した複数のサブテンプレートと１のサブテンプレートとから計算される自己距離値と、部分距離値又はテンプレートと候補局所領域とから計算される距離値とを比較し、候補局所領域周辺の局所領域の距離下限値を更新する。
このように構成することで、従来とまったく同じ結果を得ることを保証することができるとともに、かつ、従来よりも高速にテンプレートと類似した信号を検出することができるという優れた効果を奏し得る。
この結果、本手法を画像に適用した場合には人物や物体などのコンテンツの検索、動画像中からの移動物体の追跡、ステレオ照合における対応点検出などに役立つ。音・映像情報に対して本発明を適用した場合には、ＣＭや希望のシーンの検索、MPEG等の動画・音声圧縮などの高精度化、高速化に役立つ。
【０１０１】
尚、本発明の高速信号探索方法及び装置は、上述の図示例にのみ限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加え得ることは勿論である。
【０１０２】
上述のテンプレートマッチング装置は、内部に、コンピュータシステムを有している。
そして、上述したテンプレートマッチング処理に関する一連の処理の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータが読み出して実行することによって、上記処理が行われる。
すなわち、テンプレートマッチング装置における、各処理手段、処理部は、ＣＰＵ等の中央演算処理装置がＲＯＭやＲＡＭ等の主記憶装置に上記プログラムを読み出して、情報の加工・演算処理を実行することにより、実現されるものである。
ここでコンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等をいう。また、このコンピュータプログラムを通信回線によってコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしても良い。
【産業上の利用可能性】
【０１０３】
テンプレートマッチング方法、装置、プログラム及びその記録媒体は、高速に目的の信号がどこにあるかを求めることによって、音・映像の場合は、テレビ・ラジオ放送などからのＣＭ・楽曲検出技術、MPEG等の動画・音声圧縮などに、画像の場合は、人物や物体などのコンテンツの検索・位置推定などに応用可能である。
【図面の簡単な説明】
【０１０４】
【図１】テンプレートマッチング装置のブロック図である。
【図２】テンプレート、入力画像の一例である。
【図３】入力画像中からテンプレートと類似する領域を検出した結果の一例である。
【図４】テンプレートマッチング処理過程を示すフローチャートである。
【図５】テンプレート内に含まれるサブテンプレートの一例である。
【図６】サブテンプレートと、サブテンプレートと同じ大きさの局所領域の一部との照合の結果得られる距離を用いて、近傍の局所領域の距離下限値の求め方を示す図である。
【図７】サブテンプレートの大きさを変化させたときの探索時間の変化を示した実験結果を表す図である。
【図８】距離閾値を変えたときの従来手法（ＳＳＤＡ法）と本実施形態によるテンプレートマッチング装置の探索時間の変化を示した実験結果を表す図である。
【符号の説明】
【０１０５】
１…テンプレート入力手段
２…サブテンプレート生成手段
３…サブテンプレート選択手段
４…自己距離値計算手段
５…入力信号入力手段
６…局所領域設定手段
７…局所領域順序設定手段
８…候補局所領域選択手段
９…部分距離値計算手段
１０…追加距離値計算手段
１１…検出結果更新手段
１２…局所領域枝刈手段
【図１】
2005063206.tif 000028
【図２】
2005063206.tif 000029
【図３】
2005063206.tif 000030
【図４】
2005063206.tif 000031
【図５】
2005063206.tif 000032
【図６】
2005063206.tif 000033
【図７】
2005063206.tif 000034
【図８】
2005063206.tif 000035