US3816722A — Computer for calculating the similarity between p…

Claim 1

Independent Claim 135 words

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.

Claim 2

Dependent Claim 135 words

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.

Claim 3

Dependent Claim 180 words

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.

Claim 4

Dependent Claim 180 words

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.

Claim 5

Dependent Claim 49 words

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:

Claim 6

Dependent Claim 51 words

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:

Claim 7

Dependent Claim 37 words

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

Claim 8

Dependent Claim 37 words

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

Claim 9

Dependent Claim 648 words

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.

Claim 10

Independent Claim 227 words

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.

Claim 11

Independent Claim 227 words

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.

Claim 12

Independent Claim 280 words

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.

Claim 13

Independent Claim 280 words

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.

Claim 14

Independent Claim 477 words

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.

Claim 15

Independent Claim 477 words

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.

Claim 16

Dependent Claim 25 words

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

Claim 17

Dependent Claim 42 words

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.

Claim 18

Dependent Claim 13 words

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

Claim 19

Dependent Claim 14 words

A computer as claimed in claim 4 wherein: d(ai bj) ai - bj .

Claim 20

Dependent Claim 8 words

A computer as claimed in claim 5 wherein:

Claim 21

Dependent Claim 23 words

A computer as claimed in claim 5 wherein: m(ai bj) ai -bj , and the Extremum in the recurrence formula is the Minimum.

Claim 22

Dependent Claim 8 words

A computer as claimed in claim 6 wherein:

Claim 23

Dependent Claim 23 words

A computer as claimed in claim 6 wherein: m(ai bj) ai -bj , and the Extremum in the recurrence formula is the Minimum.

Claim 24

Dependent Claim 49 words

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:

Claim 25

Dependent Claim 51 words

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:

Claim 26

Dependent Claim 37 words

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

Claim 27

Dependent Claim 37 words

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

Claim 28

Dependent Claim 25 words

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

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1977-06-10	1977-12-10	1978-06-11	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1981-06-10	1981-12-10	1982-06-11	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1985-06-10	1985-12-10	1986-06-11	$7700.00	Window Closed / Lapsed

Computer for calculating the similarity between patterns and pattern recognition system comprising the similarity computer

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag