Text Size

Global Elevation Data Adaptive Compression Algorithms

 
Terrain maps generated by the Global Elevation Data Adaptive Compression Algorithms

    › Benefits
    › Applications
    › Technology Details
    › Commercial Opportunity
    › Contact Information
    › Download PDF

Software Provides Greater Compression, Faster Decompression of Digital Terrain Maps

Innovators at NASA’s Dryden Flight Research Center developed the Global Elevation Data Adaptive Compression Algorithms (GEDACA) to provide compression and rapid decompression of digital terrain maps (DTMs) in constrained computing environments. The primary purpose of these algorithms is to create and utilize highly compressed digital terrain data representing the geographical areas of the entire world to enable Automatic Ground Collision Avoidance Systems (Auto-GCAS) for high-performance fighter aircraft. Because of the data requirements that these systems and platforms must meet, the data must be formatted to be accessible anywhere in the world in real-time while also allowing for control of data resolution to support the complete range of high-performance aircraft operations. Other uses for this patent-pending technology include applications that require large databases of graphical information and are deployed via restricted environments such as tablets and smart phones.

Benefits

  • Effective: Controls error induction maximums for user-defined geographical areas from lossless to infinite and incorporates different areas seamlessly in a single compressed DTM
  • Fast: Performs rapid, high-performance decompression in real-time constrained computing environments
  • Powerful: Integrates more than 250 billion separate pieces of terrain information into a single compressed DTM
  • Customized: Supports various requirements with customizable map boundaries and error accounting
  • Proven: Features technology flown and tested on several different platforms including high-performance fighter aircraft
  • Economical: Enables implementation on existing aircraft systems without upgrading computer hardware; offers industry standard C, C++ code base and map formats
  • Innovative: Optimizes compression and error induction via adaptive algorithms based on user-defined limits and terrain types

Applications

  • Commercial and military aircraft Auto-GCAS
  • Marine electronic charting systems
  • Weapons guidance systems
  • Mars and lunar landing systems
  • Gaming systems
  • Global positioning systems (GPS)
  • Medical software
  • Any software that rapidly computes line of sight (flight simulation, war games/simulation)
  • Any software that analyzes and plans terrain routes or analyzes continual surfaces

Technology Details

The GEDACA software provides an extensive and highly efficient compression capability for continental and global-scale DTMs, along with a real-time decompression capability to locally decompress and render map data in the vicinity of a fast-moving airplane. A key feature of the innovation is its ability to render local terrain maps in real time for an Auto-GCAS in a high-performance airplane that may need to deviate from a planned flight path due to unexpected and dynamic events.

How It Works

The GEDACA software achieves its high-performance compression and decompression capability using a unique combination of regular and semi-regular geometric tiling allowing for the use of particular benefits of each aspect and the ability to mitigate the drawbacks of others. Geometric facets are fit to the data through linear regression or adaptive regression techniques and arranged in a combination structure. This allows for important slope information to be retained and continuous terrain representation to be generated, enabling the possibility of high-resolution decompression. The maps and decompression logic are integrated into an aircraft’s existing onboard computing environment and operate within the limited memory and computational power constraints that typically characterize flight control and avionics computer systems. Users can adjust compression methods and error tolerances to suit evolving platform and mission requirements. Maps can be tailored to support the missions or flight profiles of a wide range of aircraft including fighters, unmanned aerial vehicles, and general aviation aircraft.

Why It Is Better

Generally, the more accurate a DTM is, the larger the resulting file size, presenting a problem for aircraft flight control systems with constrained computing environments. Because file sizes for accurate and detailed maps are large, few can be stored in an onboard control system at any one time, substantially restricting protection coverage and also introducing the possibility of human error when swapping out maps for different flight paths. Conventional DTM compression techniques used aboard high-performance aircraft typically achieve relatively low compression ratios compared to other graphical compression methods. However for these other methods, the computational complexity of decompression can be high, making them unsuitable for the real-time constrained computing environments found in high-performance aircraft. Using current compression methods, the practicality and cost of implementing systems such as an Auto-GCAS over a wide range of aircraft types is prohibitive.

In contrast, the GEDACA software provides high compression ratios with real-time decompression using a recursive semi-regular tree-based compression that utilizes linear regression geometric tiling. Resulting file sizes fit within the memory limits of flight control systems. Additionally, the ability to selectively tailor information loss for important geographical areas enables high fidelity sections of terrain data to be incorporated seamlessly into the map. This allows for compression trades to be localized and satisfy size requirements for a larger number of applications. Costs are reduced because the innovation enables implementation on existing aircraft systems.

Patent

Dryden has applied for patent protection for this technology.

Commercial Opportunity

This technology is part of NASA’s Innovative Partnerships Office, which seeks to transfer technology into and out of NASA to benefit the space program and U.S. industry. NASA invites companies to consider licensing the Global Elevation Data Adaptive Compression Algorithms (DRC-009-008) for further development and commercial applications.

Contact Information

Julie Holland
PO Box 273, M/S 1100
NASA’s Dryden Flight Research Center
Edwards, CA 93523-0273
Phone: (661) 276-2515
E-mail: julie.a.holland@nasa.gov