Object recognition system

• US 5,125,039 A
• Filed: 06/16/1989
• Issued: 06/23/1992
• Est. Priority Date: 06/16/1989
• Status: Expired due to Term

• Current Assignee: Palmsource Incorporated (Access Company Limited)
• Original Assignee: Jeffrey C. Hawkins
• Inventors: Hawkins, Jeffrey C.
• Primary Examiner(s): Razavi, Michael
• Assistant Examiner(s): Jung, Yon
• Application Number:
  US07/367,153
• Time in Patent Office: 1,103 Days
• Field of Search: 382/30, 382/55, 382/18, 382/24, 382/14, 382/34, 382/16
• US Class Current: 382/161
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 40/157 using dictionaries or tables

Abstract

An object recognition system that includes feature encoding and dictionary look-up procedures that are independent of any particular feature set. The procedures utilize only logical operations and require no multiplications. Only one dictionary entry per object is utilized.

Claims

1. A system for recognizing the identity of an unknown object comprising:

a collection of dictionary entry bit fields, one of said dictionary entries associated with a distinct object included in a predetermined set of objects, with each dictionary entry encoding which features in a set of features have ever occurred in any instance of the object associated with the dictionary entry;

means for forming a feature encoding bit field separately encoding which features in said set of features occurs in a given instance of the unknown object;

means for logically processing such dictionary entry and said feature encoding field to form a set of results, each result associated with a distinct object in said set of objects, with each result indicating which features in said set of features occurring in said given instance of the unknown object have never occurred in any instance of the object associated with said result; and

means for assigning the identity of a given object in said predetermined set of objects associated with a result that indicates that the number of features occurring in said given instance of said unknown object that have never occurred in any instance of said given object is less than the number of features occurring in said given instance of said unknown object that have never occurred in any instance of any other object included in said set of objects.

2. The system of claim 1 wherein:

each object in said set of objects is a character; and

said unknown object is a handwritten character.

3. A system for recognizing the identity of an a handwritten character comprising:

a set of dictionary entry bits, one of said dictionary entry bits associated with each character in a character set, with each dictionary entry bit encoding whether a selected feature has ever occurred in any instance of the character associated with the dictionary entry bit;

means for forming a feature encoding bit encoding whether said selected feature occurs in a given instance of the handwritten character;

means for logically processing each dictionary entry bit and said feature encoding bit to form a set of result bits, each result bit associated with a distinct character in said character set, with each result bit indicating whether said selected feature occurring in said handwritten character has never occurred in any instance of the character associated with said result; and

means for utilizing said result bits to assign the identity of a given character in said character set to said handwritten character.

4. The system of claim 3 wherein said means for logically processing comprises:

means for forming the logical product (AND) of said feature encoding bit and the logical complement (NOT) of said dictionary entry bit.

5. A system for recognizing the identity of an object comprising:

means for setting the state of a feature encoding bit indicating whether a given feature occurs in a given instance of a given object;

means for forming a dictionary entry bit equal to the logical sum of a set of feature encoding bits for a set of previously encountered instances of the given object and the feature encoding bit of the given instance of the object indicating whether the given feature has ever occurred in any encountered instance of the object

means for setting the state of a feature encoding bit indicating whether said given feature occurs in an instance of an unknown object; and

means for forming a result bit equal to the logical product of said feature encoding bit of the instance of the unknown object and the logical complement of said dictionary entry bit that indicates whether said given feature occurring in said instance of said unknown object has ever occurred in any previously encountered instance of the given object.

6. A system for recognizing the identity of an object comprising:

means for setting the state of a feature encoding bit indicating whether a given feature occurs in a given instance of an given object;

means for forming a feature encoding NOT bit equal to the logical complement of said feature encoding bit indicating whether said given feature has not occurred in said given instance;

means for forming a first dictionary entry bit equal to the logical sum of a set of feature encoding bits for a set of previously encountered instances of the given object and said feature encoding bit of said given instance of the object indicating whether the given feature has ever occurred in any encountered instance of the object; and

means for forming a second dictionary entry bit equal to the logical sum of a set of feature encoding NOT bits for a set of previously encountered instances of said given object and said NOT feature encoding bit of the given instance of the object indicating whether the given feature has never occurred in any encountered instance of the object.

7. The system of claim 6 further comprising:

means for setting the state of a feature encoding bit indicating whether said given feature occurs in an instance of an unknown object; and

means for forming a NOT result bit equal to the logical product of said NOT feature encoding bit of the instance of the unknown object and the logical complement of said NOT dictionary entry bit that indicates whether said given feature that does not occur in said instance of said unknown object has never occurred in any previously encountered instance of the given object.

8. A system for recognizing the identity of an unknown object comprising:

a collection of dictionary entry bit fields, one of said dictionary entries associated with a distinct object included in a predetermined set of objects, with each dictionary entry encoding which features in a set of features have ever occurred and which features in said set of features have never occurred in any instance of the object associated with the dictionary entry;

means for forming a feature encoding bit field separately encoding which features in said set of features occurs and which features in said set of features do not occur in a given instance of the unknown object;

means for logically processing each dictionary entry and said feature encoding field to form a set of results, each result associated with a distinct object in said set of objects, with each result indicating which features in said set of features occurring in said given instance of the unknown object have never occurred in any instance of the object associated with said result and indicating which features not occurring in said given instance of the unknown object have always occurred in any instance of the object associated with said result; and

means for assigning the identity of a given object in said set of objects associated with a result indicating the fewest number of occurrences and non-occurrences of features in the given instance of the unknown object that have never occurred or have always occurred, respectively, in all instances of the object associated with said result.

9. A method for recognizing the identity of an unknown object comprising:

providing a collection of dictionary entry bit fields, one of said dictionary entries associated with a distinct object included in a predetermined set of objects, with each dictionary entry encoding features in a set of features which have ever occurred in any instance of the object associated with the dictionary entry;

forming a feature encoding bit field separately encoding which features in said set of features occurs in a given instance of the unknown object;

logically processing each dictionary entry and said feature encoding field to form a set of results, each result associated with a distinct object in said set of objects, with each result indicating which features in said set of features occurring in said given instance of the unknown object have never occurred in any instance of the object associated with said result; and

assigning the identity of a given object in said predetermined set of objects associated with a result that indicates that the number of features occurring in said given instance of said unknown object that have never occurred in any instance of said given object is less than the number of features occurring in said given instance of said unknown object that have never occurred in any instance of any other object included in said set of objects.

10. The method of claim 9 wherein:

each object in said set of objects is a character; and

said unknown object is a handwritten character.

11. A method for recognizing the identity of an a handwritten character comprising:

providing a set of dictionary entry bits, one of said dictionary entry bits associated with each character in a character set, with each dictionary entry bit encoding whether a selected feature has ever occurred in any instance of the character associated with the dictionary entry bit;

forming a feature encoding bit encoding whether said selected feature occurs in a given instance of the handwritten character;

logically processing each dictionary entry bit and said feature encoding bit to form a set of result bits, each result bit associated with a distinct character in said character set, with each result bit indicating whether said selected feature occurring in said handwritten character has never occurred in any instance of the character associated with said result; and

utilizing said result bits to assign the identity of a given character in said character set to said handwritten character.

12. The method of claim 11 wherein said step of logically processing comprises the steps of:

forming the logical product (AND) of said feature encoding bit and the logical complement (NOT) of said dictionary entry bit.

13. A method for recognizing the identity of an object comprising:

setting the state of a feature encoding bit indicating whether a given feature occurs in a given instance of a given object;

forming a dictionary entry bit equal to the logical sum of a set of feature encoding bits for a set of previously encountered instances of the given object and the feature encoding bit of the given instance of the object indicating whether the given feature has ever occurred in any encountered instance of the object;

setting the state of a feature encoding bit indicating whether said given feature occurs in an instance of an unknown object; and

forming a result bit equal to the logical product of said feature encoding bit of the instance of the unknown object and the logical complement of said dictionary entry bit that indicates whether said given feature occurring in said instance of said unknown object has ever occurred in any previously encountered instance of the given object.

14. A system for recognizing the identity of an object comprising:

setting the state of a feature encoding bit indicating whether a given feature occurs in a given instance of an given object;

forming a feature encoding NOT bit equal to the logical complement of said feature encoding bit indicating whether said given feature has not occurred in said given instance;

forming a first dictionary entry bit equal to the logical sum of a set of feature encoding bits for a set of previously encountered instances of the given object and said feature encoding bit of said given instance of the object indicating whether the given feature has ever occurred in any encountered instance of the object; and

forming a second dictionary entry bit equal to the logical sum of a set of feature encoding NOT bits for a set of previously encountered instance of said given object and said NOT feature encoding bit of the given instance of the object indicating whether the given feature has never occurred in any encountered instance of the object.

15. The method of claim 14 further comprising:

setting the state of a feature encoding bit indicating whether said given feature occurs in an instance of an unknown object; and

forming a NOT result bit equal to the logical product of said NOT feature encoding bit of the instance of the unknown object and the logical complement of said NOT dictionary entry bit that indicates whether said given feature that does not occur in said instance of said unknown object has never occurred in any previously encountered instance of the given object.

16. A system for recognizing the identity of an unknown object comprising:

providing a collection of dictionary entry bit fields, one of said dictionary entries associated with a distinct object included in a predetermined set of objects, with each dictionary entry encoding which features in a set of features have ever occurred and which features in said set of features have never occurred in any instance of the object associated with the dictionary entry;

forming a feature encoding bit field separately encoding which features in said set of features occurs and which features in said set of features do not occur in a given instance of the unknown object;

logically processing each dictionary entry and said feature encoding field to form a set of results, each result associated with a distinct object in said set of objects, with each result indicating which features in said set of features occurring in said given instance of the unknown object have never occurred in any instance of the object associated with said result and indicating which features not occurring in said given instance of the unknown object have always occurred in any instance of the object associated with said result; and

assigning the identity of a given object in said set of objects associated with a result indicating the fewest number of occurrences and non-occurrences of features in the given instance of the unknown object that have never occurred or have always occurred, respectively, in all instances of the object associated with said result.