JP4459940B2 - Signal search method, apparatus, program and recording medium thereof - Google Patents
Signal search method, apparatus, program and recording medium thereof Download PDFInfo
- Publication number
- JP4459940B2 JP4459940B2 JP2006271323A JP2006271323A JP4459940B2 JP 4459940 B2 JP4459940 B2 JP 4459940B2 JP 2006271323 A JP2006271323 A JP 2006271323A JP 2006271323 A JP2006271323 A JP 2006271323A JP 4459940 B2 JP4459940 B2 JP 4459940B2
- Authority
- JP
- Japan
- Prior art keywords
- feature
- database
- signal
- query
- distance
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
Description
本発明は、膨大な信号系列の中から、あらかじめ登録した信号と類似した信号の場所を探し出すのに適した信号検索方法、装置、プログラムとその記録媒体に関する。 The present invention relates to a signal search method, apparatus, program, and recording medium suitable for searching for a location of a signal similar to a signal registered in advance from an enormous signal sequence.
従来、入力された信号と類似している信号の場所を、膨大な信号系列の中から探し出す信号検索方法において、類似した信号の場所を高速に探し出す高速信号検索方法が知られている(例えば、特許文献1、特許文献2)。
また、上述のような信号検索方法において、信号の特徴圧縮を行ない特徴照合1回当たりの計算コストを削減する方法として、時系列信号の連続性を利用した区分線形写像により、効率的に特徴の次元を削減する手法が知られている(例えば、非特許文献3)。この方法は信号の性質によらず信号を一律に等分割することにより写像を構成している。さらに、信号の性質に応じて分割の長さを変化させることが知られている(例えば非特許文献1、非特許文献2)。
Conventionally, in a signal search method for searching a location of a signal similar to an input signal from a huge signal sequence, a high-speed signal search method for searching for a location of a similar signal at high speed is known (for example,
Further, in the signal search method as described above, as a method for reducing the calculation cost per feature matching by compressing the feature of the signal, the feature search is efficiently performed by the piecewise linear mapping using the continuity of the time series signal. A technique for reducing the dimension is known (for example, Non-Patent Document 3). In this method, a map is formed by equally dividing a signal regardless of the nature of the signal. Furthermore, it is known to change the division length according to the nature of the signal (for example, Non-Patent
また、上述のような信号検索方法において、不要な照合を局所的に省略する方法として、照合に用いる特徴であるヒストグラムの性質を利用し、未照合時点の距離の下限値を計算し、予め定められた閾値を上回らない時点での照合を省略する、時系列アクティブ探索方法が知られている(例えば、特許文献1、特許文献2)。
また、上述の信号検索方法に用いられる信号圧縮の技術として、音響信号から抽出した特徴系列の次元を削減し、少量の記憶装置で特徴系列を保持したり、信号同士の類似性の判定を高速に行うことを可能とする信号圧縮技術が知られている。この信号圧縮技術は、放送の音響信号の中から特定の楽曲が放映された時刻を検出するなど、信号系列の中から予め登録した信号と類似した信号の場所を探し出すといった上述の信号検索方法に用いられ、その高速な実行を可能とする。そして、このような技術に用いられる具体的な信号圧縮方法に関しては、予め用意した原信号を分割して圧縮する信号圧縮方法が知られている(例えば、非特許文献3)。
In addition, as a signal compression technique used in the signal search method described above, the dimension of feature sequences extracted from acoustic signals can be reduced, feature sequences can be retained in a small amount of storage devices, and similarity between signals can be determined at high speed. There is known a signal compression technique that can be performed in a short time. This signal compression technique is based on the signal search method described above, such as detecting the location of a signal similar to a pre-registered signal from a signal sequence, such as detecting the time when a specific piece of music was broadcast from a broadcast sound signal. Used to enable its high speed execution. As a specific signal compression method used in such a technique, a signal compression method for dividing and compressing an original signal prepared in advance is known (for example, Non-Patent Document 3).
ここで、上述の特許文献1や特許文献2の高速信号検索方法では、極めて膨大な信号系列に対しては、十分短い時間内に類似した信号を探し出すことが出来ないという問題や、ヒストグラム以外の特徴に対して適応することが出来ないという問題がある。
また、上述の非特許文献1や非特許文献2のような信号圧縮方法では、さらに高い圧縮率で信号圧縮を行なうことが可能となるものの、最適な分割を決定する処理に膨大な処理が必要になるという問題がある。
また、上述の非特許文献3に記載の信号圧縮方法では、信号の性質によらず原信号を一律に等分割することにより部分信号を構成しているが、信号の性質に応じて分割の長さを変化させることも可能である。従って、それによりさらに良い圧縮率で信号圧縮を行うことが可能となるものの、この方法では、圧縮を行う関数を決定する処理に膨大な処理が必要になるという問題があった。
Here, with the high-speed signal search methods of
In addition, in the signal compression methods such as Non-Patent
Further, in the signal compression method described in
本発明は、上記課題に鑑みてなされたもので、膨大な事前処理を回避しながら、従来の信号圧縮方法よりも信号の性質に適応した信号圧縮の処理を行うと共に、より少ない情報量で信号系列を表現することが可能な信号圧縮方法、装置、そのプログラムと記録媒体、及び該信号圧縮方法を用いた信号検索方法であって、従来よりもより計算効率の良く、また同一の検索結果を保証し、さらに検索に必要となる一時記憶容量を極端に増大させることなく、より高速な信号検索を行なうことができる、信号検索方法、装置、そのプログラムと記録媒体を提供することを目的とする。 The present invention has been made in view of the above problems, and performs signal compression processing that is more suitable for signal characteristics than conventional signal compression methods while avoiding enormous pre-processing, and reduces the amount of information required for signal processing. A signal compression method and apparatus capable of expressing a sequence, its program and recording medium, and a signal search method using the signal compression method, which are more computationally efficient than the prior art and provide the same search results An object of the present invention is to provide a signal search method, apparatus, program thereof, and recording medium capable of performing a higher-speed signal search without guaranteeing and further extremely increasing the temporary storage capacity required for the search. .
本発明は、上述の課題を解決すべくなされたもので、予め登録した時系列信号であるデータベース信号(蓄積信号)から目的とする時系列信号であるクエリ信号(参照信号)に類似した部分を探し出す信号検索方法であって、クエリ信号から多次元ベクトルとして表現されるクエリ特徴を導くクエリ特徴抽出過程(クエリ特徴抽出過程)と、データベース信号に注目窓を設定し、注目窓内の信号から、多次元ベクトルとして表現されるデータベース特徴を導き、これらの処理を、注目窓をずらしながら繰り返し行うことで多次元ベクトルの系列として表現されるデータベース特徴系列を導くデータベース特徴抽出過程(蓄積特徴抽出過程)と、前記データベース特徴抽出過程で導かれたデータベース特徴系列を系列の順序に従って区分することで、データベース部分特徴系列を導くデータベース特徴区分過程と、前記データベース特徴区分過程で導かれた各データベース部分特徴系列(例えば、実施の形態における、部分ヒストグラム特徴系列(部分特徴系列)、段落0177)から、そのデータベース部分特徴系列を代表する特徴であるデータベース代表特徴を抽出し、前記データベース特徴抽出過程で導かれたデータベース特徴系列より少ない数の特徴で構成されるデータベース代表特徴系列を導くデータベース特徴間引き過程と、前記データベース特徴区分過程で導かれた各データベース部分特徴系列中の各要素と前記データベース特徴間引き過程で導かれたデータベース代表特徴との距離の最大値dmaxを計算し、前記データベース代表特徴から前記距離の最大値dmaxの範囲内の領域であるデータベース特徴存在領域を導く特徴領域抽出過程と、前記クエリ特徴抽出過程で導かれたクエリ特徴と、前記データベース特徴間引き過程で導かれたデータベース代表特徴系列に含まれるある特定位置のデータベース代表特徴との距離を計算する特徴照合過程と、前記特徴照合過程で計算された距離から、前記特徴領域抽出過程で導かれた距離の最大値dmaxを差し引いたものを補正後の距離値とする距離補正過程と、前記距離補正過程で導かれた補正距離値と、その補正距離値に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する信号検出判定過程とを有し、前記特徴照合過程から前記信号検出判定過程による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定することを特徴とする。 The present invention has been made to solve the above-described problem, and a portion similar to a query signal (reference signal) that is a target time-series signal from a database signal (stored signal) that is a time-series signal registered in advance is provided. A signal search method for finding a query feature extraction process (query feature extraction process) for deriving a query feature expressed as a multidimensional vector from a query signal, and setting an attention window in a database signal, and from a signal in the attention window, A database feature extraction process that derives a database feature expressed as a multidimensional vector by deriving a database feature expressed as a multidimensional vector and repeating these processes while shifting the window of interest (accumulated feature extraction process) And dividing the database feature sequence derived in the database feature extraction process according to the sequence order. From the database feature classification process for deriving the database partial feature series and each database partial feature series derived from the database feature classification process (for example, the partial histogram feature series (partial feature series) in the embodiment, paragraph 0177). A database feature thinning process that extracts a database representative feature, which is a feature representing the database partial feature series, and derives a database representative feature sequence composed of fewer features than the database feature sequence derived in the database feature extraction process And calculating a maximum value dmax of the distance between each element in each database partial feature series derived in the database feature classification process and the database representative feature derived in the database feature thinning process, from the database representative feature Within the maximum distance dmax A database representative of a specific position included in the database representative feature sequence derived from the database feature feature sequence derived from the feature extraction process, the query feature derived from the query feature extraction process, and the database feature decimation process A feature matching process for calculating the distance to the feature, and a distance obtained by subtracting the maximum distance dmax derived in the feature region extraction process from the distance calculated in the feature matching process as a corrected distance value Whether the query signal is present in the corresponding part of the database signal by comparing the correction process, the correction distance value derived in the distance correction process, and the search threshold that is a threshold corresponding to the correction distance value A signal detection determination process for determining the processing from the feature matching process to the signal detection determination process in the database representative feature sequence It repeats while shifting the position, calculates the distance from the query signal for several locations in the database signal, and determines whether the query signal is present at that location in the database signal.
本発明によれば、従来の信号検索方法と比較して、同一の検索結果を保証し、かつ検索に必要となる記憶容量をほとんど増加させることなく、不要な照合を局所的に省略することで、より高速な検索を行なうことを可能とする。 According to the present invention, compared to the conventional signal search method, the same search result is guaranteed, and unnecessary collation is omitted locally without substantially increasing the storage capacity required for the search. This makes it possible to perform a faster search.
また、本発明は、上述の信号検索方法の、前記データベース特徴間引き過程において、前記データベース特徴区分過程で導かれたデータベース特徴系列の先頭のデータベース特徴をデータベース代表特徴とすることを特徴とする。 Further, the present invention is characterized in that, in the signal search method described above, in the database feature thinning-out process, the database feature at the head of the database feature series derived in the database feature classification process is used as a database representative feature.
また、本発明は、上述の信号検索方法の、前記データベース特徴間引き過程において、前記データベース特徴区分過程で導かれたデータベース特徴系列内のデータベース特徴の重心をデータベース代表特徴とすることを特徴とする。 Further, the present invention is characterized in that, in the above-described signal search method, the centroid of the database feature in the database feature sequence derived in the database feature classification process is used as the database representative feature in the database feature thinning process.
また、本発明は、上述の信号検索方法の、前記データベース特徴区分過程において、前記データベース特徴抽出過程で導かれたデータベース特徴系列を予め定められた長さで等分割することを特徴とする。 Further, the present invention is characterized in that the database feature series derived in the database feature extraction process is equally divided by a predetermined length in the database feature classification process of the signal search method described above.
また、本発明は、上述の信号検索方法の、前記データベース特徴区分過程において、前記特徴領域抽出過程で導かれるデータベース特徴存在領域が予め定められた最大領域より小さくなるように、前記データベース特徴抽出過程で導かれたデータベース特徴系列を分割することを特徴とする。 Further, the present invention provides the database feature extraction step of the signal search method described above so that the database feature existing region derived in the feature region extraction step is smaller than a predetermined maximum region in the database feature classification step. The database feature sequence derived in (2) is divided.
また、本発明は、上述の信号検索方法の、前記データベース特徴抽出過程で導かれたデータベース特徴系列を、系列の順序に従って分割することにより、データベース特徴系列よりも短い長さの部分系列であるデータベース特徴セグメントを抽出するセグメント抽出過程と、前記セグメント抽出過程で得られた各データベース特徴セグメントから,前記特徴よりも低次元の特徴を算出するための写像を決定する圧縮写像決定過程と、前記セグメント抽出過程で得られた各データベース特徴セグメントに対応する前記圧縮写像決定過程で得られた射影変換を、該データベース特徴セグメントに含まれる各データ特徴に対して行うことにより、該データベース圧縮特徴に対応する圧縮特徴であるデータベース圧縮特徴の系列であるデータベース圧縮特徴系列を導くデータベース特徴圧縮過程と(信号圧縮過程)、前記クエリ特徴抽出過程で得られたクエリ特徴に対し、前記圧縮写像決定過程で得られた射影変換を行うことにより、該クエリ特徴に対する圧縮特徴であるクエリ圧縮特徴を抽出するクエリ特徴圧縮過程(クエリ特徴圧縮過程)とを有し、前記データベース特徴間引き過程において、前記データベース特徴圧縮過程で導かれたデータベース圧縮特徴系列を入力としてデータベース代表特徴系列を導き、前記特徴照合過程において、クエリ特徴圧縮過程で導かれたクエリ圧縮特徴をクエリ特徴の代わりに用いて照合を行い、さらに、特徴照合過程から信号検出判定過程による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定することを特徴とする。 In addition, the present invention provides a database that is a partial sequence having a shorter length than the database feature sequence by dividing the database feature sequence derived in the database feature extraction process of the signal search method described above according to the sequence order. A segment extraction process for extracting feature segments, a compression map determination process for determining a map for calculating a feature of a lower dimension than the features from each database feature segment obtained in the segment extraction process, and the segment extraction The projection corresponding to each database feature segment obtained in the process is subjected to the projective transformation obtained in the compression mapping determination step for each data feature included in the database feature segment, so that the compression corresponding to the database compression feature is performed. Database pressure that is a series of database compression features A database feature compression process for deriving a feature sequence (signal compression process), and a query feature obtained in the query feature extraction process is subjected to projective transformation obtained in the compression mapping determination process to compress the query feature. A query feature compression process (query feature compression process) for extracting a query compression feature that is a feature, and in the database feature thinning-out process, a database compression feature sequence derived in the database feature compression process is used as an input to represent a database representative feature A series is derived, and in the feature matching process, the query compression feature derived in the query feature compression process is used for matching instead of the query feature, and further, processing from the feature matching process to the signal detection determination process is performed. Repeat some of the database signals by shifting the position in the series. For the portion, the distance between the query signal is calculated, and the query signal, and determines whether present in that portion of the database signals.
本発明によれば、インデックスを付与する特徴の数量を大幅に削減することで、より少ない記憶容量で検索を行なうことが出来る。 According to the present invention, it is possible to perform a search with a smaller storage capacity by greatly reducing the number of features to be indexed.
また、本発明は、上述の信号検索方法の、前記データベース特徴圧縮過程は、前記セグメント抽出過程で得られたデータベース特徴セグメントに含まれる各データベース特徴を、該データベース特徴セグメントに対応する前記圧縮写像決定過程で得られた射影変換によって写像するデータベース特徴写像過程と、前記データベース特徴写像過程で導かれた写像後の各データベース特徴について、対応する前記データベース特徴との距離を計算し、これをデータベース射影距離とするデータベース射影距離計算過程と、前記データベース特徴写像過程で導かれた写像後の各データベース特徴と、その写像後のデータベース特徴に対応して前記データベース射影距離計算過程で導かれたデータベース射影距離とを対にして、データベース圧縮特徴を構成するデータベース圧縮特徴構成過程とを有し、前記クエリ特徴圧縮過程は、前記クエリ特徴抽出過程で得られたクエリ特徴を、前記圧縮写像決定過程で得られた射影変換によって写像するクエリ特徴写像過程と、前記クエリ特徴写像過程で導かれた写像後の各クエリ特徴について、前記クエリ特徴との距離を計算し、これをクエリ射影距離とするクエリ射影距離計算過程と、前記クエリ特徴写像過程で導かれた写像後の各クエリ特徴と、その写像後のクエリ特徴に対応して前記クエリ射影距離計算過程で導かれたクエリ射影距離とを対にして、クエリ圧縮特徴を構成するクエリ圧縮特徴構成過程と、を有することを特徴とする。 Further, the present invention provides the above-described signal search method, wherein the database feature compression step determines each database feature included in the database feature segment obtained in the segment extraction step, and determines the compression mapping corresponding to the database feature segment. The distance between the database feature mapping process mapped by the projective transformation obtained in the process and each database feature after the mapping derived in the database feature mapping process is calculated from the corresponding database feature. A database projection distance calculation process, each database feature after mapping derived in the database feature mapping process, and a database projection distance derived in the database projection distance calculation process corresponding to the database feature after the mapping, Database compression features A query feature mapping process in which the query feature compression process maps the query feature obtained in the query feature extraction process by a projective transformation obtained in the compression map determination process. For each query feature after mapping derived in the query feature mapping process, a distance from the query feature is calculated, and this is used as a query projection distance, and derived in the query feature mapping process. A query compression feature constituting step of constructing a query compression feature by pairing each query feature after mapping with the query projection distance derived in the query projection distance calculation step corresponding to the query feature after mapping It is characterized by having.
また、本発明は、上述の信号検索方法の、前記信号検出判定過程でクエリ信号が存在すると判定されたデータベース信号中の当該箇所について、その当該箇所に対応する、前記データベース特徴抽出過程で導かれたデータベース特徴系列中のデータベース特徴と、前記クエリ特徴抽出過程で導かれたクエリ特徴との距離を計算する距離再計算過程と、前記距離再計算過程で導かれた距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する信号検出再判定過程とを有し、前記特徴照合過程、距離補正過程、信号検出判定過程、信号再計算過程及び信号検出再判定過程による処理を、データベース圧縮特徴系列もしくはデータベース特徴系列の中の位置をずらしながら繰り返して、データベース圧縮特徴系列もしくはデータベース特徴系列のいくつかの箇所について、クエリ信号特徴もしくはクエリ特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定することを特徴とする。 In addition, the present invention is derived in the database feature extraction process corresponding to the location in the database signal in which the query signal is determined to be present in the signal detection determination step in the signal search method described above. The distance recalculation process for calculating the distance between the database feature in the database feature sequence and the query feature derived in the query feature extraction process, and the distance derived in the distance recalculation process and the search threshold are compared. A signal detection / re-determination process for re-determining whether the query signal is present at the location of the database signal, the feature matching process, distance correction process, signal detection / determination process, signal re-calculation process, and Repeat the process of the signal detection redetermination process while shifting the position in the database compressed feature series or database feature series, Calculating the distance from a query signal feature or query feature for several locations in a database compressed feature sequence or database feature sequence and determining whether the query signal is present at that location in the database signal .
また、本発明は、上述の信号検索方法の、前記データベース特徴抽出過程で導かれたデータベース特徴系列を構成する各データベース特徴を、予め定義された距離尺度を基準として分類し、各分類について、その分類に含まれるデータベース特徴を代表する特徴である分類代表特徴を決定するデータベース特徴分類過程と、前記データベース特徴分類過程で定義された距離尺度に対する選択閾値を、予め定められた探索閾値を基準として計算する選択閾値設定過程と、前記データベース特徴分類過程で導かれた分類のうち、該分類に対応する分類代表特徴と、前記クエリ特徴抽出過程で導かれたクエリ特徴との距離が、前記選択閾値設定過程で計算された選択閾値と、該クエリ特徴を前記データベース特徴分類過程と同様の方法により分類した際に所属する分類に対応する分類代表特徴とから導かれる条件を満たすような代表特徴を持つ分類を検出し、該分類に含まれるデータベース特徴を選択するデータベース特徴選択過程と、を有し、前記特徴照合過程において、前記データベース特徴選択過程において選択されたデータベース特徴もしくは該データベース特徴に対応する前記データベース特徴圧縮過程で導かれたデータベース圧縮特徴についてのみ、前記クエリ特徴抽出過程で導かれたクエリ特徴もしくは該クエリ特徴に対応する前記クエリ特徴圧縮過程で導かれたクエリ特徴との距離を計算することを特徴とする。 In addition, the present invention classifies each database feature constituting the database feature sequence derived in the database feature extraction process of the above-described signal search method with reference to a predefined distance measure, A database feature classification process for determining a classification representative feature, which is a feature representing a database feature included in the classification, and a selection threshold for the distance measure defined in the database feature classification process is calculated based on a predetermined search threshold. Among the classifications derived in the selection threshold setting process and the database feature classification process, the distance between the classification representative feature corresponding to the classification and the query feature derived in the query feature extraction process is the selection threshold setting. The selection threshold calculated in the process and the query feature are classified by the same method as the database feature classification process. A database feature selection step of detecting a category having a representative feature that satisfies a condition derived from the category representative feature corresponding to the class to which the user belongs, and selecting a database feature included in the category, and In the feature matching process, only the database feature selected in the database feature selection process or the database compressed feature derived in the database feature compression process corresponding to the database feature is the query feature derived in the query feature extraction process or A distance from a query feature derived in the query feature compression process corresponding to the query feature is calculated.
また、本発明は、上述の信号検索方法の、前記データベース特徴分類過程は、距離尺度をユークリッド距離とした所定のベクトル量子化方法により分類することを特徴とする。 Further, the present invention is characterized in that the database feature classification step of the signal search method described above is classified by a predetermined vector quantization method using a distance measure as an Euclidean distance.
また、本発明は、上述の信号検索方法の、前記特徴照合過程は、距離尺度をマンハッタン距離もしくはユークリッド距離のいずれかとして距離を計算することを特徴とする。 Further, the present invention is characterized in that, in the above-described signal search method, the feature matching process calculates a distance using a distance scale as either a Manhattan distance or a Euclidean distance.
また、本発明は、上述の信号検索方法の、前記データベース射影距離計算過程及び前記クエリ射影距離計算過程は、距離尺度をマンハッタン距離もしくはユークリッド距離のいずれかとしてデータベース射影距離を計算することを特徴とする。 The database projection distance calculation process and the query projection distance calculation process of the signal search method described above may calculate the database projection distance using a distance scale as either a Manhattan distance or an Euclidean distance. To do.
また、本発明は、上述の信号検索方法の、前記距離再計算過程は、距離尺度をマンハッタン距離もしくはユークリッド距離のいずれかとして距離を計算することを特徴とする。 Further, the present invention is characterized in that the distance recalculation process of the signal search method described above calculates a distance using a distance scale as either a Manhattan distance or a Euclidean distance.
また、本発明は、上述の信号検索方法の、前記クエリ特徴抽出過程および前記データベース特徴抽出過程は、クエリ信号もしくはデータベース信号から所定の方法で抽出した多次元ベクトルを予め定めた方法で分類して、分類毎の度数分布表であるヒストグラムを作成し、該ヒストグラムをクエリ特徴もしくはデータベース特徴として出力することを特徴とする。 According to the present invention, in the signal search method described above, the query feature extraction process and the database feature extraction process classify a multidimensional vector extracted from a query signal or database signal by a predetermined method according to a predetermined method. A histogram that is a frequency distribution table for each classification is generated, and the histogram is output as a query feature or a database feature.
また、本発明は、上述の信号検索方法の、前記距離補正過程で計算された距離について、該距離を基準としてデータベース代表特徴系列の参照箇所のスキップ幅を計算し、そのスキップ幅の分だけデータベース代表特徴系列の参照箇所を移動するスキップ幅計算過程とを有し、前記特徴照合過程、距離補正過程、信号検出判定過程及びスキップ幅計算過程による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース特徴系列のいくつかの箇所について、クエリ特徴もしくはクエリ圧縮特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定することを特徴とする。 According to the present invention, for the distance calculated in the distance correction process of the signal search method described above, the skip width of the reference location of the database representative feature series is calculated based on the distance, and the database corresponding to the skip width is calculated. A skip width calculation process for moving the reference location of the representative feature series, and the processing in the feature matching process, distance correction process, signal detection determination process, and skip width calculation process is performed while shifting the position in the database representative feature series. Repeatedly, the distance from the query feature or the query compression feature is calculated for several locations of the database feature series, and it is determined whether the query signal is present at the location of the database signal.
また、本発明は、予め登録した時系列信号であるデータベース信号から目的とする時系列信号であるクエリ信号に類似した部分を探し出す信号検索装置であって、クエリ信号から多次元ベクトルとして表現されるクエリ特徴を導くクエリ特徴抽出手段と、データベース信号に注目窓を設定し、注目窓内の信号から、多次元ベクトルとして表現されるデータベース特徴を導き、これらの処理を、注目窓をずらしながら繰り返し行うことで多次元ベクトルの系列として表現されるデータベース特徴系列を導くデータベース特徴抽出手段と、前記データベース特徴抽出手段で導かれたデータベース特徴系列を系列の順序に従って区分することで、データベース部分特徴系列を導くデータベース特徴区分手段と、前記データベース特徴区分手段で導かれた各データベース部分特徴系列から、そのデータベース部分特徴系列を代表する特徴であるデータベース代表特徴を抽出し、前記データベース特徴抽出手段で導かれたデータベース特徴系列より少ない数の特徴で構成されるデータベース代表特徴系列を導くデータベース特徴間引き手段と、前記データベース特徴区分手段で導かれた各データベース部分特徴系列中の各要素と前記データベース特徴間引き手段で導かれたデータベース代表特徴との距離の最大値dmaxを計算し、前記データベース代表特徴から前記距離の最大値dmaxの範囲内の領域であるデータベース特徴存在領域を導く特徴領域抽出手段と、前記クエリ特徴抽出手段で導かれたクエリ特徴と、前記データベース特徴間引き手段で導かれたデータベース代表特徴系列に含まれるある特定位置のデータベース代表特徴との距離を計算する特徴照合手段と、前記特徴照合手段で計算された距離から、前記特徴領域抽出手段で導かれた距離の最大値dmaxを差し引いたものを補正後の距離値とする距離補正手段と、前記距離補正手段で導かれた補正距離値と、その補正距離値に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する信号検出判定手段とを有し、前記特徴照合手段から前記信号検出判定手段による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定することを特徴とする。 In addition, the present invention is a signal search device that searches for a portion similar to a query signal that is a target time series signal from a database signal that is a time series signal registered in advance , and is expressed as a multidimensional vector from the query signal. Query feature extraction means for deriving query features and a window of interest in the database signal, database features expressed as multidimensional vectors are derived from the signal in the window of interest, and these processes are repeated while shifting the window of interest A database feature extraction unit for deriving a database feature sequence expressed as a sequence of multidimensional vectors, and a database feature sequence derived from the database feature extraction unit according to the sequence order to derive a database partial feature sequence Database feature classifying means and guided by the database feature classifying means A database representative feature is extracted from each database partial feature series, which is a feature representing the database partial feature series, and is composed of fewer features than the database feature series derived by the database feature extraction means. Database feature decimation means for deriving a sequence, and calculating a maximum distance dmax between each element in each database partial feature sequence derived by the database feature classifying means and the database representative feature derived by the database feature decimation means. A feature region extracting unit for deriving a database feature existing region that is a region within the range of the maximum value dmax of the distance from the database representative feature, a query feature derived by the query feature extracting unit, and the database feature thinning unit Is included in the derived database representative feature series A feature matching unit that calculates the distance from the database representative feature at a specific position, and a value obtained by subtracting the maximum distance dmax derived by the feature region extracting unit from the distance calculated by the feature matching unit By comparing the distance correction means to be the distance value, the correction distance value derived by the distance correction means, and the search threshold value that is a threshold value corresponding to the correction distance value, the query signal becomes the corresponding part of the database signal. A signal detection determination means for determining whether or not the data exists in the database, and repeats the processing by the signal detection determination means from the feature collating means while shifting the position in the database representative feature series, Calculating the distance to the query signal for the location and determining whether the query signal is present at the location of the database signal .
また、本発明は、上述した信号検索装置の、前記データベース特徴抽出手段で導かれたデータベース特徴系列を、系列の順序に従って分割することにより、データベース特徴系列よりも短い長さの部分系列であるデータベース特徴セグメントを抽出するセグメント抽出手段と、前記セグメント抽出手段で得られた各データベース特徴セグメントから,前記特徴よりも低次元の特徴を算出するための写像を決定する圧縮写像決定手段と、前記セグメント抽出手段で得られた各データベース特徴セグメントに対応する前記圧縮写像決定手段で得られた射影変換を、該データベース特徴セグメントに含まれる各データ特徴に対して行うことにより、該データベース圧縮特徴に対応する圧縮特徴であるデータベース圧縮特徴の系列であるデータベース圧縮特徴系列を導くデータベース特徴圧縮手段と、前記クエリ特徴抽出手段で得られたクエリ特徴に対し、前記圧縮写像決定手段で得られた射影変換を行うことにより、該クエリ特徴に対する圧縮特徴であるクエリ圧縮特徴を抽出するクエリ特徴圧縮手段とを有し、前記データベース特徴間引き手段において、前記データベース特徴圧縮手段で導かれたデータベース圧縮特徴系列を入力としてデータベース代表特徴系列を導き、前記特徴照合手段において、クエリ特徴圧縮手段で導かれたクエリ圧縮特徴をクエリ特徴の代わりに用いて照合を行い、さらに、特徴照合手段から信号検出判定手段による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定することを特徴とする。 Further, the present invention provides a database that is a partial sequence having a shorter length than the database feature sequence by dividing the database feature sequence derived by the database feature extraction unit of the signal search device described above according to the sequence order. Segment extraction means for extracting feature segments, compression map determination means for determining a map for calculating features of a lower dimension than the features from each database feature segment obtained by the segment extraction means, and the segment extraction The projection corresponding to each database feature segment obtained by the means is subjected to the projective transformation obtained by the compression map determining means for each data feature included in the database feature segment, thereby compressing the database feature. A database that is a series of database compression features A database feature compression means for deriving a reduced feature sequence, and a query that is a compression feature for the query feature by performing projective transformation obtained by the compression mapping determination means on the query feature obtained by the query feature extraction means Query feature compression means for extracting compressed features, wherein the database feature thinning means derives a database representative feature series using the database compressed feature series derived by the database feature compression means as an input, and the feature matching means comprises: The query compression feature derived by the query feature compression unit is used instead of the query feature to perform collation, and further, the processing by the signal detection determination unit from the feature collation unit is repeated while shifting the position in the database representative feature series, For some parts of the database signal, the distance from the query signal Calculated by the query signal, and determines whether present in that portion of the database signals.
また、本発明は、上述した信号検索装置の、前記信号検出判定手段でクエリ信号が存在すると判定されたデータベース信号中の当該箇所について、その当該箇所に対応する、前記データベース特徴抽出手段で導かれたデータベース特徴系列中のデータベース特徴と、前記クエリ特徴抽出手段で導かれたクエリ特徴との距離を計算する距離再計算手段と、前記距離再計算手段で導かれた距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する信号検出再判定手段とを有し、前記特徴照合手段、距離補正手段、信号検出判定手段、信号再計算手段及び信号検出再判定手段による処理を、データベース圧縮特徴系列もしくはデータベース特徴系列の中の位置をずらしながら繰り返して、データベース圧縮特徴系列もしくはデータベース特徴系列のいくつかの箇所について、クエリ信号特徴もしくはクエリ特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定することを特徴とする。 Further, the present invention is directed to the database feature extraction unit corresponding to the location in the database signal in which the query signal is determined to be present by the signal detection determination unit of the signal search device described above. The distance recalculation means for calculating the distance between the database feature in the database feature series and the query feature derived by the query feature extraction means, and the distance derived by the distance recalculation means and the search threshold are compared. And a signal detection re-determination unit that re-determines whether or not the query signal exists at the location of the database signal, the feature matching unit, the distance correction unit, the signal detection determination unit, the signal re-calculation unit, Repeat the processing by the signal detection re-determination means while shifting the position in the database compressed feature series or database feature series. Calculating a distance from a query signal feature or a query feature for a database compression feature sequence or several locations of a database feature sequence and determining whether the query signal is present at the location of the database signal .
また、本発明は、上述した信号検索装置の、前記データベース特徴抽出手段で導かれたデータベース特徴系列を構成する各データベース特徴を、予め定義された距離尺度を基準として分類し、各分類について、その分類に含まれるデータベース特徴を代表する特徴である分類代表特徴を決定するデータベース特徴分類手段と、前記データベース特徴分類手段で定義された距離尺度に対する選択閾値を、予め定められた探索閾値を基準として計算する選択閾値設定手段と、前記データベース特徴分類手段で導かれた分類のうち、該分類に対応する分類代表特徴と、前記クエリ特徴抽出手段で導かれたクエリ特徴との距離が、前記選択閾値設定手段で計算された選択閾値と、該クエリ特徴を前記データベース特徴分類手段と同様の方法により分類した際に所属する分類に対応する分類代表特徴とから導かれる条件を満たすような代表特徴を持つ分類を検出し、該分類に含まれるデータベース特徴を選択するデータベース特徴選択手段と、を有し、前記特徴照合手段において、前記データベース特徴選択手段において選択されたデータベース特徴もしくは該データベース特徴に対応する前記データベース特徴圧縮手段で導かれたデータベース圧縮特徴についてのみ、前記クエリ特徴抽出手段で導かれたクエリ特徴もしくは該クエリ特徴に対応する前記クエリ特徴圧縮手段で導かれたクエリ特徴との距離を計算することを特徴とする。 Further, the present invention classifies each database feature constituting the database feature series derived by the database feature extraction means of the signal search device described above with reference to a predefined distance measure, and for each classification, A database feature classifying unit that determines a classification representative feature that is a feature that represents a database feature included in the classification, and a selection threshold for the distance measure defined by the database feature classifying unit is calculated based on a predetermined search threshold. Among the classifications derived by the selection threshold setting means and the database feature classification means, the distance between the classification representative feature corresponding to the classification and the query feature derived by the query feature extraction means is the selection threshold setting. The selection threshold calculated by the means and the query feature are classified by the same method as the database feature classification means. Database feature selection means for detecting a category having a representative feature that satisfies a condition derived from the category representative feature corresponding to the category to which the user belongs, and selecting a database feature included in the category, and In the feature matching unit, only the database feature selected by the database feature selection unit or the database compression feature derived by the database feature compression unit corresponding to the database feature is the query feature derived by the query feature extraction unit. Alternatively, a distance from the query feature derived by the query feature compression means corresponding to the query feature is calculated.
また、本発明は、上述した信号検索装置の、前記距離補正手段で計算された距離について、該距離を基準としてデータベース代表特徴系列の参照箇所のスキップ幅を計算し、そのスキップ幅の分だけデータベース代表特徴系列の参照箇所を移動するスキップ幅計算手段とを有し、前記特徴照合手段、距離補正手段、信号検出判定手段及びスキップ幅計算手段による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース特徴系列のいくつかの箇所について、クエリ特徴もしくはクエリ圧縮特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定することを特徴とする。 Further, according to the present invention, with respect to the distance calculated by the distance correction means of the signal search device described above, the skip width of the reference location of the database representative feature series is calculated based on the distance, and the database corresponding to the skip width is calculated. Skip width calculation means for moving the reference location of the representative feature series, and the processing by the feature matching means, distance correction means, signal detection determination means, and skip width calculation means while shifting the position in the database representative feature series Repeatedly, the distance from the query feature or the query compression feature is calculated for several locations of the database feature series, and it is determined whether the query signal is present at the location of the database signal.
また、本発明は、予め登録した時系列信号であるデータベース信号から目的とする時系列信号であるクエリ信号に類似した部分を探し出す信号検索装置のコンピュータに実行させるプログラムであって、クエリ信号から多次元ベクトルとして表現されるクエリ特徴を導くクエリ特徴抽出処理と、データベース信号に注目窓を設定し、注目窓内の信号から、多次元ベクトルとして表現されるデータベース特徴を導き、これらの処理を、注目窓をずらしながら繰り返し行うことで多次元ベクトルの系列として表現されるデータベース特徴系列を導くデータベース特徴抽出処理と、前記データベース特徴抽出処理で導かれたデータベース特徴系列を系列の順序に従って区分することで、データベース部分特徴系列を導くデータベース特徴区分処理と、前記データベース特徴区分処理で導かれた各データベース部分特徴系列から、そのデータベース部分特徴系列を代表する特徴であるデータベース代表特徴を抽出し、前記データベース特徴抽出処理で導かれたデータベース特徴系列より少ない数の特徴で構成されるデータベース代表特徴系列を導くデータベース特徴間引き処理と、前記データベース特徴区分処理で導かれた各データベース部分特徴系列中の各要素と前記データベース特徴間引き処理で導かれたデータベース代表特徴との距離の最大値dmaxを計算し、前記データベース代表特徴から前記距離の最大値dmaxの範囲内の領域であるデータベース特徴存在領域を導く特徴領域抽出処理と、前記クエリ特徴抽出処理で導かれたクエリ特徴と、前記データベース特徴間引き処理で導かれたデータベース代表特徴系列に含まれるある特定位置のデータベース代表特徴との距離を計算する特徴照合処理と、前記特徴照合処理で計算された距離から、前記特徴領域抽出処理で導かれた距離の最大値dmaxを差し引いたものを補正後の距離値とする距離補正処理と、前記距離補正処理で導かれた補正距離値と、その補正距離値に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する信号検出判定処理とを有し、前記特徴照合処理から前記信号検出判定処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、をコンピュータに実行させるプログラムである。 The present invention also provides a program to be executed by a computer of a signal search apparatus that searches for a portion similar to a query signal that is a target time-series signal from a database signal that is a pre-registered time-series signal. Query feature extraction processing that derives query features expressed as a dimensional vector, and an attention window is set in the database signal, and database features expressed as multidimensional vectors are derived from the signals in the attention window, and these processing A database feature extraction process for deriving a database feature series expressed as a sequence of multidimensional vectors by repeatedly shifting the window, and a database feature series derived by the database feature extraction process are classified according to the sequence order, Database feature classification processing to derive database partial feature series A database representative feature, which is a feature representing the database partial feature series, is extracted from each database partial feature series derived by the database feature classification process, and is smaller in number than the database feature series derived by the database feature extraction process. and database features thinning processing for guiding the database representative feature sequence formed by features, the database representative feature said derived in the database feature classification process and each element in each database partial feature sequence derived by said database, wherein the thinning processing A feature region extraction process for calculating a maximum distance value dmax and deriving a database feature existing area that is an area within the range of the maximum distance value dmax from the database representative feature , and a query feature derived by the query feature extraction process And the data derived by the database feature thinning process. A feature matching process for calculating a distance from a database representative feature at a specific position included in the database representative feature series, and a maximum distance dmax derived by the feature region extraction process from the distance calculated by the feature matching process By comparing the distance correction process in which a value obtained by subtracting is corrected distance value, the corrected distance value derived by the distance correction process, and the search threshold value corresponding to the corrected distance value, the query A signal detection determination process for determining whether or not a signal is present at the location of the database signal, and repeating the process according to the signal detection determination process from the feature matching process while shifting the position in the database representative feature series Calculate the distance to the query signal for some parts of the database signal, and the query signal is present at that part of the database signal. And a program for causing a computer to execute the process of determining whether or not to determine whether or not to determine whether or not
また、本発明は、上述したプログラムに含まれる処理に加え、前記データベース特徴抽出処理で導かれたデータベース特徴系列を、系列の順序に従って分割することにより、データベース特徴系列よりも短い長さの部分系列であるデータベース特徴セグメントを抽出するセグメント抽出処理と、前記セグメント抽出処理で得られた各データベース特徴セグメントから,前記特徴よりも低次元の特徴を算出するための写像を決定する圧縮写像決定処理と、前記セグメント抽出処理で得られた各データベース特徴セグメントに対応する前記圧縮写像決定処理で得られた射影変換を、該データベース特徴セグメントに含まれる各データ特徴に対して行うことにより、該データベース圧縮特徴に対応する圧縮特徴であるデータベース圧縮特徴の系列であるデータベース圧縮特徴系列を導くデータベース特徴圧縮処理と、前記クエリ特徴抽出処理で得られたクエリ特徴に対し、前記圧縮写像決定処理で得られた射影変換を行うことにより、該クエリ特徴に対する圧縮特徴であるクエリ圧縮特徴を抽出するクエリ特徴圧縮処理と、前記データベース特徴間引き処理において、前記データベース特徴圧縮処理で導かれたデータベース圧縮特徴系列を入力としてデータベース代表特徴系列を導き、前記特徴照合処理において、クエリ特徴圧縮処理で導かれたクエリ圧縮特徴をクエリ特徴の代わりに用いて照合を行い、さらに、特徴照合処理から信号検出判定処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、をコンピュータに実行させるプログラムである。 In addition to the processing included in the above-described program, the present invention divides the database feature sequence derived by the database feature extraction processing according to the sequence order, so that a partial sequence having a shorter length than the database feature sequence is obtained. A segment extraction process for extracting a database feature segment, and a compression map determination process for determining a map for calculating a lower-dimensional feature than the feature from each database feature segment obtained by the segment extraction process; By performing projective transformation obtained by the compression mapping determination process corresponding to each database feature segment obtained by the segment extraction process on each data feature included in the database feature segment, the database compressed feature is obtained. The database compression feature series that is the corresponding compression feature A database feature compression process for deriving a database compression feature sequence and a query feature obtained by the compression map determination process on the query feature obtained by the query feature extraction process to obtain a compression feature for the query feature In the query feature compression processing for extracting a certain query compression feature, and in the database feature thinning-out processing, a database representative feature sequence is derived using the database compression feature sequence derived in the database feature compression processing as an input, and in the feature matching processing, a query The query compression feature derived by the feature compression processing is used instead of the query feature for matching, and further, the processing from the feature matching processing to the signal detection determination processing is repeated while shifting the position in the database representative feature series, and the database Query signal for some parts of the signal The distance is calculated and the query signal is a program for executing processing and, to a computer to determine whether present in that portion of the database signals.
また、本発明は、上述したプログラムに含まれる処理に加え、前記信号検出判定処理でクエリ信号が存在すると判定されたデータベース信号中の当該箇所について、その当該箇所に対応する、前記データベース特徴抽出処理で導かれたデータベース特徴系列中のデータベース特徴と、前記クエリ特徴抽出処理で導かれたクエリ特徴との距離を計算する距離再計算処理と、前記距離再計算処理で導かれた距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する信号検出再判定処理と、前記特徴照合処理、距離補正処理、信号検出判定処理、信号再計算処理及び信号検出再判定処理による処理を、データベース圧縮特徴系列もしくはデータベース特徴系列の中の位置をずらしながら繰り返して、データベース圧縮特徴系列もしくはデータベース特徴系列のいくつかの箇所について、クエリ信号特徴もしくはクエリ特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、をコンピュータに実行させるプログラムである。 In addition to the processing included in the above-described program, the present invention provides the database feature extraction processing corresponding to the location in the database signal that is determined by the signal detection determination processing to have a query signal. A distance recalculation process for calculating a distance between the database feature in the database feature sequence derived in step (a) and the query feature derived in the query feature extraction process, and a distance and a search threshold derived in the distance recalculation process. And a signal detection re-determination process for re-determining whether a query signal is present at the location of the database signal, the feature matching process, a distance correction process, a signal detection determination process, a signal re-calculation process, and Processing by signal detection redetermination processing while shifting the position in the database compressed feature series or database feature series In return, a process for calculating a query signal feature or a distance from a query feature for a database compression feature series or some part of a database feature series, and determining whether the query signal is present at that part of the database signal Is a program that causes a computer to execute.
また、本発明は、上述したプログラムに含まれる処理に加え、前記データベース特徴抽出処理で導かれたデータベース特徴系列を構成する各データベース特徴を、予め定義された距離尺度を基準として分類し、各分類について、その分類に含まれるデータベース特徴を代表する特徴である分類代表特徴を決定するデータベース特徴分類処理と、前記データベース特徴分類処理で定義された距離尺度に対する選択閾値を、予め定められた探索閾値を基準として計算する選択閾値設定処理と、前記データベース特徴分類処理で導かれた分類のうち、該分類に対応する分類代表特徴と、前記クエリ特徴抽出処理で導かれたクエリ特徴との距離が、前記選択閾値設定処理で計算された選択閾値と、該クエリ特徴を前記データベース特徴分類処理と同様の方法により分類した際に所属する分類に対応する分類代表特徴とから導かれる条件を満たすような代表特徴を持つ分類を検出し、該分類に含まれるデータベース特徴を選択するデータベース特徴選択処理と、を有し、前記特徴照合処理において、前記データベース特徴選択処理において選択されたデータベース特徴もしくは該データベース特徴に対応する前記データベース特徴圧縮処理で導かれたデータベース圧縮特徴についてのみ、前記クエリ特徴抽出処理で導かれたクエリ特徴もしくは該クエリ特徴に対応する前記クエリ特徴圧縮処理で導かれたクエリ特徴との距離を計算する処理とをコンピュータに実行させるプログラムである。 In addition to the processing included in the above-described program, the present invention classifies each database feature constituting the database feature series derived by the database feature extraction processing on the basis of a predefined distance measure. A database feature classification process for determining a classification representative feature that is a feature representing a database feature included in the classification, a selection threshold for the distance measure defined in the database feature classification process, and a predetermined search threshold Of the classification derived by the selection threshold setting process calculated as a reference and the database feature classification process, the distance between the classification representative feature corresponding to the classification and the query feature derived by the query feature extraction process is The selection threshold calculated in the selection threshold setting process and the query feature are the same as those in the database feature classification process A database feature selection process that detects a category having a representative feature that satisfies a condition derived from the category representative feature corresponding to the category to which the category belongs when classified by the method, and selects a database feature included in the category; In the feature matching process, only the database feature selected in the database feature selection process or the database compressed feature derived in the database feature compression process corresponding to the database feature is derived in the query feature extraction process. And a process for calculating a distance from the query feature derived by the query feature compression process corresponding to the query feature.
また、本発明は、上述したプログラムに含まれる処理に加え、前記距離補正処理で計算された距離について、該距離を基準としてデータベース代表特徴系列の参照箇所のスキップ幅を計算し、そのスキップ幅の分だけデータベース代表特徴系列の参照箇所を移動するスキップ幅計算処理と、前記特徴照合処理、距離補正処理、信号検出判定処理及びスキップ幅計算処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース特徴系列のいくつかの箇所について、クエリ特徴もしくはクエリ圧縮特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、をコンピュータに実行させるプログラムである。 In addition to the processing included in the above-described program, the present invention calculates the skip width of the reference location of the database representative feature series with respect to the distance calculated in the distance correction processing based on the distance. The processing of the skip width calculation process for moving the reference location of the database representative feature series by the amount, the feature matching process, the distance correction process, the signal detection determination process, and the skip width calculation process while shifting the position in the database representative feature series Repeatedly calculate the distance from the query feature or query compression feature for some parts of the database feature series and determine whether the query signal is present at that part of the database signal. It is a program to let you.
また、本発明は、予め登録した時系列信号であるデータベース信号から目的とする時系列信号であるクエリ信号に類似した部分を探し出す信号検索装置のコンピュータに実行させるプログラムを記録した、コンピュータ読み取り可能な記録媒体であって、クエリ信号から多次元ベクトルとして表現されるクエリ特徴を導くクエリ特徴抽出処理と、データベース信号に注目窓を設定し、注目窓内の信号から、多次元ベクトルとして表現されるデータベース特徴を導き、これらの処理を、注目窓をずらしながら繰り返し行うことで多次元ベクトルの系列として表現されるデータベース特徴系列を導くデータベース特徴抽出処理と、前記データベース特徴抽出処理で導かれたデータベース特徴系列を系列の順序に従って区分することで、データベース部分特徴系列を導くデータベース特徴区分処理と、前記データベース特徴区分処理で導かれた各データベース部分特徴系列から、そのデータベース部分特徴系列を代表する特徴であるデータベース代表特徴を抽出し、前記データベース特徴抽出処理で導かれたデータベース特徴系列より少ない数の特徴で構成されるデータベース代表特徴系列を導くデータベース特徴間引き処理と、前記データベース特徴区分処理で導かれた各データベース部分特徴系列中の各要素と前記データベース特徴間引き処理で導かれたデータベース代表特徴との距離の最大値dmaxを計算し、前記データベース代表特徴から前記距離の最大値dmaxの範囲内の領域であるデータベース特徴存在領域を導く特徴領域抽出処理と、前記クエリ特徴抽出処理で導かれたクエリ特徴と、前記データベース特徴間引き処理で導かれたデータベース代表特徴系列に含まれるある特定位置のデータベース代表特徴との距離を計算する特徴照合処理と、前記特徴照合処理で計算された距離から、前記特徴領域抽出処理で導かれた距離の最大値dmaxを差し引いたものを補正後の距離値とする距離補正処理と、前記距離補正処理で導かれた補正距離値と、その補正距離値に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する信号検出判定処理とを有し、前記特徴照合処理から前記信号検出判定処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体である。 The present invention also provides a computer-readable recording medium storing a program to be executed by a computer of a signal search apparatus that searches a portion similar to a query signal that is a target time-series signal from a database signal that is a pre-registered time-series signal. A database that is a recording medium and that extracts query features that are expressed as multidimensional vectors from a query signal, sets a window of attention in the database signal, and is expressed as a multidimensional vector from the signal in the window of attention A database feature extraction process for deriving a database feature sequence expressed as a multidimensional vector sequence by repeatedly performing these processes while shifting the attention window, and a database feature sequence derived by the database feature extraction process Database according to the order of the series A database feature segmentation process for deriving a partial feature sequence; and a database representative feature that is a feature representing the database partial feature sequence is extracted from each database partial feature sequence derived by the database feature segmentation process, and the database feature extraction process Database feature decimation process for deriving a database representative feature sequence composed of a smaller number of features than the database feature sequence derived in step 1, each element in each database partial feature sequence derived in the database feature classification process, and the database feature Calculating a maximum value dmax of the distance to the database representative feature derived by the thinning process, and a feature area extraction process for deriving a database feature existing area that is an area within the range of the maximum value dmax of the distance from the database representative feature ; Query feature derived by the query feature extraction process A feature matching process for calculating a distance from a database representative feature at a specific position included in the database representative feature series derived by the database feature thinning process, and the feature region from the distance calculated by the feature matching process A distance correction process in which a value obtained by subtracting the maximum distance value dmax derived by the extraction process is a corrected distance value, a correction distance value derived by the distance correction process, and a threshold value corresponding to the correction distance value A signal detection determination process for determining whether or not a query signal is present at the relevant part of the database signal by comparing with a certain search threshold, and the process by the signal detection determination process from the feature matching process, Repeatedly shifting the position in the database representative feature series to calculate the distance to the query signal at several points in the database signal, and A computer-readable recording medium having recorded thereon a program for causing a computer to execute a process for determining whether an error signal is present at a corresponding portion of a database signal.
また、本発明は、上述したプログラムに含まれる処理に加え、前記データベース特徴抽出処理で導かれたデータベース特徴系列を、系列の順序に従って分割することにより、データベース特徴系列よりも短い長さの部分系列であるデータベース特徴セグメントを抽出するセグメント抽出処理と、前記セグメント抽出処理で得られた各データベース特徴セグメントから,前記特徴よりも低次元の特徴を算出するための写像を決定する圧縮写像決定処理と、前記セグメント抽出処理で得られた各データベース特徴セグメントに対応する前記圧縮写像決定処理で得られた射影変換を、該データベース特徴セグメントに含まれる各データ特徴に対して行うことにより、該データベース圧縮特徴に対応する圧縮特徴であるデータベース圧縮特徴の系列であるデータベース圧縮特徴系列を導くデータベース特徴圧縮処理と、前記クエリ特徴抽出処理で得られたクエリ特徴に対し、前記圧縮写像決定処理で得られた射影変換を行うことにより、該クエリ特徴に対する圧縮特徴であるクエリ圧縮特徴を抽出するクエリ特徴圧縮処理と、前記データベース特徴間引き処理において、前記データベース特徴圧縮処理で導かれたデータベース圧縮特徴系列を入力としてデータベース代表特徴系列を導き、前記特徴照合処理において、クエリ特徴圧縮処理で導かれたクエリ圧縮特徴をクエリ特徴の代わりに用いて照合を行い、さらに、特徴照合処理から信号検出判定処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体である。 In addition to the processing included in the above-described program, the present invention divides the database feature sequence derived by the database feature extraction processing according to the sequence order, so that a partial sequence having a shorter length than the database feature sequence is obtained. A segment extraction process for extracting a database feature segment, and a compression map determination process for determining a map for calculating a lower-dimensional feature than the feature from each database feature segment obtained by the segment extraction process; By performing projective transformation obtained by the compression mapping determination process corresponding to each database feature segment obtained by the segment extraction process on each data feature included in the database feature segment, the database compressed feature is obtained. The database compression feature series that is the corresponding compression feature A database feature compression process for deriving a database compression feature sequence and a query feature obtained by the compression map determination process on the query feature obtained by the query feature extraction process to obtain a compression feature for the query feature In the query feature compression processing for extracting a certain query compression feature, and in the database feature thinning-out processing, a database representative feature sequence is derived using the database compression feature sequence derived in the database feature compression processing as an input, and in the feature matching processing, a query The query compression feature derived by the feature compression processing is used instead of the query feature for matching, and further, the processing from the feature matching processing to the signal detection determination processing is repeated while shifting the position in the database representative feature series, and the database Query signal for some parts of the signal A distance calculation, the query signal is a whether a computer readable recording medium recording a program for executing a process of determining, to a computer to present in that portion of the database signals.
また、本発明は、上述したプログラムに含まれる処理に加え、前記信号検出判定処理でクエリ信号が存在すると判定されたデータベース信号中の当該箇所について、その当該箇所に対応する、前記データベース特徴抽出処理で導かれたデータベース特徴系列中のデータベース特徴と、前記クエリ特徴抽出処理で導かれたクエリ特徴との距離を計算する距離再計算処理と、前記距離再計算処理で導かれた距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する信号検出再判定処理と、前記特徴照合処理、距離補正処理、信号検出判定処理、信号再計算処理及び信号検出再判定処理による処理を、データベース圧縮特徴系列もしくはデータベース特徴系列の中の位置をずらしながら繰り返して、データベース圧縮特徴系列もしくはデータベース特徴系列のいくつかの箇所について、クエリ信号特徴もしくはクエリ特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体である。 In addition to the processing included in the above-described program, the present invention provides the database feature extraction processing corresponding to the location in the database signal that is determined by the signal detection determination processing to have a query signal. A distance recalculation process for calculating a distance between the database feature in the database feature sequence derived in step (a) and the query feature derived in the query feature extraction process, and a distance and a search threshold derived in the distance recalculation process. And a signal detection re-determination process for re-determining whether a query signal is present at the location of the database signal, the feature matching process, a distance correction process, a signal detection determination process, a signal re-calculation process, and Processing by signal detection redetermination processing while shifting the position in the database compressed feature series or database feature series In return, a process for calculating a query signal feature or a distance from a query feature for a database compression feature series or some part of a database feature series, and determining whether the query signal is present at that part of the database signal And a computer-readable recording medium on which a program for causing a computer to execute is recorded.
また、本発明は、上述したプログラムに含まれる処理に加え、前記データベース特徴抽出処理で導かれたデータベース特徴系列を構成する各データベース特徴を、予め定義された距離尺度を基準として分類し、各分類について、その分類に含まれるデータベース特徴を代表する特徴である分類代表特徴を決定するデータベース特徴分類処理と、前記データベース特徴分類処理で定義された距離尺度に対する選択閾値を、予め定められた探索閾値を基準として計算する選択閾値設定処理と、前記データベース特徴分類処理で導かれた分類のうち、該分類に対応する分類代表特徴と、前記クエリ特徴抽出処理で導かれたクエリ特徴との距離が、前記選択閾値設定処理で計算された選択閾値と、該クエリ特徴を前記データベース特徴分類処理と同様の方法により分類した際に所属する分類に対応する分類代表特徴とから導かれる条件を満たすような代表特徴を持つ分類を検出し、該分類に含まれるデータベース特徴を選択するデータベース特徴選択処理と、前記特徴照合処理において、前記データベース特徴選択処理において選択されたデータベース特徴もしくは該データベース特徴に対応する前記データベース特徴圧縮処理で導かれたデータベース圧縮特徴についてのみ、前記クエリ特徴抽出処理で導かれたクエリ特徴もしくは該クエリ特徴に対応する前記クエリ特徴圧縮処理で導かれたクエリ特徴との距離を計算する処理と、をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体である。 In addition to the processing included in the above-described program, the present invention classifies each database feature constituting the database feature series derived by the database feature extraction processing on the basis of a predefined distance measure. A database feature classification process for determining a classification representative feature that is a feature representing a database feature included in the classification, a selection threshold for the distance measure defined in the database feature classification process, and a predetermined search threshold Of the classification derived by the selection threshold setting process calculated as a reference and the database feature classification process, the distance between the classification representative feature corresponding to the classification and the query feature derived by the query feature extraction process is The selection threshold calculated in the selection threshold setting process and the query feature are the same as those in the database feature classification process A database feature selection process for detecting a classification having a representative feature that satisfies a condition derived from the classification representative feature corresponding to the classification to which the classification belongs when classified by the method, and selecting a database feature included in the classification; In the feature matching process, only the database feature selected in the database feature selection process or the database compressed feature derived in the database feature compression process corresponding to the database feature, the query feature derived in the query feature extraction process or A computer-readable recording medium recording a program for causing a computer to execute a process of calculating a distance from a query feature derived by the query feature compression process corresponding to the query feature.
また、本発明は、上述したプログラムに含まれる処理に加え、前記距離補正処理で計算された距離について、該距離を基準としてデータベース代表特徴系列の参照箇所のスキップ幅を計算し、そのスキップ幅の分だけデータベース代表特徴系列の参照箇所を移動するスキップ幅計算処理と、前記特徴照合処理、距離補正処理、信号検出判定処理及びスキップ幅計算処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース特徴系列のいくつかの箇所について、クエリ特徴もしくはクエリ圧縮特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理とをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体である。 In addition to the processing included in the above-described program, the present invention calculates the skip width of the reference location of the database representative feature series with respect to the distance calculated in the distance correction processing based on the distance. The processing of the skip width calculation process for moving the reference location of the database representative feature series by the amount, the feature matching process, the distance correction process, the signal detection determination process, and the skip width calculation process while shifting the position in the database representative feature series Repeatedly calculate the distance from the query feature or the query compression feature for some parts of the database feature series, and let the computer execute the process of determining whether the query signal is present at that part of the database signal A computer-readable recording medium on which a program is recorded.
本発明によれば、部分信号構成過程と部分信号再構成過程とを備えた新たな信号圧縮方法あるいは信号圧縮装置を用いて、膨大な事前処理を回避しながら信号の性質に適応して部分信号の長さを変化させることにより、予め用意した原信号を従来より更に圧縮して、より少ない情報量で信号系列を表現することができるという効果が得られる。
また、予め登録した蓄積信号から、目的とする参照信号に類似した部分を探し出す信号検索方法、信号検索装置においては、この信号圧縮方法あるいは信号圧縮装置を用いることにより、特徴情報を情報圧縮することができ、より検索の高速化を図ることができると共に、蓄積情報量も削減することができるという効果が得られる。
According to the present invention, a new signal compression method or signal compression apparatus including a partial signal configuration process and a partial signal reconstruction process is used, and a partial signal is adapted to the characteristics of the signal while avoiding enormous preprocessing. By changing the length of the signal, it is possible to further compress the original signal prepared in advance and to express the signal sequence with a smaller amount of information.
Further, in the signal search method and signal search device for searching for a portion similar to the target reference signal from the stored signal registered in advance, the feature information is compressed by using this signal compression method or signal compression device. As a result, the speed of search can be further increased and the amount of stored information can be reduced.
また、本発明によれば、従来の信号検索方法と比較して、同一の検索結果を保証し、かつ検索に必要となる記憶容量をほとんど増加させることなく、不要な照合を局所的に省略することで、より高速な信号検索を行なうことを可能とする。 Further, according to the present invention, compared with the conventional signal search method, the same search result is guaranteed, and unnecessary collation is locally omitted without substantially increasing the storage capacity required for the search. This makes it possible to perform signal search at higher speed.
また、本発明によれば、インデックスを付与する特徴の数量を大幅に削減することで、より少ない記憶容量で信号検索を行なうことが出来る。 Further, according to the present invention, signal search can be performed with a smaller storage capacity by greatly reducing the number of features to which an index is assigned.
以下、本発明の一実施形態による信号圧縮装置を図面を参照して説明する。本発明では、様々な処理対象信号を用いることができるが、ここでは、該処理対象信号(原信号)の一例として、映像信号から作成されると共に、多次元ベクトルの一形態であるヒストグラム系列を用いるものとする。なお、ヒストグラムとは、例えば映像信号から特徴を抽出し、それらを予め定めた方法で分類して得られる分類毎の度数分布表である。また、原信号の特徴を多次元ベクトル系列として抽出可能であれば、原信号はヒストグラムには限定されず、多次元ベクトル系列を用いても良い。 Hereinafter, a signal compression apparatus according to an embodiment of the present invention will be described with reference to the drawings. In the present invention, various processing target signals can be used. Here, as an example of the processing target signal (original signal), a histogram sequence that is created from a video signal and is a form of a multidimensional vector is used. Shall be used. The histogram is a frequency distribution table for each classification obtained by, for example, extracting features from video signals and classifying them by a predetermined method. Further, as long as the features of the original signal can be extracted as a multidimensional vector series, the original signal is not limited to a histogram, and a multidimensional vector series may be used.
[第1実施例]
図1は、第1の実施形態の構成を示すブロック図である。図1において、符号1は、原信号から該原信号より短い長さの部分信号を構成する初期部分信号構成部である。符号2は、初期部分信号構成部1から出力された各部分信号について、原信号よりもデータ量が少ない部分信号構成の候補を絞り込む部分信号構成選択部である。符号3は、部分信号構成選択部2から出力された部分信号構成の候補を用いて、実際に用いるベき部分信号構成を決定する部分信号再構成部である。符号4は、部分信号再構成部3から出力された各部分信号から圧縮信号を算出するための写像を決定する圧縮写像決定部である。符号5は、部分信号再構成部3から出力された各部分信号に対応する圧縮信号を、圧縮写像決定部4から出力された写像に基づいて算出する信号圧縮部である。
[First embodiment]
FIG. 1 is a block diagram showing the configuration of the first embodiment. In FIG. 1,
なお、信号圧縮部5は、部分信号再構成部3から出力される部分信号、及び圧縮写像決定部4から出力される線形写像の集合を用いて、部分信号内の各ヒストグラムを、その部分信号から作成された部分空間へ射影する信号写像部51と、部分信号再構成部3から出力される部分信号、圧縮写像決定部4から出力される線形写像の集合、及び信号写像部51から出力される圧縮ヒストグラム系列の集合とを用いて、各ヒストグラムと、それに対応する圧縮ヒストグラムとの距離を計算する射影距離計算部52と、信号写像部51から出力された圧縮ヒストグラム系列の集合、及び射影距離計算部52から出力された射影距離とを用いて、圧縮特徴の系列を算出する圧縮特徴構成部53とを備えている。
The
図1に示す信号圧縮装置は、原信号、すなわち圧縮しようとしている映像信号から抽出したヒストグラム系列を入力とし、圧縮信号、すなわち映像信号から抽出したヒストグラム系列を圧縮した圧縮ヒストグラムの系列を出力するものである。 The signal compression apparatus shown in FIG. 1 receives a histogram sequence extracted from an original signal, that is, a video signal to be compressed, and outputs a compressed signal, that is, a compressed histogram sequence obtained by compressing a histogram sequence extracted from the video signal. It is.
次に、図5から図15を参照して、図1に示す信号圧縮装置の動作を説明する。初めに、図5に示す本実施形態の信号圧縮装置の処理動作を示すフローチャートを参照して、信号圧縮装置の全体の動作フローを説明する。各処理の詳細な動作は後述する。
図5において、まず、初期部分信号構成部1は、与えられた原信号を読み込む(ステップS1)。続いて、初期部分信号構成部1は、初期部分信号構成処理を行う(ステップS2)。次に、部分信号構成選択部2は、部分信号構成選択処理を行う(ステップS3)。
次に、部分信号再構成部3は、部分信号再構成処理を行う(ステップS4)。次に、圧縮写像決定部4は、圧縮写像決定処理を行う(ステップS5)。更に、信号圧縮部5は、信号圧縮処理を行う(ステップS6)。そして、信号圧縮部5は、原信号の圧縮信号を出力する(ステップS7)。
Next, the operation of the signal compression apparatus shown in FIG. 1 will be described with reference to FIGS. First, the overall operation flow of the signal compression apparatus will be described with reference to a flowchart showing the processing operation of the signal compression apparatus of the present embodiment shown in FIG. Detailed operations of each process will be described later.
In FIG. 5, first, the initial partial
Next, the partial
次に、図6を参照して、図5に示す初期部分信号構成処理(ステップS2)の詳細を説明する。図6は、初期部分信号構成部1の動作を示すフローチャートである。
まず、初期部分信号構成部1は、原信号であるヒストグラムの系列を読み込む(ステップS11)。続いて初期部分信号構成部1は、読み込んだヒストグラム系列を、予め与えられたセグメント数に従って等分割する(ステップS12)。そして、初期部分信号構成部1は、分割されたヒストグラム系列であるセグメントの集合を出力する(ステップS13)。
Next, details of the initial partial signal configuration process (step S2) shown in FIG. 5 will be described with reference to FIG. FIG. 6 is a flowchart showing the operation of the initial partial
First, the initial partial
次に、図7を参照して、図5に示す部分信号構成選択処理(ステップS3)の詳細を説明する。図7は、部分信号構成選択部2の動作を示すフローチャートである。
図7において、まず、部分信号構成選択部2は、初期部分信号構成部1から出力される固定長セグメント(部分信号)の集合を読み込む(ステップS15)。次に、分割境界を現在の位置から移動させることができる幅である分割境界移動可能幅を予め与えておき、各分割境界について、現在の分割境界の位置から前後に分割境界移動可能幅の分の範囲を、分割境界移動可能範囲として設定する(ステップS16)。続いて、セグメントの分割境界のうち、先頭の分割境界に注目する(ステップS17)。そして、分割境界を共有する2つのセグメントに対して、分割境界が現在の位置にあるときの圧縮信号の次元数を計算し、それらをセグメント長で正規化した平均値を計算する(ステップS18)。
Next, details of the partial signal configuration selection process (step S3) shown in FIG. 5 will be described with reference to FIG. FIG. 7 is a flowchart showing the operation of the partial signal
In FIG. 7, first, the partial signal
続いて、分割境界を共有する2つのセグメントに対して、分割境界が分割境界移動可能範囲の両端にあるときの圧縮信号の次元数を計算し、それらをセグメント長で正規化した平均値を計算する(ステップS19)。
さらに、分割境界移動可能範囲の中のいくつかの箇所で、同様に次元数の平均値を計算する。計算を行う回数は、上記3箇所の分割境界における次元数の平均値から求められる。続いて、求められた計算回数を基に、分割境界移動可能範囲の中で等間隔となるように、分割境界移動可能範囲の先頭から順に次元数の平均値を計算する(ステップS20、S21、S22)。
Next, for two segments that share the division boundary, calculate the number of dimensions of the compressed signal when the division boundary is at both ends of the division boundary movable range, and calculate the average value normalized by the segment length (Step S19).
Furthermore, the average value of the number of dimensions is calculated in the same way at several points in the range where the dividing boundary is movable. The number of times of calculation is obtained from the average value of the number of dimensions at the three division boundaries. Subsequently, based on the calculated number of calculations, an average value of the number of dimensions is calculated in order from the beginning of the division boundary movable range so that the division boundary movable range is equally spaced (steps S20, S21, S22).
そして、分割境界を共有するヒストグラム系列のうちいずれかで次元数に変化があるか否かを判定し(ステップS23)、分割境界を共有するヒストグラム系列のうちいずれかで次元数に変化が起きたときは(ステップS23のYES)、現在の計算箇所から1つ手前の計算箇所までの間を、最適な分割境界の候補として、その範囲の位置を全て保持しておく(ステップS24)。なお、次元数の平均値を計算する方法については、図面を参照して詳細を後述する。
また、分割境界移動可能範囲の片側で計算を行う箇所の数xは、以下のようにして求められる。
Then, it is determined whether or not there is a change in the number of dimensions in any one of the histogram series sharing the division boundary (step S23), and the number of dimensions has changed in any of the histogram series sharing the division boundary. If this is the case (YES in step S23), all the positions in the range are held as candidates for the optimum division boundary from the current calculation location to the previous calculation location (step S24). The method for calculating the average value of the number of dimensions will be described later in detail with reference to the drawings.
Further, the number x of points to be calculated on one side of the divided boundary movable range is obtained as follows.
まず、部分信号構成選択部2、及び後述する部分信号再構成部3の処理において、1つの分割境界を決定するために必要となる次元数の平均値を計算する箇所の数f(x)は、以下で与えられる。
First, in the processing of the partial signal
このf(x)は、 This f (x) is
以上のようにして、計算を行う回数が求められるので、全ての計算箇所について計算が終了していなければ(ステップS25のNO)、境界を次の計算箇所に移動し(ステップS26)、ステップS22からステップS24における操作を繰り返す。
As described above, since the number of times of calculation is obtained, if the calculation has not been completed for all the calculation points (NO in step S25), the boundary is moved to the next calculation point (step S26), and step S22. To repeat the operation in step S24.
また、全ての計算箇所について計算が終了していれば(ステップS25のYES)、全ての分割境界について操作が終了したか否かを判定し(ステップS27)、全ての分割境界について操作が終了していなければ(ステップS27のNO)、分割境界を次の分割境界に変更し(ステップS28)、ステップS18からステップS26における操作を繰り返す。そして、全ての分割境界について操作が終了した時点で(ステップS27のYES)、部分信号構成選択部2は、保持していた分割境界の候補の集合を出力する(ステップS29)。
If the calculation has been completed for all calculation locations (YES in step S25), it is determined whether or not the operation has been completed for all division boundaries (step S27), and the operation has been completed for all division boundaries. If not (NO in step S27), the division boundary is changed to the next division boundary (step S28), and the operations from step S18 to step S26 are repeated. When the operation is completed for all the division boundaries (YES in step S27), the partial signal
次に、図8、及び図9を参照して、上述の次元数の平均値を計算する方法について説明する。図8は、平均次元数計算処理の全体の流れを示すフローチャートであり、図9は、平均次元数計算処理に用いられる基底抽出処理の流れを示すフローチャートである。具体的には、次元数の平均値は、以下のようにして計算される。
図8において、まず、分割境界を共有する2つのセグメントを読み込む(ステップS31)。次に、与えられた2つのセグメントから、原信号の性質をよく表現する部分空間の基底を抽出する(ステップS32)。
Next, with reference to FIG. 8 and FIG. 9, a method for calculating the above average value of the number of dimensions will be described. FIG. 8 is a flowchart showing the overall flow of the average dimension number calculation process, and FIG. 9 is a flowchart showing the flow of the base extraction process used for the average dimension number calculation process. Specifically, the average value of the number of dimensions is calculated as follows.
In FIG. 8, first, two segments sharing a division boundary are read (step S31). Next, the base of the subspace that well expresses the nature of the original signal is extracted from the two given segments (step S32).
なお、ステップS32における基底の抽出方法について、先に図9を用いて説明すると、図9において、まず与えられた各セグメント(ステップS36)に対してKL(Karhunen−Loeve)展開を行う(ステップS37)。具体的には、KL展開は、以下の手順によって行われる。初めに、セグメント内のヒストグラムの平均ヒストグラム、及び共分散行列を計算する。j番目のセグメント The base extraction method in step S32 will be described with reference to FIG. 9. First, in FIG. 9, KL (Karhunen-Loeve) expansion is performed on each given segment (step S36) (step S37). ). Specifically, the KL expansion is performed according to the following procedure. First, the average histogram of the histograms in the segment and the covariance matrix are calculated. jth segment
次に、共分散行列S(j)(j=1、2、・・・、M)の固有値、及び固有ベクトルを求める。以上がKL展開の手順である。
なお、KL展開によって得られた各固有ベクトルに対応する固有値を全固有ベクトルの固有値の合計値で除算した値を、その固有ベクトルの寄与率と呼ぶ。続いて、寄与率が大きい順に固有ベクトルを並ベ換え、寄与率の合計値が、予め与えられた寄与閾値を上回るまで、順に固有ベクトルを選択していき(ステップS38、S39)、選択された固有ベクトルを部分空間の基底として(ステップS40)、基底の集合を得る(ステップS41)。
Next, eigenvalues and eigenvectors of the covariance matrix S (j) (j = 1, 2,..., M) are obtained. The above is the procedure for KL expansion.
A value obtained by dividing the eigenvalue corresponding to each eigenvector obtained by KL expansion by the total value of the eigenvalues of all eigenvectors is referred to as a contribution rate of the eigenvector. Subsequently, the eigenvectors are rearranged in descending order of the contribution rate, and the eigenvectors are selected in order until the total value of the contribution ratios exceeds a predetermined contribution threshold (steps S38 and S39), and the selected eigenvectors are selected. As a subspace basis (step S40), a set of bases is obtained (step S41).
図8のステップS33では、このようにして、それぞれのセグメントから抽出された基底の本数Nj(j=1、2、・・・、M)が圧縮信号の次元数となるので、以下のように、これらをそれぞれのセグメント長で正規化して平均値Nj´(j=1、2、・・・、M−1)を計算する(ステップS33)。 In step S33 of FIG. 8, the number of bases Nj (j = 1, 2,..., M) extracted from each segment in this way becomes the number of dimensions of the compressed signal. These are normalized by the respective segment lengths to calculate an average value Nj ′ (j = 1, 2,..., M−1) (step S33).
次に、図10を参照して、図5に示す部分信号再構成処理(ステップS4)の詳細を説明する。図10は、部分信号再構成部3の動作を示すフローチャートである。
図10において、まず、部分信号再構成部3は、初期部分信号構成部1から出力される固定長セグメントの集合、及び部分信号構成選択部2から出力される分割境界の候補の集合を読み込む(ステップS42)。次に、セグメントの分割境界のうち、先頭の分割境界に注目し(ステップS43)、この境界における分割境界候補のうち先頭の位置に分割境界を移動する(ステップS44)。続いて、分割境界を共有する2つのセグメントに対して、分割境界が現在の位置にあるときの圧縮信号の次元数を計算し、それらをセグメント長で正規化した平均値を計算する(ステップS45)。なお、次元数の平均値は、部分信号構成選択部2と同様に、上述の図8、及び図9に示した手順により計算される。
Next, the details of the partial signal reconstruction process (step S4) shown in FIG. 5 will be described with reference to FIG. FIG. 10 is a flowchart showing the operation of the partial
In FIG. 10, first, the partial
次に、次元数の平均値が、注目している分割境界においてこれまで計算された中で最も小さい値であれば(ステップS46のYES)、その平均値、及び現在の分割境界の位置を保持する(ステップS47、S48)。そして、全ての候補について計算が完了していなければ(ステップS49のNO)、分割境界を次の候補点に移動させ(ステップS50)、ステップS45へ戻り、次元数平均値の計算からこれまでの操作を繰り返す。候補点がなくなった時点で、注目している分割境界を次元平均値の最小値に対応する分割境界の位置に移動させ、分割境界を確定する。 Next, if the average value of the number of dimensions is the smallest value calculated so far at the partition boundary of interest (YES in step S46), the average value and the current position of the partition boundary are retained. (Steps S47 and S48). If the calculation has not been completed for all candidates (NO in step S49), the division boundary is moved to the next candidate point (step S50), the process returns to step S45, and the calculation of the average number of dimensions is performed so far. Repeat the operation. At the time when there are no candidate points, the partition boundary of interest is moved to the position of the partition boundary corresponding to the minimum value of the dimension average value, and the partition boundary is determined.
そして、最後の分割境界についての計算が完了していなければ(ステップS51のNO)、注目する分割境界を次の分割境界に変更し(ステップS52)、ステップS44へ戻り、これまでの操作を繰り返す。全ての分割境界について操作が終了した時点で(ステップS51のYES)、部分信号再構成部3は、分割境界を移動させることによって確定した可変長のセグメントの集合を出力する(ステップS53)。
If the calculation for the last division boundary has not been completed (NO in step S51), the division boundary of interest is changed to the next division boundary (step S52), the process returns to step S44, and the above operations are repeated. . When the operation is completed for all the division boundaries (YES in step S51), the partial
次に、図11を参照して、図5に示す圧縮写像決定処理(ステップS5)の詳細を説明する。図11は、圧縮写像決定部4の動作を示すフローチャートである。
図11において、まず、圧縮写像決定部4は、部分信号再構成部3から出力されるセグメントの集合を読み込む(ステップS55)。次に、各セグメントの基底を抽出する(ステップS56)。なお、基底の抽出は、部分信号構成選択部2と同様に、前述の図9に示した手順により計算される。
次に、部分空間への射影をそのセグメントに対する写像とする(ステップS58)。そして、圧縮写像決定部4は、各セグメントに対応した写像を出力する(ステップS59)。
Next, details of the compression mapping determination process (step S5) shown in FIG. 5 will be described with reference to FIG. FIG. 11 is a flowchart showing the operation of the compression
In FIG. 11, first, the compression
Next, the projection onto the partial space is set as a mapping for the segment (step S58). Then, the compressed
次に、図12から図15を参照して、図5に示す信号圧縮処理(ステップS6)の詳細を説明する。図12は、信号圧縮部5の全体動作を示すフローチャートである。
図12において、まず、信号圧縮部5は、部分信号再構成部3から出力されるセグメントの集合、及び圧縮写像決定部4から出力される線形写像の集合を読み込む(ステップS60)。次に、与えられた部分信号、及び線形写像の集合を用いて、部分信号内の各ヒストグラムを、その部分信号から作成された部分空間へ射影する信号写像処理を行う(ステップS61)。
Next, details of the signal compression processing (step S6) shown in FIG. 5 will be described with reference to FIGS. FIG. 12 is a flowchart showing the overall operation of the
In FIG. 12, the
また、与えられた部分信号と線形写像の集合、及び信号写像処理により求められた圧縮ヒストグラム系列の集合とを用いて、各ヒストグラムと、それに対応する圧縮ヒストグラムとの距離を計算する射影距離計算処理を行う(ステップS62)。更に、信号写像処理により求められた圧縮ヒストグラム系列の集合、及び射影距離計算処理により求められた射影距離とを用いて、圧縮特徴の系列を算出する圧縮特徴構成処理を行う(ステップS63)。そして、信号圧縮部5は、圧縮特徴構成処理により求められた圧縮特徴の系列を出力する(ステップS64)。
Also, a projection distance calculation process for calculating the distance between each histogram and the corresponding compressed histogram using a given partial signal, a set of linear mappings, and a set of compressed histogram sequences obtained by signal mapping processing. Is performed (step S62). Further, a compression feature construction process is performed for calculating a compression feature series using the set of compression histogram series obtained by the signal mapping process and the projection distance obtained by the projection distance calculation process (step S63). Then, the
図13は、図12に示す信号写像処理(ステップS61)の手順を示すフローチャートである。
図13において、信号圧縮部5を構成する信号写像部51は、まず、部分信号再構成部3から出力されるセグメント、及び圧縮写像決定部4から出力される線形写像の集合を読み込む(ステップS66)。次に、セグメント内の各ヒストグラムを、そのセグメントから作成された部分空間へ射影する(ステップS67)。
FIG. 13 is a flowchart showing the procedure of the signal mapping process (step S61) shown in FIG.
In FIG. 13, the
具体的には、セグメントX(j)から得られた部分空間の基底の集合を、 Specifically, the set of subspace bases obtained from segment X (j) is
これにより、信号写像部51は、圧縮ヒストグラム系列の集合Y(1)、Y(2)、・・・、Y(M)を出力する(ステップS68)。
Thereby, the
図14は、図12に示す射影距離計算処理(ステップS62)の手順を示すフローチャートである。
図14において、信号圧縮部5を構成する射影距離計算部52は、まず、部分信号再構成部3から出力されるセグメント、圧縮写像決定部4から出力される線形写像の集合、及び信号写像部51から出力される圧縮ヒストグラム系列の集合を読み込む(ステップS70)。次に、圧縮ヒストグラムを逆射影する(ステップS71)ことにより、以下のように原ヒストグラムの存在する空間での圧縮ヒストグラムの位置が求められるので、各ヒストグラムと、それに対応する圧縮ヒストグラムとの距離を計算する(ステップS72)。
FIG. 14 is a flowchart showing the procedure of the projection distance calculation process (step S62) shown in FIG.
In FIG. 14, the projection
具体的には、 In particular,
これにより、射影距離計算部52は、各ヒストグラムに対応した射影距離を出力する(ステップS73)。
Thereby, the projection
図15は、図12に示す圧縮特徴構成処理(ステップS63)の手順を示すフローチャートである。
図15において、信号圧縮部5を構成する圧縮特徴構成部53は、まず、信号写像部51から出力された圧縮ヒストグラム系列の集合、及び射影距離計算部52から出力された射影距離を読み込む(ステップS75)。次に、圧縮ヒストグラムy=(y1、y2、・・・、yk)と、それに対応して計算された射影距離
FIG. 15 is a flowchart showing the procedure of the compression feature configuration process (step S63) shown in FIG.
In FIG. 15, the compression
これにより、圧縮特徴構成部53は、圧縮特徴の系列を出力する(ステップS77)。
Thereby, the compression
[第2実施例]
図2は、第2の実施形態の構成を示すブロック図である。第2の実施形態では、第1の実施形態で説明した信号圧縮装置を応用した信号検索装置について説明する。図2において、第1の実施形態で図1を用いて説明した信号圧縮装置と同一の符号を付与された構成要素は、信号圧縮装置と同一の動作をする構成要素であるので、ここでは説明を省略する。
[Second Embodiment]
FIG. 2 is a block diagram showing the configuration of the second embodiment. In the second embodiment, a signal search device to which the signal compression device described in the first embodiment is applied will be described. 2, components given the same reference numerals as those of the signal compression device described with reference to FIG. 1 in the first embodiment are components that operate in the same manner as the signal compression device. Is omitted.
図2において、符号6は、目的とする信号である参照信号から特徴系列を算出する参照特徴抽出部である。符号7は、予め登録した原信号である蓄積信号に注目窓を設定し、注目窓内の信号から特徴系列を算出する蓄積特徴抽出部である。符号8は、参照特徴抽出部6から出力された参照特徴系列を、圧縮写像決定部4から出力された写像に基づいて圧縮する参照特徴圧縮部である。符号9は、参照特徴圧縮部8から出力された参照圧縮信号と、蓄積特徴抽出部7から出力された特徴系列を新たに用いることで信号圧縮部5から出力された蓄積圧縮信号との距離を計算する特徴照合部である。符号10は、特徴照合部9から出力された距離と、距離に対応する同値である探索閾値とを比較することにより、参照信号が、蓄積信号の当該箇所に存在するかどうかを判定する信号検出判定部である。
In FIG. 2,
図2に示す信号検索装置は、参照信号すなわち見本となる検索したい映像信号と、蓄積信号すなわち検索される映像信号を入力とし、参照信号との距離が予め設定した値(これを探索閾値という)がθ1を下回る蓄積信号中の箇所を出力するものである。 The signal search apparatus shown in FIG. 2 receives a reference signal, that is, a video signal to be searched as a sample, and an accumulation signal, that is, a video signal to be searched, and has a preset distance from the reference signal (this is called a search threshold). Outputs a portion in the accumulated signal where is less than θ1.
次に、図16から図24を参照して、図2に示す信号検索装置の動作を説明する。初めに、図16に示す本実施形態の信号検索装置の処理動作を示すフローチャートを参照して、信号検索装置の全体の動作フローを説明する。各処理の詳細な動作は後述する。
図16において、まず、参照特徴抽出部6は、参照特徴抽出処理を行う(ステップS81)。次に、蓄積特徴抽出部7は、蓄積特徴抽出処理を行う(ステップS82)。次に、初期部分信号構成部1は、初期部分信号構成処理を行う(ステップS83)。次に、部分信号構成選択部2は、部分信号構成選択処理を行う(ステップS84)。次に、部分信号再構成部3は、部分信号再構成処理を行う(ステップS85)。次に、圧縮写像決定部4は、圧縮写像決定処理を行う(ステップS86)。次に、信号圧縮部5は、信号圧縮処理を行う(ステップS87)。更に、参照特徴圧縮部8は、参照特徴圧縮処理を行う(ステップS88)。
Next, the operation of the signal search apparatus shown in FIG. 2 will be described with reference to FIGS. First, the overall operation flow of the signal search apparatus will be described with reference to a flowchart showing the processing operation of the signal search apparatus of this embodiment shown in FIG. Detailed operations of each process will be described later.
In FIG. 16, first, the reference
そして、信号圧縮部5から出力される蓄積圧縮特徴系列に対して設定する注目窓を、蓄積信号の先頭に設定する(ステップS89)。次に、特徴照合部9は、特徴照合処理を行う(ステップS90)。また、信号検出判定部10は、信号検出判定処理を行う(ステップS91)。そして、信号検出判定処理が行われたら、注目窓の現在位置が蓄積信号の終点であるか否かの判定を行い(ステップS95)、注目窓の現在位置が蓄積信号の終点ではない場合(ステップS95のNO)、注目窓をずらしてステップS90へ戻り、上述の処理を繰り返す。また、注目窓の現在位置が蓄積信号の終点である場合(ステップS95のYES)、信号の探索結果を出力する(ステップS96)。
Then, the attention window set for the accumulated compression feature sequence output from the
なお、図16に示すステップS92のスキップ幅計算処理は、第2の実施形態では必要なく、後述する第3の実施形態で説明するものとする。同様に、図16に示すステップS93の距離再計算処理と、ステップS94の信号検出再判定処理とは、第2の実施形態では必要なく、後述する第4の実施形態で説明するものとする。
また、上述の初期部分信号構成処理(ステップS83)、部分信号構成選択処理(ステップS84)、部分信号再構成処理(ステップS85)、圧縮写像決定処理(ステップS86)、信号圧縮処理(ステップS87)については、図6から図15に示す第1の実施形態の信号圧縮装置で実行される処理と同一であるので、ここでは説明を省略する。ただし、初期部分信号構成処理(ステップS83)は、入力として、蓄積特徴抽出処理(ステップS82)から出力される蓄積特徴系列を用いる。
Note that the skip width calculation processing in step S92 shown in FIG. 16 is not necessary in the second embodiment, and will be described in a third embodiment to be described later. Similarly, the distance recalculation process in step S93 and the signal detection re-determination process in step S94 shown in FIG. 16 are not necessary in the second embodiment, and will be described in a fourth embodiment to be described later.
The initial partial signal configuration process (step S83), partial signal configuration selection process (step S84), partial signal reconstruction process (step S85), compression mapping determination process (step S86), and signal compression process (step S87). Since this is the same as the processing executed by the signal compression apparatus of the first embodiment shown in FIGS. 6 to 15, the description thereof is omitted here. However, the initial partial signal configuration process (step S83) uses the accumulated feature series output from the accumulated feature extraction process (step S82) as an input.
次に、図17を参照して、図16に示す参照特徴抽出処理(ステップS81)の詳細を説明する。図17は、参照特徴抽出部6の動作を示すフローチャートである。
図17において、まず、参照特徴抽出部6は、与えられた参照信号を読み込む(ステップS98)。次に、読み込んだ参照信号に対して特徴抽出を行う(ステップS99)。
Next, details of the reference feature extraction process (step S81) shown in FIG. 16 will be described with reference to FIG. FIG. 17 is a flowchart showing the operation of the reference
In FIG. 17, first, the reference
ここでは、対象の信号が音響信号の場合に抽出する特徴としてスペクトル特徴を用いる。スペクトル特徴抽出は、音響信号に対して、帯域通過フィルタによって行うことができる。例えば、テレビやラジオ等の放送音響信号から15秒程度の音響信号を検索したい場合、特徴抽出の具体的な設定を次のようにすると、良い結果が得られる。すなわち、7個の帯域通過フィルタを用い、それらの中心周波数を対数軸上で等間隔に設定し、60ミリ秒程度の時間長の分析窓を10ミリ秒ずつ移動させながら、分析窓内の各帯域通過フィルタの出力の自乗の平均値を計算し、得られた7個の値を一組にして7次元特徴ベクトルとする。この場合特徴ベクトルは10ミリ秒ごとに1つ得られる。 Here, a spectral feature is used as a feature to be extracted when the target signal is an acoustic signal. Spectral feature extraction can be performed on the acoustic signal by a band pass filter. For example, if it is desired to search for an acoustic signal of about 15 seconds from a broadcast acoustic signal such as a television or radio, good results can be obtained by setting the specific feature extraction settings as follows. That is, seven bandpass filters are used, their center frequencies are set at equal intervals on the logarithmic axis, and the analysis windows having a time length of about 60 milliseconds are moved 10 milliseconds at a time. The average value of the square of the output of the band pass filter is calculated, and the obtained seven values are combined into a seven-dimensional feature vector. In this case, one feature vector is obtained every 10 milliseconds.
一方、映像信号に対しては、特徴として色特徴を用いる。例えば、テレビ等の放送映像信号から15秒程度の映像信号を検索したい場合、特徴抽出の具体的な設定を次のようにすると、良い結果が得られる。すなわち、映像を構成する各画像を縦に2分割、横に3分割し、各分割においてRGB値を計算し、各分割で得られたRGB3個の値、合計18個の値を一組にして18次元特徴ベクトルとする。映像が1秒当たり30枚の画像で構成されている場合、特徴ベクトルは30分の1秒ごとに1つ得られる。 On the other hand, color features are used as features for video signals. For example, when searching for a video signal of about 15 seconds from a broadcast video signal of a television or the like, good results can be obtained by setting the specific feature extraction settings as follows. That is, each image constituting the video is divided vertically into two and horizontally into three, and RGB values are calculated in each division, and three values obtained in each division, a total of 18 values, are combined into one set. Let it be an 18-dimensional feature vector. If the video is composed of 30 images per second, one feature vector is obtained every 1 / 30th of a second.
続いて、特徴ベクトルをベクトル量子化(ステップS100)を用いて符号化することによって、特徴ベクトルの時系列から、特徴ベクトルのヒストグラムを作成する(ステップ101)。例えば、ベクトル量子化の符号語数が512であれば、ヒストグラム全体のビン(区間)の数は512となり、各特徴ベクトルは、この512個のビンのうちどれか1つに分類されることになる。なお、以下の説明において、参照信号から作成されたヒストグラムを参照ヒストグラムと称する。そして、参照特徴抽出部6は、得られた参照ヒストグラムを出力する(ステップS102)。
Subsequently, a feature vector histogram is created from the time series of the feature vectors by encoding the feature vectors using vector quantization (step S100) (step 101). For example, if the number of code words for vector quantization is 512, the number of bins (sections) in the entire histogram is 512, and each feature vector is classified into one of the 512 bins. . In the following description, a histogram created from a reference signal is referred to as a reference histogram. Then, the reference
次に、図18を参照して、図16に示す蓄積特徴抽出処理(ステップS82)の詳細を説明する。図18は、蓄積特徴抽出部7の動作を示すフローチャートである。
図18において、まず、蓄積特徴抽出部7は、蓄積信号を読み込む(ステップS104)。次に、読み込んだ蓄積信号に対して、注目窓を蓄積信号の先頭に設定する(ステップS105)。ここでは、参照特徴抽出部6に与えられた参照信号と同一の長さの注目窓を設定する。
Next, with reference to FIG. 18, the details of the accumulated feature extraction process (step S82) shown in FIG. 16 will be described. FIG. 18 is a flowchart showing the operation of the accumulated
In FIG. 18, first, the accumulation
続いて、注目窓内の蓄積信号に対して特徴抽出を行う(ステップS106)。なお、特徴抽出は、参照特徴抽出部6において行った処理と同一処理を行う。さらに、注目窓内の特徴ベクトルの時系列から、特徴ベクトルのヒストグラムを作成する(ステップS107、S108)。ヒストグラムの作成の仕方は、参照特徴抽出部6で行ったものと同一の方法によって行う。そして、蓄積特徴抽出部7は、処理の開始時において蓄積信号の先頭に設定した注目窓を順次1特徴ベクトルずつずらしながら、ステップS106からステップS108の処理を、蓄積信号の終端まで繰り返し実行する(ステップS109、ステップS110)。なお、以下の説明においては、蓄積信号から作成された各ヒストグラムを蓄積ヒストグラムと称する。最後に、蓄積特徴抽出部7は、得られた蓄積ヒストグラム系列を出力する(ステップS111)。
Subsequently, feature extraction is performed on the accumulated signal in the window of interest (step S106). Note that the feature extraction performs the same processing as the processing performed in the reference
次に、図19から図22を参照して、図16に示す参照特徴圧縮処理(ステップS88)の詳細を説明する。図19は、参照特徴圧縮部8の動作を示すフローチャートである。
図19において、まず、参照特徴圧縮部8は、参照特徴抽出部6から出力される参照ヒストグラム、及び圧縮写像決定部4から出力される線形写像の集合を読み込む(ステップS113)。次に、参照ヒストグラムを、各線形写像を用いて、対応する部分空間へ射影する参照信号写像処理を行う(ステップS114)。射影は、第1の実施形態で説明した信号圧縮部5と同様の処理により行われる。例えば、セグメント数をM=1000とすると、1000個の圧縮ヒストグラムが作成される。
Next, the details of the reference feature compression process (step S88) shown in FIG. 16 will be described with reference to FIGS. FIG. 19 is a flowchart showing the operation of the reference
In FIG. 19, first, the reference
続いて、ヒストグラムと各圧縮ヒストグラムとの距離、すなわちヒストグラムの射影距離を計算する参照射影距離計算処理を行う(ステップS115)。計算は、同じく信号圧縮部5と同様の処理によって行われる。最後に、圧縮ヒストグラムとそれに対応する射影距離とから、圧縮特徴を構成する参照圧縮特徴構成処理を行う(ステップS116)。圧縮特徴の構成は、同じく信号圧縮部5と同様の処理によって行われる。そして、参照特徴圧縮部8は、参照圧縮特徴の集合を出力する(ステップS117)。
Subsequently, a reference projection distance calculation process for calculating a distance between the histogram and each compressed histogram, that is, a projection distance of the histogram is performed (step S115). The calculation is performed by the same processing as that of the
図20は、図19に示す参照信号写像処理(ステップS114)の手順を示すフローチャートである。
図20において、参照特徴圧縮部8を構成する参照信号写像部(図示せず)は、まず、参照特徴抽出部6から出力される参照ヒストグラム、及び圧縮写像決定部4から出力される線形写像の集合を読み込む(ステップS119)。次に、参照ヒストグラムを各セグメントに対応した線形写像により部分空間へ射影する(ステップS120)。
これにより、参照信号写像部は、参照圧縮ヒストグラムの集合を出力する(ステップS121)。
FIG. 20 is a flowchart showing the procedure of the reference signal mapping process (step S114) shown in FIG.
In FIG. 20, a reference signal mapping unit (not shown) constituting the reference
Thereby, the reference signal mapping unit outputs a set of reference compression histograms (step S121).
図21は、図19に示す参照射影距離計算処理(ステップS115)の手順を示すフローチャートである。
図21において、参照特徴圧縮部8を構成する参照射影距離計算部(図示せず)は、まず、参照特徴抽出部6から出力される参照ヒストグラム、圧縮写像決定部4から出力される線形写像の集合、及び参照信号写像部から出力される参照圧縮ヒストグラムの集合を読み込む(ステップS123)。次に、各圧縮ヒストグラムを逆射影する(ステップS124)ことにより、各ヒストグラムと、それに対応する圧縮ヒストグラムとの距離を計算する(ステップS125)。
これにより、参照射影距離計算部は、各ヒストグラムに対応した射影距離を出力する(ステップS126)。
FIG. 21 is a flowchart showing the procedure of the reference projection distance calculation process (step S115) shown in FIG.
In FIG. 21, a reference projection distance calculation unit (not shown) constituting the reference
Accordingly, the reference projection distance calculation unit outputs the projection distance corresponding to each histogram (step S126).
図22は、図19に示す参照圧縮特徴構成処理(ステップS116)の手順を示すフローチャートである。
図22において、参照特徴圧縮部8を構成する参照圧縮特徴構成部(図示せず)は、まず、参照信号写像部から出力された参照圧縮ヒストグラムの集合、及び参照射影距離計算部から出力された射影距離を読み込む(ステップS128)。次に、圧縮ヒストグラムと、それに対応して計算された射影距離から、圧縮特徴を構成する(ステップS129)。
これにより、参照圧縮特徴構成部は、圧縮特徴の集合を出力する(ステップS130)。
FIG. 22 is a flowchart showing the procedure of the reference compression feature configuration process (step S116) shown in FIG.
In FIG. 22, the reference compression feature component (not shown) constituting the
Thereby, the reference compression feature component outputs a set of compression features (step S130).
次に、図23を参照して、図16に示す特徴照合処理(ステップS90)の詳細を説明する。図23は、特徴照合部9の動作を示すフローチャートである。
図23において、まず、特徴照合部9は、信号圧縮部5から出力される蓄積圧縮特徴系列、及び参照特徴圧縮部8から出力される参照圧縮特徴の集合を読み込む(ステップS132)。次に、参照圧縮特徴y*Rと蓄積圧縮特徴y*Sとの距離を計算する(ステップS133)。
Next, details of the feature matching process (step S90) shown in FIG. 16 will be described with reference to FIG. FIG. 23 is a flowchart showing the operation of the feature matching unit 9.
In FIG. 23, first, the feature matching unit 9 reads the accumulation compression feature series output from the
具体的には、距離d(y*R,y*S)は、ユークリッド距離を用いて以下のように定義する。 Specifically, the distance d (y * R, y * S) is defined as follows using the Euclidean distance.
ここで、KL展開(主成分分析)の性質により、以下の式が成り立つ。 Here, the following equation is established depending on the nature of the KL expansion (principal component analysis).
また、式(4)より、主成分分析には、その性質(3)式から、圧縮特徴間の距離値がヒストグラム間の距離の下限値となる特異な効果がある。そして、さらに射影距離を用いることによって、それを用いない場合に比べて、ヒストグラム間の距離のより大きな下限値d(y*R,y*S)を得ることがてきる。
これにより、特徴照合部9は、得られた距離の下限値を出力する(ステップS134)。
Further, from the equation (4), the principal component analysis has a peculiar effect that the distance value between the compression features becomes the lower limit value of the distance between the histograms from the property (3) equation. Further, by using the projection distance, it is possible to obtain a larger lower limit d (y * R, y * S) of the distance between the histograms as compared with the case where it is not used.
Thereby, the feature matching unit 9 outputs the lower limit value of the obtained distance (step S134).
次に、図24を参照して、図16に示す信号検出判定処理(ステップS91)の詳細を説明する。図24は、信号検出判定部10の動作を示すフローチャートである。
図24において、まず、信号検出判定部10は、特徴照合部9から出力される距離下限値を読み込む(ステップS139)。次に、距離下限値と、距離尺度であるユークリッド距離に基づいて予め定められた値である探索閾値とを比較する(ステップ140)。距離値が探索閾値を下回る場合(注目窓を時間方向に分割した場合にあっては、全ての時間分割において距離値が探索閾値を下回ることが判明した場合)(ステップS140のYES)、参照信号が、蓄積信号の当該箇所に存在すると判断し(ステップS141)、信号検出結果として、蓄積信号に対する時系列中の現在位置(フラグ)を出力する(ステップS142)。
Next, details of the signal detection determination process (step S91) shown in FIG. 16 will be described with reference to FIG. FIG. 24 is a flowchart illustrating the operation of the signal
In FIG. 24, first, the signal
[第3実施例]
図3は、第3の実施形態の構成を示すブロック図である。第3の実施形態では、第2の実施形態で説明した信号検索装置に、特徴照合部9から出力された距離に基づいて、信号圧縮部5から出力される蓄積圧縮特徴系列に対して設定する注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動するスキップ幅計算部11が新たに設けられた信号検索装置について説明する。図3において、第1、第2の実施形態で図1を用いて説明した信号圧縮装置、及び図2を用いて説明した信号検索装置と同一の符号を付与された構成要素は、信号圧縮装置または信号検索装置と同一の動作をする構成要素であるので、ここでは説明を省略する。
[Third embodiment]
FIG. 3 is a block diagram showing the configuration of the third embodiment. In the third embodiment, the signal search device described in the second embodiment is set for the accumulated compression feature sequence output from the
なお、図3に示す信号検索装置も、参照信号すなわち見本となる検索したい映像信号と、蓄積信号すなわち検索される映像信号を入力とし、参照信号との距離が予め設定した値(これを探索閾値という)がθ1を下回る蓄積信号中の箇所を出力するものである。 Note that the signal search apparatus shown in FIG. 3 also receives a reference signal, that is, a video signal to be searched as a sample, and an accumulation signal, that is, a video signal to be searched, as the input, and the distance from the reference signal is a preset value (this is a search threshold Output a portion in the accumulated signal below θ1.
次に、図16及び図25を参照して、図3に示す信号検索装置の動作を説明する。初めに、図16を参照して、信号検索装置の全体の動作フローを説明すると、本実施形態の信号検索装置の動作の特徴は、第2の実施形態で説明した動作フローに対して、ステップS91の「信号検出判定処理」とステップS95の「注目窓の現在位置が蓄積信号の終点であるか否かの判定処理」との間において、信号圧縮部5から出力される蓄積圧縮特徴系列に対して設定する注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動するスキップ幅計算処理(ステップS92)が実行されることである。
Next, the operation of the signal search apparatus shown in FIG. 3 will be described with reference to FIGS. First, the overall operation flow of the signal search device will be described with reference to FIG. 16. The operation feature of the signal search device of this embodiment is different from the operation flow described in the second embodiment. Between the “signal detection determination process” in S91 and the “determination process whether or not the current position of the window of interest is the end point of the stored signal” in step S95, the stored compression feature series output from the
次に、図25を参照して、図16に示すスキップ幅計算処理(ステップS92)の詳細を説明する。図25は、スキップ幅計算部11の動作を示すフローチャートである。
図25において、まず、スキップ幅計算部11は、特徴照合部9から出力される距離下限値を読み込む(ステップS144)。次に、探索漏れが生じないことを保証したまま特徴照合、すなわち距離計算を省略できるスキップ幅を計算する(ステップS145)。
Next, details of the skip width calculation process (step S92) shown in FIG. 16 will be described with reference to FIG. FIG. 25 is a flowchart showing the operation of the
In FIG. 25, first, the skip
具体的なスキップ幅決定の原理を、以下で説明する。
ヒストグラムは特徴ベクトルの時系列を分類し累積したものであるから、蓄積信号の特徴ベクトルに対する時間窓の移動に伴って、ヒストグラム間の距離値が急激に変化することはない。時間窓の1特徴ベクトル分の移動当たりの距離値の変化率の絶対値は、決して、(√2)を越えない。すなわち、蓄積信号に対する時間窓の先頭がm1番目の特徴ベクトルであるときのヒストグラム間の距離値をd(xR,xS(m1))とするとき、時間窓がm2番目の特徴ベクトルまで移動したときの距離値の下限
The specific principle of determining the skip width will be described below.
Since the histogram is obtained by classifying and accumulating time series of feature vectors, the distance value between the histograms does not change suddenly with the movement of the time window with respect to the feature vector of the accumulated signal. The absolute value of the rate of change of the distance value per movement for one feature vector of the time window never exceeds (√2). That is, when the distance value between the histograms when the head of the time window for the accumulated signal is the m1st feature vector is d (xR, xS (m1)), the time window is moved to the m2nd feature vector. Lower bound for distance value
処理の開始時は、圧縮蓄積特徴を、圧縮特徴系列の先頭から取り出していくが、処理の過程で、圧縮蓄積特徴を取り出す位置を順次時間方向にずらしながら(ステップS146)処理を進めていく。時間方向にずらす量は、スキップ幅計算部11で与えられる。
At the start of processing, the compressed accumulation feature is extracted from the beginning of the compression feature series. In the process, the position where the compression accumulation feature is extracted is sequentially shifted in the time direction (step S146). The amount of shift in the time direction is given by the
[第4実施例]
図4は、第4の実施形態の構成を示すブロック図である。第4の実施形態では、第3の実施形態で説明した信号検索装置に、信号検出判定部10で参照信号が存在すると判定された蓄積信号の当該場所について、参照特徴抽出部6から出力された特徴系列と、蓄積特徴抽出部7から出力された特徴系列との距離を計算する距離再計算部12と、距離再計算部12から出力された距離と探索閾値とを比較することにより、参照信号が、蓄積信号の当該箇所に存在するかどうかを再判定する信号検出再判定部13とが新たに設けられた信号検索装置について説明する。図4において、第1から第3の実施形態で図1から図3を用いて説明した信号圧縮装置または信号検索装置と同一の符号を付与された構成要素は、信号圧縮装置または信号検索装置と同一の動作をする構成要素であるので、ここでは説明を省略する。
[Fourth embodiment]
FIG. 4 is a block diagram showing a configuration of the fourth embodiment. In the fourth embodiment, in the signal search apparatus described in the third embodiment, the reference
なお、図4に示す信号検索装置も、参照信号すなわち見本となる検索したい映像信号と、蓄積信号すなわち検索される映像信号を入力とし、参照信号との距離が予め設定した値(これを探索閾値という)がθ1を下回る蓄積信号中の箇所を出力するものである。 The signal search apparatus shown in FIG. 4 also receives a reference signal, that is, a video signal to be searched as a sample, and an accumulation signal, that is, a video signal to be searched, as input, and a distance from the reference signal that is set in advance (this is a search threshold) Output a portion in the accumulated signal below θ1.
次に、図16及び図26、図27を参照して、図4に示す信号検索装置の動作を説明する。初めに、図16を参照して、信号検索装置の全体の動作フローを説明すると、本実施形態の信号検索装置の動作の特徴は、第3の実施形態で説明した動作フローに対して、ステップS92の「スキップ幅計算処理」とステップS95の「注目窓の現在位置が蓄積信号の終点であるか否かの判定処理」との間において、信号検出判定部10で参照信号が存在すると判定された蓄積信号の当該場所について、参照特徴抽出部6から出力された特徴系列と、蓄積特徴抽出部7から出力された特徴系列との距離を計算する距離再計算処理(ステップS93)と、距離再計算処理により求められた距離と探索閾値とを比較することにより、参照信号が、蓄積信号の当該箇所に存在するかどうかを再判定する信号検出再判定処理(ステップS94)とが実行されることである。
Next, the operation of the signal search apparatus shown in FIG. 4 will be described with reference to FIGS. 16, 26, and 27. First, the overall operation flow of the signal search device will be described with reference to FIG. 16. The operation feature of the signal search device of this embodiment is different from the operation flow described in the third embodiment. Between the “skip width calculation process” in S92 and the “determination process for determining whether or not the current position of the window of interest is the end point of the accumulated signal” in step S95, the signal
次に、図26を参照して、図16に示す距離再計算処理(ステップS93)の詳細を説明する。図26は、距離再計算部12の動作を示すフローチャートである。
図26において、まず、距離再計算部12は、参照特徴抽出部6から出力される参照ヒストグラム、蓄積特徴抽出部7から出力される蓄積ヒストグラム系列及び信号検出判定部10から出力される検出結果を読み込む(ステップS148)。次に、参照信号が存在すると判定された蓄積信号中の箇所に対応する蓄積ヒストグラムに対して、参照ヒストグラムとの距離を計算する(ステップS149)。ヒストグラム間の距離は、ユークリッド距離を用いて前述の式(1)と同様に定義する。そして、求めた距離値を出力する(ステップS150)。
Next, the details of the distance recalculation process (step S93) shown in FIG. 16 will be described with reference to FIG. FIG. 26 is a flowchart showing the operation of the
In FIG. 26, first, the
次に、図27を参照して、図16に示す信号検出再判定処理(ステップS94)の詳細を説明する。図27は、信号検出再判定部13の動作を示すフローチャートである。
図27において、まず、信号検出再判定部13は、距離再計算部12から出力される距離値を読み込む(ステップS152)。次に、距離値と探索閾値とを比較する(ステップS153)。この比較の結果、距離値が探索閾値を下回る場合は(ステップS153のYES)、その参照信号が蓄積信号中に存在したことを意味するので、信号検出結果として、蓄積信号に対する時系列中の現在位置を出力する(ステップS154)。
Next, the details of the signal detection re-determination process (step S94) shown in FIG. 16 will be described with reference to FIG. FIG. 27 is a flowchart showing the operation of the signal
In FIG. 27, first, the signal
なお、図4に示す信号検索装置において、スキップ幅計算部11は、必要に応じて備えていればよく、必要なければ備えていなくてもよい。
In the signal search apparatus shown in FIG. 4, the skip
<実験結果>
次に、本発明による信号検索装置の動作実験結果を説明する。
本発明の効果を確認するため、まず、第1の実験として、24時間の映像信号からヒストグラムを作成したものを蓄積信号とし、セグメント数及び寄与閾値を変化させたときのセグメント長で正規化した圧縮ヒストグラムの平均次元数の変化を調べた。
なお、圧縮のパラメータは、サンプリング周波数=29.97[Hz]、画像の分割数=6(縦2分割、横3分割)、ヒストグラムの次元数=256、時間窓の幅=15[秒]とした。また、分割境界移動可能幅△(デルタ)は、1から500まで、1、2、5、10、・・・のように変化させた。
<Experimental result>
Next, an operation experiment result of the signal search apparatus according to the present invention will be described.
In order to confirm the effect of the present invention, first, as a first experiment, a histogram created from a 24-hour video signal was used as an accumulated signal, and normalized with the segment length when the number of segments and the contribution threshold were changed. The change of the average dimension number of the compressed histogram was investigated.
The compression parameters are as follows: sampling frequency = 29.97 [Hz], image division number = 6 (vertical 2-division, horizontal 3-division), histogram dimension number = 256, time window width = 15 sec. did. Further, the dividing boundary movable width Δ (delta) was changed from 1 to 500 as 1, 2, 5, 10,.
第1の実験の結果を図28に示す。グラフの横軸は分割境界移動可能幅△(図28中では”Width of shiftable range”と示す)、縦軸は△=0のときの平均次元数を基準とした平均次元数の比(図28中では”Ratio of dimensions ”と示す)を表している。例えば、分割境界移動可能幅△=500、セグメント数M=1000[segments]、寄与閾値(contribution rate )σ=0.75において、平均次元数は2.91、分割境界移動可能幅△=0としたときの平均次元数が3.30、次元削減比は0.882であった。 The result of the first experiment is shown in FIG. The horizontal axis of the graph is the dividing boundary movable width Δ (indicated as “Width of shiftable range” in FIG. 28), and the vertical axis is the ratio of the average dimension number based on the average dimension number when Δ = 0 (FIG. 28). It is expressed as “Ratio of dimensions”. For example, when the division boundary movable width Δ = 500, the number of segments M = 1000 [segments], and the contribution threshold (contribution rate) σ = 0.75, the average number of dimensions is 2.91, and the division boundary movable width Δ = 0. The average number of dimensions was 3.30, and the dimension reduction ratio was 0.882.
続いて、第2の実験として、24時間の映像信号からヒストグラムを作成したものを原信号とし、部分信号構成選択部2及び部分信号再構成部3において平均次元数を計算する回数を調べた。なお、探索のパラメータは第1の実験と同様であり、さらに、セグメント数M=1000[segments]、寄与閾値(contribution rate )σ=0.75とした。
Subsequently, as a second experiment, the number of times of calculating the average number of dimensions in the partial signal
第2の実験の結果を図29に示す。グラフの横軸は分割境界移動可能幅△(図29中では”Width of shiftable range”と示す)、縦軸は計算回数(図29中では”Number ofcalculation ”と示す)を表す。例えば、分割境界移動可能幅△=500のとき、本発明の方法(図29中では”speedup ”としてグラフ化)で約80000回、部分信号構成選択部2を実施しない方法(図29中では”non-speedup”としてグラフ化)で約1000000回、計算回数削減比は約12.5であった。
The result of the second experiment is shown in FIG. The horizontal axis of the graph represents the dividing boundary movable width Δ (shown as “Width of shiftable range” in FIG. 29), and the vertical axis represents the number of calculations (shown as “Number of calculation” in FIG. 29). For example, when the dividing boundary movable width Δ = 500, the method of the present invention (in FIG. 29, graphed as “speedup”) does not execute the partial signal
[第5実施例]
次に、本発明の第5の実施形態について図面を用いて説明する。
本実施形態では、該処理対象信号の一例として音響信号を用いる。なお、具体的な特徴の抽出方法やヒストグラムの作成方法は、後述のクエリ特徴抽出部101の処理を用いて説明する。
図30は、第5の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。図30より、本実施形態の信号検索装置は、クエリ信号(参照信号)から特徴を導くクエリ特徴抽出部101(参照特徴抽出部)と、データベース信号(蓄積信号)に注目窓を設定し、注目窓内の信号から特徴を導くデータベース特徴抽出部(蓄積特徴抽出部)102と、前記データベース特徴抽出部102の処理において注目窓をずらしながら繰り返し行うことで出力された特徴系列を区分するデータベース特徴区分部103と、前記データベース特徴区分部103から出力された区分後の特徴系列から代表的な特徴を抽出し、より少ない数の特徴で構成される代表特徴系列を導くデータベース特徴間引き部104と、前記データベース特徴区分部103から出力された区分に含まれる特徴が存在する領域を導く特徴領域抽出部105と、前記クエリ特徴抽出部101から出力された特徴系列と前記データベース特徴間引き部104から出力された代表特徴系列との距離を計算する特徴照合部106と、前記特徴照合部106から出力された距離を、前記特徴照合部106から出力された領域を用いて補正する距離補正部107と、前記距離補正部7から出力された距離と、前記距離に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する信号検出判定部108とで構成される。
[Fifth embodiment]
Next, a fifth embodiment of the present invention will be described with reference to the drawings.
In the present embodiment, an acoustic signal is used as an example of the processing target signal. A specific feature extraction method and histogram creation method will be described using processing of the query
FIG. 30 is a diagram illustrating functional blocks of a signal search apparatus to which the method of the fifth embodiment is applied. From FIG. 30, the signal search apparatus according to the present embodiment sets an attention window in a query feature extraction unit 101 (reference feature extraction unit) that derives a feature from a query signal (reference signal) and a database signal (accumulated signal). A database feature extraction unit (accumulated feature extraction unit) 102 for deriving features from signals in the window, and a database feature classification that classifies the feature series output by repeatedly performing the processing of the database
そして、図30に示す信号検索装置は、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)θ1を下回るデータベース信号中の箇所を出力する。 The signal search apparatus shown in FIG. 30 receives a query signal, that is, an acoustic signal to be searched as a sample, and a database signal, that is, an acoustic signal to be searched, and inputs a distance from the query signal in advance (this is a search threshold value). The portion in the database signal below θ1 is output.
次に、図30、図38〜図42を参照して、図30に示す信号検索装置の動作を説明する。なお上述のクエリ特徴抽出部101、データベース特徴抽出部102、信号検出判定部108の処理については、図16〜図24を用いて説明した第2実施形態と同様である。
Next, the operation of the signal search apparatus shown in FIG. 30 will be described with reference to FIGS. 30 and 38 to 42. The processes of the query
図38はデータベース特徴区分部の処理を示すフローチャートである。
次に図38より、データベース特徴区分部103は、データベース特徴抽出部102の処理を、注目窓をずらしながら繰り返し行って出力されるDBヒストグラム(蓄積ヒストグラム)の系列(特徴系列)を読み込む(ステップS164)。次に、データベース特徴区分部103はヒストグラム系列を区分する(ステップS165)。この区分方法は各種考えられるが、ここでは2つの手法を説明する。 最初の方法では、ヒストグラム系列を予め定められた分割幅にしたがって等分割する。 例えば、分割幅を50としたとき、長さが50フレームの部分ヒストグラム系列(部分特徴系列)が多数作成される。2番目の方法では、部分ヒストグラム系列の各ヒストグラムが、後述の特徴領域抽出部105で導かれる部分ヒストグラム系列を代表するヒストグラムから一定距離以内に存在するように、部分ヒストグラム系列の長さを調節する。具体的には、以下のように行う。まず、部分ヒストグラム系列をある長さに設定し、系列の中から代表ヒストグラムを抽出する。代表ヒストグラムの選び方は、データベース特徴間引き部104の処理に従う。次に、部分ヒストグラム系列の各ヒストグラムに対して、代表ヒストグラムとの距離を計算し、その最大値を求める。部分ヒストグラム系列の長さを1から始め、最大値が予め定められた領域閾値を上回るまで、系列の長さを1つずつ伸ばしながら上記操作を繰り返す。以上が、ヒストグラム区分における2番目の方法である。そしてデータベース特徴区分部103は、分割された部分ヒストグラム系列の集合を出力する(ステップS166)。
FIG. 38 is a flowchart showing the processing of the database feature classification unit.
Next, referring to FIG. 38, the database
図39はデータベース特徴間引き部の処理を示すフローチャートである。次に図39より、データベース特徴間引き部104は、データベース特徴区分部103から出力される部分ヒストグラム系列の集合を読み込む(ステップS167)。次に、データベース特徴間引き部104は、各部分ヒストグラム系列から代表特徴を取り出す(ステップS168)。代表特徴の抽出方法は各種考えられるが、ここでは2つの方法を説明する。最初の方法は、部分ヒストグラム系列の中のいずれか1つのヒストグラムをそのまま代表特徴とする。例えば、部分ヒストグラム系列の先頭のヒストグラムを代表とする。2番目の方法は、部分ヒストグラム系列の中の、ヒストグラムの(ユークリッド距離空間における)重心を計算し、それを代表とする。最後に、代表特徴を元の部分ヒストグラム系列の順に並べ、それを新しい系列とする(ステップS169)。この手順によって導かれた特徴系列を、以下、代表特徴系列と呼ぶ。そしてデータベース特徴間引き部104は代表特徴系列を出力する(ステップS170)。
FIG. 39 is a flowchart showing processing of the database feature thinning unit. Next, referring to FIG. 39, the database
図40は特徴領域抽出部の処理を示すフローチャートである。
次に図40より、特徴領域抽出部105は、データベース特徴区分部103から出力される部分ヒストグラム系列の集合、及びデータベース特徴間引き部104から出力される代表特徴系列を読み込む(ステップS171)。次に、部分ヒストグラム系列の中の各ヒストグラムについて、代表特徴との距離を計算し、その最大値dmaxを計算する(ステップS172)。上記操作により、部分ヒストグラム系列内のヒストグラムが存在する範囲を確定することができ、それは、代表特徴から距離dmaxの範囲内となる。そして、特徴領域抽出部105は、dmaxの集合を出力する(ステップS173)。
FIG. 40 is a flowchart showing the processing of the feature region extraction unit.
Next, referring to FIG. 40, the feature
図41は特徴照合部の処理を示す第2のフローチャートである。
次に図41より、特徴照合部106は、データベース特徴間引き部104から出力される代表特徴系列及びデータベース特徴抽出部102から出力されるクエリ特徴を読み込む(ステップS174)。次に特徴照合部106は、クエリ特徴xQと代表特徴xDとの距離を計算する(ステップS175)。距離尺度は各種用いることができるが、例えば、マンハッタン距離やユークリッド距離を用いる。
FIG. 41 is a second flowchart showing processing of the feature matching unit.
Next, from FIG. 41, the
マンハッタン距離は、 Manhattan distance is
そして、特徴照合部106は、距離d(xQ、xD)を出力する(ステップS176)。
Then, the
図42は距離補正部の処理を示すフローチャートである。
次に図42より、距離補正部107は、特徴領域抽出部105から出力される距離値dmax、及び特徴照合部106から出力される距離値d(xQ、xD)を読み込む(ステップS177)。次に距離補正部107は、補正距離値を計算する。すなわち、d(xQ、xD)−dmaxを計算し、距離値を補正する(ステップS178)。これにより、代表特徴に対応する部分ヒストグラム系列について、その中のヒストグラムとの距離の最小値が得られる。そして距離補正部107は補正後の距離値(補正距離値)を出力する(ステップS179)。
FIG. 42 is a flowchart showing the processing of the distance correction unit.
Next, from FIG. 42, the
[第6実施例]
次に、本発明の第6実施形態について図面を用いて説明する。
図31は、第6の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。本実施形態の信号検索装置は、第5の実施形態の信号検索装置に、セグメント抽出部109と、圧縮写像決定部110と、データベース特徴圧縮部(蓄積特徴圧縮部)111と、クエリ特徴圧縮部(参照特徴圧縮部)112とをさらに備えた構成となっており、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)がθ1を下回るデータベース信号中の箇所を出力する。
[Sixth embodiment]
Next, a sixth embodiment of the present invention will be described with reference to the drawings.
FIG. 31 is a diagram illustrating functional blocks of a signal search apparatus to which the method of the sixth embodiment is applied. The signal search apparatus according to the present embodiment is the same as the signal search apparatus according to the fifth embodiment except that the
セグメント抽出部109は、前記データベース特徴抽出部102が注目窓をずらしながら繰り返し行うことで導いた特徴系列を分割することにより、部分系列であるセグメント(部分信号)を抽出する。また圧縮写像決定部110は、前記セグメント抽出部109から出力された各セグメントから、前記特徴よりも低次元の特徴を算出するための写像を決定する。データベース特徴圧縮部111は、前記セグメント抽出部109から出力されたセグメントに対応する、前記特徴よりも低次元の特徴を、前記圧縮写像決定部110から出力された写像に基づいて算出する。クエリ特徴圧縮部112は、前記クエリ特徴抽出部101から出力された特徴に対応する、前記特徴よりも低次元の特徴を、前記圧縮写像決定部110から出力された写像に基づいて算出する。
The
次に、本実施形態による信号検索装置の処理を、図31及び図43を用いて説明する。
まず、クエリ特徴抽出部101、データベース特徴抽出部102、圧縮写像決定部110、データベース特徴圧縮部111、クエリ特徴圧縮部112の処理は第2の実施形態と同様のため、その説明を省略する。
図43はセグメント抽出部の処理を示すフローチャートである。
セグメント抽出部109は、2つの構成が考えられる。最初の構成は、前述の初期部分信号構成部1のみによる構成である。2番目の構成では、前述の初期部分信号構成部1、部分信号構成選択部2、部分信号再構成部3による構成である。いずれも第2の実施形態の処理と同様のため省略する(ステップS183〜ステップS184)。セグメント抽出部109は、分割されたヒストグラム系列であるセグメントの集合を出力する(ステップS185)。
Next, processing of the signal search apparatus according to the present embodiment will be described with reference to FIGS.
First, the processing of the query
FIG. 43 is a flowchart showing the processing of the segment extraction unit.
The
そしてその後、データベース特徴区分部103〜信号検出判定部108までの処理が行なわれる。なお、このデータベース特徴区分部103〜信号検出判定部108までの処理は第5の実施形態と同様の為省略する。
Thereafter, the processing from the database
[第7実施例]
次に、本発明の第7実施形態について図面を用いて説明する。
図32は、第7の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。本実施形態の信号検索装置は、第6の実施形態の信号検索装置に、距離再計算部113と、信号検出再判定部114とをさらに加えた構成となっており、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)がθ1を下回るデータベース信号中の箇所を出力する。
[Seventh embodiment]
Next, a seventh embodiment of the present invention will be described with reference to the drawings.
FIG. 32 is a diagram illustrating functional blocks of a signal search device to which the method of the seventh embodiment is applied. The signal search apparatus according to the present embodiment has a configuration in which a
ここで、距離再計算部113は、前記信号検出判定部108でクエリ信号が存在すると判定されたデータベース信号の当該場所について、前記クエリ特徴抽出部101から出力された特徴系列と、前記データベース特徴抽出部102から出力された特徴系列との距離を計算する。信号検出再判定部114は、前記距離再計算部113から出力された距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する。
その他の処理は第4の実施形態と同一の為、省略する。
Here, the
The other processes are the same as those in the fourth embodiment, and will be omitted.
[第8実施例]
次に、本発明の第8実施形態について図面を用いて説明する。
図33は、第8の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。本実施形態の信号検索装置は、第7の実施形態の信号検索装置に、スキップ幅計算部118をさらに加えた構成となっており、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)がθ1を下回るデータベース信号中の箇所を出力する。
[Eighth embodiment]
Next, an eighth embodiment of the present invention will be described with reference to the drawings.
FIG. 33 is a diagram illustrating functional blocks of a signal search apparatus to which the method of the eighth embodiment is applied. The signal search apparatus according to the present embodiment has a configuration in which a skip
ここで、スキップ幅計算部118は、前記特徴照合部106から出力された距離に基づいて、データベース特徴圧縮部111から出力される圧縮特徴系列に対して設定される注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動する。処理は第3実施形態と同様である。その他の処理は第7の実施形態と同一のため省略する。なお図33に示す信号検索装置において、距離再計算部113及び信号検出再判定部114は、必要に応じて備えていればよく、必要なければ備えていなくてもよい。
Here, the skip
<実験結果>
次に、第8実施形態による信号検索装置の動作実験結果を説明する。
200時間分の音響信号を蓄積信号とし、これとは別に用意された信号から無作為に選択した15秒の異なる信号200個の参照信号に対して検索を行ない、参照信号が与えられてからの検索に要する時間、及び特徴照合部106の処理の実行回数、すなわち特徴の照合回数を調べた。なお、この時のパラメータは、特徴ベクトルの次元数=7、特徴ベクトルの時間幅=60msec、特徴ベクトルの時間刻み=10msec、ヒストグラムの次元数=128、また圧縮特徴はa=50フレームごとに作成した。また寄与閾値=0.9、探索閾値=85とした。
この実施形態の実験結果、を図48、図49に示す。図48は実験結果を示す第3の説明図である。図49は実験結果を示す第4の説明図である。
横軸はセグメント数、縦軸は検索に要する時間(図48)、及び照合回数(図49)である。セグメント数を10000とするとき、本発明の方法(proposed method)において、検索に要する時間は0.364秒、照合回数は772784回、射影距離を利用せずに照合を行なう方法(projection distance unavaliable)において、検索に要する時間は1.491秒、照合回数は1036493回、従来の方法(特許第3065314号:conventional method)において、検索に要する時間は4.218秒、照合回数は633047回であった。
<Experimental result>
Next, operation experiment results of the signal search apparatus according to the eighth embodiment will be described.
An acoustic signal for 200 hours is used as an accumulation signal, and a search is performed for 200 reference signals of 15 different signals randomly selected from signals separately prepared, and the reference signal is given. The time required for the search and the number of executions of the process of the
The experimental results of this embodiment are shown in FIGS. FIG. 48 is a third explanatory diagram showing experimental results. FIG. 49 is a fourth explanatory diagram showing experimental results.
The horizontal axis represents the number of segments, the vertical axis represents the time required for the search (FIG. 48), and the number of collations (FIG. 49). When the number of segments is 10,000, in the proposed method of the present invention, the time required for the search is 0.364 seconds, the number of collations is 772784, and the collation without using the projection distance (projection distance unavaliable) The time required for the search was 1.491 seconds, the number of verifications was 1036493, and in the conventional method (Japanese Patent No. 30653314: conventional method), the time required for the search was 4.218 seconds and the number of verifications was 630347. .
[第9実施例]
次に、本発明の第9実施形態について図面を用いて説明する。
図34は、第9の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。本実施形態の信号検索装置は、第7の実施形態の信号検索装置に、データベース特徴分類部115と、選択閾値設定部116と、データベース特徴選択部117とをさらに加えた構成となっており、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)がθ1を下回るデータベース信号中の箇所を出力する。
[Ninth embodiment]
Next, a ninth embodiment of the present invention will be described with reference to the drawings.
FIG. 34 is a functional block diagram of a signal search apparatus to which the method of the ninth embodiment is applied. The signal search device of this embodiment has a configuration in which a database
データベース特徴分類部115は、前記データベース特徴抽出部102の処理において、注目窓をずらしながら繰返し行うことで導かれた各特徴を、予め定義された距離に基づいて分類し、その分類の代表特徴を決定する。選択閾値設定部116は、前記データベース特徴分類部115で定義された距離に対する選択閾値を、予め定義された探索閾値から計算する。またデータベース特徴選択部117は、前記データベース特徴分類部115から出力された分類のうち、前記クエリ特徴抽出部101から出力された特徴との距離が、前記選択閾値設定部116から出力された選択閾値から導かれる条件を満たすような分類に含まれる特徴を選択する。
The database
次に、本実施形態による信号検索装置の処理を、図34及び図44〜図47を用いて説明する。まず、クエリ特徴抽出部101、データベース特徴抽出部102の処理は第7の実施形態と同様の為、その説明を省略する。
図44はデータベース特徴分類部の処理を示すフローチャートである。そして図44より、次に、データベース特徴分類部115が、データベース特徴抽出部102が注目窓をずらしながら繰り返し行って出力したヒストグラムの系列を読み込む(ステップS210)。次に、ヒストグラム系列の各ヒストグラムを、例えば、ユークリッド距離に従って分類する(ステップS211)。ヒストグラムの分類は、各ヒストグラムを、そのビンの数と等しい次元数を持ったベクトルと考えて、そのベクトルをベクトル量子化を用いて符号化することによって行う。例えば、ベクトル量子化の符号語数が1024個であれば、ヒストグラムを1024個の集合(これをクラスタと呼ぶ)のいずれか1つに分類されることになる。そして、各クラスタに所属するヒストグラムの重心となるヒストグラム(重心ヒストグラムと呼ぶ)によって、クラスタを代表させることにする。このとき、クラスタは、それに所属するヒストグラムと重心ヒストグラムとの距離の総和が最小になるように、かつそのクラスタに所属するヒストグラムについて、所属するクラスタの重心ヒストグラムとの距離が、他のどのクラスタの重心ヒストグラムとの距離よりも小さくなるように構成される。そしてデータベース特徴分類部115は、ヒストグラムの分類であるクラスタの集合を出力する(ステップS212)。
Next, processing of the signal search apparatus according to the present embodiment will be described with reference to FIGS. 34 and 44 to 47. First, since the processing of the query
FIG. 44 is a flowchart showing the processing of the database feature classification unit. Next, referring to FIG. 44, the database
図45は選択閾値設定部の処理を示すフローチャートである。
次に図45より、選択閾値設定部116が探索閾値θ1を読み込み(ステップS213)、その探索閾値θ1から選択閾値θ2を算出する(ステップS214)。ここで選択閾値とは、検索すべき信号に対応するDBヒストグラムを含む可能性のあるクラスタを選択する際の、クエリヒストグラムとクラスタとの距離の上限を指す。照合の際の距離尺度がユークリッド距離である場合、選択閾値は探索閾値と同じ値にする。分類・選択で用いる尺度と共通であるので、検索漏れを生じることはない。照合の際の距離尺度がマンハッタン距離である場合、パラメータpを用いて、以下のように選択閾値を設定する。
FIG. 45 is a flowchart showing processing of the selection threshold setting unit.
Next, referring to FIG. 45, the selection threshold
図46はデータベース特徴選択部の処理を示す図である。
次に図46より、データベース特徴選択部117が、クエリ特徴抽出部101から出力されるクエリヒストグラム、データベース特徴分類部115から出力されるヒストグラムの分類(クラスタ)、及び選択閾値設定部116から出力される選択閾値を読み込む(ステップS216)。次に、読み込んだクエリヒストグラムと、データベース信号側の各クラスタの重心ヒストグラムとの(ユークリッド)距離を計算する(ステップS217)。
続いて、計算された距離に基づき、探索するべき信号に対応するヒストグラムを含む可能性のあるクラスタを選択する(ステップS218)。この原理を以下に説明する。
ここで図47は、Q、C1、C2の3点が載るような平面でヒストグラム空間(上記の例では128次元)を切り出した様子を示す図である。ここで、Qはクエリヒストグラム、C1はヒストグラムQが所属しているクラスタの重心ヒストグラム、C2は他のクラスタの重心ヒストグラムを表し、dQ1、dQ2、d12はそれぞれ、QとC1との距離、QとC2との距離、C1とC2との距離を示す。ここで、ヒストグラムQからの距離がd以内であるヒストグラムに対応するデータベース信号の箇所を検出しなければならないとすると、Qを中心とする半径dの超球(図47においては円)の内部にあるヒストグラムが検出すべきデータベース信号の箇所と対応する。Qを中心とする超球の半径がdθより大きくなったとき、C2に代表されるクラスタに属するヒストグラムの中に、検出すべきデータベース信号の箇所と対応するヒストグラムが含まれている可能性がある。そこで、選択閾値θ2がdθより大きくなったとき、C2に代表されるクラスタを選択する。
dθは次のようにして求められる。図47より、次の式が成り立つ。
FIG. 46 is a diagram showing processing of the database feature selection unit.
46, the database
Subsequently, based on the calculated distance, a cluster that may include a histogram corresponding to the signal to be searched is selected (step S218). This principle will be described below.
FIG. 47 is a diagram showing a state in which the histogram space (128 dimensions in the above example) is cut out on a plane on which three points Q, C1, and C2 are placed. Here, Q is a query histogram, C1 is a centroid histogram of a cluster to which the histogram Q belongs, C2 is a centroid histogram of another cluster, dQ1, dQ2, and d12 are distances between Q and C1, Q and The distance between C2 and the distance between C1 and C2 are shown. Here, if it is necessary to detect the location of the database signal corresponding to the histogram whose distance from the histogram Q is within d, it is inside a hypersphere (circle in FIG. 47) having a radius d centered on Q. A histogram corresponds to the location of the database signal to be detected. When the radius of the hypersphere centered at Q is larger than dθ, there is a possibility that the histogram corresponding to the location of the database signal to be detected is included in the histogram belonging to the cluster represented by C2. . Therefore, when the selection threshold θ2 is larger than dθ, a cluster represented by C2 is selected.
dθ is obtained as follows. From FIG. 47, the following equation is established.
そして、セグメント抽出部109〜データベース特徴圧縮部111の処理、データベース特徴区分部103〜信号検出判定部108及び距離再計算部113、信号検出再判定部114の処理が行なわれる。なお、これらの処理は第7の実施形態と同様である。距離再計算部113及び信号検出再判定部114は、必要に応じて備えていれば良く、必要なければ備えなくともよい。
Then, the processing of the
次に、クエリ特徴圧縮部112が、データベース特徴選択手段17から出力されたデータベース信号中の箇所、クエリ特徴抽出部101から出力されるクエリヒストグラム及び圧縮写像決定部110から出力される線形写像の集合を読み込む。次に、ヒストグラムを、各線形写像を用いて、対応する部分空間への写像を行う。写像は、データベース特徴選択部117から出力された箇所で用いられている。そして線形写像のみ行なえば十分であり、全ての線形写像に対して行なう必要はない。これにより処理時間を削減するという特異な効果を生む。
Next, the query
[第10実施例]
次に、本発明の第10実施形態について図面を用いて説明する。
図35は、第10の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。本実施形態の信号検索装置は、第9の実施形態の信号検索装置に、スキップ幅計算部118とをさらに加えた構成となっており、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)がθ1を下回るデータベース信号中の箇所を出力する。
スキップ幅計算部118は、前記距離補正部107から出力された距離に基づいて、注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動する。なお、スキップ幅計算部118の処理は、第3の実施形態と同様のため省略する。
[Tenth embodiment]
Next, a tenth embodiment of the present invention will be described with reference to the drawings.
FIG. 35 is a functional block diagram of a signal search apparatus to which the method of the tenth embodiment is applied. The signal search device of this embodiment has a configuration in which a skip
The skip
<実験結果>
次に、本実施形態による信号検索装置の動作実験結果を説明する。
ここで実験条件は第7の実施形態と同様である。その他のパラメータとして、クラスタ数を1024と設定した。
本実験の結果を、図50、図51に示す。図50は実験結果を示す第5の説明図である。図51は実験結果を示す第6の説明図である。ここで横軸はセグメント数、縦軸は検索に要する時間(図50)、及び照合回数(図51)である。セグメント数を10000とするとき、本実施形態の方法において、検索に要する時間は0.234秒、照合回数は305351回、特徴圧縮のみを実施した方法(using feature compression)において、検索に要する時間は0.364秒、照合回数は772784回、従来の方法(Time-series Active Search)において、検索結果に要する時間は4.218秒、照合回数は633047回であった。
<Experimental result>
Next, an operation experiment result of the signal search apparatus according to the present embodiment will be described.
Here, the experimental conditions are the same as in the seventh embodiment. As another parameter, the number of clusters was set to 1024.
The results of this experiment are shown in FIGS. FIG. 50 is a fifth explanatory diagram showing experimental results. FIG. 51 is a sixth explanatory diagram showing experimental results. Here, the horizontal axis represents the number of segments, and the vertical axis represents the time required for the search (FIG. 50) and the number of collations (FIG. 51). When the number of segments is 10,000, in the method of the present embodiment, the time required for the search is 0.234 seconds, the number of matching times is 305351, and in the method using only feature compression (using feature compression), the time required for the search is In the conventional method (Time-series Active Search), the time required for the search result was 4.218 seconds, and the number of collations was 633047.
[第11実施例]
次に、本発明の第11実施形態について図面を用いて説明する。
図36は、第11の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。本実施形態の信号検索装置は、第5の実施形態の信号検索装置に、距離再計算部113と、信号検出再判定部114と、データベース特徴分類部115と、選択閾値設定部116と、データベース特徴選択部117とを加えた構成になっており、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)がθ1を下回るデータベース信号中の箇所を出力する。
なお、本実施形態の処理は、上述した第5の実施形態で記述したクエリ特徴抽出部101における処理、データベース特徴抽出部102における処理の後、上述の第9の実施形態で記述したデータベース特徴分類部115におけるステップS210〜ステップS212、選択閾値設定部116におけるステップS213〜ステップS215、データベース特徴選択部117におけるステップS216〜ステップS220の処理が行なわれる。
そして、次に、第5の実施形態で記述したデータベース特徴区分部103におけるステップS164〜ステップS166、データベース特徴間引き部104におけるステップS167〜ステップS170、特徴領域抽出部105におけるステップS171〜ステップS173の処理が行なわれる。そして、次に特徴照合部106が、データベース特徴間引き部104から出力される代表特徴系列及びデータベース特徴選択部117から出力されるクエリ特徴を読み込んで、ステップS174〜ステップS176の処理を行なう。その後、第5の実施形態で記述した距離補正部107におけるステップS177〜ステップS179の処理、信号検出判定部108における処理と、第7の実施形態で記述した距離再計算部113、信号検出再判定部114の処理が行なわれる。なお、距離再計算部113及び信号検出再判定部114は、必要に応じて備えていれば良く、必要なければ備えなくともよい。
[Eleventh embodiment]
Next, an eleventh embodiment of the present invention will be described with reference to the drawings.
FIG. 36 is a diagram illustrating functional blocks of a signal search device to which the method of the eleventh embodiment is applied. The signal search apparatus according to the present embodiment is the same as the signal search apparatus according to the fifth embodiment except that a
Note that the processing of the present embodiment is the database feature classification described in the ninth embodiment after the processing in the query
Then, the processing from step S164 to step S166 in the database
[第12実施例]
次に、本発明の第12実施形態について図面を用いて説明する。
図37は、第12の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。本実施形態の信号検索装置は、第11の実施形態の信号検索装置に、スキップ幅計算部118をさらに加えた構成になっており、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)がθ1を下回るデータベース信号中の箇所を出力する。
ここで、スキップ幅計算部118は、前記距離補正部107から出力された距離に基づいて、データベース特徴抽出部102から出力されるDBヒストグラムの系列に対して設定される注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動する。その他の処理は第11の実施形態と同様である。
[Twelfth embodiment]
Next, a twelfth embodiment of the present invention will be described with reference to the drawings.
FIG. 37 is a diagram illustrating functional blocks of a signal search device to which the method of the twelfth embodiment is applied. The signal search apparatus according to the present embodiment is configured by further adding a skip
Here, the skip
[第13実施例]
次に、本発明の第13実施形態について図面を用いて説明する。
本実施形態は様々な処理対象信号を用いることができるが、ここでは、該処理対象信号の一例として音響信号を用いる。
図52は、第13の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。図52より、本実施形態の信号検索装置は、クエリ特徴抽出部101と、データベース特徴抽出部102と、データベース特徴分類部115と、選択閾値設定部116と、データベース特徴選択部17と、セグメント抽出部109と、圧縮写像決定部110と、データベース特徴圧縮部111と、クエリ特徴圧縮部112と、特徴照合部106と、信号検出判定部8とで構成される。
[Thirteenth embodiment]
Next, a thirteenth embodiment of the present invention will be described with reference to the drawings.
Although various processing target signals can be used in the present embodiment, here, an acoustic signal is used as an example of the processing target signal.
FIG. 52 is a diagram illustrating functional blocks of a signal search device to which the method of the thirteenth embodiment is applied. 52, the signal search apparatus according to this embodiment includes a query
そして図52に示す信号検索装置は、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)θ1を下回るデータベース信号中の箇所を出力する。 The signal search apparatus shown in FIG. 52 receives a query signal, that is, a sample acoustic signal to be searched, and a database signal, that is, a searched acoustic signal, and sets a distance from the query signal in advance (this is called a search threshold). ) Output the location in the database signal below θ1.
なお、クエリ特徴抽出部101はクエリ信号から特徴を導く。データベース特徴抽出部102は、データベース信号に注目窓を設定し、注目窓をずらしながら特徴を導く。またデータベース特徴分類部115は、前記データベース特徴抽出部102による処理を、注目窓をずらしながら繰返し行うことで導かれた各特徴を、予め定義された距離に基づいて分類し、その分類の代表特徴を決定する。選択閾値設定部116は、前記データベース特徴分類部115で定義された距離に対する選択閾値を、予め定義された探索閾値から計算する。データベース特徴選択部117は、前記データベース特徴分類部115から出力された分類について、前記クエリ特徴抽出部101から出力された特徴との距離が、前記選択閾値設定部116から出力された選択閾値から導かれる条件を満たすような分類に含まれる特徴を選択する。
Note that the query
またセグメント抽出部109は、前記データベース特徴抽出部102を注目窓をずらしながら繰り返し行うことで導かれた特徴系列を分割することにより、部分系列であるセグメントを抽出する。圧縮写像決定部110は、前記セグメント抽出部109から出力された各セグメントから、前記特徴よりも低次元の特徴を算出するための写像を決定する。データベース特徴圧縮部111は、前記セグメント抽出部109から出力されたセグメントに対応する、前記特徴よりも低次元の特徴を、前記圧縮写像決定部110から出力された写像に基づいて算出する。クエリ特徴圧縮部112は、前記クエリ特徴抽出部101から出力された特徴に対応する、前記特徴よりも低次元の特徴を、前記圧縮写像決定部110から出力された写像に基づいて算出する。
The
また特徴照合部106は、前記データベース特徴選択部117の出力したデータベース信号中の箇所に対して、前記データベース特徴圧縮部111から出力された圧縮特徴系列と、前記クエリ特徴圧縮部112から出力された圧縮特徴系列との距離を計算する。信号検出判定部108は、特徴照合部106から出力された距離と、前記距離に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する。
In addition, the
次に、本実施形態による信号検索装置の処理を、図52、図55を用いて説明する。
クエリ特徴抽出部101、データベース特徴抽出部102の処理は第2の実施形態と同様である。またデータベース特徴分類部115、選択閾値設定部116、データベース特徴選択部117の処理は第9の実施形態と同様である。またセグメント抽出部109の処理は第6の実施形態と同様である。また圧縮写像決定部110、データベース特徴圧縮部111、特徴照合部106、信号検出部108の処理は第2の実施形態と同様である。またクエリ特徴圧縮部112の処理は第9の実施形態と同様である。
Next, processing of the signal search apparatus according to the present embodiment will be described with reference to FIGS.
The processing of the query
[第14実施例]
次に、本発明の第14実施形態について図面を用いて説明する。
図53は、第14の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。本実施形態の信号検索装置は、第13の実施形態の信号検索装置に、距離再計算部113と、信号検出再判定部114とをさらに加えた構成となっており、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)がθ1を下回るデータベース信号中の箇所を出力する。
[14th embodiment]
Next, a fourteenth embodiment of the present invention will be described with reference to the drawings.
FIG. 53 is a diagram illustrating functional blocks of a signal search device to which the method of the fourteenth embodiment is applied. The signal search apparatus according to the present embodiment is configured by further adding a
ここで、距離再計算部113は、前記信号検出判定部108でクエリ信号が存在すると判定されたデータベース信号の当該場所について、前記クエリ特徴抽出部101から出力された特徴系列と、前記データベース特徴抽出部102から出力された特徴系列との距離を計算する。信号検出再判定部114は、前記距離再計算部113から出力された距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する。
なお、距離再計算部113と信号検出再判定部114の処理は第4の実施形態と同様である。
また、クエリ特徴抽出部101、データベース特徴抽出部102、データベース特徴分類部115、選択閾値設定部116、データベース特徴選択部117、セグメント抽出部109、圧縮写像決定部110、データベース特徴圧縮部111、クエリ特徴圧縮部112、特徴照合部106、信号検出判定部108の処理は、第13の実施形態と同様の為、その説明を省略する。
Here, the
Note that the processing of the
The query
[第15実施例]
次に、本発明の第15実施形態について図面を用いて説明する。
図54は、第15の実施形態の方法を適用した信号検索装置の機能ブロックを示す図である。本実施形態の信号検索装置は、第14の実施形態の信号検索装置に、スキップ幅計算部118とをさらに加えた構成となっており、クエリ信号すなわち見本となる検索したい音響信号と、データベース信号すなわち検索される音響信号を入力とし、クエリ信号との距離が予め設定した値(これを探索閾値という)がθ1を下回るデータベース信号中の箇所を出力する。
スキップ幅計算部118は、前記特徴照合部106から出力された距離に基づいて、注目窓のスキップ幅を計算し、そのスキップ幅だけ注目窓を移動する。
[15th embodiment]
Next, a fifteenth embodiment of the present invention is described with reference to the drawings.
FIG. 54 is a diagram illustrating functional blocks of a signal search apparatus to which the method of the fifteenth embodiment is applied. The signal search apparatus according to the present embodiment is configured by further adding a skip
The skip
次に、本実施形態による信号検索装置の処理を説明する。
まず、クエリ特徴抽出部101、データベース特徴抽出部102、データベース特徴分類部115、選択閾値設定部116、データベース特徴選択部117、セグメント抽出部109、圧縮写像決定部110、データベース特徴圧縮部111、クエリ特徴圧縮部112の処理は、特徴照合部106、信号検出判定部108、距離再計算部113、信号検出再判定部114の処理は、第13、14の実施形態と同様の為、その説明を省略する。またスキップ幅計算部118の処理は第3の実施形態と同様である。
Next, processing of the signal search apparatus according to the present embodiment will be described.
First, the query
<実験結果>
次に第5の実施形態を適用した装置の動作実験例を示す。
本発明の効果を確認するため、まず、約10時間の音響信号からヒストグラムを作成したものをデータベース信号とし、圧縮特徴をファイルに書き込んだ場合のファイルサイズ、探索時間、及び特徴照合回数を調べた。探索のパラメータは、音響信号のサンプリング周波数=33kHz、特徴ベクトルの次元数=7、特徴ベクトルの時間幅=60ミリ秒、、特徴ベクトルの時間刻み=10ミリ秒、ヒストグラムの次元数=128、時間窓の幅=15秒、寄与閾値=0.9、セグメント数=200、探索閾値=85とした。特徴間引きにおいて、系列の区分は等分割で行い、代表特徴は部分ヒストグラム系列の先頭をそのまま用いた。照合の際の距離尺度はユークリッド距離とした。
<Experimental result>
Next, an operation example of the apparatus to which the fifth embodiment is applied will be shown.
In order to confirm the effect of the present invention, first, a database created from a histogram generated from an acoustic signal of about 10 hours was used as a database signal, and the file size, search time, and number of feature matching when a compressed feature was written to a file were examined . The search parameters are: acoustic signal sampling frequency = 33 kHz, feature vector dimension = 7, feature vector time width = 60 ms, feature vector time increment = 10 ms, histogram dimension = 128, time Window width = 15 seconds, contribution threshold = 0.9, number of segments = 200, search threshold = 85. In the feature thinning, the series is divided into equal parts, and the head of the partial histogram series is used as it is as the representative feature. The distance scale used for matching was Euclidean distance.
図56は実験結果を示す第7の説明図である。図57は実験結果を示す第9の説明図である。部分ヒストグラム系列の幅を10から50まで10ずつ変化させたときの実験結果を、図56及び図57に示す。グラフの横軸は部分ヒストグラム系列の幅a、縦軸はそれぞれファイルサイズ(図56)、照合箇所の数(図57左側)、探索時間(図57右側)である。a=0は、すなわち、本発明の方法を用いない場合である。
図56及び図57より、部分ヒストグラム系列の幅を大きくすることによって、ファイルサイズ及び照合箇所の数が単調に減少している。また、図57より、照合箇所の数の減少にともなって探索時間も削減されている。a=40を境に探索時間が増加に転じるのは、特徴の存在範囲が拡大することによってヒストグラムによる再照合を行う必要がある箇所が増加するためである。
以上のことから、a=40が最適な部分ヒストグラム系列の幅であると考えられ、その時のファイルサイズは5.8メガバイト(本発明を用いない場合の約1/30)、探索時間は23ミリ秒(本発明を用いない場合の約60%)、照合箇所の数は41855回(本発明を用いない場合の約85%)であった。
FIG. 56 is a seventh explanatory diagram showing experimental results. FIG. 57 is a ninth explanatory diagram showing experimental results. 56 and 57 show the experimental results when the width of the partial histogram series is changed by 10 from 10 to 50. FIG. The horizontal axis of the graph is the width a of the partial histogram series, and the vertical axis is the file size (FIG. 56), the number of matching points (left side of FIG. 57), and the search time (right side of FIG. 57). a = 0 is the case where the method of the present invention is not used.
56 and 57, the file size and the number of collation points are monotonously decreased by increasing the width of the partial histogram series. In addition, as shown in FIG. 57, the search time is reduced as the number of collation points is reduced. The reason why the search time starts to increase after a = 40 is that the number of points that need to be re-matched by the histogram increases as the existence range of the features expands.
From the above, it is considered that a = 40 is the optimum width of the partial histogram series, the file size at that time is 5.8 megabytes (about 1/30 when the present invention is not used), and the search time is 23 mm. Seconds (about 60% when the present invention is not used), the number of collation points is 41855 (about 85% when the present invention is not used).
以上、説明したように、本発明によれば、予めデータベース信号の特徴を間引いて時間方向に圧縮することによって、検索漏れが生じないことを保証しながら大幅にインデックスの数量を削減し、公知の方法に比較して、より高速な信号検索を行うことができるという利点がある。 As described above, according to the present invention, the number of indexes can be significantly reduced while guaranteeing that no search omission occurs by thinning out the features of the database signal in advance and compressing in the time direction. Compared to the method, there is an advantage that signal search can be performed at higher speed.
なお、図1から図4における各処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより信号圧縮処理または信号検索処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、OSや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、WWWシステムを利用している場合であれば、ホームページ提供環境(あるいは表示環境)も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ROM、CD−ROM等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ(RAM)のように、一定時間プログラムを保持しているものも含むものとする。 1 to 4 is recorded on a computer-readable recording medium, and the program recorded on the recording medium is read into a computer system and executed. Signal compression processing or signal search processing may be performed. The “computer system” here includes an OS and hardware such as peripheral devices. Further, the “computer system” includes a homepage providing environment (or display environment) if a WWW system is used. The “computer-readable recording medium” refers to a storage device such as a flexible medium, a magneto-optical disk, a portable medium such as a ROM and a CD-ROM, and a hard disk incorporated in a computer system. Further, the “computer-readable recording medium” refers to a volatile memory (RAM) in a computer system that becomes a server or a client when a program is transmitted via a network such as the Internet or a communication line such as a telephone line. In addition, those holding programs for a certain period of time are also included.
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク(通信網)や電話回線等の通信回線(通信線)のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル(差分プログラム)であっても良い。 The program may be transmitted from a computer system storing the program in a storage device or the like to another computer system via a transmission medium or by a transmission wave in the transmission medium. Here, the “transmission medium” for transmitting the program refers to a medium having a function of transmitting information, such as a network (communication network) such as the Internet or a communication line (communication line) such as a telephone line. The program may be for realizing a part of the functions described above. Furthermore, what can implement | achieve the function mentioned above in combination with the program already recorded on the computer system, and what is called a difference file (difference program) may be sufficient.
1・・・初期部分信号構成部 2・・・部分信号構成選択部 3・・・部分信号再構成部 4、110・・・圧縮写像決定部 5・・・信号圧縮部 6・・・参照特徴抽出部 7・・・蓄積特徴抽出部 8・・・参照特徴圧縮部 9・・・圧縮特徴間距離計算部 10、108・・・信号検出判定部 11、118・・・スキップ幅計算部 12、113・・・距離再計算部 13、114・・・信号検出再判定部 51・・・信号写像部 52・・・射影距離計算部 53・・・圧縮特徴構成部 101・・・クエリ特徴抽出部 102・・・データベース特徴抽出部 103・・・データベース特徴区分部 104・・・データベース特徴間引き部 105・・・特徴領域抽出部 106・・・特徴照合部 107・・・距離補正部 109・・・セグメント抽出部 111・・・データベース特徴圧縮部 112・・・クエリ特徴圧縮部 115・・・データベース特徴分類部 116・・・選択閾値設定部 117・・・データベース特徴選択部
DESCRIPTION OF
Claims (30)
クエリ信号から多次元ベクトルとして表現されるクエリ特徴を導くクエリ特徴抽出過程と、
データベース信号に注目窓を設定し、注目窓内の信号から、多次元ベクトルとして表現されるデータベース特徴を導き、これらの処理を、注目窓をずらしながら繰り返し行うことで多次元ベクトルの系列として表現されるデータベース特徴系列を導くデータベース特徴抽出過程と、
前記データベース特徴抽出過程で導かれたデータベース特徴系列を系列の順序に従って区分することで、データベース部分特徴系列を導くデータベース特徴区分過程と、
前記データベース特徴区分過程で導かれた各データベース部分特徴系列から、そのデータベース部分特徴系列を代表する特徴であるデータベース代表特徴を抽出し、前記データベース特徴抽出過程で導かれたデータベース特徴系列より少ない数の特徴で構成されるデータベース代表特徴系列を導くデータベース特徴間引き過程と、
前記データベース特徴区分過程で導かれた各データベース部分特徴系列中の各要素と前記データベース特徴間引き過程で導かれたデータベース代表特徴との距離の最大値dmaxを計算し、前記データベース代表特徴から前記距離の最大値dmaxの範囲内の領域であるデータベース特徴存在領域を導く特徴領域抽出過程と、
前記クエリ特徴抽出過程で導かれたクエリ特徴と、前記データベース特徴間引き過程で導かれたデータベース代表特徴系列に含まれるある特定位置のデータベース代表特徴との距離を計算する特徴照合過程と、
前記特徴照合過程で計算された距離から、前記特徴領域抽出過程で導かれた距離の最大値dmaxを差し引いたものを補正後の距離値とする距離補正過程と、
前記距離補正過程で導かれた補正距離値と、その補正距離値に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する信号検出判定過程とを有し、
前記特徴照合過程から前記信号検出判定過程による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する
ことを特徴とする信号検索方法。 A signal search method for searching for a portion similar to a query signal that is a target time series signal from a database signal that is a time series signal registered in advance,
A query feature extraction process that derives query features expressed as multidimensional vectors from the query signal;
A database window is set in the database signal, database features expressed as multidimensional vectors are derived from the signal in the window of interest, and these processes are repeated while shifting the window of interest to be expressed as a series of multidimensional vectors. Database feature extraction process to derive a database feature sequence
A database feature classification process for deriving a database partial feature series by classifying the database feature series derived in the database feature extraction process according to the sequence order;
A database representative feature, which is a feature representing the database partial feature series, is extracted from each database partial feature series derived in the database feature classification process, and is less in number than the database feature series derived in the database feature extraction process. A database feature decimation process for deriving a database representative feature sequence composed of features;
The maximum value dmax of the distance between each element in each database partial feature series derived in the database feature classification process and the database representative feature derived in the database feature thinning process is calculated, and the distance of the distance is calculated from the database representative feature. A feature region extraction process for deriving a database feature existing region that is a region within the maximum value dmax ;
A feature matching process for calculating a distance between the query feature derived in the query feature extraction process and a database representative feature at a specific position included in the database representative feature sequence derived in the database feature thinning process;
A distance correction process in which a distance value after correction is obtained by subtracting the maximum value dmax of the distance derived in the feature region extraction process from the distance calculated in the feature matching process;
A signal for determining whether or not the query signal is present at the relevant part of the database signal by comparing the corrected distance value derived in the distance correction process with a search threshold value that is a threshold value corresponding to the corrected distance value. A detection determination process,
The processing from the feature matching process to the signal detection determination process is repeated while shifting the position in the database representative feature series, and the distance from the query signal is calculated for several locations of the database signal. A signal search method characterized by determining whether or not the signal exists at the corresponding portion of the signal.
ことを特徴とする請求項1に記載の信号検索方法。 The signal search method according to claim 1, wherein in the database feature thinning-out process, a database feature at the head of the database feature series derived in the database feature classification process is used as a database representative feature.
ことを特徴とする請求項1に記載の信号検索方法。 The signal search method according to claim 1, wherein, in the database feature thinning-out process, a database feature centroid of the database feature in the database feature series derived in the database feature classification process is used as a database representative feature.
ことを特徴とする請求項1から請求項3のいずれかに記載の信号検索方法。 The signal search according to any one of claims 1 to 3, wherein, in the database feature classification process, the database feature series derived in the database feature extraction process is equally divided by a predetermined length. Method.
ことを特徴とする請求項1から請求項4のいずれかに記載の信号検索方法。 In the database feature classification process, the database feature sequence derived in the database feature extraction process is divided so that a database feature existing area derived in the feature area extraction process is smaller than a predetermined maximum area. The signal search method according to any one of claims 1 to 4.
前記セグメント抽出過程で得られた各データベース特徴セグメントから,前記特徴よりも低次元の特徴を算出するための写像を決定する圧縮写像決定過程と、
前記セグメント抽出過程で得られた各データベース特徴セグメントに対応する前記圧縮写像決定過程で得られた射影変換を、該データベース特徴セグメントに含まれる各データ特徴に対して行うことにより、該データベース圧縮特徴に対応する圧縮特徴であるデータベース圧縮特徴の系列であるデータベース圧縮特徴系列を導くデータベース特徴圧縮過程と、
前記クエリ特徴抽出過程で得られたクエリ特徴に対し、前記圧縮写像決定過程で得られた射影変換を行うことにより、該クエリ特徴に対する圧縮特徴であるクエリ圧縮特徴を抽出するクエリ特徴圧縮過程と
を有し、
前記データベース特徴間引き過程において、前記データベース特徴圧縮過程で導かれたデータベース圧縮特徴系列を入力としてデータベース代表特徴系列を導き、前記特徴照合過程において、クエリ特徴圧縮過程で導かれたクエリ圧縮特徴をクエリ特徴の代わりに用いて照合を行い、さらに、特徴照合過程から信号検出判定過程による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する
ことを特徴とする請求項1から請求項5のいずれかに記載の信号検索方法。 A segment extraction step of extracting a database feature segment that is a partial sequence having a shorter length than the database feature sequence by dividing the database feature sequence derived in the database feature extraction step according to the sequence order;
A compressed map determination step for determining a map for calculating a feature having a lower dimension than the feature from each database feature segment obtained in the segment extraction step;
By performing the projective transformation obtained in the compression mapping determination process corresponding to each database feature segment obtained in the segment extraction process on each data feature included in the database feature segment, the database compressed feature is obtained. A database feature compression process that derives a database compression feature sequence that is a sequence of database compression features that are corresponding compression features;
A query feature compression step of extracting a query compression feature that is a compression feature for the query feature by performing a projective transformation obtained in the compression mapping determination step on the query feature obtained in the query feature extraction step. Have
In the database feature decimation process, a database representative feature sequence is derived using the database compressed feature sequence derived in the database feature compression process as an input, and in the feature matching process, the query compressed feature derived in the query feature compression process is used as a query feature. In addition, the process from the feature matching process to the signal detection determination process is repeated while shifting the position in the database representative feature sequence, and the distance from the query signal at several points in the database signal. The signal search method according to claim 1, further comprising: determining whether or not the query signal is present at the location of the database signal.
前記セグメント抽出過程で得られたデータベース特徴セグメントに含まれる各データベース特徴を、該データベース特徴セグメントに対応する前記圧縮写像決定過程で得られた射影変換によって写像するデータベース特徴写像過程と、
前記データベース特徴写像過程で導かれた写像後の各データベース特徴について、対応する前記データベース特徴との距離を計算し、これをデータベース射影距離とするデータベース射影距離計算過程と、
前記データベース特徴写像過程で導かれた写像後の各データベース特徴と、その写像後のデータベース特徴に対応して前記データベース射影距離計算過程で導かれたデータベース射影距離とを対にして、データベース圧縮特徴を構成するデータベース圧縮特徴構成過程と
を有し、
前記クエリ特徴圧縮過程は、
前記クエリ特徴抽出過程で得られたクエリ特徴を、前記圧縮写像決定過程で得られた射影変換によって写像するクエリ特徴写像過程と、
前記クエリ特徴写像過程で導かれた写像後の各クエリ特徴について、前記クエリ特徴との距離を計算し、これをクエリ射影距離とするクエリ射影距離計算過程と、
前記クエリ特徴写像過程で導かれた写像後の各クエリ特徴と、その写像後のクエリ特徴に対応して前記クエリ射影距離計算過程で導かれたクエリ射影距離とを対にして、クエリ圧縮特徴を構成するクエリ圧縮特徴構成過程と、
を有することを特徴とする請求項6に記載の信号検索方法。 The database feature compression process includes:
A database feature mapping process in which each database feature included in the database feature segment obtained in the segment extraction process is mapped by a projective transformation obtained in the compressed map determination process corresponding to the database feature segment;
For each database feature after mapping derived in the database feature mapping process, calculate a distance from the corresponding database feature, and use this as a database projection distance, a database projection distance calculation process,
A database compression feature is obtained by pairing each database feature after mapping derived in the database feature mapping process with a database projection distance derived in the database projection distance calculation process corresponding to the database feature after the mapping. A database compression feature composition process to configure,
The query feature compression process includes:
A query feature mapping process for mapping the query feature obtained in the query feature extraction process by a projective transformation obtained in the compression mapping determination process;
For each query feature after mapping derived in the query feature mapping process, a distance to the query feature is calculated, and this is used as a query projection distance.
Each query feature after mapping derived in the query feature mapping process and a query projection distance derived in the query projection distance calculation process corresponding to the query feature after the mapping are paired to obtain a query compression feature. Configuring query compression feature composition process;
The signal search method according to claim 6, further comprising:
前記距離再計算過程で導かれた距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する信号検出再判定過程と
を有し、
前記特徴照合過程、距離補正過程、信号検出判定過程、信号再計算過程及び信号検出再判定過程による処理を、データベース圧縮特徴系列もしくはデータベース特徴系列の中の位置をずらしながら繰り返して、データベース圧縮特徴系列もしくはデータベース特徴系列のいくつかの箇所について、クエリ信号特徴もしくはクエリ特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する
ことを特徴とする請求項1から請求項7のいずれかに記載の信号検索方法。 The database feature in the database feature sequence derived in the database feature extraction process corresponding to the location in the database signal determined to have a query signal in the signal detection determination process, and the query feature A distance recalculation process to calculate the distance from the query feature derived in the extraction process;
A signal detection re-determination step for re-determining whether a query signal is present at the location of the database signal by comparing the distance derived in the distance re-calculation step with a search threshold;
The database compression feature sequence is repeated by shifting the processing in the feature matching process, the distance correction process, the signal detection determination process, the signal recalculation process, and the signal detection redetermination process while shifting the position in the database compression feature series or the database feature series. Alternatively, the query signal feature or the distance from the query feature is calculated for several locations of the database feature series, and it is determined whether or not the query signal is present at the location of the database signal. The signal search method according to claim 7.
前記データベース特徴分類過程で定義された距離尺度に対する選択閾値を、予め定められた探索閾値を基準として計算する選択閾値設定過程と、
前記データベース特徴分類過程で導かれた分類のうち、該分類に対応する分類代表特徴と、前記クエリ特徴抽出過程で導かれたクエリ特徴との距離が、前記選択閾値設定過程で計算された選択閾値と、該クエリ特徴を前記データベース特徴分類過程と同様の方法により分類した際に所属する分類に対応する分類代表特徴とから導かれる条件を満たすような代表特徴を持つ分類を検出し、該分類に含まれるデータベース特徴を選択するデータベース特徴選択過程と、
を有し、
前記特徴照合過程において、前記データベース特徴選択過程において選択されたデータベース特徴もしくは該データベース特徴に対応する前記データベース特徴圧縮過程で導かれたデータベース圧縮特徴についてのみ、前記クエリ特徴抽出過程で導かれたクエリ特徴もしくは該クエリ特徴に対応する前記クエリ特徴圧縮過程で導かれたクエリ特徴との距離を計算することを特徴とする請求項1から請求項8のいずれかに記載の信号検索方法。 Each database feature constituting the database feature series derived in the database feature extraction process is classified with reference to a predefined distance measure, and each classification is a feature that represents a database feature included in the classification. Database feature classification process to determine representative features;
A selection threshold setting process for calculating a selection threshold for the distance measure defined in the database feature classification process based on a predetermined search threshold;
Of the classifications derived in the database feature classification process, the selection threshold value calculated in the selection threshold value setting process is the distance between the classification representative feature corresponding to the classification and the query characteristic derived in the query feature extraction process. And a class having a representative feature that satisfies a condition derived from a class representative feature corresponding to a class to which the class belongs, when the query feature is classified by a method similar to the database feature classification process, A database feature selection process for selecting included database features;
Have
In the feature matching process, only the database feature selected in the database feature selection process or the database compressed feature derived in the database feature compression process corresponding to the database feature is the query feature derived in the query feature extraction process. The signal search method according to claim 1, wherein a distance from the query feature derived in the query feature compression process corresponding to the query feature is calculated.
ことを特徴とする請求項9に記載の信号検索方法。 The signal search method according to claim 9, wherein the database feature classification process is performed by a predetermined vector quantization method using a distance measure as an Euclidean distance.
ことを特徴とする請求項1から請求項10のいずれかに記載の信号検索方法。 The signal search method according to any one of claims 1 to 10, wherein in the feature matching process, the distance is calculated by using a distance scale as either a Manhattan distance or an Euclidean distance.
ことを特徴とする請求項7から請求項11のいずれかに記載の信号検索方法。 12. The database projection distance calculation process and the query projection distance calculation process calculate a database projection distance using a Manhattan distance or a Euclidean distance as a distance scale. 12. Signal search method.
ことを特徴とする請求項9から12のいずれかに記載の信号検索方法。 The signal search method according to any one of claims 9 to 12, wherein the distance recalculation process calculates a distance using a distance scale as either a Manhattan distance or an Euclidean distance.
ことを特徴とする請求項1から請求項13のいずれかに記載の信号検索方法。 In the query feature extraction process and the database feature extraction process, multidimensional vectors extracted from a query signal or database signal by a predetermined method are classified by a predetermined method, and a histogram that is a frequency distribution table for each classification is created. The signal search method according to any one of claims 1 to 13, wherein the histogram is output as a query feature or a database feature.
を有し、
前記特徴照合過程、距離補正過程、信号検出判定過程及びスキップ幅計算過程による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース特徴系列のいくつかの箇所について、クエリ特徴もしくはクエリ圧縮特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する
ことを特徴とする請求項1から請求項14のいずれかに記載の信号検索方法。 For the distance calculated in the distance correction process, the skip width calculation process of calculating the skip width of the reference location of the database representative feature series based on the distance and moving the reference location of the database representative feature series by the skip width And
The process of the feature matching process, the distance correction process, the signal detection determination process, and the skip width calculation process is repeated while shifting the position in the database representative feature series, and a query feature or query compression is performed for several parts of the database feature series. The signal search method according to any one of claims 1 to 14, wherein a distance from the feature is calculated and it is determined whether or not the query signal is present at the corresponding portion of the database signal.
クエリ信号から多次元ベクトルとして表現されるクエリ特徴を導くクエリ特徴抽出手段と、
データベース信号に注目窓を設定し、注目窓内の信号から、多次元ベクトルとして表現されるデータベース特徴を導き、これらの処理を、注目窓をずらしながら繰り返し行うことで多次元ベクトルの系列として表現されるデータベース特徴系列を導くデータベース特徴抽出手段と、
前記データベース特徴抽出手段で導かれたデータベース特徴系列を系列の順序に従って区分することで、データベース部分特徴系列を導くデータベース特徴区分手段と、
前記データベース特徴区分手段で導かれた各データベース部分特徴系列から、そのデータベース部分特徴系列を代表する特徴であるデータベース代表特徴を抽出し、前記データベース特徴抽出手段で導かれたデータベース特徴系列より少ない数の特徴で構成されるデータベース代表特徴系列を導くデータベース特徴間引き手段と、
前記データベース特徴区分手段で導かれた各データベース部分特徴系列中の各要素と前記データベース特徴間引き手段で導かれたデータベース代表特徴との距離の最大値dmaxを計算し、前記データベース代表特徴から前記距離の最大値dmaxの範囲内の領域であるデータベース特徴存在領域を導く特徴領域抽出手段と、
前記クエリ特徴抽出手段で導かれたクエリ特徴と、前記データベース特徴間引き手段で導かれたデータベース代表特徴系列に含まれるある特定位置のデータベース代表特徴との距離を計算する特徴照合手段と、
前記特徴照合手段で計算された距離から、前記特徴領域抽出手段で導かれた距離の最大値dmaxを差し引いたものを補正後の距離値とする距離補正手段と、
前記距離補正手段で導かれた補正距離値と、その補正距離値に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する信号検出判定手段とを有し、
前記特徴照合手段から前記信号検出判定手段による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する
ことを特徴とする信号検索装置。 A signal search device that searches for a portion similar to a query signal that is a target time series signal from a database signal that is a time series signal registered in advance,
Query feature extraction means for deriving query features expressed as multidimensional vectors from the query signal;
A database window is set in the database signal, database features expressed as multidimensional vectors are derived from the signal in the window of interest, and these processes are repeated while shifting the window of interest to be expressed as a series of multidimensional vectors. Database feature extraction means for deriving a database feature sequence;
Database feature classification means for deriving a database partial feature series by classifying the database feature series derived by the database feature extraction means according to the sequence order;
A database representative feature, which is a feature representing the database partial feature series, is extracted from each database partial feature series derived by the database feature classification means, and the number is smaller than the number of database feature series derived by the database feature extraction means. Database feature decimation means for deriving a database representative feature sequence composed of features;
A maximum value dmax of a distance between each element in each database partial feature series derived by the database feature classification unit and the database representative feature derived by the database feature thinning unit is calculated, and the distance of the distance is calculated from the database representative feature. A feature region extraction means for deriving a database feature existence region that is a region within the range of the maximum value dmax ;
A feature matching unit for calculating a distance between the query feature derived by the query feature extraction unit and a database representative feature at a specific position included in the database representative feature series derived by the database feature thinning unit;
Distance correction means for subtracting the maximum distance dmax derived by the feature region extraction means from the distance calculated by the feature matching means, and a distance value after correction;
A signal for determining whether or not the query signal is present at the relevant part of the database signal by comparing the corrected distance value derived by the distance correcting means with a search threshold value that is a threshold value corresponding to the corrected distance value. Detection and determination means,
The processing by the signal detection determination unit from the feature matching unit is repeated while shifting the position in the database representative feature series, and the distance from the query signal is calculated for several locations of the database signal. It is determined whether it exists in the said location of a signal, The signal search device characterized by the above-mentioned.
前記セグメント抽出手段で得られた各データベース特徴セグメントから,前記特徴よりも低次元の特徴を算出するための写像を決定する圧縮写像決定手段と、
前記セグメント抽出手段で得られた各データベース特徴セグメントに対応する前記圧縮写像決定手段で得られた射影変換を、該データベース特徴セグメントに含まれる各データ特徴に対して行うことにより、該データベース圧縮特徴に対応する圧縮特徴であるデータベース圧縮特徴の系列であるデータベース圧縮特徴系列を導くデータベース特徴圧縮手段と、
前記クエリ特徴抽出手段で得られたクエリ特徴に対し、前記圧縮写像決定手段で得られた射影変換を行うことにより、該クエリ特徴に対する圧縮特徴であるクエリ圧縮特徴を抽出するクエリ特徴圧縮手段と
を有し、
前記データベース特徴間引き手段において、前記データベース特徴圧縮手段で導かれたデータベース圧縮特徴系列を入力としてデータベース代表特徴系列を導き、前記特徴照合手段において、クエリ特徴圧縮手段で導かれたクエリ圧縮特徴をクエリ特徴の代わりに用いて照合を行い、さらに、特徴照合手段から信号検出判定手段による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する
ことを特徴とする請求項16に記載の信号検索装置。 A segment extraction unit that extracts a database feature segment that is a partial sequence having a shorter length than the database feature sequence by dividing the database feature sequence derived by the database feature extraction unit according to the sequence order;
Compression map determining means for determining a map for calculating a feature having a lower dimension than the feature from each database feature segment obtained by the segment extracting means;
By performing projective transformation obtained by the compression map determining means corresponding to each database feature segment obtained by the segment extracting means on each data feature included in the database feature segment, the database compressed feature is obtained. Database feature compression means for deriving a database compression feature sequence that is a sequence of database compression features that are corresponding compression features;
Query feature compression means for extracting a query compression feature that is a compression feature for the query feature by performing projective transformation obtained by the compression map determination means on the query feature obtained by the query feature extraction means. Have
The database feature decimation means derives a database representative feature series using the database compressed feature series derived by the database feature compression means as an input, and the feature matching means obtains the query compression feature derived by the query feature compression means as a query feature. In addition, the process from the feature matching unit to the signal detection determination unit is repeated while shifting the position in the database representative feature series, and the distance from the query signal at several points in the database signal. The signal search device according to claim 16, further comprising: calculating whether or not a query signal is present at the location of the database signal.
前記距離再計算手段で導かれた距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する信号検出再判定手段と
を有し、
前記特徴照合手段、距離補正手段、信号検出判定手段、信号再計算手段及び信号検出再判定手段による処理を、データベース圧縮特徴系列もしくはデータベース特徴系列の中の位置をずらしながら繰り返して、データベース圧縮特徴系列もしくはデータベース特徴系列のいくつかの箇所について、クエリ信号特徴もしくはクエリ特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する
ことを特徴とする請求項16または請求項17に記載の信号検索装置。 A database feature in the database feature sequence derived by the database feature extraction unit corresponding to the location of the location in the database signal determined by the signal detection judging means to be present, and the query feature A distance recalculation means for calculating a distance from the query feature derived by the extraction means;
A signal detection re-determination unit that re-determines whether the query signal is present at the location of the database signal by comparing the distance derived by the distance re-calculation unit with a search threshold;
A database compression feature sequence is repeated by repeating the processing by the feature matching unit, the distance correction unit, the signal detection determination unit, the signal recalculation unit, and the signal detection re-determination unit while shifting the position in the database compression feature sequence or the database feature sequence. Or calculating a query signal feature or a distance from the query feature for several locations of the database feature series and determining whether the query signal is present at that location of the database signal or The signal search device according to claim 17.
前記データベース特徴分類手段で定義された距離尺度に対する選択閾値を、予め定められた探索閾値を基準として計算する選択閾値設定手段と、
前記データベース特徴分類手段で導かれた分類のうち、該分類に対応する分類代表特徴と、前記クエリ特徴抽出手段で導かれたクエリ特徴との距離が、前記選択閾値設定手段で計算された選択閾値と、該クエリ特徴を前記データベース特徴分類手段と同様の方法により分類した際に所属する分類に対応する分類代表特徴とから導かれる条件を満たすような代表特徴を持つ分類を検出し、該分類に含まれるデータベース特徴を選択するデータベース特徴選択手段と、
を有し、
前記特徴照合手段において、前記データベース特徴選択手段において選択されたデータベース特徴もしくは該データベース特徴に対応する前記データベース特徴圧縮手段で導かれたデータベース圧縮特徴についてのみ、前記クエリ特徴抽出手段で導かれたクエリ特徴もしくは該クエリ特徴に対応する前記クエリ特徴圧縮手段で導かれたクエリ特徴との距離を計算することを特徴とする請求項16から請求項18のいずれかに記載の信号検索装置。 Each database feature constituting the database feature series derived by the database feature extraction means is classified with reference to a predefined distance measure, and each classification is a feature that represents a database feature included in the classification. Database feature classification means for determining representative features;
A selection threshold value setting means for calculating a selection threshold value for the distance scale defined by the database feature classifying means with reference to a predetermined search threshold value;
Of the classifications derived by the database feature classification unit, the selection threshold value calculated by the selection threshold setting unit is a distance between the classification representative feature corresponding to the classification and the query feature derived by the query feature extraction unit And a class having a representative feature that satisfies a condition derived from a class representative feature corresponding to a class to which the query characteristic belongs when the query feature is classified by the same method as the database feature classifying unit, and Database feature selection means for selecting included database features;
Have
In the feature matching unit, only the database feature selected by the database feature selection unit or the database compression feature derived by the database feature compression unit corresponding to the database feature is the query feature derived by the query feature extraction unit. The signal search apparatus according to claim 16, wherein a distance from the query feature derived by the query feature compression unit corresponding to the query feature is calculated.
を有し、
前記特徴照合手段、距離補正手段、信号検出判定手段及びスキップ幅計算手段による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース特徴系列のいくつかの箇所について、クエリ特徴もしくはクエリ圧縮特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する
ことを特徴とする請求項16または請求項17に記載の信号検索装置。 With respect to the distance calculated by the distance correction means, a skip width calculation means for calculating a skip width of a reference position of the database representative feature series based on the distance and moving the reference position of the database representative feature series by the skip width And
The processing by the feature matching unit, the distance correction unit, the signal detection determination unit, and the skip width calculation unit is repeated while shifting the position in the database representative feature sequence, and the query feature or the query compression is performed for some parts of the database feature sequence. The signal search device according to claim 16 or 17, wherein a distance from the feature is calculated, and it is determined whether or not the query signal is present at the corresponding portion of the database signal.
クエリ信号から多次元ベクトルとして表現されるクエリ特徴を導くクエリ特徴抽出処理と、
データベース信号に注目窓を設定し、注目窓内の信号から、多次元ベクトルとして表現されるデータベース特徴を導き、これらの処理を、注目窓をずらしながら繰り返し行うことで多次元ベクトルの系列として表現されるデータベース特徴系列を導くデータベース特徴抽出処理と、
前記データベース特徴抽出処理で導かれたデータベース特徴系列を系列の順序に従って区分することで、データベース部分特徴系列を導くデータベース特徴区分処理と、
前記データベース特徴区分処理で導かれた各データベース部分特徴系列から、そのデータベース部分特徴系列を代表する特徴であるデータベース代表特徴を抽出し、前記データベース特徴抽出処理で導かれたデータベース特徴系列より少ない数の特徴で構成されるデータベース代表特徴系列を導くデータベース特徴間引き処理と、
前記データベース特徴区分処理で導かれた各データベース部分特徴系列中の各要素と前記データベース特徴間引き処理で導かれたデータベース代表特徴との距離の最大値dmaxを計算し、前記データベース代表特徴から前記距離の最大値dmaxの範囲内の領域であるデータベース特徴存在領域を導く特徴領域抽出処理と、
前記クエリ特徴抽出処理で導かれたクエリ特徴と、前記データベース特徴間引き処理で導かれたデータベース代表特徴系列に含まれるある特定位置のデータベース代表特徴との距離を計算する特徴照合処理と、
前記特徴照合処理で計算された距離から、前記特徴領域抽出処理で導かれた距離の最大値dmaxを差し引いたものを補正後の距離値とする距離補正処理と、
前記距離補正処理で導かれた補正距離値と、その補正距離値に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する信号検出判定処理とを有し、
前記特徴照合処理から前記信号検出判定処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、
をコンピュータに実行させるプログラム。 A program for causing a computer of a signal search device to search for a portion similar to a query signal that is a target time series signal from a database signal that is a time series signal registered in advance,
Query feature extraction processing for deriving query features expressed as multidimensional vectors from the query signal;
A database window is set in the database signal, database features expressed as multidimensional vectors are derived from the signal in the window of interest, and these processes are repeated while shifting the window of interest to be expressed as a series of multidimensional vectors. Database feature extraction processing for deriving database feature sequences;
A database feature classification process for deriving a database partial feature series by classifying the database feature series derived by the database feature extraction process according to the sequence order;
A database representative feature, which is a feature representing the database partial feature series, is extracted from each database partial feature series derived by the database feature classification process, and is smaller in number than the database feature series derived by the database feature extraction process. A database feature decimation process for deriving a database representative feature sequence composed of features;
The maximum value dmax of the distance between each element in each database partial feature series derived by the database feature classification process and the database representative feature derived by the database feature thinning process is calculated, and the distance of the distance is calculated from the database representative feature. A feature region extraction process for deriving a database feature existing region that is a region within the range of the maximum value dmax ;
A feature matching process for calculating a distance between the query feature derived by the query feature extraction process and a database representative feature at a specific position included in the database representative feature series derived by the database feature thinning process;
A distance correction process in which a distance value after correction is obtained by subtracting the maximum value dmax of the distance derived in the feature region extraction process from the distance calculated in the feature matching process;
A signal for determining whether or not the query signal is present at the relevant part of the database signal by comparing the corrected distance value derived by the distance correction process with a search threshold value that is a threshold value corresponding to the corrected distance value. Detection determination processing,
The process from the feature matching process to the signal detection determination process is repeated while shifting the position in the database representative feature series, and the distance from the query signal is calculated for several parts of the database signal. Processing to determine if it exists at that point in the signal;
A program that causes a computer to execute.
前記データベース特徴抽出処理で導かれたデータベース特徴系列を、系列の順序に従って分割することにより、データベース特徴系列よりも短い長さの部分系列であるデータベース特徴セグメントを抽出するセグメント抽出処理と、
前記セグメント抽出処理で得られた各データベース特徴セグメントから,前記特徴よりも低次元の特徴を算出するための写像を決定する圧縮写像決定処理と、
前記セグメント抽出処理で得られた各データベース特徴セグメントに対応する前記圧縮写像決定処理で得られた射影変換を、該データベース特徴セグメントに含まれる各データ特徴に対して行うことにより、該データベース圧縮特徴に対応する圧縮特徴であるデータベース圧縮特徴の系列であるデータベース圧縮特徴系列を導くデータベース特徴圧縮処理と、
前記クエリ特徴抽出処理で得られたクエリ特徴に対し、前記圧縮写像決定処理で得られた射影変換を行うことにより、該クエリ特徴に対する圧縮特徴であるクエリ圧縮特徴を抽出するクエリ特徴圧縮処理と
前記データベース特徴間引き処理において、前記データベース特徴圧縮処理で導かれたデータベース圧縮特徴系列を入力としてデータベース代表特徴系列を導き、前記特徴照合処理において、クエリ特徴圧縮処理で導かれたクエリ圧縮特徴をクエリ特徴の代わりに用いて照合を行い、さらに、特徴照合処理から信号検出判定処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、
をコンピュータに実行させるプログラム。 In addition to the processing included in the program according to claim 21,
A segment extraction process for extracting a database feature segment that is a partial series having a shorter length than the database feature series by dividing the database feature series derived by the database feature extraction process according to the sequence order;
A compressed map determination process for determining a map for calculating a feature of a lower dimension than the feature from each database feature segment obtained by the segment extraction process;
By performing projective transformation obtained by the compression mapping determination process corresponding to each database feature segment obtained by the segment extraction process on each data feature included in the database feature segment, the database compressed feature is obtained. Database feature compression processing for deriving a database compression feature sequence that is a sequence of database compression features that are corresponding compression features;
A query feature compression process for extracting a query compression feature that is a compression feature for the query feature by performing a projective transformation obtained by the compression map determination process on the query feature obtained by the query feature extraction process; In the database feature decimation process, a database representative feature sequence is derived using the database compressed feature sequence derived in the database feature compression process as an input, and in the feature matching process, the query compressed feature derived in the query feature compression process is converted into a query feature Instead, the matching is performed, and the processing from the feature matching processing to the signal detection determination processing is repeated while shifting the position in the database representative feature series, and the distance from the query signal is determined for several portions of the database signal. Calculate and query signal is present at the relevant part of the database signal Processing to determine whether to
A program that causes a computer to execute.
前記信号検出判定処理でクエリ信号が存在すると判定されたデータベース信号中の当該箇所について、その当該箇所に対応する、前記データベース特徴抽出処理で導かれたデータベース特徴系列中のデータベース特徴と、前記クエリ特徴抽出処理で導かれたクエリ特徴との距離を計算する距離再計算処理と、
前記距離再計算処理で導かれた距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する信号検出再判定処理と
前記特徴照合処理、距離補正処理、信号検出判定処理、信号再計算処理及び信号検出再判定処理による処理を、データベース圧縮特徴系列もしくはデータベース特徴系列の中の位置をずらしながら繰り返して、データベース圧縮特徴系列もしくはデータベース特徴系列のいくつかの箇所について、クエリ信号特徴もしくはクエリ特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と
をコンピュータに実行させるプログラム。 In addition to the processing included in the program according to claim 21 or claim 22,
A database feature in the database feature sequence derived by the database feature extraction process corresponding to the location in the database signal determined by the signal detection determination processing to determine that a query signal exists, and the query feature A distance recalculation process for calculating the distance from the query feature derived by the extraction process;
A signal detection re-determination process for re-determining whether a query signal is present at the location of the database signal by comparing the distance derived by the distance re-calculation process with a search threshold; and the feature matching process, distance The correction processing, signal detection determination processing, signal recalculation processing, and signal detection redetermination processing are repeated while shifting the position in the database compression feature sequence or database feature sequence. A program that causes a computer to execute a process of calculating a query signal feature or a distance from the query feature and determining whether the query signal is present at the location of the database signal.
前記データベース特徴抽出処理で導かれたデータベース特徴系列を構成する各データベース特徴を、予め定義された距離尺度を基準として分類し、各分類について、その分類に含まれるデータベース特徴を代表する特徴である分類代表特徴を決定するデータベース特徴分類処理と、
前記データベース特徴分類処理で定義された距離尺度に対する選択閾値を、予め定められた探索閾値を基準として計算する選択閾値設定処理と、
前記データベース特徴分類処理で導かれた分類のうち、該分類に対応する分類代表特徴と、前記クエリ特徴抽出処理で導かれたクエリ特徴との距離が、前記選択閾値設定処理で計算された選択閾値と、該クエリ特徴を前記データベース特徴分類処理と同様の方法により分類した際に所属する分類に対応する分類代表特徴とから導かれる条件を満たすような代表特徴を持つ分類を検出し、該分類に含まれるデータベース特徴を選択するデータベース特徴選択処理と、
を有し、
前記特徴照合処理において、前記データベース特徴選択処理において選択されたデータベース特徴もしくは該データベース特徴に対応する前記データベース特徴圧縮処理で導かれたデータベース圧縮特徴についてのみ、前記クエリ特徴抽出処理で導かれたクエリ特徴もしくは該クエリ特徴に対応する前記クエリ特徴圧縮処理で導かれたクエリ特徴との距離を計算する処理と
をコンピュータに実行させるプログラム。 In addition to the processing included in the program according to any one of claims 21 to 23,
Each database feature constituting the database feature series derived by the database feature extraction process is classified based on a predefined distance measure, and each classification is a feature that represents the database feature included in the classification. Database feature classification processing for determining representative features;
A selection threshold value setting process for calculating a selection threshold value for the distance scale defined in the database feature classification process with reference to a predetermined search threshold value;
Of the classifications derived by the database feature classification process, the selection threshold calculated by the selection threshold setting process is the distance between the classification representative feature corresponding to the classification and the query characteristic derived by the query feature extraction process And a class having a representative feature that satisfies a condition derived from a class representative feature corresponding to a class to which the class belongs when the query feature is classified by the same method as the database feature classification process, A database feature selection process for selecting included database features;
Have
In the feature matching process, only the database feature selected in the database feature selection process or the database compressed feature derived in the database feature compression process corresponding to the database feature is the query feature derived in the query feature extraction process. Or a program for causing a computer to execute a process of calculating a distance from the query feature derived by the query feature compression process corresponding to the query feature.
前記距離補正処理で計算された距離について、該距離を基準してデータベース代表特徴系列の参照箇所のスキップ幅を計算し、そのスキップ幅の分だけデータベース代表特徴系列の参照箇所を移動するスキップ幅計算処理と
前記特徴照合処理、距離補正処理、信号検出判定処理及びスキップ幅計算処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース特徴系列のいくつかの箇所について、クエリ特徴もしくはクエリ圧縮特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と
をコンピュータに実行させるプログラム。 In addition to the processing included in the program according to claim 21 to claim 22,
With respect to the distance calculated by the distance correction process, a skip width of the reference location of the database representative feature series is calculated based on the distance, and a skip width calculation for moving the reference location of the database representative feature series by the skip width The process and the feature matching process, the distance correction process, the signal detection determination process, and the skip width calculation process are repeated while shifting the position in the database representative feature series. A program that causes a computer to execute a process of calculating a distance from a query compression feature and determining whether a query signal is present at a corresponding portion of a database signal.
クエリ信号から多次元ベクトルとして表現されるクエリ特徴を導くクエリ特徴抽出処理と、
データベース信号に注目窓を設定し、注目窓内の信号から、多次元ベクトルとして表現されるデータベース特徴を導き、これらの処理を、注目窓をずらしながら繰り返し行うことで多次元ベクトルの系列として表現されるデータベース特徴系列を導くデータベース特徴抽出処理と、
前記データベース特徴抽出処理で導かれたデータベース特徴系列を系列の順序に従って区分することで、データベース部分特徴系列を導くデータベース特徴区分処理と、
前記データベース特徴区分処理で導かれた各データベース部分特徴系列から、そのデータベース部分特徴系列を代表する特徴であるデータベース代表特徴を抽出し、前記データベース特徴抽出処理で導かれたデータベース特徴系列より少ない数の特徴で構成されるデータベース代表特徴系列を導くデータベース特徴間引き処理と、
前記データベース特徴区分処理で導かれた各データベース部分特徴系列中の各要素と前記データベース特徴間引き処理で導かれたデータベース代表特徴との距離の最大値dmaxを計算し、前記データベース代表特徴から前記距離の最大値dmaxの範囲内の領域であるデータベース特徴存在領域を導く特徴領域抽出処理と、
前記クエリ特徴抽出処理で導かれたクエリ特徴と、前記データベース特徴間引き処理で導かれたデータベース代表特徴系列に含まれるある特定位置のデータベース代表特徴との距離を計算する特徴照合処理と、
前記特徴照合処理で計算された距離から、前記特徴領域抽出処理で導かれた距離の最大値dmaxを差し引いたものを補正後の距離値とする距離補正処理と、
前記距離補正処理で導かれた補正距離値と、その補正距離値に対応する閾値である探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを判定する信号検出判定処理とを有し、
前記特徴照合処理から前記信号検出判定処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、
をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。 A computer-readable recording medium recording a program to be executed by a computer of a signal search device that searches for a portion similar to a query signal that is a target time-series signal from a database signal that is a pre-registered time-series signal ,
Query feature extraction processing for deriving query features expressed as multidimensional vectors from the query signal;
A database window is set in the database signal, database features expressed as multidimensional vectors are derived from the signal in the window of interest, and these processes are repeated while shifting the window of interest to be expressed as a series of multidimensional vectors. Database feature extraction processing for deriving database feature sequences;
A database feature classification process for deriving a database partial feature series by classifying the database feature series derived by the database feature extraction process according to the sequence order;
A database representative feature, which is a feature representing the database partial feature series, is extracted from each database partial feature series derived by the database feature classification process, and is smaller in number than the database feature series derived by the database feature extraction process. A database feature decimation process for deriving a database representative feature sequence composed of features;
The maximum value dmax of the distance between each element in each database partial feature series derived by the database feature classification process and the database representative feature derived by the database feature thinning process is calculated, and the distance of the distance is calculated from the database representative feature. A feature region extraction process for deriving a database feature existing region that is a region within the range of the maximum value dmax ;
A feature matching process for calculating a distance between the query feature derived by the query feature extraction process and a database representative feature at a specific position included in the database representative feature series derived by the database feature thinning process;
A distance correction process in which a distance value after correction is obtained by subtracting the maximum value dmax of the distance derived in the feature region extraction process from the distance calculated in the feature matching process;
A signal for determining whether or not the query signal is present at the relevant part of the database signal by comparing the corrected distance value derived by the distance correction process with a search threshold value that is a threshold value corresponding to the corrected distance value. Detection determination processing,
The process from the feature matching process to the signal detection determination process is repeated while shifting the position in the database representative feature series, and the distance from the query signal is calculated for several parts of the database signal. Processing to determine if it exists at that point in the signal;
The computer-readable recording medium which recorded the program which makes a computer perform.
前記データベース特徴抽出処理で導かれたデータベース特徴系列を、系列の順序に従って分割することにより、データベース特徴系列よりも短い長さの部分系列であるデータベース特徴セグメントを抽出するセグメント抽出処理と、
前記セグメント抽出処理で得られた各データベース特徴セグメントから,前記特徴よりも低次元の特徴を算出するための写像を決定する圧縮写像決定処理と、
前記セグメント抽出処理で得られた各データベース特徴セグメントに対応する前記圧縮写像決定処理で得られた射影変換を、該データベース特徴セグメントに含まれる各データ特徴に対して行うことにより、該データベース圧縮特徴に対応する圧縮特徴であるデータベース圧縮特徴の系列であるデータベース圧縮特徴系列を導くデータベース特徴圧縮処理と、
前記クエリ特徴抽出処理で得られたクエリ特徴に対し、前記圧縮写像決定処理で得られた射影変換を行うことにより、該クエリ特徴に対する圧縮特徴であるクエリ圧縮特徴を抽出するクエリ特徴圧縮処理と
前記データベース特徴間引き処理において、前記データベース特徴圧縮処理で導かれたデータベース圧縮特徴系列を入力としてデータベース代表特徴系列を導き、前記特徴照合処理において、クエリ特徴圧縮処理で導かれたクエリ圧縮特徴をクエリ特徴の代わりに用いて照合を行い、さらに、特徴照合処理から信号検出判定処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース信号のいくつかの箇所について、クエリ信号との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と、
をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。 In addition to the processing included in the program according to claim 26,
A segment extraction process for extracting a database feature segment that is a partial series having a shorter length than the database feature series by dividing the database feature series derived by the database feature extraction process according to the sequence order;
A compressed map determination process for determining a map for calculating a feature of a lower dimension than the feature from each database feature segment obtained by the segment extraction process;
By performing projective transformation obtained by the compression mapping determination process corresponding to each database feature segment obtained by the segment extraction process on each data feature included in the database feature segment, the database compressed feature is obtained. Database feature compression processing for deriving a database compression feature sequence that is a sequence of database compression features that are corresponding compression features;
A query feature compression process for extracting a query compression feature that is a compression feature for the query feature by performing a projective transformation obtained by the compression map determination process on the query feature obtained by the query feature extraction process; In the database feature decimation process, a database representative feature sequence is derived using the database compressed feature sequence derived in the database feature compression process as an input, and in the feature matching process, the query compressed feature derived in the query feature compression process is converted into a query feature Instead, the matching is performed, and the processing from the feature matching processing to the signal detection determination processing is repeated while shifting the position in the database representative feature series, and the distance from the query signal is determined for several portions of the database signal. Calculate and query signal is present at the relevant part of the database signal Processing to determine whether to
The computer-readable recording medium which recorded the program which makes a computer perform.
前記信号検出判定処理でクエリ信号が存在すると判定されたデータベース信号中の当該箇所について、その当該箇所に対応する、前記データベース特徴抽出処理で導かれたデータベース特徴系列中のデータベース特徴と、前記クエリ特徴抽出処理で導かれたクエリ特徴との距離を計算する距離再計算処理と、
前記距離再計算処理で導かれた距離と探索閾値とを比較することにより、クエリ信号が、データベース信号の当該箇所に存在するかどうかを再判定する信号検出再判定処理と
前記特徴照合処理、距離補正処理、信号検出判定処理、信号再計算処理及び信号検出再判定処理による処理を、データベース圧縮特徴系列もしくはデータベース特徴系列の中の位置をずらしながら繰り返して、データベース圧縮特徴系列もしくはデータベース特徴系列のいくつかの箇所について、クエリ信号特徴もしくはクエリ特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と
をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。 In addition to the processing included in the program according to claim 26 or claim 27,
A database feature in the database feature sequence derived by the database feature extraction process corresponding to the location in the database signal determined by the signal detection determination processing to determine that a query signal exists, and the query feature A distance recalculation process for calculating the distance from the query feature derived by the extraction process;
A signal detection re-determination process for re-determining whether a query signal is present at the location of the database signal by comparing the distance derived by the distance re-calculation process with a search threshold; and the feature matching process, distance The correction processing, signal detection determination processing, signal recalculation processing, and signal detection redetermination processing are repeated while shifting the position in the database compression feature sequence or database feature sequence. A computer-readable recording of a program that causes a computer to execute a process that calculates a query signal feature or a distance from the query feature and determines whether the query signal is present at the location of the database signal. recoding media.
前記データベース特徴抽出処理で導かれたデータベース特徴系列を構成する各データベース特徴を、予め定義された距離尺度を基準として分類し、各分類について、その分類に含まれるデータベース特徴を代表する特徴である分類代表特徴を決定するデータベース特徴分類処理と、
前記データベース特徴分類処理で定義された距離尺度に対する選択閾値を、予め定められた探索閾値を基準として計算する選択閾値設定処理と、
前記データベース特徴分類処理で導かれた分類のうち、該分類に対応する分類代表特徴と、前記クエリ特徴抽出処理で導かれたクエリ特徴との距離が、前記選択閾値設定処理で計算された選択閾値と、該クエリ特徴を前記データベース特徴分類処理と同様の方法により分類した際に所属する分類に対応する分類代表特徴とから導かれる条件を満たすような代表特徴を持つ分類を検出し、該分類に含まれるデータベース特徴を選択するデータベース特徴選択処理と、
前記特徴照合処理において、前記データベース特徴選択処理において選択されたデータベース特徴もしくは該データベース特徴に対応する前記データベース特徴圧縮処理で導かれたデータベース圧縮特徴についてのみ、前記クエリ特徴抽出処理で導かれたクエリ特徴もしくは該クエリ特徴に対応する前記クエリ特徴圧縮処理で導かれたクエリ特徴との距離を計算する処理と
をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。 In addition to the processing included in the program according to any one of claims 26 to 28,
Each database feature constituting the database feature series derived by the database feature extraction process is classified based on a predefined distance measure, and each classification is a feature that represents the database feature included in the classification. Database feature classification processing for determining representative features;
A selection threshold value setting process for calculating a selection threshold value for the distance scale defined in the database feature classification process with reference to a predetermined search threshold value;
Of the classifications derived by the database feature classification process, the selection threshold calculated by the selection threshold setting process is the distance between the classification representative feature corresponding to the classification and the query characteristic derived by the query feature extraction process And a class having a representative feature that satisfies a condition derived from a class representative feature corresponding to a class to which the class belongs when the query feature is classified by the same method as the database feature classification process, A database feature selection process for selecting included database features;
In the feature matching process, only the database feature selected in the database feature selection process or the database compressed feature derived in the database feature compression process corresponding to the database feature is the query feature derived in the query feature extraction process. Alternatively, a computer-readable recording medium storing a program for causing a computer to execute a process of calculating a distance from the query feature derived by the query feature compression process corresponding to the query feature.
前記距離補正処理で計算された距離について、該距離を基準としてデータベース代表特徴系列の参照箇所のスキップ幅を計算し、そのスキップ幅の分だけデータベース代表特徴系列の参照箇所を移動するスキップ幅計算処理と
前記特徴照合処理、距離補正処理、信号検出判定処理及びスキップ幅計算処理による処理を、データベース代表特徴系列中の位置をずらしながら繰り返して、データベース特徴系列のいくつかの箇所について、クエリ特徴もしくはクエリ圧縮特徴との距離を計算し、クエリ信号が、データベース信号の当該箇所に存在するかどうかを決定する処理と
をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。 In addition to the processing included in the program according to claim 26 or claim 27,
For the distance calculated in the distance correction process, a skip width calculation process for calculating the skip width of the reference position of the database representative feature series based on the distance and moving the reference position of the database representative feature series by the skip width And repeating the process by the feature matching process, the distance correction process, the signal detection determination process, and the skip width calculation process while shifting the position in the database representative feature series, and the query feature or query A computer-readable recording medium storing a program for calculating a distance to a compression feature and causing a computer to execute a process of determining whether a query signal is present at the corresponding portion of a database signal.
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2006271323A JP4459940B2 (en) | 2002-12-06 | 2006-10-02 | Signal search method, apparatus, program and recording medium thereof |
Applications Claiming Priority (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2002355444 | 2002-12-06 | ||
JP2006271323A JP4459940B2 (en) | 2002-12-06 | 2006-10-02 | Signal search method, apparatus, program and recording medium thereof |
Related Parent Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP2003403634A Division JP3884006B2 (en) | 2002-12-06 | 2003-12-02 | Signal compression method, apparatus, program and recording medium thereof, signal search method, apparatus, program and recording medium thereof |
Publications (2)
Publication Number | Publication Date |
---|---|
JP2007034325A JP2007034325A (en) | 2007-02-08 |
JP4459940B2 true JP4459940B2 (en) | 2010-04-28 |
Family
ID=37793571
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP2006271323A Expired - Fee Related JP4459940B2 (en) | 2002-12-06 | 2006-10-02 | Signal search method, apparatus, program and recording medium thereof |
Country Status (1)
Country | Link |
---|---|
JP (1) | JP4459940B2 (en) |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US10572812B2 (en) | 2015-03-19 | 2020-02-25 | Kabushiki Kaisha Toshiba | Detection apparatus, detection method, and computer program product |
Families Citing this family (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN109547989A (en) * | 2018-12-17 | 2019-03-29 | 深圳壹账通智能科技有限公司 | Bluetooth pairing methods, device, medium and terminal device based on fingerprint recognition |
-
2006
- 2006-10-02 JP JP2006271323A patent/JP4459940B2/en not_active Expired - Fee Related
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US10572812B2 (en) | 2015-03-19 | 2020-02-25 | Kabushiki Kaisha Toshiba | Detection apparatus, detection method, and computer program product |
Also Published As
Publication number | Publication date |
---|---|
JP2007034325A (en) | 2007-02-08 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
US6710822B1 (en) | Signal processing method and image-voice processing apparatus for measuring similarities between signals | |
EP1650683B1 (en) | Search of similar features representing objects in a large reference database | |
US10713229B2 (en) | Index generating device and method, and search device and search method | |
CN110929745A (en) | Neural network based classification method and classification device thereof | |
JP6708043B2 (en) | Data search program, data search method, and data search device | |
US12020483B2 (en) | Dynamic detection and recognition of media subjects | |
KR20140079262A (en) | Image retrieval method, real-time drawing prompting method and devices thereof | |
CN108320024A (en) | Dictionary creating apparatus and method, apparatus for evaluating and method and storage medium | |
JP3884006B2 (en) | Signal compression method, apparatus, program and recording medium thereof, signal search method, apparatus, program and recording medium thereof | |
US10437803B2 (en) | Index generation apparatus and index generation method | |
EP2115737B1 (en) | Method and system to improve automated emotional recognition | |
JP4459940B2 (en) | Signal search method, apparatus, program and recording medium thereof | |
KR20220032805A (en) | Memory Management Apparatus and Method | |
CN116110113A (en) | Iris recognition method based on deep learning | |
CN112463894B (en) | Multi-label feature selection method based on conditional mutual information and interactive information | |
US11048730B2 (en) | Data clustering apparatus and method based on range query using CF tree | |
KR101704736B1 (en) | Apparatus and Method of Support Vector Machine Classifier Using Multistage Sub-Classifier | |
CN100592326C (en) | Method and device for extracting signal | |
CN112465054B (en) | FCN-based multivariate time series data classification method | |
JP3916813B2 (en) | Data series search apparatus and method | |
JP3574075B2 (en) | Signal detection method, signal detection device, recording medium, and program | |
JP3730179B2 (en) | SIGNAL SEARCH DEVICE, SIGNAL SEARCH METHOD, SIGNAL SEARCH PROGRAM, AND RECORDING MEDIUM CONTAINING SIGNAL SEARCH PROGRAM | |
JP2019096118A (en) | Pattern recognition program, device and method | |
Le Naour et al. | Fast motion retrieval with the distance input space | |
CN114021631A (en) | Bank customer classification method and device |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20091001 |
|
A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20091020 |
|
A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20091221 |
|
TRDD | Decision of grant or rejection written | ||
A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20100202 |
|
A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20100210 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130219 Year of fee payment: 3 |
|
S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
LAPS | Cancellation because of no payment of annual fees |