JPH0420197B2 - - Google Patents

Description

[Detailed description of the invention]

(1) Description of the field to which the invention pertains The present invention relates to a sequence pattern matching processing method, particularly a pattern recognition device which is a main component of a pattern recognition device using sequence matching of, for example, speech.
The present invention relates to a matching processing method. (2) Description of the prior art The sequence that can be handled by the sequence pattern matching processing method according to the present invention may be any sequence data as long as it is sequence data, but below, as an example of a typical sequence, a sequence that targets a time series of audio will be used. The pattern matching method will be explained. Speech is the easiest means of information transmission for humans, and with the practical application of speech recognition devices,
It has applications in many fields such as voice data entry, interaction with machines, and voice dialing. Matching using dynamic programming in speech recognition (hereinafter abbreviated as DP matching) uses the time series of input speech = a ₁ a ₂ ...a _o and the time series of standard pattern feature vectors = b ₁ b ₂ ...b _n Allows expansion and contraction of the time axis, correlates elements, and is used when calculating the distance between series. Conventionally, in this type of dynamic programming, the distance matrix between the elements of the series 〓, 〓 = (d _ij ) (d _ij is a _i and b _j
(distance of The disadvantage is that it requires a large amount of calculation due to the restriction (slope restriction) 12 to prevent mismatching, and the storage of sequentially calculated values g (i, j) as shown in FIG. 1B during DP matching. Therefore, it has the disadvantage that the buffer memory 13 becomes large. That is, in the conventional method, (1) a restriction regarding the slope of the bus is given, for example, as indicated by the dotted line in FIG. 1A, and all possible buses within the range are searched. In other words, at all grid points within the dotted lines in Figure 1A,
(2) However, as will be explained later, it is necessary to give greater weight to diagonal buses than to vertical and horizontal buses. In other words, there is a problem that fairness is not maintained when comparing buses. (3) Purpose of the present invention The present invention is intended to largely eliminate the above-mentioned drawbacks, and because the repeated calculations of the sequential calculation of DP matching are performed only at every three grid points, the number of repeated calculations is reduced to 1. /3 and 1 for slope restriction
It has the characteristics that the amount of calculation for each batch of sequential calculations can be reduced to 1/2 or less, and that the buffer memory for storing g(i, j) is only required to be twice the window limit width. There is. Therefore, the conventional
DP matching (for example, the DP shown in Proceedings of the Autumn Conference of the Acoustical Society of Japan, October 1980, 1-1-10)
The amount of calculation can be reduced to less than 1/6 compared to (matching). In other words, while simplification is achieved in the sense of thinning out bus calculations, bus comparisons are performed more strictly (providing equality) than in the conventional case. (4) Description of structure and operation of the invention FIG. 2 shows an embodiment of the present invention, in which 1 is an input voice, 2 is a feature parameter extraction unit, and 3 is a time series of feature parameters of the input voice = a ₁ a ₂ … a _o , 4 is the time series of the feature parameters of the standard pattern stored in advance = b ₁ b ₂ … b _n , 5 is the time series of the input voice = a ₁ a ₂ … a _o and the standard A distance calculation unit that calculates a distance matrix = (d _ij ) between the time series of characteristic parameters of the pattern = b ₁ b ₂ ...b _n , 6 is a distance matrix, 7 is a DP matching unit according to the present invention, 8 is a matching score, 9 is a word determination unit that determines the word with the minimum score, and 10 is a word name. Dynamic programming involves tracing the grid point (i, j) from the starting point (1, 1) to the ending point (n, m) on a distance matrix = (d _ij ) as shown in Figure 1. Then,
The purpose is to obtain the score when the sum of the distances d _ij becomes the minimum, and is expressed, for example, as in the following equation.

【table 1)
{However, {(i, j)} is (i ₁ , j ₁ ) (i ₂ , j ₂ )...
It represents a sequence of (n, m), |i _k+1 −i _k |+|j _k+1 −j _k |=1 (2), and the path that gives the minimum value is called the optimal path. } Expressed as a continuous system, this is the distance function d(x,y)
This is an approximate solution to the above problem of finding the smallest integral value from the point (0,0) to the point (n,m).

[Table] {where c is a monotonically increasing integral path from (0, 0) to (n, m). } The following constraints are usually attached to the optimal path on the distance matrix. () How to follow a path Usually, the path (1, ₁ ) (i ₁ , j 1 ) (i ₂ , j ₂ )...
For (n, m), as in equation (2), a path is selected such that the urbanization distance is 1, or max{|i _k+1 −i _k |, |j _k+1 −j A path is selected such that _k |}=1 (4). Therefore, the path progressing on the grid points is a path 14 as indicated by the arrow in FIG. If the length of the vertical and horizontal paths is "1", the length of the diagonal path is "2". The actual length of the diagonal is √2 if the vertical or horizontal length is ``1'', which results in a significant difference from the continuous system in equation (3). () Slope restriction In order to prevent extremely uneven matching, a path 15 with a slope restriction as shown in FIG. 4 is used. Although this slope-limited path contributes to improving recognition performance, it increases the amount of calculation. The present invention relates to a means for reducing the inconsistency between the lengths of the vertical and horizontal paths of () and the lengths of diagonal paths in DP matching, and for realizing the slope restriction of () without increasing the amount of calculation. It is. This will be explained in detail below. In order to naturally realize the slope restriction on the distance matrix, consider grid points 16 that are shifted every three points as shown in FIG. Then, as shown in Figure 6, the shifted lattice points can be connected by diamond-shaped paths, and all paths have the same length. Therefore, the inconsistency in the path length of () is alleviated. Furthermore, the slope restriction of the path () can be naturally introduced as shown in FIG. Moreover, the repeated and sequential calculations for DP matching only need to be performed every three points, which is one-third the number of steps compared to conventional methods. Furthermore, the buffer memory 13 for storing the sequentially calculated values g(i,j) can also be reduced. In other words, the iterative and sequential calculation of DP matching is performed as shown in Figure 7, i+j=3l
On the grid point (i, j) that satisfies +2, l=0, 1,
2,..., the buffer memory g as shown in Fig. 7 is twice the number of lattice points (r) in each stage.
It is sufficient to prepare (-r) to g(r). The iterative and sequential calculations at each grid point (i, j) will be shown below. However, the buffer memory for sequentially calculated values corresponding to the grid point (i, j) is assumed to be g(p). (Method) g(p)=min{g(p-1), g(p+1)}+d _ij
(5) This converts the path in Figure 6 to the terminal point (i, j).
This means that d _ij is used instead. In order to get closer to the integral value of equation (3), distance values of other points near the path can also be used, and the following method can be considered.

[Table] In equations (5) and (6), the value of p is determined by p=ji−i. Compared to the DP matching formula shown in Figure 1, the calculation formula for this method has a calculation amount of 1/1 per stage.
4 or less, and the overall DP matching is less than 1/12. Compared to the DP matching formula shown in FIG. 1, the method requires less than 1/2 the amount of calculation per stage, and the total amount of calculation is less than 1/6. In order to investigate the effectiveness of DP matching of the methods described above, we used the conventional DP matching shown in Figure 1.
We compared the processing time and recognition performance with matching (referred to as the conventional method). The recognition target was audio data of 641 city name words uttered twice by four men. As a method for word recognition, October 1980, Acoustical Society of Japan Autumn Presentation Proceedings 1-1-17
We used the SPLiT method shown in . In the SPLiT method, most of the computational effort is spent on the DP matching section. First, we will compare processing times. in the traditional way
Recognition experiment of 641 words x 64 words using minicomputer PE3240
If I went there, it would have taken about 8 hours. Under the same conditions, the test time was about 60 minutes, and the test time was about 70 minutes.
It can be seen that the total amount of calculation for the SPLiT method is approximately 1/8. Next, we evaluated the method and its recognition performance using voice data from four speakers. With the conventional method, an average recognition rate of 96.3% was obtained for four people. By method, 94.7%; By method, 95.6%
The recognition rate was obtained. The method has almost the same performance as the method. Although the recognition performance was slightly lower than the conventional method, it was confirmed that a considerably high recognition rate could be obtained. In the above explanation, the DP matching method has been described based on the distance between elements, but it can be similarly formulated for the similarity between elements. Furthermore, in the present invention, it has been described that the repeated sequential calculation of DP matching is performed at every three points, that is, only at the point (i, j) above i+j=3l+2. (However, Q
=5, 7, 9, . . . ), the amount of calculation is further reduced, and it is possible to perform repeated and sequential calculations with strong slope restrictions. (5) Explanation of effects As described above, according to the present invention, the conventional
Compared to DP matching, DP matching can be performed with less than 1/6 to 1/12 of the amount of calculation while maintaining processing rigor, and it also achieves relatively high recognition performance. be able to. Furthermore, it is possible to simplify the word speech recognition device using DP matching. Furthermore, it goes without saying that the present invention can also be used for nonlinear expansion/contraction matching of series in other fields.

[Brief explanation of drawings]

Figure 1 shows an example of conventional DP matching and a distance matrix, Figure 2 shows an example of a word speech recognition system, and Figure 3 shows vertical, horizontal, and diagonal paths in DP matching. An explanatory diagram, FIG. 4 is an explanatory diagram showing a typical slope restriction path, and FIG. 5 is an explanatory diagram showing grid points on a distance matrix shifted every third point considered in the present invention.
FIG. 6 is an explanatory diagram showing paths of DP matching that are equal in length and have slope restrictions, as considered in the present invention. FIG. 7 is an explanatory diagram showing a buffer memory for storing sequentially calculated values of DP matching in the present invention. An explanatory diagram is shown. In the figure, 2 is a feature parameter extraction section, 4 is a standard pattern, 5 is a distance calculation section, 7 is a DP matching section,
Reference numeral 9 represents a word determination unit, 13 represents a buffer memory (or buffer memory storage range), and 17 represents a path.

Claims (1)

[Claims] 1. Sequence of two feature parameters = a ₁ , a ₂ ,
..., a _o and 〓 = b ₁ , b ₂ , ..., b _n In the sequence pattern matching processing method that calculates the distance between the sequences by nonlinear normalized matching using dynamic programming, the distance between the elements of the sequence is Distance matrix = (d _ij ) (where, i means the i-th element a _i of the sequence 〓, j means the j-th element b _j of the sequence 〓, d _ij means the element a _i and the element b i+ _j =Q・l+
c (however, Q is 3, c is a positive integer constant), and calculates the distance for the extracted point. For coordinates (i, j), j-i=p coordinate (i −1, j−2), (j−2)−
(i-1)=j-i-1=p-1 For the coordinates (i-2, j-1), (j-1)-
(i-2)=j-i+1=p+1, and in calculating the distance, i+j=
Coordinates (i-1, j-
2) g'(p-1) and i+j=Q・(l-
1) Using g(p+1) on the coordinates (i-2, j-1) that satisfy +c, repeat successively g(p)=min{g(p-1), g(p+1)}+d _ij By sequentially performing calculations in the order of l = 0, 1, 2, ..., the inter-sequence distance S (〓:
A series pattern characterized by calculating 〓)
Matching processing method. 2 Sequence of two feature parameters = a ₁ , a ₂ ,
..., a _o and 〓 = b ₁ , b ₂ , ..., b _n In the sequence pattern matching processing method that calculates the distance between the sequences by nonlinear normalized matching using dynamic programming, Distance matrix between elements = (d _ij )
(However, i means the i-th element a _i of the series 〓,
j means the jth element b _j of the series 〓, and d _ij is the element
i+j=Q・representing the distance between a _i and element b _j )
Extract the points corresponding to l+c (where Q is 3 and c is a positive integer constant), and calculate the distance for the extracted points. For coordinates (i, j), j-i=p coordinates (i −1, j−2), (j−2)−
(i-1)=j-i-1=p-1 For the coordinates (i-2, j-1), (j-1)-
(i-2)=j-i+1=p+1, and in calculating the distance, i+j=
Coordinates (i-1, j-
2) Above g(p-1) and i+j=Q・(l-
1) Using g(p+1) on the coordinates (i-2, j-1) that satisfy +c, g(p)=min{g(p-1)+d _i,j-1 , g(p+1) }+d _i-1,j }+d _i-1,j-1 is sequentially performed in the order of l=0, 1, 2,..., and the inter-sequence distance S(〓:
A series pattern characterized by calculating 〓)
Matching processing method. 3 Sequence of two feature parameters = a ₁ , a ₂ ,
..., a _o and 〓 = b ₁ , b ₂ , ..., b _n In the sequence pattern matching processing method that calculates the distance between the sequences by nonlinear normalized matching using dynamic programming, the distance between the elements of the sequence is Distance matrix = (d _ij ) (where i means the i-th element a _i of the sequence 〓, j means the j-th element b _j of the sequence 〓, and d _ij means the element a _i and the element b represents the distance from _j ) above i+j=Q・l+
c (however, Q is 3, c is a positive integer constant), and calculates the distance for the extracted point. For coordinates (i, j), j-i=p coordinate (i −1, j−2), (j−2)−
(i-1)=j-i-1=p-1 For the coordinates (i-2, j-1), (j-1)-
(i-2)=j-i+1=p+1, and in calculating the distance, i+j=
Coordinates (i-1, j-
2) Above g(p-1) and i+j=Q・(l-
1) Using g(p+1) on the coordinates (i-2, j-1) that satisfy +c, g(p)=min{g(p-1)+d _i,j-1 , g(p+1) }+d _i-1,j }+d _ij is sequentially performed in the order of l=0, 1, 2,..., and the inter-sequence distance S(〓:
A series pattern characterized by calculating 〓)
Matching processing method.