JPH022159B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an improvement in a pattern matching device that compares patterns expressed as a series of feature vectors, such as voice patterns.

As a pattern recognition method, the pattern to be recognized is registered in advance as a standard pattern, and the unknown pattern input during recognition is compared with the standard pattern.
A pattern matching method that determines the one with the highest degree of similarity as the recognition result has been widely used.

In the pattern matching method, it is important to deal with fluctuations such as fluctuations in speaking rate in the speech pattern, but the time normalized matching method (hereinafter referred to as the DP method) using dynamic programming is extremely effective. (Acoustical Society of Japan Vol. 27 No. 9)
(See pages 483-487) It is widely used in practical applications.
However, this matching method assumes that the pattern to be matched is a time series of feature vectors sampled at a constant cycle, so the storage capacity increases for temporally long audio patterns, and the amount of calculation processing also increases. increase To solve this problem, if there is a stationary part in the voice pattern, such as the vowel part, we can take advantage of this and sample representative vectors non-uniformly. A method of applying the DP method to a series of representative vectors (compressed DP method) has been proposed (Japanese Patent Application No. 1983-032060).

However, in the compression DP method, the amount of data is not compressed in the transitional part where the pattern changes, and the representative vectors are approximated by rectangles, so errors with the original pattern are unavoidable. On the other hand, the original pattern is approximated by a broken line,
By extracting the break point as a representative vector, the amount of data is compressed even in the transitional part where the pattern changes, and the error with the original pattern is also reduced.
Highly accurate matching can be achieved with small storage capacity and processing amount. However, in this case, the representative vector itself does not represent the section with the original pattern, but the line segment connecting adjacent representative vectors represents the section with the original pattern. Therefore 2
When matching two patterns A and B, the conventional compressed DP matching method that uses the distance between the representative vector of pattern A and the representative vector of pattern B cannot be applied.

The present invention introduces the concept of a distance between a line segment connecting two points on a vector space corresponding to two adjacent representative vectors of one pattern and a point corresponding to a representative vector of the other pattern, and calculates the distance. using, 2
Achieved matching of two patterns using the DP method,
The purpose of this invention is to realize a highly accurate pattern matching device with a small storage capacity and processing amount.

Now, when the series of feature vectors of two patterns A and B are each compressed by broken line approximation, the series of representative vectors extracted as break points are respectively A={a(1), ..., a(i), ..., a(I)} B={b(1), ..., b(j), ..., b(J)}, and the series of extraction points of the representative vectors of patterns A and B are respectively P = {p(1), ..., p(i), ..., p(I)} Q = {q(1), ..., q(i), ..., q(J)} . At this time, in the conventional DP method, the distance between patterns A and B is determined as follows.

For the integral g regarding the distance d(i,j) between vectors a(i) and b(j), the initial condition g(1,1)=d
(1, 1), and the recurrence formula g (i, j) = mind (i, j) + g (i-1,
j) d(i,j)+g(i,j-1) 2d(i,j)+g(i-1,j-1) (1) from i=1, j=1 to i=I, j= Repeat sequentially up to J. From the finally obtained g(I, J), the distance between patterns A and B is determined from D=g(I, J)/(I+J-1).

The conventional method has been described above, but in the present invention, instead of d(i, j), a line segment connecting adjacent representative vectors in the representative vector series of one pattern and the representative vector of the other pattern is used. The distances d _A (i, j) and d _B (i, j) are defined as follows.

d _A (i, j) = dist (b (j), a (i - 1) a (i)), d _B (i, j) = dist (a (i), b (j - 1) b ( j))
(2) However, vectors x, y on vector space
dist(a,) represents the distance between the point corresponding to vector a and the line segment. d _A (i, j) and d _B (i, j) are generally 2
Regarding the distance d ₀ between the straight line connecting points x and y and point Z, if a perpendicular line can be drawn from point z to line segment xy, then d ₀ ² =‖x−z‖ ²・‖y−z‖ ² − ｜(x
−z)・(y−z)| ² /‖x−y‖ ² . Also, if a perpendicular line cannot be drawn from point z to line segment xy, ‖x-z‖ and ‖y-z
It is sufficient to define the smaller one among ‖.

d _A (i, j), d _B (i, j) defined by formula (2)
The values obtained for i=1,...,I, j=1,...,J can be made to correspond to each side of the grid on the grid M as shown in FIG.

At this time, with respect to the point (i, j) on the grid M, the integral quantity g (i, j) regarding the distance is set to the initial condition g (1, 1) = 0, and the recurrence component g (i, j) = min w _A (i)d _A (i,j)+g(i-1,j) w _B (j)d _B (i,j)+g(i,j-1) (3) However, w _A (i)=p( i)-p(i-1) w _B (j)=q(j)-q(j-1).

In equation (3), w _A (i) and w _B (j) are the time lengths of the broken lines when the original pattern is approximated by the broken lines, and mean the paths and weights as shown in FIG. Expression (3) as i
= 1, j = 1 to i = I, j = J, and by dividing the finally obtained g(I, J) by the sum of the time lengths of the two patterns before compression, the two patterns A and B are created. The distance of Obtainable.

The apparatus according to the present invention extracts a representative vector from a first pattern A expressed as a feature vector series {a(1), . . . , a(i), . . . a(I)} and a sequence of extraction points {p(1), ..., p(i), ..., p(I)}; The series of representative vectors {b(1), ..., b(j), ..., b(J)} obtained by extracting representative vectors from pattern B of 2 and the series of extraction points {q( 1), ..., q(j), ..., q(J)} and the specified i, j
The representative vector a(i+1) in vector space for
The distance d A (i, j) between the line segment connecting and _a (i) and the point corresponding to the representative vector b(j) and the representative vector b(j
+1) and b(j) and the point corresponding to the representative vector a(i), a distance calculation unit that calculates the distance d _B (i, j), and the distance d _A (i, j) correspond to the edge connecting point (i, j) and point (i+1, j) of the grid of time points of I×J, and let d _B (i, j) correspond to the point (i, j) and point (i, j+1). ); and a distance storage section that stores at least the required number of distance information having a grid structure obtained by sequentially changing i and j when associated with the edges connecting the points of the grid; an integral quantity storage unit that stores at least a required number of integral quantities g; and an integral quantity g at each point of the grid;
It includes a recurrence formula calculation unit that calculates the weighted sum of the past integral quantity stored in the integral quantity storage unit and the past distance stored in the distance storage unit for a plurality of combinations, and calculates the result as a subtracted value. consists of i=1, j=1
The method is characterized in that the distance between the patterns A and B is calculated by sequentially changing i and j from i=I to j=J.

The principle of the present invention will be explained below with reference to the drawings.

FIG. 3 is a block diagram showing one embodiment of the apparatus according to the present invention.

The first vector storage unit 1 stores the representative vector sequence {a(1),..., a(i),...a(I)} and representative vectors of the first pattern A obtained by compressing it by broken line approximation. The sequence of extraction points {p(1), ... p(i), ..., p
(I)} is stored. The second vector storage unit 2 stores the representative vector sequence of the second pattern B {b(1),...,
b(j), ..., b(J)} and a series of representative vector extraction points {q(1), ..., q(j), ..., q(J)} are stored.

3 is a distance calculation unit that calculates d _A (i, j) and d _B (i, j) in equation (2) for i and j specified by the control unit 7.
and w _A (i) and w _B (j) in equation (3) are calculated, and the results are stored in the distance storage unit 5.

4 is a recurrence formula calculation unit, which calculates the integral amount g (i, j) for i, j specified by the control unit 7 into a recurrence formula.
Obtained by calculating (3). At this time, the distance information necessary for calculating equation (3) is read from the distance storage section 5, the past integral amount g is read from the integral amount storage section 6, and the obtained g(i, j) is Amount storage section 6
is stored in 7 is a control unit which receives control signals i, j
are sequentially changed from i=1, j=1 to i=I, j=J, and the distance calculation unit 3 and recurrence formula calculation unit 4 are controlled to calculate the integral obtained at the point of i=I, j=J. Amount g
Using (I, J), the distance between patterns is calculated and output according to equation (4).

Although the principle of the present invention has been explained above, these descriptions do not limit the scope of the present invention. It is possible to use a similar recurrence formula instead of the recurrence formula (3) used in the explanation. Furthermore, any method can be used to compress the pattern using broken line approximation. In the explanation, an example of a voice pattern is used, but the principles of the present invention can be applied to any pattern such as voice or text as long as the pattern is expressed as a series of feature vectors.

As described above, according to the present invention, it is possible to perform pattern matching by applying the DP method to patterns compressed by polygonal line approximation, so it is possible to perform pattern matching with a small storage capacity and processing amount and with high accuracy. It becomes possible to realize this.

[Brief explanation of drawings]

Fig. 1 is a diagram for explaining the concept of distance in the present invention, Fig. 2 is a diagram for explaining a first example of a recurrence formula, and Fig. 3 is a block diagram showing an embodiment according to the present invention. . 1, 2... Vector storage unit, 3... Distance calculation unit, 4... Recurrence formula calculation unit, 5... Distance storage unit, 6
. . . integral quantity storage section, 7 . . . control section.

Claims (1)

[Claims] 1 A series of representative vectors obtained by extracting representative vectors from the first pattern A expressed as a series of feature vectors {a(1), ..., a
(i), ..., a(I)} and the sequence of extraction points {p(1), ...
..., p(i), ..., p(I)}, and a representative vector obtained by extracting a representative vector from a second pattern B expressed as a series of feature vectors. Sequence of vectors {b(1),...
..., b(j), ..., b(J)} and the sequence of extraction points {q
(1), ..., q(j), ..., q(J)}, and representative vectors a(i+1) and a in vector space for specified i and j. The distance d _A (i, j) between the line segment connecting (i) and the point corresponding to representative vector b(j), and the representative vectors b(j+1) and b
(j) and a point corresponding to representative _vector a(i);
Let the above distance d _A (i, j) correspond to the edge connecting point (i, j) and point (i+1, j) on the grid of time points of I×J, and let d _B (i, j) correspond to the point (i, j) and point (i,
j+1); a distance storage unit that stores at least a necessary number of distance information having a grid-like structure obtained by sequentially changing i and j; an integral quantity storage unit that stores at least a required number of integral quantities g for the lattice; and a recurrence formula calculation unit that calculates the weighted sum for multiple combinations and calculates it as the minimum value, and from i=1, j=1 to i=
A pattern matching device characterized in that the distance between the patterns A and B is calculated by sequentially changing i and j until I, j=J.