Adaptive hierarchical RBF interpolation for creating smooth digital elevation models

ABSTRACT

This paper presents a fast algorithm for smooth digital elevation model interpolation and approximation from scattered elevation data. The global surface is reconstructed by subdividing it into overlapping local subdomains using a perfectly balanced binary tree. In each tree leaf, a smooth local surface is reconstructed using radial basis functions. Finally a hierarchical blending is done to create the final C¹-continuous surface using a family of functions called Partition of Unity. We present two terrain data sets and show that our method is robust since the number of data points in the Partition of Unity blending areas is explicitly specified.

REFERENCES

• 1: P. Arrighi and P. Soille. From scanned topographic maps to digital elevation models. In Proceedings of Geovision'99, 1999.
• 2: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to splines for use in computer graphics & geometric modeling, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 3: R.K. Beatson and W.A. Light. Fast evaluation of radial basis functions: methods for two-dimensional polyharmonic splines. Computational Mathematics and Applications, 24(12):7--20, 1992.
• 4: Martin Bertram , Xavier Tricoche , Hans Hagen, Adaptive smooth scattered-data approximation for large-scale terrain visualization, Proceedings of the symposium on Data visualisation 2003, p.177-184, May 26-28, 2003, Grenoble, France
• 5: I. Briggs. Machine contouring using minimum curvature. Geophysics, (39):39--48, 1974.
• 6: 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, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.67-76, August 2001 [doi>10.1145/383259.383266]
• 7: J. Childs. Development of a two-level iterative computational method for solution of the Franklin approximation algorithm for the interpolation of large contour line data sets. Master's thesis, Rensselaer Polytechnic Institute, Troy, NY 12180, may 2003.
• 8: J. Duchon. Splines minimizing rotation-invariant semi-norms in sobolev spaces. In Walter Schempp and Karl Zeller, editors, Constructive Theory of Functions of Several Variables, pages S. 85--100. Springer-Verlag, Berlin-Heidelberg, 1977. NAM-Bibliothek S/M/571.
• 9: R. Franke. Scattered data interpolation: Tests of some methods.Mathematics of Computation, 38(157):181--200, 1982.
• 10: R. Franke and G. M. Nielson. Scattered data interpolation and applications- a tutorial and survey. In H. Hagen and D. Roller, editors, Geometric Modelling: Methods and Their Application, pages 131--160, Berlin: Springer-Verlag, 1991.
• 11: W. R. Franklin. Elevation data operations. Dagstuhl - Workshop on computational cartography, 1996.
• 12: M. B. Gousie and W. R. Franklin. Converting elevation contours to a grid. Eighth International Symposium on Spatial Data Handling (SDH), 1998.
• 13: Michael B. Gousie , Wm. Randolph Franklin, Constructing a dem from grid-based data by computing intermediate contours, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.71-77, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956686]
• 14: Jörg Haber , Frank Zeilfelder , Oleg Davydov , Hans Peter Seidel, Smooth approximation and rendering of large scattered data sets, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 15: R. L. Hardy. Multiquadric equations of topography and other irregular surfaces. J. Geophys. res, 76:1905--1915, 1971.
• 16: M.F. Hutchinson. Calculation of hydrologically sound digital elevation models. In Proceedings of the Third International Symposium on Space Data Handling, pages 117--133, Columbus, Ohio, 1988. International Geographical Union.
• 17: N. Kojekine, I. Hagiwara, and V. Savchenko. Software tools using csrbfs for processing scattered data. Computers & Graphics, 27(2):311--319, 2003.
• 18: Seungyong Lee , George Wolberg , Sung Yong Shin, Scattered Data Interpolation with Multilevel B-Splines, IEEE Transactions on Visualization and Computer Graphics, v.3 n.3, p.228-244, July 1997 [doi>10.1109/2945.620490]
• 19: Suresh K. Lodha , Richard Franke, Scattered Data Techniques for Surfaces, Proceedings of the Conference on Scientific Visualization, p.181, June 09-13, 1997
• 20: Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H.-P. Seidel. Multi-level partition of unity implicits. In Proceedings of SIGGRAPH'03, pages 463--470, 2003.
• 21: L. L. Schumaker. Fitting surfaces to scattered data. In G.G. Lorentz, C.K. Chui, and L.L. Schumaker, editors, Approximation Theory II, pages 203--268, New York, 1976. Academic Press.
• 22: Donald Shepard, A two-dimensional interpolation function for irregularly-spaced data, Proceedings of the 1968 23rd ACM national conference, p.517-524, August 27-29, 1968 [doi>10.1145/800186.810616]
• 23: R. Sibson. A Brief Description of Natural Neighbor Interpolation, in Interpreting Multivariate Data, pages 21--36. V. Barnett, John Wiley and Sons, 1981.
• 24: P. Soille. Spatial distributions from contour lines: An efficient methodology based on distance transformation. Journal of Visual Communication and Image Representation, 2(2):138--150, june 1991.
• 25: S. Spinello and G. Greiner. Automatic contour line recognition from scanned topographic maps. Technical report, University of Erlangen, 2001.
• 26: S. Spinello and P. Guitton. Contour line recognition from scanned topographic maps. Journal of WSCG, 12(1-3), 2004.
• 27: I. Tobor, P. Reuter, and C. Schlick. Efficient reconstruction of large scattered geometric datasets using the partition of unity and radial basis functions. In Journal of WSCG 2004, volume 12, pages 467--474, 2004.
• 28: H. Wendland. Piecewise polynomial, positive definite and compactly supported radial basis functions of minimal degree. Advances in Computational Mathematics, 4:389--396, 1995.
• 29: H. Wendland. Fast evaluation of radial basisc functions: Methods based on partition of unity. Approximation theory X: Abstract and classical analysis, pages 473--483. Vanderbilt University Press, Nashville, 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

General Terms:
Algorithms

Keywords:
DEM, GIS, approximation, computational geometry, contours, grid, interpolation, scattered data