JP2003242510A - Signal search device, signal search method, signal search program, and recording medium storing signal search program - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To provide a signal search device for performing high-speed signal search. SOLUTION: Means for deriving a feature sequence from a reference signal, means for setting a window of interest in an accumulated signal, and deriving a feature sequence from a signal within the window of interest, and each feature derived by repeating the process while shifting the window of interest Means for classifying a sequence, means for determining a mapping for calculating a lower-dimensional feature than the feature sequence from the obtained feature sequences after segmentation, and features corresponding to the obtained feature sequences after segmentation Means for calculating a lower-dimensional feature than the sequence based on the obtained mapping; and means for calculating a lower-dimensional feature than the feature sequence corresponding to the obtained feature sequence based on the obtained mapping. Means for calculating the distance between the derived compressed feature sequence and the compressed feature sequence, and comparing the derived distance and a search threshold that is a threshold corresponding to the distance, the reference signal is stored in the corresponding location of the accumulated signal. Means for determining whether it exists Prepare.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention records a signal search device, a signal search method, a signal search program, and a signal search program suitable for finding a location of a signal similar to a signal registered in advance from a signal sequence. Recording medium.

[0002]

2. Description of the Related Art Conventionally, a time when a specific commercial is broadcast is detected from an audio signal of a broadcast or the like and automatically recorded, or a specific theme song is detected to start or stop video recording. A signal detection technique for enabling the above is known. In addition, this signal detection technology can be used to automatically monitor the time when a clap sound is emitted from a broadcast, the time when a laughter is emitted, etc., and it is also possible to search for a specific scene. Used. Further, this signal detection technique can be applied to detection of not only audio signals but also general signals such as video signals.

[0003]

By the way, as a conventional signal search method, a signal similar to a signal registered in advance, such as "high-speed signal search method, apparatus and recording medium thereof" (Japanese Patent No. 3065314), is used. A high-speed signal search method for finding the location of is known. However, this method has a problem that it is not possible to find a similar signal within a sufficiently short time for an extremely large number of signals.

The present invention has been made in view of the above circumstances, and provides a signal search processing unit having higher calculation efficiency than that of the conventional method, and requires less matching calculation time than the conventional method. It is an object of the present invention to provide a signal search device, a signal search method, a signal search program, and a recording medium having the signal search program recorded therein, which are capable of performing a faster signal search.

[0005]

According to a first aspect of the present invention, a distance between a reference signal and an arbitrary portion of a stored signal is calculated, and it is determined whether or not the reference signal exists at the portion of the stored signal. By doing so, a signal retrieving device that searches for a portion similar to the target reference signal from the pre-registered accumulated signals, wherein the signal retrieving device is a reference feature extraction unit that derives a feature sequence from the reference signal, and the accumulated signal. An accumulation feature extraction unit that sets a window of interest to a feature sequence that derives a feature sequence from a signal inside the window of interest, an accumulation feature division unit that divides each feature sequence that is repeatedly obtained by shifting the window of interest, and the accumulation From each of the post-classification feature sequences obtained by the feature segmentation unit, a compression mapping determination unit that determines a map for calculating features of a lower dimension than the feature sequence, and after the segmentation obtained by the accumulated feature segmentation unit. Each feature of Corresponds to a feature series obtained by the reference feature extraction unit and a stored feature compression unit that calculates a lower dimensional feature corresponding to a column than the feature sequence based on the mapping obtained by the compression mapping determination unit. A reference feature compression unit that calculates a lower-dimensional feature than the feature sequence based on the mapping obtained by the compression mapping determination unit, a compression feature sequence derived by the accumulated feature compression unit, and the reference A compressed inter-feature distance calculation unit that calculates a distance to the compressed feature series derived by the feature compression unit, a distance derived by the compressed inter-feature distance calculation unit, and a search threshold value that is a threshold value corresponding to the distance. It is characterized in that it is provided with a signal detection determination unit for determining whether or not the reference signal exists at the location of the accumulated signal by comparison.

According to a second aspect of the present invention, the signal retrieval device calculates the skip width of the window of interest based on the distance output from the inter-compression-feature distance calculation unit, and selects the window of interest by the skip width. It is characterized by further comprising a skip width calculator that moves.

According to a third aspect of the present invention, in the signal search device, the feature series derived by the reference feature extraction unit with respect to the location of the accumulated signal for which the reference signal is determined to be present in the signal detection determination unit. And a distance recalculation unit that calculates a distance to the feature series derived by the accumulated feature extraction unit,
The reference signal further includes a signal detection re-determination unit that re-determines whether or not the reference signal exists at the location of the accumulated signal by comparing the distance derived by the distance re-calculation unit and the search threshold value. Is characterized by.

According to a fourth aspect of the present invention, the storage feature compression unit maps each of the feature sequences after the division obtained by the storage feature division unit by the mapping obtained by the compression map determination unit. The reference feature compression unit includes a feature mapping unit and a cumulative projection distance calculation unit that calculates a distance between the compressed feature sequence derived by the accumulated feature mapping unit and the feature sequence derived by the accumulated feature extraction unit. Is a reference feature mapping unit that maps the feature sequence obtained by the reference feature extraction unit by the mapping obtained by the compression mapping determination unit, and the compressed feature sequence derived by the reference feature mapping unit, And a reference projective distance calculation unit that calculates a distance to the feature series derived by the feature extraction unit.

According to a fifth aspect of the present invention, the reference feature extraction unit and the accumulated feature extraction unit classify the features by a predetermined method and create a histogram which is a frequency distribution table for each of the features. The feature is that the histogram is output as a new feature.

The invention according to claim 6 is characterized in that the compression mapping determination unit extracts a representative feature by a principal component analysis.

According to a seventh aspect of the present invention, the distance between an arbitrary portion of the accumulated signal and the reference signal is calculated, and whether the reference signal exists at the portion of the accumulated signal is registered in advance. A signal search method for searching a portion similar to a target reference signal from the stored signal, wherein the signal search method comprises a reference feature extraction process of deriving a feature sequence from the reference signal and setting a window of interest in the stored signal. The accumulated feature extraction process for deriving a feature sequence from the signal in the window of interest, the accumulated feature segmentation process for segmenting each feature sequence derived by repeating the window of interest, and the accumulated feature segmentation process. From each of the feature sequences after classification, a compression map determination process for determining a map for calculating a feature having a dimension lower than that of the feature sequence, and each feature sequence after classification obtained in the accumulated feature segmentation process Corresponding to the feature series obtained in the reference feature extraction step, and the corresponding feature series having a lower dimension than the feature series, which is calculated based on the mapping obtained in the compression mapping determination step. A reference feature compression process for calculating a feature of a lower dimension than the feature sequence based on the mapping obtained in the compression mapping determination process, a compression feature sequence derived in the accumulated feature compression process, and the reference feature compression. Comparing the inter-compression-feature distance calculation process for calculating the distance with the compression-feature series derived in the process, and the distance derived in the inter-compression-feature distance calculation process, and a search threshold that is a threshold corresponding to the distance. Accordingly, a signal detection determination process for determining whether or not the reference signal exists at the location of the accumulated signal is provided.

According to an eighth aspect of the present invention, in the signal search method, the skip width of the window of interest is calculated based on the distance output from the compression feature distance calculation step, and the window of interest is skipped by the skip width. It is characterized by further comprising a moving skip width calculation process.

According to a ninth aspect of the present invention, in the signal search method, a feature sequence derived in the reference feature extraction process is applied to the location of the stored signal determined to have a reference signal in the signal detection determination process. And a distance recalculation process for calculating the distance to the feature series derived in the accumulated feature extraction process, and a comparison between the distance derived in the distance recalculation process and the search threshold, the reference signal is accumulated. And a signal detection re-determination process for re-determining whether or not the signal is present at the location.

According to a tenth aspect of the present invention, in the storage feature compression process, each of the feature sequences after the division obtained in the storage feature division process is mapped by the mapping obtained in the compression map determination process. The reference feature compression process includes a feature mapping process and a cumulative projection distance calculation process for calculating a distance between the compressed feature sequence derived in the accumulated feature mapping process and the feature sequence derived in the accumulated feature extraction process. The reference feature mapping process of mapping the feature sequence obtained in the reference feature extraction process by the mapping obtained in the compression mapping determination process, and the compressed feature sequence derived in the reference feature mapping process, And a reference projection distance calculation process for calculating the distance to the feature series derived in the feature extraction process.

According to an eleventh aspect of the present invention, in the reference feature extraction process and the accumulated feature extraction process, features are classified by a predetermined method, and a histogram which is a frequency distribution table for each classification is created. The feature is that the histogram is output as a new feature.

According to a twelfth aspect of the present invention, in the compression mapping determination process, representative features are extracted by principal component analysis.

The invention described in claim 13 registers in advance by calculating the distance from the reference signal to an arbitrary portion of the accumulated signal and determining whether or not the reference signal exists at the portion of the accumulated signal. A signal search program for searching a portion similar to a target reference signal from the stored signal, wherein the signal search program is a reference feature extraction process for deriving a feature sequence from the reference signal, and a window of interest is set in the stored signal. , Accumulated feature extraction processing for deriving a feature series from a signal in the window of interest, accumulated feature segmentation processing for segmenting each feature sequence derived by repeatedly performing the window of interest, and accumulated feature segmentation processing From each of the feature sequences after the classification, a compression map determination process for determining a map for calculating a feature having a dimension lower than that of the feature sequence, and the segment obtained by the accumulated feature segmentation process. Corresponding to each feature series, the low-dimensional features of the than the characteristic sequence, an accumulation feature compression processing for calculating, based on the mapping obtained by the compression map determination process,
Corresponding to the feature series obtained by the reference feature extraction processing,
A reference feature compression process for calculating a feature of a lower dimension than the feature sequence based on the mapping obtained by the compression mapping determination process, a compressed feature sequence derived by the accumulated feature compression process, and the reference feature compression. The inter-compressed-feature distance calculation process for calculating the distance to the compressed-feature series derived by the process, and the distance derived by the inter-compressed-feature distance calculation process are compared with a search threshold that is a threshold corresponding to the distance. Thus, the computer is caused to perform a signal detection determination process of determining whether or not the reference signal exists at the location of the accumulated signal.

According to a fourteenth aspect of the present invention, the signal search program calculates the skip width of the window of interest based on the distance output from the inter-compression-feature distance calculation processing, and sets the window of interest by the skip width. It is characterized in that the computer is further caused to perform a moving skip width calculation process.

According to a fifteenth aspect of the present invention, the signal search program is characterized in that the location of the accumulated signal for which it is determined that the reference signal is present in the signal detection determination process,
A distance recalculation process for calculating the distance between the feature series derived by the reference feature extraction process and the feature series derived by the accumulated feature extraction process, and a distance and a search threshold value derived by the distance recalculation process. By comparing the reference signal with the stored signal, the computer is further caused to perform signal detection re-determination processing for re-determining whether or not the reference signal exists at the location of the accumulated signal.

According to a sixteenth aspect of the present invention, in the storage feature compression processing, storage is performed in which each of the feature sequences after the division obtained in the storage feature division processing is mapped by the mapping obtained in the compression mapping determination processing. The reference feature compression process includes a feature mapping process and a cumulative projection distance calculation process for calculating a distance between the compressed feature sequence derived in the accumulated feature mapping process and the feature sequence derived in the accumulated feature extraction process. The reference feature mapping process for mapping the feature series obtained by the reference feature extraction process by the mapping obtained by the compression map determination process, and the compressed feature sequence derived by the reference feature mapping process, And a reference projection distance calculation process for calculating a distance to the feature series derived by the feature extraction process.

According to a seventeenth aspect of the present invention, in the reference feature extraction process and the accumulated feature extraction process, features are classified by a predetermined method, and a histogram which is a frequency distribution table for each classification is created. The feature is that the histogram is output as a new feature.

According to the eighteenth aspect of the present invention, the compression mapping determination process extracts a representative feature by principal component analysis.

The invention described in claim 19 is characterized in that the signal search program according to any one of claims 13 to 18 is recorded in a computer-readable recording medium.

[0024]

BEST MODE FOR CARRYING OUT THE INVENTION A signal search apparatus according to an embodiment of the present invention will be described below with reference to the drawings. In the present invention,
Although various processing target signals can be used, in the following description, an audio signal and a video signal are used as an example of the processing target signal. <First Embodiment> FIG. 1 is a block diagram showing the arrangement of the first embodiment. In this figure, reference numeral 1 is a reference feature extraction unit that derives a feature sequence from a reference signal. Reference numeral 2 sets a window of interest in the accumulated signal,
It is an accumulated feature extraction unit that derives a feature sequence from the signal in the window of interest. Reference numeral 3 is the accumulated feature extraction unit 2 while shifting the window of interest.
It is an accumulated feature partitioning unit that partitions each feature series output by repeatedly performing the above process. Reference numeral 4 is a compression mapping determination unit that determines a mapping for calculating a feature having a dimension lower than the feature, from each of the feature sequences after the classification output from the accumulated feature partitioning unit 3. Reference numeral 5 is an accumulated feature compression that calculates, based on the mapping output from the compression mapping determination unit 4, a feature that is lower in dimension than the feature and that corresponds to each of the feature sequences after classification output from the storage feature partitioning unit 3. It is a department. Reference numeral 6 is a reference feature compression unit that calculates, based on the mapping output from the compression mapping determination unit 4, a feature that is lower in dimension than the feature and that corresponds to the feature series output from the reference feature extraction unit 1. Reference numeral 7 is an inter-compression-feature distance calculation unit that calculates the distance between the compression feature sequence output from the accumulated feature compression unit 5 and the compression feature sequence output from the reference feature compression unit 6. Code 8
Is a signal for determining whether or not the reference signal is present at the location of the accumulated signal by comparing the distance output from the inter-compression-feature distance calculation unit 7 with a search threshold that is a threshold corresponding to the distance. It is a detection determination unit.

The signal retrieving apparatus shown in FIG. 1 receives a reference signal, that is, an audio signal or video signal as a sample to be retrieved, and a stored signal, that is, an audio signal or video signal to be retrieved, and sets a distance between the reference signal and the signal in advance. The value in the stored signal whose value (called the search threshold) is less than θ ₁ is output.

Next, the operation of the signal search device shown in FIG. 1 will be described with reference to FIGS. Note that, in the following, for simplification of description, a case where the length of the window of interest is set to be the same as the reference signal will be described. However, in “High-speed signal search method, device and recording medium thereof” (Japanese Patent No. 3065314). The same applies to the case of temporally dividing the window of interest as described.

First, the overall operation flow will be described with reference to FIG. Detailed operation of each process will be described later. First, the reference feature extraction unit 1 performs a reference feature extraction process (step S1). Next, the accumulated feature extraction unit 2 performs accumulated feature extraction processing (step S2). Next, the accumulated feature classification unit 3
Accumulation feature classification processing is performed (step S3). Next, the compression mapping determination unit 4 performs compression mapping determination processing (step S).
4). Next, the accumulated feature compression unit 5 performs accumulated feature compression processing (step S5). Next, the reference feature compression unit 6 performs a reference feature compression process (step S6). Next, the processing target is set to the head of the accumulated signal (step S7). Next, the compressed feature distance calculation unit 7 performs a compressed feature distance calculation process (step S8). Next, the signal detection determination unit 8 performs signal detection determination processing (step S9). Next, the skip width calculation unit 9 performs a skip width calculation process (step S
10). Next, the distance recalculation unit 13 performs distance recalculation processing (step S11). Next, the signal detection re-determination unit 14
Performs signal detection re-determination processing (step S12). Subsequently, it is determined whether the current position of the processing target is the end point of the accumulated signal (step S13), and the processes of steps S8 to S12 are repeatedly executed until the end point of the accumulated signal is detected. Then, when the processing up to the end point of the accumulated signal is completed, the search result is output (step S14).

Next, the details of the reference feature extraction processing (step S1) shown in FIG. 4 will be described with reference to FIG. Figure 5
3 is a flowchart showing the operation of the reference feature extraction unit 1. First, the reference feature extraction unit 1 reads the given reference signal (step S11). Subsequently, the reference feature extraction unit 1
Performs feature extraction on the read reference signal (step S12). Then, the feature vector is vector-quantized (step S13).

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 bandpass filter. For example, when it is desired to retrieve a sound signal of about 15 seconds from a broadcast sound signal of television, radio, etc., a good result can be obtained by setting the concrete setting of the feature extraction as follows. That is, seven band pass filters are used, their center frequencies are set at equal intervals on the logarithmic axis, and the analysis window having a time length of about 60 milliseconds is moved by 10 milliseconds, and each of the analysis windows in the analysis window is moved. 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 set of seven-dimensional feature vectors. In this case, one feature vector is obtained every 10 milliseconds.

On the other hand, a color feature is used as a feature for the video signal. For example, 1 from a broadcast video signal from a television, etc.
When a video signal of about 5 seconds is desired to be searched, good results can be obtained by setting the specific settings for feature extraction as follows. That is, each image forming the video is vertically divided into two and horizontally divided into three, RGB values are calculated in each division, and three RGB values obtained in each division, a total of 18 values, are set as a set. 18
Let it be a dimensional feature vector. If the video consists of 30 images per second, one feature vector is obtained every 1/30 second.

Then, a histogram of the feature vector is created from the time series of the feature vector (step 14).
The histogram is created by encoding the feature vector using vector quantization. For example, if the number of code words for vector quantization is 512, the number of bins (sections) in the entire histogram will be 512, and each feature vector will be classified into any one of these 512 bins. . Then, the obtained histogram is output (step S15). In the following description, the histogram created from the reference signal is referred to as the reference histogram.

Next, the details of the accumulated feature extraction processing (step S2) shown in FIG. 4 will be described with reference to FIG. Figure 6
3 is a flowchart showing the operation of the accumulated feature extraction unit 1. First, the accumulated feature extraction unit 2 reads an audio signal or a video signal, which has been accumulated in advance, that is, an accumulated signal (step S16). Next, the accumulated feature extraction unit 2 sets a window of interest at the beginning of the read accumulated signal (step S17). First, an attention window having the same length as the reference signal given to the reference feature extraction unit 1 is set.

Subsequently, the accumulated feature extracting section 2 extracts a feature from the accumulated signal in the window of interest (step S18).
The feature extraction is the same as the process performed by the reference feature extraction unit 1. Further, the accumulated feature extraction unit 2 creates a histogram of feature vectors from the time series of feature vectors in the window of interest (steps S19 and S20). The method of creating the histogram is the same as that performed by the reference feature extraction unit 1. Then, the accumulated feature extraction unit 2
At the start of processing, the window of interest set at the beginning of the accumulated signal is sequentially shifted by one feature vector (step S2).
2) The processes of steps S18 to S20 are repeatedly executed until the end of the accumulated signal (step S1), and the obtained accumulated histogram sequence is output (step S23). In the following description, each histogram created from the accumulated signal is referred to as an accumulated histogram.

Next, the details of the accumulated feature classification process (step S3) shown in FIG. 4 will be described with reference to FIG. Figure 7
3 is a flowchart showing the operation of the accumulation feature classification unit 3. First, the accumulated feature classification unit 3 reads the series of accumulated histograms output from the accumulated feature extraction unit 2 (step S24). Next, the accumulation feature division unit 3 divides this histogram sequence according to a division number given in advance. Although various dividing methods can be considered, the simplest dividing method is used here (step S25). Subsequently, the accumulated feature classification unit 3 outputs the divided accumulated histogram series (step S26).

Next, the details of the compression mapping determination process (step S4) shown in FIG. 4 will be described with reference to FIG. Figure 8
3 is a flowchart showing the operation of the compression mapping determination unit 4. First, the compression mapping determination unit 4 reads the divided histogram series output from the accumulated feature classification unit 3 (step S27). Next, the compression mapping determination unit 4 performs the following KL expansion for each histogram series, and extracts all principal components of each division (step S28).

The KL expansion is performed by the following procedure.
First, the mean histogram and covariance matrix of the histograms in the series are calculated. Histogram series

[Equation 1] The covariance matrix S ^{(j) for} is calculated as follows.

[Equation 2] Here, M is the length of each histogram sequence obtained in the accumulation feature classification unit 3, x ^(j) is the average histogram of X ^(j) ,
(•) ^T represents the transpose of the matrix. Next, the covariance matrix S
^(j) Obtain the eigenvalue and eigenvector of (j = 1, 2, ..., N). The above is the procedure for KL expansion.

Each eigenvector obtained by the KL expansion is called a principal component, and a value obtained by dividing the eigenvalue corresponding to each principal component by the sum of the eigenvalues of all principal components is called the contribution rate of that principal component. Next, the compression mapping determination unit 4 rearranges the principal components in descending order of the contribution rate, and sequentially selects the principal components until the total value of the contribution rates exceeds a contribution threshold given in advance (steps S29 and S30). ). Then, using the selected principal component as a basis, a subspace corresponding to each division is formed, and the projection to the subspace is used as a mapping for the division (step S
31). Next, the compression mapping determination unit 4 outputs the obtained set of subspaces (step S32).

Next, the details of the accumulated feature compression processing (step S5) shown in FIG. 4 will be described with reference to FIGS.
9 to 11 are flowcharts showing the operation of the accumulated feature compression unit 5. First, the accumulated feature compression unit 5 reads the divided histogram output from the accumulated feature partitioning unit 3 and the set of subspaces output from the compression mapping determination unit 4 (step S33). Next, the accumulated feature compression unit 5 executes the accumulated feature mapping process (step S34) and the accumulated projective distance calculation process (step S35). Here, the accumulated feature mapping process (step S34) will be described with reference to FIG. First, the set of divided histograms and subspaces read in step S33 is input (step S37). Next, each histogram of the series is projected onto the subspace created from the series (step S38).
The set of subspace bases obtained from the histogram sequence X ^(j)

[Equation 3] And the compressed histogram series

[Equation 4] Is calculated as follows:

[Equation 5] However, N is the number of divisions of the histogram series, and K (j) is X
the number of basis of the subspace obtained from ^(j) ,

[Equation 6] Is. Then, the obtained storage compression histogram sequence is output (step S39).

Next, the cumulative projection distance calculation process (step S
35) will be described with reference to FIG. First, the divided histogram sequence output from the accumulation feature division unit 3, the set of subspaces output from the compression mapping determination unit 4, and the accumulation compression histogram sequence obtained by the accumulation feature mapping process (steps S37 to S39) are Read (Step S
40). Next, the distance between each histogram and the corresponding compressed histogram is calculated by the following formula. By inversely projecting the compressed histogram, the position of the compressed histogram in the space where the histogram exists is obtained (steps S41 and S42).

[Equation 7] However,

[Equation 8] And each

[Equation 9] Represents the position of the compressed histogram y _i ^{(j) in} the histogram space.

[Equation 10] The distance between and is defined as the distance between the histogram and the compressed histogram, and this is called the projected distance of the histogram x _i ^(j) . That is, the projective distance of x is defined as follows using the Euclidean distance.

[Equation 11] However, n is the number of dimensions of the histogram,

[Equation 12] Is.

Accumulation feature mapping processing (steps S37 to S3)
9) The compressed histogram y = (y ₁ ,
y ₂ , ..., y _K ) and the projection distance obtained by the accumulated projection distance calculation process (steps S40 to S43) corresponding to this

[Equation 13] Then, the compression feature y ^* is constructed as follows.

[Equation 14] However, K is the number of dimensions of the compression histogram y.

Next, details of the reference feature compression processing (step S6) shown in FIG. 4 will be described with reference to FIGS. 12 to 14 are flowcharts showing the operation of the reference feature compression unit 6. First, the reference feature compression unit 6 reads the reference histogram output from the reference feature extraction unit 1 and the set of subspaces output from the compression mapping determination unit 4 (step S44). Next, the reference feature compression unit 5 executes a reference feature mapping process (step S45) and a reference projective distance calculation process (step S46).

Here, the reference feature mapping process (step S4)
5) will be described with reference to FIG. First, step S
The set of histograms and subspaces read in 44 is input (step S48). Next, the reference histogram is projected onto each subspace (step S49). The projection is performed by the same operation as the accumulated feature mapping process (step S38). For example, if the number of divisions of the accumulated histogram series is M = 1000, 1000 compressed histograms are created. Next, the obtained set of reference compression histograms is output (step S50).

Next, reference projection distance calculation processing (step 4
6) will be described with reference to FIG. First, the histogram output from the reference feature extraction unit 1 and the compression mapping determination unit 4
The set of subspaces output from the above and the set of compressed histograms obtained by the reference feature mapping process (steps S48 to S50) are read (step S51). next,
The distance between the histogram and each compressed histogram, that is, the projection distance of the histogram is calculated. By inversely projecting the compressed histogram, the position of the compressed histogram in the space where the histogram exists is obtained (step S5).
2, S53). The calculation is performed by the same operation as the cumulative projection distance calculation process. Then, each projection distance obtained here is output (step S54). Next, the compression feature is configured in the same manner as the accumulated feature compression unit 5 from the compression histogram obtained by the reference feature mapping process and the corresponding projection distance obtained by the reference projection distance calculation process. Then, the reference feature compression unit 6 outputs the obtained set of reference compression features (step S47).

Details of the compression feature distance calculation process (step S8) shown in FIG. 4 will be described below with reference to FIG. FIG. 15 is a flowchart showing the operation of the compression feature distance calculation unit 7. First, the compression feature distance calculation unit 7
Reads the set of accumulated compression feature series output from the accumulated feature compression unit 5 and the reference compressed feature output from the reference feature compression unit 6 (step 55). Next, the inter-compression-feature distance calculation unit 7 calculates the distance between the reference compression feature y ^* _R and the accumulated compression feature y ^* _S (step S56). Distance d (y ^* _R , y
^* _S ) is defined as follows using the Euclidean distance.

[Equation 15] Where x _R is a reference histogram, x _S is a cumulative histogram, y _R and y _S are compression histograms corresponding to x _R and x _S ,

[Equation 16] Is the position of y _R and y _{S in} the histogram space, y ^* _Ri ,
And y ^* _Si are the values of the i-th dimension of y ^* _R and y ^* _S , respectively. The following formula is established due to the nature of the KL expansion (principal component analysis).

[Equation 17] Furthermore, d (y ^* _R , y ^* _S ) has the following properties.

[Equation 18] However, the minimum value in equation (4) is

[Formula 19] A set of all histograms (x _R ,
x _S ). From the formula (4), for the principal component analysis,
From the property (3), there is a peculiar effect that the distance value between the compression features becomes the lower limit value of the distance between the histograms. Further, by using the projection distance, it is possible to obtain a larger lower limit value d (y ^* _R , y ^* _S ) of the distance between the histograms as compared with the case where it is not used. Next, the compression feature distance calculation unit 7 outputs the lower limit value of the obtained distance (step S57).

Details of the signal detection determination process (step S9) shown in FIG. 4 will be described below with reference to FIG. Figure 1
6 is a flowchart showing the operation of the signal detection determination unit 8. First, the signal detection determination unit 8 reads the distance lower limit value output from the inter-compression-feature distance calculation unit 7 (step S
58). Next, the lower limit value of distance is compared with the search threshold value that is a predetermined value based on the Euclidean distance that is a distance measure (step S59). As a result of this comparison, when the distance value is below the search threshold value (when the attention window is divided in the time direction, it is found that the distance value is below the search threshold value in all time divisions), the reference signal is Then, it is determined that the accumulated signal is present at that location, and the current position in time series for the accumulated signal is output as the signal detection result (step S60).

<Second Embodiment> FIG. 2 is a block diagram showing the arrangement of a signal search apparatus according to the second embodiment. The signal search apparatus shown in FIG. 2 is different from the signal search apparatus shown in FIG. 1 in that the skip width of the window of interest is calculated based on the distance output from the inter-compression-feature distance calculation unit 7, and only the skip width is calculated. This is that a skip width calculation unit 9 for moving the window of interest is newly provided. By providing the skip width calculation unit 9, the reference signal, that is, the sample audio signal or video signal to be searched and the accumulated signal, that is, the audio signal or video signal to be searched are input.
A location in the accumulated signal whose distance from the reference signal is a preset value (referred to as a search threshold) is less than θ ₁ is output.

Next, the operation of the signal search device shown in FIG. 2 will be described with reference to FIG. FIG. 17 is a flowchart showing the operation of the skip width calculation unit 9. First, the skip width calculation unit 9 reads the distance lower limit value output from the inter-compression-feature distance calculation unit 7 (step S61). Next, the feature matching, that is, the skip width that can omit the distance calculation is calculated while ensuring that no omission of the search occurs (step S62). Then, the window of interest is shifted by the obtained skip width (step S63). Subsequent processing operations are the same as those of the signal search device according to the first embodiment, and therefore description thereof is omitted here.

Here, the principle of determining the skip width will be described. Since the histogram is obtained by classifying and accumulating time series of feature vectors, the distance value between the histograms does not change abruptly with the movement of the time window with respect to the feature vector of the accumulated signal. The absolute value of the change rate of the distance value per movement of one feature vector of the time window is (√
Do not exceed 2). That is, when the distance value between the histograms when the head of the time window for the accumulated signal is the m1th feature vector is d (x _R , x _S (m ₁ )), the time window is up to the m2th feature vector. Lower limit of distance value when moving

[Equation 20] Is given by the following equation when m ₁ <m ₂ <m ₁ + D.

[Equation 21] However, D represents the width of the time window. From the equation (4), the equation (5) is transformed as follows.

[Equation 22] Since the distance value does not fall below 0, the lower limit value given by equation (6)

[Equation 23] When is less than 0, 0 is the lower limit value. By replacing the lower limit with the search threshold θ ₁ and replacing m ₂ −m ₁ with the skippable width w, the skippable width can be obtained as follows.

[Equation 24] However, floor (x) represents the maximum integer not exceeding x. At the start of the process, the compressed storage feature is extracted from the beginning of the compression feature series, but in the process of the process, the process proceeds while sequentially shifting the position of extracting the compressed storage feature in the time direction. The amount of shift in the time direction is given by the skip width calculation unit 9.

<Third Embodiment> FIG. 3 is a block diagram showing the arrangement of a signal search apparatus according to the third embodiment. The signal search device shown in FIG. 3 is different from the signal search device shown in FIG. 2 in that the reference feature extraction unit 1 outputs the location of the accumulated signal for which the signal detection determination unit 8 determines that the reference signal exists. Feature series and accumulated feature extraction unit 2
By comparing the distance output from the distance recalculation unit 13 with the search threshold, the reference signal is present at the location of the accumulated signal. The point is that a signal detection re-determination unit 14 that re-determines whether or not to perform is newly provided.

By providing the distance recalculation unit 13 and the signal detection redetermination unit 14, the reference signal, that is, the audio signal or video signal to be searched as a sample, and the accumulated signal, that is, the audio signal or video signal to be searched, are stored. As an input, the position in the accumulated signal whose distance to the reference signal is a preset value (referred to as a search threshold) is less than θ ₁ is output.

Next, the operation of the signal search device shown in FIG. 3 will be described with reference to FIGS. Here, only the operations of the newly provided distance recalculation unit 13 and signal detection redetermination unit 14 will be described. FIG. 18 is a flowchart showing the operation of the distance recalculation unit 13. FIG. 19 is a flowchart showing the operation of the signal detection redetermination unit 14. First, the distance recalculation unit 13 reads the histogram output from the reference feature extraction unit 1, the histogram series output from the accumulated feature extraction unit 2, and the detection result output from the signal detection determination unit 8 (step S64). Next, the distance from the reference histogram is calculated for the accumulated histogram corresponding to the location in the accumulated signal where the reference signal is determined to exist (step S65). The distance between the histograms is defined using Euclidean distance as in equation (1). Then, the calculated distance value is output (step S66).

Next, the signal detection re-determination unit 14 reads the distance value output from the distance re-calculation unit 13 (step S
67). Next, the distance value and the search threshold value are compared (step S68). As a result of this comparison, when the distance value is less than the search threshold value (when the target window is divided in the time direction,
If the distance value is found to be less than the search threshold in all time divisions), it means that the reference signal was present in the accumulated signal.Therefore, as a signal detection result, the current position in the time series for the accumulated signal is detected. Is output (step S
69).

In the signal search device shown in FIG.
The skip width calculation unit 9 may be provided if necessary, and may not be provided if not required.

<Experimental Results> Next, the operation experimental results of the signal retrieval apparatus according to the present invention will be described. In order to confirm the effect of the signal search device according to the present invention, first, a video signal of 24 hours is used as a storage signal, and a search is performed on 10 randomly selected reference signals (15 seconds), and the number of collations and The time required for the processing related to the signal detection re-determination unit 14 from the reference feature compression unit 6, that is, the time required for the search after the reference signal was given (search time) was examined. The search parameters are: sampling frequency = 29.97 Hz, image division number = 6 (vertical 2 division, horizontal 3 division), histogram bin number = 256, time window width = 15 seconds, no time window division, accumulated histogram Number of divisions of series = 100, search threshold = 50,
The contribution threshold value is 0.975.

The results of this experiment are shown in FIG. The average of the number of collations for 10 reference signals is 194 by a known method.
33 times, the method of the present invention 22721 times, the method of using the compressed histogram as a compression feature without performing the cumulative projective distance calculation process and the reference projective distance calculation process in the method of the present invention (in the table, ")
It was 6 times. Further, the average of the search execution times for the 10 reference signals is 165.1 milliseconds by the known method, 84.1 milliseconds by the method of the present invention, and the accumulated projection distance calculation processing and the reference projection distance are performed by the method of the present invention. It was 95.2 milliseconds by the method in which the calculation processing was not performed.

Next, using a sound signal of 24 hours as an accumulation signal, a search was performed for 10 randomly selected reference signals (15 seconds), and the number of collations and the search time were examined. Search parameters are: sampling frequency = 32kHz,
Number of bandpass filters = 7, analysis window length of frequency analysis = 60 m
sec, analysis window shift = 10 msec, histogram bin number = 256, time window width = 15 seconds, no time window division, accumulation histogram sequence division number = 1000, search threshold = 70, contribution threshold = 0.9. .

The results of this experiment are shown in FIG. The average of the number of collations for 10 reference signals is 143 by a known method.
765 times, 241739 times by the method of the present invention, and 568190 times by the method in which the cumulative projection distance calculation processing and the reference projection distance calculation processing are not performed in the method of the present invention. The average search execution time for 10 reference signals is
It was 1774 msec by the known method, 250 msec by the method of the present invention, and 679 msec by the method in which the accumulated projective distance calculation process and the reference projective distance calculation process were not performed in the method of the present invention.

As is clear from the experimental results, the number of collations is increased as compared with the known method, but the same retrieval result is obtained by significantly reducing the time required for one collation by using the compression feature. It can be seen that the search execution time can be significantly reduced while guaranteeing.

As described above, according to the present invention,
By performing feature compression in advance for each partial section of the accumulated signal and performing a search while significantly reducing the cost of matching calculation, compared to known methods, a faster matching signal search can be performed with less matching calculation time. It can be performed.

It should be noted that a program for realizing the function of each processing unit in FIGS. 1 to 3 is recorded in a computer-readable recording medium, and the program recorded in this recording medium is read into a computer system and executed. Therefore, the signal search processing may be performed. The “computer system” mentioned here includes an OS and hardware such as peripheral devices. In addition, the “computer system” includes a homepage providing environment (or display environment) if a WWW system is used. Further, the “computer-readable recording medium” refers to a portable medium such as a flexible disk, a magneto-optical disk, a ROM, a CD-ROM, or a storage device such as a hard disk built in a computer system. Further, the "computer-readable recording medium" is a volatile memory (RAM) inside a computer system which serves as 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 that hold the program for a certain period of time are also included.

Further, the above 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. Further, the program may be a program for realizing some of the functions described above. further,
It may be a so-called difference file (difference program) that can realize the above-mentioned functions in combination with a program already recorded in the computer system.

[0062]

As described above, according to the present invention, the distance from the reference signal is calculated for an arbitrary portion of the accumulated signal, and it is determined whether or not the reference signal exists at that portion of the accumulated signal. As a result, in the signal search device that searches for a portion similar to the target reference signal from the stored signal registered in advance, the search speed can be increased by compressing the characteristic information, and the amount of stored information can be reduced. The effect that can be obtained is obtained. Further, as compared with the conventional method, it is possible to detect a signal at a higher speed by efficiently suppressing the dimension of the feature while ensuring that no search omission occurs. In addition, it is possible to detect a signal at a higher speed by effectively suppressing the dimension of a very small amount while guaranteeing the same search result.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of a first exemplary embodiment of the present invention.

FIG. 2 is a block diagram showing a configuration of a second exemplary embodiment of the present invention.

FIG. 3 is a block diagram showing a configuration of a third exemplary embodiment of the present invention.

FIG. 4 is a flowchart showing a processing operation of the signal search device according to the present invention.

5 is a flowchart showing the operation of the reference feature extraction unit 1 shown in FIG.

FIG. 6 is a flowchart showing an operation of the accumulated feature extraction unit 1 shown in FIG.

FIG. 7 is a flowchart showing an operation of the accumulated feature classification unit 3 shown in FIG.

8 is a flowchart showing the operation of the compression mapping determination unit 4 shown in FIG.

9 is a flowchart showing the operation of the accumulated feature compression unit 5 shown in FIG.

10 is a flowchart showing an operation of the accumulated feature compression unit 5 shown in FIG.

11 is a flowchart showing the operation of the accumulated feature compression unit 5 shown in FIG.

12 is a flowchart showing the operation of the reference feature compression unit 6 shown in FIG.

13 is a flowchart showing an operation of the reference feature compression unit 6 shown in FIG.

FIG. 14 is a flowchart showing an operation of the reference feature compression unit 6 shown in FIG.

FIG. 15 is a flowchart showing an operation of a compression feature distance calculation unit 7 shown in FIG. 1.

16 is a flowchart showing the operation of the signal detection / determination unit 8 shown in FIG.

FIG. 17 is a flowchart showing an operation of the skip width calculation unit 9 shown in FIG.

FIG. 18 is a flowchart showing an operation of the distance recalculation unit 13 shown in FIG.

19 is a flowchart showing the operation of the signal detection re-determination unit 14 shown in FIG.

FIG. 20 is an explanatory diagram showing an experimental result of signal search.

FIG. 21 is an explanatory diagram showing experimental results of signal search.

[Explanation of symbols]

1 ... Reference feature extraction unit 2 ... Accumulation feature extraction unit 3 ... Accumulation feature classification section 4 ... compression map determination unit 5 ... Accumulation feature compression unit 6 ... Reference feature compression unit 7: Compressed feature distance calculation unit 8 ... Signal detection determination unit 9: Skip width calculation unit 13: Distance recalculation unit 14 ... Signal detection re-determination unit

   ─────────────────────────────────────────────────── ─── Continued front page    (72) Inventor Takayuki Kurozumi             2-3-1, Otemachi, Chiyoda-ku, Tokyo             Inside Telegraph and Telephone Corporation (72) Inventor Hiroshi Murase             2-3-1, Otemachi, Chiyoda-ku, Tokyo             Inside Telegraph and Telephone Corporation F-term (reference) 5C052 AA01 AC08 DD04 DD06                 5C053 FA14 HA29 JA05                 5D015 HH04                 5L096 FA00 GA17 JA11

Claims (19)

[Claims] 1. A method of calculating a distance between a reference signal and an arbitrary portion of a stored signal and determining whether or not the reference signal exists at the portion of the stored signal, thereby determining a target from the stored signal registered in advance. A signal search device that searches for a portion similar to the reference signal, wherein the signal search device is a reference feature extraction unit that derives a feature sequence from the reference signal, and sets a target window in the stored signal, An accumulated feature extraction unit that guides a characteristic sequence, an accumulated feature division unit that divides each characteristic sequence derived by repeatedly performing the attention window while shifting, and each divided feature sequence obtained by the accumulated feature division unit From the compression series determining unit for determining a mapping for calculating a feature of a lower dimension than the feature series, and corresponding to each feature series after the division obtained by the accumulated feature division unit, more than the feature series Low A dimensional feature, which is lower in dimension than the feature sequence, corresponding to the accumulated feature compression unit that calculates the dimensional feature based on the mapping obtained by the compression mapping determination unit and the feature sequence obtained by the reference feature extraction unit. , A reference feature compression unit that calculates based on the mapping obtained by the compression mapping determination unit, a compression feature sequence derived by the accumulated feature compression unit, and a compression feature sequence derived by the reference feature compression unit. By comparing the distance between the compressed features for calculating the distance between the compressed features and the distance introduced by the distance between the compressed features calculator and the search threshold value which is the threshold value corresponding to the distance, the reference signal is the accumulated signal. 2. A signal search device comprising: a signal detection determination unit that determines whether or not it exists at the location. 2. The signal search device calculates a skip width of a window of interest based on the distance output from the inter-compression-feature distance calculation section, and a skip width calculation section that moves the window of interest by the skip width. The signal search device according to claim 1, further comprising: 3. The signal search device, wherein the feature series derived by the reference feature extraction unit and the stored feature extraction unit for the location of the stored signal determined to have a reference signal by the signal detection determination unit. In the distance recalculation unit that calculates the distance to the feature series derived in step (1), the reference signal is present at the location of the accumulated signal by comparing the distance derived by the distance recalculation unit and the search threshold. The signal search device according to claim 1 or 2, further comprising: a signal detection re-determination unit that re-determines whether or not. 4. The accumulated feature compressing section stores each of the divided feature series obtained by the accumulated feature dividing section,
The distance between the accumulated feature mapping unit that is mapped by the mapping obtained by the compression mapping determination unit and the compressed feature sequence guided by the accumulated feature mapping unit is calculated with respect to the characteristic sequence guided by the accumulated feature extraction unit. And a reference feature mapping unit configured to map the feature series obtained by the reference feature extraction unit by the mapping obtained by the compression mapping determination unit, and the reference feature compression unit. For the compressed feature series derived by the feature mapping unit,
4. The signal search device according to claim 1, further comprising a reference projection distance calculation unit that calculates a distance to the feature series derived by the reference feature extraction unit. 5. The reference feature extraction unit and the accumulated feature extraction unit classify features by a predetermined method, create a histogram that is a frequency distribution table for each classification, and regard the histograms as new features. The signal search device according to any one of claims 1 to 4, wherein the signal search device outputs the signal. 6. The compression mapping determination unit extracts a representative feature by principal component analysis.
6. The signal search device according to any one of 5 to 5. 7. The distance from a reference signal is calculated for an arbitrary location of the stored signal, and it is determined whether or not the reference signal exists at the location of the stored signal. A signal search method for finding a portion similar to the reference signal, wherein the signal search method is a reference feature extraction process of deriving a feature sequence from the reference signal, A stored feature extraction process for deriving a feature sequence, a stored feature segmentation process for segmenting each feature sequence derived by repeatedly performing the feature window while shifting, and each feature sequence after segmentation obtained in the accumulated feature segmentation process From the above, the compression mapping determination process for determining a mapping for calculating a feature having a lower dimension than the feature sequence, and the feature corresponding to each feature sequence after the division obtained in the accumulated feature division process A feature having a lower dimension than a sequence, corresponding to a feature sequence obtained in the reference feature extraction process, and an accumulated feature compression process in which the feature is calculated based on the map obtained in the compression map determination process,
A reference feature compression process for calculating a feature of a lower dimension than the feature sequence based on the mapping obtained in the compression map determination process, a compression feature sequence derived in the accumulated feature compression process, and the reference feature compression. Comparing the inter-compression-feature distance calculation process for calculating the distance with the compression-feature sequence derived in the process, and the distance derived in the inter-compression-feature distance calculation process, and a search threshold that is a threshold corresponding to the distance. As a result, a signal search method comprising: a signal detection determination step of determining whether or not the reference signal exists at the location of the accumulated signal. 8. The signal search method calculates a skip width of a window of interest based on the distance output from the inter-compression-feature distance calculation step, and performs a skip width calculation step of moving the window of interest by the skip width. The signal search method according to claim 7, further comprising: 9. The signal retrieving method comprises: a feature series derived in the reference feature extraction process and a stored feature extraction process for the location of the stored signal in which the reference signal is determined to exist in the signal detection determination process. In the distance recalculation process of calculating the distance to the feature sequence derived in step (1), and by comparing the distance derived in the distance recalculation process with the search threshold value, the reference signal is present at the location of the accumulated signal. 9. The signal search method according to claim 7, further comprising: a signal detection re-determination step of re-determining whether or not. 10. The accumulated feature compression step, wherein the accumulated feature mapping step of mapping each of the feature sequences after the division obtained in the accumulated feature division step by the mapping obtained in the compression map determination step, A compressed feature sequence derived in the feature mapping process, and a cumulative projection distance calculation process for calculating a distance from the feature sequence derived in the accumulated feature extraction process, wherein the reference feature compression process is the reference feature extraction process. The reference feature mapping process of mapping the feature sequence obtained in step (3) by the mapping obtained in the compression map determination process, and the compressed feature sequence derived in the reference feature mapping process, are derived in the reference feature extraction process. 10. The signal search method according to claim 7, further comprising a reference projective distance calculation process for calculating a distance to the feature series. 11. In the reference feature extraction process and the accumulated feature extraction process, features are classified by a predetermined method, a histogram that is a frequency distribution table for each classification is created, and the histogram is regarded as a new feature. The signal retrieval method according to claim 7, wherein the signal retrieval method outputs the signal. 12. The signal search method according to claim 7, wherein in the compression mapping determination process, representative features are extracted by principal component analysis. 13. A method for calculating a distance from a reference signal to an arbitrary portion of a stored signal and determining whether or not the reference signal exists at the portion of the stored signal, thereby determining a target from a stored signal registered in advance. A signal search program for finding a portion similar to the reference signal, wherein the signal search program is a reference feature extraction process for deriving a feature sequence from the reference signal, and setting a window of interest in the accumulated signal, An accumulated feature extraction process for deriving a feature sequence, an accumulated feature segmentation process for segmenting each feature sequence derived by repeatedly performing the window of interest, and each segmented feature sequence obtained by the accumulated feature segmentation process. From the compression sequence determination process for determining a map for calculating a feature having a dimension lower than that of the feature sequence, and corresponding to each feature sequence after classification obtained by the accumulated feature classification process. The feature series having a lower dimension than the feature series corresponds to the feature series obtained by the reference feature extraction processing, and the accumulated feature compression processing for calculating the feature based on the mapping obtained by the compression mapping determination processing.
A reference feature compression process for calculating a feature of a lower dimension than the feature sequence based on the mapping obtained by the compression mapping determination process, a compressed feature sequence derived by the accumulated feature compression process, and the reference feature compression The inter-compression-feature distance calculation process for calculating the distance to the compression-feature series derived by the process, and the distance derived by the inter-compression-feature distance calculation process and a search threshold value that is a threshold value corresponding to the distance are compared. As a result, the signal search program is characterized by causing a computer to perform a signal detection determination process of determining whether or not the reference signal exists at the location of the accumulated signal. 14. The signal search program calculates a skip width of a window of interest based on the distance output from the inter-compression-feature distance calculation processing, and performs a skip width calculation processing of moving the window of interest by the skip width. The signal search program according to claim 13, which is further executed by a computer. 15. The signal search program includes a feature series derived by the reference feature extraction process and a stored feature extraction process for the location of the stored signal determined to have a reference signal in the signal detection determination process. In the distance recalculation processing for calculating the distance to the feature series derived in step (1), and by comparing the distance derived in the distance recalculation processing with the search threshold value, the reference signal is present at the location of the accumulated signal. 15. The signal search program according to claim 13 or 14, further comprising: a signal detection re-determination process for determining again whether or not the signal is detected. 16. The accumulated feature compressing process, wherein the accumulated feature mapping process maps each segmented feature series obtained by the accumulated feature segmenting process by a map obtained by the compression map determination process, The compressed feature series derived in the feature mapping process includes a cumulative projective distance calculation process for calculating a distance from the feature series derived in the accumulated feature extraction process, wherein the reference feature compression process is the reference feature extraction process. The reference feature mapping process that maps the feature sequence obtained in step S1 by the map obtained in the compression map determination process, and the compressed feature sequence derived in the reference feature mapping process is introduced in the reference feature extraction process. The signal search program according to any one of claims 13 to 15, further comprising a reference projective distance calculation process for calculating a distance to a feature series. 17. The reference feature extraction process and the accumulated feature extraction process classify features by a predetermined method, create a histogram that is a frequency distribution table for each classification, and regard the histogram as a new feature. The signal search program according to any one of claims 13 to 16, which outputs the signal. 18. The signal search program according to claim 13, wherein the compression mapping determination process extracts a representative feature by principal component analysis. 19. A computer-readable recording medium in which the signal search program according to claim 13 is recorded.