Pattern recognition method and apparatus

• US 4,805,225 A
• Filed: 11/06/1986
• Issued: 02/14/1989
• Est. Priority Date: 11/06/1986
• Status: Expired due to Fees

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Clark, David M.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/927,832
• Time in Patent Office: 831 Days
• Field of Search: 382/14, 382/15, 382/37, 382/38, 382/39
• US Class Current: 382/161
• CPC Class Codes: G06V 30/194 References adjustable by an adaptive method, e.g. learning
• CPC Class Codes: G10L 15/16 using artificial neural networks

Abstract

A general purpose pattern recognition method and apparatus comprises a hierarchical network of basic recognizers, each basic recognizer being capable of discriminating a particular feature at a lower level and providing outputs for higher levels of abstraction. In a learning mode, a series of sample patterns having a feature are presented as input along with several near-miss patterns. The pattern recognition apparatus learns to recognize the feature by keeping track of which basic recognizers detect patterns containing the feature. In a recognition mode, the invention determines if a presented pattern has the feature by polling the basic recognizers. A summation algorithm calculates the likelihood that the presented pattern has a particular feature.

Claims

1. A method of pattern learning, comprising the steps of:

(a) entering a pattern having a feature to be learned on a primary retina of a pattern recognition apparatus comprising a plurality of basic recognizers, each basic recognizer including a plurality of recognition elements;

(b) for each recognition element of each basic recognizer of said pattern recognition apparatus, if a learning cycle count is less than a learning constant and if the recognition element sees the pattern having the feature to be learned, incrementing by one a count of the number of patterns having the feature to be learned that have been seen by that recognition element;

(c) for each recognition element of each basic recognizer of said pattern recognition apparatus, if said learning cycle count is greater than or equal to said learning constant, reducing said count of the number of patterns having the feature to be learned that have been seen by that recognition element as a factor of the number by a forgetting constant consisting of a positive number less than 1;

(d) for each recognition element of each basic recognizer of said pattern recognition apparatus, if said learning cycle count is greater than or equal to said learning constant and if the recognition element sees the pattern having the feature to be learned, incrementing by one the count of the number of patterns having the feature to be learned that have been seen by that recognition element;

(e) for each basic recognizer, setting said learning cycle count equal to the lessor of said learning cycle count plus one or said learning constant; and

(f) for each basic recognizer of said pattern recognition apparatus, calculating an estimate of the average number of recognition elements that have seen a pattern having the feature to be learned.

2. A method of pattern learning and feature discrimination according to claim 1, wherein said estimate of the average number of recognition elements that have seen a pattern having the feature to be learned is calculated by the formula ##EQU7## where s is the estimate of the average number of recognition elements that see a pattern having the feature to be learned, x is a count of the total number of recognition elements in the basic recognizer, r_i is the count of the number of patterns having the feature to be learned that have been seen by that recognition element, and c is the learning cycle count.

3. A method of pattern learning and feature discrimination according to claim 1, feature comprising the steps of repeating (a) through (e) above for each additional pattern to be learned.

4. A method of pattern recognition, comprising the steps of:

(a) calculating an average likelihood of the presence of a feature for a plurality of patterns having the feature that have been entered on a primary retina of a pattern recognition apparatus having a plurality of basic recognizers, each basic recognizer including a plurality of recognition elements;

(b) entering a pattern to be tested on said primary retina;

(c) calculating a likelihood of the presence of the feature for said pattern to be tested;

(d) if said likelihood of the presence of the feature for the pattern to be tested approximates said average likelihood of the presence of the feature for plurality of patterns having the feature, outputting a response indicating the presence of the feature;

(e) if said likelihood that the pattern to be tested has the feature does not approximate said average likelihood for patterns having the feature, outputting a response indicating the absence of the feature; and

wherein said average likelihood of the presence of the feature for a plurality of patterns having the feature is calculated by the formula ##EQU8## wherein b is the average likelihood of the presence of the feature for a plurality patterns having the feature, c is a learning cycle count, s is an estimate of the average number of recognition elements that have seen a pattern having the feature, x is a count of the total number of recognition elements in the basic recognizer, and r_i is a count of the number of patterns having the feature that have been seen by that recognition element.

9. A method of pattern recognition according to claim 4, which further includes the step of calculating the quotient of said likelihood of the presence of the feature for the pattern to be tested divided by said average likelihood of the presence of the feature for a plurality of patterns having the feature.

5. A method of pattern recognition, comprising the steps of:

(a) calculating an average likelihood of the presence of a feature for a plurality of patterns having the feature that have been entered on a primary retina of a pattern recognition apparatus having a plurality of basic recognizers, each basic recognizer including a plurality of recognition elements;

(b) entering a pattern to be tested on said primary retina;

(c) calculating a likelihood of the presence of the feature for said pattern to be tested;

(d) if said likelihood of the presence of the feature for the pattern tobe tested approximates said average likelihood of the presence of the feature for plurality of patterns having the feature, outputting a response indicating the presence of the feature;

(e) if said likelihood that the pattern to be tested has the feature does not approximate said average likelihood for patterns having the feature, outputting a response indicating the absence of the feature; and

wherein said likelihood of the presence of the feature for the pattern to be tested is calculated by the formula ##EQU9## where b_q is the likelihood of the presence of the feature for the pattern q to be tested, c is a learning cycle count, s is an estimate of the average number of recognition elements that have seen a pattern having the feature, x is a count of the total number of recognition elements in the basic recognizer, r_i is a count of the number of patterns having the feature that have been seen by that recognition element, and f_i is a recognition flag for that recognition element.

6. A method of pattern recognition, comprising the steps of:

(a) calculating an average likelihood of the presence of a feature for a plurality of patterns having the feature that have been entered on a primary retina of a pattern recognition apparatus having a plurality of basic recognizers, each basic recognizer including a plurality of recognition elements;

(b) entering a pattern to be tested on said primary retina;

(c) calculating a likelihood of the presence of the feature for said pattern to be tested;

(d) if said likelihood of the presence of the feature for the pattern to be tested approximates said average likelihood of the presence of the feature for plurality of patterns having the feature, outputting a response indicating the presence of the feature;

(e) if said likelihood that the pattern to be tested has the feature does not approximate said average likelihood for patterns having the feature, outputting a response indicating the absence of the feature; and

wherein said average likelihood of the presence of the feature for a plurality of patterns having the feature is calculated by the formula ##EQU10## wherein b is the average likelihood of the presence of the feature for a plurality of patterns having the feature, c is a learning cycle count, s is an estimate of the average number of recognition elements that have seen a pattern having the feature, x is a count of the total number of recognition elements in the basic recognizer, and r_i is a count of the number of patterns having the feature seen by that recognition element.

7. A method of pattern recognition, comprising the steps of:

(a) calculating an average likelihood of the presence of a feature for a plurality of patterns having the feature that have been entered on a primary retina of a pattern recognition apparatus having a plurality of basic recognizers, each basic recognizer including a plurality of recognition elements;

(b) entering a pattern to be tested on said primary retina;

(c) calculating a likelihood of the presence of the feature for said pattern to be tested;

(d) if said likelihood of the presence of the feature for the pattern to be tested approximates said average likelihood of the presence of the feature for plurality of patterns having the feature, outputting a response indicating the presence of the feature;

(e) if said likelihood that the pattern to be tested has the feature does not approximate said average likelihood for patterns having the feature, outputting a response indicating the absence of the feature; and

wherein said average likelihood of the presence of the feature for a plurality of patterns having the feature is calculated by the formula ##EQU11## where b is the average likelihood of the presence of the feature for a plurality of patterns having a feature F, |F| is a count of the total number of patterns having the feature F, e(p,q) is the number of individual bits on which the pattern q to be tested and pattern p having a feature be learned have the same input on the primary retina, m is the number of input connectors per recognition element, and n is the number of individual bits on said primary retina.

8. A method of pattern recognition, comprising the steps of:

(a) calculating an average likelihood of the presence of a feature for a plurality of patterns having the feature that have been entered on a primary retina of a pattern recognition apparatus having a plurality of basic recognizers, each basic recognizer including a plurality of recognition elements;

(b) entering a pattern to be tested on said primary retina;

(c) calculating a likelihood of the presence of the feature for said pattern to be tested;

(d) if said likelihood of the presence of the feature for the pattern to be tested approximates said average likelihood of the presence of the feature for plurality of patterns having the feature, outputting a response indicating the presence of the feature; and

(e) if said likelihood that the pattern to be tested has the feature does not approximate said average likelihood for patterns having the feature, outputting a response indicating the absence of the feature; and

wherein said likelihood of the presence of the feature for the pattern to be tested is calculated by the formula ##EQU12## where b_q is the likelihood of the presence of a feature F for the pattern q to be tested, |F| is a count of the total number of patterns having the feature F, e(p,q) is a count of the number of individual bits on which pattern p having a feature to be learned and pattern q to be tested have the same inputs on the primary retina, m is a count of the number of input connectors per recognition element, and n is a count of the number of individual bits on the primary retina.

10. A method of pattern learning, comprising the steps of:

(a) entering a pattern having a feature to be learned on a primary retina of a pattern recognition apparatus comprising a plurality of basic recognizers, each basic recognizer including a plurality of recognition elements;

(b) for each recognition element of each basic recognizer of said pattern recognition apparatus, calculating an average number of patterns having a feature to be learned that can be seen by a recognition element;

(c) for each basic recognizer of said pattern recognition apparatus, setting a learning cycle count equal to the lessor of said learning cycle count plus one or a learning constant equal to the largest number that the recognition elements of said basic recognizer can represent;

(d) for each basic recognizer of said pattern recognition apparatus, calculating an estimate of the average number of recognition elements that have seen a pattern having the feature to be learned.

11. A method of pattern learning according to claim 10, wherein said average number of patterns having a feature to be learned that can be seen by the recognition element is calculated by the formula

12. A method of pattern learning according to claim 10, wherein said estimate of the average number of recognition elements that have seen a pattern having the feature to be learned is calculated by the formula ##EQU13## where s is an estimate of the average number of recognition elements that see a pattern having the feature to be learned, x is a count of the total number of recognition elements in the basic recognizer, W_i is a count of the total number of patterns having the feature to be learned that can be seen by the recognition element, and |F| is a count of the total number of patterns having the feature to be learned.

13. A method of pattern recognition, comprising the steps of:

(a) entering a pattern having a feature to be learned on a primary retina of a pattern recognition apparatus comprising a plurality of basic recognizers, each basic recognizer including a plurality of recognition elements; and

(b) for each basic recognizer of said pattern recognition apparatus, calculating an estimate of the average number of recognition elements that have seen a pattern having the feature to be learned; and

wherein said estimate of the average number of recognition elements that have seen a pattern having the feature to be learned is calculated by the formula ##EQU14## where s is an estimate of the average number of recognition elements that have seen a pattern having a feature to be learned, x is a count of the total number of recognition elements in the basic recognizer, r_i is a count of the number of patterns having the feature to be learned that have been seen by the recognition element, and c is a learning cycle count.

14. A method of pattern learning, comprising the steps of:

(a) entering a pattern having a feature to be learned on a primary retina of a pattern recognition apparatus comprising a plurality of basic recognizers, each basic recognizer including a plurality of recognition elements;

(b) for each recognition element of each basic recognizer of said pattern recognition apparatus, if the recognition element sees the pattern having the feature to be learned setting a count of the number of patterns having the feature to be learned that have been seen by the recognition element equal to one; and

(c) for each basic recognizer of said pattern recognition apparatus, calculating an estimate of the average number of recognition elements that have seen a pattern having the feature to be learned.

15. A method of pattern learning according to claim 14, wherein said estimate of the average number of recognition elements that have seen a pattern having the feature to be learned is calculated by the formula ##EQU15## where s is the estimate of the average number of recognition elements that have seen a pattern having the feature to be learned, x is a count of the total number of recognition elements in the basic recognizer, r_i is a count of the number of patterns having the feature that have been seen by that recognition element, and c is a learning cycle count.

16. A method of pattern learning discrimination according to claim 14, further comprising the steps of repeating (a) through (b) above for each additional pattern to be learned.