JPS58162995A - Pattern analogy calculator - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a pattern similarity calculation device that calculates the similarity between two patterns, and is based on calculating the similarity between a standard pattern known in advance and an unknown input pattern. The purpose of this method is to pattern recognize this unknown input pattern.

This 11-layer similarity calculation device is mainly used for recognition processing of patterned speech and character information, and in particular when dealing with speech patterns, the expansion and contraction of the time axis is important. It is necessary to remove fluctuations in speech patterns caused by noise, and it has been proposed to use a dynamic counting method for this purpose.

A pattern similarity calculation method using such a dynamic needle method will be explained using a voice pattern as an example. As a voice pattern, for example, a time series with frequency spectrum values as parameters is used, but as shown in Figure 1, even in the voice pattern of the voice "Sakura", the time axis expands and contracts non-linearly depending on the utterance state. , Therefore, the parameter 15 and bs between the voice pattern A with 8 sequences and the voice pattern S with 9 sequences
, and since a6 and b6 no longer belong to the same phoneme, d3
The error between and b3, the error between 16 and b6, and the error between 0 and b9 become extremely large.

Therefore, as shown in FIG. 2, there is a need for a combination 111 (i, j) of each parameter mi, bj between both patterns A%B, and the means for this purpose is dynamic programming.

According to such dynamic programming method-ζ, at the same time as detecting the above-mentioned optimal corresponding path P, the integrated value S of the error d between each parameter mi and bj of both patterns A and B located on this optimal corresponding path P is calculated. is determined, and the degree of similarity between both patterns A and B is calculated based on this minimum error integrated value S. Specifically, the second
As shown in the figure, the optimal corresponding path P is the point X at coordinates (1, 1)
The following recurrence formula is calculated, assuming that the starting point is the point Y with coordinates (8, 9) and the ending point is within the range limited to the extreme non-zero coordinates (i, j). .

S (1, 1) = d (1, 1) where d (i, j) - 1 turtle 1 - bjl In other words, if we focus on the coordinates (4, 3) point a number of the younger brother 2 figure, the integration Value S(4,
3) is the integrated value S(4,2) at the coordinate (4,2) point A, the integrated value S(3,3) at the coordinate (3,3) point, and the integrated value S(3,3) at the coordinate (3,3) point
, 2) The minimum value among the integrated values S(3, 2) at Al, for example, Si, 2) K is the sum of the error d(4, 3) at this point A. The same calculation process has already been performed on each of the 41 points 0Al, and the integrated value S(3,2) at Al is the product jE value s(3,2) at the coordinate (3,1) point O.
, 1), seat 11 (2, 2) point force teno integrated value S (2, 2)
, and the minimum value of the integrated value S(2,1) at the coordinates (2,1) point K, for example, the error d(5,2) at this Al is added to the integrated value S(2,1). It is something. In addition, regarding the derivation of the integrated value S (4, 2) at the above point A,
1) Since the point deviates from the preconditions of the coordinate range described above, the integrated value S(3,2) at Al and the integrated value S(3, 2) at point O.
, 1), and the error d(4, 2) at this point A is added to the smaller value of the two. Then, the integrated value S (2, 1) at point K is the integration value of the starting point This is the value S(1,1), that is, the error d(1,1) plus the error d(2,1) specific to this point. Thus, the minimum error integrated value S(4,3)' at point A with coordinates (4,3)'
) ends up being S(4,3)-d(1,1)+d(2,1)+
d(3,2)+d(4,3), and as a result, it is found that the optimal route q from the starting point X to point A passes through points K and A.

Similarly, among the combination coordinates (i, j) of the customer parameters *i, b j of both patterns A and -f shown in FIG. 2, for all coordinates indicated by white circles and black circles, i and j
If su, t) are calculated sequentially from the smallest one, 8 (8, 9) is finally obtained, and as a result, the optimal corresponding path P
It turns out that the smaller the value of 8 (8, 9), the higher the similarity between these two patterns A and l.

As shown in FIG. 3, this conventional type similarity calculation device has upper and lower register groups R1, 1L2, and the upper register group has 1 as the standard pattern person's parameter a1. Turtle 2...
, the first corresponding to each number of tortoise shells. 1st 2. ...8th register r11. r12. , rllll and an attached register r10, and the lower register group R2 is also composed of the first . Second. ..., 8th register r 21 , rzz
In the initial state before calculation processing, the maximum storable value - is written in all registers of these register groups R1 and R2. In the first step of the calculation process, as shown in FIG. 4, the integrated value S(1,
1), the integrated value 8 (2, 1) in the second register X l r 12
Ili3 register xs6r - integrated value S (5, 1) h<
New f = sc is written, and after this, the contents of the upper register group R are saved to the lower register group IL (f').In the second step, the attached register of the lower register group IL2 at this time is The integrated value S (which is forced to become the minimum value depending on the value Z of r20, the value Z of its second register r12, the value Z of the genus register r10, and the minimum value among them, that is, the two maximum values -)
1, 1) is selected, and the integrated value S(1, 2) is derived by adding this value number error d(1, 2), and the upper register group R
It is stored in the first register r11. Following this, the two integrated values S, S stored in the lower register group [2 and the upper register group IL depending on the previous calculation process]
Each integrated value S(2,2), S(
3,2), S(4,2) are sequentially derived, and each register r12 . r13. r14 is sequentially derived, and then all the contents of the upper register group R1 are saved to the lower register group R2.

In this way, the calculation processing in the third to ninth stages J is executed in the same way, and the upper and lower register groups IL1 and IL2 are sequentially translated in four directions from the parameters b1 to b9 of the input cover turn B, Finally, the minimum accumulated error value S(
8, 9) can be stored.

What is important in such calculation processing is that in order to satisfy the restriction conditions of the optimal correspondence path, for example, in stage II5, the second register R12 of the upper register group R1 contains the integrated value S(2 ,5)=S(2,4)+d(4:2
．． -1rs) must be forcibly written to the maximum value -. That is, in order to calculate the value S(3,5) to be stored in the third register r13 of the upper register group Mouse 1 based on this, the second register of the lower register group R2 is r2
2(F) integrated value S(2,4)<- and third register pr'
1stv integrated value S(3,4)<-, the minimum value of (2) is selected, and it is possible to avoid selecting the value - of the second register r12 of the upper register group IL1. Therefore, for example, parameter a2 of standard pattern A and input cover pattern B
This means that extreme non-edge correspondences with parameter b5 will be excluded.

However, for the reasons mentioned above, in the fourth step,
The second register r12 of the upper register group IL1 is written, and in the fifth step, the second register r12 is written.
2# In the sixth step, the third register r15 is
In the seventh step, the fourth register r14 and the eighth
In the step, the maximum value - is stored in the fifth register r15.
Writing such a similarity complicates the calculation process and causes a decrease in calculation speed.

Furthermore, in the conventional apparatus as described above, each parameter IL112 of the standard pattern A having 8 series, for example,
The first one corresponding to aa4ζ. Second. ...Although the upper and lower register groups including the 8th register are fixedly provided,
Each parameter b1, b2 of the input cover turn B. ...b9
The number of sequences is not always limited to, for example, 9, and may increase or decrease depending on the length of time that occurs each time the voice fades. Therefore, if the number of series of parameter b of input cover turn B is, for example, 7, the number of calculation steps described above is only 7, but as the number of series increases, the number of calculation steps also increases. In this case, the calculation speed will further decrease.

The present invention has been made in view of the above-mentioned benefits, and provides a similarity calculation device that simplifies calculation processing.

FIG. 5 shows the configuration of an embodiment of the similarity calculation device of the present invention. (1) is the standard pattern person's eight parameters a1.
a2. ..., standard pattern memory storing 18, (
2) is the nine parameters b1. of input cover turn B. b2.
・, b9 is an input pattern memory that stores parameters, and in this case, a maximum of 10 series of parameters can be stored. (3) is an error calculation circuit that calculates the standard pattern memory (1) for each switch F1, F2 . ..., each parameter ml obtained via Fa and the input pattern memory (
2) to each switch G1, G2 . ..., G? Each parameter bj obtained through
is calculated.

(4) is a register group, and as shown in FIG. 6, among the combination coordinates (i, j) of each parameter xi, bj of both patterns A%B, 1=j-n (however, n=1. 2.
・,8) The central register (goods) corresponding to the combination Z coordinates (n, n) and the combination coordinates (n+1, n), (n+2
．． the first and second horizontal registers (42, 42, n) respectively corresponding to
- and the attached horizontal register (anchor and combination coordinates (n, n-H), (n, n
+z), respectively. It consists of a second vertical register, -, and a corresponding attached vertical register for combination coordinates (n, n+3). (5) is a minimum value detection circuit, and is a Switches W1.W1.Wl, W2, W2, W2, - from inside
, Ws.

The minimum value is selected and outputted from among the three input values input via either Ws or Ws.

(6) is an adder, which obtains a minimum error integrated value by adding the error value obtained from the error calculation circuit (3) to the minimum value from the minimum value detection circuit (5). This value is then used for switches W1, W2. . . . An attached horizontal register (an trowel and an attached vertical register (equipment) that is input to the register group (4) through one of the Ws and always holds the maximum value ~
Any register except 啜1 (transfer), 啜.

(c) The contents of va are rewritten.

Next, the operation of the apparatus of the present invention will be explained with reference to FIG. First, the central register (6) of the register group (4) is set to 0.
Write and write each remaining register (transfer), ..., (capital)
Write the maximum value that can be stored in these registers in , and in the first step number switch W1
．． W1. W1. By closing the minimum value detection circuit (
5) is the value 0 of the central register (sha) and the first horizontal register (sha)
The error calculation circuit (3) outputs the minimum value 0 between the value of the first vertical register (a) and the first vertical register (the value of a), and at the same time closes the switches F1 and G1. 1,
1), and in the adder (6), this error d(1,1)
The sum d(1,
1), that is, the integrated value 8(1,1) is derived. The integrated value S (1, 1) thus obtained is changed to ? in FIG. 6 by closing the switch W'1. As shown in , a new write is made to the central register. Then, switch W2.
2, W2. By closing F2 and G1, the error d(2,1) from the error calculation circuit (3) is added to the integrated value S(1,1) from the minimum value detection circuit (5) (6
); S(1,1)+d(2,1), that is, the integrated value S(2
, 1) is obtained, and by closing switch W2, this value is newly written to the first horizontal register, as shown by mouse 0 in FIG.
, Ws , F3 , G1゜By closing Ws, S
C2,1>+dC5°1), that is, the integrated value S(3,1) is calculated and newly written to the second horizontal register.

Furthermore, sweet Jchi Wa, Wa, Wa, F 1
．． G2.

Depending on the car number that closes W4, S (1, 1) + d (1゜2
) That is, the integrated value S(1,3) is calculated, and this value is newly written to the first vertical register (to) as shown by ■ in FIG. 6, and then the switch Ws.

Ws, Ws, F1. By closing Gs and Ws, S(1,2)+d(1,5), that is, the integrated value S(1,
3) is calculated and newly written to the second vertical register ((transfer).

Thereafter, the calculation processing of steps 2 to 8 is performed sequentially, but taking the second step as an example and referring to FIGS. (transition), (0, 1st and 2nd vertical register (to) #
mI already has integrated values s (1 n convex), 1), S (2, 1), 51.1), 5 (1°)"
2), S (1, 5) are stored, and the maximum value - written in the initial state before calculation processing is stored in the attached horizontal register (4IA) and the attached vertical register (material). First, Switch W1.W1.W1, F2,
G2. By closing Wl, as shown in FIG. (
The minimum error integrated value 8(2,2) is obtained by adding the minimum value of the three integrated values S(2,1) of
, 2), and this value is newly written to the central register (41) as shown in FIG.

F3. G2. Closing Wl - Therefore, Figure 7 (II
), the integrated value S(2,2
) The minimum value of the three, the integrated value S (2, 1) of the first horizontal register, the integrated value S (3, 1) of the second horizontal register (43), and the error d (3, 2), A minimum integrated value S (2, 3) is calculated by adding the values, and this value is newly written to the first horizontal register (0) as shown in the figure (-).

Next, switch W3, Ws, Ws.

By closing p 4 , G 2 , and Ws, the integrated value s(3,2) of the first horizontal register (42) and the integrated value S(
3,1) The minimum value of the three attached horizontal registers (the maximum value of the trowel -), that is, the values S(3,2), S( Depending on the car number, the standard pattern is calculated to calculate the minimum error integrated value S (4, 2), which is obtained by adding the minimum value of the three inner values of 5, 1) and the error d (f, 2). Excluding the extremely non-linear correspondence between the person's parameter 4 and the parameter b1 of the input turn B, this value S(
4, 2) is newly written to the second horizontal register @ as shown in FIG. 7 (lvllc).The attached horizontal register continues to hold the maximum value -.

Furthermore, switches W4, W4, W4, F2,
Gs.

By closing W4, the minimum error integrated value S(2,3
) is calculated, and this value is newly written to the first vertical register (to) number ζ, as shown in (V) of the same figure. By closing the last part, as shown in Figure 7M, the figure (1)
As in the case of , the value S(
1,3), S(2,3) and the error d
(4, 2) and the minimum error integrated value S(2, 4
), we exclude the extreme non-linear correspondence between the parameter 1 of the standard pattern person and the parameter b4 of the introvert island, and calculate this value 8 (2, 4) as shown in the same figure (vile
ζ As shown, a new [11] is stored in the second vertical register @.

Note that the attached vertical register (capital) continues to hold the maximum value -. Thus, the calculation process in the second step is completed, and the calculation process in the sixth step is completed.
As shown at t in the figure, the register group (4) is in a state where each integrated value is stored, and from then on, the calculation process similar to the above-mentioned second step is repeatedly executed until the eighth step. As shown by the dashed arrow, each step register group (
4) translates the coordinates (i, j) in the direction in which both 1 and j are large.

Next, the calculation processing in the seventh step and the eighth step, which is the final step, will be described. In the seventh step, as shown in FIG. , 7) should be stored, but the ninth parameter a9 does not exist in the standard pattern person.

Therefore, the value ? actually stored in this register (41) has no meaning, but this value ? is used in the 8th step when the number of series of parameters xi of the standard pattern person is 8, and the input cover pattern B Since the number of sequences in is 9, the coordinates (8, 9) of the end point Y of the optimal corresponding path shown in Fig. 2 I [the corresponding minimum error integrated value S (8, 9) are The integrated value S(a,
S) are stored and the first and second horizontal registers (43(a
A meaningless value ? is stored in the sequence number ζ second vertical register (a).

Therefore, the j11 vertical register (
The degree of similarity is obtained based on aI and the stored minimum error integrated value S(8,9) number ζ. That is, the smaller this value S(8,9) is, the higher the degree of similarity is.

In the above embodiment, the number of parameter series of the input cover turn B is 9, but if this number of series is the maximum value 10 that can be stored in the input cover turn memory (2),
1! The register group at the 8th step (RO in Figure I6)
4) S(8,10) stored in the second vertical register
Based on this, the similarity between both patterns A and 8 is obtained.

Furthermore, the number of standard pattern series M is the number of input cover turn series N
= value smaller than 8, e.g. 6 for M-7 or M-6
C is stored in the first horizontal register of the register group (4) in the seventh step shown as 10 in FIG.
), or S(8,6) stored in the second horizontal register IaK of the register group (4) in the sixth step, the similarity is obtained based on 4.

In the embodiment described above, the number of sequences of standard pattern A is Nx'8. , and the numbers of horizontal and vertical registers to determine the allowable range of the nonlinear optimal correspondence path were set as xzt and x2, respectively. However, the number of series N of standard pattern A is determined as appropriate depending on the type of parameter. Moreover, the numbers K and L of horizontal and vertical registers do not need to be the same, but these numbers k and L are approximately L=L-1/! It would be appropriate to set it to N.

A bank that performs speech recognition using such a pattern similarity calculation device of the present invention stores a plurality of standard children's voice patterns of recognized speech, and compares each standard speech pattern with a person, "J".
By calculating the similarity with the f voice pattern and detecting the standard voice pattern with the highest degree of similarity, the internal voice at this time can be recognized.

As is clear from the above description, the pattern similarity calculation device of the present invention stores standard and input patterns consisting of N and M parameters, and stores a central register, N horizontal registers, L vertical registers, and registers. Based on the minimum error cumulative value written in the group, the minimum error cumulative value in the next step is obtained, and based on these values, the contents of the above register group are rewritten, and the register group in the final forging step is Since the similarity between both patterns ASB is determined based on the minimum accumulated error value stored in any of the registers, the similarity is determined based on the maximum value that is always stored in the attached horizontal register and the attached vertical register. This not only prevents the appearance of extremely nonlinear correspondence paths, but also eliminates the process of writing the maximum value to a specific register in a register group for each step of calculation processing, which is required in conventional devices. .

Furthermore, the number of steps in the calculation process can be set to the smaller number of sequences M or N between the number of parameter sequences M of input cover pattern 1 and the number of parameter sequences N of standard pattern A, so for example, Even if the number M of parameter series of input cover turn B is larger than the number N of parameter series of standard pattern A, a fixed bias can be obtained in M steps, greatly speeding up the calculation process of such similarity. It becomes possible to convert into

In addition, the allowable range of the unique number ζ nonlinear correspondence path can be determined by the numbers K and L of the horizontal and vertical registers, and the number of registers in the register group can be reduced compared to conventional devices, making it possible to improve the configuration of such a device. It can be simplified.

[Brief explanation of the drawing]

Fig. 1 is a schematic diagram showing the variation of the parameter series of two patterns, Fig. 2 is a schematic diagram showing the optimal correspondence path of the two patterns, and Figs. 3 and 4 are the configuration and diagram of a conventional similarity calculation device. A schematic diagram showing the operation, FIG. 5 is a professional diagram showing the configuration of an embodiment of the pattern similarity calculation device of the present invention, and FIG.
7 and 7 are schematic diagrams showing the operation of the apparatus of the present invention. (1)...Standard pattern memory, (2)...Input pattern memory, (3)...Error calculation circuit, (4)...
・Register group, (5)... Minimum value detection circuit, (6)...
・Addition circuit. Figure 1 Figure 2 Figure 6 (Figure 7 (1) +iv+
July lz, 1980 1, Indication of the case Patent application No. 45418 of 1988 2, Name of the invention Pattern similarity calculation device 6, Person making the amendment Patent applicant Address 2-18 Keihan Hondori, Moriguchi City Name (188) Sanyo Electric Co., Ltd. Representative Kaoru Iue 4, Agent Address Moriguchi Type Keihan Hondori 2 Ryo-me 18-6, Scope of Claims column of the specification to be amended. 7. Contents of the amendment The "Claims of claims" on the 6th line of page 1 of the specification will be amended to read [Scope of claims].

Claims (1)

[Claims] 1) A standard pattern memory in which a standard pattern A-(al, a2.-xi, -, aN) consisting of N parameter sequences is stored in advance, and an input consisting of M parameter sequences. The error d(mi, bj・) and both patterns A above. First parameter h of B 1. Starting point coordinates of bl (1
, 1), the combination coordinates (
1, J), the sum of errors 1d(ai, bj) obtained by the above error calculation circuit at each combination coordinate of both parameters ai, bj existing on that path is the minimum. and the combination coordinate (n, n) of the combination coordinates (i, j) of each parameter xi, bj of both patterns A and B. However, n=1.2. ..., central register corresponding to N, combination coordinates (n+1.0), (n+2, n),...
...(nlL,n), where K (N horizontal registers corresponding to N, an attached horizontal register that always stores the maximum value that can be stored corresponding to the stitching coordinate (n-1+1゜n),
Combination coordinates (n, n+1), (n#n+2)I・5(I
lln+L)l However, a register group ζ consisting of L vertical registers corresponding to L<M and an attached vertical register that stores the maximum value that can always be stored corresponding to the combination coordinate (n, [1+L+1), , and the calculated value at the n-th step 11 of the minimum error accumulating circuit is the value scn+kan)m where lxl, 2. , , K are respectively stored in the above horizontal registers, and L values S(
n, n-1-1) but lxl, 2. ,,,L are each L
The above vertical registers are stored, and the values S(n,
n) is stored in the central register, and in the next (n+1)th step, the minimum error accumulation circuit calculates the values S(n+1 to n+1) based on the multiple values of these register groups.
, L values 8 (n+j, n+1+1), and values S (n
+1, n+1), and calculate the register group at the smaller number N or M step of both the number N of parameter series of the standard pattern A and the number M of parameter series of the cover turn B. Among them, the combination coordinates (N, M) k
The contents of the corresponding central or horizontal or vertical register S(N,
A pattern similarity calculating device characterized by calculating the similarity between both patterns AB based on the value indicated by M).