JPH0646358B2 - 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 to identify the input pattern, In particular, the present invention relates to a pattern comparison device applicable to recognition of continuously-spoken word sounds.

2. Description of the Related Art If voice, which is the most natural information generating means for human beings, can be used as an inputting means of human-machine system, its effect is very large. In that case, it is desirable for the voice recognition device to be able to recognize continuously uttered voices as a condition for recognizing a more natural voice.

As a pattern comparison device effective for recognition of continuously spoken word voices, a pattern comparison device using a so-called two-stage DP method using a dynamic programming method (hereinafter referred to as DP) in two steps 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 is complicated and expensive. There is no choice but to become something like that.

In order to eliminate the above-mentioned drawbacks, a pattern comparison device having a significantly small calculation amount is used as an O (N) DP method, a CWDP method,
A pattern comparison device using the CDP method or the like has been proposed. However, there is a drawback that a large-capacity memory that can be accessed at high speed is required to implement these methods by hardware.

The present invention provides a pattern comparison apparatus in which these drawbacks are eliminated, and particularly, Japanese Patent Application No. 58-48600.
The ACDP (Augmented Co
ntinuous DPMatching) method. This method can be applied to both cases of unknown word number and known word number, and automan control is also possible.

Prior to describing the present invention, the ACDP method will be described next. Hereinafter, for simplicity, the case of word counting will be described. Further, the pattern comparison apparatus of the present invention,
Although it can be used for recognition of various input patterns, a continuous word voice that is continuously uttered 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 expanding and contracting input pattern with the standard pattern, the feature vectors of the input pattern and the standard pattern are associated with each other in a non-linear manner. We need to calculate which is most similar to. However, although this input voice expands and contracts non-linearly, it does not extend or shorten abnormally.

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 covered.

The input speech signal is converted into a series of several numerical value groups (feature vectors) by frequency analysis, LPC analysis, PARCOR analysis, correlation analysis, etc. in a pattern comparison device and compared with the series of feature vector of this input pattern. The series of feature vectors of the target 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 huge to compare each vector for all combinations.

Considering a plane having the input pattern on one axis and the standard pattern on the other axis (hereinafter referred to as the 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 lattice point (hereinafter, simply referred to as a point). Therefore, to calculate the distance between the vectors for each of the combinations is to calculate the distance between the vectors at each point, and to calculate the cumulative distance is to calculate the feature vector of the input pattern,
The vector distance between the corresponding feature vector of the standard pattern and the vector distance is sequentially calculated and totaled. 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. To limit the range of comparison in consideration of the physical properties of the input pattern described above means to set a constraint condition on the selection of the 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 : Feature vector of i-th frame of input pattern A I: Number of frames of input pattern R ⁿ : n-th standard pattern (R ⁿ = b ⁿ ₁ , b ⁿ ₂ , ...,
b ⁿ _j , ..., b ⁿ _Jn ) b ⁿ _j : Feature vector of j-th frame of n-th standard pattern J ⁿ : Number of frames of n-th standard pattern n: Word name (word number) 1 ≦ n ≦ NN: Total number of standard patterns d ⁿ (i, j): inter-vector distance D ⁿ (s: t) 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 : part of the input pattern pattern _a s ~a
Minimum cumulative distance between _t and standard pattern R ⁿ (hereinafter referred to as partial cumulative distance) D (i): pattern of the input patterns from the 1st to i-th frames and the combined pattern of the optimum combination of each standard pattern Distance between frames (hereinafter referred to as “terminal cumulative distance”) N (i): constructs a combination pattern when an optimum combination pattern of each standard pattern with respect to the input patterns of the 1st to i-th frames is obtained. Number indicating the last standard pattern (hereinafter referred to as the last word name) B (i): Frame number indicating the frame immediately before the starting point frame of N (i) (hereinafter referred to as back pointer) The minimum value of m of the minimum cumulative distance between the partial patterns a _{m + 1 to a} i of the input pattern and the partial patterns b ⁿ _{1 to} b ⁿ _j of the standard pattern and the standard pattern R ⁿ (hereinafter, referred to as intermediate cumulative distance) The starting point position of the input pattern that satisfies the following (hereinafter referred to as the intermediate back pointer) However, the path of DP matching is D ⁿ (s: t), D (i)
Is a path with the axis on the input pattern side as the basic axis, Is a path with the axis on the standard pattern side as the basic axis.

Continuous word speech recognition by DP matching is efficiently performed by calculating the following recurrence formula. I.e. However, for m ^* and n ^* , i = 1 to m
If I is calculated sequentially, N (I), N (B (I)), N (B
The words input by (B (I)), ..., N (B (B (... B (I) ...))) are obtained in the reverse order.

FIG. 2 is a diagram explaining the physical meaning of the calculation of equation (1). b is an embodiment of the constraint condition of the path when D ⁿ (m: i) is calculated. That is, the path to the point (i, j) always passes through the points (i-2, j-1), (i-1, j-1), (i-1, j-2),
When the cumulative distance is calculated, the vector distance of each point is weighted by the numbers shown on the path according to the selected path. If the weights are given in this way, no matter which path is selected, the sum of the weights along the path is not equal to the number of frames of the input pattern, regardless of the path selected. “A” shows a state of matching between the partial pattern from the (m + 1) th frame to the i-th frame of the input pattern and the nth standard pattern R ⁿ . Straight line 1 has a slope of 1/2, straight line 2 has a slope of 2
Therefore, the DP matching path is limited to the area between the two straight lines under the constraint condition of b. 3 is an example of the selected matching path.

In order to calculate the equation (1), D ⁿ (m + 1: i) is set to n = 1 to N
For, over a range of m related to i and J ⁿ ,
It has to be calculated for each i = 1 to I. That is, in the example of FIG. 2a, the vector distance and the cumulative distance have to be calculated for all grid points in the triangular area surrounded by the straight lines 1 and 2 every time i changes.

In the ACDP method, the calculation amount of D ⁿ (m + 1: i) is approximately reduced by introducing the concept of word spotting, and the calculation amount is greatly reduced.

FIG. 3 is a diagram for explaining the concept of the ACDP method. FIG. 5A is a diagram showing an example of a constraint condition of a path. That is, the point (i,
The path to j) is point (i-2, j-1), (i-1, j-1), (i-1,
j-2) is always passed and the number shown on the path represents this weight. The essential difference from the one shown in FIG. 2b is that if the weights are given in this way, no matter what path is selected under the constraint conditions of the path shown in FIG. The sum is equal to the number of frames in the standard pattern and is constant.

To summarize the concept of the ACDP method, (1) In accordance with the constraint condition of the path with the axis on the standard pattern side as the basic axis as shown in FIG. To calculate.

(2) From D ⁿ (m-r + 1: i) to D ⁿ (m + r + 1: i) are approximately estimated. That is, Becomes Here, r is the range of estimation of D ⁿ (m + 1: i).

From (1) and (2), It means that D ⁿ (m + 1: i) having an arbitrary point of as a starting point and an end point of i can be estimated approximately.

When this method is applied to continuous word speech recognition, it becomes as follows.

(1) Initial condition (2) Perform (3) to (7) for i = 1 to I (3) Perform (4) to (6) for n = 1 to N (4) (5) Regarding j = 3 to J ⁿ (6) About r '= 0 to r (7) (8) Judgment processing (obtaining a word string from B (i) and N (i) in the reverse order as described above) As is clear from the above processing, according to the ACDP method, the d The calculation of steps (4) and (5) including the calculation of ⁿ (i, j) needs to be performed only once for each i and n, so that the calculation amount is significantly reduced as compared with the normal two-stage DP. Is.

However, the inter-vector distance d ⁿ (i, j) and the midway cumulative distance ⁿ (i, j) are n = 1 to N, j = 1 for each frame i.
To determine the through J ⁿ as a standard pattern storage memory, is considerably the high-speed access is required. For example, if the frame period is 5 msec, the number of standard patterns is N = 300, and the average number of frames of standard patterns is J = 30, the average number of grid points to be calculated per frame of the input pattern is NJ = 9000, and If the number of dimensions is 15, the number of accesses to the standard pattern storage memory per frame of the input pattern is 90.
00 × 15 = 135,000 times. In order to do this within 5 msec, an access time of 37 nsec 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, which means that a high-speed memory that can be accessed in 37 nsec or less requires 135 kB. However, the device becomes very expensive.

DISCLOSURE OF THE INVENTION Problems to be Solved by the Invention An object of the present invention is to significantly reduce the number of memories that require high-speed access in the continuous pattern comparison apparatus using the ACDP method.

Means for Solving the Problems The pattern comparison apparatus of the present invention is a feature extraction means for converting an input signal into a sequence of feature vectors a ₁ , a ₂ , ..., A _i , ..., A _{I, and} a sequence of feature vectors. b ⁿ ₁ , b ⁿ ₂ , ...,
A standard pattern R ⁿ ( ^where b ⁿ ₃ , ..., B ⁿ _jn
(n = 1 to N), and in the lattice graph having the input frame i as the horizontal axis and the standard pattern frame j as the vertical axis, when the input pattern is matched with the standard pattern R ⁿ W for each frame
For the grid points in the area sandwiched by straight lines separated by frames, DP matching j = 1 to J with the width W in the i-axis direction for each of the feature vectors b ⁿ _j of each frame j of the standard pattern. ^A DP matching means for performing the matching calculation over the entire range of the input pattern is performed in such a manner that, when the calculation of one region is completed, the calculation of the next adjacent region similar to the above is performed in the same manner by performing the calculation in the order of ^n. I have it.

The working input signal is represented by feature vectors a ₁ , a ₂ , ..., A _i , ..., A
_I ⁿ sequence, and the feature vector sequence b ⁿ ₁ , b ⁿ ₂ ,
, B ⁿ _j , ..., B ⁿ J ⁿ , a standard pattern R ⁿ (where n = 1 to N), and a grid graph with the input frame i as the horizontal axis and the standard pattern frame j as the vertical axis. In the case of matching with the standard pattern R ⁿ , in the feature vector b ⁿ _j of each frame j of the standard pattern with respect to the grid point of the area sandwiched by the straight lines separated by W frames from the frame of the input pattern. For each of them, DP matching is performed in the width of W in the i-axis direction in the order of j = 1 to J ⁿ , and when the calculation of one region is completed, the calculation of the next adjacent region similar to the above is similarly performed. In this way, the matching calculation is performed over the entire range of the input pattern.

Embodiment FIG. 4 is a diagram showing the principle of the present invention. If the path limiting condition is selected as shown in FIG. 3, ^assuming that 8 and 9 are straight lines parallel to the j-axis and separated by W (≦ J ⁿ / 2) frames from each other, the cumulative cumulative distance ⁿ ( i, j) is obtained,
Cumulative distance ^{n in} the middle of the area (shaded area) sandwiched by both straight lines
(I, j) can be calculated, and if the intersection of the straight line 8 and the straight line j = J ⁿ is 10, and the intersection of the straight line 9 and the straight line j = J ⁿ is 11, it is included in 10-11. The cumulative end distance D (i) to each grid point can be calculated if the cumulative end distance before the straight line 8 is obtained. The calculation on the way can proceed from the bottom to the top in the lateral direction as shown by arrow 12. In this way, 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. In addition, the above-described calculation can be sequentially advanced every 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 it is necessary to perform the calculation for each grid point during TW (T is the frame period), but at this time, one frame of the standard pattern is used. The calculation time allowed for is TW / JN, which is equal to the time for reading the data for one frame of the standard pattern, and if the above numerical values are applied, W = J / 2, so T (J /2)/JN=T/2N=5msec/2×300=8.3μsec, and if the order of the feature vector is the 15th order as before, the access permitted to read one vector element of the standard pattern The time is 8.3 μsec / 15 = 553 nsec, which is about 15 times as long as the access time required in the conventional example. However, this time, the memory for storing the input pattern is required to have high speed (for the j-th frame of the standard pattern, NW readings must be performed during the time TW / J. For the example, TW / J / NW = T / NJ = 5msec / 300 × 30 = 0.56μsec
It is necessary to read 15 feature vectors during the period. Therefore, the access time allowed to read one element of the vector is 37 nsec. The required capacity is 15 W = 15 × 30 = 450 bytes on average for the above example, which leads to a significant cost reduction.

Although the above is the principle of the present invention, W can be fixed or variable. When W is fixed, basically, it is easiest to set W ≦ J _min / 2 when the minimum value of J ⁿ is J _min , but very short J ⁿ is included. Sometimes it's not very effective. However, if a memory is used, calculation can be performed according to the above concept even when W> J _min / 2. That is, ⁿ (i,
J ⁿ ) itself can be calculated with an arbitrary width of the input frame, but in order to obtain D ⁿ (i) from this, it is necessary to find the terminal cumulative distance up to iJ _min / 2. Therefore, W
When> J _min / 2, W− until calculation of D ⁿ (i)
J _min / 2 frames of ^{n (i, J n),} n (i, J n) may be stored to. Further, in order to compensate the above-mentioned drawback, J ⁿ
It is also possible to make W variable according to.

In this embodiment, a case where W is variable according to J ⁿ will be described.

FIG. 5 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 D ⁿ (i- [J ⁿ / 2]) has not been obtained, the above calculation is performed for the lattice points indicated by ◯ in the figure, and D ⁿ (i- [J ⁿ / 2]), D ⁿ (i-
[J ⁿ / 2] +1), ..., D ⁿ (i) is calculated. ● is a grid point at j = 1, 2, ..., J ⁿ of the block immediately before this block, and the midway cumulative distance ⁿ (i,
j) is the initial value of the midway cumulative distance ⁿ (i, j) in this block. When D ⁿ (i- [J ⁿ / 2]) is obtained, the calculation for the standard pattern corresponding to this n is skipped.

By doing so, the width of the block for each standard pattern R ⁿ is calculated as W ⁿ = [J ⁿ / 2] +1 for each ⁿ . To determine whether D ⁿ (i- [J ⁿ / 2]) is determined, first D ⁿ (i- [J ⁿ
/ 2]) is initialized to 0 or ∞, it can be determined from the fact that it is a finite value other than 0 or ∞ when it is obtained. Or D ⁿ (i)
Is set, G ⁿ (i) = 0 is set, and when not set, a flag G ⁿ (i) is set to set G ⁿ (i) = 1, and an initial value is set to G ⁿ (i) = 1 for i = 1 to I, and D ⁿ (i)
If it is assumed that G ⁿ (i) = 0 each time is obtained, it is possible to determine whether D ⁿ (i) is obtained by looking at G ⁿ (i).

FIG. 1 is a block diagram showing an embodiment of the present invention based on the above principle. Input terminal of the I _n audio signals, 101 denotes a feature extraction section consisting of a filter bank or the like, converts the input audio signal to the series A feature vector a _i. 1
Reference numeral 02 denotes a word standard pattern storage unit, in which N words as a recognition vocabulary are standard patterns R ⁿ = b ⁿ ₁ , ..., B respectively.
ⁿ _j, ..., it is registered in advance in the form of feature vectors as _{^{b n Jn (1 ≦ n ≦}} N). Reference numeral 103 denotes an inter-vector distance calculation unit, which calculates a distance d ⁿ (m, j) between the feature vector a _i in the i-th frame of the input pattern and the standard pattern b _{j of the} ^nth standard word pattern R ⁿ , and Memorize until there is no more. In this example, the frame immediately preceding the frame for which the partial cumulative distance is calculated and the vector-to-vector distance of the frame are stored until the midway cumulative distance of the frame is calculated. d ⁿ (m, j) may be defined as a town distance eg _{a m} and b ⁿ _j. That is, the dimension of the vector is L
, A _m = (a _m1 , a _m2 , ..., a _mL ), b ⁿ _j = (b ⁿ
_j1 , b ⁿ _j2 , ..., b ⁿ _jL ) Becomes Further, in the present embodiment, the calculation direction is the i-axis direction, and an input in the range of i- [J ⁿ / 2] ≦ m ≦ i is applied to the vector b _j of the j-th frame of the ^n- th standard pattern R ⁿ . Find d ⁿ (m, j) for the pattern. Reference numeral 104 denotes an intermediate cumulative distance calculation unit, which is an intermediate cumulative distance ⁿ (m, j) and an intermediate back pointer in the same range as the d ⁿ (m, j).
^{Find n} (m, j). A terminal cumulative distance calculation unit 113 calculates D (m), B (m), N (m) in the same range as the d ⁿ (m, j). When the constraint condition of the matching path shown in FIG. 3A is adopted, ⁿ (m, j) and ⁿ (m, j) are obtained in the midway cumulative distance calculation unit 104 as follows.

When j = 1, ⁿ (m, 1) d ⁿ (m, j) ⁿ (m, 1) = m When j = 2 When j ≧ 3 However D (m), B (m) and N (m) are calculated in the terminal cumulative distance calculation unit 113 as follows.

That is, for p = ⁿ (m, j) m ′ = pr to p + r m ′ And calculate By the following recurrence formula, B (m) = m ′ ^* N (m) = n ^* is obtained. However, m ′ ^* and n ^* are m ′ and n that satisfy the equation (2).

Reference numeral 112 is for determining the execution range of the calculation of the inter-vector distance and the calculation of the cumulative distance for each n.
When (i- [J ⁿ / 2]) is not found, the calculation of d ⁿ (m, j) and ⁿ (m, j) in the range of m is performed by the inter-vector distance calculation unit 103 and the intermediate cumulative distance calculation, respectively. Part 104,
The terminal accumulated distance calculation unit 113 is instructed.

The cumulative end distance D (m) obtained as described above is stored in the cumulative end distance storage unit 105, the back pointer B (m) is stored in the back pointer storage unit 106, and the last word number N (m) is the last word. It is stored in the storage unit 107.

Note that ⁿ (m, j), ⁿ (m, j) (where j = 1,
2, ..., J ⁿ ; n = 1, 2, ..., N) is temporarily stored in the partial cumulative distance calculation unit 104 until there is no need. In the present embodiment, it is stored until the midway cumulative distance of the frame one frame before and the frame two frames before the midway cumulative distance is calculated.

Further, the cumulative end distance D (m) stored in the cumulative end distance storage unit 105 is required as the initial value of the equation (1), and D (m)
Should be stored until ⁿ (m + 1,1) is obtained.

Reference numeral 108 denotes a voice section detection unit that determines the voice section from the magnitude of the input signal or the like. Voice section detector 1
When 08 detects that voice input has started, the frame number counting unit 109 starts counting for each frame. Although the above-mentioned processing is processing for the i-th frame, the count value of the frame number counting unit 109, that is, this i is set. Therefore, the same processing as described above is performed each time the frame advances. The frame number counting unit 109 starts counting when a voice section is detected, and is reset when the voice section ends. Therefore, in the last word storage unit 107 and the back pointer storage unit 106, N (i) B (i) is i =
1, 2, ..., I will be stored.

The segmentation unit 110 is the back pointer storage unit 1.
A command to read a predetermined back pointer is issued to 06. That is, the segmentation unit 110
Is issued to the back pointer storage unit 106,
From the back pointer storage unit 106, the back pointer B
(i) is read. When the segmentation unit 110 receives the value B (i) from the back pointer storage unit 106, it sends the same value to the back pointer storage unit 106. Therefore, when the voice section detection unit 108 detects the end of voice input, the final value I of the frame number counting unit 109 is supplied to the segmentation unit 110, and the segmentation unit 110 first outputs a value I as the back pointer storage unit 10.
Depart at 6. Thereafter, in accordance with the operation described above, the back pointer storage unit 106 stores B (I), B (B (I), B (B
(I)))), ..., 0 are sequentially obtained.
These values are the end frame of the penultimate word, the end frame of the third word, the end frame of the fourth word, and so on, and N (i)
Is a word ending with the i-frame, and if this value is given as it is to the last word storage unit 107, the recognition result is obtained from the last word in the reverse order. In order to obtain the recognition result in the original order, this order conversion may be performed on the output of the back pointer storage unit 106 or the output of the last word storage unit 107.

In the above embodiment, for convenience of explanation, the inter-vector distance at the point (m, i), the midway cumulative distance, the midway back pointer, etc. are respectively d ⁿ (m, j) and ⁿ (m,
j), ⁿ (m, j), etc., these storage areas do not need to be prepared over the entire range of i, j, n,
As is clear from the above recurrence formula, the calculation of ⁿ (m, j) and ⁿ (m, j) at the grid points of the step is performed in the j-1th step and the ^nth step for the path of FIG. j-2 stages of ⁿ (m, j-1),
^{n (m, j-2)} , n (m, j-1), n m, j-2), d n (m, j-1 for inter-vector distance) (where, m = iJ ₀ -2~
Only i) needs to be stored. Also, j for every n
= 1 to J ⁿ , if these values are calculated, ⁿ (m, j) and ⁿ (i, j) will be calculated once for one block with respect to n. It is not necessary to remember.

Based on this idea, a more detailed description will be given according to FIG. Needless to say, this may be followed when implemented by software. In the figure The notation is to execute Y while X is satisfied. The notation is to execute Y until the condition X is satisfied. The notation ENDIF means to execute Y if the condition X is satisfied, and to execute Z otherwise.

Further, the notation regarding the cumulative distance on the way, the back pointer on the way, the distance between vectors, etc. is changed as follows. That is, the third
When the path shown in the figure is used, the intermediate cumulative distance and intermediate back pointer of the j-th stage are calculated by calculating the intermediate cumulative distance and intermediate back pointer of the j-1th stage and the j-2th stage, and the j-1th stage. It is sufficient to store the inter-vector distance of the vector, and the calculation of the midway cumulative distance and the midway back pointer in the frame of the first input pattern of the block is performed by calculating the midway cumulative distance one frame before and two frames before and the midway back pointer, one frame. It suffices if the previous inter-vector distance is stored. After all, the required memory is ^{n =} (i, j), i = for ⁿ (i, j)
-1 to J ₀ +1 for 3 stages, and d ⁿ (i, j) 2 stages for i = _{0 to} J ₀ +1 (where -1 is one of the last frames of the immediately preceding block). The previous frame, 0 means the last frame of the immediately preceding block.), ^N (i, j), ⁿ (i, j), ⁿ (i, j), and ⁿ in the last frame and the last frame of each block. The recurrence formula can be calculated if ^dn (i, j) in the final frame is stored, and if one block is calculated for each word n, i = -1 to J ₀
^N (i, j) and ⁿ (i, j) for 3 stages of +1 are i = −1 to
Since J _m +1 can be used in common for all n, these are respectively (i ₀ ,
k), (i ₀ , k) (where i ₀ = -1 to J _m + 1, k = 0 to 2),
The two-stage d ⁿ (i, j) of i = _{0 to} J ₀ +1 is i = _{0 to} J _m +
Since it can be commonly used for all n by setting it to 1, this is d (i ₀ , k) (where i ₀ = 0
.About.J _m + 1, k = 0 to 2), and as a memory for storing the initial value of the next block, in the frame immediately before the final frame and the final frame of each block.
^{n (i, j), n} (i, j), d n (i, j) respectively ⁿ in the last frame of each block ^{(i, j), n (} i,
j), d ⁿ (j) where i = 0 to 1, j = 1 to J ⁿ , i = 0 is the final frame, and i = 1 is 1 of the final frame.
The previous frame) can be set, and a significant saving of memory can be achieved.

In FIG. 6, steps 201 and 202 are parts for performing initialization. Step 203 is a portion for performing processing in the input i-th frame. Step 204 is a process of matching the first to Nth standard patterns with the input pattern for each grid point in the block. Step 205 finds the width of the block for the nth standard pattern. Step 206 in the i-th frame of the input, the i-J ₀ the whether the frame, second i-frame termination cumulative distance D (m) is been determined flag G
It is a process of judging from the state of ⁿ (m), and if it is not found, the block is calculated, and if it is found, it is skipped to the process of n = n + 1. In step 207, when it is determined that the corresponding block has not been calculated yet, the calculation of the block is performed in the following steps. Therefore, the flag G ⁿ (m) is set to 0 for the frames included therein beforehand. It's already calculated.
In step 208, the start frame -1 of the block to be calculated is calculated as m ₀ for convenience of later calculation. Step 209 sets initial values for j = 1 and 2.

Step 210 is (i ₀ , j), (i ₀ , for j = 1.
j) (however, i ₀ = 1 to J ₀ +1) is calculated. Step 211 finds the serial number of the frames from the first frame of the input pattern. In step 212, the m-th vector a _m of the input pattern and the first vector of the standard pattern
The vector-to-vector distance to the second vector b ⁿ ₁ is calculated.
In step 213, based on this value, for j = 1 (i ₀ ,
j) and (i ₀ , J) (where i ₀ = 1 to J ₀ +1) are calculated.

In steps 214 and 215, j = 2, i ₀ = 1 to J ₀ +1
The inter-vector distance d (i ₀ , 2) at is calculated. In step 216, based on this value, (i ₀ , j) at j = 2,
(I ₀ , j) (where i ₀ = 1 to J ₀ +1) is calculated. Step 217 performs the replacement d ⁿ (2) = d (J ₀ +1,2) for use in the calculation of the next block.

In step 218, (i ₀ , k) in j = 3 to J ⁿ ,
(I ₀ , k) (where i ₀ = 1 to J ₀ +1) is calculated. In step 219, (i ₀ , k), (i ₀ , k), d
The value of k is set according to the value of j in order to cyclically use the memory (i ₀ , k). In step 220, the initial value is set from the value of the immediately preceding block. Step 22
1 calculates the inter-vector distance in the j-th stage. In step 222, based on this value, (i ₀ ,
j) and (i ₀ , j) (where i ₀ = 1 to J ₀ +1) are calculated. Step 223 makes a replacement for use in the calculation of the next block.

Step 224 is obtained as follows (i ₀ , J ⁿ ),
From (i ₀ , J ⁿ ) (where i ₀ = 1 to J ₀ +1), D (m), B (m) and N (m) are calculated according to the above description,
Each time n changes, it is compared with the previously calculated value and finally the minimum value is obtained.

When the process of step 203 ends, the determination process starts. That is, in step 230, i = I is set, and the word string to be obtained in step 231 is obtained in the reverse order according to the above description.

In the present embodiment, since the constraint condition of the path as shown in FIG. 3 is used, the maximum inclination of the path is 2. Therefore, the width of the block is [J ⁿ / 2] +1. Various conditions other than this are conceivable. For example, in the case of FIG. 7, the maximum inclination is 3, so the block width in this case is 2- [1- (J ⁿ -1). / 3]. Generally, when the maximum inclination of the path is k, the width W of the block may be 2- [1- (J ⁿ -1) / k] or less (when k = 2, [J ⁿ / 2] +1 and 2-
[1- (J ⁿ -1) / 2] is the same when J ⁿ is an integer).

EFFECTS OF THE INVENTION As described above, according to the present invention, like the ACDP method,
A high-speed, large-capacity memory was required in the method of continuously performing DP matching at high speed, but the number of memories required for high-speed performance can be significantly reduced, and an inexpensive device can be realized. It has become.

[Brief description of drawings]

FIG. 1 is a block diagram showing the principle of the present invention, and FIG. 2 is a DP.
FIG. 3 is an explanatory diagram for explaining the principle of recognizing continuous patterns by matching, and FIG. 3 is an ACD to which the present invention is applied.
FIG. 4 is an explanatory diagram for explaining the P method, FIG. 4 is an explanatory diagram for explaining the concept of the principle of the present invention, FIG. 5 is a detailed explanatory diagram for explaining the details of the present invention, and FIG. FIG. 7 is a processing procedure diagram for explaining the processing procedure of the invention in detail, and FIG. 7 is an explanatory diagram for explaining another example of the constraint condition of the path. 101 ... Feature extraction unit, 102 ... Word standard pattern storage unit, 103 ... Vector distance calculation unit, 104 ... Midway cumulative distance calculation unit, 105 ... Terminal cumulative distance storage unit, 1
06 ... Back pointer storage unit, 107 ... Last word storage unit, 108 ... Voice section detection unit, 109 ... Frame number counting unit, 110 ... Segmentation unit, 112
...... Matching calculation execution range determination unit.

Claims (1)

[Claims] 1. An input signal is characterized by feature vectors a ₁ , a ₂ ,.
a _i, ..., a feature extraction means for converting the series of aI, sequence b ⁿ ₁ feature _{^{vectors, b n 2, ..., b}} n j, ..., b n consists _jn standard pattern ^{R n} (however, n = 1 to N) and a grid graph having the input frame i as the horizontal axis and the frame j of the standard pattern as the vertical axis, and when matching with the standard pattern R ⁿ , the grid graph is used. In the path on the (i-j plane), the distance between the patterns is determined by the dynamic programming method by the matching path in which the sum of the loads along the path always depends only on the length of the standard pattern regardless of how the path is selected. In the calculation device, the features of each frame j of the standard pattern are defined with respect to the grid points of the region sandwiched by straight lines parallel to the standard pattern axis which are W frames apart from the frame of the input pattern. For each of the vectors b ⁿ j, DP matching is performed in the i-axis direction with the width of W in the order of j = 1 to J ⁿ , and when the calculation of one region is completed, the next adjacent region similar to the above And a DP matching means for performing the matching calculation over the entire range of the input pattern such that the above-mentioned calculation is performed.