×

Univariate subdivision schemes for noisy data with geometric applications. (English) Zbl 1417.65079

Summary: We introduce and analyze univariate, linear, and stationary subdivision schemes for refining noisy data by fitting local least squares polynomials. This is the first attempt to design subdivision schemes for noisy data. We present primal schemes, with refinement rules based on locally fitting linear polynomials to the data, and study their convergence, smoothness, and basic limit functions. Then, we provide several numerical experiments that demonstrate the limit functions generated by these schemes from initial noisy data. The application of an advanced local linear regression method to the same data shows that the methods are comparable. In addition, several extensions and variants are discussed and their performance is illustrated by examples. We conclude by applying the schemes to noisy geometric data.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersson, Lars-Erik; Stewart, Neil Frederick, Introduction to the mathematics of subdivision surfaces, (2010), Society for Industrial and Applied Mathematics Philadelphia · Zbl 1207.68412
[2] Cavaretta, Alfred S.; Dahmen, Wolfgang; Micchelli, Charles A., Stationary subdivision, Memoirs of the American Mathematical Society, vol. 93, (1991), no. 453, September, 186 pp · Zbl 0741.41009
[3] Chaikin, George Merrill, An algorithm for high speed curve generation, Comput. Graph. Image Process., 3, 4, 346-349, (December 1974)
[4] Conti, Costanza; Dyn, Nira, Analysis of subdivision schemes for nets of functions by proximity and controllability, J. Comput. Appl. Math., 236, 4, 461-475, (September 2011) · Zbl 1235.65020
[5] Deslauriers, Gilles; Dubuc, Serge, Symmetric iterative interpolation processes, Constr. Approx., 5, 1, 49-68, (December 1989) · Zbl 0659.65004
[6] Donoho, David L.; Yu, Thomas P. Y., Nonlinear pyramid transforms based on Median-interpolation, SIAM J. Math. Anal., 31, 5, 1030-1061, (2000) · Zbl 0953.42017
[7] Dubuc, Serge, Interpolation through an iterative scheme, J. Math. Anal. Appl., 114, 1, 185-204, (February 1986) · Zbl 0615.65005
[8] Dyn, Nira, Subdivision schemes in computer-aided geometric design, (Light, Will, Advances in Numerical Analysis, vol. II, (1992), Oxford University Press New York), 36-104 · Zbl 0760.65012
[9] Dyn, Nira, Analysis of convergence and smoothness by the formalism of Laurent polynomials, (Iske, Armin; Quak, Ewald; Floater, Michael S., Tutorials on Multiresolution in Geometric Modelling, Mathematics and Visualization, (2002), Springer Berlin, Heidelberg), 51-68 · Zbl 1004.65028
[10] Dyn, Nira; Farkhi, Elza, Spline subdivision schemes for compact sets. A survey, Serdica Math. J., 28, 4, 349-360, (2002) · Zbl 1041.42023
[11] Dyn, Nira; Floater, Michael S.; Hormann, Kai, A \(C^2\) four-point subdivision scheme with fourth order accuracy and its extensions, (Dæhlen, Morten; Mørken, Knut; Schumaker, Larry L., Mathematical Methods for Curves and Surfaces, Tromsø, 2004, Modern Methods in Mathematics, (2005), Nashboro Press Brentwood), 145-156 · Zbl 1080.65526
[12] Dyn, Nira; Hormann, Kai; Sabin, Malcolm A.; Shen, Zuowei, Polynomial reproduction by symmetric subdivision schemes, J. Approx. Theory, 155, 1, 28-42, (November 2008) · Zbl 1159.41003
[13] Dyn, Nira; Levin, David, Subdivision schemes in geometric modelling, Acta Numer., 11, 73-144, (January 2002) · Zbl 1105.65310
[14] Eisinberg, Alfredo; Fedele, Giusepp, Discrete orthogonal polynomials on equidistant nodes, Int. Math. Forum, 2, 21, 1007-1020, (2007) · Zbl 1203.42035
[15] Härdle, Wolfgang; Müller, Marlene; Sperlich, Stefan; Werwatz, Axel, Nonparametric and semiparametric models, Springer Series in Statistics, (2004), Springer-Verlag Berlin, Heidelberg · Zbl 1059.62032
[16] Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome, The elements of statistical learning, (2009), Springer · Zbl 1273.62005
[17] Itai, Uri; Dyn, Nira, Generating surfaces by refinement of curves, J. Math. Anal. Appl., 388, 2, 913-928, (April 2012) · Zbl 1246.65032
[18] Mustafa, Ghulam; Li, Hao; Zhang, Juyong; Deng, Jiansong, \(\ell_1\)-regression based subdivision schemes for noisy data, Comput. Aided Des., 58, 189-199, (2015)
[19] Penrose, Roger, A generalized inverse for matrices, Proc. Am. Math. Soc., 51, 3, 406-413, (July 1955) · Zbl 0065.24603
[20] Peters, Jörg; Reif, Ulrich, Subdivision surfaces, Springer Series in Geometry and Computing, vol. 3, (2008), Springer · Zbl 1148.65014
[21] Sharon, Nir; Itai, Uri, Approximation schemes for functions of positive-definite matrix values, IMA J. Numer. Anal., 33, 4, 1436-1468, (2013) · Zbl 1284.65028
[22] Wallner, Johannes; Dyn, Nira, Convergence and \(C^1\) analysis of subdivision schemes on manifolds by proximity, Comput. Aided Geom. Des., 22, 7, 593-622, (October 2005) · Zbl 1083.65023
[23] Wallner, Johannes; Nava Yazdani, Esfandiar; Grohs, Philipp, Smoothness properties of Lie group subdivision schemes, Multiscale Model. Simul., 6, 2, 493-505, (2007) · Zbl 1144.41003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.