To appear
Previous: 1 Introduction
This review will first consider data compression and entropy, then effects of errors in DEMS on interesting properties, and finally other operations on DEMs, which might be affected by errors.
For an excellent introduction to data compression in general, see the Usenet comp.compression Frequently Asked Questions file (FAQ)[12]. It discusses Huffman, Lempel-Ziv-Welch (LZW), JPEG, and others, and gives references. Nelson[23] is a good introduction to the standard compression algorithms, and includes floppies with code. Whitten[39] describes a suite of programs for text and image compression. One non-technical issue inhibiting optimal compression is the large number of patents on the most popular methods.
Burrough[1] and Peuquet[25] consider data compression issues in GIS. Fractals, as presented in Clarke and Schweizer[6], might also be used to compress terrain. Neumann[24] introduces information issues, such as entropy, in representing the topological relations in a map.
Carter[2] describes the errors in the 
DEMs,
produced by interpolating contours on 1:250K maps, which we use
in this study. Walsh et al[36] also discuss this
problem.
Weibel[38] filters gridded DEMs in various ways. He
uses global filtering doing smoothing as in image processing by
convolving with a 
or 
filter. He compares
this with a selective filtering to eliminate points that do not
add anything to our characterization of the surface. He tests a
elevation grid to see whether generalization changes
essentials of the terrain, such as hill sharing and RMS error.
Shea and McMaster[32] also discuss generalization.
Chang and Tsai[4] found that lowering DEM resolution hurt the accuracy of the calculated slope and aspect of the terrain. Carter[3] shows that the 1 meter resolution particularly affects the aspect, causing a bias towards the four cardinal directions, and suggests smoothing the data. Lee et al[19] analyze the effect of elevation errors on feature extraction. Fisher[10] considers the effect on visibility.
One operation often performed on terrain data is visibility
determination, De Floriani and Magillo[7]. Puppo et
al[26] use a parallel machine to convert a DEM to a TIN.
They scale the elevation to 8 bits and perform experiments on
grids of up to 
, reporting results for a
grid. For example, for a 30 meter accuracy 497 of
the 16,384 points are selected. This TIN is then used to calculate
line-of-sight-communication in De Floriani et al[8].
Drainage pattern determination is another frequent DEM operation, as described by McCormack et al[22]. Skidmore[33] extracts properties of a location, such as being on a ridge line, from a DEM. Franklin and Ray[11,27] do visibility calculations on large amounts of data.
The use of a linear quadtree with 2-D run-length encoding and
Mortin sequences is discussed in Mark and
Lauzon[21]. The storage can be about 7 bits per
leaf. Waugh[37] critically evaluates when quadtrees
are useful, while Chen and Tobler[5] find that
quadtrees always require more space for a given accuracy than a
ruled surface. Dutton[9] presents a region quadtree
based on triangles, not squares. This quaternary triangular
mesh defines coordinates on a quasi-spherical world better than a
planar, Cartesian, system does. Leifer and Mark[20]
use orthogonal polynomials of order up to 6 and quadtrees for a lossy
compression of three 
DEMs. Their work anticipates
ideas used in wavelets and in the best methods that we will see
later in this paper.
To appear
Previous: 1 Introduction