Filetype PDF | Posted on 16 Sep 2022 | 3 years ago
Authentication
digital resources
150x 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.
