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

• US 4,467,437 A
• Filed: 03/01/1982
• Issued: 08/21/1984
• Est. Priority Date: 03/06/1981
• Status: Expired due to Term

• Current Assignee: Nippon Electric Company Limited 33-1 Shiba Gochome Minato-Ku Tokyo Japan
• Original Assignee: Nippon Electric Company Limited (NEC Corporation)
• Inventors: Sakoe, Hiroaki, Tsuruta, Shichiro
• Primary Examiner(s): Kemeny, E. S. Matt
• Application Number:
  US06/353,293
• Time in Patent Office: 904 Days
• Field of Search: 381/41-50, 382/30, 364/513, 364/513.5
• US Class Current: 704/241
• 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

This pattern matching system features the calculation of a weighting factor based on the variable interval between feature vector samples. On carrying out matching of two information compressed patterns, a weighted similarity measure calculator (64) calculates a weighted similarity measure by multiplying an intervector similarity measure between one each feature vector of the respective patterns by a weighting factor calculated by the use of a variable interval between each feature vector and a next previous one. A recurrence formula is calculated by the use of such weighted similarity measures instead of the intervector similarity measures. A predetermined value δ may be used in reducing the number of signal bits used for the recurrence formula. Preferably, a sum for the recurrence formula is restricted by two preselected values. Most preferably, an additional similarity measure is used for the recurrence formula.

Claims

1. 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.

2. 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.

3. 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.

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 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;

6. 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).

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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).

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 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).

14. 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).

15. 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.

16. 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).

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 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).

18. 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.

19. 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.

20. 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.

21. 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.

22. 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).

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 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).

24. 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.

25. 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.

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 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.

27. 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.

28. 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.

29. 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.

30. 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.

5. 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).