Pattern matching method and apparatus

• US 7,295,980 B2
• Filed: 08/31/2006
• Issued: 11/13/2007
• Est. Priority Date: 10/28/1999
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Garner, Philip Neil, Charlesworth, Jason Peter Andrew, Higuchi, Asako
• Primary Examiner(s): {hacek over (S)}mits; Talivadis Ivars
• Assistant Examiner(s): Rider; Justin W.
• Application Number:
  US11/513,064
• Publication Number:
  US 20070150275A1
• Time in Patent Office: 439 Days
• Field of Search: 704/254
• US Class Current: 704/254
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/3343 using phonetics
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/685 using automatically derived transcript of audio data, e.g. lyrics speech recognition G10L15/00

Abstract

A system is provided for matching two or more sequences of phonemes both or all of which may be generated from text or speech. A dynamic programming matching technique is preferably used having constraints which depend upon whether or not the two sequences are generated from text or speech and in which the scoring of the dynamic programming paths is weighted by phoneme confusion scores, phoneme insertion scores and phoneme deletion scores where appropriate.

Claims

1. A feature comparison apparatus comprising:

a receiver operable to receive first and second sequences of features;

an aligner operable to align features of the first sequence with features of the second sequence to form a number of aligned pairs of features;

a comparator operable to compare the features of each aligned pair of features formed by said aligner to generate a comparison score representative of the similarity between the aligned pair of features; and

a combiner operable to combine the comparison scores for all the aligned pairs of features to provide a measure of the similarity between the first and second sequences of features;

wherein said comparator comprises;

a first sub-comparator operable to compare, for each aligned pair, the first sequence feature in the aligned pair with each of a plurality of features taken from a set of predetermined features to provide a corresponding plurality of intermediate comparison scores representative of the similarity between said first sequence feature and the respective features from the set;

a second sub-comparator operable to compare, for each aligned pair, the second sequence feature in the aligned pair with each of said plurality of features from the set to provide a further corresponding plurality of intermediate comparison scores representative of the similarity between said second sequence feature and the respective features from the set; and

a calculator operable to calculate said comparison score for the aligned pair by combining said pluralities of intermediate comparison scores.

2. An apparatus according to claim 1, wherein said first and second sub-comparators are operable to compare the first sequence feature and the second sequence feature respectively with each of the features in said set of predetermined features.

3. An apparatus according to claim 1, wherein said comparator is operable to generate a comparison score for an aligned pair of features which represents a probability of confusing the second sequence feature of the aligned pair as the first sequence feature of the aligned pair.

4. An apparatus according to claim 3, wherein said first and second sub-comparators are operable to provide intermediate comparison scores which are indicative of a probability of confusing the feature taken from the set of predetermined features as the corresponding feature in the aligned pair.

5. An apparatus according to claim 4, wherein said calculator is operable (i) to multiply the intermediate scores obtained when comparing the first and second sequence features in the aligned pair with the corresponding feature from the set to provide a plurality of multiplied intermediate comparison scores;

and (ii) to add the resulting multiplied intermediate scores, to calculate said comparison score for the aligned pair.

6. An apparatus according to claim 5, wherein each of said features in said set of predetermined features has a predetermined probability of occurring within a sequence of features, and wherein said calculator is operable to weight each of said multiplied intermediate comparison scores with the respective probability of occurrence for the feature from the set used to generate the multiplied intermediate comparison scores.

7. An apparatus according to claim 5, wherein said intermediate scores represent log probabilities, and wherein said calculator is operable to perform said multiplication by adding the respective intermediate scores and to perform said addition of said multiplied scores by performing a log addition calculation.

8. An apparatus according to claim 1, wherein said aligner is operable to identify feature deletions and insertions in said first and second sequences of features, and wherein said comparator is operable to generate said comparison score for an aligned pair of features in dependence upon feature deletions and insertions which are identified by said aligner and which occur in the vicinity of the features in the aligned pair.

9. An apparatus according to claim 1, wherein said aligner comprises a dynamic programmer for aligning said first and second sequences of features using a dynamic programming technique.

10. An apparatus according to claim 9, wherein said dynamic programmer is operable to progressively determine a plurality of possible alignments between said first and second sequences of features, and wherein said comparator is operable to determine a comparison score for each of the possible aligned pairs of features determined by said dynamic programmer.

11. An apparatus according to claim 9, wherein said dynamic programmer is operable to determine an optimum alignment between said first and second sequences of features, and wherein said combiner is operable to provide said measure of the similarity between said first and second sequences of features by combining the comparison scores only for the optimum aligned pairs of features.

12. An apparatus according to claim 1, wherein each of the features in said first and second sequences of features belong to said set of predetermined features, and wherein said first and second sub-comparators are operable to provide said intermediate scores using predetermined data which relates the features in said set to each other.

13. An apparatus according to claim 12, wherein the predetermined data used by said first sub-comparator is dependent upon the system used to generate the first sequence of features, and wherein the predetermined data used by said second sub-comparator depends upon the system used to generate the second sequence of features and is different than the predetermined data used by said first sub-comparator.

14. An apparatus according to claim 12, wherein the predetermined data comprises, for each feature in the set of features, a probability of confusing that feature with each of the other features in the set of features.

15. An apparatus according to claim 1, wherein said first and second sequences of features represent time sequential signals.

16. An apparatus according to claim 1, wherein said first and second sequences of features represent audio signals.

17. An apparatus according to claim 1, wherein said first sequence of features comprises a plurality of sub-word units generated from a typed input, and wherein said first sub-comparator is operable to provide said intermediate comparison scores based on mis-typing probabilities and/or mis-spelling probabilities.

18. An apparatus according to claim 1, wherein said second sequence of features comprises a sequence of sub-word units generated from a spoken input, and wherein said second sub-comparator is operable to provide said intermediate scores based on mis-recognition probabilities.

19. An apparatus according to claim 1, wherein said receiver is operable to receive three or more sequences of features;

wherein said aligner is operable to align the features of each of the received sequences of features to form a number of aligned groups of features;

wherein said comparator is operable to compare the features in each aligned group of features to generate a comparison score representative of the similarity between the aligned group of features; and

wherein said combiner is operable to combine the comparison scores for all the aligned groups of features to provide a measure of the similarity between the three or more sequences of features.

20. An apparatus according to claim 19, wherein said aligner is operable to simultaneously align the sequences of features with each other.

21. An apparatus according to claim 1, wherein said receiver is operable to receive a plurality of second sequences of features, wherein said aligner is operable to align said first sequence of features with each of said second sequences of features to form a number of aligned pairs of features for each alignment, and wherein said combiner is operable to combine the comparison scores for each alignment to provide respective measures of the similarity between the first sequence of features and each second sequence of features of said plurality of second sequences of features.

22. An apparatus according to claim 21, further comprising a second comparator operable to compare said similarity measures output by said combiner and to output a signal indicative of the second sequence of features which is most similar to said first sequence of features.

23. An apparatus according to claim 21, wherein said combiner comprises a normalizer operable to normalize each of said similarity measures.

24. An apparatus according to claim 23, wherein said normalizer is operable to normalize each similarity measure by dividing each similarity measure by a respective normalisation score which varies in dependence upon the length of the corresponding second sequence of features.

25. An apparatus according to claim 24, wherein said aligner comprises a dynamic programmer operable to align said first and second sequences of features using a dynamic programming technique and operable to progressively determine a plurality of possible alignments between said first and second sequences of features, and wherein said normalizer is operable to calculate the respective normalisation scores during the progressive calculation of said possible alignments by said dynamic programmer.

26. An apparatus for searching a database comprising a plurality of information entries to identify information to be retrieved therefrom, each of said plurality of information entries having an associated annotation comprising a sequence of features, the apparatus comprising:

a receiver operable to receive an input query comprising a sequence of features;

an apparatus according to claim 1 for comparing the query sequence of features with the features of each annotation to provide a set of comparison results; and

an identifier operable to identify said information to be retrieved from said database using said comparison results.

27. A feature comparison method comprising:

receiving first and second sequences of features;

aligning features of the first sequence with features of the second sequence to form a number of aligned pairs of features;

comparing the features of each aligned pair of features to generate a comparison score representative of the similarity between the aligned pair of features; and

combining the comparison scores for all the aligned pairs of features to provide a measure of the similarity between the first and second sequences of features;

wherein said comparing step comprises;

a first comparing step of comparing, for each aligned pair, the first sequence feature in the aligned pair with each of a plurality of features taken from a set of predetermined features to provide a corresponding plurality of intermediate comparison scores representative of the similarity between said first sequence feature and the respective features from the set;

a second comparing step of comparing, for each aligned pair, the second sequence feature in the aligned pair with each of said plurality of features from the set to provide a further corresponding plurality of intermediate comparison scores representative of the similarity between said second sequence feature and the respective features from the set; and

calculating said comparison score for the aligned pair by combining said pluralities of intermediate comparison scores.