Splines & Meshes
Optimal Spline Approximation via ℓ0-Minimization
Christopher Brandt,
Hans-Peter Seidel, Klaus Hildebrandt,
Christopher Brandt
Delft University of Technology
Max Planck Institute for Informatics
Search for more papers by this authorKlaus Hildebrandt
Delft University of Technology
Max Planck Institute for Informatics
Search for more papers by this authorChristopher Brandt,
Hans-Peter Seidel, Klaus Hildebrandt,
Christopher Brandt
Delft University of Technology
Max Planck Institute for Informatics
Search for more papers by this authorKlaus Hildebrandt
Delft University of Technology
Max Planck Institute for Informatics
Search for more papers by this authorAbstract
Splines are part of the standard toolbox for the approximation of functions and curves in ℝd. Still, the problem of finding the spline that best approximates an input function or curve is ill-posed, since in general this yields a “spline” with an infinite number of segments. The problem can be regularized by adding a penalty term for the number of spline segments. We show how this idea can be formulated as an ℓ0-regularized quadratic problem. This gives us a notion of optimal approximating splines that depend on one parameter, which weights the approximation error against the number of segments. We detail this concept for different types of splines including B-splines and composite Bézier curves. Based on the latest development in the field of sparse approximation, we devise a solver for the resulting minimization problems and show applications to spline approximation of planar and space curves and to spline conversion of motion capture data.
Supporting Information
| Filename | Description |
|---|---|
| cgf12589-sup-0001-S1.mp418.1 MB | Supporting Information |
Please note: The publisher is not responsible for the content or functionality of any supporting information supplied by the authors. Any queries (other than missing content) should be directed to the corresponding author for the article.
References
- Andersen E.D., Andersen K.D.: The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm. In High performance optimization. Springer, 2000, pp. 197–232. 6
- Bahmani S., Boufounos P., Raj B.: Greedy sparsity-constrained optimization. In Forty Fifth Asilomar Conference on Signals, Systems and Computers (2011), pp. 1148–1152. 2, 5
- Blumensath T., Davies M.E.: Normalized iterative hard thresholding: Guaranteed stability and performance. IEEE J. Sel. Topics Signal Process. 4, 2 (2010), 298–309. 2, 5
- Beck A., Eldar Y.C.: Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM J. Optim. 23, 3 (2013), 1480–1509. 2, 5
- Bergeaud F., Mallat S.: Matching pursuit of images. Wavelet Analysis and Its Applications 7 (1998), 285–300. 2, 5
10.1016/S1874-608X(98)80011-3 Google Scholar
- Burchard H.G.: Splines (with optimal knots) are better. Applicable Analysis 3, 4 (1974), 309–319. 2
10.1080/00036817408839073 Google Scholar
- Chouzenoux E., Jezierska A., Pesquet J.-C., Talbot H.: A majorize-minimize subspace approach for ℓ2 - ℓ0 image regularization. SIAM Journal on Imaging Science 6 (2013), 563–591. 2, 5
- De Boor C.: Good approximation by splines with variable knots. In Spline Functions and Approximation Theory. Springer, 1973, pp. 57–72. 2
10.1007/978-3-0348-5979-0_3 Google Scholar
- Deng C., Lin H.: Progressive and iterative approximation for least squares B-spline curve and surface fitting. Computer-Aided Design 47 (2014), 32–44. 2, 8
- Foucart S.: Hard thresholding pursuit: An algorithm for compressive sensing. SIAM J. Numer. Anal. 49, 6 (2011), 2543–2563. 2, 5
- Gribov A., Bodansky E.: A new method of polyline approximation. In Structural, Syntactic, and Statistical Pattern Recognition, vol. 3138 of Lecture Notes in Computer Science. Springer, 2004, pp. 504–511. 2
- Gálvez A., Iglesias A.: Efficient particle swarm optimization approach for data fitting with free knot B-splines. Computer-Aided Design 43, 12 (2011), 1683–1692. 2, 8
- Gaffney P., Powell M.: Optimal interpolation. In Numerical Analysis, G. Watson, (Ed.), vol. 506 of Lecture Notes in Mathematics. Springer Berlin Heidelberg, 1976, pp. 90–99. 8
- Hofer M., Pottmann H.: Energy-minimizing splines in manifolds. ACM Trans. Graph. 23, 3 (2004), 284–293. 4
- He L., Schaefer S.: Mesh denoising via ℓ0 minimization. ACM Trans. Graph. 32, 4 (2013), 64:1–64:8. 2, 5
- Hildebrandt K., Schulz C., von Tycowicz C., Polthier K.: Interactive spacetime control of deformable objects. ACM Trans. Graph. 31, 4 (2012), 71:1–71:8. 4
- Jupp D. L. B.: Approximation to data by splines with free knots. SIAM J. Numer. Anal. 15 (1978), 328–343. 2
- Kass M., Anderson J.: Animating oscillatory motion with overlap: wiggly splines. ACM Trans. Graph. 27, 3 (2008), 28:1–28:8. 4
- Kang H., Chen F., Li Y., Deng J., Yang Z.: Knot calculation for spline fitting via sparse optimization. Computer-Aided Design 58 (2015), 179–188. 2, 8
- Kolesnikov A.: Segmentation and multi-model approximation of digital curves. Pattern Recognition Letters 33, 9 (2012), 1171–1179. 2
- Lyche T., Mørken K.: Knot removal for parametric B-spline curves and surfaces. Comput. Aided Geom. Des. 4, 3 (Nov. 1987), 217–230. 2
10.1016/0167-8396(87)90013-6 Google Scholar
- Lyche T., Mørken K.: A data-reduction strategy for splines with applications to the approximation of functions and data. IMA J. Numer. Anal. 8, 2 (1988), 185–208. 2
- Li W., Xu S., Zhao G., Goh L.P.: Adaptive knot placement in B-spline curve approximation. Computer-Aided Design 37, 8 (2005), 791–797. 2
- Maier G.: Optimal arc spline approximation. Computer Aided Geometric Design 31, 5 (2014), 211–226. 2
- Mann R., Jepson A., El-Maraghi T.: Trajectory segmentation using dynamic programming. In 16th Intern. Conf. on Pattern Recognition (2002), vol. 1, pp. 331–334. 2
10.1109/ICPR.2002.1044709 Google Scholar
- Moriyama M., Yoshimoto F., Harada T.: Automatic knot placement by a genetic algorithm for data fitting with a spline. In Proc. Shape Model. Intern. (1999), pp. 162–169. 2
- Nikolova M., Ng M.K., Zhang S., Ching W.-K.: Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. SIAM J. Imaging Sciences 1, 1 (2008), 2–25. 2, 5
- Patrascu A., Necoara I.: Iteration complexity analysis of random coordinate descent methods for ℓ0 regularized convex problems. arXiv:1403.6622. 1, 2, 5, 9
- Perez J.-C., Vidal E.: Optimum polygonal approximation of digitized curves. Pattern Recognition Letters 15, 8 (1994), 743–750. 2
- Schweikert D.: An interpolating curve using a spline in tension. J. Math. Phys. 45 (1966), 312–317. 4
- Sarfraz M., Raza S.A.: Capturing outline of fonts using genetic algorithm and splines. In Proc. Intern. Conf. on Information Visualisation (2001), pp. 738–743. 2
- Schulz C., von Tycowicz C., Seidel H.-P., Hildebrandt K.: Animating deformable objects using sparse spacetime constraints. ACM Transactions on Graphics 33, 4 (2014), 109:1–109:10. 4
- Vassilev T.I.: Fair interpolation and approximation of B-splines by energy minimization and points insertion. Computer-Aided Design 28, 9 (1996), 753–760. 2
- Xu L., Lu C., Xu Y., Jia J.: Image smoothing via L0 gradient minimization. ACM Trans. Graph. 30, 6 (2011), 174:1–12. 2, 5, 8
- Yoshimoto F., Harada T., Yoshimoto Y.: Data fitting with a spline using a real-coded genetic algorithm. Computer-Aided Design 35, 8 (2003), 751–760. 2
- Yang H., Wang W., SUN J.: Control point adjustment for B-spline curve approximation. Computer Aided Design 36, 7 (2004), 639–652. 2
- Zhao X., Zhang C., Yang B., Li P.: Adaptive knot placement using a GMM-based continuous optimization algorithm in B-spline curve approximation. Computer-Aided Design 43, 6 (2011), 598–604. 2
