Fast vocabulary independent method and apparatus for spotting words in speech

• US 6,073,095 A
• Filed: 10/15/1997
• Issued: 06/06/2000
• Est. Priority Date: 10/15/1997
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Roukos, Salim Estephan, Eide, Ellen Marie, Dharanipragada, Satyanarayana
• Primary Examiner(s): Dorvil, Richemond
• Application Number:
  US08/950,621
• Time in Patent Office: 965 Days
• Field of Search: 704/256, 704/242, 704/231, 704/236, 704/246, 704/250, 704/251, 704/257, 704/255, 704/270
• US Class Current: 704/242
• CPC Class Codes: G10L 15/08 Speech classification or search
• CPC Class Codes: G10L 15/187 Phonemic context, e.g. pronunciation rules, phonotactical constraints or phoneme n-grams
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams
• CPC Class Codes: G10L 2015/088 Word spotting

Abstract

A fast vocabulary independent method for spotting words in speech utilizes a preprocessing step and a coarse-to-detailed search strategy for spotting a word/phone sequence in speech. The preprocessing includes a Viterbi-beam phone level decoding using a tree-based phone language model. The coarse search matches phone-ngrams to identify regions of speech as putative word hits, and the detailed search performs an acoustic match at the putative hits with a model of the given word included in the vocabulary of the recognizer.

Claims

1. A fast vocabulary independent method for spotting words in speech comprising the steps of:

converting a speech waveform into a representation comprising phone-ngrams and a corresponding time interval of occurrence of each of the phone-ngrams;

receiving phone-ngrams of at least one input word;

performing a coarse match by selecting time intervals of the speech waveform having phone-ngrams that correspond to the phone-ngrams of the at least one input word; and

performing a detailed acoustic match at the selected time intervals.

2. The method according to claim 1, wherein said step of converting the speech waveform comprises the steps of:

generating feature vectors representative of the speech waveform;

processing the feature vectors to generate the phone-ngrams for each word in the speech waveform; and

storing the phone-ngrams and their corresponding time intervals in a look-up table.

3. The method according to claim 2, wherein said step of processing the feature vectors comprises the steps of:

constructing a phone language model from a phonetic baseforms vocabulary; and

performing a time synchronous Viterbi-Beam search using the phone language model for converting the speech waveform into phone-ngrams.

4. The method according to claim 3, wherein said step of performing a time synchronous Viterbi-Beam search further comprises the steps of:

computing the maximum probability of all leaves of a phone;

placing all start nodes in an active list "A";

determining the best path through the constructed phone language model;

updating the scores of all active nodes at every third frame;

computing the maximum score "M";

determining a list of all successor nodes;

placing the successor nodes in a next list "N"; and

determining the phone-ngrams produced by the nodes for the top K scores in A.

5. The method according to claim 1, wherein a given time interval of the speech waveform is selected during the step of performing the coarse match if a predetermined fraction of the total number of phone-ngrams of the input word are determined to be within the given time interval.

6. The method according to claim 1, wherein said step of performing a detailed acoustic match comprises the steps of:

building a model of a given word associated with at least one of the selected time intervals;

conducting a modified Viterbi search at the at least one selected time interval associated with the given word;

computing an a posteriori probability of the end state of the given word; and

outputting the at least one selected time interval if the a posteriori probability of the given word exceeds a predetermined threshold.

7. The method according to claim 1, wherein said step of converting the speech waveform is performed offline as a preprocessing step, and said steps of performing the coarse match and the detailed acoustic match are performed online during processing.

8. The method according to claim 1, wherein the phone-ngrams of the speech waveform and the phone-ngrams of the at least one input word are triphones.

9. The method according to claim 1, wherein said step of receiving phone-ngrams of at least one input word comprises the steps of:

determining a phonetic baseform of the at least one input word; and

identifying all phone-ngrams of the phonetic baseform.

10. The method according to claim 9, wherein said step of determining the phonetic baseform is performed using one of a group consisting of a large dictionary of baseforms and a spelling to baseform generator.

11. A fast vocabulary independent method for spotting words in speech comprising the steps of:

converting a speech waveform into a table comprising phone-ngrams and the corresponding times of occurrence in the speech waveform of the phone-ngrams;

generating phone-ngrams of at least one input word;

performing a coarse match by implementing the table to identify time intervals of the input waveform having phone-ngrams associated therewith that correspond to the phone-ngrams of the at least one input word; and

performing a detailed acoustic match at each of the identified time intervals of the speech waveform to finally decide whether the at least one input word was actually uttered in the identified time intervals.

12. The method according to claim 11, wherein the phone-ngrams of the speech waveform and the phone-ngrams of the at least one input word are triphones.

13. The method according to claim 11, wherein a time interval of the speech waveform is identified during the step of performing the coarse match search if a user-defined fraction of a total number of phone-ngrams of the at least one input word are determined to be within the time interval.

14. A fast vocabulary independent method for spotting words in speech for use in voice mail retrieval systems and browsing and searching audio/video content, the method comprising the steps of:

receiving a search query from a user;

determining a phonetic baseform for each word of the search query and converting each baseform to phone-ngrams;

identifying the locations of the search query words in an audio/video database by comparing phone-ngrams of the search query words and phone-ngrams of at least one audio waveform in the audio/video database; and

retrieving segments of the at least one audio waveform and corresponding video segments that are relevant to the received query.

15. The method according to claim 14, wherein said step of determining the phonetic baseforms is performed using one of a group consisting of a large dictionary of baseforms and a spelling to baseform generator.

16. The method according to claim 14, wherein said step of identifying the locations further comprises the steps of:

converting the at least one audio waveform into a table of phone-ngrams;

performing a coarse match by implementing the table to identify time intervals of the at least one audio waveform having phone-ngrams associated therewith that correspond to the phone-ngrams of the query words; and

performing a detailed acoustic match at each of the identified time intervals of the at least one audio waveform to determine whether the search query words were actually uttered in the identified time intervals.

17. The method according to claim 16, wherein said step of converting further comprises the steps of:

generating feature vectors representative of the at least one audio waveform;

processing the feature vectors to generate the phone-ngrams for each word in the at least one audio waveform; and

storing the phone-ngrams and their corresponding time intervals in a look-up table.

18. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a fast vocabulary independent method for spotting words in speech, the method steps comprising:

converting a speech waveform into a table comprising phone-ngrams and the corresponding times of occurrence in the speech waveform of the phone-ngrams;

generating phone-ngrams of at least one input word;

performing a coarse match by implementing the table to identify time intervals of the speech waveform having phone-ngrams associated therewith that correspond to the phone-ngrams of the at least one input word; and

performing a detailed acoustic match at each of the identified time intervals of the speech waveform to finally decide whether the at least one input word was actually uttered in the identified time intervals.

19. The program storage device of claim 18, wherein the phone-ngrams of the speech waveform and the phone-ngrams of the at least one input word are triphones.

20. The program storage device of claim 18, wherein a time interval of the speech waveform is identified during the step of performing the coarse match search if a user-defined fraction of a total number of phone-ngrams of the at least one input word are determined to be within the time interval.