JP3574075B2

JP3574075B2 - Signal detection method, signal detection device, recording medium, and program

Info

Publication number: JP3574075B2
Application number: JP2001031388A
Authority: JP
Inventors: 昭悟木村; 邦夫柏野; 隆行黒住; 洋村瀬
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 2001-02-07
Filing date: 2001-02-07
Publication date: 2004-10-06
Anticipated expiration: 2021-02-07
Also published as: JP2002236496A

Description

【０００１】
【発明の属する技術分野】
本発明は、信号系列の中から、予め登録した信号と類似した信号の場所を探し出すのに用いて好適な、信号検出方法、信号検出装置、記録媒体及びプログラムに関する。
【０００２】
【従来の技術】
放送の音響信号の中から特定のコマーシャルが放映された時刻を検出し、自動記録したり、あるいは、特定のテーマソングを検出してビデオ録画を開始したり、停止したりするのに音響信号検出技術が用いられる。
上記した音響信号検出技術により、ある信号系列の中から、予め登録した信号と類似した信号の位置を割り出すことが可能となる。また、放送から拍手音の発せられた時刻や、笑い声が発せられた時刻等を自動的に監視したり、あるいは特定シーンの検索を行なうこともできる。
上述した音響信号検出技術の代表的なものに、平成１２年５月１２日に登録された特許第３０６５３１４号「高速信号探索方法、装置およびその記録媒体」がある。
【０００３】
【発明が解決しようとする課題】
しかしながら上述した従来技術によれば、信号検出処理を行いながら蓄積信号特徴ヒストグラムを作成するために、蓄積信号が極めて長時間に及ぶ場合は、信号検出処理に多大な処理時間を要し、目的とする類似した箇所を高速に探索することができなかった。
本発明はこのような事情に鑑みてなされたものであり、新たに蓄積特徴量分類過程、選択閾値設定過程及び蓄積特徴量選択過程を設けることにより、上記特許明細書に記載の実施例に比べて、同一の精度を保証したまま、探索の範囲を効率的に小さくすることで、より高速な信号検出を可能とした信号検出方法、信号検出装置、記録媒体及びプログラムを提供することを目的とする。
【０００４】
【課題を解決するための手段】
上記目的を達成するために、請求項１に記載の発明は、蓄積信号から、あらかじめ登録した目的信号に類似した部分を探し出す信号検出方法であって、目的信号から特徴量系列を導く目的特徴量計算過程と、蓄積信号に注目窓を設定し、注目窓内の信号から特徴量系列を導く蓄積特徴量計算過程と、前記蓄積特徴量計算過程による処理を、注目窓をずらしながら繰り返し行うことで導かれた各特徴量系列を、予め定義された距離に基づいて分類し、その分類の代表特徴量系列を決定する蓄積特徴量分類過程と、前記蓄積特徴量分類過程で定義された距離に対する選択閾値を、特徴量同士の類似度に関して予め設定した閾値である探索閾値から計算する選択閾値設定過程と、前記蓄積特徴量分類過程で導かれた分類について、前記目的特徴量計算過程で導かれた特徴量系列との類似度が、選択閾値から導かれる条件を満たすような代表特徴量系列を持つ分類に含まれる特徴量系列を選択する蓄積特徴量選択過程と、前記蓄積特徴量選択過程で選択された特徴量系列と、前記目的特徴量計算過程で導かれた特徴量系列との類似度を計算する類似度計算過程と、前記類似度計算過程による計算結果に基づいて得られた、蓄積信号のいくつかの箇所についての目的信号との前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するかどうかを決定する類似度判定過程とを有することを特徴とする。
【０００５】
請求項２に記載の発明は、請求項１に記載の信号検出方法において、さらに、前記類似度計算過程で計算された類似度に基づいて、注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動するスキップ幅計算過程を有し、前記類似度計算過程からスキップ幅計算過程に至る処理を繰り返して、蓄積信号のいくつかの箇所について、目的信号との類似度を計算し、前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するか否かを決定することを特徴とする。
【０００６】
請求項３に記載の発明は、請求項１または２のいずれかに記載の信号検出方法において、前記目的特徴量計算過程および前記蓄積特徴量計算過程では、特徴量系列に対してヒストグラムを作成し、前記蓄積特徴量分類過程において該ヒストグラムに基づいて距離を計算し、前記蓄積特徴量選択過程および前記類似度計算過程において該ヒストグラムに基づいて類似度を計算することを特徴とする。
【０００７】
請求項４に記載の発明は、請求項３に記載の信号検出方法において、前記蓄積特徴量選択過程および前記類似度計算過程は、ヒストグラム重なり率によって類似度を計算することを特徴とする。
【０００８】
請求項５に記載の発明は、請求項１ないし４のいずれかに記載の信号検出方法において、前記蓄積特徴量分類過程は、Ｌ２距離（ユークリッド距離）に基づいて各特徴量系列を分類することを特徴とする。
【０００９】
請求項６に記載の発明は、蓄積信号から、あらかじめ登録した目的信号に類似した部分を探し出す信号検出装置であって、目的信号から特徴量系列を導く目的特徴量計算手段と、蓄積信号に注目窓を設定し、注目窓内の信号から特徴量系列を導く蓄積特徴量計算手段と、前記蓄積特徴量計算手段による処理を、前記注目窓をずらしながら繰り返し行うことで導かれた各特徴量系列を、予め定義された距離に基づいて分類し、その分類の代表特徴量系列を決定する蓄積特徴量分類手段と、前記蓄積特徴量分類手段で定義された距離に対する選択閾値を、特徴量同士の類似度に関して予め設定した閾値である探索閾値から計算する選択閾値設定手段と、前記蓄積特徴量分類手段で導かれた分類について、前記目的特徴量計算手段で導かれた特徴量系列との類似度が、前記選択閾値から導かれる条件を満たすような代表特徴量系列を持つ分類に含まれる特徴量系列を選択する蓄積特徴量選択手段と、前記蓄積特徴量選択手段で選択された特徴量系列と、前記目的特徴量計算手段で導かれた特徴量系列との類似度を計算する類似度計算手段と、前記類似度計算手段手段による計算結果に基づいて得られた、蓄積信号のいくつかの箇所についての目的信号との前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するかどうかを決定する類似度判定手段とを有することを特徴とする。
【００１０】
請求項７に記載の発明は、請求項６に記載の信号検出装置において、さらに、前記類似度計算手段で計算された類似度に基づいて、注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動するスキップ幅計算手段を有し、
前記類似度計算手段からスキップ幅計算手段に至る処理を繰り返して、蓄積信号のいくつかの箇所について、目的信号との類似度を計算し、前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するか否かを決定することを特徴とする。
【００１１】
請求項８に記載の発明は、蓄積信号から、あらかじめ登録した目的信号に類似した部分を探し出す信号検出装置に用いられる信号検出プログラムが記録されたコンピュータ読み取り可能な記録媒体において、前記信号検出プログラムは、目的信号から特徴量系列を導く第１のステップと、蓄積信号に注目窓を設定し、注目窓内の信号から特徴量系列を導く第２のステップと、前記第２のステップにおける処理を、注目窓をずらしながら繰り返し行うことで導かれた各特徴量系列を、予め定義された距離に基づいて分類し、その分類の代表特徴量系列を決定する第３のステップと、前記第３のステップで定義された距離に対する選択閾値を、特徴量同士の類似度に関して予め設定した閾値である探索閾値から計算する第４のステップと、前記第３のステップで導かれた分類について、前記第１のステップで導かれた特徴量系列との類似度が、選択閾値から導かれる条件を満たすような代表特徴量系列を持つ分類に含まれる特徴量系列を選択する第５のステップと、前記第５のステップで選択された特徴量系列と、前記第１のステップで導かれた特徴量系列との類似度を計算する第６のステップと、前記第６のステップによる計算結果に基づいて得られた、蓄積信号のいくつかの箇所についての目的信号との前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するかどうかを決定する第７のステップとをコンピュータに実行させる信号検出プログラムを記録したことを特徴とする。
【００１２】
請求項９に記載の発明は、請求項８に記載の記録媒体において、前記信号検出プログラムは、さらに、前記第６のステップで計算された類似度に基づいて、注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動する第８のステップを有し、前記第６のステップから第８のステップに至る処理を繰り返して、蓄積信号のいくつかの箇所について、目的信号との類似度を計算し、前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するか否かを決定するようにコンピュータに実行させる信号検出プログラムを記録したことを特徴とする。
【００１３】
請求項１０に記載の発明は、蓄積信号から、あらかじめ登録した目的信号に類似した部分を探し出す信号検出装置に用いられる信号検出プログラムであって、該信号検出プログラムは、目的信号から特徴量系列を導く第１のステップと、蓄積信号に注目窓を設定し、注目窓内の信号から特徴量系列を導く第２のステップと、前記第２のステップにおける処理を、注目窓をずらしながら繰り返し行うことで導かれた各特徴量系列を、予め定義された距離に基づいて分類し、その分類の代表特徴量系列を決定する第３のステップと、前記第３のステップで定義された距離に対する選択閾値を、特徴量同士の類似度に関して予め設定した閾値である探索閾値から計算する第４のステップと、前記第３のステップで導かれた分類について、前記第１のステップで導かれた特徴量系列との類似度が、選択閾値から導かれる条件を満たすような代表特徴量系列を持つ分類に含まれる特徴量系列を選択する第５のステップと、前記第５のステップで選択された特徴量系列と、前記第１のステップで導かれた特徴量系列との類似度を計算する第６のステップと、前記第６のステップによる計算結果に基づいて得られた、蓄積信号のいくつかの箇所についての目的信号との前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するかどうかを決定する第７のステップとをコンピュータに実行させることを特徴とする。
【００１４】
請求項１１に記載の発明は、請求項１０に記載の信号検出プログラムにおいて、該信号検出プログラムは、さらに、前記第６のステップで計算された類似度に基づいて、注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動する第８のステップを有し、前記第６のステップから第８のステップに至る処理を繰り返して、蓄積信号のいくつかの箇所について、目的信号との類似度を計算し、前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するか否かを決定するようにコンピュータに実行させることを特徴とする。
【００１５】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照して詳細に説明する。本発明では、様々な処理対象信号を用いることができるが、ここでは、該処理対象信号の一例として、音響信号を用いる。
図１は、本発明の実施の形態に係る信号検出装置の構成を示すブロック図である。
【００１６】
本実施の形態に係る信号検出装置は、蓄積信号から、あらかじめ登録した目的信号に類似した部分を探し出す信号検出方法であって、目的信号から特徴量系列を導く目的特徴量計算過程と、蓄積信号に注目窓を設定し、注目窓内の信号から特徴量系列を導く蓄積特徴量計算過程と、前記蓄積特徴量計算過程による処理を、注目窓をずらしながら繰り返し行うことで導かれた各特徴量系列を、予め定義された距離に基づいて分類し、その分類の代表特徴量系列を決定する蓄積特徴量分類過程と、前記蓄積特徴量分類過程で定義された距離に対する選択閾値を、特徴量同士の類似度に関して予め設定した閾値である探索閾値から計算する選択閾値設定過程と、前記蓄積特徴量分類過程で導かれた分類について、前記目的特徴量計算過程で導かれた特徴量系列との類似度が、選択閾値から導かれる条件を満たすような代表特徴量系列を持つ分類に含まれる特徴量系列を選択する蓄積特徴量選択過程と、前記蓄積特徴量選択過程で選択された特徴量系列と、前記目的特徴量計算過程で導かれた特徴量系列との類似度を計算する類似度計算過程と、前記類似度計算過程による計算結果に基づいて得られた、蓄積信号のいくつかの箇所についての目的信号との前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するかどうかを決定する類似度判定過程とを有することを特徴とする信号検出方法を実施するための装置である。
【００１７】
図１において、本実施の形態に係る信号検出装置は、目的特徴量計算手段１と、蓄積特徴量計算手段２と、蓄積特徴量分類手段３と、選択閾値設定手段４と、蓄積特徴量選択手段５と、類似度計算手段６と、スキップ幅計算手段７と、類似度判定手段８とで構成され、目的信号すなわち見本となる検索したい音響信号と、蓄積信号すなわち検索される音響信号を入力とし、目的信号との類似度があらかじめ設定した値（これを探索閾値という）θ以上となる蓄積信号中の箇所を出力する。
【００１８】
上記構成において、目的特徴量計算手段１は、目的信号から特徴量系列を導く機能を有している。
また、蓄積特徴量計算手段２は、蓄積信号に注目窓（注目個所）を設定し、設定された注目窓内の蓄積信号から特徴量系列を導く機能を有している。
蓄積特徴量分類手段３は、蓄積特徴量計算手段２により、蓄積信号に設定した注目窓をずらしながら特徴量抽出を繰り返し行うことで得られた各特徴量系列を、予め定義された距離に基づいて分類し、その分類の代表特徴量系列を決定する機能を有している。
【００１９】
選択閾値設定手段４は、蓄積特徴量分類手段３で定義された距離に対する選択閾値を、特徴量同士の類似度に関して予め設定した閾値である探索閾値から計算する機能を有する。
蓄積特徴量選択手段５は、蓄積特徴量分類手段３から出力された分類について、目的特徴量計算手段１から出力された特徴量系列との類似度が、選択閾値から導かれる条件を満たすような代表特徴量系列を持つ分類に含まれる特徴量系列を選択する機能を有する。
類似度計算手段６は、蓄積特徴量選択手段５から出力された特徴量系列と、目的特徴量計算手段１から出力された特徴量系列との類似度を計算する機能を有する。
【００２０】
また、スキップ幅計算手段７は、類似度計算手段で計算された類似度に基づいて、注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動する機能を有する。
さらに、類似度判定手段８は、類似度計算手段６による計算結果に基づいて得られた、蓄積信号のいくつかの箇所についての目的信号との類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するかどうかを決定する機能を有する。
【００２１】
次に、上記構成からなる信号検出装置の動作を図２に示すフローチャートを参照して具体的に説明する。なお、以下では、説明を簡潔にするために、注目窓の長さを目的信号と同一とした場合について説明するが、「高速信号探索方法、装置及びその記録媒体」（特許第３０６５３１４号）のように注目窓を時間的に分割する場合にも同様に適用できる。
図２において、目的特徴量計算手段１では、はじめに、与えられた目的信号を読み込む（ステップ１１）。
【００２２】
次に、読み込んだ目的信号に対して特徴抽出を行う（ステップ１２）。本実施の形態では、特徴としてスペクトル特徴を用いるので、特徴抽出は、例えば、帯域通過フィルタによって行うことができる。例えば、テレビやラジオ等の放送信号から１５秒程度の音響信号を探索したい場合、特徴抽出の具体的な設定を次のようにすると、良い結果が得られる。すなわち、７個の帯域通過フィルタを用い、それらの中心周波数を対数軸上で等間隔に設定し、６０ミリ秒程度の時間長の分析窓を１０ミリ秒ずつ移動させながら、分析窓内の各帯域通過フィルタの出力の自乗の平均値を計算し、得られた７個の値を一組にして７次元特徴ベクトルとする。この場合特徴ベクトルは１０ミリ秒ごとに１つ得られる。
【００２３】
続いて、特徴ベクトルの時系列から、特徴ベクトルのヒストグラムＨｏを作成する（ステップ１３）。ヒストグラムＨｏは、特徴ベクトルを、ベクトル量子化を用いて符号化することによって作成する。例えば、ベクトル量子化の符号語数が５１２であれば、ヒストグラム全体のビン（区間）の数は５１２となり、各特徴ベクトルは、この５１２個のビンのうちどれか１つに分類されることになる。次いで、蓄積特徴量計算手段２では、はじめに、蓄積音響信号を読み込む（ステップ１４）。
【００２４】
次に、蓄積特徴量計算手段２は、読み込んだ蓄積音響信号に対してスキップ注目窓を設定する。まず、目的特徴量計算手段１に与えられた目的信号と同じ長さの注目窓を設定する。処理の開始時は、注目窓を蓄積信号の先頭に設定するが、処理の過程で、注目窓を順次１特徴ベクトルずつずらしながら処理を進めていく。
続いて、蓄積特徴量計算手段２は、注目窓内の音響信号に対して特徴抽出を行う（ステップ１５）。特徴抽出は、目的特徴量計算手段１において行ったのと同じ操作を行う。
さらに、注目窓内の特徴ベクトルの時系列から、特徴ベクトルのヒストグラムを作成する（ステップ１６）。ヒストグラムの作成の仕方は、目的特徴量計算手段１で行ったのと同じ方法によって行う。
【００２５】
蓄積特徴量分類手段３では、はじめに、蓄積特徴量計算手段２において、注目窓をずらしながら繰り返し行って出力される特徴ベクトルのヒストグラムの系列を読み込む。
蓄積特徴量計算手段２から出力されるヒストグラムをＨｓとする。ただし、Ｓはヒストグラムが蓄積信号の特徴ベクトルから作られたものであることを表す。次に、蓄積特徴量分類手段３は、ヒストグラム系列Ｈｓの各ヒストグラムを、例えば、以下で定める距離に従って分類する（ステップ１７）。すなわち、２つのヒストグラムＨｉとＨｊとの距離ｄ_ｉｊ ^（２）、ユークリッド距離を用いて、以下のように定義する。
【数１】

ただし、Ｌはヒストグラムのビンの総数（上記の例では５１２）であり、ｈｉｌ，ｈｊｌは、それぞれＨｉ，Ｈｊのｌ番目のビンに含まれる特徴ベクトルの数（度数）を表す。
また、距離ｄ_ｉｊ ^（２）の右上につく２は、距離の尺度が２次距離（ユークリッド距離）であることを示す。
【００２６】
ヒストグラムの分類は、各ヒストグラムを、そのビンの数と等しい次元数を持ったベクトルと考えて、そのベクトルをベクトル量子化を用いて符号化することによって行う。例えば、ベクトル量子化の符号語数が５１２個であれば、ヒストグラムを５１２個の集合（本出願ではこれをクラスタと呼ぶ）のいずれか１つに分類されることになる。そして、各クラスタに所属するヒストグラムの重心となるヒストグラム（重心ヒストグラムと呼ぶ）によって、クラスタを代表させることにする。
このとき、クラスタは、それに所属するヒストグラムと重心ヒストグラムとの距離の総和が最小になるように、かつそのクラスタに所属するヒストグラムについて、所属するクラスタの重心ヒストグラムとの距離が、他のどのクラスタの重心ヒストグラムとの距離よりも小さくなるように構成される。
【００２７】
選択閾値設定手段４では、探索閾値θ１から選択閾値θ２バー（ｂａｒ）を決定する（ステップ１８）。
ここで、探索閾／値は、目的信号が蓄積信号中のある時点に存在すると判断する、例えば、目的信号側のヒストグラムと蓄積信号側のヒストグラムとの類似度の下限を指す。
目的信号のヒストグラムＨｏと、蓄積信号のヒストグラムＨｓとの類似度Ｓｏｓは、次のように定義される。
【数２】

ただし、Ｄはヒストグラムの総度数（一つの参照信号から導かれた特徴ベクトルの総数）を表し、ｏはヒストグラムが目的信号の特徴ベクトルから作られたものであることを示す。
【００２８】
また、選択閾値は、探索するべき信号に対応する蓄積信号側のヒストグラムを含む可能性のあるクラスタを選択する際の、目的信号側のヒストグラムとクラスタとの距離の上限を指す。
探索閾値θ１から選択閾値θ２バー（ｂａｒ）を決定する原理を以下で説明する。式（２）で定義された類似度Ｓｏｓは、以下のように、１次距離を用いて表すことができる。
【数３】

ただし、Ｌ１距離に基づくＨｏとＨｓとの距離である。なお、ｄｏｓ^（１）は、
【数４】

である。
【００２９】
ここで、式（２）で定義される類似度はＬ１距離に基づくので、改めてＳｏｓ^（１）として書き表すこととする。Ｌ１距離とＬ２距離との間に成り立つ関係から、
【数５】

が得られる。また、式（１）、（３）、（４）より、
【数６】

となる。
ただし、Ｓｏｓ^（２）はＬ２距離に基づく類似度である。また、Ｓｏｓ^（２）は
【数７】

と定義できる。
【００３０】
ヒストグラムの性質から、
【数８】

が成立するので、式（７）で定義される類似度は、０から１までの値を取る。選択閾値θ２バー（ｂａｒ）によって選択されたヒストグラム、すなわち，
【数９】

が成立する蓄積信号側のヒストグラムが、探索閾値θ１によって検出されるヒストグラム、すなわち、
【数１０】

が成立する蓄積信号側のヒストグラムを全て含む必要があるので、式（６）より、
【数１１】

すなわち、
【数１２】

となればよい。よって、選択閾値θ２バー（ｂａｒ）は、探索閾値θ１によって、次のように与えられる。
【００３１】
【数１３】

蓄積特徴量選択手段５では、はじめに、目的特徴量計算手段１から出力される特徴べクトルのヒストグラムＨｏ、蓄積特徴量分類手段３から出力されるヒストグラムＨｓの分類（クラスタ）、および選択閾値設定手段４から出力される選択閾値を読み込む（ステップ１９）。
次に、読み込んだ目的信号側のヒストグラムＨｏと、蓄積信号側の各クラスタの重心ヒストグラムとの距離を計算する（ステップ２０）。距離の計算は、蓄積特徴量分類手段３で行ったのと同じ操作を行う。
【００３２】
続いて、計算された距離に基づき、探索するべき信号に対応するヒストグラムを含む可能性のあるクラスタを選択する（ステップ２１）。この原理を以下に説明する。
図２は、Ｒ，Ｃ１，Ｃ２の３点が乗るような平面でヒストグラム空間（上記の例では５１２次元）を切り出した様子を示している。ここで、Ｒは目的特徴量計算手段１から出力された特徴べクトルのヒストグラム、Ｃ１はヒストグラムＲが所属しているクラスタの重心ヒストグラム、Ｃ２はある他のクラスタの重心ヒストグラムを表し、ｄ_Ｒ１、ｄ_Ｒ２、ｄ_１２はそれぞれ、式（１）で定義されたＲとＣ_１との距離、ＲとＣ_２との距離、Ｃ_１とＣ_２との距離を示す。
【００３３】
ここで、ヒストグラムＲからの距離がｄ以内であるヒストグラムに対応する蓄積信号の箇所を検出しなければならないとすると、Ｒを中心とする半径ｄの超球（図３においては円）の内部にあるヒストグラムが検出すべき蓄積信号の箇所に対応する。Ｒを中心とする超球の半径が図３におけるｄ_θより大きくなったとき、Ｃ_２に代表されるクラスタに属するヒストグラムの中に、検出すべき蓄積信号の箇所と対応するヒストグラムが含まれている可能性がある。そこで、選択閾値θ２バー（ｂａｒ）がｄ_θより入きくなったとき、Ｃ_２に代表されるクラスタを選択する。
【００３４】
ｄ_θは次のようにして求められる。図３より、次の式が成り立つ。
【数１４】

したがって、式（１４）より、
【数１５】

となる。
よって、式（１５）、（１３）より、
【数１６】

が成り立つとき、Ｃ_２に代表されるクラスタに属するヒストグラムを全て選択する。
【００３５】
この手順を、ヒストグラムＲが所属するクラスタを除く全てのクラスタに対して行い、最終的に選択されたヒストグラムを時刻順に並べ、時間的に連続しているヒストグラムに関しては、連結して時系列を構成する。得られた各ヒストグラムの系列は、蓄積特徴量計算手段２から出力されるヒストグラム時系列の部分系列となっている。このヒストグラム系列の集合を出力する（ステップ２２）。
類似度計算手段６では、はじめに、目的特徴量計算手段１から出力される特徴べクトルのヒストグラムと、蓄積特徴量選択手段５から出力されるヒストグラム時系列の集合を読み込み、目的信号と蓄積信号のヒストグラムとの類似度を計算する（ステップ２４）。
【００３６】
処理の開始時は、蓄積信号のヒストグラムを、ヒストグラム時系列集合の第１要素の先頭から取り出していくが、後に述べるように、処理の過程で、ヒストグラムを取り出す位置を順次時間方向にずらしながら処理を進めていく。時間方向にずらす量は、注目窓をスキップさせるスキップ幅を計算するスキップ幅計算手段７により与えられる（ステップ２５）。
類似度計算手段６は、類似度の値を、スキップ幅計算手段７及び類似度判定手段８に対して出力する。
類似度判定手段は、もし、類似度の値が探索閾値θ１を越えている場合（注目窓を時間方向に分割した場合にあっては、全ての時間分割において類似度の値がθ１を越えていることが判明した場合）は、その目的信号が蓄積信号中に存在したことを意味するので、信号検出結果として、蓄積信号に対する時系列中の現在位置を出力する（ステップ２６、２７、２８）。
【００３７】
次に、本発明を適用した信号検出装置の動作実験例について示す。本発明の効果を確認するため、２４時間の音響信号を蓄積信号とし、無作為に選択した１２個の参照信号（１５秒間）に対して探索を行い、類似度が探索閾値以下であった照合回数について、本発明を適用しなかった場合が、本発明を適用した場合に比べてどのくらいの割合であるか（本出願ではこれを照合回数削減比と呼ぶ）、及び目的特徴量計算手段１から蓄積特徴量選択手段５を除いた処理に要する時間、すなわち探索のみに要する時間について、本発明を適用しなかった場合が、本発明を適用した場合に比べてどのくらいの割合であるか（探索時間短縮比という）について調べた。
【００３８】
探索のパラメータは、サンプリング周波数＝１１．０２５ｋＨｚ、帯域フィルタの数＝７、周波数分析の分析窓長＝６０ｍｓ、分析窓シフト＝１０ｍｓ、ヒストグラムのビン数＝５１２、時間窓分割なし、クラスタ数＝５１２とした。
また、探索閾値θ１は、０．５から１の間で０．０５刻みに変化させ、選択閾値θ２は、式（１３）に基づいて、探索閾値θ１から決定した。
本実験の結果を４３及び図５に示す。
図４は、探索閾値を変化させたときの上記探索時間の平均と探索時間短縮比を示している。例えば、探索閾値θ１＝０．８５において、探索時間の平均は、従来法で０．３９秒、提案法（本発明）で０．０３秒、探索時間短縮比は１３．０であった。
【００３９】
図５は、探索閾値を変化させたときの上記照合回数の平均と照合回数削減比を示している。例えば、探索閾値θ１＝０．８５において、照合回数の平均は、従来法で１１４２７回、提案法（本発明）で１１２６回、照合回数削減比は１０．２であった。
本実施の形態によれば、予め目的信号に類似した蓄積信号の箇所を選択する蓄積特徴量選択手段、選択閾値設定手段、蓄積特徴量分類手段を設けて、無駄な照合計算を省きながら目的とする信号の検索を行うことによって、公知の方法に比較して、より少ない照合計算回数で、より高速な信号探索を行うことができる。
【００４０】
なお、目的信号から特徴量系列を導く第１のステップと、蓄積信号に注目窓を設定し、注目窓内の信号から特徴量系列を導く第２のステップと、前記第２のステップにおける処理を、注目窓をずらしながら繰り返し行うことで導かれた各特徴量系列を、予め定義された距離に基づいて分類し、その分類の代表特徴量系列を決定する第３のステップと、前記第３のステップで定義された距離に対する選択閾値を、特徴量同士の類似度に関して予め設定した閾値である探索閾値から計算する第４のステップと、前記第３のステップで導かれた分類について、前記第１のステップで導かれた特徴量系列との類似度が、選択閾値から導かれる条件を満たすような代表特徴量系列を持つ分類に含まれる特徴量系列を選択する第５のステップと、前記第５のステップで選択された特徴量系列と、前記第１のステップで導かれた特徴量系列との類似度を計算する第６のステップと、前記第６のステップによる計算結果に基づいて得られた、蓄積信号のいくつかの箇所についての目的信号との前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するかどうかを決定する第７のステップとをコンピュータに実行させることを特徴とする信号検出プログラムをコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録された信号検出プログラムをコンピュータシステムに読み込ませ実行することにより、蓄積信号から、あらかじめ登録した目的信号に類似した部分を探し出す信号検出装置の機能を実現するようにしてもよい。
【００４１】
また、前記信号検出プログラムは、さらに、前記第６のステップで計算された類似度に基づいて、注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動する第８のステップを有し、前記第６のステップから第８のステップに至る処理を繰り返して、蓄積信号のいくつかの箇所について、目的信号との類似度を計算し、前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するか否かを決定するようにコンピュータに実行させるものであってもよい。
【００４２】
なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フロッピーディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可般媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに、「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの（伝送媒体ないしは伝送波）、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。
【００４３】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００４４】
【発明の効果】
以上に説明したように、本発明によれば、蓄積信号から、あらかじめ登録した目的信号に類似した部分を探し出す信号検出装置であって、目的信号から特徴量系列を導く目的特徴量計算手段と、蓄積信号に注目窓を設定し、注目窓内の信号から特徴量系列を導く蓄積特徴量計算手段と、前記蓄積特徴量計算手段による処理を、前記注目窓をずらしながら繰り返し行うことで導かれた各特徴量系列を、予め定義された距離に基づいて分類し、その分類の代表特徴量系列を決定する蓄積特徴量分類手段と、前記蓄積特徴量分類手段で定義された距離に対する選択閾値を、特徴量同士の類似度に関して予め設定した閾値である探索閾値から計算する選択閾値設定手段と、前記蓄積特徴量分類手段で導かれた分類について、前記目的特徴量計算手段で導かれた特徴量系列との類似度が、前記選択閾値から導かれる条件を満たすような代表特徴量系列を持つ分類に含まれる特徴量系列を選択する蓄積特徴量選択手段と、前記蓄積特徴量選択手段で選択された特徴量系列と、前記目的特徴量計算手段で導かれた特徴量系列との類似度を計算する類似度計算手段と、前記類似度計算手段手段による計算結果に基づいて得られた、蓄積信号のいくつかの箇所についての目的信号との前記類似度と、探索閾値とを比較することにより、目的信号が、蓄積信号の当該箇所に存在するかどうかを決定する類似度判定手段とを有するので、従来に比して同一の精度を保証したまま、探索の範囲を効率的に小さくすることで、より高速な信号検出を行うことが可能となる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係る信号検出装置の構成を示すブロック図。
【図２】図１に示した本発明の実施の形態に係る信号検出装置の動作を示すフローチャート。
【図３】本発明を適用した、音響信号を対象とする信号検出装置における、蓄積信号のヒストグラムを選択する原理を示す説明図。
【図４】本発明を適用した、音響信号を対象とする信号検出装置による実験結果のうち、本発明を適用した場合の探索時間を測定した結果を示す図。
【図５】本発明を適用した、音響信号を対象とする信号検出装置による実験結果のうち、本発明を適用した場合の照合回数を測定した結果を示す図。
【符号の説明】
１目的信号特徴量計算手段
２蓄積信号特徴量計算手段
３蓄積信号特徴量分類手段
４選択閾値設定手段
５蓄積特徴量選択手段
６類似度計算手段
７スキップ幅計算手段
８類似度判定手段[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a signal detection method, a signal detection device, a recording medium, and a program that are suitable for searching for a location of a signal similar to a signal registered in advance from a signal sequence.
[0002]
[Prior art]
Detects the time when a specific commercial aired from the broadcast audio signal and automatically records it, or detects a specific theme song and starts or stops video recording and detects an audio signal Technology is used.
With the above-described acoustic signal detection technique, it is possible to determine the position of a signal similar to a signal registered in advance from a certain signal sequence. It is also possible to automatically monitor the time when a clapping sound is emitted from the broadcast, the time when a laughter is emitted, or search for a specific scene.
As a typical example of the above-described acoustic signal detection technology, there is Japanese Patent No. 3065314 “High-speed signal search method, device, and recording medium” registered on May 12, 2000.
[0003]
[Problems to be solved by the invention]
However, according to the above-described conventional technology, the signal detection process requires a great deal of processing time when the accumulated signal is extremely long in order to create the accumulated signal feature histogram while performing the signal detection process. It was not possible to search for a similar part quickly.
The present invention has been made in view of such circumstances, and by newly providing an accumulated feature amount classification process, a selection threshold setting process, and an accumulated feature amount selection process, the present invention provides an advantage over the embodiment described in the above patent specification. Therefore, it is an object of the present invention to provide a signal detection method, a signal detection device, a recording medium, and a program that enable a higher-speed signal detection by efficiently reducing a search range while guaranteeing the same accuracy. I do.
[0004]
[Means for Solving the Problems]
In order to achieve the above object, an invention according to claim 1 is a signal detection method for searching a part similar to a previously registered target signal from a stored signal, wherein the target characteristic amount is derived from the target signal. A calculation process, a window of interest is set for the accumulated signal, and a storage feature calculation process of deriving a feature sequence from a signal in the window of interest, and a process by the accumulation feature calculation are repeatedly performed while shifting the window of interest. Each derived feature value series is classified based on a predefined distance, and a stored feature value classification process of determining a representative feature value sequence of the classification, and selection for the distance defined in the stored feature value classification process is performed. A threshold setting step of calculating a threshold value from a search threshold value which is a threshold value set in advance with respect to the degree of similarity between feature amounts; An accumulation feature selection step of selecting a feature sequence included in a classification having a representative feature sequence whose similarity with the feature sequence derived in the process satisfies a condition derived from the selection threshold; A similarity calculation step of calculating a similarity between the feature quantity series selected in the quantity selection step and the feature quantity series derived in the target feature quantity calculation step; and a similarity calculation step based on the calculation result of the similarity calculation step. A similarity determination for determining whether or not the target signal is present at the corresponding portion of the stored signal by comparing the similarity with the target signal at several points of the stored signal and a search threshold value And a process.
[0005]
According to a second aspect of the present invention, in the signal detection method according to the first aspect, a skip width of the window of interest is further calculated based on the similarity calculated in the similarity calculation process, and only the skip width is calculated. Having a skip width calculating step of moving the window of interest, repeating the processing from the similarity calculating step to the skip width calculating step, and calculating the similarity with the target signal for some points of the accumulated signal; By comparing the similarity with a search threshold, it is characterized in that it is determined whether or not the target signal is present at the relevant portion of the accumulated signal.
[0006]
According to a third aspect of the present invention, in the signal detection method according to any one of the first and second aspects, in the target feature amount calculating step and the accumulated feature amount calculating step, a histogram is created for a feature amount series. A distance is calculated based on the histogram in the accumulated feature classifying process, and a similarity is calculated based on the histogram in the accumulated feature selecting process and the similarity calculating process.
[0007]
According to a fourth aspect of the present invention, in the signal detection method according to the third aspect, the accumulated feature amount selecting step and the similarity calculating step calculate a similarity based on a histogram overlap rate.
[0008]
According to a fifth aspect of the present invention, in the signal detection method according to any one of the first to fourth aspects, the accumulated feature amount classification step classifies each feature amount series based on an L2 distance (Euclidean distance). It is characterized by.
[0009]
According to a sixth aspect of the present invention, there is provided a signal detecting apparatus for searching a part similar to a pre-registered target signal from a stored signal, wherein a target characteristic amount calculating unit for deriving a characteristic amount sequence from the target signal; A window is set, and each of the feature amount sequences derived by repeatedly performing the processing by the accumulated feature amount calculating means for deriving a feature amount sequence from the signal in the window of interest while shifting the window of interest. Are classified based on a predefined distance, and a storage feature classifying means for determining a representative feature sequence of the classification; and a selection threshold for the distance defined by the storage feature classifying means, Selection threshold value setting means for calculating from a search threshold value which is a threshold value set in advance for similarity, and a feature value derived by the target feature value calculation means for classification derived by the accumulated feature value classification means. A storage feature amount selection unit that selects a feature amount sequence included in a classification having a representative feature amount sequence that satisfies a condition derived from the selection threshold, and a similarity degree with a column; Similarity calculating means for calculating the similarity between the calculated feature quantity series and the feature quantity series derived by the target feature quantity calculating means; and an accumulated signal obtained based on the calculation result by the similarity calculating means means. Having similarity determining means for determining whether or not the target signal is present at the relevant portion of the stored signal by comparing the similarity with the target signal for some of the positions and the search threshold. It is characterized by.
[0010]
According to a seventh aspect of the present invention, in the signal detection device according to the sixth aspect, a skip width of the window of interest is further calculated based on the similarity calculated by the similarity calculating means, and only the skip width is calculated. A skip width calculating means for moving the window of interest;
By repeating the processing from the similarity calculation means to the skip width calculation means, for some places of the accumulated signal, calculate the similarity with the target signal, and by comparing the similarity and the search threshold, It is characterized in that it is determined whether or not the target signal is present at the location of the stored signal.
[0011]
The invention according to claim 8 is a computer-readable recording medium in which a signal detection program used for a signal detection device that searches for a portion similar to a target signal registered in advance from an accumulated signal is recorded. A first step of deriving a feature sequence from the target signal, a second step of setting a window of interest in the accumulated signal, and deriving a feature sequence from a signal within the window of interest, and a process in the second step. A third step of classifying each feature amount sequence derived by repeating the process while shifting the attention window based on a predefined distance, and determining a representative feature amount sequence of the classification; A fourth step of calculating a selection threshold value for the distance defined by the search threshold value, which is a threshold value set in advance with respect to the similarity between feature values, The feature amount sequence included in the classification having the representative feature amount sequence such that the similarity with the feature amount sequence derived in the first step satisfies the condition derived from the selection threshold for the classification derived in step A fifth step of calculating the similarity between the feature amount sequence selected in the fifth step and the feature amount sequence derived in the first step; and By comparing the similarity with the target signal for some points of the stored signal obtained based on the calculation result in the step 6 and the search threshold, the target signal is stored in the relevant part of the stored signal. A signal detection program for causing a computer to execute the seventh step of determining whether or not the signal exists is recorded.
[0012]
According to a ninth aspect of the present invention, in the recording medium according to the eighth aspect, the signal detection program further calculates a skip width of the window of interest based on the similarity calculated in the sixth step. Has an eighth step of moving the window of interest by the skip width, and repeats the processing from the sixth step to the eighth step to determine the similarity between the target signal and some points of the accumulated signal. By calculating the similarity and the search threshold, a signal detection program to be executed by a computer to determine whether or not the target signal is present at the corresponding portion of the accumulated signal is recorded. Features.
[0013]
According to a tenth aspect of the present invention, there is provided a signal detection program used in a signal detection device that searches for a portion similar to a target signal registered in advance from an accumulated signal, wherein the signal detection program extracts a feature amount sequence from the target signal. Repeating the first step of deriving, setting a window of interest in the accumulated signal, and deriving a feature sequence from the signals in the window of interest, and the processing of the second step while shifting the window of interest. A third step of classifying each of the feature quantity sequences derived in the above based on a predefined distance, and determining a representative feature quantity series of the classification, and a selection threshold for the distance defined in the third step Is calculated from a search threshold value that is a preset threshold value for the similarity between feature amounts, and the first step is performed for the classification derived in the third step. A fifth step of selecting a feature amount sequence included in a classification having a representative feature amount sequence whose similarity with the feature amount sequence derived in the step satisfies a condition derived from the selection threshold; A sixth step of calculating a similarity between the feature amount sequence selected in the step and the feature amount sequence derived in the first step, and a result obtained based on a calculation result in the sixth step; A seventh step of determining whether or not the target signal is present at the relevant position of the stored signal by comparing the similarity between the target signal and the target signal at several positions of the stored signal with a search threshold. It is characterized by being executed by a computer.
[0014]
The invention according to claim 11 is the signal detection program according to claim 10, wherein the signal detection program further calculates a skip width of the window of interest based on the similarity calculated in the sixth step. An eighth step of moving the window of interest by the skip width is provided, and the processing from the sixth step to the eighth step is repeated so that some points of the accumulated signal are similar to the target signal. The degree is calculated, and the computer is executed to determine whether or not the target signal exists at the corresponding position in the accumulated signal by comparing the similarity with the search threshold.
[0015]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. In the present invention, various signals to be processed can be used. Here, an acoustic signal is used as an example of the signal to be processed.
FIG. 1 is a block diagram illustrating a configuration of a signal detection device according to an embodiment of the present invention.
[0016]
The signal detection apparatus according to the present embodiment is a signal detection method for searching a part similar to a pre-registered target signal from a stored signal. , The accumulated feature amount calculating step of deriving a feature amount sequence from the signal in the noticed window, and the processing by the accumulated feature amount calculating step are repeatedly performed while shifting the attention window. A series is classified based on a predefined distance, and a stored feature classifying step of determining a representative feature series of the classification, and a selection threshold value for the distance defined in the stored feature class classifying step, are performed by comparing feature quantities with each other. A selection threshold value calculation step of calculating from a search threshold value which is a threshold value set in advance with respect to the similarity degree, and a classification derived in the accumulated feature quantity classification step, which is derived in the target feature quantity calculation step. An accumulation feature amount selection step of selecting a feature amount series included in a classification having a representative feature amount series whose similarity with the collection amount series satisfies a condition derived from a selection threshold; And a similarity calculation step of calculating a similarity between the feature quantity series obtained in the target feature quantity calculation step and a feature quantity series derived in the target feature quantity calculation step, and a stored signal obtained based on the calculation result by the similarity calculation step. Having a similarity determination step of determining whether or not the target signal is present at the relevant portion of the accumulated signal by comparing the similarity with the target signal for some points of the search signal and the search threshold. An apparatus for implementing a signal detection method characterized by the following.
[0017]
In FIG. 1, a signal detecting apparatus according to the present embodiment includes a target feature amount calculating unit 1, an accumulated feature amount calculating unit 2, an accumulated feature amount classifying unit 3, a selection threshold setting unit 4, a stored feature amount selecting unit. Means 5, a similarity calculating means 6, a skip width calculating means 7, and a similarity determining means 8; Then, a portion in the accumulated signal where the similarity with the target signal is equal to or larger than a predetermined value (this is referred to as a search threshold) θ is output.
[0018]
In the above configuration, the target feature value calculating means 1 has a function of deriving a feature value sequence from a target signal.
Further, the accumulated feature value calculating means 2 has a function of setting a window of interest (point of interest) in the stored signal and deriving a feature value sequence from the stored signal in the set window of interest.
The accumulated feature classifying means 3 divides each feature series obtained by repeating the feature extraction while shifting the window of interest set in the accumulated signal by the accumulated feature computing means 2 based on a predefined distance. And has a function of determining a representative feature amount series of the classification.
[0019]
The selection threshold setting unit 4 has a function of calculating a selection threshold for the distance defined by the accumulated feature classifying unit 3 from a search threshold that is a threshold set in advance for the similarity between feature amounts.
The accumulated feature amount selecting unit 5 determines that the similarity between the classification output from the accumulated feature amount classifying unit 3 and the feature amount series output from the target feature amount calculating unit 1 satisfies a condition derived from the selection threshold. It has a function of selecting a feature amount sequence included in a classification having a representative feature amount sequence.
The similarity calculation means 6 has a function of calculating the similarity between the feature quantity sequence output from the accumulated feature quantity selection means 5 and the feature quantity sequence output from the target feature quantity calculation means 1.
[0020]
The skip width calculating means 7 has a function of calculating the skip width of the window of interest based on the similarity calculated by the similarity calculating means, and moving the window of interest by the skip width.
Further, the similarity determination means 8 compares the similarity between the target signal with respect to some points of the stored signal obtained based on the calculation result by the similarity calculation means 6 and the search threshold, It has a function of determining whether or not the target signal is present at the location of the stored signal.
[0021]
Next, the operation of the signal detection device having the above configuration will be specifically described with reference to the flowchart shown in FIG. In the following, for the sake of simplicity, a case will be described where the length of the window of interest is the same as the length of the target signal. The same applies to the case where the window of interest is temporally divided.
In FIG. 2, the target feature value calculating means 1 first reads a given target signal (step 11).
[0022]
Next, feature extraction is performed on the read target signal (step 12). In the present embodiment, since a spectral feature is used as a feature, feature extraction can be performed by, for example, a band-pass filter. For example, when it is desired to search for a sound signal of about 15 seconds from a broadcast signal of a television or radio, a good result can be obtained by setting the specific feature extraction as follows. That is, using seven band-pass filters, their center frequencies are set at equal intervals on a logarithmic axis, and while moving the analysis window having a time length of about 60 milliseconds by 10 milliseconds, The average value of the square of the output of the band-pass filter is calculated, and a set of the obtained seven values is used as a seven-dimensional feature vector. In this case, one feature vector is obtained every 10 milliseconds.
[0023]
Subsequently, a feature vector histogram Ho is created from the time series of the feature vectors (step 13). The histogram Ho is created by encoding a feature vector using vector quantization. For example, if the number of code words for vector quantization is 512, the number of bins (intervals) of the entire histogram is 512, and each feature vector is classified into any one of the 512 bins. . Next, the accumulated feature amount calculation means 2 first reads the accumulated sound signal (step 14).
[0024]
Next, the accumulated feature value calculating means 2 sets a skip window of interest for the read accumulated acoustic signal. First, an attention window having the same length as the target signal given to the target feature value calculating means 1 is set. At the start of the process, the window of interest is set at the head of the accumulated signal. In the process of the process, the process proceeds while shifting the window of interest sequentially by one feature vector.
Subsequently, the accumulated feature calculating means 2 performs feature extraction on the acoustic signal in the window of interest (step 15). The feature extraction performs the same operation as performed in the target feature amount calculation means 1.
Further, a histogram of the feature vectors is created from the time series of the feature vectors in the window of interest (step 16). The method of creating the histogram is performed by the same method as that performed by the target feature amount calculating means 1.
[0025]
In the accumulated feature amount classifying means 3, first, in the accumulated feature amount calculating means 2, a series of feature vector histograms repeatedly output while shifting the window of interest is read.
The histogram output from the accumulated feature calculating means 2 is defined as Hs. Here, S represents that the histogram is created from the feature vector of the accumulated signal. Next, the accumulated feature classifying means 3 classifies each histogram of the histogram series Hs according to, for example, a distance defined below (step 17). That is, the distance d between the two histograms Hi and Hj_ij ⁽²⁾ , Using the Euclidean distance.
(Equation 1)

Here, L is the total number of bins of the histogram (512 in the above example), and hil and hjl represent the number (frequency) of feature vectors included in the l-th bin of Hi and Hj, respectively.
Also, the distance d_ij ⁽²⁾2 at the upper right of the mark indicates that the distance scale is a secondary distance (Euclidean distance).
[0026]
The histograms are classified by regarding each histogram as a vector having the same number of dimensions as the number of bins and encoding the vector using vector quantization. For example, if the number of code words for vector quantization is 512, the histogram is classified into one of 512 sets (this is called a cluster in the present application). Then, the cluster is represented by a histogram that is the barycenter of the histogram belonging to each cluster (referred to as a barycenter histogram).
At this time, the cluster is set so that the sum of the distances between the histograms belonging to the cluster and the barycenter histogram is minimized, and the distance between the clusters belonging to the cluster and the barycenter histogram of the cluster to which the cluster belongs is determined by any other cluster. It is configured to be smaller than the distance from the barycenter histogram.
[0027]
The selection threshold setting unit 4 determines a selection threshold θ2 bar from the search threshold θ1 (step 18).
Here, the search threshold / value indicates the lower limit of the similarity between the histogram on the target signal side and the histogram on the stored signal side, for example, when it is determined that the target signal exists at a certain point in the stored signal.
The similarity Sos between the histogram Ho of the target signal and the histogram Hs of the accumulated signal is defined as follows.
(Equation 2)

Here, D represents the total frequency of the histogram (total number of feature vectors derived from one reference signal), and o indicates that the histogram is created from the feature vector of the target signal.
[0028]
Further, the selection threshold indicates the upper limit of the distance between the cluster on the target signal side and the cluster when selecting a cluster that may include the histogram on the accumulation signal side corresponding to the signal to be searched.
The principle of determining the selection threshold θ2 bar from the search threshold θ1 will be described below. The similarity Sos defined by the equation (2) can be expressed using a primary distance as follows.
(Equation 3)

However, it is the distance between Ho and Hs based on the L1 distance. Note that dos⁽¹⁾Is
(Equation 4)

It is.
[0029]
Here, since the similarity defined by the equation (2) is based on the L1 distance, Sos⁽¹⁾It will be written as From the relationship that holds between the L1 distance and the L2 distance,
(Equation 5)

Is obtained. From equations (1), (3), and (4),
(Equation 6)

It becomes.
However, Sos⁽²⁾Is a similarity based on the L2 distance. Also, Sos⁽²⁾Is
(Equation 7)

Can be defined as
[0030]
From the nature of the histogram,
(Equation 8)

Holds, the similarity defined by Expression (7) takes a value from 0 to 1. The histogram selected by the selection threshold θ2 bar, ie,
(Equation 9)

Is the histogram detected by the search threshold θ1, that is, the histogram on the accumulation signal side where
(Equation 10)

Since it is necessary to include all the histograms on the accumulation signal side where
(Equation 11)

That is,
(Equation 12)

It should just be. Thus, the selection threshold θ2 bar is given by the search threshold θ1 as follows.
[0031]
(Equation 13)

In the accumulated feature amount selecting means 5, first, the histogram Ho of the feature vector output from the target feature amount calculating means 1, the classification (cluster) of the histogram Hs output from the accumulated feature amount classifying means 3, and the selection threshold setting means Then, the selection threshold value output from step 4 is read (step 19).
Next, the distance between the read-in histogram Ho on the target signal side and the barycenter histogram of each cluster on the accumulation signal side is calculated (step 20). The calculation of the distance is performed by the same operation as performed by the accumulated feature classifying means 3.
[0032]
Subsequently, based on the calculated distance, a cluster that may include a histogram corresponding to the signal to be searched is selected (step 21). This principle will be described below.
FIG. 2 shows a state where a histogram space (512 dimensions in the above example) is cut out on a plane on which three points of R, C1, and C2 ride. Here, R is the histogram of the feature vector output from the target feature amount calculating means 1, C1 is the centroid histogram of the cluster to which the histogram R belongs, C2 is the centroid histogram of some other cluster, d_R1, D_R2, D₁₂Are R and C as defined in equation (1), respectively.₁Distance between R and C₂And C₁And C₂Indicates the distance to
[0033]
Here, if it is necessary to detect the location of the accumulation signal corresponding to the histogram whose distance from the histogram R is within d, the inside of a hypersphere (circle in FIG. 3) having a radius d centered on R will be described. A certain histogram corresponds to the location of the stored signal to be detected. The radius of the hypersphere centered on R is d in FIG._θWhen it gets bigger, C₂There is a possibility that the histogram corresponding to the location of the accumulated signal to be detected is included in the histogram belonging to the cluster represented by. Therefore, the selection threshold θ2 bar is d_θWhen it gets better, C₂Select a cluster represented by.
[0034]
d_θIs determined as follows. From FIG. 3, the following equation holds.
[Equation 14]

Therefore, from equation (14),
(Equation 15)

It becomes.
Therefore, from equations (15) and (13),
(Equation 16)

Holds when C₂All the histograms belonging to the cluster represented by are selected.
[0035]
This procedure is performed for all the clusters except the cluster to which the histogram R belongs, and the finally selected histograms are arranged in chronological order, and the temporally continuous histograms are connected to form a time series. I do. The obtained series of each histogram is a partial series of the histogram time series output from the accumulated feature calculating means 2. This set of histogram sequences is output (step 22).
The similarity calculation means 6 first reads a histogram of the feature vector output from the target feature calculation means 1 and a set of histogram time series output from the storage feature selection means 5, and reads the target signal and the accumulated signal. The degree of similarity with the histogram is calculated (step 24).
[0036]
At the start of the processing, the histogram of the accumulated signal is extracted from the top of the first element of the histogram time series set. I will proceed. The shift amount in the time direction is given by the skip width calculating means 7 for calculating a skip width for skipping the window of interest (step 25).
The similarity calculating means 6 outputs the value of the similarity to the skip width calculating means 7 and the similarity determining means 8.
The similarity determination means determines whether the value of the similarity exceeds θ1 in all time divisions when the value of the similarity exceeds the search threshold θ1 (when the window of interest is divided in the time direction). Means that the target signal was present in the stored signal, the current position in the time series with respect to the stored signal is output as a signal detection result (

steps

26, 27, 28). .
[0037]
Next, an operation experiment example of the signal detection device to which the present invention is applied will be described. In order to confirm the effect of the present invention, an acoustic signal of 24 hours is used as a stored signal, and a search is performed on 12 randomly selected reference signals (15 seconds), and a comparison in which the similarity is equal to or smaller than the search threshold is performed. Regarding the number of times, the ratio in the case where the present invention is not applied is compared with the case where the present invention is applied (in the present application, this is called a collation frequency reduction ratio). Regarding the time required for processing excluding the accumulated feature amount selection means 5, that is, the time required only for search, what ratio is the case where the present invention is not applied compared to the case where the present invention is applied (search time Reduction ratio).
[0038]
Search parameters are: sampling frequency = 11.025 kHz, number of band filters = 7, analysis window length of frequency analysis = 60 ms, analysis window shift = 10 ms, histogram bin number = 512, no time window division, cluster number = 512 And
Further, the search threshold value θ1 was changed from 0.5 to 1 in increments of 0.05, and the selection threshold value θ2 was determined from the search threshold value θ1 based on Expression (13).
The result of this experiment is shown in 43 and FIG.
FIG. 4 shows the average of the search times and the search time reduction ratio when the search threshold is changed. For example, at the search threshold θ1 = 0.85, the average search time was 0.39 seconds in the conventional method, 0.03 seconds in the proposed method (the present invention), and the search time reduction ratio was 13.0.
[0039]
FIG. 5 shows the average of the number of times of matching and the reduction ratio of times of matching when the search threshold is changed. For example, at the search threshold θ1 = 0.85, the average of the number of collation times was 11,427 in the conventional method, 1126 in the proposed method (the present invention), and the reduction ratio of the number of collation was 10.2.
According to the present embodiment, a storage feature amount selection unit, a selection threshold value setting unit, and a storage feature amount classification unit for selecting a location of a storage signal similar to a target signal in advance are provided, so that unnecessary matching calculation can be omitted while achieving the purpose. By performing a search for a signal to be performed, a higher-speed signal search can be performed with a smaller number of matching calculations than in a known method.
[0040]
Note that the first step of deriving a feature value sequence from the target signal, the second step of setting a window of interest in the accumulated signal and deriving the feature value sequence from the signal within the window of interest, and the second step A third step of classifying each feature amount sequence derived by repeating the process while shifting the window of interest based on a predefined distance, and determining a representative feature amount sequence of the classification; A fourth step of calculating a selection threshold value for the distance defined in the step from a search threshold value which is a threshold value set in advance with respect to the similarity between the feature amounts; and, for the classification derived in the third step, the first step. A fifth step of selecting a feature quantity sequence included in a classification having a representative feature quantity sequence whose similarity with the feature quantity sequence derived in the step satisfies a condition derived from the selection threshold; A sixth step of calculating a similarity between the feature amount sequence selected in the step and the feature amount sequence derived in the first step, and a result obtained based on a calculation result in the sixth step; A seventh step of determining whether or not the target signal is present at the relevant position of the stored signal by comparing the similarity between the target signal and the target signal at several positions of the stored signal with a search threshold. A signal detection program characterized by being executed by a computer is recorded on a computer-readable recording medium, and the signal detection program recorded on the recording medium is read into a computer system and executed, whereby the stored signal is registered in advance. The function of the signal detection device that searches for a portion similar to the target signal described above may be realized.
[0041]
The signal detection program further includes an eighth step of calculating a skip width of the window of interest based on the similarity calculated in the sixth step, and moving the window of interest by the skip width. By repeating the processing from the sixth step to the eighth step, the similarity with the target signal is calculated for some points of the accumulated signal, and the similarity is compared with a search threshold. Alternatively, the computer may be caused to determine whether or not the target signal is present at the location of the stored signal.
[0042]
Here, the “computer system” includes an OS and hardware such as peripheral devices. The “computer-readable recording medium” refers to a general-purpose medium such as a floppy disk, a magneto-optical disk, a ROM, a CD-ROM, and a storage device such as a hard disk built in a computer system. In addition, the “computer-readable recording medium” refers to a communication line for transmitting a program via a network such as the Internet or a communication line such as a telephone line. (A transmission medium or a transmission wave), in which case a program that holds a program for a certain period of time, such as a volatile memory in a computer system serving as a server or a client, is also included.
[0043]
Further, the above-mentioned program may be for realizing a part of the above-mentioned functions, and may be a program for realizing the above-mentioned functions in combination with a program already recorded in a computer system, a so-called difference file ( Difference program).
[0044]
【The invention's effect】
As described above, according to the present invention, a signal detection device that searches for a part similar to a previously registered target signal from an accumulated signal, and a target characteristic amount calculating unit that derives a characteristic amount sequence from the target signal, A window of interest is set in the accumulated signal, and a process of the accumulated feature amount calculating means for deriving a feature amount sequence from the signal in the window of interest and the process of the accumulated feature amount calculating means are repeatedly performed while shifting the window of interest. Each feature amount series is classified based on a predefined distance, and a stored feature amount classifying unit that determines a representative feature amount series of the classification, and a selection threshold for the distance defined by the stored feature amount classifying unit, Selection threshold value setting means for calculating from a search threshold value which is a threshold value set in advance with respect to the similarity between feature quantities, and a classification derived by the accumulated feature quantity classification means, wherein the target feature quantity calculation means Storage feature amount selection means for selecting a feature amount sequence included in a classification having a representative feature amount sequence such that the degree of similarity with the extracted feature amount sequence satisfies a condition derived from the selection threshold; Means for calculating the similarity between the feature amount sequence selected by the means and the feature amount sequence derived by the target feature amount calculating means; and A similarity determining unit that determines whether the target signal is present at the corresponding position of the stored signal by comparing the similarity with the target signal at some positions of the stored signal and a search threshold value; Therefore, it is possible to perform faster signal detection by efficiently reducing the search range while guaranteeing the same accuracy as compared with the related art.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a signal detection device according to an embodiment of the present invention.
FIG. 2 is a flowchart showing the operation of the signal detection device according to the embodiment of the present invention shown in FIG.
FIG. 3 is an explanatory diagram showing a principle of selecting a histogram of an accumulated signal in a signal detection device for an audio signal to which the present invention is applied.
FIG. 4 is a diagram showing a result of measuring a search time in a case where the present invention is applied, among experimental results obtained by a signal detection apparatus for an audio signal to which the present invention is applied.
FIG. 5 is a diagram illustrating a result of measuring the number of times of collation in a case where the present invention is applied, among experimental results obtained by a signal detection apparatus for an audio signal to which the present invention is applied.
[Explanation of symbols]
1 Target signal feature value calculation means
2 Accumulated signal feature value calculation means
3 Accumulated signal feature classifier
4 Selection threshold setting means
5 Accumulated feature selection means
6 Similarity calculation means
7 Skip width calculation means
8 Similarity determination means

Claims

A signal detection method for searching for a part similar to a target signal registered in advance from an accumulated signal,
A target feature value calculation process for deriving a feature value sequence from the target signal,
Setting a window of interest in the accumulated signal, and calculating an accumulated feature amount to derive a feature amount sequence from the signal in the window of interest;
Each of the feature value sequences derived by repeatedly performing the process of the accumulated feature value calculation process while shifting the window of interest is classified based on a predefined distance, and a storage process of determining a representative feature value sequence of the classification is performed. Feature quantity classification process,
A selection threshold value setting step of calculating a selection threshold value for the distance defined in the accumulated feature value classification process from a search threshold value which is a threshold value set in advance with respect to the similarity between feature values;
Regarding the classification derived in the accumulated feature classification process, the similarity with the feature sequence derived in the target feature calculation process is classified into a classification having a representative feature sequence such that the condition derived from the selection threshold is satisfied. An accumulated feature quantity selection process of selecting a feature quantity series to be included,
A similarity calculation step of calculating a similarity between the feature quantity sequence selected in the accumulated feature quantity selection step and the feature quantity sequence derived in the target feature quantity calculation step,
The target signal is obtained by comparing the similarity with the target signal for some points of the storage signal, which is obtained based on the calculation result of the similarity calculation process, and a search threshold. A similarity determination process for determining whether or not it exists at a location;
A signal detection method comprising:

Further, based on the similarity calculated in the similarity calculation step, a skip width of the window of interest is calculated, and a skip width calculation step of moving the window of interest by the skip width is included.
By repeating the process from the similarity calculation step to the skip width calculation step, for some points of the accumulated signal, calculate the similarity with the target signal, by comparing the similarity and the search threshold, The signal detection method according to claim 1, wherein it is determined whether or not the target signal exists at the corresponding portion of the stored signal.

In the target feature amount calculation step and the accumulated feature amount calculation step, a histogram is created for the feature amount series, and a distance is calculated based on the histogram in the accumulated feature amount classification step. 3. The signal detection method according to claim 1, wherein a similarity is calculated based on the histogram in the similarity calculation process.

4. The signal detection method according to claim 3, wherein the accumulation feature amount selecting step and the similarity calculating step calculate a similarity based on a histogram overlap rate.

The signal detection method according to any one of claims 1 to 4, wherein in the accumulated feature classifying step, each feature series is classified based on an L2 distance (Euclidean distance).

A signal detection device that searches for a portion similar to a target signal registered in advance from an accumulated signal,
An objective feature amount calculating means for deriving a feature amount sequence from the objective signal,
A storage feature calculating means for setting a window of interest in the accumulated signal and deriving a feature sequence from the signal in the window of interest;
Each feature amount sequence derived by repeatedly performing the processing by the accumulated feature amount calculating means while shifting the window of interest is classified based on a predefined distance, and a representative feature amount sequence of the classification is determined. An accumulation feature classifying unit;
A selection threshold setting unit that calculates a selection threshold for the distance defined by the accumulated feature classifying unit from a search threshold that is a threshold preset for the similarity between feature amounts;
A classification having a representative feature quantity sequence such that the degree of similarity with the feature quantity sequence derived by the target feature quantity calculation means satisfies the condition derived from the selection threshold, for the classification derived by the accumulated feature quantity classification means. Stored feature amount selecting means for selecting a feature amount series included in
A similarity calculating unit that calculates a similarity between the feature amount series selected by the accumulated feature amount selecting unit and the feature amount series derived by the target feature amount calculating unit;
The target signal is obtained by comparing the similarity with the target signal for some points of the storage signal obtained based on the calculation result by the similarity calculation means, and a search threshold value, so that the target signal is Similarity determination means for determining whether or not it exists at the location;
A signal detection device comprising:

Further, based on the similarity calculated by the similarity calculating means, a skip width of the window of interest is calculated, and a skip width calculating means for moving the window of interest by the skip width is provided.
By repeating the processing from the similarity calculation means to the skip width calculation means, for some places of the accumulated signal, calculate the similarity with the target signal, and by comparing the similarity and the search threshold, 7. The signal detection device according to claim 6, wherein it is determined whether or not the target signal is present at the position of the accumulation signal.

From the stored signal, in a computer-readable recording medium in which a signal detection program used for a signal detection device that searches for a part similar to a previously registered target signal is recorded,
The signal detection program,
A first step of deriving a feature sequence from the target signal;
A second step of setting a window of interest in the accumulated signal and deriving a feature sequence from the signal in the window of interest;
The third step of classifying each feature amount sequence derived by repeatedly performing the process in the second step while shifting the window of interest based on a predefined distance, and determining a representative feature amount sequence of the classification. Steps and
A fourth step of calculating a selection threshold value for the distance defined in the third step from a search threshold value which is a threshold value set in advance with respect to the similarity between feature values;
The classification derived in the third step is included in a classification having a representative characteristic amount sequence that satisfies a condition derived from a selection threshold, with a similarity to the characteristic amount sequence derived in the first step. A fifth step of selecting a feature amount sequence;
A sixth step of calculating a similarity between the feature amount sequence selected in the fifth step and the feature amount sequence derived in the first step,
By comparing the similarity with the target signal for some points of the stored signal obtained based on the calculation result in the sixth step and a search threshold, the target signal is obtained by comparing the similarity of the stored signal with the target signal. A seventh step of determining if it is present at the location;
Recording medium for recording a signal detection program for causing a computer to execute the program.

The signal detection program,
Further, an eighth step of calculating a skip width of the window of interest based on the similarity calculated in the sixth step, and moving the window of interest by the skip width,
By repeating the processing from the sixth step to the eighth step, calculating the similarity between the target signal and some points of the accumulated signal, and comparing the similarity with a search threshold, 9. The recording medium according to claim 8, wherein a signal detection program for causing a computer to execute a determination as to whether or not the target signal is present at the location of the stored signal is recorded.

A signal detection program used in a signal detection device that searches for a portion similar to a target signal registered in advance from an accumulated signal,
The signal detection program includes:
A first step of deriving a feature sequence from the target signal;
A second step of setting a window of interest in the accumulated signal and deriving a feature sequence from the signal in the window of interest;
The third step of classifying each feature amount sequence derived by repeatedly performing the process in the second step while shifting the window of interest based on a predefined distance, and determining a representative feature amount sequence of the classification. Steps and
A fourth step of calculating a selection threshold value for the distance defined in the third step from a search threshold value which is a threshold value set in advance with respect to the similarity between feature values;
The classification derived in the third step is included in a classification having a representative characteristic amount sequence that satisfies a condition derived from a selection threshold, with a similarity to the characteristic amount sequence derived in the first step. A fifth step of selecting a feature amount sequence;
A sixth step of calculating a similarity between the feature amount sequence selected in the fifth step and the feature amount sequence derived in the first step,
By comparing the similarity with the target signal for some points of the stored signal obtained based on the calculation result in the sixth step and a search threshold, the target signal is obtained by comparing the similarity of the stored signal with the target signal. A seventh step of determining if it is present at the location;
A signal detection program for causing a computer to execute the following.

The signal detection program,
Further, an eighth step of calculating a skip width of the window of interest based on the similarity calculated in the sixth step, and moving the window of interest by the skip width,
By repeating the processing from the sixth step to the eighth step, calculating the similarity between the target signal and some points of the accumulated signal, and comparing the similarity with a search threshold, 11. The signal detection program according to claim 10, wherein the program is caused to be executed by a computer so as to determine whether or not the target signal is present at the corresponding portion of the stored signal.