System and method for pattern recognition

• US 6,081,620 A
• Filed: 08/17/1999
• Issued: 06/27/2000
• Est. Priority Date: 02/11/1997
• Status: Expired due to Fees

• Current Assignee: Vitec, Inc.
• Original Assignee: Silicon Biology, Inc.
• Inventors: Anderholm, Eric J
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US09/376,771
• Time in Patent Office: 315 Days
• Field of Search: 382/181, 382/194, 382/192, 382/221, 382/224
• US Class Current: 382/194
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields

Abstract

A method for recognizing patterns comprising extracting features from a digital image, generating a numerical representation of each feature, indexing into a look-up table using the numerical representation to determine candidate pattern-types wherein the look-up table was generated by using a number of sample patterns to generate additional patterns based on relationships between the sample patterns; and selecting among the candidate pattern-types using selected contextual information. Extracting features from a digital image comprises identifying line segments in the digital image, grouping together adjacent line segments of the image that form features, storing the coordinates of the features to a file, the coordinates of the feature define a portion of the digital image containing the feature, dividing the portion of the digital image containing the feature into a number of cells, the number of cells is less than the number of pixels in each feature. Generating a numerical representation of each feature comprises generating a count of the number of pixels that are set in each cell, assigning a value to each cell based on whether the count for the cell exceeds a threshold, and indexing into a look-up table using the numerical representations to determine candidate pattern-types for the features wherein the look-up table was generated by using a number of sample patterns and at least one transformer that generates patterns by applying the transformer to the sample patterns; to select among the candidate pattern-types with selected validation modules that determine the pattern-type of each feature.

Claims

1. A method for recognizing patterns, the method comprising the steps of:

generating a digital image of one or more physical items;

identifying line segments in the digital image;

grouping together adjacent line segments of the image that form features;

storing the coordinates of the features to a file, the coordinates of the feature define a portion of the digital image containing the feature;

dividing the portion of the digital image containing the feature into a number of cells, wherein the number of cells is less than the number of pixels in each feature;

generating a count of the number of pixels that are set in each cell;

assigning a value to each cell based on whether the count for the cell exceeds a threshold;

indexing into a look-up table using the numerical representations to determine candidate pattern-types for the features wherein the look-up table was generated by using a number of sample patterns and at least one transformer that generates patterns by applying the transformer to the sample patterns; and

selecting among the candidate pattern-types with selected validation modules that determine the pattern-type of each feature.

2. The method of claim 1, and further comprising the step of modifying the file with the coordinates of the features when a validation module provides new coordinates for a feature.

3. The method of claim 1, wherein the step of selecting among candidate pattern-types includes the step of comparing confidence and noise values of the candidate pattern-types.

4. The method of claim 1, wherein the step of assigning a value comprises the step of assigning a binary 1 to a cell when the count for the cell exceeds the average count for the cells of the feature.

5. The method of claim 4, and further comprising the step of adjusting the number of cells contained within the portion of the digital image containing the feature to produce a second numerical representation to aid in selecting among the candidate pattern-types.

6. A computer-readable medium having computer-executable instructions for the method recited in claim 1.

7. A computer-readable medium having computer-executable instructions for the method recited in claim 5.

8. A computer data signal embodied in a carrier wave readable by a computing system and encoding a computer program of instructions for executing a computer process performing the method recited in claim 1.

9. A computer data signal embodied in a carrier wave readable by a computing system and encoding a computer program of instructions for executing a computer process performing the method recited in claim 5.

10. A method for generating computer-readable data from a document, the method comprising the steps of:

scanning the document to generate an electronic image of the document;

identifying regions of pixels of the electronic image in a hierarchical data structure;

identifying line segments in the regions of pixels;

grouping together adjacent line segments of the electronic image;

storing the coordinates of the features in a file, the coordinates of the feature define a portion of the digital image containing the feature;

dividing the portion of the digital image containing the feature into a number of cells, wherein the number of cells is less than the number of pixels in the feature;

counting the number of pixels that are set in each cell;

assigning a value to each cell based on whether the count for the cell exceeds a threshold;

applying the numerical representation to a classifier to identify candidate pattern-types for each feature, wherein the classifier was generated by using a number of sample patterns and at least one transformer that generates patterns by applying the transformer to the sample patterns;

selecting among the candidate pattern-types for each feature by applying validation modules at the different levels of the hierarchical data structure, the validation modules being selected based on the expected content of the document; and

generating an output file with the computer-readable data.

11. The method of claim 10, wherein the step of identifying regions comprises using a graphical user interface to mark-up a sample form to define the hierarchical data structure.

12. The method of claim 10, and further comprising the step of modifying the file with the coordinate of the features when a validation module provides new coordinates for a feature.

13. The method of claim 10, wherein the step of selecting among candidate pattern-types includes the step of comparing confidence and noise values of the candidate pattern-types to aid in selecting the appropriate pattern-type.

14. The method of claim 10, wherein the step of assigning a value comprises the step of assigning a binary 1 to a cell when the count for the cell exceeds the average count for the cells of the feature.

15. The method of claim 10, and further comprising the step of adjusting the number of cells to produce a second numerical representation to aid in selecting among the candidate pattern-types.

16. A computer-readable medium having computer-executable instructions for the method recited in claim 10.

17. A computer-readable medium having computer-executable instructions for the method recited in claim 15.

18. A computer data signal embodied in a carrier wave readable by a computing system and encoding a computer program of instructions for executing a computer process performing the method recited in claim 10.

19. A computer data signal embodied in a carrier wave readable by a computing system and encoding a computer program of instructions for executing a computer process performing the method recited in claim 15.