Pattern matching device with a DP technique applied to feature vectors of two information compressed patterns

Claim 2

In a pattern matching device for calculating an overall similarity measure between a first pattern U represented by a first vector sequence of first through I-th extracted vectors positioned at first through I-th instants, respectively, which are arranged with variable intervals of time as a first timing sequence, and a second pattern V represented by a second vector sequence of first through J-th extracted vectors positioned at first through J-th instants, respectively, which are arranged with variable spacings of time as a second timing sequence, said device comprising first means for generating first and second timing signals indicative of a pair of instants in said first and said second timing sequences at one time, respectively, with the pair varied from a (1, 1)-th pair of the first instants of the respective timing sequences eventually to an (I, J)-th pair of said I-th and said J-th instants through an (i, j)-th pair of the i-th and the j-th instants where i and j are representative of two integers between 1 and I and between 1 and J, respectively, second means responsive to said first and said second timing signals for calculating an (i, j)-th elementary similarity measure for the i-th and the j-th extracted vectors when said first and said second timing signals are indicative of the (i, j)-th pair, and third means responsive to said first and said second timing signals and to the (i, j)-th elementary similarity measures for iteratively calculating a recurrence formula to successively give a plurality of recurrence values, said recurrence formula given, when said first and said second timing signals are indicative of the (i, j)-th pair, an (i, j)-th one f(i, j) of said recurrence values by an extremum of a plurality of results of calculation which are calculated by the use of a prescribed number of previously calculated recurrence values and at least the (i, j)-th elementary similarity measure, respectively, said recurrence formula eventually giving said overall similarity measure by an (I, J)-th one f(I, J) of said recurrence values, the improvement wherein said second means comprises: fourth means coupled to said first means for calculating, when said first and said second timing signals are indicative of the (i, j)-th pair, an (i, j)-th intervector similarity measure d(i, j) between the i-th and the j-th extracted vectors and an (i, j)-th weighting factor w(i, j) by the use of the interval of time from the (i-1)-th instant to the i-th instant; and fifth means coupled to said fourth means for calculating, when said fourth means calculates the (i, j)-th intervector similarity measure and the (i, j)-th weighting factor, the (i, j)-th elementary similarity measure.

Claim 3

A pattern matching device as claimed in claim 1, wherein said fifth means calculates, when said fourth means calculates the (i, j)-th intervector similarity measure, an (i, j)-th weighted similarity measure d w (i, j) as the (i, j)-th elementary similarity measure by multiplying the (i, j)-th intervector similarity measure d(i, j) by the (i, j)-th weighting factor w(i, j), said overall similarity measure being equal to an interpattern similarity measure D(U, V) between said first and said second patterns U and V.

Claim 4

A pattern matching device as claimed in claim 2, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of a plurality of ascendingly consecutive instants of said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants of said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values f(i-1, j), f(i-1, j-1), and f(i-1, j-2) when said first and said second timing signals are indicative of the (i, j)-th pair, wherein said third means calculates said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by three sums which are equal to the i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values f(i-1, j), f(i-1, j-1), and f(i-1, j-2) plus the (i, j)-th weighted similarity measure d w (i, j), respectively.

Claim 5

A pattern matching device as claimed in claim 2, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of a plurality of ascendingly consecutive instants of said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants of said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values f(i-1, j), f(i-1, j-1), and f(i-1, j-2) when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said second means further comprises sixth means coupled to said first means for calculating, when said first and said second timing signals are indicative of the (i, j)-th pair, j-th and (j-1)-th intervector spacings in said second timing sequence t j and t j-1 by two differences which are equal to the j-th instant minus the (j-1)-th instant and to the (j-1)-th instant minus the (j-2)-th instant, respectively;

Claim 6

said fifth means being further coupled to said sixth means for additionally calculating, when said fourth means calculates the (i, j)-th intervector similarity measure, an (i, j)-th additional similarity measure d a (i, j) by a linear combination of the (i, j)-th and the (i, j-1)-th intervector similarity measures d(i, j) and d(i, j-1) to which the (i, j)-th weighting factor w(i, J) is proportionally distributed in proportion to the j-th and the (j-1)-th intervector spacings t j and t j-1 , respectively; said third means calculating said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by two sums which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th weighted similarity measure d w (i, j), respectively, and a sum which is equal to the (i-1, j-2)-th recurrence value f(i-1, j-2) plus the (i, j)-th additional similarity measure d a (i, j).

Claim 7

said fifth means being further coupled to said sixth means for additionally calculating, when said fourth means calculates the (i, j)-th intervector similarity measure, an (i, j)-th additional similarity measure d a (i, j) by a linear combination of the (i, j)-th and the (i, j-1)-th intervector similarity measures d(i, j) and d(i, j-1) to which the (i, j)-th weighting factor w(i, J) is proportionally distributed in proportion to the j-th and the (j-1)-th intervector spacings t j and t j-1 , respectively; said third means calculating said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by two sums which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th weighted similarity measure d w (i, j), respectively, and a sum which is equal to the (i-1, j-2)-th recurrence value f(i-1, j-2) plus the (i, j)-th additional similarity measure d a (i, j).

Claim 8

A pattern matching device as claimed in claim 2, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of a plurality of ascendingly consecutive instants of said second timing siquence within each of the intervals of time during which said first timing signal indicates one of the intervals of said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values f(i-1, j), f(i-1, j-1), and f(i-1, j-2) when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said fifth means is for additionally calculating, when said fourth means calculates the (i, j)-th intervector similarity measure, an (i, j)-th additional similarity measure d a (i, j) by a linear combination of the (i, j)-th and the (i, j-1)-th intervector similarity measures d(i, j) and d(i, j-1), each of which is multiplied by a half of the (i, j)-th weighting factor w(i, j); said third means calculating said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by two sums which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, J) and f(i-1, J-1) plus the (i, j)-th weighted similarity measure d w (i, j), respectively, and a sum which is equal to the (i-1, j-2)-th recurrence value f(i-1, J-2) plus the (i, j)-th additional similarity measure d a (i, j).

Claim 9

A pattern matching device as claimed in claim 1, wherein: said second means further comprises subtracting means coupled to said fourth means for calculating, when said fourth means calculates the (i, j)-th intervector similarity measure, an (i, j)-th compensated similarity measure d'(i, j) by subtracting a predetermined value δ from the (i, j)-th intervector similarity measure d(i, j); said fifth means being further coupled to said subtracting means for calculating, when said subtracting means calculates the (i, j)-th compensated similarity measure, an (i, j)-th compensated and weighted similarity measure d w '(i, j) as the (i, j)-th elementary similarity measure by multiplying the (i, j)-th compensated similarity measure d'(i, j) by the (i, j)-th weighting factor w(i, j); said overall similarity measure being related to an interpattern similarity measure D(U, V) representative of whether said first and said second patterns U and V are similar or dissimilar to each other.

Claim 10

A pattern matching device as claimed in claim 6, wherein said third means comprises: means responsive to said first and said second timing signals and to the (i, j)-th elementary similarity measures for calculating, when said first and said second timing signals are indicative of the (i, j)-th pair and consequently when said recurrence formula gives the (i, j)-th recurrence value f(i, j), a plurality of sums of an (i, j)-th group which are equal to the previously calculated recurrence values of said prescribed number plus at least the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively; means responsive to the sums of the (i, j)-th group for producing an overflow signal which takes first, second, and third signal values when each of the sums of the (i, j)-th group is greater than a first preselected value, is less than a second preselected value, and is an (i, j)-th restricted sum which, in turn, is neither greater than said first preselected value nor less than said second preselected value, respectively; and means responsive to said overflow signal for providing each of the results of calculation for the (i, j)-th recurrence value f(i, j) by said first and said second preselected values and the (i, j)-th restricted sum when said overflow signal takes said first through said third signal values, respectively.

Claim 11

A pattern matching device as claimed in claim 7, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of a plurality of ascendingly consecutive instants of said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants of said first timing sequence, further comprising additional means responsive to said overflow signal for keeping generation by said first means of said first and said second timing signals in progress and for discontinuing said generation if said overflow signal always takes and does not always take a predetermined one of said first and said second signal values throughout at least one of the intervals of time, respectively, said predetermined one signal value being said first and said second signal values when said extremum is a minimum and a maximum, respectively.

Claim 12

A pattern matching device as claimed in claim 8, wherein said additional means comprises: means for generating a sequence of timed pulses at the beginnings of said intervals of time, respectively; means responsive to said overflow signal for producing a pulse signal only when said overflow signal does not always take said predetermined one signal value throughout each of said intervals of time; output switching means responsive to each of said timed pulses for switching an output signal thereof from a first level to a second level, said output switching means being further responsive to said pulse signal for switching said output signal from said second level back to said first level; and signal pulse producing means responsive to the output signal of said first level for producing one of said timed pulses as a signal pulse for discontinuing said generation, said signal pulse producing means being further responsive to the output signal of said second level for producing noe of said timed pulses to keep said generation in progress.

Claim 13

A pattern matching device as claimed in claims 8 or 9, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, J-1)-th, and the (i-1, J-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein said sum calculating means calculates the sums of the (i, j)-th group by adding the (i, j)-th compensated and weighted similarity measure d w '(i, j) to the (i-1, J)-th, the (i-1, j-1)-th, and the (i-1, J-2)-th recurrence values f(i-1, j), f(i-1, j-1), and f(i-1, j-2), respectively.

Claim 14

A pattern matching device as claimed in claims 8 or 9, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said second means further comprises sixth means coupled to said first means for calculating, when said first and said second second timing signals are indicative of the (i, j)-th pair, j-th and (j-1)-th intervector spacings in said second timing sequence t j and t j-1 by subtracting the (j-1)-th and the (j-2)-th instants for the j-th and the (j-1)-th instants, respectively; said fifth means being further coupled to said sixth means for additionally calculating, when said subtracting means calculates the (i, j)-th compensated similarity measure, an (i, j)-th compensated additional similarity measure d a '(i, j) by a linear combination of the (i, j)-th and the (j-1)-th compensated similarity measures d'(i, j) and d'(i, j-1) to which the (i, j)-th weighting factor w(i, j) is proportionally distributed in proportion to the j-th and the (j-1)-th intervector spacings t j and t j-1 , respectively; said sum calculating means calculating the sums of the (i, j)-th group by two sums which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively, and a sum which is equal to the (i-1, j-2)-th recurrence value f(i-1, j-2) plus the (i, j)-th compensated additional similarity measure d a '(i, j).

Claim 15

A pattern matching device as claimed in claims 8 or 9, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said fifth means additionally calculates, when said subtracting means calculates the (i, j)-th compensated similarity measure, an (i, j)-th compensated additional similarity measure d a '(i, j) by a linear combination of the (i, j)-th and the (i, j-1)-th compensated similarity measures d'(i, j) and d'(i, j-1), each of which is multiplied by a half of the (i, j)-th weighting factor w(i, j); said sum calculating means calculating the sums of the (i, j)-th group by two sums which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively, and a sum which is equal to the (i-1, j-2)-th recurrence value f(i-1, j-2) plus the (i, j)-th compensated additional similarity measure d a '(i, j).

Claim 16

A pattern matching device as claimed in claims 8 or 9, further comprising: means responsive to said first timing signal for totalizing said intervals of time to provide a total duration of said first pattern U; and means for calculating a product of said total duration and said predetermined value δ and for adding said product to said overall similarity measure to provide said interpattern similarity measure D(U, V).

Claim 17

A pattern matching device as claimed in claim 7, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signals rendered successively indicative of a plurality of ascendingly consecutive instants in said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants of said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein said sum calculating means calculates the sums of the (i, j)-th group by adding the (i, j)-th compensated and weighted similarity measure d w '(i, j) to the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values f(i-1, j), f(i-1, j-1), and f(i-1, j-2), respectively.

Claim 18

A pattern matching device as claimed in claim 7, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signals rendered successively indicative of a plurality of asendingly consecutive instants in said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants in said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said second means further comprises sixth means coupled to said first means for calculating, when said first and said second timing signals are indicative of the (i, j)-th pair, j-th and (j-1)-th intervector spacings in said second timing sequence t j and t j-1 by subtracting the (j-1)-th and the (j-2)-th instants from the j-th and the (j-1)-th instants, respectively; said fifth means being further coupled to said sixth means for additionally calculating, when said subtracting means calculates the (i, j)-th compensated similarity measure, an (i, j)-th compensated additional similarity measure d a '(i, j) by a linear combination of the (i, j)-th and the (j-1)-th compensated similarity measures d'(i, j) and d'(i, j-1) to which the (i, j)-th weighting factor w(i, j) is proportionally distributed in proportion to the j-th and the (j-1)-th intervector spacings t j and t j-1 , respectively; said sum calculating means calculating the sums of the (i, j)-th group by two sums which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively, and a sum which is equal to the (i-1, j-2)-th recurrence value f(i-1, j-2) plus the (i, j)-th compensated additional similarity measure d a '(i, j).

Claim 19

A pattern matching device as claimed in claim 7, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of a plurality of ascendingly consecutive instants in said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants in said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said fifth means is for additionally calculating, when said subtracting means calculates the (i, j)-th compensated similarity measure, an (i, j)-th compensated additional similarity measure d a '(i, j) by a linear combination of the (i, j)-th and the (i, j-1)-th compensated similarity measures d'(i, j) and d'(i, j-1), each of which is multiplied by a half of the (i, j)-th weighting factor w(i, j); said sum calculating means calculating the sums of the (i, j)-th group by two sums which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively, and a sum which is equal to the (i-1, j-2)-th recurrence value f(i-1, j-2) plus the (i, j)-th compensated additional similarity measure d a '(i, j).

Claim 20

A pattern matching device as claimed in any one of claims 14 through 16, wherein said third means further comprises additional means responsive to said overflow signal for keeping generation by said first means of said first and said second timing signals in progress and for discontinuing said generation if said overflow signal always takes and does not always take a predetermined one of said first and said second signal values throughout at least one of the intervals of time, respectively, said predetermined one signal value being said first and said second signal values when said extremum is a minimum and a maximum, respectively.

Claim 21

A pattern matching device as claimed in claim 17, wherein said additional means comprises: means for generating a sequence of timed pulses at the beginnings of said intervals of time, respectively; means responsive to said overflow signal for producing a pulse signal only when said overflow signal does not always take said predetermined one signal value throughout each of said intervals of time; output switching means responsive to each of said timed pulses for switching an output signal thereof from a first level to a second level, said output switching means being further responsive to said pulse signal for switching said output signal from said second level back to said first level; and signal pulse producing means responsive to the output signal of said first level for producing one of said timed pulses as a signal pulse for discontinuing said generation, said signal pulse producing means being further responsive to the output signal of said second level for producing none of said timed pulses as said signal pulse to keep said generation is progress.

Claim 22

A pattern matching device as claimed in any one of claims 14 through 16, further comprising: means responsive to said first timing signal for calculating a total duration of said first pattern U by totalizing said intervals of time; and means for calculating said interpattern similarity measure D(U, V) by calculating a product of said total duration and said predetermined value δ and by adding said product to said overall similarity measure.

Claim 23

A pattern matching device as claimed in claim 6, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of ascendingly consecutive instants in said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants in said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein said third means calculates said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by three sums of an (i, j)-th group which are equal to the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values f(i-1, j), f(i-1, j-1), and f(i-1, j-2) plus the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively.

Claim 24

A pattern matching device as claimed in claim 6, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of ascendingly consecutive instants in said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants in said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said second means further comprises sixth means coupled to said first means for calculating, when said first and said second timing signals are indicative of the (i, j)-th pair, j-th and (j-1)-th intervector spacings of said second timing sequence t j and t j-1 by subtracting the (j-1)-th and the (j-2)-th instants from the j-th and the (j-1)-th instants, respectively; said fifth means being further coupled to said sixth means for additionally calculating, when said subtracting means calculates the (i, j)-th compensated similarity measure, an (i, j)-th compensated additional similarity measure d a '(i, j) by a linear combination of the (i, j)-th and the (i, j-1)-th compensated similarity measures d'(i, j) and d'(i, j-1) to which the (i, j)-th weighting factor w(i, j) is proportionally distributed in proportion to the j-th and the (j-1)-th intervector spacings t j and t j-1 , respectively; said third means calculating said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by three sums of an (i, j)-th group, two of which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively, and one of which is equal to the (i-1, j-2)-th recurrence value f(i-1, j-2) plus the (i, j)-th compensated additional similarity measure d a '(i, j).

Claim 25

A pattern matching device as claimed in claim 6, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of ascendingly consecutive instants in said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants in said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said fifth means is for additionally calculating, when said subtracting means calculates the (i, j)-th compensated similarity measure, an (i, j)-th compensated additional similarity measure d a '(i, j) by a linear combination of the (i, j)-th and the (i, j-1)-th compensated similarity measures d'(i, j) and d'(i, j-1), each of which is multiplied by a half of the (i, j)-th weighting factor w(i, j); said third means calculating said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by three sums of an (i, j)-th group, two of which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively, and one of which is equal to the (i-1, j-2)-th recorrence value f(i-1, j-2) plus the (i, j)-th compensated additional similarity measure d a '(i, j).

Claim 26

A pattern matching device as claimed in claim 1, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of a plurality of ascendingly consecutive instants in said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants in said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said second means further comprises sixth means coupled to said fourth means for calculating, when said fourth means calculates the (i, j)-th weighting factor, an (i, j)-th compensation factor by multiplying the (i, j)-th weighting factor w(i, j) by a predetermined value δ; said fifth means being further coupled to said sixth means for calculating, when said fourth means calculates the (i, j)-th intervector similarity measure, an (i, j)-th weighted similarity measure d w (i, j) by multiplying the (i, j)-th intervector similarity measure d(i, j) by the (i, j)-th weighting factor w(i, j) and for subtracting the (i, j)-th compensation factor from the (i, j)-th weighted similarity measure d w (i, j) to provide an (i, j)-th compensated and weighted similarity measure d w '(i, j) as the (i, j)-th elementary similarity measure; said third means calculating said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by three sums of an (i, j)-th group which are equal to the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values f(i-1, j), f(i-1, j-1), and f(i-1, j-2) plus the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively; said overall similarity measure being related to an interpattern similarity measure D(U, V) representative of whether said first and said second patterns U and V are similar or dissimilar to each other.

Claim 27

A pattern matching device as claimed in claim 1, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of a plurality of ascendingly consecutive instants in said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants in said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said second means further comprises: sixth means coupled to said first means for calculating, when said first and said second timing signals are indicative of the (i, j)-th pair, j-th and (j-1)-th intervector spacings in said second timing sequence t j and t j-1 by subtracting the (j-1)-th and the (j-2)-th instants from the j-th and the (j-1)-th instants, respectively; and seventh means coupled to said fourth means for calculating, when said fourth means calculates the (i, j)-th weighting factor, an (i, j)-th compensation factor by multiplying the (i, j)-th weighting factor w(i, j) by a predetermined value δ; said fifth means being further coupled to said sixth means for calculating, when said fourth means calculates the (i, j)-th intervector similarity measure, an (i, j)-th weighted similarity measure d w (i, j) by multiplying the (i, j)-th intervector similarity measure d(i, j) by the (i, j)-th weighting factor w(i, j) and an (i, j)-th additional similarity measure d a (i, j) by a linear combination of the (i, j)-th and the (i, j-1)-th intervector similarity measures d(i, j) and d(i, j-1) to which the (i, j)-th weighting factor w(i, j) is proportionally distributed in proportion to the j-th and the (j-1)-th intervector spacings t j and t j-1 , respectively, said fifth means being still further coupled to said seventh means for subtracting, when said fourth means calculates the (i, j)-th intervector similarity measure, the (i, j)-th compensation factor from the (i, j)-th weighted similarity measure d w (i, j) and the (i, j)-th additional similarity measure d a (i, j) to provide an (i, j)-th compensated and weighted similarity measure d w '(i, j) as the (i, j)-th elementary similarity measure and an (i, j)-th compensated additional similarity measure d a '(i, j), respectively; said third means calculating said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by three sums of an (i, j)-th group, two of which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th compensated and weighted similarity measure d w '(i, j), respectively, and one of which is equal to the (i-1, j-2)-th recurrence value f(i-1, j-2) plus the (i, j)-th compensated additional similarity measure d a '(i, j); said overall similarity measure being related to an interpattern similarity measure D(U, V) representative of whether said first and said second patterns U and V are similar or dissimilar to each other.

Claim 28

A pattern matching device as claimed in claim 1, said first means generating said first and said second timing signals with said first timing signal rendered ascendingly consecutively indicative of said first through said I-th instants and with said second timing signal rendered successively indicative of a plurality of ascendingly consecutive instants in said second timing sequence within each of the intervals of time during which said first timing signal indicates one of the instants in said first timing sequence, said prescribed number being three, said previously calculated recurrence values being the (i-1, j)-th, the (i-1, j-1)-th, and the (i-1, j-2)-th recurrence values when said first and said second timing signals are indicative of the (i, j)-th pair, wherein: said second means further comprises sixth means coupled to said fourth means for calculating, when said fourth means calculates the (i, j)-th weighting factor, an (i, j)-th compensation factor by multiplying the (i, j)-th weighting factor w(i, j) by a predetermined value δ; said fifth means being further coupled to said sixth means for calculating, when said fourth means calculates the (i, j)-th intervector similarity measure, an (i, j)-th weighted similarity measure d w (i, j) by multiplying the (i, j)-th intervector similarity measure d(i, j) by the (i, j)-th weighting factor w(i, j) and an (i, j)-th additional similarity measure d a (i, j) by a linear combination of the (i, j)-th and the (i, j-1)-th intervector similarity measures d(i, j) and d(i, j-1), each of which is multiplied by a half of the (i, j)-th weighting factor w(i, j), and for subtracting the (i, j)-th compensation factor from the (i, j)-th weighted similarity measure d w (i, j) and the (i, j)-th additional similarity measure d a (i, j) to provide an (i, j)-th compensated and weighted similarity measure d w '(i, j) as the (i, j)-th elementary similarity measure and an (i, j)-th compensated additional similarity measure d a '(i, j), respectively; said third means calculating said recurrence formula with the results of calculation given, when said first and said second timing signals are indicative of the (i, j)-th pair, by three sums of an (i, j)-th group, two of which are equal to the (i-1, j)-th and the (i-1, j-1)-th recurrence values f(i-1, j) and f(i-1, j-1) plus the (i, j)-th compensated and weighted similarity measures d w '(i, j), respectively, and one of which is equal to the (i-1, j-2)-th recurrence value f(i-1, j-2) plus the (i, j)-th compensated additional similarity measure d a '(i, j); said overall similarity measure being related to an interpattern similarity measure D(U, V) representative of whether said first and said second patterns U and V are similar or dissimilar to each other.

Claim 29

A pattern matching device as claimed in any one of claims 20 through 25, wherein said third means comprises: means responsive to said first and said second timing signals and to the (i, j)-th elementary similarity measures for calculating, when said first and said second timing signals are indicative of the (i, j)-th pair and consequently when said recurrence formula gives the (i, j)-th recurrence value f(i, j), the three sums of the (i, j)-th group; means responsive to the three sums of the (i, j)-th group for producing an overflow signal which takes first, second, and third signal values when each of the three sums of the (i, j)-th group is greater than a first preselected value, is less than a second preselected value, and is an (i, j)-th restricted sum which, in turn, is neither greater than said first preselected value nor less than said second preselected value, respectively; and means responsive to said overflow signal for providing each of the results of calculation for the (i, j)-th recurrence value f(i, j) by said first and said second preselected values and the (i, j)-th restricted sum when said overflow signal takes said first through said third signal values, respectively.

Claim 30

A pattern matching device as claimed in claim 26, further comprising additional means responsive to said overflow signal for keeping generation by said first means of said first and said second timing signals in progress and for discontinuing said generation if said overflow signal always takes and does not always take a predetermined one of said first and said second signal values throughout at least one of the intervals of time, respectively, said predetermined one signal value being said first and said second signal values when said extremum is a minimum and a maximum, respectively.

Claim 31

A pattern matching device as claimed in claim 27, wherein said additional means comprises: means for generating a sequence of timed pulses at the beginnings of said intervals of time, respectively; means responsive to said overflow signal for producing a pulse signal only when said overflow signal does not always take said predetermined one signal value throughout each of said intervals of time; output switching means responsive to each of said timed pulses for switching an output signal thereof from a first level to a second level, said output switching means being further responsive to said pulse signal for switching said output signal from said second level back to said first level; and signal pulse producing means responsive to the output signal of said first level for producing one of said timed pulses as a signal pulse for discontinuing said generation, said signal pulse producing means being further responsive to the output signal of said second level for producing none of said timed pulses as said signal pulse to keep said generation in progress.

Claim 32

A pattern matching device as claimed in any one of claims 20 through 25, further comprising: means responsive to said first timing signal for calculating a total duration of said first pattern U by totalizing said intervals of time; and means for calculating said interpattern similarity measure D(U, V) by calculating a product of said total duration and said predetermined value δ and by adding said product to said overall similarity measure.