Smoothing large data sets using discrete thin plate splines. (English) Zbl 1512.65026
Summary: Traditional thin plate splines use radial basis functions and require the solution of a dense linear system of equations whose size is proportional to the number of data points. Instead of radial basis functions we present a method based on the use of polynomials with local support defined on finite element grids. This method is more efficient when dealing with large data sets as the resulting system of equations is sparse and its size depends only on the number of nodes in the finite element grid. Theory is developed for general \(d\)-dimensional data sets and model problems are presented in 3D to study the convergence behaviour.
MSC:
| 65D07 | Numerical computation using splines |
| 41A15 | Spline approximation |
| 65D10 | Numerical smoothing, curve fitting |
References:
| [1] | Almensa, A., Cohen, L.: Fingerprint image matching by minimization of a thin-plate energy using a two-step algorithm with auxiliary variables. In: Fifth IEEE Workshop on Applications of Computer Vision (WACV’00), Palm Springs, California, USA, December 2000. IEEE |
| [2] | Apprato D., Arcangéli R., Manzanilla R. (1987) Sur la construction de surfaces de classe C k à partir d’un grand nombre de données de Lagrange. RAIRO Modél. Math. Anal. Numér. 21(4):529–555 · Zbl 0632.65011 |
| [3] | Arcangéli, R.: Some applications of discrete D m splines. In: Mathematical methods in computer aided geometric design (Oslo, 1988), p. 35–44. Academic, Boston (1989) |
| [4] | Arcangéli R. Manzanilla R., Torrens J.J. (1997) Approximation spline de surfaces de type explicite comportant des failles. RAIRO Modél. Math. Anal. Numér. 31(5):643–676 · Zbl 0886.65008 |
| [5] | Arioli, M.: Backward error analysis and stopping criteria for krylov space method. In: 20th Biennial Conference on Numerical Analysis, page 41 pages, University of Dundee, June 2003 |
| [6] | Bab-Hadiashar, A., Suter, D., Jarvis, R.: Optic flow computation using interpolating thin-plate splines. In: Second Asian Conference on Computer Vision (ACCV’95), p. 452–456, Singapore, December 1995 |
| [7] | Beatson, R., Greengard, L.: A short course on fast multipole methods. In: Wavelets, multilevel methods and elliptic PDEs (Leicester, 1996), Numer. Math. Sci. Comput., p. 1–37. Oxford University Press, New York (1997) · Zbl 0882.65106 |
| [8] | Beatson, R.K., Goodsell, G., Powell, M.J.D.: On multigrid techniques for thin plate spline interpolation in two dimensions. In: The mathematics of numerical analysis (Park City, UT, 1995), vol. 32 of Lectures in Appl. Math. p. 77–97. Am. Math. Soc., Providence, RI, 1996 · Zbl 0862.41007 |
| [9] | Carr J.C., Fright W.R., Beatson R.K. (1997) Surface interpolation with radial basis functions for medical imaging. IEEE Trans Med Imaging 16(1):96–107 · doi:10.1109/42.552059 |
| [10] | Christen P., Hegland M., Nielsen O., Roberts S., Strazdins P., Altas I. (2001) Scalable parallel algorithms for surface fitting and data mining. Parallel Comput 27:941–961 · Zbl 0971.68214 · doi:10.1016/S0167-8191(01)00076-X |
| [11] | Ciarlet P.G. (1978) The Finite Element Method for Elliptic Problems. North-Holland, Amsterdam · Zbl 0383.65058 |
| [12] | Duchon J. (1977) Splines minimizing rotation-invariant. In: Lecture notes in Math, vol 571, p. 85–100. Springer, Berlin Heidelberg New York · Zbl 0342.41012 |
| [13] | Enciso, R., Lewis, J.P., Neumann, U., Mah. J.: 3D tooth shape from radiographs using thin-plate splines. In: MMVR11 - NextMed: Health Horizon, The 11th Annual Medicine Meets Virtual Reality Conferenc, vol. 94 of Studies in Health Technology and Informatics, p. 22–25, IOS press (2003) |
| [14] | Eriksson K., Estep D., Hansbo P., Johnson C. (1996) Computational Differential Equations. Cambridge University Press, Cambridge · Zbl 0946.65049 |
| [15] | Hegland, M., Roberts, S., Altas, I.: Finite element thin plate splines for data mining applications. In: Mathematical methods for curves and surfaces, II (Lillehammer, 1997), Innov. Appl. Math. p. 245–252. Vanderbilt University Press, Nashville (1998) · Zbl 0905.65010 |
| [16] | Hutchinson M.F. (1990) A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Comm. Statist. Simulation Comput. 19(2):433–450 · Zbl 0718.62058 · doi:10.1080/03610919008812866 |
| [17] | Lapeer R.J.A., Prager R.W. (2000) 3D shape recovery of a newborn skull using thin-plate splines. Comput. Medial Imaging Grap 24:193–204 · doi:10.1016/S0895-6111(00)00019-7 |
| [18] | Morse, B., Yoo, T.S., Rheingans, P., Chen, D.T., Subramanian, K.R.: Interpolating implicit surfaces from scattered surface data using compactly supported radial basis functions. In: Proceedings of International Conference on Shape Modeling and Applications ’01, p. 89–98. IEEE Computer Society Press, May 2001 |
| [19] | Powell, M.J.D.: A review of methods for multivariable interpolation at scattered data points. In: The state of the art in numerical analysis (York, 1996), vol. 63 of Inst. Math. Appl. Conf. Ser. New Ser. p. 283–309. Oxford University Press, New York (1997) |
| [20] | Ramsay T. (2002) Spline smoothing over difficult regions. J. R. Stat. Soc. Ser. B Stat. Methodol. 64(2):307–319 · Zbl 1067.62037 · doi:10.1111/1467-9868.00339 |
| [21] | Roberts S., Hegland M., Altas I. (2003) Approximation of a thin plate spline smoother using continuous piecewise polynomial functions. SIAM J. Numer. Anal. 41(1):208–234 · Zbl 1041.65019 · doi:10.1137/S0036142901383296 |
| [22] | Rohr, K., Fornefett, M., Stiehl, H.S.: Approximating thin-plate splines for elastic registration: integration of landmark errors and orientation attributes. In Kuba, A.,Šámal, M., Todd-Pokropek, A. (eds.) Lecture Notes in Computer Science, volume 1613, p. 252–265. Springer (1999) |
| [23] | Sibson R., Stone G. (1991) Computation of thin-plate splines. SIAM J. Sci. Statist. Comput. 12(6):1304–1313 · Zbl 0748.65013 · doi:10.1137/0912070 |
| [24] | Stals, L.: Parallel multigrid on unstructured grids using adaptive finite element methods. PhD thesis, Department Of Mathematics, Australian National University, Australia (1995) · Zbl 0836.65124 |
| [25] | Strakoš, Z., Tichý, P.: On error estimation in the conjugate gradient method and why it works in finite precision computations. Electron. Trans. Numer. Anal. 13:56–80 (electronic) (2002) · Zbl 1026.65027 |
| [26] | Strakoš Z., Tichý P. (2003) On estimation of the A-norm of the error in CG and PCG. PAMM, 3(1):553–554, (electronic) · Zbl 1354.90173 · doi:10.1002/pamm.200310545 |
| [27] | Torrens, J.J.: Discrete smoothing D m -splines: applications to surface fitting. In: Mathematical methods for curves and surfaces, II (Lillehammer, 1997), Innov. Appl. Math. p. 477–484. Vanderbilt University Press, Nashville (1998) · Zbl 0905.65012 |
| [28] | Wahba, G.: Spline models for observational data, volume 59 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1990) · Zbl 0813.62001 |
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.
