Title: What's the point? Interpolation and extrapolation with a regular grid DEM

Date: 5 July 1999

Authors: David Kidner, Mark Dorey & Derek Smith

Link: http://www.geovista.psu.edu/sites/geocomp99/Gc99/082/gc_082.htm

Abstract:

This paper advocates the use of more sophisticated approaches to the mathematical modelling of elevation samples for applications that rely on interpolation and extrapolation. The computational efficiency of simple, linear algorithms is no longer an excuse to hide behind with today's advances in processor performance. The limitations of current algorithms are illustrated for a number of applications, ranging from visibility analysis to data compression.

A regular grid digital elevation model (DEM) represents the heights at discrete samples of a continuous surface. As such, there is not a direct topological relationship between points; however, for a variety of reasons, users consider these elevations to lie at the vertices of a regular grid, thus imposing an implicit representation of surface form. For most GIS, a linear relationship between 'vertices' is assumed, while a bilinear representation is assumed within each DEM 'cell'. The consequences of imposing such assumptions can be critical for those applications that interpolate unsampled points from the DEM. The first part of the paper demonstrates the problems of interpolation within a DEM and evaluates a variety of alternative approaches such as bi-quadratic, cubic, and quintic polynomials and splines that attempt to derive the shape of the surface at interpolated points.

Extrapolation is an extension of interpolation to locations outside the current spatial domain. One can think of extrapolation as "standing in the terrain and given my field of view, what is my elevation at a location one step backwards?" This approach to elevation prediction is at the heart of many new techniques of data compression that are applied to DEMs. The demand for better data compression algorithms is a consequence of finer resolution data, e.g. LiDAR, and the wider dissemination of DEMs by intranet and internet. In a similar manner to the interpolation algorithms, the basis of elevation prediction is to determine the local surface form by correlating values within the 'field of view'. The extent of this field of view can be the nearest three DEM vertices that are used to bilinearly determine the next vertex. The second part of the paper evaluates this approach for more extensive fields of view, using both linear and non-linear techniques.

Reference:

IV International Conference on GeoComputation, Mary Washington College, Fredericksburg, VA, USA, 25-28 July 1999.