Recognition system and method for user inputs to a computer system

• US 5,463,696 A
• Filed: 07/05/1994
• Issued: 10/31/1995
• Est. Priority Date: 05/27/1992
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Pagallo, Giulia, Beernink, Ernest H., Bozinovic, Radmilo
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/270,405
• Time in Patent Office: 483 Days
• Field of Search: 382/9, 382/10, 382/13, 382/22, 382/25, 382/30, 382/34, 382/48
• US Class Current: 382/186
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

A technique for analyzing and interpreting user inputs to a computer, such as strokes, key depressions, or voice signals to a hand-held, pen-based computer system. Inputs to the system are received at a user interface, such as a dual function display/input screen from users in the form of pen strokes or gestures. A database stores the input data strokes and hypotheses regarding possible interpretations of the strokes. Recognition of the input strokes and recognition of higher level combinations of strokes (forming characters and words, etc.) is performed using recognizers, or recognition domains, each of which performs a particular recognition task. A controller is provided for controlling the hypotheses database and for scheduling the recognition tasks in the recognition domains. Arbitration resolves conflicts among competing hypotheses associated with each interpretation. The recognition domains, or recognizers generate two or more competing interpretations for the same input. The recognizers use a data structure called a unit, where a unit is a set of subhypotheses together with all their interpretations generated by a single recognizer. A recognizer operates at a first level for identifying one or more groups of related subhypotheses using grouping knowledge. These grouped subhypotheses generate a unit with no interpretations for each group and store the unit in the database in what is called a piece-pool memory. A recognizer has a second level of operation where each unit generated in the grouping stage is classified to provide the unit with one or more interpretations. The classified unit are stored in a unit pool memory. Two or more interpretations of the input data are combined in a hierarchical structure according to a predetermined scheme in successive steps to form higher level interpretations.

Claims

1. A system for recognizing user input to a computer from a user input device, comprising:

input means for receiving user input data in the form of a signal from a user input device chosen from the group consisting essentially of a tablet input device and a voice input device;

means for storing said user input data in memory of said computer system;

a hierarchy of independent recognition domains, each of said hierarchy of independent recognition domains comprising group means and classify means, including;

a first recognition domain for receiving a portion of said user input data as a first recognition domain input and performing character-related recognition on the user input data only if the user input data is of the type expected in a screen recognition area and generating one or more active character-related hypotheses, each of said active character-related hypotheses comprising a portion of said user input data together with a character-related interpretation of said user input data;

a second recognition domain for receiving at least one of said active character-related hypotheses as a second recognition domain input and performing word-related recognition on the user input data only if the user input data is of the type expected in said screen recognition area and generating one or more active word-related hypotheses, at least one of said active word-related hypotheses being derived from said one of said active character-related hypotheses;

a third recognition domain for receiving a portion of said user input data as a third recognition domain input and performing shape part recognition on the user input data only if the user input data is of the type expected in said screen recognition area and generating one or more active shape-pan-related hypotheses, each of said shape-part-related hypotheses comprising a portion of said user input data together with a shape-part-related interpretation of said user input data; and

a fourth recognition domain for receiving at least one of said active shape-part-related hypotheses as a fourth recognition domain input and performing shape recognition on the user input data only if the user input data is of the type expected in said screen recognition area and generating one or more active shape-related hypotheses, at least one of said active shape-related hypotheses being derived from said one of said active shape-part-related hypotheses;

means for storing said active hypotheses in a database comprising a piece pool and a unit pool in said memory of said computer system;

a control unit including;

first control means for managing the means for storing active hypotheses, said first control means further including means for removing a previously stored hypothesis from said database, said means for removing further removes a hierarchy of hypotheses from which said previously stored hypothesis is derived, down to constituent strokes as well all other hypotheses in said database that refer to said constituent strokes; and

second control means for scheduling the recognition tasks in said recognition domains;

arbiter means for resolving multiple active hypotheses from said recognition domains and choosing a recognition result among said multiple active hypotheses from said recognition domains; and

a user output device for communicating to said user said recognition result.

2. The system of claim 1 wherein said group means groups domain inputs into groups, said classify means generates one or more hypotheses from said groups and being a lower priority task than said group means, said classify means being activated after a settable delay time period following a completion of a grouping task by said group means.

3. The system of claim 2 wherein said group means includes:

means for identifying one or more groups of related domain inputs using domain grouping knowledge;

means for generating a unit with no hypothesis for each group and storing said unit in the database; and

means for storing units with no hypothesis in said piece-pool; and

wherein said classify means includes;

means for receiving each unit generated by the grouping means and providing a unit with a hypothesis; and

means for storing units with one or more hypothesis in said unit pool.

4. The system of claim 2 wherein said second recognition domain further comprises means for combining at least two interpretations from said one or more active character-related hypotheses to form a higher level interpretation for one of said active word-related hypotheses.

5. The system of claim 4 wherein said hierarchy of independent recognition domains comprises multiple, independent recognition domains organized into a hierarchical structure based upon hierarchy information, said hierarchy information comprises information about domain inputs and information about which type of hypothesis the domain generates so that the type of input hypotheses for a domain establishes its position in said hierarchical structure.

6. The system of claim 5 wherein each of said hierarchy of independent recognition domains further comprises means for preventing hypothesis proliferation, said means for preventing hypothesis proliferation keeps the number of hypotheses a recognition domain proposes under a given limit.