Compressing the Data for Digital Elevation Databases

The use of a Digital Elevation Database poses a special problem when the Database is used to aid a pilot flying an aircraft. (We're talking a Real Aircraft, not a simulation.)

An error in the Database can result in the pilot flying into the terrain, killing everyone onboard the aircraft.

This is especially true when the Digital Elevation Database is compressed using a lossy compression method.

While the use of a lossless compression method avoids this potentially fatal consequence, lossless compression methods do not produce as much data compression as do lossy methods (unless it is a lousy lossy method).

Lossy compression methods such as the Discrete Cosine Transform (DCT) method have been used. The DCT method smoothes over the data, leading to the possibility that a pilot could fly into terrain that had been smoothed over.

I have two patents on methods for the compression of Digital Elevation Database data that, while lossy, preserve the data necessary to warn the pilot of potentially dangerous terrain.

In U.S. Patent 6,023,278  issued February 8, 2000,  I take the original Digital Elevation Database (composed of rows and columns and elevations) and omit selected rows and columns. This forms a new database of rows and columns, which can be considered cells with four corners. However, I add a center point to each new cell. The center point can be derived in several ways. The one that is of most interest here is where the center point is selected to be the highest elevation of the points in the original uncompressed cell.

This is what provides the new compressed polygon database with the information necessary to alert the pilot of the maximum elevation of the terrain in each cell.

Each cell is rectangular with a point in the center. This center point is used to create four three-dimensional triangles. Each triangle is formed from the center point and two adjacent corner points.

I suggest you see for yourself.

About the drawings:

The drawings showing the 3D digital terrain maps made for this and the other patents were produced by a variety of methods.

Some of the drawings were rejected by the Patent Draftspersons for one reason or another, but were eventually accepted.

But, regardless of how good I made the drawings, the USPTO Contractor responsible for printing patents did a very poor job reproducing the drawings. Presumably this was either because they are under pressure to get the patents out or because they scanned the drawings at low resolution.

Therefore, in addition to the issued patent drawings, I am posting the drawings I consider especially representative in high resolution form.

U.S. Patent 6,023,278
Digital map generator and display system

Full Patent Image  (2.9 MB  PDF)
Figures 7, 9, 12, and 13 
High Resolution  (596 KB  PDF)

My second patent for compressing the data for Digital Elevation Databases, and which,  while lossy, also preserves the data necessary to warn the pilot of potentially dangerous terrain is:

U.S. Patent  5,974,423
Method for converting a digital elevation database to a polygon database

Full Patent Image  (1.6 MB  PDF)
Figures 13, 14, and 15
High Resolution (493 KB  PDF)

My third patent for compressing the data for Digital Elevation Databases is also lossy, and does not preserve the data necessary to avoid running into things.

Do not use it for flying an aircraft.

But, it would be good in a video game or an online 3D terrain map overlaid with a street map.

U.S. Patent 6,177,943

Full Patent Image  (1.8 MB  PDF)
Figures 6, 9, 12, and 16
High Resolution  (575KB  PDF)

Copyright 2001 Jed Margolin

Please send comments here