Automatic continuous speech recognition system employing dynamic programming

• US 4,059,725 A
• Filed: 12/21/1976
• Issued: 11/22/1977
• Est. Priority Date: 03/12/1975
• 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): Claffy, Kathleen H.
• Assistant Examiner(s): Kemeny, E. S.
• Application Number:
  US05/753,072
• Time in Patent Office: 336 Days
• Field of Search: 235/152, 235/181, 179/1.5 A, 179/1.5 D, 179/1.5 B
• 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/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]

Abstract

A speech pattern recognition system for continuous speech is disclosed. The system includes calculating means which calculates similarity measures between an input pattern and all of the series of patterns including reference word-patterns arranged in all possible orders through a pattern matching process without resorting to a segmentation process. The reference pattern which provides the maximum similarity measure is adopted as the recognized result.

Claims

1. A speech pattern recognition system for continuous speech composed of a series of words pronounced word by word, said system comprising:

means for producing from said continuous speech an input pattern A representative of time sequences of feature vectors a₁, a₂ - - - a_i, - - - a_I ;

first memory means for storing said input pattern A;

second memory means for storing n reference word patterns Bⁿ, each representing by time sequences of feature vectors b₁ⁿ, b₂ⁿ, - - -b_jⁿ, - - - b_jnⁿ ;

means for reading out a partial pattern A(l,m) which is a part of said input pattern A extending from a time point l to another time point m (1≦

l<

m≦

I), said partial pattern A(l,m) being represented by time sequence of feature vectors a_l+1, a_l+2, - - - a_i, - - - a_m ;

first means for calculating through dynamic programming similarity measures S(A(l,m), Bⁿ) between said partial pattern A(l,m) and said reference word pattern Bⁿ ;

means for extracting the maximum value of the partial similarity measures S<

l,m>

with respect to n words;

means for providing a partial recognized result n<

l,m>

which is a word in said n words and by which said partial similarity measure S<

l,m>

is obtained;

third memory means for said partial similarity measure s<

l,m> and

said partial recognized result n<

l,m>

obtained with respect to said time points l and m;

means for dividing said input pattern A to Y partial patterns A(l.sub.(x-1), L.sub.(x)) (X = 1, 2, 3, - - - Y), said input pattern A being composed of Y words and having (Y -

     1) breaking points l.sub.(1), l.sub.(2) - - - l.sub.(x) - - - l.sub.(Y-1) ;

means responsive to said partial similarity measure S<

l,m> and

said partial recognized result n<

l,m>

for reading out the partial similarity measures S<

O,l.sub.(1) >

, S<

l.sub.(1),l.sub.(2) >

, - - - S<

l.sub.(x-1), l.sub.(x) >

, - - - S<

l_Y-1), l.sub.(Y) >

with respect to the combinations (O,l.sub.(1)), (l.sub.(1), l.sub.(2)), - - - (l.sub.(x-1), l.sub.(x)), - - - (l.sub.(Y-1), l.sub.(Y)) of said breaking points;

second means for calculating the maximum value of the sum of said partial similarity measures S>

O,l.sub.(1) >

+S<

l.sub.(1), l.sub.(2) >

+- - - + S<

l.sub.(x-1), l.sub.(x) >

- - - + S<

l.sub.(Y-1), l.sub.(Y) >

; and

means responsive to said second calculating means and said partial recognized result n, m for providing Y words.

2. A speech pattern recognition system as recited in claim 1 wherein said first means for calculating similarity measures comprises:

recurrence coefficient calculating means for successively calculating recurrence coefficients g(i, j) for each similarity quantity s(c_i, b_j) defined as ##EQU16## starting from the initial condition

space="preserve" listing-type="equation">j = 1

space="preserve" listing-type="equation">g(1,

     1) = s(c.sub.1, b.sub.1)

and arriving at the ultimate recurrence coefficient g(I, J) for i = I and j = J within a domain of m'"'"'s satisfying the expression

space="preserve" listing-type="equation">l + J.sub.n + r - 1 ≦

m ≦

l + J.sub.n + J.sub.n + r - 1

to obtain said similarity measures.

3. A speech pattern recognition system as recited in claim 1 wherein said first means for calculating similarity measures comprises:

recurrence coefficient calculating means for successively calculating recurrence coefficients g(i, j) for each similarity quantity S(C_i, b_j) defined as ##EQU17## starting from the initial condition

space="preserve" listing-type="equation">j = 1

space="preserve" listing-type="equation">g(1,

     1) = s(c.sub.1, b.sub.1)

and arriving at the ultimate recurrence coefficient g(I, J) for i = I and j = J, and

a first register for storing said recurrence coefficients g(i, j).

4. A speech pattern recognition system as recited in claim 2 wherein said second means for calculating the maximum value of the sum of said partial similarity measures comprises:

first recurrence calculating means for calculating the expression

space="preserve" listing-type="equation">T(m) = Max [S <

h, m>

+ T(h) ] h<

m

where m = 1 - I,

starting from the initial condition T(O) = 0 and continuing to T(I) from m = I to provide h(m) defined as

space="preserve" listing-type="equation">h(m) = argmax [S <

h, m>

+ T(h)] h <

m

where the operator "argmax" stands for "h" for which the expression in the square bracket [ ] has a maximum value, with reference to said partial similarity measures S <

l, m>

, and

second recurrence calculating means for calculating the expression

space="preserve" listing-type="equation">l.sub.(x) = h(l.sub.(x+1))

from the initial condition l.sub.(r) = J to the ultimate recurrence coefficient l(O) = 0 referring to h(m) to obtain the number Y of the words and breaking points l.sub.(x).

5. A speech pattern recognition system as recited in claim 3 wherein said second means for calculating the maximum value of the sum of said partial similarity measures comprises:

recurrence calculating means for calculating the expression

space="preserve" listing-type="equation">T(m) = Max [S <

h, m>

+ T(h)] h<

m

where m = 1-I,

starting from the initial condition T(0) = 0 and continuing to T(I) for m = I to provide T(m), N(m) and h(m) defined as

space="preserve" listing-type="equation">N(m) = n <

h(m), m>

space="preserve" listing-type="equation">h(m) = argmax [S <

h, m>

+ T(h)] h <

m

where the operator "argmax" stands for "h" for which the expression in the square bracket [ ] has a maximum value, with reference to said partial similarly measures S <

l, m>

, and

fourth memory means for storing the calculated values T(m), N(m) and h(m0).