System and method for pattern recognition

• US 6,021,220 A
• Filed: 02/11/1997
• Issued: 02/01/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:
  US08/798,938
• Time in Patent Office: 1,085 Days
• Field of Search: 382/194, 382/190, 382/195, 382/198, 382/243, 382/212, 382/149, 382/228, 382/224, 380/30
• 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 and system includes a method for generating a classifier from a set of collected sample patterns for use in pattern recognition. The sample patterns are representative of data to be processed by the classifier and are converted to electronic signals to be manipulated by a programmed computer. Further, the method and system generate and identify a number of transformers that map between sample patterns of the same pattern-type in the collected sample patterns. The method and system use the transformers and the sample patterns to generate additional patterns. The method and system then forms a table that contains the generated patterns and an indication of the pattern-type to which each pattern belongs. The process repeats the steps of generating additional patterns and forming a table until a measure accuracy for the mapping of the sample patterns and transformers do not provide an acceptable improvement.

Claims

1. The method for generating a classifier, comprising the steps of:

collecting sample patterns that are representative of data to be processed by the classifier;

generating sample pattern signals that represent the sample patterns for processing;

generating a number of transformers;

identifying the transformers that map between sample patterns of the same pattern-type in the collected sample patterns;

generating additional patterns with the identified transformers and the sample pattern signals;

forming a table that contains the generated patterns and an indication of the pattern-type to which each pattern belongs;

testing the table of the classifier with some of the collected sample patterns to measure the accuracy of the classifier; and

repeating the steps of generating additional patterns and forming a table until the measure accuracy does not provide an acceptable improvement.

2. The method of claim 1, wherein steps in determining when the measured accuracy does not provide an acceptable improvement comprise:

determining if the transformers correctly map sample patterns and same pattern-types;

discarding transformers which incorrectly map sample patterns to same pattern-types; and

determining a statistical measure for the transformer and recording the statistical measure in a fitness matrix.

3. The method of claim 1, and further comprising the step of re-seeding the sample patterns used to identify the transformers when the measure of the accuracy does not improve and the size of the classifier is not acceptable.

4. The method of claim 1, wherein the step of identifying the transformers that map between sample patterns of the same pattern-type comprises the steps of generating and testing transformers using a genetic algorithm.

5. The method of claim 4, wherein the step of using a genetic algorithm comprises the step of applying a point mutation to a transformer.

6. The method of claim 4, wherein the step of using a generic algorithm comprises the step of applying a cross over algorithm to at least two transformers.

7. The method of claim 4, wherein the step of using a generic algorithm (58) comprises the step of applying an aging algorithm to a transformer.

8. The method of claim 1, wherein the step of generating additional patterns comprises the step of applying the identified transformers to the sample patterns.

9. The apparatus for generating a classifier, comprising:

means for collecting sample patterns that are representative of data to be processed by the classifier;

means for generating sample pattern signals that represent the sample patterns for processing;

means for generating a number of transformers;

means for identifying the transformers that map between sample patterns of the same pattern-type in the collected sample patterns;

means for generating additional patterns with the identified transformers and the sample pattern signals;

means for forming a table that contains the generated patterns and an indication of the pattern-type to which each pattern belongs;

means for testing the table of the classifier with some of the collected sample patterns to measure the accuracy of the classifier; and

means for repeating the generation of additional patterns and forming a table until the measure accuracy does not provide an acceptable improvement.

10. The apparatus of claim 9, wherein means for determining when the measured accuracy does not provide an acceptable improvement comprise:

means for determining if the transformers correctly map sample patterns and same pattern-types;

means for discarding transformers which incorrectly map sample patterns to same pattern-types; and

means for determining a statistical measure for the transformer and recording the statistical measure in a fitness matrix.

11. The apparatus of claim 9, and further comprising a means for re-seeding the sample patterns used to identify the transformers when the measure of the accuracy does not improve and the size of the classifier is not acceptable.

12. The apparatus of claim 9, wherein the means for identifying the transformers that map between sample patterns of the same pattern-type comprises a means for generating and testing transformers using a genetic algorithm.

13. The apparatus of claim 12, wherein the means for using a genetic algorithm comprises a means for applying a point mutation to a transformer.

14. The apparatus of claim 12, wherein the means for using a generic algorithm comprises a means for applying a cross over algorithm to at least two transformers.

15. The apparatus of claim 12, wherein the step of using a generic algorithm comprises a means for applying an aging algorithm to a transformer.

16. The apparatus of claim 9, wherein the means for generating additional patterns comprises a means for applying the identified transformers to the sample patterns.