Script character processing method for compression encoding and smoothing of ink strokes

• US 6,442,578 B1
• Filed: 10/19/1998
• Issued: 08/27/2002
• Est. Priority Date: 03/20/1991
• Status: Expired due to Fees

• Current Assignee: Microsoft Corporation
• Original Assignee: Microsoft Corporation
• Inventors: Forcier, Mitchell D.
• Primary Examiner(s): Hong, Stephen S.
• Application Number:
  US09/175,054
• Time in Patent Office: 1,408 Days
• Field of Search: 707/541, 707/530, 707/531, 345/863, 382/292, 382/311
• US Class Current: 715/273
• CPC Class Codes: G06F 3/0488 using a touch-screen or digitiser, e.g. input of commands through traced gestures
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06F 40/10 Text processing natural language analysis G06F40/20; semantic analysis G06F40/30; processing or translation of natural language G06F40/40
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting

Abstract

A pen-based processor needs to be usable to input and edit script like a text-based computer but retain a resemblance to the user of a pad and pencil. The disclosed system and method implement input, editing and other manipulation of glyphs including handwritten script, ASCII test, bit-mapped images and drawings in a common document, using a compatible internal representation of the data and a simple, consistent set of user control functions. These functions are invoked using an intuitive and interactive set of user gestures which do not distract the user from the task of inputting or editing the document. A two-step gesture method avoids confusion between strokes and command gestures and allows use of similar gestures for different functions within the same and different contexts. The system infers from customary user writing conventions that certain relationships of data are to be preserved and maintains the relationships, subject to user override, during editing. The display document is formatted to contain lined or unlined areas of glyphs that can be edited, including insertion of a moving space into pre-existing document text and word wrapping. Adjoining drawing areas are unaffected by editing of text data.

Claims

1. A computerized method for compression encoding ink strokes, each stroke consisting of a finite series of data points including a starting point, the method comprising:

storing a value from which the starting point of the stroke can be determined;

establishing a current direction by examining point placement in the stroke;

determining and storing a direction for each successive data point in the stroke, including storing a datum defining each occurrence or an absence of a change of direction from the current direction.

2. A method according to claim 1 in which an initial direction is encoded from the starting point to a second point and a second direction from the second point to a third point is encoded so as to define one of no-change-in-direction from the preceding point and a clockwise or counterclockwise change from said direction to establish a new direction.

3. A method according to claim 2 including encoding the initial direction as at least three binary digits, encoding the no-change-of-direction as at least one binary digit, encoding the clockwise or counterclockwise change of direction as at least one binary digit, and serially concatenating said binary digits for the finite series of points in the stroke.

4. A method according to claim 3 including encoding a predetermined number of binary digits defining a number of data points in each stroke and concatenating said plurality of binary digits with the binary digits serially concatenated for the finite series of points in the stroke.

5. A method according to claim 4 including dividing strokes having a length exceeding a predetermined maximum length into at least two ministrokes and concatenating each encoded ministroke to form the whole stroke.

6. A method according to claim 2 including dividing strokes having a change in direction exceeding a predetermined maximum deflection, into at least two ministrokes and concatenating each encoded ministroke to form the whole stroke.

9. A method according to claim 1 including preprocessing the data points defining the stroke with a smoothing algorithm in order to reduce the number of directional changes and the magnitude of the directional changes within the stroke.

7. A computerized method for smoothing ink strokes to enable more efficient compression encoding, each stroke consisting of a finite series of data points, the method comprising:

(a) searching for a series of three adjoining data points which form an L formation beginning at a first point;

(b) removing the one of the second or third points forming an L formation that requires the largest change in X and Y coordinate values to get to a fourth point;

(c) referring to the retained second or third point as the first point; and

(d) processing the entire stroke with steps (a), (b) and (c).

8. A method according to claim 7 including preprocessing the data points defining each stroke to remove gaps or duplicate data points.—

10. A computerized method for compression encoding ink strokes, each stroke consisting of a finite series of data points, the method comprising:

identifying one or more portions of the stroke that are compressed to the greatest extent by a particular compression technique;

compression encoding the identified portions of the stroke using the particular compression technique;

compression encoding any remaining portions of the stroke using other compression techniques;

concatenating the various compressed portions of the stroke to form the whole stroke.

11. A method according to claim 10 including preprocessing the data points defining the stroke with a smoothing algorithm in order to reduce the number of directional changes and the magnitude of the directional changes within the stroke.

12. A computerized method for compression encoding a finite series of data points for compressed storage in a computer memory, the method comprising:

storing a first value from which the starting point of the series can be determined;

storing a second value from which an initial current direction can be determined;

storing in series a third value for each successive data point that, when combined with the current direction, yields the direction of the point from its preceding point;

the third value used to determine the direction of a point from its preceding point being encoded so as to define one of no-change-in-direction from the current direction and a clockwise or counterclockwise change from said direction.

13. A method according to claim 12 including encoding one of the no-change-of-direction, clockwise change of direction, or counterclockwise change of direction as at least one binary digit, and encoding the other changes of direction as at least two binary digits.

14. A method according to claim 12 including storing a count of the number of compression encoded data points in the series.

15. A method according to claim 14 in which the count is encoded in a predetermined number of binary digits and concatenated with the values stored for the finite series of points.

16. A method according to claim 12 including dividing a series of data points having a length exceeding a predetermined maximum length into at least two parts and chaining together each encoded part to form the whole series of data points.

17. A method according to claim 12 including dividing a series of data points having a change in direction exceeding a predetermined maximum deflection, into at least two parts and chaining together each encoded part to form the whole series of data points.

18. A method according to claim 12 in which the second value for the initial current direction is determined by examining data point placement within the series of data points to be compressed.

19. A method according to claim 18 in which the direction from a first point to a second point represents the initial current direction.

20. A method according to claim 12 in which the direction of a point from its preceding point becomes the new current direction.

21. A method according to claim 12 in which a delimiter value is stored to indicate the end of the series of compression encoded data points.

22. A method according to claim 12 including preprocessing the data points with a smoothing algorithm in order to reduce the number of directional changes and the magnitude of the directional changes among the data points.

23. A computerized method for smoothing a series of data points, the method comprising:

(a) searching for a series of three adjoining data points beginning with a first point which represent a 90 degree change in direction;

(b) removing the one of the second or third points in the group of three adjoining points that requires the largest change in X and Y coordinate values to get to a fourth point;

(c) referring to the retained second or third point as the first point; and

(d) processing the entire series of data points with steps (a), (b) and (c).

24. A method according to claim 23 including preprocessing the data points to remove gaps and duplicate data points.

25. A computerized method for compression encoding a finite series of data points using two different compression techniques, the method comprising:

identifying one or more segments in the series of data points that can be compressed to the greatest extent by a selected one of the two compression techniques;

compression encoding the identified segments using the selected one compression technique;

compression encoding any remaining segments using the other one of the two compression techniques;

chaining together the various compressed segments to form the entire series of data points.

26. A method according to claim 25 including preprocessing the data points with a smoothing algorithm in order to reduce the number of directional changes and the magnitude of the directional changes among the data points.