Method and apparatus for processing graphically input equations

• US 5,627,914 A
• Filed: 06/07/1995
• Issued: 05/06/1997
• 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): Razavi, Michael T.
• Assistant Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/488,039
• Time in Patent Office: 699 Days
• Field of Search: 382/186, 382/187, 382/188, 382/189, 382/229, 364/419.08, 364/735, 364/736, 395/12
• 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; all 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, graphically input equations on a computer system, comprising the steps of:

(a) receiving an input pattern in a computer system comprising an equation which was derived from user handwritten strokes input using a pointing device;

(b) 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;

(c) providing a parsed tree from said parsing step, said parsed tree being derived from said input pattern when said input pattern is determined to be a valid pattern in said parsing step;

(d) 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;

(e) detecting an edit made to said equation having said result; and

(f) editing said parsed tree associated with said equation in response to said edit made to said 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 pointing device comprises a touch sensitive tablet.

3. A method as recited in claim 2 further comprising displaying said result on said tablet.

4. 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 input by said pointing device.

5. 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.

6. A method as recited in claim 1 wherein said constraints include keywords to be identified within said subpatterns, wherein said parsing step includes determining the relevance of said keywords to provide an order of parsing said subpatterns matched to said keywords.

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 role, 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 1 wherein said step of parsing said input pattern includes identifying a subpattern by determining that said subpattern 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 both a vertical and horizontal relationship with different subpatterns.

10. A method as recited in claim 1 wherein said constraints including keywords to be identified in said subpatterns, wherein a relevance of said keywords is determined to provide an order of parsing said subpatterns matched to said keywords, said step of determining the relevance of said keywords includes determining said relevance based on a spatial width of said subpattern.

11. A system for processing handwritten equations comprising:

a digital processor;

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

equation recognition means responsive to said stroke signals and operative to detect valid equations formed on said display screen, 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;

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 display 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.

12. A system as recited in claim 11 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.

13. A system as recited in claim 12 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.

14. A system as recited in claim 13 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.

15. A computer system for processing handwritten equations comprising:

a processor;

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

a parser for parsing said input pattern, said parser being implemented by said processor and including;

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; and

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

data manipulation means implemented by said processor 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;

editing means for editing said parsed tree in response to an edit to said equation, said parsed tree being edited without changing a structure of said parsed tree; and

a display screen coupled to said processor for displaying said result of said equation.

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

17. A computer system as recited in claim 16 wherein one of said relevance measures is determined based upon a dimension of a side of a bounding box of said keyword associated with said relevance measure.

18. A computer system as recited in claim 16 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.

19. A computer system as recited in claim 18 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, wherein said parsed tree is determined not to be changed when said edit changes only a value or an operator of said equation; and

means for editing said parsed tree when said edit does not change the structure of said parsed tree, 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.

20. A computer system as recited in claim 15 wherein said constraints part includes spatial constraints, and further comprising means for determining that one of said subpatterns satisfies a spatial constraint by determining that one of said subpatterns has both a vertical and horizontal relationship with different ones of said subpatterns.

21. A computer system as recited in claim 20 wherein said parser is included in a recognition domain, and said computer system further comprises a plurality of recognition domains, each recognition domain including a data portion having said production rules and a procedures portion having said parser, said plurality of 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.

22. A computer readable medium containing program instructions for:

receiving an input pattern in a computer system comprising an equation which was derived from user handwritten strokes input using an input pointing device;

displaying said equation on a display screen of said computer system;

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;

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

deriving and displaying 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;

detecting an edit made to said equation displayed upon said display screen;

determining whether said edit changes the structure of said parsed tree, wherein said parsed tree is determined not to be changed when said edit changes only a value or an operator of said equation;

editing said parsed tree in response to said edit made to said displayed equation when said edit does not change the structure of said parsed tree, wherein said editing step includes substituting a changed value or a changed operator into said structure of said parsed tree; and

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.