Method and apparatus for processing graphically input equations

• US 5,544,262 A
• Filed: 01/05/1993
• Issued: 08/06/1996
• Est. Priority Date: 04/07/1992
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.)
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Pagallo, Giulia
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US08/000,932
• Time in Patent Office: 1,309 Days
• Field of Search: 382/13, 382/1, 382/69, 382/187, 382/189, 382/186, 395/161, 364/735, 364/736, 364/709.01, 364/705.03
• US Class Current: 382/189
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: G06V 30/274 Syntactic or semantic context, e.g. balancing
• CPC Class Codes: G06V 30/32 Digital ink

Abstract

A method for processing equations in a graphical computer system characterized by the steps of: receiving at least one unit comprising an equation which was derived from a graphical user input device; parsing the units into a parsed tree utilizing a constrained attribute grammar; and deriving a result of the equation utilizing the parsed tree. Preferably, the graphical user input device is a table or the screen of a pen-based computer system, where stroke units derived from strokes made by a stylus on the screen are passed to at least one recognition domain. The process preferably also includes the steps of: receiving at least one stroke unit comprising an edit to an equation on the screen; determining whether the edit changes the structure of the parsed tree of the equation; and editing the parsed tree if the edit does not change the structure of the parsed tree. A system for processing equations is characterized by: a digital processor; a screen assembly coupled to the digital processor for displaying images in response to signals provided by the digital processor and for transmitting signals to the digital processor in response to stroke made on the screen assembly with a stylus; an equation recognizer responsive to the stroke signals and operative to detect valid equations formed on the screen; an equation solver operative to produce a result for valid equations; and a mechanism for displaying the result on the screen assembly proximate to the equation.

Claims

1. A method for processing handwritten equations on a computer system comprising the steps of:

receiving an input pattern comprising an equation which was derived from user handwritten strokes on a graphical user input device;

parsing said input pattern utilizing a defined constrained attribute grammar to determine if said input pattern defines a valid pattern within said constrained attribute grammar, said valid pattern including a set of subpatterns satisfying constraints of production rules included in said constrained attribute grammar, said constraints being used by said parsing step to establish correspondence between said subpatterns and said production rules, said constraints including keywords to be identified within said subpatterns;

providing a parsed tree from said step of parsing said input pattern when said input pattern is determined to be a valid pattern in said parsing step;

deriving and displaying said equation and a result of said equation utilizing said parsed tree by executing an operator at nodes of said parsed tree using operands included in said parsed tree, wherein said receiving, parsing, providing, and deriving steps are performed on said computer system;

detecting an edit made to said displayed equation having said result; and

editing said parsed tree associated with said equation in response to said edit made to said displayed equation and without changing a structure of said parsed tree when said edit changes only a value or an operator of said equation.

2. A method as recited in claim 1 wherein said graphical user input device comprises a tablet means.

3. A method as recited in claim 2 wherein said tablet means comprises a touch sensitive screen assembly.

4. A method as recited in claim 3 further comprising the step of displaying said result on said screen assembly.

5. A method as recited in claim 1 wherein said input pattern includes a plurality of stroke units which were derived from said user input strokes on said graphical user input device.

6. A method as recited in claim 1 wherein said step of parsing said input pattern comprises:

a) identifying a subpattern of said input pattern that can be rewritten as a nonterminal symbol of a grammar of a predefined language;

b) rewriting said subpattern as said nonterminal symbol; and

c) determining if one of said production rules of said grammar exists where a start symbol of said grammar produces said nonterminal symbol, wherein said production rule includes a syntactic part, a semantic part, a constraints part including said constraints, and an action part.

7. A method as recited in claim 6 wherein said nonterminal symbol comprises at least one of said keywords and identifiers, and wherein said step of identifying a subpattern further comprises the steps of:

a) determining that a subpattern in said pattern matches one of said keywords;

b) identifying one of said production rules that corresponds to said keyword;

c) identifying said subpattern that satisfies a first constraint of said production rule, said first constraint having a corresponding nonterminal symbol N;

d) determining that said subpattern contains only one symbol X; and

e) determining that a production rule exists wherein said syntactic part and said nonterminal rule symbol N produces said symbol X.

8. A method as recited in claim 6 wherein said step of identifying a subpattern further comprises a step of determining that a subpattern in said input pattern satisfies a spatial constraint relative to a different subpattern in said input pattern.

9. A method as recited in claim 8 wherein said step of determining that a subpattern satisfies a spatial constraint includes determining that a subpattern has multi-dimensional relationships with different subpatterns.

10. A method as recited in claim 1 wherein said step of identifying a subpattern further comprises examining a relevance measure of each of said keywords to determine the relevance of said keywords and the order of keywords to be matched to said subpattern.

11. A method as recited in claim 1 wherein said editing step includes substituting a changed value or a changed operator into said structure of said parsed tree.

12. A method as recited in claim 1 further comprising deriving and displaying a result of said equation utilizing said edited parsed tree by executing an operator at nodes of said parsed tree using operands included in said parsed tree.

13. A system for processing handwritten equations comprising:

digital processing means;

screen means coupled to said digital processing means, said screen means being operative to display images in response to signals from said digital processing means and to transmit stroke signals to said digital processing means in response to the movement of a stylus means across said screen means;

equation recognition means responsive to said stroke signals and operative to detect valid equations formed on said screen means, said equation recognition means including;

means for parsing said equation to form a parsed tree, said means for parsing utilizing a constrained attribute grammar including a set of production rules, wherein said stroke signals are input to said means for parsing as a pattern including a set of subpatterns, and

means for detecting whether a valid parsed tree has been formed by checking when said set of subpatterns can be rewritten as a start symbol according to said production rules and constraints included within said production rules, said constraints including keywords to be identified in said subpatterns;

equation solving means operative to provide a result for said valid equations from said valid parsed tree;

means for displaying said equation and said result on said screen proximate to said equation; and

editing means for detecting an edit to said displayed equation and for editing said parsed tree in response to said edit to said displayed equation and without changing a structure of said parsed tree.

14. A system as recited in claim 13 wherein said editing means comprises:

means for detecting an edit made to an equation displayed upon said screen means having a valid parsed tree;

means for determining whether said edit changes the structure of said parsed tree; and

means for editing said parsed tree if said edit does not change the structure of said parsed tree.

15. A system as recited in claim 14 wherein said means for determining comprises means for determining that the parsed tree is not changed if said edit changes only a value or an operator of said equation.

16. A system as recited in claim 15 wherein said means for editing said parsed tree comprises means for substituting a changed value or a changed operator into said structure of said parsed tree.

17. A computer system for processing handwritten equations comprising:

a) means for receiving an input pattern comprising an equation which was derived from user handwritten strokes on an input tablet;

b) a parser for parsing said input pattern, said parser including;

i) means for recognizing said input pattern as a valid pattern utilizing a defined constrained attribute grammar, said grammar including a set of production rules and a grammar start symbol, wherein said means for recognizing determines when said input pattern is valid by determining when said set of input subpatterns can be rewritten as said start symbol according to said set of production rules, wherein said production rules include a syntactic part, a semantic part, a constraints part, and an action part, said constraints part including spatial constraints that require predetermined spatial relationships be satisfied between said input subpatterns; and

ii) means for providing a parsed tree when said means for recognizing recognizes said input pattern as a valid pattern;

c) data manipulation means for deriving a result of said equation utilizing said parsed tree by executing an operator at nodes of said parsed tree using operands included in said parsed tree; and

d) editing means for detecting an edit to said equation and for editing said parsed tree in response to said edit to said equation and without changing a structure of said parsed tree.

18. A computer system as recited in claim 17 further comprising a display screen for displaying said result on said screen assembly and wherein said tablet comprises a touch sensitive screen assembly.

19. A computer system as recited in claim 18 wherein said production rules include constraints for identifying keywords and non-keywords within said input subpatterns and relevance measures for said keywords for matching said keywords to said input subpatterns in an order based on the relevance measures of said keywords.

20. A computer system as recited in claim 19 wherein said parser includes:

a) means for determining that one of a plurality of subpatterns in said pattern matches one of said keywords;

b) means for identifying a production rule that corresponds to said keyword;

c) means for identifying said subpattern that satisfies a first constraint of said production rule, said first constraint having a corresponding nonterminal symbol N;

d) means for determining that said subpattern contains only one symbol X; and

e) means for determining that a production rule exists wherein said syntactic part of said production rule and said nonterminal symbol N produces said symbol X.

21. A computer system as recited in claim 20 wherein said editing means includes:

means for detecting an edit made to an equation displayed upon said display screen having a valid parsed tree;

means for determining whether said edit changes the structure of said parsed tree; and

means for editing said parsed tree if said edit does not change the structure of said parsed tree.

22. A computer system as recited in claim 21 wherein said means for determining whether said edit changes the structure of said parsed tree comprises means for determining that the parsed tree is not changed if said edit changes only a value or an operator of said equation, and wherein said means for editing said parsed tree comprises means for substituting a changed value or a changed operator into said structure of said parsed tree.

23. A computer system as recited in claim 21 wherein said parser is included in a recognition domain, and said computer system further comprises a plurality of recognition domains, each including a parser, said recognition domains including:

a strokes recognition domain;

a word recognition domain coupled to an output of said strokes recognition domain;

a math symbols recognition domain coupled to an output of said word recognition domain; and

a calculation recognition domain coupled to an output of said math symbols recognition domain.

24. A method as recited in claim 17 wherein said step of determining that one of said subpatterns satisfies a spatial constraint includes determining that one of said subpatterns has multi-dimensional relationships with different subpatterns.