“Bézier Spline Simplification Using Locally Integrated Error Metrics” by Wang, Liu, Zorin and Jacobson
Conference:
Type(s):
Title:
- Bézier Spline Simplification Using Locally Integrated Error Metrics
Session/Category Title: Smooth-Parametric-LINE
Presenter(s)/Author(s):
Abstract:
Inspired by surface mesh simplification methods, we present a technique for reducing the number of Bézier curves in a vector graphics while maintaining high fidelity. We propose a curve-to-curve distance metric to repeatedly conduct local segment removal operations. By construction, we identify all possible lossless removal operations ensuring the smallest possible zero-error representation of a given design. Subsequent lossy operations are computed via local Gauss-Newton optimization and processed in a priority queue. We tested our method on the OpenClipArts dataset of 20,000 real-world vector graphics images and show significant improvements over representative previous methods. The generality of our method allows us to show results for curves with varying thickness and for vector graphics animations.
References:
[1]
Pankaj K. Agarwal. 2007. Lecture 23: Hausdorff and Frechet distance.
[2]
Sameer Agarwal, Keir Mierle, and The Ceres Solver Team. 2022. Ceres Solver. https://github.com/ceres-solver/ceres-solver
[3]
Marc Alexa and Wolfgang Müller. 2000. Representing animations by principal components. In Computer Graphics Forum, Vol. 19. Wiley Online Library, 411–418.
[4]
Stephen Boyd and Lieven Vandenberghe. 2006. Convex Optimization.
[5]
Stephen P Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press.
[6]
Hung-Hsin Chang and Hong Yan. 1998. Vectorization of hand-drawn image using piecewise cubic Bezier curves fitting. Pattern recognition 31, 11 (1998), 1747–1755.
[7]
Boris Dalstein, Rémi Ronfard, and Michiel Van De Panne. 2015. Vector graphics animation with time-varying topology. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–12.
[8]
Carl De Boor, Klaus Höllig, and Malcolm Sabin. 1987. High accuracy geometric Hermite interpolation. Computer Aided Geometric Design 4, 4 (1987), 269–278.
[9]
Paul Dierckx. 1995. Curve and surface fitting with splines. Oxford University Press.
[10]
David H Douglas and Thomas K Peucker. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: the international journal for geographic information and geovisualization 10, 2 (1973), 112–122.
[11]
Van Than Dung and Tegoeh Tjahjowidodo. 2017. A direct method to solve optimal knots of B-spline curves: An application for non-uniform B-spline curves fitting. PloS one 12, 3 (2017), e0173857.
[12]
Michael Garland and Paul S Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques. 209–216.
[13]
Hugues Hoppe. 1996. Progressive meshes. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. 99–108.
[14]
Yixin Hu, Teseo Schneider, Xifeng Gao, Qingnan Zhou, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2019. TriWild: robust triangulation with curve constraints. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–15.
[15]
Alec Jacobson 2021. gptoolbox: Geometry Processing Toolbox. http://github.com/alecjacobson/gptoolbox.
[16]
David LB Jupp. 1978. Approximation to data by splines with free knots. SIAM J. Numer. Anal. 15, 2 (1978), 328–343.
[17]
Hongmei Kang, Falai Chen, Yusheng Li, Jiansong Deng, and Zhouwang Yang. 2015. Knot calculation for spline fitting via sparse optimization. Computer-Aided Design 58 (2015), 179–188.
[18]
Brian Karis. 2022. The Journey to Nanite.
[19]
Zachi Karni and Craig Gotsman. 2004. Compression of soft-body animation sequences. Computers & Graphics 28, 1 (2004), 25–34.
[20]
Alexander Kolesnikov. 2010. Approximation of digitized curves with cubic Bézier splines. In 2010 IEEE International Conference on Image Processing. IEEE, 4285–4288.
[21]
Jerome Edward Lengyel. 1999. Compression of time-dependent geometry. In Proceedings of the 1999 symposium on Interactive 3D graphics. 89–95.
[22]
Raphael Linus Levien. 2009. From spiral to spline: Optimal techniques in interactive curve design. University of California, Berkeley.
[23]
Songrun Liu, Alec Jacobson, and Yotam Gingold. 2014. Skinning Cubic Bézier Splines and Catmull-Clark Subdivision Surfaces. ACM Transactions on Graphics (TOG) 33, 6 (2014), 9 pages.
[24]
PD Loach and AJ Wathen. 1991. On the best least squares approximation of continuous functions using linear splines with free knots. IMA journal of numerical analysis 11, 3 (1991), 393–409.
[25]
Tom Lyche and Knut Mørken. 1987. Knot removal for parametric B-spline curves and surfaces. Computer Aided Geometric Design 4, 3 (1987), 217–230.
[26]
J. N. Lyness and C. B. Moler. 1967. Numerical Differentiation of Analytic Functions. SIAM J. Numer. Anal. 4, 2 (1967), 202–210.
[27]
Asif Masood and Muhammad Sarfraz. 2009. Capturing outlines of 2D objects with Bézier cubic approximation. Image and Vision Computing 27, 6 (2009), 704–712.
[28]
Farzin Mokhtarian, Yoke Khim Ung, and Zhitao Wang. 2005. Automatic fitting of digitised contours at multiple scales through the curvature scale space technique. Computers & Graphics 29, 6 (2005), 961–971.
[29]
Alvin Penner. 2019. Fitting a cubic Bezier to a parametric function. The College Mathematics Journal 50, 3 (2019), 185–196.
[30]
Günter Rote. 2007. Computing the Fréchet distance between piecewise smooth curves. Comput. Geom. 37, 3 (2007), 162–174. https://doi.org/10.1016/j.comgeo.2005.01.004
[31]
Muhammad Sarfraz and Asif Masood. 2007. Capturing outlines of planar images using Bézier cubics. Computers & Graphics 31, 5 (2007), 719–729.
[32]
Muhammad Sarfraz and MFA Razzak. 2002. An algorithm for automatic capturing of the font outlines. Computers & Graphics 26, 5 (2002), 795–804.
[33]
Mirko Sattler, Ralf Sarlette, and Reinhard Klein. 2005. Simple and efficient compression of animation sequences. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation. 209–217.
[34]
Philip J Schneider. 1990. An algorithm for automatically fitting digitized curves. Graphics gems 1 (1990), 612–626.
[35]
Lejun Shao and Hao Zhou. 1996. Curve fitting with Bezier cubics. Graphical models and image processing 58, 3 (1996), 223–232.
[36]
Arthur van Goethem, Wouter Meulemans, Andreas Reimer, Herman Haverkort, and Bettina Speckmann. 2013. Topologically safe curved schematization. The Cartographic Journal 50, 3 (2013), 276–285.
[37]
Libor Váša and Václav Skala. 2009. Cobra: Compression of the basis for pca represented animations. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1529–1540.
[38]
Jiayi Eris Zhang, Seungbae Bang, David IW Levin, and Alec Jacobson. 2020. Complementary dynamics. arXiv preprint arXiv:2009.02462 (2020).
