The Robust Compression of Digital Elevation Models

  • Lesley Hughes

    Student thesis: Doctoral Thesis


    The representation of terrain by a regular grid Digital Elevation Model (DEM) requires a large amount of data which increases with the resolution. The nature of the typical applications of terrain data, for example, aeronautical navigation, dictates that the reliability of the data is of prime importance. Thus any compression scheme used for compressing OEMs, in the presence of errors, must be able to achieve competitive compression while retaining a level of accuracy in the decompressed data. The requirements for effective data compression and error control tend to conflict. In some situations, for example, mobile storage devices used in hostile environments, the use of both techniques is essential. In this research the use of data compression for a storage channel subject to error is considered. The suitability of some standard data compression techniques (statistical and dictionary based methods) for robust terrain compression, is examined. The results indicate, as expected, that these methods,
    as they stand, are unable to tolerate any error in the compressed data.

    Five possible methods for the robust progressive compression of terrain data, based on common image and other compression methods, are developed and implemented. The five methods are a bit splitting method, a grid interpolation method, a discrete cosine transform based method, a vector quantization based method and a linear quadtree method. All methods are used in conjunction with a statistical encoder. Each method identifies the information critical for obtaining a good approximation to the original terrain, and thus the information which requires strong error control. It is shown that grid interpolation is the natural choice for lossless robust DEM compression.

    A progressive strategy which incorporates various levels of data is employed. The levels are formed by down-sampling the data to form a coarse and fine grid of elevations. Grid interpolation techniques are then employed to obtain an approximation of the fine grid from the coarse grid. The corrections to this approximation are then compressed using an arithmetic encoder. This process is done repeatedly to produce the required number of levels. Protection is achieved primarily through the use of BCH codes. The protection is incorporated in such a way that the coarsest levels of data receive stronger error control. Secondary error detection mechanisms exist through the use of the arithmetic encoder and also some prior knowledge of the compressed data.

    The software developed here proves to be successful with regard to progressively reconstructing terrain in the presence of errors, while also producing compression results which compare favourably with theoretical results based on a known DEM compression method.

    Consideration is also given to the task of validating the decompressed data, and determining if terrain data may be distinguished from other digital data. A series of tests which use the grid interpolation and DCT methods discussed previously are used, along with Moran's Index, to measure spatial auto correlation. Local tests based on image processing techniques (edge and point detection masks) are also employed to detect any anomalies in data which may otherwise be classified as terrain. The results indicate that while the differentiation of terrain and uncorrelated data is a relatively straightforward task, the task of distinguishing between terrain data and other correlated data provides great scope for further research.
    Date of AwardDec 2000
    Original languageEnglish


    • Digital mapping

    Cite this