System and method for word recognition using size and placement models

• US 5,675,665 A
• Filed: 09/30/1994
• Issued: 10/07/1997
• Est. Priority Date: 09/30/1994
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.)
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Lyon, Richard F.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/315,886
• Time in Patent Office: 1,103 Days
• Field of Search: 382/159, 382/177, 382/184, 382/185, 382/187, 382/195, 382/199, 382/200, 382/203, 382/229, 382/230
• US Class Current: 382/229
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/146 Aligning or centring of the image pick-up or image-field
• CPC Class Codes: G06V 30/244 using graphical properties, e.g. alphabet type or font
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

A bounds evaluation unit generates a bounds measurement pair corresponding to a character pattern pair determined from a handwritten word. Within the bounds measurement pair, a first bounds measurement corresponds to a first character pattern, and a second bounds measurement corresponds to a second character pattern. The first and second bounds measurements are each a bounding box that defines a left-most, a right-most, a top-most, and a bottom-most extent of the corresponding character pattern. The bounds measurement pair is compared against one or more bounds model pairs, where each bounds model pair corresponds to a hypothesized character identifier pair in which each individual hypothesized character identifier has been determined by a character recognition unit. Each bounds model pair indicates the expected size and position of a character pattern pair corresponding to the hypothesized character identifier pair. Bounds model pairs are trained based upon size and positional relationships between character pattern pairs within handwritten training words. The comparison of the bounds measurement pair against a given bounds model pair produces a set of error values. The error values are used in conjunction with an error covariance matrix that has also been trained with handwritten training words to determine a pairwise cost value associated with the hypothesized character identifier pair. A word recognition unit incorporates individual character cost values and each pairwise cost value in a conventional minimum-cost path search method to determine the identity of the handwritten word.

Claims

1. A method for word recognition using size and placement models comprising the steps of:

generating a first bounds measurement from a first character pattern within a word;

generating a second bounds measurement from a second character pattern within the word, the first bounds measurement and the second bounds measurement forming a bounds measurement pair;

selecting a hypothesized character identifier associated with the first character pattern;

selecting a hypothesized character identifier associated with the second character pattern;

generating a bounds model pair corresponding to the hypothesized character identifier associated with the first character pattern and the hypothesized character identifier associated with the second character pattern; and

generating a pairwise cost value indicating a size and a placement difference between the bounds measurement pair and the bounds model pair, the pairwise cost value being substantially independent of a size or a position of any additional character pattern within the word.

2. A method for word recognition using size and placement models comprising the steps of:

selecting a hypothesized character identifier associated with a first character pattern within a word;

selecting a hypothesized character identifier associated with a second character pattern within the word;

generating a bounds model pair corresponding to the hypothesized character identifier associated with the first character pattern and the hypothesized character identifier associated with the second character pattern;

generating a first bounds measurement from the first character pattern;

generating a second bounds measurement from the second character pattern, the first bounds measurement and the second bounds measurement forming a bounds measurement pair; and

generating a pairwise similarity measure indicating a difference in size and placement between the bounds measurement pair and the bounds model pair, the pairwise similarity measure being substantially independent of a size or a position of any character pattern within the word other than the first and second character patterns.

3. The method of claim 2, wherein the step of generating a pairwise similarity measure comprises the step of scaling the bounds measurement pair relative to the bounds model pair.

4. The method of claim 2, wherein the step of generating the bounds model pair comprises the steps of:

retrieving a first bounds model defining an expected character pattern size and position corresponding to the hypothesized character identifier associated with the first character pattern; and

retrieving a second bounds model defining an expected character pattern size corresponding to the hypothesized character identifier associated with the second character pattern.

5. The method of claim 4, further comprising the step of positioning the first and second bounds models according to a spacing value.

6. The method of claim 4, wherein the step of generating a pairwise similarity measure comprises the step of generating a set of error values indicating a size and a placement difference between the first bounds model and the first bounds measurement, and a size and a placement difference between the second bounds model and the second bounds measurement.

7. The method of claim 6, wherein the step of generating a pairwise similarity measure further comprises the step of multiplying the set of error values by an error covariance matrix.

8. A means for word recognition using size and placement models comprising:

means for selecting a hypothesized character identifier associated with a first character pattern within a word;

means for selecting a hypothesized character identifier associated with a second character pattern within the word;

means for generating a bounds model pair corresponding to the hypothesized character identifier associated with the first character pattern and the hypothesized character identifier associated with the second character pattern;

means for generating a first bounds measurement from a first character pattern within a word;

means for generating a second bounds measurement from a second character pattern within the word, the first bounds measurement and the second bounds measurement forming a bounds measurement pair; and

means for generating a pairwise similarity measure indicating a difference in size and placement between the bounds measurement pair and the bounds model pair, the pairwise similarity measure being substantially independent of a size or a position of any character pattern within the word other than the first and second character patterns.

9. The means for word recognition using size and placement models of claim 8, wherein the means for generating a pairwise similarity measure comprises a means for scaling the bounds measurement pair relative to the bounds model pair.

10. The means for word recognition using size and placement models of claim 8, wherein the means for generating a bounds model pair comprises:

means for retrieving a first bounds model defining an expected character pattern size and position corresponding to the hypothesized character identifier associated with the first character pattern; and

means for retrieving a second bounds model defining an expected character pattern size corresponding to the hypothesized character identifier associated with the second character pattern.

11. The means for word recognition using size and placement models of claim 10, wherein the means for generating a bounds model pair further comprises a means for positioning the first and second bounds models according to a spacing value.

12. The means for word recognition using size and placement models of claim 10, wherein the means for generating a pairwise similarity measure comprises a means for generating a set of error values indicating a size and a placement difference between the first bounds model and the first bounds measurement, and a size and a placement difference between the second bounds model and the second bounds measurement.

13. The means for word recognition using size and placement models of claim 12, wherein the means for generating a pairwise similarity measure further comprises a means for multiplying the set of error values by an error covariance matrix.

14. A system for word recognition using size and placement models comprising:

a bounds evaluation unit having an output for comparing a bounds measurement pair with a bounds model pair and for generating a corresponding comparison result independent of a word baseline estimation, the bounds measurement pair characterizing a relative size and position of a pair of adjacent handwritten characters, the bounds model pair characterizing an expected relative size and position of a pair of hypothesized characters;

a word recognition unit having an input, for generating a word recognition result using a comparison result generated by the bounds evaluation unit, the input of the word recognition unit coupled to the output of the bounds evaluation unit, and

a character recognition unit having an output, for generating a set of hypothesized character identifiers corresponding to a character pattern, the output of the character recognition unit coupled to the input of the word recognition unit.