Sketch simplification guided by complex agglomeration
|
摘要
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.
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.
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.
引文
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
2 Liu X,Wong T T,Heng P A.Closure-aware sketch simplification.ACM Trans Graph,2015,34:1-10
3 Shesh A,Chen B Q.Efficient and dynamic simplification of line drawings.Comput Graph Forum,2008,27:537-545
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
5 Pusch R,Samavati F,Nasri A,et al.Improving the sketch-based interface.Visual Comput,2007,23:955-962
6 Orbay G,Kara L B.Beautification of design sketches using trainable stroke clustering and curve fitting.IEEE Trans Visual Comput Graph,2011,17:694-708
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
8 Simo-Serra E,Iizuka S,Sasaki K,et al.Learning to simplify:fully convolutional networks for rough sketch cleanup.ACM Trans Graph,2016,35:1-11
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
10 Favreau J D,Lafarge F,Bousseau A.Fidelity vs.simplicity:a global approach to line drawing vectorization.ACMTrans Graph,2016,35:1-10
11 Parakkat A D,Pundarikaksha U B,Muthuganapathy R.A Delaunay triangulation based approach for cleaning rough sketches.Comput Graph,2018,74:171-181
12 Zou J J,Yan H.Cartoon image vectorization based on shape subdivision.In:Proceedings of the International Computer Graphics,2001.225-231
13 Bo P B,Luo G N,Wang K Q.A graph-based method for fitting planar B-spline curves with intersections.J Comput Des Eng,2016,3:14-23
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
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
16 Shesh A,Chen B.Smartpaper:an interactive and user friendly sketching system.In:Proceedings of the Computer Graphics Forum,2004
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
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
19 Bae S H,Balakrishnan R,Singh K.ILove Sketch: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
20 Grimm C,Joshi P.Just DrawIt:a 3D sketching system.In:Proceedings of the International Symposium on SketchBased Interfaces and Modeling,2012.121-130
21 Schroeder W J,Zarge J A,Lorensen W E.Decimation of triangle meshes.In:Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques,1992.65-70
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
23 Gu′eziec A.Surface simplification with variable tolerance.In:Proceedings of the 2nd International Symposium on Medical Robotics and Computer Assisted Surgery,1995.132-139
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
25 Cohen J,Manocha D,Olano M.Simplifying polygonal models using successive mappings.In:Proceedings of the Conference on Visualization,1997.395-402
26 Kobbelt L,Campagna S,Seidel H P.A general framework for mesh decimation.In:Proceedings of the Graphics Interface Conference,1998.43-50
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
28 Tarini M,Puppo E,Panozzo D,et al.Simple quad domains for field aligned mesh parametrization.ACM Trans Graph,2011,30:1
29 Gao X F,Deng Z G,Chen G N.Hexahedral mesh re-parameterization from aligned base-complex.ACM Trans Graph,2015,34:142:1-142:10
30 Noris G,Hornung A,Sumner R W,et al.Topology-driven vectorization of clean line drawings.ACM Trans Graph,2013,32:1-11
31 Kauppinen H,Seppanen T,Pietikainen M.An experimental comparison of autoregressive and Fourier-based descriptors in 2D shape classification.IEEE Trans Pattern Anal Mach Intell,1995,17:201-207
32 Loncaric S.A survey of shape analysis techniques.Pattern Recogn,1998,31:983-1001
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
34 Zhang D S,Lu G J.Study and evaluation of different Fourier methods for image retrieval.Image Vision Comput,2005,23:33-49
35 Glassner A.Graphics Gems.Orlando:Academic Press,1990
36 El-ghazal A,Basir O,Belkasim S.Farthest point distance:a new shape signature for Fourier descriptors.Signal Process-Image Commun,2009,24:572-586
37 Durand F.Where do people draw lines?:technical perspective.Commun ACM,2012,55:106
2 Liu X,Wong T T,Heng P A.Closure-aware sketch simplification.ACM Trans Graph,2015,34:1-10
3 Shesh A,Chen B Q.Efficient and dynamic simplification of line drawings.Comput Graph Forum,2008,27:537-545
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
5 Pusch R,Samavati F,Nasri A,et al.Improving the sketch-based interface.Visual Comput,2007,23:955-962
6 Orbay G,Kara L B.Beautification of design sketches using trainable stroke clustering and curve fitting.IEEE Trans Visual Comput Graph,2011,17:694-708
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
8 Simo-Serra E,Iizuka S,Sasaki K,et al.Learning to simplify:fully convolutional networks for rough sketch cleanup.ACM Trans Graph,2016,35:1-11
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
10 Favreau J D,Lafarge F,Bousseau A.Fidelity vs.simplicity:a global approach to line drawing vectorization.ACMTrans Graph,2016,35:1-10
11 Parakkat A D,Pundarikaksha U B,Muthuganapathy R.A Delaunay triangulation based approach for cleaning rough sketches.Comput Graph,2018,74:171-181
12 Zou J J,Yan H.Cartoon image vectorization based on shape subdivision.In:Proceedings of the International Computer Graphics,2001.225-231
13 Bo P B,Luo G N,Wang K Q.A graph-based method for fitting planar B-spline curves with intersections.J Comput Des Eng,2016,3:14-23
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
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
16 Shesh A,Chen B.Smartpaper:an interactive and user friendly sketching system.In:Proceedings of the Computer Graphics Forum,2004
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
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
19 Bae S H,Balakrishnan R,Singh K.ILove Sketch: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
20 Grimm C,Joshi P.Just DrawIt:a 3D sketching system.In:Proceedings of the International Symposium on SketchBased Interfaces and Modeling,2012.121-130
21 Schroeder W J,Zarge J A,Lorensen W E.Decimation of triangle meshes.In:Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques,1992.65-70
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
23 Gu′eziec A.Surface simplification with variable tolerance.In:Proceedings of the 2nd International Symposium on Medical Robotics and Computer Assisted Surgery,1995.132-139
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
25 Cohen J,Manocha D,Olano M.Simplifying polygonal models using successive mappings.In:Proceedings of the Conference on Visualization,1997.395-402
26 Kobbelt L,Campagna S,Seidel H P.A general framework for mesh decimation.In:Proceedings of the Graphics Interface Conference,1998.43-50
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
28 Tarini M,Puppo E,Panozzo D,et al.Simple quad domains for field aligned mesh parametrization.ACM Trans Graph,2011,30:1
29 Gao X F,Deng Z G,Chen G N.Hexahedral mesh re-parameterization from aligned base-complex.ACM Trans Graph,2015,34:142:1-142:10
30 Noris G,Hornung A,Sumner R W,et al.Topology-driven vectorization of clean line drawings.ACM Trans Graph,2013,32:1-11
31 Kauppinen H,Seppanen T,Pietikainen M.An experimental comparison of autoregressive and Fourier-based descriptors in 2D shape classification.IEEE Trans Pattern Anal Mach Intell,1995,17:201-207
32 Loncaric S.A survey of shape analysis techniques.Pattern Recogn,1998,31:983-1001
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
34 Zhang D S,Lu G J.Study and evaluation of different Fourier methods for image retrieval.Image Vision Comput,2005,23:33-49
35 Glassner A.Graphics Gems.Orlando:Academic Press,1990
36 El-ghazal A,Basir O,Belkasim S.Farthest point distance:a new shape signature for Fourier descriptors.Signal Process-Image Commun,2009,24:572-586
37 Durand F.Where do people draw lines?:technical perspective.Commun ACM,2012,55:106