Method and apparatus for grouping and manipulating electronic representations of handwriting, printing and drawings

• US 5,517,578 A
• Filed: 05/20/1993
• Issued: 05/14/1996
• Est. Priority Date: 05/20/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: aha! Software Corp. (Microsoft Corporation)
• Inventors: Thompson, Michael P., Altman, Dan, Kusmer, Steven R., Stikeleather, Gregory
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Feild, Joseph H.
• Application Number:
  US08/064,954
• Time in Patent Office: 1,090 Days
• Field of Search: 395/144, 395/145-149, 395/154, 395/900, 395/155-161, 382/9, 382/13, 382/48, 382/57, 382/173, 382/176-179, 382/180, 382/181-182, 382/185-187, 382/189-190, 382/199-200, 382/202-203, 345/179-183, 345/126, 364/419.17
• US Class Current: 382/181
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: G06V 30/333 Preprocessing; Feature extraction
• CPC Class Codes: Y10S 706/90 Fuzzy logic

Abstract

A note taking system that integrates word-processing functionality and computerized drawing functionality for processing ink strokes comprises novel methods that provide this functionality such as: a method for modeless operation of the note taking system that automatically switches between providing word-processing functionality and drawing functionality; a novel method for processing ink strokes as drawings, a unique method for processing ink strokes as writing, and other methods for parsing the ink strokes into words, lines, and paragraphs. The present invention also includes additional methods for manipulating figures such as a division between line and shape type figures, and a special handle performing either rotation or re-sizing.

Claims

1. A computerized method for automatically selecting a layer with which to process an input ink stroke representation in a system having a display device, a drawing layer that processes input as drawing strokes and a writing layer that processes input as writing strokes, the drawing and writing layers corresponding to a same area shown on the display device, said method comprising the steps of:

determining bounds of the input ink stroke representation;

determining whether the bounds of the input stroke representation are greater than a predeterdmined size;

processing the input ink stroke representation with the drawing layer if the bounds of the input stroke representation are great than said predetermined side;

processing the input stroke representation with the writing layer if the bounds of the input ink stroke representation are not greater than said predetermined size;

determining whether the input ink stroke representation is a special case character; and

processing the input ink stroke representation using the operating system, wherein the special case character is processed by applying fuzzy logic to determine whether the input ink stroke representation is a tap gesture or a part of an ink character.

2. A computerized method for processing ink stroke representations into groups for manipulation as words, lines and paragraphs, said method comprising the steps of:

grouping the ink stroke representations into a plurality of line groups based on a position of each ink stroke representation;

combining the ink stroke representations of a selected line group into at least one word group;

dividing a display area on a screen into a first zone, a second zone, and a third zone, the first, second and third zones extending in a first direction substantially perpendicular to a second direction in which the plurality of line groups extend;

determining placement of the ink stroke representations for a first line group;

determining placement of the ink stroke representations for a second line group, said second line group adjacent to and following the first line group; and

combining the first and second line groups into a paragraph group if the first line group has strokes in third zone and the second line group has strokes in the first zone; and

forming separate paragraphs with the first and second line groups if the first line group does not have a stroke in third zone or the second line group does not have a stroke in the first zone.

3. The method of claim 2, wherein the step of grouping the ink stroke representations into a plurality of line groups based on a position of each ink stroke representation further comprises the steps of:

defining a plurality of line areas on a screen display;

determining a bounding box for each of the ink stroke representations;

dividing the plurality of ink stroke representations into word groups where each stroke in a word group has a bounding box within a predetermined distance of at least one other ink stroke representation in the word group;

selecting a word group of ink stroke representations;

calculating a weighted center for the selected word group based upon the bounding boxes of the ink stroke representations of selected word group; and

associating the ink stroke representations in the selected word group with the line area in which the weighted center for the selected word lies.

4. The method of claim 2, wherein the step of combining the ink stroke representations of the selected line group into at least one word group further comprises the steps of:

a) retrieving a first ink stroke representation associated with a line area;

b) calculating bounding bands for the first ink stroke representation;

c) forming a first word from the first stroke and the bounding bands of the first stroke;

d) retrieving a second ink stroke representation;

e) calculating bounding bands for the second ink stroke representation;

f) comparing the first ink stroke representation to the second ink stroke representation band by band;

g) grouping the first ink stroke representation and the second ink stroke representation together as a first word, if any of the bounding bands of the first ink stroke representation are within a predetermined distance of corresponding bounding bands of the second ink stroke representation;

h) grouping the first ink stroke representation as the first word and the second ink stroke representation as a second word, if none of the bounding bands are within a predetermined distance of corresponding bounding bands of the second ink stroke representation.

5. A computerized method for grouping a plurality of ink stroke representations and associating them with a line area, said method comprising the steps of:

defining a plurality of line areas on a screen display;

determining a bounding box for each of the ink stroke representations;

dividing the plurality of ink stroke representations into word groups where each ink stroke representation in a word group has a bounding box within a predetermined distance of at least one other ink stroke representation in the word group;

selecting a word group of ink stroke representations;

calculating a weighted center for the selected word group based upon the bounding boxes of the ink stroke representations of the selected word group; and

associating the ink stroke representations in the selected word group with the line area in which the weighted center for the selected word lies.

6. The method of claim 5, wherein the step of associating the ink stroke representations in the selected word group further comprises the steps of:

determining whether a first ink stroke representation in the selected word group was made within a predefined distance of other ink stroke representations that have been processed with the writing layer;

processing the first ink stroke representation with the writing layer if the first ink stroke representation was made within a predefined distance of other ink stroke representations that have been processed with the writing layer; and

processing the first ink stroke representation using the operating system if the first ink stroke representation was not made within a predefined distance of other ink stroke representations that have been processed with the writing layer.

7. The method of claim 5, wherein the step of associating the ink stroke representations in the selected word group further comprises the steps of:

identifying the selected word group as a punctuation mark;

determining whether the selected word group is positioned within a predetermined tolerance of the bottom right corner of an existing word associated with a previous line area adjacent to the line area in which the weighted center lies;

associating the selected word with the previous line area, if the selected word is positioned within a predetermined-tolerance of the bottom right corner of the existing word; and

associating the selected word with the line area in which the weighted center lies if the selected word is not positioned within the predetermined tolerance of the bottom right corner of the existing word.

8. A computerized method for processing a plurality of ink stroke representations associated with a line area into words, said method comprising the steps of:

a) retrieving a first ink stroke representation associated with the line area;

b) calculating bounding bands for the first ink stroke representation;

c) retrieving a second ink stroke representation

d) calculating bounding bands for the second ink stroke representation;

e) comparing the first ink stroke representation to the second ink stroke representation band by band;

f) grouping the first ink stroke representation and the second ink stroke representation together as a first word, if any of the bounding bands of the first ink stroke representation are within a predetermined distance of corresponding bounding bands of the second ink stroke representation;

g) grouping the first ink stroke representation as the first word and the second ink stroke representation as a second word, if none of the bounding bands of the first ink stroke representation are within a predetermined distance of corresponding bounding bands of the second ink stroke representation.

9. The method of claim 8, further comprising the steps of:

comparing the first word to an existing word already formed on the line area; and

grouping the ink stroke representations forming the first word and the ink stroke representations forming the existing word together into a single new word, if any of the bounding bands of ink stroke representations forming the first word are within a predetermined distance of corresponding bounding bands of ink stroke representations forming the existing word.

10. The method of claim 8, wherein step g further comprises the steps of:

retrieving an third ink stroke representation associated with the line area;

calculating bounding bands for the third ink stroke representation;

comparing bounding bands of the third ink stroke representation to the bounding bands of the first word band by band;

grouping the third ink stroke representation and the first word together as an increased sized first word, if any of the bounding bands of the third ink stroke representation are within a predetermined distance of corresponding bounding bands of the first word; and

grouping the third ink stroke representation as a second word if none of the bounding bands of the third ink stroke representation are within a predetermined distance of corresponding bounding bands of the first word.

11. A computerized method for combining a plurality of strokes associated with a selected line area together, said method comprising the steps of;

calculating a leftmost and a rightmost coordinate for a first stroke associated with the selected line area and a leftmost a rightmost coordinate for a second stroke associated with the selected line area;

calculating a center point for the first stroke and a center point for the second stroke;

comparing the center point of the first stroke to the leftmost and rightmost coordinates of the second stroke, and comparing the center point of the second stroke to the leftmost and rightmost coordinates of the first stroke; and

combining the first stroke and the second stroke together as a single word group if the center point of the first stroke is horizontally between approximately the leftmost and the rightmost coordinates of the second stroke or if the center point of the second stroke is horizontally between approximately the leftmost and the rightmost coordinates of the first stroke;

inputting a gesture over a word, the gesture indicating the word is to be split into two words;

identifying a hot point for the gesture;

determining the center point of each stroke forming the word;

forming a left word with the strokes forming the word that have a center point to the left of the hot point of the gesture;

forming a right word with the strokes forming the word that have a center point to the right of the hot point of the gesture; and

inserting a predetermined amount of space between the right word and the left word.

12. The method of claim 11, wherein the gesture is a stroke including a downward portion and rightward portion.

13. The method of claim 11, wherein the hot point of the gesture is the starting point from which the stroke forming the gesture begins.

14. A computerized method for grouping a plurality of lines of ink stroke representations into paragraph groups, said method comprising the steps of:

dividing a display area on a screen into a left zone, a center zone and a right zone, the left, center, and right zones extending across the plurality of lines;

determining a placement of the ink stroke representations on a first line;

determining a placement of the ink stroke representations on a second line, said second line adjacent to and following the first line; and

grouping the first line and the second line together as a paragraph group if the first line has ink stroke representations in the right zone and the second line has ink stroke representations in the left zone.

15. The computerized method of claim 14, wherein the left, center, and right zones extend substantially vertically across the display area.

16. The computerized method of claim 14, wherein the left, center, and right zones extend substantially horizontally across the display area.

17. The computerized method of claim 14, wherein the left, center, and right zones are not visible on the display area.

18. The computerized method of claim 14, wherein the left, center, and right zones are visible on the display area.

19. A computerized method for automatically categorizing a stroke as a line-type or shape-type, said method comprising the steps of:

determining a bounding box for the stroke;

determining a length, L, of a longest side of the bounding box;

determining a width, W, of an adjacent side the bounding box;

determining a position of a beginning point of the stroke;

determining a position of an ending point of the stroke;

setting the stroke to be a line-type if the position of the beginning point is within a predetermined percentage of L and W of a first corner of the bounding box, and the position of the end point is within the predetermined percentage of L and W of a second corner of the bounding box, and wherein the first and second corners are opposite corners.

20. The method of claim 19, wherein the predetermined percentage is less than 25%.

21. A computerized method for automatically categorizing a plurality of strokes as a line-type or shape-type object, said method comprising the steps of:

identifying the plurality of strokes for categorization;

defining a single bounding box surrounding the identified plurality of strokes;

determining a length, L, of a longest side of the bounding box;

determining a width, W, of an adjacent side the bounding box;

determining a position of a beginning point for each stroke in the identified plurality of strokes;

determining a position of an ending point for each stroke in the identified plurality of strokes;

setting the identified plurality of strokes to be a line-type object of for any stroke, the position of the stroke'"'"'s beginning point is within a predetermined percentage of L and W of a first corner of the bounding box, and the position of the stroke'"'"'s end point is within the predetermined percentage of L and W of a second corner of the bounding box, and wherein the first and second corners are opposite corners.

22. The method of claim 21, wherein the predetermined percentage is less than 25%.

23. A computerized method for automatically resizing or rotating a displayed position of a drawing figure on a display device based upon a single input by the user, said method comprising the steps of:

determining a handle of an associated figure selected by the user;

determining a direction in and an end point to which the handle is dragged by the user;

determining a bounding box for the associated figure and a closest side of the bounding box;

determining whether to rotate or resize the associated figure depending on the direction in which the handle is dragged;

rotating the figure such that the handle is aligned with the endpoint if the direction the handle is dragged is substantially parallel to the closest side of the bounding box; and

resizing the figure such that the handle is aligned with the endpoint if the direction the handle is dragged is substantially perpendicular to the closest side of the bounding box.

24. A computerized method for automatically identifying special characters that delineate outline-type formatting of paragraphs and inserting hanging indents, said method comprising the steps of:

retrieving words on a line;

identifying a bullet character;

determining a left boundary and a right boundary of the bullet character;

determining a left boundary of a first word to the right of the bullet character;

comparing the left boundary of the bullet character to leftmost boundaries of other words on preceding lines of a previous paragraph; and

setting an outline level based on the comparing step and a position for the hanging indent at the left boundary of the first word.

25. The computerized method of claim 24 further comprising the steps of:

storing the left and right boundaries of the bullet character and the left boundary of the first word; and

repeating the steps of retrieving, identifying, determining the left boundary and right boundary, determining the left boundary of the first word, comparing, setting, and storing for each additional line of words.

26. A computerized method for combining a plurality of strokes associated with a selected line area together as words, said method comprising the steps of:

grouping the plurality of strokes into characters;

determining measurement parameters about the characters including average character width;

defining a membership function for joining two adjacent characters together as a word from the measurement parameters;

retrieving a first character;

retrieving a second character that is adjacent to the first character;

determining measurement parameters between the first character and the second character;

combining the first and second characters into a word using the defined membership function and the measurement parameters between the first character and the second character.

27. The computerized method of claim 26, wherein the step of grouping the plurality of strokes into characters comprises the substeps of:

calculating a leftmost and a rightmost coordinate of each stroke;

averaging the leftmost and rightmost coordinates to get a center point for each stroke;

combining a first and second stroke together as a character if the center point of the first stroke is within approximately the leftmost and the rightmost coordinates of the second stroke; and

combining the first and second strokes together if the center point of the second stroke is within approximately the leftmost or rightmost coordinates of the first stroke.

28. The computerized method of claim 26, wherein the measurement parameters about the characters also include the average calculated distance between adjacent character center points;

and the average calculated space between words.

29. The computerized method of claim 28, wherein the measurement parameters are calculated using fuzzy membership function and a center of gravity calculation.

30. The computerized method of claim 26, wherein the membership function includes:

a Narrow Width membership function for discriminating very narrow characters;

a Character Width membership function for determining a typical character;

a Not Character Width membership function for determining if a stroke is too wide to be a character;

a Character Distance and Not Character Width membership functions for distances between characters;

a Character Delta and Word Delta membership functions for indicating whether characters form a word;

an Overlapping and Not Overlapping membership functions for determining whether the characters are overlapping; and

an Entry Merge membership table for determining whether to clump characters as words.

31. The computerized method of claim 30, wherein:

the measurement parameters about the characters include waviness of the stroke, where the waviness is the number of times the angle of a stroke polyline changed from heading up to heading down; and

the membership function includes Cursive and Printed membership functions for determining whether the characters are in cursive handwriting or printed handwriting.

32. The computerized method of claim 26, further comprising the step of calculating an overlap between the first character and the second character;

a character width of the first character and a character width of the second character.

33. The computerized method of claim 26, wherein the characters are combined by proceeding from left to right in the line and analyzing two characters at a time.

34. The computerized method of claim 26, further comprising a step of merging the word produced by the combining step with an existing word already present on the line area by:

calculating a leftmost and a rightmost coordinate of the existing word;

determining a center point for the word produced by the combining step; and

combining into a single new word the word produced by the combining step and the existing word if the center point of the word produced by the combining step is between approximately the leftmost and the rightmost coordinates of the existing word.

35. A computerized method for generating highlighting on strokes input and displayed by a computer system, said method comprising the steps of:

retrieving strokes selected for highlighting;

defining a bounding rectangle for the strokes, the bounding rectangle having a top, a bottom, a left side and a right side;

horizontally subdividing the bounding rectangle at intervals having at least 1/4 of line height;

generating a random number, h, between zero and 1/3 a line height for each horizontal subdivision;

setting a point at one line height minus h and another point at h for each subdivision;

creating a polygon by connecting the points proximate the top, the two points proximate the left side, points proximate the bottom and the two points proximate the right side of the bounding rectangle; and

displaying an area enclosed by the polygon in a visually distinct manner.

36. The computerized method of claim 35, further comprising the steps of testing whether there are additional words or spaces to highlight and repeating the steps of defining, horizontally subdividing, generating, setting, creating and displaying for each additional word to highlight.

37. The computerized method of claim 35, wherein the bounding rectangle is horizontally subdivided by intervals having about 1/32 of a line height.

38. A computerized method for grouping a plurality of lines of ink stroke representations into paragraph groups, said method comprising the steps of:

dividing a display area on a screen into a first zone, a second zone, a third zone and a fourth zone, the first, second, third and fourth zones extending in a direction substantially perpendicular a direction in which the lines extend;

determining placement of the ink stroke representations on a first line;

determining placement of the ink stroke representations on a second line, said second line following the first line; and

determining placement of the ink stroke representations on a third line, said third line following the second line;

grouping the first line and the second line together as a paragraph group if the first line has ink stroke representations in the first and fourth zones and the second line has ink stroke representations in the first zone; and

grouping the third line with the first line and the second line as a paragraph group if the second line has ink stroke representations in the fourth zone and the third line has ink stroke representations within a predetermined distance of a leftmost ink stroke representation of the second line.

39. The method of claim 38, wherein:

the first zone extends from a left edge of the display area to about 1/3 of a width of the display area from the left edge;

the second zone extends from 1/3 of the width of the display area from the left edge to about a middle of the display area;

the third zone extends from about the middle of the display area to about 2/3 the width of the display area from the left edge; and

the fourth zone extends from the right edge of display area to the right about 1/3 the width of the display area.

40. The method of claim 48, further comprising the steps of:

performing character recognition on a first character in the first line area;

determining whether the first character in the first line area is a valid bullet character;

determining the position of the first character

grouping the first line area and the second line area together as a paragraph group if (1) the first character in the first line is a valid bullet character, (2) the bullet character is positioned in the first or second zone, (3) the first line has ink stroke representations in the fourth zone, and (4) the second line has ink stroke representations in the first or second zone; and

grouping the third line area with the first line area and the second line area as a paragraph group if the second line area has ink stroke representations in the fourth zone and the third line area has ink stroke representations within a predetermined distance of a leftmost ink stroke representations of the second line area.

41. The method of claim 40, further comprising the steps of:

determining a left edge of the second line area;

determining a left edge of a following word in the first line area, the following word being the word immediately to the right of the bullet character; and

adjusting the left edge of the second line area to be about the same as the left edge of the following word.

42. A computerized method for grouping a plurality of lines of ink stroke representations into paragraph groups, said method comprising the steps of:

defining on a display area of a screen a plurality of line areas extending in a first direction;

dividing the display area of the screen into a first zone and a second zone, the first and second zones extending in a second direction substantially perpendicular to the first direction and across the plurality of line areas;

determining placement of the ink stroke representations in a first line area;

determining placement of the ink stroke representations in a second line area, said second line area adjacent and following the first line area;

grouping the ink stroke representations associated with the first line area and the second line area together as a paragraph group if the first line area has ink stroke representations in the second zone and the second line area has ink stroke representations in the first zone; and

grouping the ink stroke representations associated with the first line area as a first paragraph group and the ink stroke representations associated with the second line area as a second paragraph group if the first line area does not have ink stroke representations in the second zone or the second line area does not have ink stroke representations in the first zone.

43. A computerized method for grouping a plurality of lines of ink stroke representations into paragraph groups, said method comprising the steps of:

identifying a current line;

performing character recognition on a first character in the current line;

determining whether the first character in the current line is a valid bullet character; and

creating a new paragraph group beginning with the current line if the first character in the current line is a valid bullet character.