Terrain Elevation Data Operations in Computational Cartography

Terrain Elevation

1. gridded (in a matrix),
2. Triangulated Irregular Network (TIN),
3. contours.

Variations

1. combined with a spline,
2. lossily compressed, (Said and Pearlman's wavelets)

1. RMS error,
2. the accuracy of derivative properties such as
1. visibility indices, and
2. drainage patterns.

So What's New?

• data (1 meter grid soon),
• hardware,
• algorithms.

Special or General Algorithm?

Question: Use a special-purpose compression algorithm (say, TIN) or general-purpose (image processing algorithms)?

Reflect on: Lisp machines, floating point processors, database engines, special graphics engines, and parallel machines. Dead!

A lot of money has been spent improving general-purpose compression algorithms.

Sample Data

• 24 USGS DEMs
• Alphabetically the first starting with each letter: A-W,Y. (No cells start with X or Z).
• 1201x1201 elements.

Lossy Compression

• Use progcode.
• User specifies bpp (bits per point). One bpp is 1201x1201/8=180300 bytes.
• Try 0.005, 0.010, 0.015, 0.02 (0.02) up to lossless rate.
• Next image shows bpp vs RMS elevation error for first 12 DEMs, and the stdev of the original elevations.

Hailey-E, Lossless

Hailey-E, 0.03 bpp

Hailey-E, 0.005 bpp

Compressing Hurts Interactivity?

• Don't want to have to decompress whole cell to use only a piece.
• Partition, then compress blocks separately?
• Does total compressed size grow? (Not much. gzip sometimes shrinks.)
• What is variance of compressed sizes? (Maybe a problem.)

Effect on Visibility Index

• For each of the 1201x1201 points (observers) in cell, fire 16 rays out to distance of 50 points to estimate fraction of targets within that range that are visible from that point. Observer and target heights are 10.
• Result is a number from 0 to 100 for each point, i.e., a new image. 25-, 50-, 75- percentiles are 38, 50, 62.
• Next slides show visibility indices of the original Hailey-E cell, and of it when compressed to 0.03 bpp, or 5409 bytes.

Hailey-E, Visibility Indices

Hailey-E, 0.03 bpp, Visibility Indices

Quantify that?

• 25-percentile: 2.3 (out of 100).
• median: 5.7.
• 75-percentile: 11.

• 25-percentile: 0.75.
• median: 1.5.
• 75-percentile: 3.8.

Transformations: Contour to Gridded

1. An old problem, but
2. We can do it better.
3. Mike Gousie's PhD work.

Techniques

1. Lagrangian PDE: the surface ``droops'' unacceptably between the contour lines.
2. Thin plate equation: Generated surfaces oscillate.
3. Other PDEs?
4. Interpolating gradients (lofting)
5. Interpolating Splines:
6. Techniques From Medical Imaging: No.
7. {Interpolation by Compression}

Transformations: Gridded to Planar TIN

1. I did it first (1973).
2. TINs are obvious.
3. Do they deserve their reputation?

1. Inherently lossy.
2. Topology takes space.
3. Surprisingly hard to implement
4. Even when implemented correctly, the topology can take ten times as much storage as the heights. This seems excessive. Experimenting with the succinct data structures mentioned above is a possible future research area.
5. Probably, in the limit, all compression methods would take the same space for the same accuracy.
6. The remaining question would be algorithm complexity and programmer time.

Planar TIN to Spline TIN

1. No new info, but
2. Might increase accuracy.
3. Real world not always $C^0$.

Transformations: Gridded to Visibility

1. Where to play the good guys to watch the bad guys?
2. Clark Ray's PhD thesis

N37E127 DTED Cell

Visibility Index For Each Point

Visibility Index vs Elevation of Some Random Points

Visibility Indices to Features

Negative of Visibility Index of Baboon

Fitting the Pieces Together

Towards a General Model of Surfaces

1. Is available data statistically representative of the real world?
2. Much existing input, e.g., autocorrelations or fractals.
3. With enough parameters, anything works, c.f., Ptolemaic planetary model.
4. Shallow or deep model?

Implementation Details

1. Sun Sparc IPC and 10/30 workstations,
2. SunOS Unix,
3. about 32MB of memory,
4. C++ with the Apogee compiler.
5. Tomas Rokicki's dvips,
6. Jef Poskanzer's Portable Bit Map (PBM) package, Netpbm version,
7. John Bradley's xv.

Conclusions

1. Unified view of various terrain representation data structures.
2. Sometime generic (IP) algorithms are best.
3. Multimedia research is forcing continuous research: better algorithms in the future.
4. Future: Effect of compression on drainage etc.