JPH0566600B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to a pattern comparison device that compares a pattern of speech or the like with a standard pattern and determines the distance or similarity between the patterns. Configuration of conventional examples and their problems Similar to the normalization of the time axis in speech recognition using pattern matching, series of feature vectors with different lengths are compared by normalizing the length of the series, and the similarity between the two is compared. It is already known that in pattern comparison devices that calculate degree or dissimilarity (distance), it is most common to use dynamic programming for this purpose, and the best results are obtained. be. That is, the i-th feature vector of input pattern A=a→ ₁ , a→ ₂ , ..., a→ _I is a _i , and the standard pattern R ⁿ = b→
ⁿ ₁ ,b→ ⁿ ₂ ...b→ ⁿ The i-th feature vector of _Jo is b→ ⁿ _j
year,
When the distance between both vectors is d ⁿ (i, j),
The distance D (A, R ⁿ ) between A and R ⁿ can be found, for example, by solving the following recurrence formula. g ⁿ (i, j) = ming ⁿ (i-2, j-1) + d ⁿ (i-
1, j) + d ⁿ (i, j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1, j-2) + d ⁿ (i, j) ...( 1) Initial value g ⁿ (1, 1) = d ⁿ (1, 1) D (A, R ⁿ ) = g ⁿ (I, J ⁿ ) Figures 1 and 2 explain this formula graphically. It is something to do. That is, input pattern A and standard pattern
The distance R ⁿ is determined by the tolerance of the predetermined constraint condition for path 1, which represents the correspondence between the feature vectors constituting both series, in a grid graph with i as the horizontal axis and j as the vertical axis, as shown in Figure 1. d ⁿ (i, j) along the path
Find the minimum weighted average of D
(A, R ⁿ ). The constraint conditions for route selection corresponding to equation (1) are shown in FIG. 2a.
In other words, the path leading to point (i, j) is point (i-2,
j-1) → point (i-1, j) → point (i, j), or
Point (i-1, j-1) → point (i, j) or point (i
−1, j−2)→point (i, j), and the path that minimizes g ⁿ (i, j) is selected.
In the figure, the numerical value attached to the route is the weighting system when that route is selected, and is 1 in this example. Various other constraints on route selection can be considered, and FIG. 2 shows typical ones. Figure 2 a to e are so-called asymmetric paths, and the sum of the weights of the paths a to c is equal to the input pattern length (the number of feature vectors of the input pattern).
d and e are equal to the standard pattern length (the number of feature vectors of the standard pattern). Further, f is a so-called symmetrical path, and the sum of the weights of the path is the sum of the input pattern length and the standard pattern length. The symmetrical path of f is often used in isolated word speech recognition. a
The asymmetric path of ~c is used for continuous word speech recognition,
The d and e asymmetric paths are used in word spotting and continuous word speech recognition. Of course, if the constraint conditions for this path change, the form of the recurrence formula of equation (1) will change accordingly. The recurrence formulas corresponding to FIG. 2 b to f are as follows. (b) g ⁿ (i, j) = ming ⁿ (i-2, j-1) + d ⁿ (i-
1, j) + d ⁿ (i, j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1, j-2) + d ⁿ (i, j-1) ( c) g ⁿ (i, j) = ming ⁿ (i-1, j) + d ⁿ (i, j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1 , j-2) + d ⁿ (i, j) (d) g ⁿ (i, j) = ming ⁿ (i-2, j-1) + d ⁿ (i,
j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1, j-2) + d ⁿ (i, j-1) + d ⁿ (i, j
) (e) g ⁿ (i, j) = ming ⁿ (i-2, j-1) + d ⁿ (i-
1, j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1, j-2 )+d ⁿ (i, j-1)+d ⁿ (i, j
) (f) g ⁿ (i, j) = ming ⁿ (i-2, j-1) + 2d ⁿ (i-
1, j) + d ⁿ (i, j) g ⁿ (i-1, j-1) + 2d ⁿ (i, j) g ⁿ (i-1, j-1) + 2d ⁿ (i, j) g ⁿ ( i-1, j-2)+2d ⁿ (i, j-1)+d ⁿ (i,
j) For a to c, the sum of the weights of the paths is constant regardless of the standard pattern, so D(A, R ⁿ )=g(I, J ⁿ ), and d and e can be set as D(A, R ⁿ )=g(I,
J ⁿ )/J ⁿ , f is D(A, J ⁿ )=g(I, J ⁿ )/(I
+J ⁿ ). The lines a, b, d, e, and f in FIG. 2 are so-called inclination restrictions, and in this example, the selected route has an inclination of 1/2 or more and 2 or less. Therefore, in the case of Fig. 1, if the starting end vectors and ending vectors of the input pattern and the standard pattern are always made to correspond, the selected path will be straight lines 2, 3, 4, 5.
limited to the area enclosed by. Also, Figure 2c
In the case of the constraint condition, the selected route is the area surrounded by straight lines 4, 5, 6, and 7 based on a similar idea. FIG. 3 explains how the constraint conditions for route selection result in differences during pattern matching. That is, if the length of the input pattern is considerably longer than that of the standard pattern, matching paths cannot exist in Figure 2 a, b, d, e, and f, but in Figure 2 c, there is no matching path. In the above example, there may be 8 paths, but path c has a higher degree of freedom in matching, and it becomes possible to make a rather unreasonable correspondence between the input pattern and the standard pattern. For this reason, better results have been obtained with slope-limited types such as a and b. However, as is clear from Fig. 2, when using slope-limited constraint conditions, it is difficult to find g ⁿ (i, j) for j = 1, 2, ..., J ⁿ for a→i. is g ^{n (} i-1,
j), g ⁿ (i-2, j), d ⁿ (i-1, j), and in particular, each time a new input feature vector a→ _i arrives, j = 1, 2 ,...,J ⁿ ;n=
Find g ⁿ (i, j) for 1, 2,...,N, and a→ _I
Immediately after input g ⁿ for n = 1, 2, ..., N
When performing so-called real-time processing in which all the results of (I, J ⁿ ) are obtained, the intermediate results are n=1,
Since all of 2,...,N must be stored, the amount becomes quite large. For example, to recognize 1000 words of speech with an average number of feature vectors of 50, the gradient-limited method requires 150K words of memory. In the case of continuous word recognition, 100K words of memory are required for the back pointer, resulting in a total of 250K words. In addition, in the recognition of monosyllabic speech, the time axis expansion and contraction of the vowel part is large, but the consonant part does not expand and contract so much. It is considered desirable to perform matching with a higher degree of freedom in order to improve recognition accuracy, but conventionally, the constraint conditions for matching have been uniform over the entire range. OBJECTS OF THE INVENTION The present invention aims to reduce the amount of memory for storing intermediate results of recurrence formula calculations and improve recognition accuracy in a pattern comparison device using dynamic programming. Configuration of the Invention The present invention converts an input signal into a sequence of feature vectors a→ ₁ ,
A standard ^{pattern B n} _{( where n} ⁼ _{1 ,} 2,...,N), and a pattern distance between the input pattern and the standard pattern R ⁿ ,
Feature vector a→ ₁ , which constitutes the input pattern
Minimize by dynamic programming as a function consisting of a→ ₂ ,..., a→ _I and feature vectors b→ ⁿ ₁ , b→ ⁿ ₂ ,..., b→ ⁿ _Jo that constitute the standard pattern R ⁿ The minimizing means is characterized in that the recurrence formula of the dynamic programming method is made variable in accordance with the number of feature vectors of the input pattern, the standard pattern, or both. Description of the Embodiment In order to introduce the effect of slope restriction on the matching path, it is sufficient to prevent the vector b→ ⁿ _j of the standard pattern from corresponding to more than a certain number of vectors of the input pattern. In the example shown in FIG. 2, c is not subject to such restrictions, but if path 9 is added as in a, the effect of restricting the inclination will be produced. However, as mentioned above, the amount of storage required also increases. FIG. 4 is a diagram illustrating the principle of the present invention that compensates for this drawback. That is, the slope restriction can be realized by changing the constraint condition of the matching path for each input pattern a→ _i . Figure a, c, e
It is only necessary to alternately switch the constraint conditions for path selection of and those of b, d, and e for each i of the feature vector a→ _i of the input pattern. For example, if i is an even number, a, c, e, if i is an odd number, b,
d, f, etc. Figure 4 a and b are when the sum of weights of the matching paths is equal to the input pattern length, c and d are when the sum of weights of the matching paths is equal to the standard pattern length, and e and f are when the sum of weights of the matching paths is input. This is the case when the pattern length is the sum of the standard pattern length.
The recurrence formulas corresponding to each are changed depending on whether i is odd or even, and become as follows. In the case of a combination of a and b, when i is an odd (even) number, g ⁿ (i, j) = ming ⁿ (i-1, j) g ⁿ (i-1, j-1) g ⁿ (i- 1, j-2) + d ⁿ (i, j) When i is even (odd) g ⁿ (i, j) = ming ⁿ (i-1, j-1) g ⁿ (i-1, j- 2) +d ⁿ (i, j) For the combination of c, d When i is an odd (even) number g ⁿ (i, j) = ming ⁿ (i-1, j) g ⁿ (i-1, j -1) +d ⁿ (i, j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1, j-2) + d ⁿ (i, j-1) + d ⁿ (i, j
) If i is an even (odd) number, g ⁿ (i, j) = ming ⁿ (i-1, j-1) g ⁿ (i, j) = ming ⁿ (i-1, j-1) g ⁿ (i-1, j-2)+d ⁿ (i, j-1)+d ⁿ (i, j
) For combinations of e and f When i is an odd (even) number g ⁿ (i, j) = ming ⁿ (i-1, j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1, j-1) + d ⁿ (i, j) g ⁿ (i-1, j-2) + 2d ⁿ (i, j-1) + d ⁿ (i,
j) When i is even (odd) g ⁿ (i, j) = ming ⁿ (i-1, j-1) + d ⁿ (i,
j) g ⁿ (i, j) = ming ⁿ (i-1, j-1) + d ⁿ (i,
j) g ⁿ (i-1, j-2) + 2d ⁿ (i, j-1) + d ⁿ (i,
j) In this case, in the case of isolated word speech recognition, the cumulative distance g ⁿ (i, j) is j=1, 2,
..., for J ^n, it is only necessary to remember g ⁿ (i-1, j), and there is no need to remember d ⁿ (i, j), so
The required storage capacity for intermediate results is 50K words, which is 1/3 of that of the prior art example of the slope-limited type. In addition, in the case of continuous word recognition, it is 100K words, which is 1/1/2 of the conventional example.
It becomes 2.5. In this example, the recurrence formula is switched depending on whether i is odd or even, but the present invention is not limited to this. That is, for the combination of a and b, a is set to 2.
The present invention also includes alternating application of 1 time and 1 time of b. In addition, the constraint conditions for the route are not limited to this example, and it goes without saying that various conditions are possible. FIG. 5 shows an example where a is applied when i is an odd number and b is applied when an even number, and the solid line shows the selectable routes, and the effect of the slope restriction is clear. FIG. 6 shows an embodiment of the present invention in which the constraint conditions shown in FIGS. 4a and 4b are switched for odd and even i. 10 is an input terminal for input patterns. 1
Reference numeral 1 denotes an input buffer for temporarily storing input patterns. 12 is a standard pattern storage section that stores standard patterns. Reference numeral 13 denotes an inter-vector distance calculation unit that calculates the inter-vector distance between the input pattern feature vector read from the input buffer 11 and the standard pattern feature vector read from the standard pattern storage unit 12. Reference numeral 14 is a cumulative distance storage unit in which intermediate results g ⁿ (i
-1, j) as j=1,2,...,J ⁿ ;n=1,2,
..., N is memorized. 15 is recurrence formula calculation unit 1
Then, recurrence formula 2 is calculated. Reference numeral 16 denotes a recurrence formula calculation unit 2, which calculates recurrence formula 3. Reference numeral 17 is a selection gate that selects the result of recurrence formula calculation unit 1 or the result of recurrence formula calculation unit 2 as the value of the dynamic programming recurrence formula, depending on whether i is an odd number or an even number. . The obtained results are stored again in the cumulative distance storage unit 14 in preparation for the next calculation. At this time, if the calculation of the recurrence formula is performed in the order of j=J ⁿ , J ⁿ -1, ..., 2, 1, the g ⁿ (i, j) used in the calculation of g ⁿ (i, j)
j) will not be used again, so the obtained g ⁿ
(i,j) can be stored in the location where g ⁿ (i-1,j) was stored. Therefore, if this is done, the amount of memory required to store the intermediate cumulative distance g ⁿ (i, j) can be the average JN, where J is the average of J ⁿ over n. Reference numeral 18 denotes an even/odd determining section, which determines whether i is an even number or an odd number. Reference numeral 19 denotes an n counter, which sequentially specifies the address of each standard pattern stored in the standard pattern storage section.
20 is a j counter, which sequentially specifies the address of the j-th feature vector b→ ⁿ _j of the standard pattern n stored in the standard pattern storage unit 12 from J ⁿ to 1 for each combination of i and each n. It is something to do.
Reference numeral 21 denotes an i counter, which specifies an address for a→ _i for writing and reading an input pattern into the input buffer 11. 19-21
Each counter is reset before the voice is input, and the n counter 19 is reset when the count value of the i counter is 1.
The j counter is reset each time the count value of the n counter increases by 1, and the initial value J ⁿ is set, and the count value decreases by 1. Therefore, the standard pattern storage unit 12 also stores J ⁿ for each n. In the embodiments described above, the constraint conditions for the paths shown in FIG. 4 are alternately switched with respect to i, but generally they do not need to be alternate.
Further, the shape of the path is not limited to a and b, and the shape and type are not limited to two types. Further, in this embodiment, the recurrence formula to be applied with respect to i is switched, but it is of course possible to perform this with respect to j or with respect to both i and j. In this example, the purpose of the explanation was to reduce the amount of memory required, but when used for pattern recognition,
This idea of having multiple types of recurrence formulas can also be used for the purpose of increasing recognition accuracy. In other words, in the case of recognition of monosyllabic speech, matching of the consonant part at the beginning of a word has a small expansion/contraction of the time axis, so unreasonable matching is avoided by using slope restrictions, and for vowel parts, the expansion/contraction of the time axis is large, so matching in the i-axis direction is For example, matching is performed to increase the degree of freedom.
As an example, in this case, the recurrence formula corresponding to Figure 2 a is applied to the consonant part number frame at the beginning of the word, and the recurrence formula corresponding to Figure 2 c is applied to the vowel part, etc. It is. Furthermore, in order to increase recognition accuracy while reducing the amount of memory required, apply the combination of Figure 4 a and b to the consonant part, and apply only Figure 4 a to the vowel part, or apply the combination of Figure 4 a to the vowel part. It is effective to increase the number of circuits from b. Effects of the invention In a pattern comparison device using dynamic programming,
By having multiple types of recurrence formulas to be calculated and appropriately switching between them, it is possible to reduce the amount of storage required for intermediate results of recurrence formula calculations and improve recognition accuracy. Table 1 shows the results when the present invention was applied to continuous digit speech recognition and continuous syllable speech recognition. As a result, it can be seen that the recognition accuracy is equivalent to or higher than that of the conventional method. 【table】

[Brief explanation of drawings]

Figures 1 and 2 are schematic diagrams for explaining pattern matching using dynamic programming, Figure 3 is a schematic diagram for explaining the conventional example, and Figures 4 and 5 are the principles of the present invention. FIG. 6 is a block diagram illustrating a pattern comparison device according to an embodiment of the present invention. 11...Input buffer, 12...Standard pattern storage section, 13...Vector distance calculation section, 14...
... Cumulative distance storage unit, 15... Recurrence formula calculation unit 1, 1
6... Recurrence formula calculation unit 2, 17... Selection gate, 1
8...Even number, odd number determination unit, 19...n counter,
20...j counter, 21...i counter.

Claims (1)

[Claims] 1 The input signal is converted into a sequence of feature vectors a→ ₁ , a→ ₂ ,
..., a→ _I , and a standard pattern B ⁿ consisting of a series of feature vectors → b ⁿ ₁ , b→ ⁿ ₂ ,..., b→ ⁿ _Jo (where n=1, 2,..., N), and a standard pattern storage means for storing the distance between the input pattern and the standard pattern R ⁿ as feature vectors a→ ₁ , a→ that constitute the input pattern.
₂ ,..., a→ _I and the feature vectors b→ ⁿ ₁ , b→ ⁿ ₂ ,..., b→ ⁿ _Jo constituting the standard pattern R ⁿ as a function to be minimized by dynamic programming. 2. A pattern comparison device, characterized in that said minimization means makes the recurrence formula of said dynamic programming variable in accordance with the number of feature vectors of an input pattern, a standard pattern, or both.