Patent EP0789349A2 successfully refreshed from Google Patents.
EP0789349A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Pattern matching method and apparatus and telephone system
Assignee: Canon Inc
•
Filing: 1997-02-07
•
Granted: —
•
Expires: 2017-02-07
Abstract
Abstract A method for matching an input pattern with a number of stored reference patterns using a dynamic programming matching technique is described. The reference patterns of a reference signal which are at the end of a dynamic programming path for a current input pattern are listed in an active list 201. The dynamic programming paths are propagated by processing the reference patterns on the active list, and a new active list 205 is generated for the succeeding input pattern. The amount of processing required for each pattern on the active list is reduced by using a pointer which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed on the new active list during the processing of a preceding dynamic programming path. In a second aspect, a speech recognition interface is used as a control system for a telephony system.
Inventors
- 👤 Eli Canon Res. Centre Europe Ltd Tzirkel-Hancock
- 👤 Alexander Canon Res. Centre Europe Ltd. Keiller
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 11:52
CPC Classifications
H; H04; H04M; H04M3/00; H04M3/42; H04M3/50; H04M3/53; H04M3/533; G; G10; G10L; G10L15/00; G10L15/08; G10L15/12; H04M3/42204; G10L2015/085; H04M1/00; H04M1/26; H04M1/27; H04M1/271; H04M1/57; H04M1/64; H04M1/65; H04M1/6505; H04M2201/00; H04M2201/40; H04M3/53366; H04M3/53383
Claims Analysis
Total Claims: 62
Claim 1
Independent Claim
383 words
A method of performing a dynamic programming pattern matching process between a sequence of input patterns representative of an input signal, and a number of stored sequences of reference patterns, each sequence being representative of a reference signal, wherein the method processes each input pattern in turn with respect to at least some of the reference signals in turn, by: (1) defining as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for a current input pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and listing the active patterns for the current input pattern in a current active list; (2) for each active pattern, storing in a store associated with that active pattern, a cumulative value representative of the score for the dynamic programming path which ends at that active pattern for said current input pattern; and (3) updating said cumulative values and propagating said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, by processing each active pattern of said current reference signal in reverse sequential order, by: (A) updating the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and then (B) propagating the dynamic programming path associated with the current active pattern, and listing, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in anew active list; and wherein the propagation of each dynamic programming path for a current reference signal is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the propagation of each dynamic programming path is achieved without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of processing preceding active patterns.
Claim 2
Dependent Claim
100 words
A method according to claim 1, wherein the following steps are performed in step 3(B): (i) determining which of the reference patterns of the current reference signal are potentially at an end of the dynamic programming path which ends at said current active pattern for said succeeding input pattern, based upon said constraints which are placed on the dynamic programming path propagation; and then (ii) propagating the dynamic programming path, updating the new active list and copying appropriate cumulative values into stores associated with the reference patterns determined in step (i), by processing each reference pattern determined in step (i).
Claim 3
Dependent Claim
171 words
A method according to claim 2, wherein each reference pattern determined in step (i) of claim 2, except the current active pattern if it is one of those reference patterns, is processed by: (a) determining whether a current reference pattern being processed is sequentially beyond any reference pattern identified by said pointer; then (b) if the current reference pattern is the same as or sequentially beyond the identified reference pattern, then copying the cumulative value stored in the store associated with said current active pattern into the store associated with the current reference pattern, if it is better than the cumulative value already stored there; and (c) if the current reference pattern is sequentially before the identified reference pattern or if there are no reference patterns of the current reference signal in the new active list, then copying the cumulative value stored in the store associated with said current active pattern into the store associated with said current reference pattern, and listing said current reference pattern in the new active list.
Claim 4
Dependent Claim
69 words
A method according to claim 2 or 3, wherein if one of the reference patterns determined in step (i) of claim 2 is the current active pattern, then the processing of the current active pattern in step (ii) of claim 2 comprises the step of listing the current active pattern in the new active list, if this is not contrary to any constraint placed on the dynamic programming process.
Claim 5
Independent Claim
58 words
A method according to any preceding claim, wherein after the new active list has been updated by the processing of the current active pattern, said pointer associated with the current reference signal is set to identify the reference pattern on the new active list which is the earliest in the sequence of patterns of the current reference signal.
Claim 6
Independent Claim
24 words
A method according to any preceding claim, wherein the processing of the current input pattern is performed before the succeeding input pattern is received.
Claim 7
Independent Claim
24 words
A method according to any of claims 1 to 5, wherein the whole input signal is received before the first input pattern is processed.
Claim 8
Independent Claim
22 words
A method according to any preceding claim, wherein each reference signal has associated therewith a current active list and new active list.
Claim 9
Independent Claim
26 words
A method according to any preceding claim, wherein when a reference pattern is added to said new active list it is placed at the end thereof.
Claim 10
Dependent Claim
27 words
A method according to any of claims 2 to 9, wherein the reference patterns processed in step (ii) of claim 2, are processed in reverse sequential order.
Claim 11
Dependent Claim
34 words
A method according to any preceding claim, wherein the method only performs step (3) of claim 1 for the current active pattern, if the cumulative value associated therewith is better than a threshold value.
Claim 12
Dependent Claim
33 words
A method according to claim 11, wherein said threshold value is varied to try to maintain the number of active patterns processed for each input pattern to be below a given maximum number.
Claim 13
Dependent Claim
51 words
A method according to claim 12, wherein the threshold value used during the processing of the succeeding input pattern is determined during the processing of the current input pattern, and is dependent upon the total number of reference patterns in the new active list or lists for the succeeding input pattern.
Claim 14
Independent Claim
41 words
A method according to any preceding claim, wherein one of said dynamic programming constraints is that a limit is placed on the number of consecutive input patterns that a reference pattern can be matched with, on the same dynamic programming path.
Claim 15
Independent Claim
54 words
A method according to any preceding claim, wherein one of said dynamic programming constraints is that if a reference pattern is matched with an input pattern, then a limited number of reference patterns which are sequentially beyond that reference pattern can be matched with the succeeding input pattern, on the same dynamic programming path.
Claim 16
Independent Claim
51 words
A method according to any preceding claim, wherein one of said dynamic programming constraints is that if a reference pattern is matched with an input pattern, then reference patterns which are sequentially before that reference pattern can not be matched with the succeeding input pattern, on the same dynamic programming path.
Claim 17
Independent Claim
24 words
A method according to any preceding claim, wherein said reference patterns are representative of a template, and wherein said cumulative values are distance measures.
Claim 18
Independent Claim
28 words
A method according to any of claims 1 to 16, wherein said reference patterns are representative of a statistical model, and wherein said cumulative values are probabilistic measures.
Claim 19
Independent Claim
38 words
A method according to any preceding claim, wherein said input signal can be matched with a sequence of said reference signals, by allowing dynamic programming paths propagating in one reference signal to subsequently propagate into other reference signals.
Claim 20
Dependent Claim
36 words
A method according to claim 19, wherein only the dynamic programming path which has the best cumulative value of all the dynamic programming paths which leaves the reference pattern for the current input pattern, propagates further.
Claim 21
Dependent Claim
30 words
A method according to claim 19 or 20, wherein the sequence of reference signals, against which the input signal can be matched, is constrained by a set of defined rules.
Claim 22
Independent Claim
93 words
A method according to any of claims 19 to 21, wherein after the current input pattern has been processed with respect to the reference signals, the method processes those reference signals to update the new active list and to update the cumulative values associated with the reference patterns at the beginning of those reference signals, which are potentially at an end of a dynamic programming path which enters the corresponding reference signal, based upon said constraints, using the best cumulative value of all the dynamic programming paths which can enter that reference signal.
Claim 23
Independent Claim
41 words
A method according to any preceding claim, wherein said input signal is representative of a speech signal, and wherein each input pattern comprises a number of parameters representative of the acoustic properties of the speech signal during a corresponding time frame.
Claim 24
Dependent Claim
32 words
A method according to claim 23, wherein said input speech signal can be matched to a sequence of reference speech signals, and wherein the allowed sequences are defined by a language model.
Claim 25
Dependent Claim
39 words
A method according to claim 24, wherein the end of a dynamic programming path which leaves a reference signal when processing the current input pattern can be matched with a pattern representative of background noise for succeeding input patterns.
Claim 26
Dependent Claim
88 words
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 any of claims 23 to 25; and providing a recognition result from cumulative values determined by said matching step.
Claim 27
Dependent Claim
35 words
A method according to claim 26, wherein said recognition result is provided by determining which of the dynamic programming paths which end at the last input pattern in the sequence has the best cumulative value.
Claim 28
Independent Claim
143 words
A method for adapting existing reference models which are used in a pattern matching system, wherein each reference model comprises a sequence of reference patterns, the method comprising the steps of: (a) inputting a number of input signals for which the content is known; (b) processing each input signal to generate a sequence of representative input patterns; (c) for each input signal, aligning the representative sequence of input patterns with the sequence or sequences of reference patterns of the existing reference model or models of the signals known to be in that input signal; (d) for each reference pattern which is aligned with a number of input patterns of one or more input signals: (i) combining the input patterns of the aligned input signals; and (ii) replacing that reference pattern of the reference model with the combined input pattern determined in step (i).
Claim 29
Dependent Claim
16 words
A method according to claim 28, wherein the aligned input patterns are combined by averaging them.
Claim 30
Dependent Claim
29 words
A method according to claim 28 or 29, wherein said reference models represent speech, and wherein said input signals are speech signals for which the speech content is known.
Claim 31
Dependent Claim
17 words
A method according to claim 30, wherein each reference model is representative of one or more words.
Claim 32
Independent Claim
65 words
A method according to any of claims 28 to 31, wherein for each reference pattern of a reference model aligned with at least one input signal for which there are no aligned input patterns of the input signals, that reference pattern is replaced with a pattern derived by interpolating between or extrapolating from neighbouring reference patterns of that reference model which have already been replaced.
Claim 33
Dependent Claim
23 words
A method according to claim 32, wherein said reference pattern is replaced by interpolating between or extrapolating from the nearest neighbouring reference patterns.
Claim 34
Dependent Claim
20 words
A data carrier programmed with software for carrying out a method according to any one of claims 1 to 33.
Claim 35
Independent Claim
15 words
An apparatus for carrying out a method according to any of claims 1 to 33.
Claim 36
Dependent Claim
138 words
A control system for controlling a telephony system, comprising: a speech recognition user interface for allowing a user to input speech commands for controlling the telephony system, and for outputting a recognition result based on comparing the input speech commands with pre-stored reference models; control means, responsive to the recognition result output from the interface, for controlling the telephony system in accordance with an input speech command; characterised in that the speech recognition user interface is adapted to be able to recognise continuously spoken commands comprising a plurality of words defining a desired telephony service and an identifier of another user by comparing allowed sequences of word models, defined by a stored language model, with the input speech command, and in that the control means comprises execution means for executing an operation corresponding to the input speech command.
Claim 37
Dependent Claim
114 words
A telephony system comprising: a speech recognition user interface for allowing a user to input speech commands for controlling telephony services provided by the system, and for outputting a recognition result based on comparing the input speech commands with pre-stored reference models; and execution means, responsive to the recognition result output from the interface, for executing an operation corresponding to the speech command; wherein each user of the system is identified by a telephone number and an associated identifier, and wherein the execution means is adapted to predict, using current system status information, what telephony service is wanted, if the user inputs, via the speech recognition user interface, only the identifier of another user.
Claim 38
Dependent Claim
108 words
A system according to claim 36 or 37, wherein the execution means is adapted to communicate with users of the system in dependence upon information representative of the current status of the system, wherein the execution means is adapted i) to hold the current system status information; ii) to check that the operation corresponding to the speech command does not conflict with the current system status information; and iii) if there is no conflict, to request the user to confirm the speech command prior to execution, and wherein a buffer is provided for buffering new system status information which is generated whilst the execution means awaits user confirmation.
Claim 39
Dependent Claim
62 words
A system according to claim 37 or 38, wherein the status information comprises, for each user, a selection from: who the user is currently speaking to, who the user is dialling, who is on hold, who is trying to ring that user, whether that user is playing messages, who has that user on hold and who has that user in a conference.
Claim 40
Independent Claim
43 words
A system according to any one of claims 36 to 39, wherein the telephony services comprises a selection from: setting up a call, transferring a call, holding a call, returning to a call, setting up a conference call and message selection and replaying.
Claim 41
Independent Claim
31 words
A system according to any one of claims 36 to 40, wherein the control means further comprises interpretation means for interpreting the recognition result, which uses a factory set pre-stored dictionary.
Claim 42
Independent Claim
54 words
A system according to any one of claims 36 to 41, wherein each user in the system has an associated storage means for storing the telephone numbers and associated identifiers of other users, whereby a user can designate another user of the system by speaking the corresponding identifier into the speech recognition user interface.
Claim 43
Dependent Claim
46 words
A system according to claim 42 when not dependent upon claim 37, wherein the execution means is adapted to predict, using current system status information, what telephony service is wanted if the user inputs, via the speech recognition user interface, only the identifier of another user.
Claim 44
Independent Claim
25 words
A system according to any one of claims 36 to 43, wherein the speech recognition user interface can be trained to recognise new speech commands.
Claim 45
Dependent Claim
48 words
A system according to claim 44, wherein means is provided for adapting the language model to accommodate the new speech commands, and wherein means is provided for generating new reference models for those words in the new speech commands for which there is not an existing reference model.
Claim 46
Independent Claim
21 words
A system according to any one of claims 36 to 45, wherein each user has an associated set of reference models.
Claim 47
Independent Claim
16 words
A system according to any one of claims 36 to 46 provided in a local exchange.
Claim 48
Dependent Claim
42 words
A telephony system comprising a control system according to any one of claims 36 to 47 for controlling the telephony system and a number of communication devices for use by users of the telephony system, which are interconnected via a local exchange.
Claim 49
Dependent Claim
33 words
A system according to claim 48, wherein the execution means is adapted to communicate with each of the users via the respective communication devices, information representative of the current status of the system.
Claim 50
Dependent Claim
40 words
A system according to claim 48 or 49, wherein at least some of the communication devices have an associated display arranged to display messages representative of the operation corresponding to the input speech command, for a predetermined amount of time.
Claim 51
Independent Claim
40 words
A system according to any of claims 48 to 50, wherein the local exchange is connected to the public exchange so that users connected to the local exchange can communicate with remote users on the public exchange and vice versa.
Claim 52
Independent Claim
36 words
A system according to any of claims 48 to 51, further comprising a mail box facility which stores messages for users of the system left by callers, when the users are unable to take the calls.
Claim 53
Dependent Claim
28 words
A system according to claim 52, wherein each message stored in the mail box facility is associated with the telephone number of the caller who left the message.
Claim 54
Dependent Claim
26 words
A system according to claim 53, wherein users can request, via the speech recognition user interface, the mail box to replay messages from a particular caller.
Claim 55
Dependent Claim
37 words
A system according to claim 54, wherein after replaying one of a plurality of selected messages a user can access other telephony services and return and replay the remaining selected messages after using those other telephony services.
Claim 56
Independent Claim
32 words
A system according to any of claims 48 to 55, wherein the use of the speech recognition user interface and the execution means is time multiplexed between a number of different users.
Claim 57
Independent Claim
32 words
A system according to any of claims 48 to 56, wherein a plurality of speech recognition user interfaces and execution means are provided, for simultaneous use by a plurality of different users.
Claim 58
Independent Claim
15 words
A system according to any of claims 36 to 44, provided in a communication device.
Claim 59
Dependent Claim
35 words
A system according to any one of claims 36 to 58 in which said speech recognition user interface is arranged to recognise an input speech command using a speech recognition method according to claim 26.
Claim 60
Independent Claim
67 words
A method of controlling a telephony system comprising the steps of: providing a system according to any preceding claim; inputting a speech command into the system via the speech recognition user interface; outputting a recognition result based on a comparison of the input speech command with pre-stored reference models made by the speech recognition user interface; and controlling the telephony system in response to the recognition result.
Claim 61
Dependent Claim
15 words
A data carrier programmed with software for carrying out a method according to claim 60.
Claim 62
Dependent Claim
131 words
A mail box facility for use with a telephony system, comprising: a speech recognition user interface for allowing a user to input speech commands for controlling the mail box facility, and for outputting a recognition result based on comparing the input speech commands with pre-stored reference models; control means, responsive to the recognition result output from the interface, for controlling the mail box facility in accordance with an input speech command; and storage means for storing messages left by callers, when the users are unable to take the calls; characterised in that each message stored in the mailbox is associated with the telephone number of the caller who left the message, whereby users can request, via the speech recognition user interface, the mailbox facility to replay messages from a particular caller.
References Cited (Backward Citations)
US4592086A
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.