Reshaping freehand drawn lines and shapes in an electronic document

• US 7,450,763 B2
• Filed: 03/18/2005
• Issued: 11/11/2008
• Est. Priority Date: 04/16/2001
• Status: Expired due to Term

• Current Assignee: Bending Spoons SpA
• Original Assignee: Evernote Corp. (Bending Spoons SpA)
• Inventors: Gorbatov, Boris, Lossev, Ilia
• Primary Examiner(s): Desire; Gregory M
• Application Number:
  US11/084,709
• Publication Number:
  US 20050244058A1
• Time in Patent Office: 1,334 Days
• Field of Search: 348/443, 348/468, 382/187, 382/190, 382/202, 382/203, 382/186, 345/441, 345/443, 345/468, 700/182
• US Class Current: 382/202
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

The invention improves the appearance of freehand drawn lines and shapes in an electronic document by first recognizing freehand drawn lines and shapes and generating a line made up of sequential straight line segments for the freehand drawn line when the line does not form a closed line and generating a multiple straight-line-segment shape when the line forms a closed line. If a multiple segment shape is being reshaped, a basic shape is selected from reference ideal shapes as the basic shape of the multiple segment shape. The basic shape is adjusted to provide a specific shape as an improved shape for the freehand drawn shape. The recognition of the freehand drawn lines and shapes is accomplished by comparing source segments of a source freehand drawn line to a straight line and substituting a straight line segment for a source segment if the deviation between the source segment and the straight line is below a predetermined value. Sequential source segments of a source freehand drawn line are evaluated to determine if they are an angle segment. A segment pair of sequential source line segments are defined as an angle segment having two straight line segments intersecting at a common end point if both source segments of the segment pair are within a predetermined deviation value from a straight line. The straight line segments and angle segments are combined to form a multiple segment line if the line does not close on itself and a multiple segment shape if the line does close on itself.

Claims

1. A method for reshaping freehand drawn inputs in a system having a display and a device for drawing on the display, the method comprising:

analyzing freehand drawn inputs;

generating a polyline which substitutes for a freehand drawn input if the freehand drawn input does not form a substantially closed line and generating a polyline shape which substitutes for the freehand drawn input if the freehand drawn input forms a substantially closed line;

selecting a basic shape from reference ideal shapes for said polyline shape; and

adjusting the basic shape to a specific shape as an improved polyline shape.

2. The method of claim 1 wherein selecting and adjusting are performed based on a logical tree where the basic shape occupies a high level node and the specific shape occupies a low level node associated to the high level node for the basic shape.

3. The method of claim 1 wherein generating the polyline and the polyline shape comprises:

defining a source segment from the freehand drawn input as a line segment if a deviation between the source segment and a first straight line is less than a first predetermined value;

defining the source segment and a neighbor source segment from the freehand drawn input as an angle segment if the deviation between the source segment and the first straight line is not less than the predetermined value but if deviations between both the source segment and the neighbor source segment and a second straight line are less than a second predetermined value;

dividing the source segment into a plurality of new source segments if either the deviation between the source segment and the second straight line or the deviation between the neighbor source segment and the second straight line is not less than the second predetermined value, and repeating said defining process until substantially all source segments from the freehand drawn input are defined as either a line segment or an angle segment;

generating a combined segment by combining one or more line segments and one or more angle segments; and

generating the polyline if the combined segment does not close on itself and generating the polyline shape if the combined segment does close on itself.

4. The method of claim 1 wherein the freehand drawn inputs are described as a sequence of X, Y coordinates.

5. The method of claim 1 wherein the freehand drawn inputs are resulted from a stroke preprocessing operation including data filtering or data extrapolation.

6. The method of claim 1 wherein selecting the basic shape comprises:

generating a transformed shape for each ideal shape by transforming points of said ideal shape to points of the polyline shape;

obtaining a similarity value by matching the transformed shape against the polyline shape; and

determining the ideal shape having the transformed shape with the highest similarity as the basic shape.

7. A system for reshaping freehand drawn inputs in a computing system having a display and a device for drawing on the display, the system comprising:

a polyline recognition module which analyzes freehand drawn inputs, generating a polyline which substitutes for a freehand drawn input if the freehand drawn input does not form a substantially closed line and generating a polyline shape which substitutes for the freehand drawn input if the freehand drawn input forms a substantially closed line;

a basic shape recognition module which selects a basic shape from reference ideal shapes for said polyline shape; and

a shape adjustment module which adjusts the basic shape to a specific shape as an improved polyline shape.

8. The system of claim 7 wherein the basic shape recognition module performs the selecting based on a logical tree where the basic shape occupies a high level node and the specific shape occupies a low level node associated to the high level node for the basic shape.

9. The system of claim 8 wherein the shape adjustment module performs the adjusting based on the logical tree.

10. The system of claim 7 wherein the polyline recognition module further comprises:

a definition module which defines a source segment from the freehand drawn input as a line segment if a deviation between the source segment and a first straight line is less than a first predetermined value, and defines the source segment and a neighbor source segment from the freehand drawn input as an angle segment if the deviation between the source segment and the first straight line is not less than the predetermined value but if deviations between both the source segment and the neighbor source segment and a second straight line are less than a second predetermined value;

a divider module which divides the source segment into a plurality of new source segments if either the deviation between the source segment and the second straight line or the deviation between the neighbor source segment and the second straight line is not less than the second predetermined value, and sends the new source segments to the definition module until substantially all source segments from the freehand drawn input are defined as either a line segment or an angle segment; and

a combiner module which combines one or more line segments and one or more angle segments to generate a combined segment in order for the polyline recognition module to generate the polyline if the combined segment does not close on itself and generate the polyline shape if the combined segment does close on itself.

11. The system of claim 7 wherein the freehand drawn inputs are described as a sequence of X, Y coordinates.

12. The system of claim 7 wherein the freehand drawn inputs are resulted from a stroke preprocessing operation including data filtering or data extrapolation.

13. The system of claim 7 wherein the selection module generates a transformed shape for each ideal shape by transforming points of said ideal shape to points of the polyline shape, obtains a similarity value by matching the transformed shape against the polyline shape, and determines the ideal shape having the transformed shape with the highest similarity as the basic shape.

14. A computer program product readable by a computer readable storage medium, which contains a computer program comprising instructions for executing a computer process for reshaping freehand drawn inputs in a system having a display and a device for drawing on the display, said computer process comprising:

analyzing freehand drawn inputs;

generating a polyline which substitutes for a freehand drawn input if the freehand drawn input does not form a substantially closed line and generating a polyline shape which substitutes for the freehand drawn input if the freehand drawn input forms a substantially closed line;

selecting a basic shape from reference ideal shapes for said polyline shape; and

adjusting the basic shape to a specific shape as an improved polyline shape.

15. The computer program product of claim 14 wherein selecting and adjusting are performed based on a logical tree where the basic shape occupies a high level node and the specific shape occupies a low level node associated to the high level node for the basic shape.

16. The computer program product of claim 14 wherein generating the polyline and the polyline shape comprises:

defining a source segment from the freehand drawn input as a line segment if a deviation between the source segment and a first straight line is less than a first predetermined value;

defining the source segment and a neighbor source segment from the freehand drawn input as an angle segment if the deviation between the source segment and the first straight line is not less than the predetermined value but if deviations between both the source segment and the neighbor source segment and a second straight line are less than a second predetermined value;

dividing the source segment into a plurality of new source segments if either the deviation between the source segment and the second straight line or the deviation between the neighbor source segment and the second straight line is not less than the second predetermined value, and repeating said defining process until substantially all source segments from the freehand drawn input are defined as either a line segment or an angle segment;

generating a combined segment by combining one or more line segments and one or more angle segments; and

generating the polyline if the combined segment does not close on itself and generating the polyline shape if the combined segment does close on itself.

17. The computer program product of claim 14 wherein the freehand drawn inputs are described as a sequence of X, Y coordinates.

18. The computer program product of claim 14 wherein the freehand drawn inputs are resulted from a stroke preprocessing operation including data filtering or data extrapolation.

19. The computer program product of claim 14 wherein selecting the basic shape comprises:

generating a transformed shape for each ideal shape by transforming points of said ideal shape to points of the polyline shape;

obtaining a similarity value by matching the transformed shape against the polyline shape; and

determining the ideal shape having the transformed shape with the highest similarity as the basic shape.