(57)【要約】【課題】類似位置を高速に探索可能であり、過剰検出や探索漏れを抑制可能な類似区間検出技術を提供する。【解決手段】特徴量抽出部１２２は、第１入力受付部１２０が入力を受け付けた映像信号Ｖｘから特徴量列Ｘを抽出し、第２入力受付部１２１が入力を受け付けた映像信号Ｖｙから特徴量列Ｙを抽出する。類似位置検出部１２３は、特徴量列Ｘ及び特徴量列Ｙを時系列に照合して、その類似度がしきい値記憶部１２４に記憶された探索しきい値θより大きい位置を類似位置として検出する。検出結果出力部１２５は、類似位置検出部１２３の検出結果ｒを２値化して出力する。類似位置分布算出部１２６は、検出結果ｒを用いて、類似位置の数の分布を算出する。しきい値更新部１２７は、類似位置の分布が所定の分布条件を満たす場合に、しきい値記憶部１２４に記憶された探索しきい値θを更新する。【選択図】        図１
2010224481.tif 000002
【特許請求の範囲】
【請求項１】
第１の時系列信号の入力を受け付ける第１入力受付手段と、
第２の時系列信号の入力を受け付ける第２入力受付手段と、
前記第１の時系列信号から第１の特徴量を抽出し、前記第２の時系列信号から第２の特徴量を抽出する抽出手段と、
第１のしきい値を記憶する記憶手段と、
前記第１の特徴量及び前記第２の特徴量を時系列に照合して、その類似度が前記第１のしきい値以上の位置である類似位置を検出する検出手段と、
前記類似位置の数の分布を算出する算出手段と、
前記類似位置の数の分布が所定の分布条件を満たす場合に、検出される類似位置の数が減少するように前記第１のしきい値を更新する更新手段と、
前記検出手段、前記算出手段及び前記更新手段を繰り返し動作させることにより、前記類似位置の集合である類似区間を取得する制御手段とを備える
ことを特徴とする類似区間検出装置。
【請求項２】
前記所定の分布条件は、前記類似位置の数と、前記類似位置の数の変化率と、前記第１の特徴量を第１軸とし前記第２の特徴量を第２軸とする２次元空間上で直線検出によって求めた、前記第１軸又は前記第２軸に平行な線分の長さとのうち少なくとも１つに基づいて設定されるものであり、
前記更新手段は、
前記所定の分布条件を満たすか否かを判定する判定手段と、
前記所定の分布条件を満たす場合に、前記第１のしきい値を更新するしきい値更新手段とを有する
ことを特徴とする請求項１に記載の類似区間検出装置。
【請求項３】
前記所定の分布条件は、前記類似位置の数が第２のしきい値を超えること、前記類似位置の数の変化率が第３のしきい値を超えること及び前記線分の長さが第４のしきい値を超えることのうち少なくとも１つであり、
前記判定手段は、前記所定の分布条件を満たすか否かを判定する
ことを特徴とする請求項２に記載の類似区間検出装置。
【請求項４】
前記所定の分布条件は、類似位置を検出する際に用いられ前記類似位置の数の増加に応じて増加するパラメータと、前記第１の特徴量及び前記第２の特徴量の照合を省略可能な領域を管理する谷の数とのうち少なくとも１つに基づいて設定されるものであり、
前記更新手段は、
前記所定の分布条件を満たすか否かを判定する判定手段と、
前記所定の分布条件を満たす場合に、前記第１のしきい値を更新するしきい値更新手段とを有する
ことを特徴とする請求項１に記載の類似区間検出装置。
【請求項５】
前記所定の分布条件は、前記パラメータが第５のしきい値を超えること及び前記谷の数が第６のしきい値を超えることのうち少なくとも１つであり、
前記判定手段は、前記所定の分布条件を満たすか否かを判定する
ことを特徴とする請求項４に記載の類似区間検出装置。
【請求項６】
前記更新手段は、前記類似位置の数の分布が所定の分布条件を満たす場合に、前記第１のしきい値に対して定数を加える又は前記第１のしきい値に反比例する値を新たな第１しきい値とすることにより、前記第１のしきい値を更新する
ことを特徴とする請求項１乃至５のいずれか一項に記載の類似区間検出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似区間検出装置のしきい値の最適化に関する。
【背景技術】
【０００２】
例えば、異なる日に放送された同じ番組の２つの映像の時系列信号から類似区間を検出することによって、映像にインデックスを付加して視聴を容易にする技術が提案されている（例えば特許文献１参照）。類似区間とは連続する類似位置の集合である。映像などの２つの時系列信号から類似区間を探索することを部分信号探索という。部分信号探索では、時系列信号Ｘ上に探索窓Ｗｘを設定すると共に時系列信号Ｙ上に探索窓Ｗｙを設定し、探索窓Ｗｘ内の信号と探索窓Ｗｙ内の信号とを照合する際に、探索窓Ｗｘと探索窓Ｗｙの間で類似度を算出し、類似度が探索しきい値θを上回る場合に、探索窓Ｗｘ内の信号と探索窓Ｗｙ内の信号とが類似すると判定して、類似区間を探索する方法がある。しかし、このような探索をしらみつぶしに行うと処理量が膨大になる。このため、近年では類似度が探索しきい値θを明らかに下回る位置での照合を省略して、探索を高速化する方法が提案されている（例えば非特許文献１参照）。この手法はＲＩＦＡＳ法と呼ばれる。ＲＩＦＡＳ法では、探索しきい値θが大きいほど高速に探索できるが、探索漏れが増えるというトレードオフの関係がある。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第４０２１５４５号公報
【非特許文献】
【０００４】
【非特許文献１】西村拓一，ほか，”アクティブ探索法による時系列データ中の一致区間検出‐参照区間自由時系列アクティブ探索法‐，“信学論Ｄ−ＩＩ，Ｖｏｌ．Ｊ８４−Ｄ−ＩＩ，Ｎｏ．８，ｐｐ．１８２６−１８３７，Ａｕｇ．２００１．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
探索漏れが起きない最大値に探索しきい値θを設定すれば最も高速に探索ができる。しかし、従来は、探索しきい値θを適切な値に設定することは困難であり、探索しきい値θを経験的に求めていた。このため、過剰検出や探索漏れが発生する恐れがあった。
【０００６】
本発明は、上記に鑑みてなされたものであって、類似位置を高速に探索可能であり、過剰検出や探索漏れを抑制可能な類似区間検出装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上述した課題を解決し、目的を達成するために、本発明は、類似区間検出装置であって、第１の時系列信号の入力を受け付ける第１入力受付手段と、第２の時系列信号の入力を受け付ける第２入力受付手段と、前記第１の時系列信号から第１の特徴量を抽出し、前記第２の時系列信号から第２の特徴量を抽出する抽出手段と、第１のしきい値を記憶する記憶手段と、前記第１の特徴量及び前記第２の特徴量を時系列に照合して、その類似度が前記第１のしきい値以上の位置である類似位置を検出する検出手段と、前記類似位置の数の分布を算出する算出手段と、前記類似位置の数の分布が所定の分布条件を満たす場合に、検出される類似位置の数が減少するように前記第１のしきい値を更新する更新手段と、前記検出手段、前記算出手段及び前記更新手段を繰り返し動作させることにより、連続する前記類似位置の集合である類似区間を取得する制御手段とを備えることを特徴とする。
【発明の効果】
【０００８】
本発明によれば、類似位置を高速に探索可能であり、過剰検出や探索漏れを抑制可能になる。
【図面の簡単な説明】
【０００９】
【図１】図１は、一実施の形態にかかる類似区間検出装置１００のハードウェア構成を例示する図である。
【図２】図２は、類似区間検出装置１００の機能的構成を例示する図である。
【図３】図３は、類似区間検出装置１００の行う類似区間検出処理の手順を示すフローチャートである。
【図４】図４は、探索しきい値θを最適化する原理を説明するための図である。
【発明を実施するための形態】
【００１０】
以下に添付図面を参照して、この発明にかかる類似区間検出装置の最良な実施の形態を詳細に説明する。
【００１１】
[第１の実施の形態]
（１）構成
図１の通り、類似区間検出装置１００は、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）１０４やＲＡＭ（Random Access Memory）１０５等の主記憶部と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶部１０７と、これらを接続するバス１０８とを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、類似区間検出装置１００には、情報を表示する表示部１０３と、ユーザの指示入力を受け付けるキーボードやマウス等の操作部１０２と、外部装置との通信を制御する通信部１０６とが有線又は無線により各々接続される。
【００１２】
次に、このようなハードウェア構成において、類似区間検出装置１００のＣＰＵ１０１が記憶部や外部記憶部１０７に記憶された各種プログラムを実行することにより実現される各種機能について、図２を参照して説明する。類似区間検出装置１００は、第１入力受付部１２０と、第２入力受付部１２１と、特徴量抽出部１２２と、類似位置検出部１２３と、しきい値記憶部１２４と、検出結果出力部１２５と、類似位置分布算出部１２６と、しきい値更新部１２７とを有する。第１入力受付部１２０と、第２入力受付部１２１と、特徴量抽出部１２２と、類似位置検出部１２３と、検出結果出力部１２５と、類似位置分布算出部１２６と、しきい値更新部１２７とは、ＣＰＵ１０１のプログラム実行時にＲＡＭ１０５などの記憶部に生成されるものである。しきい値記憶部１２４は、ＨＤＤなどの外部記憶部１０７に生成される記憶領域である。
【００１３】
第１入力受付部１２０は、単位時間毎に撮像された映像を時系列で表す映像信号Ｖｘの入力を受け付ける。第２入力受付部１２１は、第１入力受付部１２０に入力される信号とは異なる映像信号Ｖｙの入力を受け付ける。しきい値記憶部１２４は、探索しきい値θ（０≦θ≦１）を記憶する。
【００１４】
特徴量抽出部１２２は、第１入力受付部１２０が入力を受け付けた映像信号Ｖｘから、単位時間毎の特徴量を抽出することにより、単位時間毎の特徴量を含む特徴量列Ｘを抽出すると共に、第２入力受付部１２１が入力を受け付けた映像信号Ｖｙから、単位時間毎の特徴量を抽出することにより、単位時間毎の特徴量を含む特徴量列Ｙを抽出する。映像信号から特徴量列を抽出する方法は、例えば以下の通りである。特徴量抽出部１２２は、単位時間に撮像された１枚のフレーム画像を９つの領域に分割し、各領域について平均輝度を求め、４段階（２ｂｉｔ）に量子化する。また、特徴量抽出部１２２は、これとは別に１つのフレーム画像全体の平均輝度も求め、１６段階（４ｂｉｔ）に量子化する。そして、特徴量抽出部１２２は、これらの平均輝度を連結して２２ｂｉｔの特徴量を抽出する。このようにして特徴量抽出部１２２は単位時間毎の特徴量を抽出し、これらを時系列で配列したものを特徴量列として抽出する。
【００１５】
類似位置検出部１２３は、特徴量列Ｘ及び特徴量列Ｙを時系列に照合して類似位置を探索し、その類似度がしきい値記憶部１２４に記憶された探索しきい値θより大きい位置を類似位置として検出する。具体的には、類似位置検出部１２３は、特徴量列Ｘ上に探索窓Ｗｘを設定すると共に、特徴量列Ｙ上に探索窓Ｗｙを設定し、探索窓Ｗｘ内の特徴量列と探索窓Ｗｙ内の特徴量列を照合して、映像信号Ｖｘ，Ｖｙにおける類似位置を探索する。探索窓とは、所定の時間の範囲であり、特徴量列上に設定されることにより、所定の時間の範囲内に対応する特徴量を含む特徴量列が照合の対象となる。このような探索窓Ｗｘ内の特徴量列と探索窓Ｗｙ内の特徴量列とを照合する際に、類似位置検出部１２３は、探索窓Ｗｘ,Ｗｙの間で特徴量列の類似度を算出し、当該類似度が、しきい値記憶部１２４に記憶された探索しきい値θより大きい場合に、探索窓Ｗｘの位置ｘ及び探索窓Ｗｙの位置ｙを表すｐ（ｘ，ｙ）を類似位置として検出する。そして類似位置検出部１２３は、検出した類似位置及びその類似度ｓを出力する。類似位置検出部１２３は、このような類似位置を探索する処理を、例えば、探索窓Ｗｙの位置ｙを０から１サンプルずつ順に進めて固定し、固定した位置ｙにおいて探索窓Ｗｘを自由に移動させて位置ｙ毎に繰り返し行う。
【００１６】
探索窓Ｗｘ,Ｗｙの間の特徴量列の類似度を算出する方法は例えば以下の通りである。類似位置検出部１２３は、探索窓Ｗｘ内の特徴量列のヒストグラムＨｘと、探索窓Ｗｙ内の特徴量列のヒストグラムＨｙとを求め、ヒストグラムＨｘ,Ｈｙが重なる割合を表すヒストグラム重なり率を類似度として算出する。ヒストグラムＨｘ，Ｈｙを各々構成する各ビン（柱）の数をＭ，ヒストグラムの要素を各々ｈｘｉ，ｈｙｉとすると（１≦ｉ≦Ｍ）、ヒストグラム重なり率ｓ（Ｈｘ，Ｈｙ）は以下の式１により求めることができる。
【００１７】
【数１】
2010224481.tif 000003
【００１８】
なお、本実施の形態においては、類似位置検出部１２３は、ＲＩＦＡＳ法に示されるように、類似度が探索しきい値θを明らかに下回る位置での照合を省略することによって、類似位置を高速に探索する。上述したＲＩＦＡＳ法では、探索空間上の１点で類似度ｓが求まると、類似度が探索しきい値θを超えない領域であり、即ち、探索をスキップ可能であるスキップ可能領域があることが示されている。ＲＩＦＡＳ法では、このスキップ可能領域で探索空間全体を敷き詰めて探索を進める。スキップ可能領域は４５度傾いた正方形の領域であり、対角線の長さを２ｗとするとｗは以下の式２で表すことができる。
【００１９】
【数２】
2010224481.tif 000004
【００２０】
この式２は、探索しきい値θが大きければ、スキップ可能領域も大きくなることを示している。よって、探索しきい値θが大きければ探索を高速化できる。一方大きくし過ぎると探索しきい値θ以下の類似位置は検出できなくなるから、探索漏れが発生する。本実施の形態においては、類似位置検出部１２３の機能により類似位置を高速に探索可能にする。また、以下で説明する検出結果出力部１２５、類似位置分布算出部１２６及びしきい値更新部１２７の各機能により、検出される類似位置の数が減少するように探索しきい値θを最適化することにより、過剰検出や探索漏れを抑制可能にする。
【００２１】
検出結果出力部１２５は、類似位置検出部１２３の検出結果ｒを２値化して出力する。即ち、探索窓Ｗｘ内の特徴量列と探索窓Ｗｙ内の特徴量列との照合の結果、類似位置ｐ（ｘ，ｙ）が出力された場合、検出結果出力部１２５は、「ｒ＝１」として検出結果ｒを出力し、類似位置が出力されない場合、「ｒ＝０」として検出結果ｒを出力する。
【００２２】
類似位置分布算出部１２６は、類似位置検出部１２３が出力する検出結果ｒを用いて、類似位置の数の分布を算出する。具体的には、類似位置分布算出部１２６は、例えば、探索窓Ｗｙの位置ｙ毎に、当該探索窓Ｗｙに対して各々設定される探索窓Ｗｘにおいて各々出力される検出結果ｒについて、当該値が１の個数を算出して、単位長さ辺りの類似位置の数の平均値Ｎを算出する。
【００２３】
しきい値更新部１２７は、類似位置分布算出部１２６が算出した、類似位置の分布が所定の分布条件を満たす場合に、探索しきい値θを更新し、更新した値をしきい値記憶部１２４に記憶させる。所定の分布条件とは、例えば、類似位置分布算出部１２６が算出した平均値Ｎが更新しきい値α１を超えることである。更新しきい値α１は例えばＨＤＤなどの外部記憶部１０７に予め記憶されている。探索しきい値θの更新は、例えば、更新の都度、探索しきい値θに対して定数ｄを加えることにより行なう。この結果、更新の都度、探索しきい値θは定数ｄずつ増加することになる。定数ｄは例えばＨＤＤなどの外部記憶部１０７に予め記憶されている。このように更新された探索しきい値θを用いて類似位置検出部１２３が類似位置を探索すると、更新前の探索しきい値θを用いた場合と比べて、検出される類似位置の数は減少することになり、過剰検出が減少することになる。
【００２４】
本実施の形態において、平均値Ｎが更新しきい値α１が超える場合に、過剰検出が発生していると判定するのは以下の理由からである。特徴量列ＸをＸ軸とし特徴量列ＹをＹ軸とする２次元のＸＹ空間において、類似区間は傾き１の線分として検出される。一方、過剰検出はＸ軸あるいはＹ軸に平行な線分として検出される。従って、類似位置検出部１２３が位置ｙ毎の単位長さ辺りの類似位置数の平均値Ｎを算出することでＸ軸に平行な線分を検出し、この平均値Ｎと更新しきい値α１とを比較することにより過剰検出が発生しているか否かを判定することができるからである。そして、本実施の形態においては、過剰検出が発生していると判定した場合には、しきい値更新部１２７が、過剰検出が減少するように、即ち、検出される類似位置の数が減少するように探索しきい値θを更新する。このように、類似位置分布算出部１２６が位置ｙ毎に算出した平均値Ｎが更新しきい値α１より大きくなる都度、しきい値更新部１２７が探索しきい値θを更新することにより、探索しきい値θを最適化し、最適化された探索しきい値θを用いて類似位置検出部１２３が類似位置の探索を行なう。このような処理を類似位置検出部１２３は類似位置の探索を行なう過程で過剰検出が発生しなくなるまで繰り返すことによって、探索しきい値θを最適化し、連続する類似位置の集合である類似区間を取得する。
【００２５】
（２）動作
次に、本実施の形態にかかる類似区間検出装置１００の行う類似区間検出処理の手順について図３を用いて説明する。ステップＳ１では、類似区間検出装置１００には、第１入力受付部１２０の機能により、映像信号Ｖｘの入力を受け付け、第２入力受付部１２１の機能により、映像信号Ｖｙの入力を受け付ける。そして、類似区間検出装置１００は、特徴量抽出部１２２の機能により、映像信号Ｖｘから特徴量列Ｘを抽出し、映像信号Ｖｙから特徴量列Ｙを抽出する。ステップＳ２では、類似区間検出装置１００は、類似位置検出部１２３の機能により、特徴量列Ｘ上に探索窓Ｗｘを設定すると共に、特徴量列Ｙ上に探索窓Ｗｙを設定し、まず、探索窓Ｗｙの位置ｙを０に初期化する。ステップＳ３では、類似区間検出装置１００は、類似位置検出部１２３の機能により、特徴量列ＸをＸ軸とし特徴量列ＹをＹ軸とした２次元のＸＹ空間上の全ての位置ｙ，ｘで類似位置の探索が終了したか否かを判断し、当該判断結果が肯定的である場合、処理を終了し、当該判断結果が否定的である場合、探索窓Ｗｙの位置ｙを正方向に１サンプル移動させ、ステップＳ４に進む。
【００２６】
ステップＳ４では、類似区間検出装置１００は、探索窓Ｗｙの位置ｙを固定して、探索窓Ｗｘの位置ｘを自由に移動させ（例えば１サンプルずつ正方向に移動させる。あるいはＲＩＦＡＳ法によって探索が必要な位置に移動する。）、探索窓Ｗｘ内の特徴量列と探索窓Ｗｙ内の特徴量列とを照合して、類似位置を探索する。この照合の際に、類似区間検出装置１００は、探索窓Ｗｘ,Ｗｙの間で特徴量列の類似度を算出し、当該類似度が、しきい値記憶部１２４に記憶された探索しきい値θより大きいか否かを判定する。当該類似度が、しきい値記憶部１２４に記憶された探索しきい値θより大きい場合に、類似区間検出装置１００は、探索窓Ｗｘ,Ｗｙの位置ｐ（ｘ，ｙ）を類似位置として検出し、当該類似位置及びその類似度ｓを出力する。また、類似区間検出装置１００は、検出結果出力部１２５の機能により、類似位置の検出結果ｒを出力する。なお、上述したＲＩＦＡＳ法を用いて、ステップＳ４では、類似区間検出装置１００は、類似度が探索しきい値θを明らかに下回る位置（スキップ可能領域）での照合を省略する。
【００２７】
位置ｙに対する全ての位置ｘについて類似位置の探索が終了すると、ステップＳ５では、類似区間検出装置１００は、類似位置分布算出部１２６の機能により、位置ｙにおいて位置ｘ毎に各々検出された検出結果ｒについてその値が１の個数を算出して、単位長さ辺りの類似位置数の平均値Ｎを算出する。ステップＳ６では、類似区間検出装置１００は、しきい値更新部１２７の機能により、ステップＳ５で算出した平均値Ｎが更新しきい値α１を超えるか否かを判定する。平均値Ｎが更新しきい値α１を超える場合は、過剰検出が発生したということである。この場合、ステップＳ７では、類似区間検出装置１００は、しきい値記憶部１２４に記憶された探索しきい値θに対して定数ｄを加えて探索しきい値θを更新して、更新した値をしきい値記憶部１２４に記憶させる。その後ステップＳ３に戻る。
【００２８】
次に、本実施の形態で探索しきい値θを最適化する原理について図４を用いて説明する。符号３０１は、特徴量列ＸをＸ軸とし特徴量列ＹをＹ軸とした２次元のＸＹ空間において設定される探索窓Ｗｘ，Ｗｙ及び当該ＸＹ空間において類似位置検出部１２３が検出した類似位置を黒点の集合として表している。同図においては、黒点の集合は、傾き１の線分や、Ｘ軸に平行な線分や、Ｙ軸に平行な線分として表されている。符号３０２は、類似位置分布算出部１２６がＹ軸上の位置毎に算出した単位長さ当たりの類似位置の数についての推移を表している。符号３０３は、しきい値更新部１２７が更新する探索しきい値θの推移を表している。
【００２９】
まず，過剰検出による類似位置と真の類似位置の違いを説明する。上述したように、類似区間検出装置１００は、探索窓Ｗｙの位置ｙを０から１サンプルずつ順に移動して固定し、固定した位置ｙにおいて探索窓Ｗｘを自由に移動させて類似位置を探索するという処理を位置ｙ毎に繰り返し行う。符号３０１に示されるように、真の類似位置は傾きが１の線分の周辺に分布する。一方、過剰検出による類似位置はＸ軸またはＹ軸に平行な線分の周辺に分布する。例えば、映像信号Ｖｙの表す映像に暗部がある場合、映像信号Ｖｘの表す映像にある暗部と類似するとしてこの暗部が類似位置として検出されることがある。また、映像信号Ｖｘにおいて暗部を有するフレーム画像が連続する場合は、Ｘ軸に平行な線分の周辺に類似位置が分布する傾向がある。暗部自体は厳密には一致するものではないため、過剰検出による暗部での類似度は、真の類似位置での類似度よりも低くなる。このため、探索しきい値を適切に設定すれば、真の類似位置と過剰検出による類似位置とを区別することができる。
【００３０】
次に、類似位置の過剰検出と探索しきい値の最適化とについて説明する。まず、類似区間検出装置１００は、探索しきい値θを、当該探索しきい値の最適な値として想定される最適値θａよりも低い値θｏに設定して探索を始める。即ち、探索しきい値θの初期値としてθｏがしきい値記憶部１２４に予め記憶される。上述したように過剰検出による類似位置はＸ軸に平行な線分の周辺に分布するから、例えば探索窓Ｗｙの位置が０からｙ１まで進むと、符号３０２に示されるように、位置ｙ１でのＸ軸についての単位長さ当たりの類似位置の数が急激に増加する。この数の平均値をＮ（ｙ１）とすると、以下の式３が成立する場合に過剰検出が発生したと類似区間検出装置１００は判定する。α１は、上述した更新しきい値である。
【００３１】
【数３】
2010224481.tif 000005
【００３２】
そして、類似区間検出装置１００は、過剰検出が発生したと判定した場合、探索しきい値θを定数ｄだけ増加させることにより、探索しきい値を更新する。更新後の探索しきい値をθ’とすると、以下の式４が成り立つ。
【００３３】
【数４】
2010224481.tif 000006
【００３４】
類似区間検出装置１００は、更新後の探索しきい値θ’を新たに探索しきい値θとして用いて類似位置を探索する。探索しきい値θが大きくなると、検出される類似位置の数は減少する。しかし、更新された探索しきい値θが最適値よりも小さい場合、探索を進めるうちに、符号３０２に示すように、Ｘ軸の単位長さ当たりの類似位置の数が更新しきい値α１を超えることが繰り返し起こり得る。このため、このようなことが起こった場合に、類似区間検出装置１００は、探索しきい値θを式４により改めて更新することで、検出される類似位置の数が減少するように探索しきい値θを最適化する。このようにして、本実施の形態によれば、探索しきい値を自動的に最適値に設定することができ、その結果、過剰検出や探索漏れを抑制可能に、また類似位置を高速に探索することができる。
【００３５】
[第２の実施の形態]
次に、類似区間検出装置の第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００３６】
（１）構成
本実施の形態においては、時系列信号として音声信号を取り扱い、２つの音声信号から類似区間を検出する構成について説明する。本実施の形態にかかる類似区間検出装置１００の機能的構成自体は図２に例示したものと略同様である。本実施の形態にかかる構成が、上述の第1の実施の形態と異なる点は以下の通りである。第１入力受付部１２０は、単位時間毎に音声信号の入力を受け付け、第２入力受付部１２１は、単位時間毎に音声信号の入力を受け付ける。特徴量抽出部１２２は、第１入力受付部１２０が入力を受け付けた音声信号から、単位時間毎の特徴量を抽出することにより、単位時間毎の特徴量を含む特徴量列を抽出すると共に、第２入力受付部１２１が入力を受け付けた音声信号から、単位時間毎の特徴量を抽出することにより、単位時間毎の特徴量を含む特徴量列を抽出する。音声信号号から特徴量列を抽出する方法は、例えば以下の通りである。なお、音声信号は例えば１１０２５［Ｈｚ］でサンプリングされた１６ｂｉｔのＰＣＭ信号とする。特徴量抽出部１２２は、２次ＩＩＲデジタルフィルタを有し、２次ＩＩＲデジタルフィルタを用いて２００［Ｈｚ］から３７００［Ｈｚ］をｌｏｇスケールで６等分した７つの周波数を中心とするバンドパスフィルタ群を構成する。２次ＩＩＲデジタルフィルタはＣＰＵ１０１がＲＯＭ１０４や外部記憶部１０７に記憶されたプログラムを実行することにより実現しても良いし、ＤＳＰや順序回路で構成しても良い。このバンドパスフィルタ群に、第１入力受付部１２０が入力を受け付けた音声信号及び第２入力受付部１２１が入力を受け付けた音声信号を入力し、特徴量抽出部１２２は、時間について一定間隔毎にパワーを算出する。チャンネル数は７だから一回のサンプリングで７個のパワーＰ（ｉ）（１≦ｉ≦７）が得られる。サンプリング間隔は２９．９７［Ｈｚ］とする。そして、特徴量抽出部１２２は、パワー値Ｐ（ｉ）を３つのしきい値を用いて２ｂｉｔにベクトル量子化してＢ（ｉ）を得る。特徴量抽出部１２２は、このベクトルをＢ（１）Ｂ（２）Ｂ（３）Ｂ（４）Ｂ（５）Ｂ（６）Ｂ（７）の順に連結して１４ｂｉｔの符号を生成し、これを音声信号の特徴量とする。なお、ベクトル量子化で用いるしきい値としては、入力される音声信号が表す音声に似た音声を分析して符号化の効率が最も良い値を求め、この値を固定値として用いれば良い。
【００３７】
（２）動作
次に、本実施の形態にかかる類似区間検出装置１００の行う類似区間検出処理の手順について説明する。本実施の形態にかかる類似区間検出処理の手順自体は図３に示したものと略同様である。ステップＳ１では、類似区間検出装置１００には、第１入力受付部１２０の機能により、音声信号の入力を受け付け、第２入力受付部１２１の機能により、音声信号の入力を受け付ける。そして、類似区間検出装置１００は、特徴量抽出部１２２の機能により、入力を受け付けた２つの音声信号から各々特徴量列を抽出する。ステップＳ２以降は上述の第１の実施の形態と同様である。
【００３８】
以上のような構成によれば、音声信号について類似位置を探索する場合であっても、探索しきい値を自動的に最適値に設定することができ、その結果、過剰検出や探索漏れを抑制可能に、類似位置を高速に探索することができる。
【００３９】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【００４０】
＜変形例１＞
上述した各実施の形態において、類似区間検出装置１００で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供するように構成しても良い。
【００４１】
また、第１入力受付部１２０と、第２入力受付部１２１と、特徴量抽出部１２２と、類似位置検出部１２３と、検出結果出力部１２５と、類似位置分布算出部１２６と、しきい値更新部１２７とは、ＣＰＵ１０１のプログラム実行時にＲＡＭ１０５などの記憶部に生成されるものであるとしたが、これらのうち少なくとも１つをプロセッサなどのハードウェアにより構成しても良い。
【００４２】
＜変形例２＞
上述した各実施の形態において、類似位置検出部１２３は、探索窓Ｗｙを位置ｙに固定して探索窓Ｗｘの位置ｘを自由に移動させて、類似位置の探索を行なったが、探索窓Ｗｘを位置ｘに固定して探索窓Ｗｙの位置ｙを自由に移動させて、類似位置の探索を行なっても良い。
【００４３】
また、上述した各実施の形態において、過剰検出が発生しているか否かを判定するための所定の分布条件は、探索窓Ｗｙを固定した場合の類似位置の数の平均値が更新しきい値α１を超えることであったが、過剰検出による類似位置がＸ軸またはＹ軸に平行な線分の周辺に分布する性質を利用した条件であればどのような分布条件であっても良い。
【００４４】
例えば、類似位置の数の変化率が更新しきい値α２を超えることを所定の分布条件として、過剰検出を判定しても良い。例えば、探索窓Ｗｙが位置ｙ（ｉ）にある場合の類似位置の数をＮ（ｙ（ｉ））、位置ｙ（ｉ＋１）にある場合の類似位置の数をＮ（ｙ（ｉ＋１））とすると、類似位置の変化率Ａ（ｉ）は以下の式５により表すことができる。
【００４５】
【数５】
2010224481.tif 000007
【００４６】
類似位置の変化率Ａ（ｉ）が予め決められた更新しきい値α２を超えて以下の式６に表される関係を満たす場合に所定の条件を満たすとして、過剰検出過剰検出が発生したと判定すれば良い。
【００４７】
【数６】
2010224481.tif 000008
【００４８】
また、探索窓Ｗｙを固定した線分上だけで類似位置の数を計数するのではなく、特徴量列ＸをＸ軸とし特徴量列ＹをＹ軸とした２次元のＸＹ空間を１６等分して、等分された各領域内における類似位置の数Ｎが更新しきい値α３を超えることを所定の条件として、過剰検出を判定しても良い。
【００４９】
また、特徴量列ＸをＸ軸とし特徴量列ＹをＹ軸とした２次元のＸＹ空間上で、上述した各実施の形態のように探索窓Ｗｙを少しずつ移動させながら探索を進める場合に、ハフ変換を用いてＸ軸またはＹ軸に平行な線分を検出し、その線分の長さが更新しきい値α４を超えることを所定の分布条件として、過剰検出を判定しても良い。
【００５０】
また、上述した各実施の形態のように探索窓Ｗｙを少しずつ移動させながら類似位置の数を記憶しておいて、類似位置の数の推移に基づいて所定の分布条件を設定して、過剰検出を判定しても良い。例えば、類似位置の数の推移から分散を求めて、この分散が更新しきい値α５を下回る場合には、類似位置が極端に密に分布していることを表すから、この場合に所定の分布条件を満たすとして、過剰検出が発生したと判定する。
【００５１】
＜変形例３＞
上述した第１の実施の形態において、ＲＩＦＡＳ法ではスキップ可能領域で評価した領域を谷の位置の列Ｕで管理するが、この谷Ｕの数が更新しきい値α６を超えるか否かにより、過剰検出を判定しても良い。ＲＩＦＡＳ法で類似位置を探索する原理を以下に簡単に説明して、この手法で用いられる谷がどのようなものであるかを説明する。ＲＩＦＡＳ法では、特徴量列ＸをＸ軸とし特徴量列ＹをＹ軸とした２次元のＸＹ空間（探索空間という）においてある一点の位置で類似度が求められた場合に、その位置の周囲に探索しきい値θを上回り得ない領域があることを示し、この領域での照合を省略することによって探索を高速化した。この領域がスキップ可能領域である。スキップ可能領域は類似度を求めた位置を中心とする４５度傾いた正方形であり、正方形の対角線の長さは類似度から算出できる。ＲＩＦＡＳ法では部分信号探索問題を２次元の探索空間をスキップ可能領域か類似位置かで敷き詰める問題として定式化した。まず探索窓Ｗｙを固定した状態で探索窓Ｗｘを走査して全ての位置についてスキップ可能領域か類似位置であるかの評価をすると、探索窓Ｗｙを１サンプル移動させる処理を繰り返す。この際にスキップ可能領域か類似位置として評価した領域と未評価の領域との境界線の形状を記憶する必要がある。ＲＩＦＡＳ法ではスキップ可能領域が重なる場合にはその交点を記憶し、類似位置である場合にはその位置を記憶する。これらの位置は他のスキップ可能領域内の位置と比較して、Ｙ軸について小さい位置にあって谷のように見える。そこでこれらの位置を谷と呼ぶ。類似位置が少ない場合にはスキップ可能領域が大きくなるから谷の数も少なくなる。逆に類似位置が多い場合にはスキップ可能領域が小さくなるから谷の数も多くなる。即ち、谷の数は、類似位置の数の増加に応じて増加し、類似位置の数の減少に応じて減少する。この性質を利用して、類似位置の数を直接計数するのではなく、谷の数を計数し、谷の数が更新しきい値α６を超えることを所定の条件として、過剰検出を判定しても良い。
【００５２】
以上のような構成によれば、探索の過程で谷の数は分かっているので、類似位置の数を計数する仕組みを探索処理に新たに加えなくても良い。
【００５３】
その他、類似位置検出部１２３が類似位置を検出する際に用いるパラメータであって類似位置の数の増加に応じて増加するパラメータ値が、更新しきい値α７を超えることを所定の分布条件として、過剰検出を判定しても良い。
【００５４】
なお、更新しきい値を超えるか否かを判定するための対象の値は、上述した類似位置の数、類似位置の数の変化率、ハフ変換によって求めた線分の長さ及びパラメータのうち少なくとも１つの最大値、最小値、平均値及び分散のうち少なくとも１つであれば良い。
【００５５】
＜変形例４＞
上述した第１の実施の形態において、探索しきい値θの更新は、探索しきい値θに対して定数ｄを加えることにより行なったが、検出される類似位置の数が減少するように探索しきい値θを更新するのであればこれに限らない。例えば、１以上の定数ｅを探索しきい値θで割った値を新たな探索しきい値としても良い。更新後の探索しきい値θ’は以下の式７により表わすことができる。
【００５６】
【数７】
2010224481.tif 000009
【００５７】
探索しきい値とその最適値とが大きく離れている場合には、探索しきい値を更新するための更新量は大きい方が好ましく、探索しきい値とその最適値とがあまり離れていない場合には、更新量は小さい方が好ましい。本変形例の構成では、「θ≦１」なので更新量が徐々に減少する。よって，定数を加えて探索しきい値を更新するのと比較すると探索しきい値を最適値により近付けることができる。
【符号の説明】
【００５８】
１００  類似区間検出装置
１０１  ＣＰＵ
１０２  操作部
１０３  表示部
１０４  ＲＯＭ
１０５  ＲＡＭ
１０６  通信部
１０７  外部記憶部
１０８  バス
１０８  しきい値更新部
１２０  第１映像入力受付部
１２１  第２映像入力受付部
１２２  特徴量抽出部
１２３  類似位置検出部
１２４  しきい値記憶部
１２５  検出結果出力部
１２６  類似位置分布算出部
１２７  しきい値更新部
【図１】
2010224481.tif 000010
【図２】
2010224481.tif 000011
【図３】
2010224481.tif 000012
【図４】
2010224481.tif 000013