US 4,488,243 AGrant
Dynamic Time Warping Arrangement
Issue Date:1984-12-11
•22 Claims
•6 Drawing Sheets
Abstract
In a speech recognition system, dynamic time warp (DTW) calculations are reduced by use of a search strategy for an optimal non-linear search warp function path: signals predictive of the similarity are generated responsive to the preceding and current correspondence signals of the input word to reference warped words.
Metadata
Assignee
- AT&T Bell Laboratories
Inventors
- Michael K. Brown
- Lawrence R. Rabiner
Application Information
Application Number:US 3743071
Filing Date:1982-05-03
Priority Date:1982-05-03
Art Unit:237
Classifications
IPC:
G10L 100
Field of Search:
364381382513.541-4333;34;37
Patent Drawings (6 sheets)
Description
Background of the Invention
Our invention relates to speech analysis and, more particularly, to dynamic time warping arrangements for speech pattern recognition.
Speech recognizers permit direct input to communication, data processing and control systems. A recognizer typically has a reference vocabulary stored digitally as acoustic patterns called templates. An input utterance is converted to digital form and compared to the reference templates. The most similar template is selected as the identity of the input. An overview of automatic recognition may be found in the article by S. E. Levinson and M. Y. Liberman entitled, "Speech Recognition by Computer", Scientific American, April 1981, Vol. 244, No. 4, pages 64-76.
In order to compare an input pattern, e.g. a spoken word, with a reference, each word is divided into a sequence of time frames. In each time frame, signals representative of acoustic features of the speech pattern are obtained. For each frame of the input word, a frame of the reference word is selected. Signals representative of the similarity or correspondence between each selected pair of frames are obtained responsive to the acoustic feature signals. The correspondence signals for the sequence of input and reference word frame pairs are used to obtain a signal representative of the global or overall similarity between the input word and a reference word template.
Since there are many different ways of pronouncing the same word, the displacement in time of the acoustic features comprising the word is variable. Different utterances of the same word, even by the same individual, may be widely out of time alignment. The selection of frame pairs is therefore not necessarily linear. Matching, for example, the fourth, fifth and sixth frames of the input utterance with the fourth, fifth and sixth frames respectively of the reference word may distort the similarity measure and produce unacceptable errors.
Dynamic time warping arrangements have been developed which align the frames of a test and reference pattern in an efficient or optimal manner. The alignment is optimal in that the global similarity measure assumes an extremum. It may be, for example, that the fifth frame of the test word should be paired with the sixth frame of the reference word to obtain the best similarity measure.
In U.S. Pat. No. 3,816,722 (Sakoe et al), feature signals are obtained for the frames of input and reference words. Local correspondence signals are generated between all possible pairs of input and reference word frames within a given range or window. An extremum path of local correspondence signals is selected by a dynamic programming recursive process. The generation of all local correspondence signals within a given window, however, may be burdensome. In a simple microprocessor system, for example, the Sakoe process is comparatively slow.
It is thus an object of the invention to provide an improved arrangement for time alignment of speech patterns which abates local correspondence signal generation.
Summary of the Invention
The invention is directed to an arrangement for time aligning a first speech pattern with a second speech pattern. A time frame sequence of acoustic feature signals is generated for each speech pattern. For each successive first speech pattern time frame signal, a set of signals corresponding to second speech pattern candidate time frames is generated. A set of signals representative of the correspondence between the acoustic features of the current first speech pattern time frame and the acoustic feature signals of the second speech pattern candidate time frames is obtained. Responsive to the correspondence signals of the preceding and current first speech pattern time frames, a signal for each second speech pattern candidate time frame and the current first speech pattern time frame is generated which is predictive of the similarity of the first and second speech patterns along a path including the second speech pattern time frame and current first speech pattern time frame. Responsive to the predictive signals of the current first speech pattern time frame, one of the second speech pattern candidate time frames is selected for the current first speech pattern time frame pair.
Brief Description of the Drawing
FIG. 1 shows a microcomputer speech recognition circuit illustrative of the invention;
FIG. 2 shows a flow chart of the overall operation of the circuit in FIG. 1;
FIG. 3 shows a flow chart illustrative of the invention;
FIG. 4 shows a flow chart of the dynamic time warping operation of the circuit in FIG. 1;
FIG. 5 shows a flow chart of predicted total distance signal generation in FIG. 4; and
FIG. 6 shows a graph illustrating the operation sequence of the invention.
Detailed Description
FIG. 1 shows a general block diagram of a microcomputer speech recognizer adapted to perform the digital signal processing functions of the invention. The system of FIG. 1 may be used to identify a spoken utterance. Alternatively, the word recognition arrangement may be implemented with special purpose digital hardware, as is well known in the art.
Referring to FIG. 1, microcomputer 100 comprises input device 101, A/D (analog-to-digital) converter 102, microprocessor 103, memory 104 and utilization device 105. Data bus 106 interconnects the data terminals of converter 102, microprocessor 103, memory 104 and utilization device 105. Address bus 107 likewise interconnects the respective address terminals.
Converter 102 may be, for example, a type TDC1010J integrated circuit made by TRW, Incorporated, La Jolla, Calif. Microprocessor 103 may be, for example, a type 8086 integrated circuit made by Intel Corporation, Santa Clara, Calif. Memory 104 may be, for example, type 2118 integrated circuits made by Intel Corporation. Input device 101 may be, for example, microphone, telephone, voice storage or other communication equipment.
Utilization device 105 may be, for example, a speaker verification system or a spoken word recognizer. A spoken word recognizer is described in detail in the article by L. R. Rabiner, S. E. Levinson, A. E. Rosenberg and J. G. Wilpon entitled, "Speaker Independent Recognition of Isolated Words Using Clustering Techniques", IEEE Transactions On Acoustics, Speech, and Signal Processing, Vol. ASSP-27, No. 4, pages 336-349, August 1979.
Referring to FIG. 2, flow chart 200 shows operation and decision boxes representative of processes run by microprocessor 100. Responsive to signal START from utilization device 105, microprocessor 103 is conditioned to begin signal processing operations (box 205 in FIG. 2). An analog speech waveform from input device 101 is applied to the input of converter 102 (box 210). In converter 102, the waveform is digitized (box 215). The digitized input signal is thereby available to microprocessor 103. Responsive to the digitized input signals, microprocessor 103 obtains signals T(n) representative of the acoustic features of the input waveform (box 220). Index n specifies a particular frame of the input word, where each frame represents, for example, 45 msec of speech and adjacent frames are spaced 15 msec apart. Acoustic feature signals T(n) may be obtained on the basis of linear prediction analysis, well known in the art. Alternatively, spectral, formant derived, or other feature signals may be used. Feature signals T(n) are then normalized and linearly warped to a standard duration of, for example, N=21 time frames by microprocessor 103 (box 225). The index n therefore ranges from n=1, 2, . . . , N. Normalization and linear time warp methods of signal processing are further described in the article by C. S. Myers, L. R. Rabiner and A. E. Rosenberg entitled, "Performance Trade Offs In Dynamic Time Warping Algorithm For Isolated Word Recognition", IEEE Transactions On Acoustic, Speech, and Signal Processing, Vol. ASSP-28, pages 623-635, December 1980.
Normalized and linearly warped input feature signals T(n) are stored in memory 104. Previously obtained feature template signals R.sub.v (m) for reference words are also stored in memory 104. Subscript v of R.sub.v (m) specifies a particular reference word in a vocabulary having a total of V reference words; the range v=1, 2, . . . , V. Index m specifies a particular frame of a reference word, where the reference word frames have the same duration and spacing as the input word frames (45 and 15 msec).
Following the linear time warping operations (box 225), microprocessor 103 selects one of the reference words v for comparison with the input word (box 230). The comparison is performed by dynamic time warping signal processing in accordance with the invention (box 235). The resultant similarity signal D.sub.v is stored in memory 104 (box 240). Similarity signals D.sub.v are likewise obtained and stored for the other reference words. After the last similarity signal has been generated (box 245), the extremum similarity signal is selected in microprocessor 103 and output to utilization device 105 (box 250). The corresponding reference word index v is also supplied to device 105 as the identity of the input word. Processing for a particular input word is thereby finished (box 255).
The dynamic time warp signal processing of the invention (box 235) is conveniently illustrated with reference to graph 600 in FIG. 6. Graph 600 has a grid of points or nodes. The sequence of test frames n is mapped to the abscissa (the independent variable) and the sequence of reference frames m is mapped to the ordinate (the dependent variable). Each node represents the similarity or correspondence between the n.sup.th frame feature signals T(n) of the input word and the m.sup.th frame feature signals R.sub.v (m) of the reference word. This correspondence signal may be obtained according to the Itakura log likelihood ratio, as described in the article by F. Itakura entitled, "Minimum Prediction Residual Principle Applied to Speech Recognition", IEEE Transaction on Acoustics, Speech, and Signal Processing, Vol. ASSP-23, No. 1, pages 67-72, February, 1975:
i.e., a log of the dot product of the two vectors T(n) and R.sub.v (m).
The correspondence signal d is conventionally called the local distance because the magnitude of d increases as the correspondence between T(n) and R(m) decreases. It is to be understood, however, that other measures of similarity may be used, such as correlation coefficients which increase as the correspondence between T(n) and R(m) increases.
Since input frame index n was defined to be the independent variable, the reference frame index m may be written equivalently as a function of n:
This orientation has been found to give good performance in word recognition systems. The local distance signal in equation (1) may therefore be written as d(T(n), R.sub.v (n))). The converse orientation is also possible.
In order to optimally align the input frames n with the reference frames m, the sum of the local distance signals d(T(n)), R.sub.v (w(n))) between an input word and a reference word v are minimized: ##EQU1## Signal D.sub.v is called the total or global average distance signal for reference word v. It will be recalled that the reference word index v=1, 2 . . . V which corresponds to the minimum global distance signal is passed to utilization device 105 as the best candidate for identifying the input word. Alternatively, it may be useful to provide an ordered list of global distance signals to device 105.
In order to obtain a global average distance signal D.sub.v, it would be possible to generate a local distance signal d for every node in graph 600. The particular sequence of nodes or "path" which yields the minimum global distance signal could then be found. Such an exhaustive search, however, would not only be inefficient, it may also yield an acoustically unrealistic path. It is therefore desirable to impose certain constraints on the path.
It is assumed that the beginning and ending frames of both the input and reference words have been accurately determined. The first input frame n=1 is thus paired with the first reference frame m=1 or:
Similarly, the last input frame n=N is paired with the last reference frame m=M:
It is also assumed that the Itakura path constraints are obeyed:
These local path constraints guarantee that the average slope of the warping function w(n) lies between 1/2 and 2 and that the path is monotonic non-decreasing. In other words, the local path constraints define acoustically possible paths.
The preceding endpoint and local path constraints may be summarized by a set of global path constraints:
where
The global path constraints define the parralelogram or window shown on graph 600 of FIG. 6. Allowable paths include only nodes within the window.
According to the prior art, the minimum path can be found by a dynamic programming process. An accumulated distance signal D.sub.A at any given pair of frames n and m is defined to be the sum of the local distance signals d from node (1,1) to and including the present node (n,m), along the minimum distance or "best" path between nodes (1,1) and (n,m). Accumulated distance signal D.sub.A may be generated recursively from node (1,1) to node (N,M) according to the following equation:
where the constraints are
and where g(n,m) is the nonlinear weighting ##EQU2## to guarantee that the optimum path to (n,m) does not stay flat for two consecutive frames. The desired global distance signal D.sub.v for a reference word v is thereby equal to the accumulated distance signal D.sub.A (N,M).
The preceding dynamic time warping process requires the generation of a local distance signal at every node within the window in graph 600. Local distance signal generation, however, is comparatively slow in a simple microprocessor. According to the invention, therefore, local distance signals are generated only at nodes which are likely candidates for the minimum path.
Referring to graph 600, the i.sup.th node is designated by its coordinates n and m:
The starting node s is defined as s=(1,1) and the ending or terminal node t is defined as t=(N,M). In the present example, N=M=21.
An accumulated distance signal g(i) is defined as the sum of the local distance signals d along the best path from starting node s to and including node i. The best path comprises the sequence of nodes preceding node i which has the minimum total distance.
A second accumulated distance signal h(i) is defined as the sum of the local distance signals d along the best path from node i to ending node t. Beginning at node s=(1,1) and proceeding from left to right on graph 600, signal g(i) may be known exactly at any node i. Signal h(i), on the other hand, is not known and therefore must be estimated or predicted. The predictor of h(i) is designated h(i).
From accumulated distance signal g(i) and predictor signal h(i), a predicted total distance signal f(i) may be found according to equation (15):
Signal f(i) represents the predicted total distance of a path from node s to node t which passes through node i.
Before describing how predictor h(i) is itself generated, the use of h(i) in accordance with the invention to generate local distance signals only at likely candidate nodes is detailed immediately below.
The nodal state at any node i is defined to include: the predictor signal h(i), the accumulated distance signal g(i), and a pointer signal (address) to the previous or "parent" node on the path. The path from start node s to any intermediate node i is thus completely characterized by the nodal state of node i and its predecessor nodes.
In searching for the minimum distance path through graph 600, generally nodes from several possible paths are encountered. The nodal state of the last node on each of the possible paths is entered on an "open list". The entries are sorted so that the nodal state of the last node of the path which has the lowest total distance f(i) is at the top of the list. The top nodal state is then removed from the open list and entered at the top of a "closed list". The top nodal state from the closed list is "expanded", that is, all permissible successor nodes are selected. New total distance f(i) are generated for each successor node. The nodal state information for each successor node is sorted into the open list and the process repeats until the terminal node t is identified. The distance g(t) at node t becomes minimum distance signal D.sub.v.
The preceding search process may be summarized in accordance with the invention as illustrated by flow chart 300 in FIG. 3. Acoustic feature signals are generated for first and second speech patterns (box 305). The first and second speech patterns may correspond to, for example, a test word and a reference word, respectively. A current first speech pattern time frame is generated (box 310). A second speech pattern candidate time frame is generated for the current first speech pattern time frame (box 320). Correspondence signals are generated between the acoustic feature signals of the current first speech pattern time frame and the acoustic feature signals of the second speech pattern candidate time frame (box 330). A predicted similarity signal is generated for a path which includes the second speech pattern candidate time frame and the current first speech pattern time frame (box 340). The generation of correspondence and predictor signals (boxes 320, 330 and 340) is repeated for each second speech pattern candidate time frame and the current first speech pattern time frame (box 350). One of the second speech pattern candidate time frames is then selected for the current first speech pattern time frame pair (box 360). The operations (boxes 310-360) are repeated for each successive first speech pattern time frame signal.
The search process of the invention may be implemented by microprocessor 103. Microprocessor 103 is controlled by instruction codes stored in memory 104. The instruction codes are listed in FORTRAN language form in Appendix 1. The operations in accordance with the instruction codes may be illustrated with reference to flow chart 400 in FIG. 4 and graph 600 in FIG. 6. The open and closed lists are initialized, that is, cleared or reset (box 405). The nodal state of start node s=(1,1) is then entered at the top of the open list (box 405). The top entry from the open list is removed and placed at the top of the closed list for expansion (box 410). A successor node is generated, subject to the local constraints (box 415). In the case of start node s=(1,1), nodes (2,1), (2,2) and (2,3) are the three legal successors. In graph 600 generally, permitted successor nodes are joined by a line to their predecessor or parent node.
If a successor node is generated (box 420), the open and closed lists are checked to see if the node appears on either list (box 425). If the node appears on the closed list, it need not be added to the open list since an optimal path to this node was already found. Furthermore, if the successor node already appears on the open list it need not be added again since the path by which this node was previously generated is optimal to the expanded node and must be of lower distance than the path currently under consideration, or else it would not have been expanded previously (box 430).
The successor node is next checked against the global constraints (box 435). If the node is within the boundaries of the window (box 440), a pointer to the parent node is saved, a local constraints parameter is set and the accumulated local distance signal g(i) is generated (box 445). The local constraints parameter is required according to equation (13) so that the path is forced to rise by 1 every other node.
If the successor node is not the terminal node t (box 450), the predicted total distance f(i) is generated. Based on signal f(i), the nodal state of the successor node is sorted onto the open list (box 455). Another successor node is selected (box 415) and processed (boxes 420-455) until all the legal successor nodes have been generated and their corresponding nodal states sorted onto the open list. When no additional successor nodes can be generated (box 420), the successor node having the lowest f(i) is selected as the new parent node (box 410). The parent node is expanded as above.
The process repeats (boxes 410-455) until a successor node is identified as the terminal node t (box 450). The global distance D.sub.v is equal to g(t), that is, the accomulated distance at node t (box 465). The process of comparing one input word and one reference word is thereby finished.
In FIG. 6, the search process begins at node s=(1,1). Of the possible successor nodes (2,1), (2,2) and (2,3); node (2,1) has the lowest predicted total distance f(i) and is therefore selected for expansion. In graph 600, numerals designate (in order) the nodes selected for expansion; node (2,1) is labeled node 1.
Recalling that the path is constrained to rise by 1 every other frame, node 1 has two possible successor nodes: nodes (3,2) and (3,3). Node (3,3), labeled node 2, has the lowest f(i) and is therefore expanded. This process continues until node 17 is expanded. The possible successors to node 17, nodes (19,19) and (19,20) are both found to have a larger predicted total distance f(i) than node (8,7). Node (8,7) therefore becomes node 18 and is expanded.
The possible successor nodes (9,8) and (9,9), are shown connected by dotted lines to parent node 18 in graph 600. Node (9,9) is eliminated from further consideration since it was previously encountered when node 7 was expanded. Node (9,8), on the other hand, is found to have a greater predicted total distance f(i) than node (19,19). Node (19,19) therefore becomes node 19 and is expanded. Node 19 is next expanded to node 20 and finally node t is reached with a minimal total distance.
The savings in the number of local distance signals d that must be generated (in this example where N=21 frames) over a conventional dynamic programming process is approximately the ratio of the unconnected nodes to connected nodes in graph (600), or about 2 to 1. The savings have been found experimentally to be even better--about 3 to 1--in a more usual case where N=42 frames.
Returning now to consideration of the predictor h(i), it will be recalled that h(i) is summed together with accumulated local distance signal g(i) to give the total estimated distance f. Predictor h(i) may be generated in several ways. It may be, for example, a fixed estimator of the form
where .alpha. is a parameter of the estimator. This fixed form, however, may be a gross underestimate of the accumulated distance from node i to node t when the input and reference words are from different acoustic classes.
Preferably, predictor signal h(i) may be generated adaptively according to the equation: ##EQU3## The predictor of equation (17) has the advantage that for input and reference words from different acoustic classes, g(i)/n becomes large and forces h into the proper range.
Experimentation with the predictor of equation (17) showed that the resulting path distances were insensitive to .alpha. over a wide range. Based on this experimentation, a value of .alpha.=0.7, for example, is suitable.
The efficiency of the path search process can be improved further by forcing .alpha. to become much larger than 0.7 when preliminary results indicate that the test and reference words come from different acoustic classes. This makes h(i) predominant in generating f(i) and thereby minimizes backing up during the search. Predictor h(i) may be accordingly generated as follows: ##EQU4## where .beta. is the largest reasonable average distance expected when comparing test and reference words of the same acoustic class. Values of .beta. between about 0.6 and 0.7, for example, are suitable.
Referring to FIG. 5, flow chart 500 shows the generation of predictor signal h(i) and predicted total distance signal f(i). Flow chart 500 illustrates in detail the operations of box 455 in FIG. 4. If accumulated distance signal g(i) divided by the input frame index n is less than average distance .alpha. (box 510), the parameter .alpha. is set equal to 0.7 (box 520). On the other hand, if g(i)/n is greater than or equal to .beta., .alpha. is set to 2.0 (box 530). The process continues (box 540) and predictor signal h(i) is generated in accordance with equation (18) (box 550). Accumulated distance signal g(i) and predictor signal h(i) are combined to generate predicted total distance signal f(i) (box 550).
While the invention has been shown and described with reference to a preferred embodiment, various modifications and changes may be made by one skilled in the art without departing from the spirit and scope of the invention. The sequence of nodes which comprise the optimal path, for example, may be optionally recovered by backtracking through the closed list of nodal states (box 460).
Claims
What is claimed is:
1. A method for time aligning a first speech pattern with a second speech pattern comprising the steps of: generating a time frame sequence of signals representative of the acoustic features of the first speech pattern, generating a time frame sequence of signals representative of the acoustic features of the second speech pattern, and pairing each first speech pattern time frame with one of the second speech pattern time frames responsive to the first speech pattern feature signals and the second speech pattern feature signals, the time frame pairing comprising; generating a series of signals representative of the succession of first speech pattern time frames, responsive to each successive first speech pattern time frame signal, performing the steps of, generating a set of signals corresponding to second speech pattern candidate time frames for the current first speech pattern time frame, generating a set of signals representative of the correspondence between the acoustic feature signals of the current first speech pattern time frame and the acoustic feature signals of the second speech pattern candidate time frames, generating a signal for each second speech pattern candidate time frame and the current first speech pattern time frame predictive of the similarity of the first and second speech patterns along a path including the second speech pattern candidate time frame and current first speech pattern time frame responsive to the correspondence signals of the preceding and current first speech pattern time frames, and selecting one of the second speech pattern candidate time frames for the current first speech pattern time frame pair responsive to the predictor signals of the current first speech pattern time frame.
2. The method of claim 1 wherein the correspondence signals are distance signals.
3. The method of claim 2 wherein each predictive signal f is generated according to where i is the index of a node which comprises the current first speech pattern time frame and one of the second speech pattern candidate time frames, g(i) is the minimum accumulated distance of the current and predecessor nodes and h(i) is the predicted accumulated distance of successor nodes.
4. The method of claim 3 wherein the predictor signal h(i) is generated according to ##EQU5## where .alpha. is a parameter of predictor h(i), n is the current first speech pattern time frame and N is the last first speech pattern time frame.
5. The method of claim 4 wherein the parameter .alpha. is approximtely 0.7.
6. The method of claim 4 wherein the parameter .alpha. is approximately 0.7 if ##EQU6## and the parameter .alpha. is approximately 2.0 if ##EQU7## where .beta. is the average distance expected between comparisons of speech patterns from the same acoustic class.
7. The method of claim 6 wherein the average distance .beta. is in the range of about 0.6 to 0.7.
8. The method of claim 2 wherein each first speech pattern acoustic feature signal T(n) is a linear predictive feature of the n.sup.th time frame of the first speech pattern, and each second speech pattern acoustic feature signal R(m) is a linear predictive feature of the m.sup.th time frame of the second speech pattern.
9. The method of claim 8 wherein the distance signals are generated according to where .multidot. represents the dot product.
10. Apparatus for time aligning a first speech pattern with a second speech pattern comprising: means for generating a time frame sequence of signals representative of the acoustic features of the first speech pattern, means for generating a time frame sequence of signals representative of the acoustic features of the second speech pattern, and means responsive to the first speech pattern feature signals and the second speech pattern feature signals for pairing each first speech pattern time frame with one of the second speech pattern time frames, the time frame pairing means comprising; means for generating a series of signals representative of the succession of first speech pattern time frames, means for generating a set of signals corresponding to second speech pattern candidate time frames for the current first speech pattern time frame, means for generating a set of signals representative of the correspondence between the acoustic features of the current first speech pattern time frame and the acoustic feature signals of the second speech pattern candidate time frames, means responsive to the correspondence signals of the preceding and current first speech pattern time frames for generating a signal for each second speech pattern candidate time frame and the current first speech pattern time frame predictive of the similarity of the first and second speech patterns along a path including the second speech pattern candidate time frame and current first speech pattern time frame, and means responsive to the predictor signals of the current first speech pattern time frame for selecting one of the second speech pattern candidate time frames for the current first speech pattern time frame pair.
11. The apparatus of claim 10 wherein the correspondence signals are distance signals.
12. The apparatus of claim 11 wherein each predictive signal f is generated according to where i is the index of a node which comprises the current first speech pattern time frame and one of the second speech pattern candidate time frames, g(i) is the minimum accumulated distance of the current and predecessor nodes and h(i) is the predicted accumulated distance of successor nodes.
13. The apparatus of claim 12 wherein the predictor signal h(i) is generated according to ##EQU8## where .alpha. is a parameter of predictor h(i), n is the current first speech pattern time frame and N is the last first speech pattern time frame.
14. The method of claim 13 wherein the parameter .alpha. is approximately 0.7.
15. The apparatus of claim 13 wherein the parameter .alpha. is approximately 0.7 if ##EQU9## and the parameter .alpha. is approximately 2.0 if ##EQU10## where .beta. is the average distance expected between comparisons of speech patterns from the same acoustic class.
16. The apparatus of claim 15 wherein the average distance .beta. is in the range of about 0.6 and 0.7.
17. The apparatus of claim 10 wherein each first speech pattern acoustic feature signal T(n) is a linear predictive feature of the n.sup.th time frame of the first speech pattern, and each second speech pattern acoustic feature signal R(m) is a linear predictive feature of the m.sup.th time frame of the second speech pattern.
18. The apparatus of claim 17 wherein the distance signals are generated according to where .multidot. represents the dot product.
19. A method for recognizing an input speech pattern as one of a set of reference speech patterns comprising the steps of: comparing each reference speech pattern with the input speech pattern, each comparison comprising the steps of; generating a time frame sequence of signals representative of the acoustic features of the input speech pattern, storing a time frame sequence of signals representative of the acoustic features of the current reference speech pattern, pairing each input speech pattern time frame with one of the current reference speech pattern time frames responsive to the input speech pattern feature signals and the current reference speech pattern time frame signals, and generating a signal representative of the correspondence between the input speech pattern and the current reference speech pattern responsive to the time frame pairs, the time frame pairing comprising; generating a series of signals representative of the succession of input speech pattern time frames, responsive to each successive input speech pattern time frame signal, performing the steps of, generating a set of signals corresponding to reference speech pattern candidate time frames for the current input speech pattern time frame, generating a set of signals representative of the correspondence between the acoustic feature signals of the current input speech pattern time frame and the acoustic feature signals of the reference speech pattern candidate time frames, generating a signal for each reference speech pattern candidate time frame and the current input speech pattern time frame predictive of the similarity of the input and reference speech patterns along a path including the reference speech pattern candidate time frame and current input speech pattern time frame responsive to the correspondence signals of the preceding and current input speech pattern time frames, and selecting one of the reference speech pattern candidate time frames for the current input speech pattern time frame pair responsive to the predictor signals of the current input speech pattern time frame.
20. The method of claim 19 wherein the reference speech patterns are spoken words.
21. Apparatus for recognizing an input speech pattern as one of a set of reference speech patterns comprising: means for comparing each reference speech pattern with the input speech pattern, the comparing means comprising; means for generating a time frame sequence of signals representative of the acoustic features of the input speech pattern, means for storing a time frame sequence of signals representative of the acoustic features of the current reference speech pattern, means for pairing each input speech pattern time frame with one of the current reference speech pattern time frames responsive to the input speech pattern feature signals and the current reference speech pattern time frame signals, and means for generating a signal representative of the correspondence between the input speech pattern and the current reference speech pattern responsive to the time frame pairs, the time frame pairing means comprising; means for generating a series of signals representative of the succession of input speech pattern time frames, means for generating a set of signals corresponding to reference speech pattern candidate time frames for the current input speech pattern time frame, means for generating a set of signals representative of the correspondence between the acoustic features of the current input speech pattern time frame and the acoustic feature signals of the reference speech pattern candidate time frames, means responsive to the correspondence signals of the preceding and current input speech pattern time frames for generating a signal for each reference speech pattern candidate time frame and the current input speech pattern time frame predictive of the similarity of the input and reference speech patterns along a path including the reference speech pattern candidate time frame and current input speech pattern time frame, and means responsive to the predictor signals of the current input speech pattern time frame for selecting one of the reference speech pattern candidate time frames for the current input speech pattern time frame pair.
22. The apparatus of claim 21 wherein reference speech patterns are spoken words.
Patent Citations (2)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3816722 | 1974-06-01 | Sakoe et al. | |
| US4256924 | 1981-03-01 | Sakoe |
Non-Patent Literature (6)
- "Speech Recognition by Computer", S. E. Levinson et al., Scientific American, vol. 244, No. 4, Apr. 1981, pp. 64-76.
- "Speaker-Independent Recognition of Isolated Words Using Clustering Techniques", L. R. Rabiner et al., IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-27, No. 4, Aug. 1979, pp. 336-349.
- "Performance Tradeoffs in Dynamic Time Warping Algorithms for Isolated Word Recognition", C. Myers et al., IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-28, No. 6, Dec. 1980, pp. 623-635.
- "Minimum Prediction Residual Principle Applied to Speech Recognition", F. Itakura, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-23, No. 1, Feb. 1975, pp. 67-72.
- "State-Space Search Methods", Problem-Solving Methods in Artificial Intelligence, McGraw-Hill, 1971, N. J. Nilsson, pp. 43-77.
- "The Harpy Speech Understanding System", B. Lowerre et al., Prentice-Hall, Inc., Trends in Speech Recognition, 1980, Chapt. 15, pp. 340-360.