Abstract
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.
Similar content being viewed by others
References
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
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
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)
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
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
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
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)
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
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
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
Ciarlet P.G. (1978) The Finite Element Method for Elliptic Problems. North-Holland, Amsterdam
Duchon J. (1977) Splines minimizing rotation-invariant. In: Lecture notes in Math, vol 571, p. 85–100. Springer, Berlin Heidelberg New York
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)
Eriksson K., Estep D., Hansbo P., Johnson C. (1996) Computational Differential Equations. Cambridge University Press, Cambridge
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)
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
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
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
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)
Ramsay T. (2002) Spline smoothing over difficult regions. J. R. Stat. Soc. Ser. B Stat. Methodol. 64(2):307–319
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
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)
Sibson R., Stone G. (1991) Computation of thin-plate splines. SIAM J. Sci. Statist. Comput. 12(6):1304–1313
Stals, L.: Parallel multigrid on unstructured grids using adaptive finite element methods. PhD thesis, Department Of Mathematics, Australian National University, Australia (1995)
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)
Strakoš Z., Tichý P. (2003) On estimation of the A-norm of the error in CG and PCG. PAMM, 3(1):553–554, (electronic)
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)
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)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by G. Wittum.
Rights and permissions
About this article
Cite this article
Stals, L., Roberts, S. Smoothing large data sets using discrete thin plate splines. Comput. Visual Sci. 9, 185–195 (2006). https://doi.org/10.1007/s00791-006-0033-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00791-006-0033-x