DP Pattern matching which determines current path propagation using the amount of path overlap to the subsequent time point
First Claim
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, wherein the method processes each first signal pattern in-turn by:
- defining as active patterns the second signal patterns which are at the end of a path for a current first signal pattern being processed, each path representing a possible matching between an ordered sequence of second signal patterns and an ordered sequence of first signal patterns ending at said current first signal pattern;
for each active pattern, storing a cumulative value which is indicative of the closeness of the match for the path which ends at that active pattern for said current first signal pattern; and
updating said cumulative values and propagating said paths based on constraints which are placed on the path propagation, by processing each active pattern in reverse sequential order, by;
(i) determining which of the second signal patterns the path ending at the current active pattern can propagate to for the succeeding first signal pattern to be processed, based upon said path propagation constraints;
(ii) identifying how many of the second signal patterns determined in step (i) have previously been so determined during the processing of a previous active pattern for the current first signal pattern being processed; and
(iii) propagating the path associated with the current active pattern in dependence upon how many of said second signal patterns are identified in said step (ii).
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for matching a first sequence of patterns representative of a first signal with a second sequence of patterns representative of a second signal using a dynamic programming matching technique is described. The second signal patterns which are at the end of a dynamic programming path for a current first signal pattern are listed in an active list 201. The dynamic programming paths are propagated by processing the second signal patterns on the active list, and a new active list 205 is generated for the succeeding input pattern. In order to propagate each path, the system determines how many second signal patterns lie within an overlap region in which a comparison has to be made, and processes each path in dependence upon the determined amount of overlap.
51 Citations
153 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, wherein the method processes each first signal pattern in-turn by:
-
defining as active patterns the second signal patterns which are at the end of a path for a current first signal pattern being processed, each path representing a possible matching between an ordered sequence of second signal patterns and an ordered sequence of first signal patterns ending at said current first signal pattern;
for each active pattern, storing a cumulative value which is indicative of the closeness of the match for the path which ends at that active pattern for said current first signal pattern; and
updating said cumulative values and propagating said paths based on constraints which are placed on the path propagation, by processing each active pattern in reverse sequential order, by;
(i) determining which of the second signal patterns the path ending at the current active pattern can propagate to for the succeeding first signal pattern to be processed, based upon said path propagation constraints;
(ii) identifying how many of the second signal patterns determined in step (i) have previously been so determined during the processing of a previous active pattern for the current first signal pattern being processed; and
(iii) propagating the path associated with the current active pattern in dependence upon how many of said second signal patterns are identified in said step (ii). - 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, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 92, 93)
(a) comparing D[S] with D[S+N+1−
m];
(b) if D[S] is better than D[S+N+1−
m], then propagating the path ending at the current active pattern to the second signal pattern S+N+1−
m by making D[S+N+1−
m]=D[S], decrementing m and returning to step (a); and
(c) if D[S] is worse than D[S+N+1−
m], then not propagating the path ending at the current active pattern to the second signal pattern S+N−
1−
m or any second signal pattern sequentially beyond second signal pattern S+N+1−
m;
where S is the current active pattern being processed, N is the number of second signal patterns which are sequentially beyond the current active pattern to which the path ending at the current active pattern can propagate for the succeeding first signal pattern to be processed and m is a positive integer variable which is initially set at the number of second signal patterns identified in said step (ii).
-
-
5. A method according to claim 4, wherein said steps (a), (b) and (c) are performed while m is greater than zero.
-
6. A method according to claim 4, wherein m is less than N.
-
7. A method according to claim 4, further comprising the step of storing the minimum cumulative value of all paths being propagated and wherein if the path associated with the current active pattern is propagated to the second signal pattern S+N by making D[S+N]=D[S], then the method further comprises the steps of comparing D[S] with said minimum cumulative value and making the minimum cumulative value equal to D[S] if D[S] is better than the minimum cumulative value.
-
8. A method according to claim 1, wherein said active patterns for the current first signal pattern are listed, in reverse sequential order, in a current active list, and wherein the second signal patterns identified in step (i) are listed, if they are not already listed, in a new active list in reverse sequential order.
-
9. A method according to claim 8, further comprising the step of using an identifier to identify the second signal pattern which is the earliest in the sequence of second signal patterns which is listed in the new active list after processing the preceding active pattern, and wherein said step (ii) identifies how many of the second signal patterns determined in step (i) have previously been so determined by determining a positional relationship between the current active pattern being processed and the second signal pattern which is identified by said identifier.
-
10. A method according to claim 9, wherein said positional relationship is determined by testing for the different possibilities which the relationship can have.
-
11. A method according to claim 10, wherein the method identifies said positional relationship by testing for the following situations:
-
(A) the identifier identifies a second signal pattern which sequentially immediately succeeds the current active pattern being processed;
(B) the identifier identifies a second signal pattern which is sequentially beyond second signal pattern S+N;
(C) the identifier identifies a second signal pattern S+i, for i=1 to N−
1;
where S is the current active pattern being processed and N is the number of second signal patterns which are beyond the current active pattern to which the path ending at the current active pattern can propagate to for the succeeding first signal pattern.
-
-
12. A method according to claim 11, wherein the method tests for situation (A) first and only tests for situation (B) if situation (A) is false.
-
13. A method according to claim 12, wherein the method tests for situation (C) only if situation (B) is false.
-
14. A method according to claim 13, wherein the method test situation (C) for a current value of i and only tests for situation (C) for i+1 if situation (C) for i is false.
-
15. A method according to claim 9, wherein after the new active list has been updated by the processing of the current active pattern, said identifier is set to identify the second signal pattern on the new active list which is the earliest in the sequence of patterns representative of the second signal.
-
16. A method according to claim 8, wherein a sentinel pattern is added to the end of the current active list so that the method can identify when all the active patterns, for the current first signal pattern, have been processed.
-
17. A method according to claim 16, wherein the cumulative value associated with the sentinel pattern is set to a predetermined value, and wherein the method identifies the sentinel pattern by comparing the cumulative value of each active pattern with said predetermined value.
-
18. A method according to claim 17, wherein said predetermined value is zero.
-
19. A method according to claim 16, wherein after the method has processed all the active patterns on the current active list, the method further comprises the step of adding the sentinel pattern to the end of the new active list.
-
20. A method according to claim 1, wherein one of said path propagation constraints is that if a second signal pattern is matched with a first signal pattern, then second signal patterns which are sequentially before that second signal pattern cannot be matched with the succeeding first signal pattern on the same path.
-
21. A method according to claim 1, wherein one of said path propagation constraints is that a penalty is added to the cumulative value associated with a path which is matched with the same second signal pattern for consecutive first signal patterns being processed.
-
22. A method according to claim 1, wherein the method only updates the cumulative value of the current active pattern and propagates the path associated with the current active pattern if the cumulative value associated therewith is better than a threshold value.
-
23. A method according to claim 22, wherein said threshold value is varied in order to try to maintain the number of active patterns processed for each first signal pattern to be below a given maximum number.
-
24. A method according to claim 23, wherein the threshold value used during the processing of the succeeding first signal pattern is determined during the processing of the current first signal pattern, and is dependent upon the total number of second signal patterns in the new active list for the succeeding first signal pattern to be processed.
-
25. A method according to claim 22, wherein a plurality of threshold values are used, and wherein the threshold value used for a given path depends upon the position, within the sequence of second signal 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.
-
26. A method according to claim 25, wherein the threshold values used for paths ending towards the beginning of the sequence is larger than the thresholds used for paths ending towards the end of the sequence.
-
27. A method according to claim 22, wherein a soft pruning operation is performed, whereby some paths which have a cumulative value worse than the threshold are not discarded.
-
28. A method according to claim 1, wherein the processing of the current first signal pattern is preformed before the succeeding first signal pattern is received.
-
29. A method according to claim 1, wherein the whole first signal is received before the first signal pattern is processed.
-
30. A method according to claim 1, wherein said second signal patterns are representative of a template, and wherein said cumulative values are distance measures.
-
31. A method according to claim 1, wherein said second signal patterns are representative of a statistical model, and wherein said cumulative values are probabilistic measures.
-
32. A method according to claim 1, further comprising the step of comparing said first signal with a plurality of second signals.
-
33. A method according to claim 32, wherein said first signal can be matched with a sequence of said plurality of second signals, by allowing paths propagating in one second signal to subsequently propagate into another second signal.
-
34. A method according to claim 33, wherein the sequence of second signals against which the first signal can be matched is constrained by a set of predefined rules.
-
35. A method according to claim 33, wherein each of said patterns are represented by a plurality of parameter values and wherein said distance measure represents a sum of the magnitude of the difference between the corresponding parameter values of the current first signal pattern and the current active pattern.
-
36. A method according to claim 1, wherein said method utilises a dynamic programming matching process.
-
37. A method according to claim 1, wherein the cumulative value for a path is updated by adding a distance measure representative of the distance between the current first signal pattern and the current active pattern.
-
38. A method according to claim 37, wherein said distance measure is determined by using the following equation:
-
where d(S,f,k) is the distance measure, Sp is the pth parameter value of the current active pattern and fkp is the pth parameter value of the current first signal pattern being processed.
-
-
39. A method according to claim 38, wherein a look up table is used in the determination of the distance measure which is to be added to the cumulative value of a path.
-
40. A method according to claim 39, wherein the respective parameter values of the current first signal pattern and the current active pattern address the look up table, and wherein the values stored in that location of the look up table corresponds to the difference between the two parameter values.
-
41. A method according to claim 39, wherein prior to processing the current first signal pattern, the method identifies a sub table of look up values using the parameter values of the current first signal pattern, and wherein the distance measure which is to be added to the cumulative value for a path is determined by addressing the sub table of look up values with the parameter values of the current active pattern.
-
42. A method according to claim 39, wherein the distance measure which is to be added to the cumulative value of the path is determined using the following equation:
-
where TPp is the address of the look up table which is dependent upon the pth parameter of the current first signal pattern and Sp is the pth parameter value of the current active pattern.
-
-
43. A method according to claim 42, wherein TPp is determined once per first signal pattern to be processed.
-
44. A method according to claim 1, wherein said first and second signals are representative of speech, and wherein each pattern comprises a number of parameters representative of the acoustic properties of the speech during a corresponding time frame.
-
45. A speech recognition method for recognising an input speech signal by comparing it with a plurality of reference speech signals, the method comprising the steps of:
-
extracting a sequence of input patterns representative of said input speech signal;
storing sequences of reference patterns, each sequence being representative of a corresponding reference speech signal;
matching the sequence of input patterns with the reference speech signals, using a method according to claim 44; and
providing a recognition result from the cumulative values determined by said matching step.
-
-
46. A method according to claim 45, wherein said recognition result is provided by determining which of the paths, which end at the last input pattern in the sequence of input patterns, has the best cumulative value.
-
92. An apparatus according to claim 39, wherein the distance measure which is to be added to the cumulative value of the path is determined from the following equation:
-
where TPp is the address of the look up table which is dependent upon the pth parameter of the current first signal pattern and Sp is the pth parameter value of the current active pattern.
-
-
93. An apparatus according to claim 92, wherein TPp is determined once per first signal pattern to be processed.
-
47. 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, wherein the method processes each first signal pattern in-turn by:
-
defining as active patterns the second signal patterns which are at the end of a path for a current first signal pattern being processed, each path representing a possible matching between an ordered sequence of second signal patterns and an ordered sequence of first signal patterns ending at said current first signal pattern;
for each active pattern, storing a cumulative value which is indicative of the closeness of the match for the path which ends at that active pattern for said current first signal pattern; and
updating said cumulative values and propagating said paths based on constraints which are placed on the path propagation, by processing each active pattern in reverse sequential order;
wherein each of said patterns is represented by a plurality of parameter values and wherein the cumulative value for a path is updated by adding a distance measure representative of the distance between the current first signal pattern and the current active pattern and wherein the respective parameter values of the current first signal pattern and the current active pattern address a look up table, and wherein the value stored in that location of the look up table corresponds to the difference between the two parameter values. - View Dependent Claims (48, 49, 50)
where TPp is the address of the look up table which is dependent upon the pth parameter of the current first signal pattern and Sp is the pth parameter value of the current active pattern.
-
-
50. A method according to claim 49, wherein TPp is determined once per first signal pattern to be processed.
-
51. 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, wherein the apparatus is operable to process each first signal pattern in-turn and comprises:
-
definition circuitry for defining as active patterns the second signal patterns which are at the end of a path for a current first signal pattern being processed, each path representing a possible matching between an ordered sequence of second signal patterns and an ordered sequence of first signal patterns ending at said current first signal pattern;
a memory for storing, for each active pattern, a cumulative value which is indicative of the closeness of the match for the path which ends at that active pattern for said current first signal pattern; and
processing circuitry for processing each active pattern in reverse sequential order to update said cumulative values and to propagate said paths based on constraints which are placed on the path propagation, said processing circuitry comprising;
(i) first circuitry for determining which of the second signal patterns the path ending at the current active pattern can propagate to for the succeeding first signal pattern to be processed, based upon said path propagation constraints;
(ii) second circuitry for identifying how many of the second signal patterns determined by said first circuitry have previously been so determined during the processing of a previous active pattern for the current first signal pattern being processed; and
(iii) third circuitry for propagating the path associated with the current active pattern in dependence upon how many of said second signal patterns are identified by said second circuitry. - View Dependent Claims (52, 53, 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, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 94, 95, 96)
(a) comparing D[S] with D[S+N+1−
m];
(b) if D[S] is better than D[S+N+1−
m], then propagating the path ending at the current active pattern to the second signal pattern S+N+1−
m by making D[S+N+1−
m]=D[S], decrementing m and returning to step (a); and
(c) if D[S] is worse than D[S+N+1−
m], then not propagating the path ending at the current active pattern to the second signal pattern S+N−
1−
m or any second signal pattern sequentially beyond second signal pattern S+N+1−
m;
where S is the current active pattern being processed, N is the number of second signal patterns which are sequentially beyond the current active pattern to which the path ending at the current active pattern can propagate for the succeeding first signal pattern to be processed and m is a positive integer variable which is initially set at the number of second signal patterns identified by said third circuitry.
-
-
55. An apparatus according to claim 54, wherein said third circuitry is operable to perform said steps (a), (b) and (c) while m is greater than zero.
-
56. An apparatus according to claim 54, wherein m is less than N.
-
57. An apparatus according to claim 54, further comprising a memory for storing the minimum cumulative value of all paths being propagated, and wherein said processing circuitry is operable to compare D[S] with said minimum cumulative value and to make the minimum cumulative value equal to D[S] if D[S] is better than the minimum cumulative value, if the path associated with the current active pattern is propagated by said processing circuitry to the second signal pattern S+N by making D[S+N]=D[S].
-
58. An apparatus according to claim 51, comprising listing circuitry for listing said active patterns for the current first signal pattern in reverse sequential order in a current active list and for listing, if they are not already listed, the second signal patterns identified by said second circuitry in a new active list in reverse sequential order.
-
59. An apparatus according to claim 58, further comprising an identifier for identifying the second signal pattern which is the earliest in the sequence of second signal patterns which is listed in the new active list by said listing circuitry after said processing circuitry has processed the preceding active pattern, and wherein said second circuitry is operable to identify how many of the second signal patterns determined by said first circuitry have previously been so determined by determining a positional relationship between the current active pattern being processed and the second signal pattern which is identified by said identifier.
-
60. An apparatus according to claim 59, wherein said positional relationship is determined by testing for the different possibilities which the relationship can have.
-
61. An apparatus according to claim 60, wherein said second circuitry identifies said positional relationship by testing for the following situations:
-
(A) the identifier identifies a second signal pattern which sequentially immediately succeeds the current active pattern being processed;
(B) the identifier identifies a second signal pattern which is sequentially beyond second signal pattern S+N;
(C) the identifier identifies a second signal pattern S+i, for i=1 to N−
1;
where S is the current active pattern being processed and N is the number of second signal patterns which are beyond the current active pattern to which the path ending at the current active pattern can propagate to for the succeeding first signal pattern.
-
-
62. An apparatus according to claim 61, wherein said second circuitry is operable to test for situation (A) first and only test for situation (B) if situation (A) is false.
-
63. An apparatus according to claim 62, wherein said second circuitry is operable to test for situation (C) only if situation (B) is false.
-
64. An apparatus according to claim 63, wherein said second circuitry is operable to test situation (C) for a current value of i and only test for situation (C) for i+1 if situation (C) for i is false.
-
65. An apparatus according to claim 59, wherein after the new active list has been updated by the processing of the current active pattern by the processing circuitry, said identifier is operable to identify the second signal pattern on the new active list which is the earliest in the sequence of patterns representative of the second signal.
-
66. An apparatus according to claim 58, wherein a sentinel pattern is added to the end of the current active list, and wherein said processing circuitry is operable to identify when all the active patterns, for the current first signal pattern, have been processed by detecting the sentinel pattern.
-
67. An apparatus according to claim 66, wherein a cumulative value associated with the sentinel pattern is set to a predetermined value, and wherein the processing circuitry detects the sentinel pattern by comparing the cumulative value of each active pattern with said predetermined value.
-
68. An apparatus according to claim 67, wherein said predetermined value is zero.
-
69. An apparatus according to claim 66, wherein after the processing circuitry has processed all the active patterns on the current active list, said listing circuitry is operable to add the sentinel pattern to the end of the new active list.
-
70. An apparatus according to claim 51, wherein one of said path propagation constraints is that if a second signal pattern is matched with a first signal pattern, then second signal patterns which are sequentially before that second signal pattern cannot be matched with the succeeding first signal pattern on the same path.
-
71. An apparatus according to claim 51, wherein one of said path propagation constraints is that a penalty is added to the cumulative value associated with a path which is matched with the same second signal pattern for consecutive first signal patterns being processed.
-
72. An apparatus according to claim 51, wherein said processing circuitry is operable to only update the cumulative value of the current active pattern and to propagate the path associated with the current active pattern if the cumulative value associated therewith is better than a threshold value.
-
73. An apparatus according to claim 72, comprising threshold varying circuitry for varying said threshold value in order to try to maintain the number of active patterns processed for each first signal pattern to be below a given maximum number.
-
74. An apparatus according to claim 73, wherein said threshold varying circuitry is operable to vary said threshold value so that the threshold value used during the processing of the succeeding first signal pattern by said apparatus is determined during the processing of the current first signal pattern, and is dependent upon the total number of second signal patterns in the new active list for the succeeding first signal pattern to be processed.
-
75. An apparatus according to claim 72, wherein said processing circuitry is operable to use a plurality of threshold values, and wherein the threshold value used for a given path depends upon the position, within the sequence of second signal 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.
-
76. An apparatus according to claim 75, wherein the threshold values used for paths ending towards the beginning of the sequence are larger than the threshold values used for paths ending towards the end of the sequence.
-
77. An apparatus according to claim 72, wherein said processing circuitry is operable to perform a soft pruning operation, whereby some paths which have a cumulative value worse than the threshold are not discarded.
-
78. An apparatus according to claim 51, operable to process the current first signal pattern before the succeeding first signal pattern is received.
-
79. An apparatus according to claim 51, operable to receive the whole first signal before processing the first signal pattern.
-
80. An apparatus according to claim 51, wherein said second signal patterns are representative of a template, and wherein said cumulative values are distance measures.
-
81. An apparatus according to claim 51, wherein said second signal patterns are representative of a statistical model, and wherein said cumulative values are probabilistic measures.
-
82. An apparatus according to claim 51, further comprising comparison circuitry for comparing said first signal with a plurality of second signals.
-
83. An apparatus according to claim 82, operable to allow said first signal to be matched with a sequence of said plurality of second signals, by allowing paths propagating in one second signal to subsequently propagate into another second signal.
-
84. An apparatus according to claim 83, comprising a set of predefined rules for constraining the sequence of second signals against which the first signal can be matched.
-
85. An apparatus according to claim 83, wherein each of said patterns are represented by a plurality of parameter values and wherein said distance measure represents a sum of the magnitude of the difference between the corresponding parameter values of the current first signal pattern and the current active pattern.
-
86. An apparatus according to claim 51, employing a dynamic programming matching technique.
-
87. An apparatus according to claim 51, wherein said processing circuitry is operable to update the cumulative value for a path by adding a distance measure representative of the distance between the current first signal pattern and the current active pattern.
-
88. An apparatus according to claim 87, wherein said distance measure is determined from the following equation:
-
where d(S,f,k) is the distance measure, Sp is the pth parameter value of the current active pattern and fkp is the pth parameter value of the current first signal pattern being processed.
-
-
89. An apparatus according to claim 88, comprising a look up table which is used in the determination of the distance measure which is to be added to the cumulative value of a path.
-
90. An apparatus according to claim 89, wherein the respective parameter values of the current first signal pattern and the current active pattern address the look up table, and wherein the values stored in that location of the look up table corresponds to the difference between the two parameter values.
-
91. An apparatus according to claim 89, wherein prior to processing the current first signal pattern, the apparatus is operable to identify a sub table of look up values using the parameter values of the current first signal pattern, and wherein the distance measure which is to be added to the cumulative value for a path is determined by addressing the sub table of look up values with the parameter values of the current active pattern.
-
94. An apparatus according to claim 51, wherein said first and second signals are representative of speech, and wherein each pattern comprises a number of parameters representative of the acoustic properties of the speech during a corresponding time frame.
-
95. A speech recognition apparatus for recognising an input speech signal by comparing it with a plurality of reference speech signals, the apparatus comprising:
-
extracting circuitry for extracting a sequence of input patterns representative of said input speech signal;
a memory for storing sequences of reference patterns, each sequence being representative of a corresponding reference speech signal;
a pattern matcher for matching the sequence of input patterns with the reference speech signals, using an apparatus according to claim 94; and
output circuitry for outputting a recognition result from the cumulative values determined by said pattern matcher.
-
-
96. An apparatus according to claim 95, wherein said recognition result is provided by determining which of the paths, which end at the last input pattern in the sequence of input patterns, has the best cumulative matcher.
-
97. 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, wherein the apparatus is operable to process each first signal pattern in-turn and comprises:
-
definition circuitry for defining as active patterns the second signal patterns which are at the end of a path for a current first signal pattern being processed, each path representing a possible matching between an ordered sequence of second signal patterns and an ordered sequence of first signal patterns ending at said current first signal pattern;
a memory for storing, for each active pattern, a cumulative value which is indicative of the closeness of the match for the path which ends at that active pattern for said current first signal pattern; and
processing circuitry for processing each active pattern in reverse sequential order to update said cumulative values and to propagate said paths based on constraints which are placed on the path propagation;
wherein each of said patterns is represented by a plurality of parameter values and wherein the cumulative value for a path is updated by adding a distance measure representative of the distance between the current first signal pattern and the current active pattern and wherein the respective parameter values of the current first signal pattern and the current active pattern address a look up table, and wherein the value stored in that location of the look up table corresponds to the difference between the two parameter values. - View Dependent Claims (98, 99, 100)
where TPp is the address of the look up table which is dependent upon the pth parameter of the current first signal pattern and Sp is the pth parameter value of the current active pattern.
-
-
100. An apparatus according to claim 99, wherein TPp is determined once per first signal pattern to be processed.
-
101. A computer readable medium storing computer executable process steps to perform a pattern matching method for 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 steps for processing each first signal pattern in-turn by:
-
defining as active patterns the second signal patterns which are at the end of a path for a current first signal pattern being processed, each path representing a possible matching between an ordered sequence of second signal patterns and an ordered sequence of first signal patterns ending at said current first signal pattern;
for each active pattern, storing a cumulative value which is indicative of the closeness of the match for the path which ends at that active pattern for said current first signal pattern; and
updating said cumulative values and propagating said paths based on constraints which are placed on the path propagation, by processing each active pattern in reverse sequential order, by;
(i) determining which of the second signal patterns the path ending at the current active pattern can propagate to for the succeeding first signal pattern to be processed, based upon said path propagation constraints;
(ii) identifying how many of the second signal patterns determined in step (i) have previously been so determined during the processing of a previous active pattern for the current first signal pattern being processed; and
(iii) propagating the path associated with the current active pattern in dependence upon how many of said second signal patterns are identified in said step (ii). - View Dependent Claims (102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146)
(a) comparing D[S] with D[S+N+1−
m];
(b) if D[S] is better than D[S+N+1−
m], then propagating the path ending at the current active pattern to the second signal pattern S+N+1−
m by making D[S+N+1−
m]=D[S], decrementing m and returning to step (a); and
(c) if D[S] is worse than D[S+N+1−
m], then not propagating the path ending at the current active pattern to the second signal pattern S+N−
1−
m or any second signal pattern sequentially beyond second signal pattern S+N+1−
m;
where S is the current active pattern being processed, N is the number of second signal patterns which are sequentially beyond the current active pattern to which the path ending at the current active pattern can propagate for the succeeding first signal pattern to be processed and m is a positive integer variable which is initially set at the number of second signal patterns identified in said step (ii).
-
-
105. A computer readable medium according to claim 104, wherein said steps (a), (b) and (c) are performed while m is greater than zero.
-
106. A computer readable medium according to claim 104, wherein m is less than N.
-
107. A computer readable medium according to claim 104, further comprising the step of storing the minimum cumulative value of all paths being propagated and wherein if the path associated with the current active pattern is propagated to the second signal pattern S+N by making D[S+N]=D[S], then the method further comprises the steps of comparing D[S] with said minimum cumulative value and making the minimum cumulative value equal to D[S] if D[S] is better than the minimum cumulative value.
-
108. A computer readable medium according to claim 101, wherein said active patterns for the current first signal pattern are listed, in reverse sequential order, in a current active list, and wherein the second signal patterns identified in step (i) are listed, if they are not already listed, in a new active list in reverse sequential order.
-
109. A computer readable medium according to claim 108, further comprising the step of using an identifier to identify the second signal pattern which is the earliest in the sequence of second signal patterns which is listed in the new active list after processing the preceding active pattern, and wherein said step (ii) identifies how many of the second signal patterns determined in step (i) have previously been so determined by determining a positional relationship between the current active pattern being processed and the second signal pattern which is identified by said identifier.
-
110. A computer readable medium according to claim 109, wherein said positional relationship is determined by testing for the different possibilities which the relationship can have.
-
111. A computer readable medium according to claim 110, wherein the method identifies said positional relationship by testing for the following situations:
-
(A) the identifier identifies a second signal pattern which sequentially immediately succeeds the current active pattern being processed;
(B) the identifier identifies a second signal pattern which is sequentially beyond second signal pattern S+N;
(C) the identifier identifies a second signal pattern S+i, for i=1 to N−
1;
where S is the current active pattern being processed and N is the number of second signal patterns which are beyond the current active pattern to which the path ending at the current active pattern can propagate to for the succeeding first signal pattern.
-
-
112. A computer readable medium according to claim 111, wherein the method tests for situation (A) first and only tests for situation (B) if situation (A) is false.
-
113. A computer readable medium according to claim 112, wherein the method tests for situation (C) only if situation (B) is false.
-
114. A computer readable medium according to claim 113, wherein the method test situation (C) for a current value of i and only tests for situation (C) for i+1 if situation (C) for i is false.
-
115. A computer readable medium according to claim 109, wherein after the new active list has been updated by the processing of the current active pattern, said identifier is set to identify the second signal pattern on the new active list which is the earliest in the sequence of patterns representative of the second signal.
-
116. A computer readable medium according to claim 108, wherein a sentinel pattern is added to the end of the current active list so that the method can identify when all the active patterns, for the current first signal pattern, have been processed.
-
117. A computer readable medium according to claim 116, wherein the cumulative value associated with the sentinel pattern is set to a predetermined value, and wherein the method identifies the sentinel pattern by comparing the cumulative value of each active pattern with said predetermined value.
-
118. A computer readable medium according to claim 117, wherein said predetermined value is zero.
-
119. A computer readable medium according to claim 116, wherein after the method has processed all the active patterns on the current active list, the method further comprises the step of adding the sentinel pattern to the end of the new active list.
-
120. A computer readable medium according to claim 101, wherein one of said path propagation constraints is that if a second signal pattern is matched with a first signal pattern, then second signal patterns which are sequentially before that second signal pattern cannot be matched with the succeeding first signal pattern on the same path.
-
121. A computer readable medium according to claim 101, wherein one of said path propagation constraints is that a penalty is added to the cumulative value associated with a path which is matched with the same second signal pattern for consecutive first signal patterns being processed.
-
122. A computer readable medium according to claim 101, wherein the method only updates the cumulative value of the current active pattern and propagates the path associated with the current active pattern if the cumulative value associated therewith is better than a threshold value.
-
123. A computer readable medium according to claim 122, wherein said threshold value is varied in order to try to maintain the number of active patterns processed for each first signal pattern to be below a given maximum number.
-
124. A computer readable medium according to claim 123, wherein the threshold value used during the processing of the succeeding first signal pattern is determined during the processing of the current first signal pattern, and is dependent upon the total number of second signal patterns in the new active list for the succeeding first signal pattern to be processed.
-
125. A computer readable medium according to claim 122, wherein a plurality of threshold values are used, and wherein the threshold value used for a given path depends upon the position, within the sequence of second signal 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.
-
126. A computer readable medium according to claim 125, wherein the threshold values used for paths ending towards the beginning of the sequence is larger than the thresholds used for paths ending towards the end of the sequence.
-
127. A computer readable medium according to claim 122, wherein a soft pruning operation is performed, whereby some paths which have a cumulative value worse than the threshold are not discarded.
-
128. A computer readable medium according to claim 101, wherein the processing of the current first signal pattern is preformed before the succeeding first signal pattern is received.
-
129. A computer readable medium according to claim 101, wherein the whole first signal is received before the first signal pattern is processed.
-
130. A computer readable medium according to claim 101, wherein said second signal patterns are representative of a template, and wherein said cumulative values are distance measures.
-
131. A computer readable medium according to claim 101, wherein said second signal patterns are representative of a statistical model, and wherein said cumulative values are probabilistic measures.
-
132. A computer readable medium according to claim 101, further comprising the step of comparing said first signal with a plurality of second signals.
-
133. A computer readable medium according to claim 132, wherein said first signal can be matched with a sequence of said plurality of second signals, by allowing paths propagating in one second signal to subsequently propagate into another second signal.
-
134. A computer readable medium according to claim 133, wherein the sequence of second signals against which the first signal can be matched is constrained by a set of predefined rules.
-
135. A computer readable medium according to claim 133, wherein each of said patterns are represented by a plurality of parameter values and wherein said distance measure represents a sum of the magnitude of the difference between the corresponding parameter values of the current first signal pattern and the current active pattern.
-
136. A computer readable medium according to claim 101, wherein said method utilises a dynamic programming matching process.
-
137. A computer readable medium according to claim 101, wherein the cumulative value for a path is updated by adding a distance measure representative of the distance between the current first signal pattern and the current active pattern.
-
138. A computer readable medium according to claim 137, wherein said distance measure is determined by using the following equation:
-
where d(S,f,k) is the distance measure, Sp is the pth parameter value of the current active pattern and fkp is the pth parameter value of the current first signal pattern being processed.
-
-
139. A computer readable medium according to claim 138, wherein a look up table is used in the determination of the distance measure which is to be added to the cumulative value of a path.
-
140. A computer readable medium according to claim 139, wherein the respective parameter values of the current first signal pattern and the current active pattern address the look up table, and wherein the values stored in that location of the look up table corresponds to the difference between the two parameter values.
-
141. A computer readable medium according to claim 139, wherein prior to processing the current first signal pattern, the method identifies a sub table of look up values using the parameter values of the current first signal pattern, and wherein the distance measure which is to be added to the cumulative value for a path is determined by addressing the sub table of look up values with the parameter values of the current active pattern.
-
142. A computer readable medium according to claim 139, wherein the distance measure which is to be added to the cumulative value of the path is determined using the following equation:
-
where TPp is the address of the look up table which is dependent upon the pth parameter of the current first signal pattern and Sp is the pth parameter value of the current active pattern.
-
-
143. A computer readable medium according to claim 142, wherein TPp is determined once per first signal pattern to be processed.
-
144. A computer readable medium according to claim 101, wherein said first and second signals are representative of speech, and wherein each pattern comprises a number of parameters representative of the acoustic properties of the speech during a corresponding time frame.
-
145. A computer readable medium storing computer executable process steps to perform a speech recognition method for recognising an input speech signal by comparing it with a plurality of reference speech signals, the process steps comprising the steps of:
-
extracting a sequence of input patterns representative of said input speech signal;
storing sequences of reference patterns, each sequence being representative of a corresponding reference speech signal;
matching the sequence of input patterns with the reference speech signals, using the process steps of claims 144; and
providing a recognition result from the cumulative values determined by said matching step.
-
-
146. A computer readable medium according to claim 145, wherein said recognition result is provided by determining which of the paths, which end at the last input pattern in the sequence of input patterns, has the best cumulative value.
-
147. A computer readable medium storing computer executable process steps to perform a pattern matching method for 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 steps for processing each first signal pattern in-turn by:
-
defining as active patterns the second signal patterns which are at the end of a path for a current first signal pattern being processed, each path representing a possible matching between an ordered sequence of second signal patterns and an ordered sequence of first signal patterns ending at said current first signal pattern;
for each active pattern, storing a cumulative value which is indicative of the closeness of the match for the path which ends at that active pattern for said current first signal pattern; and
updating said cumulative values and propagating said paths based on constraints which are placed on the path propagation, by processing each active pattern in reverse sequential order;
wherein each of said patterns is represented by a plurality of parameter values and wherein the cumulative value for a path is updated by adding a distance measure representative of the distance between the current first signal pattern and the current active pattern and wherein the respective parameter values of the current first signal pattern and the current active pattern address a look up table, and wherein the value stored in that location of the look up table corresponds to the difference between the two parameter values. - View Dependent Claims (148, 149, 150)
where TPp is the address of the look up table which is dependent upon the pth parameter of the current first signal pattern and Sp is the pth parameter value of the current active pattern.
-
-
150. A computer readable medium according to claim 149, wherein TPp is determined once per first signal pattern to be processed.
-
151. A signal for conveying computer executable process steps to perform a pattern matching method for 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 steps for processing each first signal pattern in-turn by:
-
defining as active patterns the second signal patterns which are at the end of a path for a current first signal pattern being processed, each path representing a possible matching between an ordered sequence of second signal patterns and an ordered sequence of first signal patterns ending at said current first signal pattern;
for each active pattern, storing a cumulative value which is indicative of the closeness of the match for the path which ends at that active pattern for said current first signal pattern; and
updating said cumulative values and propagating said paths based on constraints which are placed on the path propagation, by processing each active pattern in reverse sequential order, by;
(i) determining which of the second signal patterns the path ending at the current active pattern can propagate to for the succeeding first signal pattern to be processed, based upon said path propagation constraints;
(ii) identifying how many of the second signal patterns determined in step (i) have previously been so determined during the processing of a previous active pattern for the current first signal pattern being processed; and
(iii) propagating the path associated with the current active pattern in dependence upon how many of said second signal patterns are identified in said step (ii). - View Dependent Claims (152)
extracting a sequence of input patterns representative of said input speech signal;
storing sequences of reference patterns, each sequence being representative of a corresponding reference speech signal;
matching the sequence of input patterns with the reference speech signals, using the process steps according to claim 151; and
providing a recognition result from the cumulative values determined by said matching step.
-
-
153. A signal conveying computer executable process steps to perform 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 process steps comprising steps for processing each first signal pattern in-turn by:
-
defining as active patterns the second signal patterns which are at the end of a path for a current first signal pattern being processed, each path representing a possible matching between an ordered sequence of second signal patterns and an ordered sequence of first signal patterns ending at said current first signal pattern;
for each active pattern, storing a cumulative value which is indicative of the closeness of the match for the path which ends at that active pattern for said current first signal pattern; and
updating said cumulative values and propagating said paths based on constraints which are placed on the path propagation, by processing each active pattern in reverse sequential order;
wherein each of said patterns is represented by a plurality of parameter values and wherein the cumulative value for a path is updated by adding a distance measure representative of the distance between the current first signal pattern and the current active pattern and wherein the respective parameter values of the current first signal pattern and the current active pattern address a look up table, and wherein the value stored in that location of the look up table corresponds to the difference between the two parameter values.
-
Specification