Petr Vaněček
ABSTRACT
The Radial Basis Function method (RBF) provides a generic mathematical tool for various interpolation and smoothing problems in computer graphics and vision, such as surface reconstruction from scattered data, smoothing of noisy data, filling gaps and restoring missing data. As the radial function uses distances in the data set, it does not depend on the dimension of the problem. Thus, RBF can be used for 2D data processing (images, height fields), 3D data processing (surfaces, volumes), 4D data processing (time-varying data) or even higher.
In this paper, we present a novel RBF based approach for reconstruction of images and height fields from highly corrupted data, which can handle large images in feasible time, while being very simple to program. Our approach uses an image partitioning via Delaunay triangulation of the dataset. The advantage of our approach is that it can be combined with fast evaluation of RBF using R-expansion [Zandifar et al. 2004] of the basis function.
- Beatson, R. K., and Newsam, G. N. 1992. Fast evaluation of radial basis functions: I. Computers Math. Applic. 24, 12, 7--19.Google Scholar
Cross Ref
- Beatson, R. K., Cherrie, J. B., and Mouat, C. T. 1999. Fast fitting of radial basis functions: Methods based on preconditioned gmres iteration. Advances in Computational Mathematics, 253--270.Google Scholar
- Beatson, R. K., Cherrie, J. B., and Ragozin, D. L. 2001. Fast evaluation of radial basis functions: Methods for four-dimensional polyharmonic splines. SIAM J. Math. Anal. 32, 6, 1272--1310.Google ScholarDigital Library
- Beatson, R. K., Powell, M. J. D., and Tan, A. M., 2006. Fast evaluation of polyharmonic splines in three dimensions. Not accepted? DAMTP2006/NA03.Google Scholar
- Delaunay, B. N. 1934. Sur la sphere vide. Bulletin of Academy of Sciences of the USSR, 6, 793--800.Google Scholar
- Demaret, L., Dyn, N., and Iske, A. 2006. Image compression by linear splines over adaptive triangulations. Signal Process. 86, 7, 1604--1616. Google ScholarDigital Library
- Duchon, J. 1977. Splines minimizing rotation-invariant seminorms in sobolev spaces. In Constructive Theory of Functions of Several Variables, W. Schempp and K. Zeller, Eds. Springer-Verlag, Berlin-Heidelberg, 85--100.Google Scholar
- Fornberg, B., Driscoll, T. A., Wright, G., and Charles, R. 2002. Observations on the behavior of radial basis function approximations near boundaries. Computers and Mathematics with Applications 43, 3 (February), 473--490(18).Google ScholarCross Ref
- Greengard, L., and Rokhlin, V. 1987. A Fast Algorithm for Particle Simulations. Journal of Computational Physics 73, 325--348. Google ScholarDigital Library
- Gumerov, N., and Duraiswami, R., 2004. Fast multipole methods: Fundamentals and applications (lecture 2: Key ideas in the fast multipole method) (presentation).Google Scholar
- Gumerov, N. A., and Duraiswami, R. 2006. Fast multipole method for the biharmonic equation in three dimensions. Journal of Computational Physics, 215, 363--383. Google ScholarDigital Library
- Kolingerová, I., and Žalik, B. 2002. Improvements to randomized incremental delaunay insertion. Computers and Graphics 26, 3, 477--490.Google ScholarCross Ref
- Ohtake, Y., Belyaev, A., and Seidel, H. P. 2003. A multi-scale approach to 3d scattered data interpolation with compactly supported basis functions. In Poceedings of the Shape Modeling International 2003 (SMI'03), IEEE Computer Society, Washington, DC, USA, 153. Google ScholarDigital Library
- Ohtake, Y., Belyaev, A., and Seidel, H. P. 2004. 3d scattered data approximation with adaptive compactly supported radial basis functions. In Poceedings of the Shape Modeling International 2004 (SMI'04), IEEE Computer Society, Washington, DC, USA, 31--39. Google ScholarDigital Library
- USC - University of Southern California - Signal and Image Processing Institute, 2007. The USC-SIPI image database. http://sipi.usc.edu/services/database/, 6.Google Scholar
- Wendland, H. 1995. Piecewise polynomial, positive definite and compactly supported radial basis functions of minimal degree. Advances in Computational Mathematics 4, 389--396.Google Scholar
- Žalik, B. 2005. An efficient sweep-line delaunay triangulation algorithm. Computer-Aided Design 37, 10, 1027--1038. Google ScholarDigital Library
- Zandifar, A., Lim, S., Duraiswami, R., Gumerov, N. A., and Davis, L. S. 2004. Multi-level fast multipole method for thin plate spline evaluation. In International Conference on Image Processing, vol. 3, 1683--1686.Google Scholar
Index Terms
- Delaunay space division for RBF image reconstruction
Recommendations
Pruning RBF networks with QLP decomposition
NN'07: Proceedings of the 8th Conference on 8th WSEAS International Conference on Neural Networks - Volume 8The radial basis function (RBF) network is the main practical alternative to the multi-layer perceptron for non-linear modeling. This paper describes a methodology to adjust predictions models, calculated from experimental data using regression with ...
Efficient preconditioning for image reconstruction with radial basis functions
Radial basis functions are a popular basis for interpolating scattered data during the image reconstruction process in graphic analysis. In this context, the solution of a linear system of equations represents the most time-consuming operation. In this ...
RBF WENO Reconstructions with Adaptive Order and Applications to Conservation Laws
AbstractThis paper develops a framework for finite volume radial basis function (RBF) approximation of a function u on a stencil of mesh cells in multiple dimensions. The theory of existence of the approximation is given. In one dimension, as the cell ...
Comments