Method and apparatus for processing a freehand sketch

• US 6,233,351 B1
• Filed: 10/08/1997
• Issued: 05/15/2001
• Est. Priority Date: 08/12/1994
• Status: Expired due to Term

• Current Assignee: Dassault Systemes Americas Corp. (Dassault Systemes SA)
• Original Assignee: Dassault Systemes Americas Corp. (Dassault Systemes SA)
• Inventors: Feeney, Mark A., Corn, Edward T.
• Primary Examiner(s): Patel, Jay
• Application Number:
  US08/947,051
• Time in Patent Office: 1,315 Days
• Field of Search: 382/100, 382/203, 382/155, 382/156, 382/159, 382/173, 382/187, 364/488-491, 364/512, 345/425-443, 345/501, 345/964, 345/474.24, 345/433-440, 345/522, 345/442, 33/11, 33/181, 33/182-21, 33/211, 33/193, 33/203, 33/204, 707/502, 707/500, 706/15, 706/20
• US Class Current: 382/155
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction

Abstract

A computerized method of drawing provides sketching-type drawing capabilities in a computer-aided design (CAD) environment. Geometrical drawing parts or elements, sketched through a hand-controlled indicator and lacking in the precision criteria or standards associated with formal drawings, are recognized and interpreted as points, straight lines, open arcs, circles and ellipses. Delete and “areafill” symbols, similarly, are recognized and interpreted. The method also provides the capability to distinguish and interpret relatively complex, multiple-part or element strokes. This is done by determining break locations for the elements along the stroke, and by recognizing these elements before re-constituting a stroke meeting precision criteria. A variety of geometrical constraints which are important in a CAD environment, including coincidence, parallelism, tangency and relimitation, are also recognized and imposed. The recognizing of geometrical elements includes the use of pattern recognition and the use of a neural net. The determination of breaks incorporates the calculation of functions representative of changes in angle, of curvature, and of changes in slope, and the classification of information elements representative of locations, based on such calculations.

Claims

1. A computerized method for processing a drawing path from a sketch, said method comprising:

receiving a point stream representing the drawing path;

resolving the point stream into first and second segments based on at least one geometrical characteristic, each segment having a plurality of constituent points from the point stream;

classifying each of the first and second segments into one of a plurality of groups of geometric elements using a predetermined limit value;

identifying a geometric constraint between the first and second segments based on a classification of the first and second segments into the plurality of groups of geometric elements; and

repositioning the constituent points of the first segment relative to the constituent points of the second segment based upon the geometric constraint.

2. The method of claim 1 wherein repositioning includes making the first segment parallel to the second segment based upon a parallelism constraint.

3. The method of claim 2 wherein identifying a geometric constraint includes identifying the parallelism constraint between the first and second segments based upon a classification of the first and second segments into a line geometric element group.

4. The method of claim 1 wherein repositioning includes terminating the first and second segments at a common point based upon a relimitation constraint.

5. The method of claim 1 wherein repositioning includes making the first segment tangent to the second segment based upon a tangency constraint.

6. A computerized method for processing a freehand sketch, said method comprising:

receiving a point stream representing freehand movement by a computer-user;

resolving the point stream into one or more segments based on at least one geometrical characteristic;

classifying each of the one and more segments with a neural network as a line, arc or circle, using a predetermined limit value; and

generating a representation of the one or more segments based on a classification of each of the one or more segments as a line, arc or circle.

7. The method of claim 6 wherein generating a representation of the one or more segments based on a classification comprises generating a representation of each of the one or more segments substantially satisfying the geometric characteristics of a line, arc or circle.

8. The method of claim 6 wherein resolving the point stream into one or more segments comprises:

identifying a breakpoint in the point stream; and

resolving the point stream into two segments based on the breakpoint.

9. The method of claim 8 wherein identifying a breakpoint in the point stream comprises:

determining angles defined by sequences of points in the point stream; and

identifying the breakpoint based on the angles.

10. The method of claim 6 wherein classifying each of the one or more segments comprises mapping a first segment of the one or more segments into a grid.

11. The method of claim 10 wherein classifying each of the one or more segments with a neural network further comprises the steps of:

processing the first segment mapped into the grid with the neural network; and

the neural network outputting a plurality of values indicating a likelihood that the first segment is a line, arc or circle.

12. The method of claim 10 wherein mapping a first segment into a grid comprises rotating the first segment.

13. The method of claim 10 wherein mapping a first segment into a grid comprises scaling the first segment.

14. The method of claim 10 further comprises determining whether the one or more segments are open segments or closed segments and wherein mapping a first segment of the one or more segments into a grid comprises mapping the first segment in a first section of the grid if the first segment is an open segment and mapping the first segment in a second section of the grid if the first segment is a closed segment.

15. The method of claim 6 wherein classifying each of the one or more segments comprises classifying each of the one or more segments as a point, line, arc, circle, ellipse, area fill symbol or delete symbol.

16. The method of claim 6 further comprising:

generating dimensional information based on the point stream; and

displaying the dimensional information with the representation of the one or more segments.

17. A computer system for processing a drawing path from a sketch, said computer system comprising:

a processor;

a user input device;

a display device; and

a memory coupled to said processor, said memory having stored therein sequences of instructions which, when executed by said processor, cause said processor to perform the steps of;

receiving a point stream representing the drawing path lacking in certain precision criteria, the point stream representing input from said user input device;

resolving the point stream into first and second segments based on at least one geometrical characteristic, each segment having a plurality of constituent points from the point stream;

classifying each of the first and second segments into one of a plurality of groups of geometric elements using a predetermined limit value;

identifying a geometric constraint between the first and second segments based on a classification of the first and second segments into a plurality of groups of geometric elements; and

displaying the first and second segments on said display device, the constituent points of the first segment being repositioned relative to the constituent points of second segment based upon the geometric constraint.

18. A computer system for processing a freehand sketch, said computer system comprising:

a processor;

a user input device;

a display device; and

a memory coupled to said processor, said memory having stored therein sequences of instruction which, when executed by said processor, cause said processor to perform;

receiving a point stream based on input from said user-input, the point stream representing freehand movement by a user of said computer system;

resolving the point stream into one or more segments based on at least one geometric characteristic;

classifying each of the one or more segments with a neural network as a line, arc or circle, using a predetermined limit value, and

displaying on said display device a representation of the one or more segments based on a classification of each of the one or more segments as a line, arc or circle.

19. The computer system of claim 18 wherein the sequences of instructions which, when executed by said processor, cause said processor to perform classifying each of the one or more segments comprise instructions which, when executed by said processor, cause said processor to perform mapping a first segment of the one or more segments into a grid.

20. The computer system of claim 19 wherein the sequence of instructions which, when executed by said processor, cause said processor to perform classifying each of the one or more segments with a neural network further cause said processor to perform:

inputting values from the grid, including values representing the first segment mapped therein, into the neural network; and

reading a plurality of values output by the neural network, each value indicating the likelihood that the first segment is a line, arc or circle.

21. Computer-readable media having stored thereon a plurality of sequences of instructions, said plurality of sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to process a drawing path from a sketch by:

receiving a point stream representing the drawing path lacking in certain precision criteria;

resolving the point stream into first and second segments based on at least one geometrical characteristic, each segment having a plurality of constituent points from the point stream;

classifying each of the first and second segments into one of a plurality of groups of geometric elements using a predetermined limit value;

identifying a geometric constraint between the first and second segments based on a classification of the first and second segments into the plurality of groups of geometric elements; and

repositioning the constituent points of the first segment relative to the constituent points of the second segment based upon the geometric constraint.