JPS6240754B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to an improvement in a pattern matching device which is a main component of a pattern recognition system for speech, etc. The patterns handled by the pattern matching device according to the present invention are not limited in any way as long as they are expressed as a time series of feature values, but below, we will focus on speech patterns as a particularly representative example. The pattern matching device will be explained. Speech recognition devices, which are devices that automatically recognize voice patterns and convert them into machine codes, have a wide range of applications as highly efficient and easy-to-use data input devices of the new era. Pattern matching is widely used as the most reliable and simplest method for automatically recognizing speech patterns. In this method, a standard pattern (hereinafter referred to as standard pattern) is prepared for each word to be recognized.
When an unknown pattern (hereinafter referred to as an input pattern) is given, this input pattern is determined by comparing it with the standard pattern (i.e., pattern matching) and determining the standard pattern that provides the best match. It is determined that the pattern is the same word as the standard pattern. In this pattern matching method, it is important to select a distance measure for comparing the input pattern and the standard pattern. That is, even when the same word is uttered, the movement of the vocal tract system is not necessarily constant at each time, so the speech pattern undergoes complex deformation. Only by performing pattern matching using a scale that is not easily affected by this deformation can highly accurate speech recognition processing be achieved. The most reliable pattern matching method (or pattern matching device that performs it) that has been published so far is the publication published in 1974, "Acoustical Society of Japan Speech Study Group Material S74. −30
This is described in a paper titled ``Real-time speech recognition system using a minicomputer and DP processor'' (hereinafter referred to as cited document (1)). In this method, an audio signal is processed by being converted into a time series of vectors (hereinafter referred to as feature vectors) representing audio characteristics at each point in time through spectrum analysis and time sampling. In the following, a pattern expressed as a time series of feature vectors in this manner will be referred to as a speech pattern. According to the method described in the above-mentioned cited document (1), it is possible to perform a stable matching operation against nonlinear expansion and contraction of the time axis caused by fluctuations in speaking rate.
As a result, highly accurate recognition results are said to be obtained. However, the method in cited document (1) above mainly assumes that the input pattern and the standard pattern to be compared are time-sampled at a sufficiently short and constant sampling period (for example, about 10 ms). It can be said that it was devised. On the other hand, it is known that the speech patterns obtained by such time sampling are extremely redundant. In other words, for stationary phonemes like vowels, the spectrum is almost constant.
It may continue for more than 100ms. Therefore, if time sampling is performed as described above, the same phoneme will be divided into 10
Points or more are also time sampled. For purposes of speech recognition, it is sufficient to obtain one time sampling point for one phoneme, so such multiple time sampling is redundant. However, in reality, it is difficult to perform time sampling in which only one hour sampling point is selected from one phoneme.
As described in a paper entitled "Real-time word speech recognition system using microprocessor" published in June 1953 (hereinafter referred to as cited document (2)), the steady part fluctuates roughly. A method of densely time-sampling is used for the parts that are According to such time sampling, the number of sample points in the stationary portion is reduced, so that it is possible to obtain a speech pattern with low redundancy as a whole. Hereinafter, such time sampling will be referred to as nonuniform interval sampling. The matching algorithm described in the cited document (1) was devised on the premise that the time axis is evenly sampled. Naturally, in the case of non-uniform time sampling, a matching method suitable for that must be adopted. In the cited document (2), the following matching method is proposed. In other words, two voice patterns A and B are expressed as A=a ₁ , a ₂ , ...a _i , ..., a _I B=b ₁ , b ₂ , ...b _j , ...b _J (1) show. Here, a _i is the spectrum giving the spectral feature at the i-th time sample point t(i) (2) of speech pattern A, and b _j is the spectrum giving the spectral feature at the j-th time sample point τ(j) of speech pattern B. It is a vector indicating the characteristics. In FIG. 1, these two voice patterns A and B are shown expanded on the i-axis and the j-axis, respectively. This i
A point (i, j) on the −j plane indicates a combination of feature vector a _i and feature vector b _j . In the method described in the cited document (1), the distance between a _i and b _j (hereinafter referred to as vector distance) is calculated for each of these points (i, j) as follows: d(i, j) = a _i − I am thinking of b _j (3). From point (1, 1) to point (I, J)
(I=8, J=6 in Figure 1)
Figure reference number 1) (i(1), j(1)), (i(2), j(2)), ... (i(k), j(k)), ..., (i(k) ), j(k)) (4). However, i(1)=1, j(1)=1, i(k)
= I, j(k) = J. By minimizing the sum of distances d (i(k), j(k))) on this point sequence, the time axis fluctuations between these two patterns are corrected, and the distance between both patterns (hereinafter referred to as pattern distance) is call). in particular The pattern distance between voice patterns A and B is defined by . Here, N is called a normalization coefficient and is defined as N=I+J (6). Also, W(k) is a loading coefficient, W(k)=(i(k)-i(k-1))+(j(k)-j(k-
1)) (7) The above equation (5) is calculated by the following dynamic programming operation. Initial condition g (1, 1) = d (1, 1) (8) Recurrence formula Pattern distance D (A, B) = 1/Ng (I, J) (10) The method described in intersection (1) above is, for example,
“IEEE Transactions on Acoustics, Speech;
and Signal Processing, Vol.ASSP−26, No.1,
(February 1978)” in “Dynamic Programming
Algorithm Optimization for spoken word
This method is applied when audio patterns A and B are both time-sampled at a common fixed period, as described on page 44 of the paper entitled "Recognition" (hereinafter referred to as cited document (3)). Therefore, it is inappropriate when targeting speech patterns sampled at irregular intervals, as envisaged in the present invention. A matching algorithm devised to handle unevenly sampled speech patterns is described.According to it,
For each vector a _i, the difference between the time t(i) at which the vector was sampled and the time t(i-1) at which the immediately preceding vector ai-1 was sampled α(i) = t Let (i)−t(i−1) (11) be the weighting factor, and similarly for each vector b _j , let β(j)=τ(j)−τ(j−1) (12) be the weighting factor. Calculate it. And in the matching process, instead of the above equation (9), Perform the recurrence formula operation. Further, in parallel with this calculation, a normalization coefficient N is calculated using the following recurrence formula. Here, it is assumed that the value in brackets [ ] is selected according to which of the three values in brackets [ ] in equation (13) is selected. In equation (13), on the right side (α(i) + β(j))/2
It is said that the purpose of the load is as follows. That is, for example, by multiplying coarsely sampled parts such as vectors a(4) and b(4) in Figure 1 by a large load (α(4)+β(4))/2, The purpose of this is to restore the proportion of the time interval on the original time axis. However, when comparing the two types of point sequence 2 and point sequence 3 shown in Figure 2, it can be seen that there is a serious disadvantage in the use of the loading coefficient described in this cited document (2). . In other words, on the point sequence 2, the weighting coefficient (α(i) + β
(i))/2, N(I, J) = (1+1)/2+(1+2)/2 +(1+2)/2(1+2)/2+(3+2)/
2 + (3 + 2) / 2 + (3 + 1) / 2 + (3 +
2)/2 +(3+2)/2+(1+2)/2+(2+
2)/2 + (1+2)/2=22.5. Doing the same thing on the point sequence 3, N (I, J) = (1 + 1) / 2 + (1 + 1) / 2 + (1 + 1) / 2 + (3 + 1) / 2 + (1 +
1)/2 +(2+1)/2+(1+1)/2+(1+
2)/2 +(1+2)/2+(1+1)/2+(1+
2)/2 + (1+2)/2 = 15.5. These load coefficients are d on the right side of equation (13).
(i, j), so equation (13) becomes g
When the calculation up to (I, J) is completed, the point sequence 2
There is a tendency for the value of g(I, J) to be smaller when passing through point sequence 3 than when passing through . As a result, even though point sequence 2 in FIG. 2 is the optimal point sequence for time axis fluctuation correction, point sequence 3 is selected due to the influence of the above-mentioned loading coefficient, resulting in incorrect time axis correction (i.e., This means that the method in document (2) has the disadvantage that normalization) is performed. In addition, in literature (2), the pattern distance between speech patterns A and B is D (A, B) = g (I, J) / N (I,
J). In order to calculate this normalization coefficient N(I, J), it is necessary to calculate the recurrence formula of equation (14) at each point in the i-j plane in Figure 1, but this requires extra calculations. Is required. SUMMARY OF THE INVENTION An object of the present invention is to provide a pattern matching device that eliminates the above-mentioned drawbacks of conventional devices and can perform accurate time axis normalization with a minimum amount of calculation. The device of _the present invention has an input pattern buffer, a vector b _j
standard pattern storage for holding the standard pattern B expressed as a time series of input pattern A, input pattern weight storage for storing the weight coefficient α(i) for each vector a _i of the input pattern A, and storage for the standard pattern A; B
Standard pattern weighting factor storage for storing the weighting factor β(j) for each vector b _j of , the distance d(i,j) between said vector a _i and said vector b _j
The following three types of values (1) are calculated as the recurrence formula value g(i, j) using time i and j as indexes. The distance d is added to the formula value g(i, j-1)
(i, j) and the product of the weighting coefficient β(j), (2) the recurrence formula value g(i-1, j-1) and the distance d
(i, j) and the sum of the weighting coefficients (α(i)+β(j))
(3) The sum of the products of (3) the recurrence formula value g(i-1, j) and the distance d
It is comprised of a recurrence formula calculation unit having a function of selectively outputting the maximum value of the sum of the products of (i, j) and the weighting coefficient α(i). The above recurrence formula can be written down mathematically as follows. The coefficients loaded by this recurrence formula are as shown in FIG. In other words, when the i-coordinate increases, the weighting coefficient α(i) becomes β(j) on the path where the j-coordinate increases.
However, on the path where both i-coordinates increase (α
(i)+β(j)) are respectively loaded. According to such a load coefficient, the inconvenience that occurred in the case of FIG. 2 in the cited document (2) can be solved. That is,
Regardless of whether point sequence 2 or point sequence 3 in FIG. 2 is selected, the total sum of loads will be a constant value of 20. Generally, the sum of the load factors is becomes. Therefore, the tendency that a specific point sequence is selected due to the influence of the loading coefficient has been eliminated. Also, since the normalization coefficient N is given by equation (16), (14)
There is no need to calculate the recurrence formula many times. Therefore, according to the principles of the present invention, it is possible to realize a simple pattern matching device that has accurate time axis normalization capabilities. The configuration of the present invention will be explained in detail below with reference to the drawings from FIG. 4 onwards. FIG. 4 is a diagram showing an embodiment of the present invention. Before the pattern matching operation described below is started, the input pattern buffer 21 and the standard pattern memory 23 respectively store an input pattern A and a standard pattern B as shown in equation (1), and also store an input pattern weight coefficient. It is assumed that input pattern loading coefficient α(i) and standard pattern loading coefficient β(j) defined by equations (11) and (12) are stored in 22 and standard pattern loading coefficient memory 24, respectively. . First, the reset signal r is set to 1, and the addressing signals i and j are set to i=1, j=1. The working memory 27 receives an address signal i from the control section.
The address is specified two-dimensionally by and j, and the recurrence formula value g
(i, j) is stored.
While the reset signal r is applied as 1, the following initial conditions and settings are executed. That is, vector a ₁ is read from the input pattern buffer 21 and vector b ₁ is read from the standard pattern memory 23 and sent to the distance calculation section 25 . There the vectors a ₁ and b ₁
The distance d(1, 1) is calculated, and the recurrence formula calculation unit 2
Sent to 6. The input pattern weight coefficient α(1) is read from the input pattern weight coefficient memory 22, and the standard pattern weight coefficient β(1) is read from the standard pattern weight coefficient memory and sent to the recurrence formula calculation unit 26.
Based on the above input, the recurrence formula calculation unit 26 stores the initial condition settings as g(1,1)=d(1,1)×(α(1)+β(1))(17) in working memory. It will be held on the 27th. This corresponds to equation (8), but in the case of the present invention, (α(1)+β(1)) is changed to d( 1, 1). The recurrence formula calculation section 26 is configured as shown in FIG. In the initial condition setting operation, standard pattern weight coefficient α(1) and input pattern weight coefficient β(1) are input via signal lines α and β, respectively. The adder circuit 261 calculates the sum (α(1)+β(1)), and sends it to the multiplier circuit 263 as a signal αβ. The multiplication circuit 263 calculates the product of the distance d(1, 1) input via the signal line d and the signal αβ, so that g(1, 1) in equation (17) becomes the signal x ₂ It is calculated as On the other hand, the gate circuit 26
0 is a numerical value of 0 while the reset signal r is set to 1.
Outputs a signal. Therefore, the addition circuit 266
The output y ₂ of is equal to the value of the signal x ₂ g(1, 1)
becomes. The multiplexer 269 receives the reset signal r
While is 1, signal _y2 is selected and output. For this reason,
The output g ₀ of the recurrence formula calculation unit 26 is g in equation (1).
(1, 1) is obtained. This output g ₀ is written to the working memory 27. When the above initial condition setting operation is completed, the reset signal r is reset to 0, and the address designation signals i and j sequentially change in the increasing direction. That is, the signals i and j are arranged so as to cover all the points on the i-j plane in FIG.
= J. In this way, the operations of each part in FIG. 4 that are performed while the address designation signals i and j change are generally expressed as g.
A case where (i, j) is calculated will be explained.
When the address designation signals i and j are designated, the input pattern buffer 21 outputs the vector a _i and the standard pattern memory 23 outputs the vector b _j . The distance calculation unit 25 calculates the distance d(i, j) between these two vectors a _i and b _j and outputs it as a signal d. From the input pattern load memory 22, the load coefficient α(i)
However, from the standard pattern load memory 24, the load coefficient β(j)
is output. Loading coefficients α(i) and β(j) are input to the adder circuit 261 in FIG. 5, and their sum (α(i)+
β(j) is calculated and output as a signal αβ. The multiplier circuit 262 has a load system α(i) and a distance d(i, j).
are input, and their product d(i,j)·β(j) is calculated and output as a signal _x3 . On the other hand, when the address designation signals i and j are given to the buffer memory 27 in FIG.
(i-1, j), g (i-1, j-1) and g
(i, j-1) are output as signals g ₃ , g ₂ and g ₁ , respectively. The adder circuit 265 receives d(i, j) and β(j) as the signal x ₃ and receives g(i-1, j) as the signal g ₃ . Therefore, from this adder circuit, g(i-1, j) is output as signal _y3 .
+d(i,j)·α(i), that is, the value of the third equation in brackets [ ] on the right side of equation (15) is output. Similarly, the output of the multiplication circuit 263 is d(i,j)・(α
(i)+β(j)) and is input to the adder circuit 266 as a signal x ₂ . At this time, since the reset signal r is 0, the gate circuit 260 allows its input g ₂ to pass through as is. Therefore, adder circuit 2
At 66, the signals x ₂ and g ₂ are added, resulting in
The second equation in brackets [ ] on the right side of equation (15), that is, g(i-1, j-1) + d(i, j)・(α(i)
+β(j)) is output as signal _y2 . Similarly, by the functions of the multiplier circuit 264 and the adder circuit 267, the signal y ₁ is converted to the right-hand side of equation (15).
The first equation g(i, j-1) + d(i, j)・β(j)
is calculated. These three signals y ₁ , y ₂ and y ₃
are compared by the comparator 268, and the minimum value among them is output as the signal gm. In this way, the calculation of equation (15) is executed and the recurrence formula value g
(i, j) is calculated as the signal gm. At this time, since the reset signal r is 0, the multiplexer 269 selects the input signal gm, and the signal g ₀
is sent to the working memory 27 in FIG. 4 and stored as the recurrence formula value g(i,j). In the above manner, the recurrence formula value is calculated by i=I,
The process is executed until the final recurrence formula value g(I, J) is calculated with j=J. This recurrence formula value 9(I,
When J) is calculated, a pulse signal e is generated from the control section 20, and the following operations are thereby performed. The input pattern load coefficient memory 22 and the standard pattern load coefficient memory 23 in FIG.

[expression] and

[Formula] are calculated in advance and stored respectively. These weighting coefficient sums δα and δβ are input to the normalization unit 28. The normalization unit 28 adds the weighting coefficient sums δα and δβ to calculate the normalization coefficient N of equation (16). On the other hand, from the recurrence formula calculation unit 26, the signal line g ₀
The recurrence formula value g(I, J) is input via . This value is divided by the normalization coefficient N calculated previously to calculate the pattern distance given by equation (10) and output to the signal line S. In this way, the fourth
The configuration and operation of the pattern matching device have been explained with reference to the figures and FIG. FIG. 6 is a diagram showing the configuration of a further improved recurrence formula calculation section. This figure only shows the vicinity of comparator 268 in FIG. 5. Patent Application No. 2418 of 1972 filed by the same applicant states that if the curve formed by point sequence 1 shown in Fig. 1 is smoothed, it will not be extremely curved as shown in Fig. 2. There is a statement that better results can be obtained compared to when a point sequence is allowed. FIG. 6 is constructed taking this point into consideration. The fine P ₁ is added by the addition circuit 2681 to the signal y ₁ , that is, the first equation in brackets [ ] on the right side of equation (15), and to the signal y ₂ , that is, the third equation in brackets [ ] above. The fine P ₃ is added by the addition circuit 2683. As a result, the values of signals y ₁ and y ₃ tend to be larger than y ₂ . Therefore, the probability that the comparison circuit 268 selects the signal y ₂ as the minimum value increases. This means that the second equation in brackets [ ] on the right side of equation (15) is selected, and indicates that the point sequence 1 shown in FIG. 1 tends to be smoothed. In order to simplify the configuration, a configuration in which a constant P ₂ is subtracted from the signal y ₂ by a subtracter 2682 as shown in FIG. 7 may be used, but a substantially equivalent effect can be obtained. Furthermore, the same effect can be obtained by multiplying by a constant coefficient instead of adding and subtracting. As mentioned above, although the present invention has been explained using Examples, these descriptions do not limit the scope of the present invention. In particular, in Fig. 5, addition functions, multiplication functions, etc. are realized in a space-divided manner.
It is also possible to configure it in a time-division manner. Furthermore, the definition of the load coefficient is not limited to that defined in the cited document (2) (corresponding to equations (11) and (12) in this specification). For example, it is written in the paper titled "Variable frame speech analysis and synthesis method using optimal rectangular wave approximation" on page 385 of the Proceedings of the Acoustical Society of Japan (published in May 1978). When selecting and using a representative vector from a speech pattern as shown in FIG. Furthermore, since the above explanation is given based on the short distance measure, equations (15) etc. are minimization problems. On the other hand, when using a quantity such as a correlation value whose magnitude relationship is opposite to the distance, maximization processing may be performed instead of minimization processing such as equation (15).

[Brief explanation of the drawing]

Figures 1 to 3 are diagrams for explaining the principle of the present invention, Figure 4 is a diagram showing an embodiment of the present invention, and Figure 5 is a diagram showing a recurrence formula calculation unit used in the embodiment of the present invention. 6 and 7 are diagrams showing further improved examples of the recurrence formula calculation section. 4 to 7, 21 is an input pattern buffer, 22
23 is an input pattern weight coefficient memory, 23 is a standard pattern memory, 24 is a standard pattern weight coefficient memory, 25 is a distance calculation unit, 26 is a recurrence formula calculation unit, 27 is a working memory, 28 is a normalization unit, 20 is a control unit Part, 26
0 is a gate circuit, 262, 263, 264 are multiplication circuits, 261, 265, 266, 267 are addition circuits, 268 is a comparator, 269 is a multiplexer,
2681 and 2683 are addition circuits, and 2682 is a subtraction circuit.

Claims (1)

[Claims] 1. Input pattern buffer for holding input pattern A expressed as a time series of vectors a _i sampled at irregular intervals, expressed as a time series of vectors b _j sampled at uneven intervals. standard pattern memory for holding standard pattern B;
Input pattern weight coefficient storage for storing a group of weight coefficients α( _i ) corresponding to the time interval length represented by a _i for each vector a i of the previous input pattern A, and each vector b of the standard pattern B. Standard pattern weighting coefficient storage for storing a group of weighting coefficients β(j ₎ corresponding to the time interval length represented by b _j for _j , the distance _d (i, j) for any combination of time i and j, and the following three types of values (1 ) The distance d is added to the recurrence formula value g(i, j-1).
The value obtained by adding the product of (i, j) and the weighting coefficient β(j), (2) the recurrence formula value g(i-1, j-1) and the distance d
(i, j) and the sum of the weighting coefficients (α(i)+β(j))
(3) The value obtained by adding the product of (3) the recurrence formula value g(i-1, j) to the distance d
A recurrence formula calculator having a function of selecting and outputting the minimum value of (i, j) and the product of the weighting coefficient α(i), coefficient group α
1. A pattern matching device comprising: a normalization section for calculating an inter-pattern distance D (A, B) by dividing (i) by the sum of β(j).