Pattern matching method and apparatus

• US 6,240,389 B1
• Filed: 02/08/1999
• Issued: 05/29/2001
• Est. Priority Date: 02/10/1998
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Tzirkel-Hancock, Eli, Keiller, Robert Alexander, Seward, Julian Richard
• Primary Examiner(s): Korzuch, William R.
• Assistant Examiner(s): ABEBE, DANIEL DEMELASH
• Application Number:
  US09/246,202
• Time in Patent Office: 841 Days
• Field of Search: 704/241, 704/238, 704/243, 704/251, 704/257, 704/232, 704/252, 704/245, 704/256, 704/247
• US Class Current: 704/243
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G10L 15/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]
• CPC Class Codes: G10L 2015/085 Methods for reducing search complexity, pruning

Abstract

A method and apparatus is provided for matching a first sequence of patterns representative of a first signal with a second sequence of patterns representative of a second signal. The system uses a plurality of different pruning thresholds (th) to control the propagation of paths which represent possible matchings between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern. In particular, the pruning threshold used for a given path during the processing of a current first signal pattern depends upon the position, within the sequence of patterns representing the second signal, of the second signal pattern which is at the end of the given path.

Claims

1. A method of matching a first sequence of patterns representative of a first signal with a second sequence of patterns representative of a second signal, the method comprising of the steps of:

matching the first signal with the second signal using a matching process which processes each first signal pattern in sequence and which propagates a plurality of paths using predetermined path propagation constraints, each path representing a possible matching between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed, and each path having an associated cumulative value representative of the closeness of the match; and

controlling the matching step by comparing said cumulative values with a pruning value during the processing of each first signal pattern and discarding paths in dependence upon the result of the said comparing step;

characterised in that a number of different pruning values are used in said controlling step during the processing of a current first signal pattern, and in that the pruning value used for a given path during the processing of the current first signal pattern depends upon the position, within the sequence of patterns representing said second signal, of the second signal pattern which is at the end of the given path for the current first signal pattern being processed.

2. A method according to claim 1, wherein the pruning values used in the comparing step for a succeeding first signal pattern are determined by adding a variable which varies with said position to the minimum cumulative value of all the paths remaining after processing a current first signal pattern.

3. A method according to claim 2, wherein said variable also varies with the number of paths which were propagated during the processing of a preceding first signal pattern.

4. A method according to claim 1, wherein said sequence of second signal patterns are divided into a plurality of groups of subsequences, and wherein during the processing of a current first signal pattern, said comparing step uses a different pruning value for each group.

5. A method according to claim 1, wherein during the processing of a current first signal pattern, said comparing step uses a first pruning value for paths ending at one of the first n second signal patterns, a second pruning value for paths ending at one of the next m second signal patterns and a third pruning value for paths ending at one of the remaining second signal patterns.

6. A method according to claim 1, wherein during the processing of a current first signal pattern, said comparing step uses a pruning value which is larger for paths which end towards the beginning of the second signal than the pruning value used for paths which end towards the end of the second signal.

7. A method according to claim 1, wherein said controlling step performs a hard pruning operation, whereby paths having a cumulative value worse than the corresponding pruning value are discarded.

8. A method according to claim 1, wherein said controlling step performs a soft pruning operation, whereby some paths which have a cumulative value worse than the corresponding pruning value are not discarded.

9. A method according to claim 8, wherein said controlling step performs said soft pruning for paths which have a cumulative value which is within a predetermined amount of the corresponding pruning value.

10. A method according to claim 9, wherein said controlling step randomly discards paths which have a cumulative value which is within the predetermined amount of the corresponding pruning value.

11. A method according to claim 9, wherein said controlling step discards paths which have a cumulative value which is within the predetermined amount of the corresponding pruning value, in dependence upon the value of said cumulative value relative to said corresponding pruning value.

12. A method according to claim 9, wherein said sequence of second signal patterns are divided into a plurality of groups of subsequences, and wherein during the processing of a current first signal pattern, said comparing step uses a different plurality of pruning values for each of said groups.

13. A method according to claim 12, wherein the plurality of pruning values associated with the first group of second signal patterns are greater than the plurality of pruning values used for subsequent groups of second signal patterns.

14. A method according to claim 12, wherein the number of groups, the number of different pruning values associated with each group and the difference between the pruning values associated with a group are determined in dependence upon said path propagation constraints.

15. A method according to claim 1, wherein the pruning value used for a given path depends upon the pruning value used for paths which end at the second signal pattern which is adjacent to the second signal pattern which is at the end of the given path.

16. A method according to claim 1, wherein said matching step performs a dynamic programming matching operation.

17. A method according to claim 1, wherein said first signal is representative of a speech signal and said second signal is representative of a reference speech signal, and wherein each of said patterns comprises a number of parameters representative of acoustic properties of the corresponding speech signal during a corresponding time frame.

18. A computer readable medium storing computer executable process steps to perform a pattern matching method of matching a first sequence of patterns representative of a first signal with a second sequence of patterns representative of a second signal, the process steps comprising of the steps of:

matching the first signal with the second signal using a matching process which processes each first signal pattern in sequence and which propagates a plurality of paths using predetermined path propagation constraints, each path representing a possible matching between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed, and each path having an associated cumulative value representative of the closeness of the match; and

controlling the matching step by comparing said cumulative values with a pruning value during the processing of each first signal pattern and discarding paths in dependence upon the result of the said comparing step;

characterised in that a number of different pruning values are used in said controlling step during the processing of a current first signal pattern, and in that the pruning value used for a given path during the processing of the current first signal pattern depends upon the position, within the sequence of patterns representing said second signal, of the second signal pattern which is at the end of the given path for the current first signal pattern being processed.

19. A computer readable medium according to claim 18, wherein the pruning values used in the comparing step for a succeeding first signal pattern are determined by adding a variable which varies with said position to the minimum cumulative value of all the paths remaining after processing a current first signal pattern.

20. A computer readable medium according to claim 19, wherein said variable also varies with the number of paths which were propagated during the processing of a preceding first signal pattern.

21. A computer readable medium according to claim 18, wherein said sequence of second signal patterns are divided into a plurality of groups of subsequences, and wherein during the processing of a current first signal pattern, said comparing step uses a different pruning value for each group.

22. A computer readable medium according to claim 18, wherein during the processing of a current first signal pattern, said comparing step uses a first pruning value for paths ending at one of the first n second signal patterns, a second pruning value for paths ending at one of the next m second signal patterns and a third pruning value for paths ending at one of the remaining second signal patterns.

23. A computer readable medium according to claim 18, wherein during the processing of a current first signal pattern, said comparing step uses a pruning value which is larger for paths which end towards the beginning of the second signal than the pruning value used for paths which end towards the end of the second signal.

24. A computer readable medium according to claim 18, wherein said controlling step performs a hard pruning operation, whereby paths having a cumulative value worse than the corresponding pruning value are discarded.

25. A computer readable medium according to claim 18, wherein said controlling step performs a soft pruning operation, whereby some paths which have a cumulative value worse than the corresponding pruning value are not discarded.

26. A computer readable medium according to claim 25, wherein said controlling step performs said soft pruning for paths which have a cumulative value which is within a predetermined amount of the corresponding pruning value.

27. A computer readable medium according to claim 26, wherein said controlling step randomly discards paths which have a cumulative value which is within the predetermined amount of the corresponding pruning value.

28. A computer readable medium according to claim 26, wherein said controlling step discards paths which have a cumulative value which is within the predetermined amount of the corresponding pruning value, in dependence upon the value of said cumulative value relative to said corresponding pruning value.

29. A computer readable medium according to claim 26, wherein said sequence of second signal patterns are divided into a plurality of groups of subsequences, and wherein during the processing of a current first signal pattern, said comparing step uses a different plurality of pruning values for each of said groups.

30. A computer readable medium according to claim 29, wherein the plurality of pruning values associated with the first group of second signal patterns are greater than the plurality of pruning values used for subsequent groups of second signal patterns.

31. A computer readable medium according to claim 29, wherein the number of groups, the number of different pruning values associated with each group and the difference between the pruning values associated with a group are determined in dependence upon said path propagation constraints.

32. A computer readable medium according to claim 18, wherein the pruning value used for a given path depends upon the pruning value used for paths which end at the second signal pattern which is adjacent to the second signal pattern which is at the end of the given path.

33. A computer readable medium according to claim 18, wherein said matching step performs a dynamic programming matching operation.

34. A computer readable medium according to claim 18, wherein said first signal is representative of a speech signal and said second signal is representative of a reference speech signal, and wherein each of said patterns comprises a number of parameters representative of acoustic properties of the corresponding speech signal during a corresponding time frame.

35. An apparatus for matching a first sequence of patterns representative of a first signal with a second sequence of patterns representative of a second signal, the apparatus comprising:

a pattern matcher for matching the first signal with the second signal using a matching process which processes each first signal pattern in sequence and which propagates a plurality of paths using predetermined path propagation constraints, each path representing a possible matching between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed, and each path having an associated cumulative value representative of the closeness of the match; and

a controller for controlling the pattern matcher by comparing said cumulative values with a pruning value during the processing of each first signal pattern and discarding paths in dependence upon the result of the said comparison;

characterised in that a number of different pruning values are used by said controller during the processing of a current first signal pattern, and in that the pruning value used for a given path during the processing of the current first signal pattern depends upon the position, within the sequence of patterns representing said second signal, of the second signal pattern which is at the end of the given path for the current first signal pattern being processed.

36. An apparatus according to claim 35, wherein the pruning values used in the comparison for a succeeding first signal pattern are determined by adding a variable which varies with said position to the minimum cumulative value of all the paths remaining after processing a. current first signal pattern.

37. An apparatus according to claim 36, wherein said variable also varies with the number of paths which were propagated during the processing of a preceding first signal pattern.

38. An apparatus according to claim 35, wherein said sequence of second signal patterns are divided into a plurality of groups of subsequences, and wherein during the processing of a current first signal pattern, said comparison uses a different pruning value for each group.

39. An apparatus according to claim 35, wherein during the processing of a current first signal pattern, said comparison uses a first pruning value for paths ending at one of the first n second signal patterns, a second pruning value for paths ending at one of the next m second signal patterns and a third pruning value for paths ending at one of the remaining second signal patterns.

40. An apparatus according to claim 35, wherein during the processing of a current first signal pattern, said comparison uses a pruning value which is larger for paths which end towards the beginning of the second signal than the pruning value used for paths which end towards the end of the second signal.

41. An apparatus according to claim 35, wherein said controller is operable to perform a hard pruning operation, whereby paths having a cumulative value worse than the corresponding pruning value are discarded.

42. An apparatus according to claim 35, wherein said controller is operable to perform a soft pruning operation, whereby some paths which have a cumulative value worse than the corresponding pruning value are not discarded.

43. An apparatus according to claim 42, wherein said controller is operable to perform said soft pruning for paths which have a cumulative value which is within a predetermined amount of the corresponding pruning value.

44. An apparatus according to claim 43, wherein said controller is operable to randomly discard paths which have a cumulative value which is within the predetermined amount of the corresponding pruning value.

45. An apparatus according to claim 43, wherein said controller is operable to discard paths which have a cumulative value which is within the predetermined amount of the corresponding pruning value, in dependence upon the value of said cumulative value relative to said corresponding pruning value.

46. An apparatus according to claim 43, wherein said sequence of second signal patterns are divided into a plurality of groups of subsequences, and wherein during the processing of a current first signal pattern, said comparison uses a different plurality of pruning values for each of said groups.

47. An apparatus according to claim 46, wherein the plurality of pruning values associated with the first group of second signal patterns are greater than the plurality of pruning values used for subsequent groups of second signal patterns.

48. An apparatus according to claim 46, wherein the number of groups, the number of different pruning values associated with each group and the difference between the pruning values associated with a group are determined in dependence upon said path propagation constraints.

49. An apparatus according to claim 35, wherein the pruning value used for a given path depends upon the pruning value used for paths which end at the second signal pattern which is adjacent to the second signal pattern which is at the end of the given path.

50. An apparatus according to claim 35, wherein said pattern matcher is operable to perform a dynamic programming matching operation.

51. An apparatus according to claim 35, wherein said first signal is representative of a speech signal and said second signal is representative of a reference speech signal, and wherein each of said patterns comprises a number of parameters representative of acoustic properties of the corresponding speech signal during a corresponding time frame.

52. A signal conveying computer executable process steps to perform a pattern matching method of matching a first sequence of patterns representative of a first signal with a second sequence of patterns representative of a second signal, the process steps comprising of the steps of:

matching the first signal with the second signal using a matching process which processes each first signal pattern in sequence and which propagates a plurality of paths using predetermined path propagation constraints, each path representing a possible matching between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed, and each path having an associated cumulative value representative of the closeness of the match; and

controlling the matching step by comparing said cumulative values with a pruning value during the processing of each first signal pattern and discarding paths in dependence upon the result of the said comparing step;

characterised in that a number of different pruning values are used in said controlling step during the processing of a current first signal pattern, and in that the pruning value used for a given path during the processing of the current first signal pattern depends upon the position, within the sequence of patterns representing said second signal, of the second signal pattern which is at the end of the given path for the current first signal pattern being processed.

53. Computer executable process steps for controlling a processor to perform a pattern matching method of matching a first sequence of patterns representative of a first signal with a second sequence of patterns representative of a second signal, the process steps comprising the steps of:

matching the first signal with the second signal using a matching process which processes each first signal pattern in sequence and which propagates a plurality of paths using predetermined path propagation constraints, each path representing a possible matching between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed, and each path having an associated cumulative value representative of the closeness of the match; and

controlling the matching step by comparing said cumulative values with a pruning value during the processing of each first signal pattern and discarding paths in dependence upon the result of the said comparing step;

characterized in that a number of different pruning values are used in said controlling step during the processing of a current first signal pattern, and in that the pruning value used for a given path during the processing of the current first signal pattern depends upon the position, within the sequence of patterns representing said second signal, of the second signal pattern which is at the end of the given path for the current first signal pattern being processed.

54. Computer-executable process steps according to claim 53, wherein the pruning values used in the comparing step for a succeeding first signal pattern are determined by adding a variable which varies with said position to the minimum cumulative value of all the paths remaining after processing a current first signal pattern.

55. Computer-executable process steps according to claim 54, wherein said variable also varies with the number of paths which were propagated during the processing of a preceding first signal pattern.

56. Computer executable process steps according to claim 53, wherein said sequence of second signal patterns are divided into a plurality of groups of subsequences, and wherein during the processing of a current first signal pattern, said comparing step uses a different pruning value for each group.

57. Computer-executable process steps according to claim 53, wherein during the processing of a current first signal pattern, said comparing step uses a first pruning value for paths ending at one of the first n second signal patterns, a second pruning value for paths ending at one of the next m second signal patterns and a third pruning value for paths ending at one of the remaining second signal patterns.

58. Computer-executable process steps according to claim 53, wherein during the processing of a current first signal pattern, said comparing step uses a pruning value which is larger or paths which end towards the beginning of the second signal than the pruning value used for paths which end towards the end of the second signal.

59. Computer-executable process steps according to claim 53, wherein said controlling step performs a hard pruning operation, whereby paths having a cumulative value worse than the corresponding pruning value are discarded.

60. Computer-executable process steps according to claim 54, wherein said controlling step performs a soft pruning operation, whereby some paths which have a cumulative value worse than the corresponding pruning value are not discarded.

61. Computer-executable process steps according to claim 60, wherein said controlling step performs said soft pruning for paths which have a cumulative value which is within a predetermined amount of the corresponding pruning value.

62. Computer-executable process steps according to claim 61, wherein said controlling step randomly discards paths which have a cumulative value which is within the predetermined amount of the corresponding pruning value.

63. Computer-executable process steps according to claim 61, wherein said controlling step discard paths which have a cumulative value which is within the predetermined amount of the corresponding pruning value, in dependence upon the value of said cumulative value relative to said corresponding pruning value.

64. Computer-executable process steps according to claim 61, wherein said sequence of second signal patterns are divided into a plurality of groups of subsequences, and wherein during the processing of a current first signal pattern, said comparing step uses a different plurality of pruning values for each of said groups.

65. Computer-executable process steps according to claim 64, wherein the plurality of pruning values associated with the first group of second signal patterns are greater than the plurality of pruning values used for subsequent groups of second signal patterns.

66. Computer-executable process steps according to claim 64, wherein the number of groups, the number of different pruning values associated with each group and the difference between the pruning values associated with a group are determined in dependence upon said path propagation constraints.

67. Computer-executable process steps according to claim 53, wherein the pruning value used for a given path depends upon the pruning value used for paths which end at the second signal pattern which is adjacent to the second signal pattern which is at the end of the given path.

68. Computer-executable process steps according to claim 53, wherein said matching step performs a dynamic programming matching operation.

69. Computer-executable process steps according to claim 53, wherein the first signal is representative of a speech signal and said second signal is representative of a reference speech signal, and wherein each of said patterns comprises a number of parameters representative of acoustic properties of the corresponding speech signal during a corresponding time frame.