Method and system for recognizing a graphic object's shape, line style, and fill pattern in a pen environment

• US 5,287,417 A
• Filed: 09/10/1992
• Issued: 02/15/1994
• Est. Priority Date: 09/10/1992
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Leyerle, Christopher, Pardikar, Shishir P., Eller, Marlin
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/942,952
• Time in Patent Office: 523 Days
• Field of Search: 382/41, 382/49, 382/45, 382/46, 382/47, 382/9, 382/22, 340/727, 340/731, 395/100, 395/118, 395/133, 395/137-139, 395/143
• US Class Current: 382/276
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• 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/32 Digital ink

Abstract

A method and system for recognizing a graphic object'"'"'s shape, line style, and fill pattern in a pen environment are provided. In a preferred embodiment, a user draws a graphic object on an electronic tablet of a computer system. The graphic object comprises a shape attribute, a line style attribute, and a fill pattern attribute. A Recognizer, provided by the present invention, recognizes the graphic object drawn by the user. The graphic object drawn by the user is made up of a plurality of data points, each data point having an x-coordinate and a y-coordinate. The Recognizer subdivides the plurality of data points into one or more strokes, each stroke representative of a path travelled by the handwriting instrument after the handwriting instrument touches the electronic tablet and before the handwriting instrument is lifted off of the electronic tablet. For each data point in each stroke, the recognizer maps the data point to a normalized data point, then transforms the normalized data point into a transformed data point, and then determines whether the transformed data point is a shape-defining data point or an interior-defining data point. Shape-defining data points are representative of the shape attribute and the line style attribute, while the interior-defining data points are representative of the fill pattern attribute. Based on the coordinates of the transformed data points and the coordinates of the data points input by the user, the recognizer determines the attributes. After determining what the attributes of the graphic object are, the recognizer selects a representation of the graphic object that corresponds to the determined attributes and displays the selected representation on the electronic tablet.

Claims

1. A method of recognizing a graphic object in a computer system, the computer system comprising a handwriting instrument and an electronic tablet, the graphic object comprising a shape attribute, a line style attribute, and a fill pattern attribute, the method comprising the steps of:

drawing the graphic object on the electronic tablet with the handwriting instrument to produce a plurality of data points, the data points comprising shape-defining data points and interior-defining data points, the shape-defining data points representative of the shape attribute and the line style attribute and the interior-defining data points representative of the fill pattern attribute, each data point having an x-coordinate and a y-coordinate;

segmenting the plurality of data points into one or more strokes, wherein each stroke comprises one or more data points in a path traveled by the handwriting instrument after the handwriting instrument touches the electronic tablet and before the handwriting instrument is lifted off of the electronic tablet, the strokes comprising shape-defining strokes and interior-defining strokes, each shape-defining stroke having only shape-defining data points and each interior-stroke having only interior-defining data points;

for selected ones of the data points

mapping the data point to a normalized data point, the normalized data point having an x-coordinate and a y-coordinate that are within a predetermined range of values; and

transforming the normalized data point into a transformed data point by rotating the normalized data point a preselected angle;

determining an average number of data points per stroke;

based on the average number of data points per stroke, determining the line style attribute of the graphic object;

based on the largest and smallest x-coordinate of the data points, the largest and smallest y-coordinate of the data points, the largest and smallest x-coordinate of the transformed data points, and the largest and smallest y-coordinate of the transformed data points, determining the shape attribute of the graphic object;

based on the largest and the smallest y-coordinate of the transformed data points, determining the slope of the shape attribute of the graphic object when the shape attribute is determined to be equal to a line;

based on the x-coordinate and y-coordinate of the interior-defining data points, determining the fill pattern attribute of the graphic object; and

selecting a representation of the graphic object corresponding to the determined line style attribute, the determined shape attribute, and the determined format attribute.

2. The method of claim 1 wherein the step of transforming the normalized data point into a transformed data point by rotating the normalized data point includes the steps of:

setting the x-coordinate of the transformed data point equal to the x-coordinate of the normalized data point plus the y-coordinate of the normalized data point; and

setting the y-coordinate of the transformed data point equal to the x-coordinate of the normalized data point minus the y-coordinate of the normalized data point.

3. The method of claim 1 wherein the step of transforming the normalized data point into a transformed data point includes the steps of:

after transforming the normalized data point, determining whether the transformed data point corresponds to a shape-defining data point or an interior-defining data point;

incrementing a value representative of the total number of interior-defining data points when the transformed data point is determined to be an interior-defining data point; and

incrementing a value representative of the total number of shape-defining data points when the transformed data point is determined to be a shape-defining data point.

4. The method of claim 3 wherein the step of determining whether the transformed data point corresponds to a shape-defining data point or an interior defining data point includes the steps of:

mapping the transformed data point to the first quadrant of the x-y coordinate plane;

when the x-coordinate or the y-coordinate of the mapped data point is greater than a first border threshold value, determining the transformed data point to be a shape-defining point;

when the sum of the x-coordinate of the mapped data point and the y-coordinate of the mapped data point is greater than a second border threshold, determining the transformed data point to be a shape-defining point; and

when the x-coordinate or the y-coordinate of the mapped data point is less than or equal to the first border threshold value and the sum of the x-coordinate of the mapped data point added to the y-coordinate of the mapped data point is less than or equal to the second border threshold, determining the transformed data point to be an interior-defining point.

5. The method of claim 4 wherein the first border threshold and the second border threshold represent a linear approximation of a circular line.

6. The method of claim 3 wherein the step of determining an average number of data points per stroke includes dividing the total number of shape-defining data points by the total number of strokes that contain shape-defining data points.

7. The method of claim 1 including, subsequent to the step of transforming the normalized data point into a transformed data point, the step of determining which octant of the x-y coordinate plane contains the transformed data point.

8. The method of claim 1 wherein the predetermined range of values is equal to -1000 to 1000.

9. The method of claim 1 wherein the step of determining the line style attribute of the graphic object includes determining the line style attribute of the graphic object to be equal to a dotted line style when the average number of data points per stroke is less than or equal to a predetermined value.

10. The method of claim 9 wherein the predetermined value is equal to 136.

11. The method of claim 1 wherein the step of determining the line style attribute of the graphic object includes determining the line style attribute of the graphic object to be equal to a dashed line style when the average number of data points per stroke is greater than a first predetermined value and less than or equal to a second predetermined value.

12. The method of claim 11 wherein the first predetermined value is equal to 136 and the second predetermined value is equal to 512.

13. The method of claim 1 wherein the step of determining the line style attribute of the graphic object includes determining the line style attribute of the graphic object to be equal to a solid line style when the average number of data points per stroke is greater than a second predetermined value.

14. The method of claim 13 wherein the second predetermined value is equal to 512.

15. The method of claim 1 wherein the step of determining the shape attribute of the graphic object includes the steps of:

when the largest x-coordinate is substantially equal to the smallest x-coordinate, determining the shape of the graphic object to be equal to a vertical line; and

when the distance between the largest y-coordinate and the smallest y-coordinate, divided by the distance between the largest x-coordinate and the smallest x-coordinate, is greater than a line slant threshold value, determining the shape of the graphic object to be equal to a vertical line.

16. The method of claim 1 wherein the step of determining the shape attribute of the graphic object includes the steps of:

comparing the largest of y-coordinate to the smallest coordinate;

when the largest y-coordinate is equal to the smallest y-coordinate, determining the shape of the graphic object to be equal to a horizontal line;

subtracting the smallest x-coordinate from the largest x-coordinate; and

when the distance between the largest x-coordinate and the smallest x-coordinate, divided by the distance between the largest y-coordinate and the smallest y-coordinate, is greater than the line slant threshold value, determining the shape of the graphic object to be equal to a horizontal line.

17. The method of claim 1 wherein the step of determining the shape attribute of the graphic object includes determining the shape attribute of the graphic object to be equal to a negatively sloped line when the largest x-coordinate is not equal to the smallest x-coordinate and the largest y-coordinate is not equal to the smallest y-coordinate and the absolute value of both the largest and the smallest y-coordinates of the transformed data points are less than an incline threshold value.

18. The method of claim 1 wherein the step of determining the shape attribute of the graphic object includes determining the shape attribute of the graphic object to be equal to a positively sloped line when the largest x-coordinate is not equal to the smallest x-coordinate, the largest y-coordinate is not equal to the smallest y-coordinate, the absolute value of either the largest or the smallest y-coordinate of the transformed data points is greater than or equal to an incline threshold value, and the absolute value of both the largest and the smallest x-coordinates of the transformed data points are less than the incline threshold value.

19. The method of claim 1 wherein the step of determining the shape attribute of the graphic object includes determining the shape attribute of the graphic object to be equal to a scribble when the largest x-coordinate is not equal to the smallest x-coordinate, the largest y-coordinate is not equal to the smallest y-coordinate, the absolute value of either the largest or the smallest y-coordinate of the transformed data points is greater than or equal to an incline threshold value, and the absolute value of either the largest or the smallest x-coordinate of the transformed data points is greater than or equal to the incline threshold value.

20. The method of claim 1 wherein the step of determining the fill pattern attribute of the graphic object includes determining the fill pattern attribute to be equal to a transparent fill pattern when the number total number of inter-defining points is less than or equal to an interior threshold value.