logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 5: 052105(2019) https://doi.org/10.1007/s11432-018-9694-8

Sketch simplification guided by complex agglomeration

More info
  • ReceivedAug 13, 2018
  • AcceptedSep 30, 2018
  • PublishedApr 2, 2019

Abstract

We propose a novel method for vector sketch simplification based on the simplification of the geometric structure that is extracted from the input vector graph, which can be referred to as a base complex. Unlike the sets of strokes, which are treated in the existing approaches, a base complex is considered to be a collection of various geometric primitives. Guided by the shape similarity metrics that are defined for the base complex, an agglomeration procedure is proposed to simplify the base complex by iteratively merging a pair of geometric primitives that exhibit the minimum cost into a new one. This simplified base complex is finally converted into a simplified vector graph.Our algorithm is computationally efficient and is able to retain a large amount of useful shape information from the original vector graph, thereby achieving a tradeoff between efficiency and geometric fidelity. Furthermore, the level of simplification of the input vector graph can be easily controlled using a single threshold in our method. We make comparisons with some existing methods using the datasets that have been provided in the corresponding studies as well as using different styles of sketches drawn by artists. Thus, our experiments demonstrate the computational efficiency of our method and its capability for producing the desirable results.


Acknowledgment

This work was partly supported by National Natural Science Foundation of China (Grant Nos. 61572292, 6160227, 61672187), NSFC Joint Fund with Guangdong (Grant No. U1609218), and Shandong Provincial Key Research and Development Project (Grant No. 2018GGX103038).


References

[1] Barla P, Thollot J, Sillion F X. Geometric clustering for line drawing simplification. In: Proceedings of the 16th Eurographics Conference on Rendering Techniques, 2005. 183--192. Google Scholar

[2] Liu X, Wong T T, Heng P A. Closure-aware sketch simplification. ACM Trans Graph, 2015, 34: 1-10 CrossRef Google Scholar

[3] Shesh A, Chen B. Efficient and Dynamic Simplification of Line Drawings. Comput Graphics Forum, 2008, 27: 537-545 CrossRef Google Scholar

[4] Grabli S, Durand F, Sillion F X. Density measure for line-drawing simplification. In: Proceedings of the 12th Pacific Conference on Computer Graphics and Applications, 2004. 309--318. Google Scholar

[5] Pusch R, Samavati F, Nasri A. Improving the sketch-based interface. Visual Comput, 2007, 23: 955-962 CrossRef Google Scholar

[6] Orbay G, Kara L B. Beautification of Design Sketches Using Trainable Stroke Clustering and Curve Fitting.. IEEE Trans Visual Comput Graphics, 2011, 17: 694-708 CrossRef PubMed Google Scholar

[7] Ogawa T, Matsui Y, Yamasaki T, et al. Sketch simplification by classifying strokes. In: Proceedings of the International Conference on Pattern Recognition, 2016. 1065--1070. Google Scholar

[8] Simo-Serra E, Iizuka S, Sasaki K. Learning to simplify. ACM Trans Graph, 2016, 35: 1-11 CrossRef Google Scholar

[9] Bartolo A, Camilleri K P, Fabri S G, et al. Scribbles to vectors: preparation of scribble drawings for CAD interpretation. In: Proceedings of the 4th Eurographics Workshop on Sketch-Based Interfaces and Modeling, 2007. 123--130. Google Scholar

[10] Favreau J D, Lafarge F, Bousseau A. Fidelity vs. simplicity. ACM Trans Graph, 2016, 35: 1-10 CrossRef Google Scholar

[11] Parakkat A D, Bondi Pundarikaksha U, Muthuganapathy R. A Delaunay triangulation based approach for cleaning rough sketches. Comput Graphics, 2018, 74: 171-181 CrossRef Google Scholar

[12] Zou J J, Yan H. Cartoon image vectorization based on shape subdivision. In: Proceedings of the International Computer Graphics, 2001. 225--231. Google Scholar

[13] Bo P, Luo G, Wang K. A graph-based method for fitting planar B-spline curves with intersections. J Comput Des Eng, 2016, 3: 14-23 CrossRef Google Scholar

[14] Wang Y T, Wang L Y, Deng Z G, et al. Sketch-based shape-preserving tree animations. In: Proceedings of the Computer Animation and Social Agents, 2018. Google Scholar

[15] Guo X K, Lin J C, Xu K, et al. CustomCut: on-demand extraction of customized 3D parts with 2D sketches. In: Proceeding of the Eurographics Symposium on Geometry Processing, 2016. Google Scholar

[16] Shesh A, Chen B. Smartpaper: an interactive and user friendly sketching system. In: Proceedings of the Computer Graphics Forum, 2004. Google Scholar

[17] Ku D C, Qin S F, Wright D K. Interpretation of overtracing freehand sketching for geometric shapes. In: Proceedings of the Computer Graphics, Visualization and Computer Vision, 2006. 263--270. Google Scholar

[18] Schmidt R, Wyvill B, Sousa M C, et al. Shapeshop: sketch-based solid modeling with blobtrees. In: Proceedings of the ACM SIGGRAPH, San Diego, 2007. Google Scholar

[19] Bae S H, Balakrishnan R, Singh K. ILoveSketch: as-natural-as-possible sketching system for creating 3D curve models. In: Proceedings of the ACM Symposium on User Interface Software and Technology, 2008. 151--160. Google Scholar

[20] Grimm C, Joshi P. Just DrawIt: a 3D sketching system. In: Proceedings of the International Symposium on Sketch-Based Interfaces and Modeling, 2012. 121--130. Google Scholar

[21] Schroeder W J, Zarge J A, Lorensen W E. Decimation of triangle meshes. In: Proceedings of the ACM Siggraph Computer Graphics, 1992. 65--70. Google Scholar

[22] Hoppe H, DeRose T, Duchamp T, et al. Mesh optimization. In: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, 1993. 19--26. Google Scholar

[23] Guéziec A. Surface simplification with variable tolerance. In: Proceedings of the 2nd International Symposium on Medical Robotics and Computer Assisted Surgery, 1995. 132--139. Google Scholar

[24] Garland M, Heckbert P S. Surface simplification using quadric error metrics. In: Proceedings of the 24th International Conference on Computer Graphics and Interactive Techniques, 1997. 209--216. Google Scholar

[25] Cohen J, Manocha D, Olano M. Simplifying polygonal models using successive mappings. In: Proceedings of the Conference on Visualization, 1997. 395--402. Google Scholar

[26] Kobbelt L, Campagna S, Seidel H P. A general framework for mesh decimation. In: Proceedings of the Graphics Interface Conference, 1998. 43--50. Google Scholar

[27] Hoppe H. View-dependent refinement of progressive meshes. In: Proceedings of the 24th International Conference on Computer Graphics and Interactive Techniques, 1997. 189--198. Google Scholar

[28] Tarini M, Puppo E, Panozzo D. Simple quad domains for field aligned mesh parametrization. ACM Trans Graph, 2011, 30: 1 CrossRef Google Scholar

[29] Gao X, Deng Z, Chen G. Hexahedral mesh re-parameterization from aligned base-complex. ACM Trans Graph, 2015, 34: 142:1-142:10 CrossRef Google Scholar

[30] Noris G, Hornung A, Sumner R W. Topology-driven vectorization of clean line drawings. ACM Trans Graph, 2013, 32: 1-11 CrossRef Google Scholar

[31] Kauppinen H, Seppanen T, Pietikainen M. An experimental comparison of autoregressive and Fourier-based descriptors in 2D shape classification. IEEE Trans Pattern Anal Machine Intell, 1995, 17: 201-207 CrossRef Google Scholar

[32] Loncaric S. A survey of shape analysis techniques. Pattern Recognition, 1998, 31: 983-1001 CrossRef Google Scholar

[33] Zhang D S, Lu G J. A comparative study on shape retrieval using Fourier descriptors with different shape signatures. In: Proceedings of Asian Conference on Computer Vision, 2002. Google Scholar

[34] Zhang D, Lu G. Study and evaluation of different Fourier methods for image retrieval. Image Vision Computing, 2005, 23: 33-49 CrossRef Google Scholar

[35] Glassner A. Graphics Gems. Orlando: Academic Press, 1990. Google Scholar

[36] El-ghazal A, Basir O, Belkasim S. Farthest point distance: A new shape signature for Fourier descriptors. Signal Processing-Image Communication, 2009, 24: 572-586 CrossRef Google Scholar

[37] Durand F. Where do people draw lines?. Commun ACM, 2012, 55: 106 CrossRef Google Scholar

  • Figure 1

    (Color online) (a) Drawing a triangle with seven strokes; (b) the base complex of (a) comprises black curves, red nodes, and differently colored patches; (c) the largest blue patch in (b) is a polygon surrounded by dense boundary points.

  • Figure 2

    (Color online) (a) Input vector sketch; (b) base complex of the input vector graph containing nodes, curves, and patches; (c) simplified result obtained after merging pairs of primitives under the constraint of shape similarity measurements; (d) two types of unsmoothing cases are marked in red boxes; one is the curve confusion at an intersection, the other is a zigzag shape; (e) the obtained simplified graph.

  • Figure 3

    (Color online) (a) Simple input vector graph; (b) intersections between various strokes are shown as red dots; (c) base complex extracted from (a), where the patches are set in different colors; the black solid lines show the open curves; the black dotted lines show the closed curves, and nodes are represented as red dots.

  • Figure 4

    (Color online) (a) Contour of a triangle and its central point; (b) periodic function $R(t)$ of the triangle created using 256 sampling points on the contour in (a). The horizontal axis indicates the sampling points, whereas the vertical axis indicates the distance from the sampling point to the central point.

  • Figure 5

    (Color online) (a) Input vector graph; (b) the red patch has a common edge with the green patch, so that they can be paired; (c) a new patch is obtained after the patch-patch merging. The public edge of the two patches is marked by a blue dashed line.

  • Figure 6

    (Color online) (a) Input vector graph; (b) the point A is the common point of the curve ${O_{l}}$ and the patch ${O_{p}}$. The blue dashed curve is the affected edge ${E_{\rm~AB}}$ on ${O_{p}}$, and ${E_{\rm~AB}}$ is expanded outwards because of ${O_{l}}$.

  • Figure 7

    (Color online) Two representative cases of a curve-curve pair merging, where (a)–(d) present the merging process of two broken curves and (e)–(h) present the merging process of two overlapped curves. Both the processes are achieved by fitting the two nearest line segments into a Bézier curve and then connecting the remaining line segments to create a new curve.

  • Figure 8

    (Color online) The initial base complex (a), one part on detail (b) and its simplified base complex (c).

  • Figure 9

    (Color online) Border patch.

  • Figure 10

    (Color online) (a) Vertices $v_0$–$v_5$ are vertices of the first type, each with a degree larger than 2. The edge ${e_{03}}$ is adjacent to both the patch ${O_{p1}}$ and ${O_{p2}}$, whereas the other edges are only adjacent to one patch. (b) Vertex ${v_2}$ is an auxiliary vertex added to the blue patch, and it belongs to the second type of vertices. (c) Vertex ${v_1}$ is of the third type.

  • Figure 11

    (Color online) (a) The leftmost picture depicts the result of merging simplification. The zigzag curve problem is presented in more detail on the right, where the short edge ${e_{ij}}$ is marked in red. The edge ${e_{ij}}$ and both of its two neighboring edges (${e_{ki}}$ and ${e_{jh}}$) that are found using one of the adjacent patches ${O_{p1}}$ and ${O_{p2}}$. The edges ${e_{ki}}$ and ${e_{jh}}$ can be merged into a new curve by curve-curve merging. (b) Details of the curve confusion problem at a junction. The short edge ${e_{ij}}$ located on the confusion junction is marked in red. Two valid curve pairs ${e_{ki}}$ ${e_{jn}}$ and ${e_{jh}}$ ${e_{mi}}$ are merged into the corresponding new curves.

  • Figure 12

    (Color online) (a) Eight lines are drawn from right to left with a progressive increase in the bend angle;protect łinebreak (b) shape similarities of the lines.

  • Figure 13

    (Color online) Graphs in the first row are input sketches. Their simplified versions are shown in the second row.

  • Figure 14

    (Color online) (a) Input sketch of a girl, where the red rectangle denotes an example area of region detection; (b) patches in the base complex of our method; (c) initial over-segmented regions obtained by “trapped ball" method in [2].

  • Figure 15

    The graphs in the first row are the input sketches, where (a) is obtained from [1], (b) and (c) from [6], (d) and (e) from [2], and (f) is a vector graph simulated from [8]. The second row shows the results of the compared methods, and the third row presents the results of our method.

  • Figure 16

    (Color online) (a) Input sketches; (b) outputs of our method; (c) output of the method from [10]in the first row and that of the method from [2]in the second row. The parameter options of [10], i.e., the maximal number of open curves, the minimal length of open curves, and the minimal region size, are set to 12, 10, and 7, respectively.

  • Figure 17

    (Color online) Six results obtained using a different simplification degree (from weak to strong) of the [8]online demonstration. The final graph is the result of our method. Despite minor deviations in the sequence, the part highlighted by the red rectangle is not simplified as accurately as in the result of our method. The blue dots show the topological nodes.

  • Figure 18

    (Color online) (a) Initial base complex, containing 198 patches and 176 curves; (b) by setting ${\varepsilon=0.015}$, we obtain a simplified base complex with 28 patches and 15 curves; (c) by setting ${\varepsilon=0.05}$, we obtain a simplified base complex with 8 patches and 11 curves. The nose and an ear of the squirrel are merged into the neighboring patch, which does not occur in (b).

  • Figure 19

    (Color online) (a) By setting $N=128$ and ${\varepsilon=0.015}$, 41 patches and 16 curves remaine in the base complex after merging; (b) by setting $N=1024$ and ${\varepsilon=0.015}$, 23 patches and 14 curves remaine in the base complex after merging.

  • Table 1   Parameter settings and running time
    Input $\varepsilon$ $\alpha$ Time (s)
    a0.0180.0126.332
    b0.0250.0128.118
    c0.0130.0127.652
    d0.0140.0123.488
    e0.0140.0135.085
    f0.0150.0121.317

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号