Pattern matching device operable with signals of a compressed dynamic range

• US 4,479,236 A
• Filed: 02/03/1982
• Issued: 10/23/1984
• Est. Priority Date: 02/17/1981
• Status: Expired due to Term

• Current Assignee: Nippon Electric Company Limited (NEC Corporation)
• Original Assignee: Nippon Electric Company Limited (NEC Corporation)
• Inventors: Sakoe, Hiroaki
• Primary Examiner(s): Martin, John C.
• Assistant Examiner(s): McDowell, Erin A.
• Application Number:
  US06/345,447
• Time in Patent Office: 993 Days
• Field of Search: 381/41-45, 382/34, 382/36, 382/3
• US Class Current: 704/238
• 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/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]

Abstract

A pattern matching device generally comprises a first circuit (36) for calculating an elementary similarity measure between two feature vectors, one and the other selected from two feature vector sequences representative of two patterns, respectively, and a second circuit (37) for iteratively calculating a recurrence formula which defines a recurrence value by a sum of such an elementary similarity measure and an extremum of a prescribed number of previously calculated recurrence values. The recurrence formula eventually gives an overall similarity measure between the two patterns. The elementary similarity measure is now calculated by calculating a primitive similarity measure by a conventional circuit (15) and subtracting a predetermined value therefrom by a compensation circuit (31). Preferably, the second circuit (37) comprises circuitry (41, 42) for preventing the sum from overflowing outwardly of a preselected range.

Claims

1. In a pattern matching device for calculating an overall similarity measure between a first and a second pattern represented by a first and a second sequence of feature vectors, respectively, said device comprising first means for calculating an elementary similarity measure between each feature vector of said first sequence and each feature vector of said second sequence, and second means for iteratively calculating a recurrence formula which defines a recurrence value by a sum of each elementary similarity means and an extremum of a prescribed number of previously calculated recurrence values, said recurrence formula eventually giving said overall similarity measure, the improvement wherein said first means comprises:

means for calculating a primitive similarity measure between each feature vector of said first sequence and each feature vector of said second sequence; and

means for subtracting a predetermined value from said primitive similarity measure to provide said elementary similarity measure.

2. A pattern matching device for calculating an overall similarity measure between a first and a second pattern represented by a first and a second sequence of feature vectors, respectively, said device comprising first means for calculating an elementary similarity measure between each feature vector of said first sequence and each feature vector of said second sequence, and second means for iteratively calculating a recurrence formula which defines a recurrence value by a sum of each elementary similarity measure and an extremum of a prescribed number of previously calculated recurrence values, said recurrence formula eventually giving said overall similarity measure, the improvement wherein said first means comprises:

means for calculating a primitive similarity measure between each feature vector of said first sequence and each feature vector of said second sequence;

means for subtracting a predetermined value from said primitive similarity measure to provide said elementary similarity measure; and

said primitive similarity measure calculating means successively calculating the primitive similarity measures between each feature vector of said first sequence and a plurality of those sequential feature vectors of said second sequence which are in a range specified by the first sequence feature vector under consideration, said device comprising means for providing the total number of feature vectors of said first sequence when said overall similarity measure is given, wherein said device further comprises third means for adding a product of said predetermined value and the total number to said overall similarity measure to provide an eventual similarity measure representative of whether said first and said second patterns are similar or dissimilar to each other.

3. A pattern matching device as claimed in claim 2, wherein said second means comprises:

means for producing an overflow signal which takes first, second, and third signal values when said sum is greater than a first preselected value, is less than a second preselected value, and is neither greater than said first preselected value nor less than said second preselected value, respectively, said first preselected value being greater than said second preselected value; and

means for producing a new recurrence value signal which represents said first preselected value, said second preselected value, and said sum when said overflow signal takes said first through said third signal values, respectively, such recurrence value signals produced previously of said new recurrence value signal providing said previously calculated recurrence values.

4. A pattern matching device as claimed in claim 3, said device comprising means for generating a first and a second timing signal, said first timing signal consecutively designating the feature vectors of said first sequence, said second timing signal successively designating those feature vectors of said second sequence which are within a range specified by each feature vector designated by said first timing signal, wherein said device further comprises additional means for keeping operation of said device in progress and discontinuing said operation if said overflow signal always takes and does not always take a predetermined one of said first and said second signal values, respectively, throughout an interval of time in which each feature vector of said first sequence is designated by said first timing signal, said predetermined one signal value being said first and said second signal values when said extremum is a minimum and a maximum, respectively.

5. A pattern matching device as claimed in claim 4, wherein said additional means comprises:

means for generating a sequence of timed pulses at the beginning of the intervals of time in which said first timing signal consecutively designates the respective feature vectors of said first sequence;

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 during each of said intervals;

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 that discontinues said operation, said signal pulse producing means being further responsive to the output signal of said second level for producing none of said timed pulses to keep said operation in progress.