Dynamic time warping using frequency distributed distance measures

• US 6,983,246 B2
• Filed: 05/21/2002
• Issued: 01/03/2006
• Est. Priority Date: 05/21/2002
• Status: Expired due to Term

• Current Assignee: Musicqubed Innovations LLC (Ascend Innovation Management, LLC)
• Original Assignee: ThinkEngine Networks, Inc.
• Inventors: Kepuska, Veton K., Reddy, Harinath K.
• Primary Examiner(s): Knepper, David D.
• Application Number:
  US10/152,447
• Publication Number:
  US 20030220790A1
• Time in Patent Office: 1,323 Days
• Field of Search: 704236-242, 704251-255
• US Class Current: 704/241
• CPC Class Codes: G10L 15/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]
• CPC Class Codes: G10L 2015/088 Word spotting

Abstract

Distances are measured between vectors representing speech and a stored reference template. Frequency distributions of the distance measurements are generated by counting how many times a particular reference template resulted in the lowest local distance. The numbers in the counters indicate regions (successive vectors) in a reference template that are good matches for speech input.

Claims

1. A method comprising

measuring distances between vectors that represent an utterance and vectors that represent a template,

generating additional information including a frequency measure based on the measured distances, the additional information indicative of how well the vectors of the utterance match the vectors of the template, and

making a matching decision based on the measured distances and on the generated additional information.

2. The method of claim 1 wherein generating additional information including a frequency measure includes producing a distribution of values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance.

3. The method of claim 2 in which the matching decision is based on the extent to which the distribution is non-uniform.

4. The method of claim 3 in which the matching decision is based on the spikiness of the distribution.

5. The method of claim 3 in which the matching decision is based on how well the entire set of vectors representing the template are used in the matching.

6. The method of claim 1 in which the measuring of distances includes generating a raw dynamic time warping score and rescoring the score based on the information indicative of how well the vectors of the utterance match the vectors of the template.

7. The method of claim 6 in which the rescoring is based on both a spikiness of a distribution and on how well an entire set of vectors representing the template are used in the matching.

8. A method comprising

using dynamic time warping to generate a score representing distances between vectors that represent an utterance and vectors that represent a template,

producing a distribution of values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance, and

rescoring the score based on a spikiness of the distribution and on how well the entire set of vectors representing the template are used in the matching.

9. A medium carrying instructions adapted to cause a machine to

measure distances between vectors that represent an utterance and vectors that represent a template,

generate additional information including a frequency measure based on the measured distances, the additional information indicative of how well the vectors of the utterance match the vectors of the template, and

make a matching decision based on the measured distances and on the generated additional information.

10. Apparatus comprising

an input port connected to receive digitized speech, and

a speech recognizer configured to

measure distances between vectors that represent an utterance and vectors that represent a template,

generate additional information including a frequency measure based on the measured distances, the additional information indicative of how well the vectors of the utterance match the vectors of the template, and

make a matching decision based on the measured distances and on the generated additional information.

11. The apparatus of claim 10 wherein the configurations causing the speech recognizer to generate additional information including a frequency measure includes configurations causing the speech recognizer to produce a distribution of values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance.

12. The apparatus of claim 10 further comprising configurations causing the speech recognizer to generate a raw dynamic time warping score and rescore the score based on the information indicative of how well the vectors of the utterance match the vectors of the template.

13. The apparatus of claim 10 wherein the configurations causing the speech recognizer to rescore include configurations causing the speech recognizer to rescore based on both a spikiness of a distribution and on how well an entire set of vectors representing the template are used in the matching.

14. Apparatus comprising

means for measuring distances between vectors that represent an utterance and vectors that represent a template,

means for generating additional information including a frequency measure based on the measured distances, the additional information indicative of how well the vectors of the utterance match the vectors of the template, and

means for making a matching decision based on the measured distances and on the generated additional information.

15. The apparatus of claim 14 wherein the means for generating information including a frequency measure includes a means for producing a distribution of values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance.

16. The apparatus of claim 14 in which the means for measuring of distances includes a means for generating a raw dynamic time warping score and rescoring the score based on the information indicative of how well the vectors of the utterance match the vectors of the template.

17. The apparatus of claim 16 in which the means for rescoring includes a means for rescoring based on both a spikiness of a distribution and on how well an entire set of vectors representing the template are used in the matching.

18. The medium of claim 14 wherein the instructions causing a machine to generate information include instructions causing a machine to produce a distribution of values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance.

19. The medium of claim 14 further comprising instructions causing a machine to rescore a score based on the information indicative of how well the vectors of the utterance match the vectors of the template.

20. The medium of claim 19 wherein the instructions causing a machine to rescore includes instructions causing a machine to rescore based on both a spikiness of a distribution and on how well an entire set of vectors representing the template are used in the matching.

21. A method comprising

measuring distances between vectors that represent an utterance and vectors that represent a template, and

generating additional information including a distribution of values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance, the information indicative of how well the vectors of the utterance match the vectors of the template.

22. The method of claim 21 further comprising making a matching decision based on the measured distances and on the generated additional information.

23. The method of claim 22 in which the matching decision is based on the extent to which the distribution is non-uniform.

24. The method of claim 22 which the matching decision is based on the spikiness of the distribution.

25. The method of claim 22 in which the matching decision is based on how well the entire set of vectors representing the template are used in the matching.

26. The method of claim 21 in which the measuring of distances includes generating a raw dynamic time warping score and rescoring the score based on the information indicative of how well the vectors of the utterance match the vectors of the template.

27. The method of claim 26 which the rescoring is based on both a spikiness of a distribution and on how well an entire set of vectors representing the template are used in the matching.

28. A method comprising

using dynamic time warping to generate a score representing distances between vectors that represent an utterance and vectors that represent a template,

producing a distribution of values associated with the distances between vectors that represent an utterance and vectors that represent a template, and

rescoring the score based on a spikiness of the distribution and on how well the entire set of vectors representing the template are used in the matching.

29. The method of claim 28 wherein the distribution of values includes values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance.

30. A medium adapted to carry instructions causing a machine to:

use dynamic time warping to generate a score representing distances between vectors that represent an utterance and vectors that represent a template,

produce a distribution of values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance, and

rescore the score based on a spikiness of the distribution and on how well the entire set of vectors representing the template are used in the matching.