Pattern matching device with a DP technique applied to feature vectors of two information compressed patterns
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
30 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. - View Dependent Claims (2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
-
-
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 da (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 tj and tj-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 dw (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 da (i, j).
Specification