COMPUTER FOR CALCULATING THE SIMILARITY BETWEEN PATTERNS AND PATTERN RECOGNITION SYSTEM COMPRISING THE SIMILARITY COMPUTER

• US 3,816,722 A
• Filed: 09/28/1971
• Issued: 06/11/1974
• Est. Priority Date: 09/29/1970
• Status: Expired due to Term

• Current Assignee: Hiroaki Sakoe, Seibi Chiba
• Original Assignee: Hiroaki Sakoe, Seibi Chiba
• Inventors: Sakoe, Hiroaki, Chiba, Seibi
• Primary Examiner(s): Ruggiero, Joseph F.
• Application Number:
  US05/184,403
• Time in Patent Office: 987 Days
• Field of Search: 235/181,152 340/146.3R,146.3A,146.3Q,146.3H,146.3FT,146.3WD,172.5 179/1SA,1SB 444/1
• US Class Current: 708/424
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: G10L 15/00 Speech recognition G10L17/00 takes precedence
• CPC Class Codes: G10L 15/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]

Abstract

The feature vectors of a sequence representative of a first pattern are correlated to those in another sequence representative of a second pattern in such a manner that the normalized sum of the quantities representative of the similarity between each feature vector of a sequence and at least one feature vector of the other sequence may assume an extremum. The extremum is used as the similarity measure to be calculated between the two patterns. With the pattern recognition system, the similarity measure is calculated for each reference pattern and a variable-length partial pattern to be recognized. The partial pattern is successively recognized to be a permutation with repetitions of reference patterns, each having the maximum similarity measure.

Claims

1. A computer for calculating the similarity measure between two patterns, each represented by a sequence of feature vectors, based on the quantities representative of the similarity between the feature vectors of the respective sequences, wherein the improvement comprises means for calculating the normalized sum of said quantities, said means comprising means for calculating said quantities in a sequence such that a preceeding quantity is calculated between one of the feature vectors of one of said sequences and one of the feature vectors of the other sequence and the succeeding quantity is calculated between two feature vectors of said respective patterns at least one of which is the next succeeding feature vector from the one in said preceeding quantity and neither of which preceeds in sequence the respective feature vector used to calculate said preceeding quantity.

2. A computer for calculating the similarity measure between two patterns, one represented by a first sequence of successive feature vectors ai (i 1, 2, . . . , and I), I in number, the other represented by a second sequence of successive feature vectors bj (j - 1, 2, . . . , and J), J in number, based on the quantities representative of the similarity between said feature vectors of said first sequence and said feature vectors of said second sequence, wherein the improvement comprises means for calculating the extremum normalized sum of the quantities representative of the similarity m(ai, bj) between each feature vector as (s each of the integers i) of said first sequence and at least one t-th feature vector bt (t at least one of the integers j) of said second sequence, said means for calculating the extremum normalized sum of the quantities including means for calculating said quantities in the following sequence m (a1, b1) . . . m(as 1 bx) m(as bt) . . . m(aI bJ) where t >

or = x.

3. A computer as claimed in claim 2 wherein said similarity quantities are defined as r(ai bj) and said means for calculating the extremum normalized sum of the quantities further comprises, recurrence formula calculating means for successively calculating g(ai bj) for each r(ai bj), where g(ai bj) is defined as:

4. A computer as claimed in claim 2 wherein said similarity quantities are defined as d(ai bj) and said means for calculating the extremum normalized sum of the quantities further comprises, recurrence formula calculating means for successively calculating g(ai bj) for each calculation of d(ai bj), where g(ai bj) is defined as:

5. A computer as claimed in claim 2, wherein said means for calculating the extremum normalized sum of the quantities further comprises:

recurrence formula calculating means;

for calculating a recurrence formula for a cumulative quantity for the similarity

6. A computer as claimed in claim 2, wherein said means for calculating the extremum normalized sum of the quantities further comprises:

recurrence formula calculating means for calculating a recurrence formula for a cumulative quantity for the similarity

7. A computer as claimed in claim 6, wherein said recurrence formula calculating means comprises first and second vector shift register means having a plurality of stages for storing the feature vectors of said first and said second sequences, respectively, buffer register means having a plurality of stages responsive to the content of a predetermined stage of said first vector register means for storing the feature vectors of said first sequence, a first and a second quantity shift register having a plurality of stages for storing the cumulative quantities g(a, b, ), a calculator responsive to the contents of the respective preselected stages of said buffer and said second vector register means for producing the quantity m(a, b) representative of the similarity between the last-mentioned contents, a first adder responsive to the content of a first predetermined stage of said second quantity register and the quantity produced by said first adder for producing the sum of the last-mentioned content and quantity, a selector responsive to the contents of a predetermined stage of said first quantity register and of a second predetermined stage of said second quantity register and said sum for producing the extremum of the last-mentioned contents and said similarity quantity, a second adder responsive to said sum and said extremum for producing the cumulative quantity for the contents of said respective preselected stages of said vector register means, vector shift means for successively shifting the contents of said first and said second vector register means to place a prescribed feature vector of said second sequence having a prescribed suffix in said preselected stage of said second vector register means following the feature vector having a preceding suffix equal to said prescribed suffix minus one, buffer shift means for cyclically shifting the contents of said buffer register means to place, while said prescribed vector is placed in said preselected stage, the feature vectors of said first sequence in said preselected stage of said buffer register means from the feature vector having a first suffix equal to said prescribed suffix minus a predetermined integer successively to the feature vector having a second suffix equal to said First suffix plus twice said predetermined integer, said vector shift means placing the feature vector having a suffix equal to said second suffix in said predetermined stage of said first vector register means while said prescribed vector is placed in said preselected stage, said buffer shift means placing the vector with said second suffix placed in said predetermined stage of said first vector register means in said buffer register means next succeeding the feature vector having a third suffix equal to said second suffix minus one at the latest before the vector with said third suffix is shifted from said preselected stage of said buffer register means, quantity shift means for successively shifting the contents of said quantity registers substantially simultaneously with the cyclic shift of the contents in said buffer register means, write-in means for writing the cumulative quantities successively produced by said second adder in the respective stages of said first quantity register, and transfer means for transferring the contents of said first quantity register to said second quantity register in timed relation to the shift of the contents of each said vector register means by one feature vector, said quantity shift means placing, when the feature vector having a fourth suffix is placed in said preselected stage of said buffer register means, the cumulative quantities produced for the feature vector having a suffix equal to said fourth suffix minus one and said prescribed vector, for the vectors having said fourth suffix and said preceding suffix, respectively, and for the feature vectors having a suffix equal to said fourth suffix minus one and said preceding suffix, respectively, in said predetermined stage of said first quantity register and in said second and said first predetermined stages of said second quantity register, respectively.

8. A system for recognizing a given pattern represented by a given-pattern sequence of feature vectors with reference to a predetermined number of reference patterns, each represented by a reference sequence of feature vectors, said system having means for successively selecting every one of said reference sequences, means for calculating the similarity measure between said given pattern and the reference pattern represented by the selected reference sequence based on the quantities representative of the similarity between the feature vectors of said given-pattern sequence and those of the selected reference sequence, and means for finding out the maximum of the similarity measures calculated for all of said reference sequences thereby recognizing said given pattern to be that one of said reference patterns for which the similarity measure is the maximum, wherein the improvement comprises means in said calculating means for calculating the normalized sum of said quantities, each said quantity being calculated between one of the feature vectors of said given-pattern sequence and one of the feature vectors of the selected reference sequence followed by the quantity representative of the similarity between those two feature vectors in the respective last-mentioned sequences, both of which are not placed in the respective last-mentioned sequences preceding said ones of the feature vectors, respectively, and at least one of which is placed in the sequence next succeeding said one of the feature vectors.

9. A system for recognizing a given pattern represented by a given-pattern sequence of feature vectors with reference to a predetermined number of reference patterns, each represented by a reference sequence of feature vectors, said system having means for successively selecting every one of said reference sequences, means for calculating the similarity measure between said given pattern and the reference pattern represented by the selected reference sequence based on the quantities representative of the similarity between the feature vectors of said given-pattern sequence and those of the selected reference sequence, and means for findiNg out the maximum of the similarity measures calculated for all of said reference sequences thereby recognizing said given pattern to be that one of said reference patterns for which the similarity measure is the maximum, wherein the improvement comprises:

first means in said calculating means for finding out the extremum normalized sum of the quantities representative of the similarity between each of the feature vectors of the selected reference sequence and at least one of the feature vectors of said given-pattern sequence up to the quantity for the last feature vector of said selected reference sequence and each of a plurality of k-th feature vectors of said given-pattern sequence, the number k satisfying J - R <

or = k <

or = J + R, where J and R are predetermined integers, respectively, and second means in said maximum finding means for finding out the extremum of the extremum normalized sums found for all of said numbers k and for all of said reference sequences, whereby said given pattern is recognized to comprise that one of said reference patterns for which the last-mentioned extremum is found.

10. A system for recognizing a given pattern U represented by a given-pattern sequence of successive feature vectors ui (i 1, 2, . . . , and I), I in number, with reference to a predetermined number T of reference patterns Vt (t 1, 2, . . . , and T), each said reference pattern Vh (h each of the integers t) being represented by a reference sequence of successive feature vectors vjh (j 1, 2, . . . , and Jh), Jh in number, said system having means for successively selecting every one of said reference sequences, means for calculating the similarity measure between said given pattern and the reference pattern represented by the selected reference sequence based on the quantities representative of the similarity between the feature vectors of said given-pattern sequence and those of the selected reference sequence, and means for finding out the maximum of the similarity measures calculated for all of said reference sequences thereby recognizing said given pattern to be that one of said reference patterns for which the similarity measure is the maximum, wherein the improvement comprises:

first means in said maximum finding means for recognizing an f-th definite portion of said given pattern (f each of positive integers) represented by the successive feature vectors including the first feature vector u1 of said given-pattern sequence to be a definite f-permutation with repetitions of the reference patterns VD1.. . . .VD(f

     1).VDf, the number f being at least one, said permutation being a definite concatination of a first through an (f -

     1)-th definite reference sequence and an f-th definite reference sequence, and second means in said calculating means for finding out the extremum normalized sum of the quantities representative of the similarity between each of the feature vectors of a partly definite concatination of said first through said (f -

     1)-th definite reference sequences plus a reference sequence selected as the f-th possible reference sequence of said partly definite concatination and at least one feature vector of said given-pattern sequence up to the quantity for the last feature vector v J (hf) (hf) of said f-th possible reference sequence and each of a plurality of k-th feature vectors of said given-pattern sequence, the numbers k satisfying kD(f

     1) + J(hf) - R <

or = k <

or = kD(f

     1) + J(hf) + R, where kD(f

     1) is the number of the feature vectors of a concatination of said first through said (f -

     1)-th definite reference sequences, said first means comprising means for finding out the extremum of the extremum normalized sums found for all of said numbers k and for all of said reference sequences successively selected as said f-th possible reference sequence, thereby recognizing that one of said all of said reference sequences to be said f-th definite reference sequence for which the last-mentioned extremum is found.

11. A system as claimed in claim 10, wherein said second means comprises:

means for calculating a recurrence formula for a cumulative quantity for the similarity

12. A computer as claimed in claim 2 wherein each quantity calculated, m(ai, bj) satisfies the following condition, i - R <

or = j <

or = i + R, where R is a predetermined integer smaller than both I and J.

13. A computer as claimed in claim 3 wherein r(ai, bi) is defined as:

14. A computer as claimed in claim 4 wherein:

d(ai bj) ai - bj .

15. A computer as claimed in claim 5 wherein:

16. A computer as claimed in claim 5 wherein:

m(ai bj) ai -bj , and the Extremum in the recurrence formula is the Minimum.

17. A computer as claimed in claim 6 wherein:

18. A computer as claimed in claim 6 wherein:

m(ai bj) ai -bj , and the Extremum in the recurrence formula is the Minimum.

19. A computer as claimed in claim 2 wherein said similarity quantities are defined as r(ai bj) and said means for calculating the extremum normalized sum of the quantities further comprises, recurrence formula calculating means for successively calculating g(ai bj) for each r(ai bj), where g(ai bj) is defined as:

20. A computer as claimed in claim 2 wherein said similarity quantities are defined as d(ai bj) and said means for calculating the extremum normalized sum of the quantities further comprises, recurrence formula calculating means for successively calculating g(ai bj) for each calculation of d(ai bj), where g(ai bj) is defined as:

21. A computer as claimed in claim 2, wherein said means for calculating the extremum normalized sum of the quantities further comprises:

recurrence formula calculating means for calculating a recurrence formula for a cumulative quantity for the similarity

22. A computer as claimed in claim 2, wherein said means for calculating the extremum normalized sum of the quantities further comprises:

recurrence formula calculating means for calculating a recurrence formula for a cumulative quantity for the similarity

23. A system as claimed in claim 10, wherein said second means comprises:

means for calculating a recurrence formula for a cumulative quantity for the similarity