Pattern matching method and apparatus
AssigneeCanon Kabushiki Kaisha
InventorsRobert Alexander Keiller, Eli Tzirkel-Hancock, Julian Richard Seward
Life of this patent
Estimating the term…
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.
Claims60
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 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 a current first signal pattern being processed, and each path having an associated cumulative score representative of the closeness of the match;
- controlling the matching step during the processing of the current first signal pattern by:
- (i) defining a range of cumulative scores a predetermined amount from a current best cumulative score of a current best path representing the current best match between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed;
- and
- (ii) discarding some but not all of the paths having a cumulative score within said range of cumulative scores.
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 a current first signal pattern being processed, and each path having an associated cumulative score representative of the closeness of the match;
- a controller for controlling the pattern matcher during the processing of the current first signal pattern comprising:
- (i) a range definer for defining a range of cumulative scores a predetermined amount from a current best cumulative score of a current best path representing the current best match between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed;
- and
- (ii) a path discarder operable to discard some but not all of the paths having a cumulative score within said range of cumulative scores.
A computer readable medium storing 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 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 a current first signal pattern being processed, and each path having an associated cumulative score representative of the closeness of the match;
- controlling the matching step during the processing of the current first signal pattern by:
- (i) defining a range of cumulative scores a predetermined amount from a current best cumulative score of a current best path representing the current best match between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed;
- and
- (ii) discarding some but not all of the paths having a cumulative score within said range of cumulative scores.
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 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 a current first signal pattern being processed, and each path having an associated cumulative score representative of the closeness of the match;
- controlling the matching step during the processing of the current first signal pattern by:
- (i) defining a range of cumulative scores a predetermined amount from a current best cumulative score of a current best path representing the current best match between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed;
- and
- (ii) discarding some but not all of the paths having a cumulative score within said range of cumulative scores.
A computer executable program for controlling processor to perform a pattern matching method of matching a first sequence of patterns representative of a first signal with a second sequence of pattern representative of a second signal, the program comprising:
- code 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 a current first signal pattern being processed, and each path having an associated cumulative score representative of the closeness of the match;
- code for controlling the matching code during the processing of the current first signal pattern, comprising:
- (i) code for defining a range of cumulative scores a predetermined amount from a current best cumulative score of a current best path representing the current best match between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed;
- and
- (ii) code for discarding some but not all of the paths having a cumulative score within said range of cumulative scores.
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:
- means 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 a 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 a current first signal pattern being processing, and each path having an associated cumulative score representative of the closeness of the match;
- means for controlling the matching means during the processing of the current first signal pattern comprising:
- (i) means for defining a range of cumulative scores a predetermined amount from a current best cumulative score of a current best path representing the current best match between a sequence of second signal patterns and a sequence of first signal patterns ending at the current first signal pattern being processed;
- and
- (ii) means for discarding some but not all of the paths having a cumulative score within said range of cumulative scores.
Dependencies are inferred from the claim text.