Pattern recognition method and system

• US 5,982,929 A
• Filed: 04/07/1995
• Issued: 11/09/1999
• Est. Priority Date: 04/10/1994
• Status: Expired due to Term

• Current Assignee: Advanced Recognition Technologies, Inc.
• Original Assignee: Advanced Recognition Technologies, Inc.
• Inventors: Aharonson, Eran, Ilan, Gabriel
• Primary Examiner(s): Chang, Jon
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/418,530
• Time in Patent Office: 1,677 Days
• Field of Search: 364/419.05, 364/419.08, 364/419.02, 364/419.01, 382/159, 382/186, 382/187, 382/195, 382/202, 382/225, 382/226, 382/227, 382/228, 382/229, 382/230, 382/231, 704/2, 704/9, 704/5
• US Class Current: 382/200
• CPC Class Codes: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models

Abstract

A method for pattern recognition of indicia composed of alphabetical characters of a language in the form of at least a part of a word. The shape of each character in a word is established by means of a pattern shape recognizer. A probability value designating the relative confidence in the recognition of the character as one of the language characters is assigned to each character. The established shapes of the characters are then sequentially applied to a linguistic recognizer for further processing and the probability values of language structure to each of the language characters is assigned. Then the probability values assigned to the characters in the shape recognizer is combined with the corresponding probability values assigned to the characters in the linguistic recognizer and the path between characters possessing the highest probability values is determined.

Claims

1. A method for pattern recognition of shapes representative of characters defining alphabetic characters, numbers and other symbols, the method comprising the steps of:

identifying, for each of the shapes, at least one candidate character that may be represented by the shape;

forming paths by connecting each candidate character to a previous candidate character or previous candidate characters appearing in a sequence of candidate characters immediately preceding the candidate character;

calculating, for each of the candidate characters, a character probability value representative of a relative confidence in the recognition of an associated shape as that candidate character;

forming said character probability values for each candidate character by blending the character probability values associated with the candidate character and the probability values of language structure associated with the candidate character;

determining best path pointers for identifying a path from each candidate character to a candidate character of an immediate previous stage having a highest character probability value;

selecting, based on analysis of at least one candidate character, which type of probability values of language structure to apply to the candidate characters;

applying, in response to the determining step, the candidate characters to a linguistic recognizer to assign probability values of language structure to the candidate characters; and

identifying a path having a highest path probability value wherein a path probability value is based on at least one of the group consisting of character probability values associated with a path and probability values of language structure associated with a path.

2. The method of claim 1 wherein the analysis of at least one candidate character comprises comparing at least one of the character probability values with at least one other probability value.

3. The method of claim 2 wherein the at least one other probability value comprises at least one threshold value that is representative of whether the characters define a lingual character sequence.

4. The method of claim 2 wherein the at least one other probability value comprises a word probability value.

5. The method of claim 1 wherein the analysis of at least one candidate character comprises determining whether the candidate characters represent a lingual character sequence.

6. The method of claim 5 further comprising the step of combining, for each character, the character probability value associated with the character and the probability value of language structure associated with the character.

7. The method of claim 6 further comprising the step of selecting the probability values of language structure from the group of types consisting of language statistical N-grams, where N is a positive integer, and language syntax descriptions.

8. The method of claim 1 wherein the selected type of probability values of language structure comprises statistical dictionary entries.

9. The method of claim 8 further comprising the steps of:

obtaining, for each of the paths, a word probability value from a statistical dictionary component and identifying a path having a highest word probability value; and

selecting, from the highest probability path and the highest word probability path, a path with a highest probability.

10. The method of claim 1 further comprising the step of selecting the probability values of language structure from the group of types consisting of statistical dictionary entries, language statistical N-grams, where N is a positive integer, and language syntax descriptions.

11. A pattern recognition system for recognizing shapes representative of characters defining alphabetic characters, numbers and other symbols, the system comprising:

a pattern shape recognizer, including an input device;

a digitizer;

a segmentation unit;

feature extraction unit; and

a classification unit for classifying extracted features of the shapes into vectors of candidate characters, each vector constituted by at least one candidate character and at least one path indicator defining possible character sequences between candidate characters corresponding to the shapes, said classification unit assigning to each candidate character a character probability value designating the relative confidence in the recognition of an associated shape as that candidate character;

a linguistic recognizer, adapted to receive the vectors of candidate characters having assigned character probability values, for analyzing at least one candidate character to select which type of probability values of language structure to apply to the candidate characters and for assigning probability values of language structure to the candidate characters to form edge probability values;

a vector selector for identifying a vector having a highest path probability value wherein a path probability value is based on at least one of the group consisting of character probability values associated with a path and probability values of language structure associated with a path;

wherein said linguistic recognizer further comprises;

means for forming paths by connecting each candidate character to a previous candidate character or previous candidate characters appearing in a sequence of candidate characters immediately preceding the candidate character;

means for forming character probability values for each candidate character by blending the character probability values associated with the candidate character and the probability values of language structure associated with the candidate character; and

means for determining best path pointers for identifying a path from each candidate character to a candidate character of an immediate previous stage having a highest character probability value.

12. The system of claim 11 wherein the linguistic recognizer compares at least one of the character probability values with at least one other probability value during the analysis of at least one candidate character.

13. The system of claim 12 wherein the at least one other probability value comprises at least one threshold value that is representative of whether the characters define a lingual character sequence.

14. The system of claim 13 wherein the linguistic recognizer selects the probability values of language structure from the group of types consisting of language statistical N-grams, where N is a positive integer, and language syntax descriptions.

15. The system of claim 12 wherein the at least one other probability value comprises a word probability value.

16. The system of claim 11 wherein the linguistic recognizer determines whether the candidate characters represent a lingual character sequence during the analysis of at least one candidate character.

17. The system of claim 16 wherein the linguistic recognizer combines, for each character, the character probability value associated with the character and the probability value of language structure associated with the character.

18. The system of claim 17 wherein selected type of probability values of language structure comprises statistical dictionary entries.

19. The system of claim 17 wherein the vector selector further comprises:

means for obtaining, for each of the vectors, a word probability value from a statistical dictionary component and identifying a vector having a highest word probability value; and

means for selecting, from the highest probability vector and the highest word probability vector, a vector with a highest probability.

20. The system of claim 17 wherein the linguistic recognizer selects the probability values of language structure from the group types consisting of statistical dictionary entries, language statistical N-grams, where N is a positive integer, and language syntax descriptions.