JPS592954B2 - pattern luigi dokeisan sochi - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention also relates to an improvement of a device that calculates the degree of similarity between time-series patterns such as voice patterns.

Conventionally, speech recognition devices using this type of pattern similarity calculation device first ask the user to recognize the word (
numbers, place names, etc.), and the speech pattern for each word is stored in the device 5 as a standard pattern.

Next, a comparison operation (pattern matching) is performed on the input unknown word sounds (called input patterns) with each standard pattern, the degree of matching between the two (pattern similarity) is checked, and the maximum matching The obtained standard pattern is determined, and it is determined that the standard pattern belongs to the same 30 words. In this case, the main cause of pattern variation is variation in speaking speed. As a result, the audio pattern expands and contracts nonlinearly in the time axis direction. For this reason, simply calculating the distance between the input pattern and the standard pattern does not allow accurate pattern matching35, resulting in many recognition errors. Therefore, when matching patterns that expand and contract rapidly in the time axis direction, such as audio patterns, it is difficult to obtain a sufficiently accurate degree of similarity using the matching method described above. It becomes necessary to remove it. Regarding this issue, a method can be considered that approximates the time axis fluctuation of time series patterns by nonlinear transformation and determines the similarity between patterns while removing the influence of the time axis deviation between patterns. As a method for achieving this with high accuracy, a DP matching method has been considered in which a dynamic programming method (hereinafter abbreviated as DP) is used to calculate a degree of similarity by normalizing fluctuations in the time axis. The following describes the DP matching method in a known document (Journal of the Acoustical Society of Japan, VOL 27, 9, 1971, P
483-P49O "Continuous word recognition based on temporal normalization of speech using dynamic programming"), a speech pattern will be briefly explained as an example. Speech patterns are generally expressed as a time series of feature vectors. As a feature vector, for example, the output of a 16-channel frequency analysis filter (spectrum analysis device) can be time-sampled at a certain point in time. If the sound pattern A is an input pattern and the sound pattern B is another standard pattern, it is expressed as 〇Here, the correspondence between the feature vectors Ai and Bj is expressed as i=i(
j), when A. The similarity between patterns in 5B is ▲ 1
υ Todoroki Otori' - Defined as a tool.

This method is said to be a stable measure against variations in speech speed. That is, the correspondence between time axes 1 and j is optimally determined, the sum of the distances between Ai and Bj is minimized, and the similarity between batons is defined as the minimum value of the average of the above distances over the entire pattern? This minimization problem can be handled by the following DP.

However, d(1,j) is the distance between Ai and Bj.

That is, by sequentially calculating equation (4) and taking the subpattern Al of A to obtain g(1, J)0, by dividing this by l+J, Al. ! : This is a method of calculating the similarity of B as 〇Here, by setting l=, the similarity between patterns S(A
,B) can be calculated.

In this case, as shown in FIG. 1, equation (5) limits the allowable range for (1, j), which is hereinafter referred to as a matching window and indicated by NW according to the literature.

That is, for a certain number r.

Further, the set of (1, j) where j is constant and is included in the window NW is called the j-th stage.

As a specific method for calculating equation (8), the recurrence equation of equation (4) is calculated sequentially in the direction of increasing i within the same stage, and then moves to the (''+1)th stage. Run it with

In this way, after execution up to stage J, g(
1, J): (J-r≦′≦J+r) are all found, and (
8) The similarity S(Al, B) of the equation can be calculated. The above is the algorithm for time-normalized similarity calculation using the DP matching method.

When this method is implemented using a specific device,
5-114149 (Special Publication No. 50-19227) "Pattern Similarity Calculator Mountain Cl As you can see, especially regarding the calculation of the recurrence formula of equation (4), if you try to execute the recurrence formula of the Jth stage now, As can be seen from equation (4), the value of the previous recurrence formula, that is, the value g (1, j-1) of the (j-1)th stage, is expressed as j-r-1≦i≦j+r-1 with respect to i. A previous value storage circuit that stores NW values within the matching window is required, and when processing the (j+1)th stage, the jth
Value of the recurrence formula of the stage g(1, j): (j-r≦i≦j+r)
In order to use Two storage circuits are required.

Furthermore, when executing the (J+1)th stage recurrence formula after executing the jth stage recurrence formula, prior to execution, the previous value storage circuit that stores the value of the (j-1)th stage is It is necessary to update the contents with the contents of the current value storage circuit that stores the value of stage j.

As mentioned above, the recurrence formula calculation unit consisting of two memory circuits has the disadvantage that the device becomes complex and large, and also requires the operation of updating the contents of the memory circuit in advance when executing the recurrence formula. This has the disadvantage of slowing down the processing speed.

An object of the present invention is to provide a pattern similarity calculation device that eliminates the above-mentioned drawbacks and executes the recurrence formula processing of equation (4) with a simple circuit configuration and at high speed. is characterized by having a memory circuit for storing the value g (1, j) of the recurrence formula in terms of recurrence formula processing, with j being constant, and the minimum value of i determined by that j. corresponds to the lowest memory address n of the memory circuit, and the value g(1-1,j)
(from n-1 sowings, the value g(1,j-1) is (n+1)
The configuration is such that the value g(1-1,j-1) is read from address n, the resulting value g(1,j) is stored in address n, and n or i is sequentially increased to the maximum value determined by j. The purpose of this increase is to perform calculations of recurrence formulas for a constant j at high speed and without contradiction.

Hereinafter, one embodiment of the present invention will be described in detail with reference to the drawings.

FIG. 2 is a block diagram of an embodiment of a pattern similarity calculation device according to the present invention. 1 inputs Ai and bj from input terminals A and B for a certain 1 and J, and outputs the distance d (1, j) or 2d (1, j) between the vectors to the signal line c according to equation (6). This is the distance calculation section.

2 is a recurrence formula calculation unit that executes the recurrence formula calculation of formula (4) for one stage, and 6 is an address assignment from A1 to ANW that has NW memory sections for storing one stage of the value of the recurrence formula. This is a memory circuit that has been designed.

4 is the output d(1,j), 2d(1,j
) and the output of the memory circuit 6, and 5 successively compares the numerical values input from the signal line E a certain number of times, and calculates the minimum value among the input numerical values. This is a minimum value detection circuit that outputs the value to the signal line F.

Considering this configuration, let us now consider executing the j-th stage recurrence formula.

At this time, NW values g(1,
j-1): j-r-1≦1≦j+, -1 is assumed to be stored in a storage circuit of 6 in correspondence with the minimum i value of the matching window and the lowest memory address. FIG. 3 shows the contents of the storage circuit 6 when NW=7 (that is, r=3), and 61 shows the state after the (j-1)th stage is executed.
62 indicates the state during and after the execution of the jth stage 0
The following explanation will be given assuming NW=7. Here, when executing the j-th stage, the value of the recurrence formula to be obtained and the value of the (j-1)th stage are converted and considered as follows, and the three terms in equation (4) and the In figure 3, path a, path b, path c
Think about it in response to.

First, when determining GAl(j), the contents of the address corresponding to An in FIG. 4 are sequentially read from the memory circuit 6, and
It is output to the adder circuit using signal line D. At the same time, the signal line C receives d(j-3,j) from the distance calculation unit 1 during cycle Tll in FIG. 4, and d(j-3, j) during cycle Tl2 in FIG.
3, j), 2d(j-3, j) is output in cycle Tl3, and addition is performed to obtain each term i=J-3, j=j in the recurrence formula of equation (4). is calculated. Outputs corresponding to each term are input to five minimum value detection circuits via signal line E.

If the number of comparisons is set to 3 in the minimum value detection circuit No. 5, the minimum value among path A, path B, and path c is detected in cycle Tl4, and at the same time, the minimum value of path A (n
) by the write signal W/R.

In this case, GAl(j-1) is stored at address A(1), but it will not be used in subsequent processing. Through these series of operations, the value of GA,(j) can be obtained.

Similarly, the value of GA2(j) is 1/T2
Memory address A(n
) can be obtained by changing as shown in FIG. In this case, path a requires the value of the jth stage, but at the stage of calculating GA,(J), since GAl(j) is stored at address A(1), calculation of equation (4) is necessary. can be executed without contradiction. In other words, generally when calculating the value of GAO(1), as shown in Figure 4, address A(n-1) corresponds to path a, and address A(n+
1) By outputting to four adder circuits from address A(n) corresponding to address and bus c, cycle Tn
4, the minimum value among them is calculated and stored at address A(n). The above operation is performed in the direction of increasing i,
At the same time, n is also increased and the operations are performed sequentially. In this case, address An may be at the boundary point in Figure 4, and O and 8 may be taken, but in that case, if a sufficiently large value is output to signal line D, equation (4) can be executed without contradiction. can. By performing the above operation NW (-7) times in this way, all the values of the recurrence formula regarding the j-th stage of equation (4) are stored in the storage circuit 6. ) stage is also completed at the same time. Further, when j=1, by storing the initial value shown by equation (3) in the memory circuit 6, the above operations are executed sequentially from j=2, and after the operation of j=J is completed, the initial value shown by the formula (3) is stored. In the memory circuit (8)
g(1, J) used in the equation: 0 in which all (Jgo≦2≦J+r) are stored.The value of this recurrence formula is outputted via the signal line G. 3 also inputs the value of the recurrence formula in 2 from the calculation unit via the signal line G, normalizes it according to equation (8), and uses the minimum value as the similarity to the signal line. This is a similarity calculation unit that outputs to H.

Each of the above calculation units is operated sequentially from J=1 to J=J,
Execute the minimum value detection operation in the recurrence formula processing without contradiction,
It is possible to realize a device that calculates the similarity between two batons.

The present invention has been described above using one embodiment, but this does not limit the present invention. For example, the minimum value of i is made to correspond to the highest rank of n, and as i increases, n is decreased. By doing so, similar recurrence formula processing can be realized.

As is clear from the above description, when calculating time-normalized similarity using the DP matching method, the present invention can process recurrence formulas with a simple circuit configuration, at high speed, and without contradiction. This brings about an extremely effective effect in realizing a pattern similarity calculation device based on the method.

[Brief explanation of the drawing]

FIG. 1 is a diagram for explaining recurrence formula processing in a conventional pattern similarity calculation device. ○FIG. 2 is a configuration diagram showing an embodiment of a pattern similarity calculation device according to the present invention. 2 is a recurrence formula calculation unit, 3 is a similarity calculation unit, 4 is an addition circuit, 5 is a minimum value detection circuit, 6 is a storage circuit, and A( 1), A(2)...
, A(NW) represent storage addresses.

Claims (1)

[Claims] 1 vector sequence a_1, a_2..., a_i,..., a
The distance d(i, j ), and a distance calculation unit that calculates the distance d(
The value g(i, j) of the recurrence formula, which is expressed as the sum of i, j) and is a dynamic programming operation regarding the combination of i and j, is stored for the number of i in a finite interval where j is constant. With only one set of memory circuits, j is constant, the minimum value of i in the finite interval corresponds to the lowest memory address n of the memory circuit, and The value g(i-
1, j) from address (n+1) to the value g(i, j
-1) from address n to the recurrence formula value g(i-1, j-1)
The distance d(i
, j), and the minimum value of them is calculated as g(
i, j) is configured to be able to be stored at address n of the memory addresses, and calculates a recurrence formula for a constant j by sequentially increasing n or i in the finite interval; and the contents of the memory circuit as i, j
and a similarity calculation unit that normalizes by a numerical value determined by and outputs the minimum value thereof, and sequentially executes each calculation unit in the direction of increasing j according to the number of times set by the length J of pattern B. A pattern similarity counting device characterized in that it is operated to calculate the similarity between patterns A and B.