JPH067354B2 - Pattern comparison device - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a pattern comparison apparatus that compares a plurality of types of standard patterns represented by a series of feature vectors with an input pattern and identifies the input pattern, The present invention relates to a pattern comparison device that can be applied to, for example, recognition of continuously spoken word sounds.

Configuration of the conventional example and its problems If the voice, which is the most natural information generating means for human beings, can be used as the inputting means of the human-machine system, the effect is very large. In that case, it is desirable that the voice recognition device be capable of recognizing continuously uttered voices as a condition for recognizing a more natural voice.

As a pattern comparison device effective for recognizing continuously spoken word voices, a pattern comparison device using a so-called two-stage DP method in which a dynamic programming method (hereinafter referred to as DP) is used twice has already been put into practical use. .

However, this two-stage DP method has many duplicated calculations and enormous amount of calculation. Therefore, the pattern comparison apparatus capable of real-time processing using this method requires extremely high-speed processing, and the apparatus becomes complicated and expensive. There is no choice but to become something like that.

In order to eliminate the above drawbacks, a pattern comparison apparatus using the O (n) DP method, the CWDP method or the like has been proposed as a pattern comparison apparatus which requires a significantly small amount of calculation. However, in order to implement these methods by hardware, there is a drawback that a large-capacity memory that can be accessed at high speed is required.

The present invention provides a pattern matching device that eliminates these drawbacks. This will be described by taking the O (n) DP method as an example. Prior to describing the present invention, the O (n) DP will be described next.
The method will be described first.

The pattern comparison apparatus of the present invention can be used for recognizing various input patterns, but the continuous word utterances that are uttered continuously will be described below as an example.

A voice uttered by a human changes temporally and temporally, and is expanded / contracted nonlinearly with respect to a standard pattern serving as a reference. In order to recognize the input voice by comparing the non-linearly stretched input pattern with the standard pattern, the feature vectors of the input pattern and the standard pattern are associated in a non-linear manner, and the standard pattern We need to calculate which is most similar to. However, although this input voice expands and contracts non-linearly, it does not grow or shrink abnormally long.

Paying attention to such physical characteristics of the input pattern, when comparing the input pattern and the standard pattern, it is considered that the validity is determined by the physical properties of the input pattern, rather than unlimited comparison of all possibilities. Be sure to make a comparison for the range.

The input voicing signal is converted into a series of several numerical value groups (feature vectors) by frequency analysis, LPC analysis, PARCOR analysis, correlation analysis, etc. in the pattern comparison device, and is compared with the feature vector of this input pattern. The feature vector of the standard pattern is compared for each vector. The comparison value for each vector, that is, the cumulative distance obtained by summing the distances between the vectors is used as a measure of pattern similarity. When this cumulative distance is calculated, it is not possible to put it into practical use as a pattern comparison device, because the amount of calculation is enormous when comparing each vector for all combinations.

Considering a plane having an input pattern on one axis and a standard pattern on the other axis (hereinafter referred to as i-j plane), the combination of each vector of the input pattern and the standard pattern is on the i-j plane. It can be indicated by each grid point (hereinafter, simply referred to as a point). Therefore, to calculate the distance between each vector for all the above combinations,
Is to calculate the distance between the vectors at each point,
To calculate the cumulative distance is to sequentially calculate and sum the inter-vector distances of the feature vector of the input pattern and the feature vector of the corresponding standard pattern. The correspondence between the feature vectors of the input pattern and the standard pattern selected in the process of calculating the cumulative distance, that is, the point sequence is called a path.

Limiting the range of comparison in consideration of the physical properties of the input pattern described above means that a constraint condition is set for selecting a path.

Here, terms and symbols used in the following description will be described.

A: input pattern (A = a ₁ , a ₂ , ..., a _i , ..., a _I ), a _i is the feature vector of the first frame, I is the number of frames of the input pattern R ⁿ : nth standard pattern (R ⁿ = ▲ b ⁿ ₁ ▼, ▲ b ⁿ ₂ ▼, ...,
▲ b ⁿ _j ▼, ..., ▲ b ⁿ _J ▼ n) ▲ b ⁿ _j ▼ is the feature vector of the j-th frame of the n-th standard pattern J ⁿ is the number of frames of the n-th standard pattern, and N is the total number of standard patterns 1nN d ⁿ (i, j): inter-vector distance D (i) between the feature vector ▲ b ⁿ _j ▼ of the j-th frame of the n-th standard pattern and the feature vector a _i of the i-th frame of the input pattern The distance between the patterns of the input patterns from the 1st to i-th frames and the combined pattern of the optimum combination of the respective standard patterns (hereinafter referred to as the terminal cumulative distance) N (j): the input patterns of the 1st to i-th frames Number indicating the final tail standard pattern that constitutes the binding pattern when the optimal combination pattern of each standard pattern is obtained (hereinafter, final tail standard pattern name) B (i): N (i) starting point frame Shows the frame one before No. (hereinafter, a back pointer that) D ⁿ (i, j): distance between the pattern of the partial patterns to the first to the j-th frame of the partial pattern and R ⁿ up to the i'~ the i-th frame of the input pattern ( Below, the partial cumulative distance ▲ D ⁿ _j
▼ '(i, j)) and D (i'-1), the minimum value for i' (hereinafter referred to as intermediate cumulative distance) B ⁿ (i, j): partial cumulative distance ▲ D ⁿ _i ▼ ′ (i, j) and D (i′-1) are minimized i ′ Ie And when A number indicating the frame immediately preceding the frame (hereinafter referred to as the intermediate back pointer) [] Indicates a value of x when the value in [] is minimized with respect to x.

D ⁿ (i): Intermediate cumulative distance when j = J ⁿ , and D ⁿ (i) = D ⁿ
(i, J ⁿ ).

B ⁿ (i): an intermediate back pointer when j = J ⁿ , B
ⁿ (i) = ^Bn (i, ^Jn ).

In the O (n) DP method, if it is assumed that the input pattern ends at the i _O-th frame, i ′ is the starting point for obtaining the intermediate cumulative distance D ⁿ (i _O ) when the final tail pattern is R ^n. flame,
Partial pattern of input pattern with i _O as the end frame
The DP matching between A (i′-1, i _O ) and the standard pattern R ⁿ is performed with the starting point free and the terminal point fixed, and the initial value D ⁿ (i ′) of the intermediate cumulative distance at the starting point i ′ , 1) and the initial value B ⁿ (i ′, O) of the intermediate back pointer are D ⁿ (i ′, 1) ＝ D (i′−1) + d ⁿ (i, 1) B ⁿ (i ′, O) ) = B ⁿ (i′−1), the DP matching of the partial pattern A (i′-1, i _O ) and the standard pattern R ⁿ is performed as a continuation of the DP matching of the i′th to 1st frames. It is a thing. By doing so, for example, under the constraint condition for the matching path as shown in FIG. 1, the possible matching paths are limited to the area P in FIG. 2, and D ⁿ (i
The calculation of d ⁿ (i, j) and D ⁿ (i, j) required for obtaining _O ) only needs to be performed once for each point in the region P. In FIG. 2, the horizontal axis is the input pattern and the vertical axis is the last standard pattern R ⁿ . The region P is a region surrounded by a straight line P ₁ having a slope of 1/2 and a straight line 2 having a slope of 2. D ⁿ (i,
To obtain j), D ⁿ (i-2, j-
1), D ⁿ (i-1, j-1), D ⁿ (i-1, j-2), d ⁿ (i-1, j), d ⁿ (i, j) From, the intermediate cumulative distance on the i-th frame
To obtain D ⁿ (i _O , j) (where j = 1,2, ..., J ⁿ ), the i-th
Intermediate cumulative distance D ⁿ (i-
1, j), D ⁿ (i-2, j) and inter-vector distances d ⁿ (i-1, j) and d ⁿ (i, j) on the (i-1) ^th frame and the i-th frame (where j = 1,
2, ..., J ⁿ ).

At this time, D ⁿ (i _O ) can be obtained as D ⁿ (i _O ) = D ⁿ (i _O , J ⁿ ).

As described above, every time the frame i of the input pattern advances by one frame, the intermediate cumulative distance D ⁿ (i, j) on that frame (where j = 1,2, ..., J ⁿ ; n = 1,2, …, N) 1 frame before and 2
Intermediate cumulative distance D ⁿ (i-1, j), D ⁿ (i-2, j) before the frame and vector-to-vector distance d ⁿ (i-1, j), d ⁿ (i , j) (where j = 1,2, ..., J ⁿ ; n = 1,2,
,, N), As a result, the terminal cumulative distance to the i-th frame can be obtained. D ⁿ (i, j) (where j
= 1,2, ..., J ⁿ , n = 1,2, ..., N) is no longer needed, that is, D in the next frame or the next frame.
It is stored until the calculation of ⁿ (i, j) is completed.

The back pointer for D (1) (the value obtained by subtracting 1 from the starting point for D (i)) B (i) is obtained as follows.

When the intermediate back pointer for D ⁿ (i, j) is B ⁿ (i, j), 1) D ⁿ (i, j) ＝ D ⁿ (i-2, j-1) + d ⁿ (i- When 1, j) + d ⁿ (i, j), B ⁿ (i, j) ＝ B ⁿ (i-2, j-1) 2) D ⁿ (i, j) ＝ D ⁿ (i-1 , j-1) + d ⁿ (i, j), B ⁿ (i, j) ＝ B
^{When n} (i-1, j-1) 3) D ⁿ (i, j) ＝ D ⁿ (i-1, j-2) + d ⁿ (i, j), B ⁿ (i, j) ＝ B
^{By setting n} (i-1, j-2) given that Becomes Therefore, remember B ⁿ (i, j) one frame before and two frames before.

In the case of the path shown in Fig. 3, D ⁿ (i, j) and B ⁿ (i, j)
Need only remember the value of the previous frame.

A conventional example of the pattern comparison device using the above-described principle will be described. FIG. 4 is a block diagram showing a conventional example when the pattern comparison apparatus based on the above principle is applied to continuous word recognition. In the figure, In is a voice signal input terminal, and 1 is a feature extraction unit composed of a filter bank or the like, which converts the input voice signal into a system A of a feature vector a _i . Reference numeral 2 denotes a word standard pattern storage unit, in which N words as a recognition vocabulary are each a standard pattern R ⁿ = ▲ b
ⁿ ₁ ▼,…, ▲ b ⁿ _j ▼,…, ▲ b ⁿ _J n ▼, (1nN)
Is registered in advance in the form of a feature vector. Reference numeral 3 denotes an inter-vector distance calculation unit that calculates a distance d ⁿ (i, j) between the feature vector a _i in the i-th frame of the input pattern and the feature vector b _{j of the} ^nth word standard pattern R ⁿ as j =
Calculate 1, 2, ..., J ⁿ and store until no longer needed. In the present example, the vector distance one frame before the frame for which the intermediate cumulative distance is being calculated and the vector-to-vector distance of the frame are stored until the intermediate cumulative distance of the frame is calculated. For example, d ⁿ (i, j) can be defined as the city distance between a _i and b _j . That is, the dimension of the vector is set to 1, and a _i = (a _i1 , a _i2 , ..., a _i1 ), ▲ b ⁿ _j ▼ = (▲ b ⁿ _j1 ▼, ▲ b ⁿ
_j2 ▼,…, ▲ b ⁿ _j1 ▼) Becomes

Reference numeral 4 denotes a cumulative distance calculating unit, which is an intermediate cumulative distance D ⁿ (i, j), a terminal cumulative distance D (i), an intermediate back pointer B ⁿ (i, j), and a back pointer B (i) for the i-th frame. J = 1,2, ..., J ⁿ ;
N (i) indicating the last word obtained for n = 1, 2, ..., N
Ask for. When the constraint condition of the matching path shown in FIG. 1 is adopted, D ⁿ (i, j), D (i) is obtained from the following equation.

B ⁿ (i, j), B (i) is calculated from the following equation. B ⁿ (i, j) is 1) D ⁿ (i, j) ＝ D ⁿ (i-2, j-1) + d with B ⁿ (i, O) ＝ B ⁿ (i-1) as initial condition ^{When n} (i, j) + d ⁿ (i-1, j), B ⁿ (i, j) ＝ B ⁿ (i-2, j-1) …… (2) 2) D ⁿ (i, j When j) ＝ D ⁿ (i-1, j-1) + d ⁿ (i, j), B ⁿ (i, j) ＝ B ⁿ (i-1, j-1) …… (3) 3 ) D ⁿ (i, j) ＝ D ⁿ (i-1, j-2) + d ⁿ (i, j), B ⁿ (i, j) ＝ B ⁿ (i-1, j-2) ...... (4) is obtained, and B (i) is a word number that satisfies equation (1). Cumulative end distance calculated as above It is stored in the tail word storage unit 7.

Note that D ⁿ (i, j), B ⁿ (i, j) (where j = 1,2, ..., J ⁿ ; n = 1,2,
, N) is temporarily stored in the cumulative distance calculation unit 14 until it is no longer needed. In this embodiment, the intermediate cumulative distances of the frames one and two frames before the frame for which the intermediate cumulative distance is calculated are stored until the intermediate cumulative distance of the frame is calculated.

In addition, the terminal cumulative distance D stored in the terminal cumulative distance storage unit 5
(i) is necessary for obtaining the initial condition of the equation (1), and D (i) may be stored until D ⁿ (i + 1,1) is obtained.

Reference numeral 8 is a voice section detection unit that determines the voice section from the magnitude of the input signal or the like. The voice section detection unit 8
When it is detected that voice input is started, the frame number counting section 9 starts counting for each frame. The above process is the i-th
Although the processing was performed for frames, the count value of the frame number counting section 9 sets the i. Therefore, the same processing as described above is performed each time the frame advances. The frame number counting unit 9 starts counting when a voice section is detected, and is reset when the voice section ends. Therefore, N (i) and B (i) are stored in the last word storage unit 7 and the back pointer storage unit 6 for i = 1, 2, ...

The segmentation unit 10 issues a command for reading a predetermined back pointer to the back pointer storage unit 6. That is, the segmentation unit 10
When the following value is issued to the back pointer storage unit 6, the back pointer B (i) is read from the back pointer storage unit 6. When the segmentation unit 10 receives the value B (i) from the back pointer storage unit 6, the segmentation unit 10 issues the same value to the back pointer storage unit 6. Therefore, the voice section detection unit 8
When detects the end of voice input, the final value I of the frame number counting unit 9 is supplied to the segmentation unit 10, and the segmentation unit 10 first issues a value I to the back pointer storage unit 6. Thereafter, in accordance with the operation described above, the back pointer storage unit 6 stores B (I), B (B (I)), B (B (B (B
(I))), ..., O will be sequentially obtained. These values are the end frame of the penultimate word, the end frame of the third, the end frame of the fourth,
.., and N (i) is a word that ends in the i frame, so if this value is given to the last word storage unit 7 as it is, the recognition result is obtained from the last word in the reverse order. In order to prevent the recognition result from being obtained in the reverse order, this order conversion may be performed on the output of the back pointer storage unit 6 or the output of the last word storage unit 7.

The total number of calculations to the last frame I in the conventional device is the vector distance d (i, j),
Since the calculation of the intermediate cumulative distance D ⁿ (i, j) is performed only once for each point, if the average number of frames of the standard pattern is J, then NIJ is obtained. Total number of calculations in a conventional 2-stage DP method become. Now the frame length is 10msec and the word length is 0.5s on average.
If it is ec, the average number of frames of the standard pattern is J
Since J = 50, the number of calculations is 1 / 37.5. In addition, the number of calculations N when a window of R (calculation restricted area) is provided
Compared to IJR, it is 1 / R, and R is roughly 20th place, so the number of calculations is 1/20.

As described above, in the O (n) DP method, continuously uttered speech can be recognized with a far smaller number of calculations than in the two-stage DP method, and a continuous speech recognition device with a high recognition speed is realized. Since the processing can be performed for each input frame, a recognition device that operates in real time can be provided.

However, the inter-vector distance d ⁿ (i, j) and the intermediate cumulative distance D
ⁿ (i, j) is n = 1, 2, ..., N; j = 1, for each frame i
In order to obtain 2, 2, ..., J ⁿ , a fairly high-speed access is required as a standard pattern storage memory. For example, the frame period is 5 ms, the number of standard patterns N = 300, the average number of frames of standard patterns J =
If the number is 30, the average number of grid points to be calculated per frame of the input pattern is NJ = 9000, and if the dimension number of the feature vector is 15, the number of accesses to the standard pattern storage memory per frame of the input pattern Is
9000 x 15 = 135,000 times. In order to do this within 5 msec, an accelerator time of 37 ns or less is required. Also, the amount of memory required to store the standard pattern is 135 KB if one element of the feature vector is represented by 1 byte, and a high-speed memory that can be accessed in 37 nsec or less requires 135 KB. ,
It becomes a very expensive device.

OBJECT OF THE INVENTION It is an object of the present invention to significantly reduce the number of memories that require high speed access in a continuous pattern comparison device for real time by the above method.

According to the present invention, an input signal is converted into a feature vector a ₁ , a ₂ , ..., A _i , ..., A _I
, A standard pattern R ⁿ (however, a standard pattern R ⁿ composed of a series of feature vectors ▲ b ⁿ ₁ ▼, ▲ b ⁿ ₂ ▼, ..., ▲ b ⁿ _j ▼, ..., ▲ b ⁿ _J ▼ n. n = 1, 2, ..., N)
In a standard pattern storage means for storing the input pattern i and a standard graph frame j on the vertical axis in a lattice graph, with a gradient k when matching the standard pattern R ^n, with respect to the frame of the input pattern. For grid points sandwiched by straight lines separated by frames, j = 1, 2, ..., J ⁿ for the feature vector ▲ b ⁿ _j ▼ of each frame j of the standard pattern in the order of the matching path in the i-axis direction. The above-mentioned matching is performed over the entire range of the input pattern such that DP matching having a slope limit of maximum slope k is performed, and when calculation of one region is completed, calculation of the next adjacent region similar to the above is similarly performed. It is a pattern comparison device including a DP matching means for performing calculation.

Description of Embodiments FIG. 5 is a diagram showing the principle of the present invention. If the path limiting conditions are selected as shown in FIG. 1 or FIG. 3, 24 and 25 are straight lines with a slope of 2, and 20 and 21 are j = J ⁿ and straight lines 24 and 25.
, And the intersection points 22 and 23 between j = 1 and the straight lines 24 and 25, and W is J ⁿ / 2, the terminal cumulative distances of the lattice points included in 20 to 21 are included in 22 to 23. If the terminal cumulative distance to each grid point and the intermediate cumulative distance on the straight line 24 are obtained, it can be calculated. Further, in the middle of the calculation, it is possible to sequentially proceed from the bottom to the top in the horizontal direction as shown by the arrow 26. Thus, when the frame period is T, the calculation of the shaded area A is performed as described above during the time WT, and the calculation of the shaded area B is performed as described above during the next WT. The calculation described above can be sequentially advanced at each time WT.

In this way, the j-th frame of the standard pattern is W
Since it can be constant while matching with the input pattern of the frame,
The access time required for the standard pattern memory can be delayed. That is, the number of grid points in each shaded area is WJ, and the calculation for each grid point is TJ.
Although it has to be done during W (T is the frame period), the allowable calculation time for one frame of the standard pattern is TW / JN, which is equivalent to one frame of the standard pattern. It is equal to the time to read the data of, and if the above numerical example is applied, then W = J / 2 Therefore, if the order of the feature vector is the 15th order as before, the access time allowed to read the element of one vector of the standard pattern is 8.3 μsec / 15 = 553 nsec.
Therefore, the access time is about 15 times longer than the value required in the conventional example. However, this time, although high speed is required for the memory for storing the input pattern (reading NW times for the j-th frame of the standard pattern must be performed during the time TW / J. For the example, It is necessary to read 15 feature vectors during. Therefore, the access time allowed to read one element of the vector is 37 nsec), and the required capacity is 15 * W = 15 * 30 = 450 bytes on average for the above example. Will lead to a significant cost reduction.

The above is the principle of the present invention, but in the simple idea that W is fixed, In some cases, the value of W is determined by the shortest pattern among the standard patterns, which is not very effective. In order to compensate for this drawback, it is conceivable to change W according to the change of J ⁿ (W ⁿ = (J ⁿ /
2] +1). The principle of a comparison device according to this further principle according to the invention will now be described.

FIG. 6 is a detailed diagram for explaining the principle of the present invention. Now
The processing when the input pattern is the i-th frame will be described.
Each of the diagonal lines A and B will be called a block. At this time, If is not found, perform the above calculation for the grid points indicated by ○ in the figure, Ask for.

● is j = 1, 2, of the block immediately before this block
.., J ⁿ , the intermediate cumulative distance at these points is the initial value of the intermediate cumulative distance in this block. In this case, the constraint condition of the matching path is as shown in FIG. When the constraint condition of the path shown in FIG. 1 is used, it is necessary to further store the intermediate cumulative distance.

Is calculated, the calculation for the standard pattern corresponding to n is skipped.

According to the above, for each standard pattern R ⁿ , W ⁿ = [J ⁿ / 2] +1 is calculated for each ⁿ .

To determine whether or not If is initialized to O or ∞, it can be determined from the fact that it should be 0 or ∞ finite value when it is obtained.

FIG. 7 is a block diagram showing an embodiment of the present invention based on the above principle. Reference numeral 101 is a feature extraction unit that shows the same operation as 1 in FIG. 4, 102 is a word standard pattern storage unit similar to FIG. 4, and 103 is an inter-vector distance calculation unit similar to FIG. In the embodiment, the calculation direction is the i-axis direction, and for the vector b _j of the j-th frame of the ^n- th standard pattern R ⁿ , Find d ⁿ (m, j) for the input pattern in the range. 104
Is a cumulative distance calculation unit, which calculates an intermediate cumulative distance and a terminal cumulative distance in the same range as the d ⁿ (m, j). 112 is for determining the execution range of the calculation of the inter-vector distance and the calculation of the cumulative distance for each of n and j, Is not found, d ⁿ (m, j), D ⁿ (m,
The calculation of j) is instructed to the inter-vector distance calculation unit 103 and the cumulative distance calculation unit 104, respectively. 105 to 107 operate in the same manner as in FIGS. Reference numeral 111 is an output terminal for the recognition result, which is exactly the same as that obtained in FIG.

FIG. 8 explains the operation by software in order to more clearly explain the embodiment in FIG. 7, and the present invention may be implemented by software according to this example.

In this embodiment, the constraint condition of the path is as shown in FIG.

Reference numeral 201 denotes a step for performing initialization such as substituting ∞ for the intermediate cumulative distance, the terminal cumulative distance, etc. before starting the matching process. 202 is for processing after the end of the voice section
This is a step of setting flag to "0". 203
Is a step of detecting the start of a voice section and corresponds to the operation performed by FIG. Steps 201 and 202 are executed until the voice section is detected. When the voice section is detected, steps 204 to 229 are executed for each input frame. Steps 205 to 224 are executed for each standard pattern in frame i. 206 is a step of determining whether or not to perform matching calculation for the standard pattern n in the frame i. It is determined that the matching calculation should be executed when the following three conditions are satisfied.

This corresponds to the operation of the matching calculation execution range determination unit in FIG. 112. In steps 207 to 210, prior to the execution of the matching calculation in the i-th frame,
The initial value of the recurrence formula of the matching calculation is set for the standard pattern n. That is, Where D ⁿ (m-1, O) ＝ D (m-1), B ⁿ (m-1, O) ＝ m-1 Run about. In steps 211 to 217, j = 1, ..., J ⁿ ; For the standard pattern n, the intermediate cumulative distance and the intermediate back pointer are calculated. 213 is its recurrence formula, Is.

This formula has exactly the same form except that i in formula (1) is changed to m.
While it was calculated by changing to ~ J ⁿ , in this formula,
For each j, It is different in that it is changed and requested. Step 218-
Step 222 was calculated in Step 213 Intermediate cumulative distance D ⁿ for (m, J ⁿ⁾ is, ^{'intermediate} cumulative Kyoriri D ^{n for'} standard pattern R ⁿ which it was previously calculated
When it is smaller than the minimum value of (m, J ^{n ′} ), step 220
The replacement shown in is performed. As described above, when the operations of steps 205 to 224 are completed, i
For each previous frame, the minimum value for the calculated R ⁿ will be in D (i). The above operation is mainly performed in FIGS.
225 is a step of detecting the end of the voice section. The above steps 205 are performed until the end of the voice section is detected.
~ The operation of step 225 is performed, and the terminal end cumulative distance D
(i), end back pointer B (i), and last word N (i) are sequentially calculated and stored in a predetermined place. Step two
In steps 26 to 229, even if it is detected that the voice section is finished by performing the above calculation, the processing is performed for each block, so that the D (i), B (i), N ( Since i) etc. are generally not obtained until the end frame of the voice section, in order to obtain this completely, the above calculation is further performed. It is the part to proceed to. However, And I is the frame at the end of the voice section. Step 231 is a part for obtaining an input word string from the end back pointer B (i) and the last word N (i) obtained as described above in the same manner as in the conventional example. Step 232 is a part for outputting the result, which is printed out as a character or becomes an output of a command for moving another device.

In the present embodiment, for convenience of explanation, the inter-vector distance, the intermediate cumulative distance, the intermediate back pointer, etc. at the point (i, j) are respectively d ⁿ (i, j), D ⁿ (i, j). ), B ⁿ (i,
j) etc., these storage areas do not need to be prepared over the entire range of i, j, and the calculation of D ⁿ (i, j), B ⁿ (i, j) at the j- ^th grid point As is clear from the recurrence formula shown in FIG. 213 in FIG. 8, the intermediate cumulative distance D ⁿ (j−1) th j−2nd cumulative distance D ⁿ (for both the paths in FIGS. 1 and 3). i, j
-1), D ⁿ (i, j-2), intermediate back pointer B ⁿ (i, j-1), B ⁿ (i, j-
Only 2) needs to be memorized, and when this calculation is completed, D ⁿ
The stored contents of (i, j-2), B ⁿ (i, j-2) are discarded, and D ⁿ (i, j-
1), B ⁿ (i, respectively and the content of the ^{j-1) D n (i} , j-2), B n (i, in the storage area of ^{j-2), D n (} i, j), B n The content of (i, j) is D ⁿ (i, j-1), B ⁿ (i,
It is sufficient to move to the storage area of (j-1) and store the calculation result of the next stage in the storage area of D ⁿ (i, j), B ⁿ (i, j). Also, the width of each block is at most Since it is sufficient, as the buffer memory for the calculation of the recurrence formula, and W _max buffer memory 1 stage of the frame for the input pattern, W _max frame as a buffer memory for intermediate cumulative distance and the intermediate back pointer In the case of the path limiting condition of FIG. 1, it is necessary to store only d ⁿ (i-1, j) for storing the distance between vectors, and only one frame It will be good if you prepare. In the case of the path limiting condition of FIG. 3, the vector-to-vector distance is used each time it is calculated, so it need not be stored.

Further, in this embodiment, since the constraint condition of the path as shown in FIG. 1 or FIG. 3 is used, the maximum inclination of the path is 2. Therefore, the width of the block is [J ⁿ / 2] +1. But
Various other constraint conditions for the route are conceivable. For example, in the case of FIG. 9, the maximum inclination is 3, so the block width in this case is Becomes Generally, when the maximum slope of the path is k, the width W of the block is The following is good (when k = 2, Is the same when J ⁿ is an integer).

Further, in this embodiment, the intermediate cumulative distance In the above, the case of initializing this to ∞ or the like to determine whether or not has been obtained has been described, but it is determined whether or not i is divisible by W ⁿ for the input frame i, and if it is divisible, the matching calculation is performed. The matching calculation may be skipped if it is not divisible.

EFFECTS OF THE INVENTION As described above, according to the present invention, the CWDP method and the O (n) D method are used.
In the method of continuously performing DP matching at high speed like the P method, a high-speed and large-capacity memory was required. However, the number of memories requiring high-speed performance can be significantly reduced, and the cost is low. It has become possible to realize various devices.

[Brief description of drawings]

FIG. 1 is a diagram showing the constraint condition of the matching calculation path, and FIG.
FIG. 3 is a diagram showing a region for performing matching calculation, FIG. 3 is a diagram showing another constraint condition of a matching calculation path, FIG. 4 is a block diagram showing a conventional example of a voice recognition device, and FIG. 5 is a principle of the present invention. FIG. 6 is a diagram for explaining the details of the principle of the present invention, FIG. 7 is a block diagram of a voice recognition device of an embodiment of the present invention, and FIG. 8 is a function of the device of the same embodiment. FIG. 9 is a flowchart when the above is realized by software, and FIG. 9 is a view showing another column of the constraint condition of the matching calculation path. 101 ... Feature extraction unit, 102 ... Word standard pattern storage unit, 103 ... Vector distance calculation unit, 104 ... Cumulative distance calculation unit, 105 ... Terminal cumulative distance storage unit, 106
...... Back pointer storage unit, 107 ...... End word storage unit, 108 ...... Voice section detection unit, 109 ...... Frame number counting unit, 108 ...... Voice section detection unit, 109 ...... Frame number counting unit, 110 ... segmentation section, 112
...... Matching calculation execution range determination unit.

Claims (1)

[Claims] 1. An input signal is represented by feature vectors a ₁ , a ₂ , ..., A _i ,.
A feature extraction means for converting into a series of _I (input pattern),
A standard pattern consisting of a series of feature vectors b ⁿ , b ⁿ , ..., b ⁿ , ..., b ⁿ _n In a standard pattern storage means for storing the input pattern and a lattice graph having the frame i of the input pattern as the horizontal axis and the frame j of the standard pattern as the vertical axis, when the input pattern is matched with the standard pattern R ⁿ , the gradient k , In a region surrounded by two straight lines separated from each other by W (n) frames with respect to the frame of the input pattern and each straight line of j = 1 and j = J ⁿ , corresponding to the lattice point of the j-th stage of the region. Input pattern feature vector series and standard pattern frame j
DP matching with the feature vector ▲ b ⁿ _j ▼ of j = 1, 2,
, J ⁿ , and when the calculation of the region is completed (j
= The calculation of J ⁿ stages is completed) and so do the following Aitonaru calculation of the similar region in a similar order, and a DP matching unit for performing the matching calculation over the entire range of the input pattern, the DP matching is the maximum slope k following lean limiting matching path, the W (n) is a function of frame number J ⁿ of R ^n, each n reference pattern R ⁿ to be matching calculation A pattern comparison device characterized by being set to.