×

Scattered data reconstruction by regularization in B-spline and associated wavelet spaces. (English) Zbl 1181.41013

The concern of this paper is the reconstruction of a curve or surface from given scattered data. Scattered data reconstruction (also known as scattered data fitting) problems arise in many fields and applications, such as signal processing, computer graphics and neural networks. The two basic approaches to scattered data reconstruction are interpolation and approximation. A classical approach to scattered data approximation is the solution of the regularized least square problem, where the minimization is taken over all functions belonging to the Beppo-Levi space. The approach of the authors is to solve the minimization problem, not over the Beppo-Levi space, but rather, over the principal shift invariant (PSI) space generated by a single, carefully chosen, compactly supported function. A computational formulation is given in the univariate case when this function is a uniform B-spline and in the bivariate case when this function is the tensor product of uniform B-splines. The PSI space has a simple structure and provides good approximations to smooth functions; it leads to simple and accurate algorithms. The PSI space can be associated to a wavelet system and then one can solve the data fitting problem in the wavelet domain with an efficient algorithm. The proposed method is compared with the classical cubic/thin-plate smoothing spline methods via numerical experiments, where it is seen that the quality of the obtained fitting function is very much equivalent to that of the classical methods, but proposed method offers advantages in terms of numerical efficiency. The numerical experiments demonstrate the computational efficiency of solving data fitting problems in the wavelet domain.

MSC:

41A15 Spline approximation
65D15 Algorithms for approximation of functions
42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arigovindan, M.; Suhling, M.; Hunziker, P.; Unser, M., Variational image reconstruction from arbitrarily spaced samples: A fast multiresolution spline solution, IEEE Trans. Image Process., 14, 4, 450-460 (2005)
[2] Beatson, R. K.; Light, W. A.; Billings, S., Fast solution of the radial basis function interpolation equations: Domain decomposition methods, SIAM J. Sci. Comput., 22, 5, 1717-1740 (2000) · Zbl 0982.65015
[3] Bramble, J. H.; Pasciak, J. E.; Xu, J., Parallel multilevel preconditioners, Math. Comput., 55, 191, 1-22 (1990) · Zbl 0725.65095
[4] Buhmann, M. D., Radial Basis Functions: Theory and Implementations (2003), Cambridge university press · Zbl 1038.41001
[5] J.C. Carr, R.K. Beatson, J.B. Cherrie, T.J. Mitchell, W.R. Fright, B.C. McCallum, T.R. Evans, Reconstruction and representation of 3D objects with radial basis functions, in: Computer Graphics, SIGGRAPH 2001 Proceedings, 2001, pp. 67-76; J.C. Carr, R.K. Beatson, J.B. Cherrie, T.J. Mitchell, W.R. Fright, B.C. McCallum, T.R. Evans, Reconstruction and representation of 3D objects with radial basis functions, in: Computer Graphics, SIGGRAPH 2001 Proceedings, 2001, pp. 67-76
[6] Castaño, D.; Kunoth, A., Multilevel regularization of wavelet based fitting of scattered data—some experiments, Numer. Algorithms, 39, 1-3, 81-96 (2005) · Zbl 1069.65012
[7] Cohen, A.; Daubechies, I.; Feauveau, J. C., Biorthogonal bases of compactly supported wavelets, Comm. Pure Appl. Math., 45, 5, 485-560 (1992) · Zbl 0776.42020
[8] Dahmen, W.; Kunoth, A., Multilevel preconditioning, Numer. Math., 63, 315-344 (1992) · Zbl 0757.65031
[9] Daubechies, I., Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math., 41, 7, 909-996 (1988) · Zbl 0644.42026
[10] de Boor, C., Spline Toolbox User’s Guide (2004), Mathworks Inc.
[11] de Boor, C., A Practical Guide to Splines (2001), Springer-verlag: Springer-verlag New York · Zbl 0987.65015
[12] de Boor, C.; Devore, R. A.; Ron, A., Approximation from shift-invariant subspaces of \(L_2(R^d)\), Trans. Amer. Math. Soc., 341, 2, 787-806 (1994) · Zbl 0790.41012
[13] de Boor, C.; Hollig, K.; Riemenschneider, S., Box Splines (1993), New York: New York Springer-verlag · Zbl 0814.41012
[14] de Boor, C.; Ron, A., Fourier analysis of the approximation power of principal shift-invariant spaces, Constr. Approx., 8, 4, 427-462 (1992) · Zbl 0801.41027
[15] Demmel, J. W., Applied Numerical Linear Algebra (1997), SIAM: SIAM Philadelphia · Zbl 0879.65017
[16] Devore, R. A., Nonlinear approximation, Acta Numer., 7, 51-150 (1998) · Zbl 0931.65007
[17] Dierckx, P., Curve and Surface Fitting with Splines (1993), Oxford University Press · Zbl 0782.41016
[18] Duchon, J., Sur l’erreur d’interpolation des fonctions de plusieur variables par les \(D^m\)-splines, RAIRO Anal. Numer., 12, 4, 325-334 (1978) · Zbl 0403.41003
[19] Dyn, N.; Levin, D.; Rippa, S., Numerical procedures for surface fitting of scattered data by radial functions, SIAM J. Sci. Stat. Comput., 2, 639-659 (1986) · Zbl 0631.65008
[20] Evgeniou, T.; Pontil, M.; Poggio, T., Regularization networks and support vector machines, Adv. Comput. Math., 1, 1-50 (2000) · Zbl 0939.68098
[21] Franke, R., Scattered data interpolation: Tests of some methods, Math. Comput., 38, 157, 181-200 (1982) · Zbl 0476.65005
[22] Franke, R.; Nielson, G. M., Scattered data interpolation and applications: A tutorial and survey, (Gometric Modelling (1991), Springer: Springer Berlin), 131-160
[23] Green, P. J.; Silverman, B. W., Nonparametric Regression and Generalized Linear Models: A Roughness Penalty Approach (1994), Chapman and Hall · Zbl 0832.62032
[24] Han, B.; Shen, Z. W., Wavelets with short support, SIAM J. Math. Anal., 38, 2, 530-556 (2006) · Zbl 1119.42016
[25] B. Han, Z.W. Shen, Dual wavelet frames and Riesz bases in Sobolev spaces, Constr. Approx. (in press); B. Han, Z.W. Shen, Dual wavelet frames and Riesz bases in Sobolev spaces, Constr. Approx. (in press) · Zbl 1161.42018
[26] Han, B.; Shen, Z. W., Wavelets from the loop scheme, J. Fourier Anal. Appl., 11, 6, 615-637 (2005) · Zbl 1129.42434
[27] He, X. M.; Shen, L. X.; Shen, Z. W., A data-adaptive knot selection scheme for fitting splines, IEEE Signal Process. Lett., 8, 5, 137-139 (2001)
[28] Inoue, H., A least-squares smooth fitting for irregularly spaced data: Finite-element approach using the cubic B-spline basis, Geophysics, 51, 11, 2051-2066 (1986)
[29] Jaffard, S., Wavelet methods for fast resolution of elliptic problems, SIAM J. Numer. Anal., 29, 4, 965-986 (1992) · Zbl 0761.65083
[30] Jia, R. Q., The Toeplitz theorem and its applications to approximation theory and linear PDE’s, Trans. Amer. Math. Soc., 347, 7, 2585-2594 (1995) · Zbl 0823.41009
[31] Jia, R. Q.; Lei, J., Approximation by multiinteger translates of functions having global support, J. Approx. Theory, 72, 1, 2-23 (1993) · Zbl 0778.41016
[32] Jia, R. Q.; Shen, Z. W., Multiresolution and wavelets, Proc. Edinburgh Math. Soc., 37, 2, 271-300 (1994) · Zbl 0809.42018
[33] Johnson, M. J., Scattered data interpolation from principal shift-invariant spaces, J. Approx. Theory, 113, 2, 172-188 (2001) · Zbl 0991.41005
[34] Lee, S.; Wolberg, G.; Shin, S., Scattered data interpolation with multilevel B-splines, IEEE Trans. Vis. Comput. Graphics, 3, 3, 228-244 (1997)
[35] Mallat, S., A theory for multiresolution signal decomposition: The wavelet representation, IEEE Trans. Pattern Anal. Mach. Intell., 11, 7, 674-693 (1989) · Zbl 0709.94650
[36] Meinguet, J., Mulitvariate interpolation at arbitary points made simple, Z. Angew. Math. Phys., 30, 292-304 (1979) · Zbl 0428.41008
[37] Meyer, Y., Wavelets and Operators (1992), Cambridge Univ. Press
[38] Norcowich, F. J.; Ward, J. D.; Wendland, H., Sobolev bounds on functions with scattered zeros with applications to radial basis function surface fitting, Math. Comput., 74, 250, 743-763 (2005) · Zbl 1063.41013
[39] Sibson, R.; Stone, G., Computation of thin-plate splines, SIAM J. Sci. Stat. Comput., 12, 6, 1304-1313 (1991) · Zbl 0748.65013
[40] Szeliski, R., Fast surface interpolation using hierarchical basis functions, IEEE Trans. Pattern Anal. Mach. Intell., 12, 6, 513-528 (1990)
[41] Terzopoulos, D., Regularization of inverse visual problems involving discontinuities, IEEE Trans. Pattern Anal. Mach. Intell., 8, 4, 413-424 (1986)
[42] Vazquez, C.; Dubois, E.; Konrad, J., Reconstruction of nonuniformly sampled images in spline spaces, IEEE. Trans. Image Process., 14, 6, 713-725 (2005)
[43] Wahba, G., Spline Models for Observational Data (1990), SIAM · Zbl 0813.62001
[44] Yserentant, H., On the multi-level splitting of finite element spaces, Numer. Math., 49, 379-412 (1986) · Zbl 0608.65065
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.