Pattern matching apparatus

• US 4,742,547 A
• Filed: 07/28/1987
• Issued: 05/03/1988
• Est. Priority Date: 09/03/1982
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Watanabe, Takao
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Mills, III, John G.
• Application Number:
  US07/080,249
• Time in Patent Office: 280 Days
• Field of Search: 381/51, 381/41-50, 364/513, 364/513.5, 364/900 MS File, 382/30, 382/37, 382/34
• US Class Current: 704/241
• CPC Class Codes: G10L 15/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]

Abstract

A pattern matching apparatus wherein an input pattern is compared against a reference pattern by a distance or similarity measure (d_ij) between data at respective time points (i, j) of the two patterns. An integration variable (g_ij) of the distance measure is developed along a time path between the time axes of the two patterns to provide a measure of pattern matching. According to the invention, the path may deviate from 45°, i.e. the input pattern becomes locally time-compressed or time-expanded, only toward the time axis of the longer pattern. Therefore, local time compression or expansion is allowed only if the total input pattern length requires time compression or expansion, respectively, to match the total length of the reference pattern.

Claims

1. A pattern matching apparatus for speech pattern recognition comprising:

first means for developing a first quantity representing a distance or similarity measure between feature vectors at respective time points (i, j) of first and second patterns, each of said first and second patterns expressed by a time sequence of feature vectors, along time axes;

second means for developing a second quantity which is an integration quantity of said first quantity at integration time point (i, j) on the basis of said first quantity at time points including at least said integration time point and a plurality of second quantities obtained at a plurality of predetermined time points previous to said integration time point (i, j); and

comparison means for comparing lengths I, J of said first and second patterns with each other and producing a signal for selecting said plurality of predetermined time points in said second means in accordance with the result of the comparison.

2. The pattern matching apparatus as defined in claim 1 wherein said second means develops said second quantity g(i, j) in accordance with the following formulas:

when I≧

J;

##EQU9## when I<

J;

##EQU10##

3. The pattern matching apparatus as defined in claim 1 wherein said second means develops said second quantity g(i, j) in accordance with the following formulas:

when I≧

J;

##EQU11## when I<

J;

##EQU12##

4. The pattern matching apparatus as defined in claim 1 further including means for weighting said first quantity as the basis for obtaining said second quantity.

5. The pattern matching apparatus as defined in claim 1 wherein said predetermined time points are determined in accordance with the comparison result of I and J so that the slope constraint of the advance of matching path when developing said second quantity is limited at 45°

as the boundary.

6. The pattern matching apparatus as defined in claim 1 wherein said first and second patterns are input and reference patterns of speech, respectively.

7. A pattern matching apparatus for speech pattern recognition comprising:

first and second memories for storing first and second patterns, each expressed as a time sequence of feature vectors, respectively;

first means for calculating a first quantity of a distance or similarity measure between said first and second patterns at each time point (i,j);

a third memory for storing said first quantity thus obtained;

comparison means for generating a signal S₁ or S₂ when the length of said first pattern is longer or shorter, respectively, than that of said second pattern;

second means for developing a second quantity which is an integration quantity of said first quantity at a time point (i,j) on the basis of said first quantity at said time point and the second quantity obtained at a plurality of time points predetermined in response to said signals S₁ and S₂ at time points previous to said time point (i,j); and

fourth memory for storing said second quantity obtained from said second means.