Pattern recognition employing arbitrary segmentation and compound probabilistic evaluation

• US 5,862,259 A
• Filed: 03/27/1996
• Issued: 01/19/1999
• Est. Priority Date: 03/27/1996
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Caere Corp. (Mexico) (Microsoft Corporation)
• Inventors: Yang, Jun, Choy, Kenneth, Pon, Leonard, Bokser, Mindy
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US08/622,988
• Time in Patent Office: 1,028 Days
• Field of Search: 382/171, 382/173, 382/177, 382/179, 382/228, 382/229, 382/156
• US Class Current: 382/228
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/153 using recognition of characters or words

Abstract

A pattern recognition system classifies images of patterns in which the definition of individual features of the pattern may have become blurred. The image is segmented into pieces of arbitrary size and shape, and various combinations are examined to determine those which represent the most likely segmentation of the pattern into its individual features. These individual features are then classified, according to known techniques. Through the use of a second order Markov model, not all possible combinations of pieces need to be examined, to determine the best ones. Rather, the examination of various combinations is limited in accordance with previously determined information, to thereby render the process more efficient. By combining multiple, independently determined probabilities, the accuracy of the overall operation is enhanced.

Claims

1. A method for classifying an image containing a sequence of patterns, said method comprising the steps of:

segmenting the image into a plurality of pieces of arbitrary size;

forming a plurality of different pattern sequences, wherein each of the plurality of pattern sequences comprises a sequence of runes, and wherein each rune comprises a select subset of the plurality of pieces;

determining a plurality of different probabilities for each of the plurality of pattern sequences, wherein each of the plurality of probabilities represents a different type of probability; and

combining the plurality of different probabilities for each of the pattern sequences, thereby generating a composite probability for each pattern sequence, wherein a composite probability reflects a likelihood that the corresponding pattern sequence represents a correct classification of the image.

2. The method of claim 1 wherein one of said plurality of different probabilities is a segmentation probability which indicates a likelihood that the steps of segmenting and forming for a given pattern sequence were performed correctly.

3. The method of claim 2, wherein said segmentation probability is retrieved from one of a plurality of segmentation probability tables, a choice of tables being determined based upon a manner in which said pattern sequence is formed.

4. The method of claim 2 wherein another one of said plurality of different probabilities is a visual recognition probability which indicates a likelihood that a portion of the image within the pattern sequence is classified in a particular pattern class from a set of pattern classes.

5. The method of claim 2 wherein another one of said plurality of different probabilities is a contextual probability which indicates a likelihood that individual patterns in the pattern sequence are properly arranged with respect to at least one other pattern in the pattern sequence.

6. The method of claim 1 further including the steps of:

analyzing the image multiple times using different respective combinations of said plurality of different probabilities to generate multiple possible choices for a pattern represented by the image; and

processing the probabilities associated with each of said choices in a neural network to select one of said choices.

7. A method for classifying an image of a word, comprising the steps of:

dividing the image into a plurality of segments of arbitrary size;

combining the segments to form a plurality of different pattern sequences, wherein each pattern sequence contains a string of possible characters, and wherein different pattern sequences contain a different number of possible characters;

determining a probability for each character in a given string of possible characters, and multiplying the probabilities for each character in the string to determine a composite probability for the corresponding pattern sequence;

adjusting the composite probability by a normalization factor that is related to the number of characters in the string; and

selecting one of the pattern sequences on the basis of its adjusted composite probability.

8. A method for classifying an image of a word comprising the steps of:

dividing the image into a plurality of sufficiently small segments, wherein no one segment overlaps more than a recognizable pixel pattern;

combining the plurality of segments to form a plurality of possible character sequences, wherein different character sequences have a different number of characters;

selecting a number of character sequences from amongst said plurality of possible character sequences, based on the contextual probability associated with less than all of the characters in each of the plurality of possible character sequences; and

determining a classification probability value for each of the selected character sequences using dynamic programming techniques, wherein the character sequences are selected on the basis of a limited number of characters in the character sequence.

9. The method of claim 8 wherein said step of selecting a number of character sequences from amongst said plurality of possible character sequences comprises the step of:

determining a contextual probability value associated with the last two characters in each of said possible character sequences.

10. A method for classifying an image comprised of a plurality of features, said method comprising the steps of:

segmenting the image into a plurality of pieces of arbitrary size;

combining said pieces into a plurality of pattern sequences, each representing a different combination of the pieces;

determining a segmentation probability for each pattern sequence, wherein said segmentation probability represents a likelihood that the image has been correctly segmented and the pieces have been correctly combined; and

determining a most likely pattern sequence based upon said segmentation probability.