The elevation pyramid: a method for compressing elevation data

A quadtree-like representation for storing gridded elevation data is described. In its simplest form, the data structure is a pyramid with each node containing a two bit code. The root of the pyramid has associated with it the minimum elevation for the grid and the range (the greatest power of 2 less than or equal to the difference between the minimum and maximum elevation values). Any specified elevation value is determined by traversing a path from the root to a leaf node. As the traversal proceeds, the minimum and range values are refined by interpreting the codes stored at each node along the path. At the leaf level, the final minimum value equals the associated elevation value. Since the total number of nodes in the pyramid is 4/3 the number of elevation grid cells, the amortized storage cost is less than 3 bits per grid cell. When the difference between elevation values is not "too great", this basic representation is quite effective. For data where greater elevation differences occur between neighboring cells, this basic method is modified to improve the representation, but at a cost in storage. Our method is most appropriate for efficient secondary storage archival, such as on CD-ROM. It also allows efficient retrieval of complete elevation data from any subregion, at multiple scales, within the entire elevation database.