Method and apparatus for automated text recognition

• US 5,644,656 A
• Filed: 06/07/1994
• Issued: 07/01/1997
• Est. Priority Date: 06/07/1994
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Akra, Mohamad A., Mitter, Sanjoy K.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/254,938
• Time in Patent Office: 1,120 Days
• Field of Search: 382/194, 382/195, 382/198, 382/199, 382/200, 382/203, 382/205, 382/206, 382/209, 382/215-219, 382/249, 382/221
• US Class Current: 382/215
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

A method, and related apparatus, for recognizing alphanumeric characters within a sample includes applying ideal alphanumeric character templates to the sample to identify each template which is included substantially within the sample. A template will be considered to be included substantially within the sample even if the sample has portions thereof with which the template does not substantially correspond or substantially match. That is, a template can be considered to be included substantially within the sample even if the template and the sample do not have a substantially one-to-one symmetrical correspondence. Of all of the templates which are identified as included substantially within the sample, the template having the most information (e.g., the template which requires the largest number of data points to define its shape) is selected as a recognized version of the sample.

Claims

1. Apparatus for recognizing alphanumeric characters within a sample, comprising:

(A) a data storage device for storing a plurality of first sets of data, each of the first sets of data is representative of a different alphanumeric character template and includes a plurality of data points which together define the shape of the template;

(B) a template applicator for;

receiving a second set of data which is representative of a sample to be recognized and which includes a plurality of data points which together define the shape of the sample,

accessing the first sets of data and applying each of the first sets of data to the second set of data according to a single-sided Hausdorff function to identify each template shape which is included substantially within the sample shape regardless of whether the sample shape has other portions thereof within which the template shape is not substantially included and thus regardless of whether the sample shape and the template shape have a substantially one-to-one symmetrical correspondence, and

outputting a plurality of third sets of data, each of the third sets of data is representative of at least one of the template shapes identified as included substantially within the sample shape; and

(C) a template selector for;

receiving the third sets of data,

manipulating the third sets of data to determine which third set of data represents the template shape or shapes having the largest number of data points and designating that third set of data as representative of a recognized version of the sample, and

outputting a fourth set of data which is representative of the recognized version of the sample.

2. The apparatus of claim 1 wherein the template applicator includes a template deformer for manipulating at least one of the first sets of data to deform the template represented thereby before that first set of data is applied to the second set of data.

3. The apparatus of claim 2 wherein the template deformer manipulates the first set of data to scale the size of the template.

4. The apparatus of claim 2 wherein the template deformer manipulates the first set of data to slant the template.

5. The apparatus of claim 2 wherein the template deformer manipulates the first set of data to rotate the template.

6. The apparatus of claim 2 wherein the template deformer manipulates the first set of data to deform the template by premultiplying the first set of data with a fifth set of data representative of a matrix.

7. The apparatus of claim 2 wherein the template applicator identifies template shapes included substantially within the sample shape by applying the single-sided Hausdorff function to each of the deformed templates and the undeformed sample.

8. The apparatus of claim 1 wherein the second set of data is representative of at least one handwritten alphanumeric character to be recognized.

9. The apparatus of claim 1 wherein the second set of data is representative of at least one machine-printed alphanumeric character to be recognized.

10. A method for recognizing alphanumeric characters within a sample, comprising:

(A) receiving a first set of data which is representative of a sample to be recognized and which includes a plurality of data points which together define the shape of the sample;

(B) accessing a plurality of second sets of data, each of the second sets of data is representative of a different alphanumeric character template and includes a plurality of data points which together define the shape of the template;

(C) applying each of the second sets of data to the first set of data according to a single-sided Hausdorff function to identify each template shape which is included substantially within the sample shape regardless of whether the sample shape has other portions thereof within which the template shape is not substantially included and thus regardless of whether the sample shape and the template shape have a substantially one-to-one symmetrical correspondence;

(D) providing a plurality of third sets of data, each of the third sets of data is representative of at least one of the template shapes identified as included substantially within the sample shape;

(E) manipulating the third sets of data to determine which third set of data represents the template shape or shapes having the largest number of data points and designating that third set of data as representative of a recognized version of the sample; and

(F) outputting a fourth set of data which is representative of the recognized version of the sample.

11. The method of claim 10 further comprising, prior to step (C), manipulating at least one of the second sets of data to deform the template represented thereby before that second set of data is applied to the first set of data.

12. The method of claim 11 wherein the step of manipulating to deform includes manipulating the second set of data to scale the size of the template represented thereby.

13. The method of claim 11 wherein the step of manipulating to deform includes manipulating the second set of data to slant the template represented thereby.

14. The method of claim 11 wherein the step of manipulating to deform includes manipulating the second set of data to rotate the template represented thereby.

15. The method of claim 11 wherein the step of manipulating to deform includes manipulating the second set of data to deform the template represented thereby by premultiplying the second set of data with a fifth set of data representative of a matrix.

16. The method of claim 14 wherein step (C) comprises identifying template shapes included substantially within the sample shape by applying the single-sided Hausdorff function to each of the deformed templates and the undeformed sample.

17. The method of claim 10 wherein step (A) comprises receiving the first set of data which is representative of at least one handwritten alphanumeric character to be recognized.

18. The method of claim 10 wherein step (A) comprises receiving the first set of data which is representative of at least one machine-printed alphanumeric character to be recognized.