Sage Journals: Discover world-class research

Abstract

A novel method is presented based on fuzzy hybrid-based features to classify strokes into 2D line drawings, and a human computer interactive system is developed for assisting designers in conceptual design stage. Fuzzy classifiers are built based on some geometric features and speed features. The prototype system can support rapid classification based on fuzzy classifiers, and the classified stroke is then fitted with a 2D geometry primitive which could be a line segment, polyline, circle, circular arc, ellipse, elliptical arc, hyperbola, and parabola. The human computer interaction can determine the ambiguous results and then revise the misrecognitions. The test results showed that the proposed method can support online freehand sketching based on conceptual design with no limitation on drawing sequence and direction while achieving a satisfactory interpretation rate.

1. Introduction

Sketching is an effective means of visualizing information, which can convey information and rapidly express creative ideas. Sketching plays a key role in conceptual design process, in which conceptual designers frequently use vague and imprecise geometry to convey information via 2D or 3D sketches. A computer aided conceptual design (CACD) system which is based on the CAD system for the conceptual design with a user friendly interface can permit the geometric specification of these sketches [1] and permit online freehand sketching input [2 –4]. However, conceptual designers still would rather use paper and pencil than operating CAD systems for expression, communication, and recording of novel ideas [5] due to the nonuser friendly interface of the CAD systems [6].

As part of CACD system, sketch recognition interface provides a paper-like interface for users to sketch their ideas [7], and automatically recognize them into line drawing which can seamlessly enter into the computer aided detail design step. Two main methods have been developed to solve the challenges of freehand sketch recognition, that is, (i) gesture-based recognizers and (ii) geometric-based recognizers. The first method only interprets freehand sketches as two-dimensional gestures by using some sketching constraints on the user. And the second method which focuses on the shapes rather than the gestures can interpret input stroke as geometrical shape [8 –10]; to date, this method has obtained more and more attentions [11]. However, these geometric-based recognizers, which just can recognize basic primitives by thresholds and heuristic hierarchies, are not enough for ambiguous sketches. This paper presents a novel method for classifying stroke into geometry primitive based on fuzzy hybrid features. The approach consists of three stages: (i) stroke preprocessing, (ii) fuzzy hybrid-based features classifying, and (iii) human computer interaction. A prototype system, Online Freehand Sketch Recognition (OFSR), was developed successfully. Compared with the other low-level fuzzy recognizers [8, 9], this method displays three outstanding advantages: (i) it returns multiple interpretations when the freehand sketch is very ambiguous, (ii) it is much easier to correct the recognition errors when users find that the recognition result is not right, and (iii) it recognizes more primitives, for example, distinguishing circle from ellipse and circular/elliptical arc from open conic curve.

The paper structure is as follows: Section 2, which follows this introduction, summarizes the related works on online sketch classification models and methods; Section 3 demonstrates the method for classifying sketches; and Section 4 reports the implementation of the algorithm and shows some examples before the conclusion.

2. Related Works

Although more and more researchers reported the application of sketch in CAD modeling [12 –17], these reports focused on the feature recognition by using primitive recognition techniques. The main methods in these reports can be classified into two categories, namely, gesture-based recognition and geometric-based recognition.

The gesture-based recognition method is an active research area in robotics as well as in human computer interaction community [18]. This method typically focuses on how a sketch was drawn rather than on what the final sketch actually looks like. The typical goal of this method is to take an input stroke and classify each one into a set of predefined gestures [19]. In 1991, Rubine [20] firstly proposed thirteen features which could be used to classify simple gestures with an accuracy of 98% on a fifteen-class gesture set when trained with at least fifteen examples per class by using pen-based gesture recognition. But it can only handle single stroke which must be drawn in a predetermined manner. Later, Long et al. [21] extended Rubine's features by decreasing two time-based features and increasing eleven new features. However, these two systems required strokes that are drawn in the same pattern. The ink features were presented in [22]. These feature sets were well designed, but they often troubled user because they need to be extracted by manual entry way. In a word, this approach used mathematical sound classifiers to produce fast classification along with normalized confidence value, but this method required individual training to give good recognition result. In addition, this method displays sensitivity to change in scale and rotation.

Due to the limitations of gesture-based recognition as described previously, a shift has occurred towards more geometric-based recognition [8 –10]. For this reason, more and more single stroke recognition systems have been developed that do not use gesture-based approach but, rather, use geometric attributes to classify stroke in basic primitive [8 –10]. This method has been used to describe shapes geometrically, focusing on what the sketch looks like and less on how it was actually drawn. This method includes two systems: (i) low-level system and (ii) high-level system.

In low-level system, the strokes are segmented into various primitives such as straight line and circle, which can be used to produce higher-level shapes. Yu and Cai [9] presented an alternative low-level sketch recognition. They introduced a feature area error metric and achieved near 98% accuracy. Sezgin et al. [8] reported an interesting work which focused on the low-level geometric descriptions by using scale space theory. They claimed that this theory looks like a promising way of detecting different scales inherent in the data and avoiding a priori judgments about the size of relevant features. The system was limited to only a few primitive shapes: lines, ellipses, and complex fits. For complex fits and vertex (corner) approximation, the authors reported an accuracy of 96%.

Typically, diagrams and sketches consist of symbols that are more complex than the primitives supported by these recognizers. Therefore, tools such as LADDER [23] have been created which allow users to describe higher-level symbols as a combination of lower level primitives meeting certain geometric constraints. UML diagrams, mechanical engineering diagrams, circuit diagrams, military course of action diagrams, and flow charts are all examples of various sketch systems that have been produced by using this shape definition language. However, it will be very difficult to define geometrical shape by using this method. Avola et al. [24] proposed a method to handle ambiguous strokes by introducing the spatial and temporal information that represent the user's sketching, editing, and overtracing process. This method allows users to sketch in free manner without any sketching constraints. However, their method just focused on the ambiguity interpretation of the few geometrical elements including point, polyline, and polygon. Furthermore, the recognition accuracy was not very high except for a specific domain.

Comparing gesture-based methods with geometric-based methods, because the latter recognize a stroke to an ideal primitive using geometric formula, it is more natural, where the user can be allowed to draw without interruption to ensure a continuous flow of ideas. However, some of the present geometric-based methods just consider the geometry features and just blend the speed features. Some of them adopt a set of related fixed thresholds and are short of human computer interaction for ambiguous results and revising misrecognition.

3. New Methods

The OFSR system for the sketch classification process is shown in Figure 1. The geometry primitives (e.g., line segment, polyline, ellipse, etc.) can be recognized in the OFSR system. The classification method is based on four procedures, namely, (i) remove of redundant points in the stroke preprocessing, (ii) detection of shapes by using distinctive criteria that are based on hybrid features, (iii) determination of membership degree by using fuzzy logic to recognize primitives, and (iv) development of HCI tool for determining recognition results and revising misrecognition. Therefore, it allows recognition indeterminacy or error to be easily corrected or determined by the users through a simple click which could be used to switch to a human computer interaction.

Figure 1:

Process of classification based on fuzzy hybrid features.

3.1. Stroke Preprocessing

In the OFSR system, a stroke is defined as a sequence of mouse positions which is obtained from pressing a button, moving the mouse while the button is still pressed, and releasing it. The split and merge algorithm of polygonal approximation is used to represent a stroke by an approximate polygon. The algorithm depends on a given threshold which is expressed by a measure function as described in [25]. Assuming a stroke is represented by a sequence of sampling points {P_i = (x_i, y_i, t_i); 0 ≤ i ≤ n}, where P_i is the coordinate and time of the ith point in the sampling list. The distance of any point (x_i, y_i) from the line segment consisting of two endpoints is

d_{i} = \frac{(y_{n} - y_{0}) x_{i} + (x_{0} - x_{n}) y_{i} + (x_{n} y_{0} - x_{0} y_{n})}{\sqrt{{(x_{n} - x_{0})}^{2} + {(y_{n} - y_{0})}^{2}}} .

(1)

The sign of d_i can be used to compute the deflected times from line segment between the first point and the last point. The normalized maximum absolute error is

∊ = \frac{\max_{i} | d_{i} |}{\sqrt{{(x_{n} - x_{0})}^{2} + {(y_{n} - y_{0})}^{2}}} .

(2)

The stroke is represented initially as a line segment between the first and last points which were labeled as v₀ and v₁, respectively (see Figure 2(a)). The farthest point from the straight line (v₀v₁) can be determined by (1). If the normalized maximum error (∊) is above a threshold, then the initial stroke will be represented as a polyline (v₀v₁v₂), as shown in Figure 2(b). Then, the splitting algorithm is used recursively to calculate both of the line segments (v₀v₁, v₁v₂). The splitting algorithm will terminate when the normalized maximum error (∊), for all sampling points along the polyline, is less than the threshold (∊_z).

Figure 2:

Split and merge method for an approximate polygon.

In the stroke preprocessing step, a sequence of vertices {v_i; 0 ≤ i ≤ u ≤ n} with drawing position and time can be obtained. The vertices are linked orderly to create a polyline which can represent the stroke. The vertices and the polyline are defined as polygon vertices and an approximate polygon, respectively.

3.2. Fuzzy Feature Detection

In order to solve the problems of imprecision and uncertainty when sketching by using the traditional method, in the OFSR system, fuzzy logic is used to determine the degree of membership for classifying strokes, which is a more natural method of handling ambiguities.

3.2.1. Fuzzy Logic

The selection of fuzzy membership functions is a key step in this process, and the functions should meet two requirements: (i) reflecting users' intention correctly and precisely and (ii) high computational efficiency [26]. Three frequent triangular membership functions are shown in Figure 3.

Figure 3:

Definition of membership function.

Consider

u (x : s_{l}, a, s_{r}) = {\begin{cases} 1 + \frac{x - a}{s_{l}}, & a - s_{l} \leq x \leq a, \\ 0, & others, \\ 1 - \frac{x - a}{s_{r}}, & a < x \leq a + s_{r} . \end{cases}

(3)

In this paper, a general membership function is defined as depicted in (3) with three scalar parameters s_l, a, and s_r, which can, respectively, represent the special triangular membership functions u₁(x), normal triangular u₂(x), and u₃(x), as shown in Figure 3. These functions are shown in (4), respectively

\begin{matrix} u_{1} (x) = u (x : + \infty, a - s_{l}, s_{l}), \\ u_{2} (x) = u (x : s_{l}, a, s_{r}), \\ u_{3} (x) = u (x : s_{r}, a + s_{r}, + \infty) . \end{matrix}

(4)

A stroke is classified by computing their degrees of membership. Each geometry primitive is defined by several fuzzy sets which do nothave the same number of features for all primitives.

3.2.2. Fuzzy Feature

In our OFSR system, each classified stroke will be fitted into a corresponding conic curve (see (5)) by least median squares method. The open/closed classifier is used, which was detailed in [11] to detect open or closed when the stroke is in the conic section. This method permits users to draw a stroke by any direction of rotation. A closed conic can be circle or ellipse; otherwise it can be circular arc, elliptical arc, hyperbola, and parabola.

Consider

q (x, y) = a x^{2} + b x y + c y^{2} + d x + e y + f .

(5)

(1) Open/Closed Detection. Suppose a stroke is represented by a sequence of vertices {v_i; 0 ≤ i ≤ u} with drawing position and drawing time. The open/closed detecting method is designed for determining open or closed when the stroke is a conic section. Firstly, the mass center o(x_o, y_o) of the stroke is calculated. Linking the mass center to the vertex v_i accordingly, a sequence of radius vectors, ${\bar{o} {\bar{v}}_{i}, 0 \leq i \leq u}$ , is built. In light of whether the cross product directions of all neighboring vectors are coincident, we can classify whether the stroke is conic section or not. If it is a possible conic curve, we calculate the circumferential angle θ_i between two adjacent radii in clockwise (positive value) and anticlockwise (negative values). A sequence of the corresponding circumferential angles is represented as {θ_i; 0 ≤ i ≤ u – 1}. Define the sum of all circumferential angles as the rotation angle of this stroke. Comparing this rotation angle with the rotation angle 2π of the closing conic curve, we can estimate easily whether the stroke is open or closed.

(2) Fitting Error Detection. By employing least median squares method [15] to fit the polygon vertices of a stroke to a conic curve in (5), we can get a series of constructed functions of fitting error detection. The mean absolute error is calculated as follow:

\bar{∊} = \frac{1}{u + 1} \sum_{i = 0}^{u} | q (v_{i}) | .

(6)

Equation (7) is the standardized error measurement function with the stroke length L:

∊_{e} = \frac{\bar{∊}}{L} .

(7)

The measurement function of maximum absolute value is described as

∊_{\max} = \max {| q (v_{i}) |; 0 \leq i \leq u} .

(8)

The membership functions of the aforementioned measurement functions for standardized error and maximum absolute value can be constructed by triangular membership function.

(3) Subdivision of Conic Curve. When a stroke is classified as conic curve, OFSR system will determine the details deeply. The invariants of conic section are used to filter the detail categories. For example, I2 can be used to determine the stroke which belongs to ellipse, hyperbola, or parabola. If the stroke is ellipse type, it will be segmented into closed (ellipse, circle) and open (ellipse arc, arc) by the aforementioned open/closed detection.

3.3. Hybrid-Based Classifiers

After drawing a new stroke, obtaining the polygon vertices by stroke preprocessing, a set of approximation features are calculated, such as first/last points, stroke length, enclosing rectangle of the stroke, and speed features. Each primitive employs various classifiers. Next, we exemplify how to develop hybrid-based classifiers for sketch recognition.

(1) Line-Segment Classifier. We classify line segment by comparing the length (h) and its width (w) of the minimum enclosure rectangle. The w/h ratio will have values near 0 for line segment and near 1 for other geometry primitives. It ascertains that very slim stroke should be recognized as line segment.

(2) Polyline Classifier. For the polyline classifier, the stroke is broken into sub-strokes by the polygon vertices. First, a least median squares line is fitted to sub-stroke sampling points. The orthogonal average distance (OAD) between the fitted line and the sub-stroke sampling points is calculated, which is similar to the [27]. Second, the sum of orthogonal average distances for every sub-stroke is divided by the stroke length, which is defined as the least median squares error ∊_e for the polyline fitting which must be below a certain threshold k_z.

(3) Conic Section Classifier. Through the experiment analysis in the OFSR system, the membership functions of conic curve based on hybrid features are related to some aforementioned classifiers. The membership functions of conic section are different for open/closed strokes.

3.4. Classification with Human Interaction

In our OFSR system, a human computer interactive dialog is developed for determining the ambiguous recognition result and revising misrecognition, as shown in Figure 4. On the one hand, it is designed for resolving the indeterminacy by interaction with the users. In this OFSR system, whenever the fuzzy classifiers return more than one geometry primitive, in other word, whenever there are at least two values in all membership degree values close to 1, as a result, this OFSR system displays a dialog in which all possibilities are activated (see Figure 5(a)), allowing the user to choose their intentions by themselves.

Figure 4:

Human interactive dialogs.

Figure 5:

Examples of single stroke recognition.

On the other hand, it is designed for correcting the error recognition result. If the user finds that the recognition result is not in accordance with their intentions, the wrong result can be corrected easily by moving the mouse near the stroke. The user just needs to the click right-hand button of the mouse to activate the dialog of human computer interaction, as shown in Figure 5(b). This interactive method makes the stroke recognition easier and eliminates the need to redraw the sketch for the desired result.

4. Implementation and Examples

This OFSR system has been implemented on Windows XP by using Visual C++. This input sketch interface of OFSR system allows the user to sketch freely as though using pencil and paper. The input device is a computer mouse. The system interprets the strokes into geometry primitives, if the results are ambiguous, OFSR system will need the users to say the last word, as shown in Figure 5(c).

This OFSR system has been tested in many fields such as 2D/3D engineering drawing, flow chart, and statistical diagram, and some examples of them are shown in Figure 6. The first column shows the original sketches in different colors to indicate the difference strokes; the second column gives the comparisons of input sketches and recognition results; the recognition results are shown in the third column, which has consisted of 2D line drawings. The results show that the OFSR system can interpret users' freehand single strokes into 2D line drawing correctly and effectively.

Figure 6:

Examples of the application in different fields.

The OFSR system has been tested for 3D reconstruction from freehand sketches with several examples and some of them are shown in Figure 7. Figure 7(a) shows the original sketches, and Figure 7(b) gives the results of elementary recognitions. The endpoint clustering result and 3D reconstruction result are shown in Figures 7(c) and 7(d), respectively. Figure 7(e) is the recovered 3D model from the freehand sketches.

Figure 7:

Examples of 3D reconstruction from freehand sketches.

This system gives users greater freedom to quickly specify 2D/3D geometry through 2D drawing and can encourage users with poor sketching skills to use it for a creative design task. Table 1 gives the statistical result of freehand sketch recognition. It can be inferred from the statistical data, before the human computer interaction, that recognition rates are all more than 97% except for hyperbolas and parabolas. The recognition rate can receive apparent improvement after the human computer interaction, especially the hyperbolas and parabolas.

Table 1:

Statistical result of freehand sketch recognition.

Target sketches	Straight line	Overtraced line	Polygon	Circle (arc)	Ellipse (arc)	Overtraced ellipse	Overtraced circle	Hyperbola	Parabola

Drawing times	118	100	46	119	76	70	47	30	30
Before HCI
Recognition rate %	1.0	1.0	0.978	0.983	0.974	0.986	0.979	0.8	0.6
After HCI
Recognition rate %	/	/	1.0	0.992	0.987	1.0	1.0	1.0	1.0

5. Conclusion

This paper presents a novel stroke fuzzy classification method based on hybrid features to interpret sketches into line drawing for low-level recognition, which is aimed to enable the user to use it easily and intuitively. The OFSR system developed is capable of classifying eight primitive shapes including line segment, polyline, circle, circular arc, ellipse, elliptical arc, hyperbola, and parabola. The proposed method is suitable for online freehand sketching. It can easily correct the recognition errors and determining the recognition result by activating a dialog of human computer interaction. Furthermore, through the integration of our researches into the high-level sketch recognition system, we are developing interpretations system for fitting overtraced strokes [27]. The work presented here is only a part of our final sketched-based 3D modeling system. The future work is to improve the endpoint clustering method and reconstruct a 2D line drawing to 3D model.

Footnotes

Acknowledgment

This work was partly supported by National Natural Science Foundation of China (Grant no. 51105310).

References

Serré

Ortuzar

, and Rivière

, “Non-cartesian modelling for analysis of the consistency of a geometric specification for conceptual design,” International Journal of Computational Geometry and Applications, vol. 16, no. 5–6, pp. 549–565, 2006.

Lipson

and Shpitalni

, “Optimization-based reconstruction of a 3D object from a single freehand line drawing,” CAD Computer Aided Design, vol. 28, no. 8, pp. 651–663, 1996.

Eggli

Hsu

C.-Y.

Brüderlin

B. D.

, and Elber

, “Inferring 3D models from freehand sketches and constraints,” CAD Computer Aided Design, vol. 29, no. 2, pp. 101–112, 1997.

Qin

S.-F.

Wright

D. K.

, and Jordanov

I. N.

, “A conceptual design tool: a sketch and fuzzy logic based system,” Proceedings of the Institution of Mechanical Engineers B, vol. 215, no. 1, pp. 111–116, 2001.

Lim

Qin

S. F.

Prieto

Wright

, and Shackleton

, “A study of sketching behaviour to support free-form surface modelling from on-line sketching,” Design Studies, vol. 25, no. 4, pp. 393–413, 2004.

Qin

S. F.

Wright

D. K.

, and Jordanov

I. N.

, “From on-line sketching to 2D and 3D geometry: a system based on fuzzy knowledge,” CAD Computer Aided Design, vol. 32, no. 14, pp. 851–866, 2000.

Costagliola

Hammond

, and Plimmer

, “JVLC special issue on sketch computation,” Journal of Visual Languages and Computing, vol. 21, no. 2, pp. 67–68, 2010.

Sezgin

T. M.

Stahovich

, and Davis

, “Sketch based interfaces: early processing for sketch understanding,” in Proceedings of the 33rd International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '07), Boston, Mass, USA, August 2007.

and Cai

, “A domain-independent system for sketch recognition,” in Proceedings of the 1st International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia (GRAPHITE '03), pp. 141–146, February 2003.

10.

Paulson

and Hammond

, “PaleoSketch: accurate primitive sketch recognition and beautification,” in Proceedings of the 13th International Conference on Intelligent User Interfaces (IUI '08), pp. 1–10, January 2008.

11.

Bae

S. H.

Kim

W. S.

, and Kwon

E. S.

, “Digital styling for designers: sketch emulation in computer environment,” in Computational Science and Its Applications, vol. 2669 of Lecture Notes in Computer Science, pp. 690–700, Springer, Berlin, Germany, 2003.

12.

Pugh

, “Designing solid objects using interactive sketch interpretation,” in Proceedings of the Symposium on Interactive 3D graphics, pp. 117–126, ACM, 1992.

13.

Donikian

and Hégron

, “A declarative design method for 3d scene sketch modeling,” in Proceedings of the Computer Graphics Forum, pp. 223–236, Wiley Online Library, 1993.

14.

Bloomenthal

Zeleznik

Fish

, “Sketch-N-Make: automated machining of CAD sketches,” in Proceedings of the International Design Engineering Technical Conferences (IDETC '98), pp. 1–11, ASME, 1998.

15.

Lou

, and Ramani

, “A 2D sketch-based user interface for 3D CAD model retrieval,” Computer-Aided Design and Applications, vol. 2, no. 6, pp. 717–725, 2005.

16.

Ijiri

Owada

, and Igarashi

, “The sketch l-system: global control of tree modeling using free-form strokes,” in Smart Graphics, vol. 4073 of Lecture Notes in Computer Science, pp. 138–146, Springer, Berlin, Germany, 2006.

17.

Olsen

Samavati

F. F.

Sousa

M. C.

, and Jorge

J. A.

, “Sketch-based modeling: a survey,” Computers and Graphics, vol. 33, no. 1, pp. 85–103, 2009.

18.

Basçetinçelik

, WiiRobot: Controlling Robots With Wii Gestures, Department of Computer Science Brown University, Providence, RI, USA, 2009.

19.

Paulson

Rajan

Davalos

Gutierrez-Osuna

, and Hammond

, “What!?! no Rubine features? using geometric-based features to produce normalized confidence values for sketch recognition,” in Proceedings of the VL/HCC Workshop: Sketch Tools for Diagramming, pp. 57–63, IEEE, Herrsching am Ammersee, Germany, 2008.

20.

Rubine

, “Specifying gestures by example,” in Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques, pp. 329–337, ACM, 1991.

21.

Long

A. C.

Jr. Landay

J. A.

Rowe

L. A.

, and Michiels

, “Visual similarity of pen gestures,” in Proceedings of the Conference on Human Factors in Computing Systems (CHI '00), pp. 360–367, April 2000.

22.

Patel

Plimmer

Grundy

, and Ihaka

, “Ink features for diagram recognition,” in Proceedings of the Sketch-Based Interfaces and Modeling, ACM SIGGRAPH/Eurographics Symposium, pp. 131–138, August 2007.

23.

Hammond

and Davis

, “LADDER, a sketching language for user interface developers,” Computers and Graphics, vol. 29, no. 4, pp. 518–532, 2005.

24.

Avola

Caschera

M. C.

Ferri

, and Grifoni

, “Classifying and resolving ambiguities in sketch-based interaction,” International Journal of Virtual Technology and Multimedia, vol. 1, pp. 104–139, 2010.

25.

Wang

Gao

, and Qi

, “Freehand sketching interfaces: early processing for sketch recognition,” in Human-Computer Interaction. Interaction Platforms and Techniques, vol. 4551 of Lecture Notes in Computer Science, pp. 161–170, Springer, Berlin, Germany, 2007.

26.

Chen

C. L. P.

and Xie

, “Freehand drawing system using a fuzzy logic concept,” CAD Computer Aided Design, vol. 28, no. 2, pp. 77–89, 1996.

27.

Wang

Chen

Geng

, and Deng

, “Customer participating 3D garment design for mass personalization,” Textile Research Journal, vol. 81, no. 2, pp. 187–204, 2011.

Using Fuzzy Hybrid Features to Classify Strokes in Interactive Sketches

Abstract

1. Introduction

2. Related Works

3. New Methods

3.1. Stroke Preprocessing

3.2. Fuzzy Feature Detection

3.2.1. Fuzzy Logic

3.2.2. Fuzzy Feature

3.3. Hybrid-Based Classifiers

3.4. Classification with Human Interaction

4. Implementation and Examples

5. Conclusion

Footnotes

Acknowledgment

References