Pattern matching method, apparatus and computer readable memory medium for speech recognition using dynamic programming
First Claim
1. An apparatus for performing a dynamic programming pattern matching process, the apparatus comprising:
- input means for inputting a sequence of input patterns representative of an input signal;
memory means for storing a plurality of sequences of references patterns, each sequence being representative of a reference signal;
means for processing a current input pattern with respect to at least some of the reference signals in turn, comprising;
(1) means for defining as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for the current into pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and for listing the active patterns for the current input pattern in a current active list;
(2) means for storing in a store associated with each active pattern, a cumulative value representative of a score for the dynamic programming path which ends at that active pattern for said current input pattern; and
(3) means for processing each active pattern of said current reference signal in reverse sequential order, to update said cumulative values and to propagate said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, said active pattern processing means comprising;
(A) means for updating the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and
(B) means for propagating the dynamic programming path associated with the current active pattern, and for listing, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in a new active list; and
wherein said propagating means is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the propagating means can propagate each dynamic programming path without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of said active pattern processing means processing preceding active patterns of the current reference signal.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for matching an input pattern with a number of stored reference patterns using a dynamic programming matching technique is described. The reference patterns of a reference signal which are at the end of a dynamic programming path for a current input pattern are listed in an active list. The dynamic programming paths are propagated by processing the reference patterns on the active list, and a new active list is generated for the succeeding input pattern. The amount of processing required for each pattern on the active list is reduced by using a pointer which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed on the new active list during the processing of a preceding dynamic programming path. In a second aspect, a speech recognition interface is used as a control system for a telephony system.
-
Citations
133 Claims
-
1. An apparatus for performing a dynamic programming pattern matching process, the apparatus comprising:
-
input means for inputting a sequence of input patterns representative of an input signal; memory means for storing a plurality of sequences of references patterns, each sequence being representative of a reference signal; means for processing a current input pattern with respect to at least some of the reference signals in turn, comprising; (1) means for defining as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for the current into pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and for listing the active patterns for the current input pattern in a current active list; (2) means for storing in a store associated with each active pattern, a cumulative value representative of a score for the dynamic programming path which ends at that active pattern for said current input pattern; and (3) means for processing each active pattern of said current reference signal in reverse sequential order, to update said cumulative values and to propagate said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, said active pattern processing means comprising; (A) means for updating the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and (B) means for propagating the dynamic programming path associated with the current active pattern, and for listing, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in a new active list; and wherein said propagating means is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the propagating means can propagate each dynamic programming path without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of said active pattern processing means processing preceding active patterns of the current reference signal. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 117, 118, 119)
-
-
26. A speech recognition apparatus for recognizing an input speech signal by comparing it with a plurality of reference speech signals, the apparatus comprising:
-
means for extracting a sequence of input patterns representative of an input speech signal; means for storing sequences of reference patterns, each sequence being representative of a corresponding reference speech signal; means for matching the sequence of input patterns with the reference speech signal, using an apparatus for performing a dynamic programming pattern matching process, the dynamic-programming-pattern-matching-process apparatus comprising; input means for inputting a sequence of input patterns representative of an input signal; memory means for storing a plurality of sequences of references patterns, each sequence being representative of a reference signal; and means for processing a current input pattern with respect to at least some of the reference signals in turn, comprising; (1) means for defining as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for the current input pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and for listing the active patterns for the current input pattern in a current active list; (2) means for storing in a store associated with each active pattern, a cumulative value representative of a score for the dynamic programming path which ends at that active pattern for said current input pattern; and (3) means for processing each active pattern of said current reference signal in reverse sequential order, to update said cumulative values and to propagate said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, said active pattern processing means comprising; (a) means for updating the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and (b) means for propagating the dynamic programming path associated with the current active pattern, and for listing, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in a new active list; and wherein said propagating means is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the propagating means can propagate each dynamic programming path without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of said active pattern processing means processing preceding active patterns of the current reference signal, and wherein said input signal is a speech signal, and wherein each input pattern comprises a number of parameters representative of the acoustic properties of the speech signal during a corresponding time frame; and means for providing a recognition result from cumulative values determined by said matching means. - View Dependent Claims (27)
-
-
28. A computer-readable memory medium storing a computer-readable program embodied therein for instructing a computer to perform a dynamic programming pattern matching process between a sequence of input patterns representative of an input signal, and a number of stored sequences of reference patterns, each sequence being representative of a reference signal, wherein the program instructs the computer to process each input pattern in turn with respect to at least some of the reference signals, said program comprising:
-
(1) a defining instructing means for instructing the computer to define as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for a current input pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and for instructing the computer to list the active patterns for the current input pattern in a current active list; (2) a storing instructing means for instructing the computer to, for each active pattern, store in a store associated with that active pattern, a cumulative value representative of a score for the dynamic programming path which ends at that active pattern for said current input pattern; and (3) an updating and propagating instructing means for instructing the computer to update said cumulative values and to propagate said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, by processing each active pattern of said current reference signal in reverse sequential order, comprising; (A) an updating instructing means for instructing the computer to update the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and (b) (B) a first propagating instructing means for instructing the computer to propagate the dynamic programming path associated with the current active pattern, and to list, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in a new active list; and wherein the propagating operation for each dynamic programming path for a current reference signal is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the propagation of each dynamic programming path is achieved without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of processing preceding active patterns. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52)
-
-
53. Computer executable software stored on a computer-readable medium, for instructing a computer to perform speech recognition to recognize an acoustic speech signal produced by a user and input into a microphone which produces an electrical speech signal representative thereof by comparing the electrical speech signal with a plurality of reference speech signals, the software comprising:
-
a first instruction for instructing the computer to extract a sequence of input patterns from the input electrical speech signal representative of the input acoustic speech signal produced by the user; a second instruction for instructing the computer to store sequences of reference patterns, each sequence being representative of a corresponding reference speech signal; a third instruction for instructing the computer to match the sequence of input patterns with the reference speech signal using a dynamic programming pattern matching process, the third instruction comprising a fourth instruction for instructing the computer to process a current input pattern with respect to at least some of the reference signals in turn, said fourth instruction comprising; a fifth instruction for instructing the computer to define as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for the current into pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and for listing the active patterns for the current input pattern in a current active list; a sixth instruction for instructing the computer to store in a store associated with each active pattern, a cumulative value representative of a score for the dynamic programming path which ends at that active pattern for said current input pattern; and a seventh instruction for instructing the computer to process each active pattern of said current reference signal in reverse sequential order, to update said cumulative values and to propagate said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, said seventh instruction comprising; an eighth instruction for instructing the computer to update the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and a ninth instruction for instructing the computer to propagate the dynamic programming path associated with the current active pattern, and for listing, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in a new active list; and wherein said ninth instruction instructs the computer to control the propagating means using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the ninth instruction instructs the computer to propagate each dynamic programming path without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of said seventh instruction instructing the computer to process preceding active patterns of the current reference signal; and a tenth instruction for instructing the computer to display recognized speech derived from the cumulative values caused to be determined by said third instruction or to use the recognized speech as operator commands to control at least one operation of the computer from the cumulative values caused to be determined by said third instruction. - View Dependent Claims (54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77)
-
-
78. A computer-readable memory medium for storing a first computer-readable program embodied therein for instructing a computer to perform a speech recognition process for recognizing an input speech signal by comparing it with a plurality of reference speech signals, the first program comprising:
-
an extracting instructing means for causing the computer to extract a sequence of input patterns representative of said input speech signal; a first storing instructing means for causing the computer to store sequences of reference patterns, each sequence being representative of a corresponding reference speech signal; a matching instructing means for causing the computer to match the sequence of input patterns with the reference speech signals, the matching instructing means comprising; a second program instructing means embodied for instructing a computer to perform a dynamic programming pattern matching process between a sequence of input patterns representative of an input signal, and a number of stored sequences of reference patterns, each sequence being representative of a reference signal, wherein the second program instructing means instructs the computer to process each input pattern in turn with respect to at least some of the reference signals, said second program instructing means comprising; (1) a defining instructing means for instructing the computer to define as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for a current input pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and for instructing the computer to list the active patterns for the current input pattern in a current active list; (2) a second storing instructing means for instructing the computer to, for each active pattern, store in a store associated with that active pattern, a cumulative value representative of a score for the dynamic programming path which ends at that active pattern for said current input pattern; and (3) an updating and propagating instructing means for instructing the computer to update said cumulative values and to propagate said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, by processing each active pattern of said current reference signal in reverse sequential order, comprising; (A) an updating instructing means for instructing the computer to update the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and
then(B) a first propagating instructing means for instructing the computer to propagate the dynamic programming path associated with the current active pattern, and to list, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in a new active list; and wherein the propagating operation for each dynamic programming path for a current reference signal is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the propagation of each dynamic programming path is achieved without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of processing preceding active patterns; and a providing instructing means for causing the computer to provide a recognition result from cumulative values determined by said matching step. - View Dependent Claims (79)
-
-
80. A speech recognition apparatus for recognizing all input speech signal by comparing it with a plurality of reference speech signals, the apparatus comprising:
-
a first circuit configured to extract a sequence of input patterns representative of an input speech signal from an input speech signal; a second circuit configured to store sequences of reference patterns, each sequence being representative of a corresponding reference speech signal; a third circuit configured to match the sequence of input patterns with the reference speech signal, using a fourth circuit configured to perform a dynamic programming pattern matching process, the fourth circuit comprising; a fifth circuit configured to input the sequence of input patterns representative of an input speech signal; and a sixth circuit configured to process a current input pattern with respect to at least some of the reference signals in turn, comprising; (1) a seventh circuit configured to define as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for the current input pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and for listing the active patterns for the current input pattern in a current active list; (2) an eighth circuit configured to store in a storeassociated with each active pattern, a cumulative value representative of a score for the dynamic programming path which ends at that active pattern for said current input pattern; and (3) a ninth circuit configured to process each active pattern of said current reference signal in reverse sequential order, to update said cumulative values and to propagate said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, ninth circuit comprising; (a) a tenth circuit configured to update the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and (b) an eleventh circuit configured to propagate the dynamic programming path associated with the current active pattern, and for listing, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in a new active list; and wherein said eleventh circuit is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the propagating means can propagate each dynamic programming path without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of said ninth circuit processing preceding active patterns of the current reference signal, and wherein said input signal is a speech signal, and wherein each input pattern comprises a number of parameters representative of the acoustic properties of the speech signal during a corresponding time frame; and a twelfth circuit configured to provide a recognition result from cumulative values determined by said third circuit. - View Dependent Claims (81)
-
-
82. An apparatus for performing a dynamic programming pattern matching process, the apparatus comprising:
-
a first circuit configured to input a sequence of input patterns representative of an input signal; a second circuit configured to store a plurality of sequences of references patterns, each sequence being representative of a reference signal; a third circuit configured to process a current input pattern with respect to at least some of the reference signals in turn, comprising; (1) a fourth circuit configured to define as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for the current into pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and all ordered sequence of input patterns ending at said current input pattern, and for listing the active patterns for the current input pattern in a current active list; (2) a fifth circuit configured to store in a store associated with each active pattern, a cumulative value representative of a score for thc dynamic programming path which ends at that active pattern for said current input pattern; and (3) a sixth circuit configured to process each active pattern of said current reference signal in reverse sequential order, to update said cumulative values and to propagate said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, said sixth circuit comprising; (a) a seventh circuit configured to update the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and (b) an eighth circuit configured to propagate the dynamic programming path associated with the current active pattern, and for listing, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path fur the succeeding input pattern, in a new active list; and wherein said eighth circuit is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest iii the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the eighth circuit can propagate each dynamic programming path without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of said sixth circuit processing preceding active patterns of the current reference signal. - View Dependent Claims (83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106)
-
-
107. A method of performing a dynamic programming pattern matching process between a sequence of input patterns representative of an input signal, and a number of stored sequences of reference patterns, each sequence being representative of a reference signal, wherein the method processes each input pattern in turn with respect to at least some of the reference signals in turn, by:
-
(1) defining as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for a current input pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and listing the active patterns for the current input pattern in a current active list; (2) for each active pattern, storing in a store associated with that active pattern, a cumulative value representative of the score for the dynamic programming path which ends at that active pattern for said current input pattern; and (3) updating said cumulative values and propagating said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, by processing each active pattern of said current reference signal in reverse sequential order, by; (A) updating the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and
then(B) propagating the dynamic programming path associated with the current active pattern, and listing, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in a new active list; and wherein the propagation of each dynamic programming path for a current reference signal is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the propagation of each dynamic programming path is achieved without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of processing preceding active patterns. - View Dependent Claims (108, 109, 110, 111, 112, 113, 114, 115, 116, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133)
-
Specification