JPH0247759B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to a pattern comparison device that compares a plurality of registered patterns with an input pattern and identifies the input pattern, and particularly relates to a pattern comparison device that is applicable to recognition of continuously uttered word sounds. In order for voice, which is the most natural means of information generation for humans, to demonstrate its true value as an input means for human-machine systems, it is necessary to be able to recognize continuous normal conversational speech without limiting the speaker. This is desirable. FIG. 1 is a block diagram of a speech recognition apparatus that uses words as recognition units. 1 is the audio signal input terminal, 2 is the input audio signal for frequency analysis, LPC analysis,
An acoustic analysis unit 3 that converts into a series of several sets of numerical values (feature vectors) by PARCOR analysis, correlation analysis, etc. is a standard pattern storage unit in which words to be recognized are registered as a series of feature vectors; a pattern matching unit that compares the series of feature vectors for the input audio signal to be recognized analyzed by the analysis unit 2 with each of the standard patterns and calculates the distance or similarity between the two; 5 is a pattern matching unit; 4 is a determination unit that determines a word corresponding to a standard pattern closest to the input speech pattern as a recognition result based on the calculation result, and 6 is an output terminal that outputs this recognition result. In a speech recognition device having such a configuration, an excellent pattern matching method is a method of performing matching (DP matching) using time-based nonlinear expansion/contraction using dynamic programming. In continuous word recognition using the device of the present invention, this
DP matching plays a central role. Then DP
The matching algorithm will be briefly explained. Now, assume that A = a ₁ , a ₂ ... a _I ... A〓 B = b ₁ , b ₂ ... b _j ... b _J ... (1) as two speech patterns. That is, those speech patterns are represented by a series of feature vectors a _i and b _j for each. When the distance between vectors a _i and b _j is d(i, j), calculate the weighted average of d(i, j) for the various correspondences of the vectors that make up both series, and find the weighted average of d(i, j) that is the minimum The correspondence between the two series is set as the optimal correspondence between the two series, and the weighted average at that time is set as the distance D (A, B) between the two series. This procedure is efficiently performed using dynamic programming. This is DP matching. Note that d(i,j) is usually a vector a _i
The Euclidean distance or city distance of and b _j is used. Figure 2 shows this two-dimensionally.
The time correspondence between patterns A and B, that is, the time conversion coefficient j(i), is given by the grid point c(k) = (i
(k), j(k)) series F=c(1),c(2)...c(k)...c(K)...(2) (i(K)=I,i(k) =J). At this time, D(A, B) is defined as follows. Here, W(k) is a non-negative constant, and its value is determined by the method used to approximate the time conversion function j(i) by a point sequence. Here, if the denominator of equation (3) is a constant M= _K 〓 ^l=1 W(k) that does not depend on F, then D(A, B)
can be efficiently determined using dynamic programming. That is, g(c(k))=min c(1)c(2)...c(k)[ _K 〓 ^l=1 d(c(l)W(l)]=min c(k)[min c (1) c(2)...c(k-1) [ _K 〓 ^l=1 d(c(l))W(l)] +d(c(k))W(k)]=min +d(c( k))W(k)]=min (CK)[g(c(k-1))+d(c(k))W(k)
]...(4), so g(c(1)=g(1,1)=d(1,1)
, solve recurrence equation (4) and get g(c(k))=g(I,
J) is obtained, then D(A, B) is obtained as D(A, B)=1/Mg(I, J)...(5). As a method of constantizing the denominator of equation (3), M=I+
There are two methods: one method is to make sure that J (symmetric type), and the other is to make sure that M=I or J (asymmetric type). FIGS. 3a to 3f show examples of constraint conditions when selecting the point sequence F, and only the route indicated by the arrow in the figure can be taken to reach the point (i, j). Further, the number shown on each line segment indicates the load W(k) when that line segment is selected as the route. For a and b, M=I+J in the symmetrical example, and M=I for c to f in the asymmetrical example. To recognize word sounds using such a matching method, proceed as follows. The word class to be recognized is represented by n (n=1 to N), and its standard pattern is represented by B ⁿ . Input A and each standard pattern B ⁿ
The distance D _o = D (A, B ⁿ ) from the above is calculated using the above method, and the class n ₀ that gives D _o0 = ^min _o (D _o ) is taken as the recognition result for A. If M=I in the asymmetric DP matching, M becomes a quantity that is related only to the input pattern length, and M is constant for any standard pattern in equation (5), so D It can be defined as (A, B)=g(I,J)=min[ _I 〓 ⁱ⁼¹ d(i,j)]...(6). Hereinafter, the distance between patterns will be based on equation (6). Under the constraint conditions shown in Figure 3 c, the formula
To obtain (6), the following recurrence formula (7) can be calculated. g(i,j)=d(i,j)+ming(i-
1, j) [g (i-1, j-1) g (i-1, j-2)] ...(7) Initial condition g (1, 1) = d (1, 1) Next, continuous words Explain speech recognition. Continuous word speech recognition can be formulated as follows. Let A represent the speech pattern when X words q(1), q(2),...q(x) are uttered consecutively. A=a ₁ , a ₂ …ai…a ₁ …(8) The standard pattern of word q(x) is B _q(x) =b ₁ ^q(x) b ₂ ^q(x) …b ^q(x) When _j …b ^q(x) _Jq(x) …(9), the standard obtained by connecting X words B _q(1) , B _q(2) , …B _q(x) The pattern is =B _q(1) B _q(2) …B _q(x) =b ₁ ^q(1) b ₂ ^q(1) …b ^q(1) _Jq(1) ,b ₁ ^q(2) b ₂ ^q(2) …b ^q(2) _jq(
2) …b ₁ ^q(x)
b ₂ ^q(x) b ^q(x) _jq(x) ...(10) This shows the connection of patterns. Therefore, in continuous word speech recognition, DP matching is performed between this and the input speech pattern A, so that the obtained D(A,) is minimized.
The problem is to determine X and q(x) (x=1, 2, ..., x). That is, T= ^min _X,q(x) [D(A,B _q(1) B _q(2) …B _q(x) ]
…(11) and find the conditions that minimize T.
If we attempt to properly perform the calculation of equation (11), a huge amount of calculation will be required. That is, if the maximum number of consecutively uttered words in the input speech pattern is k and the number of word standard patterns is N, calculations will be performed N ^k times. Therefore, in reality, this problem is reduced to the problem of solving the following recurrence formula. In the input speech pattern A, the partial interval from i=l+1 to i=m is converted into the partial pattern A(l,
Defined in m). A(l,m)=a _l+1 a _l+2 ...a _n ...(12) At this time, if the distance between the patterns is defined by equation (6), the following can be said. D (A, B ₁ B ₂ ) = min m [D (A (o, m) , B ₁ ) + D (A (m, I), B ₂ )] ... (13) Using this, the formula ( 11) can be solved as follows. The meanings of the symbols used hereinafter are summarized in Table 1.

_[ Table] _{When the} number of _input ^words , _B From the last word name and segmentation result to the first word name and segmentation result are found sequentially. When _{the number of} ^{input words} ]
...(15) N(i)=n, B(i)=m (n, m are n and m that satisfy equation (15)) From the solution of the recurrence formula, the recognition result is obtained according to the flowchart in Figure 5. is found. The problem with calculating equations (14) and (15) is (a) the small amount of calculation. (b) The required storage capacity should be as small as possible. (c) It must be a real-time algorithm. It is. Regarding (a), the main calculations to find the solution are mainly D ⁿ ₀ (s:t) and d ⁿ (i, j) necessary to find this. In particular, each frame is usually
It is expressed by parameters with more than 10 dimensions, and the problem is how to reduce the amount of calculation. Next, the conventional calculation method is 2.
The step DP method will be explained. The two-stage DP method first sets D ⁿ ₀ (s:t) to any s,
Find the combination of t by DP, then D
It is a method to obtain (i) using DP, and is characterized by having two stages of DP. A forward algorithm and a backward algorithm have been proposed as this two-stage DP method, but the backward algorithm will be explained here. For frame i-1 of the input pattern, D
It is assumed that (i-1), N(i-1), and B(i-1) have been found. The standard pattern of word n (n=1, 2, . . . , N) and the input pattern are DP matched in reverse time direction starting from i ₀ . Therefore, the constraint conditions for the path are as shown in Fig. 7, corresponding to c, d, e, and f in Fig. 3.
Figures a, b, c, and d are shown. The matching range is
Although it is conceivable to perform this with the matching window width R, here it is assumed that the adjustment is performed with an inclination in the range of 1/2 to 2 (within the inclination limit, the shaded area in FIG. 6). This matching is performed with the termination free, and as a result, D ⁿ ₀ (s:
i) is found. However, i−2J ⁿ +1si
−(1/2)J ⁿ . Find D(i), N(i), and B(i) in equation (15). Return to i=i+1. This method requires calculating the interframe distance d and the cumulative distance D within the matching range for each word for each input frame. Therefore, the total number of calculations is N・I・for both the interframe distance d and the cumulative distance D.
3/4J ² (when the matching window width R is N・I・J・
R). The above is the two-stage DP matching method, but the drawback of this method is that it still requires a large number of calculations.
The reason is that for each word in each input frame 3/
4J This is to calculate d and D ^twice . On the other hand, the simplest method for reducing the number of calculations is to save all the values of d once calculated until they are no longer needed. However, with this method, the amount of calculation for d is N.I.J, but the amount of storage required for this calculation is quite large. Moreover, with this method, it is necessary to change the storage address of the calculation result of d for each input frame. The present invention eliminates the above-mentioned drawbacks, significantly reduces the amount of calculation required when comparing an input pattern and a standard pattern without significantly increasing the amount of memory, and provides a pattern comparison device with high calculation speed. purpose. In order to achieve this object, the present invention performs the backward algorithm of the two-stage DP method at regular intervals.The principle of the present invention will be explained below with reference to FIG. In FIG. 8, the shaded area indicates an area where d is calculated at one time (hereinafter referred to as area A). This area A is a W×J area (hereinafter referred to as area B) shown in the hatched area in FIG. 6 (hereinafter referred to as area B).
(referred to as area C). W
is the number of frames, and the calculation of d is thereafter performed by shifting by W frames. In this way, the amount of calculation for d is only J ² +W/2J on average for each W frame, and this is performed I/W times for the number of frames I of the input pattern, so the total amount of calculation for d is N・It becomes IJ (1/2 + J/W). Embodiments of the present invention using the above principle will be described below with reference to the drawings. FIG. 9 is a block diagram showing an embodiment in which the pattern comparison device of the present invention is applied to a speech recognition device. In the figure, 1 is an input terminal for audio signals, and 2 is an acoustic analysis unit that converts the input audio signal of continuous words into a series of feature vectors and outputs them as input patterns A=a ₁ , a ₂ . . . a _I. Let I be the length of the input pattern output from this acoustic analysis section 2. That is, the input pattern consists of I frames. 3 is a series of feature vectors in which the words to be recognized (number of words N)
In _the standard pattern storage unit, ^the standard pattern is stored as B ⁿ =b ₁ ⁿ b ₂ ⁿ . The acoustic analysis section 2 and standard pattern storage section 3 are similar to those shown in FIG. 7 is a DP matching unit, which includes an interframe distance calculation unit 7a that calculates the interframe distance d ⁿ (i, j) between the standard pattern feature vector b ⁿ _j and the input pattern feature vector a ₁ ; d ⁿ (i,
j) and the interframe distance d ⁿ (i, j) stored in this interframe distance storage 7b, the input pattern of word n and frames i' to i is determined. The partial distance D ⁿ ₀ (i′:
It is composed of a partial distance calculation section 7c that calculates i). 8 is a matching start frame setting unit that provides matching start frame information to the interframe distance calculation unit 7a and partial distance calculation unit 7c in the DP matching unit 7, and the start frame i ₀ has an initial value of 1.
From then on, values are set for each W frame, such as W+1, 2W+1, . . . 9 is the partial distance calculated by the partial distance calculation unit 7c
This is a partial distance storage unit that stores D ⁿ ₀ (i′:i).
However, n=1, 2,..., N, i=i ₀ , i ₀ +1,
..., i ₀ +W-1, i' is i-2J ⁿ +1i'i-1/2J ⁿ
is within the range of 10 calculates the minimum cumulative distance D(i) of the word string ending at frame i of the input pattern from the partial distances stored in the partial distance storage unit 9, i=i ₀ , i ₀ +1,
…, i ₀ +W−1, and this D
(i) from the last word N(i) of the word string ending in frame i, and from the starting frame of this word N(i)
This is a cumulative distance calculation unit that calculates B(i) indicating the frame from which . 11 is D(i) calculated by the cumulative distance calculation unit 10,
This is a cumulative distance information storage unit that stores N(i) and B(i). However, i=i ₀ , i ₀ +1,..., i ₀ +W−i, i ₀
=1, W+1, 2W+1,..., LW+1,
L=[(I-1)/W]. Note that [X] represents the integer part of X. Reference numeral 12 indicates a back pointer B(), B indicating the word boundary of the input continuous words at the time when the calculation of the cumulative distance to the final frame I of the input pattern is completed.
(B()),…,B(B((…B(B())…))
), 0
This is a segmentation unit that calculates the following in reverse order starting from the last frame. Reference numeral 13 denotes a word determining unit which sequentially reads words ending in the relevant boundary frame from the cumulative distance information storage unit 11 based on the back pointers determined by the segmentation unit 12 and uses them as recognized words. The operation of this embodiment will be described below with reference to FIGS. 8 and 9. When the input pattern is output from the acoustic analysis section 2, the interframe distance calculation section 7a starts calculating the interframe distance d ⁿ (i, j) between the feature vector of the standard pattern and the feature vector of the input pattern. The range in which this calculation is performed is the shaded area A shown in _FIG .
W + 1, ... and each time the width of W is changed sequentially, W
Move by the width of . Inter-frame distance d ⁿ (i, j), partial distance D ⁿ ₀ (i′:
i) Since the minimum cumulative distance D(i) is calculated using the same procedure for each area A, only the starting frame i ₀ will be described below to simplify the explanation. The interframe distance d ⁿ (i, d) is sequentially calculated for N words stored in the standard pattern storage section 3. This calculation is performed within area A. Note that the area A changes depending on the standard pattern length J ⁿ . For example, for the first word (n=1), point (i ₀ , J ⁱ ), point (i ₀ −2J′+1,1), point (i ₀
+W-i, J ¹ ) and the point (i ₀ +W-1/2J ¹ , 1) are connected to form an area A ₁ . Therefore, for n=1, the interframe distance d ¹ at each point in the area A ₁
(i,j) is calculated. Similarly, n=2,
For n=3,...,n=N, interframe distance d ²
(i, j), d ³ (i, j), ..., d ^N (i, j) are calculated. Note that the calculation of d ⁿ (i, j) is D ⁿ ₀ (i′:i)
This is done alternately with the calculation of That is, when the calculation of the interframe distance d ¹ (i, j) for n=1 is completed,
Next, the partial distance D ₀ ¹ (i′:j) is calculated. The partial distance D ₀ ¹ (i':j) is calculated based on the inter-frame distance d ¹ (i:j) determined previously.
In other words, the partial distance is from the starting point i = i ₀ , j = J ¹ ,
Routes are sequentially selected within the region _A1 and under the constraint conditions shown in FIG. Which of the three routes based on the constraint condition is selected is the route that minimizes the sum of the inter-frame distances on the route at the point immediately before reaching the point. As described above, starting point i=i ₀ , j=J ¹
Thus, the route to the end point i=j', j=1 is determined, and the partial distance D ₀ ¹ (i':i ₀ ) is calculated. In addition,
i′ has a value in the range of i ₀ −2J ¹ +1i′i ₀ −1/2J ¹ . The partial distance when this (i ₀ , J ¹ ) is the starting point
D ₀ ¹ (i′:i ₀ ) is stored in the partial distance storage section 9. Similarly, (i ₀ +i, J ₁ ), (i ₀ +2, J ₁ ),...
^{Partial distance D 0 1} _{( i} ′:i ₀ +
1D ₀ ¹ (i': i ₀ +2), . . . , D ₀ ¹ (i': i ₀ +W-1) are calculated and stored in the partial distance storage section 9. Next, for the second word (n=2), the interframe distance d ² (i, j) is similarly calculated, and the partial distance D ₀ ² (i':i) is calculated. Thereafter, calculations are made in the same manner up to the Nth word (n=N), and the partial distances D ₀ ² (i':i), . . . , D ₀ ^N (i':i) are stored in the partial distance storage section 9. Next, the minimum cumulative distance D(i) of the word string ending at frame i of the input pattern is calculated by calculating the cumulative distance using the partial distance D ⁿ ₀ (i′:i) stored in the partial distance storage unit 9. It is found in section 10. That is, the cumulative distance calculation unit 10 calculates the partial distance D ⁿ ₀ (i':i) between the input pattern of frames i' to i and the standard pattern of word n, and the frame i'-1 of the input pattern.
and the minimum cumulative distance D(i':1) of the word string ending at , and the minimum cumulative distance D(i) with respect to n and i' of the sum. The cumulative distance calculation unit 10 converts the D(i) into frame i of the input pattern.
This is stored in the cumulative distance information storage unit 11 as the minimum cumulative distance of the word example ending in . Further, the cumulative distance calculation unit 10 calculates that when n and i are respectively n and i' when calculating the D(i), N(i)=n, B(i)=i'-1
The recognition candidate word N(i) and the back pointer B(i) indicating the word boundary are stored in the cumulative distance information storage unit 11 together with D(i). DP matching section 7 and cumulative distance calculation section 10
The above processing in is repeated every time the matching start frame setting section 8 changes the start frame _i0 . The matching start frame setting unit 8 sets a start frame corresponding to the final frame I of the input pattern, and the cumulative distance calculation unit 10 calculates D(i), N(i), B for the area A defined by this start frame.
After (i) is determined and stored in the cumulative distance storage unit 11, the segmentation unit 12 performs processing to determine the word boundaries of the input word string. This process first reads B(i) in frame I, that is, B(I), from the cumulative distance information storage unit 11, and then calculates B(i) in frame B() based on the read value of B(). That is, B (B()) is read out from the cumulative distance information storage section 11. Below, B(B
(B()),…,B(B(B(…B(B())…)
)),
0 is read. Note that 0 means the frame one frame before the input start frame of the input pattern. B(i) read by the segmentation unit 12 as described above is input to the word determination unit 13. The word determining unit 13 reads N(i) from the cumulative distance information storage unit 11 based on this B(i). That is, initially the word N() that ends in the final frame I is written as
The next word N(B()) ends in the B() frame.
Similarly, N(B(B())),...N(B(
B
Read out (B(...B(B())...)))). This read word N(i) is output from the terminal 6 as a recognition result. FIG. 10 shows a flowchart when the functions of the apparatus shown in FIG. 9 are realized by software. In the figure, steps 100 to 102
is the part that sets the initial value of the minimum cumulative distance.
Steps 105 to 107 are the parts for calculating the distance between frames, and steps 108 to 11
4 indicates a portion for calculating partial distances, and step 104 indicates that these are performed for all words. Steps 115 and 116 are steps for determining the minimum cumulative distance, recognized words, and word boundaries.
Step 103 is similar to Step 104 to Step 1.
16 is repeated every W frames. Steps 117 to 120 are steps in which, after the recognized words and word boundaries up to the final frame I have been determined, the word boundaries and recognized words are determined in reverse order from the final frame. FIG. 11 shows a flowchart of an embodiment in which the number of input words is known (X) and is realized by software. Each step is almost the same as in the case where the number of input words is unknown as shown in FIG. The difference is that when calculating the cumulative distance, we assume the number of input words up to that frame, calculate the cumulative distance D _x (i) for each number of words, and calculate the number of recognized words N _x (i) and word boundaries. This is the point to find B _x (i). In this case, the amount of calculation increases according to the value of X, and the recognition accuracy improves. In the embodiment shown in FIG. 9, D(i)
is obtained after calculating D ⁿ ₀ (i':i) for all n=1 to N, but it may be obtained for each n. FIG. 12 shows a flowchart of this embodiment implemented by software. This flowchart differs from the flowchart of FIG. 10 in steps 115' and 116'. By changing the steps in this way, the memory required to store the partial distances D ⁿ ₀ (i:i) required to calculate the cumulative distance D(i) can be significantly reduced. Further, in the embodiment shown in FIG. 9, the recognition candidate words N(i) stored in the cumulative distance storage unit 11 were only those corresponding to the minimum cumulative distance D(i); Recognition candidate word (hereinafter referred to as next recognition candidate word N'(i)) corresponding to the next smallest cumulative distance of D(i) (hereinafter referred to as next minimum cumulative distance)
may also be stored in the cumulative distance information storage unit 11. In this case, the word determining unit 13 reads N from the cumulative distance information storage unit 11.
Based on (i) and N′(i), various recognized word sequences are output as recognition results. As a recognized word string,
Using only N(i) (same as the recognition result in the example of FIG. 9), word 1 of the N(i) word string
Various options are possible, such as replacing N'(i) with N'(i), or replacing two words. In this case, the word determining unit includes a memory unit that stores N(i) and N′(i), and a selective readout unit that selectively reads N(i) and N′(i) from this memory unit. It can be composed of two parts. In addition, the area A shown in Figure 8 was used as the range for the matching calculation, but area B of this area A
The part corresponding to is surrounded by the broken line in Fig. 6, and the width R
area (hereinafter referred to as area)
B′), and as a new area A, the area
The area may be obtained by shifting B' by W frames. Setting such areas requires the required recognition accuracy,
This is done taking into consideration calculation speed, etc. By the way, if the starting point of the matching calculation is frame i ₀ , the most appropriate position for the ending frame is considered to be near the starting point frame i ₀ by a frame length corresponding to the standard pattern length J _o , and the area A
Settings are also made based on these. Therefore, the position of the end frame is generally given as a function of the standard pattern length J ⁿ . In other words, the starting frame is i ₀ ,
If the end frame is i′, then i ₀ +R ₁ (J ⁿ )i′i ₀
+R ₂ (J ⁿ ). In area A, the starting edge changes in the range from starting frame i ₀ to frame i ₀ +W-1, so the ending edge i' is
i ₀ +R ₁ (J ⁿ )i′i ₀ +R ₂ (J ⁿ )+W. As described above, the pattern comparison device of the present invention is configured to set the starting frame i ₀ of matching calculation for each W frame, and to collectively calculate d(i, j) for the pattern comparison area determined for each W frame. Therefore, compared to a pattern comparison device using the conventional two-stage DP method, the interframe distance d(i, j)
The number of calculations can be significantly reduced. For example, when J=30 and W=10, 3/4NIJ ² /NIJ (1/2+J/W) = 3/4J/(1/2+J/W)≒6.4, and the number of calculations is approximately 1/6th. . On the other hand, the amount of memory increases by only 40%, as (3/4J ² +WJ)/3/4J ² =1+3/4·W/J≒1.4.

[Brief explanation of drawings]

Fig. 1 is a block diagram of a conventional speech recognition device, Fig. 2 is a diagram showing the correspondence between feature vectors of patterns A and B, and Figs. FIGS. 4 and 5 are diagrams showing examples of constraint conditions, and FIGS. 4 and 5 are flowcharts showing the segmentation and recognition word determination procedures in continuous word speech recognition when the number of input words is known and unknown, respectively. FIG. is an explanatory diagram of the backward algorithm of the two-stage DP method; Figures 7a to d are diagrams showing examples of constraint conditions when selecting grid points on the i-j plane; Figure 9 is a block diagram of one embodiment of the present invention, Figure 10 is a flowchart of software that realizes the functions of the device of the same embodiment, and Figures 11 and 12 are flowcharts of other embodiments. . 1...Acoustic analysis section, 3...Standard pattern storage section, 7
... DP matching unit, 7a... Inter-frame distance calculation unit, 7b... Inter-frame distance storage unit, 7c... Partial distance calculation unit, 8... Matching start frame setting unit,
9... Partial distance storage section, 10... Cumulative distance calculation section, 1
1... Cumulative distance information storage section, 12... Segmentation section, 13... Word determination section.

Claims (1)

[Claims] 1. Feature extraction means for converting a continuous pattern input signal into a time series A=a ₁ , a ₂ ...a _I of feature vectors a _i ;
Standard pattern B ⁿ = b ⁿ ₁ , b ⁿ ₂ ... b ⁿ Jn (n = 1, 2,
..., N), and a standard pattern storage means for storing J ⁿ
In a lattice graph where the minimum value for n is Jmin, the horizontal axis is the input pattern, and the vertical axis is the standard pattern, when the maximum slope of the matching path is S _nax and the minimum slope is S _nio , W≦J _nio /S _nax For W,
a _{matching start} frame setting means for setting a starting frame ⁱ ₀ of matching calculation for the time series A every W frames ^; ), (i _p +W-1,
1), the inter-frame distance d ⁿ (i, j) of the feature vectors of the standard pattern and the input pattern only for the grid points within the trapezoid surrounded by (i _p −J ⁿ /S _nio , 1)
an inter-frame distance calculation means that calculates each time the start frame i _p is set; and an inter-frame distance calculation means that calculates the inter-frame distance d ⁿ (i,
j), reads out the interframe distance stored in the interframe distance storage means, and generates a partial input pattern and a standard pattern B ⁿ with frame i as the starting point and frame i' as the ending point. A partial distance calculating means for calculating a partial distance D ⁿ o (i':i) between D ⁿ o ( i': partial distance storage means for storing i);
The sum of the cumulative distance D (I'-1) to frame i'-1 and the partial distance D ⁿ o (i':i) is minimized for i',n, and as a result, the cumulative distance D (I'-1) to frame i is i), and N(i)=n and B(i)= for the cumulative distance D(i) and the n and i' used in calculating the cumulative distance D(i); i'-1, and when the calculation of the cumulative distance to the final frame I is completed, the cumulative distance information stored in the cumulative distance information storage means is B(i) to B(), B.
(B()),...,B(B(...B())...), O, that is, segmentation means for obtaining boundaries of consecutively input patterns in reverse order; B(), B(B
Using ()),…,B(B(…B())…),O,
From the cumulative distance information storage means, N(), N(B()),..., N(B(...B()
))
...), and pattern determining means for determining ...) in reverse order.