Global Elevation Data Adaptive Compression Algorithms

These algorithms can be used in applications requiring large databases of graphical information that are deployed via restricted environments, such as tablets and smartphones.

The Global Elevation Data Adaptive Compression Algorithms (GEDACA) were developed 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. The data is formatted to be accessible anywhere in the world in real time, and also allows for control of data resolution to support the complete range of high-performance aircraft operations. Other uses include applications that require large databases of graphical information and are deployed via restricted environments, such as tablets and smartphones.

Terrain Maps generated by the GEDACA software.
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.

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.

Generally, the more accurate a DTM, 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.

This work was done by Shaun McWherter, Mark Skoog, Jamie Willhite, Loyd Hook, and K. Patterson of Armstrong Flight Research Center. DRC-009-008