141x Filetype PDF File size 0.28 MB Source: core.ac.uk
CORE Metadata, citation and similar papers at core.ac.uk Provided by Brunel University Research Archive Interpretation of Overtracing Freehand Sketching for Geometric Shapes Day Chyi Ku Sheng-Feng Qin David K. Wright School of Engineering and Design School of Engineering and Design School of Engineering and Design Brunel University Brunel University Brunel University Uxbridge Uxbridge Uxbridge UB8 3PH, UK UB8 3PH, UK UB8 3PH, UK Daychyi.Ku@brunel.ac.uk Sheng.Feng.Qin@brunel.ac. David.Wright@Brunel.ac.uk uk ABSTRACT This paper presents a novel method for interpreting overtracing freehand sketch. The overtracing strokes are interpreted as sketch content and are used to generate 2D geometric primitives. The approach consists of four stages: stroke classification, strokes grouping and fitting, 2D tidy-up with endpoint clustering and parallelism correction, and in-context interpretation. Strokes are first classified into lines and curves by a linearity test. It is followed by an innovative strokes grouping process that handles lines and curves separately. The grouped strokes are fitted with 2D geometry and further tidied-up with endpoint clustering and parallelism correction. Finally, the in-context interpretation is applied to detect incorrect stroke interpretation based on geometry constraints and to suggest a most plausible correction based on the overall sketch context. The interpretation ensures sketched strokes to be interpreted into meaningful output. The interface overcomes the limitation where only a single line drawing can be sketched out as in most existing sketching programs, meanwhile is more intuitive to the user. Keywords Freehand sketching, multistroke sketching, calligraphic interface, design 1. INTRODUCTION On the other hand, the system will also need to be Sketch interface is an important, natural application able to correctly interpret the user’s intent from the to support conceptual design. A sketch system drawing of the sketch. A trade-off is often required in implemented in a computer has the advantage the design of the calligraphic interface between being whereby further manipulations and processing, such natural, easy-to-use, and that of accuracy of the as 3D modelling from 2D sketch, can be made system’s interpretation of user’s intent. directly with minimal steps within a short time. One problem in the design of a natural but accurate However, this is realistic only if the system allows calligraphic interface is that of interpreting the flexibility of transferring ideas directly from overtracing of freehand sketch. Overtracing is designers through a series of freehand sketch. To frequently used to enhance and complete an edge support this process, the system should provide an during freehand sketching. A system that supports interface that is natural to the user as sketching with overtracing, i.e., accepts multiple stroke inputs, has pen and paper. Users may find sketching with the advantage of providing more drawing freedom to extensive menus difficult as a result of frequent the user. However, at the same time, overtracing interruptions. further increases the number of possible interpretations of a sketch, and as such, making the Permission to make digital or hard copies of all or part of system more susceptible to making mistakes in this work for personal or classroom use is granted without interpreting the user’s actual intent. fee provided that copies are not made or distributed for In this paper, we are concerned specifically with the profit or commercial advantage and that copies bear this interpretation of overtracing freehand sketches of notice and the full citation on the first page. To copy geometric objects. Although there are sketch systems otherwise, or republish, to post on servers or to redistribute that support overtracing inputs, they do not actually to lists, requires prior specific permission and/or a fee. interpret them [FIO02a, GRO00a, KAR05a], or Conference proceedings ISBN 80-86943-03-8 provide limited interpretations (e.g., only supports WSCG’2006, January 30-February 3, 2006 certain sketching primitives or has a very strict Plzen, Czech Republic. Copyright UNION Agency – Science Press WSCG2006 Full Papers proceedings 263 ISBN 80-86943-03-8 definition of how a sketch is interpreted) and as such, the availability of hardware such as the stylus tablet, not applicable to general cases [MIT02a, SHE04a]. there are still many problems left to be solved in the Here, we developed a system that supports and development of a full-fledged, functional free-hand interprets overtracing freehand sketch of general sketching calligraphic interface, such as geometric objects (Figure 1). The work presented in interpretation of multiple strokes, in-context this paper is a part of our on-going project that is classification and clustering of strokes, inferring aimed at reconstructing 3D models from 2D constraints from freehand sketches for tidy-up and sketches. The preliminary system is developed to beautification. address the problem of interpreting overtraced Perhaps Pavlidis [PAV85a] made the first attempt to strokes, i.e., multiple strokes that are part of the same infer constraints from initial freehand sketch to geometric primitives. automatically tidy-up rectilinear drawings. However, the method is bound to produce unintended and undesirable results in practice and negative constraints were suggested to address the problem [PAV85a]. Similarly in Easel [JEN92a], Jenkins and Martin developed a system that can automatically analyze and tidy-up sketches. Easel introduced more constraints and processed freeform curves [JEN92a]. Pegasus [IGA98a, IGA97a] is a prototype system for Figure 1: A freehand sketch with overtracing and beautification of freehand sketching through an its tidy-up output from our system. interactive process. The system generates several candidate strokes based on geometry constraints for There are two important differences between our user selection. This interaction process is to ensure system and other earlier, calligraphic interface that the resulting sketch is as closely desired by the systems such as in [MIT02a, SHE04a]. First, our user, i.e., the precise and correct sketch that the user system supports and interprets both straight-line and had in mind but unable to accurately draw himself. curve overtracing sketches. In [SHE04a], the system However, the process of selecting candidates, stroke- can only interpret straight-line input. Second, our by-stroke, is somewhat distracting to the user. system interprets overtracing strokes with various Consequently, the system is not suitable for curvatures and represents them in parametric conceptual design sketching, where the designer equations that best represent the strokes. In must be allowed to sketch without interruption to [MIT02a], the overtracing strokes are represented by ensure a continuous flow of ideas. polylines after grouping into core curves and only In addition to the tidy-up process, there are other curves with low curvatures are showed in their research efforts focused on sketch interpretation examples. problems such as the strokes classification and Furthermore, some of the systems impose frequent clustering. For example, Shpitalni and Lipson interruptions to users during the sketching process. [SHP97a] presented a method for classifying input This is normally associated with interactive systems strokes in an online sketching system that is based on that prompt users for selection of choices [IGA97a]. linear least squares fitting to a conic section equation. The frequent interruptions can be a source of They also introduced new endpoints clustering distractions that can impede the flow of thoughts of scheme based on adaptive tolerances [SHP97a]. Qin the designer, and as such, should be addressed in the [QIN00a] introduced a system that classified strokes design of a calligraphic interface. using adaptive threshold and fuzzy knowledge with Therefore, the interpretation process in our system is respect to curve’s linearity and convexity. After that, carried out automatically and designed to have 2D primitives are identified and a 2D relationship minimum interruption to the user. To achieve this, inference engine is used to study their relationship we designed the system to carry out the interpretation for 3D recognition. process between sketching sessions rather than Although advances have been made in developing a interrupting the user during sketching for further functional calligraphic interface for freehand inputs to clarify ambiguous cases. This allows a user sketching, in general, most of the current 2D to draw in a more intuitive and natural way without freehand sketch interpreters have the limitation of diverting attention from the sketching flow. either not supporting overtracing sketches [JEN92a, IGA98a, IGA97a, PAV85a, QIN00a, QIN00b, 2. RELATED WORKS SHP97a], or have limited support ([SHE4a], Computer calligraphic interface has been receiving [MIT02a]). SMARTPAPER [SHE4a] groups more attention over recent years. However, despite overtracing strokes into segments. The grouping WSCG2006 Full Papers proceedings 264 ISBN 80-86943-03-8 process was carried out in two passes where the 3. SYSTEM OVERVIEW distance between end points and the slopes of the We propose the interpretation of overtracing strokes strokes are checked against each other. However, by carrying out a set of tests automatically to group SMARTPAPER is limited to straight-line input with and tidy up the sketched strokes into segments. The limited configurations only. Furthermore the system output of the system is edge-vertex graph with initial does not support curves input. There is no discussion sketched strokes associated to the edges. The graph of wrongly drawn lines correction and hence it is can be transferred into CAD or 3D modelling assumed that the system is limited to interpret systems for further processing and manipulation sketches with correct strokes. 3D SKETCH while the edges can be reproduced in sketchy style [MIT02a] supports both overtracing and hatching with the sketched strokes information. Another sketch. Strokes are divided into core strokes (strokes advantage to our proposed system is that the new that touch the characteristic curves of the object), and edges that looked similar to the original sketching hatching strokes (strokes that are mapped to the faces style can be produced from the information obtained of the object). Although the system can interpret during the sketching process. However, for this overtracing strokes (e.g., by grouping strokes into paper, we focus only on planar objects and objects bundles), there is no explanation of how the with ellipsoidal curves for inputs to reduce the characteristic strokes are distinguished from the system’s bounds in producing unintended and hatching strokes. Furthermore, the system used undesirable result. Additional work is needed to polylines to represent the core curve limited its extend the system to support the interpretation B- accuracy in representing curves with higher spline curves and freeform objects. curvature. Interruptions such as prompts for clarifying There are other sketch systems that support ambiguous strokes are made at the end of the overtracing strokes but do not interpret them as part drawing session. For example, our system prompts of the sketch. In [GRO00a], the system filters out the user to decide whether an ambiguous stroke overtraced lines to produce simpler, approximated should be deleted or kept with the existing drawing drawings (e.g., filtering out elements that are smaller only at the end of the drawing session. than a specified size) rather than performing The system can take in the sketch directly from the interpretations in the context of the sketch as a user through a tablet with a digital pen or mouse. A whole. In [KAR05a], the sketch recognizer allows stroke is a set of points that is captured during the overtracing symbol recognition based on image period when the mouse button is pressed down, processing techniques, e.g., it relies entirely on the moved, and released. An edge refers to the symbol libraries for the recognition where the sketch intersection of two faces of a solid object, which in is examined in pixel and hence no work is done on 2D drawing is represented by strokes. In many interpretation of individual stroke. In [FIO02a], drawings an edge is often composed of a set of overtracing is used to edit an existing stroke that is discontinuous strokes. The overtracing strokes are represented in cubic Bezier splines. The movements used to complete, correct or enhance an edge in the of oversketching is sampled and interpreted sketch. The strokes will be processed by the 2D specifically as transformation attractor to the sketch interpreter and automatically grouped together underlying curve’s control points. The overtracing to represent the associated edges. strokes are used as gesture input to alter the existing sketch rather than sketching information that actually The 2D sketch interpretation is divided into five add more lines to the existing sketch. stages: grouping and fitting of strokes, end points In this paper, we propose an interactive calligraphic clustering, parallelism correction, in-context interface that addresses the limitations discussed interpretation and user interactive selection. First, all above. Referring to the systems discussed above, we classified strokes (using the linearity test) will be use Qin’s curve classification, Shiptalni and Lipson’s grouped according to their positional relations. After conic fitting equation, and others geometry that, the grouped strokes are fitted collectively into constraints as the backbone of our system to interpret an appropriate parametric equation in the least square and tidy-up freehand sketch. However, stroke pre- sense. A tidied-up sketch will be produced from the processing, i.e., segmentation, is not covered in this equations. Lastly, lines with similar gradients (within paper. All input strokes are taken to represent only a some tolerance levels) are adjusted to be parallel to segment or part of a segment. However, the system each other, thus reflecting the user intention because here can be easily extended to include pre-processing it is not possible for the user to draw exactly parallel algorithms for segmentation such as those described edges in freehand sketch. When there are strokes that in [QIN00b, SEZ01a]. cannot be interpreted correctly according to geometry constraints, the system will tag the strokes as ambiguous cases. The system only prompts the WSCG2006 Full Papers proceedings 265 ISBN 80-86943-03-8 user for further action and correction of the together to represent the same edge. The line ambiguous cases at the end of the drawing session. segments will be grouped together if they are close in After the interpretation process, the system is then position and orientation to each other. able to generate tidied-up 2D single line drawing, 4.2.1.1 Distance Tests while at the same time, still have initial sketchy A series of distance tests is used to determine the strokes linked to the appropriate tidied-up edges. smallest distance between two line segments. The tests are carried out in sequence as follows: 4. CLASSIFITION AND GROUPING 1) Get the smallest Euclidean distances between 4.1 Stroke Classification endpoints of lines A and B (Figure 2). The All drawn strokes will be classified into either one of resulting distance is compared with a threshold the categories, straight-lines or curves. The linearity value. The threshold value represents the largest test is used to classify a straight-line from a curve tolerance of the distance between two line [QIN00a]. It is simpler and faster compared to the segments to be grouped together. The threshold conic curve equation used in [SHP97a]. This is value varies according to the lines’ length, as in because the linearity test involves only a simple [SHP97a]. If the two line segments (A and B) calculation of two parameters, while the conic curve pass the threshold test, go to the angular test, equation requires the calculation of five parameters otherwise go to step 2. in the quadratic equation. 2) Calculate the perpendicular Euclidean distances The linearity is defined as the ratio of the distance from line endpoints of one line to the other line between two endpoints of a stroke to the segment, as shown in Figure 2. Eliminate the accumulative chord length between sequences of distances that corresponding projection points points captured. are out of the other line segment, e.g., (a) and (d) The linearity value is a floating point between zero to in Figure 2. Compare the smallest distance one. A greater linearity value for a stroke indicates among the remains, (b), with a threshold value. that the stroke is more likely to be a straight-line If the distance is smaller than the threshold, go rather than a curve. An ideal straight-line will have to the angular test. Otherwise the two line unity linearity, which rarely happened in freehand segments are grouped into separate edges. sketching. Therefore, we set an arbitrary straight-line e1 tolerance for the classification. A Each classified stroke will be fitted either into a (a) (b) general straight-line equation to generate a straight- (c) (d) s1 s2 line, or a general conic curve equation to generate a curve. With equations, strokes can be represented in B e2 a more general and effective way compared to using a list of points. Furthermore, the representation of Figure 2: Distance calculated between A and B. input strokes with parameterised equations allow for more effective and efficient tests of input strokes 4.2.1.2 Angular Test during the interpretation process. The Angular test is to ensure that strokes grouped as one edge are pointing in the same direction. 4.2 Strokes Grouping and Fitting The absolute dot product value, which is the smallest The strokes grouping process groups sketched angle between the lines A and B, is calculated. The strokes into the appropriate edges that they represent. two lines will be grouped into one segment if the However, the grouping process only tries to group angle is smaller than a threshold value. The threshold strokes in the same category, i.e., lines only grouped value is adjusted according to the longest length of with lines, and curves only grouped with curves. The the lines A and B. The value is calculated to be grouped strokes are fitted with equations to obtain inversely proportional to the length of the parameters that best represent them. corresponding line, e.g. the longer line will have a 4.2.1 Line Segment Grouping and Fitting smaller threshold value. This is because the longer A straight-line is approximated by fitting data points length of lines will “look” more apart than shorter of the strokes into a line equation that give the line with the same angle. minimum least-square error [ONE83a]. The fitted The lines do not have to intersect, or overlap each line end points are the points on the equation that other to be grouped together. The grouped strokes have the minimum Euclidian distance from the will undergo another round of straight-line least- sketched stroke end points. All straight-lines will be square fitting to update its equation and endpoints tested to determine whether they should be grouped (Figure 3). WSCG2006 Full Papers proceedings 266 ISBN 80-86943-03-8
no reviews yet
Please Login to review.